OS丛话(算法篇)
2022-12-18 08:48:49 Author: www.freebuf.com(查看原文) 阅读量:3 收藏

操作系统这门课,从应试的角度来讲,无非就是几个算法和几个问题。 ——r2ate1

两个问题

生产者消费者问题

核心是分清同步和互斥关系,然后设置几个对应的信号量,实现同步和互斥

注意:实现互斥的P操作应置于实现同步的P操作之后,来避免死锁

关于信号的设置问题:empty和full自然不必多说,每个缓冲区对应一对的empty和full;那么mutex呢,也是如此,不只是同类进程之间要互斥,不同类型的进程之间也要实现互斥。其实从互斥锁的角度来讲,生产者进程和消费者进程都是进程,是平等的,而且这个缓冲区的数量决定了互斥锁的数量。

举个例子儿:

1669987865_6389fe1975b76617e9135.png!small?1669987865821

1669991051_638a0a8bd4860437c8199.png!small?1669991052395

哲学家进餐问题

设计不同时进餐的算法:

1671118264_639b3db831b72d05a208f.png!small?1671118266221

设计既没有同时进餐,又不会有人饿死的算法:设置奇数(优先拿左边的筷子i)和偶数(优先拿右边的筷子(i+1)mod(5))

1671118295_639b3dd73d55a27694ecd.png!small?1671118297052

5(进程调度)+1(死锁避免)+8(页面调度)+6(磁盘调度)个算法

进程和线程:

调度算法:

先来先服务 时间片轮转 短作业优先 高相应比优先 优先级调度 多级调度 和多级反馈队列调度。

先来先服务:算法简单但代价是效率低,对长作业有利,对短作业不利;有利于CPU繁忙型,不利于IO繁忙型。

短作业优先:有利于短作业,不利于长作业,这里的不利,是真正会造成饥饿现象,也就是长作业长期不能得到调度;没有考虑作业的紧迫性问题;同时估计时间可能会被恶意用户欺骗;突出特点就是该算法平均等待时间和平均周转时间最少。

时间片轮转:主要用于分时系统,为了多个用户能及时干预系统。

高相应比优先:就一个公式,(等待时间+要求服务时间)/(要求服务时间)。由待定系数法得,等待时间相同时,要求服务时间越短,相应比越高;当要求服务时间相同时,等待时间越长,相应比越高,由此克服了“饥饿”现象。

优先级调度:
主要考虑作业的紧迫性问题,注意在设置优先级的时候,I/O型进程的优先级要高于计算型进程的优先级。

多级调度和多级反馈队列调度期末考的比较少,在此不展开讨论。

死锁避免:
银行家算法

看到网上有很多视频讲这个东西,越看越复杂,做了几道题之后,感觉思路又清晰了起来。

其实就是一个安全性判断的问题,记得老师讲课的时候是以充分必要条件引入的此问题(死锁一定处于不安全状态,处于不安全状态不一定会发生死锁),银行家算法的本质就是找一个安全序列。

内存管理:

首次适应算法 邻近适应 最佳适应 最坏适应

首次适应算法和邻近适应算法比较简单,不想不说。

最佳适应和最坏适应算法一个是按容量递增,另一个是按容量递减。

这里主要注意一点,单一和固定都只有内部碎片,没有外部碎片,动态反之。

页面调度/置换算法: 
LRU CLock和改进的clock  OPT(理想注意者) 先进先出

先进先出,没什么好说的。

OPT(最佳置换算法),先知型调度算法,没有人可以预测未来,算法也不例外。

LRU,基于局部性原理,即过去可以在一定程度上反应未来的哲学,该算法在实际研发中也得到了广泛的应用。

Clock和改进的Clock,

Clock:12字真言:首入置1,若0则出,若1则0(给出当前则始于当前,否则始于装入最早,按页面递增进行);

改进的Clock,简而言之,就是检查访问位和修改位均为0的换出

其实对于页面置换,重在置换二字,上到小菜,感兴趣的简单悟一悟即可:

(注:本题明确基于字节编址)

1669990999_638a0a57d7e1bd246ca33.png!small?1669991000521

1669991015_638a0a6756cf12cf2f1c1.png!small?1669991015978

磁盘调度算法

先来先服务和最短寻找时间优先比较简单,不再赘述。

SCAN算法

又称为电梯算法:实际上就是在SSTF算法的基础上规定了磁头移动方向,该算法对最近扫描过的区域不公平。

C-SCAN算法

在扫描算法的基础上规定磁头单向移动来提供服务,回返时直接快速移动到起始端而不服务任何请求。

LOOK

SCAN算法的不需要到达磁盘端点形式

CLOOK

C-SCAN算法的不需要到达磁盘端点形式


文章来源: https://www.freebuf.com/articles/neopoints/352811.html
如有侵权请联系:admin#unsafe.sh