操作系統(tǒng)-課件lec7存儲(chǔ)器管理

計(jì)算機(jī)與操作系統(tǒng)

第七講存儲(chǔ)管理南京大學(xué)軟件學(xué)院15:52本主題教學(xué)目標(biāo)掌握存儲(chǔ)管理的基本內(nèi)容掌握固定分區(qū)存儲(chǔ)管理掌握可變分區(qū)存儲(chǔ)管理掌握對(duì)換、重定位、地址等概念初步掌握段式存儲(chǔ)管理初步掌握頁式存儲(chǔ)管理掌握Cache的工作原理

第七講存儲(chǔ)管理7.1內(nèi)存管理的需求7.2內(nèi)存分區(qū)7.3分段管理

7.4分頁管理7.5Cache7.1內(nèi)存管理的需求7.1內(nèi)存管理的需求內(nèi)存的重定位內(nèi)存保護(hù)內(nèi)存共享內(nèi)存的邏輯組織內(nèi)存的物理組織進(jìn)程在尋址方面的需求重定位可用的主存空間通常被許多進(jìn)程共享并不能事先知道在某個(gè)程序執(zhí)行期間會(huì)有其他哪些程序駐留在主存中希望通過提供一個(gè)巨大的就緒進(jìn)程池，能夠把活動(dòng)進(jìn)程換入或換出主存，以便使處理器的利用率最大化操作系統(tǒng)需要知道進(jìn)程控制信息和執(zhí)行棧，以及該進(jìn)程開始執(zhí)行程序的入口點(diǎn)的位置處理器硬件和操作系統(tǒng)軟件必須能夠把程序代碼中的存儲(chǔ)器訪問轉(zhuǎn)換成實(shí)際的物理存儲(chǔ)器地址，以反映程序在主存中的當(dāng)前位置重定位地址轉(zhuǎn)換與存儲(chǔ)保護(hù)

程序的編譯、鏈接、裝入和執(zhí)行鏈接動(dòng)態(tài)重定位靜態(tài)重定位…源程序模塊1源程序模塊2源程序模塊n…目標(biāo)代碼1目標(biāo)代碼2目標(biāo)代碼n可重定位目標(biāo)代碼(裝載代碼)(輔存)編譯裝入執(zhí)行程序名字空間邏輯地址空間物理地址空間可執(zhí)行二進(jìn)代碼(主存)庫代碼可執(zhí)行二進(jìn)代碼(主存)

內(nèi)存的保護(hù)每個(gè)進(jìn)程都應(yīng)該受到保護(hù)，以免被其他進(jìn)程有意或無意地干涉，該進(jìn)程以外的其他進(jìn)程中的程序不能地訪問(讀操作或?qū)懖僮?該進(jìn)程的內(nèi)存單元在某種意義上，要滿足重定位的需求增加了滿足保護(hù)需求的難度。由于程序在主存中的位置是不可預(yù)測的，因而在編譯時(shí)不可能檢查絕對(duì)地址來確保保護(hù)必須在運(yùn)行時(shí)檢查進(jìn)程產(chǎn)生的所有存儲(chǔ)器訪問，以便確保它們只訪問了分配給該進(jìn)程的存儲(chǔ)空間內(nèi)存的共享以允許多個(gè)進(jìn)程訪問主存的同一部分例如，如果許多進(jìn)程正在執(zhí)行同一個(gè)程序，則允許每個(gè)進(jìn)程訪問該程序的同一個(gè)副本要比讓每個(gè)進(jìn)程有自己單獨(dú)的副本更有優(yōu)勢內(nèi)存的邏輯組織模塊可以被獨(dú)立地編寫和編譯，系統(tǒng)在運(yùn)行時(shí)解析從一個(gè)模塊到其他模塊的所有引用可以給不同的模塊以不同的保護(hù)級(jí)別(只讀、只執(zhí)行)模塊可以被多個(gè)進(jìn)程共享內(nèi)存的物理組織當(dāng)可供程序和數(shù)據(jù)使用的主存可能不足時(shí)，程序員必須采用覆蓋技術(shù)來組織程序和數(shù)據(jù)，不同的模塊被指派到主存中的同一塊區(qū)域，主程序員在需要時(shí)換入或換出模塊在多道程序設(shè)計(jì)環(huán)境中，程序員在編寫代碼時(shí)并不能知道可用空間的大小及位置7.2內(nèi)存分區(qū)7.2內(nèi)存分區(qū)7.2.1固定分區(qū)7.2.2動(dòng)態(tài)分區(qū)7.2.3伙伴系統(tǒng)7.2.4內(nèi)存不足的存儲(chǔ)管理技術(shù)7.2.1固定分區(qū)固定分區(qū):大小相等或者大小相等小于或等于分區(qū)容量的任何進(jìn)程都可以裝入到任何可用分區(qū)中如果所有的分區(qū)都滿了，并且沒有進(jìn)程處于就緒態(tài)或運(yùn)行態(tài)，則操作系統(tǒng)可以換出一個(gè)進(jìn)程，并裝入另一個(gè)進(jìn)程，使得處理器有事可做程序可能超出任意分區(qū)的容量，程序員必須使用覆蓋技術(shù)設(shè)計(jì)程序，使得在任何時(shí)候該程序只有一部分需要放到主存中7.2.1固定分區(qū)主存的利用率非常低任何程序，即使很小，都需要占據(jù)一個(gè)完整的分區(qū)假設(shè)存在一個(gè)長度小于2M的程序，當(dāng)它被換入時(shí)，仍占據(jù)了一個(gè)8M的分區(qū)由于被裝入的數(shù)據(jù)塊小于分區(qū)大小，從而導(dǎo)致分區(qū)內(nèi)部有空間浪費(fèi)，這種現(xiàn)象稱為內(nèi)部碎片7.2.1固定分區(qū)(例)固定分區(qū)的放置算法大小相等的分區(qū)由于所有的分區(qū)大小相等，因而使用哪個(gè)分區(qū)都沒有關(guān)系大小不等的分區(qū)最簡單的方法是把每個(gè)進(jìn)程指定到足夠容納它的最小分區(qū)每個(gè)分區(qū)都需要維護(hù)一個(gè)調(diào)度隊(duì)列使每個(gè)分區(qū)內(nèi)部浪費(fèi)的空間(內(nèi)部碎片)最少固定分區(qū)的內(nèi)存分配固定分區(qū)的內(nèi)存分配7.2.2動(dòng)態(tài)分區(qū)7.2.2動(dòng)態(tài)分區(qū)外部碎片動(dòng)態(tài)定分區(qū)的內(nèi)存分配未分配區(qū)表已分配區(qū)表可變分區(qū)回收算法

AXB

ABAXA

XBB

x

變?yōu)樽優(yōu)樽優(yōu)樽優(yōu)閄終止前X終止后X7.2.2動(dòng)態(tài)分區(qū)分區(qū)長度和數(shù)目是可變的當(dāng)進(jìn)程被裝入主存時(shí)，給它分配與所需空間相等的存儲(chǔ)空間動(dòng)態(tài)分區(qū)方法開始時(shí)很好，但最終會(huì)導(dǎo)致在內(nèi)存中出許多小的空洞，隨著時(shí)間的推移，內(nèi)存中產(chǎn)生了越來越多的碎片，內(nèi)存的利用率隨之下降。這種現(xiàn)象稱為外部碎片現(xiàn)象（在分區(qū)外的存儲(chǔ)空間存在越來越多的碎片）克服外部碎片的一種技術(shù)是壓縮(compaction):操作系統(tǒng)不時(shí)地移動(dòng)進(jìn)程，使得進(jìn)程占用的空間連續(xù)，并且所有空閑空間連成一片動(dòng)態(tài)分區(qū)的適配算法最佳適配:選擇與要求的大小最接近的塊首次適配:從低地址掃描內(nèi)存，選擇大小足夠的第一個(gè)可用塊鄰近適配:從上一次放置的位置開始掃描內(nèi)存，選擇下一個(gè)大小足夠的可用塊最壞適配:掃描整個(gè)未分配區(qū)表或鏈表，總是挑選一個(gè)最大的空閑區(qū)首度適配最佳適配鄰近適配需求16M已分配未分配可能的新分配最后一次分配14K7.2.3伙伴系統(tǒng)在伙伴系統(tǒng)中，可用內(nèi)存塊的大小2K,LKU，其中，2L表示分配的最小塊的尺寸。2U表示分配的最大塊的尺寸；通常2U

是可供分配的這個(gè)內(nèi)存的大小?？捎糜诜峙涞恼麄€(gè)空間被看做是一個(gè)大小為2U的塊，如果請(qǐng)求的大小s滿足2U-1s2U,則分配整個(gè)空間否則，該塊被分成兩個(gè)大小相等的伙伴，大小均為2U-1如果有2U-2

s2U-1,則給該請(qǐng)求進(jìn)程分配兩個(gè)伙伴中的任何一個(gè)；否則，其中一個(gè)伙伴又被分成兩半這個(gè)過程一直持續(xù)直到產(chǎn)生大于等于s的最小塊，并分配之7.2.3伙伴系統(tǒng)7.2.3伙伴系統(tǒng)7.2.4內(nèi)存不足的存儲(chǔ)管理技術(shù)移動(dòng)技術(shù)對(duì)換技術(shù)覆蓋技術(shù)移動(dòng)技術(shù)

操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)作業(yè)4對(duì)換技術(shù)

如果當(dāng)前一個(gè)或多個(gè)駐留進(jìn)程都處于阻塞態(tài)，此時(shí)，通過選擇其中的一個(gè)，把其暫時(shí)移出到磁盤，騰出空間給其他進(jìn)程使用，同時(shí)把磁盤中的某個(gè)進(jìn)程再換進(jìn)主存，讓其投入運(yùn)行，該技術(shù)稱為對(duì)換當(dāng)一個(gè)進(jìn)程執(zhí)行某系統(tǒng)調(diào)用時(shí)變成阻塞狀態(tài)，這時(shí)存儲(chǔ)管理程序會(huì)收到進(jìn)程管理的通知，以決定是否將該進(jìn)程的主存映射對(duì)換到磁盤反之，當(dāng)進(jìn)程管理程序把已對(duì)換出去的進(jìn)程改變?yōu)榫途w狀態(tài)時(shí)，會(huì)通知存儲(chǔ)管理程序，如果主存可用或一旦可用，立即把該進(jìn)程對(duì)換回主存使用硬件地址重定位寄存器，對(duì)換進(jìn)來的進(jìn)程映射被拷貝到新分配的主存區(qū)域并重置重定位寄存器的值對(duì)換技術(shù)覆蓋技術(shù)如果程序長度超出物理主存總和，或超出固定分區(qū)的大小時(shí)，出現(xiàn)主存永久性短缺，大程序無法運(yùn)行，則需要采用覆蓋(overlaying)技術(shù)覆蓋指程序執(zhí)行過程中程序的不同模塊在主存中相互替代，以達(dá)到小主存執(zhí)行大程序的目的實(shí)現(xiàn)技術(shù)：把用戶空間分成固定區(qū)和一個(gè)或多個(gè)覆蓋區(qū)，把控制或不可覆蓋部分放在固定區(qū)，其余按調(diào)用結(jié)構(gòu)及先后關(guān)系分段并存放在磁盤上，運(yùn)行時(shí)被依次調(diào)入覆蓋區(qū)系統(tǒng)必須提供覆蓋控制程序及相應(yīng)系統(tǒng)調(diào)用程序員必須指明同時(shí)駐留在主存的是哪些程序段，哪些是被覆蓋的程序段，這種聲明可從程序調(diào)用結(jié)構(gòu)中獲得

7.3分段管理程序的分段結(jié)構(gòu)分段存儲(chǔ)管理引入的主要原因模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)分頁存儲(chǔ)管理一維地址結(jié)構(gòu)分段存儲(chǔ)管理二維地址結(jié)構(gòu)模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)

子程序段X數(shù)組段A┇call[X]∣<E>(調(diào)用X段的入口E)┇call[Y]∣<F>(調(diào)用Y段的入口F)┇load1,[A]∣<G>(調(diào)用數(shù)組段A[G])┇主程序段E：┅┅┅┅┅┅F：┅┅┅┅┅┅子程序段YG：┅┅┅┅┅┅工作區(qū)段分段程序和相關(guān)的數(shù)據(jù)被劃分成一組段(segment)分段有一個(gè)最大段長度，但并不要求所有程序的所有段的長度相等分段的邏輯地址由兩部分組成：段號(hào)和偏移量由于使用大小不等的段，因此分段類似于動(dòng)態(tài)分區(qū)分段的特點(diǎn)程序員或編譯器把程序和數(shù)據(jù)指定到不同的段，為了實(shí)現(xiàn)模塊化程序設(shè)計(jì)的目的，程序或數(shù)據(jù)可能進(jìn)一步分成多個(gè)段程序的用戶視圖分段(例)分段的重定位SegTableLengthprocess…ASegTable…xxxxxxLength…3ProcesstablelencompsegoffsetSegmenttableSegmentRegAbsoluteaddressRelativeaddresssinterruptstart+分段的實(shí)現(xiàn)邏輯地址由兩部分組成：段號(hào)和偏移量與動(dòng)態(tài)分區(qū)不同，通過段表實(shí)現(xiàn)不連續(xù)存儲(chǔ)的重定位段表：段的長度、段的起始地址、其他控制位與標(biāo)志位分段采用分段法，某個(gè)分段的邏輯地址的段號(hào)為2,段內(nèi)偏移量為100,計(jì)算它的物理地址段表長度段表地址控制寄存器2 1008k 100主存8292offsetsegnumoffset基址1k8005002006k4k8k92008K+100=8292段表長度段表地址段的共享多對(duì)基址/限長寄存器段的共享，是通過不同作業(yè)段表中的項(xiàng)指向同一個(gè)段基址來實(shí)現(xiàn)幾道作業(yè)共享的例行程序就可放在一個(gè)段中，只要讓各道作業(yè)的共享部分有相同的基址/限長值對(duì)共享段的信息必須進(jìn)行保護(hù)分段和分頁的比較(1)

分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶可見，段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何主存地址開始。分段方式中，源程序(段號(hào)，段內(nèi)位移)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。分段和分頁的比較(2)

分頁是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無關(guān)，用戶不可見，頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始分頁方式中，源程序(頁號(hào)，頁內(nèi)位移)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)7.4分頁管理7.4分頁主存被劃分成大小固定相等的塊，且塊相對(duì)比較小，每個(gè)進(jìn)程也被分成同樣大小的小塊，進(jìn)程中稱為頁(page)的塊可以指定到內(nèi)存中稱為頁框(frame)或者頁框的可用塊僅有一個(gè)簡單的基址寄存器是不夠的，操作系統(tǒng)需要為每個(gè)進(jìn)程維護(hù)一個(gè)頁表(pagetable)頁表給出了該進(jìn)程的每一頁對(duì)應(yīng)的頁框的位置每個(gè)邏輯地址包括一個(gè)頁號(hào)和在頁中的偏移量指定進(jìn)程頁到空閑頁框指定進(jìn)程頁到空閑頁框頁表分頁的重定位PageTabLengthProcess…APageTab…xxxxxxLength…3ProcesstableFrameNumCompPageNumoffsetPagetablePagetableregRelativeaddressinterruptFrameNumoffsetAbsoluteaddress分頁的內(nèi)存分配分頁:邏輯地址物理地址邏輯地址物理地址PageNum offsetFrameNum offset分頁:邏輯地址物理地址分頁:邏輯地址物理地址分頁地址轉(zhuǎn)換(例)頁面與頁框的大小為1024字節(jié),指令MOV2100,3100求MOV指令中兩個(gè)操作數(shù)的物理地址2100＝1024×2＋523468頁表地址控制寄存器2 526 52主存6196offsetPagenumoffsetframenum頁面與頁框的大小為1024字節(jié),指令MOV2100,3100求MOV指令中兩個(gè)操作數(shù)的物理地址3100?3468頁表地址控制寄存器

主存8220offsetPagenumoffsetframenum282838分頁地址轉(zhuǎn)換(例)多級(jí)頁表

多級(jí)頁表的概念現(xiàn)代計(jì)算機(jī)普遍支持232～264容量的邏輯地址空間，采用分頁存儲(chǔ)管理時(shí)，頁表相當(dāng)大，以Windows為例，其運(yùn)行的Intelx86平臺(tái)具有32位地址，規(guī)定頁面4KB(212)時(shí)，那么，4GB(232)的邏輯地址空間由1兆(220)個(gè)頁組成，若每個(gè)頁表項(xiàng)占用4個(gè)字節(jié)，則需要占用4MB(222)連續(xù)主存空間存放頁表。系統(tǒng)中有許多進(jìn)程，因此頁表存儲(chǔ)開銷很大。多級(jí)頁表的具體做法邏輯地址結(jié)構(gòu)邏輯地址到物理地址轉(zhuǎn)換過程多級(jí)頁表的概念系統(tǒng)為每個(gè)進(jìn)程建一張頁目錄表,它的每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)頁表頁,而頁表頁的每個(gè)表項(xiàng)給出了頁面和頁框的對(duì)應(yīng)關(guān)系,頁目錄表是一級(jí)頁表,頁表頁是二級(jí)頁表。邏輯地址結(jié)構(gòu)有三部分組成：頁目錄、頁表頁和位移兩級(jí)頁表(32位地址)頁面尺寸4k(212),頁表項(xiàng)4bytes,多級(jí)頁表地址轉(zhuǎn)換過程

BoffsetdirpageoffsetBF進(jìn)程一級(jí)頁表進(jìn)程二級(jí)頁表物理地址邏輯地址頁目錄表控制寄存器Two-LevelSchemefor32-bitAddress二級(jí)頁表0x00x10x20x00x10x2SUNSPARC計(jì)算機(jī)三級(jí)

分頁結(jié)構(gòu)

上下文號(hào)索引1(8)索引2(6)索引3(6)偏移(12)上下文表第一級(jí)第二級(jí)第三級(jí)4K頁面04095頁表問題:增加了尋址時(shí)間，在計(jì)算機(jī)系統(tǒng)中時(shí)間與空間總是存在一些矛盾，因此經(jīng)常會(huì)采取折衷的方案，以時(shí)間換空間，或者以空間換取時(shí)間。多級(jí)頁表結(jié)構(gòu)的本質(zhì)多級(jí)不連續(xù)導(dǎo)致多級(jí)索引。以二級(jí)頁表為例，用戶程序的頁面不連續(xù)存放，要有頁面地址索引，該索引是進(jìn)程頁表；進(jìn)程頁表又是不連續(xù)存放的多個(gè)頁表頁，故頁表頁也要頁表頁地址索引，該索引就是頁目錄。頁目錄項(xiàng)是頁表頁的索引，而頁表頁項(xiàng)是進(jìn)程程序的頁面索引。反置頁表頁表設(shè)計(jì)的一個(gè)重要缺陷是頁表的大小與虛擬地址空間的大小成正比在反向頁表方法中，虛擬地址的頁號(hào)部分使用一個(gè)簡單散列函數(shù)映射到哈希表中。哈希表包含一個(gè)指向反向表的指針，而反向表中含有頁表項(xiàng)。通過這個(gè)結(jié)構(gòu)，哈希表和反向表中只有一項(xiàng)對(duì)應(yīng)于一個(gè)實(shí)存頁(面向?qū)嵈?，而不是虛擬頁(面向虛存)。因此，不論由多少進(jìn)程、支持多少虛擬頁，頁表都只需要實(shí)存中的一個(gè)固定部分。PowerPC,UltraSPARC,andIA-64反置頁表頁號(hào)：虛擬地址頁號(hào)部分。進(jìn)程標(biāo)志符：使用該頁的進(jìn)程。頁號(hào)和進(jìn)程標(biāo)志符結(jié)合起來標(biāo)志一個(gè)特定的進(jìn)程的虛擬地址空間的一頁?？刂莆唬涸撚虬恍?biāo)記，比如有效、訪問和修改，以及保護(hù)和鎖定的信息。鏈指針：如果某個(gè)項(xiàng)沒有鏈項(xiàng)，則該域?yàn)榭?允許用一個(gè)單獨(dú)的位來表示)。

反置頁表的結(jié)構(gòu)反置頁表

頁框號(hào)位移進(jìn)程標(biāo)識(shí)頁號(hào)位移

進(jìn)程標(biāo)識(shí)頁號(hào)特征位鏈指針序號(hào)反置頁表物理地址邏輯地址··哈希函數(shù)哈希表反置頁表及其地址轉(zhuǎn)換反置頁表

反置頁表地址轉(zhuǎn)換過程如下:

邏輯地址給出進(jìn)程標(biāo)識(shí)和頁號(hào),用它們?nèi)ケ容^IPT,若整個(gè)反置頁表中未能找到匹配的頁表項(xiàng),說明該頁不在主存,產(chǎn)生缺頁中斷,請(qǐng)求操作系統(tǒng)調(diào)入;否則，該表項(xiàng)的序號(hào)便是頁框號(hào),塊號(hào)加上位移,便形成物理地址。線性反置頁表linearinvertedpagetable.n>m反置頁表哈希線性反置頁表頁表的結(jié)構(gòu)稱為“反向”是因?yàn)樗褂脦?hào)而不是虛擬頁號(hào)來索引頁表項(xiàng)使用Hash列表主存分配的位示圖和鏈表方法分頁存儲(chǔ)空間的頁面共享和保護(hù)數(shù)據(jù)共享--允許不同進(jìn)程對(duì)共享的數(shù)據(jù)頁用不同的頁號(hào)，只要讓各自頁表中的有關(guān)表項(xiàng)指向共享的數(shù)據(jù)頁框程序共享--由于指令包含指向其他指令或數(shù)據(jù)的地址，進(jìn)程依賴于這些地址才能執(zhí)行，不同進(jìn)程中正確執(zhí)行共享代碼頁面，必須為它們?cè)谒羞壿嫷刂房臻g中指定同樣頁號(hào)段頁式存儲(chǔ)管理段頁式存儲(chǔ)管理7.5Cache7.5Cache7.5.1TLB與Cache工作原理7.5.2Cache映射7.5.3Cache替換算法7.5.4Cache寫策略TLB

(TranslationLookasideBuffer)每個(gè)虛存地址訪問可能引起兩次物理內(nèi)存訪問：一次取相應(yīng)的頁表項(xiàng)一次取需要的數(shù)據(jù)為克服這個(gè)問題，大多數(shù)虛擬內(nèi)存方案為頁表項(xiàng)使用一個(gè)特殊的高速緩存，通常稱為轉(zhuǎn)移后備緩沖器(TranslationLookasideBuffer,TLB)這個(gè)高速緩存的功能和高速緩沖器相似，包含有最近用過的頁表項(xiàng)給定一個(gè)虛擬地址，處理器首先檢查TLB如果需要的頁表項(xiàng)在其中(TLB命中)，則檢索頁框號(hào)并形成實(shí)地址如果沒有找到需要的頁表項(xiàng)(TLB未命中)，則處理器用頁號(hào)檢索進(jìn)程頁表，并檢查相應(yīng)的頁表項(xiàng)如果“存在位”已置位，則該頁在主存中，處理器從頁表現(xiàn)中檢索頁框號(hào)以形成實(shí)地址，處理器同時(shí)更新TLB，使其包含這個(gè)新的頁表項(xiàng)如果“存在位”沒有置位，則表示需要的頁不在主存中，這時(shí)將產(chǎn)生一次缺頁(pagefault)，這時(shí)離開硬件作用范圍，調(diào)用操作系統(tǒng)，由OS負(fù)責(zé)裝入所需要的頁，并更新頁表TLB

(TranslationLookasideBuffer)分頁和TLBEffectiveAccessTimeAssociativeLookup=timeunitAssumememorycycletimeisftimeunitHitratio–percentageoftimesthatapagenumberisfoundintheassociativeregisters;ratiorelatedtonumberofassociativeregistersHitratio=EffectiveAccessTime(EAT) EAT=(f+)+(2f+)(1–) =2f+–f

采用相聯(lián)存儲(chǔ)器的地址轉(zhuǎn)換

假定訪問主存時(shí)間為100毫微秒，訪問相聯(lián)存儲(chǔ)器時(shí)間為20毫微秒，相聯(lián)存儲(chǔ)器為32個(gè)單元時(shí)快表命中率可達(dá)90%，按邏輯地址存取的平均時(shí)間為：(100＋20)×90%＋(100+100+20)×(1-90%)＝130毫微秒比兩次訪問主存的時(shí)間100毫微秒×2+20＝200毫微秒下降了三成多。TLB和Cache操作頁表項(xiàng)的直接映射和關(guān)聯(lián)映射Cache存儲(chǔ)器原理高速緩沖存儲(chǔ)器/主存儲(chǔ)器結(jié)構(gòu)Cache讀操作數(shù)據(jù)總線Cache替換機(jī)構(gòu)可裝進(jìn)？

命中？主存Cache

地址映射變換機(jī)構(gòu)主存訪問主存替換Cache

Cache存儲(chǔ)體標(biāo)記塊內(nèi)地址直接通路訪問主存裝入CacheNNYY塊號(hào)塊內(nèi)地址CPU主存地址地址總線Cache地址Cache的基本結(jié)構(gòu)Cache替換機(jī)構(gòu)由CPU完成

Cache存儲(chǔ)體主存Cache

地址映射變換機(jī)構(gòu)

三級(jí)CachePentium4架構(gòu)(例)7.5.2Cache映射直接映射全關(guān)聯(lián)映射組關(guān)聯(lián)映射字塊2m-1

字塊2c+1

字塊2c+1-1

字塊2c+1

字塊2c字塊2c－1

字塊1字塊0………主存儲(chǔ)體字塊1

標(biāo)記字塊0

標(biāo)記字塊2c-1標(biāo)記Cache存儲(chǔ)體t位01C－1…字塊字塊地址主存字塊標(biāo)記t

位c

位b

位主存地址比較器（t位）=≠不命中有效位=1？*m位

Cache內(nèi)地址否是命中每個(gè)緩存塊j

可以和若干

個(gè)主存塊

對(duì)應(yīng)每個(gè)主存塊i

只能和一個(gè)緩存塊

對(duì)應(yīng)，不靈活，降低命中率或

J=I

mod2c

字塊2c+1

字塊2c字塊0字塊0直接映射方式直接映射地址變換優(yōu)點(diǎn)：硬件簡單，成本低缺點(diǎn):是每個(gè)主存塊只有一個(gè)固定的行位置可存放,容易產(chǎn)生沖突。因此適合大容量cache采用直接映射方式的優(yōu)缺點(diǎn)全關(guān)聯(lián)映射方式主存

中的任一塊

可以映射到緩存

中的任一塊所需邏輯電路甚多，成本較高字塊2m－1字塊2c－1字塊1

字塊0……字塊2c－1字塊1字塊0…標(biāo)記標(biāo)記標(biāo)記主存字塊標(biāo)記

字塊內(nèi)地址主存地址m=t+c

位b位m

=

t+cCache存儲(chǔ)器主存儲(chǔ)器

字塊0

全相聯(lián)映射方式的映射規(guī)則是主存的每一塊都可以映射到cache中的任何一個(gè)字塊上，允許從已被占滿的cache中替換出任何一個(gè)字塊。主存儲(chǔ)器中的第0塊可以映射到cache中的第0塊、第1塊，┅第2c–1塊；主存儲(chǔ)器中的第1塊可以映射到cache中的第0塊、第1塊，┅第2c–1塊。主存地址：主存字塊標(biāo)記–

塊內(nèi)地址這種方法可使主存的一個(gè)塊直接拷貝到cache中的任意一塊上，非常靈活全關(guān)聯(lián)映射方式全相聯(lián)映射的地址變換方法優(yōu)點(diǎn)：靈活，使得cache得到充分利用缺點(diǎn)：標(biāo)記位數(shù)增加，導(dǎo)致cache標(biāo)記容量大，成本增大。比較器電路難于設(shè)計(jì)和實(shí)現(xiàn),因此只適合于小容量cache采用全關(guān)聯(lián)映射方式的優(yōu)缺點(diǎn)組相聯(lián)映射上述兩種方案的折衷。把Cache分成2C’組，每組有

=2r個(gè)字塊；則主存字塊i映射到cache的j塊上j=(imod2C’)×2r+k0≦k≦2r-1k為位于上列范圍內(nèi)（組內(nèi)）的可選參數(shù)（整數(shù)）按這種映射方式,組間為直接映射,而組內(nèi)的字塊為全相聯(lián)映射方式.組相聯(lián)映射把地址劃分成3段,末b位為塊內(nèi)地址,中間c’位為Cache組地址,高t 位和r位形成標(biāo)記字段字塊2m－1字塊2c-r+1

字塊2c-r+1字塊2c-r字塊2c-r

－

字塊1字塊0………字塊3標(biāo)記字塊1標(biāo)記字塊2c-1標(biāo)記字塊2標(biāo)記字塊0標(biāo)記字塊2c-2標(biāo)記…………字塊內(nèi)地址組地址主存字塊標(biāo)記s=t+r

位q=

c－r

位b

位組012c-r－1主存地址Cache主存儲(chǔ)器m

位共u

組，每組內(nèi)兩塊（r=1)1某一主存塊j

按模u

映射到緩存

的第i

組中的任一塊i=j

mod

u直接映射全相聯(lián)映射組關(guān)聯(lián)映射方式字塊0字塊1字塊0字塊2c-r字塊2c-r+1直接映射、全相聯(lián)映射是組相聯(lián)映射的2個(gè)特例：①當(dāng)S=1，也就是將Cache所有塊分成一組（即不分組）時(shí)，組相聯(lián)映射變成了全相聯(lián)映射；②當(dāng)E=1，也就是Cache所有塊分組時(shí)，每組只有一個(gè)塊，組相聯(lián)映射變成了直接映射。Cache映射功能小結(jié)：某一

主存塊只能固定

映射到某一

緩存塊直接全相聯(lián)組相聯(lián)某一

主存塊能映射到任一

緩存塊某一主存塊能映射到某一緩存組中的任一塊不靈活成本高Cache映射功能7.5.3Cache替換算法程序局部性原理先進(jìn)先出(FIFO)最近最少使用(LRU)隨機(jī)算法程序局部性原理(1)指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲(chǔ)區(qū)域中。又可細(xì)分時(shí)間局部性和空間局部性早在1968年P(guān).Denning研究程序執(zhí)行時(shí)的局部性原理，對(duì)此進(jìn)行研究的還有Knuth(分析一組學(xué)生的Fortran程序)、Tanenbaum(分析操作系統(tǒng)的過程)、Huck(分析通用科學(xué)計(jì)算程序)，發(fā)現(xiàn)程序和數(shù)據(jù)的訪問都有聚集成群的傾向某存儲(chǔ)單元被使用，其相鄰存儲(chǔ)單元很快也被使用(稱空間局部性spatiallocality)，或者最近訪問過的程序代碼和數(shù)據(jù)，很快又被訪問(稱時(shí)間局部性temporallocality)分頁下的運(yùn)行情況程序局部性原理(2)(1)

程序中只有少量分支和過程調(diào)用，存在很多順序執(zhí)行的指令(2)程序含有若干循環(huán)結(jié)構(gòu)，由少量代碼組成，而被多次執(zhí)行(3)過程調(diào)用的深度限制在小范圍內(nèi)，因而，指令引用通常被局限在少量過程中(4)涉及數(shù)組、記錄之類的數(shù)據(jù)結(jié)構(gòu)，對(duì)它們的連續(xù)引用是對(duì)位置相鄰的數(shù)據(jù)項(xiàng)的操作(5)程序中有些部分彼此互斥，不是每次運(yùn)行時(shí)都用到FIFO替換算法FIFO策略把分配給進(jìn)程的頁框看做是一個(gè)循環(huán)緩沖區(qū)，按循環(huán)方式移動(dòng)頁實(shí)現(xiàn)時(shí)，需要一個(gè)指針，這個(gè)指針在該進(jìn)程的頁框中循環(huán)這是一種實(shí)現(xiàn)起來最簡單的替換策略這種替換算法所隱含的邏輯是替換駐留在主存中時(shí)間最長的頁；一個(gè)在很久以前取入主存的頁，到現(xiàn)在可能已經(jīng)不會(huì)在用到了LRU替換算法LRU策略替換主存中上次使用距離當(dāng)前最遠(yuǎn)的頁根據(jù)局部性原理，這也是最近最不可能訪問到的頁該方法實(shí)現(xiàn)比較困難，一種實(shí)現(xiàn)方法是給每一頁添加一個(gè)最后一次訪問的時(shí)間標(biāo)簽，并且必須在每次訪問存儲(chǔ)器時(shí)，不論訪問的是指令還是數(shù)據(jù)，都更新這個(gè)標(biāo)簽即使有支持這種方案的硬件，開銷仍然非常大另一種可選擇的方法是維護(hù)一個(gè)關(guān)于訪問的棧，當(dāng)開銷同樣很大替換算法(例)回顧過去7.5.4Cache寫策略寫回法(write--back)寫直達(dá)(write--trough)寫一次(write--once)1.寫回法(write--back)當(dāng)CPU對(duì)cache寫命中時(shí)，只修改cache的內(nèi)容不立即寫入主存，只當(dāng)此行被換出時(shí)才寫回主存這種策略使cache在CPU－主存之間，不僅在讀方向而且在寫方向上都起到高速緩存作用對(duì)cache行的多次寫命中都在cache中快速完成修改，只在需被替換時(shí)才寫回速度較慢的主存，減少了訪問主存的次數(shù)，從而提高了效率為支持這種策略，每個(gè)cache行必須配置一個(gè)修改位，以反映此行是否被CPU修改過。當(dāng)某行被換出時(shí)，根據(jù)此行修改位是1還是0，決定是將該行內(nèi)容寫回主存還是簡單地丟棄

1.寫回法(write--back)對(duì)于cache寫未命中，寫回法的處理是為