Hệ điều hành - Chapter 12: File management

Chapter 12File ManagementOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingFilesFiles are the central element to most applicationsfile as an input to applicationsfile as an output for long-term storage and for later access Desirable properties of files:Long-term existenceControlled sharing between processes Structure that is convenient for particular applicationsFile StructureFields and RecordsFieldsBasic element of data e.g., student’s last nameContains a single valueCharacterized by its length and data typeRecordsCollection of related fields e.g., a student recordTreated as a unitFile StructureFile and DatabaseFileCollection of similar recordsTreated as a single entity and may be referenced by nameAccess control restrictions usually apply at the file levelDatabaseCollection of related dataExplicit relationships exist among elementsConsists of one or more filesA Big PictureHow to identify and locate a selected file?How to enforce user access control in shared systems? How to organize records as a sequence of blocks for I/O?individual block I/O requests must be scheduled for optimizing performanceHow to organize records in a file and access a particular record in a file?RoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingFile OrganizationThe basic operations that a user or application may perform on a file are performed at the record levelThe file is viewed as having some structure that organizes the recordsFile organization refers to the logical structuring of recordsDetermined by the way in which files are accessed (access method)Criteria for File OrganizationImportant criteria include:Short access timeEase of updateEconomy of storageSimple maintenanceReliabilityCriteria for File OrganizationPriority will differ depending on the useFor batch mode file processing, rapid access for retrieval of a single record is of minimal concernThese criteria may conflictUse of indexes (conflict with economy of storage) can be a primary means of increasing the speed of access to dataThe PileData are collected in the order they arriveNo structurePurpose is to accumulate a mass of data and save itRecords may have different fieldsfield should be self-describing (field name + value)field length should be known (delimiters, subfield or default for a field type)The PileRecord access is by exhaustive searchUsed when data are collected and stored prior to processing or data are not easy to organize Uses space well when data vary in size and structure Adequate for exhaustive searches Easy to update Unsuitable for most applicationsThe Sequential FileFixed format used for recordsRecords are of the same lengthsame number of fixed-length fields in a particular orderOnly the values of fields need to be stored Field name and length are attributes of the file structureThe Sequential FileKey fieldUniquely identifies the recordRecords are stored in key sequence Optimal for batch applications if they involve the processing of all the records Easily stored on tape and disk Poor performance for interactive applicationsconsiderable processing and delay due to the sequential search of the file for a key matchIndexed Sequential FileAn index is added to support random accessAn index record contains a key field and a pointer into the main fileThe index is a sequential fileFor searchingSearch the index to find the highest key value that is equal to or precedes the desired key valueSearch continues in the main file at the location indicated by the pointerIndexed Sequential FileExampleConsider searching a particular key value in a sequential file with 1 million recordswithout indexrequires on average one-half million record accesseswith an index containing 1000 entries with the keys in the index evenly distributed over the main filerequires on average 500 accesses to the index file + 500 accesses to the main fileAn overflow file is addedA new record is added to the overflow file and is located by following a pointer from its predecessor record The indexed sequential file is occasionally merged with the overflow file in batch modeGreatly reduces the time required to access a single record, without sacrificing the sequential nature.Indexed Sequential FileIndexed FileRecords are accessed only through their indexesno restriction on the placement of recordsallows variable-length records Uses multiple indexes for different key fieldsAn exhaustive index contains one entry for every record in the main fileA partial index contains entries to records where the field of interest existsIndexed FileWhen a new record is added to the main file, all of the index files must be updated.Used mostly in applications where timeliness of information is critical and data are rarely processed exhaustivelyexamples: airline reservation systems and inventory control systemsRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingFile DirectoryContains information about filesAttributesLocationOwnershipDirectory itself is a file owned by the operating systemDirectory ElementsBasic InformationFile name: must be uniqueFile type: e.g., text, binary File organizationAddress InformationVolume: device on which file is storedStarting address: e.g., cylinder, track on diskSize used: in bytes, words or blocksSize allocated: maximum size of the fileDirectory ElementsAccess Control InformationOwner: able to grant/deny access to other users and to change these privilegesAccess information: e.g., user’s name and password for each authorized userPermitted actions: controls reading, writing, executing, transmitting over a networkUsage InformationDate Created, Identity of Creator, Date Last Read Access, Identity of Last Reader, Date Last ModifiedHierarchical, or Tree-Structured DirectoryMaster directory with user directories underneath itEach user directory may have subdirectories and files as entriesEach directory and subdirectory can be organized as a sequential fileHierarchical, or Tree-Structured Directory Easily enforce access restriction on directories. Easily organize collections of files.  Minimize the difficulty in assigning unique names.NamingThe tree structure allows users to find a file by following a path from the root or master directory down various branches until the file is reachedThe series of directory names, culminating in the file name itself, constitutes a pathname for the fileDuplicate filenames are possible if they have different pathnames NamingUsually an interactive user or a process is associated with a current or working directoryFiles are referenced relative to the working directory unless an explicit full pathname is usedRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingFile SharingIn multiuser system, there is almost always a requirement for allowing files to be shared among a number of usersTwo issuesAccess rightsManagement of simultaneous accessAccess RightsA wide variety of access rights have been used by various systemsoften as a hierarchy, with each right implying those that precede it. NoneUser may not know the existence of file by not allowing to read the user directory that includes this fileKnowledgeUser can only determine that the file exists and who its owner isAccess Rights contExecutionThe user can load and execute a program but cannot copy it, e.g., proprietary programsReadingThe 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 ClassesAccess can be provided to different classes of usersOwner: usually the files creator, has full rights and may grant rights to othersSpecific users: individual users who are designated by user IDUser groups: a set of users identified as a groupAll: all users who have access to this systemSimultaneous AccessWhen access is granted to append or update a file to more than one user, the OS or file management system must enforce disciplineUser may lock the entire file or individual records during updateMutual exclusion and deadlock are issues for shared access, ref. readers/writers problemRoadmapOverviewFile organisation and AccessFile DirectoriesFile SharingRecord BlockingBlocks and recordsRecords are the logical unit of access of a structured fileBlocks are the unit for I/O with secondary storageFor I/O to be performed, records must be organized as blocks.Three methods of blocking 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 blockUnused space at the end of a block is internal fragmentationCommon for sequential files with fixed-length recordsFixed BlockingVariable Length Spanned BlockingVariable-length records are used and are packed into blocks with no unused spaceSome records may span multiple blocksContinuation is indicated by a pointer to the successor block Efficient for storage and does not limit the size of recordsVariable Blocking: Spanned Difficult to implement Records that span two blocks require two I/O operationsVariable-length unspanned blockingUses variable length records without spanning Wasted 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 Limits record size to the size of a blockVariable Blocking: UnspannedRevisit the Big PictureDescribes the location of all files plus their attributesOnly authorized users are allowed to access particular files in particular waysRecords must be organized as a sequence of blocks for output and unblocked after inputindividual block I/O requests must be scheduled for optimizing performanceUser views the file as having some structure that organizes the records; different access methods reflect different file structures