页面走向 物理块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，页号 0 1 2 存储块号 2 1 0 加载时间 30 160 10 访问时间 160 157 162 访问位 0 0 1 修改位 2 0 0 其中存入的4个页面的情况如下表 3 3 220 165 1 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 移动问题是：（147-143）+（150-147）+（150-130）+（130-102）+（102-94）+（94-91）+（91-86）+（175-86）+（177-175）＝162
（3）采用扫描算法时，存取臂的移动顺序是：
143、147、150、175、177、130、102、94、91、86 移动问题是：（147-143）+（150-147）+（175-150）+（177-175）+（177-130）+（130-102）+（102-94）+（94-91）+（91-86）＝125
（4）采用循环扫描算法时，存取臂的移动顺序是： 143、147、150、175、177、86、91、94、102、130
移动问题是：（147-143）+（150-147）+（175-150）+（177-175）+（177-86）+（91-86）+（94-91）+（102-94）+（130-102）＝169
7、磁盘的访问时间分成三部分：寻道时间、旋转时间和数据传输时间。而优化磁盘磁道上的信息分布能减少输入/输出服务的时间。例如，有一个文件有10个记录A，B，…，J存放在磁盘的某一磁道上，假定该磁盘共有10个扇区，每个扇区存放一个记录，安排如下表所示。现在要从这个磁道上顺序地将A~J这10个记录读出，如果磁盘的旋转速度为20ms转一周，处理程序每读出一个记录要花4ms进行处理？试问：（1）处理完10个记录的总时间为多少？（2）为了优化分布缩短处理时间，如何安排这些记录？并计算处理的总时间。 扇区号 记录号 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 I 10 J 答：（1）由题目所列条件可知，磁盘的旋转速度为20ms转一周，每个磁道有10个记录，因此读出1个记录的时间为：20ms/10＝2ms。
对于表中记录的初始分布，读出并处理记录A需要2ms+4ms＝6ms。6ms后读/写头已转到了记录D处，为了读出记录B，必须再转8个扇区，即需要8*2ms＝16ms，记录B的读取时间为2ms，处理时间为4ms，故处理记录B共花时间为：16ms+2ms+4ms＝22ms。后续8个记录的读取时间与记录B相同。所以处理10个记录的总时间为：9*22ms+6ms＝204ms。
（2）为了缩短处理时间，按下图安排这些记录。
经优化处理后，读出并处理记录A后，读写头刚好转到记录B的开始处，因此立即可读取并处理记录B，后续记录的读取与处理情况相同。故处理10个记录的总时间为：10*（2ms+4ms）＝60ms。
9 G 8 J 7 C 10 D 1 A 2 H 3 E 4 B 6 F 5 I
8、假设一个磁盘有100个柱面，每个柱面有10个磁头，每个磁道有15个扇区。当进程的要访问磁盘的13524扇区时，计算该扇区在磁盘的第几柱面、第几磁道、第几扇区？
答：由题目可知，磁盘每个柱面有10个磁头，每个磁道有15个扇区。则每个柱面的扇区数为：10*15＝150。13524/150=90余24，故13524所在的柱面为90。24/15＝1余9，故13524所在的磁头号为1，扇区号为9。
9、一个文件记录大小为32B，磁盘输入/输出以磁盘块为单位，一个盘块的大小为512B。当用户进程顺序读文件的各个记录时，计算实际启动磁盘I/O占用整个访问请求的比例。
答：由题目可知，盘块的大小为512B，一个文件记录大小为32B，故一个盘块包含的记录数为：512/32＝16。
显然在访问16个记录中，只需要一次启动磁盘，故实际启动磁盘I/O占用整个访问请求的比例为1/16＝6.25%。
10、如果磁盘扇区的大小固定为512B，每个磁道有80个扇区，一共有4个可用的盘面。假设磁盘旋转速度是360rpm。处理机使用中断驱动方式从磁盘读取数据，每个字节产生一次中断。如果处理中断需要2.5ms，试问：（1）处理花费在处理I/O上的时间占整个磁盘访问时间的百分比是多少（忽略寻道时间）？（2）采用DMA方式，每个扇区产生一次中断，处理花费在处理I/O上的时间占整个磁盘访问时间的百分比又是多少？
答：磁盘旋转一周的时间为60/360＝1/6s。查找一个扇区的平均时间为1/2周，即1/12s。访问一个扇区所需要的时间为：Tt＝b/rN＝1/6*1/80＝1/480s。
（1）处理机使用中断驱动方式从磁盘读取一个盲区，每个字节产生一次中断，如果处理中断需要25在，处理机花费在处理I/O上的时间汇款单整个磁盘访问时间的百分比是：
（512*2.5）/（（1/12+1/480）+（512*2.5））*100%＝99.9%
（2）采用DMA方式，每个扇区产生一次中断，处理机花费在处理I/O上的时间占整个磁盘访问时间的百分比是：
2.5/（（1/12+1/480）+2.5）*100%＝96.7%