and Design Chapter 12 Principles File Management

1 Chapter 12 File Management Eighth Edition By William Stallings Operating Systems: Internals and Design Principles Files data collections created by users The File System is one of the most important parts of the OS to a user Desirable properties of files: Long-term existence files are stored on disk or other secondary storage and do not disappear when a user logs off Sharable between processes files have names and can have associated access permissions that permit controlled sharing Structure files can be organized into hierarchical or more complex structure to reflect the relationships among files File Systems Provide a means to store data organized as files as well as a collection of functions that can be performed on files Maintain a set of attributes associated with the file Typical operations include: Create Delete Open Close Read Write File Structure Four terms are commonly used when discussing files.

2 Field Record File Database Structure Terms Field basic element of data contains a single value fixed or variable length File collection of related fields that can be treated as a unit by some application program fixed or variable length Record Database collection of similar records treated as a single entity may be referenced by name access control restrictions usually apply at the file level collection of related data relationships among elements of data are explicit designed for use by a number of different applications consists of one or more types of files File Management System Objectives Meet the data Management needs of the user Guarantee that the data in the file are valid Optimize performance Provide I/O support for a variety of storage device types Minimize the potential for lost or destroyed data Provide a standardized set of I/O interface routines to user processes Provide I/O support for multiple users in the case of multiple-user systems Minimal User Requirements Each user.

3 1 should be able to create, delete, read, write and modify files 2 may have controlled access to other users files 3 may control what type of accesses are allowed to the files 4 should be able to restructure the files in a form appropriate to the problem 5 should be able to move data between files 6 should be able to back up and recover files in case of damage 7 should be able to access his or her files by name rather than by numeric identifier IndexedSequentialPileSequentialLogical I/OBasic I/O SupervisorFigure File System Software ArchitectureBasic File SystemDisk Device DriverTape Device DriverIndexedHashedUser ProgramDevice Drivers Lowest level Communicates directly with peripheral devices Responsible for starting I/O operations on a device Processes the completion of an I/O request Considered to be part of the operating system Basic File System Also referred to as the physical I/O level Primary interface with the

4 Environment outside the computer system Deals with blocks of data that are exchanged with disk or tape systems Concerned with the placement of blocks on the secondary storage device Concerned with buffering blocks in main memory Considered part of the operating system Basic I/O Supervisor Responsible for all file I/O initiation and termination Control structures that deal with device I/O, scheduling, and file status are maintained Selects the device on which I/O is to be performed Concerned with scheduling disk and tape accesses to optimize performance I/O buffers are assigned and secondary memory is allocated at this level Part of the operating system Logical I/O Enables users and applications to access records Provides general-purpose record I/O capability Maintains basic data about file Access Method Level of the file system closest to the user Provides a standard interface between applications and the file systems and devices that hold the data Different access methods reflect different file structures and different ways of accessing and processing the data DirectorymanagementAccessmethodBlockingD iskschedulingFileallocationFileStructure RecordsFile Management concernsFigure Elements of File ManagementOperating system concernsPhysical blocksin main memorybuffersPhysical blocksin

5 Secondarystorage (disk)User accesscontrolUser & programcomandsOperation,File nameFree storagemanagementFilemanipulationfunctio nsI/O File Organization and Access File organization is the logical structuring of the records as determined by the way in which they are accessed In choosing a file organization, several criteria are important: short access time ease of update economy of storage simple maintenance reliability Priority of criteria depends on the application that will use the file File Organization Types Five of the common file organizations are: The pile The sequential file The indexed sequential file The indexed file The direct, or hashed, file (a) Pile File(c) Indexed Sequential File(d) Indexed FileFigure Common File OrganizationsVariable-length recordsVariable set of fieldsChronological order(b) Sequential FileFixed-length recordsFixed set of fields in fixed orderSequential order based on key fieldMain FileOverflowFileIndexlevelsExhaustiveind exExhaustiveindexPartialindexPrimary File(variable-length records)Index12nThe Pile Least complicated form of file organization data are collected in the order they arrive Each record consists of one burst of data Purpose is simply to accumulate the mass of data and save it Record access is by exhaustive search (a) Pile File(c) Indexed Sequential File(d) Indexed FileFigure Common File OrganizationsVariable-length recordsVariable set of fieldsChronological order(b)

6 Sequential FileFixed-length recordsFixed set of fields in fixed orderSequential order based on key fieldMain FileOverflowFileIndexlevelsExhaustiveind exExhaustiveindexPartialindexPrimary File(variable-length records)Index12nThe Sequential File Most common form of file structure A fixed format is used for records Key field uniquely identifies the record Typically used in batch applications Only organization that is easily stored on tape as well as disk (a) Pile File(c) Indexed Sequential File(d) Indexed FileFigure Common File OrganizationsVariable-length recordsVariable set of fieldsChronological order(b) Sequential FileFixed-length recordsFixed set of fields in fixed orderSequential order based on key fieldMain FileOverflowFileIndexlevelsExhaustiveind exExhaustiveindexPartialindexPrimary File(variable-length records)Index12nIndexed Sequential File Adds an index to the file to support random access Adds an overflow file Greatly reduces the time required to access a single record Multiple levels of indexing can be used to provide greater efficiency in access (a) Pile File(c) Indexed Sequential File(d) Indexed FileFigure Common File OrganizationsVariable-length recordsVariable set of fieldsChronological order(b) Sequential FileFixed-length recordsFixed set of fields in fixed orderSequential order based on key fieldMain FileOverflowFileIndexlevelsExhaustiveind exExhaustiveindexPartialindexPrimary File(variable-length records)

7 Index12nIndexed File Records are accessed only through their indexes Variable-length records can be employed Exhaustive index contains one entry for every record in the main file Partial index contains entries to records where the field of interest exists Used mostly in applications where timeliness of information is critical Examples would be airline reservation systems and inventory control systems (a) Pile File(c) Indexed Sequential File(d) Indexed FileFigure Common File OrganizationsVariable-length recordsVariable set of fieldsChronological order(b) Sequential FileFixed-length recordsFixed set of fields in fixed orderSequential order based on key fieldMain FileOverflowFileIndexlevelsExhaustiveind exExhaustiveindexPartialindexPrimary File(variable-length records)Index12nDirect or Hashed File Access directly any block of a known address Makes use of hashing on the key value Often used where: very rapid access is required fixed-length records are used records are always accessed one at a time Examples are: directories pricing tables schedules name lists B-Trees A balanced tree structure with all branches of equal length Standard method of organizing indexes for databases Commonly used in OS file systems Provides for efficient searching, adding, and deleting of items Key1 Subtree1 Subtree2 Subtree3 Subtreek 1 SubtreekFigure A B-tree Node with k ChildrenKey2 Keyk 1B-Tree Characteristics every node has at most 2d 1 keys and 2d children or, equivalently, 2d pointers every node, except for the root, has at least d 1 keys and d pointers, as a result, each internal node, except the root, is at least half full and has at least d children the root has at least 1 key and 2 children all leaves appear on the same level and contain no information.

8 This is a logical construct to terminate the tree; the actual implementation may differ. a nonleaf node with k pointers contains k 1 keys A B-tree is characterized by its minimum degree d and satisfies the following properties: Figure Inserting Nodes into a B-tree(b) Key = 90 inserted. This is a simple insertion into a node.(c) Key = 45 inserted. This requires splitting a node into two parts and promoting one key to the root node.(d) Key = 84 inserted. This requires splitting a node into two parts and promoting one key to the root nodeThis then requires the root node to be split and a new root created.(a) B-tree of minimum degree d = Table Information Elements of a File Directory Basic Information File Name Name as chosen by creator (user or program). Must be unique within a specific directory. File Type For example: text, binary, load module, etc. File Organization For systems that support different organizations Address Information Volume Indicates device on which file is stored Starting Address Starting physical address on secondary storage ( , cylinder, track, and block number on disk) Size Used Current size of the file in bytes, words, or blocks Size Allocated The maximum size of the file Access Control Information Owner User who is assigned control of this file.

9 The owner may be able to grant/deny access to other users and to change these privileges. Access Information A simple version of this element would include the user's name and password for each authorized user. Permitted Actions Controls reading, writing, executing, transmitting over a network Usage Information Date Created When file was first placed in directory Identity of Creator Usually but not necessarily the current owner Date Last Read Access Date of the last time a record was read Identity of Last Reader User who did the reading Date Last Modified Date of the last update, insertion, or deletion Identity of Last Modifier User who did the modifying Date of Last Backup Date of the last time the file was backed up on another storage medium Current Usage Information about current activity on the file, such as process or processes that have the file open, whether it is locked by a process, and whether the file has been updated in main memory but not yet on disk (Table can be found on page 537 in textbook)

10 Operations Performed on a Directory To understand the requirements for a file structure, it is helpful to consider the types of operations that may be performed on the directory: Search Create files Delete files List directory Update directory Two-Level Scheme There is one directory for each user and a master directory Master directory has an entry for each user directory providing address and access control information Each user directory is a simple list of the files of that user Names must be unique only within the collection of files of a single user File system can easily enforce access restriction on directories Master DirectorySubirectorySubirectoryFileFigur e Tree-Structured DirectorySubirectorySubirectoryFileSubir ectoryFileFileSystemMaster DirectoryUser_AUser_BUser_CDirectory"Use r_C"Directory"User_A"Directory "User_B"DrawWordDirectory "Unit_A"ABCD irectory "Word"Unit_ADirectory "Draw"ABCFile"ABC"Pathname: /User_B/Word/Unit_A/ABCP athname.