十大题型算法全实现——（五）磁盘存储空间的管理[1]

五 磁盘存储空间的管理

主要有

位示图 和内存的位示差不多

空闲块表 和可变内存管理差不多

空闲块链 主要是UNIX成组链接法的设计与实现

UNIX系统文件管理成组连接算法说明

UNIX系统文件管理成组连接算法

把空闲块分成若干组把指向一组中各空闲块的指针集中一起

这样既可方便查找又可减少为修改指针而启动磁盘的次数

UNIX系统采用空闲块成组连接的方法

UNIX系统把每个空闲块作为一组每一组的第一个空闲块中登记下一组空闲块的块号和空闲块数

余下不足块的那部分空闲块的块号及块数登记在一个专用块中登记最后一组块号的那个空闲块其中第个单元填

表示该块中指出的块号是最后一组的块号空闲块链到此结束

系统初始化时先把专用块内容读到内存当需分配空闲块时就直接在内存中可找到哪些块强障械模糠峙湟豢楹蟀芽障锌槭

但要把一组中的第一个空闲块分配出去之前应把登记在该块中的下一组的块号及块数保存到专用块中

当一组空闲块被分配完后则再把专用块的内容读到内存指出另一组可供分配的空闲块当归还一块时

只要把归还块的块号登记到当前组中且空闲块数加如果当前组已满块则把内存中的内容写到归还的那块中

该归还块作为新组的第一块假设初始化时系统已把专用块读入内存L单元开始的区域中分配和回收的算法如下

分配一个空闲块

查L单元内容(空闲块数)

当空闲块数 i =L+空闲块数;

从i单元得到一空闲块号;

把该块分配给申请者;

空闲块数减

当空闲块数= 取出L+单元内容(一组的第一块块号或);

其值=无空闲块申请者等待

不等于零把该块内容复制到专用块;

该块分配给申请者;

把专用块内容读到主存L开始的区域

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