操作系統(tǒng)概述（二）

操作系統(tǒng)內(nèi)存管理

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

我們先來了解一下什么是內(nèi)存：

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

講到內(nèi)存我們可以講一下關(guān)于存儲器的分類：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

NAND FLASH和NOR FLASH都是現(xiàn)在用得比較多的非易失性閃存。
程序的執(zhí)行過程

執(zhí)行程序要將程序和數(shù)據(jù)裝入內(nèi)存。將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序，通常需要以下幾個步驟：

編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊。
鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及所需庫函數(shù)鏈接在一起，形成一個完整的裝入模塊。
裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存運行。

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

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

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

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

系統(tǒng)分區(qū)

內(nèi)存分為兩個區(qū)域，一個用來存放操作系統(tǒng)，一個用來存放用戶進程，當(dāng)進程調(diào)入內(nèi)存是我們需要為它分配一塊內(nèi)存空間，在這里我們采用的是連續(xù)內(nèi)存分配，一個進程存放在連續(xù)的一段內(nèi)存空間內(nèi)。
內(nèi)存保護

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

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

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

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

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

分段和分頁機制

要理解分段和分頁，首先我們要知道為什么會出現(xiàn)分段和分頁這兩項技術(shù)；

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

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

從這里我們可以看出以前的內(nèi)存分配的缺點；

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

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

為了實現(xiàn)分段技術(shù)，人們又引入了虛擬地址空間的概念，什么是虛擬地址空間呢，就是這個空間真實不存在，只是我們?yōu)榱烁玫夭僮魑锢淼刂范龅囊粋€概念，簡單來說就是我們的程序在運行前它的操作都是虛擬地址；例如，程序A的虛擬地址空間是0x00000100~0x100000200,此時，我們不僅需要一塊連續(xù)的物理內(nèi)存來存放A，還需要把A的虛擬地址映射到物理地址空間，可能A的虛擬地址空間是從0x00000100~0x100000200映射到物理地址空間0x00000000~0x00000100；

那么分段是什么呢？

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

分段的作用是什么？

段的共享和保護：在這里我們講一下段的保護機制，段的保護機制分為越界檢查和權(quán)限檢查，越界檢查是段表寄存器中存放著段表信息，里面包括段的起始地址和段的長度，在進行存儲訪問時，首先將邏輯地址空間的段號與段表長度進行比較，如果段號等于或大于段表長度，將發(fā)出地址越界中斷信號，其次還要檢查段內(nèi)地址是否大于段長，若大于段長，將產(chǎn)生越界中斷信號，從而保證每個進程只能在自己的地址空間運行。權(quán)限檢查就是在段表的每個表項中，都設(shè)置了‘存取控制’字段，用于規(guī)定對該段的訪問方式，通常的訪問方式有只讀，只執(zhí)行，讀/寫。通過段保護和共享可以解決一個程序?qū)ζ渌绦虻挠绊懙膯栴}。

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

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

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

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

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

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

分段和分頁是區(qū)別：

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

2、分頁使用固定大小的塊更為適合管理物理內(nèi)存，分段機制使用大小可變的塊更適合處理復(fù)雜系統(tǒng)的邏輯分區(qū)。

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

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

分段的作業(yè)地址空間是二維的，程序員在標(biāo)識一個地址時，既需給出段名（比如數(shù)據(jù)段、代碼段和堆棧段等），又需給出段內(nèi)地址。