Needi (0,0,2,0) (2,1,0,0) (1,1,1,2) (3,1,0,0) (2,1,1,0)

分配的进程： P3 → P0 → P1 → P2 → P4 ∵ 存在安全分配序列{P3、P0、P1、P2、P4}

∴ 当前系统处于安全状态。

（2）因Request1(1,0,1,0)≤Need1(1,1,1,2)，P1请求合法；

因Request1 (1,0,1,0)≤Available(1,0,2,0)，系统可用资源可满足P1请求； 试把资源分配给进程P1并修改有关数据结构的数值：

Available=Available(1,0,2,0)-Request1(1,0,1,0)=Available(0,0,1,0) Need1=Need1(1,1,1,2)-Request1(1,0,1,0)=Need1(0,1,0,2)

Allocation1=Allocation1(2,1,0,0)+Request1(1,0,1,0)=Allocation(3,1,1,0) 而P0～P4进程还需的资源分别为(2,1,0,0)、(0,1,0,2)、(3,1,0,0)、(0,0,2,0)和(2,1,1,0)，所以系统可用资源（0,0,1,0）不能满足任一进程的需求，系统进入不安全状态，故作废试分配，P1的资源请求不能满足。

2、设有五个进程P0、P1、P2、P3、P4，共享一组资源A、B、C、D，假设在某一时刻资

源分配情况如下：

进程名 Need Allocation Available ABCD ABCD ABCD

P0 1 1 0 0 3 0 1 1 1 0 2 0 P1 0 1 1 2 0 1 0 0 P2 3 1 0 0 1 1 1 0 P3 0 0 1 0 1 1 0 1 P4 2 1 1 0 0 0 0 0 问：

（1）此时系统是否处在安全状态？为什么？ （2）若进程P1请求资源（0,0,1,0），系统能马上给予分配吗？为什么？ [解]：

（1）找安全序列：

Available (1,0,2,0) (2,1,2,1) (2,1,2,1) (5,1,3,2) (5,2,3,2) (5,3,4,3) 进程 P3 → P4 → P0 → P 1 → P 2 → 需要量 (0,0,1,0) (2,1,1,0) (1,1,0,0) (0,1,1,2) (3,1,0,0) ∵存在安全分配序列P3→P 4→P 0→P 1→P 2 ∴系统当时安全

（2）∵ Request1（0，0，1，0）≤Need1 （0，1，1，2）， 请求合理； Request1（0，0，1，0）≤Available （0，1，1，2），系统可用资源能满足； 进行试分配：

Need1 =（0，1，1，2）-（0，0，1，0）=（0，1，0，2）

Allocation1 = （0，1，0，0）+ Request1 （0，0，1，0）=（0，1，1，0） Avalable=（1，0，2，0）-（0，0，1，0）=（1，0，1，0）

在新状态下，存在安全分配序列P3→ P4→ P0→ P1→ P2，系统处于状态安全，

将试分改为正式分配。

第5章自测题

一、单项选择题，在四个备选答案中选一个合适的答案 1．（ ）是按某种算法，从就绪队列中挑选一个进程，并向它移交处理器的控制权。

A．作业调度 B．进程调度 C．磁盘调度 D．中级调度

11

[答案]：B

2．采用（ ）调度算法，运行时间最短的作业被优先调度。

A．FCFS B．SJF C．FB D．RR [答案]：B

3．某系统中预计有50个用户同时上机，为使每个用户能在2秒内得到响应，时间片最大限

度应为（ ）。

A．20ms B．30 ms C．40 ms D．50 ms [答案]：C 二、填空题

1．处理器的三级调度是指作业调度，中级调度和_____________。 [答案]：低级调度或进程调度

2．进程调度采用抢占方式时，常用的抢占原则有3种，时间片原则、短进程优先原则和_____________。 [答案]：优先权原则

3．作业在生命期有四个状态，其中运行状态是通过___________来实现的。 [答案]：进程及其状态

4．在动态优先权调度的系统中，如果某个进入就绪队列的进程的优先权高于正在运行的进

程时，系统采用抢占方式，将___________分配给优先权高的进程使之执行。 [答案]：处理器

5．常用的实时调主度算法，时间片轮转法、非抢占的优先级法、基于时钟中断的抢占优先级法和 。 [答案]：立即抢占的优先级法 三、判断改错题

判断下列各题正误，正者打“√”，误者打“×”，并将具体修改内容写在该题的下面，但有下划线部分不能改。

1．引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量，因此也可以把它归入到主存管理。（ ） [答案]：√。

2．在实时要求严格的实时系统中进程调度采用非抢占方式。 [答案]：×，将“非抢占方式”改成“抢占方式”。 四、简答题

1．进程调度需要完成哪些功能？ [答案]：记录系统中所有进程执行情况。选择下次占有处理器的进程。进行进程上下文切换。 2．实时调度常用哪些调度算法？它门适用什么场合？ [答案]：实时调度常用4种调度算法：

时间片轮转调度算法，适用于一般的实时信息处理系统；

非抢占的优先级调度算法，适用于实时要求不太严格的实时控制系统； 基于时钟中断抢占的优先级调度算法，适用于大多数实时系统；

立即抢占的优先级调度算法，适用于实时要求比较严格的实时控制系统。 五、应用题

1．在单道批处理系统中，假设有四道作业，它们的情况描述如下：

作业号 提交时间 运行时间（分） 开始执行时间 完成时间

1 8：00 30

12

2 8：10 20 3 8：20 5 4 8：30 10

约定系统从8：00开始调度，要求：

（1）计算这批作业在（FCFS）先来先服务算法时的作业平均周转时间T、作业平均带权周

转时间W。

（2）计算这批作业在（SJF）短作业优先算法时的作业平均周转时间T、作业平均带权周转

时间W。

[答案]：(1)FCFS：调度的次序是1→2→3→4

T=(8:30-8:00+8:50-8:10+8:55-8:20+9:05-8:30)/4

=(30+40+35+35)/4=35（分）

W=(30/30+40/20+35/5+35/10)/4=(1+2+7+3.5)/4=3.375

(2)SJF：调度的次序是1→3→4→2

T=(8:30-8:00+8:35-8:20+8:45-8:30+9:05-8:10)/4 =(30+15+15+55)/4=28.75（分）

W=(30/30+15/5+15/10+55/20)/4=(1+3+1.5+2.75)/4=8.25/4=2.0625

2．假设有四道作业，他们的提交时间和执行时间由下表给出。请计算在单道程序环境下，用先来先服务调度算法(FCFS)和最短作业优先调度算法(SJF)时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（从相对时间0开始调度）

作业名 A B C D E 提交时刻（时） 0 1 2 3 4 执行时间（小时） 4 5 2 3 4 先来先服务调度算法： ①平均周转时间 ②平均带权周转时间 最短作业优先调度算法：①平均周转时间 ②平均带权周转时间 [答案]：

先来先服务调度算法：调度的次序是A→B→C→D→E

①平均周转时间 9.2（小时）

②平均带权周转时间 2.85

最短作业优先调度算法：调度的次序是A→C→D→E→B

①平均周转时间 8（小时） ②平均带权周转时间 2.13

第6章自测题

一、单项选择题，在四个备选答案中选一个合适的答案 1．属于内存连续分配方式的是（ ）。

A．固定分区分配方式 B．分段存储管理方式 C．分页存储管理方式D．段页式存储管理方式 [答案]：A

2．属于内存连续分配方式的是（ ）。

A．分页存储管理 B．分段存储管理 C．可变分区管理 D．段页式存储管理 [答案]：C

13

3．可变分区管理中的（ ）算法，空闲区按其大小递增次序组成链。

A．首次适应 B．最佳适应 C．下次首次适应 D．最坏适应 [答案]：B

4．关于分段存储管理说法错误的是（ ）。

A．便于编程 B．便于分段共享 C．便于内存分配 D．能动态链接 [答案]：B

5．在下面的页面置换算法中，（ ）是实际上难以实现的

A．先进先出置换算法 B．最近最久未使用置换算法 C．clock 置换算法 D．最佳置换算法 [答案]：D

6．以下不是存储管理处理的功能有（ ）。

A．为每个程序安排内存空间 B．保护运行程序不受干扰

C．将运行中程序的地址转换成物理地址 D．决定哪个进程的程序和数据切换到内存中 [答案]：D 二、填空题

1．在分区存储管理中，存储保护有两种方法：界限寄存器法和___________。 [答案]：存储保护键法

2．在分页存储管理方式中，地址结构有页号P和位移量W组成，地址转换时页号P与页

表长度L进行比较，如果___________，则产生越界中断。 [答案]：P≥L

3．分区存储管理中存在内零头的是___________分配方式。 [答案]：固定分区

4．请求分页存储管理方式中，调入页面的时机可采用两种策略，预先调页和___________。 [答案]：请求式调页

5．动态地址重定位是在___________过程中完成地址变换的。 [答案]：程序的执行

6．一个用户程序中含有代码段A、代码段B和数据段，当该程序在段页式管理机构中运行

时，系统至少为该用户程序建立___________个段表。 [答案]：1

三、判断改错题

判断下列各题正误，正者打“√”，误者打“×”，并将具体修改内容写在该题的下面，但有下划线部分不能改。

1．页面最佳置换算法是一种性能最好，且容易实现的算法。 [答案]：×，将“且容易实现”改成“但实际上不能实现”。

2．采用静态重定位方式装入内存的程序可以在内存中移动。 [答案]：×，将“可以”改成“不可以”。

3．可变式分区分配方式为某作业分配内存时，分配给的区域大小往往大于该作业的大小。 [答案]：×，将“往往大于”改成“等于”。

4．请求分页系统中的页表表项中修改位，表示该页调入内存后是否允许修改。 [答案]：×，将“允许修改”改成“已经修改”。 四、简答题

1．什么是动态重定位？它有什么好处？

14

[答案]：

动态重定位是指在程序执行过程中进行的地址重定位，即可使装配模块不加任何修改就装入内存。

好处主要有2个，一是被装入的程序可以在内存中移动而不影响其程序正确运行；二是程序的若干个相对独立的目标模块可以装在不相邻的内存区域。 2．什么是虚拟存储器？有何特征？ [答案]：

虚拟存储器是具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的存储器系统。虚拟存储器有如下4个特性：

离散性，内存采用离散分配方式。

多次性，一个作业分多次调入内存运行。

对换性，作业运作业行过程中在内存和外存对换区之间换进、换出。 虚拟性，从逻辑上对内存容量进行扩充。 五、应用题

1．假定某请求页式存储管理系统中，为一进程分配了内存物理块3块，考虑以下的页面引

用串：1,2,3,4,2,1,4,5,2,1,2,3。 问：（1）若按最近最久未使用（LRU）页面置换算法，请问将发生缺页中断的次数和缺页率（开始3页不算缺页），并画图示意。

（2）若页面大小为1KB，试给出虚地址(12345)8对应的物理地址（仍用8进制表示，假定该虚页对应的内存物理块号为7）。 [答案]：

（1）页面引用串如下： 1 2 3 4 2 1 4 5 2 1 2 3 LRU 1 1 1 4 4 4 4 4 4 1 1 1 M=3 2 2 2 2 2 2 5 5 5 5 3

3 3 3 1 1 1 2 2 2 2

缺页： * * * * * *

缺页次数F＝6次， 缺页率f=6/12=50%。

（2）因为页面为1KB，所以页内地址占10位，虚地址对应的物理块号为7 所以虚地址(12345)8=(1010011100101)2=(101)2(0011100101)2 转换 (111)2(0011100101)2=(1110011100101)2=(16345)8

2．假定某请求分页存储管理系统中，进程的页面引用串为：1,2,3,4,1,2,3,5,4,3,2,1。若系统分配给该进程内存物理块是3块。要求：

（1）若按先进先出FIFO页面置换算法，请给出发生缺页的次数F（开始的3页不算缺页），并画图示意。

（2）若页面大小为2KB，试给出虚地址8进制数654321对应的物理地址（仍用8进制数表示，假定该页已装在内存的物理块号为7）。 [答案]：

(1)FCFS 时 T=(8:30-8:00+8:50-8:10+8:55-8:20+9:05-8:30)/4 =(30+40+35+35)/4=35（分）

W=(30/30+40/20+35/5+35/10)/4=(1+2+7+3.5)/4=3.375 (2)SJF 时 T=(8:30-8:00+8:35-8:20+8:45-8:30+9:05-8:10)/4 =(30+15+15+55)/4=28.75（分）

W=(30/30+15/5+15/10+55/20)/4=(1+3+1.5+2.75)/4=8.25/4=2.0625

15