操作系统期末复习
五分钟了解期末大题大题银行家算法+页面置换算法
只是个人整理快速记忆理解，有错误请私聊纠正
1.银行家算法
首先认识几个词
- Available：可利用资源（未分配）
- Max：最大需求矩阵 max = 已分配+需求资源
- Allocation：分配矩阵（已分配）
- Need：需求矩阵（需资源）
- work ：未分配 （工作）
例题1
第一问：该状态是安全的吗？
按照下列流程计算，当可以以一种路线满足p0-4 则是安全的
按照这个流程计算即可，固定方式 无脑计算 （个人简便记忆理解）
-
未分配资源是当前空闲的资源
-
尚需资源是需要分配的资源
-
已分配资源是 当需求资源满足后会释放的空闲资源
所以计算的思路是，拿未分配的空闲资源，看看能满足谁的需求，当满足了需求以后，该已分配资源就会释放变为未分配资源。
可以看到 以p0 -> p3 -> p4 -> p2 -> p1这条路线满足了p0-4，所以该状态是安全的！
第二问：如果p1再次提出请求 0 3 2 1系统能否分配给它？
提出请求资源，那么未分配资源就会先满足他 。满足以后 该项的需求就会变低 所以最新的数据变成
按照这个最新数据 还是问题1的流程 看看是否能全部满足
2 1 1 0可以满足p0 释放后未分配资源为 2 1 2 0 不能满足任何一项 没能按照一条路线满足全部需求
所以系统不能够把资源分配给它！
正确的解答方式应该是这样的
例题2
第一问：
? p0 -> p3 -> p4 -> p1 -> p2 为安全序列 所以是安全的
第二问：
如果p2提出请求1 2 2 2则 数据更新为例题括号所示 未分配0 4 0 0 不能满足任何一项的需求资源，所以系统不能把资源分配给它！
2.页面置换算法
例题1
可以这样理解
一共有18个页(数字)先排列好 一共有3块存储空间，也就是说一次可以容纳三个数
在这个规则下，使用各种算法 列出计算的整个过程表
1.OPT最佳算法 ：淘汰最远将来才使用的页
耐心对照图片看完解释
首先第一个数 2进入空间1 这时空间还有空余 是缺页的
第二个数 3进入空间2 缺页
第三个数 1进入空间3 缺页
2进入空间 本身就在空间 不缺页
4进入空间 从231淘汰最远使用的数字 1是最远才能用到的 所以淘汰 4进入1的位置 空间3 缺页的
3进入 本身就在空间 不缺页
5进入空间 最远的是4 所以把4替换成5 缺页
后面省略
缺页10个 一共18个数 所以缺页率为10/18
2.FIFO先进先出置换算法：淘汰先进来的页
首先第一个数 2进入空间1 这时空间还有空余 是缺页的
第二个数 3进入空间2 缺页
第三个数 1进入空间3 缺页
2进入空间 本身就在空间 不缺页
4进入空间 2 3 1有一个要出去 看看谁先进来的 2是先进来的 4替换2
3进入空间 本身就在空间 不缺页
5进入空间 4 3 1有一个要出去 看看谁先进来的 1是先进来的 5替换1
后面省略
缺页14个 总共18个 所以缺页率是14/18
3.LRU最近最久未使用置换算法：淘汰最近最久未使用的页
首先第一个数 2进入空间1 这时空间还有空余 是缺页的
第二个数 3进入空间2 缺页
第三个数 1进入空间3 缺页
2进入空间 本身就在空间 不缺页
4进入空间 2 3 1有一个要出去 看看谁已经很长时间没使用了 3是最久没用的 4替换3
3进入空间 2 4 1有一个要出去 看看谁已经很长时间没使用了 1是最久没用的 3替换1
5进入空间 2 4 3有一个要出去 看看谁已经很长时间没使用了 2是最久没用的 5替换2
后面省略
