第七章 容量大且快速：利用階層式記憶體,頁,計算機組織與設計-軟硬體介面,Ch.7 記憶體,Ch.7 記憶體,虛擬記憶體,主記憶體作為次儲存體(一般為disk)的快取.這個技巧我們稱為虛擬記憶體.,設計虛擬記憶體的動機:,1.使記憶體能夠有效率且安全的分享給好幾個程式.,許多的程式都能同時在一部機器上執行,2.由於主記憶體的容量限制,能搬移小負荷的程式到次儲存體裏.,允許使用者程式超過主記憶容量大小,磁碟位址,實體位址,虛擬位址,位址轉譯,page,虛擬記憶體主記憶體作為次儲存體(一般為disk)的快取.這個,Page faults,:the data is not in memory,retrieve it from disk,huge miss penalty,thus pages should be fairly large(e.g.,4KB),reducing page faults is important(LRU is worth the price),can handle the faults in software instead of hardware,using write-through is too expensive so we use writeback,虛擬記憶體,Page faults:the data is not,P,a,g,e,o,f,f,s,e,t,V,i,r,t,u,a,l,p,a,g,e,n,u,m,b,e,r,V,i,r,t,u,a,l,a,d,d,r,e,s,s,P,a,g,e,o,f,f,s,e,t,P,h,y,s,i,c,a,l,p,a,g,e,n,u,m,b,e,r,P,h,y,s,i,c,a,l,a,d,d,r,e,s,s,P,h,y,s,i,c,a,l,p,a,g,e,n,u,m,b,e,r,V,a,l,i,d,I,f,0,t,h,e,n,p,a,g,e,i,s,n,o,t,p,r,e,s,e,n,t,i,n,m,e,m,o,r,y,P,a,g,e,t,a,b,l,e,r,e,g,i,s,t,e,r,P,a,g,e,t,a,b,l,e,2,0,1,2,1,8,3,1,3,0,2,9,2,8,2,7,1,5,1,4,1,3,1,2,1,1,1,0,9,8,3,2,1,0,2,9,2,8,2,7,1,5,1,4,1,3,1,2,1,1,1,0,9,8,3,2,1,0,指向分頁表開始處,一個page為4,KB,實體記憶體大小為1GB,可定址到4GB,虛擬記憶體,Page offsetVirtual page number,P,h,y,s,i,c,a,l,m,e,m,o,r,y,D,i,s,k,s,t,o,r,a,g,e,V,a,l,i,d,1,1,1,1,0,1,1,0,1,1,0,1,P,a,g,e,t,a,b,l,e,V,i,r,t,u,a,l,p,a,g,e,n,u,m,b,e,r,P,h,y,s,i,c,a,l,p,a,g,e,o,r,d,i,s,k,a,d,d,r,e,s,s,虛擬記憶體,0表示資料在磁碟,1表示資料在記憶體.,Page table 也是儲存在記憶裏,故至少做兩次記憶體存取.(效能問題?),Physical memoryDisk storageVal,V,a,l,i,d,1,1,1,1,0,1,1,0,1,1,0,1,P,a,g,e,t,a,b,l,e,P,h,y,s,i,c,a,l,p,a,g,e,a,d,d,r,e,s,s,V,a,l,i,d,T,L,B,1,1,1,1,0,1,T,a,g,V,i,r,t,u,a,l,p,a,g,e,n,u,m,b,e,r,P,h,y,s,i,c,a,l,p,a,g,e,o,r,d,i,s,k,a,d,d,r,e,s,s,P,h,y,s,i,c,a,l,m,e,m,o,r,y,D,i,s,k,s,t,o,r,a,g,e,A cache for address translations:translation lookaside buffer,虛擬記憶體,TLB:分頁表的cache,Valid111101101101Page tablePhy,虛擬記憶體,一旦作業系統知道造成分頁錯誤的虛擬位址,它一定會完成下列三個步驟.,1.使用虛擬位址來查詢分頁表登錄項目並找出磁碟中參考頁的位置.,2.選擇一實體來代替;如果選擇頁次被修正過了,在我們將一新的虛擬頁次載入實體頁次之前,它必須先寫出到磁碟.,3.開始一讀取動作,將參考的頁次由磁碟帶入選擇的體頁次.,虛擬記憶體一旦作業系統知道造成分頁錯誤的虛擬位址,它一定會完,虛擬記憶體,分頁錯誤時,會造成很多的時間浪費,可使用下列幾個技術來減少miss rate.,1.使用較大的區塊(page),利用空間區域性來減少miss rate.,2.虛擬記憶體之間的映射以完全關連性分頁表來製作,因此虛擬頁次可以放在主記憶體的任一個地方.,3.作業系統使用如LRU與參考位元的技術來選擇哪個頁次需被替換.,虛擬記憶體分頁錯誤時,會造成很多的時間浪費,可使用下列幾個技,階層式記憶體的通用組織架構,問題1.一個區塊可以被放置在什麼地方?,階層式記憶體任兩層間產生的4個問題.,放置方式的名稱,集合的數目,每個集合中區塊的數目,直接映射,等於快取中區塊的數目,1,集合關聯式,快取中區塊的數目/關聯性,關聯性(n-way),完全關聯式,1,等於快取中區塊的數目,增加關聯性,優點是可降低miss rate,缺點是增加成本及存取時間變長.,階層式記憶體的通用組織架構問題1.一個區塊可以被放置在什麼地,階層式記憶體的通用組織架構,問題2.如何找到區塊?,關聯性,找到區塊的方法,需要比較器數目,直接映射,索引,1,集合關聯式,利用引找到集合,再搜尋集合中的資料成員,關聯性的級數(n-way需要n個),完全關聯式,搜尋快取中所有的項目,快取的容量,分離查表,0,用來索引記憶體,階層式記憶體的通用組織架構問題2.如何找到區塊?關聯性找到,虛擬記憶體系統使用完全關聯式的放置方式.,1.因為誤失的成本很昂貴.,2.完全關聯性可以讓我們用軟體來執行複雜的放置方式以降低誤失比例.,3.完全關聯映射可以簡單的用索引方式來達成,而不需要額外的硬體及搜尋.,4.容量大的頁次代表頁次表格負荷比較小.,階層式記憶體的通用組織架構,虛擬記憶體系統使用完全關聯式的放置方式.1.因為誤失的成本很,階層式記憶體的通用組織架構,問題3.當快取誤失時,哪一個區塊將被取代替換?,1.隨機(random):被替換的區塊是隨機選出來的.,2.LRU:最長時間沒有被使用的那一個區塊會被取代替換掉.,隨機取代的方式簡單,容易實作,LRU方式則miss rate較低,當快取容量變大時,miss rate均下降,且兩者的絕對差值也會變小.,階層式記憶體的通用組織架構問題3.當快取誤失時,哪一個區塊將,階層式記憶體的通用組織架構,問題4.在寫入時會發生什麼事?,1.Write through:資訊不但被寫到快取中,還被寫到較低層次的階層式記憶體中.,簡單且成本便宜.,容易製作.,可以用寫入緩衝器增加效能.,2.Write back:資訊只有寫到快取中,只有當區塊被取代時,如果此區塊被修改過,則必須被寫入到較低層的階層式記憶體中.,單一字組能以快取記憶體的速率被處理機寫入.,寫入快取多次,但可當區塊被取代時,才寫入到次記憶體,故寫入較低層的記憶體只需要一次.,頻寬利用較有效率.,階層式記憶體的通用組織架構問題4.在寫入時會發生什麼事?1,階層式記憶體的通用組織架構,三種C:,1.強迫性誤失(,compulsory misses,):若此區塊從未被使用過,那麼,第一次讀取時,此區塊必定不在快取中,故第一次存取此區塊就會發生誤失.這也稱冷開機誤失(cold-star misses).,2.容量性誤失(,capacity misses,):當程式在執行時,若快取記憶體的,容量不夠,不能包含所有該程式需要的區塊時,就會發生誤失.因為區塊不斷被替換而當需要時又被重新擷取.,3.衝突性誤失(,conflict misses,):在集合關聯式或直接映射快取記憶體中,當,許多區塊映射到同一個集合時,所發生的快取誤失.衝突性誤失就是在集合關聯式或直接映射快取中發生的誤失.這種誤失在相同容量的完全關聯式快取中是不會發生的.也稱為碰撞誤失(collision misses).,階層式記憶體的通用組織架構三種C:1.強迫性誤失(comp,