操作系统课件前四章作业答案

第四章存储管理4.1存储管理的基本概念4.2早期的存储管理4.3分页存储管理4.4请求分页存储管理4.5分段存储管理4.6段页式存储管理4.7WindowsNT虚拟内存管理4.1存储管理的基本概念4.1.1存储管理研究的四个问题(1)存储分配问题=存储器被多个进程共享的问题。重点是研究如何对进程分配存储器空间的算法。处理器共享通过在时间上的划分来实现，而存储器共享通过在空间上的划分来实现。

(2)装配模块的地址再定位问题。研究各种地址变换机构，以及静态和动态再定位方法。

(3)存储保护问题。研究保护各类程序、数据区的方法。

(4)存储扩充问题。主要研究虚拟存储器问题及其各种调度算法。4.1.2地址再定位1.地址空间和存储空间

装配模块

源程序

进程编译，链接加载符号指令变量类型高级语言结构二进制指令对存储空间的引用字节大小以及排列方式变成顺序结构装配模块内容+进程环境Transform内存管理：Transform：LASpace->PASpace2.地址定位发生的时态时间程序设计时或叫做编写程序时编译或汇编时加载模块产生时加载时运行时2.地址的静态再定位，发生在加载时

LoaderLoaderTransform：LA->LA+AllocationStartAddress动态地址再定位——发生在运行时

Transform：LA->LA+[BR]如果LA+[BR]<[BR]+[LR]，则地址访问时安全的静态再定位与动态再定位的区别Load1,500123450100500…………Load1,150012345100011001500…………StartAddress=1000静态Load1,500123450100500…………Load1,50012345100011001500…………[BR]=1000动态在加载时解析地址在运行时解析地址Load1,500123450100500…………Load1,50012345100011001500…………[BR]=1000动态Load1,50012345200021002500…………[BR]=2000程序能否在内存中移动程序在存储空间中是否连续存储是否有利于程序共享执行效率应用领域静态不能。除非再装载一次，这对已经开始运行的程序不可行需要不利于高。因为物理地址是在装载时得到解析的，因此执行每条指令时，不需要再解析嵌入式控制器，DSP，Cray超级计算机动态可以。只需修改寄存器BR的内容即可不需要。为每个分散的内存区域增加一对<基址-限长>寄存器利于低。因为物理地址是在运行中边解析边执行，但是可以通过硬件来加速PC，服务器静态地址再定位与动态地址在定位比较4.1.3虚拟存储器概念的引入

虚拟存储器的基本思想是把作业地址空间和实际主存的存储空间，视为两个不同的概念。一个计算机系统为程序员提供了一个足够大的地址空间，而完全不必考虑实际主存的大小。由此，可以引出虚拟存储器更一般的概念，即把系统提供的这个地址空间，想象成有一个存储器(虚存)与之对应，正像存储空间有一个主存与之对应一样。这就是说，虚拟存储器实际上是一个地址空间。

根据地址空间结构不同，虚拟存储器有两种形式。一种是单段式虚存，它是一个连续的线性地址空间，其地址顺序为：0，1，2，…，n-1。其中n=2k,k为CPU给出的有效地址的长度。另一种是多段式虚存，它是把地址空间分成若干段，而每一段Si是一个连续的线性地址空间。每个地址可用［Si,W］来表示，Si为段名或段号，W为段内的相对地址。VA=Bi+W私有用户地址空间（程序、数据）用户栈进程控制信息处理器状态信息进程标识符共享地址空间Linux进程的虚拟地址空间0x080480000xffffffffVAS=2^32=4GCPUMMUVAMemoryPACPUchip动态地址再定位4.2早期的存储管理4.2.1单一连续分配图4.4单一连续分配特点：

单道处理系统

作业起始地址固定

内存资源和处理器

没有得到充分使用

作业需要的内存>

物理内存时，

作业无法运行4.2.2分区分配特点：

分区大小固定，不能改变

当存在一个分区：状态=“未用”/\capacity>RequiredMemory

则分配给作业，否则作业不能运行

内存资源利用率低表4–1固定式分区举例分区号分区容量作业容量剩余容量123458KB32KB32KB120KB520KB1KB9KB9KB33KB121KB7KB23KB23KB87KB399KB合计712KB173KB539KB2.可变式分区法图4.6可变式分区的例子合并表4-2(a)已分配的分区状态表分区号分区容量分区位置状态123458KB32KB120KB321KB320KB384KB已分配已分配空项已分配空项分区号分区容量分区位置状态1232KB520KB352KB504KB可用可用表4-2(b)未分配的分区状态表判断空白区是否可用判断空白区大小是否满足要求修改内存分配状态图4.8可变式分区中释放一个分区的流程可变式分区分配法分配分区的算法当有多个空白区都可以满足作业内存需求时，究竟该选择哪个分区予以分配？有如下几种策略

最佳适应算法（BestFit）min{xi|xi>RM}

其中xi是分区的容量，RM是作业请求内存分配的大小

最差适应算法（WorstFit）max{xi|xi>RM}

最先适应算法（FirstFit）{xi|startaddressofxiismin/\xi>RM}3.可再定位式分区分配图4.9可再定位式分区分配的靠拢过程图4.10利用浮动寄存器进行地址变换图4.11可再定位式分区分配算法流程没有足够空白区时再靠拢4.多重分区分配

如果我们不想采用靠拢的办法，又想使存储器分区的碎片问题适当地得到解决，那么可以采用多重分区分配方案。通常一个作业由一些相对独立的程序段和数据段组成，如主程序、子程序、数据组等。这些程序段中的每一个在逻辑上必须是连续的，但是相应的各分区却不要求是连续的，只要有足够的保护措施就可以了。例如一个要求100KB存储空间的作业，实际上由五个20KB的段组成时，则可以分配给该作业一个100KB的分区或者五个20KB的分区，或者两个40KB的分区和一个20KB的分区等等。这种给一个作业分配一个以上分区的方法，称为多重分区分配。采用这种方法时，作业可以在其执行期间申请附加的分区。5.分区的保护措施图4.12分区的界地址寄存器保护分区保护的特点：

在运行过程中，每次访问存储器

时进行越界检查

只需要一组寄存器组就可以6.分区分配方案的评价分区分配方案的主要优点可归纳如下：

(1)实现了主存的共享，因而有助于多道程序设计，更有效地利用了处理机和I/O设备，从而使系统的吞吐量和作业周转时间得到了相应的改善。至于主存利用率，可变式分区比固定式分区高些，可再定位式分区则更高些。

(2)相对于后面介绍的存储管理方式，本方案为实现分区分配所使用的表格、占用的存储容量相对较少，算法也相对简单。

(3)实现存储保护的措施也比较简单。

(4)多重分区分配方案能实现对子程序、数据段的共享。

分区分配的主要缺点有：

(1)主存仍不能充分利用，除了可再定位式分区法外，都存在着严重的碎片问题。另外，即使不把存储器分碎，整个空白区也可能因容纳不下一个作业而造成浪费。例如，有156KB的存储空间可用，而某个作业序列是由100KB和60KB的作业组成的。如果分配了一个100KB的分区后，则剩下的56KB存储空间就要浪费掉。(2)不能实现对主存的扩充。因此，作业的大小受到主存可用空间的限制。

(3)和单一连续分配一样，要求一个作业在执行之前必须全部装入主存，因此在主存中可能包含从未使用过的信息。

(4)采用靠拢方法，虽然能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。

(5)除多重分区外，几个共行作业之间不能共享存入主存的单一信息副本(如公用子程序、数据段等)。回顾1、可执行文件（装载模块）三个地址空间Load1,500123450100…………500Load1,50012345…………磁盘空间逻辑(相对)地址空间Load1,50012345x100+x…………500+x物理地址空间<磁碟号,磁道号,起始单元>所有地址从程序入口地址开始编号程序在内存中占据的地址空间映射映射回顾2、静态再定位和动态在定位Load1,500123450100Jmp400……500Load1,500+x12345x100+xJmp400+x……500+x静态定位发生在装载时一旦装载，程序不能再浮动，否则会出现地址引用错乱400400+xLoad1,500123450100Jmp400……500Load1,50012345x100+xJmp400……500+x动态定位发生在某条代码执行时，当这条代码引用了某个地址时，才进行地址的定位400400+xJmp400得到逻辑地址400再定位寄存器x+400+x物理地址当运行这条指令时，才进行逻辑地址到物理地址的转换4.3分页存储管理4.3.1分页原理解决作业的内存空间必须连续的问题…………进程地址空间(3K+10)B0kB1kB2kB3kBP0P1P2P3OSOS内存地址空间B0B1B2B3B4B5B6B7B8B9PMTP0->B3P1->B4P2->B6P3->B810分页管理的特点：1、页面的大小是固定的，通常是2^k，如256B，1KB，4KB2、内存块的大小=页面的大小3、连续页所分配的块不需要连续分页管理的优点：1、内存碎片小。内存碎片只能发生在分配给进程地址空间的最后一页的内存块中，而块的大小通常很小，因此可以想象碎片也很小。2、不用浮动程序的内存空间就可以实现空闲空间的利用。因为只要内存中有空闲块，无论这些块是否相邻，总可以进行分配。当然，付出的代价是需要建立一个PMT。分页管理需要付出的代价1、维护大页表需要一定的内存空间。2、逻辑地址到物理地址的转换更复杂。【例子】设某进程地址空间大小为16MB。页面大小为1KB。问保存该进程的页表需要多大内存空间？（1）16MB的程序可以划分出：2^{24}/2^{10}=2^12个页面（2）要编码2^12个页面，至少需要12bits（3）考虑到字节对齐，保存12bits需要2Bytes，也就是用2Bytes

保存一个页面编号（4）共需要2^12X2Bytes=2^{13}Bytes=8KB分页管理的关键——地址转换：LAddr->PAddr步骤：（1）把逻辑地址LAddr分解为形式：<PageNum,offset>

假定pagesize=1KB，那么：400=><0,400>1024=><1,0>2049=><2,1>PageNum=[LAddr/Pagesize]offset=LAddrmodPagesize分页管理的关键——地址转换步骤：（2）查PMT表，把PageNum映射到BlockNum。一般通过硬件实现。（3）通过BlockNum和offset构造物理地址PAddr：PAddr=BlockNum*Blocksize+offset【例子】假定pagesize=blocksize=1KB。页表如下。求逻辑地址2049转换的物理地址？2049=><2,1>Page2对应Block66*1kB+1=6145031526310PMT地址转换的硬件实现上面的地址转换需要使用算法除法和乘法，比较复杂。实际上采用二进制表示页号和块号时，这个转换很容易。【定理】对于一个

n位的逻辑地址，假如页面的大小为2^{k}，则高(n-k)位表示该逻辑地址所在的页号，低k

位表示该逻辑地址的页面偏移量。nkn-koffsetPageNum逻辑地址低位高位地址转换过程：offsetPageNum逻辑地址PMT：PageNum->BlockNum查表offsetBlockNum物理地址【例子】用24位表示一个逻辑地址，pagesize=4KB。求地址0000,0000,0010,0000,1001,0000的页号和页内偏移地址。【解答】因为4KB=2^{12}B，因此表示2^{12}个页内偏移地址需要12位。0000,0000,0010,0000,1001,0000PageNum=2Offset=144剩下的问题：如何高效的查页表？1、页表保存在内存中还是寄存器中？2、页表要不要与进程关联？页表地址寄存器页表与进程的关系：1、页表的生命周期：页表随着进程程序和数据的装载而建立，随着进程的消亡而消亡。因此LifeCycle(PMT)<=LifeCycle(Process)2、在进程的不同生命周期中，页表的内容可能不同。3、进程需要保存页表的起始位置，否则进程在执行时就无法通过查PMT表来进行物理地址的解析（定位）。4、页表起始地址通常保存在进程的PCB中。当该进程被调度执行时，取出页表起始地址，放入PMTAR寄存器，加快页表访问速度。页表访问的加速1、高速页面变换寄存器2、联想存储器（快表）

3.联想存储器图4.17利用联想存储器加速查表快表：容量较小的存储器，保存最近常用的页面映射。PMT的一个高速缓存表。最后一个问题：页面管理的整个流程——进程内存分配算法如何记录进程内存分配状态？进程表：记录进程的页表长度和页表起始地址

PMT：进程页面的分配状态MBT：内存块的分配状态在页面分配过程中，算法需要改变这三个表的状态图4.19分页存储分配算法流程创建PMT实际分配4.3.4分页存储管理方案的评价(1)采用动态地址变换会增加计算机成本和降低处理机的速度。

(2)各种表格要占用一定容量的主存空间，而且还要花费一部分处理机时间用来建立和管理这些表格。

(3)虽然说碎片消除了，但每个作业的最后一页一般都有不能充分利用的空白区。

(4)存储扩充问题仍未得到解决。单一连续分配只适用于单道作业处理固定分区法为了让多个作业共享内存可变分区法限制了作业的个数内存浪费严重已分配分区状态表未分配分区状态表可再定位式分区法程序一旦装载，不可再移动碎片过多通过重新定位程序，把碎片连成整片内存由于程序在装载后重新移动了位置，因此在装载时解析逻辑地址已不可能，因此必须依赖动态再定位技术的辅助分页存储管理程序可在装载后重新定位和移动程序必须连续程序可以不连续存储BestfitWorstfitFirstfit非连续存储PMT，PMTAR的支持动态地址变换机构硬件联想存储器进程结构（地址空间）与分页存储管理的关系程序段数据段堆栈内核代码，数据PCB，内核栈等0x080480000x00000000程序PMT进程P1虚拟地址空间0xFFFFFFFF程序私有地址空间程序间共享地址空间PMTAR程序段数据段堆栈内核代码，数据PCB，内核栈等进程P2虚拟地址空间物理内存PMT4.4请求分页存储管理4.4.1请求分页原理前面的内存管理方法都是以程序和数据的完全装载为前提的，但是有时物理内存不足以满足多个进程的完全装载，这时就要通过把页面换入和换出物理内存内存来实现。这样从用户来看，就好像内存能够存放比它的物理大小大得多的程序，这就是存储器的扩充。解决存储器扩充问题请求分页机制（DemandPaging）预取分页机制（Prepaging）为实现请求分页机制，我们需要先解决几个问题：

能不能先把部分页面载入内存，让程序运行起来？

在程序运行时，如何判断某条指令或数据所在的页没有

被载入内存？

当某条指令或数据所在的页没有被载入内存时，采用什么机制

把该页载入内存？

当把新页载入内存，而内存不够用时，需要换出一部分页面，

这时，被换出的页面是被简单的覆盖还是需要回写磁盘？当把新页载入内存，而内存不够用时，需要换出的页面是在分配给当前进程中挑选，还是在整个内存中挑选？

挑选被换出页面的策略是什么？

1、能不能先把部分页面载入内存，让程序运行起来？——程序的“局部性”原理使得上述问题的回答是肯定的局部性空间局部性：程序在不久的将来需要访问的内存单元与当前正在访问的内存单元具有簇聚性时间局部性：程序当前正在访问的内存单元在不久的将来又会被重复访问到。局部性原理指示：一旦一个页面被载入内存，程序的执行在很大程度上会一直访问该页，从而使得程序执行会持续一段时间，不会产生频繁缺页的状况。2、在程序运行时，如何判断某条指令或数据所在的页没有

被载入内存？方案一、维护部分页表，该页表中只包括那些已被映射到内存中

的页号方案二、维护全部页表，通过增加一个标志位来指示该页

是否已被映射3、当某条指令或数据所在的页没有被载入内存时，采用什么机制把该页载入内存？进程P缺页中断Block操作系统把进程P的状态从Run->Block请求I/O通道完成磁盘文件到内存块的

数据传输3.调度其它就绪进程并执行等待当页面装载完毕时，产生一个中断，OS在处理这个中断时，发现P正在等待这个事件的发生，于是将P从Block->Ready。如果P被调度，则从Ready->Run，这样得以继续运行下去。这里一个遗留问题是：如何建立磁盘文件块与页面之间的关系？表4-3(b)辅助页表虚页号辅存地址保护信息4、当把新页载入内存，而内存不够用时，需要换出一部分页面，这时，被换出的页面是被简单的覆盖还是需要回写磁盘？Pagen内存块PagemPagen磁盘块回写辅助页表表4-3(a)扩充后的PMT表虚页号主存块号改变位引进位状态位辅存地址标识该页面是否被修改过标识该页面是否被映射到内存该页面在外存介质中的物理位置5、当把新页载入内存，而内存不够用时，需要换出的页面是在分配给当前进程中挑选，还是在整个内存中挑选？OSOS进程1.P0B0B1B2B3B4B5B6B7B8B9进程1.P1进程1.P2进程2.P0进程2.P1进程2.P2进程2.P3进程3.P0进程2.P4请求分配置换范围局部置换全局置换6、置换策略问题——FIFO,LRU

例1

设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=3，置换算法采用FIFO，则缺页中断次数及缺页率按表4-4给出。表4-4FIFO性能分析例(M=3)

例3

设页面走向如上，M=3，置换算法为LRU，则系统模型如表4-6所示。在表4-6中，由于采用LRU算法，M中各列按访问的时间顺序排列，最近被访问的页面在最前。由表4-6算出缺页中断次数F=10，缺页率f=10/12=83%。表4-6LRU性能分析例(M=3)内存大小与缺页中断次数的关系图4.26存储容量与缺页中断次数的关系不同置换策略与内存大小的关系表4-4FIFO性能分析例(M=3,4)表4-6LRU性能分析例(M=3，4)

由表4-6，表4-7可得如下事实：设G(P,M,t)表示当页面走向为P，主存容量为M，在时刻t的页面集合，对于LRU算法，存在如下关系，即成立。即对于任何时刻t(t=1,2,…,12),G(P,M,t)所选中的页号必定包含在G(P,M+1,t)之中。这种关系说明了增加主存容量不会增加缺页中断次数，然而对FIFO算法，此关系并不成立。图4.21缺页中断的发生及其处理4.4.4请求分页存储管理方案的评价(1)它提供了大容量的多个虚拟存储器，作业地址空间不再受实存容量的限制；

(2)更有效地利用了主存，一个作业的地址空间不必全部同时都装入主存，只装入其必要部分，其它部分根据请求装入，或者根本就不装入(如错误处理程序等)；

(3)更加有利于多道程序的运行，从而提高了系统效率；

(4)方便了用户，特别是大作业用户。

但请求分页还存在以下缺点：

(1)为处理缺页中断，增加了处理机时间的开销，即请求分页系统是用时间的代价换取了空间的扩大；

(2)可能因作业地址空间过大或多道程序道数过多以及其它原因而造成系统抖动；

(3)为防止系统抖动所采取的各种措施会增加系统的复杂性。作业：P1352,3,13,21,224.5分段存储管理细分用户程序的方案分页（paging）分段采用分段技术，可以把程序和其相关的数据划分到几个段中。值得注意的是：分段是程序设计语言提供给程序员的一种组织程序和数据的手段。在FORTRAN等语言中有对段的支持，但在C语言中没有段的概念。大小是否固定是否对程序员透明是否需要连续存储表示逻辑地址的方法分页是是不需要<页号，页内偏移>分段否否不需要<段号，段内偏移>分页与分段的比较4.5分段存储管理4.5.1分段原理图4.27分段管理概念图逻辑地址到物理地址的映射：LA->PAoffsetSegmentNum（1）LA:mn（2）查段表，得到对应段号的内存起始地址start（3）PA=start+offset【例子】在上图中，指令L1，[A]|6中引用了地址[A]|6中的数据。在那样的段表下，求逻辑地址[A]|6的物理地址。1、数组段A的段号为5,地址[A]|6的偏移量是62、在SMT中，对应A的起始地址为38003、因此，逻辑地址[A]|6对应的物理地址为3800+6=3806图4.28段式地址变换过程4.5.3分段存储管理方案的评价分段管理的优点如下：消除了碎片。(2)提供了大容量的虚存。(3)允许动态增加段的长度。因为(4)便于动态装入和链接。(5)便于共享。当两个或两个以上的作业要使用同一子程序时，在实存上就要有两个或两个以上的程序副本，这样一来，实存的地址空间就可能被这些共用的子程序或标准应用程序所塞满。

(6)便于实现存储保护。图4.29两个作业对SQRT的共享

分段存储管理的缺点有：

(1)进行地址变换和实现靠拢操作要花费处理机时间，为管理各分段，要设立若干表格，提供附加的存储空间；

(2)在辅存上管理可变长度的段比较困难；

(3)段的最大长度受到实存容量的限制；

(4)会出现系统抖动现象。4.6段页式存储管理4.6.1段页式存储管理的实现

在段页存储管理系统中，处理机给出的有效地址被划分为三部分：段号、页号和页内地址。在某计算机系统中，24位有效地址的划分是：段号S页号P页内地址W0781516192031

处理机给出的有效地址长度确定了作业地址空间的范围。换言之，它确定了虚存的容量。一个具体的地址结构，确定了一个作业最多能有几段，每段最多能有几页以及每页的大小。上述的24位有效地址确定了虚存的容量为16MB。8位的段号确定了一个作业地址空间最多有256个段，段号为0～255，每个段最多为16页，页号为0～15，每页的大小为4KB。

现在假定有一个作业，它有三段：第0段段长为15KB，占4页(最后一页有1KB未用)；第1段为8KB，占2页；第2段为10KB，占3页(最后2KB未用)。该作业的地址空间如图4.30所示。图4.30段页式管理的作业地址空间例

程序的分段，可由程序员或编译程序按信息的逻辑结构来划分，而分页与程序员无关，它是由操作系统自动完成的。这就是说，程序员所使用的编址方式或编译程序给出的目标程序其地址形式仍是二维的，即(S，W′)，其中S为段号，W′为段内地址。而段内地址W′则由地址变换机构把W′的高4位解释为页号P，把低12位解释为页内地址W。对主存而言，和分页管理一样，划分为许多和页面大小相等的存储块(也称为实页)。因此，一个段可装入不连续的存储块中，于是就用不着再用靠拢的办法来消除碎片了。通常把超出页面大小的碎片称为外碎片(或大碎片)，而小于页面大小的碎片称为内碎片(或小碎片)。图4.31地址变换中所用表格的关系图4.32段页式系统地址变换过程4.6.2段页式存储管理的评价段页存储管理方案保留了分段存储管理和请求分页存储管理的全部优点。其主要优点是它提供了大量的虚存空间，能有效地利用主存，为组织多道程序运行提供了方便。当然，段页存储管理也有缺点，主要缺点是增加了硬件成本、系统的复杂性和管理上的开销；页面使用不充分(和请求分页一样，存在着内碎片)；各种表格(如SMT、PMT等)占用主存空间；存在着系统发生抖动的危险。4.7WindowsNT虚拟内存管理4.7.1进程的虚拟地址空间图4.33虚拟地址空间4.7.2虚拟存储的实现图4.34二级页表地址变换结构图4.35地址变换过程举例我们计算一下，分页管理和分级页管理下，页表所占内存大小。在分页管理下，一个进程的虚拟空间共需要2^{32}/2^{12}=2^{20}=1M个页表项，假定用一个word（即4Bytes）保存一个页表项，那么共需4MB来保存一个页表。

在分级页管理下，一个进程的虚拟空间被分为一个页目录，其中包含1K个页目录项，每个页目录项包括1K个页表。这样保存页目录需要1K*4B=4KB，保存页表需要1K*1K*4B=4MB所以共需4KB+4MB。

尽管分级页管理保存页目录和页表的内存大于分页管理的页表内存，但是搜索效率得到了提高：O(1K)+O(1K)<<O(1M)

采用两级页表的缺点是降低了访问主存的速度。因为每进行一次地址变换要有三次访问主存：查页目录访问一次，查页表访问一次，到主存中存取目标数据又访问一次。但实际上WindowsNT的访问主存速度并不慢，相对来说还比较快，这主要是因为它采取了如下两个措施：

(1)使用快表，即使用联想存储器加快了查表速度，在WindowsNT中称其为变换查找缓冲区TLB。

(2)使用高速缓冲存储器cache，在处理机和主存间设置了32KB或64KB的高速缓冲存储器，大部分的指令和数据取自高速缓存(命中率达98%)，所以存取数据和指令速度相当快，与处理机的速度完全匹配。

2.页面调度页面调度策略包括取页、置页和淘汰策略。

WindowsNT的取页策略分为两种，一种是按进程需要的“请求取页”，另一种是提前取页。前一种方法是在请求分页存储管理中普遍采用的方法，而后一种是WindowsNT所独有的，采取集群方法把一些页面提前装入主存。集群方法提前取页的意思是，当一个线程在发生缺页时，不仅把它需要的那一页装入主存，而且还把该页附近的一些页也一起装入。这样做的主要依据就是程序行为的局部性。因此采取提前装入取页会减少缺页次数，尤其在一个线程开始执行时，请求取页会造成频繁缺页，降低系统的性能。

置页策略是指把虚页放入主存的哪个页帧，这个问题在线性存储结构中比较简单，只要找到一个未分配的页帧即可。置换(淘汰)策略，是为每个进程分配一个固定数量的页面(但可动态调整这个数量)，当发生缺页中断时，从本进程的范围内进行替换。在WindowsNT中采用了局部置换策略。WindowsNT采用先进先出(FIFO)页面置换算法，即把在主存中驻留时间最长的页面淘汰出去，采用这种方法的出发点是算法实现简单。第一章作业：T6ABCI/O30A:10101050B:30201020C:40第一种情况：A，B，C共用一个I/O10T=190ms第一章作业：T6ABCI/O130A:10101050B:302020C:40第二种情况：A，B，C拥有不同I/OI/O2T=180msABCI/O130A:10101050B:302020C:40假如考虑调度器调度时间I/O2T=msSched10ABCI/O130A:10101050B:302020C:40假如考虑调度器调度时间I/O2T=msSched10问题：1、调度程序的执行通常发生在什么时刻？调度程序的执行是怎样触发的？2、下图中，在什么时段系统状态是：<Exit,Block,Block>第二章补充题：给定一组作业J1,J2,…,Jn，其执行时间依次为R1,R2,…,Rn。假定这些作业同时到达，并且在同一台处理机上按单道方式执行。试证明：按最短作业优先算法调度时，其平均周转时间最短。假定按照J1,J2,…,Jn的顺序来调度，则周转时间为：T1=R1T2=T1+R2=R1+R2T3=T2+R3=R1+R2+R3……Tn=Tn-1+Rn=R1+R2+…+Rn-1+Rn总周转时间：T=Sigma_{i=1,…,n}Ti=nR1+(n-1)R2+(n-2)R3+…+2Rn-1+Rn=平均周转时间：第三章作业：T12LOCK：while(w==1)skip;w:=1;UNLOCK:w:=0;要点：1、从进程调度和状态变化方面来说明。2、与P，V操作进行对比CriticalregionP1P2CPULOCKP1P2第三章作业：T12LOCK：while(w==1)skip;w:=1;UNLOCK:w:=0;要点：1、从进程调度和状态变化方面来说明。2、与P，V操作进行对比CriticalregionP1P2CPULOCKP1P2>第三章作业：T231、如果每次只允许一个进程进入互斥段，信号量初值为1，变化

范围是1,0,-1,…,-(n-1)，即[1-n,1]2、如果最多允许m（m<n）个进程同时进入互斥段，信号量初值

为m，变化范围是：m,m-1,…,0,-1,…,-(n-m)思考：在第（2）问中，当信号量值是-(n-m)时，这些进程分别处于什么状态？第三章作业：T24为描述读者的动作，需要编写三个程序：实现登记操作Checkin()实现进入阅览室之后的阅读操作Read()实现读者离开时的注销动作Checkout()。如果阅览室最多允许n个读者进入的话，那么就会为每一个读者i创建一个进程Pi，每个进程按照Pi：Checkin();Read();Checkout()的次序依次顺序三个程序执行。这里存在的并发问题主要有：最多只能允许n个读者（即n个进程）进入阅览室（即关键区）每个读者在进行Checkin和Checkout时对于登记表关键区必须互斥。为此，我们有如下算法：SemaphoreSn:=100;//最多只允许n个读者进入阅览室SemphoreS:=0;//Checkin之间，Checkout之间以及//Checkin和Checkout之间互斥Algorithm：foreachreaderintendingtoenterreading-roomcreateaprocess{P(Sn);P(S);Checkin();V(S);Read();P(S);Checkout();V(S);V(Sn);}//foreachreaderproc