《os-2-2-同步互斥2》由会员分享，可在线阅读，更多相关《os-2-2-同步互斥2（162页珍藏版）》请在金锄头文库上搜索。
1、1,并发进程间制约关系,资源共享关系间接制约多个进程彼此无关，完全不知道或只能间接感知其它进程的存在系统须保证诸进程能互斥地访问临界资源系统资源应统一分配，而不允许用户进程直接使用相互合作关系直接制约系统应保证相互合作的诸进程在执行次序上的协调和防止与时间有关的差错,2,2.3 进程的同步与互斥,进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。进程互斥 进程同步 利用信号量机制解决具体问题,3,2.3.1进程同步的基本概念并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的
2、制约关系：1 间接制约关系（进程互斥） 由于共享资源而引起的暂临界区内不允许并发进程交叉执行的现象。由共享公有资源而造成的对并发进程执行速度的间接制约2 直接制约关系（进程同步） 由于并发进程互相共享对方的私有资源所引起的直接制约。,4,什么叫互斥？ 一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。 临界资源:一次仅允许一个进程使用的资源。 临界区：每个进程中访问临界资源的那段代码（critical section）。（不允许多个并发进程交叉执行的那段程序),5,例如，各种程序中经常
3、出现的赋值语句：X=X+1；在用汇编语言书写时，就变成：LOAD A，XADDI A，1STORE A，X等三条语句，这里 A代表累加器。根据系统的设计和要求，在这三条语句的执行期间，也有可能发生中断或调度，从而使得与当前进程无关的程序得以执行。为了保证程序执行最终结果的正确性，必须对并发执行的各进程进行制约，以控制它们的执行速度和对资源的竞争。,6,设有两个计算进程A，B共享内存S。其中 S分为三个领域，即系统区、进程工作区和数据区。这里数据区被划分大小相等的块，每个块中既可能放有数据，也有可能未放有数据。系统区主要是堆栈，其中存放那些空数据块的地址（如图）,7,getspace:begin
4、localggstack top toptop-1endrelease(ad):begin top top+1stack top adend,8,设时刻t0时，top=h0，则getspace和 release(ad)可能按以下顺序执行：首先 release(ad)的第一句执行，t0：top top+1 top=h0+1；接着getspace 执行，得：t1：g stack topg=stack h0+1；t2：top top-1 top=h0；再是 release(ad)的第二句执行，得：t3：stack top ad stack h0 ad；其结果是调用getspace的进程取到的是h0+
5、1中的一个未定义值，而调用release(ad)的进程把所释放的空数据块的地址ad重复放入了h0中。,9,怎样保证上述执行结果的正确性呢？ 一个较为明显的答案是，如果把getspace和release(ad)抽象为两个各以一个动作完成的顺序执行单位，那么执行结果的正确性是可以保证的。把不允许多个并发进程交叉执行的一段程序称为临界部分（critical section ）或临界区（critical region）。临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，例如上例中就是因为过程 getspace 和 release(ad)共同访问栈中的数据而引起的。临界区不可能用增加
6、硬件的方法来解决。因此，临界区也可以被称为访问公用数据的那段程序。,10,临界区的管理 计算机专家Dijkstra 1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足：每次至多有一个进程处于临界区当若干进程同时要求进入它们的临界区时，应在有限时间内使一进程进入临界区，而不应相互堵塞而致使彼此不能进入临界区进程仅在临界区内逗留有限的时间。简言之，同步机制的准则有：1 空闲让进；2 忙则等待；3 让权等待；4 有限等待；,11,一种可能的办法是对临界区加锁以实现互斥。 设临界区的类名为，为了保证每一次临界区中只能有一个程序段被执行，又设锁定位KeyS，KeyS表示锁定位属于类名为的临界
7、区。加锁后的临界区程序描述如下：lock ( keyS ) unlock( keyS ),加锁法,12,设keyS=1时表示类名为S的临界区可用，keyS=0时表示类名为的临界区不可用。则，unlock(keyS)只用一条语句即可实现。即：keyS 1 不过，由于lock(keyS)必须满足keyS=0时，不允许任何进程进入临界区，而keyS=1时仅允许一个进程进入临界区的准则，因而实现起来较为困难。,13,一种简便的实现方法是：lock(x)= begin local v repeat v x until v=1 (临界资源成为可用） x 0end,14,不过，这种方法是不能保证并发进程互斥
8、执行所要求的准则（3）的（只允许一个进程进入临界区）。因为当同时有几个进程调用lock(key )时，在x0语句执行之前，可能已有两个以上的多个进程由于key =1而进入临界区。为解决这个问题有些机器在硬件中设置了“测试与设置指令，保证第一步和第二步执行不可分离。注意：在系统实现时锁定位key 总是设置在公有资源所对应的数据结构中的。,15,尽管用加锁的方法可以实现进程之间的互斥，但这种方法仍然存在一些影响系统可靠性和执行效率的问题。例如，循环测试锁定位将损耗较多的 CPU计算时间。如果一组并发进程的进程数较多，且由于每个进程在申请进入临界区时都得对锁定位进行测试，这种开销是很大的。另外，使用
9、加锁法实现进程间互斥时，还将导致在某些情况下出现不公平现象。某些进程可能不能进入临界区。,16,加锁法和、原语法： 加锁法是采用反复测试lock而实现互斥的，存在CPU浪费和不公平现象；而、原语法是采用信号量来管理相应的临界区的共有资源，信号量的值只能由、原语操作来改变，克服了加锁法的弊端。,17,2.3.2 信号量和P、V原语,信号：铁路交通管理中的一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理。信号量（semaphore)简称sem，sem是一整数，在sem大于等于零时，代表可供并发进程使用的资源实体数，但它小于零时是表示正在等待使用临界区的进程数。,18,P、V原语,信号量的
10、数值仅能由P、V原语操作改变。一次P原语操作使得信号量sem减1，而一次V原语操作使信号量sem加1.在操作系统中，信号量sem是一整数。用于互斥的信号量sem的初值应该大于零，而建立一个信号量必须经过说明所建信号量所代表的意义，和赋初值以及建立相应的数据结构以便指向那些等待使用该临界区的进程。,19,P原语操作的主要动作S1如果S1以后仍大于等于零，则进程继续进行如果S1以后小于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度V原语操作的主要动作S1如果相加后结果大于零，则继续进行相加后结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调度。,20,必
11、须强调的一点是，当某个进程正在临界区内执行时，其他进程如果执行了原语操作，则该进程并不像调用lock时那样因进不了临界区而返回到lock的起点，等以后重新执行测试，而是在等待队列中等待有其他进程做原语操作释放资源后，进入临界区，这时，原语的执行才算真正结束。当有好几个进程执行原语未通过而进入等待状态之后，如有某进程作了原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。,21,，过程要以原语实现的原因。如果多个进程同时调用操作或操作的话，则有可能在操作刚把sem-1而未把对应进程送入等待队列时，操作开始执行。从而，操作将无法发现等待进程而返回。因此，操作都必须以原语实现，且在，原语
12、执行期间不允许中断发生。,22,入口,s.value=s.value-1,s.value0,调度进程入等待队列,转进程调度,入口,s.value=s.value1,s.value0,唤醒等待队列中的一个进程,返回或转进程调度,返回,返回,s.value0,是,是,否,P原语操作功能流程图,V原语操作功能流程图,23,（sem）：begin封锁中断；lock(lockbit)valsem=valsem-1if valsem0保护当前进程CPU现场当前进程状态置为等待将当前进程插入信号sem等待队列转进程调度fiunlock(lockbit)；开放中断end,24,（sem）：begin封锁中断；
13、lock(lockbit)vasem=valsem+1if valsem0localk从sem等待队列中选取一等待进程，将其指针置入k中将k插入就绪队列进程状态置“就绪”fiunlock(lockbit)；开放中断end,25,利用P、V原语实现进程互斥,设sem为互斥信号量，取值范围为（1，0，-1），有两个并发的进程PA、PBsem 1表示进程PA、PB都没有进入类名为S的临界区sem 0表示进程PA、PB中的一个已经进入临界区sem -1表示进程中，一个进程已经进入临界区，另一个进程阻塞，等待进入临界区,26,利用，原语和信号量，可以方便地解决并发进程的互斥问题。设信号量sem是用于互斥
14、的信号量，且其初值为1表示没有并发进程使用该临界区。只要把临界区置于(sem)和(sem)之间，即可实现进程间的互斥。当一个进程想要进入临界区时，它必须先执行原语操作以将信号量sem减1。在一个进程完成对临界区的操作之后，它必须执行原语操作以释放它所占用的临界区。由于信号量初始值为 1，所以，任一进程在执行原语操作之后将sem的值变为0，表示该进程可以进入临界区。,27,描述：PA： P（sem)V(sem):Pb：P（sem)V(sem):,28,sem:integer:=1；cobeginp1: p2: while(true) while(true) p(sem) p(sem) 临界区代码 临界区代码 v(sem) v(sem) coend,29,信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作,信号量及P、V操作,30,用P、V操作解决进程间互斥问题,31,例1：某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一个进程。,
