[数据结构与算法]内存调页算法+CPU调度算法

1、内存调页算法

当进程访问虚拟地址时，会查看页表，如果发生对应的数据不再物理内存上会发生缺页异常，产生一个缺页中断去寻找空闲页，找不到空闲页的话，就说明此时内存已满了，就需要页面置换算法选择?个物理页。

1. 最佳页面置换算法（OPT）计算页面下一次访问时间，然后比较，选择未来最长时间不访问的页面，实际中无法实现，访问页面是动态的，用来衡量其他算法效率。
2. 先进先出置换算法（FIFO）:选择在内存驻留时间很长的页面进行中置换。
3. 最近最久未使用的置换算法（LRU）：完全实现 LRU，需要在内存中维护?个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。在每次访问内存时都必须要更新整个链表。在链表中找到?个页面，删除它，然后把它移动到表头是?个十分费时的操作。
4. 时钟页面置换算法（lock）：所有页面保存在环形链表，表针指向最老页面；①它的访问位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移?个位置；②如果访问位是1就清除访问位，置0，并把表针前移?个位置，重复这个过程直到找到了?个访问位为0的页面为止；
5. 最不常用置换算法（LFU）选择访问次数最少的那个页面，并将其淘汰，增加计数器，被访问就会累加。

2、CPU调度算法

选择某个进程分配给CPU，影响的是等待时间。

1. 先来先服务：选择最先进入队列的进程，直到退出或阻塞；对长作业有利，适合CPU繁忙型不适合IO繁忙型，因为短作业等待时间长。
2. 最短作业优先：优先选择运行时间最短的进程运行，可以提高系统吞吐量。
3. 高响应比优先：响应比优先级高的先运行，响应比优先级 =(等待时间 + 要求服务时间）/要求服务时间。兼顾长短作业。
4. 时间片轮转算法：每个进程被分配?个时间段，称为时间片。一个进程时间片用完就会进行调度，CPU分配给另一个进程；在时间片结束前阻塞或结束，CPU立即进行切换。
5. 最高优先级：多用户系统希望可以选择优先级最高的进程先运行。
6. 多级反馈队列：多个队列优先级越高时间片越短，优先级高的进程进入，停止当前去运行优先级高的；兼顾了长短作业，同时有较好的响应时间。