os22同步互斥2.pptVIP

并发进程间制约关系 资源共享关系?间接制约 多个进程彼此无关，完全不知道或只能间接感知其它进程的存在 系统须保证诸进程能互斥地访问临界资源 系统资源应统一分配，而不允许用户进程直接使用 相互合作关系?直接制约 系统应保证相互合作的诸进程在执行次序上的协调和防止与时间有关的差错 2.3 进程的同步与互斥 进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。 进程互斥 进程同步 利用信号量机制解决具体问题 2.3.1进程同步的基本概念 并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的制约关系： 1 间接制约关系（进程互斥） 由于共享资源而引起的在临界区内不允许并发进程交叉执行的现象。由共享公有资源而造成的对并发进程执行速度的间接制约 2 直接制约关系（进程同步） 由于并发进程互相共享对方的私有资源所引起的直接制约。 什么叫互斥？ 一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。 临界资源:一次仅允许一个进程使用的资源。 临界区：每个进程中访问临界资源的那段代码（critical section）。 （不允许多个并发进程交叉执行的那段程序) 例如，各种程序中经常出现的赋值语句：X=X+1；在用汇编语言书写时，就变成： LOAD A，X ADDI A，1 STORE A，X 等三条语句，这里 A代表累加器。根据系统的设计和要求，在这三条语句的执行期间，也有可能发生中断或调度，从而使得与当前进程无关的程序得以执行。为了保证程序执行最终结果的正确性，必须对并发执行的各进程进行制约，以控制它们的执行速度和对资源的竞争。 设有两个计算进程ＰA，ＰB共享内存ＭS。其中 ＭS分为三个领域，即系统区、进程工作区和数据区。这里数据区被划分大小相等的块，每个块中既可能放有数据，也有可能未放有数据。系统区主要是堆栈Ｓ，其中存放那些空数据块的地址（如图） getspace: begin local g g←stack ［ top ］ top←top-1 end release(ad): begin top ← top+1 stack ［ top ］←ad end 设时刻t0时，top=h0，则getspace和 release(ad)可能按以下顺序执行： 首先 release(ad)的第一句执行， t0：top ← top+1 → top=h0+1； 接着getspace 执行，得： t1：g ← stack ［top］→g=stack ［ h0+1］； t2：top ← top-1 → top=h0； 再是 release(ad)的第二句执行，得： t3：stack ［top］← ad → stack ［ h0 ］ ← ad； 其结果是调用getspace的进程取到的是h0+1中的一个未定义值，而调用release(ad)的进程把所释放的空数据块的地址ad重复放入了h0中。 怎样保证上述执行结果的正确性呢？ 一个较为明显的答案是，如果把getspace和release(ad)抽象为两个各以一个动作完成的顺序执行单位，那么执行结果的正确性是可以保证的。 把不允许多个并发进程交叉执行的一段程序称为临界部分（critical section ）或临界区（critical region）。 临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，例如上例中就是因为过程 getspace 和 release(ad)共同访问栈Ｓ中的数据而引起的。临界区不可能用增加硬件的方法来解决。因此，临界区也可以被称为访问公用数据的那段程序。 临界区的管理 计算机专家Dijkstra 1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足： ①每次至多有一个进程处于临界区 ②当若干进程同时要求进入它们的临界区时，应在有限时间内使一进程进入临界区，而不应相互堵塞而致使彼此不能进入临界区 ③进程仅在临界区内逗留有限的时间。 简言之，同步机制的准则有：1 空闲让进；2 忙则等待；3 让权等待；4 有限等待； 尽管用加锁的方法可以实现进程之间的互斥，但这种方法仍然存在一些影响系统可靠性和执行效率的问题。例如，循环测试锁定位将损耗较多的 CPU计算时间。如果一组并发进程的进程数较多，且由于每个进程在申请进入临界区时都得对锁定位进行测试，这种开销是很大的。 另外，使用加锁法实现进程间互斥时