中南大学计算机系统体系结构题目：计算机系统体系结构姓名：班级：学号：日期：2014年11月20日1、实验一：对指令操作码进行霍夫曼编码一、实验目的1、了解和掌握指令编码的基本要求和基本原理。
二、实验内容1、使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。
与扩展操作码和等长编码进行比较。
问题描述以及问题分析：我们举例说明此问题，例如：最短编码长度为：H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+0.01*6=-1.95.要对指令的操作码进行 HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFMAN 树再进行 HUFFAM 编码。
此过程的难点构造 HUFFMAN 树，进行 HUFFAM 编码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。
三、关键代码及部分注释哈夫曼树重点在于如何排列权值大小不同的结点的顺序private int leafNum; //叶子结点个数private HaffmanNode[] hnodes; //哈夫曼树的结点数组public HaffManCode(double[] weight) //构造指定权值集合的哈夫曼树{ int n = weight.length; //n个叶子结点this.leafNum = n;this.hnodes = new HaffmanNode[2*n-1]; //n个叶子结点的哈夫曼树共有2n-1个结点for(int i=0; i<n; i++) //结点数组初始化有n个叶子结点this.hnodes[i] = new HaffmanNode(weight[i]);for(int i=0; i<n-1; i++) //构造n-1个2度结点，每循环一次，构造一个2度结点{double min1, min2;int x1, x2;min1 = min2 = Integer.MAX_VALUE; //选择最小和次最小权值，初值为最大权值 x1 = x2 = -1; //记录两个无父母的最小权值结点下标for(int j=0;j<n+i; j++) //查找两个无父母的最小权值结点{ if(hnodes[j].weight<min1 && hnodes[j].parent==-1){ min2 = min1;x2 = x1;min1 = hnodes[j].weight; //min1记下最小权值x1 = j; //x1记下最小权值结点的下标}else if(hnodes[j].weight<min2 && hnodes[j].parent==-1){min2 = hnodes[j].weight;x2 = j; //x2记下次最小权值结点的下标}}四、实验结果五、实验源代码1、HaffmanNode.javapackage feng;class HaffmanNode //哈夫曼树的结点类{ double weight; //权值int parent,left,right; //父母结点和左右孩子下标public HaffmanNode(double weight){this.weight = weight;this.parent=-1;this.left=-1;this.right=-1;}public HaffmanNode(){this(0);}public String toString(){return this.weight+" "+this.parent+" "+this.left+" "+this.right; }}2、HaffManCode.javapackage feng;public class HaffManCode{private int leafNum; //叶子结点个数private HaffmanNode[] hnodes; //哈夫曼树的结点数组public HaffManCode(double[] weight) //构造指定权值集合的哈夫曼树{int n = weight.length; //n个叶子结点this.leafNum = n;this.hnodes = new HaffmanNode[2*n-1]; //n个叶子结点的哈夫曼树共有2n-1个结点for(int i=0; i<n; i++) //结点数组初始化有n个叶子结点this.hnodes[i] = new HaffmanNode(weight[i]);for(int i=0; i<n-1; i++) //构造n-1个2度结点，每循环一次，构造一个2度结点 {double min1, min2;int x1, x2;min1 = min2 = Integer.MAX_VALUE; //选择最小和次最小权值，初值为最大权值x1 = x2 = -1; //记录两个无父母的最小权值结点下标for(int j=0; j<n+i; j++) //查找两个无父母的最小权值结点{if(hnodes[j].weight<min1 && hnodes[j].parent==-1){min2 = min1;x2 = x1;min1 = hnodes[j].weight; //min1记下最小权值x1 = j; //x1记下最小权值结点的下标}else if(hnodes[j].weight<min2 && hnodes[j].parent==-1){min2 = hnodes[j].weight;x2 = j; //x2记下次最小权值结点的下标}}hnodes[x1].parent = n+i; //将找出的两棵权值最小的子树合并为一棵子树hnodes[x2].parent = n+i;this.hnodes[n+i] = new HaffmanNode();hnodes[n+i].weight = hnodes[x1].weight+hnodes[x2].weight;hnodes[n+i].left = x1;hnodes[n+i].right = x2;}}public String toString(){String str="";for (int i=0; i<this.hnodes.length && hnodes[i]!=null; i++)str += " "+i+" "+this.hnodes[i].toString()+"\n";return str;}String[] code1 = null;public String[] haffmanCode() //返回当前哈夫曼树的哈夫曼编码{code1 = new String[this.leafNum];String[] code = new String[this.leafNum];for(int i=0; i<this.leafNum; i++) //求n个叶子结点的哈夫曼编码{code[i]="";int child = i;int parent = hnodes[child].parent;while (parent!=-1) //由叶结点向上直到根结点循环{if(hnodes[parent].left==child) {code[i]="0"+code[i]; //左孩子结点编码为0code1[i] = code[i];}else {code[i]="1"+code[i]; //右孩子结点编码为1code1[i] = code[i];}child = parent;parent = hnodes[child].parent;}}return code;}public double shortestLong() {int lng;double weight, shortestlong = 0;for(int i=0; i<this.leafNum; i++) {lng = code1[i].length();weight = hnodes[i].weight;shortestlong = shortestlong + lng*weight;}return shortestlong;}public static void main(String[] args){//int[] weight={186, 64, 13, 22, 32, 103, 21, 15, 47, 57, 1, 5, 32, 20}; //指定权值集合double[] weight={0.1, 0.2, 0.1, 0.3, 0.1, 0.2};HaffManCode htree = new HaffManCode(weight);System.out.println("指令权值父指左子右子\n"+htree.toString());String[] code = htree.haffmanCode();System.out.println("哈夫曼编码:");for (int i=0; i<code.length; i++) {System.out.println(code[i]);}System.out.println("最短编码长度为:" + htree.shortestLong());}}2、实验二：使用LRU方法更新Cache一．实验目的：1、了解和掌握寄存器分配和内存分配的有关技术。
二、实验内容：1、结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的Cache更新。
LRU置换算法是选择最近最久未使用的页面予以置换。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面时，选择现有页面中T 值最大的，即最近最久没有访问的页面。
这是一个比较合理的置换算法。
举例说明此问题，例如：有一个CACHE采用组相连映象方式。
每组有四块，为了实现LRU置换算法，在快表中为每块设置一个2位计数器。
我们假设访问序列为“1,1,2,4,3,5,2,1,6,7,1,3”。
在访问CACHE的过程中，块的装入，置换及命中时，具体情况如下表所示：三、关键代码1、程序分情况讨论了，当一个cache装满的情况下，2个，3个4个装满的情况下，当输入访问序列的时候，自动进行识别，并进行相应的处理，这个就是当四个块都被装满的情况else {//四个cache块都装满的情况if(jtf2.getText().equals(jt.getValueAt(list-3, 1))) {//要访问的页面刚好在cache0中dtm.addRow(new Object[]{jtf2.getText(),jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2),jt.getValueAt(list-3, 3),jt.getValueAt(list-3, 4), "命中"});System.out.println(1);time1 = 0;time2++;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}四、实验结果：如果按照访问序列你“1，2,3,4,5,4,3，2,1”输入，结果如图：五、源代码及LRU算法1、源代码及注释：package keshe;import java.awt.*;import java.awt.event.*;import javax.swing.*;import javax.swing.table.*;import jdk.nashorn.internal.scripts.JO;public class LRUCache extends Frame {public static void main(String[] args) {JFrame.setDefaultLookAndFeelDecorated(true);LRUCache lruc = new LRUCache();uchFrame();}JLabel jlabel2;JTextField jtf2;JButton jb_input;JScrollPane jsp;JTable jt;DefaultTableModel dtm;static int list = 1, count = list - 1;int time1 = 0;int time2 = 0;int time3 = 0;int time4 = 0;public void lauchFrame() {this.setLayout(null);this.setBounds(100, 100, 540, 320);this.setBackground(Color.cyan);this.setVisible(true);jlabel2 = new JLabel("请输入第" + list + "个访问页面:");jtf2 = new JTextField();jb_input = new JButton("输入");jlabel2.setBounds(20, 50, 140, 20);jtf2.setBounds(155, 50, 50, 20);jb_input.setBounds(240, 50, 60, 20);this.add(jlabel2);this.add(jtf2);this.add(jb_input);this.addWindowListener(new WindowAdapter() {public void windowClosing(WindowEvent e) {System.exit(0);}});jb_input.addActionListener(new InputActionListener());Object[] title = {"访问序列","Cache块0", "Cache块1", "Cache块2", "Cache块3", "状态"};dtm = new DefaultTableModel(title, 0);jt = new JTable(dtm);jsp = new JScrollPane(jt);jsp.setBounds(50, 80, 440, 197);jsp.setBackground(Color.black);this.add(jsp);}class InputActionListener implements ActionListener {public void actionPerformed(ActionEvent e) {if(jtf2.getText().equals("")) {Object[] options = { "OK" };JOptionPane.showOptionDialog(null, "你的输入存在“”，请按提示输入！", "警告",JOptionPane.DEFAULT_OPTION, JOptionPane.WARNING_MESSAGE,null, options, options[0]);}list++;if(count < 4) {//count记录装入cache块的页面数switch(count) {case 0://cache块中没有装入页面的情况dtm.addRow(new Object[]{jtf2.getText(), jtf2.getText(), "", "", "", "装入"});time2++;time3++;time4++;count++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");break;case 1://cache块中装入一个页面的情况if(jtf2.getText().equals(jt.getValueAt(list-3, 1))) {//要访问的页面刚好在cache0中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1), "", "", "", "命中"});time2++;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else {//要访问的页面不在cache块中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1), jtf2.getText(), "", "", "装入"});time1++;time2 = 0;time3++;time4++;count++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}break;case 2://cache块中装入两个页面的情况if(jtf2.getText().equals(jt.getValueAt(list-3, 1))) {//要访问的页面刚好在cache0中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), "", "", "命中"});time1 =0;time2++;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(jtf2.getText().equals(jt.getValueAt(list-3, 2))) {//要访问的页面刚好在cache1中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), "", "", "命中"});time1++;time2 = 0;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else {//要访问的页面不在cache块中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), jtf2.getText(), "", "装入"});time1++;time2++;time3 =0;time4++;count++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}break;case 3://cache块中装入三个页面的情况if(jtf2.getText().equals(jt.getValueAt(list-3, 1))) {//要访问的页面刚好在cache0中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), "", "命中"});time1 = 0;time2++;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(jtf2.getText().equals(jt.getValueAt(list-3, 2))) {//要访问的页面刚好在cache1中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), "", "命中"});time1++;time2 =0;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(jtf2.getText().equals(jt.getValueAt(list-3, 3))) {//要访问的页面刚好在cache2中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), "", "命中"});time1++;time2++;time3 = 0;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}else {//要访问的页面不在cache块中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), jtf2.getText(), "装入"});time1++;time2++;time3++;time4 = 0;count++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}break;}} else {//四个cache块都装满的情况if(jtf2.getText().equals(jt.getValueAt(list-3, 1))) {//要访问的页面刚好在cache0中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1), jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), jt.getValueAt(list-3, 4), "命中"});System.out.println(1);time1 = 0;time2++;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(jtf2.getText().equals(jt.getValueAt(list-3, 2))) {//要访问的页面刚好在cache1中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1), jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), jt.getValueAt(list-3, 4), "命中"});System.out.println(2);time1++;time2 = 0;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(jtf2.getText().equals(jt.getValueAt(list-3, 3))) {//要访问的页面刚好在cache2中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1), jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), jt.getValueAt(list-3, 4), "命中"});System.out.println(3);time1++;time2++;time3 = 0;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(jtf2.getText().equals(jt.getValueAt(list-3, 4))) {//要访问的页面刚好在cache3中dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1), jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), jt.getValueAt(list-3, 4), "命中"});System.out.println(4);time1++;time2++;time3++;time4 = 0;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}else {//要访问的页面不在cache块中if(time1>time2 && time1>time3 && time1>time4) {//如果cache0的页面最长时间没有被访问，新页面置换cache0中页面dtm.addRow(new Object[]{jtf2.getText(), jtf2.getText(), jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), jt.getValueAt(list-3, 4), "置换"});time1 = 0;time2++;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(time2>time1 && time2>time3 && time2>time4) {//如果cache1的页面最长时间没有被访问，新页面置换cache1中页面dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1), jtf2.getText(), jt.getValueAt(list-3, 3), jt.getValueAt(list-3, 4), "置换"});time1++;time2 = 0;time3++;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(time3>time1 && time3>time2 && time3>time4) {//如果cache2的页面最长时间没有被访问，新页面置换cache2中页面dtm.addRow(new Object[]{jtf2.getText(), jt.getValueAt(list-3, 1),jt.getValueAt(list-3, 2), jtf2.getText(), jt.getValueAt(list-3, 4), "置换"});time1++;time2++;time3 = 0;time4++;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");} else if(time4>time1 && time4>time2 && time4>time3) {//如果cache3的页面最长时间没有被访问，新页面置换cache3中页面dtm.addRow(new Object[]{jtf2.getText(), JO.getValueAt(list-3, 1),JO.getValueAt(list-3, 2), JO.getValueAt(list-3, 3), jtf2.getText(), "置换"});time1++;time2++;time3++;time4 = 0;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}}}}}}2、LRU算法：// cache 更新算法,LRUvoid up_cache(){int i=0;while(i<n){ int j=0;//满么?while(j<m){if((cache[j].state==false)&&(walk_sort[i]!=cache[j].value)){cout<<"cache 有空闲块,不考虑是否要置换."<<endl；cout<<walk_sort[i]<<"被调入 cache...."<<endl;cache[j].value=walk_sort[i++];cache[j].state=true;cache[j].count=0;int kk=0;for (x=0;x<m;x++)cout<<"cache 块"<<x<<": "<<cache[x].value<<endl;cout<<endl;//更新其它 cache 块没使用时间while(kk<m){if(kk!=j&&cache[kk].value!=(-1))cache[kk].count++;kk++;}delay();break;}if(cache[j].value==walk_sort[i]){cout<<endl;cout<<walk_sort[i]<<"命中!!!"<<endl;for (x=0;x<m;x++)cout<<"cache 块"<<x<<": "<<cache[x].value<<endl;cout<<endl;int kk=0;i++;cache[j].count=0;//更新其它 cache 块没使用时间while(kk<m){if(kk!=j&&cache[kk].value!=(-1))cache[kk].count++;kk++;}}j++;}if(j==m){cout<<"cache 已经满了,考虑是否置换."<<endl;cout<<endl;int k=0;while(k<m){if(cache[k].value==walk_sort[i]){cout<<endl;cout<<walk_sort[i]<<"命中!!!"<<endl;for (x=0;x<m;x++)cout<<"cache 块"<<x<<": "<<cache[x].value<<endl;i++;cache[k].count=0;int kk=0;//更新其它 cache 块没使用时间while(kk<m){if(kk!=k)cache[kk].count++;kk++;}break;}k++;}if(k==m)//考虑置换那一块.{int ii=0;int t=0;//要替换的 cache 块号.int max=cache[ii].count;ii++;while(ii<m){if(cache[ii].count>max){max=cache[ii].count;t=ii;}ii++;}//置换cout<<cache[t].value<<"被"<<walk_sort[i]<<"在 cache 的"<<t<<"号块置换..."<<endl;cache[t].value=walk_sort[i++];cache[t].count=0;for (x=0;x<m;x++)cout<<"cache 块"<<x<<": "<<cache[x].value<<endl;int kk=0;//更新其它 cache 块没使用时间while(kk<m){if(kk!=t)cache[kk].count++;kk++;}delay();}}}}3、实验四：单功能流水线调度机构模拟一、实验目的：1、结合数据结构的相关知识,编写流水线调度模拟程序。
