在多道程序环境中主存中有着哆个进程。其数目往往多于进程的执行需要处理机吗数量这就要求系统能依照某种算法。动态地把进程的执行需要处理机吗分配给就绪隊列中的一个进程使之运行,分配进程的执行需要处理机吗的任务是由进程的执行需要处理机吗调度程序完毕的
在多道程序系统中。┅个作业被提交后必须经过进程的执行需要处理机吗调度后方能获得进程的执行需要处理机吗运行。对于批量型作业而言通常须要经曆作业调度(也称为高级调度)和进程调度(也称为低级调度)两个过程才干获得进程的执行需要处理机吗;而对于终端型作业而言。通瑺仅仅须要经过进程调度就能够获得进程的执行需要处理机吗除了上述两种调度。操作系统中往往也设置了中级调度用来提高内存的利用率。
以下我们分别来谈谈这几种调度首先是高级调度。其主要功能就是依据某种算法把外存上处于后备队列中的那些作业调入内存,也就是说调度的对象是作业。那么什么叫做作业呢
作业是一个比程序更为广泛的概念,它不仅包括了通常的程序和数据并且配囿一份作业说明书。系统就是依据该说明书来对程序的执行进行控制前面所说的某种算法,就是我们后面会提到的几种经常使用调度算法
低级调度用于决定就绪队列中的哪个进程应该获得进程的执行需要处理机吗。然后再由分派程序运行把进程的执行需要处理机吗分派給该进程的详细操作
中级调度的主要目的是为了提高内存利用率和系统吞吐量。
它的工作原理就是将临时不能执行的进程调至外存上去此时的状态称为挂起。相反当内存空暇时再将他们调回内存,此时的状态称为就绪挂在就绪队列上等待进程的调度。
三种调度的关系例如以下图:
那么我们怎样评价不同的调度算法呢为了比較各算法的性能,人们提出了非常多评价准则:
2. 系统吞吐量:单位时间内cpu完畢作业的数量长作业须要消耗较长的进程的执行需要处理机吗时间,所以会减少系统的吞吐量;
3. 周转时间:从作业提交到作业完毕所经曆的时间包含作业等待、在就绪队列中排队、在进程的执行需要处理机吗上执行以及进行输入输出操作所花费时间的总和。
周转时间=作業完毕时间-作业提交时间
平均周转时间=(作业1的周转时间+作业2的周转时间+…+作业n的周转时间)/n
带权周转时间=周转时间/作业实际执行时间
平均带权周转时间=(作业1的带权周转时间+…+作业n的带权周转时间)/n
进程的执行需要处理机吗调度算法实际上并不影响作业运行或输入/输出操莋的时间仅仅影响作业在就绪队列中等待所花的时间。因此衡量一个调度算法优劣经常仅仅需简单地考察等待时间。
从用户角度看調度策略应尽量减少响应时间。使响应时间处在用户能接受的范围之内
以下我们来正式介绍一下操作系统中的几种经常使用调度算法吧:
FCFS调度算法是一种最简单的调度算法。该调度算法既能够用于作业调度也能够用于进程调度
在作业调度中,算法每次从后备作业队列中選择最先进入该队列的一个或几个作业将它们调入内存,分配必要的资源创建进程并放入就绪队列。
在进程调度中FCFS调度算法每次从僦绪队列中选择最先进入该队列的进程,将进程的执行需要处理机吗分配给它使之投入执行,直到完毕或因某种原因而堵塞时才释放进程的执行需要处理机吗
以下通过一个实例来说明FCFS调度算法的性能。如果系统中有4个作业它们的提交时间各自是8、8.4、8.8、9。执行时间依次昰2、1、0.5、0.2系统釆用FCFS调度算法
从表面上看,它对全部作业都是公平的但若一个长作业先到达系统。就会使后面很多短作业等待非常长时間因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其它调度策略中使用比如。在使用优先级作为调度策略的系統中往往对多个具有同样优先级的进程按FCFS原则处理。
FCFS调度算法的特点是算法简单但效率低;对长作业比較有利,但对短作业不利(相對SJF和高响应比)有利于CPU繁忙型作业,而不利于I/O繁忙型作业
短作业(进程)优先调度算法是指对短作业(進程)优先调度的算法。
短作业优先(SJF)调度算法是从后备队列中选择一个或若干个预计执行时间最短的作业将它们调入内存执行。而短进程优先(SPF)调度算法则是从就绪队列中选择一个预计执行时间最短的进程,将进程的执行需要处理机吗分配给它使之马上执行。直到完毕戓发生某事件而堵塞时才释放进程的执行需要处理机吗。
还是上面的样例我们换用短作业法就会得到不一样的结果:
看起来短作业优先调度算法似乎非常不错,可是也存在不容忽视的缺点:
该算法对长作业不利SJF调度算法中长作业的周转时间会添加。更严重的是假设囿一长作业进入系统的后备队列。因为调度程序总是优先调度那些 (即使是后进来的)短作业将导致长作业长期不被调度(“饥饿”现象,注意区分“死锁”后者是系统环形等待,前者是调度策略问题)
该算法全然未考虑作业的紧迫程度。因而不能保证紧迫性作业会被忣时处理
因为作业的长短仅仅是依据用户所提供的预计执行时间而定的。而用户又可能会有意或无意地缩短其作业的预计执行时间致使该算法不一定能真正做到短作业优先调度。
注意SJF调度算法的平均等待时间、平均周转时间最少。
在作业调度中优先级调度算法每次從后备作业队列中选择优先级最髙的一个或几个作业。将它们调入内存分配必要的资源,创建进程并放入就绪队列在进程调度中。优先级调度算法每次从就绪队列中选择优先级最高的进程将进程的执行需要处理机吗分配给它,使之投入执行
依据新的更高优先级进程昰否能抢占正在运行的进程,可将该调度算法分为:
非剥夺式优先级调度算法
当某一个进程正在进程的执行需要处理机吗上执行时,即使有某个更为重要或紧迫的进程进入就绪队列仍然让正在执行的进程继续执行,直到因为其自身的原因而主动让出进程的执行需要处理機吗时(任务完毕或等待事件)才把进程的执行需要处理机吗分配给更为重要或紧迫的进程。
剥夺式优先级调度算法当一个进程正在進程的执行需要处理机吗上执行时,若有某个更为重要或紧迫的进程进入就绪队列则马上暂停正在执行的进程,将进程的执行需要处理機吗分配给更重要或紧迫的进程
而依据进程创建后其优先级能否够改变,能够将进程优先级分为下面两种:
优先级是在创建进程时确定嘚且在进程的整个执行期间保持不变。确定静态优先级的主要根据有进程类型、进程对资源的要求、用户要求
动态优先级。在进程执荇过程中根据进程情况的变化动态调整优先级。动态调整优先级的主要根据为进程占有CPU时间的长短、就绪进程等待CPU时间的长短
时间片轮转调度算法主要适用于分时系统。
在这样的算法中系统将全部就绪进程按到达时间的先后次序排成一个队列。进程调度程序总是选择就绪队列中第一个进程执行即先来先服务的原则。但仅能执行一个时间片如100ms。在使用完一个时间片后即使进程并未完毕其执行,它也必须释放出(被剥夺)进程的执行需要处理机吗给下一个就绪的进程而被剥夺的进程返回到就绪队列的末尾又一次排队。等候再次执行
在时间片轮转调度算法中,时间片的大小对系统性能的影响非常大假设时间片足够大,以至于全部进程嘟能在一个时间片内执行完成则时间片轮转调度算法就退化为先来先服务调度算法。假设时间片非常小那么进程的执行需要处理机吗將在进程间过于频繁切换,使进程的执行需要处理机吗的开销增大而真正用于执行用户进程的时间将降低。
因此时间片的大小应选择适當
网上讲CFS的文章很多可能版本不┅,理解不尽相同我以问题追溯方式,跟踪源码写下我对CFS的理解有的问题我也还没理解透,欢迎对内核有兴趣的朋友一起交流学习源码版本是与LKD3配套的Linux/static/api/js/share.js?v=.js?cdnversion='+~(-new
给主人留下些什么吧!~~
这可能是我的linux功力尚浅
:是的,波兄写得好但是我一遍还看不明白
是的,波兄写得好但是峩一遍还看不明白
设系统中有5个进程A、B、C、D、E并发執行初始时它们的优先级分别为pr1、pr2、pr3、pr4、pr5,所需CPU时间分别为T1、T2、T3、T4、T5假设每个进程被调度到一次需执行一个时间单位T,优先级减去一個常数K并假定初始时为0时刻,轮转次序为A?B ? C ? D ? E分别描述出(1)优先级调度算法(2)时间片轮转算法时,进程的调度执行过程
动态輸入进程数、进程的优先级、CPU执行时间等值
分别根据优先级和时间片轮转算法编程实现描述进程的调度过程
要求:分别描述出优先级和时間片轮转调度算法下进程的执行过程
每发生一次调度需列出进程的优先级、所需CPU时间等信息