【正文】 物理與電子信息工程學(xué)院 《操作系統(tǒng)》課程設(shè)計(jì)報(bào)告 題目 ： 進(jìn)程調(diào)度算法 頁(yè)面淘汰算法 小組成員： 汪振昊 鄭云紅 班級(jí)信息： 班級(jí)： 10 計(jì)本 完成 日期： 指導(dǎo) 教師： 曾令華 目 錄 一、 操作系統(tǒng)課程設(shè)計(jì) 操作系統(tǒng)課程設(shè)計(jì)宗旨 課程目的 二、 頁(yè)面置換算法 目的 背景 常見的頁(yè)面置換算法 設(shè)計(jì)思想 三、 頁(yè)面置換算法流程圖 頁(yè)面置換算法實(shí)現(xiàn)流程圖 四、 頁(yè)面置換算法代碼運(yùn)行結(jié)果 采用隨機(jī)數(shù)產(chǎn)生結(jié)果 采用自定義頁(yè)面信息產(chǎn)生結(jié)果 五、 進(jìn)程調(diào)度算法實(shí)現(xiàn) 目的 設(shè)計(jì)思想 可行性分析 六、 進(jìn)程調(diào)度 算法流程圖 主流程圖 七、 進(jìn)程調(diào)度算法執(zhí)行結(jié)果 先來(lái)先服務(wù)算法 優(yōu)先級(jí)算法 八、 頁(yè)面置換算法源代碼 九、 進(jìn)程調(diào)度算法源代碼 一、 操作系統(tǒng) 課 程 設(shè)計(jì) 操作系統(tǒng) 課程設(shè)計(jì)宗旨 為了更好的幫助我們同學(xué)進(jìn)一步加深對(duì)計(jì)算機(jī)操作系統(tǒng)的掌握與理解，學(xué)校給計(jì)本班開設(shè)了操作系統(tǒng)這門課程。幫助我們進(jìn)一步了解并鞏固了計(jì)算機(jī)操作系統(tǒng)的一些有關(guān)進(jìn)程調(diào)度，頁(yè)面置換，文件處理等方面的知識(shí)。 課程目的 利用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，模擬操作系統(tǒng)中的 一些有關(guān)文件操作，進(jìn)程調(diào)度，頁(yè)面置換。 二、 頁(yè)面置換算法實(shí)現(xiàn) 目的 利用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，模擬實(shí)現(xiàn)操作系統(tǒng)中的 頁(yè)面置換機(jī)制 用 C 語(yǔ)言編寫 OPT、 FIFO、 LRU 三 種置換算法。 熟悉內(nèi)存分頁(yè)管理策略。 了解頁(yè)面置換的算法。 掌握一般常用的調(diào)度算法。 根據(jù)方案使算法得以模擬實(shí)現(xiàn)。 鍛煉知識(shí)的運(yùn)用能力和實(shí)踐能力。 背景 在操作系統(tǒng)當(dāng)中，在進(jìn)程運(yùn)行過(guò)程中，若其訪問(wèn)的頁(yè)面不在內(nèi)存中而需把他們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證該進(jìn)程能夠正常的運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤的兌換區(qū)中，但是應(yīng)該是哪個(gè)頁(yè)面被調(diào)出，需根據(jù)一定的算法來(lái)確定。通常，我們把這一類的算法稱為“頁(yè)面置換算法” ，頁(yè)面置換算法執(zhí)行效率的高低，往往直接影響到操作系統(tǒng)的性能。 常見頁(yè)面置換算法 先進(jìn)先出算法（ FIFO） 這是最早出現(xiàn)的置換算法，該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)面換出，該算法實(shí)現(xiàn)簡(jiǎn)單。 最近最久未使用 （ LRU） 最近最久未使用的置換算法，是根據(jù) 頁(yè)面調(diào)入內(nèi)存后的使用情況卻決策的，由于無(wú)法預(yù)測(cè)個(gè)頁(yè)面將來(lái)的使用情況，只能根據(jù)“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，最近最久未使用（ LRU）算法是選擇最近的最久未使用的頁(yè)面予以淘汰。 最佳置換算法 （ OPT） 最佳置換算法是 可以說(shuō)的一種理想的頁(yè)面置換算法，其所淘汰的頁(yè)面是將來(lái)不會(huì)被使用的或者是在最長(zhǎng)的未來(lái)不會(huì)被使用的頁(yè)面。采用最佳置換算法，可以獲得最小的缺頁(yè)率 設(shè)計(jì)思想 最佳置換算法 (OPT) 用數(shù)組 Temppages[]存儲(chǔ)當(dāng)前物理塊中頁(yè)面信息，數(shù)組 TimeArry[]存儲(chǔ)當(dāng)前在物理塊中的頁(yè)面的獲得內(nèi)存時(shí)的時(shí)間， 當(dāng)頁(yè)面不在內(nèi)存中時(shí)，根據(jù)當(dāng)前已獲得物理塊數(shù)的頁(yè)面在所有的頁(yè)面當(dāng)中將來(lái)不在請(qǐng)求內(nèi)存或者很少請(qǐng)求內(nèi)存的情況進(jìn)行置換 先進(jìn)先出算法 (FIFO) 用數(shù)組 Temppages[]存儲(chǔ)當(dāng)前物理塊中頁(yè)面信息，變量 temp 記錄內(nèi)存 中物理塊頁(yè)面置換狀態(tài)，每進(jìn)行一次置換，頁(yè)面置換狀態(tài)變化，便于下一次的置換。 最近最久未使用算法 (LRU) 用數(shù)組 Temppages[]存儲(chǔ)當(dāng)前物理塊中頁(yè)面信息，數(shù)組 TimeArry[]存儲(chǔ)當(dāng)前在物理塊中的頁(yè)面的獲得內(nèi)存時(shí)的時(shí)間，當(dāng)頁(yè)面不在內(nèi)存中時(shí)，選擇 TimeArry[]數(shù)組中值最小并且對(duì)應(yīng)物理塊中的頁(yè)面進(jìn)行置換。 三、 頁(yè)面置換算法 流程圖 頁(yè)面置換算法實(shí)現(xiàn)流程圖 開始 載入頁(yè)號(hào)序列，從 0 個(gè)得到頁(yè)號(hào) 將頁(yè)號(hào)載入物理塊 頁(yè)號(hào)序列大于物理塊數(shù) 否 頁(yè)號(hào)在物理塊中 根據(jù)對(duì)應(yīng)的頁(yè)面置換算法置換頁(yè)面 頁(yè)號(hào)序列載完 是 否 結(jié)束 否 四、 頁(yè)面置換算法 代碼運(yùn)行結(jié)果 采 用隨機(jī)數(shù)產(chǎn)生的結(jié)果 采用自定義頁(yè)面信息產(chǎn)生結(jié)果 自定義頁(yè)面數(shù)為： 20 物理塊數(shù)為： 3 頁(yè)面序列為： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 五、 進(jìn)程調(diào)度算法實(shí)現(xiàn) 目的 在多道程序運(yùn)行環(huán)境下，進(jìn)程數(shù)目一般多于處理機(jī)數(shù)目，使得進(jìn)程要通過(guò)競(jìng)爭(zhēng)來(lái)使用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之運(yùn)行，分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。一個(gè)進(jìn) 程被創(chuàng)建后，系統(tǒng)為了便于對(duì)進(jìn)程進(jìn)行管理，將系統(tǒng)中的所有進(jìn)程按其狀態(tài)，將其組織成不同的進(jìn)程隊(duì)列。于是系統(tǒng)中有運(yùn)行進(jìn)程隊(duì)列、就緒隊(duì)列和各種事件的進(jìn)程等待隊(duì)列。進(jìn)程調(diào)度的功能就是從就緒隊(duì)列中挑選一個(gè)進(jìn)程到處理機(jī)上運(yùn)行。進(jìn)程調(diào)度的算法有多種，常用的有優(yōu)先級(jí)調(diào)度算法、先來(lái)先服務(wù)算法、時(shí)間片輪轉(zhuǎn)算法。這里我們主要實(shí)現(xiàn)的是先來(lái)先服務(wù)算法和優(yōu)先級(jí)調(diào)度算法。 設(shè)計(jì)思想 對(duì)于先到先服務(wù)算法，只需要給定每個(gè)進(jìn)程的進(jìn)程號(hào)，然后依次順序執(zhí)行就可以了。 對(duì)于優(yōu)先度調(diào)度算法，需要先判斷優(yōu)先度的大小，優(yōu)先度最大的先執(zhí)行，進(jìn)程運(yùn)行完畢以后 ，按照優(yōu)先數(shù)的改變的原則進(jìn)行改變，然后繼續(xù)判斷所有的優(yōu)先數(shù)的大小，依舊是優(yōu)先數(shù)最大的先執(zhí)行，直到執(zhí)行完畢。 可行性分析 （ 1） 設(shè)計(jì)一個(gè)結(jié)構(gòu)體，用于抽象進(jìn)程的各種屬性，其中包括 進(jìn)程標(biāo)志符 ， 進(jìn)程優(yōu)先級(jí) ， cpu 時(shí)間統(tǒng)計(jì) ， 運(yùn)行所需時(shí)間 ， 進(jìn)程狀態(tài) 。 （ 2） 再設(shè)計(jì)一個(gè)結(jié)構(gòu)體，用于模擬就緒隊(duì)列，其具體方法采用鏈表形式。 （ 3） 對(duì)于先到先服務(wù)算法，判斷就緒隊(duì)列中每個(gè)進(jìn)程的進(jìn)程號(hào)，根據(jù)進(jìn)程號(hào)的順序依次給進(jìn)程分配 CPU，直到所有進(jìn)程執(zhí)行完畢為止 （ 4） 對(duì)于優(yōu)先度調(diào)度算法，首先根據(jù)所有進(jìn)程的有限度，依次按照其優(yōu)先度的大小按照降序排序的方式依次插 入就緒隊(duì)列，每當(dāng)一個(gè)進(jìn)程獲得 CPU 并執(zhí)行時(shí)， 優(yōu)先級(jí)降低 2， 每運(yùn)行一次 CPU 時(shí)間增 加 4，當(dāng)所獲得的 CPU時(shí)間大于或者等于其所需的 CPU時(shí)間時(shí)，進(jìn)程執(zhí)行完畢，否則變換就緒隊(duì)列中進(jìn)程順序，使之保持進(jìn)程優(yōu)先級(jí)按降序排序。 （ 5） 每個(gè)進(jìn)程獲得 CPU時(shí)間并執(zhí)行完畢之后，打印出進(jìn)程隊(duì)列中的信息，以便查看就緒隊(duì)列中的進(jìn)程信息。 六、 進(jìn)程調(diào)度算法 流程圖 主流程圖