天天看點

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

1. 存儲器層次結構

最頂層:CPU内部的一些寄存器

第二層:高速緩存(cache)

第三層:主存儲器(記憶體)

第四層:磁盤(非易失的 nonvolatile)

作業系統作為一個系統軟體,其任務就是協調好這些不同類型的存儲器的使用

2. 存儲管理器(memory manager)

一、在作業系統中,負責管理這個存儲器層次結構的那一部分程式,稱為存儲器管理器。在大多數作業系統中,存儲管理器都位于核心之中(MINIX3除外)

二、它的主要任務:

  • 記錄存儲器的使用情況;
  • 當程序需要存儲空間時,就配置設定給它;當它運作結束後,再把存儲空間回收回來;
  • 把記憶體中暫時不能運作的程序送到磁盤上,然後再把磁盤上的另一個程序裝入内

3.記憶體管理

3.1分類

①需要在記憶體和磁盤之間,把程序換進換出;

②不需要這種換進換出

(注:程序的換進換出和頁面置換都是由于記憶體不足造成的。)

3.2常見的記憶體管理技術

3.2.1單一連續配置設定(單道程式存儲管理)

一、單道程式存儲管理的基本思路

單道程式存儲管理是最簡單的一種存儲管理方法。它的基本思路是,把整個記憶體劃分為兩個區域:系統區和使用者區。每次把一個應用程式裝入到使用者區去運作,由它和作業系統來共享整個記憶體。而且從裝入開始一直到它運作結束,在這段時期内,該程式始終獨占着整個使用者區。

二、實作方式(3種)

①作業系統被放在了随機存取存儲器(Random Access Memory, RAM)的最低端——早期的大型機和小型機

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

②作業系統被放在了記憶體位址的最高端,而且是放在了隻讀存儲器(Read-Only Memory,ROM)裡面——掌上型電腦和嵌入式系統

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

③作業系統被分為兩部分,一部分是裝置驅動程式,被存放在記憶體高端的ROM中;另一部分則放在了記憶體的最低端——早期的個人計算機系統

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

(存放在記憶體高端的ROM中的系統内容,稱為基本輸入輸出系統)

注意:在單道程式存儲管理方式下,每次隻能運作一個程式!

3.2.2分區管理

3.2.2.1 固定式分區管理

固定分區配置設定是将記憶體空間劃分為若幹個固定大小的區域,每個分區隻裝入一道作業。當有空閑分區時,便可以再從外存的後備作業隊列中,選擇适當大小的作業裝入該分區,如此循環。

固定分區方式存在兩個問題:

1)程式可能太大而放不進任何一個分區中,這時使用者不得不使用覆寫技術來使用記憶體空間;

2)主存使用率低,當程式小于固定分區大小時,也占用了一個完整的記憶體分區空間,這樣分區内部有空間浪費,這種  現象稱為内部碎片。

I. 固定分區和多個輸入隊列

可能出現的情形:小分區的輸入隊列是滿的,而大分區的輸入隊列是空的,造成記憶體空間的浪費

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理
《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

II. 固定分區和單個輸入隊列

當某個分區變得空閑時,可以采用兩種辦法來選擇合适的程序:

①選擇離隊首最近的、能夠裝入該分區的程序——如果選中的程序是一個比較小的程序,那麼就會浪費大量的記憶體空間;

②先搜尋整個隊列,從中選擇能夠裝入該分區的最大程序,進而盡可能地減少所浪費的空間——不利于比較小的程序(通常是一些互動式程序)

 解決辦法:1)始終保留至少一個小分區

                  2)制定一條規則,規定一個程序被忽略次數不能超過k次

3.2.2.2 可變式分區管理

可變式分區在程序裝入記憶體時,根據程序的大小動态地建立分區,并使分區的大小正好适合程序的需要。動态分區在開始配置設定時是很好的,但是之後會導緻記憶體中出現許多小的記憶體塊。随着時間的推移,記憶體中會産生越來越多的碎片,且随着程序的換入/換出,很可能會出現更多更小的記憶體塊,記憶體的使用率随之下降。這些小的記憶體塊稱為外部碎片,指在所有分區外的存儲空間會變成越來越多的碎片,這與固定分區中的内部碎片正好相對。

3.2.2.3 動态分區的配置設定政策

①首次适配算法(最簡單)(first fit):空閑分區以位址遞增的次序連結。配置設定記憶體時順序查找,找到大小能滿足要求的第一個空閑分區。除非空洞大小與要配置設定的空間大小剛好一樣,否則這個空洞将會分為兩部分:一部分供程序使用+另一部分是未用的記憶體

②下次适配算法(next fit):工作方式與首次适配相同,差別:配置設定記憶體時從上次查找結束的位置開始繼續查找。,而不是每次都從頭開始。(下次适配的性能略低于首次适配)

③最佳适配算法(best fit):把空閑分區按照大小排成一個鍊,從鍊首開始查詢,找到第一個适合的空閑分區(速度比首次适配算法慢,甚至比它造成更多的記憶體浪費)

④最差适配算法(worst fit):空閑分區以容量遞減的次序連結,找到第一個能滿足要求的空閑分區,也就是挑選出最大的分區,使分裂出來的空洞比較大進而繼續使用(但不是一個好主意)

⑤快速适配算法(fast fit): 為一些經常被用到長度的空洞設立單獨的連結清單。

3.3碎片概念及解決辦法

①碎片概念:

在記憶體管理中,

内部碎片是已經被配置設定出去的的記憶體空間大于請求所需的記憶體空間。

外部碎片是指還沒有配置設定出去,但是由于大小太小而無法配置設定給申請空間的新程序的記憶體空間空閑塊。

(固定分區、頁式虛拟存儲系統存在内部碎片,可變式分區、段式虛拟存儲器系統存在外部碎片;)

②解決碎片的辦法:

采取記憶體緊縮(memory compaction)技術,即對碎片進行拼接,把所有的程序都盡可能地往記憶體位址的低端移動,相應地,那些空閑的小分區就會往位址的高端移動,進而在位址高端形成一個較大的空閑分區。但是需要消耗系統資源,我們不經常采用這種操作。

4.重定位和存儲保護

多道程式技術引發了兩個重要問題:位址重定位和存儲保護。不同的作業将在不同的位址區間運作。當一個程式被連結時,連結器必須知道程式将在記憶體的什麼位址開始運作

一、位址重定位

重定位就是把程式的邏輯位址空間變換成記憶體中的實際實體位址空間的過程,也就是說在裝入時對目标程式中指令和資料的修改過程。它是實作多道程式在記憶體中同時運作的基礎。

二、存儲保護

             存儲保護包括兩方面的内容,防止位址越界和防止非法操作。

             (1) 防止位址越界

                     每個程序都具有其相對獨立的程序空間,如果程序在運作時所産生的位址超出其位址空間,則發生位址越界,侵犯其他

                     程序的空間/侵犯作業系統空間,導緻系統混亂。

             (2) 防止非法操作

                     對于允許多個程序共享的公共區域,每個程序都有自己的通路權限。例如,有些程序可以執行寫操作,而其他程序隻能

                     執行讀操作等。是以,必須對公共區域的通路加以限制和檢查。

             存儲保護一般以硬體保護機制為主,軟體為輔;因為完全用軟體實作系統開銷太大,速度成倍降低。當發生越界或非法操作

             時,硬體産生中斷,進入作業系統處理。

三、解決方案:

①重定位問題:

當一個程式被裝入時,直接對指令代碼進行修改,一次性地實作從檔案内的相對位址到記憶體中的絕對位址的轉換

條件:連結器必須在可執行檔案中包含一個連結清單/位圖,列出各個需要重定位的位址單元的位置

②重定位+存儲保護問題:

  1. 使用記憶體單元的保護碼與CPU的密鑰(隻有作業系統才能修改保護碼和密鑰)
  2. 在機器中增加兩個特殊的硬體寄存器,即基址(base)寄存器和邊界(limit)寄存器

  (——缺點:在每一次記憶體通路中,都必須增加一次加法和比較操作)

     條件:必須用硬體把基位址寄存器和邊界寄存器保護起來,不能讓使用者随便去修改它們

5.覆寫與交換

一、基本概念:

覆寫是指同一主存區可以被不同的程式段重複使用。作業在一次運作時,把那些不會同時執行的程式段共用一個主存區。

互相覆寫的程式段叫做覆寫,可共享的主存區叫做覆寫區。覆寫技術的基礎是提供正确的覆寫結構。

交換:交換就是系統根據需要把主存中暫時不允許的某個或某些作業部分或全部移到輔存,而把輔存中的某個或某些作業移到相應的主存區,并使其投入運作。

根據硬體條件的不同,可以采用兩種不同的存儲管理方法:交換(swapping)技術(最簡單的政策)、虛拟存儲器(virtual memory)

6.交換技術、虛拟存儲器情形

  交換技術:把各個程序完整地調入記憶體,運作一段時間,再放回到磁盤上

  虛拟存儲器:程序隻有一部分内容存放在記憶體中,它也能運作

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

随着程序的換入還出,在記憶體中會造成一些不連續的黑洞(即比較小的空閑分區),這時可以采用記憶體緊縮(memory compaction)技術——把所有的程序盡可能都往記憶體位址的低端移動,相應的,那些空閑的小分區就會往位址的高端移動,進而在位址高端形成一個較大的空閑分區——一般不采用,需要耗費大量的CPU實踐

7.空間配置設定

當一個程序被建立/換入時,應該給它配置設定多大的記憶體空間?

 ①程序大小固定:程序需要多少,作業系統就配置設定多少

 ②程序大小不固定:作業系統為程序配置設定額外的記憶體空間以便于增長

8.對換(Swapping)

概念

對換,又稱交換,swapping,在可變式分區存儲管理方案當中,假設某時刻t程序P要進入記憶體,如果此時記憶體不夠用,可以有兩處理辦法:一種是讓程序P等待,直到有一個其他程序運作完釋放記憶體為止;另一種辦法是選擇一個程序淘汰(并把被淘汰程序的映像寫到磁盤),讓P運作。這種方法稱作是具有對換的可變式分區。

對換的類型

整體對換:程序對換,解決記憶體緊張問題。(中級排程)

部分對換:頁面對換/分段對換,提供虛存支援。

對換空間的管理

具有對換功能的OS中,通常把外存分為檔案區和對換區。前者用于存放檔案,後者存放從記憶體換出的程序。對換區比檔案區側重于對換速度。是以對換區一般采用連續配置設定。

程序的換出與換入

選擇換出程序:優先級,程序狀态。

選擇換入程序:優先級,程序狀态,換出時間等。

對換與虛拟存儲器之間的差别

交換技術:把各個程序完整地調入記憶體,運作一段時間,再放回到磁盤上

虛拟存儲器:程序隻有一部分内容存放在記憶體中,它也能運作

交換是把整個程序換入換出主存,而虛拟存儲器的基本思想是程式的大小可以超過實體記憶體的大小,作業系統把程式的一部分調入主存來運作,而把其他部分保留在磁盤上。交換并未實作虛拟存儲器!!

9. 基于位圖、空閑連結清單的存儲管理

 主要有兩種方法來記錄記憶體的使用狀況:位圖法和空閑連結清單法

  一、基于位圖的存儲管理

在位圖法中,記憶體被劃分為很多個配置設定單元,每個單元可能特别小,隻有幾個字;也可能特别大,包含幾千個位元組。每個配置設定單元都對應于位圖中的某個資料位,0表示該單元是空閑的,1表示該單元已經被占用

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

(注:位圖法的大小僅取決于記憶體和配置設定單元的大小,如果配置設定單元比較大,那麼位圖比較小)

二、基于連結清單的存儲管理

建立一個連結清單來描述已配置設定和空閑的記憶體分區。對于每一個分區,它可能存放了某個程序,也可能是兩個程序之間的空閑區。連結清單中的每一個結點,分别描述了一個記憶體分區(起始位址、長度、指向下一個結點的指針以及分區的目前狀态)H:空閑區(Hole) P:已經被某個程序(Process)占用了

                                                              程序x終止時與左右鄰居合并的4種方式

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

10. 虛拟存儲器(Virtual Memory)

請求分頁管理基本思想

請求分頁管理也稱為虛拟頁式存儲管理,是建立在基本分頁基礎上,為了能支援虛拟存儲器功能而增加了請求調頁功能和頁面置換功能,其基本思想是:在程序開始運作之前,不是裝入全部頁面,而是裝入部分頁面,之後根據程序運作的需要,動态裝入其他頁面,當記憶體空間已滿,又需要裝入新的頁面時,根據某種算法淘汰某個頁面,以便裝進新的頁面。

虛拟頁式存儲管理/請求分頁管理

大部分虛拟存儲器系統都使用了一種稱為分頁(paging)的技術

虛位址與實體記憶體位址之間的關系

由程式産生的位址被稱為虛位址,它們構成了一個虛位址空間(virtual address space)

使用虛拟存儲器的情況下,虛位址不是直接送到記憶體總線上,而是送到記憶體管理單元(MMU),它由一個/一組晶片組成,其功能是把虛位址映射為實體位址。

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

虛位址空間被劃分為頁(pages)的機關,在實體存儲器中對應的機關稱為頁框(page frames),頁和頁框的大小總是相等的(注:記憶體和磁盤之間的傳輸總是以頁為機關的)

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

虛實位址變換過程

虛實位址變換過程:

在進行位址映射時,使用虛拟頁面号作為索引去通路頁表(page table),進而得到相應的實體頁面号。如果有效位的值為0,則将引發一個缺頁中斷,陷入到作業系統;如果有效位的值為1,則将頁表中查到的實體頁面号複制到輸出寄存器的高位中,再加上輸入的虛拟位址中的偏移量,構成了實體位址。輸出寄存器的内容随即被作為實體位址送到記憶體總線。

①存儲管理單元(Memory Management Unit,MMU)做什麼:

  1. 負責把虛拟位址映射為實體位址
  2. 控制存儲器空間的通路權限
  3. 設定緩沖

②頁表做什麼:存放虛拟位址對應的實體位址、通路權限、緩沖特性等

③OS做什麼:查詢頁表

1)若給定一個邏輯位址為A,頁面大小為L,則頁号P=INT[A/L],頁内位址W=A MOD L

則實體位址=P*L+W

2)邏輯位址= 頁号+頁内位址

  實體位址= 塊号+頁内位址;

分頁、分段的概念及差别

分頁:将程序的邏輯位址空間分成若幹大小相等的片(頁),然後裝入記憶體

分段:使用者可以把自己的作業按邏輯關系劃分成若幹個段,每個段都是從0開始編制,并有自己的名字和長度

相同點:①二者都屬于存儲器管理方式中的離散配置設定方式;

②都要通過位址映射機構來實作位址變換

不同點:

①離散配置設定方式的基本機關不同,一個是頁一個是段,頁的大小固定且由系統決定,而段的長度卻不固定。

②頁是資訊的實體機關,段是資訊的邏輯機關

③分頁的作業位址空間是一維的,線性的,程式員隻需利用一個記憶符表示一個位址;

分段的作業位址空間是二維的,程式員在表示一個位址的時候既要給出段名,又要給出段内位址。其中,段名可以了解為函數名,段内位址可以了解成變量等的位址

11. 頁表

頁表的作用

作用:将虛拟頁面映射為相應的實體頁面。從數學的角度說,頁表是一個函數,它的輸入是虛拟頁面号,輸出是實體頁面号。通過這個函數可以把虛拟位址中的虛拟頁面号替換成實體頁面号,進而形成實體位址。

頁表的具體實作

  • 兩個重要問題的考慮

          ① 頁表可能會非常大

          ② 位址映射必須十分迅速

  • 解決辦法

          ① 使用一個頁表,由一組快速的硬體寄存器組成,每一個虛拟頁面對應一個表項,并用虛拟頁面号作為索引,在啟動一個程序時,作業系統把位于記憶體中的頁表裝入寄存器中。——貴、降低系統的性能

          ② 把頁表全部放在記憶體中

          ③ 多級頁表(一般的頁表不會超過二級)

           基本思路:程序在運作時,并不會用到所有的虛拟位址,沒有必要把所有的頁表項都儲存在記憶體中

           例如:假設虛拟位址32位,頁面的大小為4KB.

                     通常的頁式存儲管理,把虛拟位址劃分為兩部分:虛拟頁面号20位+頁内偏移量12位

                     二級頁表的結構下:還需把虛拟頁面号再進一步劃分為兩部分:10位字段PT1+10位字段PT2

頁表項的結構

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

① 實體頁面号(最重要的字段):因為位址映射的最終目标是把虛拟頁面号映射為相應的實體頁面号

② 有效位:表示該頁面現在是否存在記憶體中

③ 保護位:表示允許對這個頁面做何種類型的通路

④ 修改位和通路位    用來記錄頁面的使用情況(當作業系統回收一個實體頁面時,先要檢查修改位,如果為1:“髒頁面”,必須把它寫回到磁盤中;如果為0:“幹淨頁面”,直接把它覆寫掉)

⑤ 禁用緩沖位

12.關聯存儲器TLB

TLB作用

 TLB是一個記憶體管理單元,用于改進虛拟位址到實體位址轉換速度的緩存,用來存放那些最常用的頁表項。這種硬體裝置能夠直接把虛拟頁面号映射為相應的實體頁面号,而不需要去通路記憶體中的頁表。TLB通常位于MMU中。

TLB工作原理

當一個虛拟位址到來時,MMU首先會到TLB中去查找,看看這個虛拟頁面号是否出現在TLB中。這個查找的速度很快,因為它是以并行的方式進行的,同時與所有的頁表項進行比較。

①如果能夠找到而且此次通路是合法的,那麼直接從TLB中把相應的實體頁面号取出來;

②如果能夠找到該虛拟頁面号,但違反了通路權限,則引發一個中斷保護;

③如果找不到該虛拟頁面号,那麼就要采用通常的辦法去通路記憶體中的頁表,把相應的實體頁面号取出來,與此同時,硬體還會從TLB中把某一個表項驅逐出來,往TLB中載入剛剛通路的頁表項。

注意:當一個表項被驅逐出TLB時,要把它修改位複制到記憶體的頁表項中,因為它的值可能會發生變化!

TLB命中率的提高

  TLB未命中率往往高于缺頁中斷發生的頻率,為了降低TLB的未命中率:作業系統有時可以預測出哪些頁面即将被通路,并把它們預先裝入TLB,以避免TLB中斷的發送

13.中斷

缺頁中斷概念

在請求分頁系統中,當通路的頁不在記憶體,便産生一缺頁中斷,請求OS将所缺頁調入記憶體空閑塊,若無空閑塊,則需置換某一頁,同時修改相應表表目。

缺頁中斷與一般中斷的差別

①在指令執行期間産生和進行中斷信号

②一條指令在執行期間,可能産生多次缺頁中斷

14. 頁面置換算法

  當一個缺頁中斷發生時,需要從磁盤上調入相應的頁面。如果此時記憶體已經滿了,就需要從記憶體中選擇一個頁面,把它置換出去,進而把它所占用的空間騰出來,裝入新的頁面。如果被選中的頁面曾經被修改過,那麼必須把它寫回到磁盤,已更新磁盤上的副本。如果該頁面違背修改過,則可以直接抛棄,用新的頁面來覆寫它。

*最優頁面置換算法(Optimal Replacement Algorithm,OPT)

 基本思路:當一個缺頁中斷發生時,對于記憶體中的每一個虛拟頁面,計算在它下一次通路之前,還需要等多久時間,用指令數表示,選擇等待時間最長的那個頁面,把它作為被置換的頁面。

缺點:無法實作,作業系統不知道每一個頁面還要等待多長時間

用處:用作其他算法性能評價的依據

最近未使用頁面置換算法(Not Recently Used,NRU)

 基本思路:每個頁面都有兩個狀态标志位:R(通路位)和M(修改位),這兩個标志位存放在頁面的頁表項中。當一個程序被啟動時,作業系統會把它的所有頁面的這兩個位都置0.在程序運作過程中,R位會被定期地清零,這樣就把最近未被通路過的頁面與最近被通路過的頁面差別開來。随機地從編号最小的非空類中挑選一個頁面置換。選擇記憶體中等待時間最長的頁作為置換頁面

當一個缺頁中斷發生時,作業系統回去檢查所有的頁面,根據目前的R位和M位的值,把它們分為4類:

第0類(00):未被通路,未被修改

第1類(01):未被通路,已被修改

第2類(10):已被通路,未被修改

第3類(11):已被通路,已被修改

注意:M位不能清零,是因為将來該頁面被置換出去時,需要根據這個資訊來決定是否需要把這個頁面的内容寫回磁盤

缺點:性能不是很好

優點:易于了解,實作起來效率較高

*先進先出頁面置換算法(First-In,First-Out,FIFO)

  基本思路:作業系統維護一個連結清單,在這個連結清單中,記錄了所有位于記憶體中的虛拟頁面,從連結清單的排列順序來看:鍊首頁面駐留時間最長,鍊尾頁面駐留時間最短。當發生一個缺頁中斷時,就把鍊首的頁面淘汰,并把新的頁面添加到鍊尾。

缺點:被它淘汰出去的可能是經常要通路的頁面,FIFO算法很少被單獨使用

第二次機會頁面置換算法(second chance)

  基本思想:對于最古老的頁面,檢測其R位。如果R位是0,則立刻被淘汰出局;如果R位是1,則說明該頁面曾經被通路過,是以就再給它一次機會:先把R位清0,然後把這個頁面放到連結清單的尾端,并修改它的裝入時間,就好像它剛剛進入系統一樣,然後繼續往下搜尋。

如果所有的頁面都被通路過了,就退化成純粹的FIFO算法

缺點:經常要在連結清單中移動頁面,降低了效率

時鐘頁面置換算法

  基本思想:把各項頁面組織成環形連結清單的形式,類似于時鐘表面。然後把一個指針指向最古老的那個頁面。當一個缺頁中斷發生時,檢查指針所指向的那個頁面,如果它的R位的值=0,立刻被淘汰;如果R=1,則把它清零,并把指針指向下一個頁面,直到發現一個其通路位的值=0的頁面并把它淘汰掉。

功能與第二次機會算法的功能實完全一樣的,隻是具體實作上有所不同

*(面試題程式設計)最近最久未使用頁面算法(Least Recently Used,LRU)

  基本思想:當一個缺頁中斷發生時,從記憶體中選擇最久未被使用的那個頁面,把它淘汰出局。理論依據:程式的局部性原理。在最近的一小段時間内,它們還可能會再一次被頻繁地通路。反過來說,如果在過去一段時間内,某些頁面長時間未被通路,那麼在将來,它們還可能會長時間未被通路。LRU利用過去的、已知的頁面通路情況,來預測将來的情況

  實作:計數器,在每條指令執行完後,計數器會自動+1,在每一次記憶體通路後,C的目前值會被存放在被通路頁面的頁表項中。當發生一個缺頁中斷時,作業系統會去檢查頁表中所有的計數器的值,從中找出一個最小值,該頁面就是最近最久未使用的頁面。

硬體支援:寄存器、棧

15. 頁式存儲管理中的設計問題

工作集模式

  • 請求調頁(demand paging)

請求調頁指的是一種動态記憶體配置設定技術,它把頁面的配置設定推遲到不能再推遲為止,也就是說,一直推遲到程序要通路的頁不在實體記憶體時為止,由此引起一個缺頁錯誤。

特點:頁面不是預先被裝入記憶體,而是根據需要随要随調

  • 絕大多數的程序都會表現出一種通路的局部性(locality of reference),在程序運作的任何一個階段,它隻會去通路一小部分的頁面。
  • 概念

①一個程序目前正在使用的頁面集合稱為它的工作集(working set)

②需要頻繁地在記憶體與外存之間置換頁面,進而使得程序的運作速度變得很慢,我們把這種狀态稱之為抖動(Denning)

③工作集模式:頁式存儲管理系統試圖記錄每個程序的工作集,并確定在程序運作之前,它的工作集已經在記憶體中(預先調頁,prepaing),旨在大大減少缺頁中斷的次數。

16. 段式存儲管理

段的概念

機器上提供多個互相獨立的位址空間,稱為段(segment),在每個段的内部,是一個一維的線性序列,從0開始一直到某個最大值。一般來說,每個段的長度是不相等的,而且在執行過程中,段的長度可以動态變化。

段式存儲的優點

①簡化處理動态增長/縮短的資料結構

②分段有助于在幾個程序之間共享函數和資料,一個典型的例子就是共享庫(shared library)

③調用第n個段中的函數,隻需要使用二維位址(n,0)就可以跳轉到該函數的入口位址

頁式和段式存儲管理的比較

考慮的問題      
頁式存儲管理      
段式存儲管理      
程式員需要知道正在使用這種技術嗎?      
不需要      
需要      
有多少個線性位址空間?      
1個      
N個      
位址空間可以超過實體記憶體的大小嗎?      
可以      
可以      
資料和函數可以差別開來,分别進行保護嗎?      
不可以      
可以      
能夠很容易地容納長度經常變化的表嗎?      
不可用      
可以      
使用者之間的函數共享是否容易?      
為什麼要發明這項技術?      
為了在實體記憶體空間不變的情形下,
得到更大的線性位址空間      
為了能将代碼和資料劃分為邏輯獨立的位址空間,
為了幫助實作共享和保護      

純分段系統的實作

  當系統運作一段時間後,記憶體将會被劃分為許多塊,其中有些是段,有些是空洞,這種現象稱為跳棋盤(checkerboarding)/外碎片(external fragmentation)      
由于外碎片通常比較小,無法再裝入新的段,因而造成記憶體空間浪費——解決:緊縮技術
      

17. 段頁式存儲管理

一、Pentium虛拟存儲器的核心是兩張表:局部描述符表(Local Descriptor Table,LDT)和全局描述符表(Global Descriptor Table,GDT),每個程式都有自己的LDT,但GDT隻有一個,為計算機上的所有程式共享

段頁式位址變換

頁式存儲-位址轉換:通路2次記憶體,第一次是頁表,第二次是真正的實體記憶體。

頁式存儲—二級頁表:通路3次記憶體

段頁式存儲-位址轉換:通路3次記憶體,第一次是段表,第二次是頁表,第三次是真正實體記憶體

1.基本原理:是分頁與分段的結合,即先将擁護程式分為若幹段,再把每個段分為若幹頁,并為每個段賦予一個段名。

2.位址結構:

《作業系統設計與實作》(第三版)第四章 存儲管理 重要概念彙總1. 存儲器層次結構2. 存儲管理器(memory manager)3.記憶體管理4.重定位和存儲保護5.覆寫與交換6.交換技術、虛拟存儲器情形7.空間配置設定8.對換(Swapping)9. 基于位圖、空閑連結清單的存儲管理10. 虛拟存儲器(Virtual Memory)11. 頁表12.關聯存儲器TLB13.中斷14. 頁面置換算法15. 頁式存儲管理中的設計問題16. 段式存儲管理17. 段頁式存儲管理18. 段式存儲管理

在段頁式存儲管理采用動态重定位,處理器每執行一條指令就将要通路的邏輯位址(s,p,d)取來,要經過如下位址轉換步驟,才能得到最終的實體位址。

(1) 通過段号(s)查段表,得到頁表所在位置。

(2) 根據邏輯頁号(p)通路頁表,得到該頁所在的實體頁号(p’)。

(3) 将實體頁号(p’)和邏輯位址中的頁内位址(d)拼接,形成通路記憶體單元的實體位址(p’,d)。

18. 段式存儲管理

分頁和分段存儲管理有何差別?

①頁是資訊的實體機關,分頁是為實作離散配置設定方式,以消減記憶體的外零頭,提高記憶體的使用率。或者說,分頁僅僅是由于系統管理的需要,而不是使用者的需要。段則是資訊的邏輯機關,它含有一組有意義相對完整的資訊。分段的目的是為了更好地滿足使用者的需要

②頁的大小固定且由系統決定,由系統吧邏輯位址劃分為頁号和頁内位址兩部分,是由機器硬體實作的,因而在系統中隻能有一種大小的頁面,根據資訊的性質來劃分

③分頁的作業位址空間是一維的,即單一的線性位址空間,程式員隻需利用一個記憶符,即可表示一個位址;而分段的作業位址空間則是二維的,程式員在辨別一個位址時,需要給出段名,又需給出段内位址

繼續閱讀