一個小型的操作系統(tǒng)設計與實現

1、操作系統(tǒng)課程設計報告南通大學計算機科學與技術學院操作系統(tǒng)課程設計報告專業(yè)：計嵌151學生姓名：王志宏學號：1513052018時間：2017/6/28設計一個小型的操作系統(tǒng)設計要求將本學期三次的實驗集成實現：1. 中斷處理2. 作業(yè)調度3. PV原語4. 死鎖5. 頁面替換6. 磁盤調度(一)設計流程圖主流程圖開始的圖形界面 作業(yè)調度PV原語死鎖頁面替換磁盤調度中斷處理哲學家吃通心面先來先服務時鐘銀行家算法先進先出算法LRU算法先來先服務1. 中斷處理模擬時鐘中斷的產生及設計一個對時鐘中斷事件進行處理的模擬程序。計算機系統(tǒng)工作過程中，若出現中斷事件，硬件就把它記錄在中斷寄存器中。中斷寄存器的每

2、一位可與一個中斷事件對應，當出現某中斷事件后，對應的中斷寄存器的某一位就被置成1。處理器每執(zhí)行一條指令后，必須查中斷寄存器，當中斷寄存器內容不為0時，說明有中斷事件發(fā)生。硬件把中斷寄存器內容以及現行程序的斷點存在主存的固定單元，且讓操作系統(tǒng)的中斷處理程序占用處理器來處理出現的中斷事件。操作系統(tǒng)分析保存在主存固定單元中的中斷寄存器內容就可知道出現的中斷事件的性質，從而作出相應的處理。本實習中，用從鍵盤讀入信息來模擬中斷寄存器的作用，用計數器加 1 來模擬處理器執(zhí)行了一條指令。每模擬一條指令執(zhí)行后，從鍵盤讀入信息且分析，當讀入信息=0 時，表示無中斷事件發(fā)生，繼續(xù)執(zhí)行指令；當讀入信息=1 時，表示

3、發(fā)生了時鐘中斷事件，轉時鐘中斷處理程序2.作業(yè)調度 1)先來先服務FCFS開始初始化進程控制塊，讓進程控制塊按進程到達先后順序讓進程排隊調度數組中首個進程，并讓數組中的下一位移到首位計算并打印進程的完成時刻、周轉時間、帶權周轉時間其中：周轉時間 = 完成時間 - 到達時間帶權周轉時間=周轉時間/服務時間更改計時器的當前時間,即下一刻進程的開始時間當前時間=前一進程的完成時間+其服務時間數組為空NY結束 先來先服務算法流程3.PV原語 1）哲學家吃通心面問題哲學家吃通心面：在這道題目里，每把叉子必須互斥使用，當一位哲學家吃通心面之前必須執(zhí)行兩個P操作，獲得自己左右兩邊的叉子，在吃完通心面后必須執(zhí)

4、行兩個V操作，放下叉子。4. 死鎖1） 銀行家算法5.頁面替換 1)先進先出FIFO開始FIFO的缺頁中斷處理查主存分塊表有空閑塊可用？Y分配一塊NJ=pHEADJ的修改標志=1？NY輸出“將J頁復寫入交換區(qū)”輸出“裝入L頁”調整FIFO隊列，將L插入隊尾（HEAD=(HEAD+1)modM)修改主存分塊表和頁表終止FIFO淘汰算法流程 2）LRU開始LRU的缺頁中斷處理查主存分塊表有空閑塊可用？Y分配一塊N找到棧底元素：J=pM-1J的修改標志=1？NY輸出“將J頁送到入交換區(qū)”輸出“裝入L頁”調整堆棧，使HEAD所指元素及以下的元素下移PHEAD=L修改主存分塊表和頁表終止LRU淘汰算法流

5、程6. 磁盤調度1）先來先服務算法FCFS）（二）實現原理主界面設計一個框架分別去鏈接處理機管理、存儲器管理和缺頁調度相關的程序。1. 中斷2.作業(yè)調度 1)先來先服務FCFS（1） 任務先來先服務的調度算法實現處理機調度。（2） 要求1. 實現對FCFS算法的模擬實現2. 計算出該算法的平均作業(yè)周轉時間、平均帶權作業(yè)周轉時間。（3） 原理按作業(yè)到達CPU時間先后順序進行非剝奪式調度，先到達CPU的作業(yè)先被執(zhí)行。（4） 數據結構 struct task_struct char name; /*進程名稱*/ int number; /*進程編號*/ float come_time; /*到達時間

6、*/ float run_begin_time; /*開始運行時間*/ float run_time; /*運行時間*/ float run_end_time; /*運行結束時間*/ int priority; /*優(yōu)先級*/ int order; /*運行次序*/ int run_flag; /*調度標志*/ tasksMAX;int fcfs()/*先來先服務算法*/進程名鏈接指針到達時間估計運行時間進程狀態(tài)進程控制塊結構（5） 實現方法建立一個鏈表按照到達CPU的時間從小到大排列，只需從第一個作業(yè)（頭結點）依次調度到最后一個作業(yè)（尾結點）。（6） 運行界面測試數據：作業(yè)名到達時間運行時間

7、A028B09C03執(zhí)行FCFS算法如下：3. 死鎖假定本系統(tǒng)中的各個所需資源均是獨占型資源，在進程運行的過程中不再釋放，故只需要遍歷鏈表將各個進程中所需的資源統(tǒng)計出來，只要不大于系統(tǒng)中預設的即可，一旦進程所需的資源大于系統(tǒng)中的最大量，給予用戶選擇kill一進程，已達到釋放資源的目的。死鎖檢測函數：void sisuo() 死鎖解除函數：void safe()4.缺頁調度 1)先進先出FIFO（1） 任務采用先進先出FIFO算法實現分頁管理的缺頁調度，并輸出每次調入調出的頁號和運行結果。（2） 要求1.實現對FIFO算法的模擬實現2.輸出每次執(zhí)行的結果。（3） 原理基于程序總是按線性順序來訪問

8、物理空間這一假設，總是淘汰最先調入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認為駐留時間最長的頁不再使用的可能性較大。（4） 數據結構void FIFO()int length;int fifo100=0;int pageLength;int fifoPage100=0;int i,j;cout<<" *先進先出算法*"<<endl;pageLength=3;length=9; for(i=1;i<=length;i+)int flag=0;for(j=1;j<=pageLength;j+)if(fifoi=fifoPagej)fla

9、g=1;j=pageLength+1;else if(fifoPagej=0)fifoPagej=fifoi;j=pageLength+1;flag=1; if(flag=1)elsecout<<" 淘汰"<<fifoPage1<<endl;for(j=1;j<=pageLength;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=fifoi;（5） 實現方法當采用先進先出算法時，用一個數組構成先進先出隊列，數組中各個元素為進程已在主存的頁號，其隊列頭指針初始化為0.假設分配給每個進程的內存塊

10、數固定。當隊列滿需淘汰時，淘汰最先進入主存的一頁。若該頁修改過，還有存入磁盤。然后要把當前訪問的頁裝入該塊，并修改頁表和存儲分塊表的對應標志。（6） 運行界面測試數據：頁表長度：9；頁框長度：3；頁面請求數列：4,4,3,5,1,1,2,3,2執(zhí)行先進先出FIFO算法結果如下：2）LRU（1） 任務采用先進先出LRU算法實現分頁管理的缺頁調度，并輸出每次調入調出的頁號和運行結果。（2） 要求1.實現對LRU算法的模擬實現2.輸出每次執(zhí)行的結果。（3） 原理最近最少使用頁面替換算法淘汰的頁面是在最近一段時間內最久未被訪問的那一頁，它是基于程序局部性原理來考慮的，認為那些剛被使用過的頁面可能還有立

11、即被使用，而那些在較長時間內未被使用的頁面可能不會立即使用。在分頁虛擬存儲系統(tǒng)中，當硬件發(fā)出缺頁中斷后轉操作系統(tǒng)處理缺頁中斷。如果主存中已無空閑塊，可采用LRU算法進行缺頁處理。（4） 數據結構void LRU()int length;int lru100=0;int pageLength;int lruPage100=0; int i,j;cout<<" *最近最少使用LRU算法*"<<endl;pageLength=3;length=9; for(i=1;i<=length;i+)int flag=0;for(j=1;j<=pageL

12、ength;j+)if(lrui=lruPagej)for(int cc=j;cc>0;cc-)lruPagecc=lruPagecc-1;lruPage1=lrui;flag=1;j=pageLength+1;else if(lruPagej=0)for(int vv=j;vv>0;vv-)lruPagevv=lruPagevv-1;lruPage1=lrui;j=pageLength+1;flag=1; if(flag=1)elsecout<<" 淘汰"<<lruPagepageLength<<endl;for(j=pag

13、eLength;j>0;j-)lruPagej=lruPagej-1;lruPage1=lrui;（5） 實現方法當采用LRU算法時，用一個數組構成堆棧，堆棧中各個元素為進程已在主存的頁號，為了進行頁面置換，可設置一個棧指針，初始化為0.假定分配給每個進程的內存塊數固定不變。當隊列滿需淘汰時，操作系統(tǒng)選擇棧底元素淘汰，其他元素向下移一個位置，將新調入頁放棧指針指示的棧頂。當訪問的頁在棧中時，還應調整頁從當前位置到棧頂。（6） 運行界面測試數據：頁表長度：9；頁框長度：3；頁面請求數列：2,3,5,1,5,5,4,4,3執(zhí)行最近最少使用LRU算法結果如下：5. 磁盤調度1）先來先服務算法F

14、CFS）這是一種比較簡單的磁盤調度算法。它根據進程請求訪問磁盤的先后次序進行調度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優(yōu)化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。（三）總結與體會通過本次課程設計讓我對于圖形界面設計有了一定的思路和看法，同時我對先來先服務、時間片輪轉、首次適應算法、最佳適應算法、先進先出和最近最少使用算法有了更詳盡的認識。在編程的過程中發(fā)現會用到大量的指針，用指針來操作大量的數據比較方便，但最后應

15、該記得釋放資源。從這次實驗中我發(fā)現我對于c+掌握也有所不足，程序經過了多次修改才得以完善，在以后應該注重編程方面的訓練。此外我還更深入的理解了各個進程調度算法，及實現過程。在編寫程序時查詢了很多資料，間接提高了我的搜索能力。在此次課程設計過程中，對進程的相關知識有了一定的加深。特別是對進程的進程控制塊的存在和價值有了更進一步的認識。在編寫程序的過程之中，對進程自身信息的設計和管理以及調度的算法都有助于對書本知識的理解和掌握。特別是設計先來先服務調度算法和時間片輪轉調度算法的時候，對進程的調度算法有了更好的深入理解。對進程管理中的等待隊列，就緒隊列，時間片等概念有了更深刻的印象。在設計此模擬操作

16、系統(tǒng)的課設中，也加深了對c+知識的把握。解決了一些以往在編程中遇到了困難。通過此次的課程設計，不僅提高了對操作系統(tǒng)的認知，也在同時提高了編程的能力，加強了實踐。另外，我覺得此次課程設計雖然主要問題是在編程上，但是經過不斷的去調試，還是成功的調試了出來。但是這幾個程序用了多天的時間進行分析和修改，雖然出現了不少問題，但收獲頗多！源代碼：#include<iostream>#include<cstring>#include <cstddef>#include <windows.h> #include <time.h> #include &

17、lt;string> #include <assert.h> #include<stdio.h>#include<stdlib.h>using namespace std;int fcfsoutput(); /*調度結果輸出*/int fcfsinput(); /進程參數的初始化void kaishi();#define MAX 10#define maxsize 1000struct node /建立鏈表來存放進程數據 char name5; /進程名稱 int need_time; /所需要的時間 int allocation; /占用cpu的情況

18、 char state; /目前的狀態(tài) R為運行，E為運行完畢 node *next; /鏈表的尾結點 ;struct task_structchar name; /*進程名稱*/int number; /*進程編號*/float come_time; /*到達時間*/float run_begin_time; /*開始運行時間*/float run_time; /*運行時間*/float run_end_time; /*運行結束時間*/int priority; /*優(yōu)先級*/int order; /*運行次序*/int run_flag; /*調度標志*/tasksMAX;int coun

19、ter; /*實際進程個數*/int fcfs()/*先來先服務算法*/fcfsinput();float time_temp = 0;int i;int number_schedul;time_temp = e_time;for (i = 0; i<counter; i+)tasksi.run_begin_time = time_temp;tasksi.run_end_time = tasksi.run_begin_time + tasksi.run_time;tasksi.run_flag = 1;time_temp = tasksi.run_end_time;n

20、umber_schedul = i;tasksnumber_schedul.order = i + 1;fcfsoutput();return 0;int fcfsinput()task_struct tt;int i, j;/初始化進程數counter = 3;/初始化每個到達系統(tǒng)的時間為5、7、8e_time = rand() % 9;e_time = rand() % 9;e_time = rand() % 9;for (i = 1; i<3; i+)for (j = 0; j<3 - i; j+)if (tasks

21、e_time>tasksj + 1.come_time)tt = tasksj;tasksj = tasksj + 1;tasksj + 1 = tt;/初始化每個進程估計運行的時間tasks0.run_time = 28;tasks1.run_time = 9;tasks2.run_time = 3;/初始化每個進程的名字 = 'A' = 'B' = 'C'cout << "*先來先服務算法*" << endl <

22、< endl;for (i = 0; i<counter; i+)tasksi.run_begin_time = 0;tasksi.run_end_time = 0;tasksi.order = 0;tasksi.run_flag = 0;return 0;int fcfsoutput() /*調度結果輸出*/int i;float turn_round_time = 0, f1, w = 0;cout << " *先來先服務*" << endl;cout << "作業(yè)名 到達時間 運行時間 開始時間 停止時間 運行

23、次序 周轉時間" << endl;for (i = 0; i<counter; i+)f1 = tasksi.run_end_time - e_time;turn_round_time += f1;w += (f1 / tasksi.run_time);cout << " " << << 't' << " " << e_time << 't' <<

24、" "<< tasksi.run_time << 't' << " " << tasksi.run_begin_time << 't' << " "<< tasksi.run_end_time << 't' << tasksi.order << 't' << f1 << 't' << endl;cout

25、 << "平均周轉時間：" << turn_round_time / counter << endl;cout << "平均帶權周轉時間：" << w / counter << endl;cout << " "return 0;void zuoyediaodu()/作業(yè)調度int n;cout << "t1.先來先服務算法t 2.返回開始菜單" << endl;cin >> n;switch (n

26、)case 1: fcfs(); kaishi(); break;case 2: kaishi(); kaishi(); break;/*-*/void FIFO()int length;int fifo100 = 0 ;int pageLength;int fifoPage100 = 0 ;int i, j;cout << " *先進先出算法*" << endl;pageLength = 3;length = 9;cout << "時刻t" << 't'for (i = 0; i<l

27、ength; i+)cout << i << 't'cout << endl << "引用串" << 't'for (i = 1; i <= length; i+)fifoi = rand() % 5 + 1;cout << fifoi << 't'for (i = 1; i <= length; i+)int flag = 0;for (j = 1; j <= pageLength; j+)if (fifoi = fifoP

28、agej)flag = 1;j = pageLength + 1;else if (fifoPagej = 0)fifoPagej = fifoi;j = pageLength + 1;flag = 1;if (flag = 1)elsecout << " 淘汰" << fifoPage1 << endl;for (j = 1; j <= pageLength; j+)fifoPagej = fifoPagej + 1;fifoPagepageLength = fifoi;cout << endl << &q

29、uot;t=" << i - 1 << "時" << 't'for (int jk = 1; jk <= pageLength; jk+)cout << "P" << jk << 't'cout << endl << 't'for (int s = 1; s <= pageLength; s+)cout << fifoPages << 't'cout

30、<< endl;void LRU()int length;int lru100 = 0 ;int pageLength;int lruPage100 = 0 ;int i, j;cout << " *最近最少使用LRU算法*" << endl;pageLength = 3;length = 9;cout << "時刻t" << 't'for (i = 0; i<length; i+)cout << i << 't'cout <&

31、lt; endl << "引用串" << 't'for (i = 1; i <= length; i+)lrui = rand() % 5 + 1;cout << lrui << 't'for (i = 1; i <= length; i+)int flag = 0;for (j = 1; j <= pageLength; j+)if (lrui = lruPagej)for (int cc = j; cc>0; cc-)lruPagecc = lruPagecc - 1

32、;lruPage1 = lrui;flag = 1;j = pageLength + 1;else if (lruPagej = 0)for (int vv = j; vv>0; vv-)lruPagevv = lruPagevv - 1;lruPage1 = lrui;j = pageLength + 1;flag = 1;if (flag = 1)elsecout << " 淘汰" << lruPagepageLength << endl;for (j = pageLength; j>0; j-)lruPagej = lr

33、uPagej - 1;lruPage1 = lrui;cout << endl << "t=" << i - 1 << "時" << 't'for (int jk = 1; jk <= pageLength; jk+)cout << "P" << jk << 't'cout << endl << 't'for (int s = 1; s <= pageLen

34、gth; s+)cout << lruPages << 't'cout << endl;void queye()/頁面替換int n;cout << endl;cout << "t1.先進先出算法t2.LRU算法t3.返回開始菜單" << endl;cin >> n;switch (n)case 1: FIFO(); kaishi(); break;case 2: LRU(); kaishi(); break;case 3: kaishi(); kaishi(); break

35、;/*-*/*判斷輸入數據是否有效*/int decide(char str) /判斷輸入數據是否有效int i = 0;while (stri != '0')if (stri<'0' | stri>'9')return 0;break;i+;return i;/*將字符串轉換成數字*/int trans(char str, int a) /將字符串轉換成數字int i;int sum = 0;for (i = 0; i<a; i+)sum = sum + (int)(stri - '0')*pow(10, a

36、- i - 1);return sum;/*先來先服務調度算法*/void FCFS(int cidao, int m) /磁道號數組，個數為mint now;/當前磁道號int sum = 0; /總尋道長度int j, i;int a;char str100;float ave; /平均尋道長度cout << " *先來先服務*" << endl;cout << "磁盤請求序列為："for (i = 0; i<m; i+) /按先來先服務的策略輸出磁盤請求序列cout << cidaoi <

37、< " "cout << endl;cout << "請輸入當前的磁道號："B: cin >> str; /對輸入數據進行有效性判斷a = decide(str);if (a = 0)cout << "輸入數據的類型錯誤,請重新輸入！" << endl;goto B;elsenow = trans(str, a); /輸入當前磁道號sum += abs(cidao0 - now);cout << "磁盤掃描序列為："for (i = 0;

38、 i<m; i+) /輸出磁盤掃描序列cout << cidaoi << " "for (i = 0, j = 1; j<m; i+, j+) /求平均尋道長度sum += abs(cidaoj - cidaoi);ave = (float)(sum) / (float)(m);cout << endl;cout << "平均尋道長度：" << ave << endl;void cipandiaodu() /磁盤調度int a;int c; /菜單項int cidaoma

39、xsize;int i = 0, count;char str100;cout << endl;cout << "t1.先來先服務t2.返回開始菜單" << endl;F:cin >> str; /對輸入數據進行有效性判斷a = decide(str);if (a = 0)cout << "輸入數據的類型錯誤,請重新輸入！" << endl;goto F;/輸入錯誤，跳轉到F，重新輸入elsec = trans(str, a);cout << "請輸入磁道序列（

40、0結束）：" << endl;A:cin >> str; /對輸入數據進行有效性判斷a = decide(str);if (a = 0)cout << "輸入數據的類型錯誤,請重新輸入！" << endl;goto A;/輸入錯誤，跳轉到A，重新輸入elsecidaoi = trans(str, a);i+;while (cidaoi - 1 != 0)cin >> str; /對輸入數據進行有效性判斷a = decide(str);if (a = 0)cout << "輸入數據的類

41、型錯誤,請重新輸入！" << endl;elsecidaoi = trans(str, a);i+;count = i - 1; /要訪問的磁道數cout << "你輸入的磁道序列為："for (i = 0; i<count; i+)cout << cidaoi << " " /輸出磁道序列cout << endl;switch (c)case 1: /使用FCFS算法FCFS(cidao, count); kaishi(); break;case 2: kaishi(); ka

42、ishi(); break;/*-*/bool tools5; /全局變量，用餐工具CRITICAL_SECTION cs; /信號量, 在線程中使用，臨界區(qū)class Philosopherprivate:int number;int status; /標記當前哲學家的狀態(tài),0表示正在等待/ (即處于饑餓狀態(tài)),1表示得到兩支筷子正在吃飯,2表示正在思考public:Philosopher(int num = 0) : status(2), number(num) const int find()return number;const int getinfo()return status;v

43、oid Change(); /狀態(tài)改變函數void dead_lock();void Philosopher:dead_lock()EnterCriticalSection(&cs); /進入臨界區(qū)string s;if (status = 1)toolsnumber % 5 = true;/ tools(number-1)%5=true;status = 2;else if (status = 2)status = 0;/tools(number-1)%5=false;/tools(number-1)%5=true;else if (status = 0)toolsnumber %

44、5 = false;tools(number - 1) % 5 = false;status = 1;LeaveCriticalSection(&cs);/ cout<<"*"void Philosopher:Change()EnterCriticalSection(&cs); /進入臨界區(qū)if (status = 1) /正在進餐toolsnumber % 5 = true; /放下左手工具tools(number - 1) % 5 = true; /放下右手工具status = 2; /改變狀態(tài)為思考else if (status = 2)

45、/思考中status = 0; /改變狀態(tài)為等待else if (status = 0) /等待中if (toolsnumber % 5 && tools(number - 1) % 5) /左右手兩邊工具均為空閑狀態(tài)toolsnumber % 5 = false; /拿起左手工具tools(number - 1) % 5 = false; /拿起右手工具status = 1;LeaveCriticalSection(&cs);string print(Philosopher *pA)/pA->Change(); int i = pA->getinfo();

46、string str;if (i = 0)str = "等待"else if (i = 1)str = "就餐"else str = "思考"return str;string toolstatus(bool a)string state;if (a = true)state = "閑"if (a = false)state = "用"return state;void dead_lock()char con = 'y' /判斷是否繼續(xù)/ con = 'n'for

47、 (int i = 0; i<5; i+)toolsi = true; /筷子都未使用，初始化Philosopher P1(1), P2(2), P3(3), P4(4), P5(5);InitializeCriticalSection(&cs); /初始化初始化臨界區(qū)cout << " *PV原語*" << endl;cout << "-狀態(tài)說明示意圖：-" << endl;cout << " " << "哲學家1號的狀態(tài)" &

48、lt;< " " << endl;cout << " 筷子0的狀態(tài)" << " " << "筷子1的狀態(tài)" << endl;cout << "哲學家5號的狀態(tài)" << " " << "哲學家2號的狀態(tài)" << endl;cout << " 筷子4的狀態(tài)" << " " <&l

49、t; "筷子2的狀態(tài)" << endl;cout << " 哲學家4號的狀態(tài)" << " " << "哲學家3號的狀態(tài)" << endl;cout << " " << "筷子3的狀態(tài)" << endl;/cout<<" "<<"哲學家3號的狀態(tài)"<<" "<<endl; co

50、ut << "筷子的狀態(tài)，用表示使用中，閑表示空閑中。" << endl;cout << "-" << endl;/cout<<"哲學家們開始生活："<<endl; /cout<<"當前狀態(tài)：" cout << endl;/cin>>con;while (con = 'y')P1.Change(); P2.Change(); P3.Change(); P4.Change(); P5.Chang

51、e();cout << "當前狀態(tài)為：" << endl;cout << " " << P1.find() << print(&P1) << " " << endl;cout << " " << toolstatus(tools0) << " " << toolstatus(tools1) << endl;cout << "

52、 " << P5.find() << print(&P5) << " " << P2.find() << print(&P2) << endl;cout << " " << toolstatus(tools4) << " " << toolstatus(tools2) << endl;cout << " " << P4.find() &

53、lt;< print(&P4) << " " << P3.find() << print(&P3) << endl;cout << " " << toolstatus(tools3) << endl;cout << "-" << endl;cout << "若要繼續(xù)下一狀態(tài)，輸入y；輸入n進入死鎖；輸入其他，結束程序："cin >> con;Sleep(20);while (con = 'n')P1.dead_lock();P2.dead_lock(); P3.dead_lock(); P4.dead_lock(); P5