计算机体系结构报告

1、中南大学计算机体系结构实验报告学生姓名 代巍 指导教师 雷向东 学 院 信息科学与工程学院 专业班级 信安1201班 学 号 0909121615 完成时间 2014年11月20日 实验 1 对指令操作码进行霍夫曼编码一、实验目的了解和掌握指令编码的基本要求和基本原理二、实验要求使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。问题描述以及问题分析：我们举例说明此问题，例如：有一组指令的操作码共分七类，它们出现概率如下表所示：P1 P2 P3 P4 P5 P6 P70.45 0.30 0.15 0.05 0.03

2、 0.01 0.01对此组指令进行 HUFFMAN 编码正如下图所示：三、实验内容因为各字符在信息中出现的频率是不同的，若根据字符出现的不同频率分配给不同长度的编码：频繁出现的字符分配给较短的编码，不常出现的字符分配给较长的编码，且这种编码还具有“前缀特性”，那么这样的编码电文总长会最短，发送效率会最高，占用的空间会最少。而哈弗曼编码就是这样一种编码，字符出现的频率与该程序中对应的权重。首先将建立哈弗曼树，将权重最小的放在二叉树的最低端，将权重最大的放置在离根结点最近的位置，这样就可以使权重大的结点的编码较短，权重小的结点的编码较长。实际上是建立一个表格，中间有结点的权重，父亲和孩子的信息。

3、建立好哈弗曼树之后，要使得哈弗曼的左子树的编码为0，右子树的编码为1。可以通过这个来确定字符的哈弗曼编码。 四、实验原理构造 HUFFMAN 树所要做的工作：1、先对各指令操作码的出现概率进行排序，构造一个有序链表。2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。3、在对链表进行排序，链表是否只有一个节点，是则 HUFFAN 树构造完毕，否则继续做 2 的操作。为此设计一个工作链表（链表的元素时类，此类的功能相当结构。）、HUFFMAN 树节点、HUFFMAN 编码表节点五、实验结果输入的n为4，各节点的权重为23,34,54,65六、源程序代码#i

4、nclude #include#include #include #include #define MAXBIT 100#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1 typedef struct int bitMAXBIT; int start; HCodeType; /* 编码结构体 */typedef struct int weight; int parent; int lchild; int rchild; int value; HNodeType; /* 结点结构体 */ /* 构造一颗哈夫曼树

5、 */void HuffmanTree (HNodeType HuffNodeMAXNODE, int n) /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值， x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼树数组 HuffNode 中的结点 */ for (i=0; i2*n-1; i+) HuffNodei.weight = 0;/权值 HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild

6、=-1; HuffNodei.value=i; /实际值，可根据情况替换为字母 /* end for */ /* 输入 n 个叶子结点的权值 */ for (i=0; in; i+) printf (Please input weight of leaf node %d: n, i); scanf (%d, &HuffNodei.weight); /* end for */ /* 循环构造 Huffman 树 */ for (i=0; in-1; i+) m1=m2=MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */ x1=x2=0; /* 找出所有结点中权值

7、最小、无父结点的两个结点，并合并之为一颗二叉树 */ for (j=0; jn+i; j+) if (HuffNodej.weight m1 & HuffNodej.parent=-1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight m2 & HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /* end for */ /* 设置找到的两个子结点 x1、x2 的父结点信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent

8、 = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.lchild = x1; HuffNoden+i.rchild = x2; printf (x1.weight and x2.weight in round %d: %d, %dn, i+1, HuffNodex1.weight, HuffNodex2.weight); /* 用于测试 */ printf (n); /* end for */ / int main(void) HNodeType HuffNodeMAXNODE; /*

9、定义一个结点结构体数组 */ HCodeType HuffCodeMAXLEAF, cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */ int i, j, c, p, n; char pp100; printf (Please input n:n); scanf (%d, &n); HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父结点存在 */ if (HuffNodep.lchild

10、 = c) cd.bitcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求编码的低一位 */ c=p; p=HuffNodec.parent; /* 设置下一循环条件 */ /* end while */ /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */ for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; /* end for */ /* 输出已保存好的所有存在编码的哈夫曼编码 */ for (i=0; in; i+)

11、 printf (%d s Huffman code is: , i); for (j=HuffCodei.start+1; j n; j+) printf (%d, HuffCodei.bitj); printf( start:%d,HuffCodei.start); printf (n); 实验 2 使用 LRU 方法更新 Cache一、实验目的了解和掌握寄存器分配和内存分配的有关技术。二、实验要求1、用C语言实现最近最久未使用（LRU）置换算法。2、了解内存分页管理策略3、掌握调页策略4、LRU调度算法D的模拟实现三、实验内容LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每

12、个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有页面中 T 值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。Cache 更新结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有页面中 T 值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。四、实验原理 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页

13、面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持： 寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为1

14、8。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。 五、实验结果输入的数据为六、源程序代码#include #include #include#include #define M 4 #define N 12#define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-|n)/*表格控制*/ typedef struct Page int

15、num;/*记录页面号*/ int time;/*记录调入内存时间*/ Page;/* 页面逻辑结构，结构为方便算法实现设计*/ /*全局变量*/ Page page_inM;/*内存单元数*/ int cMN;/*暂保存内存当前的状态：缓冲区 第M的位置在第N次调入时的数值*/ int queue100;/*记录调入队列*/ int K;/*调入队列计数变量*/ /*初始化内存单元、缓冲区*/ void Init(Page *page_in,int cMN) int i,j; for(i=0;iN;i+) page_ini.num=-1; page_ini.time=N-i-1; for(i

16、=0;iM;i+) for(j=0;jN;j+) cij=-1; /*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/ int GetMax(Page *page_in) int i; int max=-1; int tag=0; for(i=0;imax) max=page_ini.time; tag=i; return tag; /*判断页面是否已在内存中*/ int Equation(int fold,Page *page_in) int i; for(i=0;i=0) / 页面在内存中 page_inval.time=0; /该页面的时间置零for(i=0;iM;i+) /其

17、余的页面的时间都增加if (i!=val) page_ini.time+; else /页面不在内存中，从外部调入 queue+K=fold;/*记录调入页面*/ val=GetMax(page_in); /找到最近最久未使用的页面编号 page_inval.num=fold; /调入page_inval.time=0; for(i=0;iM;i+) if (i!=val) page_ini.time+; /*主程序*/ int main() int aN=1,1,2,4,3,5,2,1,6,7,1,3; int i,j; char judge = n;/用于控制循环while(judge =

18、 n) srand(int)time(0);/产生随机数种子 printf(待调入的页面号:n); for(i=0; iN; i+) ai = (int)(10.0*rand()/(RAND_MAX+1.0) + 1);/产生随机数 printf(%d ,ai); printf(n); K=-1; Init(page_in, c); / 初始化内存单元、缓冲区 for(i=0;iN;i+) Lru(ai,page_in); c0i=ai; /记录当前的内存单元中的页面 for(j=0;jM;j+) /将内存中的四个页面在第i次的情况记录下cji=page_inj.num; /结果输出 prin

19、tf(内存状态为：n); Myprintf; for(j=0;jN;j+) printf(|%2d ,aj); printf(|n); Myprintf; for(i=0;iM;i+) for(j=0;jN;j+) if(cij=-1) printf(| ); /printf(|%2c ,32); else printf(|%2d ,cij); printf(|n); Myprintf; printf(n调入队列为:); for(i=0;i cm.getMaxDevCap()cm.setMaxDevCap(this.dataLength);public void setDataLength(i

20、nt dataLength) this.dataLength = dataLength;public int getDataLength() return dataLength;public void setDatas(String datas) this.datas = datas;public String getDatas() return datas;ChannelManager.classpackage passage;import java.util.ArrayList;import java.util.List;public class ChannalManager implem

21、ents Runnable private String interrupt;/提示中断信号private int maxDevCap=0;/所有设备的最大传输数据长度private List Devices;/所有外围设备private List memory;/存储器public ChannalManager()errupt=none;this.Devices = new ArrayList();this.Devices.add(new Device();this.Devices.add(new Device();this.Devices.add(new Device();

22、this.memory = new ArrayList();this.memory.add(new Device(daiwei,this);this.memory.add(new Device(love,this);this.memory.add(new Device(computer,this);public void setInterrupt(String interrupt) errupt = interrupt;public String getInterrupt() return interrupt;public void setMaxDevCap(int maxDe

23、vCap) this.maxDevCap = maxDevCap;public int getMaxDevCap() return maxDevCap;public void setDevices(List devices) Devices = devices;public List getDevices() return Devices;public void printDevice()for(Device d : this.Devices)System.out.println(d.getDatas();Overridepublic void run() /通道处理器进行数据传送/ TODO

24、 Auto-generated method stubfor(int fence = 0 ;fence this.maxDevCap; fence+) for(int i = 0;i this.Devices.size() ; i+) if(fence this.memory.get(i).getDataLength() this.Devices.get(i).setDatas(this.memory.get(i).getDatas().substring(0, fence+1); printDevice(); printDevice(); errupt=finish;/传送完后发中断RunningCpu.classpackage passage;public class RunningCpu private ChannalManager channalMg;public RunningCpu()this.channalMg = new ChannalManager();public void setChannalMg(ChannalManager channalMg) this.channalMg = channalMg;public C