計(jì)算機(jī)系統(tǒng)基礎(chǔ)2模擬題答案

1、計(jì)算機(jī)系統(tǒng)基礎(chǔ)2模擬題答案1.(a) 在流水線處理器中，什么是冒險(xiǎn)(hazard)？在什么情況下出現(xiàn)冒險(xiǎn)？對于冒險(xiǎn)一般如何處理？(b) 什么是 CISC？什么是 RISC？它們各自有什么特點(diǎn)和區(qū)別？（c）什么是虛擬地址？虛擬地址有什么作用？（d）解釋下列名詞：大端（big endian）、小端(little endian)、主機(jī)序、網(wǎng)絡(luò)序（a） 流水線沖突：在流水線系統(tǒng)中，由于相關(guān)的存在，使得指令不能在指定的周期內(nèi)完成。流水線沖突包括結(jié)構(gòu)沖突、數(shù)據(jù)沖突和控制沖突三種。1） 結(jié)構(gòu)沖突：因?yàn)橛布Y源滿足不了指令重疊執(zhí)行要求而產(chǎn)生的沖突。解決方法：設(shè)置獨(dú)立的數(shù)據(jù)、指令cache；阻塞后面指令運(yùn)行2）

2、 數(shù)據(jù)沖突：一條指令依賴于前面指令的運(yùn)行結(jié)果而產(chǎn)生的沖突。解決方法：定向、流水線互鎖和編譯器指令調(diào)度3） 控制沖突：流水線遇到跳轉(zhuǎn)指令或者其它更改pc值的指令。解決方法：預(yù)測指令運(yùn)行、延遲跳轉(zhuǎn)、盡快計(jì)算跳轉(zhuǎn)目標(biāo)地址。（b）CISC 是“復(fù)雜指令集”的簡稱，復(fù)雜指令集指令數(shù)量很多，部分指令的延遲很長，編 碼是可變長度的。RISC 是“精簡指令集”的簡稱，精簡指令集指令數(shù)量少得多，沒有較長延遲 的指令，編碼是固定長度的。（c）虛擬地址是操作系統(tǒng)提供的對主存的抽象，它為每個進(jìn)程提供了一個大的、一致的 和私有的地址空間。它的作用是 1）它將主存看成一個存儲在磁盤上的地址空間的高速緩存， 在主存中只保存

3、活動區(qū)域，并根據(jù)需要在主存和磁盤之間來回傳送數(shù)據(jù)，通過這種方式，它 高效的利用了主存 2）它為每個進(jìn)程提供了一致的地址空間，從而簡化了存儲器管理 3）它 保護(hù)了每個進(jìn)程的地址空間不被其它進(jìn)程破壞。(d) 最低有效字節(jié)在最前面的方式，稱為小端法，最低有效字節(jié)在最后面的方式，稱為大 端法。主機(jī)序是指機(jī)器 CPU 采用的字節(jié)表示方法。網(wǎng)絡(luò)序是 TCP/IP 中規(guī)定的數(shù)據(jù)表示格式，與 CPU 類型和操作系統(tǒng)無關(guān)，網(wǎng)絡(luò)序采用大端排列。2.有如下假設(shè)：（1） 存儲器是字節(jié)尋址的；（2） 存儲器訪問的是 1 字節(jié)的字（不是 4 字節(jié)的字）；（3） 地址寬度為 13 位；（4） 高速緩存是 2 路組相聯(lián)的（E

4、=2），塊大小為 4 字節(jié)（B=4），有 8 個組（S=8）； 高速緩存的內(nèi)容如下，所有數(shù)字都是以十六進(jìn)制來表示的：（a）下面的放開展示的是地址格式（每個小方框一個位）。指出（在圖中標(biāo)出）用來確定下列內(nèi)容的字段：（1） CO 高速緩存塊偏移（2） CI 高速緩存組索引（3） CT 高速緩存標(biāo)記（b）假設(shè)一個程序運(yùn)行在上述機(jī)器上，它引用 0xE34 處的 1 個字節(jié)的字。指出訪問的 高速緩存條目和十六進(jìn)制表示的返回的高速緩存字節(jié)值。指出是否會發(fā)生緩存不命中， 如果出現(xiàn)緩存不命中，用“-”來表示“返回的高速緩存字節(jié)”。(a) 由于塊大小是 4(22)，那么需要兩位來表示塊內(nèi)偏移；由于緩存一共有 8

5、(23)組，那么 需要 3 位來表示組索引；由于地址一共 13 位，那么標(biāo)記位為 8(13 2 - 3)位；按照 高速緩存地址劃分的規(guī)則（從高位到低位依次是標(biāo)記，組索引，塊內(nèi)偏移），13 位地 址可標(biāo)記為：(b) 地址 0xE34 的二進(jìn)制表示為：0b111000110100；根據(jù)上面的討論，末兩位為塊內(nèi)偏 移 0b00(0x0) ， 末 兩位 之前 三位 為 組 索引 0b101(0x5) ， 末 五 位 之前 是 標(biāo)記 0b1110001(0x71)；通過查表可以找到組號為 5，標(biāo)記為 0x71 的位置，該位置有效位 為 1，讀取第一個字節(jié)得到數(shù)據(jù) 0xB。3.（a） 確定下面的 mall

6、oc 請求序列得到的塊大小和頭部值。假設(shè)：（1） 分配器維持雙字對齊，使用隱式空閑鏈表，格式如下圖所示。（2） 塊大小向上攝入為最接近的 8 字節(jié)的倍數(shù)。7 / 77 / 7(b) 確定下面每種對齊要求和塊格式的組合的最小塊大小。假設(shè)：隱式空閑鏈表，不允許有效載荷為零，頭部和腳部放在 4 字節(jié)的字中。（a） 塊大小包括塊頭部大?。ㄈ绻麎K有尾部的話，那么也包含尾部大?。?，當(dāng)請求 3 字節(jié)大小的塊時，需要 3+4=7 字節(jié)的內(nèi)容，而根據(jù)條件的 8 字節(jié)倍數(shù)要求，塊 的大小確定為 8 字節(jié)（最后一字節(jié)雖然沒有申請，但也分配了）；根據(jù)圖片顯示 的塊結(jié)構(gòu)，塊頭部值的最后三位為元數(shù)據(jù)，元數(shù)據(jù)頭兩位始終為

7、0，最后一位為1 表示已占用的塊；塊頭部值可計(jì)算為塊大小加上塊元數(shù)據(jù)值，即 0x8+0b001， 即頭部值為 9。根據(jù)上面的方法，malloc(11)需要分配 16 字節(jié)的塊，頭部值為 17(0x11)；malloc(20) 需要分配 24 字節(jié)的塊，頭部值為 25（0x19）;malloc(21)需要分配 32 字節(jié)的塊， 頭部值為 33(0x21)(c) 第一項(xiàng)，塊對齊單字，已分配和空閑塊都有頭部和尾部，那么頭部和尾部數(shù)據(jù)需要8 字節(jié)；而有效載荷不允許為 0，那么大于 8 且能被 4 整除的最小正整數(shù)為 12，因 此最小塊大小為 12。第二項(xiàng)，塊對齊單字，已分配塊可以省略腳部，那么僅考慮已

8、分配塊，頭部數(shù)據(jù)需 要 4 個字節(jié)；有小載荷不允許為 0，那么大于 4 且能被 4 整除的最小正整數(shù)為 8， 因此最小塊大小為 8。第三項(xiàng)，大于 8 且能被 8 整除的最小整數(shù)為 16。 第四項(xiàng)，大于 4 且能被 8 整除的最小整數(shù)為 8。4.(a) 下面是一個并行求和算法，將其補(bǔ)充完整。#include #include #include #define MAXTHREADS 32/* Global shared variables */ long psumMAXTHREADS; long nelems_per_thread;void *sum(void *vargp)/* Extract

9、the thread id */int myid = *(int *)vargp);/* Start element index */long start = myid * nelems_per_thread;/* End element index */long end = start + nelems_per_thread;long i, sum = 0;for (i = start; i end; i+) sum += i;psummyid = sum;return NULL;int main(int argc, char *argv)long i, nelems, log_nelems

10、, nthreads, result = 0;pthread_t tidMAXTHREADS;int myidMAXTHREADS;/* Get input arguments */if (argc != 3) printf(Usage:%s n, argv0);exit(0);nthreads = atoi(argv1); log_nelems = atoi(argv2); nelems = (1L log_nelems);nelems_per_thread = nelems / nthreads;/* Create peer threads and wait for them to fin

11、ish */for (i = 0; i nthreads; i+) myidi = i; (1) ;for (i = 0; i nthreads; i+) (2) ;/* Add up the partial sums computed by each thread */for (i = 0; i nthreads; i+) (3) ;/* Check final answer */if (result != (nelems *(nelems - 1)/2) printf(Error: result=%ldn, result);exit(0);(b) 思考下面的程序，它視圖使用一對信號量來實(shí)現(xiàn)互斥。初始時： s = 1, t = 0線程 1：P(s)V(s)P(t)V(t)線程 2：P(s)V(s)P(t)*(t) (1) 畫出這個程序的進(jìn)度圖。(2) 它總是死鎖嗎？請分析原因(3) 如果是，那么對初始信號量的值做那些改變就能消除潛在的死鎖呢？(4) 畫出得到的無死鎖程序的進(jìn)度條。(a) (