在多道程序系统中建议使用局部置换策略。这样，即使某个进程出现了抖动现象，也不致引起其他进程产生抖动，从而将抖动局限在较小范围内。

3、存储存储器的特征是什么？虚拟存储器的容量受到哪两个方面的限制？ 答：虚拟存储器的特征有以下几方面。（1）离散性，指进程不必装入连续的内存空间，而是“见缝插针”。（2）多次性，指一个进程的程序和数据要分多次调入内存。（3）对换性，指进程在运行过程中，允许将部分程序和数据换进、换出。（4）虚拟性，指能从逻辑上扩充内存容量。

虚拟存储器的容量主要受计算机的地址长度和外存容量的限制。

4、已知页面走向是1、2、1、3、1、2、4、2、1、3、4，且进程开始执行时，内存中没有页面，若该进程分配两个物理块，当采用以下算法时的缺页率是多少？（2）先进先出置换算法。（2）假如有一种页面置换算法，它总是淘汰刚使用过的页面。

答：（1）根据题中页面走向，采用先进先出置换算法时的页面调度情况如下表 页面走向 物理块1 物理块2 缺页 1 1 缺 2 1 2 缺 1 3 3 2 缺 1 3 1 缺 2 2 1 缺 4 2 4 缺 2 1 1 4 缺 3 1 3 缺 4 4 3 缺 从表中可看出，页面引用11次，缺页9次，所以缺页率为9/11=81.8%。 （2）根据题中给定页走向，假如有一种页面置换算法，它部是淘汰刚使用过的页面时的页面调度情况如下表 页面走向 物理块1 物理块2 缺页 1 1 缺 2 1 2 缺 1 3 3 2 缺 1 1 2 缺 2 4 1 4 缺 2 1 2 缺 1 3 3 2 缺 4 4 2 缺 从表中可看出，页面引用11次，缺页8次，所以缺页率为8/11=72.7%

5、在请页式存储管理系统中，使用先进先出页面置换算法，会产生一种奇怪的现象，分配给进程的页面数越多，进程执行时的缺页次数反而升高。试举例说明这一现象。

答：如果一个进程的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，若给该进程分配3个物理块，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 缺页 4 4 缺 3 4 3 缺 2 4 3 2 缺 1 1 3 2 缺 4 1 4 2 缺 3 1 4 3 缺 5 5 4 3 缺 4 3 2 5 2 3 缺 1 5 2 1 缺 5 从表中可看出，页面引用12次，缺页9次。

若给该进程分配4个物理块，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 物理块4 缺页 4 4 缺 3 4 3 缺 2 4 3 2 缺 1 1 3 2 1 缺 4 3 5 5 3 2 1 缺 4 5 4 2 1 缺 3 5 4 3 1 缺 2 5 4 3 2 缺 1 1 4 3 2 缺 5 1 5 3 2 缺

从表中可看出，页面引用12次，缺页10次。

由上例可看出，对于以上页面走向，当分配给进程的物理块数从3变成4时，缺页次数不但没有下降，反而从9次增加到10次。

6、某请页式系统中，页的大小为100字，一个程序的大小为1200字，可能的访问序列如下：10、205、110、40、314、432、320、225、80、130、272、420、128（字），若系统采用LRU置换算法，当分配给该进程的物理块数为3时，给出进程驻留的各个页面的变化情况、页面淘汰情况及缺页次数。

答：由于页的大小为100字，因此访问序列10、205、110、40、314、432、320、225、80、130、272、420、128对应的页号是0、2、1、0、3、4、3、2、0、1、2、4、1。给该进程分配3个物理块，采用LRU置换算法，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 缺页 0 0 缺 2 0 2 缺 1 0 2 1 缺 0 3 0 3 1 缺 4 0 3 4 缺 3 2 2 3 4 缺 0 2 3 0 缺 1 2 1 0 缺 2 4 2 1 4 缺 1 从表中可看出，被淘汰的页号分别是2、1、0、4、3、0，共缺页9次。

7、在一个采用局部置换策略的请求页式系统中，分配中给进程的物理块数为4，其中存入的4个页面的情况如下表 页号 0 1 2 3 存储块号 2 1 0 3 加载时间 30 160 10 220 访问时间 160 157 162 165 访问位 0 0 1 1 修改位 2 0 0 1 当发生缺页时，分别采用下列页面置换算法时，将置换哪一页，并解释原因。（1）OPT（最佳）置换算法；（2）FIFO（先进先出）置换算法；（3）LRU（最近最少使用）算法；（4）CLOCK置换算法

答：（1）OPT转换算法是选择永久不用的页或长时间不用的页，将其换出，题目中没有给出页面的将来走向，所以无法判断将转换哪一页。

（2）FIFO转换算法是选择最先装入内存的页面，将其换出。从表中可知，应考察的是页面的加载时间，加载时间最小的是10，此最先装入内存的是第2页。

（3）LRU算法是选择最近最久没有被访问的页面，将其换出。从表中可知，应考察的是页面的访问时间，访问时间最小的是157，应此最近最久没有被访问的页面是第1页。

（4）CLOCK转换算法是LRU算法的变种，它首先选择访问位和修改位均为0的一页，将其换出，从表中可知，满足该条件的是第1页。

8、某虚拟存储器的用户空间有32个页面，每页1KB，内存的大小为16KB，假设某时刻系统为用户的第0、1、2、3页分配的物理块号是5、10、4、7。而该用户进程的长度是6页，试将以下十六进制的虚拟地址转换成物理地址。（1）0A5C；（2）103C；（3）257B；（4）8A4C

答：（1）虚拟地址0A5C的二进制是0000101001011100，由页大小为1KB，可知页号为000010（二进制），即2（十进制），从页表中得到其物理块号为4（十进制），即000100（二进制）。与页内位移1001011100（二进制）拼接得到物理地址为0001001001011100（二进制），即125C（十六进制）。

（2）虚拟地址103C的二进制是0001000000111100，页大小为1KB，可知页号为000100（二进制），即4（十进制），由题目可知，该用户进程的长度是6页，因此页号合法。但页表中没有第4页，说明该页未装入内存，故主生缺页中断。

（3）虚拟地址257B的二进制是0010010101111011，由页大小为1KB，可知页号为001001（二进制），即9（十进制），由题目可知，该用户进程的长度是6页，因此页号非法，产生越界中断。

（4）虚拟地址8A4C的二进制是1000101001001100，由题目可知，用户空间有32个页面，每页1KB，即虚拟地址空间为32KB，而地址1000101001001100超出32KB，因此地址8A4C错误。

9、在请页式存储管理系统中，页面大小是100字节，有一个50*50的数组按行连续存放，每个整数占2字节。将数组初始化的程序如下：

程序A： 程序B： int i,j; int i,j;

int a[50][50]; int a[50][50]; for(i=0;i<50;i++) for(j=0;j<50;j++) for(j=0;j<50;j++) for(i=0;i<50;i++) a[i][j]=0; a[i][j]=0;

若在程序执行过程中内存中只有一个页面用来存放数组的信息，试问程序A和程序B执行时产生的中断次数分别是多少？

答：由题可知，数组a中有50*50＝2500个整数，每个整数占2字节，数组共需要2*2500＝5000字节。而页面的大小是100字节，则数组占用的空间为5000/100＝50页。

对程序A：由于数组是按行存放的，而初始化数组的程序也是按行进行初始化的。因此当缺页后调入一页，位于该页的所有数组元素全部进行初始化，然后再调入另一页。所以缺页的次数为50次。

对程序B：由于数组是按行存放的，而初始化数组的程序却是按列进行初始化的，因此当缺页后调入的一页中，位于该页上的数组元素只有1个。所以程序B每访问1个元素产生一次缺页中断，则访问整个数组将产生2500次缺页。

7 设备管理

1、数据传送控制方式有哪几种？试比较它们的优缺点。

答：数据传送控制方式有程序直接控制方式、中断控制方式、DMA控制方式和通道控制方式。

程序直接控制方式是由用户直接控制数据从CPU（或内存）到外部设备之间的传送，它的优点是控制简单，不需要多少硬件的支持。它的缺点是CPU与外设只能串行工作；多台外设之间也是串行工作；无法发现和处理由于设备和其他硬件所产生的错误。

中断控制方式是通过向CPU发送中断的方式控制外部设备和CPU之间的数据传送。它的优点是大大提高了CPU的利用率且能支持多道程序与外设的并行操作。它的缺点是：由于数据缓冲寄存器较小，数据传送时必然导致中断次数较多，从而占用的大量的CPU时间；当外部设备较多时，由于中断次数的急剧增加，可能导致CPU无法响应中断而出现中断丢失现象。

DMA控制方式是在外部设备和CPU之间开辟直接的数据交换通路进行数据传送。它的优点是除了在数据块传送的开始时需要CPU的启动指令，在整个数据块传送完毕时需要发送中断通知CPU进行中断处理之外，不需要CPU的频繁干预。它的缺点是在外部设备越来越多的情况下，多个DMA控制器的同时使用，会引起内存地址的冲突并使得控制过程进一步复杂化。

通道方式是使用通道来控制CPU（或内存）和外部设备之间的数据传送，即使传送多个数据块，也不必需要CPU的干预。通道是一个独立于CPU的专管输入/输出的处理机，它控制外设与内存直接进行数据交换。它有自己的通道指令，这些指令由CPU启动，并在操作结束时向CPU发中断信号。该方式的优点是进一步减轻了CPU的负担，增强了计算机系统的并行程序，缺点是拉架了额外的硬件，造价昂贵。

2、何谓设备的独立性？如何实现设备的独立性？

答：设备的独立性是指应用程序独立于具体使用的物理设备。此时，用户使用逻辑设备名申请使用某类物理设备。当系统中有多台该类型设备时，系统可将其中的任意一台分配给请求进程，而不局限于某一台指定的设备。这样，可以显著地改善资源的利用率及可适应性。设备独立性使用户程序独立于设备的类型。如进行输出时，既可以使用显示终端，也可以使用打印机。有了这种独立性，就可以很方便地进行输入/输出重定向。

为了实现设备独立性，系统必须将应用程序中使用的逻辑设备名映射为物理设备名。为此，系统应为用户建立逻辑设备表（LUT），用来进行逻辑设备到物理设备的映射，其中每个表目中包含了逻辑设备名、物理设备名和设备驱动程序的入口地址三项。当应用程序使用逻辑设备名请求I/O操作时，系统便可以从LUT

中得到物理设备和驱动程序的入口地址。

3、什么是缓冲？为什么要引入缓冲？操作系统如何实现缓冲技术？

答：缓冲是在两个不同速度的设备之间传输信息时，用于平滑传输过程的一种手段。 在操作系统中引入缓冲的原因主要如下：（1）缓解CPU与I/O设备之间速度不匹配的矛盾；（2）减少中断CPU的次数。（3）提高CPU与I/O设备之间的并行性。

在计算机系统中，除了关键的地方采用少量硬件缓冲之外，大多都采用软缓冲。软缓冲是指在输入/输出操作期间，用来临时存放输入/输出数据的一块区域，这块区域一般在内存中。操作系统把所有用于输入的缓冲区和用于输出的缓冲区统一管理起来，就形成了由若干个大小相同的缓冲区组成，任何进程都可以申请使用缓冲池。缓冲池由操作系统管理，并分为3个队列：空缓冲区队列、装满数据的缓冲区队列和装满输出数据的缓冲区队列。

当输入设备需要输入数据时，从空缓冲区队列上取下一个空缓冲区，待装满输入数据后将其加入输入数据队列。当CPU需要处理输入数据时，就从输入数据队列取下一个数据缓冲区进行数据处理，处理完该缓冲区的数据后又将其加入空缓冲区队列。

当CPU要输出结果时，从空缓冲区队列上取下一个空缓冲区，待装满输出数据后将其加入输出数据队列。当输出设备要输出结果时，从输出数据队列取下一个数据缓冲区进行数据输出，输出完毕再将该缓冲区加入空缓冲区队列。

4、设备分配中为什么可能出现死锁？

答：在某些操作系统中，一个进程只能提出一个I/O请求。也就是说，执行进程向系统提出I/O请求后便立即进入等待状态，直到I/O请求完成后才被唤醒。这样的系统对设备的分配比较安全，不会出现死锁。但这种方式对进程来说，因CPU与I/O设备是串行工作（仅对该进程而言）的，这使得该进程的推进速度缓慢。为了加快进程执行时的推进速度，使CPU与I/O设备对本进程而言能够并行工作，某些操作系统允许进程在发出I/O请求后仍能继续执行，当需要时有可能接着发出第二个、第三个I/O请求，仅当所请求的I/O设备已被另一个进程占用时，进程才进入等待状态。这种一个进程同时可使用多个I/O设备的方式提高了系统的资源利用率，但也带来了一种危险，即如果两个进程都提出请求使用对方已占有的I/O设备时，就会出现死锁。

5、以打印机为例说明SPOOLing技术的工作原理。

答：当用户进程请求打印输出时，操作系统接收用户的打印请求，但并不真正把打印机分配给该用户进程，而是为进程在磁盘上的输出井中分配一空闲盘块区，并将要打印的数据送入其中，同时还为用户进程申请一张用户请求打印表，将用户的打印要求填入其中，再将该表挂在请求打印队列上。如果还有进程要求打印输出，系统仍可以接受请求，也为进程完成上述操作。

如果打印机空闲，输出进程将从请求打印队列中队首取出一张请求打印表，根据表中的要求将要打印的数据从输出井传送到内存的输出缓冲区，再由打印机进行打印。打印完毕后，输出进程再查看打印请求队列中是否还有请求打印表，若有，则再取一张请求打印表，并根据其中的打印要求进行打印，如此反复，直到打印请求队列空为止，输出进程才将自己阻塞起来，直到下次再有打印请求时才被唤醒。

6、假设一个磁盘有200个柱面，编号为0~199，当前存取臂的位置是143号柱面上，并刚刚完成了125号柱面的服务请求，如果存在以下的请求序列86、147、91、177、94、150、102、175、130，试问：为完成上述请求，下列算法存取臂的移动顺序是什么？移动问题是多少？（1）先来先服务（FCFS）；（2）最短寻道时间优先（SSTF）；（3）扫描算法（SCAN）；（4）循环扫描算法（CSCAN）

答：（1）采用先来先服务算法时，存取臂的移动顺序是： 143、86、147、91、177、94、150、102、175、130 移动问题是：（143-86）+（147-86）+（147-91）+（177-91）+（147-94）+（150-94）+（150-102）+（175-102）+（175-130）＝565

（2）采用最短寻道时间优先时，存取臂的移动顺序是： 143、147、150、130、102、94、91、86、175、177