連續(xù)分配方式：一個(gè)進(jìn)程連續(xù)的裝進(jìn)內(nèi)存一個(gè)大小合適的區(qū)。
????->“碎片”->“緊湊”->增大開(kāi)銷(xiāo)
如果允許一個(gè)進(jìn)程直接分散裝入多個(gè)不相鄰分區(qū)中，則無(wú)需“緊湊”
產(chǎn)生存儲(chǔ)管理的離散分配方式。
3. 基本分頁(yè)存儲(chǔ)管理方式
本部分討論不具備對(duì)換功能的純分頁(yè)模式，作業(yè)運(yùn)行需要全部裝入內(nèi)存。
比較連續(xù)分配方式
????作業(yè)邏輯地址空間有M大，就需要向內(nèi)存申請(qǐng)一個(gè)M大的連續(xù)區(qū)域。
????分頁(yè)的目的是更細(xì)粒度的處理空間，減少粗放管理的浪費(fèi)或開(kāi)銷(xiāo)問(wèn)題。
離散分配內(nèi)存：
????作業(yè)規(guī)定大小劃分成小份；內(nèi)存也按同樣大小劃分成小份
????作業(yè)的任一小份可分散放入內(nèi)存任意未使用的小份
分頁(yè)方式下，內(nèi)存的使用率高，浪費(fèi)少。但不是絕對(duì)沒(méi)有碎片（進(jìn)程的最后一頁(yè)不總是能占滿(mǎn)一個(gè)物理塊）
1）頁(yè)面的概念
內(nèi)存劃分成多個(gè)小單元，每個(gè)單元K大小，稱(chēng)（物理）塊。作業(yè)也按K單位大小劃分成片，稱(chēng)為頁(yè)面。
????① 物理劃分塊的大小 = 邏輯劃分的頁(yè)的大小
????②頁(yè)面大小要適中。太大，（最后一頁(yè)）內(nèi)碎片增大，類(lèi)似連續(xù)分配的問(wèn)題。太小的話(huà)，頁(yè)面碎片總空間雖然小，提高了利用率，但每個(gè)進(jìn)程的頁(yè)面數(shù)量較多，頁(yè)表過(guò)長(zhǎng)，反而又增加了空間使用。
2）頁(yè)表的概念
????為了找到被離散分配到內(nèi)存中的作業(yè)，記錄每個(gè)作業(yè)各頁(yè)映射到哪個(gè)物理塊，形成的頁(yè)面映射表，簡(jiǎn)稱(chēng)頁(yè)表。
????每個(gè)作業(yè)有自己的頁(yè)表
????頁(yè)表的作用：
????????頁(yè)號(hào)到物理塊號(hào)的地址映射
????要找到作業(yè)A
????????關(guān)鍵是找到頁(yè)表（PCB）
????????根據(jù)頁(yè)表找物理塊
3）地址的處理
連續(xù)方式下，每條指令用基地址+偏移量即可找到其物理存放的地址。
分頁(yè)方式下詳細(xì)的地址處理會(huì)如何呢？
地址映射（地址計(jì)算）的過(guò)程？
????若要執(zhí)行某作業(yè)的一條指令，其相對(duì)地址是24B （設(shè)10B一頁(yè)，頁(yè)表如右表），其物理地址到底是多少呢？
????????分析其所在的頁(yè)和偏移得：2號(hào)頁(yè)（頁(yè)號(hào)從0開(kāi)始） ，偏移4B處是該條指令
????????查頁(yè)表找頁(yè)面對(duì)應(yīng)的塊（2號(hào)頁(yè)保存在6號(hào)物理塊）
????????找物理塊6，向下偏移4B，找到要執(zhí)行的指令。取出執(zhí)行即可。
????????計(jì)算上就是求商（頁(yè)號(hào)）及取余（偏移量）的過(guò)程
規(guī)律
????作業(yè)相對(duì)地址在分頁(yè)下不同位置的數(shù)有一定的意義結(jié)構(gòu)：
????????頁(yè)號(hào)+頁(yè)內(nèi)地址（即頁(yè)內(nèi)偏移）
????關(guān)鍵的計(jì)算是：根據(jù)系統(tǒng)頁(yè)面大小找到不同意義二進(jìn)制位的分界線(xiàn)。
????從地址中分析出頁(yè)號(hào)后，地址映射只需要把頁(yè)號(hào)改為對(duì)應(yīng)物理塊號(hào)，偏移不變，即可找到內(nèi)存中實(shí)際位置。
注意：一作業(yè)所有指令在用戶(hù)地址空間是順序編址
上例若作業(yè)頁(yè)表如右表所示，任意取一用戶(hù)程序指令，如第1011個(gè)指令，如何知道放在內(nèi)存的哪里？
????重要參數(shù)：系統(tǒng)頁(yè)面大小=8B
????????頁(yè)內(nèi)的所有指令編址用了3位
????????111增一后進(jìn)位，下一條第9條指令已經(jīng)到了下一頁(yè)1000
????????1011中的1代表是1號(hào)頁(yè)，而011代表是該頁(yè)中偏移3B后的第4條，
????根據(jù)頁(yè)表，1號(hào)頁(yè)存在7#物理塊上。
????7#物理塊又在哪？
????????物理塊的編址也是8B大小決定的，地址結(jié)構(gòu)類(lèi)似
????????7#塊的第一條指令地址是111000。第7塊中向下偏移3就是要找的指令。其地址就是111011。
4）地址變換機(jī)構(gòu)
????前面講解了地址變換的原理，那么誰(shuí)具體實(shí)現(xiàn)地址映射？——地址變換機(jī)構(gòu)。
????圍繞頁(yè)表進(jìn)行工作，那么頁(yè)表數(shù)據(jù)放在哪？
????????寄存器。一個(gè)進(jìn)程有n個(gè)頁(yè)，頁(yè)表就需要記錄n項(xiàng)數(shù)據(jù)，需要n個(gè)寄存器。不現(xiàn)實(shí)。
????????內(nèi)存。只設(shè)置一個(gè)頁(yè)表寄存器PTR（page table register）記錄頁(yè)表在內(nèi)存中的首地址和頁(yè)表長(zhǎng)度，運(yùn)行時(shí)快速定位頁(yè)表。
地址變換過(guò)程
分頁(yè)系統(tǒng)中，進(jìn)程創(chuàng)建，放入內(nèi)存，構(gòu)建頁(yè)表，在PCB中記錄頁(yè)表存放在內(nèi)存的首地址及頁(yè)表長(zhǎng)度。
????運(yùn)行某進(jìn)程A時(shí)，將A進(jìn)程PCB中的頁(yè)表信息寫(xiě)入PTR中；
????每執(zhí)行一條指令時(shí)，根據(jù)分頁(yè)計(jì)算原理，得到指令頁(yè)號(hào)X和內(nèi)部偏移量Y；
????CPU高速訪(fǎng)問(wèn)PTR找到頁(yè)表在哪里；
????查頁(yè)表數(shù)據(jù)，得到X實(shí)際對(duì)應(yīng)存放的物理塊，完成地址映射計(jì)算，最終在內(nèi)存找到該指令。
訪(fǎng)問(wèn)內(nèi)存的有效時(shí)間
進(jìn)程發(fā)出邏輯地址的訪(fǎng)問(wèn)請(qǐng)求，經(jīng)過(guò)地址變換，到內(nèi)存中找到對(duì)應(yīng)的實(shí)際物理地址單元并取出數(shù)據(jù)，所需花費(fèi)的總時(shí)間，稱(chēng)為內(nèi)存的有效訪(fǎng)問(wèn)時(shí)間EAT（effective access time）
設(shè)訪(fǎng)問(wèn)一次內(nèi)存時(shí)間為t，則基本分頁(yè)機(jī)制下EAT=2t，why？
????CPU操作一條指令需訪(fǎng)問(wèn)內(nèi)存兩次：
????????訪(fǎng)問(wèn)內(nèi)存中的頁(yè)表（以計(jì)算指令所在的實(shí)際物理地址）
????????訪(fǎng)問(wèn)指令內(nèi)存地址
5）引入快表——針對(duì)訪(fǎng)問(wèn)速度問(wèn)題
問(wèn)題：基本分頁(yè)機(jī)制下，一次指令需兩次內(nèi)存訪(fǎng)問(wèn)，處理機(jī)速度降低1/2，分頁(yè)空間效率的提高以如此的速度為代價(jià)，得不償失。
改進(jìn)：減少第1步訪(fǎng)問(wèn)內(nèi)存的時(shí)間。增設(shè)一個(gè)具有“并行查詢(xún)”能力的高速緩沖寄存器，稱(chēng)為“快表”，也稱(chēng)“聯(lián)想寄存器”（Associative memory），IBM系統(tǒng)稱(chēng)為T(mén)LB（Translation Look aside Buffer）。
快表放什么？：
????正在執(zhí)行進(jìn)程的頁(yè)表的數(shù)據(jù)項(xiàng)。
引入快表后的內(nèi)存訪(fǎng)問(wèn)時(shí)間如何？
????快表的寄存器單元數(shù)量是有限的，不能裝下一個(gè)進(jìn)程的所有頁(yè)表項(xiàng)。雖不能完全避免兩次訪(fǎng)問(wèn)內(nèi)存，但如果命中率a高還是能大幅度提高速度。
????設(shè)一次查找訪(fǎng)問(wèn)快表時(shí)間為t' ，則
? ????EAT= a*t' + (1-a)(t'+t)? ? +? ? t
? ? ???? = 2t +t' -t*a
6）兩級(jí)、多級(jí)頁(yè)表，反置頁(yè)表?——針對(duì)大頁(yè)表占用內(nèi)存問(wèn)題
頁(yè)表大小的討論
????進(jìn)程分頁(yè)離散存放，但頁(yè)表的數(shù)據(jù)是連續(xù)在存放內(nèi)存的。而頁(yè)表可能很大：
????????現(xiàn)代操作系統(tǒng)支持非常大的邏輯地址空間的進(jìn)程。如32位系統(tǒng)，可編址的最大代碼數(shù)為232，若頁(yè)面大小為4KB（4*210），則支持的最大進(jìn)程頁(yè)表項(xiàng)數(shù)可達(dá)碼232/212=220，有1M個(gè)，每個(gè)頁(yè)表項(xiàng)占1B（字節(jié)），則頁(yè)表大小就有1MB。
①兩級(jí)頁(yè)表
將頁(yè)表分頁(yè)，并離散地將頁(yè)表的各個(gè)頁(yè)面分別存放在不同的物理塊中
為離散分配的頁(yè)表再建立一張頁(yè)表，稱(chēng)為“外層頁(yè)表”，其每個(gè)表項(xiàng)記錄了頁(yè)表頁(yè)面所在的物理塊號(hào)。
32位邏輯地址空間，頁(yè)面大小為4KB(即12位)
一級(jí)頁(yè)表機(jī)構(gòu)，剩余20位是頁(yè)號(hào)，可編出的220個(gè)頁(yè)（也即頁(yè)表長(zhǎng)1M/或頁(yè)表項(xiàng)有1M個(gè)）；
兩級(jí)頁(yè)表：討論頁(yè)表的分頁(yè)
分頁(yè)原理類(lèi)似：
將頁(yè)表也按4K大小分頁(yè)（212）
頁(yè)表被分頁(yè)后，頁(yè)表的一個(gè)外頁(yè)4K，外頁(yè)偏移量需10位，為什么？
課本將頁(yè)表每1024個(gè)頁(yè)表項(xiàng)就分一外頁(yè)，外頁(yè)內(nèi)的偏移需要10位?？衫斫鉃槊總€(gè)頁(yè)表項(xiàng)占4B(塊號(hào)、權(quán)限等)，如此一外頁(yè)頁(yè)表信息才占滿(mǎn)一個(gè)4KB大小的物理塊
②多級(jí)頁(yè)表
64位操作系統(tǒng)下，兩級(jí)仍然不足以解決頁(yè)表過(guò)大問(wèn)題時(shí)，可按同樣道理繼續(xù)分頁(yè)下去形成多級(jí)頁(yè)表。
③反置頁(yè)表
每個(gè)進(jìn)程一張頁(yè)表
一張OS 反置頁(yè)表 + 每進(jìn)程一張外部頁(yè)表
反置頁(yè)表（Inverted Page Tale）：站在物理塊的角度，記錄占用它的已調(diào)入內(nèi)存的進(jìn)程標(biāo)識(shí)和頁(yè)號(hào)。系統(tǒng)中只需一張?jiān)摫砑纯?。一個(gè)64MB內(nèi)存，若頁(yè)面大小4KB（64M/4K=2^16=16K個(gè)物理塊），反置頁(yè)表占用64KB（16K*4B）
進(jìn)程外部頁(yè)表（External Page Table）：每個(gè)進(jìn)程一張，記錄進(jìn)程不在內(nèi)存中的那些頁(yè)面所在的外存物理位置。
如何提高檢索反置頁(yè)表速度：內(nèi)存容量大時(shí)，反置頁(yè)表的頁(yè)表項(xiàng)還是會(huì)很大，利用進(jìn)程標(biāo)識(shí)符和頁(yè)號(hào)去檢索一張大的線(xiàn)性表很費(fèi)時(shí)，可利用hash算法提高檢索速度。
4.基本分段存儲(chǔ)管理方式
從提高內(nèi)存利用率角度；
????固定分區(qū)->動(dòng)態(tài)分區(qū)->分頁(yè)
從滿(mǎn)足并方便用戶(hù)（程序員）和使用上的要求角度：
????分段存儲(chǔ)管理：作業(yè)分成若干段，各段可離散放入內(nèi)存，段內(nèi)仍連續(xù)存放。
????????方便編程：如匯編中通過(guò)段：偏移確定數(shù)據(jù)位置
????????信息共享：同地位的數(shù)據(jù)放在一塊方便進(jìn)行共享設(shè)置
????????信息保護(hù)
????????動(dòng)態(tài)增長(zhǎng)：動(dòng)態(tài)增長(zhǎng)的數(shù)據(jù)段事先固定內(nèi)存不方便
????????動(dòng)態(tài)鏈接：往往也是以邏輯的段為單位更方便
1）分段系統(tǒng)的基本原理
????程序通過(guò)分段(segmentation)劃分為多個(gè)模塊，每個(gè)段定義一組邏輯信息。如代碼段（主程序段main，子程序段X）、數(shù)據(jù)段D、棧段S等。
????誰(shuí)決定一個(gè)程序分幾段，每段多大？
????????編譯程序（基于源代碼）
????段的特點(diǎn)
????????每段有自己的名字（一般用段號(hào)做名），都從0編址，可分別編寫(xiě)和編譯。裝入內(nèi)存時(shí)，每段賦予各段一個(gè)段號(hào)。
????????每段占據(jù)一塊連續(xù)的內(nèi)存。（即有離散的分段，又有連續(xù)的內(nèi)存使用）
????????各段大小不等。
分段下的相對(duì)地址：
地址結(jié)構(gòu)：段號(hào) + 段內(nèi)地址
段表：記錄每段實(shí)際存放的物理地址
2）段表與地址變換機(jī)構(gòu)
段是連續(xù)存放在內(nèi)存中。段表中針對(duì)每個(gè)“段編號(hào)”記錄：“內(nèi)存首地址”和“段長(zhǎng)”
同樣有兩次內(nèi)存訪(fǎng)問(wèn)問(wèn)題
解決方法：設(shè)置聯(lián)想寄存器，用于保存最近常用的段表項(xiàng)。
3）分頁(yè)和分段的主要區(qū)別
? ? ①需求：分頁(yè)是出于系統(tǒng)管理的需要，是一種信息的物理劃分單位，分段是出于用戶(hù)應(yīng)用的需要，是一種邏輯單位，通常包含一組意義相對(duì)完整的信息。
????????一條指令或一個(gè)操作數(shù)可能會(huì)跨越兩個(gè)頁(yè)的分界處，而不會(huì)跨越兩個(gè)段的分界處。
? ? ②大?。喉?yè)大小是系統(tǒng)固定的，而段大小則通常不固定。分段沒(méi)有內(nèi)碎片，但連續(xù)存放段產(chǎn)生外碎片，可以通過(guò)內(nèi)存緊縮來(lái)消除。相對(duì)而言分頁(yè)空間利用率高。
? ? ③邏輯地址：
????????分頁(yè)是一維的，各個(gè)模塊在鏈接時(shí)必須組織成同一個(gè)地址空間；
????????分段是二維的，各個(gè)模塊在鏈接時(shí)可以每個(gè)段組織成一個(gè)地址空間。
? ? ④其他：通常段比頁(yè)大，因而段表比頁(yè)表短，可以縮短查找時(shí)間，提高訪(fǎng)問(wèn)速度。分段模式下，還可針對(duì)不同類(lèi)型采取不同的保護(hù)；按段為單位來(lái)進(jìn)行共享
4）信息共享
分段系統(tǒng)的突出優(yōu)點(diǎn)：
????易于實(shí)現(xiàn)共享
????????在分段系統(tǒng)中，實(shí)現(xiàn)共享十分容易，只需在每個(gè)進(jìn)程的段表中為共享程序設(shè)置一個(gè)段表項(xiàng)。
????????比較課本圖。對(duì)同樣的共享內(nèi)容的管理上，很明顯分段的空間管理更簡(jiǎn)單。分頁(yè)的圖涉及太多的頁(yè)面劃分和地址記錄的管理。
????易于實(shí)現(xiàn)保護(hù)：
????????代碼的保護(hù)和其邏輯意義有關(guān)，分頁(yè)的機(jī)械式劃分不容易實(shí)現(xiàn)。
分頁(yè)容易造成共享和非共享數(shù)據(jù)共處一頁(yè)，不方便設(shè)置權(quán)限。
????可重入代碼：
????????又稱(chēng)為純代碼，允許多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)的代碼
????????不允許任何進(jìn)程對(duì)它進(jìn)行修改。
????????可共享的代碼必須是可重入的；
5）段頁(yè)式存儲(chǔ)管理方式
① 基本原理
將用戶(hù)程序分成若干段，并為每個(gè)段賦予一個(gè)段名。
把每個(gè)段分成若干頁(yè)
地址結(jié)構(gòu)包括段號(hào)、段內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)地址三部分
②地址變換過(guò)程
進(jìn)程的虛存空間是映射的基礎(chǔ)
Linux僅把運(yùn)行進(jìn)程當(dāng)前使用的少量頁(yè)面裝入內(nèi)存（內(nèi)存分配）
地址映射。若訪(fǎng)問(wèn)的虛頁(yè)不在內(nèi)存，產(chǎn)生一個(gè)頁(yè)故障并報(bào)告故障原因，再通過(guò)請(qǐng)頁(yè)機(jī)制將其調(diào)入內(nèi)存。（請(qǐng)頁(yè)、交換）
linux下虛擬空間的管理
malloc分配的是虛存區(qū)，只有內(nèi)核管理為進(jìn)程創(chuàng)建空間，由內(nèi)核代碼實(shí)際執(zhí)行alloc_pages()等內(nèi)核函數(shù)時(shí)才真正分配內(nèi)存
現(xiàn)階段分配方式的不足：
基本分頁(yè)/分段方式都是進(jìn)程全部裝入內(nèi)存的方式。內(nèi)存空間使用上仍有局限。
虛擬存儲(chǔ)管理：請(qǐng)求式分頁(yè)/分段
