Operating System Concepts

Presentation on theme: "Operating System Concepts"— Presentation transcript:

1 Operating System Concepts
Module 4: Processes 进程 Process Concept 进程概念 Process Scheduling 进程调度 Operation on Processes 进程上的操作 Cooperating Processes 协同进程 Interprocess Communication 进程间通信 Operating System Concepts

2 Operating System Concepts
Course Overview Goals: Understanding of OS and the OS/architecture interface/interaction Prerequisites: Data structure, compiler What to expect: We will cover core concepts and issues in lectures In sections, you and your TA will practice paper & pencil problems and talk about the project A significant project(32 学时) 1 Midterms and 1 Final Operating System Concepts

3 Operating System Concepts
Textbook and Topics Operating System Concepts (6th Edition), Silberschatz and Galvin, ISBN: Operating Systems (4th Edition), Stallings, ISBN: (recommand) Operating systems design and implement,Andrew S.Tanenbaum Topics Processes and threads Processor scheduling Synchronization Virtual memory File systems I/O systems Operating System Concepts

4 Operating System Concepts
Today Process Concept 进程概念 Process Scheduling 进程调度 Operation on Processes 进程上的操作 Cooperating Processes 协同进程 Interprocess Communication 进程间通信 Silberschatz Chapter 4 ( ) Operating System Concepts

5 What Is An Operating System?
application (user) operating system hardware A software layer between the hardware and the application programs/users which provides a virtual machine interface: easy and safe A resource manager that allows programs/users to share the hardware resources: fair and efficient A set of utilities to simplify application development Operating System Concepts

6 Abstract View of System Components
Operating System Concepts

7 Operating System Concepts
Why Do We Want An OS? Benefits for application writers Easier to write programs See high level abstractions instead of low-level hardware details E.g. files instead of disk blocks Portability Benefits for users Easier to use computers Can you imagine trying to use a computer without the OS? Safety OS protects programs from each other OS protects users from each other Operating System Concepts

8 Basic computer structure
CPU Memory memory bus I/O bus disk Net interface Operating System Concepts

9 System Abstraction: Processes
A process is a system abstraction: illusion of being the only job in the system hardware: computer operating system: process user: run application create, kill processes, inter-process comm. Multiplexing resources Operating System Concepts

10 Processes: Mechanism and Policy
Creation, destruction, suspension, context switch, signaling, IPC, etc. Policy: Minor policy questions: Who can create/destroy/suspend processes? How many active processes can each user have? Major policy question that we will concentrate on: How to share system resources between multiple processes? Typically broken into a number of orthogonal policies for individual resource such as CPU, memory, and disk. Operating System Concepts

11 Processor Abstraction: Threads
A thread is a processor abstraction: illusion of having 1 processor per execution context application: execution context create, kill, synch. operating system: thread context switch hardware: processor Operating System Concepts

12 Threads: Mechanism and Policy
Creation, destruction, suspension, context switch, signaling, synchronization, etc. Policy: How to share the CPU between threads from different processes? How to share the CPU between threads from the same process? How can multiple threads synchronize with each other? How to control inter-thread interactions? Can a thread murder other threads at will? Operating System Concepts

13 Operating System Concepts
Process Concept 进程概念 An operating system executes a variety of programs: 操作系统执行各种程序 Batch system – jobs 批处理系统 - 作业 Time-shared systems – user programs or tasks 分时系统 - 用户程序或任务 Textbook uses the terms job and process almost interchangeably. 本书使用的名词作业和进程，基本可互换 Process – a program in execution; process execution must progress in sequential fashion. 进程 - 在执行中的程序；进程的执行必须以顺序方式进行 A process includes: 一个进程包括 program counter 程序计数器 stack 栈 data section 数据部分 Operating System Concepts

14 Run Time Storage Organization
Each variable must be assigned a storage class Global (static) variables Allocated in globals region at compile-time Method local variables and parameters 函数和系统调用 Allocate dynamically on stack Dynamically created objects (using new)数据空间 Allocate from heap Objects live beyond invocation of a method Garbage collected when no longer “live” Code 代码 Globals Stack Heap 数据 Memory Operating System Concepts

15 Why Did We Talk About All That Stuff?
Process = system abstraction for the set of resources required for executing a program = a running instance of a program = memory image + registers’ content (+ I/O state) The stack + registers’ content represent the execution context or thread of control Operating System Concepts

16 Operating System Concepts
What About The OS? Recall that one of the function of an OS is to provide a virtual machine interface that makes programming the machine easier So, a process memory image must also contain the OS OS Code Memory Globals Stack Code Globals Heap Stack OS data space is used to store things like file descriptors for files being accessed by the process, status of I/O devices, etc. Heap Operating System Concepts

17 What Happens When There Are More Than One Running Process?
OS Code Globals P0 Stack Heap P1 P2 Operating System Concepts

18 Operating System Concepts
Process State 进程状态 As a process executes, it changes state 进程执行时，改变状态 new: The process is being created. 新建：在创建进程 running: Instructions are being executed. 运行：指令在执行 waiting: The process is waiting for some event to occur. 等待：进程等待某些事件发生 ready: The process is waiting to be assigned to a processor. 就绪：进程等待分配处理器 terminated: The process has finished execution. 终止：进程执行完毕 Operating System Concepts

19 Diagram of Process State 进程状态图
Operating System Concepts

20 Process Control Block (PCB) 进程控制块
The OS manage information for each process in each process table Information associated with each process. 同进程有关的信息 Process state 进程状态 Program counter 程序计数器 CPU registers CPU寄存器 CPU scheduling information CPU调度信息 Memory-management information内存管理信息 Accounting information 计账信息 I/O status information I/O状态信息 Operating System Concepts

21 Process Control Block (PCB) 进程控制块
Operating System Concepts

22 CPU Switch From Process to Process 进程间CPU的切换
Operating System Concepts

23 Process Scheduling Queues 进程调度队列
Job queue – set of all processes in the system. 作业队列 - 在系统中的所有进程的集合 Ready queue – set of all processes residing in main memory, ready and waiting to execute. 就绪队列 - 在主内存中的，就绪并等待执行的所有进程的集合 Device queues – set of processes waiting for an I/O device. 设备队列 - 等待某一I/O设备的进程队列 Process migration between the various queues. 在各种队列之间进程的迁移 Operating System Concepts

24 Ready Queue And Various I/O Device Queues 就绪队列和各种I/O设备队列
Operating System Concepts

25 Representation of Process Scheduling 进程调度的描述
Operating System Concepts

26 Operating System Concepts
Schedulers 调度 Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue. 长程调度（或作业调度）- 选择可以进入就绪队列的进程 Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU. 短程调度（或CPU调度）- 选择可被下一个执行并分配CPU的进程 Operating System Concepts

27 Addition of Medium Term Scheduling 中程调度
Operating System Concepts

28 Operating System Concepts
Schedulers调度(Cont.) Short-term scheduler is invoked very frequently (milliseconds)  (must be fast). 短程调度切换频率高 Long-term scheduler is invoked very infrequently (seconds, minutes)  (may be slow). 长程调度不快 The long-term scheduler controls the degree of multiprogramming. 长程调度控制了多道程序的“道” Processes can be described as either: 进程可以用下列方式描述： I/O-bound process – spends more time doing I/O than computations, many short CPU bursts. I/O型进程 - 花费I/O 时间多于计算，许多短CPU处理 CPU-bound process – spends more time doing computations; few very long CPU bursts. CPU 型进程 - 花费更多时间于计算，许多长CPU处理 Operating System Concepts

29 Operating System Concepts
Context Switch 上下文切换 When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process. 当CPU切换至另一个进程时，系统必须保存旧进程状态并为新进程调入所保留的状态 Context-switch time is overhead; the system does no useful work while switching. 上下文切换的时间开销较重；在切换时，系统没有做有用的工作 Time dependent on hardware support. 时间取决于硬件的支持 Operating System Concepts

30 Operating System Concepts
Process Creation 进程创建 Parent process creates children processes, which, in turn create other processes, forming a tree of processes. 父进程创建子进程，如此轮流创建进程下去，构成一个进程树 Resource sharing 资源共享 Parent and children share all resources. 父进程子进程共享所有的资源 Children share subset of parent’s resources. 子进程共享父进程资源的子集 Parent and child share no resources. 父进程和子进程无资源共享 Execution执行 Parent and children execute concurrently. 父进程和子进程并发执行 Parent waits until children terminate. 父进程等待，直到子进程终止 Operating System Concepts

31 Process Creation (Cont.) 进程创建
Address space 地址空间 Child duplicate of parent. 子女复制双亲 Child has a program loaded into it. 子女有一个程序被调入 UNIX examples UNIX例子 fork system call creates new process fork 系统调用创建新进程 execve system call used after a fork to replace the process’ memory space with a new program. 在fork 用一个新程序替代了进程的内存空间之后，采用execve系统调用 Operating System Concepts

32 Operating System Concepts
Process Creation How to create a process? System call. In UNIX, a process can create another process using the fork() system call int pid = fork(); /* this is in C */ The creating process is called the parent and the new process is called the child The child process is created as a copy of the parent process (process image and process control structure) except for the identification and scheduling state Parent and child processes run in two different address spaces By default, there’s no memory sharing Process creation is expensive because of this copying The exec() call is provided for the newly created process to run a different program than that of the parent Operating System Concepts

33 Operating System Concepts
Process Creation fork() code exec() PCBs fork() Operating System Concepts

34 Example of Process Creation Using Fork
The UNIX shell is command-line interpreter whose basic purpose is for user to run applications on a UNIX system cmd arg1 arg2 ... argn Operating System Concepts

35 A Tree of Processes On A Typical UNIX System 典型UNIX系统中的进程树
Operating System Concepts

36 Process Termination 进程终止
Process executes last statement and asks the operating system to decide it (exit).进程执行的最后一项并询问操作系统作出决定（退出） Output data from child to parent (via wait). 从子进程向父进程输出数据）（通过等待） Process’ resources are deallocated by operating system. 操作系统收回进程的资源 Parent may terminate execution of children processes (abort). 父进程可中止子进程的执行（终止） Child has exceeded allocated resources.子进程超量分配资源 Task assigned to child is no longer required. 赋予子进程的任务不再需要 Parent is exiting. 父进程 Operating system does not allow child to continue if its parent terminates. 若父进程终止，不允许子进程继续 Cascading termination. 级联终止 Operating System Concepts

37 Process Creation/Destruction in Java
In Java, this API is hidden in the java.lang.Runtime and java.lang.Process classes import java.lang.* … Runtime rt = Runtime.getRuntime(); // get runtime Process child = rt.exec(“loop-forever-program”); // create child child.destroy(); // kill child Operating System Concepts

38 Cooperating Processes 协同进程
Independent process cannot affect or be affected by the execution of another process. 独立进程不会影响另一个进程的执行或被另一个进程执行影响 Cooperating process can affect or be affected by the execution of another process 协同进程可能影响另一个进程的执行或被另一个进程执行影响 Advantages of process cooperation 进程协同的优点 Information sharing 信息共享 Computation speed-up 加速运算 Modularity 模块化 Convenience 方便 Operating System Concepts

39 Producer-Consumer Problem 生产者-消费者问题
Paradigm for cooperating processes, producer process produces information that is consumed by a consumer process. 生产者进程生产供消费者进程消费的信息 unbounded-buffer places no practical limit on the size of the buffer. 无界缓冲没有对缓冲区大小的限制 bounded-buffer assumes that there is a fixed buffer size. 有界缓冲对缓冲区大小作了限定 Operating System Concepts

40 Bounded-Buffer – Shared-Memory Solution
Shared data #define BUFFER_SIZE 10 Typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; Solution is correct, but can only use BUFFER_SIZE-1 elements Operating System Concepts

41 Bounded-Buffer – Producer Process
item nextProduced; while (1) { while (((in + 1) % BUFFER_SIZE) == out) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; } Operating System Concepts

42 Bounded-Buffer – Consumer Process
item nextConsumed; while (1) { while (in == out) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; } Operating System Concepts

43 Interprocess Communication (IPC) 进程间通信
Mechanism for processes to communicate and to synchronize their actions.用于进程通信的机制，同步其间的活动 Message system – processes communicate with each other without resorting to shared variables. 消息系统 - 进程间通信无须对共享变量进行再分类 IPC facility provides two operations IPC提供两个操作 : send(message) – message size fixed or variable 发送 - 固定或可变大小消息 receive(message)接受 If P and Q wish to communicate, they need to 若P与Q要通信，需要: establish a communication link between them 建立通信连接 exchange messages via send/receive 通过send/receive交换消息 Implementation of communication link 通信连接的实现 physical (e.g., shared memory, hardware bus)物理的（如，共享存储，硬件总线） logical (e.g., logical properties)逻辑的（如，逻辑特性） Operating System Concepts

44 Implementation Questions 实现中的问题
How are links established? 连接如何建立？ Can a link be associated with more than two processes? 连接可同多于两个的进程相关吗？ How many links can there be between every pair of communicating processes? 每对在通信进程有多少连接？ What is the capacity of a link? 一个连接的容量是多少？ Is the size of a message that the link can accommodate fixed or variable? 连接可使用的固定或可变消息的大小？ Is a link unidirectional or bi-directional? 连接是无向的还是双向的？ Operating System Concepts

45 Direct Communication 直接通信
Processes must name each other explicitly: 进程必须显式的命名 send (P, message) – send a message to process P向进程P发消息 receive(Q, message) – receive a message from process Q从进程Q收消息 Properties of communication link 通信连接的特性 Links are established automatically. 连接自动建立 A link is associated with exactly one pair of communicating processes. 连接精确的与一对在通信的进程相关 Between each pair there exists exactly one link. 在每一对之间就存在一个连接 The link may be unidirectional, but is usually bi-directional. 连接可以无向，但通常是双向的 Operating System Concepts

46 Indirect Communication间接通信
Messages are directed and received from mailboxes (also referred to as ports).消息导向至信箱并从信箱接收（被视作端口） Each mailbox has a unique id. 每一个信箱有一个唯一的id Processes can communicate only if they share a mailbox. 仅当共享一个信箱时进程才能通信 Properties of communication link 通信连接的特性 Link established only if processes share a common mailbox 仅当进程共有一个信箱时连接才能建立 A link may be associated with many processes.连接可同多个进程相关 Each pair of processes may share several communication links. 每一对进程可共享多个通信连接 Link may be unidirectional or bi-directional.连接可是无向或双向的 Operations操作 create a new mailbox 创建新的信箱 send and receive messages through mailbox 通过信箱发送和接收消息 destroy a mailbox 销毁信箱 Operating System Concepts

47 Indirect Communication (Continued) 间接通信
Mailbox sharing 信箱共享 P1, P2, and P3 share mailbox A. P1, P2与P3共享信箱A P1, sends; P2 and P3 receive. P1发送； P2与P3接受 Who gets the message?谁得到消息？ Solutions 解决方案 Allow a link to be associated with at most two processes. 允许一个连接最多同2个进程相关 Allow only one process at a time to execute a receive operation. 只允许一个时刻有一个进程执行接受操作 Allow the system to select arbitrarily the receiver. Sender is notified who the receiver was. 允许系统任意选择接收者。发送者被通知谁是接收者。 Operating System Concepts

48 Operating System Concepts
Buffering 缓冲 Queue of messages attached to the link; implemented in one of three ways. 消息队列附加在连接上；采用三个之一的实现方案 1. Zero capacity – 0 messages 零容量 - 0 消息 Sender must wait for receiver (rendezvous). 发送者必须等待接收者 2. Bounded capacity – finite length of n messages 有界容量 - n个消息有限长度 Sender must wait if link full. 若连接满了发送者必须等待 3. Unbounded capacity – infinite length 无界容量 - 无限长度 Sender never waits. 发送者从不等待 Operating System Concepts

49 Client-Server Communication
Sockets 套接字 Remote Procedure Calls 远端系统调用 Operating System Concepts

50 Operating System Concepts
Sockets A socket is defined as an endpoint for communication. 套接字定义成通讯中的端 Concatenation of IP address and port 与ip地址和端口相关 The socket :1625 refers to port 1625 on host Communication consists between a pair of sockets. Operating System Concepts

51 Operating System Concepts
Socket Communication Operating System Concepts

52 Remote Procedure Calls
Remote procedure call (RPC) abstracts procedure calls between processes on networked systems. RPC是网络系统中进程之间的系统调用的抽象 Stubs – client-side proxy for the actual procedure on the server. Stub为服务器端客户程序的代理 The client-side stub locates the server and marshalls the parameters. The server-side stub receives this message, unpacks the marshalled parameters, and peforms the procedure on the server. Operating System Concepts

53 Operating System Concepts
Execution of RPC Operating System Concepts

54 Remote Method Invocation
Remote Method Invocation (RMI) is a Java mechanism similar to RPCs. RMI allows a Java program on one machine to invoke a method on a remote object. Operating System Concepts

55 Marshalling Parameters
Operating System Concepts

56 Exception Conditions – Error Recovery 异常条件 - 出错恢复
Process terminates 进程终止 Lost messages 消息丢失 Scrambled Messages 消息受损 Operating System Concepts

57 Operating System Concepts
Process: Summary An “instantiation” of a program System abstraction: the set of resources required for executing a program Execution context(s) Address space File handles, communication endpoints, etc. Historically, all of the above “lumped” into a single abstraction More recently, split into several abstractions Threads, address space, protection domain, etc. OS process management: Supports user creation of processes and interprocess communication (IPC) Allocates resources to processes according to specific policies Interleaves the execution of multiple processes to increase system utilization Operating System Concepts

58 Operating System Concepts
Next Time Threads Read Silberschatz Chapter 5 Operating System Concepts