第5章存儲管理存儲管理的任務和功能是什么？答：存儲管理的主要任務是：支持多道程序的并發執行，使多道程序能共享存儲資源，在互不干擾的環境中并發執行。方便用戶，使用戶減少甚至擺脫對存儲器的管理，使用戶從存儲器的分配、保護和共享等繁瑣事物中解脫出來。提高存儲器的利用率和系統吞吐量。從邏輯上擴充內存空間，支持大程序能在小的內存空間運行或允許更多的進程并發執行。為了完成上述任務，現代操作系統的存儲管理應具有以下功能：（1）存儲空間的分配和回收。（2）地址轉換，實現邏輯地址到物理地址的映射。（3）主存空間的共享。（4）主存空間的保護。（5）主存儲空間的擴充。（6）對換，對換的主要任務是實現在內存和外存之間的全部或部分進程的對換，即將內存中處于阻塞狀態的進程調換到外存上，而將外存上處于就緒狀態的進程換入內存。對換的目的主要是為了提高內存利用率，提高系統的吞吐量。2.為什么要配置層次式存儲器？答：為了解決CPU和存儲器之間速度上的不匹配，在現代計算機系統中，存儲系統通常采用層次結構，存儲層次可粗略分為三級：最高層為CPU寄存器，中間為主存，最底層是輔存。根據具體功能還可以細分為寄存器、高速緩存、主存儲器、磁盤緩存、輔存儲設備(固定磁盤、可移動存儲介質)5層。一個文件的數據可能出現在存儲系統的不同層次中，例如，一個文件數據通常被存儲在輔存中(如硬盤)，當其需要運行或被訪問時，就必須調入主存，也可以暫時存放在主存的磁盤高速緩存中。大容量的輔存常常使用磁盤，磁盤數據經常備份在可移動磁盤或者光盤上，以防止硬盤故障時丟失數據。3.什么是邏輯地址？什么是物理地址？為什么要進行二者的轉換工作？答：邏輯地址是應用程序中使用的訪存地址，有時也稱為相對地址，由邏輯地址構成的地址空間稱為邏輯空間。每個應用程序的邏輯地址空間都是從零號地址碼開始的。物理地址是內存儲器的實際存儲單元地址，有時也稱為絕對地址，由物理地址構成的地址空間稱為物理空間。物理地址空間也是從零號地址碼開始的。在多道程序環境下，程序邏輯地址空間和內存物理地址空間是不一致的。用戶程序的邏輯地址可以是一維線性或多維線性，而內存中的每一個存儲單元都有相應的內存地址相對應，屬于一維線性地址。在將用戶程序部分或全部地裝入內存空間時，要實現邏輯地址到物理地址的映射。4.地址重定位，靜態地址重定位和動態地址重定位有什么區別？答：地址重定位指從邏輯地址到物理地址的映射過程，也稱為地址映射。靜態地址重定位是指在用戶程序執行之前完成地址映射工作，即把程序的邏輯地址都轉換為實際的內存物理地址。靜態地址重定位的地址變換只是在裝入時一次完成，而在程序運行期間不再變化。動態地址重定位是指在程序執行過程中，CPU在訪問內存之前，將要訪問的程序或數據地址轉換為內存地址。5.什么是內部碎片和外部碎片？。答：在一個分區內部出現的碎片(即被浪費的空間)稱作內部碎片，如固定分區法就會產生內部碎片；在所有分區之外新增的碎片稱作外部碎片，如在動態分區法實施過程中出現的越來越多的小空閑塊就是外部碎片，由于它們太小，無法裝入一個進程，因而被浪費掉。6.什么是分頁和分段存儲技術，兩者有何區別？答：在分頁系統中，系統會把用戶程序的地址空間劃分成若干個大小相等的區域，每個區域稱作一個頁面或頁。每個頁都有一個編號，叫做頁號。頁號一般從0開始，如0，1，2，…，等。類似地，也把內存空間劃分成若干和頁大小相同的物理塊，這些物理塊叫“幀”(frame)或內存塊。同樣，每個物理塊也有一個編號，塊號也是從0開始依次順序排列。系統為進程分配內存時，以塊為單位將進程中的若干頁分別裝入多個可以不相鄰接的塊中。在分段存儲管理方式中，程序按內容或過程(函數)關系劃分為若干個段，每個段定義一組邏輯信息，都有自己的名字。一個用戶作業所包含的段對應于一個二維線性虛擬空間，也就是一個二維虛擬存儲器。段式管理程序以段為單位進行內存分配，然后通過地址映射機構把段式虛擬地址轉換為實際的內存物理地址。分段和分頁有許多相似之處，比如，二者在內存中都采用離散分配方式，而不是整體連續分配方式，而且都要通過地址映射機構來實現地址轉換。但二者在概念上卻完全不同，具體表現在下述三個方面：頁是信息的物理單位，而段是信息的邏輯單位。分頁是為了實現離散分配，減少內存碎片，提高內存利用率。或者說，分頁是由于系統管理的需要，而不是用戶的需要。段則是信息的邏輯單位，它含有一組意義相對完整的信息。段的長度不是固定的，取決于用戶所編寫的程序。分段的目的是為了能更好地滿足用戶的需要，更方便用戶編程，更好地實現信息共享和保護。頁的大小由系統確定，由系統把邏輯地址劃分為頁號和頁內地址兩部分，整個系統只能有一種大小的頁面；而段的長度卻不固定，它取決于用戶的程序。通常由編譯程序在對源碼進行編譯時，根據程序的性質來劃分。分頁的進程地址空間是一維的，即單一的線性空間；而分段的進程地址空間是二維的，由段號和段內地址兩部分組成。7.什么是虛擬存儲器？列舉采用虛擬存儲器的必要性和可能性。答：虛擬存儲器是指在具有層次結構存儲器的計算機系統中，具有請求調入和交換功能，為用戶提供一個比實際物理內存容量大得多的可尋址的一種存儲器系統，它能從邏輯上對內存容量進行擴充。采用虛擬存儲器的必要性：傳統存儲管理方式要求將作業全部裝入內存之后才能運行，這一特征導致大作業和多個作業要求運行時系統無法滿足；另外，傳統存儲管理方式具有駐留性，即作業裝入內存直到運行結束，便一直駐留在內存中。盡管進程在運行中會因I/O等原因而長期處于阻塞狀態，或有的程序模塊在運行過一次后就不再需要，但它們都仍將繼續占用寶貴的內存資源。采用虛擬存儲器的可能性：根據程序的局部性定理，應用程序在執行之前，沒有必要全部裝入內存，而只需要將那些當前要運行的部分頁或段先裝入內存即可運行，其余部分可以仍然留在外存。程序在執行時，如果它所訪問的頁(段)已經調入內存，便可繼續執行下去。但如果程序所要訪問的頁(段)不在內存中(稱為缺頁或缺段)，此時程序可以利用操作系統提供的請求調頁(段)功能，將它們調入內存，以便程序能夠繼續執行下去。如果內存已滿，無法裝入新調入的頁(段)，則必須利用一定的頁(段)置換功能，將內存中暫時不用的頁(段)換到外存中，以騰出足夠的空間來存放新調入的頁(段)，從而保證程序的順利執行。這樣，一個大的程序就可以在較小的內存空間中執行。從用戶的角度來看，該系統所具有的內存容量比實際內存容量大了很多。但實際上，用戶所看到的大容量存儲器是不存在的，只是虛擬的，故把這樣的存儲器稱為虛擬存儲器。(8.一個計算機系統的虛擬存儲器，其最大容量和實際容量分別由什么決定？答：虛擬存儲器的最大容量由主存和輔存的容量之和確定。虛擬存儲器的實際容量由指令中表示地址的字長決定，也就是計算機的地址結構決定的。9.描述下列算法：①首次適應；②最佳適應；③最差適應答：最先適應算法又稱首次適應算法，該算法要求空閑分區表或空閑分區鏈按起始地址遞增的次序排列。在進行內存分配時，從空閑分區表(鏈)首開始順序查找，一旦找到大于或等于所要求內存長度的分區，則結束查找。然后，該算法從該分區中劃出所要求的內存長度分配給請求者，余下的空閑分區仍留在空閑分區表(鏈)中，同時修改其相應的表(鏈)項。最佳適應算法要求空閑分區按容量大小遞增的次序排列。當用戶作業申請一個空閑區時，存儲管理程序從空閑分區表(鏈)首開始順序查找，當找到第一個滿足要求的空閑區時，停止查找。按這種方式為作業分配內存，就能把既滿足作業要求又與作業大小最接近的空閑分區分配給作業。如果空閑分區大于作業的大小，則與最先適應算法相同，將減去作業請求長度后的剩余空閑區仍然留在空閑分區表(鏈)中。最壞適應算法要求空閑分區按其大小遞減的順序組成空閑分區表(鏈)。當用戶作業申請一個空閑區時，先檢查空閑分區表(鏈)的第一個空閑分區的大小是否大于或等于所要求的內存長度，若空閑分區表(鏈)的第一項長度小于所要求的大小，則分配失敗，否則從該空閑分區中劃出與作業大小相等的一塊內存空間分配給作業，余下的空閑分區仍然留在空閑分區表(鏈)中。10.如果內存劃分為100KB、500KB、200KB、300KB和600KB(按順序)，那么，首次適應、最佳適應和最差適應算法各自將如何放置大小分別為215KB、414KB、110KB和430KB(按順序)的進程，哪一種算法的內存利用率高？解:見下圖，在首次適應和最差適應算法中，最后430KB沒有空間分配。由圖可知，最佳適應算法的內存利用率高。11.某操作系統采用分區存儲管理技術。操作系統占用了低地址端的100KB的空間，用戶區從100KB處開始共占用512KB，初始時，用戶區全部空閑，分配時截取空閑區的低地址部分作為一個分配區。在執行了如下的申請、釋放操作序列后：作業1申請300KB、作業2申請100KB、作業1釋放300KB、作業3申請150KB、作業4申請50KB、作業5申請90KB。①分別畫出采用首次適應算法、最佳適應算法進行內存分配后的內存分配圖和空閑區隊列；②若隨后又申請80KB，針對上述兩種情況會產生什么后果？解:采用首次適應算法、最佳適應算法進行內存分配后的內存分配圖和空閑區隊列圖如下所示。若隨后又申請80KB，只有采用首次適應算法的內存分配還有空間可以分配，分配圖如下：12.假設一個有8個1024字節頁面的邏輯地址空間，映射到一個有32幀的物理內存：①邏輯地址有多少位？②物理地址有多少位？答：邏輯地址有13位；物理地址有15位。13.某虛擬內存的用戶編程空間共32頁，每頁的大小為1KB，內存為16KB，假設某時刻系統為用戶的第0、1、2、3頁分配的物理塊為5、10、4、7，而該用戶作業的長度為6頁，試將16進制的虛擬地址0A5C、093C、1A5C轉換成物理地址。答：虛擬地址為0A5C,對應的二進制數為：0000101001011100。其中，頁內偏移量占10位地址碼，為25C。頁號占6位地址碼，為2號頁。因第2頁存儲在4號塊中，其基地址為：0001000000000000，即十六進制的1000H。這樣，其物理地址為十六進制的125C。虛擬地址為093C，對應的二進制數為：0000100100111100。其中，頁內偏移量占10位地址碼，為13C。頁號占6位地址碼，為2號頁。因第2頁存儲在4號塊中，其基地址為：0001000000000000，即十六進制的1000H。這樣，其物理地址為十六進制的113C。虛擬地址為1A5C，對應的二進制數為：0001101001011100。頁內偏移量占10位地址碼，為25C。頁號占6位地址碼，為6號頁。因為該用戶作業的長度為6頁，最大的頁號為5號。因為虛擬地址為1A5C對應的6號頁超出了地址范圍，所以屬于越界。14.覆蓋技術和虛擬存儲技術有何區別，交換技術和虛擬存儲器中使用的調入和調出技術有何區別和聯系？解:覆蓋技術與虛擬存儲技術最本質的不同在于覆蓋程序段的最大長度要受內存容量大小的限制，而虛擬存儲器中程序的最大長度不受內存容量的限制，只受計算機地址結構的限制。另外，覆蓋技術中的覆蓋段由程序員設計，且要求覆蓋段中的各個覆蓋具有相對的獨立性，不存在直接聯系或相互交叉訪問；而虛擬存儲技術對用戶的程序段之間沒有這種要求。交換技術就是把暫時不用的某個程序及數據從內存移到外存中去，以便騰出必要的內存空間，或把指定的程序或數據從外存讀到內存中以允許其運行的一種內存擴充技術。交換技術與虛存中使用的調入/調出技術的主要相同點是：都要在內存與外存之間交換信息。主要區別是：交換技術調入/調出整個進程，因此一個進程的大小要受內存容量大小的限制；而虛存中使用的調入/調出技術在內存和外存之間來回傳遞的是頁面或分段，而不是整個進程，從而使得進程的地址映射具有了更大的靈活性，且允許進程的大小比可用的內存空間大。15.在虛擬頁式存儲系統中引入了缺頁中斷，說明引入缺頁中斷的原因，并給出其實現的方法。答：虛擬頁式存儲系統中，系統允許作業的一部分頁面在內存。當系統產生了缺頁中斷后，操作系統才能將不在內存的頁面從外存調入內存。當缺頁被調入，使中斷恢復，進程就可以繼續執行它的程序了。缺頁中斷的實現由硬件和軟件兩部分組成。其實現方法如下：當CPU執行一條指令時，形成操作數的有效地址。其中的頁號部分用來檢查頁表，看該頁是否在內存。如果在內存，則進行地址變換，按變換后的地址取出操作數；如果不在內存，則引起缺頁中斷，進入缺頁中斷處理程序。在缺頁中斷處理程序中，主要的處理為：（1）利用存儲器分塊表檢查實存是否有空閑頁面。（2）如果有空閑存儲塊，則根據頁表提供的磁盤地址調入所需的頁面，修改頁表和分塊表后返回。（3）如果沒有空閑存儲塊，則選擇一頁淘汰掉。若該頁被修改過還需寫回外存，調入所需的頁面。然后修改頁表和分塊表，返回。16.試述缺頁中斷與一般中斷的主要區別。答：程序在執行時，當訪問的頁面不在內存時，便產生缺頁中斷，請求操作系統將所缺頁調入內存。中斷處理程序將把控制轉向缺頁中斷子程序。然后系統執行此子程序，把所缺頁面裝入主存中。接著處理器將重新執行缺頁時打斷的指令。缺頁中斷是一種特殊的中斷，也就是說，缺頁中斷同樣需要經歷諸如保護CPU環境、分析中斷原因、轉入缺頁中斷處理程序進行處理、恢復CPU環境等幾個步驟，但與一般的中斷相比，它又具有以下不同點：一般中斷是一條指令完成后中斷，而缺頁中斷是在一條指令執行時中斷。通常，CPU都是在一條指令執行完之后，才檢查是否有中斷請求到達。如果有，便去響應中斷，否則，繼續執行下一條指令。然而，缺頁中斷則是在指令執行期間，發現所訪問的指令或數據不在內存時所產生和處理的。一條指令執行時可能產生多個缺頁中斷。如指令可能訪問多個內存地址，這些地址在不同的頁中。17.假設有下面的段表：下面邏輯地址的物理地址分別是多少？①[0,430]；②[1,12]；③[2,500];④[3,400];⑤[4,122]段基址長度02196001230014290100313275804195296答：①：649；②：2312；③：越界；④：1727；⑤：越界18.考慮下面存儲訪問序列，該程序的大小為460字(以下數字均為十進制數字)：10、11、104、170、73、309、185、245、246、434、458、364該頁面的大小為100字，該程序的基本可用內存為200字，計算采用FIFO、LRU和OPT置換算法的缺頁次數。解:因為頁面的大小為100字，該程序的基本可用內存為200字，即可用內存為2塊。程序的存儲訪問序列可轉換為如下頁面訪問序列：1、1、2、2、1、4、2、3、3、5、5、4采用FIFO、LRU和OPT置換算法的訪問序列如下：由圖可知FIFO算法的缺頁次數為6次，LRU的缺頁次數為7次，OPT的缺頁次數為5次。19.有一個矩陣inta[100][100]以行為先進行存儲。有一虛擬存儲系統，物理內存共有3塊，其中1塊用于存放程序，其余2塊用于存放數據。假設程序已經在內存中占用1塊，其余2塊空閑。程序A:程序B:for(i=0;i<100;i++)for(j=0;i<100;j++)for(j=0;j<100;j++)for(i=0;i<100;i++)a[i][j]=0;a[i][j]=0;若每頁可存放200個整數，則程序A和程序B在執行過程中各會發生多少次缺頁？若每頁只能存放100個整數呢？以上說明了什么問題？答：由題目所給條件可知，數組a有100100=10000個整數，系統中共有2個內存塊用于存放數組信息，數組中的元素按行編址。若每頁可以存放200個整數，則一個內存頁中可以存放2行數組元素，對于程序A，數組元素的訪問順序為：a[0][0],a[0][1],…,a[0][99]a[1][0],a[1][1],…,a[1][99]…a[99][0],a[99][1],…,a[99][99]顯然，程序A對數組a的訪問順序與存儲順序一致，也是按行進行的。因此程序A每訪問2行數組元素都會產生一次缺頁中斷，則訪問整個數組會產生100/2=50次缺頁中斷。對于程序B，數組元素的訪問順序是：a[0][0],a[1][0],…,a[99][0]a[0][1],a[1][1],…,a[99][1]…a[0][99],a[1][99],…,a[99][99]顯然，程序B對數組a的訪問順序與存儲順序不一致。因此程序B每訪問2個元素將產生一次缺頁中斷，則訪問整個數組將產生10000/2=5000次缺頁中斷。若每塊只能存放100個整數，則一個內存塊中只能存放1行數組元素，對于程序A，每訪問1行數組元素都會產生一次缺頁中斷，則訪問整個數組會產生100次缺頁中斷；對于程序B，每訪問1個元素將產生一次缺頁中斷，則訪問整個數組將產生10000次缺頁中斷。以上結果說明，缺頁中斷的次數和數據存放方法及程序訪問數據的方法有很大關系；當缺頁次數較少時，減小頁面大小影響不大，當缺頁次數很大時，頁面的減小對系統效率及程序的執行會帶來很大影響。什么是進程在某時刻t的工作集？工作集與頁面的調入和淘汰策略有什么關系？答：工作集是指在某段時間間隔Δ里，進程實際訪問的頁面集合，具體地說便是把某進程在時間t-Δ~t之間所訪問的頁面集合計為w(t,Δ)，把變量Δ稱為工作集窗口尺寸。正確選擇工作集窗口尺寸，對存儲器的有效利用和系統吞吐率的提高，都將產生重要影響。一方面，如果把Δ選得很大，進程雖不易產生缺頁，但存儲器也將不會得到充分利用。另一方面，如果把Δ選得過小，則會使進程在運行過程中頻繁地產生缺頁中斷，反而降低了系統的吞吐率。什么是抖動？產生抖動的原因是什么？答：抖動是由于內存空間競爭引起的。當需要將一個新頁面調入內存時，因內