Operating

Systems:
Internals
and
Design Chapter 12
Principles File Management
Seventh Edition
By William Stallings
 Operating Systems:
Internals and Design Principles
If there is one singular characteristic that makes squirrels unique
among small mammals it is their natural instinct to hoard food.
Squirrels have developed sophisticated capabilities in their hoarding.
Different types of food are stored in different ways to maintain quality.
Mushrooms, for instance, are usually dried before storing. This is done
by impaling them on branches or leaving them in the forks of trees for
later retrieval. Pine cones, on the other hand, are often harvested while
green and cached in damp conditions that keep seeds from ripening.
Gray squirrels usually strip outer husks from walnuts before storing.

— SQUIRRELS: A WILDLIFE HANDBOOK,

Kim Long
 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:

Field Record File Database

 Structure Terms
Field Record
 collection of related fields that can
 basic element of data
be treated as a unit by some
 contains a single value application program
 length and data type
 fixed or variable length
Database
 collection of related data File
 relationships among elements  collection of similar records
of data are explicit
 treated as a single entity
 designed for use by a number
of different applications
 may be referenced by name
 consists of one or more types
 access control restrictions usually
of files apply at the file level
 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:
• should be able to create, delete, read, write and modify files
1

• may have controlled access to other users’ files

2

• may control what type of accesses are allowed to the files

3

• should be able to restructure the files in a form appropriate to the problem

4

• should be able to move data between files

5

• should be able to back up and recover files in case of damage

6

• should be able to access his or her files by name rather than by numeric identifier
7
Typical Software Organization
 Device 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 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

Provides
general-
Enables users purpose record
and I/O capability Maintains
applications to basic data
access records 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
Elements of File Management
 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
The pile

The
The direct, or sequential
hashed, file file

Five of the common

file organizations
are:
The indexed
The
sequential
indexed
file
file
Grades of Performance
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
 Table 12.2 Information Elements of a File Directory

File
Directory
Information
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:

Create Delete List Update

Search
files files directory directory
Two-Level Scheme
Master directory has
There is one
an entry for each user Each user directory
directory for each
directory providing is a simple list of the
user and a master
address and access files of that user
directory
control information

Names must be unique File system can easily

only within the enforce access
collection of files of a restriction on
single user directories
Figure 12.4

Tree-Structured

Directory

 Master directory
with user
directories
underneath it

 Each user
directory may
have
subdirectories and
files as entries
Figure 12.7
Example of
Tree-Structured
Directory
 File Sharing

Two issues arise

when allowing files
to be shared among a
number of users:

management of
access rights simultaneous
access
 Access Rights
 None  Appending
 the user would not be allowed to
read the user directory that includes  the user can add data to the file
the file but cannot modify or delete any
of the file’s contents
 Knowledge
 the user can determine that the file  Updating
exists and who its owner is and can
then petition the owner for
 the user can modify, delete, and
additional access rights add to the file’s data
 Execution  Changing protection
 the user can load and execute a  the user can change the access
program but cannot copy it rights granted to other users
 Reading
 Deletion
 the user can read the file for any
purpose, including copying and  the user can delete the file from
execution the file system
 User Access Rights
Specific User
Owner All
Users Groups
usually the
initial creator of all users who
the file have access to
this system
individual a set of users
users who are who are not
has full rights
designated by individually
user ID defined
these are public
may grant files
rights to others
 Record Blocking
1) Fixed-Length Blocking – fixed-
 Blocks are the unit of I/O length records are used, and an
with secondary storage integral number of records are
 for I/O to be stored in a block
performed records Internal fragmentation – unused
must be organized as space at the end of each block
blocks
2) Variable-Length Spanned Blocking
– variable-length records are used and
are packed into blocks with no unused
space

 Given the size of a block, 3) Variable-Length Unspanned

three methods of blocking Blocking – variable-length records
can be used: are used, but spanning is not
employed
Fixed Blocking
Variable Blocking: Spanned
Variable Blocking: Unspanned
 File Allocation
 On secondary storage, a file consists of a collection of blocks
 The operating system or file management system is responsible for
allocating blocks to files

 The approach taken for file allocation may influence the approach taken
for free space management

 Space is allocated to a file as one or more portions (contiguous set of

allocated blocks)

 File allocation table (FAT)

 data structure used to keep track of the portions assigned to a file
 Preallocation vs
Dynamic Allocation
 A preallocation policy requires that the maximum size of a file be
declared at the time of the file creation request
 For many applications it is difficult to estimate reliably the maximum
potential size of the file
 tends to be wasteful because users and application programmers tend to
overestimate size

 Dynamic allocation allocates space to a file in portions as needed

 Portion Size
 In choosing a portion size there is a trade-off between efficiency from
the point of view of a single file versus overall system efficiency
 Items to be considered:
1) contiguity of space increases performance, especially for
Retrieve_Next operations, and greatly for transactions running in
a transaction-oriented operating system
2) having a large number of small portions increases the size of
tables needed to manage the allocation information
3) having fixed-size portions simplifies the reallocation of space
4) having variable-size or small fixed-size portions minimizes waste
of unused storage due to overallocation
 Alternatives
 Two major alternatives:

Variable, large contiguous Blocks

portions • small fixed portions provide
• provides better performance greater flexibility
• the variable size avoids waste • they may require large tables or
• the file allocation tables are small complex structures for their
allocation
• contiguity has been abandoned as
a primary goal
• blocks are allocated as needed
Table 12.3
File Allocation Methods
Contiguous File Allocation
A single
contiguous set of
blocks is allocated
to a file at the time
of file creation

Preallocation
strategy using
variable-size
portions

Is the best from the

point of view of the
individual
sequential file
12.9
After Compaction

Figure 12.10 Contiguous File Allocation (After Compaction)

Chained
Allocation
Allocation is on an
individual block basis

Each block contains a

pointer to the next block in
the chain

The file allocation table

needs just a single entry for
each file

No external fragmentation

to worry about
12.11
Best for sequential files
Chained Allocation After Consolidation

12.12
Indexed Allocation with Block
Portions

12.13
Indexed Allocation with
Variable Length Portions

12.14
 Free Space Management
 Just as allocated space must be managed, so must the unallocated space
 To perform file allocation, it is necessary to know which blocks are
available
 A disk allocation table is needed in addition to a file allocation table
Bit Tables
 This 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 method
• it is as small as possible
 Chained Free Portions
 The free portions may be chained together by using a pointer and length
value in each free portion
 Negligible space overhead because there is no need for a disk allocation
table
 Suited to all file allocation methods

Disadvantages:
• leads to fragmentation
• every time you allocate a block you need to read the
block first to recover the pointer to the new first
free block before writing data to that block
 Indexing
 Treats free space as a file and uses an index table as it would for file
allocation
 For efficiency, the index should be on the basis of variable-size
portions rather than blocks
 This approach provides efficient support for all of the file allocation
methods
Free Block List
Depending on the size of the There are two effective
Each block is assigned a disk, either 24 or 32 bits will techniques for storing a small
number sequentially be needed to store a single part of the free block list in
block number main memory:

the size of the free block the list can be treated as a

the list of the numbers of
list is 24 or 32 times the push-down stack with the
all free blocks is
size of the corresponding first few thousand elements
maintained in a reserved
bit table and must be stored of the stack kept in main
portion of the disk
on disk memory

the list can be treated as a

FIFO queue, with a few
thousand entries from both
the head and the tail of the
queue in main memory
 UNIX File  In the UNIX file system, six types
of files are distinguished:
Management
Regular, or ordinary
• contains arbitrary data in zero or more data blocks

Directory
• contains a list of file names plus pointers to associated inodes

Special
• contains no data but provides a mechanism to map physical devices to file names

Named pipes
• an interprocess communications facility

Links
• an alternative file name for an existing file

Symbolic links
• a data file that contains the name of the file it is linked to
 Inodes
 All types of UNIX files are administered by the OS by means of inodes
 An inode (index node) is a control structure that contains the key
information needed by the operating system for a particular file
 Several file names may be associated with a single inode
 an active inode is associated with exactly one file
 each file is controlled by exactly one inode
FreeBSD Inode and File Structure
 File Allocation
 File allocation is done on a block basis
 Allocation is dynamic, as needed, rather than using preallocation
 An indexed method is used to keep track of each file, with part of the
index stored in the inode for the file
 In all UNIX implementations the inode includes a number of direct
pointers and three indirect pointers (single, double, triple)
Capacity of a FreeBSD File with 4
Kbyte Block Size

Table 12.4
 UNIX Directories

and Inodes
 Directories are
structured in a
hierarchical tree

 Each directory can

contain files and/or
other directories

 A directory that is
inside another
directory is referred to
as a subdirectory Figure 12.17
 Volume Structure
 A UNIX file
system resides Boot block Superblock Inode table Data blocks

on a single
logical disk or
disk partition
and is laid out contains
contains
with the code
attributes and
collection storage space
required to of inodes available for
information
following boot the
about the file
for each data files and
operating file subdirectories
elements: system
system
UNIX File Access Control
 Access Control Lists
in UNIX
 FreeBSD allows the administrator to assign a list of UNIX user IDs and
groups to a file
 Any number of users and groups can be associated with a file, each with
three protection bits (read, write, execute)
 A file may be protected solely by the traditional UNIX file access
mechanism
 FreeBSD files include an additional protection bit that
indicates whether the file has an
extended ACL
 Summary
 A file management system:
 is a set of system software that provides services to users and applications in the use of files
 is typically viewed as a system service that is served by the operating system
 Files:
 consist of a collection of records
 if a file is primarily to be processed as a whole, a sequential file organization is the simplest
and most appropriate
 if sequential access is needed but random access to individual file is also desired, an indexed
sequential file may give the best performance
 if access to the file is principally at random, then an indexed file or hashed file may be the
most appropriate
 directory service allows files to be organized in a hierarchical fashion
 Some sort of blocking strategy is needed
 Key function of file management scheme is the management of disk space
 strategy for allocating disk blocks to a file
 maintaining a disk allocation table indicating which blocks are free