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

1.(a) 在流水線(xiàn)處理器中，什么是冒險(xiǎn)(hazard)？在什么情況下出現(xiàn)冒險(xiǎn)？對(duì)于冒險(xiǎn)一般如何處理？(b) 什么是 CISC？什么是 RISC？它們各自有什么特點(diǎn)和區(qū)別？（c）什么是虛擬地址？虛擬地址有什么作用？（d）解釋下列名詞：大端（big endian）、小端(little endian)、主機(jī)序、網(wǎng)絡(luò)序（a） 流水線(xiàn)沖突：在流水線(xiàn)系統(tǒng)中，由于相關(guān)的存在，使得指令不能在指定的周期內(nèi)完成。流水線(xiàn)沖突包括結(jié)構(gòu)沖突、數(shù)據(jù)沖突和控制沖突三種。1） 結(jié)構(gòu)沖突：因?yàn)橛布Y源滿(mǎn)足不了指令重疊執(zhí)行要求而產(chǎn)生的沖突。解決方法：設(shè)置獨(dú)立的數(shù)據(jù)、指令cache；阻塞后面指令運(yùn)行2） 數(shù)據(jù)沖突：一條指令依賴(lài)于前面指令的運(yùn)行結(jié)果而產(chǎn)生的沖突。解決方法：定向、流水線(xiàn)互鎖和編譯器指令調(diào)度3） 控制沖突：流水線(xiàn)遇到跳轉(zhuǎn)指令或者其它更改pc值的指令。解決方法：預(yù)測(cè)指令運(yùn)行、延遲跳轉(zhuǎn)、盡快計(jì)算跳轉(zhuǎn)目標(biāo)地址。（b）CISC 是“復(fù)雜指令集”的簡(jiǎn)稱(chēng)，復(fù)雜指令集指令數(shù)量很多，部分指令的延遲很長(zhǎng)，編 碼是可變長(zhǎng)度的。RISC 是“精簡(jiǎn)指令集”的簡(jiǎn)稱(chēng)，精簡(jiǎn)指令集指令數(shù)量少得多，沒(méi)有較長(zhǎng)延遲 的指令，編碼是固定長(zhǎng)度的。（c）虛擬地址是操作系統(tǒng)提供的對(duì)主存的抽象，它為每個(gè)進(jìn)程提供了一個(gè)大的、一致的 和私有的地址空間。它的作用是 1）它將主存看成一個(gè)存儲(chǔ)在磁盤(pán)上的地址空間的高速緩存， 在主存中只保存活動(dòng)區(qū)域，并根據(jù)需要在主存和磁盤(pán)之間來(lái)回傳送數(shù)據(jù)，通過(guò)這種方式，它 高效的利用了主存 2）它為每個(gè)進(jìn)程提供了一致的地址空間，從而簡(jiǎn)化了存儲(chǔ)器管理 3）它 保護(hù)了每個(gè)進(jìn)程的地址空間不被其它進(jìn)程破壞。(d) 最低有效字節(jié)在最前面的方式，稱(chēng)為小端法，最低有效字節(jié)在最后面的方式，稱(chēng)為大 端法。主機(jī)序是指機(jī)器 CPU 采用的字節(jié)表示方法。網(wǎng)絡(luò)序是 TCP/IP 中規(guī)定的數(shù)據(jù)表示格式，與 CPU 類(lèi)型和操作系統(tǒng)無(wú)關(guān)，網(wǎng)絡(luò)序采用大端排列。2.有如下假設(shè)：（1） 存儲(chǔ)器是字節(jié)尋址的；（2） 存儲(chǔ)器訪(fǎng)問(wèn)的是 1 字節(jié)的字（不是 4 字節(jié)的字）；（3） 地址寬度為 13 位；（4） 高速緩存是 2 路組相聯(lián)的（E=2），塊大小為 4 字節(jié)（B=4），有 8 個(gè)組（S=8）； 高速緩存的內(nèi)容如下，所有數(shù)字都是以十六進(jìn)制來(lái)表示的：（a）下面的放開(kāi)展示的是地址格式（每個(gè)小方框一個(gè)位）。指出（在圖中標(biāo)出）用來(lái)確定下列內(nèi)容的字段：（1） CO 高速緩存塊偏移（2） CI 高速緩存組索引（3） CT 高速緩存標(biāo)記（b）假設(shè)一個(gè)程序運(yùn)行在上述機(jī)器上，它引用 0xE34 處的 1 個(gè)字節(jié)的字。指出訪(fǎng)問(wèn)的 高速緩存條目和十六進(jìn)制表示的返回的高速緩存字節(jié)值。指出是否會(huì)發(fā)生緩存不命中， 如果出現(xiàn)緩存不命中，用“-”來(lái)表示“返回的高速緩存字節(jié)”。(a) 由于塊大小是 4(22)，那么需要兩位來(lái)表示塊內(nèi)偏移；由于緩存一共有 8(23)組，那么 需要 3 位來(lái)表示組索引；由于地址一共 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)；通過(guò)查表可以找到組號(hào)為 5，標(biāo)記為 0x71 的位置，該位置有效位 為 1，讀取第一個(gè)字節(jié)得到數(shù)據(jù) 0xB。3.（a） 確定下面的 malloc 請(qǐng)求序列得到的塊大小和頭部值。假設(shè)：（1） 分配器維持雙字對(duì)齊，使用隱式空閑鏈表，格式如下圖所示。（2） 塊大小向上攝入為最接近的 8 字節(jié)的倍數(shù)。(b) 確定下面每種對(duì)齊要求和塊格式的組合的最小塊大小。假設(shè)：隱式空閑鏈表，不允許有效載荷為零，頭部和腳部放在 4 字節(jié)的字中。（a） 塊大小包括塊頭部大?。ㄈ绻麎K有尾部的話(huà)，那么也包含尾部大?。?，當(dāng)請(qǐng)求 3 字節(jié)大小的塊時(shí)，需要 3+4=7 字節(jié)的內(nèi)容，而根據(jù)條件的 8 字節(jié)倍數(shù)要求，塊 的大小確定為 8 字節(jié)（最后一字節(jié)雖然沒(méi)有申請(qǐng)，但也分配了）；根據(jù)圖片顯示 的塊結(jié)構(gòu)，塊頭部值的最后三位為元數(shù)據(jù)，元數(shù)據(jù)頭兩位始終為 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)，塊對(duì)齊單字，已分配和空閑塊都有頭部和尾部，那么頭部和尾部數(shù)據(jù)需要8 字節(jié)；而有效載荷不允許為 0，那么大于 8 且能被 4 整除的最小正整數(shù)為 12，因 此最小塊大小為 12。第二項(xiàng)，塊對(duì)齊單字，已分配塊可以省略腳部，那么僅考慮已分配塊，頭部數(shù)據(jù)需 要 4 個(gè)字節(jié)；有小載荷不允許為 0，那么大于 4 且能被 4 整除的最小正整數(shù)為 8， 因此最小塊大小為 8。第三項(xiàng)，大于 8 且能被 8 整除的最小整數(shù)為 16。 第四項(xiàng)，大于 4 且能被 8 整除的最小整數(shù)為 8。4.(a) 下面是一個(gè)并行求和算法，將其補(bǔ)充完整。#include #include #include #define MAXTHREADS 32/* Global shared variables */ long psumMAXTHREADS; long nelems_per_thread;void *sum(void *vargp)/* 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, nelems, log_nelems, 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 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) 思考下面的程序，它視圖使用一對(duì)信號(hào)量來(lái)實(shí)現(xiàn)互斥。初始時(shí)： s = 1, t = 0線(xiàn)程 1：P(s)V(s)P(t)V(t)線(xiàn)程 2：P(s)V(s)P(t)*(t) (1) 畫(huà)出這個(gè)程序的進(jìn)度圖。(2) 它總是死鎖嗎？請(qǐng)分析原因(3) 如果是，那么對(duì)初始信號(hào)量的值做那些改變就能消除潛在的死鎖呢？(4) 畫(huà)出得到的無(wú)死鎖程序的進(jìn)度條。(a) (1