第一章习题及答案
二、单项选择题
三、多项选择题 四、是非判断题
第二章 习题及答案
一、填空题
六、综合应用题 ?
请回答下列问题：
（1）该系统采用了怎样的进程调度算法？说明理由。 （2）把图中发生①-④的状态变化原因填入下表中。
变化 ① ② ③ ④ 【参考答案】
（1）该系统采用的是“时间片轮转调度算法”。
该调度算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占用处理器，但规定只能使用一个“时间片”。如果一个时间片用完，进程工作尚未结束，则它也必须让出处理器而被重新排到就绪队列的末尾，等待再次运行，当再次轮到运行时，重新开始使用一个新的时间片。这样，就绪队列中的进程就依次轮流地占用处理器运行。
（2）
变化原因 1． 某系统中进程有如下的状态变化图：
变化 ① ② ③ ④
变化原因 进程到达就绪队列头，从就绪状态变为运行状态。 运行的时间片到，从运行状态变为就绪状态，进入就绪队列末尾排队，等待调度。 运行过程中，进程申请IO，从运行状态变为等待状态，进入等待队列等待IO完成。 进程所申请的IO完成，进入就绪队列末尾排队，等待调度。 2．设某系统采用可抢占的优先级进程调度算法，系统在某一段时间内有A、B、C三个进程，进程C优先级最高，进程A优先级最低，进程B优先级介于进程A、C之间，它们的就绪时刻、计算与I/O所需时间如下表所示：
进程 A B C 进程就绪时刻 0ms 10ms 15ms 计算时间 15ms 25ms 3ms I/O操作时间 10ms 15ms 20ms 计算时间 5ms 10ms 10ms （1）若系统采用多道方式运行，给出这三个进程运行完成总共所需的时间，并用图示给出三个进程的实际运行过程（忽略进行系统调度所需时间）。
（2）采用多道方式运行比采用单道方式运行节省多少时间。 【参考答案】
（1）若系统采用多道方式运行，这三个进程运行完成总共所需的时间为68ms。 （图示略）
（2）采用单道方式运行，这三个进程运行完成总共所需的时间为113ms
采用多道方式运行比采用单道方式运行节省时间：
113-68=45ms
3．设某系统采用可抢占的优先级进程调度算法，在系统的就绪队列中有X、Y、Z三个进程，进程Z优先级最高，进程X优先级最低，进程Y优先级介于进程X、Z之间，它们的计算与I/O所需时间如下表所示：
进程 X Y Z 计算时间 15ms 25ms 3ms I/O操作时间 10ms 15ms 20ms 计算时间 5ms 10ms 10ms （1）若系统采用多道方式运行，给出这三个进程运行完成总共所需的时间，并用图示给出三个进程的实际运行过程（忽略进行系统调度所需时间）。
（2）采用多道方式运行比采用单道方式运行节省多少时间。 【参考答案】
（1）若系统采用多道方式运行，这三个进程运行完成总共所需的时间为68ms。 （图示略）
（2）采用单道方式运行，这三个进程运行完成总共所需的时间为113ms
采用多道方式运行比采用单道方式运行节省时间：
113-68=45ms
第三章 习题及答案
四、是非判断题 五、简答题
六、综合应用题
1．有一128行、128列的整数数组A在系统中按行存放。系统采用页式存储管理，内存一个页面可放128个整数。给数组A赋值分别采用程序段（1）、程序段（2）时，各自产生的缺页中断次数为多少。 程序段（1）： for i:=1 to 128 do for j:=1 to 128 do A[i][j]:=0; 程序段（2）： for j:=1 to 128 do for i:=1 to 128 do A[i][j]:=0; 设在内存中给A分配十个物理页面，并且开始时A的第一个页面已在内存，当分别完成上述程序后， 【参考答案】
采用代码（1）其访问顺序与数组存放顺序一致，由于第一页已在内存中，所以除了访问第一页时不发生缺页，对其余127页的访问均发生缺页，所以共发生128-1次缺页中断。
采用代码（2）其访问顺序是按列访问，与数组存放顺序不一致，经分析可知共发生128*128-1次缺页中断。
2．已知某系统采用虚拟页式存储管理，虚地址为16位，其中第10~15位为页号，0~9位为页内地址。
（1）假定某进程P包含5页，操作系统为该进程在内存中固定分配了3个物理块，开始时为空。设该进程运行时对页面的访问顺序为：1，2，1，0，4，1，3，4，2，1，4，1
在采用FIFO（先进先出）、LRU（最近最少使用）两种置换算法的情况下，分别会产生多少次缺页？给出各自被淘汰的页。
（2）假定在时刻t，进程P只有第0、1、2页在内存中，对应物理块号分别为5、8、10。下列虚拟地址是否在内存中。若在给出相应的物理地址。
（a）0A4EH （b）122AH 【参考答案】 （1）
FIFO 共发生9次缺页
1 * 1 2 * 2 1 1 2 1 0 * 0 2 1 4 * 4 0 2 1 1 * 1 4 0 2 3 * 3 1 4 0 4 3 1 4 2 * 2 3 1 4 1 2 3 1 4 * 4 2 3 1 1 * 1 4 2 3 依次被淘汰的页为：1、2、0、4、1、3
LRU 共发生7次缺页
1 * 1 2 * 1 2 1 1 2 0 * 1 2 4 * 1 4 1 1 4 3 * 1 4 4 1 4 2 * 2 4 1 * 2 4 4 2 4 1 2 4 （2）
0 0 2 0 3 0 3 3 1 1 3 1 1 依次被淘汰的页为：2、0、1、3
（a）0A4EH对应的二进制为 0000 10,10 0100 1110
该地址表明它对应第2页,根据已知该页在内存,对应物理块为10,所以,物理地址为: 0010 10,10 0100 1110 (十六进制为2A4EH)
（b）122AH对应的二进制为 0001 00,10 0010 1010 该地址表明它对应第4页, 根据已知该页不在内存中。
3．分页式存储空间的分配由于块的大小是固定的，可以用一张位示图来构成主存分配表。现设主存有8192块，则可用字长为32位的256个字作为位示图。若块号、字号、位号（从高位到低位）都是从0开始，试问4999块对应的字号和位号；129字的29位对应哪一块？
【参考答案】
依题目所给条件，已知位示图如下所示：
0 0 0 1 32 2 255
4999÷32=156,余1。所以4999块对应的字号为156，位号为1。
129字的29位对应的块号为：129*32+29=4157（块），即对应内存的第4157块。
4．某进程，若它对页面的访问串为： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
???设运行开始时，内存中没有属于该进程的页面。当分别用最近最少用（ＬＲＵ）调度算法、先进先出（ＦＩＦＯ）调度算法实现页面更换时，写出相应的淘汰过程并给出各自依次淘汰页及缺页次数。（设允许进程在内存中最多占三个页面）
【参考答案】 LRU更换算法： 是否缺页 内存中包含的页 被淘汰的页 7 * 7 0 * 7 0 1 * 7 0 1 2 * 2 0 1 7 0 3 0 2 0 3 4 * 4 0 3 2 2 * 4 0 2 3 3 * 4 3 2 0 0 * 0 3 2 4 3 0 3 2 2 1 2 1 3 2 0 * 1 0 2 3 1 7 0 1 0 7 1 1 33 2 2 34 ? ? ? ? 31 31 8191 * 2 0 1 2 0 3 * 0 3 2 1 3 2 * 1 0 2 1 0 7 1 0 2 共发生12次缺页，依次淘汰页为：7 1 2 3 0 4 0 3 2 FIFO更换算法： 是否缺页 内存中包含的页 7 * 7 0 * 0 7 1 * 1 0 2 * 2 1 0 2 1 3 * 3 2 0 * 0 3 4 * 4 0 2 * 2 4 3 * 3 2 0 * 0 3 3 0 3 2 0 3 1 * 1 0 2 * 2 1 0 2 1 1 2 1 7 * 7 2 0 * 0 7 被淘汰的页 7 0 7 0 1 0 2 1 3 2 0 3 4 0 2 4 2 2 3 2 0 3 0 0 1 0 2 1 共发生14次缺页，依次淘汰页为：7 0 1 2 3 0 4 2 3 0 1
5．描述采用虚拟页式存储管理机制的系统，当发生缺页中断时系统的处理过程。
【参考答案】
空闲页吗？
页修改过吗？
护现场
择一页淘汰
写回外存修改页表 将该页调入内存，修改页表相应表目 复现场，返回
缺页中断
6．某进程，若它对页面的访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 试用LRU、FIFO两种算法实现页面更换，并给出各自的缺页次数。（设该进程在内存中占四个页架）
【参考答案】
M=4时，采用LRU算法，系统的淘汰过程： 7 0 1 2 0 3 是否缺* * * * * 页： 7 7 7 7 7 3 内存中 0 0 0 0 0 包含的 1 1 1 1 页面： 2 2 2 被淘汰 7 页 即F=8（次缺页）
M=4时，采用FIFO算法，系统的淘汰过程：
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 0 4 * 3 0 1 2 3 0 4 2 1 2 3 0 3 2 1 * 3 0 4 2 3 0 4 2 3 0 4 2 3 0 4 2 3 0 4 2 3 0 1 2 4 2 0 1 7 * 3 0 1 2 3 0 1 2 3 0 1 2 7 0 1 2 3 0 7 0 1 2
