计算机操作系统期末复习1.ppt

1、期末复习仅仅复习重点章节,4.7.3 用信号灯实现进程的同步,（一）合作进程的执行次序 用进程流图来描述诸进程合作完成某一任务的次序，其规则如下,4.7.3 用信号灯实现进程的同步,用信号灯及P、V操作来描述左图 1、说明进程的同步关系 进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。 2、设置信号灯，说明含义、初值。 初值s13 = 0 表示进程P1尚未执行完成； 初值s23 = 0 表示进程P2尚未执行完成；,4.7.3 用信号灯实现进程的同步,P、V操作实现合作进程的同步,练习：设pa、pb、pc为一组合作进程，其进程流图如右图所示，试用信号灯的p、v操作实现

2、这三个进程的同步。,解答,(1) 三个进程的同步关系： 任务启动后pa先执行，当它结束后pb、pc可以开始执行， pb、pc执行完毕，任务终止。 (2) 信号灯设置： 设两个同步信号灯sb、sc分别表示进程pb和pc能否开始执行，其初值均为0。,解答,多缓冲的生产者消费者问题,问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。 即满足如下条件：（1）消费者想接收数据时，有界缓冲区中至少有一个单元是满的。（2）生产者想发送数据时，有界缓冲区中至少有一个单元是空的。,生产者与消费

3、者,生产者：当有界缓冲区中无空位置时，要等待； 向有界缓冲区放入物品后，要发消息（V操作）。 消费者：当有界缓冲区中无物品时，要等待； 从有界缓冲区取出物品后，要发消息（P操作） 。,多缓冲区的P-C问题之间的关系,一、同步关系： 对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待； 对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。 这种相互等待，并互通信息就是典型的进程同步。,多缓冲区的P-C问题之间的关系,二、互斥关系 缓冲区又是个临界资源，在多个进程

4、在生产产品时，它不允许在缓冲区的某一个单元同时存放产品 也不允许多个进程同时消费缓冲区的某一个单元产品，因此，还有个互斥的问题。,多生产者-消费者问题的一般解答,信号灯设置 两个同步信号灯empty:表示空缓冲区的数目，初值为有界缓冲区的大小n； full :表示满缓冲区的数目，其初值为0； 一个互斥信号灯- mutex：互斥信号灯，初值为1。,同步描述,程序描述,程序描述,例2 一道考研题,苹果桔子问题：桌上有一只盘子，最多可以容纳两个水果，每次只能放入/取出一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子里的

5、苹果。请用P，V操作来实现爸爸、妈妈儿子、女儿之间的同步和互斥。（南京大学2000年）,分析,这个问题实际上是两个生产者和两个消费者被连结到仅能放两个产品的缓冲器上。 生产者各自生产不同的产品，但就其本质而言，他们是同一类生产者。而消费者则各自取需要的产品消费，他们的消费方式不同。 程序如下：,main() tpyedef int semaphore; semaphore empty； /* 盘子里可以放几个水果 */ semaphore orange; /* 盘子里有桔子 */ semaphore apple; /* 盘子里有苹果 */ semaphore mutex; /*不能同时对盘子操

6、作的互斥量 empty = 2; /* 盘子里允许放一个水果*/ orange =0; /* 盘子里没有桔子 */ apple = 0; /* 盘子里没有苹果*/ mutex=1 cobegin/*可并发的进程*/ father(); mother(); son(); daugher(); coend ,father() while(手中还有苹果) P(empty); P(mutex)； 向盘中放苹果； V(mutex)； V(apple); ,mother() while(手中还有桔子) P(empty); P(mutex)； 向盘中放桔子； V(mutex)； V(orange); ,so

7、ni()/i=1，2 while(盘中还有苹果) P(apple); P(mutex)； 从盘中拿苹果； V(mutex)； V(empty); ,daugheri() /i=1，2 while(盘中还有桔子) P(orange); P(mutex)； 从盘中拿桔子； V(mutex)； V(empty); ,经典问题,（1）读者写者问题 问题描述：有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,第一类：读者优先,如果读者到： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读

8、3）有写者写，新读者等 如果写者到： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,第一类读者写者问题的解法,读者不固定情况：,第一类读者写者问题的解法,/初始化 mutex1=1；W=1；count=0； 读者： Readeri while (true) P(mutex1); readcount +; if (readcount=1) P (w);/禁止写 V(mutex1); 读 P(mutex1); readcount -; if (readcount=0) V(w);/可以允许写 V(mutex1); ,写者： Writej while (true) P

9、(w); 写 V(w); ,实例训练,有N个读者和两个编辑同时处理一篇文章。 对于读操作是可以同时进行的，若有读者正在读这篇文章，编辑就不能工作； 若编辑正在处理这篇文章，读者就不能作读操作。 编辑与编辑的工作也是互斥的，试用信号灯及P、V操作写出读者与编辑之间协同工作的程序描述。,解：mutex:用于读者与编辑、编辑与编辑的互斥信号灯，初值为1mutex1:用于对counter操作的互斥的信号灯，初值为1。,说明,读者写者问题，它为数据库访问建立了一个模型。例如，设想一个飞机定票系统，其中有许多竞争的进程试图读写其中的数据。,说明,在读者优先的进程中：现在假设一个写者到来，由于写操作是排他的

10、，所以它不能访问数据库，而是被挂起。 随后其他的读者到来，这样只要有一个读者活跃，随后而来的读者都被允许访问数据库。这样的结果是只要有读者陆续到来，它们一来就被允许进入，而写者将一直被挂起直到没有一个读者为止。 假如每2秒钟来一个读者，而其操作时间为5秒钟，则写者将永远不能访问数据库，或者我们说写者发生了饥饿现象。,思考,思考题：请大家试着写出写者优先的解法，并且考虑一下，能不能设计出一种算法使得无论对读者还是写者都是公平的，不会存在任何一方可能的饥饿现象。,写者优先（第二类读写/者问题）,写者优先： 条件： 1）多个读者可以同时进行读 2）写者必须互斥（只允许一个写者写，也不能读者写者同时进

11、行） 3）写者优先于读者（一旦有写者，则后续读者必须等待没有进入计数的进程，唤醒时优先考虑写者）,解1 读者数量固定,如果读者数是固定的，我们可采用下面的算法： rwmutex：用于写者与其他读者/写者互斥的访问共享数据 rmutex： 设该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作,写者优先,写者优先,解2 读者数不固定,如果读者数不固定，采用下面的算法： 设置三个互斥信号量： rwmutex 用于写者与其他读者/写者互斥的访问共享数据 rmutex 用于读者互斥的访问读者计数器readcount nrmutex 用于写者等待已进入读者退出，所有读者退出前互斥写操作,对比

12、：第一类读者不固定情况,什么是死锁？,死锁的定义： 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而无限期地僵持下去的局面 ，这种现象称为进程死锁。 这一组进程就称为死锁进程,死锁产生的条件,1971年Coffman总结出了对于可再使用资源，系统产生死锁必定同时保持四个必要条件： 互斥条件（mutual exclusion） 占有和等待条件（hold and wait） 不剥夺条件（no preemption） 循环等待条件（circular wait）,死锁产生的条件,互斥条件（mutual exclusion）：进程应互斥使用资源，任一时刻一个资源仅为一个进程独占，若另

13、一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。,死锁产生的条件,2.占有和等待条件（hold and wait）（或称部分分配条件）：一个进程请求资源得不到满足而等待时，不释放已占有的资源。,死锁产生的条件,不剥夺条件（no preemption）：任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。 循环等待条件（circular wait）：存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。,5.4.3 解决死锁问题的策略-预防死锁,一、解决死锁问题的几个策略 为了不发生死锁，必须设法破坏产生死锁的四个

14、必要条件之一。 条件1（互斥条件）：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；,5.4.3 解决死锁问题的策略-预防死锁,条件2（占有和等待条件）：容易否定也容易实现，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。 在资源分配策略上可以采取静态资源分配的方式一次性的把所需资源全部分配到位，否则就不分配。,5.4.3 解决死锁问题的策略-预防死锁,条件3（不剥夺条件）：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统

15、一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。,5.4.3 解决死锁问题的策略-预防死锁,条件4（循环等待条件）：通过有序资源分配法，可以破坏环路条件。 实际上系统还可以不采用部分分配，也就破坏了环路等待条件。,死锁的解决策略,归纳起来，可以采用以下策略之一来解决死锁问题： 忽略该问题 采用静态资源分配来预防死锁 采用有控分配方法来避免死锁 当死锁发生时检测死锁，并设法修复,5.4 死锁的预防静态分配策略,所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。 采用静态分配后，进程在执行中不再申请资源，因而，不会出现占有

16、了某些资源再等待另一些资源的情况，即破坏了第二个条件（占有和等待条件）的出现。,5.4 死锁的预防静态分配策略,静态分配策略实现简单，被许多操作系统采用。但这种策略严重地降低了资源利用率，其缺点也是明显的： 一个用户（进程）在程序运行之前很难提出将要使用的全部设备； 用户的作业必须等待，直到所有的资源满足时才能投入运行。实际上某些设备可能很晚的时候才使用,5.4 死锁的预防静态分配策略,设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到。 例如：一个分支语句，只有当程序出错的时候才将错误从打印机输出，但如果采用静态资源分配策略的话，也要把打印机分配给这个

17、程序，所以这种分配策略对系统来说是很浪费的。,5.4 死锁的预防层次分配,在层次分配策略下，资源被分成多个层次，一个进程得到某一层的一个资源后，它只能再申请在较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源。 层次分配策略将阻止第四个条件（循环等待条件）的出现。,5.4 死锁的预防层次分配,这种策略的一个变种是按序分配策略。把系统的所有资源排列成一个顺序，例如，系统若共有n个进程，共有m个资源，用ri表示第i个资源，于是这m个资源是：r1,r2,rm 规定如果进程不得在占用资源ri(1im)后再申请rj(ji)，即这种算法资源按申请多项资源时必须以上升的次序依次

18、申请。,5.4有序资源分配法,例如：进程P1，使用资源的顺序是R1，R2； 进程P2，使用资源的顺序是R2，R1； 若采用动态分配有可能形成环路条件，造成死锁。,5.4.5 死锁的避免,预防死锁： 采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁； 死锁避免： 与预防死锁相反，它允许系统中同时存在四个必要条件，如果能掌握并发进程中与每个进程有关的资源动态申请情况，做出明智和合理的选择，仍然可以避免死锁的发生。,5.4.5 死锁的避免,死锁避免不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能安全地分配。,5.4.5 死锁的避免,问题

19、是：是否存在一种算法总能做出正确的选择从而避免死锁？ 答案是肯定的，但条件是必须事先获得与进程有关的一些特定信息。本节将讨论使用银行家算法（bankers algorithm）避免死锁的方法。,银行家算法,避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法：它的模型基于一个小城镇的银行家，现将该算法描述如下：假定一个银行家拥有资金，数量为，被N个客户共享。银行家对客户提出下列约束条件：,银行家问题的例子 银行共有资金10万元，客户u1需贷款3万，客户u2需贷款8万，客户u3需贷款9万 。某一时刻：,5.4.1 死锁的概念行家的例子）,对于客户来说，只有所需要

20、的所有贷款全部得到满足，这样生意才能完成，之后才能把所贷款项归还。 贷不到款，客户死 贷款得不到归还，银行家死,单资源的银行家算法,单资源的银行家算法,在上图a中列出了4个客户，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以，他只保留10个单位的资金来为客户服务，而不是22个单位。 图（b）所示的状态是客户们各做自己的生意，在某些时刻需要贷款。客户已获得的贷款（已分配的资源）和可用的最大数额贷款称为与资源分配相关的系统状态。,单资源的银行家算法,一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所有的贷款(即所有的进程得到所需的全部资源并终止

21、)。,几种放置策略 首次适应算法 空闲区首址：低 高 ，尽可能用低地址空闲区 最佳适应算法： 空闲区大小：小 大 ，尽可能用小的空闲区 最坏适应算法： 空闲区大小：大 小，尽可能用大的空闲区,7.3.5 放置策略,7.3分区存贮管理,例：有一作业序列：作业A要求18K，作业B要求25 K，作业 C 要求30 K。试用首次适应算法、最佳适应算法、最坏适应算法处理该作业序列，看哪种算法合适？,例：有一作业序列：作业A要求18K，作业B要求25 K，作业 C 要求30 K。试用首次适应算法、最佳适应算法、最坏适应算法处理该作业序列，看哪种算法合适？,例：有一作业序列：作业A要求18K，作业B要求25

22、 K，作业 C 要求30 K。试用首次适应算法、最佳适应算法、最坏适应算法处理该作业序列，看哪种算法合适？,7.3 分区存储管理 7.3.5 几种放置策略,这三种放置算法的优劣很难区分，要具体情况具体分析。 例如：某时刻系统中有三个空闲区 其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB) 有一作业系列：(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)尝试分析那种放置策略可以满足作业的内存需求（分别画出空闲存储区链表）。,Address Translation Architecture,7.4.2 页式地址变换 二、虚地址结构,7

23、.4.2 页式地址变换 三、页式地址映射,7.4.2 页式地址变换 三、页式地址映射小结,1. 虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出 将虚地址转换成二进制的数； 按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）； 根据题意产生页表； 将低位部分位移量直接复制到内存地址寄存器的低位部分； 以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。,7.4.2 页式地址变换 三、页式地址映射,2.虚地址以十进制数给出 页号虚地址 / 页大小 位移量虚地址 % 页大小 根据题意产生页表； 以页号查页表，得到对

24、应页装入内存的块号 内存地址块号页大小位移量,7.4.2 页式地址变换 三、页式地址映射,例1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。 虚地址0AFEH 0000 1010 1111 1110 P1 W010 1111 1110 MR0100 1010 1111 11104AFEH,7.4.2 页式地址变换 三、页式地址映射,虚地址1ADDH 0001 1010 1101 1101 P3 W010 1101 1101 MR0010 1010 1101 11012ADDH,7.4.2 页式

25、地址变换 三、页式地址映射,例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。,7.4.2 页式地址变换 三、页式地址映射,虚地址 3412 P3412 2048 1 W 3412 mod 2048 1364 MR=9*2048+1364=19796 虚地址3412的内存地址 是：19796,7.4.2 页式地址变换 三、页式地址映射,虚地址 7145 P7145 2048 3 W7145 mod 2048 1001 MR=5*2048+1001=11241 虚地址7145的内存地址是：1124

26、1,一道考研题 西北工业大学（2002）,设有8页的逻辑空间，每页有1024字节，它们被映射到32块的物理存储区中，那么逻辑地址的有效位是（）位，物理地址至少是（）位。,最佳算法 选择以后不用的页或很长时间以后才能用的页淘汰 先进先出淘汰的算法 选择居留时间最长的一页淘汰 。 最久未使用淘汰算法（LRU算法） 选择最长时间未使用的页淘汰。,7.4.5 几种置换算法,7.4.5 几种置换算法,1.最佳页面算法（OPTimal replacemant algorithm） OPT)： 当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。,7.4.5 几

27、种置换算法,最佳页面算法是指对于任何m和p，r:调度算法有缺页中断率f最小。 但这种算法是不可能的。 Why? 因为,answer,淘汰以后不再需要的或最远的将来才会用到的页面。 它的缺页中断率最低。然而因为这个策略要求操作系统了解程序“未来”的信息，因而是不可能实现的。 通常可以作为判断其它淘汰算法优劣的标准。效果越靠近opt，算法就越优。,7.4.5 几种置换算法,2.先进先出算法 先进入内存的页，先退出内存。 实质上是淘汰在内存驻留时间最长的页。 其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。 这种算法简单，实现容易。,7.4.5 几种置换算法,3.最久未使用淘汰算法（LRU算法） 这种算法的实质：当需要淘