Lecture3-存儲管理

存儲管理是操作系統(tǒng)的重要組成部分，負責(zé)管理計算機系統(tǒng)的重要資源——內(nèi)存儲器。

內(nèi)存空間一般分為兩部分

系統(tǒng)區(qū)：存放操作系統(tǒng)內(nèi)核程序和數(shù)據(jù)結(jié)構(gòu)等。

用戶區(qū)：存放應(yīng)用程序和數(shù)據(jù)。

存儲管理包括以下功能：

存儲分配：位進程分配內(nèi)存空間以便運行，完成內(nèi)存區(qū)的分配和去配工作。

地址映射：內(nèi)存被抽象為一維或二維地址空間；邏輯空間到物理空間映射。

存儲保護：系統(tǒng)隔離分配給進程的內(nèi)存區(qū)，防止地址越界或操作越權(quán)。

存儲共享：系統(tǒng)允許多個進程共享內(nèi)存區(qū)。

存儲擴充：形成虛擬存儲器。

1. 存儲管理的基礎(chǔ)

1.1. 邏輯地址

邏輯地址：又稱相對地址，即用戶編程所使用的地址空間

邏輯地址從零開始編號，有兩種形式：

一維邏輯地址(地址)

二維邏輯地址(段號:段內(nèi)地址)
。

1.2. 物理地址：從處理器角度看到的物理內(nèi)存單元。

物理地址：又稱絕對地址，即程序執(zhí)行所使用的地址空間

處理器執(zhí)行指令時按照物理地址進行

1.3. 段式程序設(shè)計

把一個程序設(shè)計成多個段：代碼段、數(shù)據(jù)段、堆棧段等等

用戶可以自己應(yīng)用段覆蓋技術(shù)擴充內(nèi)存空間使用量，這一技術(shù)是程序設(shè)計技術(shù)，不是OS存儲管理的功能：只是用一些段構(gòu)成一個比較小的程序，然后動態(tài)來調(diào)整。

結(jié)合虛存完成內(nèi)存部分的擴充

1.4. 主存儲器的復(fù)用

多道程序設(shè)計需要復(fù)用主存

按照分區(qū)復(fù)用：

主存劃分為多個固定/可變尺寸的分區(qū)

一個程序/程序段占用一個分區(qū)

按照頁架復(fù)用：

主存劃分成多個固定大小的頁架

一個程序/程序段占用多個頁架

1.5. 存儲管理的基本模式

單連續(xù)存儲管理：一維邏輯地址空間的程序占用一個主存固定分區(qū)或可變分區(qū)

段式存儲管理：段式二維邏輯地址空間的程序占用多個主存可變分區(qū)

頁式存儲管理：一維邏輯地址空間的程序占用多個主存頁架區(qū)

段頁式存儲管理：段式二維邏輯地址空間的程序占用多個主存頁架區(qū)

注意是否可以虛擬化

1.6. 存儲管理模式示意圖

應(yīng)用級程序員直接面對的是邏輯地址，而最后運行需要使用的是物理地址：從處理器角度看到的物理內(nèi)存單元。。

一般目前常用的是動態(tài)重定位，將邏輯地址轉(zhuǎn)換為對應(yīng)的物理地址。

分頁：形成頁框加載程序，頁框和頁框之間可以是不連續(xù)的。

分段：每一個段有相應(yīng)分區(qū)，使用段表完成邏輯段向物理段的映射

段頁式：在分段基礎(chǔ)上，還實現(xiàn)了頁框部分。

2. 存儲管理的功能

2.1. 地址轉(zhuǎn)換

地址轉(zhuǎn)換：又稱重定位，即把邏輯地址轉(zhuǎn)換成絕對地址

靜態(tài)重定位：在程序裝入內(nèi)存時進行地址轉(zhuǎn)換：由裝入程序執(zhí)行，早期小型OS使用，基于地址固定值進行偏移。

動態(tài)重地位(主流)：在CPU執(zhí)行程序時進行地址轉(zhuǎn)換：從效率出發(fā)，依賴硬件地址轉(zhuǎn)換機構(gòu)，運行時正確的將其邏輯地址轉(zhuǎn)換為物理地址。

解釋執(zhí)行指令的時候才進行地址的轉(zhuǎn)換，必須要借助硬件電路完成，而不能用軟件完成(效率考量)

2.2. 存儲保護

為避免主存中的多個進程相互干擾，必須對主存中的程序和數(shù)據(jù)進行保護

私有主存區(qū)中的信息：可讀可寫

公共區(qū)中的共享信息：根據(jù)授權(quán)

非本進程信息：不可讀寫

這一功能需要軟硬件協(xié)同完成：CPU檢查是否允許訪問，不允許則產(chǎn)生地址保護異常，由OS進行相應(yīng)處理

地址越界保護依賴于硬件設(shè)施、常用的有界地址和存儲鍵。

進程在訪問分配給自己的內(nèi)存區(qū)時，要對訪問權(quán)限進行檢查

2.3. 主存儲器空間的分配與去配

分配：進程裝入主存時，存儲管理軟件進行具體的主存分配操作，并設(shè)置一個表格記錄主存空間的分配情況

去配：當某個進程撤離或主動歸還主存資源時，存儲管理軟件要收回它所占用的全部或者部分存儲空間，調(diào)整主存分配表信息

2.4. 主存儲器空間的共享

多個進程共享主存儲器資源：多道程序設(shè)計技術(shù)使若干個程序同時進入主存儲器，各自占用一定數(shù)量的存儲空間，共同使用一個主存儲器

多個進程共享主存儲器的某些區(qū)域：若干個協(xié)作進程有共同的主存程序塊或者主存數(shù)據(jù)塊

2.5. 主存儲器空間的擴充

存儲擴充：把磁盤作為主存擴充，只把部分進程或進程的部分內(nèi)容裝入內(nèi)存：擴大多道程序設(shè)計的道數(shù)

對換技術(shù)：把部分不運行的進程調(diào)出

虛擬技術(shù)：只調(diào)入進程的部分內(nèi)容，對單個進程不使用對換技術(shù)完成，特點是自動化、透明

這一工作需要軟硬件協(xié)作完成

對換進程決定對換，硬件結(jié)構(gòu)完成調(diào)入

CPU處理到不在主存的地址，發(fā)出虛擬地址異常，OS將其調(diào)入，重執(zhí)指令

進程的內(nèi)存為$4MB$，一個頁框$4KB$，有$1024$個頁框，頁框表一共$16$個頁框，頁的壓縮比是$\frac{1024}{16}=64$。

3. 連續(xù)存儲管理

3.1. 單連續(xù)分區(qū)存儲管理

每個進程占用一個物理上完全連續(xù)的存儲空間(區(qū)域)

單連續(xù)分區(qū)存儲管理細分:

單用戶連續(xù)存儲管理

固定分區(qū)存儲管理

可變分區(qū)存儲管理

分區(qū)方式不能實現(xiàn)虛擬存儲。

3.1.1. 單用戶連續(xù)分區(qū)存儲管理

適用于單用戶單任務(wù)操作系統(tǒng)，如DOS

主存區(qū)域(內(nèi)存空間)劃分為系統(tǒng)區(qū)與用戶區(qū)

系統(tǒng)區(qū)用于存放操作系統(tǒng)內(nèi)核程序和數(shù)據(jù)結(jié)構(gòu)等

用戶區(qū)用于存放應(yīng)用程序和數(shù)據(jù)

設(shè)置一個柵欄寄存器界分兩個區(qū)域，硬件用它在執(zhí)行時進行存儲保護

一般采用靜態(tài)重定位進行地址轉(zhuǎn)換

硬件實現(xiàn)代價低

單用戶連續(xù)分區(qū)存儲管理示意

靜態(tài)重定位：在裝入一個作業(yè)時，把該作業(yè)中程序的指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對地址

界限地址:放置軟件訪問到操作系統(tǒng)的部分

3.1.2. 固定分區(qū)存儲管理

固定分區(qū)存儲管理又稱靜態(tài)分區(qū)模式

3.1.2.1. 固定分區(qū)方式的基本思想

內(nèi)存空間被劃分為數(shù)目固定不變的分區(qū)，各分區(qū)大小不等，每個分區(qū)只裝入一個作業(yè)，若多個分區(qū)中都裝有作業(yè)，則它們都可以并發(fā)執(zhí)行。

可用靜態(tài)/動態(tài)重定位、硬件實現(xiàn)代價低、被早期OS采用

3.1.2.2. 固定分區(qū)方式的主存分配

主存分配表：包含內(nèi)容：起始地址、長度、占用標志

內(nèi)存分配方法很簡單，其任務(wù)有何時吧內(nèi)存空間劃分成分區(qū)：由系統(tǒng)管理員和操作系統(tǒng)初始化模塊協(xié)同完成。

作業(yè)進入分區(qū)的排隊策略：

每個分區(qū)有自己的作業(yè)等待隊列，作業(yè)等待能裝下自身的最小分區(qū)。

所有等待處理作業(yè)排成等待隊列，每當有空閑，找到隊列中能進入的最大的一個。

3.1.2.3. 固定分區(qū)方式的地址轉(zhuǎn)換

3.1.2.4. 固定分區(qū)存儲管理的缺點

由于預(yù)先規(guī)定了分區(qū)的大小，使得大作業(yè)無法裝入，而不得不采用覆蓋技術(shù)，帶來負擔(dān)。

內(nèi)存空間利用率不高，作業(yè)很少填滿分區(qū)：固定分區(qū)存儲管理不夠靈活，既不適應(yīng)大尺寸程序，又存在內(nèi)存內(nèi)零頭，有浪費，內(nèi)存內(nèi)零頭是因為在分區(qū)內(nèi)部有零頭。

如果作業(yè)在運行中要求動態(tài)擴展內(nèi)存空間是困難的。

分區(qū)數(shù)目是操作系統(tǒng)初啟動時確定的，會限制多道運行程序的道數(shù)。

3.2. 可變分區(qū)存儲管理

可變分區(qū)存儲管理又稱動態(tài)分區(qū)模式，按照作業(yè)大小劃分分區(qū)，但劃分的時間、大小和位置都是動態(tài)的。

創(chuàng)建一個進程時，根據(jù)進程所需主存量查看主存中是否有足夠的連續(xù)空閑空間

若有，則按需要量分割一個分區(qū)

若無，則令該進程等待主存資源

由于分區(qū)大小按照進程實際需要量來確定，因此分區(qū)個數(shù)是隨機變化的

3.2.1. 可變分區(qū)方式的內(nèi)存分配示例

3.2.2. 可變分區(qū)方式的主存分配表

管理的數(shù)據(jù)結(jié)構(gòu)：已分配區(qū)表與未分配區(qū)表，采用鏈表實現(xiàn)

找一個最大的空閑的位置進行分配

3.2.3. 可變分區(qū)方式的內(nèi)存回收

可變分區(qū)方式的內(nèi)存回收會導(dǎo)致內(nèi)存空間的轉(zhuǎn)換

作業(yè)X撤離后有且僅有如上4種情況。

3.2.4. 可變分區(qū)方式的內(nèi)存分配

最先適應(yīng)分配算法：

最先適應(yīng)就是從上向下查找，找到第一塊區(qū)域放進去，將剩下的區(qū)域分割后仍作為空閑區(qū)。

有利于大作業(yè)裝入，但也使得內(nèi)存低地址和搞地質(zhì)兩端的分區(qū)利用不均衡，回收分區(qū)麻煩。

鄰近適應(yīng)分配算法：

從上次查找結(jié)束的地方開始執(zhí)行最先適應(yīng)分配算法

縮短平均查找時間，且存儲空間利用率更均衡，不會使得小空閑區(qū)集中在內(nèi)存一側(cè)

最優(yōu)適應(yīng)分配算法：

每次都是分配最接近需要使用大小的部分，會生成很多很小的內(nèi)存內(nèi)零頭。

通常會將空閑區(qū)按照長度遞增順序排列，等同于最先適應(yīng)分配算法，查找時間最長

最壞適應(yīng)分配算法：

每次都是挑選最大的一塊區(qū)域進行分配

有利于中小型作業(yè)。

可把空閑區(qū)按長度遞減順序排列，等同于最先適應(yīng)分配算法。

快速適應(yīng)分配算法：課本補充

為經(jīng)常用到的長度的空閑區(qū)設(shè)立單獨的空閑區(qū)鏈表，查找非常快速

歸還內(nèi)存空間時和鄰近空閑區(qū)的合并復(fù)雜且耗時。

最常用的是最先適應(yīng)分配算法，其次是鄰近適應(yīng)分配算法和最優(yōu)適應(yīng)分配算法

3.3. 地址轉(zhuǎn)換與存儲保護

硬件實現(xiàn)機制與動態(tài)重定位

進程的程序和數(shù)據(jù)的地址由硬件完成

基址寄存器：分配進程的起始地址

限長寄存器：進程占用的連續(xù)存儲空間的長度

3.4. 分區(qū)方式的內(nèi)存零頭

固定分區(qū)方式會產(chǎn)生內(nèi)存內(nèi)零頭

可變分區(qū)方式也會隨著進程的內(nèi)存分配產(chǎn)生一些小的不可用的內(nèi)存分區(qū)，稱為內(nèi)存外零頭，內(nèi)存外零頭是指分區(qū)內(nèi)部是沒有零頭的，而是在外面的零頭。

最優(yōu)適配算法最容易產(chǎn)生外零頭

任何適配算法都不能避免產(chǎn)生外零頭

3.5. 內(nèi)存不足的存儲技術(shù)

3.5.1. 移動技術(shù)(程序浮動技術(shù))

碎片：內(nèi)存中的小空閑區(qū)，移動分區(qū)來解決內(nèi)存外零頭問題。

當未分配區(qū)表中找不到足夠大的空閑區(qū)來裝入新進程時，我們使用移動技術(shù)來完成內(nèi)存緊湊，實現(xiàn)方法：

全部移動到一側(cè)

移動直到有足夠大的空閑區(qū)

需要動態(tài)重定位支撐:靜態(tài)重定位無法解決內(nèi)存外零頭

問題：移動技術(shù)有極大的系統(tǒng)開銷，而且并不是任何時間下都可以進行的，比如通道或DMA等按照絕對物理地址交換信息時。

移動技術(shù)的工作流程

注意如果剩余空間地方不足，那么是不會移動分區(qū)的

3.5.2. 對換技術(shù)

對換技術(shù)廣泛應(yīng)用于分時系統(tǒng)的調(diào)度，用來解決內(nèi)存容量不足的問題，也可以應(yīng)用于批處理系統(tǒng)，以平衡系統(tǒng)負載。

如果當前一個或多個駐留進程都處于阻塞態(tài)，此時選擇其中一個進程，將其暫時移出內(nèi)存，騰出空間給其他進程使用；同時把磁盤中的某個進程換入內(nèi)存，讓其投入運行，這種互換稱為對換。

被對換出去的進程的狀態(tài)會調(diào)整為就緒態(tài)，并且通知存儲管理程序，一旦內(nèi)存可用，立即將該進程對換回內(nèi)存。

對換技術(shù)關(guān)鍵點

被對換進程：通常系統(tǒng)選擇時間片耗盡或優(yōu)先級較低的進程對換出去。

對換的進程信息：將數(shù)據(jù)區(qū)和堆棧通過文件系統(tǒng)轉(zhuǎn)換為特殊文件保存。

被對換的時機：

批處理系統(tǒng)中：進程需要擴充內(nèi)存空間但不能被滿足時

分時系統(tǒng)：

時間片結(jié)束時

執(zhí)行I/O操作時

對換需要訪問磁盤，是I/O集中型操作，但是操作系統(tǒng)可以讓計算型任務(wù)與對換并行，不會造成系統(tǒng)效率顯著下降。

詳見P205

3.5.3. 覆蓋技術(shù)

移動和對換技術(shù)解決因多個程序存在而導(dǎo)致內(nèi)存區(qū)不足問題。

但是如果程序長度超過物理內(nèi)存的總和，或者超出固定分區(qū)大小，則會出現(xiàn)內(nèi)存永久性短缺，大程序無法運行，解決方案是覆蓋技術(shù)。

覆蓋是指程序執(zhí)行過程中程序的不同模塊在內(nèi)存中相互替代，以達到小內(nèi)存執(zhí)行大程序的目的。

基本的實現(xiàn)技術(shù)是把用戶空間分成固定區(qū)和一個或多個覆蓋區(qū)，把控制或不可覆蓋的部分放到固定區(qū)，其余按照調(diào)用結(jié)構(gòu)以及先后關(guān)系分段并存放在磁盤上，運行時一次調(diào)入覆蓋區(qū)。

不足是將存儲管理工作轉(zhuǎn)給程序員，他們必須根據(jù)可用物理內(nèi)存空間來設(shè)計和編寫程序。

4. 虛擬存儲器的概念

之前所介紹的存儲管理，我們稱為實存管理，必須為進程分配足夠內(nèi)存空間，裝入其全部信息，否則無法運行。

4.1. 虛擬存儲器思想的提出

主存容量限制帶來諸多不便

用戶編寫程序必須考慮主存容量限制

多道程序設(shè)計的道數(shù)受到限制

用戶編程行為分析

全面考慮各種情況，執(zhí)行時有互斥性

順序性和循環(huán)性等空間局部性行為

某一階段執(zhí)行的時間局部性行為

因此可以考慮部分調(diào)入進程內(nèi)容

4.1.1. 分區(qū)存儲的限制

每個進程(每個連續(xù)邏輯地址空間)必須獲得物理地址上的完全連續(xù)，突破：分區(qū)，分段

必須一次性滿足滿足每個進程運行時的全部內(nèi)存需求，突破：虛擬存儲，部分裝入對換

注：一旦發(fā)生缺頁，則會從運行態(tài)調(diào)整到阻塞態(tài)，可能會導(dǎo)致部分進程的速度被拖慢，但是整體效率會提高

4.1.2. 程序運行的局部性原理

在一個周期內(nèi)，這個進程在運行時會集中訪問一些存儲區(qū)：某存儲單元被訪問，改單元機器相鄰存儲單元很可能會被訪問(空間局部性)，或者最近訪問過的存儲單元很快又能被訪問(時間局部性)。

根據(jù)程序運行的局部性原理，會保證程序的訪問效率比較高，缺頁率相對低，以時間換取空間

4.2. 虛擬存儲器的基本思想

部分裝入：存儲管理把進程全部信息放在輔存中，執(zhí)行時先將其中一部分裝入主存，以后根據(jù)執(zhí)行行為隨用隨調(diào)入

按需調(diào)出：如主存中沒有足夠的空閑空間，存儲管理需要根據(jù)執(zhí)行行為把主存中暫時不用的信息調(diào)出到輔存上去

4.3. 虛擬存儲器的實現(xiàn)思路

需要建立與自動管理兩個地址空間

(輔存)虛擬地址空間：容納進程裝入

(主存)實際地址空間：承載進程執(zhí)行

對于用戶，計算機系統(tǒng)具有一個容量大得多的主存空間，即虛擬存儲器

4.4. 虛擬存儲器

在具有層次結(jié)構(gòu)存儲器的計算機系統(tǒng)中，自動實現(xiàn)部分裝入和部分替換功能，能從邏輯上為用戶提供一個比物理內(nèi)存容量大得多的、可尋址的內(nèi)存儲器。

虛擬存儲器是一種地址空間擴展技術(shù)，通常意義上對用戶編程是透明的，除非用戶需要進行高性能的程序設(shè)計

邏輯地址：進程角度看到的邏輯內(nèi)存單元。

物理地址：從處理器角度看到的物理內(nèi)存單元。

對換技術(shù)以進程為單位，虛存管理以頁或段為單位。

5. 存儲管理的硬件支撐

5.1. 存儲器的組織層次

越處于頂端，訪問速度越快，容量越小，單位字節(jié)價格會越高。我們根據(jù)實際情況，選擇使用什么樣子的存儲器。

寄存器、緩存和內(nèi)存屬于操作系統(tǒng)存儲管理的范疇，掉電后信息丟失。

磁盤和磁帶屬于穩(wěn)健管理和設(shè)備管理的管轄對象，信息永久保存。

可執(zhí)行程序必須被保存在內(nèi)存中，與設(shè)備交換的信息也依托于內(nèi)存地址空間。

由于程序處理數(shù)據(jù)時存在順序性和局部性，故執(zhí)行時僅需調(diào)入當前運行使用的一部分，其他部分待需要時再逐步調(diào)入。

5.2. 存儲管理涉及的存儲對象

存儲管理是OS管理主存儲器的軟件部分

為獲得更好的處理性能，部分主存程序與數(shù)據(jù)(特別是關(guān)鍵性能數(shù)據(jù))被調(diào)入Cache，存儲管理需要對其進行管理，甚至包括對聯(lián)想存儲器的管理

為獲得更大的虛擬地址空間，存儲管理需要對存放在硬盤、固態(tài)硬盤、甚至網(wǎng)絡(luò)硬盤上的虛擬存儲器文件進行管理，首選固態(tài)硬盤

5.3. 高速緩存存儲器(Cache)

Cache是介于CPU和主存儲器間的高速小容量存儲器，由靜態(tài)存儲芯片SRAM組成，容量較小但比主存DRAM技術(shù)更加昂貴而快速，接近于CPU的速度

CPU往往需要重復(fù)讀取同樣的數(shù)據(jù)塊，Cache的引入與緩存容量的增大，可以大幅提升CPU內(nèi)部讀取數(shù)據(jù)的命中率，從而提高系統(tǒng)性能

5.3.1. 高速緩存存儲器的構(gòu)成

高速緩沖存儲器通常由高速存儲器、聯(lián)想存儲器、地址轉(zhuǎn)換部件、替換邏輯等組成

聯(lián)想存儲器：根據(jù)內(nèi)容進行尋址的存儲器

地址轉(zhuǎn)換部件：通過聯(lián)想存儲器建立目錄表以實現(xiàn)快速地址轉(zhuǎn)換。命中時直接訪問Cache；未命中時從內(nèi)存讀取放入Cache

替換邏輯部件：在緩存已滿時按一定策略進行數(shù)據(jù)塊替換，并修改地址轉(zhuǎn)換部件

MMU：硬件，存儲管理單元

5.3.2. 高速緩存存儲器的組織

由于CPU芯片面積和成本，Cache很小

根據(jù)成本控制，劃分為L1、L2、L3三級

5.3.3. 高速緩存存儲器的分級

L1 Cache：分為數(shù)據(jù)緩存和指令緩存；內(nèi)置；其成本最高，對CPU的性能影響最大；通常在32KB-256KB之間

L2 Cache：分內(nèi)置和外置兩種，后者性能低一些；通常在512KB-8MB之間

L3 Cache：多為外置，在游戲和服務(wù)器領(lǐng)域有效；但對很多應(yīng)用來說，總線改善比設(shè)置L3更加有利于提升系統(tǒng)性能

5.3.4. 早期奔騰處理器架構(gòu)

Intel在最初的奔騰處理器中只包含L1 Cache(含Code Cache和Data Cache)

5.3.5. 奔騰4處理器架構(gòu)

奔騰4的處理器中包含L1 Cache和L2 Cache

5.3.6. i5處理器架構(gòu)

5.3.7. i7處理器架構(gòu)

i7處理器中包含L1至L3三級Cache，如果是包含了三級Cache，那么意味著CPU與Cache之間的鏈接在CPU內(nèi)部，Core i7處理器方案是將L3 Cache設(shè)計為包含在處理中的多個核心Cache

5.4. 地址轉(zhuǎn)換/存儲保護的硬件支撐

限長寄存器來檢查越界中斷

相加體現(xiàn)了動態(tài)重定位

比較體現(xiàn)了存儲保護

5.5. 存儲管理與硬件支撐

鑒于程序執(zhí)行與數(shù)據(jù)訪問的局部性原理，存儲管理軟件使用Cache可以大幅度提升程序執(zhí)行效率

動態(tài)重定位、存儲保護等，若無硬件支撐在效率上是無意義的，即無實現(xiàn)價值

無虛擬地址中斷，虛擬存儲器無法實現(xiàn)

無頁面替換等硬件支撐機制，虛擬存儲器在效率上是無意義的

5.6. 虛擬存儲與硬件支撐

操作系統(tǒng)的存儲管理依靠底層硬件支撐來完成任務(wù)，該硬件是存儲管理部件(Memory Managment Unit, MMU)，提供地址轉(zhuǎn)換和存儲保護并支持虛存管理和多任務(wù)管理。

MMU由一組集成電路芯片組成，邏輯地址作為輸入，物理地址作為輸出，直接送達總線，對內(nèi)存單元進行尋址。

主要功能：P217

管理硬件頁表基址寄存器

分解邏輯地址

管理快表

訪問頁表

發(fā)出異常

管理特征位

6. 頁式存儲管理

6.1. 頁式存儲管理的基本原理

頁面：金層邏輯地址空間分成大小相等的區(qū)，每個區(qū)稱為頁面或頁，頁號從0開始編號。比如出版一本書，出版受到頁大小影響，最后由若干頁組成，一般大小為4KB

頁框：又稱頁幀，把內(nèi)存物理地址空間分成大小相等的區(qū)，其大小與頁面大小相等，每個區(qū)都是一個頁框(物理塊)，塊號從0開始。

邏輯地址：分頁存儲器的邏輯地址由頁號 + 頁面偏移組成(地址總線32位)

頁號：32-12 = 20位，則包含頁$2^{20}$位

頁面偏移：頁面大小為4KB，則需要12位

內(nèi)存頁框表：該表長度取決于內(nèi)存劃分的物理塊數(shù)，表項中給出物理塊使用情況，0為空閑，1為占用，有的系統(tǒng)還會添加保護位、臟位等等。

頁表：將頁裝入到內(nèi)存中，頁未必連續(xù)，我們需要為每一個頁面設(shè)立一個重定向寄存器，這個寄存器的集合就是頁表。

數(shù)學(xué)角度：$頁面號\to 頁框號$

系統(tǒng)設(shè)置頁表基址寄存器，存放當前運行進程的頁表起始地址。

$物理地址=頁框號?塊長+頁內(nèi)偏移$，實際轉(zhuǎn)換時，我們將頁內(nèi)偏移作為低地址，根據(jù)頁號從頁表中查找到頁框號并作為高地址即可。

頁表不存儲頁號，只存儲頁框號和相應(yīng)標志位

頁式存儲產(chǎn)生的碎片是內(nèi)部碎片

可以類比固定分區(qū)

比如19KB的程序，加載到頁大小為4KB中，會產(chǎn)生1KB的內(nèi)存內(nèi)零頭。

頁號p

頁內(nèi)偏移d

頁框號b

6.2. 頁式存儲管理中的地址

頁式存儲管理的邏輯地址由兩部分組成，頁號和單元號(頁內(nèi)偏移)，邏輯地址形式：

頁式存儲管理的物理地址也有兩部分組成：頁架號(頁框號)和單元號(頁內(nèi)偏移)，物理地址形式：

地址轉(zhuǎn)換可以通過查頁表完成

用戶不必關(guān)心頁的具體存儲，系統(tǒng)幫助用戶完成從頁號/頁架號映射到物理地址來完成。

6.3. 頁式存儲管理的地址轉(zhuǎn)換例子

邏輯地址頁號，作為偏移量到頁表中進行偏移，得到頁架號(頁框號)。

對頁架號(頁框號)進行二進制移位操作(補充12個0)，映射到物理空間中本頁的首地址，然后根據(jù)offset(單元號)在頁內(nèi)進行偏移，從而獲取到絕對地址(物理地址：從處理器角度看到的物理內(nèi)存單元)中的值。

6.4. 頁式存儲管理的內(nèi)存分配/去配

頁式存儲管理，系統(tǒng)要建立一張內(nèi)存物理塊表，用來記錄頁框狀態(tài)，管理物理內(nèi)存的而分配，所包含的信息包含內(nèi)存總塊數(shù)、哪些為空閑塊、哪些已經(jīng)分配以及分配給哪個進程等。

最簡單方法是用一張位示圖來記錄主存分配情況，使用一位來標記一個頁框的使用或空閑的狀態(tài)(壓縮的思想)

如果夠，則去查找一個標記為0的裝入

如果不夠，采用一定的策略

建立進程頁表維護主存邏輯完整性

分頁存儲管理頁框分配算法：

進行內(nèi)存分配時，先檢查空閑塊數(shù)是否滿足用戶進行要求

若不能則使進程等待。

若能則查位示圖，將位0置為占用標志，從空閑塊數(shù)中減去本次占用快熟，找到對應(yīng)的頁框號，寫入頁表。

歸還時逆操作。

6.5. 頁的共享

頁式存儲管理能夠?qū)崿F(xiàn)多個進程共享程序和數(shù)據(jù)

數(shù)據(jù)共享：不同進程可以使用不同頁號共享數(shù)據(jù)頁，但是必須解決共享信息保護問題，常用的是在頁表中添加標記位。

程序共享：不同進程必須使用相同頁號共享代碼頁，共享代碼頁中的(JMP <頁內(nèi)地址>)指令，使用不同頁號是做不到，進程一和二都要跳轉(zhuǎn)到頁內(nèi)的位置，程序共享要求頁號相同。

6.6. 頁式存儲管理的地址轉(zhuǎn)換

快表TLB，Translation Look_aside Buffer

6.6.1. 頁式存儲管理的地址轉(zhuǎn)換代價

頁表放在主存: 每次地址轉(zhuǎn)換必須訪問兩次主存

按頁號讀出頁表中的相應(yīng)頁架號

按計算出來的絕對地址進行讀寫

存在問題：降低了存取速度

解決辦法：利用Cache存放部分頁表，即快表

6.6.2. 頁式存儲管理的快表

為提高地址轉(zhuǎn)換速度，設(shè)置一個專用的高速存儲器，用來存放頁表的一部分

快表：存放在高速存儲器中的頁表部分，快表表項：頁號+頁架號

這種高速存儲器是聯(lián)想存儲器(TLB)，即按照內(nèi)容尋址，而非按照地址訪問，根據(jù)頁號進行尋址。

6.6.3. 基于快表的地址轉(zhuǎn)換流程

按邏輯地址中的頁號查快表

若該頁已在快表中，則由頁架號和單元號形成絕對地址

若該頁不在快表中，則再查主存頁表形成絕對地址，同時將該頁登記到快表中

當快表填滿后，又要登記新頁時，則需在快表中按一定策略淘汰一個舊登記項

快表可以理解為一個簡單的賬本

6.6.4. 引入快表后的地址轉(zhuǎn)換代價

采用快表后，可以加快地址轉(zhuǎn)換速度

假定主存訪問時間為200毫微秒，快表訪問時間為40毫微秒，查快表的命中率是90%，平均地址轉(zhuǎn)換代價為$(200+40)?90\%+(200+200+40)?10\%=260$毫微秒

比兩次訪問主存的時間(400毫微秒)下降了36%

6.6.5. 多道程序環(huán)境下的進程表

進程表中登記了每個進程的頁表

進程占有處理器運行時，其頁表起始地址和長度送入頁表控制寄存器

頁表長度就是頁表項的數(shù)量

6.6.6. 多道程序環(huán)境下的地址轉(zhuǎn)換

頁表控制寄存器存儲了當前的頁表的地址和長度

頁表控制寄存器和進程表是有關(guān)聯(lián)的，所有進程在進程表中都有一項，當這個進程占據(jù)CPU時，這個進程就占據(jù)頁表控制寄存器。

不使用快表:首先從邏輯地址中，提取出頁號，比較頁號是否出現(xiàn)越界中斷，如果沒有越界，則根據(jù)頁表向下偏移到對應(yīng)的塊號，提取出頁表信息和頁框號，頁框號結(jié)合單元號，得到物理地址

快表:不是從頁表中查找，而是優(yōu)先從快表中查詢塊號。

6.7. 多級頁表

6.7.1. 多級頁表的概念

現(xiàn)代計算機普遍支持$2^{32}?2^{64}$容量的邏輯地址空間，采用分頁存儲管理時，頁表相當大，以Windows為例，其運行的Intel x86平臺具有32位地址，規(guī)定頁面4KB($2^{12}$)時，那么，4GB($2^{32}$)的邏輯地址空間由1MB($2^{20}$)個頁組成，若每個頁表項占用4個字節(jié)，則需要占用4MB($2^{22}$)連續(xù)主存空間存放頁表。系統(tǒng)中有許多進程，因此頁表存儲開銷很大。

做法：把整個頁表分割成許多小頁表，每個稱為頁表頁，它的大小與頁框長度相同，于是每個頁表頁含有若干頁表表項。

頁表項從0開始編號，允許放到不連續(xù)的頁框中，為了找到頁表頁，建立地質(zhì)索引，稱為頁目錄表。

系統(tǒng)為每一個進程建立一張頁目錄表，他的每一個表項指出一個頁表頁，而頁表頁的每個表項給出頁面和頁框的對應(yīng)關(guān)系。

邏輯地址結(jié)構(gòu)有三部分組成：頁目錄、頁表頁和位移

解決頁表頁如何占用內(nèi)存空間的問題，解決方法：進程運行設(shè)計到的頁面的頁表頁放置在內(nèi)存中，其他頁表頁使用時動態(tài)調(diào)入，因此需要添加標志位指示是否調(diào)入內(nèi)存。

6.7.2. 多級頁表地址轉(zhuǎn)換過程

6.7.3. 多級頁表結(jié)構(gòu)的本質(zhì)

多級不連續(xù)導(dǎo)致多級索引。

以二級頁表為例，用戶程序的頁面不連續(xù)存放，要有頁面地址索引，該索引是進程頁表；進程頁表又是不連續(xù)存放的多個頁表頁，故頁表頁也要頁表頁地址索引，該索引就是頁目錄。

頁目錄項是頁表頁的索引，而頁表頁項是進程程序的頁面索引。

6.8. 反置頁表(IPT)

頁表設(shè)計的一個重要缺陷是頁表的大小與虛擬地址空間的大小成正比

對于一個128MB的計算機，如果頁面尺寸為4KB，頁表項大小為4B，那么其反置頁表只占有128KB的內(nèi)存。

通過這個結(jié)構(gòu)，哈希表和反向表中只有一項對應(yīng)于一個實存頁(面向?qū)嵈?，而不是虛擬頁(面向虛存)。因此，不論由多少進程、支持多少虛擬頁，頁表都只需要實存中的一個固定部分。

正向頁表(名單)、反置頁表(現(xiàn)場坐的是誰)

正向頁表:以頁號為索引(隱含)，完整連續(xù)排列，頁表項中不含頁號，每個進程單獨一個頁表

反置頁表:以頁框號為索引(隱含)，完整連續(xù)排列，每個頁框填入的是哪個進程的哪個頁號，索引進程共用一個反置頁表。其頁表項不包含頁框號

6.8.1. 反置頁表的提出

頁表及相關(guān)硬件機制在地址轉(zhuǎn)換、存儲保護、虛擬地址訪問中發(fā)揮了關(guān)鍵作用，為頁式存儲管理設(shè)置專門硬件機構(gòu)

內(nèi)存管理單元MMU：CPU管理虛擬/物理存儲器的控制線路，把虛擬地址映射為物理地址，并提供存儲保護，必要時確定淘汰頁面

反置頁表IPT：MMU使用的數(shù)據(jù)結(jié)構(gòu)

6.8.2. 反置頁表的基本設(shè)計思想

針對內(nèi)存中的每個頁架建立一個頁表，按照塊號(頁架號)排序

表項包含：正在訪問該頁框的進程標識、頁號及特征位，和哈希鏈指針等

用來完成內(nèi)存頁架到訪問進程頁號的對應(yīng)，即物理地址到邏輯地址的轉(zhuǎn)換

6.8.3. 反置頁表的頁表項

頁號：虛擬地址頁號

進程標志符：使用該頁的進程號(頁號和進程標志符結(jié)合起來標志一個特定進程的虛擬地址空間的一頁)

標志位：有效、引用、修改、保護和鎖定等標志信息

鏈指針：哈希鏈，如果某個項沒有鏈項，則該域為空(允許用一個單獨的位來表示)。

6.8.4. 反置頁表的邏輯地址

進程標識符：使用該頁的進程。

頁號：虛擬地址頁號部分，頁號和進程標志符結(jié)合起來標志一個特定的進程的虛擬地址空間的一頁。

頁內(nèi)位移

6.8.5. 反置頁表的地址轉(zhuǎn)換

上圖4-10中，以頁框號為索引，記錄當前頁框中存儲的是哪個進程的哪個頁

反置頁表地址轉(zhuǎn)換過程如下:

需要訪問內(nèi)存地址時，地址轉(zhuǎn)換機制用進程標識符與頁號作為輸入，由哈希函數(shù)先映射到哈希表，哈希表項存放的是指向IPT表項的指針

此指針可能就是指向匹配的IPT表項

如果不是則遍歷哈希鏈直至找到進程標識符與頁號均匹配的IPT表項：因為多個頁號通過哈希值可能得到了相同的哈希值，所以我們選擇使用哈希鏈。

而此表項的**序號(索引)**就是頁框號，通過拼接頁內(nèi)位移便可生成物理地址。

若在反置頁表中未能找到匹配的IPT頁表項，說明此頁不在內(nèi)存，觸發(fā)缺頁異常，請求操作系統(tǒng)通過頁表調(diào)入：發(fā)生缺頁中斷時需要多訪問一次磁盤，速度會比較慢。

頁框號是根據(jù)公式換算出來的:$x_i=x_0+4?i$

6.8.6. 反置頁表

線性反置頁表反置頁表

哈希線性反置頁表	主存分配的位示圖和鏈表方法

6.8.7. 反置頁表下的地址轉(zhuǎn)換示意

未顯示選擇淘汰頁面，同樣由MMU完成

使用哈希提高性能->不必遍歷

7. 段式存儲管理

段式存儲管理基于可變分區(qū)存儲管理原理。

7.1. 程序分段結(jié)構(gòu)

高級語言采用模塊化程序設(shè)計方法。應(yīng)用程序由若干程序段(模塊)組成，如由主程序段(M)、子程序段(X)、數(shù)據(jù)段(D)和工作區(qū)段(W)組成，每一段都從0開始編制，各有各自名字和長度且實現(xiàn)不同功能。

編譯后段間地址是不連續(xù)的，段內(nèi)地址是連續(xù)的。

7.2. 段式存儲邏輯地址

分段存儲器的邏輯地址由兩部分組成:段號+段內(nèi)偏移

頁式存儲管理中頁的劃分對程序員不可見。

段式存儲管理中段的劃分對程序員可見。

7.3. 段式存儲的段表

存儲分配時，應(yīng)該為進入內(nèi)存的作業(yè)建立段表，各段在內(nèi)存中的情況有段表來記錄，包含了段號、段起始長度和長度。

撤銷進程時，回收所占用的內(nèi)存空間，并清除此進程的段表。

段表表項實際上起到了基址/限長寄存器的作用，設(shè)置段表控制寄存器

7.4. 段式存儲管理的基本思想

段式存儲管理基于可變分區(qū)存儲管理實現(xiàn)，一個進程要占用多個分區(qū)

硬件需要增加一組用戶可見的段地址寄存器(代碼段、數(shù)據(jù)段、堆棧段，附加段)，供地址轉(zhuǎn)換使用

存儲管理需要增加設(shè)置一個段表，每個段占用一個段表項，包括：段始址、段限長，以及存儲保護、可移動、可擴充等標志位

7.5. 段式存儲管理的地址轉(zhuǎn)換流程

使用終端來完成

7.6. 段的共享

如果多個進程段表中的某段指向內(nèi)存相同的地址，內(nèi)存中以該處為起始地址的某段就可以被共享。

對共享段的信息必須進行保護，如規(guī)定只能讀出不能寫入，不滿足保護條件則產(chǎn)生保護中斷

為了方便共享，系統(tǒng)中常常建立一張共享段表記錄所有共享段，包含段名、共享計數(shù)、段長、段首址、保護位等。

8. 分頁和分段的尋址計算

8.1. 分段和分頁的比較

分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶可見

段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何主存地址開始。

分段方式中，源程序(段號，段內(nèi)位移)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。

分頁是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無關(guān)，用戶不可見，

頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始

分頁方式中，源程序(頁號，頁內(nèi)位移)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)

8.2. 分頁:邏輯地址到物理地址

9. 段頁式存儲管理

9.1. 段頁式存儲管理的基本思想

段式存儲管理可以基于頁式存儲管理實現(xiàn)

每一段不必占據(jù)連續(xù)的存儲空間，可存放在不連續(xù)的主存頁架中

能夠擴充為段頁式虛擬存儲管理

裝入部分段，或者裝入段中部分頁面

9.2. 段頁式存儲管理的段表和頁表

既有段表，也有頁表

段表中存儲的是頁表和頁表始址

9.3. 段頁式存儲管理的地址轉(zhuǎn)換

10. 頁式虛擬存儲管理

10.1. 頁式虛擬存儲管理的基本原理

將進程信息副本存放在外存中，當它被調(diào)度投入運行時，程序和數(shù)據(jù)沒有全部裝入內(nèi)存，僅裝入當前使用頁面，進程執(zhí)行過程中訪問到不再內(nèi)存的頁面時，再由系統(tǒng)自動調(diào)入。

頁式虛擬存儲是現(xiàn)代OS的主流存儲管理技術(shù)

請求頁式存儲管理：由于頁面在需要時是根據(jù)進程請求裝入內(nèi)存的

請求頁式存儲管理

優(yōu)點：進程的程序和數(shù)據(jù)可按頁分散存儲在內(nèi)存中，有利于內(nèi)存利用率和多道程序運行

缺點：需要硬件支持、處理缺頁中斷、機器成本增加、系統(tǒng)開銷加大，頁內(nèi)存在碎片。

10.1.1. 頁式虛擬存儲管理的頁表

需要擴充頁表項，至少包含如上信息，指出：

主存駐留標志：指出頁面是否已經(jīng)裝入內(nèi)存。1表示在內(nèi)存中可以被正常訪問，0表示不能立即訪問，產(chǎn)生缺頁異常。

修改位：被設(shè)置后，該頁被調(diào)出內(nèi)存前必須先寫回磁盤，保障數(shù)據(jù)一致性

保護位：限制頁面訪問權(quán)限

引用位：在頁面被引用無論是讀寫時設(shè)置，用來幫助系統(tǒng)進行頁面淘汰。

內(nèi)存塊號：頁面對應(yīng)的頁框號，用來地址轉(zhuǎn)換。

32位操作系統(tǒng):32bit標識一個頁表項

頁號是隱含信息，不是直接存儲的信息。

10.2. 頁式虛擬存儲管理的實現(xiàn)

CPU處理地址

若頁駐留，則獲得塊號形成絕對地址

若頁不在內(nèi)存，則CPU發(fā)出缺頁中斷

OS處理缺頁中斷

若有空閑頁架，則根據(jù)輔存地址(虛存)調(diào)入頁，更新頁表與快表等

若無空閑頁架，則決定淘汰頁，調(diào)出已修改頁，調(diào)入頁，更新頁表與快表

10.2.1. 頁式虛擬存儲管理的地址轉(zhuǎn)換

本指令沒有被處理完，是在查找地址的時候發(fā)生的中斷，所以要回退指令執(zhí)行。
缺頁中斷完成后要重新執(zhí)行被中斷指令。

10.2.2. 頁式虛擬存儲管理的地址轉(zhuǎn)換全過程

地址轉(zhuǎn)換過程

MMU接收CPU傳送來的邏輯地址并自動按頁面大小把它從某位起分解成兩部分:頁號和頁內(nèi)位移。

以頁號為索引快速搜索快表TLB。

如果命中，立即送出頁框號，并與賈內(nèi)位移拼接成物理地址，然后進行訪問權(quán)限檢查，如獲通過，進程就可以訪問物理地址。

如果不命中，由硬件以頁號為索引搜索頁表，頁表基址由硬件頁表基址寄存器指出。

如果頁表被命中，說明訪問頁面已在內(nèi)存中，可送出頁框號，并與頁內(nèi)位移拼接成物理地址，然后進行訪問權(quán)限檢查，如獲通過，進程就可以訪問物理地址，同時要把這個頁面和頁框信息裝入快表TLB，以備再次訪問。

如果發(fā)現(xiàn)頁表中的對應(yīng)頁面失效，MMU發(fā)出缺頁異常，請求操作系統(tǒng)進行處理，MMU工作到此結(jié)束。

MMU發(fā)現(xiàn)缺頁并發(fā)出缺頁異常，存儲管理接收控制，進行缺頁異常處理的過程如下：

掛起請求調(diào)頁的進程。

根據(jù)頁號搜索外頁表，找到存放此頁的磁盤物理地址。

查看內(nèi)存是否有空閑頁框，如有則分配一個，轉(zhuǎn)(6)。

如果內(nèi)存中無空閑頁框，按照替換算法選擇淘汰頁面，檢查其是否被寫過或修改過，若否則轉(zhuǎn)(6)，若是則轉(zhuǎn)(5)。

10.2.3. TLB(快表)

Note:快表存儲正在進行的進程的若干(非連續(xù))的頁表項，其意義在于：快表訪問速度高于內(nèi)存，減少訪問內(nèi)存的次數(shù)，提高也是尋址效率

11. 頁面調(diào)度

當主存空間已滿而又需要裝入新頁時，頁式虛擬存儲管理必須按照一定的算法將已在主存的一些頁調(diào)出去

選擇淘汰頁的工作成為頁面調(diào)度

選擇淘汰頁的算法稱為頁面調(diào)度算法

11.1. 交換區(qū)

操作系統(tǒng)需要在磁盤上定義一個交換區(qū)用來保存臨時換出的頁面，交換區(qū)由磁盤上的一個或多個磁盤分區(qū)組成。

簡單做法：進程啟動時，留出大小和進程一樣大的交換分區(qū)。

與進程對應(yīng)的是其交換區(qū)的磁盤地址，即進程映像所保存的位置，這一信息記錄在進程的外頁表中。

問題：進程啟動可能會在增大，解決：將正文、數(shù)據(jù)和堆棧分別保留交換區(qū)，并且多留幾塊。

交換區(qū)管理重點是維護交換區(qū)映射表，記錄所有的唄換出內(nèi)存的頁面在交換區(qū)中的位置，以便需要時換入，第二次被換出內(nèi)存時，當且僅當頁面修改過才再次寫入，否則直接拋棄。

11.2. 頁面裝入策略和清除策略

頁面裝入策略用來解決何時將頁面裝入內(nèi)存

請頁式：當產(chǎn)生缺頁異常時調(diào)入頁面

在替換時只有發(fā)生了更改才寫回。

優(yōu)點：只有被訪問頁面才會被調(diào)入，節(jié)省內(nèi)存

缺點：缺頁異常處理次數(shù)多，系統(tǒng)開銷大。

預(yù)調(diào)式：在使用頁面前預(yù)先調(diào)入內(nèi)存，操作系統(tǒng)根據(jù)某種算法動態(tài)預(yù)測進程最可能訪問的界面，每次調(diào)入若干頁面。

在替換前需要將他們都寫回磁盤，可成批進行。

優(yōu)點：減少磁盤I/O的啟動次數(shù)，節(jié)省尋道和搜索時間。

缺點：如果調(diào)入的大多數(shù)界面都沒有被使用則效率很低。

11.3. 頁面分配策略

請求分頁虛存管理可能在缺頁方面付出很大的代價，需要確定頁面調(diào)度算法的作用范圍是此進程的頁面，還是內(nèi)存中的所有進程的頁面。

全局替換：不考慮進程屬主

局部替換：僅限于進程本身

分配方式

固定分配：進程生命周期中保持頁框數(shù)固定不變，有平均分配、比例分配、優(yōu)先權(quán)分配等方式。

可變分配：進程生命周期中所分得的頁框數(shù)可變。

缺頁率較高，說明局部性較差，可以適度提高分配的頁框數(shù)。

缺頁率較低，可以適度降低分配的頁框數(shù)

工作集(駐留集)：每個進程維護的一組頁面。

可變分配配合局部替換可以克服全局替換的缺點。

11.3.1. 固定分配，本地范圍

分配給進程的幀數(shù)是固定的

從分配給過程的框架中選擇要替換的頁面

11.3.2. 變量分配，全局范圍

分配給進程的幀數(shù)是可變的

從所有框架中選擇要替換的頁面

最容易實現(xiàn)

被許多操作系統(tǒng)采用

操作系統(tǒng)保留空閑幀列表

發(fā)生頁面錯誤時，將空閑幀添加到駐留的進程集

課本224全局頁面替換策略和229局部頁面替換策略

11.3.3. 變量分配，本地范圍

分配給進程的幀數(shù)是可變的

從分配給過程的框架中選擇要替換的頁面

添加新流程后，請根據(jù)應(yīng)用程序類型，程序請求或其他條件分配頁框數(shù)量

發(fā)生頁面錯誤時，請從發(fā)生故障的進程的常駐集中選擇頁面。

不時重新評估分配

11.4. 缺頁中斷率

頁面調(diào)度算法設(shè)計不當，會出現(xiàn)(剛淘汰的頁面立即又要調(diào)入，并如此反復(fù))，這種現(xiàn)象稱為抖動或顛簸，主要原因是內(nèi)存中同時運行的進程太多，而分配給每個進程的頁框太少。

假定進程$P$共有$n$頁，系統(tǒng)分配頁架數(shù)$m$個

$P$運行中成功訪問次數(shù)為$S$，不成功訪問次數(shù)為$F$，總訪問次數(shù)$A=S+F$

缺頁中斷率定義為: $f=\frac{F}{A}$

缺頁中斷率是衡量存儲管理性能和用戶編程水平的重要依據(jù)

11.4.1. 缺頁中斷率的影響因素

分配給進程的頁框數(shù)：可用頁框數(shù)越多，則缺頁中斷率就越低

頁面的大小：頁面尺寸越大，則缺頁中斷率就越低

頁面替換算法：算法的優(yōu)劣影響缺頁異常次數(shù)

程序特性：程序局部性要好，它對缺頁中斷率有很大影響。

11.4.2. 用戶編程的例子

不同的訪問方式會到導(dǎo)致出現(xiàn)缺頁情況的。

11.5. 全局頁面替換策略

11.5.1. OPT頁面調(diào)度算法(Belady算法)

算法描述：當要調(diào)入新頁面時，首先淘汰以后不再訪問的頁，然后選擇距現(xiàn)在最長時間后再訪問的頁。

該方法由Belady提出，稱為BeLady算法，又稱最佳算法(OPT)

OPT只可以模擬，不可以實現(xiàn)，因為永遠無法預(yù)知之后的事情。

這種算法可以用作衡量其他各種算法的標準。

11.5.2. 先進先出頁面調(diào)度算法(FIFO)

算法描述：首先淘汰最先調(diào)入主存的那一頁，或者說主存駐留時間最長的那一頁(常駐的除外)

模擬的是程序執(zhí)行的順序性，有一定合理性，并不能很好模擬程序的循環(huán)性。

根據(jù)估計，缺頁中斷率也是最佳算法的2-3倍。

FIFO算法的Belady異常：更多的頁框?qū)е铝烁叩娜表撀?#xff0c;頁框為3和4的時候

11.5.3. 頁面緩沖算法

頁面緩沖算法是對FIFO替換算法的一種改進

算法策略

系統(tǒng)維護兩個FIFO隊列，被替換的頁面添加到如下兩個隊列中

修改頁面隊列

非修改(空閑)頁面隊列

替換的頁面仍保留在內(nèi)存中

如果再次引用，則找回的費用很少

當修改頁面隊列中的頁面到達一定數(shù)量后，頁面以群集形式寫回磁盤，并把空閑頁框加入非修改頁面隊列尾部。

11.5.4. 最近最少用LRU頁面調(diào)度算法

淘汰最近一段時間較久未被訪問的那一頁，即那些剛被使用過的頁面，可以馬上還要被使用到。

模擬了程序執(zhí)行的局部屬性，既考慮了循環(huán)性，又兼顧了順序性

嚴格實現(xiàn)的代價大(需要維持特殊隊列——頁面淘汰隊列)，實現(xiàn)需要硬件支持。

LRU算法得到模擬實現(xiàn)：模擬是相當?shù)牟粐乐?#xff0c;非常粗粒度的一個模擬。

引用位法：每頁建立一個引用標志，供硬件使用，設(shè)置一個時間間隔中斷，發(fā)生時將頁引用標志置0，訪問頁面時將引用標志置為1，頁面置換的時候選擇標志為0的頁面，在選中淘汰頁時，將所有的頁的引用為全部置為0

計數(shù)法：每頁添加頁面引用計數(shù)器，根據(jù)計數(shù)器選擇最小的，定時清空頁面引用計數(shù)器

計時法：每頁添加計時單元，引用時，將絕對時間記錄進入計時單元，定時清空計時單元。

老化算法：設(shè)置一個多位寄存器，被訪問將最左側(cè)設(shè)置為1，定時將寄存器右移，缺頁中斷時找到最小值的寄存器界面淘汰，被采用較多。

上圖使用老化算法

T3時刻替換P2頁面，因為和P1他們在3時刻都沒有被訪問，但是2時刻P1被訪問了

11.5.5. 第二次機會頁面替換算法(SCR，Second Chance Replacement)

將FIFO算法和頁表中引用位結(jié)合。

算法描述：

首先檢查FIFO頁面隊列隊首

引用位為0，則淘汰該頁面

引用位為1，將引用位清0，并將該頁面移到隊列尾部

如果第一遍全為1，則循環(huán)

11.5.6. 最不常用LFU的頁面調(diào)度算法

淘汰最近一段時間內(nèi)訪問次數(shù)較少的頁面，對OPT的模擬性比LRU更好

算法過程：基于時間間隔中斷，并給每一頁設(shè)置一個計數(shù)器，時間間隔中斷發(fā)生后，所有計數(shù)器清0，每訪問頁1次就給計數(shù)器加1，選擇計數(shù)最小的頁面淘汰

11.5.7. 時鐘CLOCK頁面調(diào)度算法

CLOCK就是SCR結(jié)合FIFO形成循環(huán)，使用頁引用標志位。

算法描述：采用循環(huán)隊列機制構(gòu)造頁面隊列，形成了一個類似鐘表面的環(huán)形表，隊列指針則相當于鐘表面上的表針，指向可能要淘汰的頁面

11.5.7.1. CLOCK算法的工作流程

頁面調(diào)入主存時，其引用標志位置為1

訪問主存頁面時，其引用標志位置為1

淘汰頁面時，從指針當前指向的頁面開始掃描循環(huán)隊列

把所遇到的引用標志位是1的頁面的引用標志位清0并跳過

把所遇到的引用標志位是0的頁面淘汰，指針推進一步

11.5.7.2. CLOCK算法的例子

灰色和星號代表1，藍色和無星號代表0

發(fā)生命中，指針不動

指針運動是為了尋找替換的頁

1->5其實是循環(huán)一輪，如果為1，指針不替換，但是會將標志位置為0

當一頁被替換時，指向下一幀。雖然早就進來，但是最近使用過，所以不急著替換

當需要替換一頁時，掃描緩沖區(qū)，查找使用位被置為0的一幀。

每當遇到一個使用位為1的幀時，就將該位重新置為0；

如果在這個過程開始時，所有幀的使用位均為0，選擇遇到的第一個幀替換；

如果所有幀的使用位為1，則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁。

11.5.7.3. 第三次機會時鐘替換算法：結(jié)合引用位和修改位

一共四種情況：r是引用位，m是修改位

最近未被引用，未被修改：r=0，m=0

最近被引用，未被修改：r=1，m=0

最近未被引用，被修改：r=0，m=1

最近被引用，被修改：r=1，m=1

算法描述

掃描，不修改引用位，找到第一個r=0，m=0的頁面替換

如果1沒有找到，則從原位置開始，修改引用位，查找r=0，m=1的頁面替換寫回

如果2沒有找到，重復(fù)1或2操作。

11.5.8. 不同算法性能比較

整體上來講FIFO > CLOCK > LRU > OPT

11.6. 局部頁面替換算法(不考)

P229-233

11.6.1. 局部最佳頁面替換算法(MIN)

實現(xiàn)思想：進程在時刻t訪問某頁面，如果該頁面不在主存中，導(dǎo)致一次缺頁，把該頁面裝入一個空閑頁框

不論發(fā)生缺頁與否，算法在每一步要考慮引用串，如果該頁面在時間間隔(t, t+τ)內(nèi)未被再次引用，那么就移出；否則，該頁被保留在進程駐留集中

t為一個系統(tǒng)常量，間隔(t, t+τ)稱作滑動窗口 。例子中τ=3，雙閉區(qū)間

11.6.2. 工作集模型和工作集置換算法(WS)

進程工作集指"在某一段時間間隔內(nèi)進程運行所需訪問的頁面集合"

實現(xiàn)思想：工作集模型用來對局部最佳頁面替換算法進行模擬實現(xiàn)，不向前查看頁面引用串，而是基于程序局部性原理向后看

任何給定時刻，進程不久的將來所需主存頁框數(shù)，可通過考查其過去最近的時間內(nèi)的主存需求做出估計

11.6.2.1. 進程工作集

指"在某一段時間間隔內(nèi)進程運行所需訪問的頁面集合"，W(t，Δ)表示在時刻t-Δ到時刻t之間( (t-Δ，t))所訪問的頁面集合，進程在時刻t的工作集

Δ是系統(tǒng)定義的一個常量。變量Δ稱為"工作集窗口尺寸"，可通過窗口來觀察進程行為，還把工作集中所包含的頁面數(shù)目稱為"工作集尺寸"

Δ=3

11.6.2.2. 示例

工作集:程序在運行過程時，程序的局部性是變更的。有的部分是比較陡的，大量調(diào)入，然后平穩(wěn)期，訪問替換進來的頁們。

11.6.3. 模擬工作集替換算法

11.6.4. 缺頁頻率替換算法

定義頁面錯誤率的上限U和下限L。

如果缺頁率高于U，則為進程分配更多頁框。

如果缺頁率低于U，則為進程分配更少頁框。

駐留集的大小應(yīng)該和工作集大小W緊密相關(guān)的。

如果PFF(缺頁率)>U并且沒有更多可用幀，我們將暫停該過程，ROI(Return On Investment)

頁框的大小是需要根據(jù)程序動態(tài)調(diào)整的。

11.6.5. 通過工作集確定駐留集大小

監(jiān)視每個進程的工作集，只有屬于工作集的頁面才能留在主存；

定期地從進程駐留集中刪去那些不在工作集中的頁面；

僅當一個進程的工作集在主存時，進程才能執(zhí)行。

12. 段式虛擬存儲管理

12.1. 段式虛擬存儲管理的基本思想

把進程的所有分段都存放在輔存中，進程運行時先把當前需要的一段或幾段裝入主存，在執(zhí)行過程中訪問到不在主存的段時再把它們動態(tài)裝入

段式虛擬存儲管理中段的調(diào)進調(diào)出是由OS自動實現(xiàn)的，對用戶透明

與段覆蓋技術(shù)不同，它是用戶控制的主存擴充技術(shù)，OS不感知

12.2. 段式虛擬存儲管理的段表擴充

段表的擴充

特征位: 00(不在內(nèi)存)01(在內(nèi)存)11(共享段)

存取權(quán)限: 00(可執(zhí)行)01(可讀)11(可寫)

擴充位: 0(固定長)1(可擴充)

標志位: 00(未修改)01(已修改)11(不可移動)

12.3. 段式虛擬存儲管理的地址轉(zhuǎn)換

13. 段頁式虛擬存儲管理

13.1. 段頁式虛擬存儲基本原理

虛地址以程序的邏輯結(jié)構(gòu)劃分為段，這是段頁式的段式特征。

實地址劃分層位置固定、大小相同的頁框(塊)，這是段頁式的頁式特征。

將每一段的線性地址空間劃分成與頁框大小相同的頁面，段頁式的特征

邏輯地址由段號s、段內(nèi)頁號p和頁內(nèi)偏移d組成

對用戶，虛擬地址由段號s和段內(nèi)位移d’組成

系統(tǒng)內(nèi)部將d’分解為p和d，d’ = p * 塊長 + d

請求段頁式虛擬存儲管理的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜，包含作業(yè)表、段表和頁表三部分。

作業(yè)表：進入系統(tǒng)的作業(yè)和作業(yè)段表的起始地址

段表：是否在內(nèi)存、段頁表起始地址

頁表：是否在內(nèi)存、對應(yīng)內(nèi)存塊號

13.2. 段頁式虛擬存儲管理的地址轉(zhuǎn)換

14. 存儲管理方案以及虛存頁面替換算法小結(jié)

15. 補充：關(guān)于快表問題

有效位為0，不指引

Valid并不全表示頁表項是否在主存中

發(fā)生頁面替換的時候，被替換的頁如果在快表中，則其的valid位置0或者將該頁刪除。

16. Linux虛擬存儲管理

16.1. 伙伴系統(tǒng)(一種算法)

伙伴系統(tǒng)(Knuth，1973)，又稱buddy算法，是一種固定分區(qū)和可變分區(qū)折中的主存管理算法

基本原理是：任何尺寸為$2^i$的空閑塊都可被分為兩個尺寸為$2^{i?1}$的空閑塊，這兩個空閑塊稱作伙伴，它們可以被合并成尺寸為$2^i$的原先空閑塊。

伙伴通過對大塊的物理主存劃分而獲得

假如從第0個頁面開始到第3個頁面結(jié)束的主存

每次都對半劃分，那么第一次劃分獲得大小為2頁的伙伴，如0、1和2、3

進一步劃分，可以獲得大小為1頁的伙伴，例如0和1，2和3

16.1.1. 例子：類似二叉樹的形式進行分配

16.1.2. Linux伙伴系統(tǒng)

以page結(jié)構(gòu)為數(shù)組元素的mem_map[]數(shù)組

以free_area_struct結(jié)構(gòu)為數(shù)組元素的free_area數(shù)組

位圖數(shù)組(bitmap)

16.1.2.1. Linux基于伙伴的slab分配器

為什么要使用slab分配器?

伙伴系統(tǒng)以頁框為基本分配單位，內(nèi)核在很多情況下，需要的主存量遠遠小于頁框大小，如inode、vma、task_struct等，為了更經(jīng)濟地使用內(nèi)核主存資源，引入SunOS操作系統(tǒng)中首創(chuàng)的基于伙伴系統(tǒng)的slab分配器，其基本思想是：為經(jīng)常使用的小對象建立緩存，小對象的申請與釋放都通過slab分配器來管理，僅當緩存不夠用時才向伙伴系統(tǒng)申請更多空間。//頁內(nèi)可以按2的冪次拆分。

優(yōu)點：充分利用主存，減少內(nèi)部碎片，對象管理局部化，盡可能少地與伙伴系統(tǒng)打交道，從而提高效率。

slab的結(jié)構(gòu)

struct slab{struct list_head; // slab滿、半滿或空閑鏈表unsigned long colouoff; //slab著色偏移量void * s_mem; //slab的第一個對象unsigned int inuse; //已分配的對象數(shù)kmem_bufctl_t free; //第一個空閑對象 }

slab的操作

16.1.2.2. slab分配器主要操作

kmem_cache_create()函數(shù)：創(chuàng)建專用cache，規(guī)定對象的大小和slab的構(gòu)成，并加入cache管理隊列；

kmem_cache_alloc()與kmem_cache_free()函數(shù)：分別用于分配和釋放一個擁有專用slab隊列的對象；

kmem_cache_grow()與kmem_cache_reap()函數(shù)：

kmem_cache_grow()它向伙伴系統(tǒng)申請向cache增加一個slab

kmem_cache_reap()用于定時回收空閑slab

kmem_cache_destroy()與kmem_cache_shrink()：用于cache的銷毀和收縮；

kmalloc()與kfree()函數(shù)：用來從通用的緩沖區(qū)隊列中申請和釋放空間；

kmem_getpages()與kmem_freepages()函數(shù)：slab與頁框級分配器的接口，當slab分配器要創(chuàng)建新的slab或cache時，通過kmem_getpages()向內(nèi)核提供的伙伴算法來獲得一組連續(xù)頁框。如果釋放分配給slab分配器的頁框，則調(diào)用kmem_freepages()函數(shù)。

總結(jié)

以上是生活随笔為你收集整理的计算机操作系统-3-存储管理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。