第五章并发性互斥和同步浙江工业大学

1并发性：互斥和同步第五章2并发(Concurrency)多道程序设计技术、多处理器技术以及分布式处理技术使得操作系统设计时必须要面对多个进程并发的问题，设计时需要考虑下列问题：并发进程间如何通信？怎么解决资源的共享和竞争？多个进程之间如何同步？处理器的时间如何分配？3并发进程间的制约关系在多道程序环境下，系统中各进程以不可预测的速度向前推进，进程的异步性会造成结果的不可再现性。为防止这种现象，异步的进程间推进受到两种限制：1.资源共享关系多进程共享资源，例如各进程争用一台打印机，这时各进程使用这台打印机时有一定的限制。每次只允许一个进程使用一段时间打印机，等该进程使用完毕后再将打印机分配给其它进程。这种使用原则称为互斥使用。4进程之间竞争资源面临三个控制问题：互斥（mutualexclusion)指多个进程不能同时使用同一个资源；死锁（deadlock)指多个进程互不相让，都得不到足够的资源；饥饿（starvation)指一个进程一直得不到资源（其他进程可能轮流占用资源）2.相互合作关系在某些进程之间还存在合作关系，例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行，由于这三个进程间存在着相互合作的关系，即先输入再计算、最后再打印的关系，所以这三个进程在并发执行时推进序列受到限制，要保证其合作关系正确，进程间这种关系称为同步关系。5一个简单的例子voidecho(){chin=getchar();chout=chin;putchar(chout);}6ProcessP1ProcessP2..chin=getchar();..chin=getchar();.chout=chin;.putchar(chout);chout=chin;putchar(chout);发生中断P1输入x，P2输入y结果：y显示了两次，而x没有显示原因：chin是共享的全局变量一个简单的例子7解决办法控制访问共享资源。必须强加一条规则：一次只允许一个进程访问共享资源。（互斥）8和并发相关的术语表5.1与并发相关的关键术语9临界资源象打印机这类资源一次只允许一个进程使用的资源称为临界资源。属于临界资源的有硬件打印机、磁带机等，软件有消息缓冲队列、变量、数组、缓冲区等。当然还有一类象磁盘等资源，它允许进程间共享，即可交替使用，所以它称为共享资源，而临界资源又称独享资源。10临界区(criticalsections)多个进程共享临界资源时必须互斥使用，将程序中使用临界资源的那一段代码称为临界区。如二个进程A和B它们的程序如下：A:{Inputdata1fromI/O1;Computer……;Printresults1byprinter;A临界区}B:{Inputdata1fromI/O2;Computer……;Printresults2byprinter;B临界区}进程A和B必须互斥地分别进入各自的临界区A和B11竞争条件多个进程或线程在读写一个共享数据时，结果依赖于它们执行的相对时间，这种情形叫竞争。例1:两个进程p1和P2，共享同一个全局变量a。P1和P2同时更新a，因此两个进程竞争地写变量a。a=？例2:两个进程P3和P4，P3:b=b+c,P4:c=b+c(初始值b=1,c=2)。若P3先执行,则结果为b=3,c=5;若P4先执行，则结果为b=4,c=312操作系统关注的问题跟踪每个进程的信息：通过PCB为进程分配和释放各种资源处理器时间：进程调度内存：内存管理文件：文件系统I/O设备：I/O管理保护进程的数据和资源，避免其他进程的干扰一个进程的功能和输出结果必须与执行速度无关（进程同步机制）13多个进程的交互进程间相互不知道对方：独立的进程，存在着资源竞争关系，会带来互斥、死锁和饥饿的问题进程间通过共享对象间接知道对方：带来互斥、死锁、饥饿和数据一致性的问题进程直接知道对方：进程间通过通信合作，会带来死锁和饥饿的问题14进程同步机制进程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。15所有的进程同步机制应遵循下述四条准则：空闲让进当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。忙则等待当已有进程进入自己的临界区时，即相应的临界资源正被访问，其它试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源。有限等待对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入“饥饿”状态。让权等待当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。16临界区的互斥操作17一个由临界区和剩余区1和剩余区2程序段组成的进程采用进程同步机制后的描述如下：beginremaindersection1；剩余区1进入区criticalsection；临界区退出区remaindersection2；剩余区2end进程同步机制在临界区前加上进入区，它负责对欲访问的临界资源状态进行检查，以决定是否允许该进程进入临界区还是等待。同时在临界区后加上退出区，它负责释放临界资源以便其它等待该临界资源的进程使用。18Constintn=/*进程的数目*/Voidp(inti){while(true){entercritical(Ra);//进入临界区/*criticalsection*/exitcritical(Ra);//退出临界区/*remainder*/}}Voidmain(){parbegin(p(1),p(2),…p(n));}当有进程在临界区时，任何其他想要访问临界区的进程必须等待19互斥的三种实现方法软件方法：由进程本身负责实施互斥，不需要操作系统支持。增加一定的开销硬件方法：使用专门的机器指令来实现互斥。可减少开销，但依赖于硬件，难以成为通用的解决办法操作系统层提供支持解决互斥信号量机制、管程机制和消息传递机制20互斥：软件支持Dekker算法第一次尝试intturn=0;Process0Process1....While(turn!=0)While(turn!=1){donothing}{donothing}/*criticalsection*//*criticalsection*/turn=1;turn=0;实现方法：若turn值等于该进程的进程号，则该进程可以进入临界区执行。21第二次尝试：每个进程都有自己可进入临界区的钥匙。enumboolean{false=0;true=1};booleanflag[2]={false,false}Process0Process1....While(flag[1])While(flag[0]){donothing}{donothing}flag[0]=true;flag[1]=true;/*criticalsection*//*criticalsection*/flag[0]=false;flag[1]=false;互斥：软件支持22第三次尝试：可能导致死锁enumboolean{false=0;true=1};booleanflag[2]={false,false}Process0Process1....flag[0]=true;flag[1]=true;While(flag[1])While(flag[0]){donothing}{donothing}/*criticalsection*//*criticalsection*/flag[0]=false;flag[1]=false;互斥：软件支持23第四次尝试：导致活锁enumboolean{false=0;true=1};booleanflag[2]={false,false}Process0Process1....flag[0]=true;flag[1]=true;While(flag[1])While(flag[0]){flag[0]=false;{flag[1]=false;/*延迟一段时间*//*延迟一段时间*/flag[0]=true;}flag[1]=true;}/*criticalsection*//*criticalsection*/flag[0]=false;flag[1]=flase;互斥：软件支持24Peterson算法booleanflag[2];intturn;VoidP0()VoidP1(){while(true){while(true){flag[0]=true;{flag[1]=true;turn=1;turn=0;While(flag[1]&&turn=1)While(flag[0]&&turn=0)/*donothing*//*donothing*//*criticalsection*//*criticalsection*/flag[0]=false;flag[1]=false;}}}}互斥：软件支持25中断禁用(InterruptDisabling)单处理器情况下，并发进程交替执行。处于运行状态的进程只有调用系统服务或被中断时才会将控制权交给操作系统。为保证对临界区的互斥，只要保证进程在临界区内不被中断即可。通过系统内核启用中断和禁用中断的原语来实现。缺陷：处理器执行效率降低对于多处理器环境下，无法保证互斥互斥：硬件支持26特殊的机器指令在单个指令周期内执行，是原子性的指令（不能被中断）在该指令执行时，任何需要访问内存的其他指令都将被阻塞两种常见的指令：Testset和exchange指令互斥：硬件支持27booleantestset(inti){if(i==0){i=1;returntrue;}else{returnfalse;}}i相当于锁值，i=0表示当前该临界区未被访问Testset指令28voidexchange(intregister,intmemory){inttemp;temp=memory;memory=register;register=temp;}交换存储器单元和寄存器单元的内容Exchange指令29发现bolt=0的进程是惟一可以进入临界区的进程30优点适用于在单处理器或共享内存的多处理器上任何数目的进程非常简单且易于证明可用于支持多个临界区缺点忙等待可能饥饿：多个进程等待进入临界区，选择哪个进程是随机的可能死锁：考虑优先级情况硬件方法31信号量(Semaphores)机制1965年，由荷兰学者Dijkstra提出（P、V分别是荷兰语的test(proberen)和increment(verhogen))一种卓有成效的进程同步机制。最初提出的是二元信号量（互斥）,推广到一般信号量（多值）（同步）。EdsgerW.Dijkstra32信号量(Semaphores)机制基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到它接收到一个特定的信号。这是一种卓有成效的进程同步工具，在长期广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量机制发展到记录型信号量机制，进而发展为“信号集”机制。现在信号量机制已广泛应用于OS中。33信号量(Semaphores)特殊的变量，称为信号量，用于发送信号一个进程为了通过信号量s发送信号,它需要执行原语semSignal(s)/V(s)一个进程通过信号量s接收信号,它需要执行原语semWait(s)/P(s)如果相应的信号没有接收到，该进程将被挂起，直接它所需的信号发送为止34信号量（记录型信号量）一个具有整型数值的变量被初始化为非负数(nonnegativenumber).semWait/P操作使信号量值减1。如果信号量值变为负数，则执行该操作的进程被阻塞。semSignal/V操作使信号量值增1。如果值小于或等于零，表示之前有进程在等该信号，则需要在该信号量的阻塞队列中唤醒一个进程。（该进程的状态如何变化？）35信号量原语的定义等待该信号量的进程队列