计算机软考系统分析师重点与难点：位示图

　　位示图法在近年的系统分析师考试中出现较为频繁，属于考试重点，该考点涉及的知识点的难度并不大，但如果考生从未学习过相关知识就很容易出错。故笔者从《系统分析师考试全程指导》与《系统分析师考试综合知识试题分类精解》中选取部分内容以及例题组成该文，供考生参考。阅读本文即可应对相关考题。

　　位示图法是操作系统中一种管理空闲存储空间的方法。管理空闲空间除使用位示图法还可用：空闲区表法、空闲链表法、成组链接法本文将详细介绍这几种方法。

　　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。