存盤管理

首先先上一張思維導圖，接下來的內容根據思維導圖來進行

存盤器管理概述

主存和輔存

存盤器管理主要是對記憶體部分的管理，同時也涉及對記憶體和外存交換資訊的管理

記憶體又可以分成系統區和用戶區 —> 系統區用來存盤作業系統等系統軟體 ， 用戶區用來分配給用戶行程使用

行程管理實際上是對用戶區的管理

存盤器管理的目的

三個目的 ----->為用戶提供方便、安全和充分大的存盤空間

存盤器管理的任務

存盤器管理的認為主要為五個方面分別為地址轉換，記憶體的分配和回收，記憶體的地址保護，記憶體的共享，記憶體的擴充

1. 地址轉換

關于地址轉換首先要清楚邏輯地址和物理地址這兩個概念

• 邏輯地址

邏輯地址指用戶源程式經過編譯和匯編后形成的目標代碼中出現的地址

如規定目標程式的首地址為零，其他指令的地址都是相對于首地址而定的 把這里的地址稱為邏輯地址也叫相對地址

• 物理地址

記憶體中各存盤單元的編號稱為物理地址 也稱絕對地址

地址轉換即在行程運行之前將行程指令中的邏輯地址轉換成記憶體中的物理地址

2. 記憶體的分配和回收

當用戶程式需要裝入記憶體創建行程時，需要向作業系統提出申請，作業系統按一定策略分配記憶體空間，行程執行完畢時作業系統需要及時回收記憶體空間，

作業系統必須隨時掌握記憶體的使用情況，

3. 記憶體的地址保護

避免記憶體中多個行程互相干擾，尤其防止用戶行程侵犯系統行程所在的記憶體區域，對記憶體進行地址保護來保證各個行程都在自己所屬的記憶體空間中或在公共區域中作業，互不干擾，

4. 記憶體的共享

提高記憶體的利用率

1. 共享記憶體資源
2. 共享記憶體的某些區域

5. 記憶體的擴充

虛擬存盤

程式的連接和裝入

一個用戶源程式變為一個可以在記憶體中執行的程式需要經歷：

程式的連接

源程式經過編譯后會得到一個或者多個目標模塊，一些模塊無需連接可以直接裝入記憶體，一些模塊需要通過連接程式將它們和所需要的庫函式連接形成裝入模塊

三種連接方式

1. 靜態連接方式

在程式運行之前，將各個目標模塊及他們需要的庫函式，連接成一個完整的裝入模塊又稱可執行檔案

2. 裝入時動態連接

目標模塊在裝入記憶體時，邊裝入邊連接 —> 在裝入一個目標模塊時，如果發生一個外部模塊呼叫事件，將引起裝入程式去找出相應的外部目標模塊，并將它裝入記憶體，進行連接

3. 運行時動態連接

將對某些模塊的連接推遲到執行時才進行，

程式的裝入

將一個裝入模塊裝入記憶體時，需要進行地址轉換

三種裝入方式

1. 絕對裝入方式

   邏輯地址轉換成物理地址的程序發生在程式編譯或匯編時

2. 可重定位裝入方式

? 地址轉換發生在程式裝入記憶體時

? 可重定位裝入方式不允許程式在記憶體中移動位置

3. 動態運行時裝入方式

? 地址轉換發生在程式真正執行時

? 通常會設計一個重定位暫存器來實作動態重定位

連續分配方式

單一連續分配

記憶體的用戶區一次只分配給一個用戶程式使用

磁區分配

1. 固定磁區

系統預先將記憶體中的用戶區分成若干個連續的區域，每個區域稱為一個磁區，磁區大小可以相同也可以不同

2. 可變磁區

   在程式裝入時根據程式的實際需要動態的劃分記憶體空間

?

磁區分配中的資料結構

1.已分磁區表 2.空閑磁區表

磁區分配演算法

記憶體碎片的概念 ：當我們在進行分配程序，產生的一些小且不連續的磁區，這些磁區不能夠供用戶作業使用，這些小的磁區稱為記憶體碎片

1. 首次適應演算法

   要求空閑磁區鏈以地址遞增的次序連接，在分配時從鏈首開始順序查找，找到一個能滿足大小的空閑磁區

   這種演算法從低址部分開始劃分很容易產生記憶體碎片，且每次查找都從低址部分開始，增加了查找可用空閑磁區的開銷

2. 回圈首次適應演算法

   由首次適應演算法演變而來，即為程式分配記憶體空間時不再從鏈首開始，而是從上一次分配的空閑磁區的下一個空閑磁區開始

3. 最佳適應演算法

   最佳適應演算法其實不是“最佳”，“最佳”的意思是指找到能夠滿足要求且最小的空閑磁區，按照這種思想每次分配后剩下的空閑磁區一定是最小的，很容易產生記憶體碎片，

4. 最差適應演算法

   最差適應演算法其實不是“最差”，“最差”的意思是指分配是找到滿足要求且最大的空閑磁區，以至于剩下的空閑磁區不會太小產生記憶體碎片

記憶體磁區分配操作

令請求磁區大小為request，每個空閑磁區的大小為free，不再切割的剩余磁區大小為size，分配流程為

磁區回收操作

磁區回收可能出現四種情況

1. 回收區與插入點的前一個磁區相鄰接

   將回收區與插入點前一個磁區合并，不再為回收磁區分配新表項，只需要修改前一個磁區的大小為兩個磁區之和

2. 回收區與插入點的后一個磁區相鄰接

   兩磁區合并形成新的空閑區，用回收區的首址作為新空閑區的首址，大小為兩磁區之和

3. 回收區同時與插入點的前后兩個磁區相鄰接

   三個磁區合為一個磁區，使用前一個磁區的首址，取消后一個磁區的表項

4. 回收區沒有鄰接磁區

   為回收區單獨建立一個新表項，填寫回收區的首址和大小，并根據首址插入到空閑表（鏈）的適當位置

可變磁區分配的優缺點

優點：

1. 有助于多道程式設計，提高了記憶體利用率
2. 要求硬體支持少，代價低
3. 管理演算法容易，容易實作

缺點：

1. 必須給程式分配一個連續的記憶體區域
2. 碎片問題嚴重
3. 不能實作對記憶體的擴充
4. 無法實作虛擬存盤

緊湊

當當前剩余空閑磁區不能滿足程式使用，但是可以將分散的小磁區拼接成一個大磁區時可以把程式裝入運行，

這個拼接程序就是緊炊訓者拼接

只有動態重定位的裝入方式才能支持緊湊，因為緊湊后行程在記憶體中的位置發生了變化，如果不對程式和資料的地址進行修改，程式將無法執行，必須進行重定位才能使之執行，

覆寫技術與交換技術

覆寫和交換技術是實作虛擬存盤的基礎，是對記憶體在邏輯上的擴充，

覆寫

覆寫是指同一記憶體區可以被不同的程式段重復使用，

通常一個程式由若干個功能上相互獨立的程式段組成，程式在執行時也就用到其中幾段，所以可以讓那些不會同時執行的程式段共享一個記憶體區，

把那些可以互相覆寫的程式段稱為覆寫，把那些可共享的記憶體區稱為覆寫區，

把程式執行時并不需要同時裝入記憶體的覆寫組成一組，稱為覆寫段，并分配同一個記憶體區，

覆寫技術的關鍵

提供正確的覆寫結構

覆寫技術的主要特點

打破了必須將一個程式的全部資訊裝入記憶體后才能運行的限制，在一定程度上解決了小記憶體運行大程式的矛盾

交換

根據系統需要把記憶體中暫時不運行的某個(或某些)行程部分或全部移到外存，以便騰出足夠的記憶體空間，再把外存中的某個(或某些)已具備運行條件的程式移到相應的記憶體去，創建行程，并使之投入作業

交換的時機

1. 行程用完時間片或等待輸入/輸出
2. 行程需求擴充存盤而得不到滿足時

具有交換功能的存盤系統通常把記憶體分為檔案區和交換區

• 檔案區用于存放檔案 對檔案區管理的主要目的是提高存盤空間的利用率，所以采用離散分配方式
• 交換區用于存放從記憶體中換出的程式(行程) 對交換區管理的主要目的是提高程式的換入換出速度，所以采用連續分配方式

交換的關鍵

設法減少每次交換的資訊量，以提高速度

交換技術的主要特點

打破了一個程式一旦進入記憶體便一直運行到結束的限制

離散分配方式

分頁存盤管理方式

基本思想

把行程的邏輯空間分成一些大小相同的片段稱為頁或頁面，把記憶體也分成大小相同的片段稱為物理塊或頁框

在分配存盤空間時，總是以塊為單位按照行程的頁數分配物理塊，分配的物理塊可以連續也可以不連續

行程的最后一頁經常裝不完一塊而形成不可以利用的碎片稱為頁內碎片

頁表

為了能在記憶體中找到頁面對應的物理塊，系統為每個行程建立了一個頁面映射表簡稱頁表

作用

實作從頁號到物理塊號的地址映射

動態地址變換

地址結構

分頁管理系統中可以邏輯地址和物理地址可以分解成兩部分

邏輯地址： 頁號 頁內偏移量

物理地址： 塊號 塊內偏移量

給一個邏輯地址為1239 頁面大小為512B

1239 / 512 = 2 余 215

可以判斷該邏輯地址屬于2號頁 頁內位移為215

地址結構可以表示為

地址變換

對于分頁管理方式，頁內偏移量和對應的塊內偏移量是一樣的，所以只需要根據頁表實作頁號到塊號的轉換即可

系統設定一個頁表暫存器(PTR)來存放頁表在記憶體中的始址和頁表的長度

行程未執行時，頁表的始址和長度存放在對應行程的PCB中，當調度程式調度到某行程時，才將它們裝入到頁表暫存器中

邏輯地址轉換成物理地址的程序

首先將頁號和頁表長度進行比較，判斷是否地址越界，如沒有越界，將頁表始址與頁號和頁表項長度的成績相加，找到該表項在頁表中的位置，得到物理塊號裝入物理地址暫存器中，與此同時，再將邏輯地址暫存器中的頁內地址裝入物理地址暫存器中，

一共發生了兩次訪存

1. 根據頁號訪問頁表
2. 根據物理地址進行讀/寫操作

快表

為提高存取速度，在地址變換結構中增設了一個具有并行查尋能力的特殊高速快取存盤器又稱聯想存盤器或快表

其思想與cache相似

兩級和多級頁表

解決頁表變得非常大的問題

對頁表進行分頁，并將各個頁表頁分別存放的不同的記憶體塊中，然后為離散分配的頁表再建立一張頁表稱為外層頁表，來記錄存放各頁表頁的記憶體塊號從而形成了兩級頁表

按照兩級頁表的思路我們也可以設計出多級頁表

分配與回收

分頁存盤管理方式中記憶體的分配和回收采用位示圖法

用一位來表示一個記憶體塊，用一位的兩種狀態來表示記憶體塊是空閑還是已分配

分段存盤管理方式

基本思想

將每個程式的地址空間按照自身的邏輯關系劃分成若干段 ----> 主程式段 子程式段 資料段 堆疊段等

段的長度由回應的邏輯資訊組的長度決定，各段的長度不等，分配記憶體時為每個段分配一連續的存盤空間，段間地址空間可以不連續

段表

為了能從記憶體中找到每個邏輯段所存盤的位置，系統為每個行程建立了一個段映射表簡稱段表

地址變換

存盤保護

1. 越界保護

   段號要小于段表長度，段內地址要小于段長才能進行地址變換，否則會產生越界中斷

2. 越權保護

   設定存取控制欄位來實作對各段的保護

分段和分頁的主要區別

1. 頁是資訊的物理單位，對于用戶來說分頁不是可見的，段是資訊的邏輯單位是程式邏輯上的要求，對用戶來說段是可見的

2. 頁的大小是固定的，由系統決定；段的大小是不固定的，由用戶程式本身決定

3. 從用戶角度來看分頁的地址空間是一維的，段的地址空間是二維的

   ? 為什么

   因為頁的大小是固定的，根據給定一個地址就能算出頁號和頁內偏移量進行定位

   而分段管理必須給出一個段號找到始址然后再根據段內偏移量進行定位，所以說對用戶來說段的地址是二維的

段頁式存盤管理方式

基本思想

記憶體分成大小相同的塊，每個程式地址空間按照邏輯關系分成若干段，并為每個段賦予一個段名，每段可以獨立從0編址，每段按記憶體塊大小分成頁

地址結構

地址變換

學習資料 ：作業系統 第四版 劉振鵬 張明 王煜著