[数据结构与算法]操作系统位示图bitMap算法实现

1.位示图简介（Bit Map）

爆肝4小时~
这种方法是为文件存储空间建立一张位示图用以反映整个存储空间的分配情况。
普遍采用这种方法的OS：NOVA机中的RDOS，PDP-11的DOS和微型机CP/M
基本思想：用若干字节构成一张图，每个字节中的每一位对应文件存储器中的一个物理块。文件存储器上的物理块，依次编号为0,1，2，3……。在位示图中的第一个字节对应0，1，2…，号块，7，第二字节对应8，9，…,15号块，一次类推。若某位位“1”，表示对应的物理块已分配；若某位为“0”，表示对应的物理块空闲。

上代码：
//Manager.java

package com.xin;

import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;

public class Manager {
    int m , p , q;//磁盘柱面数,每柱面磁道数, 每磁道物理块数
    int size;//行数
    int[][] block;//相对磁盘块号 table
    int[][] bitmap;//位示图
    Stored list = null;//已分配磁盘对象
    ArrayList<Stored> lists = new ArrayList<Stored>();//已分配磁盘链表
    //构造方法输入m，p，q以及随机生成数据对位示图进行初始化
    public Manager() {
        System.out.println("请分别输入磁盘柱面数,每柱面磁道数, 每磁道物理块数:");
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        p = scanner.nextInt();
        q = scanner.nextInt();
        size =  m * p * q / 8;
        bitmap = new int[size][8];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < 8; j++) {
                int random = new Random().nextInt(2);
                //Random随机数类.nextInt()方法生成随机数
                 bitmap[i][j] = random;
            }
        }
    }
    //输出位示图
    public void printBM() {
        System.out.println("位示图:");
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < 8; j++) System.out.print(bitmap[i][j] + "  ");
            System.out.println();
        }
        System.out.println("-----------------------");
    }
    //输出相对磁盘块号 table
    public void printBlock() {
        block = new int[size][8];//创建相对磁盘块号 table
        System.out.println("block:");
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < 8; j++) {
                block[i][j] = i * 8 + j;//计算对应的磁盘块号
                System.out.print(block[i][j] + "   \t");
            }
            System.out.println();
        }
        System.out.println("----------------------------------------------------------");
    }
    //输出已分配磁盘块表
    public void printStored() {
        int index = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < 8; j++) {
                if (bitmap[i][j] == 1) {
                    lists.add(new Stored(block[i][j] / (4 * 8),//柱面号
                            block[i][j] % (4 * 8) / 8,//磁道号
                            block[i][j] % 8, index++));//物理块号
                }
            }
        }
        System.out.println("柱面号     磁道号      物理块号");
        for (Stored list : lists) {//遍历已分配磁盘链表 foreh循环
            System.out.println(list.C + "        \t" + list.H + "       \t" + list.R);
        }
        System.out.println("-----------------");
    }
    //申请磁盘块
    public void apply() {
        System.out.print("申请前的");
        printBM();//申请前位示图
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < 8; j++) {
                if (bitmap[i][j] == 0) {//如果 == 0就申请
                    bitmap[i][j] = 1;//置位1
                    System.out.println("申请磁盘信息:" + block[i][j] / (4 * 8) + "," +
                            " " + block[i][j] % (4 * 8) / 8 + ", " + block[i][j] % 8);
                    System.out.print("申请后的");
                    printBM();//申请后位示图
                    return;
                }
            }
        }
    }
    //释放磁盘号
    public void release() {
        //随机数随机释放一块被占用的
        int random = new Random().nextInt(lists.size());
        System.out.println("释放的random:" + random);
        for (int i = 0; i < lists.size(); i++) {
            if (random == lists.get(i).index) {//寻找释放块
                list = lists.get(i);
                int bnum = list.C * 4 * 8 + list.H * 8 + list.R;//相对磁盘块号
                int x = bnum / 8;//第x行
                int y = bnum % 8;//第y列
                System.out.println("i = " + x + ", j = " + y);
                System.out.print("释放前的");
                printBM();
                bitmap[x][y] = 0;
                System.out.print("释放后的");
                printBM();
                return;
            }
        }

    }


}

//Stored.java

package com.xin;

public class Stored {
    int C, H, R, index;//  柱面号,磁道号,物理块号,下标

    public Stored(int c, int h, int r, int index) {
        C = c;
        H = h;
        R = r;
        this.index = index;
    }

}

//Start.java

package com.xin;

import java.util.Scanner;

public class Start {
    public static void main(String[] args) {
        Manager manager = new Manager();
        int i = 0;
        do {
            System.out.println("1.随机形成位示图");
            System.out.println("2.打印block");
            System.out.println("3.打印存储信息");
            System.out.println("4.申请磁盘块");
            System.out.println("5.释放磁盘块");
            System.out.println("6.退出");
            System.out.println("请输入操作序号：");
            Scanner scanner = new Scanner(System.in);
            i = scanner.nextInt();
            switch (i) {
                case 1:
                    manager.printBM();
                    break;
                case 2:
                    manager.printBlock();
                    break;
                case 3:
                    manager.printStored();
                    break;
                case 4:
                    manager.apply();
                    break;
                case 5:
                    manager.release();
                    break;
                case 6:
                    break;
            }
        }while (i != 6);
        System.out.println("运行结束！");
    }
}

运行结果

原创作品，谢谢浏览！