《第03讲_进程间通信与同步.ppt》由会员分享，可在线阅读，更多相关《第03讲_进程间通信与同步.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第二章第二章 进程管理进程管理1.进程（进程（Process）2.线程（线程（Thread）3.进程间通信与同步进程间通信与同步4.经典的经典的IPC问题问题5.进程调度进程调度22.3 进程间通信与同步进程间通信与同步进程间通信（进程间通信（InterProcess Communi-cation，IPC）：进程之间的信息交流）：进程之间的信息交流与协调。与协调。并发进程之间的两种关系：并发进程之间的两种关系：相互独立：进程之间没有任何关联关系（直接的相互独立：进程之间没有任何关联关系（直接的或间接的），仅有或间接的），仅有CPU竞争关系。无需通信，由竞争关系。无需通信，由进程调度器来协调（
2、如进程调度器来协调（如Word、MP3）；）；相互关联：进程之间存在着某种关联关系（直接相互关联：进程之间存在着某种关联关系（直接或间接），需要相互通信。例如：共享内存变量、或间接），需要相互通信。例如：共享内存变量、共享软硬件资源、数据传递、协同工作等。共享软硬件资源、数据传递、协同工作等。3需要讨论的问题：需要讨论的问题：进程间如何通信呢，如何来相互传递信息呢？进程间如何通信呢，如何来相互传递信息呢？当两个或多个进程在访问共享资源时，如何确保当两个或多个进程在访问共享资源时，如何确保它们不会相互妨碍它们不会相互妨碍 进程互斥进程互斥问题；问题；当进程之间存在着某种依存关系时，如何来调整当进
3、程之间存在着某种依存关系时，如何来调整它们运行的先后次序它们运行的先后次序 进程同步进程同步问题。问题。生活中的例子：教室座位、打饭窗口；一组同学生活中的例子：教室座位、打饭窗口；一组同学做大作业。做大作业。上述问题是否也适用于线程？上述问题是否也适用于线程？42.3.1 进程间通信方式进程间通信方式低级通信：低级通信：只能传递状态和整数值（控只能传递状态和整数值（控制信息）制信息）信号量（信号量（semaphore）信号（信号（signal）高级通信：高级通信：能够传送任意数量的数据能够传送任意数量的数据共享内存（共享内存（shared memory）消息传递（消息传递（message pa
4、ssing）管道（管道（pipe）能否共享内存单元（变量或缓冲区）？能否共享内存单元（变量或缓冲区）？5共享内存共享内存绝大多数现代的操作系统都提供了相应的方法，来绝大多数现代的操作系统都提供了相应的方法，来让各个进程共享它们地址空间当中的某些部分，即让各个进程共享它们地址空间当中的某些部分，即共享内存共享内存。在共享内存中，可以任意读写和使用任。在共享内存中，可以任意读写和使用任意的数据结构（缓冲区）。意的数据结构（缓冲区）。一组进程向共享内存中写，另一组进程从共享内存一组进程向共享内存中写，另一组进程从共享内存中读，通过这种方式实现两组进程间的信息交换。中读，通过这种方式实现两组进程间的信
5、息交换。6消息传递消息传递消息：由若干数据位组成；消息：由若干数据位组成；消息传递：进程之间通过发送和接收消息来交换消息传递：进程之间通过发送和接收消息来交换信息；信息；消息机制由消息机制由OS来维护，包括定义寻址方式、认证来维护，包括定义寻址方式、认证协议、消息的大小等。一般提供两个操作：协议、消息的大小等。一般提供两个操作：send()，发送一条消息；，发送一条消息；receive()，接收一条消息。，接收一条消息。如果两个任务如果两个任务P和和Q想要进行通信，它们需要想要进行通信，它们需要在两者之间建立一个通信链路；在两者之间建立一个通信链路；使用使用send()和和receive()交
6、换信息。交换信息。7管道（管道（pipe）管道通信由管道通信由UNIX首创，由于其有效性，后来的首创，由于其有效性，后来的一些系统相继引入了管道技术；一些系统相继引入了管道技术；管道通信以文件系统为基础，所谓管道即连接两管道通信以文件系统为基础，所谓管道即连接两个进程之间的一个打开的共享文件，专用于进程个进程之间的一个打开的共享文件，专用于进程之间的数据通信；之间的数据通信；发送进程从管道的一端写入数据流，接收进程从发送进程从管道的一端写入数据流，接收进程从管道的另一端按先进先出的顺序读出数据流；管道的另一端按先进先出的顺序读出数据流；管道的读写操作即为文件操作管道的读写操作即为文件操作fwr
7、ite/fread，数据，数据流的长度和格式没有限制。流的长度和格式没有限制。82.3.2 进程的互斥进程的互斥进程互斥的产生原因：进程互斥的产生原因：进程宏观上并发执行，依靠时钟中断来实现进程宏观上并发执行，依靠时钟中断来实现微观上轮流执行；微观上轮流执行；访问共享资源。访问共享资源。9【例子例子1】后台打印程序后台打印程序（两个进程同时想要访问共享数据）（两个进程同时想要访问共享数据）后台程序后台程序4 7share.txt10 4 7 share.txtnext_free_slot=in;/7第一步：进程第一步：进程A中中断断next_free_slot=in;/7第二步：进程第二步：进
8、程Bprog.n678file_bwrite“file_b”to item 7next_free_slot+;/8update in;8第三步：进程第三步：进程Awrite“file_a”to item 7next_free_slot+;/8update in;file_aoutin11【例子例子2】两个进程，读修改写两个进程，读修改写进程进程1 进程进程2tmp1=count;tmp2=count;tmp1+;tmp2=tmp2+2;count=tmp1;count=tmp2;请问：如果在这些进程执行之前，请问：如果在这些进程执行之前，count变量的变量的值为值为1，那么它最后的结果是多少
9、，那么它最后的结果是多少？12进程进程1 进程进程2tmp1=count;(=1)interrupt.tmp2=count;(=1)tmp2=tmp2+2;(=3)count=tmp2;(=3)tmp1+;(=2)count=tmp1;(=2)情形113进程进程1 进程进程2 tmp2=count;(=1)interrupt.tmp1=count;(=1)tmp1+;(=2)count=tmp1;(=2)tmp2=tmp2+2;(=3)count=tmp2;(=3)情形214进程进程1 进程进程2tmp1=count;(=1)tmp1+;(=2)count=tmp1;(=2)tmp2=coun
10、t;(=2)tmp2=tmp2+2;(=4)count=tmp2;(=4)情形315竞争状态（竞争状态（race condition）：）：两个或多个进程对同一共享数据同时进行读写两个或多个进程对同一共享数据同时进行读写操作，而最后的结果是不可预测的，它取决于操作，而最后的结果是不可预测的，它取决于各个进程具体运行情况。各个进程具体运行情况。解决之道：解决之道：在同一时刻，只允许一个进程访问该共享数据，在同一时刻，只允许一个进程访问该共享数据，即如果当前已有一个进程正在使用该数据，那么即如果当前已有一个进程正在使用该数据，那么其他进程暂时不能访问。这就是其他进程暂时不能访问。这就是互斥互斥的概
11、念。的概念。16竞争状态问题的抽象描述竞争状态问题的抽象描述把一个进程在运行过程中所做的事情分为两类：把一个进程在运行过程中所做的事情分为两类：进程内部的计算或其他的一些事情，肯定不会进程内部的计算或其他的一些事情，肯定不会 导致竞争状态的出现；导致竞争状态的出现；对共享内存或共享文件的访问，可能会导致竞对共享内存或共享文件的访问，可能会导致竞 争状态的出现。我们把完成这类事情的那段程争状态的出现。我们把完成这类事情的那段程 序称为序称为“临界区临界区”，把需要互斥访问的共享资，把需要互斥访问的共享资源源 称为称为“临界资源临界资源”。如果我们能设计出某种方法，使得任何两个进如果我们能设计出某
12、种方法，使得任何两个进程程都不会同时出现在临界区中，就可以避免竞争状都不会同时出现在临界区中，就可以避免竞争状态的出现。态的出现。17实现互斥访问的四个条件实现互斥访问的四个条件1.任何两个进程都不能同时进入临界区；任何两个进程都不能同时进入临界区；2.不能事先假定不能事先假定CPU的个数和运行速度；的个数和运行速度；3.当一个进程运行在它的临界区外面时，当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区；不能妨碍其他的进程进入临界区；4.任何一个进程进入临界区的要求应该在任何一个进程进入临界区的要求应该在有限时间内得到满足。有限时间内得到满足。18基于临界区的互斥访问基于临界区的
13、互斥访问（本图摘自（本图摘自Andrew S.Tanenbaum：“Modern Operating Systems”，下同），下同）19如何实现进程之间的互斥访问？如何实现进程之间的互斥访问？问题描述：两个进程，在各自临界区中需问题描述：两个进程，在各自临界区中需要对某个共享资源进行访问。要对某个共享资源进行访问。非临界区；非临界区；临界区；临界区；非临界区；非临界区；进程进程P1非临界区；非临界区；临界区；临界区；非临界区；非临界区；进程进程P2202.3.3 基于关闭中断的互斥实现基于关闭中断的互斥实现进程的切换是由中断引发的，关闭中断后，进程的切换是由中断引发的，关闭中断后，CPU不会
14、被分配给其他进程，其他进程无法执行；不会被分配给其他进程，其他进程无法执行；操作系统内核经常使用这种方法来更新内部的数操作系统内核经常使用这种方法来更新内部的数据结构（变量、链表等）。据结构（变量、链表等）。当一个进程进入临界区后，关闭所有的中断；当当一个进程进入临界区后，关闭所有的中断；当它退出临界区时，再打开中断。它退出临界区时，再打开中断。21问题：问题：如果进程在临界区中执行大量的计算，结如果进程在临界区中执行大量的计算，结果会如何？果会如何？这种方法能否用于用户进程？这种方法能否用于用户进程？这种方法能否用在多这种方法能否用在多CPU的系统中？的系统中？22方法1.加锁标志位法loc
15、k的初始值为的初始值为0，当一个进程想进入临界区时，当一个进程想进入临界区时，先查看先查看lock的值，若为的值，若为1，说明已有进程在临界区，说明已有进程在临界区内，只好循环等待。等它变成了内，只好循环等待。等它变成了0，才可进入。，才可进入。while (lock);lock =1;临界区临界区lock =0;共享变量共享变量缺点：可能出现针对缺点：可能出现针对lock的竞争状态问题。的竞争状态问题。2.3.4 基于繁忙等待的互斥实现基于繁忙等待的互斥实现23方法2.强制轮流法基本思想：每个进程严格地按照轮流的顺序来基本思想：每个进程严格地按照轮流的顺序来进入临界区。进入临界区。while
16、 (turn!=0);临界区临界区turn =1;非临界区非临界区共享变量共享变量优点：保证在任何时刻最多只有一个进程在临界区优点：保证在任何时刻最多只有一个进程在临界区缺点：违反了互斥访问四条件中的第三个条件缺点：违反了互斥访问四条件中的第三个条件while (turn!=1);临界区临界区turn =0;非临界区非临界区process 0process 124方法3.Peterson方法当一个进程想进入临界区时，先调用当一个进程想进入临界区时，先调用enter_region函数，判断是否能安全进入，不能的话等待；当它函数，判断是否能安全进入，不能的话等待；当它从临界区退出后，需调用从临界区
17、退出后，需调用leave_region函数，允许其函数，允许其它进程进入临界区。两个函数的参数均为进程号。它进程进入临界区。两个函数的参数均为进程号。enter_region (0);临界区临界区leave_region (0);非临界区非临界区enter_region (1);临界区临界区leave_region (1);非临界区非临界区process 0process 125Peterson方法（续）#define FALSE 0#define TRUE 1#define N 2/进程的个数进程的个数int turn;/轮到谁？轮到谁？int interestedN;/兴趣数组，初始值均为
18、兴趣数组，初始值均为FALSEvoid enter_region(int process)/process=0 或或 1 int other;/另外一个进程的进程号另外一个进程的进程号 other =1 -process;interestedprocess =TRUE;/表明本进程感兴趣表明本进程感兴趣 turn =process;/设置标志位设置标志位 while(turn=process&interestedother=TRUE);26Peterson方法（续）void leave_region(int process)interestedprocess =FALSE;/本进程已离开临界区
19、本进程已离开临界区Peterson算法解决了互斥访问的问题，而且算法解决了互斥访问的问题，而且克服了强制轮流法的缺点，可以完全正常地克服了强制轮流法的缺点，可以完全正常地工作。工作。27方法4.TSL指令加锁标志位法的缺点在于可能加锁标志位法的缺点在于可能出现针对共享变量出现针对共享变量 lock 的竞争的竞争状态。例如，当进程状态。例如，当进程 0 执行完执行完循环判断语句后，被时钟中断循环判断语句后，被时钟中断打断，从而可能使多个进程同打断，从而可能使多个进程同时进入临界区。时进入临界区。while (lock);lock =1;临界区临界区lock =0;加锁标志位法加锁标志位法能不能把
20、查询能不能把查询lock变量与修改变量与修改lock变量这两个操作变量这两个操作捆绑在一起，使它们不会被打断？这就是硬件上的捆绑在一起，使它们不会被打断？这就是硬件上的TSL（Test and Set Lock）指令。）指令。28TSL指令（续）TSL RX,LOCKTSL指令指令该指令读入内存变量该指令读入内存变量LOCK的值，保存在寄存器的值，保存在寄存器RX中，然后存放一个中，然后存放一个非零值非零值到到LOCK当中。当中。TSL是一是一个原子操作，即不可分隔的操作。个原子操作，即不可分隔的操作。Intel x86系列：系列：BTS(Bit Test and Set)指令。指令。问题：如
21、何使用问题：如何使用TSL指令来实现进指令来实现进程间互斥？程间互斥？29TSL指令（续）enter_region:TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RETleave_region:MOVE LOCK,#0 RET使用使用LOCK来作为加锁标志位，协调各个进程对来作为加锁标志位，协调各个进程对共享资源的访问；共享资源的访问；当当LOCK为为0时，任何进程均可使用时，任何进程均可使用TSL指令把它指令把它设置为非设置为非0，进而访问共享资源；，进而访问共享资源；当当LOCK为非为非0时，循环等待；时，循环等待；在退出临界区时，把
22、在退出临界区时，把LOCK置为置为0。30小结以上的各种方法，都是基于繁忙等待以上的各种方法，都是基于繁忙等待(busy waiting)的策略，都可归纳为一种形式：当一个进程想要进的策略，都可归纳为一种形式：当一个进程想要进入它的临界区时，首先检查一下是否允许它进入，入它的临界区时，首先检查一下是否允许它进入，若允许，就直接进入了；若不允许，就在那里循环若允许，就直接进入了；若不允许，就在那里循环地等待，一直等到允许它进入。地等待，一直等到允许它进入。缺点：缺点：1）浪费）浪费CPU时间；时间；2）可能导致预料之外）可能导致预料之外的结果（如：的结果（如：一个低优先级进程位于临界区中，一个低
23、优先级进程位于临界区中，这时有一个高优先级的进程也试图进入临界区这时有一个高优先级的进程也试图进入临界区）31一个低优先级的进程正在临界区中；一个低优先级的进程正在临界区中；另一个高优先级的进程就绪了；另一个高优先级的进程就绪了；调度器把调度器把CPU分配给高优先级的进程；分配给高优先级的进程；该进程也想进入临界区；该进程也想进入临界区；高优先级进程将会循环等待，直到低优先级高优先级进程将会循环等待，直到低优先级进程退出临界区；进程退出临界区；低优先级进程无法获得低优先级进程无法获得CPU，无法离开临界，无法离开临界区。区。怎么办？怎么办？32解决之道：解决之道：当一个进程无法进入临界区时，应
24、该被阻塞当一个进程无法进入临界区时，应该被阻塞起来（起来（sleep）；）；当一个进程离开临界区时，需要去唤醒当一个进程离开临界区时，需要去唤醒（wake up）被阻塞的进程；）被阻塞的进程；克服了繁忙等待方法的两个缺点（浪费克服了繁忙等待方法的两个缺点（浪费CPU时间、可能死锁）。时间、可能死锁）。如何实现这种阻塞和唤醒机制？如何实现这种阻塞和唤醒机制？33现有的进程互斥问题形式：两个或多个进程都想现有的进程互斥问题形式：两个或多个进程都想进入各自的临界区，但在任何时刻，只允许一个进入各自的临界区，但在任何时刻，只允许一个进程进入临界区。进程进入临界区。新的进程互斥问题形式：两个或多个进程都
25、想进新的进程互斥问题形式：两个或多个进程都想进入各自的临界区，但在任何时刻，只允许入各自的临界区，但在任何时刻，只允许 N 个进个进程同时进入临界区（程同时进入临界区（N 1）。）。342.3.4 信号量（信号量（Semaphore）1965年由著名的荷兰计算机科学家年由著名的荷兰计算机科学家Dijkstra提出，提出，其基本思路是用一种新的变量类型（其基本思路是用一种新的变量类型（semaphore）来记录当前可用资源的数量。来记录当前可用资源的数量。有两种实现方式：有两种实现方式：1）semaphore的取值必须大于的取值必须大于 或等于或等于0。0表示当前已没有空闲资源，而正数表表示当前
26、已没有空闲资源，而正数表 示当前空闲资源的数量；示当前空闲资源的数量；2）semaphore的取值可的取值可 正可负，负数的绝对值表示正在等待进入临界区正可负，负数的绝对值表示正在等待进入临界区 的进程个数。的进程个数。信号量是由操作系统来维护的，用户进程只能通信号量是由操作系统来维护的，用户进程只能通 过初始化和两个标准过初始化和两个标准原语原语（P、V原语）来访问。原语）来访问。初始化可指定一个非负整数，即空闲资源总数。初始化可指定一个非负整数，即空闲资源总数。35 P、V原语作为操作系统内核代码的一部分，是一原语作为操作系统内核代码的一部分，是一 种不可分割的原子操作（种不可分割的原子操
27、作（atomic action），在其），在其 运行时，不会被时钟中断所打断；运行时，不会被时钟中断所打断；P、V原语包含有进程的阻塞和唤醒机制，因此原语包含有进程的阻塞和唤醒机制，因此 在进程等待进入临界区时不会浪费在进程等待进入临界区时不会浪费CPU时间；时间；P原语：原语：P是荷兰语是荷兰语Proberen（测试）的首字母。（测试）的首字母。申请一个空闲资源（把信号量减申请一个空闲资源（把信号量减1），若成功，），若成功，则退出；若失败，则该进程被阻塞；则退出；若失败，则该进程被阻塞；V原语：原语：V是荷兰语是荷兰语Verhogen（增加）的首字母。（增加）的首字母。释放一个被占用的资源
28、（把信号量加释放一个被占用的资源（把信号量加1），如果），如果 发现有被阻塞的进程，则选择一个唤醒之。发现有被阻塞的进程，则选择一个唤醒之。36信号量和P、V原语的实现信号量结构体类型的定义信号量结构体类型的定义typedef struct int count;/计数变量计数变量 struct PCB*queue;/进程等待队进程等待队列列 semaphore;37P原语：申请一个资源原语：申请一个资源P(semaphore S)-S.count;/表示申请一个资源表示申请一个资源;if(S.count 0)/表示没有空闲资源表示没有空闲资源;该进程进入等待队列该进程进入等待队列S.queue
29、末尾末尾;阻塞该进程阻塞该进程;38 V原语：释放一个资源原语：释放一个资源V(semaphore S)+S.count;/表示释放一个资源表示释放一个资源;if(S.count=0)/表示有进程被阻塞表示有进程被阻塞;从等待队列从等待队列S.queue中取出一个进程中取出一个进程;把该进程改为就绪状态，插入就绪队列把该进程改为就绪状态，插入就绪队列 39Windows 2000CreateSemaphore（创建信号量）（创建信号量）WaitForSingleObject（P操作）操作）ReleaseSemaphore（V操作）操作）COS-IIosSemCreate（创建信号量）（创建信号量）osSemPend（P操作）操作）osSemPost（V操作）操作）40利用信号量来实现进程互斥int count;/共享变量（临界资源）共享变量（临界资源）semaphore mutex；/互斥信号量，初始化为互斥信号量，初始化为1非临界区非临界区P(mutex);临界区临界区V(mutex);非临界区非临界区P1非临界区非临界区P(mutex);临界区临界区V(mutex);非临界区非临界区P2非临界区非临界区P(mutex);临界区临界区V(mutex);非临界区非临界区P3