作業系統基礎知識之記憶體管理

記憶體管理

文章目錄

• 記憶體管理
• 一、記憶體管理的概念
• • 1.1 什麼是記憶體？有何作用？
  • 1.2 程序運作的原理
  • • 1.2.1 裝入的三種方式
    • 1.2.2 連結的三種方式
• 二、記憶體管理
• • 2.1、記憶體空間的擴充
  • • 2.1.1 覆寫與交換
    • 2.1.2 交換技術（對換）
  • 2.2、記憶體空間的配置設定與回收
  • • 2.2.1 連續配置設定管理方式
    • • 2.2.1.1 單一連續配置設定
      • 2.2.1.2 固定分區配置設定
      • 2.2.1.3 動态分區配置設定
      • • 2.2.1.3.1 動态分區配置設定算法
    • 2.2.2 非連續配置設定管理方式
    • • 2.2.2.1 基本分頁存儲管理
      • 2.2.2.2 基本位址變換機構
      • 2.2.2.3 具有快表的位址變換機構
      • 2.2.2.4 兩級頁表
      • 2.2.2.5 基本分段存儲管理
      • 2.2.2.4 段頁存儲管理
  • 2.3 虛拟記憶體
  • • 2.3.1 基本概念
    • 2.3.2 請求分頁管理方式
    • 2.3.3 頁面置換算法
    • • 2.3.3.1 最佳置換算法（OPT）
      • 2.3.3.2 先進先出置換算法（FIFO）
      • 2.3.3.3 最近最久未使用置換算法（LRU）
      • 2.3.3.4 時鐘置換算法（CLOCK）
      • 2.3.3.5 改進型的時鐘置換算法
    • 2.3.4 頁面配置設定政策

一、記憶體管理的概念

1.1 什麼是記憶體？有何作用？

1.2 程序運作的原理

指令

經過編譯：

//	   操作碼   	 存取數字的目标位址	取數字原位址
指令1 (00101100,00000011,01001111)資料傳送指令
    
指令2 (10010010,00000011,00000001 )加法指令
指令3 (00101100,01001111,00000011)資料傳送指令
           

邏輯位址 實體位址

編譯時産生的指令隻關心相對位址，實際放入記憶體中時再想辦法根據其實位址得到絕對位址。

編譯時隻需确定變量x存放的相對位址是100(也就是說相對于程序在記憶體中的起始位址而言的位址)。

CPU想要找到x在記憶體中的實際存放位置，隻需要用程序的起始位址+100即可。

c語言從寫程式到運作程式的過程

編譯:由編譯程式将使用者源代碼編譯成若千個目标子產品(編譯就是把進階語言翻譯為機器語言)

連結:由連結程式将編譯後形成的一組目标子產品，以及所需庫函數連結在一起，形成一個完整的裝入子產品

裝入(裝載) :由裝入程式将裝入子產品裝入記憶體運作

1.2.1 裝入的三種方式

① 絕對裝入

絕對裝入：在編譯時，如果知道程式将放在記憶體中的哪個位置，編譯程式将産生絕對位址的目标代碼。

裝入程式按照裝入子產品中的位址，将程式和資料裝入記憶體。

絕對裝入隻适用于單道程式環境。

② 靜态重定位

靜态重定位：又稱可重定位裝入。編譯、連結後的裝入子產品的位址都是從0開始的，指令中使用的位址、資料存放的位址都是相對于起始位址而言的邏輯位址。可根據記憶體的目前情況，将裝入子產品裝入到記憶體的适當位置。裝入時對記憶體位址進行“重定位”，将邏輯位址變換為實體位址（位址變換是在裝入時一次完成的）。

靜态重定位的特點是：一個作業裝入記憶體時，必須配置設定其要求的全部記憶體空間，如果沒有足夠的記憶體，就不能裝入該作業。作業一旦進入記憶體後，在運作期間就不能再移動，也不能再申請記憶體空間。

③ 動态重定位

動态重定位:又稱動态運作時裝入。編譯、連結後的裝入子產品的位址都是從0開始的。裝入程式把裝入子產品裝入記憶體後，并不會立即把邏輯位址轉換為實體位址，而是把位址轉換推遲到程式真正要執行時才進行。是以裝入記憶體後所有的位址依然是邏輯位址。這種方式需要一個重定位寄存器的支援。

優點：

可将程式配置設定到不連續的存儲區中;

在程式運作前隻需裝入它的部分代碼即可投入運作，然後在程式運作期間，根據需要動态申請配置設定記憶體;

便于程式段的共享，可以向使用者提供一個比存儲空間大得多的位址空間

1.2.2 連結的三種方式

1. 靜态連結: 在程式運作之前，先将各目标子產品及它們所需的庫函數連接配接成一個完整的可執行檔案(裝入子產品) ,之後不再拆開。
2. 裝入時動态連結: 将各目标子產品裝入記憶體時，邊裝入邊連結的連結方式。
3. 運作時動态連結: 在程式執行中需要該目标子產品時，才對它進行連結。其優點是便于修改和更新，便于實作對目标子產品的共享。

二、記憶體管理

1. 記憶體空間的配置設定和回收。
2. 作業系統需要提供某種技術從邏輯上對記憶體空間進行擴充（虛拟存儲）。
3. 作業系統需要提供位址轉換功能，負責程式的邏輯位址與實體位址的轉換。
4. 作業系統需要提供記憶體保護功能。保證各程序在各自存儲空間内運作，互不幹擾。

記憶體保護的兩種方法：（保證各程序在自己的記憶體空間内，不會通路越界）

方法一： 在CPU中設定一對上、下限寄存器，存放程序的上、下限位址。程序的指令要通路某個位址時，CPU檢查是否越界。

方法二： 采用重定位寄存器（基址寄存器）和界位址寄存器（限長寄存器）進行越界檢查。重定位寄存器存放的是程序的起始實體位址。界位址寄存器中存放的是程序的最大邏輯位址。

2.1、記憶體空間的擴充

2.1.1 覆寫與交換

覆寫是在同一程式或程序中的，是為了解決程式大小超過實體記憶體總和的問題。

覆寫技術的思想:将程式分為多個段(多個子產品)。常用的段常駐記憶體，不常用的段在需要時調入記憶體。

記憶體中分為一個“固定區”和若幹個“覆寫區”

需要常駐記憶體的段放在“固定區”中，調入後就不再調出(除非運作結束)

必須由程式員聲明覆寫結構，作業系統完成自動覆寫。

缺點:對使用者不透明，增加了使用者程式設計負擔。

覆寫技術隻用于早期的作業系統中，現在已成為曆史。

2.1.2 交換技術（對換）

交換是在不同程序（或作業）之間的。

交換(對換)技術的設計思想: 記憶體空間緊張時，系統将記憶體中某些程序暫時換出外存，把外存中某些已具備運作條件的程序換入記憶體(程序在記憶體與磁盤間動态排程)

PCB常駐記憶體

問題1：應該在外存（磁盤）什麼位置儲存被換出的程序？

具有對換功能的作業系統中，通常把磁盤空間分為檔案區和對換區兩部分。

檔案區主要用于存放檔案，主要追求存儲空間的使用率，是以對檔案區空間的管理采用離散配置設定方式;

對換區空間隻占磁盤空間的小部分，被換出的程序資料就存放在對換區。由于對換的速度直接影響到系統的整體速度，是以對換區空間的管理主要追求換入換出速度，是以通常對換區采用連續配置設定方式。

總之，對換區的I/O速度比檔案區的更快。

問題2：什麼時候應該換出？

交換通常在許多程序運作且記憶體吃緊時進行，而系統負荷降低就暫停。

例如:在發現許多程序運作時經常發生缺頁，就說明記憶體緊張，此時可以換出一些程序;如果缺頁率明顯下降，就可以暫停換出。

問題3：應該換出哪些程序？

可優先換出阻塞程序;可換出優先級低的程序;為了防止優先級低的程序在被調入記憶體後很快又被換出，有的系統還會考慮程序在記憶體的駐留時間…

2.2、記憶體空間的配置設定與回收

2.2.1 連續配置設定管理方式

連續配置設定：指為使用者程序配置設定的必須是一個連續的記憶體空間。

2.2.1.1 單一連續配置設定

在單一連續配置設定方式中，記憶體被分為系統區和使用者區。系統區通常位于記憶體的低位址部分，用于存放作業系統相關資料；使用者區用于存放使用者程序相關資料。

優點：實作簡單：無外部碎片；可以采用覆寫技術擴充記憶體；不一定需要采用記憶體保護（eg:早期的PC作業系統MS-DOS）

缺點：隻能用于單使用者、單任務的作業系統中；有内部碎片；存儲區使用率極低。

配置設定給某程序的記憶體區域中，如果有些部分沒有用上，就是“記憶體碎片”。

2.2.1.2 固定分區配置設定

這裡用覆寫技術，是因為最大的分區都不能承載該程式，隻能每次裝入該程式的部分。

2.2.1.3 動态分區配置設定

對于第二個問題：當有多個空閑分區都能滿足需求時，應該選擇哪個分區進行配置設定？

這個涉及到動态分區配置設定算法，從空閑分區表（鍊）中選擇一個分區配置設定給該作業，後面會介紹四種動态分區配置設定算法。

對于第三個問題：如何進行分區的配置設定與回收操作？

配置設定：在對應的表項改變分區大小，如果分區大小為0，就在分區表或者分區鍊中删除該分區；

回收：回收區的前後如果有相鄰的空閑分區，那麼就合并。

2.2.1.3.1 動态分區配置設定算法

1. 首次适應算法

2. 最佳适應算法

**缺點：**每次都選最小的分區進行配置設定，會留下越來越多的、很小的、難以利用的記憶體塊。是以這種方法會産生很多的外部碎片。

3. 最壞适應算法

**缺點：**每次選擇都是最大的分區進行配置設定，雖然可以讓配置設定後留下的空閑分區更大，但是這種方式會導緻交大的連續空閑分區被迅速用完，如果之後有“大程序”到達，就沒有記憶體分區可用了。

4. 鄰近适應算法

2.2.2 非連續配置設定管理方式

将記憶體空間分為一個個大小相等的分區，每個分區就是一個記憶體塊（頁框、頁幀、實體塊），将使用者程序的位址空間也分為與記憶體塊大小相等的一個個區域，稱之為頁（頁面），每個頁面也有一個編号，即頁号，頁号也是從0開始。（程序的最後一個頁面可能沒有一個記憶體塊那麼大。是以記憶體塊也不能太大，否則可能産生過大的内部碎片）

作業系統以記憶體塊為機關為各個程序配置設定記憶體空間。程序的每個頁面分别放入一個記憶體塊中。也就是說，程序的頁面與記憶體的記憶體塊一一對應。

各頁面不必連續存放，也不必按先後順序來，可以放到不相鄰的各個記憶體塊中。

思考：如何實作位址的轉換？

2.2.2.1 基本分頁存儲管理

如何知道邏輯位址在頁面内的偏移量：

總結：

2.2.2.2 基本位址變換機構

上述這種方式需要兩次通路記憶體，一次是查頁表，一次是通路目标記憶體單元，後面會講解更好的方法。

2.2.2.3 具有快表的位址變換機構

局部性原理

什麼是快表？

快表，又稱聯想寄存器（TLB），是一種通路速度比記憶體塊很多的告訴緩沖存儲器，用來存放目前通路的若幹頁表項，以加速位址變換的過程。與此對應，記憶體中的頁表常稱為慢表。

引入快表後，位址的變換過程

2.2.2.4 兩級頁表

單級頁表存在什麼問題？怎麼解決？

兩級頁表的原理、邏輯位址結構

如何實作位址變換？

兩級頁表問題需要注意的幾個細節

如果沒有快表，那麼n幾頁表通路記憶體的次數為n+1次

2.2.2.5 基本分段存儲管理

與“分頁”最大的差別就是–離散配置設定時所配置設定位址空間的基本機關不同。

什麼是分段？

什麼是段表？

如何實作位址變換？

分段、分頁管理的對比

2.2.2.4 段頁存儲管理

分頁、分段管理方式中最大的優缺點

分段管理中産生的外部碎片也可以“緊湊”來解決，隻是需要付出較大的時間代價。

分段 + 分頁的結合--------段頁式管理方式

段表、頁表

如何實作位址轉換

2.3 虛拟記憶體

2.3.1 基本概念

傳統存儲方式的特征、缺點

局部性原理

虛拟記憶體的定義和特征

如何實作虛拟記憶體技術

2.3.2 請求分頁管理方式

掌握三點：什麼時候請求調頁？ 在什麼時候進行頁面置換？ 當調頁和頁面置換完成之後，有需要對那些資料結構進行修改？

2.3.3 頁面置換算法

2.3.3.1 最佳置換算法（OPT）

!!! 最佳置換算法可以保證最低的缺頁率，但實際上，隻有在程序執行的過程中，才能知道接下來會通路到的是那個頁面，作業系統無法提前預判頁面通路序列。是以，最佳置換算法是無法實作的。

2.3.3.2 先進先出置換算法（FIFO）

2.3.3.3 最近最久未使用置換算法（LRU）

該算法的實作需要專門的硬體支援，雖然算法性能好，單實線困難，開銷大。

2.3.3.4 時鐘置換算法（CLOCK）

隻有在缺頁的時候，指針才會移動。

2.3.3.5 改進型的時鐘置換算法

2.3.4 頁面配置設定政策

系統會鎖定一些頁面，這些頁面中的内容不能置換出外存(如:重要的核心資料可以設為“鎖定”)

系統擁有足夠的對換區空間:頁面的調入、調出都是在記憶體與對換區之間進行，這樣可以保證頁面的調入、調出速度很快。在程序運作前，需将程序相關的資料從檔案區複制到對換區。

系統缺少足夠的對換區空間:凡是不會被修改的資料都直接從檔案區調入，由于這些頁面不會被修改，是以換出時不必寫回磁盤，下次需要時再從檔案區調入即可。對于可能被修改的部分，換出時需寫回磁盤對換區，下次需要時再從對換區調入。

UNIX 方式:運作之前程序有關的資料全部放在檔案區，故未使用過的頁面，都可從檔案區調入。若被使用過的頁面需要換出，則寫回對換區，下次需要時從對換區調入。

抖動（颠簸）現象

剛剛換出的頁面馬上又要換入記憶體，剛剛換入的頁面馬上又要換出外存，這種頻繁的頁面排程行為稱為抖動，或颠簸。

産生抖動的主要原因是程序頻繁通路的頁面數目高于可用的實體塊數(配置設定給程序的實體塊不夠)

為程序配置設定的實體塊太少，會使程序發生抖動現象。為程序配置設定的實體塊太多，又會降低系統整體的并發度，降低某些資源的使用率

為了研究為應該為每個程序配置設定多少個實體塊，Denning 提出了程序 “工作集” 的概念

工作集

駐留集: 指請求分頁存儲管理中給程序配置設定的記憶體塊的集合。

工作集: 指在某段時間間隔裡，程序實際通路頁面的集合。

某程序的頁面通路序列如下，視窗尺寸為4，各時刻的工作集為?

工作集大小可能小于視窗尺寸，實際應用中，作業系統可以統計程序的工作集大小，根據工作集大小給程序配置設定若幹記憶體塊。如:視窗尺寸為 5 ，經過一段時間的監測發現某程序的工作集最大為 3 ，那麼說明該程序有很好的局部性，可以給這個程序配置設定 3 個以上的記憶體塊即可滿足程序的運作需要。

一般來說，駐留集大小不能小于工作集大小，否則程序運作過程中将頻繁缺頁。

拓展:基于局部性原理可知，程序在一段時間内通路的頁面與不久之後會通路的頁面是有相關性的。是以，可以根據程序近期通路的頁面集合(工作集)來設計一種頁面置換算法- - -選擇一個不在工作集中的頁面進行淘汰。