操作系统中的调度算法

处理机调度层次：

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

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

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

一、作业调度算法

1.先来先服务算法（FCFS）

2.短作业优先算法（SJF）

3.优先级调度算法（PR）

4.高响应比调度算法（PR特例）

5.时间片轮转算法（RR）

6.多级队列调度算法

7.基于公平原则的调度算法（主要考虑调度的公平性）

补：实时调度算法：针对实时任务

实现实时调度算法的基本条件：

1.提供必要的信息

如开始截止时间，完成截止时间、处理时间、资源、优先级

2.系统处理能力强

ps：处理时间ci，周期时间pi

3.采用抢占式调度机制

4.采用快速切换机制

对中断具有快速的响应能力；

快速的任务分派能力

实时调度算法：

1.最早截止时间优先调度算法（EDF）

2.最低松弛度优先算法（LLF）

二、连续分配存储管理方式--动态分区分配算法（第五章：存储器管理）

1.顺序式动态分区分配算法：

首次适应算法：从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。

缺点：低址部分留下许多小碎片

循环首次适应算法：从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。

优点：空闲分区分布均匀，减少了查找开销。

缺点：缺乏大的空闲分区。

最佳适应算法：空闲分区按照容量从小到大的顺序链接，搜索整个序列，找到适合条件的最小分区进行分配。

优点：用最小的空间满足要求。

缺点：留下许多难已利用的小碎片。

最坏适应算法：空闲分区按照容量从大到小的顺序链接搜索整个序列，寻找最大的分区进行分配。

优点：分割后空闲块仍为较大分块。

缺点：缺乏大的空闲块。

2.索引式动态分区分配算法：

快速适应算法：

伙伴系统：主要用于多处理机系统中。

哈希算法：建立哈希函数，构造一张以空闲区大小为关键字的哈希表，该表的每一个表项对应一个空闲分区链表的头指针。进行分配时，根据空闲区大小，通过计算哈希函数，得到哈希表中的位置，找到对应的空闲分区链表。

优点：查找快速

补：连续分配存储管理方式---动态重定位分区分配算法

类似于动态分区分配算法，增加了紧凑功能

紧凑：通过移动内存中的作业位置，把原来多个小分区拼接成一个大分区的方法，也叫拼接。

离散分区分配存储管理方式

补：局部性原理（存储器管理）

** 时间局部性：**如果程序的某个指令被执行，那么不久后这条指令很有可能再次被执行；如果某个数据被访问，不久后这个数据很可能再次被访问（因为程序中存在大量循环）。

空间局部性：一旦程序访问了某个存储单元，不久后其附近的存储单元很有可能被访问（因为很多数据在内存中都是连续存放的）

页面置换算法（第六章：虚拟存储器）

1.最佳置换算法（OPT）：

2.先进先出置换算法（FIFO）：

只有FIFO算法会出现Belady异常

Belady异常---当为进程分配的物理块数增多时，缺页次数不减反增的现象。

原因：虽实现简单，但是与进程实际运行时的规律不适应，因为先进入的页面可能是最常使用的页面。

** 3.最近最少使用算法（LRU）：**

选择最近最久未使用的页面予以淘汰

LRU实现需要专门的硬件支持，所以虽然性能好（性能最接近最佳适应算法），但实现困难，开销大。

4.最少使用置换算法（LFU）：

选择最近使用最少的页面进行淘汰。

5.clock算法

LRU近似算法，又称最近未用(NRU)或二次机会页面置换算法

最近未用(NRU)或二次机会页面置换算法

最近未用(NRU)或二次机会页面置换算法

6.改进的时钟置换算法：

补：抖动

抖动：一个进程的页面经常换入换出。

原因：系统为进程分配的物理块太少。