操作系统2006A答案.doc

操作系统2006A答案
参考答案

一、名词与术语解释：选择解释其中5个（20分）
多道程序技术：一种在计算机内同时运行两个或更多的程序的技术。多个程序共享系统资源，当某个程序的执行因某个事件而暂停执行时，处理器转向执行另一个程序。
并发：在同一时间段内发生的活动(进程和线程)。期间，这些活动可能共享相同的资源。 线程：进程中的一个执行线路，是可分配CPU的最小单位，包括进程上下文和线程自己的数据栈。
进程互斥：一种约束一组进程执行的条件，在任何时候，它们中只有一个进程可以访问某个资源或执行某一个特定功能。
信号量：一种受操作系统保护的数据结构，由一个整数域和指针域组成，并只能进行初始化、P操作和V操作，可以实现进程互斥和同步。
死锁：一组进程并发执行期间产生的一种僵局，其中每个进程占有一些资源并等待其中另些进程中占有的资源，且这些等待永远不会结束。
文件目录：文件系统中用于组织所有文件的控制信息的一种数据结构，可看作是文件控制块的集合。
二、简答题：选择回答其中5小题（30）
1、 简单比较分时系统与实时系统的区别。
所谓分时系统,就是在一台计算机上,连接多个终端,用户通过各自的终端和终端命令把作业送入计算机,计算机又通过终端向各用户报告其作业的运行情况,这种计算机能分时轮流地为各终端用户服务并能及时对用户服务请求予以响应,这就构成了分时系统。分时系统设计的主要目标是使用户能与系统交互作用,对用户的请求及时响应,并在可能的条件下尽量提高系统资源的利用率。
实时系统是为了能对特定输入做出及时响应,并在规定的时间内完成对该事件的处理而引入的。实时系统分为两大类: 实时控制系统和实时信息处理系统。
(1)实时控制系统: 在这类应用中要求计算机系统实时采集测量系统的数据,对被测量的数据及时进行加工处理及输出。它主要用于军事和生产过程中的自动控制领域。
(2)实时信息处理系统：在这类应用中要求计算机系统能对用户的服务请求及时作出回答,并能及时修改、处理系统中的数据。它主要用于像飞机票的预定、银行储蓄的财务管理等大量数据处理的实时系统中。 实时系统与分时系统的主要区别如下: ①系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很强的系统:而实时系统则大多数都是具有某种特殊用途的专用系统。
②响应时间的长短不同。分时系统的响应时间通常为秒级:而实时系统的响应时间通常为毫秒级甚至是微秒级。
③交互性的强弱不同。分时系统的交互性强,而实时系统的交互性相对较弱。 2、 简单描述进程上下文的作用和主要内容。
答： 进程上下文是操作系统控制和管理进程的内部数据，包括进程运行时相关的信息和操作使用的信息，如处理器寄存器的内容、进程优先级、消息和打开的文件信息等。 在多道程序的操作系统中，当一个执行中的进程转为阻塞时，该进程的处理器现场保存到上下文中；当一个就绪的进程转为执行之前，从该进程的上下文中获得处理器现场并恢复到处理器中，保证该进程正确地接着执行。
3、 操作系统创建一个新进程的主要步骤是什么？
答： 主要步骤包括：1分配一个空闲的PCB；2 分配进程的相关资源，并将相应的信息填写进PCB内 3 设置进程的状态为就绪，并将PCB插入到适当的就绪队列中。
4、 为什么说应用程序采用多线程的实现通常比多进程的实现的开销更低？
答： 主要原因包括：1在已有进程内新建一个线程的开销比新建一个进程的开销要小得多； 2 撤销一个线程的开销比撤销一个进程的开销要小得多； 3 CPU在线程之间调度时，线程的上下文切换设开销比进程的上下文切换设开销更小； 4 同一进程的线程同属一个地址空间内，线程之间的通信可以直接进行，不需要使用操作系统的复杂的通信机制。
5、 产生死锁的四个必要条件是什么？ 答： 四个必要条件包括：1互斥条件 2 占有且等待（部分分配）条件 3 非剥夺条件 4 循环等待条件。
6、 驻留集与工作集有什么区别和联系？
答： 驻留集是进程当前分配到物理页框中的所有页构成的集合，它受操作系统的页分配策略和内存可用状态的影响。
工作集是研究进程执行过程中访问页的规律的理论模型中的一个概念，是指进程在其过去的t个虚拟执行时间中访问的页的集合。程序局部性表现为在t>t0后，进程的工作集有一段相对长时间的稳定。工作集与进程的由程序逻辑和输入条件决定，与操作系统的分配策略和内存状态无关。
在虚拟分页管理中，工作集的变化规律客观上影响驻留集，为了提高内存管理效率，理想的页替换算法是总能选择不属于工作集的页替换出去，实际操作系统中，可以通过缺页率来调整进程的内存分配配额量。

7、 简述页式存储管理的基本原理。
答：在页式存储管理系统中,把每个作业的地址空间划分成大小相等的页,把内存的存储空间分成与页大小相同的物理块。存储分配以块为单位,一个作业的地址空间可以分配到内存不连续的物理块中。系统为每个作业建立一张页面变换表(简写为PMT,简称为页表),记录相应页在内存中对应的物理块号。页表(PMT)是用来完成逻辑地址到物理地址变换的一个重要数据结构。当进程访问逻辑地址时,地址变换机构自动地将逻辑地址分为页号和页内地址两部分,再以页号为索引去检索页表,得到该页的物理块号。把该物理块号与页内地址拼接便得到了物理地址。请求分页是指作业的所有页面并不一定都在实存,在作业运行过程中再请求调入所用的虚页。分页管理系统根据请求装入页面的方法,称为请求分页存储管理。
8、 抢占式和非抢占式调度有什么区别？
答：抢占式调度中，进程一次执行的CPU时间是由调度算法确定的，如时间片片轮转法中的一个时间片；非抡占式调度中，进程一次执行的CPU时间是由进程自身运行中的事件确定的，如进程提出I/O操作而转为阻塞。 三、应用分析题(7个题选5个)
1、 假设我们有一台多道程序的计算机，且每个作业具有相同的特征，即在一个计算周
期T内，作业前一半的时间花费在I/O上，后一半用于CPU上执行指令，且一个作业的I/O操作可与另一个作业的CPU操作完全并行。每个作业一共运行N个计算周期。有4个这样的作业同时进入系统中。用FIFO调度算法调度这批作业，给
出这批作业的推进时序图，并计算完成这批作业的总时间和CPU的利用率。（10分） 答：推进时序图（局部，完成了前两个计算周期）

完成四个作业的总计算周期数5N/2
CPU利用率2N÷5N/2=0.8
2、 有人提出了一种软件解决互斥问题的方法，其程序描述如下：
boolean blocked[2]; int turn;
void Process(int id) { while (true) {
blocked[id]=true; while (turn!=id) {
while (blocked[1-id])
/* do nothing */;
turn=id;
}
/* critical section */ blocked[id]=false; /* remainder */ } }
void main() {
blocked[0]=false; blocked[1]=false;
turn=0;
parbegin(Process(0), Process(1)); }
请举出一个反例，说明该方法是不正确的。 （10分）
3、 在一个虚拟页式系统中，有一个进程共有5个页：A、B、C、D和E，访问顺序如
下：A、B、C、D、A、B、E、A、B、C、D、E。假设置换算法为先进先出，该进程在主存有四个页帧，开始时未装入页，按这个访问顺序时，该进程何时发生页错
A A 缺页
误（即缺页中断）？发生多少次页错误？（10分） 答：发生页错误的时间见下表 B C D A B E A A B
A B C
A B C D
A B C D
A B C D
B C D E 缺页
C D E A 缺页
B D E A B 缺页
C E A B C 缺页
D A B C D 缺页
E B C D E 缺页
缺页 缺页 缺页
缺页10次，缺页率10/12

4、 假设磁头当前定位在磁道100处，且没着磁道号减少的方向移动。如果有下列磁盘
请求：27，129，110，186，147，41，10，64，120，给出在SCAN调度算法下，完成这批磁盘请求的顺序，并计算平均寻道长度。（10分）
答：顺序：64、41、27、10、110、120、129、186，总寻道数266，平均寻道长度：29.6
5、 某类UNIX的操作系统中，其文件系统也采用索引结点存贮文件的控制信息，但其
索引结点只有10个磁盘块地址域，其中前8个地址指向文件的最初8个数据块（数据块大小为1KB），第9个是一级索引指针，而第10个是二级索引指针。一个索引块可存贮256个磁盘块号。请计算这个操作系统中文件的最大字节数。如果有一个文件大小为456KB，请画出其索引结点和索引块中地址存贮示意图。（10分）
答：
最大文件：8KB+256KB+256×256KB=65800KB
文件大小为456KB其存贮示意图如下，二级索引块的第一块中有192个指针已使用，实线箭头表示已指向盘块。

6、 一个32位计算机有两个选择通道和一个多路通道，每个选择通道支持两个磁盘和
两个磁带部件，多路通道有两个行式打印机、两个卡片阅读机，并连接着10个VDT终端。假设有以下的传输率：
磁盘驱动器 800KB/s 磁带驱动器 200KB/s 行式打印机 6.6KB/s 卡片阅读机 1.2KB/s VDT 1KB/s 系统中的最大合计传输率为多少？（10分）
答：因为选择通道每次只能与上个外设联机，而多路通道则可同时让多个外设联机，因此系统最大合计传输率为
2×800kb/s＋2×6.6kb/s+2×1.2kb/s＋10×1kb/s=1625.6kb/s 7、 在一个单道批处理系统中,一组作业的提交时刻和运行时间如下表所示:
作业 1 2 3 4 提交时间 8：00 8：50 9：00 9：10 运行时间 1.0 0.50 0.20 0.10 试计算以下二种作业调度算法的平均周转时间T和和平均带权周转时间W: (1) 先来先服务；(2)短作业优先；
答案：
1.(1)采用先来先服务作业调度算法时,作业的运行情况如下表所示: 作业执行次序 1 2 3 4 提交时间 运行时间 开始时刻 完成时刻 周转时间 8：00 8：50 9：00 9：10 1.0 0.50 0.20 0.10 8：00 9：00 9：50 9：70 9：00 9：50 9：70 9：80 1.0 1.0 0.7 0.7 带权周转时间 1.0 2.0 3.5 7.0 所以,平均周转时间为:
T=(1.O+1.O+0.7+0.7)/4=0.85
平均带权周转时间为:
W=(1.O+2.O+3.5+7.O)/4=3.375
(2)采用短作业优先调度算法时,作业的运行情况如下表所示: 作业执行次序 1 3 4 2 提交时间 运行时间 开始时刻 完成时刻 周转时间 带权周转时间 8：00 9：50 9：10 8：50 1.0 0.20 0.10 0.50 8：00 9：00 9：20 9：30 9：00 9：20 9：30 9：80 1.0 0.2 0.2 1.3 1.0 1.0 2.0 2.6 所以,平均周转时间为:
T=(1.O+0.2+0.2+1.3)/4=0.675
平均带权周转时间为:
W=(1.0+1.O+2.O+2.6)/4=1.65
7 / 7