3.1 記憶體的基礎知識

3.1.1 什么是記憶體，有何作用

1. 記憶體：用于存放資料的硬體，程式執行前需要先放到記憶體中才能被CPU處理，
2. 存盤單元
   1. 記憶體地址從0開始,每個地址對應個存盤單元
   2. 記憶體中也有一個一個的“小房間”，每個小房間就是一個“存盤單元”
   3. 如果計算機“按位元組編址”則每個存盤單元大小為1位元組，即1B，即8個二進制位
   4. 如果字長為16位的計算機“按字編址”，則每個存盤單元大小為1個字；每個字的大小為16個二進制位
   5. 一臺手機/電腦有4GB記憶體，是什么意思?
      1. 是指該記憶體中可以存放4*230個位元組，如果是按位元組編址的話，也就是有4*230 = 232個“小房間”
3. 記憶體地址

3.1.2 行程運行的基本原理

1. 指令的作業原理
   1. 我們寫的代碼要翻譯成CPU能識別的指令，這些指令會告訴CPU應該去記憶體的哪個地址存/取資料，這個資料應該做什么樣的處理，在這個例子中，指令中直接給出了變數x的實際存放地址（物理地址)，但實際在生成機器指令的時候并不知道該行程的資料會被放到什么位置，所以編譯生成的指令中一般是使用邏輯地址（相對地址)
2. 邏輯地址VS物理地址
   1. 指令中的地址也可以采用這種思想，編譯時產生的指令只關心“相對地址”，實際放入記憶體中時再想辦法根據起始位置得到“絕對地址”，
   2. Eg：編譯時只需確定變數x存放的相對地址是100（也就是說相對于行程在記憶體中的起始地址而言的地址），CPU想要找到x在記憶體中的實際存放位置，只需要用行程的起始地址+100即可，
   3. 相對地址又稱邏輯地址，絕對地址又稱物理地址，
3. 從寫程式到程式運行：編輯--編譯--鏈接--裝入
   1. 編譯:由編譯程式將用戶源代碼編譯成若干個目標模塊（編譯就是把高級語言翻譯為機器語言)
   2. 鏈接:由鏈接程式將編譯后形成的一組目標模塊，以及所需庫函式鏈接在起，形成一個完整的裝入模塊
   3. 裝入（裝載）:由裝入程式將裝入模塊裝入記憶體運行
   4. 

4. 三種鏈接方式
   1. 靜態鏈接：在程式運行之前，先將各目標模塊及它們所需的庫函式連接成一個完整的可執行檔案（裝入模塊）,之后不再拆開，
   2. 裝入時動態鏈接：將各目標模塊裝入記憶體時，邊裝入邊鏈接的鏈接方式，
   3. 運行時動態鏈接：在程式執行中需要該目標模塊時，才對它進行鏈接，其優點是便于修改和更新，便于實作對目標模塊的共享，
5. 三種裝入方式
   1. 絕對裝入---（只適用于單道程式環境）
      1. 絕對裝入:在編譯時，如果知道程式將放到記憶體中的哪個位置，編譯程式將產生絕對地址的目標代碼，裝入程式按照裝入模塊中的地址，將程式和資料裝入記憶體，
   2. 靜態重定位---（早期的多道批處理系統）
      1. 靜態重定位:又稱可重定位裝入，編譯、鏈接后的裝入模塊的地址都是從0開始的，指令中使用的地址、資料存放的地址都是相對于起始地址而言的邏輯地址，可根據記憶體的當前情況，將裝入模塊裝入到記憶體的適當位置，裝入時對地址進行“重定位”，將邏輯地址變換為物理地址（地址變換是在裝入時一次完成的），
   3. 動態重定位----（現代作業系統）
      1. 動態重定位:又稱動態運行時裝入，編譯、鏈接后的裝入模塊的地址都是從0開始的，裝入程式把裝入模塊裝入記憶體后，并不會立即把邏輯地址轉換為物理地址，而是把地址轉換推遲到程式真正要執行時才進行，因此裝入記憶體后所有的地址依然是邏輯地址，這種方式需要一個重定位暫存器的支持，（允許程式在記憶體中移動）

3.2 記憶體管理的概念

作業系統作為系統資源的管理者，當然也需要對記憶體進行管理，要管些什么呢?

作業系統要怎么記錄哪些記憶體區域已經被分配出去了,哪些又還空閑?

當行程運行結束之后，如何將行程占用的記憶體空間回收?

很多位置都可以放,那應該放在哪里?

1. 記憶體空間的分配與回收
   1. 連續分配管理方式
      1. 單一連續分配
      2. 固定連續分配
         1. 磁區大小相等
         2. 磁區大小不等
      3. 動態磁區分配
   2. 非連續分配管理方式
      1. 基于分頁存盤管理
      2. 基于分段存盤管理
      3. 段頁式存盤管理
2. 記憶體空間的擴充
   1. 覆寫技術
   2. 交換技術
   3. 虛擬存盤技術
3. 地址轉換
   1. 作業系統負責實作邏輯地址到物理地址的轉換
   2. 三種方式：
      1. 絕對裝入
      2. 可重定位裝入
      3. 動態運行時裝入
4. 存盤保護
   1. 各個行程只能訪問自己行程對應的記憶體空間，而不能訪問作業系統或其他行程的記憶體空間，
   2. 保證各行程在自己的記憶體空間運行，不能越界訪問，
   3. 方法一：在CPU中設定一對上、下限暫存器，存放行程的上、下限地址，行程的指令要訪問某個地址時，CPU檢查是否越界，
   4. 方法二：采用重定位暫存器（又稱基址暫存器）和界地址暫存器(又稱限長暫存器）進行越界檢查，重定位暫存器中存放的是行程的起始物理地址，界地址暫存器中存放的是行程的最大邏輯地址，

3.3 覆寫與交換

3.3.1覆寫技術

1. 早期的計算機記憶體很小，比如 IBM推出的第一臺PC機最大只支持1MB大小的記憶體，因此經常會出現記憶體大小不夠的情況，
2. 后來人們引入了覆寫技術，用來解決“程式大小超過物理記憶體總和”的問題
3. 覆寫技術的思想:將程式分為多個段（多個模塊)，常用的段常駐記憶體，不常用的段在需要時調入記憶體，
4. 記憶體中分為一個“固定區”和若干個“覆寫區”，
5. 需要常駐記憶體的段放在“固定區”中，調入后就不再調出(除非運行結束)
6. 不常用的段放在“覆寫區”，需要用到時調入記憶體，用不到時調出記憶體
7. 必須由程式員宣告覆寫結構，操柞系統完成自動覆寫，缺點：對用戶不透明，增加了用戶編程負擔，

3.3.2交換技術

1. 交換（對換）技術的設計思想：記憶體空間緊張時，系統將記憶體中某些行程暫時換出外存，把外存中某些已具備運行條件的行程換入記憶體（行程在記憶體與磁盤間動態調度)
2. 具有對換功能的作業系統中，通常把磁盤空間分為檔案區和對換區兩部分，
   1. 檔案區主要用于存放檔案，主要追求存盤空間的利用率，因此對檔案區空間的管理采用離散分配方式；
   2. 對換區空間只占磁盤空間的小部分，被換出的行程資料就存放在對換區，由于對換的速度直接影響到系統的整體速度，因此對換空間的管理主要追求換入換出速度，因此通常對換區采用連續分配方式（學過檔案管理章節后即可理解），總之，對換區的I/O速度比檔案區的更快，
3. 交換通常在許多行程運行且記憶體吃緊時進行，而系統負荷降低就暫停，例如：在發現許多行程運行時經常發生缺頁，就說明記憶體緊張，此時可以換出一些行程;如果缺頁率明顯下降，就可以暫停換出，
4. 可優先換出阻塞行程；可換出優先級低的行程；為了防止優先級低的行程在被調入記憶體后根快又被換出，有的系統還會考慮行程在記憶體的駐留時間..

3.3.3 覆寫技術與交換技術的區別

1. 覆寫是在同一個程式或行程中的
2. 交換是在不同行程(或作業)之間的

3.4 連續分配管理方式

1. 連續分配管理方式 -- 用戶行程分配的必須是一個連續的記憶體空間
   1. 單一連續分配
      1. 在單一連續分配方式中，記憶體被分為系統區和用戶區，系統區通常位于記憶體的低地址部分，用于存放作業系統相關資料；用戶區用于存放用戶行程相關資料，
      2. 記憶體中只能有一道用戶程式，用戶程式獨占整個用戶區空間，
      3. 優點：實作簡單；無外部碎片；可以采用覆寫技術擴充記憶體;不一定需要采取記憶體保護（eg:早期的PC作業系統MS-Dos) ，
      4. 缺點：只能用于單用戶、單任務的作業系統中;有內部碎片;存盤器利用率極低，
   2. 固定連續分配（無外部碎片，有內部碎片）
      1. 20世紀60年代出現了支持多道程式的系統，為了能在記憶體中裝入多道程式，且這些程式之間又不會相互干擾，于是將整個用戶空間劃分為若干個固定大小的磁區，在每個磁區中只裝入一道作業，這樣就形成了最早的、最簡單的一種可運行多道程式的記憶體管理方式，
      2. 作業系統需要建立一個資料結構―一磁區說明表，來實作各個磁區的分配與回收，每個表項對應一個磁區，通常按磁區大小排列，每個表項包括對應磁區的大小、起始地址、狀態（是否已分配），
      3. 磁區大小相等
         1. 磁區大小相等:缺乏靈活性，但是很適合用于用一臺計算機控制多個相同物件的場合（比如:鋼鐵廠有n個相同的煉鋼爐，就可把記憶體分為n個大小相等的區域存放n個煉鋼爐控制程式)
      4. 磁區大小不等
         1. 磁區大小不等:增加了靈活性，可以滿足不同大小的行程需求，根據常在系統中運行的作業大小情況進行劃分(比如:劃分多個小磁區、適量中等磁區、少量大磁區)
   3. 動態磁區分配（有外部碎片，無內部碎片）
      1. 動態磁區分配又稱為可變磁區分配，這種分配方式不會預先劃分記憶體磁區，而是在行程裝入記憶體時，根據行程的大小動態地建立磁區，并使磁區的大小正好適合行程的需要，因此系統磁區的大小和數目是可變的，（eg:假設某計算機記憶體大小為64MB，系統區8MB，用戶區共56 MB.….)
      2. 動態記憶體分配的內部碎片與外部碎片
         1. 內部碎片，分配給某行程的記憶體區域中，如果有些部分沒有用上，
         2. 外部碎片，是指記憶體中的某些空閑磁區由于太小而難以利用，
      3. 系統要用什么樣的資料結構記錄記憶體的使用情況?
         1. 空閑磁區表
            1. 每個空閑磁區對應一個表項，表項中包含磁區號、磁區大小、磁區起始地址和狀態等資訊
         2. 空閑磁區鏈
            1. 每個磁區的起始部分和末尾部分分別設定前向指標和后向指標，起始部分處還可記錄磁區大小等資訊
      4. 當很多個空閑磁區都能滿足需求時，應該選擇哪個磁區進行分配?
         1. 動態磁區分配演算法：
            1. 從空閑磁區表（或空閑磁區鏈）中選出一個磁區分配給該作業，由于分配演算法演算法對系統性能有很大的影響，因此人們對它進行了廣泛的研究，
      5. 如何進行磁區的分配與回收操作?
         1. 第一個情況：重寫記憶體磁區表/鏈
         2. 第二種情況：洗掉記憶體磁區表/鏈
      6. 如何進行磁區的分配與回收操作?
         1. 修改記憶體磁區表
         2. 合并記憶體磁區表
2. 非連續分配管理方式

3.5 動態磁區分配演算法

1. 首次適應演算法（First Fit）
   1. 演算法思想：每次都從低地址開始查找，找到第一個能滿足大小的空閑磁區，
   2. 如何實作：空閑磁區以地址遞增的次序排列，每次分配記憶體時順序查找空閑磁區鏈（或空閑磁區表），找到大小能滿足要求的第一個空閑磁區，
2. 最佳適應演算法（Best Fit）
   1. 演算法思想：由于動態磁區分配是一種連續分配方式，為各行程分配的空間必須是連續的一整片區域，因此為了保證當“大行程”到來時能有連續的大片空間，可以盡可能多地留下大片的空閑區，即，優先使用更小的空閑區，
   2. 如何實作：空閑磁區按容量遞增次序鏈接，每次分配記憶體時順序查找空閑磁區鏈（或空閑磁區表），找到大小能滿足要求的第一個空閑磁區，
3. 最壞適應演算法（Worst Fit）
   1. 演算法思想：為了解決最佳適應演算法的問題――即留下太多難以利用的小碎片可以在每次分配時優先使用最大的連續空閑區，這樣分配后剩余的空閑區就不會太小，更方便使用，
   2. 如何實作：空閑磁區按容量遞減次序鏈接，每次分配記憶體時順序查找空閑磁區鏈（或空閑磁區表），找到大小能滿足要求的第一個空閑磁區，
4. 鄰近適應演算法（Next Fit）
   1. 演算法思想：首次適應演算法每次都從鏈頭開始查找的，這可能會導致低地址部分出現很多小的空閑磁區，而每次分配查找時，都要經過這些磁區，因此也增加了查找的開銷，如果每次都從上次查找結束的位置開始檢索，就能解決上述問題，
   2. 如何實作：空閑磁區以地址遞增的順序排列（可排成一個回圈鏈表），每次分配記憶體時從上次查找結束的位置開始查找空閑磁區鏈（或空閑磁區表)，找到大小能滿足要求的第一個空閑磁區，
5. 

3.6 基本分頁存盤管理的基本概念

1. 將記憶體空間分為一個個大小相等的磁區（比如：每個磁區4KB)，每個磁區就是一個“頁框”，或稱“頁幀”、“記憶體塊”、“物理塊”，每個頁框有一個編號，即“頁框號”(或者“記憶體塊號”、“頁幀號”、“物理塊號”)頁框號從0開始，
2. 將用戶行程的地址空間也分為與頁框大小相等的一個個區域，稱為“頁”或“頁面”，每個頁面也有一個編號，即“頁號”，頁號也是從0開始，
3. (注：行程的最后一個頁面可能沒有一個頁框那么大，因此，頁框不能太大，否則可能產生過大的內部碎片)
4. 作業系統以頁框為單位為各個行程分配記憶體空間，行程的每個頁面分別放入一個頁框中，也就是說，行程的頁面與記憶體的頁框有一一對應的關系，
5. 各個頁面不必連續存放，也不必按先后順序來，可以放到不相鄰的各個頁框中，
6. 
7. 計算步驟：
   1. 要算出邏輯地址對應的頁號（頁號 = 邏輯地址 / 頁面長度 ）取整
   2. 要知道該頁號對應頁面在記憶體中的起始地址
   3. 要算出邏輯地址在頁面內的“偏移量”（頁內偏移量 = 邏輯地址 % 頁面長度）取余
   4. 物理地址 = 頁面地址 + 頁內偏移量
8. 頁表
   1. 為了能知道行程的每個頁面在記憶體中存放的位置，作業系統要為每個行程建立一張頁表，
   2. 一個行程對應一張頁表
   3. 行程的每一頁對應一個頁表項
   4. 每個頁表項由“頁號”和“塊號”組成
   5. 頁表記錄行程頁面和實際存放的記憶體塊之間的對應關系
   6. 每個頁表項的長度是相同的，頁號是“隱含”的
   7. 

3.7 基本地址變換機構

1. 用于實作邏輯地址到物理地址轉換的一組硬體機構
2. 通常會在系統中設定一個頁表暫存器（PTR)，存放頁表在記憶體中的起始地址F和頁表長度M，行程未執行時，頁表的始址和頁表長度放在行程控制塊（PCB）中，當行程被調度時，作業系統內核會把它們放到頁表暫存器中，
3. 設頁面大小為L，邏輯地址A到物理地址E的變換程序如下:
   1. 計算頁號Р和頁內偏移量w（如果用十進制數手算，則P=A/L，W=A%L；但是在計算機實際運行時，邏輯地址結構是固定不變的，因此計算機硬體可以更快地得到二進制表示的頁號、頁內偏移量)
   2. 比較頁號P和頁表長度M，若P>M，則產生越界中斷，否則繼續執行，(注意：頁號是從O開始的，而頁表長度至少是1，因此P=M時也會越界)
   3. 頁表中頁號p對應的頁表項地址=頁表起始地址F+頁號p*頁表項長度，取出該頁表項內容b，即為記憶體塊號，（注意區分頁表項長度、頁表長度、頁面大小的區別，頁表長度指的是這個頁表中總共有幾個頁表項，即總共有幾個頁;頁表項長度指的是每個頁表項占多大的存盤空間;頁面大小指的是一個頁面占多大的存盤空間)
   4. 

3.8 具有快表的地址變換機構

1. 區域性原理
2. 什么是快表（TLB）
3. 引入快表后，地址的變換程序