【正文】 去了。 (散列 ) 頁號 偏移量 虛地址 散列表 頁號 表項 鏈 反向頁表 幀號 幀號 偏移量 實地址 頁面替換算法 ? 頁的置換算法：當發(fā)生缺頁，而主存中已無空閑頁架時，需選一頁淘汰。節(jié)省了大量的物理空間。 并且操作系統(tǒng)可以根據(jù)進程的性質(zhì)，自動預裝進程可能需要的頁面這樣，就是進程的缺頁率大大減少。 工作時，當有虛地址需要轉(zhuǎn)換時，先到 TLB中去作判斷，如果不在 TLB中，就去頁表中查詢，并在獲得后更新 TLB中的頁號數(shù)據(jù)，淘汰一個條目，將其信息寫回內(nèi)存中的頁表項，把新的條目加入；如果虛頁號在 TLB中，則判斷保護情況，合法就直接取出使用，不用查詢頁表，不合法時，就出現(xiàn)保護故障。 當一個虛地址定位的時候，具體過程如下： 10位 10位 12位 虛地址 根頁表指針 幀號 偏移量 頁幀 根頁表 1024個 PTE 頁表 1024個 PTE 物理內(nèi)存 當用戶的頁不在主存中，就會發(fā)生缺頁故障，由操作系統(tǒng)完成換頁的工作。 ****多級頁表 為了不將龐大的頁表全放內(nèi)存，引入了多級頁表技術： 對于此例： 32位虛地址分為了 10位的 PT1域， 10位的 PT2域，每個頁的大小是 12位。但缺點是執(zhí)行每條指令時都要一次或多次訪問內(nèi)存。 二、另一種極端，全放入內(nèi)存 這時的硬件開銷就很小，只需要指向頁表起始地址的寄存器即可。但這樣當頁表大的時候，就要多的硬件寄存器來存放，代價昂貴。而64位系統(tǒng)的更為龐大 ……. 即問題主要是頁表的龐大導致了索引不再高效； 另外，從虛地址到物理地址的映射的頻繁執(zhí)行，現(xiàn)有的龐大頁表無法完成快速的查找定位 ….... 即問題是地址映射相應變慢。 MMU的內(nèi)部結(jié)構(gòu)及工作方法 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 110 在 /不在內(nèi)存 頁表 虛地址 8196 物理地址 24580 000 0 15 000 0 14 000 0 13 000 0 12 111 1 11 000 0 10 101 1 9 000 0 8 000 0 7 000 0 6 011 1 5 100 1 4 000 1 3 110 1 2 001 1 1 010 1 0 2 =16 4 2 =4096 12 頁表 （ page table） 頁表是用來索引頁面的，通過判斷頁表的存在位，判斷這個虛頁在物理內(nèi)存中是否有對應的頁框，當有的時候，就直接通過頁表函數(shù)獲得實際的物理地址來定位到實際的物理內(nèi)存，如果沒有，就通知操作系統(tǒng)，引發(fā)陷入，去找空頁框來裝入這個虛頁。這是的故障就叫做缺頁故障。虛頁是否被對應了都專門有一位來存儲這個信息。它是一組或一個芯片，完成地址映射的功能。 實現(xiàn)思想： 當進程運行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存，當要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存工作。 虛擬存儲器支持多道程序設計技術。 例子：目前這一技術用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上， MSDOS的啟動過程中，多次使用覆蓋技術；啟動之后，用戶程序區(qū) TPA的高端部分與 蓋結(jié)構(gòu)。 一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后又由操作系統(tǒng)完成自動覆蓋。 把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域。 交換技術與覆蓋技術共同點： 進程的程序和數(shù)據(jù)主要放在外存，當前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進行信息交換。 虛擬存儲器 交換技術與覆蓋技術是 在多道環(huán)境下擴充內(nèi)存的方法，用以解決在較小的存儲空間中運行較大程序時遇到的矛盾。 ** 快速適配法，按照常見進程需要的空間大小設置單獨的鏈表，這種算法就根據(jù)進程所需空間的大小快速在這些特殊的空洞鏈表中查找空內(nèi)存。 **一些改進思路 ** 進程和空洞存放在兩個鏈表中，針對最佳適配算法的缺陷，將空洞的組織不按地址，而是按照大小來組織，這樣就減小了搜索時的開銷。 **放棄最佳適配算法 — 采用最差適配算法 采用最差，即每次找最大的內(nèi)存空間分給進程，這樣就不會產(chǎn)生大量的極小的內(nèi)存空洞，即被分開后剩余的那部分仍然足夠大，可以繼續(xù)被使用。 **首次適配的變形 — 下次適配 工作方式與首次適配相同，區(qū)別在于每次搜索完畢后記錄當前的位置，下次搜索時從此處開始搜索。 A B X A X A B B X X A B 變?yōu)? 變?yōu)? 變?yōu)? 變?yōu)? （ a） （ b） （ c） （ d） 對于某進程 X結(jié)束的時候同鄰居合并的四種方式 對于這種內(nèi)存的組織和管理方法，我們需要討論如何用合理的方法來為新創(chuàng)建的進程和新?lián)Q進來的進程分配大小： **最簡單的分配算法 — 首次適配算法 存儲管理器沿內(nèi)存段鏈表從頭開始尋找足夠的空間來裝載進程，除非找到的這個區(qū)域的大小剛好和進程相同，否則就要把這個空間拆為兩部分，一部分來裝進程，另一部分依然為空。這是一般，鏈表的組織都按照地址來排列，這樣的進程切換會很直觀，更有效的方法是采用雙向鏈表來記錄。這里的內(nèi)存段可以使被某個進程所占用，也可以是個空洞，即尚未分配的區(qū)域。故實際不很常用。（ B） OS A B A 為增長內(nèi)存準備的內(nèi)存 實際使用的內(nèi)存 為增長內(nèi)存準備的內(nèi)存 實際使用的內(nèi)存 OS APROG ADATA ASTACK BDATA BSTACK BPROG B 為增長內(nèi)存準備的內(nèi)存 為增長內(nèi)存準備的內(nèi)存 .1 使用位圖的內(nèi)存管理 由于操作系統(tǒng)需要對內(nèi)存進行分配管理和回收，所以，它必須很好地對內(nèi)存進行跟蹤，常用的是位圖法和自由鏈表： A B C D E (a) 對于位圖方法，位圖的大小與內(nèi)存的大小和分配的單位的大小相關，內(nèi)存不變時，被分配的單個單元越小，則位圖就越大。 ****新問題的解決帶來的矛盾： 多數(shù)的進程都需要動態(tài)的空間，且申請新的內(nèi)存空間，頻繁的交換導致大量的進程等待和時間開銷。即空閑區(qū)域的合并 內(nèi)存緊縮。 實際上，內(nèi)存空間在不斷劃分的時候，本身的分布也在變化的越來越復雜，越來越不便于管理。 OS OS OS OS OS OS A A A B B B B C C C C D D a b c d e f OS C D E 進程依次進入，并獲得到自己所需要的內(nèi)存空間，當某個進程執(zhí)行完畢后便離開，它原來的占用的內(nèi)存資源便得到釋放，當新的進程到來的時候，又可以從這個被釋放的空間中劃分新的空間，因此主存的利用變得很高效。 但在分時系統(tǒng)中，或者個人的 PC中，這種方案就不太實際，會常常由于主存不夠，需要把進程保存到磁盤，同樣的，也需要常常動態(tài)地把進程從磁盤調(diào)入內(nèi)存。 交換 固定分區(qū)的方案在批處理系統(tǒng)中是種簡單高效的方案，每一個作業(yè)都在隊列中一直到被分配到某個分區(qū)，然后被執(zhí)行完畢。 對于右圖，所有的作業(yè)都被放入一個隊列，每次當有分區(qū)被釋放的時候，就從等待隊列中尋找，最適合這個分區(qū)大小的進程，這樣做是為了避免把大的分區(qū)分給那小的作業(yè)，免得資源被浪費，但這樣卻常常把小的作業(yè)推到了后面；但對于操作系統(tǒng)，我們做普通的要求就是簡單的操作能被最快的反饋給我們，即小的作業(yè)能夠被最快的處理，因此，為了總能夠滿足用戶的這個要求，一般要專門保證總有一個小的分區(qū)，專門來處理那些小的事件、作業(yè)，免得被大的作業(yè)搶去分區(qū)。忙得忙，閑的閑。而同時，程序也可按照單個輸入隊列的方式進行輸入，也可以按照多個輸入隊列的方式進行輸入。 固定分區(qū)的多道程序