Operating Systems: Internals and Design Principles, 6/E William Stallings - Chapter 12: File Management

Chapter 12File ManagementDave BremerOtago Polytechnic, N.Z.©2008, Prentice HallOperating Systems:Internals and Design Principles, 6/EWilliam StallingsRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemFilesFiles are the central element to most applicationsThe File System is one of the most important part of the OS to a userDesirable properties of files:Long-term existence Sharable between processesStructureFile ManagementFile management system consists of system utility programs that run as privileged applicationsConcerned with secondary storageTypical OperationsFile systems also provide functions which can be performed on files, typically:CreateDeleteOpenCloseReadWriteTermsFour terms are in common use when discussing files:FieldRecordFileDatabaseFields and RecordsFieldsBasic element of dataContains a single valueCharacterized by its length and data typeRecordsCollection of related fieldsTreated as a unitFile and DatabaseFileHave file namesIs a collection of similar recordsTreated as a single entityMay implement access control mechanismsDatabaseCollection of related dataRelationships exist among elementsConsists of one or more filesFile Management SystemsProvides services to users and applications in the use of filesThe way a user or application accesses filesProgrammer does not need to develop file management softwareObjectives for a File Management SystemMeet the data management needs of the userGuarantee that the data in the file are validOptimize performanceProvide I/O support for a variety of storage device typesMinimize lost or destroyed dataProvide a standardized set of I/O interface routines to user processesProvide I/O support for multiple users (if needed)Requirements for a general purpose systemEach user should be able to create, delete, read, write and modify filesEach user may have controlled access to other users’ filesEach user may control what type of accesses are allowed to the users’ filesEach user should be able to restructure the user’s files in a form appropriate to the problemRequirements cont.Each user should be able to move data between filesEach user should be able to back up and recover the user’s files in case of damageEach user should be able to access the user’s files by using symbolic namesTypical software organizationDevice DriversLowest levelCommunicates directly with peripheral devicesResponsible for starting I/O operations on a deviceProcesses the completion of an I/O requestBasic File SystemPhysical I/OPrimary interface with the environment outside the computer systemDeals with exchanging blocks of dataConcerned with the placement of blocksConcerned with buffering blocks in main memoryBasic I/O SupervisorResponsible for all file I/O initiation and termination.Control structures deal withDevice I/O, Scheduling,File status.Selects and schedules I/O with the deviceLogical I/OEnables users and applications to access recordsProvides general-purpose record I/O capabilityMaintains basic data about fileAccess MethodClosest to the userReflect different file structuresProvides a standard interface between applications and the file systems and devices that hold the dataAccess method varies depending on the ways to access and process data for the device.Elements of File ManagementRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemFile OrganizationFile Management Referring to the logical structure of recordsPhysical organization discussed laterDetermined by the way in which files are accessedCriteria for File OrganizationImportant criteria include:Short access timeEase of updateEconomy of storageSimple maintenanceReliabilityPriority will differ depending on the use (e.g. read-only CD vs Hard Drive)Some may even conflictFile Organisation TypesMany exist, but usually variations of:PileSequential fileIndexed sequential fileIndexed fileDirect, or hashed, fileThe PileData are collected in the order they arriveNo structurePurpose is to accumulate a mass of data and save itRecords may have different fieldsRecord access is by exhaustive searchThe Sequential FileFixed format used for recordsRecords are the same lengthAll fields the same (order and length)Field names and lengths are attributes of the fileKey fieldUniquely identifies the recordRecords are stored in key sequenceIndexed Sequential FileMaintains the key characteristic of the sequential file: records are organized in sequence based on a key field.Two features are added: an index to the file to support random access, and an overflow file. Indexed FileUses multiple indexes for different key fieldsMay contain an exhaustive index that contains one entry for every record in the main fileMay contain a partial indexWhen a new record is added to the main file, all of the index files must be updated.File OrganizationAccess directly any block of a known address.The Direct or Hashed FileDirectly access a block at a known addressKey field required for each recordPerformanceRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemContentsContains information about filesAttributesLocationOwnershipDirectory itself is a file owned by the operating systemProvides mapping between file names and the files themselvesDirectory Elements: Basic InformationFile NameName as chosen by creator (user or program).Must be unique within a specific directory.File typeFile OrganisationFor systems that support different organizationsDirectory Elements: Address InformationVolumeIndicates device on which file is storedStarting AddressSize Used Current size of the file in bytes, words, or blocksSize Allocated The maximum size of the fileDirectory Elements: Access Control InformationOwner The owner may be able to grant/deny access to other users and to change these privileges.Access InformationMay include the user’s name and password for each authorized user.Permitted Actions Controls reading, writing, executing, transmitting over a networkDirectory Elements: Usage InformationDate CreatedIdentity of Creator Date Last Read AccessIdentity of Last ReaderDate Last ModifiedIdentity of Last ModifierDate of Last BackupCurrent Usage Current activity, locks, etcSimple Structure for a DirectoryThe method for storing the previous information varies widely between systemsSimplest is a list of entries, one for each fileSequential file with the name of the file serving as the keyProvides no help in organizing the filesForces user to be careful not to use the same name for two different filesOperations Performed on a DirectoryA directory system should support a number of operations including:SearchCreate filesDeleting filesListing directoryUpdating directoryTwo-Level Scheme for a DirectoryOne directory for each user and a master directoryMaster directory contains entry for each userProvides address and access control informationEach user directory is a simple list of files for that userDoes not provide structure for collections of filesHierarchical, or Tree-Structured DirectoryMaster directory with user directories underneath itEach user directory may have subdirectories and files as entriesNamingUsers need to be able to refer to a file by nameFiles need to be named uniquely, but users may not be aware of all filenames on a systemThe tree structure allows users to find a file by following the directory pathDuplicate filenames are possible if they have different pathnamesExample of Tree-Structured DirectoryWorking DirectoryStating the full pathname and filename is awkward and tediousUsually an interactive user or process is associated with a current or working directoryAll file names are referenced as being relative to the working directory unless an explicit full pathname is usedRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemFile SharingIn multiuser system, allow files to be shared among usersTwo issuesAccess rightsManagement of simultaneous accessAccess RightsA wide variety of access rights have been used by various systemsoften as a hierarchy where one right implies previousNoneUser may not even know of the files existenceKnowledgeUser can only determine that the file exists and who its owner isAccess Rights contExecutionThe user can load and execute a program but cannot copy itReadingThe user can read the file for any purpose, including copying and executionAppendingThe user can add data to the file but cannot modify or delete any of the file’s contentsAccess Rights contUpdatingThe user can modify, delete, and add to the file’s data. Changing protectionUser can change access rights granted to other usersDeletionUser can delete the fileUser ClassesOwnerUsually the files creator, usually has full rightsSpecific UsersRights may be explicitly granted to specific usersUser GroupsA set of users identified as a groupAlleveryoneSimultaneous AccessUser may lock entire file when it is to be updatedUser may lock the individual records during the updateMutual exclusion and deadlock are issues for shared accessRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemBlocks and recordsRecords are the logical unit of access of a structured fileBut blocks are the unit for I/O with secondary storageThree approaches are commonFixed length blockingVariable length spanned blockingVariable-length unspanned blockingFixed BlockingFixed-length records are used, and an integral number of records are stored in a block. Unused space at the end of a block is internal fragmentationFixed BlockingVariable Length Spanned BlockingVariable-length records are used and are packed into blocks with no unused space.Some records may span multiple blocksContinuation is indicated by a pointer to the successor blockVariable Blocking: SpannedVariable-length unspanned blockingUses variable length records without spanningWasted space in most blocks because of the inability to use the remainder of a block if the next record is larger than the remaining unused space.Variable Blocking: UnspannedRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemSecondary Storage ManagementThe Operating System is responsible for allocating blocks to filesTwo related issuesSpace must be allocated to filesMust keep track of the space available for allocationFile allocation issuesWhen a file is created – is the maximum space allocated at once?Space is added to a file in contiguous ‘portions’What size should be the ‘portion’?What data structure should be used to keep track of the file portions?Preallocation vs Dynamic AllocationNeed the maximum size for the file at the time of creationDifficult to reliably estimate the maximum potential size of the fileTend to overestimated file size so as not to run out of spacePortion sizeTwo extremes:Portion large enough to hold entire file is allocatedAllocate space one block at a timeTrade-off between efficiency from the point of view of a single file, or the overall system efficiencyFile Allocation MethodThree methods are in common use: contiguous, chained, and indexed.Contiguous AllocationSingle set of blocks is allocated to a file at the time of creationOnly a single entry in the file allocation tableStarting block and length of the fileExternal fragmentation will occurNeed to perform compactionContiguous File AllocationExternal fragmentationChained AllocationAllocation on basis of individual blockEach block contains a pointer to the next block in the chainOnly single entry in the file allocation tableStarting block and length of fileNo external fragmentationBest for sequential filesChained AllocationChained Allocation ConsolidationIndexed AllocationFile allocation table contains a separate one-level index for each fileThe index has one entry for each portion allocated to the fileThe file allocation table contains block number for the indexIndexed Allocation MethodAllocation may be eitherFixed size blocks or Variable sized blocksAllocating by blocks eliminates external fragmentationVariable sized blocks improves localityBoth cases require occasional consolidationIndexed allocation with Block PortionsIndexed Allocation with Variable Length PortionsFree Space ManagementJust as allocated space must be managed, so must the unallocated spaceTo perform file allocation, we need to know which blocks are available.We need a disk allocation table in addition to a file allocation tableBit TablesThis method uses a vector containing one bit for each block on the disk. Each entry of a 0 corresponds to a free block, and each 1 corresponds to a block in use.Advantages:Works well with any file allocation methodSmall as possibleChained Free Portions The free portions may be chained together by using a pointer and length value in each free portion. Negligible space overheadSuited to all file allocation methodsLeads to fragmentationIndexingtreats free space as a file and uses an index table as it would for file allocationFor efficiency, the index should be on the basis of variable-size portions rather than blocks. Thus, there is one entry in the table for every free portion on the disk. This approach provides efficient support for all of the file allocation methods.Free Block List Each block is assigned a number sequentially the list of the numbers of all free blocks is maintained in a reserved portion of the disk. VolumesA collection of addressable sectors in secondary memory that an OS or application can use for data storage.The sectors in a volume need not be consecutive on a physical storage device;instead they need only appear that way to the OS or application. A volume may be the result of assembling and merging smaller volumes.RoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemAccess ControlBy successfully logging on to a system, the user is identifiedThe OS can then enforce rulesGranting access to files and applications (or denying)The OS needs a rule-set to enforceAccess MatrixOne such rule set is an Access MatrixAccess Control ListsA matrix may be decomposed by columnsGiving an Access Control List (ACL) for each file.Capability ListsDecomposition by rows yields capability lists (or ticket)specifies authorized objects and operations for a user.RoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemUNIX File ManagementSix types of filesRegular, or ordinaryDirectorySpecialNamed pipesLinksSymbolic linksInodesIndex nodeControl structure that contains key information for a particular file.Several filenames may be associated with a single inodeBut an active inode is associated with only one file, andEach file is controlled by only one inodeFree BSD Inodes include:The type and access mode of the fileThe file’s owner and group-access identifiersCreation time, last read/write timeFile sizeSequence of block pointersNumber of blocks and Number of directory entriesBlocksize of the data blocksKernel and user setable flagsGeneration number for the fileSize of Extended attribute informationZero or more extended attribute entriesFreeBSD Inode and File StructureFile AllocationFile allocation is done on a block basis.Allocation is dynamicBlocks may not be contiguousIndex method keeps track of filesPart of index stored in the file inode.Inode includes a number of direct pointersAnd three indirect pointersUNIX Directories and InodesDirectories are files containing: a list of filenames Pointers to inodesUNIX File Access ControlFiles are associated with permissions for:User IDGroup IDEveryone elseUNIX File Access ControlRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemLinux Virtual File SystemUniform file system interface to user processesRepresents any conceivable file system’s general feature and behaviorAssumes files are objects that share basic properties regardless of the target file systemKey ingredients of VFS StrategyA user process issues a file system call (e.g., read) using the VFS file scheme.The VFS converts this into an internal file system call The new call is passed to a mapping function for a specific file systemThe role of VFS within the KernelPrimary Objects in VFSSuperblock objecta specific mounted file systemInode objecta specific fileDentry objecta specific directory entryFile objectan open file associated with a processRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingSecondary Storage ManagementFile System SecurityUnix File ManagementLinux Virtual File SystemWindows File SystemWindows File SystemKey features of NTFSRecoverabilitySecurityLarge disks and large filesMultiple data streamsJournalingCompression and EncryptionNTFS Volume and File StructureSectorThe smallest physical storage unit on the diskAlmost always 512 bytesClusterOne or more contiguous sectorsVolumeLogical partition on a diskEfficient with Large FilesVolume SizeSectors per ClusterCluster Size512Mbyte1512bytes512Mbyte – 1 Gbyte21K1–2 Gbyte42K2–4 Gbyte84K4–8 Gbyte168K8–16 Gbyte3216K16–32 Gbyte6432K>32Gbyte12864KNTFS Volume LayoutEvery element on a volume is a file, and every file consists of a collection of attributes. Even the data contents of a file is treated as an attribute.Windows NTFS Components