資訊安全系統設計基礎第十四周學習總結

估算學習時間：共10小時

讀書：4

代碼：3

作業：1

部落格：2

實際學習時間：共8.5小時

讀書：2.5

代碼：3.5

部落格：1.5

耗時估計的公式：Y=X+X/N ，Y=X-X/N

第九章 虛拟存儲器

• 為了更加有效地管理存儲器并且少出錯，現代系統提供了一種對主存的抽象概念，叫做虛拟存儲器（VM）。虛拟存儲器是硬體異常、硬體位址翻譯、主存、磁盤檔案和核心軟體的完美互動，它為每個程序提供了一個大的、一緻的和私有的位址空間。通過一個很清晰的機制，虛拟存儲器提供了三個重要的能力：

  1）它将主存看成是一個存儲在磁盤上的位址空間同，主存中隻儲存活動區域，并根據需要在磁盤和主存之間來回傳送資料，通過這種方式，它高效地使用了主存。

  2）它為每個程序提供了一緻的位址空間，進而簡化了存儲器管理。

  3）它保護了每個程序的位址空間不被其他程序破壞。

9.1 實體和虛拟尋址535

• 當CPU執行這條加載指令時，它會生成一個有效實體位址，通過存儲器總線，把它傳遞給主存。主存取出從實體位址4處開始的4位元組的字，并将它傳回給CPU，CPU會将它存放在一個寄存器裡。早期的PC使用實體尋址，而且諸如數字信号處理器、嵌入式微控制器以及Cray超級計算機這樣的系統仍然繼續使用這種尋址方式。然而，現代處理器使用的是一種稱為虛拟尋址的尋址形式，參見圖：

  

9.2 位址空間535

• 位址空間是一個非負整數位址的有序集合。
• 一個位址空間的大小是由表示最大位址所需要的位數來描述的，例如一個包含N＝2的n次方個位址的虛拟位址空間就叫做一個n位位址空間。現代系統典型地支援32位或者64位虛拟位址空間，一個系統還有一個實體位址空間，它與系統中實體存儲器的M個位元組相對應。

9.3 虛拟存儲器作為緩存的工具536

• 概念上而言，虛拟存儲器被組織為一個由存放在磁盤上的N個連續的位元組大小的單元組成的數組。每位元組都有一個唯一的虛拟位址，這個唯一的虛拟位址是作為到數組的索引的。磁盤上數組的内容被緩存在主存中。和存儲器層次結構中其他緩存一樣，磁盤（較低層）上的資料被分割成塊，這些塊作為磁盤和主存（較高層）之間的傳輸單元。VM系統通過将虛拟存儲器分割為稱為虛拟頁的大小固定的塊來處理這個問題。每個虛拟頁的大小為P=2的p次方位元組。類似地，實體存儲器被分割為實體頁大小也為P位元組（實體頁也稱為頁幀。

• 在任意時刻，虛拟頁面的集合都分為三個不相交的子集

  未配置設定的：VM系統還未配置設定（回或者建立）的頁。未配置設定的塊沒有任何資料和它們相關聯，是以也就不占用任何磁盤空間。

  緩存的：目前緩存在實體存儲器中的已配置設定頁。

  未緩存的：沒有緩存在實體存儲器中的已配置設定頁。

9.3.1 dram緩存的組織結構537

• 為了有助于清晰地了解存儲 中不同的緩存概念，我們将使用術語SRAM緩存來表示位于CPU和主存之間的L1、L2和L3高速緩存，并且用術語DRAM緩存來表示虛拟存儲器系統的緩存，它在主存中緩存虛拟頁。
• 在存儲層次結構中，DRAM緩存的位置對它的組織結構有很大的影響。回想一下SRAM比DRAM要快大約10倍，而DRAM要比磁盤快大約100000多倍。是以，DRAM緩存中的不命中比起SRAM緩存中的不命中要昂貴得多，因為DRAM緩存不命中要由磁盤來服務，而SRAM緩存不命中通常是由基于DRAM的主存來服務的。而且，從磁盤的一個扇區讀取第一位元組的時間開銷要比從這個扇區中讀連續的位元組慢大約100000倍。歸根到底，DRAM緩存的組織結構完全是由巨大的不命中開銷驅動的。
• 因為大的不命中處罰和通路第一位元組的開銷，虛拟頁往往很大，典型地是4KB～2MB。由于大的不命中處罰，DRAM緩存是全相聯的，也就是說，任何虛拟頁都可以放置在任何的實體頁中。不命中時的替換政策也很重要，因為替換錯了虛拟頁的處罰也非常之高。是以，與硬體對SRAM緩存相比,作業系統對DRAM緩存使用了更複雜精密的替換算法。最後，因為對磁盤的通路時間很長，DRAM緩存總是使用寫回，而不是直寫。

9.3.2 頁表537

• 同任何緩存一樣，虛拟存儲器系統必須有某種方法來判定一個虛拟頁是否存放在DRAM中的某個地方。如果是，系統還必須确定這個虛拟頁存放在哪個實體頁中。如果不命中，系統必須判斷這個虛拟頁存放在磁盤的哪個位置，在實體存儲器中選擇一個犧牲頁，并将虛拟頁從磁盤拷貝到DRAM中，替換這個犧牲頁。
• 這些功能是由許多軟硬體聯合提供的，包括作業系統軟體、MMU（存儲器管理單元）中的位址翻譯硬體和一個存放在實體存儲器中叫做頁表的資料結構，頁表将虛拟頁映射到實體頁。每次位址翻譯硬體将一個虛拟位址轉換為實體位址時都會讀取頁表。作業系統負責維護頁表的内容，以及在磁盤與DRAM之間來回傳送頁。

9.3.3 頁命中538

9.3.4 缺頁538

• 在虛拟存儲器的習慣說法中，DRAM緩存不命中稱為缺頁。
• 缺頁異常調用核心中的缺頁異常處理程式，該程式會選擇一個犧牲頁，在此例中就是存放在PP3中的VP4。如果VP4已經被修改了，那麼核心就會将它拷貝回磁盤。無論哪種情況，核心都會修改VP4的頁表條目，反映出VP4不再緩存在主存中這一事實。
• 接下來，核心從磁盤拷貝VP3到存儲器中的PP3，更新PTE3，随後傳回。當異常處理程式傳回時，它會重新啟動導緻缺頁的指令，該指令會把導緻缺頁的虛拟位址重發送到位址翻譯硬體。但是現在，VP3已經緩存在主存中了，那麼頁命中也能由位址翻譯硬體正翻譯硬體正常處理了。圖4展示了在缺頁之後我們的示例頁表的狀态：

  

9.3.5 配置設定頁面539

• 下圖展示了當作業系統配置設定一個新的虛拟存儲器頁時對我們示例頁表的影響，例如調用malloc的結果。

  

9.3.6 又是局部性救了我們539

• 隻要我們的程式有好的時間局部性，虛拟存儲器系統就能工作得相當好。但是，當然不是所有的程式都能展現良好的時間局部性。如果工作集的大小超出了實體存儲器的大小，那麼程式将産生一種不幸的狀态，叫做颠簸這時頁面将不斷地換進換出。雖然虛拟存儲器通常是有效的，但是如果一個程式性能慢得像爬一樣，那麼聰明的程式員會考慮是不是發生了颠簸。

9.4 虛拟存儲器作為存儲器管理的工具540

• 按需頁面排程和獨立的虛拟位址空間的結合，對系統中存儲器的使用和管理造成了深遠的影響。特别地，VM簡化了連結和加載、代碼和資料共享，以及應用程式的存儲器配置設定。
• 簡化連結
• 簡化加載
• 簡化共享
• 簡化存儲器配置設定

9.5 虛拟存儲器作為存儲器保護的工具541

• 任何現代計算機系統必須為作業系統提供手段來控制對存儲器系統的通路。不應該允許一個使用者程序修改它的隻讀文本段。而且也不應該允許它讀或修改任何核心中的代碼和資料結構。不應該允許它讀或者寫其他程序的私有存儲器，并且不允許它修緻任何與其他程序共享的虛拟頁面，除非所有的共享者都顯式地允許它這麼做（通過調用明确的程序間通信系統調用）。
• 就像我們所看到的，提供獨立的位址空間使得分離不同程序的私有存儲器變得容易。但是，位址翻譯機制可以以一種自然的方式擴充到提供更好的通路控制。因為每次CPU生成一個位址時，位址翻譯硬體都會讀一個PTE，是以通過在PTE上添加一些額外的許可位來控制對一個虛拟頁面内容的通路十分簡單。下圖展示了大緻的思想。在這個示例中，每個PTE中已經添加了三個許可位。SUP位表示程序是否必須運作在核心超級使用者）模式下才能通路該頁。

  

9.6 位址翻譯542

• 所有符号如下：

  

• 當頁面命中時，CPU硬體執行的步驟

  第一步：處理器生成一個虛拟位址并把它傳送給MMU

  第二步：MMU生成PTE位址，并從高速緩存／主存請求得到它

  第三步：高速緩存／主存向MMU傳回PTE

  第四步：MMU構造實體位址并把它傳送給高速緩存／主存

  第五步：高速緩存／主存傳回所請求的資料字給處理器。

  頁面命中完全是由硬體來處理的，與之不同的是，處理缺頁要求硬體和作業系統核心協作完

  第一步到第三步：和圖中的第一步到第三步相同；

  第四步：PTE中的有效位是零，是以MMU觸發了一次異常，傳遞CPU中的控制到作業系統核心中的缺頁異常處理程式。

  第五步：缺頁處理程式确定出實體存儲器中的犧牲頁，如果這個頁面已經被修改了，則把它換出到磁盤。

  第六步：缺頁處理程式頁面調入新的頁面，并更新存儲器中的PM。

  第七步：缺頁處理程式返虛拟位址重新發送給MMU。因為虛拟頁面現在緩回到原來的程序，再次執行導緻缺頁的指令。CPU将引起缺頁的現在緩存在實體存儲器中，是以就會命中，在MMU執行了圖中的步驟之後，主存就會将所請求字傳回給處理器。

9.6.1 結合高速緩存和虛拟存儲器544

• 在任何既使用虛拟存儲器又使用SRAM高速緩存的系統中，都存在應該使用虛拟位址還是使用讨論範圍，但是大多數系統是選擇實體尋址的。使用實體尋址L多個程序同時在高速緩存中有存儲塊和共享來自相同虛拟頁面的塊成為很簡單的事情。而且，高速緩存無需處理保護問題，因為通路權限的檢查是位址翻譯過程的一部分。

9.6.2 利用tlb加速位址翻譯545

• 正如我們看到的，每次CPU産生一個虛拟位址，MMU就必須查閱一個PTE，以便将虛拟位址翻譯為實體位址。在最糟糕的情況下，這又會要求從存儲器取一次資料，代價是幾十到幾百個周期。如果PTE正碰巧緩存在L1中，那麼開銷就下降到1個或2個周期。然而，許多系統都試圖消除這樣的開銷，它們在MMU中包括了一個關于PTE的小的緩存，稱為翻譯後備緩沖器。
• TLB是一個小的、虛拟尋址的緩存，其中每一行都儲存着一個由單個PTE組成的塊。TLB通常有高度的相聯性。如圖所示，用于組選擇和和行比對的索引和标記字段是從虛拟位址中的虛拟頁号中提取出來的。如果TLB有T＝2的t次方個組，那麼TLB索引（T田1）是由VPN的t個最低位組成的，而TLB标記是由VPN中剩餘的位組成的。

9.6.3 多級頁表546

• 到目前為止，我們一直假設系統隻用一個單獨的頁表來進行位址翻譯。但是如果我們隻有32位的位址空間、4KB的頁面和一個4位元組的PTE，那麼即使應用所引用的隻是虛拟位址空間中的很小一部分，也總是需要—個4MB的頁表駐留在存儲器中。對于位址空間為64位的系統來說，問題将變得更複雜。

9.6.4 綜合:端到端的位址翻譯547

1. TLB是利用VPN的位進行虛拟尋址的。因為TLB有四個組，是以VPN的低兩位就作為組索引（TLBI）。VPN中剩下的高6位作為标記（TLBT），用來差別可能映射到同一個TLB組的不同的VPN。
2. 頁表。這個頁表是一個單級設計，一共有256個頁表條目（PTE）。然而，我們隻對這些條目中的開頭16個感興趣。為了友善，我們用索引它的VPN來辨別每個PTE；但是要記住PPN都用一個破折号來表示，以加強一個概念：無論剛好這裡存儲的是什麼位值，都是沒有任何意義的。
3. 高速緩存。直接映射的緩存是通過實體位址中的字段來尋址的。

9.7 案例研究:intel core i7/linux存儲器系統550

1. 處理器包包括四個核、一個大的所有核共享的L3高速緩存，以及一個DDR3存儲器控制器。
2. 每個核包含一個層次結構的TLB、一個層次結構的資料和指令高速緩存，以及一組快速的點到點連接配接，這種連接配接是基于Intel QuickPath技術的，是為了讓一個核與其他核和外部Ｉ／Ｏ橋直接通信。TLB是虛拟尋址的，是四路組相聯的。L１、Ｌ２和Ｌ３高速緩存是實體尋址的，其中，Ｌ１和Ｌ２是八路組相聯的，Ｌ３是16路組相聯的，塊大小為64位元組。頁大小在啟動時被配置為4KB或4MB。Ｌｉｎｕｘ使用的是4KB的頁。

9.7.1 core i7位址翻譯551

1. PTE有三個權限位，控制對頁的通路。R／Ｗ位确定頁的内容是可以讀寫的還是隻讀的。U／Ｓ位确定是否能夠在使用者模式中通路該頁，進而保護作業系統核心中的代碼和資料不被使用者程式通路。XD（禁止執行）位是在６４位系統中引入的，可以用來禁止從某些存儲器頁取指令。這是一個重要的新特性，通過限制隻能執行隻讀文本段，使得作業系統核心降低了緩沖區溢出攻擊的風險。
2. 當MMU翻譯每一個虛拟位址時，它還會更新另外外兩個核心缺頁處理程式會用到的位。每次通路一個頁時，MMU都會設定A位，稱為引用位。核心可以用這個引用位來實作它的頁替換算法。每次對一個頁進行了寫之後，MMU都會設定D位，又稱髒位。髒位告訴核心在拷貝替換頁之前是否必須寫回犧牲頁。核心可以通過調用一條特殊的核心模式指令來清除引用位或髒位。

9.7.2 linux虛拟存儲器系統554

1. 一個虛拟存儲器系統要求硬體和核心軟體之間的緊密協作。版本與版本之間細節都不盡同，對此完整的闡釋超出了我們讨論的範圍，但是，在這一小節中我們的目标是對Linux的虛拟存儲器系統做一個描述，使你能夠大緻了解一個實際的作業系統是如何組織虛拟存儲器，以及如何處理缺頁的。
2. 核心虛拟存儲器包含核心中的代碼和資料結構。核心虛拟存儲器的某些區域被映射到所有程序共享的實體頁面。例如，每個程序共享核心的代碼和全局資料結構。有趣的是，Linux也将一組連續的虛拟頁面（大小等于系統中DRAM的總量）映射到相應的一組連續的實體頁面。這就為核心提供了一種便利的方法來通路實體存儲器中任何特定的位置，例如，當它需要通路頁表，或在一些裝置上執行存儲器映射的I/O操作，而這些裝置被映射到特定的實體存儲器位置時。
3. （1）Linux虛拟存儲區域（2）Linux缺頁異常處理

9.8 存儲器映射556

Linux(以及其他一些形式的Unix)通過将一個虛拟存儲器區域與一個磁盤上的對象(object)關聯起來，以初始化這個虛拟存儲器區域的内容，這個過程稱為存儲器映射(memory mapping)。虛拟存儲器區域可以映射到兩種類型的對象的一種：

(1)Unix檔案上的普通檔案：一個區域可以映射到一個普通磁盤檔案的連續部分，例如一個可執行目标檔案。檔案區(section)被分成頁大小的片，每一片包含一個虛拟頁面的初始化内容。因為按需進行頁面高度，是以這些虛拟頁面沒有實際進行實體存儲器，直到CPU第一次引用到頁面(即發射一個虛拟位址，落在位址空間這個頁面的範圍之内)。如果區域檔案區要大，那麼就用零來填充這個區域的餘下部分。

(2)匿名檔案：一個區域也可以映射到一個匿名檔案，匿名檔案是由核心建立的，包含的全是二進制零。CPU第一次引用這樣一個區域内的虛拟頁面時，核心就在實體存儲器中找到一個合适的犧牲頁面，如果該頁面被修改過，就将這個頁面換出來，用二進制零覆寫犧牲頁面并更新頁表，将這個頁面标記為是駐留在存儲器中的。注意在磁盤和存儲器之間沒有實際的資料傳送。因為這個原因，映射到匿名檔案的區域中的頁面有時也叫做請求二進制零的頁(demand-zero page)。

無論在哪種情況下，一旦一個虛拟頁面被初始化了， 它就在一個由核心維護的專門的交換檔案(swap file)之間換來換去。交換檔案也叫做交換空間(swap space)或者交換區域(swap area)。需要意識到的很重要的一點，在任何時刻，交換空間都限制着目前運作着的程序能夠配置設定的虛拟頁面的總數。

9.8.1 再看共享對象557

1. 存儲器映射的概念來源于一個聰明的發現：如果虛拟存儲器系統可以內建到傳統的檔案系統中，那麼就能提供一種簡單而高效的把程式和資料加載到存儲器中的方法。
2. 正如我們已經看到的程序這一抽象能夠為每個程序提供自己私有的虛拟位址空間，可以免受其他程序的錯誤讀寫。不過，許多程序有同樣的隻讀文本區域例如，每個運作Unix外殼程式tcsh的程序都有相同的文本區域。而且，許多程式需要通路隻讀運作時庫代碼的相同拷貝。例如，每個C程式都需要來自标準c庫的諸如printf這樣的函數。那麼，如果每個程序都在實體存儲器中保持這些常用代碼的複制拷貝，那就是極端的浪費了。幸運的是，存儲器映射給我們提供了一種清晰的機制，用來控制多個程序如何共享對象。

3. 一個對象可以被映射到虛拟存儲的一個區域，要麼作為共享對象，要麼作為私有對象。如果一個程序将一個共享對象映射到它的虛拟位址空間的一個區域内，那麼這個程序對這個區域的任何寫操作，對于那些也把這個共享對象映射到它們虛拟存儲器的其他程序而言也是可見的。而且，這此變化也會反映在磁盤上的原始對象中。(IPC的一種方式)

   另一方面，對一個映射到私有對象的區域做的改變，對于其他程序來說是不可見的，并且程序對這個區域所做的任何寫操作都不會反映在磁盤上的對象中。一個映射到共享對象的虛拟存儲器區域叫做共享區域。類似地，也有私有區域。

4. 共享對象的關鍵點在于即使對象被映射到了多個共享區域，實體存儲器也隻需要存放共享對象的一個拷貝。
5. 一個共享對象(注意，實體頁面不一定是連續的。)
6. 私有對象是使用一種叫做寫時拷貝(copy-on-write)的巧妙技術被映射到虛拟存儲器中的。對于每個映射私有對象的程序，相應私有區域的頁表條目都被标記為隻讀，并且區域結構被标記為私有的寫時拷貝。

9.8.2 再看fork函數558

1. 當fork函數被目前程序調用時，核心為新程序建立各種資料結構，并配置設定給它一個唯一的PID。為了給這個新程序建立虛拟存儲器，它建立了目前程序的mm_struct、區域結構和頁表的原樣拷貝。它将兩個程序中的每個頁面都為标記隻讀，并将兩個程序中的每個區域結構都标記為私有的寫時拷貝。
2. 當fork在新程序中傳回時，新程序現在的虛拟存儲器剛好和調用fork時存在的虛拟存儲器相同。當這兩個程序中的任一個後來進行寫操作時，寫時拷貝機制就會建立新頁面，是以，也就為每個程序保持了私有位址空間的抽象概念。

9.8.3 再看execve函數559

假設運作在目前程序中的程式執行了如下的調用：

execve("a.out",NULL,NULL) ;

execve函數在目前程序中加載并運作包含在可執行目标檔案a.out中的程式，用a.out程式有效地替代了目前程式。加載并運作a.out需要以下幾個步驟：

删除已存在的使用者區域。删除目前程序虛拟位址使用者部分中的已存在的區域結構。

映射私有區域。為新程式的文本、資料、bss和棧區域建立新的區域結構。所有這些新的區域都是私有的、寫時拷貝的。文本和資料區域被映射為a.out檔案中的文本和資料區。bss區域是請求二進制零的，映射到匿名檔案，其大小包含在a.out中。棧和堆區域也是請求二進制零的。

映射共享區域。如果a.out程式與共享對象(或目标)連結，比如标準C庫libc.so，那麼這些對象都是動态連結到這個程式的，然後再映射到使用者虛拟位址空間中的共享區域内。

設定程式計數器(PC)。execve做的最後一件事情就是設定目前程序上下文中的程式計數器，使之指向文本區域的入口點。

下一次排程這個程序時，它将從這個入口點開始執行。Linux将根據需要換入代碼和資料頁面。

9.8.4 使用mmap函數的使用者級存儲器映射559

參數含義：

start：這個區域從start開始

fd：檔案描述符

length：連續的對象片大小

offset：距檔案開始處的偏移量

prot：通路權限位，具體如下：

PROT_EXEC:由可以被CPU執行的指令組成

PROT_READ:可讀

PROT_WRITE:可寫

PROT_NONE:不能被通路

flag：由描述被映射對象類型的位組成，具體如下：

MAP_ANON:匿名對象，虛拟頁面是二進制0

MAP_PRIVATE:私有的、寫時拷貝的對象

MAP_SHARED：共享對象

mmap函數要求核心建立一個新的虛拟存儲器區域是，最好是從位址start開始的一個區域，并将檔案描述符fd指定的對象的一個連續的片(chunk)映射到這個新區域。連續的對象片大小為length位元組，從距檔案開始處偏移量為offset位元組的地方開始。start位址僅僅是一個暗示，通常被定義為NULL。

9.9 動态存儲器配置設定561

1. 動态存儲器配置設定器維護着一個程序的虛拟存儲器區域，稱為堆。
2. 存儲器配置設定器有兩種：顯示配置設定器，隐式配置設定器。

9.9.1 malloc和free函數561

1. 顯示配置設定器包括：malloc和free，這兩個函數就是兩個配置設定器，隻是職能不同。
2. 隐式配置設定器，也叫垃圾收集器，看來隻有垃圾收集的功能。沒有相應的配置設定功能。
3. malloc傳回一個指針，指向大小為至少size位元組的存儲塊。遇到問題的話，就傳回NULL。
4. sbrk擴充和收縮堆。
5. freee參數必須為malloc，calloc，realloc傳回的指針。其沒有傳回值。

9.9.2 為什麼要使用動态存儲器配置設定563

這裡的存儲器配置設定器，是對堆内部空間的配置設定和釋放。和堆大小沒有關系。

直到程式實際運作時，程式才知道某些資料結構的大小。

9.9.3 配置設定器的要求和目标564

顯式配置設定器必須在一些相當嚴格的限制條件下工作：

(1)處理任意請求序列

(2)立即響應請求

(3)隻使用堆

(4)對齊塊（對齊要求）——在大多數系統中，這意味着配置設定器傳回的塊是8位元組邊界對齊的。

不修改已配置設定的塊——像壓縮已配置設定塊這樣的技術是不允許被使用的（這裡是指已配置設定的塊，而不是堆，sbrk函數可以擴充和收縮堆）

配置設定器有兩個目标：

(1)最大化的吞吐率——其實就是以最快的方式執行諸如malloc和free這樣的函數；

(2)最大化存儲器使用率——通常用峰值使用率來表示存儲器使用率，這個值是有效載荷/堆大小。

這兩個目标其實是互相抑制的。

9.9.4 碎片565

堆的碎片：内部碎片和外部碎片。

内部碎片——對齊限制條件和具體實作中有最小配置設定塊的要求。

外部碎片——有很多空間塊，但滿足不了一個配置設定請求。

9.9.5 實作問題565

9.9.6 隐式空閑連結清單565

隐式空閑連結清單——空閑塊通過頭部的大小字段隐含地連接配接在一起。

9.9.7 放置已配置設定的塊567

1. 當一個應用請求一個k位元組的塊時，配置設定器搜尋空閑連結清單，查找一個足夠大可以放置所請求塊的空閑塊，執行這種搜尋的方式由放置政策确定。
2. 首次配置設定:從頭開始搜尋空閑連結清單
3. 下一次适配：從上一次查詢結束的地方開始搜尋
4. 最佳适配：檢查每個空閑塊，選擇适合所請求大小的最小空閑塊

9.9.8 分割空閑塊567

9.9.9 擷取額外的堆存儲器567

9.9.10 合并空閑塊568

為了解決假碎片問題，任何實際的配置設定器都必須合并相鄰的空閑塊，這個過程稱為合并。這就出現了一個重要的政策決定，那就是何時執行合并。配置設定器可以選擇立即合并以選擇推遲合并。也就是等到某個稍晚的時候再合并空閑塊。例如，配置設定器可以推遲合并，直到某個配置設定請求失敗，然後掃描整個堆，合并所有的空閑塊。立即合并很簡單明了，可以在常數時間内執行完成，但是對于某些請求模式，這種方式會産生一種形式的抖動，塊會反複地合并，然後馬上分割。例如，在圖中，反複地配置設定和釋放個3個字的塊将産生大量不必要的分割和合并。在對配置設定器的讨論中，我們會假設使用立即合并，但是你應該了解，快速的配置設定器通常會選擇某種形式的推遲合并。

9.9.11 帶邊界标記的合并568

想要釋放的塊稱為目前塊。

考慮當配置設定器釋放目前塊時所有可能存在的情況：

1）前面的塊和後面的塊都是已配置設定的。

2）前面的塊是已配置設定的，後面的塊是空閑的

3）前面的塊是空閑的，而後面的塊是已配置設定的。

4）前面的和後面的塊都是空閑的。

9.9.12 綜合:實作一個簡單的配置設定器570

構造一個配置設定器是一件富有挑戰性的任務。設計空間很大，有多種塊格式、空閑連結清單格式，以及放置、分割和合并政策可供選擇。另一個挑戰就是你經常被迫在類型系統的安全和熟悉的限定之外程式設計，依賴于容易出錯的指針強制類型轉換和指針運算，這些操作都屬于典型的低層系統程式設計。

1. 一般配置設定器設計
2. 操作空閑連結清單的基本常數和宏
3. 建立初始空閑連結清單
4. 釋放和合并塊
5. 配置設定塊

9.9.13 顯式空閑連結清單576

使用雙向連結清單而不是隐式空閑連結清單，使首次适配的配置設定時間從塊總數的線性時間減少到了空所選擇的閑塊數量的線性時間。不過，釋放一個塊的時間可以是線線性的，也可能是個常數，這取決于我們所選擇的空閑連結清單中塊的排序政策。

一種方法是用後進先出的順序維護連結清單，将新釋放的塊放置在連結清單的開始處。使用LIFO的順序和首次适配的放置政策，配置設定器會最先檢查最近使用過的塊。在這種情況下，釋放一個塊可以在常數時間内完成。如果使用了邊界标記，那麼合并也可以在常數時間内完成；

另一種方法是按照位址順序來維護連結清單，其中連結清單中每個塊的位址都小于它後繼的位址。在這種情況下，釋放一個塊需要線性時間的搜尋來定位合适的前驅。平衡點在于，按照位址排序的首次适配比LIFO排序的首次适配有更高的存儲器使用率，接近最佳适配的使用率。一般而言，顯式連結清單的缺點是空閑塊必須足夠大以包含所有需要的指針，以及頭部和可能的腳部。這就導緻了更大的最小塊大小，也潛在地提高了内部碎片的程度。

9.9.14 分離的空閑連結清單576

1. 簡單分離存儲

   每個大小類的空閑連結清單包含大小相等的塊，每個塊的大小就是這個大小類中最大元素的大小。

   優點：配置設定和釋放塊快

   缺點：容易造成碎片

2. 分離适配

   配置設定一個塊：确定請求的大小類，對适當的空閑連結清單做首次适配，查找一個合适的塊，找到一個之後，可選的分割它，并将剩餘部分插入适當的空閑連結清單中，如果找不到合适的塊，就搜尋下一個更大的大小類的空閑連結清單，直到找到一個合适的塊，如果沒有合适的塊，就向作業系統請求額外的堆存儲器，并從這個新的堆存儲器中配置設定出一個塊，将剩餘部分放置在适當的大小類中，釋放塊時，執行合并，并将結果放置在相應的空閑連結清單裡。

3. 夥伴系統

   夥伴系統是分離适配的一種特例，每個大小類都是2的幂。

   優點：快速搜尋和快速合并。

   缺點：内部碎片。

9.10 垃圾收集578

垃圾收集：采用何種方式來辨識垃圾呐，系統采用的是圖的方式進行，将存儲器視為一張有向圖，每個節點是根節點或堆節點，節點表示的一個配置設定塊，如果在一個塊中指向另一個塊的某個位置，就連接配接，當存在一條從任意根節點出發并到達堆節點的有向路徑時，視為可達，那些不可達的節點就是垃圾節點。再進行回收時，有兩個階段，标記和回收，标記垃圾節點，清除。

9.10.1 垃圾收集器的基本知識579

垃圾收集器将存儲器視為一張有向可達圖，其形式如圖所示。該圖的節點被分成一組根節點和一組堆節點每個堆節點對應于堆中的一個已配置設定塊。有向邊p一q意味着塊p中的某個位置指向塊q中的某個位置。根節點對應于這樣一種不在堆中的位置，它們中包含指向堆中的指針。這些位置可以是寄存器、棧裡的變量，或者是虛拟存儲器中讀寫資料區域内的全局變量。

9.10.2 mark&sweep垃圾收集器580

mark&sweep垃圾收集器由标記和清除階段組成。

9.10.3 c程式的保守mark&sweep580

第一，C不會用任何類型資訊來标記存儲器位置。是以，對isPtr沒有一種明顯的方式來判斷它的輸入參數p是不是一個指針。第二，即使我們知道p是一個指針，對isPtr也沒有明顯的方式來判斷p是否指向一個已配置設定塊的有效載荷中的某個位置。

對後一問題的解決方法是将已配置設定塊集合維護成一棵平衡二叉樹，這棵樹保持着這樣一個屬性：左子樹中的所有塊都放在較小的位址處，而右子樹中的所有塊都放在較大的位址處。如圖所示，這就要求每個已配置設定塊的頭部裡有兩個附加字段（left和right）。每個字段指向某個已配置設定塊的頭部。

9.11 c程式中常見的與存儲器有關的錯誤581

9.11.1 間接引用壞指針582

經典的scanf錯誤

在這種情況下，scanf将把val的内容解釋為一個位址，并試圖将一個字寫到這個位置。在最好的情況下，程式立即以異常中止。在最糟糕的情況下，val的内容對應于虛拟存儲器的某合法的讀／寫區域，于是我們就覆寫了存儲器，這通常會在相當長的段時間以後造成災難性的、令人困惑的後果。

9.11.2 讀未初始化的存儲器582

一個常見的錯誤

9.11.3 允許棧緩沖區溢出582

使用fgets()糾正錯誤，這個函數限制了輸入串的大小。

9.11.4 假設指針和它們指向的對象是相同大小的583

一種常見的錯誤是假設指向對象的指針和他們所指向的對象是大小相同的。

9.11.5 造成錯位錯誤583

錯位錯誤是一種很常見的覆寫錯誤來源。

9.11.6 引用指針，而不是它所指向的對象583

9.11.7 誤解指針運算584

另一種常見的錯誤是忘記了指針的算術操作是以它們指向的對象的大小為機關來進的，而這種大小機關并不一定是位元組。

9.11.8 引用不存在的變量584

不了解棧的規則，有時會引用不再合法的本地變量。

9.11.9 引用空閑堆塊中的資料584

一個相似的錯誤是引用已經被釋放了的堆塊中的資料。

9.11.10 引起存儲器洩漏585

存儲器洩露是緩慢隐形的殺手。

9.12 小結585

虛拟存儲器是對主存的一個抽象。支援虛拟存儲器的處理器通過使用一種叫做虛拟尋址的間接形式來引用主存。處理器産生一個虛拟位址，在被發送到主存之前，這個位址被翻譯成一個實體位址。從虛拟位址空間到實體位址空間的位址翻譯要求硬體和軟體緊密合作。專門的硬體通過使用頁表來翻譯虛拟位址，而頁表的内容是由作業系統提供的。

參考資料

1. 教材：第九章，詳細學習指導：http://group.cnblogs.com/topic/73069.html
2. 課程資料：https://www.shiyanlou.com/courses/413 實驗十，課程邀請碼：W7FQKW4Y
3. 教材中代碼運作、思考一下，讀代碼的學習方法：http://www.cnblogs.com/rocedu/