計(jì)算機(jī)體系結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、計(jì)算機(jī)體系結(jié)構(gòu)F南大學(xué)計(jì)算機(jī)體系結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)生姓名信息科學(xué)與工程學(xué)院專(zhuān)業(yè)班級(jí)1.實(shí)驗(yàn)內(nèi)容.2.實(shí)驗(yàn)1 :對(duì)指令操作碼進(jìn)行霍夫曼編碼2.1實(shí)驗(yàn)?zāi)康?.2實(shí)驗(yàn)內(nèi)容2.3實(shí)驗(yàn)結(jié)果3.實(shí)驗(yàn)2 :使用3.1實(shí)驗(yàn)?zāi)康?.2實(shí)驗(yàn)內(nèi)容3.3實(shí)驗(yàn)結(jié)果LRU方法更新Cache .444 4.總結(jié).5.代碼附錄.第3頁(yè)共12頁(yè)計(jì)算機(jī)體系結(jié)構(gòu)計(jì)算機(jī)體系結(jié)構(gòu)第14頁(yè)共12頁(yè)1.實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)1對(duì)指令操作碼進(jìn)行霍夫曼編碼實(shí)驗(yàn)2 使用LRU方法更新Cache2.實(shí)驗(yàn)1 :對(duì)指令操作碼進(jìn)行霍夫曼編碼2.1實(shí)驗(yàn)?zāi)康牧私夂驼莆罩噶罹幋a的基本要求和基本原理2.2實(shí)驗(yàn)內(nèi)容使用編程工具編寫(xiě)一個(gè)程序，對(duì)一組指令進(jìn)行霍夫曼編碼，并輸出最后

2、的編碼結(jié)果以及 對(duì)指令碼的長(zhǎng)度進(jìn)行評(píng)價(jià)。與擴(kuò)展操作碼和等長(zhǎng)編碼進(jìn)行比較。要對(duì)指令的操作碼進(jìn)行HUFFMAN 樹(shù)再進(jìn)行HUFFMAN 編碼，只要根據(jù)指令的各類(lèi)操作碼的出現(xiàn)概率構(gòu)造HUFFAM 編碼。此過(guò)程的難點(diǎn)構(gòu)造HUFFMAN 樹(shù)，進(jìn)行 HUFFAM 編碼只要對(duì)你所生成 的HUFFMAN 樹(shù)進(jìn)行中序遍歷即可完成編碼工作。2.3實(shí)驗(yàn)結(jié)果Ml 3-mh Inn 3nH- 豐 m L* 二 r dm -.14 JliJ- lif axax.xaa 卽郭釀第卵 一 F1 * I IM n n - -二亠i s 1- 1吃桁生雄塑旺礎(chǔ)腐珂舊平均憶変力二上琵翊宓魏豁跖衞”2Pr-nr-f： aa rr-l

3、-hmif-fl H r-vrcit innFf-s-E ATI V ko-V to cont nu-.3. 實(shí)驗(yàn)2 :使用LRU方法更新Cache3.1實(shí)驗(yàn)?zāi)康牧私夂驼莆占拇嫫鞣峙浜蛢?nèi)存分配的有關(guān)技術(shù)。3.2實(shí)驗(yàn)內(nèi)容Cache更新：結(jié)合數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，使用LRU的策略，對(duì)一組訪問(wèn)序列進(jìn)行內(nèi)部的LRU置換算法是選擇最近最久未使用的頁(yè)面予以置換。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)經(jīng)歷的時(shí)間T,當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中T值最大的，即最近最久沒(méi)有訪問(wèn)的頁(yè)面。這是一個(gè)比較合理的置換算法。3.3實(shí)驗(yàn)結(jié)果為為 執(zhí) J 伶聲1,耶e.75weaHeKCU.t lU

4、fi C Iht = LJ.bKl CTcSi 於hy hr# tJ tMCtirtiltr4. 總結(jié)實(shí)驗(yàn)一是曾在學(xué)習(xí)數(shù)字通信原理課程時(shí)編寫(xiě)的，當(dāng)時(shí)只有簡(jiǎn)單的排序后編碼的功能，學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)后，我往里面加入了樹(shù)的結(jié)構(gòu)，使編碼后的結(jié)果更加清晰明了了。學(xué)習(xí)了計(jì)算機(jī)體系結(jié)構(gòu)之后，我又往里面加入了求編碼長(zhǎng)度的功能。通過(guò)這個(gè)程序，我更加了解哈夫曼編碼的知識(shí)了。實(shí)驗(yàn)二是寫(xiě)出LRU算法，這個(gè)相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，因?yàn)樵趯W(xué)習(xí)操作系統(tǒng)原理時(shí)接觸過(guò)FIFO等等算法并且編程實(shí)現(xiàn)了，難點(diǎn)在于輸出結(jié)果的排版，一開(kāi)始我想輸出一個(gè)表格，這樣更符合書(shū)上關(guān)于此算法的內(nèi)容，但是出現(xiàn)了各種不對(duì)齊的問(wèn)題，最后只好讓它直接輸出結(jié)果。通過(guò)這

5、幾次實(shí)驗(yàn)，我發(fā)現(xiàn)了自身的不足，比如沒(méi)有很好的書(shū)寫(xiě)習(xí)慣，考慮問(wèn)題不周到，對(duì)于計(jì)算機(jī)體系結(jié)構(gòu)課程中知識(shí)的理解不夠深入等。但在編程的過(guò)程中我體驗(yàn)到了一分耕耘一分收獲的喜悅；多次調(diào)試后程序成功運(yùn)行了，那時(shí)候的歡樂(lè)是我以前無(wú)法想象的。果然,學(xué)習(xí)任何一門(mén)課程，只要學(xué)得用心，都可以從中體會(huì)到學(xué)習(xí)的快樂(lè)。今后我的進(jìn)步，想必都是從這一點(diǎn)一點(diǎn)敲入編譯器的代碼中獲得的。5. 代碼附錄實(shí)驗(yàn)1#in clude#in cludeusing n ames pace std;#defi ne N 8class huff_ ppublic:huff_p* r_child; II大概率的節(jié)點(diǎn)；huff_p* l_child;

6、II小概率的節(jié)點(diǎn)；char op_mask3; II 指令標(biāo)號(hào)；float p; II指令使用概率；;class f_min_ppublic:f_min_P* n ext;char op_mask3; II 指令標(biāo)號(hào)；float p; II指令使用概率； huff_ p* huf_ p;class huff_codepublic:huff_code* n ext;float p;char op_mask3;char codeN; IIhuffman 編碼；;f_min_p* input_instruct_set();II 輸入指令集子模塊；huff_p* creat_huffman_tree(

7、f_min_p* head);II 構(gòu)造 huffman 樹(shù);f_min_p* fin_min(f_min_p* h);f_min_p* del_ min(f_min_p* h,f_ min_p* p);void in sert_ 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);II 生成 huffman 編碼;void r_fin d(huff_ p* p 1,char code,i nt i,huff_code* h);v

8、oid output_hufman(huff_code* head);/ 輸出 huffman 編碼;void cal_sort_length(huff_code* head);/ 計(jì)算指令用 huffman 編碼的平均編碼字長(zhǎng) int mai n() f_min_p *h,*h1;huff_ p *root;huff_code* head,* pl;int i=0;h=input_in struct_set();h1=h;root=creat_huffma n_tree(h1);head=new huff_code;head- next=NULL;creat_huffma n_code(ro

9、ot,head);out pu t_huffma n( head);cal_sort_le ngth(head);pl=head-n ext;while( pl)delete head;head=pl;pl=p l-n ext;f_min_p* input_in struct_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;H.cout h-op_mask;cout h-p;int i=0;f_min_p* point;f_min_P* P 1=head;for(

10、;i n-1;i+) point=new f_min_p;H.coutpoin t- op _mask;H.p oi nt-op_mask2=0;coutpoint-p;poi nt-huf_p=NULL; point-n ext=p1-n ext; p1-n ext=point; p1=poin t; return head; huff_ p* creat_huffma n_tree(f_min _p* h) f_min _p *h1,*mi n1,*mi n2,*comb; huff_ p* head,*rd,*ld,* parent;h1=h;min 1=fi n_min( h1); l

11、d=creat_huffp (min 1); h1=del_mi n(h1,mi n1); if(h1- next) min 2=fi n_min( h1);elsemin 2=h1; rd=creat_huffp (min 2); comb=new f_min _p; comb-n ext=NULL; comb-p=rd-p+ld-p; comb-op_mask0=0; comb-op_mask1=0; parn t=creat_huffp(comb); in sert_ n( h1,comb); if(h1- next!=NULL) h1=del_mi n(h1,mi n2); paren

12、 t-l_child=ld; paren t-r_child=rd; comb-huf_ p=parent; head=parent;int i=0;while(h1- next!=NULL) min 1=fi n_min( h1);if(mi n1-huf_p=NULL) ld=creat_huffp (min 1); else ld=min 1-huf_ p; h1=del_mi n(h1,mi n1); if(h1- next) min 2=fi n_min( h1);elsemin 2=h1;if(mi n2-huf_p=NULL) rd=creat_huffp (min 2);els

13、erd=min 2-huf_ p; comb=new f_min_p; comb-n ext=NULL; comb-p=rd-p+ld-p; comb-op_mask0=0; comb-op_mask1=0;paren t=creat_huffp(comb);if(h1!=NULL)in sert_ n( h1,comb);if(h1- next!=NULL) h1=del_mi n(h1,mi n2);paren t-l_child=ld;paren t-r_child=rd; comb-huf_ p=parent; head=parent;if(h1- next=NULL)break; d

14、elete 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(mi n(h1- p) min=h1- p;p1=h1;h1=h1- next;return p 1;f_min_p* del_ min( f_min _p *h,f_min _p *p) f_min_p *p 1,* p2;p1=h;p2=h;if(h=p) h=h-n ext;delete p;elsewhile( p1- next!=NULL

15、)p1=p1-n ext;if(p 1=p)p2-n ext=p1-n ext;delete p;break;p2=p1；return h;void in sert_ n(f_min_p *h,f_ min_p *p 1)p1-n ext=h-n ext;h-n ext =p 1;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;P 1- op _mask0=d- op _mask0;P 1- op _mask1=d- op _mask1;re

16、turn p 1;void r_fin d(huff_ p* p 1,char code,i nt i,huff_code* h) if(p 1-l_child)codei=1;r_fin d( p1-l_child,code,i+1,h);if(P 1-op_mask0!=0)huff_code* p2=new huff_code;p 2- op _mask0 =p 1- op _mask0;p 2- op _mask1=p 1- op _mask1;p1-op_mask2=0;p2-p=p1-p;int j;for( j=0;jcodej=codej;p2-codej=0;p2-n ext

17、=h-n ext;h-n ext =p 2;if(P 1-r_child)codei=0;r_fin d( p1-r_child,code,i+1,h);delete p1;void creat_huffma n_code(huff_ p* h1,huff_code* h) int i=0;char codeN;r_fin d(h1,code,i,h);void out pu t_huffma n( huff_code* head)huff_code* h=head-n ext;coute ndl;cout標(biāo)號(hào):-概率- -編碼-endl;coutop_mask2=0;endl;cout op

18、 _mask: p coden ext; coutcoutn ext;double j=0;float one_len gth=0;float p er_le ngth=0;float ext_length=0;/按1-2-3-5擴(kuò)展編碼的最小長(zhǎng)度為。 while(h)float le ngth=0;int i=0;while(h-codei!=0)len gth+;i+;on e_le ngth=h-p *le ngth;p er_le ngth=p er_le ngth+one_len gth; /12h=h-n ext;j+;int i1=i nt(j);huff_code *p 2=h

19、ead-n ext; float* p_a=new floati1; int i0=0;while( p2)p_ai0+=p2- p; p2=p 2- next; float max,te mp; int l;for(i nt s=0;si1;s+)max=p _as;l=s;for(i nt k=s+1;ki1;k+) if(maxp_ak) max=p _ak;l=k; temp=p _as;p_as=max; p_al=tem p; float* code_le n=new floati1;code_le n0=1;code_le n1=2; code_le n2=3;code_le n

20、3=5;for(i nt i=4;ij;i+)code_le ni=5;while(li1)ext_le ngth=ext_le ngth+code_le nl* p_al;double q_le ngth=log10(j)/log10(2);cout此指令集操作碼 huffman編碼的平均長(zhǎng)度為 per_lengthendl;cout等長(zhǎng)編碼的平均長(zhǎng)度為 q_lengthendl;cout按1-2-3-5的擴(kuò)展編碼的最短平均編碼長(zhǎng)度為ext_length;coute ndl;coute ndl;實(shí)驗(yàn)2#in clude #in clude#defi ne M 4#defi ne N 12#defi ne Myprintf printf(|-+-+-+-+-|n) typ edef struct p ageint num;int time;Page;Page bM;int cMN;int queue100;int K;/*記錄頁(yè)面號(hào)*/*記錄調(diào)入內(nèi)存時(shí)間*/*頁(yè)面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)/*內(nèi)存單元數(shù)*/*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)/*記錄調(diào)入隊(duì)列*/*調(diào)入隊(duì)列計(jì)數(shù)變量*/*/*/void lnit(P age *b,i nt cMN)int i,j;for(i=0;iN;i+)bi. nu m=-1;bi.time=N-i-1;for(i=