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

计算机体系结构
课程设计

学院：　 信息科学与工程学院
专业班级：　
指导老师：　　　
学号：　　
姓名：　　 　

目录
实验 1 对指令操作码进行霍夫曼编码 3
一、实验目的 3
二、实验内容 3
三、设计思路 4
四、关键代码 4
五、实验截图 5
六、源代码 5
实验 2 使用 LRU 方法更新 Cache 8
一、实验目的 8
二、实验内容 8
三、设计思路 9
四、程序截图 9
五、实验代码 9
实验总结 16
参考文献 16

实验 1 对指令操作码进行霍夫曼编码
一、实验目的
了解和掌握指令编码的基本要求和基本原理
二、实验内容
1. 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果
以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。
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.
要对指令的操作码进行 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();
lruc.lauchFrame();
}

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(), jt.getValueAt(list-3, 1), jt.getValueAt(list-3, 2), jt.getValueAt(list-3, 3), jtf2.getText(), "置换"});
time1++;
time2++;
time3++;
time4 = 0;
jtf2.setText("");
jlabel2.setText("请输入第" + list + "个访问页面:");
}
}
}

}
}
}

实验总结
体系结构属于计算机整个的结构，涉及计算机的整个结构，从底层到高层，每层的原理，结构及实现，是一门比较抽象的学科，通过这次的几个实验，让我对计算机的编码和页面的替换算法有了更深层次的理解。 计算机是一门理论性很强的学科，但是实际的操作又是必不可少的。实践可以加深对课程的理解，也能提高编程能力，总之，通过这次实验，我学到了很多。

参考文献
[1] 郑纬民 汤志忠 计算机系统结构 清华大学出版社 2002
[2] 余腊生 计算机系统结构实验指导书 中南大学信息科学与工程学院制定