第一篇：操作系統課程設計

操作系統課程設計

注意事項：

0.請每位同學必須按時提交課程設計報告（包括電子版和紙質版），算入期末成績

1.在三個題目中選擇一個

2.如果選擇題目

（一）進程調度算法，要求實現其中2個以上（包括2個）進程調度算法 3.如果選擇題目

（二）銀行家算法，要求能夠判斷系統的安全狀態

4.如果選擇題目

（三）頁面調度算法，要求實現其中2個以上（包含2個）進程調度算法 5.報告應包含算法分析、實驗截圖、核心算法源代碼，請各位同學認真對待，獨立完成 6.提交要求：電子版（包括實驗程序）請發至ropeal@163.com，紙質版請班長收齊，由班長統一在課堂上提交（并提交未交人員名單），截止時間第16周周三(2014.1.31)7.格式要求：

7.1 A4紙10頁左右

7.2 封面請注明班級、姓名、學號、所選題目

7.3 電子版發送時，請打包成一個文件，將文件名設置為：學號+姓名+題目名稱（如20130000張三進程調度算法課程設計），郵件主題同文件名

一、進程調度算法

1.1 實驗目的： a、設計進程控制塊PCB表結構，模擬實現進程調度算法：FIFO，靜態優先級調度，時間片輪轉調度，多級反饋隊列調度。（實現其中之二）。* b、建立進程就緒隊列。對不同算法編制入鏈子程序。c、編寫一進程調度程序模擬程序。模擬程序只對PCB進行相應的調度模擬操作，不需要實際程序。* 由用戶輸入進程名和進程長度，然后按照短進程優先的進程處理順序給出進程的排序。

1.2 實驗原理 調度算法是指：根據系統的資源分配策略所規定的資源分配算法。1.2.1 先來先服務和短作業（進程）優先調度算法

1.先來先服務調度算法。先來先服務（FCFS）調度算法是一種最簡單的調度算法，該算法既可用于作業調度，也可用于進程調度。FCFS算法比較有利于長作業（進程），而不利于短作業（進程）。由此可知，本算法適合于CPU繁忙型作業，而不利于I/O繁忙型的作業（進程）。

2.短作業（進程）優先調度算法。短作業（進程）優先調度算法（SJ/PF）是指對短作業或短進程優先調度的算法，該算法既可用于作業調度，也可用于進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。1.2.2 高優先權優先調度算法

1.優先權調度算法的類型。為了照顧緊迫性作業，使之進入系統后便獲得優先處理，引入了最高優先權優先（FPF）調度算法。此算法常被用在批處理系統中，作為作業調度算法，也作為多種操作系統中的進程調度，還可以用于實時系統中。當其用于作業調度，將后備隊列中若干個優先權最高的作業裝入內存。當其用于進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時，又可以進一步把該算法分成以下兩種： 1)非搶占式優先權算法

2)搶占式優先權調度算法（高性能計算機操作系統）

2.優先權類型。對于最高優先權優先調度算法，其核心在于：它是使用靜態優先權還是動態優先權，以及如何確定進程的優先權。3．高響應比優先調度算法

為了彌補短作業優先算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間 1.2.3 基于時間片的輪轉調度算法

1.時間片輪轉法。時間片輪轉法一般用于進程調度，每次調度，把CPU分配隊首進程，并令其執行一個時間片。當執行的時間片用完時，由一個記時器發出一個時鐘中斷請求，該進程被停止，并被送往就緒隊列末尾；依次循環。2.多級反饋隊列調度算法 多級反饋隊列調度算法多級反饋隊列調度算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度算法。其實施過程如下：

1)設置多個就緒隊列，并為各個隊列賦予不同的優先級。在優先權越高的隊列中，為每個進程所規定的執行時間片就越小。

2)當一個新進程進入內存后，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度?? 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最后隊列）后，便按第n隊列時間片輪轉運行。3)僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1到第（i-1）隊列空時，才會調度第i隊列中的進程運行，并執行相應的時間片輪轉。4)如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列，則此新隊列搶占正在運行的處理機，并把正在運行的進程放在第i隊列的隊尾。

1．3 實驗要求

a、使用模塊化設計思想來設計； b、給出算法的流程圖或偽碼說明。c、學生可按照自身條件，隨意選擇采用的算法，（例如：采用冒泡法編寫程序，實現短進程優先調度的算法）

d、進程調度程序模擬程序只對PCB進行相應的調度模擬操作，不需要實際程序。

1.4 算法簡析 a、每個進程可有三個狀態，并假設初始狀態為就緒狀態。b、為了便于處理，程序中的某進程運行時間以時間片為單位計算。各進程的優先數或輪轉時間數以及進程需運行的時間片數的初始值均由用戶給定。c、在優先數算法中，優先數可以先取值為（50-該進程所需時間），進程每執行一次，優先數減3，CPU時間片數（CPUtime）加1，* 進程還需要的時間片數（needtime）減1。在時間片輪轉算法中，采用固定時間片

（即：每執行一次進程，該進程的執行時間片數為已執行了2個單位），這時，CPU時間片（CPUtime）數加2，* 進程還需要的時間片數（needtime）減2，并排列到就緒隊列的尾上。

d、對于遇到優先數一致的情況，采用FIFO策略解決。

二、銀行家算法

2.1 概述

2.1.1 設計目的1、了解多道程序系統中，多個進程并發執行的資源分配。

2、掌握死鎖的產生的原因、產生死鎖的必要條件和處理死鎖的基本方法。

3、掌握預防死鎖的方法，系統安全狀態的基本概念。

4、掌握銀行家算法，了解資源在進程并發執行中的資源分配策略。

5、理解死鎖避免在當前計算機系統不常使用的原因

2.2 關于死鎖

2.2.1 死鎖概念：

在多道程序系統中，雖可借助于多個進程的并發執行，來改善系統的資源利用率，提高系統的吞吐量，但可能發生一種危險━━死鎖。所謂死鎖(Deadlock),是指多個進程在運行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當進程處于這種僵持狀態時，若無外力作用，它們都將無法再向前推進。一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種現象稱為進程死鎖，這一組進程就稱為死鎖進程。

2.2.2 關于死鎖的一些結論：

參與死鎖的進程最少是兩個（兩個以上進程才會出現死鎖）

參與死鎖的進程至少有兩個已經占有資源

參與死鎖的所有進程都在等待資源

參與死鎖的進程是當前系統中所有進程的子集

注：如果死鎖發生，會浪費大量系統資源，甚至導致系統崩潰。

2.2.3 資源分類：

永久性資源： 可以被多個進程多次使用（可再用資源），分為：可搶占資源與不可搶占資源

臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源）

“申請--分配--使用--釋放”模式

2.2.4 產生死鎖的四個必要條件：

1、互斥使用（資源獨占）

一個資源每次只能給一個進程使用

2、不可強占（不可剝奪）

資源申請者不能強行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放

3、請求和保持（部分分配，占有申請）

一個進程在申請新的資源的同時保持對原有資源的占有（只有這樣才是動態申請，動態分配）

4、循環等待

存在一個進程等待隊列

{P1 , P2 , ? , Pn}，其中P1等待P2占有的資源，P2等待P3占有的資源，?，Pn等待P1占有的資源，形成一個進程等待環路

2.2.5 死鎖的解決方案 1 產生死鎖的例子

申請不同類型資源產生死鎖

P1： ?

申請打印機 申請掃描儀 使用

釋放打印機 釋放掃描儀 ? P2： ?

申請掃描儀 申請打印機 使用

釋放打印機 釋放掃描儀 ?

申請同類資源產生死鎖（如內存）

設有資源R，R有m個分配單位，由n個進程P1,P2,?,Pn（n > m）共享。假設每個進程對R的申請和釋放符合下列原則： * 一次只能申請一個單位 * 滿足總申請后才能使用 * 使用完后一次性釋放

m=2，n=3 資源分配不當導致死鎖產生

2死鎖預防: 定義:在系統設計時確定資源分配算法，保證不發生死鎖。具體的做法是破壞產生死鎖的四個必要條件之一

①破壞“不可剝奪”條件

在允許進程動態申請資源前提下規定，一個進程在申請新的資源不能立即得到滿足而變為等待狀態之前，必須釋放已占有的全部資源，若需要再重新申請 ②破壞“請求和保持”條件

要求每個進程在運行前必須一次性申請它所要求的所有資源，且僅當該進程所要資源均可滿足時才給予一次性分配 ③破壞“循環等待”條件 采用資源有序分配法：

把系統中所有資源編號，進程在申請資源時必須嚴格按資源編號的遞增次序進行，否則操作系統不予分配。

2.2.6 安全狀態與不安全狀態

安全狀態： 如果存在一個由系統中所有進程構成的安全序列P1，?Pn，則系統處于安全狀態。一個進程序列{P1，?，Pn}是安全的，如果對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統當前剩余資源量與所有進程Pj(j < i)當前占有資源量之和，系統處于安全狀態(安全狀態一定是沒有死鎖發生的)。

不安全狀態:不存在一個安全序列，不安全狀態一定導致死鎖。

2.3 數據結構設計

1.可利用資源向量矩陣AVAILABLE。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果AVAILABLE [j]= K，則表示系統中現有R類資源K個

2.最大需求矩陣MAX。這是一個n*m的矩陣，用以表示每一個進程對m類資源的最大需求。如果MAX [i,j]=K，則表示進程i需要R類資源的數目為K。

3.分配矩陣ALLOCATION。這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果ALLOCATION [i,j]=K，則表示進程i當前已分得R類資源的數目為K。

4.需求矩陣NEED。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果NEED [i,j]=K，則表示進程i還需要R類資源K個，才能完成其任務。上述矩陣存在下述關系：

NEED [i,j]= MAX[i,j]﹣ ALLOCATION[i,j]

2.4 算法的實現 2.4.1 初始化 由用戶輸入數據，分別對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。2.4.2 銀行家算法

在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處于安全狀態，便可以避免發生死鎖。

銀行家算法的基本思想是分配資源之前,判斷系統是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。

設進程cusneed提出請求REQUEST [i]，則銀行家算法按如下規則進行判斷。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(2)；否則，出錯。

(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(3)；否則，出錯。(3)系統試探分配資源，修改相關數據： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。

2.4.3 安全性檢查算法

(1)設置兩個工作向量Work=AVAILABLE;FINISH(2)從進程集合中找到一個滿足下述條件的進程，FINISH==false;NEED<=Work;如找到，執行(3)；否則，執行(4)(3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。

Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的進程Finish= true，則表示安全；否則系統不安全。

三、頁面調度算法 3.1 實驗名稱

頁式虛擬存儲管理：頁面調度算法 3.2 實驗目的

頁式虛擬存儲器實現的一個難點是設計頁面調度（置換）算法，即將新頁面調入內存時，如果內存中所有的物理頁都已經分配出去，就要按某種策略來廢棄某個頁面，將其所占據的物理頁釋放出來，供新頁面使用。本實驗的目的是通過編程實現幾種常見的頁面調度（置換）算法，加深讀者對頁面思想的理解。3.3 實驗原理

頁面調度算法

目前有許多頁面調度算法，本實驗主要涉及先進先出調度算法、最近最少調度算法、最近最不常用調度算法。本實驗使用頁面調度算法時作如下假設，進程在創建時由操作系統為之分配一個固定數目物理頁，執行過程中物理頁的數目和位置不會改變。也即進程進行頁面調度時只能在分到的幾個物理頁中進行。

下面對各調度算法的思想作一介紹。

<1> 先進先出調度算法

先進先出調度算法根據頁面進入內存的時間先后選擇淘汰頁面，先進入內存的頁面先淘汰，后進入內存的后淘汰。本算法實現時需要將頁面按進入內存的時間先后組成一個隊列，每次調度隊首頁面予以淘汰。

<2>最近最少調度算法

先進先出調度算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。

<3>最近最不常用調度算法

由于程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬件或操作系統自動定時清零。

缺頁調度次數和缺頁中斷率、缺頁置換率計算

缺頁中斷次數是缺頁時發出缺頁中斷的次數。

缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%

缺頁調度次數是調入新頁時需要進行頁面調度的次數

缺頁置換率=缺頁調度次數/總的頁面引用次數*100% 3.4 實驗內容

（1）設計程序實現以上三種頁面調度算法，要求：

①.可以選擇頁面調度算法類型；

②.可以為進程設置分到物理頁的數目，設置進程的頁面引用情況，可以從鍵盤輸入頁面序列，也可從文件中讀取；

③.隨時計算當前的頁面調度次數的缺頁中斷率；

④.使用敲鍵盤或響應WM-TIMER的形式模仿時間的流逝；

⑤.以直觀的的形式將程序的執行情況顯示在計算機屏幕上；

⑥.存盤及讀盤功能，可以隨時將數據存入磁盤文件，供以后重復實驗時使用。

（2）假定進程分配到3個物理塊，對于下面的頁面引用序列：（test.txt）

7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1

請分別用先進和先出調度算法，最近最少用調度算法，最近最不常用調度算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。

再假定進程分配到4、5個物理塊，重復本實驗。

（3）假定進程分配到3個物理塊，對于下面的頁面引用序列：（test2.txt）

4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9

請分別用先進先出調度算法、最近最少用調度算法，最近最不常用調度算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。

再假定進程分配到4、5個物理塊，重復本實驗。

（4）假定進程分配到3個物理塊，使用程序的動態頁面序列生成算法，生成一個頁面序列，將此序列存入磁盤文件。再從磁盤文件讀入該序列，用程序分別計算三種算法下的缺頁中斷次數、缺頁中斷率和缺頁調度次數、缺頁置換率。

第二篇：操作系統課程設計

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

（操作系統課程設計）

連續動態分區內存

管理模擬實現

學生姓名： 韓 慧 學生學號： 031140312 班 級： 031140--3 0311401、02、03、04班制

二〇一三年十二月 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

目錄

《操作系統》課程設計.......................................................1 引言......................................................................3 課程設計目的和內容......................................................3 需求分析.........................................................................3 概要設計...................................................................3 開發環境........................................................................4 系統分析設計.....................................................................4 有關了解內存管理的相關理論..................................................4 內存管理概念........................................................................4 內存管理的必要性..............................................................4 內存的物理組織.............................................................4 什么是虛擬內存.................................................................5 連續動態分區內存管理方式...................................................5 單一連續分配（單個分區)...................................................5

固定分區存儲管理...............................................................5 可變分區存儲管理（動態分區）..............................................5 可重定位分區存儲管理........................................................5 問題描述和分析....................................................................6 程序流程圖........................................................................6 數據結構體分析..................................................................8 主要程序代碼分析...............................................................9 分析并實現四種內存分配算法.................................................11 最先適應算.....................................................................11 下次適應分配算法..........................................................13 最優適應算法...............................................................16 最壞適應算法...............................................................18 回收內存算法................................................................20 調試與操作說明.................................................................22

初始界面.......................................................................22 模擬內存分配...............................................................23

已分配分區說明表面............................................................24 空閑區說明表界面.............................................................24 回收內存界面.....................................................................25 重新申請內存界面..........................................................26.總結與體會......................................................................28 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

參考文獻.........................................................................28

引言

操作系統是最重要的系統軟件，同時也是最活躍的學科之一。我們通過操作系統可以理解計算機系統的資源如何組織，操作系統如何有效地管理這些系統資源，用戶如何通過操作系統與計算機系統打交道。

存儲器是計算機系統的重要組成部分，近年來，存儲器容量雖然一直在不斷擴大，但仍不能滿足現代軟件發展的需要，因此，存儲器仍然是一種寶貴而又緊俏的資源。如何對它加以有效的管理，不僅直接影響到存儲器的利用率，而且還對系統性能有重大影響。而動態分區分配屬于連續分配的一種方式，它至今仍在內存分配方式中占有一席之地。

課程設計目的和內容：

理解內存管理的相關理論，掌握連續動態分區內存管理的理論；通過對實際問題的編程實現，獲得實際應用和編程能力。

編寫程序實現連續動態分區內存管理方式，該程序管理一塊虛擬內存，實現內存分配和回收功能。分析并實現四種內存分配算法，即最先適應算法，下次最先適應算法，最優適應算法，最壞適應算法。內存分配算法和回收算法的實現。

需求分析

動態分區分配是根據進程的實際需要，動態地為之分配內存空間。在實現動態分區分配時，將涉及到分區分配中所用的數據結構、分區分配算法和分區的分配和回收操作這樣三個問題。常用的數據結構有動態分區表和動態分區鏈。在對數據結構有一定掌握程度的情況下設計合理的數據結構來描述存儲空間，實現分區存儲管理的內存分配功能，應該選擇最合適的適應算法（首次適應算法，最佳適應算法，最后適應算法，最壞適應算法），在動態分區存儲管理方式中主要實現內存分配和內存回收算法，在這些存儲管理中間必然會有碎片的產生，當碎片產生時，進行碎片的拼接等相關的內容

概要設計

本程序采用機構化模塊化的設計方法，共分為四大模塊。⑴最先適應算法實現

從空閑分區表的第一個表目起查找該表，把最先能夠滿足要求的空閑區分配給作業，這種方法目的在于減少查找時間。為適應這種算法，空閑分區表（空閑區鏈）中的空閑分區要按地址由低到高進行排序。該算法優先使用低址部分空閑區，在低址空間造成許多小的空閑區，在高地址空間保留大的空閑區。⑵下次適應分配算法實現 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

該算法是最先適應算法的變種。在分配內存空間時，不再每次從表頭（鏈首）開始查找，而是從上次找到空閑區的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區為止，并從中劃出一塊與請求大小相等的內存空間分配給作業。該算法能使內存中的空閑區分布得較均勻。⑶最優適應算法實現

它從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此算法，空閑分區表（空閑區鏈）中的空閑分區要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。⑷最壞算法實現

最壞適應分配算法要掃描整個空閑分區或鏈表，總是挑選一個最大的空閑分區分割給作業使用。該算法要求將所有的空閑分區按其容量從大到小的順序形成一空閑分區鏈，查找時只要看第一個分區能否滿足作業要求。

開發環境：

win7 下 VC++6.0 系統分析設計：

相關算法原理，算法流程圖，涉及的數據結構內容都相應包含在各章節中

有關了解內存管理的相關理論

內存管理概念：

內存管理，是指軟件運行時對計算機內存資源的分配和使用的技術。其最主要的目的是如何高效，快速的分配，并且在適當的時候釋放和回收內存資源。內存不是預先劃分好的，而是在系統運行的過程中建立分區.當作業裝入主存時，根據作業所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區給該作業；否則令該作業等待.分區長度不固定分區個數不固定。這種存儲管理的方法克服了固定分區嚴重浪費主存的問題，提高了主存資源的利用率。

內存管理的必要性：

內存管理對于編寫出高效率的 Windows 程序是非常重要的，這是因為Windows 是多任務系統，它的內存管理和單任務的 DOS 相比有很大的差異。DOS是單任務操作系統，應用程序分配到內存后，如果它不主動釋放，系統是不會對它作任何改變的；但 Windows 卻不然，它在同一時刻可能有多個應用程序共享內存，有時為了使某個任務更好地執行，Windows 系統可能會對其它任務分配的內存進行移動，甚至刪除。因此，我們在 Windows 應用程序中使用內存時，要遵循Windows 內存管理的一些約定，以盡量提高 Windows 內存的利用率。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

1.3 內存的物理組織：

物理地址：

把內存分成若干個大小相等的存儲單元，每個存儲單元占 8 位，稱作字節（byte）。每個單元給一個編號，這個編號稱為物理地址（內存地址、絕對地址、實地址）。

二、物理地址空間： 物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維空間。

什么是虛擬內存：

虛擬內存是內存管理技術的一個極其實用的創新。它是一段程序（由操作系統調度），持續監控著所有物理內存中的代碼段、數據段，并保證他們在運行中的效率以及可靠性，對于每個用戶層（user-level）的進程分配一段虛擬內存空間。當進程建立時，不需要在物理內存件之間搬移數據，數據儲存于磁盤內的虛擬內存空間，也不需要為該進程去配置主內存空間，只有當該進程被被調用的時候才會被加載到主內存。

連續動態分區內存管理方式的實現

在早期的操作系統中，主存分配廣泛采用連續分配方式。連續分配方式，是指為一個用戶程序分配一個連續的內存空間，該連續內存空間指的的是物理內存。下面介紹連續分配的四種方式。

單一連續分配（單個分區）

最簡單的存儲管理方式，用于多道程序設計技術之前。內存分為系統區和用戶區，系統區由操作系統使用。用戶區作為一個連續的分區分配給一個作業。分區存儲管理是滿足多道程序設計的最簡單的一種存儲管理方法，它允許多 4個用戶程序同時存在系統內存中，即共享內存空間。按分區劃分方式可分為固定分區和可變分區。

固定分區存儲管理

把內存的用戶區預先劃分成多個分區，每個分區大小可以相同，也可以不同。（分區的劃分由計算機的操作員或者由操作系統給出，并給出主存分配表）分區個數固定，分區的大小固定。一個分區中可裝入一個作業，作業執行過程中不會改變存放區域。早期的 IBM 的 OS/MFT（具有固定任務數的多道程序系統）采用了這種固定分區的方法。

可變分區存儲管理（動態分區）

內存不是預先劃分好的，而是在系統運行的過程中建立分區.當作業裝入主存時，根據作業所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區給該作業；否則令該作業等待。分區長度不固定分區個數不固定。這種存儲管理的方法克服了固定分區嚴重浪費主存的問題，提高了主存資源的利用率。ＩＢＭ操作系統ＯＳ／ＭＶＴ采用可變分區存儲管理。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

可重定位分區存儲管理

解決碎片問題的一種簡單方法是采用可重定位分區分配.。其中心思想是，把不同程序，且在內存中地址不連續的想法讓他們連續。

例：內存中現有 3 個空閑區，現有一作業到達，要求獲得 30k 內存空間，沒有分區滿足容量要求，若想把作業裝入，可將內存中所有作業進行移動，這樣把原來分散的空閑區匯集成一個大的空閑區。將內存中的作業進行移動使它們連接在一起把原來分散的多個小分區拼接成一個大的空閑區.這個過程稱為”緊湊”或”移動”。需解決的問題:每次”緊湊”后程序或數據裝入的物理地址變化采用動態重定位。

問題描述和分析

系統應利用某種分配算法，從空閑分區鏈表中找到所需大小的分區，如果空閑分區大小大于請求分區大小，則從該分區中按改請求的大小劃分出一塊內存空間大小劃分出一塊內存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區的首址返回給調用者。

當進程運行完畢師范內存時，系統根據回收區的首址，從空閑區中找到相應的插入點，此時可能出現以下四種情況之一：

⑴該空閑區的上下兩相鄰分區都是空閑區：將三個空閑區合并為一個空閑區。新空閑區的起始地址為上空閑區的起始地址，大小為三個空閑區之和。空閑區合并后，取消可用表或自由鏈中下空閑區的表目項或鏈指針，修改上空閑區的對應項。

⑵該空閑區的上相鄰區是空閑區：將釋放區與上空閑區合并為一個空閑區，其起始地址為上空閑區的起始地址，大小為上空閑區與釋放區之和。合并后，修改上空閑區對應的可用表的表目項或自由鏈指針。

⑶該空閑區的下相鄰區是空閑區：將釋放區與下空閑區合并，并將釋放區的起始地址作為合并區的起始地址。合并區的長度為釋放區與下空閑區之和。同理，合并后修改可用表或自由鏈中相應的表目項或鏈指針。

⑷兩相鄰區都不是空閑區：釋放區作為一個新空閑可用區插入可用表或自由鏈。

程序流程圖

內存分配流程圖，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

從頭開始查表檢索完否？NY返回分區大小>所需大小N繼續檢索下一個表項Y分區大小-所需大小<=不可再分割大小N從該分區中劃出所需大小的新分區Y將該分區從鏈中移出將該分區分配給請求者修改有關數據結構返回

內存回收流程圖，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

開始判斷空閑區上下內存情況上為空下為空上下都為空上下都不為空將上面的空閑區合并，并回收將下面的空閑區合并，并回收將上下的空閑區合并，并回收直接將其回收結束 數據結構體分析

⑴進程屬性結構體 typedef struct readyque { char name[10];int size;}readyque,*readyqueue;⑵空閑鏈表結構體 typedef struct idlyspace { int from;int size;idlyspace * next;}idlyspace,*idly;⑶已分配鏈表結構體 typedef struct busyspace { int from;readyque r;湖北民族學院信息工程學院11級計算機專業操作系統課程設計

busyspace * next;}busyspace,*busy

主要程序代碼分析

⑴主函數//代碼請添加適當的注釋。int main(){ Is=(idly)malloc(sizeof(idlyspace));Is->from=0;Is->size=256;Is->next=NULL;Is2=Is;Bs=(busy)malloc(sizeof(busyspace));Bs->next=NULL;int t,t1;printf(“n.......................歡迎來到動態分區存儲管理系統..................nn”);printf(“...........................請選擇要執行的算法:...........................n”);printf(“.........................1.最先適應算法

...............................n”);printf(“.........................2.下次適應算法............................n”);printf(“..........................3.最優適應算法

...............................n”);printf(“.........................4.最壞適應算法................................n”);printf(“........................................................................n”);printf(“請輸入您的選擇:”);scanf(“%d”,&t);int i;while(i!=5){

printf(“........................................................................n”);

printf(“.........................操作菜單如下：（請選擇）.......................n”);

printf(“..........................1.輸入進程分配空間...........................n”);

printf(“.........................2.進程撤銷回收空間...........................n”);

printf(“.........................3.輸出所有空閑分區

..........................n”);

printf(“..........................4.輸出所有已分配分區..........................n”);

printf(“..........................5.退

出..........................n”);

printf(“........................................................................n”);

scanf(“%d”,&i);

switch(i)

{

case 1:

switch(t)

{

case 1:

t1=FF();湖北民族學院信息工程學院11級計算機專業操作系統課程設計

break;

case 2:

t1=NF();

break;

case 3:

t1=BF();

break;

case 4:

t1=WF();

break;

default:

printf(“選擇算法錯誤n”);

return 1;

}

if(t1)

printf(“分配空間成功n”);

else

printf(“分配空間失敗n”);

break;

case 2:

t1=recover();

if(t1)

printf(“回收成功n”);

else

printf(“回收失敗n”);

break;

case 3:

Isprint();

break;

case 4:

Bsprint();

break;

} } return 0;}

第三章 ：分析并實現四種內存分配算法

最先適應算法

空閑區按地址從小到大的次序排列。

分配：當進程申請大小為 SIZE 的內存時，系統順序查找空閑區表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區為止。從該空閑區中劃出大小為 SIZE的分區分配給進程，余下的部分仍作為一個空閑區，但要修改其首址和大小。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

優點：這種算法是盡可能地利用低地址部分的空閑區，而盡量地保證高地址 6部分的大空閑區，有利于大作業的裝入。

缺點:主存低地址和高地址分區利用不均衡。在低地址部分集中了許多非常小的空閑區碎片降低了主存的利用率。最先適應算法 int FF(){ int t=0;readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

printf““輸入進程申請空間大小:””);scanf““%””,&D.size);

idly l=Is;int mt=256;busy b=Bs;idly min=NULL;while(l)

//尋找空閑表中大小滿足申請進程所需大小并且起址最小的空閑結點

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));

//如果找到則為進程分配空間

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;} return t;}

下次適應分配算法

最先適應算法的變種。

總是從空閑區上次掃描結束處順序查找空閑區表（鏈），直到找到第一個滿足容量要求的空閑區為止，分割一部分給作業，剩余部分仍作為空閑區。下次適應分配算法 int NF(){ int t=0;readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

printf““輸入進程申請空間大小:””);scanf““%””,&D.size);

int mt=256;idly l=Is2;idly min=NULL;busy b=Bs;while(l)//尋找空閑表中大小滿足申請進程所需大小并且起址最小的空閑結點

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

//如果找到則為進程分配空間

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

}

//將申請空間進程插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改相應空閑節點的起址和大小

min->from=min->from+D.size;

min->size=min->size-D.size;

Is2=min->next;

結點

t=1;

return t;}

l=Is;//l指向空閑表的頭

while(l!=Is2)

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256){

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

//ls2指向修改結點的下一個

//循環查找 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;

Is2=min->next;

t=1;

return t;} return t;}

最優適應算法

空閑區按容量遞增的次序排列。

分配：當進程申請存儲空間，系統順序查找空閑區表（鏈），直到找到第一個滿足容量要求的空閑區為止。采用最優適應算法選中的空閑區是滿足容量要求的最小空閑區。優點：選中的空閑區是滿足容量要求的最小空閑區，而不致于毀掉較大的空閑區。

缺點：空閑區的大小一般與申請分區大小不相等，因此將其一分為二，留下來的空閑區一般情況下是很小的，以致無法使用。隨著時間的推移，系統中的小空閑區會越來越多，從而造成存儲空間的浪費。最優適應算法 int BF(){ int t=0;湖北民族學院信息工程學院11級計算機專業操作系統課程設計

readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

printf““輸入進程申請空間大小:””);scanf““%””,&D.size);

idly l=Is;idly min=NULL;int mt=256;busy b=Bs;while(l)//在空閑鏈中尋找第一個大于所輸入的進程大小的空閑塊

{

if(D.size<=l->size)

{

if(l->size

{

mt=l->size;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));空間

j->from=min->from;

//申請分配用于存放進程的內存

//找到第一個滿足要求的空閑塊

//將第一個滿足要求的空閑塊（min）的首地址賦給j

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];16 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

}

j->r.size=D.size;

while(b->next)

//按從小到大的順序查找新進程在已分配區中的位置

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;

} return t;}

最壞適應算法

為了克服最佳適應算法把空閑區切割得太小的缺點，人們提出了一種最壞適應算法，即每次分配時，總是將最大的空閑區切去一部分分配給請求者，剩余的部分仍是一個較大的空閑區。避免了空閑區越分越小的問題。要求空閑區按容量遞減的順序排列。

分配：進程申請存儲區時，檢查空閑區表（鏈）的第一個空閑區的大小是否滿足要求，若不滿足則令進程等待；若滿足則從該空閑區中分配一部分存儲區給用戶，剩下的部分仍作為空閑區。最壞適應算法 int WF(){ int t=0;readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

printf““輸入進程申請空間大小:””);

//將所輸入的進程插入進程鏈

//改變該空閑塊的起始地址 //改變該空閑塊的剩余大小 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

scanf““%””,&D.size);

//輸入進程申請的空間大小

idly l=Is;//l指向空閑鏈表ls頭

idly min=NULL;int mt=0;busy b=Bs;

//b指向已分配鏈表Bs頭

//找到空閑分區中大小滿足進程的請求且尺寸最大的結點

while(l){

if(D.size<=l->size)//判斷進程所申請的大小是否小于空閑區的各結點大小

{

if(l->size>mt)

{ mt=l->size;min=l;//min指向空閑區中尺寸最大的結點

t=1;

}

}

l=l->next;} if(mt!=0)點

{

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

//判斷是否找到了空閑區的滿足結

//l指向空閑鏈表下一個結點

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

while(b->next)置

//尋找插入到已分配鏈表中的位

{ if(b->next->fromfrom)

b=b->next;else

break;

}

//把此進程結點j插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改空閑鏈表的相應結點的參數

min->from=min->from+D.size;

min->size=min->size-D.size;} return t;}

可變分區的回收

當某個進程釋放某存儲區時，系統首先檢查釋放區是否與系統中的空閑區相鄰若相鄰則把釋放區合并到相鄰的空閑區去，否則把釋放區作為一個空閑區插入到空閑表的適當位置。

釋放區與空閑區相鄰的四種情況。

（1）釋放區與前空閑區相鄰：把釋放區與前空閑區合并到一個空閑區。其首址仍為前空閑區首址，大小為釋放區大小與空閑區大小之和。

（2）釋放區與后空閑區相鄰：則把釋放區合并到后空閑區，其首地址為釋放區首地址，大小為二者之和。

（3）釋放區與前后兩空閑區相鄰：這三個區合為一個空閑區，首地址為前空閑區首址，大小為這三個空閑區之和，并取消后空閑區表目。

（4）釋放區不與任何空閑區相鄰：將釋放區作為一個空閑區，將其大小和首址插入到空閑區表的適當位置。

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

回收內存算法

int recover(){ readyque D;printf““請輸入想要回收的進程名””);

scanf““%””,D.name);

busy b=Bs;idly l=Is;while(b->next)鏈表中

{

bool yo=1;

for(int i=0;i<10;i++)

{

if(b->next->r.name[i]==D.name[i])yo=yo*1;

else yo=0;

}

//如果在已分配鏈表中則釋放該結點所占空間

if(yo)

{

int t=b->next->from;

int ts=b->next->r.size;

//查找輸入的進程名是否在已分配湖北民族學院信息工程學院11級計算機專業操作系統課程設計

while(l)

{ if(l->from>t+ts)不鄰接

{ idly tl;tl=(idly)malloc(sizeof(idlyspace));tl->from=t;tl->size=ts;tl->next=l;Is=tl;break;} if(l->from==t+ts)

l->from=t;

l->size=l->size+ts;

busy tb=b->next;

b->next=b->next->next;

free(tb);

return 1;}

if(l->from+l->size

idly tl;

tl=(idly)malloc(sizeof(idlyspace));

tl->from=t;

tl->size=ts;

tl->next=l->next;

l->next=tl;

break;}

else if(l->from+l->size==t)

//所回收進程與空閑結點上鄰接 {

//所回收進程與空閑結點上下都不鄰接

//所回收進程與空閑結點下鄰接 {

//所回收進程與空閑結點上下都 21 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

l->size=l->size+ts;

if(l->from+l->size==l->next->from)接

{

l->size=l->size+l->next->size;

idly tm=l->next;

l->next=l->next->next;

freI);

}

br

l=l->next;

}

//從已分配鏈表中釋放所回收進程

busy tb=b->next;

b->next=b->next->next;

free(tb);

return 1;

}

b=b->next;} printf(“沒找到這”進程n”);return 0;}

//所回收進程與空閑結點上下都鄰調試與操作說明

初始界面

程序初始界面，有四個塊選擇，選擇要執行的算法，調試以最壞算法為例，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

選擇最壞適應算法，如圖

模擬內存分配

給進程a分配內存20，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

已分配分區說明表界面

同理，給進程b分配內存30，給進程c分配內存40，給進程d分配50，給進程e分配60，如圖

空閑分區說明表界面 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

查看空閑分區，如圖

回收內存界面

回收進程b和d所占內存，如圖

已分配分區說明表和空閑分區說明表 如圖 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

重新申請內存界面

再為新進程i分配內存30，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

根據最壞適應算法結合圖所示可知，該算法將會從空閑分區表中選擇一塊最大的內存空間分配給進程i，從圖也可看出該模擬算法實現了最壞適應算法

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

總結與體會

本次做的課題是動態分區分配算法實現，此次課程設計成功實現了內存分配和內存回收，內存分配中包含了四種算法，分別是首次適應算法，循環首次適應算法，最佳適應算法和最壞適應算法。經編碼調試，表明該程序模塊是有效可行的。

通過這門課程的學習讓我充分了解了內存管理的機制實現，從而更深一步的的對計算機

有了很多了解，這對于以后我們的研究和學習計算機系統起到了很重要的作用。

對于本次論文制作，自己的編程能力有所提高，對操作系統內存分配，存儲空間的回收都有全新的認識。

在這次操作系統課程設計中，我使用了c++編寫系統軟件，對os中可變分區存儲管理有了深刻的理解，但是過程中遇到了很多困難，一邊做一邊學，對c++有了比較多的理解。

實驗中遇到很多問題，浪費了很多時間，總而言之是自己學習還不夠好，不扎實，希望在以后學習中加以改善，學到更多知識。

參考文獻

【1】 湯子瀛，哲鳳屏，湯小丹.計算機操作系統.西安：西安電子科技大學出版社，2001.。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

【2】 任愛華.操作系統實用教程.北京：清華大學出版社，2001。

第三篇：操作系統課程設計

長春理工大學 軟件學院 0813111班 27號

姓名：丁為勝 一． 概述

1、課程設計目的及任務課程設計地點及要求

每個學生一臺微機，需要安裝windows98或windows2000操作系統，配備VC、VB、java或C編程語言，每個學生上機時間不少于24個小時。

操作系統是計算機專業的核心專業課，“操作系統課程設計”是理解和鞏固操作系統基本理論、原理和方法的重要的實踐環節。

操作系統課程主要講述的內容是多道操作系統的原理與技術，與其它計算機原理、編譯原理、匯編語言、計算機網絡、程序設計等專業課程關系十分密切。本課程設計的目的綜合應用學生所學知識，建立系統和完整的計算機系統概念，理解和鞏固操作系統基本理論、原理和方法，掌握操作系統基本理論與管理方式。在算法基礎上，解決實際的管理功能的問題，提高學生實際應用、編程的能力。

主要任務是實現操作系統和相關系統軟件的設計，其中涉及進程創建，同步，進程間的通信，存儲管理，文件系統等操作系統概念。

2.課程設計地點及要求

每個學生一臺微機，需要安裝windows98或windows2000操作系統，配備VC、VB、java或C編程語言，每個學生上機時間不少于24個小時。

3.課程設計的內容

設計二： 設計任務：

掌握進程的管道通訊機制和信號量同步互斥機制。1． 進程的管道通訊

編制一個程序，程序中創建一個子進程。然后父子進程各自獨立運行，父進程不斷地在標準輸入設備上讀入小寫字母，寫入管道。子進程不斷地從管道中讀取字符，轉換為大寫字母后輸出到標準輸出設備上。當讀到x時，結束。

2． 信號量實現的同步互斥機制

編制一個程序，程序中創建5個子進程，代表五位哲學家，然后父進程結束。使用信號量機制解決哲學家進餐問題。當哲學家進餐時，屏幕輸出：

[進程號] eating!當哲學家思考時，屏幕輸出： [進程號] thinging!相關的系統調用和函數：pipe();write();read();semget();sepop();semctl();要求：查找并閱讀上述系統調用的相關資料，將上述相關的函數封裝為P()、V()操作，使用你封裝的P()、V()操作實現5位哲學家的同步和互斥。

二． 設計的基本概念和原理

1.進程的管道通訊

管道（Pipe）實際是用于進程間通信的一段共享內存，創建管道的進程稱為管道服務器，連接到一個管道的進程為管道客戶機。命名管道（Named Pipes）是在管道服務器和一臺或多臺管道客戶機之間進行單向或雙向通信的一種命名的管道。一個命名管道的所有實例共享同一個管道名，但是每一個實例均擁有獨立的緩存與句柄，并且為客戶——服務通信提供有一個分離的管道。實例的使用保證了多個管道客戶能夠在同一時間使用同一個命名管道。

2.信號量實現的同步互斥機制

規定奇數號的哲學家先拿起他左邊的筷子,然后再去拿他右邊的筷子;而偶數號 的哲學家則相反.按此規定,將是1,2號哲學家競爭1號筷子,3,4號哲學家競爭3號筷子.即 五個哲學家都競爭奇數號筷子,獲得后,再去競爭偶數號筷子,最后總會有一個哲學家能獲 得兩支筷子而進餐。而申請不到的哲學家進入阻塞等待隊列，根FIFO原則，則先申請的哲 學家會較先可以吃飯，因此不會出現餓死的哲學家。

三． 總體設計

1.實現的方法和主要技術路線

1.無名管道

無名管道用于具有親緣關系的父子進程，子子進程之間的通訊。它的實現函數有 int pipe(int fd[2]);

//fd[2] 為描述符數組，包含一個讀描述符與一個寫描述符，在使用管道通信時，關閉某些不需要的讀或寫描述符，建立起單向的讀或寫管道，然后用read 和write 像操作文件一樣去操作它即可。

如圖便是進程1 到進程2 的一個讀管道。

分別在父進程和父子進程里向管道寫數據，然后在子進程和子子進程里讀數據。2.哲學家進餐偽碼：

semaphore chopstick[5]={1，1，1，1，1};void philosopher(int i){

while(true){

think();

if(i%2 == 0)//偶數哲學家，先右后左。

{

wait(chopstick[ i + 1 ] mod 5);wait(chopstick[ i]);eat();

signal(chopstick[ i + 1 ] mod 5);signal(chopstick[ i]);}

Else //奇數哲學家，先左后右。

{

wait(chopstick[ i]);

wait(chopstick[ i + 1 ] mod 5);eat();

signal(chopstick[ i]);

signal(chopstick[ i + 1 ] mod 5);} } 四． 詳細設計

進程的管道通信代碼： import java.io.IOException;import java.io.PipedReader;

public class ReceiverThread1 extends Thread { PipedReader pipedReader;

public ReceiverThread1(SenderThread1 sender)throws IOException

{

pipedReader=new PipedReader(sender.getPipedWriter());

}

public void run()

{ char[] ch=new char[100];StringBuffer sb=null;String str=null;int i=0;try {

while((i=pipedReader.read(ch))!=-1)

{

sb=new StringBuffer();

for(int j=0;j

{

sb.append(ch[j]);

}

str=sb.toString();

System.out.println(“子進程讀取的字符為：”+str.toUpperCase());

if(!str.endsWith(“x”))

{

System.out.print(“父進程讀入字符為：”);

}else if(str.endsWith(“x”))

{

System.out.println(“結束無法再次輸入字符”);

}

} } catch(IOException e){

e.printStackTrace();}finally{

try {

pipedReader.close();

} catch(IOException e){

e.printStackTrace();

} }

}

}

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.PipedWriter;

public class SenderThread1 extends Thread { PipedWriter pipedWriter;

public SenderThread1(){

pipedWriter=new PipedWriter();}

public PipedWriter getPipedWriter(){

return pipedWriter;}

public void run()

{ BufferedReader ir=new BufferedReader(new InputStreamReader(System.in));char[] ch=new char[100];StringBuffer sb=null;String str=null;int i=0;System.out.print(“父進程讀入字符為：”);try {

while((i=ir.read(ch))!=-1)

{

sb=new StringBuffer();

for(int j=0;j

{

if(ch[j]>='a' && ch[j]<='z')

{

sb.append(ch[j]);

if(ch[j]=='x')

{

break;

}

}

}

str=sb.toString();

pipedWriter.write(str);

if(str.startsWith(“x”)||str.endsWith(“x”))

{

break;

// this.stop();

}

}

} catch(IOException e){

e.printStackTrace();}finally{

try {

ir.close();

pipedWriter.close();

} catch(IOException e){

e.printStackTrace();

}

}

} }

public class ThreadComm1 { public static void main(String[] args)throws Exception{ SenderThread1 sender=new SenderThread1();ReceiverThread1 receiver=new ReceiverThread1(sender);sender.start();receiver.start();} } 哲學家進餐問題代碼： #include “stdafx.h” using namespace std;bool chop[100];//定義筷子 class ph { protected: bool * left,* right;//哲學家的左右手指向的筷子

int eattime;//哲學家的吃飯時間 public: bool check()//用于檢查哲學家左右手的筷子是不是被占用

{

if(*left && *right)

return true;

else

return false;} void eat(int ineattime)//哲學家開始進餐

{

eattime=ineattime;

*left=false;

*right=false;} bool finish()//檢查哲學家是否完成進餐

{

if(eattime>0)//沒完成的話剩余時間減少

{

eattime--;

if(eattime==0)//完成的話歸還筷子

{

*left=true;

*right=true;

return true;

}

else

return false;

}

else

return false;} void init(int num,int max)//初始化哲學家，指定他們使用的筷子

{

eattime=0;

left=&chop[num];

if(num

right=&chop[num+1];

else

right=&chop[0];} };void main(){ system(“title 哲學家進餐問題”);int in,i,temp,time,j=1;queue Q;ph P[100];

for(int i=0;i<5;i++){

chop[i]=1;

} for(int i=0;i<5;i++){ P[i].init(i,5);} cout<<“輸入哲學家進餐隊列：”<>in;if(in==0)

break;else

if(in>5)

{

cout<<“一共只有”<<5<<“個人！”<

}

else

{

Q.push(in-1);

} } cout<<“每個人吃飯時間：”<>time;system(“CLS”);system(“color 0a”);while(!Q.empty()){ temp=Q.front();Q.pop();if(P[temp].check()){

P[temp].eat(time);

cout<

if(temp+2>5)

cout<<1<

else

cout<

Q.push(temp);} for(i=0;i<5;i++)

{

if(P[i].finish())

cout<

}

//Q.push(-1);

for(i=0;i

{

temp=Q.front();

Q.pop();

//if(temp!=-1)

{

cout<

Q.push(temp);

}

//else

{

// Q.pop();

break;

}

} } for(int j=0;j

if(P[i].finish())

{

cout<

} getch();}

第四篇：操作系統課程設計

引言

操作系統是計算機科學與技術專業的主要專業基礎課和主干課。操作系統對計算機系統資源實施管理，是所有其他軟件與計算機硬件的唯一接口，所有用戶在使用計算機時都要得到操作系統提供的服務。

通過模擬操作系統的全部或者部分功能的實現，加深對操作系統工作原理和操作系統實現方法的理解，達到練習編程的目的，提高學生運用理論知識分析問題、解決問題的能力，為學生從事科學研究和獨立負擔計算機及其應用方面的工作打好扎實的基礎。

0 河北大學工商學院2011級操作系統課程設計論文（設計）課程設計任務及要求

2.1 設計任務

模擬采用多道程序設計方法的單用戶操作系統，該操作系統包括進程管理、存儲管理、設備管理、文件管理和用戶接口四部分。

本部分要求實現文件的邏輯結構、文件的物理結構、目錄結構、磁盤分配和回收、文件的保護和用戶接口。

2.2 實現方法和原理

2.2.1文件的邏輯結構：

文件的邏輯結構采用流式結構； 文件均采用文本文件；

系統中有兩種文件，一種是存放任意字符的文件，一種是可執行文件。可執行文件的內容就是模擬系統內進程的程序體。

文件中要有一種特定命令的“可執行”文件，文件中的命令非常簡單，包括： x=?;

給x賦值一位數 x++;

x加1 x--;

x減1!??；

第一個？為A,B,C中某個設備，第二個？為一位數，表示使用設備的時間（由于沒有實際設備，所以無法知道設備何時工作完成，所以假定一個數，這個數隨著系統時間增加而遞減，減到0時，認為是設備工作完成）；

end.表示文件結束，同時將結果寫入文件out，其中包括文件路徑名和x的值。2.2.2 磁盤模擬：

用一個文件disk模擬磁盤，磁盤的每個盤塊64字節，模擬磁盤共有128塊。第0、1塊存放文件分配表，第2塊存放根目錄，其余存放子目錄和文件。2.2.3目錄結構

目錄結構采用樹型目錄結構，目錄項內容共十六個字節。①目錄項內容（8個字節）： 目錄名、文件名：3個字節；

河北大學工商學院2011級操作系統課程設計論文（設計）

擴展名：1個字節（可執行文件擴展名為e，目錄沒有擴展名）； 目錄、文件屬性：1字節； 起始盤塊號：1個字節；

文件長度：2字節（目錄沒有長度）。②根目錄

根目錄位置固定，為磁盤第2塊，大小固定，共8項，占用模擬磁盤第2塊； ③子目錄

位置不固定，大小不固定。2.2.4磁盤分配

磁盤的分配采用鏈接結構（顯式鏈接）的分配方式。系統采用文件分配表方式記錄磁盤空間的使用情況和鏈接結構的指針。

因為磁盤有占用磁盤由128塊，所以文件分配表中一項需要1字節，而磁盤由128塊，因而需要128項，所以模擬磁盤空間中的第0、1塊被用來存放文件分配表。2.2.5用戶接口

用戶接口提供用戶命令接口，要求實現以下命令： 創建文件：create 拷貝文件：copy 刪除文件：delete 移動文件：move 顯示文件：type 編輯文件：edit 改變文件屬性：change 磁盤格式化命令 format 建立目錄：makdir 改變目錄路徑：chadir

刪除空目錄：rdir 刪除目錄：deldir（既可刪除空目錄又可刪除非空目錄）

河北大學工商學院2011級操作系統課程設計論文（設計）

磁盤分區命令：fdisk 運行可執行文件：可執行文件的文件名（可創建進程）。

上述命令在實際系統中都是需要建立進程才可以實現的，這里由于模擬系統的能力達不到，所以除運行可執行文件需要建立進程外，其他指令執行不必在模擬系統中建立進程，可直接執行。

注意打開文件表。2.2.6屏幕顯示

如圖所示，屏幕顯示要求包括：

用戶命令接口，用于系統運行時用戶輸入命令； 磁盤目錄顯示，要求顯示磁盤的樹型目錄結構；

磁盤使用情況，顯示磁盤每一個磁盤塊的空間是占用還是空閑。

3程序設計與實現

3.1目錄結構的實現

3.1.1創建目錄

#region CreateMenu(建立目錄)

public void CreateMenu(string pathname,string harddisk)3.1.2刪除空目錄

刪除空目錄首先要找到該目錄，如果目錄不存在，執行指令失敗；如果存在，但是根 河北大學工商學院2011級操作系統課程設計論文（設計）

目錄或非空目錄顯示不能刪除，操作失敗；若是非空子目錄，則刪除器目錄項并回收對應空間。刪除空目錄的過程和刪除文件的過程相似。

3.1.3刪除目錄

#region DeleteMenu(刪除目錄)

public void DeleteMenu(string pathname, string harddisk)

{

if(Search(pathname,harddisk)== 1)

{

MessageBox.Show(“文件路徑不正確！”, “注意”, MessageBoxButtons.OK, MessageBoxIcon.Exclamation);3.2文件 3.2.1創建文件

#region CreateFile(建立文件)public void CreateFile(string pathname, byte attribute, byte address, char length, string harddisk){

if(attribute == 3 || attribute == 5){

MessageBox.Show(“只讀性質，建立失敗！”, “注意”, MessageBoxButtons.OK，MessageBoxIcon.Exclamation);

return;} 3.2.2拷貝文件

#region CopyFile(復制文件,只復制FCB)

public void CopyFile(string pathname1, string pathname2, string harddisk)

{

string[] pnames = pathname1.Split(new char[] { '', '.' });

string halfpathname = pathname1.Remove(pathname1.Length1]);

UTF8Encoding utf = new UTF8Encoding();4 河北大學工商學院2011級操作系統課程設計論文（設計）

byte[] name = utf.GetBytes(pnames[pnames.Length1];

CreateFile(pathname2, buffer.Attribute, buffer.Address, buffer.Length,harddisk);

}

#endregion 3.2.3刪除文件 #region DeleteFile(刪除文件)

public void DeleteFile(string pathname, string harddisk)

{

if(Search(pathname,harddisk)==1)

{

MessageBox.Show(“文件路徑不正確！”, “注意”, MessageBoxButtons.OK, MessageBoxIcon.Exclamation);

return;

}

else if(Search(pathname,harddisk)== 2)

//文件存在 {

string[] pnames = pathname.Split(new char[] { '', '.' });

string halfpathname = pathname.Remove(pathname.Length2]);

int disknum;

if(pnames.Length == 3)

//c:aaa.t

{

disknum = 3;

}

else

{

disknum = Search(halfpathname,harddisk);

}

int item = FindItem(disknum, name, attribute,harddisk)[0];

int address = FindItem(disknum, name, attribute,harddisk)[1];

byte addr = Convert.ToByte(address);

DeleteFCB(disknum, item,harddisk);

//刪除FCB

if(addr==0)

{

return;3.2.4移動文件

#region CutFile(移動文件)

public void CutFile(string pathname1, string pathname2, string harddisk)

{

CopyFile(pathname1, pathname2,harddisk);//復制FCB到新目錄下

string[] pnames = pathname1.Split(new char[] { '', '.' });

string halfpathname = pathname1.Remove(pathname1.Length1]);

UTF8Encoding utf = new UTF8Encoding();6 河北大學工商學院2011級操作系統課程設計論文（設計）

byte[] name = utf.GetBytes(pnames[pnames.Length1)+ 8 *(Itemnumber-1), SeekOrigin.Begin);

Disk.Write(buffer.Name, 0, buffer.Name.Length);

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(buffer.Type);

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(buffer.Attribute);

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(buffer.Address);7 河北大學工商學院2011級操作系統課程設計論文（設計）

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(Convert.ToByte(buffer.Length));

}

Disk.Close();

}

#endregion

3.2.7顯示文件

#region ReadFile(讀文件畫節點)

public void ReadFile(TreeView treeView, ContextMenuStrip contextMenuStrip,ImageList imageList)

{

treeView.Nodes.Clear();

//刪除集合中所有樹節點

//重新添加樹節點

treeView.ImageList = imageList;

TreeNode root = new TreeNode(“計算機”, 0, 0);

TreeNode node_C = new TreeNode(“本地磁盤C”, 4, 4);

TreeNode node_D = new TreeNode(“本地磁盤D”, 4, 4);

node_C.ContextMenuStrip = contextMenuStrip;

node_D.ContextMenuStrip = contextMenuStrip;

treeView.Nodes.Add(root);

root.Nodes.Add(node_C);

root.Nodes.Add(node_D);

DrawTree(node_C, 3,“disk1.txt”,contextMenuStrip);

DrawTree(node_D, 3, “disk2.txt”,contextMenuStrip);

treeView.ExpandAll();

}

#endregion

4.程序運行部分截圖

4.1主頁面 河北大學工商學院2011級操作系統課程設計論文（設計）

4.2創建文件

4.3編輯文件河北大學工商學院2011級操作系統課程設計論文（設計）

4.4創建目錄 總結

在此系統我主要模擬的是文件部分。通過編寫此系統，采用了c#語言。但是，在實現此系統中，一方面因為我對c#這門語言掌握的不是很熟練，另外一方面，對操作系統理解的不夠深入以至于部分功能沒有實現，讓我發現了自己的不足，從而要在以后的學習中更加努力，不短提高自己個方面的能力。

河北大學工商學院2011級操作系統課程設計論文（設計）

裝

訂

第五篇：操作系統課程設計報告

課程設計報告

題 目： 模擬請求頁式管理

課程名稱： 計算機操作系統 學 院： 信息工程學院

專 業： 計算機科學與技術

班 級： 14計本（1）學生姓名： * * * 學 號： 201403031** 指導教師： * * 成 績：

開課時間： 2016-2017 學年 一 學期

模擬請求頁式管理

第1章 需求分析

1.1設計要求

請求頁式管理是一種常用的虛擬存儲管理技術。本設計通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式管理的頁面置換算法。本實驗要求用Vc＋＋或其他高級語言編寫和調試。

編寫程序實現：

（1）先進先出頁面置換算法（FIFO）（2）最近最久未使用頁面置換算法（LRU）最佳置換頁面置換算法（OPT）設計一個虛擬存儲區和內存工作區，編程序演示以上三種算法的具體實現過程，并計算訪問命中率。

1.2解決方案

首先確定實現語言使用c#實現圖形化界面，后確定要實現哪些功能，比如算法選擇，頁面添加，模擬控制。然后確定輸出結構以便于程序的測試和驗證。將基本框架建立后再進行編程。編程前進行算法結構分析最后編程實現。

1.3算法實現原理

1、先進先出置換算法（FIFO）：

發生缺頁中斷時按照頁面進入內存順序總是淘汰最先進入內存的頁面。

2、最近最久未使用置換算法（LRU）：

發生缺頁中斷時總是淘汰存在內存中最長時間未被使用的頁面。

3、最佳置換算法（OPT）：

發生缺頁中斷時若一個或幾個頁面將來將不會被調用則按先進先出原則淘汰頁面，若將來都有調用則比較調用時刻選擇最遠時刻頁面淘汰。

4、缺頁率：缺頁次數占頁面調用次數的百分比。

第2章 概要設計

2.1數據設計

常變量：調用頁面最大數量（MaxN），內存最大頁面數（MaxM）待調用頁面數組：page_dd[MaxN]存放等待調用的頁面號

頁面數組專用指針 page_p，用于指向page_dd數組中正需調入內存的頁號 內存塊數組：Memery[MaxM]，存放內存當前存放的頁號 缺頁計數器：count，記錄缺頁次數

內存塊狀態數組：M1[MaxN],M2[MaxN],M3[MaxN]，記錄每次頁面調用結束后內存各塊的狀態

缺頁記錄數組s[MaxN]，用于記錄頁面調用時是否產生缺頁中斷，初始化為是

2.2函數設計

1、頁面添加函數：void btnAdd_Click(object sender, EventArgs e)用于實現通過點擊按鈕實現數據輸入。

2、內存初始化函數：init(int[] a, int[] b,int []m1,int[]m2,int[]m3)參數有頁面數組、內存數組、狀態數組，采用先進先出算法對內存先進行裝滿 服務于先進先出頁面置換函數和最佳置換函數。

3、輸出函數：void display(int[]a,int[]m1,int[]m2,int[]m3,char[]c)用于輸出模擬結果，參數有頁面數組，內存數組，狀態數組，缺頁記錄數組。再模擬之后調用。

4、模擬控制函數：void btnmo_Click(object sender, EventArgs e）用于實現通過單擊模擬按鈕，根據用戶所選算法進行模擬并顯示結果。

5、先進先出算法模擬函數：

void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s)用于實現先進先出算法模擬，參數有頁面數組，內存數組、內存狀態記錄數組，缺頁記錄數組。在模擬函數中調用。

6、最近最久未使用算法模擬函數：

void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于 3 實現最近最久未使用算法模擬，參數有頁面數組，內存數組，內存狀態記錄數組，缺頁記錄數組。在模擬函數中被調用。

7、最近最久未使用函數輔助函數：void LUR_I(int[] a,int e)用于對最近最久未使用算法中所用輔助數組（記錄頁面存在時長）進行調整，參數有輔助數組及需調整的數據下標。在最近最久未使用函數中調用。

8、最佳置換算法模擬函數：

void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于模擬最佳置換算法。參數有頁面數組，內存數組，內存狀態記錄數組，缺頁記錄數組。在模擬函數中被調用。

9、最佳置換算法輔助函數：void OPT_F(int[] a, int e)用于對最佳置換算法中的輔助數組進行調整。參數有輔助數組，需調整數據下標。在最佳置換算法中被調用。

10、重置函數：void btncz_Click(object sender, EventArgs e)用于重新選擇算法進行新的模擬。

2.3主要算法設計

1、初始化函數算法：

第一步：將第一個頁面調入內存，調整最佳置換算法輔助數組，缺頁計數器加一，保存內存數組狀態。

第二步：調用下一個頁面并判斷內存中是否有本頁面有轉第三步，無轉第四步。第三步：更改缺頁數組對應下標值，記錄當前內存狀態，調整最佳置換算法輔助數組，頁面指針指向下一頁。

第四步：將頁面調入內存，調整最佳置換算法輔助函數，缺頁計數器加一，保存內存數組狀態。若內存尚不滿轉第一步。具體見圖1初始化算法流程圖。

開始頁面調入內存缺頁計數器加一記錄內存狀態調用下一頁否否內存是否有該頁面是記錄內存狀態修改缺頁數組內存已滿是結束

圖1 初始化算法流程圖

2、先進先出頁面置換算法：

第一步：檢查內存中是否已有需調用頁面，有則轉第二步，無則轉第三步。第二步：記錄當前內存狀態，修改缺頁數組對應下標值。

第三步：內存中無需要調用的頁面，進行出隊操作，然后進行入隊操作，記錄內存塊狀態，缺頁計數器加一。

第四步：若頁面數組未被調用結束轉第一步。具體見圖2先進先出算法流程圖。

開始頁面調入內存該頁在內存中是否已存在是否否先出隊操作后入隊操作記錄內存狀態修改缺頁數組值記錄內存狀態缺頁計數器加一頁面調用結束是結束

圖2 先進先出算法流程圖

3、最近最久未使用置換算法：

第一步：將頁面調入內存，記錄內存狀態，缺頁計數器加一，調整輔助數組，頁面指針加一。

第二步：檢查內存中是否已有所需頁面，有轉第三步，無轉第一步。

第三步：修改缺頁數組對應下標記錄，記錄內存狀態，調整輔助數組，頁面指針加一。第四步：內存是否已滿，無則轉第一步，是則轉第五步。

第五步：檢查內存中是否有所需頁面，有則記錄當前內存狀態，修改缺頁數組對應下標值。無則轉第六步。

第六步：檢查輔助數組找出最大值并記錄其下標，置換內存中對應下標的數據，調整輔助數組，缺頁計數器加一。

第七步：頁面是否調用結束未結束則轉第五步。具體見圖3最近最久未使用算法流程圖。

開始調入頁面至內存記錄內存狀態計數器加一否調整輔助數組調用下一頁內存中是否已有該頁否內存已滿是通過輔助數組確定淘汰頁面是修改缺頁數組記錄內存狀態調整輔助數組否頁面置換記錄內存狀態計數器加一調用結束是結束

圖3 最近最久未使用算法

4、最佳置換算法：

第一步：檢查內存中是否已有所需頁面，有則記錄內存狀態，修改缺頁數組對應下標數值。無則轉第二步。

第二步：判斷內存中各頁面的未來調用情況，記錄是否還有調用，若有則記錄調用時刻。

第三步：分析調用情況，內存中頁面都在將來不會被調用轉第四步，有一個被調用轉第五步，有兩個被調用轉第六步，全被調用轉第七步。

第四步:查找輔助數組找到內存中存在時間最長的頁面進行置換，修改內存狀態，缺頁計數器加一，修改輔助數組。

第五步：查找到不會被調用的頁面，并根據輔助數組選擇最早進入內存的頁面將其置換。修改內存狀態，缺頁計數器加一，修改輔助數組。

第六步：查找輔助數組找到將來不需要在調用的頁面將其置換，修改輔助數組，記錄內存狀態，缺頁計數器加一。

第七步：查找輔助數組，找尋最晚被調用的頁面，將其置換。記錄內存狀態，修改輔助數組，缺頁計數器加一。

第八步：頁面是否調用完成，否則轉第一步。具體見圖4最佳置換算法流程圖

開始調入頁面記錄內存狀態計數器加一更新輔助函數是頁面已存在否向后檢查內存當前頁面調用情況所有頁面都不會再度調用否是一個頁面會調用否否是兩個頁面會調用是否查找輔助數組得到最先進入頁面通過輔助數組得到不會再調用的頁面通過輔助數組獲取最晚調用的頁面通過輔助數組得到另外兩個頁面中最先進入的頁面置換頁面記錄內存狀態計數器加一更新輔助函數頁面調用結束是結束

圖4 最佳置換算法流程圖 2.4界面設計

采用c# 設計windows窗體應用程序，使用下拉列表框選擇算法，通過按鈕添加待調用的頁面。通過文本控件顯示模擬結果。顯示樣式：第一行：算法名稱；

第二行：調用頁面順序；

第三行至第五行顯示內存在每調用一次頁面后的狀態；

第六行：是否缺頁；

最后一行顯示缺頁率；

第3章 詳細設計與實現

3.1函數設計

1、添加按鈕功能實現代碼

主要功能：實現單擊一次添加一個調用頁面，并給出相應的提示，如正在輸入的是第幾次調度頁面，在輸入為空時能夠彈出對話框提示用戶，在輸入完成時為避免數組越界應在輸入完成時隱藏；輸入過程中始終保證時輸入焦點。private void btnAdd_Click(object sender, EventArgs e){ if(txtAdd.Text!= “")//輸入不為空才能繼續輸入 { page_dd[i_add] = Convert.ToInt32(txtAdd.Text);/*將輸入值賦值給頁面數組*/ txtShow.Text += txtAdd.Text + ” “;/*顯示供用戶查閱*/ i_add++;txtAdd.Clear();/*清空*/ if(i_add == MaxN)//輸入結束時 { txtAdd.ReadOnly = true;//不允許繼續輸入 btnAdd.Hide();//按鈕隱藏 return;} txtAdd.Focus();//設置為輸入焦點

label2.Text = ”第“ +(i_add + 1)+ ”次調度頁面：“;/*提示用戶正在輸入的是第幾次調度頁面*/ } /*輸入為空則彈出對話框提示用戶輸入為空*/ else { MessageBox.Show(”請輸入調用頁面！“, ”輸入為空“, MessageBoxButtons.OK, MessageBoxIcon.Warning);txtAdd.Focus();} }

2、初始化函數

主要功能：將內存一先進先出方式填滿，并記錄每個頁面進入時間，服務于先進先出頁面置換算法和最佳置換算法。

void init(int[] a, int[] b,int []m1,int[]m2,int[]m3){ /*內存未滿時循環*/ for(int i = 0;i < MaxM&&page_p

//調整輔助數組將剛進入內存的頁面的對應時間 OPT_F(O_Q ,i)； count++;//缺頁計數器加一 m1[page_p] = b[0];//保存內存狀態 m2[page_p] = b[1];m3[page_p] = b[2];page_p++;//調用下一頁面

//檢查內存中是否原先就有需要的頁面； for(int j = 0;j <= i&&page_p

s[page_p] = 'F';//缺頁數組對應數據更改 m1[page_p] = b[0];//記錄內存狀態 m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);//調整最佳置換算法輔助函數 page_p++;//調用下一頁 j =-1;//重新開始尋找 } } } }

3、先進先出頁面置換函數

主要功能：根據先進先出算法要求在產生缺頁中斷時采用先進先出方式確定淘汰頁面，并在每次頁面調用時記錄下內存狀態，缺頁次數；采用循環隊列使得每次出隊的一定是最先進入內存的。

private void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s){ int Fpage_p = page_p;int front, rear;//定義隊列對手和對尾指針并初始化 front = 0;rear = MaxM1;int sa;for(;Fpage_p < MaxN;Fpage_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//檢查內存中是否已有要調用的頁面。

{ if(b[i] == a[Fpage_p]){ m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];s[Fpage_p] = 'F';sa = 1;break;} } if(sa == 0){ front =(front + 1)% MaxM;

rear =(rear + 1)% MaxM;b[rear] = a[Fpage_p];m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];count++;} else continue;} } /*最近最久未使用算法輔助數組調整函數*/ private void LUR_I(int[] a,int e){ int temp;temp = a[e];a[e] = 1;for(int i = 0;i < MaxM;i++){ if(a[i] < temp && i!=e)a[i]++;} } /*最佳置換算法輔助數組調整函數*/ private void OPT_F(int[] a, int e){ if(e!=-1){ a[e] = 0;for(int i = 0;i < MaxM;i++){ if(i!= e)a[i]++;} } else for(int i = 0;i < MaxM;i++){ a[i]++;} } /*最近最久未使用算法*/ private void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){

int[] L_Q = new int[MaxM]{3,3,3};int sa;for(int i = 0;i < MaxM && page_p < MaxN;i++){ b[i] = a[page_p];//調入內存 count++;m1[page_p] = b[0];//保存內存狀態 m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);page_p++;for(int j = 0;j <= i && page_p < MaxN;j++){ if(b[j] == a[page_p]){ s[page_p] = 'F';m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, j);page_p++;j =-1;} } } for(;page_p < MaxN;page_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//用的頁面。{ if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];s[page_p] = 'F';LUR_I(L_Q, i);sa = 1;break;} } if(sa == 0){

檢查內存中是否已有要調40 for(int i = 0;i < MaxM;i++){ if(L_Q[i] == 3){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);break;} } count++;} else continue;} } /*最佳置換算法*/ private void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){ int sa;int O_p;int Ocount;int[] OPT_I=new int [MaxM ]{-1 ,-1 ,-1 };int[] OPT_J=new int [MaxM]{MaxN ,MaxN ,MaxN };for(;page_p < MaxN;page_p++){ for(int i = 0;i < MaxM;i++){ OPT_I[i] =-1;//刷新狀態數組 OPT_J[i] = MaxN;} sa = 0;for(int i = 0;i < MaxM;i++)//檢查內存中是否已有要調用的頁面。

{

if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);

s[page_p] = 'F';sa = 1;break;} } if(sa == 0)//缺頁 { Ocount = 0;for(int i = 0;i < MaxM;i++){ O_p = page_p + 1;for(;O_p < MaxN;O_p++){ if(b[i] == a[O_p]){ Ocount++;OPT_I[i] = 1;OPT_J[i] = O_p;break;} } } switch(Ocount){ case 0://全部頁面以后都不會再度調用 int temp = 0;for(int i = 0;i < MaxM;i++){ if(O_Q[i] > O_Q[temp])temp = i;} b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 1://有一個頁面將在以后調用 temp = 0;for(int i = 0;i < MaxM;i++){ if(OPT_I[i]!= 1 && O_Q[i] > O_Q[temp])temp = i;

} b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 2: for(int i = 0;i < MaxM;i++){ if(OPT_I[i] ==-1){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, i);count++;} } break;case 3: int p = 0;for(int i = 0;i < MaxM;i++){ if(OPT_J[i] >OPT_J[p])p = i;} b[p] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, p);count++;break;} } } } /*重置函數*/ private void btncz_Click(object sender, EventArgs e){ comboBox1.SelectedIndex = 0;

txtAdd.Text = ”“;page_p = 0;i_add = 0;count = 0;//txtShow.Text = ”";for(int i = 0;i < MaxM;i++)Memery[i] =-1;for(int i = 0;i < MaxN;i++)s[i] = 'T';} } }