操作系统5--信号量机制

操作系统

3.3.2 信号量(semaphore)机制

P51

前面的互斥算法都存在问题，它们是平等进程间的一种协商机

制，需要一个地位高于进程的管理者来解决公有资源的使用问题 。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提 供的管理公有资源的有效手段 1965年，由荷兰学者Dijkstra提出，他把互斥的关键概念抽象 到信号量这个概念中，是一种卓有成效的进程同步机制 信号量是一个被保护的变量，并且只能通过初始化和两个标准

的原子操作来访问.

1、整型信号量机制 2、记录型信号量机制 3、信号量集机制5.1/28 2011

操作系统

1、整型信号量机制1).整型信号量 是一个整数，表示空闲资源总数(又称为“资源信号量”) ----若为非负值表示当前的空闲资源数， ----为负值其绝对值表示当前等待临界区的进程数 ----初值应该大于零。 两个原子操作即: P,V操作。也常称为wait(s),singal(s)

(P、V分别是荷兰语的test(proberen)和increment(verhogen)) 即： P(s): Wait(s): while s<=0 do no_op s:=s-1; V(s): Singal(s): s:=s+1;5.2/28 2011

2).利用信号量实现互斥

操作系统

为临界资源设置一个互斥信号量mutex(MUTual EXclusion),初值为1; 在每个进程中将临界区代码置于wait(mutex)和signal(mutex)原语之间 利用信号量实现进程互斥：

Var mutex: semaphore ;//说明一个信号量process1: begin repeat wait(mutex); critical section; signal(mutex); remainder section; until false; end process2: begin repeat wait(mutex); critical section; signal(mutex); remainder section; until false; endprocess1: begin repeat P(mutex); critcial section; V(mutex); remainder section; until false; end

5.3/28

2011

操作系统

注

意：

必须成对使用wait和signal原语

wait、signal原语不能出现次序错误、重复或遗漏

遗漏wait原语则不能保证互斥访问 遗漏signal原语则不能在使用临界资源之后将其 释放(给其他等待的进程);

5.4/28

2011

操作系统

3). 利用信号量来描述前趋(合作)关系C1 C2

前趋关系：并发执行的进程P1和P2中，分别有代码C1和 C2,要求C1在C2开始前完成； 为每个前趋关系设置一个互斥信号量S12,其初值为0P1 C1 V(S12);5.5/28

P2

P(S12);C2 2011

操作系统

例：用信号量来描述如下的前趋图s1 s2 s4 s3

s5s6

Var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0,0;Parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; Parend;5.6/28 2011

操作系统

2、记录型信号量机制引入进程阻塞机制 在信号量里增加对阻塞进程的记录 typedef struct Semaphore{ int value; process_list

* list; } semaphore ; 资源个数 阻塞进程(PCB)队列

5.7/28

2011

操作系统

记录型信号量的P,V操作(wait(s)和signal(s))P( s ) V( s )

s.value = s.value - 1 Y s .value< 0 ?N 本进程获得 一个资源 本进程进入s.list 队列，进入阻塞 状态

s.value = s.value + 1 Ys .value<= 0 ? N 将s.list中 第一个进程 唤醒，

临界区/资源访问区5.8/28 2011

操作系统

伪码描述Procedure wait(s) var S: semaphore; begin S.value:=s.value-1; if S.value<0 then block(S,L); end; Procedure signal(s) Var S:semaphore; Begin S.value:=S.value+1; If S.value<=0 then wakeup(S.L); End;

当s.value初值为1时，转化为互斥信号量5.9/28 2011

操作系统

3、信号量集 整型信号量机制和记录型信号量机制都是针对进程间要共享

一个临界资源而言的； 当一段处理代码需要同时获取两个或多个临界资源时，使用 整型或记录型信号量，会产生各进程分别获得部分临界资源， 然后等待其余的临界资源，“各不相让”的问题---死锁。 如：A,B进程都要访问共享资源D,E.

信号量集用于进程需要多个资源时的信号量操作；

5.10/28

2011

操作系统

1) AND型信号量集机制 基本思想： 将一段代码同时需要的多个临界资源，采用原子 方式，要么全部分配给它，要么一个都不分配。称为 Swait(Simultaneous Wait)。同样地，使用结束后一 起释放，称为Ssignal;

5.11/28

2011

操作系统

Swait(Simultaneous Wait)Swait(S1, S2, …, Sn) //P原语； { if (S1 ≥1 and S2 ≥ 1 … Sn ≥ 1) {//满足资源要求时的处理； for (i = 1; i <= n; ++i) Si=Sj-1;//注：与wait的处理不同，这里是在确信可满足 //资源要求时，才进行减1操作 } else {//某些资源不够时的处理； 调用进程进入第一个小于1信号量的等待队列Sj.queue ,阻 塞调用进程; } }5.12/28 2011

//次序并不重要，虽然会影响进 程归入哪个阻塞队列，但由于是 对资源全部分配或不分配，所以 总有进程获得全部资源并在推进 之后释放资源，因此不会死锁

Ssignal(Simultaneous Signal)

操作系统

Ssignal(S1, S2, …, Sn){ for (i = 1; i <= n; ++i){ ++Si; //释放占用的资源； for (each process P waiting in Si.queue){ //检查每种资源的等待队列中的所有进程； 从等待队列Si.queue中取出进程P; if(判断P是否通过Swait中的测试){ //注:与signal不同，需重新判断 进程P进入就绪队列; break; } else{ //未通过检查(资源不够用)时的处理； 进程P进入某等待队列；//然后继续循环判断下一个进程 } } } }5.13/28 2011

2) 一般“信号量集”机制一次需要N个某类临界资源时，要进行N次wait操作——低效

操作系统

一般信号量集的基本思想：在AND型信号量集的基础上进行扩充,扩充为 进程需要申请多个资源，每个资源可能申请多个

的情况， 每个资源对应一个信号量Si: 进程对资源i的需求值为di:每次申请或释放di个，Si=Si-di和Si=Si+di 资源i的测试值为ti:当资源个数小于ti时，便不再分配PV原子操作： Swait(S1, t1, d1; ...; Sn, tn, dn); Ssignal(S1, d1; ...; Sn, dn); 一般“信号量集”的几种特定情况： Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配 Swait(S, 1, 1)表示互斥信号量； Swait(S, 1, 0)作为一个可控开关，并不申请资源 当S>=1时，可以通过测试，允许多个进程进入某特定区； 当S=0时，无法通过测试，禁止任何进程进入某特定区；5.14/28 2011

操作系统

信号量

整型信号量机制 多个进程共享一个临界资源 记录型信号量机制 And型信号量集机制： 同时需要多种资 信号量集机制 源且每种占用一个时的信号量操作； 一般信号量集机制：同时需要多种资源、每 种占用的数目不同、且可分配的资源还存在 一个临界值时的处理；

5.15/28

2011

操作系统

3.3.3 经典进程同步问题

P58

1. 生产者-消费者问题(producer-consumer problem) 问题描述：若干进程通过有限的共享缓冲区交换数据。其中， “生产者”进程不断写入，而“消费者”进程不断读出；共 享缓 …… 此处隐藏：3262字，全部文档内容请下载后查看。喜欢就下载吧 ……