第4章进程及进程管理

学习内容-64个学时第1章绪论第2章OS的结构和硬件支持第3章OS的用户接口第4章进程及进程管理第5章资源分配和调度第6章内存管理（重点）-20个学时（包括实验学时）第7章设备管理（重点）-7个学时第8章文件系统（重点）-6个学时期末复习-1个学时（基础）-10个学时（重点）-20个学时（包括实验学时）第4章进程及进程管理

4.1进程引入（顺序和并发程序）4.2进程概念4.3进程控制（进程创建、撤销、阻塞、唤醒）4.4进程之间的约束关系（同步和互斥）4.5同步机构4.6进程互斥与同步的实现4.7进程通信4.8线程（了解）4.10进程调度24.1并发活动——进程的引入操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等等。要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引入新的概念——进程。4.1.1顺序程序一个程序由若干个程序段组成，这些程序段的执行必须按照严格的先后次序顺序地执行，即只有当一个操作结束后，才能开始后继操作。这种程序执行的方式就称为程序的顺序执行。例：讨论单道系统的工作情况用户作业的处理，通常分为如下3个步骤：首先输入用户的程序和数据然后进行计算最后打印计算结果例：讨论单道系统的工作情况这三个顺序执行的操作分别设为：I：输入操作C：计算操作P：输出操作顺序程序设计的特点传统的程序设计方法是顺序程序设计，即把一个程序设计成一个顺序执行的程序模块。顺序程序设计具有如下的特点：1.执行的顺序性一个程序的执行是严格按序的，即每个操作必须在下一个操作开始之前结束。顺序程序设计的特点2.环境的封闭性程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。顺序程序设计的特点3.计算过程的可再现性程序执行的结果与初始条件有关，而与执行时间（执行速度）无关。即，只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。顺序程序设计的特点顺序程序设计的顺序性、封闭性和再现性给程序的编制、调试带来很大方便，其缺点是计算机系统效率不高。在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。4.1.2并发程序例：在多道批处理系统中，对大量作业的处理在系统中有n个作业，每个作业都有3个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,3,...,n)。批量作业执行的先后次序4.1.2程序的并发执行这些作业在系统中执行时是对时间的偏序：有些操作必须在其它操作之前执行，这是有序的；但有些操作是可以同时执行的。也就是说：I1、C1、P1的执行必须严格按照I1、C1、P1的顺序，I2、C2、P2的执行也必须严格按照I2、C2、P2的顺序，而C1与I2，P1与C2、I3是可以同时执行的。讨论(1)哪些程序段的执行必须是顺序的？为什么？(2)哪些程序段的执行可以是并行的？为什么？并发执行的条件该条件在1966年首先由Bernstein提出，又称之为Bernstein条件假设，对于程序pi：R(pi)={a1，a2，…，an}，表示程序pi在执行期间引用的变量集，即要读的变量集合；W(pi)={b1，b2，…，bm}，表示程序pi在执行期间改变的变量集，即要写的变量集合；若两个程序p1和p2能满足Bernstein条件：引用变量集与改变变量集交集之和为空集。并发执行的条件Bernstein条件：任意两个程序P(i)和P(j)，有：R(pi)W(pj)=;W(pi)R(pj)=;W(pi)W(pj)=;前两条保证程序在读数据时数据没有变化；最后一条保证写的结果不冲突。

并发执行的条件例如，有如下四条语句：S1:a:=x+yS2:b:=z+1S3:c:=a-bS4:w:=c+1哪些语句能并发执行？哪些语句不能并发执行？并发执行的条件分析有：R(S1)={x，y}，R(S2)={z}，R(S3)={a，b}，R(S4)={c}；W(S1)={a}，W(S2)={b}，W(S3)={c}，W(S4)={w}。可见S1和S2可并发执行，因为，满足Bernstein条件。其他语句间因变量交集之和非空，并发执行可能会产生与时间有关的错误。程序并发执行（定义）程序并发执行：若干个程序段同时在系统中运行，这些程序的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。程序并发执行的描述程序并发执行的描述：cobegin

S1;S2;S3;...;SNcoend;其中Si(i=1,2,3,...,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。说明：co是concurrent的头两个字符。这是著名的荷兰计算机科学家Dijkstra提出的。程序并发执行的描述假设有一个程序有S0-Sn+1个语句，其中S1-Sn语句是并发执行的，程序描述如下：

S0;

cobegin

S1;S2;S3;...;SN

coend;Sn+1;采用并发程序设计的目的目的是：充分发挥硬件的并行性，消除处理器和I/O设备的互等现象，提高系统效率。机器部件能并行工作仅仅是有了提高效率的可能性，其实现还需要软件技术去利用和发挥，这种软件技术就是并发程序设计。并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到单处理器的系统中。思考顺序程序有一个很大的特性就是：运行结果具有确定性，与程序的运行时间及运行速度无关。那么，当程序并发执行时是否还具有这个特性呢？4.1.3与时间有关的错误两个交互的并发进程，其中一个进程对另一个进程的影响常常是不可预期的，甚至无法再现。这是因为两个并发进程执行的相对速度不可预测，交互进程的速率不仅受到处理器调度的影响，而且还受到与其交互的并发进程的影响，甚至受到与其无关的其他进程的影响，所以，一个进程的速率通常无法为另一个进程所知。4.1.3与时间有关的错误因此，对资源的共享充满了危险，各种与时间有关的错误就可能出现，与时间有关的错误有两种表现形式：结果不唯一永远等待为了说明与时间有关的错误，现观察下面的例子：例1（结果不唯一）购买飞机票问题假设一个飞机订票系统有两个终端，分别运行进程Tl和T2。该系统的公共数据区中的一些单元Aj(j=l，2，…)分别存放某月某日某次航班的余票数，Tl和T2共享Aj。飞机票售票程序如下：例1（结果不唯一）购买飞机票问题。例1（结果不唯一）购买飞机票问题由于T1

和T2

是两个可以同时执行的并发进程，它们在同一个计算机系统中运行，共享与余票数Aj，因此，有可能出现几种不同的运行情况。并发多道程序，有3个特点：多道宏观上并行微观上串行微观上串行的含义是多道程序轮流和分时的占有处理机，交替执行。当这个交替执行交替的不巧的时候，就会产生与时间有关的错误。例1（结果不唯一）购买飞机票问题例如，可能出现如下所示的运行情况：T1:X1=Aj;//（T1执行此处暂停，T2执行）T2:X2=Aj;T2:X2=X2-1;Aj=X2;输出一张票；//（T2执行完毕后，T1才接着执行）T1:X1=X1-1;Aj=X1;输出一张票；例1（结果不唯一）购买飞机票问题假设初值Aj=5，在这种执行顺序下买了两张票，可是Aj的终值却为4。（为什么？）显然，两个旅客各自都买到了一张同天同次航班的机票，可是，Aj的值实际上只减去了1，造成余票数不正确。特别是，当某次航班只有一张余票时，就可能把这一张票同时售给了两位旅客，这是不能允许的。思考1：再考虑另外一种情况：T1:X1=Aj;T1:X1=X1-1;Aj=X1;输出一张票；T2:X2=Aj;T2:X2=X2-1;Aj=X2;输出一张票；还假设初值Aj=5，在这种执行顺序下买了两张票，可是Aj的终值为多少？（思考之）答案：为3，没有出错。思考2：而如果出现如下所示的运行情况：T1:X1=Aj;T2:X2=Aj;T1:X1=X1-1;Aj=X1;输出一张票；T2:X2=X2-1;Aj=X2;输出一张票；还假设初值Aj=5，在这种执行顺序下买了两张票，可是Aj的终值为多少？（思考之）答案：为4，还是出现一票两买。例2（永远等待）内存管理问题假定有两个并发进程borrow和return分别负责申请和归还主存资源，算法描述中，x表示现有的空闲主存总量，B表示申请或归还的主存量。并发进程算法及执行描述如下：34例2（永远等待）内存管理问题由于borrow和return共享了表示主存物理资源的变量x，对并发执行不加限制会导致错误。例如，一个进程调用borrow申请主存，在执行了比较B和x的指令后，发现B>x，但在将要执行{申请进程进入等待队列等主存资源}时（这条语句没有执行），另一个进程调用return抢先执行，归还了所借全部的主存资源。这时，由于前一个进程borrow还未成为等待状态，return中的{释放等主存资源的进程}相当于空操作，即，当前等待队列中没有进程。以后当调用borrow的进程被设置成等主存资源状态时，可能己经没有其他进程来归还主存资源了，从而，申请资源的进程borrow可能永远处于等待状态。一道考研题兄弟俩共用一个账户，每次限存或取10元，存钱与取钱的进程如下所示，由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在哥哥第三次存钱时，弟弟在取钱，请问最后的帐号上amount可能有多少钱？（南京大学2000年考题5分）：答案：amount=20,30,10答案分析4种情况：savetake,amount=20;takesave,amount=20;takesavetake（take没有运行完，先运行前2个语句，等save运行完之后，再运行最后一条语句）,amount=10;savetakesave（save没有运行完，先运行前2个语句，等take运行完之后，再运行最后一条语句）,amount=30;并发程序的特点并发程序执行虽然提高了系统的处理能力和机器的利用率，但它也带来了一些新的问题，产生了与顺序程序不同的特征：一、失去了程序的封闭性和可再现性

如果程序执行的结果是一个与时间无关的函数，即具有封闭性。若一个程序的执行可改变另一个程序的变量（共享变量,例如，现有内存数x，银行账号amount），程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。一、失去了程序的封闭性和可再现性

例：讨论共享公共变量的两个程序，它们执行时可能产生的不同结果。设：初值n=0，程序A每执行一次都要做n加1的操作，程序B每隔一定时间打印出n值，并将它重新置为零。程序A、B并发执行。讨论n的最终值与其打印值。举例说明n=0;举例说明即产生与时间有关的错误——结果不唯一000100二、程序与计算不再一一对应在程序顺序执行时，一个程序总是对应一个具体的计算。但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的。例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。二、程序与计算不再一一对应三、程序并发执行的相互制约在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的也有间接。直接的相互制约关系-同步间接的相互制约关系-互斥历史回顾回头来，我们再看看操作系统的第三个特性：不确定性：在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况，进程的执行不是一贯到低，而是“走走停停”。思考：并发和并行的区别并行和并发的区别

并行同一时刻，两个事物均处于活动状态例如：多CPU环境下，每个程序有各自的CPU，真正的同时执行

并发（多道程序运行方式）宏观上存在并行特征，微观上存在顺序性同一时刻，只有一个事物处于活动状态例如：分时操作系统中多个程序的同时运行，共享CPU（只有一个CPU），轮流使用CPU49OS对进程的要求OS必须交替执行多个进程，以便最大程度的使用CPU，同时提供合理的响应时间。OS必须将资源分配给进程，同时避免死锁（永远等待）。OS必须支持进程间通信以及用户进程创建。50第4章进程及进程管理

4.1进程引入（顺序和并发程序）4.2进程概念4.3进程控制（进程创建、撤销、阻塞、唤醒）4.4进程之间的约束关系（同步和互斥）4.5同步机构4.6进程互斥与同步的实现4.7进程通信4.8线程（了解）4.10进程调度514.2.1进程的定义在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引人新的概念－－进程。进程的概念来自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系统中也曾叫过任务（task)。进程的定义-很多行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra）。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw）进程是执行中的程序。（KenThompsonandDennisRitchie）教材上给出的进程的定义：进程，即是一个具有一定独立功能的程序关于某个数据集合的一次活动。进程与程序的区别与联系1、程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并行（并发）活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。阅读菜谱准备原料烹制菜肴饭菜阅读洗衣机手册准备衣服、洗衣粉设定参数，洗衣服干净衣服程序输入运行输出程序输入运行输出分时切换洗衣进程做饭进程进程与程序的区别55进程的类型在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程：执行操作系统核心代码的进程。系统进程起着资源管理和控制的作用。2、用户进程：执行用户程序的进程。系统进程与用户进程的区别1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；2、用户进程不能直接做I/O操作，而系统进程可以做显示的、直接的I/O操作。3、系统进程在管态下活动，而用户进程则在用户态（目态）下活动。4.2.2进程的状态进程在系统中的活动规律是：执行——暂停——执行进程的三种基本状态：运行状态就绪状态等待状态（又称阻塞、挂起、睡眠）进程的基本状态1、就绪状态（Ready)存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行，这些进程所取的状态为就绪状态。（可有多个进程处于此状态）2、运行状态(Running）当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，某一时刻，总是只有一个进程处于此状态，这也就是所谓的微观上串行。）3、等待状态（Wait)若一个进程正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU，它也无法执行，则称该进程处于等待状态。进程状态变迁图进程的状态不是固定不变的，而是在不断变换。如下图所示：61AThree-stateProcessModelReadyRunningBlockedEventOccursDispatchTime-outEventWait运行就绪等待进程的状态及其转换-动画63在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：

就绪—运行（进程调度）

运行—就绪（时间片到等）

运行—等待（服务请求，如请求I/O等）

等待—就绪（服务完成/事件来到）进程状态转换：进程转换就绪运行调度程序选择一个新的进程运行运行就绪运行进程用完了时间片运行进程被中断，因为一个高优先级进程处于就绪状态进程转换运行等待OS尚未完成服务(例如，系统功能调用)对一资源的访问尚不能进行初始化I/O且必须等待结果等待某一进程提供输入等待就绪当所等待的事件发生时/请求的服务已经完成创建状态：创建一个新的进程终止状态：完成任务，结束进程挂起（suspend）状态进程没有占用内存空间处在挂起状态的进程映像在磁盘上进程的其它状态五状态进程模型操作系统的控制结构操作系统作为资源管理和分配程序，其本质任务是自动控制程序的执行，并满足进程执行过程中提出的资源使用要求。因此，操作系统的核心控制结构是进程结构(如何定义和实现它？)，资源管理的数据结构将围绕进程结构展开。在研究进程的控制结构之前，首先介绍一下操作系统的控制结构。操作系统的控制结构为了有效的管理进程和资源，操作系统必须掌握每一个进程和资源的当前状态。操作系统通常是通过构造一组表（思考：表是什么？怎么编程实现？）来管理和维护进程和每一类资源的信息。操作系统的控制表分为四类：进程控制表存储控制表I/O控制表文件控制表操作系统的控制结构71操作系统的控制结构进程控制表用来管理进程及其相关信息。存储控制表用来管理一级（主）存储器和二级（辅）存储器。I/O控制表用来管理计算机系统的I/O设备和通道。文件控制表用来管理文件。4.2.3进程的描述——进程控制块(1)什么是进程控制块？描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构（怎么去编程实现？），称为进程控制块pcb(processcontrolblock)或称为进程描述器(processdescriptor)。4.2.3进程的描述——进程控制块系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。进程控制块进程控制块PCB集中反映一个进程的动态特征。在进程并发执行时，由于资源共享，带来各进程之间的相互制约。显然，为了反映这些制约关系和资源共享关系，在创建一个进程时，应首先创建其PCB（怎么创建？），然后才能根据PCB中的信息对进程实施有效的管理和控制。当一个进程完成其功能时之后，系统则释放PCB（怎么释放？），进程也随之消亡。一个比喻：PCB就象我们的户口。PCB的结构PCB的结构说明1、进程标识符/name：每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。UNIX系统中就是一个整型数，在进程创建时由系统赋予。2、进程当前状态status：说明本进程目前处于何种状态（运行、就绪、等待），作为进程调度时的主要依据。PCB的结构说明3、当前队列指针next：登记与本进程处于同一队列的下一个进程的PCB的地址。PCB的结构说明4、总链指针all-q-next：登记在系统总链队列中，下一个进程的pcb地址。5、执行程序开始地址

start-addr：该进程的程序将从此地址开始执行。6、进程优先级priority：

进程的优先级反映进程的紧迫程度，通常由用户指定和系统设置。PCB的结构说明7、CPU现场保护区cpustatus：当处理机被中断时，各种寄存器的内容都必须保存在被中断进程的PCB中，以便在该进程重新执行时，能从断点继续执行。通常被保护的信息有：通用寄存器、指令计数器PC以及程序状态字PSW等。例如，我们下课，这时我要记住这次讲到什么地方，以便下次课接着讲。PCB的结构说明8.通信信息communicationinformation：每个进程在运行过程中和别的进程进行通信时所记录的有关信息。9.家族关系processfamily：有的系统还允许一个进程创建自己的子进程，这样会形成一个进程家族。在pcb中必须指明本进程与家族的关系，如它的子进程和父进程的标识符。PCB的结构说明10.占有资源清单own-resource

记录进程占用系统资源的情况。说明：PCB包含的这些信息，通常占几百-几千字节思考：如何编程实现这样一个数据结构struct？PCB的实现？实验：进程调度实验中用到的主要数据结构是进程控制块PCB，其结构如图所示：数据项作用next前向指针，指向下一个进程控制块，用来构成进程队列process_name进程名称process_number进程号，当进程有相同名称时，用来区分进程process_start_moment进程启动时刻process_need_time进程要求运行时间process_time_slice时间片process_priority优先数PCB的实现typedefstructpcb{ structpcb*next;//下一个进程控制块指针 charprocess_name[20];//进程名 intprocess_number;//进程编号 intprocess_start_moment;//进程启动时刻 intprocess_need_time;//要求运行时间 intprocess_time_slice;//时间片 intprocess_priority;//优先数}PCB;//自定义数据类型：进程控制块PCBpcb_table[MAX_PROCESS];//进程控制块表，数组进程控制块表即数组pcb_table说明：队列指针为了便于对进程实施管理，通常把具有相同状态的进程链接在一起，组成各种队列。例如：把所有处于就绪状态的进程链在一起，称为就绪队列。把所有因等待某事件而处于等待状态的进程链在一起就形成了等待（阻塞）队列。PCB的组成方式在一个系统中，通常可拥有数十个、数百个，乃至数千个PCB，为了能对它们进行有效的管理，应该用适当的方式将它们组织起来，目前常用的组织方式有两种：链接方式、索引方式。系统中进程队列分类：就绪队列、等待队列、运行队列。就绪队列：整个系统一个等待队列：每一个等待事件一个运行队列：单机系统中整个系统一个88PCB表组织方式-索引方式索引表就绪队列等待队列1等待队列2PCB1PCB2PCB3PCB4PCB5PCB6PCB7…PCBnPCB表系统根据所有进程的状态，建立几张索引表，例如：就绪索引表，阻塞索引表等，在索引表的表目中，记录具有相应状态的PCB在PCB表中的地址。进程队列及其管理当发生的某个事件使一个进程的状态发生变化时，这个进程就要退出所在的某个队列而排入到另一个队列中去。一个进程从一个所在的队列中退出的事件称为出队。一个进程排入到一个指定的队列中的事件称为入队。处理器调度中负责入队和出队工作的功能模块称为队列管理模块，简称队列管理。下图给出了操作系统的队列管理和状态转换示意图。91①就绪队列结构及指针①就绪队列结构及指针编程实现PCB*ready_q_start=&pcb_table[0];//就绪队列头指针指向第一个进程②等待队列结构及指针②等待队列结构及指针③运行指针③运行指针编程实现例子：先来先服务进程调度算法：选择就绪队列的队首进程让其运行running=ready_q_start;//将就绪队列的头指针指向的第一个进程的地址赋值给running指针④总链队列结构及指针系统中存在大量的进程，它们依各自的状态分别处于相应的队列中，这便于对进程实施调度。但是当进行某些管理功能时，如创建进程的功能时（进程的初始化），就感到系统具有所有进程的总链是十分方便的。譬如检查进程名是否重名，进入各个队列中查询是很麻烦的。进程控制块表即数组pcb_table第4章进程及进程管理

4.1进程引入（顺序和并发程序）4.2进程概念4.3进程控制（进程创建、撤销、阻塞、唤醒）4.4进程之间的约束关系（同步和互斥）4.5同步机构4.6进程互斥与同步的实现4.7进程通信4.8线程（了解）4.10进程调度1024.3.1进程控制的概念进程是有生命周期的，产生、运行、暂停、终止。对进程的这些操作叫进程控制。进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度）。进程控制进程控制包括：

进程创建、

进程撤消、

进程阻塞、

进程唤醒这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。4.3.1进程控制的概念原语的概念原语是一种特殊的系统调用命令，它可以完成一个特定的功能，一般为外层软件所调用，其特点是原语执行时是不可中断的，所以原语操作具有原子性，它是不可再分的。常用的进程控制原语常用的进程控制原语有：创建原语撤消原语阻塞原语唤醒原语4.3.2进程创建进程创建原语的形式:create(name,priority,start_addr)其中：name为被创建进程的标识符priority为进程优先级start_addr为程序的开始地址UNIX/Linux系统：fork()108109进程创建进程创建原语的功能：创建一个具有指定标识符的进程，建立进程的PCB结构。进程创建的步骤所谓资源池也就是pcb的集合，它是在系统存储区域开辟的一片区域，用来集中存放所有的进程控制块。自己编程实现？首先为进程分配一个唯一标识号ID初始化进程控制块表即数组pcb_table编程实现如何实现：向PCB资源池/进程控制表里申请一个空的PCB？设置一个pcb_free指针，该指针总是指向第一个空的PCB。PCB*pcb_free=NULL;//进程空闲队列的头指针，初始为空pcb_free=&pcb_table[0];//编程实现if(pcb_free==NULL)//如果无空闲的PCB则返回空指针returnNULL;else //如果有空闲的PCB{pcb_free=pcb_free->next;//空闲PCB指针下移一个节点PCB初始化；PCB插入就绪队列和总链队列；}进程创建后队列的变化图-修改链接指针编程实现新建的PCB插入就绪队列队尾：PCB*p=pcb_free;//定义了一个局部变量p，代表新建进程if(pcb_ready==NULL) //如果就绪队列为空pcb_ready=pcb_ready_rear=p;//则新PCB为就绪队列的唯一节点，队首指针与队尾指针相同else //如果就绪队列不空，新建的PCB插入就绪队列队尾{ pcb_ready_rear->next=p;//原就绪队列的最后一个节点指向新建的PCB pcb_ready_rear=p;//修改就绪队列的尾指针，指向新建的PCB}4.3.2进程撤销进程完成其任务，希望终止时，调用撤消进程的系统调用（进程撤消原语）撤消进程。（相当于某人死亡后，就要去派出所消户口）在一般操作系统中进程撤消的系统调用是：killUNIX系统中是exit()

4.3.2进程撤销撤消进程以下几种情况导致进程被撤消：该进程已完成所要求的功能而正常终止由于某种错误导致非正常终止父进程要求撤消某个子进程进程撤销进程撤消原语的形式：kill(或exit)该命令没有参数，其执行结果也无返回信息。进程撤消原语的功能：撤消当前运行的进程。将该进程的pcb结构归还到pcb资源池，所占用的资源归还给父进程，从总链队列中摘除它。进程撤销4.3.3进程阻塞进程阻塞亦称进程等待：当一个处在运行状态的进程，因等待某个事件的发生（如等待打印机）而不能继续运行时，将调用进程阻塞系统调用，把进程的状态设置为阻塞状态，并调用进程调度程序（等于让出处理机）。4.3.3进程阻塞进程从运行状态转换成阻塞状态是由进程阻塞原语实现的，因此，调用进程阻塞操作是在进程处于运行状态下执行的。它的执行将引起等待某事件的队列的改变。例如，进程是因等待打印机而进入阻塞状态，则该进程将加入到等待打印机的队列。4.3.3进程阻塞进程阻塞的内部调用形式（UNIX系统）：sleep(chan,pri)其中：chan表示进程挂起（睡眠）的原因pri进程被唤醒后的优先级

一般调用形式：susp(chan)4.3.3进程阻塞4.3.3进程阻塞

在阻塞队列中插入了一个新的进程4.3.3进程唤醒一个正在运行的进程会因等待某事件（例如，等待打印机）的发生，由运行状态转换成阻塞状态。而当它等待的事件发生后，这个进程将由阻塞状态转换成就绪状态。这种转换由进程唤醒操作完成。1294.3.3进程唤醒进程唤醒原语的形式：wakeup(chan)参数chan：进程等待的原因进程唤醒原语的功能：当进程等待的事件发生时，唤醒等待该事件的所有进程或等待该事件的首进程。4.3.3进程唤醒例如，打印机在完成了打印完成的操作后，就去检查等待打印机的队列，若不为空，则调用进程唤醒操作，唤醒一个（或多个）等待打印机的进程。

4.3.3进程唤醒算法：wakeup输入：chan：等待的事件（阻塞原因）输出：无{

找到chan的等待队列的指针；

for(该队列不为空）

{从队列中移出一个进程；设置进程状态为“就绪”，并加入到就绪队列；

}}4.3.3进程唤醒按此算法，是把等待在chan事件上的所有进程唤醒。也有的系统只唤醒一个等待chan事件的进程，若这样处理，等待队列就要按某种优先级排队。进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。复习：进程的阻塞与唤醒

阻塞原因：请求系统服务；启动某种操作，如I/O；新数据尚未到达；暂时无新工作可做等。当出现阻塞事件，进程调用阻塞原语将自己阻塞。并将其状态变为“阻塞状态”，并进入相应事件的阻塞队列；当阻塞进程期待的事件发生，有关进程调用唤醒原语，将等待该事件的进程唤醒。并将其状态变为“就绪状态”，插入就绪队列。一般,进程可以自己阻塞自己；而唤醒操作则由操作系统，或其它相关进程来完成，进程无法自己唤醒自己。

第4章进程及进程管理

4.1进程引入（顺序和并发程序）4.2进程概念4.3进程控制（进程创建、撤销、阻塞、唤醒）4.4进程之间的约束关系（同步和互斥）4.5同步机构4.6进程互斥与同步的实现4.7进程通信4.8线程（了解）4.10进程调度1354.4进程的相互制约关系在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。产生这种错综复杂的相互制约关系的原因有二：资源共享进程合作进程间的关系进程之间有两种关系：第一种是竞争关系，从而有进程的互斥是解决进程间竞争关系的手段。第二种是协作关系，某些进程为完成同一任务需要分工协作。进程的同步是解决进程间协作关系的手段。进程间的关系进程的互斥是指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。临界区管理可以解决进程互斥问题，后续课程将详细介绍临界区的解决方案。动画-互斥进程间的关系进程的同步是解决进程间协作关系的手段。指一个进程的执行依赖于另一个进程的消息，当一个进程没有得到来自于另一个进程的消息时则等待，直到消息到达才被唤醒。动画-同步进程间的关系对于协作关系有如下例子：设input、process、和output三个进程分工协作完成读入数据、加工处理和打印输出任务，这是一种典型的协作关系。操作系统要确保诸进程在执行次序上协调一致：没有输入完一块数据之前不能加工处理没有加工处理完一块数据之前不能打印输出等等4.4.2互斥的概念例子：宿舍固定电话的使用打印机的使用还有内存变量、指针、数组等等也是临界资源临界资源说明例1：两个进程A、B共享一台打印机，

若不加以控制，两个进程的输出结果可能交织在一起，很难区分。临界资源说明例2：两个进程共享一个变量x，设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。这两个进程在一个处理机C上并发执行，两个进程共享一个变量x时，两种可能的执行次序：情况B为x=10+1

说明以前的课程也讲到了与时间有关的错误，其实就是因为共享变量，这个共享的变量就是临界资源。如果不对临界资源加以控制，那么就可能出现错误，这就是本节要解决的问题。什么是临界资源特点：当两个进程公用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。一次仅允许一个进程使用的资源称为临界资源。

哪些是临界资源？临界资源：物理设备，如输入机、打印机、磁带机等都具有这种性质。软件资源，如公用变量、数据、表格、队列等也都具有这一特点。什么是临界区临界区：在每个进程中，访问临界资源的那段程序能够从概念上分离出来，称为临界区或临界段。动画什么是临界区什么是互斥？互斥：在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。例如上图所示：进程A正在执行csa段时，进程B就不能进入csb段执行。151进入临界区的准则：进入临界区的准则：每次至多有一个进程处于临界区当有若干个进程欲进入临界区时，应在有限的时间内使其进入（有限等待）进程在临界区内仅逗留有限的时间4.5.1锁和上锁、开锁操作解决进程互斥的最简单的办法是加锁。什么是锁：用变量w代表某种资源的状态，w称为“锁”。锁位值：为“0”表示资源可用为"1"表示资源已被占用（不可用）

在系统中为每个临界资源设置一个锁位4.5.1锁和上锁、开锁操作当一个进程使用某个临界资源之前必须完成下列操作：1、考察锁位的值(是0还是1)；2、若原来的值是为“0”，将锁位置为“1”，此为上锁操作（表示准备占用该资源）；3、若原来的值是为“1”，（该资源已被别人占用），则不改变原来的值，循环检测等待。4、当某进程使用完资源后，将锁位置为“0”

，称为开锁操作，此时别的等待进程一旦检测到w的不为1了，则表示可以使用临界资源了。4.5.1锁和上锁、开锁操作说明在上述简单的上锁原语中，goto语句使得lock(w)原语的进程占用处理机而等待进入互斥段（称为忙等待busywaiting)测试法，浪费CPU时间。为此，可将上述上锁原语和开锁原语做进一步修改。修改后的原语如下所示：改进的lock和unlock算法经过锁处理，任何时候都不可能有两个及以上的进程进入临界区。

4.6.1用上锁原语和开锁原语实现互斥假设有两个进程共享打印机，两个进程中使用打印机的程序段为临界区。为保证打印的正确，设置打印机的锁print，其初值为“0”，表示打印机可用。4.6.1用上锁原语和开锁原语实现互斥4.5.2信号灯的概念前面介绍的方法虽能保证互斥，可以正确解决临界区问题，但有明显缺点：对不能进入临界区的进程，采用忙式等待(busywaiting)测试法，浪费CPU时间。将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程的负担。4.5.2信号灯的概念1965年荷兰的计算机科学家Dijkstra提出了新的同步工具——信号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过信号量(Semaphore)展开交互。进程在某一特殊点上停止执行直到得到一个对应的信号量，通过信号量这一设施，任何复杂的进程交互要求都可以得到满足，这种特殊的变量就是信号量。4.5.2信号灯的概念信号量只能由同步原语对其进行操作（原语是操作系统中执行时不可中断的过程、即原子操作）。Dijkstra发明了两个同步原语：P操作和V操作（荷兰语中“测试(Proberen)”

和“增量(Verhogen)”

的头字母。）利用信号量和P、V操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题。信号灯的分类信号量按其用途可分为两种：公用信号量：联系一组并发进程，相关的进程均可在此信号量上执行P和V操作。初值常常为1，用于实现进程互斥。私有信号量：联系一组并发进程，仅允许此信号量拥有的进程执行P操作，而其他相关进程可在其上施行V操作。初值常常为0或正整数，用于并发进程同步。信号灯的分类信号量按其取值可分为两种：二元信号量：仅允许取值为0和1，主要用于解决进程互斥问题（非我即你，通常用一个布尔量来表示）。一般信号量：允许取值为非负整数，主要用于解决进程间的同步问题。4.5.2信号灯的概念信号灯的定义：信号灯是一个确定的二元组（s,q），s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。

S代表资源的实体。在实际应用中应准确地说明s的意义和初值，每个信号灯都有一个队列，其初始状态为空。4.5.2P、V操作信号灯的值只能由P、V操作来改变。对信号灯的P操作记为：P(S)，P操作是一个原子操作。对信号灯的V操作记为：V(S),V操作是一个原子操作。信号量值的物理意义信号灯是整型变量。变量值≥0时，表示绿灯，进程执行。变量值<0时，表示红灯，进程停止执行。4.5.2P、V操作P操作：s值减1；若相减结果大于等于0，则进程继续执行；若结果小于0，则该进程挂起。注：推起该进程包括：保留调用进程CPU现场；置“等待”状态；入等待队列；转进程调度；消耗掉一个资源4.5.2P、V操作V操作：s值加1；若相加结果大于0，进程继续执行；否则，唤醒一个（或多个）等待该信号灯的进程。回收一个资源用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)4.6.2用信号灯实现进程互斥例子：两个进程共享打印机。设信号灯print表示打印机，初值为1，表示打印机可用(也可理解为有一台打印机)。说明：print是用于互斥的信号灯，教材上设置为mutex，设置成何种符号无所谓，只要可读性好即可。4.6.2用信号灯实现进程互斥信号量的物理意义S>0：其数值代表可用的资源数量S=0：代表无资源可用，但也没有等待的进程，即也没有申请资源的进程S<0：其|S|表示等待队列中想申请资源而还没有成功的进程数量用信号灯实现进程互斥的例子设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。试用信号灯的P、V操作实现这两个进程的互斥。设：mutex为互斥信号灯，初值为1（通过pv操作，可以解决与时间有关的错误）五个哲学家就餐问题下面再来看一下使用互斥信号量和PV操作解决操作系统经典的五个哲学家就餐问题。有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。五个哲学家就餐-动画演示179五个哲学家就餐问题在这道题目中，每一把叉子都是必须互斥使用的，因此应为每把叉子（临界资源）设置一个互斥信号量Si，初值均为1。#typedefintsemaphere;semaphorechopstick[5];for(inti=0;i<=4;i++)chopstick[i]=1;//因为均为互斥信号量，故初始化为1五个哲学家就餐问题当一个哲学家吃通心面前必须获得自己左边和右边的两把叉子，即执行两个P操作，吃完通心面后必须放下叉子，即执行两个V操作。程序如下：cobeginprocessPi//i=0,1,2,3,4begin

L1:

思考…；饥饿…；P(chopstick[i])；//拿左叉子P(chopstick[(i+1)mod5]);//拿右叉子

吃通心面…；

V(chopstick[i]);//放下左叉子V(chopstick[(i+1)mod5]);//放下右叉子

gotoL1;end;coend;思考：这样做能保证每个哲学家都能吃到面吗？五个哲学家就餐问题分析请大家注意，如果五个哲学家同时变得饥饿的话，且同时拿起他左边的叉子。这样所有的chopstick都变成0。就有可能出现每个哲学家举起左边的一把叉子，却又在永远等待相邻哲学家手中的叉子的情况——哲学家就都会饿死。死锁现象-永远等待五个哲学家就餐问题分析思考：如果增加一条指令：吃不到就放下自己手中的叉子，这样哲学家就不会饿死吗？这样同样会导致哲学家会饿死，因为可能在上面的情况下，五个哲学家因为自己吃不到东西，同时放下叉子，因为大家还饿着呢，环顾一看左右都有叉子，可能又同时拿起叉子，就这样，同时拿起，同时放下…循环往复。哲学家们不饿死，也得累死。这就是——死锁情况。并发进程临界区的管理原则计算机专家Dijkstra在1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足：空闲让进：当无进程在临界区时，任何有权使用临界区的进程都可进入忙则等待：不允许两个以上的进程同时进入临界区有限等待：任何进入临界区的要求在有限时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权同步的例子引例1：两位同学约好星期天去东湖，早上8:00在校门口，不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一道打的去东湖。同步的例子——病员就诊187同步的概念互斥的概念来自于多个进程对独占使用资源（设备）的竞争，同步来源于多个进程的合作。在人类社会中竞争与合作是永恒的。同步的定义：所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。4.6.3用信号灯实现进程的同步在操作系统中，同步有各种各样，但归纳起来有两类：诸进程合作完成某工作的逻辑顺序：如看病拿药问题对系统资源的共享：如两个进程共享一个（或多个）打印机，一个（或多个）变量4.6.3用信号灯实现进程的同步用信号灯及P、V操作来描述左图1、说明进程的同步关系进程P1、P2可并发执行，P3的执行必须等待P1、P2都完成后才能开始执行。2、设置信号灯，说明含义、初值初值s13=0表示进程P1尚未执行完成；初值s23=0表示进程P2尚未执行完成；4.6.3用信号灯实现进程的同步P、V操作实现合作进程的同步练习：设pa、pb、pc为一组合作进程，其进程流图如右图所示，试用信号灯的p、v操作实现这三个进程的同步。解答(1)三个进程的同步关系：pa先执行，当它结束后pb、pc可以开始执行。(2)信号灯设置：设两个同步信号灯sb、sc分别表示进程pb和pc能否开始执行，其初值均为0。解答共享缓冲区的合作进程的同步例：计算进程cp和打印进程iop公用一个单缓冲（buffer大小为1个字节），为了完成正确的计算与打印，试用信号灯的p、v操作实现这两个进程的同步。4.6.3用信号灯实现进程的同步分析：CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。4.6.3用信号灯实现进程的同步要保证打印结果的正确，CP、IOP必须遵循以下同步规则，两个进程的同步关系如下：当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待；当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。1974.6.3用信号灯实现进程的同步解决这个问题的步骤：分析问题，弄清楚同步关系，如上分析；设置信号灯，说明含义、初值；写出程序描述。198用信号灯实现进程的同步信号灯设置：设置两个信号灯sa和sb。信号灯sa--表示缓冲区中是否有可供打印的计算结果，其初值为0。信号灯sb--表示缓冲区有无空位置存放新的信息，其初值为1。用信号灯实现进程的同步信号量的小结信号量值的小结（回顾）：S>0：其数值代表可用的资源数量S=0：代表无资源可用，但也没有等待的进程，即也没有申请资源的进程S<0：其|S|表示等待队列中想申请资源而还没有成功的进程数量信号量的小结P和V的位置放置的小结：对于互斥资源：P、V操作在同一个进程中。对于共享资源的同步：P、V操作在不同进程中（强调的是你中有我，我中有你的协作关系）P和V信号量的初始化：必须置一次初值，且只能置一次初值初值必须>=0，不能为负值4.6.4多缓冲的生产者－消费者问题

问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。即满足如下条件：（1）消费者想接收数据时，有界缓冲区中至少有一个单元是满的。（2）生产者想发送数据时，有界缓冲区中至少有一个单元是空的。动画：生产者和消费者生产者－消费者的例子例1：计算进程和打印进程：计算进程cp不断产生数据，是生产者；打印进程iop不断打印数据，是消费者。例2：通信问题：发消息进程send不断产生消息，是生产者；收消息进程receive不断接收消息，是消费者。

生产者--消费者问题图示生产者与消费者生产者：当有界缓冲区中无空位置时，要等待；向有界缓冲区放入物品后，要发消息。消费者：当有界缓冲区中无物品时，要等待；从有界缓冲区取出物品后，要发消息。多缓冲区的P-C问题之间的关系一、同步关系：对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待；对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。多缓冲区的P-C问题之间的关系二、互斥关系缓冲区是临界资源，在多个进程在生产产品时，它不允许在缓冲区的某一个单元同时存放产品；也不允许多个进程同时消费缓冲区的某一个单元产品，因此，还有个互斥的问题。多生产者-消费者问题的一般解答信号灯设置：两个同步信号灯：empty：表示空缓冲区的数目，初值为有界缓冲区的大小nfull：表示满缓冲区的数目，其初值为0一个互斥信号灯：mutex：互斥信号灯，初值为1同步描述程序描述程序描述动画演示214思考与说明如果我们把消费者进程中的两个P操作交换次序，即那么会有什么问题吗？参见下图的程序参考：主程序216并发程序思考与说明在这个问题中P操作的次序是很重要的，如果我们把消费者进程中的两个P操作交换次序，那么就会产生与时间有关的错误。分析如下：分析说明在某个时刻，消费者消费的比较快，把所有的产品消费完，有：empty=n，mutex=1，full=0接着消费者进程运行到1处，使得mutex=0，运行到2处full=-1<0，消费者进程等待接着，生产者进程运行到3处，由于生产了一个产品，故空位置-1，empty=n-1，运行到4处，由于p(mutex)操作，mutex=mutex-1=-1<0，生产者进程也等待。故而，这两个程序陷于相互等待的死锁状态。思考思考与延伸：交换生产者的两个p操作会不会带来与时间有关的错误呢？如果会，在什么情况下会？请分析之。程序见下图：思考与说明思考与结论所以，在使用PV操作实现进程同步时，特别要当心P操作的次序，而V操作的次序倒是无关紧要的。一般来说，用于互斥的信号量上的P操作，总是在用于协作的P操作之后执行。即，同步的P操作在互斥的P操作之前。P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要，同步P操作在互斥P操作前而两个V操作的顺序无关紧要信号量及P、V操作总结P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全：P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂信号量及P、V操作总结一道考研题苹果桔子问题：桌上有一只盘子，最多可以容纳两个水果，每次只能放入/取出一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子里的苹果。请用PV操作来实现爸爸、妈妈、儿子、女儿之间的同步和互斥。（南京大学2000年）分析这个问题实际上是两个生产者和两个消费者被连接到仅能放两个产品的缓冲区上。生产者各自生产不同的产品，但就其本质而言，他们是同一类生产者。而消费者则各自取需要的产品消费，他们的消费方式不同。程序如下：main(){tpyedefintsemaphore;semaphoreempty；/*盘子里可以放几个水果*/semaphoreorange;/*盘子里有桔子*/semaphoreapple;/*盘子里有苹果*/semaphoremutex;/*不能同时对盘子操作的互斥量

empty

=2;/*盘子里最多放两个水果*/

orange

=0;/*盘子里没有桔子*/

apple

=0;/*盘子里没有苹果*/mutex=1cobegin/*可并发的进程*/father();mother();son();daugher();

coend}father(){while(手中还有苹果){

P(empty);P(mutex)；

向盘中放苹果…；

V(mutex)；

V(apple);}}

mother(){while(手中还有桔子){

P(empty);P(mutex)；

向盘中放桔子…；

V(mutex)；

V(orange);}}

soni()//i=1，2{while(盘中还有苹果){

P(apple);P(mutex)；

从盘中拿苹果…；

V(mutex)；

V(empty);}}

daugheri()//i=1，2{while(盘中还有桔子){

P(orange);P(mutex)；

从盘中拿桔子…；

V(mutex)；

V(empty);}}

回顾：哲学家就餐问题问题描述：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子哲学家就餐问题解法#defineN5voidphilosopher(inti){while(true){

思考；

P(fork[i]);P(fork[(i+1)%5])；进食；

V(fork[i]);V(fork[(i+1)%5])；

}}为防止死锁发生可采取的措施：最多允许4个哲学家同时去拿右/左边的筷子（解1）给所有哲学家编号，奇数号的哲学家必须首先拿右边的筷子，偶数号的哲学家则反之（解2）仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子-全部分配回顾：哲学家就餐问题最多允许4个哲学家同时去拿右边的筷子设fork[5]为5个互斥信号量，初值均为1设信号量S，初值为4，S用于封锁第5个哲学家无死锁哲学家就餐问题---解1234Philosopheri：{

思考；

P(S);//S的值减1P(fork[i]);P(fork[(i+1)mod5])；吃饭；

V(fork[i]);V(fork[(i+1)mod5])；

V(S);}给所有哲学家编号，奇数号的哲学家必须首先拿右边的筷子，偶数号的哲学家则反之。235无死锁哲学家就餐问题---解2Philosopher1：{

思考；

P(fork[1]);//右边的筷子P(fork[2]);//左边的筷子吃饭；

V(fork[2]);V(fork[1])；}Philosopher2：{

思考；

P(fork[3]);P(fork[2])；吃饭；

V(fork[2]);V(fork[3])；}经典问题读者写者问题问题描述：有两组并发进程:读者和写者,共享数据区要求：

允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作动画-读者与写者读者-写者问题分析如果读者来：1）无读者、写者，新读者可以读2）有写者等，但同时有其它读者正在读，则新读者也可以读（多个读者可同时读数据）3）有写者正在写，新读者等（读者和写者不能同时操作）如果写者来：1）无读者，新写者可以写2）有读者正在读，新写者等待（读者和写者不能同时操作）3）有其它写者正在写，新写者等待（多个写者不能同时写数据）信号量w用于读者和写者、写者和写者之间的互斥（互斥信号量），即用来控制由谁使用共享数据区；变量readcount表示正在读的读者数目，它是一个临界资源（因为多个读者进程都可以访问readcount变量，而每次只能允许一个读者进程使用这个变量，所以readcount变量是一个临界资源）；信号量mutex用于对readcount这个临界资源的互斥访问；所以，有两个互斥信号量，初值w=1，mutex=1。读者-写者问题分析因为只要有一个读者在读，便不允许写者去写。所以：从第1个读者进入共享数据区开始，就不允许写者去写，即当readcount+1后其值为1时，读者进程执行p(w)，表示对共享数据区实行保护，不允许写者去写；当最后1个读者退出共享数据区之后，也就是当共享数据区中没有读者时，就可以让写者进来写，即当readcount-1后其值为0时,读者进程执行v(w)，让出对共享数据区的使用权。读者-写者问题分析读者：

read{P(mutex);readcount++;if(readcount==1)P(w);//禁止写V(mutex);

读

P(mutex);readcount--;if(readcount==0)V(w);//可以允许写V(mutex);};写者：

write{P(w);

写

V(w);};//写者在写数据的时候不允许其他写者写，也不允许其他读者读。读者-写者问题的解法动画演示!//初始化mut