虛擬存儲頁演算法

① 什麼是虛擬存儲器請求式分頁存儲管理常用的頁面置換演算法有哪些試比較他們的性能。

虛擬存儲器(Virtual Memory)：在具有層次結構存儲器的計算機系統中，自動實現部分裝入和部分替換功能，能從邏輯上為用戶提供一個比物理貯存容量大得多，可定址的「主存儲器」。虛擬存儲區的容量與物理主存大小無關，而受限於計算機的地址結構和可用磁碟容量。
最佳置換演算法（OPT）（理想置換演算法）
先進先出置換演算法（FIFO）：
最近最久未使用（LRU）演算法
Clock置換演算法（LRU演算法的近似實現）
最少使用（LFU）置換演算法

② 目前大多數虛擬存儲系統採用什麼演算法

大多數虛擬存儲系統採用OPT（優化）淘汰演算法。根據相關信息展示，常用的虛擬存儲系統由主存、輔存兩級存儲器組成，其中輔存是大容量的磁表面存儲器，其採用OPT（優化）淘汰演算法。

③ 虛擬存儲方式都有哪些

目前虛擬存儲的發展尚無統一標准，從虛擬化存儲的拓撲結構來講主要有兩種方式：即對稱式與非對稱式。對稱式虛擬存儲技術是指虛擬存儲控制設備與存儲軟體系統、交換設備集成為一個整體，內嵌在網路數據傳輸路徑中；非對稱式虛擬存儲技術是指虛擬存儲控制設備獨立於數據傳輸路徑之外。從虛擬化存儲的實現原理來講也有兩種方式；即數據塊虛擬與虛擬文件系統。具體如下： 圖1對稱式虛擬存儲解決方案的示意圖
在圖1所示的對稱式虛擬存儲結構圖中，存儲控制設備 High Speed Traffic Directors（HSTD）與存儲池子系統Storage Pool集成在一起，組成SAN Appliance。可以看到在該方案中存儲控制設備HSTD在主機與存儲池數據交換的過程中起到核心作用。該方案的虛擬存儲過程是這樣的：由HSTD內嵌的存儲管理系統將存儲池中的物理硬碟虛擬為邏輯存儲單元（LUN），並進行埠映射（指定某一個LUN能被哪些埠所見），主機端將各可見的存儲單元映射為操作系統可識別的盤符。當主機向SAN Appliance寫入數據時，用戶只需要將數據寫入位置指定為自己映射的盤符（LUN），數據經過HSTD的高速並行埠，先寫入高速緩存，HSTD中的存儲管理系統自動完成目標位置由LUN到物理硬碟的轉換，在此過程中用戶見到的只是虛擬邏輯單元，而不關心每個LUN的具體物理組織結構。該方案具有以下主要特點：
（1）採用大容量高速緩存，顯著提高數據傳輸速度。
緩存是存儲系統中廣泛採用的位於主機與存儲設備之間的I/O路徑上的中間介質。當主機從存儲設備中讀取數據時，會把與當前數據存儲位置相連的數據讀到緩存中，並把多次調用的數據保留在緩存中；當主機讀數據時，在很大幾率上能夠從緩存中找到所需要的數據。直接從緩存上讀出。而從緩存讀取數據時的速度只受到電信號傳播速度的影響（等於光速），因此大大高於從硬碟讀數據時碟片機械轉動的速度。當主機向存儲設備寫入數據時，先把數據寫入緩存中，待主機端寫入動作停止，再從緩存中將數據寫入硬碟，同樣高於直接寫入硬碟的速度
（2）多埠並行技術，消除了I/O瓶頸。
傳統的FC存儲設備中控制埠與邏輯盤之間是固定關系，訪問一塊硬碟只能通過控制它的控制器埠。在對稱式虛擬存儲設備中，SAN Appliance的存儲埠與LUN的關系是虛擬的，也就是說多台主機可以通過多個存儲埠（最多8個）並發訪問同一個L

④ 虛擬頁式存儲系統

二維數組在內存中表現為連續的數據，100行 150列數據，則有15000個數據，存放在100個頁面中，因此，缺頁中斷為100次

⑤ lru的演算法是什麼

lru的演算法是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

對於虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的——當需要一個放在外存的頁面時，把它調入內存，同時為了保持原有空間的大小，還要把一個內種調動越少，進程執行的效率也就越高。

硬體支持

LRU置換演算法雖然是一種比較好的演算法，但要求系統有較多的支持硬體。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬體之一的支持：寄存器或棧。

寄存器

為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為：

R = Rn-1 Rn-2 Rn-3…R2 R1 R0。

⑥ 儲存管理中,分頁式虛擬儲存管理的頁面淘汰演算法有

儲存管理中，分頁式虛擬儲存管理的頁面淘汰演算法有先進先出法，最近最少使用頁面先淘汰，最優淘汰演算法。最優淘汰演算法(OPT)：系統預測作業今後要訪問的頁面，淘汰頁是將來不被訪問的頁面或者在最長時間後才被訪問的頁面。它保證有最少的缺頁率，但它實現困難，只能通過理論分析用來衡量其它演算法的優劣。

⑦ Windows98/XP的虛擬存儲器採用的頁面調度演算法是什麼

1 隨機演算法
用軟體或硬體隨機數產生器確定替換的頁面。
2 先進先出
先調入主存的頁面先替換。
3 近期最少使用演算法
替換最長時間不用的頁面。
4 最優演算法
替換最長時間以後才使用的頁面。這是理想化的演算法，只能作為衡量其他各種演算法優劣的標准。

⑧ 計算機組成原理——虛擬存儲器

（1）程序員在比實際主存大得多的邏輯地址空間中編寫程序

（2）程序執行時，把當前需要的程序段和數據塊掉入主存，其他暫不使用的放在磁碟上

（3）執行指令時，通過硬體將邏輯地址轉化為物理地址。虛擬地址高位為虛頁號，低位為頁內偏移地址

（4）當程序發生數據訪問或程序訪問失效(缺頁時)，由操作系統把信息從磁碟調入主存中

    （1）基本思想：

        內存被分成固定長度且長度較小的存儲塊（頁框，實頁，物理頁）

        每個進程也被劃分為固定長度的程序塊（頁，虛頁，邏輯頁）

        通過頁表，實現邏輯地址想物理地址的轉化

    （2）邏輯地址

        程序中指令所使用的地址（進程所在地址空間）

    （3）物理地址

        存放指令或數據的實際內存地址

（1）與「cache-主存」層次相比，頁大小遠比cache的行大小要大（windows中的頁位4k）

（2）採用全相聯映射方式：磁碟中的任意一個頁能用射到內存中的任意一個頁

    因為缺頁導致中斷時，操作系統從磁碟拿數據通常要耗費幾百萬個時鍾周期。增大頁大小，可以減少缺頁中斷

（3）為什麼讓軟體處理「缺頁」

    因為訪問磁碟需要好粉幾百萬個時鍾周期，硬體即使能立刻把地址打給磁碟，磁碟也不能立即響應

（4）為什麼地址轉換用硬體實現

    硬體實現地址轉換可以加快指令的執行速度

（5）為什麼頁寫會策略採用write back

    避免頻繁的慢速磁碟訪問

頁表的首地址放在基址寄存器。採用基址定址方式

每個頁表項前面有一個虛頁號：從0開始遞增的序號。頁表項又分為幾個結構：

（1）裝入位：該頁是否在內存中

（2）修改位：該也在內存中是否被修改

（3）替換控制位：用於clock演算法

（4）其他

（5）實頁號（8進制）

（1）一次磁碟引用需要訪問幾次主存？2次，一次查頁表，一次查物理地址。於是，把經常查的頁表放到cache中。這種在cache頁表項組成的頁表稱為TLB（Translation Lookside Buffer）

（2）TLB的頁表結構：tag + 主存中的頁表項

當採用全相連映射時，tag為頁表項前面的虛頁號。需要把tag和虛頁號一一比較

當採用組相聯映射時，tag被分為tag+index，虛頁號的高位為tag，虛頁號的低位為index，做組內索引(屬於組內第幾行)

    1.段式存儲是根據程序邏輯，給程序分段。使得每段大小不同。這種虛擬地址劃分方法適合程序設計

    2.段式存儲的虛擬地址由段號和段內偏移地址組成。段式虛擬存儲器到物理地址的映射通過段表實現

    3.段式虛擬存儲會造成空頁

    1.段頁式虛擬存儲，先把程序按照邏輯分成段，再把每段分成固定大小的頁。

    2.程序對主存的調入調出是按照頁面進行的；但他有可以根據段實現共享和保護

    3.缺點是段頁式虛擬地址轉換成物理地址需要查詢2個表：段表和頁表。段表找到相應頁表的位置，頁表找到想也頁的位置

    4.段頁式細膩地址的結構可以為以下形式：

            程序地址： 用戶號(進程pid) | 段號 | 頁號 | 頁內偏移地址

（1）某計算機的cache塊工16塊，採用二路組相聯映射方式，每個主存塊大小為32位元組，按照位元組編制。則主存129號單元的主存塊硬裝如刀cache的組號是：（C）A、0      B、2      C、4      D、6

解：二路組相聯，所以每組2塊，共有16/2=8組，所以組號佔3位。

      每塊32位元組，所以塊內地址佔5位。

      129轉化為二進制：1000 0001：前3位為組號，100：=4

（2）假設用若干個2K4位的晶元組成一個8K8位的存儲器，則地址0B1FH所在晶元的最小地址為：

解：用2片組成一行，共4行，所以片選地址佔2位。片內地址有2k=211，所以佔11位

      0B1FH：000|0 1|011 0001 1111 這三段為前綴，片選地址，片內地址。

      該片晶元的最小地址是片內地址全0：000|0 1|000 0000 0000 = 0800H

（3）某計算機的主存地址空間大小為256MB，按位元組編址，指令cache和數據cache分離，均有8個cache行，每行大小為64B，數據cache採用直接映射方式，現有兩個程序A，B對數組int a[256][256]進行遍歷，程序A按行遍歷，程序B按列遍歷。假定int類型數據用32位補碼表示，數組a按行優先方式存儲，其地址為320（十進制）。

問：(1) 若不考慮cache一致性維護和替換演算法所需的控制位，則數據cache的總容量佔多少？

      (2) 數組元素a[0][31]和a[1][1]各自所在主存塊對應的cache行號分別為多少（cache從0行開始）？

      (3)程序A和B的數據訪問命中率各自為多少？哪個程序的執行時間更短？

解：(1) 因為cache的總容量是cache每行的數據存儲大小+tag位+數據是否有效位+其他一致性控制位。

          主存地址空間256MB，佔28位。直接映射方式，8行，行號佔3位。每行64B，所以塊內地址佔6位，因此，tag佔28-3-6=19位

          每行有一個數據有效位。因此，cache共（19+1+648）8 = 532位元組

      (2) 因為int類型佔32位，所以一個int佔4B。a[0][31] = 320 + 314 = 444 a1 = 320 + 4(256+1) = 1348。

          塊內地址佔6位，直接映射下行號佔3位，因此444 = 110 | 111100，所以行號為6

          1348 = 10 | 101 | 000100，所以行號為5

      (3) 因為1行cache佔64B，每個int數佔4B，所以一行有16個數。第一個數會因cache缺失而不命中，然後調入cache。，使得後面的15個int訪問全部命中。所以命中率為1516 對於程序B，每次調入16個數，小於數組每行的128個元素，因此每次都不會命中，命中率為0