中南大学数学院计算机操作系统第四章课件进程通信.ppt

1、第四章 进程通信,1,2,4.1 进程的同步与互斥,4.1.1 同步与互斥的概念,两个或两个以上的进程要协作完成一个任务，它们之间就要互相配合，需要在某些动作之间进行同步。 进程间另一种关系是互斥，这种关系一般发生在两个或两个以上的进程竞争某些同时只能被一个进程使用的资源的情况下。,3,4.1.2 临界段问题,在一段时间内只能允许一个进程访问的资源称为临界资源，如打印机、磁带机、光盘刻写机、绘图仪等 进程执行的访问临界资源的程序段称为临界段或互斥段。,临界资源与临界段,4,统计两个进程 P1和P2对共享变量count访问计数：,P1： : P2：: R1=count （0） R2=count（

2、1） R1=R1+1 R2=R2+1 count=R1 （1） count=R2 （2） : : 结果：count2,设count初值0,5,两个进程可能的相对执行次序,P1：R1=count （0） R1=R1+1 （1） P2：R2=count （0） R2=R2+1 （1） count=R2 （1） P1：count=R1 （1） 虽然P1和P2进程各自都执行了对count加1的操作段，但结果count只增加1。 因此，变量count就是临界资源，P1、P2访问count的两个程序段就是临界段，诸进程必须互斥地进入临界段。,6,4.2 进程间互斥控制方法,锁可以用于控制临界段的互斥执行。

3、锁有两个状态，一个是打开状态，另一个是关闭状态，故锁可以用布尔变量表示。在C中，锁变量可以定义为char或int类型变量。设x为锁变量，则定义： x = 0 锁的打开状态； 1 锁的关闭状态。,4.2.1 锁的表示和操作,7,当进程希望进入临界段时，首先要测试锁的状态，如锁是打开的，表示无进程处于临界段，那么可以关闭该锁，并进入临界段。 当该进程处于临界段时，其他试图进入临界段的进程由于在测试锁的状态时发现它处于关闭状态，就只能在临界段外等待。,用锁变量控制临界段的执行,8,用锁操作控制进程对临界段的互斥执行,(a),LOCK (x),x=0 ?,x=1,临界段,+,-,UNLOCK (x),

4、临界段,x=0,(b),9,4.2.2 锁的安全控制,锁的关闭操作LOCK包括测试和关闭两个操作步骤，这两个操作步骤涉及临界资源x,故这段程序也是临界段。 假定锁是打开的，当一个进程P1在测试锁的状态后，还没来得及关闭它的一瞬间，发生了中断； 中断返回时，系统可能调度另一个进程P2执行。P2执行时也对该锁的状态进行测试，发觉它处于打开状态，于是关闭该锁，并进入临界段。那么两个进程就同时处于一个临界段之中。,10,1. 测试并设置指令test semWait (products); semWait (buffers); get product from buffers; Put product

5、into buffers; semSignal (buffers) semSignal (products);consume product; ,40,producers: customers: while ( ) while ( ) produce next product; semWait (products); semWait (buffers); semWait (mutex); semWait (mutex); get product from buffers; Put product into buffers; semSignal (mutex); semSignal (mutex

6、); semSignal (buffers) semSignal (products);consume product; ,请仔细推敲semWait、semSignal操作的次序。这些操作的次序安排得不合理，就有可能发生“死锁”。,41,4.4.5 读者写者问题,常会有若干个并发进程对数据对象进行读写的情况。有些进程只要求读数据对象，有些进程则要求修改数据对象。 若干个读者可以同时访问数据对象，不需要互斥也不会产生任何问题，但一个写者不能与任何的读者或者写者同时访问数据对象，否则就可能破坏数据对象的完整性、正确性与一致性。 可将所有的读进程看成是一类的，但写进程必须和任何其他的写进程和读进程类

7、互斥。,42,当有读进程正在访问数据对象时，读进程的个数与互斥要求没有关系。只有当第一个读进程需要对数据对象访问时，才需要执行semWait操作，以判断是否有写进程正在更新数据对象。 只有当最后一个读进程退出访问数据对象的临界段时，才需要执行semSignal操作，以便拆除“路障”，让一个写进程进入。 需要设置一个跟踪正在临界段访问数据对象的读进程个数的全局共享变量count。由于该计数器也是一个临界资源，所以诸进程对它的访问也应当互斥地进行，为此，还要设置另外一个互斥信号灯。,43,解决读者写者问题的算法,信号灯初值：mutex 为1 wrt为1 计数器变量：int count = 0 wr

8、itors: while ( ) semWait(wrt); write information semSignal(wrt); ,44,readers: while ( ) semWait(mutex); if( +count = 1) semWait(wrt); semSignal(mutex); Read information; semWait(mutex); if ( -count = 0 ) semSignal(wrt); semSignal(mutex); ,45,4.5 进程间的数据通信,4.5.1 消息通信,消息通信的基本思想是由系统的消息通信机构统一管理一组空闲的消息缓冲区

9、。 一个进程要向另一个进程发送消息，先要向系统申请一个缓冲区，填写了消息正文和其他有关消息的特征、控制信息后，通过消息通信机构将该消息送到接收其他消息队列中。 接收进程在一个适当时机从消息队列中移出一个消息，读取所有的信息后，再释放消息缓冲区。 一个消息缓冲区的数据结构中除了要包括消息的正文外，一般还要包括其他有关的控制信息。,46,send_pid：发送进程标识 type：消息类型 size：消息长度 next_ptr：下一个消息的指针 text ：消息正文 为了支持消息通信，在进程控制PCB中还要增设有关管理消息的成员，如： hd_ptr ：进程已收到消息的队列首指针 mutex ：对消息

10、队列进行操作的互斥信号灯 ssm ：接收进程和发送进程之间的同步信号灯，其值表示接收进程消息队列中的消息数。,47,发送进程在发送消息之前，先要在进程自己的内存空间中开辟一个发送缓冲区，将消息正文及有关控制信息填入其中，再调用发送消息的系统调用msgsnd(sm_ptr)，其中参数sm-ptr指向进程的发送缓冲区始址。 接收进程在接收消息之前，也先要在进程自己的内存空间中开辟一个接收缓冲区，再调用接收消息的系统调用msgrcv(rm_ptr)，其中参数rm_ptr指向接收缓冲区始址。,msgsnd和msgrcv系统调用,48,4.5.2 共享存储区,共享存储区机制可以把内存中的一个区域连入多个

11、进程的虚地址空间，当一个进程对该地址空间写入数据后，另一个进程就可以从自己所连入的虚地址空间直接读出共享存储区中的数据，就如同进程存取自己的私有数据一样方便。 进程要求分配一个共享存储区时，核心先要按进程提供的关键字值查找系统的共享存储区段表，如已存在指定关键字的共享段，则说明该共享段已先由其他进程创建，只要权限允许，可简单地返回该表项的描述符。,49,共享存储区（续）,如未找到指定关键字的表项，系统就根据进程对共享存储区的大小及存取控制权的要求，分配一个空闲的页表区和空闲的内存块，在共享存储区段表中填入共享段的关键字、大小、共享段的页表始址及存取控制权等信息，并返回该表项的描述符。 接下来进

12、程就可以通过该共享存储区的描述字，将共享存储段映射到进程的虚地址空间。,50,4.5.3 管道通信,管道是一种信息流缓冲机构，它用于连接发送进程和接收进程，以实现它们之间的数据通信。管道以先入先出（FIFO）的方式组织数据的传输。 在发送进程和接收进程之间能传递任意大的信息，但在实现时所开的缓冲区太小是有限的，故当管道写满时，发送进程就被阻塞，只有当接收进程从管道中读出一部或全部信息后，发送进程才能继续向管道写信息。 反之也一样，当接收进程读空管道时，就要等待发送进程继续将信息写入管道。 在UNIX中，管道是以文件为基础，再适当考虑其特殊要求而实现的通信机构。,51,4.6 软中断和信号机构,

13、4.6.1 信号的产生与类型,1. 信号的概念,UNIX提供了一组软中断信号，用于模拟硬件中断，但它们的实现机制是不同的。信号是一取值为119（MAX_SIGS）的某个整数，可以在进程之间传送，用于通知进程发生了某种异常事件，需要执行事先安排好的动作。 进程在运行中的某几个时机要主动通过信号机制检查是否有信号到达，如有，便中断正在执行的程序，转入对应的事件处理程序。 处理完毕，再返回断点执行原先的程序。信号处理过程与硬件中断处理很相似，故称为“软中断”。,52,2. 信号的产生,在UNIX中，主要在以下几种情况下向进程发送软中断信号： 1）在用户态运行时产生了各种软、硬件故障。 2）用户通过键

14、盘按键向与该终端有关的进程发信号 3）进程之间通过系统调用kill传送信号。 信号机构将发给进程的信号存放在该进程proc结构的p_sig项。进程收到信号后并不立即进行处理，只有当进程从核心态即将返回到用户态时，即系统调用、陷入或中断返回时才检查p_sig项，并处理与信号对应的事件。 如一个进程处于较低优先级的睡眠状态，那么系统将唤醒该进程，使其转入就绪状态，并在被调度程序选中，转入执行状态时执行信号处理程序。,53,3. 信号的类型,0 没有收到信号 1 SIGHUP 终止进程 终端线挂断 2 SIGINT 终止进程 在键盘上击“ DELETE”键 7 SIGFPE 产生core 浮点溢出

15、9 SIGKILL 终止进程 无条件终止进程 11 SIGSEGV 产生core 段违例 14 SIGALARM 终止进程 闹钟 15 SIGTERM 终止进程 软件终止 16 SIGUSR1 终止进程 用户自定义 17 SIGUSR2 终止进程 用户自定义 19 SIGPWR 终止进程 电源故障,54,4.6.2 信号的处理方式及设置,1. 信号的处理方式,每一个进程的user结构中有一个长度为NSIG（20）的数组signalNSIG，以信号类型作为该数组的下标索引，元素的值决定了对应信号的处理方式。信号的处理方式有三类 （1）若数组元素值为0，则执行信号机构定义的缺省动作。 （2）若数组

16、元素值为1（或奇数），则忽略该信号，不执行任何动作。 （3）若数组元素值为偶数（函数入口地址），则作为对应信号处理程序的指针。,55,2. 信号处理方式的设置,一个进程在创建时，继承了父进程所有的信号处理方式，也即其signalNSIG各元素的值与父进程完全相同。但此后除了SIGKIL外，信号表中定义的信号处理方式都可以用系统调用signal（sig，func）设置或修改。设置的方法是： int sig； int func（），（*oldptr）（）； : oldptr = signal（sig，func）； : 其中sig为信号类型，取值范围为119，但不包括9（SIGKIL），func为新

17、的信号处理函数，oldptr为函数指针，用于保存系统调用signal返回的信号sig原先处理函数入口地址，以便有必要时可恢复原先的信号处理方式。,56,&newfunc,0,a,oldptr,proc,u.u-signal,进程Pa的图像,图4-9信号处理方式的设置,57,4.6.3 信号的传送,利用信号实施进程间通信的主要方式是使用系统调用kill（pid，sig），其功能是将信号sig传送给由参数pid限定的进程。当： pid为正值时，对应于一个有效的进程标识数，该信号就发送给这个唯一的进程。 pid为0时，将信号发送给受同一终端控制的所有进程。 pid为-1时，将信号发送给与发送进程用户

18、标识数相同的所有进程。 pid -1时，将信号发送给组标识数为pid的绝对值的所有进程。 下面举一个信号机构方法的例子。,58,# include # include main ( ) int status； pid_t pid； void func ( )； signal (SIGUSR1,func)；1 /* 预置信号处理程序 */ if (pid=fork () ) 2 printf (Parent: will send signal.n)；4 kill (pid, SIGUSR1)； 5/* 发送信号 */ wait (& status)； 6/* 等待子进程停止 */ printf

19、(status=%d: Parent finish:n，status)；10 else sleep (10)； 3/* 等待接受信号 */ printf (Child：signal is received.n)；8 exit (0)； 9 ,59,void func () printf (It is signal processing function.n)； 7 ,在程序的开始部分用系统调用设置信号16的处理方式为执行func程序，在父进程用fork创建子进程后，子进程继承了对信号的处理方式。父进程向子进程发送信号后，如子进程处于低优先权睡眠，则将其唤醒。子进程被唤醒后，检查是否收到信号，发

20、现已收到信号，就执行该信号（SIGUSR1）所对应的处理程序func（）。执行完毕后返回，继续执行余下程序段。,60,Solaris的进程通信机制,SPARC处理机为互斥原语实现了有原子性test-and-set语义的内存访问指令。如cas（compare and swap，比较和交换）指令，如果第一个寄存器与内存单元的内容相同，则交换内存单元和第二个寄存器的内容。 锁以几种不同的形式出现。Solaris内核中最常用的是互斥锁，它可以实现对数据的互斥读写访问。此外还有读/写锁，它适用于在同一时刻对同一数据可以有多个读操作，但只能有一个写操作的情况。 在内核的一些部分，如果获取最佳性能是要追求的

21、首要目标，为了提高速度，许多锁代码用汇编语言实现，而不是C语言。,61,Solaris支持System V的三种IPC机制（共享内存、信号量和消息队列），还支持基于套接字的进程间通信机制。同时，Solaris引入了自己独特的IPC机制Solaris门。 Solaris门是一种快速的进程间过程调用，这种类似于远程过程调用的机制允许我们快速地调用其他进程中的方法。 一个进程可以通过创建门而成为门服务器，门是一个函数，在服务器中以线程的形式存在，其他的客户端进程可以调用门。,Solaris门,62,Solaris门服务器会在线程池中创建一个内核线程以等待客户端的调用，只要门线程池中还有空闲的线程，客

22、户端就能马上得到服务，这就使得门函数的调用非常快速。 服务器进程成功创建门时，返回一个门的描述符。门服务器进程通过创建一个门(door_create()来使得该进程中的一个函数可以被客户端的进程所使用。 内核中将门实现为一个伪文件系统doorfs。进程通过门描述符来引用门，门描述符在形式和功能上都与文件描述符相似。服务器必须将创建的门和一个文件系统名字空间的文伴描述符相关联，服务器端是通过调用fattach()来将一个文件系统路径名和门文件描述符相关联的。 一旦关联充成，客户端就可以对该路径名进行打开操作，并且在door_call()使用打开操作返回的文件捕述符来得到一个门的描述符，客户端通过

23、门描述符来找到一个门。,Solaris门,63,Solaris中的信号处理,Solaris中的信号处理是进程级别的，但每个线程可以有自己的信号屏蔽掩码。 线程可以独立于同一进程中执行的其他线程来选择自己要屏蔽的信号，因而在进程执行的不同时刻可以有不同的线程来接收不同的信号。 接口pthread_sigmask()用来建立每个线程的信号屏蔽掩码。进程中的所有线程共享所有信号的处理及处理例程，那么具有默认处理的SIGINT信号（作为例子）的产生将会使整个进程退出。作为异常的结果产生的同步信号（SIGFPE、SIGILL等）将被发送到产生异常的线程本身。 异步信号是所有没有被定义为异常的其他信号，它

24、们将被传递到系统找到的第一个不屏蔽该信号的线程。 信号在数据结构中表示为二进制位，例如设置第16位，SIGURS1（这实际上是位15，位的编号是从0开始的）。,64,4.7 死锁,4.7.1 产生死锁的原因,图4-10 过河的相持,65,当两个进程各占了对方所要的一个资源，就会形成死锁,进程B等待资源R1,资源R1,进程B,进程A,资源R2,进程A占用资源R1,进程A等待资源R2,进程B占用资源R2,图4-11两个进程的死锁,66,系统资源可分为两类，一类是可重复使用的永久性资源，另一类是会被消耗的临时性资源。可重复用的资源在使用后不会减少资源。进程在释放了可重用资源后，该资源又可被其他进程再

25、次使用。可重用的资源有处理机、主存、暂存、I/O通道、打印机以及文件、数据库等。 可重用的资源又可分为可剥夺的资源和不可剥夺的资源。最典型的可剥夺的资源是处理机。最普通的不可剥夺的资源是打印机，当系统把这类资源分配给进程后，只能在使用完毕后由进程自愿释放，系统不能强行收回。 涉及到可重用资源的死锁例子是：一个进程占用了打印机，又要申请磁带机，另一个进程占用了磁带机，又要申请打印机，这样每个进程都占用并保持了一个资源，并等待对方所占用的资源时就发生了死锁。,67,4.7.2 产生死锁的条件,同时具备下列三个静态的必要条件时，才有可能产生死锁。 (1) 互斥执行 每次只能允许一个进程占有和使用一个

26、资源，其他申请该资源的进程被阻塞。 (2) 保持并等待 当进程等待分配给它新的资源时，保持占有已分配的资源。 (3) 不可剥夺 不能强迫移去进程占有的未使用完的资源。 上述这三个条件是产生死锁的必要条件，但即使存在全部这三个条件也不一定会发生死锁。要产生死锁必须存在第四个动态条件： (4) 循环等待 存在一个闭合的进程资源链，以致每一个进程至少占有链中下一个进程所需要的一个资源。,68,4.7.3 死锁的预防,1互斥执行 一般说，第一个条件是不能排除的，如果存取一个资源需要互斥执行，那么操作系统就要支持互斥执行。某些资源，例如文件，可以允许多个用户同时读，但对写只能互斥地进行。就是在这个情况，

27、如果一个以上的进程需要进行写操作，就可能发生死锁。 2保持和等待 保持和等待条件是能预防的，只要进程一次申请它所需要的所有的资源，在所有的需要同时满足以前，阻塞自己。,69,有几种方法可预防这个条件。一个方法是，如占有某些资源的进程不能获得进一步的资源，该进程必须释放原先所占有的资源；如果需要，以后再申请这些资源。 另外的方法是，如果一个进程需要申请当前正被其他进程占用的资源，操作系统就要求后者释放它所占用的这类资源。这种预防死锁的方法只能用在后申请资源的进程优先级较高的情况下。 只有当资源的状态容易保存和便于以后恢复的情况下，这种方法才是实际可行的。处理机就是这类资源的例子，如剥夺像打印机那

28、样的资源，就会使输出变得杂乱无章、毫无意义。但借助spooling技术可将独享设备改为虚拟的共享设备，就能破坏本条件，预防死锁。,3不可剥夺,70,4循环等待 采用有序资源使用法可以防止循环等待条件。如果一个进程已经分配了类型R的资源，那么以后它只能申请在资源顺序表中排在R后面的资源类型。,1,2,3,4,5,数,模,转,换,器,磁,带,机,光,刻,机,绘,图,仪,71,五个哲学家吃通心面,P1: 思考 semWait(f1) 取 f1 semWait (f2) 取 f2 吃通心面 放下f1,f2 semSignal(f1) semSignal(f2),p1,f1,f2,p2,f3,f4,f5

29、,p3,p4,p5,P5: 思考 semWait (f5) 取 f5 semWait (f1) 取 f1 吃通心面 放下f5,f1 semSignal (f5) semSignal (f1),.,72,五个哲学家吃通心面,P1: 思考 semWait(f1) 取 f1 semWait (f2) 取 f2 吃通心面 放下f1,f2 semSignal(f1) semSignal(f2),p1,f1,f2,p2,f3,f4,f5,p3,p4,p5,P5: 思考 semWait (f1) 取 f5 semWait (f5) 取 f1 吃通心面 放下f5,f1 semSignal (f5) semSi

30、gnal (f1),.,73,4.7.4 死锁的避免,死锁避免的方法允许三个死锁的必要条件都存在，但要动态地进行审慎的判断，以保证运行不会到达死锁这一点上。避免死锁主要有以下两个判断和处理时机： (1) 进程启动时判断 如果对资源的要求会导致死锁，就不启动有关进程。这种方法仅仅在当前所有进程对资源的最大请求加上启动进程对资源的请求都满足的情况下，才能启动新进程，故这种避免死锁的策略不会是最优的，因为它假定的是最坏情况，即所有进程都同时需要最大数量的资源。 (2) 资源分配时判断 如果对资源的分配会导致死锁，就暂不允许进一步为进程分配资源。,74,分配资源时，申请者要把同类资源的最大需求量告诉系

31、统，如系统现存的可用资源数能满足申请者剩余需求量时，就满足当前的部分或全部申请，否则就推迟分配。 这样至少保证有一个申请者能得到所需的全部资源，可执行到结束，然后释放资源供别的申请者使用。 如果系统保证申请者在有限的时间内能获得所需的全部资源，则称系统处于安全状态，否则称系统处于不安全状态，并有可能引起死锁。银行家算法是在能确保系统处于安全状态时才把资源分配给申请者。,银行家算法,75,例: 有8个资源供三个进程共享，它们的最大需求数分别为6、4、7。在某一时刻，资源的分配情况如下所示： 最大需求 当前占有 还要申请 P0624 P1422 P2716 系统剩余数3 这时，系统处于安全状态，因

32、为剩余的资源可以先供进程P1使用，P1运行结束后将释放所占全部资源，这样系统剩余资源数变为5，又可保证P0的全部申请得到满足。等到P0归还所占资源后，就可满足P2的申请。如此系统存在着一个安全的资源分配序列。,76,但在上述的状态中，如果P0要申请2个（而不是1个）资源，系统就不能立即分配给它，而要推迟到一个适当的时机再实施分配过程，否则系统资源的分配情况将变为： 最大需求当前占有还要申请 P0642 P1422 P2716 系统剩余数1 这种状态是不安全的，因为剩余的资源数已不能满足任何一个进程还要申请的资源数，如此就可能形成死锁。,77,4.7.5 死锁的检测,死锁的预防策略是非常保守的，

33、它是靠限制对资源的存取及进程的并发执行程度来实施的。 与其相反，死锁检测策略不减少对资源的存取或限制进程的并发运行。使用死锁检测，只要可能，就将所申请的资源分配给进程。操作系统定期地执行检查算法，以判断是否存在条件4的循环等待链。,78,资源分配表,资源等待表,状态图和状态表,79,4.7.6 死锁的解除,下面列举了一些解除死锁的方法。 强迫撤销所有的死锁进程。 将每一个死锁进程退回到一些以前定义的“检查站”，再启动进程。这需要系统支持进程的回退和重启动机制。 逐个撤销死锁进程，直至死锁不存在。终止死锁进程的次序应当基于最小代价的标准。每终止一个进程后就调用死锁检测算法，以判定死锁是否还存在。 相继地剥夺进程所占的资源，直至死锁不再存在。同样，剥夺资源的次序应基于成本方面的考虑。被剥夺资源的进程必需回退到获得该资源之前的某个执行点上。,80,4.9 Solaris的进程通信机制,SPARC处理机为互斥原语实现了有原子性test-and-set语义的内存访问指令。如cas（compare and swap，比较和交换）指令，如果第一个寄存器与内存单元的内容相同，则交换内存单元和第二个寄存器的内容。 锁以几种不同的形式出现。Solaris内核中最常用的是互斥锁，它可以实现对数据的互斥读写访问。此外还有