注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

无线时代辐射无穷

抓紧生宝宝,小心辐射

 
 
 

日志

 
 

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

2011-06-21 12:31:18|  分类: 文件存储 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 
一、当前文件格式定义:

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("%d%s",&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,首地址:0x%x,大小:%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(n*sizeof(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; 
    } 
}  

  评论这张
 
阅读(810)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017