計(jì)算機(jī)體系結(jié)構(gòu)報(bào)告

1、中南大學(xué)計(jì)算機(jī)體系結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)生姓名 代巍 指導(dǎo)教師 雷向東 學(xué) 院 信息科學(xué)與工程學(xué)院 專(zhuān)業(yè)班級(jí) 信安1201班 學(xué) 號(hào) 0909121615 完成時(shí)間 2014年11月20日 實(shí)驗(yàn) 1 對(duì)指令操作碼進(jìn)行霍夫曼編碼一、實(shí)驗(yàn)?zāi)康牧私夂驼莆罩噶罹幋a的基本要求和基本原理二、實(shí)驗(yàn)要求使用編程工具編寫(xiě)一個(gè)程序，對(duì)一組指令進(jìn)行霍夫曼編碼，并輸出最后的編碼結(jié)果以及對(duì)指令碼的長(zhǎng)度進(jìn)行評(píng)價(jià)。與擴(kuò)展操作碼和等長(zhǎng)編碼進(jìn)行比較。問(wèn)題描述以及問(wèn)題分析：我們舉例說(shuō)明此問(wèn)題，例如：有一組指令的操作碼共分七類(lèi)，它們出現(xiàn)概率如下表所示：P1 P2 P3 P4 P5 P6 P70.45 0.30 0.15 0.05 0.03

2、 0.01 0.01對(duì)此組指令進(jìn)行 HUFFMAN 編碼正如下圖所示：三、實(shí)驗(yàn)內(nèi)容因?yàn)楦髯址谛畔⒅谐霈F(xiàn)的頻率是不同的，若根據(jù)字符出現(xiàn)的不同頻率分配給不同長(zhǎng)度的編碼：頻繁出現(xiàn)的字符分配給較短的編碼，不常出現(xiàn)的字符分配給較長(zhǎng)的編碼，且這種編碼還具有“前綴特性”，那么這樣的編碼電文總長(zhǎng)會(huì)最短，發(fā)送效率會(huì)最高，占用的空間會(huì)最少。而哈弗曼編碼就是這樣一種編碼，字符出現(xiàn)的頻率與該程序中對(duì)應(yīng)的權(quán)重。首先將建立哈弗曼樹(shù)，將權(quán)重最小的放在二叉樹(shù)的最低端，將權(quán)重最大的放置在離根結(jié)點(diǎn)最近的位置，這樣就可以使權(quán)重大的結(jié)點(diǎn)的編碼較短，權(quán)重小的結(jié)點(diǎn)的編碼較長(zhǎng)。實(shí)際上是建立一個(gè)表格，中間有結(jié)點(diǎn)的權(quán)重，父親和孩子的信息。

3、建立好哈弗曼樹(shù)之后，要使得哈弗曼的左子樹(shù)的編碼為0，右子樹(shù)的編碼為1?？梢酝ㄟ^(guò)這個(gè)來(lái)確定字符的哈弗曼編碼。 四、實(shí)驗(yàn)原理構(gòu)造 HUFFMAN 樹(shù)所要做的工作：1、先對(duì)各指令操作碼的出現(xiàn)概率進(jìn)行排序，構(gòu)造一個(gè)有序鏈表。2、再取出兩個(gè)最小的概率節(jié)點(diǎn)相加，生成一個(gè)生的節(jié)點(diǎn)加入到鏈表中，同時(shí)從兩表中刪除此兩個(gè)節(jié)點(diǎn)。3、在對(duì)鏈表進(jìn)行排序，鏈表是否只有一個(gè)節(jié)點(diǎn)，是則 HUFFAN 樹(shù)構(gòu)造完畢，否則繼續(xù)做 2 的操作。為此設(shè)計(jì)一個(gè)工作鏈表（鏈表的元素時(shí)類(lèi)，此類(lèi)的功能相當(dāng)結(jié)構(gòu)。）、HUFFMAN 樹(shù)節(jié)點(diǎn)、HUFFMAN 編碼表節(jié)點(diǎn)五、實(shí)驗(yàn)結(jié)果輸入的n為4，各節(jié)點(diǎn)的權(quán)重為23,34,54,65六、源程序代碼#i

4、nclude #include#include #include #include #define MAXBIT 100#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1 typedef struct int bitMAXBIT; int start; HCodeType; /* 編碼結(jié)構(gòu)體 */typedef struct int weight; int parent; int lchild; int rchild; int value; HNodeType; /* 結(jié)點(diǎn)結(jié)構(gòu)體 */ /* 構(gòu)造一顆哈夫曼樹(shù)

5、 */void HuffmanTree (HNodeType HuffNodeMAXNODE, int n) /* i、j： 循環(huán)變量，m1、m2：構(gòu)造哈夫曼樹(shù)不同過(guò)程中兩個(gè)最小權(quán)值結(jié)點(diǎn)的權(quán)值， x1、x2：構(gòu)造哈夫曼樹(shù)不同過(guò)程中兩個(gè)最小權(quán)值結(jié)點(diǎn)在數(shù)組中的序號(hào)。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼樹(shù)數(shù)組 HuffNode 中的結(jié)點(diǎn) */ for (i=0; i2*n-1; i+) HuffNodei.weight = 0;/權(quán)值 HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild

6、=-1; HuffNodei.value=i; /實(shí)際值，可根據(jù)情況替換為字母 /* end for */ /* 輸入 n 個(gè)葉子結(jié)點(diǎn)的權(quán)值 */ for (i=0; in; i+) printf (Please input weight of leaf node %d: n, i); scanf (%d, &HuffNodei.weight); /* end for */ /* 循環(huán)構(gòu)造 Huffman 樹(shù) */ for (i=0; in-1; i+) m1=m2=MAXVALUE; /* m1、m2中存放兩個(gè)無(wú)父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個(gè)結(jié)點(diǎn) */ x1=x2=0; /* 找出所有結(jié)點(diǎn)中權(quán)值

7、最小、無(wú)父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)，并合并之為一顆二叉樹(shù) */ for (j=0; jn+i; j+) if (HuffNodej.weight m1 & HuffNodej.parent=-1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight m2 & HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /* end for */ /* 設(shè)置找到的兩個(gè)子結(jié)點(diǎn) x1、x2 的父結(jié)點(diǎn)信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent

8、 = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.lchild = x1; HuffNoden+i.rchild = x2; printf (x1.weight and x2.weight in round %d: %d, %dn, i+1, HuffNodex1.weight, HuffNodex2.weight); /* 用于測(cè)試 */ printf (n); /* end for */ / int main(void) HNodeType HuffNodeMAXNODE; /*

9、定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu)體數(shù)組 */ HCodeType HuffCodeMAXLEAF, cd; /* 定義一個(gè)編碼結(jié)構(gòu)體數(shù)組， 同時(shí)定義一個(gè)臨時(shí)變量來(lái)存放求解編碼時(shí)的信息 */ int i, j, c, p, n; char pp100; printf (Please input n:n); scanf (%d, &n); HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父結(jié)點(diǎn)存在 */ if (HuffNodep.lchild

10、 = c) cd.bitcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求編碼的低一位 */ c=p; p=HuffNodec.parent; /* 設(shè)置下一循環(huán)條件 */ /* end while */ /* 保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位 */ for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; /* end for */ /* 輸出已保存好的所有存在編碼的哈夫曼編碼 */ for (i=0; in; i+)

11、 printf (%d s Huffman code is: , i); for (j=HuffCodei.start+1; j n; j+) printf (%d, HuffCodei.bitj); printf( start:%d,HuffCodei.start); printf (n); 實(shí)驗(yàn) 2 使用 LRU 方法更新 Cache一、實(shí)驗(yàn)?zāi)康牧私夂驼莆占拇嫫鞣峙浜蛢?nèi)存分配的有關(guān)技術(shù)。二、實(shí)驗(yàn)要求1、用C語(yǔ)言實(shí)現(xiàn)最近最久未使用（LRU）置換算法。2、了解內(nèi)存分頁(yè)管理策略3、掌握調(diào)頁(yè)策略4、LRU調(diào)度算法D的模擬實(shí)現(xiàn)三、實(shí)驗(yàn)內(nèi)容LRU置換算法是選擇最近最久未使用的頁(yè)面予以置換。該算法賦予每

12、個(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è)比較合理的置換算法。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è)比較合理的置換算法。四、實(shí)驗(yàn)原理 LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁(yè)

13、面各有多少時(shí)間未被進(jìn)程訪問(wèn)，以及如何快速地知道哪一頁(yè)是最近最久未使用的頁(yè)面，須有以下兩類(lèi)硬件之一的支持： 寄存器 為了記錄某個(gè)進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為 R=Rn-1Rn-2Rn-3R2R1R0 當(dāng)進(jìn)程訪問(wèn)某物理塊時(shí)，要將相應(yīng)寄存器的Rn-1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個(gè)整數(shù)，那么具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁(yè)面，就是最近最久未使用的頁(yè)面。如圖1示出了某進(jìn)程在內(nèi)存中具有8個(gè)頁(yè)面，為每個(gè)內(nèi)存頁(yè)面配置一個(gè)8位寄存器時(shí)的LRU訪問(wèn)情況。這里，把8個(gè)內(nèi)存頁(yè)面的序號(hào)分別定為1

14、8。由圖可以看出，第7個(gè)內(nèi)存頁(yè)面的R值最小，當(dāng)發(fā)生缺頁(yè)時(shí)首先將它置換出去。棧 可利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)民，而棧底則是最近最久未使用的頁(yè)面的頁(yè)面號(hào)。 五、實(shí)驗(yàn)結(jié)果輸入的數(shù)據(jù)為六、源程序代碼#include #include #include#include #define M 4 #define N 12#define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-|n)/*表格控制*/ typedef struct Page int

15、num;/*記錄頁(yè)面號(hào)*/ int time;/*記錄調(diào)入內(nèi)存時(shí)間*/ Page;/* 頁(yè)面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/ /*全局變量*/ Page page_inM;/*內(nèi)存單元數(shù)*/ int cMN;/*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū) 第M的位置在第N次調(diào)入時(shí)的數(shù)值*/ int queue100;/*記錄調(diào)入隊(duì)列*/ int K;/*調(diào)入隊(duì)列計(jì)數(shù)變量*/ /*初始化內(nèi)存單元、緩沖區(qū)*/ void Init(Page *page_in,int cMN) int i,j; for(i=0;iN;i+) page_ini.num=-1; page_ini.time=N-i-1; for(i

16、=0;iM;i+) for(j=0;jN;j+) cij=-1; /*取得在內(nèi)存中停留最久的頁(yè)面,默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面*/ int GetMax(Page *page_in) int i; int max=-1; int tag=0; for(i=0;imax) max=page_ini.time; tag=i; return tag; /*判斷頁(yè)面是否已在內(nèi)存中*/ int Equation(int fold,Page *page_in) int i; for(i=0;i=0) / 頁(yè)面在內(nèi)存中 page_inval.time=0; /該頁(yè)面的時(shí)間置零for(i=0;iM;i+) /其

17、余的頁(yè)面的時(shí)間都增加if (i!=val) page_ini.time+; else /頁(yè)面不在內(nèi)存中，從外部調(diào)入 queue+K=fold;/*記錄調(diào)入頁(yè)面*/ val=GetMax(page_in); /找到最近最久未使用的頁(yè)面編號(hào) page_inval.num=fold; /調(diào)入page_inval.time=0; for(i=0;iM;i+) if (i!=val) page_ini.time+; /*主程序*/ int main() int aN=1,1,2,4,3,5,2,1,6,7,1,3; int i,j; char judge = n;/用于控制循環(huán)while(judge =

18、 n) srand(int)time(0);/產(chǎn)生隨機(jī)數(shù)種子 printf(待調(diào)入的頁(yè)面號(hào):n); for(i=0; iN; i+) ai = (int)(10.0*rand()/(RAND_MAX+1.0) + 1);/產(chǎn)生隨機(jī)數(shù) printf(%d ,ai); printf(n); K=-1; Init(page_in, c); / 初始化內(nèi)存單元、緩沖區(qū) for(i=0;iN;i+) Lru(ai,page_in); c0i=ai; /記錄當(dāng)前的內(nèi)存單元中的頁(yè)面 for(j=0;jM;j+) /將內(nèi)存中的四個(gè)頁(yè)面在第i次的情況記錄下cji=page_inj.num; /結(jié)果輸出 prin

19、tf(內(nèi)存狀態(tài)為：n); Myprintf; for(j=0;jN;j+) printf(|%2d ,aj); printf(|n); Myprintf; for(i=0;iM;i+) for(j=0;jN;j+) if(cij=-1) printf(| ); /printf(|%2c ,32); else printf(|%2d ,cij); printf(|n); Myprintf; printf(n調(diào)入隊(duì)列為:); for(i=0;i cm.getMaxDevCap()cm.setMaxDevCap(this.dataLength);public void setDataLength(i

20、nt dataLength) this.dataLength = dataLength;public int getDataLength() return dataLength;public void setDatas(String datas) this.datas = datas;public String getDatas() return datas;ChannelManager.classpackage passage;import java.util.ArrayList;import java.util.List;public class ChannalManager implem

21、ents Runnable private String interrupt;/提示中斷信號(hào)private int maxDevCap=0;/所有設(shè)備的最大傳輸數(shù)據(jù)長(zhǎng)度private List Devices;/所有外圍設(shè)備private List memory;/存儲(chǔ)器public ChannalManager()errupt=none;this.Devices = new ArrayList();this.Devices.add(new Device();this.Devices.add(new Device();this.Devices.add(new Device();

22、this.memory = new ArrayList();this.memory.add(new Device(daiwei,this);this.memory.add(new Device(love,this);this.memory.add(new Device(computer,this);public void setInterrupt(String interrupt) errupt = interrupt;public String getInterrupt() return interrupt;public void setMaxDevCap(int maxDe

23、vCap) this.maxDevCap = maxDevCap;public int getMaxDevCap() return maxDevCap;public void setDevices(List devices) Devices = devices;public List getDevices() return Devices;public void printDevice()for(Device d : this.Devices)System.out.println(d.getDatas();Overridepublic void run() /通道處理器進(jìn)行數(shù)據(jù)傳送/ TODO

24、 Auto-generated method stubfor(int fence = 0 ;fence this.maxDevCap; fence+) for(int i = 0;i this.Devices.size() ; i+) if(fence this.memory.get(i).getDataLength() this.Devices.get(i).setDatas(this.memory.get(i).getDatas().substring(0, fence+1); printDevice(); printDevice(); errupt=finish;/傳送完后發(fā)中斷RunningCpu.classpackage passage;public class RunningCpu private ChannalManager channalMg;public RunningCpu()this.channalMg = new ChannalManager();public void setChannalMg(ChannalManager channalMg) this.channalMg = channalMg;public C