操作系统：第三章 进程管理和处理机管理

1、第三章 进程管理和处理机管理（进程管理）3.1 进程(PROCESS)3.2进程的描述3.3进程的状态及转换3.4 进程控制3.5 进程互斥3.6进程同步3.7 进程间通信3.8 死锁问题3.9 线程的基本概念为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。在本章中，我们将讨论进程概念、进程控制和进程间关系。3.1 进程(PROCESS)3.1.1 程序的顺序执行和并发执行3.1.2 进程的定义返回3.1.1 程序的顺序执行和并发执行程序的执行有两种方式：顺序执行和并发执行。顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；现在的操作系

2、统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。顺序执行的特征顺序性：按照程序结构所指定的次序（可能有分支或循环）封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。并发执行的特征（独立性、随机性、资源共享）间断(异步)性：走走停停，一个程序可能走到中途停下来，失去原有的时序关系；失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。失去可再现性：失去封闭性 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特

3、征。并发执行的条件：达到封闭性和可再现性程序 P(i) 针对共享变量的读集和写集 R(i)和W(i)条件：任意两个程序P(i)和P(j)，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。（这里没有考虑执行速度的影响。）前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。现在的问题是这个条件不好检查。3.1.2 进程的定义它对应虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收；引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加

4、了OS 的复杂性；1. 进程的定义一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。2. 进程的特征动态性：进程具有动态的地址空间（数量和内容），地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块的生成和删除）独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性、异步性：虚拟结构化：代码段、数据段和核心段（在地址空间中）；程序文件中通常也划分了代码段和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）3. 进程与程序的区别进程是动态的，有并行特征；程序是静态的，无并行特征：程序是有序代码的集合；进程是程

5、序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。4. 处理机调度器（dispatcher）把处理机从一个进程切换到另一个进程；防止某进程独占处理机；处理机调度器是操作系统中的一段代码，它完成如下功能： 作业是用户向计算机提交任务的任务实体。用户提交作业后，系统将把它放在外存的作业等待队列中等待执行。 进程是计算机为了完成用

6、户任务实体而置的执行实体，是向系统申请分配资源的基本单位。 一个作业总是由多个进程组成，并且至少由一个进程组成，但反过来不成立。作业的概念主要用于批处理中。5. 作业与进程的关系操作系统核心控制结构是进程结构,资源管理的数据结构将围绕进程结构展开。 MemoryDevicesFilesProcessesMemory TablesI/O TablesFile TablesPrimary Process TableProcess 1Process NProcess 2Process ImageProcess 1ImageProcess NImage进程控制表管理进程及其相关信息3.2 进程的描述操

7、作系统核心控制结构是进程结构,资源管理的数据结构将围绕进程结构展开。 1、操作系统的控制结构MemoryDevicesFilesProcessesMemory TablesI/O TablesFile TablesPrimary Process TableProcess 1Process NProcess 2Process ImageProcess 1ImageProcess NImage存储控制表管理一级（主）存储器和二级（虚拟）存储器，内容包括：主存储器的分配信息，二级存储器的分配信息，存储保护和分区共享信息，虚拟存储器管理信息操作系统核心控制结构是进程结构,资源管理的数据结构将围绕进程结

8、构展开。 1、操作系统的控制结构MemoryDevicesFilesProcessesMemory TablesI/O TablesFile TablesPrimary Process TableProcess 1Process NProcess 2Process ImageProcess 1ImageProcess NImageI/O控制表管理系统的I/O设备和通道，包括：I/O设备和通道是否可用，I/O设备和通道分配信息，I/O操作的状态和进展，I/O操作传输数据所在主存区。操作系统核心控制结构是进程结构,资源管理的数据结构将围绕进程结构展开。 1、操作系统的控制结构MemoryDevic

9、esFilesProcessesMemory TablesI/O TablesFile TablesPrimary Process TableProcess 1Process NProcess 2Process ImageProcess 1ImageProcess NImage文件控制表管理文件，包括：被打开文件的信息，文件在主存储器和二级存储器中的位置信息，被打开文件的状态和其他属性信息。进程程序进程数据栈用于系统调用、过程调用时的参数存储和传递进程控制块PCB (进程属性)处于核心段用户进程不能直接访问、修改自己的PCB2、进程映象 (进程要素)进程上下文：进程本身运行环境 对进程执行活动

10、全过程的静态描述 由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成用户级上下文：进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段和用户栈寄存器级上下文：程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值系统级上下文：静态部分（PCB和资源表格）动态部分：核心栈（核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈） 进程映象 (进程要素)进程空间任一进程,都有一个自己的地址空间,把该空间成为进程空间或虚空间.进程空间的大小只与处理机位数有关。程序的执行都在进程空间内进行。用户程序、进程的各种控制表格等都按一定的结构排列在进程空间中。UNIX,L

11、inux等系统中，进程空间被划分成用户空间和系统空间。计算机系统还通过程序状态寄存器等设置不同的执行模式，即用户模式和系统模式来进行保护。核心态和用户态用户态时不可直接访问受保护的OS代码；核心态时执行OS代码，可以访问全部进程空间。概念：系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的3.2.1进程控制块（Process Control Block）每个进程在OS中的登记表项（可能有总数目限制），OS据此对进程进行控制和管理（PCB中的内容会动态改变），不

12、同OS则不同处于核心段，通常不能由应用程序自身的代码来直接访问，而要通过系统调用，或通过UNIX中的进程文件系统(/proc)直接访问进程映象(image)。文件名为进程标识（如：00316），权限为创建者可读写。进程控制块 (PCB, process control block)进程控制块是由OS维护的用来记录进程相关信息的一块内存。进程控制块的内容进程描述信息：进程标识符(process ID)，唯一，通常是一个整数；进程名，通常基于可执行文件名（不唯一）；用户标识符(user ID)；进程组关系(process group)进程控制信息：当前状态；优先级(priority)；代码执行入口

13、地址；程序的外存地址；运行统计信息（执行时间、页面调度）；进程间同步和通信；阻塞原因资源占用信息：虚拟地址空间的现状、打开文件列表CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针） PCB的组织方式链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表各状态的进程形成不同的链表：就绪链表、阻塞链表索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表各状态的进行形成不同的索引表：就绪索引表、阻塞索引表 进程在运行过程中有3种基本状态。这些状态与系统调度占有处理机密切相关。所以又称它们为进程调度状态。运行状

14、态（Running） 当一个进程已分配到处理机，他的程序正由处理机执行时，称此进程处于执行状态。就绪状态（Ready） 如果进程已具备执行条件，但是因为处理机已由其他进程占用，暂时不能执行而等待分配处理机，称此为就绪状态。3.3进程的状态及其变化 等待状态（Blocked，阻塞状态） 进程因等待某一事件（如等待某一输入，输出操作完成）而暂时不能运行的状态称为等待状态，此时即使CPU空闲，它也无法使用。进程的状态及其变化进程的状态及其转换运行就绪等待在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换就绪 - 运行调度程序选择一个新的进程运行运行 -

15、就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态运行 - 等待当一进程必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I/O且必须等待结果等待某一进程提供输入 (IPC)等待 - 就绪当所等待的事件发生时增加: 创建状态，终止状态三种进程状态-五状态进程模型创建(新new)状态OS 已完成为创建一进程所必要的工作已构造了进程标识符已创建了管理进程所需的表格但还没有允许执行该进程 (尚未同意) 因为资源有限终止（退出exit)状态中止后进程移入该状态它不再有执行资格表格和其它信息暂时由辅助程序保留一旦其他进程完成了对终止态进程的信息抽取之后，系统将删除该进程。五状态

16、进程模型NULL新建态：创建一个子进程。新建态就绪态：系统完成了进程创建操作，且当前系统的性能和内存的容量均允许。运行态终止态：一个进程到达自然结束点，或出现了无法克服的错误，或被操作系统所终结，或被其他有终止权的进程所终结。终止态NULL：完成善后操作。就绪态终止态：某些操作系统允许父进程终结子进程。等待态终止态：某些操作系统允许父进程终结子进程。增加: “挂起”状态五状态进程模型-七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起七状态进程模型 为什么要有“挂起”状态? 由于进程的不断创建，系统资源已不能满足进程运行的要求，就必须把某些进程挂起（suspend），对换到

17、磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的。七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起就绪状态(Ready)：进程在内存且可立即进入运行状态阻塞状态(Blocked)：进程在内存并等待某事件的出现阻塞挂起状态（Blocked, suspend）：进程在外存并等待某事件的出现就绪挂起状态（Ready, suspend）：进程在外存，但只要进入内存，即可运行七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起挂起（Suspend）：把一个进程从内存转到外存可能有以下几种情况阻塞阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时

18、，发生这种转换，以提交新进程或运行就绪进程就绪就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程运行就绪挂起：对抢占式系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况：就绪挂起就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，发生转换阻塞挂起阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞状态

19、。3.4 进程控制3.4.1 进程控制的功能3.4.2 进程的创建和撤消3.4.3 UNIX进程的阻塞和唤醒返回3.4.1 进程控制的功能 系统使用一些具有特定功能的程序段来创建、撤销进程及完成进程状态的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。原语(primitive)：由若干条指令构成的“原子操作(atomic operation)”过程，作为一个整体而不可分割要么全都完成，要么全都不做。许多系统调用就是原语。注意：系统调用并不都是原语。进程A调用read()，因无数据而阻塞，在read()里未返回。然后进程B调用read()，此时read()被重入。系统调用不一定一次

20、执行完并返回该进程，有可能在特定的点暂停，而转入到其他进程。3.4.2 进程创建和撤消 批处理中，由操作系统的作业调度程序为用户作业创建相应的进程以完成用户所要求的功能。 由父进程创建，在层次结构的系统中，父进程创建子进程以完成并行工作。 PCB表的有关参数： 进程标识符N，初始CPU状态S。（它包括CPU的工作方式（管态或目态），本进程的开始地址，以及屏蔽码等），优先数K，初始内存M0、资源R0等。入 口查PCB表有空PCB？取空表PCB（i）将有关参数填入PCB（i）相应项PCB（i）入就绪队列PCB(i)入进程家族或进程链返 回创建失败创建原语流程图 创建原语的操作过程：先向PCB集合索

21、取一张空白PCB，并获得PCB的内部名字。 若该进程的程序不在内存中，应将它从后援存储器调入内存，然后把调用者提供的参数以及父进程的内部名称填入PCB，并设置，最后把它分别插入进程家族和就绪队列RL中。 当一个进程在完成其任务后应予以撤销，以后及时释放它所用的资源（外部设备和内存空间） 当被撤销进程不是运行状态势，就不需要调用调度程序。为标志这两种情况，在撤销原语中设置了一个标志位SCHESD。若标志位的值为真，则调用处理机调度程序。进程撤消有三种情况： 该进程已完成所要求的功能而正常终止。 由于某种错误导致非正常终止。 祖先进程要求撤销某个子进程被撤销进程的外部名。 入 口查进程链表或进程家

22、族有此PCB吗？释放该进程所占有的资源返 回出错处理撤消原语流程图该PCB有子进程吗？释放该PCB结构本身有无有无无撤销原语的操作过程是： 以调用者所提供的标识符n为索引，到PCB集合中去搜索，获得该进程的内部名称I和状态。若进程正处于执行状态，则应立即中断CPU，把CPU状态保存在CPU状态保护区，停止执行该进程，并设置要重新调度的标志。（调度程序SCHEDULER以将CPU分给其它进程。）Procedure Destroy (n);BeginSched := false;i:=Get Internal Name(n);Kill(i);if Sched=true then SCHEDULER

23、;调度程序从就绪队列中调入一个进程占CPUEnd(Destroy)Procedur Kill(i)Beginif status(i)=Running thenBeginStop(i);Sched:=true;EndREMOVE(Queue(i),i);从进程队列中移走一个进程for all SProgeny(i) doKill(S);for all RResources(i) doRELEASE(r); 释放资源RELEASE( PCB(i) ); 释放PCB表End(Kill)阻塞原语 阻塞原语在一个进程期待某一事件（例如键盘输入数据、写盘、其它进程发来的数据等）发生，但条件尚不具备时，被该

24、进程自己调用来阻塞自己。阻塞原语在阻塞一个进程时，由于该进程正处在执行状态，故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。 3.4.2 进程的阻塞与唤醒 入口保存当前进程的CPU现场置该进程的状态被阻塞进程入等待队列转进程调度阻 塞 原 语 阻塞进程原语描述如下： procedure block begin i:=EP; /* 当前执行程序的指针*/ stop(i); i.status:=”blockeda”; i.sdata=WQ(r); insert(WQ(r), i); schedler end 唤醒原

25、语该原语主要时实现进程从阻塞状态到就绪状态的转换。处于阻塞态的进程，当期待的事件出现时，有“发现者”将其唤醒。唤醒一个进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。入口从等待队列中摘下被唤醒进程将被唤醒进程置为就绪态将被唤醒进程送入就绪队列转进程调度或返回 唤 醒 原 语 唤醒原语描述如下： procedure wakeup(n) begin i:=getinternal name(n); remove(WQ(r),i); i.status:=”ready”; i.status:=RQ; insert(RQ,i); continue end3.5 进程互斥什么叫互斥？ 一组

26、并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。返回例如：进程p1，p2都需要使用打印机，如果让它们同时使用，则两个进程的输出交织在一起，打印出的结果无法使用。为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机分配给它，就一直由它独占使用，其它申请使用打印机的进程则必须等待。 一次仅允许一个进程使用的资源称为临界资源。3.5.1 资源共享所引起的制约3.5.2 互斥的加锁实现3.5.3 信号量和P,V原语3.5.4 用P,V原语实现互斥返回3.5.1 资源共享所引起的制约临界资

27、源临界区的访问过程同步机制应遵循的准则进程互斥的软件方法进程互斥的硬件方法临界资源进程间资源访问冲突共享变量的修改冲突操作顺序冲突进程间的制约关系间接制约：进行竞争独占分配到的部分或全部共享资源，“互斥”直接制约：进行协作等待来自其他进程的信息，“同步”硬件或软件（如外设、共享代码段、共享数据结构），多个进程在对其进行访问时（关键是进行写入或修改），必须互斥地进行有些共享资源可以同时访问，如只读数据多道程序环境进程之间存在资源共享，进程的运行时间受影响共享变量的修改冲突操作顺序冲突有3个进程：get, copy和put，它们对4个存储区域f、s、t和g进行操作。有6种可能的操作顺序，只有一种结

28、果是正确的。进程的交互关系：可以按照相互感知的程度来分类互斥，指多个进程不能同时使用同一个资源；死锁，指多个进程互不相让，都得不到足够的资源；饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）临界区的访问过程临界区临界区(critical section)：进程中访问临界资源的一段代码。进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志退出区(exit section)：用于将正在访问临界区标志清除。剩余区(remainder section)：代码中的其余部分。同步机制应遵循的准则空闲则入：其他进程

29、均不处于临界区；忙则等待：已有进程处于其临界区；有限等待：等待进入临界区的进程不能死等；让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）3.5.2互斥的加锁实现有两个进程Pi, Pj，其中的Pi算法1：单标志设立一个公用整型变量 turn：描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入；在退出区修改允许进入进程标识：进程Pi退出时，改turn为进程Pj的标识j；缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区；算法2：双标志、先检查设立一个

30、标志数组flag：描述进程是否在临界区，初值均为FALSE。先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。按下面序列执行时，会同时进入：Pi Pj Pi Pj。即在检查对方flag之后和切换自己flag之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能连续进行。算法3：双标志、后检查类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。缺点：Pi和Pj可能都进入不了临界区。按下面序列执行时，会都进不了临界区：Pi P

31、j Pi Pj。即在切换自己flag之后和检查对方flag之前有一段时间，结果都切换flag，都检查不通过。算法4(Petersons Algorithm)：先修改、后检查、后修改者等待结合算法1和算法3，是正确的算法turn=j;描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后：检查对方flag，如果不在临界区则自己进入空闲则入否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待进程互斥的硬件方法完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用。可以利用某些硬件指令其读写操作由一条指令完成，因而保证读操作与

32、写操作不被打断；Test-and-Set指令该指令读出标志后设置为TRUEboolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲互斥算法（TS指令）利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；Swap指令（或Exchange指令）交换两个字（字节）的内容void SWAP(int *a, int *b) int

33、 temp; temp = *a; *a = *b; *b = temp;互斥算法（Swap指令）利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现让权等待可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上可能死锁3.5.3 信号量和P、V原语1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(pr

34、oberen)和increment(verhogen)），是一种卓有成效的进程同步机制。每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数二进制信号量(binary semaphore)：只允许信号量取0或1值1. P原语wait(s)-s.count;/表示申请一个资源;if (s.count 0)/表示没

35、有空闲资源; 调用进程进入等待队列s.queue; 阻塞调用进程;2. V原语signal(s)+s.count;/表示释放一个资源；if (s.count = 0)/表示有进程处于阻塞状态； 从等待队列s.queue中取出一个进程P; 进程P进入就绪队列;V原语通常唤醒进程等待队列中的头一个进程3. 利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P

36、、V原语不能次序错误、重复或遗漏4. 利用信号量来描述前趋关系前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个互斥信号量S12，其初值为03.6 进程同步 3.6.1同步的概念 3.6.2私用信号量和 公用信号量 3.6.3用P,V操作实现同步 3.6.4生产者和消费者问题 3.6.5管程 在一个计算机系统中的各个进程存在着相互依赖、相互制约的关系。一方面，某些进程相互协作，以便正确地运行用户作业；另一方面，它们又互相竞争使用系统的有限资源。进程之间的这种相互依赖又相互制约，相互合作又相互竞争的关系意味着进程之间需要某种形式的通讯，这

37、主要表现在同步和互斥两个方面。 1.同步 同步指两个事件的发生有着某种时序上的关系。 一般来说，一个进程相对于另一个进程的运行速度是不确定的。它与每一个进程被中断的频率、占用处理机的频繁程度以及每次占用的时间长度有关。 所以进程相互之间是异步运行的但是协同工作的几个进程需要在某些确定的点上协调它们的工作。一个进程达到了这些点后，除非另一进程已经完成了某些操作，否则就不得不停下来以等待这些操作执行结束，这就是进程间的同步。 在现实生活中，同步的例子是俯拾皆是的，例如，在一辆公共汽车上，司机的职责是驾驶车辆；售票员的工作是售票、开关车门，各有各的职责范围。但两者的工作又需要相互配合、协调。当汽车到

38、站时，驾驶员将车辆停稳后，售票员才能将车门打开让乘客上下车，然后关车门，只有在得到车门已经关好的信号后，驾驶员才能开动汽车继续前进。所以，在驾驶员停止、启动汽车和售票员开关门之间有两个同步的过程。 到站停车 开 车 开 车 门 关 车 门 售 票 正常行车。售票员司机 比如：有一道算题： x=func1(y)*func2(z); 其中func1(y)和func2(z)都是比较复杂的函数，如果计算机系统中有两台处理机，则为了加快计算速度，可以用两个进程P1、P2各计算一个函数，而这两个进程又各自在一台处理机上运行，它们的工作情况大致如图：进程进程P2算完Func2(z)?取用P2计算结果进程P1

39、计算Func2(z)设置计算完成标志终止进程P2计算未完完成1）公用信号量 互斥时使用的信号量2）私用信号量 只与制约进程及被制约进程有关而不是与整组并发进程有关的信号量 1：生产者消费者的同步问题举例： 生产者把产品生产出来，送入仓库。给消费者发信号，消费者得到信号后，到仓库取产品，取走产品后给生产者发信号产品仓 库一个生产者一个消费者Begin procedure c s1,s2:sem; begin s1:=1; s2:=0; L2: 想取产品Cobegin P(s2); procedure p 取产品； begin V(s1); L1:生产产品； goto L2; p(s1); end

40、 放产品； Coend V(s2); End goto L1; endBUF1BUFnBUF2 .Pb Pa2）发送进程和接收进程的同步问题 利用信号量可以解决合作进程之间的同步。 例：设进程Pa,Pb通过缓冲区队列传送数据 发送和接送过程满足的条件是： 1)在Pa至少送一块数据入一个缓冲区之前,Pb不可能从缓冲区中取出数据(假定数据块长等于缓冲区长度); 2)Pa往缓冲队列发送数据时,至少有一个缓冲区是空的; 3)由Pa发送的数据块在缓冲队列中按先进先出(FIFO)方式排列. 描述发送过程deposit (data)和接受过程remove (data) . 1)Bufempty进程Pa的私用

41、信号量, Buffull 进程Pb的私用信号量; 2)Bufempty的初始值为n(n 为缓冲队列的缓冲区个数),Buffull的初始值为0; 发送过程Deposit(data),接送过程Remove(data),这两个过程必须同步，因为,因为过程deposit(data)的执行结果是过程remove(data)的执行条件,而当缓冲队列全部装满数据时,remove(data)的执行结果又是deposit(data)的执行条件。 Pa:deposit(data) Pb:remove(data) begin local x begin local x P(Bufempty) P(Buffull)

42、按FIFO方式选择一个 按FIFO方式选择一个 空缓冲Buf(x); 装满数据的缓冲Buf(x) Buf(x)-data data-Buf(x) Buf(x)置满标记 Buf(x)置满标记 V(Buffull) V(Bufempty) end end 信号量用于表示资源数目或请求使用某一资源的进程个数的整形量，其取值仅能由和操作改变，操作系统利用它的状态对进程和资源进行管理。根据用途的不同可把信号量分为：互斥信号量（二元信号量）：它仅允许取值为“”与“”，用作互斥。它联系着一组共行进程，初值为，每个进程均可对之施加、操作。一般信号量（资源信号量）：它联系着一组共行进程，但其初值为，或为某个正整

43、数，表示资源的数目，主要用于进程同步。123.nP1P2P3 .Pn.C1C2C3.Cn 计算机专家Dijkstra把同步问题抽象成一种生产者和消费者关系，计算机系统中的许多问题都可以被归结为生产者和消费者关系，例如，生产者可以是计算进程，消费者是打印进程，输入时输入进程是生产者，计算进程是消费者我们可以通过一个缓冲区把生产者和消费者联系起来 设生产者进程和消费者进程是互相等效的，其中各生产者进程使用的过程deposit (data)和消费者进程使用的过程remove(data)可描述如下： 首先，我们可以看到，上述生产者-消费者问题是一个同步问题。即生产者和消费者之间满足如下条件： 1)消费

44、者想接收数据时，有界缓冲区中至少有一个单元是满的； 2)生产者想接收数据时，有界缓冲区中至少有一个单元是空的。 另外，由于有界缓冲区是临界资源，因此，各生产者进程和消费者进程之间必须互斥执行。 有以上分析我们设公用信号量mutex保证生产者进程和消费者进程之间的互斥,设信号量 avail表示有界缓冲区中的空单元数,初值为n;信号量full表示有界缓冲区中的非空单元数,初值为0.信号量mutex表示有界缓冲区中的个数,初值为1.从而有: deposit (data); remove(data); begin begin p(avail) p(full) p(mutex) p(mutex)送数据入

45、缓冲区某单元 取缓冲区中某单元数据 V(full) V(avail) V(mutex) V(mutex) end end采用信号量机制：full是满数目，初值为0，empty是空数目，初值为N。实际上，full和empty是同一个含义：full + empty = Nmutex用于访问缓冲区时的互斥，初值是1 每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？)2. 读者写者问题(the readers-writers problem)问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读写”互斥，“写写”互斥，读读允许采

46、用信号量机制：Wmutex表示允许写，初值是1。公共变量Rcount表示“正在读”的进程数，初值是0；Rmutex表示对Rcount的互斥操作，初值是1。3. 哲学家进餐问题(the dining philosophers problem)问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；3.6.5 管程什么是管程?(1)把分散在各进程中的

47、临界区集中起来进行管理 ；防止进程有意或无意的违法同步操作， 便于用高级语言来书写程序，也便于程序正确性验证。 什么是管程?(2)管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块 管程有以下属性共享性：安全性：互斥性：管程的基本形式TYPE = MONITOR ; define ; use ； procedure (); begin ； end; procedure (); begin ； end; begin ； end;管程的结构condition c1wait(c1)condition cn wait(cn)Urgent queue signal局部数

48、据条件变量过程1过程k出口初始化代码入口管程等待调用的进程队列管程等待区域管程的示例TYPE SSU = MONITOR var busy : boolean; nobusy : semaphore; define require, return; use wait, signal； procedure require; begin if busy then wait(nobusy); /*调用进程加入等待队列*/ busy := ture； end; procedure return; begin busy := false； signal(nobusy); /*从等待队列中释放进程*/ e

49、nd; begin /*管程变量初始化*/ busy := false； end;管程的条件变量(1)条件变量：当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量同步原语wait：当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，这个动作引起调用进程阻塞管程的条件变量(2)另一个进程可以通过对其伙伴在等待的同一个条件变量condition上执行同步原语signal操作来唤醒等待进程。条件变量与P、V操作中信号量的区别? 管程的问题讨论 使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：执行signal的进程等待，直到被释放进程退出管

50、程或等待另一个条件被释放进程等待，直到执行signal的进程退出管程或等待另一个条件霍尔采用了第一种办法；汉森选择了两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作 管程与进程作比较(1)管程定义的是公用数据结构，而进程定义的是私有数据结构；管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的；管程与进程作比较(2)管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；管程是语言或操作系统的成分，不必创建或撤销，而进程有生

51、命周期，由创建而产生至撤销便消亡。3.7 进程间通信(IPC, INTER-PROCESS COMMUNICATION)3.7.1 进程间通信的类型3.7.2 信号(signal)3.7.3 共享存储区(shared memory)3.7.4 管道(pipe)3.7.5 消息(message)3.7.6 邮箱通信3.7.7 套接字(socket)返回3.7.1 进程间通信的类型低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。优点的速度快。缺点是：传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。编程复杂：用户直接实现通信的

52、细节，编程复杂，容易出错。高级通信：能够传送任意数量的数据，包括三类：共享存储区、管道、消息。返回1. 低级通信和高级通信 进程的同步与互斥是一种通讯方式，一进程可通过修改变量或信号量告知另一进程，它是否可以继续执行下去或不可继续，利用生产者消费者算法，生产者进程可以传送一批数据给消费进程，或者说生产者通过缓冲区与消费者进行通讯，但P、V操作只能传递信号，信号本身不包含任何数据，而进程不当还容易导致进程死锁，因此，称这些同步机构为低级通讯机构.直接通信和间接通信直接通信：信息直接传递给接收方，如管道。在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址；在接收时，允许接收来自任意

53、发送方的消息，并在读出消息的同时获取发送方的地址。间接通信：借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。通常收方和发方的数目可以是任意的。高级通信的特征通信链路(communication link)：点对点/多点/广播单向/双向有容量（链路带缓冲区）/无容量（发送方和接收方需自备缓冲区）数据格式：字节流(byte stream)：各次发送之间的分界，在接收时不被保留，没有格式；报文(datagram/message)：各次发送之间的分界，在接收时被保留，通常有格式（如表示类型），定长/不定长报文，可靠报文/不可靠报文。收发操作的同步方式发送阻塞（直到被链路容量或接收方所接受

54、）和不阻塞（失败时立即返回）接收阻塞（直到有数据可读）和不阻塞（无数据时立即返回）由事件驱动收发：在允许发送或有数据可读时，才做发送和接收操作3.7.2 信号(signal)返回信号相当于给进程的“软件”中断；进程可发送信号，指定信号处理例程；它是单向和异步的。对信号的处理进程可以设置信号处理例程, 在接收到信号时就被调用，称为捕获该信号。信号处理例程的参数是接收到信号的编号。进程也可以忽略指定的信号。进程创建后为信号设立了默认处理例程3.7.3 共享存储区(shared memory)返回相当于内存，可以任意读写和使用任意数据结构（当然，对指针要注意），需要进程互斥和同步的辅助来确保数据一致

55、性3.7.4 管道(pipe)返回管道是一条在进程间以字节流方式传送的通信通道。它由OS核心的缓冲区（通常几十KB）来实现，是单向的；常用于命令行所指定的输入输出重定向和管道命令。在使用管道前要建立相应的管道，然后才可使用。管道（pipe）通讯由unix首创，作为unix 的一大特色立即引起了人们的兴趣。由于其有效性，一些系统继unix之后相继引入了管道技术，如pc-dos，管道通信将成为进程通讯的一种重要方式。 消息缓冲通信机构是以内存缓冲去为基础。 管道是以文件系统为基础。 管道（pipe）连接两个进程之间的一个打开的共享文件，专用于进程之间进行数据通信。管道通信的思想（1）发送进程可以源

56、源不断的从pipe一端写入数据流，在规定的pipe文件的最大长度（如4096字节）范围内，每次写入的信息长度是可变的（2）接收进程在需要时可以从pipe的另一端读出数据，读出单位长度也是可变的1 Pipe的建立和使用方式 pipe 文件在使用之前，必须先由使用者建立并打开，建立pipe的主要工作是在系统打开文件表中建立该pipe的两个表目，一个表目用于控制该pipe的写操作，另一表目用于控制该pipe的读操作，即它们分别定义了该pipe的写入端和读出端，此时，pipe本身还是个空白文件。 系统文件 write(Fd1,buf,size) 功能：把buf中的长度为size字符的消息送入管道入口f

57、d1 fd1pipe入口 buf:存放消息的空间 size :要写入的字符长度 系统文件 read(fd0,buf,size)fd0Pipe的出口功能：从pipe出口fd0读出size字符的消息置入 buf中。 pipe只允许建立者及其子进程使用。一进程及其所有子孙构成一个进程族，同族中的多个进程可共享一个pipe，为了避免混乱，通常一个pipe为两个进程专用，且一个进程只用其写入端，另一进程只用其读出端。1 Pipe文件的读写操作的同步与互斥 如同消息缓冲一样，在对pipe文件进行读写操作过程中要对发送进程和接送进程实施正确的同步与互斥以确保通信的正确性. 接收进程：当接收进程读pipe时，

58、若发现pipe为空，则进入等待状态。一旦有发送进程对该pipe执行写操作是唤醒等待进程.发送进程：当发送进程在写pipe时，总是先按pipe文件的当前长度设置，如果pipe文件长度已经到4096字节，但仍有一部分信息没有写入，则系统使要求写pipe的进程进入睡眠状态，当读pipe进程收走了全部信息时，此时，系统再唤醒待写的进程。它将余下部分信息继续送入pipe中。3.7.5 消息(message)返回与窗口系统中的“消息”不同。通常是不定长数据块。消息的发送不需要接收方准备好，随时可发送。消息的一般形式 消息缓冲通讯技术由Hansen 首先提出的，基本思想是：根据“生产者消费者关系”原理，利用

59、公用消息缓冲区实现进程间的信息交换。 发送进程先申请一个消息缓冲区，写入消息后把该消息缓冲区送入接收进程的消息队列中，通知接收进程。接收进程从消息队列中摘下一消息缓冲区，取出所需要的信息。 消息的一般形式: 发送消息的进程名 接收消息的进程名 消息长度 消息正文消息缓冲机制 消息缓冲通讯机构包含下列内容： 1.消息缓冲区是一个数据结构 用Pascal 描述为： type msg=recorod sender： 消息发送者名 size： 消息长度 Text： 消息正文 Next： 下一个消息的链指针 2.发送原语和接收原语发送原语：send ( B, m)发送一个消息给进程 B；发送进程存放的消

60、息内存区的首址在m 中。接收原语：Receive ( A, n) 接收来自A进程的消息。例子：Send ( B, m )Begin向系统申请一个消息缓冲区P (mutex )将发送区消息m 送入新申请的消息缓冲区把消息缓冲区挂入接收进程的消息队列V ( mutex )V ( SM )End注：SM 为私用信号量，初值为0Receive ( n )BeginP( SM )P ( mutex ）摘下消息队列中的消息n将消息n从缓冲区复制到接收区释放缓冲区V ( metex )End1 信（邮）箱 信箱是一种数据结构，逻辑上它分成两部分：信箱头和由若干格子组成的信箱体。 信箱中每个格子存放一封信，信