上机2(操作系统上机).pdf

《上机2(操作系统上机).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章同步和互斥现代操作系统的中心方案是多道程序设计、多处理和分布式处理，这些方案的基础以及操作系统设计的基础是并发。当多个进程并发执行时，不论是在多处理器系统的情况下，还是单处理器多道程序系统中，都会产生解决冲突和合作的问题。并发进程可以按照多种方式进行交互。互相之间不知道对方的进程可能需要竞争的资源，如处理器时间或对I/O设备的访问。进程间由于共享访问一个公共对象，如主存中的一块空间或一个文件，可能间接知道对方，这类交互中产生的重要问题是互斥和死锁。互斥指的是，对一组并发进程，一次只有一个进程能够访问一个给定的资源或执行一个给定的功能。互知技术可以用于解决诸如资源

2、争用之类的冲突，还可以用于进程间的同步，使得它们可以合作。后一种情况的一个例子是生产者/消费者模型。为解决互斥问题，已经开发了许多软件算法，其中最著名的是Dekker算法。这种方法的处理开销很高，并且产生逻辑错误的危险也很高。支持互斥的第二种方法涉及到专门的及其指令，这种方法减少了开销，但由于使用了忙等待，因而仍然是低效的。支持互斥的另一种方法是在操作系统中提供功能，其中最常见的两种技术是信号量和消息机制。信号量用于在进程间发送信号，并可以很容易的用于实施一个互斥规定。消息对实施互斥是很有用的，它还为进程间的通信提供了一种有效的方法。在Unix和Linux中，可以有几

3、种方式来实现同步互斥：z互斥锁和条件变量z读写锁z记录上锁zPosix信号量zSystemV信号量本章主要讨论解决互斥问题的两种方法，一种是软件算法，一种是信号量实现。4.1互斥算法软件方法是为在一个处理器或者共享主存的处理器机器上执行的并发进程实现的。4.1.2Peterson算法Dekker算法解决了互斥问题，但相对比较复杂，关于正确性证明也需要一定的技巧。Peterson提出了一种简单而优雅的方案。和Dekker算法一样，全局数组变量flag表示每个进程关于互斥的位置，全局变量turn解决同时冲突。#include#include

4、o.h>#definefalse0#definetrue1intflag[2];intturn;voidP0(){while(true){flag[0]=true;turn=1;while(flag[1]&&turn==1);//临界区flag[0]=false;//其余代码}}voidP1(){while(true){flag[1]=true;turn=0;while(flag[0]&&turn==0);//临界区flag[1]=false;//其余代码}}intmain(){flag[0]=false;flag[1]=false;parbegin(P0,P1);}

5、显然，互斥可以得到保证。考虑进程P0。一旦它把flag[0]设置为ture，P1不能进入其临界区；如果P1已经在自己的临界区中，则flag[1]＝true，且P0被阻止进入临界区。另一方面，还可以防止互相阻塞。假设P0在它的while循环被阻塞，这意味着flag[1]为true且turn＝1，则当flag[1]变成false或者当turn变成0时，P0都可以进入自己的临界区。现在穷举三种情况：1、P1不想进入临界区。这种情况是不可能的，因为它已经表示了想进入（flag[1]=false）。2、P1正在等待进入它的临界区。这种情况也不可能，因此如果turn＝1，P1就能

6、够进入它的临界区。3、P1正在重复使用它的临界区，从而垄断了对临界区的访问。这不可能发生，因此P1在每次试图进入自己的临界区之前都被迫把turn设置为0，从而给了P0进入的机会。因此，我们对两个进程间的互斥问题给出了一种简单的解决方案。此外，Peterson算法可以很容易的推广到n个进程的情况。4.2信号量4.2.1信号量原语信号量可以看作一个具有整数值的变量，在它之上定义三个操作：1.一个信号量可以初始化成非负数。2.wait操作使信号量减1。如果值变成负数，则执行wait的进程被阻塞。3.signal操作使信号量加1。如果值不是正数，则被wait操作阻塞的进程被解

7、除阻塞。wait和signal原语被假设是原子的，也就是说，它们不能被中断，每个例程被看作是一个不可分割的步骤。一个二元信号量的值只能是0或1。下面分别给出信号量和二元信号量原语的定义。structsemaphore{structsemaphore{intcount;enum(zero,one)value;queueTypequeue;queueTypequeue;}}voidwait(semaphores)voidwait(semaphores){{if(s.value==1)s.count--;s.value=0;if(s.count<0){{p