毕业设计（论文）-操作系统文件管理算法研究.doc

操作系统文件管理算法研究 毕 业 设 计（论 文）题目： 操作系统文件管理算法研究（英文）： On the Research of the File Management Algorithm in Operating System院 别： 专 业： 姓 名： 学 号： 指导教师： 日 期： 操作系统文件管理算法研究摘要文件管理是操作系统中一项重要的功能。其重要性在于，在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。随着信息化进程，文件管理越来越受到企业的重视，但是企业在进行文件管理的过程中，经常会碰到以下的问题：海量文件存储，管理困难；查找缓慢，效率低下；文件版本管理混乱；文件安全缺乏保障；文件无法有效协作共享；知识管理举步维艰等。所以文件管理逐渐成为国内外业界研究的热点。文章通过对现在的主流的文件管理算法及数据结构进行研究，并编写程序模拟，论证了在各种不同的算法下，文件管理的优缺点，得出在各种不同情况下使用何种算法的来管理文件。关键词：文件管理；文件存储；文件管理算法On the Research of the File Management Algorithm in Operating SystemABSTRACTFile management is one of important function in the operating system. In the modern computer system. The user program and data, the operating systems program and data ,even more all kinds of output input device are the documents form. With the process of information, file management more and more get the attention of the enterprise. But in the process of file management, the following question often come in enterprise: mass file storage, management difficultly; search slow; file version management confusion; The lack of security files; File cannot effectively cooperation sharing; Knowledges management has struggled and so on. So the file management gradually become the research focus in the industry at home and abroad. According to the mainstream of document management algorithm and the structure of the data for study in nowadays, and write the program simulation, demonstrates in various algorithm, the advantages and disadvantages of file management. In all sorts of different that use what algorithm to management files.Key words: file management; filestore; file management algorithm目录第1章 绪 论11.1操作系统文件管理概述11.1.1操作系统的定义11.1.2操作系统文件管理概述21.2操作系统文件管理的意义2第2章 文件管理42.1 文件与文件系统42.1.1 文件的定义42.1.2 文件系统概念42.1.3 文件系统的功能52.1.4 文件的分类52.2 文件的逻辑结构与存取方式52.3 文件的物理结构与存储介质62.3.1 文件的物理结构62.4 文件目录102.4.1 文件目录组成102.4.2 文件目录结构112.5 文件系统的实现122.5.1 文件记录块132.5.2 磁盘空间的管理13第3章 编程环境介绍183.1 Vmware183.1.1 构建虚拟机183.1.2 安装Linux操作系统193.1.3 安装VMware Tool203.2 VI（VIM）编辑器203.3 GCC编译器213.3.1 GCC基本规则213.3.2 GCC基本用法213.4 GDB调试工具22第四章 文件管理算法研究与模拟244.1 位示图算法研究244.2 位示图模拟274.3 UNIX系统文件管理成组连接算法284.4 成组链接程序模拟29参考文献32致谢33附录34第1章 绪 论在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。可以说，尽管文件有多种存储介质可以使用，如硬盘、软盘，光盘，闪存，记忆棒等等，但是，它们都以文件的形式出现在操作系统的管理者和用户面前。所以，文件管理是操作系统中的一项重要的功能。1.1 操作系统文件管理概述1.1.1 操作系统的定义 操作系统的功能包括管理计算机系统的硬件、软件及数据资源；控制程序运行；改善人机界面；为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。 许多操作系统制造者对OS的定义也不大一致，例如有些OS集成了图形用户界面，而有些OS仅使用文本接口，而将图形界面视为一种非必要的应用程序。 操作系统理论在计算机科学中为历史悠久而又活跃的分支，而操作系统的设计与实现则是软件工业的基础与内核。 操作系统的主要功能是资源管理，程序控制和人机交互等。计算机系统的资源可分为设备资源和信息资源两大类。设备资源指的是组成计算机的硬件设备，如中央处理器，主存储器，磁盘存储器，打印机，磁带存储器，显示器，键盘输入设备和鼠标等。信息资源指的是存放于计算机内的各种数据，如文件，程序库，知识库，系统软件和应用软件等。 操作系统位于底层硬件与用户之间，是两者沟通的桥梁。用户可以通过操作系统的用户界面，输入命令。操作系统则对命令进行解释，驱动硬件设备，实现用户要求。以现代观点而言，一个标准个人电脑的OS应该提供以下的功能： 进程管理（Processing management） 39记忆空间管理（Memory management） 文件系统（File system） 网络通讯（Networking） 安全机制（Security） 使用者界面（User interface） 驱动程序（Device drivers）1.1.2 操作系统文件管理概述文件管理是操作系统的五大职能之一，主要涉及文件的逻辑组织和物理组织，目录的结构和管理。所谓文件管理，就是操作系统中实现文件统一管理的一组软件、被管理的文件以及为实施文件管理所需要的一些数据结构的总称（是操作系统中负责存取和管理文件信息的机构）从系统角度来看，文件系统是对文件存储器的存储空间进行组织，分配和回收，负责文件的存储，检索，共享和保护。从用户角度来看，文件系统主要是实现按名取存，文件系统的用户只要知道所需文件的文件名，就可存取文件中的信息，而无需知道这些文件究竟存放在什么地方。其功能在于：统一管理文件存储空间(即外存)，实施存储空间的分配与回收。 确定文件信息的存放位置及存放形式。 实现文件从名字空间到外存地址空间的映射，即实现文件的按名存取。 有效实现对文件的各种控制操作(如建立、撤销、打开、关闭文件等)和存取操作(如读、写、修改、复制、转储等) 实现文件的高速存取 1.2 操作系统文件管理的意义文件管理是操作系统中一项重要的功能。其重要性在于，在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。可以说，尽管文件有多种存储介质可以使用，如硬盘、软盘，光盘，闪存，记忆棒等等，但是，它们都以文件的形式出现在操作系统的管理者和用户面前。随着信息化进程，文件管理越来越受到企业的重视，但是企业在进行文件管理的过程中，经常会碰到以下的问题：海量文件存储，管理困难；查找缓慢，效率低下；文件版本管理混乱；文件安全缺乏保障；文件无法有效协作共享；知识管理举步维艰等。所以文件管理逐渐成为国内外业界研究的热点。第2章 文件管理在计算机系统中，信息的组织、存取、加工和保管等工作主要是由文件系统来完成的。文件系统是操作系统中一个重要的组成部分。而且，对大多数用户来说，除了人机界面之外，文件系统是用户经常访问，直接处理的一个部分。2.1 文件与文件系统研究文件系统有两种不同的观点，一种是用户的观点，另一种是操作系统的观点。从用户的观点看文件系统，主要是关心文件由什么组成，如何命名，如何保护文件，可以进行何种操作等等。从操作系统的观点看文件系统，主要关心文件目录是怎样实现的，怎么样管理存储空间，文件存储位置，磁盘实际动作方式等问题。2.1.1 文件的定义文件是一组带标识的、在逻辑上有完整意义的信息项的序列。这个标识符为文件名，信息项构成了文件内容的基本单位。一般地，文件建立在存储器空间里，以便使文件能够长期保存。文件是一个抽象机制，它提供了一种把信息保存在存储介质上，而且便于以后存取的方法，用户不必关心文件实现的细节。2.1.2 文件系统概念所谓文件系统，是操作系统中统一管理信息资源的一种软件。它管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。从用户的角度来看，文件系统负责为用户建立文件、读写文件、修改文件、复制文件和撤消文件。文件系统还负责完成对文件的按名存取和对文件进行存取控制。2.1.3 文件系统的功能作为一个统一的文件管理机构，文件系统具有下述功能：（1）统一管理文件的存储空间，实施存储空间的分配与回收。（2）实现文件从名字空间到外存地址空间的映射，即实现文件的按名存取，以对用户透明的方式管理名字空间。（3）实现文件信息的共享，并提供文件的保护和保密措施。（4）向用户提供一个方便使用的接口。（5）系统维护及向用户提供有关信息。（6）保持文件系统的执行效率。（7）提供与I/O的统一接口。2.1.4 文件的分类（1）根据文件的性质和用途：系统文件、用户文件、库文件。（2）根据文件中数据的形式：源文件、目标文件、可执行文件。（3）根据存取控制属性：只执行文件、只读文件、读写文件。（4）根据组织形式和处理方式：普通文件、目录文件、特殊文件。2.2 文件的逻辑结构与存取方式文件的逻辑结构就是用户所看到的文件的组织形式。文件逻辑结构是一种经过抽象的结构，所描述的是记录在文件中信息的组织形式工。文件中的这些信息到底在物理介质上是如何组织存储的，与用户没有直接关系。图2.1 文件的逻辑结构从用户角度看，按文件的逻辑结构可以把文件划分成三类：无结构的字符流式文件、定长记录文件和不定长记录文件构成的记录树，如图2.1所示：一个字节一个记录字符流式文件定长记录文件不定长记录文件构成的记录树图 2.1用户通过对文件的存取来完成对文件的各种操作，文件的存取方式是由文件的性质和用户使用文件的情况而确定的。常用的存取方法有：顺序存取、随机存取和按键存取等三种方式。2.3 文件的物理结构与存储介质2.3.1 文件的物理结构 常用的文件物理结构有顺序结构、链表结构、索引结构和I节点结构。1、顺序结构文件信息存放在若干连续的物理块中。如下图中，文件count从编号为0的物理块开始存储，占用两个连续的物理块；文件mail从编号为19的物理块开始存储，占用6个连续的物理块。图2.2 文件的顺序结构l 顺序结构的优点：1、简单：存储与管理都简单，且容易实现。2、支持顺序存取和随机存取。3、顺序存取速度快。4、所需的磁盘寻道次数和寻道时间最少。l 顺序结构的缺点：1、需要为每个文件预留若干物理块以满足文件增长的部分需要。2、 不利于文件插入和删除。2、链表结构 文件信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。下图说明文件jeep存储时所占用的物理块。图2.3 文件的链表结构l 优点1、提高了磁盘空间利用率，不需要为每个文件预留物理块。2、有利于文件插入和删除。3、有利于文件动态扩充。l 缺点1、存取速度慢，不适于随机存取。2、当物理块间的连接指针出错时，数据丢失。3、更多的寻道次数和寻道时间。4、链接指针占用一定的空间，降低了空间利用率。3、索引结构文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构，称为索引表，并将存放文件信息的物理块的块号存放在索引表中。索引表是磁盘块地址数组,其中第i个条目指向文件的第i块。如下图所示：图2.4 文件的索引结构l 优点1、不需要为每个文件预留物理块。2、既能顺序存取，又能随机存取。3、满足了文件动态增长、插入删除的要求。l 缺点1、较多的寻道次数和寻道时间。2、索引表本身带来了系统开销。如：内外存空间，存取时间等。4、多级索引结构UNIX的I节点UNIX文件系统采用的是多级索引结构（综合模式）。每个文件的索引表为13个索引项，每项2个字节。最前面10项直接存放文件信息的物理块号（直接寻址）。如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址。UNIX中采用三级索引结构后，文件最大可达16兆个物理块。如下图所示：图2.5 I节点结构2.4 文件目录在一个计算机系统中保存有许多文件，用户在创建和使用文件时只给出文件的名字，由文件系统根据文件名找到指定文件。为了便于对文件进行管理，设置了文件目录，用于检索系统中的所有文件。2.4.1 文件目录组成文件系统的一个最大的特点是“按名存取”，用户只要给出文件的符号名就能方便地存取在外存空间的文件信息，而不必关心文件的具体物理地址。而实现文件符号到文件物理地址映射的主要环节是检索文件目录。系统为每个文件设置一个描述性数据结构文件控制块FCB，文件目录就是文件控制块的有序集合，即把所有文件控制块有机地组织起来，就构成了文件目录。（1）文件控制块FCB结构FCB是系统为管理文件而设置的一个数据结构。FCB是文件存在的标志，它记录了系统管理文件所需要的全部信息。FCB通常应包括以下内容：文件名，文件号，用户名，文件地址，文件长度，文件类型，文件属性，共享计数，文件的建立日期，保存期限，最后修改日期，最后访问日期，口令，文件逻辑结构，文件物理结构等。（2）目录文件为了实现对文件目录的管理，通常将文件目录以文件的形式长期保存在外存空间，这个文件就被称为目录文件。通常，目录文件是长度固定的记录式文件。2.4.2 文件目录结构文件目录结构分为一级目录结构，二级目录结构和多级目录结构。文件名文件说明 物理地址ABCFCB1FCB2FCB3ABC图2.6 一级目录结构主目录图2.7 二级目录结构表示目录表示普通文件根目录图2.8 多级目录结构2.5 文件系统的实现前面讨论的文件系统，主要是从用户的角度探讨问题。这里是将从实现的角度讨论文件系统如何实现，也就是文件系统的内在物理结构。文件的使用者关心文件是如何命名、可以进行哪些文件操作。文件目录是如何组织的、如何检索或查找文件目录等问题。而设计和实现者感兴趣的是，在磁盘上怎样安排文件和目录存储，如何管理磁盘空间以及怎样使文件系统有效而可靠地工作等。文件系统实现的关键是，找到一种符合设计要求的方法，把文件记录到磁盘块上去。所谓文件的物理结构，是从系统的角度来看文件，从文件在物理介质上的存放方式来研究文件。2.5.1 文件记录块 文件的存储设备常常划分为若干大小相等的物理块。同时也将文件信息划分成逻辑块，所有块统一编号。以块为单位进行信息的存储、传输和分配。从用户的角度来看文件，是把每一个文件看作是一个整体的，不考虑文件实际在磁盘上的存放方法。事实上，文件有大有小，磁盘的存储空间也有大小，另外，文件传输时也必须分块。这样，在文件系统中，是以块作为分配和传送信息的基本单位。显然，对于字符流的无结构文件来说，每一个物理块中存放长度相等的文件信息。不过，对于记录式文件来说，由于记录长度可以是固定的，也可以是可变的，而且其长度不一定刚好等于其物理块的长度，从而有可能给由记录的逻辑地址到物理地址的变换带来了额外的负担。2.5.2 磁盘空间的管理一个存储设备上的空闲空间登记表（FSL）动态跟踪记录该存储设备上所有空闲块的数目和块号。该数据结构虽称为表，但不一定以二维表形式实现。为方便高效安全起见，一般把FSL放在存储实体上。由于设备空间是有限的，故不再使用的空间必须回收以重用，然后在建立文件等操作中重新动态分配。可见在文件删除、文件建立、写文件等操作中都会访问与修改空闲空间表。在实际系统中四种不同的方案，分别为位示图、空闲块表、空闲块链表、成组链表。1、 位示图位示图法的基本思想是利用一串二进制的值来反映磁盘空间的分配使用情况。每一个磁盘物理块对应一个二进制位，如果物理块为空闲，则相应的二进制位为0；如果物理块已分配，则相应的二进位为1，如图所示：图 2.9 位示图 申请磁盘物理块时，可在位示图中从头查找为0的字位，将其改为1，返回对应的物理块号；归还物理块时，在位示图中将该块所对应的字位改为0。磁盘空闲空间登记数据结构在大部分情况下以位示图实现。位示图描述能力强，一个二进位就描述一个物理块的状态，因而位示图较小，可以复制到内存，使查找既方便又快速。位示图适用于各种文件物理结构的文件系统。位示图的主要优点是能够简单有效地盘上找到n个连续空闲块。的确，很多计算机提供了位操作指令，使位示图查找能够高效进行。例如，Intel x86微处理器系列就有这样的指令：返回指定寄存器的所有位中值为1的第一位。Linux的文件系统Ext2就是采用位示图来描述数据块和索引节点的使用情况的。2、空闲块表文件系统建立一张空闲块表，该表记录了全部空闲的物理块：包括首空闲块号和空闲块个数。空闲块表方式特别适合于文件物理结构为顺序结构的文件系统。建立新文件时，系统查找空闲块表，寻找合适的表项，分配一组连续的空闲块。如果对应表项所拥有空闲块个数恰好等于所申请值，就将该表项从空闲块表中删去。当删除文件时，系统收回它所占用的物理块，考虑是否可以与原有空闲块相邻接，合并成更大的空闲区域，最后修改有关表项。序号空闲块个数首空闲块号01210a89002899a0812482568图 2.10 空闲块表3、空闲块链表系统将所有的空闲物理块连成一个链，用一个空闲块首指针指向第一个空闲块，然后每个空闲块含有指向下一个空闲块的指针，最后一块的指针为空，表示链尾。空闲块首指针空闲块12空闲块13空闲块14图 2.11 空闲块链接表在图2.11中，空闲块首指针维持一个指向盘块12的指针，该块是第一个空闲盘块。盘块12包含一个指向盘块13的指针，盘块13指向盘块14等等。这种模式效率低，要遍历整张表，必须读第一个块，需要大量I/O时间。外存空间的申请和释放以块为单位，申请时从链首取一块，释放时将其链入链尾，空闲块链表节省内存，但申请释放速度较慢，实现效率较低。4、成组链接对链接表的改进就是将空闲盘块分成若干组，每一组空闲盘块的地址存放在另一空闲盘块组的第一个空闲块中，该组中其余n-1个空闲盘块是实际空闲的。假设每100个空闲块为一组。通常第一组可能不足100块，第一组空闲盘块的地址通常放在一个专用块中，专用块的第1个单元给出下一组空闲盘块的个数，第2个单元以后存放下一组空闲盘块的地址；第二组有100个空闲盘块，其地址放在第一组中的第一个空闲盘块中，该块的第1个单元给出第一组空闲盘块的个数，第2个以后存放第二组空闲盘块的地址；依次类推，组与组之间形成链接关系。最后一组有99个空闲盘块，其地址放在前一组中的第一个空闲盘块中，而该块中的第2个单元填“0”，表示该块中存放的是最后一组的块号，空闲块链到些结束，这种方式称为成组链接。系统在初始化时先把专用块内容读到内存中，当需分配空闲块时，就直接在内存中找到哪些块是空闲的，每分配一块后把空闲块数减1.但在把一组中的第一个空闲块分配出去之前，就把登记在该块中的下一组的块号及块数保存到专用块中。娄一组空闲块被分配完后，则再把专用块的内容读到内存中，指出另一组可供分配的空闲块。空块数20920空块数100空块数99600专用块920400图2.12 成组链接采用成组链接后，分配、回收空闲块时均在内存中查找和修改，只有在一组空闲块分配完或空闲的磁盘块构成一组时才需要启动磁盘读写。因些，成组链接的管理方式比普通链接方式效率高。 第3章 编程环境介绍3.1 VmwareVMWare (Virtual Machine ware)是一个“虚拟PC”软件公司.它的产品可以使你在一台机器上同时运行二个或更多Windows、DOS、LINUX系统。与“多启动”系统相比，VMWare采用了完全不同的概念。多启动系统在一个时刻只能运行一个系统，在系统切换时需要重新启动机器。VMWare是真正“同时”运行，多个操作系统在主系统的平台上，就象标准Windows应用程序那样切换。而且每个操作系统你都可以进行虚拟的分区、配置而不影响真实硬盘的数据，你甚至可以通过网卡将几台虚拟机用网卡连接为一个局域网，极其方便。安装在VMware操作系统性能上比直接安装在硬盘上的系统低不少，因此，比较适合学习和测试。3.1.1 构建虚拟机1.运行VMware Workstation 6，单击“FileNewVirtual Machine”命令，进入创建虚拟机向导。2.在弹出的欢迎页中单击“下一步”按钮。 3.在“Virtual machine configuration”选项区域内选择“Custom”单选按钮。 4.在Choose the Virtual Machine Hardware Compatibility页中，选择虚拟机的硬件格式，可以在Hardware compatibility下拉列表框中，在VMware Workstation 6、VMware Workstation 5或VMware Workstation 4三者之间进行选择。通常情况下选择Workstation 6的格式，因为新的虚拟机硬件格式支持更多的功能，选择好后单击“下一步”按钮。 5.在Select a Guest Operating System对话框中，选择要创建虚拟机类型及要运行的操作系统，这里选择Windows 2000 Professional操作系统，单击“下一步”按钮。 6.在Name the Virtual Machine对话框中，为新建的虚拟机命名并且选择它的保存路径。 7.在Processors选项区域中选择虚拟机中CPU的数量，如果选择Two，主机需要有两个CPU或者是超线程的CPU。 8.在Memory for the Virtual Machine页中，设置虚拟机使用的内存，通常情况下，对于Windows 98及其以下的系统，可以设置64MB；对于Windows 2000/XP，最少可以设置96MB；对于Windows 2003，最低为128MB；对于Windows Vista虚拟机，最低512MB。 9.在Network Type页中选择虚拟机网卡的“联网类型” 选择第一项，使用桥接网卡(VMnet0虚拟网卡)，表示当前虚拟机与主机(指运行VMware Workstation软件的计算机)在同一个网络中。 选择第二项，使用NAT网卡(VMnet8虚拟网卡)，表示虚拟机通过主机单向访问主机及主机之外的网络，主机之外的网络中的计算机，不能访问该虚拟机。 选择第三项，只使用本地网络(VMnet1虚拟网卡)，表示虚拟机只能访问主机及所有使用VMnet1虚拟网卡的虚拟机。主机之外的网络中的计算机不能访问该虚拟机，也不能被该虚拟机所访问。 选择第四项，没有网络连接，表明该虚拟机与主机没有网络连接。 10.在Select I/O Adapter Type页中，选择虚拟机的SCSI卡的型号，通常选择默认值即可。 11.在Select a Disk页中，选择Create a new virtual disk(创建一个新的虚拟硬盘)。 12.在Select a Disk Type页中，选择创建的虚拟硬盘的接口方式，通常选择默认值即可。 13.在Specify Disk Capacity页中设置虚拟磁盘大小，对于一般的使用来说，选择默认值即可。 14.在Specify Disk File页的Disk file选项区域内设置虚拟磁盘文件名称，通常选择默认值即可，然后单击完成按钮。3.1.2 安装Linux操作系统在虚拟机中安装操作系统，和在 VMware真实的计算机中安装没有什么区别，但在虚拟机中安装操作系统，可以直接使用保存在主机上的安装光盘镜像(或者软盘镜像)作为虚拟机的光驱(或者软驱)。 可以用打开前文创建的Windows 2000虚拟机配置文件，在Virtual Machine Settings页中的Hardware选项卡中，选择CD-ROM项，在Connection选项区域内选中Use ISO image单选按钮，然后浏览选择Windows XP安装光盘镜像文件Red hat Enterprise Linux AS v5.4-i386-dvd.ISO。如果使用安装光盘，则选择Use physical drive并选择安装光盘所在光驱。 选择光驱完成后，然后单击工具栏上的播放按钮，打开虚拟机的电源，用鼠标在虚拟机工作窗口中单击一下，进入虚拟机。 以后在虚拟机中安装操作系统，就和在主机中安装一样了。3.1.3 安装VMware Tool在虚拟机中安装完操作系统之后，接下来需要安装VMware Tools。VMware Tools相当于VMware虚拟机的主板芯片组驱动和显卡驱动、鼠标驱动，在安装VMware Tools后，可以极大提高虚拟机的性能，并且可以让虚拟机分辨率以任意大小进行设置，还可以使用鼠标直接从虚拟机窗口中切换到主机中，不需要Ctrl+Alt。 VMware Tools的安装很简单： 1.从VM菜单下选择安装VMware Tools。 2.按照提示安装，最后重新启动虚拟机即可。3.2 VI（VIM）编辑器 VI 编辑器是Visual interface的简称，通常称之为VI。它在Linux上的地位就像Edit程序在DOS上一样。它可以执行输出、删除、查找、替换、块操作等众多文本操作，而且用户可以根据自己的需要对其进行定制，这是其他编辑程序所没有的。 VI 编辑器并不是一个排版程序，它不像Word或WPS那样可以对字体、格式、段落等其他属性进行编排，它只是一个文本编辑程序。没有菜单，只有命令，且命令繁多。Vi有3种基本工作模式：命令行模式、文本输入模式和末行模式。 VIM是VI的加强版，比vi更容易使用。vi的命令几乎全部都可以在vim上使用。3.3 GCC编译器GCC（GNU Compiler Collection，GNU编译器套装），是一套由 GNU 开发的编程语言编译器。它是一套 GNU编译器套装以 GPL 及 LGPL 许可证所发行的自由软件，也是 GNU计划的关键部分，亦是自由的类Unix及苹果电脑 Mac OS X 操作系统的标准编译器。 GCC 原名为 GNU C 语言编译器，因为它原本只能处理 C语言。GCC 很快地扩展，变得可处理 C+。之后也变得可处理 Fortran、Pascal、Objective-C、Java, 以及 Ada与其他语言。3.3.1 GCC基本规则gcc所遵循的部分约定规则： .c为后缀的文件，C语言源代码文件； .a为后缀的文件，是由目标文件构成的档案库文件； .C，.cc或.cxx 为后缀的文件，是C+源代码文件； .h为后缀的文件，是程序所包含的头文件； .i 为后缀的文件，是已经预处理过的C源代码文件； .ii为后缀的文件，是已经预处理过的C+源代码文件； .m为后缀的文件，是Objective-C源代码文件； .o为后缀的文件，是编译后的目标文件； 3.3.2 GCC基本用法在使用Gcc编译器的时候，我们必须给出一系列必要的调用参数和文件名称。GCC编译器的调用参数大约有100多个，其中多数参数我们可能根本就用不到，这里只介绍其中最基本、最常用的参数。 GCC最基本的用法是gcc options filenames 其中options就是编译器所需要的参数，filenames给出相关的文件名称。 -c，只编译，不连接成为可执行文件，编译器只是由输入的.c等源代码文件生成.o为后缀的目标文件，通常用于编译不包含主程序的子程序文件。 -o output_filename，确定输出文件的名称为output_filename，同时这个名称不能和源文件同名。如果不给出这个选项，gcc就给出预设的可执行文件a.out。 -g，产生符号调试工具(GNU的gdb)所必要的符号资讯，要想对源代码进行调试，我们就必须加入这个选项。 -O，对程序进行优化编译、连接，采用这个选项，整个源代码会在编译、连接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是，编译、连接的速度就相应地要慢一些。 -O2，比-O更好的优化编译、连接，当然整个编译、连接过程会更慢。 -Idirname，将dirname所指出的目录加入到程序头文件目录列表中，是在预编译过程中使用的参数。C程序中的头文件包含两种情况 A)#include B)#include “myinc.h” 其中，A类使用尖括号()，B类使用双引号(“ ”)。对于A类，预处理程序cpp在系统预设包含文件目录(如/usr/include)中搜寻相应的文件，而B类，预处理程序在目标文件的文件夹内搜索相应文件。3.4 GDB调试工具GDB是GNU开源组织发布的一个强大的UNIX下的程序调试工具。一般来说，GDB主要帮助你完成下面四个方面的功能： 1、启动你的程序，可以按照你的自定义的要求随心所欲的运行程序。 2、可让被调试的程序在你所指定的调置的断点处停住。（断点可以是条件表达式） 3、当程序被停住时，可以检查此时你的程序中所发生的事。 4、动态的改变你程序的执行环境。第四章 文件管理算法研究与模拟文件系统对于设计和实现者来说，他们感兴趣的是，在磁盘上怎么样安排文件和目录存储，如何管理磁盘空间以及怎样使文件系统文件目录等问题。磁盘格式化时，系统把磁盘存储空间分成许多磁道。每个磁道又分成若干个扇区（又叫做磁盘块）。之后用fdisk命令对硬盘进行分区，即使只有一个分区，也必须用fdisk命令进行分区。分区的目的，就是制作文件卷，形成文件系统。一个文件卷一般都被划分成引导扇区、文件系统管理区和文件数据区。其中，文件数据区用来存放系统文件和用户文件。用户可以通过文件系统提供的API，创建、打开、关闭和对文件进行读写。当用户的文件不再需要时，就应该删除。把一个文件放到磁盘上时，可以组织成连续文件、链接文件或索引文件等。因此，磁盘空间的分配方法也有两种，一种是连续空间的分配，一种是不连续空间的分配（又叫动态分配）。本章将研究磁盘空间的管理，目前大多操作系统用的方案是位示图，空闲块成组链表。4.1 位示图算法研究假定现有一个磁盘组，共有40个柱面。每个柱面4个磁道，每个磁道又划分成4个物理记录。磁盘的空间使用情况用位示图表示。位示图用若干个字构成，每一位对应一个磁盘道。“1”表示占用，“0”表示空闲。为了简单，假定字长为16位，一个字可用来模拟磁盘的一个柱面，其位示图如图4.1所示。系统设置一个变量S记录当前的空闲磁盘块个数。位示图的初始状态由户自己设定。图4.1申请一个磁盘块时，由磁盘块分配程序查位示图，找出一个为0的位，并计算磁盘的物理地址（即求出它的柱面号、磁道号和扇区号）。由位示图计算磁盘的相对块号的公式如下： 相对块号=字号*16+位号再将相对块号转换成磁盘的物理地址： 柱面号=(相对块号/16)的商，也即柱面号=字号 磁道号=（相对块号/16的余数）/4）的商，也即（位号/4）的商 物理块号=（相对块号/16）的余数）/4）的余数，也即（位号/4）的余数当释放一个相对物理块时，运行回收程序，计算该块在位示图中的位置，再把相应由“1”改为“0”。计算公式如下： 先由磁盘的三维地址柱面号、磁道号和扇区号计算相对块号： 相对块号=柱面号*16+磁道号*4+物理块号 再计算字号和位号： 字号=相对块号/16的商，也即字号=柱面号 位号=磁道号*（物理块数/每磁道）+物理块号分配算法和回收算法流程分别如图4.2和4.3所示。图4.2 磁盘空间分配的流程图4.2 磁盘空间回收的流程4.2 位示图模拟 程序用一个8*8的二维数组做为管理磁盘分配的位示图，1代表该磁盘块已分配，0代表未分配，详细程序见附录。程序模拟的结果图如下 ：图4.3 磁盘的分配图 4.4 磁盘的回收4.3 UNIX系统文件管理成组连接算法UNIX系统把每100个空闲块作为一组，每一组的第一个空闲块中登记下一组空闲块的块号和空闲块数，余下不足100块的那部分空闲块的块号及块数登记在一个专用块中，登记最后一组块号的那个空闲块，其中第2个单元填“0”，表示该块中指出的块号是最后一组的块号，空闲块链到此结束。系统初始化时先把专用块内容读到内存，当需分配空闲块时，就直接在内存中可找到哪些块。 但要把一组中的第一个空闲块分配出去之前应把登记在该块中的下一组的块号及块数保存到专用块中。 当一组空闲块被分配完后，则再把专用块的内容读到内存，指出另一组可供分配的空闲块。当归还一块时，只要把归还块的块号登记到当前组中且空闲块数加1。如果当前组已满100块，则把内存中的内容写到归还的那块中，该归还块作为新组的第一块。假设初始化时系统已把专用块读入内存L单元开始的区域中，分配和回收的算法如下： 1、分配一个空闲块 查L单元内容（空闲块数）： 当空闲块数1, i :L空闲块数； 从i单元得到一空闲块号； 把该块分配给申请者； 空闲块数减1。 当空闲块数1 取出L1单元内容（一组的第一块块号或0）； 其值0无空闲块，申请者等待 不等于零把该块内容复制到专用块,该块分配给申请者； 把专用块内容读到主存L开始的区域。 2、归还一块 查L单元的空闲块数； 当空闲块数100 空闲块数加1； j :L空闲块数； 归还块号填入j单元。 当空闲块数100 把主存中登记的信息写入归还块中； 把归还块号填入L1单元； 将L单元置成1。 采用成组连接后，分配回收磁盘块时均在内存中查找和修改，只是在一组空闲块分配完或空闲的磁盘块构成一组时才启动磁盘读写。比单块连接方式效率高。4.4 成组链接程序模拟首先定义磁盘分配数组并初始化，9个一维数组分别表示9个空闲块，程序运行时，先将专用块A0复制到内存中，然后进行功能选择，分配时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。 回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。显示分组情况。系统初始化时先将专用块内容读入 内存 ，当有申请空闲块要求时，就直接在内存专用块中找到哪些块是空闲的，每分配一块后把空闲块数减 1。但要把一组中第一块分配出去之前，可以先把登记在该块中的下一组的块号保存在专用块中(此时 ，原专用块中的信息巳经无用了 ，因它指示的一组空闲块都已分配掉)。当中文组空闲块分配完后,则将下一组内容读入内存专用块中，以便继续分配时查找。程序模拟图如下：图4.5 磁盘块的分配图 4.6 磁盘的回收参考文献1汤小丹计算机操作系统M.西安：西安电子科技大学出版社，2007.05.2西尔伯沙实用操作系统概念M.北京：高等教育出版社，2001.3陈向群. 操作系统教程M.北京：北京大学出版社. 2006.6.4张尧学.计算机操作系统教程M.北京：清华大学出版社.2000.8.5凤羽.操作系统M.北京:电子工业出版社,20046马季兰.操作系统原理与LinuxM. 北京:人民邮电出版社,20007孟静.操作系统原理教程M.北京:清华大学出版社,20008周苏.操作系统原理实验M.北京: 科学出版社,20009汤子瀛.计算机操作系统M.西安：西安电子科技大学出版社,200110A.S.Tanenbaum.现代操作系统M.北京：机械工业出版社，2002致谢非常感谢老师在我大学的最后学习阶段毕业设计阶段给自己的指导，从最初的定题，到资料收集，到写作、修改，到论文定稿，他给了我耐心的指导和无私的帮助。为了指导我们的毕业论文，他放弃了自己的休息时间，他的这种无私奉献的敬业精神令人钦佩，在此我向他表示我诚挚