2024年4月11日发(作者：候访波)
例1、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把
一叠卡片逐一输入到缓冲区B1中，加工处理后再搬到缓冲区B2中，并在打印机上打印结
果。问：
① 系统要设几个进程来完成这个任务？各自的工作是什么？
② 这些进程间有什么样的相互制约关系？
③ 用P、V操作写出这些进程的同步算法。
分析 我们画一个草图来帮助我们理解这道题：
输
处输
入
理 出
缓冲区B1 缓冲区B2
卡片机
打印机
从图中可以看出，从“卡片机”到“打印机”共需要3个操作，即输入、处理、输出。这3
个动作就是完成任务的3个进程。
下面我们看看这些进程之间有什么样的制约关系。可以看出，这3个进程之间是同步关
系，合作完成从输入到输出的工作任务。对其中任何一个进程，要处理好与其关联的两端设
备的协调工作。以“输入进程”为例，它与卡片机和缓冲区B1关联，将卡片机的卡片输入到
缓冲区B1，在不考虑卡片机的情况下，就要考虑缓冲区的情况，即是满还是空，是空缓冲
区，输入进程就可以输入信息，如果缓冲区满，则要等待“处理进程”将B1中的信息取走，
使之为空，输入进程才能继续工作。依此类推，可以找出另外2个进程的制约关系。
一般来说，处理进程同步需要2个信号量，“输入进程”和“处理进程”同步，需要2个信号
量，解决缓冲区B1的协调操作问题；而“处理进程”和“输出进程”同步，还需要2个信号量，
解决缓冲区B2的协调操作问题。因此，共需要4个信号量。本题中“处理进程”的算法有一些
难度，因为它需要协调两个缓冲区的工作，考虑的因素比较多，算法复杂些。
答案
①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入
到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区
B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。
②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，
才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它
们，且B2被取空后，C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放
满后P进程才可从中取出它们,进行打印。
③信号量含义及初值：
B1full—— 缓冲区B1满，初值为0；
B1empty——缓冲区B1空，初值为0；
B2full—— 缓冲区B2满，初值为0；
B2empty——缓冲区B2空，初值为0；
例二：应用题(每小题10分，共20分)
1．设A：B两个进程共用一个缓冲区Q，A向Q写入信息，B从Q读出信息，算法框图
如图所示。判断该同步问题的算法是否正确?若有错，请指出错误原因并予以改正。
这个算法不对。(1分)
因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q
中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从、Q中读出完整的信息。
(1分)’进行改正：A、B两进程要同步使用缓冲区Q。为此，设立两个信号量：
empty表示缓冲区Q为空，初值为l； (2分)full表示缓冲区Q为满，初值为0。 (2
分)算法框图如图所示。(每个图正确各2分，共4分)
例3、下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优
先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进
行计算。）
作业号
1
2
3
提交时间
0.0
0.4
1.0
运行时间
8.0
4.0
1.0
分析 解此题关键是要清楚系统中各道作业随时间的推进情况。我们用一个作业执行时
间图来表示作业的执行情况，帮助我们理解此题。
采用先来先服务调度策略，其作业执行时间图如下：
作业
作业3
作业2
作业1
0 0.4 1.0 8.0 12.0 13.0 时间
作业提交时间 各作业陆续完成时间
采用短作业优先调度策略，其作业执行时间图如下：
作业
作业3
作业2
作业1
0 0.4 1.0 8.0 9.0 13.0 时间
作业提交时间 各作业陆续完成时间
另外，作业i的周转时间T
i
＝作业完成时间－作业提交时间
系统中n个作业的平均周转时间
T(
T
i
)
i1
n
1
，其中Ti为作业i的周转时间。
n
完成时间
8.0
12.0
13.0
周转时间
8.0
11.6
12.0
解：采用先来先服务调度策略，则调度次序为l、2、3。
作业号
1
2
3
提交时间 运行时间
0.0
0.4
1.0
8.0
4.0
1.0
开始时间
0.0
8.0
12.0
平均周转时间T＝（8＋11.6＋12）/3＝10.53
采用短作业优先调度策略，则调度次序为l、3、2。
作业号
1
3
2
提交时间
0.0
1.0
0.4
运行时间
8.0
1.0
4.0
开始时间
0.0
8.0
9.0
完成时间
8.0
9.0
13.0
周转时间
8.0
8.0
12.6
平均周转时间T＝（8＋8＋12.6）/3＝9.53
例3、今有三个批处理作业。第一个作业10:00到达，需要执行2小时；第二个作业在10:10到
达，需要执行1小时；第三个作业在10:25到达，需要执行25分钟。分别采取如下两种作业调
度算法：
调度算法1：
作业号 到达时间 开始执行时间 执行结束时间
1
2
3
10:00
10:10
10:25
10:00
12:00
13:00
12:00
13:00
13:25
调度算法2：
作业号 到达时间 开始执行时间 执行结束时间
1
2
3
10:00
10:10
10:25
11:50
10:50
10:25
13:50
11:50
10;50
（1）计算各调度算法下的作业平均周转时间。
（2）调度算法1是什么作业调度算法？
分析 作业的周转时间＝作业完成时间－作业提交时间。
以调度算法1的作业2为例，其周转时间=作业完成时间13:00－作业提交时间10:10，
得到结果为2小时50分钟，转换为小时为2.83小时。转换的目的是为了方便计算平均周转
时间。
解：（1）采用调度算法1时：
作业1的周转时间为2小时；作业2的周转时间为2.83小时；作业3的周转时间为3
小时；平均周转时间为：（2＋2.83＋3）／3＝2.61小时。
采用调度算法2时：
作业1的周转时间为3.83小时；作业2的周转时间为1.67小时；作业3的周转时间为
0.42小时；平均周转时间为：（3.83＋l.67＋0.42）／3＝l.97小时。
（2）调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。
例4、考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理
块的存储器中，问：
（1）逻辑地址需要多少二进制位表示？
（2）物理地址需要多少二进制位表示？
解 因为页面数为8=2
3
，故需要3位二进制数表示。每页有1024个字节，1024=2
10
，于
是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=2
5
）。
（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。
（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。
分析 在分页存储管理中，逻辑地址结构如下图所示。
页号p 页内地址d
它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内地址（页
内位移）d。页号的地址位数决定了页的多少，假设页号有20位，则地址空间中最多可容纳
的页面数为2
20
，即1MB个页面。页内地址位数确定了每页的大小，若页内地址为12位，
则每页大小为2
12
，即2KB。
同理，物理地址中块号的地址位数决定了块的多少，由于页式存储管理内存空间块的
大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。
例5、若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，
试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。
页号 块号
0
1
2
3
2
3
1
6
解 本题中，为了描述方便，设页号为p，页内位移为d，则：
（1）对于逻辑地址1011，p＝int（1011/1024）＝0，d＝1011 mod 1024＝1011。查页表
第0页在第2块，所以物理地址为10242＋1011＝3059。
（2）对于逻辑地址2148，p＝int（2148/1024）＝2，d＝2148 mod 1024＝100。查页表
第2页在第1块，所以物理地址为1024＋100＝1124。
（3）对于逻辑地址4000，p＝int（4000/1024）＝3，d＝4000 mod 1024＝928。查页表
第3页在第6块，所以物理地址为10246＋928＝7072。
（4）对于逻辑地址5012，p＝int（5012/1024）＝4，d＝5012 mod 1024＝916。因页号
超过页表长度，该逻辑地址非法。
例6、考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少？
解 使用FIFO算法，缺页次数是16；使用LRU算法，缺页次数是15；使用OPT算法，
缺页次数是11。
分析 所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。
当内存块数量为3时：
FIFO 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
块1 1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6
块2 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1
块3 3 3 3 5 5 5 1 1 1 6 6 6 3 3
缺页
因此，FIFO算法发生缺页中断的次数为16。
在FIFO算法中，先进入内存的页面被先换出。例如，当页6要调入时，内存的状态为
4、1、5，考查页6之前调入的页面，分别为5、1、2、4、…，可见4为最先进入内存的，
本次应换出，然后把页6调入内存。
LRU 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
块1 1 1 1 4 4 5 5 5 1 1 7 7 2 2 2
块2 2 2 2 2 2 6 6 6 3 3 3 3 3 3
块3 3 3 1 1 1 2 2 2 2 6 6 1 6
缺页
因此，LRU算法发生缺页中断的次数为15。
在LRU算法中，最近最少使用的页面被先换出。例如，当页6要调入时，内存的状态
为5、2、1，考查页6之前调入的页面，分别为5、1、2、…，可见2为最近一段时间内使
用最少的，本次应换出，然后把页6调入内存。
OPT 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
块1 1 1 1 1 1 1 3 3 3 3 6
块2 2 2 2 2 2 2 7 2 2 2
块3 3 4 5 6 6 6 6 1 1
缺页
因此，OPT算法发生缺页中断的次数为11。
在OPT算法中，在最远的将来才被访问的页面被先换出。例如，当页6要调入时，内存的
状态为1、2、5，考查页6后面要调入的页面，分别为2、1、2、…，可见5为最近一段时
间内使用最少的，本次应换出，然后把页6调入内存。
例7假设一个磁盘有200个磁道，编号从0～199。当前磁头正在143道上服务，并且刚刚
完成了125道的请求。如果寻道请求队列的顺序是：
86, 147, 91, 177, 94, 150, 102, 175, 130
问：为完成上述请求，下列算法各自磁头移动的总量是多少？
① FCFS ② SSTF ③ 电梯法
答案 FCFS为565；SSTF为162；电梯法为125。
分析
① 磁头在143道上，下一个请求为86，采用先来先服务磁盘调度算法FCFS，按照请
求到来的次序依次响应，于是磁头从143道移动到86道上，移动磁道数为143-86=57。再
从86道移动到147道，依此类推，进行调度的情况为：
下一磁道 移动磁道数
86
147
91
177
94
150
102
175
130
57
61
56
86
83
56
48
73
45
磁头移动总量为565。
② 采用最短寻道时间优先磁盘调度算法SSTF，当前磁头在143道上，选择的下一个请
求距当前磁头所在位置应具有最小的寻道时间。比较离143道最近的两个请求：130和147，
可知，从143道移动到147道花费的时间最短，仅为4，于是磁头移动到147道上。依此类
推，进行调度的情况为：
下一磁道 移动磁道数
147
150
130
102
94
91
86
175
177
4
3
20
28
8
3
5
89
2
磁头移动总量为162。
③ 采用电梯磁盘调度算法，要按照磁头移动的方向对请求进行扫描法，一侧的所有请
求完成后，才掉头回扫。题中的条件“当前磁头正在143道上服务，并且刚刚完成了125道
的请求”说明磁头移动的方向是从125道到143道。根据电梯法，磁头要继续向数大的方向
扫描下去，于是先遇到147道的请求，然后是150道，…，直到177道请求处理完，这时这
一侧的请求全部完成了。于是磁头掉头回扫，首先碰到130道的请求，…，最后处理的是
86道的请求。具体的调度情况为：
下一磁道 移动磁道数
147
150
175
177
130
102
4
3
25
2
47
28
94
91
86
8
3
5
磁头移动总量为125。
例8：．用如下图所示的进程状态转换图能够说明有关处理机管理的大量内容。试回答：
(1)图中标识的4种进程状态的变迁是由什么事件引起的？(2)下述进程状态变迁的因
果关系能否发生？为什么？
A．2—1 B．3—2 C．4—1
就绪一运行：CPU空闲，就绪态进程被调度程序选中。
运行一就绪：正在运行的进程用完了本次分配给它的CPU时间片。
运行一阻塞：运行态进程因某种条件未满足而放弃对CPU的占用，如等待读文件。阻
塞一就绪：阻塞态进程所等待的事件发生了，例如读数据的操作完成。
(2)下述进程状态变迁：(6分)
(A)2一1：可以。运行进程用完了本次分配给它的时间片，让出CPU，然后操作系统按
照某种算法从就绪队列中选出一个进程投入运行。
(B)3—2：不可以。任何时候一个进程只能处于一种状态，它既然由运行态变为阻塞态，
就不能再变为就绪态。
(C)4一1：可以。某一阻塞态进程等待的事件出现了，而且此时就绪队列为空，该进
程进入就绪队列后马上又被调度运行。
例8：考虑下面存储访问序列，该程序大小为460字：
10 ,11,104,170,73,309,185,245,246,434,458,364设页面大小是100字，请给出该访问序
列的页面走向。又设该程序的基本可用内存是
200字，如果采用最近最少使用置换算法(LRU)置换算法，缺页率是多少？（注：缺页率一
缺页次数／访问页面总数，要求给出计算过程）
根据已知条件页面大小是100字，将页面访问序列简化为：0,0,1,1,0,3,1,2,2,4,4,3 (2
分)
又因为该程序基本可用内存是200字，可知内存块数为2。（1分）
采用最近最少使用置换算法( LRU)，总共有7次缺页（2分），缺页率为7/12—58%(2
分)，具体算法如下：（过程3分）
1364
例9：
设Linux文件系统中的目录结构如下图所示：
(1)Linux的文件系统采用的是哪一种目录结构?有什么优点? +
(2)设当前工作目录是／usr，那么，访问文件ml．c的绝对路径名和相对路径名各是什么?
(3)现在想把工作目录改到liu，应使用什么命令(写出完整命令行)?
(4)如果用ls -l／usr／mengqc命令列出指定目录的内容，其中有如下所示的一项：
-rw--r--2 mengqc group l98 Jun 23 2007 m2．c
那么，该文件m2．C对文件主、同组用户、其他用户分别规定了什么权限
(1)UNIX的文件系统采用的是带链接的树形目录结构，即非循环图目录结构。其优点是
易于实现文件共享。 (2分)
(2)访问文件ml．C的绝对路径名是：／usr／mengqc／subl／ml．C(2分)
访问文件ml．C的相对路径名是：mengqc／subl／ml．C(2分)
(3)cd／usr／liu或者cd liu(2分)
(4)文件主权限是可读、可写，但不可执行；同组用户权限是只可读；其他用户权限是无，即不能
读、写或执行。 (2分) 。
2024年4月11日发(作者：候访波)
例1、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把
一叠卡片逐一输入到缓冲区B1中，加工处理后再搬到缓冲区B2中，并在打印机上打印结
果。问：
① 系统要设几个进程来完成这个任务？各自的工作是什么？
② 这些进程间有什么样的相互制约关系？
③ 用P、V操作写出这些进程的同步算法。
分析 我们画一个草图来帮助我们理解这道题：
输
处输
入
理 出
缓冲区B1 缓冲区B2
卡片机
打印机
从图中可以看出，从“卡片机”到“打印机”共需要3个操作，即输入、处理、输出。这3
个动作就是完成任务的3个进程。
下面我们看看这些进程之间有什么样的制约关系。可以看出，这3个进程之间是同步关
系，合作完成从输入到输出的工作任务。对其中任何一个进程，要处理好与其关联的两端设
备的协调工作。以“输入进程”为例，它与卡片机和缓冲区B1关联，将卡片机的卡片输入到
缓冲区B1，在不考虑卡片机的情况下，就要考虑缓冲区的情况，即是满还是空，是空缓冲
区，输入进程就可以输入信息，如果缓冲区满，则要等待“处理进程”将B1中的信息取走，
使之为空，输入进程才能继续工作。依此类推，可以找出另外2个进程的制约关系。
一般来说，处理进程同步需要2个信号量，“输入进程”和“处理进程”同步，需要2个信号
量，解决缓冲区B1的协调操作问题；而“处理进程”和“输出进程”同步，还需要2个信号量，
解决缓冲区B2的协调操作问题。因此，共需要4个信号量。本题中“处理进程”的算法有一些
难度，因为它需要协调两个缓冲区的工作，考虑的因素比较多，算法复杂些。
答案
①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入
到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区
B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。
②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，
才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它
们，且B2被取空后，C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放
满后P进程才可从中取出它们,进行打印。
③信号量含义及初值：
B1full—— 缓冲区B1满，初值为0；
B1empty——缓冲区B1空，初值为0；
B2full—— 缓冲区B2满，初值为0；
B2empty——缓冲区B2空，初值为0；
例二：应用题(每小题10分，共20分)
1．设A：B两个进程共用一个缓冲区Q，A向Q写入信息，B从Q读出信息，算法框图
如图所示。判断该同步问题的算法是否正确?若有错，请指出错误原因并予以改正。
这个算法不对。(1分)
因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q
中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从、Q中读出完整的信息。
(1分)’进行改正：A、B两进程要同步使用缓冲区Q。为此，设立两个信号量：
empty表示缓冲区Q为空，初值为l； (2分)full表示缓冲区Q为满，初值为0。 (2
分)算法框图如图所示。(每个图正确各2分，共4分)
例3、下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优
先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进
行计算。）
作业号
1
2
3
提交时间
0.0
0.4
1.0
运行时间
8.0
4.0
1.0
分析 解此题关键是要清楚系统中各道作业随时间的推进情况。我们用一个作业执行时
间图来表示作业的执行情况，帮助我们理解此题。
采用先来先服务调度策略，其作业执行时间图如下：
作业
作业3
作业2
作业1
0 0.4 1.0 8.0 12.0 13.0 时间
作业提交时间 各作业陆续完成时间
采用短作业优先调度策略，其作业执行时间图如下：
作业
作业3
作业2
作业1
0 0.4 1.0 8.0 9.0 13.0 时间
作业提交时间 各作业陆续完成时间
另外，作业i的周转时间T
i
＝作业完成时间－作业提交时间
系统中n个作业的平均周转时间
T(
T
i
)
i1
n
1
，其中Ti为作业i的周转时间。
n
完成时间
8.0
12.0
13.0
周转时间
8.0
11.6
12.0
解：采用先来先服务调度策略，则调度次序为l、2、3。
作业号
1
2
3
提交时间 运行时间
0.0
0.4
1.0
8.0
4.0
1.0
开始时间
0.0
8.0
12.0
平均周转时间T＝（8＋11.6＋12）/3＝10.53
采用短作业优先调度策略，则调度次序为l、3、2。
作业号
1
3
2
提交时间
0.0
1.0
0.4
运行时间
8.0
1.0
4.0
开始时间
0.0
8.0
9.0
完成时间
8.0
9.0
13.0
周转时间
8.0
8.0
12.6
平均周转时间T＝（8＋8＋12.6）/3＝9.53
例3、今有三个批处理作业。第一个作业10:00到达，需要执行2小时；第二个作业在10:10到
达，需要执行1小时；第三个作业在10:25到达，需要执行25分钟。分别采取如下两种作业调
度算法：
调度算法1：
作业号 到达时间 开始执行时间 执行结束时间
1
2
3
10:00
10:10
10:25
10:00
12:00
13:00
12:00
13:00
13:25
调度算法2：
作业号 到达时间 开始执行时间 执行结束时间
1
2
3
10:00
10:10
10:25
11:50
10:50
10:25
13:50
11:50
10;50
（1）计算各调度算法下的作业平均周转时间。
（2）调度算法1是什么作业调度算法？
分析 作业的周转时间＝作业完成时间－作业提交时间。
以调度算法1的作业2为例，其周转时间=作业完成时间13:00－作业提交时间10:10，
得到结果为2小时50分钟，转换为小时为2.83小时。转换的目的是为了方便计算平均周转
时间。
解：（1）采用调度算法1时：
作业1的周转时间为2小时；作业2的周转时间为2.83小时；作业3的周转时间为3
小时；平均周转时间为：（2＋2.83＋3）／3＝2.61小时。
采用调度算法2时：
作业1的周转时间为3.83小时；作业2的周转时间为1.67小时；作业3的周转时间为
0.42小时；平均周转时间为：（3.83＋l.67＋0.42）／3＝l.97小时。
（2）调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。
例4、考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理
块的存储器中，问：
（1）逻辑地址需要多少二进制位表示？
（2）物理地址需要多少二进制位表示？
解 因为页面数为8=2
3
，故需要3位二进制数表示。每页有1024个字节，1024=2
10
，于
是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=2
5
）。
（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。
（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。
分析 在分页存储管理中，逻辑地址结构如下图所示。
页号p 页内地址d
它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内地址（页
内位移）d。页号的地址位数决定了页的多少，假设页号有20位，则地址空间中最多可容纳
的页面数为2
20
，即1MB个页面。页内地址位数确定了每页的大小，若页内地址为12位，
则每页大小为2
12
，即2KB。
同理，物理地址中块号的地址位数决定了块的多少，由于页式存储管理内存空间块的
大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。
例5、若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，
试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。
页号 块号
0
1
2
3
2
3
1
6
解 本题中，为了描述方便，设页号为p，页内位移为d，则：
（1）对于逻辑地址1011，p＝int（1011/1024）＝0，d＝1011 mod 1024＝1011。查页表
第0页在第2块，所以物理地址为10242＋1011＝3059。
（2）对于逻辑地址2148，p＝int（2148/1024）＝2，d＝2148 mod 1024＝100。查页表
第2页在第1块，所以物理地址为1024＋100＝1124。
（3）对于逻辑地址4000，p＝int（4000/1024）＝3，d＝4000 mod 1024＝928。查页表
第3页在第6块，所以物理地址为10246＋928＝7072。
（4）对于逻辑地址5012，p＝int（5012/1024）＝4，d＝5012 mod 1024＝916。因页号
超过页表长度，该逻辑地址非法。
例6、考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少？
解 使用FIFO算法，缺页次数是16；使用LRU算法，缺页次数是15；使用OPT算法，
缺页次数是11。
分析 所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。
当内存块数量为3时：
FIFO 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
块1 1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6
块2 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1
块3 3 3 3 5 5 5 1 1 1 6 6 6 3 3
缺页
因此，FIFO算法发生缺页中断的次数为16。
在FIFO算法中，先进入内存的页面被先换出。例如，当页6要调入时，内存的状态为
4、1、5，考查页6之前调入的页面，分别为5、1、2、4、…，可见4为最先进入内存的，
本次应换出，然后把页6调入内存。
LRU 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
块1 1 1 1 4 4 5 5 5 1 1 7 7 2 2 2
块2 2 2 2 2 2 6 6 6 3 3 3 3 3 3
块3 3 3 1 1 1 2 2 2 2 6 6 1 6
缺页
因此，LRU算法发生缺页中断的次数为15。
在LRU算法中，最近最少使用的页面被先换出。例如，当页6要调入时，内存的状态
为5、2、1，考查页6之前调入的页面，分别为5、1、2、…，可见2为最近一段时间内使
用最少的，本次应换出，然后把页6调入内存。
OPT 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
块1 1 1 1 1 1 1 3 3 3 3 6
块2 2 2 2 2 2 2 7 2 2 2
块3 3 4 5 6 6 6 6 1 1
缺页
因此，OPT算法发生缺页中断的次数为11。
在OPT算法中，在最远的将来才被访问的页面被先换出。例如，当页6要调入时，内存的
状态为1、2、5，考查页6后面要调入的页面，分别为2、1、2、…，可见5为最近一段时
间内使用最少的，本次应换出，然后把页6调入内存。
例7假设一个磁盘有200个磁道，编号从0～199。当前磁头正在143道上服务，并且刚刚
完成了125道的请求。如果寻道请求队列的顺序是：
86, 147, 91, 177, 94, 150, 102, 175, 130
问：为完成上述请求，下列算法各自磁头移动的总量是多少？
① FCFS ② SSTF ③ 电梯法
答案 FCFS为565；SSTF为162；电梯法为125。
分析
① 磁头在143道上，下一个请求为86，采用先来先服务磁盘调度算法FCFS，按照请
求到来的次序依次响应，于是磁头从143道移动到86道上，移动磁道数为143-86=57。再
从86道移动到147道，依此类推，进行调度的情况为：
下一磁道 移动磁道数
86
147
91
177
94
150
102
175
130
57
61
56
86
83
56
48
73
45
磁头移动总量为565。
② 采用最短寻道时间优先磁盘调度算法SSTF，当前磁头在143道上，选择的下一个请
求距当前磁头所在位置应具有最小的寻道时间。比较离143道最近的两个请求：130和147，
可知，从143道移动到147道花费的时间最短，仅为4，于是磁头移动到147道上。依此类
推，进行调度的情况为：
下一磁道 移动磁道数
147
150
130
102
94
91
86
175
177
4
3
20
28
8
3
5
89
2
磁头移动总量为162。
③ 采用电梯磁盘调度算法，要按照磁头移动的方向对请求进行扫描法，一侧的所有请
求完成后，才掉头回扫。题中的条件“当前磁头正在143道上服务，并且刚刚完成了125道
的请求”说明磁头移动的方向是从125道到143道。根据电梯法，磁头要继续向数大的方向
扫描下去，于是先遇到147道的请求，然后是150道，…，直到177道请求处理完，这时这
一侧的请求全部完成了。于是磁头掉头回扫，首先碰到130道的请求，…，最后处理的是
86道的请求。具体的调度情况为：
下一磁道 移动磁道数
147
150
175
177
130
102
4
3
25
2
47
28
94
91
86
8
3
5
磁头移动总量为125。
例8：．用如下图所示的进程状态转换图能够说明有关处理机管理的大量内容。试回答：
(1)图中标识的4种进程状态的变迁是由什么事件引起的？(2)下述进程状态变迁的因
果关系能否发生？为什么？
A．2—1 B．3—2 C．4—1
就绪一运行：CPU空闲，就绪态进程被调度程序选中。
运行一就绪：正在运行的进程用完了本次分配给它的CPU时间片。
运行一阻塞：运行态进程因某种条件未满足而放弃对CPU的占用，如等待读文件。阻
塞一就绪：阻塞态进程所等待的事件发生了，例如读数据的操作完成。
(2)下述进程状态变迁：(6分)
(A)2一1：可以。运行进程用完了本次分配给它的时间片，让出CPU，然后操作系统按
照某种算法从就绪队列中选出一个进程投入运行。
(B)3—2：不可以。任何时候一个进程只能处于一种状态，它既然由运行态变为阻塞态，
就不能再变为就绪态。
(C)4一1：可以。某一阻塞态进程等待的事件出现了，而且此时就绪队列为空，该进
程进入就绪队列后马上又被调度运行。
例8：考虑下面存储访问序列，该程序大小为460字：
10 ,11,104,170,73,309,185,245,246,434,458,364设页面大小是100字，请给出该访问序
列的页面走向。又设该程序的基本可用内存是
200字，如果采用最近最少使用置换算法(LRU)置换算法，缺页率是多少？（注：缺页率一
缺页次数／访问页面总数，要求给出计算过程）
根据已知条件页面大小是100字，将页面访问序列简化为：0,0,1,1,0,3,1,2,2,4,4,3 (2
分)
又因为该程序基本可用内存是200字，可知内存块数为2。（1分）
采用最近最少使用置换算法( LRU)，总共有7次缺页（2分），缺页率为7/12—58%(2
分)，具体算法如下：（过程3分）
1364
例9：
设Linux文件系统中的目录结构如下图所示：
(1)Linux的文件系统采用的是哪一种目录结构?有什么优点? +
(2)设当前工作目录是／usr，那么，访问文件ml．c的绝对路径名和相对路径名各是什么?
(3)现在想把工作目录改到liu，应使用什么命令(写出完整命令行)?
(4)如果用ls -l／usr／mengqc命令列出指定目录的内容，其中有如下所示的一项：
-rw--r--2 mengqc group l98 Jun 23 2007 m2．c
那么，该文件m2．C对文件主、同组用户、其他用户分别规定了什么权限
(1)UNIX的文件系统采用的是带链接的树形目录结构，即非循环图目录结构。其优点是
易于实现文件共享。 (2分)
(2)访问文件ml．C的绝对路径名是：／usr／mengqc／subl／ml．C(2分)
访问文件ml．C的相对路径名是：mengqc／subl／ml．C(2分)
(3)cd／usr／liu或者cd liu(2分)
(4)文件主权限是可读、可写，但不可执行；同组用户权限是只可读；其他用户权限是无，即不能
读、写或执行。 (2分) 。