1File SystemsChapter 4vFilesvDirectoriesvFile System ImplementationvExample File Systems2OverviewvRequirements for long term information storage:1.Must store large amounts of data2.Information stored must survive the termination of the process using it3.Multiple processes must be able to access the information concurrentlyvSolution: Store information on disk or other external media in units called files.vThe file system is a part of operating system that manages files.3Basic Functions of File SystemvPresent logical (abstract) view of files and directoriesHide complexity of hardware devicesvFacilitate efficient use of storage devicesOptimize access, e.g., to diskvSupport sharingProvide protection4File SystemvUsers view on file systems (4.1, 4.2)How files are named?What operations are allowed on them?What the directory tree looks like?vImplementers view on file systems (4.3)How files and directories are stored?How disk space is managed?How to make everything work efficiently and reliably?5FilesvContentsFile NamingFile StructureFile TypesFile AccessFile AttributesFile OperationsAn Example Program Using File System Calls6File Naming (1)vFile naming - FileName.FileExtentionvValid nameNumber of charactersvStrings of letters, digits, and special charactersvUp to 255 characterslower vs. upper casevExtensionTied to type of fileUsed by applications7File Naming (2)Typical file extensions8File Structure (1)vNone - sequence of words, bytes (Unix, Windows)vSimple record structureLinesFixed lengthvComplex StructuresRecord TreevRecords not necessarily the same lengthvRecords contain keysvTree sorted on key9File Structure (2) vThree kinds of filesbyte sequence record sequencetree10Files types (1)vFile typesRegular files contain user informationvASCII file: displayed, printed, editedvBinary file (internal 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 (2)(a) An executable file (b) An archive12File AccessvSequential accessread all bytes/records from the beginningcannot jump around, could rewind or back upconvenient when medium was magnetic tapevRandom accessbytes/records read in any orderessential for database systemsTwo methods are used for specifying where to start reading.vread and then move file markervmove file marker (seek), then read (UNIX, Windows)13File AttributesPossible file attributesvOperating systems associate extra information with each file, called file attributes (metadata).14File Operations1.Create2.Delete3.Open4.Close5.Read6.Write7.Append8.Seek9.Get attributes10.Set Attributes11.RenamevOperations 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)17DirectoryvContentsSingle-level Directory SystemTwo-level Directory SystemHierarchical Directory SystemPath NamesDirectory Operations18DirectoryvFile systems have directories or folders to keep track of files.vDirectory is a file containing correspondence between filenames and file locationsvDirectory entries contain info about a filei.e. its attributesvDirectory entries are created when the files they describe are created and removed when files are deleted19Organize the Directory to ObtainvEfficiency locating a file quicklyvNaming convenient to usersTwo users can have same name for different filesThe same file can have several different namesvGrouping logical grouping of files by properties (e.g., all Java programs, all games, )20Directory StructurevA single-level directory has one directory (root) containing all the files.vA two-level directory has a root directory and user directories.vA hierarchical directory has a root directory and arbitrary number of subdirectories.21A single level directory system (1)vA single level directory systemcontains 4 filesowned by 3 different people, A, B, and C22A single level directory system (2)vAdvantageEasy to support and understandvDisadvantagesNaming ProblemvAll files must have unique namesvName Collision ProblemGrouping ProblemvDifficult to remember file names in a large file system23Two-level Directory Systems (1)Letters indicate owners of the directories and filesvA user name and a file name define a path name24vAdvantagesResolves name-collision problemvCan have the same file name for different userEfficient searchingFile sharing and protectionvDisadvantageGrouping problem not resolvedTwo-level Directory Systems (2)25vGeneralization of two-level directory (with arbitrary height)vLeaf nodes are filesvInterior nodes are directoriesvEach user has a current directory (working directory)Can change current directory via cd command or system callv Path names can be absolute or relativeHierarchical Directory Systems (1)26Hierarchical Directory Systems (2)A hierarchical directory system27Path Name (1)vTwo different methods are used to specify file names in a directory tree:Absolute path name consists of the path from the root directory to the file.Relative path name consists of the path from the current directory (working directory).vThe path name would be written:Winodws usrastmailboxUNIX /usr/ast/mailboxvDot and dotdot are two special entries in the file system.Dot (.) refers to the current directory. Dot dot (.) refers to its parent.28A UNIX directory treePath Name (2)vAssume working Dir/usr/astvExamplecp /usr/lib/dictionary .cp ./lib/dictionary .29Directory OperationsvCreate a new directoryvDelete an empty directoryvOpen a directory for readingvClose a directory to release spacevReaddir return next entry in the directoryvRename a directoryvLinkCreate a link from the existing file to a path name. (ie. Make a “hard link”.)vUnlink remove a “hard link”30File System ImplementationvContentsFile System LayoutImplementing FilesImplementing DirectoryShared FilesDisk Space ManagementFile System ReliabilityFile System Performance31File System Layout (1)vMBR (Master Boot Record) in sector 0 is used to boot the computer.vThe partition table gives the starting and ending addresses of each partition, one of which is marked as activevEach partition can hold its own file system, Unix file system, Window file system or othersvEvery partition starts with a “boot block”The boot block contains a small program, which can load the OS in that partitionvOS StartupBIOS reads MBR, then locates the active partition, reads in its boot block and executes it32File System layout (2) A possible file system layout33Implementing filesvImplementing file storage is keeping track of which disk blocks go with which files.vThree methodsContiguous AllocationLinked List AllocationIndexed Allocation34Contiguous Allocation (1)vStore each file as contiguous block of data.(a) Contiguous allocation of disk space for 7 files(b) State of the disk after files D and F have been removed35Contiguous Allocation (2) 36Contiguous Allocation (3) vAdvantagesSimple to implement (Need only starting sector & length of file)Read performance is excellent (suits for sequential access and direct access)vDisadvantagesDisk fragmentationThe maximum file size must be known when file is created, or files cannot growvGood for CD-ROMs, DVDs and other write-once optical mediaAll file sizes are known in advanceFiles are never deleted37Linked List Allocation (1) vStoring a file as a linked list of disk blocks, blocks may be scattered anywhere on the disk.vThe first word of each block is used as a pointer to the next one.38Linked List Allocation (2)39Linked List Allocation (3)vAdvantages: 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 accessvDisadvantages: Random access slowThe amount of data in a block is not a power of 2 40Linked List Allocation Using FAT (1)vTake table pointer word from each block and put them in an index table, FAT (File Allocation Table).vA section of disk at the beginning of each partition is set aside to contain FATvFAT should be kept in memory to minimize disk seeksSpace overhead can be substantialvFile 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 freevUsed 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)vAdvantagesThe entire block is available for dataRandom access.vSearch the linked list (but all in memory)Directory Entry needs only one numbervStarting block numbervDisadvantageEntire table must be in memory all at once!vExample20 GB = disk size1 KB = block size4 bytes = FAT entry size80 MB of memory used to store the FAT44Indexed Allocation (i-Node) (1)vBring all the pointers together into one location (index block or index-node)vEach 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)vLoading the i-node need only into memory when the corresponding file is opened.vEach directory entry contains i-number onlyvExample:46Indexed Allocation (i-Node) (3)vMulti-level Indexed Allocation47Indexed Allocation (i-Node) (4)vAdvantagesSupports direct accessWithout suffering from external fragmentationi-node need only be in memory when the corresponding file is openvDisadvantageSpace overhead for indexes48Implementation Directories (1) vWhen a file is opened, the file system uses the path name to locate the directory entry. vThe 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)vWhere to store attributes? 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) vHandling long file names in a directory:Fixed-length names (Waste space)In-line (When a file is removed, a variable-sized gap is introduced.)Heap (The heap management needs extra effort.)vHow to search files in each directory?LinearlyHash tableCache the results of searches51Implementing Directories (4)vTwo ways of handling long file names in directory(a) In-line(b) In a heap52Shared Files (1)vA shared file is used to allow a file to appear in several directories.vThe connection between a directory and the shared file is called a link. The file system is a Directed Acyclic Graph (DAG), not a tree.vProblemsIf directories contain disk address, 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)vSolution:Do not list disk block addresses in directories but in a little data structure, i-node Hard LinkvBoth 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)vOne directory points to the files i-nodevOther directory contains the “path”vSee page 5755Shared Files (4)vHard Link56Shared Files (5) vPats working directory: /users/pat/bin/v$ 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 xtrv$ ln /users/steve/wb . (hard link)v$ ls -l total 5-rwxr-xr-x 1 pat DP3832 1358 Jan 15 11:01 lcat -rwxr-xr-x 2 steve DP3725 89 Jun 25 13:30 wb -rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr57Shared Files (6)vSymbolic Link58Shared Files (7) v$ rm wbv$ 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 xtrv$ ln -s /users/steve/wb ./symwb (symbolic link)v$ ls -l total 5-rwxr-xr-x 1 pat DP3832 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)vDeleting a fileDirectory entry is removed from directoryAll blocks in file are returned to free listWhat about sharing?vMultiple links to one file (in Unix)vHard 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 filevSymbolic Link (only the owner directory has a pointer to i-node)Remove the real file. (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)vProblems of symbolic link Extra overhead in the traversing pathHaving multiple copies of a file may set copied when dumping a file onto a tape.62Journaling File Systems (1)vJournaling 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 workvRebooting the systemvLook in the log to see whats going on at the time of crashvFinish the jobE.g., NTFS, ext3, ReiserFS63Journaling File Systems (2)vOperations 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.vThe journaling file systemWrite a log entry listing 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 beginvAfter the operations complete successfully, the log entry is erasedvIf the system crashes, upon recovery the file system can check the log to see if any operations were pending.64Position of the virtual file system.Virtual File Systems65Disk space managementvStrategies for storing an n byte file:Allocate n consecutive bytes of disk space - segmentAllocate a number n/k blocks of size k bytes each - pagingvProblem of contiguous allocation If the file grows it will have to be moved on the disk, it is an expensive operation and causes external fragmentation. = vAlmost all file systems chop files up into fixed-size blocks that need not to be adjacent.66Block size (1)vReviewFile systems define a block sizevBlock size = 2n * sector sizevContiguous sectors are allocated to a blockFile systems view the disk as an array of blocksvMust allocate blocks to filevMust manage free space on disk67Block size (2)vLarge block sizes Internal fragmentationvLast block has (on average) 1/2 wasted spaceLots of very small files; waste is greater.Lower disk space utilization, but better performancevSmall block sizesMore seeks; file access will be slower.Better disk utilization, but poor performancevUsual size k = 1k, 2k or 4k68vDotted line (left hand scale) gives data rate of a diskvDark line (right hand scale) gives disk space efficiencyvAssume all files are 4KBBlock size (3)69Keeping Track of Free Blocks (1) vUse 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. vUse bit-map: A disk with n blocks requires 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.vBit map generally better if it can be kept 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)vThe loss of a file system can be catastrophic.vBackups are made to handleRecover from disasterRecover from stupidity (e.g. Recycle bin)vWhere to backup? Tertiary storageTape: holds 10 or 100s of GBs, costs pennies/GBvsequential access high random access timevBackup takes time and space72File System Reliability (2)vBackup IssuesShould the entire FS be backup up?vBinaries, special I/O files usually not backed upDo not backup unmodified files since last backupvIncremental dumps: complete per month, modified files dailyCompress data before writing to tapeHow to backup an active FS?vNot acceptable to take system offline during backup hoursSecurity of backup media73File System Reliability (3)vTwo strategies for dumping a disk to tape:Physical dump: starts at block 0 to the last one, write each block in ordervAdvantages: simple and fastvDisadvantagesCan not skip selected directoriesCan not make incremental dumpsCan not restore individual files upon request74File System Reliability (4)vTwo strategies for dumping a disk to tape:Logical dump: starts at one or more specified directories and recursively dumps all files and directories found that have changed since some given base datevBase date could be of last incremental dump, last full dump, etc.vAlso dump all directories (even unmodified) that lie on the path to a modified file or directory75vFile System ConsistencyMost systems have a utility program that checks file system consistencyvWindows: scandiskvUNIX: fsckTwo types of consistency checks can be made: vBlocks vFiles (directory)fsck: checking blocksvReads all the i-nodes and mark used blocksvExamines the free list or bit maps and mark free blocksFile System Reliability (5)76vFile System ConsistencyInconsistent StatesvSome block is not in a file or on free list (“missing block”)Add it to the free listvSome 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 oncevSome block is in more than one fileAllocate another blockCopy the blockPut it in a fileNotify the user that one file may contain data from another filevSome block is on free list and is in some fileRemove it from the free listFile System Reliability (6)77File System Reliability (7)vFile system states(a) consistent(b) missing block(c) duplicate block in free list(d) duplicate data block(c)(d)block numberblock number78vFile System Consistencyfsck: checking directoriesvUse a per-file counter instead of per-blockvRecursively descends the tree from the root directory, increasing the counter for each file, include hard links.vCompare these numbers with the link counts stored in the i nodes.vProblems: Reference count is too large or too smallvSolutionCorrect the reference count, force the link count in the i-node to the actual number of directory entries.File System Reliability (8)79vCachingAvoid disk I/O overheadvBlock Read AheadvReducing Disk Arm MotionAvoid seek overheadFile System Performance80Example File SystemsvThe MS-DOS File SystemvThe Windows 98 File SystemvThe Unix V7 File System81The MS-DOS File System (1)The MS-DOS directory entry82The MS-DOS File System (2)vMaximum partition for different block sizes(The empty boxes represent forbidden combinations)83The Windows 98 File System (1)The extended MOS-DOS directory entry used in Windows 98Bytes84The Windows 98 File System (2)An entry for (part of) a long file name in Windows 98BytesChecksum85The Windows 98 File System (3)An example of how a long name is stored in Windows 98(File name: The quick brown fox jumps over the lazy dog)r86The UNIX V7 File System (1)A UNIX V7 directory entry87The UNIX V7 File System (2)A UNIX i-node88The UNIX V7 File System (3)The steps in looking up /usr/ast/mbox89QuizHow many disk operations are needed to read the second block of the file /usr/student/lab/mp1.tar? Why? (Assume that nothing else along the path is in memory. Also assume that all directories fit in one disk block. )90Solutioni-node for /directory for /i-node for /usrdirectory for /usri-node for /usr/studentdirectory for /usr/studenti-node for /usr/student/labdirectory for /usr/student/labi-node for /usr/student/lab/mp1.tarthe second block of /usr/student/lab/mp1.tarIn total, 10 disk reads are required.91SummaryvFiles vDirectories vFile system implementation vExample file systems 92Homeworkv3、14、20、32、33