admin 管理员组文章数量: 887019
操作系统期末大题复习，简单的语言讲解各种算法。
1.作业调度
(1). 先来先服务调度算法---------FCFS
按照作业到达的先后次序来进行调度
完成时间=开始时间+服务时间
周转时间=完成时间-到达时间
带权周转时间=周转时间/服务时间
A的结束时间，是B作业的开始时间
例：
| 作业号 | 提交时间 | 执行时间 |
|---|---|---|
| 1 | 8.0 | 2.5 |
| 2 | 8.5 | 1.8 |
| 3 | 9.4 | 1.0 |
求平均周转时间
解：求平均周转时间，就要知道完成时间和周转时间
| 作业号 | 提交时间 | 执行时间 | 开始时间 | 完成时间 | 周转时间 |
|---|---|---|---|---|---|
| 1 | 8.0 | 2.5 | 8.0 | 10.5 | 2.5 |
| 2 | 8.5 | 1.8 | 10.5 | 12.3 | 3.8 |
| 3 | 9.4 | 1.0 | 12.3 | 13.3 | 3.9 |
平均周转时间：（2.5+3.8+3.8）/3=3.4
(2). 短作业优先调度算法--------SJF
以作业的长短来计算优先级，作业越短，优先级越高。
从1号作业开始运行，运行完以后，看后面的服务时间，优先服务时间短的。
| 作业号 | 提交时间 | 执行时间 |
|---|---|---|
| 1 | 8.0 | 2.5 |
| 2 | 8.5 | 1.8 |
| 3 | 9.4 | 1.0 |
解：
| 作业号 | 提交时间 | 执行时间 | 开始时间 | 完成时间 | 周转时间 |
|---|---|---|---|---|---|
| 1 | 8.0 | 2.5 | 8.0 | 10.5 | 2.5 |
| 2 | 8.5 | 1.8 | 11.5 | 13.3 | 4.8 |
| 3 | 9.4 | 1.0 | 10.5 | 11.5 | 2.1 |
平均周转时间：（2.5+4.8+2.1）/3≈3.1
2. 银行家算法--------避免死锁
银行家算法中的数据结构：
-
Available--可利用资源向量--系统总共有多少资源
-
Max--最大需求矩阵--进程需要系统给多少资源
-
Allocation--分配矩阵--系统已经给进程多少资源
-
Need--需求矩阵--进程还要多少资源
Need=Max-Allocation
例：
| Process | Allocation | Need | Available |
|---|---|---|---|
| P0 | 0 0 3 2 | 0 0 1 2 | 1 6 2 2 |
| P1 | 1 0 0 0 | 1 7 5 0 | |
| P2 | 1 3 5 4 | 2 3 5 6 | |
| P3 | 0 3 3 2 | 0 6 5 2 | |
| P4 | 0 0 1 4 | 0 6 5 6 |
该状态是否安全？
解：要判断是否安全，我们需要设置两个向量
依次找到Need＜Available的作业，进行下面操作
-
Work--工作向量--系统可以提供的资源--开始时 work=Available;等到下个进程时，work=上个进程的work+allocation;
-
Finish--进行判断,需要的是否小于系统有的，Need ≤ Work
| Process | Work(系统有的) | Need(他需要的) | Allocation(已经给的) | Work+Allocation(弄完还的) | Finish |
|---|---|---|---|---|---|
| P0 | 1 6 2 2 | 0 0 1 2 | 0 0 3 2 | 1 6 5 4 | ture |
| P3 | 1 6 5 4 | 0 6 5 2 | 0 3 3 2 | 1 9 8 6 | ture |
| P4 | 1 9 8 6 | 0 6 5 6 | 0 0 1 4 | 1 9 9 10 | ture |
| P1 | 1 9 9 10 | 1 7 5 0 | 1 0 0 0 | 2 9 9 10 | ture |
| P2 | 2 9 9 10 | 2 3 5 6 | 1 3 5 4 | 3 12 14 14 | ture |
存在安全序列{P0，P3，P4，P1，P2}故安全
若P2提出请求（1,2,2,2）后，系统能否分配？
解： 系统剩余（1,6,2,2),P2提出（1,2,2,2），系统还剩（0,4,0,0），此时已经不满足任何一个作业，所以不能分配。
3. 页号、页内地址和物理地址的计算
-
页号--P
-
页内地址--d
-
页面大小--L
-
1KB=1024B;2KB=2048B
P = INT[A/L]--------INT取整
d = [A] MOD L
物理地址：页号*页面大小+页内地址
例：
(1). 某页式存储系统页表如下，设每页为1KB，请写出逻辑地址为8300对应的页号和页内地址，以及物理地址。
| 页号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 块号 | 3 | 5 | 6 | 10 | 8 | 7 | 1 | 2 | 4 |
解：
-
页号P = INT [A/L]=[8300/1024]=8
-
页内地址d = [A] MOD L = 8300 % 1024 = 108
-
物理地址：4 * 1024 + 108 =4204
(2). 已知如下表：
| 段号 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 基址 | 219 | 2300 | 90 | 1327 | 1952 |
| 长度 | 600 | 14 | 100 | 580 | 96 |
在分段存储管理下，逻辑地址a(1,10)和b(4,112)的物理地址什么？[第一位表示段号，第二位表示段内位移]
解：a(1,10) 1为段号，对应基址2300，段内位移10，物理地址 = 2300+10=2310；
b(4,112) 4为段号，对应基址1952，段内位移112，但b的长度为96，所以地址(4,122)越界。
4. 页面置换算法
页面置换次数 = 从第一次置换开始到最后依一次结束，中断不算
缺页 = 正确的载入内存
中断 = 有重复的页面进入
(1). 先进先出算法-------FIFO
淘汰最先进入内存的页面---就看哪个存在的最长时间，直接替换，中断页面不算更新
(2).最近最久未使用算法--------LRU
淘汰最近最最久未使用的页面---就看哪个最长时间没动过，直接替换，中断算更新，t值重新计算(t值为页面进入内存的时间)
5. 电梯调度算法
即扫描算法---------SCAN
从当前位置出发，照着磁头的方向（增大或减小）扫描。
减小：从当前柱面出发，依次递减找到比自己小的柱面，直至没有更小，在递增比自己大的柱面。
增大：从当前柱面出发，依次递增找到比自己大的柱面，直至没有更大，在递减比自己大的柱面。
磁道数：拿现在的磁道数 — 下一个磁道数 --- 当递增时，拿下一个磁道数 — 现在的磁道数
平均寻道长度：总磁道数/总柱面个数
例：磁头在100柱面，磁头向磁道号减小方向移动。柱面号：190,10,160,80,90,125,30,20,29,140,25.求总磁道数和平均寻道长度。
解：处理次序：100 - 90 - 80 - 30 - 29 - 25 - 20 - 10 - 125 - 140 - 160 - 190
总磁道数：(100-90)+(90-80)+(80-30)+(30-29)+(29-25)+(25-20)+(20-10)+(125-10)+(140-125)+(160-140)+(190-160)=270
平均寻到长度：270/11=24.5
版权声明：本文标题：操作系统期末复习之大题讲解-远离挂科-作业调度算法-银行家算法-页号、页内地址和物理地址的计算-电梯调度算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727376398h1110867.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论