发布时间 : 星期一 文章08~09第一学期操作系统期末考试论文更新完毕开始阅读
2009～2010第一学期操作系统期末论文
（1） 你认为操作系统下一步如何发展？
（2） CPU调度算法决定了被调度进程的执行次序。在单处理机上若有n个进程同时处于
就绪状态，那么对这n个进程有多少种不同的调度次序？请给出关于n的公式。
（3） 在支持批处理与分时的操作系统中，用户如何在终端上提交批处理作业和交互式作
业？
（4） 1981年，Peterson提出了一个解决两个进程临界段问题的算法。进程P和Q共享
如下变量。该算法能满足解决临界段问题的五条准则吗？
pturn,qturn:初值为false
Turn:枚举类型,初值任意 P:pturn=true;
turn=2;
while( qturn&&turn=2);
临界区
pturn=false；
Q: qturn=true;
turn=1;
while (pturn&&turn=1); 临界区
qturn=false;
该算法能满足解决临界段问题的五条准则吗？
（5） “理发师睡觉”问题：假设理发店由等待间（n个座位）和理发间（只有一个座位）
构成。无顾客时，理发师睡觉。当顾客进入理发店发现理发师在睡觉时，则叫醒理 发师。试写出模拟理发师和顾客的程序。
（6） “吸烟者”问题：假设一个系统有三个吸烟者（Smoker）进程和一个供货商（Agent）
进程。每个吸烟者连续不断地制造香烟并吸掉它。但是，制造一支香烟需要三种材料：烟、纸、火柴。一个吸烟者进程有纸，另一个有烟，第三个有火柴。供货商进程可以无限地提供这三种材料。供货商将两种材料一起放在桌上，持有另一种材料的吸烟者即可制造一支香烟并吸掉它。当此吸烟者抽香烟时，它发出一个信号通知供货商进程，供货商马上给出另外两种材料，如此循环往复。试编写一个程序使供货商与吸烟者同步执行。
（7） 设某系统没有死锁预防和死锁避免机构。该系统每月运行5000个作业，大约每一
个月发生两次死锁。当死锁出现时要求中止并重新启动大约10个作业。每个作业平均耗费6元钱，作业被中止时平均有一半的工作已被完成。
性能管理者已估算出，若装配一个死锁避免机构，将使每个作业的执行时间增
加10％，平均周转时间增加20％。由于系统当钱有30％的空闲时间，所以每月仍能运行完5000个作业。问：赞成装配死锁避免机构的理由是什么？反对装配死锁避免机构的理由又是什么？
（8） 在页式虚拟存储系统中，通常规定页表全部放在主存。但是若虚存空间很大，页面
又较小时，页表的体积非常打。若页表全部放入主存，空间消耗太大。在这种情况
下，通常把虚存空间分成系统虚拟空间和用户虚拟空间。映射系统虚拟空间的页表全部放入主存，而映射用户虚拟空间的页表页属于系统虚拟空间。因此用户页表页可能不在主存。
试给出这种情况下地址转换的过程。指出那些地方可能产生页故障。产生页故障后应该如何处理？哪些工作由硬件完成？哪些工作由软件完成？
（9） 对磁盘的请求并不总是服从均匀分布的，例如，存放文件目录的柱面总是比存放文
件本身的柱面更常被访问。假设已知50％的磁盘请求均是访问某固定柱面（编号较小的柱面）。 （1） 将使用何种磁盘调度算法？ （2） 能否设计一个满足这种情况的调度新算法？
（10） 什么时冗余廉价磁盘阵列（RAID）?它分为哪几级？每一级的主要特征是什么？ （11） 某些系统用保持一个副本的方法提供文件的共享，而另一些系统则保持多个副本，
即对每个共享用户均设置一个副本，试讨论两种方法的优缺点。
（12） 桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿
子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P.V原语实现爸爸、儿子、女儿三个并发进程的同步。
（13） 下述程序是解决两个进程互斥访问临界区问题的一种方法，试从“互斥”，“有空让
进”，“有限等待”等三个方面讨论它是否正确。 int c1=1; int c2=1; main()
{ p1(); /* 进程p1,p2并发执行 */ p2(); }
p1() /* 第一个进程p1 */ {
while (1)
{ other section 1: /* 其他部分 */ do
{ c1=1-c2;}while(c2= =0)；
critical section ; / * 临界区 */ c1=1; }
} }
p2() /* 第二个进程p2 */ {
while (1)
{ other section 2: /* 其他部分 */ do
{ c2=1-c1;}while(c2= =0)；
critical section ; / * 临界区 */ c2=1; }
} }
（14） Dekker提出了一个解决两个进程临界段问题的算法。进程P和Q共享如下变量。
该算法能满足解决临界段问题的五条准则吗？
pturn,qturn:初值为false
P进入临界区的条件:pturn ∧ not qturn Q进入临界区的条件:not Pturn ∧ qturn
Turn:枚举类型,初值任意
P:While (true)
{ pturn=true;
while( qturn) { if (turn==2) { pturn=false; while(turn==2); pturn=true; } }
临界区 turn=2; pturn=false;
}
Q: While (true)
{ qturn=true; while( pturn) { if (turn==2) { qturn=false; while(turn==1); qturn=true; } }
临界区 turn=1; qturn=false;
}
（15） （1） 写出P、V操作的定义。
（2） 有三个进程PA,PB,和PC合作解决文件打印问题：PA将文件记录从磁盘读
入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行
一次打印一个记录。缓冲区的大小等于一个记录大小。请用p.v操作来保证文件的正确打印。
（16） 设有8个程序prog1、prog2、…、prog8. 它们在并发系统中执行时有如图2.13所
示的制约关系，试用P、V操作实现这些程序间的同步。
prog1
prog3
Prog5 prog4 prog7 Prog8
prog2
prog6
（17） 在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段每次只允许一辆
自行车通过，但其中有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车已从两端进入小路情况下错车使用，如图所示。试设计P、V算法使来往的自行车均可顺利通过。
天津大学 T K S 南开大学
M L
（18） 有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登
记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，问：
(1) 为描述读者的动作，应编写几个程序，设置几个进程？ (2) 试用P.V操作描述读者进程之间的同步关系。
（19） 存储管理设计1
（a）使用C语言设计一个虚拟存储区和内存工作区，并用C编制LRU（最近最久未
使用调度算法）算法计算访问命中率。命中率＝（1－页面失效次数）/页地址流长度。 （b）设计指导