计算机操作系统习题

第4章 作业

注：在标注“可选”的题目中至少选择2道题目。

1． 以Linux为例，列举出进程状态转换的典型原因和引起进程调度的因素。

2．说明下列活动是属于哪种制约关系？ （1）若干同学去图书馆借书； （2）两队进行篮球比赛；

（3）流水线生产中的各道工序；

（4）商品生产和社会消费。

3．有K个进程共享一个临界区，对于下述情况，请说明信号量的初值、含义，并用P、V操作写出有关的互斥算法。

（1）一次只允许一个进程进入临界区；

（2）一次允许m个进程进入临界区（m

4．（可选）假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记（进入时登记，离开时去掉登记项），而且每次只允许一人登记或去掉登记，问：

（1）应编写几个程序完成此项工作，程序的主要动作是些什么？应设置几个进程？进程与程序间的对应关系如何？

（2）用P，V操作写出这些进程的同步通信关系。

5．进程A1、A2、?、An1通过m个缓冲区向进程B1、B2、?、Bn2不断地发送消息，发送和接收工作遵循如下规则：

（1）每个发送进程每次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样。 （2）对每一个消息，B1、B2、?、Bn2都需要各接收一次，读到各自的数据区内。 （3）m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。 试用P、V操作组织正确的发送和接收操作。

6．爱睡觉的理发师问题[Dijkstra，1968]。一个理发店有两间相连的屋子。一间是私室，里面有一把理发椅，另一间是等候室，有一个滑动门和N把椅子。理发师忙的时候，通向私室的门被关闭，新来的顾客找一把空椅子坐下，如果椅子都被占用了，则顾客只好离去。如果没有顾客，则理发师在理发椅上睡觉，并打开通向私室的门。理发师睡觉时，顾客可以叫醒他理发。请编写理发师和顾客的程序，正确实现同步互斥问题。 7．（可选）在一间酒吧里有三个音乐爱好者，第一位音乐爱好者只有随身听，第二位只有音乐CD，第三位只有电池。而要听音乐就必须随身听、音乐CD和电池这三种物品俱全。酒吧老板一次出借这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出借这三种物品中的任意两种。于是第二名音乐爱好者得到这三种物品，并开始听乐曲。整个过程就这样进行下去。

试用P、V操作正确完成这一过程。

8．（可选）巴拿马运河建在太平洋和大西洋之间。由于太平洋和大西洋水面高度不同，有巨大落差，所以运河中修建有T（T>=2）级船闸，并且只能允许单向通行。船闸依次编号为1、2、……、T。由大西洋来的船需经由船闸T、T-1、……、2、1通过运河到太平洋；由太平洋来的船需经由船闸1、2、……、T-1，T通过运河到大西洋。 试用P、V操作正确解决大西洋和太平洋的船只通航问题。 9．（可选）某银行有人民币储蓄业务，由 n个柜员负责。每个顾客进入银行后先取一个号，并且等着叫号。当一个柜台人员空闲下来，就叫下一个号。试用P、V操作正确编写柜台人员和顾客进程的程序。

10．某系统如此定义P、V操作：

P（S）

S = S ?C 1；

若S＜0，本进程进入S信号量等待队列的末尾；否则，继续执行。

V（S）

S ＝ S ＋ 1；

若S≤0，释放等待队列中末尾的进程，否则继续运行。 （1）上面定义的P、V操作有什么问题？

（2）现有四个进程P1、P2、P3、P4竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面定义的P、V操作正确解决P1、P2、P3、P4对该互斥资源的使用问题。

11．试用P、V操作解决第二类读者写者问题。所谓第二类读者写者问题是指写者优先，条件为：

（1）多个读者可以同时进行读；

（2）写者必须互斥（只允许一个写者写，同时也不能读者、写者同时进行）；

（3）写者优先于读者（一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者）。

12．一家快餐店招有4种雇员：（1）开票者，获取顾客的订单；（2）厨师，准备饭菜；（3）包装员，把食品塞入袋中；（4）出纳，一手收钱一手交货。每位雇员可以看作一个进程。他们采用的是什么形式的进程间通信？

13．请用进程通信的方法解决生产者消费者问题。

14．对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T。一次进程切换需要的时间为S，这里S实际上就是开销。对于采用时间片长度为Q的时间片轮转法，请给出以下各种情况的CPU利用率的计算公式。

（1）Q=∞； （2）Q > T； （3）S < Q < T； （4）Q = S；

（5）Q趋近于0。

15．有5个批处理作业A到E几乎同时到达一计算中心。它们的估计运行时间分别为10、6、2、4和8分钟。其优先数（由外部设定）分别为3、5、2、1和4，其中5级为最高优先

级。对于下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的开销。

（1）时间片轮转法； （2）优先级调度；

（3）先来先服务（按照次序10、6、2、4、8运行）； （4）最短作业优先。

对（1），假设系统具有多道处理能力，每个作业均获得公平的CPU时间，对（2）到（4）假设任一时刻只有一个作业运行，直到结束。所有的作业都是CPU密集型作业。

16．有5个待运行的进程，它们的估计运行时间分别是9、6、3、5和X。采用哪种次序运行各进程将得到最短的平均响应时间（答案依赖于X）？

思考题（*）

1．多个程序在单CPU上并发运行和多个程序在多CPU上并行执行，这两者在本质上是否相同？为什么？在实现CPU调度算法时应考虑什么问题？ 2．假设A、B两个火车站之间是单轨线，许多列车可以同时到达A站，然后经A站到B站。又列车从A到B的行驶时间是t，列车到B站后的停留时间是t/2。试问在该问题模型中，什么是临界资源？什么是临界区？

3．在多个生产者、多个消费者和多个缓冲区问题的解决方案中，如果对调生产者（或消费者）进程中的两个P操作或两个V操作的次序，会发生什么情况？试说明之。

4．设有无穷多个信息，输入进程把信息逐个写入缓冲区，输出进程逐个地从缓冲区中取出信息。在下述两种情况下：缓冲区是环形的，最多可容纳n个信息；缓冲区是无穷大的。试分别回答下列问题：

（1）输入、输出两进程读、写缓冲区需要什么条件？

（2）用P、V操作写出输入、输出两进程的同步算法，并给出信号量含义及初值。 （3）指出信号量的值的变化范围和其值的含义。

5．进程间为什么要进行通信？在你编写自己的程序时，是否考虑到要和别的用户程序进行通信？各用户进程之间是否存在制约关系？

6．设计一种信箱通信机制，描述你的设计方案。

7．时间片是否只在分时系统的调度算法中使用？在Windows中怎样选择并改变时间片？

第5章 作业

1．用可变分区方式管理内存时，假定内存中按地址顺序依次有五个空闲区，空闲区的大小依次为32K、10K、5K、228K、100K。现有五个作业J1、J2、J3、J4和J5。它们各需内存1K、10K、108K、28K和115K。若采用最先适应分配算法能把这五个作业按J1～J5的次序全部装入内存吗？你认为按怎样的次序装入这五个作业可使内存空间利用率最高。 2．设在内存中按地址递增次序有三个不连续的空闲区F1、F2、F3，它们的容量分别是60K、130K、20K。请给出一个后备作业序列，使得实施存储分配时， （1）采用最佳适应算法将取得好的效果，而采用最差适应算法和首先适应算法效果都不好； （2）采用最佳适应算法效果不好，而采用最差适应算法和首先适应算法都可取得好的效果； （3）采用最差适应算法将取得好的效果，而采用首先适应算法和最佳适应算法效果都不好； （4）采用这三种算法都可取得好效果； （5）采用这三种算法效果都不好。

3．设计一个页表应考虑哪些因素？怎样解决页表很大的问题？

4．为什么要引入虚拟存储器？虚拟存储器是什么？它需要什么硬件支持？根据什么说一个计算机系统有虚拟存储器？怎样确定虚拟存储器的容量？

5．在虚拟页式存储管理中，进程在内外存中的存放有以下两种方法： （1）一部分页面放在内存，其余页面放在外存；

（2）一部分页面放在内存，全部页面放在外存。

试从系统开销的角度分析两种方法各自的优缺点，并说明页表的差别。

6．有一个虚拟存储系统。分配给某进程3页内存，开始时内存为空，页面访问序列如下： 6，5，4，3，2，1，5，4，3，6，5，4，3，2，1，6，5 （1）若采用先进先出页面置换算法(FIFO)，缺页次数为多少？ （2）若采用最近最少使用页面置换算法(LRU)，缺页次数为多少？ （3）若采用最佳页面置换算法呢？

7．有一个虚拟存储系统采用最近最少使用（LRU）页面置换算法，每个程序占3页内存，其中一页用来存放程序和变量i、j（不作他用）。每一页可存放150个整数变量。程序A和程序B如下： 程序A： var C: array[1..150,1..100] of integer; i,j:integer; for i:=1 to 150 do for j:=1 to 100 do C[i,j]:=0;

程序B： var C: array[1..150,1..100] of integer; i,j:integer; for j:=1 to 100 do for i:=1 to 150 do C[i,j]:=0; 设变量i、j放在程序页中，初始时，程序及变量i、j已在内存，其余两页为空。矩阵C按行序存放。

（1）试问当程序A和程序B执行完后，分别缺页多少次？ （2）最后留在内存中的各是矩阵C的哪一部分？

8．比较各种存储管理方式的特征（包括内存空间的分配方式、是否要有硬件的地址转换机构作支撑、适合单道或多道系统等）、重定位方式、地址转换的实现（操作系统和硬件怎样配合）、存储保护的实现（操作系统和硬件各自做些什么工作）。

思考题

1．可变分区管理方式下，采用移动技术有什么优点？移动一道作业时操作系统要做哪些工作？

2．了解Intel x86的地址转换机制。 3．64位计算机中页表的设计思路。

4．总结Windows请求页式存储管理功能解决问题的要点。

第6章 作业

1．有一个文件系统，根目录常驻内存，如图所示：

目录文件采用链接结构，规定一个目录下最多存放40个下级文件。下级文件可以是目录文件，也可以是普通文件。每个磁盘块可存放10个下级文件的描述信息，若下级文件为目录文件，则上级目录指向该目录文件的第一块，否则指向普通文件的文件控制块。（假设文件按自左向右的顺序建立。）

（1）普通文件采用UNIX的三级索引结构，即文件控制块中给出13个磁盘地址，前10个磁盘地址指出文件前10块的物理地址，第11个磁盘地址指向一级索引表，一级索引表给出256个磁盘地址，即指出该文件第11块至第266块的物理地址；第12个磁盘地址指向二级索引表，二级索引表中指出256个一级索引表的地址；第13个磁盘地址指向三级索引表，三级索引表中指出256个二级索引表的地址。该文件系统中的普通文件最大可有多少块？ 假设主索引表放在FCB中，若要读文件\\A\\D\\G\\I\\K中的某一块，最少要启动磁盘几次？ 最多要启动磁盘几次？若要减少启动磁盘的次数，可采用什么方法？

（2）普通文件采用链接结构，若要读\\A\\D\\G\\I\\K的第75块，最少启动硬盘几次，最多几次？ 2．在实现文件系统时，为加快文件目录的检索速度，可采用“文件控制块分解法”。 假设目录文件存放在磁盘上，每个盘块512 字节。文件控制块占64 字节，其中文件名占8字节，文件控制块分解后，第一部分占有10字节（包括文件名和文件内部号），第二部分占56字节（包括文件内部号和文件其他信息）。

（1）假设某一目录文件共有256个文件控制块，试分别给出采用分解法前和分解法后查找该目录文件的一个文件控制块的平均访盘次数。

（2）一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号部分，请给出访盘次数减少的条件。

3．在文件系统中，使用文件前要先打开文件，请写出“打开文件”系统调用的主要实现步骤，包括相关的数据结构。假设命令为fopen（文件名，打开方式）。

4．假设某文件由100个逻辑记录组成，每个逻辑记录长度为80个字符。磁盘空间被划分为若干块，块长度为2048个字符。为了充分利用磁盘空间，采用成组方式把该文件保存在磁盘上。

（1）请回答该文件占用多少个磁盘块？每个磁盘块上存放了多少个逻辑记录？

（2）若文件物理结构是链接结构，当用户要求处理第56个逻辑记录时，系统应为用户做哪

些工作？

5．假定磁带的记录密度为每英寸1000个字符，每一个逻辑记录长为180个字符，块与块之间的间隙为0.5英寸，现有800个逻辑记录需要存储到磁带上，请回答下列问题： （1）在没有采用成组操作时，磁带空间的利用率是多少？

（2）在采用以8个逻辑记录为一组的成组操作时，磁带空间的利用率是多少？

（3）为了使磁带空间的利用率大于70％，采用记录成组操作时的块因子至少应为多少？ 6．假设一个活动头磁盘有200道，编号从0-199。当前磁头正在143道上服务，并且刚刚完成了125道的请求。现有如下访盘请求序列(磁道号)：

86，147，91，177，94，150，102，175，130

试给出采用下列算法后磁头移动的顺序和移动总量（总磁道数）。 （1）最短寻道时间优先（SSTF）磁盘调度算法。

（2）扫描法（SCAN）磁盘调度算法（假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动）。

7．假设磁盘的移动臂现在第8号柱面上，有6个访盘请求在等待，如下所示。请给出最省时间的响应次序。

序号 柱面号 磁头号 扇区号 ① 9 6 3 ② 7 5 6 ③ 15 20 6 ④ 9 4 4 ⑤ 20 9 5 ⑥ 7 15 2

8．对下列每个问题，试说明它是由文件系统的哪个部分处理的？是如何处理的？ （1）存储碎片问题；

（2）允许给不同的文件以相同的文件名； （3）缓冲处理；

（4）扩充文件时存储空间的申请。

9．文件系统的性能对整体系统的性能影响很大，请总结在实现文件系统时可以从哪些方面提高文件系统的性能，简要给出这些手段的具体解决思路。 10．一些操作系统提供了RENAME系统调用给文件改名。试用基本文件操作（如建立文件、打开文件、读文件、写文件、关闭文件、删除文件等）设计出一种实现RENAME（A，B）系统调用的方案，其中A为原文件名，B为新文件名。

第7章 作业

1．画出从用户要求I/O操作开始，到I/O操作完成过程的流程图。 2．下列工作在四层I/O的哪一层上完成？

（1）对于读磁盘操作，计算磁道、扇区和磁头； （2）维护最近使用的块而设的超高速缓存； （3）向设备寄存器写命令；

（4）查看用户是否被允许使用设备；

（5）为了打印，把二进制整数转化为ASCII码。 3．在I/O系统中引入缓冲的主要原因是什么？

4．设备驱动程序的主要功能是什么？

第8章 作业

1．某系统有同类资源m个，供n个进程共享。如果每个进程至少申请一个资源，且所有进程对资源的最大需求量之和小于（m + n），证明该系统不会发生死锁。 2．某系统状态如下表所示：

已分配的资源 最大需求量

A B C A B C

P1 0 1 0 7 5 3 P2 2 0 0 3 2 2 P3 3 0 2 9 0 2 P4 2 1 1 2 2 2 P5 0 0 2 4 3 3 剩余资源 A B C 3 3 2

（1）此状态是否为安全状态，如果是, 则找出安全序列

（2）在此基础上，P2 申请（1，0，2）能否分配？为什么？ （3）P5 申请（3，3，0）能否分配？为什么？ （4）P1 申请（0，2，0）能否分配？为什么？

2． 化简如图所示的资源分配图，并说明系统是否处于死锁状态。

4．画出5个进程陷入死锁的所有非同构模型。

本文来源：https://www.bwwdw.com/article/og1g.html