处理机调度

处理机调度

1.基本概念

1.调度

所谓调度，就是在资源有限的情况下，有些事情没办法同时处理，这就需要确定某种规则来决定处理这些任务的顺序。即调度研究的问题

2.处理机调度

在多道程序系统中，进程的数量往往是多于处理机个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

2.调度的三个层次

1.高级调度（作业调度）

1.出现原因

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序

2.高级调度（作业调度）

按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB），以使它们获得竞争处理机的权利

3.特点

1）高级调度是辅存（外存）和内存之间的调度。

2）每个作业只调入一次，调出一次。

3）作业调入时会建立相应的PCB，作业调出时才撤销PCB。

4）高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出

2.中级调度（内存调度）

1.出现原因

引入虚拟存储技术后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又有空闲时，再重新调入内存。

2.目的

为了提高内存利用率和系统吞吐量

3.注意

暂时调到外存等待的进程状态为挂起状态，值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。

被挂起的进程PCB会被发到挂起队列中

4.中级调度

1）就是要决定哪个处于挂起状态的进程重新调入内存

2）一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高

5.进程的挂起状态和七状态模型

3.低级调度（进程调度）

1.主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它

2.进程的调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度

3.进程调度的频率很高，一般几十毫秒一次

4.三层调度的区别

3.进程调度

1.时机

1.什么时候需要进程调度？

1）当前运行的进程主动放弃处理机：进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞（等待I/O）

2）当前运行的进程被动的放弃处理机：分给进程的时间片用完、有更紧急的事要处理（I/O中断）、有更高优先级的进程进入就绪队列

2.什么时候不需要进程调度？

1）在处理中断的过程中。

2）进程在操作系统内核程序临界区中

3）在原子操作过程中（原语）。原子操作不可中断，要一气呵成

3.进程调度的时机

2.切换与过程

3.方式

4.调度算法的评价指标

1.CPU利用率

单道程序：CPU利用率 = 忙碌的时间/总时间

多道程序：甘特图来判断

2.系统吞吐量

单位时间完成作业的数量

系统吞吐量 = 总共完成了多少作业/总时间

3.周转时间

指作业被提交给系统开始，到作业完成为止的这段时间间隔

包括四个部分：

1）作业在外存后备队列上等待作业调度的时间

2）进程在就绪队列上等待进程调度的时间

3）进程在CPU上执行的时间

4）进程等待I/O操作完成的时间

注意：在一个作业的整个处理过程中，可能发生多次

周转时间 = 作业完成时间 - 作业提交时间

平均周转时间 = 各作业周转时间之和/作业数

带权周转时间 = 作业周转时间/作业实际运行的时间

平均带权周转时间 = 各作业带权周转时间之和/作业数

带权周转时间肯定大于1，周转时间和带权周转时间越小越好

4.等待时间

指进程/作业处于等待处理状态时间之和，等待时间越长，用户满意度越跌

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间

注意：一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。

5.响应时间

指从用户提交请求到首次得到响应的时间

5.调度算法

1.先来先服务FCFS

1.算法详解

2.例子

2.短作业优先SJF

1.算法详解

2.例子非抢占式

3.例子抢占式

1）调度顺序：

2）算法评价

4.注意

3.高响应比优先HRRN

1.算法详解

2.例子

4.调度算法比较

6.调度算法II

1.时间片轮转调度算法RR

1.算法详解

2.例子

如果时间片过大，则会导致算法退化为先来先服务算法，并且会增大响应时间，因此时间片不能太大。

如果时间片过小，则会导致进程频繁切换，导致系统会花费大量的时间进行进程切换

2.优先级调度算法

1.算法详解

2.例子

1）非抢占式

2）抢占式

3.补充

3.多级反馈队列调度算法

1.算法详解

2.例子

4.算法对比