进程间通信与同步.ppt

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