請求頁式存儲管理的頁面置換算法(已修改)
2024-11-28 19:59 本頁面
【正文】 請求頁式存儲管理的頁面置換算法 實(shí)驗(yàn)環(huán)境 Linux 實(shí)驗(yàn)內(nèi)容 設(shè)計(jì)一個(gè)虛擬存儲區(qū)和內(nèi)存工作區(qū) ,并使用下列算法計(jì)算頁面失效次數(shù) . （ 1） 進(jìn)先出的算法（ FIFO） （ 2） 最近最少使用的算法（ LRU） （ 3） 最佳淘汰算法 (OPT) 在本實(shí)驗(yàn)中，頁地址流長度為 320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令 所 對應(yīng)的頁不在內(nèi)存的次數(shù)。 算法描述及實(shí)驗(yàn)步驟 實(shí)驗(yàn)步驟 （ 1）通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共 320 條指令。指令的地址按下述原則生成： ① 50%的指令是順序執(zhí)行的； ② 50%的指令是均勻分布在前地址部分； ③ 50%的指令是均勻分布在后地址部分。 具體的實(shí)施方法是： ①在 [0， 319] 的指令之間隨即選取一起點(diǎn) m。 ②順序執(zhí)行一條指令，即執(zhí)行地址為 m+1 的指令； ③在前地址 [0， m+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為 m′； ④順序執(zhí)行一條指令，其地址為 m′ + 1； ⑤在后地址 [m′ + 2， 319]中隨機(jī)選取一條指令并執(zhí)行； ⑥重復(fù)上述步驟① ⑤，直到執(zhí)行 320 次指令。 （ 2）將指令序列變換為頁地址流 設(shè)：①頁面大小為 1k； ②用戶內(nèi)存容量為 4 頁到 32 頁； ③用戶虛存容量為 32k。 在用戶虛存中，按每 k存放 10條指令排在虛存地址，即 320 條指令在虛存中的存放方式為： 第 0 條 第 9 條指令為第 0 頁（對應(yīng)虛存地址為 [0， 9]）； 第 10 條 第 19 條指令為第一頁（對應(yīng)虛存地址為 [10， 19]）； … … 第 310 條 ~第 319 條指令為第 31 頁（對應(yīng)虛地址為 [310， 319]）。 按以上方式，用戶指令可組成 32 頁 。 （ 3）計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的 頁面失效次數(shù) 。 ①先進(jìn)先出的算法（ FIFO）； ②最近最少使用算法（ LRU)； ③最佳淘汰算法（ OPT）先淘汰最不常用的頁地址； 隨機(jī)數(shù)產(chǎn)生辦法， Linux 或 UNIX 系統(tǒng)提供函數(shù) strand()和 rand(),分別進(jìn)行初始化和產(chǎn)生隨機(jī)數(shù)。例如： strand ()。 語句可初始化一個(gè)隨機(jī)數(shù)； a[0]=10*rand()/65535*319+1。 a[1]=10*rand()/65535*a[0]。 語句可用來產(chǎn)生 a[0]與 a[1]中的隨機(jī)數(shù) 實(shí)驗(yàn)指導(dǎo) 本實(shí)驗(yàn)的程序設(shè)計(jì)基本上按照實(shí)驗(yàn)內(nèi)容進(jìn)行。即首先用 srand()和 rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計(jì)算出相應(yīng)的命中率。相關(guān)定義如下： 1 數(shù)據(jù)結(jié)構(gòu) (1)頁面類型 typedef struct{ int pn,pf
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1