第四章內(nèi)存管理(三)

河北科技師范學(xué)院大專課程

操作系統(tǒng)第十八講主講人：曾曉寧2023/2/6第4章內(nèi)存管理4.1內(nèi)存管理功能4.2分區(qū)管理4.3頁式管理4.4段式管理4.5段頁式管理2023/2/64.2.3可變分區(qū)內(nèi)存不事先進(jìn)行劃分，而是在裝入程序時(shí)，根據(jù)裝入程序的實(shí)際需要來分配內(nèi)存空間，這樣，內(nèi)存分區(qū)的個(gè)數(shù)、各分區(qū)的大小、在內(nèi)存中活動(dòng)的內(nèi)存?zhèn)€數(shù)都是隨時(shí)間變化的。2023/2/64、分區(qū)的回收回憶復(fù)習(xí)回收區(qū)不與任何空閑區(qū)相鄰；回收區(qū)與后空閑區(qū)相鄰；回收區(qū)與前空閑區(qū)相鄰；回收區(qū)與前后兩個(gè)空閑區(qū)相鄰；2023/2/64.2.4碎片問題及其解決辦法這種不能被任何用戶使用的極小的空閑區(qū)稱為碎片。碎片的出現(xiàn)造成了存儲(chǔ)空間的浪費(fèi)。采用移動(dòng)技術(shù)，把在內(nèi)存中的所有進(jìn)程移動(dòng)到內(nèi)存的一端，同時(shí)修改每個(gè)進(jìn)程的基址、限長(zhǎng)值，從而把內(nèi)存中分散的碎片集中在一起，形成一個(gè)較大的空閑分區(qū)，以便裝入較大的程序。2023/2/64.2.5覆蓋技術(shù)與交換技術(shù)把程序劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序段，并規(guī)定好它們的執(zhí)行和覆蓋次序，然后讓那些不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存分區(qū)；并把這些程序段組成一組，稱為覆蓋段，而把共享的內(nèi)存分區(qū)稱為覆蓋區(qū)。覆蓋段與覆蓋區(qū)一一對(duì)應(yīng)；交換是指把主存中暫時(shí)不能運(yùn)行的進(jìn)程，或暫時(shí)不用的程序和數(shù)據(jù)，換出到外存上，把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需要的程序或數(shù)據(jù)，換入主存的技術(shù)。2023/2/64.3頁式管理

頁式管理允許將程序分散地裝入到內(nèi)存中若干個(gè)不連續(xù)的空閑分區(qū)中，可以全部裝入，也可以部分裝入。即有效地解決了碎片問題，又能充分利用內(nèi)存空間，提高了內(nèi)存利用率。2023/2/61、頁面（用戶程序劃分）

把用戶進(jìn)程的邏輯地址空間劃分成若干個(gè)大小相等的區(qū)域，每個(gè)區(qū)域稱為一個(gè)頁面。簡(jiǎn)稱頁。程序的各頁面從0開始依次編號(hào)，稱為頁號(hào)。頁內(nèi)地址：每個(gè)頁面從0開始依次編址，稱為頁內(nèi)地址。2、物理塊系統(tǒng)將內(nèi)存空間按頁面大小劃分為大小相等的若干個(gè)存儲(chǔ)塊，稱為塊或物理塊（塊，頁框）；內(nèi)存的所有物理塊也從0開始依次編號(hào)，稱為塊號(hào)；每個(gè)塊從0開始依次編址，稱為塊內(nèi)地址。2023/2/6裝入方法：在裝入程序時(shí)，內(nèi)存以塊為單位進(jìn)行分配，程序的任一頁可以裝入內(nèi)存的任一塊中，實(shí)現(xiàn)了離散分配。但由于程序的最后一頁經(jīng)常裝不滿一塊，會(huì)形成不可利用的碎片，稱為“頁內(nèi)碎片”，每個(gè)頁內(nèi)碎片的大小不會(huì)超過一頁。2023/2/63、邏輯地址結(jié)構(gòu)設(shè)邏輯地址為n位頁內(nèi)地址為m位則每頁大小為2m最多包含2n-m頁mn-mn2023/2/6計(jì)算時(shí)要注意：若給出的地址為16進(jìn)制，則將其轉(zhuǎn)換為二進(jìn)制，然后，根據(jù)頁長(zhǎng)及邏輯地址的長(zhǎng)度，分別取出邏輯地址的高幾位和低幾位就得到頁號(hào)及頁內(nèi)地址。如頁長(zhǎng)為2K，邏輯地址為16位，則高5位為頁號(hào)，低11位為頁內(nèi)地址。若給出的地址為10進(jìn)制，則用公式：

邏輯/頁長(zhǎng)商為頁號(hào)，余數(shù)為頁內(nèi)地址。如程序地址為8457，

頁長(zhǎng)為4KB，則8457/4096可得：商為2，余數(shù)為256?；貞浗Y(jié)束2023/2/6思想：要求程序全部裝入內(nèi)存后，才能開始運(yùn)行。在裝入程序時(shí)，首先把程序劃分成若干個(gè)大小相等的頁面，然后系統(tǒng)按塊為單位，將程序的每一頁分散地裝入到內(nèi)存的物理塊中；一個(gè)程序有多少頁，就給它分配多少物理塊，且這些物理塊可以不連續(xù)。4.3.2靜態(tài)頁式管理2023/2/61、頁表頁面系統(tǒng)為了能在內(nèi)存中找到每個(gè)頁面對(duì)應(yīng)的物理塊而為進(jìn)程建立一張頁面映像表，簡(jiǎn)稱頁表。頁表作用：實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射。記錄了頁面與內(nèi)存物理塊之間的對(duì)應(yīng)關(guān)系。包含頁號(hào)和塊號(hào)兩項(xiàng)內(nèi)容。2023/2/6頁表的特點(diǎn)系統(tǒng)為每個(gè)用戶進(jìn)程建立一張頁表，頁表的長(zhǎng)度隨用戶程序的大小而定；每個(gè)頁面在頁表中占一個(gè)表項(xiàng)；頁表大多駐留在內(nèi)存中，其長(zhǎng)度和首地址存放在該程序?qū)?yīng)進(jìn)程的PCB中。2023/2/60頁1頁0頁1頁2頁02150017230123456789程序A程序B程序A頁表程序B頁表內(nèi)存空間靜態(tài)頁式管理2023/2/62、靜態(tài)頁式管理的內(nèi)存分配與回收為了實(shí)現(xiàn)頁式存儲(chǔ)管理方式，系統(tǒng)設(shè)置了主存分配表、位示圖和頁表，記錄主存空間的使用情況和每個(gè)作業(yè)的分配情況。2023/2/62023/2/6（1）位示圖位示圖由內(nèi)存中的若個(gè)字節(jié)組成，位示圖的每一位對(duì)應(yīng)內(nèi)存中的一個(gè)塊，當(dāng)其值為0時(shí)，表示對(duì)應(yīng)的物理塊空閑；為1時(shí)，表示已分配。見書P151例11101001101010102023/2/6主存空間的分配過程為：首先，系統(tǒng)要初始化位示圖，即把位示圖中的標(biāo)志位全部置為“0”，空閑塊數(shù)置為主存的塊數(shù)。其次，在進(jìn)行主存分配時(shí)，從作業(yè)隊(duì)列中取出隊(duì)首作業(yè)，計(jì)算該作業(yè)的頁數(shù)，然后，與位示圖中的空閑塊數(shù)比較；若不能滿足作業(yè)的要求，則作業(yè)不能裝入，顯示主存不足的信息，把該作業(yè)放到隊(duì)尾或刪除該作業(yè)；若能滿足作業(yè)的空間要求，則為該作業(yè)建立頁表，并根據(jù)位示圖中主存塊的狀態(tài)標(biāo)志，找出標(biāo)志為“0”的那些位，置上占用標(biāo)志“1”，2023/2/6把作業(yè)頁裝入對(duì)應(yīng)的主存塊，并在頁表中填入對(duì)應(yīng)的塊號(hào)。直到所有作業(yè)頁全部裝入。最后，修改位示圖中空閑塊數(shù)，即原有空閑塊數(shù)減去本次占用的塊數(shù)（頁數(shù)）。2023/2/6（2）空閑塊鏈將所有空閑塊鏈接成一個(gè)空閑塊鏈。每次分配時(shí)，從鏈?zhǔn)组_始，根據(jù)程序的大小依次摘下若干個(gè)空閑塊進(jìn)行分配?；厥湛臻e塊時(shí)，將其插入空閑塊鏈的末尾。2023/2/6（3）內(nèi)存分塊表包含塊號(hào)、進(jìn)程號(hào)、頁號(hào)和狀態(tài)等信息，用于記錄內(nèi)存中所有塊的使用情況。當(dāng)狀態(tài)為0時(shí)，表示該塊空閑，當(dāng)狀態(tài)為1時(shí)，表示該塊已分配，并記錄了該塊是由哪個(gè)進(jìn)程的哪一頁所占用。內(nèi)存中的每一塊在內(nèi)存分塊表中都有一個(gè)表項(xiàng)。2023/2/6在進(jìn)行內(nèi)存分配時(shí)，首先要看空閑塊數(shù)是否能滿足程序的要求，若不能，則不進(jìn)行分配；否則在內(nèi)存分塊表中找出狀態(tài)為“0”的若干塊，將其中狀態(tài)置為1，填寫每塊中裝入的頁號(hào)，以及該頁所屬的進(jìn)程號(hào)；并把當(dāng)前空閑塊減去本次分配的塊數(shù)。分配2023/2/6回收當(dāng)進(jìn)程結(jié)束時(shí)，應(yīng)回收其占用的物理塊。根據(jù)進(jìn)程號(hào)檢索內(nèi)存分塊表，將匹配表項(xiàng)的狀態(tài)修改為0；并把回收的塊數(shù)加到當(dāng)前空閑塊數(shù)中。2023/2/63、地址轉(zhuǎn)換分頁中的地址映射其實(shí)與通常的地址映射的概念是一樣的，即把程序地址轉(zhuǎn)換成內(nèi)存地址，這個(gè)轉(zhuǎn)換過程是在程序執(zhí)行過程中完成的，是動(dòng)態(tài)地址映射。在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，由系統(tǒng)提供的地址映射硬件來完成地址映射工作。2023/2/6實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換。實(shí)際上是把邏輯地址中的頁號(hào)，轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。地址變化任務(wù)是借助于頁表來完成的?；救蝿?wù)2023/2/6頁表由一組專門的寄存器來實(shí)現(xiàn)，一個(gè)頁表專用一個(gè)寄存器。頁表大多駐留在內(nèi)存中。系統(tǒng)中只設(shè)置一個(gè)頁表寄存器，存放頁表在內(nèi)存的起始地址和頁表的長(zhǎng)度。進(jìn)程未執(zhí)行時(shí)，頁表的始值和頁表長(zhǎng)度存放在本進(jìn)程PCB中。當(dāng)調(diào)度到進(jìn)程時(shí)裝入頁表寄存器中。2023/2/6地址轉(zhuǎn)換過程：當(dāng)進(jìn)程要訪問某個(gè)邏輯地址中的數(shù)據(jù)時(shí)，由系統(tǒng)自動(dòng)將邏輯地址分為頁號(hào)和頁內(nèi)地址兩部分；將頁號(hào)與頁表寄存器中的頁表長(zhǎng)度進(jìn)行比較，如果頁號(hào)大于等于頁表長(zhǎng)度，則表示本次所訪問的地址已超越作業(yè)的地址空間。這一錯(cuò)誤將被系統(tǒng)發(fā)現(xiàn)并產(chǎn)生“地址越界”中斷。若未出現(xiàn)越界錯(cuò)誤，則將頁表始址+頁號(hào)×頁表項(xiàng)長(zhǎng)度，便得到該表項(xiàng)在頁表中的位置，可以從中得到該頁的物理塊號(hào)；2023/2/6將塊號(hào)裝入物理地址寄存器中。與此同時(shí)，再將邏輯地址寄存器中的頁內(nèi)地址，直接送入物理地址寄存器的塊內(nèi)地址字段中。經(jīng)過硬件機(jī)制，把物理地址寄存器中的塊號(hào)和塊內(nèi)地址，轉(zhuǎn)換成物理地址。這樣，便完成了從邏輯地址到物理地址的變換。頁式地址轉(zhuǎn)換過程如圖3-18所示。2023/2/6越界中斷頁表始址頁表長(zhǎng)度頁表寄存器頁號(hào)塊號(hào)邏輯地址頁號(hào)P塊號(hào)P’頁號(hào)P頁內(nèi)地址W物理地址塊號(hào)P’塊內(nèi)地址W＞頁表2023/2/6例1設(shè)有8頁的邏輯空間，每頁有1024字節(jié)，它們被映射到32塊的物理存儲(chǔ)區(qū)中，那么，邏輯地址的有效位是多少位？物理地址至少多少位？2023/2/6例2在一分頁存儲(chǔ)管理系統(tǒng)中，邏輯地址長(zhǎng)度為16位，頁面大小為2048B，對(duì)應(yīng)的頁表如表所示，現(xiàn)有兩邏輯地址為0A5CH和2F6AH，經(jīng)過地址變換后所對(duì)應(yīng)的物理地址各是多少？頁號(hào)塊號(hào)0511024372023/2/6解：由題設(shè)條件可知，分頁存儲(chǔ)管理系統(tǒng)的邏輯地址結(jié)構(gòu)為：頁號(hào)P頁內(nèi)位移W0101115PWBW邏輯地址0A5CH的頁號(hào)為1，從表中右知此頁對(duì)應(yīng)的物理塊號(hào)B為10，所以，將二進(jìn)制表示的頁號(hào)換為塊號(hào)得：01010010010111000000101001011100邏輯地址0A5CH的二進(jìn)制表示如下：用16進(jìn)制表示即為525CH。2023/2/6PW0010111101101010邏輯地址2F6AH的二進(jìn)制表示如下：也即，邏輯地址2F6A的頁號(hào)為5，查表已超過頁表長(zhǎng)度，故產(chǎn)生越界中斷。2023/2/6例3在某個(gè)采用頁式存儲(chǔ)管理的系統(tǒng)中，現(xiàn)有J1、J2和J3共3個(gè)作業(yè)同駐主存，其中J2有4個(gè)頁面，被分別裝入到主存的第3、4、6、8塊中。假定頁面和存儲(chǔ)塊的大小均為1024字節(jié)，主存容量為10KB字節(jié)。（1）寫出J2的頁面映像表；（2）當(dāng)J2在CPU上運(yùn)行時(shí)，執(zhí)行到其地址空間第500號(hào)處遇到一條傳送指令：

MOV2100，3100請(qǐng)用地址變換圖計(jì)算MOV指令中兩個(gè)操作數(shù)的物理地址。2023/2/6（1）J2的頁表如表所示：頁號(hào)塊號(hào)031426382023/2/6（2）已知頁面大小為1024字節(jié)，可知頁內(nèi)位移為10位；P=[A/L]d=AmodL則邏輯地址2100的頁號(hào)為2，頁內(nèi)位移為2100-2048=52；則邏輯地址3100的頁號(hào)為3，頁內(nèi)位移為3100-3072=28；邏輯地址2100的地址變換過程如下圖所示：2023/2/6越界中斷頁表始址頁表長(zhǎng)度頁表寄存器頁號(hào)塊號(hào)邏輯地址

0

3

1

4

6252物理地址

6

52＞頁表

3

8

26196主存6×1024+522023/2/6越界中斷頁表始址頁表長(zhǎng)度頁表寄存器頁號(hào)塊號(hào)邏輯地址

0

3

1

4

6328物理地址

8

28＞頁表

3

8

28220主存8×1024+282023/2/6根據(jù)上圖可得出邏輯地址2100所對(duì)應(yīng)的物理地址為6196，同理，邏輯地址3100所對(duì)應(yīng)的物理地址為8220。2023/2/6練習(xí)若某頁式管理系統(tǒng)的主存容量為64KB，被分成1