lOMoARcPSD|29978266

5th module S3 BCA-OS File-System Interface

Syllabus: Unit 5: Storage Management: File System: - File Concept, Access Methods,
Directory structure. Implementing File Systems:-File System Structure, Allocation
Methods, Free Space Management, Disk Scheduling.

File-System Interface
File Concept

The most visible aspects of a computer is the data that it is storing. This view is generally
of files and directories.

The operating system abstracts the hardware details of storing a file, and presents a clean
file interface, using which we can access the files and modify them. The users generally
do not care how the file is stored on the hardware, how the sectors on the hard drive are
arranged, etc. All those low level details are handled by the operating system.

A file is a named collection of related information that is recorded on secondary storage.

From a user’s perspective, a file is the smallest allotment of logical storage; that is, data
cannot be written to secondary storage unless they are within a file. Commonly, files
represent programs (both source and object forms) and data. Data files may be numeric,
alphabetic, alphanumeric, or binary. Files may be free form, such as text files, or may be
formatted rigidly. In general, a file is a sequence of bits, bytes, lines, or records, the
meaning of which is defined by the file’s creator and user.

File systems are generally arranged in a tree like manner, where root and branches are
directories and files are leafs.

File Attributes

Various operating systems may store various attributes for files. Some will store the
owner of the file, while others won't. Generally, there are a few attributes that are always
there:

Name of the file : The symbolic file name is the only information kept in human readable
form.

Identifier : This unique tag, usually a number, identifies the file within the file system; it
is the non-human-readable name for the file.

Type: This information is needed for those systems that support different types

S3 BCA-OS-RKR 1

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Location: This information is a pointer to a device and to the location of the file on that
device.

Size : The current size of the file.

Protection information : Access-control information determines who can do reading,

writing, executing and so on.

Time, date, and user identification : The information may be kept for creation, last
modification, and last use. These data can be useful for protection, security, and usage
monitoring.

The information about files is kept in the directory where these files are residing.

File Operations

Treating the file as an abstract data type, we can imagine performing abstract operations
on them, like:

Creating a file: Two steps are needed in creating a file. First, space must be found for
the file. Then, an entry in the directory needs to be created to illustrate that the file is
there.

Writing a file : To write a file we use a system call. We provide a file identifier, and the
information to be written. The operating system performs the write (or lets some driver
handle it). The operating system must maintain the write pointer in the file.

Reading a file: To read a file we use a system call. We provide the file identifier, and the
address where we want the data to be read (and the size of how much data to read). The
operating system handles the read. The operating system must maintain the read pointer
in the file (which is generally the same as the writing pointer).

Repositioning within a file : Moving the read/write pointer in the file (or moving
through the directory entries) is one of the basic operations on files. This does not have to
do any IO, since the data structures that maintain the read/write code are in memory, and
can be updated in memory.

Deleting a file : The operating system must provide for the deletion of a file. This
involves freeing the space allocated to the file, and removing the file entry from the
directory. (the reverse operation of creating a file).

Truncating a file: Truncating a file means erasing the contents of the file but keeping the
directory entry. (freeing memory allocated to the file, but not touching the directory entry
of the file). The file will effectively be empty.

S3 BCA-OS-RKR 2

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Some additional operations associated with a file are:

Open Files

For open files, the operating system usually maintains several lists. There is a global list,
which contains references to open files all across the system (for all processes), there is
also a local list that maintains open files per process.

Depending on the setup, these lists and data structures will contain:

File Pointer: The read/write pointer inside the file.

File Open Count: In the global table the system needs to maintain how many instances
of this file are currently opened by various processes.

Disk location of the file: The hard drive location of the file is usually kept in memory to
avoid having to read the hard drive to save something to a file.

Access Rights: Each file is opened in some access mode (read only, etc.) An operating
system can store this in a per-process open file table so that it can deny or allow some file
operation on a per-process basis.

File Types

There are various file types. The problem for the users and operating system is to
somehow maintain the type of the file. Some operating systems (notably Windows) rely
on the file extension to indicate the type of file. Others, like UNIX, rely on a magic
number in the file header to indicate the type. Refer the following figure:

S3 BCA-OS-RKR 3

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

File Structure

Determining the structure of the file sometimes goes hand in hand with the file type. If
we know the type, we can usually determine the file format.

For example, if we know that the type is a plain ASCII file, then we can be pretty sure the
file contains text. If we know that the extension is .java, then we know it contains java
code. Similarly, if we know the type is executable, we can expect the structures normally
found in executable files.

There are also binary types, which don't directly have any type. These are the most
flexible, but provide least support. Applications using such files must define their own
file format and read/write that format.

Internal File Structure

Files are generally stored on block devices, where data is stored in blocks. These blocks
can be hard drive sectors, or some other logically defined entity.

What this means is that the file, as a stream of bytes, may need to be subdivided into
these blocks. And tables will need to be maintained to indicate which block belongs to
what file.

There is also the problem of internal fragmentation. Here parts of the last block can be
wasted. For example, if the file is 513 bytes, and we have blocks of size 512, then we
need at least 2 blocks to store the file, with one block having only 1 byte (and the other
511 bytes being mostly wasted).

So, while increasing the block size reduces the size of tables that need to be maintained
for the disk, it does produce internal fragmentation.

Access Methods

There are several ways of accessing a file in a system.

Following code represent Sequential Access

read next
write next
reset
no read after last write
(rewrite)

Following code represent Direct Access

read n
write n

S3 BCA-OS-RKR 4

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

position to n
read next
write next
rewrite n

n = relative block number

From the above instructions read next and write next and reset are sequential accessing
operations. Read n and write n are direct accessing operations, where n is the relative
block number.

Sequential Access
Files can be accessed sequentially, meaning we read one byte of data at a time, and never
readjust the file pointer. This mode of accessing is very common. Programs like
compilers and many text editors use this format.

This access method also utilizes buffering to the maximum possible level. For example,
the library/operating system can read an entire hardware block (a sector for example) into
memory, and then simply provide bytes from memory.

This access method is so common that the notion of standard IO is based on them. Even
in java, the most common way to do IO is via Streams, which provide essentially
sequential file IO.

Direct Access
For some file manipulation sequential access is not enough. This is where we need direct
access or relative access. . a file is made up of fixed length logical records that allow
programs to read and write records rapidly in no particular order. Direct access lets us
seek to some location, and read/write data from that file location.

For direct access, the file is viewed as a numbered sequence of block or records. For the
direct-access method, the file operations must be modified to include the block number as
a parameter. Thus we have read n, where n is the block number, rather than read next
and write n rather than write next.

The block number provided by the user to the OS is normally beginning of the file. The
use of relative block numbers allows the OS to decide where the file should be placed and
helps to prevent the user from accessing portions of the file system that may not be part
of his file.

S3 BCA-OS-RKR 5

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Obviously we can simulate sequential access via direct access (by seeking every time we
read a byte).

Many databases use this method, since sequentially going through many records is time
consuming. The following table shows the Simulation of Sequential Access on a Direct-
access File. Cp is the current pointer in a file.

Other Access Methods

We can build many other access methods on top of direct-access method. These methods
generally involve the construction of an index for the file. The index, like an index in the
back of a book, contains pointers to the various blocks. To find a record in the file, we
first search the index, and then use the pointer to access the file directly and to find the
desired record.

With large files the index file itself may become too large to be kept in memory. One
solution is to create an index for the index file. The primary index file would contain
pointers to secondary index file, which would point to the actual data items.

Example of Index and Relative Files

The above figure a pointer from master is pointed relative file.

S3 BCA-OS-RKR 6

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Directory Structure

Directory can be defined as the listing of the related files on the disk. The directory may
store some or the entire file attributes.

To get the benefit of different file systems on the different operating systems, A hard disk
can be divided into the number of partitions of different sizes. The partitions are also
called volumes or mini disks.

Each partition must have at least one directory in which, all the files of the partition can
be listed. A directory entry is maintained for each file in the directory which stores all the
information related to that file.

A directory can be viewed as a file which contains the Meta data of the bunch of files.

Directory

Files F F F F
1 2 3 4 F
n

S3 BCA-OS-RKR 7

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

First is that disks are broken up into partitions. Each partition is logically treated as a
separate hard drive. A disk can have many partitions. There is usually at least one
partition on every hard drive.

Each partition (being a logical hard drive) has a directory that maintains a list of files in
the directory. This information is kept in entries in a device directory or volume table of
contents. The device directory records information – such as name, location, size and
type – for all files on that partition. Following figure shows the typical file system
organization.

Operations performed on directory

Just as with files, there are several basic operations on a directory:

Search for a file: we need to be able to search the directory for a specific file.
Create a file: We need to be able to create files and place the entry in the directory.
Delete a file: We need to be able to delete a file and remove its entry from the directory.
List a directory: We need to be able to get a list of files in the directory.
Rename a file: We need to be able to rename files in the directory.
Traverse the file system: We need some way (or ability) to traverse the directory. This is
useful in backups, compression (zipping the entire directory), etc.

Single-Level Directories

A single directory for all users. Directory structures are usually not simple, and some
simple systems may provide a limited view of what we know today as a directory
structure.

S3 BCA-OS-RKR 8

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Some systems only provide a single level directory structure. This means that we cannot
nest directories. There is a pictorial view of this is given below.

A single level directory has significant limitations, when the number of files increases or
when the system has more than one user. Since all files are in the same directory, they
must have unique names. Even a single user on a single level directory may find it
difficult to remember the names of all the files, as the number of files increases.

Advantages
1. Implementation is very simple.
2. If the sizes of the files are very small then the searching becomes faster.
3. File creation, searching, deletion is very simple since we have only one directory.

Disadvantages
1. We cannot have two files with the same name.
2. The directory may be very big therefore searching for a file may take so much
time.
3. Protection cannot be implemented for multiple users.
4. There are no ways to group same kind of files.
5. Choosing the unique name for every file is a bit complex and limits the number of
files in the system because most of the Operating System limits the number of
characters used to construct the file name.

Two-Level Directories

Single level directory structure has some major limitations. The namespace is fairly
limited and restricts any decent use of the system.

Two level directories aren't much better, but they provide a bit more abstraction. For
example, we can have several users having their own set of single-level directories.

In two level directory system each user has her own user file directory (UFD). Each
UFD has a similar structure, but lists only the files of a single user. When a user job
starts or a user logs in, the system’s master file directory (MFD) is searched.

S3 BCA-OS-RKR 9

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Path Names

You can specify the location of a file in the file hierarchy by using either an absolute
versus or a Relative path to the file

 An absolute path starts at the root.

 A relative path starts at the current (working) directory.
 The special directories . and .. represent the current directory and the parent of the
current directory respectively.

Characteristics of two level directory system

1. Each files has a path name as /User-name/directory-name/
2. Different users can have the same file name.
3. Searching becomes more efficient as only one user's list needs to be traversed.
4. The same kind of files cannot be grouped into a single directory for a particular
user.

Every Operating System maintains a variable as PWD which contains the present
directory name (present user name) so that the searching can be done appropriately.

Tree-Structured Directories

Most operating systems today use a variant of the Tree Structured directory. What this
means is that directories are like branches in a tree, and files are like leafs.

The tree has a root, which is a directory. A file is either a regular file, or a subdirectory.
A subdirectory can have either files or other subdirectories.

This structure in effect provides an arbitrary directory level.

S3 BCA-OS-RKR 10

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Acyclic-Graph Directories

Tree Structured directories, by definition, do not allow sharing of files (otherwise they
wouldn't be a 'tree' structure).

Thus, acyclic graph directories were created, so that users can share files and directories.

What this structure provides are files which are links to other files somewhere on the
system.

Acyclic directories suffer from the fact that they cannot have any cycles. In acyclic
directories we are intentionally restricting the structure not to have any cycles. This
means that every time we create a link file, we need to check and ensure that no cycle has
been created. This is not an easy task.

S3 BCA-OS-RKR 11

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

General Graph Directories

We can have General Graph directories that allow cycles in the graph. Unfortunately, the
algorithms that traverse graphs and acyclic graphs are quire different. For a graph with
possible cycles in it, we need to maintain a list of nodes we've already visited, in order
not to visit them again once they came up again in a cycle.

For large file systems, this storage of nodes may be prohibitive

S3 BCA-OS-RKR 12

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Protection

When information is kept in a computer system, we want to keep it safe from physical
damage(reliability) and improper access(protection). Reliability is generally provided by
duplicate copies of files. Many computers have systems programs that automatically
copy disk files to tape at regular intervals to maintain a copy should a file system be
accidentally destroyed.

Protection can be provided in many ways. For a small single-user system, we might
provide protection by physically removing the floppy disks and locking them in a desk
drawer or file cabinet.

Types of Access

Protection mechanisms provide controlled access by limiting the types of file access that
can be made. Access is permitted or denied depending on several factors, one of which is
the type of access requested. Several different types of operations may be controlled.

 Read: Read from the file

 Write : Write or rewrite the file
 Execute: Load the file into memory and execute it.
 Append: Write new information at the end of the file.
 Delete: Delete the file and free its space for possible reuse.
 List: List the name and attributes of the file.

Other operations, such as renaming, copying, or editing the file may also be controlled.

Access Control

Every file has an owner. For new files, the user who creates the file is the owner of that
file. The owner assigns an access mode to the file. Access modes grant other system users
permission to read, modify, or execute the file. Only the file's owner or users with root
authority can change the access mode of a file.

There are the three classes of users:

user/owner: The user who created the file is the owner.

group: A set of users who are sharing the file and need similar access is a group, or work
group.

universe: All other users in the system constitute the universe.

Access is granted to these groups in some combination of three modes: read, write, or
execute. For example when a new file is created, the default permissions are read, write,
and execute permission for the user who created the file. The other two groups have read
and execute permission.

S3 BCA-OS-RKR 13

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Files can be read (r), written (w), or executed (x). The system determines who has
permission and the level of permission they have for each of these activities. Access
modes are represented two ways in the operating system: symbolically and numerically.

Symbolic Representation of Access Modes

Access modes are represented symbolically, as follows:

r : Indicates read permission, which allows users to view the contents of a file.
w: Indicates write permission, which allows users to modify the contents of a file.
x : Indicates execute permission. For executable files (ordinary files that contain
programs), execute permission means that the program can be run. For directories,
execute permission means the contents of the directory can be searched.

For example, a file with the access modes set to rwxr-xr-x gives read and execute
permission to all three groups, but write permission only to the owner of the file. This is
the symbolic representation of the default setting.

File System Implementation

File system is the part of the operating system which is responsible for file management.
It provides a mechanism to store the data and access to the file contents including data
and programs. Some Operating systems treats everything as a file for example Ubuntu.

The File system takes care of the following issues

 File Structure

We have seen various data structures in which the file can be stored. The task of
the file system is to maintain an optimal file structure.

 Recovering Free space

Whenever a file gets deleted from the hard disk, there is a free space created in
the disk. There can be many such spaces which need to be recovered in order to
reallocate them to other files.

 disk space assignment to the files

The major concern about the file is deciding where to store the files on the hard
disk. There are various disks scheduling algorithm which will be covered later in
this tutorial.

 tracking data location

S3 BCA-OS-RKR 14

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

A File may or may not be stored within only one block. It can be stored in the non
contiguous blocks on the disk. We need to keep track of all the blocks on which
the part of the files reside.

File system structure

Disks provide the bulk of secondary storage on which a file system is maintained. They
have two characteristics that make them a convenient medium for storing multiple files.

1. They can be rewritten in place; it is possible to read a block from the disk, to
modify the block, and to write it back into the same place.
2. They can access directly any given block of information on the disk. Thus, it is
simple to access any file either sequentially or randomly, and switching form one
file to another requires only moving the read-write heads and waiting for the disk
to rotate
To provide an efficient and convenient access to the disk, the OS imposes one or more
file systems to allow the data to be stored, located and retrieved easily. The file system
itself is generally composed of many different levels. The structure shown in following
figure is an example of a layer design.

The lowest level, the I/O control, consists of device drivers and interrupt handlers to
transfer information between the main memory and the disk system. The basic file
system needs only to issue generic commands to the appropriate device driver to read and
write physical blocks on the disk. The file-organization module knows about files and
their logical blocks, as well as physical blocks. The logical file system manages metadata
information. Metadata includes all of the file-system structure, excluding the actual data.
The logical file system manages the directory structure to provide the file organization
module with the information the latter needs, given a symbolic file name. it maintains file
structure via file-control blocks. A file control block (FCB) contains information about
the file, including ownership, permissions, and location of the file contents.

S3 BCA-OS-RKR 15

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Directory Implementations

We can implement the directory in several ways.

Linear List

The simplest approach to implementing a directory is simply maintaining a list (or array)
of file names (and other info). It is the Linear list of file names with pointer to the data
blocks. It is very simple to program but time-consuming to execute.

This approach has some problems like: searching for a file means we must do a linear
search, and inserting and deleting from a fixed list is not simple.

We can also maintain a sorted list, but that would mean maintaining the sorted structure.

Hash Table

We can also implement the directory as a hash table. In this method, a linear list stores
the directory entries, but a has data structure is also used. The hash table takes a value
computed from the file name and returns a pointer to the file name in the linear list.
Therefore, it can greatly decreases the directory search time. Insertion and deletion are
also fairly straightforward, although some provision must be made for collisions –
situations where two file names hash to the same location.

The major difficulties with a hash table are its generally fixed size and the dependence of
the hash function on that size.

File Allocation Methods

Storing files is the primary job of the disk, but the method we use to allocate space to the
file plays a key role in performance.

An allocation method refers to how disk blocks are allocated for files: There are 3 types
of allocation methods.

 Contiguous allocation

 Linked allocation

 Indexed allocation

Contiguous Allocation

S3 BCA-OS-RKR 16

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

In Contiguous Allocation we allocate a file as a contiguous set of disk sectors. Disk

addresses define a linear ordering on the disk. It is simple and only starting location
(block #) and length (number of blocks) is required for directory entry for each file.
Contiguous allocation of a file is defined by the disk address and length of the first block.
If the file is n blocks long and starts at location b, then it occupies blocks b, b+1, b+2,
….., b+n-1. First fit and best fit are the most common strategies used to select a free hole
from the set of available holes. Random accessing used to move between files.

This has benefits that seeking within a file is easy, since we can easily calculate where
parts of file are on the disk. Reading a file is also efficient since the read/write had
doesn't have to do too much seeking from sector to sector. The following figure shows
the contiguous allocation.

The above figure count, tr, mail etc are file names. Starting location and size are attached
with each file. For example count is started with 0 and 0 and 1 are used for allocate it.

The disadvantage is that this approach causes external fragmentation. As files are
allocated and deleted, the free disk space is broken into little pieces.

Finding space for a file may become a problem. Because of advance allocation of space
lead to wasteful of space (dynamic storage-allocation problem).

It is not possible to grow the file size in contiguous allocation. If we allocated enough
space for its final size, much of that space may be unused for a long time. So there may
be a chance of large amount of internal fragmentation.

We can overcome some difficulties by allocating a contiguous block, then once that is
used up, allocate another large contiguous block for a file and link those together.

S3 BCA-OS-RKR 17

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Linked Allocation
Linked allocation creates inked lists using disk sectors as nodes. Each file is a linked list
of disk blocks: blocks may be scattered anywhere on the disk.

block = pointer

For example, if the sector size is 512 bytes, and it takes a 32 bit number to represent the
next block address, then only 508 bytes can be used to store data (the other 4 bytes are
used to locate the next file sector). The following fig shows this allocation.

From the above figure jeep is the file name and start and end are the representation of
starting and ending of blocks.

Linked allocation is simple and need only starting address. It is a free-space management
system because no waste of space. Random accessing is not possible

This approach eliminates external fragmentation (since even the smallest block can now
be used).

Some problems with this approach are that seeking within a file is now difficult. For
example, if we're interested in the last 100 bytes of a 100mb file, we need to traverse all
the sectors of the file (follow links) to get to the last 100 bytes.

Another major issue is that we need to do a disk seek with every disk sector (unless disk
sectors are contiguous).
S3 BCA-OS-RKR 18

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

And yet another issue with this is that storing pointers on every disk sector uses up a lot
of disk space.

An important variation on the linked allocation method is the use of a file allocation table
(FAT). A section of disk at the beginning of each partition is set aside to contain the
table. The table has one entry for each disk block, and is indexed by block number. The
FAT is used much as is a linked list. The directory entry contains the block number of
the first block of the file. The table entry indexed by that block number the contains the
block number of the next block in the file. This chain continues until the last block,
which has a special end of file value as the table entry. Unused blocks are indicated by a
0 table value.
The following figure shows it.

Indexed Allocation

Indexed allocation is similar to linked allocation, but instead of having each node having
a reference to the next node, there is one node, that has links to all the other nodes (based
on an index). We can also use nested indexes, etc.

Dynamic access without external fragmentation, but have overhead of index block.

Mapping from logical to physical in a file of maximum size of 256K words and block
size of 512 words. We need only 1 block for index table.

S3 BCA-OS-RKR 19

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Each file has its own index block, which is an array of disk-block addresses. The ith entry
in the index block points to the ith block of the file. The directory contains the address of
the index block. This is shown in the following figure. To read the ith block, we use the
pointer in the ith index-block entry to find and read the desired block.

Indexed allocation does suffer from wasted space. The pointer overhead of the index
block is generally greater than the pointer overhead of linked allocation.

Every file has an index block. If the index block is too small, however, it will not be able
to hold enough pointer for a large file.

Solutions to this problem are:

Linked scheme

Multi level index

Combined scheme

Free Space Management

In order to make a file system work we not just have to care how to allocate files, but
how to allocate and manage free space. To keep track of free disk space, the system
maintains a free-space list. The free-space list records all free disk blocks-those not
allocated to some file or directory. To create a file, we search the free-space list for the
required amount of space, and allocate that space to the new file.

S3 BCA-OS-RKR 20

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Bit Vector

One approach to allocating free space is to maintain a bit vector or bit map used sectors.
Each block is represented by 1 bit. If the block is free, the bit is 1, if the block is
allocated, the bit is 0.

0 1 2 n-1
…

For example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26,
and 27 are free and the rest of the blocks are allocated. The free space bit map would be

001111001111110001100000011100000…

The main advantage of this approach is its relatively simplicity and efficiency in finding
the first free block, or n consecutive free blocks on the disk.

This approach suffers from the fact that even with a bit for each sector the memory
requirements for the bit vector are relatively large (especially for large disks).

Linked Lists

We can also use linked lists of free sectors (or clusters). A linked list would contain the
next free block, which would point to next free block, etc. Once a block is allocated, the
next free block becomes the 'free block'.

S3 BCA-OS-RKR 21

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

In the above example we would keep a pointer to block 2, as the first free block. Block 2
would contain a pointer to block 3, which would point to block 4, which would point to
block 5, which would point to block 8, and so on.

How ever, this scheme is not efficient.

Grouping
A modification of the free-list approach is to store the addresses of n free blocks in the
first free block. The firs n-1 of these blocks are actually free. The last block contains the
addresses of another n free block, and so on.

Counting

Here, rather than keeping a list of n free disk addresses, we can keep the address of the
first free block and the number n of free contiguous blocks that follow the first block.
Each entry in the free-space list then consists of a disk address and a count.

Performance

Depending on the chosen algorithm and its implementation we can specialize the system
for a specific type of use and desired efficiency. For some systems, linked allocation
scheme might work best, for others, contiguous might be better, and yet others, a hybrid
approach might do well.

In any case, the system can improve efficiency by storing parts of the disk data in
memory and accessing it there instead of the disk. For example, the system can maintain
the file allocation table in memory, etc.

This presents some reliability problems, since in case of a crash, volatile memory gets
wiped out, and the disk may no longer be in valid state.

We can apply all sorts of recovery and proper state management techniques to try to
avoid any problems a crash might cause to the operating system.

Recovery

Data recovery is the process of salvaging data from damaged, failed, corrupted, or
inaccessible secondary storage media when it cannot be accessed normally. Often the
data are being salvaged from storage media such as hard disk drives, storage tapes, CDs,
DVDs, and other electronics.

Consistency checking

A part of the directory information is kept in main memory to speed up access. The
directory information in main memory is generally more up to date than is the
corresponding information on the disk, because the write of cached directory information
to disk does not necessarily occur as soon as the update takes place.

S3 BCA-OS-RKR 22

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Consider the possible effect of a computer crash. In this case, the table of opened files is
generally lost, and with it any changes in the directories of opened files. This event can
leave the file system in an inconsistent state.

The consistency checker compares the data in the directory structure with the data blocks
on disk, and tries to fix any inconsistencies it finds. The allocation and free-space-
management algorithms dictate what types of problems the checker can find, and how
successful it will be in fixing them.

Backup and restore

In information technology, a backup or the process of backing up refer to making copies

of data so that these additional copies may be used to restore the original after a data loss
event. These additional copies are typically called "backups."

Backups are useful primarily for two purposes. The first is to restore a state following a
disaster (called disaster recovery-is the process, policies and procedures related to
preparing for recovery). The second is to restore small numbers of files after they have
been accidentally deleted or corrupted. Data loss is also very common. 66% of internet
users have suffered from serious data loss.

Disk Scheduling
The technique that operating system uses to determine the request which is to be satisfied
next is called disk scheduling.

some important terms related to disk scheduling are.

Seek Time

Seek time is the time taken in locating the disk arm to a specified track where the
read/write request will be satisfied.

Rotational Latency

It is the time taken by the desired sector to rotate itself to the position from where it can
access the R/W heads.

Transfer Time

It is the time taken to transfer the data.

Disk Access Time

Disk access time is given as,

Disk Access Time = Rotational Latency + Seek Time + Transfer Time

S3 BCA-OS-RKR 23

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Disk Response Time

It is the average of time spent by each request waiting for the IO operation.

Purpose of Disk Scheduling

The main purpose of disk scheduling algorithm is to select a disk request from the queue
of IO requests and decide the schedule when this request will be processed.

Goal of Disk Scheduling Algorithm

 Fairness
 High throughout
 Minimal traveling head time

Disk Scheduling Algorithms

The list of various disks scheduling algorithm is given below. Each algorithm is carrying
some advantages and disadvantages. The limitation of each algorithm leads to the
evolution of a new algorithm.

 FCFS scheduling algorithm

 SSTF (shortest seek time first) algorithm
 SCAN scheduling
 C-SCAN scheduling
 LOOK Scheduling
 C-LOOK scheduling

1. FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the
requests are addressed in the order they arrive in the disk queue.

Advantages:

 Every request gets a fair chance

 No indefinite postponement

Disadvantages:

 Does not try to optimize seek time

 May not provide the best possible service

Given the following track requests in the disk queue, compute for the Total Head
Movement2 (THM) of the read/write head:
95, 180, 34, 119, 11, 123, 62, 64

S3 BCA-OS-RKR 24

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Consider that the read/write head is positioned at location 50. Prior to this track location 199
was serviced. Show the total head movement for a 200 track disk (0-199).

Total Head Movement Computation:

(THM) = (180 - 50) + (180-34) + (119-34) + (119-11) + (123-11) + (123-62) + (64-62)
= 130 + 146 + 85 + 108 + 112 + 61 + 2
(THM) = 644 tracks
Assuming a seek rate of 5 milliseconds is given, we compute for the seek time using the
formula:
Seek Time = THM * Seek rate = 644 * 5 ms

Seek Time = 3,220 ms

2. SSTF: In SSTF (Shortest Seek Time First), requests having shortest seek time are
executed first. So, the seek time of every request is calculated in advance in queue
and then they are scheduled according to their calculated seek time. As a result,
the request near the disk arm will get executed first. SSTF is certainly an
improvement over FCFS as it decreases the average response time and increases
the throughput of system.

Advantages:

 Average Response Time decreases

 Throughput increases

Disadvantages:

S3 BCA-OS-RKR 25

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

 Overhead to calculate seek time in advance

 Can cause Starvation for a request if it has higher seek time as compared to
incoming requests
 High variance of response time as SSTF favours only some requests

(THM) = (64-50) + (64-11) + (180-11) = 14 + 53 + 169

(THM) = 236 tracks
Seek Time = THM * Seek rate = 236 * 5ms

Seek Time = 1,180 ms

3. SCAN: In SCAN algorithm the disk arm moves into a particular direction and
services the requests coming in its path and after reaching the end of disk, it
reverses its direction and again services the request arriving in its path. So, this
algorithm works like an elevator and hence also known as elevator algorithm. As
a result, the requests at the midrange are serviced more and those arriving behind
the disk arm will have to wait.

Advantages:

 High throughput
 Low variance of response time
 Average response time

Disadvantages:

 Long waiting time for requests for locations just visited by disk arm

S3 BCA-OS-RKR 26

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

(THM) = (50-0) + (180-0) = 50 + 180

(THM) = 230
Seek Time = THM * Seek rate = 230 * 5ms

Seek Time = 1,150 ms

4. CSCAN: In SCAN algorithm, the disk arm again scans the path that has been
scanned, after reversing its direction. So, it may be possible that too many
requests are waiting at the other end or there may be zero or few requests pending
at the scanned area.

These situations are avoided in CSAN algorithm in which the disk arm instead of
reversing its direction goes to the other end of the disk and starts servicing the requests
from there. So, the disk arm moves in a circular fashion and this algorithm is also similar
to SCAN algorithm and hence it is known as C-SCAN (Circular SCAN).

Advantages:

 Provides more uniform wait time compared to SCAN

S3 BCA-OS-RKR 27

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

Assume that in this example, α has a value of 20ms, the computation would be as follows:
(THM) = (50-0) + (199-62) + α = 50 + 137 + 20
(THM) = 207 tracks
Seek Time = THM * Seek rate = 187 * 5ms

Seek Time = 935 ms

5. LOOK: It is similar to the SCAN disk scheduling algorithm except the difference
that the disk arm in spite of going to the end of the disk goes only to the last
request to be serviced in front of the head and then reverses its direction from
there only. Thus it prevents the extra delay which occurred due to unnecessary
traversal to the end of the disk.

S3 BCA-OS-RKR 28

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

(THM) = (50-11) + (180-11) = 39 + 169

(THM) = 208 tracks
Seek Time = THM * Seek rate = 208 * 5ms

Seek Time = 1,040 ms

6. CLOOK: As LOOK is similar to SCAN algorithm, in similar way, CLOOK is

similar to CSCAN disk scheduling algorithm. In CLOOK, the disk arm inspite of
going to the end goes only to the last request to be serviced in front of the head
and then from there goes to the other end’s last request. Thus, it also prevents the
extra delay which occurred due to unnecessary traversal to the end of the disk.

Note: using the same value of the alpha in C-SCAN.

S3 BCA-OS-RKR 29

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])

 lOMoARcPSD|29978266

(THM) = (50-11) + (180-62) + α = 39 + 118 + 20

(THM) = 177 tracks
Seek Time = THM * Seek rate = 157 * 5ms
Seek Time = 785 ms

Analysis

Disk scheduling algorithms are used to allocate the services to the I/O requests on the disk and
improve its performance. Different qualities exists on these algorithms based on the given
examples and computations. Several disadvantages also occur on these different algorithm and
these are:
The FCFS performs operations in order requested. No reordering of work queue since it
processed disk requests according to its arrival. There is no starvation and all the requests are
serviced but it doesn’t provide fastest service.
The Shortest Seek Time First (SSTF) selects the disk I/O request that requires the least
movement of the disk access arm from its current position regardless of direction. It also
reduces the seek time compared to FCFS but in this algorithm, I/O requests at the edges of the
disk surface may get starved.
The SCAN algorithm go from the outside to the inside servicing requests and then back from
the outside to the inside servicing requests. It also reduces variance compared to SSTF.

The Circular SCAN (C-SCAN) moves from one end of the disk to the other, servicing requests.
When other end is reached, it immediately returns to the beginning of the disk, without
servicing any requests. This algorithm treats the cylinders as a circular list that wraps around
from the last cylinder to the first one. It also provides a more uniform wait time than SCAN.
In LOOK scheduling algorithm, the arm goes only as far as the final request in each direction.
The direction reverses immediately, without going all the way to the end of the disk.
The Circular LOOK (C-LOOK) algorithm is similar to C-SCAN. The disk head also goes as far as
the last request in its direction then reverses its direction immediately without first going all the
way to the end of the disk.
When selecting a Disk Scheduling algorithm, performance depends on the number and types of
requests. SSTF is common and has a natural appeal. SCAN gives better performance than FCFS
and SSTF. From the given examples, a SCAN change is seen from 644 total head movements to
just 157. There is now an understanding as to why an operating system truly relies on the type
of algorithm it needs when it is dealing with multiple processes.
The disk-scheduling algorithm should be written as a separate module of the operating system,
allowing it to be replaced with a different algorithm if necessary. Either SCAN or C-LOOK is a
reasonable choice for the default algorithm.

S3 BCA-OS-RKR 30

Downloaded by amruthavarshini R (amruthavarshinir338@[Link])