浙江大學(xué)計(jì)算機(jī)專業(yè)考博試題計(jì)算機(jī)軟件及應(yīng)用it計(jì)算機(jī)專業(yè)資料

1、2000年春季浙江大學(xué)計(jì)算機(jī)考博試題操作系統(tǒng)一、 非搶占式系統(tǒng)和搶占式操作系統(tǒng)的區(qū)別，實(shí)時(shí)os為何要采用搶占式系統(tǒng)？二、 按缺頁(yè)率大小排列下述算法1、 lru 2、fifo 3、second change 4、optimal 順序算法belady異常1optimalno2lruno3second changeyes4fifoyes三、 進(jìn)程進(jìn)入就緒隊(duì)列后的等待時(shí)間+運(yùn)行時(shí)間=周轉(zhuǎn)時(shí)間，現(xiàn)有三個(gè)進(jìn)程：進(jìn)程進(jìn)入隊(duì)列時(shí)間（s）執(zhí)行時(shí)間（s）p108p20.44p3111、 對(duì)非搶占式系統(tǒng)，若采用最短任務(wù)優(yōu)先，請(qǐng)計(jì)算三個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間。采用最短任務(wù)優(yōu)先算法時(shí)，進(jìn)程運(yùn)行情況如下：進(jìn)程進(jìn)入隊(duì)列時(shí)間（s

2、）開(kāi)始時(shí)間（s）執(zhí)行時(shí)間（s）結(jié)束時(shí)間（s）周轉(zhuǎn)時(shí)間（s）p100888p20.4941312.6p318198三個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間=（8+12.6+8）/3=9.53（s）注意：帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間2、 若cpu空等1s后再執(zhí)行進(jìn)程，請(qǐng)計(jì)算三個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間。進(jìn)程進(jìn)入隊(duì)列時(shí)間（s）開(kāi)始時(shí)間（s）執(zhí)行時(shí)間（s）結(jié)束時(shí)間（s）周轉(zhuǎn)時(shí)間（s）p10681414p20.42465.4p311121三個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間=（14+5.4+1）/3=6.8（s）四、 有三個(gè)作業(yè)對(duì)空間要求分別為250k，412k，523k，342k，現(xiàn)內(nèi)存分區(qū)大小為200k，300k，400k，500k

3、，600k，若分別采用first-fit，best-fit和worst-fit分配結(jié)果如何？1、first-fit：從頭到尾搜索整個(gè)有效空間，找到第1個(gè)滿足條件的存儲(chǔ)塊時(shí)，即返回。250k作業(yè)裝到300k內(nèi)存分區(qū)412k作業(yè)裝到500k內(nèi)存分區(qū)523k作業(yè)裝到600k內(nèi)存分區(qū)342k作業(yè)裝到400k內(nèi)存分區(qū)2、best-fit：搜索整個(gè)有效空間，找出滿足條件的存儲(chǔ)塊中，最小的一個(gè)，返回。250k作業(yè)裝到300k內(nèi)存分區(qū)412k作業(yè)裝到500k內(nèi)存分區(qū)523k作業(yè)裝到600k內(nèi)存分區(qū)342k作業(yè)裝到400k內(nèi)存分區(qū)3、worst-fit：搜索整個(gè)有效空間，找出滿足條件的存儲(chǔ)塊中，最大的一個(gè)，返回

4、。（采用這種策略，是考慮到，被選中的存儲(chǔ)塊割去所申請(qǐng)的長(zhǎng)度后，留下的部分還相對(duì)較大，比best-fit算法留下的部分更有用）250k作業(yè)裝到600k內(nèi)存分區(qū)412k作業(yè)裝到500k內(nèi)存分區(qū)523k作業(yè)暫時(shí)等待342k作業(yè)裝到400k內(nèi)存分區(qū)五、 若一個(gè)系統(tǒng)有4個(gè)同樣的資源，可供三個(gè)進(jìn)程共享，每個(gè)進(jìn)程最多占用2個(gè)資源，根據(jù)進(jìn)程死鎖的四個(gè)條件，說(shuō)明此系統(tǒng)不會(huì)產(chǎn)生死鎖。答：如果系統(tǒng)發(fā)生死鎖，必然是系統(tǒng)中的3個(gè)進(jìn)程都占用了1個(gè)資源，然后申請(qǐng)另外1個(gè)資源。因?yàn)橄到y(tǒng)中共有4個(gè)資源，必然會(huì)有一個(gè)進(jìn)程得到2個(gè)資源，則這個(gè)進(jìn)程不再需要更多的資源，它必然會(huì)執(zhí)行完，然后釋放所有的資源，這樣就不會(huì)導(dǎo)致死鎖。六、 某個(gè)

5、操作系統(tǒng)共支持5000個(gè)用戶，若通過(guò)對(duì)用戶的權(quán)限和文件屬性的控制來(lái)實(shí)現(xiàn)只有其中4990個(gè)用戶可以訪問(wèn)文件devlist，可以采用兩種控制策略，請(qǐng)比較其區(qū)別。答：在unix中有兩種控制策略可以實(shí)現(xiàn)：1、 建立一張包含所有4990個(gè)用戶名字的存取控制表；2、 把所有4990個(gè)用戶放入一個(gè)組中，并設(shè)置這個(gè)組的存取權(quán)限。由于這些用戶組受到系統(tǒng)限制，這個(gè)方案不一定總能實(shí)現(xiàn)比unix方案更有效的保護(hù)方案：規(guī)定所有的用戶都能存取文件信息，除非他們的名字出現(xiàn)在沒(méi)有存取權(quán)限的存取控制表中。據(jù)此，可以把余下的10個(gè)用戶的名字放入該存取控制表中，但是他們沒(méi)有給予任何存取權(quán)限。體系結(jié)構(gòu)一、1、寫(xiě)出三條計(jì)算機(jī)設(shè)計(jì)的定量

6、定理。2、若cache速度比內(nèi)存高10倍，若內(nèi)存利用率是90%，請(qǐng)問(wèn)系統(tǒng)的加速比為多少？1、計(jì)算機(jī)設(shè)計(jì)的定量定理：（1）amdahl定律；（2）高頻事件高速處理；（3）局部性原理2、系統(tǒng)加速比=1/(1-10%)+10%/10)=9.09二、cpu的操作數(shù)有三種存儲(chǔ)方式，是區(qū)別不同體系計(jì)算機(jī)的重要標(biāo)志。1、是哪三種存儲(chǔ)方式？2、對(duì)于c=a+b，請(qǐng)寫(xiě)出三種方式的實(shí)現(xiàn)程序。cpu的操作數(shù)有三種存儲(chǔ)方式：1、堆棧結(jié)構(gòu)操作數(shù)是隱含在棧頂，首先要用壓棧指令將操作數(shù)從內(nèi)存壓入棧頂，運(yùn)算結(jié)果也在棧頂，要用退棧指令彈回內(nèi)存。根據(jù)這種結(jié)構(gòu)，只有push和pop指令才能訪問(wèn)存儲(chǔ)器。這種結(jié)構(gòu)完成上述操作需如下指令：

7、指令格式： 操作指令：push a存儲(chǔ)器操作數(shù) push apush b存儲(chǔ)器操作數(shù) push badd addpop c存儲(chǔ)器操作數(shù) pop c2、累加器結(jié)構(gòu)有一個(gè)操作數(shù)是隱含在累加器中而另一個(gè)是在存儲(chǔ)器中的，總操作數(shù)只有兩個(gè)，完成上述運(yùn)算只要三條指令。指令格式： 操作指令：load a存儲(chǔ)器操作數(shù) load aadd b存儲(chǔ)器操作數(shù) add batore c存儲(chǔ)器操作數(shù) store c3、寄存器結(jié)構(gòu)。根據(jù)操作數(shù)的位置有兩種情況，第一是alu運(yùn)算的操作數(shù)都在寄存器中的l/s結(jié)構(gòu)；另一種情況操作數(shù)部分在寄存器，部分在存儲(chǔ)器中。（1）指令格式： 操作指令：load r1 a存儲(chǔ)器操作數(shù) load

8、 r1，aload r2 b存儲(chǔ)器操作數(shù) load r2，badd r3 r1 r2 add r3，r1，r2store r3 c存儲(chǔ)器操作數(shù) store r3，c（2）指令格式： 操作指令：load r1 a存儲(chǔ)器操作數(shù) load r1，aadd r1 b存儲(chǔ)器操作數(shù) add r1，bstore r1 c存儲(chǔ)器操作數(shù) store r1，c三、1、流水線中結(jié)構(gòu)、數(shù)據(jù)、控制競(jìng)爭(zhēng)產(chǎn)生的原因。（1）結(jié)構(gòu)競(jìng)爭(zhēng)：由資源沖突引起。當(dāng)多條指令進(jìn)入流水線后，硬件不能支持所有可能的指令組合形式同時(shí)重疊執(zhí)行。（2）數(shù)據(jù)競(jìng)爭(zhēng)：由指令間數(shù)據(jù)相關(guān)而引起。某條指令的執(zhí)行依賴于前面指令的執(zhí)行結(jié)果，而指令的流水重疊操作使當(dāng)前

9、指令對(duì)數(shù)據(jù)使用時(shí)間提前了，而此時(shí)前面指令的執(zhí)行結(jié)果還沒(méi)有完成。（3）控制競(jìng)爭(zhēng)：由指令指針pc值的改變而引起。流水線中出現(xiàn)條件轉(zhuǎn)移及其它要改變pc指針的指令都將改變流水線中的后繼指令。2、寫(xiě)出有停頓周期的流水線系統(tǒng)的性能公式。流水線停頓(stall)：若 i 指令引起競(jìng)爭(zhēng)，在 i 指令之前進(jìn)入流水線的指令繼續(xù)執(zhí)行，而在 i 指令之后進(jìn)入流水線或尚未進(jìn)入流水線的指令停下來(lái)等待競(jìng)爭(zhēng)消除。cpiun cpiunspeedup = - = - cpip 1+流水線stall周期四、1、什么是ilp？2、ilp的必要性和實(shí)現(xiàn)技術(shù)。1、指令之間可重疊執(zhí)行性稱為指令級(jí)并行性（instruction paral

10、lelism-ilp)2、要提高計(jì)算機(jī)的性能，就要進(jìn)一步降低cpi，就必須挖掘指令間存在的不相關(guān)性和并行處理能力。為此，我們必須拓寬現(xiàn)有的流水線思想，采取一些新的更高的技術(shù)，充分增加和利用指令間的并行性。實(shí)現(xiàn)技術(shù)主要有：循環(huán)展開(kāi)、超標(biāo)量流水線、超級(jí)流水線、超長(zhǎng)指令字和軟件流水、路徑調(diào)度等。五、某cache容量為8kbytes，塊大小為32bytes，字節(jié)為64bits，地址長(zhǎng)度為32bits，對(duì)于直接映像系統(tǒng)，請(qǐng)分別寫(xiě)出構(gòu)成地址的索引（index）、標(biāo)志（tag）和塊地址的長(zhǎng)度。六、說(shuō)明并行計(jì)算面臨的兩大障礙。并行計(jì)算面臨的兩大障礙：1、在程序中可利用的并行性有限；2、通信代價(jià)過(guò)高。計(jì)算理論一

11、、1、根據(jù)圖靈機(jī)理論，說(shuō)明現(xiàn)代計(jì)算機(jī)系統(tǒng)的理論基礎(chǔ)。圖靈機(jī)裝置由下面幾個(gè)部分組成：一個(gè)無(wú)限長(zhǎng)的紙帶，一個(gè)讀寫(xiě)頭，內(nèi)部狀態(tài)，還有一個(gè)程序?qū)@個(gè)盒子進(jìn)行控制。這個(gè)裝置就是根據(jù)程序的命令以及它的內(nèi)部狀態(tài)進(jìn)行磁帶的讀寫(xiě)、移動(dòng)。圖靈機(jī)只要根據(jù)每一時(shí)刻讀寫(xiě)頭讀到的信息和當(dāng)前的內(nèi)部狀態(tài)進(jìn)行查表可以確定它下一時(shí)刻的內(nèi)部狀態(tài)和輸出動(dòng)作了。圖靈機(jī)在理論上能模擬現(xiàn)代數(shù)字計(jì)算機(jī)的一切運(yùn)算，可視為現(xiàn)代數(shù)字計(jì)算機(jī)的數(shù)學(xué)模型。實(shí)際上，一切可計(jì)算函數(shù)都等價(jià)于圖靈機(jī)可計(jì)算函數(shù)，而圖靈機(jī)可計(jì)算函數(shù)類(lèi)又等價(jià)于一般遞歸函數(shù)類(lèi)。2、說(shuō)明按喬姆斯基分類(lèi)，語(yǔ)言、語(yǔ)法、自動(dòng)機(jī)的關(guān)系。二、定義停機(jī)謂詞h(x,y)如下：三、1、證明遞歸集都是遞

12、歸可枚舉集。 2、舉例屬于遞歸可枚舉集但不是遞歸集的集合，并證明之。遞歸可枚舉集: 可數(shù)集合s被稱為遞歸可枚舉的, 如果存在生成s的元素的算法. 等價(jià)定義:可數(shù)集合s被稱為遞歸可枚舉的, 如果有一個(gè)圖靈機(jī), 在給定s的一個(gè)元素作為輸入的時(shí)候總是停機(jī), 并在給定的輸入不屬于s的時(shí)候永不停機(jī).遞歸集: 可數(shù)集合s被稱為遞歸的, 如果存在能夠在有限步驟內(nèi)判定任意給定元素是否屬于s的算法.四、1、證明l=（a，b）*|a，b的個(gè)數(shù)相同為上下文無(wú)關(guān)語(yǔ)言。選取字符串，s=uvxyz1）當(dāng)v和y都只含有一種符號(hào)時(shí)，這時(shí)字符串不可能含有個(gè)數(shù)相同的a、b。2）當(dāng)v或者y含有一種以上符號(hào)時(shí)， 2、并證明其不是正則

13、的。2000年秋季浙江大學(xué)計(jì)算機(jī)試題操作系統(tǒng)1、產(chǎn)生死鎖的必要條件。產(chǎn)生死鎖的必要條件如下：（1）互斥條件：進(jìn)程所競(jìng)爭(zhēng)的資源必須被互斥使用。（2）占有并等待條件：當(dāng)前已擁有的進(jìn)程，仍能申請(qǐng)新的資源；而且，當(dāng)該進(jìn)程因新的資源被其他進(jìn)程占用而阻塞時(shí)，它對(duì)自己已獲得的資源仍保持不放。（3）非搶占條件：進(jìn)程已獲得的資源，只能在使用完時(shí)自行釋放。（4）循環(huán)等待條件：存在一個(gè)至少包含兩個(gè)進(jìn)程的循環(huán)等待鏈，鏈中的每個(gè)進(jìn)程都正在等待下一個(gè)進(jìn)程所占有的資源。解決死鎖問(wèn)題常用的措施有如下幾種：（1）死鎖的預(yù)防：通過(guò)事先破壞死鎖產(chǎn)生的必要條件來(lái)防止死鎖的發(fā)生。（2）死鎖的避免：在進(jìn)程申請(qǐng)資源時(shí)，通過(guò)安全性檢查以決定

14、是否可以分配相應(yīng)資源，避免系統(tǒng)進(jìn)入不安全狀態(tài)，防止死鎖的發(fā)生。（3）死鎖的檢測(cè)與解除：系統(tǒng)通過(guò)死鎖檢測(cè)程序來(lái)判斷是否有進(jìn)程已進(jìn)入死鎖狀態(tài)，如果有，則通過(guò)撤銷(xiāo)某些死鎖進(jìn)程或者剝奪某些進(jìn)程的資源來(lái)解除死鎖現(xiàn)象。2、寫(xiě)出生產(chǎn)者和消費(fèi)者的互斥程序（書(shū)上的例子）。生產(chǎn)者-消費(fèi)者問(wèn)題（producer-consumer）是最著名的進(jìn)程同步問(wèn)題，常用于檢測(cè)進(jìn)程同步機(jī)制。它描述了一組生產(chǎn)者與一組消費(fèi)者，它們共享一個(gè)有界緩沖池，生產(chǎn)者向池中投入消息，消費(fèi)者從中取得消息。生產(chǎn)者-消費(fèi)者問(wèn)題實(shí)際上是相互合作進(jìn)程關(guān)系的一種抽象。例如，在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者；在輸出時(shí)，計(jì)算進(jìn)程是生產(chǎn)者，打印進(jìn)程是

15、消費(fèi)者。因此，該問(wèn)題具有很大實(shí)用價(jià)值。假定緩沖池中具有n個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)存放一個(gè)消息，可利用互斥信號(hào)量mutex使諸進(jìn)程對(duì)緩沖池實(shí)現(xiàn)互斥訪問(wèn)；利用資源信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)及滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從取走一個(gè)消息。生產(chǎn)者-消費(fèi)者問(wèn)題可描述如下：var mutex,empty,full:semaphore:=1,n,0; buffer:array0,n-1 of message; in,out:0,n-1:=0,0;begin parbegin producer:beg

16、inrepeat . . . producer a new message m; . . . p(empty); p(mutex); buffer(in):=m; in:=(in+1) mod n; v(mutex); v(full); until false end consumer:begin repeat p(full); p(mutex); m:=buffer(out); out:=(out+1) mod n; v(mutex); v(empty); consume message m; until false end parendend在生產(chǎn)者-消費(fèi)者問(wèn)題中應(yīng)當(dāng)注意：（1）在每個(gè)程序

17、中用于實(shí)現(xiàn)互斥的p(mutex)和v(mutex)必須成對(duì)出現(xiàn)。（2）對(duì)資源信號(hào)量empty和full的p、v操作同樣需要成對(duì)出現(xiàn)，但它們分別處于不同的程序中，例如，p(empty)在計(jì)算進(jìn)程中，而v(empty)則在打印進(jìn)程中，計(jì)算進(jìn)程因執(zhí)行p(empty)而阻塞，則以后將由打印進(jìn)程將它喚醒。（3）在每個(gè)程序中的p操作順序不能顛倒，應(yīng)先執(zhí)行對(duì)資源信號(hào)量的p操作，然后再執(zhí)行互斥信號(hào)量的p操作，否則可能引起進(jìn)程死鎖。3、寫(xiě)出可對(duì)文件和目錄進(jìn)行的操作。4、虛擬存儲(chǔ)頁(yè)面置換的幾種算法。5、談?wù)勀銓?duì)操作系統(tǒng)的設(shè)計(jì)和通用性的看法。6、舉例說(shuō)明cache在操作系統(tǒng)中的應(yīng)用。6、微內(nèi)核的優(yōu)點(diǎn)，列舉微內(nèi)核操作

18、系統(tǒng)的特點(diǎn)和實(shí)例。微內(nèi)核技術(shù)的主要優(yōu)點(diǎn)：（1）統(tǒng)一的接口，在用戶態(tài)和核心態(tài)之間無(wú)需進(jìn)程識(shí)別；（2）可伸縮性好，能適應(yīng)硬件更新和應(yīng)用變化；（3）可移植性好，所有與具體機(jī)器特征相關(guān)的代碼，全部隔離在微內(nèi)核中，如果操作系統(tǒng)要移植到不同的硬件平臺(tái)上，只需修改微內(nèi)核中極少代碼即可；（4）實(shí)時(shí)性好，微內(nèi)核可以方便地支持實(shí)時(shí)處理；（5）安全可靠性高，微內(nèi)核將安全性作為系統(tǒng)內(nèi)部特性來(lái)進(jìn)行設(shè)計(jì)，對(duì)外僅使用少量應(yīng)用編程接口；（6）支持分布式系統(tǒng)，支持多處理器的體系結(jié)構(gòu)和高度并行的應(yīng)用程序；（7）真正面向?qū)ο蟮牟僮飨到y(tǒng)。由于操作系統(tǒng)核心常駐內(nèi)存，而微內(nèi)核結(jié)構(gòu)精簡(jiǎn)了操作系統(tǒng)的核心功能，內(nèi)核規(guī)模比較小，一些功能都移到了

19、外存上，所以微內(nèi)核結(jié)構(gòu)十分適合嵌入式的專用系統(tǒng)，對(duì)于通用性較廣的系統(tǒng)，將使cpu的通信開(kāi)銷(xiāo)增大，從而影響到計(jì)算機(jī)的運(yùn)行速度。7、什么叫系統(tǒng)調(diào)用？編寫(xiě)一段包含系統(tǒng)調(diào)用的程序，完成如下工作：打開(kāi)一個(gè)文件，向文件中添加一個(gè)字符串，關(guān)閉該文件。 系統(tǒng)調(diào)用是操作系統(tǒng)提供給編程人員的唯一接口。利用系統(tǒng)調(diào)用，編程人員在源程序中動(dòng)態(tài)請(qǐng)求和釋放系統(tǒng)資源，調(diào)用系統(tǒng)中已有的功能來(lái)完成那些與機(jī)器硬件部分相關(guān)的工作以及控制程序的執(zhí)行速度等。系統(tǒng)調(diào)用如同一個(gè)黑匣子，對(duì)使用者屏蔽了具體操作動(dòng)作，只是提供了有關(guān)功能。有關(guān)文件系統(tǒng)的系統(tǒng)調(diào)用是用戶經(jīng)常使用的，包括文件的創(chuàng)建（create）、打開(kāi)(open)、讀(read)、寫(xiě)(

20、write)、關(guān)閉(close)等。下面是一個(gè)有關(guān)文件系統(tǒng)的系統(tǒng)調(diào)用的例子。main(argc,argv)int argc;char *argv;int fd1,fd2,fd3,n;char buf512,ch=n;fd1=open(argv1,0); /*打開(kāi)argv1對(duì)應(yīng)的文件，返回標(biāo)識(shí)符fd1*/fd2=open(argv2,0); /*打開(kāi)argv2對(duì)應(yīng)的文件，返回標(biāo)識(shí)符fd2*/fd1=create(argv3,0644); /*創(chuàng)建argv3對(duì)應(yīng)的文件，返回標(biāo)識(shí)符fd3*/while(n=read(fd1,buf,512)0) /*從fd1中讀n0) /*從fd2中讀n=512字節(jié)

21、入buf*/write(fd3,buf,n); /*將buf中n個(gè)字節(jié)寫(xiě)入fd3*/close(fd1); /*關(guān)閉文件*/close(fd2); /*關(guān)閉文件*/close(fd3); /*關(guān)閉文件*/體系結(jié)構(gòu)1、 寫(xiě)出cputime公式，并給出如何減少cputime。 cpu時(shí)間的計(jì)算公式：cputime = *i*cpi :時(shí)鐘周期，取決于硬件工藝和計(jì)算機(jī)組成； cpi:指令的平均時(shí)鐘周期數(shù)，與計(jì)算機(jī)組成和指令系統(tǒng)有關(guān)； i:程序指令數(shù)，取決于機(jī)器指令系統(tǒng)和編譯技術(shù)。2、 給出下列定義a、有哪幾種數(shù)據(jù)競(jìng)爭(zhēng)？b、什么是load/store機(jī)構(gòu)？ 3、畫(huà)出集中式共享存儲(chǔ)和分布式存儲(chǔ)的結(jié)構(gòu)圖，

22、并給出通信方式。 ieyx|qh* 集中式共享存儲(chǔ)器多處理器結(jié)構(gòu)圖：分布存儲(chǔ)器多處理器結(jié)構(gòu)圖：通信方式：1、shared memory2、message passing計(jì)算理論2001年浙江大學(xué)春季計(jì)算機(jī)試題操作系統(tǒng)1、邏輯地址空間為32位，物理地址空間為24位，頁(yè)大小為64k。計(jì)算理論原始遞歸函數(shù)的三個(gè)基本函數(shù)：2001年浙江大學(xué)秋季計(jì)算機(jī)試題操作系統(tǒng)1、 關(guān)于分頁(yè)虛擬內(nèi)存地址轉(zhuǎn)換2、 為什么要引入“進(jìn)程狀態(tài)”，畫(huà)出進(jìn)程狀態(tài)轉(zhuǎn)換圖。3、 塊設(shè)備和字符設(shè)備的特點(diǎn)和區(qū)別。 4、 打開(kāi)的文件，它的文件標(biāo)識(shí)，保存在系統(tǒng)什么地方？為什么？體系結(jié)構(gòu)1、 cputime公式及其理解，如何減少cputime

23、？ cpu時(shí)間的計(jì)算公式：cputime = *i*cpi :時(shí)鐘周期，取決于硬件工藝和計(jì)算機(jī)組成； cpi:指令的平均時(shí)鐘周期數(shù)，與計(jì)算機(jī)組成和指令系統(tǒng)有關(guān)； i:程序指令數(shù)，取決于機(jī)器指令系統(tǒng)和編譯技術(shù)。2、 一段循環(huán)相關(guān)性分析。3、 dlx機(jī)器一段代碼的數(shù)據(jù)競(jìng)爭(zhēng)，結(jié)構(gòu)競(jìng)爭(zhēng)分析及其解決方法。4、 并行處理的兩個(gè)障礙是什么？并行處理的兩個(gè)障礙是：（1）在程序中可利用的并行性有限；（2）通信代價(jià)過(guò)高。5、 關(guān)于cache直接映射的實(shí)現(xiàn)細(xì)節(jié)。直接映射：主存中的每個(gè)信息塊只能對(duì)應(yīng)cache中的一個(gè)特定塊。計(jì)算理論1、a,b上遞歸枚舉語(yǔ)言是否可數(shù)？證明。2、 l=a,b,c數(shù)目相同的語(yǔ)言是否cfl（

24、上下文無(wú)關(guān)語(yǔ)言），證明。3、 被2，3整除的非負(fù)整數(shù)的十進(jìn)制表示的集合是否正則。4、證明：若l是遞歸語(yǔ)言，則它的補(bǔ) 也是遞歸語(yǔ)言。證明：若turing機(jī)m = ( k，s，y，n)能夠判定l，則turing機(jī)m = ( k，s，y，n)能夠判定 。此處，除了m 反轉(zhuǎn)兩種特殊停機(jī)狀態(tài)y和n的作用以外，m與m是相同的，即定義如下m（w) = y 當(dāng)且僅當(dāng) m（w) = n ，因此m能夠判定 。2002年浙江大學(xué)春季計(jì)算機(jī)試題操作系統(tǒng)1、 處理機(jī)調(diào)度、內(nèi)存分配和資源分配三者結(jié)合，以打印機(jī)為例（銀行家算法）。2、 什么叫系統(tǒng)調(diào)用？編寫(xiě)一段包含系統(tǒng)調(diào)用的程序，完成如下工作：打開(kāi)一個(gè)文件，向文件中添加一個(gè)

25、字符串，關(guān)閉該文件。3、 談?wù)勀銓?duì)操作系統(tǒng)的設(shè)計(jì)和通用性的看法。4、 列舉微內(nèi)核操作系統(tǒng)的特點(diǎn)和實(shí)例。體系結(jié)構(gòu)1、 cpu time的計(jì)算公式及減少它的措施。 cpu時(shí)間的計(jì)算公式：cputime = *i*cpi :時(shí)鐘周期，取決于硬件工藝和計(jì)算機(jī)組成； cpi:指令的平均時(shí)鐘周期數(shù)，與計(jì)算機(jī)組成和指令系統(tǒng)有關(guān)； i:程序指令數(shù)，取決于機(jī)器指令系統(tǒng)和編譯技術(shù)。2、說(shuō)明集中式多處理器和分布式多處理器體系結(jié)構(gòu)的通信模型。（1）共享存儲(chǔ)器通信模型對(duì)應(yīng)與統(tǒng)一地址空間組織，因?yàn)檫@一統(tǒng)一的地址空間可用作隱含的數(shù)據(jù)通信機(jī)制，即直接用load、store共享變量即可。（2）消息傳遞模型：對(duì)應(yīng)于多重地址空間組

26、織。這里處理器獲得數(shù)據(jù)通信需要顯式地通過(guò)傳遞消息來(lái)進(jìn)行。3、數(shù)據(jù)相關(guān)分析。4、簡(jiǎn)答：數(shù)據(jù)相關(guān)、amdahl定理、cache主存映射方式。計(jì)算理論1、 什么是計(jì)算？計(jì)算理論研究的內(nèi)容和意義是什么？為什么要使用計(jì)算的抽象模型？2、 請(qǐng)寫(xiě)出一個(gè)正則表達(dá)式，描述下面的語(yǔ)言：在字母表0，1上，不包含00字串且以1結(jié)尾。1011 0113、 為什么說(shuō)能被2或者3整除的語(yǔ)言是正則的？4、5、 一個(gè)succ(n+1)的組合turing機(jī)描述，說(shuō)出它的作用。6、 什么是turing機(jī)的停機(jī)問(wèn)題？它是可判定的么？為什么？7、 證明這個(gè)問(wèn)題不可判定：一個(gè)turing機(jī)半判定的語(yǔ)言等于這樣的一個(gè)語(yǔ)言，這個(gè)預(yù)言是w和w

27、的轉(zhuǎn)置的連接。2003年浙江大學(xué)秋季計(jì)算機(jī)試題操作系統(tǒng)體系結(jié)構(gòu)1、 寫(xiě)出計(jì)算機(jī)設(shè)計(jì)的三個(gè)原理計(jì)算機(jī)設(shè)計(jì)的定量定理：（1）amdahl定律；（2）高頻事件高速處理；（3）局部性原理2、 cputime公式，及如何減少cputime？ cpu時(shí)間的計(jì)算公式：cputime = *i*cpi :時(shí)鐘周期，取決于硬件工藝和計(jì)算機(jī)組成； cpi:指令的平均時(shí)鐘周期數(shù)，與計(jì)算機(jī)組成和指令系統(tǒng)有關(guān)； i:程序指令數(shù)，取決于機(jī)器指令系統(tǒng)和編譯技術(shù)。3、 畫(huà)出分布式多處理器的體系結(jié)構(gòu)，并說(shuō)明它的兩種存儲(chǔ)器體系及其對(duì)應(yīng)的通信機(jī)制。分布式多處理器的體系結(jié)構(gòu)如下：分布式存儲(chǔ)器結(jié)構(gòu)模型：1、distributed sh

28、ared memory：shared memory2、multiple computers：message passing 計(jì)算理論1、 l=ambmca2nb2n:m,nn,m,n1（1）寫(xiě)出它的文法（2）寫(xiě)出它對(duì)應(yīng)的確定性下推自動(dòng)機(jī)2、 作出判定0n1n2n（n0）的圖靈機(jī)。3、 用泵定理證明a(n+1)2不是上下文無(wú)關(guān)文法（a有一個(gè)上標(biāo)為（n+1）的平方）4、 l為上下文無(wú)關(guān)文法，r為正則文法，判斷l(xiāng)是r的子集是否可判定，并說(shuō)明理由。面向?qū)ο?、 名詞解釋封裝 永久對(duì)象 多態(tài) 繼承（1）封裝：就是把對(duì)象的屬性和操作結(jié)合成一個(gè)獨(dú)立的系統(tǒng)單位，并盡可能隱蔽對(duì)象的內(nèi)部細(xì)節(jié)。（2）永久對(duì)象：是指

29、生存期可以超越程序的執(zhí)行時(shí)間而長(zhǎng)期存在的對(duì)象。（3）多態(tài)：在計(jì)算機(jī)語(yǔ)言學(xué)中，多態(tài)性的一般含義是一個(gè)命名在不同的語(yǔ)境下有不同的語(yǔ)義。在面向?qū)ο蠹夹g(shù)中，對(duì)象的多態(tài)性通常是指一般特殊結(jié)構(gòu)中對(duì)象所體現(xiàn)的多態(tài)性，即在一般類(lèi)中定義的屬性或操作被特殊類(lèi)繼承之后，可以具有不同的數(shù)據(jù)類(lèi)型或表現(xiàn)出不同的行為。（4）繼承：特殊類(lèi)擁有其一般類(lèi)的全部屬性與操作，稱為特殊類(lèi)對(duì)一般類(lèi)的繼承。2、 做出收款機(jī)的usecase和交互圖3、 判斷一種ooa好壞的標(biāo)準(zhǔn)4、 說(shuō)明ooa的過(guò)程5、 uml的作用及它所使用的圖6、 做出一個(gè)監(jiān)控系統(tǒng)的對(duì)象圖2004年浙江大學(xué)春季計(jì)算機(jī)試題操作系統(tǒng)1、關(guān)于硬件、操作系統(tǒng)、實(shí)用程序、用戶應(yīng)用

30、程序的層級(jí)關(guān)系圖。2、剝奪式內(nèi)核與非剝奪式內(nèi)核的異同特點(diǎn)。體系結(jié)構(gòu)1、8kbcache，塊大小32b，采用直接映像，數(shù)據(jù)字為32位，地址為34位，問(wèn)block offset，index，tag各為多少位？2、循環(huán)代碼如下：for (i = 1; i1，l2= ambncp：n不等于p且m、n、p1 （2）證明語(yǔ)言a，b，c* -(l1ul2)不是上下文無(wú)關(guān)的。4、 給出一個(gè)turing機(jī)包括轉(zhuǎn)移關(guān)系等。（1）根據(jù)給定的turing機(jī)的計(jì)算過(guò)程求出它所接受的語(yǔ)言l(m)。（2）構(gòu)造一個(gè)文法來(lái)生成l(m)。5、 一個(gè)有關(guān)遞歸的判斷題，并說(shuō)出理由。6、 一個(gè)根據(jù)語(yǔ)言描述來(lái)判斷兩個(gè)語(yǔ)言之間關(guān)系的選擇題

31、。如語(yǔ)言1是語(yǔ)言2的真子集，語(yǔ)言2是語(yǔ)言1的真子集，語(yǔ)言2=語(yǔ)言1，語(yǔ)言1、語(yǔ)言2無(wú)任何關(guān)系。面向?qū)ο?、 ooa與ood的關(guān)系。2、 uml的視圖有幾種，有幾種圖？分別是哪些？關(guān)聯(lián)有哪幾種？試分別簡(jiǎn)述之。3、 什么是use case，它的作用是什么？4、 畫(huà)出圖書(shū)銷(xiāo)售管理系統(tǒng)的對(duì)象層圖。5、 畫(huà)出小劉給小王打電話的順序圖；小劉提起電話，聽(tīng)見(jiàn)電話響聲，小王接電話，通話，通話完畢小王掛電話，小劉掛電話。6、 什么是多態(tài)性，試舉例說(shuō)明之。在一般類(lèi)中定義的屬性或操作被特殊類(lèi)繼承之后，可以具有不同的數(shù)據(jù)類(lèi)型或表現(xiàn)出不同的行為。2005年浙江大學(xué)秋季計(jì)算機(jī)試題操作系統(tǒng)1、 庫(kù)函數(shù)與系統(tǒng)調(diào)用的調(diào)用方法相同

32、，它們有何區(qū)別？2、“沒(méi)有兩個(gè)操作系統(tǒng)是相同的”。判斷這句話是否正確？體系結(jié)構(gòu)1、 cputime公式，與哪些技術(shù)相關(guān)，縮短cputime的途徑。2、 cache比主存快10倍，內(nèi)存利用率90%，求cache加速比。3、 直接映射，cache容量8kb，block32b，data word 64bits，地址32bits，求tag，index，block offset各幾位？4、 畫(huà)分布存儲(chǔ)處理機(jī)框圖，有哪兩種存儲(chǔ)結(jié)構(gòu)，哪兩種通訊機(jī)制？分布式存儲(chǔ)多處理機(jī)的基本結(jié)構(gòu)如下：分布式存儲(chǔ)器結(jié)構(gòu)模型如下：1、distributed shared memory2、multiple computers 通信

33、模型：1、共享存儲(chǔ)器通信模型2、消息傳遞模型5、 代碼，求真相關(guān)，反相關(guān)，輸出相關(guān)，循環(huán)相關(guān)，有無(wú)循環(huán)并行性？理由？有哪兩句相關(guān)，關(guān)于哪個(gè)變量相關(guān)？for(i=2;i100;i+1)ai=bi+ai s1ci-1=ai+di s2ai-1=2bi s3 bi+1=2bi s41、數(shù)據(jù)相關(guān)（真數(shù)據(jù)相關(guān)）： 若下面的條件之一成立，則指令j數(shù)據(jù)相關(guān)于指令i：（1）指令i產(chǎn)生的結(jié)果為j引用；（2）指令j數(shù)據(jù)相關(guān)于指令k，而指令k數(shù)據(jù)相關(guān)于指令i。2、名字相關(guān)：當(dāng)兩條指令使用同一寄存器或是同一個(gè)內(nèi)存地址時(shí)，即發(fā)生了名字相關(guān)，有名字相關(guān)的指令之間不存在數(shù)據(jù)流。（1）反相關(guān)，指令j寫(xiě)一個(gè)寄存器或一個(gè)內(nèi)存單元

34、，而指令i則去讀該寄存器或內(nèi)存單元，且i的執(zhí)行在前。此時(shí)必須保證指令原來(lái)的順序不變，以保證i能讀到正確的值。（2）輸出相關(guān)，指令i和j對(duì)同一個(gè)寄存器或內(nèi)存地址執(zhí)行寫(xiě)操作，這種操作順序必須正確，以使最后寫(xiě)入的值由j決定。3、控制相關(guān)：由程序控制指令引起的相關(guān)性?？刂葡嚓P(guān)對(duì)流水線的影響可通過(guò)延遲轉(zhuǎn)移等方法減少或消除。1、 s1和s1在a上有反相關(guān)關(guān)系；2、 s1和s2在a上有真相關(guān)關(guān)系；3、 s4和s1在b上有由循環(huán)帶來(lái)的真相關(guān)關(guān)系；4、 s4和s3在b上有由循環(huán)帶來(lái)的真相關(guān)關(guān)系；5、 s3和s3在b上有由循環(huán)帶來(lái)的真相關(guān)關(guān)系；6、 s3和s3在a上有由循環(huán)帶來(lái)的輸出相關(guān)關(guān)系。如果要并行化一個(gè)循環(huán)

35、，那么循環(huán)的每一次都應(yīng)該和其他循環(huán)無(wú)關(guān)，但是該題不是這種情況。在上面的分析中，3,4,5是真相關(guān)關(guān)系，他們不能通過(guò)重命名或者其他方法消除，另外，由于這些關(guān)系和循環(huán)相關(guān)，因此每一次循環(huán)之間不是獨(dú)立的。綜上所述，該循環(huán)無(wú)法直接被并行化。6、產(chǎn)生結(jié)果指令利用該結(jié)果指令必須延遲時(shí)鐘周期數(shù)浮點(diǎn)alu操作指令另一浮點(diǎn)alu結(jié)果指令3浮點(diǎn)alu操作指令store雙精度浮點(diǎn)2load雙精度浮點(diǎn)數(shù)浮點(diǎn)alu操作指令1load雙精度浮點(diǎn)數(shù)store雙精度0loop：l.d f0, 0(r1) add.d f4, f0, f2 s.d 0(r1), f4 sub1 r1, r2, 8 bnez r1, loop f

36、0=array else add in f2 store result decreet porter subtes cper double word試用循環(huán)體展開(kāi)并調(diào)度的方法提高指令集并行度，4次循環(huán)體展開(kāi)調(diào)度后，新循環(huán)體代碼序列，上述優(yōu)化后執(zhí)行單位循環(huán)體所需時(shí)鐘周期可縮短多少？計(jì)算理論1、 判斷下列語(yǔ)言是否為正則語(yǔ)言，請(qǐng)具體說(shuō)出理由（1）l1=w1|wa,b*,na(w)-nb(w) mod 30（2）l2= w1|wa,b*,na(w)-nb(w)0這里na(w), nb(w)分別表示字符串w中a, b的個(gè)數(shù)。2、（1）給出上下文無(wú)關(guān)文法生成語(yǔ)言l3=xcy|2|x|=|y|,x,ya,b

37、* （2）證明l4=aibjcidj|i,jn,i,j1不是上下文無(wú)關(guān)語(yǔ)言。3、證明語(yǔ)言l=“m”|turing機(jī)在空串e上停機(jī)是非遞歸的，其中“m”表示turing機(jī)m的編碼。4、給定n個(gè)數(shù)x1xn，判定是否存在不同的i1，i2ik，使?jié)M足下列兩個(gè)條件：（1）xi1+xi2+xik=(x1+x2+xn)/2（2）xi1+xi2+xik不是素?cái)?shù)，給出一個(gè)算法，并估計(jì)其計(jì)算時(shí)間，說(shuō)明這個(gè)問(wèn)題屬于np類(lèi)（給算法描述即可）面向?qū)ο?、 名詞解釋多繼承 永久對(duì)象 問(wèn)題域 系統(tǒng)邊界（1） 多繼承：如果允許一個(gè)特殊類(lèi)同時(shí)繼承多個(gè)一般類(lèi)的屬性與操作，則這種繼承叫做多繼承。（2） 永久對(duì)象：是指生存期可以超越

38、程序的執(zhí)行時(shí)間而長(zhǎng)期存在的對(duì)象。（3） 問(wèn)題域：被開(kāi)發(fā)的應(yīng)用系統(tǒng)所考慮的整個(gè)業(yè)務(wù)范圍。（4） 系統(tǒng)邊界：是指系統(tǒng)內(nèi)部的所有成分與系統(tǒng)以外各種事物之間的分界線。2、 簡(jiǎn)述建立實(shí)例連接的過(guò)程。3、 分別敘述ooa和ood過(guò)程的主要活動(dòng)。ooa包括以下主要活動(dòng)：（1）建立需求模型-用況圖：定義系統(tǒng)邊界；發(fā)現(xiàn)參與者；定義用況；（2）建立基本模型-類(lèi)圖：發(fā)現(xiàn)對(duì)象、定義它們的類(lèi)；定義對(duì)象的內(nèi)部特征-屬性和操作；定義對(duì)象的外部關(guān)系-一般-特殊結(jié)構(gòu)、整體-部分結(jié)構(gòu)、關(guān)聯(lián)和消息（3）建立輔助模型：劃分包，建立包圖；建立順序圖；建立活動(dòng)圖；建立其他模型圖；（4）建立模型規(guī)約；（5）原型開(kāi)發(fā)。ood包括以下活動(dòng)：總體結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、過(guò)程設(shè)計(jì)。4、 電梯運(yùn)行方式，用狀態(tài)圖描述它的各種狀態(tài)和可能的轉(zhuǎn)移。5、 簡(jiǎn)要分析過(guò)程抽象與數(shù)據(jù)抽象。抽象是指從許多事物中舍棄個(gè)別的、非本質(zhì)性的特征，抽取共同的、本質(zhì)性的特征。（1）過(guò)程抽象是指任何一個(gè)完成確定功能的操作序列，其使用者都可把它看成一個(gè)單一的實(shí)體，盡管實(shí)際上它可能是由一系列更低級(jí)的操作完成的。（2）數(shù)據(jù)抽象是根據(jù)施加于數(shù)據(jù)之上的操作來(lái)定義數(shù)據(jù)類(lèi)型，并限定數(shù)據(jù)的值只能由這些操作來(lái)修改和觀察。6、 分析兩種觀點(diǎn)：（1） 用c+開(kāi)發(fā)的軟件系統(tǒng)就是面向?qū)ο蟮膽?yīng)用系統(tǒng)；（2） 面向?qū)ο?/p>