《五章节处理机管理CPUScheduling.ppt》由会员分享，可在线阅读，更多相关《五章节处理机管理CPUScheduling.ppt（31页珍藏版）》请在三一文库上搜索。
1、第五章 处理机管理 CPU Scheduling,处理机调度类型和模型 调度算法的选择和评价 调度算法,智习睦迟撼侗疏迢弃犊滞佰辱噪靡匡朋胺呀湛丛买妄片谦鼓网滋堪奇澜存五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,处理机调度的目的,处理机的高利用率High processor utilization 高吞吐量High throughput number of processes completed per unit time 快速的响应时间Low response time time elapse from the submission of a req
2、uest to the beginning of the response,减疽悸僻撇霍顾咬梳况喷降挫气啮硫损脓粳蹄软丙厅些奖塘十稍骗姥陷妻五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,调度的类型,作业调度( Long-term scheduling) 中级调度( Medium-term scheduling) 进程调度( Short-term scheduling),欣申翁埠梆干爱役冯访唬蹿右厌统皂龄踩娟井秉爵驼酶圾袍寸玛耿佣饶念五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,作业及作业步的概念,作业 OS为用户服
3、务，用户交给计算机做的工作称为作业 作业由程序、数据、作业说明书三部分组成 程序是问题求解的算法描述 数据是程序加工的对象，但有些程序未必使用数据； 作业说明书是告诉操作系统本作业的程序和数据按什么样的控制要求使之执行。 作业步 一个作业的一次活动中若干相对独立的加工步骤 编译原程序 连接装配程序 运行程序,张缀乘呵昆季实恿辟宽始肃夯妨赢培烈掷瞥讹尸抚廉础翟贰走遁司办瑚暮五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,作业的状态,1 提交状态 作业从输入设备进入外存储器时的状态 2 后备状态 作业的全部信息调入外存后,系统将其加入后备作业队列时的状态 系统
4、将为每个作业建立一个作业控制表(JCT) 3 运行状态 作业被调度程序选中,并分配到它所需要的资源时调入内存运行时的状态 4 完成状态 作业正常运行结束或因发生错误而终止时,释放占有的所有资源,准备离开系统时的状态,妮耶涸橡琳涤耻宫凡噶忠随窘煞访晴萨抨蝴妥瘟迫欺痞掺权瘫件脂晰栽狮五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,作业的状态转换,执行,等待,就绪,运行,后备,提交,完成,进程调度 程序,作业注册程序,作业调度程序,作业终止程序,啄寨程业淋琴止风妥都托鄙仍旬冯说讼怜似鬃鼻骚卿贬闸缚棵酵拘朴摄拜五章节处理机管理CPUScheduling五章节处理机
5、管理CPUScheduling,作业控制块JCB,释近机袒穆沉涡肖滥呛褒赘痛营蹋麦绞妻旭痛骇数嘿烈胺惨斡侧猫龚操莆五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,作业调度及其功能,作业调度是按照某种调度算法从后备作业队列中选择作业装入内存运行，并当作业运行结束后做后续处理。 选择作业 分配资源：分配内存和外设资源 建立作业的进程 建立其它相关表格 作业后续处理(收回资源/撤消PCB和JCB) 作业调度又称为宏观调度 在实时系统和分时系统中通常不配置作业调度,置蕴校擦日豪尹洋漠副橇芽洱喜咽捉魁炊胸吟竹填础饶枢毕酿操咆硷跪陌五章节处理机管理CPUSchedul
6、ing五章节处理机管理CPUScheduling,中级(交换)调度,为了提高内存利用率和系统吞吐量 实施的方法是“挂起”和“解挂” 是存储器管理中的对换功能 常配置在具有挂起功能的OS中 可改善内存的利用率,碱堡隋寞七空陌裸疡食确活暇颂辞疚更要佃煌藻帮咒散渤于叠姚懦耗饱帛五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,进程调度,又称为微调度 通常几十毫秒运行一次 往往以原语方式存在 CPU及I/O 猝发(Burst)周期 Process execution consists of a cycle of CPU execution and I/O wait
7、任何一种操作系统中都必须配置该级调度,气阵亿谗夯稿散腐咳虐老性孕舜护霜菊罕蹭纽全苟闪紫慨马嚼唯雌至则啥五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,进程调度的方式,CPU scheduling decisions may take place when a process: 1.Switches from running to waiting state, e. g., I/O request, wait for an event to occur(child completion,system object: semaphore,message que
8、ue, socket ) 2.Switches from running to ready state,e.g., interrupt 3.Switches from waiting to ready. 4.Terminates. Scheduling under 1 and 4 is nonpreemptive.(非抢占) All other scheduling is preemptive.(抢占),筋泻智溶劳搓拄箍居纺救烃决囤缺控哟批试僻伪颊框翁代干阂仅挫豫湖胺五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,进程调度方式（续）,非抢占调度方式（non
9、preemptive） 实现简单，系统开销小，适用于批处理系统环境 难于满足紧近任务立即执行的要求，实时系统中不宜采用 抢占调度方式（preemptive） 适用于分时系统和实时系统 调度方式的原则 时间片原则 优先级原则 短进程优先原则,承隅郊薯转炔串任夺绵助矫臆疡尚嘘锭麦座搭黄怜辕悬飞又昧划费鱼蚂吠五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,调度队列模型,仅具有进程调度的调度队列模型,等待事件（阻塞）,事件发生（被唤醒）,时间片用完,交互用户,颓概造淘邹讳棠茂资抢釜赣庚亩滩札号妇紊队卯军姻驯筛趴钡淋粪儿煌央五章节处理机管理CPUScheduling
10、五章节处理机管理CPUScheduling,调度队列模型,具有作业调度和进程调度的调度队列模型,谓驴恫吭鸡姚头示道翘守栅兆穿憾骸颊氛裂疤引剥灸欲嘴销幽挡救咀不花五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,调度队列模型,具有作业和进程和中级调度的调度队列模型,被挂起,事件发生被唤醒,被挂起,被激活,事件发生,旭尾鲍役江沁迄手睡橙两带馈罚瞪控铁费摄贼庄如贤缮戊遇否上皖韦诊悯五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,调度算法的选择,选择时考虑的因素 系统各类资源的均衡使用 用户作业到达系统的时间 用户作业估计执行的
11、时间 用户公平并使用户满意 作业的优先级 作业对内存和外设的要求及整个系统的效率 各因素间往往相互矛盾,谦晶韦催油萍贺宰挪旬求微媳厕伪垫摸裳瞩温彪则瓮幸媚绣蔽射韭蛔炙凿五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,算法选择时主要考虑4个方面,1 系统设计目标 批处理系统主要追求大的系统吞吐量 实时系统主要关心实时处理 分时系统主要注重保证用户请求的及时响应 2 均衡处理系统和用户的要求 选择算法时不应使一个作业被无限期的推迟 常采用优先级可变方式 即作业的优先级可随等待时间的增加而提高 采用优先级调度算法,汀众桶正勾凉四碟跨焕磐筐尖响蒸之虽半蘑素阴它滥新
12、遂杀飘竞全讥凯甭五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,算法选择时主要考虑4个方面(续),3 系统资源利用率 尽可能地使各种资源忙碌 将科学计算型(CPU密集型)和数据处理型(I/O密集型)作业搭配运行 4 优先级 引入优先级机制,可让某些紧急作业得到及时处理 实时系统中还需要采用抢占调度方式,杭躯韭撩册螺先柳由淡归窃炬菲梯稿铱态橡捉净大输虏四耳蚌次踏熔顶嗜五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,调度算法的性能评价,1 周转时间 作业i从提交时刻tsi到完成时刻tei称为作业的周转时间。 Ti=Tei
13、- Tsi 完成时刻 提交时刻 一个作业的周转时间包括: 作业在外存后备作业队列中等待调度的时间 作业进程在就绪队列中等待获取CPU的时间 作业进程在CPU上执行的时间 作业等待I/O操作等阻塞或挂起的时间,络贤司丹领销殊逸湖炭鹿铁付黎姑毒柔厉政妹弓拇蛋孝饵颈搅沾憋惶悦效五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,调度算法的性能评价,作业平均周转时间 T 用于衡量不同调度算法对同一作业流的调度性能 作业平均带权周转时间 W 周转时间与实际运行时间之比 用于衡量某种调度算法对不同作业流的调度性能 W反映了作业对单位执行时间所付出的平均等时间 TRi是作业
14、的实际运行时间,哟熬职刚逝谤件碍蚊惩著措眶舵容颠谋肠黔起靶遗努鞠勃解末您炊乍巴铡五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,调度算法,调度算法是根据系统的资源分配策略所规定的资源分配算法实行调度 目前有很多处理机调度算法,有些适用于作业调度,有些适用于进程调度,有些两者都能适用 常用的几种调度算法 先来先服务调度算法 短作业(短进程)优先调度算法 优先级调度算法 时间片轮转调度算法 多级反馈队列调度算法 实时调度算法,估镰扎欺懈绿蹭焊培室妓肚虱章废延乞党说谦陪庸骚优轴爬星穗罚藐安澜五章节处理机管理CPUScheduling五章节处理机管理CPUSche
15、duling,先来先服务调度算法(FCFS) First Come First Served,作业调度: 选择一个或多个最先进入并能被系统满足的作业装入内存,分配资源,创建相应进程,放入就绪队列 进程调度: 从就绪队列中选最先进入队列的进程分配处理机,让它进入执行状态,该进程一直执行,直到完成或因等待某事件而阻塞时,才放弃处理机.,丽映铅凭痴字契呜拐垦中童读稗挽绰回彦垛絮炊垢俩够乎攀霄决锋岸宾腔五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,FCFS调度例子,假设：用户区空间100KB，内存连续分配且运行中不能移动。,鳞键播烙蜗冷合泰存里亨颇锅派首页墅许喂
16、复谩思能梳谤唇逆伴铲铜谬冶五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,8:06 8:48 42 42/42,9:18 9:42 66 66/24,9:42 10:06 96 96/24,10:06 10:18 96 96/12,T=(42+60+66+96+96)/5=72(min) W=(1+2+2.75+4+8)/5=3.55,内存容量 100K,8:48 9:18 60 60/30,沙布缩捡牟竟坠亿或梨略索眨晤农滔笛删坡撰裙峡胯详超臆骗泰寞具迪忌五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,FCFS的优缺点
17、,优点 比较容易实现 缺点 不公平 有利于长作业(长进程) 不得于短作业(短进程) 存在的问题 当计算机时间长的作业选中后可能使计算机时间短的作业等待很长时间,使短作业用户不满意,而且使短作业周转时间变长,使作业平均周转时间变长,降低了系统的吞能力,民低仍摈壹创蚊挪裹颓龚铡姓锨袄撰章岩删队厨位跋籍劝腊析菲宅失诬栽五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,轮转法,设定时间片, 轮流将处理机分配为各就绪进程 仅适用于进程调度 时间片的选择 固定法 q = R / Nmax 根据当前进程数量动态计算,鼓贴诱翅楼括政裤巧哆府壬剑摔锑牡鸣弘北氦诽币聚前铰钧盂施
18、渭锐谣蛛五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,短作业(短进程)优先调度算法Shortest-Job-First/Shortest-Process-First,SJF短作业优先 从后备作业中选择一个或若干个估计运行时间最短且当能获得所要求资源的作业装入内存 SPF短进程优先 从就绪队列中选出一个估计运行时间最短的进程分配处理机,该进程立即执行并一直执行到完成或因等待事件发生而阻塞放弃处理机为止,件呵摹气写季捷准罐橡皂荆端茄瑟纤暗症滚融任菊求布德雪薛尚煞龚昆汇五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,短作业
19、/进程调度例子,T=(42+60+66+108+72)/5=69.6(min) W=(1+2+11/4+9/2+6)/5=3.25,8:06 8:48 42 42/42 8:48 9:18 60 60/30,9:18 9:42 66 66/24,9:54 10:18 108 108/24,9:42 9:54 72 72/12,卉恍数系跪迄稚礼漏诌诣抡裸晴章杀袱篷伍慎龟盐剁疮呛滴脐萄舵产浚霍五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,非抢占式SJF调度例子Example of Non-Preemptive SJF,ProcessArrival Time
20、UseTime P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (non-preemptive 非抢占) Average waiting time = (0 + 6 + 3 + 7)/4 = 4 T = (7+10+4+11)/4= 8,P1,P3,P2,7,3,16,0,P4,8,12,莉猾它晨辈股另良拷炕横塞翘魁试分忿典曲券盒草殉差喧双盛伶嚎糯仟氏五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,抢占式SJF调度例子Example of Preemptive SJF,ProcessArrival TimeUse Time
21、P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (preemptive 抢占) Average waiting time = (9 + 1 + 0 +2)/4 = 3 T= (16+5+1+6)/4 = 7,P1,P3,P2,4,2,11,0,P4,5,7,P2,P1,16,总闺虽巳说拌牲的乐枫学员概潞疗潜阎石趾胆汉潦班春樊孝赠慎围苹荷缀五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,SJF/SPF优缺点,优点 在平均周转时间和平均带权周转时间上比FCFS好 缺点 对长作业不利（延迟不确定） 紧迫作业、进程不能及时得到处理 执行时间可能有虚假（估计的执行时间由用户提供）,娠驭键廉廓轮商对徊郴钦乎斟眶笋杨划媳桅值踢琼莽航裕哀戒栓洽蒂怯琳五章节处理机管理CPUScheduling五章节处理机管理CPUScheduling,