Khoa học máy tính - Chapter 13: File systems

Chapter 13File SystemsCopyright © 20081Operating Systems, by Dhananjay Dhamdhere*IntroductionOverview of File ProcessingFiles and File OperationsFundamental File Organizations and Access MethodsDirectoriesMounting of File SystemsFile ProtectionAllocation of Disk SpaceInterface Between File System and IOCS2Operating Systems, by Dhananjay Dhamdhere*Introduction (continued)File ProcessingFile Sharing SemanticsFile System ReliabilityJournaling File SystemsVirtual File SystemCase Studies of File SystemsPerformance of File Systems3Operating Systems, by Dhananjay Dhamdhere*Overview of File Processing4Operating Systems, by Dhananjay Dhamdhere*File System and the IOCSFile system views a file as a collection of data that is owned by a user, shared by a set of authorized users, and reliably stored over an extended periodIOCS views it as a repository of data that is accessed speedily and stored on I/O device that is used efficientlyTwo kinds of data: file data and control data5Operating Systems, by Dhananjay Dhamdhere*File Processing in a ProgramAt programming language level:File: object with attributes describing organization of its data and the method of accessing the data6Operating Systems, by Dhananjay Dhamdhere*File types can be grouped into two classes:Structured files: Collection of recordsRecord: collection of fieldsField: contains a single data itemEach record is assumed to contain a unique key fieldByte stream files: “Flat”A file has attributes, stored in its directory entryFiles and File Operations7Operating Systems, by Dhananjay Dhamdhere*Files and File Operations (continued)8Operating Systems, by Dhananjay Dhamdhere*Fundamental File Organizations and Access MethodsFundamental record access patterns:Sequential accessRandom accessFile organization is a combination of two features:Method of arranging records in a fileProcedure for accessing themAccesses to files governed by a specific file organization are implemented by IOCS module called access method9Operating Systems, by Dhananjay Dhamdhere*Sequential File OrganizationRecords are stored in an ascending or descending sequence according to the key fieldRecord access pattern of an application is expected to follow suitTwo kinds of operations:Read the next (or previous) recordSkip the next (or previous) recordUses:When data can be conveniently presorted into an ascending or descending orderFor byte stream files10Operating Systems, by Dhananjay Dhamdhere*Direct File OrganizationProvides convenience/efficiency of file processing when records are accessed in a random orderFiles are called direct-access filesRead/write command indicates value in key fieldKey value is used to generate address of record in storage mediumDisadvantages:Record address calculation consumes CPU timeSome recording capacity of disk is wastedDummy records exist for key values that are not in use11Operating Systems, by Dhananjay Dhamdhere*Example: Sequential and Direct FilesEmployees with the employee numbers 3, 5–9 and 11 have left the organizationDirect file has dummy records for them12Operating Systems, by Dhananjay Dhamdhere*Index Sequential File OrganizationAn index helps determine location of a record from its key valuePure indexed organization: (key value, disk address)Index sequential organization uses index to identify section of disk surface that may contain the recordRecords in the section are then searched sequentially13Operating Systems, by Dhananjay Dhamdhere*Access MethodsAccess method: IOCS module that implements accesses to a class of files using a specific file organizationProcedure determined by file organizationAdvanced I/O techniques are used for efficiency:Buffering of recordsRecords of an input file are read ahead of the time when they are needed by a processBlocking of recordsA large block of data, whose size exceeds the size of a record in the file, is always read from, or written onto, the I/O medium14Operating Systems, by Dhananjay Dhamdhere*Directories15Operating Systems, by Dhananjay Dhamdhere*Directories (continued)File system needs to grant users:File naming freedomFile sharingFile system creates several directoriesUses a directory structure to organize themProvides file naming freedom and file sharing16Operating Systems, by Dhananjay Dhamdhere*Directory TreesSome concepts: home directory, current directoryPath names used to uniquely identify filesRelative path nameAbsolute path name17Operating Systems, by Dhananjay Dhamdhere*Directory GraphsTree structure leads to a fundamental asymmetry in the way different users can access a shared fileSolution: use acyclic graph structure for directoriesA link is a directed connection between two existing files in the directory structure18Operating Systems, by Dhananjay Dhamdhere*Operations on DirectoriesMost frequent operation on directories: searchOther operations are maintenance operations like:Creating or deleting filesUpdating file entries (upon a close operation)Listing a directoryDeleting a directoryDeletion becomes complicated when directory structure is a graphA file may have multiple parentsFile system maintains a link count with each file19Operating Systems, by Dhananjay Dhamdhere*Organization of DirectoriesFlat file that is searched linearly  inefficientHash table directory  efficient searchHash with open addressing requires a single table(Sometimes) at most two comparisons needed to locate a fileCumbersome to change size, or to delete an entryB+ tree directory  fast search, efficient add/deletem-way search tree where m ≤ 2×d (d: order of tree)Balanced tree: fast searchFile information stored in leaf nodesNonleaf nodes of the tree contain index entries20Operating Systems, by Dhananjay Dhamdhere*Directory as a B+ tree21Operating Systems, by Dhananjay Dhamdhere*Mounting of File SystemsThere can be many file systems in an OSEach file system is constituted on a logical diski.e., on a partition of a diskFiles can be accessed only when file system is mounted22Operating Systems, by Dhananjay Dhamdhere*File ProtectionUsers need controlled sharing of filesProtection info field of the file’s directory entry used to control access to the fileUsually, protection info. stored in access control listList of (,)User groups can be used to reduce size of listIn most file systems, privileges are of three kinds:ReadWriteExecute23Operating Systems, by Dhananjay Dhamdhere*Allocation of Disk SpaceDisk space allocation is performed by file systemBefore  contiguous memory allocation modelLed to external fragmentationNow  noncontiguous memory allocation modelIssues:Managing free disk spaceUse: free list or disk status map (DSM)Avoiding excessive disk head movementUse: Extents (clusters) or cylinder groupsAccessing file dataDepends on approach: linked or indexed24Operating Systems, by Dhananjay Dhamdhere*Allocation of Disk Space (continued)The DSM has one entry for each disk blockEntry indicates if block is free or allocated to a fileInformation can be maintained in a single bitDSM also called a bit mapDSM is consulted every time a new disk block has to be allocated to a file25Operating Systems, by Dhananjay Dhamdhere*Linked AllocationEach disk block has data, address of next disk block Simple to implementLow allocation/deallocation overheadSupports sequential files quite efficientlyFiles with nonsequential organization cannot be accessed efficientlyReliability is poor (metadata corruption)26Operating Systems, by Dhananjay Dhamdhere*Linked Allocation (continued)MS-DOS uses a variant of linked allocation that stores the metadata separately from the file dataFAT has one element corresponding to every disk block in the diskPenalty: FAT has to be accessed to obtain the address of the next disk blockSolution: FAT is held in memory during file processing27Operating Systems, by Dhananjay Dhamdhere*Indexed AllocationAn index (file map table (FMT)) is maintained to note the addresses of disk blocks allocated to a fileSimplest form: FMT can be an array of disk block addresses28Operating Systems, by Dhananjay Dhamdhere*Indexed Allocation (continued)Other variations:Two-level FMT organization: compact, but access to data blocks is slowerHybrid FMT organization: small files of n or fewer data blocks continue to be accessible efficiently29Operating Systems, by Dhananjay Dhamdhere*Performance IssuesIssues related to use of disk block as allocation unitSize of the metadataEfficiency of accessing file dataBoth addressed using a larger unit of allocationUse the extent as a unit of disk space allocationExtent: set of consecutive disk blocksLarge extents provide better access efficiencyProblem: more internal fragmentationSolution: variable extent sizesSize is indicated in metadata30Operating Systems, by Dhananjay Dhamdhere*Interface Between File System and IOCSInterface between file system and IOCS consists ofFile map table (FMT)Open files table (OFT)File control block (FCB)31Operating Systems, by Dhananjay Dhamdhere*Interface Between File System and IOCS (continued)32Operating Systems, by Dhananjay Dhamdhere*Interface Between File System and IOCS (continued)When alpha is opened: File system copies FMTalpha in memory Creates fcbalpha in the OFT Initializes fields appropriately Passes offset in OFT to process, as internal_idalpha33Operating Systems, by Dhananjay Dhamdhere*File ProcessingFile System Actions at openSets up the arrangement involving FCB and OFTFile System Actions during a File OperationPerforms disk space allocation if necessaryFile System Actions at closeUpdates directories if necessary34File system actions at openPerform path name resolutionFor each component in the path name, locate the correct directory or fileHandle path names passing through mount pointsA file should be allocated disk space in its own file systemBuild FCB for the fileRetain sufficient information to perform a close operation on the fileClose may have to update the file’s entry in the parent directory It may cause changes in the parent directory’s entry in ancestor directories Operating Systems, by Dhananjay Dhamdhere*35Operating Systems, by Dhananjay Dhamdhere*File System Actions at open36Operating Systems, by Dhananjay Dhamdhere*File System Actions during a File OperationEach file operation is translated into a call: (internal_id, record_id,);Internal_id is the internal id of returned by the open callRecord_id is absent for sequential-access filesOperation is performed on the next recordDisk block address obtained from record_id37Operating Systems, by Dhananjay Dhamdhere*File System Actions at close38Operating Systems, by Dhananjay Dhamdhere*File Sharing SemanticsFile system provides two methods of file sharing for processes to choose from:Sequential sharingOnly one process accesses a file at a timeImplemented through lock field in file’s directory entryConcurrent sharingSystem creates a separate FCB for each processThree sharing modes exist (see Table 13.4)File sharing semantics:Determine how results of file manipulations performed by concurrent processes are visible39Operating Systems, by Dhananjay Dhamdhere*File Sharing Semantics (continued)40Single-image Mutable FilesOperating Systems, by Dhananjay Dhamdhere*41Multiple-image Mutable FilesOperating Systems, by Dhananjay Dhamdhere*42Operating Systems, by Dhananjay Dhamdhere*File System ReliabilityDegree to which a file system will function correctly even when faults occurE.g., data corruption in disk blocks, system crashes due to power interruptionsTwo principal aspects are:Ensuring correctness of file creation, deletion, and updatesPreventing loss of data in filesFault: defect in some part of the systemOccurrence of a fault causes a failureFailure: system behavior that is erroneousOr that differs from its expected behavior43Operating Systems, by Dhananjay Dhamdhere*Loss of File System ConsistencyFile system consistency implies correctness of metadata and correct operation of the file systemA fault may cause following failures:Some data from an open file may be lostPart of an open file may become inaccessibleContents of two files may get mixed upFor example, consider addition of a disk block to a file and a fault during step 3:1. dj.next := d1.next;2. d1.next := address (dj);3. Write d1 to disk.4. Write dj to disk.44Operating Systems, by Dhananjay Dhamdhere*Loss of File System Consistency (continued)45Operating Systems, by Dhananjay Dhamdhere*Approaches to File System ReliabilityRecovery is a classic approach that is activated when a failure is noticedFault tolerance provides correct operation of file system at all times46Operating Systems, by Dhananjay Dhamdhere*Recovery TechniquesA backup is a recording of the file system stateOverhead of creating backupsWhen indexed allocation of disk space is used, it is possible to create an on-disk backup of a file cheaply with technique that resembles copy-on-write of virtual memoryOverhead of reprocessingOperations performed after lash backup have to be reprocessedSolution: Use a combination of backups and incremental backups47Operating Systems, by Dhananjay Dhamdhere*Recovery Techniques (continued)48Operating Systems, by Dhananjay Dhamdhere*Recovery Techniques (continued)To reduce overhead of creating backups (when indexed allocation is used) only the FMT and disk block whose contents are updated after the backup is created would be copiedConserves both disk space and time49Operating Systems, by Dhananjay Dhamdhere*Fault Tolerance TechniquesFile system reliability can be improved by taking two precautions:Preventing loss of data or metadata due to I/O device malfunctionApproach: use stable storagePreventing inconsistency of metadata due to faultsApproach: use atomic actions50Maintain two copies of dataCan tolerate one fault in recording of a data itemIncurs high space and time overheadCan’t indicate if copy that survived is old or newOperating Systems, by Dhananjay Dhamdhere*Stable Storage51Operating Systems, by Dhananjay Dhamdhere*Atomic Actions52Operating Systems, by Dhananjay Dhamdhere*Atomic Actions (continued)53Operating Systems, by Dhananjay Dhamdhere*Journaling File SystemsAn unclean shutdown results in loss of dataTraditional approach: recovery techniquesModern approach: use fault tolerance techniques so system can resume operation quickly after shutdownA journaling file system implements fault tolerance by maintaining a journal54Operating Systems, by Dhananjay Dhamdhere*Virtual File SystemA virtual file system (VFS) facilitates simultaneous operation of several file systemsIt provides generic open, close, read and write Invokes operations of a specific file system55Operating Systems, by Dhananjay Dhamdhere*Case Studies of File SystemsUnix File SystemBerkeley Fast File SystemLinux File SystemSolaris File SystemWindows File System56Unix file systemFile system data structuresA directory entry contains only the file nameInode of a file contains file size, owner id, access permissions and disk block allocation informationA file structure contains information about an open fileIt contains current position in file, and pointer to its inode A file descriptor points to a file structureIndexed disk space allocation uses 3 levels of indirectionUnix file sharing semanticsResult of a write performed by a process is immediately visible to all other processes currently accessing the fileOperating Systems, by Dhananjay Dhamdhere*57Operating Systems, by Dhananjay Dhamdhere*Unix File System58Operating Systems, by Dhananjay Dhamdhere*Berkeley Fast File SystemFFS was developed to address the limitations of the file system s5fsSupports some enhancements like long file names and use of symbolic linksIncludes several innovations concerning disk block allocation and disk access:Permits use of large disk blocks (up to 8KB)Uses cylinder groups to reduce disk head movementTries to minimize rotational latency when reading sequential files59Operating Systems, by Dhananjay Dhamdhere*Linux File SystemLinux provides a virtual file system (VFS)Supports a common file model that resembles the Unix file modelStandard file system is ext2Variety of file locks for process synchronizationAdvisory locks, mandatory locks, leasesUses notion of a block groupext3 incorporates journaling60Operating Systems, by Dhananjay Dhamdhere*Solaris File SystemUnix-like file access permissionsThree access control pairs in each access control listConvenience and flexibility in file processing, through a virtual file systemRecord-level locking provided to implement fine-grained synchronization between processesNonblocked I/O mode to avoid indefinite waitsAsynchronous I/O mode: a process is not blocked for its I/O operation to completeProvides file integrity61Operating Systems, by Dhananjay Dhamdhere*Windows File SystemNTFS is designed for servers and workstationsKey feature: recoverability of the file systemNotion of partition and volumes (single and spanned); volumes have a master file table (MFT)Directory organized as a B+ treeHard links and symbolic links (called junctions)Special techniques for sparse files and data compressionMetadata modifications are atomic transactionsWrite behind capabilities of journaling file systemsVista has many new features for recovery62Operating Systems, by Dhananjay Dhamdhere*Performance of File Systems63Operating Systems, by Dhananjay Dhamdhere*Log-Structured File SystemCaching reduces disk head movement during readsLog-structured file systems reduce head movement through a radically different file organizationWrites file data of all files in a single sequential structure that resembles a journal (log file)Little head movement during write operations64Operating Systems, by Dhananjay Dhamdhere*SummaryFiles are structured or unstructured (byte stream)File system provides:File organizations (sequential, direct, indexed)Directories for grouping of related files logicallySharing and protection of filesDisk space allocation, typically indexedFile map table (FMT) stores allocation informationFile control block (FCB) stores information about a file’s processingAtomic actions can be used for fault toleranceJournaling file systems provide reliability modesVFS permits several file systems to be in operation65