頁(yè)面置換算法

1、頁(yè)面置換算法首先了解頁(yè)面置換算法：在地址映射過程中，若在頁(yè)面中發(fā)現(xiàn)所要訪問的頁(yè)面不在內(nèi)存中，則產(chǎn)生缺頁(yè)中斷。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)必須在內(nèi)存中選擇一個(gè)頁(yè)面將其移除內(nèi)存，以便為即將調(diào)入的頁(yè)面讓出空間。而用來選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法。 1、分類：最佳置換算法（OPT）：所選擇的被淘汰頁(yè)面將是以后永不使用的，或者是最長(zhǎng)時(shí)間內(nèi)不被訪問的頁(yè)面，這樣可以保證獲得最低的缺頁(yè)率。先進(jìn)先出算法（FIFO）：優(yōu)先淘汰最早進(jìn)入的頁(yè)面，也就是在內(nèi)存中停留時(shí)間最長(zhǎng)的頁(yè)面。最近最久未使用算法（LRU）：選擇最近最長(zhǎng)時(shí)間未被訪問過的頁(yè)面進(jìn)行淘汰。最少使用（LFU）置換算法、工作集算法、NRU算法等2、真題解

2、析：某虛擬存儲(chǔ)系統(tǒng)采用最近最少使用（LRU）頁(yè)面淘汰算法。假定系統(tǒng)為每個(gè)作業(yè)分配三個(gè)頁(yè)面的主存空間，其中一個(gè)頁(yè)面用來存放程序。現(xiàn)在某作業(yè)的部分語句如下。Var A:Array1.128,1.128 OF integer;i,j:integer;FOR i:=1 to 128 DO FOR j:=1 to 128 DO Ai,j:=0;設(shè)每個(gè)頁(yè)面可存放128個(gè)整數(shù)變量，變量i、j放在程序頁(yè)中，矩陣A按行序存放。初始時(shí)，程序及變量i、j已在內(nèi)存，其余兩頁(yè)為空。在上面程序片段執(zhí)行過程中，共產(chǎn)生_次缺頁(yè)中斷。最后留在內(nèi)存中的是矩陣A的最后_。解析：系統(tǒng)為每個(gè)作業(yè)分配三個(gè)頁(yè)面的主存控件，其中一個(gè)存放程序

3、，另外兩個(gè)存放的是：二位數(shù)組A128，,128共128行，128列，所以每行都有128個(gè)整型變量。因?yàn)榫仃嘇按行序排列，又因?yàn)橐粋€(gè)頁(yè)面可以存放128個(gè)整數(shù)變量，所以一個(gè)頁(yè)面存放矩陣A中的一行，兩個(gè)頁(yè)面存放矩陣A中的兩行。其用最近最少使用頁(yè)面淘汰算法（淘汰最久未被訪問的頁(yè)面，如1、2行先進(jìn)入頁(yè)面，當(dāng)?shù)谌羞M(jìn)入頁(yè)面的時(shí)候，第一行相對(duì)于第二行就是最久未被訪問的頁(yè)面，所以淘汰第一行，第三行進(jìn)入主存）如下分析行數(shù) 1 23 4 5 . . 128頁(yè)面一 11 3 3 5 . . 頁(yè)面二 2 2 4 4 . .缺頁(yè)（*） * * * * * * * * 128次缺頁(yè) 由以上分析可知，最后留在內(nèi)存中的是矩陣

4、A的最后兩行，因?yàn)槭且恍幸恍械倪M(jìn)入的，而且內(nèi)存中允許兩個(gè)頁(yè)面存在，再有前5行進(jìn)入主存的規(guī)律分析，所以是最后兩行127行和128行。在某計(jì)算機(jī)中，假設(shè)某程序的6個(gè)頁(yè)面如下圖所示，其中某指令“COPY A TO B”跨兩個(gè)頁(yè)面，且源地址A和目標(biāo)地址B所涉及的區(qū)域也跨兩個(gè)頁(yè)面。若地址為A和B的操作數(shù)均不在內(nèi)存，計(jì)算機(jī)執(zhí)行該COPY指令時(shí)，系統(tǒng)將產(chǎn)生_次缺頁(yè)中斷；若系統(tǒng)產(chǎn)生產(chǎn)生三次缺頁(yè)中斷，那么該程序應(yīng)有_個(gè)頁(yè)面在內(nèi)存。解析：如題，系統(tǒng)存在6個(gè)頁(yè)面，12存放指令，36將來要用來存放A的源地址和B的目標(biāo)地址，當(dāng)執(zhí)行指令的時(shí)候，系統(tǒng)會(huì)去訪問A的源地址和B的目標(biāo)地址，因?yàn)锳B本身沒有存在主存中，所以每次訪問

5、的頁(yè)面不在主存中，就會(huì)發(fā)生一次缺頁(yè)中斷。即訪問AB時(shí)，36的頁(yè)面都會(huì)發(fā)生缺頁(yè)中斷，即發(fā)生4次缺頁(yè)中斷。整個(gè)程序中有6個(gè)頁(yè)面，若發(fā)生3次中斷，應(yīng)該就是進(jìn)入主存35頁(yè)面時(shí)發(fā)生了中斷，那時(shí)程序里有35頁(yè)面再內(nèi)存里，即3個(gè)頁(yè)面。設(shè)文件索引節(jié)中有8個(gè)地址項(xiàng)，每個(gè)地址項(xiàng)大小為4字節(jié)，其中5個(gè)地址項(xiàng)為直接地址索引，2個(gè)地址項(xiàng)是一級(jí)間接地址索引，1個(gè)地址項(xiàng)是二級(jí)間接地址索引，磁盤索引塊和磁盤數(shù)據(jù)塊大小均為1KB。若要訪問文件的邏輯塊號(hào)分別為5和518，則系統(tǒng)分別采用_；而且可表示的單個(gè)文件最大長(zhǎng)度是_KB。解析：(1)磁盤索引塊和磁盤數(shù)據(jù)塊的塊長(zhǎng)1024字節(jié)，索引塊號(hào)長(zhǎng)8*4=32字節(jié)，所以一個(gè)索引可以存放1

6、024/32=32個(gè)盤塊號(hào)直接索引可尋址的文件的最大長(zhǎng)度1個(gè)塊（1*1K=5/8KB）因?yàn)榇疟P索引塊的塊長(zhǎng)1024字節(jié)（1個(gè)塊）一級(jí)索引可尋址的文件的最大長(zhǎng)度32個(gè)塊（32*1024B=32KB）二級(jí)索引可尋址的文件的最大長(zhǎng)度N=32*32=1024個(gè)盤塊（1024*1024B=1MB=1024KB）題中是求第5個(gè)塊和518個(gè)塊，分別是一級(jí)間接地址索引（1532+1）和二級(jí)間接地索引(32+15181024+32+1)(2)1024/4=256 1024/32=32個(gè)塊5個(gè)直接地址對(duì)應(yīng)的文件大小5*1=5KB2個(gè)一級(jí)間接地址對(duì)應(yīng)文件大小2*256*1=512KB1個(gè)二級(jí)間接地址對(duì)應(yīng)文件大小1*

7、256*256*1=65536KB單個(gè)文件的最大長(zhǎng)度為：5+512+65536=66053KB可變分區(qū)的請(qǐng)求和釋放分區(qū)主要有如下4種算法。 最佳適應(yīng)算法：選擇等于或接近作業(yè)需求的內(nèi)存自由區(qū)進(jìn)行分配。這種方法可以減少碎片，但同時(shí)也可能帶來更多小得無法再用的碎片。 首次適應(yīng)算法：從主存低地址開始，尋找第一個(gè)可用（即大于等于作業(yè)需求的內(nèi)存）的自由區(qū)。這種方法可實(shí)現(xiàn)快速分配，縮短查找時(shí)間。 最差適應(yīng)法：選擇整個(gè)主存中最大的內(nèi)存自由區(qū)。 循環(huán)首次適應(yīng)算法：是首次適應(yīng)法的一個(gè)變種，也就是不再是每次都從頭開始匹配，而是連續(xù)向下匹配。（2）分頁(yè)存儲(chǔ)管理分成兩部分：其一部分為頁(yè)號(hào)P；后一部分為偏移量W，即頁(yè)內(nèi)地址。途中的地址長(zhǎng)度為32位，其中011位為頁(yè)內(nèi)地址（每頁(yè)的代銷為4KB），1231位為頁(yè)號(hào)，所以允許地址空間的大小最多為1MB個(gè)頁(yè)頁(yè)式存儲(chǔ)管理的地址