Three popular ways to access I/O devices:

1. Programmed I/O: means the CPU is involved all the way through the I/O process. The
CPU issues command to initiate the I/O device, tell it what to do, and wait until the I/O
process is finished. Almost all I/O devices are slower than the CPU, so the latter has to be
idle for a long time, which results in inefficiency.

2. Interrupt-driven I/O: otherwise aims to let the CPU and the I/O devices work
simultaneously. With this scheme, the CPU, after issuing a command on behalf of a
process to start an I/O operation, may turn to execute another process. When the I/O
operation completes, an I/O interrupt will be generated to signal the CPU to resume the
former process. Although switching between different processes involves overhead, it is
still worth doing unless the context switching is too frequent.

3. DMA: When a large amount of data needs to be transferred to/from an I/O device, it is
not realistic any longer to take the interrupt-driven approach because frequent context
switching is unavoidable in this case. To deal with this problem, the DMA approach is
taken, in which a DMA controller is responsible to control the data exchange between
main memory and an I/O device. What the CPU needs to do is simply to send necessary
information to the DMA controller at the very beginning. An interrupt is also generated
finally so that the CPU knows the completion of the whole DMA process.
Secondary Storage and Disk Scheduling Algorithms
Secondary storage devices are those devices whose memory is non volatile, meaning; the stored
data will be intact even if the system is turned off. Here are a few things worth noting about
secondary storage.

 Secondary storage is also called auxiliary storage.

 Secondary storage is less expensive when compared to primary memory like RAMs.
 The speed of the secondary storage is also lesser than that of primary storage.
 Hence, the data which is less frequently accessed is kept in the secondary storage.
 A few examples are magnetic disks, magnetic tapes, removable thumb drives etc.

Magnetic Disk Structure

In modern computers, most of the secondary storage is in the form of magnetic disks. Hence,
knowing the structure of a magnetic disk is necessary to understand how the data in the disk is
accessed by the computer.

Structure of a magnetic disk

A magnetic disk contains several platters. Each platter is divided into circular shaped tracks.
The length of the tracks near the centre is less than the length of the tracks farther from the
centre. Each track is further divided into sectors, as shown in the figure.
Tracks of the same distance from centre form a cylinder. A read-write head is used to read data
from a sector of the magnetic disk.
The speed of the disk is measured as two parts:

 Transfer rate: This is the rate at which the data moves from disk to the computer.
 Random access time: It is the sum of the seek time and rotational latency.

Seek time is the time taken by the arm to move to the required track. Rotational latency is
defined as the time taken by the arm to reach the required sector in the track.
Even though the disk is arranged as sectors and tracks physically, the data is logically arranged
and addressed as an array of blocks of fixed size. The size of a block can be 512 or 1024 bytes.
Each logical block is mapped with a sector on the disk, sequentially. In this way, each sector in
the disk will have a logical address.

Disk Scheduling Algorithms

On a typical multiprogramming system, there will usually be multiple disk access requests at any
point of time. So those requests must be scheduled to achieve good efficiency. Disk scheduling is
similar to process scheduling. Some of the disk scheduling algorithms is described below.

First Come First Serve

This algorithm performs requests in the same order asked by the system. Let's take an example
where the queue has the following requests with cylinder numbers as follows:
98, 183, 37, 122, 14, 124, 65, 67
Assume the head is initially at cylinder 56. The head moves in the given order in the queue
i.e., 56→98→183→...→67.
Shortest Seek Time First (SSTF)
Here the position which is closest to the current head position is chosen first. Consider the
previous example where disk queue looks like,
98, 183, 37, 122, 14, 124, 65, 67
Assume the head is initially at cylinder 56. The next closest cylinder to 56 is 65, and then the
next nearest one is 67, then 37, 14, so on.

SCAN algorithm
This algorithm is also called the elevator algorithm because of it's behavior. Here, first the head
moves in a direction (say backward) and covers all the requests in the path. Then it moves in the
opposite direction and covers the remaining requests in the path. This behavior is similar to that
of an elevator. Let's take the previous example,
98, 183, 37, 122, 14, 124, 65, 67
Assume the head is initially at cylinder 56. The head moves in backward direction and
accesses 37and 14. Then it goes in the opposite direction and accesses the cylinders as they come
in the path.
File
A file is a named collection of related information that is recorded on
secondary storage such as magnetic disks, magnetic tapes and optical
disks. In general, a file is a sequence of bits, bytes, lines or records whose
meaning is defined by the files creator and user.

File Structure
A File Structure should be according to a required format that the operating
system can understand.

 A file has a certain defined structure according to its type.

 A text file is a sequence of characters organized into lines.

 A source file is a sequence of procedures and functions.

 An object file is a sequence of bytes organized into blocks that are understandable by the
machine.

 When operating system defines different file structures, it also contains the code to
support these file structure. Unix, MS-DOS support minimum number of file structure.

File Type
File type refers to the ability of the operating system to distinguish different
types of file such as text files source files and binary files etc. Many
operating systems support many types of files. Operating system like MS-
DOS and UNIX have the following types of files −

Ordinary files

 These are the files that contain user information.

 These may have text, databases or executable program.

 The user can apply various operations on such files like add, modify, delete or even
remove the entire file.

Directory files

 These files contain list of file names and other information related to these files.

Special files

 These files are also known as device files.

  These files represent physical device like disks, terminals, printers, networks, tape drive
etc.

These files are of two types −

 Character special files − data is handled character by character as in case of terminals

or printers.

 Block special files − data is handled in blocks as in the case of disks and tapes.

File Access Mechanisms

File access mechanism refers to the manner in which the records of a file
may be accessed. There are several ways to access files −

 Sequential access

 Direct/Random access

 Indexed sequential access

Sequential access
A sequential access is that in which the records are accessed in some
sequence, i.e., the information in the file is processed in order, one record
after the other. This access method is the most primitive one. Example:
Compilers usually access files in this fashion.

Direct/Random access
 Random access file organization provides, accessing the records directly.

 Each record has its own address on the file with by the help of which it can be directly
accessed for reading or writing.

 The records need not be in any sequence within the file and they need not be in adjacent
locations on the storage medium.

Indexed sequential access

 This mechanism is built up on base of sequential access.

 An index is created for each file which contains pointers to various blocks.

 Index is searched sequentially and its pointer is used to access the file directly.

Space Allocation
Files are allocated disk spaces by operating system. Operating systems
deploy following three main ways to allocate disk space to files.
  Contiguous Allocation

 Linked Allocation

 Indexed Allocation

Contiguous Allocation

 Each file occupies a contiguous address space on disk.

 Assigned disk address is in linear order.

 Easy to implement.

 External fragmentation is a major issue with this type of allocation technique.

Linked Allocation

 Each file carries a list of links to disk blocks.

 Directory contains link / pointer to first block of a file.

 No external fragmentation

 Effectively used in sequential access file.

 Inefficient in case of direct access file.

Indexed Allocation

 Provides solutions to problems of contiguous and linked allocation.

 A index block is created having all pointers to files.

 Each file has its own index block which stores the addresses of disk space occupied by
the file.

 Directory contains the addresses of index blocks of files.

 File Allocation Methods
There are various methods which can be used to allocate disk space to the files.
Selection of an appropriate allocation method will significantly affect the performance
and efficiency of the system. Allocation method provides a way in which the disk will
be utilized and the files will be accessed.

The main idea behind these methods is to provide:

 Efficient disk space utilization.
 Fast access to the file blocks.

There are following methods which can be used for allocation.

1. Contiguous Allocation.
2. Linked List Allocation
3. FAT
4. Indexed Allocation
5. Linked Indexed Allocation
6. Multilevel Indexed Allocation
7. Inode

Contiguous Allocation

If the blocks are allocated to the file in such a way that all the logical blocks of the file
get the contiguous physical block in the hard disk then such allocation scheme is known
as contiguous allocation.

In the image shown below, there are three files in the directory. The starting block and
the length of each file are mentioned in the table. We can check in the table that the
contiguous blocks are assigned to each file as per its need.
Advantages
1. It is simple to implement.
2. We will get Excellent read performance.
3. Supports Random Access into files.

Disadvantages
1. The disk will become fragmented.
2. It may be difficult to have a file grow.

Linked List Allocation

Linked List allocation solves all problems of contiguous allocation. In linked list
allocation, each file is considered as the linked list of disk blocks. However, the disks
blocks allocated to a particular file need not to be contiguous on the disk. Each disk
block allocated to a file contains a pointer which points to the next disk block allocated
to the same file.
Advantages

1. There is no external fragmentation with linked allocation.

2. Any free block can be utilized in order to satisfy the file block requests.
3. File can continue to grow as long as the free blocks are available.
4. Directory entry will only contain the starting block address.

Disadvantages
1. Random Access is not provided.
2. Pointers require some space in the disk blocks.
3. Any of the pointers in the linked list must not be broken otherwise the file will
get corrupted.
4. Need to traverse each block.

File Allocation Table

The main disadvantage of linked list allocation is that the Random access to a particular
block is not provided. In order to access a block, we need to access all its previous
blocks.

File Allocation Table overcomes this drawback of linked list allocation. In this scheme,
a file allocation table is maintained, which gathers all the disk block links. The table has
one entry for each disk block and is indexed by block number.

File allocation table needs to be cached in order to reduce the number of head seeks.
Now the head doesn't need to traverse all the disk blocks in order to access one
successive block.
It simply accesses the file allocation table, read the desired block entry from there and
access that block. This is the way by which the random access is accomplished by using
FAT. It is used by MS-DOS and pre-NT Windows versions.

Advantages
1. Uses the whole disk block for data.
2. A bad disk block doesn't cause all successive blocks lost.
3. Random access is provided although its not too fast.
4. Only FAT needs to be traversed in each file operation.

Disadvantages
1. Each Disk block needs a FAT entry.
2. FAT size may be very big depending upon the number of FAT entries.
3. Number of FAT entries can be reduced by increasing the block size but it will
also increase Internal Fragmentation.
Indexed Allocation

Limitation of FAT

Limitation in the existing technology causes the evolution of a new technology. Till
now, we have seen various allocation methods; each of them was carrying several
advantages and disadvantages.

File allocation table tries to solve as many problems as possible but leads to a
drawback. The more the number of blocks, the more will be the size of FAT.

Therefore, we need to allocate more space to a file allocation table. Since, file allocation
table needs to be cached therefore it is impossible to have as many space in cache. Here
we need a new technology which can solve such problems.

Indexed Allocation Scheme

Instead of maintaining a file allocation table of all the disk pointers, Indexed allocation
scheme stores all the disk pointers in one of the blocks called as indexed block. Indexed
block doesn't hold the file data, but it holds the pointers to all the disk blocks allocated
to that particular file. Directory entry will only contain the index block address.
Advantages
1. Supports direct access
2. A bad data block causes the lost of only that block.

Disadvantages
1. A bad index block could cause the lost of entire file.
2. Size of a file depends upon the number of pointers, a index block can hold.
3. Having an index block for a small file is totally wastage.
4. More pointer overhead

Linked Index Allocation

Single level linked Index Allocation

In index allocation, the file size depends on the size of a disk block. To allow large
files, we have to link several index blocks together. In linked index allocation,

o Small header giving the name of the file

o Set of the first 100 block addresses
o Pointer to another index block

For the larger files, the last entry of the index block is a pointer which points to another
index block. This is also called as linked schema.
Advantage: It removes file size limitations

Disadvantage: Random Access becomes a bit harder

Multilevel Index Allocation

In Multilevel index allocation, we have various levels of indices. There are outer level
index blocks which contain the pointers to the inner level index blocks and the inner
level index blocks contain the pointers to the file data.

o The outer level index is used to find the inner level index.
o The inner level index is used to find the desired data block.

Advantage: Random Access becomes better and efficient.

Disadvantage: Access time for a file will be higher.

Inode

In UNIX based operating systems, each file is indexed by an Inode. Inode are the
special disk block which is created with the creation of the file system. The number of
files or directories in a file system depends on the number of Inodes in the file system.

An Inode includes the following information

1. Attributes (permissions, time stamp, ownership details, etc) of the file

2. A number of direct blocks which contains the pointers to first 12 blocks of the
file.
3. A single indirect pointer which points to an index block. If the file cannot be
indexed entirely by the direct blocks then the single indirect pointer is used.
4. A double indirect pointer which points to a disk block that is a collection of the
pointers to the disk blocks which are index blocks. Double index pointer is used
if the file is too big to be indexed entirely by the direct blocks as well as the
single indirect pointer.
5. A triple index pointer that points to a disk block that is a collection of pointers.
Each of the pointers is separately pointing to a disk block which also contains a
collection of pointers which are separately pointing to an index block that
contains the pointers to the file blocks.
 Single Level Directory
The simplest method is to have one big list of all the files on the disk. The entire
system will contain only one directory which is supposed to mention all the files
present in the file system. The directory contains one entry per each file present on
the file system.

This type of directories can be used for a simple system.

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 Directory
In two level directory systems, we can create a separate directory for each user.
There is one master directory which contains separate directories dedicated to each
user. For each user, there is a different directory present at the second level,
containing group of user's file. The system doesn't let a user to enter in the other
user's directory without permission.

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 Directory
In Tree structured directory system, any directory entry can either be a file or sub
directory. Tree structured directory system overcomes the drawbacks of two
level directory system. The similar kind of files can now be grouped in one
directory.

Each user has its own directory and it cannot enter in the other user's directory.
However, the user has the permission to read the root's data but he cannot write
or modify this. Only administrator of the system has the complete access of root
directory.

Searching is more efficient in this directory structure. The concept of current

working directory is used. A file can be accessed by two types of path, either
relative or absolute.

Absolute path is the path of the file with respect to the root directory of the
system while relative path is the path with respect to the current working
directory of the system. In tree structured directory systems, the user is given the
privilege to create the files as well as directories.
Permissions on the file and directory

A tree structured directory system may consist of various levels therefore there is
a set of permissions assigned to each file and directory.

The permissions are R W X which are regarding reading, writing and the
execution of the files or directory. The permissions are assigned to three types of
users: owner, group and others.

There is a identification bit which differentiate between directory and file. For a
directory, it is d and for a file, it is dot (.)