《【精品】【考研计算机专业课】武汉大学操作系统ppt课件 第3章 进程同步与通信1（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】武汉大学操作系统ppt课件 第3章 进程同步与通信1（可编辑.ppt（107页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【考研计算机专业课】武汉大学操作系统PPT课件 第3章 进程同步与通信13.1 同步同步与互斥与互斥的概念的概念n3.1.1 临界资源与临界区n临界资源：一段时间内仅允许一个进程使用的资源称为临界资源。n如：打印机、共享变量。n临界区：进程中访问临界资源的那段代码称为临界区，又称临界段。n同类临界区：所有与同一临界资源相关联的临界区。共享变量例nA：B：nR1=x；R2=x；nR1=R1+1；R2=R2+1；nx=R1；x=R2；n如果先执行A再执行B，则x值增加2。n若按顺序R1=x；R2=x；R1=R1+1；x=R1；R2=R2+1；x=R2；则x值增加1。这种错误称为“与时间有关的错误”
2、，产生的原因是没有互斥使用共享变量。临界资源访问过程n进入区n临界区n退出区n剩余区访问临界资源应遵循的原则n空闲让进：若无进程处于临界区时，应允许一个进程进入临界区。n忙则等待：当已有进程进入临界区，其他进程必须等待。n有限等待：应保证要求进入临界区的进程在有限时间内进入临界区。n让权等待：当进程不能进入自己的临界区时，应释放处理机。3.2 互斥的实现方法n互斥的实现既有硬件方法也有软件方法，下面将对进程互斥的一些实现方法进行介绍。3.2.1 互斥算法n有两个进程P0和P1互斥地共享某个临界资源。nP0和P1是循环进程，它们执行一个无限循环程序，每次使用该资源一个有限的时间间隔。算法算法1的
3、思想的思想n设置一个公用整型变量turn，用来指示允许进入临界区的进程标识。n若turn为0，则允许进程P0进入临界区；否则循环检查该变量，直到turn变为本进程标识；n在退出区，修改允许进入进程的标识为1。进程P1的算法与此类似。算法1的描述int turn0；P0：do while（turn!=0）；进程P0的临界区代码CS0；turn1；进程P0的其他代码；while(true)算法1的描述（续）P1：do while（turn!=1）；进程P1的临界区代码CS1；turn0；进程P1的其他代码；while(true)算法1存在的问题n此算法可以保证互斥访问临界资源，但两个进程必须以交替
4、次序进入临界区。n此算法不能保证实现空闲让进准则。算法算法2的思想的思想n设置标志数组flag 表示进程是否在临界区中执行，初值均为假。n在每个进程访问临界资源之前，先检查另一个进程是否在临界区中，若不在则修改本进程的临界区标志为真并进入临界区，n在退出临界区时修改本进程临界区标志为假。算法2的描述enum boolean false，true；boolean flag2false，false；P0：do while （flag1）；flag0true；进程P0的临界区代码CS0；flag0false；进程P0的其他代码；while(true)算法2的描述（续）P1：do while（flag
5、0）；flag1true；进程P1的临界区代码CS1；flag1false；进程P1的其他代码；while(true)算法2存在的问题n此算法解决了空闲让进的问题，但有可能两个进程同时进入临界区。n当两个进程都未进入临界区时，它们各自的访问标志值都为false，若此时刚好两个进程同时都想进入临界区，并且都发现对方标志值为false，于是两个进程同时进入了各自的临界区，这就违背了临界区的访问原则忙则等待。算法算法3的思想的思想n本算法仍然设置标志数组flag，但标志用来表示进程是否希望进入临界区。n在每个进程访问临界资源之前，先将自己的标志设置为真，表示进程希望进入临界区，然后再检查另一个进程的
6、标志。若另一个进程的标志为真，则进程等待；否则进入临界区。算法3的描述enum boolean false，true；boolean flag2false，false；P0：do flag0true；while （flag1）；进程P0的临界区代码CS0；flag0false；进程P0的其他代码；while(true)算法3的描述（续）P1：do flag1true；while （flag0）；进程P1的临界区代码CS1；flag1false；进程P1的其他代码；while(true)算法3存在的问题n该算法可以有效地防止两个进程同时进入临界区，但存在两个进程都进不了临界区的问题。n当两个进程
7、同时想进入临界区时，它们分别将自己的标志位设置为true，并且同时去检查对方的状态，发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区。算法4的思想n本算法的基本思想是算法3和算法1的结合。是一个正确的算法。n标志数组flag 表示进程是否希望进入临界区或是否正在临界区中执行。n还设置了一个turn变量，用于指示允许进入临界区的进程标识。算法4的描述enum boolean false，true；boolean flag2 false，false；int turn；P0：do flag0true；turn1；while （flag1&turn=1）；进程P0的临界区代码CS0；fl
8、ag0false；进程P0的其他代码；while(true)算法4的描述（续）P1：do flag1true；turn0；while （flag0&turn=0）；进程P1的临界区代码CS1；flag1false；进程P1的其他代码；while(true)3.2.2 硬件方法n用硬件方法实现互斥的主要思想是保证检查操作与修改操作不被打断。禁止中断方法n当进程执行临界区代码时，要防止其他进程进入其临界区访问，最简单的方法是禁止中断。n禁止中断能保证当前运行进程将临界区代码顺利执行完，从而保证了互斥的正确实现，然后再允许中断。用禁止中断方法实现互斥 关中断；临界区；开中断；开关中断方法的不足n限制
9、了处理机交替执行程序的能力，因此执行的效率将会明显降低；n将关中断的权力交给用户进程则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。硬件指令方法 n许多计算机中提供了专门的硬件指令，实现对字节内容的检查和修改或交换两个字节内容的功能。n使用这样的硬件指令就可以解决临界区互斥的问题。TS（Test-and-Set）指令nTS指令的功能可描述如下：boolean TS(boolean*1ock)boolean old；old=*lock；*lock=true；return old；用TS指令实现进程互斥n为每个临界资源设置一个共享布尔变量lock表示资源的两种状态：true表示正
10、被占用，false表示空闲。算法如下：while TS(&lock)；进程的临界区代码进程的临界区代码CS；lock=false；进程的其他代码；进程的其他代码；Swap指令（或Exchange指令）nSwap指令的功能可描述如下：Swap(boolean*a，boolean*b)boolean temp；temp=*a；*a=*b；*b=temp；用Swap指令实现进程互斥n为每个临界资源设置一个共享布尔变量lock表示临界资源状态；再设置一个局部布尔变量key用于与lock交换信息。算法如下：key=true；while(key！=false)Swap(&lock，&key)；进程的临界区
11、代码CS；lock=false；进程的其他代码；3.2.3 锁机制n锁是一个代表资源状态的变量，通常用0表示资源可用（开锁），用1表示资源已被占用（关锁）。n在使用临界资源前需先考察锁变量的值，如果值为0则将锁设置为1（关锁），如果值为1则回到第一步重新考察锁变量的值。当进程使用完资源后，应将锁设置为0（开锁）。上锁原语nlock（w）while（w=1）；）；w=1；开锁原语nunlock（w）w=0；用锁机制实现互斥n进程进程P1 进程进程P2 lock(w)；lock(w)；临界区；临界区；临界区；临界区；unlock(w)；unlock(w)；自旋锁n自旋锁是专为防止多处理器并发而引入
12、的一种锁，自旋锁是专为防止多处理器并发而引入的一种锁，它在内核中大量应用于中断处理等部分，因为中断它在内核中大量应用于中断处理等部分，因为中断处理程序中不允许睡眠。处理程序中不允许睡眠。n自旋锁最多只能被一个内核任务持有，如果一个内自旋锁最多只能被一个内核任务持有，如果一个内核任务试图请求一个已被争用核任务试图请求一个已被争用(已经被持有已经被持有)的自旋的自旋锁，那么这个任务就会一直进行忙循环锁，那么这个任务就会一直进行忙循环旋转旋转等待锁重新可用。要是锁未被争用，请求它的内等待锁重新可用。要是锁未被争用，请求它的内核任务便能立刻得到它并且继续进行。核任务便能立刻得到它并且继续进行。n持有自
13、旋锁的时间最好小于两次上下文切换的时间。持有自旋锁的时间最好小于两次上下文切换的时间。前述实现方法不能实现让权等待！即存在忙等待3.3 信号量信号量n信号量是由荷兰科学家Dijkstra提出的，是一种卓有成效的进程同步机制。3.3.1 信号量的定义信号量的定义n信号量由两个成员（s，q）组成，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。又称信号灯。n除信号量的初值外，信号量的值仅能由P操作（又称为wait操作）和V操作（又称为signal操作）改变。信号量的物理含义n信号量中的整型变量S表示系统中某类资源的数目。n当其值大于0时，表示系统中当前可用资源的数目；n当其值小于0
14、时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。P操作n设S为一个信号量，P（S）执行时主要完成下述动作：n SS1；nif（S 0）设置进程状态为等待；将进程放入信号量等待队列；转调度程序；V操作nV(S)执行时主要完成下述动作：nSS1；nif（S0）将信号量等待队列中的第一个进程移出；设置其状态为就绪状态并插入就绪队列；然后再返回原进程继续执行；注意nP操作可能阻塞执行进程，而V操作可以唤醒其他进程。nP、V操作在封锁中断的情况下执行，即一个进程在信号量上操作时，不会有别的进程同时修改该信号量。也就是说P、V操作是原语。3.3.2 利用信号量实现互斥利用信号量实现互斥n设S为两个
15、进程P1、P2实现互斥的信号量，S的初值应为1（即可用资源数目为1）。n只需把临界区置于P（S）和V（S）之间，即可实现两进程的互斥。互斥访问临界区的描述进程P1：进程P2：P(S);P(S);进程P1的临界区；进程P2的临界区；V(S)；V(S)；互斥信号量的取值范围n若2个进程共享一个临界资源，信号量的取值范围是：10-1n若只有1个进程使用临界资源n若1个进程使用临界资源，另1个进程等待使用临界资源n若N个进程共享一个临界资源，其取值范围如何？n若没有进程使用临界资源3.3.3 利用信号量实现前趋关系利用信号量实现前趋关系n例如：P1、P2、P3、P4、P5、P6为一组合作进程，其前驱图
16、如下所示，试用P、V操作完成这六个进程的同步。P1 P2 P6 P4 P3 P5解法解法1n设七个同步信号量a、b、c、d、e、f、g分别表示进程之间的前驱关系，如图所示，其初值均为0。这六个进程的同步描述如下：P1 P2 P6 P4 P3 P5abcdfeg解法解法1（1）P1（）执行P1的代码；v(a)；v(b)；P1 P2 P6 P4 P3 P5abcdfeg解法解法1（2）P2（）p(a)；执行P2的代码；v(c)；v(d)；P1 P2 P6 P4 P3 P5abcdfeg解法解法1（3）P3（）p(b)；执行P3的代码；v(e)；P1 P2 P6 P4 P3 P5abcdfeg解法解
17、法1（4）P4（）p(c)；执行P4的代码；v(f)；P1 P2 P6 P4 P3 P5abcdfeg解法解法1（5）P5（）p(d)；执行P5的代码；v(g)；P1 P2 P6 P4 P3 P5abcdfeg解法解法1（6）P6（）p(e)；p(f)；p(g)；执行P6的代码；P1 P2 P6 P4 P3 P5abcdfeg解法解法2n设五个同步信号量f1、f2、f3、f4、f5分别表示进程P1、P2、P3、P4、P5是否执行完成，其初值均为0。这六个进程的同步描述如下:解法解法2（1）P1（）执行P1的代码；v(f1)；v(f1)；P1 P2 P6 P4 P3 P5解法解法2（2）P2（）
18、p(f1)；执行P2的代码；v(f2)；v(f2)；P1 P2 P6 P4 P3 P5解法解法2（3）P3（）p(f1)；执行P3的代码；v(f3)；P1 P2 P6 P4 P3 P5解法解法2（4）P4（）p(f2)；执行P4的代码；v(f4)；P1 P2 P6 P4 P3 P5解法解法2（5）P5（）p(f2)；执行P5的代码；v(f5)；P1 P2 P6 P4 P3 P5解法解法2（6）P6（）p(f3)；p(f4)；p(f5)；执行P6的代码；P1 P2 P6 P4 P3 P53.3.4 经典进程同步问题经典进程同步问题n多道程序环境中的进程同步是一个非常有趣的问题，吸引了很多学者研究
19、，从而产生了一系列经典进程同步问题。1.生产者生产者消费者问题消费者问题n生产者消费者问题是最著名的进程同步问题。n它描述了一组生产者进程向一组消费者进程提供产品，它们共享一个有界缓冲池。缓冲池中的每个缓冲区可以存放一个产品，生产者进程不断生产产品并将产品放入缓冲池中，消费者进程不断从缓冲池内取出产品并消费。生产者生产者消费者问题示意图消费者问题示意图n同步关系有：当缓冲池满时生产者进程需等待，当缓冲池空时消费者进程需等待。诸进程应互斥使用缓冲池。P1P2Pm有界缓冲池C1C2Ck用信号量解决生产者消费者问题n设置两个同步信号量empty、full，其初值分别为n、0。n有界缓冲池是一个临界资
20、源，还需要设置一个互斥信号量mutex，其初值为1。n生产者消费者问题的同步描述如下：生产者 消费者 生产一个产品；p(empty)；p(mutex)；将一个产品送入缓冲区；v(mutex)；v(full)；p(full)；p(mutex)；从缓冲区中取一个产品；v(mutex)；v(empty)；消费一个产品；注意n无论在生产者进程还是在消费者进程中，P操作的次序都不能颠倒，否则将可能造成死锁。颠倒生产者进程中的P操作生产一个产品；p(mutex)；p(empty)；将一个产品送入缓冲区；v(mutex)；v(full)；mutex full empty 0 n -1当mutex=1，ful
21、l=n，empty=0，且生产者先执行时生产一个产品；p(mutex)；p(empty)；2.读者读者写者问题写者问题n一个数据对象（如文件或记录）可以被多个并发进程所共享，n其中有些进程只要求读数据对象的内容，而另一些进程则要求修改或写数据对象的内容，n允许多个读进程同时读此数据对象，n但是一个写进程不能与其他进程（不管是写进程还是读进程）同时访问此数据对象。读者写者问题分类n读者优先：当写者提出存取共享对象的要求后，仍允许新读者进入。n写者优先：当写者提出存取共享对象的要求后，不允许新读者进入。用信号量解决读者用信号量解决读者-写者问题写者问题n为解决读者写者问题，应设置两个信号量和一个共
22、享变量：n互斥信号量mutex，用于使读进程互斥地访问共享变量readcount，其初值为1；n共享变量readcount，用于记录当前正在读数据集的读进程数目，初值为0。n写互斥信号量writer，用于实现写进程与读进程的互斥以及写进程与写进程的互斥，其初值为1；读者描述 p(mutex)；if(readcount=0)p(writer)；readcount=readcount+1；v(mutex)；读数据集；p(mutex)；readcount=readcount-1；if(readcount=0)v(writer)；v(mutex)；写者描述 p(writer)；写数据集；v(write
23、r)；对读者写者问题的理解n请注意对信号量mutex意义的理解。nmutex是一个互斥信号量，用于使读进程互斥地访问共享变量readcount。该信号量并不表示读进程的数目，表示读进程数目的是共享变量readcount。3.哲学家进餐问题哲学家进餐问题n哲学家进餐问题描述有五个哲学家，他们的生活方式是交替地进行思考和进餐，n哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，n平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，n进餐完毕，放下筷子又继续思考。用信号量解决哲学家进餐问题用信号量解决哲学家进餐问题n用五支筷子的信号量构
24、成信号量数组：semaphore stick5；n所有信号量初值为1，1023401234笫i个哲学家的活动算法描述 p(sticki)；p(stick(i+1)%5)；进餐；v(sticki)；v(stick(i+1)%5)；思考；算法描述存在的问题n上述算法有可能引起死锁。对于这样的死锁问题有如下办法解决：n至多允许四个哲学家同时进餐。n仅当左、右两支筷子均可用时，才允许拿起筷子进餐。n奇数号哲学家先拿左筷子再拿右筷子，偶数号哲学家相反。4.睡眠的理发师问题n理发店里有一位理发师，一把理发椅和N把供等候理发顾客坐的椅子。n如果没有顾客，理发师睡眠，当一个顾客到来时叫醒理发师；n若理发师正在
25、理发时又有顾客来，那么有空椅子就坐下，否则离开理发店。用信号量解决睡眠的理发师问题n为解决睡眠的理发师问题，应使用三个信号量：ncustomers记录等候理发的顾客数（不包括正在理发的顾客）；初值为0nbarbers记录正在等候顾客的理发师数；初值为0nmutex用于互斥。初值为1n变量count记录等候的顾客数，它是customers的一份拷贝。之所以使用count是因为无法读取信号量的当前值。理发师描述p(customers)；/*是否有等候的顾客*/p(mutex)；count=count1；/*顾客数减1*/v(barbers)；/*理发师开始理发*/v(mutex)；理发；顾客描述
26、p(mutex)；if(count N）count=count+1 v(customers)；v(mutex)；p(barbers)；理发；else v(mutex)；/*无空椅子则离开*/3.3.5 信号量集机制-AND型信号量nAND型信号量的基本思想是：将进程在整个运行过程中需要的多类资源，一次性地全部分配给进程，待该进程使用完后再一起释放。只要有一个资源未能分配给该进程，其他所有资源也不分配。n我们称AND型信号量的P原语为SP或Swait，V原语为SV或Ssignal。SP操作 SP（S1，S2，Sn）if（S11&S21&Sn1）for（i=1;i=n;i+)Si=Si-1;els
27、e 将进程插入第一个小于1的信号量等待队列；将调用进程的程序计数器置为SP的第一条指令；SV操作SV（S1，S2，Sn）for（i=1；i=t1&S1=d1&Sn=tn&Sn=dn)for(i=1;i=n;i+)Si=Sidi；else 将进程插入第一个资源数小于ti或di的信号量的等待队列；将调用进程的程序计数器设置为SP的第一条指令；SVSV（S1,d1，S2,d2，Sn,dn）for（i=1；i=n notfull.wait;bufferin=item;in=(in+1)%n;count+;if notempty.queue notempty.signal;void entry get(
28、item)if count=0 notempty.wait;item=bufferout;out=(out+1)%n;count-;if notfull.queue notfull.signal;in=out=count=0;3.4.2 用管程解决生产者用管程解决生产者-消费者问题消费者问题n有了管程PC的定义之后，生产者-消费者问题描述如下：cobegin void producer(int i)while(true)produce an item in nextp;PC.put(nextp);coendvoid consumer(int i)while(true)PC.get(nextc)
29、;consumer the item in nextc;3.4.3 利用管程解决哲学家进餐问题n用三种不同状态表示哲学家的活动：进餐、饥饿、思考。（thinking，hungry，eating）state5；n为每个哲学家设置一个条件变量self（i），当哲学家饥饿又不能获得筷子时，用self来阻塞自己：n管程设置三个函数：pickup取筷子，putdown放筷子，test测试是否具备进餐条件。3.4.3 利用管程解决哲学家进餐问题Monitor Dining-Philosophers()condition state5;condition self5;void entry pickup(in
30、t i)statei=hungry;test(i);if statei!=eating selfi.wait;void entry putdown(int i)statei=thinking;test(i+4)%5);test(i+1)%5);void test(int k)if(state(k+4)%5!=eating&(statek=hungry)&(state(k+1)%5!=eating)statek=eating;selfk.signal;for(i=0;4;i+)statei=thinking;3.4.3 利用管程解决哲学家进餐问题Monitor Dining-Philosophers()cobegin void philosopher(int i)while(true)Thinking;Dining-Philosophers.pickup(i);Eating;Dining-Philosophers.putdown(i);coend