《操作系统原理与实践教程（第二版） 教学课件 ppt 作者 978-7-302-23697-9 os-ch 04》由会员分享，可在线阅读，更多相关《操作系统原理与实践教程（第二版） 教学课件 ppt 作者 978-7-302-23697-9 os-ch 04（97页珍藏版）》请在金锄头文库上搜索。
1、第4章 进程同步与死锁,4.1 进程的同步和互斥 4.2 经典同步问题 4.3 管程 4.4 进程通信 4.5 死锁 4.6 死锁的预防和避免 4.7 死锁的检测和解除,4.1.1 进程的同步,操作系统中的进程都是各自独立并以不可预知的速度向前推进，也就是一个进程相对另一个进程的执行速度是无法确定的，即它们具有异步性。但是对于需要相互合作的进程来说，其执行顺序需要在某些特定时刻进行协调，先达到条件的进程需要等待后到达的进程，此时这些进程间存在一种制约关系。,4.1.1 进程的同步,同步是进程间的直接制约关系，这种制约主要源于进程间的合作。进程同步的主要任务就是使并发执行的各进程之间能有效地共享
2、资源和相互合作，从而在执行时间、次序上相互制约，按照一定的协议协调执行，使程序的执行具有可再现性。,4.1.2 进程互斥,当多个进程需要使用相同的资源，而此类资源在任一时刻却只能供一个进程使用，获得资源的进程可以继续执行，没有获得资源的进程必须等待。 这是进程之间的间接制约关系。这种关系与源于进程间合作的同步关系不同，它们的运行具有时间次序的特征，谁先从系统获得共享资源，谁就先运行。这种对共享资源的排它性使用所造成的进程间的间接制约关系称为进程互斥。 互斥是一种特殊的同步方式,4.1.2 进程互斥,临界资源 在同一时段只能被一个进程使用的计算机资源 ，比如打印机 。 临界资源可能是硬件，也可能
3、是软件，如变量、数据、表格、队列等。它们虽然可以被若干个进程共享，但一次只能为一个进程使用。 临界资源的管理由操作系统完成，它通常将临界资源分配给首先提出使用申请的进程。,4.1.2 进程互斥,临界区(Critical Section) 为保证多个进程对临界资源进行正确的互斥访问，人们把每个进程中访问临界资源的那段代码使用特殊手段管理，这段代码被称为临界区 如果能保证诸进程互斥地进入自己的临界区，即可实现对临界资源的互斥访问。 进程在进入临界区之前，首先要对临界资源的使用情况进行查询，如果临界资源处于空闲状态，则该进程可以进入临界区，同时把临界资源的状态设置为正在使用状态；如果临界资源正在被使
4、用，那么该进程不能进入临界区。,4.1.2 进程互斥,进入区(Entry Section) 位于临界区前面的一段用于检查临界区使用状态的代码被称为进入区 。 退出区(Exit Section) 在进程完成对临界区的访问之后，要把临界区访问标志恢复为未被访问标志，完成该任务的代码段被称为退出区(Exit Section) 剩余区 进程中除了进入区、临界区和退出区之外的部分被称为剩余区。,4.1.2 进程互斥,一个描述临界资源的循环进程可以描述如下:,bool bFlag=true; do 进入区 临界区 退出区 剩余区 while (bFlag = true);,4.1.2 进程互斥,所有的同步
5、机制都应遵循下面的4条准则： （1）空闲让进 当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。 （2）忙则等待 当有一个进程在临界区时，其它欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。,4.1.2 进程互斥,（3）有限等待 对要求访问临界资源的进程，应保证进程能在有限时间内进入临界区，以免陷入“饥饿”状态。 （4）让权等待 当进程不能进入临界区时，应立即放弃占用CPU，以使其它进程有机会得到CPU的使用权，以免陷入“饥饿”状态。,4.1.3 信号量机制,信号量的发展历程 信号量(Semaphore)是荷兰学者Dijkstra在1965年提出的一种有效的进
6、程同步和互斥工具，它负责协调各个进程，以保证它们能够正确、合理地使用公共资源，有时也被称为信号灯。 经过长期广泛的应用实践，信号量机制已经有了很大的发展，形成了整型信号量、记录型信号量、信号量集等机制 。 信号量机制已经被广泛地应用到单处理机和多处理机系统以及计算机网络中。,4.1.3 信号量机制,整型信号量与P、V操作 在整型信号量机制中，信号量S是个整型变量，通常被初始化为相应资源的初始数量。 除了初始化之外，对信号量S只能通过wait和signal这两个标准的原子操作来访问 ，这就保证了当一个进程在修改某信号量时，没有其它进程同时对它进行修改 。 因为希腊语wait的首字母为P，sign
7、al的首字母为V，所以wait和signal操作通常又称为P、V操作。,4.1.3 信号量机制,wait操作可以表示为如下形式： void wait(int S) while (S=0) ; /当信号量S的值小于等于0时，做空操作， /否则将其值 减1 S = S-1; signal操作可以表示为如下形式： void signal (int S) S= S+1; ,4.1.3 信号量机制,记录型信号量 除了需要一个用于代表资源数目的整形变量value之外，又增加一个进程链表L，用于链接上述所有等待进程，这两者共同构成了记录型信号量。,4.1.3 信号量机制,记录型信号量的wait操作描述如下：
8、 void wait (semaphore S) S.value= S.value-1; /申请资源，尝试分配 if (S.value 0) /*若申请不成功，即在本次 操作前value的值小于等于零，说明系统中没有该资源，则阻塞本进程，并把本进程加入到S.L链表中*/ block(S.L); ,4.1.3 信号量机制,记录型信号量的signal操作描述如下： void signal (semaphore S) S.value = S.value+1; /释放资源，系统中该类资源当前可用数量增1 if (S.value = 0) /*若还有进程因该资源而阻塞，则唤醒阻塞进程，被唤醒者在阻塞链表
9、L的链首位置，从链表S.L头部移出一个进程P*/ wakeup(S.L); /唤醒被移出的进程P ,4.1.3 信号量机制,其中，block(S.L)操作用于阻塞调用它的进程，wakeup(P)操作用于唤醒链表L的链首阻塞进程P。这两个操作均以基本系统调用的形式由操作系统提供。,4.1.3 信号量机制,AND型信号量 AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，等到进程使用完毕后再一起释放。只要还有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给它。也就是说，对若干个临界资源的分配，采取原子操作的方式：要么全部分配给进程，要么一个也不
10、分配。 由死锁理论可知，这样就可避免上述死锁情况的发生。,4.1.4 信号量的使用方法,互斥进程组织结构模型,4.2 经典同步问题,生产者-消费者问题 读者-写者问题 哲学家进餐问题 理发师问题,4.2.1 生产者-消费者问题,问题描述 一批生产者生产特定结构的产品，并将其放入具有n个缓冲区的环状缓冲池，即若当前使用的是n-1号缓冲区，下一个可用的就是0号缓冲区。生产者一次只能生产并放入一个产品，消费者一次只能取出并消费一个产品，且生产者和消费者、消费者之间、生产者之间均对缓冲池互斥访问。在这个问题中，生产者和消费者使用固定的有限数目的n个缓冲区来进行任意数目消息的传递，因此也被称为有限缓冲区
11、问题。,4.2.1 生产者-消费者问题,显然，缓冲池是临界资源，因此需要为其设置一个互斥信号量mutex。此外，为了让生产者和消费者都能使用正确的空、满缓冲区，还需要设置两个资源信号量empty和full，其初值分别为空、满缓冲区的初值n和0。在进程选择缓冲区时，还需要使用两个特殊指针in和out，分别指向生产者使用的空缓冲区和消费者使用的满缓冲区。每当in或out当前指向的缓冲区被生产者或消费者使用后，均需要后移一个缓冲区。,4.2.1 生产者-消费者问题,使用伪代码对生产者-消费者问题描述如下： semaphore mutex = 1; semaphore full = 0; semaph
12、ore empty = n; buffType buffern; Producer() bufType *next, *in; while(TRUE) produceItem(next); /生产者生产产品放入next缓冲区暂存 P(empty)； /申请一个空缓冲区 P(mutex); /为缓冲池加锁，使其它进程无法对其中任一缓冲区操作 copyBuffer(next, in); /将next缓冲区中的数据放入in所指向的公共空缓冲区 in=(in +1) mod n; /in指针后移一位，下一位生产者到来时将使用新的空区 V(mutex); /为缓冲池解锁，使其它进程可以进入缓冲池操作 V
13、(full); /*释放已经装满数据的满缓冲区，V操作使得满缓冲区数量增1，若有因找不到满缓冲区而被阻塞的消费者时，该操作还会唤醒它*/ ,4.2.1 生产者-消费者问题,使用伪代码对生产者-消费者问题描述如下：（续） Consumer( ) bufType *next, *out; while (TRUE) P(full); /消费者申请一个满缓冲区 P(mutex); /为缓冲池加锁 copyBuffer(out, next); /*将out指针指向的满缓冲区整体复制到 next缓冲区暂存*/ out=(out+1) mod n; /*将out指针后移一位，下一个到来的消费者将使用out指
14、针新指向的满缓冲区*/ V(mutex); /为缓冲池解锁 V(empty); /*释放已经清空的空缓冲区，该V操作将使得空缓冲区数量增1，若有因找不到空缓冲区而阻塞的生产者时，该操作还会唤醒它*/ consumeItem(next); /消费者消费商品 ,4.2.1 生产者-消费者问题,有三个细节需要注意： 第一，对信号量的P操作要注意顺序问题，即当程序中出现多个P操作时顺序不能颠倒，应先对资源信号量进行P操作，再对互斥信号量进行P操作 。 第二，在同一个进程中，用于实现互斥的信号量的P、V操作必须成对出现。 第三，在合作进程之间，通过资源信号量传递信息。,4.2.2 读者-写者问题,问题描
15、述 该问题假设一种资源在两种截然不同的进程间共享，一类进程可以和同类的其它进程一起共享资源，且不会对资源进行改写，只获取资源的副本，它们的行为与去图书馆读书的读者很相似，因此被形象的称为读者(reader)；而另一类进程则能够对资源进行改写，且在使用资源的时候排斥其它任何类型的进程使用该资源，这样的行为又与书籍的作者类似，因此被称为写者(writer)。,4.2.2 读者-写者问题,读者-写者问题经常用来描述一组进程共享一个文件时，多个只读权限的进程可以同时共享该文件，一旦有进程对文件进行改写时，其它任何进程(无论是读者还是写者)均不可共享该文件。,4.2.2 读者-写者问题,读者-写者问题的
16、解决方案 第一种方案是读者优先，由于读者对资源没有修改且通常只需获取一个副本即可离开，因此其操作时间比较短，所以可以考虑让读者优先，即只要有一个读者持有资源，后继到达的读者可以被允许立即进入临界区，而后继到达的写者将被当前的读者排斥而无法进入临界区，只能阻塞自身。 这种方法中，只有第一个到达的读者才需要与写者竞争共享资源，只要读者获得共享资源后，在资源没有被释放之前，后继的读者都可以直接进入临界区访问。 这种读者优先的方案被称为第一读者-写者问题。,4.2.2 读者-写者问题,第二种解决方案是写者优先的。该方法中，当一个写者请求访问共享资源时，任一随后到达的读者进程必须等待，直到先到的读者完成共享资源的访问并释放该资源后才继续。 当第一个写者离开临界区后，由于写者的优先级高于读者，则第二个写者将进入临界区，读者将会等待。
