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

2、理算法中的首次適應法的分配算法答：首次適應法為作業分配大小為size的內存空間時，總是從表的始端的低地址部分開始查找，當第一次找到大于或等于申請大小的空閑區時，就按所需大小分配給作業。如果分配后原空閑區還有剩余空間，就修改原存儲區表項的m_size和m_addr，使它記錄余下的“零頭”。如果作業所需空間正好等于該空閑區大小，那么該空閑區表項的m_size就成為0，接下來要刪除表中這個“空洞”。2.根據作業在本次分配到的內存起始地址將可執行目標代碼裝到指定內存地址中，并修改所有有關地址部分的值的方法稱為 B 方式。A) 固定定位 B) 靜態重定位C) 動態重定位 D) 單一連續重定位3.下列程序

3、設計技術和數據結構在請求分頁的環境中，哪些是“好的”，哪些是“不好的”？1）向量 2）鏈接表 3）棧 4）隊列 5）散列表 6）順序查找7）二分排查找 8）合并排序 9）快速排序 10）堆排序 11）散列排序答:1）向量（數組） (對于一個大的向量)順序存取時是好的，隨機存取時是不好的；2）鏈接表 不好的；3）棧 順序實現時是好的，鏈接實現時是不好的；4）隊列 順序實現時是好的，鏈接實現時是不好的；5）散列表 不好的；6）順序查找 順序實現時是好的；鏈接實現時是不好的；7）二分查找 不好的；8）合并排序 順序實現時好的，鏈接實現時是不好的；9）快速排序 非遞歸實現時由于從兩頭向中間順序地比較和

4、交換，是好的；10）堆排序 不好的；11）散列排序 不好的。第三章練習題1.為什么在操作系統中要引進進程的概念？答：在多道程序系統中，系統中的硬軟件資源不再為單個用戶程序所壟斷，而由若干道程序共同使用。一個程序也不能自始至終地運行到底，中間會穿插很多其他的活動，這些活動間存在著相互依賴和相互制約的關系。由于程序并發執行所產生的一系列新的動態的特征，已不能由程序這種靜態的概念來描述，為此，引入了“進程”（process）這個概念。我們在進程創建這一節知道，一個程序可以對應多個獨立的活動進程。 2.進程所請求的輸入數據到達后，將使進程狀態從 D 。A) 運行態變為就緒態 B) 運行態變為等待態 C

5、) 就緒態變為運行態 D) 等待態變為就緒態 說明：進程要讀入數據，應當同步等待。進程狀態為等待狀態（睡眠狀態）。進程所請求的輸入數據到達后，將喚醒該進程，使進程狀態從等待狀態變為就緒狀態 ，使其有被調度程序挑選的資格。也不可能直接從等待狀態變為運行態。3. 某系統的狀態轉換圖如圖所示，（1）分別說明引起狀態轉換1、2、3、4的原因，并各舉一個事件。（2）為什么在轉換圖中沒有就緒到阻塞和阻塞到運行的轉換方向？（3）一個進程的狀態變換能夠引起另一個進程的狀態變換，說明下列因果變遷是否可能發生，原因是什么？（a）31 （b）21 （c）32 （d）34 （e）41答： （1）1： 就緒->執

6、行， 當前運行進程阻塞，調度程序選一個優先權最高的進程占有處理機；2： 執行->就緒， 當前運行進程時間片用完；3：執行->阻塞，當前運行進程等待鍵盤輸入，進入了睡眠狀態。4：阻塞->就緒，I/O操作完成，被中斷處理程序喚醒。（2） 就緒進程沒有占有處理機，也即沒有經過運行，其狀態就不會改變。阻塞狀態進程喚醒后先要進入就緒隊列，才會被調度程序選中，進入了執行狀態。（3）（a） 31： 可能，當前運行進程阻塞，調度程序選一個優先級最高的進程占有處理機。（b）21：可能，當前運行進程優先級下降，調度程序選一個優先級最高的進程占有處理機。（c）32： 不可能，占有CPU的一個進程不

7、能同時進入兩個狀態；在單CPU的系統中，狀態3發生后，cpu沒有執行進程，故不會發生狀態轉換2。（d）34：一般不可能，不相干的兩個事件。狀態轉換3是由于運行進程等待資源而發生的，這并不會使得阻塞隊列中的進程得到資源而進入就緒隊列。但在Unix中，當系統的0進程因runin標志而睡眠時，有（在內存）進程睡眠，就會喚醒0進程，使其進入就緒狀態，以便將該進程和在盤交換區就緒進程交換位置。（e）41：一般無關，但當就緒隊列為空時，一個進程被喚醒轉入就緒隊列后，調度程序使該進程占有處理機（但是同一個進程）。第四章練習題1假如一個閱覽室最多可容納N個人，讀者進入和離開閱覽室時，都必須在每次只允許一個人寫

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

9、事件。 A) 信號機構B) 管道機構 C) 消息機構D) 信號燈5.互斥和同步對信號燈操作方法的差異。答：互斥和同步都是通過對信號燈的semWait、semSignal操作來實現的，但這兩種控制機制對信號燈的操作策略是不同的。互斥的實現是不同的進程對同一信號燈進行semWait 、 semSignal 操作，一個進程在成功地對信號燈執行了semWait操作后進入臨界段，并在退出臨界段后，由該進程本身對這信號燈執行semSignal操作，表示沒有進程處于臨界段，可讓其它進程進入。同步的實現由一個進程Pa對一個信號燈進行semWait操作后，只能由另一個進程Pb對同一個信號燈進行semSignal

10、操作，使Pa能繼續前進，在這種情況下，進程Pa要同步等待Pb。如進程Pb也要同步等待Pa，則要設置另一個信號燈。6.某系統中有m個同類資源被n個進程共享，請分別討論當mn和mn時，每個進程最多可以請求多少個資源才能保證系統不會發生死鎖？答：例如11個同類資源被5個進程共享，每個進程最多可以請求多3個資源才能保證系統不會發生死鎖。因為如每個進程都已分配到2個資源，系統還剩下一個資源，就能保證某一個進程能分配到全部3個資源，并能運行到底，最終釋放這3個資源。第五章練習題1.說明UNIX為塊設備I/O設置多緩沖區的目的、緩存管理采用的主要算法以及實施方法。答：設置多緩沖區的目的： UNIX系統采用多

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

12、保留在該設備buf隊列中，以盡量重復使用原設備隊列中該緩存內容，除非被移作它用。（2）自由隊列的淘汰算法系統把空閑緩沖區的buf組成空閑buf隊列。這個隊列是雙向鏈結構，隊首塊為bfreelist，av_forw和av_back作為雙向指針。選擇適當的緩沖區管理方法是非常重要的，其中最關鍵的是淘汰算法，UNIX系統中采用了極為精確的最久未使用算法（LRU） 。實施方法（1） 一個緩存剛分配用于讀寫某一塊設備，buf的b_flags含有B_BUSY標志。它一定位于相應設備buf隊列，不在自由隊列。（2） 一旦讀寫完成，就釋放緩存，清B_BUSY標志。送入自由隊列尾，但仍留在原設備隊列。（3） 分

13、配作它用緩存從自由隊列首取。（4） 當一個buf在自由隊列中移動時，只要原設備隊列又重新使用它，立即將其從自由隊列中間抽取，使用完畢，再次送入自由隊列尾（LRU算法）。（5） 對于寫，如一塊未寫滿，在b_flags中設置B_DELWRI標志，推遲寫，再清B_BUSY，釋放至自由隊列尾。（6） 當設置B_DELWRI標志的緩存排到自由隊列首時，不能立即淘汰，而是提出I/O請求，將其內容復制到塊設備后，再次釋放到自由隊列尾并清B_DELWRI標志。2.通道又稱I/O處理機，它能完成 A之間的信息傳輸。A）主存和外設 B） CPU和外設C）外存和外設 D） 主存和CPU說明：I/O通道帶有專用處理器

14、的、有很強I/O處理功能的智能部件，它可以獨立地完成系統處理器交付的I/O操作任務，此時，I/O總線直接與通道相連而不與處理器相連。通道具有自己專門的指令集，在設備與存儲器之間傳送數據。系統主處理器只需進行I/O操作的委托，其后的所有I/O操作均由通道自己進行。完成后只需向系統處理器發出中斷，請求結束。可見，這種方式可以形成系統處理器與I/O設備之間的并行操作。第六章練習題1.一個進程獨立打開一個文件后畫出打開文件結構，標出與打開文件有關的各部分數據結構名稱。2.UNIX的rm命令使用了系統調用 B 。A) close B) unlinkC) fcntl D) umask3.在UNIX中超級塊

15、filsys的當前情況如圖6-19所示，某文件順序釋放了物理盤塊號為1150、1151、1175、1050的四個盤塊，畫出釋放后有關部分的變化結果。答：4.說明UNIX文件的地址索引結構，并描述如何由文件的邏輯塊號n找到文件的物理塊號。答：（1） 0<=n<9: 物理塊號blkno = i_an（2） 9<n<=10+341:直接索引的blkno = i_a10;物理塊號blkno =直接索引塊的第n-10項內容。（3） 10+341<n<=10+341+341*341:一級間接索引的blkno = i_a11;直接索引的blkno = 一級間接索引塊的第（

16、n-10-341）/341項內容;物理塊號blkno =直接索引塊的第（n-10-341）%341項內容；（4） 10+341+341*341 < n < 10+341+341*341+341*341*341:二級間接索引的blkno = i_a12;一級索引的blkno = 二級間接索引塊的第（n-10-341-341*341）/（341*341）項內容;其余情況可以從情況3類推。5. Unix的打開文件結構涉及到 A 這三種結構。A) ofile,file,inode B) ofile ,file,addr40C) file,direct,inode D) file,inode

17、,filsys第十一章練習題1基于符號鏈接與普通鏈接的文件共享方式各有什么優點？答：普通鏈接（硬鏈接）：在UNIX同一個文件系統中，同一層次或不同層次的目錄項可指向同一個文件的I節點，這就是目錄結構的勾連。由此，不同用戶或同用戶可以在不同的位置上用不同的文件名（或相同的文件名）訪問同一個文件。這為文件的共享提供了方便。 符號鏈接：硬鏈接有兩個局限，第一是不能為一個目錄創建一個鏈接；第二是不能在不同文件系統中建立文件鏈接。使用符號鏈接就能實現上述兩個功能。符號鏈接建立了新的文件或目錄與原來文件或目錄的路徑名映照。當你訪問一個符號鏈接時，UNIX靠這個映照找到原文件的路徑，所以這種鏈接方法又稱為軟

18、鏈接。通過軟鏈接訪問文件的速度比硬鏈接稍慢一些。 2用find命令和grep命令的組合顯示當前目錄樹下所有C源程序中含有main( )的行。答：find . name *.c | grep main( ) find . name *.c exec grep main( ) ;3. 用于確定字符串模式的一個規則集稱為 A 。A) 正則表達式B) 字符串匹配C) 文件名匹配D) 過濾器第十二章練習題1.寫出用當前目錄中所有的C目標代碼生成檔案庫arch的命令。ar rv libarch.a ./*.o2.根據一些說明和文件的修改時間自動地維護模塊間的關系的程序是 D 。A) sdb B) sccs C) ar D) make3.決定Makefile依賴行中依賴關系的是文件的 A 。A)修改時間 B) 創建時間C) 大小 D) 存取權限第十三、十四、十五章練習題1.可以在不同系統之間傳送文件的程序是 A 。（A) ftp B) rcp C) write D) telnet2.普通用戶可以利用文件的系統調用 A 實現鎖功能。A) creat B) ope