位示圖是操作系統中一種管理空閑存儲空間的方法。管理空閑除使用位示圖法還可用:空閑區表法,空閑鏈表法,成組鏈接法
1.空閑區表法
? 空閑表法屬于連續分配方法。它與內存管理中的動態分區分配方法雷同。
????????將外存空間上一個連續未分配區域稱為“空閑區”。操作系統為磁盤外存上所有空閑區建立一張空閑表,每個表項對應一個空閑區,空閑表包含“序號,第一空閑盤塊號,空閑盤塊數”等信息。它適用于連續文件結構。
????????它為每個文件分配一個連續的存儲空間。系統為外存上的所有空閑區建立一張空閑表,每個空閑區對應于一個空閑表項。
2.空閑鏈表法
????????是將所有的空閑盤區拉成一條空閑鏈。根據構成鏈的基本元素的不同,可有兩種鏈表方式:空閑盤塊,空閑盤區鏈
? ? ? 空閑盤塊鏈:它是將磁盤上的所有空閑存儲空間,以盤塊為基本元素拉成一條鏈。優點是用于分配和回收一個盤塊的過程非常簡單;缺點是空閑盤塊鏈可能很長。
? ? ? ?空閑盤區鏈:這是將磁盤上的所有空閑盤區(每個盤區可包含若干個盤塊)拉成一條鏈。在每個盤區上除了含有用于指示下一個空閑盤區的指針外,還應標有指明本盤區大小(盤塊數)的信息。這方法分配和回收過程較復雜,但空閑盤區鏈較短
3.位示圖法
? ?????????這種方法是在外存上建立一張位示圖(bitmap),記錄文件存儲器的適用情況。每一位僅對應文件存儲器上的一個物理快,取值0和1分別表示空閑和占用。文件存儲器上的物理快依次編號為:0,1,2,.......。
????????位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況。當其值為“0”時,表示對應的盤塊空閑;為“1”時表示已分配。由所有盤塊對應的位構成一個集合,稱為位示圖。位示圖也可描述為一個二位數組map:Var map:array[1......m,1......n]of bit;
盤塊的分配
? ?????????根據位示圖進行盤塊分配時,可分三步進行:
? ? 順序掃描位示圖,從中找出一個或一組值均為“0”的二進制位;
? ? ? 將找到的二進制位,轉換成與之相應的盤塊號;
? ? ? 修改位示圖,令map[i,j]=1.
盤塊的回收
? ? 盤塊的回收分兩步:
? ? ? ?將回收盤塊的盤塊號轉換成位于圖中的行號和列號。轉換公式為:
i=(b-1)DIVn+1
j=(b-1)MODn+1
修改位示圖令map[i,j]=0.