进程互斥详解.ppt

1、3.5 进程互斥,互斥:两个或两个以上的进程，由于不能同时使用同一临界资源，只能是一个进程使用完，另一个进程才能使用。这种现象称为进程互斥。,返回,3.5.1 资源共享所引起的制约 3.5.2 互斥的加锁实现 3.5.3 信号量(semaphore)与 PV原语 3.5.4 用PV原语实现进程互 斥,3.5.1 资源共享引起的制约,3.5.1.1临界资源 3.5.1.2临界区的访问过程 3.5.1.3进程互斥的软件方法 4.5.1.4进程互斥的硬件方法,3.5.1.1临界资源,多道程序环境进程之间存在资源共享，进程的运行时间受影响 临界资源：把一次仅允许一个进程使用的资源称为临界资源。,进程间

2、资源访问冲突 共享变量的修改冲突 操作顺序冲突 进程间的制约关系 间接制约：进行竞争独占分配到的部分或全部共享资源，“互斥” 直接制约：进行协作等待来自其他进程的信息，“同步”,共享变量的修改冲突,举例：共享变量x,3.5.1.2临界区的访问过程,临界区,各进程对于临界区资源的操作必须互斥， 互斥执行的程序段为临界区(critical section),临界区(critical section)：进程中访问临界资源的一段代码。 进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志 退出区(exit sectio

3、n)：用于将正在访问临界区标志清除。 剩余区(remainder section)：代码中的其余部分。,3.5.1.3进程互斥的软件方法,有两个进程Pi, Pj，其中的Pi , Pj,算法1：单标志,设立一个公用整型变量 s：描述允许进入临界区的进程标识 在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入； 在退出区修改允许进入进程标识：进程Pi退出时，改turn为进程Pj的标识j；,缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区；,3.5.2互斥的加锁实现,当某个进程进入临界区后，它

4、将锁上临界区，直到它退出临界区为止。 Lock(keys) /keys=0 加锁 临界区 Unlock(keys) /keys=1解锁,3.5.3 信号量(semaphore),4.4.2.1 信号量和P、V原语 4.4.2.2 信号量集,前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。 信号量代表可用资源实体的数量。,信号量和P、V原语,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)increm

5、ent(verhogen)），是一种卓有成效的进程同步机制。,每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中的s是阻塞在该信号量的各个进程的标识 信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断 初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数 二进制信号量(binary semaphore)：只允许信号量取0或1值,1. P原语wait(s),-s.count;/-1表示申请一个资源; if (s.count 0)/表示没有空闲

6、资源; 调用进程进入等待队列s.queue; 阻塞调用进程; ,用消息wait(消息名）等待合作进程发来消息,2. V原语signal(s),+s.count;/+1表示释放一个资源； if (s.count = 0)/表示有进程处于阻塞状态； 从等待队列s.queue中取出一个进程P; 进程P进入就绪队列; ,V原语通常唤醒进程等待队列中的头一个进程 用消息signal(消息名）表示向合作进程发去消息,3.5.4 利用信号量实现互斥,为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间 必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏,互斥模型: 进程P1 进程P2 P(S) P(S) S1 S2 V(S) V(S) 其中信号量初值:S=1；S1、S2为两个互斥程序段。,并发进程之间存在相互制约关系 “同步“ 进程P1 : 进程P2: L1:P(S) L2:V(S) 信号量初值:S=0,进程P1 Y:=1; Y:=y+2; V(s1); Z:=y+1; P(s2); Y:=z+y;,进程P2 x:=1; x:=x+1; p(s1);