操作系统实验1—实现单处理机下的进程调度程序
生活随笔
收集整理的這篇文章主要介紹了
操作系统实验1—实现单处理机下的进程调度程序
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
操作系統(tǒng)實驗1—實現(xiàn)單處理機下的進程調(diào)度程序
文章目錄
- 操作系統(tǒng)實驗1—實現(xiàn)單處理機下的進程調(diào)度程序
- 實驗描述
- 設(shè)計思路
- 上機代碼
- 測試結(jié)果
- 心得體會
實驗描述
實驗內(nèi)容：
編寫一個單處理機下的進程調(diào)度程序，模擬操作系統(tǒng)對進程的調(diào)度。
實驗?zāi)康?#xff1a;
進程是操作系統(tǒng)中最基本、最重要的概念，進程調(diào)度又是操作系統(tǒng)的核心模塊。本實驗要求學(xué)生獨立設(shè)計并實現(xiàn)進程調(diào)度模擬程序，以加深對進程控制塊概念和各種進程調(diào)度算法的理解。
實驗要求：
測試用例格式如下：
輸入：
調(diào)度算法
進程號/到達時間/運行時間/優(yōu)先級/時間片
其中調(diào)度算法選項為：
1----先來先服務(wù)，
2----短作業(yè)優(yōu)先，
3----最短剩余時間優(yōu)先，
4----時間片輪轉(zhuǎn)，
5----動態(tài)優(yōu)先級
輸出：
調(diào)度順序/進程號/開始運行時間/結(jié)束運行時間/優(yōu)先級
| 測試用例 1 | 1 1/0/24/1/1 2/0/3/1/1 3/0/3/1/1 | 1/1/0/24/1 2/2/24/27/1 3/3/27/30/1 | 1秒 | 64M | 0 |
| 測試用例 2 | 2 1/0/7/1/1 2/2/4/1/1 3/4/1/1/1 4/5/4/1/1 | 1/1/0/7/1 2/3/7/8/1 3/2/8/12/1 4/4/12/16/1 | 1秒 | 64M | 0 |
| 測試用例 3 | 3 1/0/7/1/1 2/2/4/1/1 3/4/1/1/1 4/5/4/1/1 | 1/1/0/2/1 2/2/2/4/1 3/3/4/5/1 4/2/5/7/1 5/4/7/11/1 6/1/11/16/1 | 1秒 | 64M | 0 |
| 測試用例 4 | 4 1/0/53/1/20 2/0/17/1/20 3/0/68/1/20 4/0/24/1/20 | 1/1/0/20/1 2/2/20/37/1 3/3/37/57/1 4/4/57/77/1 5/1/77/97/1 6/3/97/117/1 7/4/117/121/1 8/1/121/134/1 9/3/134/154/1 10/3/154/162/1 | 1秒 | 64M | 0 |
| 測試用例 5 | 5 1/0/3/1/2 2/0/4/1/2 3/0/2/3/2 4/2/1/1/2 5/2/4/4/2 | 1/1/0/2/4 2/2/2/4/3 3/4/4/5/3 4/3/5/7/3 5/1/7/8/4 6/2/8/10/3 7/5/10/12/3 8/5/12/14/6 | 1秒 | 64M | 0 |
設(shè)計思路
因為每一個進程輸入的時候需要輸入進程號、到達時間、運行時間、優(yōu)先級、時間片五個屬性，想到使用結(jié)構(gòu)體來存儲這些屬性；同時進程輸出的時候又要有調(diào)度順序、開始運行時間、結(jié)束運行時間三個屬性，以及短作業(yè)優(yōu)先算法中還要判斷進程是否運行結(jié)束，所以將進程需要用到的全部屬性都存儲在結(jié)構(gòu)體里面。
時間片輪轉(zhuǎn)算法中需要用到隊列+結(jié)構(gòu)體數(shù)組的形式來實現(xiàn)算法，其余四個算法使用結(jié)構(gòu)體數(shù)組的形式實現(xiàn)算法。
struct process {int pid; //進程號int comeTime; //到達時間int runTime; //運行所需時間int beginTime; //開始運行的時間int endTime; //結(jié)束運行的時間int order; //調(diào)度順序int priority; //優(yōu)先級int slot; //時間片int finish; //結(jié)束標(biāo)志 }que[1010];queue<process>q; //就緒隊列，用于時間片輪轉(zhuǎn)算法程序概要設(shè)計如下圖所示：
上機代碼
代碼使用 C++ 語言進行編寫
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> using namespace std; struct process {int pid;//進程號 int comeTime;//到達時間 int runTime;//運行所需時間 int beginTime;//開始運行的時間 int endTime;//結(jié)束運行的時間 int order;//調(diào)度順序 int priority;//優(yōu)先級 int slot;//時間片 int finish;//結(jié)束標(biāo)志 }que[1010]; void FCFS();//先來先服務(wù) void SJF();//不可剝奪的短作業(yè)優(yōu)先算法 void SRTF();//可剝奪式的短作業(yè)優(yōu)先算法 void RR();//時間片輪轉(zhuǎn) void DPSA();//動態(tài)優(yōu)先級 bool cmp1(process, process);//FCFS、RR、DPSA bool cmp2(process, process);//SJF、SRTF int num;//輸入的總進程數(shù) const int IsEnd = 1;//進程已經(jīng)結(jié)束 const int NoEnd = 0;//進程還未結(jié)束 int main() {//freopen("osin.txt", "r", stdin); //freopen("osout.txt", "w", stdout); int sig = 0;cin >> sig; //算法選擇標(biāo)志 //讀入數(shù)據(jù) num = 0;while (~scanf("%d/%d/%d/%d/%d", &que[num].pid, &que[num].comeTime, &que[num].runTime, &que[num].priority, &que[num].slot)){que[num].beginTime = que[num].endTime = que[num].order = 0;que[num].finish = NoEnd;num++;}//選擇算法 switch (sig){case 1:FCFS(); break;case 2:SJF(); break;case 3:SRTF(); break;case 4:RR(); break;case 5:DPSA(); break;}return 0; } void FCFS() {sort(que, que + num, cmp1);//先來后到排好序 for (int i = 0; i < num; i++){que[i].order = i + 1;if (i == 0)//第一個進程特判一下 {que[i].beginTime = que[i].comeTime;}else{que[i].beginTime = max(que[i].comeTime, que[i - 1].endTime);}que[i].endTime = que[i].beginTime + que[i].runTime;//輸出 printf("%d/%d/%d/%d/%d\n", que[i].order, que[i].pid, que[i].beginTime, que[i].endTime, que[i].priority);} } void SJF() {sort(que, que + num, cmp2);int lastTime = que[0].comeTime;//當(dāng)前時間 int tmp = 0;//每次選中的短作業(yè) for (int i = 0; i < num; i++)//篩選num次，每次選出最佳的短作業(yè) {bool isBool = false;//判斷當(dāng)前時間是否有短作業(yè)在就緒隊列中 while (1){if (i == 0){//排序后的第一個肯定滿足條件，特判 break;}else{for (int j = 1; j < num; j++)//for一遍的復(fù)雜度為O(n),比排序O(nlogn)快 {if (que[j].finish == IsEnd)//當(dāng)前短作業(yè)已經(jīng)結(jié)束就跳過 continue;if (que[j].comeTime <= lastTime)//當(dāng)前短作業(yè)在就緒隊列中 {if (isBool == false)//沒有標(biāo)記最優(yōu)短作業(yè) {isBool = true;tmp = j;}else//已經(jīng)標(biāo)記了最優(yōu)短作業(yè) {//比較，更新最優(yōu)短作業(yè) //當(dāng)短作業(yè)運行時間相等時，優(yōu)先調(diào)度進程號小的短作業(yè)執(zhí)行 if (que[j].runTime < que[tmp].runTime)tmp = j;else if (que[j].runTime == que[tmp].runTime&&que[j].pid < que[tmp].pid)tmp = j;}}}if (isBool)//如果存在短進程滿足條件就輸出 break;else//不存在就把時間后移再尋找 lastTime++;}}que[tmp].order = i + 1;que[tmp].beginTime = max(que[tmp].beginTime, lastTime);que[tmp].endTime = que[tmp].beginTime + que[tmp].runTime;printf("%d/%d/%d/%d/%d\n", que[tmp].order, que[tmp].pid, que[tmp].beginTime, que[tmp].endTime, que[tmp].priority);lastTime = que[tmp].endTime;//更新當(dāng)前時間 que[tmp].finish = IsEnd;//標(biāo)記短作業(yè)結(jié)束 } } void SRTF() {sort(que, que + num, cmp2);int lastTime = que[0].comeTime;int ID = 1;//輸出順序 int tmp = 0, counts = 0;//當(dāng)前進程，輸出次數(shù) int isRun = -1, start = 0;//當(dāng)前是否有進程運行,運行開始時間 while (counts < num){while (que[tmp].comeTime <= lastTime && tmp < num)//當(dāng)前時間內(nèi)的進程 {tmp++;}int minx = 0x3f3f3f, minId = -1;//最短時間和下標(biāo) for (int i = 0; i < tmp; i++)//尋找當(dāng)前進程中剩余運行時間最短的進程 {if (que[i].runTime < minx && que[i].finish == NoEnd){minx = que[i].runTime;minId = i;}}if (minId == -1)//如果當(dāng)前時間進程都結(jié)束了就等待下一個進程 {lastTime = que[tmp].comeTime;continue;}if (isRun == -1)//當(dāng)前沒有進程在運行 {isRun = minId;start = max(que[isRun].comeTime, lastTime);//運行剛找到的進程 }//如果找到進程的剩余運行時間小于當(dāng)前進程的剩余運行時間 if (que[minId].runTime < que[isRun].runTime){que[isRun].order = ID++;que[isRun].beginTime = start;que[isRun].endTime = lastTime;printf("%d/%d/%d/%d/%d\n", que[isRun].order, que[isRun].pid, que[isRun].beginTime, que[isRun].endTime, que[isRun].priority);isRun = minId;start = lastTime;}//運行進程 int run = que[tmp].comeTime - lastTime;//進程能運行完就運行完 if (run >= que[isRun].runTime || run <= 0){lastTime += que[isRun].runTime;que[isRun].order = ID++;que[isRun].beginTime = start;que[isRun].endTime = lastTime;printf("%d/%d/%d/%d/%d\n", que[isRun].order, que[isRun].pid, que[isRun].beginTime, que[isRun].endTime, que[isRun].priority);que[isRun].runTime = 0;que[isRun].finish = IsEnd;counts++;isRun = -1;start = lastTime;}//進程不能運行完就運行一個時間片 else{lastTime += run;que[isRun].runTime -= run;}} } void RR() {sort(que, que + num, cmp1);queue<process>q;//就緒隊列 int lastTime = 0;//當(dāng)前時間 int ID = 1;//輸出順序 int tmp = 0, counts = 0;//當(dāng)前進程，輸出次數(shù) while (counts < num){if (q.empty())//隊列為空則等待進程到來 {lastTime = que[tmp].comeTime;while (que[tmp].comeTime <= lastTime && tmp < num)//當(dāng)前時間內(nèi)的進程 {if (que[tmp].finish == NoEnd)//還沒完成的進程入隊 {q.push(que[tmp]);}tmp++;}}else{process ans = q.front();//取出處于隊列頭的進程 q.pop();//進程可以運行完 if (ans.runTime <= ans.slot){//輸出當(dāng)前進程調(diào)度 ans.order = ID++;ans.beginTime = lastTime;ans.endTime = ans.beginTime + ans.runTime;printf("%d/%d/%d/%d/%d\n", ans.order, ans.pid, ans.beginTime, ans.endTime, ans.priority);lastTime = ans.endTime;//更新當(dāng)前時間 ans.finish = IsEnd;//標(biāo)記短作業(yè)結(jié)束 counts++;while (que[tmp].comeTime <= lastTime && tmp < num)//當(dāng)前時間內(nèi)的進程 {if (que[tmp].finish == NoEnd)//還沒完成的進程入隊 {q.push(que[tmp]);}tmp++;}}//進程不能運行完 else{//輸出當(dāng)前進程調(diào)度 ans.order = ID++;ans.beginTime = lastTime;ans.endTime = ans.beginTime + ans.slot;printf("%d/%d/%d/%d/%d\n", ans.order, ans.pid, ans.beginTime, ans.endTime, ans.priority);lastTime = ans.endTime;ans.runTime -= ans.slot;while (que[tmp].comeTime <= lastTime && tmp < num)//當(dāng)前時間內(nèi)的進程 {if (que[tmp].finish == NoEnd)//還沒完成的進程入隊 {q.push(que[tmp]);}tmp++;}q.push(ans);//先讓新進程入隊再讓當(dāng)前進程入隊 }}} } void DPSA() {sort(que, que + num, cmp1);int lastTime = que[0].comeTime;//當(dāng)前時間 int ID = 1;//輸出順序 int tmp = 0, counts = 0;//當(dāng)前進程，輸出次數(shù) int start = lastTime;//當(dāng)前進程開始時間 int minId, Smin;while (counts < num){while (que[tmp].comeTime <= lastTime && tmp < num)//當(dāng)前時間內(nèi)的進程 {if (que[tmp].comeTime > start && que[tmp].comeTime < lastTime){que[tmp].priority = max(que[tmp].priority - 1, 0);//等待時優(yōu)先級加1 }tmp++;}//尋找最高優(yōu)先級進程 minId = -1;Smin = 0x3f3f3f;for (int i = 0; i < tmp; i++){if (que[i].priority < Smin && que[i].finish == NoEnd){Smin = que[i].priority;minId = i;}}if (minId == -1)//如果當(dāng)前時間進程都結(jié)束了就等待下一個進程 {lastTime = que[tmp].comeTime;continue;}//運行進程 start = lastTime;//進程能運行完 if (que[minId].runTime <= que[minId].slot){que[minId].order = ID++;que[minId].beginTime = lastTime;que[minId].endTime = lastTime + que[minId].runTime;printf("%d/%d/%d/%d/%d\n", que[minId].order, que[minId].pid, que[minId].beginTime, que[minId].endTime, que[minId].priority + 3);counts++;lastTime += que[minId].runTime;que[minId].finish = IsEnd;}//進程不能運行完 else{que[minId].order = ID++;que[minId].beginTime = lastTime;que[minId].endTime = lastTime + que[minId].slot;printf("%d/%d/%d/%d/%d\n", que[minId].order, que[minId].pid, que[minId].beginTime, que[minId].endTime, que[minId].priority + 3);lastTime += que[minId].slot;que[minId].runTime -= que[minId].slot;}//改變進程優(yōu)先級 for (int i = 0; i < tmp; i++){if (que[i].finish == NoEnd){if (i == minId)//運行優(yōu)先級減3 {que[i].priority += 3;}else//等待優(yōu)先級加1 {que[i].priority = max(que[i].priority - 1, 0);}}}} } bool cmp1(process a, process b) {if (a.comeTime != b.comeTime)return a.comeTime < b.comeTime;elsereturn a.pid < b.pid; } bool cmp2(process a, process b) {if (a.comeTime != b.comeTime)return a.comeTime < b.comeTime;else if (a.runTime != b.runTime)return a.runTime > b.runTime;elsereturn a.pid < b.pid; }測試結(jié)果
程序采用黑盒測試的方式，提交到樂學(xué)的 OJ 系統(tǒng)上進行在線評測
可以看到，OJ 的測試用例全部通過
心得體會
通過本次實驗，上機代碼模擬實現(xiàn)了五種進程調(diào)度算法，對操作系統(tǒng)內(nèi)部的進程調(diào)度方式有了更深刻的認(rèn)識和感受。對于非剝奪的短作業(yè)優(yōu)先算法而言，因為每次都要檢測當(dāng)前時刻的短作業(yè)，排序其實可有可無；對于其余四種算法而言，排序則顯得尤為重要。
《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的操作系统实验1—实现单处理机下的进程调度程序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 操作系统习题8—设备管理
- 下一篇： 操作系统实验2—实现动态分区分配模拟程序