FILE SYSTEM

File concept:
A file is a collection of related information that is stored on secondary storage.
Information stored in files must be persistent i.e. not affected by power failures &
system reboots. Files may be of free from such as text files or may be formatted rigidly.
Files represent both programs as well as data.
Part of the OS dealing with the files is known as file system.

The important file concepts include:

1. File attributes: A file has certain attributes which vary from one operating system to
another.
 Name: Every file has a name by which it is referred.
 Identifier: It is unique number that identifies the file within the file system.
 Type: This information is needed for those systems that support different types of files.
 Location: It is a pointer to a device & to the location of the file on that device
 Size: It is the current size of a file in bytes, words or blocks.
 Protection: It is the access control information that determines who can
read, write &execute a file.
 Time, date & user identification: It gives information about time of
creation or last modification & last use.
2. File operations: The operating system can provide system calls to create, read, write,
reposition, delete and truncate files.
 Creating files: Two steps are necessary to create a file. First, space must be
found for the file in the file system. Secondly, an entry must be made in the
directory for the new file.
 Reading a file: Data & read from the file at the current position. The system
must keep a read pointer to know the location in the file from where the next
read is to take place. Once the read has been taken place, the read pointer is
updated.
 Writing a file: Data are written to the file at the current position. The system
must keep a write pointer to know the location in the file where the next write is
to take place. The write pointer must be updated whenever a write occurs.
  Repositioning within a file (seek): The directory is searched for the
appropriate entry & the current file position is set to a given value. After
repositioning data can be read from orwritten into that position.
 Deleting a file: To delete a file, we search the directory for the required file.
After deletion, the space is releasedso that it can be reused by other files.
 Truncating a file: The user may erase the contents of a file but allows all
attributes to remain unchanged expect the file length which is rest to ‘O’ &
the space is released.
3. File types: The file name is spilt into 2 parts, Name & extension. Usually these two
parts are separated by a period. The user & the OS can know the type of the file from
the extension itself. Listed below are some file types along with their extension:
File Type Extension
Executable File exe, bin,
com Object File obj, o
(compiled) Source Code file
C, C++,
Java, pas
Batch File bat, sh (commands to command the
interpreter)Text File txt, doc (textual data documents)
arc, zip, tar (related files grouped together into file compressed for
Archieve File storage)
Multimedia File mpeg (Binary file containing audio or A/V information)
4. File structure: Files can be structured in several ways. Three common possible are:
 Byte sequence:The figure shows an unstructured sequence of bytes. The OS
doesn’t care about the content of file. It only sees the bytes. This structure
provides maximum flexibility. Users can write anything into their files & name
them according to their convenience. Both UNIX & windows use this approach.

byte
  Record sequence: In this structure, a file is a sequence of fixed length
records. Here the read operation returns one records & the write operation
overwrites or append or record.

Record

 Tree:In this organization, a file consists of a tree of records of varying lengths.

Each record consists of a key field. The tree is stored on the key field to allow
first searching for a particular key.
Access methods: Basically, access method is divided into 2 types:

 Sequential access: It is the simplest access method. Information in the file is

processed inorder i.e. one record after another. A process can read all the data in
a file in order starting from beginning but can’t skip & read arbitrarily from any
location. Sequential files can be rewound. It is convenient when storage
medium was magnetic tape rather than disk.
 Direct access: A file is made up of fixed length-logical records that allow
programs to read & write records rapidly in no particular O order. This method
can be used when disk are used for storing files. This method is used in many
applications e.g. database systems. If an airline customer wants to reserve a seat
on a particular flight, the reservation program must be able to access the record
 for that flight directly without reading the records before it. In a direct access file,
there is no restriction in the order of reading or writing. For example, we can
read block 14, then read block 50 & then write block 7 etc. Direct access files are
very useful for immediate access to large amount of information.

Directory structure: The file system of computers can be extensive. Some systems store
thousands of file on disk. To manage all these data, we need to organize them. The organization
is done in 2 steps. The file system is broken into partitions. Each partition contains information
about file within it.
Operation on a directory:
 Search for a file: We need to be able to search a directory for a particular file.
 Create a file: New files are created & added to the directory.
 Delete a file: When a file is no longer needed, we may remove it from the directory.
 List a directory: We should be able to list the files of the directory.
 Rename a file: The name of a file is changed when the contents of the file changes.
 Traverse the file system: It is useful to be able to access every directory
& every file within a directory.
Structure of a directory: The most common schemes for defining the structure of the
directoryare:

1. Single level directory: It is the simplest directory structure. All files are present
in the same directory. So it is easy to manage & understand.
Limitation: A single level directory is difficult to manage when the no. of files
increases or when there is more than one user. Since all files are in same directory,
they must have unique names. So, there is confusion of file names between
different users.
2. Two level directories: The solution to the name collision problem in single level
directory is to create a separate directory for each user. In a two level directory
structure, each user has its ownuser file directory. When a user logs in, then master
file directory is searched. It is indexed by user name & each entry points to the
UFD of that user.
Limitation: It solves name collision problem. But it isolates one user from
another. It is an advantage when users are completely independent. But it is a
 disadvantage when the users needto access each other’s files & co-operate among
themselves on a particular task.
3. Tree structured directories: It is the most common directory structure. A two level
directory is a two level tree. So, the generalization is to extend the directory structure
to a tree of arbitrary height. It allows users to create their own subdirectories &
organize their files. Every file in the system has a unique path name. It is the path
from the root through all the sub-directories to a specified file. A directory is simply
another file but it is treated in a special way. One bit in each

directory entry defines the entry as a file (O) or as sub- directories. Each user has a current
directory. It contains most of the files that are of current interest to the user. Path names can be of
two types: An absolute path name begins from the root directory & follows the path down tothe
specified files. A relative path name defines the path from the current directory. E.g. If the current
directory is root/spell/mail, then the relative path name is prt/first & the absolute path name is
root/ spell/ mail/ prt/ first. Here users can access the files of other users also by specifying their
path names.

4. A cyclic graph directory:It is a generalization of tree structured directory scheme.

An a cyclic graph allows directories to have shared sub-directories & files. A shared
directory or file is not the same as two copies of a file. Here a programmer can view
the copy but the changes made inthe file by one programmer are not reflected in the
other’s copy. But in a shared file, there is only one actual file. So many changes
made by a person would be immediately visible to others. This scheme is useful in a
situation where several people are working as a team. So, here all the files that are to
be shared are put together in one directory. Shared files and sub-directories can be
implemented in several ways. A common way used in UNIX systems is to create a
new directory entry called link. It is a pointer to another file or sub-directory. The
other approach is to duplicate all information in both sharing directories. A cyclic
graph structure is more flexible then a tree structure but it is also more complex.
Limitation: Now a file may have multiple absolute path names. So, distinct file names
may refer to the same file. Another problem occurs during deletion of a shared file.
When a file is removed by any one user. It may leave dangling pointer to the non
existing file. One serious problem in a cyclic graph structure is ensuring that there
are no cycles. To avoid these problems, some systems do not allow shared
 directories or files. E.g. MS-DOS uses a tree structure rather than a cyclic to avoid
the problems associated with deletion. One approach for deletion is to preserve the
file until all references to it are deleted. To implement this approach, we must have
some mechanism for determining the last reference to the file. For this we have to
keep a list of reference to a file. But due to the large size of the no. of references.
When the count is zero, the file can be deleted.
5. General graph directory: When links are added to an existing tree structured
directory, the tree structure is destroyed, resulting in a simple graph structure.
Linking is a technique that allows a file to appear in more than one directory. The
advantage is the simplicity of algorithm totransverse the graph & determines when
there are no more references to a file.
But a similar problem exists when we are trying to determine when a file can be
deleted. Here also a value zero in the reference count means that there are no more
references to the file or directory & the file can be deleted. But when cycle exists, the
reference count may be non-zero even when there are no references to the directory
or file. This occurs due to the possibility of self referencing (cycle) in the structure.
So, here we have to use garbage collection scheme to determine when the last
references to a file has been deleted & the space can be reallocated. It involves two
steps:
 Transverse the entire file system & mark everything that can be accessed.
 Everything that isn’t marked is added to the list of free space.
But this process is extremely time consuming. It is only necessary due to presence of
cycles inthe graph. So, a cyclic graph structure is easier to work than this.
Protection
When information is kept in a computer system, a major concern is its protection from
physicaldamage (reliability) as well as improper access.
Types of access: In case of systems that don’t permit access to the files of other users.
Protectionis not needed. So, one extreme is to provide protection by prohibiting access.
The other extreme is to provide free access with no protection. Both these approaches
are too extreme for general use. So, we need controlled access. It is provided by limiting
the types of file access. Access is permitted depending on several factors. One major
factor is type of access requested. The different type of operations that can be
controlled are:
 Read
 Write
 Execute
 Append
 Delete
 List
Access lists and groups:
Various users may need different types of access to a file or directory. So, we can
associate an access lists with each file and directory to implement identity dependent
access. When a user access requests access to a particular file, the OS checks the access
list associated with that file. If that user is granted the requested access, then the access is
allowed. Otherwise, a protection violation occurs & the user is denied access to the file.
But the main problem with access lists is their length.

It is very tedious to construct such a list. So, we use a condensed version of the access
list by classifyingthe users into 3 categories:
 Owners: The user who created the file.
 Group: A set of users who are sharing the files.
 Others: All other users in the system.
Here only 3 fields are required to define protection. Each field is a collection of bits each
of whicheither allows or prevents the access. E.g. The UNIX file system defines 3 fields
of 3 bits each: rwx
 r( read access)
 w(write access)
 x(execute access)
Separate fields are kept for file owners, group & other users. So, a bit is needed to record
protection information for each file.
Allocation methods
There are 3 methods of allocating disk space widely used.
1. Contiguous allocation:
a. It requires each file to occupy a set of contiguous blocks on the disk.
b. Number of disk seeks required for accessing contiguously allocated file is minimum.
c. The IBM VM/CMS OS uses contiguous allocation. Contiguous allocation of a file
is defined by the disk address and length (in terms of block units).
d. If the file is ‘n’ blocks long and starts all location ‘b’, then it occupies blocks b, b+1,
b+2,----
- -b+ n-1.
e. The directory for each file indicates the address of the starting block and the
length of the area allocated for each file.
f. Contiguous allocation supports both sequential and direct access. For sequential
access, the file system remembers the disk address of the last block referenced
and reads the next block when necessary.
g. For direct access to block i of a file that starts at block b we can immediately access block
b
+ i.
h. Problems: One difficulty with contiguous allocation is finding space for a
new file. It also suffers from the problem of external fragmentation. As files are
deleted and allocated, the free disk space is broken into small pieces. A major
problem in contiguous allocation is how much space is needed for a file. When a
file is created, the total amount of space it will need must be found and allocated.
Even if the total amount of space needed for a file is known in advances, pre-
allocation is inefficient. Because a file that grows very slowly must be allocated
enough space for its final size even though most of that space is left unused for
a long period time. Therefore, the file has a large amount of internal
fragmentation.
2. Linked Allocation:
a. Linked allocation solves all problems of contiguous allocation.
b. In linked allocation, each file is linked list of disk blocks, which are scattered
throughout the disk.
 c. The directory contains a pointer to the first and last blocks of the file.
d. Each block contains a pointer to the next block.
e. These pointers are not accessible to the user. To create a new file, we simply
create a new entry in the directory.
f. For writing to the file, a free block is found by the free space management
system and this new block is written to & linked to the end of the file.
g. To read a file, we read blocks by following the pointers from block to block.
h. There is no external fragmentation with linked allocation & any free block can
be used to satisfy a request.
i. Also there is no need to declare the size of a file when that file is created. A file
can continueto grow as long as there are free blocks.
j. Limitations: It can be used effectively only for sequential access files. To
find the ‘ i ' thblock of the file, we must start at the beginning of that file and
follow the pointers until we get the ith block. So it is inefficient to support
direct access files. Due to the presence of pointers each file requires slightly
more space than before. Another problem is reliability. Since the files are
linked together by pointers scattered throughout the disk. What would happen
if a pointer were lost or damaged.
3. Indexed Allocation:
a. Indexed allocation solves the problem of linked allocation by bringing all
the pointerstogether to one location known as the index block.
b. Each file has its own index block which is an array of disk block addresses. The
ith entry inthe index block points to the ith block of the file.

c. The directory contains the address of the index block. The read the ith block,
we use the pointer in the ith index block entry and read the desired block.
d. To write into the ith block, a free block is obtained from the free space
manager and its address is put in the ith index block entry.
e. Indexed allocation supports direct access without suffering external fragmentation.
f. Limitations: The pointer overhead of index block is greater than the pointer
overhead of linked allocation. So here more space is wasted than linked
allocation. In indexed allocation,an entire index block must be allocated, even if
 most of the pointers are nil.

(OR)

File Allocation Methods :

The allocation method defines how the files are stored in the disk blocks. The direct access
nature of the disks gives us the flexibility to implement the files. There are three major file
allocation methods, they are
1) Contiguous Allocation
2) Linked Allocation
3) Indexed Allocation

The main idea behind these methods is to provide

• o Efficient disk space utilization
• o Fast access to the file blocks

Contiguous Allocation :
In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file
requires n blocks and is given a block b as the starting location, then the blocks assigned to the
file will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the
length of the file (in terms of blocks required), we can determine the blocks occupied by the
file. The directory entry for a file with contiguous allocation contains

• Address of starting block

• Length of the allocated portion.

The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies 19,
20, 21, 22, 23, 24 blocks.
Advantages
• o Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth
block of the file which starts at block b can easily be obtained as (b+k).
• o This is extremely fast since the number of seeks are minimal because of contiguous allocation of file
blocks.

Disadvantages
• o This method suffers from both internal and external fragmentation. This makes it inefficient in terms of
memory utilization.
• o Increasing file size is difficult because it depends on the availability of contiguous memory at a particular
instance.

Linked Allocation
In this scheme, each file is a linked list of disk blocks which need not be contiguous. The disk blocks can be
scattered anywhere on the disk. The directory entry contains a pointer to the starting and the ending file block. Each
block contains a pointer to the next block occupied by the file.
The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25)
contains -1 indicating a null pointer and does not point to any other block.

Advantages
• o This is very flexible in terms of file size. File size can be increased easily since the system does
not have to look for a contiguous chunk of memory.
• o This method does not suffer from external fragmentation. This makes it relatively better in
terms of memory utilization.

Disadvantages
• o Because the file blocks are distributed randomly on the disk, a large number of seeks are needed
to access every block individually. This makes linked allocation slower.
• o Pointers required in the linked allocation incur some extra overhead.
Indexed Allocation
In this scheme, a special block known as the Index block contains the pointers to all the blocks
occupied by a file. Each file has its own index block. The ith entry in the index block contains
the disk address of the ith file block. The directory entry contains the address of the index
block as shown in the figure.

Advantages
• o This supports direct access to the blocks occupied by the file and therefore provides fast access to the file
blocks.
• o It overcomes the problem of external fragmentation.

Disadvantages
• o The pointer overhead for indexed allocation is greater than linked allocation.

Free Space Management

Since there is only a limited amount of disk space, it is necessary to reuse the space from
the deleted files. To keep track of free disk space, the system maintains a free space list.
It records all the disk blocks that are free i.e. not allocated to some file or dictionary. To
create a file, we search the free space list for the required amount of space and allocate it
to the new file. This space is then removed from the free space list. When a file is deleted,
its disk space is added to the free space list.
Implementation:
There are 4 ways to implement the free space list such as:
Bit Vector: The free space list is implemented as a bit map or bit vector. Each
block is represented as 1 bit. If the block is free, the bit is 1 and if it is allocated
then the bit is 0. For example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11,
12, 13, 17, 18, 25, 26 & 27 are freeand rest of the blocks are allocated. The free
space bit map would be 0011110011111100011000000111……………………..
The main advantage of this approach is that it is simple and efficient to find the first
free block or n consecutive free blocks on the disk. But bit vectors are inefficient
unless the entire vector is kept in main memory. It is possible for smaller disks but
not for larger ones.
Linked List: Another approach is to link together all the free disk blocks and keep a
pointer to the first free block. The first free block contains a pointer to the next free
block and so on. For example, we keep a pointer to block 2 as the free block. Block
2 contains a pointer to block which points to block 4 which then points to block 5
and so on. But this scheme is not efficient. To traverse the list, we must read each
block which require a lot of I/O time.

Grouping: In this approach, we store the address of n free blocks in the first free
block. The first n-1 of these blocks is actually free. The last block contains the
address of another n free blocks and so on. Here the addresses of a large number of
free blocks can be found out quickly.
Counting: Rather than keeping a list of n free disk block addresses, we can keep the
address ofthe first free block and the number of free contiguous blocks. So here
each entry in the free space list consists of a disk address and a count.
OVERVIEW OF MASS STORAGE STRUCTURE:

All the mass storage media belongs to the secondary memory.

Difference between Primary Memory and Secondary Memory

S. Primary Memory Secondary Memory

No

1.) Primary Memory is also primarily known as Secondary Memory is also

main memory or primary storage memory primarily known as secondary
memory storage

2.) They are also known as Internal Memory They are also known as Auxiliary
Memory or Backup Memory or
Additional Memory.

3.) Primary Memory is more costlier than Secondary Memory is less costlier
Secondary Memory than Secondary Memory

4.) Primary memory is said to be faster than Secondary memory is said to be

Secondary memory. slower than primary memory.

5.) It stores information or data that the processing It has a substantial amount of
unit is currently using. Usually, capacity ranges information and data storage.
from sixteen Giga Bytes (16 GB) to Thirty Two Typically, capacity ranges from 200
Giga Bytes (32 GB). GB to terabytes.

6.) The Primary Memory can be divided as Volatile The Secondary Memory can only be
and Non Volatile Memories classified as Non Volatile Memory
only.

7.) Data cannot be preserved in the event of a Because it has a non-volatile

power outage since it is a volatile memory. memory, the information may be
kept even in the event of a power
outage.
 Mass Storage Structure

Systems designed to store enormous volumes of data are referred to as mass storage devices. The
basic idea of Mass Storage is to create a Data Backup or Data Recovery System.

Mass storage may include several kinds of hard disks or solid-state storage devices, as well
as tape drives and other physical data storage devices.

The concepts of data backup and data recovery are frequently linked to mass storage media. The
biggest Business Companies will make plans for recording, storing, and backing up all accessible
data, which calls for a lot more mass storage media. This suggests a method for handling
continuous mass storage that uses tape or other media. Other kinds of mass storage could
function well as a data storage plan for a big network or a bunch of mobile distant devices. To
backup data on a portable tablet that doesn't have a lot of internal capacity, for instance, mass
storage for a tablet might require the usage of flash or Universal Serial Bus media (USB Media).

The Mass Storage Structure Devices are:

1. Magnetic Disks
2. Solid State Disks
3. Magnetic Tapes

Magnetic Disks

The process of magnetization is used to write, rewrite, and access data on a magnetic disk, a
storage device. This process is known as Magnetic Disk. It is coated magnetically and has tracks,
spots, and sectors for storing data.

Basic Common Examples of Magnetic Disks are:

1. Floppy Disks
2. Hard Disks
3. Zip Disks

Magnetic Disks

 Traditional magnetic disks have the following basic structure:

o One or more platters in the form of disks covered with magnetic media. Hard
disk platters are made of rigid metal, while "floppy" disks are made of more
flexible plastic.
o Each platter has two working surfaces. Older hard disk drives would sometimes
not use the very top or bottom surface of a stack of platters, as these surfaces were
more susceptible to potential damage.
o Each working surface is divided into a number of concentric rings
called tracks. The collection of all tracks that are the same distance from the edge
of the platter, ( i.e. all tracks immediately above one another in the following
diagram ) is called a cylinder.
o Each track is further divided into sectors, traditionally containing 512 bytes of
data each, although some modern disks occasionally use larger sector sizes. (
Sectors also include a header and a trailer, including checksum information
among other things. Larger sector sizes reduce the fraction of the disk consumed
by headers and trailers, but increase internal fragmentation and the amount of disk
that must be marked bad in the case of errors. )
o The data on a hard drive is read by read-write heads. The standard configuration (
shown below ) uses one head per surface, each on a separate arm, and controlled
by a common arm assembly which moves all heads simultaneously from one
cylinder to another. ( Other configurations, including independent read-write
heads, may speed up disk access, but involve serious technical difficulties. )
o The storage capacity of a traditional disk drive is equal to the number of heads (
i.e. the number of working surfaces ), times the number of tracks per surface,
times the number of sectors per track, times the number of bytes per sector. A
particular physical block of data is specified by providing the head-sector-cylinder
number at which it is located.
 Moving-head disk mechanism.

 In operation the disk rotates at high speed, such as 7200 rpm ( 120 revolutions per
second. ) The rate at which data can be transferred from the disk to the computer is
composed of several steps:
o The positioning time, a.k.a. the seek time or random access time is the time
required to move the heads from one cylinder to another, and for the heads to
settle down after the move. This is typically the slowest step in the process and
the predominant bottleneck to overall transfer rates.
o The rotational latency is the amount of time required for the desired sector to
rotate around and come under the read-write head.This can range anywhere from
zero to one full revolution, and on the average will equal one-half revolution. This
is another physical step and is usually the second slowest step behind seek time. (
For a disk rotating at 7200 rpm, the average rotational latency would be 1/2
revolution / 120 revolutions per second, or just over 4 milliseconds, a long time
by computer standards.
o The transfer rate, which is the time required to move the data electronically from
the disk to the computer. ( Some authors may also use the term transfer rate to
refer to the overall transfer rate, including seek time and rotational latency as well
as the electronic data transfer rate. )
 Disk heads "fly" over the surface on a very thin cushion of air. If they should accidentally
contact the disk, then a head crash occurs, which may or may not permanently damage
the disk or even destroy it completely. For this reason it is normal to park the disk heads
when turning a computer off, which means to move the heads off the disk or to an area of
the disk where there is no data stored.
 Floppy disks are normally removable. Hard drives can also be removable, and some are
even hot-swappable, meaning they can be removed while the computer is running, and a
new hard drive inserted in their place.
 Disk drives are connected to the computer via a cable known as the I/O Bus. Some of the
common interface formats include Enhanced Integrated Drive Electronics, EIDE;
Advanced Technology Attachment, ATA; Serial ATA, SATA, Universal Serial Bus,
USB; Fiber Channel, FC, and Small Computer Systems Interface, SCSI.
 The host controller is at the computer end of the I/O bus, and the disk controller is built
into the disk itself. The CPU issues commands to the host controller via I/O ports. Data is
transferred between the magnetic surface and onboard cache by the disk controller, and
then the data is transferred from that cache to the host controller and the motherboard
memory at electronic speeds.

Solid-State Disks - New

 As technologies improve and economics change, old technologies are often used in
different ways. One example of this is the increasing used of solid state disks, or SSDs.
  SSDs use memory technology as a small fast hard disk. Specific implementations may
use either flash memory or DRAM chips protected by a battery to sustain the information
through power cycles.
 Because SSDs have no moving parts they are much faster than traditional hard drives,
and certain problems such as the scheduling of disk accesses simply do not apply.
 However SSDs also have their weaknesses: They are more expensive than hard drives,
generally not as large, and may have shorter life spans.
 SSDs are especially useful as a high-speed cache of hard-disk information that must be
accessed quickly. One example is to store filesystem meta-data, e.g. directory and inode
information, that must be accessed quickly and often. Another variation is a boot disk
containing the OS and some application executables, but no vital user data. SSDs are also
used in laptops to make them smaller, faster, and lighter.
 Because SSDs are so much faster than traditional hard disks, the throughput of the bus
can become a limiting factor, causing some SSDs to be connected directly to the system
PCI bus for example.

Magnetic Tapes

Magnetic tapes were once used for common secondary storage before the days of hard disk
drives, but today are used primarily for backups.

 Accessing a particular spot on a magnetic tape can be slow, but once reading or writing
commences, access speeds are comparable to disk drives.
 Capacities of tape drives can range from 20 to 200 GB, and compression can double that
capacity.

Disk Structure:
 Disks are the mainly used mass storage devices. They provide the bulk of secondary
storage in operating systems today.
 Each modern disk contains concentric tracks and each track is divided into multiple
sectors. The disks are usually arranged as a one dimensional array of blocks, where
blocks are the smallest storage unit.Blocks can also be called as sectors. For each surface
of the disk, there is a read/write desk available. The same tracks on all the surfaces is
known as a cylinder.

 The traditional head-sector-cylinder, HSC numbers are mapped to linear block addresses
by numbering the first sector on the first head on the outermost track as sector 0.
Numbering proceeds with the rest of the sectors on that same track, and then the rest of
the tracks on the same cylinder before proceeding through the rest of the cylinders to the
center of the disk. In modern practice these linear block addresses are used in place of the
HSC numbers for a variety of reasons:
 1. The linear length of tracks near the outer edge of the disk is much longer than for
those tracks located near the center, and therefore it is possible to squeeze many
more sectors onto outer tracks than onto inner ones.
2. All disks have some bad sectors, and therefore disks maintain a few spare sectors
that can be used in place of the bad ones. The mapping of spare sectors to bad
sectors in managed internally to the disk controller.
3. Modern hard drives can have thousands of cylinders, and hundreds of sectors per
track on their outermost tracks. These numbers exceed the range of HSC numbers
for many ( older ) operating systems, and therefore disks can be configured for
any convenient combination of HSC values that falls within the total number of
sectors physically on the drive.
 There is a limit to how closely packed individual bits can be placed on a physical media,
but that limit is growing increasingly more packed as technological advances are made.
 Modern disks pack many more sectors into outer cylinders than inner ones, using one of
two approaches:
o With Constant Linear Velocity, CLV, the density of bits is uniform from cylinder
to cylinder. Because there are more sectors in outer cylinders, the disk spins
slower when reading those cylinders, causing the rate of bits passing under the
read-write head to remain constant. This is the approach used by modern CDs and
DVDs.
o With Constant Angular Velocity, CAV, the disk rotates at a constant angular
speed, with the bit density decreasing on outer cylinders. ( These disks would
have a constant number of sectors per track on all cylinders. )

Disk Scheduling:
There are many disk scheduling algorithms that provide the total head movement for various
requests to the disk. Here are the types of disk scheduling algorithms −

 As mentioned earlier, disk transfer speeds are limited primarily by seek

times and rotational latency. When multiple requests are to be processed there is also
some inherent delay in waiting for other requests to be processed.
 Bandwidth is measured by the amount of data transferred divided by the total amount of
time from the first request being made to the last transfer being completed, ( for a series
of disk requests. )
 Both bandwidth and access time can be improved by processing requests in a good order.
 Disk requests include the disk address, memory address, number of sectors to transfer,
and whether the request is for reading or writing.
All these algorithms are explained using the following requests for the disk −
10,95,23,78,80
First Come First Serve Scheduling (FCFS)
In first come first served scheduling, the requests are serviced in their coming order. This
algorithm is fair as it allows all requests a chance but it does not provide the fastest possible
service. An example of FCFS scheduling is given below −

In the above example, the requests are serviced in the order they appear i.e 10, 95, 23, 78, 80.
The seek head is initially positioned at 50 and it starts from there.
Shortest Seek Time First Scheduling
The requests that are closest to the current head are served first before moving away in shortest
seek time first scheduling algorithm. A problem with SSTF algorithm is that it may cause
starvation for some requests. An example of Shortest Seek Time First Scheduling is given below
−
In the above example, the requests are serviced in the order 23, 10, 78, 80, 95. The seek head is
initially positioned at 50 and it starts from there. 23 is closest to 50 so it is services first. Then 10
is closer to 23 than 78 so it is services next. After this 78, 80 and 95 are serviced.
SCAN Scheduling
In this scheduling algorithm, the head moves towards one direction while servicing all the
requests in that direction until it reaches the end of the disk. After that it starts moving towards
the other direction. In this way, the head continuously scans back and forth across the disk. An
example of SCAN scheduling is given below −

In the above example, the requests are serviced in the order 23, 10, 78, 80, 95. The head is
initially at 50 and moves towards the left while servicing requests 23 and 10. When it reaches
the end of the disk, it starts moving right and services 78, 80 and 95 as they occur.
LOOK Scheduling
LOOK scheduling algorithm is similar to SCAN scheduling but is its practical version. In this
algorithm, the head moves towards one direction while servicing all the requests in that direction
until it reaches the last request. After that it starts moving towards the other direction. An
example of LOOK scheduling is given below −
In the above example, the requests are serviced in the order 23, 10, 78, 80, 95. The head is
initially at 50 and moves towards the left while servicing requests 23 and 10. When it reaches
the last request on the left i.e. 10, it starts moving right and services 78, 80 and 95 as they occur.

(OR)
FCFS Scheduling

 First-Come First-Serve is simple and intrinsically fair, but not very efficient. Consider in
the following sequence the wild swing from cylinder 122 to 14 and then back to 124:

Figure - FCFS disk scheduling.

SSTF Scheduling

 Shortest Seek Time First scheduling is more efficient, but may lead to starvation if a
constant stream of requests arrives for the same general area of the disk.
 SSTF reduces the total head movement to 236 cylinders, down from 640 required for the
same set of requests under FCFS. Note, however that the distance could be reduced still
further to 208 by starting with 37 and then 14 first before processing the rest of the
requests.
 - SSTF disk scheduling.

SCAN Scheduling

 The SCAN algorithm, the elevator algorithm moves back and forth from one end of the
disk to the other, similarly to an elevator processing requests in a tall building.

Figure - SCAN disk scheduling.

  Under the SCAN algorithm, If a request arrives just ahead of the moving head then it will
be processed right away, but if it arrives just after the head has passed, then it will have to
wait for the head to pass going the other way on the return trip. This leads to a fairly wide
variation in access times which can be improved upon.
 Consider, for example, when the head reaches the high end of the disk: Requests with
high cylinder numbers just missed the passing head, which means they are all fairly
recent requests, whereas requests with low numbers may have been waiting for a much
longer time. Making the return scan from high to low then ends up accessing recent
requests first and making older requests wait that much longer.

C-SCAN Scheduling

 The Circular-SCAN algorithm improves upon SCAN by treating all requests in a circular
queue fashion - Once the head reaches the end of the disk, it returns to the other end
without processing any requests, and then starts again from the beginning of the disk:

Figure C-SCAN disk scheduling.

LOOK Scheduling

 LOOK scheduling improves upon SCAN by looking ahead at the queue of pending
requests, and not moving the heads any farther towards the end of the disk than is
necessary. The following diagram illustrates the circular form of LOOK:
 
Figure - C-LOOK disk scheduling.

Selection of a Disk-Scheduling Algorithm

 With very low loads all algorithms are equal, since there will normally only be one
request to process at a time.
 For slightly larger loads, SSTF offers better performance than FCFS, but may lead to
starvation when loads become heavy enough.
 For busier systems, SCAN and LOOK algorithms eliminate starvation problems.
 The actual optimal algorithm may be something even more complex than those discussed
here, but the incremental improvements are generally not worth the additional overhead.
 Some improvement to overall filesystem access times can be made by intelligent
placement of directory and/or inode information. If those structures are placed in the
middle of the disk instead of at the beginning of the disk, then the maximum distance
from those structures to data blocks is reduced to only one-half of the disk size. If those
structures can be further distributed and furthermore have their data blocks stored as
close as possible to the corresponding directory structures, then that reduces still further
the overall time to find the disk block numbers and then access the corresponding data
blocks.
 On modern disks the rotational latency can be almost as significant as the seek time,
however it is not within the OSes control to account for that, because modern disks do
not reveal their internal sector mapping schemes, ( particularly when bad blocks have
been remapped to spare sectors. )
o Some disk manufacturers provide for disk scheduling algorithms directly on their
disk controllers, ( which do know the actual geometry of the disk as well as any
remapping ), so that if a series of requests are sent from the computer to the
controller then those requests can be processed in an optimal order.
o Unfortunately there are some considerations that the OS must take into account
that are beyond the abilities of the on-board disk-scheduling algorithms, such as
priorities of some requests over others, or the need to process certain requests in a
particular order. For this reason OSes may elect to spoon-feed requests to the disk
controller one at a time in certain situations.
Disk Management

Disk Formatting

 Before a disk can be used, it has to be low-level formatted, which means laying down all
of the headers and trailers marking the beginning and ends of each sector. Included in the
header and trailer are the linear sector numbers, and error-correcting codes, ECC, which
allow damaged sectors to not only be detected, but in many cases for the damaged data to
be recovered ( depending on the extent of the damage. ) Sector sizes are traditionally 512
bytes, but may be larger, particularly in larger drives.
 ECC calculation is performed with every disk read or write, and if damage is detected but
the data is recoverable, then a soft error has occurred. Soft errors are generally handled
by the on-board disk controller, and never seen by the OS. ( See below. )
 Once the disk is low-level formatted, the next step is to partition the drive into one or
more separate partitions. This step must be completed even if the disk is to be used as a
single large partition, so that the partition table can be written to the beginning of the
disk.
 After partitioning, then the filesystems must be logically formatted, which involves
laying down the master directory information ( FAT table or inode structure ), initializing
free lists, and creating at least the root directory of the filesystem. ( Disk partitions which
are to be used as raw devices are not logically formatted. This saves the overhead and
disk space of the filesystem structure, but requires that the application program manage
its own disk storage requirements. )

Boot Block

 Computer ROM contains a bootstrap program ( OS independent ) with just enough code
to find the first sector on the first hard drive on the first controller, load that sector into
memory, and transfer control over to it. ( The ROM bootstrap program may look in
floppy and/or CD drives before accessing the hard drive, and is smart enough to
recognize whether it has found valid boot code or not. )
 The first sector on the hard drive is known as the Master Boot Record, MBR, and
contains a very small amount of code in addition to the partition table. The partition table
documents how the disk is partitioned into logical disks, and indicates specifically which
partition is the active or boot partition.
 The boot program then looks to the active partition to find an operating system, possibly
loading up a slightly larger / more advanced boot program along the way.
 In a dual-boot ( or larger multi-boot ) system, the user may be given a choice of which
operating system to boot, with a default action to be taken in the event of no response
within some time frame.
 Once the kernel is found by the boot program, it is loaded into memory and then control
is transferred over to the OS. The kernel will normally continue the boot process by
initializing all important kernel data structures, launching important system services ( e.g.
network daemons, sched, init, etc. ), and finally providing one or more login prompts.
Boot options at this stage may include single-user a.k.a. maintenance or safe modes, in
 which very few system services are started - These modes are designed for system
administrators to repair problems or otherwise maintain the system.

Figure - Booting from disk in Windows 2000.

Bad Blocks

 No disk can be manufactured to 100% perfection, and all physical objects wear out over
time. For these reasons all disks are shipped with a few bad blocks, and additional blocks
can be expected to go bad slowly over time. If a large number of blocks go bad then the
entire disk will need to be replaced, but a few here and there can be handled through
other means.
 In the old days, bad blocks had to be checked for manually. Formatting of the disk or
running certain disk-analysis tools would identify bad blocks, and attempt to read the data
off of them one last time through repeated tries. Then the bad blocks would be mapped
out and taken out of future service. Sometimes the data could be recovered, and
sometimes it was lost forever. ( Disk analysis tools could be either destructive or non-
destructive. )
 Modern disk controllers make much better use of the error-correcting codes, so that bad
blocks can be detected earlier and the data usually recovered. ( Recall that blocks are
tested with every write as well as with every read, so often errors can be detected before
the write operation is complete, and the data simply written to a different sector instead. )
 Note that re-mapping of sectors from their normal linear progression can throw off the
disk scheduling optimization of the OS, especially if the replacement sector is physically
far away from the sector it is replacing. For this reason most disks normally keep a few
spare sectors on each cylinder, as well as at least one spare cylinder. Whenever possible a
bad sector will be mapped to another sector on the same cylinder, or at least a cylinder as
close as possible. Sector slipping may also be performed, in which all sectors between
the bad sector and the replacement sector are moved down by one, so that the linear
progression of sector numbers can be maintained.
  If the data on a bad block cannot be recovered, then a hard error has occurred., which
requires replacing the file(s) from backups, or rebuilding them from scratch.

Directory Implementation In Operating System:

Directory implementation in the operating system can be done using Singly Linked List and
Hash table. The efficiency, reliability, and performance of a file system are greatly affected by
the selection of directory-allocation and directory-management algorithms. There are
numerous ways in which the directories can be implemented. But we need to choose an
appropriate directory implementation algorithm that enhances the performance of the system.

Directory Implementation using Singly Linked List

The implementation of directories using a singly linked list is easy to program but is time-
consuming to execute. Here we implement a directory by using a linear list of filenames with
pointers to the data blocks.
the data blocks.

Directory Implementation Using Singly Linked List

 To create a new file the entire list has to be checked such that the new directory does not
exist previously.
 The new directory then can be added to the end of the list or at the beginning of the list.
 In order to delete a file, we first search the directory with the name of the file to be deleted.
After searching we can delete that file by releasing the space allocated to it.
 To reuse the directory entry we can mark that entry as unused or we can append it to the list
of free directories.
 To delete a file linked list is the best choice as it takes less time.
Disadvantage
The main disadvantage of using a linked list is that when the user needs to find a file the user
has to do a linear search. In today’s world directory information is used quite frequently and
linked list implementation results in slow access to a file. So the operating system maintains a
cache to store the most recently used directory information.

Directory Implementation using Hash Table

An alternative data structure that can be used for directory implementation is a hash table. It
overcomes the major drawbacks of directory implementation using a linked list. In this
method, we use a hash table along with the linked list. Here the linked list stores the directory
entries, but a hash data structure is used in combination with the linked list.

n the hash table for each pair in the directory key-value pair is generated. The hash function on
the file name determines the key and this key points to the corresponding file stored in the
directory. This method efficiently decreases the directory search time as the entire list will not
be searched on every operation. Using the keys the hash table entries are checked and when the
file is found it is fetched.

Directory Implementation Using Hash Table

Disadvantage:
The major drawback of using the hash table is that generally, it has a fixed size and its
dependency on size. But this method is usually faster than linear search through an entire
directory using a linked list.
I/O Systems:

 Management of I/O devices is a very important part of the operating system - so

important and so varied that entire I/O subsystems are devoted to its operation. ( Consider
the range of devices on a modern computer, from mice, keyboards, disk drives, display
adapters, USB devices, network connections, audio I/O, printers, special devices for the
handicapped, and many special-purpose peripherals. )
 I/O Subsystems must contend with two ( conflicting? ) trends: (1) The gravitation
towards standard interfaces for a wide range of devices, making it easier to add newly
developed devices to existing systems, and (2) the development of entirely new types of
devices, for which the existing standard interfaces are not always easy to apply.
 Device drivers are modules that can be plugged into an OS to handle a particular device
or category of similar devices.

I/O Hardware:

 I/O devices can be roughly categorized as storage, communications, user-interface, and

other
 Devices communicate with the computer via signals sent over wires or through the air.
 Devices connect with the computer via ports, e.g. a serial or parallel port.
 A common set of wires connecting multiple devices is termed a bus.
o Buses include rigid protocols for the types of messages that can be sent across the
bus and the procedures for resolving contention issues.
o Figure 13.1 below illustrates three of the four bus types commonly found in a
modern PC:
1. The PCI bus connects high-speed high-bandwidth devices to the memory
subsystem ( and the CPU. )
2. The expansion bus connects slower low-bandwidth devices, which
typically deliver data one character at a time ( with buffering. )
3. The SCSI bus connects a number of SCSI devices to a common SCSI
controller.
4. A daisy-chain bus, ( not shown) is when a string of devices is connected
to each other like beads on a chain, and only one of the devices is directly
connected to the host.
 Figure - A typical PC bus structure.

 One way of communicating with devices is through registers associated with each port.
Registers may be one to four bytes in size, and may typically include ( a subset of ) the
following four:
1. The data-in register is read by the host to get input from the device.
2. The data-out register is written by the host to send output.
3. The status register has bits read by the host to ascertain the status of the device,
such as idle, ready for input, busy, error, transaction complete, etc.
4. The control register has bits written by the host to issue commands or to change
settings of the device such as parity checking, word length, or full- versus half-
duplex operation.
 Figure 13.2 shows some of the most common I/O port address ranges.
 Figure - Device I/O port locations on PCs ( partial ).

 Another technique for communicating with devices is memory-mapped I/O.

o In this case a certain portion of the processor's address space is mapped to the
device, and communications occur by reading and writing directly to/from those
memory areas.
o Memory-mapped I/O is suitable for devices which must move large quantities of
data quickly, such as graphics cards.
o Memory-mapped I/O can be used either instead of or more often in combination
with traditional registers. For example, graphics cards still use registers for
control information such as setting the video mode.
o A potential problem exists with memory-mapped I/O, if a process is allowed to
write directly to the address space used by a memory-mapped I/O device.
o ( Note: Memory-mapped I/O is not the same thing as direct memory access,
DMA. See section 13.2.3 below. )

1. Polling

 One simple means of device handshaking involves polling:

1. The host repeatedly checks the busy bit on the device until it becomes clear.
2. The host writes a byte of data into the data-out register, and sets the write bit in
the command register ( in either order. )
3. The host sets the command ready bit in the command register to notify the device
of the pending command.
4. When the device controller sees the command-ready bit set, it first sets the busy
bit.
5. Then the device controller reads the command register, sees the write bit set,
reads the byte of data from the data-out register, and outputs the byte of data.
 6. The device controller then clears the error bit in the status register, the command-
ready bit, and finally clears the busy bit, signaling the completion of the
operation.
 Polling can be very fast and efficient, if both the device and the controller are fast and if
there is significant data to transfer. It becomes inefficient, however, if the host must wait
a long time in the busy loop waiting for the device, or if frequent checks need to be made
for data that is infrequently there.

2. Interrupts

 Interrupts allow devices to notify the CPU when they have data to transfer or when an
operation is complete, allowing the CPU to perform other duties when no I/O transfers
need its immediate attention.
 The CPU has an interrupt-request line that is sensed after every instruction.
o A device's controller raises an interrupt by asserting a signal on the interrupt
request line.
o The CPU then performs a state save, and transfers control to the interrupt
handler routine at a fixed address in memory. ( The CPU catches the interrupt
and dispatches the interrupt handler. )
o The interrupt handler determines the cause of the interrupt, performs the
necessary processing, performs a state restore, and executes a return from
interrupt instruction to return control to the CPU. ( The interrupt
handler clears the interrupt by servicing the device. )
 ( Note that the state restored does not need to be the same state as the one
that was saved when the interrupt went off. See below for an example
involving time-slicing. )

 Figure illustrates the interrupt-driven I/O procedure:
 Figure - Interrupt-driven I/O cycle.

 The above description is adequate for simple interrupt-driven I/O, but there are three
needs in modern computing which complicate the picture:
1. The need to defer interrupt handling during critical processing,
2. The need to determine which interrupt handler to invoke, without having to poll
all devices to see which one needs attention, and
3. The need for multi-level interrupts, so the system can differentiate between high-
and low-priority interrupts for proper response.
 These issues are handled in modern computer architectures with interrupt-
controller hardware.
o Most CPUs now have two interrupt-request lines: One that is non-maskable for
critical error conditions and one that is maskable, that the CPU can temporarily
ignore during critical processing.
o The interrupt mechanism accepts an address, which is usually one of a small set
of numbers for an offset into a table called the interrupt vector. This table
( usually located at physical address zero ? ) holds the addresses of routines
prepared to process specific interrupts.
o The number of possible interrupt handlers still exceeds the range of defined
interrupt numbers, so multiple handlers can be interrupt chained. Effectively the
addresses held in the interrupt vectors are the head pointers for linked-lists of
interrupt handlers.
o Figure 13.4 shows the Intel Pentium interrupt vector. Interrupts 0 to 31 are non-
maskable and reserved for serious hardware and other errors. Maskable interrupts,
including normal device I/O interrupts begin at interrupt 32.
o Modern interrupt hardware also supports interrupt priority levels, allowing
systems to mask off only lower-priority interrupts while servicing a high-priority
interrupt, or conversely to allow a high-priority signal to interrupt the processing
of a low-priority one.

Figure - Intel Pentium processor event-vector table.

  At boot time the system determines which devices are present, and loads the appropriate
handler addresses into the interrupt table.
 During operation, devices signal errors or the completion of commands via interrupts.
 Exceptions, such as dividing by zero, invalid memory accesses, or attempts to access
kernel mode instructions can be signaled via interrupts.
 Time slicing and context switches can also be implemented using the interrupt
mechanism.
o The scheduler sets a hardware timer before transferring control over to a user
process.
o When the timer raises the interrupt request line, the CPU performs a state-save,
and transfers control over to the proper interrupt handler, which in turn runs the
scheduler.
o The scheduler does a state-restore of a different process before resetting the timer
and issuing the return-from-interrupt instruction.
 A similar example involves the paging system for virtual memory - A page fault causes
an interrupt, which in turn issues an I/O request and a context switch as described above,
moving the interrupted process into the wait queue and selecting a different process to
run. When the I/O request has completed ( i.e. when the requested page has been loaded
up into physical memory ), then the device interrupts, and the interrupt handler moves the
process from the wait queue into the ready queue, ( or depending on scheduling
algorithms and policies, may go ahead and context switch it back onto the CPU. )
 System calls are implemented via software interrupts, a.k.a. traps. When a ( library )
program needs work performed in kernel mode, it sets command information and
possibly data addresses in certain registers, and then raises a software interrupt. ( E.g. 21
hex in DOS. ) The system does a state save and then calls on the proper interrupt handler
to process the request in kernel mode. Software interrupts generally have low priority, as
they are not as urgent as devices with limited buffering space.
 Interrupts are also used to control kernel operations, and to schedule activities for optimal
performance. For example, the completion of a disk read operation
involves two interrupts:
o A high-priority interrupt acknowledges the device completion, and issues the next
disk request so that the hardware does not sit idle.
o A lower-priority interrupt transfers the data from the kernel memory space to the
user space, and then transfers the process from the waiting queue to the ready
queue.
 The Solaris OS uses a multi-threaded kernel and priority threads to assign different
threads to different interrupt handlers. This allows for the "simultaneous" handling of
multiple interrupts, and the assurance that high-priority interrupts will take precedence
over low-priority ones and over user processes.

Direct Memory Access

 For devices that transfer large quantities of data ( such as disk controllers ), it is wasteful
to tie up the CPU transferring data in and out of registers one byte at a time.
 Instead this work can be off-loaded to a special processor, known as the Direct Memory
Access, DMA, Controller.
 The host issues a command to the DMA controller, indicating the location where the data
is located, the location where the data is to be transferred to, and the number of bytes of
data to transfer. The DMA controller handles the data transfer, and then interrupts the
CPU when the transfer is complete.
 A simple DMA controller is a standard component in modern PCs, and many bus-
mastering I/O cards contain their own DMA hardware.
 Handshaking between DMA controllers and their devices is accomplished through two
wires called the DMA-request and DMA-acknowledge wires.
 While the DMA transfer is going on the CPU does not have access to the PCI bus (
including main memory ), but it does have access to its internal registers and primary and
secondary caches.
 DMA can be done in terms of either physical addresses or virtual addresses that are
mapped to physical addresses. The latter approach is known as Direct Virtual Memory
Access, DVMA, and allows direct data transfer from one memory-mapped device to
another without using the main memory chips.
 Direct DMA access by user processes can speed up operations, but is generally forbidden
by modern systems for security and protection reasons. ( I.e. DMA is a kernel-mode
operation. )
 Figure below illustrates the DMA process.

Figure - Steps in a DMA transfer.

I/O Hardware Summary

Application I/O Interface

 User application access to a wide variety of different devices is accomplished through

layering, and through encapsulating all of the device-specific code into device drivers,
while application layers are presented with a common interface for all ( or at least large
general categories of ) devices.

Figure - A kernel I/O structure.

 Devices differ on many different dimensions, as outlined in Following Figure

 Figure - Characteristics of I/O devices.

 Most devices can be characterized as either block I/O, character I/O, memory mapped file
access, or network sockets. A few devices are special, such as time-of-day clock and the
system timer.
 Most OSes also have an escape, or back door, which allows applications to send
commands directly to device drivers if needed. In UNIX this is the ioctl( ) system call (
I/O Control ). Ioctl( ) takes three arguments - The file descriptor for the device driver
being accessed, an integer indicating the desired function to be performed, and an address
used for communicating or transferring additional information.

1. Block and Character Devices

 Block devices are accessed a block at a time, and are indicated by a "b" as the first
character in a long listing on UNIX systems. Operations supported include read( ), write(
), and seek( ).
o Accessing blocks on a hard drive directly ( without going through the filesystem
structure ) is called raw I/O, and can speed up certain operations by bypassing the
buffering and locking normally conducted by the OS. ( It then becomes the
application's responsibility to manage those issues. )
o A new alternative is direct I/O, which uses the normal filesystem access, but
which disables buffering and locking operations.
 Memory-mapped file I/O can be layered on top of block-device drivers.
 o Rather than reading in the entire file, it is mapped to a range of memory
addresses, and then paged into memory as needed using the virtual memory
system.
o Access to the file is then accomplished through normal memory accesses, rather
than through read( ) and write( ) system calls. This approach is commonly used
for executable program code.
 Character devices are accessed one byte at a time, and are indicated by a "c" in UNIX
long listings. Supported operations include get( ) and put( ), with more advanced
functionality such as reading an entire line supported by higher-level library routines.

2 .Network Devices

 Because network access is inherently different from local disk access, most systems
provide a separate interface for network devices.
 One common and popular interface is the socket interface, which acts like a cable or
pipeline connecting two networked entities. Data can be put into the socket at one end,
and read out sequentially at the other end. Sockets are normally full-duplex, allowing for
bi-directional data transfer.
 The select( ) system call allows servers ( or other applications ) to identify sockets which
have data waiting, without having to poll all available sockets.

3 .Clocks and Timers

 Three types of time services are commonly needed in modern systems:

o Get the current time of day.
o Get the elapsed time ( system or wall clock ) since a previous event.
o Set a timer to trigger event X at time T.
 Unfortunately time operations are not standard across all systems.
 A programmable interrupt timer, PIT can be used to trigger operations and to measure
elapsed time. It can be set to trigger an interrupt at a specific future time, or to trigger
interrupts periodically on a regular basis.
o The scheduler uses a PIT to trigger interrupts for ending time slices.
o The disk system may use a PIT to schedule periodic maintenance cleanup, such as
flushing buffers to disk.
o Networks use PIT to abort or repeat operations that are taking too long to
complete. I.e. resending packets if an acknowledgement is not received before the
timer goes off.
o More timers than actually exist can be simulated by maintaining an ordered list of
timer events, and setting the physical timer to go off when the next scheduled
event should occur.
 On most systems the system clock is implemented by counting interrupts generated by
the PIT. Unfortunately this is limited in its resolution to the interrupt frequency of the
PIT, and may be subject to some drift over time. An alternate approach is to provide
direct access to a high frequency hardware counter, which provides much higher
resolution and accuracy, but which does not support interrupts.
4. Blocking and Non-blocking I/O

 With blocking I/O a process is moved to the wait queue when an I/O request is made, and
moved back to the ready queue when the request completes, allowing other processes to
run in the meantime.
 With non-blocking I/O the I/O request returns immediately, whether the requested I/O
operation has ( completely ) occurred or not. This allows the process to check for
available data without getting hung completely if it is not there.
 One approach for programmers to implement non-blocking I/O is to have a multi-
threaded application, in which one thread makes blocking I/O calls ( say to read a
keyboard or mouse ), while other threads continue to update the screen or perform other
tasks.
 A subtle variation of the non-blocking I/O is the asynchronous I/O, in which the I/O
request returns immediately allowing the process to continue on with other tasks, and
then the process is notified ( via changing a process variable, or a software interrupt, or a
callback function ) when the I/O operation has completed and the data is available for
use. ( The regular non-blocking I/O returns immediately with whatever results are
available, but does not complete the operation and notify the process later. )

Figure - Two I/O methods: (a) synchronous and (b) asynchronous.

5. Vectored I/O ( NEW )

Kernel I/O Subsystem:

I/O Scheduling

 Scheduling I/O requests can greatly improve overall efficiency. Priorities can also play a
part in request scheduling.
  The classic example is the scheduling of disk accesses, as discussed in detail in chapter
12.
 Buffering and caching can also help, and can allow for more flexible scheduling options.
 On systems with many devices, separate request queues are often kept for each device:

Figure - Device-status table.

Buffering

 Buffering of I/O is performed for ( at least ) 3 major reasons:

1. Speed differences between two devices. ( See Figure 13.10 below. ) A slow
device may write data into a buffer, and when the buffer is full, the entire buffer is
sent to the fast device all at once. So that the slow device still has somewhere to
write while this is going on, a second buffer is used, and the two buffers alternate
as each becomes full. This is known as double buffering. ( Double buffering is
often used in ( animated ) graphics, so that one screen image can be generated in a
buffer while the other ( completed ) buffer is displayed on the screen. This
prevents the user from ever seeing any half-finished screen images. )
2. Data transfer size differences. Buffers are used in particular in networking
systems to break messages up into smaller packets for transfer, and then for re-
assembly at the receiving side.
3. To support copy semantics. For example, when an application makes a request for
a disk write, the data is copied from the user's memory area into a kernel buffer.
Now the application can change their copy of the data, but the data which
 eventually gets written out to disk is the version of the data at the time the write
request was made.

Figure - Sun Enterprise 6000 device-transfer rates ( logarithmic ).

Caching

 Caching involves keeping a copy of data in a faster-access location than where the data is
normally stored.
 Buffering and caching are very similar, except that a buffer may hold the only copy of a
given data item, whereas a cache is just a duplicate copy of some other data stored
elsewhere.
 Buffering and caching go hand-in-hand, and often the same storage space may be used
for both purposes. For example, after a buffer is written to disk, then the copy in memory
can be used as a cached copy, (until that buffer is needed for other purposes. )
Spooling and Device Reservation

 A spool ( Simultaneous Peripheral Operations On-Line ) buffers data for ( peripheral )

devices such as printers that cannot support interleaved data streams.
 If multiple processes want to print at the same time, they each send their print data to files
stored in the spool directory. When each file is closed, then the application sees that print
job as complete, and the print scheduler sends each file to the appropriate printer one at a
time.
 Support is provided for viewing the spool queues, removing jobs from the queues,
moving jobs from one queue to another queue, and in some cases changing the priorities
of jobs in the queues.
 Spool queues can be general ( any laser printer ) or specific ( printer number 42. )
 OSes can also provide support for processes to request / get exclusive access to a
particular device, and/or to wait until a device becomes available.

Error Handling

 I/O requests can fail for many reasons, either transient ( buffers overflow ) or permanent
( disk crash ).
 I/O requests usually return an error bit ( or more ) indicating the problem. UNIX systems
also set the global variable errno to one of a hundred or so well-defined values to indicate
the specific error that has occurred. ( See errno.h for a complete listing, or man errno. )
 Some devices, such as SCSI devices, are capable of providing much more detailed
information about errors, and even keep an on-board error log that can be requested by
the host.

I/O Protection

 The I/O system must protect against either accidental or deliberate erroneous I/O.
 User applications are not allowed to perform I/O in user mode - All I/O requests are
handled through system calls that must be performed in kernel mode.
 Memory mapped areas and I/O ports must be protected by the memory management
system, but access to these areas cannot be totally denied to user programs. ( Video
games and some other applications need to be able to write directly to video memory for
optimal performance for example. ) Instead the memory protection system restricts access
so that only one process at a time can access particular parts of memory, such as the
portion of the screen memory corresponding to a particular window.
 Figure - Use of a system call to perform I/O.

Kernel Data Structures

 The kernel maintains a number of important data structures pertaining to the I/O system,
such as the open file table.
 These structures are object-oriented, and flexible to allow access to a wide variety of I/O
devices through a common interface. ( See Figure 13.12 below. )
 Windows NT carries the object-orientation one step further, implementing I/O as a
message-passing system from the source through various intermediaries to the device.
 Figure - UNIX I/O kernel structure.

Kernel I/O Subsystem Summary

Transforming I/O Requests to Hardware Operations

 Users request data using file names, which must ultimately be mapped to specific blocks
of data from a specific device managed by a specific device driver.
 DOS uses the colon separator to specify a particular device ( e.g. C:, LPT:, etc. )
 UNIX uses a mount table to map filename prefixes ( e.g. /usr ) to specific mounted
devices. Where multiple entries in the mount table match different prefixes of the
filename the one that matches the longest prefix is chosen. ( e.g. /usr/home instead of /usr
where both exist in the mount table and both match the desired file. )
 UNIX uses special device files, usually located in /dev, to represent and access physical
devices directly.
o Each device file has a major and minor number associated with it, stored and
displayed where the file size would normally go.
o The major number is an index into a table of device drivers, and indicates which
device driver handles this device. ( E.g. the disk drive handler. )
o The minor number is a parameter passed to the device driver, and indicates which
specific device is to be accessed, out of the many which may be handled by a
particular device driver. ( e.g. a particular disk drive or partition. )
 A series of lookup tables and mappings makes the access of different devices flexible,
and somewhat transparent to users.
 Figure 13.13 illustrates the steps taken to process a ( blocking ) read request:
 Figure - The life cycle of an I/O request.

STREAMS ( Optional )

 The streams mechanism in UNIX provides a bi-directional pipeline between a user

process and a device driver, onto which additional modules can be added.
 The user process interacts with the stream head.
 The device driver interacts with the device end.
 Zero or more stream modules can be pushed onto the stream, using ioctl( ). These
modules may filter and/or modify the data as it passes through the stream.
 Each module has a read queue and a write queue.
 Flow control can be optionally supported, in which case each module will buffer data
until the adjacent module is ready to receive it. Without flow control, data is passed along
as soon as it is ready.
 User processes communicate with the stream head using either read( ) and write( ) ( or
putmsg( ) and getmsg( ) for message passing. )
 Streams I/O is asynchronous ( non-blocking ), except for the interface between the user
process and the stream head.
 The device driver must respond to interrupts from its device - If the adjacent module is
not prepared to accept data and the device driver's buffers are all full, then data is
typically dropped.
 Streams are widely used in UNIX, and are the preferred approach for device drivers. For
example, UNIX implements sockets using streams.

Figure - The SREAMS structure.

UNIT-I TOPIC

Performance ( Optional )

 The I/O system is a major factor in overall system performance, and can place heavy
loads on other major components of the system ( interrupt handling, process switching,
memory access, bus contention, and CPU load for device drivers just to name a few. )
 Interrupt handling can be relatively expensive ( slow ), which causes programmed I/O to
be faster than interrupt-driven I/O when the time spent busy waiting is not excessive.
 Network traffic can also put a heavy load on the system. Consider for example the
sequence of events that occur when a single character is typed in a telnet session, as
shown in figure. ( And the fact that a similar set of events must happen in reverse to echo
back the character that was typed. ) Sun uses in-kernel threads for the telnet daemon,
increasing the supportable number of simultaneous telnet sessions from the hundreds to
the thousands.

Figure - Intercomputer communications

 Other systems use front-end processors to off-load some of the work of I/O processing
from the CPU. For example a terminal concentrator can multiplex with hundreds of
terminals on a single port on a large computer.
 Several principles can be employed to increase the overall efficiency of I/O processing:
1. Reduce the number of context switches.
2. Reduce the number of times data must be copied.
3. Reduce interrupt frequency, using large transfers, buffering, and polling where
appropriate.
4. Increase concurrency using DMA.
5. Move processing primitives into hardware, allowing their operation to be
concurrent with CPU and bus operations.
6. Balance CPU, memory, bus, and I/O operations, so a bottleneck in one does not
idle all the others.
 The development of new I/O algorithms often follows a progression from application
level code to on-board hardware implementation, as shown in Figure 13.16. Lower-level
implementations are faster and more efficient, but higher-level ones are more flexible and
easier to modify. Hardware-level functionality may also be harder for higher-level
authorities ( e.g. the kernel ) to control.

Figure : Device functionality progression