操作系統精選題（四）（論述題）

🌈?個人主頁：十二月的貓-CSDN博客
🔥?系列專欄：?🏀操作系統

💪🏻?十二月的寒冬阻擋不了春天的腳步，十二點的黑夜遮蔽不住黎明的曙光?

前言

一、銀行家算法的一道例題

二、頁大小為 1024 字節，計算邏輯地址 2560 和 4220 對應的物理地址

三、頁計算問題

四、進程同步問題

六、單級頁表；TLB 命中率為 90%，訪問 TLB 需 5ns，訪問主存為 25ns，求有效內存的訪問時間

七、請求分頁系統中，頁表項中包含哪些數據項？它們的作用？

八、畫出分頁內存管理方案的過程圖，描述流程、過程中硬件或軟件所起的作用。

九、分頁式文件系統的主要數據結構，要使用這個分頁結構需要哪些硬件支持

十、當前頁表如下。頁大小為1024字節，該程序分配2個幀，頁號0先裝入內存。采用先進先出和局部置換策略，現在訪問邏輯地址為3000的字節，問在這個過程中發生了什么主要事件并寫出置換后的頁表。

十一、比對FIFO算法和LRU算法

十二、增強的二次機會算法的基本思想；為什么會發生抖動，怎么解決？

十三、三種磁盤空間分配方法（contiguous、linked、indexed）的優缺點

十四、基于磁盤的分配方法，設計一種高效的磁盤空閑空間分配和回收方法，說出基本思想，操作過程和數據結構。

十五、某磁盤文件區16GB，每個磁盤塊為1KB，

（1）若空閑存儲空間采用位圖管理方法那么位圖需占用多少個盤塊

（2）若采用FAT，FAT中每個盤塊地址用4字節表示，問FAT表需要幾個盤塊

十六、某文件系統為一級目錄，文件的數據一次性寫入磁盤，已經寫入的文件不可修改，但可以多次創建新文件，請回答：

十七、假如盤塊的大小為4KB，每個盤塊號占4個字節，在兩級索引分配時，允許的最大文件是多少？（請寫出計算過程）

十八、簡要描述操作系統中打開文件的工作過程（等價于如何通過文件名找到文件）

十九、三種磁盤空間分配方法（連續、鏈接、索引）FCB中的描述字段

二十、非阻塞和阻塞I/O是什么，主要有什么不同，分別用在哪里？

總結

前言

本系列題目均選自山東大學往年考題，供大家復習參考。一定要在復習完基礎知識后（最好把書本都看一遍，這樣子知識體系才是完善的），再來參考這個練習題。

兩個不可取：一、不可不復習知識點，光做題；二、不可只復習知識點，不復習

貓貓祝大家都能取得好成績呀~~~

一、銀行家算法的一道例題

?題目解答：

二、頁大小為 1024 字節，計算邏輯地址 2560 和 4220 對應的物理地址

?2560的物理地址：

2560/1024=2.幾，因此在第三頁即頁號為2的頁，同時頁內偏移為：2560-2048=512
對應塊號為60。分頁算法中內存中的每一塊對應就是一頁。所以物理地址為：60*1024+512=61952

?4220的物理地址：

4220=1024*4+124
因為在第五頁，而進程頁表中只有四頁，所以這是越界訪問，邏輯地址4220是非法的

三、頁計算問題

2560=1024*2+512

4098=1024*4+2

18*1024+512=18944

頁號4越界，邏輯地址4098非法

四、進程同步問題

//確定進程類別：只有一種類別的進程，這種進程有三個
//確定主營業務：過橋、在白板上更新物資200個（不用dowhile循環）
//找同步約束:互斥、資源、限額（這里是資源里的進程執行順序限制）
int wuzi_num=0;//白板，臨界區
semaphore mutex=1;//臨界區互斥變量
semaphore liang=0;//讓小亮啟動的同步信號量
semaphore ming=0;//讓小明啟動的同步信號量
xiaohua{/*過橋*/signal(liang);wait(mutex);wuzi_num+=200;signal(mutex);
}
xiaoming{wait(ming)/*過橋*/wait(mutex)wuzi_num+=200;signal(mutex);
}
xiaoliang{wait(liang);/*過橋*/signal(ming)wait(mutex)wuzi_num+=200;signal(mutex);
}

六、單級頁表；TLB 命中率為 90%，訪問 TLB 需 5ns，訪問主存為 25ns，求有效內存的訪問時間

一、頁表存放在內存中，所以如果通過頁表訪問內存，需要訪問主存兩次

二、如果通過TLB訪問內存，則通過TLB能找到數據在主存中的位置，所以訪問主存一次

0.9*（5+25）+0.1*（5+25+25）=32.5ns

七、在某個分頁管理系統中，某一個作業有 4 個頁面，被分別裝入到主存的第 3、4、6、8 塊中，假定頁面和塊大小均為 1024 字節，當作業在 CPU 上運行時，執行到其地址空間第 500 號處遇到一條傳送命令： MOV 2100,3100 畫地址轉換圖計算出 MOV 指令中兩個操作數的物理地址

1、作業=進程

2、內存中的塊和頁都是從0開始算的

2100=1024*2+52

3100=1024*3+28

2100對應第三頁，頁內偏移為52；3100對應第四頁，頁內偏移為28

2100物理地址為：6*1024+52=6196

3100物理地址為：8*1024+28=8220

七、請求分頁系統中，頁表項中包含哪些數據項？它們的作用？

頁表項中包含：頁號（隱含）、幀號、保護位、修改位、訪問位

保護位：也叫有效/無效位，記錄該頁是否是有效的。無效位包括缺頁和其他情況。

訪問位：用來判斷該頁在一段時間內被訪問的次數，或者多長時間未訪問（不同頁面置換算法不同），通過這一位頁面置換算法可以確定置換哪一頁

修改位：判斷該頁是否被修改過。通過修改頁能夠在該頁被置換出來后判斷要不要寫入磁盤

幀號：記錄對應頁號在物理內存中的那一塊

八、畫出分頁內存管理方案的過程圖，描述流程、過程中硬件或軟件所起的作用。

分頁內存管理方案=分頁內存創建與維護方案+分頁內存使用方案

分頁內存創建與維護方案流程：

頁面創建：創建進程時，操作系統為該進程創建一個頁表，這個頁表大小取決于該進程有多少頁，而多少頁又取決于進程地址空間大小以及頁面大小。同時操作系統要對頁表進行初始化
頁面維護：在虛擬內存中，如果發生缺頁就會陷入內核。操作系統就要更新頁表，同時更新頁表時可能也涉及到頁面置換等操作

分頁內存使用方案流程：

應用程序提供邏輯地址
MMU接受應用程序提供的地址，計算得到頁號，頁內偏移等
MMU查找頁表，獲取頁表項
MMU根據頁表項中的幀號和頁內偏移計算得到邏輯地址對應的物理地址

硬件作用：里面發揮作用的硬件就是MMU。MMU起到查詢頁表項、根據邏輯地址計算物理地址等作用

軟件作用：里面發揮作用的軟件就是操作系統。操作系統在里面發揮創建維護頁表、更新頁表等作用

九、分頁式文件系統的主要數據結構，要使用這個分頁結構需要哪些硬件支持

分頁式文件系統和分頁式內存管理系統是類似的

其所用的數據結構、硬件支持也是一樣的

分頁式系統的主要數據結構——頁表

要使用這個分頁結構（頁表）需要的硬件支持：

內存管理單元(MMU)
TLB
頁表寄存器（PTR）

十、當前頁表如下。頁大小為1024字節，該程序分配2個幀，頁號0先裝入內存。采用先進先出和局部置換策略，現在訪問邏輯地址為3000的字節，問在這個過程中發生了什么主要事件并寫出置換后的頁表。

?局部置換策略：每個進程在物理內存中有自己的幀集合，不能訪問其他進程的幀集合

十一、比對FIFO算法和LRU算法

FIFO優先淘汰最先進入內存的頁面，但是可能置換出去的是很久之前初始化并且一直在用的變量。性能很差，存在Belady異常。上述結果可以看出，對FIFO而言，增加分配給作業的內存塊數反而出現缺頁次數增加的異常現象。給進程分配4個幀產生的頁面錯誤率比分配 3個幀還多。

LRU優先淘汰最近最久沒訪問的頁面。和最優置換（OPT）一樣，都沒有Belady異常（它們屬于同一種算法，叫做棧算法）。效率較高，是一種經常被使用的頁置換算法。

十二、增強的二次機會算法的基本思想；為什么會發生抖動，怎么解決？

增強的二次機會算法的基本思想：

若用（訪問位，修改位）的形式表述，則

第一輪：淘汰（0,0）

第二輪：淘汰（0,1），并將掃描過的頁面訪問位都置為0

第三輪：淘汰（0,0）

第四輪：淘汰（0,1）

將引用位和修改位作為一組有序對來改進第二次機會算法。

(0,0)代表近期既沒有被使用過，也沒有被修改過，是最佳的頁面置換。
(0,1)代表近期沒有被使用過但是被修改過的頁面，是不太好的頁面置換，因為需要將該頁面寫回磁盤。
(1,0)代表近期被使用過但是沒有被修改的頁面，可能很快會被再次使用。
(1,1)代表近期既被使用過又被修改過，可能很快會再次使用，并且置換時需要寫回磁盤。

每個頁面必然都屬于上述這四種類型的集合。當需要頁面置換時，可以采用與Clock算法一樣的策略：檢查頁面的類型(不是僅僅檢查引用位)，我們替換掉最低類型中的一個頁面(如果這一類型的頁面有的話)。因為可能并不存在(0,0)類型的頁面，這時就選擇(0,1)類型的頁面，依此類推。增強型第二次機會算法的亮點在于它賦予了那些被修改過的頁面更高的優先級，從而降低了所需要I/O的數量。

抖動主要原因：進程頻繁訪問的頁面數目高于分配給進程可用的物理塊數

防止抖動的方法：采用可變分配方法分配進程物理塊數。

計算進程的工作集
將工作集中的幀數做一個求和得到一個總的工作集大小
駐留集（給進程分配的物理塊數）不小于上面求得總的工作集大小?

?如果出現抖動得解決方法：

減少并發進程數目
增加物理內存塊數
優化頁面置換策略

十三、三種磁盤空間分配方法（contiguous、linked、indexed）的優缺點

連續分配：對每個文件都從磁盤中連續地分配磁盤塊給需要的文件。

實現簡單、存取速度塊、效率高
難以進行文件拓展，會產生外碎片

鏈接分配：分配給文件磁盤塊時，這些塊可以不連續，彼此間用指針相聯系

不存在外碎片；實現簡單；文件可以拓展，增加文件內存
指針本身占用空間；無法實現隨機讀取；可靠性差，一旦其中一個指針出錯整個內存分配都會出問題（文件分配表FAT改進）

索引分配：從空閑塊中拿出一塊用作索引塊，在索引塊中放置其他空閑塊的指針，用以查找到其他空閑塊的物理位置

不存在外碎片；文件可拓展；
索引塊本身就是一個空間消耗（即使只有一兩個指針也要耗費一個索引塊內存）?

十四、基于磁盤的分配方法，設計一種高效的磁盤空閑空間分配和回收方法，說出基本思想，操作過程和數據結構。

空閑空間分配以及回收方法——空閑空間管理

空閑空間管理方法有空閑表法、鏈表法、組法、位圖法

①空閑表法 ②空閑鏈表法：[空閑盤塊鏈]將所有空閑磁盤塊用鏈表鏈接起來，并將指向第一個空閑塊的頭指針保存在磁盤的超級塊上，同時也緩存在內存中。[空閑盤區鏈/計數counting]類似于內存動態分區。 ③位示圖法：將空閑空間表現為位圖，每塊空閑空間用一位表示，如果空閑則為1，已分配則為 0。 ④成組鏈接法：把順序的n個空閑扇區地址保存在第一個空閑扇區內，其最后一個空閑扇區內則保存另一組順序空閑扇區的地址，如此繼續，直至所有空閑扇區均予以鏈接。系統只需要保存一個指向第一個空閑扇區的指針。

十五、某磁盤文件區16GB，每個磁盤塊為1KB，

（1）若空閑存儲空間采用位圖管理方法那么位圖需占用多少個盤塊

（2）若采用FAT，FAT中每個盤塊地址用4字節表示，問FAT表需要幾個盤塊

1、

16GB=2^34B

2^34B/2^10B=2^24塊

在位圖管理中，每塊用一位（1bit）來表示，所以需要2^24b來表示

2^24b=2^21B來表示位圖

2^21B/2^10B=2^11塊（磁盤來存儲位圖）

2、

16GB=2^34B

2^34B/2^10B=2^24塊

表示磁盤文件區有2^24塊磁盤塊

FAT方法是鏈表法的改進，文件分配表（FAT）中將有2^24條項（每一個塊一個項）

由于每個盤塊地址用4b表示，所以有2^24*4B=2^26B來表示

2^26B/2^10B=2^16塊

十六、某文件系統為一級目錄，文件的數據一次性寫入磁盤，已經寫入的文件不可修改，但可以多次創建新文件，請回答：

(1) 采用哪種文件物理結構形式更適合？說明理由，為定位文件數據塊，需要FCB中設置哪些相關的描述字段？（10分）

(2) 為快速找到文件，對于FCB是集中存儲好，還是與對應文件數據塊連續存儲好？為什么？（10分）

(1)連續更合適。因為一次寫入不存在插入問題，而且寫入文件之后不需要修改，連續的數據塊組織方式很適合一次性寫入磁盤不再修改的情況，同時連續存儲相對鏈式和索引省去了指針的空間開銷，支持隨機查找，查找速度最快。FCB中包括:存放文件的設備名、文件在外存的起始盤塊號、文件長度。

(2)FCB集中存儲較好。FCB存儲有文件的很多重要信息，同時是文件目錄的重要組成部分，在檢索時，通常會訪問對應文件的FCB。如果將FCB集中存儲，則可以減少在檢索過程中產生的訪盤次數，提高檢索速度。

十七、假如盤塊的大小為4KB，每個盤塊號占4個字節，在兩級索引分配時，允許的最大文件是多少？（請寫出計算過程）

假如盤塊的大小為4KB，每個盤塊號占4個字節，則一個索引塊可含 4KB/4B=1K個盤塊號，

于是兩級索引最多可含1K×1K = 1M個盤塊號，因此，允許的最大文件長度為4KB×1M = 4GB。

十八、簡要描述操作系統中打開文件的工作過程（等價于如何通過文件名找到文件）

?用戶給 open()傳入一個文件的邏輯路徑名，這時先將該文件系統的目錄結構加載進內存，根據文件名，操作系統會首先對系統范圍內的打開文件表進行搜索（節省時間）。如果該文件已經被其他進程打開了，則直接將該進程的打開文件表中的指針指向系統范圍打開文件表的這一項，同時，系統打開文件表該文件引用計數加1。如果該文件在系統范圍文件表中不存在，說明該文件第一次打開，則對該文件系統的目錄表進行搜索，依次查找到葉結點，葉結點包含了一個該文件控制節點號，即控制節點的物理位置指針，將這個指針返回給用戶，同時在系統范圍打開文件表中新注冊一行這個文件的信息，將該進程的打開文件表中指針指向這條新信息，open()操作的任務就完成了。