操作系统第四章并发处理

1、第四章 并发处理4.1并发活动进程的引入 假设某个作业job由输入I，计算C，打印P三个操作组成。1. 单道批处理系统中，作业序列的处理过程如下：C1I1I2P2P1C2tjob1job2为了提高资源利用率和系统吞吐量，引入多道批处理系统。2、多道批处理系统中，作业序列的处理过程如下：I1C1P1I2C3P2I3C2P3t从图中可以看出：有的程序段的执行是有先后次序的，如C1，I2先于C2；有的程序段可以并发执行，如P1，C2，I3； 可以用伪代码描述并发执行的程序段，由Dijkstra提出，Cobegin（Concomitant begin） S1;S2; ;Sn;Coend表示S1，S2，

2、Sn可以并发执行。例如：S0;Cobegin S1;S2; ;Sn;CoendSn+1; 表示先执行S0，再并发执行S1，S2，Sn；当S1，S2，Sn全部执行完毕后，再执行Sn+1。S0S1S2SnSn+1也可以用先后次序图（以后也称进程流图）表示，它是一个有向无环图。4.1.5并发执行程序的特点1.间断性 如果Ci-1完成后，若Ii未完成，则Ci也无法处理，导致计算程序段暂停。2.失去程序的封闭性 程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去封闭性。3.不可再现性 当初始条件相同时，程序多次执行，其结果必然重复出现，称为可再现性

3、。例如：有一公共变量x，r1，r2为2个寄存器。假设CPU分时执行p1,p2。有两个程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式一执行：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;结果：x=x+2例如：有一公共变量x，r1，r2为2个寄存器。假设CPU分时执行p1,p2。 有两个程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式二执行：P1:r1=x;P2:r2=x; r2+; x=r2; P1:r1+; x=r1;结果：x=x+1 可见，并发执行的程序可能发生不可再现性。 为了描

4、述并发执行程序的活动规律因而引进新的概念进程。4.2进程的概念 进程20世纪60年代初期提出，可翻译为process，task，action等。 定义1：进程时一个具有独立功能的程序关于某个数据集合的一次运行活动。 定义2：从核心看来，进程是分了类的，根据一组规则操纵的数据结构。进程与程序的关系：1. 进程与程序的联系 进程=程序（程序段、数据段、栈段）+进程控制块（PCB） 程序是构成进程的组成部分之一，一个进程存在的目的就是执行其所对应的程序。进程和程序的区别 程序是静止的，进程是动态的（有生命周期的） 进程是能独立运行的单位，能与其它进程并发执行。 进程是资源分配的基本单位，也是CPU调

5、度的基本单位。4.2.2进程的类型1.系统进程 它们运行OS的程序，也称守护进程（Daemon进程）。系统启动时创建，运行时CPU处于核心态。2.用户进程 这类进程运行用户程序，直接为用户 服务。进程的特征：进程的特征： 并发性：可以与其它进程在宏观上同时先前推进。 动态性：进程是执行中的程序。 独立性：进行是资源分配和调度的基本单位。 交互性：进程在运行时可能会与其它进程发生直接或间接的相互作业。 异步性：每个进程都可以相对独立，不可预知的速度向前推进。 结构性：每个进程都对应1个进程控制块。4.2.3进程的状态进程的基本状态 就绪状态（Ready）：获得了除CPU以外的所有资源，一旦获得C

6、PU控制权，就可以立即运行。 运行状态（Running）：当就绪进程由OS的进程调度程序调度，得到CPU控制权，占用CPU运行的状态。 等待状态（Wait）：若某一进程正在等待某一事件的发生而暂时停止，这时，即使获得CPU控制权也无法执行。或阻塞状态（Block）、睡眠状态（Sleep）。二、进程状态变迁图1、进程的三态模型：运行等待就绪 时间片到 被抢占进程调度 I/O请求 中断请求服务等I/O请求完成等进程队列模型：CPU创建就绪队列OS调度时间片用完等待事件1等待事件2等待事件n 事件1发生事件n发生事件2发生 因等待的原因不同可以分为若干个等待队列，这样发现和唤醒等待的进程较为方便。二

7、、进程状态变迁图2、进程的五态模型：运行等待就绪 时间片到 被抢占进程调度 I/O请求 中断请求服务等I/O请求完成等终止创建结束接纳创建态(Create)：进程刚刚建立（如建立PCB），完成初始化，但未分配内存等资源。终止态(Terminated)：正常结束或异常结束。13.在进程基本状态转换图中，增加换出（将进程换出至辅存）和换入（将进程从辅存换入至主存）两个操作，试画出进程状态转换图。二、进程状态变迁图3、UNIX系统进程状态变迁图（p106）4.2.4进程的描述进程控制块（Process Contral Block） 进程的活动除包括CPU执行的程序及对相关数据的操作，还需要用一个数据

8、结构来刻画进程的动态特征，描述进程的状态、占用资源、调度信息等，这个数据结构即PCB。 每个进程包括4个要素：程序段、数据段、栈段、进程控制块（PCB）。进程的组成：指针指针1指针2指针3其它信息程序段数据段堆栈段进程控制块PCB进程控制块PCB的其它信息包括一下主要内容： 进程标识符（Pid）：由OS创建进程时给出，要求唯一 进程的状态（Status） :作为进程调度时分配处理机的主要依据。为了便于对进程实施管理，通常把具有相同状态的进程链接在一起，组成各种队列。如就绪队列、各种等待队进程控制块PCB的其它信息包括一下主要内容：当前队列指针（next）：指向相同状态的下一个PCB 。next

9、nextnextnextnextnextnextRun-startReady-q-startWait-pt-startPCBiPCB2PCB1PCBn进程控制块PCB的其它信息包括一下主要内容：总链指针（all_q_next）：就系统中所有进程的PCB勾链起来。nextAll-q-nextnextAll-q-nextnextAll-q-nextnextAll-q-nextNext=All-q-nextnextAll-q-nextNext=All-q-nextRun-startReady-q-startWait-pt-startPCBiPCB2PCB1PCBnAll-start进程控制块PCB的

10、其它信息包括一下主要内容：程序开始地址（start_addr）：表示进程的程序从此开始执行。进程优先级（priority）：CPU现场保护区（cpu_status）:进程控制块PCB的其它信息包括一下主要内容：通信信息（communication information）:如：记录消息缓冲队列指针htprhptrPCB消息缓冲区1消息缓冲区2 消息缓冲区n进程控制块PCB的其它信息包括一下主要内容：家族信息（process_family）：如父进程的标识符ppid占有资源清单（own_resource）P103 unix系统的进程控制块4.3进程控制 进程控制是对系统中的全部进程实施有效的管理

11、。这些管理功能是由一些具有特定功能的程序段原语实现的。原语是一种特殊的系统调用命令，它可以完成一个特定的功能，其特定是执行时不可中断。 思考：如何实现原语执行时不可中断？ 执行原语之前关中断，执行完之后开中断。进程控制原语有：创建原语、撤销原语、阻塞原语、唤醒原语、延迟原语。执行终止就绪等待延迟创建创建原语撤销原语阻塞原语唤醒原语延迟原语4.3.2进程创建进程的创建可来源以下事件：1. 用户向系统提交作业或程序；2. OS创建服务进程3. 已存在的进程创建新的进程，如父进程创建子进程。一般来说进程的创建过程如下： 申请一个空闲的PCB； 初始化PCB，如进程号，优先级，状态等 为新的进程分配资

12、源，如内存等 将新进程插入就绪队列。4.3.3进程的撤销引起进程终止的事件： 正常结束，如程序执行完毕 异常结束，如溢出 外界干预，如程序执行时用户ctrl+break算法： 由运行指针得到当前进程的pid; 释放本进程所占用的资源给父进程； 该进程从总链队列中摘除； 释放此pcb结构； 转OS进程调度；4.3.4进程阻塞（block,supend,wait）引起进程阻塞的事件 请求OS服务 请求中断处理 新的数据还未到达 无新工作可做算法：wait(chan)Chan进程等待的原因 p104 int p_wchan 保护当前进程的CPU现场到PCB结构中；置该进程为“等待”状态；将该进程的P

13、CB插入到等待chan的等待队列；转OS进程调度； 4.3.4进程唤醒 当进程等待的事件发生后，唤醒等待该事件的所有进程。Wakeup（chan）找到该阻塞原因chan的队列指针；For（等待该事件的进程）将进程移出此等待队列；置进程状态为“就绪”；将进程插入“就绪队列”； 可以看出：当前进程执行Wakeup（chan）原语之后继续执行。4.3.6进程延迟 将需要延迟的进程的PCB按其延迟时间加入到延迟队列的适当位置。 Delay(seconds) Seconds:需延迟的秒数 Clock_ticks=secondsclock_rate /需延迟的机内时间 Clock_rate:为时钟速率，即

14、时钟中断信号/秒（如50次/秒）算法：保护调用延迟原语的进程的CPU现场；计算clock_ticks;封锁延迟队列；以clock_ticks值检索延迟队列并插入合适位置；置该进程为延迟状态；解锁延迟队列；转OS进程调度；注意:延迟队列是临界资源，使用之前需上锁，使用完毕要解锁。延迟队列的结构：PCB中有deltatime项，其值为进程所需延迟的clock_ticks与延迟队列中的前一个进程的clock_ticks数之差。例如：有进程A,B,C的clock_ticks分别为2，5，10，则延迟队列为：Pid=AnextDeltatime=2Pid=BnextDeltatime=3Pid=CNex

15、t=Deltatime=5Delay-q-start假设进程假设进程D的的clock_ticks=8，则应该插入延迟队列的什么则应该插入延迟队列的什么位置呢？位置呢？插入延迟队列过程如下：Deltatimenew=clock_ticksD;i=1;Time= Deltatimenew deltatimeiIf time0 则 Deltatimenew=time； i+；goto If time0 则插入相比较进程的前面，该进程的deltatime=deltatimenew; 后一个进程的deltatime= time;思考：画出插入进程D后的延迟队列？插入进程D后的延迟队列:Pid=Anext

16、Deltatime=2Pid=BnextDeltatime=3Pid=CNext=Deltatime=2Delay-q-startPid=DnextDeltatime=3分析这样处理延迟队列有什么好处？二、延迟唤醒进程它是一个系统进程，系统初始化时被创建，由时钟中断激活，直到系统关闭。当时钟中断信号到来时执行以下算法：封锁延迟队列；取延迟队列的首元素；将deltatime- -;If (deltatime=0) 则从延迟队列取下该进程PCB；解锁延迟队列；该进程PCB插入就绪队列；中断返回； 实验二4.4进程的相互制约关系1.竞争关系原本不存在逻辑关系的诸进程因共享资源而产生的制约关系，又称互

17、斥关系。如学生在图书馆占座位2.协作关系一组并发进程，为了完成任务需要分工协作。这种协作进程之间需要排定执行的先后次序。也称同步关系。如：一个作业分为输入I、计算C、输出P三个过程段。进程之间充足哪几种相互制约关系？各时由什么原因引起的？下列活动分别属于哪种制约关系？（1）若干同学交纳学费（2）两队举行篮球比赛（3）A考试炒B的答案（4）4个同学参加4100米接力解：因竞争资源产生的互斥；相互等待、相互制约的同步；（1）互斥（2）互斥（3）同步（4）同步 进程互斥（Mutual exclusion）:是指若干进程因相互争夺独占型资源而产生的竞争制约关系。 进程同步（Synchronizatio

18、n）：并发进程在一些关键点上可能需要互相等待或互通消息，这种制约关系称为同步。 如何实现进程间的互斥、同步？4.4.2进程互斥临界资源：一次仅允许1个进程使用的资源。（独占型资源）如：打印机，公共的变量、链表、数据结构等临界区（critical section）:每个进程中访问临界资源的那段代码，又称临界段。 对临界资源必须互斥使用，否则会发生错误，例如：例如：有一公共变量x，r1，r2为2个寄存器。假设CPU分时执行p1,p2。 有两个程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式一执行：P1:r1=x; r1+; x=r1;P2:r2=x; r2+

19、; x=r2;结果：x=x+2公共变量X是临界资源CS0CS1例如：有一公共变量x，r1，r2为2个寄存器。假设CPU分时执行p1,p2。 有两个程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式二执行：P1:r1=x;P2:r2=x; r2+; x=r2; P1:r1+; x=r1;结果：x=x+1公共变量X是临界资源CS0CS1可见，对临界资源的使用必须互斥，否则结果可能会产生错误。互斥应遵循的原则：1. 空闲让进：临界资源处于空闲状态时，应允许1个请求进入临界区的进程立即进入自己的临界区。2. 忙则等待：当已有进程进入自己的临界区时，其它所有试图进入

20、临界区的进程必须等待。3. 有限等待：要求访问临界资源的进程，应保证能在有限的时间内进入自己的临界区。4. 让权等待：当进程不能进入自己的临界区时，应立即释放CPU，以免进程陷入“忙等待”。 例如：演讲时的话筒。 互斥是同步的特例4.5同步机构 实现互斥方法之一锁 对每个临界资源设置一个锁位W（1bit）按惯例，w=0，表示资源可用；w=1，表示资源已被占用 这样，当进程使用临界资源之前必须完成上锁操作，即w置1；当进程使用完临界资源后，须开锁操作，即w置0，为此，系统提供了lock(w)和unlock(w)2个原语。算法一Lock(w)test:if (w=1) goto test; Els

21、e W=1;Unlock(w)w=0;改进算法二Lock(w)while (w=1) 保护当前进程的现场至进程的PCB; 将当前进程的PCB插入w的等待队列； 置该进程为“等待”状态； 转OS的进程调度； W=1;Unlock(w)if (w的等待队列不空) 移出等待队列的首元素； 将该进程插入就绪队列； 置该进程为“就绪”状态； W=0;4.5.2信号灯（信号量semaphore）和P、V操作1965年，dijkstra提出的信号量机制是一种有效的同步工具。信号量struct semaphore int s; /s初值0，其值只 能由P、V操 作改变 Queue q; /q是初始状态为空 的

22、 排队站 P(s)s- -; If (s0)保留当前进程的现场； 将该进程插入s的等待队列q中；置该进程为“等待”状态；转OS的进程调度程序；理解为：申请一个资源，如果申请不到就进入等待状态。思考：当进程执行p(s)后，对当前进程的状态有何影响？s0时，没有影响；s0时，当前进程由运行状态变为等待状态。V(s)s+; If (s0) 移出s等待队列q的首元素； 将该进程插入就绪队列； 置该进程为“就绪”状态； 理解为：释放一个资源，如果有进程因申请不到该资源而等待的话，就唤醒1个等待的进程。 思考：当进程执行v(s)后，对当前进程的状态有何影响？ 答：没有影响。4.6.2使用信号量实现进程互斥

23、 设置一个互斥信号量mutex，只要把进入临界区的操作置于p(mutex)和v(mutex)之间，即可实现进程互斥。Main()semaphore mutex=1;CobeginPa();pb();CoendPa( )P(mutex);Csa;V(mutex);Pb( ) P(mutex);Csb;V(mutex);有2个并发进程，若mutex=1,表示没有进程进入临界区；Mutex=0,表示有1个进程进入临界区；Mutex=-1,表示有1个进程进入临界区，另1个进程等待进入。思考：对于n个并发进程，分析mutex的取值范围以及每个值的物理 意义。对于n个并发进程，mutex的值可为1,0，-

24、1，-（n-1），当mutex0时， mutex 的值为等待进入临界区的进程数。例：以下算法用于解决两个临界区的问题。两个进程P0，P1共享如下变量，Boolean:flag0 . .1=false,false;Int turn; /turn的初值为0或1P0( ) Flag0:=true; While turn0 do Begin While flag0; Turn:=0; End; Cs0; Flag1:=falseP1( ) Flag1:=true; While turn1 do Begin While flag0; Turn:=1; End; Cs1; Flag0:=false分析：t

25、urn=0,p0进入临界区；turn=1,p1进入临界区。4.6进程互斥与同步的实现4.6.3进程同步的实现进程同步:并发进程在一些关键点上可能需要互相等待与互通消息，这种互相等待与互通消息称为进程同步。同步问题可以分为二类：一一组合作进程按逻辑需要所确定的次序执行。例如看病的流程：挂号、问诊、化验、处方二共享缓冲区（或共享数据）的合作进程同步。例如：计算进程把计算结果buf打印进程取出结果打印。一合作进程的执行次序用1个图表示进程集合的执行时间轨迹，图的连接描述了进程的开始和结束的次序约束，此图称为进程流图或先后次序图。sssfffP1P2P3顺序P1P2P3P1P2P3并行顺序/并行SfP

26、aPbPc例1：用P、V操作描述进程流图中这3个进程的同步。方法一：Semaphore Sb=0; /表示Pb是否可以开始 Sc=0; /表示Pc是否可以开始Main()cobegin Pa();Pb();Pc(); coend Pa() V(Sb); V(Sc);Pb() P(Sb); Pc() P(Sc); SfPaPbPc例1：用P、V操作描述进程流图中这3个进程的同步。方法二：Semaphore Sa=0; /表示Pa是否结束Main()cobegin Pa();Pb();Pc(); coend Pa() V(Sa); V(Sa);Pb() P(Sa); Pc() P(Sa); Sf例

27、2：用P、V操作描述进程流图中进程的同步。方法一：Semaphore S7=0; /依次表示Pi是否结束,i=0.7Main()cobegin P1();P2();P3();P4();P5();P6();P7();P8(); coend P1() V(s1); V(s1); V(s1);P1P2P3P4P5P6P7P8P2() V(s2); V(s2); V(s2);P3()P(s1); P(s2); V(s3);P4()P(s1); P(s2); V(s4);P5()P(s1); P(s2); V(s5);P6()P(s3); V(s6);P7()P(s5); V(s7);P8()P(s4)

28、; P(s6); P(s7);例3：人走路时的同步问题，假定先左腿，后右腿。问题一：能否设置1个信号量解决？Semaphore s=0; /表示右腿是否可以移动Main()cobegin L_leg();R_leg();CoendL_leg()while(1) 左腿向前； 右手前摆； 左手后摆； V(s); R_leg()while(1) p(s); 右腿向前； 左手前摆； 右手后摆； 可能存在左腿不停向前移动的情况。例3：人走路时的同步问题，假定先左腿，后右腿。改进方法二Semaphore SL=1; /表示左腿能否向前 SR=0;/表示右腿能否向前Main()cobegin L_leg()

29、;R_leg();CoendL_leg()while(1) p(SL)； 左腿向前； 右手前摆； 左手后摆； V(SR); R_leg()while(1) p(SR); 右腿向前； 左手前摆； 右手后摆； V(SL); 思考：Semaphore SL=0; /表示左腿能否向前 SR=0;/表示右腿能否向前算法如何修改？L_leg()while(1) 左腿向前； 右手前摆； 左手后摆； V(SR); P(SL); R_leg()while(1) p(SR); 右腿向前； 左手前摆； 右手后摆； V(SL); 二、共享缓冲区的合作进程的同步cpiop单缓冲区进程cp负责计算，并把计算结果送入缓冲区

30、；打印进程iop负责从缓冲区中取出数据，并打印；同步规则：单缓冲区空，iop进程等待； 单缓冲区满，cp进程等待；Semaphore Sa=0;/表示单缓冲区是否有数据 Sb=1;/表示单缓冲区是否空Main()cobegin cp();iop();CoendCp()while(计算未完成) 计算； P(sb); 计算结果送入单缓冲区； V(sa); 方法一Iop()while(打印未完成) p(sa); 从单缓冲区取出数据； V(sb); 打印数据； 方法二Iop()while(打印未完成) p(sa); 从单缓冲区取出数据； 打印数据； V(sb); 方法二，cp()与iop()不能并发。

31、4.6.4生产者消费者问题（ProducerConsumer）123n 有界缓冲区p1pmC1Ck同步规则：缓冲区空，消费者进程等待； 缓冲区满，生产者进程等待；设置2个同步信号量 1个互斥信号量Semaphore Full=0;/表示缓冲区中产品的数目 Empty=n;/表示空缓冲区的数目 Mutex=1;/互斥访问有界缓冲区产品产品Main（）cobegin P1();pm(); C1();ck();CoendPi()while(1) 生产一个产品； P(empty); P(mutex); 产品送入缓冲区； V(mutex); V(full); Cj()while(1) P(full);

32、P(mutex); 从缓冲区中取出产品； V(mutex); V(full); 消费1个产品； Main（）cobegin P1();pm(); C1();ck();Coend思考：2个p操作能否互换位置？Pi()while(1) 生产一个产品； P(mutex); P(empty); 产品送入缓冲区； V(mutex); V(full); Cj()while(1) P(full); P(mutex); 从缓冲区中取出产品； V(mutex); V(full); 消费1个产品； 例：某展览馆可以同时容纳1000名参观者，假设入口和出口每次只能1人进出，试用P、V操作描述参观者进程的同步。Sem

33、aphore N=1000;/表示展览馆可以容纳的人数 M1=1;/互斥进入入口 M2=1;/互斥进入出口Pi()p(n);P(m1);从入口进入展览馆；V(m1);参观；P(m2);从出口离开展览馆；V(m2);V(n);Main（）cobegin P1();pn(); Coend习题课：1、桌子上有一个空盘子，允许存放一个水果。父亲可向盘中放苹果或橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘子空时，一次只能放一个水果，请用P、V操作实现父亲、儿子、女儿三个并发进程的同步。Semaphore disk=1;/表示盘子是否空 apple=0;/表示盘子中是否有苹果 orange=

34、0;/表示盘子中是否有橘子Main（）cobegin Father();son();daughter(); CoendFather()while(1) p(disk); 向盘子中放入一个水果；If (是苹果) v(apple);If (是橘子) v(orange);Son()while(1) p(orange); 从盘子中取走橘子； V(disk); 吃橘子； daughter()while(1) p(apple); 从盘子中取走苹果； V(disk); 吃苹果； 2、有一个阅览室共有100个座位，读者进入时必须在入口刷卡进入，读者离开时也必须在出口刷卡，请用P、V操作描述读者进程的同步。Se

35、maphore N=100;/表示阅览室可以容纳的人数 M1=1;/互斥入口刷卡机 M2=1;/互斥出口刷卡机Main（）cobegin P1();pn(); CoendPi()p(n);P(m1);从入口刷卡进入阅览室；V(m1);阅览；P(m2);从出口刷卡离开阅览室；V(m2);V(n);3、哲学家问题：有甲、乙、丙、丁四个哲学家进餐，每人进餐时都需要使用刀、叉各一把，吃完后放下刀叉思考问题，请用P、V操作描述这四个哲学家的同步。SemaphoreF1=1;/表示第一把刀是否可用F2=1;/表示第二把刀是否可用K1=1;/表示第一把叉是否可用K2=1;/表示第二把叉是否可用注意规则：按先

36、刀后叉，或先叉后刀的顺序。甲（） While（1） p(k1); P(f1); 进餐； V(k1); V(f1); 思考； 乙（） While（1） p(k2); P(f1); 进餐； V(k2); V(f1); 思考； 丙（） While（1） p(k2); P(f2); 进餐； V(k2); V(f2); 思考； 丁（） While（1） p(k1); P(f2); 进餐； V(k1); V(f2); 思考； 食物乙甲丙丁刀1叉1叉2刀23、哲学家问题：有甲、乙、丙、丁四个哲学家进餐，每人进餐时都需要使用刀、叉各一把，吃完后放下刀叉思考问题，请用P、V操作描述这四个哲学家的同步。Semap

37、horeF1=1;/表示第一把刀是否可用F2=1;/表示第二把刀是否可用K1=1;/表示第一把叉是否可用K2=1;/表示第二把叉是否可用注意规则：按先刀后叉，或先叉后刀的顺序。如果不注意会出现什么问题？甲（） While（1） p(k1); P(f1); 进餐； V(k1); V(f1); 思考； 乙（） While（1） p(f1); P(k2); 进餐； V(k2); V(f1); 思考； 丙（） While（1） p(k2); P(f2); 进餐； V(k2); V(f2); 思考； 丁（） While（1） p(f2); P(k1); 进餐； V(k1); V(f2); 思考； 食物乙

38、甲丙丁刀1叉1叉2刀24、中国的哲学家问题：n个哲学家围在桌子前进餐、思考，桌子一次放着n根筷子，用P、V操作描述这n个哲学家的活动，并保证哲学家不会饿死。食物123in in-1ni-1规则：进餐时左右竞争相邻的筷子。如奇数号的哲学家先拿左手边的筷子（i-1），后拿右手边的筷子（i）;如偶数号的哲学家先拿右手边的筷子（i），后拿右手边的筷子（i-1）;规则：进餐时左右竞争相邻的筷子。如奇数号的哲学家先拿左手边的筷子（i-1），后拿右手边的筷子（i）;如偶数号的哲学家先拿右手边的筷子（i），后拿右手边的筷子（i-1）;Semaphore sn=1;philosopheri ()while(1)

39、 if (I mod 2 = 0)/偶数号哲学家 p(si); p(si-1); 进餐； v(si); v(si-1)； 思考； Else/奇数号哲学家 If (i=1) p(sn) else p(si-1); p(si); 进餐； v(si); If (i=1) v(sn); else v(si-1); 思考； 4、过独木桥问题方法一：Semaphore bridgemutex=1; /互斥独木桥West_easti()p(bridgemutex); 从西向东过桥； V(bridgemutex);Eest_westj()p(bridgemutex); 从东向西过桥； V(bridgemute

40、x);问题：对向互斥，同向也互斥改进方法二：Semaphore bridgemutex=1; /互斥独木桥 M1=1; /互斥count1 M2=1; /互斥count2Int count1=0;/记录从西向东的过桥人数 Count2=0;/记录从东向西的过桥人数West_easti()p(m1); Count1+; If (count1=1) p(bridgemutex);/第一个人上桥时封锁对向上桥 V(m1);从西向东过桥；p(m1); Count1- -; If (count1=0) v(bridgemutex);/最后一个人下桥时解锁对向上桥 V(m1);Eest_westj()p(

41、m2); Count2+; If (count2=1) p(bridgemutex);/第一个人上桥时封锁对向上桥 V(m2);从东向西过桥；p(m2); Count2- -; If (count2=0) v(bridgemutex);/最后一个人下桥时解锁对向上桥 V(m2);5、读者写者问题：某数据库文件有若干读、写进程，它们之间读、写操作的要求是：读-写互斥，写-写互斥，读-读不互斥，请用信号量的P、V操作描述这一组进程的同步。Semaphore DBmutex=1;/数据库文件互斥信号量 M=1;/互斥访问count Int count=0;/记录读进程数Main()cobegin R

42、eader1(); ;readern(); Writer1();writern();CoendReaderi()p(m); Count+; If (count=1) p(DBmutex);/第一个读者读数据库时，阻止写 V(m);读数据库文件；p(m); Count- -; If (count=0) v(DBmutex);/最后一个读者读完数据库后，允许写 V(m);Writerj() p(DBmutex); 写数据库文件； v(DBmutex);6. 有一个仓库，可以存放A和B两种产品，但要求每次只能存入一种产品（A或B）；-NA产品的数量B产品的数量M用信号量的P、V操作描述产品的入库过程。分析：ABM，即（AB）maxM1，说明在当前库存量和B不入库时，允许A产品入库的最大数量，用信号量Sa表示，初值为M1;-NAB，即BAN，（BA）maxN1，说明在当前库存量和A不入库时，允许B产品入库的最大数量，用信号量Sb表示，初值为N1;SemaphoreMutex=1;/互斥信号量Sa=M1;Sb=N1;Main（）while（1） 取一个产品； If （是A产品）P(Sa); P(mutex) A产品入库； V(mutex); V(sb); Else P(Sb); P(mutex) B产品入库； V(mutex); V(sa); 14.在一个盒子里存放了