一、实习内容
模拟磁盘空闲空间的表示方法,以及模拟实现磁盘空间的分配和回收。

二、实习目的
磁盘初始化时把磁盘存储空间分成许多块(扇区),这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去,这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上,可以组织成顺序文件(连续文件)、链接文件(串联文件)、索引文件等,因此,磁盘存储空间的分配有两种方式,一种是分配连续的存储空间,另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题,通过本实习来掌握磁盘存储空间的分配和回收算法。


三、实习题目
连续磁盘存储空间的分配和回收

四、设计思想
1.设计思路
(1)要在磁盘上建立顺序文件时,必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。可假定磁盘初始化时,已把磁盘存储空间划分成若干等长的块(扇区),按柱面号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空间被分成许多区(每一区包含若干块),有的区存放着文件,而有的区是空闲的。当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录,当一个文件被删除时,则该文件占用的区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用的部分,格式如下:
序号    起始空闲块号    空闲块个数    状态
1     5    6     未 分 配
2    14     3    未 分 配
3     21     30     未 分 配
4            空 表 目
(2)建立文件时,先查找空闲区表,从状态为“未分配”的表项中找出一个块数能满足要求的区,由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时,则剩余的块仍应为未分配的空闲块,这时要修改起始空闲块号和空闲块数。若占用了该区的所有块,则相应登记栏中的状态修改成“空表目”。删除一个文件时,需要考虑空闲块的合并情况。
(3)当找到空闲块后,必须启动磁盘把信息存放到指定的块中,启动磁盘必须给出由三个参数组成的物理地址:盘面号、柱面号和物理记录号(即扇区号)。故必须把找到的空闲块号换算成磁盘的物理地址。
为了减少移臂次数,磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面,(编号0-199)每个柱面有20个磁道(编号0-19,同一柱面上的各磁道分布在各盘面上,故磁道号即盘面号),每个磁道被分成等长的6个物理记录(编号0-5,每个盘面被分成若干个扇区,故每个磁道上的物理记录号即为对应的扇区号)。那么,空闲块号与磁盘物理地址的对应关系如下:
物理记录号 = 空闲块号 % 6
磁道号 = (空闲块号 / 6 )% 20
柱面号 = (空闲块号 / 6)/ 20
(4)删除一个文件时,从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数,假定每个逻辑记录占磁盘上的一块,则可推算出归还后的起始空闲块号和块数,登记到空闲区表中。换算关系如下:
起始空闲块号 = (柱面号20 + 磁道号)6 + 物理记录号
空闲块数 = 逻辑记录数
(5)设计磁盘存储空间的分配和回收程序,把分配到的空闲块转换成磁盘物理地址,把归还的磁盘空间转换成空闲块号。

2.主要数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct FreeBlockMenu
{
	long FBbegin;//起始空闲块号
	long num;//空闲块个数
	struct FreeBlockMenu *next;
	struct FreeBlockMenu *front;
};
 
struct FiletoWrite
{
	char name[10];//装入的文件名,供回收磁盘空间时查找
	long size;//文件大小
	long addr_zhumian;//装入磁盘的首地址_柱面号
	long addr_cidao;//装入磁盘的首地址_磁道号
	long addr_jilu;//装入磁盘的首地址_物理记录号
	struct FiletoWrite *next;
	struct FiletoWrite *front;
};

3.主要代码结构及代码段分析

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
//分配磁盘空间
int getMalloc()
{
	int flag = 0;
	struct FreeBlockMenu *p = FBhead;
	struct FiletoWrite *File;
	File = (struct FiletoWrite *)malloc(sizeof(struct FiletoWrite));
	printf("请输入装入的文件名:\n");
	scanf("%10s",File->name);
	printf("请输入所需要的磁盘空间大小:\n");
	scanf("%d",&File->size);
	for(p = FBhead->next;p != NULL;p = p->next)
	{
		flag = 1;
		if(p->num >= File->size )
		{
			//分配空间,块号转化为物理地址
			File->addr_zhumian = (p->FBbegin/6)/20;
			File->addr_cidao = (p->FBbegin/6)%20;
			File->addr_jilu = p->FBbegin%6;
			//加入文件链表中
			File->next = Filehead->next;
			if(Filehead->next != NULL)
			Filehead->next->front = File;
			Filehead->next = File;
			File->front = Filehead;
 
			if(p->num > File->size)
			{
				//修改该块的起始地址和块数
				p->FBbegin = p->FBbegin + File->size;
				p->num = p->num - File->size;
			}
			else if(p->num == File->size)
			{
				//从空闲块表中删除该结点
				if(p->front != NULL)
				{
					if(p->next != NULL)
					{
						p->front->next = p->next;
						p->next->front = p->front;
						free(p);
					}
					else
					{
						p->front->next = p->next;
						free(p);
					}
				}
				else
				{
					p->next->front = p->front;
					free(p);
				}
			}
			printf("\n分配磁盘成功!\n该文件的物理地址为:(柱面号	磁道号	物理块号)\n");
			printf("			%d	%d	%d\n",File->addr_zhumian,File->addr_cidao,File->addr_jilu);
		}
	}
	if(flag == 0)
	{
		printf("对不起,目前没有足够的磁盘空间分配给该文件。");
		return 0;
	}
}
int showDisk();
 
//回收磁盘空间
int setFree()
{
	char name[10];
	int flag = 0;
	struct FiletoWrite *p = Filehead;
	printf("请输入要删除的文件名:\n");
	scanf("%10s",&name);
	for(p = Filehead;p != NULL;p = p->next)
	{
		if(strcmp(p->name , name)==0)//找到该文件
		{
			flag = 1;
			int houhebing=0,qianhebing=0;
			long m = p->addr_zhumian;
			long n = p->addr_cidao;
			long k = p->addr_jilu;
			long addr =120*m + 6*n + k;//块号
 
			//先考虑和后面的部分或许会有合并的情况
			long int tail=addr+p->size;
			struct FreeBlockMenu *pNode,*qNode;
 
			pNode=FBhead->next;
 
			while(pNode!=NULL)
			{
				if(pNode->FBbegin==tail)
				{
					pNode->FBbegin=addr;
					pNode->num=pNode->num+p->size;
					houhebing=1;
					qNode=pNode;
					break;
				}
				pNode=pNode->next;
			}
 
			//再考虑是否可以和前面的进行合并
			pNode=FBhead->next;
			while(pNode!=NULL)
			{
				if(pNode->FBbegin+pNode->num==addr)
				{
					if(houhebing==0)
					{
						pNode->num=pNode->num+p->size;
						qianhebing=1;
						break;
					}
					else if(houhebing==1)
					{
						pNode->num+=qNode->num;
						pNode=FBhead;
						while(pNode->next!=qNode)
							pNode=pNode->next;
						pNode->next=qNode->next;
						free(qNode);
						qianhebing=1;
						break;
					}
				}
				pNode=pNode->next;
			}
 
			//如果没有和前面的或者后面的进行合并,则新建一个表目
			if(qianhebing==0 && houhebing==0)
			{
		        	pNode=(struct FreeBlockMenu*)malloc(sizeof(struct FreeBlockMenu));
		         	pNode->FBbegin=addr;
		        	pNode->num=p->size;
				if(FBhead->next==NULL)
				{
					FBhead->next=pNode;
					pNode->front=FBhead;
					pNode->next=NULL;
					FBhead->front=NULL;
				}
				else
				{
					pNode->next=FBhead->next;
					FBhead->next->front=pNode;
					FBhead->next=pNode;
					pNode->front=FBhead;
				}
			}
 
			//在文件链表中删除该文件
			struct FiletoWrite *pPrev=p->front;
			if(p->next==NULL)
			{
				pPrev->next=NULL;
				free(p);
			}
			else
			{
				pPrev->next=p->next;
				p->next->front=pPrev;
			}
		}
	}
	if(flag == 0)
		printf("没有该文件!\n");
	else
		printf("删除文件成功!\n");
}
 
//显示磁盘空闲区表
int showDisk()
{
	struct FreeBlockMenu *p = FBhead;
	printf("\n磁盘空闲块表\n");
	printf("起始地址	空闲块大小\n");
	for(p = FBhead->next;p != NULL;p = p->next)
		printf("	%ld	%ld\n",p->FBbegin,p->num);
}
 
int main()
{
	char choose;	
	FBhead = (struct FreeBlockMenu *)malloc(sizeof(struct FreeBlockMenu));
	if(FBhead == NULL)
	{
		printf("error in allocating...\n");
	}
	else
		printf("successed\n");
	struct FreeBlockMenu *pNew=(struct FreeBlockMenu*)malloc(sizeof(struct FreeBlockMenu));
 
	pNew->FBbegin = 0;
	pNew->num = 24000;
	pNew->next = pNew->front = NULL;
 
	FBhead->next=pNew;
	FBhead->front=NULL;
	pNew->front=FBhead;
	pNew->next=NULL;
	Filehead = (struct FiletoWrite *)malloc(sizeof(struct FiletoWrite));
	Filehead->next = Filehead->front = NULL;
	char buf[128];
	do
	{
	system("clear");
	printf("---------------------------\n");
	printf("1.请求磁盘空间\n");
	printf("2.回收磁盘空间\n");
	printf("3.显示磁盘空闲区表\n");
	printf("4.退出\n");
	printf("---------------------------\n");
		printf("请选择:");
		scanf("%c",&choose);
		switch(choose)
		{
			case '1':
				getMalloc();
				gets(buf);break;
			case '2':
				setFree();
				gets(buf);break;
			case '3':
				showDisk();
				gets(buf);break;
			case '4':
				exit(1);break;
			default:
				gets(buf);
				printf("输入错误!请重新输入。\n");
				break;
		}
		printf("\n");
		getchar();
	}while(choose != '4');
}

五、上机实习所用平台及相关软件
本程序在Linux平台(Ubuntu8.04.1)下,使用vi编辑器编写,g++编译通过。

六、调试过程
测试数据:
文件名    请求磁盘空间大小
aaa    20
bbb    1000
ccc     2000
ddd    3000
测试结果:
截图(略)

七、总结
(1)磁盘空闲区表和文件的数据结构我均使用了双链表来构建,这样可以很方便地访问到前驱节点,更容易进行链表节点的删除操作,节省了很多时间。
(2)在程序中充分考虑到出错处理。比如在功能选择菜单中,若用户输入非法字符则提示“输入错误!请重新输入”;在用户申请磁盘空间时,若要求的空间大小大于空闲空间大小,则提示“没有足够的磁盘空间”;在回收磁盘空间时,若用户输入的文件名不存在,则提示“没有该文件”。这样提高了程序的健壮性。
(3)在回收磁盘空间时,分情况讨论空闲块的合并。先考虑和后面的空闲块或许会有合并的情况,再考虑是否可以和前面的块进行合并,如果没有和前面或者后面的空闲块进行合并,则新建一个表目。这样程序结构清晰,逻辑性强。
(4)通过本实验,我进一步加深了对连续磁盘空间的分配回收过程的理解,同时也得到了将系统理论实践的机会,熟练了编程能力。