进程调度算法、页面置换算法

时间:2022-07-20 20:03:40

一、进程调度算法

1、先来先服务调度算法FCFS
先到的进程先调度,执行过程不会被中断直到进程结束。
优点:易于实现,且相当公平。
缺点:比较有利于长进程,而不利于短进程,有利于CPU 繁忙的进程,而不利于I/O 繁忙的进程
2、短作业优先调度算法SJF
优先分配给短进程执行。
优点:平均周转时间最短,进程等待时间缩短,可以增大系统吞吐量。
缺点:难以准确预估进程执行时间,开销较大;不利于长进程,有可能出现“饥饿”现象。
3、最高响应比调度算法HRRN
一种关于先来先服务和短作业优先的折中算法,当一个长进程等待时间过长,就会获得较高的优先权,因此不会出现“饥饿”现象。
优先级D = (执行时间 + 等待时间) / 执行时间。
优点:不会出现“饥饿”现象,长作业也有机会被调度。
缺点:每次都需要计算优先级,系统开销大。
4、时间片轮转调度算法RR
为进程设定时间片,即每个进程运行运行的时间,在一个时间片结束时,发生时钟中断,调度程序暂停执行并加入队尾,通过上下文切换执行当前队首进程。
优点:算法简单,响应时间短。
缺点:不利于处理紧急作业;时间片过小会导致频繁进程上下文切换,增大系统开销;时间片过长则会退化为FCFS。
5、多级反馈队列调度算法
①进程首先进入优先级最高的队列1等待 ;
②首先调度优先级最高的队列,如果队列中没有进程可调度则依次调用优先级较低的队列;
③在每一队列中按时间片轮转算法调度,且每一级队列的时间片长度都比上一级要长;(一般是上一级的2倍)
④若有新的进程到达,则当前时间片执行完后,就执行该进程。
优点:1)对于终端型用户的交互作业,通常较小,系统可以在第一队列完成作业;2)对于短批处理作业用户,可以在优先级很高的队列执行一时间片完成,周转时间仍然较短;3)对于长批作业处理用户,可以依次在1,2,3,…,n个队列中运行,不用担心长作业得不到处理。

二、页面置换算法

1、先进先出置换算法FIFO
淘汰最早进入内存的页面。
优点:只需要一个队列实现简单。
缺点:该算法与进程实际的规律并不相适应,因为在进程中,有些页面经常被访问,比如:含有全局变量、常用函数、例程等的页面,FIFO不能保证这些页面不会被淘汰。
2、最佳置换算法
每次淘汰时,找一个未来最长时间才会被访问的页面进行淘汰。
优点:缺页率最低。
缺点:需要预测未来,无法实现,但可以用来衡量其他置换算法。
3、最近最久未使用置换算法LRU
利用过去预测未来,记录每个页面从上次被访问以来经过的时间T,每次淘汰时,选择T值最大的页面进行淘汰。
4、最少使用只算算法LFU
为每个页面设置一个移位寄存器,用来记录该页面访问频率,每次访问时将最高位置1,每隔一定时间(100ms)右移一次,每次淘汰时,将访问次数最少的页面淘汰。
5、时钟置换算法
简单的时钟置换算法:为每一页设置访问位,将内存中所有页面通过链接指针接成循环队列,当页面被访问时访问位置1,每次淘汰时,从指针当前位置开始循环遍历,将访问位为1的置为0,找到第一个访问位为0的将其淘汰。
改进型时钟置换算法:添加修改位,每次修改后将修改位置1。遍历时,如果访问位为1则先将访问位置0,否则如果修改位为1则将修改位置0(并将修改写入外存),找到第一个访问位和修改位均为0的页面进行淘汰。