处理机调度

在多道程序环境下，主存中有着多个进程，其数目往往多余处理机数目。系统按照某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。

高级调度，作业调度

根据某种算法，把外存上处于后备队列中的作业调入内存。

作业步骤

1.编译作业步，通过编译程序对源程序进行编译，产生若干个目标程序段
2.链接作业步，将编译作业步产生的若干个目标程序装配成可执行目标程序 3.运行作业步，将可执行目标程序读入内存并控制其运行。

作业调度

从外存的后备队列中选取某些作业调入内存，并为他们创建进程，分配必要资源，然后插入就绪队列，准备执行。

低级调度，进程调度

进程调度决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程。主要功能：

• 保存处理机的现场信息。需要保存当前进程的处理机的现场信息，如程序计数器，多个通用寄存器中的内容，将它们送入该进程的进程控制块PCB中的相应单元
• 按某种算法选取进程。如优先数算法，轮转法，从就绪队列选取一个进程，把他状态改为运行状态，并准备把处理机分配给他
• 把处理器分配给进程，上下文切换。由分派程序(dispatcher)把处理器分配给进程。需给选中的进程恢复处理机现场，把PCB中有关处理机现场相关信息装入处理器各个寄存器中，把处理器控制权交给该进程，让它从取出的断点处开始继续运行。 上下文切换每一次大约花费几毫秒时间，该时间可以执行上千条指令。

调度方式

非抢占式

一旦把处理机分配给某个进程后，不管运行多长时间，都一直运行，直至该进程完成，或发生某事件阻塞时，才把处理机分配给其他进程。 引起调度的事件：
1.进程执行完毕
2.发起I/O请求而暂停执行
3.执行了某原语，如wait,block,wakeup等
在实时系统中，不采用这种调度方式

抢占式

允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一个进程。优点：防止一个进程长时间占用处理机，能为大多数进程提供更公平的服务。
原则：
1.优先权原则
2.短进程优先原则
3.时间片原则，各个进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。

中级调度

为了提高内存利用率和系统吞吐量，使暂时不能运行的进程不再占用内存资源，而将它们调至外存，把此时进程状态设置为挂起状态。当这些进程又具备运行条件且内存有空间时，由中级调度决定把外存上哪些进程调入内存，并修改为就绪状态。

调度算法

FCFS

先来先服务，可用于作业调度，也可用于进程调度。 每次调度时从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，直到运行完成或发生某事件阻塞。有利于长进程，不利于短进程。

SPF

短作业或短进程优先调度算法，可以作用于作业调度和进程调度。从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，直到运行完成或发生某事件阻塞。

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

为就绪队列中的每个进程分配时间片，依次执行。时间片大小从几ms到几百ms，当时间片用完，调度程序停止该进程，并将它发送就绪队列的队尾。

多级反馈队列调度算法

大部分OS所采用，包括linux 1.多个不同优先级的就绪队列，队列优先级逐个降低，赋予的时间片逐个增高，在优先级高的队列中时间片越小。如第二个队列时间片比第一个大1倍。
2.当一个进程进入内存后，放入第一队列末尾，按FCFS等待调度，执行时，如它能在该队列时间片完成，便可撤离系统。如果未完成，调度程序便将该进程转入第二队列末尾，同样按照FCFS原则等待调度。
3.仅当第一队列空闲时，才会调度第二队列。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先级高的队列，则此时暂停正在运行的进程，转而执行优先级高的进程。