中科大操作系统原理与实现课件10_FileSystem.pdf

操作系统原理与设计 第10章 FS interface 文件系统概述 陈香兰 中国科学技术大学计算机学院 2009年12月 提纲 File Concept Access Methods Directory Structure File System Mounting Protection 小结和作业 File System Outline File Concept Access Methods Directory Structure File System Mounting Protection 小结和作业 File Concept IOS provides a uniform logical view of infomation storage despite the various storage media I A fi le is a logical storage unit I A fi le is a named collection of related information that is recorded on secondary storage ITypes I Data numeric character binary I Program I In general a fi le is a sequence of bits bytes lines or records I the meaning is defi ned by the fi le s creator and user IContiguous logical address space File Attributes IName only information kept in human readable form IA name is usually a string of characters such as example c Iuppercase vs lowercase care or not care I Identifi er unique tag number identifi es fi le within FS I it is the non human readable name for the fi le I Type needed for systems that support diff erent types I Location pointer to fi le location on device I Size current fi le size may also include MAX size IProtection Access control information who can do reading writing executing I Time date and user identifi cation data for protection security and usage monitoring I Information about fi les are kept in the directory structure which is maintained on the disk File Operations I IFile is an abstract data type OS provides the 6 basic system calls 1 Create allocate space create an directory entry 2 Write write pointer 3 Read read pointer 4 Reposition within fi le also known as seek 5 Delete release space erase the directory entry 6 Truncate fi le len 0 release space all other attributes remain unchanged Iothers I for fi le append rename I for fi le attribute chown chmod Ifor directory I OS ensures locking integrity I Windows OSes IAdvisory I processes can fi nd status of locks and decide what to do I up to software developers I UNIX File Types Name Extension File Structure I I Sometimes fi le types can indicate the internal structure of fi le I fi le structures INone sequence of words bytes ISimple record structure I Lines I Fixed length I Variable length IComplex Structures I Formatted document I Relocatable load fi le I Can simulate last two with fi rst method I system supported fi le structures I Most modern OSes support a minimal number of fi le structures directly I e g UNIX sees every fi le as a sequence of 8 bit bytes File Structure II I Benefi ts I applications have more fl exibility I simplifi es the OS I internel fi le structure I How to locate an off set within a fi le I Logical fi le record Physical block IPacking is required to convert between logical records and physical blocks I Internal fragmentation will occur Outline File Concept Access Methods Directory Structure File System Mounting Protection 小结和作业 Access Methods IFile store information When it is used this information must be accessed and read into computer memory I On a logical perspective of users access a fi le of records 1 Sequential Access 2 Direct Access 3 Indexed Access Sequential Access I information in the fi le is processed in order one record after the other I A tape model of fi le I File operations move to rec 20 seek 1 move to rec 19 read ISimulation of Sequential Access on a Direct access File Direct Access II How can we get n If the record is with variable length then Indexed Access I I Make an index fi le for the fi le which contains pointers to various records Iimproves search time I Search the index fi le fi rst and then use the pointer to access the fi le directly and to fi nd the desired record II O is reduced IExample of Index and Relative Files Indexed Access II I With large fi les the index fi le itself may become to large to be kept in memory IMulti level index table Outline File Concept Access Methods Directory Structure File System Mounting Protection 小结和作业 A Typical File system Organization I IPartition mini disks volumes IOne disk IPart of a disk provide separate logical spaces on one disk IN disks group several disks into a single logical space IFiles directories IDirectory I holds fi le information e g name location size type for all fi les in that partition A Typical File system Organization II Directory Structure I A collection of nodes containing information about all fi les I Both the directory structure and the fi les reside on disk IBackups of these two structures are kept on tapes Information in a Directory entry IName IType IAddress ICurrent length IMaximum length IDate last accessed for archival IDate last updated for dump IOwner ID who pays IProtection information IDOS I FCB fi le control block I32 bytes each IMay cost many I O operations to search for an entry IUNIX I Inode Store most of fi le attributes in inode I Directory entry contains fi le name a pointer to the inode I16 bytes Operations Performed on Directory I Search for a fi le I Create a fi le I Delete a fi le IList a directory I Rename a fi le I Traverse the fi le system ISearch in the table for an entry IInsert an entry IDelete an entry IModify an entry I Organize the Directory Logically to Obtain I Eff iciency locating a fi le quickly INaming convenient to users I Two users can have same name for diff erent fi les I The same fi le can have several diff erent names IGrouping human convention I logical grouping of fi les by properties e g all Java programs all games Directory Structures ISingle level directory ITwo level directory ITree structured directory IAcyclic graph directory IGeneral graph directory Single Level Directory IEasy to support and understand IA single directory for all users I when there are large numbers of fi les and or users IVery low searching speed O N INaming problem I Small naming space Igrouping problem Two Level Directory I ISeparate directory for each user IUFD User File Directory I Each entry owns information for a user s fi le I MFD Master fi le directory IEach entry contains User name Pointer to his UFD I Can have the same fi le name for diff erent user I Eff icient searching Two Level Directory II INo grouping capability IEasy management IAdd delete a user ISecurity VS Sharing IMFD system administrator IUFD isolated from other users IDirectory tree seen as an inverted tree path name I How to share E g system wide fi les dara program I copy for each user I searching path IA UFD may be very large then Tree Structured Directories I IRoot directory directory subdirectory I Regular fi le VS subdirectory I Treat a subdirectory like another fi le Tree Structured Directories II I use a special bit in the directory entry to distinguish a fi le 0 from a subdirectory 1 ICurrent directory working searching directory I Creating a new fi le is done in current directory IInitial current directory IAbsolute vs relative path names E g spell words rade spell words rade Ioperations Ichange current directory cd spell mail prog I delete a fi le rm Ilist a dictory ls Icreate a new directory mkdir I Example if in current directory mail Tree Structured Directories III mkdir count Idelete a directory I MS DOS only empty directory VS UNIX optional I I Eff icient searching IGrouping Capability I The tree structure prohibits the sharing of fi les and directories Acyclic Graph Directories I I Have shared subdirectories and fi les with no cycles I the same fi le or directory may be in two diff erent directories having two diff erent names aliasing Acyclic Graph Directories II IImplementation ISymbolic links I A special new directory entry link I The content of such fi le is the path name of the real fi le directory I How to traverse a directory contains symbolic links IDuplicates directory entries I Hard to maintain consistency ITraversing problem I Diff erent names actual only one fi le Itraverse more than once Acyclic Graph Directories III IDeleting problem IIf direct deletes list dangling pointer I or preserve the fi le until all reference to it are deleted ISolutions I File reference list I Reference count hard link in UNIX IHow to ensure there are no cycles General Graph Directory I IIf we allow cycles existed in directory General Graph Directory II IThe traversing problem and deleting problem still exists even more complicatedly I Infi nite loop I limit the access number of a directory while for a search IGarbage garbage collection IHow do we guarantee no cycles I Allow only links to fi le not subdirectories IEvery time a new link is added use a cycle detection algorithm to determine whether it is OK Outline File Concept Access Methods Directory Structure File System Mounting Protection 小结和作业 File System Mounting I A fi le system must be mounted before it can be accessed I A unmounted fi le system is mounted at a mount point a Existing b Unmounted Partition c if using users as Mount Point Outline File Concept Access Methods Directory Structure File System Mounting Protection 小结和作业 Protection IReliability IGuarding against physical damage IFile systems can be damaged by I Hardware problems power surges or failures head crashed dirt temperature extremes or Vandalism I Generally provided by duplicate copies of fi les disk tape IProtection IGuarding against improper access Protection in multi user system ITypes of access IRead Write Execute Append Delete List IHigher level functions Irename copy edit IFi