ch3西安电子科技大学操作系统课件.ppt

1、西安电子科技大学计算机学院西安电子科技大学计算机学院1第三章 进程管理西安电子科技大学计算机学院西安电子科技大学计算机学院标题添加点击此处输入相关文本内容点击此处输入相关文本内容前言点击此处输入相关文本内容标题添加点击此处输入相关文本内容西安电子科技大学计算机学院西安电子科技大学计算机学院3第三章 进程管理n进程的定义与控制n进程调度n进程间的相互作用n进程通信n线程nUNIX和Windows的进程和线程模型西安电子科技大学计算机学院西安电子科技大学计算机学院43.1 进程的引入n在早期计算机系统中，多道程序设计还未出现之前，程序是顺序执行的。多道程序设计出现后，操作系统可以实现多个进程的并发

2、执行。n进程（process）一词在20世纪60年代初首先出现的MIT的MULTICS系统中。n进程是程序的一次执行，多个进程可以并发执行。西安电子科技大学计算机学院西安电子科技大学计算机学院53.1 进程的引入n程序的顺序执行和并发执行程序的执行有两种方式：顺序执行和并发执行。顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。n程序顺序执行：一个较大的程序通常由若干个程序段组成，程序在执行时，各程序段必须按照先后次序逐个执行。程序各程序段的这种先后次序可用前趋图表示。西安电子科技大学计算机学院西安

3、电子科技大学计算机学院63.1 进程的引入n前趋图是一个有向无循环图，图由结点和结点间的有向边组成，结点代表各程序段操作，而结点间的有向边代表程序段操作之间存在的前趋关系。两程序段Pi和Pj的前趋关系表示成PjPi Pi是Pj的前趋，Pj是Pi的后继I1C1P1I2C2西安电子科技大学计算机学院西安电子科技大学计算机学院73.1 进程的引入n顺序执行的特征顺序性：CPU严格按照程序结构所指定的次序执行。封闭性：独占全部资源，资源的状态只能由该程序本身改变，不受其它程序和外界因素影响。可再现性：如果程序执行环境和初始条件相同，则其执行的结果相同。西安电子科技大学计算机学院西安电子科技大学计算机学

4、院83.1 进程的引入n多道程序设计：把一个以上的程序放入内存中，并且同时处于运行状态，这些程序共享CPU和其它资源。特点如下：多道：内存中有多道程序，它们在任一时刻必须处于就绪、运行、阻塞三种状态。宏观上并行：从宏观上看，它们在同时执行。微观上串行：从微观上看，它们在交替、穿插执行。西安电子科技大学计算机学院西安电子科技大学计算机学院93.1 进程的引入n多道程序设计优点：CPU利用率高。设备利用率高。系统吞吐量大。P1P2tI/OCPU两个进程执行示意图西安电子科技大学计算机学院西安电子科技大学计算机学院103.1 进程的引入n并发执行的特征：失去封闭性：共享资源，程序之间互相制约。间断性

5、：程序之间的制约关系致使程序执行时间不连贯。不可再现性：失去封闭性，也就失去了可再现性，程序执行的结果随速度、环境的不同而不同。可见，并发和并行是不同的概念：并行是并发的特例，并发是并行的拓展。西安电子科技大学计算机学院西安电子科技大学计算机学院11观察者beginrepeat wait for a car through N=N+1untilend报告者beginrepeat delay print N N=0untilend初始N=n时不同执行序列，结果各不相同执行序列 123程序N=N+1print NN=0print NN=0N=N+1print NN=N+1N=0结果打印n+1,N=

6、0打印n,N=1打印n,N=0例子：观察者与报告者西安电子科技大学计算机学院西安电子科技大学计算机学院123.1 进程的引入 综上所述，由于程序的并发执行破坏了程序的封闭性和可再现性，使得程序和程序的执行不再一一对应，因此，程序这个静态的概念已经不能切实反映程序执行的各种特征。于是，引入“进程”，能够反映程序执行的独立性、并发性和动态性等特征。西安电子科技大学计算机学院西安电子科技大学计算机学院133.2 进程定义与控制n进程定义进程是程序的一次执行进程是可以和别的计算并发执行的计算进程是定义在一个数据结构上并能在其上进行操作的一个程序进程是程序在一个数据集合上运行的过程，它是系统进行资源分配

7、和调度的一个独立单位西安电子科技大学计算机学院西安电子科技大学计算机学院143.2 进程定义与控制n进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的一次执行。进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。西安电子科技大学计算机学院西安电子科技大学计算机学院153.2 进程定义与控制 进程：是程序的一次执行，该程序可与其它程序并发执行；它是一个动态实体，在传统的操作系统

8、设计中，进程既是基本的分配单位，也是基本的执行单位。西安电子科技大学计算机学院西安电子科技大学计算机学院163.2 进程定义与控制n进程组成：有程序段、数据段和进程控制块(PCB)组成。程序和数据是进程存在的物理基础，是进程的实体进程控制块是进程的灵魂，是进程存在的唯一标志操作系统为进程创建进程控制块和分配地址空间的过程就是进程创建的过程西安电子科技大学计算机学院西安电子科技大学计算机学院173.2 进程定义与控制n进程控制块：是操作系统用来记录进程详细状态和相关信息的基本数据结构，包括进程的标识信息、状态信息和控制信息。标识信息：唯一的标识一个进程，主要有进程标识、用户标识和父进程标识。状态

9、信息：与CPU有关的各种现场信息，包括寄存器状态、堆栈指针。以便该进程重新占用CPU后能够继续执行。西安电子科技大学计算机学院西安电子科技大学计算机学院183.2 进程定义与控制控制信息：操作系统对进程进行调度管理时用到的信息。主要有进程状态、调度信息、队列指针、资源占有使用信息等。n进程控制块的组织方式PCB在内存中是以表的形式存在的PCB表。还可以将相同性质的进程组织在一张表中，形成多个索引表。有些操作系统将PCB分为常驻内存和非常驻内存两部分，如UNIX。西安电子科技大学计算机学院西安电子科技大学计算机学院193.2 进程定义与控制n进程基本状态运行态（Running）：进程已经获得所需

10、资源，并占有CPU就绪态（Ready）：已经获得所需资源，只等待CPU阻塞态（Blocked）：也称为等待态、挂起态或睡眠态等，进程等待某个事件，如等待I/O完成，等待某个资源此外，还可以有新建态、终止态。西安电子科技大学计算机学院西安电子科技大学计算机学院203.2 进程定义与控制n进程状态的转换新建终止就绪阻塞运行创建完毕时间片用完结束执行选中等待事件等待结束西安电子科技大学计算机学院西安电子科技大学计算机学院21七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起西安电子科技大学计算机学院西安电子科技大学计算机学院22西安电子科技大学计算机学院西安电子科技大学计算机学院

11、23PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn.空 PCBPCB运行态就绪态等待1 1等待2 26751015进程控制块（Process Control Block）西安电子科技大学计算机学院西安电子科技大学计算机学院243.2 进程定义与控制n进程控制通过原语（Primitive）操作实现原语是指由机器指令构成的可完成特定功能的程序段。它是一个机器指令的集合，在执行时不能被中断。多采用屏蔽中断方法实现。进程控制原语有：v进程创建原语（create primitive）v进程撤消原语（destroy primitive）v进程阻塞原语（block primitive）v进

12、程唤醒原语（wakeup primitive）v进程挂起原语（suspend primitive）v进程激活原语（active primitive）西安电子科技大学计算机学院西安电子科技大学计算机学院253.2 进程定义与控制n进程关系的树型结构AA22A21A11A2A1西安电子科技大学计算机学院西安电子科技大学计算机学院263.2 进程定义与控制n进程关系的树型结构主要优点v资源分配严格：子进程仅能分配到父进程所拥有的资源，用完后归还。v进程控制灵活：可根据需要给进程以不同的控制权限。v进程结构清楚，关系明确。西安电子科技大学计算机学院西安电子科技大学计算机学院273.2 进程定义与控制n

13、进程特征动态性：“执行”、“计算”、“运行过程”都强调动态性，进程的最基本特征。并发性：进程的重要特征，同时也是操作系统的重要特征。异步性：进程按各自独立的不可预知的速度向前推进，即进程按异步方式进行，这导致了进程执行的不可再现性，因此，操作系统必须采用某些措施来限制各进程推进序列以保证各程序间正常协调运行。西安电子科技大学计算机学院西安电子科技大学计算机学院283.2 进程定义与控制n进程特征独立性：进程是一个独立运行的基本单位，即是一个独立获得资源和独立调度的单位。制约性：一个进程的执行可能依赖其他进程的执行结果。结构性：每个进程有固定结构，包括程序、数据和PCB三部分。西安电子科技大学计

14、算机学院西安电子科技大学计算机学院293.3 进程调度n进程调度属于低级调度，就是从就绪队列中，按照一定的算法选择某个进程占用CPU。n进程调度时机现运行进程或者因任务完成而正常结束，或者因错误而异常结束现运行进程因某种原因，比如I/O请求，从运行态进入阻塞状态现运行进程执行某种原语操作，如P操作、阻塞原语等，进入阻塞状态一个具有更高优先数的进程要求CPU，即已进入就绪队列分配给该进程运行的时间片已用完西安电子科技大学计算机学院西安电子科技大学计算机学院303.3 进程调度n确定调度算法的原则：面向系统性能：公平性、较大的吞吐量面向用户性能：及时性、较短的周转时间西安电子科技大学计算机学院西安

15、电子科技大学计算机学院313.3 进程调度n进程调度算法先来先服务进程调度算法（FCFS）基于优先数的进程调度算法：根据优先数大小确定优先级高低，分为v静态优先数法：进程创建时就规定好优先数v动态优先数法：优先数在执行过程中根据情况改变，例如UNIX时间片轮转进程调度算法v固定时间片v可变时间片多级队列轮转调度算法西安电子科技大学计算机学院西安电子科技大学计算机学院32多级队列轮转调度算法最高优先级队列次高优先级队列低优先级队列CPU进程进入运行结束撤消降低优先级就绪进程西安电子科技大学计算机学院西安电子科技大学计算机学院333.3 进程调度n进程调度方式当一个进程正在CPU上运行时，若有一个

16、更为紧迫或更为重要的进程需要进行处理，或者说，如果有更高优先数的进程进入就绪队列时，如何分配CPU。通常有两种方式：不可剥夺方式（不可抢占方式，non-preemptive）可剥夺方式（可抢占方式，preemptive）西安电子科技大学计算机学院西安电子科技大学计算机学院343.4 进程间的相互作用n同步：一个进程的某个操作与协作进程的某个操作之间在时序上有一定的关系。如果协作进程的某个操作没有完成，那么该进程就要等待这个操作完成才能继续下去，这种需要相互合作、协同工作的进程之间的相互关系称为进程的同步。n临界资源（独占资源）：指在一段时间内只允许一个进程访问的资源。n互斥：当两个或两个以上进

17、程竞争同一临界资源时，进程间的制约关系称为进程的互斥。西安电子科技大学计算机学院西安电子科技大学计算机学院353.4 进程间的相互作用n进程间的同步司机和售票员的同步正常行驶开车到站停车关车门开车门售票员售票司机西安电子科技大学计算机学院西安电子科技大学计算机学院363.4 进程间的相互作用又如，有用户作业程序，其形式为：Z=fun1(x)*fun2(y)其中，fun1(x)和fun2(y)均是一个复杂函数，为了加快本题的计算速度，可用两个进程P1、P2各计算一个函数。进程P2计算fun2(y)，进程P1计算完fun1(x)之后，与进程P2的计算结果相乘，以获得最终结果Z。西安电子科技大学计算

18、机学院西安电子科技大学计算机学院373.4 进程间的相互作用结束置计算完标志P2计算fun2(y)N计算fun1(x)取用P2计算结果P1P2算完fun2(y)Y西安电子科技大学计算机学院西安电子科技大学计算机学院383.4 进程间的相互作用n进程的互斥互斥使用资源进程A（阻塞）请求资源R进程B释放资源R请求资源R（使用R）释放资源RR分配拒绝唤醒西安电子科技大学计算机学院西安电子科技大学计算机学院39 进程间的制约n进程间的联系n进程间同步：相互协作的进程要共同完成一个任务，它们之间要相互配合，需要在一些动作间进行同步，即一个进程的某个动作与协作进程的某些动作之间在时序上有一定的关系。n进程

19、间互斥：当两个或两个以上的进程竞争同时只能被一个进程使用的资源时，例如竞争使用打印机，需要互斥使用该资源。进程的同步、互斥机制信号量及P.VP.V操作 西安电子科技大学计算机学院西安电子科技大学计算机学院40 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥.临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量 临界资源可以是一些硬件设备（如打印机、磁带机或绘图仪等），也可以是进程共享变量、数据、队列、或使用权限等“有形”或“无形”的资源。进程的互斥（间接制约）mu

20、tual exclusionmutual exclusion西安电子科技大学计算机学院西安电子科技大学计算机学院41n临界区（互斥区）：critical sectionn一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作.n在进程中涉及到临界资源的程序段叫临界区.n多个进程的临界区称为相关临界区.临界区（互斥区）：critical sectioncritical section西安电子科技大学计算机学院西安电子科技大学计算机学院42临界区（critical sectioncritical section）进程的互斥（间接作用）西安电子科技大学计算机学院

21、西安电子科技大学计算机学院43与时间有关的错误n 由于现在操作系统中的进程是并发执行的，各进程以自己的速度向前推进，所以，运行的顺序可能是：n n P1：R1=count；n P2：R2=count；n P1：R1=R1+1；n P1：count=R1；n P2：R2=R2+1；n P2：count=R2；错误：P1,P2 P1,P2 执行的结果countcount只加了1 1西安电子科技大学计算机学院西安电子科技大学计算机学院44程 序 段1程 序 段2程 序 段n共 享 变 量临界区西安电子科技大学计算机学院西安电子科技大学计算机学院45使用互斥区的原则n(1)当有若干个进程要求进入临界区

22、时，应使一个进程进入临界区，它们不应相互等待而使谁都不能进入，即进程不能无限地停留在等待临界资源的状态。n(2)一次只允许一个进程进入临界区中，即各进程互斥访问临界资源。n(3)各进程使用临界资源的时间是有限的，即任何一个进程都必须在有限的时间内释放所占资源。西安电子科技大学计算机学院西安电子科技大学计算机学院46解决进程互斥的方法 n 解决进程互斥的方法有硬件方法和软件方法。软件方法中著名的有Dekker算法和Peterson算法。nDekker算法 设置一个整型变量turn，指示允许进入临界区的进程标识。假设现有两个进程P1和P2，当turn的值为1时，P1被允许进入；当turn的值为2时

23、，P2被允许进入。进程退出临界区时，要把turn的值改为对方的标识符，就等于允许对方的进入。nPeterson算法 它除设置整型变量turn外，还为每一个进程设置一个标志，指示该进程是否要求进入临界区。假设还是两个进程，都在等待进入临界区。先检查对方的标志，如果不在临界区，则检查turn的值，以确定是否可以进入。西安电子科技大学计算机学院西安电子科技大学计算机学院473.4 进程间的相互作用n信号量（semaphore）与P、V操作Edsgar Wybe Dijkstra（埃德斯加狄克斯特拉）v1972年ACM图灵奖（ACM Turing Award）获得者v“一个程序的易读性和易理解性同其中

24、所包含的无条件转移控制的个数成反比关系。”v提出结构化程序设计思想西安电子科技大学计算机学院西安电子科技大学计算机学院483.4 进程间的相互作用西安电子科技大学计算机学院西安电子科技大学计算机学院49信号量及P.VP.V操作n信号量（Semaphore）是表示资源的实体，是一个与队列有关的整型变量，其值仅能由P、V操作改变。n信号量分为：公用信号量和私用信号量。n公用信号量:用于实现进程间的互斥，初值通常设为1，它所联系的一组并行进程均可对它实施P、V操作；n私用信号量用于实现进程间的同步，初始值通常设为0或n，允许拥有它的进程对其实施P操作。西安电子科技大学计算机学院西安电子科技大学计算机

25、学院50信号量：semaphoresemaphoren信号量数据结构定义如下：struct semaphore int value;pointer_PCB queue;n信号量说明：semaphore s;西安电子科技大学计算机学院西安电子科技大学计算机学院51P P、V V操作 P(s)s.value=s.value-1;if(s.value 0)该进程状态置为等待状态;将该进程的PCB插入相应的等待队列末尾s.queue;西安电子科技大学计算机学院西安电子科技大学计算机学院52P P、V V操作V(s)s.value=s.value+1;if(s.value=0时，其值表示还有可用的资源数

26、；ns.value 0 时，其绝对值表示有多少个进程因申请该信号量表示的资源，得不到而进入阻塞态；西安电子科技大学计算机学院西安电子科技大学计算机学院54用P P、V V操作解决进程间互斥问题P(S)V(S)P1P2P3互斥区P(S)P(S)V(S)V(S)设信号量:s=1;:s=1;申请进入临界区退出临界区西安电子科技大学计算机学院西安电子科技大学计算机学院55进程互斥执行序列：P2P2西安电子科技大学计算机学院西安电子科技大学计算机学院56执行序列：P2P2（就绪）-P1-P1（阻塞）-进程互斥西安电子科技大学计算机学院西安电子科技大学计算机学院57进程互斥执行序列：P2P2（就绪）-P1

27、-P1（阻塞）-P3（阻塞）西安电子科技大学计算机学院西安电子科技大学计算机学院58进程互斥执行序列：P2P2（就绪）-P1-P1（阻塞）-P3（阻塞）-P2西安电子科技大学计算机学院西安电子科技大学计算机学院59执行序列：P2P2（就绪）-P1-P1（阻塞）-P3（阻塞）-P2-P1进程互斥西安电子科技大学计算机学院西安电子科技大学计算机学院60进程互斥执行序列：P2P2（就绪）-P1-P1（阻塞）-P3（阻塞）-P2-P1-P3信号量变化范围：,即（-n-n）西安电子科技大学计算机学院西安电子科技大学计算机学院61进程互斥举例（1 1）例2，上述的“飞机订票系统”。一个飞机订票系统可以有多

28、个订票处的n个订票终端。现假设n=2，公共数据区为Hi（i=1,2，,m），分别存放各次班机的现存票数，Pi(i=1,2,n)表示售票终端的进程。西安电子科技大学计算机学院西安电子科技大学计算机学院62进程互斥举例（2 2）semaphore S;nS=1;/公用信号量ncobegin nn process Pi(i=1,2,n)n n int temp;n 按照定票要求找到单元Hi；n P（S）；n temp=Hi;if temp 1 temp=temp-1;Hi=temp;V(S);输出一张票 else V(S);输出提示“票已售完”;coned西安电子科技大学计算机学院西安电子科技大学计

29、算机学院633.4 进程间的相互作用进程间的同步西安电子科技大学计算机学院西安电子科技大学计算机学院643.4 进程间的相互作用结束置计算完标志P2计算fun2(y)N计算fun1(x)取用P2计算结果P1P2算完fun2(y)Y西安电子科技大学计算机学院西安电子科技大学计算机学院653.4 进程间的相互作用n用P，V操作实现司机售票员同步：设置信号量S车，S门，初值均为0司机进程while(true)正常行驶；到站停车；V(S门);P(S车);离站开车；售票员进程while(true)售票；P(S门);开车门；关车门；V(S车);西安电子科技大学计算机学院西安电子科技大学计算机学院663.4

30、 进程间的相互作用n用P，V操作实现司机售票员同步：设置信号量S车，S门，初值均为0n司机到站西安电子科技大学计算机学院西安电子科技大学计算机学院673.4 进程间的相互作用n用P，V操作实现司机售票员同步：n司机到站-想继续开车阻塞西安电子科技大学计算机学院西安电子科技大学计算机学院683.4 进程间的相互作用n用P，V操作实现司机售票员同步：n司机到站-想继续开车阻塞-售票员开车门西安电子科技大学计算机学院西安电子科技大学计算机学院693.4 进程间的相互作用n用P，V操作实现司机售票员同步：n司机到站-想继续开车阻塞-售票员开车门-想继续开车门阻塞西安电子科技大学计算机学院西安电子科技大

31、学计算机学院703.4 进程间的相互作用n用P，V操作实现司机售票员同步：n司机到站-想继续开车阻塞-售票员开车门-想继续开车门阻塞-司机继续行车西安电子科技大学计算机学院西安电子科技大学计算机学院713.4 进程间的相互作用n用P，V操作实现进程同步的模型P1.P(S).P2.V(S).西安电子科技大学计算机学院西安电子科技大学计算机学院723.4 进程间的相互作用n用P，V操作实现司机售票员同步：设置信号量S车，S门，初值均为0司机进程while(true)正常行驶；到站停车；V(S门);P(S车);离站开车；售票员进程while(true)售票；P(S门);开车门；关车门；V(S车);西

32、安电子科技大学计算机学院西安电子科技大学计算机学院733.4 进程间的相互作用生产者-消费者问题生产者消费者一次只能放或取一个产品放产品取产品西安电子科技大学计算机学院西安电子科技大学计算机学院743.4 进程间的相互作用同步问题：vP进程（生产者）不能往“满”的缓冲区放产品vQ进程（消费者）不能从“空”的缓冲区取产品西安电子科技大学计算机学院西安电子科技大学计算机学院753.4 进程间的相互作用单缓冲区、一个生产者和一个消费者：设置私用信号量为S缓，S产，初值为1，0生产者进程Pwhile(true)生产一件产品;P(S缓);/*申请一个空缓冲区*/放入一件产品；V(S产);/*释放产品*/

33、消费者进程Qwhile(true)P(S产);/*申请一个产品*/拿出一件产品;V(S缓);消费产品;西安电子科技大学计算机学院西安电子科技大学计算机学院763.4 进程间的相互作用n个缓冲区、k个生产者和m个消费者：增加互斥信号量mutex，初值为1，并设S缓，S产，初值分别为n和0。生产者进程Pwhile(true)生产一件产品;P(S缓);/*申请一个空缓冲区*/P(mutex);放入一件产品；V(mutex);V(S产);/*释放产品*/消费者进程Qwhile(true)P(S产);/*申请一个满缓冲区*/P(mutex);拿出一件产品;V(mutex);V(S缓);消费产品;两个P操

34、作交换？西安电子科技大学计算机学院西安电子科技大学计算机学院773.4 进程间的相互作用n用P，V操作实现进程同步的模型P1.P(S).P2.V(S).西安电子科技大学计算机学院西安电子科技大学计算机学院783.4 进程间的相互作用n对P，V操作的使用应注意：P，V操作都是成对出现的：互斥操作时，它们在同一进程中；同步操作时，它们处于不同的进程。在进程中，P操作的位置和次序至关重要。一般情况下，对互斥信号量的P操作在后。而V操作没有特别的限制。nP，V操作的优点是：原语完备，表达能力强，可以解决任何同步和互斥问题；缺点是不够安全，实现复杂。西安电子科技大学计算机学院西安电子科技大学计算机学院7

35、93.4 进程间的相互作用n读者、写者问题 多个读进程可以同时共享资源，但不能和写进程共享；写进程之间互斥，访问时必须独占资源。需设置一个全局变量对读进程进行计数，当第一个读进程开始进行访问时执行P操作，当最后一个读进程结束访问时执行V操作。现假设读者优先。使用readnum对读者计数，初值为0；mutex是对readnum进行互斥操作的信号量，初值为1；write是写信号量，初值为1。西安电子科技大学计算机学院西安电子科技大学计算机学院803.4 进程间的相互作用读者进程beginP(mutex);readnum=readnum+1;if(readnum=1)P(write);V(mutex

36、);read file;P(mutex);readnum=readnum1;if(readnum=0)V(write);V(mutex);end写者进程beginP(write);write file;V(write);end第一个读者来执行P操作最后一个读者来执行V操作西安电子科技大学计算机学院西安电子科技大学计算机学院813.4 进程间的相互作用 前面程序中，写者会出现“饥饿”现象，可以设计另一种算法，使写者优先，即当有进程读文件时，如果有写进程请求写，那么新的读进程被拒绝，待现有读进程读完后，立即让写进程开始运行，当无写进程运行时才让读进程运行。设置信号量S实现读者与写者或写者之间的互斥

37、，初值为1；用信号量Sn限制系统中最多n个进程，初值为n。西安电子科技大学计算机学院西安电子科技大学计算机学院823.4 进程间的相互作用读者进程Pi(i=1,2,.,n)beginP(S);P(Sn);V(S);read file;V(Sn);end写者进程Pj(j=1,2,.,n)beginP(S);for i=1 to n do P(Sn);write file;for i=1 to n do V(Sn);V(S);end西安电子科技大学计算机学院西安电子科技大学计算机学院833.4 进程间的相互作用n理发师问题：理发店里有一个理发师、一把理发椅、n把供等候理发的顾客坐的椅子。如果没有顾

38、客，则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，进行理发。如果理发师在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。为理发师和顾客各编写一段程序描述他们的行为，要求不能带有竞争条件。西安电子科技大学计算机学院西安电子科技大学计算机学院843.4 进程间的相互作用n设三个信号量：customers，用来记录等待理发师的顾客数（不包括正在理发的顾客），初值为0；barbers，记录正在等候顾客的理发师数，为0或1，初值为0；mutex，用于互斥，初值为1。还需一个变量waiting，初值为0，也用于记录等候的顾客数，实际上是customers的

39、一个副本。之所以使用waiting是因为无法读取信号量的当前值。在该解法中，进入理发店的顾客必须先看等待的 顾客数，如果少于椅子数，他留下来等，否则他就离开。西安电子科技大学计算机学院西安电子科技大学计算机学院853.4 进程间的相互作用理发师进程while(true)P(customers);/如果顾客为0，睡觉 P(mutex);/要求进程等候 waiting=waiting-1;/等候顾客数减1 V(barbers);/一个理发师开始理发 V(mutex);/释放等候 cuthair();/理发顾客进程P(mutex);/进入临界区if(waitingCHAIRS)waiting=wai

40、ting+1;/等候顾客数加1 V(customers);/如果必要，唤醒理发师 V(mutex);/释放访问等候 P(barbers);/如果barbers为0，就睡觉 get_haircut();/坐下等候服务else/没空椅子，就离开V(mutex);西安电子科技大学计算机学院西安电子科技大学计算机学院863.4 进程间的相互作用n管程（monitor）：解决互斥问题的抽象数据类型。进程可以调用管程中的过程，但不能在管程外的过程中直接访问管程内的数据结构。基本思想是集中管理各进程临界区，按不同的管理方式定义模块的类型和结构，用数据表示抽象系统资源，增加模块的相对独立性。西安电子科技大学计

41、算机学院西安电子科技大学计算机学院873.4 进程间的相互作用n管程（monitor）：管程是一种编程语言构件，进入管程的互斥由编译器负责，用户无需关心如何实现互斥。因此，编译器必须能识别出管程并对互斥作出处理。n缺点：在少数几种编程语言外无法使用，兼容性不好。西安电子科技大学计算机学院西安电子科技大学计算机学院883.5 进程通信使用信号量进行进程通信，程序难于理解且易于死锁。而且只能传递信号，不能传递大批量的数据，显然不能满足某些通信需求。于是引入高级通信机制。西安电子科技大学计算机学院西安电子科技大学计算机学院893.5 进程通信n分类：低级通信和高级通信：根据交换信息量的多少和效率的高

42、低，如P、V操作属于低级通信；高级通信包括管道通信和信箱通信。低级通信只传递状态和整数值，信息量小，效率低，传递较多信息需要多次通信，编程复杂，不易理解。高级通信能够传递大批量数据，减轻程序编制的复杂度。包括共享内存模式、消息传递模式和共享文件模式（管道）。西安电子科技大学计算机学院西安电子科技大学计算机学院903.5 进程通信n分类：直接通信：信息由发送方直接传递给接收方，如管道。间接通信：将收发双方进程之外的共享数据结构作为通信中转。西安电子科技大学计算机学院西安电子科技大学计算机学院913.5 进程通信n(1)共享内存模式：一种最快捷高效的方式，在UNIX系统中被使用。系统在内存中指定一

43、个区域作为共享存储区，建立一张段表进行管理，各进程可以申请其中一个存储段，并在申请时提供关键字。若申请的存储区已经被其它进程占有，系统会向申请进程返回关键字，该存储区就链接到了进程的逻辑地址空间，此后进程就可以直接存取共享存储区中的数据了。西安电子科技大学计算机学院西安电子科技大学计算机学院923.5 进程通信n(1)共享内存模式：若申请的存储段尚未分配，系统会按照申请者的要求分配存储段，并在段表中加入该进程的信息。使用共享存储区进行通信时，进程间的互斥或同步要靠其它的机构来实现。key1key2共享存储段表系统页表共享存储区正文共享区虚拟地址空间P1虚拟地址空间数据栈区正文共享区虚拟地址空间

44、P2虚拟地址空间数据栈区西安电子科技大学计算机学院西安电子科技大学计算机学院933.5 进程通信n(2)消息传递方式：消息由发送方形成，通过一定的机制传递给接收方。长度可以固定，也可以变化。每个消息都由消息头和消息体组成，其主要结构包含：v指向发送进程的指针：Sptrv指向下一消息缓冲区的指针：Nptrv消息长度：Sizev消息正文：Text西安电子科技大学计算机学院西安电子科技大学计算机学院943.5 进程通信n(2)消息传递方式：基本工作原理：把消息缓冲区作为进程通信的一个基本单位，借助系统的发送原语Send(A)和接收原语Receive(B)，实现进程间的通信。每当发送进程要发送消息时，

45、发送进程用Send(A)原语把消息从发送区复制到消息缓冲区，并把它挂在接收进程的消息队列末尾。如果该进程因等待消息而处于阻塞状态，则将其唤醒。每当接收进程要读取消息时，用接收原语Receive(B)从消息队列头取走一个消息放到自己的接收区。西安电子科技大学计算机学院西安电子科技大学计算机学院95PCBPCB.Send(R,M)Send(R,M).SIZE:SIZE:消息长度TEXT:TEXT:消息正文.PCB.PCB.消息链指针.Receive(pid,N)Receive(pid,N).SIZE:SIZE:消息长度TEXT:TEXT:消息正文.M:M:N:N:接受进程 R R发送进程 S S消

46、息消息消息.消息缓冲区结构：消息长度 消息正文 发送者 消息队列指针西安电子科技大学计算机学院西安电子科技大学计算机学院963.5 进程通信n(2)消息传递方式：消息队列要看作临界资源，需要互斥访问，在PCB中设置了一个用于互斥的信号量。类似于生产者-消费者问题。直接通信方式：Send(P,message)：发送消息message到进程PReceive(P,message)：从进程P接收消息message间接通信方式：利用信箱作为媒介进行消息传递。西安电子科技大学计算机学院西安电子科技大学计算机学院973.5 进程通信(3)信箱 是一个用来对一定数量的消息进行缓存的地方。是一段存储区，每一个信

47、箱用标识符加以区分，由信箱头和信箱体两部分组成。信箱头存放控制信息，信箱体存放消息内容。一个信箱可以被多个进程共享，就实现了消息的广播发送。vSend(X,mail)：邮件mail发送到信箱X中vReceive(X,mail)：接收信箱X中的邮件mail西安电子科技大学计算机学院西安电子科技大学计算机学院983.5 进程通信n(4)管道(pipe)：是一种共享文件模式，基于文件系统，连接于两个进程之间，以先进先出的方式实现消息的单向传送。在UNIX系统中，管道的创建用函数pipe()实现。该函数返回用于读、写操作的文件描述符fd0,fd1。读管道时调用read()函数，利用参数fd0从管道中读

48、取字节。写管道时调用write()函数，利用参数fd1向管道写信息。西安电子科技大学计算机学院西安电子科技大学计算机学院993.5 进程通信n管道(pipe)：是一种共享文件模式，基于文件系统，连接于两个进程之间，以先进先出的方式实现消息的单向传送。注意：v通过系统调用write()和read()进行管道的读写。v进程间要进行双向通信，通常需要定义两个管道。v只适用于父子进程之间的通信。管道能够把信息从一个进程的地址空间拷贝到另一个进程的地址空间。西安电子科技大学计算机学院西安电子科技大学计算机学院1003.6 线程n进程作为调度基本单位的问题：调度工作量大，耗费系统资源进程间通信延迟大，频率

49、高的通信过程效率低下。没有达到理想的并行度。西安电子科技大学计算机学院西安电子科技大学计算机学院1013.6 线程n线程（thread）：也叫轻型进程，是可执行的实体单元，可代替以往的进程，是处理机调度的基本单位。多线程：单个进程中执行多个线程。典型操作系统有Windows NT、Solaris、Mach和OS/2。在多线程环境中，进程被定义为保护单位和资源分配单位，在一个进程内部可以有多个线程。西安电子科技大学计算机学院西安电子科技大学计算机学院1023.6 线程n线程的特征：执行状态包括创建、就绪、运行、阻塞等当不处于执行状态时，要保存线程上下文环境一个执行栈进程中的所有线程共享所属进程内

50、的主存和其它资源。西安电子科技大学计算机学院西安电子科技大学计算机学院1033.6 线程n不同结构中，进程和线程的区别：单进程单线程：进程就是线程，线程就是进程。单进程多线程：一个进程中包括多个线程，共享该进程的资源。当一个线程修改了数据，其它线程将读出修改后的数据。多进程单线程：等价于单进程单线程的并发执行。多进程多线程：多个进程并发执行，每个进程内多个线程并发执行。进程内线程也存在调度问题。西安电子科技大学计算机学院西安电子科技大学计算机学院1043.6 线程n引入线程的好处：创建和撤销线程的开销小：时间和空间切换迅速：切换内容少通信效率高：共享相同的地址空间并发度高：线程个数没有限制P