操作系统原理第五章

《操作系统原理第五章》由会员分享，可在线阅读，更多相关《操作系统原理第五章（82页珍藏版）》请在金锄头文库上搜索。

1、1,第5章 并发性:互斥、同步和通信,并发执行的各个进程之间，既有独立性，又有制约性。 独立性：各进程可独立地向前推进 制约性：一个进程会受到其他进程的影响，这种影响关系可能有： 互斥 同步 通信,2,第5章 并发性:互斥、同步和通信,5.1 并发的原理 5.2 信号量机制 5.3 管程机制 5.4 进程通信,3,5.1 并发的原理,5.1.1 与时间有关的错误 5.1.2 互斥与同步的概念 5.1.3 临界区与进程互斥 5.1.4 硬件支持互斥的方法,4,5.1.1 与时间有关的错误,例：Pl，P2两并发进程共享变量count ，如果按如下顺序运行：,P1： R1=count； R1=R1+

2、1； count=R1；,P2: R2=count； R2=R2+1； count=R2；,结果: count的值+2，正确,5,5.1.1 与时间有关的错误,如果Pl，P2按如下顺序运行：,P1： R1=count； R1=R1+1； count=R1；,P2: R2=count； R2=R2+1； count=R2；,结果: count的值+1, 错误！,6,5.1.1 与时间有关的错误,原因： 1、共享了变量； 2、“同时”使用了这个变量。 解决办法： 1、取消共享（） 2、允许共享，不允许同时使用（） -进程互斥,7,5.1.2 互斥与同步的概念,1、进程间两种形式的制约关系 间接制约

3、关系：进程间要通过某种中介发生联系，是无意识安排的。 直接制约关系：进程间的相互联系是有意识的安排的。,8,2、进程的同步（直接制约）,进程的同步：synchronism 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。 具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态,5.1.2 互斥与同步的概念,9,例: 司机 P1 售票员 P2 while (true） while (true) 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； ,5.1.2 互斥与同步的概念,10,3、进

4、程的互斥（间接制约） mutual exclusion,由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。,5.1.2 互斥与同步的概念,11,5.1.3 临界区与进程互斥,1、临界资源 (critical resource） 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。 2、临界区（互斥区）：critical section 在进程中涉及到临界资源的程序段叫临界区 多个进程的临界区称为相关临界区,12,进程的互斥（间接作用）, a := a -1 print (a) ,P2,互斥,临界区的例子,13

5、,程序 段1,共享变量,程序 段2,程序 段3,临界区的例子,14,While (1) 进入区代码; 临界区代码; 退出区代码; 其余代码 ; ,3、实现各进程互斥进入临界区 进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entry section)。在临界区后面加上一段称为退出区(exit section)的代码,5.1.3 临界区与进程互斥,15,空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入 忙则等待：不允许两个以上的进程同时进入互斥区 有限等待：任何进入互斥区的要求应在有限的时间内得到满足 让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得

6、到CPU的使用权,4、使用互斥区的原则：,5.1.3 临界区与进程互斥,16,5、进程互斥的解决主要有两种: 硬件方法：分为中断禁用、专用机器指令两种（5.1.4节） 软件方法： 用编程解决，包括操作系统或程序设计语言中提供某种级别的支持，比如信号量机制和管程机制（5.25.3节 ），但常常忙等待,5.1.3 临界区与进程互斥,17,5.1.4 硬件支持互斥的方法,1中断禁用 为保证互斥，只需保证进程不被中断就可以了，通过系统内核为启用中断和禁用中断定义的原语实现。进程结构： While(true) 禁用中断; 临界区; 启用中断; 其余部分; ,缺点：效率低，不能用于多处理器结构。,18,5

7、.1.4 硬件支持互斥的方法,2专用机器指令 可用于多处理器机器 ，2条硬件指令：testset指令 和exchange指令,testset指令定义： boolean testset(int i) if (i=0) i=1; return true; else return false; ,19,5.1.4 硬件支持互斥的方法,testset指令实现进程的互斥访问,设置个共享变量bolt，其初值=0，代表资源空闲，其值为1代表资源被占用。实现互斥的各个进程为： while(true) while (!testset(bolt) ; /*当资源占用时等待*/ 临界区; bolt=0; 其余部分;

8、 ,20,5.1.4 硬件支持互斥的方法,exchange指令定义： void exchange (int register, int memory) int temp; temp=memory; memory=register; register=temp; 该指令交换一个寄存器和一个存储单元的内容,21,5.1.4 硬件支持互斥的方法,exchange指令实现进程的互斥访问,设置一个共享变量bolt,初值为0,各个并发的进程设置一个局部变量key,初值为1。实现互斥的各个进程描述为： while(true) key=1 while (key!=0) exchange (key, bolt)

9、; 临界区; exchange(key, bolt); 其余部分; ,22,5.1.4 硬件支持互斥的方法,特点：唯一可以进入临界区的进程是发现bolt等于0的进程，它将bolt置1排斥其它进程进入临界区。当该进程离开临界区时将bolt重新置0，允许另一个进程进入临界区。 缺点：不能满足“让权等待”的准则，造成处理机空等（忙等）。且只能解决互斥，不能用于同步。信号量机制能完满地解决上述问题。,23,5.2 信号量机制,5.2.1 信号量的概念 5.2.2 信号量的应用 5.2.3 生产者消费者问题 5.2.4 哲学家进餐问题 5.2.5 读者写者问题,24,5.2.1 信号量的概念,信号量(s

10、emaphore，信号灯)定义,信号量说明： semaphore s;,是一个记录型数据结构 定义如下： struc semaphore int value; pointer_PCB queue; ,25,5.2.1 信号量的概念,P、V操作,除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被称为P、V操作。 原子操作（atomic action）或简称“原语”(primitive)：在执行上不可中断的操作。,26,5.2.1 信号量的概念,P、V操作定义,P(s) /*= wait(s)）*/ s.value=s.value; if

11、 (s.value 0) block(s.queue) ,V(s) /*=signal(s) */ s.value=s.value+; if (s.value = 0) wakeup(s.queue) /*唤醒等待队列一个进程，使其变为就绪态 */ ,27,5.2.1 信号量的概念,P、V操作含义,信号量的物理含义： S0 表示有S个资源可用 S=0 表示无资源可用 S0 则 |S| 表示S等待队列中的进程个数 P、V操作的含义 P(S):表示申请一个资源 V(S)：表示释放一个资源。信号量的初值应0,28,5.2.2 信号量的应用,利用信号量实现进程互斥,while (true) P(mut

12、ex); critical section; V(mutex); remainder section; ,while (true) P(mutex); critical section; V(mutex); remainder section; ,Process1:,Process2:,29,5.2.2 信号量的应用,30,5.2.2 信号量的应用,利用信号量实现前驱关系（同步例子）,设置一个信号量S，其初值为0,P1； V(S);,P(S)； P2;,如此即可实现先执行P1，再执行P2,31,5.2.2 信号量的应用,利用信号量实现前驱关系,设5个信号量 semaphore fl=f2=f3

13、=f4=f5=O；,含义：分别表示进程 S1、S2、S3、S4、S5是否执行完成。,32,5.2.2 信号量的应用,各个进程的结构为：,33,5.2.3 生产者消费者问题,单缓冲区：生产者进程P和消费者进程C共用一个缓冲区，P生产产品放入缓冲区，C从缓冲区取产品来消费。,34,5.2.3 生产者消费者问题,单缓冲区的同步问题 P进程不能往“满”的缓冲区中放产品，设置信号量为empty C进程不能从“空”的缓冲区中取产品，设置信号量full 单缓冲区的互斥问题 P、C进程不能同时使用缓冲区,35,5.2.3 生产者消费者问题,单缓冲区的生产者消费者问题解,P： C： while (true) w

14、hile (true) 生产一个产品; P(full); P(empty) ; 从缓冲区取产品; 送产品到缓冲区; V(empty); V(full); 消费产品; ; ;,empty初值为1，full初值为0,36,5.2.3 生产者消费者问题,多个缓冲区：若干个生产者进程P1, P2, , Pn，若干个消费者进程Cl，C2，Cm。它们通过一个有界缓冲池(k个)联系。,37,5.2.3 生产者消费者问题,多缓冲区的同步互斥问题 同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。 互斥：所有进程应互斥使用缓冲池这一临界资源。,38,5.

15、2.3 生产者消费者问题,多缓冲区的生产者消费者问题解法,设置三个信号量mutex，empty，full的初始值分别为1，n，0；,思考：P操作的顺序可换吗？,39,5.2.3 生产者消费者问题,注意：此解中，无论是生产者进程还是消费者进程，V操作的次序无关紧要，但P操作的次序不能随意交换，否则可能造成死锁。例如，若将生产者进程中的P(empty)与P(mutex)的次序交换，则在一定条件下就会出现死锁现象。,40,5.2.4 哲学家进餐问题,5个哲学家围坐在圆桌旁，每人面前有一只空盘子，每2人之间放一只筷子，如图所示。 为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子。,41,5.2.4 哲学家进餐问题 -解,Semaphore chopstick5=1；/为每支筷子设置一个信号量 哲学家i的活动为： void philosopher (int i) while (true) 思考； P(chopsticki) ； /取左边筷子 P(chopstick(i+1) % 5) ； /取右边筷子 进食； V(chopsticki) ；