《计算机操作系统第2章进程管理教学课件PPT.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第2章进程管理教学课件PPT.ppt（175页珍藏版）》请在三一办公上搜索。
1、第二章,进程管理,概述 进程的描述 进程控制 线程,进程互斥和同步 进程间通信 死锁问题 进程其他方面的举例,为了描述程序在并发执行时对系统资源的共享，需要一个描述程序执行时动态特征的概念，这就是进程。本章将讨论进程概念、进程控制和进程间关系。,本章要点,基础：进程描述及控制实现：互斥与同步解决：几个经典问题关于：进程通信,重点难点,2.1进程的基本概念,前趋图：是一个有向无循环图。,前趋图用于描述进程之间执行的前后关系。,图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系“”。,节点,概述：,图21(a)中存在着这样的前趋关系：P
2、1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9,图 2-1 前趋图,或表示为：P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9),应当注意，前趋图中必须不存在循环，但在左图中却有着下述的前趋关系：S2S3,S3S2,程序并发执行的目的：提高计算机的处理能力提高资源利用率 分为两种形式：多道程序环境下的多道程序的并发执行在某道程序的几个程序段中，包含可同时执
3、行或可颠倒顺序执行的代码。,计算：顺序执行和并发执行下各设备的使用效率？,顺序执行:并发执行：程序具有封闭性 程序失去封闭性独享资源 共享资源(互为存在条件)可再现性 程序与“计算”不再一一对应有相互制约,进程的定义 进程的特征动态性：进程对应程序的执行进程是动态产生：创建运行消亡进程在其生命周期内，在三种基本状态之间转换独立性：各进程的地址空间相互独立，除非采用进程间通信手段;并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行;异步性：每个进程都以其相对独立的不可预知的速度向前推进;结构化：进程=代码段+数据段+PCB;,进程与程序的区别进程是动态的，程序是静态的：炒菜菜谱进程是暂
4、时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程具有并行特征，程序没有。进程是竞争计算机资源的基本单位。,进程的描述 进程=程序+数据+进程控制块PCB 有人把这三部分称为”进程映像”.程序是进程的不可缺少的组成部分；如果一个程序段允许被共享，则它应该是可重入的，或纯代码段数据是进程处理的对象进程控制块是进程的控制结构，包含了进程的描述信息、控制信息和资源信息以及现场保护区，是进程的唯一标识，系统通过P
5、CB管理和控制进程。通常的程序是不能并发执行的,为使程序能并发执行,应为之配置一进程控制块,即PCB;所谓创建进程是指创建进程实体中的PCB，撤销亦如此。,进程控制块PCB(Process Control Block)进程控制块是由OS维护的用来记录进程相关信息和管理进程而设置的一个专门的数据结构包含了进程的描述信息、控制信息和资源信息以及现场保护区PCB是进程动态特性的集中反映系统通过PCB感知进程的存在，通过PCB中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的,PCB结构的全部或部分常驻内存；PCB随进程的创建而填写，随进程的撤消而释放,有生命周期；系统利用PCB来控制和
6、管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的,进程控制块的内容（数据结构很复杂）,进程标识符：内部进程标识符(process ID)，唯一，通常是一个整数；进程名(外部标识符)，通常基于可执行文件名（不唯一）；用户标识符(user ID)；进程组关系(process group)进程控制信息：程序和数据的地址；进程同步和通信机制；资源清单；链接指针进程调度信息：进程状态、进程优先级、资源信息等处理机状态：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）,PCB的组织方式,链接方式：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表各状态的进程形成
7、不同的链表：就绪链表、阻塞链表,链接,索引方式：,PCB索引表：,执行指针,就绪表指针,等待表指针,空闲表指针,PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9,就绪索引表,143,等待索引表,675,空闲索引表,89,进程的状态及其转换其它状态创建状态：创建(新new)状态 OS 已完成为创建一进程所必要的工作已构造了进程标识符已创建了管理进程所需的表格终止状态（Exit）终止后进程移入该状态它不再有执行资格表格和其它信息暂时保留实用程序为了分析性能和利用率，可能要提取程序的历史信息挂起状态：把一个进程从内存转到外存,挂起状态 这个问题的引入是由于进程优先级的引入，一
8、些低优先级进程可能等待较长时间，从而被对换至外存。目的是：提高处理机效率：就绪进程表为空时，OS将阻塞进程从内存中“挂起”到磁盘的“挂起队列”，再从该队列选另一进程进入内存，或接受一个新进程的请求。为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张用于调试：在调试时，挂起被调试进程（从而对其地址空间进行读写）,状态间的转换挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况：阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以纳入新进程或运行就绪进程；就绪到就绪挂起：当有高优先级阻塞（系统认为会很快就绪的
9、）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程；运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态；,状态间的转换激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况：就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换；阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转为阻塞状态；较少出现。,UNIX V中的进程状态：,另一进程,用户运行态,核心运行态,被抢占状态,僵死状态,内存中睡眠,睡眠且交换,就绪且交
10、换,内存中就绪,创建状态,fork,exit,内存足够,内存不足,交换进,交换进,交换出,交换出,唤醒,唤醒,睡眠,被调度,中断返回,系统调用,返回,被抢占,返回用户态,就绪（/睡眠）且交换态：外存就绪（/睡眠）态。由于内存有限，将原位于内存的程序和数据交换出去，使之位于外存。被抢占态：在进程完成系统调用返回用户态之前，检查是否有优先级更高的进程存在。若有，则当前进程被抢占。,这些控制和管理功能是由操作系统的原语来实现。原语(Primitive)是在管态下执行、完成系统特定功能的过程。原语和机器指令类似，其特点是执行过程中不允许被中断，是一个不可分割的基本单位，原语的执行是顺序的而不可能是并发
11、的。一种原语的实现方法是以系统调用方式提供原语接口，且采用屏蔽中断的方式来实现原语功能，以保证原语操作不被打断的特性。,何时创建进程：用户登录时：作业调度时：用户程序向OS提出服务请求时：如创建打印进程 用户程序调用其他子程序时：创建过程：create(pstat,paddr,pid,prio,pname,）原语 fork（）分配空白PCB及内存，初始化PCB并插入就绪队列。,输入：新进程的符号名，优先级、开始执行地址输出：新创建进程的内部标识符pid 在总链队列上查找有无同名的进程；if（有同名进程）return（错误码）；/*带错误码返回*/从PCB资源池中申请一个空闲的PCB结构；if（
12、无空PCB结构）return（错误码）；/*带错误码返回*/用入口参数设置PCB内容；置进程为“就绪”态；将新进程的PCB插入就绪队列；将新进程的PCB插入总链队列；return（新进程的pid）；,创建原语creat,2、进程的终止：何时终止进程：正常结束：halt，return，exit()，logout。异常结束：越界，访问权限错，特权指令错，非法指令错，运行/等待超时，算术运算错，I/O故障等 OS干预（如死锁时），父进程请求终止某子进程，父进程本身已终止时 终止过程：kill(pid)、exit()原语 找到其PCB，终止运行并重新调度，终止所有子进程，释放资源，将PCB移入空队列。
13、,命令形式为：kill原语 无参数，无返回信息。算法 kill输入：无输出：无 由运行指针得当前进程的pid；释放本进程所占用的资源；该进程从总链队列中摘除；释放PCB结构；转进程调度程序；,3、进程的阻塞：何时阻塞：请求系统服务得不到满足时：启动I/O操作时：合作进程提供的数据尚未到达时：系统进程无新任务可处理时：阻塞过程：wait()原语 保护现场停止执行，修改进程状态，将其PCB插入到阻塞队列，调度另一进程。4、进程的唤醒：当等待事件发生时唤醒。signal()将其PCB改为就绪态，并从阻塞队列移入就绪队列。,正在执行的进程由于其时间片完而被暂停执行，此时进程应从运行态变为 A 状态；处
14、于静止阻塞状态的进程，在进程等待的事件出现后，应转变为 B 状态；若进程正处于运行态时，应终端的请求而暂停下来以便研究其运行情况(执行挂起进程原语)，这时进程应转变为 C 状态，若进程已处于阻塞状态，则此时应转变为 D 状态，若进程已处于就绪状态，则此时应转变为 E 状态；执行解除挂起进程原语后，如挂起进程处于就绪状态，则应转变为 F 态，如处于阻塞状态，则应转变为 G 态；一个进程刚被创建时，它的初始状态为 H。,AH：(1)静止阻塞；(2)活动阻塞；(3)静止就绪；(4)活动就绪；(5)执行。,进程同步与互斥一、进程间的相互作用：无关进程：不影响其它进程，与其它进程的进展情况无关。相关进程
15、：由于共享某些资源，所以一个进程的执行可能会影响其它进程的执行结果。“与时间有关的错误”：对一次只允许一个进程使用的资源（临界资源）的共享过程不加以控制时，会导致程序结果与执行速度有关。（即结果不可再现）例：程序A的n:=n+1和程序B的print(n)、n:=0交叉运行。,进程的同步：直接制约,进程的互斥：由资源共享引起间接制约,互斥：不允许两个以上的进程同时使用临界资源或进入临界区。互斥时的原则：有空让进：当临界区空闲时，允许请求进程立即进入该临界区。无空等待：有进程正在临界区时，其它请求进程等待。有限等待：请求进程应在有限的等待时间内进入临界区。让权等待：当进程不能进入临界区时，应立即释
16、放处理机。,2.3.2 信号量机制,基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。任何复杂的合作需求都可以通过适当的信号结构得到满足。为了发信号，需要使用一个称作信号量的特殊变量。为通过信号量s传送信号，进程可执行原语signal(s)；为通过信号量s接收信号，进程可执行原语wait(s)；如果相应的信号仍然没有发送，进程被阻塞，直到发生传送。这两个操作被称为“P、V”操作。,公用信号量：通常用于实现进程间互斥，初值为1。私有信号量：用于实现进间的同步,初值为0或正整数n。仅允许拥有它的进程实施P操作。信号量S大于等于零时表示可
17、供并发进程使用的资源实体数，但S小于零时表示正在等待使用临界区的进程数。P原语的操作功能V原语的操作功能,除初始化外，对s值的修改只能通过原子操作进行，而不能使用一般的赋值语句。,1 整型信号量 信号量s是个特殊的整型变量，信号s的值描述了可用资源的数量或等待该资源的进程个数 当s0时表示可用资源数；当s0时其绝对值|s|表示等待该资源的进程数。除初始化外，对s值的修改只能通过原子操作进行，而不能使用一般的赋值语句。,s是一个整型量，通过2个原子操作wait(s)和signal(s)来访问。wait(s):while s=0 do no-op/空操作指令，“忙等”s:=s-1;Signal(s
18、):s:=s+1;,2 记录型信号量,由于整型机制中会不断测试不满足“让权等待”而引入type semaphore=recordvalue:integer;L:list of process;endL:为进程链表，用于链接所有等待该类资源进程。procedure wait(s)var s:semaphorebegins.value:=s.value 1;if s.value 0 them block(s.L)end,procedure signal(S)var s:semaphonebegins.value:=s.vaule+1if s.value=0 then wakeup(s.L)end用
19、wait(s)和signal(s)实现同步与互斥。在记录型信号量机制中：s.value初值：表示系统中某类资源的数目。s.value0:表该信号量链表中已阻塞进程的数目。,3 AND型信号量,当不用它时，有可能发生系统死锁。死锁：在无外力作用下的一种僵持状态。特点：要么全分配，要么一个也不分配。,Swait(s1,s2,sn)if s11 and and sn 1 then for i:=1 to n do si:=si-1;endforelse 进程进入第一个达到的满足si1条件的si信号量队列等待，同时将该进程的程序计数器地址回退，置为SP操作处。end if Ssignal(s1,s2,
20、sn)for i:=1 to n do si:=si+1;从所有si信号量等待队列中移出进程并置入就绪队列。endfor,4 信号量集(略),为提高效率而对AND信号的扩充。三种特例：（1）Swait(S,d,d)：允许每次申请d个资源。当资源数少于d时，不予分配。（2）Swait(s,1,1)：S1，记录型信号量。S=1时，互斥型信号量。（3）Swait(s,1,0)，可控开关，当时，允许进入，S1时，不能进入。,信号量小结：一个信号量可用于n个进程的同步互斥；且只能由P、V操作修改。用于互斥时，S初值为1，取值为1(-(n-1)（相当于临界区的通行证，实际上也是资源个数）S=1时：临界区可
21、用 S=0时：已有一进程进入临界区 S=0，S=0 表示可用资源个数 S0 表示该资源的等待队列长度,P、V操作小结：P(S)：请求分配一个资源。V(S)：释放一个资源。P、V操作必须成对出现。用于互斥时，位于同一进程内；用于同步时，交错出现于两个合作进程内。多个P操作的次序不能颠倒，否则可能导致死锁。同步P操作应出现在互斥P操作之前。多个V操作的次序可任意。,用P、V操作实现进程同步的算法可以简单归纳如下：分析每个进程的执行条件和释放条件，针对每个执行条件设置一个信号量，其初值根据初始情况确定；对每个进程做如下处理：在请求条件处执行P（执行条件信号量）；在释放条件处执行V（释放条件信号量）。
22、同步问题与互斥问题的区别：互斥问题中各进程涉及共同的临界资源，因此每个进程中涉及同一个临界资源的临界区中所执行的P、V操作的信号量是相同的；而同步问题中每个进程由于执行条件和释放条件的不同因而其P、V操作涉及的信号量也不同。这是解决这两类问题算法的不同之处。,2.3.3 信号量的应用,信号量的分类：互斥信号量和资源信号量,互斥信号量用于保证互斥的，用于申请或释放资源的使用权，常初始化为1。,资源信号量，用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数。,wait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己。,signal操作用于释放资源（或归
23、还资源使用权），进程执行signal原语时，有责任唤醒一个阻塞进程。,1.利用信号量实现互斥,用于互斥时，对每一个临界资源设一个信号量S，S初值为1，取值为1(-(n-1)（相当于临界区的通行证，实际上也是资源个数）S=1时：临界区可用 S=0时：已有一进程进入临界区 S0时：临界区已被占用，|S|个进程正等待进入,利用信号量实现互斥：对每一临界资源（区）设一信号量S，初值=1。（此时S相当于此临界资源的使用许可证）,进程1：begin P(s)临界区;V(s)end,进程2：begin P(s)临界区;V(s)end,例：有一单向行驶的公路桥,每次只允许一辆汽车通过。当汽车到达桥头时,若桥上
24、无车便可上桥;否则,需等待,直到桥上的汽车下桥为止。若每一辆汽车为一个进程,请用P,V操作编程实现。解：公路桥是1个临界资源,由于它每次只允许一辆汽车通过,故可为它设置一个初值为1的临界资源mutex。汽车过公路桥的动作可描述为：Semaphore mutex=1;CrossBridge()begin行驶到桥头;P(mutex);上桥行驶,从另一头下桥;V(mutex);end;,例：某车站售票厅有20个窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把一个购票者看作一个进程，请用P、V操作管理这些并发进程，要求如下：在主函
25、数中给出信号量的定义和初值。给出一个购票者进程的算法。给出当购票者最多不超过n(设n20)个时，信号 量可能的变化范围。,问题分析,判断该问题是互斥问题还是同步问题：可以将该售票厅的每个窗口看作是一个临界资源为每个购票者进程共享，每个购票者进程只能使用其中一个窗口。售票厅有20个窗口，所以有20个同类的临界资源，一次可以允许20个进程进入，并且先来者先进入。由此可知：该问题满足互斥的2个必要条件（共享临界资源，共享方式是先来者先进入），所以该问题是互斥问题。根据互斥问题的解决方法设置信号量并赋初值：设置一个信号量mutex，初值为20。用信号量的P、V操作将临界区括起来。,算法描述,主函数算法
26、：main()int mutex=20;cobeginP1();Pi();Pn();coend,购票者i的算法：Pi()P(mutex);进入售票厅占有一个窗口购票；V(mutex);,该类问题是指多个合作进程在执行时有先后次序的要求，前后形成前驱后继关系，可以用前趋图描述。在前驱与后继同步问题中，每个进程是否能够执行，取决于它的所有前驱是否执行结束。每个前驱的结束都是它得以执行的必要条件之一，因此，需要针对该进程的每个前驱设置一个信号量，并在该进程开始处执行相应的P操作。同样，如果进程有后继，则当它结束时，需要执行其后继所等待的信号量的V操作，释放其后继所等待的执行条件。,2.利用信号量来描
27、述前趋关系,合作进程的执行次序：例：PA、PB、PC为一组合作进程，其前驱图如右：要求PA执行结束后，PB、PC才能执行。设两个信号量SB、SC分别表示进程PB、PC能否开始执行，初值为SB=0、SC=0。PA：PB：PC：P（SB）P（SC）V（SB）V（SC）,共享单缓冲区的两个进程的同步问题：例：设一计算进程IC和一打印进程OP共用一个单缓冲，如图所示。IC进程负责不断地计算数据并输入缓冲区T中，OP进程负责从缓冲区T中取出数据去打印。,同步约束：OP进程只有在IC进程将数据输入缓冲区后，才能取出打印。IC进程只有在OP进程将数据取出打印后，才能送入下一个计算数据。,SA=0；/SA信号
28、量表示缓冲区中有无信息（初始无数据）SB=1；/SB信号量表示缓冲区中有无空位（初始有空位）,对于前驱后继同步问题的算法可以按下列步骤进行：分析每个进程j，看它有无前驱，如果有，则针对每个前驱i设置一个信号量v，初值皆为0；在每个进程j开始时，针对其每个前驱的信号量Sij执行P操作，有几个前驱执行几个P操作；在每个进程i执行完毕后，针对其每个后继的信号量Sij执行V操作，有几个后继执行几个V操作。其中：i表示前驱进程号，j表示后继进程号。,此时，让他们共享一个公用信号量S，S初值一般为=0，S=0 表示可用资源个数 S0 表示该资源的等待队列长度,例如：设有4个进程，其执行的先后关系如下图所示
29、。用P、V操作实现其同步。,算法描述：main()int s12=s13=s24=s34=0;cobeginp1();p2();p3();p4();coendp1()执行P1自己的程序;V(s12);V(s13);p2()P(s12);执行P2自己的程序;V(s24);,p3()P(s13);执行P3自己的程序;V(s34);p4()P(s24);P(s34);执行P4自己的程序;这样，无论哪个进程先来，只要不是p1进程，都会在执行了相应的P操作后，因为执行条件不成立而被挂到相应信号量的等待队列上，等待其前驱执行该信号量的V操作后将其唤醒，从而保证这些进程并发执行时其执行的时序遵循给定的同步关
30、系。,S1,S2,S3,S4,S5,S6,a,b,c,d,e,g,f,图210 前趋图举例,Var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;Beginparbegin begin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);
31、S6;end;parendend,用信号量描述同步：有一个同步条件设一S，初值S=0。（S为可用资源个数）实现：A进程已执行过程序段1，B进程才能执行程序段2。设一信号量S，初值为0。,A进程 程序段1 L1：V(s);,B进程L2：P(s);程序段2,若P、V操作的信号量初值为1，当前值为-3，则表示有 个等待进程。,3个,2.4 经典进程同步问题,2.4.1生产者消费者问题2.4.2哲学家进餐问题2.4.3读者写者问题,2.4.1 生产者消费者问题,生产者和消费者问题，是相互合作进程关系的一种 抽象，是一个广义的概念，可以代表一类具有相同 属性的进程。,生产者和消费者问题：生产者和消费者进
32、程共享一个固定大小的缓冲区，其中，一个或多个生产者生产数据，并将数据存入缓冲区，并有一个消费者从缓冲区中取数据。,假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。,分别设置两个指针in和out，in指向生产者将存放数据的存储单元，而out指向消费者将取数据的存储单元。,生产者和消费者必须互斥：必须是生产者和消费者互斥进入缓冲区。即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其它任何生产者。,生产者和消费者必须同步：生产者不能向满缓冲区写数据；消费者也不能在空缓冲区取数据。,一个互斥条件：缓冲区一次只能让一个进程访问，设一互斥信号量mutex，初
33、值为1。两个同步条件：缓冲区中至少有一个单元为空时，生产者才 送数。设一信号量empty，表示空缓冲区的数量，初值为n。缓冲区中至少有一个单元为满时，消费者才 取数。设一信号量full，表示满缓冲区的数量，初值为0。,void main()int mutex=1,empty=n,full=0;int in=0，out=0；elemtype buffern;cobegin producer();consumer();coend,full:装满产品的缓冲区数目，初值为0；empty：空缓冲区数目，初值为n；mutex：对缓冲区互斥使用的公用信号量，初值为1；,一、利用记录型信号量解决生产者一消费者
34、问题,void producer()while(TRUE)生产一个数据;wait(empty);/*申请空缓冲区*/wait(mutex);/*实现对缓冲池的互斥使用*/bufferin=生产的数据;in=（in+1）mod n;signal(mutex);signal(full);/*满缓冲区的个数加1*/,void consumer()while(TRUE)wait(full);/*申请满缓冲区*/wait(mutex);/*实现互斥*/消费bufferout中的数据；out=（out+1）mod n；signal(mutex);signal(empty);/*空缓冲区的个数加1*/,二、
35、利用AND信号量解决生产者消费者问题,void producer()while(TRUE)生产一个数据;Swait(empty,mutex);/*申请空缓冲区,实现对缓冲池的互斥使用*/bufferin=生产的数据;in=（in+1）mod n;Ssignal(mutex，full);/*满缓冲区的个数加1*/,void consumer()while(TRUE)Swait(full，mutex);/*申请满缓冲区，实现互斥*/消费bufferout中的数据；out=（out+1）mod n；Ssignal(mutex，empty);/*空缓冲区的个数加1*/,注意：进程应该先申请资源信号量，
36、再申请互斥信号量，顺序不能颠倒。对任何信号量的wait与signal操作必须配对。同一进程中的多对wait与signal语句只能嵌套，不能交叉。对同一信号量的wait与signal可以不在同一个进程中。wait与signal语句不能颠倒顺序，wait语句一定先于signal语句。,2.4.2哲学家进餐问题,1.利用记录型信号量解决哲学家进餐问题,放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：var chopstick:array0,4 of semaphore;所有的信号量都要初始
37、化为1,1）原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。,semaphore chopstick5=1，1，1，1，1;semaphore room=4;void philosopher(int i)while(true)think();wait(room);/请求进入房间进餐 wait(c
38、hopsticki);/请求左手边的筷子 wait(chopstick(i+1)%5);/请求右手边的筷子 eat();signal(chopstick(i+1)%5);/释放右手边的筷子 signal(chopsticki);/释放左手边的筷子 signal(room);/退出房间释放信号量room,2）原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足
39、FIFO 的要求，因此不会出现饥饿的情形。,semaphore chopstick5=1，1，1，1，1;void philosopher(int I)while(true)think();Swait(chopstick(I+1)%5,chopstickI);eat();Ssignal(chopstick(I+1)%5,chopstickI);,方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。semaphore mutex=1;semaphore chopstick5=1，1，1，1，1;vo
40、id philosopher(int I)while(true)think();wait(mutex);wait(chopstick(I+1)%5);wait(chopstickI);signal(mutex);eat();signal(chopstick(I+1)%5);signal(chopstickI);,3）原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进
41、入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。,semaphore chopstick5=1，1，1，1，1;void philosopher(int i)while(true)think();if(i%2=0)/偶数哲学家，先右后左。wait(chopstick i+1 mod 5);wait(chopstick i);eat();signal(chopstick i+1 mod 5);signal(chopstick i);,else/奇数哲学家，先左后右。wait(chopstick i);wait(chopstick i+1 mod 5);e
42、at();signal(chopstick i);signal(chopstick i+1 mod 5);,2.4.3 读者写者问题,读者/写者进程应满足的条件：允许多个读者进程可以同时读数据。不允许多个写者进程同时写数据，即只能互斥写数据。若有写者进程正在写数据，则不允许读者进程读数据。,问题描述：为多个进程访问一个共享数据区，如数据库、文件、内存区以及一组寄存器等的数据问题建立一个通用模型，其中若干读进程只能读数据，若干写进程只能写数据。,解决读者/写者问题，需设置两个信号量：（1）读互斥信号量rmutex,用于使读者互斥地访问共享变量readcount,这里readcount是记录有多少
43、读者正在读;（2）写互斥信号量wmutex,用于实现读写互斥和写写互斥地访问共享文件。读者/写者问题进行如下描述：int rmutex,wmutex,readcount=0;rmutex=1;wmutex=1;,void reader()while(TRUE)wait(rmutex);if（readcount=0）wait(wmutex);readcount+;signal(rmutex);perform read operation;wait(rmutex);readcount=readcount-1;if（readcount=0）signal(wmutex);signal(rmutex);
44、,一、利用记录型信号量解决读者写者问题,void writer()while(TRUE)wait(wmutex);perform write operation;signal(wmutex)；void main()readcount=0;parbegin(reader,writer);,2.5 进程通信,例：建立一pipe，子进程向pipe写，父进程从pipe读。,#include#include main()int x,fd2;char buf30,s30;pipe(fd);/*创建管道*/while(x=fork()=-1);/*循环创建，直至成功*/if(x=0)sprintf(buf,
45、”This is a test.n”);/*写入buf数组*/write(fd1,buf,30);/*把buf中字符写入管道*/exit(0);/*正常结束*/else/*从子进程返回，执行父进程*/wait(0);/*阻塞父进程，直至子进程终止*/read(fd0,s,30);/*从管道中读30B至s数组*/printf(“%s”,s);,子进程执行部分,父进程执行部分,父进程执行部分,2.5.3 消息传递系统中的几个问题,一、通信链路：（1）显式建立：（进程完成）（2）隐式建立：（系统完成）链路类型：（1）由连接方法分：点点链路，多点链路。（2）由通信方式分：单向、双向。（3）由容量分：无
46、容量（无缓冲区）、有（有缓冲区）。,2.5.3消息传递系统中的几个问题,二、消息格式：消息头：含控制信息如：收/发进程名，消息长度、类型、编号消息内容：定长消息：系统开销小，用户不便（特别是传长消息用户）变长消息：开销大，用户方便。,2.5.3消息传递系统中的几个问题,三、进程同步方式1.发送和接收进程阻塞（汇合）用于紧密同步，无缓冲区时。2.发送进程不阻塞，接收进程阻塞（多个）相当于接收进程（可能是多个）一直等待发送进程，如：打印进程等待打印任务。3.发送/接收进程均不阻塞一般在发、收进程间有多个缓冲区时。,2.5.4 消息缓冲队列通信机制,一、数据结构1.消息缓冲区type message
47、 buffer=recordsender:size:text:next:指向下一指针2.PCB中应增数据项：type pcb=recordmq 消息队列指针mutex 消息队列互斥信息量sm消息队列资源信息量（表资源消息数）,2.5.4 消息缓冲队列通信机制,二、发送原语 procedure send(receiver,a)begin getbuf(a.size,i);i.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0;getid(PCB set,receiver.j);wait(j.mutex);insert(j.mq,i);
48、signal(j.mutex);signal(j.sm);end,2.5.4 消息缓冲队列通信机制,三、接收原语procedure receive(b)begin j:=internal name;wait(j.sm);wait(j.mutex);remove(j.mq,i);signal(j.mutex);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;end,2.5.4 消息缓冲队列通信机制,sender:A,size:5,text:Hello,send(B,a),发送区A,sender:A,size:5,text:Hello,receiv
49、e(b),接收区B,a,b,进程A,PCB(B),进程B,2.6 线程,引入线程（Thread）：减少程序并发执行时的时间空间开销。为更好地解决“基于同一数据空间来同时处理多个请求”问题：对拥有资源的基本单位（进程），不频繁地进行切换；对被调度运行的基本单位（线程），不拥有资源，使之轻装运行。,二、线程：线程是一个进程内部的基本调度单位。一个进程可产生多个线程，线程间并发运行。进程是资源分配和抢占处理机的单位，线程不拥有系统资源，进程的资源及地址空间供其所有线程共享。线程执行环境小（仅PC、寄存器、栈等），同一进程的不同线程间切换和通信时开销少。,线程的基本概念,三、线程（轻量型进程）与进程：调度：线程是被系统独立调度运行的基本单位，进 程是资源分配的单位。并发性：一个进程包含若干个线程，线程间并发运 行。拥有资源：线程不拥有系统资源，进程的资源供其 所有线程共享。系统开销：对进程进行操作所需要的系统开销要比 线程大。,
