第一篇：操作系統(tǒng)課程設(shè)計(jì)題目
遼寧科技大學(xué)操作系統(tǒng)課程設(shè)計(jì)指導(dǎo)書
一、課程設(shè)計(jì)目的和要求
本設(shè)計(jì)是專業(yè)基礎(chǔ)課《操作系統(tǒng)》的課程設(shè)計(jì)。由于操作系統(tǒng)課的學(xué)時(shí)有限，安排實(shí)驗(yàn)的次數(shù)不多。為了進(jìn)一步鞏固實(shí)驗(yàn)成果，加強(qiáng)理論聯(lián)系實(shí)際、分析問題、解決問題的能力，加深對(duì)操作系統(tǒng)的基本概念、原理、技術(shù)和方法的理解，特安排此次課程設(shè)計(jì)。它是操作系統(tǒng)課程的實(shí)踐環(huán)節(jié)。由于具體的操作系統(tǒng)相當(dāng)復(fù)雜，在短短的一周之內(nèi)，不可能對(duì)所有管理系統(tǒng)進(jìn)行詳細(xì)地分析。因此，選擇了操作系統(tǒng)中最重要的管理之一進(jìn)程管理（或進(jìn)程的死鎖、頁面置換算法）作為本設(shè)計(jì)的任務(wù)。另外，通過此次設(shè)計(jì)使學(xué)生在使用系統(tǒng)調(diào)用的同時(shí)，進(jìn)一步了解系統(tǒng)內(nèi)部是如何實(shí)現(xiàn)系統(tǒng)調(diào)用的全過程，使學(xué)生在更深層次上對(duì)操作系統(tǒng)有所了解。要求：
1.在具有自主版權(quán)的Linux環(huán)境下，用c或c++語言，以及相關(guān)的系統(tǒng)調(diào)用，編程實(shí)現(xiàn)進(jìn)程的創(chuàng)建、控制、軟中斷通信、管道通信等功能。2.利用某種高級(jí)語言編程實(shí)現(xiàn)銀行家算法。
3.常用的頁面置換算法有：最佳置換算法（Optimal）、先進(jìn)先出法（Fisrt In First Out）、、最近最久未使用（Least Recently Used），至少實(shí)現(xiàn)其中的兩種算法。
二、課程設(shè)計(jì)內(nèi)容
設(shè)計(jì)題目1：進(jìn)程管理及理解（1）進(jìn)程的創(chuàng)建
編寫一段程序，使用系統(tǒng)調(diào)用fork（）創(chuàng)建兩個(gè)子進(jìn)程。當(dāng)此程序運(yùn)行時(shí)，在系統(tǒng)中有一個(gè)父進(jìn)程和兩個(gè)子進(jìn)程活動(dòng)。讓每一個(gè)進(jìn)程在屏幕上顯示一個(gè)字符：父進(jìn)程顯示“a”；子進(jìn)程分別顯示字符“b”和“c”。試觀察記錄屏幕上的顯示結(jié)果，并分析原因。
（2）進(jìn)程的控制
修改已編寫的程序，將每個(gè)進(jìn)程輸出一個(gè)字符改為每個(gè)進(jìn)程輸出一句話，再觀察程序執(zhí)行時(shí)屏幕上出現(xiàn)的現(xiàn)象，并分析原因。
如果在程序中使用系統(tǒng)調(diào)用lockf（），來給每一個(gè)進(jìn)程加鎖，可以實(shí)現(xiàn)進(jìn)程之間的互斥，觀察并分析出現(xiàn)的現(xiàn)象。
（3）①編制一段程序，使其實(shí)現(xiàn)進(jìn)程的軟中斷通信。
要求：使用系統(tǒng)調(diào)用fork（）創(chuàng)建兩個(gè)子進(jìn)程，再用系統(tǒng)調(diào)用signal（）讓父進(jìn)程捕捉鍵盤上來的中斷信號(hào)；當(dāng)捕捉到中斷信號(hào)后，父進(jìn)程用系統(tǒng)調(diào)用kill（）向兩個(gè)子進(jìn)程發(fā)出信號(hào)，子進(jìn)程捕捉到信號(hào)后分別輸出下列信息后終止：
Child Process11 is Killed by Parent！Child Process12 is Killed by Parent！
父進(jìn)程等待兩個(gè)子進(jìn)程終止后，輸出如下的信息后終止： Parent Process is Killed！
②在上面的程序中增加系統(tǒng)調(diào)用signal（SIGINT,SIG_IGN）和signal（SIGQUIT,SIG_IGN），觀察執(zhí)行結(jié)果，并分析原因。
（4）進(jìn)程的管道通信
編制一段程序，實(shí)現(xiàn)進(jìn)程的管道通信，使用系統(tǒng)調(diào)用pipe（）建立一個(gè)管道文件；兩個(gè)子進(jìn)程P1和P2分別向管道各寫一句話： Child1 is sending a message！Child2 is sending a message！
而父進(jìn)程則從管道中讀出來自于兩個(gè)子進(jìn)程的信息，顯示在屏幕上。
要求父進(jìn)程先接收子進(jìn)程P1發(fā)來的消息，然后再接收子進(jìn)程P2發(fā)來的消息。設(shè)計(jì)題目2：銀行家算法實(shí)現(xiàn)資源分配
要求如下：
(1)進(jìn)程可動(dòng)態(tài)地申請(qǐng)資源和釋放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)地分配資源。(2)要求程序具有顯示和打印各進(jìn)程的某一時(shí)刻的資源分配表和安全序列的功能。(3)顯示和打印各進(jìn)程依次要求申請(qǐng)的資源號(hào)以及為某進(jìn)程分配資源后的有關(guān)資源數(shù)據(jù)。
(4)可能用到的數(shù)據(jù)結(jié)構(gòu)：
? 可利用資源向量Available。它是一個(gè)含有m個(gè)元素的數(shù)組，其中每個(gè)元素代表一類可利用資源的數(shù)目。
? 最大需求矩陣Max。n*m矩陣，表示n個(gè)進(jìn)程的每一個(gè)對(duì)m類資源的最大需求。? 分配矩陣Allocation。n*m矩陣，表示每個(gè)進(jìn)程已分配的每類資源的數(shù)目。? 需求矩陣Need。n*m矩陣，表示每個(gè)進(jìn)程還需要各類資源數(shù)。設(shè)計(jì)題目3：虛擬頁面置換算法的實(shí)現(xiàn)
要求如下：
(1)至少實(shí)現(xiàn)OPT、FIFO、LRU三種置換算法中的兩種。
(2)做成GUI界面最好，若不能，則要求界面盡量友好，便于操作。(3)算法中涉及到的頁面訪問序列可以固定，也可以隨機(jī)生成。
(4)在實(shí)現(xiàn)算法的同時(shí)要計(jì)算每種算法的缺頁數(shù)。(5)以表格的形式輸出最終的頁面置換結(jié)果。
注：以上三個(gè)題目任選其一，還可以自擬其它題目。
選擇題目1的同學(xué)，應(yīng)事先了解（1）Linux的命令及使用格式；
可通過下面的幾個(gè)任務(wù)熟悉有關(guān)文件（夾）操作的命令。
（2）在虛擬機(jī)vmware下讓Linux加載U盤的方法。
（3）利用gcc、gdb編譯、調(diào)試C/C++程序
第二篇：《操作系統(tǒng)課程設(shè)計(jì)》題目要求
操作系統(tǒng)課程設(shè)計(jì)要求
一．設(shè)計(jì)目的
熟悉Linux編程環(huán)境，加強(qiáng)對(duì)Linux命令的理解及函數(shù)的運(yùn)用
二．設(shè)計(jì)內(nèi)容
1.在Linux環(huán)境下模擬實(shí)現(xiàn)簡單命令解釋器。(1)要求實(shí)現(xiàn)的基本命令包括：
pwd
//顯示當(dāng)前所在目錄的路徑名
dir <目錄名>
//列出指定目錄名中的所有目錄及文件 cd <目錄名或路徑>
//改變當(dāng)前工作目錄 newdir <目錄名>
//新建目錄 deldir <目錄名>
//刪除目錄
exit //退出命令解釋程序(2)可選做的擴(kuò)展命令包括：
rename <舊文件名> <新文件名> //重命名一個(gè)文件或目錄
find <目錄>-name <待查找的文件名> //在指定的目錄及其子目錄中查找指定的文件
date //顯示當(dāng)前日期(3)提示：整個(gè)程序的大致框架可參考如下：
while(exit未被輸入){
接收鍵盤的一行輸入
分析輸入的命令
對(duì)輸入的命令進(jìn)行處理，調(diào)用系統(tǒng)函數(shù)實(shí)現(xiàn)功能
} 2.設(shè)計(jì)要求
(1)設(shè)計(jì)必須在Linux環(huán)境下進(jìn)行。
(2)命令解釋程序的提示符為：姓名拼音@(3)程序編寫中不得使用system()系統(tǒng)調(diào)用。
(4)整個(gè)程序必須嚴(yán)格經(jīng)過測試，完成所有基本功能。源程序應(yīng)有較詳盡的注釋。
3.可能用到的系統(tǒng)調(diào)用：
open(),close(),read(),write(),creat()chdir(), opendir(),readdir(),rewinddir(),closedir(),rmdir(),mkdir()getcwd(), ftw()
time(), localtime(), asctime()三． 提交要求：
1.完成的源程序和可執(zhí)行程序必須保存在Linux服務(wù)器上。
2.要求實(shí)現(xiàn)的基本命令必須全部實(shí)現(xiàn)。完成可選做的擴(kuò)展命令將得到較高的分?jǐn)?shù)。容錯(cuò)性強(qiáng)和功能細(xì)節(jié)考慮更完全也將得到較高的分?jǐn)?shù)。
3.每位同學(xué)必須完成操作系統(tǒng)課程設(shè)計(jì)說明書并上交紙質(zhì)打印版（不少于3000字），設(shè)計(jì)說明書格式請(qǐng)從ftp下載《操作系統(tǒng)課程設(shè)計(jì)說明書（模板）》查看。（學(xué)習(xí)委員收齊后交到老師辦公室）。說明書電子版提交到老師的FTP
11計(jì)算機(jī)2班的同學(xué)： 交給韋婷老師
說明書電子版提交到：ftp://we:345678@10.5.1.請(qǐng)?zhí)峤坏皆揻tp的“/作業(yè)/操作系統(tǒng)課程設(shè)計(jì)/”文件夾中 每位同學(xué)的課程設(shè)計(jì)說明書按以下格式命名： “班內(nèi)序號(hào)-姓名.doc”
例如：05-李凱.doc
4.獨(dú)立完成，不得抄襲，凡是發(fā)現(xiàn)抄襲的（無論抄與被抄者），均不及格。5.課程設(shè)計(jì)上交截止日期： 11月12 日
6.設(shè)計(jì)提交后將抽取一部分同學(xué)進(jìn)行答辯，答辯時(shí)間另行通知。
注意：
1.Linux服務(wù)器遠(yuǎn)程連接方式：telnet 10.5.1.6（telnet連接服務(wù)器的過程可能需要十幾秒，屬正常現(xiàn)象，請(qǐng)耐心等待）2.登陸的用戶名和密碼 11計(jì)算機(jī)2班的同學(xué)：
用戶名：112班內(nèi)序號(hào)
例如: 11計(jì)算機(jī)2班的5號(hào)同學(xué)的用戶名是：11205
初始密碼：123456
3.在Linux環(huán)境編程，若要使用cin、cout，則必須用
#include
4.本課程設(shè)計(jì)所需資料從ftp://we:345678@10.5.1.5 “/下載/操作系統(tǒng)課程設(shè)計(jì)/” 文件夾中下載。
第三篇：操作系統(tǒng)課程設(shè)計(jì)題目及代碼
題目一
模擬操作系統(tǒng)設(shè)計(jì)
設(shè)計(jì)一個(gè)模擬操作系統(tǒng)管理程序，實(shí)現(xiàn)下列管理功能： 1．內(nèi)存管理功能 2．文件管理功能 3．磁盤管理功能
題目二
虛擬存儲(chǔ)器各頁面置換算法的實(shí)現(xiàn)與比較 內(nèi) 容：設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，通過產(chǎn)生一個(gè)隨機(jī)數(shù)的方法得到一個(gè)頁面序列，假設(shè)內(nèi)存給定的頁面數(shù)由鍵盤輸入，分別計(jì)算使用下述各方法時(shí)的內(nèi)存命中率：
先進(jìn)先出算法（FIFO）、最近最少使用算法（LRU）、最佳淘汰算法（OPT）、最少訪問頁面算法（LFU）等。
參考資料
題目二
資料
虛擬存儲(chǔ)器各頁面置換算法的實(shí)現(xiàn)與比較
1．實(shí)驗(yàn)?zāi)康?/p>
存儲(chǔ)管理的主要功能之一是合理的分配空間。請(qǐng)求頁式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。
本實(shí)驗(yàn)的目的是通過請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁式存儲(chǔ)管理的頁面置換算法。2．實(shí)驗(yàn)內(nèi)容
（1）通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。指令的地址按下述原則生成： 1）50%的指令是順序執(zhí)行的；
2）25%的指令是均勻分布在前地址部分； 3）25%的指令是均勻分布在后地址部分； 具體的實(shí)施方法是：
1）在[0，319]的指令地址之間隨機(jī)選取一起點(diǎn)m； 2）順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；
3）在前地址[0，m+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m'； 4）順序執(zhí)行一條指令，其地址為m'+1；
5）在后地址[m'+2,319]中隨機(jī)選取一條指令并執(zhí)行； 6）重復(fù)上述步驟1）-5），直到執(zhí)行320次指令。（2）將指令序列變換成為頁地址流 設(shè)：1）頁面大小為1k；
2）用戶內(nèi)存容量為4頁到32頁； 3）用戶虛存容量為32k； 在用戶虛存中，按每k存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為： 第0條-第9條指令為第0頁（對(duì)應(yīng)虛存地址為[0，9]）； 第10條-第19條指令為第1頁（對(duì)應(yīng)虛存地址為[10，19]）；
...第310條-第319條指令為第31頁（對(duì)應(yīng)虛存地址為[310，319]）；
按以上方式，用戶指令可組成為32頁。
（3）計(jì)算并輸出下列各種算法在不同內(nèi)存容量下的命中率。1）先進(jìn)先出的算法（FIFO）； 2）最近最少使用算法（LRR）;3）最佳淘汰算法(OPT)：先淘汰最不常用的頁地址； 4）最少訪問頁面算法（LF.U）； 5）最近最不經(jīng)常使用算法（NUR）。其中３）和４）為選擇內(nèi)容。命中率＝１－頁面失效次數(shù)／頁地址流長度
在本實(shí)驗(yàn)中，頁地址流長度為３２０，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁不在內(nèi)存的次數(shù)。３．隨機(jī)數(shù)產(chǎn)生辦法
關(guān)于隨機(jī)數(shù)產(chǎn)生辦法，Linux或Unix系統(tǒng)提供函數(shù)srand()和rand()，分別進(jìn)行初始化和產(chǎn)生隨機(jī)數(shù)。例如： srand()；
語句可初始化一個(gè)隨機(jī)數(shù)； a[0]=10*rand()/32767*319+1;a[1]=10*rand()/32767*a[0]；
..語句可用來產(chǎn)生a[0]與a[1]中的隨機(jī)數(shù)。
提示：
首先用Srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對(duì)不同的算法計(jì)算出相應(yīng)的命中率。
命中率=1-頁面失效次數(shù)/頁地址流長度
1、數(shù)據(jù)結(jié)構(gòu)
（1）頁面類型 typedef struct{
int pn,pfn,counter,time;}pl-type;
其中pn為頁號(hào)，pfn為頁面號(hào)，count為一個(gè)周期內(nèi)訪問該頁面的次數(shù)，time為訪問時(shí)間。
（2）頁面控制結(jié)構(gòu) pfc_struct{
int pn,pfn;
struct pfc_struct *next;
};typedef struct
pfc_struct pfc_type;pfc_type
pfc[total_vp],*freepf_head,*busypf_head;pfc_type *busypf_tail;其中，pfc[total_vp]定義用戶進(jìn)程虛頁控制結(jié)構(gòu)，*freepf_head為空頁面頭的指針，*busypf_head為忙頁面頭的指針，*busyf_tail為忙頁面尾的指針。
2、函數(shù)定義
（1）Void initialize()：初始化函數(shù)，給每個(gè)相關(guān)的頁面賦值。（2）Void FIFO()：計(jì)算使用FIFO算法時(shí)的命中率。（2）Void LRU（）：計(jì)算使用FIFO算法時(shí)的命中率。（4）VoidOPT（）：計(jì)算使用OPT算法時(shí)的命中率。（5）Void LFU（）：計(jì)算使用LFU算法時(shí)的命中率。（6）Void
NUR（）：計(jì)算使用NUR算法時(shí)的命中率。
3、變量定義
(1)int a[tatal_instruction] ：指令流數(shù)據(jù)組。
(2)int page[total_instruction]：每條指令所屬頁號(hào)。
(3)int offset[total_instruction]：每頁裝入不敷出0條指令后取模運(yùn)算頁號(hào)偏移量。(4)int total_pf：用戶進(jìn)程的內(nèi)存頁面數(shù)。(5)int diseffect：頁面失效次數(shù)。
程序清單
程序: 程序: #include “stdio.h” #include “process.h” #include “stdlib.h” #define TRUE 1 #define FALSE 0 #define INVALID-1 #define null 0 #define total_instruction 320 /*指令流長*/ #define total_vp 32 /*虛頁長*/ #define clear_period 50 /*清0周期*/ typedef struct { int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp];/*頁面數(shù)據(jù)結(jié)構(gòu)*/ struct pfc_struct{ /*頁面控制結(jié)構(gòu)*/ int pn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;int diseffect,a[total_instruction];int page[total_instruction],offset[total_instruction];void initialize();void FIFO();void LRU();void OPT();void LFU();void NUR();main(){ int S,i,j;srand(getpid()*10);/*由于每次運(yùn)行時(shí)進(jìn)程號(hào)不同，故可用來作為初始化隨機(jī)數(shù)隊(duì)
列的種子*/ S=(float)319*rand()/32767+1;for(i=0;i
busypf_head=busypf_tail=freepf_head;else {busypf_tail->next=freepf_head;busypf_tail=freepf_head;} freepf_head=p;} } printf(“FIFO:%6.4”,1-(float)diseffect/320);} void LRU(total_pf)/*LRU*/ int total_pf;{ int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i 1、操作系統(tǒng)實(shí)驗(yàn)教程 張麗芬編著 清華大學(xué)出版社 2、操作系統(tǒng)原理實(shí)驗(yàn)教程（基于Linux）胡峰松編 清華大學(xué)出版社 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) （操作系統(tǒng)課程設(shè)計(jì)） 連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存 管理模擬實(shí)現(xiàn) 學(xué)生姓名： 韓 慧 學(xué)生學(xué)號(hào)： 031140312 班 級(jí)： 031140--3 0311401、02、03、04班制 二〇一三年十二月 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 目錄 《操作系統(tǒng)》課程設(shè)計(jì).......................................................1 引言......................................................................3 課程設(shè)計(jì)目的和內(nèi)容......................................................3 需求分析.........................................................................3 概要設(shè)計(jì)...................................................................3 開發(fā)環(huán)境........................................................................4 系統(tǒng)分析設(shè)計(jì).....................................................................4 有關(guān)了解內(nèi)存管理的相關(guān)理論..................................................4 內(nèi)存管理概念........................................................................4 內(nèi)存管理的必要性..............................................................4 內(nèi)存的物理組織.............................................................4 什么是虛擬內(nèi)存.................................................................5 連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式...................................................5 單一連續(xù)分配（單個(gè)分區(qū))...................................................5 固定分區(qū)存儲(chǔ)管理...............................................................5 可變分區(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)）..............................................5 可重定位分區(qū)存儲(chǔ)管理........................................................5 問題描述和分析....................................................................6 程序流程圖........................................................................6 數(shù)據(jù)結(jié)構(gòu)體分析..................................................................8 主要程序代碼分析...............................................................9 分析并實(shí)現(xiàn)四種內(nèi)存分配算法.................................................11 最先適應(yīng)算.....................................................................11 下次適應(yīng)分配算法..........................................................13 最優(yōu)適應(yīng)算法...............................................................16 最壞適應(yīng)算法...............................................................18 回收內(nèi)存算法................................................................20 調(diào)試與操作說明.................................................................22 初始界面.......................................................................22 模擬內(nèi)存分配...............................................................23 已分配分區(qū)說明表面............................................................24 空閑區(qū)說明表界面.............................................................24 回收內(nèi)存界面.....................................................................25 重新申請(qǐng)內(nèi)存界面..........................................................26.總結(jié)與體會(huì)......................................................................28 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 參考文獻(xiàn).........................................................................28 引言 操作系統(tǒng)是最重要的系統(tǒng)軟件，同時(shí)也是最活躍的學(xué)科之一。我們通過操作系統(tǒng)可以理解計(jì)算機(jī)系統(tǒng)的資源如何組織，操作系統(tǒng)如何有效地管理這些系統(tǒng)資源，用戶如何通過操作系統(tǒng)與計(jì)算機(jī)系統(tǒng)打交道。 存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，近年來，存儲(chǔ)器容量雖然一直在不斷擴(kuò)大，但仍不能滿足現(xiàn)代軟件發(fā)展的需要，因此，存儲(chǔ)器仍然是一種寶貴而又緊俏的資源。如何對(duì)它加以有效的管理，不僅直接影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。而動(dòng)態(tài)分區(qū)分配屬于連續(xù)分配的一種方式，它至今仍在內(nèi)存分配方式中占有一席之地。 課程設(shè)計(jì)目的和內(nèi)容： 理解內(nèi)存管理的相關(guān)理論，掌握連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理的理論；通過對(duì)實(shí)際問題的編程實(shí)現(xiàn)，獲得實(shí)際應(yīng)用和編程能力。 編寫程序?qū)崿F(xiàn)連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式，該程序管理一塊虛擬內(nèi)存，實(shí)現(xiàn)內(nèi)存分配和回收功能。分析并實(shí)現(xiàn)四種內(nèi)存分配算法，即最先適應(yīng)算法，下次最先適應(yīng)算法，最優(yōu)適應(yīng)算法，最壞適應(yīng)算法。內(nèi)存分配算法和回收算法的實(shí)現(xiàn)。 需求分析 動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配和回收操作這樣三個(gè)問題。常用的數(shù)據(jù)結(jié)構(gòu)有動(dòng)態(tài)分區(qū)表和動(dòng)態(tài)分區(qū)鏈。在對(duì)數(shù)據(jù)結(jié)構(gòu)有一定掌握程度的情況下設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)來描述存儲(chǔ)空間，實(shí)現(xiàn)分區(qū)存儲(chǔ)管理的內(nèi)存分配功能，應(yīng)該選擇最合適的適應(yīng)算法（首次適應(yīng)算法，最佳適應(yīng)算法，最后適應(yīng)算法，最壞適應(yīng)算法），在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中主要實(shí)現(xiàn)內(nèi)存分配和內(nèi)存回收算法，在這些存儲(chǔ)管理中間必然會(huì)有碎片的產(chǎn)生，當(dāng)碎片產(chǎn)生時(shí)，進(jìn)行碎片的拼接等相關(guān)的內(nèi)容 概要設(shè)計(jì) 本程序采用機(jī)構(gòu)化模塊化的設(shè)計(jì)方法，共分為四大模塊。⑴最先適應(yīng)算法實(shí)現(xiàn) 從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。⑵下次適應(yīng)分配算法實(shí)現(xiàn) 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 該算法是最先適應(yīng)算法的變種。在分配內(nèi)存空間時(shí)，不再每次從表頭（鏈?zhǔn)祝╅_始查找，而是從上次找到空閑區(qū)的下一個(gè)空閑開始查找，直到找到第一個(gè)能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得較均勻。⑶最優(yōu)適應(yīng)算法實(shí)現(xiàn) 它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開始查找到第一個(gè)滿足要求的自由分區(qū)分配。⑷最壞算法實(shí)現(xiàn) 最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)或鏈表，總是挑選一個(gè)最大的空閑分區(qū)分割給作業(yè)使用。該算法要求將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。 開發(fā)環(huán)境： win7 下 VC++6.0 系統(tǒng)分析設(shè)計(jì)： 相關(guān)算法原理，算法流程圖，涉及的數(shù)據(jù)結(jié)構(gòu)內(nèi)容都相應(yīng)包含在各章節(jié)中 有關(guān)了解內(nèi)存管理的相關(guān)理論 內(nèi)存管理概念： 內(nèi)存管理，是指軟件運(yùn)行時(shí)對(duì)計(jì)算機(jī)內(nèi)存資源的分配和使用的技術(shù)。其最主要的目的是如何高效，快速的分配，并且在適當(dāng)?shù)臅r(shí)候釋放和回收內(nèi)存資源。內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時(shí)，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長度不固定分區(qū)個(gè)數(shù)不固定。這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問題，提高了主存資源的利用率。 內(nèi)存管理的必要性： 內(nèi)存管理對(duì)于編寫出高效率的 Windows 程序是非常重要的，這是因?yàn)閃indows 是多任務(wù)系統(tǒng)，它的內(nèi)存管理和單任務(wù)的 DOS 相比有很大的差異。DOS是單任務(wù)操作系統(tǒng)，應(yīng)用程序分配到內(nèi)存后，如果它不主動(dòng)釋放，系統(tǒng)是不會(huì)對(duì)它作任何改變的；但 Windows 卻不然，它在同一時(shí)刻可能有多個(gè)應(yīng)用程序共享內(nèi)存，有時(shí)為了使某個(gè)任務(wù)更好地執(zhí)行，Windows 系統(tǒng)可能會(huì)對(duì)其它任務(wù)分配的內(nèi)存進(jìn)行移動(dòng)，甚至刪除。因此，我們?cè)?Windows 應(yīng)用程序中使用內(nèi)存時(shí)，要遵循Windows 內(nèi)存管理的一些約定，以盡量提高 Windows 內(nèi)存的利用率。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 1.3 內(nèi)存的物理組織： 物理地址： 把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)存儲(chǔ)單元占 8 位，稱作字節(jié)（byte）。每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為物理地址（內(nèi)存地址、絕對(duì)地址、實(shí)地址）。 二、物理地址空間： 物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維空間。 什么是虛擬內(nèi)存： 虛擬內(nèi)存是內(nèi)存管理技術(shù)的一個(gè)極其實(shí)用的創(chuàng)新。它是一段程序（由操作系統(tǒng)調(diào)度），持續(xù)監(jiān)控著所有物理內(nèi)存中的代碼段、數(shù)據(jù)段，并保證他們?cè)谶\(yùn)行中的效率以及可靠性，對(duì)于每個(gè)用戶層（user-level）的進(jìn)程分配一段虛擬內(nèi)存空間。當(dāng)進(jìn)程建立時(shí)，不需要在物理內(nèi)存件之間搬移數(shù)據(jù)，數(shù)據(jù)儲(chǔ)存于磁盤內(nèi)的虛擬內(nèi)存空間，也不需要為該進(jìn)程去配置主內(nèi)存空間，只有當(dāng)該進(jìn)程被被調(diào)用的時(shí)候才會(huì)被加載到主內(nèi)存。 連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式的實(shí)現(xiàn) 在早期的操作系統(tǒng)中，主存分配廣泛采用連續(xù)分配方式。連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間，該連續(xù)內(nèi)存空間指的的是物理內(nèi)存。下面介紹連續(xù)分配的四種方式。 單一連續(xù)分配（單個(gè)分區(qū)） 最簡單的存儲(chǔ)管理方式，用于多道程序設(shè)計(jì)技術(shù)之前。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)使用。用戶區(qū)作為一個(gè)連續(xù)的分區(qū)分配給一個(gè)作業(yè)。分區(qū)存儲(chǔ)管理是滿足多道程序設(shè)計(jì)的最簡單的一種存儲(chǔ)管理方法，它允許多 4個(gè)用戶程序同時(shí)存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。按分區(qū)劃分方式可分為固定分區(qū)和可變分區(qū)。 固定分區(qū)存儲(chǔ)管理 把內(nèi)存的用戶區(qū)預(yù)先劃分成多個(gè)分區(qū)，每個(gè)分區(qū)大小可以相同，也可以不同。（分區(qū)的劃分由計(jì)算機(jī)的操作員或者由操作系統(tǒng)給出，并給出主存分配表）分區(qū)個(gè)數(shù)固定，分區(qū)的大小固定。一個(gè)分區(qū)中可裝入一個(gè)作業(yè)，作業(yè)執(zhí)行過程中不會(huì)改變存放區(qū)域。早期的 IBM 的 OS/MFT（具有固定任務(wù)數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。 可變分區(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)） 內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時(shí)，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待。分區(qū)長度不固定分區(qū)個(gè)數(shù)不固定。這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問題，提高了主存資源的利用率。ＩＢＭ操作系統(tǒng)ＯＳ／ＭＶＴ采用可變分區(qū)存儲(chǔ)管理。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 可重定位分區(qū)存儲(chǔ)管理 解決碎片問題的一種簡單方法是采用可重定位分區(qū)分配.。其中心思想是，把不同程序，且在內(nèi)存中地址不連續(xù)的想法讓他們連續(xù)。 例：內(nèi)存中現(xiàn)有 3 個(gè)空閑區(qū)，現(xiàn)有一作業(yè)到達(dá)，要求獲得 30k 內(nèi)存空間，沒有分區(qū)滿足容量要求，若想把作業(yè)裝入，可將內(nèi)存中所有作業(yè)進(jìn)行移動(dòng)，這樣把原來分散的空閑區(qū)匯集成一個(gè)大的空閑區(qū)。將內(nèi)存中的作業(yè)進(jìn)行移動(dòng)使它們連接在一起把原來分散的多個(gè)小分區(qū)拼接成一個(gè)大的空閑區(qū).這個(gè)過程稱為”緊湊”或”移動(dòng)”。需解決的問題:每次”緊湊”后程序或數(shù)據(jù)裝入的物理地址變化采用動(dòng)態(tài)重定位。 問題描述和分析 系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈表中找到所需大小的分區(qū)，如果空閑分區(qū)大小大于請(qǐng)求分區(qū)大小，則從該分區(qū)中按改請(qǐng)求的大小劃分出一塊內(nèi)存空間大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)用者。 當(dāng)進(jìn)程運(yùn)行完畢師范內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一： ⑴該空閑區(qū)的上下兩相鄰分區(qū)都是空閑區(qū)：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起始地址，大小為三個(gè)空閑區(qū)之和。空閑區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項(xiàng)或鏈指針，修改上空閑區(qū)的對(duì)應(yīng)項(xiàng)。 ⑵該空閑區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對(duì)應(yīng)的可用表的表目項(xiàng)或自由鏈指針。 ⑶該空閑區(qū)的下相鄰區(qū)是空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長度為釋放區(qū)與下空閑區(qū)之和。同理，合并后修改可用表或自由鏈中相應(yīng)的表目項(xiàng)或鏈指針。 ⑷兩相鄰區(qū)都不是空閑區(qū)：釋放區(qū)作為一個(gè)新空閑可用區(qū)插入可用表或自由鏈。 程序流程圖 內(nèi)存分配流程圖，如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 從頭開始查表檢索完否？NY返回分區(qū)大小>所需大小N繼續(xù)檢索下一個(gè)表項(xiàng)Y分區(qū)大小-所需大小<=不可再分割大小N從該分區(qū)中劃出所需大小的新分區(qū)Y將該分區(qū)從鏈中移出將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回 內(nèi)存回收流程圖，如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 開始判斷空閑區(qū)上下內(nèi)存情況上為空下為空上下都為空上下都不為空將上面的空閑區(qū)合并，并回收將下面的空閑區(qū)合并，并回收將上下的空閑區(qū)合并，并回收直接將其回收結(jié)束 數(shù)據(jù)結(jié)構(gòu)體分析 ⑴進(jìn)程屬性結(jié)構(gòu)體 typedef struct readyque { char name[10];int size;}readyque,*readyqueue;⑵空閑鏈表結(jié)構(gòu)體 typedef struct idlyspace { int from;int size;idlyspace * next;}idlyspace,*idly;⑶已分配鏈表結(jié)構(gòu)體 typedef struct busyspace { int from;readyque r;湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) busyspace * next;}busyspace,*busy 主要程序代碼分析 ⑴主函數(shù)//代碼請(qǐng)?zhí)砑舆m當(dāng)?shù)淖⑨尅nt 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.......................歡迎來到動(dòng)態(tài)分區(qū)存儲(chǔ)管理系統(tǒng)..................nn”);printf(“...........................請(qǐng)選擇要執(zhí)行的算法:...........................n”);printf(“.........................1.最先適應(yīng)算法 ...............................n”);printf(“.........................2.下次適應(yīng)算法............................n”);printf(“..........................3.最優(yōu)適應(yīng)算法 ...............................n”);printf(“.........................4.最壞適應(yīng)算法................................n”);printf(“........................................................................n”);printf(“請(qǐng)輸入您的選擇:”);scanf(“%d”,&t);int i;while(i!=5){ printf(“........................................................................n”); printf(“.........................操作菜單如下：（請(qǐng)選擇）.......................n”); printf(“..........................1.輸入進(jìn)程分配空間...........................n”); printf(“.........................2.進(jìn)程撤銷回收空間...........................n”); printf(“.........................3.輸出所有空閑分區(qū) ..........................n”); printf(“..........................4.輸出所有已分配分區(qū)..........................n”); printf(“..........................5.退 出..........................n”); printf(“........................................................................n”); scanf(“%d”,&i); switch(i) { case 1: switch(t) { case 1: t1=FF();湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) break; case 2: t1=NF(); break; case 3: t1=BF(); break; case 4: t1=WF(); break; default: printf(“選擇算法錯(cuò)誤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;} 第三章 ：分析并實(shí)現(xiàn)四種內(nèi)存分配算法 最先適應(yīng)算法 空閑區(qū)按地址從小到大的次序排列。 分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE 的內(nèi)存時(shí)，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為 SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)，但要修改其首址和大小。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 優(yōu)點(diǎn)：這種算法是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址 6部分的大空閑區(qū)，有利于大作業(yè)的裝入。 缺點(diǎn):主存低地址和高地址分區(qū)利用不均衡。在低地址部分集中了許多非常小的空閑區(qū)碎片降低了主存的利用率。最先適應(yīng)算法 int FF(){ int t=0;readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name); printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size); idly l=Is;int mt=256;busy b=Bs;idly min=NULL;while(l) //尋找空閑表中大小滿足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn) { 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ìn)程分配空間 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 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->from 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;} 下次適應(yīng)分配算法 最先適應(yīng)算法的變種。 總是從空閑區(qū)上次掃描結(jié)束處順序查找空閑區(qū)表（鏈），直到找到第一個(gè)滿足容量要求的空閑區(qū)為止，分割一部分給作業(yè)，剩余部分仍作為空閑區(qū)。下次適應(yīng)分配算法 int NF(){ int t=0;readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name); 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size); int mt=256;idly l=Is2;idly min=NULL;busy b=Bs;while(l)//尋找空閑表中大小滿足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn) { 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->from b=b->next;else break; //如果找到則為進(jìn)程分配空間 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) } //將申請(qǐng)空間進(jìn)程插入到已分配鏈表中 j->next=b->next; b->next=j; //修改相應(yīng)空閑節(jié)點(diǎn)的起址和大小 min->from=min->from+D.size; min->size=min->size-D.size; Is2=min->next; 結(jié)點(diǎn) 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指向修改結(jié)點(diǎn)的下一個(gè) //循環(huán)查找 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) j->r.name[i]=D.name[i]; } j->r.size=D.size; while(b->next) { if(b->next->from 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;} 最優(yōu)適應(yīng)算法 空閑區(qū)按容量遞增的次序排列。 分配：當(dāng)進(jìn)程申請(qǐng)存儲(chǔ)空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個(gè)滿足容量要求的空閑區(qū)為止。采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。優(yōu)點(diǎn)：選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。 缺點(diǎn)：空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來越多，從而造成存儲(chǔ)空間的浪費(fèi)。最優(yōu)適應(yīng)算法 int BF(){ int t=0;湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name); printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size); idly l=Is;idly min=NULL;int mt=256;busy b=Bs;while(l)//在空閑鏈中尋找第一個(gè)大于所輸入的進(jìn)程大小的空閑塊 { 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; //申請(qǐng)分配用于存放進(jìn)程的內(nèi)存 //找到第一個(gè)滿足要求的空閑塊 //將第一個(gè)滿足要求的空閑塊（min）的首地址賦給j for(int i=0;i<10;i++) { j->r.name[i]=D.name[i];16 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) } j->r.size=D.size; while(b->next) //按從小到大的順序查找新進(jìn)程在已分配區(qū)中的位置 { if(b->next->from 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;} 最壞適應(yīng)算法 為了克服最佳適應(yīng)算法把空閑區(qū)切割得太小的缺點(diǎn)，人們提出了一種最壞適應(yīng)算法，即每次分配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，剩余的部分仍是一個(gè)較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。要求空閑區(qū)按容量遞減的順序排列。 分配：進(jìn)程申請(qǐng)存儲(chǔ)區(qū)時(shí)，檢查空閑區(qū)表（鏈）的第一個(gè)空閑區(qū)的大小是否滿足要求，若不滿足則令進(jìn)程等待；若滿足則從該空閑區(qū)中分配一部分存儲(chǔ)區(qū)給用戶，剩下的部分仍作為空閑區(qū)。最壞適應(yīng)算法 int WF(){ int t=0;readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name); printf““輸入進(jìn)程申請(qǐng)空間大小:””); //將所輸入的進(jìn)程插入進(jìn)程鏈 //改變?cè)摽臻e塊的起始地址 //改變?cè)摽臻e塊的剩余大小 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) scanf““%””,&D.size); //輸入進(jìn)程申請(qǐng)的空間大小 idly l=Is;//l指向空閑鏈表ls頭 idly min=NULL;int mt=0;busy b=Bs; //b指向已分配鏈表Bs頭 //找到空閑分區(qū)中大小滿足進(jìn)程的請(qǐng)求且尺寸最大的結(jié)點(diǎn) while(l){ if(D.size<=l->size)//判斷進(jìn)程所申請(qǐng)的大小是否小于空閑區(qū)的各結(jié)點(diǎn)大小 { if(l->size>mt) { mt=l->size;min=l;//min指向空閑區(qū)中尺寸最大的結(jié)點(diǎn) t=1; } } l=l->next;} if(mt!=0)點(diǎn) { 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; //判斷是否找到了空閑區(qū)的滿足結(jié) //l指向空閑鏈表下一個(gè)結(jié)點(diǎn) 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) while(b->next)置 //尋找插入到已分配鏈表中的位 { if(b->next->from b=b->next;else break; } //把此進(jìn)程結(jié)點(diǎn)j插入到已分配鏈表中 j->next=b->next; b->next=j; //修改空閑鏈表的相應(yīng)結(jié)點(diǎn)的參數(shù) min->from=min->from+D.size; min->size=min->size-D.size;} return t;} 可變分區(qū)的回收 當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)去，否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑表的適當(dāng)位置。 釋放區(qū)與空閑區(qū)相鄰的四種情況。 （1）釋放區(qū)與前空閑區(qū)相鄰：把釋放區(qū)與前空閑區(qū)合并到一個(gè)空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。 （2）釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑區(qū)，其首地址為釋放區(qū)首地址，大小為二者之和。 （3）釋放區(qū)與前后兩空閑區(qū)相鄰：這三個(gè)區(qū)合為一個(gè)空閑區(qū)，首地址為前空閑區(qū)首址，大小為這三個(gè)空閑區(qū)之和，并取消后空閑區(qū)表目。 （4）釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當(dāng)位置。 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 回收內(nèi)存算法 int recover(){ readyque D;printf““請(qǐng)輸入想要回收的進(jìn)程名””); 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; } //如果在已分配鏈表中則釋放該結(jié)點(diǎn)所占空間 if(yo) { int t=b->next->from; int ts=b->next->r.size; //查找輸入的進(jìn)程名是否在已分配湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 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) //所回收進(jìn)程與空閑結(jié)點(diǎn)上鄰接 { //所回收進(jìn)程與空閑結(jié)點(diǎn)上下都不鄰接 //所回收進(jìn)程與空閑結(jié)點(diǎn)下鄰接 { //所回收進(jìn)程與空閑結(jié)點(diǎn)上下都 21 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 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; } //從已分配鏈表中釋放所回收進(jìn)程 busy tb=b->next; b->next=b->next->next; free(tb); return 1; } b=b->next;} printf(“沒找到這”進(jìn)程n”);return 0;} //所回收進(jìn)程與空閑結(jié)點(diǎn)上下都鄰調(diào)試與操作說明 初始界面 程序初始界面，有四個(gè)塊選擇，選擇要執(zhí)行的算法，調(diào)試以最壞算法為例，如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 選擇最壞適應(yīng)算法，如圖 模擬內(nèi)存分配 給進(jìn)程a分配內(nèi)存20，如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 已分配分區(qū)說明表界面 同理，給進(jìn)程b分配內(nèi)存30，給進(jìn)程c分配內(nèi)存40，給進(jìn)程d分配50，給進(jìn)程e分配60，如圖 空閑分區(qū)說明表界面 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 查看空閑分區(qū)，如圖 回收內(nèi)存界面 回收進(jìn)程b和d所占內(nèi)存，如圖 已分配分區(qū)說明表和空閑分區(qū)說明表 如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 重新申請(qǐng)內(nèi)存界面 再為新進(jìn)程i分配內(nèi)存30，如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 根據(jù)最壞適應(yīng)算法結(jié)合圖所示可知，該算法將會(huì)從空閑分區(qū)表中選擇一塊最大的內(nèi)存空間分配給進(jìn)程i，從圖也可看出該模擬算法實(shí)現(xiàn)了最壞適應(yīng)算法 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 總結(jié)與體會(huì) 本次做的課題是動(dòng)態(tài)分區(qū)分配算法實(shí)現(xiàn)，此次課程設(shè)計(jì)成功實(shí)現(xiàn)了內(nèi)存分配和內(nèi)存回收，內(nèi)存分配中包含了四種算法，分別是首次適應(yīng)算法，循環(huán)首次適應(yīng)算法，最佳適應(yīng)算法和最壞適應(yīng)算法。經(jīng)編碼調(diào)試，表明該程序模塊是有效可行的。 通過這門課程的學(xué)習(xí)讓我充分了解了內(nèi)存管理的機(jī)制實(shí)現(xiàn)，從而更深一步的的對(duì)計(jì)算機(jī) 有了很多了解，這對(duì)于以后我們的研究和學(xué)習(xí)計(jì)算機(jī)系統(tǒng)起到了很重要的作用。 對(duì)于本次論文制作，自己的編程能力有所提高，對(duì)操作系統(tǒng)內(nèi)存分配，存儲(chǔ)空間的回收都有全新的認(rèn)識(shí)。 在這次操作系統(tǒng)課程設(shè)計(jì)中，我使用了c++編寫系統(tǒng)軟件，對(duì)os中可變分區(qū)存儲(chǔ)管理有了深刻的理解，但是過程中遇到了很多困難，一邊做一邊學(xué)，對(duì)c++有了比較多的理解。 實(shí)驗(yàn)中遇到很多問題，浪費(fèi)了很多時(shí)間，總而言之是自己學(xué)習(xí)還不夠好，不扎實(shí)，希望在以后學(xué)習(xí)中加以改善，學(xué)到更多知識(shí)。 參考文獻(xiàn) 【1】 湯子瀛，哲鳳屏，湯小丹.計(jì)算機(jī)操作系統(tǒng).西安：西安電子科技大學(xué)出版社，2001.。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì) 【2】 任愛華.操作系統(tǒng)實(shí)用教程.北京：清華大學(xué)出版社，2001。 長春理工大學(xué) 軟件學(xué)院 0813111班 27號(hào) 姓名：丁為勝 一． 概述 1、課程設(shè)計(jì)目的及任務(wù)課程設(shè)計(jì)地點(diǎn)及要求 每個(gè)學(xué)生一臺(tái)微機(jī)，需要安裝windows98或windows2000操作系統(tǒng)，配備VC、VB、java或C編程語言，每個(gè)學(xué)生上機(jī)時(shí)間不少于24個(gè)小時(shí)。 操作系統(tǒng)是計(jì)算機(jī)專業(yè)的核心專業(yè)課，“操作系統(tǒng)課程設(shè)計(jì)”是理解和鞏固操作系統(tǒng)基本理論、原理和方法的重要的實(shí)踐環(huán)節(jié)。 操作系統(tǒng)課程主要講述的內(nèi)容是多道操作系統(tǒng)的原理與技術(shù)，與其它計(jì)算機(jī)原理、編譯原理、匯編語言、計(jì)算機(jī)網(wǎng)絡(luò)、程序設(shè)計(jì)等專業(yè)課程關(guān)系十分密切。本課程設(shè)計(jì)的目的綜合應(yīng)用學(xué)生所學(xué)知識(shí)，建立系統(tǒng)和完整的計(jì)算機(jī)系統(tǒng)概念，理解和鞏固操作系統(tǒng)基本理論、原理和方法，掌握操作系統(tǒng)基本理論與管理方式。在算法基礎(chǔ)上，解決實(shí)際的管理功能的問題，提高學(xué)生實(shí)際應(yīng)用、編程的能力。 主要任務(wù)是實(shí)現(xiàn)操作系統(tǒng)和相關(guān)系統(tǒng)軟件的設(shè)計(jì)，其中涉及進(jìn)程創(chuàng)建，同步，進(jìn)程間的通信，存儲(chǔ)管理，文件系統(tǒng)等操作系統(tǒng)概念。 2.課程設(shè)計(jì)地點(diǎn)及要求 每個(gè)學(xué)生一臺(tái)微機(jī)，需要安裝windows98或windows2000操作系統(tǒng)，配備VC、VB、java或C編程語言，每個(gè)學(xué)生上機(jī)時(shí)間不少于24個(gè)小時(shí)。 3.課程設(shè)計(jì)的內(nèi)容 設(shè)計(jì)二： 設(shè)計(jì)任務(wù)： 掌握進(jìn)程的管道通訊機(jī)制和信號(hào)量同步互斥機(jī)制。1． 進(jìn)程的管道通訊 編制一個(gè)程序，程序中創(chuàng)建一個(gè)子進(jìn)程。然后父子進(jìn)程各自獨(dú)立運(yùn)行，父進(jìn)程不斷地在標(biāo)準(zhǔn)輸入設(shè)備上讀入小寫字母，寫入管道。子進(jìn)程不斷地從管道中讀取字符，轉(zhuǎn)換為大寫字母后輸出到標(biāo)準(zhǔn)輸出設(shè)備上。當(dāng)讀到x時(shí)，結(jié)束。 2． 信號(hào)量實(shí)現(xiàn)的同步互斥機(jī)制 編制一個(gè)程序，程序中創(chuàng)建5個(gè)子進(jìn)程，代表五位哲學(xué)家，然后父進(jìn)程結(jié)束。使用信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題。當(dāng)哲學(xué)家進(jìn)餐時(shí)，屏幕輸出： [進(jìn)程號(hào)] eating!當(dāng)哲學(xué)家思考時(shí)，屏幕輸出： [進(jìn)程號(hào)] thinging!相關(guān)的系統(tǒng)調(diào)用和函數(shù)：pipe();write();read();semget();sepop();semctl();要求：查找并閱讀上述系統(tǒng)調(diào)用的相關(guān)資料，將上述相關(guān)的函數(shù)封裝為P()、V()操作，使用你封裝的P()、V()操作實(shí)現(xiàn)5位哲學(xué)家的同步和互斥。 二． 設(shè)計(jì)的基本概念和原理 1.進(jìn)程的管道通訊 管道（Pipe）實(shí)際是用于進(jìn)程間通信的一段共享內(nèi)存，創(chuàng)建管道的進(jìn)程稱為管道服務(wù)器，連接到一個(gè)管道的進(jìn)程為管道客戶機(jī)。命名管道（Named Pipes）是在管道服務(wù)器和一臺(tái)或多臺(tái)管道客戶機(jī)之間進(jìn)行單向或雙向通信的一種命名的管道。一個(gè)命名管道的所有實(shí)例共享同一個(gè)管道名，但是每一個(gè)實(shí)例均擁有獨(dú)立的緩存與句柄，并且為客戶——服務(wù)通信提供有一個(gè)分離的管道。實(shí)例的使用保證了多個(gè)管道客戶能夠在同一時(shí)間使用同一個(gè)命名管道。 2.信號(hào)量實(shí)現(xiàn)的同步互斥機(jī)制 規(guī)定奇數(shù)號(hào)的哲學(xué)家先拿起他左邊的筷子,然后再去拿他右邊的筷子;而偶數(shù)號(hào) 的哲學(xué)家則相反.按此規(guī)定,將是1,2號(hào)哲學(xué)家競爭1號(hào)筷子,3,4號(hào)哲學(xué)家競爭3號(hào)筷子.即 五個(gè)哲學(xué)家都競爭奇數(shù)號(hào)筷子,獲得后,再去競爭偶數(shù)號(hào)筷子,最后總會(huì)有一個(gè)哲學(xué)家能獲 得兩支筷子而進(jìn)餐。而申請(qǐng)不到的哲學(xué)家進(jìn)入阻塞等待隊(duì)列，根FIFO原則，則先申請(qǐng)的哲 學(xué)家會(huì)較先可以吃飯，因此不會(huì)出現(xiàn)餓死的哲學(xué)家。 三． 總體設(shè)計(jì) 1.實(shí)現(xiàn)的方法和主要技術(shù)路線 1.無名管道 無名管道用于具有親緣關(guān)系的父子進(jìn)程，子子進(jìn)程之間的通訊。它的實(shí)現(xiàn)函數(shù)有 int pipe(int fd[2]); //fd[2] 為描述符數(shù)組，包含一個(gè)讀描述符與一個(gè)寫描述符，在使用管道通信時(shí)，關(guān)閉某些不需要的讀或?qū)懨枋龇⑵饐蜗虻淖x或?qū)懝艿溃缓笥胷ead 和write 像操作文件一樣去操作它即可。 如圖便是進(jìn)程1 到進(jìn)程2 的一個(gè)讀管道。 分別在父進(jìn)程和父子進(jìn)程里向管道寫數(shù)據(jù)，然后在子進(jìn)程和子子進(jìn)程里讀數(shù)據(jù)。2.哲學(xué)家進(jìn)餐偽碼： semaphore chopstick[5]={1，1，1，1，1};void philosopher(int i){ while(true){ think(); if(i%2 == 0)//偶數(shù)哲學(xué)家，先右后左。 { wait(chopstick[ i + 1 ] mod 5);wait(chopstick[ i]);eat(); signal(chopstick[ i + 1 ] mod 5);signal(chopstick[ i]);} Else //奇數(shù)哲學(xué)家，先左后右。 { wait(chopstick[ i]); wait(chopstick[ i + 1 ] mod 5);eat(); signal(chopstick[ i]); signal(chopstick[ i + 1 ] mod 5);} } 四． 詳細(xì)設(shè)計(jì) 進(jìn)程的管道通信代碼： 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(“子進(jìn)程讀取的字符為：”+str.toUpperCase()); if(!str.endsWith(“x”)) { System.out.print(“父進(jìn)程讀入字符為：”); }else if(str.endsWith(“x”)) { System.out.println(“結(jié)束無法再次輸入字符”); } } } 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(“父進(jìn)程讀入字符為：”);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();} } 哲學(xué)家進(jìn)餐問題代碼： #include “stdafx.h” using namespace std;bool chop[100];//定義筷子 class ph { protected: bool * left,* right;//哲學(xué)家的左右手指向的筷子 int eattime;//哲學(xué)家的吃飯時(shí)間 public: bool check()//用于檢查哲學(xué)家左右手的筷子是不是被占用 { if(*left && *right) return true; else return false;} void eat(int ineattime)//哲學(xué)家開始進(jìn)餐 { eattime=ineattime; *left=false; *right=false;} bool finish()//檢查哲學(xué)家是否完成進(jìn)餐 { if(eattime>0)//沒完成的話剩余時(shí)間減少 { eattime--; if(eattime==0)//完成的話歸還筷子 { *left=true; *right=true; return true; } else return false; } else return false;} void init(int num,int max)//初始化哲學(xué)家，指定他們使用的筷子 { eattime=0; left=&chop[num]; if(num right=&chop[num+1]; else right=&chop[0];} };void main(){ system(“title 哲學(xué)家進(jìn)餐問題”);int in,i,temp,time,j=1;queue for(int i=0;i<5;i++){ chop[i]=1; } for(int i=0;i<5;i++){ P[i].init(i,5);} cout<<“輸入哲學(xué)家進(jìn)餐隊(duì)列：”< break;else if(in>5) { cout<<“一共只有”<<5<<“個(gè)人！”< } else { Q.push(in-1); } } cout<<“每個(gè)人吃飯時(shí)間：”< 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();}第四篇：操作系統(tǒng)課程設(shè)計(jì)
第五篇：操作系統(tǒng)課程設(shè)計(jì)
點(diǎn)擊咨詢 