江苏龙网

  1. 主页 > 生活百科 > >

Linux操作系统中常用调度算法( 二 )

调度算法


（3）进程的转换时间 。若执行进程调度时的转换时间为t，时间片为q，为保证系统开销不大于某个标准，应使比值t/q不大于某一数值，如1/10 。
（4）CPU运行指令速度 。CPU运行速度快，则时间片可以短些；反之，则应取长些 。
（三）优先级法“急事先办”、“重要的事先办”，这是大家都熟知的办事原则 。先办就是优先处理，表明急事、重要的事有最高的优先级 。在操作系统中也经常使用优先级法作为作业调度和进程调度的算法 。利用优先级调度算法进行进程调度时，是从就绪队列中选出优先级最高的进程，把CPU分给它使用 。
在进程调度时，当前就绪队列中有最高优先级的那个进程获得CPU的使用权 。以后在该进程的运行过程中，如果在就绪队列中出现优先级更高的进程时，怎么办？有两种不同的处理方式 。
（1）非抢占式优先级法 。这种办法就是：当前占用CPU的进程一直运行下去，直到完成任务或者因等待某事件而主动让出CPU时，系统才让另一个优先级高的进程占用CPU 。
（2）抢占式优先级法 。这种办法就是：当前进程在运行过程中，一旦有另一个优先级更高的进程出现在就绪队列中，进程调度程序就停止当前进程的运行，强行将CPU分给那个进程 。
进程的优先级如何确定呢？一般说来，进程优先级可由系统内部定义或由外部指定 。内部决定优先级是利用某些可度量的量来定义一个进程的优先级 。例如，进程类型、进程对资源的需求（时间限度、需要内存大小、打开文件的数目、I/O平均工作时间与CPU平均工作时间的比值等），用它们来计算优先级 。外部优先级是按操作系统以外的标准设置的，例如，使用计算机所付款的类型和总数，使用计算机的部门以及其他的外部因素 。
进程的优先级是“一定终身”、还是“随机应变”？这涉及两种确定进程优先级的方式：静态方式和动态方式 。
（1）静态优先级是在创建进程时就确定下来的，而且在进程的整个运行期间保持不变 。往往利用上述的内部定义或外部指定的办法规定进程的静态优先级 。
优先级一般用某个固定范围内的整数表示，例如0～7或0～4095中的某一个数 。这种整数称作优先数 。注意，优先级与优先数的对应关系因系统而异，在有些系统中优先数越大，优先级越高；而另外一些系统则恰恰相反，优先数越小，优先级越高，如UNIX/linux系统就是这样 。本书采用“优先数小、优先级高”的表示方式 。
静态优先级调度算法易于实现，系统开销小 。但其主要问题是会出现“饥饿”现象 。即某些低优先级的进程无限期地等待CPU 。在负载很重的计算机系统中，如果高优先级的进程很多，形成一个稳定的进程流，就使得低优先级进程任何时候也得不到CPU 。
（2）动态优先级是随着进程的推进而不断改变的 。解决低优先级进程“饥饿”问题的一种办法是“论年头” 。这种办法使系统中等待CPU很长时间的进程逐渐提升其优先级 。例如在UNIX系统中，正在运行的用户进程随着占用CPU时间的加长，其优先数也逐渐增加（优先级降低）；而在就绪队列中的用户进程随着等待CPU时间的加长，其优先数递减（优先级渐升） 。经过一段时间后，原来级别较低的进程的优先级就升上去，而正在运行进程的级别就降下来，从而实现“负反馈”作用—— 防止一个进程长期占用CPU，也避免发生“饥饿”现象 。
对于作业调度同样可采用优先级法，即系统从后备作业队列中选择一批优先级相对高的作业调入内存 。
设有如下一组进程，它们都在时刻0到达，依次为P1，P2，…，P5，各自的运行时间和优先数如表所示 。采用优先级调度算法，这5个进程的执行顺序如图所示 。可以算出，这5个进程的平均周转时间是12个时间单位 。

Linux操作系统中常用调度算法

文章插图
 

Linux操作系统中常用调度算法

文章插图
优先级调度算法执行顺序




推荐阅读


上一篇：蒙特卡洛方法分析Web页面浏览量

下一篇：新石器时代黄河流域上游形成的文化 新石器时代黄河下游的文化