What communicate directly with peripheral devices or their controllers or channels

12.1 - Overview

File and File Systems

Long-term existence - files are stored on disk or other secondary storage 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 - depending on the file system, a file can have an internal structure that is convenient for particular applications. In addition, files can be organized into hierarhical or more complex structure to reflect the relationships among files

Create - a new file is defined and positioned within the structure of files

Delete - a file is removed from the file structure and destroyed

Open - an existing file is declared to be "op

Close - the file is closed with respect to a process, so that the process no longer may perform functions on that file

Read - a process reads all or a portion of the data in a file

Write - A process updates a file, either by adding new data that expands the size of the file or by changing the values of existing data items in the file

File Structure

Field - the basic element of data; a single value characterized by it's length and data type

Record - a collection of related fields that can be treated as a unit by some application program

• e.g. an employee record can contain name, position, date of hire etc.

File - a collection of similar records; where access control restriction is usually applied

Database - a collection of related data where the relationships that exists among elements of data are explicit

File Management Systems

• The set of system software that provides services to users and applications in the use of files

Objectives

• To meet data management needs and requirements of the user (storage of data, operations)
• To guarantee the validity of the data (to the extent possible)
• To optimize performance for both the system (overall throughput) and the user (response time)
• To provide I/O support for a variety of storage device types
• To minimize or elimate the potential for lost or destroyed data
• To provide a standaridized set of I/O interface routines to user processes
• To provide I/O support for multiple users, in the case of multiple-user systems

Each user can:

• Create, delete, read, write, modify files
• Controlled access to other users' files
• Control what types of accesses are allowed to the user's files
• Move data between files
• Backup and recover the user's files in case of damage
• Access his/her files by name rather than by numeric identifier

Architecture

Device drivers - communicate directly with peripheral devices or their controller or channels

Basic file system (Physical I/O) - deals with blocks of data that are exchanged with disk or tape systems; the placement of the blocks on the secondary storage

Basic I/O supervisor - responsible for all file I/O initiation and termination

• Device I/O, scheduling, file status
• Part of the OS

Logical I/O - enables users and applications to access records; deals with file records

• The level of the file system closest to the user is often termed the accessed method (interface between application and file systems)

File Management Functions

• Identify and locate the selected files
• Enforce user access control

12.2 - File Organization and Access

• Logical structuring of the records as determined by the way in which they are accessed

The Pile

• Data collected in the order in which they arrives
• Records may contain different fields, or similar fields in different orders
  • Need to be self describing
• No structure, record access by exhaustive search
  • May need to search the entire file
• Used during data collection before the processing stage or when data are not easy to organize
• Unsuited for most applications

The Sequential File

• A fixed format is used for records with the same length
  • Consists of same number of fixed-length fields in a particular order
• Only need to store field value
• Has a key field (usually the first one) which uniquely identifies the record
• Records are stored in key sequence
• Most commonly used
• Good performance in batch applications
• Poor performance for interactive applications that involves queries/updates of individual updates

The Indexed Sequential File

• Records organized in sequence based on a key field
• An index to the file to support random access
• An overflow file similar to the log file used with sequential file but is integrated so that a record in the overflow file is located by following a pointer from its predecessor record
• When a new record is added
  • It gets added to the overflow file
  • The preceding record in the main file is updated to contain a pointer to the new record
  • The sequential file is occasionally merged with the overflow file in batch mode
• Effective processing is limited to that which is based on a single field of the file

The Indexed File

• Employs multiple indexes that may be the subject of search
• Records are accessed only through their indexes

• No restrictions on the placement of records

• The exhaustive index contains one entry for every record in the main file

  • Organized as a sequential file for ease of searching

• The partial index contains entires to records where the field of interest exists

The Direct/Hashed File

• Direct access to any block of a known address
• No sequential ordering
• Makes use of hashing on the key value

12.4 - File Directories

• The way that this information is stored differs widely among different systems

Structure

• Type of operations that can be performed in a directory

  • Search - when a user or application references a file, the directory must be searched to find the entry corresponding to that file
  • Create file - when a new file is created, an entry must be added to the directory
  • Delete file - when a file is deleted, an entry must be removed from the directory
  • List directory - listing of all files owned by that user, plus some attributes of each file (all or a portion of the directory)
  • Update directory - a change in a file attribute may require a change in the corresponding directory entry

• The most widel adopted scheme is a hierarchical or tree-structure

Naming

• Users need to be refer to a file by a symbolic name
• The series of directory names, culminating in the file name itself, constitutes a pathname for the file
• Working directory - the directory associated with an interactive user or a process
  • Files are referenced relative to the working directory

12.5 - File Sharing

Access Rights

• None - the user does not know the existence of the file; the user may read the user directory that includes this file
• Knowledge - the user can determine that the file exists and who the owner is
• Execution - the user can load and execute the program but cannot copy it
• Reading - the user can read the file (includes copying and execution); some system can make distinctions between reading and copying
• Appending - the user can add data to the file (often only at the end) but cannot modify or delete any of the file's contents
• Updating - the user can modify, delete, and add to the file's data
• Changing protection - the user can change access rights granted to the other users; typically held only by the owner of the file
• Deletion - the user can delete the file from the file system

Different classes of users:

• Specific user - individual users with an unique user ID
• User groups - a set of users who are not individually defined
• All - all users who have access to this system (public files)

12.6 - Record Blocking

• Blocks are the unit of I/O with secondary storage
• For I/O to be performed record must be organzied as blocks

Fixed blocking - fixed-length records are used, and an integral number of records are stored in a block

• There may be unused space at the end of each block (internal fragmentation)

Variable-length spanned blocking - variable-length records are used and are packed into blocks with no unsed space

• Records that spans multiple blocks have pointers to the successor blocks

Variable-length unspanned blocking - variable-length records are used without spanning

• Wasted space in most blocks with the inability to use the reamainder of a block if the next record is larger than the remaining unused space

12.7 - Secondary Storage Management

• The file management system is responsible for allocating blocks to files

File Allocation

Preallocation vs. Dynamic Allocation

• Preallocation requires that the maximum size of a file be declared at the time of the file creation request
  • May be hard to estimate in many applications
• Dynamic allocation allocates space to a file in portion as needed

Portion size

• A portion is a contiguous set of allocated blocks
• There are several tradeoffs
  • Contiguity of space increases performance
  • A large number of small portions increase the size of tables needed to manage the allocation information
  • Fixed-size portions simplifies reallocation of space
  • Vairable-size or small fixed-size portions minimizes waste of unused storage due to overallocation
• Variable, large contiguous portions
  • Better performance
  • Avoids waste
  • Small allocation tables
  • Space is hard to reuse
• Blocks (small fixed size portions)
  • Greater flexibility
  • Large allocation tables
  • Contiguity abandoned
  • Blocks are allocated as needed

Methods to deal with fragmentation

• First fit
• Best fit
• Nearest fit - choose the unsued group of sufficient size that is closest to the previous allocation for the file to increase locality

File Allocation Methods:

Contiguous allocation

• A single contiguous set of blocks is allocated to a file at the time of file creation
• A preallocation strategy using variable-size portions
• File allocation table needs just a single entry for each file
• Good I/O performance for sequential processing
• Easy to retrieve a single block
• Need compaction algorithm to free up additonal space on the disk

Chained allocation

• Allocation on an individual block basis
• Each block contains a pointer to the next block in the chain
• File allocation table needs just a single entry for each file
• No external fragmentation
• Good for sequential processing
• No principle of locality
  • Some systems need to periodically consolidate files (cluster files adjacent in the chain)

Indexed allocation

• File allocation table contains a spearate one-level index for each file
  • The index has one entry for each portion allocated to the file
• Allocation may feature fixed-blocks or variable-size portions (fixed blocks in the diagram)
  • Blocks eliminates external fragmentation, variable-sized portions improves locality
• Consolidation may be done from time to time (reduces the size of index with variable-size portions)
• Supports both sequential and direct access to the file
  • Most popular

Free Space Management

• Requires a disk allocation table to keep track of what blocks on the disk are available

Bit tables

• A vector containing one bt for each block on the disk
  • 0 corresponds to free block, 1 correspond to a block in use
• Relatively easy to find one or contiguous group of free blocks
• Amount of memory required for a block bitmap

disk size in bytes8×file system  block size\frac{disk~{}size~{}in~{}bytes}{8\times file~{}system~{}block~{}size}

• Exhaustive search of the table can slow system performance
• Most systems that uses bit tables has auxiliary data structures that summarize the contents of subranges in the table
  • The system can scan the summary table to find an appropriate subrange and then search that subrange

Chained free portions

• Free portions chained together by a pointer and length value in each free portion
• No need for disk allocation table
• Suited to all of the file allocation methods
  • Choose the free block at the head of the chain for blocks
  • Can use first-fit for variable-length portion
• Disk may become very fragmented after some use
• Slows file creation since you need to read the block first to recover the pointer to the new first free block before writing data

Indexing

• Treats free space a a file and uses an index table
• Should be based on variable-size portion for efficiency
• One entry in the table for every free portion on the disk
• Provides efficient support for all of the file allocation methods

Free block list

• Each block is assigned a number sequentially and the list of numbers of all free blocks is maintained in a reserved portion of the disk
• Either 24 or 32 bits will be needed to store a single block number
  • The size of the free block list is 24 or 32 times the size of the corresponding bit table and must be stored on disk rather than main memory

Volumes

• A collection of addressable sectors in secondary memory that an OS or application can use for data storage
• Sectors in a volume don't need to be contiguous physically but need to appear that way to the OS or application
• A volume can be a disk, or partitions gained by dividing a disk

Reliability

• To prevent inconsistencies between the disk allocation table and file allocation table on disk and in memory, the following steps can be taken

• Lock the disk allocation table on disk which prevents another user from causing alterations to the table until this allocation is completed

• Search the disk allocation table for available space
• Allocate space, update the disk allocation table, and update the disk
• Update the file allocation table and update the disk (writing the table back onto disk)

• Unlock the disk allocation table

• Prevent errors but impact performance when small portions are allocated frequently

  • A batch storage allocation scheme could be used