计算机体系结构报告Word格式文档下载.docx
《计算机体系结构报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《计算机体系结构报告Word格式文档下载.docx（26页珍藏版）》请在冰点文库上搜索。
#include<
stdio.h>
#include<
stdlib.h>
malloc.h>
string.h>
conio.h>
#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个叶子结点的权值*/
n;
printf（"
Pleaseinputweightofleafnode%d:
\n"
i）;
scanf（"
%d"
&
HuffNode[i].weight）;
/*循环构造Huffman树*/
n-1;
m1=m2=MAXVALUE;
/*m1、m2中存放两个无父结点且结点权值最小的两个结点*/
x1=x2=0;
/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/
for（j=0;
j<
n+i;
j++）
if（HuffNode[j].weight<
m1&
&
HuffNode[j].parent==-1）
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif（HuffNode[j].weight<
m2&
m2=HuffNode[j].weight;
x2=j;
/*设置找到的两个子结点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;
x1.weightandx2.weightinround%d:
%d,%d\n"
i+1,HuffNode[x1].weight,HuffNode[x2].weight）;
/*用于测试*/
\n"
）;
/
intmain（void）
HNodeTypeHuffNode[MAXNODE];
/*定义一个结点结构体数组*/
HCodeTypeHuffCode[MAXLEAF],cd;
/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/
inti,j,c,p,n;
charpp[100];
Pleaseinputn:
n）;
HuffmanTree（HuffNode,n）;
i<
n;
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;
{HuffCode[i].bit[j]=cd.bit[j];
}
HuffCode[i].start=cd.start;
/*输出已保存好的所有存在编码的哈夫曼编码*/
%d'
sHuffmancodeis:
"
for（j=HuffCode[i].start+1;
j<
HuffCode[i].bit[j]）;
printf（"
start:
HuffCode[i].start）;
实验2使用LRU方法更新Cache
了解和掌握寄存器分配和内存分配的有关技术。
1、用C语言实现最近最久未使用（LRU）置换算法。
2、了解内存分页管理策略
3、掌握调页策略
4、LRU调度算法D的模拟实现
LRU置换算法是选择最近最久未使用的页面予以置换。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面时，选择现有页面中T值最大的，即最近最久没有访问的页面。
这是一个比较合理的置换算法。
Cache更新
结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的LRU置换算法是选择最近最久未使用的页面予以置换。
LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。
为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：
寄存器
为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3……R2R1R0当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。
此时，定时信号将每隔一定时间（例如100ms）将寄存器右移一位。
如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。
这里，把8个内存页面的序号分别定为1˜˜8。
由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。
栈
可利用一个特殊的栈来保存当前使用的各个页面的页面号。
每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。
因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。
输入的数据为
time.h>
#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<
N;
i++）
{
page_in[i].num=-1;
page_in[i].time=N-i-1;
}
M;
for（j=0;
j<
j++）
c[i][j]=-1;
}
/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
intGetMax（Page*page_in）
inti;
intmax=-1;
inttag=0;
if（page_in[i].time>
max）
{
max=page_in[i].time;
tag=i;
}
returntag;
/*判断页面是否已在内存中*/
intEquation（intfold,Page*page_in）
if（fold==page_in[i].num）
returni;
return-1;
/*LRU核心部分*/
voidLru（intfold,Page*page_in）//把页面号为fold的页调入内存
intval;
val=Equation（fold,page_in）;
if（val>
=0）//页面在内存中
page_in[val].time=0;
//该页面的时间置零
for（i=0;
i++）//其余的页面的时间都增加
if（i!
=val）
page_in[i].time++;
else//页面不在内存中，从外部调入
{queue[++K]=fold;
/*记录调入页面*/
val=GetMax（page_in）;
//找到最近最久未使用的页面编号
page_in[val].num=fold;
//调入
/*主程序*/
intmain（）
inta[N]={1,1,2,4,3,5,2,1,6,7,1,3};
charjudge='
n'
;
//用于控制循环
while（judge=='
）
srand（（int）time（0））;
//产生随机数种子
printf（"
待调入的页面号:
a[i]=（int）（10.0*rand（）/（RAND_MAX+1.0）+1）;
//产生随机数
%d"
a[i]）;
K=-1;
Init（page_in,c）;
//初始化内存单元、缓冲区
Lru（a[i],page_in）;
c[0][i]=a[i];
//记录当前的内存单元中的页面
j++）//将内存中的四个页面在第i次的情况记录下
c[j][i]=page_in[j].num;
//结果输出
内存状态为：
Myprintf;
|%2d"
a[j]）;
|\n"
{
for（j=0;
{if（c[i][j]==-1）printf（"
|"
//printf（"
|%2c"
32）;
else
printf（"
c[i][j]）;
}
\n调入队列为:
"
K+1;
%3d"
queue[i]）;
\n缺页次数为：
%6d\n缺页率：
%16.6f"
K+1,（float）（K+1）/N）;
\nAreyouquit!
\ty\\n?
if（getche（）=='
y'
{judge='
}
else
实验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
importjava.util.ArrayList;
importjava.util.List;
publicclassChannalManagerimplementsRunnable{
privateStringinterrupt;
//提示中断信号
privateintmaxDevCap=0;
//所有设备的最大传输数据长度
privateList<
Device>
Devices;
//所有外围设备
memory;
//存储器
publicChannalManager（）
this.interrupt="
none"
this.Devices=newArrayList<
（）;
this.Devices.add（newDevice（））;
this.memory=newArrayList<
this.memory.add（newDevice（"
daiwei"
this））;
love"
computer"
publicvoidsetInterrupt（Stringinterrupt）{
this.interrupt=interrupt;
publicStringgetInterrupt（）{
returninterrupt;
publicvoidsetMaxDevCap（intmaxDevCap）{
this.maxDevCap=maxDevCap;
publicintgetMaxDevCap（）{
returnmaxDevCap;
publicvoidsetDevices（List<
devices）{
Devices=devices;
publicList<
getDevices（）{
returnDevices;
publicvoidprintDevice（）
for（Deviced:
this.Devices
升级会员 