计算机操作系统第四

《计算机操作系统第四》由会员分享，可在线阅读，更多相关《计算机操作系统第四（75页珍藏版）》请在装配图网上搜索。

1、会计学1计算机操作系统第四计算机操作系统第四第1页/共75页1、作业和作业步l作业：程序+数据+作业说明书l作业步：作业运行期间的每个加工步骤例如：编译 连结装配 运行第2页/共75页第3页/共75页n法法n作业调度运行频率低，几分钟一次作业调度运行频率低，几分钟一次系统规模运行速度第4页/共75页低级调度（进程/短程调度）l决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作是最基本的调度，在三种类型的OS中都必须配置3.1.2、低级调度1、低级调度的功能l保存处理机的现场信息l按照某种算法选取进程l把处理机分配给进程第5页/共75页2、进程调度中的三个基

2、本机制l排队器l分派器（分派程序）l上下文切换机制3、进程调度方式l非抢占方式l抢占方式第6页/共75页1）非抢占方式：l一旦进程获得处理机，则一直执行，直到该进程完成或被阻塞l此方式下，可能引起进程调度的因素：（1）正在执行的进程执行完毕，或因发生某事件不能再继续执行（2）执行中的进程因提出I/O请求而暂停执行（3）在进程通信或同步过程中执行了某原语，P操作等l优点：简单、系统开销小，适合大多数批处理系统l缺点：无法满足紧急任务的需要，不适合实时系统第7页/共75页2）抢占方式：）抢占方式：l允许调度程序根据某原则，暂停正在执行的进程允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分

3、配，将处理机重新分配抢占原则：抢占原则：l优先权原则优先权原则 就绪的高优先权进程有权抢占低优先权进程的就绪的高优先权进程有权抢占低优先权进程的CPUl短作业优先原则短作业优先原则 就绪的短作业就绪的短作业(进程进程)有权抢占长作业有权抢占长作业(进程进程)的的CPUl时间片原则时间片原则 一个时间片用完后，系统重新进行进程调度一个时间片用完后，系统重新进行进程调度第8页/共75页中级调度（中程调度）l目的：提高内存利用率和系统吞吐量l按一定的算法将外存上已具备运行条件的挂起进程换入内存，挂到就绪队列上，准备执行；而将内存中处于阻塞状态的某些进程换出至外存。3.1.3、中级调度第9页/共75页

4、第10页/共75页仅具有进程调度的调度队列模型就 绪 队 列阻 塞 队 列CPU时间片完交互用户进程调度进程完成等待事件事件发生 具有高、低两级调度的调度队列模型就 绪 队 列阻 塞 队 列CPU时间片完作业调度进程调度进程完成等待事件1阻 塞 队 列阻 塞 队 列等待事件2等待事件n事件1发生事件2发生事件n发生后 备 队 列 具有高、低、中三级调度的调度队列模型就 绪 队 列绪就、挂 起 队 列CPU时间片完作业调度进程调度进程完成事件出现阻 塞 队 列挂起等待事件中级调度事件发生后 备 队 列塞阻、挂 起 队 列挂起第11页/共75页包括四部分时间：包括四部分时间：1）等待作业调度时间）

5、等待作业调度时间 2）等待进程调度时间）等待进程调度时间 3）执行时间）执行时间 4）进程等待）进程等待I/O操作完成时间操作完成时间第12页/共75页平均周转时间：niTinT11带权周转时间：TsTW 周转时间服务时间niTsTinW11平均带权周转时间：第13页/共75页（2）响应时间快评价分时系统 响应时间：从用户通过键盘提交一个请求开始直至系统首次产生响应为止。包括三部分时间：1）从键盘输入的请求信息传送到处理机的时间2）处理时间3）响应信息回送终端的时间第14页/共75页（3）截止时间保证）截止时间保证评价实时系统评价实时系统 截止时间：截止时间：任务必须开始执行的最迟时任务必须开

6、始执行的最迟时间，或必须完成的最迟时间。间，或必须完成的最迟时间。（4）优先权准则）优先权准则三种系统中皆适用三种系统中皆适用第15页/共75页2、面向系统的准则l系统吞吐量高评价批处理系统l处理机利用率好针对大中型系统l各类资源的平衡利用对大中型系统第16页/共75页第17页/共75页第18页/共75页第19页/共75页进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A010111B110011011001C21101102100100D31001022021991.99性能评价：性能评价：l周转时间周转时间 =完成

7、时间完成时间 到达时间到达时间l带权周转时间带权周转时间 =周转时间周转时间/服务（运行）时间服务（运行）时间第20页/共75页n完全没考虑作业的紧迫程度（某些完全没考虑作业的紧迫程度（某些特殊的）；特殊的）；n用户做出的估计时间带有很大的主用户做出的估计时间带有很大的主观性。观性。第21页/共75页2.259133.5141844E3.116182101252C2.678926731B1.5365.5111423D2.11带权周转时间84周转时间4完成时间FJS2.81带权周转时间94周转时间4完成时间FCFS4服务时间0到达时间平均A进程名 作调 业 度 情 算 况 法l周转时间周转时间

8、=完成时间完成时间 到达时间到达时间l带权周转时间带权周转时间 =周转时间周转时间/服务时间服务时间第22页/共75页1、优先权调度算法的类型第23页/共75页第24页/共75页第25页/共75页2、优先权的类型 1）静态优先权 在进程创建时确定的，在进程整个运行期间保持不变优先权利用某一范围的整数来表示，该整数称为优先数。如：07，0255确定优先权的依据：（1）进程类型（2）进程对资源的需求（3）用户要求第26页/共75页 注：规定优先数越小，其优先权越高4/348334C15/81517482B119118D带权周转时间周转时间155完成时间2优先权非抢占式优先权算法5服务时间0到达时间

9、A进程名 作调 业 度 情 算 况 法平均6.251.3例：非抢占式优先权算法第27页/共75页t(等待)优先权t(运行)优先权l2)动态优先权动态优先权在进程创建时创立的优先权，可随进程的推进或等在进程创建时创立的优先权，可随进程的推进或等待时间的增加而改变。如等待时间长，优先权升高待时间的增加而改变。如等待时间长，优先权升高。第28页/共75页 等待时间+要求服务时间优先权 =-要求服务时间 等待时间+要求服务时间 响应时间 响应比(Rp)=-=-要求服务时间 要求服务时间3、高响应比优先调度算法、高响应比优先调度算法(HRRN)l为每个进程引入动态优先权，随着等待时间为每个进程引入动态优

10、先权，随着等待时间增加优先权提高。增加优先权提高。优点：等待时间相同，短作业优先权高(即SPF)要求服务时间相同，等待时间长，优先权高(即FCFS)对于长作业，在等待足够时间后，可获得处理机第29页/共75页3.571528E2.2591344C1.177962B2.8142056D2.141带权周转时间83周转时间3完成时间3服务时间0到达时间平均A进程名 作调 业 度 情 算 况 法RC1+(9-4)/4=2.25RD1+(9-6)/5=1.6RE1+(9-8)/2=1.5RD1+(13-6)/5=2.4RE1+(13-8)/2=3.5执行顺序：ABCEDHRRN（R大，优先权高）第30页

11、/共75页1、时间片轮转法1）基本原理系统将所有的就绪进程按FIFO原则排成一个队列，将CPU分配给队首进程，执行一个时间片。在时间片内进程未完，则插入就绪队列未尾，CPU交给下一个进程。2）时间片大小的确定时间片略大于一次典型的交互所需要的时间。第31页/共75页3.3313173.33131744E2.259113.5141642C2673.67111231B5101336923D带权周转时间2.58.4周转时间144完成时间RRq=4带权周转时间3.4611.8周转时间3.751515完成时间RRq=14服务时间0到达时间平均A进程名 作调 业 度 情 算 况 法l周转时间周转时间 =完

12、成时间完成时间 到达时间到达时间l带权周转时间带权周转时间 =周转时间周转时间/服务时间服务时间第32页/共75页n才调度第二级队列中的进程运行，才调度第二级队列中的进程运行，依次类推依次类推；新进程可抢占低级；新进程可抢占低级进程的处理机。进程的处理机。第33页/共75页 多级反馈队列调度算法示意图CPU时间片完进程调度进程完成就 绪 队 列 一就 绪 队 列 二就 绪 队 列 三就 绪 队 列 n时间片完时间片完第34页/共75页就级1绪 队 列空就级2绪 队 列就级3绪 队 列运行等待12354时间片 小 大优先级 高 低第35页/共75页多级反馈队列调度算法的性能 多级反馈队列调度算法

13、能较好地满足各种类型用户（进程）的需要：l终端（交互）型作业用户l短批处理作业用户l长批处理作业用户第36页/共75页1、保证调度算法如果系统中有n个相同类型的进程同时运行，保证每个进程都获得相同的处理机时间1/n。2、公平分享调度算法使所有用户能获得相同的处理机时间。第37页/共75页第38页/共75页 1.实时调度是为了完成实时处理任务而分配处理机的调度方法。2.硬实时任务要求计算机系统必须在用户给定的时限内完成 3.软实时任务允许计算机系统在用户给定的时限左右处理完毕。提供更详细的调度信息：就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级等；含有硬实时任务的实时系统中，广

14、泛采用基于优先级的抢占式调度策略第39页/共75页l实时调度算法分类：n非抢占式轮转调度算法：只适用于一般实时信息处理系统n非抢占式优先级调度算法：优先级最高的实时任务排在就绪队列队首，当前任务终止或完成后才被调度。n 基于时钟中断抢占式优先级调度算法：新到的实时任务的优先级高于当前任务时，并不立即抢占CPU，而是等到时钟中断到来，才进行切换。用于大多数的实时系统中。n 立即抢占的优先级调度算法：这种算法适用于实时要求比较严格的实时控制系统。第40页/共75页1、最早截止时间优先算法（EDF）该算法根据任务的开始截止时间来确定任务的优先级。截止时间越早，优先级越高。该算法要求实时任务的就绪队列

15、按任务截止时间的早晚排序。调度程序总选择队首的任务执行。该算法可用于抢占式和非抢占式调度。t任务到达任务执行开始截止时间134211224433非抢占式调度方式第41页/共75页2、最低松弛度优先算法（LLF）该算法根据任务的松弛度来确定任务的优先级。松弛度越低，优先级越高。松弛度任务必须完成的时间运行时间当前时间 该算法要求实时任务的就绪队列按松弛度排序。调度程序总选择队首的任务执行。该算法主要用于抢占式调度方式。第42页/共75页松弛度任务必须完成的时间运行时间当前时间例：实时系统中有两个周期性实时任务A、B，任务A每20ms执行一次，执行时间10ms；任务B每50ms执行一次，执行时间2

16、5ms。采用抢占式LLF算法：t0 20 40 60 80 100 120 140 160A1 A2 A3 A4 A5 A6 A7 A8B1B2B3任务A B每次必须完成的时间松弛度t0 10 20 30 40 45 50 55 60 70 80A1=10B1=25A2=20B1=15A2=0B1=15A3=10B1=5A3=5B2=30此时执行B2A4=0B2=20A4完B2=10第43页/共75页3、优先级倒置问题 （1）问题的形成 即OS中广泛采用的优先级调度算法和抢占方式。举例:三个独立进程P1、P2、P3，优先级由高到低。P1、P3共享临界资源进行交互。代码：P1：.P(mutex)

17、;CS-1;V(mutex).;P2:.program2.;P3:.P(mutex);CS-3;V(mutex).;执行顺序：P3P2(抢占)P1（阻塞）P2(执行结束)P3(执行结束)P1(执行结束)问题：P1优先级最高，但最后执行结束第44页/共75页3、优先级倒置问题（续）（2）问题的解决方案方案2：建立在动态优先级继承基础上。规定：P1阻塞时由P3继承P1的优先级，一直保持到P3退出临界区。目的：防止P2进程插进来，延缓P3退出临界区。方案1：P3进入临界区后不允许处理机被抢占。适用情况：系统中临界区较短且不多。第45页/共75页第46页/共75页二、产生死锁的原因：l1、竞争资源l2

18、、进程间推进顺序非法第47页/共75页可抢占性资源：CPU、RAM等；不可抢占性资源：打印机、磁带机等；可重用性资源：打印机可消耗性资源：进程通信中的消息、数据等第48页/共75页l1.2 竞争不可抢占性资源引起死锁：系统中配备的非剥夺性资源的数量不能满足诸进程运行的需要时，会使进程因争夺资源而陷入僵局。打印机P1磁带机P21.3 竞争可消耗资源引起死锁：第49页/共75页2、进程间推进顺序不当引起死锁l进程推进顺序合法不会导致死锁l进程推进顺序非法可能会导致死图1：顺序合法消息1P1消息2P2P3消息3图2：顺序非法消息1P1消息2P2P3消息3第50页/共75页源请求链。源请求链。第51页

19、/共75页第52页/共75页第53页/共75页第54页/共75页n较上述两种方法的综合性能要好；较上述两种方法的综合性能要好；但系统配置资源的序号要稳定，固但系统配置资源的序号要稳定，固定的访问顺序不一定合理。定的访问顺序不一定合理。第55页/共75页例1：进程A占有3号资源，现在又申请5号资源占有资源号小于申请资源号，此申请可以满足。进程B占有5号资源，现在又申请3号资源由于53，所以此申请不能满足。进程B要想得到3号资源，必须先放弃5号以及所有编号比3大的资源。第56页/共75页 信号量定义：var chopstick 0,4 of semaphore;信号量初值均为1；第i(i=0,1,

20、2,3)位哲学家活动描述：第4位哲学家活动描述:while(true)while(true)P(chopsticki);P(chopstick0);P(chopstick(i+1);P(chopstick4);eating;eating;V(chopsticki);V(chopstick0);V(chopstick(i+1);V(chopstick4);thinking;thinking;第57页/共75页不安全状态安全状态死锁实质：把系统的状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可避免发生死锁第58页/共75页第59页/共75页进程进程 最大最大需求需求已已分分配配系统

21、系统可用可用P1P2P310495223系统资源总数：系统资源总数：12进程进程最大最大需求需求已已分分配配系统系统可用可用P1P2P310495232系统资源总数：系统资源总数：122、安全状态之例：转化第60页/共75页第61页/共75页3、安全性算法：、安全性算法：工作向量工作向量Work、Finish2、银行家算法：（1）Requesti=Need?（2）Requesti=Available?（3）修改相关向量的值（4）执行安全性算法第62页/共75页MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29

22、0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2资源总数资源总数 10 5 7进程资源某时刻系统资源分配情况A B CWork AllocationA B CA B CA B CFinishAllocationNeedWork进程资源安全序列(1)该时刻T0系统是安全的吗？解：利用安全性算法对该时刻的资源分配情况进行分析，方法如下图：1 2 2 2 0 0 5 3 2 true 0 1 1 2 1 1 7 4 3 true 4 3 1 2 1 1 7 4 5 true 6 0 0 3 0 2 10 4 7

23、true 7 4 3 0 1 0 10 5 7 true 3 3 25 3 27 4 37 4 510 4 7P 1P 3P 4P 2P 0第63页/共75页(2)若此时P1请求资源，发出请求向量Request1(1,0,2)系统可以为满足请求吗？解：系统按银行家算法进行检查：Request1(1,0,2)=Need1(1,2,2)Request1(1,0,2)=Available(3,3,2)系统先假定可为P1分配资源，修改相关向量值：利用安全性算法检查此时系统是否安全。具体：MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47

24、5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2资源总数资源总数 10 5 7进程资源某时刻资源分配情况3 0 20 2 02 3 0第64页/共75页5 3 27 4 37 4 57 5 510 5 7A B CWork AllocationA B CA B CA B Ctruetruetruetruetrue3 0 22 1 10 0 20 1 03 0 20 2 00 1 14 3 17 4 36 0 02 3 05 3 27 4 37 4 57 5 5P1P3P4P0P2Fini

25、shAllocationNeedWork进程资源安全序列MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2资源总数资源总数 10 5 73 0 20 2 02 3 0进程资源某时刻资源分配情况第65页/共75页A B CA B CA B CA B C3 3 2资源总数 10 5 77 4 31 2 26 0 00 1 14 3 10 1 02 0 03 0 22 1 10 0

26、 27 5 33 2 29 0 22 2 24 3 3P0P1P2P3P4AvailableNeedAllocationMax进程资源某时刻资源分配情况3 0 20 2 02 3 0（3）若此时P4请求资源，发出请求向量Request4(3,3,0)系统可以满足请求吗？解：系统按银行家算法进行检查：Request4(3,3,0)Available(2,3,0)因此，让P4等待。第66页/共75页A B CA B CA B CA B C3 3 2资源总数 10 5 77 4 31 2 26 0 00 1 14 3 10 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 2

27、2 2 24 3 3P0P1P2P3P4AvailableNeedAllocationMax进程资源某时刻资源分配情况3 0 20 2 02 3 0（4）若此时P0请求资源，发出请求向量Request0(0,2,0)系统可以满足请求吗？解：系统按银行家算法进行检查：Request0(0,2,0)=Need0(7,4,3)Request0(0,2,0)=Available(2,3,0)系统暂时先假定可为P0分配资源，并修改有关数据 进行安全性检查，Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，系统不能分配资源 0 3 07 2 32 1 0第67页/共75页1、

28、资源分配图 P112l含义：该图是由一组结点N和一组边E组成的一个对偶G（N，E）le=(Pi,ri)是资源请求边，e=(ri，Pi)是资源分配边3.7.1、死锁的检测第68页/共75页P1P2r1r2资源分配图资源请求边资源分配边进程资源第69页/共75页2、死锁定理l含义：S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。l简化方法：找一个既不阻塞又不孤立的进程结点，消去所有的边。最终，当所有进程结点都成为孤立结点，则该图称为可完全简化的，否则，称为不可完全简化的第70页/共75页P1P2r1r2资源分配图的简化过程例1：资源分配图的简化第71页/共75页练习题：对下图进行简化P1P2P3P4r1r2第72页/共75页第73页/共75页0 占用输入机 A 进程的进展占用打印机B 进程的进展第74页/共75页