linux系统进程调度算法,Linux操作系统中常⽤调度算法
明确先来先服务FCFS、时间⽚轮转RR、优先级三种常⽤的调度算法的实现思想，并在此基础上计算周转时间、带权周转时间、平均周转时间和平均带权周转时间。
(⼀)先来先服务
先来先服务(First-Come，First-Served，FCFS)⽅法是最简单的⼀种调度算法。它的实现思想就是“排队买票”的办法。对于作业调度来说，按照先来先服务法，是每次调度从后备作业队列(按进⼊时间先后为序)中选择队头的⼀个或⼏个作业，把它们调⼊内存，分配相应的资源，创建进程，然后把进程放⼊就绪队列。
对于进程调度算法来说，采⽤先来先服务法，就是每次调度从就绪队列中选择⼀个最先进⼊该队列的进程，把CPU分给它，令其投⼊运⾏。该进程⼀直运⾏下去，直⾄完成或者由于某些原因⽽阻塞，才放弃CPU。这样，当⼀个进程进⼊就绪队列时，它的PCB就链⼊就绪队列的末尾。每次进程调度时就把队头进程从该队列中摘下，分给它CPU，使它运⾏。
设有3个作业，编号为1，2，3，各作业分别对应⼀个进程。各作业依次到达，相差⼀个时间单位。图⽰出采⽤FCFS⽅式调度时这3个作业的执⾏顺序。
FCFS调度算法⽰意图
根据图，可算出各作业的周转时间和带权周转时间等，如表所⽰。
linux是一个分时操作系统
表 FCFS调度算法性能
由表可以看出，FCFS算法⽐较有利于长作业(进程)，⽽不利于短作业(进程)。因为短作业运⾏时间很短，如果让它等待较长时间才得到服务，它的带权周转时间就会很长。
另外，FCFS调度算法对CPU繁忙型作业(指需要⼤量CPU时间进⾏计算的作业)较有利，⽽不利于I/O繁
忙型作业(指需要频繁请求I/O的作业)。因为在执⾏I/O操作时，往往该作业(进程)要放弃对CPU的占有。当I/O完成后要进⼊就绪队列排队，可能要等待相当长⼀段时间，才得到较短时间的CPU服务，从⽽使这种作业的周转时间和带权周转时间都很⼤。
FCFS调度算法容易实现，但它的效率较低。
(⼆)时间⽚轮转法
时间⽚轮转法(Round-Robin，RR)主要⽤于分时系统中的进程调度。为实现轮转调度，系统把所有就绪进程按先⼊先出的原则排成⼀个队列。新来的进程加到就绪队列末尾。每当执⾏进程调度时，进程调度程序总是选出就绪队列的队⾸进程，让它在CPU上运⾏⼀个时间⽚的时间。
时间⽚是⼀个⼩的时间单位，通常为10⾄100毫秒数量级。当进程⽤完分给它的时间⽚后，系统的计时器发出时钟中断，调度程序便停⽌该进程的运⾏，并把它放⼊就绪队列的末尾；然后，把CPU分给就绪队列的队⾸进程，同样也让它运⾏⼀个时间⽚，如此往复。
例如，考虑如下4个进程A、B、C和D的执⾏情况。设它们依次进⼊就绪队列，但彼此相差时间很少，可以近似认为“同时”到达。四个进程分别需要运⾏12，5，3和6个时间单位。图3-6⽰出时间⽚q=1和q=4时它们运⾏的情况。
RR法(q=1和q=4时进程运⾏情况)
由图可以看出，在轮转法中，⼀次轮回时间内分给任何进程的CPU时间都不会⼤于⼀个时间⽚。如果⼀个进程在⼀个时间⽚内没有做完⾃⼰的事情，那么在时间⽚⽤完后，该进程就失去对CPU的控制权，被放到就绪队列的末尾。所以，⼀个运⾏较长时间的进程需要经过多次轮转才能完成。
可见，时间⽚的⼤⼩对轮转法的性能有很⼤影响。如果时间⽚太长，每个进程都在这段时间内运⾏完毕，那么时间⽚轮转法就退化为先来先服务算法。很显然，对⽤户的响应时间必然加长。如果时间⽚太短，CPU在进程间的切换⼯作就⾮常频繁，从⽽导致系统开销增加。因为在每个时间⽚末尾，都产⽣时钟中断，操作系统要处理这个中断，在把CPU分给另⼀个进程之前，要为“⽼”的进程保留全部寄存器的内容，还要为新选中的进程装配所有寄存器的值。这⼀⼯作⽆疑加⼤了系统开销。
时间⽚的长短通常由以下4个因素确定：
(1)系统的响应时间。在进程数⽬⼀定时，时间⽚的长短直接正⽐于系统对响应时间的要求。
(2)就绪队列进程的数⽬。当系统要求的响应时间⼀定时，时间⽚的⼤⼩反⽐于就绪队列中的进程数。
(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个时间单位。
优先级调度算法执⾏顺序

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。