操作系统——进程调度算法理解

调度算法分类：

1. 批处理

2. 交互式

3. 实时

调度算法的目标：

所有系统：公平、策略强制执行、平衡

批处理系统：吞吐量、周转时间、CPU利用率

交互式：响应时间、均衡性

实时系统：满足截止时间、可预测性

批处理系统中的调度

1. 先到先服务(FCFS)：在所有调度算法中，最简单的是非抢占式的FCFS算法。 

算法原理：

 

算法优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平 

算法缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程

2. 最短作业优先(SJF)：适用于运行时间可以预知的批作业的非抢占式调度算法

算法原理：

 

算法优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。 

算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。

3. 最短剩余时间优先：最短作业优先的抢占式版本就是最短剩余时间优先

4. 三级调度：

1>.准入调度：决定那些作业进入系统。

2>.内存调度：决定哪个进程留在内存，而那个进程换出到磁盘。

3>.CPU调度器：在内存中选取下一个将要运行的程序。

算法原理：

 

交互式系统中的调度

1. 时间片轮转调度：一种最古老、最简单、最公平且是使用最广的算法。

算法原理：让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。 

算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。 

算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当 

怎样确定时间片的大小：

时间片大小的确定 

1.系统对响应时间的要求 

2.就绪队列中进程的数目 

3.系统的处理能力

2. 优先级调度：每一个进程被赋予一个优先级，率先运行优先级最高的就绪进程。

3. 多重队列

4. 最短进程优先

5. 保证调度算法

6. **调度算法

7. 公平分享调度

实时系统调度