l           區(qū)分邏輯地址與絕對地址

絕對地址：主存儲器以字節(jié)為編址單位，容量為n的主存儲器中，每個(gè)單元有唯一的編號，從0到n-1，這個(gè)唯一的編號就是主存儲器的物理地址也叫絕對地址。

    邏輯地址:在多道程序設(shè)計(jì)的系統(tǒng)中，操作系統(tǒng)為了方便用戶，就允許每個(gè)用戶都認(rèn)為自己作業(yè)的程序和數(shù)據(jù)存放在地址從 0開始的連續(xù)空間中。這樣用戶程序中使用的地址就是邏輯地址也叫相對地址。 

l          對主存儲器為什么要區(qū)分絕對地址和邏輯地址？

中央處理器訪問主存時(shí)必須指定確切的存儲單元。在計(jì)算機(jī)系統(tǒng)中通常對主存儲器以字節(jié)（每個(gè)字節(jié)8個(gè)二進(jìn)制位）為編址單位，每個(gè)字節(jié)都有一個(gè)地址與其對應(yīng)，這樣的地址稱為主存儲器的“絕對地址”。

在多道程序設(shè)計(jì)系統(tǒng)中，主存中同時(shí)存放了多個(gè)用戶作業(yè)。操作系統(tǒng)根據(jù)主存的使用情況為用戶分配主存空間。每個(gè)用戶不能預(yù)先知道他的作業(yè)將被存放到主存儲器的什么地方。這樣，用戶程序中就不能使用主存的絕對地址。為了方便用戶，允許用戶程序中使用“邏輯地址”，每個(gè)用戶都可認(rèn)為自己作業(yè)的程序和資料存放在一組從“0”地址開始的連續(xù)的邏輯地址空間中。 

l          重定位

為了保證作業(yè)的正確執(zhí)行，必須根據(jù)分配給作業(yè)的主存區(qū)域?qū)ψ鳂I(yè)中指令和數(shù)據(jù)的存放進(jìn)行重定位，這種把邏輯地址轉(zhuǎn)換成絕對地址的工作稱為“重定位”或“地址轉(zhuǎn)換”。重定位的方式有“靜態(tài)重定位”和“動態(tài)重定位”兩種。

(1)靜態(tài)重定位

在裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對地址。這種轉(zhuǎn)換工作是在作業(yè)開始前集中完成的，在作業(yè)執(zhí)行過程中無需再進(jìn)行地址轉(zhuǎn)換。所以稱為“靜態(tài)重定位”。圖4_2.1指出了靜態(tài)重定位的過程。

在圖4－2.l中，假定用戶作業(yè)的邏輯地址空間從“0”到“124”，其中第8號單元處有一條“加法”指令，該指令要求從第32號單元處取出操作數(shù)3465，然后進(jìn)行加法操作。如果存儲管理為該作業(yè)分配的主存區(qū)域是從100單元開始，那么，邏輯地址第8號單元在主存中的對應(yīng)位置是108單元，第32號單元在主存中的對應(yīng)位置應(yīng)該是132單元。如果不修改上述“加法”指令中的操作數(shù)地址，則處理器執(zhí)行該指令時(shí)將從主存的032單元中去取操作數(shù)，這顯然是錯(cuò)誤的。于是，應(yīng)把程序中所有邏輯地址都轉(zhuǎn)換成絕對地址。上述加法指令中的操作數(shù)地址也應(yīng)改成132。這樣，在執(zhí)行指令時(shí)便可從132單元取到正確的操作數(shù)。

(2)動態(tài)重定位

在裝入一個(gè)作業(yè)時(shí)，不進(jìn)行地址轉(zhuǎn)換，而是直接把作業(yè)裝到分配的主存區(qū)域中。在作業(yè)執(zhí)行過程中，每當(dāng)執(zhí)行一條指令時(shí)都由硬件的地址轉(zhuǎn)換機(jī)構(gòu)轉(zhuǎn)換成絕對地址。這種方式的地址轉(zhuǎn)換是在作業(yè)執(zhí)行時(shí)動態(tài)完成的，所以稱為動態(tài)重定位。圖4_2.2指出了動態(tài)重定位的過程。

在圖4－2.2中，基址寄存器中存放了作業(yè)所在主存區(qū)域的起始地址100。當(dāng)處理器從108單元取出指令后，該指令中的邏輯地址是032，把基址寄存器中的值100與邏輯地址032相加得到絕對地址132，處理器便可從132單元中取出正確的操作數(shù)。

  點(diǎn)擊見相關(guān)動畫

l          什么是“程序浮動”？為什么動態(tài)重定位能支持程序浮動？

若在作業(yè)的執(zhí)行過程中改變了該作業(yè)在主存中的存放區(qū)域后，該作業(yè)仍然能正確執(zhí)行，則稱該作業(yè)的程序是可浮動的。采用動態(tài)重定位的系統(tǒng)能支持“程序浮動”。這是因?yàn)閯討B(tài)重定位是在每執(zhí)行一條指令時(shí)進(jìn)行地址轉(zhuǎn)換的。當(dāng)作業(yè)在主存中的位置被移動后，只要把新區(qū)域的起始地址存入基址寄存器中，作業(yè)繼續(xù)執(zhí)行時(shí)硬件的地址轉(zhuǎn)換機(jī)構(gòu)就會按基址寄存器中新存入的地址與邏輯地址相加，所得的絕對地址就是新區(qū)域中的存儲單元地址，作業(yè)當(dāng)然仍可正確執(zhí)行。

　第三節(jié)    分區(qū)存儲管理 

l          什么是分區(qū)存儲管理？

分區(qū)存儲管理是把存儲器中的用戶區(qū)作為一個(gè)連續(xù)區(qū)或分成若干連續(xù)區(qū)進(jìn)行管理。早先使用一個(gè)分區(qū)的存儲管理，后發(fā)展成多分區(qū)的存儲管理。多個(gè)分區(qū)的管理可采用固定分區(qū)方式和可變分區(qū)方式。 

l          一個(gè)分區(qū)的存儲管理

(1)     一個(gè)分區(qū)的存儲管理

     又稱單連續(xù)存儲管理，是最簡單的存儲管理方式。除操作系統(tǒng)占用的一部分存儲空間外，其余的用戶區(qū)域作為一個(gè)連續(xù)的分區(qū)分配給一個(gè)作業(yè)使用，即在任何時(shí)刻主存儲器中最多只有一個(gè)作業(yè)。一個(gè)分區(qū)的存儲管理只適用于單用戶的情況。

(2)     一個(gè)分區(qū)的存儲管理方法

    等待裝入主存儲器的作業(yè)排成一個(gè)作業(yè)隊(duì)列。當(dāng)主存儲器中無作業(yè)或一個(gè)作業(yè)執(zhí)行結(jié)束；就可以讓作業(yè)隊(duì)列中的一個(gè)作業(yè)裝入主存儲器。如圖4_3.1所示。

l          固定分區(qū)存儲管理

(1) 固定分區(qū)

固定分區(qū)是指把主存儲器中可分配的用戶區(qū)域預(yù)先劃分成若干個(gè)連續(xù)區(qū)。每個(gè)連續(xù)區(qū)的大小可以相同，也可以不同。但是一旦劃分好分區(qū)之后，主存儲器中分區(qū)的個(gè)數(shù)就固定了，且每個(gè)分區(qū)的大小也固定不能再變。

(2)  固定分區(qū)存儲管理的原理

    圖4_3.2是劃分成三個(gè)分區(qū)的固定分區(qū)管理方式的示意圖。

(3) 主存空間的分配與去配

設(shè)置一張“主存分配表”，以說明各分區(qū)的分配情況。主存分配表中應(yīng)指出各分區(qū)的起始地址和長度，并為每個(gè)分區(qū)設(shè)一個(gè)標(biāo)志位。當(dāng)標(biāo)志位為“0”時(shí)，表示對應(yīng)的分區(qū)是空閑分區(qū)，當(dāng)標(biāo)志位為非“0”時(shí)，表示對應(yīng)的分區(qū)已被占用。空閑分區(qū)可以用來裝作業(yè)，已被占用的分區(qū)需指出被哪個(gè)作業(yè)占用。

用“順序分配算法”進(jìn)行主存空間的分配。順序查看主存分配表，找到一個(gè)標(biāo)志為“0”的分區(qū)，再把欲裝入作業(yè)的邏輯地址空間的長度與找到的分區(qū)長度進(jìn)行比較。當(dāng)能容納該作業(yè)時(shí)，則把此分區(qū)分配給該作業(yè)，把它的作業(yè)名填到占用標(biāo)志位上。當(dāng)找到的分區(qū)不能容納該作業(yè)時(shí)，則重復(fù)上述過程繼續(xù)順序查看主存分配表中是否有能滿足該作業(yè)長度要求的且標(biāo)志為“0”的分區(qū)，若有，則分配，若無，則該作業(yè)暫時(shí)得不到主存空間而不能裝入。

(4) 地址轉(zhuǎn)換

固定分區(qū)管理可采用靜態(tài)重定位的方式裝入作業(yè)。裝入程序把作業(yè)中的邏輯地址轉(zhuǎn)換為絕對地址與分區(qū)的下限地址相加，得到相應(yīng)的絕對地址。

(5) 存儲保護(hù)

實(shí)現(xiàn)存儲保護(hù)需要軟件與硬件相互配合。采用固定分區(qū)方式管理時(shí)，處理器中應(yīng)設(shè)置兩個(gè)寄存器：下限寄存器和上限寄存器。

當(dāng)一個(gè)被裝入分區(qū)的作業(yè)能占用處理器時(shí)，由操作系統(tǒng)把該分區(qū)的上限地址和下限地址分別存入處理器的上限寄存器和下限寄存器之中。處理器執(zhí)行該作業(yè)時(shí)，對每條指令中的地址都要核對絕對地址是否在上下限地址之間，即核對

          “下限地址＜絕對地址＜上限地址”

是否成立。若成立，表示絕對地址在規(guī)定的分區(qū)之內(nèi)，可按絕對地址訪問主存，否則便形成“地址越界”的程序性中斷事件。從而達(dá)到存儲保護(hù)的目的。

當(dāng)一個(gè)作業(yè)讓出處理器時(shí)，另一作業(yè)可能被選中占用處理器。這時(shí)應(yīng)更改上、下限寄存器的內(nèi)容為當(dāng)前被選中作業(yè)所在分區(qū)的上限地址和下限地址，以保證處理器能控制每個(gè)作業(yè)都在規(guī)定的分區(qū)內(nèi)執(zhí)行。

(6) 固定分區(qū)管理方式不能充分利用主存空間

采用固定分區(qū)方式管理主存時(shí)，規(guī)定每個(gè)分區(qū)只能裝入一個(gè)作業(yè)，且總是要為作業(yè)分配一個(gè)不小于作業(yè)長度的分區(qū)。這樣就有可能造成很多作業(yè)實(shí)際上只占用了分區(qū)的一部分空間，使分區(qū)中有一部分空間不能被利用，影響了主存空間的利用率。

(7) 固定分區(qū)管理方式提高主存空間利用率的辦法

1)分區(qū)按大小順序排列，這樣可以使作業(yè)總是先使用滿足要求的最小分區(qū)。

2)根據(jù)經(jīng)常出現(xiàn)的作業(yè)大小和頻率劃分分區(qū)。

3)按作業(yè)對主存空間的需求量排成多個(gè)隊(duì)列，規(guī)定隊(duì)列與分區(qū)的對應(yīng)關(guān)系。也就是說多大的作業(yè)只能放在多大的分區(qū)里，就算有更大的分區(qū)空著，也不許他進(jìn)入。

l           可變分區(qū)的管理

可變就是指分區(qū)的大小和位置不是固定的,而是根據(jù)作業(yè)要求的主存量來分配分區(qū)的大小。

圖4_3.3是可變分區(qū)管理方式的存儲空間分配示意圖。

（1）主存的分配和去配

     在系統(tǒng)初始化時(shí)，主存除了操作系統(tǒng)所占部分外，整個(gè)用戶區(qū)是一個(gè)大的空閑區(qū)，可以按作業(yè)需要的空間大小順序分配空閑區(qū)直到不夠時(shí)為止。

當(dāng)作業(yè)結(jié)束時(shí)，它的占用分區(qū)被收回。這個(gè)空閑區(qū)又可以根據(jù)新作業(yè)的大小重新用于分配，所以主存中的已占分區(qū)和空閑區(qū)的數(shù)目和大小都是在變化的。可以用兩張表“已分配區(qū)表”和“空閑區(qū)表”來記錄和管理。

圖4_3.5是可變分區(qū)管理方式的主存分配表，表中內(nèi)容是按圖4_3.4(b)的情況填寫的。

（2）常用的分配算法

最先適應(yīng)分配算法：空閑區(qū)按地址順序由小到大登記在空閑區(qū)表中,在分區(qū)表中順序查找，找到夠大的空閑區(qū)就分配。但是這樣的分配算法可能形成許多不連續(xù)的空閑區(qū)，造成許多“碎片”，使主存空間利用率降低。    點(diǎn)擊見相關(guān)動畫

最優(yōu)適應(yīng)分配算法：這種算法總是挑選一個(gè)能滿足作業(yè)要求的最小空閑區(qū)。           點(diǎn)擊見相關(guān)動畫

    在實(shí)現(xiàn)這種算法時(shí)，可把空閑區(qū)按長度以速增順序登記在空閑區(qū)表中。分配時(shí)順序查找空閑區(qū)表，由于查找時(shí)每次總是從最小的一個(gè)區(qū)開始，同時(shí)要不斷調(diào)整空閑區(qū)表，每當(dāng)收回一個(gè)分區(qū)，必須把收回后的分區(qū)按長度順序插入登記到空閑區(qū)表的適當(dāng)位置。 但是這種算法可能形成一些極小的空閑區(qū)，以致無法使用，這也會影響主存利用率。

最壞適應(yīng)分配算法：這種算法總是挑一個(gè)最大的空閑區(qū)分給作業(yè)使用，使剩下的空間不至于太小。空閑區(qū)按長度以遞減順序登記在空閑區(qū)表中。

    一個(gè)歸還區(qū)可能有上鄰空閑區(qū)，也可以有下鄰空閑區(qū)，或既有上鄰又有下鄰空閑區(qū)，或既無上鄰又無下鄰空閑區(qū)。在實(shí)現(xiàn)去配時(shí)應(yīng)順序檢查空閑區(qū)表中標(biāo)志為“未分配”的欄目，以確定是否有相鄰空閑區(qū)。四種情形如圖4_3.6所示。

假定作業(yè)歸還的分區(qū)始址為s,長度為L，則：

   （1）歸還區(qū)有下鄰空閑區(qū)。如果S+L正好等于空閑區(qū)表中某個(gè)登記欄目（假定為第j欄）所示分區(qū)的始址，則表明歸還區(qū)有一個(gè)下鄰空閑區(qū)。這時(shí)修改第j欄登記項(xiàng)的內(nèi)容：

          始址：=S

          長度：=原長度+L

則第j欄指示的空閑區(qū)是歸還區(qū)與下鄰空閑區(qū)合并后的一個(gè)大空閑區(qū)。

   （2）歸還區(qū)有上鄰空閑區(qū)。如果空閑區(qū)表中第j個(gè)登記欄中的“始址+長度”正好等于s，則表明歸還區(qū)有一個(gè)上鄰空閑區(qū)。這時(shí)修改第j欄登記項(xiàng)的內(nèi)容：始址不變，長度為原長度加上L。于是，歸還區(qū)便與上鄰空閑區(qū)合在一起了。

   （3）歸還區(qū)既有上鄰空閑區(qū)又有下鄰空閑區(qū)。

      S=第j欄始址+長度

    如果

        S＋L=第k欄始址

則表明歸還區(qū)既有上鄰空閑區(qū)，又有下鄰空閑區(qū)。此時(shí)，須把這三個(gè)區(qū)合并成一個(gè)空閑區(qū)登記入空閑區(qū)表中，只需使用一個(gè)登記欄目。進(jìn)行如下修改：第j欄始址不變；第j欄長度為“j欄中原長度+k欄中長度+L”；第k欄的標(biāo)志應(yīng)修改成“空”狀態(tài)。于是，第j欄中登記的空閑區(qū)就是合并后的空閑區(qū)，而第k欄成為空表目了。

（4）歸還區(qū)既無上鄰又無下鄰空閑區(qū)。如果在檢查空閑區(qū)表時(shí)，無上述三種情況出現(xiàn)，則表明歸還區(qū)既無上鄰又無下鄰空閑區(qū)。這時(shí)，應(yīng)找一個(gè)標(biāo)志為“空”的登記欄，把歸還區(qū)的始址和長度登記入表，且把該欄目中的標(biāo)志位修改成“未分配”。

(3) 可變方式管理主存時(shí)的存儲保護(hù)

       (4) 移動技術(shù)的應(yīng)用

但是移動技術(shù)的應(yīng)用也要注意以下問題：

    1）  移動會增加系統(tǒng)開銷。所以要盡量減少移動。

　第四節(jié)   頁式存儲管理

l          基本原理

頁式存儲管理中有兩個(gè)名詞：“頁”和“塊”，其中的“塊”是針對硬件來說的，就是把存儲器分成若干相等大小的區(qū)，每個(gè)區(qū)就稱為一個(gè)塊。對應(yīng)的，在程序中，邏輯地址進(jìn)行“分頁”，其大小和每個(gè)塊相一致。

事實(shí)上，頁面的大小是由塊的大小自然決定的。對于程序來說，其邏輯地址還是和原來一樣采用連續(xù)的地址。只是按照塊的位數(shù)取其前面數(shù)位做為頁號。

分配空間時(shí)，根據(jù)作業(yè)長度可以確定它的頁面數(shù)，根據(jù)這個(gè)頁面數(shù)在主存中分配相應(yīng)的塊數(shù)，只要是空閑塊就可以放入，即使不是相鄰的。并把分配情況記在“頁表”中，根據(jù)頁表可以找到相對應(yīng)的頁號與塊號，就得出絕對地址了。

采用頁式管理，使主存空間充分利用，頁不必為了得到連續(xù)空間而進(jìn)行移動。可以提高系統(tǒng)效率。 

l          頁式存儲管理中主存塊的大小是如何決定的？

主存塊的大小是由硬件地址結(jié)構(gòu)確定的。在頁式存儲管理中，地址由兩部分組成：頁號和頁內(nèi)地址。假定地址用m個(gè)二進(jìn)制位表示，其中頁內(nèi)地址部分占用了n個(gè)二進(jìn)制，那么每一個(gè)塊的長度就是 。 

l          頁表的構(gòu)造與作用

每個(gè)被裝入主存的作業(yè)都有一張頁表，指出該作業(yè)邏輯地址中的頁號與所占用的主存塊號之間的對應(yīng)關(guān)系。頁表的長度由作業(yè)擁有的頁面數(shù)決定，行號對應(yīng)為頁號，行中記錄的是主存中的塊號。

頁表是硬件進(jìn)行地址轉(zhuǎn)換的依據(jù)，每執(zhí)行一條指令時(shí)按邏輯地址中的頁號查找頁表并轉(zhuǎn)換成絕對地址。絕對地址的計(jì)算公式如下：

          絕對地址= 塊號* 塊長+ 頁內(nèi)地址

圖4-4.1中假定作業(yè)J有四個(gè)頁面： JP0， JP1， JP2， JP3，現(xiàn)只要找出四個(gè)空閑塊就可把作業(yè)1裝入主存。如果找到的四個(gè)空閑塊是第5，23，24， 27塊，則四個(gè)頁面就分別裝入其中。同時(shí)應(yīng)為該作業(yè)建立一張“頁表”，指出邏輯地址中的頁號與主存中塊號的對應(yīng)關(guān)系，頁表的一般格式如圖4-4.1中所示。作業(yè)執(zhí)行時(shí)，按邏輯地址中的頁號查“頁表”，得到該頁對應(yīng)的塊號，就可知道該頁在主存中的位置，再按頁內(nèi)地址就能算出欲訪問的絕對地址。絕對地址的計(jì)算公式為：絕對地址= 塊號* 塊長+ 頁內(nèi)地址。因此，雖然作業(yè)被存放在若干個(gè)不連續(xù)的塊中，但在作業(yè)執(zhí)行中總是能按確切的絕對地址進(jìn)行存取。

l          在采用頁式存儲管理的系統(tǒng)中，怎樣利用“位示圖”來進(jìn)行主存空間的分配與回收？

位示圖:位示圖中的每一位與一個(gè)主存塊對應(yīng)，每一位的值可以是“0”或“1”，當(dāng)取值為“0”時(shí)表示對應(yīng)塊為空閑，當(dāng)取值為“1”時(shí)表示對應(yīng)塊已被占用。在位示圖中增加一個(gè)字節(jié)記錄當(dāng)前剩余的空閑塊數(shù)

                            塊號=字號x字長+位號

這個(gè)塊號就是當(dāng)前所分配用來裝作業(yè)信息的主存塊的塊號。

    當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束時(shí)，應(yīng)收回該作業(yè)所占用的主存塊。根據(jù)歸還的塊號可計(jì)算出歸還塊在位示圖中的對應(yīng)位置，計(jì)算公式如下，并將該位的占用標(biāo)志置為“0”。

           字號=［塊號/字長］，位號=塊號  mod 字長

l          地址轉(zhuǎn)換

    每執(zhí)行一條指令時(shí)按邏輯地址中的頁號查頁表，若頁表中無此頁號，則產(chǎn)生一個(gè)“地址錯(cuò)”的程序性中斷事件；若頁表中有此頁號，則可得到對應(yīng)的主存塊號，按計(jì)算公式可轉(zhuǎn)換成欲訪問的主存絕對地址。按絕對地址的計(jì)算公式為“塊號*塊長+頁內(nèi)地址”

l          采用頁式存儲管理為什么會延長指令的執(zhí)行周期？有什么辦法可提高指令的執(zhí)行速度？

    頁式存儲管理中的頁表一般是存放在主存中的。當(dāng)要按給定的邏輯地址進(jìn)行讀／寫時(shí)，首先要按頁號從頁表中讀出對應(yīng)的塊號，然后算出絕對地址進(jìn)行讀／寫。這樣就必須訪問主存兩次，多花了一次訪問主存的時(shí)間，因而延長了指令的執(zhí)行周期，降低了執(zhí)行速度。

為了提高存取速度，通常都設(shè)置一個(gè)小容量的高速緩沖存儲器，用來存放頁表的一部分。把這部分頁表稱為“快表”。根據(jù)程序執(zhí)行局部性的特點(diǎn)，在一段時(shí)間內(nèi)總是經(jīng)常訪問某些頁。若把這些頁登記在快表中，就可不要從主存中查頁表，而是從高速緩沖存儲器中查快表，這樣就可縮短查找時(shí)間，從而提高了指令執(zhí)行速度。

l          頁的共享與保護(hù)