一.进程的同步和互斥
临界资源:诸进程间需要互斥方式对其进行共享的资源(进程中访问临界资源的那段代码也称为临界区)
互斥:同一时刻只能由一个进程访问。互斥的进程形成间接制约关系。
同步:进程间速度有差异,快的进程需要等待慢的进程,这样的制约关系是直接制约关系。
这两者并不是互相排斥的关系,进程调度可以有互斥,可以有同步,也可以两种模型交叉形成。
二.PV操作
进程与进程之间并发时,如何限定进程间形成协调的同步模型,这就需要PV操作。
PV操作是针对P(S)和V(S)的操作,这里的S指的是信号量,是一种特殊的变量,它可以表示:
1.资源数量。
2.其为负数时还可以表示排队进程数。
接下来,对PV操作具体分析:
P操作:
S=S-1:表示申请/锁定资源
S<0 :检查资源是否足够 (注意:这里我们是先做申请,再进行比较的,所以S=0时资源也是足够的,只有S<0,表示资源不够)
资源不足会进入阻塞队列,只有资源释放才能进入就绪队列
V操作:
S=S+1:释放/解锁资源
S<=0: 检查是否有进程排队,如果有人排队就通知并唤醒阻塞进程(注意:这里是<=0,若=0,又有进程申请,=-1,即有一个进程在排队,若资源释放,先对进程+1,S=S+1,这时=0,说明S=0时就有进程在排队了)
阻塞进程的唤醒并不会立即进行,只有V操作过程进行完,才会进行唤醒。
三.互斥模型和同步模型
互斥模型
PV操作在互斥模型中是成对存在的,这里的S表示资源数,也称为互斥信号量,S=1。
同步模型
成对的PV操作,在不同的模型中协调进行,称为同步模型。
这里的市场是单缓冲区,也可以存在多缓冲区
将资源送到缓冲区之前,一定要查看缓冲区是否存在空闲的空间资源,如果缓冲区已满,那么P操作(生产产品)就会被阻塞,只有消费者方消费产品(释放资源),才会继续进行P操作
这里的第二个PV操作中的V操作表示将产品送到缓冲区,P操作表示从缓冲区取产品。所以PV操作一定是成对存在的,但是并没有固定的先后顺序。
在这里S1是在送缓冲区之前,所以S1针对的是缓冲区资源,S2是产品送到之后才有的,所以S2针对的是产品资源,所以S1的初值=1,S2的初值=0。
互斥与同步模型结合
缓冲区是典型的临界资源,同一时刻只能让一个进程使用,除了成对的同步模型PV以外,还需要控制两个进程,不能使两个进程同时使用缓冲区。
这就需要在使用缓冲区的时候(送产品到缓冲区/从缓冲区取产品)进行加锁,使用完缓冲区后立即解锁。这里的S表示的是临界资源,初值=1。当一个进程拿到临界资源的访问权之后,其他进程就不能访问该临界资源了。
同步信号量:S1初值为1,S2初值为0
互斥信号量:S初值为1
若变为空间为m的缓冲区
那么此时S1的初值=m,其他不变
例题:
假设铁路自动售票系统有n个售票终端,该系统为每个售票终端创建一个进程Pi (i=1,2,..,n)管理车票销售过程。假设Tj (j=1,2,...m)单元存放某日某趟车的车票剩余票数,Temp为Pi进程的临时工作单元,x为某用户的购票张数。Pi进程的工作流程如下图所示,用P操作和V操作实现进程间的同步与互斥。初始化时系统应将信号量S赋值为 ( )。图中(a),(b) 和 (c) 处应分别填入 ( )
A.n-1 B.0 C.1 D.2
A.V(S)、P(S)和P(S) B. P(S)、P(S)和V(S)
C.V(S)、V(S)和P(S) D. P(S)、V(S)和V(S)
这里的Temp(临时工作单元)可以理解为缓冲区,只能允许一个进程访问,初始时系统信号量S=1
答案:C,D
四.前驱图
对于前驱图而言:每一条箭线流出的地方,表示一个前驱活动的完成,需要通过V操纵通知后继,每
一条箭线流入的地方都需要有 P操作用来检查前驱活动是否完成。
这里初始信号量的个数=箭线的条数,Sa=Sb=Sc=Sd=0,初始时信号量是没有意义的,需要根据题目来判断信号量的位置。
程序的执行过程如下:
例题1:
这里的a为V(S1)V(S2),b为V(S3),c为P(S2),d为V(S4),e为V(S5),f为P(S4)P(S5)
所以可以看到,所有执行之前的操作,要么没有要么就是P操作,执行之后的操作,要么没有要么就是V操作
例题2:
第一行对应的是输入设备,第二行对应的是CPU,第三行对应的是输出设备,横向来看是不同的作业在同一个设备上的流动,纵向来看是同一个作业在不同设备流动。
所以答案:C,D