1. 基本分頁存儲管理方式的頁面與頁表
1) 頁面和物理塊
分頁存儲管理是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，並為各頁加以編號，從0開始，如第0頁、第1頁等。相應地，也把內存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號，如0#塊、1#塊等等。在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由於進程的最後一頁經常裝不滿一塊而形成了不可利用的碎片，稱之為「頁內碎片」。
2) 頁面大小
在分頁系統中的頁面其大小應適中。頁面若太小，一方面雖然可使內存碎片減小，從而減少了內存碎片的總空間，有利於提高內存利用率，但另一方面也會使每個進程佔用較多的頁面，從而導致進程的頁表過長，佔用大量內存；此外，還會降低頁面換進換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進換出的速度，但卻又會使頁內碎片增大。因此，頁面的大小應選擇適中，且頁面大小應是2的冪，通常為512 B～8 KB。 分頁地址中的地址結構如下：
對於某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內地址d可按右圖所示公式求得：
其中，INT是整除函數，MOD是取余函數。例如，其系統的頁面大小為1 KB，設A = 2170 B，則由上式可以求得P = 2，d = 122。 頁表的功能可以由一組專門的寄存器來實現。一個頁表項用一個寄存器。由於寄存器具有較高的訪問速度，因而有利於提高地址變換的速度；但由於寄存器成本較高，且大多數現代計算機的頁表又可能很大，使頁表項的總數可達幾千甚至幾十萬個，顯然這些頁表項不可能都用寄存器來實現，因此，頁表大多駐留在內存中。在系統中只設置一個頁表寄存器PTR(Page-Table Register)，在其中存放頁表在內存的始址和頁表的長度。平時，進程未執行時，頁表的始址和頁表長度存放在本進程的PCB中。當調度程序調度到某進程時，才將這兩個數據裝入頁表寄存器中。因此，在單處理機環境下，雖然系統中可以運行多個進程，但只需一個頁表寄存器。
當進程要訪問某個邏輯地址中的數據時，分頁地址變換機構會自動地將有效地址(相對地址)分為頁號頁內地址兩部分，再以頁號為索引去檢索頁表。查找操作由硬體執行。在執行檢索之前，先將頁號與頁表長度進行比較，如果頁號大於或等於頁表長度，則表示本次所訪問的地址已超越進程的地址空間。於是，這一錯誤將被系統發現並產生一地址越界中斷。若未出現越界錯誤，則將頁表始址與頁號和頁表項長度的乘積相加，便得到該表項在頁表中的位置，於是可從中得到該頁的物理塊號，將之裝入物理地址寄存器中。與此同時，再將有效地址寄存器中的頁內地址送入物理地址寄存器的塊內地址欄位中。這樣便完成了從邏輯地址到物理地址的變換。右圖示出了分頁系統的地址變換機構。 由於頁表是存放在內存中的，這使CPU在每存取一個數據時，都要兩次訪問內存。第一次是訪問內存中的頁表，從中找到指定頁的物理塊號，再將塊號與頁內偏移量W拼接，以形成物理地址。第二次訪問內存時，才是從第一次所得地址中獲得所需數據(或向此地址中寫入數據)。因此，採用這種方式將使計算機的處理速度降低近1/2。可見，以此高昂代價來換取存儲器空間利用率的提高，是得不償失的。
為了提高地址變換速度，可在地址變換機構中增設一個具有並行查尋能力的特殊高速緩沖寄存器，又稱為「聯想寄存器」(Associative Memory)，或稱為「快表」，在IBM系統中又取名為TLB(Translation Lookaside Buffer)，用以存放當前訪問的那些頁表項。此時的地址變換過程是：在CPU給出有效地址後，由地址變換機構自動地將頁號P送入高速緩沖寄存器，並將此頁號與高速緩存中的所有頁號進行比較，若其中有與此相匹配的頁號，便表示所要訪問的頁表項在快表中。於是，可直接從快表中讀出該頁所對應的物理塊號，並送到物理地址寄存器中。如在塊表中未找到對應的頁表項，則還須再訪問內存中的頁表，找到後，把從頁表項中讀出的物理塊號送地址寄存器；同時，再將此頁表項存入快表的一個寄存器單元中，亦即，重新修改快表。但如果聯想寄存器已滿，則OS必須找到一個老的且已被認為不再需要的頁表項，將它換出。右圖示出了具有快表的地址變換機構。
2. 一個具有快表的分頁存儲系統。訪問一次內存需要100納秒,訪問一次快表需要20納
設命中率為x
則120=100x+（100+180*2）(1-x)
x=94.4%
應該對哈~~
3. 求一道操作系統查表時間題目求解
作業名 到達段仔時間 估計斗鄭運行時間（分鍾） 優先數 完成時間 執行順序
A 10：00 50 5 10:50 1
B 10：20 60 7 11:50 2
C 10：50 40 3 15:30 6
D 11：20 80 8 13:10 3
E 11：40 30 6 14:50 5
F 12：00 70 9 14:20 4
作業調度是將作業後備隊列中的一批作業調入內存，現在作業已經在內存，所以作業調度已經執空燃頌行完畢。計算作業完成時間看進程的調度演算法--優先數（優先數大者優先）調度演算法.
10:00時只有A到達，所以先執行A；A完成時10:50時B、C到達，B優先數高，所以再執行B；
11:50D、E又到達，執行D，D完成時F也到達了，此時執行F，之後以次執行E、C。
4. （存儲管理）01.分頁式存儲管理
將內存劃分為若干個大小相等的分區，叫做塊；將邏輯空間劃分出與塊大小一致的分區，叫做頁。作業運行時，通過地址重定位技術，實現頁與塊的對應。這樣就以頁的方式來管理存儲塊，就叫分頁式存儲管理。
在分配存儲塊時，會根據作業的邏輯地址的大小計算所需要多少個存儲塊，然後查找空閑塊並更新空閑塊的狀態為佔用；回收存儲塊時，會將作業關聯的所有空閑塊的狀態設置為空閑。記錄空閑塊狀態的方法有兩種：點陣圖法和鏈表法。
在分配存儲塊之後，就在頁表中，增加頁和塊對應關系的記錄；同理，回收存儲塊時，就會刪除對應記錄。
訪問存儲塊時，就會根據邏輯地址的頁號，在頁表找到對應的塊號，然後再通過塊號計算出物理地址，找到對應的存儲塊。如下圖：
補充
頁表：記錄頁號與塊號對應關系的表，包含頁號和塊號兩個欄位。
邏輯地址：由 「頁號」 和 「頁內地址」 組成。其中頁內地址是通過頁大小來決定。
例如：邏輯地址長度為 16 位，頁大小是 1kb （二的十次冪），那麼頁內地址占低十位，高六位是頁號。如下：
在重定位存儲塊時，需要訪問頁表。為了加快重定位，就會通過快表（聯想存儲器，記錄常用的頁號和塊號的對應關系）來快速通過頁號找到對應的塊號。但是如果不能通過快表找到對應的塊號，那麼就會按照查找頁表的方式來完成重定位。
5. 採用快表進行分頁存儲管理，最壞情況下要幾次訪問內存
最壞情況3次，最好情況2次。
最壞情況是：現在快表中查詢頁號，但是沒有查到系統給出的頁號（這是第一次訪問內存），所以只能再去頁表中查詢相應的頁號，進而得到物理塊號（這是第二次訪問內存），最後一次是得到了物理地址後訪問真的系統所需數據，這是第三次。
最好的情況的話就是第一步在快表中查詢到了相應的頁號，從而就沒有第二部了，直接到了第三部，這種情況下，需要訪問2次內存
6. 基本分頁存儲管理
閱讀前請先閱讀 內存管理基礎 。從本文開始就介紹不連續分配的幾種方式，本文主要介紹基本分頁存儲管理。
假設進程A的大小為23MB，但是每個分區的大小隻有10MB，如果進程只能佔用一個分區，顯然是放不下的。
解決思路：如果允許進程佔用多個分區，那麼可以把進程拆分成 10MB + 10MB + 3MB三個部分 ，再把這三個部分別放在三個分區中（這些分區不要求連續）.....
將內存空間分為一個個大小相等的分區（如每個分區4KB，每個分區就是一個 「頁框」 ，或稱 「內存塊」 、 「物理塊」 。每個頁框有一個編號，即 「頁框號」 ，或 「內存塊號」 、 「物理塊號」 ，頁框號 從0開始 ）。將用戶進程的地址空間也分為與頁框大小相等的一個個區域，稱為 頁面 或 頁 。頁框的大小不能太大，否則可能會產生過大的內存碎片。
操作系統 以頁框為單位為各個進程分配內存空間。 進程的每個頁面分別放入一個頁框中，即進程的 頁面和內存的頁框 有 一一對應 的關系。
進程分頁後，進程的各個頁面可以放在不連續的頁框中，所以如何實現邏輯地址到物理的地址的轉換？
如下圖，將下面的進程分頁，假設每頁大小為50B，那麼就分為4個頁面。
手動計算方法：
頁號 = 邏輯地址 / 頁面長度（取整數部分）。
頁內偏移量 = 邏輯地址 % 頁面長度
頁面在內存中的起始位置 ：操作系統需要用某種數據結構記錄進程各個頁面的起始位置。
對於計算機，通常將 頁面的大小劃分為2的整數次冪 。假設用32個二進制位表示邏輯地址，頁面大小為取2 12 B = 4096B = 4KB。
如邏輯地址2，用二進製表示00000000 00000000 0000 0000 00000010 ，前24位二進制對應的十進制值就是邏輯地址2對應的頁號，即0號頁，而後12二進制位對應的十進制值就是偏移量。如果0號頁在內存中的起始地址為X，那麼邏輯地址2對應的物理地址就是 X + 2.
同理，邏輯地址4097，用二進製表示00000000 00000000 0001 0000 00000001 ，前24位二進制對應的十進制值就是邏輯地址4097對應的頁號，即1號頁，而後12二進制位對應的十進制值就是偏移量。如果0號頁在內存中的起始地址為Y，那麼邏輯地址4097對應的物理地址就是 Y + 1.
結論： 如果每個頁面的大小為2 k B，用二進製表示邏輯地址，則末尾的K位表示頁內偏移量，其餘部分就是頁號。
因此，如果讓 每個頁面的大小為2的整數次冪， 計算機就可以很方便的得出一個邏輯地址對應的頁號和頁內偏移量。
如果一個頁面的大小為2KB，那分頁存儲管理的邏輯地址結構為：
地址結構包括兩個部分：前一個部分表示頁號，後一個部分表示頁內偏移量W。
在知道如何計算頁號和偏移量後，要計算實際的物理地址，還需要知道頁號在內存中的起始地址，如何知道每個頁面在內存中存放的位置——操作系統要為 每個進程建立一張頁表。
按照之前的方法計算出邏輯地址所對應的頁號N，然後根據頁表區查詢實際的內存塊號M，由於每個內存塊號的大小都是相等的，所以實際地址 = M * 內存塊大小 + 偏移量。
在實際上，頁表中是沒有頁號的，那怎麼找到實際對應的內存塊號呢？
假設某系統物理內存大小為4GB，頁面大小為4KB，則每個頁表項至少應該佔用多少位元組？
各頁表項會 按順序連續地 存放在內存中，如果該頁表在內存中存放的地址為X，則M號頁對應的頁表項存放的地址為：X + M * 3B
因此，頁表的頁號可以是隱含的。只需要知道 頁表存放的起始地址 和 頁表項長度 ，即可找到各個頁號對應的頁表項存放的位置，找到位置後就可以讀取該位置的值，即實際內存塊號。
舉個例子，如果按照邏輯地址計算出了偏移量為20，頁號為1，頁表中的頁號是隱藏的，那麼根據頁表在內存中的起始地址20（假設的值），以及頁表項長度3B，那麼頁號為1所對應的實際內存塊號的值所在的地址就是：20 + 3 * 1 = 23的位置，然後在該位置的值，該值就是實際內存塊號，如果是4的話，那麼實際地址就是： 4 * 頁面大小（4096B） + 20 = 16404。
基本地址變換結構可以藉助進程的頁表將邏輯地址轉換為物理地址。
通常在系統中設置一個 頁表寄存器（PTR Page-Table Register） ，存放 頁表在內存中起始地址F 和 頁表長度M 。
進程在未執行時，頁表的起址和頁表長度放在 進程式控制制塊（PCB）中 ，當進程被調度時，操作系統內核會把它們放在頁表寄存器中。
邏輯地址到物理地址變換的過程：
比較頁表長度，頁表項長度和頁面大小三個概念：
在分頁存儲管理（頁式管理）系統中，只要確定了每個頁面的大小，邏輯地址結構就確定了。因此， 頁式管理中地址是一維的。 即只要給出一個邏輯地址，系統就可以自動算出頁號、頁內偏移量兩個部分，並不需要顯示告系統這個邏輯地址中，頁內偏移量佔多少位。
基本地址變換結構需要訪問兩次內存： 第一次訪問內存查找頁表；第二次訪問物理內存對應的內存單元。
對於上圖，會很頻繁地訪問10號塊中的指令、23號塊。
時間局部性 ：如果執行了程序中的某條指令，那麼不久後這條指令很有可能再次執行：如果某個數據被訪問過，不久之後該數據很有可能再次被訪問。（因此程序中存在大量循環）。
空間局限性 ：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元也很有可能被訪問。（因為很多數據在內存中都是連續存放的。如上面的數組，每次循環一次都會訪問鄰近的下一個元素地址）。
在基本地址變換機構中，每次訪問一個邏輯地址，都需要查詢內幕才能中的頁表。由於局部性原理，可能連續很多次查找到的都是一個頁表項。既然如此，就可以利用這個特性減少訪問頁表的次數——快表。
快表 ，又稱 聯想寄存器（TLB） ，是一種 訪問速度比內存快很多 的高速緩沖存儲器，用來存儲當前訪問的若干頁表項，以加速地址變換的過程。與此對應，內存中的頁表常稱為 慢表。
快表的地址包換過程：
(1) CPU給出邏輯地址，由某個硬體算得頁號、頁內偏移量，將頁號與快表中的所有頁號進行比較。
(2) 如果找到匹配的頁號，說明要訪問的頁表項在快表中有副本，則直接從中取出該頁對應的內存塊號，再根據內存塊號中與頁內偏移量算地物理地址。最後訪問該物理地址對應的內存單元。因此如果快表命中，則訪問某個邏輯地址只需 一次 訪問內存即可。
(3) 如果沒有找到匹配的頁號，則就需要訪問頁表，需要兩次訪問內存，在第一次訪問內存查詢得到頁號後，需要將頁號添加到快表中，以便後面再次被訪問。如果快表已滿，則必須按照一定的演算法對舊的頁表項進行替換。
由於查詢快表比查詢頁表的速度快很多，因此只要快表命中，就可以節省很多時間。因為局部性原理，一般來說快表的命中率可以達到90%以上。
7. 基本分頁存儲管理
假設是按位元組編址
考慮支持多道程序的兩種連續分配方式
原因：連續分配要求進程佔有的必須是一塊連續的內存區域
能否講一個進程分散地裝入到許多不相鄰的分區，便可充分利用內存
基本分頁存儲管理的思想：把內存分為一個個相等的小分區，再按照分區大小把進程拆分成一個個小部分
頁框/頁幀：內存空間分成的一個個大小相等的分區（比如4KB）
頁框號：頁框的編號，從0開始，從低地址開始
頁/頁面：用戶進程的地址空間分為和頁框大小相等的一個個區域
頁號：頁/頁面的編號，從0開始
進程的最後一個頁面可能沒有一個頁框那麼大，頁框不能太大，否則可能產生過大的內部碎片
操作系統以頁框為單位為各個進程分配內存空間。進程的每個頁面分別放入一個頁框中，也就是說，進程的頁面與內存的頁框有一一對應的關系
每個頁面不必連續存放，也不必按照先後順序，可以放到不相鄰的各個頁框中
進程在內存中連續存放時，通過動態重定位實現邏輯地址到物理地址的轉換。在裝入模塊之後，內存中指令使用的依然是邏輯地址，直到指令執行的時候才會進行地址轉換。系統會設置一個重定位寄存器，用來存放裝入模塊存放的起始位置，重定位寄存器中的值加上邏輯地址就是該邏輯地址實際對應的物理地址
如果採用分頁技術
頁框大小為4KB，地址空間為4GB的系統
頁號為前20位，頁內偏移量為後12位
頁表：為了能知道進程的每個頁面在內存中存放的位置，操作系統要為每個進程建立一張頁表
一個進程對應一張頁表
進程的每一頁對應一個頁表項
每個頁表項由頁號和頁框號組成
頁表記錄進程頁面和實際存放的頁框之間的對應關系
每個頁表項的長度是相同的，頁號是隱含的
各頁表項會按順序連續存放在內存中，如果該頁表在內存中的起始地址是X，4GB/4KB系統的頁框有
用於實現邏輯地址到物理地址轉換的一組硬體機構
通常會在系統中設置一個頁表寄存器(PTR)，存放頁表在內存中的起始地址F和頁表長度M（M個頁表項）
進程未執行時，頁表的起始地址和頁表長度放在進程式控制制塊(PCB)中，當進程被調度時，操作系統內核會把他們放到頁表寄存器中
基本分頁存儲管理中地址是一維的，即只要給出一個邏輯地址，系統就可以自動計算出頁號、偏移量，不需要顯式告訴系統偏移量是多少
理論上，頁表項長度為3即可表示內存塊號的范圍，但是為了方便頁表查詢，會讓頁面恰好能裝得下整數個頁表項，令每個頁表項佔4位元組
4KB頁面，可以放4096/3 =1365個頁表項，有4096%3 =1B的碎片，訪問1365及之後的頁表項時，還要考慮前面的頁框中的碎片，才能得到頁表項的物理地址，比較麻煩
進程頁表通常存放在連續的頁框中，這樣就能用統一的計算方式得到想要得到的頁表項存儲的位置
地址變換過程中有兩次訪存操作：查詢頁表、訪問目標內存單元
局部性原理
如果這個程序將程序對應的指令存放在10號內存塊，將程序中定義的變數存放在23號內存塊，當這個程序執行時，會很頻繁地反問10、23號內存塊
時間局部性：如果執行了程序中的某條指令，那麼不久後這條指令很有可能被再次執行；如果某個數據被訪問過，不久之後該數據很有可能再次被訪問（因為程序存在大量循環）
空間局部性：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元也很有可能被訪問（因為很多數據在內存中連續存放）
基本地址變換機構中，每次要訪問一個邏輯地址，都要查詢頁表，由於局部性原理，可能連續多次查詢同一個頁表項
快表：又稱聯想寄存器（TLB），是一種訪問速度比內存塊很多的高速緩存，用來存放當前訪問的若干頁表項，以加速地址變換的過程。內存中的頁表常稱為慢表
引入快表後地址的變換過程
一般來說，快表的命中率可以達到90%以上
單級頁表存在的問題
對問題1
可將頁表進行分組，使每個內存塊剛好可以放入一個分組。為離散分配的頁表再建立一張頁表，稱為頁目錄表，或外層頁表
各級頁表的大小不能超過一個頁面
針對兩級頁表
對問題2
可以在需要訪問頁面時，才把頁面調入內存（虛擬存儲技術），可以在頁表項中增加一個標志位，用於表示該頁面是否已經調入內存
若想訪問的頁面不在內存中，會產生缺頁中斷（內中斷），然後將目標頁面從外存調入內存
之後的文章會有展開
兩級頁表訪存次數分析：如果沒有TLB，第一次訪存是訪問內存中的頁目錄表，第二次訪存是訪問內存中的二級頁表，第三次訪存是訪問目標內存單元