非連續(xù)分配允許一個(gè)程序分散地裝入到不相鄰的內(nèi)存分區(qū)中，根據(jù)分區(qū)的大小是否固定分為分頁(yè)存儲(chǔ)管理方式和分段存儲(chǔ)管理方式。在分頁(yè)存儲(chǔ)管理方式中，如果不具備頁(yè)面對(duì)換功能，則稱(chēng)為基本分頁(yè)存儲(chǔ)管理方式，或純分頁(yè)管理方式。
基本分頁(yè)存儲(chǔ)管理方式
固定分區(qū)會(huì)產(chǎn)生內(nèi)部碎片，動(dòng)態(tài)分區(qū)會(huì)產(chǎn)生外部碎片，這兩種技術(shù)對(duì)內(nèi)存的利用率都比較低。為盡量避免碎片的產(chǎn)生，引入了分頁(yè)的思想：把主存空間劃分為大小相等且固定的塊，塊相對(duì)較小，作為主存的基本單位。每個(gè)進(jìn)程也以塊為單位進(jìn)行劃分，進(jìn)程在執(zhí)行時(shí)，以塊為單位逐個(gè)申請(qǐng)主存中的塊空間。
分頁(yè)方法與固定分區(qū)技術(shù)不同點(diǎn)在于：塊的大小相對(duì)于分區(qū)小很多，而且進(jìn)程也按照塊進(jìn)行劃分，進(jìn)程運(yùn)行時(shí)，按照塊申請(qǐng)主存可用空間并執(zhí)行。與分區(qū)留在較大的內(nèi)部碎片不同，分頁(yè)方式只會(huì)在最后一個(gè)主存塊上留下頁(yè)內(nèi)碎片。
1 分頁(yè)存儲(chǔ)的幾個(gè)基本概念
1.1 頁(yè)面和頁(yè)面大小
進(jìn)程中的塊稱(chēng)為頁(yè)(Page)，內(nèi)存中的塊稱(chēng)為頁(yè)框或頁(yè)幀（Page Frame）。外存也以同樣的單位進(jìn)行劃分，直接稱(chēng)為塊(Block)。進(jìn)程在執(zhí)行時(shí)需要申請(qǐng)主存空間，就是要為每個(gè)頁(yè)面分配主存中的可用頁(yè)框，頁(yè)與頁(yè)框的一一對(duì)應(yīng)。
為方便地址轉(zhuǎn)換，頁(yè)面大小應(yīng)是2的整數(shù)冪，通常是512B~8KB。同時(shí)頁(yè)面大小應(yīng)該適中，需要進(jìn)行空間效率和時(shí)間效率的權(quán)衡。如果頁(yè)面太小，會(huì)使進(jìn)程的頁(yè)面數(shù)過(guò)多，這樣頁(yè)表就過(guò)長(zhǎng)，占用大量?jī)?nèi)存，而且也會(huì)增加硬件地址轉(zhuǎn)換的開(kāi)銷(xiāo)，降低頁(yè)面換入/換出的效率；頁(yè)面過(guò)大又會(huì)使頁(yè)內(nèi)碎片增大，降低內(nèi)存的利用率。
1.2 地址結(jié)構(gòu)
分頁(yè)存儲(chǔ)管理的邏輯地址結(jié)構(gòu)如圖所示：
地址結(jié)構(gòu)包含兩部分：前一部分為頁(yè)號(hào)P，后一部分為頁(yè)內(nèi)偏移量W。地址長(zhǎng)度為32 位，其中0-11位為頁(yè)內(nèi)地址，即每頁(yè)大小為4KB；12-31位為頁(yè)號(hào)，地址空間最多允許有2^20(1M)頁(yè)。
1.3 頁(yè)表
為了便于在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)表，記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)，頁(yè)表一般存放在內(nèi)存中。
進(jìn)程通過(guò)查表得到每頁(yè)在內(nèi)存中的物理塊號(hào)。由頁(yè)表實(shí)現(xiàn)了從頁(yè)號(hào)到物理塊號(hào)的地址映射。如下圖所示：
2 基本地址變換機(jī)構(gòu)
地址變換機(jī)構(gòu)的任務(wù)是將邏輯地址轉(zhuǎn)換為內(nèi)存中物理地址，地址變換是借助于頁(yè)表實(shí)現(xiàn)的。轉(zhuǎn)換過(guò)程中，業(yè)內(nèi)偏移是固定的，需要完成由頁(yè)號(hào)到塊號(hào)的變換。
在系統(tǒng)中通常設(shè)置一個(gè)頁(yè)表寄存器(PTR)，存放頁(yè)表在內(nèi)存的始址F和頁(yè)表長(zhǎng)度M。進(jìn)程未執(zhí)行時(shí)，頁(yè)表的始址和長(zhǎng)度存放在進(jìn)程控制塊中，當(dāng)進(jìn)程執(zhí)行時(shí)，才將頁(yè)表始址和長(zhǎng)度存入頁(yè)表寄存器。設(shè)頁(yè)面大小為L(zhǎng)，邏輯地址A到物理地址E的變換過(guò)程如下：
- 計(jì)算頁(yè)號(hào)P(P=A/L)和頁(yè)內(nèi)偏移量W (W=A%L)。
- 比較頁(yè)號(hào)P和頁(yè)表長(zhǎng)度M，若P >= M，則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。
- 頁(yè)表中頁(yè)號(hào)P對(duì)應(yīng)的頁(yè)表項(xiàng)地址 = 頁(yè)表起始地址F + 頁(yè)號(hào)P * 頁(yè)表項(xiàng)長(zhǎng)度，取出該頁(yè)表項(xiàng)內(nèi)容b，即為物理塊號(hào)。
- 計(jì)算E=b*L+W，用得到的物理地址E去訪(fǎng)問(wèn)內(nèi)存。
以上整個(gè)地址變換過(guò)程均是由硬件自動(dòng)完成的。
3 具備快表的地址變換機(jī)構(gòu)
若頁(yè)表全部放在內(nèi)存中，則存取一個(gè)數(shù)據(jù)或一條指令至少要訪(fǎng)問(wèn)兩次內(nèi)存：一次是訪(fǎng)問(wèn)頁(yè)表，確定所存取的數(shù)據(jù)或指令的物理地址，第二次才根據(jù)該地址存取數(shù)據(jù)或指令。這種方法比通常執(zhí)行指令的速度慢了一半。
為加速地址變換的過(guò)程，在地址變換機(jī)構(gòu)中增設(shè)了一個(gè)具有并行查找能力的高速緩沖存儲(chǔ)器——快表，又稱(chēng)聯(lián)想寄存器(TLB)，用來(lái)存放當(dāng)前訪(fǎng)問(wèn)的若干頁(yè)表項(xiàng)。與此對(duì)應(yīng)，主存中的頁(yè)表也常稱(chēng)為慢表，配有快表的地址變換機(jī)構(gòu)如圖所示：
在具有快表的分頁(yè)機(jī)制中，地址的變換過(guò)程：
- CPU給出邏輯地址后，由硬件進(jìn)行地址轉(zhuǎn)換并將頁(yè)號(hào)送入高速緩存寄存器，并將此頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較。
- 如果在快表中找到匹配的頁(yè)號(hào)，則直接從中取出該頁(yè)對(duì)應(yīng)的頁(yè)框號(hào)，與頁(yè)內(nèi)偏移量拼接形成物理地址。這樣，存取數(shù)據(jù)僅一次訪(fǎng)存便可實(shí)現(xiàn)。
- 如果沒(méi)有找到，則需要訪(fǎng)問(wèn)主存中的頁(yè)表，在讀出頁(yè)表項(xiàng)后，應(yīng)同時(shí)將其存入快表，以便后面可能的再次訪(fǎng)問(wèn)。但若快表已滿(mǎn)，則必須按照一定的算法對(duì)舊的頁(yè)表項(xiàng)進(jìn)行替換。
有些處理機(jī)設(shè)計(jì)為快表和慢表同時(shí)查找，如果在快表中查找成功則終止慢表的查找。一般快表的命中率可以達(dá)到90%以上，這樣，分頁(yè)帶來(lái)的速度損失就降低到10%以下。
4 兩級(jí)和多級(jí)頁(yè)表
現(xiàn)代大多數(shù)計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間（232~264），在這樣的環(huán)境下，頁(yè)表就變得非常大，要占很大的內(nèi)存空間。32 位邏輯地址空間、頁(yè)面大小4KB、頁(yè)表項(xiàng)大小4B為例，若要實(shí)現(xiàn)進(jìn)程對(duì)全部邏輯地址空間的映射，則每個(gè)進(jìn)程需要2^20個(gè)頁(yè)表項(xiàng)。也就是說(shuō)，每個(gè)進(jìn)程僅頁(yè)表這一項(xiàng)就需要4MB主存空間，這顯然是不切實(shí)際的。
此問(wèn)題解決分兩方面：一方面，只將當(dāng)前需要的部分表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表仍然駐留在磁盤(pán)上，需要時(shí)再調(diào)入。另一方面，需要對(duì)頁(yè)表映射的思想進(jìn)一步延伸，就可以得到二級(jí)分頁(yè)。
二級(jí)頁(yè)表將頁(yè)表的10頁(yè)空間也進(jìn)行地址映射，建立上一級(jí)頁(yè)表，用于存儲(chǔ)頁(yè)表的映射關(guān)系。上一級(jí)頁(yè)表只需要1頁(yè)就足夠（可以存儲(chǔ)2^10=1024個(gè)頁(yè)表項(xiàng)）。在進(jìn)程執(zhí)行時(shí)，只需要將這1頁(yè)的上一級(jí)頁(yè)表調(diào)入內(nèi)存即可，進(jìn)程的頁(yè)表和進(jìn)程本身的頁(yè)面，可以在后面的執(zhí)行中再調(diào)入內(nèi)存。
對(duì)二級(jí)頁(yè)表再進(jìn)行拓展，得到多級(jí)頁(yè)表。64位計(jì)算機(jī)通常將可尋址存儲(chǔ)空間減少為45位長(zhǎng)度，這樣可以使用三級(jí)頁(yè)表結(jié)構(gòu)來(lái)實(shí)現(xiàn)分頁(yè)存儲(chǔ)管理。
基本分段存儲(chǔ)管理方式
分頁(yè)管理方式是從計(jì)算機(jī)的角度考慮設(shè)計(jì)的，以提高內(nèi)存的利用率，提升計(jì)算機(jī)的性能, 且分頁(yè)通過(guò)硬件機(jī)制實(shí)現(xiàn)，對(duì)用戶(hù)完全透明；而分段管理方式的提出則是考慮了用戶(hù)和程序員，以滿(mǎn)足方便編程、信息保護(hù)和共享、動(dòng)態(tài)增長(zhǎng)及動(dòng)態(tài)鏈接等多方面的需要。
1 分段
段式管理方式按照用戶(hù)進(jìn)程中的自然段劃分邏輯空間。例如，用戶(hù)進(jìn)程由主程序、兩個(gè)子程序、棧和一段數(shù)據(jù)組成，于是可以把這個(gè)用戶(hù)進(jìn)程劃分為5個(gè)段，每段從0 開(kāi)始編址，并分配一段連續(xù)的地址空間（段內(nèi)要求連續(xù)，段間不要求連續(xù)，因此整個(gè)作業(yè)的地址空間是二維的）。其邏輯地址由段號(hào)S與段內(nèi)偏移量W兩部分組成。
下圖中，段號(hào)是16位，段內(nèi)偏移量是為16位，則一個(gè)作業(yè)最多可有216=65536個(gè)段，最大段長(zhǎng)為64KB。
在頁(yè)式系統(tǒng)中，邏輯地址的頁(yè)號(hào)和頁(yè)內(nèi)偏移量對(duì)用戶(hù)是透明的，但在段式系統(tǒng)中，段號(hào)和段內(nèi)偏移量必須由用戶(hù)顯示提供，在髙級(jí)程序設(shè)計(jì)語(yǔ)言中，這個(gè)工作由編譯程序完成。
2 段表
每個(gè)進(jìn)程都有一張邏輯空間與內(nèi)存空間映射的段表，其中每一個(gè)段表項(xiàng)對(duì)應(yīng)進(jìn)程的一個(gè)段，段表項(xiàng)記錄該段在內(nèi)存中的起始地址和段的長(zhǎng)度。段表的內(nèi)容如圖所示：
段表用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。在配置了段表后，執(zhí)行中的進(jìn)程可通過(guò)查找段表，找到每個(gè)段所對(duì)應(yīng)的內(nèi)存區(qū)。
3 地址變換機(jī)構(gòu)
為了實(shí)現(xiàn)進(jìn)程從邏輯地址到物理地址的變換功能，在系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址F和段表長(zhǎng)度M。其從邏輯地址A到物理地址E之間的地址變換過(guò)程如下：
- 從邏輯地址A中取出前幾位為段號(hào)S，后幾位為段內(nèi)偏移量W。
- 比較段號(hào)S和段表長(zhǎng)度M，若S多M，則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。
- 段表中段號(hào)S對(duì)應(yīng)的段表項(xiàng)地址 = 段表起始地址F + 段號(hào)S * 段表項(xiàng)長(zhǎng)度，取出該段表項(xiàng)的前幾位得到段長(zhǎng)C。若段內(nèi)偏移量>=C，則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。
- 取出段表項(xiàng)中該段的起始地址b，計(jì)算 E = b + W，用得到的物理地址E去訪(fǎng)問(wèn)內(nèi)存。
分段系統(tǒng)的地址變換過(guò)程如下圖所示：
4 段的共享與保護(hù)
在分段系統(tǒng)中，段的共享是通過(guò)兩個(gè)作業(yè)的段表中相應(yīng)表項(xiàng)指向被共享的段的同一個(gè)物理副本來(lái)實(shí)現(xiàn)的。當(dāng)一個(gè)作業(yè)正從共享段中讀取數(shù)據(jù)時(shí)，必須防止另一個(gè)作業(yè)修改此共享段中的數(shù)據(jù)。
不能修改的代碼稱(chēng)為純代碼或可重入代碼（它不屬于臨界資源）。這樣的代碼和不能修改的數(shù)據(jù)是可以共享的，而可修改的代碼和數(shù)據(jù)則不能共享。（需要修改數(shù)據(jù)時(shí)，每個(gè)訪(fǎng)問(wèn)進(jìn)程必須配置局部數(shù)據(jù)區(qū)，并在執(zhí)行中可能改變的部分拷貝到該區(qū)域）
與分頁(yè)管理類(lèi)似，分段管理的保護(hù)方法主要有兩種：一種是存取控制保護(hù)，另一種是地址越界保護(hù)。地址越界保護(hù)是利用段表寄存器中的段表長(zhǎng)度與邏輯地址中的段號(hào)比較，若段號(hào)大于段表長(zhǎng)度則產(chǎn)生越界中斷；再利用段表項(xiàng)中的段長(zhǎng)和邏輯地址中的段內(nèi)位移進(jìn)行比較，若段內(nèi)位移大于段長(zhǎng)，也會(huì)產(chǎn)生越界中斷。
段頁(yè)式管理方式
頁(yè)式存儲(chǔ)管理能有效地提高內(nèi)存利用率，而分段存儲(chǔ)管理能反映程序的邏輯結(jié)構(gòu)并有利于段的共享。如果將這兩種存儲(chǔ)管理方法結(jié)合起來(lái)，就形成了段頁(yè)式存儲(chǔ)管理方式。
在段頁(yè)式系統(tǒng)中，作業(yè)的地址空間首先被分成若干個(gè)邏輯段，每段都有自己的段號(hào)，然后再將每一段分成若干個(gè)大小固定的頁(yè)。對(duì)內(nèi)存空間的管理仍然和分頁(yè)存儲(chǔ)管理一樣，將其分成若干個(gè)和頁(yè)面大小相同的存儲(chǔ)塊，對(duì)內(nèi)存的分配以存儲(chǔ)塊為單位，如圖所示：
在段頁(yè)式系統(tǒng)中，作業(yè)的邏輯地址分為三部分：段號(hào)、頁(yè)號(hào)和頁(yè)內(nèi)偏移量：
注意：在一個(gè)進(jìn)程中，段表只有一個(gè)，而頁(yè)表可能有多個(gè)。
在進(jìn)行地址變換時(shí)，首先通過(guò)段表查到頁(yè)表起始地址，然后通過(guò)頁(yè)表找到頁(yè)幀號(hào)，最后形成物理地址。如圖所示，進(jìn)行一次訪(fǎng)問(wèn)實(shí)際需要三次訪(fǎng)問(wèn)主存，這里同樣可以使用快表以加快查找速度，其關(guān)鍵字由段號(hào)、頁(yè)號(hào)組成，值是對(duì)應(yīng)的頁(yè)幀號(hào)和保護(hù)碼。
