进程的描述与控制

1第二章进程的描述与控制2.1前趋图和程序执行2.2进程的描述2.3进程控制2.4进程同步2.5

经典的进程同步问题2.6进程通信2.7

线程的基本概念2.8线程的实现2本章前言在传统的操作系统中，为了提高资源利用率和系统吞吐量，通常采用多道程序技术，将多个程序同时装入内存，并使之并发运行，传统意义上的程序不再能独立运行。此时，作为资源分配和独立运行的基本单位都是进程。操作系统所具有的四大特征也都是基于进程而形成的，并从进程的角度对操作系统进行研究。可见，在操作系统中，进程是一个极其重要的概念。因此，本章专门对进程进行详细阐述。32.1前趋图和程序执行2.1.1前趋图前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于表示一个程序或程序段，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder，亦称偏序关系)或前趋关系(PrecedenceRelation)“→”。4→={(Pi，Pj)|PimustcompletebeforePjmaystart}，如果(Pi，Pj)∈→，可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或程序的执行时间。5图

2-1前趋图

6对于图2-1(a)所示的前趋图，存在下述前趋关系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9或表示为：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)}应当注意，前趋图中不允许存在循环（循环意味着不可实现的前趋关系），在图2-1(b)中就有着下述不可实现的前趋关系：S2→S3，S3→S27尝试画出下述四条语句的前趋图：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b四条语句的前趋关系

82.1.2程序的顺序执行及其特征1.程序的顺序执行含义：前趋程序段未完成时，后继程序段不能开始，如：在进行计算任务时，必须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。若用I代表输入操作，C代表计算操作，P为打印操作，则三个程序段的执行顺序如图2-2(a)中。对一个程序段中的多条语句来说，也有一个执行顺序问题，例如对于下述三条语句的程序段应按图2-2(b)所示的顺序执行:S1:a=x+y;S2:b=a-5;S3:c=b+1;图

2-2

程序顺序执行的前趋图

92.程序顺序执行时的特征(1)顺序性。处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在上一个操作结束之后开始。(2)封闭性(独占)。程序是在封闭的环境下执行的，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响。(3)可再现性。只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。102.1.3程序的并发执行及其特征1．程序的并发执行含义：为增强计算机系统的处理能力和提高资源利用率而采取的一种“同时”操作技术。在图2-2中的输入程序、计算程序和打印程序三者之间，存在着Ii→Ci→Pi这样的前趋关系，以至对同一个作业的输入、计算和打印三个操作，必须顺序执行，但并不存在Pi→Ii+1的关系，因而在对一批程序进行处理时，可使它们并发执行。一般来说，输入程序在输入第i+1个程序时，计算程序可能正在对第i个程序进行计算，而打印程序正在打印第i-1个程序的计算结果。类似于指令流水线（取指、译码、取数、执行），在某一时刻，Pi-1，Ci，Ii+1并发执行。11图2-3并发执行时的前趋图

时间轴12看一个例子有一个公有变量i，其初值为1，现有两个程序：程序1程序2①i++;③i=0;②printf(“%d”,i);④printf(“%d”,--i);如果让程序1和程序2并发执行，在OS不施加并发规则的情况下，屏幕上的显示结果可能是哪些？①→②→③→④，显示结果为：2,-1①→③→②→④，显示结果为：0,-1①→③→④→②，显示结果为：-1,-1。。。思考：这个例子说明了什么问题？132．程序并发执行时的特征1)间断性程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。相互制约将导致并发程序具有“执行-暂停-执行”这种间断性的活动规律。2)失去封闭性程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。这样，某程序在执行时，必然会受到其它程序的影响。143)不可再现性(危害)程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。例如，前面两个程序对于公有变量i的并发执行的结果。程序在并发执行时，由于失去了封闭性，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。153.程序并发执行的条件（Bernstein）Bernstein定理：保证并发时的可再现性。定义R(Pi)={a1,a2,…,am}，a1~am是程序Pi将读取的变量的集合(读集)定义W(Pi)={b1,b2,…,bn}，b1~bn是程序Pi将写入的变量的集合(写集)如：R(c=a-b;)={a,b}W(c=a-b;)={c}若两个程序P1和P2能满足下述条件，则允许并发执行且结果可再现：Bernstein条件：R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)=φ16例：四条语句：S1:a=x+y;S2:b=z+1;S3:c=a–b;S4:d=c+1;右表各情况能否并发？R(S1)={x,y}W(S1)={a}R(S2)={z}W(S2)={b}R(S3)={a,b}W(S3)={c}R(S4)={c}W(S4)={d}S1S2S3S4S1S2S3S4S1S2S3S4S1/√×√S2/×√S3/×S4/172.2进程的描述2.2.1进程的定义和特征1.进程的定义出于程序并发执行的不封闭性和不可再现性，加上程序本身是静态和顺序的，故用程序作为描述其执行过程以及共享资源的基本单位是不合适的。进程是什么(Process)？可以并行执行的计算部分。一个独立的可以调度的活动。一个抽象实体，当它执行某个任务时，将要分配和释放各种资源。行为的规则叫程序，程序在处理机上执行时的活动称为进程。一个具有独立功能的程序对某个数据集在处理机上的动态执行过程和分配资源的基本单位。一个程序在给定活动空间和初始环境下，在一个处理机上的执行过程。182.进程的特征1)结构性特征一个进程由3部分组成：Code、Data、PCB，亦即程序段、数据段、进程控制块，总称为进程实体或进程映像，简称为进程2)动态性特征由创建而产生、由调度而执行、由撤销而消亡。3)并发性特征多进程并发。4)独立性特征进程独立参与运行、调度、分配、回收。5)异步性特征走走停停，完成顺序与开始顺序无关。19现在我们再来讨论进程的定义。进程是程序的一次执行。进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。本书给出的进程定义：进程是程序实体的运行过程，是系统进行资源分配和调度的一个独立单位。推荐定义一个具有独立功能的程序对某个数据集在处理机上的动态执行过程和分配资源的基本单位。20进程与程序的关系与区别进程是动态而暂时的，程序是静态而永久的。(如何理解？)进程具有并发特征，而程序没有。不同的进程可以基于同一程序来创建，只是对应的数据集不同。(举例说明？)某进程在执行过程中可调用多个程序（创建多个子进程）。进程有一定的生命期，而程序是指令的集合，本身无“运动”的含义。没有建立进程的程序不能作为一个独立任务单位得到操作系统的认可。进程包括程序代码、数据和进程控制块。212.2.2进程的基本状态及转换1.进程的三种基本状态1)就绪(Ready)状态进程万事俱备(所有目前所需资源均已申请到手)，只欠CPU。所有的就绪进程组成了就绪队列。2)执行(Running)状态进程已获得CPU并正在执行。在单处理机系统中，任一时刻至多有一个进程处于执行状态；在多处理机系统中，则可能有多个进程同时处于执行状态。3)阻塞(Blocked)状态进程因发生某事件而暂停执行的状态，也称为等待/封锁状态。某事件：如请求I/O，申请缓存空间失败，等待设备资源等…所有的阻塞进程组成了阻塞队列。(也可按阻塞原因构成多个阻塞队列)就绪：有获得CPU的愿望执行：已经获得CPU阻塞：无获得CPU的愿望结束22图2-5进程的三种基本状态及其转换

创建接纳就绪执行进程调度进程中断(如时间片完)终止阻塞I/O请求或等待某事件(阻塞)I/O完成或该事件发生(唤醒)2.进程三种基本状态的转换23回顾进程的三种基本状态之间的迁移就绪→执行进程被调度，获得CPU。执行→阻塞请求资源未被满足或开始I/O操作，让出CPU。执行→就绪中断发生（如时间片完或有抢占式任务到达），让出CPU。阻塞→就绪请求的资源已被满足或结束I/O操作，等待CPU。243．创建状态和终止状态1)创建状态创建一个进程一般要通过两个步骤：首先，为一个新进程创建PCB，并填写必要的控制和管理信息；其次，为该进程分配其初期运行所必需的资源（比如内存）；最后，进程状态便可由创建状态转入就绪状态并插入就绪队列之中。当一个新进程被创建时，系统已为其分配了PCB，填写了进程标识等信息，但由于该进程所必需的资源（如主存资源）尚未分配。虽然此时的进程已拥有了自己的PCB，但进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行，此时所处的状态就是创建状态。252)终止状态进程的终止也要通过两个步骤：首先等待操作系统进行善后处理，然后将其PCB清零，并将PCB空间返还给系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其它进程收集。一旦其它进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。图2-6示出了增加了创建状态和终止状态后，进程的三种基本状态衍变为五种状态。26图2-6进程的五种基本状态及转换

272.2.3.挂起(Suspend)操作和进程状态的转换引入：操作系统的挂起：STR(SuspendToRAM)技术/STD(SuspendToDisk)技术STR意为“挂起到内存”，是一种瞬间开机技术。具体地说，是把数据和系统运行状态信息保存到内存中，然后整机断电，进入STR后，主板仍然会提供3.3V的电压给内存条供电，用来维持内存里的信息，其它设备(包括风扇)则一律断电，以达到了节电的目的。当下次开机(指开启机箱上的电源开关)的时候，电脑将跳过POST(加电自检)等过程，可不通过复杂的OS系统检测，而从内存中读取相应数据直接使系统进入挂起前的状态。一般从启动到进入Windows不会超过10秒钟。实现STR的条件：ATX电源、BIOS和芯片组支持STR、支持ACPI的操作系统（Windows2000、XP、2003、VISTA…）。STR在Windows中的实现：睡眠（待机）功能。STD意为“挂起到硬盘”，原理雷同。在Windows中的实现：休眠功能（Shift+待机）。281.引入挂起状态的原因终端用户的请求。父进程请求。负荷调节的需要。操作系统的需要。对换的需要。…与挂起（Suspend）操作对应的操作是激活（Active）292.引入挂起后进程状态的转换在引入挂起状态后，又将增加从挂起状态(又称为静止状态)到非挂起状态(又称为活动状态)的相互转换。(1)活动就绪→静止就绪。当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys，处于Readys状态的进程不再被调度执行。(2)活动阻塞→静止阻塞。当进程处于未被挂起的阻塞状态时，称它是处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进程便转变为静止阻塞状态，表示为Blockeds。处于该状态的进程在其所期待的事件出现后，将从静止阻塞变为静止就绪。(3)静止就绪→活动就绪。处于静止就绪状态的进程，若用激活原语Active激活后，该进程将转变为活动就绪状态。(4)静止阻塞→活动阻塞。处于静止阻塞状态的进程，若用激活原语Active激活后，该进程将转变为活动阻塞状态。30图

2-7具有挂起状态的进程状态图

接纳I/O完成或该事件发生(唤醒)活动就绪执行进程调度进程中断(如时间片完)静止阻塞活动阻塞I/O请求或等待某事件(阻塞)I/O完成或该事件发生(唤醒)挂起激活静止就绪挂起挂起激活创建终止延迟创建结束31图2-8具有创建、终止和挂起状态的进程状态图

322.2.4

进程管理中的数据结构1．操作系统中用于管理控制的数据结构操作系统为每个资源设置了资源信息表，为每个进程设置了进程信息表，并分类链接为不同的队列，以便于操作系统进行管理图2-9操作系统控制表的一般结构332．进程控制块的作用进程控制块PCB(ProcessControlBlock)PCB包含了该进程全部的描述信息、控制信息以及资源信息，是进程动态特征的集中反映，PCB是进程存在的唯一标志，OS完全通过PCB来感知进程的存在，同时完全依据PCB来对该进程进行并发的控制和管理，PCB需要常驻内存，所有进程的PCB构成了内存中的PCB链表/队列。34例如，当OS要调度某进程执行时，要从该进程的PCB中查出其现行状态及优先级；在调度到某进程后，要根据其PCB中所保存的处理机状态信息来设置该进程恢复运行的现场，并根据PCB中的程序和数据的内存始址，找到其程序和数据；进程在执行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也都需要访问PCB；当进程由于某种原因而暂停执行时，又须将其断点的处理机环境保存在PCB中。35PCB的具体作用（1）作为独立运行基本单位的标志创建进程时为其建立PCB，终止进程时回收其PCB（2）能实现间断性运行方式中断或阻塞时用于保存CPU现场信息，以供下次调度运行时恢复（3）提供进程管理所需要的信息记录程序或数据的地址、该进程所需资源清单等（4）提供进程调度所需要的信息记录进程当前状态、优先级、各类时间信息等（5）实现与其它进程的同步与通信记录同步信号量、通信缓冲区等363．进程控制块中的信息1)进程标识符：进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：①内部标识符(整数形式)；②外部标识符(单词形式)。2)处理机状态（CPU上下文）①通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息；②指令计数器，其中存放了要访问的下一条指令的地址；③程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；④用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。373)进程调度信息①进程当前状态；②进程优先级；③进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；④事件，即阻塞原因。4)进程控制信息①程序和数据的地址，指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；②进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等；③资源清单，即一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；④链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。384.进程控制块的组织方式1)线性方式将系统中所有PCB组织在一张线性表中。实现简单、开销小，适合进程数目不多的系统。PCB1PCB2PCB3…PCBn图2-10PCB线性表示意图392)链接方式这是把具有同一状态的PCB，用其中的链接字链接成一个队列。这样，可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按进程优先级的高低排列，把优先级高的进程的PCB排在队列前面。此外，也可根据阻塞原因的不同而把处于阻塞状态的进程的PCB排成等待I/O操作完成的队列和等待分配内存的队列等。图2-11示出了一种链接队列的组织方式。40图2-11

PCB链接队列示意图0413)索引方式系统根据所有进程的状态建立几张索引表。例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。这种方式适合于进程数量很多的情况。图2-12示出了索引方式的PCB组织。42图

2-12按索引方式组织PCB432.3

进程控制进程控制是进程管理中最基本的功能。它用于创建(Create)一个新进程，终止(Terminate)一个已完成的进程，还负责进程运行中的状态转换：如当一个正在执行的进程因等待某事件而暂时不能继续执行时，将其阻塞(Block)到阻塞队列，而当该进程所期待的事件出现时，又将该进程唤醒(Wakeup)到就绪队列，另外还有挂起(Suspend)和激活(Active)操作。进程控制一般是由OS的内核中的原语来实现的。44原语(Primitive)：是操作系统定义好的，由若干条指令组成的，在系统态下执行的，具备特定功能的一个原子性程序。它与一般过程的区别在于：原语是“原子操作(ActionOperation)”，其中所有动作要么全做，要么全不做。换言之，原语是一个不可分割的基本单位，因此在执行过程中不允许被中断或并发。原语常驻内存。原语的三大特点：系统态（管态）下执行；不允许被中断；不允许并发执行。原语分类：进程控制原语、进程同步原语、进程通信原语等。452.3.1

操作系统内核OS内核：是指操作系统中一些与硬件紧密相关的模块（如中断处理程序）、设备驱动程序、运行频率较高的模块等，常驻内存。处理机的执行状态：系统态（又叫管态或内核态）：高特权，能执行一切指令，访问所有寄存器和存储区。主要负责OS内核运行。用户态（目态）：低特权，仅能执行规定的指令，访问指定的寄存器和存储区。主要负责应用程序运行。OS内核的两大功能：支撑功能：如中断处理、时钟管理、原语操作。资源管理功能：如进程管理、存储器管理、设备管理。462.3.2进程的创建1．进程的层次结构OS允许一个进程去创建另一个进程。这样，由若干级父进程、子进程构成了层次结构。子进程可以继承父进程所拥有的资源。2.进程图(ProcessGraph)进程图是用于描述一个进程的家族关系的有向树，如图2-13所示。图中的结点(圆圈)代表进程。在进程A创建了进程B之后，称A是B的父进程(ParentProcess)，B是A的子进程(ProgenyProcess)。47图2-13进程树

483．引起创建进程的事件(1)用户登录(由系统内核模块负责创建)。(2)作业调度(由系统内核模块负责创建)。(3)提供服务(由系统内核模块负责创建)。(4)应用请求(由父进程负责创建)。494．进程的创建(CreationofProcess)一旦操作系统发现了上述要求创建新进程的事件后，便调用进程创建原语Create()按下述步骤创建一个新进程。有有50入口查PCB链表有空PCB？无取空表PCB(i)并初始化分配资源否PCB(i)入就绪队列PCB(i)入进程家族或进程链返回创建失败等待进程内外标识、处理机状态、优先级、地址、资源清单等内存、文件、设备等512.3.3进程的终止1．引起进程终止的事件1)正常结束：如Halt，Logoff等2)异常结束(1)越界错误。(2)保护错。(3)非法指令。(4)特权指令错。(5)运行超时。(6)等待超时。(7)算术运算错。(8)I/O故障。3)外界干预(1)人工干预（如taskkill）。(2)父进程请求。(3)父进程终止。522．进程的终止过程如果系统中发生了上述要求终止进程的某事件，OS便调用进程终止原语Terminate()，按下述过程去终止指定的进程。53入口查进程链表或进程家族有此PCB？无有该进程正执行？终止执行并转进程调度是否释放该进程所占有的资源并归还给父进程或系统释放该PCB结构并移出进程链表或进程家族返回出错处理该进程有子进程？有处理子进程的终止无542.3.4进程的阻塞（Block）与唤醒（Wakeup）1.引起进程阻塞和唤醒的事件1)请求系统服务或资源而得不到满足时。2)启动某种操作(典型如I/O操作)。3)受合作方进程影响(如生产者进程和消费者进程)。4)无新工作可做。552．进程阻塞过程执行状态→阻塞状态，是一种自主行为。入口停止当前进程的执行并将CPU现场保存到该进程PCB置该进程PCB状态为阻塞该进程PCB入阻塞队列转进程调度返回56在抢占式OS中，可能引发进程调度3．进程唤醒过程阻塞状态→就绪状态，是一种被动行为。入口从阻塞队列中摘下被唤醒进程的PCB置该进程PCB状态为就绪该进程PCB入就绪队列视情况决定是否进程调度返回57应当指出，Block原语和Wakeup原语是一对作用刚好相反的原语，必须成对使用。即：如果进程A调用了阻塞原语将自己阻塞，则必须在与之相合作的另一进程或其他相关的进程中安排唤醒原语，方能在此后某个时间唤醒阻塞进程A；否则，已阻塞进程A将会因不能被唤醒而永远地处于阻塞状态，从而再无机会继续运行。582.3.5进程的挂起（Suspend）与激活（Active）1．进程的挂起过程：内存→外存入口该进程PCB状态为执行？是置PCB为静止就绪并转进程调度否该进程PCB状态为活动阻塞？否是置PCB为静止阻塞置PCB为静止就绪进程换至外存返回592．进程的激活过程：外存→内存入口该进程PCB状态为静止阻塞？否置PCB为活动就绪是置PCB为活动阻塞返回进程换入内存抢占式OS？是处理进程调度否602.4

进程同步2.4.1进程同步的基本概念1．生产者-消费者问题：生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品的缓冲区中投放产品。同步：对多个并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行具有可再现性。61数据结构定义：(假定产品的数据类型为Item)#definen20intin=0,out=0,counter=0;Itembuffer[n],nextp,nextc;数据结构说明：n：缓冲区大小常量。in：下一个产品的存放位置，初值为0，范围0~n-1，操作为in=(in+1)%n。out：下一个产品的消费位置，初值为0，范围0~n-1，操作为out=(out+1)%n。counter：当前缓冲区中的产品总数量，初值为0，范围0~n。生产者执行counter++，消费者执行counter--。nextp：由生产者生产出的产品在放入缓冲区之前的暂存地。nextc：由消费者从缓冲区中取走的产品在消费掉之前的暂存地。Producer→→Consumer共享缓冲区(长度为n)0123…n-2n-1消费指针out↑↑生产指针in

→指针的移动方向62/*生产者程序*/voidProducer(void){

生产一个产品并暂存到nextp;while(counter==n){printf(“库房已满，等待！”);}buffer[in]=nextp;in=(in+1)%n;counter++;}/*消费者程序*/voidConsumer(void){while(counter==0){printf(“库房已空，等待！”);}nextc=buffer[out];out=(out+1)%n;counter--;

将nextc中暂存的产品消费掉;}两个程序共享counter变量，生产者进行counter++，消费者进行counter--，假定counter当前值为1，现在生产和消费各一次，按理说结束后counter的值应该仍为1。但事实上…63在这里r1和r2为寄存器，生产者借助寄存器r1完成counter++操作，消费者借助寄存器r2完成counter--操作。假设counter的初值为1，现在让生产者进程和消费者进程并发执行：①②③④⑤⑥：结果为1④⑤⑥①②③：结果为1①②④⑤③⑥：结果为0①②④⑤⑥③：结果为2上述结果说明：程序的执行失去了可再现性。结论：counter属于临界资源，应互斥访问。生产者加1①r1=counter;②r1++;③counter=r1;消费者减1④

r2=counter;⑤r2--;⑥counter=r2;642．相关概念临界资源——在一段时间内只允许一个进程访问的资源，如打印机、磁带机、公有变量、缓冲区等，即独占资源。临界区——每个并发进程中访问临界资源的程序段，即不允许多个并发进程交叉执行的一段程序。进程间接制约——由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象。对应于进程间的互斥。比如打印机正被进程A使用，若进程B此时提出申请打印机则必阻塞，此时A和B之间就形成了间接制约关系。再如前面生产者进程和消费者进程之间因counter形成间接制约。进程直接制约——一组在异步环境下的并发合作进程，各自的执行结果互为对方的执行条件，从而限制各进程执行速度的过程。对应于进程间的同步。比如当缓冲区空时，生产者进程直接制约了消费者进程。而当缓冲区满时，消费者进程直接制约了生产者进程。65互斥访问——不允许两个或以上的共享某一临界资源的并发进程同时进入各自的临界区。饥饿——某进程长期无法申请到所需资源的现象。死锁——一组并发进程中的每个成员彼此互相等待对方所拥有的资源，且在得到对方的资源之前不会释放自己已拥有的资源，从而导致各并发进程无法继续推进的状态。典型如哲学家进餐问题。663．临界区(criticalsection)若能保证竞争同一临界资源的各并发进程互斥地进入自己的临界区，便可实现诸进程对该临界资源的互斥访问。为此，每个进程在进入自己的临界区之前，应先对欲访问的临界资源的状态进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被另一某进程访问，则该进程不能进入临界区。因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区(entrysection)。相应地，在临界区后面也要加上一段称为退出区(exitsection)的代码，用于将临界资源正被访问的标志恢复为未被访问的标志。67进程A…进入区代码临界区A退出区代码…进程B…进入区代码临界区B退出区代码…检查能否进入临界区，若能则进入并为临界资源加锁进程A对临界资源的访问进程B对临界资源的访问退出时为临界资源解锁在现实生活中能找到很多类似临界区访问的例子。注意：对于竞争不同临界资源的临界区不需要互斥访问。684．同步机制应遵循的规则(1)空闲让进只要临界资源空闲就应该允许进程进入自己的临界区。(2)忙则等待只要临界资源不空闲就应该禁止进程进入自己的临界区。(3)有限等待进程在有限时间内有机会进入自己的临界区(避免“死等”)。(4)让权等待正处于执行状态的进程若进不了临界区就应主动让出CPU并阻塞自己(避免“忙等”)。692.4.2

硬件同步机制（略）关中断利用Test-and-Set指令实现进程互斥利用Swap指令实现进程互斥702.4.3信号量机制信号量(Semaphore)：OS中管理公有资源的有效手段，用来代表可用资源实体的数量。整型信号量记录型信号量AND型信号量一般信号量集711．整型信号量最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被分别称为P、V操作。Wait(S)和signal(S)操作可描述为：由于wait(S)和signal(S)是两个原子操作，因此，它们在执行时是不可中断的。这样，当S<=0时，wait(S)会不断占用CPU进行测试。所以整型信号量的致命缺点是：不符合“让权等待”，即出现“忙等”现象。Wait(S)while(S<=0){;}S--;Signal(S)S++;722．记录型信号量(1)每个信号量S除了有一个整型信号量S.Value之外，还有一个进程阻塞队列S.L，其中记录因该信号量而阻塞的各进程的标识，即：structSemaphore{intValue;/*该资源的当前可用数量*/Process_QueueL;/*因该资源而阻塞的进程队列*/}S;73(2)Wait(S)和Signal(S)操作Block(S.L)：进程将自己阻塞并进入阻塞队列S.L。Wakeup(S.L)：从阻塞队列S.L中唤醒首个进程并放入就绪队列。Wait(S)S.Value--;if(S.Value<0)Block(S.L);Signal(S)S.Value++;if(S.Value<=0)Wakeup(S.L);74在记录型信号量机制中，S.value的初值表示系统中某类资源的数目，因而又称为资源信号量。对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此描述为S.value--；当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个，故S.value++操作表示资源数目加1。若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程正在阻塞，故还应调用wakeup原语，将S.L链表中的第一个阻塞进程唤醒。75假设S.Value当前值为n，则n在不同的值范围代表着不同的含义：

>0：本资源当前空闲可用数目为n个。

=0：无可用资源也无等待该资源的进程。

<0：还需该资源的数目，即当前因该资源而阻塞的进程数为|n|个。例：设资源信号量S.Value初值为1，请按下面的进程表写出从10:00之前到10:30之后S.Value值的变化过程？

时间进程申请归还A10:0010:10B10:0510:20C10:0610:25D10:1510:30记录型信号量：1→0→-1→-2→-1→-2→-1→0→1思考：如果是整型信号量呢？n76(3)利用信号量实现互斥访问若S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量用于进程互斥，即初值为1的信号量称为互斥信号量。对应地，初值不为1的信号量称为资源信号量。为临界资源设置一个互斥信号量mutex，其初值为1，将每个进程的临界区代码置于wait和signal之间：注意：①必须成对使用Wait(mutex)和Signal(mutex)且次序不能颠倒；②遗漏Wait将违反互斥访问原则，使得多个进程同时活跃在临界区，导致系统混乱；③遗漏Signal将导致其它竞争该临界资源的进程饿死(整型)或睡死(记录型)，即其它进程永远无法再进入临界区执行或永远不会被唤醒。每个需访问该临界资源的进程的互斥算法…Wait(mutex);本进程的临界区代码Signal(mutex);…773．AND型信号量例：现有进程A和B，两者都要访问临界资源S1和S2，

已知S1和S2信号量初值均为1。下列访问算法有问题吗？若按①②③④或③④①②的顺序并发，不会出问题。若按①③②④、①③④②、③①②④、③①④②中的任何一种顺序并发，结果将导致死锁！解决方法：某进程所需的资源，要么全给，要么一个都不给。这就是AND型信号量的实现思想。进程A①Wait(S1);②Wait(S2);

临界区代码A;Signal(S2);Signal(S1);进程B③Wait(S2);④Wait(S1);

临界区代码B;Signal(S1);Signal(S2);78SWait(S1….Sn)和SSignal(S1…Sn)操作SWait实际上是将多条连续的Wait原语封装为一条更大的原语，SWait比Wait更安全，但效率稍低。SWait(S1,S2,…,Sn)if(S1>=1&&S2>=1&&…&&Sn>=1){for(i=1;i<=n;i++)Si--;}else{调用该进程进入第一个小于1的信号量Si的阻塞队列Si.L，并将进程的程序计数器恢复到Swait开始处;}SSignal(S1,S2,…,Sn)for(i=1;i<=n;i++){Si++;

唤醒因Si而阻塞的所有进程并送入就绪队列;}794．信号量集在记录型信号量机制中，wait(S)或signal(S)操作仅能对同一信号量施以加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时，便要进行N次wait(S)操作，显然这是低效并且容易导致死锁的。此外，在有些情况下，当资源数量低于某一下限值时，便不予以分配。因而，在每次分配之前，都必须测试该资源的数量，看其是否大于其下限值。基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集”机制。Swait操作可描述如下，其中S为信号量，d为需求值，而t为下限值。80(1)Swait(S，d，d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S，1，1)。此时的信号量集已蜕化为一般的资源信号量(S>1时)或互斥信号量(S=1时)。(3)Swait(S，1，0)。相当于一个可控开关：当S设置为≥1时，允许多个进程进入某特定区；当S设置为0后，将阻止任何进程进入特定区。SWait(S1,t1,d1;…;Sn,tn,dn)if(S1>=t1&&S2>=t2&&…&&Sn>=tn){for(i=1;i<=n;i++)Si=Si-di;}else{调用该进程进入第一个小于ti的信号量Si的阻塞队列Si.L，并将进程的程序计数器恢复到Swait开始处;}SSignal(S1,d1;…;Sn,dn)for(i=1;i<=n;i++){Si=Si+di;

唤醒因Si而阻塞的所有进程并送入就绪队列;}812.4.4信号量的应用1．利用信号量实现进程互斥为使多个进程能互斥地访问某临界资源，只须为该资源设置一个互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区置于wait(mutex)和signal(mutex)操作之间即可。这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对mutex执行wait操作，若该资源此刻未被访问，本次wait操作必然成功，进程便可进入自己的临界区，这时若再有其他进程也欲进入自己的临界区，此时由于对mutex执行wait操作定会失败，因而该进程阻塞，从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后，又应对mutex执行signal操作，以便释放该临界资源。利用信号量实现进程互斥的进程可描述如下：每个需访问该临界资源的进程的互斥算法…Wait(mutex);本进程的临界区代码Signal(mutex);…82例：小王和小张是同一个寝室的同学，该寝室只有一个卫生间，请分别写出小王和小张互斥使用卫生间的步骤。答：设该寝室卫生间的信号量为S，其初值为1小王

Wait(S);

小王使用卫生间的过程;Signal(S);小张

Wait(S);

小张使用卫生间的过程;Signal(S);如果该寝室有两个卫生间呢？832．利用信号量实现前趋关系还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，我们只须使进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面；而在S2语句前面插入wait(S)操作，即：在进程P1中，用：S1；signal(S)；在进程P2中，用：wait(S)；S2；84例：图2-14示出了一个前趋图，其中S1，S2，S3，…，S6是最简单的程序段(只有一条语句)。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。如为保证S1→S2，S1→S3的前趋关系，应分别设置信号量a和b，同样，为了保证S2→S4，S2→S5，S3→S6，S4→S6和S5→S6，应设置信号量c，d，e，f，g。85Semaphorea=0,b=0,c=0,d=0,e=0,f=0,g=0;S1;Signal(a);Signal(b);Wait(a);S2;Signal(c);Signal(d);Wait(b);S3;Signal(g);Wait(c);S4;Signal(e);Wait(d);S5;Signal(f);Wait(e);Wait(f);Wait(g);S6;图2-14前趋图举例

abcdefg862.4.5管程机制(自学内容)1．管程的定义系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。例如，对一台电传机，可用与分配该资源有关的状态信息(busy或free)和对它执行请求与释放的操作，以及等待该资源的进程队列来描述。又如，一个FIFO队列，可用其队长、队首和队尾以及在该队列上执行的一组操作来描述。87利用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据结构实施的操作定义为一组过程，如资源的请求和释放过程request和release。进程对共享资源的申请、释放和其它操作，都是通过这组过程对共享数据结构的操作来实现的，这组过程还可以根据资源的情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。88代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，我们称之为管程。管程被请求和释放资源的进程所调用。Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据”。由上述的定义可知，管程由四部分组成：①管程的名称；②局部于管程内部的共享数据结构说明；③对该数据结构进行操作的一组过程；④对局部于管程内部的共享数据设置初始值的语句。图2-15是一个管程的示意图。89图2-15管程的示意图90管程的语法描述如下：

typemonitor_name=MONITOR；<共享变量说明>；define<(能被其他模块引用的)过程名列表>；use<(要调用的本模块外定义的)过程名列表>；procedure<过程名>(<形式参数表>)；begin

…end;…91function<函数名>(<形式参数表>)：值类型；begin

…end；

…begin<管程的局部数据初始化语句序列>；end92需要指出的是，局部于管程内部的数据结构，仅能被局部于管程内部的过程所访问，任何管程外的过程都不能访问它；反之，局部于管程内部的过程也仅能访问管程内的数据结构。由此可见，管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程(相当于通过围墙的门)才能进入，而管程每次只准许一个进程进入管程，从而实现了进程互斥。93管程是一种程序设计语言结构成分，它和信号量有同等的表达能力，从语言的角度看，管程主要有以下特性：(1)模块化。管程是一个基本程序单位，可以单独编译。(2)抽象数据类型。管程中不仅有数据，而且有对数据的操作。(3)信息掩蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见。94管程和进程不同，主要体现在以下几个方面：(1)虽然二者都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据结构，如消息队列等；(2)二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关的操作，而管程主要是进行同步操作和初始化操作；(3)设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题；(4)进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，因而管程为被动工作方式，进程则为主动工作方式；(5)进程之间能并发执行，而管程则不能与其调用者并发；(6)进程具有动态性，由“创建”而诞生，由“撤销”而消亡，而管程则是操作系统中的一个资源管理模块，供进程调用。952．条件变量在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上，如图2-15所示。仅当另一进程访问完成并释放该资源之后，管程才又调用signal原语，唤醒等待队列中的队首进程。96在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上，如图2-15所示。仅当另一进程访问完成并释放该资源之后，管程才又调用signal原语，唤醒等待队列中的队首进程。97但是仅仅有上述的同步工具是不够的。考虑一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其它进程无法进入管程，被迫长时间地等待。为了解决这个问题，引入了条件变量condition。通常，一个进程被阻塞或挂起的条件(原因)可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问，只能在管程中进行。98管程中对每个条件变量都须予以说明，其形式为：Varx，y：condition。对条件变量的操作仅仅是wait和signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作即可表示为x.wait和x.signal，其含义为：①x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。②x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程。如果存在多个这样的进程，则选择其中的一个，如果没有，则继续执行原进程，而不产生任何结果。这与信号量机制中的signal操作不同，因为后者总是要执行s=s+1操作，因而总会改变信号量的状态。99如果有进程Q因x条件处于阻塞状态，当正在调用管程的进程P执行了x.signal操作后，进程Q被重新启动，此时两个进程P和Q，如何确定哪个执行，哪个等待，可采用下述两种方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件。(2)Q等待，直至P离开管程或等待另一条件。采用哪种处理方式，当然是各执一词。Hoare采用了第一种处理方式，而Hansan选择了两者的折衷，他规定管程中的过程所执行的signal操作是过程体的最后一个操作，于是，进程P执行signal操作后立即退出管程，因而进程Q马上被恢复执行。1002.5经典的进程同步问题2.5.1生产者—消费者问题1．利用记录型信号量解决生产者—消费者问题假定在生产者和消费者之间的公用缓冲池（即库房）中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者—消费者的数据结构可描述如下:/*生产者-消费者数据结构*/Semaphoremutex=1,empty=n,full=0;Itembuffer[n],nextp,nextc;intin=0,out=0;/*buffer[n]：长度为n的缓冲区(0~n-1)，用于存放Item类型的产品。in：下一个产品的存放位置,初值为0,范围0~n-1,操作为in=(in+1)%n。out：下一个产品的消费位置,初值为0,范围0~n-1,操作为out=(out+1)%n。nextp：由生产者生产出的产品在放入缓冲区之前的暂存地。nextc：由消费者从缓冲区取走的产品在消费掉之前的暂存地。mutex：互斥信号量，用于实现互斥访问缓冲区buffer，初值为1。empty和full：资源信号量，分别代表当前缓冲区的空位数(初值为n)和满位数(初值为0)。*/思考：empty和full的值有何关系？能否只定义其中一个？答：empty和full的值相加恒等于n。但由于信号量不允许直接参与算术运算，故两者都要定义。101说明：用于互斥的Wait(mutex)和Signal(mutex)必须在同一程序中配对出现。Wait(empty)和Signal(empty)在不同程序中出现，同理，Wait(full)和Signal(full)在不同程序中出现。Wait(mutex)必须出现在Wait(empty)或Wait(full)之后，否则可能导致死锁。(一般原则，先Wait资源信号量再Wait互斥信号量)同一个程序中的Signal的顺序可以调换。/*生产者程序*/voidProducer(void){

生产一个产品并暂存到nextp;Wait(empty);Wait(mutex);buffer[in]=nextp;in=(in+1)%n;Signal(mutex);Signal(full);}/*消费者程序*/voidConsumer(void){Wait(full);Wait(mutex);nextc=buffer[out];out=(out+1)%n;Signal(mutex);Signal(empty);

将nextc中暂存的产品消费掉;}1022．利用AND信号量解决生产者-消费者问题对于生产者—消费者问题，也可利用AND信号量来解决，即用Swait(empty，mutex)来代替wait(empty)和wait(mutex)；用Ssignal(mutex，full)来代替signal(mutex)和signal(full)；用Swait(full，mutex)来代替wait(full)和wait(mutex)，以及用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。利用AND信号量来解决生产者—消费者问题的算法描述如下：103/*生产者程序*/voidProducer(void){

生产一个产品并暂存到nextp;Wait(empty);Wait(mutex);buffer[in]=nextp;in=(in+1)%n;Signal(mutex);Signal(full);}/*消费者程序*/voidConsumer(void){Wait(full);Wait(mutex);nextc=buffer[out];out=(out+1)%n;Signal(mutex);Signal(empty);

将nextc中暂存的产品消费掉;}Swait(empty,mutex);Ssignal(mutex,full);Swait(full,mutex);Ssignal(mutex,empty);1043．利用管程解决生产者—消费者问题(自学)

在利用管程方法来解决生产者—消费者问题时，首先便是为它们建立一个管程，并命名为ProclucerConsumer，或简称为PC。其中包括两个过程：(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品，消费者应等待。105PC管程可描述如下：

typeproducer-consumer=monitor

Varin,out,count:integer；

buffer:array[0,…,n-1]ofitem；

notfull，notempty:condition；

procedureentryput(item)

begin

ifcount>=nthennotfull.wait；

buffer(in):=nextp；

in:=(in+1)modn；

count:=count+1；

ifnotempty.queuethennotempty.signal；

endprocedureentryget(item)

begin

ifcount<=0thennotempty.wait；

nextc:=buffer(out)；

out:=(out+1)modn；

count:=count-1；

ifnotfull.quenethennotfull.signal；

end

beginin:=out:=0；

count:=0end106在利用管程解决生产者—消费者问题时，其中的生产者和消费者可描述为：

producer:begin

repeat

produceaniteminnextp；

PC.put(item)；

untilfalse；

end

consumer:begin

repeat

PC.get(item)；

consumetheiteminnextc；

untilfalse；

end1072.5.2哲学家进餐问题由Dijkstra提出并解决的哲学家进餐问题是典型的同步问题。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕后放下筷子继续思考。圆桌1081．利用记录型信号量解决哲学家进餐问题经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：Semaphorechopstick[5]={1,1,1,1,1};用记录型信号量实现的哲学家i的进餐方案(0≤i≤4)Wait(chopstick[i]);/*先尝试拿左手边的筷子*/Wait(chopstick[(i+1)%5]);/*再尝试拿右手边的筷子*/开始进餐…Signal(chopstick[i]);/*归还左手边的筷子*/Signal(chopstick[(i+1)%5]);/*归还右手边的筷子*/继续思考…请思考这样的方案安全吗？如果每个哲学家都同时拿到左手边的筷子，那么谁也无法得到右手边的筷子。最终所有人饿死！109上述方案的解决方法(1)至多允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐(如何实现？)。(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐(如何实现？)。(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而