C語(yǔ)言模擬操作系統(tǒng)運(yùn)行課程設(shè)計(jì)

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告時(shí)間：2010-12-202010-12-31地點(diǎn)：信息技術(shù)實(shí)驗(yàn)中心計(jì)算機(jī) 專業(yè)2008級(jí)x班xx號(hào)xx2010-12-31目錄一 課程設(shè)計(jì)的目的和意義3二 進(jìn)程調(diào)度算法模擬41 設(shè)計(jì)目的42 設(shè)計(jì)要求43 時(shí)間片輪轉(zhuǎn)算法模擬44 先來(lái)先服務(wù)算法模擬9三 主存空間的回收與分配141 設(shè)計(jì)目的142 設(shè)計(jì)要求143 模擬算法的實(shí)現(xiàn)15四 模擬dos文件的建立和使用261 設(shè)計(jì)目的262 設(shè)計(jì)要求263 模擬算法的實(shí)現(xiàn)27五 磁盤(pán)調(diào)度381 設(shè)計(jì)目的382 設(shè)計(jì)要求383 模擬算法的實(shí)現(xiàn)38六 總結(jié)49一、課程設(shè)計(jì)的目的和意義本次操作系統(tǒng)課程設(shè)計(jì)的主要任務(wù)是進(jìn)行系統(tǒng)級(jí)的程序設(shè)計(jì)

2、。本課程設(shè)計(jì)是操作系統(tǒng)原理課程的延伸。通過(guò)該課程設(shè)計(jì)，使學(xué)生更好地掌握操作系統(tǒng)各部分結(jié)構(gòu)、實(shí)現(xiàn)機(jī)理和各種典型算法，加深對(duì)操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)思路的理解，培養(yǎng)學(xué)生的系統(tǒng)設(shè)計(jì)和動(dòng)手能力，學(xué)會(huì)分析和編寫(xiě)程序。課程設(shè)計(jì)的實(shí)施將使學(xué)生在以下幾個(gè)方面有所收獲：（1）加深對(duì)操作系統(tǒng)原理的理解，提高綜合運(yùn)用所學(xué)知識(shí)的能力；（2）培養(yǎng)學(xué)生自主查閱參考資料的習(xí)慣，增強(qiáng)獨(dú)立思考和解決問(wèn)題的能力；（3）通過(guò)課程設(shè)計(jì)，培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和協(xié)作精神。二：進(jìn)程調(diào)度算法模擬1 設(shè)計(jì)目的（1）要求學(xué)生設(shè)計(jì)并實(shí)現(xiàn)模擬進(jìn)程調(diào)度的算法：時(shí)間片輪轉(zhuǎn)及先來(lái)先服務(wù)。（2）理解進(jìn)程控制塊的結(jié)構(gòu)。（3）理解進(jìn)程運(yùn)行的并發(fā)性。（4）掌握進(jìn)程調(diào)度

3、算法。2 設(shè)計(jì)要求在多道程序運(yùn)行環(huán)境下，進(jìn)程數(shù)目一般多于處理機(jī)數(shù)目，使得進(jìn)程要通過(guò)競(jìng)爭(zhēng)來(lái)使用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之運(yùn)行，分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。一個(gè)進(jìn)程被創(chuàng)建后，系統(tǒng)為了便于對(duì)進(jìn)程進(jìn)行管理，將系統(tǒng)中的所有進(jìn)程按其狀態(tài)，將其組織成不同的進(jìn)程隊(duì)列。于是系統(tǒng)中有運(yùn)行進(jìn)程隊(duì)列、就緒隊(duì)列和各種事件的進(jìn)程等待隊(duì)列。進(jìn)程調(diào)度的功能就是從就緒隊(duì)列中挑選一個(gè)進(jìn)程到處理機(jī)上運(yùn)行。進(jìn)程調(diào)度的算法有多種，常用的有優(yōu)先級(jí)調(diào)度算法、先來(lái)先服務(wù)算法、時(shí)間片輪轉(zhuǎn)算法。進(jìn)程是程序在處理機(jī)上的執(zhí)行過(guò)程。進(jìn)程存在的標(biāo)識(shí)是進(jìn)程控制塊（pcb），進(jìn)程控制塊結(jié)構(gòu)如

4、下：typedef struct node char name10; /* 進(jìn)程標(biāo)識(shí)符 */ int prio; /* 進(jìn)程優(yōu)先數(shù) */ int round; /* 進(jìn)程時(shí)間輪轉(zhuǎn)時(shí)間片 */ int cputime; /* 進(jìn)程占用 cpu 時(shí)間*/ int needtime; /* 進(jìn)程到完成還需要的時(shí)間*/ int count; /* 計(jì)數(shù)器*/ char state; /* 進(jìn)程的狀態(tài)*/ struct node *next /*鏈指針*/ pcb; 系統(tǒng)創(chuàng)建一個(gè)進(jìn)程，就是由系統(tǒng)為某個(gè)程序設(shè)置一個(gè)pcb，用于對(duì)該進(jìn)程進(jìn)行控制和管理，進(jìn)程任務(wù)完成，由系統(tǒng)收回其pcb，該進(jìn)程便消亡。每個(gè)進(jìn)程

5、可以有三個(gè)狀態(tài)：運(yùn)行狀態(tài)、就緒狀態(tài)和完成狀態(tài)。用c語(yǔ)言、c+或者java語(yǔ)言編寫(xiě)一個(gè)程序?qū)崿F(xiàn)進(jìn)程調(diào)度的算法，模擬進(jìn)程調(diào)度的過(guò)程，加深對(duì)進(jìn)程控制塊概念和進(jìn)程調(diào)度算法的理解。本任務(wù)要求完成時(shí)間片輪轉(zhuǎn)及先來(lái)先服務(wù)兩個(gè)算法。3.時(shí)間片輪轉(zhuǎn)算法完成進(jìn)程的調(diào)度3.1設(shè)計(jì)要求：（1）進(jìn)程的調(diào)度采用時(shí)間片輪轉(zhuǎn)算法。（2）設(shè)計(jì)三個(gè)鏈隊(duì)列，分別用來(lái)表示運(yùn)行隊(duì)列、就緒隊(duì)列和完成隊(duì)列。（3）用戶輸入進(jìn)程標(biāo)識(shí)符以及進(jìn)程所需的時(shí)間，申請(qǐng)空間存放進(jìn)程 pcb信息。（4）輸出的格式和上面的運(yùn)行結(jié)果分析中的格式相同。時(shí)間片輪轉(zhuǎn)調(diào)度，具體做法是調(diào)度程序每次把 cpu 分配給就緒隊(duì)列首進(jìn)程使用一個(gè)時(shí)間片。當(dāng)這個(gè)時(shí)間片結(jié)束時(shí)，就強(qiáng)迫

6、一個(gè)進(jìn)程讓出處理器，讓它排列到就緒隊(duì)列的尾部，等候下一輪調(diào)度。實(shí)現(xiàn)這種調(diào)度要使用一個(gè)間隔時(shí)鐘。當(dāng)一個(gè)進(jìn)程開(kāi)始運(yùn)行時(shí)，就將時(shí)間片的值置入間隔時(shí)鐘內(nèi)，當(dāng)發(fā)生間隔時(shí)鐘中斷時(shí)，就表明該進(jìn)程連續(xù)運(yùn)行的時(shí)間已超過(guò)一個(gè)規(guī)定的時(shí)間片。此時(shí)，中斷處理程序就通知處理器調(diào)度進(jìn)行處理器的切換工作。3.2.時(shí)間片輪轉(zhuǎn)算法主要思想：在計(jì)算機(jī)中系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把cpu分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來(lái)停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后再把處理機(jī)分配給就緒隊(duì)列

7、中給定的時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。3.3算法的實(shí)現(xiàn)1.數(shù)據(jù)結(jié)構(gòu)及變量說(shuō)明 typedef struct pcb char name10; /進(jìn)程標(biāo)識(shí)符 int parrivetime; /到達(dá)時(shí)間 int pruntime; /估計(jì)運(yùn)行時(shí)間 int round; /進(jìn)程時(shí)間輪轉(zhuǎn)時(shí)間片 int cputime; /進(jìn)程占用cpu時(shí)間 int needtime; /進(jìn)程到完成還要的時(shí)間 int count; /計(jì)數(shù)器 char state; /進(jìn)程的狀態(tài) struct pcb *next; /鏈指針pcb;pcb *finish,*ready,*tail,*run; /隊(duì)列指針pcb

8、 head_input; int n; /進(jìn)程數(shù)2.完成功能的主要函數(shù)void roundrun()/時(shí)間片輪轉(zhuǎn)法函數(shù)3.時(shí)間片輪轉(zhuǎn)的主要算法功能及注釋：void insert2(pcb *p2)/輪轉(zhuǎn)法插入函數(shù) tail-next=p2; /將新的pcb插入在當(dāng)前就緒隊(duì)列的尾 tail=p2; p2-next=null;void create2()/輪轉(zhuǎn)法創(chuàng)建進(jìn)程pcb pcb *p; int i,time,n; char na10; ready=null; finish=null; run=null; printf(輸入進(jìn)程名及所需時(shí)間n); for(i=1;iname,na); p-cp

9、utime=0; p-needtime=time; p-count=0; /計(jì)數(shù)器 p-state=w; p-round=3; if(ready!=null) insert2(p); else p-next=ready; ready=p; tail=p; system(cls); printf( 輪轉(zhuǎn)法輸出n); printf(*n); prt(); /輸出進(jìn)程pcb信息 run=ready; /將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行 ready=ready-next; run-state=r;void roundrun()/時(shí)間片輪轉(zhuǎn)法 while(run!=null) run-cputime=ru

10、n-cputime+1; run-needtime=run-needtime-1; run-count=run-count+1; if(run-needtime=0)/運(yùn)行完將其變?yōu)橥瓿蓱B(tài)，插入完成隊(duì)列 run-next=finish; finish=run; run-state=f; run=null; if(ready!=null) firstin(); /就緒對(duì)列不空，將第一個(gè)進(jìn)程投入運(yùn)行 else if(run-count=run-round) /如果時(shí)間片到 run-count=0; /計(jì)數(shù)器置0 if(ready!=null) /如就緒隊(duì)列不空 run-state=w; /將進(jìn)程插

11、入到就緒隊(duì)列中等待輪轉(zhuǎn) insert2(run); firstin(); /將就緒對(duì)列的第一個(gè)進(jìn)程投入運(yùn)行 prt(); /輸出進(jìn)程信息 4.時(shí)間片算法主要流程圖如下：開(kāi)始創(chuàng)建pcb進(jìn)程，輸入進(jìn)程名及時(shí)間就緒隊(duì)列ready!nullyrun-cputime=run-cputime+1;run-needtime=run-needtime-1;run-count=run-count+1;run-needtime=0yrun-next=finish; finish=run;run-state=f; run=null;ready!=nullyrun=ready; run-state=r;ready=r

12、eady-next;run-count=run-roundnrun-count=0;/計(jì)數(shù)器置0yready!=nullytail-next=run; tail=run;run-next=null; run-state=w; run=ready; run-state=r; ready=ready-next;輸出進(jìn)程信息nn結(jié)束ready!=null5.時(shí)間片算法運(yùn)行結(jié)果分析如下：4.用先來(lái)先服務(wù)算法完成進(jìn)程的調(diào)度4.1設(shè)計(jì)要求：（1）進(jìn)程的調(diào)度采用先來(lái)先服務(wù)算法。（2）設(shè)計(jì)三個(gè)鏈隊(duì)列，分別用來(lái)表示運(yùn)行隊(duì)列、就緒隊(duì)列和完成隊(duì)列。（3）用戶輸入進(jìn)程標(biāo)識(shí)符以及進(jìn)程所需的時(shí)間，申請(qǐng)空間存放進(jìn)程pcb信

13、息。（4）輸出的格式和上面的運(yùn)行結(jié)果分析中的格式相同。先來(lái)先服務(wù)：按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)分配處理器。先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先被挑選，運(yùn)行進(jìn)程一旦占有處理器將一直運(yùn)行下去直到運(yùn)行結(jié)束或被阻塞，這是一種非剝奪式調(diào)度。4.2先來(lái)先服務(wù)調(diào)度算法主要思想：此算法既可用于作業(yè)調(diào)度，也歌詞用于進(jìn)程調(diào)度。當(dāng)作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源，創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用fcfs算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而

14、阻塞后才放棄處理機(jī)。4.3 算法的實(shí)現(xiàn)1.數(shù)據(jù)結(jié)構(gòu)及變量說(shuō)明 typedef struct pcb char name10; /進(jìn)程標(biāo)識(shí)符 int parrivetime; /到達(dá)時(shí)間 int pruntime; /估計(jì)運(yùn)行時(shí)間 int round; /進(jìn)程時(shí)間輪轉(zhuǎn)時(shí)間片 int cputime; /進(jìn)程占用cpu時(shí)間 int needtime; /進(jìn)程到完成還要的時(shí)間 int count; /計(jì)數(shù)器 char state; /進(jìn)程的狀態(tài) struct pcb *next; /鏈指針pcb;pcb *finish,*ready,*tail,*run; /隊(duì)列指針pcb head_input;

15、int n; /進(jìn)程數(shù)2.完成功能的主要函數(shù)void execprocesslist()/先來(lái)先服務(wù)函數(shù)3.先來(lái)先服務(wù)的主要算法功能及注釋：void execprocesslist() run=head_input.next; while(run!=null) run=head_input.next;/run指向?qū)︻^的下一個(gè)進(jìn)程 printf(開(kāi)始運(yùn)行 正在運(yùn)行 已經(jīng)運(yùn)行時(shí)間 剩余時(shí)間 等 待 中 的 進(jìn)程 已結(jié)束進(jìn)程n); for (int j=0;jpruntime)/1000;j+)/輸出每次運(yùn)行的統(tǒng)計(jì)信息 if (0=j) printf( %s n,run-name);/到達(dá)進(jìn)程開(kāi)始執(zhí)

16、行 printf( %s %d %d,run-name,j+1,(run-pruntime/1000)-(j+1); ready=run-next; /判斷此時(shí)還有哪些進(jìn)程在隊(duì)列里面 while (ready!=null) printf( %s ,ready-name); ready=ready-next; printf(n); run-state=c; /將進(jìn)城狀態(tài)設(shè)置為執(zhí)行完的狀態(tài) printf( %sn,run-name); ready=run;/將run指向下一個(gè)元素 run=run-next; head_input.next=run; delete ready;/將此進(jìn)程從進(jìn)程隊(duì)列里

17、面刪除 4.先來(lái)先服務(wù)算法主要流程圖如下：ready=run-next; printf( %s %d %d,run-name,j+1,(run-pruntime/1000)-(j+1);開(kāi)始run=head_input.next;run!=nullyrun=head_input.next; run-state=c; printf( %sn,run-name); ready=run; run=run-next; head_input.next=run; delete ready; j=0j=0?yprintf( %s n,run-name);ready!=nullprintf( %s ,read

18、y-name); ready=ready-next;結(jié)束5.先來(lái)先服務(wù)運(yùn)行結(jié)果如下：三：主存空間的回收與分配1 設(shè)計(jì)目的主存是中央處理器能直接存取指令和數(shù)據(jù)的存儲(chǔ)器，能否合理地利用主存，在很大程度上將影響到整個(gè)計(jì)算機(jī)系統(tǒng)的性能。主存分配是指在多道作業(yè)和多進(jìn)程環(huán)境下，如何共享主存空間。主存回收是指當(dāng)作業(yè)執(zhí)行完畢或進(jìn)程運(yùn)行結(jié)束后將主存空間歸還給系統(tǒng)。主存分配與回收的實(shí)現(xiàn)是與主存儲(chǔ)器的管理方式有關(guān)。本次設(shè)計(jì)主要是為了幫助學(xué)生深入理解主存空間的分配與回收的幾種算法。（1）掌握最先適應(yīng)分配算法（2）掌握最優(yōu)適應(yīng)分配算法（3）掌握最壞適應(yīng)分配算法2 設(shè)計(jì)要求用戶提出內(nèi)存空間請(qǐng)求，系統(tǒng)根據(jù)申請(qǐng)者要求，按照最

19、先適應(yīng)分配算法的分配策略分析內(nèi)存空間的使用情況，找出能滿足請(qǐng)求的空閑區(qū)，分給申請(qǐng)者，當(dāng)程序執(zhí)行完畢時(shí)，系統(tǒng)要收回它所占用的內(nèi)存空間。建立空閑數(shù)據(jù)文件，空閑區(qū)數(shù)據(jù)文件包括若干行，每行有兩個(gè)字段：起始地址、內(nèi)存塊大?。ň鶠檎麛?shù)），各字段以逗號(hào)隔開(kāi)。下面是一個(gè)空閑區(qū)數(shù)據(jù)文件的示例：0，10 10，08 18，10 28，06 34，10 44，09 讀取空閑區(qū)數(shù)據(jù)文件，建立空閑區(qū)表并在屏幕上顯示空閑內(nèi)存狀態(tài)，空閑區(qū)表記錄了可供分配的空閑內(nèi)存的起始地址和大小，用標(biāo)志位指出該分區(qū)是否是未分配的空閑區(qū)。接收用戶的內(nèi)存申請(qǐng)，格式為：作業(yè)名、申請(qǐng)空間的大小。按照內(nèi)存分配算法中的一種方法選擇一個(gè)空閑區(qū)，分割并分

20、配，修改空閑區(qū)表，填寫(xiě)內(nèi)存已分配區(qū)表（起始地址、長(zhǎng)度、標(biāo)志位），其中標(biāo)志位的一個(gè)作用是指出該區(qū)域分配給哪個(gè)作業(yè)。進(jìn)程結(jié)束后回收內(nèi)存。本次設(shè)計(jì)要求完成如下算法：（1）設(shè)計(jì)一個(gè)內(nèi)存分配回收的程序使用最先適應(yīng)分配算法（2）設(shè)計(jì)一個(gè)內(nèi)存分配回收的程序使用最優(yōu)適應(yīng)分配算法（3）設(shè)計(jì)一個(gè)內(nèi)存分配回收的程序使用最壞適應(yīng)分配算法用戶提出內(nèi)存空間請(qǐng)求，系統(tǒng)根據(jù)申請(qǐng)者要求，選擇上述算法的一種分配策略分析內(nèi)存空間的使用情況，找出合適的空閑區(qū)，分給申請(qǐng)者，當(dāng)進(jìn)程執(zhí)行完畢時(shí)，系統(tǒng)收回它所占用的內(nèi)存空間。創(chuàng)建空閑區(qū)表：空閑區(qū)表的結(jié)構(gòu)如下：typedef struct node int start; int length;

21、 char tag20; job; 3.算法的設(shè)計(jì)實(shí)現(xiàn)3.1設(shè)計(jì)實(shí)現(xiàn)：1.數(shù)據(jù)結(jié)構(gòu)及變量說(shuō)明const int maxjob=100;/定義表最大記錄數(shù) typedef struct node int start; int length; char tag20; job; job freesmaxjob;/定義空閑區(qū)表 int free_quantity; job occupysmaxjob;/定義已分配區(qū)表 int occupy_quantity;2.完成功能的主要函數(shù)initial() 初始化readdata() 從文本文件讀取數(shù)據(jù)sortearliest() 最先適應(yīng)算法排序earlie

22、st() 實(shí)現(xiàn)最先適應(yīng)算法sortbest() 最佳適應(yīng)算法排序bestmethod() 實(shí)現(xiàn)最佳適應(yīng)算法sortbad() 最壞適應(yīng)算法排序badmethod() 實(shí)現(xiàn)最壞適應(yīng)算法finished() 實(shí)現(xiàn)主存回收view() 顯示3.2.最先適應(yīng)算法的功能及注釋/聲明變量char job_name20; int job_length; int i,j,flag,t; /輸入進(jìn)程名和空間大小coutjob_name; cinjob_length; flag=0; /標(biāo)志變量for(i=0;i=job_length)/空閑區(qū)長(zhǎng)度是否大于進(jìn)程所需空間 flag=1; if(flag=0) /空閑

23、區(qū)長(zhǎng)度小于進(jìn)程所需空間coutendlsorry,當(dāng)前沒(méi)有能滿足你申請(qǐng)長(zhǎng)度的空閑內(nèi)存,請(qǐng)稍候再試=job_length) t=1; i+; i-; occupysoccupy_quantity.start=freesi.start; strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length; occupy_quantity+; if(freesi.lengthjob_length) freesi.start+=job_length; freesi.length-=job_lengt

24、h; else for(j=i;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-;最先適應(yīng)算法的主要流程圖如下：最先適應(yīng)算法運(yùn)行結(jié)果如下：3.3.最佳適應(yīng)算法的實(shí)現(xiàn)/聲明變量char job_name20; /名字 int job_length; /長(zhǎng)度 int i,j; int max=0,min=0,maxx;/輸入進(jìn)程名和空間大小 coutjob_name; cinjob_length;/查找最合適的空閑區(qū) for(i=0;ifree_quantity;i+) for(j=0;ji;j+) if(freesj.length=free

25、si.length) max=i;elsemax=j; for(j=0;j=freesi.length) min=i;elsemin=j; if(freesmin.length=job_length) maxx=i; if(freesmaxx.lengthjob_length)/ 沒(méi)有能滿足的空閑區(qū) coutendlsorry,當(dāng)前沒(méi)有能滿足你申請(qǐng)長(zhǎng)度的空閑內(nèi)存,請(qǐng)稍候再試job_length) freesmaxx.start+=job_length; freesmaxx.length-=job_length; else for(j=maxx;jfree_quantity-1;j+) free

26、sj=freesj+1;free_quantity-;最優(yōu)流程圖：最佳算法運(yùn)行結(jié)果如下：3.4.最壞適應(yīng)算法的實(shí)現(xiàn)/聲明變量char job_name20; /名字 int job_length; /長(zhǎng)度 int i,j; int max;/輸入進(jìn)程名和空間大小 coutjob_name; cinjob_length;/找出空閑區(qū)最大的 for(i=0;ifree_quantity;i+) for(j=0;ji;j+) if(freesj.lengthfreesi.length) max=i; else max=j; if(freesmax.lengthjob_length)/如果最大空閑區(qū)都

27、臂進(jìn)程空間小，則不滿足要求 coutendlsorry,當(dāng)前沒(méi)有能滿足你申請(qǐng)長(zhǎng)度的空閑內(nèi)存,請(qǐng)稍候再試job_length) freesmax.start+=job_length; freesmax.length-=job_length; else for(j=max;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-;最壞流程圖：最壞算法運(yùn)行結(jié)果如下：3.5.主存回收算法的實(shí)現(xiàn)/聲明變量char job_name20; int i,j,flag,p=0; int start; int length; /輸入要回收的進(jìn)程名coutjob_n

28、ame; flag=-1; /標(biāo)志變量/找到指定進(jìn)程for(i=0;ioccupy_quantity;i+) if(!strcmp(occupysi.tag,job_name) flag=i; start=occupysi.start; length=occupysi.length; if(flag=-1) cout沒(méi)有這個(gè)作業(yè)名endl; else /加入空閑表 for(i=0;ifree_quantity;i+) if(freesi.start+freesi.length)=start) if(i+1)free_quantity)&(freesi+1.start=start+length)

29、 freesi.length=freesi.length+freesi+1.length+length; for(j=i+1;jfree_quantity;j+) freesj=freesj+1; free_quantity-; p=1; else freesi.length+=length; p=1; if(freesi.start=(start+length) freesi.start=start; freesi.length+=length; p=1; if(p=0) freesfree_quantity.start=start; freesfree_quantity.length=le

30、ngth; free_quantity+; /刪除分配表中的該作業(yè) for(i=flag;ioccupy_quantity;i+) occupysi=occupysi+1; occupy_quantity-;主存回收的流程圖如下：回收算法運(yùn)行結(jié)果如下：四：模擬dos文件的建立和使用1 設(shè)計(jì)目的磁盤(pán)文件是磁盤(pán)上存儲(chǔ)的重要信息，通過(guò)本實(shí)驗(yàn)?zāi)Mdos文件的建立和使用情況，理解磁盤(pán)文件的物理結(jié)構(gòu)。文件管理是操作系統(tǒng)中重要的內(nèi)容之一，不同的文件系統(tǒng)提供了不同的物理結(jié)構(gòu)，通過(guò)實(shí)驗(yàn)，深入理解文件的物理結(jié)構(gòu)與存取方法之間的關(guān)系，以便更好的掌握文件系統(tǒng)的概念。2 設(shè)計(jì)要求（1） 模擬設(shè)計(jì)dos操作系統(tǒng)中磁盤(pán)文件

31、的存儲(chǔ)結(jié)構(gòu)dos操作系統(tǒng)對(duì)磁盤(pán)文件的管理采用鏈接結(jié)構(gòu)，將所有的鏈接指針集中在一起，存放在文件分配表（fat）中。連接文件的第一個(gè)物理塊號(hào)登記在文件目錄中。其設(shè)計(jì)思想是：假定磁盤(pán)上共有n個(gè)物理塊可供使用，當(dāng)要存放文件時(shí)，從fat表中尋找其值為0的項(xiàng)，用其對(duì)應(yīng)的物理塊存放文件信息，并把文件占有的各物理塊用鏈接指針登記在fat表中，再把文件的第一個(gè)物理塊號(hào)登記在文件目錄中。文件目錄及fat表如圖所示: 在dos中fat表的前兩項(xiàng)用來(lái)記錄磁盤(pán)的類型。而從第2項(xiàng)開(kāi)始記錄磁盤(pán)的分配情況和文件各物理塊的鏈接情況。在fat表中第三項(xiàng)的值如果為0，表示對(duì)應(yīng)的第三塊空閑。由圖還知道文件a的各記錄依次存放在第2、第

32、4、第15、第16、第50等六個(gè)物理塊中。第50塊中的指針為fff，表示文件a的結(jié)束。文件b的各記錄依次存放在第7、第10、第20等三個(gè)物理塊中。第20塊中的指針為fff。假定磁盤(pán)存儲(chǔ)空間共有100個(gè)物理塊，設(shè)計(jì)一個(gè)文件分配表。為了簡(jiǎn)單，文件分配表可用一個(gè)數(shù)組定義，其中每一個(gè)元素與一個(gè)物理塊對(duì)應(yīng)。當(dāng)?shù)?i 個(gè)元素為 0 時(shí)，表示第 i 塊空閑；當(dāng)?shù)?i 個(gè)元素既不為 0 也不為 fff 時(shí)，其值表示該文件的下一個(gè)物理塊號(hào)。另外，再設(shè)一個(gè)空閑塊總數(shù)變量記錄系統(tǒng)還有的空閑塊數(shù)。為了簡(jiǎn)單，假定一個(gè)物理塊指存放一個(gè)邏輯記錄，要求設(shè)計(jì)一個(gè)程序，把文件的邏輯記錄結(jié)構(gòu)轉(zhuǎn)換成 dos 的鏈接結(jié)構(gòu)。當(dāng)用戶要求將

33、已在主存的文件保存在磁盤(pán)上時(shí)，給出文件名及文件的記錄個(gè)數(shù)，系統(tǒng)應(yīng)能在磁盤(pán)上正確地保存文件?；虍?dāng)用戶要求給指定文件增加記錄時(shí)，也應(yīng)正確的實(shí)現(xiàn)，并插在指定記錄之后。為了正確地執(zhí)行模擬程序，可用鍵盤(pán)模擬輸入用戶的要求。輸入格式為：write(文件名，記錄個(gè)數(shù)) 或insert(文件名，邏輯記錄號(hào)) （2） 模擬設(shè)計(jì)便于直接存取的索引文件結(jié)構(gòu)為了便于用戶直接存取文件的各個(gè)邏輯記錄，在 ms-dos 中通過(guò)文件目錄，再沿著鏈查找fat表，便可直接找到指定邏輯記錄對(duì)應(yīng)的物理塊。在小型機(jī)或更高級(jí)的文件系統(tǒng)中，直接存取文件的方法是為每個(gè)文件建立一個(gè)索引表，指出各邏輯記錄與物理塊的對(duì)應(yīng)關(guān)系。最簡(jiǎn)單的形式是一個(gè)邏

34、輯記錄對(duì)應(yīng)一個(gè)物理塊。文件目錄與索引表的關(guān)系如圖所示。通常索引表按照邏輯記錄順序建立，這樣既有利于順序存儲(chǔ)，又有利于直接存儲(chǔ)。為了標(biāo)識(shí)哪些記錄已經(jīng)建立，哪些記錄還沒(méi)建立，故在索引表中增設(shè)一個(gè)標(biāo)志位。寫(xiě)文件或插入一個(gè)記錄的過(guò)程是尋找一個(gè)空閑物理塊，然后將其填入索引表對(duì)應(yīng)項(xiàng)中。其建立過(guò)程同第一題，即 write（文件名，記錄號(hào)）和 insert（文件名，記錄號(hào)）。要求用位示圖描繪出磁盤(pán)的使用情況，并要求模擬程序執(zhí)行過(guò)程的每一步都能顯示文件目錄、位示圖、索引表。3模擬算法的實(shí)現(xiàn):1.數(shù)據(jù)結(jié)構(gòu)及變量名：const int fdf=-2;const int fff=-1;const int n=100;

35、/存儲(chǔ)空間(fat表長(zhǎng)度)int filenumber;/文件數(shù)量struct fileinfochar filename10;int startaddress;int filelength;2.實(shí)現(xiàn)功能的主要函數(shù)void printfmenu()/打印目錄表void printffat()/打印fat表void search2()/搜索文件void write(char *tmpname,int tmplength)/寫(xiě)入文件void insert(char *tmpname,int insertpoint)/插入文件（1）.模擬設(shè)計(jì)dos操作系統(tǒng)中磁盤(pán)文件的存儲(chǔ)結(jié)構(gòu)的主要算法功能及注釋如下

36、：寫(xiě)入函數(shù)算法：void write(char *tmpname,int tmplength)int last,i,j;strcpy(filefilenumber.filename,tmpname);/復(fù)制文件名和文件塊個(gè)數(shù)filefilenumber.filelength=tmplength;for(i=2;in;i+)/存文件if(fati=0) filefilenumber.startaddress=i;/首個(gè)空閑塊為文件開(kāi)始?jí)Klast=i;fatlast=fff;break;for(i=1;itmplength;i+)/last為上個(gè)記錄的位置for(j=2;jn;j+)/步進(jìn)，用來(lái)確

37、定索引步長(zhǎng)if(fatj=0)fatlast=j;last=j;fatlast=fff;break;fatlast=fff;/文件末存結(jié)束標(biāo)記remainingspace-=tmplength;/改變空閑塊個(gè)數(shù)filenumber+;printf(文件名和長(zhǎng)度:%s %dn,tmpname,tmplength);寫(xiě)入函數(shù)的主要流程圖如下：開(kāi)始intlast,i,j;strcpy(filefilenumber.filename,tmpname);filefilenumber.filelength=tmplength;i=2inyfati=0yfilefilenumber.startaddress

38、=i;last=i;fatlast=fff;break;i+i=1itmplengthyj=2jnyfatlast=j;last=j;fatlast=fff;break;fatj=0yj+i+fatlast=fff;remainingspace-=tmplength;filenumber+;printf(文件名和長(zhǎng)度:%s %dn,tmpname,tmplength);結(jié)束n寫(xiě)入函數(shù)運(yùn)行結(jié)果如下：插入函數(shù)主要算法如下：void insert(char *tmpname,int insertpoint)int i;int last,brpoint;for(i=0;ifilenumber;i+)/

39、尋找要執(zhí)行插入操作的文件，將其數(shù)組下標(biāo)存入lastif(strcmp(filei.filename,tmpname)=0)/比較插入文件名與已存在文件名是否相同 last=i;break;brpoint=filelast.startaddress;/brpoint記錄當(dāng)前文件掃描到的位置for(i=0;iinsertpoint-1;i+)brpoint=fatbrpoint; /掃描直到找到插入位置for(i=0;in;i+)/尋找一個(gè)空閑塊插入if(fati=0)fati=fatbrpoint;fatbrpoint=i;break;filelast.filelength+;/改變空閑塊個(gè)數(shù)與

40、文件長(zhǎng)度remainingspace-;printf(文件名和長(zhǎng)度:%s %dn,tmpname,filelast.filelength);插入函數(shù)主要流程圖：開(kāi)始int i;int last,brpoint;i=0ifilenumberystrcmp(filei.filename,tmpname)=0ylast=i;break;i+brpoint=filelast.startaddress;i=0iinsertpoint-1brpoint=fatbrpoint;yi+i=0inyfati=0fati=fatbrpoint;fatbrpoint=i;break;yi+filelast.file

41、length+;remainingspace-;printf(文件名和長(zhǎng)度:%s %dn,tmpname,filelast.filelength);結(jié)束nn插入的運(yùn)行結(jié)果如下：（2）.模擬設(shè)計(jì)便于直接存取的索引文件結(jié)構(gòu)的主要算法功能及注釋如下： void search(char *tmpname) int i; for(i=0;ifilenumber;i+)if(strcmp(filei.filename,tmpname)=0)/比較插入文件名與已存在文件名是否相同 printf(找到了!n); printf(文件名 起始?jí)K號(hào) 文件長(zhǎng)度n); printf( %s %d %dn,filei.f

42、ilename,filei.startaddress,filei.filelength); void search2(int searchpoint) int i=0; int m; if(fatsearchpoint=0) printf(該點(diǎn)空缺,沒(méi)有文件!); else if(fatsearchpoint=-1&fatsearchpoint-1=-2|fatsearchpoint=-2&fatsearchpoint+1=-1)printf(此處為系統(tǒng)空間!);else if(fatsearchpoint!=0) for(i=0;i=0&mfilei.filelength)printf(找到了!此處的文件名為:%s,filei.filename);break;1.模擬設(shè)計(jì)便于直接存取的索引文件結(jié)構(gòu)的主要流程圖如下：開(kāi)始int i=0; int m;fatsearchpoint=0yprintf(該點(diǎn)空缺,沒(méi)有文件!);fatsearchpoint=1&fatsearchpoint-1=-2|fatsearchpoint=-2&fatsearchpoint+1=-1nyprintf(此處為系統(tǒng)空間!);nfatsearchpoint!=0yi=0i=0&mfilei.filelengthprintf(找到了!此處的文件名為:%s,filei.filename);brea