1、1File SystemsChapter 4FilesDirectoriesFile System ImplementationExample File Systems2OverviewRequirements for long term information storage:Must store large amounts of dataInformation stored must survive the termination of the process using itMultiple processes must be able to access the information

2、 concurrentlySolution: Store information on disk or other external media in units called files.The file system is a part of operating system that manages files.3Basic Functions of File SystemPresent logical (abstract) view of files and directoriesHide complexity of hardware devicesFacilitate幫助 effic

3、ient use of storage devicesOptimize優(yōu)化 access, e.g., to diskSupport sharingProvide protection4File SystemUsers view on file systems (4.1, 4.2)How files are named?What operations are allowed on them?What the directory tree looks like?Implementers view on file systems (4.3)How files and directories are

4、 stored?How disk space is managed?How to make everything work efficiently and reliably?5FilesContentsFile NamingFile StructureFile TypesFile AccessFile AttributesFile OperationsAn Example Program Using File System Calls6File Naming (1)File naming - FileName.FileExtentionValid nameNumber of character

5、sStrings of letters, digits, and special charactersUp to 255 characterslower vs. upper caseExtension擴(kuò)展名Tied to type of fileUsed by applications7File Naming (2)Typical file extensions8File Structure (1)None - sequence of words, bytes (Unix, Windows)無(wú)結(jié)構(gòu)的字節(jié)序列Simple record structure簡(jiǎn)單的記錄結(jié)構(gòu)LinesFixed len

6、gthComplex StructuresRecord TreeRecords not necessarily the same lengthRecords contain keysTree sorted on key9File Structure (2) Three kinds of filesbyte sequence record sequencetree10Files types (1)File typesRegular files contain user informationASCII file: displayed, printed, editedBinary file (in

7、ternal structure): executable file, archive存檔 fileDirectories are system files for maintaining the structure of the file system.Character special files字符特殊文件 are used to model serial I/O devices such as terminals, printers, and networks.Block special files塊特殊文件 are used to model disks.11File Types (

8、2)(a) An executable file (b) An archive12File AccessSequential accessread all bytes/records from the beginningcannot jump around, could rewind倒回 or back upconvenient when medium was magnetic tapeRandom accessbytes/records read in any orderessential for database systemsTwo methods are used for specif

9、ying where to start reading.read and then move file markermove file marker (seek), then read (UNIX, Windows)13File AttributesPossible file attributesOperating systems associate extra information with each file, called file attributes (metadata元數(shù)據(jù)).14File OperationsCreateDeleteOpenCloseReadWriteAppen

10、dSeekGet attributesSet AttributesRenameOperations for “sequence of bytes” files15An Example Program Using File System Calls (1)A Unix program that copy files . Copyfile sourcefile destfile16An Example Program Using File System Calls (2)17DirectoryContentsSingle-level Directory SystemTwo-level Direct

11、ory SystemHierarchical Directory SystemPath NamesDirectory Operations18DirectoryFile systems have directories or folders to keep track of files.Directory is a file containing correspondence一致 between filenames and file locationsDirectory entries contain info about a filei.e. its attributesDirectory

12、entries are created when the files they describe are created and removed when files are deleted19Organize the Directory to ObtainEfficiency locating a file quicklyNaming convenient to usersTwo users can have same name for different filesThe same file can have several different namesGrouping logical

13、grouping of files by properties (e.g., all Java programs, all games, )20Directory StructureA single-level directory has one directory (root) containing all the files.A two-level directory has a root directory and user directories.A hierarchical directory has a root directory and arbitrary number of

14、subdirectories.21A single level directory system (1)A single level directory systemcontains 4 filesowned by 3 different people, A, B, and C22A single level directory system (2)AdvantageEasy to support and understandDisadvantagesNaming ProblemAll files must have unique namesName Collision沖突 ProblemGr

15、ouping ProblemDifficult to remember file names in a large file system23Two-level Directory Systems (1)Letters indicate owners of the directories and filesA user name and a file name define a path name24AdvantagesResolves name-collision problemCan have the same file name for different userEfficient s

16、earchingFile sharing and protectionDisadvantageGrouping problem not resolvedTwo-level Directory Systems (2)25Generalization of two-level directory (with arbitrary height)Leaf nodes are filesInterior nodes are directoriesEach user has a current directory (working directory)Can change current director

17、y via cd command or system call Path names can be absolute or relativeHierarchical Directory Systems (1)26Hierarchical Directory Systems (2)A hierarchical directory system27Path Name (1)Two different methods are used to specify file names in a directory tree:Absolute path name consists of the path f

18、rom the root directory to the file.Relative path name consists of the path from the current directory (working directory).The path name would be written:Winodws usrastmailboxUNIX /usr/ast/mailboxDot and dotdot are two special entries in the file system.Dot (.) refers to the current directory. Dot do

19、t (.) refers to its parent.28A UNIX directory treePath Name (2)Assume working Dir/usr/astExamplecp /usr/lib/dictionary .cp ./lib/dictionary .29Directory OperationsCreate a new directoryDelete an empty directoryOpen a directory for readingClose a directory to release spaceReaddir return next entry in

20、 the directoryRename a directoryLinkCreate a link from the existing file to a path name. (ie. Make a “hard link”.)Unlink remove a “hard link”30File System ImplementationContentsFile System LayoutImplementing FilesImplementing DirectoryShared FilesDisk Space ManagementFile System ReliabilityFile Syst

21、em Performance31File System Layout (1)MBR (Master Boot Record)主引導(dǎo)記錄 in sector 0 is used to boot the computer.The partition table gives the starting and ending addresses of each partition, one of which is marked as activeEach partition can hold its own file system, Unix file system, Window file syste

22、m or othersEvery partition starts with a “boot block”The boot block contains a small program, which can load the OS in that partitionOS StartupBIOS reads MBR, then locates the active partition, reads in its boot block and executes it32File System layout (2) A possible file system layout33Implementin

23、g filesImplementing file storage is keeping track of which disk blocks go with which files.Three methodsContiguous AllocationLinked List AllocationIndexed Allocation34Contiguous Allocation (1)Store each file as contiguous block of data.(a) Contiguous allocation of disk space for 7 files(b) State of

24、the disk after files D and F have been removed35Contiguous Allocation (2) 36Contiguous Allocation (3) AdvantagesSimple to implement (Need only starting sector & length of file)Read performance is excellent (suits for sequential access and direct access)DisadvantagesDisk fragmentationThe maximum file

25、 size must be known when file is created, or files cannot growGood for CD-ROMs, DVDs and other write-once optical mediaAll file sizes are known in advanceFiles are never deleted37Linked List Allocation (1) Storing a file as a linked list of disk blocks, blocks may be scattered分散 anywhere on the disk

26、.The first word of each block is used as a pointer to the next one.38Linked List Allocation (2)39Linked List Allocation (3)Advantages: No external fragmentationDirectory entries are simple (Need only starting address)A file can continue to grow as long as free blocks are availableGood for sequential

27、 accessDisadvantages: Random access slowThe amount of data in a block is not a power of 2 40Linked List Allocation Using FAT (1)Take table pointer word from each block and put them in an index table, FAT (File Allocation Table).A section of disk at the beginning of each partition is set aside to con

28、tain FATFAT should be kept in memory to minimize disk seeksSpace overhead can be substantialFile Allocation TableOne entry per block on the disk, ordered by block numberEach entry contains the address of the “next” blockEnd of file marker (-1)A special value (e.g. -2) indicates the block is freeUsed

29、 by OS/2 and MS-DOS41Linked List Allocation Using FAT (2)Linked list allocation using FAT in RAM42Linked List Allocation Using FAT (3)43Linked List Allocation Using FAT (4)AdvantagesThe entire block is available for dataRandom access.Search the linked list (but all in memory)Directory Entry needs on

30、ly one numberStarting block numberDisadvantageEntire table must be in memory all at once!Example20 GB = disk size1 KB = block size4 bytes = FAT entry size80 MB of memory used to store the FAT44Indexed Allocation (i-Node) (1)Bring all the pointers together into one location (index block or index-node

31、)Each file has its own index-node (i-node), which lists the attributes and disk block addresses of the file.An example i-node45Indexed Allocation (i-Node) (2)Loading the i-node need only into memory when the corresponding file is opened.Each directory entry contains i-number onlyExample:46Indexed Al

32、location (i-Node) (3)Multi-level Indexed Allocation47Indexed Allocation (i-Node) (4)AdvantagesSupports direct accessWithout suffering from external fragmentationi-node need only be in memory when the corresponding file is openDisadvantageSpace overhead for indexes48Implementation Directories (1) Whe

33、n a file is opened, the file system uses the path name to locate the directory entry. The directory entry provides information needed to find the disk blocks.disk address of the entire file (contiguous blocks)the number of first block (linked list)the number of i-node (i-node)Where to store attribut

34、es? In directory or i-node?49Implementing Directories (2)(a) A simple directory MS-DOS/Windowsfixed size entriesdisk addresses and attributes in directory entry(b) Directory in which each entry just refers to an i-node - UNIX50Implementation Directories (3) Handling long file names in a directory:Fi

35、xed-length names (Waste space)In-line (When a file is removed, a variable-sized gap is introduced.)Heap (The heap management needs extra effort.)How to search files in each directory?LinearlyHash tableCache the results of searches51Implementing Directories (4)Two ways of handling long file names in

36、directory(a) In-line(b) In a heap52Shared Files (1)A shared file is used to allow a file to appear in several directories.The connection between a directory and the shared file is called a link. The file system is a Directed Acyclic Graph (DAG)有向無(wú)環(huán)圖, not a tree.ProblemsIf directories contain disk ad

37、dress, a copy of the disk address will have to be made in directory B. If B or C append the file, the new blocks will only appear in one directory.53Shared Files (2)File system containing a shared file54Shared Files (3)Solution:Do not list disk block addresses in directories but in a little data str

38、ucture, i-node Hard LinkBoth directories point to the same i-node (next page)Create a new file of type LINK which contains the path name of the file to which it is linked Symbolic Link (Soft Link)One directory points to the files i-nodeOther directory contains the “path”See page 5755Shared Files (4)

39、Hard Link56Shared Files (5) Pats working directory: /users/pat/bin/$ ls -ltotal 4-rwxr-xr-x 1 pat DP3832 1358 Jan 15 11:01 lcat -rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr$ ln /users/steve/wb . (hard link)$ ls -l total 5-rwxr-xr-x 1 pat DP3832 1358 Jan 15 11:01 lcat -rwxr-xr-x 2 steve DP3725 89 Jun

40、 25 13:30 wb -rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr57Shared Files (6)Symbolic Link58Shared Files (7) $ rm wb$ ls -ltotal 4-rwxr-xr-x 1 pat DP3832 1358 Jan 15 11:01 lcat -rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr$ ln -s /users/steve/wb ./symwb (symbolic link)$ ls -l total 5-rwxr-xr-x 1 pat DP

41、3832 1358 Jan 15 11:01 lcat lrwxr-xr-x 1 pat DP3725 15 Jul 20 15:22 symwb-/users/steve/wb -rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr59Shared Files (8)Deleting a fileDirectory entry is removed from directoryAll blocks in file are returned to free listWhat about sharing?Multiple links to one file (i

42、n Unix)Hard LinksPut a “reference count” field in each i-nodeCounts number of directories that point to the fileWhen removing file from directory, decrement countWhen count goes to zero, reclaim all blocks in the fileSymbolic Link (only the owner directory has a pointer to i-node)Remove the real fil

43、e. (normal file deletion)Symbolic link becomes “broken”60Shared Files (9)(a) Situation prior to linking(b) After the link is created(c) After the original owner removes the file61Shared Files (10)Problems of symbolic link Extra overhead in the traversing pathHaving multiple copies of a file may set

44、copied when dumping轉(zhuǎn)儲(chǔ) a file onto a tape磁帶.62Journaling File Systems (1)Journaling File SystemKeep a log of what the file system is going to do before it does itIf the system crashes before it completes its planned workRebooting the systemLook in the log to see whats going on at the time of crashFin

45、ish the jobE.g., NTFS, ext3, ReiserFS63Journaling File Systems (2)Operations required to remove a file in UNIXRemove 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.The journaling file systemWrite a log entry listi

46、ng the three actions to be completed, and write the log entry to diskOnly after the log entry has been written to disk, the various operations can beginAfter the operations complete successfully, the log entry is erasedIf the system crashes, upon recovery the file system can check the log to see if

47、any operations were pending.64Position of the virtual file system.Virtual File Systems65Disk space managementStrategies for storing an n byte file:Allocate n consecutive bytes of disk space - segmentAllocate a number n/k blocks of size k bytes each - pagingProblem of contiguous allocation If the fil

48、e grows it will have to be moved on the disk, it is an expensive operation and causes external fragmentation. = Almost all file systems chop files up into fixed-size blocks that need not to be adjacent.66Block size (1)ReviewFile systems define a block sizeBlock size = 2n * sector sizeContiguous sect

49、ors are allocated to a blockFile systems view the disk as an array of blocksMust allocate blocks to fileMust manage free space on disk67Block size (2)Large block sizes Internal fragmentationLast block has (on average) 1/2 wasted spaceLots of very small files; waste is greater.Lower disk space utiliz

50、ation, but better performanceSmall block sizesMore seeks; file access will be slower.Better disk utilization, but poor performanceUsual size k = 1k, 2k or 4k68Dotted line (left hand scale) gives data rate of a diskDark line (right hand scale) gives disk space efficiencyAssume all files are 4KBBlock

51、size (3)69Keeping Track of Free Blocks (1) Use linked list of disk blocks: each block holds as many free disk block numbers as will fit.With 1 KB block and 32-bit disk block number 1024 * 8/32 = 256 disk block numbers 255 free blocks (and) 1 next block pointer. Use bit-map: A disk with n blocks requ

52、ires a bit map with n bitsFree blocks are represented by 1sAllocated blocks represented by 0s16GB disk has 224 1-KB and requires 224 bits 2048 blocksUsing a linked list = 224/255 = 65793 blocks. However, these blocks can be freed up as the disk is filled up.Bit map generally better if it can be kept

53、 completely in memory.70(a) Storing the free list on a linked list(b) A bit mapKeeping Track of Free Blocks (2) 71File System Reliability (1)The loss of a file system can be catastrophic.Backups are made to handleRecover from disasterRecover from stupidity (e.g. Recycle bin)Where to backup? Tertiary

54、 storageTape: holds 10 or 100s of GBs, costs pennies/GBsequential access high random access timeBackup takes time and space72File System Reliability (2)Backup IssuesShould the entire FS be backup up?Binaries, special I/O files usually not backed upDo not backup unmodified files since last backupIncr

55、emental dumps: complete per month, modified files dailyCompress data before writing to tapeHow to backup an active FS?Not acceptable to take system offline during backup hoursSecurity of backup media73File System Reliability (3)Two strategies for dumping a disk to tape:Physical dump: starts at block

56、 0 to the last one, write each block in orderAdvantages: simple and fastDisadvantagesCan not skip selected directoriesCan not make incremental dumpsCan not restore individual files upon request74File System Reliability (4)Two strategies for dumping a disk to tape:Logical dump: starts at one or more

57、specified directories and recursively dumps all files and directories found that have changed since some given base dateBase date could be of last incremental dump, last full dump, etc.Also dump all directories (even unmodified) that lie on the path to a modified file or directory75File System Consi

58、stencyMost systems have a utility program that checks file system consistencyWindows: scandiskUNIX: fsckTwo types of consistency checks can be made: Blocks Files (directory)fsck: checking blocksReads all the i-nodes and mark used blocksExamines the free list or bit maps and mark free blocksFile Syst

59、em Reliability (5)76File System ConsistencyInconsistent StatesSome block is not in a file or on free list (“missing block”)Add it to the free listSome block is on the free list more than onceCant happen when using a bitmap for free blocksFix the free list so the block appears only onceSome block is

60、in more than one fileAllocate another blockCopy the blockPut it in a fileNotify the user that one file may contain data from another fileSome block is on free list and is in some fileRemove it from the free listFile System Reliability (6)77File System Reliability (7)File system states(a) consistent(