操作系統(tǒng)題解析

南開大學信息技術科學學院考試卷2004-2005年度第一學期期末操作系統(tǒng)A卷（共7頁）專業(yè) 姓名 學號 成績 第一部分：基本知識與概念（共25分）一．名詞解釋（共8分，每題2分）1．競爭條件與臨界區(qū)競爭條件：兩個或者多個進程讀寫某些共享數(shù)據(jù)，而最后的結果取決于進程運行的精確時序，這稱為競爭條件。臨界區(qū)：對共享數(shù)據(jù)進行訪問的程序片斷稱為臨界區(qū)。（注意，共享數(shù)據(jù)或共享內存都算對）。2．DMADMA，全稱為存儲器直接讀取。它是一種機制，用以實現(xiàn)I/O設備與進程之間的數(shù)據(jù)異步傳輸。（描述性回答即可，重點在于異步傳輸）3．系統(tǒng)顛簸在分頁式存儲管理系統(tǒng)中，如果一個進程的工作集無法全部保存在內存中，那么在進程運行的過程中將引起頻繁的頁面調度，每隔幾條指令就發(fā)生一次頁面故障。這種現(xiàn)象稱為系統(tǒng)顛簸。（重點在于頻繁的頁面調度，不說出工作集也沒關系）4．文件與目錄文件是磁盤（或外部存儲設備）保存數(shù)據(jù)和信息的邏輯單元。目錄是為了實現(xiàn)對文件的有效管理（檢索、讀?。┒O計的一種機制，在很多操作系統(tǒng)中，目錄也以文件的形式存在。二．判斷題（共5分，每題0.5分）操作系統(tǒng)的存儲器管理部分負責對進程進行調度。 （F）a） 正確答案：內核負責進程調度設計實時操作系統(tǒng)時，應首先考慮系統(tǒng)可靠性和靈活性。（F）a）正確答案：首先考慮實時性，呵呵。進程是指令的集合。（F）a）正確答案：進程是指令和數(shù)據(jù)的集合。P、V操作（Up、Down操作）可以解決一切互斥問題。 （T）a）解釋：P、V操作的確可以解決一切互斥問題信箱通信是一種進程間直接通信方式。（F）a）正確答案：信箱通信是一種間接通信方式，而基于會合機制的消息通信是直接通信。TOC\o"1-5"\h\z銀行家算法是一種死鎖避免算法。 （T）a）解釋：地球人都知道吧！當進程數(shù)大于資源數(shù)時，一定會產(chǎn)生死鎖。 （F）a）正確答案：可能產(chǎn)生死鎖，但不一定，要是一定產(chǎn)生死鎖的話，要銀行家算法干嗎呀！采用虛擬存儲器技術的首要目的是為了實現(xiàn)存儲保護。 （F）a）正確答案：首要目的是擴充存儲空間在操作系統(tǒng)中，用戶使用I/O設備時，通常采用物理設備名。 （F）a）正確答案：設備無關性使得用戶使用統(tǒng)一命名的邏輯名稱。順序式文件結構不利于文件長度的動態(tài)增長。（T）a）解釋：順序文件的特點在于一次分配所有空間，動態(tài)增長的話就難辦了。三．單項選擇題（共12分，每題2分）進程地址空間中邏輯地址變成內存中物理地址的過程叫做__A 重定位B.物理化C.邏輯化D.加載進程間的同步是指進程間在邏輯上的相互__B 關系。A.聯(lián)接B.制約C.繼續(xù)D.調用中斷發(fā)生后，應保存__B 。A.緩沖區(qū)指針 B.關鍵寄存器內容C.被中斷的程序 D.頁表以下敘述正確的是__C 。A.在現(xiàn)代計算機中，只有I/O設備才是有效的中斷源在中斷處理過程中必須屏蔽所有中斷（所有同類中斷）同一用戶使用的I/O設備也可能并行工作Spooling是脫機I/O系統(tǒng)某系統(tǒng)中有3個并發(fā)進程，都需要同類資源4個，試問該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是__B 個。A.9B.10C.11D.12常用的文件存取方法有兩種：順序存取和__D___存取。A.流式B.串聯(lián)C.索引D.隨機第二部分：操作系統(tǒng)結構與原理（共40分）四．簡答題（共28分，每題7分）操作系統(tǒng)以進程為單位分配各種資源，進程調度是操作系統(tǒng)必須完成的重要任務，請簡要回答，操作系統(tǒng)有哪兩種進程調度方式？并舉出至少4種不同類型的進程調度算法。答案：兩種調度方式：可剝奪調度和不可剝奪調度方式。（答錯一個扣1分）四種調度算法：時間片輪轉、優(yōu)先級調度、多重隊列、最短作業(yè)優(yōu)先、保證調度、彩票調度、實時調度、兩級調度法等，任選四種即可。（少答或者答錯一個扣1分）I/O設備管理是操作系統(tǒng)的主要功能之一，請簡要回答，操作系統(tǒng)設計種，I/O軟件的主要功能目標和主要層次。答案：I/O軟件的功能目標：解決同步（阻塞）－異步（傳輸）問題實現(xiàn)對設備訪問的錯誤處理實現(xiàn)設備無關性——統(tǒng)一命名法實現(xiàn)對專有設備和共享設備的有效管理以上未答或者少答一個扣1分，只要表達含義正確即可，無順序要求I/O軟件的主要層次：用戶層軟件－設備無關操作系統(tǒng)軟件－設備驅動程序－中斷處理程序軟件層次如果未答或者少答，每個扣1分，注意，如果發(fā)生順序錯誤也要扣1分。造成進程死鎖的條件有哪些？處理死鎖的主要策略有哪些？答案：造成死鎖的條件：互斥條件；保持和等待條件；非剝奪條件；循環(huán)等待條件。少答或者錯答每個扣0.5分。處理死鎖的策略有哪些：不理會：鴕鳥算法死鎖檢測和恢復：通過監(jiān)控資源圖并撤銷死鎖進程予以恢復死鎖預防：破壞造成死鎖的四個條件以防止死鎖發(fā)生死鎖避免：通過資源軌跡圖或銀行家算法進行有效避免。如果少答或者答錯一個策略，每個扣1分。注意：本題正常的評分總分為6分，另外1分是專門提供給描述死鎖策略的學生。如果只列出死鎖的解決策略名稱而未進行解釋，則最高給6分。

請列出最少4種用于分頁存儲管理的頁面替換算法答案：最近未使用頁面替換算法先進先出頁面替換算法第二次機會頁面替換算法（時鐘頁面替換算法）最久未使用頁面替換算法（軟件模擬的LRU算法）以上為四種常見的頁面替換算法，少答一個或者答錯一個扣 1.5分，總分為6分，額外1分提供給對算法進行簡要介紹的同學。特別注意，答案中括號內的算法與其前面括號外的算法只能算 1種，如兩者皆出現(xiàn)則只算一種頁面調度算法。五?論述題（共12分）操作系統(tǒng)被引導后，經(jīng)歷了一個復雜的初始化過程，其中包括內存初始化、中斷初始化以及系統(tǒng)任務初始化。請簡要論述中斷處理從啟動到就緒（等待各類中斷）的過程，簡要說明存在哪些數(shù)據(jù)結構、需要進行哪些處理步驟。答案：示意圖形式如下:gate_tablem在prot_init函數(shù)中初始化gate_table答案：示意圖形式如下:gate_tablem在prot_init函數(shù)中初始化gate_table，填充中斷處理程序的入口地址建立堆棧、設置寄存器cstart函數(shù)（初始化」rqtable）引導分區(qū)Boot程序引導引導分區(qū)MPX386.S答案細則:與中斷初始化直接關聯(lián)的數(shù)據(jù)結構包括 gate_table和」rq_table,與中斷初始化有關的數(shù)據(jù)結構包括tasktab和rdy_head,rdy_tail。數(shù)據(jù)結構內容的的答案分值為5分，其中gate_table和」rq_table各為2分,tasktab和rdy_head>rdy_tail共占1分。不要求數(shù)據(jù)結構嚴格的用變量名描述,用文字描述亦可。處理過程主要包括3部分：a） 第一部分：系統(tǒng)引導階段，初始化gate_table（填充中斷門描述符），這一部分是在CStart函數(shù)中完成的。該步驟2分b） 第二部分：8259初始化階段，初始化」rq_table，將其填充為無效值，這一部分是在Main函數(shù)中通過調用intr_init實現(xiàn)的。該步驟2分。c） 第三部分：填充_irq_table并開始響應中斷階段。這一部分是在Main函數(shù)中通過初始化系統(tǒng)任務進程并將其插入到系統(tǒng)任務進程的就緒隊列中完成的。該步驟2分。以上兩部分的總分為11分，剩余1分用于提供給卷面清晰、描述完整、準確的學生作為卷面分。注意，可用圖、文字的形式描述。第三部分：操作系統(tǒng)設計與實現(xiàn)（35分）六．若在操作系統(tǒng)的就緒進程隊列中等待運行的共有三個進程 1、2、3，已知它們各自的運行時間為a、b、c，且滿足關系a<b<c。請證明采用最短作業(yè)優(yōu)先調度算法能夠獲得最小平均周轉時間。（10分）證明：假設進程被調度運行的順序為P1、P2、P3，每個進程的運行時間為T1、T2、T3。若采用非時間片輪轉算法，則平均周轉時間的計算公式為：平均周轉時間=（3T1+2T2+T3）/3=T1+2T2/3+T3/3;若采用時間片輪轉算法，則平均周轉時間的計算公式為：平均周轉時間=（N1+N2+N3—2）Ts=T1+T2+T3—2Ts其中Ts為時間片大小顯然可見，采用非時間片輪轉的平均周轉時間小于采用時間片輪轉算法，在各種非時間片輪轉的線程調度算法中，保證平均周轉時間最小的條件為T1<T2<T3,即遵循最短作業(yè)優(yōu)先的思想調度進程運行。該題實際是考察平均周轉時間的計算公式，同時考察對各類進程調度算法進行分析的準確性。凡是平均周轉時間的計算公式寫錯的，最多給2分。公式正確給4分，分析過程清晰合理給6分，適當給分即可。

七?試論述分頁存儲管理和分段存儲管理技術的主要區(qū)別。 （10分）差別因素分頁分段地址空間維度1維2維，可以有多個線性地址空間管理維護方式（或者是“需要程序員知道此種技術嗎？”）不需要，OS自己維護頁表和地址映射需要，需要提供段號和段內地址才能實現(xiàn)地址重定位數(shù)據(jù)和指令空間可分離嗎？不可分離可分離能夠較好的適應動態(tài)大小變化嗎？不能能主要缺陷內零頭外零頭主要目的擴充存儲器的可用空間，使得超過存儲器大小的程序也能夠正常運行對進程內的數(shù)據(jù)和指令實現(xiàn)邏輯獨立的地址劃分，從而促進共享和保護。注意：分頁和分段技術的差別主要體現(xiàn)在5-6個層面，凡是回答出上表中5個或者5個以上的均可得滿分。但是如果學生回答的內容中，性質相同或者原理一樣的差別因素不能累計記分，只能算一個差別。少回答或者答錯一個差別，扣2分。八?請閱讀Minix操作系統(tǒng)源代碼片斷，并回答問題。（15分）問題1:請簡述Minix操作系統(tǒng)針對消息發(fā)送的主要處理步驟。MINIX使用基于會合原理的消息通信機制。答案：首先，進行死鎖檢查目標進程是否正在向該進程發(fā)送消息，如果是則報錯返回。否則繼續(xù)，其次，檢查目標進程是否在等待該消息，如果目標進程等待該消息，則拷貝數(shù)據(jù)，設置兩進程為就緒態(tài)。第三，如果目標進程未等待該消息，則阻塞 Send進程，將其掛入等待隊列中該小問為6分，和消息內容拷貝條件的，給2分，講清楚阻塞條件的給2分，2分提供給卷面清晰、描述完整的同學。問題2：請簡述Minix操作系統(tǒng)針對消息接收的主要處理步驟MINIX使用基于會合原理的消息通信機制。答案：首先，檢查目標進程是否因為向該進程發(fā)送消息而被阻塞，如果是，則將消息自發(fā)送進程拷貝至接收進程，清除發(fā)送進程的Sending狀態(tài)或將其解除阻塞。其次，如果沒有進程向本進程發(fā)送消息，則阻塞Recv進程，將其掛如等待隊列中。并將其就緒態(tài)清除。該小問為6分，講清楚接收數(shù)據(jù)和解除阻塞過程的，給2分，講清楚自身被阻塞的給2分，2分提供給卷面清晰、描述完整的同學。問題3：請在代碼片斷中添加注釋PRIVATEintmini_send(caller_ptr,dest,m_ptr){/*Sendamessagefrom'caller_ptr'to'dest'.If'dest'isblockedwaiting*forthismessage,copythemessagetoitandunblock'dest'.If'dest'is*notwaitingatall,oriswaitingforanothersource,queue'caller_ptr'.*/registerstructproc*dest_ptr,*next_ptr;dest_ptr=proc_addr(dest);/*pointertodestination'sprocentry*/Ln7076if(dest_ptr->p_flags&SENDING){next_ptr=proc_addr(dest_ptr->p_sendto);while(TRUE){}Ln7085}if(next_ptr