【正文】 設(shè)計(jì)題目 操作系統(tǒng)課程設(shè)計(jì) 學(xué)生姓名 李飛吾 學(xué) 號(hào) 20216637 專業(yè)班級(jí) 信息計(jì) 10 2 班 指導(dǎo)教師 2021 年 12 月 22 日 設(shè) 計(jì) 共 3 題如下描述 成績 題 目 課 程 設(shè) 計(jì) 主 要 內(nèi) 容 首先感謝老師 和 同學(xué) 的 指導(dǎo) 設(shè)計(jì)目的： 《操作系統(tǒng)原理》課程設(shè)計(jì)是 信息計(jì)算科學(xué) 專業(yè)實(shí)踐性環(huán)節(jié)之一，是 對 學(xué)習(xí)完《操 作系統(tǒng)原理》 課程后進(jìn)行的一次較全面的綜合 訓(xùn)練 。 其目的在于加深對操作系統(tǒng) 的理論、 方法和基礎(chǔ)知識(shí)的理解， 掌握操作系統(tǒng)結(jié)構(gòu)、 實(shí)現(xiàn)機(jī)理和各種典型算法， 系統(tǒng)地了解操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)思路，培養(yǎng)學(xué)系統(tǒng)設(shè)計(jì)能力， 并了解操作 系統(tǒng)的發(fā)展動(dòng)向和趨勢。 對以后工作或者進(jìn)一步研究都有促進(jìn)作用 。 設(shè)計(jì)題目： 進(jìn)程調(diào)度算法 銀行家算法 頁面調(diào)度算法 設(shè)計(jì)總結(jié)： a、知識(shí)總結(jié) 有效性一直是操作系統(tǒng)所追求的目標(biāo)之一。操作系統(tǒng)的有效性包含以下兩個(gè)方面： 提高資源利用率； 提高系統(tǒng)吞吐率。引入進(jìn)程管理，處理機(jī)調(diào)度，存儲(chǔ)器管理，設(shè)備管理，文件管理等等機(jī)制，都是為了實(shí)現(xiàn)該特性的。而實(shí)現(xiàn)各種機(jī)制卻有著不同算法，算法的優(yōu)劣就顯得尤為重要了。 b、實(shí)踐感悟 由于時(shí)間倉促，此次課程設(shè)計(jì)并未投入大量時(shí)間，依然存在許多不足。但是通過對算法的進(jìn)一步理解，加以程序?qū)崿F(xiàn)，讓我對本專業(yè)的學(xué)習(xí)興趣更加濃厚了。課程設(shè)計(jì)時(shí)，遇到了一些問題，通過與老師及同學(xué)的交流，和網(wǎng)上查閱資料，學(xué)到了更多的知識(shí)。在此對老師和同學(xué)表示感謝 。 指 導(dǎo) 老 師 評(píng) 語 建議：從學(xué)生的工作態(tài)度、工作量、設(shè)計(jì) (論文的 )創(chuàng)造性、學(xué)術(shù)性、使用性及書面表達(dá)能力等方面給出評(píng)價(jià)。 簽名： 20 年 月 日 目錄 一、 算法 設(shè)計(jì)概述 設(shè)計(jì)背景 1 運(yùn)行環(huán)境 1 二 、 進(jìn)程調(diào)度算法 進(jìn)程 并發(fā)執(zhí)行 1 算法原理 及設(shè)計(jì) 2 代碼設(shè)計(jì) 3 三、 銀行家算法 進(jìn)程死鎖狀態(tài) 13 算法原理 及設(shè)計(jì) 13 代碼設(shè)計(jì) 16 四、 頁面調(diào)度算法 頁式 虛擬存儲(chǔ) 20 算法原理 及設(shè)計(jì) 20 代碼設(shè)計(jì) 21 五、課程設(shè)計(jì)總結(jié) 知識(shí)總結(jié) 26 實(shí)踐感悟 26 一、 算法設(shè)計(jì)概述 設(shè)計(jì)背景 操作系統(tǒng)是管理計(jì)算機(jī)硬件資源，控制其他程序運(yùn)行并為用戶提供交互操作界面的系統(tǒng)軟件的集合。操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)的關(guān)鍵組成部分，負(fù)責(zé)管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本任務(wù)。 操作系統(tǒng)作為系統(tǒng)與用戶之間的接口，極大方便了用戶使用操作系統(tǒng)，同時(shí)也推動(dòng)了計(jì)算機(jī)科學(xué)的發(fā)展。 《操 作系統(tǒng)原理》課程設(shè)計(jì)是 信息計(jì)算科學(xué) 專業(yè)實(shí)踐性環(huán)節(jié)之一，是 對 學(xué)習(xí)完《操 作系統(tǒng)原理》 課程后進(jìn)行的一次較全面的綜合 訓(xùn)練 。 其目的在于加深對操作系統(tǒng) 的理論、 方法和基礎(chǔ)知識(shí)的理解， 掌握操作系統(tǒng)結(jié)構(gòu)、 實(shí)現(xiàn)機(jī)理和各種典型算法， 系統(tǒng)地了解操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)思路，培養(yǎng)學(xué)系統(tǒng)設(shè)計(jì)能力， 并了解操作 系統(tǒng)的發(fā)展動(dòng)向和趨勢。 對以后工作或者進(jìn)一步研究都有促進(jìn)作用 。 設(shè)計(jì)環(huán)境 開發(fā)環(huán)境： Visual C++ 運(yùn)行環(huán)境： Windows 7 / XP 二、 進(jìn)程調(diào)度算法 進(jìn)程的并發(fā)執(zhí)行 并發(fā)性是操作系統(tǒng)的重要特征 在多道程序環(huán)境下，并發(fā)性是指在一段時(shí)間內(nèi)宏觀上有多個(gè)程序在同時(shí)運(yùn)行，但在單處理機(jī)系統(tǒng)中，每一時(shí)刻卻只能有一道程序執(zhí)行，故在微觀上這些程序只能是分時(shí)地交替運(yùn)行。倘若在計(jì)算機(jī)系統(tǒng)有多個(gè)處理機(jī)，則這些可以并發(fā)執(zhí)行的程序便可以被分配到多個(gè)處理機(jī)上，實(shí)現(xiàn)執(zhí)行，即利用每個(gè)處理機(jī)來處理一個(gè)可以并發(fā)執(zhí)行的程序，這樣，多個(gè)程序便可同時(shí)執(zhí)行。 程序是靜態(tài)實(shí)體，進(jìn)程是動(dòng)態(tài)的，通過對進(jìn)程調(diào)度實(shí)現(xiàn)，實(shí)現(xiàn)程序運(yùn)行。 調(diào)度的實(shí)質(zhì)是系統(tǒng)按照某種特定的分配策略來分配資源。進(jìn)程調(diào)度的目的是分配 CPU 資源。由于進(jìn)程調(diào)度程序執(zhí)行的頻率很高，因此調(diào)度算法的好壞將直接影響到操作系統(tǒng)的性能。本實(shí)驗(yàn)的目的是模擬實(shí)現(xiàn)幾種常見的進(jìn)程調(diào)度算法，通過對幾組進(jìn)程分別使用不同的調(diào)度算法，計(jì)算進(jìn)程的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，比較各種算法的性能優(yōu)劣。 算法原理及設(shè)計(jì) （ 1）進(jìn)程調(diào)度算法 進(jìn)程調(diào)度算法包括先來先服務(wù)調(diào)度算法、優(yōu)先數(shù)調(diào)度算法、時(shí)間片論轉(zhuǎn)算法和分級(jí)調(diào)度算法等 4 種。本實(shí)驗(yàn)包括 3 種算法，有興趣的讀者可以在完成這些算法的基礎(chǔ)上實(shí)現(xiàn)第四種算法。 下面對前 3 種算法作一 一 簡單介紹。 1 先來先服務(wù)（ FCFS）調(diào)度算法 本算法在進(jìn)行調(diào)度時(shí)，總是選擇一個(gè)最先進(jìn)入進(jìn)程就緒隊(duì)列的進(jìn)程，把處理器分配給它，使之開始運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生阻塞事件時(shí)，才放棄處理器。 2 優(yōu)先數(shù)調(diào)度算法 對每個(gè)進(jìn)程確定一個(gè)優(yōu)先數(shù)，進(jìn)程調(diào)度總是讓具有最高優(yōu)先數(shù)的進(jìn)程先使用處理器。如果就緒隊(duì)列中出現(xiàn)優(yōu)先數(shù)相同的進(jìn)程，則對這些有相同優(yōu)先數(shù)的進(jìn)程采用先來先服務(wù)算法進(jìn)行調(diào)度。 對于占用處理器的進(jìn)程，系統(tǒng)可以使用“搶占式”或“非搶占式”的策略?！胺菗屨际健敝高M(jìn)程一旦占用處理器，除非自己愿意，否則操作系統(tǒng)不能將處理器強(qiáng)行奪走，即使該進(jìn)程的優(yōu)先數(shù)已經(jīng)小于就 緒隊(duì)列中的某個(gè)進(jìn)程?！皳屨际健眲t相反，一旦就緒隊(duì)列中的某個(gè)進(jìn)程優(yōu)先數(shù)大于正在執(zhí)行的進(jìn)程，立刻進(jìn)行進(jìn)程切換。 進(jìn)程的優(yōu)先數(shù)可以發(fā)生變化。本實(shí)驗(yàn)的基本要求是實(shí)現(xiàn)固定優(yōu)先數(shù)的調(diào)度算法，讀者可以在這個(gè)基礎(chǔ)上添加動(dòng)態(tài)優(yōu)先數(shù)功能。 3 時(shí)間片輪轉(zhuǎn)調(diào)度算法 在需要保證響應(yīng)時(shí)間的場合通常采用時(shí)間片輪轉(zhuǎn)算法來分配處理器。本算法將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把 CPU 分配給隊(duì)首進(jìn)程，令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片用完，調(diào)度程序自動(dòng)停止該進(jìn)程的執(zhí)行，將它放到進(jìn)程就緒隊(duì)列的末尾，等待下一次執(zhí)行，然后將 CPU 分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，也讓它執(zhí)行一個(gè)時(shí)間片。重復(fù)這個(gè)過程，直到所有的進(jìn)程執(zhí)行完畢。 （ 2）衡量算法性能的參數(shù) 下面引入兩個(gè)衡量調(diào)度算法性能的參數(shù)。 平均周轉(zhuǎn)時(shí)間： ni11T= Tin??（ ） 平均帶權(quán)周轉(zhuǎn)時(shí)間： ni11 TiW= ( )n Tsi?? 其中： n 為進(jìn)程數(shù)目 Ti 為第 i 個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間，即進(jìn)程從開始運(yùn)行到結(jié)束的時(shí)間 Tsi 為第 i 個(gè)進(jìn)程要求執(zhí)行的時(shí)間，即需要在 CPU 上的執(zhí)行時(shí)間。 代碼設(shè)計(jì) （ 1）建立進(jìn)程控制塊 進(jìn)程控制塊至少應(yīng)該包括： 進(jìn)程名稱 進(jìn)程需要執(zhí)行時(shí)間 進(jìn)入就緒隊(duì)列時(shí)間 進(jìn)程執(zhí)行結(jié)束時(shí)間 進(jìn)程號(hào) 到達(dá)時(shí)間 要求執(zhí)行時(shí)間 0 0 4 1 1 35 2 2 10 3 3 5 4 6 9 5 7 21 6 9 35 7 11 23 8 12 42 9 13 1 10 14 7 11 20 5 12 23 3 13 24 22 14 25 31 15 26 1 （ 2）就緒進(jìn)程序列 如上右表 所示 代碼設(shè)計(jì) include include include const int timeslice=5。 //定義時(shí)間片的長度 const int MAXPCB=100。 //定義最大進(jìn)程數(shù) //定義進(jìn)程結(jié)構(gòu)體 typedef struct node{ char sNum[4]。 //進(jìn)程編號(hào) int ArriveTime。 //進(jìn)程到達(dá)時(shí)間 int RunTime。 //進(jìn)程要求執(zhí)行的時(shí)間 int Privilege。 //進(jìn)程的優(yōu)先數(shù) int Finished。 //標(biāo)志進(jìn)程是否執(zhí)行完成 《進(jìn)程控制塊代碼》 typedef struct node { char sNum[4]。 //進(jìn)程編號(hào) int ArriveTime。 //進(jìn)程到達(dá)時(shí)間 int RunTime。 //進(jìn)程要求執(zhí)行的時(shí)間 int Privilege。 //進(jìn)程的優(yōu)先數(shù) int Finished。 //標(biāo)志進(jìn)程是否執(zhí)行完成 int Time。 //進(jìn)程等待時(shí)間的借助變量 int WaitTime。 //進(jìn)程的等待時(shí)間 int TurnoverTime。 //進(jìn)程的周轉(zhuǎn)時(shí)間 float WeighTurnTime。 //進(jìn)程 帶權(quán)周轉(zhuǎn)時(shí)間 }pcb。 int Time。 //求進(jìn)程的等待時(shí)間的借助變量 int WaitTime。 //進(jìn)程的等待時(shí)間 int TurnoverTime。 //進(jìn)程的周轉(zhuǎn)時(shí)間 float WeighTurnTime。 //進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間 }pcb。 pcb pcbs[MAXPCB]。 int PCBNum。 //進(jìn)程數(shù) //PCB 初始化函數(shù) void initPCB() { int i。 for(i=0。iMAXPCB。i++) { strcpy(pcbs[i].sNum,)。 pcbs[i].ArriveTime=0。 pcbs[i].RunTime=0。 pcbs[i].Privilege=0。 pcbs[i].Finished=0。 pcbs[i].Time=0。 pcbs[i].WaitTime=0。 pcbs[i].TurnoverTime=0。 pcbs[i].WeighTurnTime=0。 } //for(i=0。iMAXPCB。i++) PCBNum=0。 } //void initPCB() //讀進(jìn)程流文件數(shù)據(jù)函數(shù) int readData() { FILE *fp。 char sFile[20]。 int i。 cout 請輸入進(jìn)程流文件名（注意：包括后綴名） : 。 cinsFile。 if((fp=fopen(sFile,r))==NULL) { cout 錯(cuò)誤 ,文件打不開 ,請檢查文件名 endl。 } else{ while(!feof(fp)) { fscanf(fp,%s %d %d %d,pcbs[PCBNum].sNum,amp。pcbs[PCBNum].ArriveTime,amp。pcbs[PCBNum].RunTime,amp。pcbs[PCBNum].Privilege)。 PCBNum++。 } //while(!feof(fp)) //輸出所讀入的數(shù)據(jù) coutendl 輸出所讀入的數(shù)據(jù)： endlendl。 cout 進(jìn)程編號(hào) 進(jìn)程到達(dá)時(shí)間 要求執(zhí)行時(shí)間 優(yōu)先數(shù) endl。 for(i=0。iPCBNum1。i++) { cout pcbs[i].sNum pcbs[i].ArriveTime pcbs[i].RunTime pcbs[i].Privilegeendl。 } return(1)。 } //if((fp=fopen(sFile,r))==NULL) return(0)。 }// int readData() //重置 PCB 數(shù)據(jù) ,以供另一個(gè)算法使用 void reInitPCB() { int i。 for(i=0。iMAXPCB。i++) { pcbs