计算机体系结构课程设计学院：信息科学与工程学院专业班级：指导老师：学号：姓名：目录实验1 对指令操作码进行霍夫曼编码 (3)一、实验目的 (3)二、实验内容 (3)三、设计思路 (4)四、关键代码 (4)五、实验截图 (5)六、源代码 (5)实验2 使用LRU 方法更新Cache (8)一、实验目的 (8)二、实验内容 (8)三、设计思路 (9)四、程序截图 (9)五、实验代码 (9)实验总结 (16)参考文献 (16)实验1 对指令操作码进行霍夫曼编码一、实验目的了解和掌握指令编码的基本要求和基本原理二、实验内容1. 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。
与扩展操作码和等长编码进行比较。
2. 问题描述以及问题分析举例说明此问题，例如：下表所示：对此组指令进行 HUFFMAN 编码正如下图所示：最后得到的HUFFMAN 编码如下表所示：最短编码长度为：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 树进行中序遍历即可完成编码工作。
三、设计思路观察上图，不难看出构造 HUFFMAN 树所要做的工作：1、先对各指令操作码的出现概率进行排序，构造一个有序链表。
2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。
3、在对链表进行排序，链表是否只有一个节点，是则 HUFFAN 树构造完毕，否则继续做 2 的操作。
为此设计一个工作链表（链表的元素时类，此类的功能相当结构。
）、HUFFMAN 树节点、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记下次最小权值结点的下标}}五、实验截图六、源代码public class huffman {private String str;public huffman(String str){this.str=str;}/*** 创建节点类* @param args*/class Node{Node left;Node right;int data;char c;String code="";}/*** 节点数组（字符串类）* @param args*/public void creatTree(){//先去掉重复的字符串，若不存在将字符加在strRepeat中String strRepeat="";for(int i=0;i<str.length();i++){char c=str.charAt(i);//判断是否存在if(strRepeat.indexOf(c)==-1){ //找到字符位置并返回字符所在的位置strRepeat+=c;}}//统计字符出现的次数并建立节点Node[] nodes=new Node[strRepeat.length()]; //定义了一个nodes数组//存储节点的坐标值int s=0;for(int i=0;i<strRepeat.length();i++){char c=strRepeat.charAt(i);int count=getCount(str,c); //c在string中出现的次数Node node=new Node();node.data=count;node.c=c;nodes[s++]=node;}//创建哈弗曼树while(nodes.length>1){sort(nodes);Node node=new Node();Node n1=nodes[0];Node n2=nodes[1];node.data=n1.data+n2.data;node.left=n1;node.right=n2;//改变节点数组长度Node[] nodes2=new Node[nodes.length-1];for(int i=2;i<nodes.length;i++){nodes2[i-2] = nodes[i];}nodes2[nodes2.length-1]=node;nodes=nodes2;}Node root=nodes[0];printCode(root,"");}/*** 统计字符出现的次数get方法*/private int getCount(String str,char c){int count = 0;for(int i=0;i<str.length();i++){if(c==str.charAt(i))count++;}return count;}/*** 冒泡排序法* @param nodes*/public void sort(Node[] nodes){for(int i=0;i<nodes.length;i++){for(int j=i+1;j<nodes.length;j++){if(nodes[i].data>=nodes[j].data){//交换节点对象Node temp=nodes[i];nodes[i]=nodes[j];nodes[j]=temp;}}}}/*** 打印编码* @param args*/public void printCode(Node node,String code){if(node != null){if(node.left==null && node.right==null)System.out.println(node.c+"..."+node.data+"的编码是："+code);printCode(node.left,code+""+0);printCode(node.right,code+""+1);}}public static void main(String[] args) {String str="add bate";huffman hf=new huffman(str);hf.creatTree();}}实验2 使用LRU 方法更新Cache 一、实验目的了解和掌握寄存器分配和内存分配的有关技术。
二、实验内容LRU置换算法是选择最近最久未使用的页面予以置换。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面时，选择现有页面中T值最大的，即最近最久没有访问的页面。
这是一个比较合理的置换算法。
举例说明此问题，例如：有一个CACHE采用组相连映象方式。
每组有四块，为了实现LRU置换算法，在快表中为每块设置一个2位计数器。
我们假设访问序列为“1,1,2,4,3,5,2,1,6,7,1,3”。
在访问CACHE的过程中，块的装入，置换及命中时，具体情况如下表所示：三、设计思路LRU 置换算法是选择最近最久未使用的页面予以置换。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面时，选择现有页面中T 值最大的，即最近最久没有访问的页面。
这是一个比较合理的置换算法。
四、程序截图五、实验代码import java.awt.*;import java.awt.event.*;import javax.swing.*;import javax.swing.table.*;public class lru extends Frame {public static void main(String[] args) {JFrame.setDefaultLookAndFeelDecorated(true);lru lruc = new lru();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++;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(),jt.getValueAt(list-3, 1), jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3),jtf2.getText(), "置换"});time1++;time2++;time4 = 0;jtf2.setText("");jlabel2.setText("请输入第" + list + "个访问页面:");}}}}}}实验总结体系结构属于计算机整个的结构，涉及计算机的整个结构，从底层到高层，每层的原理，结构及实现，是一门比较抽象的学科，通过这次的几个实验，让我对计算机的编码和页面的替换算法有了更深层次的理解。