作者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/cn.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