28 文件存储空间管理

文件存储空间分配方法与内存分配有许多相同之处,即同样采用连续或离散分配方式。文件存储空间的分配单位是磁盘块而不是字节。

1 空闲表法

空闲表法属于连续分配方式,它与内存的动态分配方式雷同,它为每个文件分配一块连续的存储空间,即系统也为外存上所有空闲区建立一张空闲表,每个空闲区对应于一个空闲表项,其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块号等信息,再将所有空闲区按其起始盘块号递增排列。

空闲盘区的分配与内存的动态分配类似,同样采用首次适应算法,循环首次适应算法等。

系统在对用户所释放的存储空间进行回收时,也采取类似于内存回收的方法,即考虑回收区是否与空闲表中插入点的前区和后区相邻接,对相邻接者应该予以合并。

当文件较小时,采用连续分配方式,当文件较大时,可采用离散分配方式。

2 空闲链表法

空闲链表法是将所有空闲盘区拉成一条空闲链。把链表分成两种形式,空闲盘块链和空闲盘区链。

2.1 空闲盘块链

这是将磁盘上的所有空闲空间,以盘块为单位拉成一条链。

当用户因创建文件而请求分配存储空间时,系统从链首开始,依次摘下适当数目的空闲盘块分配给用户。

当删除文件而释放空间时,系统将回收的盘块依次插入空闲盘块链的末尾,其优点是用于分配和回收一个盘块的过程简单,但在为文件分配盘块时,可能要重复操作多次

2.2 空闲盘区链

这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链,在每个盘区上除了含有只是下一个空闲盘区的指针外,还应有能指明本盘区大小(盘块数)的信息。

盘区分配与内存的动态分配类似,可采用首次适应算法,在回收盘区时,同样也要将回收区和相邻接的空闲盘区相合并,在采用首次适应算法时,可以采用显式链接法提高检索速度,在内存中为空闲盘区建立一张链表

3 位示图法

利用二进制的一位表示磁盘中的一个盘块的使用情况,当其值为0时,表示对应的盘块空闲,为1时,表示已经分配,磁盘上的所有盘块都有一个二进制位与之对应。由所有盘块所对应的位构成一个集合,称为位示图,通常可用m×n个位数来构成位示图,并使m×n等于磁盘的总块数。


对于盘块的分配分为如下三步:

  • 顺序扫描位示图,从中找出一个或一组值为0的二进制位。

  • 将所找到的一个或一组二进制位转换成与之赌赢的盘块号。

  • 修改位示图。

对于盘块的回收分为如下两步:

  • 将回收盘块的盘块号转换成位示图中的行号和列号。
  • 修改位示图。
优点
  • 从位示图中很容易找到一个或一组相邻接的空闲盘块。

  • 由于位示图很小,占用空间少,因而可将其保存在内存中,进而使在每次进行盘区分配时,无需首先把盘区分配表读入内存,节省磁盘启动时间。

3 成组链接法

空闲表法和空闲链表法都不适用于大型系统,因为这会使空闲表或空闲链表很长,在UNIX采用的成组链接法,结合上述两种方法。

    1. 空线盘块的组织,空闲盘块栈用来存放当前可用的一组空闲盘块的盘块号(最多含100个号),以及栈中尚有的空闲盘块号数N,顺便指出,N兼做栈顶指针使用,栈是临界资源,系统设置一把锁供进程互斥访问。其中,S.free(0)是栈底,栈满时栈顶为S.free(99)。
    1. 文件区中的所有空闲盘块被分成若干个组,如每100个盘块作为一组。
    1. 将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块S.free(0)~S.free(99)中,这样,由各组的第一个盘块可链接成一条链。
    1. 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中,作为当前可供分配的空闲盘块号。
    1. 最末一组只有99个盘块,其盘块号分别记入其前一组的S.free(1)~S.free(99)中,而在S.free(0)中则存放0,作为空闲盘块链的结束。

当系统要为用户分配文件所需的盘块时,须调用盘块分配过程来完成:

  • 首先检查空闲盘块号栈是否上锁,如未上锁,便从栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格。

  • 若该盘块号已是栈底,即S.free(0),这是当前栈中最后一个可分配的盘块号。将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内 容,并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。

  • 然后,再分配一相应的缓冲区(作为该盘块的缓冲区)。最后,把栈中的空闲盘块数减1并返回。

在系统回收空闲盘块时,须调用盘块回收过程进行回收:

  • 它是将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1操作。

  • 当栈中空闲盘块号数目已达100时,表示栈已满,便将现有栈中的100个盘块号,记入新回收的盘块中,再将其盘块号作为新栈底

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,179评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,229评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,032评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,533评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,531评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,539评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,916评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,574评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,813评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,568评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,654评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,354评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,937评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,918评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,152评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,852评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,378评论 2 342

推荐阅读更多精彩内容