coding

Defragmentation Homework

README.md

陶玮 写于 2016-12-25

Project5: Defragmentation

Overview

  • frag: 输入的文件.
  • defrag: 输出的文件.
  1. 首先将boot block从frag拷贝至defrag。
  2. 读取frag的superblock，获取块大小blk_size，inodes的个数inode_num，并将frag里面的inode block保存至inodes。
  3. begin_data用于记录data block的起始位置，此时调用函数fseek，使得同时指向frag和defrag的相同位置，即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. 处理空闲块：改变superblockspblk的free_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日由多说更换为畅言。因迁移数据表情/头像显示错误，故未予显示，尽请谅解。
标签
coding
微信
微信公众号