操作系统实验二

—、试验目的理解操作系统内存管理的原理及分页内存管理方案二、 试验要求1、 实现分页内存管理方案，假定页和帧的大小均为4KB,物理内存为128MB2、 输入为进程ID,所需内存大小等，输出为页表。3、 请按要求撰写实验报告，并和源程序一起打包上传4、 实验平台不限，linux和windows均可5、 与第一次实验的程序整合成一个程序三、 试验环境WindowsXPVisualC++6.0四、 试验内容为了与上一个实验结合，并且考虑到可能需要兼容以后的实验，所以本次实验不但重写了PCB,而且按照自己对操作系统的理解构造出了一虚拟的I/O设备和两套调度程序（作业调度程序和CPU调度程序）、首先从与内存分配相关的作业调度函数说起，程序中为Jobs_scheduler。Job_scheduler的作用如下图所示；就绪队列先将硬盘中的主程载入内存同日*加入就绪队列—PCB1PCB21PCB3PCB4PCB5就绪队列先将硬盘中的主程载入内存同日*加入就绪队列—PCB1PCB21PCB3PCB4PCB5作业调度程序(Jobs_scheduier)Job.schediiler从大容量存储设备上的缓冲池中载入新生成的进程到内存，同时生成新的PCB到就绪队列中。这里涉及到了两个数据结构classProgram,classPCBoProgram:进程编号number需要页的数日intpage_numbers县体内容，61tX®解为代53模棹用vector<int>v存储PCB：编号number进程状态intsatate程序计数器intpc[2]记账信息这里是运行时间run_timePageTablePCB中的state包含五个状态NEW、READY.RUN、WAITING、TERMINATED,加入到ReadyQueue中等待运行的PCB均为READY状态的，运行中会被置为RUN,WAITNG状态为等待UO设备的进程，如果进程状态为TERNHNATED,将会被移出作业队列。Job_scheduler函数在将program装入内存前，会查看帧表内空闲的帧的数目是否大于等于program所需的页数目，如果成立才装入，并且为PCB构造页表。构造时，先按照帧表通过顺序查找找到可用的帧，然后就将页的内容加载上去。

接下来是CPU调度程序，也成为短期调度程序。CPU.scheduler所做的工作如下图所示，其操作的队列是就绪队列RedayQueue如果terminated就删除本程序采用的调度算法为分时调度，时间片大小TnneSlice取为1（当然这个随时都可用改动），里面执行程序的函数Run是模拟CPU功能的，它会返回一个值,Normal表示执行正常,若是返回了INTERRUPT中断；ERROR出错就会中断此次运行，并且将所指PCB从ReadyQueue中移除。这里的Run函数其实模拟了CPU的取指令和翻译指令的功能，本程序只有一个有实际作用的指令，’O'，如果内存中的内容为。（十进制ASCH码值），则代表需要利用UO设备输出该地址内容。如上图所示，PCB会加入到WaitmgQueue中等待UO,并判断此时UO设备是否开启，如果未开启则开启设备。Run函数也因此返回一个intemipt值。运行结果janj■c\Dociimtmi：xnn<lSteti:in^x\A<lminixi:rorZl\ncew\Dc?l*iiK\ T23456345656565661111111111

pppppppvppppppppppPPUUUPPDDr*<<it*<<r1*UI1*UI1*UI1*UI1runrunrunviinviinviinviint*<<nt*<<nt*<<njrvtnI/Oi*uni*unrunrunrunrunviinviinvuntimt?timt?tli«ietli«ietli«ietImot;inct;incjanj■c\Dociimtmi：xnn<lSteti:in^x\A<lminixi:rorZl\ncew\Dc?l*iiK\ T23456345656565661111111111

pppppppvppppppppppPPUUUPPDDr*<<it*<<r1*UI1*UI1*UI1*UI1runrunrunviinviinviinviint*<<nt*<<nt*<<njrvtnI/Oi*uni*unrunrunrunrunviinviinvuntimt?timt?tli«ietli«ietli«ietImot;inct;incZinct:imct:imct:imct:imctimt?timt?timt?tirie?=Otli«ietli«ieZincZincZincZinct:imct:imct;5me22223344556234567H91在编号为I的进程中的第一个内存单位设置了一条uo指令，可以看出其发生中断后等待IO完成才重新回到ReadyQueue中并执行完毕。「PaceTable-txt-记事本 |-|f^||X||文件®端相⑧格五查君⑦帮肪史）*************************K*0*K12**03**45678**901234**0123456789**1*X11**11**11111**122222*0123456789*0*XX。1*J91*701234*E012345心以上结果是在内存足够大的情况，卜•面再看一组内存不能同时满足需求的情况plruntinep2runtinePlI/O:0plruntineplruntineplruntineplruntineplruntineplruntineplruntineplruntineplruntinep3runtinep3runtinep4runtinepSruntinep4runtinepSruntinepSruntinepSruntinep6runtinepSruntinep6runtinep6runtinep6runtinep6runtinep6runtine0234567891121122341523456L.PageTable.txt-记事本文件史）编帽E：格式。查看⑦帮助以）此次内存设为11帧，编号为1的进程需要10帧，编号为2的进程需要1帧，我们看到,2号进程顺利载入并执行了，但其他进程都要等到1号进程执行完释放内存后才能载入内存,符合预期情况。五、心得体会为了很好的仿真，本次试验尽可■能地模拟了硬件的工作，，如输入输出设备和模拟CPU的run函数，基本上把教材77页调度问题的队列图所示功能模拟出来了，也大体实现了从用户程序到系统进程再到硬件的执行过程。对于本次实验的核心内容一一内存管理，实现了从磁盘到内存额装载过程，实现了页表的创建，实现了内存的释放。缺陷是没有考虑到换入换出等动态的情况，也就是说在此做了一个假设：每个进程相互独立旦对于每个单独的进程来说，内存空间是足够大的。第二点缺陷是，没有按照题目要求分配那么多的内存空间，因为那么大输入输出不好控制。在本程序中，输入输出与要求有出入，并没有输入进程需要的时间，而是以进程的具体内容代替，在这里又有一个假设：假设进程在CPU中每执行一步需要一个单位的时间，这样进程的大小也就等价于进程需要的时间了（排除有I/O请求的情况），个人认为这样假设比人工限定执行时间更加贴近现实情况。程序的输入非即时的，而是通过事先设定好的5个进程加上运行后随机生成的若干进程，也是为了模拟实际情况考虑。因为全手工输入需要输入进程的到这时间，也就是需要根据到达时间来为缓冲池中进程排序的问题，但实际情况下到这时间是多余的，先创建的先加入队列即可，所以采用了随机生成的方式。为了此次实验，复习了调度和内存管理两章的大部分内容，对操作系统对进程调度和内存分配管理有了更深入的认识，但只是从概念上，没有看到真正操作系统的代码或者算法实例，所以可能很多地方的代码与实际情况出入很大。代码：#iiiclude<iostieam>#iiiclude<list>#iiiclude<queue>#iiiclude<iteratoi>#iiiclude<wiiidows.h>#iiiclude<fstream>#iiiclude<cstdlib>#iiiclude<ctmie>usingnamespacestd;侔**************随机数，后面随机生成进程用的*************/voidraiid_seed()intseed=static_cast<int>(tune(O));srand(seed);}hitiand_mt(inta,intb){returna+raiid()%(b-a+1);}座***************随机数，后面随机生成进程用的*************/hitAddOflO=0;intpcr[2]=(0.0);/*进程状态*/#defineNEW0#defineREADY1#defineRUN2#defineWAITING3^defineTERMINATED4/*运行状态*/#defineINTERRUPT2〃中断#defineNORMAL1〃正常#defineERROR0〃出错^defineFINISH1//完成/*时间片大小*/#defineTmieSlice1/*设备信息*/#defineOFF0#defineON1/*页大小*/#definePAGE1/*帧大小*/#defineFRAME1/*内存里面分成的帧的数目*/#defineMEMORY11mtMemoiy[MEMORY*FRAME];/*初始化内存*/voidInitMEMQ{for(mti=0;i<MEMORY*FRAME;i++)Memoryfi]=i;}/*一段程序，或是一个新的进程*/classPrograin{public:/*程序编号*/intnumber;/*内容，或者是代码*/vector<iiit>v;/*需要的页的数目*/intpage^numbers;/*计算需要的页的数目，向下取整*/voidftagmentation()page_numbeis=v.size()/FRAME;if(page_numbeis*FRAME<v.sizeQ)page_numbers++;//cout«page_numbeis«endl;}/**构造函数@paiaml编号@paiani2内容**/Program(constmt&n.conststiiiig&s)tliis->number=n;for(inti=0;i<s.size();i++)vpush_back(s[i]);fiagmentationQ;}};/*页表节点*/classPageTableNode{public:/*页号*/intpage_number;/*帧号*/intfiame_number;PageTableNode(constmt&page,constint&flame)page_number=page;fiaine_number=frame;}};将程序的一页加载到内存上，不考虑此帧是否可用@paraml进程@paiain2页号@paiam3帧号@return装载成功**/boolLoadMemoiy(constProgram&p,constintnP,constmt&nF){for(mti=0;i<PAGE;i++)/*It是将被写入的逻辑地址*/mtit=iiP*PAGE+i;/*addi是物理地址*/mtaddr=11F*FRAME+i;if(it<p.v.size())Memory[addr]=p.vfit];)returntine;},，*************************************************************************//*帧表节点*/classFrameTableNode{public:/*是否可用*/boolfree;/*如果不可用，被哪个进程占用*/intprocess_number;/*被该进程的哪一页占用*/intpage_number;FrameTableNode。jfiee=tme;}};classFrameTable{public:/*帧表♦/FiaineTableNodeflametable[MEMORY];/*当前可用的帧的数目*/intfiee_fiame;FiaineTableQfiee_fiame=MEMORY;}};/*这是帧表的实例啊*/FrameTableFraTable;J*************************************************************************/,**********************************************4:**********************************//*这个文件用来保存生成的页表的*/ofstieamoutfile;classPCB{public:/*进程编号*/intnumber;/*进程状态*/intstate;/*程序计数器*/mtpc[2];/*cpu寄存器*////*cpu调度信息♦////*记账信息，这里是运行时间*/intnin_tmie;/*内存管理信息，这里就是页表*/list<PageTableNode>PageTable;找到程序所在页对应的帧号@paiaml要找的页号@ieturn如果失败，返回.L成功则返回帧号**/intfuidfiame(constmt&page);/*打印页表*/voidprintPageTableQ;/*I/O状态信息*////*构造函数*/PCB(constPiogram&p);};mtPCB::findfiame(constmt&page){list<PageTableNode>:iteratorp=PageTable.begiiiQ;while(p!=PageTable.endQ)if(page==p->page_number)returnp^fiame^number;elseP++;}if(p==PageTable.endQ)return-1;}voidPCB::printPageTable(){outfile.open(HPageTable.txtM,ios_base::app);outfile«n***************************n«nPCBpM«number«””«*****************************n«end]•list<PageTableNode>:iteratorp=PageTable.begiii();for(;p!=PageTable.endQ;p++)outfile«p->page_number«””«p->franie_number«endl;outfile«^*************************************..«••*************************#**..<<endloutfile.close。;}PCB::PCB(constProgiam&p)〃先设置状态为新的state=NEW;mti=0;intj=0;/**开始一页一页地加载到内存构造页表的过程**/while(j<p.page_numbers)while(!FraTable.fiametable[i].fiee)(1++;)if(LoadMemoiy(p,j,i))(PageTable.push_back(PageTableNode(j,i));FraTable.fiametable[i].free=false;FraTable.fiee_fiaiiie-;J++;)}number=p.number;njn_tiine=0;/*pc初始化为程序在物理内存的首地址*/pc[O]=0；pc[l]=O;this->piiiitPageTable();state=READY;}boolRelease(PCB&pcb){for(mti=0;i<=pcb.PageTable.back().page_number;i++)jFraTable.frametable[pcb.fiiidfiaiiie(i)].free=tme;FraTable.free_fiaine++;//cout«"ReleaseH«pcb.findfiame(i)«”Frame;)returntine;/*就绪队列*/list<PCB>ReadyQueue;/*等待队列*/list<PCB>WaitingQueue;/*缓冲队列*/list<Program>BufferList;voidIncPc(PCB&pcb.mtpc[2]){if(pc[O]<pcb.PageTable.back().page_numbei-)fif(pc[l]<1)(pc[l]++；}else(pc[0]++；pc[l]=0;)pcb.state=READY;}elseif(pc[l]<PAGE・1)fpc[l]++；}elsepcb.state=TERMINATED;boolio_equipment=OFF;/*10设备(DMA)*/DWORDXVTNAPIIOEquipment(LPVOIDIpPaiamter){io_equipment=ON;list<PCB>:iteratorpw=WaitingQueue.begiii();wlule(pw!=WaitmgQueue.endQ)/*为了体现uo设备速度较慢，所以在此用了Sleep函数*/Sleep(lOOO);cout«HPH«pw->number«"I/O:M«(char)Memory[AddOflO]«endl:if(pw->state==WAITING)pw->state=READY;ReadyQueue.push_back(*pw);pw=WaitmgQueue.eiase(pw);iRpw!=WaitmgQueue.endQ)pw++;elsepw=WaitmgQueue.begiii();}io_equipment=OFF;returnFINISH;}HANDLEioEquipment;/**模拟CPU执行只实现了部分功能，并没有完全按照原理模拟hitRun(PCB&pcb){pcb.state=RUN;list<PageTableNode>:iteratorp=pcb.PageTable.begiiiQ;intaddi[2];addi[l]=pcb.pc[l];addi[O]=pcb.findfiame(pcb.pc[O]);switch(Memoiy[addi[0]*FRAME+addr[l]])case。，：〃如果指令触发了输出设备pcb.state=WAITING;pcr[O]=pcb.pc[O];pcr[l]=pcb.pc[l]；IncPc(pcb,per);pcb.pc[O]=pcr[O];pcb.pc[l]=pcr[l]；AddOflO=addr[0]*FRAME+addi[l];WaitingQueue.push_back(pcb);/*如果I/O设备未开启，则打开，否则什么都不做*/if(io_equipment==OFF)loEquipment=CreateTliiead(NULL.0,lOEquipment,NULL,0.NULL);elsereturnINTERRUPT;default:break;}/*在没有跳转的情况下，运行之后，pc自加*/pcr[0]=pcb.pc[0];pcr[l]=pcb.pc[l];IncPc(pcb,per);pcb.pc[0]=pcr[0];pcb.pc[l]=pci[l];returnNORMAL;}HANDLEhMutex=CreateMutex(NULL,FALSE,“screen”);/*长期调度程序，将缓冲池中的进程加载到内存上*/DWORDWINAPIJobs_scheduler(LPVOIDIpParamter){list<Prograin>::iteratorp=BuffeiList.begiii();wlule(tme)//WaitFoiSiiigleObject(liNIutex,INFINITE);iRp!=BuffeiList.endQ&&p->page_numbeis<=FraTable.fiee_fiame){Read\TQueue.push_back(PCB(*p));p=BuffeiList.erase(p);}elseif(p!=BufferList.end())P++;elsep=BufferList.begin。；//ReleaseMutex(liMutex);}}/*利用RR算法的短期调度程序*/DWORDWINAPICPU_scheduler(LPVOI