Linux和Minix的进程调度
描写友谊的古诗词 进程调度的目的是使处理机资源得到最高效的利用，应考虑的原则主要有：高效——使处理机的利用率最高，空闲最小；公平——使每个申请处理机的进程都得到合理的处理机时间；周转时间——使用户提交任务后得到结果的时间尽可能短；吞吐量——使单位时间内处理的任务数量尽可能多；响应时间——使得对每个用户的响应时间尽可能短。最常见的调度算法有以下几种：
1.先来先服务（FIFO）调度算法。
调度程序按照进程在就绪队列中的提交顺序或变为就绪状态的先后进行调度，是一种最普遍和最简单的方法，所需的系统开销最小。该算法对所有的进程一视同仁，不能反映对实时进程或特殊要求的进程的特殊处理。在实际操作中，很少单独使用该算法，而是和其他一些算法配合使用。
2.时间片轮转法（Round Robin）
在分时系统中，将CPU的处理时间分为时间片（TimeSlice）。系统给每一个进程分配若
干个时间片。被调度选中的进程进行完了系统分配的时间片后，系统就会发生调度，如果该进程还没有完成要求的任务，则调度程序暂时停止该进程的执行，将它排到就绪队列的末尾，等待下一次调度。同时，调度程序会调度当前就绪队列中的下一个进程。时间片轮转法使得就绪队列中的每个进程等待的时间与享受服务的时间成正比，这样就可以保证就绪队列中的所有进程在一个给定的时间均能得到执行。因此时间片长度的选择决定了系统开销的大小和响应时间的快慢。时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应变差。
3.优先级调度
优先级调度为不同响应要求的进程提供了解决方法，使实时性强的进程进入系统后能获得优先处理。每个进程被赋予一个优先级，率先运行优先级最高的就绪进程。优先级可以为静态或者动态的，相应的调度方法为非抢占式调度和抢占式调度。在非抢占式调度中，进程的优先级在进程启动时设定后，不再改变，系统将处理器分配给就绪队列中优先级最高的进程后，该进程执行直至完成或自动放弃处理机时，系统将处理机分配给另一个优先级高的进程。在抢占式调度中，进程的优先级随着时间变化，更高优先级的进程可以抢占处理机，系统中当前运行的永远都是就绪队列中优先级最高的进程。
严峻造句
4.多级反馈轮转法
在这种算法中，有多个就绪队列，不同的队列之间优先级不同，而同一个队列内的进程优先级相同而按照先来先服务的原则排列。对这些进程区别对待，给予不同的优先级和时间片。调度时先满足优先级高的队列。它综合了时间片轮转和优先级调度。
在现代操作系统中，一般不会只使用一个简单的调度方式，而是综合多个调度方法，实现一个灵活、高效、可靠、安全的进程调度机制。
二、Linux进程调度
1.调度的时机
Linux进程调度的时机有以下几类：
（1）进程状态转换的时刻；
（2）可运行队列中新增加一个进程时；
（3）当前进程的时间片用完时；
（4）进程从系统调用返回用户态时；
（5）内核处理完中断返回用户态时。
后面三种情况都是在该时机到来后，通过调用ret-from-sys-call()来检测调度标志，如果调度标志为1，就执行调度程序。
2.调度的策略
只有处于可运行状态的进程才可能被调度。task_struct结构中有：policy、priority、counter、rt_priority。其中，policy是进程的调度策略，用于区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程的静态优先级；counter是进程剩余的时间片；rt_priority是实时进程特有的，是实时进程之间的相对优先级，用于实时进程间的选择。
linux内核有三种调度方法：SCHED_OTHER 表示分时调度策略；SCHED_FIFO表示实时调度策略，先到先服务；SCHED_RR表示实时调度策略，婚房装饰时间片轮转。
实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，普通进程则通过nice和counter值决定权值。
当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。 SCHED_FIFO一旦占用CPU则一直运行，直到有更高优先级任务到达或自己放弃。如果有相同优先级的实时进程已经准备好，FIFO必须等待该进程主动放弃后才可以运行这个优先级相同的任务，而RR可以让每个任务都执行一段时间。
所有任务都采用linux分时调度策略时：
（1）创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。
（2）鹦鹉简笔画将根据每个任务的nice值确定在CPU上的执行时间(counter)。
（3）如果没有等待资源，则将该任务加入到就绪队列中。
（4）调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃CPU时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃CPU)中。
（5）此时调度程序重复上面计算过程，转到第4步。
（6）当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。
所有任务都采用FIFO时：
（1）创建进程时指定采用FIFO，并设置实时优先级rt_priority(1-99)。
（2）如果没有等待资源，则将该任务加入到就绪队列中。
（3）调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用CPU，该FIFO任务将一直占有CPU直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。
（4）调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒，再或被当前运行的任务唤醒，等等)，则调度程序立即在当前任务堆栈中保存当前CPU寄存器的所有数据，重新从高优先级任务的堆栈中加载寄存器数据到CPU，此时高优先级的任务开始运行。重复第3步。
电脑桌面壁纸励志
（5）如果当前任务因等待资源而主动放弃CPU使用权，则该任务将从就绪队列中删除，加入等待队列，此时重复第3步。
所有任务都采用RR调度策略时：
（1）创建任务时指定调度参数为RR，并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。
（2）如果没有等待资源，则将该任务加入到就绪队列中。
（3）调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用CPU。
（4）如果就绪队列中的RR任务时间片为0，则会根据nice值设置该任务的时间片，同时将该任务放入就绪队列的末尾。重复步骤3。
（5）当前任务由于等待资源而主动退出CPU，则其加入等待队列中。重复步骤3。
系统中既有分时调度，又有时间片轮转调度和先进先出调度：
（1）RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。
（2）当实时进程准备就绪后，如果当前CPU正在运行非实时进程，则实时进程立即抢占非实时进程。
（3）RR进程和FIFO进程都采用实时优先级作为概预算调度的权值标准，RR是FIFO的一个延伸。FIFO时，如果两个进程的优先级一样，则这两个优先级一样的进程具体执行哪一个是由其在队列中的未知决定的，这样导致一些不公正性，如果将两个优先级一样的任务的调度策略都设为RR，则保证了这两个任务可以循环执行，保证了公平。
三、Minix进程调度
Minix3调度器使用一个多级排队系统，一共定义了16个队列，但是重新编译以定义更多或更少的队列也是可以的。最低优先级队列只由IDLE进程使用，IDLE进程在系统没有其他任务时运行。用户进程启动时默认的优先级比最低优先级要高一些。
服务器进程处于比用户进程具有更高优先级的队列当中，而驱动程序进程处于比服务器进程更高优先级的队列当中，系统和时钟任务处于最高优先级队列当中。在某一时刻并不
一定所有的队列都在用。一个进程可以被系统移到一个具有不同优先级的队列当中，用户也可以通过nice命令在一定限制内改变进程优先级。改变进程优先级的目的往往是为了获得更好的性能。
除了进程所在队列所决定的优先级以外，还使用其他机制以使一些进程比其他进程更有优势：
（1）时间片，即进程在被抢占前所允许运行的最大时间间隔，在所有的进程中并不相同。用户进程有一个较小的时间片。驱动程序进程和服务器进程通常可以运行到阻塞，为了防止故障，它们是可抢占的，但具有一个大的时间片。
（2）驱动程序进程和服务器进程可以运行大的但仍是有限的时钟节拍，如果它们用完了时间片就会被抢占，这样可以使系统不至于挂起。在这种情况下，运行超时的进程仍处于就绪态，但被放到它所在队列的尾端。
白矾的功效与作用（3）如果一个用完了时间片的进程，仍然是上一次运行的进程，则可以认为它卡在了一个循环中，从而出现了阻止其他低优先级进程运行的征兆。此时，将把该进程放到一个较低
优先级队列的队尾以降低它的优先级。如果这个进程又运行超时，而还有其他进程得不到运行，它的优先级将再一次降低。最终使其他的进程都得到机会运行。
（4）一个被降低优先级的进程仍有机会提高它的优先级。如果一个进程用完了它的时间片，但没有妨碍其他进程运行，它的优先级将得到提高，直到该进程所允许的最大优先级为止。
（5）此外，使用一个经改进的轮转调度算法调度进程。如果进程转为非就绪的时候没有用完它的时间片，这说明它在I/O上阻塞，当该进程再次转为就绪时就被放到队首，并分配上次所剩余的时间片。这样是为了给用户进程更快的I/O响应。
（6）一个用完了时间片的进程以纯时间片轮转调度的方式被放到队尾。
最后我们进行一个简单的总结。Minix分成16个优先级队列，任务通常有最高优先级，驱动程序进程、服务器程序进程优先级紧跟其后，然后是用户进程，优先级最低的是键盘发送键是哪个IDLE进程。当选择进程运行的时候，调度器首先检查最高优先级队列中的进程，如果一个或多个处于就绪态，那么队首的进程运行。如果没有进程就绪，那么下一个优先级队列将会被同
样地检查，依次类推。如果没有进程就绪，将选择IDLE进程，使CPU处于低功耗模式，直到下一个中断产生。在每一个时钟节拍，都将检查当前进程是否运行完了分配给它的时间片。如果是，调度器将它放到队尾，然后选择下一个进程运行。只有当高优先级队列中没有进程且前面的那个进程在其队列中唯一时，它将再次得到运行。重要的驱动程序和服务器被分配一个较大的时间片，在被时钟抢占之前，它们通常已经阻塞。但是当出错时，将会降低它们的优先级以防止整个系统处于停滞状态。
