【知识强化】第三章内存管理 3.1 内存管理概念

谁践踏了优雅 2021-11-16 11:04 257阅读 0赞

![1089139-20190723082005215-372372272.png][]

![1089139-20190723082218650-1721573475.png][]

![1089139-20190723082316132-1174390813.png][]

![1089139-20190723082454279-1425546888.png][]

![1089139-20190723082529459-63476608.png][]

***其實内存它的作用就是用來存放數據。我們的程序本來是放在外存、放在磁盤當中的，但是磁盤的讀寫速度很慢，而CPU的處理速度又很快，所以如果CPU要執行這個程序，程序相關的數據都是從外存讀入的，那麽很顯然CPU的這個速度會被外存的速度給拖累。所以爲了緩和這個CPU和硬盤、外存之間的速度矛盾，所以我們必須先把我們要執行的、CPU要處理的這些程序數據把它放入内存裏。既然我們的内存是存放數據的，那麽我們的内存當中可能會存放很多很多數據，那操作系統是怎麽區分各個程序的數據是放在什麽地方的呢？那爲了區分這些數據存放的位置，就需要給内存進行一個地址的編號。就有點類似於說我們去住酒店的時候，怎么區分我們每個人住在哪個房間？其實很簡單，酒店的做法就是給每個房間編號，那我們的内存其實和這個酒店是一樣的，只不過酒店的這些房間裏你可以存的是人，而内存當中，它的這些“小房間”裏，它存的是一個一個的數據。那内存會被劃分成這樣一個一個的“小房間”，每個小房間就是一個存儲單元。那接下來在劃分的這些存儲單元之後，就需要給這些存儲單元進行一個編號。那内存的這個地址編號一般來説是從零開始的，然後依次遞增。并且每個地址會對應一個數據的存儲單元，也就是會對應一個“小房間”。那麽，這樣的一個存儲單元可以存放多少數據呢？這個具體得看計算機的編址方式。我們在操作系統這門課當中大部分遇到的情況是會告訴你說計算機按字節編址，按字節編址的意思就是一個地址它對應的是一個字節的數據，也就是說這樣的一個存儲單元，它可以存放一個字節，而一個字節它又由8個二進制位組成，也就是8個0101這樣組成。那在有的題目當中也有可能會告訴我們這個計算機是按字編址的，如果它告訴我們是按字編址的話，那麽就意味著一個地址它所對應的存儲單元可以存放一個字，而一個字的長度是多少個比特位？這個具體得看題目當中給出的條件。有的計算機當中字長是16位，那麽它一個字的大小就是16個比特。也有的計算機可能字長是32位，字長是64位等等。總之，我們需要根據題目給的條件來判斷一個字它占有多少個比特位。好的，那麽在這個部分我們為大家介紹了内存的一些最基本的知識。什麽叫做存儲單元，就是用於存放數據的最小單元。另外，每一個地址可以對應這樣的一個存儲單元。而一個存儲單元可以存儲多少數據，那具體要看這個計算機它是怎麽設計的。對於我們考研來説，我們就要看它題目給的條件到底是什麽。***

![1089139-20190723091053812-1999818877.png][]

***那在内存管理這個章節當中，可能會有很多題目會涉及到這個數據的一些基本單位。而對於不考計組的同學來説可能對這些單位的描述是比較陌生的，所以我們在這個地方還需要再介紹一下一些常見的單位。比如說我們平時所説的一個手機，或者說一台電腦它有4GB内存，那除了GB之外，我們還經常看到什麽MB，KB這樣的單位。那所謂的1KB，其實就是2的10次方這麽多。而1MB，其實是2的20次方這麽多。而這裏的1GB，其實是2的30次方那麽多。所以這個地方4G其實它是一個數量，而B是一個數據的單位，這個大BByte指的是字節，小b小寫的b它指的是bit，是一個比特位，一個二進制位。一個Byte也就是一個大B等於8個小b，所以如果一個手機有4GB内存的話那麽就意味著這個手機的内存當中它可以存放4\*2^30這麽多個字節的數據。所以如果這個手機或者這個電腦它是按字節編址的，那麽這個内存的地址空間就應該是4\*2^30這麽多個存儲單元。每一個存儲單元可以存放一個字節。那我們知道，在計算機的世界當中，所有的這些數字其實都是用二進制0101這樣來表示的。包括我們的内存地址，其實也需要用二進制來表示。所以有的題目當中可能會告訴我們，内存的大小是多少。比如說内存大小是4GB，并且告訴我們這個内存是按字節編址的，題目可能會問我們到底需要多少個二進制位才能表示這麽多個存儲單元也就是2^32次方個存儲單元。那對於跨考的同學來說，一定要去了解一下二進制編碼還有二進制數和這個十進制數的一個轉換關係。對二進制比較熟悉的就可以很快速地反應出來這麽多個存儲單元肯定就需要32個二進制位來表示。所以如果手機的内存是4GB，并且它是按字節編址的，那麽對於這個手機來説它的地址至少需要用32個二進制位來表示。好的那麽再次提醒，對於跨考的同學來說，如果二進制和十進制的這個轉換不是很熟練的話，一定要下去練習。***

***![1089139-20190723094829545-1570999771.png][]***

***在瞭解了内存的作用、内存的存儲單元、内存的地址這些概念之後，我們再結合之前我們提到過的一些基礎再給大家更進一步深入地講解一下指令工作的具體原理。這個知識點有助於大家對後面的那些内容的更深入的理解。那我們之前的學習當中提到過，其實我們用高級語言編程的代碼經過編譯之後，會形成與它對應的等價的一系列的機器語言指令。每一條指令就是讓CPU幹一件具體的事情。比如說我們用C語言寫的x=x+1;這樣一個很簡單的操作，經過編譯之後可能會形成這樣的三條與它對等的機器指令。那當這個程序運行的時候，系統會爲它建立相應的進程，而我們之前學到過一個進程在内存當中會有一片區域叫做程序段就是用於存放這個進程相關的那些代碼指令的。另外還有一個部分叫做數據段，數據段就是用來存放這個程序所處理的一些變量啊之類的數據。比如說我們這兒的x變量，它就是存放在所謂的數據段裏。那我們來看一下這三條指令分別代表著什麽呢？CPU在執行這几條指令的時候首先它取出了指令1，然後指令1它發現由這樣的幾個部分組成。第一個部分紅色的這個部分叫做操作碼，就是指明了這條指令是要幹一件什麽事情。那這個地方的二進制碼我只是胡亂寫的，大家只需要理解它的原理就可以了。那我們假設這個什麽101100它代表的是讓CPU做一個數據傳送的事情。那後面這兩段數據又是指明了這個操作相關的一些必要的參數。比如說我們的指令1就是讓CPU從内存地址01001111把這個地方存放的數據把它取到對應十進制就是編號為3的這個寄存器當中。所以CPU在執行這個指令的時候，它就知道我現在要做的事情是要做數據的傳送。那怎麽傳送呢？我需要從地址為79的這個内存單元當中，把它裏面的數據取出來，然後把它放到編號為3的這個寄存器當中。所以指令1的執行就會導致編號為3的這個寄存器當中有了10這個數。把x的值放到了這個寄存器中。那在執行了指令1之後，CPU就會開始執行指令2。***

***![1089139-20190723103145837-751454785.png][]***

***同樣的，它會解析這個指令2到底是要幹一件什麽事情。根據它前面的這個部分，也就是所謂的操作碼，它可以判斷出這個指令是要做一個加法操作，加法運算。而怎麽加呢？CPU需要把編號為00000011也就是換成十進制的話也就是編號為3的這個寄存器當中的内容加上1，所以根據這條指令CPU會把這個寄存器當中的值從10加1，也就是變成11。***

***![1089139-20190723113145455-555973761.png][]***

![1089139-20190723113216869-126109622.png][]

![1089139-20190723113333734-568179118.png][]

![1089139-20190723113248436-2015528146.png][]

![1089139-20190723113426895-34926779.png][]

***那再接下來它又執行的是第三條指令。這個指令同樣是一個數據傳送的指令。可以看到它的這個操作碼和第一個指令的操作碼是一樣的，就説明這兩條指令它們要幹的是同一個事情，是同一種指令。只不過它們的參數是不一樣的，大家可以對比著來看一下。那這個指令3是讓CPU幹這樣的一個事情。它需要把編號為3的這個寄存器當中的内容，把它寫回編號為01001111這個内存單元當中，所以CPU在執行第三條指令的時候，就會把這個寄存器當中的内容把它寫回x這個變量在内存當中存放的那個地址。因此這就完成了x=x+1;這樣的一個操作。當然剛才我們講的這三條指令只是我自己胡亂寫的，其實并不嚴謹。如果大家想要了解這些指令真正的什麽操作碼啊參數啊到底是什麽樣一種規範，那還需要學習計算機組成原理。但是對於不考那門課的同學來説，只要理解到這一步就差不多了。其實CPU在執行這些一條一條指令的過程當中，它就是在處理這些内存啊或者寄存器當中的數據，而怎麽處理這些數據，怎麽找到這些數據呢？它就是基於地址這個很重要的概念來進行的。我們的内存會有它自己的一些地址編址，同樣的我們的寄存器也會有一些它自己的地址編址。總之我們的程序經過編譯之後，會形成一系列等價的機器指令。在這個機器指令當中它會有一些相應的參數，告訴CPU你應該去哪些地址去讀數據，或者往哪些地址寫數據。那在剛才我們講的這個例子當中，我們默認了我們所提到的這個進程它是從0這個地址開始連續存放的。所以在它的這個指令當中，是直接指明了各個變量的存放位置。比如說x的存放地址，它就直接把它寫死在了這個指令裏。它是存放在79這個地址所對應的存儲單元裏的。那接下來我們要思考的一個問題是這樣的，如果我們的這個地址它不是從零開始存放的，而是從別的地址開始存放的，會不會導致我們的這個進程的運行出現一些問題呢？我們來具體看一下。***

***![1089139-20190723115741088-1487168735.png][]***

***這個可執行文件在Windows系統當中就是.exe，這個可執行文件又可以稱作為裝入模塊。這個概念我們之後還會具體細聊。總之我們形成了這個裝入模塊，形成了這個可執行文件之後，就可以把這個可執行文件放入内存裏然後就開始執行這個程序了。不過需要注意的是，我們所形成的這個可執行文件，它的這些指令當中所指明的這些地址參數，其實指的是一個邏輯地址，一個相對地址。所謂的相對地址就是指，這個地址指的是它相對於這個進程的起始地址而言的地址。有點繞，不過其實並不難理解，在之前的那個例子當中，我們是默認了這個進程它相關的這些數據是從内存地址為零這個地方開始存放的。所以這條指令它是要進行x這個變量的初始化，并且它指明了x這個變量它存放的地址是79，它的初始值為10，所以CPU在執行這條指令的時候，它會往79這個地址所對應的内存單元裏寫入x的初始值10，那這是我們剛才提到的情況。我們的這個程序裝入模塊，它是從内存地址為零這個地方開始往後依次存放的，所以我們的指令當中指明的這些地址并不會出現什麽問題。***

***![1089139-20190723133044612-1270825131.png][]***

***那接下來再來看另一種情況。假設我們的這個程序的裝入模塊，它裝入内存的時候，并不是從地址為零的地方開始的，而是從地址為100的這個地方開始的。那麽這就意味著操作系統給這個進程、給這個程序分配的地址空間其實是一百到279這麽多，所以如果是這種情況的話，這個程序的這些邏輯地址和它最終存放的物理地址就會出現對應不上的情況。比如説我們的指令零是要給x這個變量進行初始化，但是這個指令指明了x這個變量的值它是要寫到地址為79的那個内存單元當中的，所以如果CPU執行這條指令的話，***

***![1089139-20190723134131467-1297337101.png][]***

***它就會把x的值10把它寫在上面的這個地方，79這個地址所對應的内存單元裏。而這上面的這一片内存空間，極有可能是分配給其他進程的，所以也就意味著本來是這個進程它自己的數據然而它强行往其他進程的那個地址空間裏去寫入了自己的數據。那這顯然是一個危險的并且應該被阻止的一種行爲。而事實上在這個例子當中，我們期待的x這個變量的正確的存放位置，應該是從它的這個起始位置開始往後79個單位這樣的一個内存單元裏，也就是179這個地址所對應的内存單元當中。如果x的值寫在這兒，那就是沒問題的。相信大家對邏輯地址和物理地址應該有一個比較直觀的體會了。總之我們的程序它編譯鏈接等等之後，所形成的這些指令當中一般來説使用的是邏輯地址，也就是相對地址。而這個程序最終被裝到内存的什麽位置，這個其實是我們沒辦法確定的，所以在内存管理這個章節當中有一個很重要的我們需要解決的問題就是如何把這些指令當中所指明的這些邏輯地址把它轉換為最終的物理地址、正確的物理地址。那這個小節當中我們會介紹三種策略來解決這個地址轉換的問題。這三種策略分別是絕對裝入、可重定位裝入（靜態重定位）和動態運行時裝入（動態重定位）。那我們會依次來看一下這三種策略是怎麽解決這個問題的。***

***![1089139-20190723135424549-1542429346.png][]***

***首先來看第一種策略，絕對裝入。所謂的“絕對裝入”就是指，如果我們能夠在程序放入内存之前就知道這個程序會從哪個位置開始存放，那在這種情況下我們其實就可以讓編譯程序把各個變量存放的那些地址直接把它修改成一個正確的一個絕對地址。那還是以剛才的那個例子為例。比如說我們先前就已經知道了我們的那個裝入模塊它是要從地址為100的地方開始存放的，那麽按照之前我們的介紹來説，這個裝入模塊它裏面所使用到的這些地址都是相對地址，但是如果我們知道它是從100這個地址開始裝入的，***

***![1089139-20190723152957442-842855987.png][]***

***那其實在編譯的時候就可以由編譯器把它改爲正確的地址。比如按照之前的分析我們知道，x那個變量它正確的存放地址應該是179。所以接下來我們把這個裝入模塊從起始地址為100的這個地方開始裝入，那麽當這個程序運行的時候就可以把它的這些變量存放到一個正確的位置了，所以這是第一種方式。在編譯的那個時候，就把邏輯地址轉換成最終的物理地址。但是有一個前提就是我們需要知道我們的裝入模塊它會裝到内存的哪個位置，從什麽地方開始裝。所以這種方式的靈活性其實很差，它只適用於單道程序的環境，也就是早期的還沒有操作系統的那個階段，使用的就是這樣的一種方式。大家可以想一下，如果采用絕對裝入這種方式的話，那麽假設我的這個可執行文件此時要運行在另外一臺電腦當中，而另一臺電腦當中又不能讓它從100這個位置開始存放，那是不是就意味著這個程序換一臺電腦它就不能執行了，所以這種方式它的靈活性是特別低的。***

***![1089139-20190723154205054-997356925.png][]***

***第二種裝入方式叫做可重定位裝入，又叫靜態重定位方式。如果采用這種方式的話，那麽編譯、鏈接最終形成的這個裝入模塊這些指令當中使用的地址依然是從0開始的邏輯地址，也就是相對地址。而把這個地址重定位這個過程是留在了裝入模塊裝入内存的時候進行。比如說這個裝入模塊裝到内存裏之後，它的起始物理地址是100，那麽如果我們采用的是靜態重定位這種方式的話，就意味著在這個程序裝入内存的時候，我們同時還需要把這個程序當中所涉及的所有的這些和地址相關的參數都把它進行加100的操作。比如說指令0我們就需要把它加100，然後指令1也對79這個内存單元進行了操作，所以這個地址我們也需要把它加100。所以靜態重定位這種方式就是在我們的程序裝入内存的時候再進行這個地址的轉換。那這種方式的特點是我們給這個作業分配的這些地址空間必須是連續的，并且這個作業必須一次全部裝入内存。也就是說在它執行之前就必須給它分配它所需要的全部的内存空間。難道還可以只分配它所需要的部分空間嗎？那這個問題大家在學習了之後的虛擬存儲技術之後就會有更深入的了解。并且這個地方其實也不是特別重要。那靜態重定位這種方式它還有一個特點就是，在這個程序運行期間它是不可以移動的。這個很好理解，因爲我們的這些指令當中已經寫死了我們具體要操作那個物理地址到底是多少。如果這個程序這個進程相關的這一系列的數據發生了移動的話，那麽這個地址的指向又會發生錯誤。所以這是靜態重定位這種方式的一個局限性。***

***![1089139-20190723165041715-218193254.png][]***

***那最後我們來看一下現代的系統使用的這種地址轉換的機制，叫做動態重定位，又叫動態運行時裝入。那如果采用的是這種方式的話，程序經過編譯鏈接最後形成的裝入模塊當中，它這些指令所使用的其實也是邏輯地址也就是相對地址。并且這個可執行文件這個程序在裝入内存的時候，它們的這個指令當中所使用的同樣還是邏輯地址。如果一個系統支持這種動態重定位方式的話，那這個系統當中還需要設置一個專門的一個寄存器叫做重定位寄存器。重定位寄存器當中存放了這個進程，或者說這個作業它在内存當中的起始地址是多少，比如說我們的這個程序這個進程它是從起始地址為100的這個地方開始存放的，所以重定位寄存器當中我們就存放它的起始地址100。而當CPU在執行相應的這些指令的時候，比如說它在執行指令0的時候，這個指令0是讓他往地址為79的存儲單元當中寫入x這個變量的初始值10。CPU在對一個内存地址進行訪問的時候，它會做這樣的事情。它把邏輯地址和重定位寄存器當中存放的這個起始地址進行一個相加的操作，然後加出來的這個地址才是最終它可以訪問的地址。所以經過這樣的一步處理它就知道，指令0是讓它往地址為179的這個地方寫入數據10。那很顯然如果采用這種方式的話，我們想讓進程的數據在運行的過程當中發生移動是很方便的。比如說我們把這個進程的數據把它移到從200開始的話，那很簡單。我們只需要把重定位寄存器的值再修改成200就可以了，所以動態重定位方式有很多很多的優點。***

***![1089139-20190723175715402-2141167682.png][]***

***它可以把程序分配到不連續的存儲區。那不連續的分配這個現在先不展開，經過后续的學習大家會有更深入的理解，這兒先簡單提一下。那這些内容現在还可能都看不懂，我们在学习了之后的虚拟存储管理之后就可以对这个特性有更深入的理解了。那这个地方我们也暂时不展开，把这个点的理解往后挪一挪。***

***![1089139-20190723181428448-814778709.png][]***

***好的那么刚才我们介绍了内存的基本知识，介绍了内存的地址，介绍了什么叫逻辑地址什么叫物理地址，并且也介绍了三种装入方式来解决了逻辑地址到物理地址的转换这样的一个过程。那接下来我们再从一个更宏观更全局的这样的一个角度再来看一下我们从写程序到程序运行它所经历的步骤。目标模块文件在C语言里就是.o文件。并且这些目标模块当中其实已经包含了这些代码所对应的那些指令了，而这些指令的编址，都是一个逻辑地址也就是相对地址。每一个模块的编址都是从逻辑地址0开始的。所以经过了编译之后我们就把高级语言翻译成了与它们等价的机器语言。只不过每一个模块的逻辑地址的编址都是相互独立的，都是从0开始的。那接下来的一步叫做链接。这一步做的事情就是把这些目标模块都给组装起来，形成一个完整的装入模块。而在Windows电脑当中，所谓的装入模块就是我们很熟悉的.exe文件，也就是可执行文件。把这些目标模块链接起来之后，所形成的装入模块，就有一个完整的逻辑地址。当然在链接这一步，除了我们自己编写的这些目标模块需要链接以外，还需要把它们所调用到的一些库函数比如说printf啊之类的这些函数，也给链接起来，把它形成一个完整的装入模块。那有了装入模块或者说有了这个可执行文件之后，我们就可以让这个程序开始运行了。那程序要运行首先要做的事情就是我们刚才一直强调的那个过程，就是需要把这个装入模块装入内存当中，并且当它装入内存之后就确定了这个进程它所对应的实际的物理地址到底是多少。所以这就是我们从写程序到程序运行的一个完整的流程。那之前我们一直强调的是，装入这个步骤怎么完成，三种装入的策略可以实现逻辑地址到物理地址的转换。那接下来我们要介绍的是三种链接的方式，也就是这一步也有三种方法。***

***![1089139-20190723183458089-2077023584.png][]***

***第一种链接方式叫做静态链接，就是指在程序运行之前就把这些一个一个的目标模块把它们链接成一个完整的可执行文件，也就是装入模块，之后便不再拆开，就是刚才我们所提到的这种方式。也就是说在形成了这个装入模块之后，就确定了这个装入模块的完整的逻辑地址。***

***![1089139-20190723214931745-765556194.png][]***

***那第二种链接方式叫做装入式动态链接，就是说这些目标模块不会先把它们链接起来，而是当这些目标模块放入内存的时候才会进行链接这个动作。***

***![1089139-20190723215039929-1356882695.png][]***

***也就是说采用这种方式的话，这个进程的完整的逻辑地址是一边装入一边形成的。***

***![1089139-20190723214855823-1174357121.png][]***

***那第三种方式叫做运行时动态链接，如果采用这种方式的话那么只有我们需要用到某一个模块的时候才需要把这个模块调入内存。比如说刚开始是main函数运行，那么我们就需要把目标模块1先放到内存当中，然后执行的过程当中可能又发现main函数需要调用到a这个函数，所以我们需要把目标模块2也把它放到内存当中，并且把它装入的时候同时进行一个链接的工作。那如果说b这个函数在整个过程当中都用不到的话，那目标模块3我们就可以不装入内存。所以采用这种方式很显然它的这个灵活性要更高，并且用这种方式可以提升对于内存的利用率。***

***![1089139-20190723220124686-1231486647.png][]***

***而一个存储单元可以存放多少数据，这个我们需要看这个计算机它到底是按字节编址还是按字编址。如果是按字节编址的话，那么一个存储单元就是存放一个字节，也就是一个大B一个Byte。那内存地址其实就是给这些存储单元的一个编号，CPU可以根据内存地址这个参数来找到正确的存储单元。那之后我们又简单地介绍了指令工作的原理。一条机器指令由操作码和一些参数组成。操作码给CPU指明了你现在需要干一些什么事情，而参数指明了你现在需要怎么干。而这个参数当中可能会包含地址参数，而一般来说这个指令中所包含的地址参数指的都是逻辑地址也就是相对地址。所以为了让这个指令正常地工作，我们就需要完成从逻辑地址到物理地址的一个转换。那为了完成逻辑地址到物理地址的转换，我们又介绍了三种装入方式，分别是绝对装入、可重定位装入和动态运行时装入。其中可重定位装入又称作为静态重定位，而动态运行时装入又称为动态重定位。这三种装入方式是考研当中比较喜欢考查的内容。***

***![1089139-20190723222028995-675787367.png][]***

***那最后我们还介绍了从我们程序员写程序到最后的程序运行需要经历哪些步骤。首先是要编辑源代码文件，然后源代码文件经过编译形成若干的目标模块。目标模块经过链接之后形成装入模块，最后再把装入模块装入到内存。这个程序就可以开始正常地运行了。那我们还介绍了三种链接的方式分别是静态链接、装入时动态链接和运行时动态链接。其实经过刚才的讲解我们能够体会到，链接这一步就是要把各个目标模块的那些逻辑地址，把它们组合起来形成一个完整的逻辑地址，所以链接这一步其实就是确定这个完整的逻辑地址这样的一个步骤。而装入这一步又是确定了最终的物理地址，这个小节的内容其实考查的频率很低，只不过是为了让大家更深入地理解之后的内容所以才进行了一些补充。***

***![1089139-20190723230951794-403026333.png][]***

![1089139-20190723233004866-6548088.png][]

![1089139-20190723233029737-1331552331.png][]

***我们知道操作系统它作为系统资源的管理者，当然也需要对系统当中的各种软硬件资源进行管理，包括内存这种资源。那么操作系统在管理内存的时候需要做一些什么事情呢？我们知道各种进程想要投入运行的时候，需要先把进程相关的一些数据放入到内存当中，就像这个样子。那么内存当中，有的区域是已经被分配出去的，而有的区域是还在空闲的。操作系统应该怎么管理这些空闲或者非空闲的区域呢？另外，如果有一个新进程想要投入运行，那么这个进程相关的数据需要放入内存当中。但是如果内存当中有很多个地方都可以放入这个进程相关的数据，那这个数据应该放在什么位置呢？这也是操作系统需要回答的问题。第三，如果说有一个进程运行结束了，那么这个进程之前所占有的那些内存空间，应该怎么被回收呢？那所有的这些都是操作系统需要负责的问题。因此，内存管理的第一件事就是要操作系统来负责内存空间的分配与回收。那内存空间的分配与回收这个问题比较庞大，现在暂时不展开细聊，之后还会有专门的小节进行介绍。***

***![1089139-20190724082642980-1816864951.png][]***

***计算机当中也经常会遇到实际的内存空间不够所有的进程使用的问题。所以操作系统对内存进行管理，也需要提供某一种技术，从逻辑上对内存空间进行扩充，也就是实现所谓的虚拟性，把物理上很小的内存拓展为逻辑上很大的内存。那这个问题也暂时不展开细聊，之后还会有专门的小节进行介绍。***

***![1089139-20190724085328977-1433468422.png][]***

***第三个需要实现的事情是地址转换。为了让编程人员编程更方便，程序员在写程序的时候应该只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换，或者说地址重定位这个过程应该由操作系统来负责进行，这样的话程序员就不需要再关心底层那些复杂的硬件细节。所以内存管理的第三个功能就是应该实现地址转换。就是把程序当中使用的逻辑地址，把它转换成最终的物理地址。那么实现这个转换的方法，咱们在上个小节已经介绍过，***

***![1089139-20190724090046951-785152155.png][]***

***就是用三种装入方式分别是绝对装入、可重定位装入和动态运行时装入。绝对装入是在编译的时候就产生了绝对地址或者说在程序员写程序的时候直接就写了绝对地址。那么这种装入方式只在单道程序阶段才使用。但是单道程序阶段其实暂时还没有产生操作系统，所以这个地址转换其实是由编译器来完成的，而不是由操作系统来完成的。那第二种方式叫做可重定位装入，或者叫静态重定位，就是指在装入的时候把逻辑地址转换为物理地址，那这个转换的过程是由装入程序负责进行的。那装入程序也是操作系统的一部分。那这种方法一般来说是用于早期的多道批处理操作系统当中。那第三种装入方式叫做动态运行时装入或者叫动态重定位，就是运行的时候才把逻辑地址转换为物理地址，当然这种转换方式一般来说需要一个硬件——重定位寄存器的支持。而这种方式一般来说就是现代操作系统采用的方式，咱们之后在学习页式存储还有段式存储的时候会大量地接触这种动态运行时装入的方式。所以说操作系统一般会用可重定位装入和动态运行时装入这两种方式实现从逻辑地址到物理地址的转换。而采用绝对装入的那个时期暂时还没有产生操作系统。那这就是内存管理需要实现的第三个功能——地址转换。***

***![1089139-20190724103359751-716886403.png][]***

***第四个功能叫内存保护。就是指操作系统要保证各个进程在各自存储空间内运行，互不干扰。***

***![1089139-20190724114204010-533788882.png][]***

***我们直接用一个图让大家更形象地理解。在内存当中一般来说会分为操作系统使用的内存区域还有普通的用戶程序使用的内存区域。那各个用戶进程都会被分配到各自的内存空间，比如说进程1使用的是这一块内存區域，进程2使用的是这一块内存区域。那如果说进程1想对操作系统的内存空间进行访问的话，很显然这个行为应该被阻止。如果进程1可以随意地更改操作系统的数据，那么很明显会影响整个系统的安全。另外如果进程1想要访问其他进程的存储空间的话，那么显然这个行为也应该被阻止。如果进程1可以随意地修改进程2的数据的话，那么显然进程2的运行就会被影响，这样也会导致系统不安全。所以进程1只能访问进程1自己的那個内存空间，所以这就是内存保护想要实现的事情。让各个进程只能访问自己的那些内存空间，而不能访问操作系统的也不能访问别的进程的空间。那我們可以采用這樣的方式來進行内存保護，就是在CPU當中設置一對上限寄存器和下限寄存器，分別用來存儲這個進程的内存空間的上限和下限。那如果进程1的某一条指令想要访问某一个内存單元的時候，CPU會根據指令當中想要訪問的那個内存地址和上下限寄存器的這兩個地址進行對比。只有在這兩個地址之間才允許進程1訪問，因爲只有這兩個地址之間的這個部分才屬於進程1的内存空間。那這是第一種方法，可以設置一對上下限寄存器。***

***![1089139-20190724115706891-1625705872.png][]***

***第二種方法我們可以采用重定位寄存器和界地址寄存器來判斷此時是否有越界的嫌疑。那麽重定位寄存器又可以稱爲基址寄存器，界地址寄存器又稱爲限長寄存器。那重定位寄存器的概念咱們在上個小節已經接觸過，就是在動態運行時裝入那種方式裏，我們需要設置一個重定位寄存器，來記錄每一個進程的起始物理地址。界地址寄存器又可以稱爲限長寄存器，就是用來存放這個進程的最大邏輯長度的。比如說像進程1它的邏輯地址是0~179，所以界地址寄存器當中應該存放的是它的最大的邏輯地址也就是179。而重定位寄存器的話應該存放這個進程的起始物理地址，也就是100。那麽假如現在進程1想要訪問邏輯地址為80的那個内存單元的話，首先這個邏輯地址會和界地址寄存器當中的這個值進行一個對比。如果說沒有超過界地址寄存器當中保存的最大邏輯地址的話，那麽我們就認爲這個邏輯地址是合法的。如果超過了，那麽會抛出一個越界異常。那沒有越界的話，邏輯地址會和重定位寄存器的這個起始物理地址進行一個相加，最終就可以得到實際的想要訪問的物理地址也就是180。***

***![1089139-20190724121027993-1160703960.png][]***

***那这个小节中我们学习了内存管理的整体框架。内存管理总共需要实现四个事情，内存空间的分配与回收，内存空间的扩充以实现虚拟性，另外还需要实现逻辑地址到物理地址的转换。那么地址转换一般来说有三种方式，就是上个小节学习的内容——绝对装入、可重定位装入和动态运行时装入。其中绝对装入这个阶段其实是在早期的单道批处理阶段才使用的，这个阶段暂时还没有操作系统产生。而可重定位装入一般用于早期的多道批处理系统，现在的操作系统大多使用的是动态运行时装入。另外呢内存管理还需要提供存储保护的功能，就是要保证各个进程它们只在自己的内存空间内运行，不会越界访问。那一般来说有两种方式，第一种是设置上下限寄存器。第二种方式是利用重定位寄存器和界地址寄存器进行判断。那么重定位寄存器又可以叫做基址寄存器，而界地址寄存器又可以叫做限长寄存器。这两个别名大家也需要注意。那么本章之后内容还会介绍更多的内存空间的分配与回收，还有内存空间的扩充的一些相关策略。那这个小节的内容不算特别重要，只是为了让大家对内存管理到底需要做什么形成一个大体的框架。***

***![1089139-20190724124012959-911275835.png][]***

![1089139-20190724140151836-94710736.png][]

***那在之前的小節中我們已經學習到了操作系統對内存進行管理需要實現這樣四個功能。那地址轉換和存儲保護是上個小節詳細介紹過的。那這個小節我們會介紹兩種實現内存空間的擴充的技術——覆蓋技術和交換技術，那虛擬存儲技術會在之後用更多的專門的視頻來進行講解。***

***![1089139-20190724140610741-691379200.png][]***

***一般來説都很少有低於100MB字節的這種程序。所以可想而知1MB字節的大小很多時候應該是不能滿足這些程序的運行的。那么后来人们为了解决这个问题就引入了覆盖技术，就是解决程序大小超过物理内存总和的问题。比如说一个程序本来需要这么多的内存空间，但实际的内存大小又只有这么多。那怎么办呢？覆盖技术的思想就是要把程序分成多个段，或者理解为就是多个模块。然后常用的段就需要常驻内存，不常用的段只有在需要的时候才需要调入内存。那内存当中会分一个“固定区”和若干个“覆盖区”，常用的那些段需要放在固定区里，并且调入之后就不再调出，除非运行结束，这是固定区的特征。那不常用的段就可以放在“覆盖区”里，只有需要的时候才需要调入内存，也就是调入内存的覆盖区，然后用不到时候就可以调出内存。***

***![1089139-20190724144337075-1701750960.png][]***

***A这个模块会依次调用B模块和C模块。注意是依次调用，也就是说B模块和C模块只可能被A这个模块在不同的时间段调用，不可能是同时访问B和C这两个模块。另外由于B模块和C模块不可能同时被访问，也就是说在同一个时间段内内存当中要么有B要么有C就可以了，不需要同时存在B和C这两个模块。所以我们可以让B和C这两个模块共享一个覆盖区，那这个覆盖区的大小以B和C这两个模块当中更大的这个模块为准，也就是10KB。因为如果我们把这个覆盖区设为10KB的话，那既可以存的下C也可以存的下B。那同样的，D、E、F这几个模块也不可能同时被使用。所以这几个模块也可以像上面一样共享一个覆盖区，覆盖区1，那它的大小就是按它们之间最大的这个也就是D模块的大小12KB来计算。所以如果说我们的程序有一个明显的这种调用结构的话，那么我们可以根据它这种自身的逻辑结构，让这些不可能被同时访问的程序段共享一个覆盖区。那只有其中的某一个模块被使用的时候，那这个模块才需要放到覆盖区里。所以采用了覆盖技术之后，在逻辑上看这个物理内存的大小是被拓展了的。不过这种技术也有一个很明显的缺点，因为这个程序当中的这些调用结构操作其实系统肯定是不知道的，所以程序的这种调用结构必须由程序员来显性地声明，然后操作系统会根据程序员声明的这种调用结构或者说覆盖结构，来完成自动覆盖。所以这种技术的缺点就是对用户不透明，增加了用户编程的负担。因此，覆盖技术现在已经很少使用了，它一般就只用于早期的操作系统中，现在已经退出了历史的舞台。***

***![1089139-20190724150612369-64992430.png][]***

***所以其实采用这种技术（交换技术/对换技术）的时候，进程是在内存与磁盘或者说外存之间动态地调度的。那之前咱們其实已经提到过一个和交换技术息息相关的知识点，咱们在第二章讲处理机调度的时候，讲过一个处理机调度层次的概念，分为高级调度、中级调度和低级调度。那其中中级调度就是爲了實現交換技術而使用的一種調度策略。就是說本來我們的内存當中有很多進程正在并發地運行，那如果某一個時刻突然發現内存空間緊張的時候我們就可以把其中的某些進程把它放到暫時換出外存。***

***![1089139-20190724160621084-1485215526.png][]***

***而進程相關的PCB會保留在内存當中，并且會插入到所謂的挂起隊列裏。那一直到内存空間不緊張了，内存空間充足的時候又可以把這些進程相關的數據再給換入内存。那爲什麽進程的PCB需要常駐内存呢？因爲進程被換出外存之後其實我們必須要通過某種方式記錄下來這個進程到底是放在外存的什麽位置，那這個信息也就是進程的存放位置這個信息，我們就可以把它記錄在與它對應的這些PCB當中。那操作系統就可以根據PCB當中記錄的這些信息，對這些進程進行管理了，所以進程的PCB是需要常駐内存的。***

***![1089139-20190724160836024-1742135568.png][]***

***那麽中級調度或者説内存調度，其實就是在交換技術當中，選擇一個處於外存的進程把它換入内存這樣一個過程。那講到這個地方大家也需要再回憶一下低級調度和高級調度分別是什麽。***

***![1089139-20190724161120344-37017275.png][]***

***那既然提到了挂起我們就再來回憶一下和挂起相關的知識點。暫時換出外存等待的那些進程的狀態稱之爲挂起狀態或者簡稱挂起態。那挂起態又可以進一步細分為就緒挂起和阻塞挂起兩種狀態。在引入了這兩種狀態之後我們就提出了一種叫做進程的七狀態模型。那如果一個本來處於就緒態的進程被換出了外存，那這個進程就處於就緒挂起態。如果一個本來處於阻塞態的進程被換出外存的話，那麽這個進程就處於阻塞挂起態。那七狀態模型相關的知識點咱們在第二章當中已經進行過補充，這兒就不再贅述。那大家可以再結合這個圖回憶一下這些狀態之間的轉換是怎麽進行的，特別是中間的這三個最基本的狀態之間的轉換。所以采用了交換技術之後，如果說某一個時刻内存裏的空間不夠用了，那麽我們可以把内存中的某一些進程數據暫時換到外存裏，再把某一些更緊急的進程數據放回内存，所以交換技術其實也在邏輯上擴充了内存的空間。***

***![1089139-20190724162821015-1438078101.png][]***

***在現代計算機當中，外存一般來説就是磁盤。那具有對換功能或者說交換功能的操作系統當中，一般來説會把磁盤的存儲空間分爲文件區和對換區這樣兩個區域。文件區主要是用來存放文件的，主要是需要追求存儲空間的利用率。所以在對文件區，一般來説是采用離散分配的方式。而這個地方一會兒再做解釋。那對換區的空間一般來説只占磁盤空間的很小的部分，注意被換出的進程數據一般來説就是存放在對換區當中的，而不是文件區。那由於對換區的這個換入換出速度會直接影響到各個進程并發執行的這種速度，所以對於對換區來説我們應該首要追求換入換出的速度。因此對換區通常會經常采用連續分配的方式。那這個地方大家理解不了暫時沒有關係，咱們在第四章文件管理的那個章節會具體地再進一步學習什麽是對換區什麽是文件區，并且到時候大家就能夠理解爲什麽離散分配方式可以更大地提高存儲空間的利用率，而連續分配方式可以提高換入換出的速度。那這個地方大家只需要理解一個結論，對換區的I/O速度或者説輸入輸出的速度，是要比文件區更快的。所以我們的進程數據被換出的時候，一般是放在對換區，換入的時候也是從對換區再換回内存。***

***![1089139-20190724165034199-279126842.png][]***

***一般來説交換會發生在系統當中有很多進程在運行并且内存吃緊的時候。那在這種時候，我們可以選擇換出一些進程來騰空内存空間那一直到系統負荷明顯降低的時候就可以暫停換出。比如說如果操作系統在某一段時間發現許多進程運行的時候都經常發生缺頁，那這就説明内存的空間不夠用，所以這種時候就可以選擇換出一些進程來騰空一些内存空間。那如果說缺頁率明顯下降，也就是說看起來系統負荷明顯降低了，我們就可以暫停換出進程了。那這個地方涉及到之後的小節會講到的缺頁還有缺頁率這些相關的知識點。這兒理解不了沒有關係，大家能夠有個印象就可以了。***

***![1089139-20190724172639892-608547400.png][]***

***首先我們可以考慮優先換出一些阻塞的進程。因爲處於就緒態的進程，其實是可以投入運行的。而處於阻塞態的進程，即使是在内存當中反正它暫時也運行不了了，所以我們可以優先把阻塞進程調出換到外存當中。第二，我們可以考慮換出優先級比較低的進程。那這個不用解釋，很好理解。第三，如果我們每次都是換出優先級更低的進程的話，那麽就有可能導致優先級低的進程剛被調入内存很快又被換出的問題。那這就有可能會導致優先級低的進程飢餓的現象。所以有的系統當中爲了防止這種現象，會考慮進程在内存當中的駐留時間。如果一個進程在内存當中駐留的時間太短，那這個進程就暫時不會把它換出外存。那這個地方再强調一點，PCB是會常駐内存的，并不會被換出外存。所以其實所謂的換出進程，并不是把進程相關的所有的數據一個不漏的全部都調到外存裏，操作系統爲了保持對這些換出進程的管理，那PCB這個信息還是需要放在内存當中。那麽這就是交換技術。***

***![1089139-20190724182457672-1887542779.png][]***

***![1089139-20190724192229729-80545729.png][]***

***那这个小节我们学习了覆盖技术和交换技术相关的知识点。那这两个知识点一般来说只会在选择题当中进行考查。大家只要能够理解这两种技术的思想就可以了。那么可能稍微需要记忆一点的就是，固定区和覆盖区相关的这些知识点。在固定区当中的程序段，在运行过程当中是不会被调出的。而在覆盖区当中的程序段，在运行过程当中是有可能会根据需要进行调入调出的。另外，如果考查了覆盖技术的话，那么很有可能会把覆盖技术的缺点作为其中的某一个选项进行考查。那在讲解交换技术的过程当中我们补充了文件区和对换区相关的知识点，这些会在第四章中进行进一步的学习。那这个地方大家只需要知道换出的进程的数据一般来说是放在磁盘的对换区当中的。那最后我们再来看一下覆盖与交换这两种技术的一个明显的区别。其实覆盖技术是在同一个程序或者进程当中进行的。那相比之下交换技术是在不同进程或作业之间进行的，而暂时运行不到的进程可以调出外存。那比较紧急的进程可以优先被再重新放回内存。***

***![1089139-20190724191956678-1393996527.png][]***

***![1089139-20190724185921502-66146851.png][]***

![1089139-20190724192544443-466713429.png][]

***在之前的学习中我们知道，操作系统对内存进行管理，需要实现这样四个事情。那么内存空间的扩充，地址转换和存储保护，这是之前的小节介绍过的内容。从这个小节开始我们会介绍内存空间的分配与回收应该怎么实现。我们在这个小节中会先介绍连续分配管理方式，分别是单一连续分配，固定分区分配和动态分区分配。我们会按从上至下的顺序依次讲解。那么这儿需要注意的是，所谓的连续分配和非连续分配的区别在于，连续分配是指，系统为用户进程分配的必须是一个连续的内存空间。而非连续分配管理方式是指系统为用户分配的那些内存空间不一定是连续的，可以是离散的。***

***![1089139-20190724193325416-1077871430.png][]***

***那么我们先来看单一连续分配方式。采用单一连续分配方式的系统当中，会把内存分为一个系统区和一个用户区。那系统区就是用于存放操作系统相关的一些数据，用户区就是用于存放用户进程或者说用户程序相关的一些数据。不过需要注意的是，采用单一连续分配方式的这种系统当中，内存当中同一时刻只能有一道用户程序。也就是说它并不支持多道程序并发运行，所以用户程序是独占整个用户区的，不管这个用户区有多大。比如说一个用户进程或者说用户程序，它本来只需要这么大的内存空间。***

***![1089139-20190724213647740-1357067149.png][]***

***那当它放到内存的用户区之后，用户区当中其他那些空闲的区间其实也不会被分配给别的用户程序。所以说是整个用户程序独占整个用户区的这种存储空间的。所以这种方式其实优点很明显就是实现起来很简单，并且没有外部碎片。那外部碎片这个概念我们在讲到动态分区分配的时候再补充，这儿先有个印象。那由于整个系统当中同一时刻只会有一个用户程序在运行，所以采用这种分配方式的系统当中不一定需要采用内存保护。注意只是不一定，有的系统当中它也会设置那种越界检查的一些机制。但是像早期的个人操作系统，微软的DOS系统，就没有采用这种内存保护的机制。因为系统中只会运行一个用户程序，那么即使这个用户程序出问题了，那也只会影响用户程序本身，或者说即使这个用户程序越界把操作系统的数据损坏了，那这个数据一般来说也可以通过重启计算机就可以很方便地就进行修复。所以说采用单一连续分配方式的系统当中，不一定采取内存保护，那这也是它的优点。那另一方面，这种方式的缺点也很明显，就是只适用于单用户、单任务的操作系统，它并不支持多道程序并发运行，并且这种方式会产生内部碎片。那所谓的内部碎片，就是指我们分配给某一个进程或者说程序的内存区间当中，如果有某一个部分没有被用上，那这就是所谓的内部碎片。像这个例子当中，本来整个用户区都是分配给这个用户进程A的，但是有这么大一块它是空闲的，暂时没有利用起来。那本来给这个进程分配了，但是这个进程没有用上的这一部分内存区域就是所谓的内部碎片。所以这种方式也会导致存储器的利用率很低。那这是单一连续分配方式。***

***![1089139-20190724220002673-759406393.png][]***

***![1089139-20190724214915354-1223599589.png][]***

***多道程序技术就是可以让各个程序同时装入内存，并且这些程序之间不能相互干扰，所以人们就想到了把用户区划分成了若干个固定大小的分区，并且在每一个分区内只能装入一道作业。也就是说每一道作业或者说每一道程序它是独享其中的某一个固定大小的分区的。那这样的话就形成了最早的可以支持多道程序的内存管理方式。那固定分区分配可以分为两种，一种是分区大小相等，另外一种是分区大小不等。如果说采用的是分区大小相等的策略的话，系统会把用户区的这一整片的内存区间分割为若干个固定大小并且大小相等的区域。***

***![1089139-20190724223659784-374031985.png][]***

***比如说每个区域十个字节，像这样子。那如果说采用的是分区大小不相等的这种策略的话，系统会把用户区分割为若干个大小固定但是大小又不相等的分区，比如说像这个样子。那这两种方式各有各的特点，如果说采用的是分区大小相等的这种策略的话，很显然会缺乏灵活性。比如说一些小的进程它可能只需要占用很小的一部分内存空间，但是由于每个分区只能装入一道作业，所以一个很小的进程又会占用一个比较大的、很多余的一个分区。那如果说一个有一个比较大的进程进入的话，那么如果这些分区的大小都不能满足这个大进程的需求，那么这个大进程就不能被装入这个系统，或者说只能采用覆盖技术，在逻辑上来拓展各个分区的大小。但这又显然又会增加一些系统开销。所以说分区大小相等的这种情况是比较缺乏灵活性的，不过这种策略即使在现代也是有很广泛的用途的。那由于这n个炼钢炉本来就是相同的对象，所以对这些相同的对象进行控制的程序当然也是相同的程序。所以如果采用这种把它分割为n个大小相等的区域来分别存放n个控制程序，让这n个控制程序并发执行，并发地控制各个炼钢炉的话，那在这种场景下的应用就是很适合的。那如果分区大小不等的话，灵活性会有所增加。比如说小的进程我们可以给它分配一个小的分区，而大的进程可以给它分配一个大的分区。那一般来说可以先估计一下系统当中会出现的大作业、小作业分别到底有多少。然后再根据大小作业的比例来对这些大小分区的数量进行一个划分。比如说可以划分多个小分区，适量的中等分区、然后少量的大分区。***

***![1089139-20190724230132468-821402980.png][]***

***那接下来我们再考虑下一个问题，操作系统应该怎么记录内存当中各个分区的空闲或者分配的这些情况呢？那一般来说我们可以建立一个叫做分区说明表的一个数据结构，用这个数据结构对各个分区进行管理。比如说如果系统当中内存的情况是这个样子，那么我们可以给它建立一个对应的分区说明表。那每一个表项会对应其中的某一个分区，那每一个表项需要包含当前这个分区的大小还有这个分区的起始地址还有这个分区是否已经被分配的这种状态。那像这样一张表其实我们可以建立一个数据结构，数据结构当中有这样一些属性，然后把这个用这个数据结构组成一个数组或者组成一个链表来表示这样一个表。那如果学过数据结构的同学这儿应该不难理解。那操作系统根据这个数据结构就可以知道各个分区的使用情况，如果说一个用户程序想要装入内存的话，操作系统就可以来检索这个表，然后找到一个大小能够满足并且没有被分配出去的分区，然后把这个分区分配给用户程序。之后再把这个分区对应的状态改成已分配的状态就可以了。那么固定分区分配实现起来其实也不算复杂，并且使用这种方式也不会产生外部碎片。那么外部碎片这个概念咱们再往后拖一拖，下一个分配方式当中会进行讲解。但是这种方式也有很明显的缺点。如果说一个用户程序太大了，大到没有任何一个分区可以直接满足它的大小的话，那么我们只能通过覆盖技术来解决这个分区大小不够的问题。但是如果采用了覆盖技术，那就意味着需要付出一定的代价，会降低整个系统的性能。另外，这种分配方式很显然也会产生内部碎片，比如说有一个用户程序它所需要的内存空间是10MB，那么扫描了这个表之后会发现，只有分区6可以满足10MB这么大的需求，所以这个用户程序就会被装到分区6里。但是由于这个用户程序会独占整个分区6，所以分区6总共有12MB，那么就有两兆字节的空间是分配给了这个程序，那这个程序又用不到的。那这一部分就是所谓的内部碎片。所以固定分区分配是会产生内部碎片的，因此它的内存利用率也不是特别高。***

动态动态***![1089139-20190725074104912-1129210966.png][]***

***那么，为了解决这个问题人们又提出了动态分区分配的策略。动态分区分配又可以称作可变分区分配，这种分配方式并不会像之前固定分区分配那样预先划分内存区域。而是在进程装入内存的时候才会根据进程的大小动态地建立分区。而每一个分区的大小会正好适合进程所需要的那个大小。所以和固定分区分配不同，如果采用动态分区分配的话，系统当中内存分区的大小和数目是可以改变的。那我们来看一个例子。比如说一个计算机的内存大小总共是64MB字节，然后系统区会占8MB字节，那用户区就是56MB字节。刚开始一个用户进程1到达，它总共占用了20MB字节的分区，之后一个用户进程2到达，占用了14MB字节的分区，用户进程3到达，占用了18MB字节的分区。那么56MB字节的用户区总共只会占4MB字节的空闲分区。那么系统中这些分区的大小和数量是可变的，并且有些分区是已经被分出去的，有些分区又是没有被分出去的。操作系统应该用什么样的数据结构来记录这个内存的使用情况呢？这是我们之后要探讨的第一个问题。那再来看第二个问题，***

![1089139-20190725081840452-947576833.png][]

***如果此时占有14MB字节的进程2已经运行结束了，并且被移出了内存，******那么内存当中就会有这样一片14MB字节的空闲区间，那此时如果有一个新进程到达，并且这个进程需要4兆字节的内存空间。那这一片空闲区间是14MB，这一片空闲区间是4MB。那到底应该放这一片还是放下面这一片呢？这又是第二个问题。当我们的内存当中有很多个空闲分区都可以满足进程的需求的时候，应该把哪个空闲区间分配给那个进程呢？这是第二个问题。***

***![1089139-20190725090751908-823718679.png][]***

***第三个问题，假设此时占18MB字节的进程三运行结束，并且被撤离了内存。那么内存当中就会出现18MB字节的一个新的空闲分区。那这个空闲分区应该怎么处理？是否应该和与它相邻的这些分区进行合并呢？这就是第三个问题，我们应该如何进行分区的分配和回收的操作。那接下来我们依次对这三个问题进行探讨。***

***![1089139-20190725091118461-554699628.png][]***

***先来看第一个问题，操作系统应该用什么样的数据结构记录内存的使用情况？那一般来说会采用两种常用的数据结构，要么是空闲分区表，或者采用空闲分区链。比如某一个时刻系统当中内存的使用情况是这个样子。总共有三个空闲分区，那么如果采用空闲分区表的话，这个表就会有三个对应的表项，每一个表项会对应一个空闲分区，并且每一个表项都需要记录与这个表项相对应的空闲分区的大小是多少，起始地址是多少等等一系列的信息。那如果说没有在空闲分区表当中记录的那些分区当然就是已经被分配出去的。再来看第二种数据结构，空闲分区链。如果采用这种方式的话，那么每一个分区的起始部分和末尾部分，都会分别设置一个指向前面一个空闲分区和指向后面一个空闲分区的指针，就像这个样子。所以就会把这些空闲分区用一个类似于链表的方式把它们链接起来。那每一个空闲分区的大小，还有空闲分区的起始地址，结尾地址等等这些信息，可以统一地把它们放在各个空闲分区的起始部分。所以这是我们可以采用的两种数据结构——空闲分区表和空闲分区链。***

***![1089139-20190725103946931-62930451.png][]***

***那再来看第二个问题，当有很多空闲分区都可以满足需求的时候，到底应该选择哪个空闲分区进行分配呢？假如此时有一个进程5它只需要4兆字节的空间，那么这个空闲分区、这个分区还有这个分区这三个空闲分区都可以满足它这个需求。那我们应该用哪个分区进行分配呢？那由这个问题我们可以引出动态分区分配算法相关的问题。那所谓的动态分区分配算法，就是要从空闲分区表，或者空闲分区链当中，按照某一种规则，选择出一个合适的分区把它分配给此时请求的这个进程或者说作业。那由于这个分配算法对系统性能造成的影响是很大的，所以人们对于这个问题进行了很多的研究。那这个问题我们现在暂时不展开处理，会在下一个小节进行详细的介绍。***

***![1089139-20190725105313342-1324699435.png][]***

***接下来我们再来看第三个问题，如何进行分区的分配与回收？那假设我们采用的是空闲分区表的这种数据结构的话，进行分配的时候需要做一些什么操作呢？那这个地方我们只以空闲分区表为例，其实空闲分区链的操作也是大同小异的。那假如说此时系统当中有这样三块空闲的分区，如果此时有一个进程需要申请四兆字节的内存空间，那假设我们采用了某一种算法，最后决定从这20MB的空闲分区当中摘出四兆分配给这个进程5，***

***![1089139-20190725112126732-1069026196.png][]***

***就像这样。那么我们需要对这个空闲分区表进行一定的处理，那由于这个空闲分区的大小本来就是比此次申请的这块内存区域的大小要更大的。所以即使我们从这个分区当中摘出一部分进行了分配，那么分区的数量依然是不会改变的。所以我们只需要在这个分区对应的那个表项当中，修改一下它的分区大小还有起始地址就可以了。那这是第一种情况。***

***![1089139-20190725123136790-1855541037.png][]***

***再来看第二种情况。还是相同的地址，有一个进程5需要4MB字节。那如果说我们采用了某种分配算法，最后决定把这4MB字节的空闲分区分配给这个进程5，***

***![1089139-20190725124048568-506585841.png][]***

***那么本来这个空闲分区的大小就和此次申请的这个内存空间大小是相同的，所以如果把这个分区、空闲分区全部分配给这个进程的话，那么显然空闲分区的数量会减1，所以我们需要把这个分区对应的这个表项给删除。那如果说我们采用的是空闲分区链的话，那我们就只需要把其中的某一个空闲分区链的结点给删掉，那这是分配的时候可能会遇到的两种情况。***

***![1089139-20190725125009607-462228434.png][]***

***接下来我们再来看进行回收的时候可能会需要做一些什么样的处理？假设此时系统内存中的情况是这样的。那如果采用“空闲分区表”这种数据结构的话，那这个表应该是由两个表项分别对应一个10MB的空闲分区和一个4MB的空闲分区。那假设此时进程4已经运行结束了，我们可以把进程4占用的这4MB字节的空间给回收。那么此时这块回收的区域的后面，有一个相邻的空闲分区，也就是10MB的这块分区，***

***![1089139-20190725125758613-743077124.png][]***

***因此我们把这块内存分区回收之后，我们需要把空闲分区表当中对应的那个表项的分区大小和起始地址也进行一个更新。所以可以看到，如果两个空闲分区相邻的话，那么我们需要把这两个空闲分区进行合二为一的操作。***

***![1089139-20190725130141019-1257283589.png][]***

***再来看第二种情况。假设此时进程三已经运行结束了，那么当进程三占用的这一块分区被回收之后，在它的前面也有一个相邻的空闲分区，***

***![1089139-20190725135625626-2108846864.png][]***

***所以参照刚才的那种思路，我们也需要把这两块相邻的空闲分区进行合二为一的操作。那这和之前的那种情况其实是很类似的。***

***![1089139-20190725135712627-1821486473.png][]***

***再看第三种情况。假设此时进程四已经运行结束，需要把这四兆字节给回收，那么进程四的前面和后面都会有一个相邻的空闲分区。所以本来我们的空闲分区表有三个表项，也就是有三个空闲分区，***

***![1089139-20190725140356203-1077131809.png][]***

***但是当进程四的这块空间被回收之后，需要把这一整块的空间都进行一个合并。所以本来系统中有三个空闲分区，但如果把进程四回收之后就会合并为两个空闲分区。那当然我们也需要修改相应表项的这些分区大小、起始地址等等这一系列的信息。那这第三种情况需要把三个相邻的空闲分区合并为一个。***

***![1089139-20190725141255708-1138075556.png][]***

***再来看第四种情况。假如回收区的前后都没有相邻的空闲分区的话，应该怎么处理。假设此时进程2已经运行结束，那么当进程2的这块内存区间被回收之后，***

***![1089139-20190725151608417-116789934.png][]***

***系统当中就出现了两块空闲分区。所以相应的我们当然也需要增加一个空闲分区表的表项。那通过刚才的这一系列讲解，大家可能会发现，我们对空闲分区表的这种顺序一般来说是采用这种按照起始地址的先后顺序来进行排列的。但是这个并不一定，各个表项的排序我们一般来说需要根据我们采用哪种分区分配算法来确定。比如说有的时候我们按照分区从大到小的顺序排列会比较方便，有的时候我们按照分区大小从小到大进行排列比较方便。当然也有的时候我们就像现在这样按照起始地址的先后顺序来进行排列会比较方便。那这个地方会到下一个小节进行进一步的解释。那到这个地方，我们就回答了之前提出的三个问题，第一个问题我们需要用什么样的数据结构来记录内存的使用情况。一般来说会使用两种数据结构——空闲分区表或者空闲分区链。那第二个问题涉及到动态分区分配算法就会在下一个小节中进行进一步的解释。第三个问题我们讨论了怎么对内存的空间进行分配与回收。进行分配与回收的时候需要对这些数据结构进行什么处理。那特别需要注意的是，在回收的过程中，我们有可能会遇到四种情况。不过本质上我们可以用一句话来进行总结，在进行内存分区回收的时候如果说回收了之后发现有一些空闲分区是相邻的，那么我们就需要把这些相邻的空闲分区全部给合并。***

***![1089139-20190725151427560-1567140390.png][]***

***那接下来我们再来讨论一下动态分区分配关于内部碎片和外部碎片的问题。这儿我们给出了内部碎片和外部碎片的完整的定义，内部碎片是指分配给某个进程的内存区域当中，如果说有些部分没有用上，那么这些部分就是所谓的内部碎片。注意是分配给这个进程但是这个进程没有用上的那些部分。而外部碎片是指内存当中的某些空闲分区由于太小而难以利用。那因为各个进程需要的都是一整片连续的内存区域，所以如果这些空闲的分区太小的话那么任何一个空闲分区都不能满足进程的需求，那这种空闲分区就是所谓的外部碎片。***

***![1089139-20190725155043279-208951317.png][]***

***比如说我们系统当中依次进入了进程1、进程2、进程3它们的大小分别是这样。然后这个时候内存当中只剩下一片空闲的内部区域，就是4M字节这么大。那么此时如果进程2暂时不能运行，***

***![1089139-20190725155334043-546502667.png][]***

***我们可以暂时把它换出到外存当中。那于是这块就有14M字节的空闲区域。***

***![1089139-20190725155729979-1147430726.png][]***

***那接下来进程4到达占用4M字节，***

***![1089139-20190725160045763-1281096227.png][]***

***那这一块就应该是10M字节的大小。之后如果进程1也暂时不能运行，那么我们可以把进程1暂时换出外存。***

***![1089139-20190725160324426-1355755324.png][]***

***于是这个地方可以空出20M字节的连续的空闲区间。***

***![1089139-20190725160538734-829955781.png][]***

***那接下来如果进程2又可以恢复运行了，它再回到内存当中，它又占用了其中的14M字节。***

***![1089139-20190725160700042-1061959230.png][]***

***于是这一块就只剩下6M字节。***

![1089139-20190725164906647-568828220.png][]

***那接下来如果说进程1也就是20M字节的这个进程又可以执行了又想回到内存的话，那么此时会发现内存当中的任何一个区域都已经不能满足进程1的这个需求了。所以这就产生了所谓的外部碎片。这些空闲区间是暂时没有分配给任何一个进程的，但是由于它们都太小了太零碎了所以没办法满足这种大进程的需求。那像这种情况下，其实内存当中总共剩余的内存区间其实是6+10+4，也就是总共有20M字节。也就是说内存当中空闲区间的总和其实是可以满足进程1的需求的。所以在这种情况下，我们可以采用紧凑技术或者是拼凑技术来解决外部碎片的问题。那紧凑技术很简单，***

***![1089139-20190725170224956-1662513984.png][]***

***其实就是把各个进程挪位，***

***![1089139-20190725170424231-1000095656.png][]***

***把它们全部攒到一起，***

***![1089139-20190725170441955-1186852181.png][]***

***然后挪出一个更大的空闲、连续的空闲区间出来。***

***![1089139-20190725170540523-1252365243.png][]***

***这样的话，这块空闲区间就可以满足进程1的需求了。那这个地方大家也可以停下来回忆一下咱们刚才提到的换入换出技术和中级调度相关的一些概念，这是咱们之前讲过的内容。那显然咱们之前介绍的三种装入方式当中，动态重定位的方式其实是最方便实现这些程序或者说进程在内存当中移动位置这件事情的，所以我们采用的应该是动态重定位的方式。另外，紧凑之后我们需要把各个进程的起始地址给修改掉。那进程的起始地址这个信息一般来说是存放在进程对应的PCB当中。当进程要上CPU运行之前，会把进程的起始地址那个信息放到重定位寄存器里，或者叫基址寄存器里。那大家对这些概念还有没有印象呢？***

***![1089139-20190725165944422-624389351.png][]***

***那这个小节我们介绍了三种连续分配管理的分配方式。连续分配的特点就是为用户进程分配的必须是一个连续的内存空间。那么我们分别介绍了单一连续分配、固定分区分配和动态分区分配这三种分配方式。***

***![1089139-20190725171536622-533910199.png][]***

***那之前咱们留下了一个问题，单一连续分配和固定分区分配都不会产生外部碎片。那由于采用这两种分配方式的情况下，不会出现那种暂时没有被分配出去但是又由于这个空闲区间太小而没有办法利用的这种情况，所以这两种分配方式是不会产生外部碎片的。那对于是否有外部碎片还是内部碎片这个知识点经常在选择题当中进行考查，大家千万不能死记硬背，一定要在理解了各种分配方式的规则的这种情况下，能够自己分析到底有没有外部碎片，有没有内部碎片。另外，动态分区分配方式当中对外部碎片的处理“紧凑”技术也是曾经作为选择题的选项进行考查过，这个地方也需要有一些印象。那在回收内存分区的时候我们可能会遇到的这四种情况也是曾经在真题当中考查过所以这个点也需要注意。不过只需要抓住一个它的本质，相邻的空闲区间是需要合并的，我们只要知道这一点就可以了。另外呢我们也需要对空闲分区表和空闲分区链这两种数据结构相关的概念还有它们的原理也要有一个印象。***

***![1089139-20190725172916282-1561245222.png][]***

***在这个小节中我们会学习动态分区分配算法相关的知识点，***

***![1089139-20190725173949836-59563535.png][]***

***那这是我们上小节遗留下来的问题。在动态分区分配方式当中，如果有很多个空闲分区都能够满足进程的需求，那么我们应该选择哪个分区进行分配呢？这是动态分区分配算法需要解决的问题。那考试当中，要求我们掌握的有这样四种算法，首次适应、最佳适应、最坏适应、邻近适应这四种，我们会按从上至下的顺序依次讲解。***

***![1089139-20190725191405171-988726738.png][]***

***首先来看首次适应算法。这种算法的思想很简单，就是每次从低地址部分开始查找，找到第一个能够满足大小的空闲分区。所以按照这种思想，我们可以把空闲分区按照地址递增的次序进行排列，而每一次分配内存的时候我们就可以顺序地查找空闲分区链或者空闲分区表，找到第一个大小能够满足要求的空闲分区进行分配。那这个地方提到了空闲分区链和空闲分区表，这是两种常用于表示动态分区分配算法当中内存分配情况的数据结构。那如果我们此时系统当中内存的使用情况是这样的，那采用空闲分区表的话，我们就可以得到一个这样的表。每一个空闲分区块都会对应一个空闲分区表的表项，那这些空闲分区块是按地址从低到高的顺序依次进行排列的。那如果采用空闲分区链的话，其实也类似，也是按照地址从低到高的顺序把这些空闲分区块依次地链接起来。那这个算法对这两种数据结构的操作其实是很类似的，无非就是从头到尾依次检索，然后找到第一个能够满足要求的分区。所以这个地方我们就以空闲分区链为例子。空闲分区表的操作其实也类似。***

***![1089139-20190725192317371-1351325024.png][]***

***那按照首次适应算法的规则，那如果说此时有一个进程要求15M字节的空闲分区，那么我们会从空闲分区链的链头开始，依次查找找到第一个能够满足大小的分区。那经过检查发现第一个20M字节的这个空闲分区，已经可以满足这个要求。***

***![1089139-20190725194303381-195878567.png][]***

***所以我们会从20M字节的空闲分区当中，摘出15M分配给进程5，于是这个地方会剩余5M字节的空闲分区。***

***![1089139-20190725194938219-2075956603.png][]***

***那相应的，我们需要把空闲分区链的对应结点的这些数据包括分区的大小还有分区的起始地址等等这一系列的数据都进行修改。***

![1089139-20190725195054242-1521122759.png][]

***那么此时如果还有一个进程到来，它需要8M字节的内存空间。那我们依然还是会从空闲分区链的链头开始依次检索，***

***![1089139-20190725195310372-839085653.png][]***

***那经过一系列的检索会发现，***

***![1089139-20190725195413886-1988011404.png][]***

***第二个空闲分区的大小是足够的，于是我们会从第二个空闲分区10M字节当中，***

![1089139-20190725195445023-888585401.png][]

***摘出8M分配给进程6。那这个地方会剩余2M字节的空闲分区。所以我们和刚才一样，也需要修改空闲分区链当中相应的分区大小还有分区的起始地址这一系列的信息。那这个地方就不再展开赘述。所以这就是首次适应算法的一个规则，我们按照空闲分区以地址递增的次序进行排列，并且每一次分配内存的时候我们都会从链头开始依次往后寻找，找到第一个能够满足要求的空闲分区进行分配。***

***![1089139-20190725200204003-1780376688.png][]***

***接下来来看最佳适应算法，这种算法的思想其实也很好理解。由于动态分区分配算法是一种连续分配的方式，那既然是连续分配就意味着我们系统为各个进程分配的空间必须是连续的一整片区域。所以我们为了保证大进程到来的时候有大片的连续空间可以供大进程使用，所以我们可以尝试尽可能多地留下大片的空闲区间。那也就是说，我们可以优先地使用更小的那些空闲区间。所以最佳适应算法会把空闲分区按照容量递增的次序依次链接。那每次分配内存的时候会从头开始依次查找空闲分区链或者空闲分区表，找到大小能够满足要求的第一个空闲分区。那由于这个空闲分区是按容量递增的次序排序排列的，所以我们找到的第一个能够满足的空闲分区，一定是能够满足但是大小又最小的空闲分区。那这样的话我们就可以尽可能多地留下大片的空闲分区了。那这个地方还是一样，我们就以空闲分区链作为例子，空闲分区表的操作其实也类似。如果说系统当中的内存使用情况是这个样子，那么我们按照空闲分区块的大小从小到大也就是递增的次序链接的话，那应该是4、10、20这样的顺序链接。如果说此时有一个新的进程到达，那这个进程需要9M字节的内存空间的话，按照最佳适应算法的规则，我们会从链头开始依次往后检索，找到第一个能够满足要求的空闲分区也就是10M字节。***

***![1089139-20190725220906778-346489362.png][]***

***于是我们会从这10M字节当中摘出其中的9M分配给这个进程，那这个地方就要只剩下1M字节的大小。但是由于最佳适应算法要求我们空闲分区必须按照容量递增的次序进行链接，所以这个地方变成了1M之后我们就需要对这个整个空闲分区链进行重新排序，***

***![1089139-20190725222917102-694399268.png][]***

***那最后会更新为这个样子，也就是把更小的这个空闲分区挪到这个链的链头的位置。那之后如果还有另外一个进程需要到达它需要3M字节的空闲分区的话，那同样的我们也需要从链头开始依次查找，于是发现这个分区是可以满足的。***

***![1089139-20190725223707086-1818101114.png][]***

***那么第二个进程3M字节我们就可以从4M当中摘出3M给它分配，那这个地方也会变成只有1M字节的空闲分区。那我们之后就需要把这个结点对应的那些空闲分区大小、空闲分区的起始地址这些信息进行更新。那这个地方进行更新之后，整个空闲分区链依然是按照容量递增的次序进行链接的，所以我们不需要像刚才那样进行重新排列。那这个地方就不再展开细聊了。那从刚才的这个例子当中我们会发现最佳适应算法有一个很明显的缺点，由于我们每一次选择的都是最小的能够满足要求的空闲分区进行分配，所以我们会留下越来越多很小的、很难以利用的内存块。比如说这个地方有1M字节这个地方又有1M字节，那假如我们所有的进程都是两M字节以上，那这两个地方的碎片就是我们难以利用的，所以采用这种算法的话是会产生很多很多的外部碎片的。那这是最佳适应算法的一个缺点。***

***![1089139-20190725224111224-598799137.png][]***

***那于是为了解决这个问题，人们又提出了最坏适应算法。它的算法思想和最佳适应刚好相反，由于最佳适应算法留下了太多难以利用的小碎片，所以我们可以考虑在每次分配的时候优先使用最大的那些连续空闲区，这样的话我们进行分配之后，剩余的那些空闲区就不会太小，所以如果采用最坏适应算法的话，我们可以把空闲分区按照容量递减的次序进行排列。而每一次分配内存的时候就顺序地查找空闲分区链，找出大小能够满足要求的第一个空闲分区。那由于这个地方空闲分区是按容量递减的次序进行排列的，所以链头第一个位置的那个空闲分区肯定是能够满足要求的。如果第一个都满足不了要求，那剩下的后面的那些空闲分区，肯定都比第一个空闲分区更小，那别的那些空闲分区肯定也不会满足。那还是来看一个具体的例子。假设此时系统当中内存使用情况是这样。那我们采用空闲分区表和空闲分区链可以表示出此时的这些空闲分区的情况。那按照最坏适应算法的规则，我们需要按照容量递减的次序依次把这些空闲分区进行排列，也就是20、10、4。那此时假如有个进程它需要3M大小的内存空间，那由于链头的第一个空闲分区就可以满足，所以我们会从其中摘出3M进行分配，***

***![1089139-20190725234821044-130411865.png][]***

***那这个地方就变成了还剩17M。那接下来还有一个进程也到达，它需要9M内存，***

***![1089139-20190725235418407-1623150425.png][]***

***那同样的我们也是从这链头的这17M当中摘出其中的9M分配给进程6，于是进行数据的更新。那更新了之后我们会发现，***

***![1089139-20190725235726038-1929726782.png][]***

***此时这个空闲分区链，已经不是按照容量递减的次序进行排列的，所以我们需要把这个空闲分区链进行重新排序，也就是变成这个样子，10、8、4，依然保持按容量递减的次序进行链接，那如果有下一个进程到达的话，那我们第一个需要检查的就是10这个空闲分区。那从这个例子当中可以看到，最坏适应算法确实解决了刚才最佳适应算法留下了太多难以利用的碎片的问题。但是最坏适应算法又造成了一个新的问题，由于我们每次都是选择最大的分区进行分配，所以这就会导致我们的那些大分区会不断不断地被分割为一个一个小分区。那如果之后有一个大进程到达的话就没有连续的大分区可用了。比如说此时来了一个20M的大进程，那这个大进程就无处安放。所以这是最坏适应算法的一个明显的缺点。***

***![1089139-20190726094759844-944697582.png][]***

***那接下来我们再来看第四种，邻近适应算法，这种算法的思想其实是为了解决首次适应算法当中存在的一个问题。首次适应算法每一次都会从链头开始查找，这有可能会导致低地址部分会出现很多很小的难以利用的空闲分区，也就是碎片。但是由于首次适应算法又必须按照地址从低到高的次序来排列这些空闲分区，所以我们在每次分配查找的时候都需要经过低地址部分那些很小的分区，这样的话就有可能会增加查找的一个开销。所以如果我们能够从每次都从上一次查找结束的位置开始往后检索的话，是不是就可以够解决之前所说的这个问题了呢？所以邻近适应算法和首次适应算法很像，它也是把空闲分区按照地址递增的顺序进行排列，当然我们可以把它排成一个循环链表，这样的话比较方便我们检索。那每一次分配内存的时候都是从上次结束的位置开始往后查找，找到大小能够满足的第一个空闲分区。那假如说此时系统当中的内存使用情况是这样，那我们可以把这些空闲分区按照地址递增的次序依次进行排列，排成一个循环链表。那刚开始如果说有一个进程到达，它需要5M字节的内存空间，刚开始我们会从链头的位置开始查找，***

***![1089139-20190726101816183-686214286.png][]***

***那第一个不满足，***

***![1089139-20190726102256975-883676143.png][]***

***那******第二个6M是满足的。***

***![1089139-20190726102427273-379150432.png][]***

***于是我们会从6M当中摘出5M分配给它，***

***![1089139-20190726105350621-827847496.png][]***

***那这个地方就还剩余1M字节。于是我们需要更新这个分区链当中对应的结点，包括分区的大小还有分区的起始地址。但是有没有发现，采用邻近适应算法还有首次适应算法，我们只需要按照地址依次递增的次序来进行排列，所以即使这个地方内存分区的大小发生了一个比较大的变化，但是我们依然不需要对整个链表进行重新排列，所以这也是邻近适应算法还有首次适应算法比最佳适应算法和最坏适应算法更好的一个地方。算法的开销会比较小，不需要我们再花额外的时间对这个链表进行重新排列。***

***![1089139-20190726105627449-1781003744.png][]***

***那假如此时有一个新的进程到达，它需要5M字节的空间。那按照邻近适应算法的规则，我们只需要从上一次查找到的这个位置依次再往后查找就可以了，***

***![1089139-20190726110147338-490193075.png][]***

***所以这个不满足，***

***![1089139-20190726110210381-1515899218.png][]***

***那我们看下一个，10M是满足的，***

***![1089139-20190726110359644-325222893.png][]***

***于是会从10M当中摘出5M进行分配，***

***![1089139-20190726110723724-2101603545.png][]***

***然后更新相应的这些数据结构。那这个地方大家有没有发现，如果此时我们采用的是首次适应算法的话，如果此时需要分配5M的内存空间，那么我们依然会从链首的位置开始往后查找，所以第一个4M不满足，第二个1M不满足，第三个10M才能满足，那就会有三次查找。那如果说我们采用的是邻近适应算法的话，我们只需要从这个位置开始往后查找，也就是查两次就可以了，所以这是邻近适应算法比首次适应算法更优秀的一个地方。首次适应算法会导致低地址部分留下一些比较小的碎片，但是我们每一次开始检索都需要从低地址部分的这些小碎片开始往后检索，所以这就会导致首次适应算法在查找的时候可能会多花一些时间，不过这并不意味着邻近适应算法就比首次适应算法更优秀很多。***

***![1089139-20190726111652856-409068835.png][]***

***其实邻近适应算法又造成了一个新的问题。在首次适应算法当中，我们每次都需要从低地址部分的那些小分区开始依次往后检索，但是这种规则也决定了，如果说在低地址部分有更小的分区可以满足我们的需求的时候，我们就会优先地使用低地址部分的那些小分区，这样的话就意味着高地址部分的那些大分区就有更大的可能性被保留下来。所以其实首次适应算法当中也隐含了一点最佳适应算法的优点。那如果我们采用的是邻近适应算法的话，由于我们每一次都是从上一次检查的位置开始往后检查，所以我们无论是低地址部分还是高地址部分的空闲分区，其实都是有相同的概率被使用到的，所以这就导致了和首次适应算法相比，高地址部分的那些大分区，更有可能被使用被划分成小分区，这样的话高地址部分的那些大分区也很有可能被我们用完，那之后如果有大进程到达的话就没有那种连续的空闲分区可以进行分配了。所以其实邻近适应算法的这种策略也隐含了一点最大适应算法的缺点。所以综合来看，其实刚才介绍的这四种适应算法当中，反而首次适应算法的效果是最好的。***

***![1089139-20190726113716748-585727858.png][]***

***好的那么这个小节我们介绍了四种动态分区分配算法，分别是首次适应、最佳适应、最坏适应和邻近适应。那这个小节的内容很容易作为选择题进行考查，甚至有可能作为大题进行考查。其实我们只需要理解各个算法的算法核心思想就可以分析出这些算法的这些空闲分区应该怎么排列，它们的优点是什么，缺点是什么。那这几个算法当中，比较不容易理解的其实是邻近适应算法的优点和缺点，但是刚才咱们也进行了详细的分析这儿就不再重复了。那这个地方大家会发现，各个算法提到的算法开销的大小问题，那这个地方的算法开销指的是为了保证我们的空闲分区是按照我们规定的这种次序排列的，在最佳适应和最坏适应这两种算法当中，我们可能需要经常对整个空闲分区链进行重新排序，所以这就导致了算法开销更大的问题。而首次适应和邻近适应我们并不需要对整个空闲分区链进行顺序地检查和排序，所以这两种算法的开销是要更小的。那么这些算法大家还需要通过课后习题的动手实践来进行进一步的巩固。***

***![1089139-20190726120739018-920023012.png][]***

***在这个小节中我们会学习一个很重要的高频考点，同时也是这门课的难点，叫做分页存储管理。***

***![1089139-20190726131721503-672355150.png][]***

***那在之前的小节中我们学习了几种连续分配存储管理方式，所谓的连续分配就是指，操作系统给用户进程分配的是一片连续的内存区域，而非连续分配就是指，它给用户进程分配的可以是一些离散的、不连续的内存区域。那这个小节我们会首先学习第一种，非连续的分配管理方式，叫做基本分页存储管理。***

***![1089139-20190726131913704-1528673607.png][]***

***那首先来认识一下什么叫分页存储。那如果一个系统支持分页存储的话，那么系统会把内存分为一个一个大小相等的区域，比如说一个区域的大小是4KB，那这样的一个区域称为一个页框或者叫一个页帧，当然它还有别的一些名词，不同的教材或者不同的题目上大家可能会看到各种各样的名词出现，不过需要知道它们指的都是页框。那系统会给每个页框一个编号，并且这个编号是从零开始的，这个编号就叫做页框号，或者叫页帧号、内存块号、物理块号、物理页号。那接下来我们思考一下，内存里边它存放的其实无非就是各个进程的数据对吧，包括进程的代码啊、进程的指令啊等等这些数据，所以为了把各个进程的这些数据把它放到各个页框当中，因此操作系统也会把各个进程的这些逻辑地址空间把它分为与这个页框大小相等的一个一个的部分。比如说我们这个地方举的例子进程A，它的逻辑地址空间是0-16K-1，也就是16K，所以这个进程的大小应该是16KB这么多。把它分为与页框大小相等的一个一个部分，因此每个部分就是4KB这么多。并且系统也会给进程的各个页进行一个编号，这个编号就称作为页号或者叫页面号。***

***![1089139-20190726135406527-1105944431.png][]***

***那进程的各个页会被放到内存的各个页框当中，所以进程的页面和内存的页框是有一一对应、一一映射的关系的。那这个地方建议大家暂停，好好地来区分一下这几个很容易混淆的概念，特别是页、页面、页框和页帧。这四个术语在刚开始学习的时候，很容易认为它们指的是同一个东西。但其实不是，页框和页帧它指的是内存在物理上被划分为的这样一个一个的部分，这个叫页框。而页和页面指的是进程在逻辑上被划分为的一个一个的部分。那除了页框页帧之外，有的教材当中也会把页框称为内存块、物理块或者叫物理页面，并且在我们的课后习题当中，这些名词都有可能出现，所以这个地方建议大家特别注意一下这些很容易混淆的概念。那到这儿我们就初步了解了什么叫分页存储。接下来要思考的问题是这样的，刚才我们不是说进程的页面和内存的这个页框它有一一对应的关系吗？那操作系统是怎么记录这种一一对应关系的呢？***

***![1089139-20190726140300261-1983976793.png][]***

***这就涉及到一个很重要的数据结构，叫做页表。操作系统会给每一个进程都建立一张页表。并且这个页表一般是存放在内存的控制块当中的，也就是PCB当中。那刚才我们说过，进程的逻辑地址空间会被分为一个一个的页面，那每一个页面就会对应页表当中的一个页表项。所谓的页表项，大家可以理解为就是这个页表当中的一行。那页表项当中包含了页号和块号这样的两个数据，所以这样的一个页表就可以记录下来这个进程的各个页面和实际存放的内存块之间的映射关系。注意内存块其实就是页框，只不过内存块这个术语可能更不容易让人混淆一些，所以我们在接下来的讲解当中更多地会使用的是内存块这样的表述方式。不过大家自己答题的时候，建议使用页框这个术语。因为去看英文书的话，其实这个术语它的英文叫做page frame，所以大部分的教材其实习惯翻译成页框。因此，建议大家答题的时候使用的是页框这个术语。好的，那么再回到页表这个数据结构，从刚才的分析当中我们知道，页表它由这样一个一个的页表项组成。那接下来我们要思考的问题是这样的，首先，这些页表项是存在内存里的，那每一个页表项需要占几个字节的空间呢？第二个问题是操作系统要怎么利用页表来实现逻辑地址到物理地址的转换。***

***![1089139-20190726161628804-1418909815.png][]***

***那首先我们来分析第一个问题，直接结合一个例子来理解。不过呢计算机分配存储空间它是以字节为单位分配，而不是以比特为单位分配。***

***1GB=2^10MB=2^20KB=2^30B 4GB=2^32B  1KB=2^10B 4KB=2^12B  20bit<3B***

***![1089139-20190726162111940-650971293.png][]***

***那接下来我们再来看一下这个页号又需要占多少个字节呢？直接告诉大家答案。页号是不需要占存储空间的。因为各个页表项在内存中连续存放，所以页号可以是隐含的。什么意思呢？那刚才我们得出的结果是一个块号它至少需要占用三个字节，并且这些页表项在内存当中都是连续存放的。那如果在内存中只存储块号而没有存储页号的话，那我们又怎么找到页号为i的这个页面对应的页表项呢？其实很简单，只要我们知道了这个页表它在内存当中存放的起始地址X，我们就可以用X+3\*I就得出这个i号页表项它的存放地址了。那学过数据结构的线性表，相信这个地方并不难理解。其实就相当于是一个数组，对于普通的数组而言，数组的下标我们也不需要花存储空间来存放对吧。因此我们得出结论，页表当中的这个页号可以是隐含的，它并不占用存储空间。那结合之前的结论我们知道，一个页表项它在逻辑上其实是包含了页号和块号这样的两个信息，但是在物理上它其实只需要存放块号的这个信息，只有块号需要占用存储空间。那如果这个进程它的页号是0-n号，也就是说它总共有n+1个页面的话，那么存储这个进程的页表就至少需要3\*（n+1）这么多个字节。那我们通过页表可以知道各个页面它存放在哪个内存块当中。***

***![1089139-20190726164228629-622018616.png][]***

***但是需要注意、需要强调的是，这个地方它记录的只是内存的块号，而不是具体的内存块的起始地址。如果我们要计算一个内存块的起始地址的话，我们需要用这个块号再乘以内存块的大小。这个地方大家需要特别地注意体会一下，不然做题的时候很容易出错。好的那么到这儿我们就弄清楚了第一个问题。***

***![1089139-20190726171801255-361992954.png][]***

***接下来要探索的是第二个问题，如何实现地址的转换，也就是逻辑地址转换到物理地址。那我们先来回忆一下，我们之前在讲连续存放那种方式的时候，操作系统是怎么实现这种地址的转换的呢？如果一个进程它在内存当中连续存放，那么我们只需要知道这个进程它的起始地址，然后把接下来要访问的那个逻辑地址和起始地址相加就可以得到它最终的物理地址了，那这是连续存放的时候。那这个逻辑地址我们可以把它理解为是一种偏移量，也就是说相对于它的起始地址而言往后偏移了多少。***

***![1089139-20190726172610297-349795956.png][]***

***那如果采用分页存储的话，那这个地址转换要怎么进行呢？***

***![1089139-20190726174732951-15354039.png][]***

***这个进程会被放到内存的各个位置当中，不过有这样的一个特点，虽然进程的各个页面在内存中是离散的存放的，但是各个页面的内部它都是连续的。注意体会这个特点。那基于这个特点，我们来看一下，如果要访问逻辑地址A，应该怎么来进行呢？首先我们可以确定这个逻辑地址A，它应该对应的是进程的哪个页面。也就是说要确定这个逻辑地址A它所对应的页号。接下来操作系统就可以用这个页号去查询页表，然后找到这个页面它存放在内存当中的什么位置。那第三步我们要确定的是，逻辑地址A它相对于这个页面的起始位置而言的“偏移量”是多少。因为各个页面内部都是连续存放的嘛，所以我们只需要把这个逻辑地址A它所对应的页面在内存当中的起始地址，再加上这个逻辑地址的页内偏移量W，就可以得到这个逻辑地址A所对应的物理地址了。那这个就是实现地址变换的一个基本的思路。那在之前的讲解当中我们了解了怎么利用页表来找到一个页面在内存当中的起始地址。***

***![1089139-20190726175145796-1574688722.png][]***

***那接下来我们要探讨的就是怎么确定逻辑地址所对应的页号和页内偏移量。***

***![1089139-20190726175218327-295027565.png][]***

***还是结合一个例子来理解。***

***![1089139-20190726191206818-119005852.png][]***

***那在这个例子当中，一个页面的大小是50个字节。那熟悉二进制乘法或者无符号左移、无符号右移这些操作的同学，可能很容易理解这个原理。但对于跨考的同学来说也许会觉得它比较神奇但不知道为什么会这样。那如果想要了解呈现这种规律背后的原理的话，建议可以去看一下无符号左移、无符号右移和二进制的乘法、二进制的除法之间的一个联系。好的扯远了，回到我们的这个主题上来。***

***![1089139-20190726192439103-1331338369.png][]***

***那除此之外它还有另外一个优点。我们刚才讲页表的时候强调过一个问题，页表当中记录的是内存块号而不是内存块的起始地址，所以如果我们要计算一个内存块的起始地址的话，需要进行一个这样的乘法运算。但是如果内存块的大小刚好是2的整数幂，计算起来就没有那么麻烦。我们假设1号页面它存放的内存块号是9，如果用二进制表示的话9这个数就应该是1001。那这么完美的特性其实就是因为页面大小、内存块的大小刚好是2的整数次幂，所以在地址转换的过程当中，我们只要查到页表当中存放的这个内存块号，再把这个内存块号和逻辑地址的页内偏移量进行一个拼接其实就可以得到最终的物理地址了。如果不是2的整数次幂的话，页面在内存中的起始地址必须用这样的乘法的方式来进行，这也会导致硬件的效率降低。***

***![1089139-20190726194730536-2133579389.png][]***

***那经过刚才的这两个例子我们可以看到，页面大小是2的整数次幂有这样的两个好处。这个地方大家再结合文字好好体会一下就可以了，就不再重复。***

***![1089139-20190726195823424-1575465396.png][]***

***那如果页面大小是2的整数次幂的话，我们可以把逻辑地址把它分为这样的两个部分，分别是页号和页内偏移量。总之呢，只要知道页内偏移量的位数就可以推出页面大小，同样的知道页面大小也可以反推出页内偏移量应该占多少位，从而就可以确定逻辑地址的结构，这一点也是考题当中非常非常高频的一个考点，大家在做题的时候会经常遇到。当然，有的题目当中它的页面大小有可能不是2的整数次幂，那对于这种题目来说我们要计算页号和页内偏移量，还是只能用最原始的那种算法，用除法来得到页号，用取余得到页内偏移量。***

***![1089139-20190726220944064-1142790551.png][]***

***系统会把进程分页，会把各个页面离散地放到各个内存块当中，或者说放到各个页框当中。那由于各个页面会依次放到各个内存块当中，所以需要记录这种页面和内存块之间的映射关系，因此需要有一个很重要的数据结构叫做页表。页表由一个一个的页表项组成，并且页表项在内存中是连续存放的，各个页表项大小相等。注意，页号是隐含的，不需要占用存储空间。那我们只需要知道页表在内存当中存放的起始地址并且知道页号和页表项的大小就可以算出i号页表项存放在什么位置了。那最后我们还介绍了分页存储的逻辑地址结构，可以分为页号和页内偏移量这样两个部分。如果页面的大小刚好是2的整数次幂，那么硬件在拆分逻辑地址，在进行物理地址的计算的时候，都会更快。所以一般来说，页面大小都是2的整数次幂。当然，这个小节中我们还介绍了在分页存储这种管理方式当中，怎么实现逻辑地址到物理地址的转换，具体的转换过程大家现在只需要有个大体的印象就可以。下个小节当中我们还会结合一些硬件的细节，再进一步地阐述地址转换的过程。***

***![1089139-20190726222322251-1485760542.png][]***

![1089139-20190726225926976-795232152.png][]

***那这个小节的内容也属于基本分页存储管理。其实所谓的基本地址变换机构，就是在基本分页存储管理当中用于实现逻辑地址到物理地址转换的一组硬件机构。那我们在学习这个小节的过程当中，需要重点掌握这些变换机构的工作原理还有流程，这个小节的内容十分重要，既有可能作为选择题也有可能结合大题进行考查。***

***![1089139-20190726230543980-536157606.png][]***

***那通过上个小节的讲解我们知道，在分页存储管理当中，如果要把逻辑地址转换成物理地址的话，总共需要做四件事，第一，要知道逻辑地址对应的页号。第二，还需要知道逻辑地址对应的页内偏移量，第三我们需要知道逻辑地址对应的页面在内存当中存放的位置到底是多少。第四，我们再根据这个页面在内存当中的起始位置和页内偏移量就可以得到最终的物理地址了。那为了实现这个地址转换的功能，系统当中会设置一个页表寄存器，用来存放页表在内存当中的起始地址还有页表的长度这两个信息。在进程没有上处理机运行的时候，页表的起始地址还有页表长度这两个信息是放在进程控制块里的。只有当进程被调度，需要上处理机的时候，操作系统内核才会把这两个数据放到页表寄存器当中。那我们接下来用一个动画的形式看一下从逻辑地址到物理地址的转换应该是什么样一个过程。***

***![1089139-20190726232415783-485637464.png][]***

***我们知道操作系统会把内存分为系统区和用户区，那在系统区当中会存放着一些操作系统对整个计算机软硬件进行管理的一些相关的数据结构，包括进程控制块PCB也是存放在系统区当中的。那如果说一个进程被调度，它需要上处理机运行的话，进程切换相关的那些内核程序就会把这个进程的运行环境给恢复，那这些进程运行环境相关的信息本来是保存在PCB当中的。那之后这个内核程序会把这些信息把它放到相应的一系列寄存器当中，包括页表寄存器。页表寄存器当中存放着这个进程的页表的起始地址还有页表的长度，另外呢像程序计数器PC也是需要恢复的。程序计数器是指向这个进程下一条需要执行的指令的逻辑地址，逻辑地址A。那么接下来我们来看一下怎么把这个逻辑地址转换成实际的物理地址，也就是说CPU怎么在内存当中找到接下来要执行的这条指令。***

![1089139-20190727001355365-560222204.png][]

***那从上个小节的讲解中我们知道，采用分页存储管理方式的这种系统当中，逻辑地址结构肯定是固定不变的。在一个逻辑地址当中，页号有多少位，页内偏移量有多少位这些操作系统都是知道的。所以只要知道了逻辑地址A，那么就可以很快地切分出页号和页内偏移量这样的两个部分。那接下来会对页号的合法性进行一个检查。一个进程的页表长度M指的是这个进程的页表当中有M个页表项，也就意味着这个进程的页面总共有M页。所以如果此时想要访问的页号已经超出了这个进程的页面数量的话，那么就会认为此时想要访问的这个逻辑地址是非法的，这样就需要抛出一个越界中断。那如果说这个页号是合法的，***

***![1089139-20190727002739220-834080230.png][]***

***那么接下来会用这个页号和页表始址来进行计算，找到这个页号对应的页表项到底是多少。那通过上个小节的讲解我们知道，页表当中的每一个页表项的长度其实是相同的，所以其实只要我们知道了页号还有页表起始地址，再知道我们每一个页表项的长度，我们就可以算出我们想要访问的页号对应的页表项所存放的位置。那既然知道了它存放的内存块号，我们就可以再用内存块号结合内存偏移量得到最终的物理地址，然后就可以顺利地访问逻辑地址A所对应的那个内存单元了。所以整个过程做了这样几件事，第一是根据逻辑地址算出了页号和页内偏移量。第二需要检查这个页号是否越界，是否合法。第三，如果这个页号是合法的，那么我们会根据页号还有页表始址来计算出这个页号对应的页表项应该是在什么地方，然后找到相应的页表项。第四，在我们得知了这个页面存放的内存块号之后，我们就可以用内存块号还有页内偏移量来计算出最终的物理地址。然后最后再对这个物理地址进行访问。那在考试当中，经常会给出一个逻辑地址还有页表然后让我们计算对应的物理地址，所以大家需要对上面所说的这些过程都非常熟悉。***

***![1089139-20190727004117145-1417707652.png][]***

***那接下来我们再用文字的方式再给出一个描述，虽然说这个内容比较重复，但是也是因为这个部分的内容极其重要，所以想多让大家过几遍。特别是页表长度还有页表项长度这两个概念一定要着重注意一下。***

***![1089139-20190727102552410-1424782379.png][]***

***那这个地方的验证这儿就暂时不展开，大家下去动手尝试一下。***

***![1089139-20190727102116038-1564185951.png][]***

***页号2对应的内存块号b=8，也就是2号页面应该存在内存块号为8的地方。按字节寻址就意味着这个系统当中每个地址对应的是一个字节。逻辑地址结构中，页内偏移量占10位，这个信息很重要，页内偏移量的位数其实就直接决定了一个页面的大小是多少。那么偏移量占10位的话，那么就说明一个页面的大小是2的10次方个字节，也就是1KB。所以这种说法和上面这种说法其实是等价的，在做题的时候一定要注意这个页内偏移量还有页面大小之间的这种对应关系。那进行地址的转换第一步我们应该根据这个条件算出页号和页内偏移量。由于题目当中给出的是这种十进制表示的逻辑地址，所以我们用除法还有取余操作这样的方式来计算会更方便一些。而根据题目当中给出的条件，页号2对应的内存块号b=8，也就说明，页号为2的页表项是存在的，因此页号2肯定没有越界。并且查询页表之后已经知道这个页面应该是存放在内存块号为8的地方。那第三步，我们知道了内存块号、知道了页号、页内偏移量我们就可以计算物理地址。物理地址=内存块号\*每个页面的大小（或者说每一个内存块的大小）+页内偏移量。其实在分页存储管理（页式存储管理）的系统当中，只要我们确定了每个页面的大小是多少，那么逻辑地址的结构肯定就已经确定了。所以页式管理当中的地址是一维的，我们并不需要告诉系统除了逻辑地址以外的别的信息，不需要显式地告诉它页内偏移量占多少，页号占多少。因为这些信息都是确定的，所以在页式管理当中，我们想要让系统把逻辑地址转换成物理地址，只需要告诉系统一个信息，也就是逻辑地址的值，不需要再告诉系统别的任何信息。那因为只需要告诉它一个信息，因此这个地址是一维的。那这就是我们手动地模拟基本地址变换机构转换地址的一个过程。很多初学者会忽略的是，对页号进行越界检查的这一步操作，所以这个地方需要留个心眼。***

***![1089139-20190727110900839-1421623194.png][]***

***但是1365个页表项并不能占满整个页框。这个页框还会剩余一个字节的页内碎片。那由于这个地方只剩一个字节的空闲区域了，所以下一个页表项只能存放在下一个页框当中，它不能跨页框地存储。+1就是为了消除这一字节剩余的误差。所以说可以发现，如果说我们的这些页表项并不能装满整个页框的话，那在查找页表项的时候其实是会造成一些麻烦的。所以为了解决这个问题，我们可以把每个页表项的长度再拓展一下，把它拓展到四个字节。这样的话我们就可以保证每个页框刚好可以存放整数个1024个页表项，并且不会有任何的这种页内碎片，***

***![1089139-20190727113130205-55877941.png][]***

***就像这个样子。这样的话，我们要查询1024号的页表项，我们就不需要像上面这么麻烦了。因为这个页框当中不会有任何的页内碎片，所以在理论上来说，页表项的长度最短三个字节就可以表示所有的这些内存块号的范围。但实际的应用当中，为了方便页表的查询，经常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。不过即使这个页表项长度是3个字节，其实也没问题，只不过在查询页表的时候可能会需要做一些更麻烦的处理。如果在题目当中要我们算页表项的长度最小应该是多少，那我们按照3字节这样的思路来处理就可以了。四个字节这样的处理只是实际应用当中为了方便而采用的一种策略。那经过刚才的这个例子大家有没有发现，一个进程如果它的页表太大，也就是页表项太多的话，那么这个进程的页表一般来说装到内存里也是会尽可能地让它装在连续的一些内存块当中。因为这样的话我们都可以用一个统一的计算方式就可以得到我们想要得到的那个页表项所存储的位置。***

***![1089139-20190727115459524-1254574716.png][]***

***好的，那么在这个小节当中我们学习了如何使用基本地址变换机构这一系列的硬件来实现地址转换的一个过程。那基本地址变换机构当中，最重要的硬件就是页表寄存器。大家需要知道页表寄存器有什么作用。那这个小节中，最重要的是要掌握地址变换的整个过程。我们要知道计算机是怎么一步一步实现这些地址变换的，并且还要能用手动的方式、手算的方式来模拟出整个地址变换的过程。那这一部分是大题和小题的极高频的出题点。那除了地址变换过程之外，我们在讲解的过程中，也补充了一些小的细节。比如说页内偏移量的位数和页面大小之间是有一个对应关系的。那如果说题目当中给出了页内偏移量的位数，大家需要能够推出页面的大小。同样的，如果告知我们页面大小，也要能够推出页内偏移量的位数。如果知道地址、逻辑地址的总位数的话，我们还要能够写出整个逻辑地址的地址结构。那这个小知识点在计算题当中是很容易用到的。那除了这个之外，页式管理的地址是一维的。这一点也经常在选择题当中进行考查。那大家要理解什么叫一维，所谓的一维就是说，我们要让CPU帮我们找到某一个逻辑地址对应的物理地址的话，我们只需要告诉CPU一个信息，也就是逻辑地址的值，并不需要再告诉它其他的任何信息，所以这是一维的含义。那另外的两个小细节只是为了能够让大家更充分地了解这种页式管理的这种机制才补充的，当然考试当中一般来说不会考查。那除了这些内容之外，我们还需要注意一个很重要的知识点。在CPU得到一个想要访问的逻辑地址之后，一直到实际访问的这个逻辑地址对应的内存单元的整个过程当中，总共需要进行两次访问内存的操作。第一次访问内存是在查询页表的时候进行的，第二次访问内存是在实际访问目标内存单元的时候进行的。那在下个小节当中我们会探讨一种新的地址变换机构，是否能用一种别的地址变换机构来减少访问内存的次数，从而加快整个地址变换还有访问的过程呢？那这是下个小节想要探讨的问题。***

***![1089139-20190727122722238-1778016372.png][]在这个小节中我们会学习具有快表的地址变换机构。***

***![1089139-20190727123234909-322098420.png][]***

***那上个小节中我们学了基本地址变换机构，还有逻辑地址到物理地址转换的一个过程。那在基本地址变换机构的基础上，如果引入了快表的话，就可以让这个地址变换的过程更快，所以这个小节中我们首先会介绍什么是快表，并且会介绍引入了快表之后，地址变换的过程有什么区别。最后我们会解释为什么引入快表之后，可以让计算机的整体效率、整体性能都得到很高的提升。***

***![1089139-20190727123644460-1229069571.png][]***

*** 注意TLB它不是内存，它是一种高速缓存。那快表中存放的是最近我们访问过的一些页表项的副本，这样的设计可以让地址变换速度更快。页表其实是存放在内存当中的，在引入了快表之后，我们可以把存放在内存中的页表称为慢表。因为访问内存中的这个页表的速度更慢，而访问快表当中存放的这些页表项的速度会更快，所以这是快表和慢表名字的由来。但是由于硬盘的读写速度很慢，而CPU处理数据的速度又很快，因为硬盘速度慢而拖累CPU的速度，导致系统整体性能的降低。内存的速度要比硬盘快好几十倍，所以我们把CPU要访问的那些数据先放到内存中就可以缓和CPU和硬盘之间的速度矛盾。把内存当中最近有可能会被频繁访问到的东西放到高速缓存里，进一步地缓和CPU和存储设备之间的一个速度矛盾。高速缓存它本质上也是用于存取数据的一个硬件设备。缓存并不是内存，CPU访问高速缓存的速度要比访问内存的速度要快的多。因此如果我们可以把最近想要访问的那些页表项的副本把它存到这个快表这种高速缓存当中，那么CPU在地址变换的时候查询页表的这个速度就会快的多了。快表TLB它和我们平时所说的那种狭义上的高速缓存，狭义上的Cache其实也是有区别的。快表的查询速度要比慢表快很多。***

***![1089139-20190727152244393-1417443521.png][]***

***那接下来我们要探讨的问题是，既然快表的查询速度快那么多，那能不能把整个页表都放在快表当中呢？其实这个原因不难理解，因为快表这种存储硬件的造价更贵，因此在成本相同的情况下，快表可以存的东西肯定没有那么多。所以我们系统当中存储分级的这个思想和我们这儿提到的这个例子其实是一模一样的。***

***![1089139-20190727152846765-1873996680.png][]***

***所以为了兼顾系统整体的运行效率，同时也要考虑这个造价成本，因此才采用了这种多级的存储设备。好的那么刚才我们从硬件的角度理解了快表为什么要比慢表更快，那接下来我们再从这个操作系统的角度来看一下快表到底有什么作用。***

***![1089139-20190727153608051-477628525.png][]***

***我们来看这样的一个例子，（0，0）、（0，4）、（0，8）这样的几个逻辑地址，那前面的这个是指页号，后面的这个指的是页内偏移量。这个进程的页表存放在内存当中，是这个样子。那当这个进程上处理机运行的时候，系统会清空快表的内容。注意啊，快表是一个专门的硬件，当进程切换的时候，快表的内容也需要被清除。***

***![1089139-20190727182308314-346299224.png][]***

***那我们假设访问快表、访问TLB只需要1微秒的时间，而访问内存需要100微秒的时间。接下来我们来看一下快表是如何工作的。***

![1089139-20190727182728878-450023022.png][]

***那首先这个进程它想要访问的逻辑地址是页号为0、页内偏移量也为0的这个逻辑地址。首先这个页号需要和页表寄存器当中的页表长度进行比对，进行越界异常的检查，然后发现这个页号并没有越界。接下来就会查询快表，但是由于这个进程刚上处理机运行，因此快表此时的内容是空的。在快表中找不到页号为0所对应的页表项，因此快表没有命中。那由于快表没有命中，因此接下来就不得不去访问内存当中存放的慢表，所以接下来通过页表始址还有页号计算出对应的页表项存放的位置。于是，在查询完慢表之后就可以知道，0号页面它所存放的内存块号是600。注意，在访问了这个页表项之后，同时也会把这个页表项把它复制一份放到快表当中。同时，刚才不是已经查到这个页面所对应的内存块号了吗？那么通过这个内存块号和页内偏移量就可以得到最终的物理地址。最后，就可以访问这个逻辑地址所对应的内存单元了。那这是进程访问的第一个地址。***

***![1089139-20190727184102091-654627088.png][]***

***接下来这个进程想要访问的地址是页号为0、页内偏移量为4的这个地址。那同样的，刚开始会进行一个越界异常的判断，发现没有越界。所以接下来会根据页号来查询快表，需要确认一下这个页号所对应的页表项是否在快表当中。那由于刚才我们已经把它复制到了快表当中，因此这一次的查询就可以命中。***

***![1089139-20190727190648251-1721798110.png][]***

***而快表命中之后，系统就可以直接知道，0号页面它存放的内存块号是600，因此接下来它就不需要再查询内存当中的慢表而是直接用这个内存块号和页内偏移量得到最终想要访问的物理地址，然后进行访存。***

***![1089139-20190727191108010-1830193148.png][]***

***因此，如果快表命中的话，就不需要再访问内存中的慢表了。***

![1089139-20190727190940582-77654989.png][]

***那最后的这个地址其实也是一样的。也是会先进行越界的检查，***

![1089139-20190727191259575-409043995.png][]

***然后查询快表结果快表命中。于是系统可以直接根据查询快表的结果，得到最终的这个物理地址，然后访问最终需要访问的这个内存单元。那如果这个系统中没有快表的话，每一次地址变换的过程肯定都需要查询内存中的慢表，而访问一次内存需要100微秒的时间，因此每一次地址变换都需要花100微秒。而如果说引入了快表的话，那只要快表命中，我们的地址变换过程就只需要花费1微秒的时间，所以这也是为什么快表能够加快地址变换的一个原因。***

***![1089139-20190727191956069-1279965054.png][]***

***那需要注意的是，快表中存放的是进程页表当中的一部分副本。因为之前我们已经说了，快表虽然速度更快，但是造价其实也要比内存高很多，因此为了控制成本，快表的容量就不会特别大，所以快表当中只有可能存放慢表中的一部分页表项的副本，不过这已经可以让系统的效率有很大的提升了，这个我们之后还会继续细聊。***

***![1089139-20190727200255638-1639543695.png][]***

***那接下来我们用文字的方式来总结一遍，引入了快表机构之后，地址变换的过程。首先通过这个逻辑地址，我们可以得到页号和页内偏移量，然后进行了越界判断之后，会把这个页号和快表当中所有的这些页号进行对比。只不过查询快表的速度要比查询慢表的速度快很多。如果慢表命中，也就是找到了这个页号对应的表项的话，那么就可以直接通过快表当中存放的那些信息，直接得到最终的物理地址，最终再访问我们想要访问的那个内存单元。所以在引入了快表机构之后，如果快表命中的话，我们访问一个逻辑地址，只需要一次访存。也就是访问我们最终想要访问的那个地址单元的时候才需要访存，而地址转换的过程当中，不需要访存。当然，如果快表没有命中的话，那么我们依然需要访问内存当中的页表，所以在这种情况下，我们要访问一个逻辑地址就需要两次访存。第一次访存是查询内存当中存放的页表，第二次访存是访问我们最终想要访问的那个内存单元。那需要注意的是，在我们查询慢表之后，同时也需要把慢表当中的页表项给它复制到快表当中。而如果快表已经存满了，那么我们需要按照一定的算法，淘汰快表当中的某一些页表项进行替换。那这个是我们之后置换算法当中会学习的一个内容，这儿就暂时不展开。总之在引入了快表之后，系统在进行地址变换的时候，它会优先查询快表。只有快表没有命中的时候，它才会去查询内存当中的页表。那由于查询快表的速度要比查询慢表的速度快很多，所以这就可以使这个系统的整体效能得到提升。基于局部性原理，一般来说快表的命中率可以达到90%以上。什么是局部性原理，我们一会儿再解释。我们先来看一下假设快表的命中率可以达到90%的话，它到底可以让这个系统性能提升多少。那根据上面的分析我们知道，系统在访问一个逻辑地址的时候，它首先会查询快表，会消耗1微秒的时间。如果快表命中的话，那么系统就可以直接得到最终想要访问的物理地址并且访问这个物理地址对应的内存单元。那访问这个内存单元总共需要100微秒的时间。所以如果快表命中的情况下，访问这样的一个地址总共就需要耗费1+100这么多的时间。那再来看第二种情况，如果快表没有命中的话，首先系统会查询快表消耗1微秒的时间，接下来由于快表没有命中，所以系统需要访问内存当中的慢表。那查询慢表其实就需要访问一次内存，所以这儿就需要消耗100微秒的时间。那得到最终的物理地址之后，还需要访问最终想要访问的内存单元，因为这儿还需要加上100微秒。那发生这种情况的概率是10%，所以我们给它乘上0.1的权重。那如果这个系统没有快表机构的话，那每一次访问逻辑地址肯定都需要先查询内存中的慢表，然后最终再访问我们的目标内存单元。总之大家在做题的时候，需要注意的点就是，题目当中有没有告诉你快表和慢表是同时查找的。还是说，只有快表查询未命中的时候，再查询慢表。那不管怎样，在引入了快表之后，肯定这个地址变换的过程都快了很多，系统效能得到了大幅度的提升。***

***![1089139-20190727210148783-1576119725.png][]***

***那接下来我们来解释一下刚才所说的这个快表和慢表同时查找到底是什么意思。我们的第一个例子当中我们是默认了系统先查询快表，也就是先消耗了1微秒的时间。当快表查询未命中的时候，它才会开始查询慢表。那查询慢表的过程又需要消耗100微秒的时间，而如果快表和慢表同时查询的话，情况就会变成这样。快表和慢表是同时开始查询的，而在1微秒的时候系统发现，这个快表查询未命中。但是在这个时刻，其实慢表也已经查了一微秒的时间，因此接下来再消耗99微秒就可以得到这个慢表的查询结果。那通过这个甘特图相信并不难理解，什么叫快表和慢表同时查找，什么叫先查快表，快表未命中的时候再查慢表。这是做题的时候大家需要注意的一个小细节。那接下来我们来思考一个问题，为什么TLB当中只存放了页表中的一部分就可以让系统的效能提升那么多呢？***

***![1089139-20190727221326162-1159729536.png][]***

***这其实是因为著名的局部性原理。程序当中的变量，数组还有变量i，这些变量是存放在23号页面当中的。因为10号页面当中，存放的是它的这些代码指令。而这个数组在内存中其实是连续地存放的。那由于局部性原理，也就是说这个程序在某段时间内可能会频繁连续地访问某几个特定的页面，因此在地址变换的过程中，只要它访问的是同一个页面，那么它查询页表的时候其实查到的也都是同一个页表项。所以只要我们把慢表当中的页表项把它复制到快表当中，那这样就可以让地址变换的速度快很多了，因为就不需要每次查询慢表。那这就是为什么快表机构能够大幅度地提升系统效能的一个原因。***

***![1089139-20190727222901429-873214700.png][]***

***在没有引入快表之前，我们访问一个逻辑地址至少需要两次访存。第一次访存是查询内存当中的页表，第二次访存才是访问我们最终想要访问的那个内存单元。而在引入了快表之后，如果快表命中的话，那么就只需要一次访存。如果快表未命中的话，我们仍然需要两次访存，仍然需要查询内存中的慢表。TLB当中我们只存有页表项的副本，存放的是页表项的副本，而普通的高速缓存当中存放的是其他数据的副本。所以TLB和Cache还是有区别的，不能混为一谈。***

***![1089139-20190727223645250-1522987765.png][]***

***介绍两级页表相关的一系列知识点。***

***![1089139-20190727223947268-1316236006.png][]***

***最后我们还会强调几个两级页表问题在考试当中有可能会作为考点的一个很重要的几个细节。那我们会按照从上至下的顺序依次讲解。***

***![1089139-20190727224157494-358737273.png][]***

***首先来看咱们之前介绍过的单级页表机制存在什么问题？而我们知道每一个页面需要对应一个页表项，那么这么多的页面就需要对应同等的2的20次方个页表项。而每个页表项的大小是4个字节，所以总共就需要2的22次方个字节来存储这个进程的页表。那这么多的字节，总共就是2的10次方个页框，也就是1024个页框。但是之前咱们讲过，为了实现通过页号查询对应的页表项这件事情，那么一般来说整个页表都是需要连续地存放在内存当中的。因此在这个系统当中，一个进程光它的页表就有可能需要占用连续的1024个页框来存放。那要为一个进程分配这么多的连续的内存空间，这显然是比较吃力的，并且这已经丧失了我们离散分配这种存储管理方式的最大的一个优点，所以这是单级页表存在的第一个很明显的缺陷、问题。***

***![1089139-20190728000041823-423532050.png][]***

***那第二个问题，由之前我们介绍过的局部性原理我们可以知道，很多时候其实进程在一段时间内只需要访问某几个特定的页面就可以正常地运行了。因此，我们没有必要让进程的整个页表都常驻内存，我们只需要让进程此时会用到的那些页面对应的页表项在内存当中保存就可以了，所以这是单级页表存在的第二个问题。***

***![1089139-20190728000809334-397692855.png][]***

***那么从刚才的分析当中我们知道，单级页表存在两个明显的问题。第一个问题就是页表必须连续地存放，所以如果页表很大的话，那么光页表就需要占用连续的很多个页框。那这和我们离散分配存储管理的这种思想其实是相悖的，所以我们要尝试解决这个问题。那第二个问题就是，我们没有必要让整个页表都常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面就可以顺利地执行了，那这是基于局部性原理得出的一个结论。那我们首先讨论第一个问题应该怎么解决。其实我们可以参考一下我们之前解决进程在内存当中必须连续存储的这个问题的时候，提出的那种思路。那我们之前的做法其实很简单，就是把进程的地址空间进行分页，然后再为进程建立一张页表，用来记录它的各个页面之间的顺序，还有保存的位置这些信息。那同样的思路其实我们也可以用来解决一个页表必须连续存储、连续占用多个页框的问题。***

转载于:https://www.cnblogs.com/ZHONGZHENHUA/p/11229540.html

[1089139-20190723082005215-372372272.png]: /images/20211116/f9d15666fa084656b784b9a9f1ab5675.png
[1089139-20190723082218650-1721573475.png]: /images/20211116/7eb69c3a627546b1a35d0fa226a17157.png
[1089139-20190723082316132-1174390813.png]: /images/20211116/434a9bddb52c46dca92189dcc3026d92.png
[1089139-20190723082454279-1425546888.png]: /images/20211116/d22dc88451f6459ea0ffafdc8a51de11.png
[1089139-20190723082529459-63476608.png]: /images/20211116/48c3469b05e543ecaa7ace732d174e31.png
[1089139-20190723091053812-1999818877.png]: /images/20211116/39815cabc54f4b598ffd9fcc1186e82e.png
[1089139-20190723094829545-1570999771.png]: /images/20211116/bdb02eccd330429f9933952fcb4c81bd.png
[1089139-20190723103145837-751454785.png]: /images/20211116/d1dd05832b8241afa8396c3d389570d4.png
[1089139-20190723113145455-555973761.png]: /images/20211116/a28af22e97d2494baddca17b367392b6.png
[1089139-20190723113216869-126109622.png]: /images/20211116/74b35a180cc34a7c84e8fb5a9da54508.png
[1089139-20190723113333734-568179118.png]: /images/20211116/2f926dc37bc84f309a5cafeea3f27bb4.png
[1089139-20190723113248436-2015528146.png]: /images/20211116/b24e26b44ddb4935aaedb22b42824ba9.png
[1089139-20190723113426895-34926779.png]: /images/20211116/ecb3935172dc47c0959da5d5cd3e57c6.png
[1089139-20190723115741088-1487168735.png]: /images/20211116/96cb3501bab34a5cb9dec6fbe7c57c90.png
[1089139-20190723133044612-1270825131.png]: /images/20211116/236c289e283c4d09b9181c29da67003d.png
[1089139-20190723134131467-1297337101.png]: /images/20211116/278e065e33e445b2817d15f19c8f465b.png
[1089139-20190723135424549-1542429346.png]: /images/20211116/ee4dfc9004a946c88d7f729b5f3a5a6c.png
[1089139-20190723152957442-842855987.png]: /images/20211116/7b27b4c94a284909b730d9f283614922.png
[1089139-20190723154205054-997356925.png]: /images/20211116/ea1cbad65ea64c22b2ebea1164848dd9.png
[1089139-20190723165041715-218193254.png]: /images/20211116/c80a1aaca00a4320860f0f7127412d57.png
[1089139-20190723175715402-2141167682.png]: /images/20211116/36b1585cc794440d83b93b2473206f25.png
[1089139-20190723181428448-814778709.png]: /images/20211116/e0b22aeab3334159803589b95cd8107d.png
[1089139-20190723183458089-2077023584.png]: /images/20211116/6637475377e844cd926843b44b6ac99f.png
[1089139-20190723214931745-765556194.png]: /images/20211116/1d0800546dd841ff9ffa226eb0026c9d.png
[1089139-20190723215039929-1356882695.png]: /images/20211116/d299dc13c98e4b79a839aa9395270261.png
[1089139-20190723214855823-1174357121.png]: /images/20211116/bf2e81d5ae14449694903b7a3c394dbf.png
[1089139-20190723220124686-1231486647.png]: /images/20211116/81a2cf5bf39149168a0ddbc71745d2da.png
[1089139-20190723222028995-675787367.png]: /images/20211116/1b3c45e5327a4a2c80208071fe458d26.png
[1089139-20190723230951794-403026333.png]: /images/20211116/576a1fee7ad54bcd93540101fcb519c3.png
[1089139-20190723233004866-6548088.png]: /images/20211116/ec108cc4665246ddb8fae81851e635f1.png
[1089139-20190723233029737-1331552331.png]: /images/20211116/f8e3397cb2644cc193438fbd3849435d.png
[1089139-20190724082642980-1816864951.png]: /images/20211116/46ed13a0deb742b4a5dea60484092d47.png
[1089139-20190724085328977-1433468422.png]: /images/20211116/b61071da694d4ac59cf28b6aa40e1a41.png
[1089139-20190724090046951-785152155.png]: /images/20211116/2330f89d4ed74dbda482fabc2145e3ed.png
[1089139-20190724103359751-716886403.png]: /images/20211116/c57bec7f483c44069c5c1c1b85605a2a.png
[1089139-20190724114204010-533788882.png]: /images/20211116/214a1347eac5477488ffc83af1856acc.png
[1089139-20190724115706891-1625705872.png]: /images/20211116/895b296a2a2046fbb02e3aa08b706477.png
[1089139-20190724121027993-1160703960.png]: /images/20211116/54b9616398f34e91816a436541651eac.png
[1089139-20190724124012959-911275835.png]: /images/20211116/9280c01fb80c4721999c6d5f5b97aed1.png
[1089139-20190724140151836-94710736.png]: /images/20211116/2a74671415c44beab7c460ccdeebb7da.png
[1089139-20190724140610741-691379200.png]: /images/20211116/2e95bac9d66246a4b8fa023b5eb1a1f7.png
[1089139-20190724144337075-1701750960.png]: /images/20211116/f31cbff4b12a4a158ff48ded5b769a35.png
[1089139-20190724150612369-64992430.png]: /images/20211116/fd19311ac4f74fc98a94fc3177128193.png
[1089139-20190724160621084-1485215526.png]: /images/20211116/b25a7ddaa800443c891992167d0d24d8.png
[1089139-20190724160836024-1742135568.png]: /images/20211116/a750a780ae8948eaab3a766c1d5fd7a7.png
[1089139-20190724161120344-37017275.png]: /images/20211116/e66c1a5756614b06972b4f471f9acad5.png
[1089139-20190724162821015-1438078101.png]: /images/20211116/a1a064ca602741529aeac983e6e50df4.png
[1089139-20190724165034199-279126842.png]: /images/20211116/aee3ca26305845c6b4fbda9dee1b7cf3.png
[1089139-20190724172639892-608547400.png]: /images/20211116/d8f7dfae3acc472da4ce32886f421e81.png
[1089139-20190724182457672-1887542779.png]: /images/20211116/1ee07f003b4440b38f08189b2d373f55.png
[1089139-20190724192229729-80545729.png]: /images/20211116/c2fcf3d9e0374c7ba7d2dfc309b561ff.png
[1089139-20190724191956678-1393996527.png]: /images/20211116/841990e8e541497cbb7dcf953ae95685.png
[1089139-20190724185921502-66146851.png]: /images/20211116/29f3ce0f47874b728b32f1264fa4a79e.png
[1089139-20190724192544443-466713429.png]: /images/20211116/89222ef5069143068bb600c925823a85.png
[1089139-20190724193325416-1077871430.png]: /images/20211116/77baa7489c194880acba8397f6526fad.png
[1089139-20190724213647740-1357067149.png]: /images/20211116/d92d291212474336b15ff98430541485.png
[1089139-20190724220002673-759406393.png]: /images/20211116/208ec9c38a28452bae55d79d14cfbd3a.png
[1089139-20190724214915354-1223599589.png]: /images/20211116/06f262a7a2d343339238096c65be5161.png
[1089139-20190724223659784-374031985.png]: /images/20211116/117e62058ac84c2aba67d58398ca9deb.png
[1089139-20190724230132468-821402980.png]: /images/20211116/444cb4bbbffd4e92811cf569064bc0b8.png
[1089139-20190725074104912-1129210966.png]: /images/20211116/19b78d7760f8432695a72b087f5a0a33.png
[1089139-20190725081840452-947576833.png]: /images/20211116/3537bf6e40414563b3c9904a5dd9c714.png
[1089139-20190725090751908-823718679.png]: /images/20211116/92f6976d3f9d4b4e9d9bbc48d9da964c.png
[1089139-20190725091118461-554699628.png]: /images/20211116/91a4c350645b4e699d903c9999f3e62f.png
[1089139-20190725103946931-62930451.png]: /images/20211116/27d0b3b1709e4972835126234407a187.png
[1089139-20190725105313342-1324699435.png]: /images/20211116/884a3c949f7b4e3a8404100411e78e20.png
[1089139-20190725112126732-1069026196.png]: /images/20211116/1534e35e546d4f669e3f0de0c6ca5f7a.png
[1089139-20190725123136790-1855541037.png]: /images/20211116/74ef2aa7bc8547f1a64728c8529441bb.png
[1089139-20190725124048568-506585841.png]: /images/20211116/1a712cbfacc54564bba12fb5dac98d89.png
[1089139-20190725125009607-462228434.png]: /images/20211116/0688a8a07bb740839a3a609ec85fa088.png
[1089139-20190725125758613-743077124.png]: /images/20211116/293220326abb427c9ce04d327bcf0454.png
[1089139-20190725130141019-1257283589.png]: /images/20211116/110d629809fe4b01a94c5027b9a76663.png
[1089139-20190725135625626-2108846864.png]: /images/20211116/266baa68c79b413583c48f2b013bad81.png
[1089139-20190725135712627-1821486473.png]: /images/20211116/ef5c96c4365a49f8b43947a29b0b877e.png
[1089139-20190725140356203-1077131809.png]: /images/20211116/e0a3d0a4981c46e09909616c5440f49e.png
[1089139-20190725141255708-1138075556.png]: /images/20211116/0ce428a374d6430fa94bfdca7a799721.png
[1089139-20190725151608417-116789934.png]: /images/20211116/2b3f974534fd467e8a59459ac3c61100.png
[1089139-20190725151427560-1567140390.png]: /images/20211116/0cc8826f5cb74155bc4a31f671bc2a78.png
[1089139-20190725155043279-208951317.png]: /images/20211116/bb209206e408427b97438e625dcc99a4.png
[1089139-20190725155334043-546502667.png]: /images/20211116/0e51ba99829e4d2baf4de60bc1d08e44.png
[1089139-20190725155729979-1147430726.png]: /images/20211116/71bdd4691ee9436a850ed818ec00c459.png
[1089139-20190725160045763-1281096227.png]: /images/20211116/92b30525f3bd484590135e02c88c805b.png
[1089139-20190725160324426-1355755324.png]: /images/20211116/ab265122b0b844bb9a4d7a7ce276eacc.png
[1089139-20190725160538734-829955781.png]: /images/20211116/c92e3cdd7e2847218db686abe91756b0.png
[1089139-20190725160700042-1061959230.png]: /images/20211116/84eaf178f07747029160ffc9e0428a45.png
[1089139-20190725164906647-568828220.png]: /images/20211116/2fdee369cf50409d9c56604044c9b3a2.png
[1089139-20190725170224956-1662513984.png]: /images/20211116/ce8b69652e5c48c9bdd3960cc50ccba7.png
[1089139-20190725170424231-1000095656.png]: /images/20211116/d40799312dff49ad85983f9c6c6e970f.png
[1089139-20190725170441955-1186852181.png]: /images/20211116/3846b2db1575466eb8a403dea6704dcc.png
[1089139-20190725170540523-1252365243.png]: /images/20211116/16000c7cb6944009acaf4cb9660fb029.png
[1089139-20190725165944422-624389351.png]: /images/20211116/238f7f5a5b5140349d311a56aa1843d4.png
[1089139-20190725171536622-533910199.png]: /images/20211116/1412d1a80f004f409373fa87e858cde0.png
[1089139-20190725172916282-1561245222.png]: /images/20211116/997ba079bbfe4a6db2747975856fec79.png
[1089139-20190725173949836-59563535.png]: /images/20211116/bddc2c01d7a4450d890c4c21cca369a8.png
[1089139-20190725191405171-988726738.png]: /images/20211116/e7de11ae7e964a5ba82d1e6b2d5038b8.png
[1089139-20190725192317371-1351325024.png]: /images/20211116/49e7c078652446efa67e5d71d5fb5b85.png
[1089139-20190725194303381-195878567.png]: /images/20211116/5110b364ec2547918d1d086c585e358b.png
[1089139-20190725194938219-2075956603.png]: /images/20211116/0d965c66f6be4562b6975842a495aedc.png
[1089139-20190725195054242-1521122759.png]: /images/20211116/de8beb22de2441e785a2613914b06d53.png
[1089139-20190725195310372-839085653.png]: /images/20211116/7e67f59a6cc04900b1bc0086ab44f736.png
[1089139-20190725195413886-1988011404.png]: /images/20211116/61a9f7e34f404464b59519b9be0317b5.png
[1089139-20190725195445023-888585401.png]: /images/20211116/9254dd169ccc4b1696d147aec93231ab.png
[1089139-20190725200204003-1780376688.png]: /images/20211116/08ae21c034f943c7b194f1db1c49bbe5.png
[1089139-20190725220906778-346489362.png]: /images/20211116/01916ade65a14d1e9e05f6197b5bf5dd.png
[1089139-20190725222917102-694399268.png]: /images/20211116/4c2aacf1384b499e97740771b8ec6f8a.png
[1089139-20190725223707086-1818101114.png]: /images/20211116/cd97dd7c81534a1bb1cab8bbf68d8742.png
[1089139-20190725224111224-598799137.png]: /images/20211116/09f33551053c49dfabb99bbd2e107e0d.png
[1089139-20190725234821044-130411865.png]: /images/20211116/17ee57b6d1854191be557da01fbfe3d4.png
[1089139-20190725235418407-1623150425.png]: /images/20211116/12cd19d6ac6b4890808c65b6cb9558f3.png
[1089139-20190725235726038-1929726782.png]: /images/20211116/c7181b9dda524d3092550b831c6bdf64.png
[1089139-20190726094759844-944697582.png]: /images/20211116/e434a02cc16f451aae9f904c55ccb1b2.png
[1089139-20190726101816183-686214286.png]: /images/20211116/f49de43b9fe04f789ed0e5dbc23fef14.png
[1089139-20190726102256975-883676143.png]: /images/20211116/a8dab6dfe4e349f681170796445ecb60.png
[1089139-20190726102427273-379150432.png]: /images/20211116/b6ff78fdab444fd28285534d849b0c65.png
[1089139-20190726105350621-827847496.png]: /images/20211116/175a49f7b2a04549bac01a8ccab8fa3c.png
[1089139-20190726105627449-1781003744.png]: /images/20211116/5a742ec9508349189ece87a4bb90322d.png
[1089139-20190726110147338-490193075.png]: /images/20211116/1ab929ac14244074b90da4f40736e5b3.png
[1089139-20190726110210381-1515899218.png]: /images/20211116/6a5308e75b024696b0afb2ac531ffd12.png
[1089139-20190726110359644-325222893.png]: /images/20211116/8274c3bc3a894186bd21eddbe07dfdaf.png
[1089139-20190726110723724-2101603545.png]: /images/20211116/bd62fa26547c4dd893c518b3ab328287.png
[1089139-20190726111652856-409068835.png]: /images/20211116/3b8e152f4657456fa5cbc6cd0d41d869.png
[1089139-20190726113716748-585727858.png]: /images/20211116/071803574b454441a997a14ff9c39264.png
[1089139-20190726120739018-920023012.png]: /images/20211116/be33e09d7aee4e1494d41ec195600173.png
[1089139-20190726131721503-672355150.png]: /images/20211116/a92aa18ae6fa46d2a106e48dcb51483f.png
[1089139-20190726131913704-1528673607.png]: /images/20211116/301a19a356b84653a2e19401e922835c.png
[1089139-20190726135406527-1105944431.png]: /images/20211116/c569d9dccfd648e89c3fcf315d33e255.png
[1089139-20190726140300261-1983976793.png]: /images/20211116/2884f2207e1f4fd2ae0225ca33275996.png
[1089139-20190726161628804-1418909815.png]: /images/20211116/588355f028a146968413bf18e205e15f.png
[1089139-20190726162111940-650971293.png]: /images/20211116/4ff17073074b4885983f37aedbfb234d.png
[1089139-20190726164228629-622018616.png]: /images/20211116/5712e9497d2a4ee6b5dfda2265f457d4.png
[1089139-20190726171801255-361992954.png]: /images/20211116/0427c5dd55f241579a9027dd3b6add99.png
[1089139-20190726172610297-349795956.png]: /images/20211116/d0fe26100f4e4180aea35d99913fe9ce.png
[1089139-20190726174732951-15354039.png]: /images/20211116/ccb89384270f4aa79f8c41039166f586.png
[1089139-20190726175145796-1574688722.png]: /images/20211116/8d26568a3f934607a7556e4c809f050a.png
[1089139-20190726175218327-295027565.png]: /images/20211116/3b503b3f5ca64009b23d7f4de92c24ff.png
[1089139-20190726191206818-119005852.png]: /images/20211116/c04217de258f4567ac2c2397a78ce8b5.png
[1089139-20190726192439103-1331338369.png]: /images/20211116/56e699e2659c4687b7f06943f8539dd1.png
[1089139-20190726194730536-2133579389.png]: /images/20211116/cde9bd9cbba245cc8fcd014721a9f618.png
[1089139-20190726195823424-1575465396.png]: /images/20211116/5aab82a761cf486b91fca474f424490e.png
[1089139-20190726220944064-1142790551.png]: /images/20211116/49489f88681c410881ac3f4a97ef27df.png
[1089139-20190726222322251-1485760542.png]: /images/20211116/20e95152aa334f0dbb1da41ad30e3820.png
[1089139-20190726225926976-795232152.png]: /images/20211116/55da2a792fbc4787a5adf651fbd4e755.png
[1089139-20190726230543980-536157606.png]: /images/20211116/bd21447539544351892672114a9b6025.png
[1089139-20190726232415783-485637464.png]: /images/20211116/db103183de614425a800bb0d57124c73.png
[1089139-20190727001355365-560222204.png]: /images/20211116/b67cfb6981e9430aba88c126d6c15360.png
[1089139-20190727002739220-834080230.png]: /images/20211116/ca7870276c524cb1ac6beb6c0b5dca11.png
[1089139-20190727004117145-1417707652.png]: /images/20211116/40093394d0254d929dafcd34c8fb1672.png
[1089139-20190727102552410-1424782379.png]: /images/20211116/255e62426ac34b359d26443add1e6f1f.png
[1089139-20190727102116038-1564185951.png]: /images/20211116/2c37d8b4756149bd858d9c8598379752.png
[1089139-20190727110900839-1421623194.png]: /images/20211116/4a9fce40cb954492b4fe90a06552cc48.png
[1089139-20190727113130205-55877941.png]: /images/20211116/4afa2281ad0b4d2b88aa42e72645685e.png
[1089139-20190727115459524-1254574716.png]: /images/20211116/e63ff4f7224848ed995129c55138d9f8.png
[1089139-20190727122722238-1778016372.png]: /images/20211116/104f9d4d264540e79530651258b9a2ac.png
[1089139-20190727123234909-322098420.png]: /images/20211116/4b2328d1201f47dd8b7e5a90d1c97ca9.png
[1089139-20190727123644460-1229069571.png]: /images/20211116/d1abe7f322a44e978f93b9babd30dcb3.png
[1089139-20190727152244393-1417443521.png]: /images/20211116/524cfb63581e4fa9bc8d46c9cf57c7a6.png
[1089139-20190727152846765-1873996680.png]: /images/20211116/0dce92a421384275bcb09fe196e7414d.png
[1089139-20190727153608051-477628525.png]: /images/20211116/14b281f07d914465972d3de0fc6a4907.png
[1089139-20190727182308314-346299224.png]: /images/20211116/bac693be2de44a11a6f0bf39529df039.png
[1089139-20190727182728878-450023022.png]: /images/20211116/6516e912591a45f480bdb581179405ac.png
[1089139-20190727184102091-654627088.png]: /images/20211116/6cbb7ddda8e74a639bcb72b0b1171f2d.png
[1089139-20190727190648251-1721798110.png]: /images/20211116/9ff4cf45c41247f9a68aa866521fa72f.png
[1089139-20190727191108010-1830193148.png]: /images/20211116/881c7e6968dd4a71adaf96386e35b4e4.png
[1089139-20190727190940582-77654989.png]: /images/20211116/7dec2318ea234fd8ba65773688124712.png
[1089139-20190727191259575-409043995.png]: /images/20211116/c9405e12c3364fbf97bb370874653f6f.png
[1089139-20190727191956069-1279965054.png]: /images/20211116/8d4ed9149457407082afb90c87695649.png
[1089139-20190727200255638-1639543695.png]: /images/20211116/3e2d18eb1f1a464bb2150e80c9830514.png
[1089139-20190727210148783-1576119725.png]: /images/20211116/dfadc66a53f6454baf8851d9314bc01d.png
[1089139-20190727221326162-1159729536.png]: /images/20211116/c27461ac6e254698b624f602eb4790c0.png
[1089139-20190727222901429-873214700.png]: /images/20211116/697b86d714294b2aabd9187e1b6c5b8b.png
[1089139-20190727223645250-1522987765.png]: /images/20211116/c5f9120db4d84ed6ad2b80e06447e6a8.png
[1089139-20190727223947268-1316236006.png]: /images/20211116/baf1a4ac29204cee981fa4e45789f33f.png
[1089139-20190727224157494-358737273.png]: /images/20211116/4e93a25d4aca44b39aeff59bd57acdca.png
[1089139-20190728000041823-423532050.png]: /images/20211116/2153e915ff934a6db57cd20d4927caac.png
[1089139-20190728000809334-397692855.png]: /images/20211116/c231f852e4634bd0892a908f0a75c2b9.png