计算机操作系统实验报告-2

一、实验目的1．通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。2．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。二、实验内容：设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1.先进先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置换算法（OPT）三、实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。假设分给一作业的物理块数为3，页面数为20个。页面号为(20个)：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1四、源程序结构分析程序结构程序共有以下九个部分：intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidLRU(void);//LRU算法voidOPT(void);//OPT算法；voidBlockClear(void);//BLOCK清空，以便用另一种方法重新演示intmain()//主程序源程序代码#include<iostream.h>#defineBsize3#definePsize20structpageInfor{intcontent;//页面号inttimer;//被访问标记};classPRA{public:PRA(void);intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidLRU(void);//LRU算法voidOptimal(void);//OPTIMAL算法voidBlockClear(void);//BLOCK恢复pageInfor*block;//物理块pageInfor*page;//页面号串private:};PRA::PRA(void){intQString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};block=newpageInfor[Bsize];for(inti=0;i<Bsize}voidPRA::Optimal(void){intexist,space,position;for(inti=0;i<Psize;i++){{position=findReplace();block[position]=page[i];display();}}for(intj=0;j<Bsize;j++)block[j].timer++;//BLOCK中所有页面TIMER++}}voidPRA::BlockClear(void){for(inti=0;i<Bsize;i++){block[i].content=-1;block[i].timer=0;}}voidmain(void){cout<<"|页面置换算法|"<<endl;cout<<"|powerbywangxinchuang(080501228)|"<<endl;cout<<"||"<<endl;cout<<"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"<<endl;cout<<""<<endl;cout<<"选择<1>应用Optimal算法"<<endl;cout<<"选择<2>应用FIFO算法"<<endl;cout<<"选择<3>应用LRU算法"<<endl;cout<<"选择<0>退出"<<endl;intselect;PRAtest;while(select){cin>>select;switch(select){case0:break;case1:cout<<"Optimal算法结果如下:"<<endl;test.Optimal();test.BlockClear();cout<<""<<endl;break;case2:cout<<"FIFO算法结果如下:"<<endl;test.FIFO();test.BlockClear();cout<<""<<endl;break;case3:cout<<"LRU算法结果如下:"<<endl;test.LRU();test.BlockClear();cout<<""<<endl;break;default:cout<<"请输入正确功能号"<<endl;break;}}}五、实验结果1运行后的初始界面2opt算法3.FIFO算法4LRU算法实验目的：银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。问题分析与设计：1、算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。2、银行家算法步骤：（1）如果Requesti＜or=Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：

Available=Available-Request[i];

Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3、安全性算法步骤：（1）设置两个向量①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。（2）从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false②Need<or=Work如找到，执行步骤（3）；否则，执行步骤（4）。（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work=Work+Allocation;Finish[i]=true;转向步骤（2）。如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。实验代码：#include<iostream.h>#include<string.h>#include<stdio.h>#defineFalse0#defineTrue1intMax[100][100]={0};//各进程所需各类资源的最大需求intAvaliable[100]={0};//系统可用资源charname[100]={0};//资源的名称intAllocation[100][100]={0};//系统已分配资源intNeed[100][100]={0};//还需要资源intRequest[100]={0};//请求资源向量inttemp[100]={0};//存放安全序列intWork[100]={0};//存放系统可提供资源intp[100]={0};intq[100][100]={0};intz[100][100]={0};intM=100;//作业的最大数为100intN=100;//资源的最大数为100intgg=1;voidshowdata()//显示资源矩阵{inti,j;cout<<endl<<"此时刻的资源分配情况为："<<endl;cout<<"MaxAllocationNeedAvaliable"<<endl;cout<<"进程名";for(j=0;j<4;j++){for(i=0;i<N;i++)cout<<name[i]<<"";cout<<"";}cout<<endl;for(i=0;i<M;i++){cout<<""<<i<<"";for(j=0;j<N;j++)cout<<Max[i][j]<<"";cout<<"";for(j=0;j<N;j++)cout<<Allocation[i][j]<<"";cout<<"";for(j=0;for(i=0;i<M;i++){cout<<"*****************银行家算法的设计与实现*****************"<<endl;cout<<endl<<"请首先输入系统可供资源种类的数量:";cin>>cout<<"资源"<<i+1<<"的名称:";cin>>ming;name[i]=ming;cout<<"资源的数量:";cin>>number;Avaliable[i]=number;}cout<<endl;cout<cout<<endl<<"是否继续银行家算法？(按1键继续,按其它任意键退出):"; cin>>t; cout<<endl; }return运行截图问题描述：为了将内存中的空间运用充分，特别利用动态重定位算法对内存中的碎片进行拼接，用以放入适合大小的进程。二、程序分析与设计：1、基本思想建立一个空闲闲分区表,用于存储内存的数据信息,每个表项对应一块空闲内存的信息,程序通过查找表中的数据去寻找是否有适合当前进程的空间(利用首次适应算法),当没有找到时将对内存进行整理,即将数据往前移动,最后只剩下一快空间,再查看是否满足当前进程式的分配,如果可以则分配,否则进程放入等待队列中。2、结构定义constintMAX=1000;//空表的表项最大值constintMAX1=2048;//内存的字节数typedefclassmemoryroom{private:boolisfull;//这个字节是否可用charbyte[9];//这个字节存放的数据}MEMORY；//分区表的数据结构!!typedefclasstable{private:boolisuse;//该表项是否可用intstartaddress;//在内存中的起始地址intsize;//连续的大小}TABLE；3、算法描述/*在空分区中查找合适的内存空间*/boolprocInputMemory(TABLE*mt,intprocsize,MROOM*memory){inti;cout<<"\n正在空分区中查找合适的内存空间(按首次适应算法寻找)"<<endl;for(i=0;i<MAX;i++)if(mt[i].getIsUse()&&mt[i].getSize()>=procsize){cout<<"\n调入内成功"<<endl;cout<<"\n\n该进程在内存的"<<mt[i].getStartAddress()<<"起始处"<<endl;//内存设为被占用for(intj=mt[i].getStartAddress();j<mt[i].getStartAddress()+mt[i].getSize();j++)memory[j].setIsNotFull(true);//修改分区表if(procsize<mt[i].getSize()){mt[i].setSize(mt[i].getSize()-procsize);mt[i].setStartAddress(mt[i].getStartAddress()+procsize);}if(procsize==mt[i].getSize())mt[i].setIsUse(false);returntrue;}if(i==MAX)returnfalse;}/////////////////////////////////*对内存的碎片整理和对表项的改变*/voidmemoryRepeat(MROOM*memory,TABLE*em){inti,j,size,address;size=0;j=0;for(i=0;i<MAX;i++){if(!memory[i].getIsNotFull())size+=1;else{memory[i].setIsNotFull(false);memory[j].setIsNotFull(true);memory[j].setByte(memory[i].getByte());j++;}}em[0].setIsUse(true);em[0].setSize(size);em[0].setStartAddress(size);for(i=1;i<MAX;i++){em[i].setIsUse(false);em[i].setSize(0);em[i].setStartAddress(0);}}运行截图Demo一．实验目的1、掌握FPGA中lpm_ROM的设置，作为只读存储器ROM的工作特性和配置方法。2、用文本编辑器编辑mif文件配置ROM，学习将程序代码以mif格式文件加载于lpm_ROM中；3、在初始化存储器编辑窗口编辑mif文件配置ROM；4、验证FPGA中mega_lpm_ROM的功能。二．实验原理ALTERA的FPGA中有许多可调用的LPM(LibraryParameterizedModules)参数化的模块库，可构成如lpm_rom、lpm_ram_io、lpm_fifo、lpm_ram_dq的存储器结构。CPU中的重要部件，如RAM、ROM可直接调用他们构成，因此在FPGA中利用嵌入式阵列块EAB可以构成各种结构的存储器，lpm_ROM是其中的一种。lpm_ROM有5组信号：地址信号address[]、数据信号q[]、时钟信号inclock、outclock、允许信号memenable，其参数都是可以设定的。由于ROM是只读存储器，所以它的数据口是单向的输出端口，ROM中的数据是在对FPGA现场配置时，通过配置文件一起写入存储单元的。图3-1-1中的lpm_ROM有3组信号：inclk——输入时钟脉冲；q[23..0]——lpm_ROM的24位数据输出端；a[5..0]——lpm_ROM的6位读出地址。实验中主要应掌握以下三方面的内容：（1）lpm_ROM的参数设置；（2）lpm_ROM中数据的写入，即LPM_FILE初始化文件的编写；（3）lpm_ROM的实际应用，在GW48_CP+实验台上的调试方法。三．实验步骤（1）用图形编辑，进入mega_lpm元件库，调用lpm_rom元件，设置地址总线宽度address[]和数据总线宽度q[]，分别为6位和24位,并添加输入输出引脚，如图3-1-1设置和连接。（2）设置图3-1-1为工程。（3）在设置lpm_rom数据参数选择项lpm_file的对应窗口中（图3-1-2），用键盘输入lpm_ROM配置文件的路径（rom_a.mif），然后设置在系统ROM/RAM读写允许，以便能对FPGA中的ROM在系统读写。(4)用初始化存储器编辑窗口编辑lpm_ROM配置文件（文件名.mif）。这里预先给出后面将要用到的微程序文件：rom_a.mif。rom_a.mif中的数据是微指令码（图3-1-3）。（5）全程编译。四．实验原理图（1）rom结构图（2）初始化文件rom五．实验仿真波形图Clk为时钟脉冲，a为地址，q为数据。当clk上升沿时，将地址锁入，显示数值。波形图中，a为1时，q为00ED82；a为2是，q为00C050；a为3时，q为00E004。以此类推。可以看出，波形图与ROM初始化文件数据相同。一、实验目的：1.通过实验加深对计算机各功能部件的理解；掌握数据信息流和控制信息流的流动和实现过程，建立起整机概念；培养设计、开发和调试计算机的能力。2.提高使用EDA工具软件和可编程器件芯片的基本技能。3.培养科学研究的独立工作能力，取得工程设计与组装调试的实践和经验。二、设计方案：1.模型机的总体设计模型机的总体设计的内容包括确定各种部件的设置以及它们之间的数据通路结构。CISC模型机由CISC微处理器、地址寄存器AR、ROM和RAM存储器等组成。微处理器由算术逻辑运算单元ALU、状态条件寄存器、累加器AC、数据暂存器DR、通用寄存器R0～R2、程序计数器PC、指令寄存器IR、操作控制器和时序产生器组成。CISC模型机的操作控制器采用微程序控制器。2.微程序控制器的组成原理框图微程序控制器组成原理框图如图2所示。它主要由控制器、微指令寄存器和地址转移逻辑电路三大部分组成，其中微指令寄存器分为微地址寄存器和微命令寄存器两部分。图2微程序控制器组成原理框图3.模型机机器指令格式和指令系统CISC模型机的指令系统采用复杂的指令格式、多种指令字长度和多种寻址方式，但指令功能强大，单条指令的执行速度较慢。为了完成题目所要求的功能，模型机的指令系统共设计了8条不同的功能指令。指令字长度有单字长（1个字节）和双字长（2个字节）两种；寻址方式有三种，分别是寄存器寻址、直接寻址和立即寻址。这8条指令是IN1（输入），MOV（将一个数送入寄存器），CMP（比较），JB（小于跳转），ADD（两数相加），INC（自增1），JMP（无条件跳转），OUT1（输出）。4.时序产生器的设计原理及时序波形图CISC微处理器的时钟信号Q和清除信号CLR由外部输入，节拍脉冲信号Ti由时序产生器产生。图4-14描述了节拍脉冲信号与外部时钟信号、清除信号的时序关系。由图3可以看出，节拍脉冲信号T1、T2、T3、T4实际上是以Q为时钟输入信号的计数状态经过译码器译码后生成的，因此可写出节拍脉冲信号的逻辑表达式，并用VHDL语言实现之，然后将它创建为一个元件符号，供顶层电路调用。图3T1、T2、T3、T4与CLR、Q之间的时序关系图如果系统的时钟控制信号（即工作脉冲P）是在T1、T2、T3或T4的中间产生，且上升沿有效，则它产生方法是：先将Q取反，再和节拍脉冲信号Ti相“与”得到。如图4所示。图4时钟控制信号的形成方法5.微程序流程图根据模型机的数据通路图（图1）以及所有指令在CISC模型机中的操作过程，画出所有机器指令的微程序流程图，如图5所示。图中每个框为一个CPU周期（包含T1～T4共4个节拍脉冲周期）对应于一条微指令。框中上面的十六进制数表示的是当前微指令在控制存储器中的微地址；框中下面的十六进制数表示的是当前微指令的后续微坡地。在编写微指令时，图中的菱形框从属于它上面的方框。图5CISC模型机中所有机器指令的微程序流程6.汇编语言源程序算法思想为：采用R0寄存器存放从开关输入的任意一个整数，R1存放准备参加累加运算的奇数，R2存放累加的和，用一个循环程序实现如下：五、模型机的各单元VHDL源程序ALU的VHDL源程序ALU.vhdLIBRARYIEEE;USEIEEE.STD_LOGIC_1164.ALL;USEIEEE.STD_LOGIC_ARITH.ALL;USEIEEE.STD_LOGIC_UNSIGNED.all;ENTITYALUISPORT(A:INSTD_LOGIC_VECTOR(7DOWNTO0);B:INSTD_LOGIC_VECTOR(7DOWNTO0);S1,S0:INSTD_LOGIC;BCDOUT:OUTSTD_LOGIC_VECTOR(7DOWNTO0);CY,ZI:OUTSTD_LOGIC);ENDALU;ARCHITECTUREAOFALUISSIGNALAA,BB,TEMP:STD_LOGIC_VECTOR(8DOWNTO0);BEGINPROCESS(S1,S0)BEGINIF(S1='0'ANDS0='0')THEN--ADDAA<='0'&A;BB<='0'&B;TEMP<=AA+BB;BCDOUT<=TEMP(7DOWNTO0);CY<=TEMP(8);IF(TEMP="100000000")THENZI<='1';ELSEZI<='0';ENDIF;ELSIF(S1='0'ANDS0='1')THEN--CMP(SUB)BCDOUT<=A-B;IF(A<B)THENCY<='1';ZI<='0';ELSIF(A=B)THENCY<='0';ZI<='1';ELSECY<='0';ZI<='0';ENDIF;ELSIF(S1='1'ANDS0='0')THEN--INCAA<='0'&A;TEMP<=A+1;BCDOUT<=TEMP(7DOWNTO0);CY<=TEMP(8);IF(TEMP="100000000")THENZI<='1';ELSEZI<='0';ENDIF;ELSEBCDOUT<="00000000";CY<='0';ZI<='0';ENDIF;ENDPROCESS;ENDA;状态条件寄存器的VHDL源程序LS74.vhdLIBRARYIEEE;USEIEEE.STD_LOGIC_1164.ALL;ENTITYLS74ISPORT(LDFR:INSTD_LOGIC;CY,ZI:INSTD_LOGIC;FC,FZ:OUTSTD_LOGIC);ENDLS74;ARCHITECTUREAOFLS74ISBEGINPROCESS(LDFR)BEGINIF(LDFR'EVENTANDLDFR='1')THENFC<=CY;FZ<=ZI;ENDIF;ENDPROCESS;ENDA;LS273单元设计的VHDL语言程序8位数据寄存器的VHDL源程序LS273.vhdLIBRARYIEEE;USEIEEE.STD_LOGIC_1164.ALL;ENTITYLS273ISPORT(D:INSTD_LOGIC_VECTOR(7DOWNTO0);CLK:INSTD_LOGIC;O:OUTSTD_LOGIC_VECTOR(7DOWNTO0));ENDLS273;ARCHITECTUREAOFLS273ISBEGINPROCESS(CLK)BEGINIF(CLK'EVENTANDCLK='1')THENO<=D;ENDIF;ENDPROCESS;ENDA;1：2分配器的VHDL源程序FEN2.vhdLIBRARYIEEE;USEIEEE.STD_LOGIC_1164.ALL;ENTITYFEN2ISPORT(WR,LED_B:INSTD_LOGIC;X:INSTD_LOGIC_VECTOR(7DOWNTO0);W1,W2:OUTSTD_LOGIC_VECTOR(7DOWNTO0));ENDFEN2;ARCHITECTUREAOFFEN2ISBEGINPROCESS(LED_B,WR)BEGINIF(LED_B='0'ANDWR='0')THENW2<=X;ELSEW1<=X;ENDIF;ENDPROCESS;ENDA;3选1数据选择器单元VHDL源程序MUX3.vhdLIBRARYIEEE;USEIEEE.STD_LOGIC_1164.ALL;ENTITYMUX3ISPORT(ID:INSTD_LOGIC_VECTOR(7DOWNTO0);SW_B,CS:INSTD_LOGIC;N1,N2:INSTD_LOGIC_VECTOR(7DOWNTO0);EW:OUTSTD_LOGIC_VECTOR(7DOWNTO0));ENDMUX3;ARCHITECTUREAOFMUX3ISBEGINPROCESS(SW_B,CS)BEGINIF(SW_B='0')THENEW<=ID;ELSIF(CS='0')THENEW<=N2;ELSEEW<=N1;ENDIF;ENDPROCESS;ENDA;4选1数据选择器单元VHDL源程序MUX4.vhdLIBRARYIEEE;USEIEEE.STD_LOGIC_1164.ALL;ENTITYMUX4ISPORT(C,D,E,F:INSTD_LOGIC;X1,X2,X3,X4:INSTD_LOGIC_VECTOR(7DOWNTO0);W:outSTD_LOGIC_VECTOR(7DOWNTO0));ENDMUX4;ARCHITECTUREAOFMUX4ISSIGNALSEL:STD_LOGIC_VECTOR(3