操作系统原理课件-(3)[123页].ppt

1、 第第3章章 进程同步与通信进程同步与通信 第第3章章 进程同步与通信进程同步与通信3.1 3.1 进程同步的基本概念进程同步的基本概念3.2 3.2 进程互斥方法进程互斥方法3.3 3.3 信号量机制信号量机制3.4 3.4 经典互斥与同步问题经典互斥与同步问题3.5 3.5 经典互斥与同步问题的应用经典互斥与同步问题的应用3.6 3.6 管程机制管程机制3.7 3.7 进程通信进程通信3.8 3.8 死锁死锁 3.1 进程同步的基本概念 3.1 进程同步的基本概念 3.1 进程同步的基本概念 3.1 进程同步的基本概念 3.1 进程同步的基本概念 3.1 进程同步的基本概念 例：下面活动中

2、，每个活动分属于同步与互斥关系的哪一例：下面活动中，每个活动分属于同步与互斥关系的哪一种，并说明其理由。种，并说明其理由。（1 1）若干同学去图书馆借书；）若干同学去图书馆借书；（2 2）两队举行篮球比赛；）两队举行篮球比赛；（3 3）流水线生产的各道工序；）流水线生产的各道工序；（4 4）商品生产和社会消费。）商品生产和社会消费。同步与互斥的比较 临界资源临界资源某段时间内只能允许一个进程使用的资源（即互斥资源）。某段时间内只能允许一个进程使用的资源（即互斥资源）。临界区临界区进程中访问临界资源的代码段。进程中访问临界资源的代码段。例：进程例：进程P1P1和进程和进程P2P2共享一个公用变量

3、共享一个公用变量S S，假设进程，假设进程P1P1需要对变量需要对变量S S进行加进行加1 1操作，而进程操作，而进程P2P2需要对变量需要对变量S S进行减进行减1 1操作。操作。假设假设s s的当前值是的当前值是1 1，（1 1）先执行语句）先执行语句 、，再执行语句、，再执行语句 、，则、，则s s；（2 2）先执行语句）先执行语句 、，再执行语句、，再执行语句 、，则、，则s s；（3 3）执行语句的次序为）执行语句的次序为 、，则、，则s s0 0；3.1 进程同步的基本概念 进程进程P1：register1=s;register1=register1+1;s=register1;进

4、程进程P2：register2=s;register2=register2-1;s=register2;解决办法：把公用变量解决办法：把公用变量s s作为临界资源处理，进程作为临界资源处理，进程P1P1和和进程地进程地P2P2互斥地访问公用变量互斥地访问公用变量s s。同步机制应遵循的准则（1 1）空闲让进空闲让进。无进程处于临界区时意味着临界资源处于空闲状。无进程处于临界区时意味着临界资源处于空闲状态，这时若有进程要求进入临界区应立即允许进入。态，这时若有进程要求进入临界区应立即允许进入。（2 2）忙则等待忙则等待。当已有进程进入其临界区时则意味着某临界资源。当已有进程进入其临界区时则意味着

5、某临界资源正在使用，所有其他欲访问该临界资源的进程试图进入各自临界正在使用，所有其他欲访问该临界资源的进程试图进入各自临界区时必须等待，以保证各进程互斥地进入访问相同临界资源的临区时必须等待，以保证各进程互斥地进入访问相同临界资源的临界区。界区。（3 3）有限等待有限等待。若干进程要求进入访问同一临界资源的临界区时，。若干进程要求进入访问同一临界资源的临界区时，应在有限时间内使一进程进入临界区，即不应出现各进程相互等应在有限时间内使一进程进入临界区，即不应出现各进程相互等待而都无法进入临界区的情况。待而都无法进入临界区的情况。（4 4）让权等待让权等待。当进程不能进入其临界区时应立即释放所占有

6、的。当进程不能进入其临界区时应立即释放所占有的CPUCPU，以免陷入，以免陷入“忙等忙等”（进程在占有（进程在占有CPUCPU的同时又一直等待），的同时又一直等待），保证其他可执行的进程获得保证其他可执行的进程获得CPUCPU运行。运行。通过计算机提供的一些通过计算机提供的一些机器指令机器指令来实现进程的互斥。来实现进程的互斥。机器指令机器指令是指在一个指令周期内执行完成的指令，而专用机器指令的执行则不是指在一个指令周期内执行完成的指令，而专用机器指令的执行则不会被中断。会被中断。专用机器指令专用机器指令有有3 3个：个：1.1.开关中断指令开关中断指令：进程在进入临界区之前先执行进程在进入临

7、界区之前先执行“关中断关中断”指令来屏蔽掉所有中断；进程完成临指令来屏蔽掉所有中断；进程完成临界区的任务后，再执行界区的任务后，再执行“开中断开中断”指令将中断打开。程序结构如下：指令将中断打开。程序结构如下：cobegincobegin /伪代码伪代码cobegincobegin和和coendcoend表示其间的进程可以并发执行表示其间的进程可以并发执行 process Pi()/process Pi()/i i=1,2,3,n=1,2,3,n /与临界资源无关的代码与临界资源无关的代码 lock out interrupts;/lock out interrupts;/关中断关中断 临界区

8、临界区;unlock interrupts;/unlock interrupts;/开中断开中断 /与临界资源无关的剩余代码与临界资源无关的剩余代码 coendcoend3.2 进程互斥方法 2.2.测试与设置指令测试与设置指令TSTS（TestTest and Set and Set）：要为每个临界资源设置一个整型变量要为每个临界资源设置一个整型变量s s，可以将它看成一把锁。若，可以将它看成一把锁。若s s的值为的值为0 0（开锁状态），则表示没有进程访问该锁对应的临界资源。（开锁状态），则表示没有进程访问该锁对应的临界资源。若若s s的值为的值为1 1（关锁状态），则表示该锁对应的临界资

9、源已被某个进程（关锁状态），则表示该锁对应的临界资源已被某个进程占用。占用。3.2 进程互斥方法 TSTS指令指令的函数描述：的函数描述：intint TS(TS(intint s)s)if(s)if(s)return 1;return 1;else else s=1;s=1;return 0;return 0;应用：应用：int s=0;cobegin process Pi()/i=1,2,3,n /与临界资源无关的代码 while(TS(s);/进入区 临界区；s=0;/退出区 /与临界资源无关的剩余代码 coend 3.3.交换指令（交换指令（SwapSwap）：要为每个临界资源设置一个

10、整型的全局变量要为每个临界资源设置一个整型的全局变量s s；若；若s s的值为的值为0 0则表示没有进程在临界区，若则表示没有进程在临界区，若s s的值为的值为1 1则表示有进程在临界区（即则表示有进程在临界区（即访问临界资源）。此外，还要为每个进程设置一个整型局部变量访问临界资源）。此外，还要为每个进程设置一个整型局部变量keykey。只有当。只有当s s的值为的值为0 0并且并且keykey的值为的值为1 1时，本进程才能进入临界区。进入临界区后，时，本进程才能进入临界区。进入临界区后，s s的值的值为为1 1且且keykey的值为的值为0 0；退出临界区时，应将；退出临界区时，应将s s

11、的值置为的值置为0 0。3.2 进程互斥方法 交换指令交换指令的函数描述：的函数描述：void Swap(int*a,int*b)int temp=*a;*a=*b;*b=temp;int s=0;/s为全局变量 cobegin process Pi()/i=1,2,3,n /与临界资源无关的代码 int key=1;/key为局部变量 do /进入区 Swap(&s,&key);while(key);临界区；s=0;/退出区 /与临界资源无关的剩余代码 coend 1.1.两标志进程互斥算法两标志进程互斥算法基本思想：基本思想：为希望访问临界资源的两个并发进程设置的两个标为希望访问临界资源的

12、两个并发进程设置的两个标志志T1T1和和T2T2来表示某个进程是否在临界区；若来表示某个进程是否在临界区；若TiTi（i i=1,2=1,2）等于）等于0 0则表示进程则表示进程PiPi（i i=1,2=1,2）没有在临界区，若）没有在临界区，若TiTi（i i=1,2=1,2）等于）等于1 1则表示进程则表示进程PiPi（i i=1,2=1,2）在临界区。每个进程在进入临界区之）在临界区。每个进程在进入临界区之前，先判断临界区是否已被另一进程访问，若是则本进程等待，前，先判断临界区是否已被另一进程访问，若是则本进程等待，否则本进程进入临界区。否则本进程进入临界区。3.2 进程互斥方法 1.1

13、.两标志进程互斥算法两标志进程互斥算法算法描述如下：算法描述如下：进程P1：while(T2);/检查P2是否在临界区T1=1;/设置P1在临界区标志临界区;T1=0;/设置P1不在临界区标志 进程P2：while(T1);/检查P1是否在临界区T2=1;/设置P2在临界区标志临界区;T2=0;/设置P2不在临界区标志改进算法描述如下：改进算法描述如下：进程P1：T1=1;/设置P1在临界区标志while(T2);/检查P2是否在临界区临界区;T1=0;/设置P1不在临界区标志 进程P2：T2=1;/设置P2在临界区标志while(T1);/检查P1是否在临界区临界区;T2=0;/设置P2不在

14、临界区标志 2.2.三标志进程互斥算法三标志进程互斥算法基本思想：基本思想：设置设置3 3个标志个标志T1T1、T2T2和和T T，其中，其中T1T1和和T2T2的作用与两标志进程的作用与两标志进程互斥算法相同，而互斥算法相同，而T T是一个公共标志，用来表示允许进入临界区的进程是一个公共标志，用来表示允许进入临界区的进程标号；若进程希望进入临界区，则先设置自己的标志标号；若进程希望进入临界区，则先设置自己的标志TiTi（i=1,2i=1,2），），然后再检测公共标志然后再检测公共标志T T，若，若T T等于等于i i（i=1,2i=1,2），则表示允许进程），则表示允许进程PiPi（i=1,

15、2i=1,2）进入临界区。）进入临界区。3.2 进程互斥方法 进程P1：T1=1;/设置P1在临界区标志T=2;/允许P2进入临界区while(T2=1&T=2);临界区;T1=0;/设置P1不在临界区标志 进程P2：T2=1;/设置P2在临界区标志T=1;/允许P1进入临界区while(T1=1&T=1);临界区;T2=0;/设置P2不在临界区标志 在操作系统中，信号量代表了一类物理资源，它是相应物理在操作系统中，信号量代表了一类物理资源，它是相应物理资源的抽象。具体实现时，信号量被定义成具有某种类型的变量。资源的抽象。具体实现时，信号量被定义成具有某种类型的变量。信号量可分为整型信号量和结

16、构体信号量。信号量可分为整型信号量和结构体信号量。1.1.整型信号量整型信号量 若信号量为若信号量为S S，则，则P P操作原语和操作原语和V V操作原语可以分别描述如下：操作原语可以分别描述如下：intint S;S;P(S):while(S=0);P(S):while(S=0);S=S-1;S=S-1;V(S):S=S+1;V(S):S=S+1;3.3 信号量机制 2.2.结构体型信号量结构体型信号量结构体型信号量描述如下：结构体型信号量描述如下：3.3 信号量机制 3.3 信号量机制 P(S)原语原语 P(S)操作的物理含义操作的物理含义 V(S)V(S)原语原语 V(S)操作的物理含义

17、操作的物理含义 方法：方法：为要进入的临界区设置一个互斥信号量为要进入的临界区设置一个互斥信号量mutexmutex，将，将mutex.valuemutex.value初值设置为初值设置为1 1，然后将各进程的临界区（访问临界资源的那段代码），然后将各进程的临界区（访问临界资源的那段代码）置于置于P(P(mutexmutex)和和V(V(mutexmutex)之间。程序模型如下：之间。程序模型如下：Semaphore Semaphore mutexmutex;mutex.valuemutex.value=1;=1;cobegincobegin process Pi()/process Pi()

18、/i i=1,2,3,n=1,2,3,n /与临界资源无关的代码与临界资源无关的代码 P(P(mutexmutex););临界区；临界区；V(V(mutexmutex););/与临界资源无关的剩余代码与临界资源无关的剩余代码 coendcoend3.3 信号量机制 3.3 信号量机制 例如，有两个进程例如，有两个进程P1P1和和P2P2要访问某一临界资源，它们各要访问某一临界资源，它们各自的临界区为自的临界区为L1L1和和L2L2。可设。可设S S为这两个进程的互斥信号为这两个进程的互斥信号量，其量，其S.valueS.value的初值为的初值为1 1。这时，只需把临界区置于。这时，只需把临界

19、区置于P(S)P(S)和和V(S)V(S)之间即可实现两进程的互斥。之间即可实现两进程的互斥。3.3 信号量机制进程进程P1：P(S);L1;V(S);进程进程P2：P(S);L2;V(S);若干进程为完成一个共同的任务而相互合作，这就需要相互合作的进若干进程为完成一个共同的任务而相互合作，这就需要相互合作的进程在某些协调点处（即需要同步的地方）插入对信号量的程在某些协调点处（即需要同步的地方）插入对信号量的P P操作或操作，操作或操作，以便协调它们的工作（实现进程间的同步）。以便协调它们的工作（实现进程间的同步）。例：在公共汽车上，司机和售票员各行其职独立工作。司机只有等售票例：在公共汽车上

20、，司机和售票员各行其职独立工作。司机只有等售票员关好车门后才能启动汽车，员关好车门后才能启动汽车，售票员只有等司机停好车后才售票员只有等司机停好车后才能开车门，即两者必须密切配能开车门，即两者必须密切配合、协调一致。合、协调一致。进程的同步是采用信号应进程的同步是采用信号应答方式来进行的。答方式来进行的。3.3 信号量机制 使用信号量实现进程同步示例使用信号量实现进程同步示例程序模型如下：程序模型如下：Semaphore Start,Open;Semaphore Start,Open;Start.value=0,Open.value=0;Start.value=0,Open.value=0;c

21、obegincobegin process process 司机司机()()while(1)while(1)P(Start);P(Start);启动汽车启动汽车;正常行驶正常行驶;到站停车到站停车;V(Open);V(Open);process process 售票员售票员()()while(1)while(1)关车门关车门;V(Start);V(Start);售票售票;P(Open);P(Open);开车门开车门;coendcoend 使用信号量实现进程同步示例使用信号量实现进程同步示例例：进程例：进程P1P1P4P4存在如右图所示的存在如右图所示的运行次序运行次序：并发执行的程序描述如下：

22、并发执行的程序描述如下：Semaphore a,b,c,d;Semaphore a,b,c,d;a.value=0,b.value=0,c.value=0,d.value=0;a.value=0,b.value=0,c.value=0,d.value=0;cobegincobegin process P1()process P1()P1;V(a);V(b);P1;V(a);V(b);process P2()process P2()P(a);P2;V(c);P(a);P2;V(c);process P3()process P3()P(b);P3;V(d);P(b);P3;V(d);process

23、 P4()process P4()P(c);P(d);P4;P(c);P(d);P4;coendcoend 有向边上的字母代表信有向边上的字母代表信号量，有向边的起始端进程号量，有向边的起始端进程在执行结束时，要对该信号在执行结束时，要对该信号量实施量实施V V操作，而有向边的结操作，而有向边的结束端进程在执行之前则要对束端进程在执行之前则要对该信号量实施该信号量实施P P操作，这样就操作，这样就确保了多个合作进程按事先确保了多个合作进程按事先约定的顺序执行。约定的顺序执行。3.4 经典互斥与同步问题 例：把一个长度为例：把一个长度为n n的缓冲池（的缓冲池（n n0 0，n n为缓冲池中缓冲

24、区的个数）为缓冲池中缓冲区的个数）与一群生产者进程与一群生产者进程P1P1、P2P2、PmPm和一群消费者进程和一群消费者进程C1C1、C2C2、CkCk联系起来，如图联系起来，如图3-63-6所示。只要缓冲池未满，生产者就可以把产所示。只要缓冲池未满，生产者就可以把产品送入空缓冲区；只要缓冲池未空，消费者就可以从满缓冲区中取品送入空缓冲区；只要缓冲池未空，消费者就可以从满缓冲区中取出产品进行消费。生产者和消费者的同步关系将禁止生产者向一满出产品进行消费。生产者和消费者的同步关系将禁止生产者向一满缓冲区中投放产品，也禁止消费者从一空缓冲区中取出产品。缓冲区中投放产品，也禁止消费者从一空缓冲区中

25、取出产品。用一个具有用一个具有n n个数组元素的一维数组个数组元素的一维数组B B来来构成循环队列，并用该数组模拟缓冲池，即构成循环队列，并用该数组模拟缓冲池，即每个数组元素代表一个缓冲区每个数组元素代表一个缓冲区。解决方法：解决方法：首先考虑生产者，只有空缓冲首先考虑生产者，只有空缓冲区存在时才能将产品放入空缓冲区，即需设置空缓冲区个数的信号量区存在时才能将产品放入空缓冲区，即需设置空缓冲区个数的信号量emptyempty，且，且empty.valueempty.value的初值为的初值为n n（初始时有（初始时有n n个空缓冲区）；其次考虑个空缓冲区）；其次考虑消费者，只有存在放入产品的满

26、缓冲区时才能从满缓冲区中取出产品，消费者，只有存在放入产品的满缓冲区时才能从满缓冲区中取出产品，即需设置放入产品的满缓冲区个数信号量即需设置放入产品的满缓冲区个数信号量fullfull，且，且full.valuefull.value的初值为的初值为0 0（初始时没有放入产品的满缓冲区）。（初始时没有放入产品的满缓冲区）。生产者生产者-消费者问题消费者问题实现程序实现程序item Bn;/数组数组B用来模拟用来模拟n个缓冲区个缓冲区Semaphore mutex,empty,full;mutex.value=1,empty.value=n,full.value=0;int in=0;/in指针指

27、向一个空缓冲区指针指向一个空缓冲区int out=0;/out指针指向一个满缓冲区指针指向一个满缓冲区item product;/product代表一个产品代表一个产品cobegin process Producer_i()/i=1,2,3,m while(1)product=produce();/生产一个产品生产一个产品 P(empty);/请求空缓冲区请求空缓冲区 P(mutex);/请求独占缓冲池请求独占缓冲池 Bin=product;/产品放到空缓冲区产品放到空缓冲区 in=(in+1)%n;/in移至下一个空缓冲区移至下一个空缓冲区 V(mutex);/释放缓冲池的使用权释放缓冲池的

28、使用权 V(full);/满缓冲区个数增一满缓冲区个数增一 /若有阻塞的消费者进程则唤醒之若有阻塞的消费者进程则唤醒之 process Consumer_j()/j=1,2,3,k while(1)P(full);/请求消费满缓冲区中的产品 P(mutex);/请求独占缓冲池使用权 product=Bout;/从满缓冲区中取出产品 out=(out+1)%n;/out移至下一个满缓冲区 V(mutex);/释放对缓冲池的使用权 V(empty);/空缓冲区个数增一 /若有阻塞的生产者进程则唤醒之 consume();/进行产品消费 coend 问题描述：问题描述：5 5个哲学家同坐在一张圆桌旁

29、，每个人的面前摆放着一碗面个哲学家同坐在一张圆桌旁，每个人的面前摆放着一碗面条，碗的两旁各摆放着一只筷子。假设哲学家的生活除了吃饭就是思考条，碗的两旁各摆放着一只筷子。假设哲学家的生活除了吃饭就是思考问题（这是一种抽象，即对该问题而言其他活动都无关紧要），而吃饭问题（这是一种抽象，即对该问题而言其他活动都无关紧要），而吃饭的时候需要左手拿一只筷子，右手拿一只筷子，然后开始进餐（如下的时候需要左手拿一只筷子，右手拿一只筷子，然后开始进餐（如下图）。吃完后又将筷子放回原处，继续思考问题。图）。吃完后又将筷子放回原处，继续思考问题。3.4 经典互斥与同步问题一个哲学家的活动进程可表示为：一个哲学家的

30、活动进程可表示为：（1 1）思考问题；）思考问题；（2 2）饿了停止思考，左手拿一只筷子（如果左侧哲）饿了停止思考，左手拿一只筷子（如果左侧哲学家已持有它，则需要等待）；学家已持有它，则需要等待）；（3 3）右手拿一只筷子（如果右侧哲学家已持有它，）右手拿一只筷子（如果右侧哲学家已持有它，则需要等待）；则需要等待）；（4 4）进餐；）进餐；（5 5）放右手筷子；）放右手筷子；（6 6）放左手筷子；）放左手筷子；（7 7）重新回到思考问题状态（）重新回到思考问题状态（1 1）。）。？如何协调如何协调5 5个哲学家的活动进程，使得每一个哲学家最终都可以进餐。个哲学家的活动进程，使得每一个哲学家最终

31、都可以进餐。考虑下面的两种情况：考虑下面的两种情况：（1 1）按哲学家的活动进程，当所有的哲学家都同时拿起左手筷子时，则所有）按哲学家的活动进程，当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，最终饿死。最终饿死。（2 2）将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左）将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子，这种情况不一定没有问题，因为可能在一个瞬间，所有的哲学家都手的筷子，这种情况不一定没有问题，因为可能在一个

32、瞬间，所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子；同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子；等一会，又同时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家都等一会，又同时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家都将无法进餐。将无法进餐。在哲学家就餐问题中，筷子应作为临界资源使用，因此在哲学家就餐问题中，筷子应作为临界资源使用，因此需为每支筷子设置一个互斥信号量，其初值均为需为每支筷子设置一个互斥信号量，其初值均为1 1。每个哲学。每个哲学家在进餐之前，必须借助互斥信号量的家在进餐之前，必须借助互斥信号量的P P

33、原语进行以下两个操原语进行以下两个操作：取左边的筷子和取右边的筷子。进餐完毕后，必须借助作：取左边的筷子和取右边的筷子。进餐完毕后，必须借助互斥信号量的互斥信号量的V V原语放下手上的两支筷子。原语放下手上的两支筷子。哲学家进餐问题哲学家进餐问题解决方法解决方法Semaphore chopstick5;Semaphore chopstick5;for(int i=0;i5;i+)for(int i=0;i5;i+)chopsticki.value=1;chopsticki.value=1;cobegincobegin process Philosopher_i()/i=0,1,2,3,4 pr

34、ocess Philosopher_i()/i=0,1,2,3,4 while(1)while(1)think();/think();/思考思考 P(chopsticki);/P(chopsticki);/拿起左手的筷子拿起左手的筷子 P(chopstick(i+1)%5);/P(chopstick(i+1)%5);/拿起右手的筷子拿起右手的筷子 eat();/eat();/进餐进餐 V(chopsticki);/V(chopsticki);/放回左手的筷子放回左手的筷子 V(chopstick(i+1)%5);/V(chopstick(i+1)%5);/放回右手的筷子放回右手的筷子 coen

35、dcoend可能引起死锁！可能引起死锁！哲学家进餐问题解决方法哲学家进餐问题解决方法（1 1）最多允许）最多允许4 4位哲学家同时拿起左手（或右手）的筷子。程序如下：位哲学家同时拿起左手（或右手）的筷子。程序如下：Semaphore mutex,chopstick5;Semaphore mutex,chopstick5;mutex.value=4;mutex.value=4;for(int i=0;i5;i+)for(int i=0;i5;i+)chopsticki.value=1;chopsticki.value=1;cobegincobegin process Philosopher_i(

36、)/i=0,1,2,3,4 process Philosopher_i()/i=0,1,2,3,4 while(1)while(1)think();/think();/思考思考 P(mutex);/P(mutex);/最多允许最多允许4 4个哲学家申请筷子个哲学家申请筷子 P(chopsticki);/P(chopsticki);/拿起左手的筷子拿起左手的筷子 P(chopstick(i+1)%5);/P(chopstick(i+1)%5);/拿起右手的筷子拿起右手的筷子 V(mutex);/V(mutex);/已拿到两个筷子，解除申请已拿到两个筷子，解除申请 eat();/eat();/进餐

37、进餐 V(chopsticki);/V(chopsticki);/放回左手的筷子放回左手的筷子 V(chopstick(i+1)%5);/V(chopstick(i+1)%5);/放回右手的筷子放回右手的筷子 coendcoend可预防死锁出现可预防死锁出现 哲学家进餐问题解决方法哲学家进餐问题解决方法（2 2）仅当哲学家的左、右两支筷子均可用时，才允许他同时拿起左、右）仅当哲学家的左、右两支筷子均可用时，才允许他同时拿起左、右手的两支筷子，否则一支筷子也不拿。手的两支筷子，否则一支筷子也不拿。程序如下：程序如下：Semaphore chopstick5;Semaphore chopstick

38、5;for(int i=0;i5;i+)for(int i=0;i5;i+)chopsticki.value=1;chopsticki.value=1;cobegincobegin process Philosopher_i()/i=0,1,2,3,4 process Philosopher_i()/i=0,1,2,3,4 while(1)while(1)think();/think();/思考思考 SP(chopsticki,chopstick(i+1)%5);/SP(chopsticki,chopstick(i+1)%5);/同时拿起左、右手的两只筷子同时拿起左、右手的两只筷子 eat()

39、;/eat();/进餐进餐 SV(chopsticki,chopstick(i+1)%5);/SV(chopsticki,chopstick(i+1)%5);/同时放回左、右手的两只筷子同时放回左、右手的两只筷子 coendcoend可预防死锁出现可预防死锁出现 哲学家进餐问题解决方法哲学家进餐问题解决方法（3 3）奇数号哲学家先取左手的筷子，然后再取右手的筷子；而偶数哲学家先取右）奇数号哲学家先取左手的筷子，然后再取右手的筷子；而偶数哲学家先取右手的筷子，然后再取左手的筷子。程序如下：手的筷子，然后再取左手的筷子。程序如下：Semaphore chopstick5;Semaphore cho

40、pstick5;for(int i=0;i5;i+)chopsticki.value=1;for(int i=0;i5;i+)chopsticki.value=1;cobegin cobegin process Philosopher_i()/i=0,1,2,3,4 process Philosopher_i()/i=0,1,2,3,4 while(1)while(1)think();/think();/思考思考 if(i%2=1)/if(i%2=1)/如果是奇数号哲学家如果是奇数号哲学家 P(chopsticki);/P(chopsticki);/拿起左手的筷子拿起左手的筷子 P(chops

41、tick(i+1)%5);/P(chopstick(i+1)%5);/拿起右手的筷子拿起右手的筷子 else /else /如果是非奇数号哲学家如果是非奇数号哲学家 P(chopstick(i+1)%5);/P(chopstick(i+1)%5);/拿起右手的筷子拿起右手的筷子 P(chopsticki);/P(chopsticki);/拿起左手的筷子拿起左手的筷子 eat();/eat();/进餐进餐 V(chopsticki);/V(chopsticki);/放回左手的筷子放回左手的筷子 V(chopstick(i+1)%5);/V(chopstick(i+1)%5);/放回右手的筷子放回

42、右手的筷子 coendcoend可预防死锁出现可预防死锁出现 问题问题描述描述：有一个数据文件可以被多个进程共享，各进程共享数有一个数据文件可以被多个进程共享，各进程共享数据文件的方式不同。有的进程只是从文件中读取信息，这类进程据文件的方式不同。有的进程只是从文件中读取信息，这类进程称为称为“读者进程读者进程”。有的进程写信息到文件中或者又读又写，这。有的进程写信息到文件中或者又读又写，这些进程统称为些进程统称为“写者进程写者进程”。为了不使文件内容混乱，要求各进。为了不使文件内容混乱，要求各进程在使用文件时必须遵守以下规定：程在使用文件时必须遵守以下规定：（1 1）允许多个读者进程同时读文件

43、（读操作不破坏文件）。）允许多个读者进程同时读文件（读操作不破坏文件）。（2 2）不允许写者进程与其他进程同时访问文件（有写操作存在可）不允许写者进程与其他进程同时访问文件（有写操作存在可能造成读取信息混乱）。能造成读取信息混乱）。3.4 经典互斥与同步问题 读者读者-写者问题中的进程之间存在写者问题中的进程之间存在3 3种制约关系种制约关系：一是读者之间允许：一是读者之间允许同时读；二是读者与写者之间需要互斥；三是写者与写者之间也需要互同时读；二是读者与写者之间需要互斥；三是写者与写者之间也需要互斥。斥。方法：方法：为解决读者进程、写者进程之间的同步，需要设置如下的信号量：为解决读者进程、写

44、者进程之间的同步，需要设置如下的信号量：（1 1）读互斥信号量）读互斥信号量rmutexrmutex。用于使读者进程互斥地访问公用变量（共。用于使读者进程互斥地访问公用变量（共享变量）享变量）countcount，且，且rmutex.vaulermutex.vaule的初值为的初值为1 1。（2 2）写互斥信号量）写互斥信号量wmutexwmutex。用于实现写者进程与读者进程的互斥以及。用于实现写者进程与读者进程的互斥以及写者进程与写者进程的互斥，且写者进程与写者进程的互斥，且wmutex.valuewmutex.value的初值为的初值为1 1。（3 3）公用变量）公用变量countcou

45、nt。用于记录当前正在读文件的读者进程个数，且。用于记录当前正在读文件的读者进程个数，且count.valuecount.value的初值为的初值为0 0，仅在，仅在count.valuecount.value的值为的值为0 0时才允许写者进程访时才允许写者进程访问文件。问文件。3.4 经典互斥与同步问题 读者读者-写者问题实现写者问题实现程序程序 Semaphore rmutex,wmutex;Semaphore rmutex,wmutex;rmutex.value=1,wmutex.value=1;rmutex.value=1,wmutex.value=1;int count=0;int

46、count=0;cobegin cobegin process Reader_i()process Reader_i()/i=1,2,3,m/i=1,2,3,m P(rmutex);/P(rmutex);/申请对申请对countcount的访问权的访问权,如有读者阻塞则阻塞自己如有读者阻塞则阻塞自己 if(count=0)P(wmutex);/if(count=0)P(wmutex);/是第一个读者则阻塞写者进入是第一个读者则阻塞写者进入 /如已有写者进入则阻塞自己如已有写者进入则阻塞自己 count+;count+;/读者个数加读者个数加1 1 V(rmutex);V(rmutex);/释放

47、对释放对countcount的访问权的访问权 读文件操作读文件操作;P(rmutex);P(rmutex);/申请对申请对countcount的访问权的访问权 count-;count-;/读者个数减读者个数减1 1 if(count=0)V(wmutex);/if(count=0)V(wmutex);/最后一个读者离开则允许写者进入最后一个读者离开则允许写者进入 /如果有被阻塞的写者则唤醒阻塞的第一个写者如果有被阻塞的写者则唤醒阻塞的第一个写者 V(rmutex);V(rmutex);/释放对释放对countcount的访问权的访问权 process Writer_j()process Wr

48、iter_j()/j=1,/j=1,2,2,3,3,n n P(wmutex);P(wmutex);/无读者、写者时进入且阻塞后来的读者、写者进入无读者、写者时进入且阻塞后来的读者、写者进入 /已有读者、写者进入则阻塞自己已有读者、写者进入则阻塞自己 写文件操作写文件操作;V(wmutex);V(wmutex);/允许后续到达的读者、写者进入允许后续到达的读者、写者进入 coendcoend 读者读者-写者问题实现程序存在的问题与解决方法写者问题实现程序存在的问题与解决方法 读者读者-写者问题的写者优先写者问题的写者优先程序程序 process process Writer_jWriter_j

49、()()P(w);P(w);P(P(wmutexwmutex););V(V(wmutexwmutex););V(w);V(w);coendcoend 有了信号量有了信号量P(W)P(W)，则当写者进程，则当写者进程到达并执行了到达并执行了P(W)P(W)原语后，其后到达原语后，其后到达的所有读者进程或写者进程都因执行的所有读者进程或写者进程都因执行P(W)P(W)原语而阻塞。等到该写者进程到原语而阻塞。等到该写者进程到达前已经进行读操作的那些读者进程达前已经进行读操作的那些读者进程读操作完毕后，最后退出读操作的读读操作完毕后，最后退出读操作的读者进程，将通过者进程，将通过V(wmutex)V(

50、wmutex)唤醒该写者唤醒该写者进程让其进行写操作。当写者进程写进程让其进行写操作。当写者进程写文件操作结束后，又通过文件操作结束后，又通过V(W)V(W)原语唤原语唤醒其他阻塞的读者进程或写者进程醒其他阻塞的读者进程或写者进程（如果有的话）。（如果有的话）。问题问题描述描述：有一个理发师、一把理发椅和有一个理发师、一把理发椅和n n把供等侯理发顾客坐的椅子。把供等侯理发顾客坐的椅子。如果没有顾客则理发师就在理发椅子上睡觉。当一个顾客到来时则必须如果没有顾客则理发师就在理发椅子上睡觉。当一个顾客到来时则必须唤醒理发师进行理发。若理发师正在理发时又有顾客到来，如果有空椅唤醒理发师进行理发。若理