空闲磁盘存储空间的管理：位示图法

课程设计报告( 2009--2010年度第二学期)课程名称:操作系统实验课设题目: 用位示图管理磁盘空间的分配与回收院系:控制与计算机工程学院班级:姓名:指导教师:李为设计周数: 一周成绩:2010年7月9 日一、需求分析要求打印或显示程序运行前和运行后的位示图，以及分配和回收磁盘的物理地址过程。

（1）假定现有一个磁盘组，共40个柱面。

每个柱面4个磁道，每个磁道又划分成4个物理记录。

磁盘的空间使用情况用位示图表示。

位示图用若干个字构成，每一位对应一个磁盘块。

1表示占用，0表示空闲。

为了简单，假定字长为16位，其位示图如图9—1所示。

系统设一个变量S，记录磁盘的空闲块个数。

（2）申请一个磁盘块时，由磁盘块分配程序查位示图，找出一个为0的位，并计算磁盘的物理地址(即求出柱面号、磁道号(也即磁头号)和扇区号)。

由位示图计算磁盘的相对块号的公式如下：相对块号一字号×16+位号之后再将相对块号转换成磁盘的物理地址：由于一个柱面包含的扇区数＝每柱面的磁道数×每磁道的扇区数＝4×4＝16，故柱面号＝相对块号／16的商，即柱面号＝字号磁道号＝(相对块号／16的余数)／4的商，即(位号／4)的商物理块号＝(相对块号／16的余数)／4的余数，即(位号／4)的余数（3）当释放一个相对物理块时，运行回收程序，计算该块在位示图中的位置，再把相应位置0。

计算公式如下：先由磁盘地址计算相对块号：相对块号＝柱面号×16+磁道号×4+物理块号再计算字号和位号：字号＝相对块号／16的商，也即字号＝柱面号位号＝磁道号×物理块数／每磁道+物理块号（4）按照用户要求，申请分配一系列磁盘块，运行分配程序，完成分配。

然后将分配的相对块号返回用户，并将相对块号转换成磁盘绝对地址，再显示系统各表和用户已分配的情况。

（5）设计一个回收算法，将上述已分配给用户的各盘块释放。

并显示系统各表。

空闲磁盘存储空间的管理：位示图法空闲磁盘存储的管理：位示图法1：建立相应的数据结构2：磁盘上建立一个文件，文件长度设为10MB,为该文件来模拟一个磁盘，磁盘的物理块大小为512字节3：显示每次磁盘的请求和空间释放后的位示图状态4显示每次磁盘的请求和空间释放后的全磁盘的状态5：模拟文件的创建和删除，从而产生磁盘潘快请求和释放，验证以上设计代码：// OS暑?期ú课?程ì设Θ?计?.cpp : 定¨义?控?制??应畖用?程ì序ò的?入?口ú点?。

￡//#include"stdafx.h"#include#include#includeusing namespace std ;//文?件t类え?class file{public:string name ;int occupy ;int grade_block ;int start ;};#define MAX_LINE 3#define MAX_COLUMN 32int BIT[32][1000];int byte[MAX_LINE] ;int file_count;int judge[32] ;int judge2[32];int cycle ;file f[1000];void init(int line ,int column);void show() ;void set(int now_location, int occupy );void clear(int now_location, int occupy);void bitset(int index ,int temp_block_quantity);void create_file(string temp_name, int temp_occupy );void delete_file(string name);bool byte_judge(int num,int i);int _tmain(int argc, _TCHAR* argv[]){string cmd;string file_name ;int file_occupy ;init( MAX_LINE, MAX_COLUMN ) ; //初?始?化ˉwhile ( cin >> cmd ) //{if( "q" == cmd || "Q" == cmd ){exit(0) ;return 0 ;}cin >> file_name ;if("create" == cmd){cin >>file_occupy ;create_file(file_name,file_occupy);}else{delete_file(file_name) ;}}return 0;}void show(){for(int i = 0 ; i < MAX_LINE ; i ++){for(int j = 0 ; j < MAX_COLUMN ; j ++){//cout<cout<<byte_judge(byte[i],j)<<" ";<="" p=""> }cout<< endl ;}}void set(int now_location, int occupy ){int line ;int column ;for(int i = 0 ; i < occupy ; i ++ ){line = (now_location - i) / MAX_COLUMN ;column = (now_location - i ) % MAX_COLUMN ; //BIT[line][column] = 1 ;byte[line] |= judge[column];}}//清?零?void clear(int now_location, int occupy){int line ;int column ;for(int i = 0 ; i < occupy ; i ++){line = (now_location + i) / MAX_COLUMN ; column = (now_location + i ) % MAX_COLUMN ; //BIT[line][column] = 0 ;byte[line] &= judge2[column];}}void bitset(int index ,int temp_block_quantity) {int block_quantity = temp_block_quantity ;int free_quantity = 0 ;int line, column ;int sign = cycle - 1 ;for (;; cycle++ ){line = cycle / MAX_COLUMN ;column = cycle % MAX_COLUMN ;if( 0 == byte_judge(byte[line],column)){free_quantity ++ ;}else{free_quantity = 0 ;}if(free_quantity >= block_quantity ){f[index].start = cycle - block_quantity + 1;set(cycle, block_quantity);cycle ++;cout<<"create file success"<<endl;< p="">show();return ;}if(cycle >= MAX_LINE * MAX_COLUMN-1){cycle = -1;free_quantity = 0;}if(sign == cycle ){break ;}}cout<<"error: create file fail"<<endl;< p="">}void create_file(string temp_name, int temp_occupy ) {int block_quantity ;f[file_count].name = temp_name ;block_quantity = temp_occupy / 512 + 1 ;f[file_count].occupy=block_quantity ;bitset(file_count ,block_quantity );file_count ++ ;}//删?除y文?件tvoid delete_file(string name){for(int i = 0 ; i < file_count ; i ++){if(name == f[i].name){clear(f[i].start,f[i].occupy);for(int j = i; j < file_count - 1; j ++){f[j] = f[ j + 1 ];}file_count -- ;cout<<"delete file success"<<endl;< p=""> show();return ;}}cout<<"ERROR THE FILE NOT EXIST"<< endl ; }//初?始?化ˉvoid init(int line ,int column){int con = 1 ;file_count = 0 ;cycle = 0 ;for(int i = 0; i < 32 ; i ++) {judge[i] = con ;judge2[i]=judge[i];judge2[i] ^= 0xffffffff;con*=2;}for(int i =0 ; i<="" p=""> byte[i]= 0;}bool byte_judge(int num,int i) {bool result ;result = num & judge[i]; return result;}</endl;<></endl;<></endl;<></byte_judge(byte[i],j)<<">。

⽂件管理-空闲存储空间的管理
空闲存储空间管理:在磁盘上会有⼤量的空闲的空间,我们要将这些空闲的空间管理起来,以便在某个⽂件在申请相应空间的时候,能够有依据的分配他空间.
主要分为这⼏种办法:
空闲区表法:使⽤⼀个表来记录哪些空间是空闲的,以便来将这些空间管理起来
空闲链表法:将这些空闲的区域链成⼀条链表,当想要进⾏空间分配的时候,从这条链表之划出需要的空间来.
位⽰图法:表中 1表达该空间被占⽤了,⽽0表⽰该空间是空闲的,就像电影院选座⼀样.
成组链接法:
练习题:
4195物理块是第4196个物理块(因为是题⽬是从0开始计算的).
⽽系统中字长为32位,所以该物理块的使⽤情况应该在位⽰图的 (物理块编号+1)/系统字长 ,即是(4195+1)/32=131.25
131.25说明前131个字都有描述物理块,⽽他刚好在132个字被描述.
想要将4195号物理块分配给某⽂件,所以这个时候应该描述该任务为1,表⽰被占⽤.
想要得知在哪个位置上描述,可以先计算出上⼀个字的描述的最后⼀个物理块的位置
131*32=4192,4192-1=4191,所以131字描述的最后⼀个物理块是4191编号的物理块
所以4191号物理块的下⼀个物理块4192号物理块是在132的第0个位置被描述其使⽤情况.
以此类推4193号就是132字第⼀个位置.
即4195号物理块是132字的第三个位置被描述其使⽤情况的.
所以答案是D和B.。

在文件存储设备管理中,三类常用字的空闲块管理方法文件存储设备管理中的空闲块管理方法简介在文件存储设备管理中，对于空闲块的管理是非常重要的。

空闲块是指存储设备中尚未被使用的块或扇区。

本文将详细介绍三种常用的空闲块管理方法。

方法一：位图法位图法是一种常见的空闲块管理方法。

它通过一个位图来表示存储设备中的每个块的使用情况。

1.创建一个位图，每个位表示一个块。

2.当一个块被占用时，对应位图上的位被设置为1，表示被占用。

3.当一个块被释放时，对应位图上的位被设置为0，表示变为空闲。

该方法的优点是简单高效，但是位图的大小与存储设备的块数成正比，当存储设备较大时，位图的大小也会相应增大。

方法二：空闲链表法空闲链表法是另一种常用的空闲块管理方法。

它通过链表的形式来管理存储设备中的空闲块。

1.维护一个空闲块链表，链表中的每个节点表示一个空闲块。

2.当一个块被占用时，从空闲块链表中删除对应的节点。

3.当一个块被释放时，将该块加入到空闲块链表的末尾。

该方法的优点是节省空间，因为链表节点只需要额外记录下一个节点的指针即可。

但是在查找空闲块时需要遍历链表，效率较低。

方法三：索引表法索引表法是一种较为复杂的空闲块管理方法。

它通过索引表来记录存储设备中的所有块的使用情况。

1.创建一个索引表，表中的每个项表示一个块，包括块的地址和使用标记。

2.当一个块被占用时，在索引表中标记对应的项为已使用。

3.当一个块被释放时，将对应的索引表项标记为未使用。

该方法的优点是可以减少存储设备的访问时间，因为索引表可以直接定位到对应的块。

缺点是索引表需要额外的空间来存储，且操作复杂。

总结以上介绍了三种常用的空闲块管理方法：位图法、空闲链表法和索引表法。

每种方法都有其优缺点，选择合适的方法需要根据具体情况来决定。

在实际应用中，可以根据存储设备的大小、访问模式等因素进行选择和优化。

对于每种空闲块管理方法，我们来进一步了解它们的特点和适用场景。

1. 位图法•特点：简单高效，易于实现和理解。

用位示图管理磁盘存储空间一、实习内容模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。

二、实习目的磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。

用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。

一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。

怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实习使学生掌握磁盘存储空间的分配和回收算法。

三、实验分析连续的磁盘存储空间的分配和回收。

四、算法及说明(1) 为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。

为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。

位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。

(2) 申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。

假设现在有一个盘组共8个柱面，每个柱面有2个磁道（盘面），每个磁道分成4个物理记录。

那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：柱面号=字节号磁道号= 位数/ 4物理记录号= 位数% 4(3) 归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。

按照（2）中假设的盘组，归还块在位示图中的位置计算如下：字节号=柱面号位数=磁道号 4+物理记录号五、用到的数据结构及模块说明int area[8][8]; 表示位示图，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。

国家开放大学《操作系统》形考任务（简答题）参考答案1．简述操作系统的定义。

参考答案:操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

2．在计算机系统中操作系统处于什么地位？参考答案:操作系统是裸机之上的第一层软件，与硬件关系尤为密切。

它不仅对硬件资源直接实施控制、管理，而且其很多功能的完成是与硬件动作配合实现的，如中断系统。

操作系统的运行需要有良好的硬件环境。

操作系统是整个计算机系统的控制管理中心，其他所有软件都建立在操作系统之上。

操作系统对它们既具有支配权力，又为其运行建造必备环境。

在裸机上安装了操作系统后，就为其他软件的运行和用户使用提供了工作环境。

3．操作系统的主要功能有哪些？参考答案:操作系统的主要功能包括：存储管理，进程和处理机管理，文件管理，设备管理以及用户接口管理。

4．操作系统一般为用户提供了哪三种界面？各有什么特点？参考答案：操作系统一般为用户提供的三种界面是：图形用户接口、命令行接口和程序接口。

图形用户接口：用户利用鼠标、窗口、菜单、图标等图形界面工具，可以直观、方便、有效地使用系统服务和各种应用程序及实用工具。

命令行接口：在提示符之后用户从键盘上输入命令，命令解释程序接收并解释这些命令，然后把它们传递给操作系统内部的程序，执行相应的功能。

程序接口：也称系统调用接口。

是操作系统内核与用户程序、应用程序之间的接口。

5．操作系统主要有哪三种基本类型？各有什么特点？参考答案：主要有以下三种基本类型：多道批处理系统、分时系统和实时系统。

多道批处理系统的特点是多道和成批。

分时系统的特点是同时性、交互性、独立性和及时性。

实时系统一般为具有特殊用途的专用系统，其特点是交互能力较弱、响应时间更严格、对可靠性要求更高。

6．使用虚拟机，有什么优势和不足？参考答案：采用虚拟机的优点主要有：在一台机器上可同时运行多个操作系统，方便用户使用。

利用二进制位来表示磁盘中盘块空闲情况的方法(一)利用二进制位表示磁盘中盘块空闲情况引言在计算机系统中，磁盘是一种重要的存储介质。

为了管理磁盘上不同的盘块，我们需要记录盘块的空闲情况。

一种常见的方法是利用二进制位来表示盘块的空闲情况。

本文将详细介绍几种常见的方法。

方法一：位图法位图法是一种使用位图来记录盘块的空闲情况的方法。

位图由多个字节组成，每个字节表示一个盘块的状态，其中每个比特位表示该盘块是否空闲。

比如，0表示空闲，1表示已被占用。

利用位图法来表示磁盘中盘块的空闲情况，可以使用以下步骤：1. 初始化位图，将所有的比特位置为0，表示所有盘块均为空闲。

2. 当一个盘块被占用时，将对应的比特位置为1。

3. 当需要查找空闲盘块时，遍历位图找到第一个为0的比特位所对应的盘块。

优点： - 简单、直观，易于实现和理解。

- 占用的存储空间相对较小。

缺点： - 当磁盘较大时，位图占用的存储空间会较大。

- 查找空闲盘块的效率较低，需要逐一遍历位图。

方法二：位示图法位示图法是位图法的改进版，通过使用更小的单位来记录盘块的空闲情况。

比如，一个字节可以表示8个盘块的状态，一个位可以表示一个盘块的状态。

利用位示图法来表示磁盘中盘块的空闲情况，可以使用以下步骤：1. 初始化位示图，将所有的位置为0，表示所有盘块均为空闲。

2.当一个盘块被占用时，将对应的位置为1。

3. 当需要查找空闲盘块时，首先找到一个字节中值为0的位，然后根据位的位置计算出对应的盘块。

优点： - 存储空间占用更小，比位图法更节约空间。

- 查找空闲盘块的效率较高，因为一次可以处理多个盘块。

缺点： - 实现相对复杂，需要进行位操作。

- 当磁盘较大时，位示图占用的存储空间仍然会较大。

方法三：链表法链表法是一种使用链表来记录盘块的空闲情况的方法。

每个链表节点表示一个盘块，将空闲的盘块通过链表链接起来，已被占用的盘块不在链表中。

利用链表法来表示磁盘中盘块的空闲情况，可以使用以下步骤：1. 初始化链表，将所有盘块都加入链表中。

1. 操作系统结构设计应追求的目标是什么？正确性、高效性、维护性、移植性。

2. 在磁盘存储空间管理的位示图法中，确定已知空闲块地址的块号、柱面号的通用公式为：块号=字号×字长+位号柱面号=\[块号/柱面上的块数\]请写出确定空闲块地址的磁头号和扇区号的通用公式。

答案：磁头号=\[（块号mod柱面上的块数）/盘面上的扇区数\]扇区号=（块号mod柱面上的块数）mod盘面上的扇区数3. UNIX系统调用close是如何处理的？清除有关的表项。

检查块设备的缓冲区是否还有信息未写回，若有，则写回设备。

检查是否有其他进程仍打开此设备，若有，则不能关闭此设备。

若无其他进程打开此设备，调用驱动程序中的关闭过程，与设备断开。

4. 什么是线程？简述进程与线程的关系。

线程是进程中可独立执行的子任务。

一个进程中可以有一个或多个线程。

一个进程中的各个线程可以并发执行。

系统为进程分配主存空间，同一进程中的各线程共享该进程的主存空间。

5. 操作系统采用层次结构设计方法有什么优点和难点？主要优点是有利于系统的设计与调试，主要困难在于层次的划分和安排。

6. 目录结构有一级、二级和树形目录结构。

请简单叙述树形目录结构的优点。

解决了重名问题；有利于文件分类；提高检索文件的速度；能进行存取权限的控制。

7. 简述UNIX中系统调用命令OPEN的处理过程。

(1)分配一个活动索引节点，引用计数i_count加1。

(2)在进程打开文件表和系统打开文件表中分配表项。

(3)调用设备驱动程序检查打开的合法性。

(4)初始化驱动程度的数据结构。

(5)建立进程和设备间的联系。

8. 比较进程同步和进程互斥的异同。

答案：同：两者都是对并发进程竞争共享资源的管理。

异：进程互斥——各进程竞争共享资源没有必然的逻辑顺序。

只要无进程在使用共享资源就允许任一进程去使用。

进程同步——对共享资源的使用有一定的逻辑顺序。

9. 某系统有同类资源m个，供n个进程共享，如果每个进程最多申请x(1≤x≤m)个资源，且各进程的最大需求量之和小于(m+n)个资源，证明该系统不会发生死锁。