一、实验目的
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
四、源程序结构分析
1.程序结构
程序共有以下九个部分:
int findSpace(void);//查找是否有空闲内存
int findExist(int curpage);//查找内存中是否有该页面
int findReplace(void);//查找应予置换的页面
void display(void);//显示
void FIFO(void);//FIFO算法
void LRU(void);//LRU算法
void OPT(void);//OPT算法;
void BlockClear(void);//BLOCK清空,以便用另一种方法重新演示
int main() //主程序
2.源程序代码
#include <iostream.h>
#define Bsize 3
#define Psize 20
struct pageInfor
{
int content;//页面号
int timer;//被访问标记
};
class PRA
{
public:
PRA(void);
int findSpace(void);//查找是否有空闲内存
int findExist(int curpage);//查找内存中是否有该页面
int findReplace(void);//查找应予置换的页面
void display(void);//显示
void FIFO(void);//FIFO算法
void LRU(void);//LRU算法
void Optimal(void);//OPTIMAL算法
void BlockClear(void);//BLOCK恢复
pageInfor * block;//物理块
pageInfor * page;//页面号串
private:
};
PRA::PRA(void)
{
int QString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
block = new pageInfor[Bsize];
for(int i=0; i<Bsize
}
void PRA::Optimal(void)
{
int exist,space,position ;
for(int i=0; i<Psize; i++)
{
{
position = findReplace();
block[position] = page[i];
display();
}
}
for(int j=0; j<Bsize; j++)
block[j].timer++;//BLOCK中所有页面TIMER++
}
}
void PRA::BlockClear(void)
{
for(int i=0; i<Bsize; i++)
{
block[i].content = -1;
block[i].timer = 0;
}
}
void main(void)
{
cout<<"|----------页 面 置 换 算 法----------|"<<endl;
cout<<"|---power by wangxinchuang(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;
int select;
PRA test;
while(select)
{
cin>>select;
switch(select)
{
case 0:
break;
case 1:
cout<<"Optimal算法结果如下:"<<endl;
test.Optimal();
test.BlockClear();
cout<<"----------------------"<<endl;
break;
case 2:
cout<<"FIFO算法结果如下:"<<endl;
test.FIFO();
test.BlockClear();
cout<<"----------------------"<<endl;
break;
case 3:
cout<<"LRU算法结果如下:"<<endl;
test.LRU();
test.BlockClear();
cout<<"----------------------"<<endl;
break;
default:
cout<<"请输入正确功能号"<<endl;
break;
}
}
}
五、实验结果
1运行后的初始界面
2 opt算法 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)。
(4) 如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则,系统处于不安全状态。
三、 实验代码:
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#define False 0
#define True 1
int Max[100][100]={0};//各进程所需各类资源的最大需求
int Avaliable[100]={0};//系统可用资源
char name[100]={0};//资源的名称
int Allocation[100][100]={0};//系统已分配资源
int Need[100][100]={0};//还需要资源
int Request[100]={0};//请求资源向量
int temp[100]={0};//存放安全序列
int Work[100]={0};//存放系统可提供资源
int p[100]={0};
int q[100][100]={0};
int z[100][100]={0};
int M=100;//作业的最大数为100
int N=100;//资源的最大数为100
int gg=1;
void showdata()//显示资源矩阵
{
int i,j;
cout<<endl<<"此时刻的资源分配情况为:"<<endl;
cout<<" Max Allocation Need Avaliable"<<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、结构定义
const int MAX=1000; //空表的表项最大值
const int MAX1=2048; //内存的字节数
typedef class memoryroom{
private:
bool isfull; //这个字节是否可用
char byte[9]; //这个字节存放的数据
}MEMORY;
//分区表的数据结构!!
typedef class table{
private:
bool isuse; //该表项是否可用
int startaddress; //在内存中的起始地址
int size; //连续的大小
}TABLE;
3、算法描述
/*在空分区中查找合适的内存空间 */
bool procInputMemory(TABLE *mt,int procsize,MROOM *memory)
{ int i;
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);
return true;
}
if(i==MAX)
return false;
}
////////////////////////////////
/*对内存的碎片整理和对表项的改变*/
void memoryRepeat(MROOM *memory,TABLE *em)
{ int i,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 (Library Parameterized Modules)参数化的模块库,可构成如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语言实现之,然后将它创建为一个元件符号,供顶层电路调用。
图3 T1、T2、T3、T4与CLR、Q之间的时序关系图
如果系统的时钟控制信号(即工作脉冲P)是在T1、T2、T3或T4的中间产生,且上升沿有效,则它产生方法是:先将Q取反,再和节拍脉冲信号Ti相“与”得到。如图4所示。
图4 时钟控制信号的形成方法
5. 微程序流程图
根据模型机的数据通路图(图1)以及所有指令在CISC模型机中的操作过程,画出所有机器指令的微程序流程图,如图5所示。图中每个框为一个CPU周期(包含T1~T4共4个节拍脉冲周期)对应于一条微指令。框中上面的十六进制数表示的是当前微指令在控制存储器中的微地址;框中下面的十六进制数表示的是当前微指令的后续微坡地。在编写微指令时,图中的菱形框从属于它上面的方框。
图5 CISC模型机中所有机器指令的微程序流程
6. 汇编语言源程序
算法思想为:采用R0寄存器存放从开关输入的任意一个整数,R1存放准备参加累加运算的奇数,R2存放累加的和,用一个循环程序实现如下:
五、模型机的各单元VHDL源程序
------------------------ALU的VHDL源程序ALU.vhd --------------------------------
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
USE IEEE.STD_LOGIC_ARITH.ALL;
USE IEEE.STD_LOGIC_UNSIGNED.all;
ENTITY ALU IS
PORT(
A: IN STD_LOGIC_VECTOR(7 DOWNTO 0);
B: IN STD_LOGIC_VECTOR(7 DOWNTO 0);
S1,S0: IN STD_LOGIC;
BCDOUT: OUT STD_LOGIC_VECTOR(7 DOWNTO 0) ;
CY,ZI: OUT STD_LOGIC
);
END ALU;
ARCHITECTURE A OF ALU IS
SIGNAL AA,BB,TEMP:STD_LOGIC_VECTOR(8 DOWNTO 0);
BEGIN
PROCESS(S1,S0)
BEGIN
IF(S1='0' AND S0='0') THEN --ADD
AA<='0'&A;
BB<='0'&B;
TEMP<=AA+BB;
BCDOUT<=TEMP(7 DOWNTO 0);
CY<=TEMP(8);
IF (TEMP="100000000") THEN
ZI<='1';
ELSE
ZI<='0';
END IF;
ELSIF(S1='0' AND S0='1') THEN --CMP(SUB)
BCDOUT<=A-B;
IF(A<B) THEN
CY<='1';
ZI<='0';
ELSIF(A=B) THEN
CY<='0';
ZI<='1';
ELSE
CY<='0';
ZI<='0';
END IF;
ELSIF(S1='1' AND S0='0') THEN --INC
AA<='0'&A;
TEMP<=A+1;
BCDOUT<=TEMP(7 DOWNTO 0);
CY<=TEMP(8);
IF (TEMP="100000000") THEN
ZI<='1';
ELSE
ZI<='0';
END IF;
ELSE
BCDOUT<="00000000" ;
CY<='0';
ZI<='0';
END IF;
END PROCESS;
END A;
-------------------状态条件寄存器的VHDL源程序LS74.vhd -----------
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
ENTITY LS74 IS
PORT(
LDFR: IN STD_LOGIC;
CY,ZI: IN STD_LOGIC;
FC,FZ: OUT STD_LOGIC
);
END LS74;
ARCHITECTURE A OF LS74 IS
BEGIN
PROCESS(LDFR)
BEGIN
IF(LDFR'EVENT AND LDFR='1') THEN
FC<=CY;
FZ<=ZI;
END IF;
END PROCESS;
END A;
--------------LS273单元设计的VHDL语言程序------------------------
-- 8位数据寄存器的VHDL源程序LS273.vhd
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
ENTITY LS273 IS
PORT(
D: IN STD_LOGIC_VECTOR(7 DOWNTO 0);
CLK: IN STD_LOGIC;
O: OUT STD_LOGIC_VECTOR(7 DOWNTO 0)
);
END LS273;
ARCHITECTURE A OF LS273 IS
BEGIN
PROCESS(CLK)
BEGIN
IF(CLK'EVENT AND CLK='1') THEN
O<=D;
END IF;
END PROCESS;
END A;
-------------------- 1:2分配器的VHDL源程序FEN2.vhd ------------------
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
ENTITY FEN2 IS
PORT(
WR,LED_B:IN STD_LOGIC;
X:IN STD_LOGIC_VECTOR(7 DOWNTO 0);
W1,W2:OUT STD_LOGIC_VECTOR(7 DOWNTO 0)
);
END FEN2;
ARCHITECTURE A OF FEN2 IS
BEGIN
PROCESS(LED_B,WR)
BEGIN
IF(LED_B='0' AND WR='0') THEN
W2<=X;
ELSE
W1<=X;
END IF;
END PROCESS;
END A;
-------------3选1数据选择器单元VHDL源程序MUX3.vhd ---------------------
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
ENTITY MUX3 IS
PORT(
ID:IN STD_LOGIC_VECTOR(7 DOWNTO 0);
SW_B,CS:IN STD_LOGIC;
N1,N2:IN STD_LOGIC_VECTOR(7 DOWNTO 0);
EW:OUT STD_LOGIC_VECTOR(7 DOWNTO 0)
);
END MUX3;
ARCHITECTURE A OF MUX3 IS
BEGIN
PROCESS(SW_B,CS)
BEGIN
IF(SW_B='0') THEN
EW<=ID;
ELSIF(CS='0')THEN
EW<=N2;
ELSE
EW<=N1;
END IF;
END PROCESS;
END A;
------------------4选1数据选择器单元VHDL源程序MUX4.vhd -----------------
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
ENTITY MUX4 IS
PORT(
C,D,E,F: IN STD_LOGIC;
X1,X2,X3,X4: IN STD_LOGIC_VECTOR(7 DOWNTO 0);
W: out STD_LOGIC_VECTOR(7 DOWNTO 0)
);
END MUX4;
ARCHITECTURE A OF MUX4 IS
SIGNAL SEL: STD_LOGIC_VECTOR(3 DOWNTO 0);
BEGIN
SEL<=F&E&D&C;
一、 实验目的
1. 设计实现ADC0809采样的状态机电路;
2. 掌握状态机的Verilog设计方法;
3. 学习设计仿真工具的使用方法;
4. 学习层次化设计方法;
二、 实验内容
1. 设计实现ADC0809采样电路,启动信号START高电平开始AD转换,此时转换结束标志变为0,当EOC由低变为高,表示转会结束,此时可以置OE为1,ADC输出转换结果。ADC0809控制时序如下:
三、 实验原理
ADC0708是CMOS的8位A/D转化器,片内有8路模拟开关,可控制8个模拟量中的一个进入转换其中。转换时间是100us,含锁存控制的8路多路开关,输出有三态缓冲器控制,单5V电源供电。
START是转换启动信号,高电平有效;ALE是3位通道选择地址(ADDC、ADDB、ADDA)信号的锁存信号。但模拟量送至某一输入端时,由3位地址信号选择,而地址信号由ALE锁存;EOC是转换情况状态信号,当启动转换约100us后,EOC产生一个负脉冲,以示转换结束;在EOC的上升沿后,若使输出信号OE为高电平,则控制打开的三态缓冲器,把转换好的8位数据结果输至数据总线。至此,ADC0809的一次转换结束。
【程序源代码】(加注释)
module ADC0809(CLK,ALE,EOC,RST,ST,OE,DIN,q);
input CLK,EOC,RST;
input[7:0] DIN; //定义8为的输出DIN
output[7:0] q;
output ALE,OE,ST;
reg[7:0] q;
parameter s0=0,s1=1,s2=2,s3=3,s4=4; //使用参数定义关键词parameter
reg[2:0] c_st,n_st; //定义变量为寄存器变量
reg ALE,OE,ST,LOCK;
always @(posedge CLK) //CLK为上升沿敏感信号
begin
if(RST)
c_st=s0;
else
c_st=n_st;
end
always @(c_st or EOC)
begin
case(c_st)
s0:begin
ALE=0;OE=0;ST=0;LOCK=0;
n_st<=s1;
end
s1:begin
ALE=1;ST=1;OE=0;LOCK=0;
n_st<=s2;
end
s2:begin
ALE=0;ST=0;OE=0;LOCK=0;
if(EOC)
n_st<=s3;
else
n_st<=s2;
end
s3:begin
ALE=0;OE=1;ST=0;LOCK=0;
n_st<=s4; //使用了非阻塞赋值语句
end
s4:begin
ALE=0;OE=0;ST=0;LOCK=1;
n_st<=s0;
end
default n_st<=s0;
endcase
end
always @(posedge LOCK)
begin
if(LOCK)
q<=DIN;
end
endmodule
四、仿真和测试结果