系统文件格式定义及其存储管理算法设计

一、当前文件格式定义：


pkg = 文件头 + 打包文件流

文件头 = 文件头标记 + 版本号 + 【空闲循环双链表头指针[初始化置空] + 非空闲双链表头指针[初始化为文件包首部偏移量]】 + 文件个数 + 索引表大小 + 索引表偏移 + 索引表

打包文件流 = 二进制文件包1 + 二进制文件包2 + …... + 二进制文件包n

索引表 = id + 空闲/使用标记 + 文件/目录名称 + 偏移量（相对打包的文件流的首部，方便以后对文件进行管理） + 大小 + 类型 + 父id

【逻辑上的二进制文件包】（暂定） = llink(指向前一空闲空间的首部偏移) + tag(本包使用标记，0为未使用；1为已使用) + size(本包的大小) + rlink(指向后一空闲包的首部偏移) + space(空闲空间) + tag(尾部使用标记，内容和前面一致) + uplink(指向本包首部偏移)

说明：二进制文件包的设计在实际分配的时候，可以把整个包全部分配给文件写入。这些标记域将不浪费任何存储空间。

二、存储空间管理算法

1、一些说明

对存储空间的分配与回收，是通过加载到内存的两个表：空闲块链表和占用块链表【这两个表是在用户对文件操作的过程中，根据索引表动态生成的表格】进行管理的。这两个表都为双向循环链表，因此用到双向循环链表的常用操作：创建结点、删除结点、插入结点等操作。包括了对双向循环链表的排序：思路可以再内存中对双向循环链表进行重构，采用插入排序，空间复杂度为o(1)，性能上可行。基本操作：结点的创建、删除和插入操作。插入过程中按照size域进行排序。

2、存储空间分配算法【草稿，暂定】

分配算法分为三种：首次拟合法【无，首选】、最佳拟合法【从小到大排序】和最差拟合法【从大到小排序】。

程序流程：

删除【回收算法，见下】

插入【分配算法】：空闲块链头指针pav是否为空？

|

——是———否———

| |

在整个pkg尾部插|——————> 结点大小是否合适

入文件修改索引表| |

| | ——否———是——

| | | |

| | 指针下移 修改空闲块各个标记，返回分配首地址

| | | |

| —否—是否指空 写入文件，修改索引表

|< —————————是 |

| |

—————————————————————————

|

结束

3、文件存储空间的回收算法【草稿，暂定】

目标：物理上毗邻的空闲块组合成尽可能大的结点。

判别：释放区头部偏移量为p，则：

上一块存储区底部偏移为：p-1

下一块存储区头部偏移为：p+p-> size

使用情况判别方法：(p-1)-> tag == 0 上临区为空闲块，p+p-> size == 0 下临区为空闲块。

释放块操作：（四种）

1） 左右均为占用块：插入到空闲链表中。

2） 左邻区为空闲块，右邻区为占用块：修改左邻块size域；重设结点底部uplink。

3） 右邻区为空闲块，左邻区为占用块：修改释放块的头部域，修改有邻块的底部域。

4） 左右邻区均为空闲块：增加左邻空块的space量，链中删去右邻空间块。

4、存储空间碎片整理算法【草稿，暂定】——存储紧缩算法

5、索引表生成空闲双链表算法【思考中…】

附：存储分配与回收算法模拟实现代码



view plaincopy to clipboardprint?
#include < stdio.h>
#include < stdlib.h>
#include < string.h>

/ ==========宏定义部分========== /
#define footloc(p) (p+p-> size-1)// 指向p所指结点的底部
#define minsize 10 // 空闲区域最小的底限
#define initsize 500 // 初始化存储空间的大小
#define status int // 返回状态
#define ok 1 // 正确返回值
#define error 0 // 错误返回
#define num 20 // 内存最大个数

/ ==========结构定义部分========== /
typedef struct word // 内存字类型
{
union // head和foot分别是结点的第一个字和最后一个字
{
word link // 头部域，指向前趋结点
word uplink // 底部域，指向本结点头部
}

int tag // 块标志，0：空闲，1：占用，头部和尾部均有
int size // 头部域，块大小
word rlink // 头部域，指向后继结点
// char flag[10]
}word head foot space // space：可利用空间指针类型

typedef struct procinf // 分配的进程信息
{
space sp_head // 进程分配到的内存地址
char name[15] // 进程描述标识
struct procinf next // 链表指针
}procinf

/ =============函数声明部分============ /
space initmem( int n )
space allocboundtag( word pav int n )
status recyclealg(space p space pav)
space dusort( word pav )
void insert(word pav word p)
space delnode(procinf h char id[15])
status insertproinf(procinf h space inser char id[15])

int _tmain(int argc _tchar argv[])
{
word p ret_proc_add rec // p存放申请内存地址的头指针
procinf pi_h = null // 运行进程链表头指针

int i
int num
int size
int n = initsize
char id[15] // 存放进程标识

pi_h= (procinf )malloc(sizeof(procinf)) // 初始化运行进程链表头结点
pi_h -> next =null

p = initmem(n) // 初始化申请的内存空间，刚开始为一整块空白内存大小为n
if(!p) // 判断是否申请成功，失败结束运行
{
printf(" 内存初始化失败!\n" )
exit(1)
}

//测试用例

// 输入要创建进程的个数
printf(" 要申请的空间个数及其每一个空间所需要的存储空间：\n" )
scanf(" d" & num)

for( i = 0 i < num i++ )
{
l: printf(" 第d个空间的存储空间和空间的id：" i+1)
scanf(" ds" & size id)
getchar() // 吸收回车符号

ret_proc_add = allocboundtag( p size ) // 内存分配大小为size
if(!ret_proc_add) // 判断内存是否分配成功
{
printf(" 内存可能不足，分配失败，重新输入.\n" )
goto l
}

insertproinf(pi_h ret_proc_add id) // 插入到已经分配的内存链表当中

printf(" 分配内存标识：s 首地址：0xx 大小：d\n" id ret_proc_add ret_proc_add -> size)
}

for( i = 0 i < num i++ )
{
printf(" 输入要回收结点的名字：" )
scanf(" s" id)
getchar()
rec = delnode(pi_h id)
if(!rec)
{
printf(" 输入结点无效 请重新输入.\n" )
--i
}
else
recyclealg(rec p)

}
getchar()
return 0
}

space delnode(procinf h char id[15])
{
procinf t p
p = h -> next
t = h

if( !p )
{
printf(" 此空间不存在!\n" )
return null
}

while(p -> next!=null & & strcmp(id p-> name))
{
t = p
p = p-> next
}

if( p -> next!=null )
{
t -> next = p-> next
return p -> sp_head
}
else if(!strcmp(id p-> name))
{
t -> next = p -> next
return p-> sp_head
}
else
{
printf(" 此空间不存在!\n" )
return null
}
}

status insertproinf(procinf h space inser char id[15])
{
procinf t p
p = h-> next

if( h-> next == null )
{
if(!(t = (procinf )malloc(sizeof(procinf))))
return error
t -> sp_head = inser
strcpy( t -> name id)
t -> next = null
p = t
h -> next = p
return ok
}
else
{
if(!(t = (procinf )malloc(sizeof(procinf))))
return error
t -> sp_head = inser
strcpy( t -> name id)
t -> next = null

while(p-> next)
p = p-> next
p -> next = t
return ok
}

}

space initmem( int n ) // 初始化分配可利用内存的大小
{
space p

p = (space)malloc(nsizeof(word))

if( p )
{
p -> tag = 0 // 设置使用标志为：未使用
p -> size = n // 设置大小
p -> rlink = p -> link = p // 初始化指针
p -> uplink = p //指向本身

return p
}
else
return error // 分配失败
}

space allocboundtag( word pav int n ) // 若有不小于n的空闲块，则分配相应的存
{ // 储块，并返回其首地址；否则返回空，若
space p f // 分配后可利用空间表不空，则pav指向表中刚分配过的结点的后继结点。

// 查找不小于n的空闲块
for( p = pav p & & p-> size < n & & p-> rlink != pav p = p-> rlink )

if( !p || p-> size < n )
return null // 查找失败返回空指针
else // p指向找到的空闲块
{
f = footloc(p) // f指向此空闲块的底部
pav = p-> rlink // pav指向p结点的后继结点

if( p-> size-n < = minsize ) // 整块分配，不保留< =minsize的剩余量
{
if( pav == p ) // 如果可利用空间表变为空表，则置pav为空
pav=null
else
{ // 在表中删除分配的结点
pav-> link = p-> link
p-> link-> rlink=pav
}
p-> tag = f-> tag = 1 // 修改分配节点的头部和底部的标志
}
else // 分配该块的后n个字
{
f-> tag = 1 // 修改分配块的底部标志
p-> size -= n // 置剩余块的大小
f = footloc(p) // 指向剩余块的底部
f-> tag = 0 f-> uplink = p //设置剩余块的底部
p = f + 1 // 指向分配块的头部
p-> tag = 1 // 设置分配块头部
p-> size = n // 设置分配块的大小
}

return p // 返回分配块首地址
}
}

status recyclealg(space p space pav) // 回收算法
{
space f q ql t s
int n

if( (p-1)-> tag != 0 & & (p+p-> size)-> tag != 0 )
{
// 释放块的左右邻区均为占用块

printf(" 释放块的左右邻区均为占用块.\n" )
p -> tag = 0
footloc(p) -> uplink = p
footloc(p) -> tag = 0
if( !pav )
pav = p -> link = p -> rlink = p
else
{
q = pav -> link
p -> rlink = pav
p -> link = q
q -> rlink = pav -> link = p
pav = p // 令刚释放的结点为下次分配时的最先查询结点
}
}

if((p-1)-> tag == 0 & & (p+p-> size)-> tag != 0)
{
// 释放块左邻区为空闲块

printf(" 释放块左邻区为空闲块.\n" )
n = p -> size // 释放块的大小
s = (p-1)-> uplink // 左空闲块的的头部地址
s -> size += n // 设置新的空闲块的大小
f = p + n - 1 // 设置新的空闲块的底部
f -> uplink = s
f -> tag = 0
}

if( (p+p-> size)-> tag==0 & & (p-1)-> tag != 0 )
{
//释放块的右邻区为空闲块

printf(" 释放块的右邻区为空闲块.\n" )
t = p + p -> size // 右邻空闲块的头部地址
p -> tag = 0 // p为合并后的结点头部地址
q =t -> link
p -> link = q
q -> rlink = p
ql = t -> rlink
p -> rlink = ql
ql -> link = p
p -> size += t-> size
footloc(t) -> uplink = p
}

if((p-1)-> tag == 0 & & (p+p-> size)-> tag == 0)
{
// 释放块的左右邻块均为空闲块

printf(" 释放块的左右邻块均为空闲块.\n" )
n = p-> size
s = (p-1)-> uplink
t = p+p-> size
s -> size += n + t -> size
q = t -> link
ql = t -> rlink
q -> rlink = ql
ql -> link = q
footloc(t) -> uplink = s
}

return 0
}

space dusort( word pav ) // 双链表排序
{
space p q
p = null
q = pav -> rlink
if(!pav) return null // 如果为空链表，则返回空
while(q -> rlink != q-> link) //
{
pav-> link-> rlink = pav-> rlink
pav-> rlink-> link = pav-> link

insert(p pav)

pav = q
q = q-> rlink
}
insert(p q) // 将最后一个结点插入
return p
}

void insert(word pav word p) // 插入排序，按照可用大小从小到大
{
word t
t = pav
if(!pav)
{
pav = p
pav -> rlink = pav -> link
}
else
{
while(t-> size< p-> size)
{
t = t-> rlink
}
p -> rlink =t
p -> link = t-> link
t -> link-> rlink = p
t -> link = p
}
}