操作系统-信号量应用.ppt

1、第二章 进程管理,2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 进程通信,2.3 进 程 同 步,2.3.1 进程同步的基本概念 2.3.2 信号量机制 2.3.3 信号量的应用,1.进程同步的概念 所谓进程同步，在多道技术下，对多个相关进程在执行次序上的协调、正确，OS中用于保证这种关系的相应机制称为进程同步机制。,2.3.1 进程同步的基本概念,并发进程之间由于资源共享和进程合作，使处于一个系统内的进程存在制约关系： 直接相互制约关系：源于进程间的合作。 进程A通过缓冲区向进程B提供数据用于计算,输入进程A 计算进程B,2、进程的制约关系,

2、进程间关系,间接相互制约关系：源于共享系统资源。 相互制约的进程本身并没有关系，但由于申请使用相同的资源，但这个资源一段时间内只允许一个进程使用，这时两个进程是间接制约关系。,3。临界资源(Critical Resouce),定义：在一段时间内，只允许一个进程访问的资源。 软件：共享变量（存储单元） 硬件：打印机、扫描仪（多个任务不能穿插使用）,并发进程应互斥地访问临界资源。 （以飞机售票系统为例）, n=x n=n-1; x=n; , m=x m=m-1; x=m; ,X=10, n=x n=n-1; x=n; ,A进程,B进程,同一段程序。两个终端, n=x n=n-1; x=n; , m

3、=x m=m-1; x=m; ,X=10, n=x n=n-1; x=n; ,A进程,B进程,三条语句不能分开,公共资源,临界区,4. 临界区 (Critical Section) 定义：对临界资源访问代码段称为临界区。,对临界资源的访问控制可以通过对进入临界区的控制。互斥访问临界区便可实现对临界资源的互斥访问。,临界区互斥访问描述：,相应的，在临界区后也应加上一段“退出区”（exti section）代码 用于将正在被访问的标志恢复为未访问的标志。,每个进程在进入临界区之前，应先对临界资源做检查，看临界资 源是否正被访问，为此，每个进程在进入临界区之前，应设置一段 用于上述检查的代码，称为“

4、进入区”代码（entry section）,如果临界资源空闲，则进入，并设置正在被访问的标志。,访问临界资源的循环进程描述,Entry section,Critical section,Exit section,Remainder section,repeat,until false,5. 同步机制应遵循的规则 (1) 空闲让进 (2) 忙则等待 有限等待（避免“死等”） 确保在有限的时间内进程可以进入自己的临界区 让权等待（释放CPU） 进程不能进入临界区，应立即释放处理机，不能一直检测，以免进程陷入“忙等”,如何实现Entry section和Eixt section ?,2.3.2 信号

5、量机制,一、 什么是信号量 信号量是一个特殊变量，除初始化外，仅能通过两个标准的原子操作wait(s)和signal(S)来访问，这两个操作一直被称为P操作和V操作。这个变量时整型变量，代表物理实体。 wait(S)和signal(S) 一直被分别称为P、V操作,亦可记作 P(s),V(s)。,整型信号量机制 记录型信号量机制 AND型信号量机制 信号量集机制,信号量分类,1. 整型信号量机制（计数型）,将信号量S定义成一个整数。 P（S）、V（S）操作 Wait 和 signal操作可描述为： P(S) wait(S): while S0 do no-op S=S-1; (获取对资源访问权)

6、,V(S) singal: S=S+1; (释放访问权),1. 整型信号量机制（续）,利用信号量实现进程互斥访问临界资源 var mutex： semaphore:=1; Process i: begin repeat Wait(mutex); (获取资源) Critrical Section; Signal(mutex); (释放资源) Reminder Section until false end; end,整型信号量的缺陷,在整型信号量机制中的wait操作，只要是信号量S0， 就会不断地测试。因此，该机制并未遵循“让权等待”的准则， 而是使进程处于“忙等”的状态。,课堂练习,1、为什么

7、进程在进入临界区之前，应先执行“进入区”代码？在退出前又要执行“退出去”代码？ 2、你认为整型信号量机制是否完全遵循了同步机制的四条准则，为什么？,2. 记录型信号量机制,记录型信号量 在整型信号量机制中的wait操作，只要是信号量S0， 就会不断地测试。因此，该机制并未遵循“让权等待”的准则， 而是使进程处于“忙等”的状态。 记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。 为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。,2.

8、 记录型信号量机制(续1),记录型信号量的wait(S) (P(S) 操作可描述为： procedure wait(S) var S: semaphore; begin S.value =S.value-1; if S.value0 then block(S.L) end,1、S. value的初值表示系统中某类资源的数目， 又称为资源信号量；如S. value的初值为1，表示只允许 一个进程访问临界资源，此时的信号量转化为互斥信号量。 2、每次wait操作，意味着进程请求一个单位的该类 资源， 描述为 S. value =S. value-1； 3、当S. value0时，表示该类资源已分配

9、完毕，因 此进程应调用 block原语，进行自我阻塞，放弃处 理机，并插入到信号量链表S. L中。遵循了“让权等 待”准则。 4、当S. value0时，S. value的绝对值表示在该信号 量链表中已阻塞进程的数目。,2. 记录型信号量机制(续1),记录型信号量的signal(S)(V(S)操作可描述为： procedure signal(S) var S: semaphore; begin S.value=S.value+1; if S.value0 then wakeup(S.L); end,记录型信号量的物理意义(资源共享) S. value的初值表示系统中某类资源的数目，又称为资源信

10、号量； 当S. value0时，表示该类资源尚未分配完，还有S. value个。 对信号量的每次signal操作，表示执行进程释放一个单位资源，S. value =S. value+1操作表示资源数目加1。 若加1后仍是S. value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S. L链表中的等待进程唤醒。 如S. value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。,利用信号量实现进程互斥 利用信号量描述前趋关系 利用信号量实现进程同步,2.3.3 信号量的应用,1. 利用信号量实现进程互斥,Var mutex: s

11、emaphore=1; Begin parbegin process 1: begin repeat P(mutex); critical section; V(mutex); remainder seetion; until false; end,process 2: begin repeat P(mutex); critical section; V(mutex); remainder section; until false; end parend End.,1. 利用信号量实现进程互斥（例）,例1：过山洞/独木桥（一次只允许一人通过）问题 Var mutex:semaphore:=1;

12、 (tunnel,bridge) Parbegin Pi:begin Wait(mutex); Pass; 通过 Signal(mutex); End parend,前趋图举例,2. 利用信号量实现前趋关系(进程间执行的先后关系),方法： 为实现进程之间的前驱关系，考虑在S1和S2之间设置一个公用信号量 a,并赋予初始值为0，在s1执行完毕后signal(a),而在s2执行之前插入wait(a);,a,b,c,d,f,g,e,由于 a 的初始值为0，这样在并发执行的过程中如果先执行S2则必定阻塞，只有执行完S1, a 增1后S2才能顺利执行,3. 利用信号量实现进程同步,例1：计算进程CP、打印进程IOP共享一个缓冲区Buffer，计算进程CP一次向Buffer中送一批数据，打印进程IOP一次从Buffer中取一批数据去打印，请用记录型信号量和P、V 操作实现两进程的同步。,CP,IOP,BUFFER,3. 利用信号量实现进程同步(续1),Var Sa,Sb:semaphore:=1, 0; Begin Parbegin CP: Begin Repeat Compute next number; P(Sa); Add to Buffer; V(Sb); Until False End,IOP: Begin Repeat P(Sb); Get Number From Buf