《os进程同步》PPT课件.ppt

软件技术基础,制作 主讲,段景山,段景山,处理机管理,进程的同步,2,处理机的管理功能分为： 进程的描述 进程的控制 进程的同步 进程的通信 进程的调度,处理机管理,3,第三章 进程的同步与通信,第二篇 操作系统,进程的同步关系,进程的同步原则,信号量,进程的通信,4,进程的同步,进程同步问题的提出 进程异步推进可能造成混乱 混乱可能导致不可再现 进程同步目标,维持进程并发性 以提高系统效率,进程执行异步（断续）,资源的非封闭（共享）,结果不可再现,进程同步,进程间相互合作,资源有效共享,结果可再现,5,进程的同步关系,3.1进程同步的基本概念 进程间的两种主要关系 临界资源与临界区 进程同步必须遵循的原则 3.1.1进程间的两种主要关系 进程间的关系与进程间的独立性 进程间的关系是在进程间相对独立的前提下发展的 独立获得资源 独立调度,6,进程间的同步关系（一）,正常行车,到站停车,开车,售票,开车门,关车门,司机,售票员,合作,合作,检查车况,维持秩序,7,获得打印数据,进程间的同步关系（二）,打印进程1,打印进程2,打印,打印,互斥,获得打印数据,8,进程间的同步关系（三）,计算进程,打印进程,计算结果送到Buffer,从Buffer中取数,Buffer,互斥,完成数据计算,打印,通知打印进程打印,通知计算进程 送下一个数,合作,9,进程间的同步关系,相互合作,竞争资源,司机与售票员,多个打印者,计算者与打印者,正常行车,到站停车,开车,售票,开车门,关车门,司机,售票员,同步,同步,检查车况,维持秩序,11,同步实现初探（二）,打印进程 1,打印进程 2,打印,打印,互斥,获得打印数据,获得打印数据,12,同步实现初探（三）,计算进程,打印进程,计算结果送到Buffer,从Buffer中取数,Buffer,互斥,互斥,向打印进程发信号 通知其从Buffer里取数,Buffer空？,否,是,完成数据计算,打印,向计算进程发信号 通知其向Buffer送数,Buffer空？,否,是,合作,13,进程间的同步关系,进程同步时面临的两种主要关系,相互合作,竞争资源,司机与售票员,多个打印者,计算者与打印者,事件、设备等抽象为资源 对进程间关系的处理变为对资源的访问方式,14,临界资源,3.1.2 临界资源与临界区 (1)临界资源 一次只允许一个进程访问的资源 资源状态为临界：0 或 1 (2)临界区 每个进程用于访问临界资源的那段程序 同类临界区：同类资源的临界区 进入区 退出区,最简单的资源,15,临界区,进入区,临界区,退出区,进入区,临界区,退出区,. .,. .,. .,. .,阻塞等待 资源释放,改变资源 状态,释放资源 唤醒等待进程,进程 1,进程 2,16,同步四原则,3.1.3同步机制应遵循的原则,空闲让进,忙则等待,有限等待,让权等待,17,同步原则,进程同步应遵循的原则 空闲让进 当资源空闲时，应当允许访问资源的进程进入临界区 忙则等待 当资源被占用时，应使申请访问该资源的进程等待，等待使用者归还资源,两个基本原则，必须遵循,18,同步原则,进程同步应遵循的原则 让权等待 在进程等待资源时，从执行态转为阻塞态，应当让出CPU的使用权。系统将把CPU分配给其它进程使用，以提高系统效率 有限等待 系统应保证等待的进程能在有限的时间内获得资源，继续执行，以防止无限等待浪费该进程已占用的资源,19,锁机制,3.1.4 临界资源锁机制 例：商场的试衣间 是互斥资源 是临界资源 是共享资源 每个顾客必须遵循以下过程使用试衣间：,靠锁实现资源的共享管理,观察锁状态,关锁,使用试衣间,开锁,20,锁机制,临界资源锁机制,锁,锁变量L,每个进程必须按照以下过程操作资源,L = 1 关闭状态，资源忙,L = 0 打开状态，资源空闲,抽象,L=1,临界区,L=0,21,锁机制实现,一种简单的锁操作实现,void lock( L ) check: if ( L = = 1 ) goto check; else L = 1; ,void unlock( L ) L = 0; ,22,锁机制实现,check: if ( L = = 1),goto check;,else L = 1;,临界区,L,进程 1,进程 2,unlock( L );,check: if ( L = = 1),goto check;,else L = 1;,临界区,unlock( L );,0,0,0,23,锁操作模型,锁操作的一般模型,Pi： lock( L ) C( i ) unlock( L ) .,Pj： lock( L ) C( j ) unlock( L ) .,C( i )： Pi的临界区,Pi： 进程i,24,出了问题的锁,check: if ( L = = 1),goto check;,else L = 1;,临界区,unlock( L );,check: if ( L = = 1),goto check;,else L = 1;,临界区,unlock( L );,出现问题的锁,进程 1,进程 2,L,0,尚未执行,问题出在？,判断状态后 改变状态前 被打断,25,锁机制实现,关锁操作不可被打断 用原语实现关锁操作 关锁操作在一个指令周期内完成 （1）引入TS的操作 （2）采用“exchange”(swap)指令 利用特殊硬件机制和指令，使关锁操作在一个指令周期内完成 （3）与中断控制相结合实现锁操作 在执行原语过程中关闭中断,软件方法,硬件方法,26,TS锁,TS寄存器，各进程一个,TS 0,L=0？,TS 1,L1,TS0？,1个指令周期内完成,27,锁与中断,通过开、关中断，保证关锁操作不被打断,L=0？,L1,关中断,开中断,开中断,是,否,28,锁操作特点,锁操作的特点： 实现了进程互斥访问临界资源。 不遵循让权等待原则。忙等,29,信号量机制,3.2 进程同步的信号量机制（semaphore） 经典信号量、记录型信号量、信号量集 3.2.1 信号量机制的基本概念 （1）信号量 信号量是对具体物理资源的抽象 不同类的资源用不同名称的信号量代表 同类资源的个数用 0的信号量值表示 信号量值为 0 或 1 的信号量表示临界资源,信号量是比锁更高级的资源抽象方式,30,经典信号量,（2）经典信号量的P，V操作 资源的申请与释放原语,信号量：S,P（s）,s = 0 ?,s = s -1,N,Y,V（s）,s = s + 1,申请一个资源,释放一个 资源,忙等,临界区/资源访问区,31,信号量机制类型,3.2.2三种信号量机制 （1）经典信号量 （2）记录型信号量 （3）信号量集 （4）一般信号量集机制,32,记录型信号量,（2）记录型信号量 引入进程阻塞机制 在信号量里增加对阻塞进程的纪录,typedef struct Semaphore int value; process_list * list; semaphore ;,资源个数,阻塞进程（PCB）队列,33,纪录型信号量的P，V操作,P( s ),s.value = s.value - 1,s .value 0 ?,本进程获得 一个资源,临界区/资源访问区,本进程进入s.list 队列，进入阻塞 状态,N,Y,V( s ),s.value = s.value+1,s .value= 0 ?,将s.list中 第一个进程 唤醒，,N,Y,34,纪录型信号量机制特点： s.value的含义 大于0 等于0 小于0 是否遵循让权等待？ 阻塞队列，阻塞机制,记录型信号量特点,35,纪录型信号量机制特点： 进程对资源访问的过程： 原语保证 p（），v（）操作都是原语 保证不出现“锁不住”资源的现象,记录型信号量特点,P( s ),进入临界区,V( s ),s为0时进程会进入阻塞状态,36,记录型信号量特点,纪录型信号量机制特点： 主动阻塞与被动唤醒,P( s ),s.value = s.value - 1,s .value 0 ?,本进程获得 一个资源,临界区/资源访问区,本进程进入s.list 队列，进入阻塞 状态,N,Y,V( s ),s.value = s.value+1,s .value= 0 ?,将s.list中 第一个进程 唤醒，,N,Y,唤醒后的进程从这里开始,37,信号量集,（3）信号量集 引入原因 基本思想 流程,38,信号量集引入原因,P1（S1）；,P1（S2）；,P2（S2）；,P2（S1）；,进程1,进程2,系统推进过程为,进程2 阻塞,进程1 阻塞,S1,S2,进程1和进程2都无法继续推进出现死锁,。,。,V(S2); V(S1);,V(S1); V(S2);,39,信号量集基本思想,基本思想 将多次对多个信号量的申请改为一次，用一个原子操作完成 进程要么一次获得所有的资源，要么一个也申请不到 不会存在互相等待的局面,信号量集,SP（S1，S2，S3Sn）,40,信号量集流程,信号量集流程,SP（S1，S2，S3Sn）,S11?,S21?,。,S1=S11； S2=S21； Sn=Sn1；,N,N,本进程进入Si1的第一个Si的阻塞队列中， 并将进程的程序指针设到SP（）的开头,41,信号量集流程,信号量集流程,SV（S1，S2，S3Sn）,S1=S11； S2=S21； Sn=Sn1；,将Si队列中第一个 等待进程唤醒,42,信号量集流程,P1（S1）；,P1（S2）；,进程1,P2（S2）；,P2（S1）；,进程2,SP1（S1,S2）,SP2（S1,S2）,SP1（S1,S2）,SP2（S1,S2）,系统推进,SP1（S1,S2）,SP2（S1,S2）,或,43,一般信号量集,（4）一般信号量集 引入原因 更灵活 基本思想 si：各信号量 ti：申请下限 ti 0时，可进行资源预留 di：申请个数 一次可申请一种资源的多个,SP（S1,t1,d1,Sn,tn,dn),44,资源竞争,3.3经典进程同步问题 资源竞争时的进程同步 对竞争资源的互斥访问,P（s）,临界区,V（s）,进程1,进程2,P（s）,临界区,V（s）,P（s）,访问资源,V（s）,状态：,状态：,唤醒,就绪,执行,就绪,执行,阻塞,45,相互合作时的进程同步 保证进程间的前驱、后继关系,相互合作,司机进程,正常行车,到站停车,V（停车）,喝茶,P（关车门）,正常行车,售票,P（停车）,开车门,关车门,V（关车门）,售票,售票员进程,V（s）,P（s）,前驱,后继,信号量初值为0,46,公用与私用信号量,公用信号量：,私用信号量：,一组进程共享，都可进行P、V操作,用于进程间资源的竞争,拥有信号量的进程只对信号量进行P操作,V操作由其他进程进行,用于进程间的合作,P（s）,V（s）,访问资源,P（s）,V（s）,访问资源,进程1：,进程2：,P（s）,V（s）,后继进程：,前驱进程：,47,经典进程同步问题,经典进程同步问题 生产者消费者问题 读者写者问题 哲学家进餐问题,48,生产者消费者问题,3.3.1生产者消费者问题 问题描述: 有多个生产者在生产消息 有多个消费者在消费消息 消费者消费的是生产者生产的消息,49,生产者消费者问题,消息缓冲池 生产者产生的消息放入缓冲池内； 消费者从缓冲池内取走消息消费； 消费者消费后的空白消息块放进空白缓冲池内供生产者使用。,生产者,消费者,消息缓冲池,空白块缓冲池,2,3,1,2,1,50,生产者消费者算法分析,算法分析 两类进程：生产者进程和消费者进程 （1）进程间的关系 生产者生产消息后消费者消费 消费者消费后的空白缓冲块由生产者生产消息,P（s）,V（s）,后继进程：,前驱进程：,P（s）,V（s）,后继进程：,前驱进程：,P（full）,V（full）,生产者：,消费者：,生产者：,消费者：,P（empty）,V（empty）,51,生产者消费者算法分析,（2）队列的操作 两个共享队列： 消息缓冲队列 空白缓冲队列 多个进程共享一个队列 是否需要保护,消息缓冲池,空白块缓冲池,生产者,放入消息,取空白块,生产者,消费者,消费者,取走消息,放空白块,52,生产者消费者算法分析,入队操作,newmsg-next = msglist-head;,msglist-head = newmsg;,msglist-head,newmsg,53,队列操作,同时入队,进程1,进程2,newmsg1-next = msglist-head;,msglist-head = newmsg1;,msglist-head,newmsg1,newmsg2,两个message都挂到了队列上,就绪,执行,就绪,执行,newmsg2-next = msglist-head;,msglist-head = newmsg2;,54,出了问题的队列操作,同时入队,进程1,进程2,newmsg1-next = msglist-head;,msglist-head = newmsg1;,msglist-head,newmsg1,newmsg2,队列操作过程需要互斥进行,就绪,执行,就绪,执行,newmsg2-next = msglist-head;,msglist-head = newmsg2;,55,出了问题的队列操作,同时入队,进程1,进程2,newmsg1-next = msglist-head;,msglist-head = newmsg1;,msglist-head,newmsg1,newmsg2,就绪,执行,就绪,执行,newmsg2-next = msglist-head;,msglist-head = newmsg2;,56,生产者消费者算法分析,进程间的关系 生产者生产消息 后 消费者消费的合作关系 消费者消费 后 的空白缓冲块由生产者生产消息的合作关系 进程间在队列操作上的互斥关系,P（s）,V（s）,访问资源,P（s）,V（s）,访问资源,进程1：,进程2：,P（mutex）,V（mutex）,P（mutex）,V（mutex）,操作队列,操作队列,57,生产者消费者算法分析,信号量 full：私有信号量 empty：私有信号量 mutex：公用信号量 队列 full_list：消息队列 empty_list：空白块队列,58,生产者消费者算法流程,生产者,产生一个消息；,申请一个空白缓冲区；,从空白队列中取一个 空白缓冲区；,在空白缓冲区内填充消息,消息放入消息队列,释放一个消息信号,消费者,申请一个消息,申请队列操作的互斥；,释放队列操作的互斥,从消息队列中取一个消息；,消费消息,将消息清空为空白,空白块放入空白队列,申请队列操作的互斥；,释放队列操作的互斥；,释放一个空白块信号,void producer( ) while( 1 ) create( msg ); P( empty ); P( mutex ); buffer = pop( empty_list )； V( mutex ); fill_buffer( buffer , msg); P( mutex ); push( full_list , buffer); V( mutex ); V( full ); ,semaphore full = 0 , NULL ; semaphore empty = n , NULL;,semaphore mutex = 1 , NULL;,void consumer( ) while( 1 ) P( full ); P( mutex ); msg = pop( full_list )； V( mutex ); consume( msg ); fill_zero( msg ); P( mutex ); push( empty_list , msg); V( mutex ); V( empty ); ,60,生产者消费者算法小结,小结： 在分析进程同步问题中，逐个分析进程间的关系是关键 不管多复杂的关系，总能归结为两种基本关系（竞争与合作），总是这两种关系的组合 不管公用还是私用，信号量的使用必须成对出现,思考,多个生产者之间是什么关系，需要特别的实现吗？,多个消费者之间是什么关系，需要特别的实现吗？,61,读者写者问题,3.3.2读者写者问题 （Reader and Writer ） 问题描述 一个数据纪录，有多个进程进行读操作，另一些进程进行修改操作 （Reader） （Writer） 读写策略 允许多个进程同时进行读操作读不互斥 不允许多于一个进程进行写操作写互斥 不允许读写操作同时进行读写互斥,62,读者写者问题分析,读者,写者,读操作,写操作,p（mutex）,v（mutex）,p（mutex）,v（mutex）,写者之间互斥,读者与写者之间互斥,读者之间,互斥,63,哲学家问题,3.3.3哲学家进餐问题 问题描述 五位哲学家围桌而坐 哲学家在思考问题时不需要任何资源，思考完问题后进入进餐态。 每人必须获得左右两支筷子才能进餐,思考,思考,思考,思考,思考,准备进餐,进餐,准备进餐,进餐,64,哲学家问题分析,死锁,思考,思考,思考,思考,思考,准备进餐,准备进餐,准备进餐,准备进餐,准备进餐,思考,p（left_stick）,p（right_stick),v（right_stick),v（left_stick）,eat,65,管程机制,3.4管程机制（自学） 3.4.1引入原因 过多信号量的使用，容易造成死锁 3.4.2管程的基本概念 把数据及其上的一组操作看作一个整体管程 3.4.3管程组成 局部于管程的局部变量 局部于管程的数据初值设置 在数据上的一组操作,66,管程机制,3.4.4管程实现 各进程必须互斥调用管程 同步原语具有条件变量，以区别不同条件的wait和signal同步操作 3.4.5用管程来实现进程的两种同步关系,