頁表結(jié)構(gòu)
在現(xiàn)實(shí)中，頁表存在物理內(nèi)存里，因此這里就衍生了一系列問題，頁表占多大內(nèi)存？怎么管理這些內(nèi)存？
問題：
開始，這是一個(gè)很稀疏的東西（有很多頁），因此要用鏈表管理，并且要求是個(gè)變長，因?yàn)檫M(jìn)程所需要的內(nèi)存是變化的
解決：
- 線性列表
- 兩級(jí)列表
- 反頁表：反著做這個(gè)映射關(guān)系---很老的東西
虛擬內(nèi)存
這里有兩個(gè)方向
這里有兩個(gè)交換方向，我們單獨(dú)說起
1
頁交換算法，這里有兩種：
- 將來很長一段時(shí)間不會(huì)用到頁
- 交換進(jìn)來后，沒有修改過，我們稱之為clean，可以直接刪除，如果為臟的，我們不能直接刪，要存回去再刪除
u==use bit ,d==dirty bit
|磁盤|valid bit|u|d|
|-|-|-|
1 FIFO page replacement
使用先進(jìn)先出，替換最先進(jìn)來的頁：
假設(shè)有三個(gè)物理頁： 頁順序是1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pages 1, 2, 3 brought in to memory.
Page 1 ejected, page 4 in - 2, 3, 4 in memory.
Page 2 ejected, page 1 in - 3, 4, 1 in memory.
Page 3 ejected, page 2 in - 4, 1, 2 in memory.
Page 4 ejected, page 5 in - 1, 2, 5 in memory.
Pages 1 and 2 accessed in memory.
Page 1 ejected, page 3 in - 2, 5, 3 in memory.
Page 2 ejected, page 4 in - 5, 3, 2 in memory.
Page 5 accessed in memory.
9個(gè)頁錯(cuò)
解釋下：1彈出，4進(jìn)來，現(xiàn)在的序列是234
但是這種方法不是很好，再頁錯(cuò)很多，因此如何避免這個(gè)二次頁錯(cuò)
2 LRU (Lease Recently Used)
順序依舊是：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pages 1, 2, 3, 4 brought in to memory.
Pages 1 and 2 accessed in memory - 3, 4, 1 2 in memory.
Page 3 ejected, page 5 in - 4, 1, 2, 5 in memory.
Pages 1 and 2 accessed in memory.
Page 4 ejected, page 3 in - 5, 1, 2, 3 in memory.
Page 5 ejected, page 4 in - 1, 2, 3, 4 in memory.
Page 1 ejected, page 5 in - 2, 3, 4, 5 in memory.
8個(gè)頁錯(cuò)
插入5的時(shí)候，從5開始倒序檢查：214，這幾個(gè)設(shè)為常用，然后替換3
實(shí)現(xiàn)：
- 做一個(gè)雙向鏈表或是棧：每訪問一次，就壓棧。但是每訪問一次，都要棧操作，這么做的話，實(shí)在是很浪費(fèi)
-
做一個(gè)LRU的近似：可以用時(shí)間戳的概念來看，這個(gè)表走的很慢，由于許多頁它的時(shí)間戳是一樣的，所以它的分辨率很低（2頁平分1小時(shí)，1頁占1小時(shí)）
操作每隔一段時(shí)間就把他們存起來，然后清零，然后使用時(shí)候再設(shè)置1
3FIFO with second chance
鐘表找下一個(gè)是0還是1
- 0：替換
- 1：置為０后找下一個(gè)
進(jìn)一步更改
|磁盤|valid bit|u|d|
|-|-|-|
use = 0, dirty = 0: Best page to replace.
use = 0, dirty = 1: Next best - has not been recently used.
use = 1, dirty = 0: Next best - don't have to write out.
use = 1, dirty = 1: Worst.
在表上轉(zhuǎn)好幾圈來找
2
每個(gè)頁表或者TLB有個(gè)valid bit，如果valid bit是1則他是物理內(nèi)存，如果是0在磁盤
地板塊是虛擬頁（邏輯上的），我可以踩這些東西，如果在地上，很好可以通過頁表訪問，但是如果不在地上，某些頁在天花板上（物理上的）。我們稱之為頁錯(cuò)
- page fault：訪問頁時(shí)，他是1，那么非常好，通過映射正常訪問，但是如果是0，cpu不能直接讀磁盤，他要等磁盤的東西讀入到內(nèi)存才可訪問（這部分內(nèi)容由操作系統(tǒng)接管）：
- 保存寄存器和進(jìn)程狀態(tài)
- 檢查發(fā)生頁錯(cuò)的原因：是合法訪問還是非法訪問
- 找到空頁：每個(gè)座位是內(nèi)存頁，我們要找到空位子才能放進(jìn)來，如果沒有空位（后面會(huì)提到）
- 操作系統(tǒng)給磁盤指令讀取頁
- 在等待時(shí)，將cpu分配給其他進(jìn)程（cpu不會(huì)等你）
- 從I/O接收到中斷（數(shù)據(jù)讀取完畢，已經(jīng)存儲(chǔ)在內(nèi)存中）
- 把valid bit值更新為1
- 有效訪問時(shí)間：不關(guān)心沒次訪問的時(shí)間，如果我有大量的內(nèi)存訪問，p是0~1之間的值，如果是0，永遠(yuǎn)不會(huì)發(fā)生頁錯(cuò)，如果是1必定會(huì)發(fā)生頁錯(cuò)：
- 在內(nèi)存上：設(shè)100納秒為訪問內(nèi)存時(shí)間
- 在磁盤上：25毫秒=2.5x10^6納秒
- 則平均訪問時(shí)間=100（1-P）+2.5x10^6(1-P)
- 交換到哪里：
- 磁盤上專門開辟一個(gè)空間，叫做交換區(qū)
- 交換到系統(tǒng)盤（文件系統(tǒng)） ---windows經(jīng)常這么干
- 一些細(xì)節(jié)
當(dāng)頁錯(cuò)發(fā)生時(shí)，我們要有可用的資源，不僅要做也要能替換，還要把修改過的頁寫回磁盤－－－>使干凈頁的幾率提高
工作集：每個(gè)進(jìn)程都有頁集合，它隨著時(shí)間會(huì)變化（每段時(shí)間處理的數(shù)據(jù)不一樣）－－－解決需要頻繁處理的頁 - thrashing
當(dāng)進(jìn)程越來越多,CPU利用率越來越高,物理內(nèi)存小于工作集大小 - 花錢多買內(nèi)存
- 少跑進(jìn)程
