六，操作系统问答题（共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     　 ８：00     　　　 ７0分钟        
JOB2      　８：20      　　　２0分钟        
JOB3      　８：４0     　　　４0分钟        
JOB4      　８：50      　　　３0分钟        
JOB5　　　９：００　　　　１０分钟

答：
作业名   　进输入井时间     运行时间　　　　开始时间    完成时间  周转时间(m)
job1　　　８：００　　　8:00-8:40　　　　8:00
　　　　　　　　　　　　10:20-10:50　　　10:20　　　10:50　　　１７０
job2　　　8:20　　　　　８：４０-9:00　　8:40　　　　９:０0　    　４０
job3　　　8:40　　　　　9:00-9:40　　　　9:０0　　　　9:４0　　　６０
job4　　　8:50　　　　　9:50-10:20　　　9:50　　　　10:20　　　　９０
job5　　　9:00　　　　　9:40-9:50　　　　9:４0　　　　9:50　　　　50　　　　

２．（６分）假设一个活动头磁盘有２００道，编号从０－１９９。当前磁头正在１５５道上服务，并且在此之前完成的是１７３道的访盘请求。现有如下访盘请求序列（磁盘号）：
７５，１６８，８１，１３８，８７，１４３，１８７，１２９，１９８，４４
试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数)。
（i）最短寻道时间优先（SSTF）磁盘调度算法。
（ii）扫描法（SCAN）磁盘调度算法（假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动。）
答：（i）SSTF
磁头移动顺序：
１５５，１４３，１３８，１２９，１６８，１８７，１９８，８７，８１，７５，４４
移动总量：首先划分分成三段（１５５～１２９，１２９～１９８，１９８～４４），然后计算，移动总量为（15５-1２９）+（1９８-１２９）+（1９８-４４）=2４９
（ii）SCAN
磁头移动顺序：
１５５，１４３，１３８，１２９，８７，８１，７５，４４，１６８，１８７，１９８
移动总量：只需要划分成两段（1５５～４４，４４～１９８），移动总量为（1５５-4４）+（1９８-４４）=２６５

八． P，V操作题（１４分）
一个经典的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);
        　}
}

我做了下,不知道对不对," 进输入井时间""进内存时间"我们不这么说,我把他理解为了"到达时间"和"开始时间"

  作业      到达时间    开始时间    运行时间    结束时间   总耗时
JOB1      8:00           8:00          70分钟      9:10         70分钟
JOB2      8:20           9:10          20分钟      9:30         70分钟
JOB5      9:00　        9:30          10分钟      9:40         40分钟
JOB4      8:50           9:40          30分钟      10:10       80分钟
JOB3　　8:40           10:10        40分钟      10:50       130分钟

这个好象是非抢占式的,抢占式的 ..

我的解题思路如下：
假设一次只允许两个作业进入内存；作业调度采用最高响应时间比调度算法，而进程调度可假设用最高优先级调度算法（作业运行时间短的，其优先级高），并且采用不可抢占式调度算法：

作业名  　开始时间    完成时间  周转时间(m)
JOB1      8：00        9：10       70
JOB2      9：20        9：40       80
JOB3     10：10       10：50     130
JOB4     9：40         10：10     80
JOB5　  9：10        9：20       20

（2）假如题目中有：假设一次只允许两个作业进入内存；作业调度采用最高响应时间比调度算法，而进程调度可假设用最高优先级调度算法（作业运行时间短的，其优先级高），并且采用不可抢占式调度算法
则你做的也是不对的。

按照你做的应该这样假设：
假设允许多个作业进入内存；作业调度采用最高响应时间比调度算法，而进程调度可假设用最高优先级调度算法（作业运行时间短的，其优先级高），并且采用不可抢占式调度算法。

以下是引用aison在2006-9-24 16:32:00的发言： 书上有道题 多道短作业优先的题中没有被抢占。 这道题为什么要被抢占？能解释下么？

还有就是最后一道PV操作  好象应该考虑到先来先看病  就是每个等待的椅子之间设个信号量
用个循环吧

觉得Supremgoooo关于调度时机的说法很有道理.否则这个题还真不好做.精辟精辟!!

:)

不过如果理解为不可抢占,似乎更好做,而且比抢占方式更加简单明了.

不过,今年应该不会继续考这个了.

必须先做到坐到座位上，才可以被理发师叫去理发？
哪怕只有一个顾客，也是必须先做座位上么？