现代操作系统 Chapter 4.ppt

Chapter 4 File systemsContents4.1 Files4.2 Directories4.3 File System Implementation4.4 File System Management and Optimization4.5 Example File Systems 2File SystemsvEssential requirements for long-term information storage:It must be possible to store a very large amount of information.The information must survive the termination of the process using it.Multiple processes must be able to access the information concurrently.3File SystemsvFiles are logical units of information created by processes.vThat part of the OS dealing with files is known as the file system.44.1 Files4.1.1 File namingvWhen a process creates a file,it gives the file a name.When the process terminates,the file continues to exist and can be accessed by other processes using its name.vThe rules of file naming(文件命名规则文件命名规则)vFile extension(文件扩展名文件扩展名)5Figure 4-2.Three kinds of files.(a)Byte sequence.(b)Record sequence.(c)Tree.4.1.2 File structure64.1.3 File TypesvRegular file(普通文件普通文件)ASCII filesBinary filesvSpecial file(特殊文件特殊文件)Character special file:are related to input/output and used to model serial I/O devicesBlock special file:are used to model disks74.1.4 File accessvSequential access(顺序存取顺序存取)A process could read all the bytes or records in a file in order,starting at the beginning,but could not skip around and read them out of order.vRandom access(随机存取随机存取)The bytes or records in these files can be read in any order.84.1.5 File attributesFigure 4-4.Some possible file attributes.94.1.6 File OperationsvCreatevDeletevOpenvClosevReadvWritevAppendvSeekvGet attributesvSet attributesvRename 104.1.7 An example program using file system calls(1)11An example program using file system calls(2)124.2 Directories1.Single-level Directory systemsvAdvantages:SimplicityThe ability to locate file quickly13Directories2.Hierarchical(层次层次)directory systemsAdvantages:can group files in natural ways14Directories3.Path namesvAbsolute path name(绝对路径绝对路径):consisting of the path from the root directory to the file.It always start at the root directory and are unique.vRelative path name(相对路径相对路径):it is used in conjunction with the concept of the working directory.15Directories4.Directory OperationsCreateDeleteOpendirClosedirReaddirRenameLinkUnlink 164.3 File System Implementation4.3.1 File System Layout4.3.2 Implementing Files4.3.3 Implementing directories4.3.4 Shared files4.3.5 Journaling File Systems(JFS)4.3.6 Virtual File Systems(VFS)174.3.1 File System Layout(布局布局)Sector 0 of the disk is called the MBR(Master Boot Record,主引导记录主引导记录)and is used to boot the computer.The end of the MBR contains the partition table.184.3.2 Implementing FilesThe most important issue in implementing file storage is keeping track of which disk blocks go with which file.vContiguous allocation(连续分配连续分配)vLinked list allocation(链表分配链表分配)vLinked list allocation using a table in memoryvi-nodes 191.Contiguous allocation The simplest allocation scheme is to store each file as a contiguous run of disk blocks.20Contiguous allocationFigure 4-10.(a)Contiguous allocation of disk space for 7 files.(b)The state of the disk after files D and F have been removed.21Contiguous allocationvAdvantages:It is simple to implement.The read performance is excellent.vDisadvantage:Over the course of time,the disk becomes fragmented.vAn example of contiguous allocation:CD-ROM222.Linked list allocation Linked list allocation:The first word of each block is used as a pointer to the next one.The rest of the block is for data.23Linked list allocationFigure 4-11.Storing a file as a linked list of disk blocks.24Linked list allocationvAdvantage:every disk block can be used.No space is lost to disk fragmentation(except for internal fragmentation in the last block).vDisadvantage:random access is extremely slowThe amount of data storage in a block is no longer a power of two because the pointer takes up a few bytes.253.Linked list allocation using a table in memoryBoth disadvantages of the linked list allocation can be eliminated by taking the pointer word from each disk block and putting it in a table in memory.Such a table in main memory is called a FAT(File Allocation Table,文件分配表文件分配表).26Linked list allocation using a table in memory Figure 4-12.Linked list allocation using a file allocation table in main memory.Disadvantage:the entire table must be in memory all the time to make it work.The FAT idea doesnt scale well to large disks.274.i-nodesFigure 4-13.An example i-node.vAssociate with each file a data structure called an i-node,which lists the attributes and disk addresses of the files blocks.vAdvantage:the i-node need only be in memory when the corresponding file is open.284.3.3 Implementing directoriesvWhen a file is opened,the OS uses the path name supplied by the user to locate the directory entry.The directory entry provides the information needed to find the disk blocks.vThe main function of the directory system is to map the ASCII name of the file onto the information needed to locate the data.29Implementing directoriesvWhere should the attributes be stored?1.One obvious possibility is to store them directly in the directory entry.30Implementing directories2.For systems that use i-nodes,another possibility for storing the attributes is in the i-nodes,rather than in the directory entries.31Implementing directoriesvSo far we have made the assumption that files have short,fixed-length names.However,nearly all modern OS support longer,variable-length file names.How can these be implemented?vMethod 1:to set a limit on file name length,typically 255 characters,and then use one of the designs of Fig 4-14.This approach wastes a great deal of directory space,since few files have such long names.32vMethod 2:each directory entry contains a fixed portion,typically starting with the length of the entry,and then followed by data with a fixed format,usually including the file attributes.This fixed-length header is followed by the actual file name.Implementing directories33Implementing directoriesvMethod 3:make the directory entries themselves all fixed length and keep the file names together in a heap(堆堆)at the end of the directory.344.3.4 Shared filesvWhen several users are working together on a project,they often need to share files.35Shared filesvSolution 1:disk blocks are not listed in directories,but in i-node.This is the approach used in UNIX.Hard link(硬链接硬链接)vSolution 2:B links to one of Cs files by having the system create a new file,of type LINK.The new file contains just the path name of the file to which it is linked.Symbolic link(符号链接符号链接)36Disadvantages of the two solutions?vHard link:vSymbolic link:require extra overhead374.3.5 Journaling File Systems(JFS)vThe basic idea is to keep a log of what the file system is going to do before it does it,so that if the system crashes before it can do its planned work,upon rebooting the system can look in the log to see what was going on at the time of the crash and finish the job.Journaling file systems(日志文件系统日志文件系统)vMicrosofts NTFS systemvThe Linux ext3 file system38An examplevOperations required to remove a file in UNIX:Remove the file from its directory.Release the i-node to the pool of free i-nodes.Return all the disk blocks to the pool of free disk blocks.vWhat the JFS does is first write a log entry listing the three actions to be completed.The log entry is then written to disk.Only after the log entry has been written,do the various operations begin.After the operations complete successfully,the log is erased.394.3.6 Virtual File Systems(VFS)vMost UNIX systems have used the concept of a VFS(虚拟文件系统虚拟文件系统)to try to integrate multiple file systems into an orderly structure.Fig.4-18 Position of the VFS40VFSvThe key idea of VFS is to abstract out that part of the file system that is common to all file systems and put that code in a separate layer that calls the underlying concrete file systems to actual manage the data.vAll system calls relating to files are directed to the VFS for initial processing.These calls,coming from user processes,are the standard POSIX calls,such as open,read,write,and so on.Thus the VFS has an“upper”interface to user processes and it is the well-known POSIX interface.41VFSvThe VFS also has a“lower”interface to the concrete file systems,which is labeled VFS interface in Fig.4-18.This interface consists of several dozen function calls.Thus to create a new file system that works with the VFS,the designers of the new file system must make sure that it supplies the function calls the VFS requires.424.4 File System Management and Optimization4.4.1 Disk Space Management4.4.2 File System Backup4.4.3 File System Consistency4.4.4 File System Performance4.4.5 Defragmenting Disks434.4.1 Disk Space ManagementvTwo possible strategies for storing an n bytes file:n consecutive(连续的连续的)bytes of disk space are allocated.The file is split up into a number of(not necessarily)contiguous blocks.Problems？Nearly all file systems chop(砍砍,分割分割)files up into fixed-size blocks that need not be adjacent(相邻的相邻的).441.Block SizevHow big the block should be?vLarge block size:Every file,even a 1-byte file,ties up an entire block.Small files waste a large amount of disk space.vSmall block size:Most files will span(跨越跨越)multiple blocks and thus need multiple seeks and rotational delays(旋转延迟旋转延迟)to read them,reducing performance.45Block SizevHistorically,file systems have chosen size in the 1-KB to 4-KB range,but with disks now exceeding 1 TB,it might be better to increase the block size to 64KB and accept the wasted disk space.462.Keeping track of free blocksvTwo methods:Using a linked list of disk blocks,with each block holding as many free disk block numbers as will fit.Bitmap.A disk with n blocks requires a bitmap with n bits.47Figure 4-22.(a)Storing the free list on a linked list.(b)A bitmap.Keeping track of free blocks483.Disk Quotas(磁盘配额磁盘配额)vTo prevent people from hogging(贪婪攫贪婪攫取取)too much disk space,multi-user OS often provide a mechanism for enforcing disk quotas.vThe idea is that the system administrator assigns each user a maximum allotment of files and blocks,and the OS make sure that the users do not exceed their quotas.49Figure 4-24.Quotas are kept track of on a per-user basis in a quota table.Disk Quotas50vPer quota two limits:Soft and Hardsoft limit用户可以使用超过用户可以使用超过soft limit的空的空间，这时系统会对用户发出警告，要求用户清间，这时系统会对用户发出警告，要求用户清理自己的文件以释放空间。若用户在理自己的文件以释放空间。若用户在限期限期内没内没有释放出空间，将不能再保存任何文件。有释放出空间，将不能再保存任何文件。hard limit是分配给每个用户的最大空间。是分配给每个用户的最大空间。如果用户超过这个限制就不能再保存文件。如果用户超过这个限制就不能再保存文件。vGrace period(限期限期)identifies how long the soft limit may be exceededAfter that period,a user gets errors instead of warningsDisk Quotas51Example of quota524.4.2 File System Backup vIf a computers file system is irrevocably(不能取消的，无可挽回的不能取消的，无可挽回的)lost,restoring all the information will be difficult,time consuming,and in many cases,impossible.File System Backup 53File System Backup1.Should the entire file system be backed up or only part of it?It is usually desirable to back up only specific directories and everything in them rather than the entire file system.2.It is wasteful to back up files that have not changed since the previous backup,which leads to the idea of incremental dumps(增量转储增量转储).54File System Backup3.It may be desirable to compress the data before writing them to the tape.4.It is difficult to perform a backup on an active file system.So algorithms have been devised for making rapid snapshots of the file system state by copying critical data structures,and then requiring future changes to files and directories to copy the blocks instead of updating them in place.5.Backup tapes should be kept off-site.55File System BackupvTwo strategies can be used for dumping a disk to tape:A physical dump(物理转储物理转储)A logical dump(逻辑转储逻辑转储)56Physical dumpvA physical dump starts at block 0 of the disk,write all the disk blocks onto the output tape in order,and stops when it has copied the last one.vAdvantages:SimplicityGreat speedvDisadvantages:The inability to skip selected directoriesThe inability to make incremental dumpsThe inability to restore individual files upon request57Logical dumpvA logical dump starts at one or more specified directories and recursively(递递归地归地)dumps all files and directories found there that have changed since some given base date(基准日期基准日期).584.4.3 File System Consistency(文件系统的一致性文件系统的一致性)vMany file systems read blocks,modify them,and write them out later.If the system crashes before all the modified blocks have been written out,the file system can be left in an inconsistent state.vTo deal with the problem of inconsistent file systems,most computers have a utility program that checks file system consistency.UNIX has fsckWindows has scandisk59File System ConsistencyvTwo kinds of consistency checks:Blocks(块的一致性检查块的一致性检查)Files(文件的一致性检查文件的一致性检查)1.Check for block consistency The program builds two tables,each one containing a counter for each block,initially set to 0.The counters in the first table keep track of how many times each block is present in a file;The counters in the second table record how often each block is present in the free list.601.Check for block consistencyFigure 4-27.File system states.(a)Consistent.(b)Missing block.(c)Duplicate block in free list.(d)Duplicate data block.612.Check for file consistencyvIt also uses a table of counters,but these are per file,rather than per block.vIt starts at the root directory and recursively descends the tree,inspecting each directory in the file system.For every i-node in every directory,it increments a counter for that files usage count.vWhen the check is all done,it has a list,indexed by i-node number,telling how many directories contain each file.vIt then compares these numbers with the link counts stored in the i-nodes themselves.vIn a consistent file system,both counts will agree.624.5 Example File Systems4.5.1 The MS-DOS File System4.5.2 The UNIX V7 File System634.5.1 The MS-DOS File SystemvThe MS-DOS file system is the one the first IBM PCs came with.vThe MS-DOS uses a fixed-size 32-byte directory entry.Figure 4-31.The MS-DOS directory entry.64The MS-DOS File SystemvMS-DOS keeps track of file blocks via a FAT in main memory.vThe directory entry contains the number of the first file block.This number is used as an index into the FAT.vThe FAT file system comes in three versions:FAT-12,FAT-16,and FAT-32,depending on how many bits a disk address contains.65The MS-DOS File SystemvFor all FATs,the disk block can be set to some multiple of 512 bytes,with the set of allowed block size(called cluster sizes(簇大小簇大小)by Microsoft)being different for each variant.66The MS-DOS File SystemFigure 4-32.Maximum partition size for different block sizes.The empty boxes represent forbidden combinations.674.5.2 The UNIX V7 File SystemFigure 4-33.A UNIX V7 directory entry.vFile names are up to 14 characters.vThese parameters limit the number of files per file system to 64K.68The UNIX V7 File SystemFigure 4-34.A UNIX i-node.69Example:how to loo