进程调度算法准则

1. Linux系统的进程调度

Linux进程调度

1．调度方式

Linux系统的调度方式基本上采用“ 抢占式优先级 ”方式，当进程在用户模式下运行时，不管它是否自愿，核心在一定条件下（如该进程的时间片用完或等待I/O）可以暂时中止其运行，而调度其他进程运行。一旦进程切换到内核模式下运行时，就不受以上限制，而一直运行下去，仅在重新回到用户模式之前才会发生进程调度。

Linux系统中的调度基本上继承了UNIX系统的 以优先级为基础 的调度。也就是说，兆答核心为系统中每个进程计算出一个优先级，该优先级反映了一个进程获得CPU使用权的资格，即高优先级的进程优先得到运行。核心从进程就绪队列中挑选一个优先级最高的进程，为其分配一个CPU时间片，令其投入运行。在运行过程中，当前进程的优先级随时间喊悄递减，这样就实现了“负反馈”作用，即经过一段时间之后，原来级别较低的进程就相对“提升”了级别，从而有机会得到运行。当所有进程的优先级都变为0（最低）时，就重新计算一次所有进程的优先级。

2．调度策略

Linux系统针对不同类别的进程提供了3种不同的调度策略，即SCHED_FIFO、SCHED_RR及SCHED_OTHER。其中，SCHED_FIFO适合于 短实时进程 ，它们对时间性要求比较强，而每次运行所需的时间比较短。一旦这种进程被调度且开始运行，就一直运行到自愿让出CPU或被优先级更高的进程抢占其执行权为止。

SCHED_RR对应“时间片轮转法”，适合于每次运行需要 较长时间的实时进程 。一个运行进程分配一个时间片（200 ms），当时间片用完后，CPU被另外进程抢占，而该进程被送回相同优先级队列的末尾，核心动态调整用户态进程的优先级。这样，一个进程从创建到完成任务后终止，需要经历多次反馈循环。当进程再次被调度运行时，它就从上次断点处开始继续执行。

SCHED_OTHER是传统的UNIX调度策略，适合于交互式的 分时进程 。这类进程的优先级取决于两个因素：一个是进程剩余时间配额，如果进程用完了配给的时间，则相应优先级降到0；另一个是进程的优先数nice，这是从UNIX系统沿袭下来的方法，优先数越小，其优先级越高。nice的取值范围是-20 19。用户可以利用nice命令设定进程的nice值。但一般用户只能设定正值，从而主动降低其优先级；只有特权用户才能把nice的值设置为负数。进程的优先级就是以上二者之和。

后台命令对应后台进程（又称后台作业）。后台进程的优先级低于任何交互（前台）进程的优先级。所以，只有当系统中当前不存在可运行的交互进程时，才调度后台进程运行。后台进程往往按批处理方式调郑猜渣度运行。

3．调度时机

核心进行进程调度的时机有以下5种情况：

（1）当前进程调用系统调用nanosleep( )或者pause( )，使自己进入睡眠状态，主动让出一段时间的CPU的使用权。

（2）进程终止，永久地放弃对CPU的使用。

（3）在时钟中断处理程序执行过程中，发现当前进程连续运行的时间过长。

（4）当唤醒一个睡眠进程时，发现被唤醒的进程比当前进程更有资格运行。

（5）一个进程通过执行系统调用来改变调度策略或者降低自身的优先级（如nice命令），从而引起立即调度。

4．调度算法

进程调度的算法应该比较简单，以便减少频繁调度时的系统开销。Linux执行进程调度时，首先查找所有在就绪队列中的进程，从中选出优先级最高且在内存的一个进程。如果队列中有实时进程，那么实时进程将优先运行。如果最需要运行的进程不是当前进程，那么当前进程就被挂起，并且保存它的现场—— 所涉及的一切机器状态，包括程序计数器和CPU寄存器等，然后为选中的进程恢复运行现场。

（二）Linux常用调度命令

· nohup命令

nohup命令的功能是以忽略挂起和退出的方式执行指定的命令。其命令格式是：

nohupcommand［arguments］

其中，command是所要执行的命令，arguments是指定命令的参数。

nohup命令告诉系统，command所代表的命令在执行过程中不受任何结束运行的信号（hangup和quit）的影响。例如，

$ nohup find / -name exam.txt -print>f1 &

find命令在后台运行。在用户注销后，它会继续运行：从根目录开始，查找名字是exam.txt的文件，结果被定向到文件f1中。

如果用户没有对输出进行重定向，则输出被附加到当前目录的nohup.out文件中。如果用户在当前目录中不具备写权限，则输出被定向到$HOME/nohup.out 中。

· at命令

at命令允许指定命令执行的时间。at命令的常用形式是：

attimecommand

其中，time是指定命令command在将来执行时的时间和日期。时间的指定方法有多种，用户可以使用绝对时间，也可以用相对时间。该指定命令将以作业形式在后台运行。例如：

$ at 15:00 Oct 20

回车后进入接收方式，接着键入以下命令：

mail -s "Happy Birthday!" liuzheny

按下D键，屏幕显示：

job 862960800.a at Wed Oct 20 15:00:00 CST 1999

$

表明建立了一个作业，其作业ID号是862960800.a，运行作业的时间是1999年10月20日下午3:00，给liuzheny发一条标题为“Happy Birthday！”（生日快乐）的空白邮件。

利用 at-l 可以列出当前at队列中所有的作业。

利用 at-r 可以删除指定的作业。这些作业以前由at或batch命令调度。例如，

at-r862960797.a

将删除作业ID号是862960797.a的作业。其一般使用形式是：

at-rjob_id

注意，结尾是.a的作业ID号，表示这个作业是由at命令提交的；结尾是.b的作业ID号，表示这个作业是由batch命令提交的。

· batch命令

batch命令不带任何参数，它提交的作业的优先级比at命令提交的作业的优先级低。batch无法指定作业运行的时间。实际运行时间要看系统中已经提交的作业数量。如果系统中优先级较高的作业比较多，那么，batch提交的作业则需要等待；如果系统空闲，则运行batch提交的作业。例如，

$ batch

回车后进入接收方式，接着键入命令：

find / -name exam.txt -print

按下D。退出接收方式，屏幕显示：

job 862961540.b at Thu Nov 18 14:30:00 CST 1999

表示find命令被batch作为一个作业提交给系统，作业ID号是862961540.b。如果系统当前空闲，这个作业被立即执行，其结果同样作为邮件发送给用户。

· jobs命令

jobs命令用来显示当前shell下正在运行哪些作业（即后台作业）。例如：

$ jobs

[2] + Running tar tv3 *&

[1] - Running find / -name README -print > logfile &

$

其中，第一列方括号中的数字表示作业序号，它是由当前运行的shell分配的，而不是由操作系统统一分配的。在当前shell环境下，第一个后台作业的作业号为1，第二个作业的作业号为2，等等。

第二列中的“ ”号表示相应作业的优先级比“－”号对应作业的优先级高。

第三列表明作业状态，是否为运行、中断、等待输入或停止等。

最后列出的是创建当前这个作业所对应的命令行。

利用 jobs-l 形式，可以在作业号后显示出相应进程的PID。如果想只显示相应进程的PID，不显示其它信息，则使用 jobs-p 形式。

· fg命令

fg命令把指定的后台作业移到前台。其使用格式是：

fg [job…]

其中，参数job是一个或多个进程的PID，或者是命令名称或者作业号（前面要带有一个“%”号）。例如：

$ jobs

[2] + Running tar tv3 *&

[1] - Running find / -name README -print > logfile&

$ fg %find

find / -name README -print > logfile

注意，显示的命令行末尾没有“&”符号。下面命令能产生同样的效果：

$ fg %1

这样，find命令对应的进程就在前台执行。当后台只有一个作业时，键入不带参数的fg命令，就能使相应进程移到前台。当有两个或更多的后台作业时，键入不带参数的fg，就把最后进入后台的进程首先移到前台。

· bg命令

bg命令可以把前台进程换到后台执行。其使用格式是：

bg [job…]

其中，job是一个或多个进程的PID、命令名称或者作业号，在参数前要带“%”号。例如，在cc（C编译命令）命令执行过程中，按下Z键，使这个作业挂起。然后键入以下命令：

$ bg %cc

该挂起的作业在后台重新开始执行。

2. 进程调度的算法

算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。
例如，有三个进程P1、P2和P3先后进入就绪队列，它们的执行期分别是21、6和3个单位时间，
执行情况如下图：
对于P1、P2、P3的周转时间为21、27、30，平均周转时间为26。
可见，FIFO算法服务质量不佳，容易引起作业用户不满，常作为一种辅助调度算法。 最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First)
该算法从就绪队列中选出下一个“CPU执行期最短”的进程，为之分配处理机。
例如，在就绪队列中有四个进程P1、P2、P3和P4，它们的下一个执行期分别是16、12、4和3个单位时间，执行情况如下图：
P1、P2、P3和P4的周转时间分别为35、19、7、3，平均周转时间为16。
该算法虽可获得较好的调度性能，但难以准确地知道下一个CPU执行期，而只能根据每一个进程的执行历史来预测。 前几种算法主要用于批处理系统中，不能作为分时系统中的主调度算法，在分时系统中，都采用时间片轮转法。
简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。
多级队列方法：将系统中所有进程分成若干类，每类为一级。 多级反馈队列方式是在系统中设置多个就绪队列，并赋予各队列以不同的优先权。

3. unix系统v的进程调度是采用怎样的调度算法完成的

答案为D。 多级反馈队列轮转法 调度算法（作业调度、进程调度） 1、先来先服务调度算法（FCFS） 按进入后备（或就绪）队列的先后选择目标作业（或进程）。 有利于长作业（进程），不利于短作业（进程）。 2、最短作业优先调度算法SJ（P）F 从后备（或就绪）队列中选择估计运行时间最短的作业（或进程） tn+1=a tn+(1-a) tn tn为实际值， tn为预测值 SJF有效地降低作业的平均等待时间，提高了系统的吞吐量。 对长作业（或进程）不利，可能死等，且未考虑作业的紧迫程度。 3、时间片轮转调度算法（进程调度） 系统将所有的就绪进程按先来先服务原则，排成一个队列，每次调度时把CPU分配给队首进程，令其执行一个时间片。 就绪队列中所有进程，在一个给定的时间内，均能获得一个时间片的处理机执行时间。T=nq 4、优先权调度算法 适用于作业调度和进程调度。 非抢占式、抢占式优先权调度算法 优先权类型：静态优先权、动态优先权 5、高响应比优先调度算法（作业调度） 响应比RP= 响应时间/要求服务时间=（等待时间+要求服务时间）/要求服务时间 = 1+等待时间/要求服务时间 同时到达的作业（等待时间相同），要求服务时间越短（短作业），响应比越高，有利于短作业。 要求服务时间相同的作业，等待时间越长，响应比越高，相当于先来先服务。 长作业在等待足够长时间后，响应比上升，也可被调度，避免长作业的死等。 每次调度需计算响应比，增加系统的开销。 6、多级队列调度 根据作业的性质或类型的不同，将就绪进程队列分成若干个子队列，各个作业固定分属于一个队列。每个队列采用各自的调度算法。 7、多级反馈队列调度算法 UNIX系统中的进程调度算法。 处理方法： 设置多个就绪队列，每个队列赋予不同的优先权(S1>S2……>Sn )，且各队列中进程执行的时间片的大小各不相同(q，2q……nq)。 新进程进入内存，首先放在S1的末尾，按FCFS排队调度，执行q时间片，若未完成，该进程转入S2，依次类推。 仅当Si空闲，才会调度Si+1中进程。 能较好地满足各种类型用户的需要。

4. 第三章 进程调度的几种方式

进程调度概念：操作系统必须为多个，吗进程可能有竞争的请求分配计算机资源。对处理器而言，可分配的资源是在处理器上的执行时间，分配途径是调度。调度功能必须设计成可以满足多个目标，包括公平、任何进程都不会饿死、有效地使用处理器时间和低开销。此外，调度功能可能需要为某些进程的启动或结束考虑不同的优先级和实时最后期限。

这些年以来，调度已经成为深入研究的焦点，并且已经实现了许多不同的算法。如今，调度研究的重点是开发多处理系统，特别是用于多线程的。

下面简介几种调度算法。

一、先来先服务和短作业(进程)优先调度算法

1．先来先服务调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

2．短作业(进程)优先调度算法

短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

二、高优先权优先调度算法

1．优先权调度算法的类型

为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。

1) 非抢占式优先权算法

在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

2) 抢占式优先权调度算法

在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

2．高响应比优先调度算法

在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：

由上式可以看出：

(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。

(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。

三、基于时间片的轮转调度算法

1．时间片轮转法

1) 基本原理

在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

2．多级反馈队列调度算法

前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。

(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。

(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。

(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

5. 操作系统的进程调度算法[总结]

操作系统的进程调度算法直接关系到用户的使用体验。

如果把用户的体验时间，引入到计算机里面，我们引入以下几个概念。

周转时间，指作业从提交系统开始，直到作业完成为止的时间间隔。包括：

是指作业周转时间与作业实际运行服务时间的比值。
平均周转时间和平均带权周转时间是衡量批处理系统调度算法的重要准则。

先来先服务调度算法（First Come First Served, FCFS）是最简单的调度算法，可以用于作业调度和进程调度。
按照作业进入系统后备作业队列的先后次序来挑选作业，加入就绪队列，等待执行。

FCFS是非抢占式的，易于实现，效率不高，性能不好.
有利于长作业（CPU繁忙性）而不利于短作业（I/O繁忙性）。

服务时间：作业需要运行的时间
完成时间 = 开始时间 + 服务时间
等待时间 = 开始时间 - 提交时间
周转时间 = 完成时间 - 提交时间
带权周转时间 = 周转时间 / 服务时间
响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间/服务时间 + 1

该算法每次从后备作业队列中挑选估计服务时间最短的一个或几个作业，
将他们调入内存，分配必要的资源，创建进程并放入就绪队列。
在进程调度中的原理类似。

SJF是非抢占式的，优先照顾短作业，具有很好的性能，降低平均等待时间，提高吞吐量。
但是不利于长作业，长作业可能一直处于等待状态，出现饥饿现象；
完全未考虑作业的优先紧迫程度，不能用于实时系统。

高响应比优先调度算法（Highest Reponse Ratio First, HRRF）是非抢占式的，主要用于作业调度。
基本思想：每次进行作业调度时，先计算后备作业队列中每个作业的响应比，挑选最高的作业投入系统运行。
响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间 / 服务时间 + 1

由响应比分析可知，该算法介于FCFS和SJF之间，但是每次需要计算每个作业的响应比，增加系统开销。

6. 进程调度

当计算机中有多个process处于ready状态，将CPU分配给哪个进程呢？操作系统中做出这个决策的组件就是调度器，决策的算法叫调度算法，决策过程就是进程调度的过程。

进程调度一般发生在一下几种情况下：

在非抢占式调度中，进程开始执行以后，除非它主动放弃CPU或被block, 否则就能一直执行。
抢占式调度中，如果在进程执行过程中来了一个优先级更高的进程，CPU使用权就会被抢走，尤其在时间片调度中即使时间片没用完也可以被抢占。但抢占也不是随时可以发生的，如果设计不好可能会发生优先级逆转或者死锁问题。

在不同的场景下，为了实现不同的目标，评价调度算法的标准不尽相同。这里我们介绍一些常用的标准：
Fairness : 给每个进程公平的CPU使用机会
Balance : 让系统的各个组件都能得到最大程度的利用率
Throughput 吞吐量 ：单位时间内完成的任务数量
Turnaround Time ：一般在批处理系统中，一个批任务从提交到结束的间隔时间
CPU Utilization ：CPU的利用率
Waiting Time ：进程在ready队列里等待的时间
Response Time ：一般在交互式系统中，从用户提交任务到第一次得到响应（任务不一定完成）的间隔时间
Meeting Deadline ：一般在实时系统中及时处理数据，避免丢失或失效

接下来我们看看在三种不同类型系统中常用的调度算法。

1. FCFS : First Come, First Served
这是一种非抢占式的先来先服务算法。ready process队列只有一个。如果进程执行中被block，进入block队列，ready之后作为新的进程排到ready队列的尾部。
优点：容易理解，容易实现
缺点：平均等待时间往往很长，不好平衡CPU密集和IO密集型进程

2. SJF: Shortest Job First
SJF也是非抢占式调度，每次都选择最短的任务来执行。

3. Shortest Remaining Time Next
是SJF的抢占式版本，只要有新任务到达就重新调度选择剩余时间最短的任务执行。

SJF和Shortest Remaining Time Next的问题在于一般情况下很难判断进程的剩余执行时间是多少。除非这是经常要执行的task，根据对历史的统计分析能确定一个执行时间的大致范围。

1. Round-Robin Scheling
轮询调度。 给每个进程相同的时间片，轮流执行。一般时间片选择在20-50msec比较合适，太短会导致进程切换浪费时间，太长会导致响应时间延长。
优点：比SJF响应快
缺点：turnaround时间长

2. Priority Scheling
优先级调度为每个进程分配优先级，高优先级先执行，这也是时间片调度算法。优先级可以静态分配也可以动态分配，为了避免高优先级的进程一直占用CPU不放，可以在依次执行结束后降低其优先级。相同优先级的进程之间可以使用其他的调度算法如round-robin，不同队列可以使用不同的调度算法。
优点：引入了优先级

3. Multiple Queues
为了避免执行时间长的进程频繁进程切换，可以在不同的优先级队列之间分配不等长度的时间片。进程执行一次之后被分配其他拥有更长执行时间的优先级。比如一个进程需要100个quanta, 第一次执行时分配1个，下一次执行分配2个，再下次分配4，8，16，32，64. 比每次都只分配1的纯轮询算法减少了进程调度的次数。

4. Guaranteed Scheling
前面提到的算法都不保证进程能够得到的CPU时间，但有些情况下我们需要确保进程使用CPU的机会和时间，比如n个用户同时登录，一般要保证每个用户都能获得1/n的CPU，或者我们购买VPN服务，根据不同的用户级别需要获得一定的带宽保证。这种算法就叫Guaranteed 调度。在实现中，需要追踪给每个进程分配的CPU，与承诺分配量比较，比值最小的进程会获得下一次使用权。

5. Lottery Scheling
彩票调度算法引入了随机性，为每个进程发一张彩票，调度时就像开奖，谁中奖谁获得资源。优先级更高的进程可以获得多张彩票以提高中奖机会。
彩票调度有趣的地方在于进程之间可以互赠彩票，比如process 1 pending在process 2上，它可以把自己的彩票都给process2提高它被调度的机会。process2结束以后再把彩票还给process1.

6. Fair-Share Scheling
下面考虑一种情况，所有进程并不属于一个用户，这在Linux 系统中非常常见。如果user1有99个process，user2只有1个process，按照前面的算法可能user1能得到99%的CPU，而user2只有1%。为了实现用户层面的公平性，调度时需要考虑进程属于哪个user.

实时系统分两种：

实时系统中，一般任务时间都比较短，调度器需要使所有进程都在deadline前完成。对于周期性发生的事件，如果事件发生的周期为 , 事件处理时间(需要占用CPU的时间)为 , 只有 时，才是可调度的。

调度算法只能由操作系统实现吗，关于使用哪种调度算法进程是否有话语权呢？答案是可以的。将机制与策略分离，由操作系统提供多种实现机制，并提供system call由process传参数给OS指定具体使用哪一种调度策略。

如果线程是在用户态实现的，那么需要两级调度，OS负责调度process，process负责调度thread。如果线程是在内核态实现的，OS直接调度thread，而不关心它属于哪个process。