《《进程的同步》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《进程的同步》PPT课件.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.1 2.1 进程的概念进程的概念2.2 2.2 进程控制进程控制2.3 2.3 进程同步进程同步2.4 2.4 进程通信进程通信2.5 2.5 线程线程第2章进程管理2.3进程的同步进程的同步进程的引入虽然改善了系统的资源利用率和提高了系统的吞吐量，但是进程的异步性，特别是它们在争用临界资源时，会给系统造成一定的混乱。为了解决这个问题，提出了进程同步的概念。程序（间）并发执行的特征：程序运行时独占资源程序程序程序程序a aN=3;N=3;print(N)print(N)N=N+1N=N+1print(N)print(N)K=5;K=5;print(K)print(K)K=K+1K=K+1p
2、rint(K)print(K)程序程序程序程序b b顺序执行顺序执行顺序执行顺序执行 a b a b打印结果：打印结果：打印结果：打印结果：3 4 5 63 4 5 6并发执行并发执行并发执行并发执行 a b a b1 12 23 34 45 56 67 78 81 12 23 34 45 56 67 78 8打印结果：打印结果：打印结果：打印结果：3 5 4 63 5 4 6资源非封闭资源非封闭资源非封闭资源非封闭进程的同步进程同步问题的提出进程异步推进可能造成混乱混乱可能导致不可再现进程同步目标维持进程并发性维持进程并发性维持进程并发性维持进程并发性以提高系统效率以提高系统效率以提高系统效
3、率以提高系统效率进程执行异步（断续）进程执行异步（断续）进程执行异步（断续）进程执行异步（断续）资源的非封闭（共享）资源的非封闭（共享）资源的非封闭（共享）资源的非封闭（共享）结果不结果不结果不结果不可再现可再现可再现可再现进程同步进程同步进程同步进程同步进程间相互合作进程间相互合作进程间相互合作进程间相互合作资源有效共享资源有效共享资源有效共享资源有效共享结果可再现结果可再现结果可再现结果可再现进程间的两种主要关系进程间的关系与进程间的独立性进程间的关系是在进程间相对独立的前提下发展的独立获得资源独立调度进程间的同步关系（一）正常行车正常行车正常行车正常行车到站停车到站停车到站停车到站停车开
4、车开车开车开车售票售票售票售票开车门开车门开车门开车门关车门关车门关车门关车门司机司机司机司机售票员售票员售票员售票员合作合作合作合作合作合作合作合作检查车况检查车况检查车况检查车况维持秩序维持秩序维持秩序维持秩序获得打印数据获得打印数据获得打印数据获得打印数据进程间的同步关系（二）打印进程打印进程打印进程打印进程1 1 1 1打印进程打印进程打印进程打印进程2 2 2 2打印打印打印打印打印打印打印打印互斥互斥互斥互斥获得打印数据获得打印数据获得打印数据获得打印数据进程间的同步关系（三）计算进程计算进程计算进程计算进程打印进程打印进程打印进程打印进程计算结果送到计算结果送到计算结果送到计算结
5、果送到BufferBuffer从从从从BufferBuffer中取数中取数中取数中取数BufferBuffer互斥互斥互斥互斥完成数据计算完成数据计算完成数据计算完成数据计算打印打印打印打印通知打印进程打印通知打印进程打印通知打印进程打印通知打印进程打印通知计算进程通知计算进程通知计算进程通知计算进程送下一个数送下一个数送下一个数送下一个数合作合作合作合作进程间的同步关系司机与售票员司机与售票员司机与售票员司机与售票员多个打印者多个打印者多个打印者多个打印者计算者与打印者计算者与打印者计算者与打印者计算者与打印者？其他例子？其他例子流水线生产流水线生产流水线生产流水线生产仓库仓库仓库仓库 两个
6、队篮球比赛两个队篮球比赛两个队篮球比赛两个队篮球比赛两种形式的制约关系间接相互制约关系 -源于资源共享,产生互斥问题直接相互制约关系 -源于进程间合作,产生同步问题正常行车正常行车正常行车正常行车到站停车到站停车到站停车到站停车开车开车开车开车售票售票售票售票开车门开车门开车门开车门关车门关车门关车门关车门司机司机司机司机售票员售票员售票员售票员同步同步同步同步同步同步同步同步到站停车到站停车到站停车到站停车否否否否是是是是检查车况检查车况检查车况检查车况维持秩序维持秩序维持秩序维持秩序否否否否关车门关车门关车门关车门是是是是同步实现初探（二）打印进程打印进程打印进程打印进程 1 1 1 1打
7、印进程打印进程打印进程打印进程 2 2 2 2打印打印打印打印打印打印打印打印互斥互斥互斥互斥获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据获得打印数据打印机可用？打印机可用？打印机可用？打印机可用？设置打印机为不可用设置打印机为不可用设置打印机为不可用设置打印机为不可用是是是是否否否否打印机可用？打印机可用？打印机可用？打印机可用？设置打印机为不可用设置打印机为不可用设置打印机为不可用设置打印机为不可用是是是是否否否否同步实现初探（三）计算进程计算进程计算进程计算进程打印进程打印进程打印进程打印进程计算结果送到计算结果送到计算结果送到计算结果送到Buff
8、erBuffer从从从从BufferBuffer中取数中取数中取数中取数BufferBuffer互斥互斥互斥互斥互斥互斥互斥互斥向打印进程发信号向打印进程发信号向打印进程发信号向打印进程发信号通知其从通知其从通知其从通知其从BufferBuffer里取数里取数里取数里取数BufferBuffer空？空？空？空？否否否否是是是是完成数据计算完成数据计算完成数据计算完成数据计算打印打印打印打印向计算进程发信号向计算进程发信号向计算进程发信号向计算进程发信号通知其向通知其向通知其向通知其向BufferBuffer送数送数送数送数BufferBuffer空？空？空？空？否否否否是是是是合作合作合作合作
9、进程间的同步关系进程同步时面临的两种主要关系司机与售票员司机与售票员多个打印者多个打印者计算者与打印者计算者与打印者事件、设备等抽事件、设备等抽事件、设备等抽事件、设备等抽象为象为象为象为资源资源资源资源对进程间关系的处理变为对对进程间关系的处理变为对对进程间关系的处理变为对对进程间关系的处理变为对资源资源资源资源的访问方式的访问方式的访问方式的访问方式同步的概念同步的概念总结：两种制约关系1资源共享资源共享(进程互斥、进程间的间接相互制约）进程互斥、进程间的间接相互制约）2相互协作（进程同步、直接相互制约）相互协作（进程同步、直接相互制约）进程同步的任务进程同步的任务保证各进程能互斥地访问这
10、些资源（有效地共享资源）。保证协作进程或线程的顺序执行，使它们不会出现与时间有关的差错，对数据的一致性进行维护（有效地相互合作）。临界资源临界资源临临界界资资源源：在在一一段段时时间间内内只只允允许许一一个进程访问的资源个进程访问的资源 对对临临界界资资源源的的访访问问必必须须采采用用互互斥斥的的方式进行，以实现对资源的共享。方式进行，以实现对资源的共享。怎样才能保证并发执行结果的正确性呢？如果我们把两个进程中使用公共变量有关的语句，各自都抽象为一个顺序的执行单位，也就是说，保证任何一个进程即使运行到其中这些语句时被打断，在它下一次被调度到而继续执行直到退出这些语句之前，另一个进程不允许进入使
11、用公共变量的语句执行，也就一定能保证那些语句总能被顺序地执行，显然其执行结果也一定是正确的临界区问题临界区问题临界区的概念：将多个进程访问临界资源的那一段程序代码称为临界区。在临界区中，进程能改变变量的值，更新数据表或写文件等。系统只允许一个进程在临界区执行，而不允许其它进程进入临界区。解决临界区问题必须遵循的原则：1.当某一时刻没有进程处于临界区内时，相应的临界资源处于空闲状态。因而可允许一个请求进入临界区进程立即进入临界区，以有效地利用临界资源。2.如果此时已有进程进入临界区，则其它试图进入临界区的进程必须等待，以保证各进程互斥地访问临界资源。3.当某个进程申请进入临界区时，它应在有限时间
12、内获得系统的响应，而能够进入临界区，以免进程陷入无限等待状态。4.当进程不能进入临界区时，应立即释放处理机，以免进程陷入忙等待状态。1 空闲让进；2 忙则等待；3 让权等待；4 有限等待；临界区临界区进入区进入区临界区临界区临界区临界区退出区退出区进入区进入区临界区临界区临界区临界区退出区退出区.阻塞等待阻塞等待阻塞等待阻塞等待资源释放资源释放资源释放资源释放改变资源改变资源改变资源改变资源状态状态状态状态释放资源释放资源释放资源释放资源唤醒等待唤醒等待唤醒等待唤醒等待进程进程进程进程进程进程进程进程 1 1进程进程进程进程 2 2同步的实现同步的实现解决临界区问题可以用软件或硬件实现。使用硬
13、件实现进程的同步，可以使用户的编程任务更容易且系统的效率更高。1关中断关中断使用关中断解决单处理器环境下临界区的问题。使用关中断不能解决多处理器环境下临界区的问题。关闭中断将延误处理器的处理时间，使系统性能下降。锁机制临界资源锁机制例：商场的试衣间是互斥资源是临界资源是共享资源每个顾客必须遵循以下过程使用试衣间：靠锁实现资源的共享管理靠锁实现资源的共享管理靠锁实现资源的共享管理靠锁实现资源的共享管理观察锁状态观察锁状态观察锁状态观察锁状态关锁关锁关锁关锁使用试衣间使用试衣间使用试衣间使用试衣间开锁开锁开锁开锁锁机制临界资源锁机制锁锁锁锁锁变量锁变量锁变量锁变量L L每个进程必须按照以下过程操作
14、资源每个进程必须按照以下过程操作资源每个进程必须按照以下过程操作资源每个进程必须按照以下过程操作资源L=1 L=1 关闭状态，资源忙关闭状态，资源忙关闭状态，资源忙关闭状态，资源忙L=0 L=0 打开状态，资源空闲打开状态，资源空闲打开状态，资源空闲打开状态，资源空闲抽象抽象抽象抽象L=1L=1临界区临界区临界区临界区L=0L=0锁机制实现一种简单的锁操作实现void lock(L)void lock(L)check:check:if(L=1)if(L=1)goto check;goto check;elseelseL=1;L=1;void unlock(L)void unlock(L)L=0
15、;L=0;锁机制实现.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=1;else L=1;临界区临界区临界区临界区unlock(L);unlock(L);.0 01 10 0 1 1 0 0锁操作模型锁操作的一般模型PiPi：.lock(L)C(i)unlock(L)
16、.lock(L)C(i)unlock(L).PjPj：.lock(L)C(j)unlock(L).lock(L)C(j)unlock(L).C(i)：Pi的临界区的临界区Pi：进程进程i出了问题的锁.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);.出现
17、问题的锁出现问题的锁出现问题的锁出现问题的锁进程进程进程进程 1 1 1 1进程进程进程进程 2 2 2 2L L0 01 1尚未执行尚未执行尚未执行尚未执行问题出在？问题出在？问题出在？问题出在？判断状态后判断状态后判断状态后判断状态后改变状态前改变状态前改变状态前改变状态前被打断被打断被打断被打断锁机制实现关锁操作不可被打断用原语实现关锁操作关锁操作在一个指令周期内完成锁操作的特点：实现了进程互斥访问临界资源。不遵循让权等待原则。忙等信号量机制信号量机制：由Dijkstra提出的一种解决进程的同步与互斥的工具：信号量信号量用于表示用于表示资源数目资源数目或或请求使用请求使用某一资源的进程个
18、数某一资源的进程个数的整型量的整型量.S是与临界区内所使用的共享资源有关的信是与临界区内所使用的共享资源有关的信号量。号量。S0 可供并发进程使用的资源数可供并发进程使用的资源数S0 正在等待使用临界区的进程数正在等待使用临界区的进程数P原语操作和V原语操作P原语操作的主要动作S1如果S1以后仍大于等于零，则进程继续进行如果S1以后小于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度V原语操作的主要动作S1如果相加后结果大于零，则继续进行相加后结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调度。入口s=s-1s0调度进程入等待队列转进程调度入口s=s
19、1s0唤醒等待队列中的一个进程返回或转进程调度返回返回s.否value=0)继续执行；else阻塞并进入等待队列；V操作V（S）S=S+1;if(S0)继续运行；else唤醒等待队列中的一个进程，并继续运行；信号量：PV操作记录型的信号量机制是一个记录型的数据结构，包含两个数据项，一是计数值域，另一是等待该信号量的进程队列首指针域。描述如下：typedef struct semaphore int value;PCB*p;semaphore；记录型信号量的P，V操作P(s)P(s)s.value=s.value-1s.value=s.value-1s.value 0?s.value 0?本进程
20、获得本进程获得本进程获得本进程获得一个资源一个资源一个资源一个资源临界区临界区临界区临界区/资源访问区资源访问区资源访问区资源访问区本进程进入本进程进入本进程进入本进程进入s.ps.p队列，进入阻塞队列，进入阻塞队列，进入阻塞队列，进入阻塞状态状态状态状态N NY YV(s)V(s)s.value=s.value+1s.value=s.value+1s.value=0?s.value=0?将将将将s.ps.p中中中中第一个进程第一个进程第一个进程第一个进程唤醒，唤醒，唤醒，唤醒，N NY YP(s)和V(s)操作原语voidP(s)structsemaphores;s.value=s.valu
21、e-1;if(s.value0)block(s.p);void v(s)struct semaphore s;s.value=s.value+1;if(s.value=0)wakeup(s.p);2.3.2 信号量机制AND型信号量（只需了解）引入原因:一个进程需要先获得两个或更多的资源后,方能执行其任务.Process A:Process B:Process A:Process B:p(Dmutex);p(Emutex);p(Dmutex);p(Emutex);p(Emutex);p(Dmutex);p(Emutex);p(Dmutex);Process A:p(Dmutex);Proces
22、s A:p(Dmutex);于是于是于是于是mutexmutexProcessProcess:p(:p(mutex);mutex);于是于是于是于是mutexmutexProcess A:p(Process A:p(mutex);mutex);于是于是于是于是mutexmutex阻塞阻塞阻塞阻塞Process Process:p(:p(mutex);mutex);于是于是于是于是mutexmutex阻塞阻塞阻塞阻塞P P1 1（S1S1）；）；）；）；P P1 1（S2S2）；）；）；）；P P2 2（S2S2）；）；）；）；P P2 2（S1S1）；）；）；）；进程进程进程进程1 1进程进程
23、进程进程2 2 2 2系统推进过程为系统推进过程为系统推进过程为系统推进过程为P P1 1（S1S1）；）；）；）；P P2 2（S2S2）；）；）；）；P P2 2（S1S1）；）；）；）；P1P1（S2S2）；）；）；）；进程进程进程进程2 2阻塞阻塞阻塞阻塞进程进程进程进程1 1阻塞阻塞阻塞阻塞S1S1S2S2进程进程进程进程1 1和进程和进程和进程和进程2 2都无法都无法都无法都无法继续推进出现继续推进出现继续推进出现继续推进出现死锁死锁死锁死锁。V(S2);V(S2);V(S1);V(S1);V(S1);V(S1);V(S2);V(S2);基本思想将对多个信号量的逐个申请改为一次，用
24、一个原子操作完成进程要么一次获得所有的资源，要么一个也申请不到不会存在互相等待的局面信号量集信号量集信号量集信号量集SPSP（S1S1，S2S2，S3SnS3Sn）信号量集（了解）引入原因:在记录型信号量中每次对仅能施以加或减操作，即每次只能获得或释放一个单位的临界资源一次需要个某类临界资源时资源数量低于某一下限值时，便不予分配可对信号量机制加以扩充，形成一般化的“信号量集”机制公用与私用信号量公用信号量：公用信号量：私用信号量：私用信号量：一组进程共享，都可进行一组进程共享，都可进行一组进程共享，都可进行一组进程共享，都可进行P P、V V操作操作操作操作用于进程间资源的竞争用于进程间资源的
25、竞争用于进程间资源的竞争用于进程间资源的竞争拥有信号量的进程只对信号量进行拥有信号量的进程只对信号量进行拥有信号量的进程只对信号量进行拥有信号量的进程只对信号量进行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）后继进程：后继进程：后继进程：后继进程：前驱进程：前驱进程：前驱
26、进程：前驱进程：2.3.3 信号量的应用.利用信号量实现进程互斥P(s)P(s)V(s)V(s)临界区临界区临界区临界区P(s)P(s)V(s)V(s)临界区临界区临界区临界区临界临界临界临界资源资源资源资源进程进程进程进程进程进程进程进程原理原理原理原理:为临界资源设置一互斥信号量，初始值为，将为临界资源设置一互斥信号量，初始值为，将为临界资源设置一互斥信号量，初始值为，将为临界资源设置一互斥信号量，初始值为，将个进程的临界区个进程的临界区个进程的临界区个进程的临界区CSCS置于置于置于置于P(S)P(S)和和和和V(S)V(S)操作之间即可操作之间即可操作之间即可操作之间即可例1：n个并发
27、进程共用一个公用变量Q，写出信号量实现n个进程互斥时的程序描述，并说明信号量的取值范围。2.利用信号量实现前驱关系设有个并发执行的进程：P1:s1;P2:s2为了实现前驱关系S1 S2 ，可使他们共享一个公用信号量，初值为 P1:S1;V(s);P2:P(s);S2;利用信号量解决前驱图问题例如：PA、PB、PC为一组合作的进程，其流程如图所示，使用信号量实现三个进程的同步。ACBS SB B=0=0;S SC C=0;=0;BeginBeginP PA A:Begin:Begin V(S V(SB B)End;End;P PB B:Begin:Begin P(S P(SB B)V(S V(S
28、c c)End;End;P Pc c:Begin:Begin P(S P(Sc c)End;End;例如：PA、PB、PC为一组合作的进程，其流程如图所示，使用信号量实现三个进程的同步。设两个同步信号灯SB、SC分别表示进程和能够开始 执行，其初值均为0（SB=0，SC=0）。ACBSB=0;SC=0;BeginPA:Begin V(SB)V(SC)End;P Pc c:Begin:Begin P(S P(Sc c)End;End;EndProgram;P PB B:Begin:Begin P(S P(SB B)End;End;S1S1S2S2S3S3S4S4S5S5S6S6Var a,b,c
29、,d,e,f,g;semaphoreVar a,b,c,d,e,f,g;semaphore :=0,0,0,0,0,0,0;:=0,0,0,0,0,0,0;begin begin parbegin parbegin begin S1;v(a);v(b);end;begin S1;v(a);v(b);end;begin p(a);S2;v(c);v(d);end begin p(a);S2;v(c);v(d);end begin p(b);S3;v(e);end begin p(b);S3;v(e);end begin p(c);S4;v(f);end begin p(c);S4;v(f);en
30、d begin p(d);S5;v(g);end begin p(d);S5;v(g);end begin p(e);p(f);p(g);S6;end begin p(e);p(f);p(g);S6;end parend parendendenda ab be ed dc cf fg g利用信号量来描述前趋图关系S1S3S2S4S5S6S7S8具有具有8个结点的前趋图。图中的前趋图个结点的前趋图。图中的前趋图中共有有向边中共有有向边10条，可设条，可设10个信号量，个信号量，初值均为初值均为0；有；有8个结点，可设计成个结点，可设计成8个个并发进程，具体描述如下：并发进程，具体描述如下：S1S
31、3S2S4S5S6S7S8agefbcdhijStruct smaphore a,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0cobegin S1;V(a);V(b);V(c);P(a);S2;V(d);P(b);S3;V(e);V(f);P(c);S4;V(g);P(d);P(e);S5;V(h);P(f);P(g);S6;V(i)P(h);P(i);S7;V(j);P(j);S8;coendS1S3S2S4S5S6S7S8agefbcdhij用信号量解题的关键步骤：信号量的设置；给信号量赋初值（常用的互斥和同步信号量值的大小）；P、V操作安排的位置（其中，P的
32、顺序不能颠倒）练习ACBDE3.利用信号量实现进程同步：P(s1)P(s1)V(s2)V(s2)临界区临界区临界区临界区P(s2)P(s2)V(s1)V(s1)临界区临界区临界区临界区进程进程进程进程进程进程进程进程B B分析进程间的制约关系，确定信号量的种类，从而分析进程间的制约关系，确定信号量的种类，从而分析进程间的制约关系，确定信号量的种类，从而分析进程间的制约关系，确定信号量的种类，从而明确设置信号量。明确设置信号量。明确设置信号量。明确设置信号量。信号量的初始值与相应资源有关。信号量的初始值与相应资源有关。信号量的初始值与相应资源有关。信号量的初始值与相应资源有关。用一信号量的用一信
33、号量的用一信号量的用一信号量的P P、V V操作要操作要操作要操作要“成对成对成对成对”出现，但分别出现，但分别出现，但分别出现，但分别在不同的进程代码中。在不同的进程代码中。在不同的进程代码中。在不同的进程代码中。例例 2：已已 知知 一一 个个 求求 值值 公公 式式（A2+3B）/(B+5A),若若A,B已已赋赋值值，试试画画出该公式求值过程的前趋图。出该公式求值过程的前趋图。解解：在在该该公公式式的的求求值值过过程程中中，有有些些运运算算分分量量的的执执行行是是可可以以并并发发执执行行的的。为为了了描描述述方方便便，可可设设置置一一些些中中间间变变量量保保存存中中间间结结果果，并并给给每每个个语语句句命命名名，其其求求值值过过程程如下：如下：S1S4S6S5S3S2S1:x1=A*AS2:x2=3*BS3:x3=5*AS4:x4=x1+x2S5:x5=B+x3S6:x6=x4/x5开始结束（A2+3B）/(B+5A)作业如下图具有6个节点的前驱图，利用信号量机制来解决该前驱图所描述的并发执行的过程。S1S1S1S1S1S1