1、實驗四：實驗四：主存儲器的動態分配與回收主存儲器的動態分配與回收計算機系計算機系實驗教研室實驗教研室一一. 實驗目的實驗目的 一個好的計算機系統不僅要有一個足夠容量的、一個好的計算機系統不僅要有一個足夠容量的、存取速度高的、穩定可靠的主存儲器，而且要能合存取速度高的、穩定可靠的主存儲器，而且要能合理地分配和使用這些存儲空間。當用戶提出申請存理地分配和使用這些存儲空間。當用戶提出申請存儲器空間時，存儲管理必須根據申請者的要求，按儲器空間時，存儲管理必須根據申請者的要求，按一定的策略分析主存空間的使用情況，找出足夠的一定的策略分析主存空間的使用情況，找出足夠的空閑區域分配給申請者。當作業撤離或主動

2、歸還主空閑區域分配給申請者。當作業撤離或主動歸還主存資源時，則存儲管理要收回作業占用的主存空間存資源時，則存儲管理要收回作業占用的主存空間或歸還部分主存空間。主存的分配和回收的實現雖或歸還部分主存空間。主存的分配和回收的實現雖與主存儲器的管理方式有關的，通過本實習幫助學與主存儲器的管理方式有關的，通過本實習幫助學生理解在不同的存儲管理方式下應怎樣實現主存空生理解在不同的存儲管理方式下應怎樣實現主存空間的分配和回收。間的分配和回收。二二 .實驗題目實驗題目 在可變分區管理方式下采用最先適應算在可變分區管理方式下采用最先適應算法實現主存分配和實現主存回收法實現主存分配和實現主存回收 三三. 提示提

3、示(1)可變分區方式是按作業需要的主存空間大小可變分區方式是按作業需要的主存空間大小來分割分區的。當要裝入一個作業時，根據作來分割分區的。當要裝入一個作業時，根據作業需要的主存量查看是否有足夠的空閑空間，業需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區分配給該作業；若有，則按需要量分割一個分區分配給該作業；若無，則作業不能裝入。隨著作業的裝入、撤若無，則作業不能裝入。隨著作業的裝入、撤離，主存空間被分成許多個分區，有的分區被離，主存空間被分成許多個分區，有的分區被作業占用，而有的分區是空閑的。例如：作業占用，而有的分區是空閑的。例如： 三三. 提示提示 os作業作業1作業作

4、業3空閑區空閑區作業作業2空閑區空閑區05K10K14K26K32K46K128K三三. 提示提示為了說明哪些區是空閑的，可以用來裝入新為了說明哪些區是空閑的，可以用來裝入新作業，必須要有一張空閑區說明表，格式作業，必須要有一張空閑區說明表，格式如下：如下： 起起 址址長長 度度狀狀 態態第一欄26 K6 K未 分 配第二欄46 K82 K未 分 配 空 表 目 空 表 目 三三. 提示提示說明:起址指出一個空閑區的主存起始地址。 長度指出從起始地址開始的一個連續空閑的長度。 狀態有兩種狀態，一種是“未分配”狀態，指出對應的由起址指出的某個長度的區域是空閑區；另一種是“空表目”狀態，表示表中對

5、應的登記項目是空白（無效），可用來登記新的空閑區（例如，作業撤離后，它所占的區域就成了空閑區，應找一個“空表目”欄登記歸還區的起址和長度且修改狀態）。由于分區的個數不定，所以空閑區說明表中應有適量的狀態為“空表目”的登記欄目，否則造成表格“溢出”無法登記。 上述的這張說明表的登記情況是按提示（1）中的例所裝入的三個作業占用的主存區域后填寫的。三三. 提示提示(2) 當有一個新作業要求裝入主存時，必須查空當有一個新作業要求裝入主存時，必須查空閑區說明表，從中找出一個足夠大的空閑區。閑區說明表，從中找出一個足夠大的空閑區。有時找到的空閑區可能大于作業需要量，這時有時找到的空閑區可能大于作業需要量，

6、這時應把原來的空閑區變成兩部分：一部分分給作應把原來的空閑區變成兩部分：一部分分給作業占用；另一部分又成為一個較小的空閑區。業占用；另一部分又成為一個較小的空閑區。為了盡量減少由于分割造成的空閑區，而盡量為了盡量減少由于分割造成的空閑區，而盡量保存高地址部分有較大的連續空閑區域，以利保存高地址部分有較大的連續空閑區域，以利于大型作業的裝入。為此，在空閑區說明表中，于大型作業的裝入。為此，在空閑區說明表中，把每個空閑區按其地址順序登記，即每個后繼把每個空閑區按其地址順序登記，即每個后繼的空閑區其起始地址總是比前者大。為了方便的空閑區其起始地址總是比前者大。為了方便查找還可使表格查找還可使表格“緊

7、縮緊縮”，總是讓，總是讓“空表目空表目”欄集中在表格的后部。欄集中在表格的后部。三三. 提示提示(3) 采用最先適應算法（順序分配算法）分配主存空采用最先適應算法（順序分配算法）分配主存空間。間。 按照作業的需要量，查空閑區說明表，順序查看按照作業的需要量，查空閑區說明表，順序查看登記欄，找到第一個能滿足要求的空閑區。當空閑登記欄，找到第一個能滿足要求的空閑區。當空閑區大于需要量時，一部分用來裝入作業，另一部分區大于需要量時，一部分用來裝入作業，另一部分仍為空閑區登記在空閑區說明表中。仍為空閑區登記在空閑區說明表中。 由于本實驗是模擬主存的分配，所以把主存區分由于本實驗是模擬主存的分配，所以把

8、主存區分配給作業后并不實際啟動裝入程序裝入作業，而用配給作業后并不實際啟動裝入程序裝入作業，而用輸出輸出“分配情況分配情況”來代替。來代替。三三. 提示提示(4) 當一個作業執行結束撤離時，作業所占的當一個作業執行結束撤離時，作業所占的區域應該歸還，歸還的區域如果與其它空閑區域應該歸還，歸還的區域如果與其它空閑區相鄰，則應合成一個較大的空閑區，登記區相鄰，則應合成一個較大的空閑區，登記在空閑區說明表中。例如，在提示（在空閑區說明表中。例如，在提示（1）中列）中列舉的情況下，如果作業舉的情況下，如果作業2撤離，歸還所占主存撤離，歸還所占主存區域時，應與上、下相鄰的空閑區一起合成區域時，應與上、下相鄰的空閑區一起合成一個大的空閑區登記在空閑區說明表中。一個大的空閑區登記在空閑區說明表中。三三. 提示提示(5) 請按最先適應算法設計主存分配和回收的請按最先適應算法設計主存分配和回收的 程序。然后按（程序。然后按（1）中假設主存中已裝入三）中假設主存中已裝入三個作業，且形成兩個空閑區，確定空閑區說個作業，且形成兩個空閑區，確定空閑區說明表的初值。現有一個需要主存量為明表的初值。現有一個需要主存量為6K的作的作業業4申請裝入主存；然后作業申請裝入主存；然后作業3撤離；再作