Defragmentation Homework

README.md

陶玮 写于 2016-12-25

Project5: Defragmentation


Overview

  • frag: 输入的文件.
  • defrag: 输出的文件.
  1. 首先将boot block从frag拷贝至defrag
  2. 读取fragsuperblock,获取块大小blk_size,inodes的个数inode_num,并将frag里面的inode block保存至inodes
  3. begin_data用于记录data block的起始位置,此时调用函数fseek,使得同时指向fragdefrag的相同位置,即begin_data
  4. 对inodes逐个进行处理(直至data_blk_num <= 0):
    4.1 若inode未使用则跳过不处理。
    4.2 否则确定该inode对应文件指向的data block个数data_blk_num
    4.3 处理直接索引:按照dblocks顺序读取frag的数据块,然后连续地存储至defrag中,同时更新dblocks的数据。每读取写入一次,data_blk_num减1,以下间接索引同此,遂不赘述。
    4.4 处理一级间接索引:对于每个iblocks,调用indirect(int offset)进行数据块处理,并更新iblocks的数据写入至defrag中。
    4.5 处理二级间接索引:首先读取二级索引的地址,将其对应的每个一级索引块调用indirect(int offset)进行数据块处理,并同时更新这些块的一级间接索引数据。最后更新二级索引数据写入至defrag中。
    4.6 处理三级间接索引:首先读取三级索引的地址,将其对应的每个二级索引块进行形同4.5的处理。
  5. 处理空闲块:改变superblockspblkfree_iblock,将每个空闲块的前4个字节指向下一个空闲块,最后一个置为-1。空闲块其他字节作清零处理。写入至defrag中。
  6. 最后更新superblock和inodes block内容并写入至defrag中。
  7. 注:assert()函数主要用于调试。

Function: indirect()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
int indirect(int offset)
{ // this function is used to deal with inodes which have pointers to indirect blocks
assert(fseek(frag, (offset - offset_frag) * blk_size, SEEK_CUR) == 0);
offset_frag = offset + 1;

// initialize one-block buffer and store information which is similar to 'dblocks'
int *blkbuf = (int *)malloc(blk_size);
assert(fread(blkbuf, blk_size, 1, frag) == 1);

// initialize 'buffer' which is used to store data block information and 'node_buffer'(it has been described above)
int *buffer = (int *)malloc(blk_size);
memset(buffer, 0, blk_size);
memset(node_buffer, 0, sizeof(*node_buffer));

// n: number of indirect pointers in the one block
int n = (data_blk_num > blk_size/sizeof(int)) ? blk_size/sizeof(int) : data_blk_num;

// 'node_buffer' has the value of pointers in this block and its identity
for(int i = 0; i < n; i++)
{
node_buffer[i].num = i;
node_buffer[i].offset_dtblk = blkbuf[i];
// let the 'blkbuf' has new value which will be used in the 'defrag'
blkbuf[i] = offset_defrag + i;
}

// the contents of the array 'node_buffer' are sorted
qsort(node_buffer, n, sizeof(node), cmp);

for(int i = 0; i < n; i++)
{
assert(fseek(frag, (node_buffer[i].offset_dtblk - offset_frag) * blk_size, SEEK_CUR) == 0);
offset_frag = node_buffer[i].offset_dtblk + 1;

// in the 1st time
if(i == 0)
{
assert(fseek(defrag, node_buffer[i].num * blk_size, SEEK_CUR) == 0);
}

// not in the 1st time
else
{
assert(fseek(defrag, (node_buffer[i].num - node_buffer[i-1].num - 1) * blk_size, SEEK_CUR) == 0);
}

// read the data and store them to 'buffer'
assert(fread(buffer, blk_size, 1, frag) == 1);

// store them from 'buffer' to 'defrag'
assert(fwrite(buffer, blk_size, 1, defrag) == 1);
}

// return to the position before using the function
assert(fseek(defrag, (n - 1 - node_buffer[n-1].num) * blk_size, SEEK_CUR) == 0);

data_blk_num -= n;
offset_defrag += n;

free(buffer);

// the new indirect block
fwrite(blkbuf, blk_size, 1, defrag);
free(blkbuf);

offset_defrag++;
return offset_defrag-1;
}

代码上有详实的注释啦! ⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄
我就不写啦 (•̀ᴗ•́)و ̑̑
重点在下面啦 ( * ̄▽ ̄)


Efficiency Optimization

  1. 本来准备用递归调用函数来处理简介索引的,但考虑到递归算法通常耗时较大,而且本次作业中最多只有三级间接索引,是有限次数的。所以只写了一级间接索引的处理函数,二级,三级间接索引进行转化,for循环调用indirect()即可。
  2. 创建了结构体如下
    1
    2
    3
    4
    5
    6
    // this structure helps using function 'fseek' efficiently
    typedef struct NODE
    {
    int offset_dtblk; // offset of pointers to data blocks
    int num; // number indentify the 'offset_dtblk'
    }node;

inode_buffer数组,存放一级间接索引时的索引块,并按照offset_dtblk的顺序进行排序,方便调用函数fseek()读取frag文件时,尽可能地少用SEEK_SET而用SEEK_CUR,提高fseek()的使用效率。并按照读取顺序,连续地依次存储在defrag的数据区域中。其中结构体中的num用于保存frag中间接索引的顺序,方便标识对应的offset_dtblk,在存储至dafrag时,num也用于表示指针位置。

作业来自 http://ybwu.org/ecnu-oslabs/projects/defragmentation/docs/defragmentation.html


分享至: 微博 微信 空间 QQ



* 提示 | 本网站评论系统自2017年5月7日由多说更换为畅言。因迁移数据表情/头像显示错误,故未予显示,尽请谅解。