作者sooge (喜歡小女友Yerin )
看板Grad-ProbAsk
標題[理工] 反轉分頁表和一般page table的差別
時間Wed Jan 30 13:35:47 2019
大家好 小弟對於反轉分頁表的疑惑一直不解，一直以來都是死記硬背反轉分頁表的定義
，但始終不明白到底和一般的page table到底差在哪
希望有人可以指點一下迷津T﹏T
一般的page table是紀錄page number和frame number，將page number轉為frame number
後再透過frame number去memory找資料
反轉分頁表的定義是：page table是以physical memory作為紀錄對象，若有n個frame，
則inverted page table就有n個entry
每個entry紀錄<process id，process number>配對資訊
代表此frame是哪個page所佔用
但我對inverted page table的儲存方法一直沒有感覺
明明最後還是要去memory查資料
存成一般的page table和存成<process id，process number>的樣子有什麼差別嗎？
為什麼反轉分頁表就可以節省page table size。
求各位強者幫忙解答
一般page table
https://i.imgur.com/zABkNB2.jpg
inverted page table
https://i.imgur.com/RYDUL0I.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.248.155
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548826550.A.C91.html
※ 編輯: sooge (111.83.248.155), 01/30/2019 13:44:35
1F：→ S2067030: 因為反轉分頁表只有一份，不會浪費太多空間存別人資料 01/30 13:44
2F：→ sooge: 可是page table也是一份 01/30 13:48
3F：→ sooge: 像multilevel paging和hashing page table都是一個entry裡 01/30 13:51
4F：→ sooge: 塞很多資料所以可以縮小size 但反轉分頁表就....無法理解 01/30 13:51
5F：→ S2067030: 我想一下怎麼解釋字比較少 01/30 13:52
6F：→ S2067030: 一般的分頁表，會花很多實體記憶體，在記錄其他的實體記 01/30 13:55
7F：→ S2067030: 憶體正在使用的情形，但是反轉分頁表，只有一份紀錄全部 01/30 13:56
8F：→ S2067030: 當然這樣做缺點就是你筆記寫的那兩個，所以才要用雜湊 01/30 13:57
9F：推 gama79530: page table是用virtual page number去做tag用來對應到p 01/30 13:58
10F：→ gama79530: hysical frame number，可以有很多個page table給不同p 01/30 13:58
11F：→ gama79530: rocess用 01/30 13:58
12F：推 y2j60537: cpu裡面有10個process就有10個page table 01/30 13:59
13F：推 ko330: 一般的 page table 10個process在跑就有10份阿 01/30 14:00
14F：→ S2067030: 你把他想成，每個人都有一份資料(page table)去查找phy 01/30 14:02
15F：→ S2067030: 跟大家使用雜湊共用一份去查找phy，後者比較省空間 01/30 14:03
16F：→ S2067030: (反轉)執行的時候就是把ASID送過去逐一查找反轉分頁表 01/30 14:05
17F：→ sooge: 哦哦懂了 雖然還是有點不太理解中間轉換過程 總而言之就是 01/30 14:07
18F：→ sooge: 雜湊的裂化版就對了? 01/30 14:07
19F：→ S2067030: 轉換過程就是Process產生pid跟p跟頁篇移量 01/30 14:12
20F：→ S2067030: 然後用pid去反轉分頁表找實體記憶體的進入點 01/30 14:13
21F：→ S2067030: 找到以後在+d (頁偏移量) 就可以拿到phy位置了 01/30 14:13
22F：推 gama79530: inverted page table感覺就很像反過來，直覺上的思考方 01/30 14:14
23F：→ gama79530: 式是把physical frame number當tag用來對應到virtual p 01/30 14:15
24F：→ gama79530: age number，不過實際上我們只會需要把VA轉PA，如果照 01/30 14:15
25F：→ gama79530: 這種方式的話會不知道對應到哪一個virtual address spa 01/30 14:15
26F：→ gama79530: ce 01/30 14:15
27F：→ gama79530: 所以解套的辦法是把process id也加進去VA裡面，用這種 01/30 14:15
28F：→ gama79530: 方式的話完整的VA應該是processID串virtual address 01/30 14:15
29F：→ sooge: 所以和一般的page table就是差一個pid而已嗎 因為要紀錄所 01/30 14:25
30F：→ sooge: 有的process資訊，上面大大們講了那麼多，但感覺我理解有 01/30 14:25
31F：→ sooge: 障礙= = 這樣反轉分頁表紀錄了所有process的轉換資訊 page 01/30 14:25
32F：→ sooge: table不是應該要爆炸大嗎 01/30 14:25
33F：→ sooge: 一個frame對應到一個entry怎麼反轉分頁表不會和memory一樣 01/30 14:27
34F：→ sooge: 大 01/30 14:27
35F：→ S2067030: 大到靠北所以才要靠Hash幫忙減少次數啊y 01/30 14:31
36F：→ gama79530: 舉個例子，假設2g記憶體，32bit的address space 01/30 14:31
37F：→ gama79530: page size 1 byte，OS最多只會有4個process 01/30 14:31
38F：→ gama79530: page table entry不考慮任何其他bit ,例如dirty bit 01/30 14:31
39F：→ gama79530: (這個例子很極端根本不可能，不過只是舉例而已) 01/30 14:31
40F：→ gama79530: 使用一般的page table的話一個entry要32+30個bit，4個p 01/30 14:31
41F：→ gama79530: rocesses要4*2^32個entries 01/30 14:31
42F：→ gama79530: 使用inverted page table的話一個entry要有2+32+30個bi 01/30 14:31
43F：→ gama79530: t 01/30 14:31
44F：→ gama79530: 但總共有1*2^30個entry 01/30 14:31
45F：→ gama79530: 稍微算一下那一個比較省空間很明顯 01/30 14:31
46F：推 gama79530: inverted page table單一entry的size確實是要比普通的p 01/30 14:35
47F：→ gama79530: age table entry大，但是因為它總共會有的entry數量會 01/30 14:35
48F：→ gama79530: 比一般的page table少很多，所以才可以省空間 01/30 14:35
49F：→ sooge: 哦哦終於懂了!! 所以反轉分頁表也是藉由一個entry裡塞很多 01/30 14:49
50F：→ sooge: 資料量來減少page table size的方法 然後因為一個frame只 01/30 14:49
51F：→ sooge: 能對應的到一個特定的process的page 所以才失去了memory sh 01/30 14:49
52F：→ sooge: aring的特性 01/30 14:49
53F：→ sooge: 感謝樓上所有大大 01/30 14:50
54F：推 S2067030: 同為考生 在18天就解脫了 加油！ 01/30 15:02
55F：→ S2067030: 再啦 幹 01/30 15:02
56F：→ sooge: 一起加油!! 我是再25天XD 01/30 15:22
57F：推 TWkobe: 你想的沒錯 反轉會超大 除了hashing 還有用教粗粒度做法 01/30 15:45
58F：推 TWkobe: 一般你看到的是page level, 有的會用block level 01/30 15:47
59F：→ sooge: 謝謝TW大補充 01/30 16:06
60F：推 gama79530: 我發現我好像有寫錯不小心把TLB的觀念混進我的例子裡了 02/03 14:29
61F：→ gama79530: 一個entry會需要32 + 30 bit的是TLB的entry不是page 02/03 14:30
62F：→ gama79530: table的entry 02/03 14:31
63F：→ gama79530: 正確的應該是page table要有2^32個entry，一個entry要 02/03 14:32
64F：→ gama79530: 30個bit 02/03 14:33
65F：→ gama79530: inverted page table是有2^30個entry，一個entry要 02/03 14:35
66F：→ gama79530: 2+32 個bit 02/03 14:35