【文章內(nèi)容簡介】 還未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果 4個內(nèi)存塊均已裝入該作業(yè)，則需進(jìn)行頁面置換，最后顯示其物理地址，并轉(zhuǎn)下一條指令。 在所有 320 指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。 3） 置換算法： 最佳置換 （ OPT）算法。 提示 : （ 1）通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共 320條指令。指令的地址按下述 原則生成： ① 50%的指令是順序執(zhí)行的； ② 25%的指令是均勻分布在前地址部分； ③ 25%的指令是均勻分布在后地址部分； 具體的實施方法是： ① 在 [0， 319]的指令地址之間隨機(jī)選取一起點 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條指令為第 1頁（對應(yīng)虛存地址為 [10， 19]）； ?? ?? 13 第 310 條～第 319 條指令為第 31 頁（對應(yīng)虛存地址為 [310， 319]）。 按以上方式，用戶指令可組成 32 頁。 （ 3）計算 最佳置換 （ OPT） 算法在不同內(nèi)存容量下的命中率。 其中，命中率 =1頁面失 效次數(shù) /頁地址流長度 題目十六： 請求調(diào)頁存儲管理方式的模擬 4 1．設(shè)計 目的 通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實現(xiàn)過程的理解。 2．設(shè)計 內(nèi)容 1） 假設(shè)每個頁面中可存放 10 條指令，分配給作業(yè)的內(nèi)存塊數(shù)為 4。 2） 用 C 語言模擬一個作業(yè)的執(zhí)行過程，該作業(yè)共有 320 條指令，即它的地址空間為 32 頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，并將 相應(yīng)頁調(diào)入內(nèi)存。如果 4個內(nèi)存塊均已裝入該作業(yè)，則需進(jìn)行頁面置換，最后顯示其物理地址，并轉(zhuǎn)下一條指令。 在所有 320 指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。 3） 置換算法： 最少訪問 （ LFU）算法。 提示 : （ 1）通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共 320條指令。指令的地址按下述原則生成： ① 50%的指令是順序執(zhí)行的； ② 25%的指令是均勻分布在前地址部分； ③ 25%的指令是均勻分布在后地址部分； 具體的實施方法是： ① 在 [0， 319]的指令地址之間隨機(jī)選取一起點 m； ② 順序 執(zhí)行一條指令，即執(zhí)行地址為 m+1的指令； ③ 在前地址 [0， m+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為 m′ ； ④ 順序執(zhí)行一條指令，其地址為 m′ +1 的指令； ⑤ 在后地址 [m′ +2， 319]中隨機(jī)選取一條指令并執(zhí)行； ⑥ 重復(fù)上述步驟①～⑤，直到執(zhí)行 320 次指令。 （ 2）將指令序列變換為頁地址流 14 ① 設(shè)頁面大小為 1K； ② 用戶內(nèi)存容量為 4頁到 32 頁； ③ 用戶虛存容里為 32K。 在用戶虛存中，按每 K 存放 10條指令排列虛存地址，即 320 條指令在虛存中的存放方式為： 第 0 條～第 9 條指令為第 0 頁（對應(yīng)虛存 地址為 [0， 9]）； 第 10 條～第 19條指令為第 1頁（對應(yīng)虛存地址為 [10， 19]）； ?? ?? 第 310 條～第 319 條指令為第 31 頁（對應(yīng)虛存地址為 [310， 319]）。 按以上方式，用戶指令可組成 32 頁。 （ 3）計算 最少訪問 （ LFU） 算法在不同內(nèi)存容量下的命中率。 其中，命中率 =1頁面失效次數(shù) /頁地址流長度 題目十七： 請求調(diào)頁存儲管理方式的模擬 5 1．設(shè)計 目的 通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實現(xiàn)過程的理解。 2．設(shè)計 內(nèi)容 1） 假設(shè)每個頁面中可存 放 10 條指令，分配給作業(yè)的內(nèi)存塊數(shù)為 4。 2） 用 C 語言模擬一個作業(yè)的執(zhí)行過程，該作業(yè)共有 320 條指令，即它的地址空間為 32 頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果 4個內(nèi)存塊均已裝入該作業(yè)，則需進(jìn)行頁面置換，最后顯示其物理地址，并轉(zhuǎn)下一條指令。 在所有 320 指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。 3） 置換算法： 最近最不經(jīng)常使用 （ NRU）算法。 提示 : （ 1）通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共 320條指令。指令的地址按下述原則生成： ① 50%的指令是順序執(zhí)行的； 15 ② 25%的指令是均勻分布在前地址部分； ③ 25%的指令是均勻分布在后地址部分； 具體的實施方法是： ① 在 [0， 319]的指令地址之間隨機(jī)選取一起點 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條指令為第 1頁（對應(yīng)虛存地址為 [10， 19]）； ?? ?? 第 310 條～第 319 條指令為第 31 頁（對應(yīng)虛存地址為 [310， 319]）。 按以上方式，用戶指令可組成 32 頁。 （ 3）計算 最近最不經(jīng)常使用 （ NRU） 算法在不同內(nèi)存容量下的命中率。 其中，命中率 =1頁面失效次數(shù) /頁地址流長度 題目十八： P、 V 操作及進(jìn)程同步的實現(xiàn) 1 1．設(shè)計 目的 掌握信號量通信方式的一般方法，了解系統(tǒng)實現(xiàn) “阻塞 ”和 “喚醒 ”功能的方法和技巧。同時掌握進(jìn)程同步和互斥的概念及實現(xiàn)技術(shù)。 2．設(shè)計 內(nèi)容 16 1）用語言編程實現(xiàn) P、 V 原語并用 P、 V 原語描述如下 理發(fā)師 顧客 問題： 有一個理發(fā)師，一把理發(fā)椅和 n 把提供給等候理發(fā)的顧客座的椅子。如果沒有顧客，則理發(fā)師便在理發(fā)椅子上睡覺；當(dāng)?shù)谝粋€顧客到來時， 必須喚醒該理發(fā)師進(jìn)行理發(fā)；如果理發(fā)師正在理發(fā)時又有顧客到來，則如果有空椅子可坐，他就坐下來等待，如果沒有空椅子，他就離開理發(fā)店。 為理發(fā)師和顧客各編一段程序描述他們的行為，要求不能帶有競爭條件，試用 P、 V 操作實現(xiàn)。 2）實驗要求及說明 ① 定義信號量并將 P、 V 操作定義為帶參數(shù) ② 以輸出字符串的形式表示理發(fā)師和顧客的行為。 ③ 設(shè)計適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和函數(shù)描述顧客等待隊列和 “喚醒 ”理發(fā)師理發(fā)過程，以及沒有顧客時的 “阻塞 ”理發(fā)師過程。 ④ 編程時需考慮理發(fā)師和顧客對應(yīng)的程序是并發(fā)操作的。 提示：可利用隨機(jī)函數(shù)模擬 并發(fā)操作。 ⑤ 理發(fā)師和顧客兩個進(jìn)程各自調(diào)用一個函數(shù)模擬生產(chǎn)及消費的操作。 題目十九： P、 V 操作及進(jìn)程同步的實現(xiàn) 2 1．設(shè)計 目的 掌握信號量通信方式的一般方法，了解系統(tǒng)實現(xiàn) “阻塞 ”和 “喚醒 ”功能的方法和技巧。同時掌握進(jìn)程同步和互斥的概念及實現(xiàn)技術(shù)。 2．設(shè)計 內(nèi)容 用語言編程實現(xiàn) P、 V 原語并用 P、 V 原語 哲學(xué)家就餐 問題： 為每個哲學(xué)家 各編一段程序描述他們的行為，試用 P、 V 操作實現(xiàn)。 題目二十：銀行家算法 1．設(shè)計 目的 1）了解多道程序系統(tǒng)中，多個進(jìn)程并發(fā)執(zhí)行的資源分配。 2）掌握銀行家算法，了解資源在進(jìn) 程并發(fā)執(zhí)行中的資源分配情況。 3）掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。 2．設(shè)計 內(nèi)容 設(shè)計一個 n 個并發(fā)進(jìn)程共享 m個系統(tǒng)資源的程序以實現(xiàn)銀行家算法。要求： 1） 簡單的選擇界面； 2） 能顯示當(dāng)前系統(tǒng)資源的占用和剩余情況。 3） 為進(jìn)程分配資源，如果進(jìn)程要求的資源大于系統(tǒng)剩余的資源，不與分配并且提示分配不成功； 4） 撤銷作業(yè)，釋放資源。 編寫和調(diào)試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并采用適當(dāng)?shù)乃惴?，有效地防止和避免死鎖的發(fā)生。 17 銀行家算法分配資源的原則是：系統(tǒng)掌握每個進(jìn)程對資源的最大需求量，當(dāng)進(jìn)程要求 申請資源時，系統(tǒng)就測試該進(jìn)程尚需資源的最大量，如果系統(tǒng)中現(xiàn)存的資源數(shù)大于或等于該進(jìn)程尚需求資源最大量時，就滿足進(jìn)程的當(dāng)前申請。這樣就可以保證至少有一個進(jìn)程可能得到全部資源而執(zhí)行到結(jié)束，然后歸還它所占有的全部資源供其它進(jìn)程使用。 銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1)可利用資源向量 Available(一維數(shù)組 ) 是一個含有 m個元素，其中的每一個元素代表一類