2024年動態(tài)分區(qū)分配算法實驗報告

操作系統(tǒng)試驗報告試驗二:動態(tài)分辨別配算法.學生：學號：學院：系別：專業(yè)：試驗時間：報告時間：一、試驗內容編寫一個內存動態(tài)分辨別配模擬程序，模擬內存的分派和回收的完整過程。一個好的計算機系統(tǒng)不但要有一個足夠容量的、存取速度高的、穩(wěn)定可靠的主存儲器，并且要能合理地分派和使用這些存儲空間。當用戶提出申請存儲器空間時，存儲管理必須依照申請者的要求，按一定的方略分析主存空間的使用情況，找出足夠的空閑區(qū)域分派給申請者。當作業(yè)撤離或積極償還主存資源時，則存儲管理要收回作業(yè)占用的主存空間或償還部分主存空間。主存的分派和回收的實現(xiàn)與主存儲器的管理方式有關的，通過本試驗協(xié)助學生了解在可變分區(qū)管理方式下應怎樣實現(xiàn)主存空間的分派和回收。三、試驗原理模擬在可變分區(qū)管理方式下采取最先適應算法實現(xiàn)主存分派和回收。(1)可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當要裝入一個作業(yè)時，依照作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分辨別配給該作業(yè)；若無，則作業(yè)不能裝入。伴隨作業(yè)的裝入、撤離，主存空間被提成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：05k05k10k14k26k32k512k作業(yè)1作業(yè)3空閑區(qū)作業(yè)2空閑區(qū)為了闡明哪些區(qū)是空閑的，能夠用來裝入新作業(yè)，必須要有一張空閑區(qū)闡明表，格式如下：起址長度狀態(tài)第一欄14K12K未分配第二欄32K96K未分配MMMM其中，起址——指出一個空閑區(qū)的主存起始地址。長度——指出從起始地址開始的一個連續(xù)空閑的長度。狀態(tài)——有兩種狀態(tài)，一個是“未分派”狀態(tài)，指出對應的由起址指出的某個長度的區(qū)域是空閑區(qū)。(2)當有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)闡明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)也許不小于作業(yè)需要量，這時應把本來的空閑區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個較小的空閑區(qū)。為了盡也許減少因為分割導致的空閑區(qū)，而盡也許保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)闡明表中，把每個空閑區(qū)按其地址次序登記，即每個后繼的空閑區(qū)其起始地址總是比前者大。(3)采取最先適應算法（次序分派算法）分派主存空間。按照作業(yè)的需要量，查空閑區(qū)闡明表，次序查看登記欄，找到第一個能滿足要求的空閑區(qū)。當空閑區(qū)不小于需要量時，一部分用來裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)闡明表中。因為本試驗是模擬主存的分派，因此把主存辨別配給作業(yè)后并不實際開啟裝入程序裝入作業(yè)，而用輸出“分派情況”來替代。(4)當一個作業(yè)執(zhí)行結束撤離時，作業(yè)所占的區(qū)域應當償還，償還的區(qū)域假如與其他空閑區(qū)相鄰，則應合成一個較大的空閑區(qū)，登記在空閑區(qū)闡明表中。(5)請按最先適應算法設計主存分派和回收的程序。假設初始時主存中沒有作業(yè)，現(xiàn)按下面序列進行內存的申請與釋放：作業(yè)1申請300K，作業(yè)2申請100K，作業(yè)1釋放300K，作業(yè)3申請150K，作業(yè)4申請30K，作業(yè)5申請40K，作業(yè)6申請60K，作業(yè)4釋放30K。請你為它們進行主存分派和回收，把空閑區(qū)闡明表的初值以及每次分派或回收后的變化顯示出來或打印出來。四、試驗報告(1)畫出最先適應分派算法流程圖、償還主存時的回收算法流程圖。最先適應分派算法流程圖：輸入作業(yè)對象輸入作業(yè)對象變化變化空閑區(qū)塊隊列+變化作業(yè)隊列次序遍歷次序遍歷空閑區(qū)塊隊列輸出成果輸出成果是否有是否有足夠空間的空閑區(qū)塊 N Y償還主存時的回收算法流程圖：輸入作業(yè)對象輸入作業(yè)對象變化空閑區(qū)塊隊列+變化空閑區(qū)塊隊列+變化作業(yè)隊列是否存在該作業(yè)是否存在該作業(yè)？ N輸出成果輸出成果 Y(2)程序中使用的數(shù)據(jù)結構及符號闡明。答：本程序用c++語言編寫，其中用到了class{}類、指針，利用指針將classTable{}(空閑表類)和classPro{}(作業(yè)類)用鏈式存儲的方式進行插入、刪除、新建、排序等工作。(3)打印一份源程序并附上注釋。#include<iostream.h>#include<string.h>classPro //作業(yè)對象{ public: Pro(){ Size=0; next=NULL; Start=0; Name[0]='\0'; } Pro(intSi,charNa[]){ Size=Si; next=NULL; Start=0; strcpy(Name,Na); } voidprintf() { cout<<Name<<"\t"<<Start<<endl; } voidArrange(intSta,Pro&Ne) { Start=Sta; next=&Ne; } Pro*next; //用來指向下一個輸入的作業(yè) intSize; //作業(yè)大小 charName[10]; // 作業(yè)名稱 intStart; //在內存中存儲的起始地址};classTable //空閑表{ public: Table*next; //指向下一個空閑區(qū)塊 intSize; //空閑區(qū)塊大小 Table(){ } Table(intSta,intSiz) { Start=Sta; Size=Siz; Over=Sta+Siz; next=NULL; } intStart; //空閑區(qū)塊起始地址 intOver; //空閑區(qū)塊結束地址};voidPri(Pro*ph){ if(ph) { cout<<endl<<"內存中的作業(yè)"<<endl<<"作業(yè)名"<<"\t"<<"起始地址"<<endl; for(Pro*p=ph;p;p=p->next) p->printf(); cout<<endl; } else cout<<"作業(yè)已所有運行完成！"<<endl;}voidPrik(Table*h){ if(h) { cout<<"空閑區(qū)塊分派情況"<<endl<<"空閑區(qū)塊起始地址"<<"\t"<<"空閑區(qū)塊大小"<<endl; for(;h;h=h->next) cout<<"\t"<<h->Start<<"\t\t\t"<<h->Size<<endl; cout<<endl; } else cout<<"無空閑區(qū)塊！"<<endl;}voidPX(Table*&h,Table*p) //排序次序空閑區(qū)塊{ Table*hp=h->next; Table*hf=h; Table*hf2=h; Table*hf1=h; if(p->Start==1000) return; for(;hf1;hf1=hf1->next) //檢查新增空閑區(qū)塊是否是原空閑區(qū)塊 { if(hf1->Start<p->Over&&hf1->Start>=p->Start&&hf1==h) h=h->next; elseif(hf1->Start<p->Over&&hf1->Start>=p->Start) { hf2->next=hf1->next; } hf2=hf1; } if(!h) //檢查有無空閑區(qū)塊,當空閑區(qū)塊是原空閑塊時會清除重新分派 { h=p; } else { if(h->next==NULL) { p->next=h; h=p; } else { for(;hp;hp=hp->next) { if(p->Size<hp->Size) { p->next=hp; hf->next=p; break; } hf=h; } if(!hp) hf->next=p; } }}voidZJKX(Table*&h,Pro*p,Pro*pp) //空閑區(qū)塊的變化{ intpos=p->Start+p->Size,jugy=0; Table*ph1=h; for(Table*ph=h;ph;ph=ph->next) { if(ph->Start==pos) { jugy=1; Table*pph1=h; Table*pph=h; for(;pph;pph=pph->next) { if(pph->Over==p->Start) //3 { pph1->next=pph->next; ph1->next=ph->next; Table*n=newTable(pph->Start,ph->Size+pph->Size+p->Size); PX(h,n); break; } pph1=pph; } if(!pph) //4 { ph->Size=ph->Size+p->Size; ph->Start=p->Start; PX(h,ph); } } ph1=ph; } if(!jugy) { Table*pph1=h; for(Table*pph=h;pph&&!jugy;pph=pph->next) { for(Pro*pp1=pp;pp1;pp1=pp1->next) if(p->Start==(pp1->Start+pp1->Size)) //2 { for(Table*h2=h;h2;h2=h2->next) { if((p->Start+p->Size)==h2->Start) { Table*n=newTable(p->Start,p->Size+h2->Size); PX(h,n); jugy=1; break; } } if(!jugy) { Table*n=newTable(p->Start,p->Size); PX(h,n); jugy=1; break; } } elseif((p->Start+p->Size)==pp1->Start) //1 { for(Table*h1=h;h1;h1=h->next) { if(h1->Over==p->Start) { Table*n=newTable(h1->Start,p->Size+h1->Size); PX(h,n); jugy=1; break; } } if(!jugy) { Table*n=newTable(p->Start,p->Size); PX(h,n); jugy=1; break; } } pph1=pph; } } if(!jugy) for(Table*pph=h;pph;pph=pph->next) //5 if(pph->Over==p->Start) { pph->Size=pph->Size+p->Size; pph->Over=pph->Over+p->Size; PX(h,pph); break; } if(!h) { Table*x=newTable(p->Start,p->Size); h=x; }}voidSF(Pro*&ph,charN[],Table*&h) //釋放作業(yè){ intjugy=0; Pro*pp=ph; if(!strcmp(ph->Name,N)) { ZJKX(h,ph,ph); ph=ph->next; jugy=1; } else for(Pro*p=ph->next;p;p=p->next) { if(!strcmp(N,p->Name)) //完成作業(yè)的刪除:刪除作業(yè)對象+增加空閑區(qū)塊對象，并檢查是否能夠合并 { ZJKX(h,p,ph); pp->next=p->next; jugy=1; } pp=p; } if(!jugy) cout<<"隊列中沒有這個作業(yè)!"<<endl;}voidJR(Pro*&ph,Pro*p,Table*&h) //加入作業(yè){ Pro*pp=ph; intjugy=0; //分割空閑區(qū)塊 Table*hpp=h; for(Table*hp=h;hp;hp=hp->next) { if(p->Size<=hp->Size) { p->Start=hp->Start; if(p->Start+p->Size==1000) { if(hpp==hp) h=NULL; else hpp->next=NULL; jugy=1; } else { hp->Size=hp->Size-p->Size; hp->Start=p->Start+p->Size; jugy=1; break; } } } if(jugy) { if(!ph) { ph=p; } else { for(;pp->next;pp=pp->next) ; //作業(yè)隊列尾部插入新作業(yè)對象 pp->next=p; } } else cout<<"沒有足夠的空間分派！"<<endl;}intmain(){ cou