[理工] 反轉分頁表和一般page table的差別

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