进程互斥和同步ppt课件

1、第三章 进程互斥与同步 主要内容w 进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。w 进程互斥 w 进程同步w 利用信号量机制解决具体问题进程间的关系w 并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的制约关系：w 1 间接制约关系进程互斥）w 由于共享资源而引起的临界区内不允许并发进程交叉执行的现象。由共享公有资源而造成的对并发进程执行速度的间接制约w 2 直接制约关系进程同步）w 由于并发进程互相共享对方的私有资源所引起的直接制约。临界资源w 象打印机这类资源一次

2、只允许一个进程使用的资源称为临界资源。属于临界资源有硬件打印机、磁带机等，软件有消息缓冲队列、变量、数组、缓冲区等。当然还有一类象磁盘等资源，它允许进程间共享，即可交替使用，所以它称为共享资源，而临界资源又称独享资源。举例:临界资源P1: R1=count;R1=R1+1;count=R1;P2:R2=count;R2=R2+1;count=R2;进程P1和P2共享变量count, R1和R2是处理机中的寄存器若执行顺序变为P1: R1=count;P2:R2=count;P1:R1=R1+1;count=R1;P2:R2=R2+1;count=R2;临界区Critical sectionsw

3、 多个进程共享临界资源时必须互斥使用，例如A和B两个进程都需要使用打印机，它们必须互斥使用。如果为了保证结果的正确性限制A、B二进程推进序列，规定进程A执行好再执行进程B，这样的限制就显得过死，因为它已不能保证进程A、B能并发执行，所以必须把限制减少到最少，以尽可能支持并发执行。为此把各进程分解，把访问临界资源的那段代码称为临界区与其它段代码分割开来，只对各种进程进入自己的临界区加以限制，即各进程互斥地进入自己的临界区。 举例:临界区While ( 1 ) entry_section; /申请进入critical_section; /临界区exit_section;/声明退出进程同步机制w 进

4、程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。w 多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。w 准绳w 空闲让进w 忙则等待w 阻塞等待w 有限等待w 一个由临界区和剩余区1和剩余区2程序段组成的进程采用进程同步机制后的描述如下：w remainder section 1； 剩余区1w 进入区;w critical section ； 临界区w 退出区;w remainder section 2 ； 剩余区2ww 进程同步机制在临界区前加上进入区，它负责对欲访问的临

5、界资源状态进行检查，以决定是允许该进程进入临界区还是等待。同时在临界区后加上退出区，它负责释放临界资源以便其它等待该临界资源的进程使用。w 实现进程互斥和同步的信号量机制有软件方法、硬件指令方法、信号量机制和管程等。互斥-软件的忙等待方法-1算法1int flag2= 0, 0 Cobeginvoid P0(void)while( 1 ) while ( flag1 = 1) ;flag0 = 1; /P0的临界区代码flag0 = 0;.; / P0的非临界区代码void P1(void)while( 1 ) while ( flag0 = 1) ;flag1 = 1; / P1的临界区代码

6、flag1 = 0;.; / P1的非临界区代码Coend互斥-软件的忙等待方法-2算法2int turn = 0;Cobeginvoid P0(void)while( 1 ) while ( turn != 0 ) ; /P0的临界区代码turn = 1;.; / P0的非临界区代码void P1(void)while( 1 ) while ( turn != 1 ) ; / P1的临界区代码turn = 0;.; / P1的非临界区代码Coend1.P0每小时进一次而P1每小时进入1000次2.若某进程发生意外永远不能运行.互斥-软件的忙等待方法-3w Peterson 1981w 为了防

7、止二进程为进入临界区而无限期等待，又设置变量turn，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn标志，不允许另一个进程进入，这时再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当二个进程同时要求进入临界区时，只允许一个进程进入临界区。 w 仅适用于两个进程互斥互斥-软件的忙等待方法-3算法3Int flag2 = 0, 0 Int turn = 0; Cobeginvoid P0(void)while( 1 ) flag 0 =1; /P0申请进入临界区turn = 1;while( flag1 = 1 & turn =1) ; /等待获准进入; /

8、P0的临界区代码flag 0 =0;/声明退出临界区.; / P0的非临界区代码void P1(void)while( 1 ) flag 1 =1; /P1申请进入临界区turn = 0;while( flag0 = 1 & turn =0) ; /等待获准进入; /P0的临界区代码flag 1 =0;/声明退出临界区.; / P1的非临界区代码Coend互斥-硬件支持1-禁止中断w 提高临界区代码执行中断优先级w 这种方法在UNIX和Windows NT中都使用，它是在单机系统中有效地实现互斥的一种方法。w 因为在传统操作系统中，打断进程对临界区代码的执行只有中断请求、中断被接受后，

9、系统有可能还调用其它进程进入临界区，并修改此全局数据库。所以用提高临界区中断优先级方法就可以屏蔽了其它中断，保证了临界段的执行不被打断，从而实现了互斥。 禁止中断举例Void Pi(void)while ( 1 ) disable_interrupts; /临界区代码enable_interrupts; /非临界区代码在多处理机情况下，用提高临界段代码执行的中断优先级方法是无法保证互斥的，因为在一个处理机上提高中断优先级并不能阻止其它处理器上的中断，所以必须采用其它方法。互斥-硬件支持2-特殊机器指令1 Test-and-Set 处理机指令 对于同一主存块访问要求，即使两个处理机同时提出，存储

10、控制逻辑也只能让其中之一先访问，但在一个处理机的两个存储周期间却可以插入另一个处理机的存储周期。现在用一条指令来完成检测和修改两个功能，这样中断和插入另一处理机的存储周期均不可能，所以不会影响此公用变量数据的完整性。Test-and-Set的语义int Test_and_Set( int target )int temp;temp = target;target = 1;return temp;Test-and-Set 的应用/lock为被测试变量为被测试变量,初值为初值为0,互斥进程互斥进程Pi(i=1,2.n)调用调用TSvoid Pi( void )while (1) while( Test_and_Set( lock);.; /Pi 临界区代码临界区代码lock = 0; /退出临界区退出临界区.;/Pi 非临界区代码非临界区代码互斥-硬件支持2-特殊机器指令2 swap 处理机指令,语义如下:void swap(int a, int b)int temp;temp = a;a = b;b = temp; Swap 的应用/lock为公用变量为公用变量,初值为初值为0(表临界资源空闲表临界资源空闲)/keyi为进程为