1、一一 同步与互斥问题同步与互斥问题 分析题意，确定同步、互斥或同步与互斥问题。分析题意，确定同步、互斥或同步与互斥问题。 设信号量，给出信号量表示的含义（公用，私用）设信号量，给出信号量表示的含义（公用，私用）和初始值。和初始值。 描述算法，注意死锁问题。描述算法，注意死锁问题。把一个长度为把一个长度为n的有界缓冲区的有界缓冲区(n0)与一群生产者进程与一群生产者进程P1，P2，Pm和一群消费者进程和一群消费者进程C1，C2，Ck联联系起来系起来 3.6.4 生产者生产者消费者问题消费者问题 设生产者进程和消费者进程是设生产者进程和消费者进程是互相等效互相等效的，其中，各生产者进程的，其中，各
2、生产者进程使用的过程使用的过程deposit(data)和各消费者使用的过程和各消费者使用的过程remove(data)可可描述如下：描述如下：1. 首先首先生产者生产者消费者问题是一个消费者问题是一个同步问题同步问题。即生产者和消费者。即生产者和消费者之间满足如下条件：之间满足如下条件： 1)消费者想消费者想接收数据接收数据时，有界缓冲区中至少有时，有界缓冲区中至少有一个一个单元是单元是满的满的 2)生产者想生产者想发送数据发送数据时，有界缓冲区中至少有时，有界缓冲区中至少有一个一个单元是单元是空的空的2. 由于有界缓冲区是临界资源，因此，各生产者进程和各消费者由于有界缓冲区是临界资源，因此
3、，各生产者进程和各消费者进程之间进程之间必须互斥执行必须互斥执行。 3.6.4 生产者生产者消费者问题消费者问题 公用信号量公用信号量mutex，保证生产者进程和消费者进程之间的互斥，保证生产者进程和消费者进程之间的互斥，表示表示可用有界缓冲区的个数，可用有界缓冲区的个数，初值为初值为1；信号量信号量avail为生产者进程的私用信号量，为生产者进程的私用信号量，表示表示有界缓冲区中的有界缓冲区中的空单元个数，空单元个数，初值为初值为n； 信号量信号量full为消费者进程的私用信号量，为消费者进程的私用信号量，表示表示有界缓冲区中非空有界缓冲区中非空单元个数，单元个数，初值为初值为0。从而有：从
4、而有： 3.6.4 生产者生产者消费者问题消费者问题 deposit(data)： begin P(avail) P(mutex) 送数据入缓冲区某单元送数据入缓冲区某单元 V(full) V(mutex) End remove(data)： begin P(full) P(mutex) 取缓冲区中某单元数据取缓冲区中某单元数据 V(avail) V(mutex) end 3.6.4 生产者生产者消费者问题消费者问题 哲学家就餐问题哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每人面前有
5、一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子每个人只能直接从自己的左边或右边去取筷子设设fork5为为5 个信号量，初值为均个信号量，初值为均1, forki 表示表示i号筷子被拿号筷子被拿（i= 0， 1， 2， 3， 4）Philosopheri：while (1) 思考；思考； P(forki); P(fork(i+1) % 5)； 进食；进食； V(forki); V(fo
6、rk(i+1) % 5)；解解以上解法会出现死锁，为防止死锁发生可采取的措施：以上解法会出现死锁，为防止死锁发生可采取的措施： 最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子拿筷子 给所有哲学家编号，奇数号的哲学家必须首先拿左边给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。的筷子，偶数号的哲学家则反之。 分分 析析 设设fork5为为5 个信号量个信号量, 初值为均初值为均1， forki 表表示示i号筷子被拿号筷子被拿 设信号量设信号量S
7、，初值为，初值为4 S用于封锁第用于封锁第5个哲学家个哲学家无死锁哲学家就餐问题无死锁哲学家就餐问题 解解1 1Philosopheri：while (1) 思考； P(S)P(forki); P(fork(i+1) % 5)； 进食；V(forki); V(fork(i+1) % 5)； V(S)设设fork5为为5 个信号量，初值为均个信号量，初值为均1， forki 表示表示i号筷子被拿号筷子被拿无死锁哲学家就餐问题无死锁哲学家就餐问题 解解2 2Philosopheri：Beginif i mod 2 = 0then 思考；思考；P(forki); P(forki+1 mod 5)；
8、进食；进食；V(forki); V(forki+1mod 5)；else 思考；思考；P(forki+1 mod 5); P(forki)； 进食；进食；V(forki+1 mod 5); V(forki)；二二 作业调度作业调度 画表格计算周转时间和带权周转时间画表格计算周转时间和带权周转时间 给出作业（进程）调度序列给出作业（进程）调度序列 计算平均周转时间和平均带权周转时间计算平均周转时间和平均带权周转时间4.4 调度算法调度算法 思想：思想：按作业和就绪进程来到的次序进行调度。这按作业和就绪进程来到的次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而种算法优先考虑在系统中等待
9、时间最长的作业，而不管它要求运行时间的长短。不管它要求运行时间的长短。 优点：优点：算法简单，公平，容易实现算法简单，公平，容易实现 缺点：缺点：对于短作业或短进程，等待时间长对于短作业或短进程，等待时间长作业调度算法作业调度算法FCFS（First come first serve）4.4 调度算法调度算法作业调度算法作业调度算法FCFS下面是下面是4 4个作业在系统中从提交、运行的信息。个作业在系统中从提交、运行的信息。作业作业提交提交时间时间运行运行时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周转时间带权周转时间18228.50.5390.149.50.2平均周转时间：平
10、均周转时间：T=1.725 T=1.725 平均带权周转时间平均带权周转时间W=6.875W=6.87581010.510.610 10.5 10.6 10.8 221.61.314166.54.4 调度算法调度算法 思想：思想：比较作业缓冲区中的作业预计的运行时间，比较作业缓冲区中的作业预计的运行时间，选择选择预计时间最短的作业预计时间最短的作业进入运行状态。进入运行状态。 优点：优点：算法简单，可得到最大系统吞吐率，效率高。算法简单，可得到最大系统吞吐率，效率高。 缺点：缺点：主要问题是对长作业不利，如果系统不断地主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长时间等待。接
11、收短作业，就会使长作业长时间等待。短作业优先算法短作业优先算法SJF （shortest job first）4.4 调度算法调度算法短作业优先算法短作业优先算法SJF作业作业提交提交时间时间运行运行时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周转时间带权周转时间18228.50.5390.149.50.2平均周转时间：平均周转时间：T=1.55 T=1.55 平均带权周转时间平均带权周转时间W=5.15W=5.15810.31010.110 10.8 10.1 10.3 22.31.10.814.61144.4 调度算法调度算法响应比响应比=响应时间响应时间/预计执行时间预计
12、执行时间 响应时间响应时间=等待时间等待时间+预计执行时间预计执行时间 所以响应比为：所以响应比为：1+作业等待时间作业等待时间/预计执行时间预计执行时间 思想思想：当需要从就绪队列中选择进程投入运行时，先计算每：当需要从就绪队列中选择进程投入运行时，先计算每个进程的个进程的响应响应比，选择比，选择响应响应比最高的进程运行比最高的进程运行 优点优点：短作业响应比高，执行时间短；长作业响应比随着等：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高，不会过长等待。既照顾了短作业、也考待时间增加而提高，不会过长等待。既照顾了短作业、也考虑到了长作业。虑到了长作业。 缺点缺点：每次调度前
13、计算响应比增加了系统开销。：每次调度前计算响应比增加了系统开销。最高响应比优先最高响应比优先HRN（highest response-ratio next）4.4 调度算法调度算法作业作业提交提交时间时间运行运行时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周转时间带权周转时间18228.50.5390.149.50.20平均周转时间：平均周转时间：T=1.625 W=5.675最高响应比优先最高响应比优先HRN810.11010.610 10.6 10.1 10.8 22.11.11.314.2116.5三三 地址映射地址映射 根据公式计算逻辑地址的页号和页内地址根据公式计算逻
14、辑地址的页号和页内地址 p=intA/L d=A mod L 根据页表查找页面号。根据页表查找页面号。 页面号乘以页长页面号乘以页长，加上位移量（加上位移量（d）计算逻计算逻辑地址辑地址 多次计算直到找到数据、指令为止。多次计算直到找到数据、指令为止。逻辑空间逻辑空间上的上的地址地址为：页号为：页号+页内地址，页内的页内地址，页内的地址空间是连续的，页之间不必连续。地址空间是连续的，页之间不必连续。199100页号p页内地址d如果给定的逻辑地址是如果给定的逻辑地址是A，页面大小是，页面大小是L，则，则页页 号号p和和页内地址页内地址d可以按以下公式求得：可以按以下公式求得： p=intA/L
15、d=A mod L例例：逻辑地址：逻辑地址100 页面大小页面大小 1k 5.4.1 页式管理的基本原理页式管理的基本原理5.4.2 静态页面管理静态页面管理地址变换：地址变换：根据逻辑空间的页号，查找页表对应项找到对应的根据逻辑空间的页号，查找页表对应项找到对应的物理页面号，物理页面号，页面号乘以页长页面号乘以页长，加上位移量（页内加上位移量（页内地址）地址）就是物理地址。每个作业的逻辑地址是连续就是物理地址。每个作业的逻辑地址是连续的，重定位到内存空间后就不一定连续了。的，重定位到内存空间后就不一定连续了。变换过程全部由变换过程全部由硬件硬件地址变换机构地址变换机构自动完成自动完成。 5.
16、4.2 静态页面管理静态页面管理地址变换：地址变换： 请求表请求表中读出中读出MOV r1，2500虚地址为虚地址为100 8*1024+452=8644 四四 页面置换页面置换 根据引用页面序列画出页面置换图根据引用页面序列画出页面置换图 给出被置换页面序列，调入内存页面序列给出被置换页面序列，调入内存页面序列 计算缺页次数，缺页率，命中率计算缺页次数，缺页率，命中率5.4.4 请求页式管理的置换算法请求页式管理的置换算法先进先出算法先进先出算法(FIFO- First Input First Output）, 先进入内存的页面先淘汰。先进入内存的页面先淘汰。 优点优点：实现简单。：实现简单
17、。 缺点缺点：常用的页会被淘汰。：常用的页会被淘汰。缺页率缺页率15/20=75%123412512345111444555555222111113333332222244123412512345111111555544222222111153333332222444444333Belady现象现象：分配给一个进程的：分配给一个进程的页面增加，反而出现缺页增页面增加，反而出现缺页增加的现象加的现象5.4.4 请求页式管理的置换算法请求页式管理的置换算法缺页率为缺页率为9/12=75%缺页率缺页率=10/12=83.3%原因是原因是没有考虑页的执行顺序没有考虑页的执行顺序5.4.4 请求页式管理
18、的置换算法请求页式管理的置换算法最优淘汰算法（OPT-Optimal replacement algorithm）：是理想算法。系统预测作业将要访问的页面。淘汰预测不被访问或长时间后才被访问中的页面。缺页率缺页率9/20=45%几乎无法实现几乎无法实现!5.4.4 请求页式管理的置换算法请求页式管理的置换算法最近最近最久未使用页面淘汰法（LRU - Least Recently Used）： 淘汰最近一段时间最久没访问的页面。 缺点：每页设访问记录，每次更新，系统开销大。缺页率缺页率12/20=60%五五 死锁避免死锁避免 先验证系统初始状态的安全性，找出安全先验证系统初始状态的安全性，找出安
19、全序列。序列。 根据申请资源情况，结合剩余资源检查申根据申请资源情况，结合剩余资源检查申请合理性。请合理性。 验证分配后系统安全性，给出安全序列，验证分配后系统安全性，给出安全序列，否则不能分配资源给相应进程。否则不能分配资源给相应进程。银行家算法实例银行家算法实例 假定系统有四个进程假定系统有四个进程P1,P2,P3,P4,三种类型的资三种类型的资源源R1,R2,R3,数量分别为数量分别为9，3，6，在，在T0时刻时刻的的资源分配情况如下：资源分配情况如下：ProcessMaxallocatedNeed FinishAvailableP13/2/21/0/02/2/2 false1/1/2P
20、26/1/35/1/11/0/2 falseP33/1/42/1/11/0/3 falseP44/2/20/0/2 4/2/0 false验证验证T0时刻的安全性时刻的安全性分析分析： 1. 四进程执行状态都是未完成，四进程执行状态都是未完成，Finish=false 2. 找找Pi，其需要的资源，其需要的资源need=有效资源有效资源work 3. 当前的当前的work=1/1/2， need P1 P2 P3 P4 (2/2/2), (1/0/2), (1/0/3), (4/2/0) 4. 找到找到P2满足条件，如果让满足条件，如果让P2运行结束，运行结束，验证验证T0时刻的安全性时刻的安
21、全性存在运行序列：存在运行序列：P2,P1,P3,P4ProcessWorkneedallocation Work-new FinishP21/1/21/0/25/1/1falseP12/2/21/0/0falseP31/0/32/1/1falseP44/2/00/0/2 false0/1/00/0/06/1/3true6/2/36/2/34/0/10/0/03/2/27/2/37/2/36/2/00/0/0truetruetrue0/0/03/1/49/3/49/3/45/1/44/2/29/3/6P2请求资源请求资源1，0，1 现在现在P2请求资源请求资源1/0/1，按照银行家算法检查：，
22、按照银行家算法检查： Request21/0/1=Need21/0/2 Request21/0/1=Available21/1/2 假定可以分配，修改假定可以分配，修改Available, Allocation, NeedProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/1P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/2 4/2/0false进行安全性检查进行安全性检查验证验证P2分配资源后的安全性分配资源后的安全性存在运行序列：存在运行序列：P2,P1
23、,P3,P4ProcessWorkneedallocation Work-new FinishP20/1/10/0/16/1/2falseP12/2/21/0/0falseP31/0/32/1/1falseP44/2/00/0/2 false0/1/00/0/06/1/3true6/2/36/2/34/0/10/0/03/2/27/2/37/2/36/2/00/0/0truetruetrue0/0/03/1/49/3/49/3/45/1/44/2/29/3/6P1请求资源请求资源1/0/1，按照银行家算法检查：，按照银行家算法检查：Request11/0/1 Available10/1/1条件
24、不满足，不能分配，让条件不满足，不能分配，让P1等待。等待。P1请求资源请求资源1，0，1P3请求资源请求资源0，0，1 现在现在P3请求资源请求资源0/0/1，按照银行家算法检查：，按照银行家算法检查： Request30/0/1=Need31/0/3 Request30/0/1=Available30/1/1 假定可以分配，修改假定可以分配，修改Available, Allocation, NeedProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/0P26/1/36/1/20/0/1falseP33/1/42/1
25、/21/0/2falseP44/2/20/0/2 4/2/0false进行安全性检查进行安全性检查P3分配资源后的安全性分配资源后的安全性分析分析：四进程执行状态都是未完成，：四进程执行状态都是未完成，Finish=false找找Pi，其需要的资源，其需要的资源need=当前的当前的work=0/1/0进程的进程的need P1 P2 P3 P4 (2/2/2), 0/0/1), (1/0/2), (4/2/0)找不到满足条件的找不到满足条件的Pi,因此资源因此资源P3不能分配本次资源，回退。不能分配本次资源，回退。ProcessMaxallocatedNeedFinishAvailableP
26、13/2/21/0/02/2/2false0/1/1P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/2 4/2/0falseP2请求资源请求资源1，0，1 现在现在P2请求资源请求资源1/0/1，按照银行家算法检查：，按照银行家算法检查： Request21/0/1=Need21/0/2 Request21/0/1=Available21/1/2 假定可以分配，修改假定可以分配，修改Available, Allocation, NeedProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/1P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/2 4/2/0false
