清华大学操作系统讲义第03讲_进程间通信

1、1第第 三三 讲讲操作系统与系统编操作系统与系统编程程谌谌 卫卫 军军清华大学软件学院清华大学软件学院2004年春季年春季2第二章第二章 进程管理进程管理进程（进程（Process）线程（线程（Thread）进程间通信进程间通信经典的经典的IPC问题问题进程间高级通信进程间高级通信进程调度进程调度32.3 进程间通信进程间通信进程间通信（进程间通信（InterProcess Communi-cation，IPC）：进程之间的信息交流）：进程之间的信息交流与协调。与协调。 如果两个并发运行的进程之间没有任何关联关系如果两个并发运行的进程之间没有任何关联关系 （直接的或间接的），那么无须通信；（直

2、接的或间接的），那么无须通信； 如果两个并发运行的进程之间存在着某种关联关如果两个并发运行的进程之间存在着某种关联关 系（直接的或间接的），那么可能需要通信。例系（直接的或间接的），那么可能需要通信。例 如：两个进程使用相同的一个共享文件。如：两个进程使用相同的一个共享文件。4需要讨论的问题：需要讨论的问题： 进程间如何来通信呢，如何来相互传递信息呢？进程间如何来通信呢，如何来相互传递信息呢？ 当两个或多个进程在进行一些关键性的临界活动当两个或多个进程在进行一些关键性的临界活动 时（如对共享资源的访问），如何确保它们不会时（如对共享资源的访问），如何确保它们不会 相互妨碍相互妨碍 进程互斥进程

3、互斥问题；问题； 当进程之间存在着某种依存关系时，如何来调整当进程之间存在着某种依存关系时，如何来调整 它们的运行次序它们的运行次序 进程同步进程同步问题。问题。问题问题2和和3是是目标目标，问题，问题1是是手段手段。问题。问题2和和3同样适同样适用于线程，相同的问题，相同的解决方案。用于线程，相同的问题，相同的解决方案。52.3.1 进程的互斥进程的互斥【例子】【例子】 后台打印程序后台打印程序（两个进程同时想要访问共享数据）（两个进程同时想要访问共享数据）后台程序后台程序4 7share.txt进程间传递信进程间传递信息的一种方式息的一种方式.6 4 7 share.txtnext_fre

4、e_slot = in; / 7第一步：进程第一步：进程A中中断断next_free_slot = in; / 7第二步：进程第二步：进程Bprog.n678file_bwrite “file_b” to item 7next_free_slot +; / 8update in; 8第三步：进程第三步：进程Awrite “file_a” to item 7next_free_slot +; / 8update in; file_aoutin7竞争状态（竞争状态（race condition）：）：两个或多个进程对同一共享数据同时进行读写两个或多个进程对同一共享数据同时进行读写操作，而最后的结果

5、是不可预测的，它取决于操作，而最后的结果是不可预测的，它取决于各个进程具体运行情况。各个进程具体运行情况。解决之道：解决之道：在同一时刻，只允许一个进程访问该共享数据，在同一时刻，只允许一个进程访问该共享数据，即如果当前已有一个进程正在使用该数据，那么即如果当前已有一个进程正在使用该数据，那么其他进程暂时不能访问。这就是其他进程暂时不能访问。这就是互斥互斥的概念。的概念。8竞争状态问题的抽象描述竞争状态问题的抽象描述把一个进程在运行过程中所做的事情分为两类：把一个进程在运行过程中所做的事情分为两类：o 进程内部的计算或其他的一些事情，肯定不会进程内部的计算或其他的一些事情，肯定不会 导致竞争状

6、态的出现；导致竞争状态的出现；o 对共享内存或共享文件的访问，可能会导致竞对共享内存或共享文件的访问，可能会导致竞 争状态的出现。我们把完成这类事情的那段程争状态的出现。我们把完成这类事情的那段程 序称为序称为“临界区临界区”，把需要互斥访问的共享资源，把需要互斥访问的共享资源 称为称为“临界资源临界资源”。如果我们能设计出某种方法，使得任何两个进程如果我们能设计出某种方法，使得任何两个进程都不会同时出现在临界区中，就可以避免竞争状都不会同时出现在临界区中，就可以避免竞争状态的出现。态的出现。9实现互斥访问的四个条件实现互斥访问的四个条件任何两个进程都不能同时进入临界区；任何两个进程都不能同时

7、进入临界区；不能事先假定不能事先假定CPU的个数和运行速度；的个数和运行速度；当一个进程运行在它的临界区外面时，当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区；不能妨碍其他的进程进入临界区；任何一个进程进入临界区的要求应该在任何一个进程进入临界区的要求应该在有限时间内得到满足。有限时间内得到满足。10基于临界区的互斥访问基于临界区的互斥访问（本图摘自（本图摘自Andrew S. Tanenbaum： “Modern Operating Systems”，下同），下同）112.3.2 基于占线等待的互斥实现基于占线等待的互斥实现方法1. 关闭中断o 把关闭中断的权力授予用户进程，

8、是很不聪明把关闭中断的权力授予用户进程，是很不聪明 的。而且假设系统有多个的。而且假设系统有多个CPU，则此法无效；，则此法无效；o 对内核进程而言，是一种方便有效的办法。对内核进程而言，是一种方便有效的办法。结论：适用于内核进程，但不适用于用户进程，不结论：适用于内核进程，但不适用于用户进程，不能作为一种普遍适用的互斥实现方法。能作为一种普遍适用的互斥实现方法。当一个进程进入临界区后，关闭所有的中断；当当一个进程进入临界区后，关闭所有的中断；当它退出临界区时，再打开中断。它退出临界区时，再打开中断。12方法2. 加锁标志位法lock的初始值为的初始值为0，当一个进程想进入临界区时，当一个进程

9、想进入临界区时，先查看先查看lock的值，若为的值，若为1，说明已有进程在临界区，说明已有进程在临界区内，只好循环等待。等它变成了内，只好循环等待。等它变成了0，才可进入。，才可进入。while ( lock );lock = 1;临界区临界区lock = 0;共享变量共享变量进程间传递信息进程间传递信息的又一种方式。的又一种方式。缺点：可能出现针对缺点：可能出现针对lock的竞争状态问题。的竞争状态问题。13方法3. 强制轮流法基本思想：每个进程严格地按照轮流的顺序来基本思想：每个进程严格地按照轮流的顺序来进入临界区。进入临界区。while ( turn != 0 );临界区临界区turn

10、= 1;非临界区非临界区共享变量共享变量优点：保证在任何时刻最多只有一个进程在临界区优点：保证在任何时刻最多只有一个进程在临界区缺点：违反了互斥访问四条件中的第三个条件缺点：违反了互斥访问四条件中的第三个条件while ( turn != 1 );临界区临界区turn = 0;非临界区非临界区process 0process 114方法4. Peterson方法当一个进程想进入临界区时，先调用当一个进程想进入临界区时，先调用enter_region函数，判断是否能安全进入，不能的话等待；当它函数，判断是否能安全进入，不能的话等待；当它从临界区退出后，需调用从临界区退出后，需调用leave_re

11、gion函数，允许其函数，允许其它进程进入临界区。两个函数的参数均为进程号。它进程进入临界区。两个函数的参数均为进程号。enter_region ( 0 );临界区临界区leave_region ( 0 );非临界区非临界区enter_region ( 1 );临界区临界区leave_region ( 1 );非临界区非临界区process 0process 115Peterson方法（续）#define FALSE 0#define TRUE 1#define N 2/ 进程的个数进程的个数int turn;/ 轮到谁？轮到谁？int interestedN;/ 兴趣数组，初始值均为兴趣数组

12、，初始值均为FALSEvoid enter_region ( int process)/ process = 0 或或 1 int other;/ 另外一个进程的进程号另外一个进程的进程号 other = 1 - process; interestedprocess = TRUE; / 表明本进程感兴趣表明本进程感兴趣 turn = process;/ 设置标志位设置标志位 while( turn = process & interestedother = TRUE);16Peterson方法（续）void leave_region ( int process) interestedp

13、rocess = FALSE; / 本进程已离开临界区本进程已离开临界区Peterson算法解决了互斥访问的问题，而且算法解决了互斥访问的问题，而且克服了强制轮流法的缺点，可以完全正常地克服了强制轮流法的缺点，可以完全正常地工作。工作。17方法5. TSL指令加锁标志位法的缺点在于可能加锁标志位法的缺点在于可能出现针对共享变量出现针对共享变量 lock 的竞争的竞争状态。例如，当进程状态。例如，当进程 0 执行完执行完循环判断语句后，被时钟中断循环判断语句后，被时钟中断打断，从而可能使多个进程同打断，从而可能使多个进程同时进入临界区。时进入临界区。while ( lock );lock = 1

14、;临界区临界区lock = 0;加锁标志位法加锁标志位法能不能把查询能不能把查询lock变量与修改变量与修改lock变量这两个操作变量这两个操作捆绑在一起，使它们不会被打断？这就是硬件上的捆绑在一起，使它们不会被打断？这就是硬件上的TSL（Test and Set Lock）指令。）指令。18TSL指令（续）TSL RX, LOCKTSL指令指令该指令读入内存变量该指令读入内存变量LOCK的值，保存在寄存器的值，保存在寄存器RX中，然后存放一个非零值到中，然后存放一个非零值到LOCK当中。在读、写当中。在读、写操作之间不可分隔。操作之间不可分隔。enter_region: TSL REGIST

15、ER, LOCK CMP REGISTER, #0 JNE enter_region RETleave_region: MOVE LOCK, #0 RET19小结以上的各种方法，都是基于占线等待以上的各种方法，都是基于占线等待(busy waiting)的策略，都可归纳为一种形式：当一个进程想要进的策略，都可归纳为一种形式：当一个进程想要进入它的临界区时，首先检查一下是否允许它进入，入它的临界区时，首先检查一下是否允许它进入，若允许，就直接进入了；若不允许，就在那里循环若允许，就直接进入了；若不允许，就在那里循环地等待，一直等到允许它进入。地等待，一直等到允许它进入。缺点：缺点：1）浪费）浪费

16、CPU时间；时间；2）可能导致预料之外）可能导致预料之外 的结果。的结果。202.3.3 阻塞和唤醒原语阻塞和唤醒原语原语原语：通常由若干条语句组成，用来实现某个特定：通常由若干条语句组成，用来实现某个特定的操作。通过一段不可分割或不可中断的程序来实的操作。通过一段不可分割或不可中断的程序来实现其功能。原语是操作系统核心的一个组成部分，现其功能。原语是操作系统核心的一个组成部分，必须在管态下执行。原语的不可中断性是通过在其必须在管态下执行。原语的不可中断性是通过在其执行过程中关闭中断来实现的。执行过程中关闭中断来实现的。o sleep（阻塞原语）：把当前进程由运行状态转换（阻塞原语）：把当前进

17、程由运行状态转换 为阻塞状态，直到另外一个进程唤醒它；为阻塞状态，直到另外一个进程唤醒它； wakeup（唤醒原语）：把一个被阻塞的进程唤（唤醒原语）：把一个被阻塞的进程唤 醒。它有一个参数，即将被唤醒的进程。醒。它有一个参数，即将被唤醒的进程。21while (TestAndSet (lock);临界区临界区lock = FALSE;非临界区非临界区基于占线等待策略的方法基于占线等待策略的方法 浪费浪费CPU时间时间while (TestAndSet (lock) sleep( );临界区临界区lock = FALSE;wakeup(); / 唤醒被阻塞的进程唤醒被阻塞的进程(如果有如果有)

18、非临界区非临界区基于阻塞、唤醒原语的方法基于阻塞、唤醒原语的方法 22现有的进程互斥问题形式：两个或多个进程都想现有的进程互斥问题形式：两个或多个进程都想进入各自的临界区，但在任何时刻，只允许一个进入各自的临界区，但在任何时刻，只允许一个进程进入临界区。进程进入临界区。新的进程互斥问题形式：两个或多个进程都想进新的进程互斥问题形式：两个或多个进程都想进入各自的临界区，但在任何时刻，只允许入各自的临界区，但在任何时刻，只允许 N 个进个进程同时进入临界区（程同时进入临界区（N 1）。）。232.3.4 信号量（信号量（Semaphore） 1965年由著名的荷兰计算机科学家年由著名的荷兰计算机科

19、学家Dijkstra提出，提出， 其基本思路是用一种新的变量类型（其基本思路是用一种新的变量类型（semaphore） 来记录当前可用资源的数量。来记录当前可用资源的数量。 有两种实现方式：有两种实现方式：1）semaphore的取值必须大于的取值必须大于 或等于或等于0。0表示当前已没有空闲资源，而正数表表示当前已没有空闲资源，而正数表 示当前空闲资源的数量；示当前空闲资源的数量；2）semaphore的取值可的取值可 正可负，负数的绝对值表示正在等待进入临界区正可负，负数的绝对值表示正在等待进入临界区 的进程个数。的进程个数。 信号量是由操作系统来维护的，用户进程只能通信号量是由操作系统来

20、维护的，用户进程只能通 过初始化和两个标准原语（过初始化和两个标准原语（P、V原语）来访问。原语）来访问。 初始化可指定一个非负整数，即空闲资源总数。初始化可指定一个非负整数，即空闲资源总数。24 P、V原语作为操作系统内核代码的一部分，是一原语作为操作系统内核代码的一部分，是一 种不可分割的原子操作（种不可分割的原子操作（atomic action），在其），在其 运行时，不会被时钟中断所打断；运行时，不会被时钟中断所打断； P、V原语包含有进程的阻塞和唤醒机制，因此原语包含有进程的阻塞和唤醒机制，因此 在进程等待进入临界区时不会浪费在进程等待进入临界区时不会浪费CPU时间；时间； P原语：

21、原语：P是荷兰语是荷兰语Proberen（测试）的首字母。（测试）的首字母。 申请一个空闲资源（把信号量减申请一个空闲资源（把信号量减1），若成功，），若成功， 则退出；若失败，则该进程被阻塞；则退出；若失败，则该进程被阻塞； V原语：原语：V是荷兰语是荷兰语Verhogen（增加）的首字母。（增加）的首字母。 释放一个被占用的资源（把信号量加释放一个被占用的资源（把信号量加1），如果），如果 发现有被阻塞的进程，则选择一个唤醒之。发现有被阻塞的进程，则选择一个唤醒之。25信号量和P、V原语的实现信号量结构体类型的定义信号量结构体类型的定义typedef struct int count;/

22、计数变量计数变量 struct PCB *queue;/ 进程等待队列进程等待队列 semaphore;26P原语：申请一个资源原语：申请一个资源P( semaphore S) -S.count;/表示申请一个资源表示申请一个资源; if (S.count 0)/表示没有空闲资源表示没有空闲资源; 该进程进入等待队列该进程进入等待队列S.queue末尾末尾; 阻塞该进程阻塞该进程; 27 V原语：释放一个资源原语：释放一个资源V( semaphore S) +S.count;/表示释放一个资源表示释放一个资源; if (S.count = 0) /表示有进程被阻塞表示有进程被阻塞; 从等待队列

23、从等待队列S.queue中取出一个进程中取出一个进程; 把该进程改为就绪状态，插入就绪队列把该进程改为就绪状态，插入就绪队列 28利用信号量来实现进程互斥semaphore mutex；mutex.count = 1;/ N = 1P(mutex);临界区临界区V(mutex);非临界区非临界区292.3.5 进程的同步进程的同步【例子【例子1】 司机与售票员司机与售票员while(上班时间上班时间) 发动汽车；发动汽车； 正常运行；正常运行； 到站停车；到站停车；while(上班时间上班时间) 关闭车门；关闭车门； 售票；售票； 打开车门；打开车门；公车司机公车司机售票员售票员只有关闭车门以

24、后，才能启动汽车；只有停车以只有关闭车门以后，才能启动汽车；只有停车以后，才能打开车门。后，才能打开车门。30【例子【例子2】 三个并发进程的读写三个并发进程的读写 getget进程负责从输入序列进程负责从输入序列f f中读取字符，送到缓中读取字符，送到缓冲区冲区s s中；中； copycopy进程把缓冲区进程把缓冲区s s中的数据复制到缓冲区中的数据复制到缓冲区t t； putput进程从缓冲区进程从缓冲区t t中取出数据打印。中取出数据打印。输入缓冲区输入缓冲区输出缓冲区输出缓冲区31有有6种可能的操作顺序，只有一种结果是正确的。种可能的操作顺序，只有一种结果是正确的。fstg结果初始状态3,4,.,m22(1,2)g,