J2周转时间=10:36-8:50=106 带权周转时间=106/30=3.53
J3周转时间=10:06-9.00=66 带权周转时间=66/6=11
J4周转时间=10:48-9:50=58 带权周转时间=58/12=4.83
平均周转时间=1.375小时 平均带权周转时间=5.09小时
华中科技大学2001操作系统硕士入学试题参考答案
一、填空题（10分）
1.批处理系统主要解决（吞吐量）问题，分时系统主要解决（交互性）问题。
2.程序并发执行失去了封闭性的原因是（运行程序的制约性）。
3.UNIX系统的核心结构由（ 进程控制 ）子系统和文件子系统两个部分组成的。
4.采用（静态分配资源）方法预防死锁时，可以破坏产生死锁的四个必要条件中的部分分配条件。
5．在请求分页系统中，引用位表示（该页最近被访问过），它的用途是（供页面淘汰时作参考）。
6．UNIX缓存管理中，对空闲缓冲区的使用体现了（LRU ）淘汰算法。
7．中断响应将保留处理机状态字和指令计数器的内容，这项工作是由计算机的（ 硬件 ）完成的。
8．为了实现进程由等待状态转换为就绪状态，操作系统应该提供（ 唤醒 ）原语。
二、选择填空题（16分）
1．在用户程序中，要将一个字符送到显示器上显示，要使用操作系统提供的（（1）系统调用）接口。
（1）系统调用 （2）原语 （3）函数 （4）子程序
2．打开文件操作的主要工作是（（1）把指定的文件的目录复制到内存指定的区域 ）。
（1）把指定的文件的目录复制到内存指定的区域
（2）把指定的文件复制到内存指定的区域
（3）在指定文件的存储介质上找到指定的文件
（4）在内存寻找指定的文件
3．订购机票系统处理来自各个终端的服务请求，处理后通过中断回答用户，所以它是一个（（4）实时信息处理系统 ）。
（1）分时系统 （2）多道批处理系统 （3）计算机网络
（4）实时信息处理系统
4．某系统采用基址、限长寄存器保护法实现存储保护，在这种方法中判断是否越界的判别式为（（3）0≤被访问的物理地址<限长寄存器的内容 ）。
（1）0≤被访问的物理地址<基址寄存器的内容
（2）0≤被访问的物理地址≤基址寄存器的内容
（3）0≤被访问的物理地址<限长寄存器的内容
（4）0≤被访问的物理地址≤限长寄存器的内容
5．以下属于临界资源的是(（3）私有数据 ）。
（1）磁盘 （2）共用队列结构 （3）私有数据 （4）可重入的程序代码
6．UNIX系统是一个交互式的分时系统。在进程状态变迁中，进程从运行态转变到就绪状态的原因是（（1）时间片到 ）。
（1）时间片到 （2）中断（或自陷）返回 （3）被抢占 （4）睡眠
7.分页系统中的页面是为（（2）操作系统所感知的 ）。
（1）用户所感知时 （2）操作系统所感知的
（3）编译系统所感知的 （4）连接装配程序所感知的
8．三个进程共事四个同类资源，这些资源的分配与释放只能一次一个。已知每个进程最多需要两个该类资源，则该系统（（4）必然无死锁 ）。
（1）有某进程永远得不到该类资源 （2）必然死锁
（3）进程请求该类资源立刻能得到 （4）必然无死锁
三、简答题（32分）
- 操作系统提供上锁原语，试问采取什么措施可以保证该原语操作在执行时不会被打断？（4分）
解：硬件设施有：swap、test&set、关中断等，软件设施可用信号量。
2.现有作业序列：作业1（提交时间8：00，运行时间2.00h）；作业2（提交时间8：30，运行时间3．00h）；作业3（提交时间9：00，运行时间0.10h）；作业4（提交时间9：30，运行时间0．50h）；时间单位为小时，以十进制计。使用FIFS和SJF调度算法处理该作业程序，问哪种作业调度算法性能更好（要求给出计算的数据和必要的步骤）。（8分）
解：FIFS 平均周转时间=3.675h 平均带权周转时间=12.9h
 |
SJF 平均周转时间=2.325h 平均带权周转时间=4.225h
- 设某系统的状态除了三个基本状态外，还增加了创建状态、完成状态和延迟状态。试画出该系统的进程状态变迁图，并表明状态变迁可能的原因。（8分）
解：
 |
- 什么是缓冲？举例说明利用双缓冲可以提高系统并行操作能力。（6分）
解：开辟用于匹配CPU和设备之间差异的内存储区称缓冲。在输入数据时，首先填满缓冲区1，操作系统可从缓冲区1把数据送到用户进程区，用户进程便可对数据进行加工计算；与此同时，输入设备填充缓冲区2。当缓冲区1空出后，输入设备再次向缓冲区1输入。操作系统又可以把缓冲区2的数据传送到用户进程区，用户进程开始加工缓冲2的数据。两个缓冲区交替使用，使CPU和I/O设备、设备和设备的并行性进一步提高。例如，采用双缓冲读卡并打印可以这样进行：第一张卡片读入缓冲区1，在打印缓冲区1数据的同时，又把第二张卡片读入缓冲区2。缓冲区1打印完时，缓冲区2也刚好输入完毕，让读卡机和打印机交换缓冲。这样输入和输出处于并行工作状态。
5.某文件系统采用索引文件结构，假设文件索引表的每个表目占用3B，存放一个磁盘块的块号（盘块大小为512B），试问该文件系统能管理的最大磁盘空间是多少B？（6分）
解：每个盘块可放512/3=170个盘块号，故最大磁盘空间是170×512B。
四、（12分）某系统采用动态分区存储管理技术，某时刻在内存中有三个空闲区，其首地址和大小分别是：空闲区1（100KB，10KB），空闲区2（200KB，20KB），空闲区3（300KB，15KB）。现有如下作业序列：作业1要求15KB，作业2要求16KB，作业3要求10KB。要求：
（1）画出该时刻内存分布图；（2）有首次适应算法和最佳适应算法，画出此时的自由内存队列结构；（3）哪些算法能将该作业序列装入内存（给出简要的分配过程）。
解：
J1要求15KB
J2要求16KB
J3要求10KB
(1)采用first fit
J1占用200KB开始的空闲区
J3占用100KB开始的空闲区
J2无法分配
(2)采用best
J1占用300KB开始的空闲区
J2占用200KB开始的空闲区
J3占用100KB开始的空闲区
五、假设，某分时系统采用树型目录结构。用户USERA目录的路径名是 /usr/hame/usera，用户USERB目录的路径名是/usr/hame/userb，用户USERA在其目录下创建了目录文件asdf和普通文件myc，并在asdf目录下创建了两个普通文件filel租file2；用户USERB在其目录下创建了目录文件asdf和普通文件lusrl，并在asdf目录下创建了两个普通文件filel和file2；其中，USERA的filel文件与USERB的filel文件是同一个文件。
1.画出上述文件系统的树型结构目录。（6分）
2.试分别写出用户USERA的filel文件的文件路径名和用户USERB的filel文件的文件路径名。（4分）
3.用户USERB 的目录文件asdf下的文件file2要改名为USERB的目录文件下的文件newfile，文件系统应该如何处理？（4分）
解：
1.
2. 路径名分别为：\usr\hame\usera\asdf\file1和\usr\hame\userb\asdf\file1。
3. 先从userb的目录文件查找，直到找到asdf。再在asdf中找file2，直到找到后把file2的目录项读入指定区，改名为newfile，再写回目录区。
六、有桥如图所示。车流如箭头所示。回答下列问题：
（1）假设该桥上每次只能有一辆车行驶，请用P，V操作实现交通管理以防桥上堵塞。（6分）
（2）桥上不允许车辆交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。请用P，V操作实现交通管理以防桥上堵塞。（10分）
解：(1)只要设一个互斥信号量mutex，初值为1。通过mutex的一方，汽车过桥，即一般临界区的解法。
(2)过桥问题，见解析题。
南京航空航天大学2001操作系统试题参考答案
一、名词术语解释（每小题3分，共24分）
(1)多道程序设计
(2)计算机操作系统
(3)用户态与核心态
(4)进程控制块PCB
(5)SPOOLing系统
(6)逻辑文件和物理文件
(7)进程映像
(8)临界资源和临界区
答：
- 多道程序设计 多个用户程序(作业)同时进入主存，并启动它们同时运行的程序设计技术。在单CPU上这些程序在宏观上是同时运行的，而微观上看它们交替执行。
(2)计算机操作系统 操作系统是管理系统资源、控制程序执行、改善人机界面、提供各种服务，合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的一种系统软件。
(3) 用户态与核心态 处理器的不同状态，大多数系统把处理器状态简单的划分为核心态（又称特权状态、系统模式、特态或管态）和用户态（又称目标状态、用户模式、常态或目态）。当处理器处于管理状态时，程序可以执行全部机器指令，访问所有资源，并具有改变处理器状态的能力；当处理器处于用户状态时，程序只能执行非特权指令。
(4)进程控制块 标识进程存在和记录、刻画进程状态及有关信息的数据结构。它是操作系统掌握进程的唯一资料结构，是操作系统控制和管理进程的主要依据。它包括了进程执行时的情况，以及进程让出处理器后所处的状态、断点等的标识信息、现埸信息和控制信息。
(5)SPOOLing、 是外围设备同时联机操作的简称假脱机系统。其思路是：利用多道程序设计技术，在运行用户作业的同时，将大批新的作业信息从输入设备上预先输入到辅助存储器磁盘的输入缓冲区域中暂时保存，称为“预输入”。此后，由作业调度程序调出作业执行。作业使用数据时不必再启动输入设备，而只要从磁盘的输入缓冲区域中读入。类似地，作业执行中不必直接启动输出设备输出数据，而只要将作业的输出数据暂时保存到磁盘的输出缓冲区域中，在作业执行完毕后，由操作系统组织信息成批输出。称为“缓输出”。这样能带耒缩短作业执行时间、增加多道程序道数、加强诈作业调度灵活性的优点。Spooling技术是用一类物理设备模拟另一类物理设备技术，是使独占使用的设备变成可共享设备的技术，也是一种速度匹配技术。
(6)逻辑文件和物理文件 逻辑文件—是从用户观点出发，从方便使用的角度考虑文件信息的组织及配置方式，这种文件叫逻辑文件，它分为流式文件和记录式文件。物理文件---从系统观点出发，考虑文件在物理介质上的组织和存放方式，这种文件叫物理文件，它分串连文件、连续文件、索引文件和哈希文件。
(7)进程映象 UNIX SVR4中，进程由三部分组成：proc结构、数据段和正文段，它们合称为进程映像，而把进程定义为映像的执行。
(8) 临界资源和临界区 进程中涉及共享变量的程序段称临界区。临界区中共享变量代表的资料称临界资料，通常它们被进程互斥使用。
二、填空（每小题2分，共10分）
1．在具有两级页表的分页存储管理系统中，CPU每次要存取一个数据时，须访问 （ 3 ）次内存。
2．产生死锁的必要条件是（ 共4个，互斥、占有并等待、不剥夺、循环等待 ）。
3．在一个请求分页存储管理系统中，某程序的页面走向为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。假设分得的页框数是3，并且开始时页框中是空的，则分别采用最佳转换算法和LRU页面转换算法，在访问过程中发生缺页中断的次数分别是（ 9 ）和（ 13 ）。
4．一台计算机有十台磁带机被m个进程竞争，每个进程最多需要三台磁带机，那么m为（ 4 ）时，系统没有死锁的危险。
5．磁盘请求以10，22，20，2，40，6，38柱面的次序到达磁盘驱动器。寻道时每个柱面移动需要6ms，则采用先到先服务算法的寻道时间为（ 876ms ）；采用电梯算法（起始移动方向向外）的寻道时间为（ 348ms ）。（假设磁头开始位置在柱面20）
三、回答下列问题（每小题7分，共42分）
- 何谓系统的安全状态，试说明银行家算法避免死锁的原理？
答：如果存在一个进程请求资源序列，能够使所有的进程得到所需的全部资源并最后终止，则称此时系统处于安全状态。
Dijkstra的银行家算法的原理是：对每一个进程的请求进行检查，这次资源申请是否会导致不安全状态。若安全则分配；否则拒绝分配。
- 在实现文件系统时把文件目录的目录项分解成两部分：索引节点和符号名目录项，有什么好处？（需用图示说明）
答：能减少检索文件访问的物理块数，提高文件系统检索文件控制块的效率。以UNIX为例，把文件目录项中的文件名和其他管理信息分开，后者单独组成定长的一个数据结构，称为索引节点（i-node），该索引节点的编号称索引号。于是，文件目录项中仅剩下14个字节的文件名和两个字节的i-no，因此，一个物理块可存放32个文件目录项，可大幅度减少访盘次数，加快文件检索速度。
 |
3.在存储管理中分页与分段的主要区别是什么？分页与分段两种方法中，哪个更易于实现共享，为什么？
答：分段是信息的逻辑单位，由源程序的逻辑结构所决定，用户可见，段长可根据用户需要来规定，段起始地址可以从任何主存地址开始。在分段方式中，源程序（段号，段内位移）经连结装配后仍保持二维(地址)结构。
分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见，页长由系统确定，页面只能以页大小的整倍数地址开始。在分页方式中，源程序（页号，页内位移）经连接装配后变成了一维(地址)结构。
实现分页共享较为困难，首先，要保证共享的程序或数据占有整数块(页面)，以便于和非共享信息分开。其次，进程实现程序共享时，由于页式存储结构要求逻辑地址空间是连续的，所以，程序运行前它们的页号是确定的。所有共享信息要事先规定统一的页号，当共享程序的作业数增多时，做到这一点是较困难的。相比较分段实现信息的共享和保护更容易些，因为，它采用二维(地址)结构，可方便地把共享程序或数据单独作为一段处理，共享段可作为每个进程单独的一段，可采用动态链接方式，也不必预先规定段号。
4.在设备管理中引入单缓冲，如果从磁盘把一块数据输入到缓冲区中花费的时间为B，把缓冲区中的数据输送到用户区，所花费的时间为M；CPU对数据进行处理的时间为C，则系统对每一块数据的处理时间是多少？要求写出由B，C，M组成的表达式，并说明其中的道理。
答：不采用缓冲，数据直接从磁盘到用户区，每批数据处理时间约为B+C，而采用单缓冲，每批数据处理时间约为max[C，B]+M，通常M远小于C或T，故速度快了很多。
5.提高磁盘I/O速度的方法有哪些？并分别加以简单的说明。
答：1)建立快速磁盘缓冲区(多缓冲)，以匹配CPU和盘速度差异。2)采用成组/分解技求，减少访盘次数，相当于提高磁盘I/O速度。3)采用盘上信息优化分布。4)使用提前读、延迟写技术。
6.程序顺序执行和并发执行分别有哪些特性？程序并发执行的条件是什么？对于下列语句，哪些能并发执行，哪些不能，说明理由。
S1：a=5-x； S2：b=a*x； S3：c=4*x； S4：d=b+c： S5：e=d+3；
答：程序顺序执行指在处理器上独占全部资源，按严格顺序执行指令的，程序执行的结果与它的执行速度无关，且初始环境一定时，执行结果可再现。程序并发执行指若干程序执行在时间上是重迭的，由于打破了封闭性和可再现性，并发执行中进程的执行具有间断性。
程序并发执行且与时间无关的一个充分条件是Bernstein条件。该条件为：程序在执行期间引用变量集与改变变量集交集之和为空集。由此可见：S1/S4，S1/S5，S2/S5，S3/S5能并发执行，其他均不能。
四、一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向），这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向，同一时刻可以有多只猴子通过。但是如果在相反的方向上同时有猴子通过则会发生死锁（这些猴子将被卡在绳索中间，假设这些猴子无法在绳索上从另一只猴子身上翻过去）。如果一只猴子想越过峡谷，它必须看当前是否有别的猴子在逆向通过。请使用信号量写一个避免死锁的程序来解决该问题。（14分）
解：与过独木桥问题一个类型。
var mutex,smutex,nmutex,smonkeycount,nmonkeycount:semaphore;
smonkeycount:=0 /*由南向北攀绳索的猴子数量;
nmonkeycount:=0 /*由北向高攀绳索的猴子数量;
smutex:=nmutex:=1; /*南/北方向猴子间互斥信号量
mutex:=1; /*绳索互斥信号量
cobegin
process southi (i=1,2,3,…)
begin
P(smutex);
if smonkeycount=0 then P(mutex);
smonkeycount :=smonkeycount+1;
V(smutex);
Cross the cordage;
P(smutex);
smonkeycount :=smonkeycount-1;
