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

两个问题

生产者消费者问题

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

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

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

举个例子儿：

哲学家进餐问题

设计不同时进餐的算法：

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

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

进程和线程：

调度算法：

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

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

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

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

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

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

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

死锁避免：
银行家算法

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

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

内存管理：

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

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

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

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

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

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

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

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

Clock和改进的Clock,

Clock:12字真言：首入置1，若0则出，若1则0（给出当前则始于当前，否则始于装入最早，按页面递增进行）；

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

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

（注：本题明确基于字节编址）

磁盘调度算法

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

SCAN算法

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

C-SCAN算法

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

LOOK

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

CLOOK

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