計算機體系結(jié)構(gòu)報告

1、中南大學計算機體系結(jié)構(gòu)實驗報告學生姓名 代巍 指導教師 雷向東 學 院 信息科學與工程學院 專業(yè)班級 信安1201班 學 號 0909121615 完成時間 2014年11月20日 實驗 1 對指令操作碼進行霍夫曼編碼一、實驗目的了解和掌握指令編碼的基本要求和基本原理二、實驗要求使用編程工具編寫一個程序，對一組指令進行霍夫曼編碼，并輸出最后的編碼結(jié)果以及對指令碼的長度進行評價。與擴展操作碼和等長編碼進行比較。問題描述以及問題分析：我們舉例說明此問題，例如：有一組指令的操作碼共分七類，它們出現(xiàn)概率如下表所示：P1 P2 P3 P4 P5 P6 P70.45 0.30 0.15 0.05 0.03

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

3、建立好哈弗曼樹之后，要使得哈弗曼的左子樹的編碼為0，右子樹的編碼為1?？梢酝ㄟ^這個來確定字符的哈弗曼編碼。 四、實驗原理構(gòu)造 HUFFMAN 樹所要做的工作：1、先對各指令操作碼的出現(xiàn)概率進行排序，構(gòu)造一個有序鏈表。2、再取出兩個最小的概率節(jié)點相加，生成一個生的節(jié)點加入到鏈表中，同時從兩表中刪除此兩個節(jié)點。3、在對鏈表進行排序，鏈表是否只有一個節(jié)點，是則 HUFFAN 樹構(gòu)造完畢，否則繼續(xù)做 2 的操作。為此設計一個工作鏈表（鏈表的元素時類，此類的功能相當結(jié)構(gòu)。）、HUFFMAN 樹節(jié)點、HUFFMAN 編碼表節(jié)點五、實驗結(jié)果輸入的n為4，各節(jié)點的權(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é)點結(jié)構(gòu)體 */ /* 構(gòu)造一顆哈夫曼樹

5、 */void HuffmanTree (HNodeType HuffNodeMAXNODE, int n) /* i、j： 循環(huán)變量，m1、m2：構(gòu)造哈夫曼樹不同過程中兩個最小權(quán)值結(jié)點的權(quán)值， x1、x2：構(gòu)造哈夫曼樹不同過程中兩個最小權(quán)值結(jié)點在數(shù)組中的序號。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼樹數(shù)組 HuffNode 中的結(jié)點 */ 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; /實際值，可根據(jù)情況替換為字母 /* end for */ /* 輸入 n 個葉子結(jié)點的權(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 樹 */ for (i=0; in-1; i+) m1=m2=MAXVALUE; /* m1、m2中存放兩個無父結(jié)點且結(jié)點權(quán)值最小的兩個結(jié)點 */ x1=x2=0; /* 找出所有結(jié)點中權(quán)值

7、最小、無父結(jié)點的兩個結(jié)點，并合并之為一顆二叉樹 */ 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 */ /* 設置找到的兩個子結(jié)點 x1、x2 的父結(jié)點信息 */ 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); /* 用于測試 */ printf (n); /* end for */ / int main(void) HNodeType HuffNodeMAXNODE; /*

9、定義一個結(jié)點結(jié)構(gòu)體數(shù)組 */ HCodeType HuffCodeMAXLEAF, cd; /* 定義一個編碼結(jié)構(gòu)體數(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é)點存在 */ if (HuffNodep.lchild

10、 = c) cd.bitcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求編碼的低一位 */ c=p; p=HuffNodec.parent; /* 設置下一循環(huán)條件 */ /* end while */ /* 保存求出的每個葉結(jié)點的哈夫曼編碼和編碼的起始位 */ 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); 實驗 2 使用 LRU 方法更新 Cache一、實驗目的了解和掌握寄存器分配和內(nèi)存分配的有關(guān)技術(shù)。二、實驗要求1、用C語言實現(xiàn)最近最久未使用（LRU）置換算法。2、了解內(nèi)存分頁管理策略3、掌握調(diào)頁策略4、LRU調(diào)度算法D的模擬實現(xiàn)三、實驗內(nèi)容LRU置換算法是選擇最近最久未使用的頁面予以置換。該算法賦予每

12、個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來經(jīng)歷的時間 T，當須淘汰一個頁面時，選擇現(xiàn)有頁面中 T 值最大的，即最近最久沒有訪問的頁面。這是一個比較合理的置換算法。Cache 更新結(jié)合數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，使用LRU的策略，對一組訪問序列進行內(nèi)部的LRU置換算法是選擇最近最久未使用的頁面予以置換。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來經(jīng)歷的時間 T，當須淘汰一個頁面時，選擇現(xiàn)有頁面中 T 值最大的，即最近最久沒有訪問的頁面。這是一個比較合理的置換算法。四、實驗原理 LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進程在內(nèi)存中的各個頁

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

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

15、num;/*記錄頁面號*/ int time;/*記錄調(diào)入內(nèi)存時間*/ Page;/* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實現(xiàn)設計*/ /*全局變量*/ Page page_inM;/*內(nèi)存單元數(shù)*/ int cMN;/*暫保存內(nèi)存當前的狀態(tài)：緩沖區(qū) 第M的位置在第N次調(diào)入時的數(shù)值*/ int queue100;/*記錄調(diào)入隊列*/ int K;/*調(diào)入隊列計數(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)存中停留最久的頁面,默認狀態(tài)下為最早調(diào)入的頁面*/ 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; /*判斷頁面是否已在內(nèi)存中*/ int Equation(int fold,Page *page_in) int i; for(i=0;i=0) / 頁面在內(nèi)存中 page_inval.time=0; /該頁面的時間置零for(i=0;iM;i+) /其

17、余的頁面的時間都增加if (i!=val) page_ini.time+; else /頁面不在內(nèi)存中，從外部調(diào)入 queue+K=fold;/*記錄調(diào)入頁面*/ val=GetMax(page_in); /找到最近最久未使用的頁面編號 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)生隨機數(shù)種子 printf(待調(diào)入的頁面號:n); for(i=0; iN; i+) ai = (int)(10.0*rand()/(RAND_MAX+1.0) + 1);/產(chǎn)生隨機數(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; /記錄當前的內(nèi)存單元中的頁面 for(j=0;jM;j+) /將內(nèi)存中的四個頁面在第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)入隊列為:); 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;/提示中斷信號private int maxDevCap=0;/所有設備的最大傳輸數(shù)據(jù)長度private List Devices;/所有外圍設備private List memory;/存儲器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() /通道處理器進行數(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