2020年秋招最新作業系統之存儲管理面試知識點集錦（上）

一、基本概念：位址重定位

1.1 需要了解的内容

• 程式裝載到記憶體才可以運作

  通常，程式可以執行檔案格式儲存在磁盤上

• 多道程式設計模型
• 允許多個程式同時進入記憶體

• 每個程序有自己的位址空間

  一個程序執行時不能通路另一個程序的位址空間

  程序不能執行不合适的操作

1.2 要解決的問題

說明：

在左邊的單處理器系統中，如果一個程序想要運作，那麼必須将程序位址空間裝載到實體記憶體中才可以運作。

而右邊的是多處理器系統中有多個程序需要進入實體記憶體執行，這裡要解決的問題就是，如何将程序位址空間合理的裝載到實體記憶體中，如何合理的配置設定使用記憶體，使得每個程序能正确執行。

1.3 複習：程序位址空間

1.4 注意

• 程序中的位址不是最終的實體位址
• 在程序運作前無法計算出實體位址

這就需要位址重定位來解決這些問題。

二、位址重定位

• 邏輯位址（相對位址、虛拟位址）

  使用者程式經過編譯、彙編後形成目标代碼，目标代碼通常采用相對位址的形式，其首位址為0，其餘位址都相對于首位址而編址。

• 不能用邏輯位址在記憶體中讀取資訊。

• 實體位址（絕對位址、實位址）

  記憶體中存儲單元的位址，可直接尋址

為了保證

cpu

執行指令時可以正确通路記憶體單元，需要将使用者程式中的邏輯位址轉換為運作時可由機器直接尋址的實體位址，這一過程稱為位址沖地位。

2.1 靜态重定位與動态重定位

• 靜态重定位

  當使用者程式加載到記憶體時，一次性實作邏輯位址到實體位址的轉換。

  一般可由軟體完成。

• 動态重定位(重點)

  在程序執行過程中進行位址變換，即逐條指令執行時完成位址轉換。

  支援程式浮動

  需要硬體部件支援，較為常用。

2.2 動态重定位實作

三、實體記憶體管理

3.1 空閑記憶體管理

**說明：**我們對實體記憶體有不同的劃分，一種是等長的劃分，一種是不等長的劃分。

資料結構

1、位圖

對于等長劃分這種我們可以使用位圖的方式。每個配置設定單元對應于位圖中的一位，0表示空閑，1表示占用（或者相反）。對于不等長的劃分可以使用下面兩種配置設定結構。

2、空閑區表、已配置設定區表

表中每一項記錄了空閑區（或已配置設定區）的起始位址、長度、标志

3、空閑塊連結清單

3.2 記憶體配置設定算法

這裡我們使用空閑區表、已配置設定區表為例來說明記憶體配置設定算法。

• 首次适配

  first fit

  在空閑區表中找到第一個滿足程序要求的空閑區
• 下次适配

  next fit

  從上次找到的空閑區處接着查找
• 最佳适配

  best fit

  查找整個空閑區表，找到能夠滿足程序要求的最小空閑區
• 最差适配

  worst fit

  總是配置設定滿足程序要求的最大空閑區
• 當找到滿足程序需求的空閑區表後，需要将空閑區分為兩部分，一部分供程序使用，另一部分形成新的空閑區。

3.3 回收問題

• 記憶體回收算法

• • 當某一塊歸還後，前後空閑空間合并，修改記憶體空閑區表。

  • 四種情況

    上相鄰、下相鄰、上下都相鄰、上下都不相鄰

3.4 夥伴系統(重點)

這是

Linux

底層記憶體管理采用的一種方法

• 一種經典的記憶體配置設定方案，是一種特殊的分離适配算法
• 主要思想：将記憶體按

  2

  的整數次幂進行劃分，組成若幹空閑塊表；查找該連結清單找到能滿足程序需求的最佳比對塊。
• 算法

• • 首先将整個可用空間看作一塊：

    2^U

• • • 假設程序申請的空間大小為

      s

      ，

      如果滿足

      2^(U-1)<s<=2^U

      ，則配置設定整個塊

      否則，将塊劃分為兩個大小相等的夥伴，大小為

      2^(U-1)

• • 一直劃分下去直到産生大于或等于

    s

    的最小塊。

3.5 夥伴系統例子

**說明：**從上圖中可以看到上面的算法是如何工作的。

四、連續記憶體管理方案

4.1 單一連續區

特點：一段時間内隻有一個程序在記憶體中，簡單、記憶體使用率低。

這種方案是在早期系統中使用的，有三種不同的布局：

4.2 固定分區

• 把記憶體空間分割成若幹個區域，稱為分區
• 每個分區的大小可以相同也可以不同
• 分區大小固定不變
• 每個分區裝一個且隻能一個程序

• 

不同的程序鍊分排在不同分區位置。缺點是有的程序鍊很長，一時得不到分區，但是此時可能有些空閑分區根本沒有被使用。

于是還有右邊這種排隊方案，就是隻有一個程序鍊，然後哪個分區空閑了，排在首位的程序就進入執行。早期手機中就是采用這種方法。

4.3 可變分區

• 根據程序的需要，把記憶體空閑空間分割出一個分區，配置設定給該程序
• 剩餘部分稱為新的空閑區
• 會導緻一些問題：導緻一些外碎片，這樣會導緻記憶體使用率下降。
• 碎片問題解決
• 碎片：很小的、不易利用的空閑區，導緻記憶體使用率下降

• 解決方案：緊縮技術(又稱壓縮，緊緻，搬家技術)

  在記憶體中移動程式，将所有小的空閑區合并為較大的空閑區

• 緊縮時要考慮的問題

  系統開銷、移動時機

五、離散記憶體管理方案(重點)

5.1 頁式存儲管理方案

• 設計思想

  使用者程序位址空間被劃分為大小相等的部分，稱為頁（

  page

  ），從零開始編号。

  這是邏輯位址空間上的稱謂。

• • 記憶體空間按同樣大小劃分為大小相等的區域，稱為頁幀（

    page frame

    ），從零開始編号

  • 記憶體配置設定（規則）

    以頁為機關進行配置設定，并按程序需要的頁數來配置設定

    邏輯上相鄰的頁，實體上不一定相鄰。

  • 典型的頁面尺寸：

    4K

    或

    4M

• 邏輯位址

• 

• **說明：**邏輯位址分為頁号和頁内位址（頁内偏移），這種劃分是系統自動完成的，對使用者是透明的。
• 記憶體配置設定

• 

• **說明：**可以看到連續的程序位址空間映射到頁幀中的實體記憶體是雜亂的。

• 

• **說明：**對于邏輯位址空間和實體記憶體空間的雜亂的映射，如何進行映射呢？這裡我們需要使用頁表來記錄這種映射。
• 相關資料結構及位址轉換

• 頁表由若幹頁表項（記錄了邏輯頁号與頁框号對應關系）構成

• • 每個程序一個頁表，存放在記憶體
  • 頁表起始位址儲存在何處？
  • 空閑記憶體管理

其實我們可以使用位圖就可以管理實體記憶體了

位址轉換（硬體支援）

**cpu**取到邏輯位址，自動劃分為頁号和頁内位址；

用頁号查頁表，得到頁框号，再與頁内偏移拼接成實體位址。

在這種方案中我們也會遇到碎片問題，這裡的碎片是内碎片。比如某個程序需要5頁加一條指令，于是這裡我們需要配置設定6頁給這個程序。