计算机体系结构报告.docx
《计算机体系结构报告.docx》由会员分享，可在线阅读，更多相关《计算机体系结构报告.docx（26页珍藏版）》请在冰点文库上搜索。
计算机体系结构报告
中南大学
计算机体系结构
实验报告
学生姓名代巍
指导教师雷向东
学院信息科学与工程学院
专业班级信安1201班
学号0909121615
完成时间2014年11月20日
实验1对指令操作码进行霍夫曼编码
一、实验目的
了解和掌握指令编码的基本要求和基本原理
二、实验要求
使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。
与扩展操作码和等长编码进行比较。
问题描述以及问题分析：
我们举例说明此问题，例如：
有一组指令的操作码共分七类，它们出现概率如
下表所示：
P1P2P3P4P5P6P7
0.450.300.150.050.030.010.01
对此组指令进行HUFFMAN编码正如下图所示：
三、实验内容
因为各字符在信息中出现的频率是不同的，若根据字符出现的不同频率分配给不同长度的编码：
频繁出现的字符分配给较短的编码，不常出现的字符分配给较长的编码，且这种编码还具有“前缀特性”，那么这样的编码电文总长会最短，发送效率会最高，占用的空间会最少。
而哈弗曼编码就是这样一种编码，字符出现的频率与该程序中对应的权重。
首先将建立哈弗曼树，将权重最小的放在二叉树的最低端，将权重最大的放置在离根结点最近的位置，这样就可以使权重大的结点的编码较短，权重小的结点的编码较长。
实际上是建立一个表格，中间有结点的权重，父亲和孩子的信息。
建立好哈弗曼树之后，要使得哈弗曼的左子树的编码为0，右子树的编码为1。
可以通过这个来确定字符的哈弗曼编码。
四、实验原理
构造HUFFMAN树所要做的工作：
1、先对各指令操作码的出现概率进行排序，构造一个有序链表。
2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。
3、在对链表进行排序，链表是否只有一个节点，是则HUFFAN树构造完毕，否则继续做2的操作。
为此设计一个工作链表（链表的元素时类，此类的功能相当结构。
）、HUFFMAN树节点、HUFFMAN编码表节点
五、实验结果
输入的n为4，各节点的权重为23,34,54,65
六、源程序代码
#include
#include
#include
#include
#include
#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1
typedefstruct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*编码结构体*/
typedefstruct
{
intweight;
intparent;
intlchild;
intrchild;
intvalue;
}HNodeType;/*结点结构体*/
/*构造一颗哈夫曼树*/
voidHuffmanTree（HNodeTypeHuffNode[MAXNODE],intn）
{
/*i、j：
循环变量，m1、m2：
构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：
构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。
*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼树数组HuffNode[]中的结点*/
for（i=0;i<2*n-1;i++）
{
HuffNode[i].weight=0;//权值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//实际值，可根据情况替换为字母
}/*endfor*/
/*输入n个叶子结点的权值*/
for（i=0;i{
printf（"Pleaseinputweightofleafnode%d:
\n",i）;
scanf（"%d",&HuffNode[i].weight）;
}/*endfor*/
/*循环构造Huffman树*/
for（i=0;i{
m1=m2=MAXVALUE;/*m1、m2中存放两个无父结点且结点权值最小的两个结点*/
x1=x2=0;
/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/
for（j=0;j{
if（HuffNode[j].weight{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif（HuffNode[j].weight{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*设置找到的两个子结点x1、x2的父结点信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
printf（"x1.weightandx2.weightinround%d:
%d,%d\n",i+1,HuffNode[x1].weight,HuffNode[x2].weight）;/*用于测试*/
printf（"\n"）;
}/*endfor*/
/
intmain（void）
{
HNodeTypeHuffNode[MAXNODE];/*定义一个结点结构体数组*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/
inti,j,c,p,n;
charpp[100];
printf（"Pleaseinputn:
\n"）;
scanf（"%d",&n）;
HuffmanTree（HuffNode,n）;
for（i=0;i{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while（p!
=-1）/*父结点存在*/
{
if（HuffNode[p].lchild==c）
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求编码的低一位*/
c=p;
p=HuffNode[c].parent;/*设置下一循环条件*/
}/*endwhile*/
/*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
for（j=cd.start+1;j{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/
/*输出已保存好的所有存在编码的哈夫曼编码*/
for（i=0;i{
printf（"%d'sHuffmancodeis:
",i）;
for（j=HuffCode[i].start+1;j{
printf（"%d",HuffCode[i].bit[j]）;
}
printf（"start:
%d",HuffCode[i].start）;
printf（"\n"）;
}
}
实验2使用LRU方法更新Cache
一、实验目的
了解和掌握寄存器分配和内存分配的有关技术。
二、实验要求
1、用C语言实现最近最久未使用（LRU）置换算法。
2、了解内存分页管理策略
3、掌握调页策略
4、LRU调度算法D的模拟实现
三、实验内容
LRU置换算法是选择最近最久未使用的页面予以置换。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面时，选择现有页面中T值最大的，即最近最久没有访问的页面。
这是一个比较合理的置换算法。
Cache更新
结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的LRU置换算法是选择最近最久未使用的页面予以置换。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面时，选择现有页面中T值最大的，即最近最久没有访问的页面。
这是一个比较合理的置换算法。
四、实验原理
LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。
为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：
寄存器
为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3……R2R1R0当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。
此时，定时信号将每隔一定时间（例如100ms）将寄存器右移一位。
如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。
这里，把8个内存页面的序号分别定为1˜˜8。
由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。
栈
可利用一个特殊的栈来保存当前使用的各个页面的页面号。
每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。
因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。
五、实验结果
输入的数据为
六、源程序代码
#include
#include
#include
#include
#defineM4
#defineN12
#defineMyprintfprintf（"|---+---+---+---+---+---+---+---+---+---+---+---|\n"）/*表格控制*/
typedefstructPage
{
intnum;/*记录页面号*/
inttime;/*记录调入内存时间*/
}Page;/*页面逻辑结构，结构为方便算法实现设计*/
/*全局变量*/
Pagepage_in[M];/*内存单元数*/
intc[M][N];/*暂保存内存当前的状态：
缓冲区第M的位置在第N次调入时的数值*/
intqueue[100];/*记录调入队列*/
intK;/*调入队列计数变量*/
/*初始化内存单元、缓冲区*/
voidInit（Page*page_in,intc[M][N]）
{
inti,j;
for（i=0;i{
page_in[i].num=-1;
page_in[i].time=N-i-1;
}
for（i=0;ifor（j=0;jc[i][j]=-1;
}
/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
intGetMax（Page*page_in）
{
inti;
intmax=-1;
inttag=0;
for（i=0;i{
if（page_in[i].time>max）
{
max=page_in[i].time;
tag=i;
}
}
returntag;
}
/*判断页面是否已在内存中*/
intEquation（intfold,Page*page_in）
{
inti;
for（i=0;i{
if（fold==page_in[i].num）
returni;
}
return-1;
}
/*LRU核心部分*/
voidLru（intfold,Page*page_in）//把页面号为fold的页调入内存
{
inti;
intval;
val=Equation（fold,page_in）;
if（val>=0）//页面在内存中
{
page_in[val].time=0;//该页面的时间置零
for（i=0;iif（i!
=val）
page_in[i].time++;
}
else//页面不在内存中，从外部调入
{queue[++K]=fold;/*记录调入页面*/
val=GetMax（page_in）;//找到最近最久未使用的页面编号
page_in[val].num=fold;//调入
page_in[val].time=0;
for（i=0;iif（i!
=val）
page_in[i].time++;
}
}
/*主程序*/
intmain（）
{
inta[N]={1,1,2,4,3,5,2,1,6,7,1,3};
inti,j;
charjudge='n';//用于控制循环
while（judge=='n'）
{
srand（（int）time（0））;//产生随机数种子
printf（"待调入的页面号:
\n"）;
for（i=0;i{
a[i]=（int）（10.0*rand（）/（RAND_MAX+1.0）+1）;//产生随机数
printf（"%d",a[i]）;
}
printf（"\n"）;
K=-1;
Init（page_in,c）;//初始化内存单元、缓冲区
for（i=0;i{
Lru（a[i],page_in）;
c[0][i]=a[i];
//记录当前的内存单元中的页面
for（j=0;jc[j][i]=page_in[j].num;
}
//结果输出
printf（"内存状态为：
\n"）;
Myprintf;
for（j=0;jprintf（"|%2d",a[j]）;
printf（"|\n"）;
Myprintf;
for（i=0;i{
for（j=0;j{if（c[i][j]==-1）printf（"|"）;
//printf（"|%2c",32）;
else
printf（"|%2d",c[i][j]）;
}
printf（"|\n"）;
}
Myprintf;
printf（"\n调入队列为:
"）;
for（i=0;iprintf（"%3d",queue[i]）;
printf（"\n缺页次数为：
%6d\n缺页率：
%16.6f",K+1,（float）（K+1）/N）;
printf（"\nAreyouquit!
\ty\\n?
"）;
if（getche（）=='y'）
{judge='y';
}
else
{judge='n';
printf（"\n"）;
}
}
}
实验3字节多路通道运行机制
一、实验目的
通过模拟实现通道处理过程，掌握通道技术。
二、实验要求
通过上机用编程语言实现对计算机字节多路通道运行机制的模拟。
三、实验内容
结合数据结构的相关知识,编写通道处理过程模拟程序。
1、通道完成一次数据输入输出的过程需三步（如图一所示）：
（1）在用户程序中使用访管指令进入管理程序，由CPU通过管理程序组织一个通道程序，启动通道；
（2）通道处理机执行通道程序，完成指定的数据输入输出工作；
（3）通道程序结束后第二次调用管理程序对输入输出请求进行处理每完成一次输入输出工，CPU只需要两次调用管理程序，大大减少了对用户程序的打扰。
2通道的主要功能：
（1）接受CPU发来的指令，选择一台指定的外围设
（2）执行CPU为通道组织的通道程序
（3）管理外围设备的有关地址
（4）管理主存缓冲区的地址
（5）控制外围设备与主存缓冲区间数据交换的个数
（6）指定传送工作结束时要进行的操作
（7）检查外围设备的工作状态，是正常或故障
（8）在数据传输过程中完成必要的格式的变换
四、实验原理
字节通道是一种简单的共享通道，主要为多台低速或中速的外围设备服务。
它采用分时方式工作，依靠它与cpu之间的高速数据通路分时为多台设备服务。
如果通道上连接了多个外围设备，则此时通道上的各个设备轮流占用一个很短的时间片（通常小于100微秒）传输一个字节，或者说，不同的设备在他所分得的时间片内与通道在逻辑上建立传输连接，此方式也叫做字节交叉方式。
与此同时，它还允许一个设备一次占用通道比较长的时间传输一组数据。
或者说与通道的连接可以根据需要维持到一组数据全部传送完成，这也称为成组方式。
本次试验主要模拟的是字节交叉方式。
五、实验结果
传入的数据为
即：
字符串：
daiwei，love，computer
运行效果截图为：
六、源程序代码
Device.class
packagepassage;
publicclassDevice{
privateStringdatas;//设备/存储器中的数据
privateintdataLength;
publicDevice（）
{}
publicDevice（Stringdatas,ChannalManagercm）
{
this.setDatas（datas）;
this.dataLength=datas.length（）;
if（this.dataLength>cm.getMaxDevCap（））
cm.setMaxDevCap（this.dataLength）;
}
publicvoidsetDataLength（intdataLength）{
this.dataLength=dataLength;
}
publicintgetDataLength（）{
returndataLength;
}
publicvoidsetDatas（Stringdatas）{
this.datas=datas;
}
publicStringgetDatas（）{
returndatas;
}
}
ChannelManager.class
packagepassage;
importjava.util.ArrayList;
importjava.util.List;
publicclassChannalManagerimplementsRunnable{
privateStringinterrupt;//提示中断信号
privateintmaxDevCap=0;//所有设备的最大传输数据长度
privateListDevices;//所有外围设备
privateListmemory;//存储器
publicChannalManager（）
{
this.interrupt="none";
this.Devices=newArrayList（）;
this.Devices.add（newDevice（））;
this.Devices.add（newDevice（））;
this.Devices.add（newDevice（））;
this.memory=newArrayList（）;
this.memory.add（newDevice（"daiwei",this））;
this.memory.add（newDevice（"love",this））;
this.memory.add（newDevice（"computer",this））;
}
publicvoidsetInterrupt（Stringinterrupt）{
this.interrupt=interrupt;
}
publicStringgetInterrupt（）{
returninterrupt;
}
publicvoidsetMaxDevCap（intmaxDevCap）{
this.maxDevCap=maxDevCap;
}
publicintgetMaxDevCap（）{
returnmaxDevCap;
}
publicvoidsetDevices（Listdevices）{
Devices=devices;
}
publicListgetDevices（）{
returnDevices;
}
publicvoidprintDevice（）
{
for（Deviced:
this.Devices
升级会员 