第一篇：計(jì)算機(jī)操作系統(tǒng)-司機(jī)與售票員的進(jìn)程問題-實(shí)驗(yàn)報(bào)告
計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)報(bào)告
-------售票員和汽車司機(jī)的進(jìn)程同步問題
一、設(shè)計(jì)分析
司機(jī)與售票員要協(xié)同工作:一方面只有售票員把門關(guān)好之后司機(jī)才能開車，因此售票員關(guān)好門之后要通知司機(jī)開車；另一方面，也只有司機(jī)把車停下之后售票員才能開門讓乘客下車和上車，此時(shí)司機(jī)應(yīng)通知售票員。汽車當(dāng)前正在始發(fā)站停車讓乘客上車。因此，必須設(shè)置一定的信號(hào)量來實(shí)現(xiàn)他們之間的同步問題。
把司機(jī)與售票員的信號(hào)量設(shè)置為全局變量，并把客車上的人數(shù)：現(xiàn)在人數(shù)、下車人數(shù)、上車人數(shù)設(shè)置為全局變量；設(shè)置司機(jī)與售票員各自的線程。考慮到第一站和最后一站的問題，應(yīng)單獨(dú)處理，故在各自的線程中分情況討論：
由于下車的人數(shù)是隨機(jī)的，設(shè)計(jì)時(shí)考慮到了人數(shù)可能會(huì)超過客車的最大上限的問題。具體的思路是下面的圖示。
二、算法實(shí)現(xiàn)（源代碼）
#include
//假設(shè)汽車的最大容量為88 #define total_pork 9
//總的站數(shù)
int recent_num=0;
//某一時(shí)刻的客車上的人數(shù) int get_on_num;
//上車的人數(shù) int get_off_num;
//下車的人數(shù) int pork=1;
//賦初始值 HANDLE SJ;
//司機(jī)的信號(hào)量 HANDLE SPY;
//售票員的信號(hào)量
int Get_random(int min, int max)
//產(chǎn)生一定范圍的隨機(jī)數(shù)，可避免下面程序的判斷超出客車的最大容量問題{ int a;srand((int)time(0));
while(1){ a=rand()%(total_num+1);if(a>=min && a<=max)return a;} } //司機(jī)的線程
DWORD WINAPI Thread_Driver(LPVOID Driver){ while(pork<=total_num){ if(pork==total_pork){ WaitForSingleObject(SJ,INFINITE);cout<<“到達(dá)總站，歡迎您下次乘坐**路公交車”< { ReleaseSemaphore(SPY,1, NULL);WaitForSingleObject(SJ,INFINITE);cout<<“汽車啟動(dòng)”< } Sleep(1000);} return 0;} //售票員的線程 DWORD WINAPI Thread_Conductor(LPVOID SPY){ while(1){ if(pork cout<<“這是第”< WaitForSingleObject(SPY,INFINITE);if(pork==1){ cout<<“SPY開始售票”< get_on_num=Get_random(0,total_num-recent_num); cout< recent_num+=get_on_num;cout<<“共有”< { cout<<“SJ停好車，乘客開始上下車”< get_off_num=Get_random(0,recent_num); cout< return 0;} //主函數(shù) int main(){ HANDLE SJ;HANDLE SPY;SJ=CreateSemaphore(NULL,0,1,“semaphore_driver”);//創(chuàng)建司機(jī)的信號(hào)量 SPY=CreateSemaphore(NULL,0,1,“semaphore_conductor”);//創(chuàng)建售票員的信號(hào)量 SJ=CreateThread(NULL,0,Thread_Driver,&SJ,0,NULL);//創(chuàng)建司機(jī)的線程 SPY=CreateThread(NULL,0,Thread_Conductor,&SPY,0,NULL);//創(chuàng)建售票員的線程 CloseHandle(SJ);CloseHandle(SPY);while(1);system(“pause”);return 0;} 三．實(shí)現(xiàn)結(jié)果 四、心得體會(huì) 1、因?yàn)樗緳C(jī)與售票員是兩條單獨(dú)處理的線程。程序先對(duì)司機(jī)的線程進(jìn)行設(shè)計(jì)，接著再進(jìn)行售票員的線程設(shè)計(jì)。因?yàn)閮烧呤切枰嗷f(xié)調(diào)，又先后順序的，所以編起程序來比較復(fù)雜，而且很亂，尤其對(duì)于第一次接觸的我們而言。 2、上下車的人數(shù)是隨機(jī)的，所以，我們?cè)诰幊绦驎r(shí)必須注意使程序能夠判斷所出現(xiàn)的隨機(jī)數(shù)在汽車可以承載的最大容量之內(nèi)。 3、C++語言基礎(chǔ)不是很好，所以編起程序來比較費(fèi)力，這種設(shè)計(jì)性的實(shí)驗(yàn)對(duì)于我們而言還是有一定的難度的，所以部分程序是參照網(wǎng)上的類似程序。 實(shí)驗(yàn)報(bào)告說明書 設(shè)計(jì)名稱： 操作系統(tǒng)課程設(shè)計(jì) 實(shí) 驗(yàn) ： 進(jìn)程調(diào)度設(shè)計(jì) 學(xué)生姓名： 專 業(yè)： 網(wǎng)絡(luò)工程 班 級(jí)： 08級(jí)一班 學(xué) 號(hào)： 指導(dǎo)教師：雷曉平王東 黃營 楊躍武 日 期： 2011年 6月 19日 課程設(shè)計(jì)任務(wù)書 網(wǎng)絡(luò)工程 專業(yè) 08 年級(jí) 1 班 一、具體要求 本課程設(shè)計(jì)共2周，采取集中方式。㈠主要設(shè)計(jì)內(nèi)容 1、進(jìn)程調(diào)度 2、存儲(chǔ)管理 3、文件管理 ㈡操作系統(tǒng)分項(xiàng)設(shè)計(jì) 1、設(shè)計(jì)一 ：進(jìn)程管理系統(tǒng)設(shè)計(jì) 目的與要求：本設(shè)計(jì)的目的是加深對(duì)進(jìn)程概念及進(jìn)程管理各部分內(nèi)容的理解；熟悉進(jìn)程管理中主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及進(jìn)程調(diào)度算法、進(jìn)程控制機(jī)構(gòu)、同步機(jī)構(gòu)及通訊機(jī)構(gòu)的實(shí)施。 要求設(shè)計(jì)一個(gè)允許n個(gè)進(jìn)程并發(fā)運(yùn)行的進(jìn)程管理模擬系統(tǒng)。該系統(tǒng)包括有簡(jiǎn)單的進(jìn)程控制、同步與通訊機(jī)構(gòu)，其進(jìn)程調(diào)度算法可任意選擇。每個(gè)進(jìn)程用一個(gè)PCB表示，其內(nèi)容根據(jù)具體情況設(shè)置。各進(jìn)程之間有一定的同步關(guān)系（可選）。系統(tǒng)在運(yùn)行過程中應(yīng)能顯示或打印各進(jìn)程的狀態(tài)及有關(guān)參數(shù)的變化情況，以便觀察諸進(jìn)程的運(yùn)行過程及系統(tǒng)的管理過程。 具體詳見：設(shè)計(jì)任務(wù)書1--進(jìn)程調(diào)度算法.doc 2、設(shè)計(jì)二：存貯器管理系統(tǒng)設(shè)計(jì) 目的與要求：本設(shè)計(jì)的目的是使學(xué)生熟悉存貯器管理系統(tǒng)的設(shè)計(jì)方法；加深對(duì)所學(xué)各種存貯器管理方案的了解；要求采用一些常用的存貯器分配算法，設(shè)計(jì)一個(gè)存貯器管理模擬系統(tǒng)并調(diào)試運(yùn)行。模擬環(huán)境應(yīng)盡量接近真實(shí)。 具體詳見：設(shè)計(jì)任務(wù)書2--內(nèi)存分區(qū)管理模擬.doc 3、設(shè)計(jì)三：虛擬存儲(chǔ)器管理系統(tǒng)設(shè)計(jì) 本設(shè)計(jì)的目的是通過設(shè)計(jì)一個(gè)簡(jiǎn)單的虛擬存儲(chǔ)器管理系統(tǒng)來模擬實(shí)際的頁面調(diào)度算法與過程，以掌握這種有用的技術(shù)。要求將其輸入/輸出處理程序編成一個(gè)獨(dú)立的進(jìn)程模塊并與其它請(qǐng)求輸入/輸出的進(jìn)程并發(fā)運(yùn)行。并要求加入設(shè)備管理子模塊。 具體分析為：頁面調(diào)度算法主要有FIFO、最近最少使用調(diào)度算法（LRU）、最近最不常用調(diào)度算法（LFU）、最佳算法（OPT）等。題目要求： ① 實(shí)現(xiàn)三種算法： 1、先進(jìn)先出； 2、OPT； 3、LRU ② 頁面序列從指定的文本文件（TXT文件）中取出 ③ 輸出：第一行：每次淘汰的頁面號(hào)，第二行：顯示缺頁的總次數(shù) 4、設(shè)計(jì)四：文件管理系統(tǒng)設(shè)計(jì) 目的與要求：本設(shè)計(jì)的目的是通過設(shè)計(jì)和調(diào)試一個(gè)簡(jiǎn)單的外部文件系統(tǒng)，主要是模擬文件操作，使學(xué)生對(duì)主要文件操作命令的實(shí)質(zhì)和執(zhí)行過程有比較深入的了解，掌握它們的基本實(shí)施方法。 基本要求如下： 實(shí)現(xiàn)三種算法： 先來先服務(wù)、最短尋道優(yōu)先、電梯算法 磁道服務(wù)順序從指定的文本文件（TXT文件）中取出 輸出：第一行：磁道的服務(wù)順序；第二行：顯示移動(dòng)總道數(shù) 5、設(shè)計(jì)五：多道程序的轉(zhuǎn)換調(diào)度系統(tǒng) 題目要求：（作業(yè)調(diào)度和進(jìn)程調(diào)度結(jié)合在一起）作業(yè)流信息是從指定文本文件（TXT文件）中讀取 作業(yè)信息： 作業(yè)號(hào) 進(jìn)入系統(tǒng)時(shí)間 估計(jì)運(yùn)行時(shí)間 優(yōu)先級(jí) 內(nèi)存需求量 磁帶機(jī)需求量 都為整型 作業(yè)調(diào)度算法：先來先服務(wù)、最短作業(yè)優(yōu)先（二者選一） 進(jìn)程調(diào)度算法：先來先服務(wù)、基于優(yōu)先級(jí)的算法(靜態(tài)優(yōu)先級(jí))(二者選一)輸出格式：作業(yè)號(hào) 時(shí)間間隔 800-810（/* 8：00-8：10 */）2 810-900 1 900-930平均周轉(zhuǎn)時(shí)間：總的周轉(zhuǎn)時(shí)間/作業(yè)總數(shù) 周轉(zhuǎn)時(shí)間就是作業(yè)結(jié)束時(shí)間減去作業(yè)進(jìn)入系統(tǒng)時(shí)間 具體詳見：多道程序轉(zhuǎn)換.doc 以上設(shè)計(jì)以20-25人為組，選擇一個(gè)設(shè)計(jì)進(jìn)行。㈢操作系統(tǒng)整體設(shè)計(jì) 將第㈡部分中的全部或部分有機(jī)地組合起來，構(gòu)成一個(gè)小型的操作系統(tǒng)。 二、進(jìn)度安排 1、教師下達(dá)設(shè)計(jì)任務(wù)書(半天)任務(wù)書內(nèi)容包括題目、主要技術(shù)指標(biāo)和要求、給定條件及原始數(shù)據(jù)、所用儀器設(shè)備和參考資料及文獻(xiàn)等。教師講授必要的設(shè)計(jì)思路和設(shè)計(jì)方法。 2、學(xué)生完成預(yù)設(shè)計(jì)(1天半)本階段學(xué)生通過查閱資料及文獻(xiàn)（主要自學(xué)），明確任務(wù)，掌握工程設(shè)計(jì)基本方法，確定設(shè)計(jì)方案，進(jìn)行設(shè)計(jì)分析，完成預(yù)設(shè)計(jì)。 3、實(shí)驗(yàn)階段(7天)經(jīng)教師審查通過預(yù)設(shè)計(jì)方案后，即可進(jìn)行編程調(diào)試。實(shí)驗(yàn)由學(xué)生獨(dú)立完成，教師定時(shí)指導(dǎo)。 4、設(shè)計(jì)總結(jié)階段(1天)本階段學(xué)生要認(rèn)真完成課程設(shè)計(jì)報(bào)告書，整理技術(shù)資料，并盡可能寫出課程設(shè)計(jì)的心得體會(huì)和改進(jìn)意見。 三、完成后應(yīng)上交的材料 課程設(shè)計(jì)報(bào)告書包括：設(shè)計(jì)任務(wù)及主要技術(shù)指標(biāo)、設(shè)計(jì)方案及論證結(jié)果、系統(tǒng)的原理框圖、設(shè)計(jì)程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)中主要問題及故障現(xiàn)象的分析及設(shè)計(jì)結(jié)論等。 附實(shí)驗(yàn)數(shù)據(jù)、系統(tǒng)軟硬件環(huán)境、使用說明及參考資料。 四、總評(píng)成績(jī) 指導(dǎo)教師 簽名日期 年 月 日 系 主 任 審核日期 年 月 日 目 錄 一、實(shí)驗(yàn)?zāi)康摹? 二、實(shí)驗(yàn)要求………………………………………5 三、具體內(nèi)容………………………………………5 3.1先來先服務(wù)（FCFS）???????5 3.2作業(yè)優(yōu)先SJF 算法????????5 3.3多級(jí)隊(duì)列調(diào)度算法????????.5 3.4時(shí)間片輪轉(zhuǎn)調(diào)度法?????????5 3.5優(yōu)先級(jí)法?????????????6 3.6多隊(duì)列反饋法???????????6 3.7輪轉(zhuǎn)法??????????????.6 3.8最短周期優(yōu)先???????????6 3.9先來先服務(wù)?????????????7 四、實(shí)驗(yàn)程序………………………………………7 五、實(shí)驗(yàn)總結(jié)………………………………………13 設(shè)計(jì)題目：進(jìn)程管理系統(tǒng)設(shè)計(jì) 一、實(shí)驗(yàn)?zāi)康模?/p> 本設(shè)計(jì)的目的是加深對(duì)進(jìn)程概念及進(jìn)程管理各部分內(nèi)容的理解；熟悉進(jìn)程管理中主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及進(jìn)程調(diào)度算法、進(jìn)程控制機(jī)構(gòu)、同步機(jī)構(gòu)及通訊機(jī)構(gòu)的實(shí)施。 二、實(shí)驗(yàn)要求： 設(shè)計(jì)一個(gè)允許n個(gè)進(jìn)程并發(fā)運(yùn)行的進(jìn)程管理模擬系統(tǒng)。該系統(tǒng)包括有簡(jiǎn)單的進(jìn)程控制、同步與通訊機(jī)構(gòu)，其進(jìn)程調(diào)度算法可任意選擇。每個(gè)進(jìn)程用一個(gè)PCB表示，其內(nèi)容根據(jù)具體情況設(shè)置。各進(jìn)程之間有一定的同步關(guān)系（可選）。系統(tǒng)在運(yùn)行過程中應(yīng)能顯示或打印各進(jìn)程的狀態(tài)及有關(guān)參數(shù)的變化情況，以便觀察諸進(jìn)程的運(yùn)行過程及系統(tǒng)的管理過程。 三、具體內(nèi)容： 調(diào)度也稱dispatcher，這是內(nèi)核的主要職責(zé)之一。一個(gè)良好的任務(wù)調(diào)度算法應(yīng)該主要體現(xiàn)在以下幾個(gè)方面： 公平：保證每個(gè)進(jìn)程得到合理的CPU 時(shí)間 高效：使CPU 保持忙碌狀態(tài)，即總是有進(jìn)程在CPU 上運(yùn)行 響應(yīng)時(shí)間：使交互用戶的響應(yīng)時(shí)間盡可能短 周轉(zhuǎn)時(shí)間：使批處理用戶等待輸出的時(shí)間盡可能短 吞吐量：使單位時(shí)間內(nèi)處理的進(jìn)程盡可能多 很顯然在任何操作系統(tǒng)中這幾個(gè)目標(biāo)不可能同時(shí)達(dá)到所以不同的。 操作系統(tǒng)會(huì)在這幾個(gè)方面中做出相應(yīng)的取舍從而確定自己的調(diào)度算法，常用的處理機(jī)調(diào)度算法有：先來先服務(wù)FCFS、短作業(yè)優(yōu)先SJF、優(yōu)先級(jí)、時(shí)間片輪轉(zhuǎn)法、多級(jí)隊(duì)列法、多級(jí)反饋隊(duì)列法。 （1）先來先服務(wù)（FCFS） FCFS 是最簡(jiǎn)單的CPU 調(diào)度算法，即按進(jìn)程到來的先后次序進(jìn)行調(diào)度，這樣在系統(tǒng)中等待時(shí)間最長(zhǎng)的進(jìn)程被優(yōu)先調(diào)度，而不管其所需運(yùn)行時(shí)間的長(zhǎng)短。 （2）作業(yè)優(yōu)先SJF 算法 是指當(dāng)CPU 可供使用時(shí)SJF 算法把CPU 分給需要運(yùn)行時(shí)間最短的進(jìn)程。（3）多級(jí)隊(duì)列調(diào)度算法 把就緒隊(duì)列劃分成幾個(gè)單獨(dú)的隊(duì)列一般根據(jù)進(jìn)程的某些特性如內(nèi)存大小和進(jìn)程類型永久性地把各個(gè)進(jìn)程分別鏈入其中某一個(gè)隊(duì)列中，每個(gè)隊(duì)列都有自己的調(diào)度算法，此外在各個(gè)隊(duì)列之間也要進(jìn)行調(diào)度。通常采用固定優(yōu)先級(jí)的搶占式調(diào)度，例如某系統(tǒng)中有5 個(gè)隊(duì)列，各個(gè)隊(duì)列的優(yōu)先級(jí)自上而下降低，只有當(dāng)前3 個(gè)隊(duì)列中都為空的時(shí)候隊(duì)列4 中的進(jìn)程才可以運(yùn)行，而當(dāng)隊(duì)列4 中的進(jìn)程在運(yùn)行時(shí)，如果隊(duì)列1 中進(jìn)入了一個(gè)就緒進(jìn)程，則隊(duì)列4 中的進(jìn)程要立刻讓出CPU 使用權(quán)。多級(jí)反饋隊(duì)列法允許進(jìn)程在各隊(duì)列間移動(dòng)，其基本思想是把具有不同CPU工作時(shí)間這一特性的進(jìn)程區(qū)分開來，如果一個(gè)進(jìn)程要使用很長(zhǎng)的CPU 時(shí)間，則應(yīng)把它移至較低級(jí)的隊(duì)列中，這種方式把I/O 繁忙型和交互式進(jìn)程放在較高優(yōu)先級(jí)的隊(duì)列中同樣在低優(yōu)先級(jí)隊(duì)列中長(zhǎng)時(shí)間等待的進(jìn)程可以移到較高優(yōu)先級(jí)隊(duì)列中UNIX 系統(tǒng)采用的是多級(jí)反饋隊(duì)列輪轉(zhuǎn)法。 （4）時(shí)間片輪轉(zhuǎn)調(diào)度法 當(dāng)兩個(gè)或兩個(gè)以上任務(wù)有同樣優(yōu)先級(jí)，內(nèi)核允許一個(gè)任務(wù)運(yùn)行事先確定的一段時(shí)間叫做時(shí)間額度quantum，然后切換給另一個(gè)任務(wù)也叫做時(shí)間片調(diào)度time slicing，內(nèi)核在滿足以下條件時(shí)把CPU 控制權(quán)交給下一個(gè)任務(wù)就緒態(tài)的任務(wù)，當(dāng)前任務(wù)已無事可做，當(dāng)前任務(wù)在時(shí)間片還沒結(jié)束時(shí)已經(jīng)完成了。輪轉(zhuǎn)法主要是為分時(shí)系統(tǒng)設(shè)計(jì)的，其中時(shí)間片是一個(gè)重要的參數(shù)不能取的過大或過小，通常為10 至100ms 數(shù)量級(jí)，就緒隊(duì)列可以看成是一個(gè)環(huán)形隊(duì)列，CPU 調(diào)度程序輪流 地把CPU 分給就緒隊(duì)列中地每個(gè)進(jìn)程，時(shí)間長(zhǎng)度為一個(gè)時(shí)間片Linux 操作系統(tǒng)就是采用時(shí)間片輪轉(zhuǎn)的調(diào)度算法。 （5）優(yōu)先級(jí)法 優(yōu)先級(jí)調(diào)度的基本思想是，把當(dāng)前處于就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程投入運(yùn)行，而不管各進(jìn)程的下一個(gè)CPU周期的長(zhǎng)短和其他因素。 優(yōu)先級(jí)通常用0～4095的整數(shù)(稱為優(yōu)先數(shù))表示，是數(shù)大優(yōu)先級(jí)高還是數(shù)小優(yōu)先級(jí)高取決于規(guī)定。例如UNIX系統(tǒng)規(guī)定優(yōu)先數(shù)越大優(yōu)先級(jí)越低，優(yōu)先數(shù)越小優(yōu)先級(jí)越高。 優(yōu)先數(shù)有靜態(tài)和動(dòng)態(tài)之分。靜態(tài)優(yōu)先數(shù)是指在進(jìn)程開始運(yùn)行之前便根據(jù)某種或某些因素(如估計(jì)運(yùn)行時(shí)間、主存需求量、打開文件個(gè)數(shù)、所付經(jīng)費(fèi)多少等)算定，而且該優(yōu)先數(shù)在進(jìn)程的整個(gè)生命周期內(nèi)一直不變。靜態(tài)優(yōu)先數(shù)方法雖然簡(jiǎn)單，但有可能導(dǎo)致某些低優(yōu)先級(jí)的進(jìn)程無限期地等待。尤其在高優(yōu)先級(jí)的進(jìn)程不斷進(jìn)入就緒隊(duì)列的情況下，使等待CPU的低優(yōu)先級(jí)進(jìn)程更多，等待時(shí)間更長(zhǎng)。動(dòng)態(tài)優(yōu)先數(shù)方法是按照某種原則使各進(jìn)程的優(yōu)先級(jí)隨著時(shí)間而改變。例如隨等待時(shí)間增大優(yōu)先級(jí)也跟著提高、隨著使用CPU時(shí)間的增長(zhǎng)優(yōu)先級(jí)跟著下降，就是一種較好的策略。等待了較長(zhǎng)時(shí)間的進(jìn)程，總會(huì)因其優(yōu)先級(jí)不斷地提高而被調(diào)度運(yùn)行。 如果把進(jìn)入就緒隊(duì)列的次序作為計(jì)算進(jìn)程動(dòng)態(tài)優(yōu)先數(shù)的主要指標(biāo)，那么優(yōu)先級(jí)法就變成FCFS。如果把下一個(gè)CPU周期最短作為計(jì)算進(jìn)程動(dòng)態(tài)優(yōu)先數(shù)的主要指標(biāo)，那么優(yōu)先級(jí)法變成SBF，此時(shí)各進(jìn)程的優(yōu)先數(shù)p_pri = 1/ ti，其中ti是估算的下一個(gè)CPU周期的長(zhǎng)度。 優(yōu)先級(jí)調(diào)度也允許剝奪方式?，F(xiàn)在的許多操作系統(tǒng)，例如UNIX系統(tǒng)V，Windows NT，OS/2等都采用優(yōu)先級(jí)剝奪調(diào)度。 （6）多隊(duì)列反饋法 其基本思想是，把就緒進(jìn)程按優(yōu)先級(jí)排成多個(gè)隊(duì)列，同隊(duì)列的進(jìn)程具有相同的時(shí)間片。高優(yōu)先級(jí)隊(duì)列的時(shí)間片比低優(yōu)先級(jí)隊(duì)列的小。調(diào)度時(shí)先從高優(yōu)先級(jí)隊(duì)列中選出某一進(jìn)程投入運(yùn)行，當(dāng)該進(jìn)程的時(shí)間片到期后則轉(zhuǎn)至低一級(jí)的就緒隊(duì)列中。只有高優(yōu)先級(jí)隊(duì)列為空時(shí)才從低一級(jí)隊(duì)列中調(diào)度進(jìn)程。 例如考慮由3個(gè)隊(duì)列組成的多級(jí)隊(duì)列調(diào)度。3個(gè)隊(duì)列的編號(hào)分別為0, 1, 2，如圖所示。調(diào)度算法首先調(diào)度0號(hào)隊(duì)列中的進(jìn)程。當(dāng)0號(hào)隊(duì)列為空時(shí)才調(diào)度1號(hào)隊(duì)列中的進(jìn)程；當(dāng)0號(hào)與1號(hào)隊(duì)列都為空時(shí)才調(diào)度2號(hào)隊(duì)列中的進(jìn)程。在剝奪方式下，新進(jìn)入0號(hào)隊(duì)列的進(jìn)程將剝奪1號(hào)或2號(hào)隊(duì)列中正在執(zhí)行的進(jìn)程的CPU，而新進(jìn)入1號(hào)隊(duì)列的進(jìn)程將剝奪2號(hào)隊(duì)列中正在執(zhí)行的進(jìn)程的CPU。 其實(shí)，每個(gè)隊(duì)列都可擁有各自的調(diào)度算法，也可制定不同的“轉(zhuǎn)隊(duì)”規(guī)則。這樣看來，多隊(duì)列反饋調(diào)度算法能有多種變化。 （7）輪轉(zhuǎn)法 輪轉(zhuǎn)法就是按一定時(shí)間片(記為q)輪番運(yùn)行各個(gè)進(jìn)程。如果q是一個(gè)定值，則輪轉(zhuǎn)法是一種對(duì)各進(jìn)程機(jī)會(huì)均等的調(diào)度方法。 輪轉(zhuǎn)法本質(zhì)上是剝奪的，因?yàn)橐惠唭?nèi)，每個(gè)進(jìn)程不能獲得比一個(gè)時(shí)間片q更長(zhǎng)的運(yùn)行時(shí)間。正是由于這一特點(diǎn)，輪轉(zhuǎn)法特別適用于分時(shí)操作系統(tǒng)。 輪轉(zhuǎn)法的關(guān)鍵問題是如何確定q的大小。如果時(shí)間片太大以致每個(gè)進(jìn)程的CPU周期都能在一個(gè)時(shí)間片內(nèi)完成，則輪轉(zhuǎn)法實(shí)際上脫化為FCFS。如果q太小以致CPU切換過于頻繁，則會(huì)增加CPU的額外開銷，降低了CPU的有效利用率。這是因?yàn)?，每次CPU切換涉及到保存原運(yùn)行進(jìn)程的現(xiàn)場(chǎng)和恢復(fù)新運(yùn)行進(jìn)程的現(xiàn)場(chǎng)，這些操作一般需要10ms～100ms的時(shí)間。例如，設(shè)有一個(gè)CPU周期為10單位的進(jìn)程，在q取12，6，1時(shí)的調(diào)度次數(shù)分別為0，1，9。令時(shí)間單位為1ms(1ms=1000ms)，1次調(diào)度的開銷為100ms，則在q=1時(shí)CPU的額外開銷和有效開銷之比為1:10，這是不容忽視的。 （8）最短周期優(yōu)先 最短周期優(yōu)先(SBF: shortest burst first)把當(dāng)前就緒隊(duì)列中的下一個(gè)CPU周期最短的那個(gè)進(jìn)程調(diào)度運(yùn)行。 （9）先來先服務(wù) 如果早就緒的進(jìn)程排在就緒隊(duì)列的前面，遲就緒的進(jìn)程排在就緒隊(duì)列的后面，那么先來先服務(wù)(FCFS: first come first service)總是把當(dāng)前處于就緒隊(duì)列之首的那個(gè)進(jìn)程調(diào)度到運(yùn)行狀態(tài)。也就說，它只考慮進(jìn)程進(jìn)入就緒隊(duì)列的先后，而不考慮它的下一個(gè)CPU周期的長(zhǎng)短及其他因素。FCFS算法簡(jiǎn)單易行，但性能卻不大好。 四、實(shí)驗(yàn)程序 #include “iostream.h” //define pcb typedef struct pcb { char name[10];//進(jìn)程名 char state;//狀態(tài)w(就緒)r(運(yùn)行)f(結(jié)束)int id;//id號(hào) int super;//優(yōu)先級(jí) int ntime;//需運(yùn)行的時(shí)間 int rtime;//已運(yùn)行的時(shí)間 struct pcb *next;}*pcb1; pcb1 s,w;//define two publiced linknode ,one is s(ready queue),one is w(blocked queue) //initialize two queues void init(pcb1 &r){ r=NULL;//both queues is the kind of head index } //print the information of the ready queue void print(){pcb1 p;cout<<“您現(xiàn)在查看的是就緒隊(duì)列的信息:”;cout<<“進(jìn)程號(hào) ”<<“進(jìn)程名 ”<<“優(yōu)先級(jí) ”<<“狀態(tài)”<<“已運(yùn)行時(shí)間 ”<<“需運(yùn)行時(shí)間”< cout< id<<“ ”< name<<“ ”< super<<“ ”< state<<“ ”< rtime<<“ ”< ntime< //print the information of the blocked queue void print1(){pcb1 p;cout<<“您現(xiàn)在查看的是阻塞隊(duì)列的信息”;cout<<“進(jìn)程號(hào) ”<<“進(jìn)程名 ”<<“優(yōu)先級(jí) ”<<“狀態(tài) ”<<“已運(yùn)行時(shí)間 ”<<“需運(yùn)行時(shí)間”< id<<“ ”< name<<“ ”< super<<“ ”< state<<“ ”< rtime<<“ ”< ntime< //check the queue if empty int empty(pcb1 &r){ if(r==NULL)return 0;else return 1;} //check the first process of the ready queue if finshed int check(){ pcb1 p;p=s;if(p->rtime==p->ntime){ p->state='F';//if one process finshed then change ti's state cout<<“進(jìn)程”< id<<“ 已經(jīng)結(jié)束”< //sort process according to the super of the process and insert to the ready(blocked)queue void sort(pcb1 &r,pcb1 p){ pcb1 p1,p2;int in=0;if(r==NULL)//the queue is empty { r=p;} else { if(p->super>=r->super)//the super of the process which wait insert to the queue is highter than the super of the first process of the queue { p->next=r;r=p;} else { p1=r;p2=r->next;if(p2==NULL)//only one process in the queue { r->next=p;} else { while(in==0&&p2!=NULL)//insert to the middle of the queue { if(p->super>=p2->super){ p->next=p2;p1->next=p;in=1;} else { p1=p1->next;p2=p2->next;} } } if(in==0)//link to the last of ready queue p1->next=p;} } } //block one process and insert to block queue void block(){ if(empty(s)){ if(s->next==NULL){ sort(w,s);s=s->next;} else { pcb1 p1;p1=s;s=s->next;p1->next=NULL;sort(w,p1);} } else { cout<<“現(xiàn)在就緒隊(duì)列已經(jīng)為空，再?zèng)]有進(jìn)程需要阻塞”< //wake one process of block queue and insert to ready queue void wake(){ if(empty(w)){ pcb1 p1;p1=w;w=w->next;p1->next=NULL;sort(s,p1);} else { cout<<“阻塞隊(duì)列已經(jīng)為空，沒有進(jìn)程再需要喚醒”< //runing void runing(){ if(empty(s)){ pcb1 p;p=s;if(check())//check the first process of the queue if finished {//no s=s->next;p->rtime++;p->super--;p->next=NULL;sort(s,p);} else {//yes s=s->next;} } else { cout<<“就緒隊(duì)列已經(jīng)為空”< //creat process void input(){ pcb1 p2;p2=new pcb;cout<<“請(qǐng)輸入 進(jìn)程號(hào)、進(jìn)程名、進(jìn)程優(yōu)先級(jí)、需要運(yùn)行時(shí)間”;cin>>p2->id>>p2->name>>p2->super>>p2->ntime;p2->rtime=0;p2->state='W';p2->rtime=0;p2->next=NULL; sort(s,p2);} //main function void main(){ char ch;init(s);init(w);cout<<“*****************************進(jìn)程調(diào)度模擬程序開始*******************************”< 程序運(yùn)行界面如下： 五、實(shí)驗(yàn)總結(jié) 本次實(shí)驗(yàn)，我的任務(wù)是設(shè)計(jì)一個(gè)允許n個(gè)進(jìn)程并發(fā)運(yùn)行的進(jìn)程管理模擬系統(tǒng)。該系統(tǒng)包括有簡(jiǎn)單的進(jìn)程控制、同步與通訊機(jī)構(gòu)，系統(tǒng)在運(yùn)行過程中能顯示各進(jìn)程的狀態(tài)及有關(guān)參數(shù)的變化情況，從而觀察諸進(jìn)程的運(yùn)行過程及系統(tǒng)的管理過程，我是用C++寫的，在我的電腦能夠運(yùn)行通過，雖不能盡善盡美，但也基本能實(shí)現(xiàn)老師的要求。 兩個(gè)星期程序設(shè)計(jì)課程，雖然時(shí)間有點(diǎn)短，但我也收獲不少，這次試驗(yàn)，加深了我對(duì)進(jìn)程概念及進(jìn)程管理的理解；比較熟悉進(jìn)程管理中主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及進(jìn)程調(diào)度算法、進(jìn)程控制機(jī)構(gòu)、同步機(jī)構(gòu)及通訊機(jī)構(gòu)的實(shí)施。也讓我認(rèn)識(shí)到自己的不足，操作系統(tǒng)的有些知識(shí)，我知道的還不多，沒有掌握好，還需要多多學(xué)學(xué)，不斷提升自己的能力。 進(jìn)程調(diào)度算法模擬 專業(yè)：XXXXX 學(xué)號(hào)：XXXXX 姓名：XXX 實(shí)驗(yàn)日期：20XX年XX月XX日 一、實(shí)驗(yàn)?zāi)康?/p> 通過對(duì)進(jìn)程調(diào)度算法的模擬加深對(duì)進(jìn)程概念和進(jìn)程調(diào)度算法的理解。 二、實(shí)驗(yàn)要求 編寫程序?qū)崿F(xiàn)對(duì)5個(gè)進(jìn)程的調(diào)度模擬，要求至少采用兩種不同的調(diào)度算法分別進(jìn)行模擬調(diào)度。 三、實(shí)驗(yàn)方法內(nèi)容 1.算法設(shè)計(jì)思路 將每個(gè)進(jìn)程抽象成一個(gè)控制塊PCB，PCB用一個(gè)結(jié)構(gòu)體描述。 構(gòu)建一個(gè)進(jìn)程調(diào)度類。將進(jìn)程調(diào)度的各種算法分裝在一個(gè)類中。類中存在三個(gè)容器，一個(gè)保存正在或未進(jìn)入就緒隊(duì)列的進(jìn)程，一個(gè)保存就緒的進(jìn)程，另一個(gè)保存已完成的進(jìn)程。還有一個(gè)PCB實(shí)例。主要保存正在運(yùn)行的進(jìn)程。類中其他方法都是圍繞這三個(gè)容器可以這個(gè)運(yùn)行中的PCB展開。 主要用到的技術(shù)是STL中的vector以維護(hù)和保存進(jìn)程容器、就緒容器、完成容器。 當(dāng)程序啟動(dòng)時(shí)，用戶可以選擇不同的調(diào)度算法。然后用戶從控制臺(tái)輸入各個(gè)進(jìn)程的信息，這些信息保存到進(jìn)程容器中。進(jìn)程信息輸入完畢后，就開始了進(jìn)程調(diào)度，每調(diào)度一次判斷就緒隊(duì)列是否為空，若為空則系統(tǒng)時(shí)間加一個(gè)時(shí)間片。判斷進(jìn)程容器中是否有新的進(jìn)程可以加入就緒隊(duì)列。2.算法流程圖 主程序的框架： 開始void FCFS();//先來先服務(wù)void SJF();//最短進(jìn)程優(yōu)先調(diào)度void RR();//簡(jiǎn)單時(shí)間片輪轉(zhuǎn)void PD();//最高優(yōu)先數(shù)優(yōu)先void PCBInput();//輸入進(jìn)程信息選擇調(diào)度算法輸入進(jìn)程信息將輸入容器中以滿足進(jìn)入條件的進(jìn)程調(diào)入就緒隊(duì)列void ProcessQueueProcess();//查看當(dāng)前時(shí)間下，有無進(jìn)程加入。若有則把該進(jìn)程調(diào)入就緒隊(duì)列按照選擇的算法開始選擇就緒隊(duì)列的進(jìn)程開始執(zhí)行void ProcessSelect();//若當(dāng)前就緒隊(duì)列不為空則根據(jù)選擇的調(diào)度算法開始調(diào)度,否則，系統(tǒng)時(shí)間加一個(gè)時(shí)間片.以等待新的進(jìn)程到判斷就緒容器和輸入容器是否為空!processScheduler.m_WaitQueue.empty()||!processScheduler.m_ProcessQueue.empt()Y打印各進(jìn)程信息進(jìn)行統(tǒng)計(jì)計(jì)算周轉(zhuǎn)時(shí)間等結(jié)束void PCBDisplay();//打印當(dāng)前狀況下。就緒隊(duì)列、完成隊(duì)列、運(yùn)行中的進(jìn)程信息void SchedulerStatistics();//調(diào)度統(tǒng)計(jì)，計(jì)算周轉(zhuǎn)時(shí)間等進(jìn)程調(diào)度過程： 開始為空判斷就緒隊(duì)列是否為空if(m_WaitQueue.empty())非空讓系統(tǒng)等待一個(gè)時(shí)間片TimePast()根據(jù)設(shè)定的調(diào)度算法從就緒隊(duì)列中調(diào)入一個(gè)進(jìn)程并執(zhí)行（此時(shí)進(jìn)程從就緒隊(duì)列中刪除，賦值到表示運(yùn)行中的成員變量中）void FCFS();//先來先服務(wù)void SJF();//最短進(jìn)程優(yōu)先調(diào)度void RR();//簡(jiǎn)單時(shí)間片輪轉(zhuǎn)void PD();//最高優(yōu)先數(shù)優(yōu)先進(jìn)程運(yùn)行一個(gè)時(shí)間片N是否達(dá)到該進(jìn)程停止運(yùn)行的條件Y選入的進(jìn)程狀態(tài)是否為“完成”如進(jìn)程已完成，或者分得的時(shí)間片個(gè)數(shù)已到ProcessRun()Yvector m_WaitQueue;//進(jìn)程就緒隊(duì)列進(jìn)程未完成，將進(jìn)程優(yōu)先數(shù)減一，并放回到就緒隊(duì)列中設(shè)置進(jìn)程完成時(shí)間，將該進(jìn)程放入完成隊(duì)列vector m_FinishQueue;//完成隊(duì)列結(jié)束 3.算法中用到的數(shù)據(jù)結(jié)構(gòu) struct fcfs{ //先來先服務(wù)算法從這里開始 char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; //定義一個(gè)結(jié)構(gòu)體，里面包含的有一個(gè)進(jìn)程相關(guān)的信息 4.主要的常量變量 vector m_ProcessQueue;//進(jìn)程輸入隊(duì)列 vector m_WaitQueue;//進(jìn)程就緒隊(duì)列 vector m_FinishQueue;//完成隊(duì)列 vector ::iterator m_iter;//迭代器 PCB m_runProcess;//運(yùn)行中的進(jìn)程 int m_ProcessCount;//進(jìn)程數(shù) float m_RunTime;//運(yùn)行時(shí)間 int m_tagIsRun;//是否在運(yùn)行標(biāo)志。表示正在運(yùn)行，表示沒有 float m_TimeSlice;//時(shí)間片大小 int m_TimeSliceCount;//指時(shí)間片輪轉(zhuǎn)中一次分到的時(shí)間片個(gè)數(shù) char m_SchedulerAlgorithm;//調(diào)度算法 5.主要模塊 void PCBInput();//輸入進(jìn)程信息 void PCBSort();//對(duì)進(jìn)程控制塊按照優(yōu)先級(jí)排序(采用冒泡排序)void ProcessSelect();//若當(dāng)前就緒隊(duì)列不為空則根據(jù)選擇的調(diào)度算法開始調(diào)度。否則，系統(tǒng)時(shí)間void PCBDisplay();//打印當(dāng)前狀況下。就緒隊(duì)列、完成隊(duì)列、運(yùn)行中的進(jìn)程信息 void ProcessRun();//進(jìn)程運(yùn)行一次。運(yùn)行時(shí)間加個(gè)時(shí)間片。并判斷進(jìn)程是否達(dá)到完成條件。若是則void ProcessQueueProcess();//查看當(dāng)前時(shí)間下，有無進(jìn)程加入。若有則把該進(jìn)程調(diào)入就緒隊(duì)列 void ProcessDispatch();//進(jìn)程分派，進(jìn)程執(zhí)行完成后決定進(jìn)程該進(jìn)入哪個(gè)隊(duì)列(就緒、完成)void TimePast(){ m_RunTime +=m_TimeSlice;ProcessQueueProcess();}//當(dāng)前系統(tǒng)時(shí)間加個(gè)時(shí)間void SchedulerStatistics();//調(diào)度統(tǒng)計(jì)，計(jì)算周轉(zhuǎn)時(shí)間等 void FCFS();//先來先服務(wù) void SJF();//最短進(jìn)程優(yōu)先調(diào)度 void RR();//簡(jiǎn)單時(shí)間片輪轉(zhuǎn) void PD();//最高優(yōu)先數(shù)優(yōu)先 加.以等待新的進(jìn)程到來 ProcessStatus='f'.否則為'w';片，并檢查是否有新的進(jìn)程加入 四、實(shí)驗(yàn)代碼 #include using namespace std; struct fcfs{ //先來先服務(wù)算法從這里開始 char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; //定義一個(gè)結(jié)構(gòu)體，里面包含的有一個(gè)進(jìn)程相關(guān)的信息 fcfs a[100]; void input(fcfs *p,int N) { int i; cout< printf(“ 請(qǐng)您輸入進(jìn)程的名字 到達(dá)時(shí)間 服務(wù)時(shí)間:(例如: a 0 100)nn”); for(i=0;i<=N-1;i++) { printf(“ 請(qǐng)您輸入進(jìn)程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime); } } void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) { int k; printf(“nn調(diào)用先來先服務(wù)算法以后進(jìn)程運(yùn)行的順序是: ”); printf(“%s”,p[0].name); for(k=1;k { printf(“-->%s”,p[k].name); } cout< printf(“n 具體進(jìn)程調(diào)度信息:n”); printf(“t進(jìn)程名 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 結(jié)束時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間n”); for(k=0;k<=N-1;k++) { printf(“t%st%-.2ft %-.2ft %-.2ft %-.2ft %-.2ft %-.2fn”,p[k].name,p[k].arrivetime，p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } getchar(); //此處必須要有這個(gè)函數(shù)，否則就看不到顯示器上面的輸出，可以看到的結(jié)果只是一閃而過的一個(gè)框剪 } void sort(fcfs *p,int N)//排序 { for(int i=0;i<=N-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { fcfs temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //運(yùn)行階段 { int k; for(k=0;k<=N-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} } for(k=0;k<=N-1;k++) { p[k].zztime=p[k].finishtime-p[k].arrivetime; p[k].dqzztime=p[k].zztime/p[k].servicetime; } } void FCFS(fcfs *p,int N) { float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); getchar(); } //先來先服務(wù)算法到此結(jié)束 struct sjf{//最短進(jìn)程優(yōu)先調(diào)度算法從這里開始 char name[10];float arrivetime;//到達(dá)時(shí)間 float servicetime;//運(yùn)行時(shí)間 float starttime; //開始時(shí)間 float finishtime; //完成時(shí)間 };sjf a1[100]; void input(sjf *p,int N1)//進(jìn)程信息輸入 { int i;cout< printf(“ 請(qǐng)您輸入進(jìn)程的名字 到達(dá)時(shí)間 服務(wù)時(shí)間:(例如: a 0 100)n”); for(i=0;i<=N1-1;i++){ printf(“ 請(qǐng)您輸入進(jìn)程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} } void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)//最終結(jié)果輸出 { int k; printf(“nt調(diào)用最短進(jìn)程優(yōu)先調(diào)度算法以后進(jìn)程的調(diào)度順序?yàn)?”); printf(“%s”,p[0].name); for(k=1;k {printf(“-->%s”,p[k].name);} cout< printf(“n給個(gè)進(jìn)程具體調(diào)度信息如下:n”); printf(“nt進(jìn)程名t到達(dá)時(shí)間t運(yùn)行時(shí)間t開始時(shí)間t完成時(shí)間n”); for(k=0;k<=N1-1;k++) { printf(“ t%st %-.2ftt %-.2ftt %-.2ftt %-.2ftn”,p[k].name,p[k].arrivetime，p[k].servicetime,p[k].starttime,p[k].finishtime); } getchar(); } void sort(sjf *p,int N1)//排序 { for(int i=0;i<=N1-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { sjf temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//運(yùn)行階段 { int k; for(k=0;k<=N1-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+float(p[k].servicetime)/60;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+float(p[k].servicetime)/60;} } } void sjff(sjf *p,int N1){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0; sort(p,N1); for(int m=0;m {if(m==0) p[m].finishtime=p[m].arrivetime+float(p[m].servicetime)/60; else p[m].finishtime=p[m-1].finishtime+float(p[m].servicetime)/60; int i=0; for(int n=m+1;n<=N1-1;n++) { if(p[n].arrivetime<=p[m].finishtime) i++; } float min=p[m+1].servicetime; int next=m+1; for(int k=m+1;k { if(p[k+1].servicetime {min=p[k+1].servicetime; next=k+1;} } sjf temp; temp=p[m+1]; p[m+1]=p[next]; p[next]=temp; } deal(p,arrivetime,servicetime,starttime,finishtime,N1); Print(p,arrivetime,servicetime,starttime,finishtime,N1); getchar();}//最短進(jìn)程優(yōu)先調(diào)度算法到這里結(jié)束 char menu()//用來輸出相關(guān)信息的函數(shù) { char cse1; while(1) { system(“cls”); fflush(stdin); cout< cout< cout<<“t”<<“|| <<<<<<<<<<<<歡<<<<<<<<<<< >>>>>>>>>>>>迎>>>>>>>>>>> ||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“t 進(jìn)程調(diào)度算法模擬”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 1.先來先服務(wù)調(diào)度算法 ”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 2.最短進(jìn)程優(yōu)先調(diào)度算法”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“|| <<<<<<<<<<<<<<<<<<<<<<<<<您>>>>>>>>>>>>>>>>>>>>>>>>> ||”< cout< cout< cout<<“tt 請(qǐng)輸入您的選擇（1/2）：”; cse1=getchar(); if(cse1<'1'||cse1>'2') cout<<“你的輸入有錯(cuò)！”< else break; } return cse1;} int main(int argc, char *argv[]){ while(1) { switch(menu()) { case '1': int N; cout< cout< printf(“tt<<---！!@@@先來先服務(wù)調(diào)度算法@@@！!--->>n”); cout< printf(“輸入進(jìn)程數(shù)目:”); scanf(“%d”,&N); input(a,N); FCFS(a,N); case '2': int N1; cout< cout< printf(“tt<<---！!@@@最短進(jìn)程優(yōu)先調(diào)度算法@@@！!--->>n”); cout< printf(“輸入進(jìn)程數(shù)目: ”); scanf(“%d”,&N1); input(a1,N1); sjf *b=a1; sjf *c=a1; sjff(b,N1); getchar(); } } system(“PAUSE”); return EXIT_SUCCESS;} 五、實(shí)驗(yàn)結(jié)果 1.執(zhí)行結(jié)果 2.結(jié)果分析 先來先服務(wù)調(diào)度算法就是根據(jù)進(jìn)程達(dá)到的時(shí)間為依據(jù)，哪一個(gè)進(jìn)程先來那么該進(jìn)程就會(huì)先執(zhí)行；最短進(jìn)程優(yōu)先調(diào)度算法則是以每個(gè)進(jìn)程執(zhí)行所需時(shí)間長(zhǎng)短為依據(jù)，某一個(gè)進(jìn)程執(zhí)行所需花的時(shí)間要短些那么該進(jìn)程就先執(zhí)行。以上就是本次進(jìn)程調(diào)度實(shí)驗(yàn)的依據(jù)。 六、實(shí)驗(yàn)總結(jié) 通過本次實(shí)驗(yàn)了解到算法很重要，又更加明白算法本身可以節(jié)約時(shí)間，而且不同的函數(shù)之間在調(diào)用的時(shí)候要注意很多的問題。 自己寫的：（功能感覺達(dá)到我要目的，感覺沒有把操作量層次寫出來，大家參考學(xué)習(xí)） #include #define max 80//假設(shè)汽車的最大容量為80 int num=0;//初始還沒有啟動(dòng)客車上的人數(shù)為0 int sc=0;//上車的人數(shù) int xc=0;//下車的人數(shù) int k;//上車-下車，停站上下車后后人數(shù)變化，即凈上車人數(shù)； //k=sc-xc;//凈上車人數(shù)/ int dr();int cd(); int check(){ if(sc==-1||xc==-1) {cout<<“旅途愉快，汽車到達(dá)總站，再見”< exit(1); } return 0;} int dr()//司機(jī)driver的信號(hào)量 { //num=num+k;if(num<=max){ cout<<“汽車關(guān)門準(zhǔn)備開車！”< } cout<<“司機(jī)開車！”< int c,sji;//超載人數(shù)/實(shí)際上車人數(shù) k=sc-xc;//凈上車人數(shù)/ num=num+k;//上下乘客后車上人數(shù) if(num<=max) { cout<<“現(xiàn)在車上人數(shù)為：”< cout<<“坐好扶穩(wěn)！”< cout<<“===================================”< cout<<“===================================”< cout<<“===================================”< } if(num>max) { c=num-max;sji=sc-c; cout<<“超載”< num=max;cout<<“已下”< } return 0;} /*主函數(shù)*/ int main(){ cout<<“=========歡迎使用司機(jī)與售票員信息量同步公交車系統(tǒng)=============”< cout<<“請(qǐng)輸入上車人數(shù)！”< while(num>max) { cout<<“警告：輸入上車人數(shù)后，人數(shù)已經(jīng)超過限載人數(shù),輸入錯(cuò)誤請(qǐng)重新輸入”< cout<<“重新輸入上車人數(shù)為：”< cin>>sc; num=sc; check(); } cout<<“第一次啟動(dòng)上車人數(shù)為”< check(); while(sc!=-1||xc!=-1) { cout<<“汽車行駛中.......！”< cout<<“請(qǐng)輸入下車人數(shù)！”< check(); while(xc>num) { cout<<“輸入下車人數(shù)超過車上人數(shù)，輸入錯(cuò)誤，請(qǐng)重新輸入”< cout<<“重新輸入下車人數(shù)為：”< cin>>xc; check(); } cout<<“請(qǐng)輸入上車人數(shù)！”< //cout<<“上車人數(shù)為”< check();if(num>max) { cout<<“警告：輸入上車人數(shù)后車?yán)锶藬?shù)已經(jīng)超過車的限載人數(shù)”< } //num=num+sc-xc;//上下乘客后車上人數(shù) //cout<<“車上人數(shù)總共為”< dr(); } return 0;} 網(wǎng)上下載的：好像作者上傳缺少311.h頭文件 #include using namespace std; HANDLE Semaphore_dirver;//司機(jī)信號(hào)量的句柄 HANDLE Semaphore_condutor;//售票員信號(hào)量的句柄 int num_station=0; //司機(jī)進(jìn)程 void Thread_Driver(){ while(true) { if(WaitForSingleObject(Semaphore_dirver,INFINITE)==WAIT_OBJECT_0)//相當(dāng)與P(Semaphore_dirver)操作 {cout<<“汽車行駛中，請(qǐng)您扶穩(wěn)坐好！”< Sleep(5000);//行車時(shí)間 } ReleaseSemaphore(Semaphore_condutor, 1, NULL);//相當(dāng)與V(Semaphore_condutor)操作提醒售票員可以售票了 } } //售票員進(jìn)程 void Thread_Conductor(){ while(true) { if(WaitForSingleObject(Semaphore_condutor,INFINITE)==WAIT_OBJECT_0)//判斷車是否已停 if(!num_station) //第一站 {cout<<“沒人下車”< num_station++; NUM_ON=random_num(NUM_MAX); Sleep(3000);//乘客上車時(shí)間 cout< NUM_CURRENT=NUM_ON+NUM_INITIAL;//起始站上車的人數(shù) } else { cout<<“車輛進(jìn)站，請(qǐng)您注意安全！開門請(qǐng)當(dāng)心，下車請(qǐng)走好！下車后請(qǐng)勿從車前繞行！”< Sleep(3000);//乘客下車時(shí)間 NUM_DOWN=random_num(NUM_CURRENT);//下車人數(shù) cout< NUM_CURRENT=NUM_CURRENT-NUM_DOWN;//下車后的人數(shù) if(NUM_CURRENT { cout<<“311路無人售票車開往南門，請(qǐng)您按順序投幣上車！”< cout<<“上車的乘客請(qǐng)從后門移動(dòng)，準(zhǔn)備下車！”< Sleep(3000);//乘客上車時(shí)間 NUM_ON=random_num(NUM_MAX-NUM_CURRENT);//上車人數(shù) cout< NUM_CURRENT=NUM_CURRENT+NUM_ON;//上車后人數(shù) cout<<“車上有”< } else cout<<“座位已滿，請(qǐng)等下一輛！”< } ReleaseSemaphore(Semaphore_dirver,1,NULL);//讓司機(jī)開車的信號(hào) } } /*主函數(shù)*/ int main(){ HANDLE thread[2];//定義兩個(gè)線程句柄 Semaphore_dirver = CreateSemaphore(NULL,1, 1, NULL);//司機(jī)信號(hào)量 Semaphore_condutor = CreateSemaphore(NULL, 0, 1, NULL);//售票員信號(hào)量 DWORD threadID[2]; thread[0]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Thread_Driver),NULL,0,&threadID[0]);//司機(jī)進(jìn)程 thread[1]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Thread_Conductor),NULL,0,&threadID[1]);//售票員進(jìn)程 WaitForMultipleObjects(1, thread, TRUE, INFINITE);//等待兩個(gè)線程結(jié)束 return 0;} 實(shí) 驗(yàn) 二 經(jīng) 典 的 生 產(chǎn) 者 — 消 費(fèi) 者 問 題 一、目的 實(shí)現(xiàn)對(duì)經(jīng)典的生產(chǎn)者—消費(fèi)者問題的模擬，以便更好的理解經(jīng)典進(jìn)程同步問題。 二、實(shí)驗(yàn)內(nèi)容及要求 編制生產(chǎn)者—消費(fèi)者算法，模擬一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者，共享一個(gè)緩沖池的情形。 1、實(shí)現(xiàn)對(duì)經(jīng)典的生產(chǎn)者—消費(fèi)者問題的模擬，以便更好的理解此經(jīng)典進(jìn)程同步問題。生產(chǎn)者－ 消費(fèi)者問題是典型的 PV 操作問題，假設(shè)系統(tǒng)中有一個(gè)比較大的緩沖池，生產(chǎn)者的任務(wù)是只要緩沖池未滿就可以將生產(chǎn)出的產(chǎn)品放入其中，而消費(fèi)者的任務(wù)是只要緩沖池未空就可以從緩沖池中拿走產(chǎn) 品。緩沖池被占用時(shí)，任何進(jìn)程都不能訪問。 2、每一個(gè)生產(chǎn)者都要把自己生產(chǎn)的產(chǎn)品放入緩沖池，每個(gè)消費(fèi)者從緩沖池中取走產(chǎn)品消費(fèi)。在這種情況下，生產(chǎn)者消費(fèi)者進(jìn)程同步，因?yàn)橹挥型ㄟ^互通消息才知道是否能存入產(chǎn)品或者取走產(chǎn)品。他們之間也存在互斥，即生產(chǎn)者消費(fèi)者必須互斥訪問緩沖池，即不能有兩個(gè)以上的進(jìn)程同時(shí)進(jìn)行。 三、生產(chǎn)者和消費(fèi)者原理分析 在同一個(gè)進(jìn)程地址空間內(nèi)執(zhí)行兩個(gè)線程。 生產(chǎn)者線程生產(chǎn)物品，然后將物品放置在一個(gè)空緩沖區(qū)中供消費(fèi)者線程消費(fèi)。 消費(fèi)者線程從緩沖區(qū)中獲得物品，然后釋放緩沖區(qū)。 當(dāng)生產(chǎn)者線程生產(chǎn)物品時(shí)，如果沒有空緩沖區(qū)可用，那么生產(chǎn)者線程必須等待消費(fèi)者線程釋放一個(gè)空緩沖區(qū)。 當(dāng)消費(fèi)者線程消費(fèi)物品時(shí)，如果沒有滿的緩沖區(qū)，那么消費(fèi)者線程將被阻擋，直到新的物品被生產(chǎn)出來。 四、生產(chǎn)者與消費(fèi)者功能描述： 生產(chǎn)者功能描述：在同一個(gè)進(jìn)程地址空間內(nèi)執(zhí)行兩個(gè)線程。生產(chǎn)者線程生產(chǎn)物品，然后將物品放置在一個(gè)空緩沖區(qū)中供消費(fèi)者線程消費(fèi)。當(dāng)生產(chǎn)者線程生產(chǎn)物品時(shí)，如果沒有空緩沖區(qū)可用，那么生產(chǎn)者線程必須等待消費(fèi)者線程釋放出一個(gè)空緩沖區(qū)。 消費(fèi)者功能描述：消費(fèi)者線程從緩沖區(qū)獲得物品，然后釋放緩沖區(qū)，當(dāng)消費(fèi)者線程消費(fèi)物品時(shí)，如果沒有滿的緩沖區(qū)，那么消費(fèi)者線程將被阻塞，直到新的物品被生產(chǎn)出來。 五、實(shí)驗(yàn)環(huán)境 操作系統(tǒng)環(huán)境： Windows 系統(tǒng)。編程語言： C#。 六、生產(chǎn)者與消費(fèi)者的思路和設(shè)計(jì) 1、程序流程圖 (1)生產(chǎn)者 開 始 生產(chǎn)產(chǎn)品 Wait empty ≤ 0 Y N Wait 緩沖區(qū)內(nèi)已滿，已無 可用緩沖區(qū) N Mutex=1 Y 緩沖區(qū)正被其他 程占用 進(jìn) 存入緩沖區(qū) empty = empty-1 Signal Signal(full)結(jié) 束 (2)消費(fèi)者 開 始 Wait(full)消費(fèi)請(qǐng)求 full ≤ 0 Y N Wait 緩沖區(qū)內(nèi)產(chǎn)品已空，不能進(jìn)行消費(fèi) N Mutex=1 Y 消 費(fèi) 緩沖區(qū)正被其他 程占用 進(jìn) full = full-1 Signal Signal 結(jié) 束 2、主要程序代碼 // 初始化變量 private void Form1_Load(object sender, EventArgs e){ mutex = 1;// 互斥信號(hào)量 full = 0;// 緩沖池中滿緩沖區(qū)的數(shù)量 empty = 5;// 緩沖池中空緩沖區(qū)的數(shù)量 count1 = 0;// 生產(chǎn)的產(chǎn)品數(shù)目 i = 0;= “1”;= “0”;= “5”;} // 消費(fèi)者從緩沖區(qū)中消費(fèi)一個(gè)產(chǎn)品 private void consumer_Click(object sender, EventArgs e){ if(full > 0){ // 消費(fèi)者已進(jìn)入互斥臨界區(qū) if(mutex == 1)// 申請(qǐng)進(jìn)入臨界區(qū) { mutex = 0;// 消費(fèi)者已進(jìn)入互斥臨界區(qū) = “0”;= true;// 啟動(dòng)消費(fèi)者消費(fèi)緩沖區(qū)產(chǎn)品 } else {(“ 緩沖區(qū)被占用，請(qǐng)等待。。 ”, “ 信息提 ”;} } else {(“ 緩沖區(qū)為空，不能消費(fèi)!”, “ 信息提示 ”,;} } // 生產(chǎn)者向緩沖區(qū)中存入一個(gè)產(chǎn)品 private void producer_Click(object sender, EventArgs e){ count1 = count1 + if(empty > 0){ 1; // // 生產(chǎn)一個(gè)產(chǎn)品 有緩沖區(qū)可放產(chǎn)品 if(mutex == 1){ // 申請(qǐng)進(jìn)入臨界區(qū) mutex = 0; // 生產(chǎn)者已進(jìn)入臨界區(qū) = “0”; ();// 啟動(dòng)生產(chǎn)者將產(chǎn)品放入緩沖區(qū) } else { // 不能進(jìn)入臨界區(qū) count1 = count1-1;(“ 緩沖區(qū)被占用，請(qǐng)等待。。 ”, “ 信息提示 ”,;} } else {(“ 緩沖區(qū)已滿!”, “ 信息提示 ”,;// 無緩沖區(qū)可放產(chǎn)品 count1 = count1-1;} } // 生產(chǎn)者 private void timer1_Tick_1(object sender, EventArgs e){ if(bool1){ switch(count1){ case 1: = true;break;case 2: = true;break;case 3: = true;break;case 4: = true;break;case 5: = true;break;} = “ 生產(chǎn)者進(jìn)程占用緩沖區(qū)，請(qǐng)等待。。 ”;bool1 = false;} else { switch(count1){ case 1: = false;break;case 2: = false;break;case 3: = false;break;case 4: = false;break;case 5: = false;break;} = “ 生產(chǎn)者進(jìn)程占用緩沖區(qū)，請(qǐng)等待。。 ”;bool1 = true;} i = i + 1;if(i == 5) { // 循環(huán)緩沖區(qū)，首尾相接 i = 0;= false;mutex = 1;= “1”;switch(count1){ case 1: = true;break;case 2: = true;break;case 3: = true;break;case 4: = true;break;case 5: = true;break;} full = full + 1;=();empty = empty-1;=();= “ 生產(chǎn)結(jié)束!”;} } // 消費(fèi)者 private void timer_consumer_Tick(object sender, EventArgs e){ if(bool1){ switch(count1){ case 1: = true;break;case 2: = true;break;case 3: = true;break;case 4: = true;break;case 5: = true;break;} = “ 消費(fèi)者進(jìn)程占用緩沖區(qū)，請(qǐng)等待。。 ”;bool1 =false;} else{ switch(count1){ case 1: = false;break;case 2: = false;break;case 3: = false;break;case 4: = false;break;case 5: = false;break;} = “ 消費(fèi)者進(jìn)程占用緩沖區(qū)，請(qǐng)等待。。 ”;bool1= true;} i = i + 1;if(i==5){ i = 0;= false;mutex = 1;= “1”;switch(count1){ case 1: = false;break;case 2: = false;break;case 3: = false;break;case 4: = false;break;case 5: = false;break;} count1 = count1-1;full = full-1;=();empty = empty+1;=();=“ 消費(fèi)結(jié)束！ ”;} 3、運(yùn)行界面和運(yùn)行結(jié)果 一般情況下，點(diǎn)一次生產(chǎn)者按紐，mutex 由 1 變?yōu)?0，緩沖區(qū)呈現(xiàn)閃爍狀態(tài)（表示正在存儲(chǔ)），此時(shí)不可以再進(jìn)行緩沖區(qū)操作，否則將顯示“生產(chǎn)者進(jìn)程正在占用緩沖區(qū)，請(qǐng)等待”。閃爍約秒后，mutex 由 0 變?yōu)?1，閃爍停止，表示存儲(chǔ)過程結(jié)束；點(diǎn)一次消費(fèi)者按紐，mutex 由 1 變?yōu)?0，緩沖區(qū)呈現(xiàn)閃爍狀態(tài)（表示正在消費(fèi)），此時(shí)不可以再進(jìn)行緩沖區(qū)操作，否則將顯示“消費(fèi)者進(jìn)程正在占用緩 沖區(qū)，請(qǐng)等待”。閃爍約秒后，mutex 由 0 變?yōu)?1，閃爍停止，表示消費(fèi)過程結(jié)束。緩沖池滿后，若再點(diǎn)生產(chǎn)者按紐，會(huì)給出信息提示： “緩沖區(qū)已滿!”。 緩沖池空后，若再點(diǎn)消費(fèi)者按紐，也會(huì)給出信息提示： “緩沖區(qū)為空，不能消費(fèi)!”。 在存儲(chǔ)狀態(tài)或消費(fèi)狀態(tài)（閃爍狀態(tài)），無論是點(diǎn)生產(chǎn)者按紐還是消費(fèi)者按紐都會(huì)給出“緩沖區(qū)被占用，請(qǐng)等待?！毙畔⑻崾?。 七、心得體會(huì) 本次實(shí)驗(yàn)是關(guān)于生產(chǎn)者與消費(fèi)者之間互斥和同步的問題。問題的是指是 P、V 操作，實(shí)驗(yàn)設(shè)一個(gè)共享緩沖區(qū)，生產(chǎn)者和消費(fèi)者互斥的使用，當(dāng)一個(gè)線程使用緩沖區(qū)的時(shí)候，另一個(gè)讓其等待直到前一 個(gè)線程釋放緩沖區(qū)為止。 生產(chǎn)者與消費(fèi)者是一個(gè)與現(xiàn)實(shí)有關(guān)的經(jīng)驗(yàn)問題，通過此原理舉一反三可以解決其他類似的問題。 通過本實(shí)驗(yàn)設(shè)計(jì)，我們對(duì)操作系統(tǒng)的 P、V 進(jìn)一步的認(rèn)識(shí)，深入的了解 P、V 操作的實(shí)質(zhì)和其重 要性。課本的理論知識(shí)進(jìn)一步闡述了現(xiàn)實(shí)中的實(shí)際問題。 實(shí)驗(yàn)中，我們小組分工合作，共同學(xué)習(xí)，雖然在實(shí)驗(yàn)中遇到了一些問題，但在老師和同學(xué)的細(xì)心指導(dǎo)和熱心幫助下解決了。同時(shí)，了解到團(tuán)隊(duì)精神的重要性，也為以后的學(xué)習(xí)和工作打下了堅(jiān)實(shí)的基礎(chǔ)，同時(shí)積累了寶貴的經(jīng)驗(yàn)。第二篇：操作系統(tǒng)進(jìn)程管理系統(tǒng)設(shè)計(jì)實(shí)驗(yàn)報(bào)告
第三篇：操作系統(tǒng)進(jìn)程調(diào)度算法模擬實(shí)驗(yàn)報(bào)告
第四篇：司機(jī)與售票員原創(chuàng) 完整代碼
第五篇：操作系統(tǒng)實(shí)驗(yàn)報(bào)告經(jīng)典生產(chǎn)者—消費(fèi)者問題
點(diǎn)擊咨詢 