OS4进程管理2同步与互斥

内容纲要上节回顾进程互斥进程同步进程间通信1/14/20251回顾进程的概念进程的控制数据结构进程的状态转换1/14/20252进程的基本状态运行态阻塞态就绪态？1/14/20253进程的基本状态问题1：为什么不能从阻塞态变为运行态呢？问题2：为什么不能从就绪态变为阻塞态呢？问题3：如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？1/14/20254PCB表系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表；PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。PCB表被系统访问的频率很高，因此是全部或部分常驻内存的。操作系统专门开辟一个PCB表区，每个PCB是一片连续的存储单元。PCB表组织方式链接方式索引方式1/14/20255PCB表实现：链接方式链接方式是经常采用的方式。其原理是：按照进程的不同状态分别将其放在不同的队列。Linux操作系统就是应用这种进程控制块组织方式。运行队列指针就绪队列指针PCBPCBPCB0阻塞队列1指针阻塞队列2指针PCB0PCBPCBPCB0PCBPCBPCB0PCB链接队列示意图1/14/20256PCB表实现：索引方式系统根据所有进程的状态建立几张索引表。阻塞索引表就绪索引表执行指针就绪表指针阻塞表指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7

PCB索引结构示意图1/14/20257本讲内容上节回顾进程互斥进程同步进程间通信1/14/20258进程互斥进程的并发特性独立性异步性对有限的资源的共享和竞争引起进程的相互制约临界资源1/14/20259临界资源的概念何谓临界资源？两个或两个以上的进程不能同时使用的资源临界资源实例一些独占设备，如打印机、磁带机等一些共享变量、表格、链表等1/14/202510临界资源的概念何谓临界区？每个进程中访问临界资源的那段代码称为临界区。在临界区前面增加一段用于进行检查的代码，把这段代码称为进入区；相应地，在临界区后面再加一段用于退出临界区的代码，称为退出区。进程中除去上述进入区和退出区，其它部分的代码，称为剩余区。这样，可将一个访问临界资源的进程描述如下：

repeat

进入区；临界区；退出区；剩余区；

untilfalse;1/14/202511互斥执行时必须满足的4条准则不能假设各并发进程的相对执行速度。并发进程中的某个进程不在临界区时，它不能阻止其他进程进入临界区。并发进程中的若干进程申请进入临界区时，只能允许一个进程进入。并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区。准则1、2、3保证并发进程享有平等的、独立的竞争和使用公有资源的权力，并且保证每一个时刻至多只有一个进程在临界区。准则4则是在并发进程不发生死锁的重要保证，否则，由于某个并发进程长期占有临界区，其他进程则因为不能进入临界区而进入相互等待状态。1/14/202512互斥的加锁实现解决思想设定监控变量（lock），通过其值变化控制进程操作进程AWhile(lock!=0)NULL;lock＝1;Critical_region();lock＝0；进程BWhile(lock!=0)NULL;lock=1; Critical_region();lock=0;lock＝0依然存在竞争条件，不能根本解决互斥问题致命缺陷：不具有操作的原子性1/14/202513锁变量的缺陷示例进程AWhile(lock!=0);进程BWhile(lock!=0);lock＝0进程Alock＝1;Critical_Region();进程Block=1; Critical_Region();发生进程调度，互斥的进程开始运行发生进程调度，A并不知道B也进入临界区发生进程调度，B并不知道A也进入临界区1/14/202514互斥的加锁实现缺陷：不能保证同一时间只有一个进程进入临界区解决方法：某些机器在硬件中提供了“testandset”的指令，保证对临界区进入条件的判断(lock!=0)与资源状态的修改操作(lock=1)的不可分离性1/14/202515锁的具体实现方法1：关中断lock(){disableInterupts;}Unlock(){enableInterrupts;}1/14/202516锁的具体实现方法2：原子指令序列

用硬件实现test-and-set指令，涉及从一个内存单元的读出与写入在单处理机上很容易实现可以应用到多处理机上，但要考虑Cache一致性协议，相对复杂一些1/14/202517信号量机制基本概念信号量（Semaphore）：一个整数，表示并发进程可以使用的资源数。Down与Up原语（P/V、S/W原语）Dijkstra于1965年提出Probern和Verhogen原语信号量是一种广义上的“锁”原语：OS以关中断形式实现的不可打断操作1/14/202518信号量与P/V原语基本性质信号量的初值是一个正整数当信号量大于0时，说明“环境安全”，可继续运行当信号量小于0时，说明“互斥等待”，只能阻塞推广到一般情况，信号量可解决复杂的同步互斥问题1/14/202519信号量与P/V原语P原语将信号量sem减1

如果sem减一后小于0，那么将进程加入等待队列1/14/202520信号量与P/V原语V原语将信号量加1，并唤醒等待的进程1/14/202521最基本互斥机制的实现进程Awhile(TRUE){nocritical_region();P(mutex);critical_region();V(mutex);nocritical_region();}int

mutex=1进程Bwhile(TRUE){nocritical_region();P(mutex);critical_region();V(mutex);nocritical_region();}1/14/202522本讲内容上节回顾进程互斥进程同步进程间通信1/14/202523同步问题实例：一并发程序任务：

f,s,t,g:存放记录的内存区域进程Get,Copy,Put完成f到g的记录搬移工作（每次搬一个记录）1/14/202524可能的进程执行顺序1/14/202525合理的进程执行顺序1/14/202526进程同步同步关系分析两个或者多个进程在运行顺序上存在固定的规则由于分时操作系统的不确定性，导致同步关系无法保持必须进行显式的程序控制，保证同步关系的正确1/14/202527同步vs.互斥同步与互斥的差别互斥：体现为排他性，可表现为“0－1”关系同步：体现为时序性，比互斥更加复杂和多变解决思路保证解决办法对互斥和同步的适用性1/14/202528同步的概念进程互斥时执行顺序可以是任意的；同步是相互制约的。直接制约：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。1/14/202529同步的解决办法1私有信号量：这些信号量只与制约进程和被制约进程有关而不是与整组并发进程有关。公有信号量：互斥时使用。1/14/202530同步的解决办法2（P/V原语）图：缓冲区队列1/14/202531生产者－消费者问题分析互斥关系分析任何时刻，只能有一个进程在缓冲区中操作引入互斥信号量（二元信号量）信号量为0，表明已有进程进入临界区；同步关系分析对于“生产者”而言，缓冲区满则应等待引入同步信号量“empty”，为0表示缓冲区满对于“消费者”而言，缓冲区空则应等待引入同步信号量“full”，为0表示缓冲区空1/14/202532生产者－消费者信号量解法Producer进程intitem;While(TRUE){Produce-Item(&item);P(&empty);P(&mutex);Enter-item(item);V(&mutex);V(&full);}＃defineN100typedef

int

semphsemph

mutex=1;semphempty=N;semphfull=0;Comsumer进程intitem;While(TRUE){P(&full);P(&mutex);Remove-item(&item)V(&mutex);V(&empty);Consume-item(item);}思考1：mutex和empty两个信号量之间有什么区别吗？思考2：多信号量的操作顺序有要求吗？1/14/202533本讲内容上节回顾进程互斥进程同步进程间通信1/14/202534进程通信的基本概念进程间的信息交换称为进程通信。进程间的通信分为两种控制信息的传送（低级通信）大量信息的传送（高级通信）1/14/202535低级通信进程的互斥与同步为低级通信方式，相应地，也称wait、signal操作为低级的通信原语。1/14/202536高级通信进程间有时需要传递大量信息来同步相互之间的动作，而不是通过几个共享变量因此，除了基本的同步与互斥之外，为了满足进程间的高级通信需求，OS需要提供更为丰富的进程间通信方式1/14/202537进程间通信的方式主从式会话式消息或邮箱机制共享存储区方式1/14/202538主从式通信的特点主进程可以自由的使用从进程的资源或者数据；从进程的动作受到主进程的控制；主进程和从进程的关系是固定的。例子：终端控制进程和终端进程1/14/202539会话式会话方式中，通信进程双方可分别称为使用进程和服务进程，其中使用进程调用服务进程提供的服务。

使用进程在调用服务前必须得到服务进程许可；

服务进程根据使用进程需求提供服务，但对服务的控制由自身完成；

使用进程和服务进程在通信时有固定连接关系。例子：用户进程和磁盘管理进程之间的通信。1/14/202540消息或邮箱机制无论接收进程是否准备好接收信息，发送进程都将信息送入缓冲区或者信箱。特点：只要存在空缓冲区或者邮箱，发送进程则发送信息；发送进程和接收进程之间没有直接连接关系；发送进程和接收进程之间存在缓冲区或邮箱存放被传送的信息。1/14/202541消息缓冲机制两通信进程之间的关系:在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对该消息缓冲区队列的访问。否则，将引起消息队列的混乱。同理，当接收进程正从消息队列中取消息缓冲区消息时，也应禁止其他进程对该队列的访问。间接制约设置公用信号量:mutex

，其初值为1。当消息缓冲区队列中无消息存在时，接收进程不能接收到任何消息。直接制约设置私用信号量:SM为接收进程的私用信号量，表示等待接收的消息个数，其初值为0。1/14/202542消息缓冲机制进程之间通信的实现:向系统申请一个消息缓冲区将发送区消息m送入新申请的消息缓冲区把消息缓冲区挂入接收进程的消息队列摘下消息队列中的消息n

将消息n从缓冲区复制到接收区释放缓冲区开始结束开始结束临界区P(mutex)V(mutex)临界区P(mutex)V(mutex)P(SM)V(SM)Send(m):Receive(n):1/14/202543邮箱通信邮箱通信的基本思想:邮箱通信是由发送进程申请建立一个与接收进程连接的邮箱,发送进程把消息送往邮箱,接收进程从邮箱取走消息,从而完成进程间信息交换。邮箱由邮箱头和邮箱体组成。其中邮箱头描述邮箱名称、邮箱大小、邮箱方向以及拥有该邮箱的进程名等。邮箱体主要用来存放消息（如图）。设置邮箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制。1/14/