实 验 报 告课程名称操作系统实验名称文件系统存储空间管理模拟专业班级计 1001 姓 名 郭军涛学 号 201007010108 实验日期2013.06.20 成绩指导教师王潇潇一、 实验内容1. 模拟文件空间分配、释放过程，可选择连续分配、链式分配、索引分配方法；2. 文件空闲空间管理，可采用空白块链、空白目录、位示图方法；二、实验要求及原理根据提出的文件分配和释放请求，动态显示磁盘空闲空间的状态以及文件目录的变化，以位示图和索引分配为例：每次执行请求后要求显示或打印位示图的修改位置、分配和回收磁盘的物理块地址、更新的位示图、目录。地址过程；用数组表示位示图，其中的每一位对应磁盘一个物理块的状态，0 表示、空闲， 1 表示分配； 当请求分配一个磁盘块时，寻找到数组中为0 的位，计算相对磁盘块号，并计算其在磁盘中的物理地址（柱面号、磁道号、物理块号），并将其状态由0 变到 1。当释放某一物理块时，已知其在磁盘中的物理地址，计算其相对磁盘块号，再找到位示图数组中的相应位，将其状态由1 变为 0。三、实验步骤1. 输入磁盘基本信息参数，计算位示图大小，并随机初始化位示图；（1）磁盘基本信息：磁盘柱面数m, 每柱面磁道数p, 每磁道物理块数q；（2）假设采用整数数组存放位示图，则数组大小为：Size= ceil（ （柱面数 * 每柱面磁道数 *每磁道物理块数）/ （ sizeof(int)*8） ）（3）申请大小为size 的整数数组map ，并对其进行随机初始化。例如：假设m=2, p=4, q=8, 共有 64 个磁盘块，若 sizeof(int)=2, 则位示图大小为 4， map4 如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 map0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 map1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 map2 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 map3 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 位示图中每一位对应的相对磁盘块号如下图，磁盘块号由小到大对应于数组的低地址到高地址位上。 即 map0 的第 0 位到第 15 位分别对应0号磁盘块到15 号磁盘块的状态， map1的第 0 位到第 15 位对应 16 号磁盘块到31 号磁盘块的状态，以此类推。15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 map0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 map1 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 map2 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 map3 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 如上表所示， 29 号磁盘的状态存在map1 中，对应于第13 位；2. 输出初始位示图信息；3. 输入文件分配或释放请求，（ 1）格式：“+ 文件名申请块数”或“ - 文件名”“+”表示申请文件分配， “- ”表示删除文件如： + F1 5 4. 根据请求完成相应操作。（1）若为分配申请x 个盘块，则在位示图中找到x 个为 0 的位，将其修改为“1” ，计算相应具体物理设备的柱面号C、磁道号 H和物理块号R，并将 CHR地址或相对磁盘块号记录在文件目录中。 输出位示图修改位置、分配的磁盘块CHR地址、修改后的目录和位示图信息。否则，空间不够，退出执行下一条请求；计算公式如下：a. 已知位示图中的下标i , j, 计算相对块号 Block= i*sizeof( int )*8+j 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - b. 已知相对块号计算柱面、磁道、物理块号如下：柱面号 C= 相对块号 /( 每柱面磁道数 * 每磁道物理块数) 磁道号 H= 相对块号 % （每柱面磁道数*每磁道物理块数）/ 每磁道物理块数物理块号 R= 相对块号 % 每磁道物理块数文件目录如下（以索引表分配为例）：文件名首个物理块CHR地址块个数索引表beta (0，0，0) 2 (0,0,0)(0,0,1) Alpha (2,3,0) 3 (2,3,0) Toyota 4 3 （4 9 12 ）,Sony 文件名首个物理块地址( 相对 ) 块个数索引表beta 0 2 (0,2,3),Alpha 3 3 (3,6,7),Toyota 8 3 (8, 9,12),(2）若为删除申请，则从目录中找到要删除的文件所在的目录项，读取索引表，依次读取文件相应的盘块CHR 地址 , 计算该盘块的相对磁盘块号，再计算其相应信息在位示图中的位置 ( i,j)，将位示图中的相应位有“1”改为“ 0” ， 并从目录中删除该目录项。输出删除的磁盘块CHR 地址、相应位示图修改位置、修改过的位示图和目录。计算过程如下：相对磁盘块号 = 柱面号 *每柱面磁道数 * 每磁道物理块数+ 磁道号 * 每磁道物理块数+ 物理块号i = 相对磁盘块号 / (sizeof(int)*8) j = 相对磁盘块号 % (sizeof(int)*8) 四、源程序代码#include #include using namespace std; struct AllocatedSpace /已分配内存空间结构体 int start_address; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - int length; char job; struct AllocatedSpace *next; ; struct FreeSpace /未分配内存空间结构体 int start_address; int length; struct FreeSpace *next; ; struct AllocatedSpace *allocated_header; struct FreeSpace *free_header; struct FreeSpace *freenext; void allocatememory() /分配内存函数 char jobname; int joblength; int min,l=0; coutjobname; coutjoblength; struct FreeSpace *w=free_header; struct FreeSpace *p=free_header; /指向第一个可以分配的空闲结点p=p-next; struct FreeSpace *s=free_header; /指向 p 的前一个结点struct AllocatedSpace *t=allocated_header; while(p-lengthnext; if(p=NULL) break; if(p=NULL) coutlength-joblength; while(p!=NULL) /现在 p 指向当前要被切割的结点 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - if(p-lengthjoblength) l=p-length-joblength; if(lnext; struct AllocatedSpace *q=new AllocatedSpace; q-job=jobname; q-length=joblength; q-start_address=w-start_address; while(t-next!=NULL) t=t-next; q-next=t-next; t-next=q; while(s-next!=w) s=s-next; if(w-length=q-length) s-next=w-next; delete w; else w-start_address=w-start_address+q-length; w-length=w-length-q-length; void reclaimmemory() char jobname; coutjobname; struct FreeSpace *p=new struct FreeSpace;/指向当前被创建的空闲结点struct FreeSpace *s=free_header;/指 p 的前一个结点struct FreeSpace *m=free_header;/指向 s 的前一个结点struct AllocatedSpace *q=allocated_header;/ 指向被回收的结点struct AllocatedSpace *t=allocated_header;/ 指向被回收的结点的前一个结点while(q-job!=jobname)/ 找到被回收的结点q=q-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - if(q=NULL) coutlength=q-length; p-start_address=q-start_address; while(s-start_addressstart_address) s=s-next; while(m-next!=s) m=m-next; p-next=s; m-next=p; coutnext!=q) t=t-next; t-next=q-next; delete q; s=free_header; m=free_header; s=s-next; m=m-next; while(m!=NULL) m=m-next; if(m=NULL) break; if(s-start_address+s-length=m-start_address) s-length=s-length+m-length; s-next=m-next; continue; s=s-next; void showmemory() struct FreeSpace *s=free_header;/指向 FreeSpace的头结点，开始往后遍历s=s-next; struct AllocatedSpace *q=allocated_header;/ 指向 AllocatedSpace 的头结点， 开始往后遍历q=q-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - cout已分配区的情况如下:n; while(q!=NULL) cout作业名:job开始地址:start_address长度:lengthnext; cout 空闲结点的情况如下:n; while(s!=NULL) cout 开始地址 :start_address 长度 :lengthnext; int main() int n; allocated_header=new struct AllocatedSpace; free_header=new struct FreeSpace; freenext=new struct FreeSpace; freenext-length=100000; freenext-start_address=0; freenext-next=NULL; free_header-next=freenext; allocated_header-next=NULL; while(1) cout *n; cout 请输入您要进行的操作：0 退出1 分配内存2 回收内存3 显示内存状态 n; coutn; switch(n) case 0:exit(0); case 1:allocatememory();break; case 2:reclaimmemory();break; case 3:showmemory();break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 五、实验结果（截图）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -