1、1.(a) 在流水線處理器中，什么是冒險(hazard)？在什么情況下出現冒險？對于冒險一般如何處理？(b) 什么是 CISC？什么是 RISC？它們各自有什么特點和區別？（c）什么是虛擬地址？虛擬地址有什么作用？（d）解釋下列名詞：大端（big endian）、小端(little endian)、主機序、網絡序（a） 流水線沖突：在流水線系統中，由于相關的存在，使得指令不能在指定的周期內完成。流水線沖突包括結構沖突、數據沖突和控制沖突三種。1） 結構沖突：因為硬件資源滿足不了指令重疊執行要求而產生的沖突。解決方法：設置獨立的數據、指令cache；阻塞后面指令運行2） 數據沖突：一條指令依賴于

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

3、和磁盤之間來回傳送數據，通過這種方式，它 高效的利用了主存 2）它為每個進程提供了一致的地址空間，從而簡化了存儲器管理 3）它 保護了每個進程的地址空間不被其它進程破壞。(d) 最低有效字節在最前面的方式，稱為小端法，最低有效字節在最后面的方式，稱為大 端法。主機序是指機器 CPU 采用的字節表示方法。網絡序是 TCP/IP 中規定的數據表示格式，與 CPU 類型和操作系統無關，網絡序采用大端排列。2.有如下假設：（1） 存儲器是字節尋址的；（2） 存儲器訪問的是 1 字節的字（不是 4 字節的字）；（3） 地址寬度為 13 位；（4） 高速緩存是 2 路組相聯的（E=2），塊大小為 4 字節

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

5、 位來表示組索引；由于地址一共 13 位，那么標記位為 8(13 2 - 3)位；按照 高速緩存地址劃分的規則（從高位到低位依次是標記，組索引，塊內偏移），13 位地 址可標記為：(b) 地址 0xE34 的二進制表示為：；根據上面的討論，末兩位為塊內偏 移 0b00(0x0) ， 末 兩位 之前 三位 為 組 索引 0b101(0x5) ， 末 五 位 之前 是 標記 0b1110001(0x71)；通過查表可以找到組號為 5，標記為 0x71 的位置，該位置有效位 為 1，讀取第一個字節得到數據 0xB。3.（a） 確定下面的 malloc 請求序列得到的塊大小和頭部值。假設：（1） 分配

6、器維持雙字對齊，使用隱式空閑鏈表，格式如下圖所示。（2） 塊大小向上攝入為最接近的 8 字節的倍數。(b) 確定下面每種對齊要求和塊格式的組合的最小塊大小。假設：隱式空閑鏈表，不允許有效載荷為零，頭部和腳部放在 4 字節的字中。（a） 塊大小包括塊頭部大小（如果塊有尾部的話，那么也包含尾部大小），當請求 3 字節大小的塊時，需要 3+4=7 字節的內容，而根據條件的 8 字節倍數要求，塊 的大小確定為 8 字節（最后一字節雖然沒有申請，但也分配了）；根據圖片顯示 的塊結構，塊頭部值的最后三位為元數據，元數據頭兩位始終為 0，最后一位為1 表示已占用的塊；塊頭部值可計算為塊大小加上塊元數據值，即

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

8、能被 4 整除的最小正整數為 8， 因此最小塊大小為 8。第三項，大于 8 且能被 8 整除的最小整數為 16。 第四項，大于 4 且能被 8 整除的最小整數為 8。4.(a) 下面是一個并行求和算法，將其補充完整。#include <pthread.h>#include <stdlib.h>#include <stdio.h>#define MAXTHREADS 32/* Global shared variables */ long psumMAXTHREADS; long nelems_per_thread;void *sum(void *vargp)

9、/* Extract 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, ne

10、lems, log_nelems, nthreads, result = 0;pthread_t tidMAXTHREADS;int myidMAXTHREADS;/* Get input arguments */if (argc != 3) printf("Usage:%s <nthreads> <log_nelems>n", argv0);exit(0);nthreads = atoi(argv1); log_nelems = atoi(argv2); nelems = (1L << log_nelems);nelems_per_th

11、read = nelems / nthreads;/* Create peer threads and wait for them to finish */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) 思考下面的程序，它視圖使用一對信號量來實現互斥。初始時： s = 1, t = 0線程 1：P(s)V(s)P(t)V(t)線程 2：P(s)V(s)P(t)*(t) (1) 畫出這個程序的進度圖。(2) 它總是死鎖嗎？請分析原因(3) 如果是，那么對初始信號量的值做那些改變就能消除潛在的死鎖呢？(4) 畫出得到的無死鎖程序的進度條。(a) (1)