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

软件技术基础软件技术基础制作主讲段景山段景山段景山处理机管理进程的同步1精选课件ppt段景山段景山n n处理机的管理功能分为：处理机的管理功能分为：uu进程的描述进程的描述进程的描述进程的描述uu进程的控制进程的控制进程的控制进程的控制uu进程的同步进程的同步进程的同步进程的同步uu进程的通信进程的通信进程的通信进程的通信uu进程的调度进程的调度进程的调度进程的调度处理机管理处理机管理2精选课件ppt段景山段景山第三章第三章第三章第三章 进程的同步与通信进程的同步与通信进程的同步与通信进程的同步与通信第二篇第二篇第二篇第二篇 操作系统操作系统操作系统操作系统进程的同步关系进程的同步关系进程的同步关系进程的同步关系进程的同步原则进程的同步原则进程的同步原则进程的同步原则信号量信号量信号量信号量进程的通信进程的通信进程的通信进程的通信3精选课件ppt段景山段景山进程的同步进程的同步n n进程同步问题的提出进程同步问题的提出uu进程异步推进可能造成混乱进程异步推进可能造成混乱进程异步推进可能造成混乱进程异步推进可能造成混乱uu混乱可能导致不可再现混乱可能导致不可再现混乱可能导致不可再现混乱可能导致不可再现n n进程同步目标进程同步目标维持进程并发性维持进程并发性维持进程并发性维持进程并发性以提高系统效率以提高系统效率以提高系统效率以提高系统效率进程执行异步（断续）进程执行异步（断续）进程执行异步（断续）进程执行异步（断续）资源的非封闭（共享）资源的非封闭（共享）资源的非封闭（共享）资源的非封闭（共享）结果不结果不结果不结果不可再现可再现可再现可再现进程同步进程同步进程同步进程同步进程间相互合作进程间相互合作进程间相互合作进程间相互合作资源有效共享资源有效共享资源有效共享资源有效共享结果可再现结果可再现结果可再现结果可再现4精选课件ppt段景山段景山进程的同步关系进程的同步关系n n3.13.1进程同步的基本概念进程同步的基本概念进程同步的基本概念进程同步的基本概念uu进程间的两种主要关系进程间的两种主要关系进程间的两种主要关系进程间的两种主要关系uu临界资源与临界区临界资源与临界区临界资源与临界区临界资源与临界区uu进程同步必须遵循的原则进程同步必须遵循的原则进程同步必须遵循的原则进程同步必须遵循的原则n n3.1.13.1.1进程间的两种主要关系进程间的两种主要关系进程间的两种主要关系进程间的两种主要关系uu进程间的关系与进程间的独立性进程间的关系与进程间的独立性进程间的关系与进程间的独立性进程间的关系与进程间的独立性进程间的关系是在进程间相对独立的前提下发进程间的关系是在进程间相对独立的前提下发进程间的关系是在进程间相对独立的前提下发进程间的关系是在进程间相对独立的前提下发展的展的展的展的vv独立获得资源独立获得资源独立获得资源独立获得资源vv独立调度独立调度独立调度独立调度5精选课件ppt段景山段景山进程间的同步关系（一）进程间的同步关系（一）正常行车正常行车正常行车正常行车到站停车到站停车到站停车到站停车开车开车开车开车售票售票售票售票开车门开车门开车门开车门关车门关车门关车门关车门司机司机司机司机售票员售票员售票员售票员合作合作合作合作合作合作合作合作检查车况检查车况检查车况检查车况维持秩序维持秩序维持秩序维持秩序6精选课件ppt段景山段景山获得打印数据获得打印数据获得打印数据获得打印数据进程间的同步关系（二）进程间的同步关系（二）打印进程打印进程打印进程打印进程1 1 1 1打印进程打印进程打印进程打印进程2 2 2 2打印打印打印打印打印打印打印打印互斥互斥互斥互斥获得打印数据获得打印数据获得打印数据获得打印数据7精选课件ppt段景山段景山进程间的同步关系（三）进程间的同步关系（三）计算进程计算进程计算进程计算进程打印进程打印进程打印进程打印进程计算结果送到计算结果送到计算结果送到计算结果送到BufferBuffer从从从从BufferBuffer中取数中取数中取数中取数BufferBuffer互斥互斥互斥互斥完成数据计算完成数据计算完成数据计算完成数据计算打印打印打印打印通知打印进程打印通知打印进程打印通知打印进程打印通知打印进程打印通知计算进程通知计算进程通知计算进程通知计算进程送下一个数送下一个数送下一个数送下一个数合作合作合作合作8精选课件ppt段景山段景山进程间的同步关系进程间的同步关系司机与售票员司机与售票员司机与售票员司机与售票员多个打印者多个打印者多个打印者多个打印者计算者与打印者计算者与打印者计算者与打印者计算者与打印者9精选课件ppt正常行车正常行车正常行车正常行车到站停车到站停车到站停车到站停车开车开车开车开车售票售票售票售票开车门开车门开车门开车门关车门关车门关车门关车门司机司机司机司机售票员售票员售票员售票员同步同步同步同步同步同步同步同步到站停车到站停车到站停车到站停车否否否否是是是是检查车况检查车况检查车况检查车况维持秩序维持秩序维持秩序维持秩序否否否否关车门关车门关车门关车门是是是是10精选课件ppt段景山段景山同步实现初探（二）同步实现初探（二）打印进程打印进程打印进程打印进程 1 1 1 1打印进程打印进程打印进程打印进程 2 2 2 2打印打印打印打印打印打印打印打印互斥互斥互斥互斥获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据打印机可用？打印机可用？打印机可用？打印机可用？设置打印机为不可用设置打印机为不可用设置打印机为不可用设置打印机为不可用是是是是否否否否打印机可用？打印机可用？打印机可用？打印机可用？设置打印机为不可用设置打印机为不可用设置打印机为不可用设置打印机为不可用是是是是否否否否11精选课件ppt段景山段景山同步实现初探（三）同步实现初探（三）计算进程计算进程计算进程计算进程打印进程打印进程打印进程打印进程计算结果送到计算结果送到计算结果送到计算结果送到BufferBuffer从从从从BufferBuffer中取数中取数中取数中取数BufferBuffer互斥互斥互斥互斥互斥互斥互斥互斥向打印进程发信号向打印进程发信号向打印进程发信号向打印进程发信号通知其从通知其从通知其从通知其从BufferBuffer里取数里取数里取数里取数BufferBuffer空？空？空？空？否否否否是是是是完成数据计算完成数据计算完成数据计算完成数据计算打印打印打印打印向计算进程发信号向计算进程发信号向计算进程发信号向计算进程发信号通知其向通知其向通知其向通知其向BufferBuffer送数送数送数送数BufferBuffer空？空？空？空？否否否否是是是是合作合作合作合作12精选课件ppt段景山段景山进程间的同步关系进程间的同步关系n n进程同步时面临的两种主要关系进程同步时面临的两种主要关系司机与售票员司机与售票员多个打印者多个打印者计算者与打印者计算者与打印者事件、设备等抽事件、设备等抽事件、设备等抽事件、设备等抽象为象为象为象为资源资源资源资源对进程间关系的处理变为对对进程间关系的处理变为对对进程间关系的处理变为对对进程间关系的处理变为对资源资源资源资源的访问方式的访问方式的访问方式的访问方式13精选课件ppt段景山段景山临界资源临界资源n n3.1.2 临界资源与临界区临界资源与临界区uu(1)(1)临界资源临界资源临界资源临界资源一次只允许一个进程访问的资源一次只允许一个进程访问的资源一次只允许一个进程访问的资源一次只允许一个进程访问的资源资源状态为临界：资源状态为临界：资源状态为临界：资源状态为临界：0 0 或或或或 1 1uu(2)(2)临界区临界区临界区临界区每个进程用于访问临界资源的那段程序每个进程用于访问临界资源的那段程序每个进程用于访问临界资源的那段程序每个进程用于访问临界资源的那段程序uu同类临界区同类临界区同类临界区同类临界区：同类资源的临界区：同类资源的临界区同类资源的临界区：同类资源的临界区uu进入区进入区进入区进入区uu退出区退出区退出区退出区最简单的资源最简单的资源最简单的资源最简单的资源14精选课件ppt段景山段景山临界区临界区进入区进入区临界区临界区临界区临界区退出区退出区进入区进入区临界区临界区临界区临界区退出区退出区.阻塞等待阻塞等待阻塞等待阻塞等待资源释放资源释放资源释放资源释放改变资源改变资源改变资源改变资源状态状态状态状态释放资源释放资源释放资源释放资源唤醒等待唤醒等待唤醒等待唤醒等待进程进程进程进程进程进程进程进程 1 1进程进程进程进程 2 215精选课件ppt段景山段景山同步四原则同步四原则n n3.1.3同步机制应遵循的原则同步机制应遵循的原则空闲让进空闲让进忙则等待忙则等待有限等待有限等待让权等待让权等待16精选课件ppt段景山段景山同步原则同步原则n n进程同步应遵循的原则进程同步应遵循的原则uu空闲让进空闲让进空闲让进空闲让进当资源空闲时，应当允许访问资源的进程进入当资源空闲时，应当允许访问资源的进程进入当资源空闲时，应当允许访问资源的进程进入当资源空闲时，应当允许访问资源的进程进入临界区临界区临界区临界区uu忙则等待忙则等待忙则等待忙则等待当资源被占用时，应使申请访问该资源的进程当资源被占用时，应使申请访问该资源的进程当资源被占用时，应使申请访问该资源的进程当资源被占用时，应使申请访问该资源的进程等待，等待使用者归还资源等待，等待使用者归还资源等待，等待使用者归还资源等待，等待使用者归还资源两个基本原则，必须遵循两个基本原则，必须遵循两个基本原则，必须遵循两个基本原则，必须遵循17精选课件ppt段景山段景山同步原则同步原则n n进程同步应遵循的原则进程同步应遵循的原则uu让权等待让权等待让权等待让权等待在进程等待资源时，从执行态转为阻塞态，应在进程等待资源时，从执行态转为阻塞态，应在进程等待资源时，从执行态转为阻塞态，应在进程等待资源时，从执行态转为阻塞态，应当让出当让出当让出当让出CPUCPU的使用权。系统将把的使用权。系统将把的使用权。系统将把的使用权。系统将把CPUCPU分配给其分配给其分配给其分配给其它进程使用，以提高系统效率它进程使用，以提高系统效率它进程使用，以提高系统效率它进程使用，以提高系统效率uu有限等待有限等待有限等待有限等待系统应保证等待的进程能在有限的时间内获得系统应保证等待的进程能在有限的时间内获得系统应保证等待的进程能在有限的时间内获得系统应保证等待的进程能在有限的时间内获得资源，继续执行，以防止无限等待浪费该进程资源，继续执行，以防止无限等待浪费该进程资源，继续执行，以防止无限等待浪费该进程资源，继续执行，以防止无限等待浪费该进程已占用的资源已占用的资源已占用的资源已占用的资源18精选课件ppt段景山段景山锁机制锁机制n n3.1.4 临界资源锁机制临界资源锁机制uu例：商场的试衣间例：商场的试衣间例：商场的试衣间例：商场的试衣间是互斥资源是互斥资源是互斥资源是互斥资源是临界资源是临界资源是临界资源是临界资源是共享资源是共享资源是共享资源是共享资源每个顾客必须遵循以下过程使用试衣间：每个顾客必须遵循以下过程使用试衣间：每个顾客必须遵循以下过程使用试衣间：每个顾客必须遵循以下过程使用试衣间：靠锁实现资源的共享管理靠锁实现资源的共享管理靠锁实现资源的共享管理靠锁实现资源的共享管理观察锁状态观察锁状态观察锁状态观察锁状态关锁关锁关锁关锁使用试衣间使用试衣间使用试衣间使用试衣间开锁开锁开锁开锁19精选课件ppt段景山段景山锁机制锁机制n n临界资源锁机制临界资源锁机制锁锁锁锁锁变量锁变量锁变量锁变量L L每个进程必须按照以下过程操作资源每个进程必须按照以下过程操作资源每个进程必须按照以下过程操作资源每个进程必须按照以下过程操作资源L=1 L=1 关闭状态，资源忙关闭状态，资源忙关闭状态，资源忙关闭状态，资源忙L=0 L=0 打开状态，资源空闲打开状态，资源空闲打开状态，资源空闲打开状态，资源空闲抽象抽象抽象抽象L=1L=1临界区临界区临界区临界区L=0L=020精选课件ppt段景山段景山锁机制实现锁机制实现n n一种简单的锁操作实现一种简单的锁操作实现void lock(L)void lock(L)check:check:if(L1)if(L=1)goto check;goto check;elseelseL=1;L=1;void unlock(L)void unlock(L)L=0;L=0;21精选课件ppt段景山段景山锁机制实现锁机制实现.check:if(L=1)check:if(L=1)goto check;goto check;else L=1;else L=1;临界区临界区临界区临界区L L进程进程进程进程 1 1 1 1进程进程进程进程 2 2 2 2unlock(L);unlock(L);.check:if(L=1)check:if(L=1)goto check;goto check;else L=1else L=1;临界区临界区临界区临界区unlock(L);unlock(L);.0 01 10 0 1 1 0 022精选课件ppt段景山段景山锁操作模型锁操作模型n n锁操作的一般模型锁操作的一般模型PiPi：.lock(L)C(i)unlock(L).lock(L)C(i)unlock(L).PjPj：.lock(L)C(j)unlock(L).lock(L)C(j)unlock(L).C(i)：Pi的临界区的临界区Pi：进程进程i23精选课件ppt段景山段景山出了问题的锁出了问题的锁.check:if(L=1)check:if(L=1)goto check;goto check;else L=1;else L=1;临界区临界区临界区临界区unlock(L);unlock(L);.check:if(L=1)check:if(L=1)goto check;goto check;else L=1;else L=1;临界区临界区临界区临界区unlock(L);unlock(L);.出现问题的锁出现问题的锁出现问题的锁出现问题的锁进程进程进程进程 1 1 1 1进程进程进程进程 2 2 2 2L L0 01 1尚未执行尚未执行尚未执行尚未执行问题出在？问题出在？问题出在？问题出在？判断状态后判断状态后判断状态后判断状态后改变状态前改变状态前改变状态前改变状态前被打断被打断被打断被打断24精选课件ppt段景山段景山锁机制实现锁机制实现n n关锁操作不可被打断关锁操作不可被打断uu用原语实现关锁操作用原语实现关锁操作用原语实现关锁操作用原语实现关锁操作uu关锁操作在一个指令周期内完成关锁操作在一个指令周期内完成关锁操作在一个指令周期内完成关锁操作在一个指令周期内完成（1 1）引入）引入）引入）引入TSTS的操作的操作的操作的操作（2 2）采用）采用）采用）采用“exchange”(swap)“exchange”(swap)指令指令指令指令vv利用特殊硬件机制和指令，使关锁操作在一利用特殊硬件机制和指令，使关锁操作在一利用特殊硬件机制和指令，使关锁操作在一利用特殊硬件机制和指令，使关锁操作在一个指令周期内完成个指令周期内完成个指令周期内完成个指令周期内完成（3 3）与中断控制相结合实现锁操作）与中断控制相结合实现锁操作）与中断控制相结合实现锁操作）与中断控制相结合实现锁操作vv在执行原语过程中关闭中断在执行原语过程中关闭中断在执行原语过程中关闭中断在执行原语过程中关闭中断软件方法软件方法软件方法软件方法硬件方法硬件方法硬件方法硬件方法25精选课件ppt段景山段景山TS锁锁n nTS寄存器，各进程一个寄存器，各进程一个TS TS 0 0L=0L=0？TS TS 1 1L L1 1TSTS0 0？1 1个指个指个指个指令周期令周期令周期令周期内完成内完成内完成内完成26精选课件ppt段景山段景山锁与中断锁与中断n n通过开、关中断，保证关锁操作不被打断通过开、关中断，保证关锁操作不被打断L=0L=0？L L1 1关中断关中断关中断关中断开中断开中断开中断开中断开中断开中断开中断开中断是是是是否否否否27精选课件ppt段景山段景山锁操作特点锁操作特点n n锁操作的特点：锁操作的特点：uu实现了进程互斥访问临界资源。实现了进程互斥访问临界资源。实现了进程互斥访问临界资源。实现了进程互斥访问临界资源。uu不遵循让权等待原则。不遵循让权等待原则。不遵循让权等待原则。不遵循让权等待原则。忙等忙等忙等忙等L=0L=0？L L1 1关中断关中断关中断关中断开中断开中断开中断开中断开中断开中断开中断开中断是是是是否否否否28精选课件ppt段景山段景山信号量机制信号量机制n n3.2 进程同步的信号量机制（进程同步的信号量机制（semaphore）uu经典信号量、经典信号量、经典信号量、经典信号量、记录型信号量记录型信号量记录型信号量记录型信号量、信号量集、信号量集、信号量集、信号量集n n3.2.1 信号量机制的基本概念信号量机制的基本概念uu（1 1）信号量）信号量）信号量）信号量信号量是对具体物理资源的抽象信号量是对具体物理资源的抽象信号量是对具体物理资源的抽象信号量是对具体物理资源的抽象不同类的资源用不同名称的信号量代表不同类的资源用不同名称的信号量代表不同类的资源用不同名称的信号量代表不同类的资源用不同名称的信号量代表同类资源的个数用同类资源的个数用同类资源的个数用同类资源的个数用 0 0的信号量值表示的信号量值表示的信号量值表示的信号量值表示信号量值为信号量值为信号量值为信号量值为 0 0 或或或或 1 1 的信号量表示临界资源的信号量表示临界资源的信号量表示临界资源的信号量表示临界资源信号量是比锁更高级的资源抽象方式信号量是比锁更高级的资源抽象方式信号量是比锁更高级的资源抽象方式信号量是比锁更高级的资源抽象方式29精选课件ppt段景山段景山经典信号量经典信号量n n（2）经典信号量的）经典信号量的P，V操作操作uu资源的申请与释放资源的申请与释放资源的申请与释放资源的申请与释放原语原语原语原语信号量：信号量：信号量：信号量：S SP P（s s）s=0?s=0?s=s-1s=s-1N NY YV V（s s）s=s+1s=s+1申请一个资源申请一个资源申请一个资源申请一个资源释放一个释放一个释放一个释放一个资源资源资源资源忙等忙等忙等忙等临界区临界区临界区临界区/资源访问区资源访问区资源访问区资源访问区30精选课件ppt段景山段景山信号量机制类型信号量机制类型n n3.2.2三种信号量机制三种信号量机制uu（1 1）经典信号量经典信号量经典信号量经典信号量uu（2 2）记录型信号量）记录型信号量）记录型信号量）记录型信号量uu（3 3）信号量集）信号量集）信号量集）信号量集uu（4 4）一般信号量集机制）一般信号量集机制）一般信号量集机制）一般信号量集机制31精选课件ppt段景山段景山记录型信号量记录型信号量n n（2）记录型信号量）记录型信号量uu引入进程阻塞机制引入进程阻塞机制引入进程阻塞机制引入进程阻塞机制uu在信号量里增加对阻塞进程的纪录在信号量里增加对阻塞进程的纪录在信号量里增加对阻塞进程的纪录在信号量里增加对阻塞进程的纪录typedef struct Semaphoretypedef struct Semaphoreint value;int value;process_list*list;process_list*list;semaphore;semaphore;资源个数资源个数资源个数资源个数阻塞进程（阻塞进程（阻塞进程（阻塞进程（PCBPCB）队列）队列）队列）队列32精选课件ppt段景山段景山纪录型信号量的纪录型信号量的P，V操作操作P(s)P(s)s.value=s.value-1s.value=s.value-1s.value 0?s.value 0?本进程获得本进程获得本进程获得本进程获得一个资源一个资源一个资源一个资源临界区临界区临界区临界区/资源访问区资源访问区资源访问区资源访问区本进程进入本进程进入本进程进入本进程进入s.lists.list队列，进入阻塞队列，进入阻塞队列，进入阻塞队列，进入阻塞状态状态状态状态N NY YV(s)V(s)s.value=s.value+1s.value=s.value+1s.value=0?s.value=0?将将将将s.lists.list中中中中第一个进程第一个进程第一个进程第一个进程唤醒，唤醒，唤醒，唤醒，N NY Y33精选课件ppt段景山段景山n n纪录型信号量机制特点：纪录型信号量机制特点：uus.values.value的含义的含义的含义的含义大于大于大于大于0 0等于等于等于等于0 0小于小于小于小于0 0uu是否遵循让权等待？是否遵循让权等待？是否遵循让权等待？是否遵循让权等待？阻塞队列，阻塞机制阻塞队列，阻塞机制阻塞队列，阻塞机制阻塞队列，阻塞机制记录型信号量特点记录型信号量特点34精选课件ppt段景山段景山n n纪录型信号量机制特点：纪录型信号量机制特点：uu进程对资源访问的过程：进程对资源访问的过程：进程对资源访问的过程：进程对资源访问的过程：uu原语保证原语保证原语保证原语保证p p（），（），（），（），v v（）操作都是（）操作都是（）操作都是（）操作都是原语原语原语原语保证不出现保证不出现保证不出现保证不出现“锁不住锁不住锁不住锁不住”资源的现象资源的现象资源的现象资源的现象记录型信号量特点记录型信号量特点.P(s).P(s)进入临界区进入临界区进入临界区进入临界区V(s).Vs).s s为为为为0 0时进程会进时进程会进时进程会进时进程会进入阻塞状态入阻塞状态入阻塞状态入阻塞状态35精选课件ppt段景山段景山记录型信号量特点记录型信号量特点n n纪录型信号量机制特点：纪录型信号量机制特点：uu主动阻塞与被动唤醒主动阻塞与被动唤醒主动阻塞与被动唤醒主动阻塞与被动唤醒P(s)P(s)s.value=s.value-1s.value=s.value-1s.value 0?s.value 0?本进程获得本进程获得本进程获得本进程获得一个资源一个资源一个资源一个资源临界区临界区临界区临界区/资源访问区资源访问区资源访问区资源访问区本进程进入本进程进入本进程进入本进程进入slists.list队列，进入阻塞队列，进入阻塞队列，进入阻塞队列，进入阻塞状态状态状态状态N NY YV(s)V(s)s.value=s.value+1s.value=s.value+1s.value=0?s.valueS11?1?S2S21?1?。S1=S1S1=S11 1；S2=S2S2=S21 1；Sn=SnSn=Sn1 1；N NN N本进程进入本进程进入本进程进入本进程进入Si1Si 0ti 0时，可进行资源预留时，可进行资源预留时，可进行资源预留时，可进行资源预留didi：申请个数：申请个数：申请个数：申请个数vv一次可申请一种资源的多个一次可申请一种资源的多个一次可申请一种资源的多个一次可申请一种资源的多个SPSP（S1,t1,d1,Sn,tn,dn)S1,t1,d1,Sn,tn,dn)43精选课件ppt段景山段景山资源竞争资源竞争n n3.3经典进程同步问题经典进程同步问题uu资源竞争时的进程同步资源竞争时的进程同步资源竞争时的进程同步资源竞争时的进程同步对竞争资源的互斥访问对竞争资源的互斥访问对竞争资源的互斥访问对竞争资源的互斥访问P P（s s）临界区临界区临界区临界区V V（s s）进程进程进程进程1 1 1 1进程进程进程进程2 2 2 2P P（s s）临界区临界区临界区临界区V V（s s）P P（s s）访问资源访问资源访问资源访问资源V V（s s）状态：状态：状态：状态：唤醒唤醒唤醒唤醒就绪就绪就绪就绪执行执行执行执行就绪就绪就绪就绪执行执行执行执行阻塞阻塞阻塞阻塞44精选课件ppt段景山段景山uu相互合作时的进程同步相互合作时的进程同步相互合作时的进程同步相互合作时的进程同步保证进程间的前驱、后继关系保证进程间的前驱、后继关系保证进程间的前驱、后继关系保证进程间的前驱、后继关系相互合作相互合作司机进程司机进程司机进程司机进程正常行车正常行车正常行车正常行车到站停车到站停车到站停车到站停车V V（停车）（停车）（停车）（停车）喝茶喝茶喝茶喝茶P P（关车门）（关车门）（关车门）（关车门）正常行车正常行车正常行车正常行车售票售票售票售票P P（停车）（停车）（停车）（停车）开车门开车门开车门开车门关车门关车门关车门关车门V V（关车门）（关车门）（关车门）（关车门）售票售票售票售票售票员进程售票员进程售票员进程售票员进程同步点同步点同步点同步点同步点同步点同步点同步点V V（s s）P P（s s）前驱前驱前驱前驱后继后继后继后继信号量初值为信号量初值为信号量初值为信号量初值为0 045精选课件ppt段景山段景山公用与私用信号量公用与私用信号量公用信号量：公用信号量：私用信号量：私用信号量：一组进程共享，都可进行一组进程共享，都可进行一组进程共享，都可进行一组进程共享，都可进行P P、V V操作操作操作操作用于进程间资源的竞争用于进程间资源的竞争用于进程间资源的竞争用于进程间资源的竞争拥有信号量的进程只对信号量进行拥有信号量的进程只对信号量进行拥有信号量的进程只对信号量进行拥有信号量的进程只对信号量进行P P操作操作操作操作V V操作由其他进程进行操作由其他进程进行操作由其他进程进行操作由其他进程进行用于进程间的合作用于进程间的合作用于进程间的合作用于进程间的合作P P（s s）V V（s s）访问资源访问资源访问资源访问资源P P（s s）V V（s s）访问资源访问资源访问资源访问资源进程进程进程进程1 1：进程进程进程进程2 2：P P（s s）V V（s s）后继进程：后继进程：后继进程：后继进程：前驱进程：前驱进程：前驱进程：前驱进程：46精选课件ppt段景山段景山经典进程同步问题经典进程同步问题n n经典进程同步问题经典进程同步问题uu生产者生产者生产者生产者消费者问题消费者问题消费者问题消费者问题uu读者读者读者读者写者问题写者问题写者问题写者问题uu哲学家进餐问题哲学家进餐问题哲学家进餐问题哲学家进餐问题47精选课件ppt段景山段景山生产者消费者问题生产者消费者问题n n3.3.1生产者生产者消费者问题消费者问题uu问题描述问题描述问题描述问题描述:有多个生产者在生产消息有多个生产者在生产消息有多个生产者在生产消息有多个生产者在生产消息有多个消费者在消费消息有多个消费者在消费消息有多个消费者在消费消息有多个消费者在消费消息消费者消费的是生产者生产的消息消费者消费的是生产者生产的消息消费者消费的是生产者生产的消息消费者消费的是生产者生产的消息48精选课件ppt段景山段景山生产者消费者问题生产者消费者问题uu消息缓冲池消息缓冲池消息缓冲池消息缓冲池生产者产生的消息放入生产者产生的消息放入生产者产生的消息放入生产者产生的消息放入缓冲池内；缓冲池内；缓冲池内；缓冲池内；消费者从缓冲池内取走消费者从缓冲池内取走消费者从缓冲池内取走消费者从缓冲池内取走消息消费；消息消费；消息消费；消息消费；消费者消费后的空白消消费者消费后的空白消消费者消费后的空白消消费者消费后的空白消息块放进空白缓冲池内供息块放进空白缓冲池内供息块放进空白缓冲池内供息块放进空白缓冲池内供生产者使用。生产者使用。生产者使用。生产者使用。生产者生产者生产者生产者消费者消费者消费者消费者消息缓冲池消息缓冲池消息缓冲池消息缓冲池空白块缓冲池空白块缓冲池空白块缓冲池空白块缓冲池2312149精选课件ppt段景山段景山生产者消费者算法分析生产者消费者算法分析n n算法分析算法分析uu两类进程：生产者进程和消费者进程两类进程：生产者进程和消费者进程两类进程：生产者进程和消费者进程两类进程：生产者进程和消费者进程uu（1 1）进程间的关系）进程间的关系）进程间的关系）进程间的关系生产者生产消息后消费者消费生产者生产消息后消费者消费生产者生产消息后消费者消费生产者生产消息后消费者消费消费者消费后的空白缓冲块由生产者生产消息消费者消费后的空白缓冲块由生产者生产消息消费者消费后的空白缓冲块由生产者生产消息消费者消费后的空白缓冲块由生产者生产消息P P（s s）V V（s s）后继进程：后继进程：后继进程：后继进程：前驱进程：前驱进程：前驱进程：前驱进程：P P（s s）V V（s s）后继进程：后继进程：后继进程：后继进程：前驱进程：前驱进程：前驱进程：前驱进程：P P（fullfull）V V（fullfull）生产者：生产者：生产者：生产者：消费者：消费者：消费者：消费者：生产者：生产者：生产者：生产者：消费者：消费者：消费者：消费者：P P（emptyempty）V V（emptyempty）50精选课件ppt段景山段景山生产者消费者算法分析生产者消费者算法分析uu（2 2）队列的操作）队列的操作）队列的操作）队列的操作两个共享队列：两个共享队列：两个共享队列：两个共享队列：vv消息缓冲队列消息缓冲队列消息缓冲队列消息缓冲队列vv空白缓冲队列空白缓冲队列空白缓冲队列空白缓冲队列多个进程共享一个队列多个进程共享一个队列多个进程共享一个队列多个进程共享一个队列vv是否需要保护是否需要保护是否需要保护是否需要保护消息缓冲池消息缓冲池消息缓冲池消息缓冲池空白块缓冲池空白块缓冲池空白块缓冲池空白块缓冲池生产者生产者生产者生产者放入消息放入消息放入消息放入消息取空白块取空白块取空白块取空白块生产者生产者生产者生产者消费者消费者消费者消费者消费者消费者消费者消费者取走消息取走消息取走消息取走消息放空白块放空白块放空白块放空白块51精选课件ppt段景山段景山生产者消费者算法分析生产者消费者算法分析n n入队操作入队操作newmsg-next=msglist-head;newmsg-next=msglist-head;msglist-head=newmsg;msglist-head=newmsg;msglist-headmsglist-headnewmsgnewmsg52精选课件ppt段景山段景山队列操作队列操作n n同时入队同时入队进程进程进程进程1 1进程进程进程进程2 2newmsg1-next=newmsg1-next=msglist-head;msglist-head;msglist-head=msglist-head=newmsg1;newmsg1;msglist-headmsglist-headnewmsg1newmsg1newmsg2newmsg2两个两个两个两个messagemessage都挂到了队列上都挂到了队列上都挂到了队列上都挂到了队列上就绪就绪就绪就绪执行执行执行执行就绪就绪就绪就绪执行执行执行执行newmsg2-next=newmsg2-next=msglisthead;msglist-head;msglist-head=msglist-head=newmsg2;newmsg2;53精选课件ppt段景山段景山出了问题的队列操作出了问题的队列操作n n同时入队同时入队进程进程进程进程1 1进程进程进程进程2 2newmsg1-next=newmsg1-next=msglist-head;msglist-head;msglist-head=msglist-head=newmsg1;newmsg1;msglist-headmsglist-headnewmsg1newmsg1newmsg2newmsg2队列操作过程需要互斥进行队列操作过程需要互斥进行队列操作过程需要互斥进行队列操作过程需要互斥进行就绪就绪就绪就绪执行执行执行执行就绪就绪就绪就绪执行执行执行执行newmsg2-next=newmsg2-next=msglist-head;msglist-head;msglist-head=msglist-head=newmsg2;newmsg2;54精选课件ppt段景山段景山出了问题的队列操作出了问题的队列操作n n同时入队同时入队进程进程进程进程1 1进程进程进程进程2 2newmsg1-next=newmsg1-next=msglist-head;msglist-head;msglist-head=msglist-head=newmsg1;newmsg1;msglist-headmsglist-headnewmsg1newmsg1newmsg2newmsg2就绪就绪就绪就绪执行执行执行执行就绪就绪就绪就绪执行执行执行执行newmsg2-next=newmsg2-next=msglist-head;msglist-head;msglist-head=msglist-head=newmsg2;newmsg2;55精选课件ppt段景山段景山生产者消费者算法分析生产者消费者算法分析n n进程间的关系进程间的关系uu生产者生产消息生产者生产消息生产者生产消息生产者生产消息 后后后后 消费者消费的合作关系消费者消费的合作关系消费者消费的合作关系消费者消费的合作关系uu消费者消费消费者消费消费者消费消费者消费 后后后后 的空白缓冲块由生产者生产消息的空白缓冲块由生产者生产消息的空白缓冲块由生产者生产消息的空白缓冲块由生产者生产消息的合作关系的合作关系的合作关系的合作关系uu进程间在队列操作上的互斥关系进程间在队列操作上的互斥关系进程间在队列操作上的互斥关系进程间在队列操作上的互斥关系P P（s s）V V（s s）访问资源访问资源访问资源访问资源P P（s s）V V（s s）访问资源访问资源访问资源访问资源进程进程进程进程1 1：进程进程进程进程2 2：P P（mutexmutex）V V（mutexmutex）P P（mutexmutex）V V（mutexmutex）操作队列操作队列操作队列操作队列操作队列操作队列操作队列操作队列56精选课件ppt段景山段景山生产者消费者算法分析生产者消费者算法分析n n信号量信号量uufullfull：私有信号量：私有信号量：私有信号量：私有信号量uuemptyempty：私有信号量：私有信号量：私有信号量：私有信号量uumutexmutex：公用信号量：公用信号量：公用信号量：公用信号量n n队列队列uufull_listfull_list：消息队列：消息队列：消息队列：消息队列uuempty_listempty_list：空白块队列：空白块队列：空白块队列：空白块队列57精选课件ppt段景山段景山生产者消费者算法流程生产者消费者算法流程生产者生产者生产者生产者产生一个消息；产生一个消息；产生一个消息；产生一个消息；申请一个空白缓冲区；申请一个空白缓冲区；申请一个空白缓冲区；申请一个空白缓冲区；从空白队列中取一个从空白队列中取一个从空白队列中取一个从空白队列中取一个空白缓冲区；空白缓冲区；空白缓冲区；空白缓冲区；申请队列操作的互斥；申请队列操作的互斥；申请队列操作的互斥；申请队列操作的互斥；释放队列操作的互斥；释放队列操作的互斥；释放队列操作的互斥；释放队列操作的互斥；在空白缓冲区内填充消息在空白缓冲区内填充消息在空白缓冲区内填充消息在空白缓冲区内填充消息消息放入消息队列消息放入消息队列消息放入消息队列消息放入消息队列申请队列操作的互斥；申请队列操作的互斥；申请队列操作的互斥；申请队列操作的互斥；释放队列操作的互斥；释放队列操作的互斥；释放队列操作的互斥；释放队列操作的互斥；释放一个消息信号释放一个消息信号释放一个消息信号释放一个消息信号消费者消费者消费者消费者申请一个消息申请一个消息申请一个消息申请一个消息申请队列操作的互斥；申请队列操作的互斥；申请队列操作的互斥；申请队列操作的互斥；释放队列操作的互斥释放队列操作的互斥释放队列操作的互斥释放队列操作的互斥从消息队列中取一个消息；从消息队列中取一个消息；从消息队列中取一个消息；从消息队列中取一个消息；消