操作系统第3章进程通信与控制

1、第第三三章章进进程程目的与要求目的与要求：了解并发程序的高级语了解并发程序的高级语言表示与操作系统支持下的实现；同言表示与操作系统支持下的实现；同步与互斥问题。步与互斥问题。重点与难点重点与难点：并发程序中的同步与互：并发程序中的同步与互斥斥并发与并行的区别并发并发是指多个任务在单处理机下分时运行，是指多个任务在单处理机下分时运行，从宏观上看它们同时都在向前推进，但从从宏观上看它们同时都在向前推进，但从微观上来看，它们正在分时地轮流使用处微观上来看，它们正在分时地轮流使用处理机。理机。并行并行是指多个任务在多个处理机上正在同是指多个任务在多个处理机上正在同时运行，从微观上看这些任务分别是在各时

2、运行，从微观上看这些任务分别是在各自的物理处理机上分别运行。自的物理处理机上分别运行。回顾第2章 程序并发执行的特征3：程序执行结果的不可再现性。计算结果与执行的速度有关，从而失去了可再现性。如对共享变量的使用。例，有2个循环程序A和B，它们共享一个变量n。程序A: n+； /* n=n+1 程序B: coutn; /* 输出n的值 n=0; /* 变量n清0 程序A和B以不同的速度运行，执行顺序可能出现哪3种情况？（假定变量n的初值为100)。OSOS选择执行程序选择执行程序A A完成后再执行程序完成后再执行程序B BA A：n+n+； B B：coutncoutn； B B：n=0n=0；

3、此时得到的此时得到的n n值分别为值分别为10l10l，10l10l，O O。OSOS选择执行程序选择执行程序B B完成后再执行程序完成后再执行程序A AB B：coutncoutn；B B：n=0n=0；A A：n+;n+;此时得到的此时得到的n n值分别为值分别为100, 0, 1100, 0, 1 OS选择先执行程序B的一个语句后，再执行程序A的一个语句，最后执行程序B的第二个语句。B：coutin; cinin; Out=in; Out=in; coutout; coutin; cinin; Out=in; Out=in; Coutout; Coutin; Cinin; Out=in;

4、 Out=in; Coutout; Coutin; Cinin; Out=in; Out=in; Coutout; Cout=1) X1X1-1： AjX1； 输出一张票输出一张票 else 输出输出“票售完票售完” void T2（X2） 按旅客订票要求找到按旅客订票要求找到AjX2Aj； if (X2 =1) X2X2-1： AjX2； 输出一张票输出一张票 else输出输出“票售完票售完” 考虑以下的执行次序:(a)和(b)按按(a)的序列执行时，结果是正确的。按的序列执行时，结果是正确的。按(b)的序列执行情况，则两个旅客可的序列执行情况，则两个旅客可能各自都买到一张同天同次航班的机票

5、，可是，能各自都买到一张同天同次航班的机票，可是，Aj的值实际上只减去了的值实际上只减去了1,造造成余票数的不正确。成余票数的不正确。设设Aj=50则则x1=50此时此时x2=50此时此时x1=49此时此时x2=49此时此时Aj=49此时此时Aj=49特别是，当某次航班只有一张余票时，就可能把特别是，当某次航班只有一张余票时，就可能把这一张票同时售给了两位旅客，显然这是不能允许的。这一张票同时售给了两位旅客，显然这是不能允许的。设设Aj=1则则x1=1此时此时x2=1此时此时x1=0此时此时x2=0此时此时Aj=0此时此时Aj=0出错原因是什么？出错原因是什么？余票额是共享变量！没有建立对共享

6、变量余票额是共享变量！没有建立对共享变量的使用与保护机制。的使用与保护机制。由以上的例子说明什么？由以上的例子说明什么？要想实现多道程序并发执行，必须设法对要想实现多道程序并发执行，必须设法对共享变量（资源）加入一定的管理机制和共享变量（资源）加入一定的管理机制和一定的保护措施，保证共享资源的一定的保护措施，保证共享资源的协调使协调使用用，以避免出现与时间有关的错误，以保，以避免出现与时间有关的错误，以保持并发程序的可再现性。持并发程序的可再现性。思考：对共享变量（资源）如何加思考：对共享变量（资源）如何加上这种规则（机制）呢？上这种规则（机制）呢？这是这是现代操作系统必须解决的核心问题！现代

7、操作系统必须解决的核心问题！同步机制：信号传递？同步机制：信号传递？互斥机制：加锁？互斥机制：加锁？同步关系同步关系（亦称直接制约关系）（亦称直接制约关系）: : 指完成同一任务的伙伴进程间，因需指完成同一任务的伙伴进程间，因需要在某些位置上协调它们的工作而相互等要在某些位置上协调它们的工作而相互等待、相互交换信息所产生的制约关系。待、相互交换信息所产生的制约关系。如：如：接力跑比赛中，运动员之间要配合接力跑比赛中，运动员之间要配合默契。一棒一棒接着跑。默契。一棒一棒接着跑。3.2 进程的同步与互斥例例 ：在计算机系统中对同一缓冲：在计算机系统中对同一缓冲区的数据的输入与输出操作。缓冲区区的数

8、据的输入与输出操作。缓冲区满才能输出，缓冲区空才能输入。满才能输出，缓冲区空才能输入。 缓冲区缓冲区输入输入进程进程输出输出进程进程已存满，可取已存满，可取已取空，可存已取空，可存互斥关系互斥关系（亦称间接制约关系）（亦称间接制约关系）: : 即进程间因相互竞争使用独占型资即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。源（互斥资源）所产生的制约关系。例（例（1 1）：上例中）：上例中ECHOECHO程序中的变量程序中的变量OUTOUT和和ININ，例（例（2 2）：飞机订票系统中的余票额）：飞机订票系统中的余票额AjAj必必须互斥使用。须互斥使用。例（例（3 3）：多个用户进程

9、同用一台打印机）：多个用户进程同用一台打印机时。时。既同步又要互斥的例子：既同步又要互斥的例子：1 1、客车上的司机和售票员各司其职、客车上的司机和售票员各司其职为完成同一个运送乘客的任务相互配为完成同一个运送乘客的任务相互配合。合。互斥：司机开车时售票员不要开门，互斥：司机开车时售票员不要开门，售票员开门时司机不要开车；售票员开门时司机不要开车；同步：司机停车时售票员才能开门，同步：司机停车时售票员才能开门，售票员关门时司机才能开车）。售票员关门时司机才能开车）。正常行车正常行车到站停车到站停车启动汽车启动汽车售票售票开车门开车门关车门关车门司机进程司机进程售票员进程售票员进程互斥与同步的例

10、子：互斥与同步的例子：2 2、有限缓冲区问题。互斥：存时不要、有限缓冲区问题。互斥：存时不要取，取时不要存。同步：有数据才能取，取时不要存。同步：有数据才能取，有空区才能存。取，有空区才能存。PkP2C1C2CmP1存存取取互斥与同步的例子：互斥与同步的例子：3 3、读者与写者问题。、读者与写者问题。（Readers/WritersReaders/Writers问题）问题）4 4、哲学家就餐问题。（就餐和思、哲学家就餐问题。（就餐和思考需同步与互斥）考需同步与互斥）一一、两个基本概念：、两个基本概念：临界资源临界资源（critical resource）：）：一次仅允一次仅允许一个进程使用的资

11、源。许一个进程使用的资源。如：上例如：上例ECHO程序中的共享变量程序中的共享变量IN，OUT,飞机订票系统的余票额飞机订票系统的余票额Aj等。等。3.3 3.3 临界资源和临界区临界资源和临界区临界段（区）临界段（区）（critical section) ：各进程各进程必须互斥执行的程序段。必须互斥执行的程序段。如：对余票额如：对余票额Aj进行操作的那个程序段。进行操作的那个程序段。u二、临界资源须互斥使用例例1 1打印机：打印机： P1,P2P1,P2两进程使用同一打印机。两进程使用同一打印机。如果不互斥使用会交叉输出。如果不互斥使用会交叉输出。例例2 2共享变量：共享变量：共享变量是临界

12、资源。共享变量是临界资源。 Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=M; ;Coend;如下例对共享变量如下例对共享变量countcount的互斥访问。的互斥访问。互斥执行互斥执行例例:若若count为为300,如互斥执如互斥执行结果行结果count为为600,临界区临界区临界区临界区Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=M; ;Coend;若不互斥若

13、不互斥,可能结果为可能结果为500,400.（设（设count初值为初值为300）不互斥执行不互斥执行设设A在此处中断，在此处中断，执行完执行完B三、进程互斥进入临界区的一般结构三、进程互斥进入临界区的一般结构 进入临界段之前要申请，获得批进入临界段之前要申请，获得批准方可进入；准方可进入； 退出临界段之后要声明，以便其退出临界段之后要声明，以便其他进程进入。他进程进入。While( 1 ) 进入区进入区 临界区临界区退出区退出区 剩余区（其余代码）剩余区（其余代码） ;Cobegin void A( ) N=count; N=N+100; count=N; ; void B( ) M=cou

14、nt; M=M+200; count=M; ;Coend;例如上例对共享变量例如上例对共享变量countcount的互斥访问。的互斥访问。临界区临界区临界区临界区Entry code(Entry code(请求独占请求独占) )exit code(exit code(释放释放) )Entry code(Entry code(请求独占请求独占) )exit code(exit code(释放释放) )例如：对打印机（临界资源）的互斥使用例如：对打印机（临界资源）的互斥使用Entry code(Entry code(请求独占请求独占) )exit code(exit code(释放释放) )使用打

15、印机的程序段使用打印机的程序段P1P1：临界区临界区Entry code(Entry code(请求独占请求独占) )exit code(exit code(释放释放) )使用打印机的程序段使用打印机的程序段P2P2：临界区临界区临界资源临界资源操作系统采用怎样的方式管理临界资源呢？四、临界区进入准则（同步机制）四、临界区进入准则（同步机制）准则准则1 1：空闲让进。若无进程进入空闲空闲让进。若无进程进入空闲的临界区，一次仅允许一个进程进入。的临界区，一次仅允许一个进程进入。准则准则2 2：忙则等待。任何时候，处于临忙则等待。任何时候，处于临界区内的进程不可多于一个，如果已有界区内的进程不可多

16、于一个，如果已有进程进入自己的临界区，则其他进程必进程进入自己的临界区，则其他进程必须等待。须等待。准则准则3 3：有限等待。进入临界区的进程有限等待。进入临界区的进程要在有限时间内退出，以便其他进程及要在有限时间内退出，以便其他进程及时进入自己的临界区。时进入自己的临界区。准则准则4 4：让权等待。如果进程不能进入让权等待。如果进程不能进入自己的临界区，则应让出自己的临界区，则应让出CPUCPU，避免进程，避免进程出现出现“忙等忙等”现象。现象。有了准则后，如何在临界区上加入（或实现）这种机制呢？四、临界区进入准则（同步机制）四、临界区进入准则（同步机制）Cobegin void A( )

17、N=count; N=N+100; count=N; ; void B( ) M=count; M=M+200; count=M; ;Coend;例如上例对共享变量例如上例对共享变量countcount的互斥访问。的互斥访问。临界区临界区临界区临界区Entry code(Entry code(请求独占请求独占) )exit code(exit code(释放释放) )Entry code(Entry code(请求独占请求独占) )exit code(exit code(释放释放) )如何在临界区上加入（或实现）这种机制呢？3.4 互斥实现方法互斥实现方法2 2、专用机器指令、专用机器指令（1

18、 1）“Test and SetTest and Set”指令指令管理思想：加锁机制。开始锁打开即未锁上。先到的管理思想：加锁机制。开始锁打开即未锁上。先到的进程拿到锁并进入临界区然后反锁，直到从临界区退进程拿到锁并进入临界区然后反锁，直到从临界区退出，开锁交还。出，开锁交还。该指令功能描述为：该指令功能描述为：int ts(static int lock)int ts(static int lock) int ts=lock; int ts=lock; lock=1; lock=1;return(ts);return(ts); 这里：这里：tsts函数作为一个原语执行（即不存在中断）。函数作

19、为一个原语执行（即不存在中断）。locklock有两种状态：当有两种状态：当lock=0lock=0时，表示该资源空闲；时，表示该资源空闲；当当lock=1lock=1时，表示该资源正在被使用。时，表示该资源正在被使用。3.4 互斥实现方法互斥实现方法 例例1：利用：利用testset指令实现指令实现互斥的循环进程描述：互斥的循环进程描述：P(i):While(1) while (ts(lock) 空操作空操作; /测试锁是否已锁上？测试锁是否已锁上？ ; lock=0; main( ) lock=0; cobegin p(1);P(2);P(n); coend .假设进程假设进程P(2)欲进

20、入临欲进入临界区，调用过程界区，调用过程P（2），），执行执行ts(lock)后返回后返回ts为为假，并置假，并置lock=1,故故P(2)进入临界区，若此时有进入临界区，若此时有进程进程P(1)欲进入临界区，欲进入临界区，调用调用P(1),执行测试执行测试ts(lock),因因lock为为1，故，故ts返回真，故返回真，故P(1)被拒被拒绝进入临界区。绝进入临界区。（2 2）SwapSwap指令实现进程指令实现进程管理思想：加锁机制，一把锁配管理思想：加锁机制，一把锁配n n把钥匙，一个进程一把钥匙，一个进程一把钥匙，谁能开锁谁进入临界区。把钥匙，谁能开锁谁进入临界区。该指令功能描述为：该指

21、令功能描述为：void swapvoid swap（static int a,bstatic int a,b）；）；int tempint temp；temp=atemp=a；a=ba=b；b=tempb=temp； 这里，这里，SWAPSWAP指令也是原语。在利用指令也是原语。在利用SwapSwap实现实现进程互斥时，可为临界资源设置一个全局变量进程互斥时，可为临界资源设置一个全局变量locklock，其，其初值为初值为0 0，在每个进程中再利用一个局部变量，在每个进程中再利用一个局部变量keykey。然后。然后通过通过swapswap指令实现互斥。指令实现互斥。3.4 互斥实现方法互斥实现

22、方法2 2、专用机器指令、专用机器指令例例2：利用：利用swap指令实现互斥的描述指令实现互斥的描述/*I为进程号，如为为进程号，如为P（2） 为进程为进程P2调用调用P(I)： While(1) Keyi=1; Do swap(lock,keyi); while (keyi); ; lock=0; ; main( ) lock=0; cobegin p(1);P(2);P(n); coend例：例：P(2)先调用先调用P过程，过程，则此时则此时lock=1,Key2=0,P(2)进进入临界区。当入临界区。当P(2)正正在临界区时，若有另在临界区时，若有另一进程又想进入临界一进程又想进入临界区

23、，执行区，执行P(1)，此时，此时key1=1,lock=1,两者交两者交换还是换还是1，故，故P(1)只能只能循环等待。直至循环等待。直至P(2)退出临界区，交换使退出临界区，交换使lock=0为止。为止。v3、使用特殊机器指令实现互斥的优缺点、使用特殊机器指令实现互斥的优缺点优点：优点：（1）可用于：含有任意数量进程的单处理）可用于：含有任意数量进程的单处理机或共享主存的多处理机；机或共享主存的多处理机；（2）比较简单，易于验证；）比较简单，易于验证；（3）可支持多个临界段，每个临界段用各）可支持多个临界段，每个临界段用各自的变量加以定义。如自的变量加以定义。如lock变量的改变。变量的改

24、变。缺点：缺点：（1）由于采用忙碌由于采用忙碌-等待等待(死等，一直循环判死等，一直循环判断等待，等到可以进入临界区为止断等待，等到可以进入临界区为止)，所以在，所以在进程等待进入临界段时，将耗费处理机时间。进程等待进入临界段时，将耗费处理机时间。（2）有可能产生饥饿。）有可能产生饥饿。（3）有可能产生死锁。如：）有可能产生死锁。如：P1在执行在执行TS或或SWAP指令时，拥有更高优先级的进程指令时，拥有更高优先级的进程P2中中断断P1，并且，并且P2又要使用又要使用P1所占用的资源。所占用的资源。二、利用软件方法解决进程互斥问题二、利用软件方法解决进程互斥问题假如有假如有2 2个进程个进程P

25、1P1和和P2P2，它们共享一个临界资，它们共享一个临界资源源R R，则，则P1P1与与P2P2并发执行，并发执行，P1P1与与P2P2互斥使用互斥使用R R。并发执行的程序段如下：并发执行的程序段如下：mainmain（）（）cobegin cobegin p1p1；p2p2； 3.4 互斥实现方法互斥实现方法互斥执行的程序段用软件实现。互斥执行的程序段用软件实现。算法算法1 1（单标志算法）（单标志算法）我们设置一个公用整型变量我们设置一个公用整型变量turnturn，用于指示被允许进入临界区的进程的用于指示被允许进入临界区的进程的编号，即若编号，即若turn=1turn=1，表示允许进程

26、，表示允许进程P1P1进入临界区。算法进入临界区。算法1 1对对P1P1、P2P2进程的描进程的描述如下：述如下：P1P1：whilewhile（1 1） whilewhile（turnturn！1 1） no-opno-op； critical sectioncritical sectionturnturn2 2； P2P2：whilewhile（1 1） whilewhile（turnturn！2 2） no-opno-op； critical sectioncritical sectionturnturn1 1； 测试自己能测试自己能否进入临界否进入临界区区把临界区使把临界区使用权交给用

27、权交给P2P2对算法一的评价：对算法一的评价：该算法可确保每次只允许一个进程进该算法可确保每次只允许一个进程进入临界区。入临界区。2 2个进程是轮流地进入临界区。个进程是轮流地进入临界区。不能保证实现不能保证实现“空闲让进空闲让进”的准则。的准则。 如当进程如当进程P2P2暂时并未要求访问该临暂时并未要求访问该临界资源，而界资源，而P1P1又想再次访问该资源，但又想再次访问该资源，但它却无法进入临界区。它却无法进入临界区。算法算法2 2（双标志、先检查算法）（双标志、先检查算法）基本思想：在每一个进程访问临界资源基本思想：在每一个进程访问临界资源之前，先去查看一下临界资源是否正被之前，先去查看

28、一下临界资源是否正被访问。若正被访问，该进程需等待；否访问。若正被访问，该进程需等待；否则进入自己的临界区。为此，设置一个则进入自己的临界区。为此，设置一个数组，使其中每个元素的初值为数组，使其中每个元素的初值为0 0，表，表示所有进程都未进入临界区。若示所有进程都未进入临界区。若flag0=1flag0=1时，表示进程时，表示进程P1P1正在临界区正在临界区内执行；若且内执行；若且flag1= 1flag1= 1时，表示进程时，表示进程P2P2正在临界区内执行。算法正在临界区内执行。算法2 2的描述如的描述如下：下：Int flag2=0Int flag2=0，00；P1P1：whilewh

29、ile（1 1） while while（flag1flag1） no-opno-op； flag0=1flag0=1； critical sectioncritical section flag0=0 flag0=0； P2P2：whilewhile（1 1） while while（flag0flag0） no-opno-op； flag1=1flag1=1； critical sectioncritical section flag1=0 flag1=0； 测试对方是测试对方是否在临界区，否在临界区，如果在，在如果在，在此循环等待此循环等待如果对方不如果对方不在临界区，在临界区，自己进入

30、临自己进入临界区界区对算法对算法2 2的评价：的评价：算法算法2 2解决了有空让进的问题。解决了有空让进的问题。违背了违背了“忙则等待忙则等待”的准则。即的准则。即当当P1P1和和P2P2都未进入临界区时，它们各自都未进入临界区时，它们各自的访问标志都为的访问标志都为0.0.如果如果P1P1和和P2P2几乎是在几乎是在同时都要求进入临界区，因而都发现对同时都要求进入临界区，因而都发现对方的访问标志方的访问标志flagflag为为0 0。于是。于是2 2个进程都个进程都先后进入临界区，显然，这时又违背了先后进入临界区，显然，这时又违背了“忙则等待忙则等待”的准则。的准则。算法算法3 3（双标志、

31、先修改后检查算法）（双标志、先修改后检查算法） 算法算法3 3中仍然使用了数组中仍然使用了数组flag flag ，但但flag0=1flag0=1表示进程表示进程P1P1希望进入临界希望进入临界区，然后再去查看区，然后再去查看P2P2的标志。若此时的标志。若此时flag1=1flag1=1，则，则P1P1等待；否则，等待；否则，P1P1进入进入临界区；对于进程临界区；对于进程P2P2亦然。亦然。Int flag2=0Int flag2=0，00；P1P1：whilewhile（1 1） Flag0=1 Flag0=1； whilewhile（flag1flag1） no-opno-op； c

32、ritical sectioncritical section flag0=0 flag0=0； P2P2：whilewhile（1 1） Flag1=1 Flag1=1； whilewhile（flag0flag0） no-opno-op； critical sectioncritical section flag1=0 flag1=0； 测试对方是测试对方是否在临界区否在临界区对算法对算法3 3的评价：的评价：算法算法3 3又会造成最终谁都不能进入临又会造成最终谁都不能进入临界区的后果。因而它既违背了界区的后果。因而它既违背了“有空让进有空让进”的准则的准则1 1，又违背了，又违背了“有限

33、等待有限等待”的准则的准则3 3。例如，当例如，当P1P1和和P2P2几乎在同时要进入临界区，几乎在同时要进入临界区，双方都在双方都在“谦让谦让”，结果谁也进不了临界，结果谁也进不了临界区。区。 算法算法4 4（先修改、后检查、后修改者等待（先修改、后检查、后修改者等待算法）算法）Int flag2=0Int flag2=0，00；P1:whileP1:while（1 1） Flag0=1Flag0=1；turn=2turn=2；While(flag1&turn=2While(flag1&turn=2） no-opno-op； critical sectioncritical

34、section Flag0=0 Flag0=0； P2P2：whilewhile（1 1） Flag1=1Flag1=1；turn=1turn=1；While(flag0&turn=1While(flag0&turn=1） no-opno-op； critical sectioncritical section Flag1=0 Flag1=0； 评价：该算法是组合了算法评价：该算法是组合了算法1 1和算法和算法3 3中的中的关键概念而形成的，保证了关键概念而形成的，保证了“忙则等待忙则等待”，又实现了又实现了“有空让进有空让进”。Int flag2=0Int flag2=0，0

35、0；P1:whileP1:while（1 1） Flag0=1Flag0=1；turn=2turn=2；While(flag1&turn=2While(flag1&turn=2） no-opno-op； critical sectioncritical section Flag0=0 Flag0=0； P2P2：whilewhile（1 1） Flag1=1Flag1=1；turn=1turn=1；While(flag0&turn=1While(flag0&turn=1） no-opno-op； critical sectioncritical section

36、Flag1=0 Flag1=0； 3.5. 3.5. 信号量和信号量和PVPV操作操作(semaphore)(semaphore) 由于实现互斥的软件方法和硬件方法都存由于实现互斥的软件方法和硬件方法都存在缺陷，故需要寻找其他机制。现寄希望于在缺陷，故需要寻找其他机制。现寄希望于操作系统和程序设计提供对并发的支持。操作系统和程序设计提供对并发的支持。（信号量、管程、消息传递）（信号量、管程、消息传递）信号量机制是一种卓有成效的解决进程同步信号量机制是一种卓有成效的解决进程同步问题的工具。问题的工具。一、一、信号量的定义信号量的定义信号量一般由两个成员组成。其中一个信号量一般由两个成员组成。其中

37、一个成员为整型变量，表示该信号量的值；成员为整型变量，表示该信号量的值；另一个是指向另一个是指向PCBPCB的指针。的指针。信号量的信号量的C C语言描述如下：语言描述如下：struct semaphoreint value;/信号量的值域信号量的值域struct PCB *queue; /* *queuequeue为等待进程链表指针为等待进程链表指针S;信号量变量信号量变量S S的值只能通过的值只能通过P P、V V操作来改变它。操作来改变它。二、二、P P和和V V操作原语的伪代码形式如下：操作原语的伪代码形式如下：P操作操作(或或wait操作操作)描述：描述：Void P(semapho

38、re S) S.value-; if (s.value0)Block(S.queue );V操作操作(或或singal操作操作)描述：描述：Void V(semaphore S)s.value+;if (s.value=0)wakeup(S.queue); 通过对信号量做通过对信号量做P P、V V操作来实现互斥访操作来实现互斥访问临界区。问临界区。三、三、N N个进程利用信号量、个进程利用信号量、PVPV操作互操作互斥使用临界段的一般结构：斥使用临界段的一般结构：设互斥信号量设互斥信号量S S的初值为的初值为1 1 P(S)P(S)V(S)V(S)临界区临界区非临界段非临界段Do while

39、(1)临界资源临界资源如打印机如打印机 S.value-; S.value-; if (S.value0) if (S.value0) Block(S.L ) Block(S.L )S.value+;S.value+;if(S.value=0)if(S.value=0,s.value=0,则该进程继续执行；则该进程继续执行；如果如果s.value0,s.value0,s.value0,则该进程继续执则该进程继续执行；（行；（S0S0说明等待队列说明等待队列queuequeue中无等待的中无等待的进程）进程） 如果如果s.value=0,s.value=0,则释放信号量则释放信号量队列队列L L

40、上的第一个上的第一个PCBPCB所对应的进程（把阻所对应的进程（把阻塞态改为就绪态），执行塞态改为就绪态），执行V V操作的进程继操作的进程继续执行。续执行。五、五、信号量机制物理含义信号量机制物理含义1 1、信号量初值、信号量初值S.valueS.value表示系统中某种资表示系统中某种资源的数目，又称资源信息量。源的数目，又称资源信息量。2 2、执行一次、执行一次P P操作意味着请求分配一个单操作意味着请求分配一个单位资源，因此位资源，因此S.valueS.value的值减的值减1 1；当当S.value0S.value0S.value0时时, ,表示等待队列无等待该表示等待队列无等待该信

41、号量的进程信号量的进程, ,其值表示还可用的资源数其值表示还可用的资源数目目. .做做P P操作的进程继续执行操作的进程继续执行. .3 3、执行一次、执行一次V V操作意味着释放一个单位资源，操作意味着释放一个单位资源，因此因此S.valueS.value的值加的值加1 1；若若s.value=0s.value0s.value0时时, ,表示等待队列无等待该表示等待队列无等待该信号量的进程信号量的进程, ,其值表示还可用的资源数其值表示还可用的资源数目目. .做做V V操作的进程继续执行。操作的进程继续执行。六、信号量的一般应用u1 1、用信号量实现进程互斥、用信号量实现进程互斥要使要使N

42、N个进程互斥使用某临界资源（如打个进程互斥使用某临界资源（如打印机），只要在每个进程的使用临界资源印机），只要在每个进程的使用临界资源的临界区（即程序段）前加的临界区（即程序段）前加P P操作，退出临操作，退出临界区前加界区前加V V操作，并且操作，并且n n个个进程共享一个互进程共享一个互斥信号量斥信号量S,S,初值为初值为1 1（即只允许一个进程进（即只允许一个进程进入临界区）。入临界区）。例例1：进程：进程Pa（分配进程）和（分配进程）和Pb（释放进程）（释放进程）对某一打印机分配表的互斥使用情况，可用信对某一打印机分配表的互斥使用情况，可用信号量实现。设互斥信号量号量实现。设互斥信号量

43、mutex，其初值为，其初值为1。则则Pa和和Pb的临界区代码可按下述方式组织：的临界区代码可按下述方式组织：Pa:P(mutex)分配打印机分配打印机（读写分配表）（读写分配表）V(mutex) Pb:P(mutex)释放打印机释放打印机（读写分配表）（读写分配表）V(mutex) 1: mutex.value-; if (mutex.value0) Block(mutex.L );4: mutex.value+; if (mutex.value=0) wakeup(mutex.L);2: mutex.value-; if (mutex.value0) Block(mutex.L );3:

44、mutex.value+; if (mutex.value=1) Ri:=Ri-1; Aj:=Ri;输出一张票；输出一张票； else 输出输出“票已售完票已售完”； ;/*过程结束过程结束 cobegin P(1),P(2),P(n) coend例例2. 用用PV操作实现航空售票系统中访问余票额的同操作实现航空售票系统中访问余票额的同步与互斥。步与互斥。（该系统中的各进程中该系统中的各进程中“按旅客要求找到按旅客要求找到Aj”、“输出一张票输出一张票”、“输出票已售完输出票已售完”的操作语句的操作语句属于临界区。）属于临界区。）u2 2、用信号量实现进程同步、用信号量实现进程同步u根据信号量

45、的初值，在某个进根据信号量的初值，在某个进程的程序段程的程序段前前加加P P操作，在另一个操作，在另一个的程序段的程序段后后加加V V操作操作例例3 3、有有P1,P2 P1,P2 两进程，必须在两进程，必须在P P1 1执行完执行完S1S1语句后，语句后，P2P2才能执行才能执行S2S2。请用。请用PVPV操作实现同步操作实现同步（需同步的两进程共享信号量（需同步的两进程共享信号量s s，初值为，初值为0 0。）。）P1: S1;V(s);P2: P(s);S2;1: S.value-; if (S.value0) Block(S.L ); 2: S.value+; if (S.value=

46、0) wakeup(S.L); 0: s.value=0,初态初态1: s.value=-1,P2阻塞阻塞2: s.value=0,唤醒唤醒P2例例3 3、有有P1,P2 P1,P2 两进程，必须在两进程，必须在P P1 1执行完执行完S1S1语句后，语句后，P2P2才能执行才能执行S2S2。请用。请用PVPV操作实现同步操作实现同步（需同步的两进程共享信号量（需同步的两进程共享信号量s s，初值为，初值为0 0。）。）P2: P1: S1;V(s); P(s);S2;信号量初值为信号量初值为0，则，则P2不可能不可能先执行，因为执行先执行，因为执行P（s）操作）操作时，时，S=-10而被阻塞

47、。而被阻塞。只有只有P1执行完执行完S1,发出发出V（S）操作使操作使S增增1后，后，P2才能执行才能执行S2例例4 4：供者：供者L1L1将读卡机中的数据放入缓将读卡机中的数据放入缓冲区，用者冲区，用者L2L2从缓冲区中读取数据，用信从缓冲区中读取数据，用信号量机制实现对缓冲区的同步。号量机制实现对缓冲区的同步。缓冲区缓冲区供者供者L1L1用者用者L2L2解：设置两个信号量：解：设置两个信号量：S1S1：表示缓冲区是否空（：表示缓冲区是否空（0 0表示不空，表示不空，1 1表表示空）示空）S2S2：表示缓冲区是否满（：表示缓冲区是否满（0 0表示不满，表示不满，1 1表表示满）示满）置初值：

48、置初值：S1=1,S2=0S1=1,S2=0缓冲区缓冲区供者供者L1,S1=1?L1,S1=1?用者用者L2,S2=1?L2,S2=1?S2=1S2=1S1=1S1=1供者进程供者进程L1： do P（S1） 读入数据至缓冲区读入数据至缓冲区 V（s2）; while（1）用者进用者进L2：Do P（S2）；）； 从缓冲区取出信息从缓冲区取出信息 V（S1） 加工并且存盘加工并且存盘 while(1);置初值：置初值：S1=1,S2=0S1=1,S2=01: S1.value-; if (S1.value0) Block(S1.L );2: S2.value-; if (S2.value0)

49、Block(S2.L );0: s1.value=1,s2.value=0,初态初态 1: s1.value=0,L1进入进入 2: s2.value=-1,阻塞阻塞L23:s2.value=0,唤醒唤醒L2进入，进入，4:s1.value=1,L1进入进入供者进程供者进程L1： Do P（S1） 读入数据至缓冲区读入数据至缓冲区 V（s2）; while（1）用者进用者进L2：Do P（S2）；）； 从缓冲区取从缓冲区取 出信息出信息 V（S1） 加工并且存盘加工并且存盘 while(1);注：虚线箭头为同步通信注：虚线箭头为同步通信例例5 5、客车上的司机和售票员的工作流程、客车上的司机和

50、售票员的工作流程如下图所示：为保证旅客安全，司机与售票如下图所示：为保证旅客安全，司机与售票员应各司其职，为完成同一个运送乘客的任员应各司其职，为完成同一个运送乘客的任务相互配合。请用务相互配合。请用P P、V V操作来实现司机与售操作来实现司机与售票员之间的同步。票员之间的同步。正常行车正常行车到站停车到站停车启动汽车启动汽车售票售票开车门开车门关车门关车门司机进程：司机进程：Void Bus-driver( ) Do P(run);/判断能否开车判断能否开车启动车辆；启动车辆；正常行车；正常行车；到站停车；到站停车； V（Open）;/开门信号增开门信号增1While (1);售票员进程：

51、售票员进程：Void Conductor( )Do 售票；售票；P（Open）;/判断能否开门判断能否开门开启车门；开启车门；等待旅客陆续上车；等待旅客陆续上车；关闭车门；关闭车门；V（run）;/开车信号增开车信号增1 while(1);设两个信号量设两个信号量open表示开门表示开门,run表示开车表示开车;并并设初值设初值open=0（关门）（关门）;run=1（开车），则：（开车），则：1: run.value-; if (run.value0) Block(S1.L );2: open.value-; if (open.value=n) notfull.wait;Bufferin=n

52、extp;In=(in+1) mod n;Count+;If notempty.queue notempty.signal;Entyp get(item) if (count=0) notempty.wait; nextc=bufferout; out=(out+1) mod n; count-; If notfull.queue notfull.signal; csignal(notfull); in=out=0; count=0;共享变量共享变量说明说明放产品放产品过程过程取产品过取产品过程程局部变量置局部变量置初值初值如果缓如果缓冲池已冲池已满，放满，放产品过产品过程入等程入等待队列待队

53、列如果等如果等待取的待取的队列中队列中有进程，有进程，则唤醒则唤醒如无产品如无产品可取，则可取，则该进程进该进程进入等待队入等待队列列如果等如果等待放的待放的队列中队列中有进程，有进程，则唤醒则唤醒Void producer( ) while(1) produce an item in nextp; producer-consumer.put(item); Void consumer( ) while(1) producer-consumer.get(item);Consume the item in nextc; ;Main ( ) Cobegin producer( );consumer(

54、 ); . 三、管程与进程的异同三、管程与进程的异同(1)二者都定义了数据结构。进程定义的是私有二者都定义了数据结构。进程定义的是私有数据结构数据结构PCB,管程定义的是公共数据结构，如管程定义的是公共数据结构，如消息队列。消息队列。 (2)二者都在各自的数据结构上进行有意义的操二者都在各自的数据结构上进行有意义的操作。进程是由顺序程序执行有关操作，管程主作。进程是由顺序程序执行有关操作，管程主要是进行同步操作和初启操作。要是进行同步操作和初启操作。 (3)二者设置的目的不同。进程是为了更好地实二者设置的目的不同。进程是为了更好地实现系统的并发性而设置的，管程是为了解决进现系统的并发性而设置的

55、，管程是为了解决进程的公共变量，为了解决共享资源的互斥使用程的公共变量，为了解决共享资源的互斥使用问题而设置的。问题而设置的。 （4）进程通过调用管程中的过程对共享变量）进程通过调用管程中的过程对共享变量实行操作。此时，该过程就如通常的子程序一实行操作。此时，该过程就如通常的子程序一样被调用而处于被动工作方式，因此，称管程样被调用而处于被动工作方式，因此，称管程为被动成分。与此相对应的进程则处于主动工为被动成分。与此相对应的进程则处于主动工作方式而被称为主动成分。作方式而被称为主动成分。（5）由于进程是主动成分，故进程之间能被）由于进程是主动成分，故进程之间能被并发执行，然而管程是被动成分，管

56、程和调用并发执行，然而管程是被动成分，管程和调用它的进程不能并发执行。它的进程不能并发执行。 （6）进程可由）进程可由“创建创建”而诞生，由而诞生，由“撤消撤消”而消亡，有生命期，管程是操作系统中的固有而消亡，有生命期，管程是操作系统中的固有成分，无需进程创建，也不能为进程所撤消，成分，无需进程创建，也不能为进程所撤消，只能被进程调用。只能被进程调用。3.5 进程通信一、进程通信的概念与类型一、进程通信的概念与类型1 1、概念、概念进程通信指进程之间的信息交换。进程通信指进程之间的信息交换。2 2、类型。依据交换信息量的多少。、类型。依据交换信息量的多少。（1 1）低级通信。如进程的同步与）低

57、级通信。如进程的同步与互斥的信号量机制。特点：互斥的信号量机制。特点：一是效率低一是效率低二是通信对用户不透明。二是通信对用户不透明。（2 2）高级通信。指用户可直接）高级通信。指用户可直接通过操作系统提供的一组通信命令高通过操作系统提供的一组通信命令高效地传送大量数据的一种通信方式。效地传送大量数据的一种通信方式。特点：特点：一是效率高。一是效率高。二是通信对用户透明。二是通信对用户透明。 二、高级通信机制的类型1 1、共享存储器系统、共享存储器系统通信的进程共享某些数据结构或通信的进程共享某些数据结构或共享存储区，进程之间能够通过它们共享存储区，进程之间能够通过它们进行通信。进行通信。（1

58、 1）基于共享数据结构的通信方）基于共享数据结构的通信方式式进程间同步处理由程序员解决。进程间同步处理由程序员解决。（2 2）基于共享存储区的通信方式）基于共享存储区的通信方式2 2、消息传递系统、消息传递系统在消息传递中，进程间的数据在消息传递中，进程间的数据交换以消息为单位。程序员直接利用交换以消息为单位。程序员直接利用系统提供的通信命令（原语）来实现。系统提供的通信命令（原语）来实现。（1 1）直接通信方式。）直接通信方式。发送进程直接将消息发送给接收发送进程直接将消息发送给接收进程并将它挂在接收进程的消息缓进程并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队冲队列上，接收进程从

59、消息缓冲队列取得消息。列取得消息。Send(B,a) id:BSize:5Text:hello发发送送区区a aa a进程进程A AReceive(b) id:ASize:5Text:hello接接收收区区bb进程进程BPCB(B)mq mutexsmSize:5Text: helloNext: 0Sender:A第第1个消息缓冲区个消息缓冲区图图3-22 3-22 消息缓冲通信示意图消息缓冲通信示意图（2 2）间接通信方式。）间接通信方式。发送进程将消息发送到某种中间发送进程将消息发送到某种中间实体中，接收进程从中取得消息。实体中，接收进程从中取得消息。这种中间实体一般为信箱，故也称这种中间

60、实体一般为信箱，故也称之为信箱通信方式。之为信箱通信方式。信箱通信示意图信箱通信示意图进程进程 A A信箱头信箱头sendsendreceivereceive进程进程 B Bsendsendreceivereceive图图3-23 3-23 信箱通信示意图信箱通信示意图3 3、管道通信方式、管道通信方式管道是指用于连接一个读进程和管道是指用于连接一个读进程和一个写进程以实现它们之间通信的一个写进程以实现它们之间通信的共享文件，又称为共享文件，又称为pipepipe文件。文件。管道通信须提供管道通信须提供3 3方面的协调能力：方面的协调能力：（1 1）互斥）互斥（2 2）同步）同步（3 3）对方是否存在）对方是否存在共享文件（管道）通信示意图共享文件（