位示圖法在近年的系統(tǒng)分析師考試中出現(xiàn)較為頻繁，屬于考試重點，該考點涉及的知識點的難度并不大，但如果考生從未學習過相關(guān)知識就很容易出錯。故筆者從《系統(tǒng)分析師考試全程指導(dǎo)》與《系統(tǒng)分析師考試綜合知識試題分類精解》中選取部分內(nèi)容以及例題組成該文，供考生參考。閱讀本文即可應(yīng)對相關(guān)考題。

　　位示圖法是操作系統(tǒng)中一種管理空閑存儲空間的方法。管理空閑空間除使用位示圖法還可用：空閑區(qū)表法、空閑鏈表法、成組鏈接法本文將詳細介紹這幾種方法。

　　1.空閑區(qū)表法

　　空閑表法屬于連續(xù)分配方式。它與內(nèi)存管理中的動態(tài)分區(qū)分配方式雷同。

　　將外存空間上一個連續(xù)未分配區(qū)域稱為“空閑區(qū)”。操作系統(tǒng)為磁盤外存上所有空閑區(qū)建立一張空閑表，每個表項對應(yīng)一個空閑區(qū)，空閑表包含“序號，第一空閑盤塊號，空閑盤塊數(shù)”等信息。它適用于連續(xù)文件結(jié)構(gòu)。

　　它為每個文件分配一個連續(xù)的存儲空間。系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個空閑表項。

　　2.空閑鏈表法

　　是將所有的空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈的基本元素的不同，可有兩種鏈表方式：空閑盤塊鏈、空閑盤區(qū)鏈。

　　空閑盤塊鏈

　　它是將磁盤上的所有空閑存儲空間，以盤塊為基本元素拉成一條鏈。優(yōu)點是用于分配和回收一個盤塊的過程非常簡單;缺點是空閑盤塊鏈可能很長。

　　空閑盤區(qū)鏈

　　這是將磁盤上的所有空閑盤區(qū)(每個盤區(qū)可包含若干個盤塊)拉成一條鏈。在每個盤區(qū)上除了含有用于指示下一個空閑盤區(qū)的指針外，還應(yīng)標有指明本盤區(qū)大小(盤塊數(shù))的信息。這方法分配和回收過程較復(fù)雜，但空閑盤區(qū)鏈較短。

　　3.位示圖法

　　這種方法是在外存上建立一張位示圖(bitmap)，記錄文件存儲器的使用情況。每一位僅對應(yīng)文件存儲器上的一個物理塊，取值0和1分別表示空閑和占用。文件存儲器上的物理塊依次編號為：0、1、2、…。

　　位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況。當其值為“0”時，表示對應(yīng)的盤塊空閑;為“1”時表示已分配。由所有盤塊對應(yīng)的位構(gòu)成一個集合，稱為位示圖。位示圖也可描述為一個二維數(shù)組map：Var map:array[1...m,1...n]of bit;

　　盤塊的分配

　　根據(jù)位示圖進行盤塊分配時，可分三步進行：

　　·順序掃描位示圖，從中找出一個或一組值均為“0”的二進制位;

　　·將找到的二進制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號;

　　·修改位示圖，令map[i,j]=1。

　　盤塊的回收

　　盤塊的回收分兩步：

　　·將回收盤塊的盤塊號轉(zhuǎn)換成位于圖中的行號和列號。轉(zhuǎn)換公式為：

　　i=(b-1)DIVn+1

　　j=(b-1)MODn+1

　　·修改位示圖。令map[i,j]=0。