十大題型算法全實現——（五）磁盤存儲空間的管理[1]

　　五 磁盤存儲空間的管理

　　主要有

　　位示圖 和內存的位示差不多

　　空閒塊表 和可變內存管理差不多

　　空閒塊鏈 主要是UNIX成組鏈接法的設計與實現

　　UNIX系統文件管理成組連接算法說明

　　UNIX系統文件管理成組連接算法

　　把空閒塊分成若干組把指向一組中各空閒塊的指針集中一起

　　這樣既可方便查找又可減少為修改指針而啟動磁盤的次數

　　UNIX系統采用空閒塊成組連接的方法

　　UNIX系統把每個空閒塊作為一組每一組的第一個空閒塊中登記下一組空閒塊的塊號和空閒塊數

　　余下不足塊的那部分空閒塊的塊號及塊數登記在一個專用塊中登記最後一組塊號的那個空閒塊其中第個單元填

　　表示該塊中指出的塊號是最後一組的塊號空閒塊鏈到此結束

　　系統初始化時先把專用塊內容讀到內存當需分配空閒塊時就直接在內存中可找到哪些塊強障械模糠峙湟豢楹蟀芽障鋅槭

　　但要把一組中的第一個空閒塊分配出去之前應把登記在該塊中的下一組的塊號及塊數保存到專用塊中

　　當一組空閒塊被分配完後則再把專用塊的內容讀到內存指出另一組可供分配的空閒塊當歸還一塊時

　　只要把歸還塊的塊號登記到當前組中且空閒塊數加如果當前組已滿塊則把內存中的內容寫到歸還的那塊中

　　該歸還塊作為新組的第一塊假設初始化時系統已把專用塊讀入內存L單元開始的區域中分配和回收的算法如下

　　分配一個空閒塊

　　查L單元內容(空閒塊數)

　　當空閒塊數 i =L+空閒塊數;

　　從i單元得到一空閒塊號;

　　把該塊分配給申請者;

　　空閒塊數減

　　當空閒塊數= 取出L+單元內容(一組的第一塊塊號或);

　　其值=無空閒塊申請者等待

　　不等於零把該塊內容復制到專用塊;

　　該塊分配給申請者;

　　把專用塊內容讀到主存L開始的區域

[]  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/czxt/201311/11256.html