操作系统 答案

上进行登记（进入时登记，离开时去掉登记项），而且每次只允许一人登记或去掉登记，问： （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中的某一块，最少要启动磁盘几次？ 最多要启动磁盘几次？若要减少启动磁盘的次数，可采用什么方法？