第4章(进程同步与死锁)

1、计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院第第4 4章章 进程同步与死锁进程同步与死锁讲授教师讲授教师 屈屈 晓晓计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院学习目标学习目标1、理解进程同步2、掌握信号量的机制3、进程同步的应用4、理解管程及其作用5、理解进程的通信6、理解死锁的产生7、理解死锁的预防8、理解死锁的避免9、了解死锁的检测与解除计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院并发进程并发进程并发性：并发性： 是指两个或者多个事件在同一时间间隔内发生。在多道程序环境下，并发性是宏观上的。并发进程：并发进程： 由于

2、操作系统具有并发与共享等特性，系统中某一个进程的工作没有全部完成之前，另一个进程就可以占用CPU，开始工作，通常将这些可以同时工作的进程称为“并发进程”。并发进程的特性：并发进程的特性：(1)(1)、异步性、异步性 (2)(2)、竞争性、竞争性 (3)(3)、相互制约性、相互制约性 (4)(4)、与速、与速度有关。度有关。计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院与时间有关的错误与时间有关的错误并发运行的进程之间，可能没有任何联系，可能存在一定的关系，比如两个进程对同一个资源进行操作，这种情况下可能会产生与时间有关的错误与时间有关的错误。示例示例4-14-1：进程1和

3、进程2共享一个公共变量count. .a:a:temp1 = count;temp1 = count; temp1 = temp1 + 1; temp1 = temp1 + 1;b:b:count = temp1;count = temp1;. .c:c:temp1 = count;temp1 = count; temp1 = temp1 + 1; temp1 = temp1 + 1; count = temp1; count = temp1;d:d: print count; print count;进程进程1 1进程进程2 2示例示例4-24-2示例示例4-34-3计算机系统原理计算机系统

4、原理华南农业大学珠江学院华南农业大学珠江学院如何避免如何避免“与时间有关的错误与时间有关的错误”发生？发生？ 进程同步进程同步进程同步进程同步2-11 1、概念：、概念：进程同步是进程同步是OSOS管理共享资源和避免并发进程产生与时管理共享资源和避免并发进程产生与时间有关的错误的一种手段。包含两部分：间有关的错误的一种手段。包含两部分：(1)(1)、进程的互斥：、进程的互斥：(2)(2)、进程的同步：、进程的同步：计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院(1)(1)、进程的互斥：、进程的互斥： 指并发进程在竞争共享资源进，若进程正在使用共享资源，指并发进程在竞争共享

5、资源进，若进程正在使用共享资源，则其他想使用该资源的进程必须等待，直到使用者归还该资源则其他想使用该资源的进程必须等待，直到使用者归还该资源后才可使用，即共享资源互斥使用。后才可使用，即共享资源互斥使用。(2)(2)、进程的同步：、进程的同步： 指一个进程的执行依赖其他进程的执行情况，即一个进程在指一个进程的执行依赖其他进程的执行情况，即一个进程在没有收到其他进程的消息时必须等待，直到另一进程送来消息没有收到其他进程的消息时必须等待，直到另一进程送来消息后才继续执行。后才继续执行。进程同步进程同步2-2互斥：是因为共享资源而产生的制约关系。互斥：是因为共享资源而产生的制约关系。同步：因相互合作

6、而产生的制约关系。同步：因相互合作而产生的制约关系。计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院临界区临界区2-1当并发进程对共享资源进行激烈的竞争时，有些资源必须保护，当并发进程对共享资源进行激烈的竞争时，有些资源必须保护，防止两个或以上的进程同时存取或改变他们。防止两个或以上的进程同时存取或改变他们。如：打印机等设备和变量，队列等数据。如：打印机等设备和变量，队列等数据。临界资源：临界资源： 某段时间内只允许一个进程使用的资源。某段时间内只允许一个进程使用的资源。临界区：临界区： 把进程中涉及临界资源的那一部分操作，称为关于该临界资把进程中涉及临界资源的那一部分操作

7、，称为关于该临界资源的临界区源的临界区(critical section,cs)(critical section,cs)。计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院临界区域临界区域2-2几个进程若共享同一临界资源，它们必须互斥的使用这个资源，几个进程若共享同一临界资源，它们必须互斥的使用这个资源，否则将会造成信息混乱和操作出错。否则将会造成信息混乱和操作出错。如何保证如何各进程间互斥地执行临界区？如何保证如何各进程间互斥地执行临界区？应遵循如下的准则：应遵循如下的准则：(1)(1)、有空让进、有空让进( (临界资源的有效利用率临界资源的有效利用率) )(2)(2)、

8、无空等待、无空等待( (互斥的含义互斥的含义) )(3)(3)、多中选一、多中选一( (保证只有一个进程使用临界资源保证只有一个进程使用临界资源) )(4)(4)、有限等待、有限等待( (避免避免“死等死等”) )(5)(5)、让权等待、让权等待( (避免避免“忙等忙等”，当进程不能进入临界区，应立，当进程不能进入临界区，应立即释放处理机即释放处理机) )计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院同步机构同步机构对于进程的互斥和同步，对于进程的互斥和同步，OSOS必须有某种有效的控制手段，对互斥，必须有某种有效的控制手段，对互斥，要保证在要保证在临界区内不能交替执行临

9、界区内不能交替执行，而谁先进入临界区都可以；对，而谁先进入临界区都可以；对同步，则要保证合作进程必须相互配合共同推进，严格同步，则要保证合作进程必须相互配合共同推进，严格按照一定按照一定的先后顺序的先后顺序。在操作系统中，实现在操作系统中，实现互斥互斥和和同步同步的的机构机构统称为统称为“同步机构同步机构”。同步机构的实现：同步机构的实现：(1)(1)、互斥锁、互斥锁 ( (硬件方法硬件方法) )(2)(2)、信号量上的、信号量上的P-VP-V操作操作( (软件方法软件方法) )计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院互斥锁互斥锁2-1(1)(1)、互斥锁：、互斥锁

10、：互斥锁是借助硬件指令互斥锁是借助硬件指令Test and Set(TS)Test and Set(TS)来实现。来实现。两种状态：锁定两种状态：锁定(lock)(lock)、非锁定、非锁定(unlock)(unlock)每个对象都对应一个每个对象都对应一个“互斥锁互斥锁”标记，用来保证在任一时刻只标记，用来保证在任一时刻只能有一个进程访问该对象。能有一个进程访问该对象。思考：思考：用代码如何实现？用代码如何实现？void lock(void lock(锁变量锁变量W)W)test: if (w=1) goto test;test: if (w=1) goto test; else w = 1

11、; else w = 1; void unlock(void unlock(锁变量锁变量w)w) w = 0; w = 0; 计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院互斥锁互斥锁2-2互斥锁的缺点：互斥锁的缺点：(1)(1)、不满足、不满足“让权等待让权等待”的原则。的原则。(2)(2)、CPUCPU资源浪费，效率低。资源浪费，效率低。(3)(3)、难以实现复杂的互斥和同步。、难以实现复杂的互斥和同步。示例示例4-24-2: :用互斥锁实现用互斥锁实现例例4-14-1两并发两并发 进程访问同一个变量进程访问同一个变量count.count. lock(w);. lo

12、ck(w);a:a:temp1 = count;temp1 = count; temp1 = temp1 + 1; temp1 = temp1 + 1;b:b:count = temp1;count = temp1;unlock(w); unlock(w); . . lock(w);lock(w);c:c:temp1 = count;temp1 = count; temp1 = temp1 + 1; temp1 = temp1 + 1; count = temp1; count = temp1;d:d: print count; print count; unlock(w); unlock(w

13、);进程进程1 1进程进程2 2计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院信号量信号量3-1(2)(2)、信号量和、信号量和P-VP-V操作：操作：信号量的提出：信号量的提出：荷兰学者荷兰学者DijkstraDijkstra于于19651965年提出了年提出了“信号量信号量( (SemaphoreSemaphore) )”的概念，克服了忙碌等待现象，已经成为现代系统在进程之间的概念，克服了忙碌等待现象，已经成为现代系统在进程之间实现互斥与同步的基本工具。实现互斥与同步的基本工具。信号量：借交通管理中的信号量：借交通管理中的信号灯信号灯的含义来作为一种控制进程的含义来作

14、为一种控制进程互斥和同步的物理变量互斥和同步的物理变量。信号量的理解：信号量的理解：以停车场为例说明以停车场为例说明信号量的操作：信号量的操作：p-vp-v原语或原语或p-vp-v操作操作, ,严格设计的一对程序原语。严格设计的一对程序原语。计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院信号量信号量3-2信号量信号量S S本质上是一个本质上是一个整数计数器整数计数器，它被用来控制对公共资源的，它被用来控制对公共资源的访问，初始值为一个非负数。对信号量访问，初始值为一个非负数。对信号量S S的操作只能通过的操作只能通过P-VP-V操作操作进行。进行。具体定义如下：具体定义如

15、下：P(S):P(S):将信号量将信号量S S的值的值减减1 1，即，即S = S-1;S = S-1; 如果如果S0,S0,则该进程继续执行，否则该进程置为等待状态，则该进程继续执行，否则该进程置为等待状态，排入等待队列。排入等待队列。V(S):V(S):将信号量将信号量S S的值的值加加1 1，即，即S=S+1;S=S+1; 如果如果S0,S0,则释放队列中一个等待信号量的进程则释放队列中一个等待信号量的进程( (或优先级最高的进程或优先级最高的进程) )。计算机系统原理计算机系统原理华南农业大学珠江学院华南农业大学珠江学院信号量信号量3-3简单说，每执行一次简单说，每执行一次P P操作，即请求分配一个单位的资操作，即请求分配