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

《中科大操作系统原理与实现课件10_FileSystem.pdf》由会员分享，可在线阅读，更多相关《中科大操作系统原理与实现课件10_FileSystem.pdf（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.操作系统原理与设计第10章 FS interface（文件系统概述）陈香兰中国科学技术大学计算机学院2009年12月.提纲File ConceptAccess MethodsDirectory StructureFile System MountingProtection小结和作业.File System.OutlineFile ConceptAccess MethodsDirectory StructureFile System MountingProtection小结和作业.File ConceptIOS provides a uniform logical view of infoma

2、tion storagedespite the various storage media.IA file is a logical storage unit.IA file is a named collection of related information that isrecorded on secondary storage.ITypes:IData:numeric;character;binaryIProgramIIn general,a file is a sequence of bits,bytes,lines,orrecords.Ithe meaning is define

3、d by the files creator and user.IContiguous logical address space.File Attributes.IName only information kept in human-readable formIA name is usually a string of characters,such as example.cIuppercase vs.lowercase;care or not careIIdentifier unique tag(number)identifies file within FSIit is the non

4、-human-readable name for the fileIType needed for systems that support different typesILocation pointer to file location on deviceISize current file size;may also include MAX sizeIProtection Access-control information:who can doreading,writing,executingITime,date,and user identification data for pro

5、tection,security,and usage monitoringIInformation about files are kept in the directory structure,which is maintained on the disk.File Operations IIFile is an abstract data type.OS provides the 6 basicsystem calls1.Create:allocate space+create an directory entry2.Write:write pointer3.Read:read point

6、er4.Reposition within file:also known as seek5.Delete:release space+erase the directory entry6.Truncate:file len=0;release space;all other attributesremain unchangedIothers:Ifor file:append,renameIfor file attribute:chown,chmod,.Ifor directory&directory entries:IOpen(Fi)search the directory structur

7、e on disk for entry Fi,and move the content of entry to memoryIClose(Fi)move the content of entry Fiin memory todirectory structure on disk.Open Files&Open-File Table IIOpen-file table:a small table containing information aboutall open filesISeveral processes may open the same file at the same timeI

8、2-levels:a per-process table&a system-wide table withprocess-independent informationISeveral pieces of data are needed to manage open files:IFile pointer:pointer to last read/write location,process-dependentIFile-open count:counter of number of times a file is open to allow removal of data from open

9、-file table when lastprocesses closes itIDisk location of the file:the information needed to locatethe file on disk,always is kept in memoryIAccess rights:per-process access mode information.Open Files&Open-File Table II.Open File LockingIProvided by some OSes and FSesIallow one process to lock a fi

10、le and prevent other processesfrom gaining access to itIfunctionality is similar to reader-writer locksIOS-or FS-dependentIOS may provide either Mandatory or advisory:IMandatoryIaccess is denied depending on locks held and requested;IOS ensures locking integrityIWindows OSesIAdvisoryIprocesses can f

11、ind status of locks and decide what to doIup to software developersIUNIX.File Types Name,Extension.File Structure IISometimes,file types can indicate the internal structure of fileIfile structuresINone-sequence of words,bytesISimple record structureILinesIFixed length;IVariable lengthIComplex Struct

12、uresIFormatted documentIRelocatable load fileICan simulate last two with first methodIsystem-supported file structuresIMost modern OSes support a minimal number of filestructures directlyIe.g.UNIX sees every file as a sequence of 8-bit bytes.File Structure IIIBenefits:Iapplications have more flexibi

13、lityIsimplifies the OSIinternel file structureIHow to locate an offset within a file?ILogical file(record)Physical blockIPacking is required to convert between logical records andphysical blocksIInternal fragmentation will occur.OutlineFile ConceptAccess MethodsDirectory StructureFile System Mountin

14、gProtection小结和作业.Access MethodsIFile store information.When it is used,this information mustbe accessed and read into computer memoryIOn a logical perspective of users,access a file of records1.Sequential Access2.Direct Access3.Indexed Access.Sequential AccessIinformation in the file is processed in

15、 order,one record afterthe other.IA tape model of file;IFile operations&the effect on file pointerread/write nextresetrewind/forward n.Direct Access IIInformation in the file is processed in no particular order.IFile is made up of fixed-length of logical recordsIA disk model of a fileICan move quick

16、ly to any record location by supplying arelative record number(n)IRead n&Write n,IFile pointer=L n,0 n N,where N is the last recordnumber,L is the fixed length of each record.IPosition n&read/write next,e.g.seek(20);/move to rec.20seek(-1);/move to rec.19read();ISimulation of Sequential Access on a

17、Direct-access File.Direct Access IIHow can we get n?If the record is with variable length,then?.Indexed Access IIMake an index file for the file,which contains pointers tovarious recordsIimproves search timeISearch the index file first,and then use the pointer to accessthe file directly and to find

18、the desired record.II/O is reducedIExample of Index and Relative Files.Indexed Access IIIWith large files,the index file itself may become to large to bekept in memoryIMulti-level index table.OutlineFile ConceptAccess MethodsDirectory StructureFile System MountingProtection小结和作业.A Typical File-syste

19、m Organization IIPartition(mini-disks,volumes)IOne diskIPart of a diskprovide separate logical spaces on one diskIN disksgroup several disks into a single logical spaceIFiles+directoriesIDirectoryIholds file information(e.g.name,location,size,type)for allfiles in that partition.A Typical File-system

20、 Organization II.Directory StructureIA collection of nodes containing information about all filesIBoth the directory structure and the files reside on diskIBackups of these two structures are kept on tapes.Information in a Directory entry.INameITypeIAddressICurrent lengthIMaximum lengthIDate last ac

21、cessed(for archival)IDate last updated(for dump)IOwner ID(who pays)IProtection informationIDOSIFCB(file control block)I32 bytes eachIMay cost many I/Ooperations to search for anentryIUNIXIInode:Store most of fileattributes in inodeIDirectory entry contains filename+a pointer to the inodeI16 bytes.Op

22、erations Performed on DirectoryISearch for a fileICreate a fileIDelete a fileIList a directoryIRename a fileITraverse the filesystemISearch in the table foran entryIInsert an entryIDelete an entryIModify an entryI.Organize the Directory(Logically)to ObtainIEfficiency locating a file quicklyINaming c

23、onvenient to usersITwo users can have same name for different filesIThe same file can have several different namesIGrouping human conventionIlogical grouping of files by properties,(e.g.,all Java programs,all games,).Directory StructuresISingle-level directoryITwo-level directoryITree-structured dir

24、ectoryIAcyclic-graph directoryIGeneral-graph directory.Single-Level DirectoryIEasy to support and understand.IA single directory for all usersIwhen there are large numbers of files and/or users.IVery low searching speed,O(N)INaming problemISmall naming space&Name collisionIMS-DOS:11 bytes for filena

25、meIUNIX:256 bytesIprotection VS sharing;Igrouping problem.Two-Level Directory IISeparate directory for each userIUFD,User File DirectoryIEach entry owns information for a users fileIMFD,Master file directoryIEach entry contains:User name,Pointer to his UFDICan have the same file name for different u

26、serIEfficient searching.Two-Level Directory IIINo grouping capabilityIEasy managementIAdd/delete a userISecurity VS.SharingIMFD,system administratorIUFD,isolated from other usersIDirectory tree(seen as an inverted tree)&path nameIHow to share?E.g.system-wide files(dara,program,.)Icopy for each user?

27、Isearching pathIA UFD may be very large,then.Tree-Structured Directories IIRoot directory&directory&subdirectoryIRegular file VS.subdirectoryITreat a subdirectory like another file.Tree-Structured Directories IIIuse a special bit in the directory entry to distinguish a file(0)from a subdirectory(1)I

28、Current directory(working/searching directory)ICreating a new file is done in current directory.IInitial current directoryIAbsolute vs.relative path names.E.g./spell/words/rade./spell/words/radeIoperationsIchange current directory:cd/spell/mail/progIdelete a file:rm Ilist a dictory:lsIcreate a new d

29、irectory:mkdir IExample:if in current directory/mail.Tree-Structured Directories IIImkdir countIdelete a directoryIMS-DOS(only empty directory)VS.UNIX(optional)I.IEfficient searchingIGrouping CapabilityIThe tree structure prohibits the sharing of files anddirectories.Acyclic-Graph Directories IIHave

30、 shared subdirectories and files,with no cyclesIthe same file or directory may be in two different directories,having two different names(aliasing).Acyclic-Graph Directories IIIImplementationISymbolic linksIA special new directory entry(link)IThe content of such file is the path name of the realfile

31、/directoryIHow to traverse a directory contains symbolic links?IDuplicates directory entriesIHard to maintain consistencyITraversing problemIDifferent names,actual only one fileItraverse more than once.Acyclic-Graph Directories IIIIDeleting problemIIf direct deletes list dangling pointerIor preserve

32、 the file until all reference to it are deletedISolutions:IFile-reference listIReference count:hard link in UNIXIHow to ensure there are no cycles?.General Graph Directory IIIf we allow cycles existed in directory.General Graph Directory IIIThe traversing problem and deleting problem still exists,ev

33、enmore complicatedlyIInfinite loopIlimit the access number of a directory while for a searchIGarbage&garbage collectionIHow do we guarantee no cycles?IAllow only links to file not subdirectoriesIEvery time a new link is added use a cycle detection algorithmto determine whether it is OK.OutlineFile C

34、onceptAccess MethodsDirectory StructureFile System MountingProtection小结和作业.File System MountingIA file system must be mounted before it can be accessedIA unmounted file system is mounted at a mount point(a)Existing.(b)Unmounted Partition(c)if using/users as Mount Point.OutlineFile ConceptAccess Meth

35、odsDirectory StructureFile System MountingProtection小结和作业.ProtectionIReliabilityIGuarding against physical damageIFile systems can be damaged byIHardware problems,power surges or failures,head crashed,dirt,temperature extremes,or VandalismIGenerally provided by duplicate copies of files(disktape,.)I

36、ProtectionIGuarding against improper access.Protection in multi-user systemITypes of accessIRead/Write/Execute/Append/Delete/ListIHigher-level functionsIrename/copy/edit/.IFile owner/creator should be able to control:Iwhat can be done?by whom?.Access control IIthe most common approach to the protect

37、ion problem:ID-dependent accessImake access dependent on the ID of the userIthe most general scheme to implement ID-dependentaccess:Access control list(ACL)IAssociate with each file and directory an access list.IAccess list specifies for each listed(allowed)user name and thetypes of(allowed)access a

38、llowed.IStored in each directory entryILength problemISolution:Three classes of users.IAbout group:IAsk manager to create a group(unique name),say G,and addsome users to the group.IFor a particular file(say game)or subdirectory,define anappropriate access.IAttach a group to a filechgrp G game.Windows XP Access-control List Management.A Sample UNIX Directory Listing.OutlineFile ConceptAccess MethodsDirectory StructureFile System MountingProtection小结和作业.小结File ConceptAccess MethodsDirectory StructureFile System MountingProtection小结和作业.作业I名词解释：符号链接（symbolic links）和硬链接（hardlinks）.谢谢！