在學習作業系統時總結了筆記，并分享出來，特别是藍色和紅色字型。有問題請及時聯系部落客：Alliswell_WP，轉載請注明出處。
參考書：《作業系統》谌衛軍等，清華大學出版社，2012年5月
參考視訊：清航全套計算機專業課視訊
目錄
第四章 存儲管理
1.單道程式存儲管理
2.分區存儲管理
3.頁式和段式存儲管理
4.覆寫技術和交換技術
5.虛拟存儲技術
第四章 存儲管理
1.單道程式存儲管理
理想中的存儲器：更大、更快、更便宜的非易失性存儲器。
實際中的存儲器？
存儲管理？一般講的是記憶體
-記憶體分為兩個區域：系統區，使用者區。每次把一個應用程式裝入到使用者區運作，由它和作業系統來共享記憶體。當它運作結束後，作業系統再裝入一個新的程式把它覆寫；
-優點：簡單、開銷小，易于管理；
-适合于單使用者、單任務的OS。
缺點？
-每次隻能運作一個程式
-記憶體資源的使用效率不高——程式較小時，會浪費大量的記憶體空間
-OS的保護——應用程式的bug會破壞OS
-位址空間有限——即為實體記憶體的大小
2.分區存儲管理
-記憶體分為兩大區域：系統區，使用者區。又把使用者區劃分為若幹分區(partition)。一個程序占用一個分區。
-特點：适合多道程式系統和分時系統，支援多個程式并發執行。
固定分區存儲管理：各個使用者分區的個數、位置和大小一旦确定以後，就固定不變。
分區的大小是否相等?
-程式大小不同
-多個小分區、适量的中等分區、少量大分區
程序個數多于分區個數?
-輸入隊列
固定分區的缺點：
-記憶體使用率不高，内碎片造成很大浪費。所謂内碎片，即程序所占用分區之内的未被利用的空間。
-分區的總數固定，限制了并發執行的程式個數，不夠靈活。
-位址空間的大小有限。
-如何确定分區的大小?
可變分區(動态分區)
-初始時，作業系統會占用記憶體的一部分，其餘空間為一個完整的大空閑區
-當一個程式要求裝入記憶體運作時，系統從這個空閑區中劃一塊配置設定給它
-當程式完成後釋放所占用的存儲區
-随着一系列的記憶體配置設定和回收，原來的一整塊大空閑區就形成了若幹占用區和空閑區相間的布局。
可變分區的特點：
-分區的個數、位置和大小都是随程序的進出而動态變化的，非常靈活，避免了在固定分區中因分區大小不當所造成的内碎片，提高了記憶體使用率。
-有外碎片，即各個占用分區之間難以利用的空閑分區。
-使得記憶體的配置設定、回收和管理更為複雜。
如何實作可變分區的存儲管理技術?
1)記憶體管理的資料結構；
2)記憶體的配置設定算法
3)記憶體的回收方法
4)碎片問題
分區配置設定算法：當一個新程序到來時，需為它尋找某個空閑分區，其大小必須大于或等于該程序的要求。若大于要求，則将該分區分割成兩個分區，其中一個分區為要求大小并标記為“占用”，另一個分區為餘下部分并标記為“空閑”。
分區配置設定算法主要有：最先比對法、下次比對法、最佳比對法、最壞比對法。
地扯映射(重定位)
1)實體位址
-也叫記憶體位址、絕對位址，實位址；
-把記憶體分成很多個大小相等的存儲單元，每個單元給一個編号，這個編号稱為實體位址：
-實體位址可以直接尋址；
-實體位址的集合稱為實體位址空間(記憶體位址空間)，它是一個一維的線性空間。
2)邏輯位址
-也叫相對位址，虛位址；
-使用者程式經彙編或編譯後形成目标代碼，目标代碼通常采用相對位址的形式，其首位址為0，其餘指令中的位址都是相對首位址來編址；
-不能用邏輯位址在記憶體中讀取資訊。
3)位址映射
-為保證CPU執行指令時可正确通路存儲單元，需将使用者程式中的邏輯位址轉換為運作時由機器直接尋址的實體位址，此過程稱為位址映射。
為了保證CPU執行指令時可正确通路存儲單元，在裝入程式時必須進行位址映射，将程式中的邏輯位址轉換為實體位址。這主要有兩種方式：
靜态位址映射(靜态重定位)：當使用者程式被裝入記憶體時，直接對指令代碼進行修改，一次性實作邏輯位址到實體位址的轉換。
動态位址映射(動态重定位)：當使用者程式被裝入記憶體時，不對指令代碼做任何修改。而是在程式運作過程中，當需要通路記憶體單元時再來進行位址轉換(即在逐條執行指令時完成轉換)。
-由硬體位址映射機制完成，如設定一個基位址寄存器，并裝入程序所在分區起始位址；
-在程式運作時，硬體自動完成位址映射。
答案：1)在CPU中，隻有1個；2)準備運作時裝入值
存儲保護
為了防止一個使用者程式去通路其他使用者程式的記憶體分區，保護作業系統免受使用者程式的破壞，須進行存儲保護。
如何實作?
能否與動态位址映射內建在一起?
擴充：記憶體中的程式執行
程序的位址空間，記憶體布局是什麼樣的？
1 /*全局變量，固定位址，其他源檔案可見*/
2 int global_static;
3 /*靜态全局更量，固定位址，但隻在本檔案中可見*/
4 static int file_static;
5 /*函數參數：位于棧幀當中，動态建立，動态釋放*/
6 int foo(int auto_param)//代碼
7 {
8 /*靜态局部變量，固定位址，隻在本函數中可見*/
9 static int func_static;
10 /*普通局部變量，位于棧幀當中，隻在本函數可見*/
11 int auto_i, auto_a[10];
12 /*動态申請的記憶體空間，位于堆當中*/
13 double *auto_d=malloc(sizeof(double)*5)；
14 return auto_i;
15 } 各部分分别存儲哪些？
資料段：全局變量；堆空間：malloc；棧：靜态局部變量、普通局部變量、函數參數
3.頁式和段式存儲管理
分區存儲管理的特性
-連續性，這将會導緻碎片問題(内碎片和外碎片)
-一個例子：容器配置設定方案。總容量固定，每一種物品的重量不定，且不能混合。
頁式存儲管理
1)基本原理
-把實體記憶體劃分為許多個固定大小的記憶體塊，稱為實體頁面，或頁框(page frame)
-把邏輯位址空間劃分為大小相同的塊，稱為邏輯頁面，或簡稱頁面(page)；
-頁面大小為20，一般在512位元組到8K位元組之間；
-當一個使用者程式裝入記憶體時，以頁面為機關進行配置設定。若要運作一個大小為n個頁面的程式，需要有n個空閑的實體頁面把它裝入，這些頁面不必是連續的。
頁式存儲管理要解決如下問題：
-用于存儲管理的資料結構是什麼?
-當一個程序到來時，如何給它配置設定記憶體?
-當一個程序運作結束，釋放它所占用的記憶體空間後，如何回收記憶體?
-當一個程序被加載到記憶體以後，它如何正确運作(位址重定位)?
資料結構
-每個邏輯頁面存放在哪一個實體頁面中？
-實體記憶體的管理？
存儲：數組int pagetable[N]
一個例子：
記憶體的配置設定與回收算法與實體頁面表的具體實作方法有關。這裡以位示圖為例。
記憶體的配置設定：
-計算一個程序所需要的頁面數N，并檢視位示圖，看是否還有N個空閑頁面；
-若有，則申請一個頁表，其長度為N，并把頁表的起始位址填入PCB；
-配置設定N個空閑實體頁面，将其編号填入頁表；
-修改位示圖(0→1，空閑頁面數一N)
記憶體的回收：當一個程序運作結束，釋放它所占用的記憶體空間後，需要對這些實體頁面進行回收。
-對于每一個實體頁面，根據它的編号計算出它在位示圖當中的相應位置，并将相應位的值從1改成0；
-修改位示圖中的空閑頁面數：加上N。
位址映射
為什麼要進行位址映射?
一個程序的各個連續的邏輯頁面，被分散地裝入到記憶體的各個實體頁面當中，在這種情形下，怎樣才能保證程式能夠正确地運作？
問題描述：輸入邏輯位址，輸出實體位址。
(1)對于給定的邏輯位址，找到邏輯頁面号和頁内偏移位址；
(2)查找頁表，找到相應的實體頁面号；
(3)計算最終的實體位址。
頁表的具體實作
頁表儲存在記憶體當中(使用者/核心空間？)；頁表在作業系統的資料區。
-設定一個頁表基位址寄存器(Page-table base register,PTBR)，用來指向頁表的起始位址；
-設定一個頁表長度寄存器(Page-table length register,PTLR)，訓示頁表大小。
1)硬體寄存器位于什麼地方? MMU中
2)其内容何時更新?誰更新?如何更新? 程序切換時更新，由作業系統更新，從記憶體的PCB表去填充
備注：邏輯頁面号和偏移的分離，取頁表，疊加都是硬體MMU完成，頁表中的内容填充，寄存器中内容的填充是CPU完成，使用者程式不做任何事情。
先取出邏輯頁面号，然後去通路頁表，頁表中有頁表基位址寄存器(裡邊有頁表的起始位址)，如同用數組下标去通路數組，得到實體頁面号，去和頁面偏移疊加，就得到實體位址，進而通路資料。
問題：1)需通路幾次記憶體？兩次：一次通路頁表(記憶體中)，一次通過實體位址去記憶體資料
2)頁表需不需要提前通路記憶體？不需要，頁表基位址寄存器有實體位址(裡邊有頁表的起始位址)
如何加快頁表的查詢速度?
在現有的方案中，每一次通路記憶體(資料/指令)時，都要做兩次通路記憶體的工作。這樣，降低了存取速度，将會影響整個系統的使用效率。
為縮短頁表的查找時間，可以采用一種特殊的快速查找硬體：TLB(Translation Lookaside Buffer)或稱associative memory,用來存放那些最常用的頁表項。
優缺點
優點：
-沒有外碎片，内碎片的大小不超過頁面的大小；
-一個程式不必連續存放；
-便于管理；
缺點：
-程式必須全部裝入記憶體；
-系統必須為每個程序維護一張頁表。
Why段式存儲管理?
頁式存儲管理(和分區存儲管理)隻有一個邏輯位址空間，即一維的線性連續空間，從0到某個最大的邏輯位址。但是從程式員或系統管理的角度來說，一個程式是由一組子產品(片段)所組成的，每個片段是一個邏輯單元，如：主程式、全局變量、棧、庫函數等。
基本原理
-對程式的每個邏輯單元(代碼、資料和棧等)，設立一個完全獨立的位址空間，稱為“段”。每個段的内部是一維的線性連續位址，大小可不同；
-對于實體記憶體來說，采用可變分區(動态分區)的管理方法；
-當一個程式需要裝入記憶體時，以段為機關進行配置設定，把每一個段裝入到一個記憶體分區當中，這些記憶體分區不必是連續的。
具體實作
-在段式存儲管理中，使用者空間位址為二維位址：(段号，段内偏移)。實作方式：(1)位址高端為段号、低端為偏移；(2)指令中顯式地給出段号和段内偏移。
-段表：系統為每一個程序都建立了一個段表，它給出了程序當中的每一個段與它所對應的記憶體分區之間的映射關系。
如何實作？結構體數組
段表的具體實作：
-段表儲存在記憶體當中；
-設定一個段表基位址寄存器(Segment-table base register,STBR)，用來指向記憶體當中段表的起始位址；
-設定一個段表長度寄存器(Segment-table length register，STLR)，用來訓示段表的大小，即程式當中的段的個數；
問題1)硬體寄存器位于什麼地方? MMU中
2)其内容何時更新?誰更新?如何更新? 程序切換時更新，由作業系統更新，從記憶體的PCB表去填充
優缺點
優點：
-程式通過分段來劃分多個子產品，每個子產品可以分别編寫和編譯，可以針對不同類型的段采取不同的保護，可以按段為機關來進行共享；
-一個程式不必連續存放，沒有内碎片。
缺點：
程式必須全部裝入記憶體、外碎片等。
段式存儲和頁式存儲各有特點：
-段式存儲管理為使用者提供了一個二維的邏輯位址空間，可以滿足程式和資訊的邏輯分段要求，反映了程式的邏輯結構，有利于段的共享、保護和動态增長；
-頁式存儲管理的特征是等分記憶體，它有效地克服了碎片問題，提高了記憶體的使用率。
為了保持頁式在存儲管理上的優點和段式在邏輯上的優點，人們又提出了段頁式存儲管理技術。
4.覆寫技術和交換技術
過時不講！
5.虛拟存儲技術
在計算機系統中，尤其是在多道程式環境下，可能會出現記憶體不夠用的情況，包括三種情形：
-程式太大，超過了記憶體的容量；
-程式太多，超過了記憶體的容量；
-程式太多，且單個程式太大。
大變活人，類比。盒子類似記憶體，桌子類似硬碟，每次鑽出一人進入盒子，類似記憶體很小，每次調用一個程式
前提：任何時候，一個程式在運作時隻有一小段會被用到，大部分還在硬碟。
這個前提是否存在？程式的局部性原理。
局部性原理(principle of locality)：程式在執行過程中的一個較短時期，所執行的指令位址和指令的操作數位址，分别局限于一定區域。
局部性原理的具體表現：
-程式在執行時，大部分是順序執行的指令，少部分是轉移和過程調用指令；
-程式中存在相當多的循環結構，它們由少量指令組成，而被多次執行；
-程式中存在很多對一定資料結構的操作，如數組操作，往往局限在較小範圍内。
程式的局部性原理表明，從理論上來說，虛拟存儲技術是能夠實作的，而且在實作了以後應該是能夠取得一個滿意的效果的。
成功案例：TLB、Cache。
虛拟頁式存儲管理
太部分虛拟存儲系統都采用虛拟頁式存儲管理技術，即在頁式存儲管理的基礎上，增加請求調頁和頁面置換功能。
基本思路：
當一個使用者程式要調入記憶體運作時，不是将該程式的所有頁面都裝入記憶體，而是隻裝入部分的頁面(0或多個)，就可啟動程式運作。在運作的過程中，如果發現要執行的指令或要通路資料不在記憶體，則發出缺頁中斷請求，系統在處理這個中斷時，将外存中相應的頁面調入記憶體，使得該程式能繼續運作。
-當記憶體空間不夠用時，需要把頁面儲存在磁盤上(backing store，後備存儲)；
-記憶體實體頁面稱為page frame，磁盤上的頁面稱為後備頁面(backing frame)；
-目的：提供一種錯覺，記憶體的容量好像和磁盤容量一樣大，且速度和記憶體一樣快(理想狀态)。
虛拟頁式管理需要解決以下問題：
1)如何發現執行的代碼或通路的資料不在記憶體；
2)代碼或資料什麼時候調入記憶體，調入政策；
3)當一些頁調入記憶體時，記憶體沒有空閑記憶體時，将淘汰哪些頁，淘汰政策。
駐留位(有效位)：表示該頁是否在記憶體。若該位為1，表示該頁位于記憶體中，即該頁表項有效，可以使用；若該位為0，表示該頁目前還在外存中，此時若通路該頁表項，将導緻缺頁中斷；
保護位：表示允許對該頁做何種類型的通路，如隻讀、可讀寫、可執行等；
修改位：表明此頁在記憶體中是否被修改過。當系統回收該實體頁面時，根據此位來決定是否把它的内容寫回外存；
通路位：如果該頁面被通路過(包括讀操作或寫操作)，則設定此位。用于頁面置換算法。
思考問題：哪些位是CPU寫OS讀？哪些位是OS寫CPU讀？ CPU寫OS讀：修改位、通路位；OS寫CPU讀：駐留位、保護位
問題：邏輯位址為0的實體位址是多少？劃分頁号(0)和頁面偏移(0)，通過頁号(0)在頁表找到2，對應實體位址為：2*4K+偏移(0)=8K=8192
問題：邏輯位址為32780的實體位址是多少？劃分頁号(32780/4K=8)和頁面偏移(32780%4K=12)，通過頁号(8)在頁表查找，為X，說明頁面未在記憶體，這時候通路出現缺頁中斷。
在位址映射過程中，如果所要通路的邏輯頁面p不在記憶體，則産生缺頁中斷(page fault)。中斷處理過程：
1)如果在記憶體中有空閑的實體頁面，則配置設定一頁，設為f，然後轉第4步；否則轉第2步；
2)采用某種頁面置換算法，選擇一個将被替換的實體頁面f，它所對應的邏輯頁面為p'。如果該頁在記憶體期間被修改過，則需把它寫回外存(Where?)；
-對p'所對應的頁表項進行修改，把駐留位置為0；
-将需要通路的頁面p裝入到實體頁面f當中(程序被阻塞)，并修改p所對應的頁表項的内容，把駐留位置為1，把實體頁面号設定為f；
-重新運作被中斷的指令(PC不變)。
缺頁中斷由MMU發出，作業系統進行中斷。
頁面置換算法
功能：當缺頁中斷發生，需要調入新的頁面而記憶體已滿時，選擇記憶體當中哪個實體頁面被置換。
目标：盡可能地減少頁面的換進換出次數(即缺頁中斷的次數)。可把未來不再使用的或短期内較少使用的頁面換出。
-最優頁面置換算法(OPT，optimal)——理想情況
-最近最久未使用算法(LRU，Least Recently Used)——看時間
-最不常用算法(LFU,Least Frequently Used)——看次數
-先進先出算法(FIFO)
-時鐘頁面置換算法(Clock)——FIFO+跳過通路過的頁面
工作集——統計了局部性原理的有效性。
頁表結構
在虛拟存儲技術中，虛拟記憶體空間往往大于實際的實體記憶體，現代計算機所使用的虛拟位址至少為32位，若每個頁面的大小為4K，則邏輯頁面的個數為220，即在頁表裡有220個頁表項，而每個程序都有自己的虛拟位址空間。都需要自己的頁表，因而占用了大量的記憶體空間。為解決此問題，需提出新的頁表結構：
-多級頁表(Multilevel Page Tables)；
-反置頁表((lnverted Page Tables)。
多級頁表
由于不是所有的虛拟位址都會用到，是以不必把所有的頁表項都儲存在記憶體當中。以二級頁表為例：
·假設邏輯位址為32位，頁面大小為4K。把邏輯位址劃分為兩個部分：
-邏輯頁面号為20位
-頁内偏移位址為12位
·把邏輯頁面号再進一步地劃分為兩個部分：
-10位的字段PT1，用來指向第一級頁表當中所對應的頁表項
-10位的字段PT2，用來指向第二級頁表當中所對應的頁表項