Virtual memory 虛擬內(nèi)存

虛擬內(nèi)存的作用

• 將主存看成存儲(chǔ)在磁盤上的地址空間的高速緩存，在主存中只保存活動(dòng)區(qū)域，并根據(jù)需要在磁盤和主存之間來(lái)回傳送數(shù)據(jù)，高效實(shí)用主存
• 為每個(gè)進(jìn)程提供一致的地址空間，簡(jiǎn)化內(nèi)存管理
• 保護(hù)每個(gè)進(jìn)程的地址空間不被其他進(jìn)程破壞
  • 保護(hù)：一組確保共享處理器、主存、I/O設(shè)備的多個(gè)進(jìn)程之間沒有故意地，無(wú)意地讀寫其他進(jìn)程的數(shù)據(jù)機(jī)制

物理地址和虛擬地址 Physical Address & Virtual Address

物理地址： 主存儲(chǔ)器的地址

物理尋址： CPU執(zhí)行指令后直接生成一個(gè)物理地址，通過(guò)內(nèi)存總線傳遞給主存。主存取出物理地址處的字節(jié)并返回給CPU

虛擬地址： 虛擬空間的地址，當(dāng)需要訪問(wèn)主存時(shí)需要通過(guò)地址映射轉(zhuǎn)換為物理地址

虛擬尋址： CPU執(zhí)行指令后先生成一個(gè)虛擬地址，虛擬地址在被送到內(nèi)存之前先轉(zhuǎn)換成對(duì)應(yīng)的物理地址（地址翻譯 address translation）

虛擬存儲(chǔ)器和cache的工作原理是一樣的，在虛擬存儲(chǔ)器中，塊被稱為頁(yè)（page），訪問(wèn)缺失稱為缺頁(yè)（page fault） 即訪問(wèn)的頁(yè)不在主存中，需要到磁盤中去尋找。

Page fault的代價(jià)是很高的，一次缺頁(yè)處理將花費(fèi)數(shù)百萬(wàn)個(gè)時(shí)鐘周期，因?yàn)橹鞔娲蟾疟却疟P快100000倍。

在設(shè)計(jì)虛擬存儲(chǔ)系統(tǒng)時(shí)應(yīng)考慮一些關(guān)鍵性因素：

• 頁(yè)應(yīng)該足夠大（目前典型4-16KB）
• 使用能降低缺頁(yè)率的組織結(jié)構(gòu)（頁(yè)以全相聯(lián)（fully associated）的方式放置
• 缺頁(yè)用軟件處理，使用算法來(lái)選擇替換頁(yè)
• 由于寫時(shí)間太長(zhǎng)，因此在虛擬內(nèi)存中，寫直達(dá)機(jī)制不能很好地管理寫操作，因此虛擬存儲(chǔ)系統(tǒng)中都采用寫回機(jī)制

虛擬存儲(chǔ)器的地址被劃為虛頁(yè)號(hào)（virtual page number）和頁(yè)偏移（page offset），物理頁(yè)號(hào)構(gòu)成物理地址的高位部分，而頁(yè)偏移是不變的，構(gòu)成物理地址的低位部分，頁(yè)偏移域的位數(shù)決定了頁(yè)的大小。

Example：

64KB pages -> 2^6 * 2^10 bytes pages -> 2^16 bytes pages -> 16-bit page offset

64-bit machine -> 64-bit virtual address -> 64 - 16 (page offset) = 48-bit virtual page number

Maximum 256MB memory -> 2^8 * 2^20 Bytes memory -> 2^28 Bytes -> 28-bit Physical Address

-> 28-16 (page offset) = 12-bit Physical page number

頁(yè)的存放和查找

頁(yè)表 Page table

——保存著虛擬地址和物理地址之間轉(zhuǎn)換關(guān)系的表。頁(yè)表保存在主存中，通常使用虛頁(yè)號(hào)來(lái)索引。如果這個(gè)虛頁(yè)當(dāng)前在主存中，頁(yè)表中的對(duì)應(yīng)項(xiàng)將包含虛頁(yè)對(duì)應(yīng)的物理頁(yè)號(hào)。

• 每個(gè)進(jìn)程都有它自己的頁(yè)表
• 頁(yè)表就是一個(gè)頁(yè)表?xiàng)l目（page table entry）的數(shù)組。虛擬地址空間中的每個(gè)頁(yè)在頁(yè)表中的一個(gè)固定偏移量處都有一個(gè)PTE
• 每個(gè)頁(yè)表?xiàng)l目包含1位有效位，如果該位為無(wú)效，則該頁(yè)不在主存中，就發(fā)生一次缺頁(yè)。如果該位為有效，表明該頁(yè)在主存中，并且該頁(yè)包含有物理頁(yè)號(hào)。

為了指出頁(yè)表在存儲(chǔ)器中的位置，硬件包含一個(gè)指向頁(yè)表首地址的寄存器：頁(yè)表寄存器（Page table register）

頁(yè)表大小 Page Table Size：

E.g.

How big is a page table on the following machine?

• 32-bit machine
• 4B per page table entry
• 4KB pages

32-bit machine -> 32-bit virtual address -> 2^32 = 4 * 2^30 bytes virtual memory -> 4GB virtual memory

4GB virtual memory / 4KB page size = 2*20 virtual pages = 1M virtual pages

1M virtual pages * 4 Bytes per page table entry = 4 MB page table.

How big would the page table be with 64KB pages?

4GB virtual memory / 64KB page size = 64K virtual pages

64k virtual pages * 4B per page table entry = 256 KB

How big would it be for a 64-bit machine, 64KB pages?

64-bit machine -> 64-bit virtual address -> 2^64 bytes virtual memory

2^64 bytes virtual memory / 64KB page size = 2^48 virtual pages

2^48 virtual pages *4B per page table entry = 2^50 = 1 peta-Byte page table.

----->> TOO large to fit in memory!

并且，就算頁(yè)表的大小是4MB，每個(gè)程序在執(zhí)行的任何時(shí)候都需要4MB的存儲(chǔ)器空間，如果同時(shí)有成百上千個(gè)進(jìn)程同時(shí)運(yùn)行，每個(gè)程序都有各自的頁(yè)表，所需的存儲(chǔ)量也是巨大的。

以下幾種方法都是針對(duì)減少所需的最大存儲(chǔ)量以及減少用于頁(yè)表的主存：

• 使用界限寄存器，對(duì)給定的進(jìn)程限制其頁(yè)表的大小。

  缺陷：要求地址空間只朝一個(gè)方向拓展

• 但允許地址空間只朝一個(gè)方向拓展往往不夠，因?yàn)槎鄶?shù)語(yǔ)言需要兩種大小可擴(kuò)展的區(qū)域：從最高地址往下擴(kuò)展的棧空間和從最低地址網(wǎng)上擴(kuò)展的堆空間。這就意味著有兩個(gè)獨(dú)立的頁(yè)表和兩個(gè)獨(dú)立的界限。兩個(gè)頁(yè)表的使用將地址空間分成兩段。地址的高位用于判斷該地址使用了哪個(gè)段和哪個(gè)頁(yè)表。由于段由地址的高位部分決定，每一段可以有地址空間的一半大。每段的界限寄存器指定了當(dāng)前段的大小，該大小以頁(yè)尾單位增長(zhǎng)。

  缺陷：當(dāng)以一種稀疏方式使用地址空空間而不是連續(xù)的虛擬地址時(shí)，執(zhí)行效果就不大好。

• 反置頁(yè)表，對(duì)虛擬地址使用哈希函數(shù)，頁(yè)表需要的容量?jī)H僅是主存中的物理頁(yè)數(shù)。

  缺陷：查找過(guò)程略微復(fù)雜，因?yàn)椴荒軆H依靠索引來(lái)訪問(wèn)頁(yè)表。

• 將頁(yè)表再分頁(yè)，來(lái)減少頁(yè)表占用的實(shí)際主存空間

• 多級(jí)頁(yè)表。 這種機(jī)制允許以一種稀疏的方式來(lái)使用地址空間而不用分配整個(gè)頁(yè)表。對(duì)很大的地址空間和在需要非連續(xù)地址分配的軟件系統(tǒng)中，這種機(jī)制尤為有效。

  缺陷：地址轉(zhuǎn)換過(guò)程更為復(fù)雜。

加快地址轉(zhuǎn)換：TLB

由于頁(yè)表放在主存中，程序每次訪問(wèn)至少需要兩次：

先獲得物理地址

再獲取數(shù)據(jù)

提高訪問(wèn)性能的關(guān)鍵在于依靠頁(yè)表的訪問(wèn)局部性：當(dāng)一個(gè)轉(zhuǎn)換的虛頁(yè)號(hào)被使用時(shí)，它可能在不久的將來(lái)再次被用到（temporal locality

所以處理器中都包含一個(gè)特殊的cache來(lái)跟蹤最近使用過(guò)的地址變換，即快表（Translation-Lookaside Buffer，TLB），地址變換高速緩存。

• Small cache: 16-64 entries, often fully associated.

Work Steps

CPU產(chǎn)生一個(gè)虛擬地址

從TLB中取出相應(yīng)的PTE

• TLB命中：

  • 將虛擬地址翻譯成物理地址，并發(fā)送到高速緩存/主存
  • 高速緩存/主存將所請(qǐng)求的數(shù)據(jù)字返回給CPU

• TLB不命中（TLB Miss）

  • 在頁(yè)表中取出相應(yīng)的PTE
  • 新取出的PTE放在TLB中，可能會(huì)覆蓋一個(gè)已經(jīng)存在的條目

• 頁(yè)表不命中（Page fault）

  • 操作系統(tǒng)獲得控制權(quán)，控制的轉(zhuǎn)移由異常機(jī)制完成

  • 必須在下一集存儲(chǔ)器層次中找到該頁(yè)（通常是閃存或磁盤），然后決定將其放到主存中

  • 選擇近期內(nèi)不會(huì)被使用的頁(yè)進(jìn)行替換（LRU，最少使用替換策略）

    • LRU算法

      完全準(zhǔn)確執(zhí)行LRU代價(jià)太高，大多數(shù)OS通過(guò)跟蹤哪些頁(yè)最近被使用哪些沒有來(lái)近似地實(shí)現(xiàn)LRU算法

      提供一個(gè)引用位（reference bit/use bit），當(dāng)一頁(yè)被訪問(wèn)時(shí)該位被置位。

      OS定期將引用位清零，然后再重新記錄，來(lái)判定在這段特定時(shí)間內(nèi)哪些頁(yè)被訪問(wèn)過(guò)

    • 假定某一頁(yè)在很長(zhǎng)一段時(shí)間都沒有被訪問(wèn)，那么該頁(yè)再被訪問(wèn)的可能性比最近經(jīng)常訪問(wèn)的頁(yè)的可能性要小，被替換的頁(yè)寫入磁盤的交換區(qū)（Swap space）。

    • Swap space

      由于我們無(wú)法提前獲知存儲(chǔ)器的某一頁(yè)什么時(shí)候會(huì)被替換出去，因此OS在創(chuàng)建進(jìn)程的時(shí)候會(huì)在閃存或者磁盤上為進(jìn)程中所有的頁(yè)創(chuàng)建空間（Swap space）

存儲(chǔ)器層次結(jié)構(gòu)的全部操作

存儲(chǔ)器層級(jí)結(jié)構(gòu)由一個(gè)TLB和一個(gè)cache組成。一次存儲(chǔ)器訪問(wèn)可能遇到三種不同類型的確實(shí)：TLB缺失、缺頁(yè)以及cache缺失。

最好的情況下，虛擬地址由TLB進(jìn)行轉(zhuǎn)換，然后被送到cache找到相應(yīng)的數(shù)據(jù)，取回并送入處理器。

最壞的情況下，訪問(wèn)在存儲(chǔ)器層次結(jié)構(gòu)的TLB、頁(yè)表和cache這三個(gè)部件中都發(fā)生缺失。

總結(jié)

以上是生活随笔為你收集整理的【计算机基础】 Virtual memory 虚拟内存的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。