File SystemsFile Systems: Disk OrganizationDesign ProblemsImportant File SystemsTypical Similarities Among File SystemsTypical Differences Between File SystemsCase Study: Berkeley Fast File System (FFS)FFS HeadersFFS File TrackingFFS InodesFFS Free-Space ManagementFFS FragmentationFile Systems and Data StructuresEffect of File Systems on ProgramsSummary: Goals of Unix File SystemsFile SystemsFile SystemsTopicsTopicsDesign criteriaHistory of file systemsBerkeley Fast File SystemEffect of file systems on programsfs.pptCS 105“Tour of the Black Holes of Computing”– 2 –CS 105File Systems: Disk OrganizationFile Systems: Disk OrganizationA disk is a sequence of 512-byte sectorsA disk is a sequence of 512-byte sectorsUnfortunate historical fact; now we’re stuck with itFirst comes First comes boot blockboot block and and partition tablepartition tablePartition table divides the rest of disk into partitionsPartition table divides the rest of disk into partitionsMay appear to operating system as logical “disks”Useful for multiple OSes, etc.Otherwise bad idea; hangover from earlier daysFile systemFile system: partition structured to hold : partition structured to hold filesfiles (data) (data)Usually aggregates sectors into blocks or clustersTypical size: 2-16 sectors (1K-8K bytes)Increases efficiency by reducing overhead– 3 –CS 105Design ProblemsDesign ProblemsAs seen before, disks have mechanical delaysAs seen before, disks have mechanical delaysSeek time: move heads to where data is (2-20 ms)Rotational delay: wait for data to get under heads (2-8 ms)Transfer time: move data into memory (1-15 μs)Fundamental problem in file-system design: how to Fundamental problem in file-system design: how to hide (or at least minimize) these delays?hide (or at least minimize) these delays?Side problems also important:Side problems also important:Making things reliable (in face of s/w and h/w crashes)Organizing data (e.g., in directories or databases)Enforcing security– 4 –CS 105Important File SystemsImportant File SystemsFAT: old Windows and MSDOS standardFAT: old Windows and MSDOS standardNTFS: Windows current standardNTFS: Windows current standardFFS: Unix standard since 80’sFFS: Unix standard since 80’sAFS: distributed system developed at CMUAFS: distributed system developed at CMULFS: Berkeley redesign for high performanceLFS: Berkeley redesign for high performanceZFS: redesigned Unix system, recently released by SunZFS: redesigned Unix system, recently released by SunISO 9660: CD-ROM standardISO 9660: CD-ROM standardEXT2/EXT3: Linux standards, variants of FFSEXT2/EXT3: Linux standards, variants of FFSReiserFS: redesigned Linux systemReiserFS: redesigned Linux systemOther OS’s have own file organization: VMS, MVS, Other OS’s have own file organization: VMS, MVS, – 5 –CS 105Typical SimilaritiesAmong File SystemsTypical SimilaritiesAmong File SystemsA (secondary) boot recordA (secondary) boot recordA top-level directoryA top-level directorySupport for hierarchical directoriesSupport for hierarchical directoriesManagement of free and used spaceManagement of free and used spaceMetadata about files (e.g., creation date)Metadata about files (e.g., creation date)Protection and securityProtection and security– 6 –CS 105Typical DifferencesBetween File SystemsTypical DifferencesBetween File SystemsNaming conventions: case, length, special symbolsNaming conventions: case, length, special symbolsFile size and placementFile size and placementSpeedSpeedError recoveryError recoveryMetadata detailsMetadata detailsSupport for special filesSupport for special files– 7 –CS 105Case Study: Berkeley Fast File System (FFS)Case Study: Berkeley Fast File System (FFS)First public Unix (Unix V7) introduced many important First public Unix (Unix V7) introduced many important concepts in Unix File System (UFS)concepts in Unix File System (UFS)I-nodesIndirect blocksUnix directory structure and permissions systemUFS was simple, elegant, and slowUFS was simple, elegant, and slowBerkeley initiated project to solve the slownessBerkeley initiated project to solve the slownessMany modern file systems are direct or indirect Many modern file systems are direct or indirect descendants of FFSdescendants of FFSIn particular, EXT2 and EXT3– 8 –CS 105FFS HeadersFFS HeadersBoot block: first few sectorsBoot block: first few sectorsTypically all of cylinder 0 is reserved for boot blocks, partition tables, etc.Superblock: file system parameters, includingSuperblock: file system parameters, includingSize of partition (note that this is dangerously redundant)Location of root directoryBlock sizeCylinder groups, includingCylinder groups, includingData blocksList of inodesBitmap of used blocks and fragments in the groupReplica of superblock (not always at start of group)– 9 –CS 105FFS File TrackingFFS File TrackingDirectory: file containing variable-length recordsDirectory: file containing variable-length recordsFile nameI-node numberInode: holds metadata for one fileInode: holds metadata for one fileLocated by number, using info from superblockIntegral number of inodes in a blockIncludesOwner and groupFile type (regular, directory, pipe, symbolic link, …)Access permissionsTime of last i-node change, last modification, last accessNumber of links (reference count)Size of file (for directories and regular files)Pointers to data blocks– 10 –CS 105FFS InodesFFS InodesInode has 15 pointers to data blocksInode has 15 pointers to data blocks12 point directly to data blocks13th points to an indirect block, containing pointers to data blocks14th points to a double indirect block15th points to a triple indirect blockWith 4K blocks and 4-byte pointers, triple indirect With 4K blocks and 4-byte pointers, triple indirect block can address 4 terabytes (2block can address 4 terabytes (24242 bytes) of data bytes) of dataData blocks might not be contiguous on diskData blocks might not be contiguous on diskBut OS tries to But OS tries to clustercluster related items in cylinder group: related items in cylinder group:Directory entriesCorresponding inodesTheir data blocks– 11 –CS 105FFS Free-Space ManagementFFS Free-Space ManagementFree space managed by bitmapsFree space managed by bitmapsOne bit per blockMakes it easy to find groups of contiguous
View Full Document
Unlocking...