1.1 Applied Operating System Concepts Chap 4 Processes 进程

1.2 Applied Operating System Concepts Contents 内容 Process Concept 进程概念 Process State 进程状态 Process Control Block (PCB) 进程控制块 Process Scheduling 进程调度 Operation on Processes 进程上的操作 Cooperating Processes 协同进程 Interprocess Communication 进程间通信 Summary( 总结 ) Homework 作业

1.3 Applied 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, task and process almost interchangeably. 本书使用的名词作业和进程，基本可互换 Job: A set of computational steps package to run as a unit. 作业：被组装成一个整体运行的一组计算步骤。 Task: as process. Process – a program in execution; process execution must progress in sequential fashion. 进程 - 在执行中的程序；进程的执行必须以顺序方式进行

1.4 Applied Operating System Concepts Process Sample: Suse Linux 进程例子： Suse Linux

1.5 Applied Operating System Concepts Process Sample: Windows XP 进程例子： Windows XP

1.6 Applied Operating System Concepts Process Concept 进程概念 ( 续 ) A process includes: 一个进程包括 Text Section( Code) 代码部分 PCB 进程控制块 Stack 栈 Data Section 数据部分 The difficult between process and program 进程和程序的区 别 进程是程序的一个实例，是程序的一次执行 进程是活动的，程序相当是静止的 程序是进程的代码部分 进程在内存中，程序在外存中

1.7 Applied 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. 终止：进程执行完毕

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

1.9 Applied Operating System Concepts Transition of Process state 进程状态转换 NULL—>New: 空 —> 新建 New —>Ready ：新建 —> 就绪 Ready —>Running ：就绪 —> 运行 Running—>Blocked: 运行 —> 阻塞 Running—> Ready : 运行 —> 就绪 Running—>Exit : 运行 —> 退出 Blocked—> Ready ：阻塞 —> 就绪 Ready —>Exit ：就绪 —> 退出 Blocked—> Exit ：阻塞 —> 退出

1.10 Applied Operating System Concepts A Sample of Process State Changing 进程状态转换例子 进程 1 进程 2 进程 3 调度模块 运行 阻塞 就绪

1.11 Applied Operating System Concepts 思考 ? 1. 如果系统中有 N 个进程，运行的进程最多几 个，最少几个；就绪进程最多几个最少几个； 等待进程最多几个，最少几个？ 2. 有没有这样的状态转换，为什么？ 等待 —> 运行 ； 就绪 —> 等待 3. 一个状态转换的发生，是否一定导致另一个 转换发生，列出所有的可能。

1.12 Applied Operating System Concepts Process State of Linux Linux 进程状态 Structure task_struct : TASK_RUNNING: 进程准备运行，不仅有一个进程 TASK_INTERRUPTIBLE: 进程等待特定事件 TASK_UNINTERRUPTIBLE: 进程等待硬件条件 TASK_ZOMBIE: 进程已经退出 TASK_STOPPED: 进程已经停止运行, 但在内存仍有结构

1.13 Applied Operating System Concepts Process State of Linux （ Cont. ） Linux 进程状态（续） 停止 就绪执行 不可中断 可中断 僵死

1.14 Applied Operating System Concepts Process Control Block (PCB) 进程控制块 PCB contains many piece of Information associated with each process. It defines the state of the process. PCB 包含同进程有关的信息，定义了进程的状态。 Including these: 包括： Process state 进程状态 Program counter 程序计数器 CPU registers CPU 寄存器 CPU scheduling information CPU 调度信息 Memory-management information 内存管理信息 Accounting information 计账信息 I/O status information I/O 状态信息

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

1.16 Applied Operating System Concepts PCB List Structure PCB 链表结构 运行 就绪 阻塞 进程控制块进程控制块 进程控制块进程控制块 进程控制块进程控制块 进程控制块进程控制块 进程控制块进程控制块 进程控制块进程控制块

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

1.18 Applied Operating System Concepts 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. 在各种队列之间进程的迁移

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

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

1.21 Applied 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 的进程

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

1.23 Applied 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 处理

1.24 Applied 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. 时间取决于硬件的支持

1.25 Applied 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. 父进程等待，直到子进程终止

1.26 Applied Operating System Concepts 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 系统调用 Atomic operation

1.27 Applied Operating System Concepts 实例： UNIX_wait 演示子进程与父进程的关系和 fork 、 exec 、 wait 的使用； 程序 main.c 功能是进行 10 次循环，创建 2 个子进程。循环到第 3 次时，等待子进程结 束。 #include pid_t wait(int *stat_loc); void perror(const char *s); #include int errno; int global;

1.28 Applied Operating System Concepts main() { int local,i; pid_t child; if ((child=fork()) == -1) {// 创建失败 printf("Fork Error.\n"); } if (child == 0) {// 子进程 printf("Now it is in child process.\n"); if (execl("/home/xyong/work/ttt","ttt",NULL) == -1) {// 加载程序失败 perror("Error in child process"); } global=local + 2; exit(); } 实例： UNIX_wait （续）

1.29 Applied Operating System Concepts // 父进程 printf("Now it is in parent process.\n"); for (i=0; i<10; i++) { sleep(2); printf("Parent:%d\n",i); if (i==2) { if ((child=fork()) == -1) {// 创建失败 printf("Fork Error.\n"); } if (child == 0) {// 子进程 printf("Now it is in child process.\n"); if (execl("/home/xyong/work/ttt","ttt",NULL) == -1) {// 加载程序失败 perror("Error in child process"); } global=local + 2; exit(); } 实例： UNIX_wait （续）

1.30 Applied Operating System Concepts if (i==3) { pid_t temp; temp=wait(NULL); printf("Child process ID: %d\n", temp); } global=local + 1; exit(); } 实例： UNIX_wait （续）

1.31 Applied Operating System Concepts 程序 test.c #include pid_t getpid(void); pid_t getppid(void); int global; main() { int local; int i; pid_t CurrentProcessID, ParentProcessID; CurrentProcessID=getpid(); ParentProcessID=getppid(); printf("Now it is in the program TEST.\n"); for (i=0; i<10; i++) { sleep(2); printf("Parent: %d, Current: %d, Nunber:%d\n",ParentProcessID, CurrentProcessID,i); } global=local + 1; exit(); } 功能是进行 10 次循环。

1.32 Applied Operating System Concepts 程序 test.c 结果 Parent: 7072, Current: 7074, Nunber:4 Parent: 7072, Current: 7073, Nunber:8 Parent: 7072, Current: 7074, Nunber:5 Parent: 7072, Current: 7073, Nunber:9 Child process ID: 7073 Parent: 7072, Current: 7074, Nunber:6 Parent:4 Parent: 7072, Current: 7074, Nunber:7 Parent:5 Parent: 7072, Current: 7074, Nunber:8 Parent:6 Parent: 7072, Current: 7074, Nunber:9 Parent:7 Parent:8 Parent:9 Now it is in parent process. Now it is in child process. Now it is in the program TEST. Parent:0 Parent: 7072, Current: 7073, Nunber:0 Parent:1 Parent: 7072, Current: 7073, Nunber:1 Parent:2 Parent: 7072, Current: 7073, Nunber:2 Now it is in child process. Now it is in the program TEST. Parent: 7072, Current: 7073, Nunber:3 Parent:3 Parent: 7072, Current: 7074, Nunber:0 Parent: 7072, Current: 7073, Nunber:4 Parent: 7072, Current: 7074, Nunber:1 Parent: 7072, Current: 7073, Nunber:5 Parent: 7072, Current: 7074, Nunber:2 Parent: 7072, Current: 7073, Nunber:6 Parent: 7072, Current: 7074, Nunber:3 Parent: 7072, Current: 7073, Nunber:7

1.33 Applied Operating System Concepts NT 线程的挂起和激活 NT 中处理机的分配对象为线程，一个线程可被多次挂起和 多次激活。在线程内有一个挂起计数（ suspend count ），挂 起操作使该计数加 1 ，激活操作便该计数减 1 ；当挂起计数 为 0 时，线程恢复执行。 (1) 挂起： Windows NT 中的 SuspendThread 可挂起指定的线 程； DWORD SuspendThread( HANDLE hThread // handle to the thread ); (2) 激活： Windows NT 中的 ResumeThread 可恢复指定线程 的执行； DWORD ResumeThread( HANDLE hThread // identifies thread to restart );

1.34 Applied Operating System Concepts 例子 NT_thread.cpp #include void SubThread(void) { int i; for (i=0;i<5;i++) { cout << "SubThread" << i << endl; Sleep(2000); }

1.35 Applied Operating System Concepts void main(void) { cout << "CreateThread" << endl; // Create a thread; DWORD IDThread; HANDLE hThread; hThread = CreateThread(NULL, // no security attributes 0, // use default stack size (LPTHREAD_START_ROUTINE) SubThread, // thread function NULL, // no thread function argument 0, // use default creation flags &IDThread); // returns thread identifier // Check the return value for success. if (hThread == NULL) cout << "CreateThread error" << endl; 例子 NT_thread.cpp （续）

1.36 Applied Operating System Concepts int i; for (i=0;i<5;i++) { cout << "MainThread" << i << endl; if (i==1){ if (SuspendThread(hThread)==0xFFFFFFFF) { cout << "Suspend thread error." << endl; }else{ cout << "Suspend thread is ok." << endl; } if (i==3){ if (ResumeThread(hThread)==0xFFFFFFFF) { cout << "Resume thread error." << endl; }else{ cout << "Resume thread is ok." << endl; } Sleep(4000); } 例子 NT_thread.cpp （续）

1.37 Applied Operating System Concepts 运行结果 CreateThread MainThread0 SubThread0 SubThread1 MainThread1 Suspend thread is ok. MainThread2 MainThread3 Resume thread is ok. SubThread2 SubThread3 MainThread4 SubThread4

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

1.39 Applied Operating System Concepts 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. 级联终止

1.40 Applied Operating System Concepts 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 方便

1.41 Applied Operating System Concepts 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. 有界缓冲对缓冲区大小作了限定

1.42 Applied Operating System Concepts Bounded-Buffer – Shared-Memory Solution 有界缓冲－共享内存解决方案 Shared data var n; type item = … ; var buffer. array [0..n–1] of item; in, out: 0..n–1; Producer process repeat … produce an item in nextp … while in+1 mod n = out do no-op; buffer [in] :=nextp; in :=in+1 mod n; until false;

1.43 Applied Operating System Concepts Bounded-Buffer (Cont.) 有界缓冲（续） Consumer process repeat while in = out do no-op; nextc := buffer [out]; out := out+1 mod n; … consume the item in nextc … until false; Solution is correct, but can only fill up n–1 buffer.

1.44 Applied Operating System Concepts 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) 逻辑的（如，逻辑特性）

1.45 Applied Operating System Concepts 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? 连接是无向的还是双向的？

1.46 Applied Operating System Concepts 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. 连接可以无向，但通常是双向的

1.47 Applied Operating System Concepts 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 销毁信箱

1.48 Applied Operating System Concepts Indirect Communication (Continued) 间接通信 Mailbox sharing 信箱共享 P 1, P 2, and P 3 share mailbox A. P 1, P 2 与 P 3 共享信箱 A P 1, sends; P 2 and P 3 receive. P 1 发送； P 2 与 P 3 接受 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. 允许系统任意选择接收者。发送者被通知谁是接收者。

1.49 Applied 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. 发送者从不等待

1.50 Applied Operating System Concepts Message-passing in Windows NT Windows NT 的消息传递 The mesaage-passing facility in NT is called the local procedure-call facility(LPC). 消息传递机制在 NT 中称为 LPC 。 Windows NT uses a port object to establish and maintain a connection between two processes. NT 通过端口在进程间建立连接。 NT uses two types of ports:connection ports and communication ports. NT 用两种端口：连接端口和通信端口。

1.51 Applied Operating System Concepts Message-passing in Windows NT （ cont. ） Windows NT 的消息传递（续） Communication works as follows: 通信过程如下： The client opens a handle to the subsystem’s connection port object. 客户机打开一个子系统连接端口的句柄。 The client sends a connection request. 客户机发送连接请求。 The server creates two private communication ports,and returns the handle to one of them to the client. 服务器创建 2 个私人的通信端口，返回这两个端口的句柄给客户机。 The client and server use the corresponding port handle to send messages or callbacks and to listen for replies. 客户机和服务器利用这两个端口发送消息并监听回应。

1.52 Applied Operating System Concepts Summary( 总结 ) In this chapter we introduce the concepts of a process and concurrent execution; These concepts are at the very heart of modern operating systems. A process is a program in execution and is the unit of work in a modern time- sharing system. Such a system consists of a collection of processes: Operating-system processes executing system code and user processes executing user code. All these processes can potentially execute concurrently, with the CPU (or CPUs) multiplexed among them. By switching the CPU between processes, the operating system can make the computer more productive. We also introduce the notion of a thread (lightweight process) and interprocess communication (IPC). Threads are discussed in more detail in Chapter 5.

1.53 Applied Operating System Concepts 作业 P