Free考研资料 - 免费考研论坛

 找回密码
 注册

北京大学2006年os试题和答案(转载)

[复制链接]
高校 发表于 07-4-17 18:58:59 | 显示全部楼层 |阅读模式
来自Supremgoooo

六,操作系统问答题(共40分)
1.(10分)请描述中断响应过程,并说明操作系统对该过程提供什么支持。

答:该题的权威答案(陈向群教授版)是:
(i)保护现场,恢复现场
(ii)为中断处理做好准备

2.(每小题8分,共16分)关于存储管理:
(1)地址转换过程中快表(TLB)的作用,特点和内容.

答:引入快表主要是为了提高地址变换的速度。
  以页式变换中的快表为例,它其实是页表的一个子集,里面保存了最近一段时间内访问的页面项,其表项包括了找到一页的所有特征,快表与页表本质上构成了一个二级存储体系结构。根据程序访问的局部性原理,快表中的页面在将来是很有可能被访问到的。在地址变换的过程中,快表和页表被同时查找,由于快表相对于页表很小,且一般采用sram制作,如果命中,则大大提高了查找速度。如果没有命中,则需要将被访问页面表项复写到快表中,这一过程可以这样进行:如果快表未满,则直接写入;如果快表已满,需要采用某种替换算法加以解决,而具体的算法可能增加快表的表项,例如在LRU算法中需要设置访问计数器。

(2)提出工作集模型是为了解决什么问题?举例说明该模型对软件编程人员的影响.

答:工作集模型某个进程经常使用页面数的最小值。它的提出,一方面减少了程序缺页中断的次数,另一方面也提高了内存的使用效率。
  其对编成人员影响大致有三个方面:
  (i)作为一名计算机工作人员,要充分认识到程序访问局部性原理在各个方面的应用。
  (ii)在编程时要把常用的函数模块化,要把它们尽量放在一起;在程序中尽量不出现大范围的跳转语句或明显不合常规的语法,以提高程序执行速度。
  (iii)和cache的选取原则一样,要深刻的领悟“过犹不及”在整体设计时的重要性,任何项目都要追求最高的性价比。

3.(14分)试设计一个多级目录结构,要求目录检索速度快.请详细描述你的方案.

答:(i)参考nuix的三级索引结构:在根目录块的前12项中直接存放文件地址;13项指向一级索引表,一级索引表给出256个磁盘地址;14项指向二级索引表,二级索引表给出256个一级索引表地址;15项指向三级索引表,三级索引表给出256二级索引表地址。
(ii)采用文件的目录项分解法,把文件名与文件号单独拿出,以便在一个磁盘块中存放更多的文件,从而减少平均访盘次数
(iii)把各文件在索引结构中尽量按照访问概率排放,把经常访问的文件放到直接索引项中。增加常驻内存的索引表数,考虑将多个索引表常驻内存。要对最近访问到的文件进行缓存。
(iv)可以对磁盘进行散列处理,通过硬件实现的散列函数实现文件查找。

七.操作系统应用题(共16分)
1.(10分)在一个多道程序系统中,采用最高相应比优先算法调度作业.现有如下表所示的作业序列,请列出各个作业的开始时间,完成时间和周转时间.注意:忽略系统开销.
作业名     进入输入井的时间  估计运行时间   
JOB1       8:00         70分钟        
JOB2       8:20         20分钟        
JOB3       8:40        40分钟        
JOB4       8:50         30分钟        
JOB5   9:00    10分钟

答:
作业名    进输入井时间     运行时间    开始时间    完成时间  周转时间(m)
job1   8:00   8:00-8:40    8:00
            10:20-10:50   10:20   10:50   170
job2   8:20     8:40-9:00  8:40    9:00      40
job3   8:40     9:00-9:40    9:00    9:40   60
job4   8:50     9:50-10:20   9:50    10:20    90
job5   9:00     9:40-9:50    9:40    9:50    50    


2.(6分)假设一个活动头磁盘有200道,编号从0-199。当前磁头正在155道上服务,并且在此之前完成的是173道的访盘请求。现有如下访盘请求序列(磁盘号):
75,168,81,138,87,143,187,129,198,44
试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数)。
(i)最短寻道时间优先(SSTF)磁盘调度算法。
(ii)扫描法(SCAN)磁盘调度算法(假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动。)
答:(i)SSTF
磁头移动顺序:
155,143,138,129,168,187,198,87,81,75,44
移动总量:首先划分分成三段(155~129,129~198,198~44),然后计算,移动总量为(155-129)+(198-129)+(198-44)=249
(ii)SCAN
磁头移动顺序:
155,143,138,129,87,81,75,44,168,187,198
移动总量:只需要划分成两段(155~44,44~198),移动总量为(155-44)+(198-44)=265

八. P,V操作题(14分)
一个经典的IPC问题发生在牙科诊所.诊所里有3位牙医,3张诊椅和10把供等候就诊病人坐的椅子.如果没有病人,牙医们就坐在诊椅上聊天或休息.病人到来时,选择一名牙医为他治疗;如果牙医们都在看病人,他就坐下来等候;如果诊所病人已满,没有空椅子,他就离开.请编写牙医和病人的进程,要求正确实现该进程的同步互斥问题。
答:
semaphore seatNum=10; //表示可用的椅子数量
semaphore waitNum=0;  //表示等待看病的人数
semaphore freeNum=3;  //表示空闲的牙医数量
semaphore mutex=1; //用来对count保护
int count=0;

void Patient_i()
{
   P(mutex);
     if(count>=13)
     {
       V(mutex);
       return; //离开
     }
     else
     {
       count++;
       进入;
     }
        V(mutex);
        P(seatNum);//先占个椅子
        V(waitNum);
        P(freeNum);
        V(seatNum);
        被看病;
        P(mutex);
           count--;
        V(mutex);
        return;
}
void Dentist_i()
{
    while(true)
    {
              P(waitNum);
              看病;
              V(freeNum);
         }
}
yyzhfl 发表于 07-5-7 04:21:24 | 显示全部楼层
你知道吗?xx谢谢
li123zhou456 发表于 16-9-26 23:42:44 | 显示全部楼层
北大计算机系2007级数据结构考研提纲
您需要登录后才可以回帖 登录 | 注册

本版积分规则

联系我们|Free考研资料 ( 苏ICP备05011575号 )

GMT+8, 21-10-23 19:08 , Processed in 0.086433 second(s), 9 queries , Gzip On, Xcache On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表