非連續(xù)分配允許一個程序分散地裝入到不相鄰的內(nèi)存分區(qū)中砌创，根據(jù)分區(qū)的大小是否固定分為分頁存儲管理方式和分段存儲管理方式。在分頁存儲管理方式中鲫懒，如果不具備頁面對換功能嫩实，則稱為基本分頁存儲管理方式，或純分頁管理方式窥岩。
基本分頁存儲管理方式
固定分區(qū)會產(chǎn)生內(nèi)部碎片舶赔，動態(tài)分區(qū)會產(chǎn)生外部碎片，這兩種技術(shù)對內(nèi)存的利用率都比較低谦秧。為盡量避免碎片的產(chǎn)生，引入了分頁的思想：把主存空間劃分為大小相等且固定的塊撵溃，塊相對較小疚鲤，作為主存的基本單位。每個進(jìn)程也以塊為單位進(jìn)行劃分缘挑，進(jìn)程在執(zhí)行時集歇，以塊為單位逐個申請主存中的塊空間。
分頁方法與固定分區(qū)技術(shù)不同點在于：塊的大小相對于分區(qū)小很多语淘，而且進(jìn)程也按照塊進(jìn)行劃分诲宇，進(jìn)程運行時际歼，按照塊申請主存可用空間并執(zhí)行。與分區(qū)留在較大的內(nèi)部碎片不同姑蓝，分頁方式只會在最后一個主存塊上留下頁內(nèi)碎片鹅心。
1 分頁存儲的幾個基本概念
1.1 頁面和頁面大小
進(jìn)程中的塊稱為頁(Page)，內(nèi)存中的塊稱為頁框或頁幀（Page Frame）纺荧。外存也以同樣的單位進(jìn)行劃分旭愧，直接稱為塊(Block)。進(jìn)程在執(zhí)行時需要申請主存空間宙暇，就是要為每個頁面分配主存中的可用頁框输枯，頁與頁框的一一對應(yīng)。
為方便地址轉(zhuǎn)換占贫，頁面大小應(yīng)是2的整數(shù)冪桃熄，通常是512B~8KB。同時頁面大小應(yīng)該適中型奥，需要進(jìn)行空間效率和時間效率的權(quán)衡瞳收。如果頁面太小，會使進(jìn)程的頁面數(shù)過多桩引，這樣頁表就過長缎讼，占用大量內(nèi)存，而且也會增加硬件地址轉(zhuǎn)換的開銷坑匠，降低頁面換入/換出的效率血崭；頁面過大又會使頁內(nèi)碎片增大，降低內(nèi)存的利用率厘灼。
1.2 地址結(jié)構(gòu)
分頁存儲管理的邏輯地址結(jié)構(gòu)如圖所示：
地址結(jié)構(gòu)包含兩部分：前一部分為頁號P夹纫，后一部分為頁內(nèi)偏移量W。地址長度為32 位设凹，其中0-11位為頁內(nèi)地址舰讹，即每頁大小為4KB；12-31位為頁號闪朱，地址空間最多允許有2^20(1M)頁月匣。
1.3 頁表
為了便于在內(nèi)存中找到進(jìn)程的每個頁面所對應(yīng)的物理塊，系統(tǒng)為每個進(jìn)程建立一張頁表奋姿，記錄頁面在內(nèi)存中對應(yīng)的物理塊號锄开，頁表一般存放在內(nèi)存中。
進(jìn)程通過查表得到每頁在內(nèi)存中的物理塊號称诗。由頁表實現(xiàn)了從頁號到物理塊號的地址映射萍悴。如下圖所示：
2 基本地址變換機構(gòu)
地址變換機構(gòu)的任務(wù)是將邏輯地址轉(zhuǎn)換為內(nèi)存中物理地址，地址變換是借助于頁表實現(xiàn)的。轉(zhuǎn)換過程中癣诱，業(yè)內(nèi)偏移是固定的计维，需要完成由頁號到塊號的變換。
在系統(tǒng)中通常設(shè)置一個頁表寄存器(PTR)撕予，存放頁表在內(nèi)存的始址F和頁表長度M鲫惶。進(jìn)程未執(zhí)行時，頁表的始址和長度存放在進(jìn)程控制塊中嗅蔬，當(dāng)進(jìn)程執(zhí)行時剑按，才將頁表始址和長度存入頁表寄存器。設(shè)頁面大小為L澜术，邏輯地址A到物理地址E的變換過程如下：
- 計算頁號P(P=A/L)和頁內(nèi)偏移量W (W=A%L)艺蝴。
- 比較頁號P和頁表長度M，若P >= M鸟废，則產(chǎn)生越界中斷猜敢，否則繼續(xù)執(zhí)行。
- 頁表中頁號P對應(yīng)的頁表項地址 = 頁表起始地址F + 頁號P * 頁表項長度盒延，取出該頁表項內(nèi)容b缩擂，即為物理塊號。
- 計算E=b*L+W添寺，用得到的物理地址E去訪問內(nèi)存胯盯。
以上整個地址變換過程均是由硬件自動完成的。
3 具備快表的地址變換機構(gòu)
若頁表全部放在內(nèi)存中计露，則存取一個數(shù)據(jù)或一條指令至少要訪問兩次內(nèi)存：一次是訪問頁表博脑，確定所存取的數(shù)據(jù)或指令的物理地址，第二次才根據(jù)該地址存取數(shù)據(jù)或指令票罐。這種方法比通常執(zhí)行指令的速度慢了一半叉趣。
為加速地址變換的過程，在地址變換機構(gòu)中增設(shè)了一個具有并行查找能力的高速緩沖存儲器——快表该押，又稱聯(lián)想寄存器(TLB)疗杉，用來存放當(dāng)前訪問的若干頁表項。與此對應(yīng)蚕礼，主存中的頁表也常稱為慢表烟具，配有快表的地址變換機構(gòu)如圖所示：
在具有快表的分頁機制中，地址的變換過程：
- CPU給出邏輯地址后奠蹬，由硬件進(jìn)行地址轉(zhuǎn)換并將頁號送入高速緩存寄存器朝聋，并將此頁號與快表中的所有頁號進(jìn)行比較。
- 如果在快表中找到匹配的頁號罩润，則直接從中取出該頁對應(yīng)的頁框號，與頁內(nèi)偏移量拼接形成物理地址翼馆。這樣割以，存取數(shù)據(jù)僅一次訪存便可實現(xiàn)金度。
- 如果沒有找到，則需要訪問主存中的頁表严沥，在讀出頁表項后猜极，應(yīng)同時將其存入快表，以便后面可能的再次訪問消玄。但若快表已滿跟伏，則必須按照一定的算法對舊的頁表項進(jìn)行替換。
有些處理機設(shè)計為快表和慢表同時查找翩瓜，如果在快表中查找成功則終止慢表的查找受扳。一般快表的命中率可以達(dá)到90%以上，這樣兔跌，分頁帶來的速度損失就降低到10%以下勘高。
4 兩級和多級頁表
現(xiàn)代大多數(shù)計算機系統(tǒng)都支持非常大的邏輯地址空間（232~264），在這樣的環(huán)境下坟桅，頁表就變得非常大华望，要占很大的內(nèi)存空間。32 位邏輯地址空間仅乓、頁面大小4KB赖舟、頁表項大小4B為例，若要實現(xiàn)進(jìn)程對全部邏輯地址空間的映射夸楣，則每個進(jìn)程需要2^20個頁表項宾抓。也就是說，每個進(jìn)程僅頁表這一項就需要4MB主存空間裕偿，這顯然是不切實際的洞慎。
此問題解決分兩方面：一方面，只將當(dāng)前需要的部分表項調(diào)入內(nèi)存嘿棘，其余的頁表仍然駐留在磁盤上劲腿，需要時再調(diào)入。另一方面鸟妙，需要對頁表映射的思想進(jìn)一步延伸焦人，就可以得到二級分頁。
二級頁表將頁表的10頁空間也進(jìn)行地址映射重父，建立上一級頁表花椭，用于存儲頁表的映射關(guān)系。上一級頁表只需要1頁就足夠（可以存儲2^10=1024個頁表項）房午。在進(jìn)程執(zhí)行時矿辽，只需要將這1頁的上一級頁表調(diào)入內(nèi)存即可，進(jìn)程的頁表和進(jìn)程本身的頁面，可以在后面的執(zhí)行中再調(diào)入內(nèi)存袋倔。
對二級頁表再進(jìn)行拓展雕蔽，得到多級頁表。64位計算機通常將可尋址存儲空間減少為45位長度宾娜，這樣可以使用三級頁表結(jié)構(gòu)來實現(xiàn)分頁存儲管理批狐。
基本分段存儲管理方式
分頁管理方式是從計算機的角度考慮設(shè)計的，以提高內(nèi)存的利用率前塔，提升計算機的性能, 且分頁通過硬件機制實現(xiàn)嚣艇，對用戶完全透明；而分段管理方式的提出則是考慮了用戶和程序員华弓，以滿足方便編程食零、信息保護(hù)和共享、動態(tài)增長及動態(tài)鏈接等多方面的需要该抒。
1 分段
段式管理方式按照用戶進(jìn)程中的自然段劃分邏輯空間慌洪。例如，用戶進(jìn)程由主程序凑保、兩個子程序冈爹、棧和一段數(shù)據(jù)組成，于是可以把這個用戶進(jìn)程劃分為5個段欧引，每段從0 開始編址频伤，并分配一段連續(xù)的地址空間（段內(nèi)要求連續(xù)，段間不要求連續(xù)芝此，因此整個作業(yè)的地址空間是二維的）憋肖。其邏輯地址由段號S與段內(nèi)偏移量W兩部分組成。
下圖中婚苹，段號是16位岸更，段內(nèi)偏移量是為16位，則一個作業(yè)最多可有216=65536個段膊升，最大段長為64KB怎炊。
在頁式系統(tǒng)中，邏輯地址的頁號和頁內(nèi)偏移量對用戶是透明的廓译，但在段式系統(tǒng)中评肆，段號和段內(nèi)偏移量必須由用戶顯示提供，在髙級程序設(shè)計語言中非区，這個工作由編譯程序完成瓜挽。
2 段表
每個進(jìn)程都有一張邏輯空間與內(nèi)存空間映射的段表，其中每一個段表項對應(yīng)進(jìn)程的一個段征绸，段表項記錄該段在內(nèi)存中的起始地址和段的長度久橙。段表的內(nèi)容如圖所示：
段表用于實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射俄占。在配置了段表后，執(zhí)行中的進(jìn)程可通過查找段表淆衷，找到每個段所對應(yīng)的內(nèi)存區(qū)颠放。
3 地址變換機構(gòu)
為了實現(xiàn)進(jìn)程從邏輯地址到物理地址的變換功能，在系統(tǒng)中設(shè)置了段表寄存器吭敢，用于存放段表始址F和段表長度M。其從邏輯地址A到物理地址E之間的地址變換過程如下：
- 從邏輯地址A中取出前幾位為段號S暮芭，后幾位為段內(nèi)偏移量W鹿驼。
- 比較段號S和段表長度M，若S多M辕宏，則產(chǎn)生越界中斷畜晰，否則繼續(xù)執(zhí)行。
- 段表中段號S對應(yīng)的段表項地址 = 段表起始地址F + 段號S * 段表項長度瑞筐，取出該段表項的前幾位得到段長C凄鼻。若段內(nèi)偏移量>=C，則產(chǎn)生越界中斷聚假，否則繼續(xù)執(zhí)行块蚌。
- 取出段表項中該段的起始地址b，計算 E = b + W膘格，用得到的物理地址E去訪問內(nèi)存峭范。
分段系統(tǒng)的地址變換過程如下圖所示：
4 段的共享與保護(hù)
在分段系統(tǒng)中，段的共享是通過兩個作業(yè)的段表中相應(yīng)表項指向被共享的段的同一個物理副本來實現(xiàn)的瘪贱。當(dāng)一個作業(yè)正從共享段中讀取數(shù)據(jù)時纱控，必須防止另一個作業(yè)修改此共享段中的數(shù)據(jù)。
不能修改的代碼稱為純代碼或可重入代碼（它不屬于臨界資源）菜秦。這樣的代碼和不能修改的數(shù)據(jù)是可以共享的甜害，而可修改的代碼和數(shù)據(jù)則不能共享。（需要修改數(shù)據(jù)時球昨，每個訪問進(jìn)程必須配置局部數(shù)據(jù)區(qū)尔店，并在執(zhí)行中可能改變的部分拷貝到該區(qū)域）
與分頁管理類似，分段管理的保護(hù)方法主要有兩種：一種是存取控制保護(hù)褪尝，另一種是地址越界保護(hù)闹获。地址越界保護(hù)是利用段表寄存器中的段表長度與邏輯地址中的段號比較，若段號大于段表長度則產(chǎn)生越界中斷河哑；再利用段表項中的段長和邏輯地址中的段內(nèi)位移進(jìn)行比較避诽，若段內(nèi)位移大于段長，也會產(chǎn)生越界中斷璃谨。
段頁式管理方式
頁式存儲管理能有效地提高內(nèi)存利用率沙庐，而分段存儲管理能反映程序的邏輯結(jié)構(gòu)并有利于段的共享鲤妥。如果將這兩種存儲管理方法結(jié)合起來，就形成了段頁式存儲管理方式拱雏。
在段頁式系統(tǒng)中棉安，作業(yè)的地址空間首先被分成若干個邏輯段，每段都有自己的段號铸抑，然后再將每一段分成若干個大小固定的頁贡耽。對內(nèi)存空間的管理仍然和分頁存儲管理一樣，將其分成若干個和頁面大小相同的存儲塊鹊汛，對內(nèi)存的分配以存儲塊為單位蒲赂，如圖所示：
在段頁式系統(tǒng)中，作業(yè)的邏輯地址分為三部分：段號刁憋、頁號和頁內(nèi)偏移量：
注意：在一個進(jìn)程中滥嘴，段表只有一個，而頁表可能有多個至耻。
在進(jìn)行地址變換時若皱，首先通過段表查到頁表起始地址，然后通過頁表找到頁幀號尘颓，最后形成物理地址走触。如圖所示，進(jìn)行一次訪問實際需要三次訪問主存疤苹，這里同樣可以使用快表以加快查找速度饺汹，其關(guān)鍵字由段號、頁號組成痰催，值是對應(yīng)的頁幀號和保護(hù)碼兜辞。
