操作系統(tǒng)試驗(yàn)指導(dǎo)書

操作系統(tǒng)試驗(yàn)指導(dǎo)書李玲娟李剛 李玲娟 審核南京中醫(yī)藥大學(xué)信息技術(shù)學(xué)院202310月編者說明軟件技術(shù)是《操作系統(tǒng)》最重要的計(jì)算機(jī)系統(tǒng)軟件，同時(shí)也是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)根底課，其進(jìn)展極為快速。學(xué)習(xí)計(jì)算機(jī)軟件技術(shù)，特別是計(jì)算機(jī)操作系統(tǒng)技術(shù)，除了需要刻苦努力外，還需要把握軟件和操作系統(tǒng)的原理與設(shè)計(jì)技巧。這些原理與技巧可以說是計(jì)算機(jī)界的前輩們一代接一代不停留的努力所留下的學(xué)問與才智的結(jié)晶，學(xué)習(xí)和把握它們對于激發(fā)自己的制造力和想象力是很有幫助的。如何學(xué)習(xí)和把握操作系統(tǒng)技術(shù)的原理與實(shí)際技巧呢？除了聽課和讀書之外，最好的方法就是在實(shí)踐中練習(xí)，通過自己模擬設(shè)計(jì)操作系統(tǒng)的原理試驗(yàn)，可以培育程序設(shè)計(jì)的方法和技巧，提高編制和理解清楚、合理、可讀性好的系統(tǒng)程序的力量，加深對操作系統(tǒng)課程的理解。使自身更好的把握操作系統(tǒng)的根本概念、根本原理及根本功能，從而具有分析實(shí)際操作系統(tǒng)的根本力量，深入直觀的理解操作系統(tǒng)使用的各類算法。《操作系統(tǒng)試驗(yàn)指導(dǎo)書》是針對這門課的試驗(yàn)編寫的，書中設(shè)計(jì)了四個(gè)重要的操作系統(tǒng)原(進(jìn)程調(diào)度)和試驗(yàn)二(分區(qū)式存儲(chǔ)治理)(虛擬存儲(chǔ)治理)和試驗(yàn)四(文件治理)教材中的理論原理。全部試驗(yàn)共18學(xué)時(shí)，均承受C語言作為編程語言模擬設(shè)計(jì)完成相關(guān)程序。本書編寫中，參考了西安電子科技大學(xué)、清華大學(xué)的操作系統(tǒng)相關(guān)圖書資料。本書由信息技術(shù)學(xué)院副院長李玲娟和應(yīng)用教研室李剛兩位教師編寫南京中醫(yī)藥大學(xué)教務(wù)處賜予了指導(dǎo)和大力幫助，在此表示誠意的感謝！限于編者的水平，難免有疏漏與錯(cuò)誤，敬請讀者批判指正。李玲娟 李剛20231012日目 錄TOC\o“1-1“\h\z\u\l“_TOC_250003“試驗(yàn)一進(jìn)程調(diào)度 1\l“_TOC_250002“試驗(yàn)二分區(qū)式存儲(chǔ)治理 4\l“_TOC_250001“試驗(yàn)三虛擬存儲(chǔ)治理 8\l“_TOC_250000“試驗(yàn)四文件治理 11南京中醫(yī)藥大學(xué)信息技術(shù)學(xué)院操作系統(tǒng)試驗(yàn)?zāi)暇┲嗅t(yī)藥大學(xué)信息技術(shù)學(xué)院操作系統(tǒng)試驗(yàn)10試驗(yàn)一進(jìn)程調(diào)度試驗(yàn)性質(zhì)：設(shè)計(jì)建議學(xué)時(shí)：6學(xué)時(shí)試驗(yàn)?zāi)康模和ㄟ^這次試驗(yàn)，加深對進(jìn)程概念的理解，進(jìn)一步把握進(jìn)程狀態(tài)的轉(zhuǎn)變、進(jìn)程調(diào)度的策略及對系統(tǒng)性能的評(píng)價(jià)方法。預(yù)習(xí)內(nèi)容：閱讀教材《計(jì)算機(jī)操作系統(tǒng)》其次章和第三章，把握進(jìn)程治理及調(diào)度相關(guān)概念和原理。根本試驗(yàn)內(nèi)容：設(shè)計(jì)程序模擬進(jìn)程的輪轉(zhuǎn)法調(diào)度過程。假設(shè)初始狀態(tài)為：有n個(gè)進(jìn)程處于就緒狀態(tài)，有m(程不會(huì)堵塞)，且每過t個(gè)時(shí)間片系統(tǒng)釋放資源，喚醒處于堵塞隊(duì)列隊(duì)首的進(jìn)程。程序要求如下：1〕.輸出系統(tǒng)中進(jìn)程的調(diào)度次序；2〕.計(jì)算CPU利用率。實(shí)現(xiàn)提示：C語言實(shí)現(xiàn)提示：程序中進(jìn)程可用PCB表示，其類型描述如下：struct PCB_type{char name //進(jìn)程名int state //進(jìn)程狀態(tài)2——表示“執(zhí)行”狀態(tài)1——表示“就緒”狀態(tài)0——表示“堵塞”狀態(tài)int cpu_time //運(yùn)行需要的CPU時(shí)間〔需運(yùn)行的時(shí)間片個(gè)數(shù)〕}設(shè)置兩個(gè)隊(duì)列，將處于“就緒”狀態(tài)的進(jìn)程PCB掛在隊(duì)列ready中；將處于“堵塞”狀態(tài)的進(jìn)程PCB掛在隊(duì)列blocked中。隊(duì)列類型描述如下：struct QueueNode{struct PCB_type PCB;Struct QueueNode *next;}并設(shè)全程量：structQueueNode*ready_head=NULL,//ready隊(duì)列隊(duì)首指針*ready_tail=NULL,*blocked_head=NULL,//ready隊(duì)列隊(duì)尾指針//blocked隊(duì)列隊(duì)首指針*blocked_tail=NULL; //blocked隊(duì)列隊(duì)尾指針設(shè)計(jì)子程序：start_state; //讀入假設(shè)的數(shù)據(jù)，設(shè)置系統(tǒng)初始狀態(tài)dispath; //模擬調(diào)度calculate; //計(jì)算CPU利用率試驗(yàn)要求：上機(jī)前認(rèn)真使用C語言編寫好程序，承受TurboC作為編譯環(huán)境；上機(jī)時(shí)獨(dú)立調(diào)試程序依據(jù)具體試驗(yàn)要求，填寫好試驗(yàn)報(bào)告〔包括思想、源程序、實(shí)例運(yùn)行結(jié)果。測試用數(shù)據(jù)：n=2m=3t=5ready_headblocked_headdispath算法流程圖： beginuse_cpu=0x=0

/*use_cpu中記錄CPU運(yùn)行時(shí)間unuse_cpu=0 /*unuse_cpu中記錄CPU空閑時(shí)間ready 隊(duì)列不空或blocked隊(duì)列不空是

否end是ready隊(duì)列不空 否p ready隊(duì)首元素p->PCB.state置“運(yùn)行”p->PCB.namep->PCB.cpu_time--use_cpu++

unuse_cpu++是否 p->PCB.cpu_time>0釋放p 是pready隊(duì)列隊(duì)尾是x++x==t 否是blocked ready隊(duì)列隊(duì)尾；x=0試驗(yàn)二分區(qū)式存儲(chǔ)治理試驗(yàn)性質(zhì)：設(shè)計(jì)建議學(xué)時(shí)：6試驗(yàn)?zāi)康模和ㄟ^這次試驗(yàn)，加深對內(nèi)存治理的生疏，進(jìn)一步把握內(nèi)存的安排、回收算法的思想。預(yù)習(xí)內(nèi)容：閱讀教材《計(jì)算機(jī)操作系統(tǒng)》第四章，把握存儲(chǔ)器治理相關(guān)概念和原理。試驗(yàn)內(nèi)容：設(shè)計(jì)程序模擬內(nèi)存的動(dòng)態(tài)分區(qū)法存儲(chǔ)治理。內(nèi)存空閑區(qū)使用自由鏈治理，承受最壞適應(yīng)算法從自由鏈中查找空閑區(qū)進(jìn)展安排，內(nèi)存回收時(shí)假定不做與相鄰空閑區(qū)的合并。假定系統(tǒng)的內(nèi)存共640K，初始狀態(tài)為操作系統(tǒng)本身占用64K。在t1時(shí)間之后，有作業(yè)A、B、C、D8K、16K、64K、124Kt2C完成；在t3時(shí)間之后，作業(yè)E50Kt4時(shí)間之后，作業(yè)D完成。要求編程序分別輸出t1、t2、t3、t4時(shí)刻內(nèi)存的空閑區(qū)的狀態(tài)。實(shí)現(xiàn)提示C語言：程序中自由鏈隊(duì)列的結(jié)點(diǎn)類型可描述如下：struct freelink{int len,address; /* len/* addressstruct freelink *next;}內(nèi)存占用區(qū)用鏈表描述，其結(jié)點(diǎn)類型描述如下：struct busylink{charname; /*作業(yè)或進(jìn)程名name=’S表示OS占用int len,address;struct busylink*next;}并設(shè)全程量：structfreelink*free_head=NULL;//自由鏈隊(duì)列〔帶頭結(jié)點(diǎn)〕隊(duì)首指針structbusylink*busy_head=NULL,*busy_tail=NULL；//占用區(qū)隊(duì)列隊(duì)〔帶頭結(jié)點(diǎn)〕首指針//占用區(qū)隊(duì)列隊(duì)尾指針設(shè)計(jì)子函數(shù)：void start(void); /*設(shè)置系統(tǒng)初始狀態(tài)*/{ structfreelink*p;structbusylink*q;free_head=(struct freelink*)malloc(sizeof(struct freelink));free_head->next=NULL; //創(chuàng)立自由鏈頭結(jié)點(diǎn)busy_head=busy_tail=(struct busylink*)malloc(sizeof(structbusylink));busy_head->next=NULL; //創(chuàng)立占用鏈頭結(jié)點(diǎn)p=(structfreelink*)malloc(sizeof(structfreelink));p->address=64;p->len=640-64; 64K〕p->next=NULL;free_head->next=p;q=(struct busylink*)malloc(sizeof(structbusylink));q->name=’S’; /* S表示操作系統(tǒng)占用*/q->len=64; q->address=0; busy_head->next=q; busy_tail=q;}void requireMemo(char name,int require);/*模擬內(nèi)存安排*/void freeMemo(charname); /*模擬內(nèi)存回收*/void past(int time); /*模擬系統(tǒng)過了time時(shí)間*/void printlink; /*輸出內(nèi)存空閑狀況〔自由鏈的結(jié)點(diǎn)〕*/設(shè)計(jì)主函數(shù)：main{start;past(t1);requireMemo(‘A’,8); requireMemo(‘B’,16);requireMemo(‘C’,64);requireMemo(‘D’,124);printlink;past(t2);freeMemo(‘C’);printlink;past(t3);requireMemo(‘E’,50);printlink;freeMemo(‘D’);printlink;}試驗(yàn)要求：上機(jī)前認(rèn)真使用C語言編寫好程序，承受TurboC作為編譯環(huán)境；上機(jī)時(shí)獨(dú)立調(diào)試程序依據(jù)具體試驗(yàn)要求，填寫好試驗(yàn)報(bào)告〔包括思想、源程序、實(shí)例運(yùn)行結(jié)果。requireMemo(char name,int require)流程圖如下：begin否end printf(“Can’tallocate”)

free_head->next->len>=requirep=(struct busylink*)malloc(…);p->name=name;p->address=free_head->next->address;p->len=require;p->next=NULLbusy_tail->next=p;busy_tail=p;w=free_head->next;free_head->next=w->next;w->len==require

w->address=w->address+require;w->len=w->len-require;u=free_head;v=free_head->next;free(w)

(v!=NULL)&&v->len>w->lenu->next=ww->next=v

u=vv=v->nextendfreeMemo(charname)流程圖如下：beginq=busy_headp=busy_head->next否(p!=NULL)&&(p->name!=name)q=pp=p->nextp==NULL是if (p==busy_tail) busy_tail=q; printf(“%cisnotexist”,name)q->next=p->next;len=p->len;address=p->address;free(p)endw=(structfreelink*)malloc(…);w->len=len;w->address=address; 否是u=free_headv=free_head->next(v!=NULL)&&(v->len>len)u=vv=v->next

u->next=ww->next=vend試驗(yàn)三虛擬存儲(chǔ)治理試驗(yàn)性質(zhì)：驗(yàn)證建議學(xué)時(shí)：3試驗(yàn)?zāi)康模捍鎯?chǔ)治理的主要功能之一是合理的安排空間。懇求頁式治理是一種常用的虛擬存儲(chǔ)治理技術(shù)。本試驗(yàn)的目的是懇求頁式存儲(chǔ)治理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，把握懇求頁式存儲(chǔ)治理的頁面置換方法。預(yù)習(xí)內(nèi)容：閱讀教材《計(jì)算機(jī)操作系統(tǒng)》第四章，把握存儲(chǔ)器治理相關(guān)概念和原理。試驗(yàn)內(nèi)容：通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。指令的地址按下述原則生成：①、50%的指令是挨次執(zhí)行的；②、25%的指令是均勻分布在前地址局部；③、25%的指令是均勻分布在后地址局部。具體的實(shí)施方法是：① 在[0,319]的指令地址之間隨機(jī)選取一起點(diǎn)m;② 挨次執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；③ 在前地址[0,m+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m’；④ m’+1;⑤ 在后地址[m’+2,319]中隨機(jī)選取一條指令并執(zhí)行；⑥ 320次指令。 將指令序列變換成頁地址流1K；432頁；32K；在用戶虛存中，按每K10320條指令在虛存中的存放方式為：第0第9條指令為第0頁〔[，9；第10條第19條指令為第1頁〔[119；.第310~第319條指令為第31頁〔32頁。計(jì)算并輸出下述各種算法在不同的內(nèi)存容量下的缺頁率。①先進(jìn)先出的算法FIF；②最近最少使用算法LR；③最正確淘汰法OP：先淘汰最不常用的頁地址；④最少訪問頁面算法LF；⑤最近不常常使用算法NU其中③和④為選擇內(nèi)容。缺頁率=〔頁面失效次數(shù)〕/〔頁地址流長度〕在本試驗(yàn)中，頁地址流的長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。(4)隨機(jī)數(shù)產(chǎn)生方法試驗(yàn)指導(dǎo)

rand，分別進(jìn)展初始化和產(chǎn)生隨機(jī)數(shù)。例如：rand;語句可初始化的一個(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ù)。1、數(shù)據(jù)類型定義頁面類型typedefstruct{intpn,pfn,counter,time;}pl_type;/*pn為頁號(hào)，pfn為頁面號(hào)，counter為一個(gè)周期內(nèi)訪問該頁面次數(shù)，time為訪問時(shí)間。頁面掌握構(gòu)造pfc_struct{intpn,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)程虛頁掌握構(gòu)造*freepf_head為空頁面頭指針*busypf_head為忙頁面頭指針*busypf_tail為忙頁面尾指針2、函數(shù)定義voidinitialize();/*初始化函數(shù)，給每個(gè)相關(guān)的頁面賦值voidFIFO(); /*FIFO算法時(shí)的缺頁率voidLRU(); /*LRU算法時(shí)的缺頁率voidOPT( /*OPT算法時(shí)的缺頁率voidLRU(); /*LFU算法時(shí)的缺頁率voidNUR(); /*計(jì)算使用NUR算法時(shí)的缺頁率3、 變量定義int a[total_struction]: 指令流數(shù)據(jù)組int [total_instruction]:每個(gè)指令所屬頁號(hào)intoffset[total_instruction]:10條指令后取模運(yùn)算頁號(hào)偏移量inttotal_pf:用戶進(jìn)程的內(nèi)存頁面數(shù)intdiseffect:缺頁率2、 程序流程圖3、 程序框架：#define total_struction 320#define total_vp 32typedefstruct{intpn,pfn,counter,time;}pl_type;pl_typep[total_vp];pfc_struct{intpn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_struction];int[total_struction],offset[total_struction];voidinitialize();{……}voidFIFO();/LRU();{……}main( ){ints,i,j;sand(getpid*10);s=(float)319*rand/32767+1;for(i=0;i<total_struction;i++){a[i]=s;a[i+1]=a[i]+1;a[I+2]=(float)a[i]*rand/32767;a[i+3]=a[i+2]+1;s=(float)rand*(318-a[i+2])/32767+a[i+2]+2;}for(i=0;i<total_instruction;i++){[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i<=32;i++) FIFO(i);/LRU();}例如：a[0]=194a[1]=195a[2]=55a[3]=56a[4]=73a[5]=74a[6]=30a[7]=31a[8]=257a[9]=258a[10]=210a[11]=211a[12]=319a[13]=320a[14]=46a[15]=47a[16]=273a[17]=274a[18]=205a[19]=206試驗(yàn)四文件治理試驗(yàn)性質(zhì)：設(shè)計(jì)建議學(xué)時(shí)：3試驗(yàn)?zāi)康模罕驹囼?yàn)的目的是通過一個(gè)閱讀和設(shè)計(jì)局部簡潔多用戶文件系統(tǒng)的過程，加深理解文件系統(tǒng)的內(nèi)部功能和內(nèi)部實(shí)現(xiàn)。預(yù)習(xí)內(nèi)容：閱讀教材《計(jì)算機(jī)操作系統(tǒng)》第六章，把握文件治理相關(guān)概念和原理。試驗(yàn)內(nèi)容：DOS①可以實(shí)現(xiàn)以下幾條命令LOGIN 用戶登錄DIR 列文件名目CREATE 創(chuàng)立文件DELETE 刪除文件OPEN 翻開文件CLOSE 關(guān)閉文件READ 讀文件WRITE 寫文件COPY 拷貝文件②列名目時(shí)要列出文件名，物理地址，保護(hù)碼和文件長度。③源文件可以進(jìn)展讀寫保護(hù)。試驗(yàn)提示：①首先應(yīng)確定文件系統(tǒng)的數(shù)據(jù)構(gòu)造：主名目、子名目及活動(dòng)文件等。主名目和子名目都以文件的形式存放于磁盤，這樣便于查找和修改。②用戶創(chuàng)立的文件，可以編號(hào)存儲(chǔ)于磁盤上。如：file0,file1