操作系统典型例题分析

1操作系统引论

1、什么是操作系统，它的主要功能是什么？

关于操作系统，至今沿无严格的统一的定义，对操作系统的定义有各种说法，不同的说法反映了人们从不同的角度所揭示的操作系统的本质特征。

（1）从资源管理的角度，操作系统是控制和管理计算的软、硬件资源，合理地组织计算机的工作流程以及方便用户的程序集合。

（2）从硬件扩充的角度，操作系统是控制和管理计算机裸机之上的第一层软件，是对计算机硬件功能的一次扩充。

操作系统的主要功能有处理机管理、内存管理、设备管理文件管理等功能，以及用户接口。

2、什么是多道程序设计技术？多道程序设计技术的主要特点是什么？ 多道程序设计技术就是把多个程序同时放入内存，它们共享系统中的各种资源，并发地在处理机上运行。 特点如下：

（1）多道，即计算机内存中同时存入多道相互独立的程序。

（2）宏观上并行，是指同时进入系统的多道程序都处于运行过程中。

（3）微观上串行，是指在单处理机环境下，内存中的多道程序轮流地占有CPU，交替执行。

3、批处理系统是怎样的一种操作系统？它的特点是什么？

批处理系统是一种基本的操作系统类型。在该系统中，用户的作业（包括程序、数据及程序的处理步骤）被成批地输入到计算机中，然后在操作系统的控制下，用户的作业自动地执行。

批处理系统的特点是“成批”和“自动”。成批是指多个作业同时进入系统，其中一部分放在内存中，其余的入在外存的后备队列中，这样便于系统搭配合理的作业使之执行，从而充分发挥系统中各种资源的作用。自动是指作业一旦提交，用户就不能干预自己的作业。 4、什么是分时系统？什么是实时系统？试从交互性、及时性、独立性、多路性和可靠性几个方面比较分时系统和实时系统。

分时系统允许多个终端用户同时使用计算机，在这样的系统中，用户感觉不到其他用户的存在，好像独占计算机一样。

实时系统是指系统对特定输入做出的反应速度足以控制发出实时信号的对象。“实时”二字的含义是指在计算机对于外来信息能够及时处理，并在被控对象允许的范围内做出快速反应。

分时系统具有的多路性、独立性、及时性和交互性这四大特征，实时系统也同样具备，另外，实时系统对可靠性的要求比较高。下面从以下几方面对他们进行比较。

（1）多路性。实时信息重系统与分时系统一样具有多路性。操作系统按分时原则为多个终端用户提供服务。而对于实时控制系统，其多路性主要表现在经常对多咱的现声信息进行采集以及对多个对象或多个执行机构进行控制。

（2）独立性。不管是实时信息处理系统还是实时控制系统，与分时系统一样都具独立性。每个终端用户在向实时系统提出服务请求时，彼此独立地工作、互不干扰。

（3）及时性。实时信息处理系统对及时性要求与分时系统类似，都以人们能接受的等待时间来确定。而实时控制系统对及时性要求更高，是以控制对象所要求的开始截止时间或完成截止时间来确定，一般为秒级、几百毫秒级、毫秒级，有时甚至要求低于几百微秒。

（4）交互性。实时信息处理系统具有交互性，但人与系统的交互，仅限于访问系统中某些特定的专用服务程序。它不像分时系统那样向终端用户提供数据处理、资源共享等服务。实时控制系统的交互性要求系统具有连续的人机对话的能力，也就是说，在交互的过程中要对用户的输入有一定的记忆和进一步推断的能力。

（5）可靠性。分时系统虽然也要求具有可靠性，但相比之下，实时系统则要求系统高度可靠。因为任何的差错都可能造成巨大的经济损失，甚至产生无法预料的后果。因此，在实时系统中，都要采取多级容错措施，来保证系统的安全性及数据的安全性。

5、实时系统分为哪两种类型？

实时系统按使用方式的不同可分为两类：实时控制系统和实时信息处理系统。实时控制系统利用计算机对实时过程进行控制和提供监督环境。实时信息处理系统利用计算机对实时数据进行处理。

6、操作系统的主要特征是什么？

操作系统的主要特征是并发性、共享性、虚拟性和不确定性。并发性是指两个或两个以上的事物在同一时间间隔发生。共享性是指多道程序或任务对计算机资源的共同享用。虚拟性是指操作系统采用软件的手段将一个物理上的实体对应为多个逻辑上的对应物。不确定性是指操作系统是在一个不确定的环境中运行，人们不能对所运行程序的行为以及硬件设备的情况做出任何的假定，也无法确切地知道操作系统正处于什么样的状态。

7、操作系统与用户的接口有几种？它们各自用在什么场合？

操作系统与用户的接口分为命令接口和程序接口，命令接口提供一组命令供用户使用。命令接口用于用户操作级别。程序接口提供一组系统调用，供用户在程序中取得操作系统服务而设置。程序接口用于用户程序级别。

8、“操作系统是控制硬件的软件。”这一说法确切吗？为什么？ 这说法不确切。因为操作系统不仅控制和管理计算机的硬件资源，还要控制和管理计算机的软件资源，把操作系统定义为控制硬件的软件是片面的。

9、将下列左右两列词连接起来形成意义最恰当的对。

DOS 网络操作系统 OS/2 自由软件

UNIX 多任务 LINUX 单任务

WINDOWS NT 为开发操作系统而设计C语言

DOS 网络操作系统 OS/2 自由软件 UNIX 多任务

LINUX 单任务

WINDOWS NT 为开发操作系统而设计C语言

2 进程与线程

1、操作系统中为什么要引入进程的概念？为了实现并发进程之间的合作和协调，以及保证系统的安全，操作系统在进程管理方面要做哪些工作？

在多道程序的环境中，程序的并发执行代替了程序的顺序执行，并发执行的程序破

坏了程序的封闭性和可再现性，使得程序和它的执行不再一一对应。此外，程序的并发执行导致了资源的竞争和共享，这就造成并发执行的程序之间可能存在相互制约关系。因此并发执行的程序不再处于封闭的系统中，而出现了许多新的特征，如动态性、并发性、独立性及并发程序之间相互制约性待。程序这个静态的概念已经无法真实地反映并发执行的程序的特征，所以需要一个能够描述并发程序执行的过程的实体——进程。进程是一个数据集合上的执行过程。

操作系统在进程管理方面要做的主要工作有以下几方面：

（1）进程控制：设置一套机制来完成进程的创建、撤销以及进程状态的转化。 （2）进程同步：实现对系统中运行的所有进程之间的协调，包括进程互斥和进程同步。

（3）进程通信：在多道程序环境中，进程之间需要合作以共同完成一项任务，这些进程之间需要交换信息来协调各自的工作进度。所以系统必须具有进程之间通信的能力。

（4）进程调度：当处理机空闲时，按一定算法挑选一个进程，使其占有处理，投入运行。

2、试描述当前正在运行的进程状态改变时，操作系统进行进程切换的步骤？ 当正在执行的进程状态改变时，进程切换的步骤如下： （1）保存处理的状态到该进程的PCB中，包括各种寄存器的内容，如通用寄存器、指令计数器、程序状态字（PSW）寄存器及栈指针。

（2）对当明运行进程的PCB进行更新，包括改变进程的状态和其他相关信息。 （3）根据情况将该进程的PCB移入相应的队列（可能是就绪队列、阻塞队列及就绪挂起等）。

（4）进行进程调度，挑选一个进程。

（5）更新被选中进程的PCB，包括将其状态改为运行状态。

（6）根据被选择进程的PCB内容，得到被选进程对应程序的地址。

（7）恢复被选中进程的处理机状态。

3、现代操作系统一般都提供多任务的环境，度回答以下问题：（1）为运行多进程的并发执行，系统必须建立哪些关于进程的数据结构？（2）为支持进程的状态变迁，系统至少应提供哪些进程控制原语？（3）当进程的状态变迁时，相应的数据结构发生变化吗？

多任务环境即多道程序环境或多进程环境。

（1）为支持多进程的并发执行，系统必须建立的数据结构是PCB，不同状态进程的PCB用链表组织起来，开成就绪队列、阻塞队列等。

（2）为运行进程的状态变迁，系统至少提供的进程控制原语包括创建原语、撤销原语、阻塞原语和唤醒原语，当内存紧张时还应提供挂起原语和激话原语。

（3）当进程的状态变迁时，相应的数据结构发生变化，具体如下：

创建原语：建立进程的PCB，并将进程投入就绪队列。

撤销原语：删除进程的PCB，并将进程在其队列中摘除。

阻塞原语：将进程PCB中进程的状态从运行状态改为阻塞状态，并将进程投入到阻塞队列。

唤醒原语：将进程PCB中进程的状态从阻塞状态改为就绪状态，并将进程从阻塞队列摘下，投入到就绪队列中。

4、什么是进程控制块，从进程管理、中断处理、进程通信、文件管理、设备管理及存储管理的角度设计进程控制块应包含的内容。

进程控制块（PCB）是为了描述进程的动态变化而设置的一个与进程相联系的数据结构，用于记录系统管理进程所需信息。PCB是进程存在的唯一标识，操作系统通过PCB得知进程的存在。

为了进程管理，进程控制块的内容应包括以下几方面：（1）进程的描述信息，包括进程标识符、进程名等；（2）进程的当前状态；（3）当前队列链接指针；（4）进程的家族关系。

为了中断处理，进程控制块的内容应包括处理机状态信息和各种寄存器的内容，如通用寄存器、指令计数器、程序状态字（PSW）寄存器及栈指针等。

为了内存管理的需要，进程控制块的内容应包括程序在内存的地址及外存地址。

为了进程通信，进程控制块的内容应包括进程使用的信号量、消息队列指针等。 为了设备管理，进程控制块的内容应包括进程占有资源情况。

5、假设系统就绪队列中有10上进程，这10个进程轮换执行，每隔300ms轮换一次，CPU在进程切换时所花费的总时间是10ms，试问系统化在进程切换上的开销占系统整个时间的比例是多少？

就绪队列中有10个进程，这10个进程轮换执行，每个进程的运行时间是300ms，切换另一个进程所花费的总时间是10ms，因此系统化在进程切换上的时间开销占系统整个时间的比例是：10/（300+10）=3.2%

6、试述线程的特点及其与进程之间的关系。 线程是进程内的一个相对独立的运行单元，是操作系统调度和分派的单位。线程只拥有一点必不可少的资源（一组寄存器和栈），但可以和同属于一个进程的其他线程共享进程拥有的资源。

线程是进程的一部分，是进程内的一个实体；一个进程可以有多个线程，但至少必须有一个线程。

在多线程的操作系统中，线程是独立调度的分派的单位，进程是拥有资源的单位。 7、根据下图，回答以下问题。（1）进程发生状态变迁1、3、4、6、7的原因。（2）系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁，这种变迁称为因果变迁。下述变迁是否为因果变迁；3—>2、4—>5、7—>2、3—>6，试说明原因。（3）根据图说明该系统CPU调度的策略和效果。

时间片500ms 5 低优先级就绪 4 3 时间片100ms 2 创建 1 高优先级就绪 6 阻塞 7 运行 退出

（1）从图中可以看出，1表示新进程创建后，进入高优先级就绪队列；3表示进程因请求I/O或等待栽事件而阻塞；4表示进程运行的时间片到；6表示进程I/O完成或

等待的事件到达；7表示进程运行完毕而退出。

（2）从图中可看出，3—>2是因果变迁，当一个进程从运行态变为阻塞态时，此时CPU空闲，系统首先到高优先级队列中选择一个进程投入运行。

4—>5是因果变迁，当一个进程时间片到，从运行态变为就绪状态时，此时CPU空闲，系统首先到高优先级队列中选择进程，但如果高优先级队列为空，则从低优先级队列中选择一个进程投入运行。

7—>2是因果变迁，当一个进程运行完毕时，CPU空闲，系统首先到高优先级队列中选择一个进程投入运行。

3—>6不是因果变迁。一个进程阻塞是由于自身的原因而发生的，和另一个进程等待的事件到达没有因果关系。

（3）从图可以看出，当进程调度时，首先从高优先级就绪队列选择一个进程，赋予它的时间片为100ms。如果高优先级就绪队列为空，则从低优先级就绪队列选择进程，但赋予该进程的时间片为500ms。

这种策略一方面照顾了短进程，一个进程如果在100ms运行完毕它将退出系统，更主要的是照顾了I/O量大的进程，进程因I/O进入阻塞队列，当I/O完成后它就进入了高优先级就绪队列，在高优先级就绪队列等待的进程总是优先级就绪队列的进程。而对于计算机量较大的进程，它的计算机如果在一个100ms的时间片内不能完成，它将进入低优先级就绪队列，在这个队列的进程被选中的机会要少，只有当高优先级就绪队列为空，才从低优先级就绪队列选择进程，但对于计算量大的进程，系统给予的适当照顾是时间片增大为500ms。

8、回答以下问题。（1）若系统中没有运行进程，是否一定没有就绪进程？为什么？（2）若系统中既没有运行进程，也没有就绪进程，系统中是否就没有阻塞进程？请解释。（3）如果系统采用优先级调度策略，运行的进程是否一定是系统中优先级最高的进程。

（1）是。若系统中没有运行进程，系统会马上选择一个就绪进程队列中的进程投入运行。只有在就绪队列为空时，CPU才会空闲。

（2）不一定，当系统中所有进程分别等待各自希望发生的事件时，它们都处于阻塞状态，此时系统中既没有运行进程，也没有就绪进程。这种情况出现时，如果各个进程没有相互等待关系，只要等待的事件发生了，进程就会从等待状态转化为就绪状态。但如果处于阻塞状态的进程相互等待彼此占有的资源，系统就可能发生死锁。 （3）不一定。因为高优先级的进程有可能处于等待状态，进程调度程序只能从就绪队列中挑选一个进程投入运行。被选中进程的优先级在就绪队列中是最高的，但在整个系统中它不一定是最高的，等待队列中进程的优先级有可能高于就绪队列中所有进程的优先级。

9、假如有以下程序段，回答下面问题。S1： a=3-x；S2： b=2*a；S3： c=5+a；（1）并发程序执行的Bernstein条件是什么？（2）试画图表示它们执行时的先后次序。（3）利用Bernstain条件证明，S1、S2和S3哪两个可以并发执行，哪两个不能。

（1）Bernstain提出的程序并发执行的条件如下：

R（Pi）={a1,a2,……am}表示程序Pi在执行期间所要参考的所有变量的集合，称为“读集”；W（Pi）={b1,b2,……bn}表示程序Pi在执行期间要改变的所有变量的集合，称为“写集”。两个程序P1和P2并发执行的条件是，当且仅当 R（P1）?W（P2）?R（P2）?W（P1）?W（P1）?W（P2）＝{}

（2）三个程序段对应的三个进程的先后执行次序是，S1先于S2和S3运行，如下图所示。

S2 S1 S3

（3） R（S1）＝{x}，W（S1）＝{a} R（S2）＝{a}，W（S2）＝{b}

R（S3）＝{a}，W（S3）＝{c}

所以W（S1）?R（S2）＝{a}，因此S1和S2不能并发执行。W（S1）?R（S3）={a}，因此S1和S3也不能并发执行。而

R（S2）?W（S3）?R（S3）?W（S2）?W（S2）?W（S3）＝{}，因此S2

和S3可以并发执行。

3 进程同步与通信

1、以下进程之间存在相互制约关系吗？若存在，是什么制约关系？为什么？（1）几个同学去图书馆借同一本书；（2）篮球比赛中两队同学争抢篮板球；（3）果汁流水线生产中捣碎、消毒、灌装、装箱等各道工序；（4）商品的入库和出库；（5）工人做工与农民种粮。

进程之间的相互制约分为互斥关系和同步关系。互斥关系是多个进程之间竞争临界资源，而禁止两个以上的进程同时进入临界区所发生的制约关系。同步关系是合作进程之间协调彼此的工作，而控制自己的执行速度，由此产生的相互合作、相互等待的制约关系。

（1）几个同学去图书馆借同一本书。存在互斥关系。因为一本书只能借给一个同学。

（2）篮球比赛中两队同学争抢篮板球。存在互斥关系。因为篮球只有一个，两队只能有一个队抢到篮球。

（3）果汁流水线生产中捣碎、消毒、灌装、装箱等各道工序。存在同步关系，因为后一道工序的开始依赖于前一道工序的完成。

（4）商品的入库和出库。存在同步关系，因为商品若没有入库就无法出库，若商品没有出库，装满了库房，也就无法再入库。

（5）工人做工与农民种粮。工人和农民之间没有相互制约关系。 2、说明P、V操作为什么要设计成原语？

用信号量S表示共享资源，其初值为1表示有一个资源。设有两个进程申请该资源，若其中一个进程先执行P操作。P操作中的减1操作由3条机器指令组成：取S送寄存器R；R-1送R；R送S。若P操作不用原语实现，在执行了前述三条指令中的2条，即还未执行R送S时（此时S的值仍为1），进程被剥夺CPU，另一个进程执行也要执行P操作，执行后S的值为0，导致信号量的值错误。正确的结果是两个进程执行

完P操作后，信号量的值为-1，进程阻塞。

V操作也同样。所以要把信号量的P、V操作设计成原语，要求该操作中的所有指令要么都做，要么都不做。

3、设有一个售票大厅，可容纳200人购票。如果厅内不足200人，则允许进入，超过则在厅外等候；售票员某时只能给一个购票者服务，购票者买完票后就离开。试问：（1）购票者之间是同步关系还是互斥关系？（2）用P、V操作描述购票者的工作过程。

购票者之间是互斥关系。

P、V操作描述购票者的工作过程如下： semaphore empty=2000; semaphore mutex=1; void buyer() { P(empty); P(mutex); 购票;

V(mutex);

V(empty); }

售票大厅可容纳200人购票，说明最多允许200人共享售票大厅。引入一个信号量empty，初值为200；由于购票者必须互斥地购票，故再设置一个信号量mutex，初值为1。

4、分析生产者和消费者问题中多个P操作颠倒引起的后果。

答：如果将生产进程的两个P操作，即P（empty）和P（mutex）的位置互换，生产者和消费者问题描述如下：

semaphore mutex=1; semaphore empty=n; semaphore full=0;

int i,j;

ITEM buffer[n], data_p, data_c;

void producer() /*生产者进程*/ { while(true)

{ produce an item in data_p; P（empty） P（empty）

buffer[i] = data_p;

i=(i+1)%n; V（nutex）; V（full）; }

}

void consumer() /*消费者进程*/ { while(true) { P（full） P（mutex）

data_c = buffer[j];

j=(j+1)%n; V（nutex）; V（empty）;

consume the item in data_c; }

}

按上面的描述，当生产者进程生产了n个产品而使缓冲区满时，生产者如若继续执行，可能顺利通过P（mutex）。但当执行P（empty）时，由于缓冲区已满，生产者将在信号量empty上等待。若之后消费者欲取产品，执行P（full）顺利通过，但当执行P（mutex）时，由于生产者获得了进入临界区的权力，消费者只能在mutex上等待。此时生产者在empty上等待，消费者在mutex上等待，从而导致生产者等待消费者取走产品，消费者等待生产者释放缓冲区，这种相互等待就造成系统死锁。

4 调度与死锁

1、某进程被唤醒后立即投入运行，能说明系统采用的是可剥夺调度算法吗？ 不能。如果当前就绪队列为空，被样被唤醒的进程就是就绪队列中唯一的一个进程，于是调试程序自然选中它投入运行。

2、在哲学家进餐问题中，如果将先拿起左边筷子的哲学家称为左撇子，将先拿起右边筷子的哲学家称为右撇子。请说明在同时存在左、右撇子的情况下，任何的就座安排都不能产生死锁。

该题的关键是证明该情况不满足产生的四个必要条件之一。在死锁的四个必要条件中，本题对于互斥条件、请求与保持条件、不可剥夺条件肯定是成立的，因此必须证明环路条件不成立。

对于本题，如果存在环路条件必须是左、右的哲学家都拿起了左（或右）边的筷子，而等待右（或左）边的筷子，而这种情况只能出现在所有哲学家都是左（或右）撇子的情况下，但由于本题有右（或左）撇子存在，因此不可能出现循环等待链，所以不可能产生死锁。

3、系统中有5个资源被4个进程所共享，如果每个进程最多需要两个资源，试问系统是否会产生死锁？

由于资源数大于进程数，所以系统中总会有一个进程获得的资源数大于等于2,该进程已经满足了它的最大需求，当它运行完毕后会把它占有的资源归还给系统，此时其余3个进程也能满足最大需求而顺利运行完毕。因此系统不会产生死锁。

4、计算机系统中有8台磁带机，由N个进程竞争使用，每个进程最多需要3台。问当N为多少时，系统没有死锁的危险？

当N<4时，系统没有死锁的危险。因为当N为1时，它最多需要3台磁带机，系统中共有8台，其资源数已足够1个进程使用，因此绝对不会产生死锁；当N为2时，两个进程最多需要6台磁带机，系统中共有8台，其资源数也足够两个进程使用，因此也不会产生死锁；当N为3时，无论如何分配，3个进程中必有进程得到3台磁带机，

该进程已经达到它的最大需求，当它运行完毕后可释放这3台磁带机，这就保证了其他两个进程也可顺利执行完毕。因此当N<4时，系统没有死锁的危险。

当N＝4时，假设4个进程都得到两个资源，此时系统中已没有剩余资源，而4个进程都没有到达它们的最大需求，所以系统有可能产生死锁。同理，当N>4时，也有产生死锁的危险。

5、设系统中有5个进程P1、P2、P3、P4和P5，有三种类型的资源A、B和C，其中A资源的数量是17，B资源的数量是5，C资源的数量是20，T0时刻系统状态如下表。回答以下问题：（1）计算每个进程还可能需要的资源，并填入表的“仍需要资源数”栏目中。（2）T0时刻系统是否处于安全状态？为什么？（3）如果T0时刻进程P2又有新的资源请求（0,3,4），是否实施资源分配？为什么？（4）如果T0时刻进程P4又有新的资源请求（2,0,1），是否实施资源分配？为什么？（5）在第（4）题的基础上，若进程P1又有新的资源请求（0,2,0），是否实施资源分配？为什么？ 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A B C

（1）5个进程P1、P2、P3、P4和P5仍然需要A、B和C，三类资源数量如下表： 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A 3 1 0 2 1 B 4 3 0 2 1 C 7 4 6 1 0 （2）由已知条件，系统中A、B和C，三类资源的总数是（17,5,20），从表中可以计算出已分配情况是（15,2,17），剩余可用资源的数量是（2,3,3），如果先让进程P5执行，可以满足它的最大需求。当进程P5运行完毕，又可释放它占有的资源，使系统中可用资源的数量增加为（5,4,7）；此时可让P4执行，满足它的最大需求后又可释放它占有的资源，使系统中可用资源的数量增加为（7,4,11）；然后让P3执行，满足它的最大需求后又可释放它占有的资源，使系统中可用资源的数量增加为（11,4,16）；之后可让P2和P1执行。这样所有进程都可运行完毕，系统是在T0时刻存在安全序列{P5,P4,P3,P2,P1}，所以系统是安全的。

（3）如果T0时刻进程P2又有新的资源请求（0,3,4），进程P2请求资源数（C资源只剩下3个，而进程P2请求4个）大于剩余可用资源的数据（2,3,3），所以不能分配。

（4）如果T0时刻进程P4又有新的资源请求（2,0,1），按银行家算法进行检查，进程P4请求资源数（2,0,1）+已分配资源数量（2,0,4）小于进程P4的最大需求数量（4,2,5）；另外进程P4请求资源数（2,0,1）小于剩余可用资源的数量（2,3,3）；如果满足进程P4新的资源请求，进程P4新仍然需求资源数变为（0,2,0），如下表所示。 进程 已分配资源数量 最大资源需求量 仍然需求资源数 A P1 P2 P3 P4 2 4 4 4 B 1 0 0 0 C 2 2 5 5 A 5 5 4 4 B 5 3 0 2 C 9 6 11 5 A 3 1 0 0 B 4 3 0 2 C 7 4 6 0 P5 3 1 4 4 2 4 1 1 0 系统中剩余可用资源的数量为（0,3,2）；用安全算法进行检查可以得到安全序列{P4,P5,P3,P2,P1}，所以系统是安全的，可以满足进程P4的资源请求。

（5）在第（4）题的基础上，若进程P1又有新的资源请求（0,2,0），按银行家算法进行检查，进程P1请求资源数（0,2,0）+已分配资源数量（2,1,2）小于进程P4的最大需求数量（5,5,9）；另外进程P1请求资源数（0,2,0）小于剩余可用资源的数量（0,3,2）；如果满足进程P1新的资源请求，进程P1新仍然需求资源数变为（3,2,7），如表所示。 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A 3 1 0 0 1 B 2 3 0 2 1 C 7 4 6 0 0 系统中剩余可用资源的数量为（0,1,2），已不能满足任何进程的资源需要，故系统进入不安全状态，此时不能将资源分配给进程P1。

5 存储管理

1、存储管理的基本任务是为多道程序的并发执行提供良好的存储器环境，这包括哪些方面？

存储管理的基本任务是为多道程序的并发执行提供良好的存储器环境，它包括以下几个方面：（1）能让每道程序“各得其所”，并在不受干扰的环境中运行时，还可以使用户从存储空间的分配、保护等事物中解脱出来；（2）向用户提供更大的存储空间，使更多的程序同时投入运行或使更大的程序能在小的内存中运行。（3）为用户对信息的访问、保护、共享以及程序的动态链接、动态增长提供方便；（4）能使存储器有较高的利用率。

2、页式存储管理系统是否产生碎片？如何应对此现象？ 页式存储管理系统产生的碎片称为内碎片，它是指一个进程的最后一页没有占满一个存储块而被浪费的存储空间。减少内碎片的办法是减小页的大小。

3、在页式存储管理系统中页表的功能是什么？当系统的地址空间很大时会给页表的设计带来哪些新问题？

页式存储管理系统中，允许将进程的每一页离散地存储在内存的任何一个物理页面上，为保证进程的正常运行，系统建立了页表，记录了进程每一页被分配在内存的物理块号。页表的功能是实现从页号到物理块号的地址映射。

当系统的地址空间很大时，页表也会变得非常大，它将占有相当大的内存空间。例如，对于一个32位地址空间的页式系统，假设页的大小为4KB，则一个进程的页表项最大可达到1MB。如果每个页表项占4B，则页表要占用4MB的连续内存空间。为了解决这个问题可以从以下两个方面入手。（1）将页表离散存放。（2）只将页表的一部分

调入内存，其余部分放在外存。

具体的实现方案是采用两级页表。对页表分页，使每个页面的大小与内存的物理块的大小一致。并为它们进行编号，将各个页面放在不同的物理块中。然后为这些离散分配的页表再建立一张页表，称为外层页表（或页目录），此时的逻辑地址可描述为：

外层页号+页号+页内位移 对于要运行的进程，将其外层页表调入内存，对所有的页表而言只需调入少量的页表，使用时如果找不到相应的页表，则产生中断，请求操作系统将需要的页表调入内存。 两级页表适应了大地址空间的需要，需要虚拟存储技术的支持，增加了地址变换的开销和管理的复杂度。此外根据需要还可以设计三级页表、四级页表等。

4、什么是动态链接？用哪种存储管理方案可以实现动态链接？

动态链接是指进程在运行时，只将进程对应的主程序段装入内存，在主程序运行过程中，当需要用到哪个子程序段和数据段时，再将这些段装入内存，并与主程序段链接上。

通常一个大的程序是由一个主程序和若干个以及一些数据段组成的。而段式存储管理方案中的段就是按用户的逻辑段自然形成的，因此可实现动态链接。

5、某进程的大小为25F3H字节，被分配到内在的3A6BH字节开始的地址。（1）若使用上、下界寄存器，寄存器的值是多少？如何进程存储保护？（2）若使用地址、限长寄存器，寄存器的值是多少？如何进程存储保护？

（1）若使用下、下界寄存器，上界寄存器的值是3A6BH，下界寄存器的值是3A6BH+25F3H=605EH，当访问内在的地址大于605EH、小于3A6BH时产生越界中断。

（2）若使用地址、限长寄存器，地址寄存器值是3A6BH，限长寄存器的值是25F3H，当访问内存的地址小于3A6BH，超过3A6BH+25F3H=605EH时主生越界中断。

6、在系统中采用可变分区存储管理，操作系统占用低地址部分的126KB，用户区的大小是386KB，若采用空闲分区表管理空闲分区。若分配时从高地址开始，对于下述的作业申请序列：作业1申请80KB；作业2申请56KB；作业3申请120KB；作业1完成；作业3完成；作业4申请156KB；作业5申请80KB。试用首次适应法处理上述作业，并回答下面问题。（1）画出作业1、2、3进入内存后。内存分布情况。（2）画出作业1、3完成后。内存的分布情况。（3）画出作业4、5进入内存后。内存分布的情况。

（1）作业1、2、3进入内存后，内存分布如下图

0KB 操作系统126KB 126KB 256KB 作业3:120KB 376KB 作业2:56KB 432KB 作业1:80KB 512-1KB （2）作业1、3完成后，内存的分布情况如下图

0KB 操作系统126KB 126KB

256KB 376KB 作业2:56KB 432KB 512-1KB

（3）作业4、5进入内存后，内存的分布情况如下图

0KB 操作系统126KB 126KB 256KB 作业4:156KB 376KB 作业2:56KB 432KB 作业5:80KB

7、某系统采用页式存储管理策略，某进程的逻辑地址空间为32页，页的大小为2KB，物理地址空间的大小是4MB。（1）写出逻辑地址的格式。（2）该进程的页表有多少项？每项至少占多少位？（3）如果物理地址空间减少一半，页表的结构有何变化？

（1）进程的逻辑地址空间为32页，故逻辑地址中的页号需要5位（二进制），由于每页的大小为2KB，因此页内位移须用11位（二进制）表示，这样逻辑地址格式如下图。

15

11 10

页号 页内位移

（2）因为进程的逻辑地址空间为32页，因此该进程的页表项有32项。页表中应存储每页的块号。因为物理地址空间的大小是4MB，4MB的物理地址空间内分成4MB/2KB=2K个块，因此块号部分需要11位（二进制），所以页表中每项占11位。

（3）如果物理地址空间减少一半，页表的页表项数不变，但每一项的长度从11位（二进制）减少到10位（二进制）。 8、某页式存储管理系统，内存的大小为64KB，被分成16块，块号为0、1、2、…、15。设某进程有4页，其页号为0、1、2、3，被分别装入内存的2、4、7、5块，问：（1）该进程的大小是多少字节？（2）写出该进程每一页在内存的起始地址。（3）逻辑地址4146对应的物理地址是多少？

（1）内存的大小为64KB，被分成16块，所以块的大小是64KB/16=4KB。因为块的大小与页面的大小相等，所以页的大小是4KB。该进程的大小是4*￥KB。

（2）因为进程页号为0、1、2、3，被分别装入内存的2、4、7、5。 第0页在内存的起始地址是：2*4KB=8KB； 第1页在内存的起始地址是：4*4KB=16KB； 第2页在内存的起始地址是：7*4KB=28KB； 第3页在内存的起始地址是：5*4KB=20KB。

（3）逻辑地址4146对应的物理地址：4146/4096=1，…，50。逻辑地址4146对应的页号为1，页内位移为50。查找页表，得知页号为1的存储块号为4，所以逻辑地址4146对应的物理地址是：4*4096+50=16434。

0

512-1KB 9、某段式存储管理系统的段表如下图，请将逻辑地址[0，137]、[1，9000]、[2，3600]、[3，230]转换成物理地址。 段号 0 1 段大小 15 KB 8 KB 段起址 40KB 80 KB 2 10 KB 100 KB （1）对于逻辑地址[0，137]，段号为0，段内位移为137。查段表的项得到该段的段地址为40KB，段长为15KB。由于段号0小于进程的总段数，故段号合法；段内位移137小于段长15KB，故段内地址合法。因此可得到物理地址为：40KB+137B=40960B+137B=41097B。

（2）对于逻辑地址[1，9000]，段号为1，段内位移为9000。查段表的项得到该段的段地址为80KB，段长为8KB。由于段号1小于进程的总段数，故段号合法；段内位移9000大于段长8KB=8192B，因此产生越界中断。

（3）对于逻辑地址[2，3600]，段号为2，段内位移为3600。查段表的项得到该段的段地址为100KB，段长为10KB。由于段号2小于进程的总段数，故段号合法；段内位移3600小于段长10KB，故段内地址合法。因此可得到物理地址为：100KB+3600B=10240B+3600B=10600B。

（4）对于逻辑地址[3，230]，段号为3，段内位移为230。由于段号3大于进程的总段数，故段号不合法，因此产生越界中断。

6 虚拟存储管理

1、试说明缺页中断与一般中断的主要区别？

答：缺页中断与一般中断一样，需要经历保护CPU现场、分析中断原因、转中断处理程序进行处理及恢复中断现场等步骤。但缺页中断是一种特殊的中断，它与一般中断的区别如下：

（1）在指令执行期间产生和处理中断。通常CPU是在一条指令执行之后去检查是否有中断产生，若有便去处理中断；否则继续执行下一条指令。页缺页中断是在指令执行期间发现所要访问的指令或数据不在内存时产生和处理中断。

（2）一条指令执行期间可以产生多次中断。对于一条要求读取多个字节数据的指令，指令中的数据可能跨越两个页面。该指令执行时可以要发生3次中断，一次是访问指令，另外两次访问数据。

2、局部置换和全局置换有何区别，在多道程序系统中建议使用哪一种？

答：局部置换是指当进程在执行过程中发生缺页时，只在分配给该进程的物理块中选择一页换出。全局置换是指在所有用户使用的整个存储空间中选择一个页面换出。

在多道程序系统中建议使用局部置换策略。这样，即使某个进程出现了抖动现象，也不致引起其他进程产生抖动，从而将抖动局限在较小范围内。

3、存储存储器的特征是什么？虚拟存储器的容量受到哪两个方面的限制？ 答：虚拟存储器的特征有以下几方面。（1）离散性，指进程不必装入连续的内存空间，而是“见缝插针”。（2）多次性，指一个进程的程序和数据要分多次调入内存。（3）对换性，指进程在运行过程中，允许将部分程序和数据换进、换出。（4）虚拟性，指能从逻辑上扩充内存容量。

虚拟存储器的容量主要受计算机的地址长度和外存容量的限制。

4、已知页面走向是1、2、1、3、1、2、4、2、1、3、4，且进程开始执行时，内存中没有页面，若该进程分配两个物理块，当采用以下算法时的缺页率是多少？（2）先进先出置换算法。（2）假如有一种页面置换算法，它总是淘汰刚使用过的页面。

答：（1）根据题中页面走向，采用先进先出置换算法时的页面调度情况如下表 页面走向 物理块1 物理块2 缺页 1 1 缺 2 1 2 缺 1 3 3 2 缺 1 3 1 缺 2 2 1 缺 4 2 4 缺 2 1 1 4 缺 3 1 3 缺 4 4 3 缺 从表中可看出，页面引用11次，缺页9次，所以缺页率为9/11=81.8%。 （2）根据题中给定页走向，假如有一种页面置换算法，它部是淘汰刚使用过的页面时的页面调度情况如下表 页面走向 物理块1 物理块2 缺页 1 1 缺 2 1 2 缺 1 3 3 2 缺 1 1 2 缺 2 4 1 4 缺 2 1 2 缺 1 3 3 2 缺 4 4 2 缺 从表中可看出，页面引用11次，缺页8次，所以缺页率为8/11=72.7% 5、在请页式存储管理系统中，使用先进先出页面置换算法，会产生一种奇怪的现答：如果一个进程的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，若给该

象，分配给进程的页面数越多，进程执行时的缺页次数反而升高。试举例说明这一现象。 进程分配3个物理块，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 缺页 4 4 缺 3 4 3 缺 2 4 3 2 缺 1 1 3 2 缺 4 1 4 2 缺 3 1 4 3 缺 5 5 4 3 缺 4 3 2 5 2 3 缺 1 5 2 1 缺 5 从表中可看出，页面引用12次，缺页9次。 若给该进程分配4个物理块，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 物理块4 缺页 4 4 缺 3 4 3 缺 2 4 3 2 缺 1 1 3 2 1 缺 4 3 5 5 3 2 1 缺 4 5 4 2 1 缺 3 5 4 3 1 缺 2 5 4 3 2 缺 1 1 4 3 2 缺 5 1 5 3 2 缺

从表中可看出，页面引用12次，缺页10次。

由上例可看出，对于以上页面走向，当分配给进程的物理块数从3变成4时，缺页次数不但没有下降，反而从9次增加到10次。

6、某请页式系统中，页的大小为100字，一个程序的大小为1200字，可能的访问序列如下：10、205、110、40、314、432、320、225、80、130、272、420、128（字），若系统采用LRU置换算法，当分配给该进程的物理块数为3时，给出进程驻留的各个页面的变化情况、页面淘汰情况及缺页次数。

答：由于页的大小为100字，因此访问序列10、205、110、40、314、432、320、225、80、130、272、420、128对应的页号是0、2、1、0、3、4、3、2、0、1、2、4、1。给该进程分配3个物理块，采用LRU置换算法，其页面调度情况如下表

8 文件管理

1、文件系统要解决的问题有哪些？

答：文件系统的目标是提高存储空间的利用率，它要解决的主要问题有：完成文件存储空间的管理，实现文件名到物理地址的转换，实现文件的目录操作，提供文件共享能力和保护措施，提供友好的用户接口。文件系统向用户提供了有关文件的目录操作的各种功能接口和系统调用，如命令接口、程序接口和图形用户接口。

2、许多操作系统中提供了文件重命名功能，它能赋予文件一个新的名字。若进行文件复制，并给复制文件起一个新名字，然后删除旧文件，也能达到给文件重命名的目的。试问这两种方法在实现在有何不同？

答：给文件重命名，用户必须提供两个参数：旧文件名和新文件名。实现该功能时，系统使用旧文件名查找文件目录，若找到旧文件名所在的目录表项，则将目录表项中文件名字段对应的值改为新文件名值。从实现上看，文件重命名功能完成的工作是修改表项中的文件名字段，除文件名外，文件的其他属性都未改变。

使用文件复制的方法，首先需要复制文件，并给新复制的文件起一个新名字，此时系统完成了一次物理文件的复制工作，然后删除旧文件。虽然这样也能达到给文件重新命名的目的，但其实现过程比前一种方式复杂，并且新文件与旧文件的物理存放地址肯定是不同的。

3、使用文件系统时，通常要显式地进行Open()与Close()操作。试问：（1）这样做的目的是什么？（2）能够取消显式地Open()与Close()操作么？若能，怎样做？（3）取消显式地Open()与Close()操作有什么不利？

答：（1）显示Open()操作完成文件的打开功能，它将待访问文件的目录信息读入内存活动文件表，建立起用户进程与文件的联系。显示Close()操作完成文件关闭操作，该操作删除内存中有关该文件的目录信息，切断用户与该文件的联系。若在文件打开期间，该文件做过某种修改，还应将其写回磁盘。

（2）可以取消显式的Open()与Close()操作。如果取消了显式的Open()与Close()操作，系统在进行文件操作之前需要判断文件是否已打开，若文件未打开，则应自动完成文件的打开安乐，以建立用户与文件之间的联系。同时，在系统结束时，还应自动关闭所有打开的文件。

（3）取消显式的Open()与Close()操作使得文件读/写的系统开销增加。因为每次读/写文件之前都需要判断文件是否已被打开，若未打开，还要完成打开操作。系统在结束也要做一些额外的工作，以完成Close()操作所完成的功能。当用户进程已完成对一个文件的访问但进程本身尚未执行完毕时，因无显式的Close()操作而无法关闭文件，从而不利于系统资源的回收。

4、文件目录的作用是什么？文件目录项通常包含哪些内容？ 答：文件目录是文件名与文件所在存储位置的一张映射表。文件系统根据它实现用户按名存取文件。文件目录由若干目录项组成，每个目录项记录一个文件的管理和控制信息。其中包括文件名、文件的类型、文件在存储设备上的位置、文件的存取控制信息、文件的创建访问和修改信息等。

5、文件物理结构中的链接分配方式有几种实现方法？各有什么特点？

答：文件物理结构中的链接分配方式有两种：一种是隐式的，即文件占用的物理块

中除存储文件信息之外，还存储有一个链接指针（即指向下一个物理块的指针）；另一种是显式的，即将链接指针从物理块中提取出来，单独建立一个表，如MS-DOS操作系统就采用这种方式，该表称为文件分配表。

隐式链接结构的文件只能采用顺序存取方法，否则效率太低。

显式链接结构的文件，由于指针单独管理，通常将文件分配表放在主存中，无论采用顺序存取还是随机存取，其速度都差不多。

6、设某文件A由100个物理块组成，现分别用连续文件、链接文件和索引文件来构造。针对3种不同的结构，执行以下操作时各需要多少次磁盘I/O。（1）将一物理块加到文件头部；（2）将一物理块加到文件正中间；（3）将一物理块加到文件尾部。

答： ?

采用连续文件时的情况如下：

如果要将一物理块加到文件头部。由于文件的头部没有空间扩展文件，若要把一个物理块加到文件的头部，必须查文件控制块，找到文件的第一个物理块，计算文件第100块的位置。然后将第100块读到内存，再将它写到磁盘的下一块中。这样，一个物理块需要两次访问磁盘（一次读入，一次写入）。最后将新加入内容从内存写到磁盘的物理块中，所以共访问磁盘201次。

如果将一个物理块加到文件正中间，根据上述分析，需要访问磁盘101次。 如果将一物理块加到文件尾部，直接将新加入的内容从内存写到磁盘的物理块中即可，只需要访问磁盘一次。

? 采用链接文件时的情况如下：

如果要将一物理块加到文件头部。只需要将新加入的内容从内在写到磁盘的物理块，然后将该物理块的指针指向原来第一个物理块，并修改文件控制块中第一块的地址和文件大小即可，所以访问磁盘一次。

如果将一物理块加到文件正中间，需要读出前50块（访问磁盘次），以便找到第50块的链接指针，将新加入的内容从内存写到新分配的物理块中，将新分配的物理块的链接指针指向第51块（访问磁盘一次），再将第50块的链接指针指向新插入的物理块（访问磁盘一次）。共需要访问磁盘52次。 如果将一物理块加到文件尾部，需要将第100块读出（访问磁盘100次），以便找到第100块。修改它的链接指针指向新插入的物理块（访问磁盘一次），只需要访问磁盘102次。

? 采用索引文件，且索引块在内存。情况如下：

如果要将一物理块加到文件头部。只需要将新加入的内容从内存写到磁盘的物理块，并在文件控制块中的头部增加新加入物理块的地址和文件大小即可，所以访问磁盘一次。

如果将一物理块加到文件正中间，只需要将新加入的内容从内存写到磁盘的物理块，并在文件控制块中的正中间增加新加入物理块的地址和文件大小即可，所以访问磁盘一次。

如果将一物理块加到文件尾部，只需要将新加入的内容从内存写到磁盘的物理块，并在文件控制块中的尾部增加新加入物理块的地址和文件大小即可，所以访问磁盘一次。

7、文件系统用混合方式管理存储文件的物理块，设块的大小为512B，每个块号占3B，如果不考虑逻辑块号在物理块中所占的位置，求一级索引、二级索引和三级索引时可寻址的文件最大长度。

答：由题目可知，块的大小为512B，每个块号占3B，一个物理块可放512/3＝170

个目录项。

一级索引可寻址的最大长度为：170*512＝85KB；

二级索引可寻址的最大长度为：170*170*512＝14450KB；

三级索引可寻址的最大长度为：170*170*170*512＝2456500KB。

8、一个计算机系统中，文件控制块占64B，磁盘块的大小为1KB，采用一级目录，假定目录中有3200个目录项，问查找一个文件平均需要访问磁盘多少次？

答：3200个目录项占用的磁盘块数为：3200*64/1024＝200（块)

一级目录平均访问磁盘的次数为1/2盘块数，故幸无访问磁盘100次。 9、假定磁盘块的大小是1KB，对于1GB的磁盘，其文件分配表（FAT）需要占用多少存储空间？当硬盘的容量为10GB时，FAT需要占用多少空间？

答：由题目可知，磁盘的大小为1GB，磁盘块的大小为1KB，所以该磁盘共有盘块数为：1GB/1KB＝1M（个）

而1MB个盘块号需要用20位表示，即文件分配表的每个表目大小为2.5B。FAT要占用的存储空间总数为：2.5B*1M＝2.5MB

当磁盘大小为10GB时，硬盘共有盘块：10GB/1KB＝10M（个）

又因 8M<10M<16M 故10M个盘号要用24位二进制表示。即文件分配表的每个表目大小为3B。FAT要占用的存储空间总数为：3B*10M＝30MB。

10、UNIX系统中采用索引节点表示文件的组织，在每个索引节点中，假定有12个直接块指针，分别有一个一级、二级和三级间接指针。此外，假定系统盘块的大小为8KB。如果盘块指针用32位表示，其中8位用于标识物理磁盘号，24位用于标识磁盘块号，问：（1）该系统支持的最大文件长度是多少？（2）该系统支持的最大文件系统分区是多少？（3）假定主存中除了文件索引节点外没有其他信息，访问文件的位置为12345678B时，需要访问磁盘多少次？

答：（1）由题目可知，盘块指针用32位表示，即盘块指针占32/8＝4B，一个索引盘块可以存放的盘块数为：8KB/4B＝2K，假定文件有12个直接块，分别有一个一级、二级和三级间接指针。最大文件长度是：

12*8KB+2K*8KB+2K*8KB+2K*2K*2K*8KB＝

（2）因为24位用于标识磁盘块号，该系统支持的最大文件系统分区是：224个盘

24

块，共有8KB*2＝128GB。

（3）假定主存中除了文件索引节点外没有其他信息，访问文件的位置为12345678B，相当于访问文件的相对块号为：12345678B/8K＝1507余334，即访问文件的第1507块，块内位移为：334。

系统有12个直接块，1507-12＝1495，由于1507<2K，第1495号索引项应在一级间接索引块中，故首先访问内存，得到一级间接索引块的块号；然后访问该间接块（第1次访问磁盘），得到1495号索引项；再访问1495号索引项对应的物理块号（第2次访问磁盘），最后得到块内位移为334的位置就是文件的12345678字节。故共访问磁盘2次。

11、磁盘文件的物理结构采用链接分配方式，文件A有10个记录，每个记录的长度为256B，存放在5个磁盘块中，每个盘块中放2个记录，如下表所示。若要访问该文件的第1580字节，问：（1）应访问哪个盘块的哪个字节？（2）要访问几次磁盘才能将该字节的内容读出。

物理块号 5 7 链接指针 7 14 物理块号 4 10 链接指针 10 0 14 4 答：（1）要访问该文件的第1580字节所在的相对盘块为：

1580/（256*2）＝3余44

由表可知，文件的相对盘块为3的逻辑块存放在物理块号4中，故应访问的物理块号为4，块内位移为44。

（2）由于采用链接文件，要访问物理块号为4的盘块，首先将上述链接表从磁盘读到内存（第1次访问磁盘），然后查找逻辑块号为0的物理块5，得到链接指针7；再查找逻辑块号为1的物理块7，得到链接指针14，第3次查找逻辑块号为2的物理块14，得到链接指针4；最后就可以读出块号为4的物理块（第2次访问磁盘）了。故共访问磁盘2次。

12、有一磁盘共有10个盘面，每个盘面上有100个磁道，每个磁道有16个扇区，每个扇区512字节。假定文件分配以扇区为单位，若使用位示图来管理磁盘空间，问：（1）磁盘的容量有多大？（2）位示图需要占用多少空间？（3）若空白文件上当的每个表目占5字节，什么空白文件目录占用空间大于位示图？

答：（1）磁盘的容量为：10*100*16*512B＝8000KB

（2）位示图用于描述扇区的使用情况，每个扇区用1位表示，位示图需要存储空间为：10*100*16＝16000bit＝2000B

（3）空白文件目录的每个表目占5B，根据上述计算位示图需要2000B，

2000B/5＝400

所以当空白区数大于400时，空白文件目录占用空间大于位示图。

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