[作業系統] 位址空間和交換技術

位址空間和交換技術

• 位址空間和交換技術
  • 位址空間的概念
  • 基址寄存器和界限寄存器
  • 記憶體超載
  • 交換技術
    • 預留白間
    • 空閑記憶體管理
  • 連結清單存儲管理中用來建立程序的算法

1. 位址空間的概念

在最初系統中沒有對記憶體的抽象，直接使用實體位址進行存儲，這種方法會帶來嚴重的問題。

1. 如果使用者程式可以尋址記憶體的每個位元組，它們就可以容易地破壞作業系統。進而使作業系統停止運作
2. 想要同時運作多個程式很困難，因為使用實體位址很容易将資料覆寫。

要保證多個應用程式同時存在于記憶體并且不互相影響，要解決兩個問題：保護和重定位。

一個很好的解決方法是創造一個記憶體抽象：位址空間。位址空間為程式創造了一種抽象的記憶體，位址空間是一個程序可用于尋址記憶體的一套位址集合。每個程序都有一個自己的位址空間，并且這個位址空間獨立于其他程序的位址空間(在特殊情況下想要共享除外)。例如，電話号碼00000000000 ~ 99999999999就是一個位址空間。

2. 基址寄存器和界限寄存器

使用位址空間的困難點在于給每個程式一個自己的位址空間，假如A程式想要使用的位址為28，B程式想要使用的位址也為28。兩個程式同時運作，我們不能讓這兩個程式互相影響，就要讓他們想要使用的**邏輯位址**28對應不同的實體位址。

解決這個問題的一種方法是動态重定位。為每個CPU配置兩個特殊的寄存器，基址寄存器和界限寄存器。當程式運作時，程式的起始實體位址裝載到基址寄存器，長度裝載到界限寄存器。這樣程式在執行指令時，如果使用邏輯位址就會被解釋為基址寄存器存儲的實體位址。例如，此時程式想要通路邏輯位址28，使用指令 “JMP 28”，此時基址寄存器中的值為16412，硬體自動把這條指令解釋為”JMP 16412”。

使用這種方法的缺點是，每次通路記憶體都需要進行加法和比較

3. 記憶體超載

當所有要執行的程序所需要的記憶體大于計算機的實體記憶體時，就不能把所有程序一直儲存在記憶體中。這種情況叫做記憶體超載。要想解決這種問題，有兩種方法。

1. 交換技術

   即把一個程序完整排程記憶體，使該程序運作一段時間，然後把它存回磁盤。空閑程序主要存儲在磁盤上，就不會占用記憶體。

2. 虛拟記憶體

   可以使程式在隻有一部分被調入記憶體的情況下運作。

4. 交換技術

如圖所示，陰影區域表示未使用的記憶體。開始時記憶體中隻有程序A。之後建立程序B和C或者從磁盤将它們還如記憶體。d圖顯示A被交換到磁盤，D被調入到記憶體，然後B被調出，A再次被調入。

1. 預留白間

通過圖檔可見，使用這種方法，記憶體中有很多小的空閑區(陰影)，這些小的空閑區大部分無法放置合适的程序，就會造成浪費。通過把所有程序向下移動，将這些空閑區合在一起，可以節省空間，這種方法叫做記憶體緊縮。但是這個操作會耗費大量CPU時間。

使用這種方法我們需要注意一個問題，即如果程序大小不是一成不變的而是動态的該怎麼解決。若該程序與空閑區相鄰，可以使用空閑區來将該程序所占記憶體擴大。但如果該程序與其他程序相鄰，則無法擴大，此時隻能交換出一個或多個程序。

為了解決這個問題，在為程序配置設定記憶體空間時，可以為它們配置設定一些額外的記憶體。而寫回磁盤時，隻寫回實際使用的記憶體。

a圖為給程序配置設定多餘空間的普通方法。如果程序有兩個可增長段，如資料段和堆棧段，則可以使用b中的方法。

2. 空閑記憶體管理

在動态配置設定記憶體時，作業系統必須對記憶體進行追蹤和管理。

1. 使用位圖的存儲管理

   記憶體被劃分為幾個字到幾千位元組的配置設定單元，每個配置設定單元對應于為位圖中的一位，0表示空閑，1表示占用(或者相反)。配置設定單元越小，位圖越大。32n位的記憶體需要n位位圖。再決定把一個占k個配置設定單元的程序調入記憶體中時，存儲管理器需要搜尋位圖，在位圖中找出有個k個連續為0的串。缺點是比較耗時。

   

2. 連結清單存儲管理

   連結清單中的結點或者是一個程序，或者是兩個程序間的空閑區。每一個結點包含：空閑區，程序的訓示标志、起始位址、長度。當程序終止時，更新非常直接，如果鄰居沒有空閑去，隻把自己變為空閑區就可以。如果鄰居有空閑區則把該程序原有的位址與空閑區合并。是以雙連結清單更好，因為便于找到前後鄰居并合并。

   

5. 連結清單存儲管理中用來建立程序的算法

假設存儲管理器知道要為程序配置設定多大記憶體。

1. 首次适配

   存儲器沿着段鍊進行搜尋，找到第一個足夠大的空閑區，将空閑區的一部分給程序使用，另一部分變為新的空閑區(除非大小正好一樣)。這種方法速度很快。

2. 下次适配

   工作方式與首次适配相似，但是不同于首次适配每次從頭開始尋找，下次适配會記錄下上次配置設定的位置，然後從上次配置設定過的地方開始。

3. 最佳适配

   搜尋整個連結清單，找到能容納程序的最小空閑區。浪費時間，并且會産生許多無用的小空閑區。

4. 最差适配

   與最佳适配相反，該方法總是總是配置設定最大空閑區給程序。

   如果想要增加以上4個算法速度，可以為程序和空閑區維護各自的連結清單。但會增加記憶體釋放速度，因為要将結點從程序連結清單删除，并加入到空閑區連結清單。
   
   可以将空閑區連結清單進行增序排序，以減少最佳适配的速度。當單獨維護空閑區時，可以直接用空閑區存儲資訊，每個空閑區的第一個字可以為大小，第二個字可以指向下一個空閑區。
              

5. 快速适配：為常用大小的空閑區維護單獨清單。例如有一個n項的表。表的第一項指向大小4KB空閑區，第二項為8KB，第三項為12KB。以此類推，21KB的空閑區可以放在代表20KB連結清單中，也可以單獨放置在特别連結清單中。

參考書目：現代作業系統第三版