1、计算机体系结构实验报告中南大学计算机体系结构实验报告学生姓名 学 院 信息科学与工程学院 专业班级 完成时间 2015年10月27日 计算机体系结构1.实验内容实验 1 对指令操作码进行霍夫曼编码实验 2 使用 LRU 方法更新 Cache2.实验1：对指令操作码进行霍夫曼编码 2.1 实验目的了解和掌握指令编码的基本要求和基本原理2.2 实验内容 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。要对指令的操作码进行 HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFMAN 树再进行 HUFF
2、AM 编码。此过程的难点构造 HUFFMAN 树，进行 HUFFAM编码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。2.3 实验结果 3.实验2 ：使用 LRU 方法更新 Cache3.1 实验目的 了解和掌握寄存器分配和内存分配的有关技术。3.2 实验内容Cache 更新：结合数据结构的相关知识，使用 LRU的策略，对一组访问序列进行内部的LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有页面中 T 值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。
3、3.3 实验结果4.总结 实验一是曾在学习数字通信原理课程时编写的，当时只有简单的排序后编码的功能，学习了数据结构后，我往里面加入了树的结构，使编码后的结果更加清晰明了了。学习了计算机体系结构之后，我又往里面加入了求编码长度的功能。通过这个程序，我更加了解哈夫曼编码的知识了。实验二是写出LRU算法，这个相对来说比较简单，因为在学习操作系统原理时接触过FIFO等等算法并且编程实现了，难点在于输出结果的排版，一开始我想输出一个表格，这样更符合书上关于此算法的内容，但是出现了各种不对齐的问题，最后只好让它直接输出结果。 通过这几次实验，我发现了自身的不足，比如没有很好的书写习惯，考虑问题不周到，对于
4、计算机体系结构课程中知识的理解不够深入等。但在编程的过程中我体验到了一分耕耘一分收获的喜悦；多次调试后程序成功运行了，那时候的欢乐是我以前无法想象的。果然，学习任何一门课程，只要学得用心，都可以从中体会到学习的快乐。今后我的进步，想必都是从这一点一点敲入编译器的代码中获得的。5.代码附录实验1#include#includeusing namespace std;#define N 8class huff_ppublic:huff_p* r_child; /大概率的节点；huff_p* l_child; /小概率的节点；char op_mask3; /指令标号；float p; /指令使用概率
5、；;class f_min_ppublic:f_min_p* next;char op_mask3; /指令标号；float p; /指令使用概率；huff_p* huf_p;class huff_codepublic:huff_code* next;float p;char op_mask3;char codeN; /huffman 编码；;f_min_p* input_instruct_set();/输入指令集子模块；huff_p* creat_huffman_tree(f_min_p* head);/构造huffman树;f_min_p* fin_min(f_min_p* h);f_mi
6、n_p* del_min(f_min_p* h,f_min_p* p);void insert_n(f_min_p* h,f_min_p* p);huff_p* creat_huffp(f_min_p* p);void creat_huffman_code(huff_p* h1,huff_code* h);/生成huffman编码;void r_find(huff_p* p1,char code,int i,huff_code* h);void output_huffman(huff_code* head);/输出huffman编码;void cal_sort_length(huff_code
7、* head);/计算指令用huffman编码的平均编码字长int main()f_min_p *h,*h1;huff_p *root;huff_code* head,*pl;int i=0;h=input_instruct_set();h1=h;root=creat_huffman_tree(h1);head=new huff_code;head-next=NULL;creat_huffman_code(root,head);output_huffman(head);cal_sort_length(head);pl=head-next;while(pl)delete head;head=pl
8、;pl=pl-next;f_min_p* input_instruct_set()f_min_p* head;f_min_p* h;h=new f_min_p;h-next=NULL;h-huf_p=NULL;head=h;int n;coutn;couth-op_mask;couth-p;int i=0;f_min_p* point;f_min_p* p1=head;for(;in-1;i+)point=new f_min_p;coutpoint-op_mask;point-op_mask2=0;coutpoint-p;point-huf_p=NULL;point-next=p1-next;
9、p1-next=point;p1=point;return head;huff_p* creat_huffman_tree(f_min_p* h)f_min_p *h1,*min1,*min2,*comb;huff_p* head,*rd,*ld,*parent;h1=h;min1=fin_min(h1);ld=creat_huffp(min1);h1=del_min(h1,min1);if(h1-next)min2=fin_min(h1);elsemin2=h1;rd=creat_huffp(min2);comb=new f_min_p;comb-next=NULL;comb-p=rd-p+
10、ld-p;comb-op_mask0=0;comb-op_mask1=0;parnt=creat_huffp(comb);insert_n(h1,comb);if(h1-next!=NULL)h1=del_min(h1,min2);parent-l_child=ld;parent-r_child=rd;comb-huf_p=parent;head=parent;int i=0;while(h1-next!=NULL)min1=fin_min(h1);if(min1-huf_p=NULL)ld=creat_huffp(min1);elseld=min1-huf_p;h1=del_min(h1,m
11、in1);if(h1-next)min2=fin_min(h1);elsemin2=h1;if(min2-huf_p=NULL)rd=creat_huffp(min2);elserd=min2-huf_p;comb=new f_min_p;comb-next=NULL;comb-p=rd-p+ld-p;comb-op_mask0=0;comb-op_mask1=0;parent=creat_huffp(comb);if(h1!=NULL)insert_n(h1,comb);if(h1-next!=NULL)h1=del_min(h1,min2);parent-l_child=ld;parent
12、-r_child=rd;comb-huf_p=parent;head=parent;if(h1-next=NULL)break;delete comb;return head;f_min_p* fin_min(f_min_p* h)f_min_p *h1,*p1;h1=h;p1=h1;float min=h1-p;h1=h1-next;while(h1)if(min(h1-p)min=h1-p;p1=h1;h1=h1-next;return p1;f_min_p* del_min( f_min_p *h,f_min_p *p)f_min_p *p1,*p2;p1=h;p2=h;if(h=p)h
13、=h-next;delete p;elsewhile(p1-next!=NULL)p1=p1-next;if(p1=p)p2-next=p1-next;delete p;break;p2=p1;return h;void insert_n(f_min_p *h,f_min_p *p1)p1-next=h-next;h-next=p1;huff_p* creat_huffp(f_min_p* d)huff_p* p1;p1=new huff_p;p1-l_child=NULL;p1-r_child=NULL;p1-p=d-p;p1-op_mask0=d-op_mask0;p1-op_mask1=
14、d-op_mask1;return p1;void r_find(huff_p* p1,char code,int i,huff_code* h)if(p1-l_child)codei=1;r_find(p1-l_child,code,i+1,h);if(p1-op_mask0!=0)huff_code* p2=new huff_code;p2-op_mask0=p1-op_mask0;p2-op_mask1=p1-op_mask1;p1-op_mask2=0;p2-p=p1-p;int j;for( j=0;jcodej=codej;p2-codej=0;p2-next=h-next;h-n
15、ext=p2;if(p1-r_child)codei=0;r_find(p1-r_child,code,i+1,h);delete p1;void creat_huffman_code(huff_p* h1,huff_code* h)int i=0;char codeN;r_find(h1,code,i,h);void output_huffman(huff_code* head)huff_code* h=head-next;coutendl;cout标号:-概率- -编码-endl;cout-op_mask2=0;coutop_mask: p codenext;cout-endl;coutn
16、ext;double j=0;float one_length=0;float per_length=0;float ext_length=0;/按1-2-3-5扩展编码的最小长度为。while(h)float length=0;int i=0;while(h-codei!=0)length+;i+;one_length=h-p*length;per_length=per_length+one_length; /12 h=h-next;j+;int i1=int(j);huff_code *p2=head-next;float* p_a=new floati1;int i0=0;while(p
17、2)p_ai0+=p2-p;p2=p2-next;float max,temp;int l;for(int s=0;si1;s+)max=p_as;l=s;for(int k=s+1;ki1;k+)if(maxp_ak)max=p_ak;l=k;temp=p_as;p_as=max;p_al=temp;float* code_len=new floati1;code_len0=1;code_len1=2;code_len2=3;code_len3=5;for(int i=4;ij;i+)code_leni=5;while(li1)ext_length=ext_length+code_lenl*
18、p_al;double q_length=log10(j)/log10(2);cout此指令集操作码huffman编码的平均长度为per_lengthendl;cout等长编码的平均长度为q_lengthendl;cout按1-2-3-5的扩展编码的最短平均编码长度为ext_length;coutendl;coutendl;实验2#include#include#define M 4#define N 12#define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-|n)typedef struct page int num; /*记录页面号*/ int t
19、ime; /*记录调入内存时间*/Page; /* 页面逻辑结构，结构为方便算法实现设计*/Page bM; /*内存单元数*/int cMN; /*暂保存内存当前的状态：缓冲区*/int queue100; /*记录调入队列*/int K; /*调入队列计数变量*/void Init(Page *b,int cMN) int i,j; for(i=0;iN;i+) bi.num=-1; bi.time=N-i-1; for(i=0;iM;i+) for(j=0;jN;j+) cij=-1;int GetMax(Page *b) int i; int max=-1; int tag=0; fo
20、r(i=0;imax) max=bi.time; tag=i; return tag;int Equation(int fold,Page *b) int i; for(i=0;i=0) bval.time=0; for(i=0;iM;i+) if (i!=val) bi.time+; else queue+K=fold;/*记录调入页面*/ val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;iM;i+) if (i!=val) bi.time+;int main() int aN= 1,1,2,4,3,5,2,1,6,7,1,3; int
21、i,j;start: K=-1; Init(b, c); for(i=0;iN;i+) Lru(ai,b); c0i=ai; for(j=0;jM;j+) cji=bj.num; printf(内存状态为：n); for(j=0;jN;j+) printf(%2d ,aj); printf(n); for(i=0;iM;i+) for(j=0;jN;j+) if(cij=-1) printf(%2c ,32); else printf(%2d ,cij); printf(n);printf(n调入队列为:); for(i=0;iK+1;i+) printf(%3d,queuei); printf(n缺页次数为：%6dn缺页率：%16.6fn,K+1,(float)(K+1)/N);
