操作系统原理学习笔记（十三）-进程调度

操作系统原理学习笔记目录

书上的英文标识有点不统一，有的是首字母大写，有的是小写，
我不太清楚这两者有什么区别，但为了整体格式统一，我统一改成了大写。
当然，如果这种书写方式有问题，麻烦告知一下，谢谢。

进程调度的任务

1. 保存处理机的现场信息。
2. 按某种算法选取进程。
3. 把处理机分配给进程。

进程调度机制

• 排队器：将新出现的就绪状态插入响应的就绪队列。
• 分派器：将进程从就绪队列中取出，并进行上下文切换。
• 上下文切换器：保存当前进程上下文，将新进程上下文装入处理机的寄存器中。
  上下文切换需要执行大量指令，为了提高效率，通过移动寄存器指针的硬件实现方式进行上下文切换。

进程调度方式

早期OS使用非抢占方式，但因难以满足交互式作业与实时任务的需求，引入了抢占方式。

• 非抢占方式(Nonoreemptive Mode)：处理机分配给进程后，除非进程完成、出现I/O请求、被阻塞，进程将一直进行下去。
• 抢占方式(Preemotive)：根据不同原则，OS将当前进程处理机分配给新进程。

主要原则：

• 优先权原则：高优先级抢占低优先级进程处理机。
• 短进程优先原则：新进程若运行时间更短，则抢占当前进程处理机。
• 时间片原则：进程当前时间片结束后，停止当前进程，重新进行调度。

轮转调度算法(Round Robin, RR)

本算法于P101有图解。

最简单且最常用的算法，让每个就绪队列中每个进程仅运行一个时间片，若就绪队列有n个进程，则每个进程将获得大约1/n的处理机时间。

基本原理

根据FCFS原则，将所有就绪进程排成一个就绪队列，每隔一段时间(如30ms)产生一次中断，进程调度程序调度，将CPU分配给队首进程。时间片结束，调入下个队首进程。

进程切换时机

• 时间片未用完，进程结束，提前激活进程调度程序，并删除当前进程。
• 时间片用完，进程未结束，将进程切至对尾。

时间片大小的确定

能完成大多任务。

优先级调度算法

优先级调度算法的类型

• 非抢占式优先级调度算法：优先级的比较发生在切换进程时。
• 抢占式优先级调度算法：优先级的比较发生在切换进程与出现更高优先级进程时。

优先级的类型

• 静态优先级：进程创建时确定，运行时保持。
  用某一范围内的整数表示，例如0~255中的整数，这个整数被称为优先数。
  根据进程类型、进程对资源需求、用户要求来确定。
• 动态优先级：根据算法的不同改变优先级，
  如随着优先级时间减少的抢占式调度，或根据进入就绪队列的次序确定的FCFS算法。

多队列调度算法

根据需求不同，将进程放入不同就绪队列，公认性能良好的算法。

多级反馈队列调度算法(Multileved Feedback Queue)

调度机制

1. 设置多个就绪队列，每个队列不同优先级，第一队列优先级最高，时间片最短，随后队列优先级降低，时间片增加。
2. 每个队列采用FCFS算法，进程进入内存，放入第一队列对尾，其时间片用完后，若未完成，则放入第二队列对尾。
3. 队列间按优先级调度。

调度算法的性能

• 终端型用户作业一般属于交互型作业，在短时间内能完成，只要第一队列时间片足够运行完成作业，则性能良好。
• 短作业大多在第一队列能完成，即便没有，也能在二三队列完成。
• 长批处理作业会随着运行次数的增加，而获得更长的时间片。

基于公平原则的调度算法

保证调度算法

算法在P104页有较为详细的步骤，个人总结了一下，思想还是很简单的。

相同类型的进程获得相同时间片。
跟踪进程自创建到现在的时间C，进程获得处理机的时间R，
则进程获得处理机的时间比率为N=R/C，
为N最低的进程分配处理机，直到其N不再是最低。

公平分享调度算法

每个用户获得相同处理机时间，或所要求的时间比例。