操作系統(tǒng)課堂練習(xí)(期末必考)

1、操作系統(tǒng)課堂練習(xí)2011年6月8日Contents第一章練習(xí)題P.2第二章練習(xí)題P.3第三章練習(xí)題P.5第四章練習(xí)題P.8第五章練習(xí)題P.10第六章練習(xí)題P.12第十一章練習(xí)題P.16第十二章練習(xí)題P.17第十三、十四、十五章練習(xí)題P.18第一章練習(xí)題1.網(wǎng)絡(luò)操作系統(tǒng)與分布操作系統(tǒng)主要區(qū)別是什么？答：網(wǎng)絡(luò)操作系統(tǒng)與分布操作系統(tǒng)主要不同是它不是一個(gè)集中、統(tǒng)一的操作系統(tǒng)（它基本上是在各種各樣自治的計(jì)算機(jī)原有操作系統(tǒng)基礎(chǔ)上加上具有各種網(wǎng)絡(luò)訪問功能的模塊）。2.允許多個(gè)用戶以交互式方式使用計(jì)算機(jī)系統(tǒng)的操作系統(tǒng)稱為 B系統(tǒng)。A）批處理B) 分時(shí)C) 實(shí)時(shí) D) 多處理機(jī)第二章練習(xí)題1.簡(jiǎn)述可變分區(qū)存儲(chǔ)管

2、理算法中的首次適應(yīng)法的分配算法答：首次適應(yīng)法為作業(yè)分配大小為size的內(nèi)存空間時(shí)，總是從表的始端的低地址部分開始查找，當(dāng)?shù)谝淮握业酱笥诨虻扔谏暾?qǐng)大小的空閑區(qū)時(shí)，就按所需大小分配給作業(yè)。如果分配后原空閑區(qū)還有剩余空間，就修改原存儲(chǔ)區(qū)表項(xiàng)的m_size和m_addr，使它記錄余下的“零頭”。如果作業(yè)所需空間正好等于該空閑區(qū)大小，那么該空閑區(qū)表項(xiàng)的m_size就成為0，接下來要?jiǎng)h除表中這個(gè)“空洞”。2.根據(jù)作業(yè)在本次分配到的內(nèi)存起始地址將可執(zhí)行目標(biāo)代碼裝到指定內(nèi)存地址中，并修改所有有關(guān)地址部分的值的方法稱為 B 方式。A) 固定定位 B) 靜態(tài)重定位C) 動(dòng)態(tài)重定位 D) 單一連續(xù)重定位3.下列程序

3、設(shè)計(jì)技術(shù)和數(shù)據(jù)結(jié)構(gòu)在請(qǐng)求分頁的環(huán)境中，哪些是“好的”，哪些是“不好的”？1）向量 2）鏈接表 3）棧 4）隊(duì)列 5）散列表 6）順序查找7）二分排查找 8）合并排序 9）快速排序 10）堆排序 11）散列排序答:1）向量（數(shù)組） (對(duì)于一個(gè)大的向量)順序存取時(shí)是好的，隨機(jī)存取時(shí)是不好的；2）鏈接表 不好的；3）棧 順序?qū)崿F(xiàn)時(shí)是好的，鏈接實(shí)現(xiàn)時(shí)是不好的；4）隊(duì)列 順序?qū)崿F(xiàn)時(shí)是好的，鏈接實(shí)現(xiàn)時(shí)是不好的；5）散列表 不好的；6）順序查找 順序?qū)崿F(xiàn)時(shí)是好的；鏈接實(shí)現(xiàn)時(shí)是不好的；7）二分查找 不好的；8）合并排序 順序?qū)崿F(xiàn)時(shí)好的，鏈接實(shí)現(xiàn)時(shí)是不好的；9）快速排序 非遞歸實(shí)現(xiàn)時(shí)由于從兩頭向中間順序地比較和

4、交換，是好的；10）堆排序 不好的；11）散列排序 不好的。第三章練習(xí)題1.為什么在操作系統(tǒng)中要引進(jìn)進(jìn)程的概念？答：在多道程序系統(tǒng)中，系統(tǒng)中的硬軟件資源不再為單個(gè)用戶程序所壟斷，而由若干道程序共同使用。一個(gè)程序也不能自始至終地運(yùn)行到底，中間會(huì)穿插很多其他的活動(dòng)，這些活動(dòng)間存在著相互依賴和相互制約的關(guān)系。由于程序并發(fā)執(zhí)行所產(chǎn)生的一系列新的動(dòng)態(tài)的特征，已不能由程序這種靜態(tài)的概念來描述，為此，引入了“進(jìn)程”（process）這個(gè)概念。我們?cè)谶M(jìn)程創(chuàng)建這一節(jié)知道，一個(gè)程序可以對(duì)應(yīng)多個(gè)獨(dú)立的活動(dòng)進(jìn)程。 2.進(jìn)程所請(qǐng)求的輸入數(shù)據(jù)到達(dá)后，將使進(jìn)程狀態(tài)從 D 。A) 運(yùn)行態(tài)變?yōu)榫途w態(tài) B) 運(yùn)行態(tài)變?yōu)榈却龖B(tài) C

5、) 就緒態(tài)變?yōu)檫\(yùn)行態(tài) D) 等待態(tài)變?yōu)榫途w態(tài) 說明：進(jìn)程要讀入數(shù)據(jù)，應(yīng)當(dāng)同步等待。進(jìn)程狀態(tài)為等待狀態(tài)（睡眠狀態(tài)）。進(jìn)程所請(qǐng)求的輸入數(shù)據(jù)到達(dá)后，將喚醒該進(jìn)程，使進(jìn)程狀態(tài)從等待狀態(tài)變?yōu)榫途w狀態(tài) ，使其有被調(diào)度程序挑選的資格。也不可能直接從等待狀態(tài)變?yōu)檫\(yùn)行態(tài)。3. 某系統(tǒng)的狀態(tài)轉(zhuǎn)換圖如圖所示，（1）分別說明引起狀態(tài)轉(zhuǎn)換1、2、3、4的原因，并各舉一個(gè)事件。（2）為什么在轉(zhuǎn)換圖中沒有就緒到阻塞和阻塞到運(yùn)行的轉(zhuǎn)換方向？（3）一個(gè)進(jìn)程的狀態(tài)變換能夠引起另一個(gè)進(jìn)程的狀態(tài)變換，說明下列因果變遷是否可能發(fā)生，原因是什么？（a）31 （b）21 （c）32 （d）34 （e）41答： （1）1： 就緒-執(zhí)行， 當(dāng)

6、前運(yùn)行進(jìn)程阻塞，調(diào)度程序選一個(gè)優(yōu)先權(quán)最高的進(jìn)程占有處理機(jī)；2： 執(zhí)行-就緒， 當(dāng)前運(yùn)行進(jìn)程時(shí)間片用完；3：執(zhí)行-阻塞，當(dāng)前運(yùn)行進(jìn)程等待鍵盤輸入，進(jìn)入了睡眠狀態(tài)。4：阻塞-就緒，I/O操作完成，被中斷處理程序喚醒。（2） 就緒進(jìn)程沒有占有處理機(jī)，也即沒有經(jīng)過運(yùn)行，其狀態(tài)就不會(huì)改變。阻塞狀態(tài)進(jìn)程喚醒后先要進(jìn)入就緒隊(duì)列，才會(huì)被調(diào)度程序選中，進(jìn)入了執(zhí)行狀態(tài)。（3）（a） 31： 可能，當(dāng)前運(yùn)行進(jìn)程阻塞，調(diào)度程序選一個(gè)優(yōu)先級(jí)最高的進(jìn)程占有處理機(jī)。（b）21：可能，當(dāng)前運(yùn)行進(jìn)程優(yōu)先級(jí)下降，調(diào)度程序選一個(gè)優(yōu)先級(jí)最高的進(jìn)程占有處理機(jī)。（c）32： 不可能，占有CPU的一個(gè)進(jìn)程不能同時(shí)進(jìn)入兩個(gè)狀態(tài)；在單CPU的

7、系統(tǒng)中，狀態(tài)3發(fā)生后，cpu沒有執(zhí)行進(jìn)程，故不會(huì)發(fā)生狀態(tài)轉(zhuǎn)換2。（d）34：一般不可能，不相干的兩個(gè)事件。狀態(tài)轉(zhuǎn)換3是由于運(yùn)行進(jìn)程等待資源而發(fā)生的，這并不會(huì)使得阻塞隊(duì)列中的進(jìn)程得到資源而進(jìn)入就緒隊(duì)列。但在Unix中，當(dāng)系統(tǒng)的0進(jìn)程因runin標(biāo)志而睡眠時(shí)，有（在內(nèi)存）進(jìn)程睡眠，就會(huì)喚醒0進(jìn)程，使其進(jìn)入就緒狀態(tài)，以便將該進(jìn)程和在盤交換區(qū)就緒進(jìn)程交換位置。（e）41：一般無關(guān)，但當(dāng)就緒隊(duì)列為空時(shí)，一個(gè)進(jìn)程被喚醒轉(zhuǎn)入就緒隊(duì)列后，調(diào)度程序使該進(jìn)程占有處理機(jī)（但是同一個(gè)進(jìn)程）。第四章練習(xí)題1假如一個(gè)閱覽室最多可容納N個(gè)人，讀者進(jìn)入和離開閱覽室時(shí)，都必須在每次只允許一個(gè)人寫的登記表上做進(jìn)入登記和離開登記，

8、試用semWait、semSignal操作實(shí)現(xiàn)讀者間的協(xié)調(diào)關(guān)系。 答：信號(hào)燈含義和初值：chair: 閱覽室椅子數(shù)，即最多可容納人數(shù)，初值為Nregister: 進(jìn)入登記和離開登記的互斥信號(hào)燈，初值為12. 用ls命令以長格式列目錄信息時(shí)，若某一文件的特征在文件列表中按如下順序顯示在屏幕上： -rwxr-xr- 2 user gk 3564 OCT 2003 8:18 /user/asdh則同組用戶的訪問權(quán)限是 讀和執(zhí)行 。3.用semWait、semSignal操作實(shí)現(xiàn)同步和互斥時(shí)有什么差別？答：見第5題。4.在Unix系統(tǒng)中， A 可用于通知進(jìn)程發(fā)生了異常的事件。 A) 信號(hào)機(jī)構(gòu)B) 管道

9、機(jī)構(gòu) C) 消息機(jī)構(gòu)D) 信號(hào)燈5.互斥和同步對(duì)信號(hào)燈操作方法的差異。答：互斥和同步都是通過對(duì)信號(hào)燈的semWait、semSignal操作來實(shí)現(xiàn)的，但這兩種控制機(jī)制對(duì)信號(hào)燈的操作策略是不同的。互斥的實(shí)現(xiàn)是不同的進(jìn)程對(duì)同一信號(hào)燈進(jìn)行semWait 、 semSignal 操作，一個(gè)進(jìn)程在成功地對(duì)信號(hào)燈執(zhí)行了semWait操作后進(jìn)入臨界段，并在退出臨界段后，由該進(jìn)程本身對(duì)這信號(hào)燈執(zhí)行semSignal操作，表示沒有進(jìn)程處于臨界段，可讓其它進(jìn)程進(jìn)入。同步的實(shí)現(xiàn)由一個(gè)進(jìn)程Pa對(duì)一個(gè)信號(hào)燈進(jìn)行semWait操作后，只能由另一個(gè)進(jìn)程Pb對(duì)同一個(gè)信號(hào)燈進(jìn)行semSignal操作，使Pa能繼續(xù)前進(jìn)，在這種情

10、況下，進(jìn)程Pa要同步等待Pb。如進(jìn)程Pb也要同步等待Pa，則要設(shè)置另一個(gè)信號(hào)燈。6.某系統(tǒng)中有m個(gè)同類資源被n個(gè)進(jìn)程共享，請(qǐng)分別討論當(dāng)mn和mn時(shí)，每個(gè)進(jìn)程最多可以請(qǐng)求多少個(gè)資源才能保證系統(tǒng)不會(huì)發(fā)生死鎖？答：例如11個(gè)同類資源被5個(gè)進(jìn)程共享，每個(gè)進(jìn)程最多可以請(qǐng)求多3個(gè)資源才能保證系統(tǒng)不會(huì)發(fā)生死鎖。因?yàn)槿缑總€(gè)進(jìn)程都已分配到2個(gè)資源，系統(tǒng)還剩下一個(gè)資源，就能保證某一個(gè)進(jìn)程能分配到全部3個(gè)資源，并能運(yùn)行到底，最終釋放這3個(gè)資源。第五章練習(xí)題1.說明UNIX為塊設(shè)備I/O設(shè)置多緩沖區(qū)的目的、緩存管理采用的主要算法以及實(shí)施方法。答：設(shè)置多緩沖區(qū)的目的： UNIX系統(tǒng)采用多重緩沖技術(shù)。用于快速地暫存程序的

11、輸出數(shù)據(jù)，緩和CPU與I/O設(shè)備間速度不匹配的矛盾。提高CPU與I/O設(shè)備間的并行操作程度。減少對(duì)磁盤的讀寫操作。當(dāng)從盤上讀數(shù)據(jù)時(shí)，如果數(shù)據(jù)已經(jīng)在緩沖區(qū)中，則核心就直接從中讀出，而不必從盤上讀；僅當(dāng)所需數(shù)據(jù)不在緩沖區(qū)中時(shí)，核心才把數(shù)據(jù)從盤上讀到緩沖區(qū)，然后再由緩沖區(qū)讀出。核心盡量使數(shù)據(jù)在緩沖區(qū)停留較長時(shí)間，以減少磁盤I/O的次數(shù)。緩存管理采用的主要算法（1）設(shè)備緩沖區(qū)隊(duì)列設(shè)備緩沖區(qū)隊(duì)列連接所有各類設(shè)備使用過的緩沖區(qū)，這是一個(gè)雙向隊(duì)列，指針為b_forw和b_back。一個(gè)緩沖區(qū)被分配用于讀、寫某個(gè)設(shè)備的字符塊時(shí)，其相應(yīng)的buf就進(jìn)入該設(shè)備的設(shè)備buf隊(duì)列，并一直保留在該設(shè)備buf隊(duì)列中，以盡量

12、重復(fù)使用原設(shè)備隊(duì)列中該緩存內(nèi)容，除非被移作它用。（2）自由隊(duì)列的淘汰算法系統(tǒng)把空閑緩沖區(qū)的buf組成空閑buf隊(duì)列。這個(gè)隊(duì)列是雙向鏈結(jié)構(gòu)，隊(duì)首塊為bfreelist，av_forw和av_back作為雙向指針。選擇適當(dāng)?shù)木彌_區(qū)管理方法是非常重要的，其中最關(guān)鍵的是淘汰算法，UNIX系統(tǒng)中采用了極為精確的最久未使用算法（LRU） 。實(shí)施方法（1） 一個(gè)緩存剛分配用于讀寫某一塊設(shè)備，buf的b_flags含有B_BUSY標(biāo)志。它一定位于相應(yīng)設(shè)備buf隊(duì)列，不在自由隊(duì)列。（2） 一旦讀寫完成，就釋放緩存，清B_BUSY標(biāo)志。送入自由隊(duì)列尾，但仍留在原設(shè)備隊(duì)列。（3） 分配作它用緩存從自由隊(duì)列首取。（4

13、） 當(dāng)一個(gè)buf在自由隊(duì)列中移動(dòng)時(shí)，只要原設(shè)備隊(duì)列又重新使用它，立即將其從自由隊(duì)列中間抽取，使用完畢，再次送入自由隊(duì)列尾（LRU算法）。（5） 對(duì)于寫，如一塊未寫滿，在b_flags中設(shè)置B_DELWRI標(biāo)志，推遲寫，再清B_BUSY，釋放至自由隊(duì)列尾。（6） 當(dāng)設(shè)置B_DELWRI標(biāo)志的緩存排到自由隊(duì)列首時(shí)，不能立即淘汰，而是提出I/O請(qǐng)求，將其內(nèi)容復(fù)制到塊設(shè)備后，再次釋放到自由隊(duì)列尾并清B_DELWRI標(biāo)志。2.通道又稱I/O處理機(jī)，它能完成 A之間的信息傳輸。A）主存和外設(shè) B） CPU和外設(shè)C）外存和外設(shè) D） 主存和CPU說明：I/O通道帶有專用處理器的、有很強(qiáng)I/O處理功能的智能部

14、件，它可以獨(dú)立地完成系統(tǒng)處理器交付的I/O操作任務(wù)，此時(shí)，I/O總線直接與通道相連而不與處理器相連。通道具有自己專門的指令集，在設(shè)備與存儲(chǔ)器之間傳送數(shù)據(jù)。系統(tǒng)主處理器只需進(jìn)行I/O操作的委托，其后的所有I/O操作均由通道自己進(jìn)行。完成后只需向系統(tǒng)處理器發(fā)出中斷，請(qǐng)求結(jié)束?？梢姡@種方式可以形成系統(tǒng)處理器與I/O設(shè)備之間的并行操作。第六章練習(xí)題1.一個(gè)進(jìn)程獨(dú)立打開一個(gè)文件后畫出打開文件結(jié)構(gòu)，標(biāo)出與打開文件有關(guān)的各部分?jǐn)?shù)據(jù)結(jié)構(gòu)名稱。2.UNIX的rm命令使用了系統(tǒng)調(diào)用 B 。A) close B) unlinkC) fcntl D) umask3.在UNIX中超級(jí)塊filsys的當(dāng)前情況如圖6-1

15、9所示，某文件順序釋放了物理盤塊號(hào)為1150、1151、1175、1050的四個(gè)盤塊，畫出釋放后有關(guān)部分的變化結(jié)果。答：4.說明UNIX文件的地址索引結(jié)構(gòu)，并描述如何由文件的邏輯塊號(hào)n找到文件的物理塊號(hào)。答：（1） 0=n9: 物理塊號(hào)blkno = i_an（2） 9n=10+341:直接索引的blkno = i_a10;物理塊號(hào)blkno =直接索引塊的第n-10項(xiàng)內(nèi)容。（3） 10+341n=10+341+341*341:一級(jí)間接索引的blkno = i_a11;直接索引的blkno = 一級(jí)間接索引塊的第（n-10-341）/341項(xiàng)內(nèi)容;物理塊號(hào)blkno =直接索引塊的第（n-10

16、-341）%341項(xiàng)內(nèi)容；（4） 10+341+341*341 n 10+341+341*341+341*341*341:二級(jí)間接索引的blkno = i_a12;一級(jí)索引的blkno = 二級(jí)間接索引塊的第（n-10-341-341*341）/（341*341）項(xiàng)內(nèi)容;其余情況可以從情況3類推。5. Unix的打開文件結(jié)構(gòu)涉及到 A 這三種結(jié)構(gòu)。A) ofile,file,inode B) ofile ,file,addr40C) file,direct,inode D) file,inode,filsys第十一章練習(xí)題1基于符號(hào)鏈接與普通鏈接的文件共享方式各有什么優(yōu)點(diǎn)？答：普通鏈接（硬鏈接

17、）：在UNIX同一個(gè)文件系統(tǒng)中，同一層次或不同層次的目錄項(xiàng)可指向同一個(gè)文件的I節(jié)點(diǎn)，這就是目錄結(jié)構(gòu)的勾連。由此，不同用戶或同用戶可以在不同的位置上用不同的文件名（或相同的文件名）訪問同一個(gè)文件。這為文件的共享提供了方便。 符號(hào)鏈接：硬鏈接有兩個(gè)局限，第一是不能為一個(gè)目錄創(chuàng)建一個(gè)鏈接；第二是不能在不同文件系統(tǒng)中建立文件鏈接。使用符號(hào)鏈接就能實(shí)現(xiàn)上述兩個(gè)功能。符號(hào)鏈接建立了新的文件或目錄與原來文件或目錄的路徑名映照。當(dāng)你訪問一個(gè)符號(hào)鏈接時(shí)，UNIX靠這個(gè)映照找到原文件的路徑，所以這種鏈接方法又稱為軟鏈接。通過軟鏈接訪問文件的速度比硬鏈接稍慢一些。 2用find命令和grep命令的組合顯示當(dāng)前目錄樹

18、下所有C源程序中含有main( )的行。答：find . name *.c | grep main( ) find . name *.c exec grep main( ) ;3. 用于確定字符串模式的一個(gè)規(guī)則集稱為 A 。A) 正則表達(dá)式B) 字符串匹配C) 文件名匹配D) 過濾器第十二章練習(xí)題1.寫出用當(dāng)前目錄中所有的C目標(biāo)代碼生成檔案庫arch的命令。ar rv libarch.a ./*.o2.根據(jù)一些說明和文件的修改時(shí)間自動(dòng)地維護(hù)模塊間的關(guān)系的程序是 D 。A) sdb B) sccs C) ar D) make3.決定Makefile依賴行中依賴關(guān)系的是文件的 A 。A)修改時(shí)間 B) 創(chuàng)建時(shí)間C) 大小 D) 存取權(quán)限第十三、十四、十五章練習(xí)題1.可以在不同系統(tǒng)之間傳送文件的程序是 A 。（A) ftp B) rcp C) write D) telnet2.普通用戶可以利用文件的系統(tǒng)調(diào)用 A 實(shí)現(xiàn)鎖功能。A)