C語言模擬操作系統(tǒng)運行課程設(shè)計

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

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

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

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

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

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

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

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

9、utime=0; p-needtime=time; p-count=0; /計數(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(); /輸出進程pcb信息 run=ready; /將就緒隊列的第一個進程投入運行 ready=ready-next; run-state=r;void roundrun()/時間片輪轉(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ōu)橥瓿蓱B(tài)，插入完成隊列 run-next=finish; finish=run; run-state=f; run=null; if(ready!=null) firstin(); /就緒對列不空，將第一個進程投入運行 else if(run-count=run-round) /如果時間片到 run-count=0; /計數(shù)器置0 if(ready!=null) /如就緒隊列不空 run-state=w; /將進程插

11、入到就緒隊列中等待輪轉(zhuǎn) insert2(run); firstin(); /將就緒對列的第一個進程投入運行 prt(); /輸出進程信息 4.時間片算法主要流程圖如下：開始創(chuàng)建pcb進程，輸入進程名及時間就緒隊列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;/計數(shù)器置0yready!=nullytail-next=run; tail=run;run-next=null; run-state=w; run=ready; run-state=r; ready=ready-next;輸出進程信息nn結(jié)束ready!=null5.時間片算法運行結(jié)果分析如下：4.用先來先服務(wù)算法完成進程的調(diào)度4.1設(shè)計要求：（1）進程的調(diào)度采用先來先服務(wù)算法。（2）設(shè)計三個鏈隊列，分別用來表示運行隊列、就緒隊列和完成隊列。（3）用戶輸入進程標識符以及進程所需的時間，申請空間存放進程pcb信

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

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

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

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

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

19、先適應(yīng)分配算法的分配策略分析內(nèi)存空間的使用情況，找出能滿足請求的空閑區(qū)，分給申請者，當(dāng)程序執(zhí)行完畢時，系統(tǒng)要收回它所占用的內(nèi)存空間。建立空閑數(shù)據(jù)文件，空閑區(qū)數(shù)據(jù)文件包括若干行，每行有兩個字段：起始地址、內(nèi)存塊大?。ň鶠檎麛?shù)），各字段以逗號隔開。下面是一個空閑區(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)存的起始地址和大小，用標志位指出該分區(qū)是否是未分配的空閑區(qū)。接收用戶的內(nèi)存申請，格式為：作業(yè)名、申請空間的大小。按照內(nèi)存分配算法中的一種方法選擇一個空閑區(qū)，分割并分

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

21、 char tag20; job; 3.算法的設(shè)計實現(xiàn)3.1設(shè)計實現(xiàn)：1.數(shù)據(jù)結(jié)構(gòu)及變量說明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() 實現(xiàn)最先適應(yīng)算法sortbest() 最佳適應(yīng)算法排序bestmethod() 實現(xiàn)最佳適應(yīng)算法sortbad() 最壞適應(yīng)算法排序badmethod() 實現(xiàn)最壞適應(yīng)算法finished() 實現(xiàn)主存回收view() 顯示3.2.最先適應(yīng)算法的功能及注釋/聲明變量char job_name20; int job_length; int i,j,flag,t; /輸入進程名和空間大小coutjob_name; cinjob_length; flag=0; /標志變量for(i=0;i=job_length)/空閑區(qū)長度是否大于進程所需空間 flag=1; if(flag=0) /空閑

23、區(qū)長度小于進程所需空間coutendlsorry,當(dāng)前沒有能滿足你申請長度的空閑內(nèi)存,請稍候再試=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)算法運行結(jié)果如下：3.3.最佳適應(yīng)算法的實現(xiàn)/聲明變量char job_name20; /名字 int job_length; /長度 int i,j; int max=0,min=0,maxx;/輸入進程名和空間大小 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)/ 沒有能滿足的空閑區(qū) coutendlsorry,當(dāng)前沒有能滿足你申請長度的空閑內(nèi)存,請稍候再試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)流程圖：最佳算法運行結(jié)果如下：3.4.最壞適應(yīng)算法的實現(xiàn)/聲明變量char job_name20; /名字 int job_length; /長度 int i,j; int max;/輸入進程名和空間大小 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、臂進程空間小，則不滿足要求 coutendlsorry,當(dāng)前沒有能滿足你申請長度的空閑內(nèi)存,請稍候再試job_length) freesmax.start+=job_length; freesmax.length-=job_length; else for(j=max;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-;最壞流程圖：最壞算法運行結(jié)果如下：3.5.主存回收算法的實現(xiàn)/聲明變量char job_name20; int i,j,flag,p=0; int start; int length; /輸入要回收的進程名coutjob_n

28、ame; flag=-1; /標志變量/找到指定進程for(i=0;ioccupy_quantity;i+) if(!strcmp(occupysi.tag,job_name) flag=i; start=occupysi.start; length=occupysi.length; if(flag=-1) cout沒有這個作業(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-;主存回收的流程圖如下：回收算法運行結(jié)果如下：四：模擬dos文件的建立和使用1 設(shè)計目的磁盤文件是磁盤上存儲的重要信息，通過本實驗?zāi)Mdos文件的建立和使用情況，理解磁盤文件的物理結(jié)構(gòu)。文件管理是操作系統(tǒng)中重要的內(nèi)容之一，不同的文件系統(tǒng)提供了不同的物理結(jié)構(gòu)，通過實驗，深入理解文件的物理結(jié)構(gòu)與存取方法之間的關(guān)系，以便更好的掌握文件系統(tǒng)的概念。2 設(shè)計要求（1） 模擬設(shè)計dos操作系統(tǒng)中磁盤文件

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

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

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

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

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

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

37、定索引步長if(fatj=0)fatlast=j;last=j;fatlast=fff;break;fatlast=fff;/文件末存結(jié)束標記remainingspace-=tmplength;/改變空閑塊個數(shù)filenumber+;printf(文件名和長度:%s %dn,tmpname,tmplength);寫入函數(shù)的主要流程圖如下：開始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(文件名和長度:%s %dn,tmpname,tmplength);結(jié)束n寫入函數(shù)運行結(jié)果如下：插入函數(shù)主要算法如下：void insert(char *tmpname,int insertpoint)int i;int last,brpoint;for(i=0;ifilenumber;i+)/

39、尋找要執(zhí)行插入操作的文件，將其數(shù)組下標存入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+)/尋找一個空閑塊插入if(fati=0)fati=fatbrpoint;fatbrpoint=i;break;filelast.filelength+;/改變空閑塊個數(shù)與

40、文件長度remainingspace-;printf(文件名和長度:%s %dn,tmpname,filelast.filelength);插入函數(shù)主要流程圖：開始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(文件名和長度:%s %dn,tmpname,filelast.filelength);結(jié)束nn插入的運行結(jié)果如下：（2）.模擬設(shè)計便于直接存取的索引文件結(jié)構(gòu)的主要算法功能及注釋如下： void search(char *tmpname) int i; for(i=0;ifilenumber;i+)if(strcmp(filei.filename,tmpname)=0)/比較插入文件名與已存在文件名是否相同 printf(找到了!n); printf(文件名 起始塊號 文件長度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(該點空缺,沒有文件!); 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è)計便于直接存取的索引文件結(jié)構(gòu)的主要流程圖如下：開始int i=0; int m;fatsearchpoint=0yprintf(該點空缺,沒有文件!);fatsearchpoint=1&fatsearchpoint-1=-2|fatsearchpoint=-2&fatsearchpoint+1=-1nyprintf(此處為系統(tǒng)空間!);nfatsearchpoint!=0yi=0i=0&mfilei.filelengthprintf(找到了!此處的文件名為:%s,filei.filename);break;