操作系統(tǒng)考試知識點(diǎn)
1.什么是操作系統(tǒng)？操作系統(tǒng)主要動力？
概念：
操作系統(tǒng)是指控制和管理整個計算機(jī)系統(tǒng)的硬件和軟件管理資源，合理組織、調(diào)度計算機(jī)資源的分配，進(jìn)而為用戶和其他軟件提供方便接口與環(huán)境的程序的集合，操作系統(tǒng)是計算機(jī)系統(tǒng)中最基本的系統(tǒng)軟件。（操作系統(tǒng)是覆蓋在硬件上的第一層軟件，是對硬件系統(tǒng)的首次擴(kuò)充）。
主要動力：
不斷提高計算機(jī)資源利用率；方便用戶；器件的不斷更新?lián)Q代；計算機(jī)體系結(jié)構(gòu)不斷發(fā)展；不斷提出新的應(yīng)用需求。
作用：
作為用戶和計算機(jī)硬件之間的接口；系統(tǒng)資源的管理者；實(shí)現(xiàn)對計算機(jī)資源的抽象。
2、操作系統(tǒng)基本特性？
并發(fā)—兩個或多個進(jìn)程在同一時間間隔內(nèi)發(fā)生
共享—系統(tǒng)中的資源供并發(fā)的進(jìn)程共同使用
虛擬
異步。
3、處理機(jī)管理有哪些功能？進(jìn)程控制、進(jìn)程同步、進(jìn)程通信、進(jìn)程調(diào)度
4、存儲器管理有哪些功能？內(nèi)存保護(hù)、內(nèi)存分配、內(nèi)存擴(kuò)充、地址映射
5、設(shè)備管理有哪些功能？緩沖管理、設(shè)備分配、設(shè)備處理。
6、文件管理有哪些功能？存儲空間管理、目錄管理、文件讀寫管理和保護(hù)。
7、用戶與操作系統(tǒng)的接口包括？用戶接口、程序接口（程序接口用系統(tǒng)調(diào)用實(shí)現(xiàn)）。
8、什么是進(jìn)程？臨界區(qū)、臨界資源、進(jìn)程互斥和同步、忙等概念、
進(jìn)程：進(jìn)程是正在運(yùn)行的程序的實(shí)例（進(jìn)程是一個具有獨(dú)立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運(yùn)行活動/是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位）。
臨界區(qū)：在每個進(jìn)程中訪問臨界資源的那段代碼。
臨界資源：在一段時間內(nèi)只允許一個進(jìn)程訪問的資源。
進(jìn)程互斥：一組進(jìn)程中的一個或多個程序段因共享某一共享資源而不許交叉執(zhí)行，即不允許兩個以上的共享該資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)
進(jìn)程同步：異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約相互發(fā)送消息而進(jìn)行相互合作，等待，是各個進(jìn)程按一定的速度執(zhí)行的過程。
忙等：已經(jīng)有進(jìn)程進(jìn)入臨界區(qū)時，表明臨界區(qū)資源正在被訪問，其他試圖進(jìn)入臨界區(qū)的進(jìn)程都必須等待。
9、信號量機(jī)制，信號量必須設(shè)對
10、線程概念？
線程：是被系統(tǒng)獨(dú)立調(diào)度和分派的基本運(yùn)行程序單位，是比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位，又稱為輕量級線程。
11、進(jìn)程和程序的區(qū)別？
進(jìn)程是動態(tài)的，進(jìn)程是程序的一次執(zhí)行過程，是臨時的有生命期的，它由創(chuàng)建而產(chǎn)生，完成任務(wù)后被撤銷；
程序是靜態(tài)的， 可以作為軟件資源長期保存。
12、并發(fā)和并行（io和CPU、io和io）的區(qū)別？
并發(fā)是同一時間段內(nèi)兩個或以上的進(jìn)程同時執(zhí)行；
并行是同一時刻兩個或以上的進(jìn)程同時執(zhí)行。
13、甘特圖，求周轉(zhuǎn)時間、吞吐量、等待時間，什么是吞吐量
吞吐量：單位時間內(nèi)系統(tǒng)能完成的作業(yè)數(shù)。
14、可剝奪和不可剝奪算法有什么？
可剝奪（可搶占）算法：搶占式調(diào)度算法（CFS）、時間片輪轉(zhuǎn)算法（Round Robin）；
不可剝奪（不可搶占）算法：實(shí)時調(diào)度算法(優(yōu)先級調(diào)度算法)、死鎖避免算法（銀行家算法、資源分配圖算法）。
15、死鎖定義、四個必要條件、死鎖避免、安全狀態(tài)、資源分配圖化簡、死鎖定理、銀行家算法
什么是死鎖：在多道程序設(shè)計中，當(dāng)一組進(jìn)程中的每個進(jìn)程均無限期等待該組進(jìn)程中其他進(jìn)程才能引發(fā)的事件，系統(tǒng)則處于死鎖狀態(tài)。
形成死鎖的必要條件：1互斥條件2請求和保持條件3不可搶占條件4循環(huán)等待條件。
死鎖避免：系統(tǒng)在進(jìn)行資源分配時，應(yīng)該防止系統(tǒng)進(jìn)入不安全狀態(tài)。
安全狀態(tài)：指系統(tǒng)能按進(jìn)程某種推進(jìn)順序?yàn)槊總€進(jìn)程分配其所需資源，直至滿足每個進(jìn)程所需數(shù)量，使每個進(jìn)程都能順利完成。
死鎖定理：S為死鎖狀態(tài)的充分條件是當(dāng)且僅當(dāng)S的資源分配圖是不可完全化簡的。
16、如果系統(tǒng)中有n個進(jìn)程，則在
運(yùn)行狀態(tài)：最多1個，最少0個；
就緒狀態(tài)：最多n-1，最少0個；
等待狀態(tài)：最多n個（死鎖），最少0個。
17、存儲管理的主要方式？實(shí)存儲有幾種方法填空，頁式管理
分區(qū)存儲管理、分頁存儲管理、分段存儲管理、段頁式存儲管理、虛擬存儲管理。
18、淘汰算法
最佳置換算法（optimal）、先進(jìn)先出頁面置換算法（FIFO）、最近最久未使用算法（LRU,least recently used）、最少使用置換算法（LFU）、Clock置換算法。
19、動態(tài)分區(qū)分配算法（基于順序搜索）
首次適應(yīng)算法FF（從鏈?zhǔn)组_始查找，優(yōu)先利用內(nèi)存中的低地址部分空閑分區(qū)）；
循環(huán)首次適應(yīng)算法NF（從上次找到的空閑分區(qū)的下個空閑分區(qū)開始查找，空閑分區(qū)分布均勻但缺乏大的空閑分區(qū)）；
最佳適應(yīng)算法BF（滿足要求且最小的空閑分區(qū)）--外部碎片
最壞適應(yīng)算法WF（滿足要求且最大的空閑分區(qū)，缺乏大空閑分區(qū)，產(chǎn)生碎片的可能性最小）
（FF\NF效率差不多，效率最高）
碎片：難以利用的很小的空閑分區(qū)。
20、頁式管理?。。。?！給頁表、邏輯地址1000\2000\4000、每頁大小1024，計算物理地址，取整取余。地址越界
頁號P，頁內(nèi)偏移量W，邏輯地址A，頁面大小L；
邏輯地址對頁面大小取整INT[A/L]，取余
1000/1024=0?? 1000mod1024=1000? 第0頁在第i塊，物理地址為：i*1024+1000
2000/1024=1?? 2000mod1024=976?? 第1頁在第n塊，物理地址為：n*1024+976
4000/1024=3?? 4000mod1024=928?? 第3頁在第x塊，物理地址為：x*1024+928>頁面大小，該邏輯地址非法越界。
21、多級頁表---P
22、調(diào)入:預(yù)調(diào)入、請求調(diào)入
預(yù)調(diào)頁策略—以預(yù)測為基礎(chǔ)，將那些預(yù)計在不久后被訪問的頁面事先調(diào)入到內(nèi)存中。
請求調(diào)頁策略—當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分?jǐn)?shù)據(jù)和程序時，若發(fā)現(xiàn)其所在的頁面不在便立即提出請求，由操作系統(tǒng)將其所在的頁面調(diào)入。
23、訪問內(nèi)存的有效時間，引入快表
求EAT
24、什么是io設(shè)備？
IO設(shè)備指輸入輸出設(shè)備，是數(shù)據(jù)處理系統(tǒng)的關(guān)鍵外部設(shè)備，可以和計算機(jī)交互使用。
除了內(nèi)存和CPU的設(shè)備稱為外設(shè)。
25、IO系統(tǒng)的基本功能？
隱藏物流設(shè)備的細(xì)節(jié)、與設(shè)備的無關(guān)性、提高處理機(jī)和IO設(shè)備利用率、對IO設(shè)備進(jìn)行控制、確保對設(shè)備的正確共享、錯誤處理。
26、IO系統(tǒng)的軟件層次結(jié)構(gòu)？最上層最下層
27、塊設(shè)備、字符設(shè)備是什么？
塊設(shè)備是指數(shù)據(jù)的存取和傳輸是以數(shù)據(jù)塊為單位的設(shè)備；（磁盤（一個扇區(qū)，簇為單位，有多個sector）
字符設(shè)備是指數(shù)據(jù)的存取和傳輸是以字符為單位的設(shè)備（鍵盤）。
28、輸入輸出的通道類型？數(shù)組選擇通道、字節(jié)選擇、字節(jié)通道
30、什么是內(nèi)中斷？
內(nèi)中斷指因硬件出錯或運(yùn)算出錯引起的中斷，是不可屏蔽中斷。
31、數(shù)據(jù)傳輸?shù)乃姆N控制方式？、
程序輪詢方式（循環(huán)指令，busy=1，尚未完成輸入字符）
中斷方式（CPU和io設(shè)備都處于忙碌狀態(tài)，CPU用很短的時間處理中斷，大大提高整個系統(tǒng)的資源利用率和吞吐量）---字節(jié)
DMA方式（命令/狀態(tài)寄存器、地址寄存器、數(shù)據(jù)寄存器、數(shù)據(jù)計數(shù)器，減少了CPU干預(yù)）---一個數(shù)據(jù)塊
通道方式（通道程序結(jié)束位P=1表示本條指令是程序最后一條，程序結(jié)束；記錄結(jié)束標(biāo)志R=1表示處理某記錄的最后一條指令）---一組數(shù)據(jù)塊
緩沖區(qū)不看
32、磁盤格式化：低格（重新劃分磁道區(qū)）和高格（文件分配表，數(shù)據(jù)沒有刪）
低級格式化：將磁盤的各個磁道劃分為扇區(qū)；
高級格式化：設(shè)置一個引導(dǎo)塊，空閑存儲管理、根目錄和一個文件系統(tǒng)，同時在分區(qū)表中標(biāo)記該分區(qū)所使用的文件系統(tǒng)。
33、磁盤的三個時間？
尋道時間=S+m*n(啟動磁頭臂的時間+跨越n個磁道的時間)
延遲時間=旋轉(zhuǎn)磁盤，使磁頭定位到目標(biāo)扇區(qū)
平均延遲時間=1/2*1/r=1/2r，1/r是轉(zhuǎn)一圈的時間=讀寫一個磁道的時間
傳輸時間=從磁盤讀寫數(shù)據(jù)的時間
1/r*b/N（讀寫一個磁道的時間*磁道數(shù)），一共b字節(jié)，每個磁道存N字節(jié)
存儲容量=磁頭數(shù)（盤面數(shù)）*磁道數(shù)（柱面數(shù)）*每道扇區(qū)數(shù)*每道字節(jié)數(shù)
訪問時間=尋道時間+旋轉(zhuǎn)延遲時間+傳輸時間+控制器時間
33、磁盤引臂調(diào)度算法：FCFS，SCAN，最短作業(yè)優(yōu)先。有異議的不考
先到先服務(wù)FCFS
最短尋找時間優(yōu)先
SCAN（從內(nèi)向外移動，直到最外層再向內(nèi)從大到小移動)響應(yīng)頻率不平均
LOOK（從內(nèi)向外移動，直到?jīng)]有請求再向內(nèi)從大到小移動）
C-SCAN（從內(nèi)向外移動，直到最外層再直接移到0號位置，再向外移動）
C-LOOK（從內(nèi)向外移動，直到最外層再直接移到最內(nèi)層有請求的位置，再向外移動）
34、什么是文件？什么是文件目錄（fcb）？邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（順序、鏈接、索引）。
文件：指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合
文件目錄：一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識系統(tǒng)中的文件及其物理地址，供檢索時使用。
35、FAT會計算，課后思考題
?
36、文件存儲空間分配管理的幾種方式?
空閑表法和空閑鏈表法、位示圖法、成組鏈接法。
文件邏輯結(jié)構(gòu)：
按結(jié)構(gòu)分類—有結(jié)構(gòu)文件、無結(jié)構(gòu)文件；
按組織方式分類—順序文件、索引文件、索引順序文件；
文件物理結(jié)構(gòu)：
順序文件、索引文件。
37、塊地址在內(nèi)存和塊在內(nèi)存不一樣？
塊地址指的是內(nèi)存中某個塊的起始地址，而塊在內(nèi)存空間中指的是一段連續(xù)的地址空間。
38、磁盤三維，公式(取整取余、對余數(shù)再取整取余)？6個盤面、8個扇區(qū)、200磁道數(shù)，數(shù)數(shù)也能數(shù)出來（6列，6*8=48，0-47）
柱面號=塊號/（磁頭數(shù)*總扇區(qū)數(shù)）
盤面號=磁頭號=（塊號mod（磁頭數(shù)*總扇區(qū)數(shù)））/一個盤面的扇區(qū)數(shù)
扇區(qū)號=（塊號mod（磁頭數(shù)*扇區(qū)數(shù)））mod扇區(qū)數(shù)
39、混合索引。一個i結(jié)點(diǎn)對應(yīng)一個文件（inode）
部分習(xí)題總結(jié)
操作系統(tǒng)引論
1．??? 分時系統(tǒng)的響應(yīng)時間（及時性）主要是根據(jù)（A）確定的，而實(shí)時系統(tǒng)的響應(yīng)時間則是由（B）確定的。
A，??? B：（1）時間片大??；（2）用戶數(shù)目；（3）計算機(jī)運(yùn)行速度；（4）用戶所能接受的等待時間；（5）控制對象所能接受的時延；（6）實(shí)時調(diào)度
解答：A：（4）；B：（5）
2．??? 在分時系統(tǒng)中，為使多個用戶能夠與系統(tǒng)交互，最關(guān)鍵的問題是（A）；當(dāng)用戶數(shù)目為100時，為保證響應(yīng)時間不超過2s，此時的時間片最大應(yīng)為（B）。
A：（1）計算機(jī)具有足夠高的速度；（2）內(nèi)存容量足夠大；（3）系統(tǒng)能及時接收多個用戶的輸入；（4）能在較短的時間內(nèi)，使所有用戶程序都能得到運(yùn)行；（5）能快速進(jìn)行內(nèi)外存對換；
B：（1）10ms；（2）20ms；（3）50ms；（4）100ms；（5）200ms；
解答：A：（4）；B：（2）
?
?
3．??? 從下面關(guān)于模塊化程序的的敘述中選出，選出五條正確的敘述。
（1） 使程序設(shè)計更為方便，但比較難維護(hù)
（2） 便于由多人分工編制大型程序
（3） 便于軟件功能擴(kuò)充
（4） 在內(nèi)存能夠容納的前提下，應(yīng)使模塊盡可能大，以減少模塊的個數(shù)
（5） 模塊之間的接口叫數(shù)據(jù)文件
（6） 只要模塊接口不變，各模塊內(nèi)部實(shí)現(xiàn)細(xì)節(jié)的修改，不會影響別的模塊
（7） 使程序易于理解，也利于排錯
（8） 模塊間的單向調(diào)用關(guān)系，形成了模塊的層次式結(jié)構(gòu)
（9） 模塊愈小，模塊化的優(yōu)點(diǎn)愈明顯。一般來說，一個模塊的大小在10行以下。
（10）?? 一個模塊實(shí)際上是一個進(jìn)程
解答：2、3、6、7、8
?
4．??? 采用（A）結(jié)構(gòu)時，將OS分成用于實(shí)現(xiàn)OS最基本功能的內(nèi)核和提供各種服務(wù)的服務(wù)器兩個部分。通常，下列模塊中必須包含在操作系統(tǒng)內(nèi)核中的是（B）模塊。
A：（1）整體式；（2）模塊化；（3）層次式；（4）微內(nèi)核；
B：（1）內(nèi)存分配；（2）中斷處理；（3）文件處理；（4）命令處理；
解答：A：（4）；B：（2）
?
進(jìn)程管理習(xí)題
1．??? 在將CPU的執(zhí)行狀態(tài)分為用戶態(tài)和核心態(tài)的系統(tǒng)中，應(yīng)該在核心態(tài)下執(zhí)行的指令依次為（A）、（B）、（C）。而從用戶狀態(tài)轉(zhuǎn)換到系統(tǒng)狀態(tài)是通過（D）實(shí)現(xiàn)的。
?
A，B，C：（1）屏蔽所有中斷；（2）讀時鐘；（3）設(shè)置時鐘的值；（4）存取內(nèi)存中某地址單元的值；（5）停機(jī)。
D：（1）執(zhí)行進(jìn)程直接修改程序狀態(tài)字；（2）中斷屏蔽；（3）中斷；（4）進(jìn)程調(diào)度；
解答：A：（1）；B：（3）；C：（5）；D：（3）
?
2．??? 在分時系統(tǒng)中，導(dǎo)致進(jìn)程創(chuàng)建的典型事件是（A）；在批處理系統(tǒng)中，導(dǎo)致進(jìn)程創(chuàng)建的典型事件是（B）；由系統(tǒng)專門為運(yùn)行中的應(yīng)用進(jìn)程創(chuàng)建新進(jìn)程的事件是（C）；在創(chuàng)建進(jìn)程時，（D）不是創(chuàng)建所必須的步驟。
?
A：（1）用戶注冊；（2）用戶登錄；（3）用戶記賬；（4）用戶通信。
B：（1）作業(yè)錄入；（2）作業(yè)調(diào)度；（3）進(jìn)程調(diào)度；（4）中級調(diào)度。
C：（1）分配資源；（2）進(jìn)行通信；（3）共享資源；（4）提供服務(wù)。
D：（1）為進(jìn)程建立PCB；（2）為進(jìn)程分配內(nèi)存等資源；（3）為進(jìn)程分配CPU；（4）將進(jìn)程插入就緒隊(duì)列；
解答：A：（2）；B：（2）；C：（4）；D：（3）
?
3．??? 從下面對臨界區(qū)的論述中，選出兩條正確的論述。
（1） 臨界區(qū)是指進(jìn)程中用于實(shí)現(xiàn)進(jìn)程互斥的那段代碼
（2） 臨界區(qū)是指進(jìn)程中用于實(shí)現(xiàn)進(jìn)程同步的那段代碼
（3） 臨界區(qū)是指進(jìn)程中用于實(shí)現(xiàn)進(jìn)程通信的那段代碼
（4） 臨界區(qū)是指進(jìn)程中用于訪問共享資源的那段代碼
（5） 臨界區(qū)是指進(jìn)程中訪問臨界資源的那段代碼
（6） 臨界區(qū)是指進(jìn)程中用于實(shí)現(xiàn)進(jìn)程互斥的那段代碼
（7） 若進(jìn)程A與進(jìn)程B必須互斥地進(jìn)入自己的臨界區(qū)，則進(jìn)程A處于對應(yīng)的臨界區(qū)內(nèi)時，仍有可能被進(jìn)程B中斷
（8） 若進(jìn)程A與進(jìn)程B必須互斥地進(jìn)入自己的臨界區(qū)，則進(jìn)程A處于對應(yīng)的臨界區(qū)內(nèi)時，便不能被進(jìn)程B中斷
解答：5、6
?
4．??? 使用mail命令的信箱通信屬于（A），因?yàn)樾畔⑹潜话l(fā)送到接收方的（B）中；使用write命令，實(shí)現(xiàn)的是（C）通信，因?yàn)樾畔⑹潜话l(fā)送到接收方的（D）；使用共享文件進(jìn)行通信的方式屬于（E）。
?
A，C，E：（1）共享存儲器；（2）實(shí)時通信；（3）消息緩沖通信；（4）非實(shí)時通信；（5）管道通信。
B，D：（1）消息緩沖隊(duì)列；（2）內(nèi)存；（3）信箱；（4）消息緩沖區(qū)；（5）屏幕；（6）共享存儲區(qū)
解答：A：（4）；B：（3）；C：（2）；D：（5）；E：（5）
?
5．??? 從下面的敘述中選出一條正確的敘述。
（1） 操作系統(tǒng)的一個重要概念是進(jìn)程，不同進(jìn)程所執(zhí)行的代碼也不同
（2） 操作系統(tǒng)通過PCB來控制和管理進(jìn)程，用戶進(jìn)程可從PCB中讀出與本身運(yùn)行狀態(tài)相關(guān)的信息
（3） 當(dāng)進(jìn)程由執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)時，CPU現(xiàn)場信息必須被保存在PCB中。
（4） 當(dāng)進(jìn)程申請CPU得不到滿足時，它將處于阻塞狀態(tài)
（5） 進(jìn)程是可于其它程序并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運(yùn)行過程，所以程序段是進(jìn)程存在的唯一標(biāo)志
?
解答：3
?
6．??? 從下面的敘述中選出4條正確的敘述。
（1） 一個進(jìn)程的狀態(tài)發(fā)生變化總會引起其他一些進(jìn)程的狀態(tài)發(fā)生變化。
（2） 進(jìn)程被掛起（suspend）后，狀態(tài)變?yōu)樽枞麪顟B(tài)。
（3） 信號量的初值不能為負(fù)值。
（4） 線程是CPU調(diào)度的基本單位，但不是資源分配的基本單位。
（5） 在進(jìn)程對應(yīng)的代碼中使用wait、signal操作后，可以防止系統(tǒng)發(fā)生死鎖。
（6） 管程每次只允許一個進(jìn)程進(jìn)入。
（7） wait、signal操作可以解決一切互斥問題。
（8） 程序的順序執(zhí)行具有不可再現(xiàn)性。
?
解答：3、4、6、7
7．??? 試比較進(jìn)程和管程的異同點(diǎn)
（1）? 管程和進(jìn)程都定義了數(shù)據(jù)結(jié)構(gòu),進(jìn)程定義的是私有數(shù)據(jù)結(jié)構(gòu)進(jìn)程控制塊;管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如消息隊(duì)列。
（2）? 管程和進(jìn)程都在各自的數(shù)據(jù)結(jié)構(gòu)上進(jìn)行有意義的操作。進(jìn)程是由順序程序執(zhí)行有關(guān)操作，管程主要是同步操作和初啟操作。
（3）? 管程和進(jìn)程設(shè)置的目的不同，進(jìn)程是為了更好的刻畫可實(shí)現(xiàn)系統(tǒng)的并發(fā)性而設(shè)置的；管程是為了解決進(jìn)程進(jìn)程的公共變量，解決共享資源的互斥使用問題而設(shè)置的。
（4）? 進(jìn)程通過調(diào)用管程中的過程對共享變量進(jìn)行操作，此時該過程就如通常的子程序一樣被調(diào)用而處于被動工作方式。因此稱管程為被動成分，于此相對應(yīng)的進(jìn)程則處于主動工作方式而被稱為主動成分。
（5）? 由于進(jìn)程是主動成分，故進(jìn)程之間能被并發(fā)執(zhí)行；而管程是被動成分，管程和調(diào)用它的進(jìn)程不能并發(fā)執(zhí)行。
（6）? 進(jìn)程可由“創(chuàng)建”而誕生、由“撤消”而消亡，即具有生命期；而管程是操作系統(tǒng)中的固有成分，無需進(jìn)程創(chuàng)建，也不能被進(jìn)程撤消只能被進(jìn)程調(diào)用。
8．??? 為什么說pcb是進(jìn)程的唯一標(biāo)識
9．??? 算法
?
10．? 某寺廟，有小、老和尚若干。有一水缸，由小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次只能容一個桶取水。水桶總數(shù)為3個。每次取、入缸水僅為1桶，且不可同時進(jìn)行。試用P、V操作給出有關(guān)取水、入水的算法描述。
水缸互斥信號量：mutex1=1；井互斥信號量：mutex2=1；
同步信號量：empty=10；full=0；
水桶資源總數(shù)信號量：count=3；
?
11．? 有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：
（1）? 每次只能存入一種產(chǎn)品（A或B）
（2）? -N<A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量<M
其中,N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與產(chǎn)品B的入庫過程。
根據(jù)題意A產(chǎn)品數(shù)量不能比B產(chǎn)品數(shù)量少N個以上，A產(chǎn)品數(shù)量不能比B產(chǎn)品數(shù)量多M個以上，初始時sa為M-1，sb為N-1。當(dāng)往庫中存放入一個A產(chǎn)品數(shù)量時，則允許B產(chǎn)品數(shù)量也增加1；當(dāng)往庫中存放入一個B產(chǎn)品數(shù)量時，則允許A產(chǎn)品數(shù)量也增加1；
?
? A 、B入庫過程: (寫法不唯一，也可以分開寫)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Sem mutex=1
Sem sa=M-1;
?Sem sb=N-1;
Main()
{
? While(1)
{
??? 取一個產(chǎn)品；
if(取的是A產(chǎn)品)
?? {
p(sa)? ??
p(mutex)???
將產(chǎn)品入庫；?
v(mutex)???
v(sb);
}
Else
{
?? p(sb)
???p(mutex)
將產(chǎn)品入庫；
v(mutex)
v(sa)?
}
?}
}
12．? 寫者優(yōu)先算法
????? Reader:?????????????????????????????????? writer:
?????? p(m)????????????? ?????????????????????????p(k)
??????? p(w)????????????????????????????????????? if(wc==0) {p(w) }???
??????? p(mutex)??????????????????????????????? ????wc=wc+1
??????? if(rc==0) { p(s)}??????????????? ???????????v(k)
??????? rc=rc+1???????????????? ????????????????????p(s)??????????????????
??????? v(mutex)????????????? ?????????????????????< write>
??????? v(w)???????????????????????????????? ???????v(s)
??????? v(m)??????????????????????????????????????? p(k)
??????? <read>???????????????????????????? ????????wc=wc-1
??????? p(mutex)??????????????????????????? ???????if(wc==0) {v(w)}??????
??????? rc=rc-1?????????????????????????? ???????v(k)???
?????? if(rc==0) {v(s)} 7???????????????????????????
?????? v(mutex)
?
讀者：
?while (true) {
?P(m);
P(w);
P(rmutex);
???? readcount ++;
???? if (readcount==1)?? P (s);
?V(rmutex);
V(w);
V(m);
??? 讀
?P(mutex);
???? readcount --;
???? if (readcount==0) V(s);
? V(mutex);
? };
?
寫者：
?while (true) {
P(wmutex);
???? if (wcount==0)?? P (w);
wcount ++;
??V(wmutex);
? P(s);
??? 寫
? V(s);
P(wmutex);
wcount --;
if (wcount==0)?? V (w);
??V(wmutex);
??????? };
?
?
?管程
Type readers_writers = Monitor;
?? Var rq,wq: condition;
??????? reading_count,write_count:integer;
?? Define start_read,finish_read,
?????????? start_write,finish_write;
???
?
Procedure start_read;
?Begin
?? If write_count>0 Then
??????? wait(rq);
??? reading_count++;
??? signal(rq);
?End;
?
?
?
Procedure finish_read;
? Begin
????? reading_count--;
????? If reading_count=0
????? Then signal(wq)
? End;
?
?
Procedure start_write
?Begin
??? write_count++;
??? If (write_count>1) or
??????? (reading_count>0)
??? Then
???????? wait(wq)
?End;????
?
?
Procedure finish_write;
?
?
?Begin
?????? write_count--;
?????? If write_count>0
?????? Then signal(wq)
?????? Else signal(rq)
?? End;
?
Begin
??? reading_count:=0;
??? write_count:=0;
End;
?
?
Var rw:readers_writers;
讀者：?????????????????????????? 寫者：
rw.start_read;???????????????? rw.start_write;
{reading}????????????????????????? {writing}
rw.finish_read;???????????????? rw.finish_write
處理機(jī)調(diào)度與死鎖習(xí)題?
1．??? 一臺計算機(jī)有8臺磁帶機(jī)。它們由N個進(jìn)程競爭使用，每個進(jìn)程最大需求為3，請問N為多少時，系統(tǒng)沒有死鎖危險，并說明原因。
N=3
?
2．??? 在一個使用多級反饋隊(duì)列的系統(tǒng)中，一個使用CPU較多的進(jìn)程需要執(zhí)行50秒。如果第一個隊(duì)列時間片為5，并且較低一級的時間片是上一級時間片的2倍，那么這個作業(yè)會被中斷多少次，當(dāng)它終止時處于哪級隊(duì)列？
3次，4級
存儲管理習(xí)題
1．??? 具有兩級頁表的頁式存儲管理與段頁式存儲管理有何差別？
具有兩級頁表的頁式存儲管理的地址空間依然是一維的，兩級頁的劃分對于進(jìn)程來說都是透明的。而段頁式存儲管理的地址空間是二維的，用戶能感覺到段的劃分。
2．??? 何謂請調(diào)？何謂預(yù)調(diào)？為何在預(yù)調(diào)系統(tǒng)中必須輔以請調(diào)？
所謂請調(diào)是當(dāng)頁故障發(fā)生時進(jìn)行調(diào)度，即當(dāng)被訪問頁面不在內(nèi)存時由動態(tài)調(diào)頁系統(tǒng)將其調(diào)入內(nèi)存。顯然，采用純請調(diào)策略，被移入內(nèi)存的頁面一定會被用到，即不會發(fā)生無意義的頁面調(diào)度。但是，請調(diào)有一個缺點(diǎn)：從缺頁中斷發(fā)生到所需頁面被調(diào)入內(nèi)存，這期間所對應(yīng)的進(jìn)程必須等待，如此將會影響進(jìn)程的推進(jìn)速度。
預(yù)調(diào)也稱先行調(diào)度，是在頁故障發(fā)生前進(jìn)行調(diào)度，即當(dāng)一個頁面即將被訪問之前就由動態(tài)調(diào)頁系統(tǒng)將其調(diào)入內(nèi)存。易見，預(yù)調(diào)可以節(jié)省進(jìn)程因頁故障而等待的時間。預(yù)調(diào)通常根據(jù)程序的順序行為特性而做出：如某進(jìn)程當(dāng)前正訪問第12頁，則接下來很可能會訪問第13頁、第14頁，此時可將第13頁甚至第14頁預(yù)先調(diào)入內(nèi)存。這樣當(dāng)該進(jìn)程訪問第13頁以至第14頁時它們已經(jīng)在內(nèi)存中，不會發(fā)生缺頁故障，從而提高進(jìn)程的推進(jìn)速度。
預(yù)調(diào)不一定是百分之白準(zhǔn)確的。由于程序中存在轉(zhuǎn)移語句，第13頁用完后可能需要訪問第10頁，而該頁目前可能不在內(nèi)存。也就是說，預(yù)先調(diào)入的頁面可能未被用到，預(yù)先未調(diào)入的頁面可能被用到。當(dāng)訪問到預(yù)先未調(diào)入內(nèi)存的頁面時，仍會發(fā)生缺頁中斷。因而，在采用預(yù)調(diào)的系統(tǒng)中，必須輔以請調(diào)功能。
3．??? 給定某系統(tǒng)的各種資源使用特征如下：
CPU??????????? 低
交換設(shè)備?????? 非常高
其他I/O設(shè)備?? 低
對于以下情況，說明是明顯改進(jìn)、明顯降低了CPU利用率，還是對CPU利用率影響很小。
（11）?? 安裝更快的CPU
（12）?? 安裝更大的交換設(shè)備
（13）?? 安裝更快的交換設(shè)備
（14）?? 安裝更多的內(nèi)存
（15）?? 安裝更快的內(nèi)存
（16）?? 增加多道編程的程度
（17）?? 降低多道編程的程度
（18）?? 安裝更快的I/O設(shè)備
解答：
????? 高的交換設(shè)備利用率和低的內(nèi)存利用率，都會使系統(tǒng)到整個性能由于過多的交換而降低。
（a） 安裝更快的CPU
?? ?更快的CPU可能降低CPU的利用率（盡管降低的很少）
（b） 安裝更大的交換設(shè)備
??? 這沒有影響
（c） 安裝更快的交換設(shè)備
??? 這可能有助于提高CPU利用率。因?yàn)镃PU可能由于等待交換操作完成而經(jīng)?？臻e。
（d） 安裝更多的內(nèi)存
??? 這也可能有幫助，由于減少了需要的交換總量（因此減少了交換設(shè)備的I/O操作頻率）。
（e） 安裝更快的內(nèi)存
??? 沒有影響。
（f） 增加多道編程的程度
??? 由于系統(tǒng)顛簸得更厲害，進(jìn)而會降低性能。
（g） 降低多道編程的程度
??? 這可能是改進(jìn)性能的無代價方式。多道程序的主要目標(biāo)是讓足夠的進(jìn)程進(jìn)入內(nèi)存，使得所有的進(jìn)程都很少阻塞。由于CPU和設(shè)備的利用率很低，這降低進(jìn)程數(shù)目（減少交換），然而還有就緒進(jìn)程準(zhǔn)備在CPU上運(yùn)行。
（h） 安裝更快的I/O設(shè)備
如果設(shè)備利用率本來就很低，安裝更快的I/O設(shè)備，至多能對CPU利用率有很小的改善。
?
4．??? 給定某系統(tǒng)的各種資源使用特征如下：
CPU??????????? 低
交換設(shè)備?????? 低
其他I/O設(shè)備?? 高
對于以下情況，說明是明顯改進(jìn)、明顯降低了CPU利用率，還是對CPU利用率影響很小。
（19）?? 安裝更快的CPU
（20）?? 安裝更大的交換設(shè)備
（21）?? 安裝更快的交換設(shè)備
（22）?? 安裝更多的內(nèi)存
（23）?? 安裝更快的內(nèi)存
（24）?? 增加多道編程的程度
（25）?? 降低多道編程的程度
（26）?? 安裝更快的I/O設(shè)備
解答：
（a） 安裝更快的CPU
??? 輕微降低或沒有影響。
（b） 安裝更大的交換設(shè)備
??? 沒有影響
（c） 安裝更快的交換設(shè)備
??? 沒有影響或影響很小。
（d） 安裝更多的內(nèi)存
??? 影響很小或沒有影響。
（e） 安裝更快的內(nèi)存
??? 影響很小或沒有影響。
（f） 增加多道編程的程度
??? 可能改進(jìn)。
（g） 降低多道編程的程度
??? 在一定程度上降低性能。
（h） 安裝更快的I/O設(shè)備
可能改進(jìn)。
?
5．??? 已知某系統(tǒng)有四個頁框，下面的表格表示各個頁、裝入時間、最后訪問時間、頁面重寫標(biāo)志位、訪問位。(一定要寫明原因，否則扣分)
?
頁號
裝人時間
最后訪問時間
頁面重寫標(biāo)志位
訪問位
0
227
327
1
0
1
345
367
1
1
2
101
331
1
1
3
234
382
0
1
?
（i） FIFO算法將替換哪一頁？
（j） LRU算法將替換哪一頁？
（k） NRU算法將替換哪一頁？
（l） SECOND CHANCE算法將替換哪一頁？
?
FIFO算法將2頁
LRU算法將0頁
NRU算法將替換0頁
SECOND CHANCE算法將替換0頁
文件管理習(xí)題
1．??? 在UNIX System Ⅴ中，如果一個盤塊的大小為1KB，每個盤塊號占4個字節(jié)，那么一個進(jìn)程要訪問偏移量位263168字節(jié)處的數(shù)據(jù)時，需要經(jīng)過幾次間接？（寫出簡單計算過程）
263168/1024=257,263138mod1024=0塊內(nèi)偏移量為0
10<257<266,所以263168的塊號在一次間接內(nèi)
?
2．??? UNIX System Ⅴ系統(tǒng)為使文件的索引表較小，又能允許組織大文件，采用直接索引與多次間接索引（多級索引）方式，假設(shè)每個磁盤塊大小為1024個字節(jié)，并且每個間接塊容納256個塊號，試問
1) 直接索引、一次間接、二次間接、三次間接所能訪問的文件大小分別為多少塊？
2) 假設(shè)某個文件的FCB已在內(nèi)存，但其他信息均在外存，為了訪問該文件中某個位置的內(nèi)容，最少需要幾次訪問磁盤？最多需要幾次訪問磁盤？
3) 某進(jìn)程要訪問字節(jié)偏移量為9000、18000和350000處的數(shù)據(jù)，應(yīng)該如何找到它所在磁盤塊及其塊內(nèi)位移量？
4) 畫出簡單的示意圖。
直接索引：10
?? ??????一次間接：10+256
? ???????二次間接： 10+256+256*256
? ???????三次間接： 10+256+256*256+256*256*256
某進(jìn)程要訪問字節(jié)偏移量為9000處的數(shù)據(jù)：
9000/1024=8,9000mod1024=808
直接尋址：從i-addr（8）中找到相應(yīng)的物理塊號，在此塊號內(nèi)找808字節(jié)，為所要訪問的數(shù)據(jù)。
?
某進(jìn)程要訪問字節(jié)偏移量為18000處的數(shù)據(jù)
?? 17???? 592
一次間址：7表目中尋找的磁盤號592單元的數(shù)據(jù)為所要訪問的數(shù)據(jù)。
某進(jìn)程要訪問字節(jié)偏移量為350000處的數(shù)據(jù)
? 341?? 816??? 341-266=75?? [ 75/256]=0
二次間址：二次間址0表目中尋找的磁盤號一次間址的物理塊號，在一次間址75表目處得到的物理塊，其816單元的數(shù)據(jù)為所要訪問的數(shù)據(jù)。
?
3．??? 例子：一個FCB有48個字節(jié)，符號目錄項(xiàng)占 8字節(jié)，文件名6字節(jié)，文件號2字節(jié)，分解前后平均訪盤次數(shù)。
?? 基本目錄項(xiàng)占 48-6=42字節(jié)
?? 假設(shè)，物理塊大小512字節(jié)
解：分解前：占512/48=10個FCB
???????? 分解后：占512/8=64個符號目錄項(xiàng)或512/42=12個基本目錄項(xiàng)
??? 假設(shè)：目錄文件有128個目錄項(xiàng)
??? 分解前：占13塊
??? 分解后：符號文件占2塊
???? 基本文件占11塊
查找一個文件的平均訪盤次數(shù)
? ?????分解前：(1+13)/2=7次??
??? 分解后：(1+2)/2 +1 =2.5次
??? 減少了訪問硬盤的次數(shù)，提高了檢索速度
?
4．??? 某文件系統(tǒng)中，根目錄長駐內(nèi)存。目錄文件采用鏈接結(jié)構(gòu)，普通文件采用三級索引結(jié)構(gòu)。假設(shè)一個物理塊放10個目錄項(xiàng)，一個目錄下最多放40個文件。如果下級文件是目錄文件，則上級目錄項(xiàng)指向該目錄文件的首地址；如果下級文件是普通文件，則上級目錄項(xiàng)指向該文件的文件控制塊。又假設(shè)索引表放在FCB中，如果要讀取K的第一塊或最后一塊，需要啟動硬盤最少幾次，最多幾次？
? （假設(shè)文件按自左向右的順序建立）
?
5．??? 位示圖
計算公式：
已知字號i，位號j
??? 塊號＝i×字長＋j
已知塊號：
??? ???字號＝[ 塊號/字長]
??? 位號＝塊號 mod 字長
6．??? 某系統(tǒng)使用連續(xù)分配.為了在101塊的文件中添加或刪除一個塊應(yīng)進(jìn)行多少次讀和寫的操作?說明原因。（只寫得數(shù)不說明扣分）。假設(shè)：
l? 文件的第一個塊的地址已經(jīng)在內(nèi)存中
l? 要增加的信息塊已經(jīng)在內(nèi)存中
l? 在文件的末尾有空間可供擴(kuò)展，而在文件的開始位置不能擴(kuò)展
l? 中間塊是第51個塊
l? 不計增加一個刪除塊到空閑表所需要的I/O操作
1)? 在開頭增加一個塊
2)? 在中間塊后增加一個塊
3)? 在末尾增加一個塊
4)? 刪除開頭的塊
5)? 刪除中間塊
6)? 刪除末尾的塊
?
7．??? 在一個使用鏈接分配的系統(tǒng)中，回答和前面一題相同的問題。
?
8．??? 在使用索引分配的系統(tǒng)中，回答和前面一題相同的問題。假設(shè)所有需要的索引塊都在內(nèi)存中。如果一個索引塊的內(nèi)容改變了，不把修改后的信息重寫到磁盤的輸出操作計算在內(nèi)。
?
?
1???????????????????? ?
a)???? 203
b)??? 101
c)???? 1
d)??? 0
e)???? 100
f)????? 0
?
2???????????????????? 2
a)???? 1
b)??? 53
c)???? 103
d)??? 1
e)???? 52
f)????? 101
?
3???????????????????? 3
a)???? 1
b)??? 1
c)???? 1
d)??? 0
e)???? 0
f)????? 0
9．??? 一個文件系統(tǒng)使用大小為256字節(jié)的物理塊。每個文件都有一個目錄項(xiàng)給出了文件名、第一個塊的位置、文件的長度和最后一塊的位置。假設(shè)目錄項(xiàng)和最后讀取的物理塊已經(jīng)在主存。在下面的三種情況下，在使用連續(xù)分配的系統(tǒng)中、鏈接分配的系統(tǒng)中、索引分配的系統(tǒng)中，假設(shè)索引分配系統(tǒng)中目錄項(xiàng)中包括第一個索引塊（不是文件中的第一個塊）的位置，每一個索引塊包含指向127個文件塊的指針和一個指向下一個索引塊的指針，除了最后讀的塊外，假設(shè)含有指向最后讀的塊的指針的索引塊也在主存中，但是內(nèi)存中沒有其他的索引塊。為了訪問指定的塊，需要讀多少個物理塊？（包括指定的塊）。
1)? 最后讀的塊號：100，將要讀的塊號：600。
2)? 最后讀的塊號：20，將要讀的塊號：21。
3)? 最后讀的塊號：500，將要讀的塊號：200。
?
連續(xù)分配的系統(tǒng)中：1；1;1
鏈接分配的系統(tǒng)中：500；1;200
索引分配的系統(tǒng)中：5；1;3
設(shè)備管理習(xí)題
1．??? 存放在磁盤上的文件以鏈接結(jié)構(gòu)組織，假定磁盤的分塊大小為每塊512字節(jié)，而文件的邏輯記錄的大小為每個記錄250字節(jié)?，F(xiàn)有一個文件共有10個邏輯記錄，請回答：（10分）
1)? 采用成組操作時，幾個邏輯記錄為一組較合適？
每個盤塊存放兩個邏輯記錄。需要5個盤塊。
2)? 畫出成組時的鏈接結(jié)構(gòu)示意圖
?
?
2．??? 假定有一若有一個磁盤共有100個柱面，每個柱面上有8個磁道，每個盤面被劃分成4個扇區(qū)?，F(xiàn)有一個含3200邏輯記錄的文件，邏輯記錄的大小與扇區(qū)的大小一致，該文件以順序結(jié)構(gòu)的形式被存放到磁盤上。柱面、磁道、扇區(qū)以及邏輯記錄的編號均從“0”開始。文件信息從0柱面、0磁道、0扇區(qū)開始存放，請問
1)? 如何確定該文件的第3000個邏輯記錄存放在磁盤上的位置，其柱面號、磁頭號、和扇區(qū)號？
扇區(qū)數(shù)=8*4=32，柱面號3000/32=93,
磁頭號3000mod32=24,24/4=6,
扇區(qū)號24mod4=0
2)? 第32柱面的第1磁道的第0扇區(qū)存放了該文件的第幾個記錄？
每個盤面4個扇區(qū)，每個柱面8個磁道，第32柱面、第1磁道、第0扇區(qū)，
?
0+4*（1+32*8）=1028
解答：1）93? 6? 0??
?2）1028
?
3．??? 文件分配表FAT是管理磁盤空間的一種數(shù)據(jù)結(jié)構(gòu)，用在以鏈接方式存儲文件的系統(tǒng)中記錄磁盤分配和跟蹤空白磁盤塊。FAT整個磁盤僅設(shè)一張。如果文件首塊號為2，查找FAT序號為2的內(nèi)容得知接著物理塊2的后繼物理塊是5；再查FAT序號為5的內(nèi)容得知接著物理塊5的后繼物理塊是7；接著繼續(xù)查FAT序號為7 的內(nèi)容為“^”，即改文件結(jié)束標(biāo)志，所以該文件順序由物理塊2、5、7組成。假設(shè)磁盤物理塊大小為1KB。
1)? 對540MB的硬盤其文件分配表FAT需要占用多少存儲空間？
540M/1K=540K，540K<1024K=2的20次方，20位需要2.5個字節(jié)（3個字節(jié)是24位），2.5*540K=1350K
2)? 當(dāng)硬盤容量為1.2G時，文件分配表又需占用多少存儲空間？
1.2G/1k=1.2M,1.2M<2M=2的21次方，需要3字節(jié)，3*1.2M=3.6M
?
1350k?? 4.8M。
?
4．??? 假定有一個具有200個磁道（編號為0～199）的移動頭磁盤，在完成了磁道125處的請求后，當(dāng)前正在磁道143處為一個請求服務(wù)。若請求隊(duì)列以FIFO次序存放，即86，147，91，177，94，150，102，175，130。對下列每一個磁盤調(diào)度算法，若要滿足這些要求，則總的磁頭移動次數(shù)為多少？
1)? FCFS
2)? SSTF
3)? SCAN
4)? CSCAN
5．??? 在單緩沖的情況下，假設(shè)T是從磁盤輸入一塊數(shù)據(jù)的時間，C是CPU對一塊數(shù)據(jù)進(jìn)行處理的時間，而M是將一塊數(shù)據(jù)從緩沖區(qū)傳送到用戶區(qū)的時間。當(dāng)一用戶進(jìn)程要按順序訪問的方式處理大量數(shù)據(jù)時，請問系統(tǒng)對一塊數(shù)據(jù)的處理時間是多少？畫圖說明。
???????? ?MAX（C，T）+M
?
6．??? 在雙緩沖的情況下，假設(shè)T是從磁盤輸入一塊數(shù)據(jù)的時間，C是CPU對一塊數(shù)據(jù)進(jìn)行處理的時間，而M是將一塊數(shù)據(jù)從緩沖區(qū)傳送到用戶區(qū)的時間。當(dāng)一用戶進(jìn)程要按順序訪問的方式處理大量數(shù)據(jù)時，請問系統(tǒng)對一塊數(shù)據(jù)的處理時間是多少？畫圖說明。
??????????? ??MAX（C，T）
?
7．??? I/O軟件一般分為哪四個層次？每層完成哪些功能？畫圖說明。
層次
用戶進(jìn)程
進(jìn)行I/O調(diào)用；格式化I/O；SPOOLing
設(shè)備無關(guān)軟件
命名；保護(hù)；阻塞；緩沖；分配
設(shè)備驅(qū)動程序
建立設(shè)備寄存器；檢查狀態(tài)
中斷處理程序
當(dāng)I/O結(jié)束時喚醒驅(qū)動程序
硬件
?
?
8．??? 說明向設(shè)備寄存器寫命令、檢查用戶是否有權(quán)使用設(shè)備、將二進(jìn)制轉(zhuǎn)換成ASCII碼以便打印分別是在I/O軟件的哪一層完成的？
?
向設(shè)備寄存器寫命令：設(shè)備驅(qū)動層
檢查用戶是否有權(quán)使用設(shè)備：設(shè)備無關(guān)軟件層
將二進(jìn)制代碼轉(zhuǎn)換成ASCII碼以便打?。河脩魧?/strong>
?
