內存的基礎知識
內存分為按字節編址（8位）和字編制（不同計算機不一樣，64位計算機就是64位，即8個字節）
相對地址=邏輯地址 絕對地址=物理地址
從邏輯地址到物理地址的轉換由裝入解決。
裝入的三種方式
- 絕對裝入：在編譯時知道程序放在內存中的哪個位置，編譯程序將產生絕對地址的目標代碼。
靈活性很低，只適用于單道程序環境，只有單道程序環境可以在程序運行之前就能確定程序將要放入哪個位置 - 靜態重定位：又稱為可重定位裝入。裝入模塊全部使用邏輯地址，在裝入的時候將邏輯地址全部轉換為物理地址。
特點是必須分配其要求的全部內存空間，如果沒有足夠的內存，就不能裝入作業。作業一旦進入內存后，在運行期間就不能再移動，也不能再申請內存空間。 - 動態重定位：又稱為動態運行時裝入。裝入模塊使用相對地址。相對地址到物理地址的轉變要等到實際運行的時候才能確定。因此裝入內存后所有的地址仍然是邏輯地址。這種方式需要一個重定位寄存器的支持。
重定位寄存器：存放裝入模塊存放的起始位置。當實際運行的時候實時地將邏輯地址轉換為物理地址。
采用動態重定位允許程序在內存中發生移動。可以將程序分配到不連續的存儲區：在程序運行前只需要裝入他的部分代碼即可投入運算，然后在程序運行期間根據需要動態申請分配內存，便于程序段的共享，可以向用戶提供一個比存儲空間大得多的地址空間。
鏈接的三種方式
- 靜態鏈接：在程序運行之前，先將各個目標模塊以及他們所需要的庫函數連接成一個完整的可執行文件（裝入模塊），之后不再拆開。
- 裝入時動態鏈接：將各目標模塊裝入內存時，邊裝入邊鏈接
- 運行時動態鏈接：在程序執行中需要該目標模塊時才對他進行鏈接，優點是便于修改和更新，便于實現對目標模塊的共享。
內存管理需要解決的問題
- 內存空間的分配與回收
- 操作系統需要提供某種技術從邏輯上對內存空間進行擴充
- 地址轉換（三種裝入方式：絕對裝入、可重定位裝入/靜態重定位、動態運行時裝入/動態重定位）
- 內存保護：保護各個進行運行互不干擾
方法一：在CPU中設置一對上下限寄存器，存放進程的上下限地址。進程的指令要訪問某個地址時，CPU檢查是否越界。
方法二：采用重定位寄存器（基址寄存器）和界地址寄存器（限長寄存器）進行越界檢查。重定位寄存器中存放的是進程的起始物理地址，界地址寄存器中存放的是進程的最大邏輯地址。
內存空間的擴充
覆蓋技術
用于解決“程序大小超過物理內存總和”的問題
覆蓋技術的思想：將程序分為多個段（多個模塊）。常用的段常駐內存，不常用的段在需要時調入內存。
內存中分為固定區 和 若干個覆蓋區
需要常駐內存的段放入固定區中，調入后就不再調出（除非運行結束）。不常用的段就放在覆蓋區中。按照自身邏輯結構，讓那些不可能同時被訪問的程序段共享同一個覆蓋區。
程序員必須聲明覆蓋結構，操作系統完成自動覆蓋。缺點：對用戶不透明，增加了用戶編程負擔。（已經沒人用了）
交換技術
也叫做對換技術：內存空間緊張時，系統將內存中某些進程暫時換到外存中，把外存中某些已經具備運行條件的進程換入內存（中級調度）
進程的PCB需要常駐內存。
中級調度（內存調度）：決定將哪個處于掛起狀態的進程重新調入內存。
暫時換出外存等待的進程的狀態為掛起狀態。
掛起狀態可以分為：就緒掛起、阻塞掛起兩種狀態。
-
應該在外存的什么位置保存被換出的進程？
具有對換功能的操作系統中，通常把磁盤文件分為文件區和對換區兩部分。文件區主要用于存放文件，主要追求存儲空間的利用率，因此對文件區空間的管理采用離散分配方式；對換區空間只占磁盤空間的一小部分，被換出的進程數據就存放在對換區。對于對換的速度直接影響到系統的整體速度，因此對換區空間的管理主要追求換入換出速度，因此通常對換區采用連續分配方式。總之，對換區的I/O速度比文件區的更快。 -
應該什么時候交換？
交換通常在許多進程運行且內存吃緊時進行，而系統負荷降低就暫停。例如：在發現許多進程運行時經常發生缺頁，就說明內存緊張，因此可以換出一些進程；如果缺頁率明顯下降，就可以暫停換出。 -
應該換出哪些進程？
可優先換出阻塞進程；可換出優先級低的進程；為了防止優先級低的進程饑餓，有的系統還會考慮進程在內存的駐留時間。。。（PCB常駐內存）
覆蓋技術和交換技術的區別：
- 覆蓋是同一個程序或者進程中
- 交換是在不同進程/作業中的
內存分配
連續分配管理
系統為用戶進程分配必須是一個連續的內存空間。
單一連續分配
內存被分為系統區和用戶區。內存中只能有一道用戶程序，用戶程序獨占整個用戶區空間。
優點：實現簡單，沒有外部碎片；可以采用覆蓋技術擴充內存；不一定需要采取內存保護（eg:早期的MS-DOS）
缺點：只能用于單用戶、單任務的操作系統；有內部碎片；存儲器利用率極低
內部碎片：分配給進程的內存區域中，如果有些部分沒有用上，就是內部碎片。
固定分區分配
將用戶區劃分為若干個固定大小的分區，在每個分區中之狀如一道作業，這樣就形成了最早的，最簡單的一種可運行多道程序內存管理方式。
如果分區大小相等：缺乏靈活性，但是很適用用于同一臺計算機控制多個相同對象。
如果分區大小不等：增加了靈活性，可以滿足不同大小進程的需求。產生一些大的，產生一些小的。
分區說明表：來實現每個分區的分配與回收。每個表象對應一個分區，通常按分區大小分配。
優點：實現簡單，無外部碎片
缺點：當用戶程序太大時，可能所有分區都不能滿足需求，用覆蓋技術來解決可能降低性能；可能產生內部碎片，內存利用率低
動態分區分配
又稱為可變分區分配。根據進程裝入內存時的大小動態建立分區。因此系統分區的大小和數目時可以改變的。
- 操作使用什么樣的數據結構記錄內存
- 空閑分區表：每個空閑分區對應一個表項
- 空閑分區鏈：每個分區的起始部分和末尾部分分別設置前向指針和后向指針。起始部分處還可以記錄分區大小等信息。
- 當很多空閑分區都能夠滿足需求時選擇哪一個
使用動態分區分配算法
- 分區的分配和回收
動態分區沒有內部碎片，但是有外部碎片。
內部碎片：分配給某進程的內部區域中如果有些部分沒有用上
外部碎片：內存中的某些空閑分區由于太小而難以利用
為了解決外部碎片，我們可以采用緊湊技術，通過將不同進程的內存空間挪挪位將不連續的內存空間湊在一起。為了實現這種技術我們應該是用動態重定位的裝入方式，每次緊湊之后都將進程的起始地址都放在基址寄存器（重定位寄存器）中。
動態分區分配算法
首次適應算法
每次從低地址開始查找，找到第一個能夠滿足大小的空閑分區
實現：空閑分區以地址遞增的次序排列。每次分配內存時順序查找空閑分區表(鏈)，找到第一個滿足的空閑分區。
最佳適應算法
盡可能留下大片的空閑區，優先使用更小的空閑區
實現：空閑分區按照容量遞增的次序鏈接，每次分配內存時找到第一個滿足的空閑分區。每次分配以后還需要對空閑分區排序使其按照容量大小遞增。
缺點：每次采用最小的分區選擇，會產生很多外部碎片
最壞適應算法
每次分配優先使用最大的連續空閑區，這樣每次分配以后空閑區就不會太小。
實現：空閑分區按照容量遞減鏈接。每次分配使用第一個空閑分區（如果第一個都不滿足就GG了）然后對空閑分區進行排序
缺點：如果大進程到達就會導致沒有空間使用
鄰近適應算法
首次適應算法每次從開始查找導致開始部分出現很多外部碎片。為了解決這個問題，每次從上次查找結束的位置開始檢索。
實現：空閑分區以地址遞增的順序排列成循環鏈表。每次內存分配從上次查找結束的位置開始查找。同首次適應算法一樣每次分配以后不需要對鏈表重新排列。
首次適用算法雖然容易產生外部碎片，但是可能保留大分區。鄰近適應算法雖然減少產生外部碎片，但是可能沒有外部碎片。
綜合來看首次適應算法還是比較優秀的。
)
