《《作业系统》计算题复习.docx》由会员分享，可在线阅读，更多相关《《作业系统》计算题复习.docx（7页珍藏版）》请在金锄头文库上搜索。
1、 作业系统计算题複习 计算题複习资料 1、程序同步 ： 重点：会用讯号量实现前趋关係以及程序同步。把握经典的程序同步问题：生产者-消费者问题。 例如：利用讯号量实现下图的前趋关係。 参答：var a,b,c,d,e,f,g; semaphore = 0,0,0,0,0,0,0; begin parbegin begin s1; signal(a); signal(b); end; begin wait(a); s2; signal(c); signal(d); end; begin wait(b); s3; signal(e); end; begin wait(c); s4; signal(f
2、); end; begin wait(d); s5; signal(g); end; begin wait(e); wait(f); wait(g); s6; end; parend end（2）桌上有一空盘，允许存放一个水果。爸爸可向盘中放苹果，或放橘子，儿子专门等着吃盘中的橘子，女儿专门等着吃盘中的苹果。规定当盘空时一次只能放一个水果供取用，试实现爸爸、儿子和女儿三个併发程序的同步。 解决：讯号量:empty=1;orange=0;apple=0; 爸爸程序: while(1) 儿子程序: while(1) 女儿程序: while(1) （3）经典的程序同步问题：生产者-消费者问题 k个缓
3、冲区、i个生产者和j个消费者，通过一个迴圈有界多缓冲区把i个生产者和j个消费者联络起来。 解决：struct semaphore mutex=1, empty=k, full=0; struct message bufferk, int in,out =0; ; *sumer( ) ; 2、把握常用的排程演算法，把握银行家演算法 (1) 先来先服务(fcfs) 排程演算法 作业排程中： 根本思想：以作业进入后备伫列的先后为依据。 从后备伫列选一个或多个最先进入伫列的作业 将作业调入记忆体、安排资源、建立程序 放入程序就绪伫列 程序排程中： 根本思想：从就绪伫列中选择一个最先进入该伫列的程序，将
4、cpu安排给该程序，进入执行状态，始终执行到完成或发生某大事而让出cpu。 例如：解决： （2）短作业(程序) 排程演算法sj(p)f 作业排程中： 根本思想：作业排程程式在后备伫列中选择一个或多个估计执行时间最短的作业 ，将它们调入记忆体执行。 程序排程中： 根本思想：从就绪伫列中选出一个估计执行时间最短的程序，将cpu安排给该程序，进入执行状态，始终执行到完成或发生某大事而让出cpu。 例如：解决： （3）最高优先权优先(fpf)排程演算法 作业排程中： 根本思想：从后备伫列中选择若干个优先权最高的作业，装入记忆体。 程序排程中： 根本思想：为系统中每一个程序规定一个优先顺序，就绪伫列中具
5、有高优先顺序的程序有优先获得cpu的权利；假如几个程序的优先顺序一样，则按先来先服务演算法排程。 例如：和短作业优先演算法类似，只要把执行时间换成优先顺序即可。 （4）高响应比优先排程演算法 作业的响应比rp：某一作业已经等待的时间+要求执行时间与所需执行时间之比。 rp = 作业响应时间 /要求执行时间 作业已等待时间+要求执行时间)/要求执行时间 = 1+作业已等待时间/要求执行时间 作业排程程式每当挑选作业时，先计算当时后备伫列中各作业的响应比 ，然后选择其中响应比最高的作业进入执行状态。 例如：解决： （5）银行家演算法 os根据程序提出资源请求时的资源使用情况，根据肯定的演算法模拟安
6、排，若认为安排后系统将处于“安全状态”，就实行安排；若认为安排后系统将处于“担心全状态”，就取消安排。从而保证系统处于“安全状态”，使死锁得以避开。 避开死锁的实质:使系统不进入“担心全状态”。 例如：假定系统中有五个程序p0, p1, p2, p3, p4和三类资源a, b, c，各种资源的数量分别为10、5、7，在t0时刻的资源安排情况如图 3-15 所示。 （1）问此时该系统是否是安全状态？假如是，写出一个安全序列。 答：t0时刻存在一个安全序列(p1, p3, p4, p0, p2)或(p1, p3, p4, p2, p0) 。所以系统是安全的。 在此基础上 （1）p1请求资源(1,
7、0, 2 )，系统能否把资源安排费它？为什么？ 可以。见书上p111. 在(1)的基础上 （2）p0请求资源(0, 2, 0 )，系统能否把资源安排费它？为什么？ 系统不能把资源安排给它，因为安排后新的p0 need向量为（），其它程序的need向量不变，而新的可用资源向量为（），不满足p0p4的全部need向量。所以造成死锁。 3、储存器治理 （1）根本页式储存器治理 逻辑地址到实体地址的转换 当程序访问某逻辑地址3081时，地址变换过程： 逻辑地址3081 实体地址） 逻辑地址3081 （页号,页内地址） (3,9) 页面长度1k 比较：页号 页表长度（页表暂存器中） 越界中断 n表项在页
8、表中位置 = 页表始址+页号页表项长度 从表项中取得对应该页的物理块号，装入实体地址暂存器 第3页面对应块号是11) 逻辑地址暂存器的页内地址实体地址暂存器的块内地址 物理块号11+ 块内地址9 实体地址11*1024+9=11273 例如：已知记忆体容量为64kb，某一作业a的逻辑地址空间共有4k，分为4个页面，页面0、1、2、3分别被安排到记忆体空间的2、4、6、7四个物理块中，在逻辑地址为200处有一条取数指令“load 1，3500”， （1）画出作业a的页表； （2）当指令“load 1，3500”执行时，产生的实体地址应是什么？ 解： (1) 页表 （2）虚拟地址3500对应的页号
9、是： 3500/1024=3（“/”是整除运算子） 对应的页内位移是： 3500/1024=428（“%”是求余运算子） 3500对应的数对为（3，428）， 用3去查页表，知道第3页现在存放在记忆体的第7块。第7块的起始地址为7168。因此，逻辑地址3500所对应的实体地址是： 实体地址为（7，428）， 由于页面大小为1k 实体地址为：71024+428=7596 （2）页面淘汰演算法 先进先出页面淘汰演算法（fifo） 选择在记忆体中驻留时间最长的页并淘汰之 抱负淘汰演算法最正确页面演算法（opt） 淘汰以后不再需要的或最远的将来才会用到的页面 最近最少使用页面淘汰演算法（lru） 选择最后一次访问时间距离当前时间最长的一页并淘汰之，即淘汰没有使用的时间最长的页 例如：某程式在记忆体中安排三个物理块，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5，计算缺页次数和缺页率。 共缺页中断9次 共缺页中断10次 共缺页中断7次 4、磁碟储存器治理 磁碟排程策略： 先来先服务（fcfs）策略
