連續(xù)分配方式：一個進程連續(xù)的裝進內(nèi)存一個大小合適的區(qū)。
????->“碎片”->“緊湊”->增大開銷
如果允許一個進程直接分散裝入多個不相鄰分區(qū)中享钞，則無需“緊湊”
產(chǎn)生存儲管理的離散分配方式揍诽。
3. 基本分頁存儲管理方式
本部分討論不具備對換功能的純分頁模式，作業(yè)運行需要全部裝入內(nèi)存栗竖。
比較連續(xù)分配方式
????作業(yè)邏輯地址空間有M大暑脆，就需要向內(nèi)存申請一個M大的連續(xù)區(qū)域。
????分頁的目的是更細粒度的處理空間狐肢，減少粗放管理的浪費或開銷問題添吗。
離散分配內(nèi)存：
????作業(yè)規(guī)定大小劃分成小份；內(nèi)存也按同樣大小劃分成小份
????作業(yè)的任一小份可分散放入內(nèi)存任意未使用的小份
分頁方式下份名，內(nèi)存的使用率高碟联，浪費少妓美。但不是絕對沒有碎片（進程的最后一頁不總是能占滿一個物理塊）
1）頁面的概念
內(nèi)存劃分成多個小單元，每個單元K大小鲤孵，稱（物理）塊壶栋。作業(yè)也按K單位大小劃分成片，稱為頁面普监。
????① 物理劃分塊的大小 = 邏輯劃分的頁的大小
????②頁面大小要適中贵试。太大，（最后一頁）內(nèi)碎片增大凯正，類似連續(xù)分配的問題毙玻。太小的話，頁面碎片總空間雖然小廊散，提高了利用率桑滩，但每個進程的頁面數(shù)量較多，頁表過長允睹，反而又增加了空間使用运准。
2）頁表的概念
????為了找到被離散分配到內(nèi)存中的作業(yè)，記錄每個作業(yè)各頁映射到哪個物理塊擂找，形成的頁面映射表戳吝，簡稱頁表。
????每個作業(yè)有自己的頁表
????頁表的作用：
????????頁號到物理塊號的地址映射
????要找到作業(yè)A
????????關鍵是找到頁表（PCB）
????????根據(jù)頁表找物理塊
3）地址的處理
連續(xù)方式下贯涎，每條指令用基地址+偏移量即可找到其物理存放的地址听哭。
分頁方式下詳細的地址處理會如何呢？
地址映射（地址計算）的過程塘雳？
????若要執(zhí)行某作業(yè)的一條指令陆盘，其相對地址是24B （設10B一頁，頁表如右表）败明，其物理地址到底是多少呢隘马？
????????分析其所在的頁和偏移得：2號頁（頁號從0開始） ，偏移4B處是該條指令
????????查頁表找頁面對應的塊（2號頁保存在6號物理塊）
????????找物理塊6妻顶，向下偏移4B酸员，找到要執(zhí)行的指令。取出執(zhí)行即可讳嘱。
????????計算上就是求商（頁號）及取余（偏移量）的過程
規(guī)律
????作業(yè)相對地址在分頁下不同位置的數(shù)有一定的意義結構：
????????頁號+頁內(nèi)地址（即頁內(nèi)偏移）
????關鍵的計算是：根據(jù)系統(tǒng)頁面大小找到不同意義二進制位的分界線幔嗦。
????從地址中分析出頁號后，地址映射只需要把頁號改為對應物理塊號，偏移不變，即可找到內(nèi)存中實際位置挽鞠。
注意：一作業(yè)所有指令在用戶地址空間是順序編址
上例若作業(yè)頁表如右表所示斯够，任意取一用戶程序指令，如第1011個指令索守，如何知道放在內(nèi)存的哪里瞳购？
????重要參數(shù)：系統(tǒng)頁面大小=8B
????????頁內(nèi)的所有指令編址用了3位
????????111增一后進位褪尝，下一條第9條指令已經(jīng)到了下一頁1000
????????1011中的1代表是1號頁因谎，而011代表是該頁中偏移3B后的第4條基括，
????根據(jù)頁表，1號頁存在7#物理塊上财岔。
????7#物理塊又在哪阱穗？
????????物理塊的編址也是8B大小決定的，地址結構類似
????????7#塊的第一條指令地址是111000使鹅。第7塊中向下偏移3就是要找的指令。其地址就是111011昌抠。
4）地址變換機構
????前面講解了地址變換的原理患朱，那么誰具體實現(xiàn)地址映射？——地址變換機構炊苫。
????圍繞頁表進行工作裁厅，那么頁表數(shù)據(jù)放在哪？
????????寄存器侨艾。一個進程有n個頁执虹，頁表就需要記錄n項數(shù)據(jù)，需要n個寄存器唠梨。不現(xiàn)實袋励。
????????內(nèi)存。只設置一個頁表寄存器PTR（page table register）記錄頁表在內(nèi)存中的首地址和頁表長度当叭，運行時快速定位頁表茬故。
地址變換過程
分頁系統(tǒng)中，進程創(chuàng)建蚁鳖，放入內(nèi)存磺芭，構建頁表，在PCB中記錄頁表存放在內(nèi)存的首地址及頁表長度醉箕。
????運行某進程A時钾腺，將A進程PCB中的頁表信息寫入PTR中；
????每執(zhí)行一條指令時讥裤，根據(jù)分頁計算原理放棒，得到指令頁號X和內(nèi)部偏移量Y；
????CPU高速訪問PTR找到頁表在哪里坞琴；
????查頁表數(shù)據(jù)哨查，得到X實際對應存放的物理塊，完成地址映射計算剧辐，最終在內(nèi)存找到該指令寒亥。
訪問內(nèi)存的有效時間
進程發(fā)出邏輯地址的訪問請求邮府，經(jīng)過地址變換，到內(nèi)存中找到對應的實際物理地址單元并取出數(shù)據(jù)溉奕，所需花費的總時間褂傀，稱為內(nèi)存的有效訪問時間EAT（effective access time）
設訪問一次內(nèi)存時間為t，則基本分頁機制下EAT=2t加勤，why仙辟？
????CPU操作一條指令需訪問內(nèi)存兩次：
????????訪問內(nèi)存中的頁表（以計算指令所在的實際物理地址）
????????訪問指令內(nèi)存地址
5）引入快表——針對訪問速度問題
問題：基本分頁機制下，一次指令需兩次內(nèi)存訪問鳄梅，處理機速度降低1/2叠国，分頁空間效率的提高以如此的速度為代價，得不償失戴尸。
改進：減少第1步訪問內(nèi)存的時間粟焊。增設一個具有“并行查詢”能力的高速緩沖寄存器，稱為“快表”孙蒙，也稱“聯(lián)想寄存器”（Associative memory）项棠，IBM系統(tǒng)稱為TLB（Translation Look aside Buffer）。
快表放什么挎峦？：
????正在執(zhí)行進程的頁表的數(shù)據(jù)項香追。
引入快表后的內(nèi)存訪問時間如何？
????快表的寄存器單元數(shù)量是有限的坦胶，不能裝下一個進程的所有頁表項透典。雖不能完全避免兩次訪問內(nèi)存，但如果命中率a高還是能大幅度提高速度顿苇。
????設一次查找訪問快表時間為t' 掷匠，則
? ????EAT= a*t' + (1-a)(t'+t)? ? +? ? t
? ? ???? = 2t +t' -t*a
6）兩級、多級頁表岖圈，反置頁表?——針對大頁表占用內(nèi)存問題
頁表大小的討論
????進程分頁離散存放讹语，但頁表的數(shù)據(jù)是連續(xù)在存放內(nèi)存的。而頁表可能很大：
????????現(xiàn)代操作系統(tǒng)支持非常大的邏輯地址空間的進程蜂科。如32位系統(tǒng)顽决，可編址的最大代碼數(shù)為232，若頁面大小為4KB（4*210）导匣，則支持的最大進程頁表項數(shù)可達碼232/212=220才菠，有1M個，每個頁表項占1B（字節(jié)）贡定，則頁表大小就有1MB赋访。
①兩級頁表
將頁表分頁，并離散地將頁表的各個頁面分別存放在不同的物理塊中
為離散分配的頁表再建立一張頁表，稱為“外層頁表”蚓耽，其每個表項記錄了頁表頁面所在的物理塊號渠牲。
32位邏輯地址空間，頁面大小為4KB(即12位)
一級頁表機構步悠，剩余20位是頁號签杈，可編出的220個頁（也即頁表長1M/或頁表項有1M個）；
兩級頁表：討論頁表的分頁
分頁原理類似：
將頁表也按4K大小分頁（212）
頁表被分頁后鼎兽，頁表的一個外頁4K答姥，外頁偏移量需10位，為什么谚咬？
課本將頁表每1024個頁表項就分一外頁鹦付，外頁內(nèi)的偏移需要10位≡褙裕可理解為每個頁表項占4B(塊號睁壁、權限等)，如此一外頁頁表信息才占滿一個4KB大小的物理塊
②多級頁表
64位操作系統(tǒng)下互捌，兩級仍然不足以解決頁表過大問題時，可按同樣道理繼續(xù)分頁下去形成多級頁表行剂。
③反置頁表
每個進程一張頁表
一張OS 反置頁表 + 每進程一張外部頁表
反置頁表（Inverted Page Tale）：站在物理塊的角度秕噪，記錄占用它的已調(diào)入內(nèi)存的進程標識和頁號。系統(tǒng)中只需一張該表即可厚宰。一個64MB內(nèi)存腌巾，若頁面大小4KB（64M/4K=2^16=16K個物理塊），反置頁表占用64KB（16K*4B）
進程外部頁表（External Page Table）：每個進程一張铲觉，記錄進程不在內(nèi)存中的那些頁面所在的外存物理位置澈蝙。
如何提高檢索反置頁表速度：內(nèi)存容量大時，反置頁表的頁表項還是會很大撵幽，利用進程標識符和頁號去檢索一張大的線性表很費時灯荧，可利用hash算法提高檢索速度。
4.基本分段存儲管理方式
從提高內(nèi)存利用率角度盐杂；
????固定分區(qū)->動態(tài)分區(qū)->分頁
從滿足并方便用戶（程序員）和使用上的要求角度：
????分段存儲管理：作業(yè)分成若干段逗载，各段可離散放入內(nèi)存，段內(nèi)仍連續(xù)存放链烈。
????????方便編程：如匯編中通過段：偏移確定數(shù)據(jù)位置
????????信息共享：同地位的數(shù)據(jù)放在一塊方便進行共享設置
????????信息保護
????????動態(tài)增長：動態(tài)增長的數(shù)據(jù)段事先固定內(nèi)存不方便
????????動態(tài)鏈接：往往也是以邏輯的段為單位更方便
1）分段系統(tǒng)的基本原理
????程序通過分段(segmentation)劃分為多個模塊厉斟，每個段定義一組邏輯信息。如代碼段（主程序段main强衡，子程序段X）擦秽、數(shù)據(jù)段D、棧段S等。
????誰決定一個程序分幾段感挥，每段多大缩搅？
????????編譯程序（基于源代碼）
????段的特點
????????每段有自己的名字（一般用段號做名），都從0編址链快，可分別編寫和編譯誉己。裝入內(nèi)存時，每段賦予各段一個段號域蜗。
????????每段占據(jù)一塊連續(xù)的內(nèi)存巨双。（即有離散的分段，又有連續(xù)的內(nèi)存使用）
????????各段大小不等霉祸。
分段下的相對地址：
地址結構：段號 + 段內(nèi)地址
段表：記錄每段實際存放的物理地址
2）段表與地址變換機構
段是連續(xù)存放在內(nèi)存中筑累。段表中針對每個“段編號”記錄：“內(nèi)存首地址”和“段長”
同樣有兩次內(nèi)存訪問問題
解決方法：設置聯(lián)想寄存器，用于保存最近常用的段表項丝蹭。
3）分頁和分段的主要區(qū)別
? ? ①需求：分頁是出于系統(tǒng)管理的需要慢宗，是一種信息的物理劃分單位，分段是出于用戶應用的需要奔穿，是一種邏輯單位镜沽，通常包含一組意義相對完整的信息。
????????一條指令或一個操作數(shù)可能會跨越兩個頁的分界處贱田，而不會跨越兩個段的分界處缅茉。
? ? ②大小：頁大小是系統(tǒng)固定的男摧，而段大小則通常不固定蔬墩。分段沒有內(nèi)碎片，但連續(xù)存放段產(chǎn)生外碎片耗拓，可以通過內(nèi)存緊縮來消除拇颅。相對而言分頁空間利用率高。
? ? ③邏輯地址：
????????分頁是一維的乔询，各個模塊在鏈接時必須組織成同一個地址空間樟插；
????????分段是二維的，各個模塊在鏈接時可以每個段組織成一個地址空間竿刁。
? ? ④其他：通常段比頁大岸夯，因而段表比頁表短，可以縮短查找時間们妥，提高訪問速度猜扮。分段模式下，還可針對不同類型采取不同的保護监婶；按段為單位來進行共享
4）信息共享
分段系統(tǒng)的突出優(yōu)點：
????易于實現(xiàn)共享
????????在分段系統(tǒng)中旅赢，實現(xiàn)共享十分容易齿桃，只需在每個進程的段表中為共享程序設置一個段表項。
????????比較課本圖煮盼。對同樣的共享內(nèi)容的管理上短纵，很明顯分段的空間管理更簡單。分頁的圖涉及太多的頁面劃分和地址記錄的管理僵控。
????易于實現(xiàn)保護：
????????代碼的保護和其邏輯意義有關香到，分頁的機械式劃分不容易實現(xiàn)。
分頁容易造成共享和非共享數(shù)據(jù)共處一頁报破，不方便設置權限悠就。
????可重入代碼：
????????又稱為純代碼，允許多個進程同時訪問的代碼
????????不允許任何進程對它進行修改充易。
????????可共享的代碼必須是可重入的梗脾；
5）段頁式存儲管理方式
① 基本原理
將用戶程序分成若干段，并為每個段賦予一個段名盹靴。
把每個段分成若干頁
地址結構包括段號炸茧、段內(nèi)頁號和頁內(nèi)地址三部分
②地址變換過程
進程的虛存空間是映射的基礎
Linux僅把運行進程當前使用的少量頁面裝入內(nèi)存（內(nèi)存分配）
地址映射。若訪問的虛頁不在內(nèi)存稿静，產(chǎn)生一個頁故障并報告故障原因梭冠，再通過請頁機制將其調(diào)入內(nèi)存。（請頁改备、交換）
linux下虛擬空間的管理
malloc分配的是虛存區(qū)控漠，只有內(nèi)核管理為進程創(chuàng)建空間，由內(nèi)核代碼實際執(zhí)行alloc_pages()等內(nèi)核函數(shù)時才真正分配內(nèi)存
現(xiàn)階段分配方式的不足：
基本分頁/分段方式都是進程全部裝入內(nèi)存的方式绍妨。內(nèi)存空間使用上仍有局限。
虛擬存儲管理：請求式分頁/分段
