搜索
操作系统论文题目：文件管理算法研究专业：10计科一班姓名：韩家君学号：1010311110指导教师：柯老师日期：2012、12、232操作系统文件管理算法研究摘要文件管理是操作系统中一项重要的功能。其重要性在于，在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。随着信息化进程，文件管理越来越受到企业的重视，但是企业在进行文件管理的过程中，经常会碰到以下的问题：海量文件存储，管理困难；查找缓慢，效率低下；文件版本管理混乱；文件安全缺乏保障；文件无法有效协作共享；知识管理举步维艰等。所以文件管理逐渐成为国内外业界研究的热点。文章通过对现在的主流的文件管理算法及数据结构进行研究，并编写程序模拟，论证了在各种不同的算法下，文件管理的优缺点，得出在各种不同情况下使用何种算法的来管理文件。关键词：文件管理；文件存储；文件管理算法绪论在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。可以说，尽管文件有多种存储介质可以使用，如硬盘、软盘，光盘，闪存，记忆棒等等，但是，它们都以文件的形式出现在操作系统的管理者和用户面前。所以，文件管理是操作系统中的一项重要的功能。操作系统文件管理概述1操作系统的定义：操作系统的功能包括管理计算机系统的硬件、软件及数据资源；控制程序运行；改善人机界面；为其它应用软件提供支持等，使计算机系统所操作系统文件管理算法研究3有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。许多操作系统制造者对OS的定义也不大一致，例如有些OS集成了图形用户界面，而有些OS仅使用文本接口，而将图形界面视为一种非必要的应用程序。操作系统理论在计算机科学中为历史悠久而又活跃的分支，而操作系统的设计与实现则是软件工业的基础与内核。操作系统的主要功能是资源管理，程序控制和人机交互等。计算机系统的资源可分为设备资源和信息资源两大类。设备资源指的是组成计算机的硬件设备，如中央处理器，主存储器，磁盘存储器，打印机，磁带存储器，显示器，键盘输入设备和鼠标等。信息资源指的是存放于计算机内的各种数据，如文件，程序库，知识库，系统软件和应用软件等。操作系统位于底层硬件与用户之间，是两者沟通的桥梁。用户可以通过操作系统的用户界面，输入命令。操作系统则对命令进行解释，驱动硬件设备，实现用户要求。以现代观点而言，一个标准个人电脑的OS应该提供以下的功能：进程管理（Processingmanagement）记忆空间管理（Memorymanagement）文件系统（Filesystem）网络通讯（Networking）安全机制（Security）使用者界面（Userinterface）驱动程序（Devicedrivers）2操作系统文件管理概述文件管理是操作系统的五大职能之一，主要涉及文件的逻辑组织和物理组织，目录的结构和管理。所谓文件管理，就是操作系统中实现文件统一管理的一组软件、被管理的文件以及为实施文件管理所需要的一些数据结构的总称（是操作系统中负责存取和管理文件信息的机构）从系统角度来看，文件系统是对文件存储器的存储空间进行组织，分配和回收，负责文件的存储，检索，共享和保护。4从用户角度来看，文件系统主要是实现按名取存，文件系统的用户只要知道所需文件的文件名，就可存取文件中的信息，而无需知道这些文件究竟存放在什么地方。其功能在于：①统一管理文件存储空间(即外存)，实施存储空间的分配与回收。②确定文件信息的存放位置及存放形式。③实现文件从名字空间到外存地址空间的映射，即实现文件的按名存取。④有效实现对文件的各种控制操作(如建立、撤销、打开、关闭文件等)和存取操作(如读、写、修改、复制、转储等)⑤实现文件的高速存取操作系统文件管理的意义文件管理是操作系统中一项重要的功能。其重要性在于，在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。可以说，尽管文件有多种存储介质可以使用，如硬盘、软盘，光盘，闪存，记忆棒等等，但是，它们都以文件的形式出现在操作系统的管理者和用户面前。随着信息化进程，文件管理越来越受到企业的重视，但是企业在进行文件管理的过程中，经常会碰到以下的问题：海量文件存储，管理困难；查找缓慢，效率低下；文件版本管理混乱；文件安全缺乏保障；文件无法有效协作共享；知识管理举步维艰等。所以文件管理逐渐成为国内外业界研究的热点。文件管理在计算机系统中，信息的组织、存取、加工和保管等工作主要是由文件系统来完成的。文件系统是操作系统中一个重要的组成部分。而且，对大多数用户来说，除了人机界面之外，文件系统是用户经常访问，直接处理的一个部分。1文件与文件系统操作系统文件管理算法研究5研究文件系统有两种不同的观点，一种是用户的观点，另一种是操作系统的观点。从用户的观点看文件系统，主要是关心文件由什么组成，如何命名，如何保护文件，可以进行何种操作等等。从操作系统的观点看文件系统，主要关心文件目录是怎样实现的，怎么样管理存储空间，文件存储位置，磁盘实际动作方式等问题。1.1文件的定义文件是一组带标识的、在逻辑上有完整意义的信息项的序列。这个标识符为文件名，信息项构成了文件内容的基本单位。一般地，文件建立在存储器空间里，以便使文件能够长期保存。文件是一个抽象机制，它提供了一种把信息保存在存储介质上，而且便于以后存取的方法，用户不必关心文件实现的细节。1.2文件系统概念所谓文件系统，是操作系统中统一管理信息资源的一种软件。它管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。从用户的角度来看，文件系统负责为用户建立文件、读写文件、修改文件、复制文件和撤消文件。文件系统还负责完成对文件的按名存取和对文件进行存取控制。1.3文件系统的功能作为一个统一的文件管理机构，文件系统具有下述功能：（1）统一管理文件的存储空间，实施存储空间的分配与回收。（2）实现文件从名字空间到外存地址空间的映射，即实现文件的按名存取，以对用户透明的方式管理名字空间。（3）实现文件信息的共享，并提供文件的保护和保密措施。（4）向用户提供一个方便使用的接口。（5）系统维护及向用户提供有关信息。（6）保持文件系统的执行效率。6（7）提供与I/O的统一接口。1.4文件的分类（1）根据文件的性质和用途：系统文件、用户文件、库文件。（2）根据文件中数据的形式：源文件、目标文件、可执行文件。（3）根据存取控制属性：只执行文件、只读文件、读写文件。（4）根据组织形式和处理方式：普通文件、目录文件、特殊文件。2文件的逻辑结构与存取方式文件的逻辑结构就是用户所看到的文件的组织形式。文件逻辑结构是一种经过抽象的结构，所描述的是记录在文件中信息的组织形式工。文件中的这些信息到底在物理介质上是如何组织存储的，与用户没有直接关系。从用户角度看，按文件的逻辑结构可以把文件划分成三类：无结构的字符流式文件、定长记录文件和不定长记录文件构成的记录树。用户通过对文件的存取来完成对文件的各种操作，文件的存取方式是由文件的性质和用户使用文件的情况而确定的。常用的存取方法有：顺序存取、随机存取和按键存取等三种方式。3文件的物理结构与存储介质文件的物理结构常用的文件物理结构有顺序结构、链表结构、索引结构和I节点结构。1、顺序结构文件信息存放在若干连续的物理块中。顺序结构的优点：1、简单：存储与管理都简单，且容易实现。2、支持顺序存取和随机存取。3、顺序存取速度快。4、所需的磁盘寻道次数和寻道时间最少。操作系统文件管理算法研究7顺序结构的缺点：1、需要为每个文件预留若干物理块以满足文件增长的部分需要。2、不利于文件插入和删除。2、链表结构文件信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。优点1、提高了磁盘空间利用率，不需要为每个文件预留物理块。2、有利于文件插入和删除。3、有利于文件动态扩充。缺点1、存取速度慢，不适于随机存取。2、当物理块间的连接指针出错时，数据丢失。3、更多的寻道次数和寻道时间。4、链接指针占用一定的空间，降低了空间利用率。3、索引结构文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构，称为索引表，并将存放文件信息的物理块的块号存放在索引表中。索引表是磁盘块地址数组,其中第i个条目指向文件的第i块。优点1、不需要为每个文件预留物理块。2、既能顺序存取，又能随机存取。3、满足了文件动态增长、插入删除的要求。缺点1、较多的寻道次数和寻道时间。2、索引表本身带来了系统开销。如：内外存空间，存取时间等。84文件目录在一个计算机系统中保存有许多文件，用户在创建和使用文件时只给出文件的名字，由文件系统根据文件名找到指定文件。为了便于对文件进行管理，设置了文件目录，用于检索系统中的所有文件。4.1文件目录组成文件系统的一个最大的特点是“按名存取”，用户只要给出文件的符号名就能方便地存取在外存空间的文件信息，而不必关心文件的具体物理地址。而实现文件符号到文件物理地址映射的主要环节是检索文件目录。系统为每个文件设置一个描述性数据结构——文件控制块FCB，文件目录就是文件控制块的有序集合，即把所有文件控制块有机地组织起来，就构成了文件目录。（1）文件控制块FCB结构FCB是系统为管理文件而设置的一个数据结构。FCB是文件存在的标志，它记录了系统管理文件所需要的全部信息。FCB通常应包括以下内容：文件名，文件号，用户名，文件地址，文件长度，文件类型，文件属性，共享计数，文件的建立日期，保存期限，最后修改日期，最后访问日期，口令，文件逻辑结构，文件物理结构等。（2）目录文件为了实现对文件目录的管理，通常将文件目录以文件的形式长期保存在外存空间，这个文件就被称为目录文件。通常，目录文件是长度固定的记录式文件。4.2文件目录结构文件目录结构分为一级目录结构，二级目录结构和多级目录结构。5文件系统的实现操作系统文件管理算法研究9前面讨论的文件系统，主要是从用户的角度探讨问题。这里是将从实现的角度讨论文件系统如何实现，也就是文件系统的内在物理结构。文件的使用者关心文件是如何命名、可以进行哪些文件操作。文件目录是如何组织的、如何检索或查找文件目录等问题。而设计和实现者感兴趣的是，在磁盘上怎样安排文件和目录存储，如何管理磁盘空间以及怎样使文件系统有效而可靠地工作等。文件系统实现的关键是，找到一种符合设计要求的方法，把文件记录到磁盘块上去。所谓文件的物理结构，是从系统的角度来看文件，从文件在物理介质上的存放方式来研究文件。5.1文件记录块文件的存储设备常常划分为若干大小相等的物理块。同时也将文件信息划分成逻辑块，所有块统一编号。以块为单位进行信息的存储、传输和分配。从用户的角度来看文件，是把每一个文件看作是一个整体的，不考虑文件实际在磁盘上的存放方法。事实上，文件有大有小，磁盘的存储空间也有大小，另外，文件传输时也必须分块。这样，在文件系统中，是以块作为分配和传送信息的基本单位。显然，对于字符流的无结构文件来说，每一个物理块中存放长度相等的文件信息。不过，对于记录式文件来说，由于记录长度可以是固定的，也可以是可变的，而且其长度不一定刚好等于其物理块的长度，从而有可能给由记录的逻辑地址到物理地址的变换带来了额外的负担。5.2磁盘空间的管理一个存储设备上的空闲空间登记表（FSL）动态跟踪记录该存储设备上所有空闲块的数目和块号。该数据结构虽称为表，但不一定以二维表形式实现。为方便高效安全起见，一般把FSL放在存储实体上。由于设备空间是有限的，故不再使用的空间必须回收以重用，然后在建立文件等操作中重新动态分配。可见在文件删除、文件建立、写文件等操作中都会访问与修改空闲空间表。在实际系统中四种不同的方案，分别为位示图、空闲块表、10空闲块链表、成组链表。1、位示图位示图法的基本思想是利用一串二进制的值来反映磁盘空间的分配使用情况。每一个磁盘物理块对应一个二进制位，如果物理块为空闲，则相应