作業系統期末複習

記憶體管理

固定分割槽

分割槽大小數量在系統的生成階段就已經確定，儘管大小不同的分割槽具有一定的靈活請，但還是比較低效。

動態分割槽

放置演算法

為程序確定該分配至哪個空閒區，有以下幾種策略，顧名思義即可：

最佳適配 BF

首次適配 FF

下次適配 NF

最差適配 WF

例1

假設使用動態分割槽，下圖是經過數次放置和換出操作後的記憶體格局。記憶體地址從左到右增長；灰色區域是分配給程序的記憶體塊；白色區域是可用記憶體塊。最後一個放置的程序大小為2MB，用X標記。此後僅換出了一個程序。

a。換出程序的最大尺寸是多少？

解：8M。因為當前空閒區最大的區域就是8M，為換出程序後空下來的。

b。建立分割槽並分配給X之前，空閒塊的大小是多少？

解：答案並不唯一。至少是3M，最大是8M，因此大小為［3M，8M］。

c。下一個記憶體需求大小為3MB。在使用最佳適配/首次適配/下次適配/最差適配的情況下，分別在圖上標記出分配的記憶體區域。

四种放置演算法

夥伴系統

例2

一個1MB的記憶體塊使用夥伴系統來分配記憶體。

a。 請畫圖來表示序列的結果請求，70KB；請求35KB；請求80KB；釋放A；請求60；釋放B；釋放D；釋放C。

夥伴系統

b。畫出釋放B後的二叉樹表示。

二叉樹表示

分頁

邏輯地址

是指與當前資料在記憶體中的物理分配地址無關的地址，在使用它對記憶體訪問之前要將它轉換為物理地址。

物理地址

資料在記憶體中的實際位置。

頁表

頁表由作業系統所維護，給出了程序中每頁所對應的頁框的位置。注意頁框是與物理地址有實際關係的，頁框號代表實際物理地址的高位，而透過頁號和程序頁表可以找到頁框號，因此頁號+偏移量就是邏輯地址，可以轉化為物理地址。

例3

系統使用簡單分頁，記憶體大小為

位元組，頁大小為

位元組，邏輯地址空間包含

頁。

a。邏輯地址有多少位？

解：邏輯地址包含頁號和偏移量，頁號為16位，偏移量位10位，因此邏輯地址有26位。

b。一個頁框有多少位元組？

解：頁大小就是頁框大小，它們是一一對應的關係，一個頁框有

位元組。

c。物理地址中的多少位是頁框號？

解：32-10=22，有22位頁框號。

d。頁表中有多少表項？

解：邏輯地址空間包含

頁，所以有

項。

e。假設每個頁表項中含一位有效位，則每個頁表項有多少位？

解：22+1=23位。

分段

偏移量大於段長度，則改地址無效。

例4

在一個簡單分段系統中，包含如下段表：

起始地址

長度（位元組）

660

248

1752

442

222

198

996

604

對如下每一個邏輯地址，確定其對應的物理地址或說明段錯誤是否會發生：

a。 0， 198； 物理地址：660+198 不會

b。 2， 156； 物理地址：222+156 不會

c。 1， 530； 物理地址：1752+530 會

d。 3，444； 物理地址：996+444 不會

e。 0，222； 物理地址：660+222 不會

檔案系統

檔案的組織方式

FCB

檔案控制塊，系統為每個檔案設定描述和控制檔案的資料結構，包括檔名和存放檔案的盤物理地址。FCB的有序集合稱為檔案目錄。一個檔案控制塊就是一個檔案目錄項。注意與FAT的區別

索引節點

檢索目錄的時候並不需要所有的檔案控制塊中的資訊，而只需要檔名，檢視是不是與指定的檔名相匹配，其它的資訊都不需要，因此不需要調入記憶體。將檔案描述資訊單獨稱為一個索引界定啊，這樣一個目錄項佔用的磁碟大小就少了，一個盤塊中就能放更多的目錄項，啟動磁碟的次數就減少了。

目錄結構

應該不考，略。

檔案的分配方式

FAT

File Allocation Table，檔案分配表，一般存放檔案的起始地址和總塊數，用於跟蹤檔案的分配情況。使用連結分配時，可根據FAT可以找到檔案的起始塊順著連結指標依次往下找。看題目中給的是FAT還是FCB，就做題而言，可以說沒有區別。

連續分配

需要預分配，必須為一個檔案分配連續的磁碟空間。存在外部碎片。

連結分配

連結（鏈式）分配，每一個盤塊上的連結指標，將同屬於一個檔案的盤塊連結成一個連結串列，稱為連結檔案。不存在外部碎片。連結指標佔用一定的記憶體空間，因此在計算時需要小心。

不能有效支援檔案的直接訪問，要順著連結指標找。

索引分配

索引分配保持了連結結構的優點，同時又能順序存取，又能隨機存取，同時充分利用了外存空間，但是帶來了存取時間的開銷。

直接定址，適用於小檔案，盤塊地址可以直接放在FCB中。

一次間址，中等檔案，FCB中存放索引表。

二次間址，大檔案。

三次間址，大檔案。

混合索引分配

LINUX混合分配為例（15個64位地址，前12個地址用於直接定址，第13個用於一級間址，第14個用於二級間址，第15個用於三級間址），假設最小的塊大小為4KB，該格式下檔案的最大尺寸為：

連結索引

有了連結分配和索引分配的概念，連結索引才會比較好理解。連結索引是將索引塊連結起來了，我們知道在索引分配中的索引塊一個表項代表檔案的一個地址塊，因此可見將如此多的索引塊連結起來，理論上最大檔案會很大。

例1.

一個檔案系統中有20MB大檔案和一個20KB的小檔案，當分別採用連續、連結、連結索引、二級索引和LINUX分配方案時，每塊大小為4096B，每塊地址用4B表示，問：

1.各檔案系統管理的最大檔案是多少？

a。連續分配：理論上不受限制，可大到整個磁碟檔案區；

b。連結分配：每個盤塊的大小為4096B，其中連結指標佔用4B，最大尺寸為

c。連結索引：先算最多連結的索引塊，每個索引塊能放多少地址，得：

d。二級索引：

e。LINUX混合分配上文已給出

注意：涉及到連結，需要把連結指標的大小考慮在內

2.每種方案對大小兩檔案各需要多少專用塊來記錄檔案的物理地址，並說明各塊的用途；

a。連續分配：FCB中設定起始物理塊，檔案塊總數

b。連結分配：同連續分配，且每個檔案塊設定連結指標

c。連結索引：20KB檔案需要一個索引塊，20MB檔案需要6個索引塊（20MB/（4K（1K-1）），FCB也要

d。二級索引：20KB要1+1塊，20MB要1+5塊

e。LINUX混合：前12個地址直接存放FCB，不需要專用塊，一級索引要1塊，二級索引要1+4塊。

3.若需要讀大檔案前面5.5KB的資訊和後面16M+5.5KB的資訊，則每個方案各需要訪問盤塊多少次？（FCB已在記憶體）

a。連續分配：計算邏輯塊號，1+1次 b。連結分配：要按順序讀，後面的肯定讀很多2（前面）+n（後面）

c。連結索引：算一下每個索引塊能放多少地址，1+5次

d。二級索引：固定的3次，沒得說1+1+1，第一級1次，第二級1次，最終1次

e：LINUX混合：順序+二級，2+3

例2.

從訪問速度、儲存空間的使用和易於更新（新增/刪除/修改）這幾方面考慮，為了達到最大效率，你將選擇哪種檔案組織？

1.很少修改並且以隨機方式頻繁地訪問時；

順序分配

2.頻繁地修改並且相對頻繁地訪問檔案整體時；

索引分配（連結分配狗都不用）

3. 頻繁地修改並以隨機順序頻繁的訪問時。

索引分配

例3.

塊大小為１KB，每一塊可以存放256個地址。使用索引節點方案，一個檔案的最大尺寸是多少？

例4.

考慮由一個索引節點所表示的UNIX檔案的組織，假設有12個直接塊指標，在每個索引節點中有一個一級、二級和三級間接指標。此外，假設系統塊大小和磁碟扇區大小都是8KB。如果磁碟塊指標是32位，其中8位用於標識物理磁碟，24位用於標識物理塊，那麼

1.該系統支援的最大檔案大小是多少？

2.該系統支援的最大檔案系統分割槽是多少？

3.假設記憶體中除了檔案索引節點外沒有其他資訊，訪問在位置13423956中的位元組需要多少次磁碟訪問？

在一級索引處，所以要2次

例5.

存放在某個磁碟上的檔案系統，採用混合索引分配方式，其FCB中共有13個地址項，第0~9個地址項為直接地址，第10個地址項為一次間接地址，第11個地址項為二次間接地址，第12個地址項三次間接地址。如果每個盤塊的大小512位元組，若盤塊號需要用3個位元組來描述，而每個盤塊最多存放170個盤塊地址。

1.該檔案系統允許檔案的最大長度是多少？

2. 將檔案的位元組偏移量5000，15000，150000轉換為物理塊號和塊內偏移量。

物理塊號（15位）

塊內偏移（9位）

a。5000：物理塊號1001 塊內偏移110001000

b。15000：物理塊號11101 塊內偏移010011000

c。150000：物理地址100100100 塊內偏移111110000

轉為二進位制，後9位就是塊內偏移。

3. 假設某個檔案FCB已在記憶體，但其他資訊均在外存，為了訪問該檔案中某個位置的內容，最少需要幾次訪問磁碟，最多需要幾次訪問磁碟？

最少1次（直接），最多4次（三次間址）

期末考試大題基本混合索引沒得跑了，如有問題，歡迎評論區指出，一起進步！

分頁儲存管理

基本概念

不要求將作業同時全部裝入記憶體的連續區域，而是將記憶體空間分為一個個大小相等的分割槽，每個分割槽就是一個頁框，每個頁框有一個編號，即頁框號，頁框號從0開始。將使用者程序的地址空間也分成與頁框大小相等的一個個區域，稱為頁或頁面，每個頁面也有一個編號，頁號也是從0開始的。程序的頁面與記憶體的頁框存在一一對應的關係。分頁會產生內部碎片。

頁框：記憶體被劃分為大小固定的塊，稱為頁框

頁表項：每個頁表項的長度是相同的，頁號是隱含的，程序頁表通常是裝在連續的記憶體空間中的

TLB快表：一種訪問速度比記憶體快很多的高速儲存器，用來存放當前訪問的若干項表項。引入快表後，先訪問快表，再訪問記憶體，只需要訪問一次記憶體；沒有找到再訪問記憶體中的頁表，同時存入快表（按一定的頁面置換策略），需要訪問兩次記憶體。

地址轉換

已知邏輯地址，求物理地址。

算出邏輯地址對應的頁號

知道該頁號再記憶體中的起始地址

計算邏輯地址再頁面內的偏移量

物理地址=頁面始址+頁內偏移量

注意：已知頁面大小等價於已知頁面偏移量佔幾位，按位元組定址等價於一個地址對應一個位元組的空間

兩級頁表

解決單級頁表必須連續存放佔據連續記憶體空間的問題。當頁表項需要佔用很多很多頁面的時候，先查頁面在查頁面內的頁表項，這就是兩級頁表。

假設頁面大小為4KB，32位地址，每個頁表項大小為4B。

一個程序最多有多少個頁面？——————————————————————————————-

每個頁面都要有一個頁表項，最多有多少頁表項？————————————————————

每個頁表項的大小是多少？————————————————————————————————-

每個頁面存放多少頁表項？————————————————————————————————-

一共需要多少個頁面來存放這些頁表項？————————————————————————-

多少個頁面對應一級頁號，頁面記憶體放對應二級頁號，頁面大小就是頁內偏移量。因此設計如下：

31————————————————-22

21————————————————-12

11————————————————-0

一級頁號

二級頁號

頁內偏移量

例1.

請求分頁管理系統中，假設某程序的頁表內容如下表所示。

頁號

頁框號

有效位

0

101H

1

1

-

0

2

254H

1

頁面大小為4KB，一次記憶體訪問的時間是100ns，一次快表TLB的訪問時間為10ns，處理一次缺頁中斷的時間是

ns（包含更新TLB和頁表的時間），程序的駐留集大小固定為2，採用最近最少使用的置換演算法和區域性淘汰策略。假設：1。TLB初始為空；2。地址轉換時先訪問TLB，若TLB未命中，再訪問頁表；3。有效位為0代表頁面不在記憶體，產生缺頁中斷，缺頁中斷處理後，返回到產生缺頁中斷的指令處重新執行。設有虛地址訪問序列為：2362H、1565H、25A5H，請問：

1.一次訪問上述三個虛擬地址，各需要多少時間，給出計算過程；

a。2362H：10ns+100ns+100ns b。1565H：缺頁中斷10ns+100ns+10^8ns+100ns c。25A5H：10+100ns

2.基於以上訪問序列，虛地址為1565H的物理地址是多少，請說明理由。

發生缺頁中斷進行了替換，物理地址是101565H

分段式儲存管理

基本概念

將地址空間按照程式自身的邏輯關係或分為若干個端，每段從0開始編址；每個段佔據連續的地址空間，各段之間可以不相鄰。分段可以解決內部碎片的問題，但會造成外部碎片。

地址轉換

已知邏輯地址，求物理地址。

算出邏輯地址對應的段號，段內地址

檢查段號是否發生越界

根據段號和段表始址找到段表項

檢查段內地址是否越界

物理地址=基址+段內地址

段頁式儲存管理

每個段對應一個段表項，每個段表項由段號，頁表長度，頁表存放塊號組成，每個段表項的長度相等，因此段號可以隱藏。同樣頁號也可以隱藏。

段號

頁號

頁內偏移量

地址轉換

已知邏輯地址，求物理地址。

算出段號，頁號，頁內偏移地址

查詢段表，找到對應的段表項，檢查頁號是否越界

段表項得到頁表存放塊號

根據頁號找到頁表項

找到記憶體塊號，和頁內偏移地址結合

注意：三次訪問記憶體（訪問段表找到頁表，再訪問頁表，第三次訪問實際的物理地址）