1、进程调度算法

也称CPU调度算法，因为进程由CPU调度。当CPU空闲时选择某个就绪状态的进程并给其分配CPU

发生CPU调度的常见情况：

1. 进程从运行状态转到等待状态
2. 进程从运行状态转到就绪状态
3. 进程从等待状态转到就绪状态
4. 进程从运行状态到终止状态

1和4两种情况下的调度称为非抢占式调度，2和3称为抢占式调度。抢占的原则一般有三种：时间片原则，优先权原则和短作业优先原则。第三种情况发生CPU调度的可能原因是，假设一个进程处于等待状态但是他的优先级比较高，当他转到就绪状态时，如果调度算法基于优先级，那么他就会立马抢占正在运行的进程

调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），⽽不能影响进程真在使⽤ CPU 的时间和 I/O 时间

先来先服务调度算法（First Come First Severd, FCFS）

每次都从就绪队列选择最先进入队列的进程然后一直运行直到进程退出或阻塞

对长作业有利，适用于CPU繁忙型作业的系统而不适用于IO繁忙型作业系统

最短作业优先调度算法（Shortest Job First, SJF）

优先选择运行时间最短的进程来运行

高响应比优先调度算法（HRRN）

（Highest Response Ratio Next, HRRN）权衡了短作业和长作业，每次进行进程调度时，先计算相应比优先级，选择相应比优先级最高的进程投入运行

优先权 = (等待时间 + 要求服务时间) / 要求服务时间

时间片轮转调度算法（RR）

每个进程被分配⼀个时间段，称为时间⽚（Quantum），即允许该进程在该时间段中运⾏。通常时间⽚设为 20ms~50ms，时间片长短的设置非常关键，太短会经常引起进程上下文切换，太长会引起短作业进程响应时间太长。

最⾼优先级调度算法（HPF）

从就绪队列中选择最高优先级的进程进行运行，称为最高优先级（Highest Priority First，HPF）调度算法

进程优先级可以分为静态优先级或动态优先级

• 静态优先级：创建进程后就确定优先级并且不改变
• 动态优先级：根据进程动态变化调整优先级，比如等待时间边长则升高优先级，运行时间增长则降低优先级，即随着时间推移动态调整进程的优先级

处理优先级高的两种方式：抢占式和非抢占式

• 非抢占式：当就绪队列出现优先级高的进程，运行完当前进程再选择优先级高的进程运行
• 抢占式：一旦出现高优先级进程，当前正在运行的进程就被挂起，调度优先级高的进程运行

多级反馈队列（Multilevel Feedback Queue）调度算法

多级：多个队列，每个队列优先级从高到低，同时优先级越高时间片越短

反馈：如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列（理解为抢占）

新的进程在到来之后，会被放到第一级队列的末尾，按先来先服务的原则排队等待调度，如果在第一级队列规定的时间片没运行完成则转入第二级队列的末尾，以此类推直到完成。当较高优先级队列为空时才调度较低优先级的队列中的进程运行。如果有新进程进入较高优先级队列，则停止当前进程并移入原队列末尾，让较高优先级的进程运行。

2、内存页面置换算法

缺页中断 / 缺页异常：当CPU访问的页面不在内存时，就会产生一个缺页中断，请求操作系统将所缺⻚调⼊到 物理内存

与⼀般中断的主要区别在于：缺页中断在指令执行「期间」产生和处理中断信号，而⼀般中断在一条指令执行「完成」后检查和处理中断信号。 缺页中断返回到该指令的开始重新执⾏「该指令」，而⼀般中断返回回到该指令的「下一个指令」执行

找到了磁盘中对应页面后，需要把该页面换入到物理内存中。在换入前需要在物理内存中找空闲页，找到空闲页后就把页面换入，并把页表项中状态位修改位有效（之前是无效），然后CPU重新执行导致缺页异常的指令。

如果在内存中找不到空闲页，则说明内存已满，需要页面置换算法选择一个物理页，如果该物理页有被修改过（脏页），则把它换出到磁盘，然后把该被置换出去的页表 项的状态改成「⽆效的」，最后把正在访问的⻚⾯装⼊到这个物理页中。

页表项字段如下

页面置换算法的功能是，当出现缺页异常，需调⼊新页面而内存已满时，选择被置换的物理页面

最佳页面置换算法（OPT）

置换在未来最长时间不访问的页面，但明显在实际系统中无法实现，因为不可能预知每个页面的下一次访问的时间。最佳页面置换算法的作用是衡量算法的效率，越接近该算法的效率则越说明算法高效

先进先出置换算法（FIFO）

选择在内存中驻留时间最长的页面进行置换

最近最久未使用的置换算法（LRU）

选择最长时间没有被访问的页面进行置换

需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。每次访问内存都必须更新整个链表，找到对应页面并移到表头是个耗时的操作。因此该算法开销较大，实际应用较少使用

时钟页面置换算法（Lock）

把所有的页面都保存在⼀个类似钟面的「环形链表」中，⼀个表针指向最 ⽼的页面。

如果它的访问位位是 0 就淘汰该页面，并把新的页面插⼊这个位置，然后把表针前移⼀ 个位置；如果访问位是 1 就清除访问位（即把1变成0），并把表针前移⼀个位置，重复这个过程直到找到了⼀个 访问位为 0 的⻚⾯为⽌

最不常用置换算法（LFU）

是当发⽣缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。

实现方式是对每个页面设置一个访问计数器，一旦被访问计数器就加1.发生缺页中断时淘汰计数器值最小的页面。可以通过考虑时间问题来改进，比如发生时间中断时把过去访问的页面的访问次数除以2，来避免过去一段时间经常访问但现在不怎么访问了的数据的影响。

3、磁盘调度算法

常见机械磁盘有多个盘片，每个盘面都有自己的磁头。盘片的每一层分为多个磁道，每个磁道分多个扇区，每个扇区512字节。多个相同编号的磁道形成一个圆柱，称为磁盘的柱面。

寻道时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省⼀些不必要 的寻道时间，从⽽提⾼磁盘的访问性能。磁盘调度算法的⽬的很简单，就是为了提⾼磁盘的访问性能，⼀般是通过优化磁盘的访问请求顺序来做到的

先来先服务（First-Come，First-Served，FCFS）

根据序列一个一个按顺序处理

最短寻道时间优先先（Shortest Seek First，SSF）

以这个序列为例⼦： 98，183，37，122，14，124，65，67

根据距离磁头（ 53 位置）最近的请求的算法，具体的请求则会是下列从左到右的 顺序： 65，67，37，14，98，122，124，183

但此算法可能导致某些请求饥饿，因为如果是一个动态的请求，后续的请求都小于183，那么183磁道可能永远不会被相应，磁头只会在一小块区域来回移动

扫描算法

磁头在⼀个⽅向上移动，访问所有未完成的请求，直到磁头到达该⽅向上的最后的磁道，才调换⽅向，这就是扫描（Scan）算法。这种算法也称电梯算法

根据此算法，具体请求则会是下列从左到右的顺序： 37，14， 0 ，65，67，98，122，124，183

循环扫描算法

以总是按相同的⽅向进⾏扫描，使得每个磁道的响应频率基本⼀致。该算法规定只有朝某个特定方向移动时才处理访问请求，复位时中途不处理任何请求

根据此算法，具体请求会是下列从左到右的顺序： 65，67，98，122，124，183， 199 ， 0 ，14，37

LOOK 与 C-LOOK算法

扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始 调方向。这是可以优化的，优化思路是：是磁头在移动到「最远的请求」位置，然后立即反向移动。

那针对 SCAN 算法的优化则叫 LOOK 算法，反向移动的途中会响应请求。⽽针对C-SCAN 算法的优化则叫 C-LOOK，反向移动的途中不会响应请求。