一、当前文件格式定义:
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
}
}
分享到:
相关推荐
将文件中的数据读入内存,建立图的存储结构,可以选择邻接表或邻接矩阵作为存储结构,存储结构要准确记录旅游区各旅游景点及其相邻景点之间的相关信息。给出存储结构的C语言定义。 3、查询、编辑景点信息 提供用户...
以UNIX系统文件部分系统调用为基础设计一个简易的图书管理系统。要求实现:图书的录入、查询、借阅、清理、统计等功能、还要实现对每天的借阅情况进行统计并打印出统计报表,操作界面要尽量完善。图书资料信息必须...
将文件中的数据读入内存,建立图的存储结构,可以选择邻接表或邻接矩阵作为存储结构,存储结构要准确记录旅游区各旅游景点及其相邻景点之间的相关信息。给出存储结构的C语言定义。 3、查询、编辑景点信息 提供用户...
将文件中的数据读入内存,建立图的存储结构,可以选择邻接表或邻接矩阵作为存储结构,存储结构要准确记录旅游区各旅游景点及其相邻景点之间的相关信息。给出存储结构的C语言定义。 3、查询、编辑景点信息 提供用户...
7.1.2 结构体类型变量的定义方法及其初始化 7.1.3 结构体变量的引用 7.1.4 结构体数组 7.1.5 指向结构体变量的指针 7.1.6 结构体类型数据作为函数参数 *7.1.7 动态分配和撤销内存的运算符new和delete 7.2 共用体 ...
4.1.3电子文件基本数据类型定义及其代码可分别为: . 文本文件(Text,代码T) . 指使用文字处理软件生成的,由字、词、数字符号表达的文件。文本文件中除了存储 有效 字符信息(包括能用ASCLL码字符表示的回车、...
命令行中指定输入文件名、输出文件名(文本文件); 将输入文件打开,读入输入缓冲区;...自己定义相应操作的命令字符(一般为单个字符),用户可以输入h(或H)表示要求帮助,此时应显示所有的操作命令及其含义。
7.1.2 结构体类型变量的定义方法及其初始化 7.1.3 结构体变量的引用 7.1.4 结构体数组 7.1.5 指向结构体变量的指针 7.1.6 结构体类型数据作为函数参数 *7.1.7 动态分配和撤销内存的运算符new和delete 7.2 共用体 ...
《C++程序设计》 课程设计说明书 题 目 长途客运售票管理系统的设计 学 号 姓 名 指导教师 日 期 C++课程设计长途客运售票管理系统全文共25页,当前为第1页。 C++课程设计长途客运售票管理系统全文共25页,当前为第1...
2.1 线性表的定义及其运算 2.1.1 线性表的定义 2.1.2 各种运算简介 2.2 线性表的顺序存储结构(向量) 2.2.1 顺序存储结构(向量) 2.2.2 向量中基本运算的实现 2.3 线性表的链表存储结构 2.3.1 单链表与...
这是一个基于遗传算法的社区发现算法代码 ...3.SpeciesPopulation.java:物种群,用链表的形式来存储每一个SpeciesIndividual个体 4.GeneticAlgorithm.java:遗传算法步骤,包括选择交叉变异等操作 5.MainRun.java:主函数
课程设计任务内容 设计一个简易的学生成绩管理系统,能够完成学生成绩的增加、删除、查找、修改、统计等操作,数据信息保存文件保存。要求系统具有菜单和提示,界面友好。 2.课程设计要求 实现学生成绩的管理和保存...
2、功能的观点 操作系统是一个计算机资源管理系统,它负责计算机系统的全部资源的分配、控制、调度和回收。 3、用户的观点 操作系统是计算机与用户之间的接口,用户通过这种接口使用计算机。 4、软件的观点 操作系统...
第5章 文件系统的系统调用 5.1 系统调用Open 5.2 系统调用read 5.3 系统调用write 5.4 文件和记录的上锁 5.5 文件的输入/输出位置的调整lseek 5.6 系统调用close 5.7 文件的建立 5.8 特殊文件的建立 5.9 改变...
• 数据库管理系统的功能和特征 • 数据库模型(概念模式、外模式、内模式) • 数据模型,ER图,第一范式、第二范式、第三范式 • 数据操作(集合运算和关系运算) • 数据库语言(SQL) • 数据库的...
2.1.2用户的注册与注销11 2.1.3账户的管理12 2.1.4用户口令的管理12 2.1.5...格式68 5.1.3shell程序的运行方式69 5.2shell变量的使用69 5.2.1shell变量及变量赋值69 5.2.2变量的访问及变量参数替换70 5.2.3变量的作用域...
4.4.1 字符串宏定义及其基本格式 4.4.2 使用宏需注意的问题 4.4.3 撤销己定义的宏 4.4.4 带参数的宏定义 习题四 第5章 数组 5.1 一维数组 5.1.1 一维数组定义及数组元素引用 5.1.2 数组元素的引用...
操作系统的五大主要功能:存储管理、进程和处理机管理、文件管理、设备管理、用户接口管理。 【理解】 1.操作系统的特征:并发、共享和异步性。 理解模拟:并发——“大家都前进了”; 共享——“一件东西...
数据库管理系统的功能和特征 数据库的控制功能 数据仓库和分布式数据库基础知识 2.3 计算机网络知识 网络体系结构 传输介质,传输技术,传输方法,传输控制 常用网络设备和各类通信设备的特点 ...