操作系统-学位考复习.doc

. .
一、填空题
1. 分时操作系统的特征：多路性、交互性、独占性。
2. 信号量的物理意义：
当信号量>0时，表示 可用资源的数目。
当信号量〔逻辑上〕<0时，其绝对值表示 因请求该资源而被阻塞的进程数目。
3. 进程系统中，各进程之间逻辑上的相互制约关系称为进程同步。
4. 在多道程序系统中，进程之间存在着两种不同的制约关系 同步和互斥。
同步：是指进程间具有一定的逻辑关系。
互斥：进程间在使用共享资源方面的约束关系。
5. 将作业地址空间中的逻辑地址转换为储存中的物理地址称为 地址重定位〔映射，地址变换〕
6. 分区管理中，采用首次适应分配算法时，应将空闲区按 地址递增次序排队，登记在空闲区表中。
7. 在请求页式管理中，常用的页面淘汰算法有：
①最正确置换算法：选择淘汰永不再使用或在最长时间不再被访问的页面；
②先进先出〔FIFO〕算法：选择淘汰最先进入存的页面，即在存中逗留时间最长的页面；
③最近最久未使用算法：选择淘汰在离当前时刻最近一段时间使用最少的页面。
8. 实时操作系统与分时操作系统的主要区别：及时性、高可靠性
9. 临界资源的概念：一次仅允许一个进程访问的资源。
临界区：指进程中访问临界资源的那段程序代码。
假设一个进程已进入临界区，其他欲进入临界区的进程必须等待。
10. 程序顺序执行时有三个特点：顺序性、封闭性、可再线性。
11. 分区分配中的存储保护通常采用界限存放器和起址线长存放器。
12. 页表表目的主要容包括：页号和块号。
13. 在请求页式存储管理中采用FIFO〔先进先出〕页面淘汰算法，当分配的页面数增加时，缺页中断的页数 可能增加也可能减少。
14. 采用多道程序设计技术能充分的发挥 CPU 与外设并行工作的能力。
15. 进程在运行过程中有三种根本状态： 运行状态、就绪状态、等待状态。
16. 将进程的 PCB 在一起，就形成了进程队列。
17. 由n个进程共享同一个临界资源，假设使用信号量机制实现对临界资源的互斥访问，那么信号量值的变化围是 +1～ -〔n-1〕
18. 把逻辑地址转化为物理地址，称为地址映射〔重定位〕。
19. 静态重定位是在程序装入存时进展。
动态重定位是在程序执行时进展。
20. 最短寻道时间优先算法 是指选择与当前磁头所在磁道距离最近的请求作为下一次效劳的对象。
21. 操作系统的主要性能参数指标有吞吐量和利用率。
吞吐量 是指单位时间系统处理的作业量。
利用率 是指 在一个给定时间，系统的一个指定成分被使用的时间比例。
22. 进程主要有程序段、数据段、 PCB 三局部容组成。
其中PCB是进程存在的唯一标志，而程序段局部可以为其他进程共享。
23. 用PV操作管理临界区时，任何一个进程在进入临界区之前应调用 P 操作，退出临界区时应调用 V 操作。
24. 在一个单处理机系统中，假设有5个用户进程，且假设当前时刻为用户态，那么处于就绪状态的用户进程，最多有 4个，最少有 0 个。
25. 重定位的方式有：静态重定位、动态重定位。
26. 在断页式存储管理系统中，每道程序都有一个断表和一组页表
27. 从用户的观点出发所看到的文件的组织形式称为文件的逻辑构造。
从实现的观点出发文件在外存上的有效组织形式称为文件的物理构造。
28. 操作系统有四个模块组成：处理机管理功能，存储器管理功能，设备管理功能，文件管理功能。
29. 进程是程序的一次执行。

二、选择题
1. 从用户的观点看，操作系统是A 。
A． 用户与计算机之间的接口
B． 控制和管理计算机资源的软件
C． 合理地组织计算机工作流程的软件
D． 由假设干层次的程序按一定的构造组成的有机体
2. 所谓 B 是指将一个以上的作业放入主存，并且同时处于运行状态，这些作业共享处理机的时间和外围设备等其他资源。
A．多重处理
B．多道程序设计
C．实进处理
D．共行执行
3. 如果分时操作系统的时间片一定，那么 B ，那么响应时间越长。
A． 用户数越少
B． 用户数越多
C． 存越少
D． 存越多
4. 假设把操作系统看作计算机系统资源的管理者，以下的D 不属于操作系统所管理的资源。
A． 程序
B． 存
C． CPU
D． 中断
5. 在分时操作系统环境下运行的作业通常称为 C 。
A． 后台作业
B． 长作业
C． 终端型作业
D． 批量型作业
6. 作业的四种状态：提交，后备，运行，完成。
作业调度程序从处于 D 状态的队列中选取适当的作业投入运行。
A． 运行
B． 提交
C． 完成
D． 后备
7. OS是对 C 进展管理的。
A． 软件
B． 硬件
C． 计算机资源
D． 应用程序
8. 用户使用操作系统通常有三种手段，它们是终端命令、系统调用命令和 C 。
A． 计算机高级指令
B． 宏命令
C． 作业控制语言
D． 汇编语言
9. 既考虑作业等待时间，又考虑作业执行时间的调度算法是 A 。
A． 响应比高者优先
B． 短作业优先
C． 优先级调度
D． 先来先效劳
10. 分时操作系统通常采用 B 策略为用户效劳。
A． 可靠性和灵活性
B． 时间片轮转
C． 时间片加权分配
D． 短作业优先
11. 在进程管理中，当 C 时，进程从阻塞状态变为就绪状态。
A． 进程被进程调度程序选中
B． 等待某一事件
C． 等待的事件发生
D． 时间片用完
12. P、V操作是A 。
A． 两条低级进程通信原语
B． 两组不同的机器指令
C． 两条系统调用命令
D． 两条高级进程通信原语

1. 存储管理
2. 多道程序
3. 时间片轮转
4. 等待时间发生时
5. 有一个等待。？？？？
6. 就绪状态〔时间片用空〕
7. PCB
8. 作业控制块
9. 周转时间
10. 处理机管理→进程调度
11. 利用率
12. 通道？？中是从中断机构开展起的
13. 执行状态，就绪→运行被进程调度程序选中
14. 短作业优先
15. OS是针对……
16. PV操作是两条低级通信原语
17. OS允许在一台主机的多个终端……
18. 实时操作……作出响应

三、解析题
1.分时操作系统和实时操作系统进展比拟。
(1)多路性 实时信息处理系统与分时系统一样具有多路性。系统按分时原那么为多个终端用户效劳；而对实时控制系统，其多路性那么主要表现在经常对多路的现场信息进展采集以及对多个对象或多个执行机构进展控制。
(2)独立性 实时信息处理系统与分时系统一样具有独立性。每个终端用户在向实时系统提出效劳请求时，是彼此独立地操作，互不干扰；而在实时控制系统息的采集和对对象的控制，也都是彼此互不干扰。
(3)及时性 实时信息系统对实时性的要求与分时系统类似，都是以人所能承受的等待时间来确定；而实时控制系统的及时性，那么是以控制对象所要求的开场截止时间或完成截止时间来确定的，一般为秒级、百毫秒级，甚至有的要低于100微秒。
(4)交互性 实时信息处理系统虽也具有交互性，但这里人与系统的交互，仅限于访问系统中某些特定的专用效劳程序。它不象分时系统那样能向终端用户提供数据处理效劳、资源共享等效劳。
(5)可靠性 分时系统虽然也要求系统可靠，相比之下，实时系统那么要求系统高度可靠。因为任何过失都可能带来巨大的经济损失、甚至无法预料的灾难性后果。因此，在实时系统中，往往都采取了多级容错措施，来保证系统及数据的平安。

2.进程与程序的主要区别是什么?
答:1. 进程是一次执行的过程,是动态概念;程序是一组有序指令的集合,是静态概念
2. 一个进程可执行一个或多个程序;反之,一个程序也可由一个或多个进程来完成
3.程序可永远保存,进程具有生命周期.
4.进程是一个独立的运行单位,是提供资源利用和资源分配的独立单位,进程具有独立性,但有时有些进程之间又具有互相制约的关系,而程序不具有这种特性.
或:〔试从动态性、并发性和独立性上比拟进程和程序〕？
答:〔1〕动态性：进程既然是进程实体的执行过程，因此，动态性是进程最根本的特性。动态性还表现为：“它由创立而产生，由调度而执行，因得不到资源而暂停执行，以及由撤消而消亡〞。可见，进程有一定的生命期。而程序只是一组有序指令的集合，并存放在某种介质上，本身并无运动的含义，因此，程序是个静态实体。
〔2〕并发性：所谓进程的并发，指的是多个进程实体，同存于存中，能在一段时间同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也正是为了使其程序能和其它进程的程序并发执行，而程序是无法并发执行的。
〔3〕独立性：进程实体是一个能独立运行的根本单位，也是系统中独立获得资源和独立调度的根本单位。凡未建立进程的程序，都不能作为作为一个独立的单位参加运行

3. 文件管理系统为什么要设置翻开文件、关闭文件命令？
①操作系统需要大量的用户文件，而访问一个文件需要查询目录，有时甚至需要屡次查询目录。由于文件目录与文件一起放置在辅存上，当存许文件时，必须到辅存上读取文件目录信息，从中获得文件存放的地址，然后再去存取文件。这样一来，文件信息的存取将花费很很多时间。如果将整个文件容放入虽然可以提高读取速度，但这要占用大量主存空间，显然这也是不可取的。
②实际上在一段时间，使用文件的数量总是有限的。因此只要将目录当前要使用的那些文件目录表复制到存中就可以了。这样，既不占用太多的主存空间，又可显著提高查阅文件的速度。因此，大多数操作系统中，设置了翻开文件、关闭文件这两个操作。
③翻开文件完成的功能，是将文件的有关目录信息复制到主存的活动目录表中，以建立用户和这个文件的联系。
④关闭文件完成的功能，用户宣布这个文件当前不再使用，系统将其在主存中相应目录信息删除。因而，也就切断了用户和这个文件的联系。

4. 什么是虚拟设备？为什么要在操作系统中引入虚拟设备？
①虚拟设备是指通过虚拟技术，将一台独占设备变为假设干台虚拟设备，供假设干个用户进程同时使用，通常把这种通过虚拟技术处理后的设备称为虚拟设备。
②在操作系统中，引入虚拟设备是为了克制独占设备速度较慢，降低设备资源利用率的缺点，从而提高了设备利用率。

6．为什么说采用有序资源分配法不会产生死锁？
答:系统将所有的资源按类型进展线性的排队，并且给于不同序号，所有的进程对资源的请求必须严格按照资源序号递增的次序，这样所形成的资源分配图不可能出现环路。总有一个进程占有较高的序号资源，他继续请求的资源必然时空闲的，因此进程可继续推进，从而防止死锁发生。
答:假设系统中有m类资源、n个进程，分别用R1、R2、…、Rm〔1、2、…、m可看作资源编号〕和P1、P2、…、Pn表示。根据有序资源分配法可知，进程申请资源时必须按照资源编号的升序进展，即任何进程在占有了Ri类资源后，再申请的资源Rj的编号j一定大于i。因此在任一时刻，系统中至少存在一个进程Pk，它占有了较高编号的资源Rh，且它继续请求的资源必然是空闲的，因而Pk可以一直向前推进直至完成，当Pk运行完成后即会释放它所占有的所有资源；在Pk完成之后，剩下的进程集合中同样会存在一个进程，它占有了较高编号的资源，且它继续请求的资源必然是空闲的，因而它可以向前推进直至完成；以此类推，所有进程均可运行完成，故不会发生死锁。

7．一个操作系统有20个进程，竞争使用65个同类资源，申请方式是逐个进展的，一旦某进程获得它所需要的全部资源，那么立即归还所有资源，每个进程最多使用3个资源。假设仅考虑这类资源，该系统有无可能产生死锁，为什么？
【解】假设仅考虑同一类资源的分配，那么不会产生死锁。因为死锁产生的原因有两点：
〔1〕竞争资源，当系统中供多个进程所共享的资源，缺乏以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；
〔2〕进程推进顺序非法，进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。
产生死锁的必要条件：a互斥条件(进程对所分配到的资源进展排他性使用，即在一段时间某资源只由一个进程占有。如果此时还有其他进程要求该资源，要求者只能阻塞，直到占有该资源的进程用毕释放。)b请求和保持条件(进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其他进程占有，此时请求进程阻塞，但又对已经获得的其他资源保持不放。)c不剥夺条件(进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完后由自己释放。)d环路等待条件(在发生死锁时，必然存在一个进程——资源的环形链。即进程集合{P0,P1,P2,……,Pn}中的P0正在等待一个P1占用的资源； P1正在等待一个P2占用的资源；……， Pn正在等待一个P0占用的资源。)
在此题介绍的系统中，进程所需要的最大资源数为：20*3=60，而系统中共有该类资源65个，其资源数目已足够系统的各进程使用，因此绝不可能发生死锁。

8．试述分页系统和分段系统的主要区别。书P160
〔1〕页是信息的物理单位，段是信息的逻辑单位。
〔2〕页的大小固定且由系统确定，段的长度却不固定。
〔3〕分页的作业地址空间是一维的。分段的作业地址空间是二维的。

9、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。
解：设置3个信号量S、SO、SA，信号量S表示盘子是否为空，其初值为1；信号量SO表示盘中是否有桔子，其初值为0；信号量SA表示盘中是否有苹果，其初值为0。
同步描述：
int S=1;//表示盘子是否为空
int SO=0;//表示是否有橘子
int SA=0;//表示是否有苹果
main()
{
cobegin
father()
{
while(1)
{
p(S);//盘子是否空
将水果放入盘中;
if(放入的是桔子)v(SO);
else v(SA)
}
}
son()
{
while(1)
{
p(SO);//盘子中有无桔子
从盘中取出桔子;
v(S);
吃桔子;
}
}
daughter()
{
while(1)
{
p(SA);//盘子中有无苹果
从盘中取出苹果;
v(S);
吃苹果;
}
}
coend
}

丙
丁
甲
乙
叉2
刀1
叉1
刀2
食品
b
ψ
b
ψ
10、哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开场讨论问题；在讨论的间隙4位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如图。请用信号量及P、V操作说明这4位哲学家的同步、互斥过程。

解：在此题中，应设置4个信号量fork1、fork2、knife1、knife2，其初值均为1，分别表示资源叉1、叉2、刀1、刀2是否可用。同步描述如下：
int fork1=1;
int fork2=1;
int knife1=1;
int knife2=1;
main()
{
cobegin
Pa()
{
while(1)
{
p(knife1);
p(fork1);
进餐；
v(knife1);
v(fork1);
讨论问题；
}
}
Pb()
{
while(1)
{
p(knife2);
p(fork1);
进餐；
v(knife2);
v(fork1);
讨论问题；
}
}
Pc()
{
while(1)
{
p(knife2);
p(fork2);
进餐；
v(knife2);
v(fork2);
讨论问题；
}
}
Pd()
{
while(1)
{
p(knife1);
p(fork2);
进餐；
v(knife1);
v(fork2);
讨论问题；
}
}
coend
}

11、设公共汽车上，司机和售票员的活动分别为：
司机的活动：启动车辆；正常行车；到站停车；
售票员活动：关车门；售票；开车门；
在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现他们的同步。
解：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。
设置2个信号量：s1、s2，s1表示是否允许司机启动汽车，其初值为0；s2表示是否允许售票员开门，其初值为0。用P、V原语描述如下：
int s1=0;//是否允许司机启动汽车
int s2=0;//是否允许售票员开门
main()
{
cobegin
driver()
{
while(1)
{
p(s1);//刚开场肯定阻塞，等BUSMAN进程释放！
启动汽车；
正常行车；
到站停车；
v(s2);//通知售票员开门
}
}
busman()
{
while(1)
{
关车门；
v(s1);//通知司机可以开车了
售票；
p(s2);//判断是否可以开门
开车门；
上下乘客；
}
}
coend
}

12、图给出了4个进程合作完成某一任务的前驱图，试说明这4个进程间的同步关系，并用P、V操作描述它。

S2
S1
S4
S3

解：图说明任务启动后S1先执行。当S1完毕后，S2、S3可以开场执行。S2、S3完成后，S4才能开场执行。进程同步描述如下：
定义信号量：
a2=0;//表示S2能否开场
b2=0;//表示S2是否完毕
a3=0;//表示S3能否开场
b3=0;//表示S3是否完毕
main()
{
cobegin
S1()
{
S1
v(a2);
v(a3);
}
S2()
{
p(a2);
S2
v(b2);
}
S3()
{
p(a3);
S3
v(b3);
}
S4()
{
p(b2);
p(b3);
S4
}
Coend
}

13、.设有4道作业，它们的提交时间及执行时间如下：
作业号
提交时间
执行时间
1
8．0
2．0
2
8．3
0．5
3
8．5
0．1
4
9．0
0．4
试计算在单道环境下，采用先进先效劳调度算法(FCFS)和最短作业优先调度算法(SJF)时的平均周转时间和平均带权周转时间并指出它们的调度顺序，〔时间单位：小时，以十进制进展计算〕
完成时间=开场时间+运行时间，等待时间=开场时间-提交时间，周转时间=等待时间+运行时间=完成时间-提交时间，带权周转时间=周转时间/运行时间，响应比时间=〔等待时间+运行时间〕/运行时间
解：假设采用先来先效劳调度算法
作业号
提交时间
执行时间
开场时间
完成时间
周转时间
带权周转时间
1
8．0
2．0
8．0
10．0
2．0
1．0
2
8．3
0．5
10．0
10．5
2．2
4．4
3
8．5
0．1
10．5
10．6
2．1
21．0
4
9．0
0．4
10．6
11．0
2．0
5．0
调度顺序为1，2，3，4
平均周转时间： T=〔2.0+2.2+2.1+2.2〕/4=2.075
平均带权周转时间: W=(1.0+4.4+21.0+5.0)/4=7.25
假设采用短作业优先调度算法
作业号
提交时间
执行时间
开场时间
完成时间
周转时间
带权周转时间
1
8.0
2.0
8.0
10.0
2.0
1.0
2
8.3
0.5
10.5
11.0
2.7
5.4
3
8.5
0.1
10.0
10.1
1.6
16.0
4
9.0
0.4
10.1
10.5
1.5
3.75
调度顺序为1，3，4，2
平均周转时间： T=〔2.0+2.7+1.6+1.5〕/4=1.95
平均带权周转时间: W=(1.0+5.4+16.0+3.75)/4=6.5375
结论：SJF的平均周转时间和平均带权周转时间都比FCFS低。
假设采用响应比高者优先调度算法
作业号
提交时间
执行时间
开场时间
完成时间
周转时间
带权周转时间
1
8.0
2.0
8.0
10.0
2.0
1.0
2
8.3
0.5
10.1
10.6
2.3
4.6
3
8.5
0.1
10.0
10.1
1.6
16.0
4
9.0
0.4
10.6
11.0
2.0
5.0
调度顺序为1，3，2，4
平均周转时间： T=〔2.0+2.3+1.6+2.0〕/4=1.975
平均带权周转时间: W=(1.0+4.6+16+5.0)/4=6.65

14、今有三个批处理作业，第一个作业10：10到达，需要执行2小时；第 二个作业在10：10到达，需要执行1小时；第三个作业10：25到达，需要执行25分钟。分别采取如下三种作业调度算法：〔教师给的最后的一组数字中需要执行时间为20分钟〕
调度算法1：
作业号
到达时间
开场执行时间
执行完毕时间
1
10：00
10：00
12：00
2
10：10
12：00
13：00
3
10：25
13：00
13：25
调度算法2：
作业号
到达时间
开场执行时间
执行完毕时间
1
10：00
11：50
13：50
2
10：10
10：50
11：50
3
10：25
10：25
10：50
调度算法3：
作业号
到达时间
开场执行时间
执行完毕时间
1
10：00
10：00
12：00
2
10：10
12：25
13：25
3
10：25
12：00
12：25
〔1〕计算各调度算法下的作业平均周转时间。〔2〕调度算法1、3分别是什么作业调度算法？
解：〔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+1.67+0.42〕/ 3 =1.97小时
采用调度算法3时：作业1的周转时间为2小时
作业2的周转时间为3.25小时
作业3的周转时间为2小时
平均周转时间为：〔2+3.25+2〕/ 3 =2.42小时
〔2〕调度算法1是按照作业到达的先后次序执行的，所以它是先来先效劳调度算法〔FCFS〕；调度算法3是按照作业执行时间从短到长的次序执行的，所以它是短作业优先调度算法〔SJF〕。

15、表5.2给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。假设用首次适应算法和最正确适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？
表5.2 空闲分区表
分区号
大小
起始地址〔递增〕
1
32K
100K
2
10K
150K
3
5K
200K
4
218K
220K
5
96K
530K
解：〔1〕假设采用最正确适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小与申请空间大小一致，应从空间分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。显然采用最正确适应算法进展存分配，可以满足该作业序列的需求。为作业序列分配了存空间后，空闲分区表如表5.3〔a〕所示。
〔2〕采用首次适应算法，在申请96K存储区时，选中的是4号分区，进展分配后4号分区还剩下122K；接着申请20K时，选中1号分区，分配后剩下12K；最后申请200K，现有的五个分区都无法满足要求，该作业等待。显然采用首次适应算法进展存分配，无法满足该作业序列的需求。这时的空闲分区表如表5.3〔b〕所示。
表5.3〔a〕空闲分区表
分区号
大小
起始地址
1
12K
100K(120?)
2
10K
150K
3
5K
200K
4
18K
220K(420?)
表5.3〔b〕空闲分区表
分区号
大小
起始地址
1
12K
100K
2
10K
150K
3
5K
200K
4
122K
220K
5
96K
530K

16、某系统的进程状态转换图，请说明：//新颖！
执行
就绪
阻塞
2
3
1
4

（1） 引起各种状态转换的典型事件有哪些？
（2） 当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引起另一进程作一次状态转换。在什么情况下，当一个进程发生转换3时能立即引起另一个进程发生转换1？
（3） 试说明是否会发生下述因果转换：
a) 2à1 b〕3à2 c〕4à1
解：
（1） 当进程调度程序从就绪队列中选取一个进程投入运行时引起转换1；正在执行的进程如因时间片用完而被暂停执行就会引起转换2；正在执行的进程因等待的事件尚未发生而无法执行〔如进程请求完成I/O〕那么会引起转换3；当进程等待的事件发生时〔如I/O完成〕那么会引起转换4。
（2） 如果就绪队列非空，那么一个进程的转换3会立即引起另一个进程的转换1。这是因为一个进程发生转换3意味着正在执行的进程由执行状态变为阻塞状态，这时处理机空闲，进程调度程序必然会从就绪队列中选取一个进程并将它投入运行，因此只要就绪队列非空，一个进程的转换3能立即引起另一个进程的转换1。
（3） 所谓因果转换指的是有两个转换，一个转换的发生会引起另一个转换的发生，前一个转换称为因，后一个转换称为果，这两个转换称为因果转换。当然这种因果关系并不是什么时候都能发生，而是在一定条件下才会发生。
a) 2à1：当某进程发生转换2时，就必然引起另一进程的转换1。因为当发生转换2时，正在执行的进程从执行状态变为就绪状态，进程调度程序必然会从就绪队列中选取一个进程投入运行，即发生转换1。
b) 3à2：某个进程的转换3决不可能引起另一进程发生转换2。这是因为当前执行进程从执行状态变为阻塞状态，不可能又从执行状态变为就绪状态。
c) 4à1：当处理机空闲且就绪队列为空时，某一进程发生转换4，就意味着有一个进程从阻塞状态变为就绪状态，因而调度程序就会将就绪队列中的此进程投入运行。

17、页面走向为1、2、1、3、1、2、4、2、1、3、4，且开场执行时主存中没有页面。假设只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假设现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就一样的页面走向，其缺页率为多少？
解：根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下：
页面走向
1
2
1
3
1
2
4
2
1
3
4
物理块1
1
1
1
2
3
1
2
2
4
1
3
物理块2

2
2
3
1
2
4
4
1
3
4
缺页
缺
缺

缺
缺
缺
缺

缺
缺
缺
从上述页面置换图可以看出：页面引用次数为11次，缺页次数为9次，所以缺页率为9/11。
假设采用后一种页面淘汰策略，其页面置换情况如下：
页面走向
1
2
1
3
1
2
4
2
1
3
4
物理块1
1
1
2
2
2
1
1
1
2
2
2
物理块2

2
1
3
1
2
4
2
1
3
4
缺页
缺
缺

缺
缺

缺
缺

缺
缺
从上述页面置换图可以看出：页面引用次数为11次，缺页次数为8次，所以缺页率为8/11。

18、一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页率〔假设开场执行时主存中没有页面〕，并比拟所得结果。〔物理快为4的不做要求〕
（1） 最正确置换淘汰算法〔理论算法〕
（2） 先进先出淘汰算法
（3） 最近最久未使用淘汰算法
解：
〔1〕根据所给页面走向，使用最正确页面淘汰算法时，页面置换情况如下：
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
块2
块3
缺页
4

缺
4
3

缺
4
3
2
缺
4
3
1
缺

4
3
5
缺

2
3
5
缺
2
1
5
缺

缺页率为：7/12
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
块2
块3
块4
缺页
4

缺
4
3

缺
4
3
2

缺
4
3
2
1
缺

4
3
2
5
缺

1
3
2
5
缺

缺页率为：6/12
由上述结果可以看出，增加分配给作业的存块数可以降低缺页率。
〔2〕根据所给页面走向，使用先进先出页面淘汰算法时，页面置换情况如下：
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
块2
块3
缺页
4

缺
4
3

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

3
5
2
缺
5
2
1
缺

缺页率为：9/12
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
块2
块3
块4
缺页
4

缺
4
3

缺
4
3
2

缺
4
3
2
1
缺

3
2
1
5
缺
2
1
5
4
缺
1
5
4
3
缺
5
4
3
2
缺
4
3
2
1
缺
3
2
1
5
缺
缺页率为：10/12
由上述结果可以看出，对先进先出算法而言，增加分配给作业的存块数反而使缺页率上升，这种异常现象称为Belady现象。
〔3〕根据所给页面走向，使用最近最久未使用页面淘汰算法时，页面置换情况如下：
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
块2
块3
缺页
4

缺
4
3

缺
4
3
2
缺
3
2
1
缺
2
1
4
缺
1
4
3
缺
4
3
5
缺
3
5
4
5
4
3
4
3
2
缺
3
2
1
缺
2
1
5
缺
缺页率为：10/12
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
块2
块3
块4
缺页
4

缺
4
3

缺
4
3
2

缺
4
3
2
1
缺
3
2
1
4

2
1
4
3

1
4
3
5
缺
1
3
5
4

1
5
4
3

5
4
3
2
缺
4
3
2
1
缺
3
2
1
5
缺
缺页率为：8 /12
由上述结果可以看出，增加分配给作业的存块数可以降低缺页率。

19、设一计算机系统有输入机一台，打印机两台，现有两道程序，同时投入运行，且程序A先开场运行，程序B后运行，程序A的运行轨迹为：计算50ms,打印100ms,计算50ms,打印100ms;程序B的运行轨迹为：计算50ms，输入数据80ms,再计算方法100ms完毕。要求：
（1） 用图画出这两道程序并发执行时的工作情况
（2） 说明在两道程序运行时，CPU有无空闲等待？假设有，在哪段时间有等待？为什么会空闲等待？
（3） 程序A、B运行时，有无等待现象？在什么时候会发生等待现象？
解：
〔1〕 PA PB PA PB
CPU 50 50 100

输入机 80

打印机 100 100
〔2〕CUP有空闲等待，当PB让出CPU进展输入时，PA尚未打印完毕
〔3〕PB有等待现象，当PB输入完毕，此时PA 尚未计算完毕，PB只得等待

20、有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，存总共有8个存储块，试问逻辑地址至少应为多少位？存空间有多大？
解：
（1） 此题中，每页2048字节，所以页位移局部地址需要占据11个二进制位；逻辑地址空间最大为16页，所以页号局部地址需要占据4个二进制位。故逻辑地址至少应为15位。
〔2〕 由于存共有8个存储块，在页式存储管理系统中，存储块大小与页面的大小相等，因此，存空间为8页*2048字节=16K。

21、一请求分页存储管理系统，页面大小为每页100字节。有一个50×50的整型数组按行连续存放，每个整数占两个字节，将数组初始化为0的程序描述如下：
int a[50][50];
int i,j;
for (i=0;i<=49;i++)
for (j=0;j<=49;j++)
a[i][j]=0;
假设在程序执行时存中只有一