操作系统简答大题

1、请举例说明单用户单任务的操作系统与多用户多任务的操作系统之间的区别？

2、 死锁产生的4个必要条件是什么？它们是彼此独立的吗？

3、 当系统中的地址空间非常大时（例如 32位），会给页表的设计带来什么问题？请给岀一个方案并分析 其优缺

点。

4、 文件在磁盘上存放的形式有几种？它们与存取方法有何关系？

5、 试比较进程与程序的异同。

6、 脱机命令接口和联机命令接口有什么不同？

1、答案：DOS是单用户单任务的操作系统，通常这种操作系统没有进程调度，内存管理也比较简单，只划

分为系统区和用户区，是单道的程序运行环境。 Unix是多用户多任务的操作系统，有进程管理，内存管理

也比较复杂。它们都具有设备管理系统和文件管理系统，但功能也有差别。

2、 互斥，请求和保持，不剥夺，环路等待。

不是相互独立的，前三个条件是必要条件，而环路等待实际上是在前三者基础上的一种可能的结果，是死

锁的一种现象。

3、 会导致页表过长从而很难找到一块连续的存储空间存放页表， 此外如果页表中的行不连续也会加大访问 页表

的查找时间。

可以用多级页表解决这个问题，将页表分页，离散地存储在不同区域，同时建立另一张页表映射原来

页表的每一页。优点是不需要大块的连续空间，但并没有减少页表的空间，同时也增加了访存次数。

4、 三种存储结构的特点略。

顺序结构 链接结构 索引结构

顺序 顺序 顺序

随机 随机

1）每个进程实体中包含了程序段和数据段这 5、答案：进程与程序是紧密相关而又完全不同的两个概念：

两个部分，因此他们是紧密相关的。但从结构上看，进程实体中除了程序段和数据段外，还必须包含一个 数据结构，

即进程控制块 PCB 2）进程是程序的一次执行过程，因此是动态的；动态性还表现在进程由创 建而产生、由调度而进

行、由撤销而消亡，即它具有一定的生命周期。而程序只是一组指令的有序集合， 并可以永久的驻留在某种介质上，

其本身不具有运动的含义，是静态的。 3 ）多个进程实体可同时存放在内

存中并发执行，其实这正是引入进程的目的。而程序的并发执行具有不可再现性，因此程序不能正确并发 执行。4）进

程是一个能够独立运行、独立分配资源和独立接受调度的基本单位，而程序不可能在多道环境 下独立运行。5）进程与

程序不一一对应，同一个程序多次运行，将形成不同的进程；同一个程序的一次执 行也可以产生多个进程；而一个进

程也可以执行多个程序。

6、答案：脱机命令接口是 OS提供给批处理作业用户的作业控制语言。批处理用户不能直接与自己的运行 作业进行交

互，只能向系统提供用作业控制语言编写的作业说明书，并委托系统按照作业说明书中的作业 控制命令来对它们的作

业进行控制和管理。联机命令接口则不要求用户填写作业说明书，此时，系统将向 用户提供一组键盘命令或其他操作

方式的命令，用户可通过这些命令来交互的控制自己程序的运行并获得 操作系统的服务。

1、 简述分页和分段的区别。

2、 用户级线程与内核级线程的区别是什么？

3、 死锁产生的4个必要条件是什么？它们是彼此独立的吗？

4、 文件在磁盘上存放的形式有几种？它们与存取方法有何关系？

5、 在什么情况下需要进行重定位？为什么要引入动态重定位？

6、 命令接口和图形用户接口分别有什么优缺点？

1、 答案：分页和分段有许多相似之处， 但是在概念上两者完全不通， 主要表现在：①页是信息的物理单位， 分页是

为了系统管理内存的方便而进行的，故对用户而言，分页是不可见的，是透明的；段是信息的逻辑

单位，分段是作业逻辑上的要求，对用户而言，分段是可见的。

②页的大小是固定的，由系统决定；段的大小是不固定的，由用户作业本身决定。

③从用户角度看，分页的地址空间是一维的，而段的地址空间是二维的。

2、 答案：比较如下：

⑴ 程的调度与切换速度；对于内核级线程， OS负责以线程为单位的调度，对于用户级线程， OS的调度单

位是进程，同一个进程内部的线程切换是自己完成的。

⑵ 统调用；内核级线程的系统调用时只会引起该线程的阻塞，用户级线程的系统调用将引起整个进程的 阻塞。

⑶线程执行时间；内核级线程执行时间以线程为单位， 用户级线程执行时间以进程为单位， 内部线程共享。

3、 答案：互斥，请求和保持，不剥夺，环路等待。不是相互独立的，前三个条件是必要条件，而环路等待 实际上是在

前三者基础上的一种可能的结果，是死锁的一种现象。

4、 答案：三种存储结构的特点如下表：

顺序结构 链接结构 索引结构

顺序 顺序 顺序

随机 随机

5、 答案：源程序经过编译产生的目标模块一般总是从 0开始编址的，其中的地址都是相对于起始地址的相

0，因此指令和数 对地址。在将目标模块经过链接装入内存时，其分配到的内存空间的起始地址通常不为

据的实际物理地址与装入模块中的相对地址是不同的。此时，为了使程序能够正确执行，必须将相对地址

转换成物理地址，即进行重定位。

进程在运行过程中经常要在内存中移动位置，引入动态重定位的目的就是为了满足程序的这种需要，

动态重定位的实现需要一定的硬件支持， 重定位的过程是由硬件地址变换机构在程序执行每条指令时

自动完成的。

6、 答案：命令接口的优点：功能强，速度快，灵活性好，屏幕开销小；缺点：显示不直观，难学，难记。

图形用户接口的优点：显示直观，操作简便，易学；缺点：实现的代码规模大，对内外存容量、 CPU速度

和显示器的要求较高。

1、 何谓死锁？为什么将所有资源按类型赋予不同的序号，并规定所有进程按资源序号递增的顺序申请资 源后，系统便

不会产生死锁？

2、 简述分页和分段的区别。

3、 简述分时系统的特征？

4、 一个比较完善的文件系统应该具备哪些功能？

5、 微内核结构具有哪些优点？

6、 请说明中断驱动I/O方式和DMA方式有什么不同？

1、 答案：死锁是指多个进程在运行过程中因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无 法再向前推

进。原因是死锁的必要条件环路等待条件不可能成立。因为多个进程之间只可能存在占据较低 序号资源的进程等待占

据较高序号资源的进程释放资源的情况，但不可能存在反向的等待，因此不能形成 循环等待链。

2、 答案：分页和分段有许多相似之处，但是在概念上两者完全不通，主要表现在：

① 页是信息的物理单位，分页是为了系统

管理内存的方便而进行的， 故对用户而言，分页是不可见的，

是透明的；段是信息的逻辑单位，分段是作业逻辑上的要求，对用户而言，分段是可见的。

② 页的大小是固定的，由系统决定；段的大小是不固定的，由用户作业本身决定。

③ 从用户角度看，分页的地址空间是一维的，而段的地址空间是二维的。

3、 答案：多路性；允许一台主机连接多台终端，系统按分时原则为每个用户服务，每个用户以时间片为单 位轮流运

行。

独立性；每个用户各占一个终端，彼此独立操作互不干扰。 及时性；用户的请求能在很短的时间内得到响应，用户可

以接受。

交互性；用户可通过终端与系统进行人机对话。

4、答案 ：文件存储空间的管理；目录管理；文件的读写管理；文件的安全性管理；提供用户接口。

5、 答案：微内核结构的优点如下：1）提高了系统的灵活性和可扩充性。在微内核结构中， OS的大部分功

能都是相对独立的服务器来实现的，用户可以根据需要选配器中的部分或全部服务器，还可以随着计算机

硬件和OS技术的发展，相应的更新若干服务器或增加一些新的服务器。 2）提高了 OS的可靠性。由于所有

的服务器都是运行在用户态，它们不能直接访问硬件，因此，当某个服务器出现错误时，通常只会影响到 它自己，但

不会引起内核和其他服务器的损坏和崩溃。 3）适用于分布式系统。对用户进程而言，如果它通

过消息传递与服务器通信，那么他只须发送一个请求，然后等待服务器发来的响应，而无须知道这条消息 是在本地机

就处理还是通过网络送给远地机上的服务器。

6、 答案 ：不同之处主要有： 1）中断频率。在中断方式中，每当输入数据缓冲寄存器中装满输入数据或将 输出数据

缓冲寄存器中的数据输出之后，设备控制器便发生一次中断。由于设备控制器中配置的数据缓冲

寄存器通常较小，因此中断比较频繁；而 DMA方式下，在DMA控制器的控制下，一次能完成一批连续数据

CPU处理I/O中断的时间。2）数据的传 的传输，并在整批数据传送完后才发生一次中断，因此可大大减少

送方式。在中断方式下，由 CPU直接将输入数据写入控制器的数据缓冲寄存器供设备输出，或在中断发生 后直接从

数据缓冲寄存器中取出输入数据供进程处理，即数据传送必须经过 CPU而在DMA方式中，数据

的传输在DMA控制器的控制下直接在内存和 I/O设备间进行，CPU只需将数据传输的磁盘地址、内存地址

和字节数传给DMA空制器即可。

1. 设备分配与那些因素有关？（ 4 分）

2. 某系统中磁盘的每个盘块大小为 1KB，外存分配方法采用中的混合索引结构，

其中索引节点中直接地址 6项，一级索引地址 2项，二级索引地址 1 项，每个盘块号占用 4个字节，请问 该系统中

允许的文件最大长度是多少？（ 6 分）

3．为了能够查找到文件的位置， 在采用连续文件、 链接文件和索引文件时， 在目录中需要登记那些内容？ （6

分）

4•某采用分页存储管理的系统中，物理地址占 20位，逻辑地址中页号占6位，页大小为1KB，问：该系 统的内存空

间大小为多少？每块的大小为多少？逻辑地址共几位，每个作业最大长度为多少？若 0页放在

3块中， 1 页放在 7块中， 2页放在 9块中，逻辑地址 0420H 对应的物理地址是多少？（ 5分）

5. 试述缺页中断与一般中断的主要区别。 （4分）

6. 进程的基本状态包括哪几种？并画出其状态转换图。

7. 在一个批处理单道系统中，采用响应比高者

优先的作业调度算法。 当一个作业进入系统后就可以开始调

度，假定作业都是仅计算，忽略调度花费的时间。现有三个作业，进入系统的时间和需要计算的时间如表

所示：

作业 进入系统时间 需要计算时间 开始时间 完成时间 周转时间

1 9:00 60分钟 9:00 ⑴ ⑵

2 9:10

3 9:15

45分钟 ⑶ ⑷ ⑸

25分钟 ⑹ ⑺ ⑻

求岀每个作业的开始时间、完成时间及周转时间并填入表中

1. 答案：设备分配策略与下列因素有关：

(1) I/O设备的固有属性，对于独占设备，共享设备、虚拟设备等具有不同属性的设备，通常采用相应的 分配算法。

(2) 设备分配算法，常见的有先来先服务算法、优先级高者优先算法

(3) 设备分配的安全性，即避免死锁的产生。

(4) 设备独立性，设备独立性指应用程序独立于具体使用的物理设备。

评分标准：共4个要点，每个要点1分

2、答案：66054KB解题步骤及其评分标准：

直接地址可用的磁盘空间为 1KB6= 6KB (1分)；

X

1级索引项可用的磁盘空间为 1KB2562=512KB(2分)；

XX

2级索引项可用的磁盘空间为 1KB256256=64MB(2分)；

XX

求和：6KB+512KB+64MB=66054KB

3、 答案：连续文件：第一个磁盘块的块号和文件长度；链接文件：第一个磁盘块的块号；索引文件：索引 盘块号。

4、 答案：内存空间大小为1MB每块的大小为1KB；每个作业最大长度为 64KB;逻辑地址0420H对应的物 理地址是

1C20H.

解题步骤及其评分标准：逻辑地址0420H对应的页号为1，主存块号为7,页内地址20H,得到物理地址1C20H

5、 答案：缺页中断与一般中断的主要区别： ①在指令执行期间产生和处理中断信号。②一条指令在执 行期

间，可能产生多次缺页中断。

评分标准：共2个要点，每个要点2分

6、答案：进程的三种基本状态：就绪状态执行状态阻塞状态

7、答案: ⑴ 10: 00⑵60 分钟⑶ 10: 25(4) 11:10 ⑸ 120 分钟⑹ 10: 00(7) 10： 25(8)70 分钟

1 •简述具有通道的系统中独占设备的一般分配过程。 （3分）

2. 比较电梯调度算法和最短寻找时间优先调度算法。 （6分）

4分） 3. 为了实现虚拟页式存储管理，页表应该包含哪些内容？ （

4. 简述一种LRU页面置换算法的实现方案。（5分）

6. 列举引起进程创建的事件。简述进程创建的过程。 （6分）

7. 若系统有某类资源 mn+1个，允许进程执行过程中动态申请该类资源，但在该系统上运行的每一个进

x

程对该资源的占有量任何时刻都不会超过 m+1个。当进程申请资源时只要有资源尚未分配完则满足它的申

请，但用限制系统中可同时执行的进程数来防止发生死锁，你认为进程调度允许同时执行的最大进程数应 该是多少？

并证明之。（7分）

1、 答案：可按下述步骤进行设备分配： ①分配设备。②分配控制器。③分配通道。

2、 答案：①“电梯调度”与“最短寻找时间优先”都是要尽量减少移动臂移动时所花的时间；②不同的是

“最短寻找时间优先”不考虑臂的移动方向，总是选择离当前读写磁头最近的那个柱面的访问者，这种选 择可能导致

移动臂来回改变移动方向； “电梯调度”是沿着臂的移动方向去选择离当前读写磁头最近的那个

柱面的访问者，仅当沿臂移动方向无等待访问者时才改变臂的移动方向；③由于移动臂改变方向是机械动 作，速度相

对较谩。相比之下，电梯调度算法是一种简单、实用且高效的调度算法。但是，在实现时除了 要记住读写磁头的当前

位置外，还必须记住移动臂的移动方向。

3、 答案：在分页虚拟存储管理时使用的页表， 最少包括以下内容：物理块号、 状态位、修改位、外存地址

4、 答案：方案多个，下面仅是其一：为了实现 LRU必须在主存维护一张作业所有页的链表，表中各项按 访问时间

先后排序，最近访问的页排在表头，最久末用的页排在表尾，这就是所谓的栈式算法。每当要置

换一页时，必须对链表中的各项进行修改。若被访问的页在主存，则将其移到表头，调整相应项。若不在 主存，则将

新调的页放表头，其它项依次后移，将表尾一项挤掉。

6、答案：引起进程创建的典型事件有①分时系统中的用户登录、②批处理系统中的作业调度、③系统提供

服务、④应用进程本身的应用请求等。创建进程：①申请空白 PCB②为新进程分配资源。③初始化进程

控制块。④将新进程插入就绪队列。

7、答案：假设系统中有x个进程的进程，则资源至少要有 mx+1个，由于系统资源有 论n+1个，则可列

x

n。 出不等式：mx+1 < mn+1解不等式，得到x < n,所以系统允许同时执行的最大进程数为

x x

证明：假设在系统允许同时执行的最大进程数为 n时，仍然出现了死锁，此时应该存在一组进程进程都在

m个资源, 等待资源，而且系统已无资源可用。 则此时该组进程最多 n个，每个进程没有执行完时最多占用

所以现在系统分配出去的资源最多 mn,少于系统资源 mn+1，所以不可能有死所出现。

x x

n时系统不会有死锁发生 因此，系统允许同时执行的最大进程数为

1、有一个具有两道作业的批处理系统，有如下表所示的作业序列（表中所列作业优先级即为进程优先级,

数值越小优先级越高）。分别列岀下面两种情况下所有作业进入内存时刻及结束时刻， 并计算其平均周转时

间。

作业名 到达时刻 估计运行时间（分）

A 40 5

B 30 3

C 50 4

D 20 6

10 : 00

10 : 20

10 : 30

10 : 40

优先级

（6分）10： 00 A到达, 假设采用短作业优先的调度算法，进程调度采用优先级为基础的剥夺式算法。

无竞争， A开始运行

10： 20 B到达，进入内存，B的优先级高于 A, A停止，B运行（1分）

10： 30 C到达，不能进入内存（1分）

10： 40 D到达，不能进入内存

10： 50 B运行结束，C和D竞争进入内存，D进入，A运行（1分）

：

11

10 A运行结束，C进入内存，C运行（1分）

12： 00 C运行结束，D运行

12： 20全部结束

T=（ 70 + 30 + 90+ 100） /4 = 72.5 分钟（2 分）

2、在一分页存储管理系统中，逻辑地址长度为 16位，页面大小为4096字节，现有一逻辑地址为 2F6AH

6分） 且第0、1、2页依次存放在物理块 5、10、11中，问相应的物理地址为多少？（

由题意可知，本页式系统的逻辑地址结构为： （3分）

页号P

页内位移W

15 12 11 0

（1分） 逻辑地址2F6AH的二进制表示：0010 0

页号为2,在第11块中，故物理地址为 BF6AH （2分）

3、有一个仓库，可以存放 A和B两种产品，但要求：1）每次只能存入一种产品（A或B）; 2） -NA产品 数量一

V

B产品数量M其中，N和M是正整数。试用同步算法描述产品 A与产品B的入库过程。（13分）

V

答案：

int mutex=1; int sa=M-1; int sb=N-1; main（）

{while(1)

{取一个产品；

if(取的是A产品)

{wait(sa); wait(mutex);

将产品入库；

signal(mutex); signal(sb);

}

el

{wait(sb);

wait(mutex);

将产品入库；

signal(mutex);

signal(sa);

}

}

4、 在一个系统中，不采用死锁避免和预防措施，但当死锁发

}

生后需要能够检测岀来，请设计一个可行的死

锁检测方案

答案：死锁检测的数据结构类似银行家算法（略） ：1 ）可利用资源向量 available :表示m类资源中每一

类资源的可用数目；2）把不占用资源的进程向量 allocation=0 记入表L中，即LL; 3）从进程集合中

i

U

找到一个request < work的进程，做如下处理：将其资源分配图简化，释放出资源，增加工作向量

i

work=work+allocation ;将他记入L表中；4）若不能把所有的进程都记入 L表中，则表明系统状态 S的

资源分配图是不可完全简化的，因此该系统状态将发生死锁。

5、 设有A B、C三个进程，它们共享十个资源，每个进程最大需求量分别为 4，7, 8，它们对资源请求的 序列

如下表：（8分）

序号 进程 申请资源数

1 2

2 B 4

3 C 2

4 B 2

5 C 2

6 A 2

A

⑴请画岀执行完序号4时的资源分配矩阵；（2分）

⑵为使系统不发生死锁，执行完序号 6时，3个进程各处于什么状态，获得多少同类资源？（ 3分）

3分） ⑶按照上题时的状态，系统会发生死锁吗？为什么？（

解题步骤及其评分标准：

（2 4 2 ） （2 分）

（3分） A运行，B、C阻塞4、4、2

不会，A已得到全部资源，运行结束后释放资源可以使 B、C正常结束 （2分）

6、在实现文件系统时，为了加快文件目录的检索速度，可利用“ FCB分解法”。假设目录文件存放在磁盘

上，每个盘块512B。FCB占64B，其中文件名占8B,通常将FCB分解为符号目录项和基本目录项两部分， 其中符号

目录项大小为10B： （8分）

⑴基本目录项大小为多少字节？ （ 2分）

⑵假设某一目录文件共有 254个FCE，试分别给出采用分解法之前和之后，对该目录文件分别的平均访问 磁盘次数：

（3分）

⑶一般地，若目录文件分解前占用 N个盘块，分解后符号目录文件占用 M个盘块，请给出访问磁盘次数减

少的条件：（3分

解题步骤及其评分标准：

64 - 8 = 56B (2 分)

分解之前：平均访问次数为( 64 254/512+1 ) 12 = 165

X

分解之后：平均访问次数为(10 254/512 + 1) /2 = 3 (2分)

X

条件为：分解前平均读盘次数-分解后平均访问符号目录文件的读盘次数 >1,

即 N/2 - M/2>1，故 Mv— 2。 (3 分)

7、若在一分页存储管理系统中， 某作业的页表如下表所示。 已知页面大小为1024字节，试将逻辑地址1011、

2148、3000、4000转化为相应的物理地址。 (4分)

页号 块号

0 2

1 3

2 1

3 6

解题步骤及其评分标准：

设页号为P,页内位移为 W逻辑地址为A,页面大小为L,则：

P=int (A/L) W=A mod L

⑴ 1011 有：P=int ( 1011/1024 ) =0 W=1011 mod 1024=1011

第0页在第2块，故物理地址：3059

⑵ 2148 有：P=int ( 2148/1024 ) =2 W=2148 mod 1024=100

第2页在第1块，故物理地址：1124

⑶ 3000 有：P=int ( 3000/1024 ) =2 W=3000 mod 1024=952

第2页在第1块，故物理地址：1976

⑷ 4000 有：P=int (4000/1024 ) =3 W=4000 mod 1024=928

第3页在第6块，故物理地址：7072

&现有四个进程 R1、R2、W1 W2它们共享可以存放一个数的缓冲器 B。进程R1每次把来自键盘的一个

B中，供进程W2打 数存入缓冲器B中，供进程W1打印输岀；进程R2每次从磁盘上读一个数存放到缓冲器

(13分) 印输出。为防止数据的丢失和重复打印，问怎样用信号量操作来协调这四个进程的并发执行。

1、目的：考查学生对同步问题的掌握；满分值： 13分；答案：

四个进程可如下描述：

Semaphore sb=1,sx=0,sy=0; wait(sx); }

Item B; k:=B;

Void R1() signal(sb); Void W2()

{ {

while(1) } while(1)

{ } {

{ }

打印k中数

；

wait(sy);

j=B=接收的数

：； 乂；

wait(sb); wait(sb); {

打印j中数;

接收来自键盘的数

；

B:=x; while(1)

Signal(sx); {

} }

} }

Void w1() wait(sb); main()

{ {

while(1) Signal(sy); cobegin(

Void R2()

从磁盘上读一个数

；

y:=读入的数

；

B:=y

；

R1();

W1(); W2();

R2();

9、试设计在虚拟存储环境下实现简单的 clock 页面置换的可行方案。 （12 分）

使用 Clock 算法时，只须为每页设置一个访问位。在将内存中的所有页面都通过链接指针链成一个循环队

列（4 分）。当某页被访问时，其访问位置 1。置换算法在选择一页淘汰时，只须检查其访问位，如果是 0，

就选择该页换出； 若为 1，则重新将它复 0、暂不换出而给该页第二次驻留内存的机会 （4 分）。再按照 FIFO 算法

检查下一个页面。当检查到队列中的最后—个页面时，若其访问值仍为 1、则再返回到队首再去检查

第一个页面 （4 分）

10、某系统采用空闲区链结构对内存的空闲区进行说明，用 UPT表结构说明内存的占用情况。 UPT表和空

闲链结构分别如下所示：

#define true 1

*/ int size; /*

分区长度 */

#define fal 0

typedef struct /* }UTABLE[m]; }FREGION;

已分分区

Typedef struct /* FREGION *free;

空闲分区 表结构 */ /* 空闲

链表结构 */ 分区链表头指针 */

{

UTABLE UPT; /* 已分分区表 int address; /* 分区起始

{

地址 */ FREGION *forward; /* 上一个

int size; /*

int flag ； /*

分区长度 */ 分区起始地址 */ 函数过程：

表目状态， 1 /* 下一个分区

*/

FREGION *back;

起始地址 */ 表示有用登记项， 0 表示空表目

旅连衣斗*時杳城-

i

；

Y+J

11、司机与售票员问题：12分）

（

设信号量 so, sc, so = 1 表示门关着，sc = 1表示车停，初始状态 so = sc = 0;

void Process 司机

{while(1) {while(1)

{wait (so);

signal

卖票; 行车;

wait

(sc);

开门；｝

void Process

关门;

(so )；

售票员

开车;

停车;

signal (sc);

main ()

{cobegin

{Process_ 司机；Process_ 售票员；}

12、假定磁盘转速为 6000r/min，磁盘格式化时每个盘面被分为 8个扇区•…

读取一个扇区的时间是60/6000）/8=1.25ms ，读出该文件全部内容所需时间为:

（

1.25 8+ 2.5 7+ 7.5 7= 80ms ( 3 分)

X X X

采用交错试存储（图略），读岀全部文件的时间为:

1.25 8+ 2.5 7= 27.5ms （ 3 分）

X X

假定某页式虚拟系统中，某进程的页面访问踪迹为:

4，3，2，1，4，3，5，4，3, 2，1，5,它的实际页

面数为3。（ 6分）

⑴按FIFO页面置换算法，计算缺页率并画图示意;

（2分）

⑵按OPT页面置换算法，计算缺页率并画图示意；

（2分）

⑶按LRU页面置换算法，计算缺页率并画图示意。

（2分）

⑴缺页率75%

页面1

4 4 4 1 1 1 5 5 5 5 5 5

页面2

3 3 3 4 4 4 4 4 2 2 2

页面3

2 2 2 3 3 3 3 3 1 1

作业页面

4 3 2 1 4 3 5 4 3 2 1 5

缺页否

y y y y y y y y y

⑵缺页率58%

页面1 4 4 4 4 4 4 4 4 4 2 2 2

页面2 3 3 3 3 3 3 3 3 3 1 1

页面3 2 1 1 1 5 5 5 5 5 5

作业页面 4 3 2 1 4 3 5 4 3 2 1 5

是否缺页

y y y y y y y

⑶缺页率83%

页面1

4 4 4 1 1 1 5 5 5 2 2 2

页面2 3 3 3 4 4 4 4 4 4 1 1

页面3

2 2 2 3 3 3 3 3 3 5

作业页面

4 3 2 1 4 3 5 4 3 2 1 5

是否缺页

y y y y y y y y y y

13、在一个批处理单道系统中，采用响应比高者优先的作业调度算法• …

答案：⑴ 10: 00⑵60 分钟⑶ 10: 25（4） 11:10 （5）120 分钟⑹ 10 : 00⑺ 10: 25（8） 70 分钟 写算法：（35

分）

1、

有一个可以存放n整数的循环缓冲，今有 m个输入进程，每个• •次maphore

mutexP=1,mutexC=1,empty=n,full=0;

item buffer[n];

int in=out=0;

void producer()

{ while (1)

{ 输入一个数据放入 x 中 ;

wait(empty);

wait(mutexP);

buffer[in]=x;

in=(in+1) mod n;

signal(mutexP);

signal(full);

}

}

void consumer()

{while (1)

{ wait(full);

wait(mutexC);

y=buffer[out];

out=(out+1) mod n;

signal(mutexC);

signal(empty);

输出 y 中的数据 ;

}

}

main()

{cobegin

{ producer();

consumer();

2、写出一种可以避免死锁的资源分配算法

testsafety( )

/* 检测系统是否安全，若安全返回 true ，不安全返回 fal*/

{ int work[n];

int finish[m];

int i,k;

work = available;

/*finish[i] 表示进程 i 能否执行完，能执行完为 true ，否则 fal*/

for(i=0;i

k=0 ； i=0;

while(k

/* 循环检测进程是否可以执行完，若检测中发现连续检测 m 个进程都不能找到新的能停止运行的进程，应 停止

检测 */

{if(work>=need &&finish[i]==fal)

i

{ work=work+allocation ;

finish[i]=true;

k=0

}

i=(i+1)%m;

k++;

}

i

flag=true; /* 检测是否有进程没有执行完，若有 flag 为 fal*/

for(i=0;i

if(finish[i]==fal)flag=fal;

return(flag);

}

banker_allocation(int request[n],int i)

/* 银行家分配算法 , 分配成功返回 true, 不成功返回 fal*/

{if(!(request<=need ))return(fal);

i

if(!(request<=available))return(fal); availble=available-request; allocaition =allocaion +request; need

i i i

=need-request;

i

if(testsatefy( ))return(true);

el

{ availble=available+request; allocaition =allocaion -request; need =need+request;

i i i i

return(fal);

}