操作系統概述（二）

操作系統內存管理

內存管理包括內存管理和虛擬內存管理。
內存管理包括程序裝入等概念、交換技術、連續分配管理方式和非連續分配管理方式（分頁、分段、段頁式）。
虛擬內存管理包括虛擬內存概念、請求分頁管理方式、頁面置換算法、頁面分配策略、工作集。

我們先來了解一下什么是內存：

內存是計算機系統的一個重要組成部分，只有在內存中的程序才能被CPU所執行，而且CPU運行時所需要的數據和程序運行空間都是從內存中獲取，所以內存性能的好壞直接影響我們計算機性能的好壞.

講到內存我們可以講一下關于存儲器的分類：

存儲器按照功能分配可以分為高速緩沖存儲器（cache）,主存儲器(內存),外存儲器（外存）：

高速緩沖存儲器（cache）：cache又分為一級cache和二級cache，一級cache是位于CPU內部的存儲器，它負責存儲并向CPU傳遞需要的數據和指令，二級cache位于CPU和主存儲器(DRAM)之間，二級的作用就是存儲那些CPU處理時需要用到、一級緩存又無法存儲的數據。CPU讀取數據時，先從一級cache中尋找，找不到再從二級cache中尋找，有時還需要從三級cache中尋找.它們的共同點是讀取速度都比CPU慢比內存快，內存容量小，價格高. 緩存的出現主要是為了解決CPU運算速度與內存 讀寫速度不匹配的矛盾，因為CPU運算速度要比內存讀寫速度快很多，這樣會使CPU花費很長時間等待數據到來或把數據寫入內存。

主存儲器(內存): 我們手機或者電腦所說的運行內存便是主存儲器，程序運行時會把處于外存的數據調換到主存中，主存里面存放著大量的CPU運行時可能需要用到的數據，它的特點時讀寫速度較快，大小較小.一般為4G-8G大小.

外存儲器(外存)：外存也就是我們常說的硬盤，它負責存放系統程序和大型數據文件及數據庫，特點就是容量大，速度低.

按照存儲器的類別我們又可以分為以下幾類：

RAM
RAM(random access memory，隨機存取存儲器）。存儲單元的內容可按需隨意取出或存入，且存取的速度與存儲單元的位置無關的存儲器。這種存儲器在斷電時將丟失其存儲內容，故主要用于存儲短時間使用的程序。 按照存儲信息的不同，隨機存儲器又分為靜態隨機存儲器（Static RAM，SRAM)和動態隨機存儲器（Dynamic RAM，DRAM)。

SRAMS
RAM（Static RAM，靜態隨機存儲器），不需要刷新電路，數據不會丟失，而且，一般不是行列地址復用的。但是他集成度比較低，不適合做容量大的內存，一般是用在處理器的緩存里面。
SRAM其實是一種非常重要的存儲器，它的用途廣泛。SRAM的速度非常快，在快速讀取和刷新時能夠保持數據完整性。SRAM內部采用的是雙穩態電路的形式來存儲數據。所以SRAM的電路結構非常復雜。制造相同容量的SRAM比DRAM的成本高的多。正因為如此，才使其發展受到了限制。因此目前SRAM基本上只用于CPU內部的一級緩存以及內置的二級緩存。僅有少量的網絡服務器以及路由器上能夠使用SRAM。

DRAM
Dynamic RAM，動態隨機存取存儲器，每隔一段時間就要刷新一次數據，才能保存數據。而且是行列地址復用的，許多都有頁模式。SDRAM是其中的一種。

SDRAM
SDRAM（Synchronous DRAM，同步動態隨機存儲器），即數據的讀寫需要時鐘來同步。其存儲單元不是按線性排列的，是分頁的。
DRAM和SDRAM由于實現工藝問題，容量較SRAM大。但是讀寫速度不如SRAM。
一般的嵌入式產品里面的內存都是用的SDRAM。電腦的內存也是用的這種RAM，叫DDR SDRAM，其集成度非常高，因為是動態的，所以必須有刷新電路，每隔一段時間必須得刷新數據。

ROM
Read-Only Memory，只讀存儲器的總稱。
在微機的發展初期，BIOS都存放在ROM（Read Only Memory，只讀存儲器）中。ROM內部的資料是在ROM的制造工序中，在工廠里用特殊的方法被燒錄進去的，其中的內容只能讀不能改，一旦燒錄進去，用戶只能驗證寫入的資料是否正確，不能再作任何修改。如果發現資料有任何錯誤，則只有舍棄不用， 重新訂做一份。ROM是在生產線上生產的，由于成本高，一般只用在大批量應用的場合。

PROM
可編程只讀存儲器，只能寫一次，寫錯了就得報廢，現在用得很少了，好像那些成本比較低的OPT單片機里面用的就是這種存儲器吧。

EPROM　
EPROM（Erasable Programmable ROM，可擦除可編程ROM）芯片可重復擦除和寫入，解決了PROM芯片只能寫入一次的弊端。
EPROM芯片有一個很明顯的特征，在其正面的陶瓷封裝上，開有一個玻璃窗口，透過該窗口，可以看到其內部的集成電路，紫外線透過該孔照射內部芯片就可以擦除其內的數據，完成芯片擦除的操作要用到EPROM擦除器。

EEPROMEEPROM (Electrically Erasable Programmable ROM，電可擦可編程只讀存儲器)，一種掉電后數據不丟失的存儲芯片。EEPROM是可用戶更改的只讀存儲器，其可通過高于普通電壓的作用來擦除和重編程（重寫），即可以在電腦上或專用設備上擦除已有信息并重新編程。不像EPROM芯片，EEPROM不需從計算機中取出即可修改，是現在用得比較多的存儲器，比如24CXX系列的EEPROM。
在一個EEPROM中，當計算機在使用的時候是可頻繁地重編程的，EEPROM的壽命是一個很重要的設計考慮參數。

閃存（Flash）
閃存(FLASH)是一種非易失性存儲器，即斷電數據也不會丟失。因為閃存不像RAM（隨機存取存儲器）一樣以字節為單位改寫數據，因此不能取代RAM。 　　
閃存卡（Flash Card）是利用閃存（Flash Memory）技術達到存儲電子信息的存儲器，一般應用在數碼相機，掌上電腦，MP3等小型數碼產品中作為存儲介質，所以樣子小巧，有如一張卡片，所以稱之為閃存卡。根據不同的生產廠商和不同的應用，閃存卡大概有U盤、SmartMedia（SM卡）、Compact Flash（CF卡）、MultiMediaCard（MMC卡）、Secure Digital（SD卡）、Memory Stick（記憶棒）、XD-Picture Card（XD卡）和微硬盤（MICRODRIVE）。這些閃存卡雖然外觀、規格不同，但是技術原理都是相同的。

NAND FLASH和NOR FLASH都是現在用得比較多的非易失性閃存。
程序的執行過程

執行程序要將程序和數據裝入內存。將用戶源程序變為可在內存中執行的程序，通常需要以下幾個步驟：

編譯：由編譯程序將用戶源代碼編譯成若干個目標模塊。
鏈接：由鏈接程序將編譯后形成的一組目標模塊，以及所需庫函數鏈接在一起，形成一個完整的裝入模塊。
裝入：由裝入程序將裝入模塊裝入內存運行。

程序的鏈接又分為以下幾類：

靜態鏈接：程序在執行前，將各個模塊以及它們需要用到的庫函數鏈接成可執行文件.
裝入時動態鏈接：程序在編譯完之后得到一組目標模塊，在裝入內存時鏈接在一起.
運行時動態鏈接：程序在運行前還是離散的，在運行時把運行所需要的模塊鏈接在一起.

程序的裝入分為以下幾類：

絕對裝入：在編譯時，如果知道程序將駐留在內存的某個位置，編譯程序將產生絕對地址的目標代碼。絕對裝入程序按照裝入模塊中的地址，將程序和數據裝入內存。由于程序中的邏輯地址與實際內存地址完全相同，故不需對程序和數據的地址進行修改。
可重定位裝入：在多道程序環境下，多個目標模塊的起始地址通常都是從 0 開始，程序中的其他地址都是相對于起始地址的,此時應釆用可重定位裝入方式。根據內存的當前情況，將裝入模塊裝入到內存的適當位置。裝入時對目標程序中指令和數據的修改過程稱為重定位，地址變換通常是在裝入時一次完成的，所以又稱為靜態重定位。
靜態重定位的特點是在一個作業裝入內存時，必須分配其要求的全部內存空間，如果沒有足夠的內存，就不能裝入該作業。此外，作業一旦進入內存后，在整個運行期間不能在內存中移動，也不能再申請內存空間。
動態運行時裝入，也稱為動態重定位：程序在內存中如果發生移動，就需要釆用動態的裝入方式。裝入程序在把裝入模塊裝入內存后，并不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執行時才進行。因此，裝入內存后的所有地址均為相對地址。這種方式需要一個重定位寄存器的支持。
動態重定位的特點是可以將程序分配到不連續的存儲區中；在程序運行之前可以只裝入它的部分代碼即可投入運行，然后在程序運行期間，根據需要動態申請分配內存；便于程序段的共享，可以向用戶提供一個比存儲空間大得多的地址空間。

系統分區

內存分為兩個區域，一個用來存放操作系統，一個用來存放用戶進程，當進程調入內存是我們需要為它分配一塊內存空間，在這里我們采用的是連續內存分配，一個進程存放在連續的一段內存空間內。
內存保護

內存保護是為了防止用戶進程影響操作系統或者用戶進進程影響其他進程，操作系統通過采用重定位寄存器和界地址寄存器來實現這種保護，重定位寄存器里面包含最小物理地址，界地址寄存器包含最小的邏輯地址，每個進程的邏輯地址必須小于界地址寄存器，內存管理單元動態地將邏輯地址與界地址進行比較，若未發生越界，則再加上重定位寄存器里的地址值找到物理地址，再送到內存單元。
連續內存分配管理

為了能將程序裝入內存，必須為它分配一定大小的內存空間，連續分配是最早出現的一種存儲器分配方式·，該分配方式為用戶程序分配了一個連續的內存空間，即程序的代碼或者數據的邏輯地址相鄰 ，體現在內存空間分配時物理地址的相鄰。連續分配方式可分為四類：單一連續，固定分區分配，動態分區分配以及可重定位分區分配（緊湊)算法四種方式：

單一連續分配。內存此時分為系統區和用戶區，系統區只分配給操作系統使用，通常在低地址部分；用戶區為用戶提供。內存中只有一道程序，也無需進行內存保護。無外部碎片但是有內部碎片，且存儲器效率低下。
固定分區分配。將內存空間劃分為若干個固定大小的區域，每個分區只能裝入一道作業。當有空閑分區時，便可以再從外存的后備作業隊列中，選擇適當大小的作業裝入該區，分為（分區大小相等和分區大小不相等兩種方式）無外部碎片但是有內部碎片（分區內部有空間的浪費），且存儲器效率低下，但是可存在多道程序，是用于多道程序并發執行的最簡單的內存分配方式。

動態分區分配。也成為可變分區分配，它不預先對內存進行劃分，而是在進程裝入內存時，根據進程的大小動態的建立分區，并使分區的大小正好適合進程的需要，其分區的數目和大小是可變的。但是隨著時間的推移，很容易產生外部碎片，外部碎片指的是分區以外的存儲空間被浪費
基于順序搜索的動態分區分配算法：

首次適應算法，空閑分區以地址遞增的方式鏈接，分配內存時順序查找，找到大小滿足要求的第一個空閑分區，通常該算法是最快最好的也是最簡單的。http://www.daiqiyang.com
最佳適應算法，空閑分區以容量遞增形成分區鏈，找到第一個滿足要求的空閑分區，實際上新能不佳，因為每次最佳分配通常會留下很小的難以利用的內存塊，產生外部碎片。
最壞適應算法，又稱最大適應算法，空閑分區以容量遞減形成分區鏈，找到第一個滿足要求的空閑分區，也就是挑選出最大的分區性能較差，因為算法開銷也是需要考慮的一部分
鄰近適應算法，又稱循環首次適應算法，也就是從首次適應算法中演變而來，不同的是，從上次查找結束的位置開始繼續查找性能較差

分段和分頁機制

要理解分段和分頁，首先我們要知道為什么會出現分段和分頁這兩項技術；

首先我們要知道分段和分頁都是為了更好的管理計算機的資源--內存。

在分段技術還沒出來之前，程序在內存運行之前都是先從內存中尋找找到連續的一片地址空間，比如我們程序A需要10M的空間，那么就要從內存空間里尋找出10M的地址空間，然后再把A裝入進去，如果沒找到連續的空間，那么就不予分配。

從這里我們可以看出以前的內存分配的缺點；

地址空間不隔離，假如我們兩個程序A和B，A存放在0x000001~0x0000999這個內存空間，B存放在0X0001000~0x0001100這個空間里，那如果我們對A的操作地址0x0000500誤寫為0x0001050，那么我們不僅沒有對A實施正確的操作，還影響了程序B的執行。
程序地址的不確定，因為我們現在都是對內存地址直接操作，所以我們程序需要寫死要操作的某個內存的地址，但是如果我們想要操作地址0x0000001000，我們就必須寫死我們要操作的地址為0x0000001000，但是這樣問題來了，我們程序運行時在內存的地址在不同時候可能不一樣，比如我們第一次可能在內存中的地址為0x0000000001~0x00000100000；那么我們第一次操作可能就沒有問題，但是第二次運行時他在內存中的地址可能就變為0x000000100000~0x00000110000，那么我們第二次運行是我們想要操作的地址根本程序占有的內存里，我們可能又誤操作其他程序的數據了。
內存使用率低，假如我們內存大小為70M，我們有A B C三個程序在內存中分別連續占20M  10M  30M的地址空間，當我們B運行完被置換出來時A和C中間就有10M的內存空間，然后我們有大小為11M的程序D想要裝入內存，然后它從內存中尋找一個11M的連續地址空間，然后我找到了兩個10M的地址空間，但是它們是不連續的，所以程序沒辦法裝入內存中，只能等待A或者C運行完才能裝入，這樣這20M的內存空閑地址就沒有被利用起來。

為了解決這些問題，人們就去尋找一種辦法來解決它，所以分段技術就出來了：

為了實現分段技術，人們又引入了虛擬地址空間的概念，什么是虛擬地址空間呢，就是這個空間真實不存在，只是我們為了更好地操作物理地址而引出的一個概念，簡單來說就是我們的程序在運行前它的操作都是虛擬地址；例如，程序A的虛擬地址空間是0x00000100~0x100000200,此時，我們不僅需要一塊連續的物理內存來存放A，還需要把A的虛擬地址映射到物理地址空間，可能A的虛擬地址空間是從0x00000100~0x100000200映射到物理地址空間0x00000000~0x00000100；

那么分段是什么呢？

分段機制就是把虛擬內存組織成一些長度可變的稱為段的內存單元，通過段表來管理這些段，每個段定義了一組邏輯信息，每個程序可以有多個段，如數據段，代碼段等，每個段都是一段連續的地址空間，段的長度由程序的大小決定，所以各個段的長度不等，所以段的地址空間是二維的，由段首地址和段長組成；

分段的作用是什么？

段的共享和保護：在這里我們講一下段的保護機制，段的保護機制分為越界檢查和權限檢查，越界檢查是段表寄存器中存放著段表信息，里面包括段的起始地址和段的長度，在進行存儲訪問時，首先將邏輯地址空間的段號與段表長度進行比較，如果段號等于或大于段表長度，將發出地址越界中斷信號，其次還要檢查段內地址是否大于段長，若大于段長，將產生越界中斷信號，從而保證每個進程只能在自己的地址空間運行。權限檢查就是在段表的每個表項中，都設置了‘存取控制’字段，用于規定對該段的訪問方式，通常的訪問方式有只讀，只執行，讀/寫。通過段保護和共享可以解決一個程序對其他程序的影響的問題。

段的地址變換機制：分段管理可以提供邏輯地址到物理地址的轉換，邏輯地址到物理地址通過地址映射表完成，所以只有虛擬地址沒有改變，那么我們就不需要關心程序在內存的物理地址是什么，所以通過段的地址映射機制可以解決問題2。

但是我們的問題3還是沒有解決，內存的利用率還是沒有解決，所以我們引出了分頁管理

分頁管理是把主存空間分為大小相等且固定的塊，塊的大小較小，作為主存的基本單位，頁表存儲著這些頁的基本信息，每個進程對應一個頁表，（進程中的塊稱之為頁，主存中的塊稱為頁框，外存中稱之為塊，進程在執行時，向主存申請塊，就產生了頁與頁框的一一對應關系）如圖：

如何利用分頁機制解決外部碎片呢，我們利用分頁單元把一組非連續的空閑頁框映射到連續的線性地址，這樣他們在物理上不連續但是在邏輯上是連續的，這樣就是有效的解決外部碎片問題。

而在linux中采用了著名的伙伴算法來解決外部碎片問題。把所有的空閑頁框分組為11個塊鏈表，每個鏈表分別包含大小為1,2,4,8,16,32,64,128,256,512,1024個連續的頁框，對1024個頁框的最大請求對應著4MB大小的連續RAM（每頁大小為4KB），每個塊的第一個頁框的物理地址是該塊大小的整數倍，例如，大小為16個頁框的塊，其起始地址是16*2^12的倍數。
我們通過一個例子來說明伙伴算法的工作原理，假設現在要請求一個256個頁框的塊（1MB），算法步驟如下：
? 在256個頁框的鏈表中檢查是否有一個空閑快，如果沒有，查找下一個更大的塊，如果有，請求滿足。
? 在512個頁框的鏈表中檢查是否有一個空閑塊，如果有，把512個頁框的空閑塊分為兩份，第一份用于滿足請求，第二份鏈接到256個頁框的鏈表中。如果沒有空閑塊，繼續尋找下一個更大的塊。如圖：

以上過程的逆過程，就是頁框塊的釋放過程，也是該算法名字的由來，內核試圖把大小為B的一對空閑伙伴塊合并為一個2B的單獨塊，滿足以下條件的兩個塊稱之為伙伴：
? 兩個塊具有相同的大小http://www.daiqiyang.com
? 他們的物理地址是連續的
第一塊的第一個頁框的物理地址是2 B 2^12
該算法是遞歸的，如果它成功合并了B，就會試圖去合并2B，以再次試圖形成更大的塊。

分段和分頁是區別：

1、分頁機制會使用大小固定的內存塊，而分段管理則使用了大小可變的塊來管理內存。

2、分頁使用固定大小的塊更為適合管理物理內存，分段機制使用大小可變的塊更適合處理復雜系統的邏輯分區。

3、段表存儲在線性地址空間，而頁表則保存在物理地址空間。

4，分頁的作業地址空間是一維的，即單一的線性空間，程序員只須利用一個記憶符（線性地址的16進制表示），即可表示一地址。

分段的作業地址空間是二維的，程序員在標識一個地址時，既需給出段名（比如數據段、代碼段和堆棧段等），又需給出段內地址。