调度算法

进程调度算法

进程调度算法也称为 CPU 调度算法，毕竟进程是由 CPU 调度的。

当 CPU 空闲时，操作系统就会选择内存中的某个 [就绪状态] 的进程，并给其分配 CPU。

什么时候发生 CPU 调度？

1. 当进程从运行状态转到等待状态 - 非抢占式调度
2. 当进程从运行状态转到就绪状态 - 抢占式调度
3. 当进程从等待状态转到就绪状态 - 抢占式调度
4. 当进程从运行状态转到终止状态 - 非抢占式调度

非抢占式的意思是，当进程正在运行时，就会一直运行，知道该进程完成或者发生某个事件而被阻塞时，才会把 CPU 让给其他进程。 抢占式的意思是，进程正在运行时，可以被打断，使其把 CPU 让给其他进程。那抢占的原则一般有三种，分别是时间片原则、优先权原则、短作业优先原则。

常见的调度算法：

1. 先来先服务调度算法
2. 最短作业优先调度算法
3. 高响应比优先调度算法
4. 时间片轮转调度算法
5. 最高优先级调度算法
6. 多级反馈队列调度算法

内存页置换算法

内存页置换算法的功能是，当出现缺页异常，需要调入新页面而内存已满时，选择被置换的物理页。 也就是说选择一个物理页换出到磁盘，然后把需要访问的页面换入到物理页。

算法的目标是，尽可能少的换入和换出的次数，常见的算法有：

1. 最佳页置换算法
2. 先进先出置换算法
3. 最近最久未使用的置换算法
4. 时钟页置换算法
5. 最不常用置换算法

磁盘调度算法