进程调度
浏览数：19 /
时间：2015年06月20日
PCB 进程控制块
在内核中，保存进程状态的数据结构叫做PCB（进程控制块）。它包括了进程的非常多信息，如：进程当前状态，程序计数器，
CPU寄存器的值（当调度器暂停当前进程准备让其它进程运行时，将CPU寄存器中的数据现场保存），CPU调度信息。内存
信息（页表）。I/O状态（打开的文件和I/O设备等）。在Linux中，PCB就是我们在上一节中提到的保存在双向循环链表中的
task_struct结构，PCB是在各个操作系统中通用的概念。
总之，PCB中保存的就是进程间不同的数据，其作用就是在调度器切换运行进程时保存/恢复数据现场。
调度的时机
一个新创建的进程首先被放置在Ready队列，它一直等待运行的机会。一旦内核调度器将CPU分配给它開始运行时，有四种
可能：
（1）进程主动发起I/O请求。但I/O设备还没有准备好，所以会发生I/O堵塞，进程进入Wait状态。
（3）进程创建了子进程。并调用wait()等待子进程运行完成，进程就又一次进入Ready状态等待堵塞结束。
（4）I/O设备能够在随意时刻发生中断，CPU会停下当前正在运行的进程去处理中断，因此进程进入Ready状态。
当进程处于Wait状态时其PCB会被放置在特定的等待队列中。等待一个I/O设备的进程列表叫做设备队列(device queue)，
每一个设备都有自己的设备队列。
抢占式 多任务 分时
1.多任务
在单任务系统中。一个进程即使发生I/O堵塞（比方等待用户输入）时，操作系统也不会运行还有一进程，整个系统都将陷入
等待的空暇中。而多任务就是指当一个正在运行的进程发生I/O堵塞或等待其它资源须要暂停时。操作系统会启动还有一个
个进程继续运行，系统不会由于一个进程的堵塞而空暇下来。即单任务系统仅仅能在进程终止后才干调度其它进程開始运行。
而多任务系统在时机（1）I/O堵塞时发生调度。
此外。时机（3）属于主动放弃也是会发生调度的。
一个有趣的比喻：
"The lawyer works on several cases meanwhile and will never be idle for lack of work. Idle lawyers tend to become politicians,
so there is a certain social value in keeping lawyers busy."
2.分时
分时是在多任务的基础上。就算一个进程执行良好一直都没有发生堵塞，也不能让它就这样一直占用CPU资源直到它完毕
为止。操作系统会让每一个没有堵塞可以执行的进程共同分享CPU的计算能力。
所以。可以说分时的理念是对多任务的扩展。
分时的调度发生在时机（2）当内核分配给当前进程的时间片耗尽时。
3.抢占式
而区分一个多任务分时系统是抢占式的还是非抢占式的，则要看进程调度是否能发生在时机（4）发生中断，CPU停止当前
手头的工作（正在运行的进程），保存下当前工作的现场后，转入中断处理程序。假设在中断处理程序的运行中是否能发生
调度，即中断处理程序还没有运行完，又切换到其它进程。这里要说明的是，系统调用也是通过中断机制来实现的（以后
我们会专门学习系统调用的机制，这里先简单了解下）。
所以，也就是说要看系统调用的运行过程中，或者中断处理程序
的运行过程中是否能发生调度（抢占）。
理清了这三个概念后，让我们看一看要实现这三个目标会对操作系统的设计产生如何的影响。多任务、分时、抢占式都会
非常自然地对操作系统的设计产生根本影响。比方要为进程设计不同的状态表示执行、等待时间片、堵塞等。而且由于多进程
同一时候执行，还要对进程进行时间片分配、同步、避免死锁。
还要保护隔离各个进程不能任意訪问其它进程的资源。
能够说要
达到多任务分时的目的。这些问题是不可避免要考虑的。而抢占式在增强了进程的实时性的同一时候也添加了进程调度的复杂
度，进程或者内核全然有可能在系统调用或者中断处理程序未运行完时被抢占。
三种调度器
1.长期调度器(long-term scheduler)
在批处理系统中，通常被提交的进程远远超出能够马上运行的进程数目。
于是，这些被保存在大容量存储设备上等待运行。
长期调度器又叫作业调度器(job scheduler)从缓存中选出等待运行的进程载入到内存中，使其进入Ready状态。像UNIX
和Windows这种分时系统通常没有长期调度器。内核仅仅是简单地将提交的进程载入进内存，等待短期调度器去调度。
2.中期调度器(medium-term scheduler)
中期调度器的思想是将一些进程从内存中临时移出，从而减少调度器须要处理进程的数目。这样的将进程移出内存的机制
叫做换出(Swapping)。
3.短期调度器(short-term scheduler)
短期调度器从Ready状态的进程队列中选出一个运行。分配CPU资源给它。
这是我们最常说的调度器。
三种调度器能够在下图中找到相应的位置，它们在不同的时机对进程进行调度。
调度算法
1.先到先服务调度 First-Come, First-Served Scheduling (FCFS)
来看一个样例。如果有三个进程和它们各自运行时间（以毫秒为单位）例如以下表：
那么假设三个进程依照P1, P2, P3的顺序启动的话。依照先到先服务的调度算法，运行步骤例如以下：
平均等待时间就是(0 + 24 + 27) / 3 = 17毫秒。
FCFS算法是非抢占式的，一旦内核将CPU分配给一个进程就不会被释放
了。除非进程结束或者请求I/O堵塞。
这也是我们之前学习的多任务系统的特点。
2.基于优先级调度 Priority Scheduling
在优先级调度算法中，每一个进程都关联一个优先级，内核将CPU分配给最高优先级的进程。
具有同样优先级的进程，依照
先来先服务的原则进行调度。
如果进程的运行时间和优先级例如以下，而且这些进程同一时候存在于内存中时，内核基于优先级的
调度步骤例如以下：
採取基于优先级调度算法要考虑进程饿死的问题，由于高优先级的进程总是会被优先调度，具有低优先级的进程可能永远
都不会被内核调度运行。Aging是对于这个问题的一个解决方式，所谓Aging就是指逐渐提高系统中长时间等待的进程的
优先级。比方假设优先级的范围从127到0（127表示最低优先级）。那么我们能够每15分钟将等待进程的优先级加1。
终于
经过一段时间。即便是拥有最低优先级127的进程也会变成系统中最高优先级的进程，从而被运行。
一个有趣的谣言：
"Rumor has it that, when they shut down the IBM 7094 at MIT in 1973, they found a low-priority process that had been
submitted in 1967 and had not yet been run."
优先级调度能够抢占式或者非抢占式的。当一个进程在Ready队列中时，内核将它的优先级与正在CPU上运行的进程的优先级
进行比較。
当发现这个新进程的优先级比正在运行的进程高时：对于抢占式内核，新进程会抢占CPU。之前正在运行的进程
转入Ready队列；对于非抢占式内核，新进程仅仅会被放置在Ready队列的头部。不会抢占正在运行的进程。
3.最短作业优先调度 Shortest-Job-First Scheduling (SJF)
最短作业优先调度是优先级调度的特例。在优先级调度中我们依据进程的优先级来进行调度，在最短作业优先调度中我们
依据作业的运行时间长短来调度。
通过以下的样例来看看SJF是如何调度的。
进程1首先运行了1毫秒，当运行时间更短的进程2进入Ready队列时发生抢占。进程3在进程2运行1毫秒后到来，可是进程3的
运行时间比进程2长。
同理进程4的到来也没法抢占进程2，所以进程2能够一直运行到结束。之后是运行时间第二短的进程4
运行。最后是进程1（要看剩余运行时间，还剩7毫秒）和进程3。
SJF调度是最优的调度。但难点在于怎样预測进程的运行时间(Burst Time)。对于批处理系统中的长期调度来说，能够将用户
提交进程时输入的运行时间上限作为根据。但对于短期调度来说。没有办法可以提前得知下一个要被分配CPU的进程的运行
时间长短。我们仅仅能通过历史数据来进行预測。公式例如以下：
α能够取0.5，公式前半部分表示近期一次Burst Time。而后半部分表示过去历史平均的Burst Time。
4.循环调度 Round-Robin Scheduling (RR)
RR调度算法转为分时系统设计，它与FCFS非常像，可是增加了抢占。详细调度过程是：内核从Ready队列中选取第一个进程，
将CPU资源分配给它，而且设置一个定时器在一个时间片后中断该进程。调度Ready队列中的下一进程。非常明显，RR调度
算法是抢占式的，而且在该算法的调度下，没有一个进程可以连续占用CPU超过一个时间片，从而达到了分时的目的。
来看以下的样例，如果一个时间片的长度为4毫秒：
5.多级队列调度 Multilevel Queue Scheduling
多级队列调度Ready队列分成几个独立的队列，每个小队列都有自己的调度算法。每道工序都根据自己的特点永久分配
要他们在一个队列。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
