OS算法总结V1.0 Edit by HDJ @ HUAT 20101130
OS算法总结V1.0
第四章：并发处理
PV操作相关描述【P91】
2-1.单缓冲区
putcopygets1s2s3s4stmain() {
int S1 = 1, S2 = 0; S3 = 0; S4 = 0; cobegin get(); copy(); put(); coend } get() { while(任务未完成) { P(s1); 向s中送数据; V(S2);
} }
copy() { while(任务未完成) { P(S2); 从S中取记录; V(S1); P(S3); 向t中送数据; V(S4);
}
} put() { while(任务未完成) { P(S4); 从t中取数据; V(S3);
} }
2-2.司机售票员
main() {
int S1 = 0, S2 = 0;; cobegin driver(); conductor(); coend }
driver() { while(任务未完成) { 正常行车; 到站停车; V(S2); P(S1); 启动;
} }
conductor() { while(任务未完成) { 售票; P(S2); 开车门; 关车门; V(S1);
1
OS算法总结V1.0 Edit by HDJ @ HUAT 20101130
} }
第五章：资源分批与调度
3-1.磁盘调度【P125】
（1）FCFS【先来先服务】 （2）SSTF【最短磁道优先】
（3）SCAN【扫描算法\\电梯算法】 Example：
系统完成了磁道125处的请求后，当前正在磁道143处为一个请求服务。若轻队列顺序为：86,147,91,177,94,150,102,175,130，分别采用FCFS，SSTF，SCAN算法完成上述请求，写出磁盘磁头的移动顺序，并计算移动总量。 Solution： （1）FCFS： 磁头移动顺序：
143,86,147,91,177,94,150,102,175,130 移动总量：565 （2）SSTF： 磁头移动顺序：
143,147,150,130,102,94,91,86,175,177 移动总量：162
（3）SCAN【注意磁头移动的方向】 磁头移动顺序：
143,147,150,175,177,130,102,94,91,86 移动总量：126
设系统有3中资源，某时刻有四个进程，其最大需求向量和已分配资源向量分别是：
进程 已分配资源 最大需求 P1 （1,0,0） （3,2,2） P2 （5,1,1） （6,1,3） P3 （2,1,1） （3,1,4） P4 （0,0,2） （4,2,2）
系统资源向量Avai=（1,1,2）.，问：
（1） 如P2发出资源请求向量（1,0,1）能
否立即分配？
（2） 如P1发出（1,0,1）呢？
Steps：
（1） 列出各种向量
（2） 假定满足，列出系统状态
（3） 先满足„完成后释放资源，Avi=
（„），然后运行„
（4） 存在安全序列，可以立即分配OR不
存在安全序列，不可分配。
Solution：
step1.当前系统状态：
100511（已分配资源数） Allo211002322613（最大需求资源数） Max314422222102（仍需要资源数） Need103420step2.假定满足P2资源请求请求（1,0,1），此
时系统状态变为：
3-2.最坏情况分析法（证明）
证：假设进程Pi最大需求为Si，已知：
pSipm（p：进程数，m：最大资源
i1数），考虑最坏情况，每个进程都分配到最大需求减一个资源，则已分配的资源数为： S1-1+S2-1+…+Sp-1=
p Sip,由已知可得：
i1pSipm，所以定满足至少一个进程的
i1全部需求，不会造成死锁。
3-3.银行家算法【找安全序列P135】
Example:
2
OS算法总结V1.0 Edit by HDJ @ HUAT 20101130
100612（已分配资源数） Allo211002322613（最大需求资源数） Max314422222001（仍需要资源数） Need103420Avai=（0,1,1）
Step3.P2完成后，释放资源Avai=（6,2,3）；然后运行P1，，P1完成后，释放资源Avai=（7,2,3）；然后运行P4，Avai=（7,2,5）；然后运行P3，Avai=（9,3,6）。即存在安全序列（P2,P1,P4,P3），故可以给P2立即分配资源。
第二问解题方法相同。
BF：
300K078K150K0120K^ FF：给作业1分配50K后第一块空闲区还剩70K，然后分配给作业2，第一块空闲区剩10K，不足以分配给作业3，作业三分配到第二块空闲区中，完成分配任务。 BF：给作业1分配50K后第一块空闲区还剩28K，不足以分配给作业二，在第二块空闲区给作业2分配60K，还剩60K，剩余空间不足以分配给作业3，不能完成分配任务。
3-2 页式地址转换【P175】
Steps：
（1） 根据页长分离页号与页内地址 （2） 检索页表，根据页号查快号 （3） 拼接块号与页内地址得物理地址 Example：
MOV r1 [2500]，页面大小为1K，页表如下：
第六章：处理及调度
1-1 P157 6-6作业调度算法
注意：
（1）周转时间 = 完成时间 - 提交时间 （2）带权周转时间 = 周转时间 / 执行时间 具体描述【P143】
247
第七章：主存管理
3-1 P194 7-7 放置策略【P169】
三种基本放置策略：
（1）FF：首次适应法（从前到后放置） （2）BF：最佳适应法（从小到大放置） （3）WF：最坏适应法（从大到小放置） Solution： FF：
Solution：
可以直接用“除留余数法” 2500/(2^10)=2500/1024=2…452 其中2为页号，452为页内地址。
根据页表，可以查的块号为7，注意页号是从0开始的。
因此物理地址为：7*1024+452=7620
3-3 淘汰策略（置换策略）【P180】
缺页中断率：f’=f/a f：访问失败次数
a=f+s即总访问次数，s为访问成功次数
（1）OPT（最佳算法）理论算法，无法实现 （2）FIFO（先进先出）
（3）LRU（最久未使用淘汰） （4）LFU（最不经常使用淘汰） Example：
m=3（m为系统分配的主存块数），页号引用
3
150K0120K200K078K^ OS算法总结V1.0 Edit by HDJ @ HUAT 20101130
串为0,2,1,0,3,0,1,4,1
V(S2)； 试分别统计出引用FIFO和LRU置换算法的 P(S3)；
f’。
向buf2送数据； Solution：
V(S4)；
FIFO：【淘汰内存内出现次数最多的】
}
0}
020103get（） 20230314{ 121031101404 while（任务未完成）
P(S2)； f’=7/9=77.8% 从buf1中取数据； LRU：【淘汰内存块上面弄离之最远的】
V(S1)； 0 P(S4)； 0201031 从buf2中取数据； 2020014 V(S3)； 130141}
2-2 缓冲池管理【P203】
f’=5/9=55.6%
main（） 第八章：输入输出管理
{ int mutex=1，s=n； 2-1 双缓冲区管理【P202】
cobegin allocation（）； puts1s2getputs3s4get free（）； buf1buf2 coend
}
allocation（） putget{ s1s2s3s4 while（任务未完成）
buf1buf2{
P(s)； main()
P(mutex)； { 从缓冲池取出一个缓冲区； int S1=1,S2=0,S3=1,S4=0; V(mutex)； cobegin 分配缓冲区； get(); } put(); }
coend free（） } { put() while（任务未完成） { { while(任务未完成) P(mutex)； { 将缓冲区放入到缓冲池； P(S1)； V(mutex)； 向buf1送数据；
V(s)；
4
OS算法总结V1.0 Edit by HDJ @ HUAT 20101130
} }
第九章：文件系统
2-1 UNIX的文件索引结构【P261】
Example：
Unix下有一个文件为2222个记录，试画出其文件索引结构。
厖i_addr[0]厖厖厖i_addr[6]i_addr[7]?????????厖厖厖????7*256=17922222厖厖2530厖?????厖厖????厖????174Solution：
2-2文件目录索引结构及共享【P278 9-18】
甲乙abceadefabcead 这个题还是比较简单的，大家主要看一下画图的格式，注意共享文件时用虚线箭头，考试的时候肯定还会有写绝对路径即从哪个文件到那个文件的相对路径，注意在Linux中写路径要用“/”，“./”代表当前目录，“../”代表上级目录。
以上便是对各章可能出的大题的总结，时间仓促，未能校正，如有错误大家及时跟我说！除了这些，我们也要重视基本概念的复习，前几天我看了一下往年的题目，填空很变态！ 最后祝大家都能考个好的成绩！
奋斗的涂涂 于2010-12-1
5
