內(nèi)存管理基礎(chǔ)

程序的裝入與連接

將用戶的源程序變成一個可在內(nèi)存執(zhí)行的程序的步驟：

1. 編譯召锈，由編譯程序?qū)⒃创a編譯成目標(biāo)模塊沛厨；
2. 鏈接，由鏈接程序?qū)⒕幾g后的目標(biāo)模塊和它們的庫函數(shù)鏈接成完整的裝入模塊龄句；
3. 裝入傀蚌，由裝入程序?qū)⒀b入模塊裝入內(nèi)存勋桶；

邏輯地址：編譯后甜无，每個目標(biāo)模塊都從0單元開始編址，這稱為目標(biāo)模塊的相對地址（邏輯地址）哥遮，編程使用的地址岂丘，有了邏輯地址才能使用虛擬內(nèi)存

物理地址：內(nèi)存單元真正的地址，當(dāng)裝入程序?qū)⒖蓤?zhí)行代碼裝入內(nèi)存時眠饮，必須通過地址轉(zhuǎn)換將邏輯地址轉(zhuǎn)化為物理地址

內(nèi)存保護(hù)：

內(nèi)存分配前奥帘，需要保證操作系統(tǒng)不受用戶進(jìn)程影響，用戶進(jìn)程不受其他進(jìn)程影響仪召，所有需要進(jìn)行內(nèi)存保護(hù)：

• 在CPU中設(shè)置上寨蹋，下限寄存器,存放用戶作業(yè)在主內(nèi)存中的上限和下限地址，每當(dāng)CPU訪問內(nèi)存地址時扔茅，都會和這連個寄存器地址比較已旧，不能越界；
• 采用界地址寄存器和重定位寄存器召娜，界限地址寄存器存放最大的邏輯地址运褪，重定位寄存器存放最小的物理地址；內(nèi)存管理機(jī)構(gòu)將CPU要執(zhí)行的邏輯地址和界地址寄存器比較，如果不越界秸讹，則加上重定位寄存器的值映射成物理地址檀咙，再交給內(nèi)存單元；
  

內(nèi)存分配方式：

連續(xù)分配方式：

為用戶程序分配一個連續(xù)的內(nèi)存空間

1. 單一連續(xù)分配

將內(nèi)存分為系統(tǒng)區(qū)璃诀，用戶區(qū)弧可，系統(tǒng)區(qū)供操作系統(tǒng)使用，除系統(tǒng)區(qū)外剩下的部分為用戶區(qū)劣欢，用戶區(qū)只能放一個程序（單用戶棕诵，單任務(wù)）；

2. 固定分區(qū)分配

將用戶區(qū)分為若干個分區(qū)凿将，每個分區(qū)可以放一個作業(yè)年鸳，固定分區(qū)分配有兩種實(shí)現(xiàn)方式：

• 大小相等分區(qū)
• 大小不等分區(qū)

• 程序可能太大不能放入內(nèi)存分區(qū)
• 程序太小會造成內(nèi)存分區(qū)的浪費(fèi)內(nèi)部碎片
• 不能實(shí)現(xiàn)多進(jìn)程共享一塊內(nèi)存分區(qū)

3. 動態(tài)分區(qū)分配

將用戶區(qū)內(nèi)存根據(jù)進(jìn)程的大小動態(tài)的建立分區(qū)，分區(qū)的大小和數(shù)目可變丸相；

特點(diǎn)：

會產(chǎn)生外部碎片（撤銷大進(jìn)程，放入小進(jìn)程多出來的空間就是外部碎片）彼棍，可以通過緊湊（操作系統(tǒng)不時的對進(jìn)程進(jìn)行移動和整理）來解決外部碎片灭忠；

非連續(xù)分配方式：

一個程序分散的裝入不連續(xù)的內(nèi)存分區(qū)

1. 分頁存儲方式

把主存空間劃分為大小相等且固定的塊，塊相對較小座硕，作為主存的基本單位弛作，每個進(jìn)程已塊為單位進(jìn)行劃分，進(jìn)程執(zhí)行時逐個申請塊空間华匾；

分頁存儲方式的概念：

• 頁（頁面）：一個進(jìn)程的邏輯地址空間分成若干個大小相等的頁映琳，并為各頁加以編號，第0頁蜘拉，第1頁萨西，第2頁；

• 塊（頁框旭旭，頁幀）：內(nèi)存空間分成和頁面大小相同的若干個存儲塊谎脯，以塊為單位，將進(jìn)程中的若干個頁分別裝入不相鄰的物理塊中持寄；由于進(jìn)程的最后一頁可能裝不滿一個進(jìn)程塊源梭，所以會產(chǎn)生頁內(nèi)碎片

• 頁面大小：頁面如果太小稍味，一方面可以減小頁內(nèi)碎片废麻，提高內(nèi)存利用率，另一方面會使進(jìn)程占用過多的內(nèi)存塊模庐，導(dǎo)致頁表過長烛愧，降低頁面換進(jìn)換出的效率；如果頁面太大，可以提高頁面換進(jìn)換出的效率屑彻，但是會使頁內(nèi)碎片增大验庙；使用頁面的大小應(yīng)該適中，通常是512B-8KB（2的冪）

• 地址結(jié)構(gòu)（邏輯地址）：包含兩部分社牲，第一部分是頁號P粪薛，第二部分是位移量W（頁內(nèi)地址），地址結(jié)構(gòu)決定了虛擬內(nèi)存的尋址空間有多大搏恤；
  

  分頁存儲方式的邏輯地址

• 頁表：頁面映射表违寿，進(jìn)程在執(zhí)行時，通過查找該表熟空，即可找到每一頁在內(nèi)存中的物理塊藤巢；

地址轉(zhuǎn)換：

借助頁表將邏輯地址轉(zhuǎn)為物理地址

• 根據(jù)邏輯地址A和頁面大小L計算頁號（A/L）和頁內(nèi)偏移量(A%L)；
• 判斷頁號是否越界挨摸，越界則中斷孩革；
• 根據(jù)頁表寄存器計算出當(dāng)前頁號在頁表中的位置(頁表起始地址+頁號*頁表項(xiàng)長度)，找到對應(yīng)的物理塊號得运，即物理地址

2. 分段存儲方式

分段存儲管理的提出主要是為了滿足編程膝蜈，信息保護(hù)和共享，動態(tài)增長及動態(tài)鏈接的需要熔掺；
將用戶進(jìn)程按照邏輯結(jié)構(gòu)劃分為多個段（段內(nèi)要求連續(xù)饱搏，段間不要求連續(xù)），用戶進(jìn)程由主程序置逻，兩個子程序窍帝，棧，數(shù)據(jù)組成诽偷，可以將程序分成五個段坤学；

• 邏輯地址：
  

• 段表：段表記錄段在內(nèi)存中的起始地址和段長度，執(zhí)行中的進(jìn)程通過查找段表报慕，找到每個段對應(yīng)的內(nèi)存區(qū)深浮；
  

地址轉(zhuǎn)換：

• 從邏輯地址中取出段號和偏移量
• 段號越界中斷的判斷
• 計算段號S在段表中的位置：段表起始地址F + 段號S*段表項(xiàng)長度,找到位置后查找段長C，再次進(jìn)行中斷判斷：段內(nèi)偏移量＞段長C眠冈，則中斷
• 根據(jù)段表中的基址（始址）b飞苇，物理地址E = b + w菌瘫；

3. 段頁式存儲方式：

頁式存儲能提高內(nèi)存的利用率，段式存儲能反應(yīng)程序的邏輯結(jié)構(gòu)布卡，有利于數(shù)據(jù)共享雨让，段頁式存儲將這兩種存儲方式結(jié)合起來

段頁式存儲實(shí)現(xiàn)思路：

將用戶程序首先分成邏輯段，每個段有段號忿等，再將邏輯段分成固定大小的頁栖忠；將內(nèi)存空間按照頁式存儲一樣分成和頁面大小相等的存儲塊；

邏輯地址：

段號+頁號+頁偏移量

段頁式存儲管理地址轉(zhuǎn)換：

• 首先用邏輯地址中的段號S和段表長度做中斷判斷
• 然后利用段號S和段表起始地址查詢段表中的頁表始址
• 頁號P和頁表始址計算出頁表項(xiàng)位置及其對應(yīng)的物理塊

虛擬內(nèi)存

局部性原理：

• 事件局部性：程序的某條指令被執(zhí)行贸街，不久后該指令可能再次被執(zhí)行庵寞；某數(shù)據(jù)被訪問，不久后可能再次被訪問薛匪；
• 空間局部性：一旦程序訪問了某個存儲單元捐川，不久后其附近的存儲單元也會被訪問，即在一段時間內(nèi)所訪問的地址可能集中在一定范圍內(nèi)逸尖；

虛擬內(nèi)存的定義：

基于局部性古沥，在程序裝入內(nèi)存時，可以將一部分（即將執(zhí)行的部分）裝入內(nèi)存娇跟，其余部分（暫不執(zhí)行的部分）留在外存岩齿，就可以啟動程序；在程序執(zhí)行過程中逞频，如果需要訪問的信息不在內(nèi)存，操作系統(tǒng)就會將外存的部分調(diào)入內(nèi)存栋齿，相反苗胀，如果內(nèi)存中的某部分暫不使用就會調(diào)出內(nèi)存到外存中；

系統(tǒng)提供了部分裝入瓦堵，請求調(diào)入基协，置換功能，給用戶的感覺就是在使用一個比實(shí)際物理內(nèi)存大的多的存儲器,虛擬內(nèi)存的大小由計算機(jī)的邏輯地址決定

請求分頁管理方式：

請求分頁管理方式建立在基本分頁管理方式的基礎(chǔ)上菇用，增加了調(diào)頁功能和頁面置換功能,是目前最常用的一種實(shí)現(xiàn)虛擬內(nèi)存的方式澜驮；

• 調(diào)頁功能：程序在執(zhí)行時，當(dāng)所訪問的頁面不在內(nèi)存中惋鸥，就會使用調(diào)頁功能將其調(diào)入內(nèi)存杂穷；

• 頁面置換功能：將暫時不用的頁面換出到外存上

頁面置換算法（決定換入哪頁，換出哪也）：

1. 最佳置換算法（OPT）：

選擇以后永不使用的頁面卦绣，或是在最長時間內(nèi)部不再被訪問的頁面耐量，保證最低的缺頁率，由于人們無法預(yù)知進(jìn)程在內(nèi)存中的若干頁面中哪個是未來最長時間不再被訪問的滤港，所以該算法無法實(shí)現(xiàn)廊蜒；

2. 先進(jìn)先出頁面置換算法（FIFO）：

優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁面，該算法實(shí)現(xiàn)簡單，可以使用隊(duì)列來做山叮，但是該算法與進(jìn)程的實(shí)際運(yùn)行規(guī)律不符合著榴，有些頁面會經(jīng)常訪問；
FIFO算法會出現(xiàn) 物理塊數(shù)增加屁倔，故障頁數(shù)也增加的異衬杂郑現(xiàn)象（BeLady現(xiàn)象）

3. 最近最久未使用置換算法（LRU）：

選擇最近最長時間未被訪問過的頁面予以淘汰，該算法為每一個頁面設(shè)置一個字段汰现，用來記錄從上次被訪問到現(xiàn)在的時間挂谍，淘汰頁面時選擇現(xiàn)有頁面中最大值；
LRU算法性能較好瞎饲，但需要寄存器和棧的硬件支持口叙，不會出現(xiàn)BeLady異常

4. 時鐘置換算法（Clock）：

LRU算法的性能好但是實(shí)現(xiàn)難，開銷大嗅战，Clock算法是一種LRU近似算法妄田；

1. 簡單的Clock算法：

為每一頁設(shè)置一個訪問位,再將內(nèi)存中所有頁面連成一個循環(huán)隊(duì)列，當(dāng)一個頁面被訪問時驮捍，將其訪問位置為1疟呐，在選擇淘汰頁面時，按著FIFO檢查隊(duì)列中的頁面东且，如果其訪問位是0启具，就換出，如果是1珊泳，就置為0鲁冯，暫不換出，給該頁第二次駐留的機(jī)會色查，訪問下一個薯演；

2. 改進(jìn)的Clock算法：

在改進(jìn)Clock算法中，除了考慮頁面使用情況秧了，還增加了一個因素置換代價跨扮，選擇淘汰頁面，既要選擇未被使用的验毡，又要選擇未被修改的衡创；

將頁面分為四類：

1. 未被訪問，未被修改晶通；最佳淘汰（A = 0钧汹，M = 0）
2. 未被訪問，已被修改录择；不是很好的淘汰頁（A = 0拔莱，M = 1）
3. 已被訪問碗降，未被修改；可能再被訪問（A = 1塘秦，M = 0）
4. 已被訪問讼渊，已被修改；可能再被訪問（A = 1尊剔，M = 1）

改進(jìn)Clock算法思想：

1. 遍歷循環(huán)隊(duì)列爪幻，尋找最佳淘汰（A = 0，M = 0）须误，找到則淘汰
2. 如果第一步?jīng)]有找到挨稿，開始第二輪掃描，尋找第二類頁面（A = 0京痢，M = 1）奶甘，找到的第一個作為淘汰頁，并且將掃描過的所有頁面訪問位都設(shè)置為0祭椰；
3. 如果第二步還沒有找到臭家，就再次重復(fù)第一步，如果還沒有方淤，再次重復(fù)第二步钉赁，此時肯定會找到；

頁面分配策略：

1. 固定分配局部置換：為每一個進(jìn)程分配固定的物理塊携茂，物理塊的數(shù)量在程序的整個運(yùn)行過程都不變你踩，如果程序發(fā)生缺頁，則會在當(dāng)前程序的頁面中選出一個頁面淘汰讳苦，置換外存需要的頁面带膜；

這種策略難以確定物理塊的數(shù)量，過多會導(dǎo)致CPU利用率下降氓侧，過少會導(dǎo)致程序頻繁缺頁蒲稳，頁面切入切出的概率增大

2. 可變分配全局置換：首先為進(jìn)程分配一定數(shù)量的物理塊，操作系統(tǒng)會預(yù)留一些空閑的物理塊，如果一個進(jìn)程發(fā)生缺頁连躏，就會在預(yù)留的物理塊隊(duì)列中取出一個空閑物理塊分配給它使用；

這種方式比較靈活世囊，可以動態(tài)增加進(jìn)程物理塊的數(shù)量该抒，但是盲目的增加物理塊會降低系統(tǒng)的并發(fā)能力

3. 可變分配局部置換：為每一個進(jìn)程分配一定數(shù)量的物理塊，當(dāng)進(jìn)程缺頁時策严，只能置換當(dāng)前進(jìn)程的頁面穗慕，如果進(jìn)程頻繁的發(fā)生缺頁置換，系統(tǒng)就會再次為它分配一些物理塊妻导，如果一個進(jìn)程缺頁率減少逛绵，系統(tǒng)就會減少此進(jìn)程的物理塊數(shù)量怀各；

可以動態(tài)的增加和減少物理塊，保證了系統(tǒng)的并發(fā)能力

調(diào)入頁面的時機(jī)

1. 預(yù)調(diào)頁策略：預(yù)計在不久后會訪問的頁面預(yù)先調(diào)入內(nèi)存术浪，這種策略主要用于進(jìn)程的首次調(diào)入瓢对，成功率只有50%；

2. 請求調(diào)頁策略：進(jìn)程在運(yùn)行中需要訪問的頁面不在內(nèi)存中則會發(fā)出頁面調(diào)入的請求胰苏，這種策略易于實(shí)現(xiàn)硕蛹，目前大多虛擬存儲器采用此策略；

從何處調(diào)入頁面

外存分為兩部分：文件區(qū)（存放文件）硕并，對換區(qū)（存放對換頁面）

• 對換區(qū)空間充足：全部從對換區(qū)調(diào)入

• 對換區(qū)空間不足：不會被修改的文件從文件區(qū)調(diào)入法焰，可能被修改的部分，先調(diào)到對換區(qū)倔毙，再從對換區(qū)調(diào)入埃仪；

• UNIX方式：為運(yùn)行過的頁面從文件區(qū)調(diào)入，運(yùn)行過但又被換出的頁面從對換區(qū)調(diào)入普监；