中南大学计算机体系结构实验报告

1、 计算机体系结构 课程设计 学院：信息科学与工程学院 专业班级: 指导老师: 学号: 姓名： 目录 实验1对指令操作码进行霍夫曼编码3 一、实验目得3 二、实验内容3 三、设计思路4 四、关键代码4 五、实验截图5 六、源代码5 实验2 使用LRU方法更新Cache8 一、实验目得8 二、实验内容8 三、设计思路9 四、程序截图9 五、实验代码9 实验总结16 参考文献16 实验1对指令操作码进行霍夫曼编码 一. 实验目得 了解与掌握指令编码得基本要求与基本原理 二、实验内容 1. 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后得编码结果 以及对指令码得长度进行评价。与扩展操作

2、码与等长编码进行比较。 2. 问题描述以及问题分析 举例说明此问题，例如： P1 P2 P3 P4 P5 P6 P7 0. 45 0、30 0、15 0、05 0、03 0、01 0. 01 有一组指令得操作码共分七类，它们出现槪率如 下表所示: 对此组指令进行HUFFMAN编码正如下图所示: 就后得到得HUFFMAN编码如下表所示: P1 P2 P3 P4 P5 P6 P7 0 10 110 1110 11110 111110 111111 灵短编码长度为: H=0. 45*1+0、 30*2+0 15*3+0. 05*4+0. 03*5+0、 01*6+0. 01*6=-1 95、 要对指

3、令得操作码进行HUFFMAN编码，只要根据指令得各类操作码得出现概率构造 HUFFMAN树再进行HUFFAM编码。此过程得难点构造HUFFMAN树，进行HUFFAM编 码只要对您所生成得HUFFMAN树进行中序遍历即可完成编码工作。 三、设计思路 观察上图，不难瞧出构造HUFFMAN树所要做得工作：1.先对各指令操作码得出现 概率进行排序，构造一个有序链表。2、再取出两个最小得槪率节点相加，生成一个生得节 点加入到链表中，同时从两表中删除此两个节点。3.在对链表进行排序，链表就是否只有一 个节点，就是則HUFFAN树构造完毕，否則继续做2得操作。为此设计一个工作链表（链表 得元素时类，此类得功

4、能相当结构。）、HUFFMAN树节点、HUFFMAN编码表节点。 四、关键代码 哈夫曼树重点在于如何排列权值大小不同得结点得顺序 /叶子结点个 /哈夫曼树得结点 private int leafNum; 数pr ivate HaffmanNode hnodes; 数组 /构造指定权值築合得哈夫爱 pub Iic HaffManCode(double wei ght) int n = we i ght . length;/n 个 叶 子 结 点this. leafNum = n; this、hnodes = new Haf fmanNode 2*n-1 ;/n个叶子结点得哈夫曼树共有2nT 个结

5、 点 for (int i=0; in; i+)/结点数组初始化有n个叶子结 点thisx hnodesi = new HaffmanNodeGweighti); for (int i=0; in-1; i+)/构造 nT 个2 度 结点，每循环一次，构造一个2度结点 double mini, min2; int x1, x2; mini = min2 = Integer% MAX_VALUE:/选择it小与次最小权值初值为 最大权值 x1 = x2 = -1; /记 录两 个 无 父母得最小 权值 结点下 标 for (int j=0; jn+i;j+) /查找两个无 父母得最小权值结点 i

6、f (hnodesj. v/eightmin1 x2 = x 1； mini = hnodes j 、v/e i ght; /mini记下最小 权值 xl = J； /x1记下it小权值结点得下 标 else if (hnodesj. weightmin2 x2 = j; /x2记下次斎小权值结点得下标 五、实验截图 Problems Javadoc 冏 Declaration 貝 Console 关 a X 舔罰凰迴|出E huffman Java Application D:javaJDKbinjavaw.exe (2015-11-5 下午7:2： 2的编码是：00 的的的的的的 是是杲是

7、是是 码码码码码码 编编编编编编 :010 :0110 :0111 ;1000 :1001 :101 S的编码杲：110 y的编码是：111 六、源代码 public class huffman privatb String str; public huffman(Str ing str) thiSs str=str; I /* *创建节点类 * param args */ class Node Node left; Node right; int data: char c; Str i ng code二”; *节点数组(字符串吳) * param args */ pub Iic void c

8、reatTree () /先去坤重复得字符串，若不存在将字符加在strRepeat中 String strRepeat=M for (int i=0;istr. length ();i+) char c二str. charAt(i); 判斷就是否存在 if (str Repeat. indexOf (c)=-1) 找到字符位置并返回字符所在得位置 strRepeat+=c; /统计字符出現得次戟并建立节点 Node nodes=new Node strRepeats length 0 ；/定义 了一个nodes数组 /存储节点得坐标值 for (int i=0; i1) sort (nodes

9、); Node node二new Node (); Node n1=nodes0: Node n2=nodes1: node、 data=n1. data+n2 data; node、 Ieft=n1; node、r ight=n2; /改变节点數组长度 Node nodes2=new Nodenodes、 length-1; for (int i=2;inodes. length;i +) nodes2i-2 = nodesi; 1 nodes2nodes2、Iength-1=node; nodes=nodes2; I Node root=nodes 0; pr intCode(root,”

10、); ) *统计字符出现得次数get方法 / private int getCount (String str,char c) int count = 0; for (int i=0; i lengthO ; i+) if(c=strcharAt (i) count+; 1 return count; * param nodes */ pub Iic void sort (Node nodes) for (int i=0;inodes、length;i +) for (int j=i+1;j c+、+node. data*得编吗就是: printCode(node、 left,code+“ +

11、0); printCode(node、 right,code+ *+1); 1 I pub Ii c static void ma in (String args) Str i ng str=add bate; huffman hf=new huffman(str); hf、creatTree (); 实验2使用LRU方法更新Cache 一、实验目得 了解与掌握奇存器分配与内存分配得有关技术。 二、实验内容 LRU置换算法就是选择最近最久未使用得页面予以置换。该算法賦予每个页面一个访问 字段，用来记录一个页面自上次被访问以来经历得时间T,当须淘汰一个页面时，选择现有页 面中T值最大得，即最近最

12、久没有访问得页面。这就是一个比较合理得置换算法。举例说明 此问题，例如：有一个CACHE采用纽相连映象方式。每组有四块，为了实现LRU置换算法, 在快表中为每块设置一个2位计数器。我们假设访问序列为“ 1,1,2, 4, 3, 5, 2,1,6, 7,1,3”。 在访问CACHE得过程中，块得装入，置换及命中时，具体情况如下表所示： 1 1 2 4 3 2 1 6 7 1 3 Cache 块 0 1 1 1 1 1 5 5 5 5 7 7 7 Cache 块 1 9 2 2 2 0 2 9 3 Cache 块 2 4 4 4 1 1 1 1 1 Cache 块 3 3 3 3 3 6 6 6

13、6 入 命 中 装 入 装 入 装 入 實 换 命 中 换 : 换 换 命 中 盘 三、设计思路 LRU置换算法就是选择置近最久未使用得页面予以置换。该算法赋予毎个页面一个访问 字段，用来记录一个页面自上次被访问以来经历得时间T,当须淘汰一个页面时，选择现有 页面中T值黃大得，即最近置久没有访问得页面。这就是一个比较合理得置换算法。 四、程序截图 勾I o | GJ llwwl Problems Jo 淆辎入第13个访问页面:| 隹瓦 访问序列 Cache块0 Cache 块 1 Cache块2 Cache 決 3 1 1 A 1 1 命中 2 1 奘入 4 1 2 4 3 1 2 3 55

14、2 4 3 羞唤 2 5 2 4 3 命中 1 5 1 3 述换 6 5 1 6 7 7 2 1 6 7 1 7 2 1 6 命中 五、实验代码 import java, awt. *; import java、 awt. event. *; import javax. swing. *; import javax. swing、 table. *; pub Iic class Iru extends Frame pub Ii c static void ma in (Str ing args) JFrame、 setDefaMtLookAndFeeDecorated心3 ; I ru I r

15、ue = new I ru(); I rue、lauchFrame (); JLabeI jlabel2; JTextField jtf2; JButton jb_input; JScrolI Pane jsp; JTable jt; DefaultTableModel dtm; static int /ist = 1, count = list - 1; int time1 = 0; int time2 = 0; int time3 = 0; int time4 = 0; pub Iic void lauchFrame () this、setLayout(nu11): this setBou

16、nds(100, 100, 540. 320); /this、setBackground (Co I or cyan): this. setVisible(true); j label2 = new JLabeI (请输入第” + list* 个访问页 而：”); jtf2 = new JTextFieldO ; jb_i nput = rww JButton(输入”); jlabel2 setBounds(20, 50, 140. 20); jtf2、setBounds (155, 50, 50, 20); jb_i nputx setBounds(240, 50, 60, 20); thi

17、s、add(jlabel2); this. add(jtf2); this、add(jb_input); this、add?/indowL istener (new Wi ndowAdapter 0 ( pub I ic void v/indowClosi ng (Wi ndowEvent e) System、ex/t(0); 1); jb_ i nput addAct ionL i stenerInputAct i onL i stener (); Object title = 访问序列笃”Cache块(T, “Cache块廿,Cache块2“，“Cache块3“，“状态 dtm = rww

18、 Def au I tTab I eMode I (t i 11 e. 0); jt = new JTable (dtm); jsp = new JScrolIPane(jt); jsp、setBounds (50, 80, 440, 197); t ime4+; jtf2、setText (”)； jlabel2、setText (“请输入第+ I ist + 个*方 问页 而：“)； else /要访问得页而不在cache块中 dtm. addRow(new Ob ject jtf2、 getText () jt、 getValueAt (/sL3 1). jtf2、getTextO,二

19、二装入); time1+; time2 = 0; time3+; t ime4+; coud; jtf2、setText (”“)； jlabel2、setText(请输入第+ Iist十个f方问 页而：”)； break: case 2: /cache块中荽入两个页面绢请况 if (jtf2、getText()、equaI s (jt、getValueAt (/sL3. 1) /要访问彳寻页 而刚好在cacheO中 dtm、addRow(rww Ob ject jtf2、getText () jt、getValueAt (/s卜3 1) 企 getValueAt(/sL3, 2),”命中“)

20、; timel =0; time2+; time3+; t ime4+; jtf2、setText (”)； jlabel2、setText (”请输入第” + fist + 个 f方 问页 面：”)； else if (jtf2、getText ()、equaIs (jt、getValueAt(/,sL3 2) /要访 问得页面刚好衣cache 1中 dtm、addRow(no Object jtf2、getText (), jt、getValueAt (1), 也 getValueAt(/sL3, 2), 二 ”命中T)； time1+; time2 = 0; time3+; t ime4

21、+; jtf2 setText (”“)； jlabel2 setText(请输入第” + fist + 个f方问页而：”)； else /要访问得页面不在cache块中 dtm、addRow(rwObject jtf2、getText (), jtgetValueAt(/sL3. 1), jt getValueAt(/sL3. 2), jtf2、getText(), ”，裟入); t ime1+; time2+; time3 =0; t ime4+; jtf2、setText (”)； jlabel2、setText(请输入第+ Iist + 个f方问页而：“)； break: case 3

22、:/cache块中袋入三个页面彳寻情况 if (jtf2、getText()、equals(jt getValueAt (/s卜3. 1) /要访问彳孑页 而测好在cacheO中 dtm、addRow(rww Object jtf2、getText (), jt、getValueAt (/sL3. 1), jt getValueAt(/sL3, 2), jt、getValueAt(/,st-3, 3), “，”命中); timel = 0; time2+; time3+; t ime4+; jtf2、setText (”“)； jlabel2、setText命入第+ list个彳方问页而：”)

23、； else if(jtf2、getText()、equals(jt、getValueAt(/,sL3, 2) /要访 问得页面刚好在cachel中 dtm.addRow (now Object jtf2 getText (), jt、getValueAt (/s 卜 3. 1), jt getValueAt (/s 卜 3, 2), jt、getVa I ueAt (/,sL3, 3),“命中); time2 =0; time3+; t ime4+; jtf2 setText (“)； jlabel2、setText(”，帝$命入第” + Iist个f方问页而：“)； else if(jtf

24、2 getText()、equals(jt、getValueAt(/,sL3, 3) /要访 问得页面刚好在cache2中 dtm. addRow(nwObject jtf2 getText (). jt、getValueAt (/s3. 1), getValueAt (/s3, 2), jt、getVa I ueAt (/,s3, 3), ”命中); time1+; time2+; time3 = 0; t i me4*+; jtf2、setText(”“)； jlabel2 setText(请输入第“ + Iist + 个*方问页而：“)； else /要访问得页面不在cache块中 dt

25、m、addRow(new Ob ject jtf2、getText (), jt、getValueAt(/sL3 1), jt、getValueAt (/sL3 2). jt、getValueAt (/st-3, 3), jtf2、getText 01 “装入); time1+; time2+; time3+; time4 = 0; coud; jtf2x setText (”)； jlabel2 setText(请输入第+ list + 个访问页面：); break; 1 else /四个cache块都裟满得情况 if (jtf2、getText() x equals(jtx getValu

26、eAt (/st*-3, 1) /要访问得页面刚好 在cacheO中 dtm、addRow (newObject jtf2s getText (), jt. getVa lueAt (/st-3, 1), jt、 getVaIueAt(/istr3t 2), jt、getVaIueAt (./ist-3, 3), jt、getVaIueAt (/ist-3, 4),命中); System、out. pr intln(1); time1 = 0; time2+; t ime3+; time4+; jtf2、setText (”); j label 2 setText (请输入第+ list +

27、个访问页面：“)； )else if (jtf2x getText () x equals(jt、getVaIueAt (/st-3, 2) /要访问得 页面刚好在cachel中 dtm. addRow (new Object jtf2 getText (), jt、getVa I ueAt (/st3, 1)f jt、 getVaIueAt(/istr3. 2), jt、getVaIueAt(/st-3, 3), jts getVaIueAt(/st-3, 4),命中); System、out. printIn(2); time1+; time2 = 0; t ime3+; t ime4+;

28、 jtf2. setText (); jlabel2x setText(请输入第+ list + 个访问页面：“); )else if(jtf2、getText() x equals(jt getVaIueAt(3) /要访问得 页面刚好在cache2中 dtm、addRow (new Object jtf2 getText (), jt、getVa I ueAt (/st-3, 1)t jt、 getVa I ueAt (I istr3, 2)t jt、getVa I ueAt (/fr-3, 3), jt% getVa I ueAt (/ Zt-3, 4),命中); System、out. printIn(3); t ime1+;