UNIT-5

FILE SYSTEM
 File
• A file is a collection of correlated information
which is recorded on secondary or non-
volatile storage like magnetic disks, optical
disks, and tapes.
• In general, a file is a sequence of bits, bytes, or
records whose meaning is defined by the file
creator and user.
• Every File has a logical location where they are
located for storage and retrieval.
 Properties of a File System
• Files are stored on disk or other storage and
do not disappear when a user logs off.
• Files have names and are associated with
access permission that permits controlled
sharing.
• Files could be arranged or more complex
structures to reflect the relationship between
them.
 File structure
• A File Structure needs to be predefined format in
such a way that an operating system understands.
It has an exclusively defined structure, which is
based on its type.
• Three types of files structure in OS:
i. A text file: It is a series of characters that is
organized in lines.
ii. An object file: It is a series of bytes that is
organized into blocks.
iii. A source file: It is a series of functions and
processes.
 File Attributes
• Name: It is the only information stored in a human-
readable form.
• Identifier: Every file is identified by a unique tag number
within a file system known as an identifier.
• Location: Points to file location on device.
• Type: This attribute is required for systems that support
various types of files.
• Size. Attribute used to display the current file size.
• Protection. This attribute assigns and controls the access
rights of reading, writing, and executing the file.
• Time, date and user identification: It is used for protection,
security, and also used for monitoring
 File Operations
• Creating a file.
• Writing a file.
• Reading a file.
• Repositioning a file.
• Deleting a file.
• Truncating a file.
 File management System
• The main objectives of the file management
system:
o It provides I/O support for a variety of
storage device types.
o Minimizes the chances of lost or destroyed
data
o Helps OS to standardized I/O interface
routines for user processes.
o It provides I/O support for multiple users in
a multiuser systems environment.
 File Access Methods
• Sequential Method
• In this type of file access method, records are
accessed in a certain pre-defined sequence.
• In the sequential access method, information
stored in the file is also processed one by one.
• Most compilers access files using this access
method.
 File Access Methods
• Random Access
• The random access method is also called
direct random access.
• This method allow accessing the record
directly.
• Each record has its own address on which can
be directly accessed for reading and writing.
 File Access Methods
• Indexed Sequential Access
• This type of accessing method is based on simple
sequential access.
• In this access method, an index is built for every file,
with a direct pointer to different memory blocks.
• In this method, the Index is searched sequentially, and
its pointer can access the file directly.
• Multiple levels of indexing can be used to offer greater
efficiency in access. It also reduces the time needed to
access a single record.
 File Allocation Methods
• Contiguous Allocation
• Contiguous allocation requires that each file occupy a
set of contiguous blocks on the disk. The word
contiguous means continuous
• Because of contiguous allocation, there is minimal or
no disk-head movement which reading/writing the
blocks of the file.
• The seek time is minimal over here. Consequently,
access time of a file and the I/O performance is greatly
improved.
• To access a file, there we only need to know the
starting location and length of the file which are stored
in the directory
 File Allocation Methods
• Contiguous Allocation
 File Allocation Methods
• Linked Allocation
• Here the blocks of a single file can be scattered
anywhere on the disk. The reason because the
entire file is implemented as a Linked List.
• The directory maintained by the OS contains a
pointer to the first and the last blocks of a file.
• Each block of a file contains a pointer to the next
block after it in the list.
• For creating a new file, we need to just create a
new entry in the directory and not to search for
sufficient space as in contiguous.
 File Allocation Methods
• Linked Allocation
 File Allocation Methods
• Indexed Allocation
• In indexed allocation method, all the pointers (pointing
to the next block in the Linked list) are gathered
together into one location known as Index Block.
• Each file has an index block of its own, which is an
array of disk-block addresses.
• When a file is created initially, all pointers in the index
block are set to null value. As new blocks are written,
the pointers are modified accordingly.
• Indexed allocation supports direct access and does not
suffer from any external fragmentation.
• Indexed allocation suffers from the problem of wasted
space.
 File Allocation Methods
• Indexed Allocation
 File Allocation Methods
• Multi-level Indexed Allocation
• There is a trade-off for selecting the index block
size.
• On the one hand, we want the index block to be
as small as possible, since every file requires an
index block.
• On the other hand, if the index block is too small,
it is not able to hold enough pointers for larger
files.
• In multi-level indexing scheme, a first-level index
block points to a set of second-level index blocks,
which then points to the file blocks.
 File Implementation Issues
• Management of disc space: To prevent space wastage and to
guarantee that files can always be stored in contiguous blocks,
file systems must manage disc space effectively.
• Checking for consistency and repairing errors: The
consistency and error-free operation of files and directories
must be guaranteed by file systems.
• Locking files and managing concurrency: To prevent conflicts
and guarantee data integrity, file systems must control how
many processes or users can access a file at once.
Performance optimization: File systems need to optimize
performance by reducing file access times, increasing
throughput, and minimizing system overhead.
 I/O KERNEL SUBSYSTEM
• With the computer system, we can communicate via
input and output (I/O) devices.
• The transport of data between RAM and various I/O
peripherals is referred to as I/O.
• We can enter data via input devices such as keyboards,
mouse, card readers, scanners, voice recognition
systems, and touch screens.
• We can acquire information from the computer by
employing output devices like monitors, printers,
plotters, and speakers.
• The processor is not directly connected to these
devices. However, the data exchanges between them
are managed through an interface.
 I/O KERNEL SUBSYSTEM
• The kernel provides many I/O services.
• Scheduling:
o I/O request queue for a device.
• Buffering:
o Storing data in memory while transferring data
between devices.
o Device speed mismatch.
o Device transfer size mismatch.
• Caching:
o Fast memory holding copy of data.
o Key to performance
o Faster storage of data that resides elsewhere
 I/O KERNEL SUBSYSTEM
• Spooling:
o Hold out for a device.
o If device can serve one request at a time.
o E.g. Printer
• Device Reservation:
o It provides exclusive device access.
o Allocation of devices when required by the processes and that
device when it is no longer needed.
o It prevents deadlock.
• Error Handling:
o OS can recover from disk read/write transient errors
o Disk unavailability.
o System error log holds problem reports.
o ‘Dirty’ block management.
 RAID
• RAID (Redundant Array of Independent Disks) is a
setup consisting of multiple disks for data
storage.
• They are linked together to prevent data loss
and/or speed up performance.
• Data redundancy, although taking up extra
space, adds to disk reliability.
• This means, in case of disk failure, if the same
data is also backed up onto another disk, we can
retrieve the data and go on with the operation.
 RAID Motivation
• Reliability: In single disk system, one disk
failure results in data loss.
• Availability: What fraction of the total session
time is a system in uptime mode, i.e. how
available is the system for actual use?
• Performance: Disk speed improves slowly as
compared to CPU.
• Cost: A single fast, reliable disk is expensive.
 RAID Levels and Types
• RAID 0 (Striping), also known as a striped set or a striped
volume, requires a minimum of two disks.
• The disks are merged into a single large volume where data
is stored evenly across the number of disks in the array.
• This process is called disk striping and involves splitting data
into blocks and writing it simultaneously/sequentially on
multiple disks.
• Configuring the striped disks as a single partition increases
performance since multiple disks do reading and writing
operations simultaneously.
• Therefore, RAID 0 is generally implemented to improve
speed and efficiency.
 RAID Levels and Types
• Advantages
• It is easy to implement.
• It utilizes the storage capacity in a better way, n times speed-up.
• Disadvantages
• A single drive loss can result in the complete failure of the system.
• Not a good choice for a critical system.
 RAID Levels and Types
• RAID 1 (Mirroring), is an array consisting of at least
two disks where the same data is stored on each to
ensure redundancy.
• The most common use of RAID 1 is setting up a
mirrored pair consisting of two disks in which the
contents of the first disk is mirrored in the second.
• This is why such a configuration is also called mirroring.
• Unlike with RAID 0, where the focus is solely on speed
and performance, the primary goal of RAID 1 is to
provide redundancy.
 RAID Levels and Types
• Advantages
• It covers complete redundancy.
• It can increase data security and speed.
• Disadvantages
• It is highly expensive.
• Storage capacity is less.
 RAID Levels and Types
• RAID 10 (Mirroring with Striping), is a hybrid RAID,
which means it is a combination of two different RAID
levels.
• In the case of RAID 10, the array combines level 1
mirroring and level 0 striping.
• This RAID array is also known as RAID 1+0.
• RAID 10 uses logical mirroring to write the same data
on two or more drives to provide redundancy.
• If one disk fails, there is a mirrored image of the data
stored on another disk.
• Additionally, the array uses block-level striping to
distribute chunks of data across different drives.
 RAID Levels and Types
• Advantages
• High performance and High fault-tolerance.
• Fast read and write operations.
• Disadvantages
• Costly (compared to other RAID levels).
• Uses half of the disk space capacity.
• More complicated to set up.
 RAID Levels and Types
• RAID 2 (Bit-Level Stripping with Hamming-Code
Parity), in this the error of the data is checked at every
bit level.
• Here, we use Hamming Code Parity Method to find the
error in the data.
• It uses one designated drive to store parity.
• The structure of Raid-2 is very complex as we use two
disks in this technique.
• One disk is used to store bits of each word and another
disk is used to store error code correction.
• It is not commonly used.
 RAID Levels and Types
• Advantages
• Reliability.
• The ability to correct stored information.
• Disadvantages
• It has a complex structure and high cost due to extra drive.
• It requires an extra drive for error detection.
 RAID Levels and Types
• RAID 3 (Byte-Level Stripping with Dedicated
Parity), consists of byte-level striping with
dedicated parity striping.
• At this level, we store parity information in a
disc section and write to a dedicated parity
drive.
• Whenever failure of the drive occurs, it helps
in accessing the parity drive, through which
we can reconstruct the data.
 RAID Levels and Types
• Advantages
• Data can be transferred in bulk.
• Data can be accessed in parallel.
• Disadvantages
• It requires an additional drive for parity.
• In the case of small-size files, it performs slowly.
 RAID Levels and Types
• RAID 4 (Block-Level Striping with Dedicated
Parity), consists of block-level data striping
across two or more independent disk and a
dedicated parity disk.
• Instead of duplicating data, this adopts a
parity-based approach.
 RAID Levels and Types
• Advantages
• Low storage overhead.
• Simultaneous I/O requests.
• Disadvantages
• Bottlenecks that have big effect on overall performance.
• Redundancy is lost if the parity disk fails.
 RAID Levels and Types
• RAID 5 (Striping with Parity), is considered
the most secure and most common RAID
implementation.
• It combines striping and parity to provide a
fast and reliable setup.
• Such a configuration gives the user storage
usability as with RAID 1 and the performance
efficiency of RAID 0.
 RAID Levels and Types
• Advantages
• High performance and capacity.
• Fast and reliable read speed.
• Tolerates single drive failure.
• Disadvantages
• Uses half of the storage capacity (due to parity).
• If more than one disk fails, data is lost.
• More complex to implement.
 RAID Levels and Types
• RAID 6 (Striping with Double Parity), is an array
similar to RAID 5 with an addition of its double
parity feature.
• For this reason, it is also referred to as the
double-parity RAID.
• The setup resembles RAID 5 but includes two
additional parity blocks distributed across the
disk.
• Block-level striping with two parity blocks allows
two disk failures before any data is lost.
 RAID Levels and Types
• Advantages
• High fault and drive-failure tolerance.
• Fast read operations.
• Disadvantages
• Due to double parity, it has slow write data transactions.
• Extra space is required.
 Directory
• A directory is a list of files on a disc.
• A directory can be thought of as a file that has
the metadata for a bunch of files.
• When a user or a process requests a file, the
file system searches the directory for the file's
entry, and when a match is found, it acquires
the file's location.
 Directory Structure
1. Single Level Directory
• The most basic way is to keep a single large list of all files on a
drive.
• When the number of files grows or the system has more than
one user, a single level directory becomes a severe constraint.
• No two files with the same name are allowed.
 Directory Structure
Advantages of Single Level Directory
• Because it is just a single directory, it is relatively simple to
implement.
• Searching will be faster if the files are smaller in size.
• In such a directory structure, actions like file creation, searching,
deletion, and updating are quite simple.

Disadvantages of Single Level Directory

• In a Single-Level Directory, if the directory is vast, searching will be
difficult.
• We can't group the same type of files in a single-level directory.
• The challenge of selecting a unique file name is a little more
difficult.
 Directory Structure
2. Two-Level Directory
• There is a single master directory that contains individual directories for
each user.
• At the second level, there is a separate directory for each user, which
contains a collection of users' files.
• The mechanism prevents a user from accessing another user's directory
without their authorization.
 Directory Structure
Advantages of Two-Level Directory
• Different user can group files of the same name in a two-level
directory.
• As we have a user-defined directory this also provides privacy
related to files stored as no user can enter the other user’s
directory without permission.
• Searching for files become much simpler.
Disadvantages of Two-Level Directory
• One user cannot share a file with another user in a two-level
directory.
• The two-level directory also has the problem of not being scalable.
• Here users cannot create subdirectories only one user file directory
can be defined under one master file directory.
 Directory Structure
3. Tree-structured Directory
• The tree-structured directory structure has separate parent
directories for the sub-directories owned by each of their
specific users and the parent directories of the users are all
under the master-root directory which makes it a tree
structure.
• Tree-structured directory allows the user the ability to create
their own subdirectories and organize their files accordingly.
• This helps in total separation between the users which
provides complete naming freedom and privacy to users'
information.
 Directory Structure
3. Tree-structured Directory
 Directory Structure
Advantages of tree-structured directory
• The directory, which is organized in a tree form, is extremely
scalable.
• Collisions are less likely in the tree-structures directory.
• The searching in the tree-structure directory is relatively simple
because we may utilize both absolute and relative paths.
Disadvantages of tree-structured directory
• As we have to go under multiple directories to access a file we can
say that it is said to be inefficient
• We are unable to share files.
• Because a file might be found in several folders, it is inefficient.
 Directory Structure
4. Acyclic-Graph Directory
• The tree model forbids the existence of the same file in
several directories.
• By making the directory an acyclic graph structure, we may
achieve this.
• Two or more directory entries can lead to the same
subdirectory or file, but we'll limit it, for now, to prevent any
directory entries from pointing back up the directory
structure.
• We have numerous names for the same file, as well as
multiple paths to it.
 Directory Structure
4. Acyclic-Graph Directory
 Directory Structure
4. Acyclic-Graph Directory

• Creating a Hard Link:

ln /path/to/original.txt hardlink.txt
• This creates hardlink.txt in your current directory as a hard link to
original.txt.

• Creating a Symbolic Link:

ln -s /common/shared /home/user1/shared
• This command creates a symbolic link, making the entire
/common/shared directory appear under /home/user1/shared.
 Directory Structure
Advantages of Acyclic-Graph Directory
• We have the ability to share the files.
• Due to different-different paths, searching is simple.
Disadvantages of Acyclic-Graph Directory
• If the files are linked together, removing them may be
difficult.
• If we use softlink, then if the file is removed, all that is left is a
dangling pointer.
• If we use a hardlink, when we delete a file, we must also erase
all of the references that are associated with it.
I/O MANAGEMENT & DISK
SCHEDULING
 Disk Structure
• Hard disk is secondary storage which stores the
large amount of data.
• The secondary storage typically is formed of
stacked up magnetic disks on the top of one
another.
• One single unit of such disk is called platter.
• A single unit of secondary storage device like HDD
may have 100-200 such platters stacked up on
one another.
• Each platter is divided into circular shaped tracks.
• Each track is further divided into sectors.
 Disk Structure
• Spindle revolves the platters and is controlled by
r/w unit of OS.
• Some advanced spindles have capability to only
revolve a particular disk and keep others intact.
• Arm Assembly is there which keeps a pointy r/w
head on each disk to read of write on a particular
disk.
• A world cylinder may also be used at times to
refer disk stack.
Disk Structure
 Disk Capacity
• Size/Capacity of a (Unformatted) Disk:
Total number of platters or disks x
Total number of surfaces (heads) x
Number of tracks per surface (cylinders) x
Number of sectors per track x
Sector size (Number of bytes per sector)
 Disk Capacity
• Practice Exercise:
• Let suppose there are 8 platters in hard disk drive.
Each platter has two surfaces (required R/W head
will be 16). If, there are 1,024 cylinders and 128
sectors in each track. The sector size is 512 bytes.
Then
A). Calculate Disk Size?
B). How many number of bits required to represent the
disk size?
 Disk Capacity
• Solution:
A). Size of Hard Disk = Platters x Surfaces x Cylinder x
Sectors x Sector-Size = 8 x 2 x 1,024 x 128 x 512 Bytes
=23 x 2 x 210 x 27 x 29 Bytes
= 230 Bytes
= 1 GB
B). As 1 GB = 230 Bytes so, 30 bits are required to
represent 1GB hard disk.
 Disk Capacity
• Let format overhead = ‘a’ bytes
• Overhead size:
Total number of platters or disks x
Total number of surfaces (heads) x
Number of tracks per surface (cylinders) x
Number of sectors per track x
Format overhead (‘a’ bytes)
 Disk Capacity
• Size/Capacity of a (formatted) Disk:
• Capacity of a (unformatted) Disk – Overhead size
 Disk Capacity
• Practice Exercise:
• Given-
 32 Platters
 4 Surfaces
 256 Tracks/Surface
 2K Sectors/Track
 4KB Sector size
 64 Bytes Format overhead
• Calculate the Formatted Disk Capacity.
 Disk Capacity
• Solution:
Size of Unformatted Disk = Platters x Surfaces x Cylinder x Sectors x
Sector-Size
= 32 x 4 x 256 x 2K x 4K Bytes
=25 x 22 x 28 x 211 x 212 Bytes
= 238 Bytes
= 256 GB
Overhead size = Platters x Surfaces x Cylinder x Sectors x
format overhead
= 32 x 4 x 256 x 2K x 64 Bytes
=25 x 22 x 28 x 211 x 26 Bytes
= 232 Bytes
= 4 GB
 Disk Capacity
• Solution:
Size of Formatted Disk = Size of Unformatted Disk –
Overhead size
= 256 GB – 4 GB
= 252 GB
 Disk Capacity
• Solution:
Size of Formatted Disk = Size of Unformatted Disk –
Overhead size
= 256 GB – 4 GB
= 252 GB
 Disk Access Time
• Seek Time - It is the time taken by the disk arm to locate
the desired track.
• Rotational Latency - The time taken by a desired sector
of the disk to rotate itself to the position where it can
access the Read/Write heads is called Rotational Latency.
• The positioning time, or random-access time, consists of
two parts: seek time and rotational latency.
• Transfer Time - It is the time taken to transfer the data
requested by the processes.
• Disk Access Time - Disk Access time is the sum of the
Seek Time, Rotational Latency, and Transfer Time.
 Disk Access Time
• Average (Disk) access time =
Average seek time +
Average rotational delay +
Transfer time +
Controller overhead +
Queuing delay
 Disk Access Time
• Total seek time = No. of seeks x seek time (per track)
• Average seek time = Average No. of seeks x
seek time
= (No. of tracks-1) / 2 x seek time
• Average rotational delay = 1/2 x Time taken for
one full rotation
 Disk Capacity
• Practice Exercise:
What is the average access time for transferring 512
bytes of data with the following specifications-
o Average seek time = 5 msec
o Disk rotation = 6000 RPM
o Data transfer rate = 40 KB/sec
o Controller overhead = 0.1 msec
 Disk Capacity
• Solution:
Time Taken For One Full Rotation-
Time taken for one full rotation
= (60 / 6000) sec
= (1 / 100) sec
= 0.01 sec
= 10 msec
 Disk Capacity
• Solution:
• Average Rotational Delay-
• Average rotational delay
• = 1/2 x Time taken for one full rotation
• = 1/2 x 10 msec
• = 5 msec
 Disk Capacity
• Solution:
• Transfer Time-
• Transfer time
• = (512 bytes / 40 KB) sec
• = 0.0125 sec
• = 12.5 msec
 Disk Capacity
• Solution:
• Average Access Time-
• Average access time
• = Average seek time + Average rotational delay +
Transfer time + Controller overhead + Queuing delay
• = 5 msec + 5 msec + 12.5 msec + 0.1 msec + 0
• = 22.6 msec
 Disc Scheduling Algorithms
• A Process makes the I/O requests that may be
located at different sectors on different tracks.
• Disk Scheduling Algorithm manages those
requests and decides the order of the disk
access given to the requests.
• These algorithms help in minimizing the seek
time by ordering the requests made by the
processes.
 First Come First Serve (FCFS)
• In this algorithm, the requests are served in the
order they come.
• Those who come first are served first.
• This is the simplest algorithm.
• Advantages-
• It is simple, easy to understand and implement.
• It does not cause starvation to any request.
• Disadvantages-
• It results in increased total seek time.
• It is inefficient.
 First Come First Serve (FCFS)
• Eg. Consider a disk queue with requests for
I/O to blocks on cylinders 98, 183, 41, 122, 14,
124, 65, 67.
• The FCFS scheduling algorithm is used.
• The head is initially at cylinder number 53.
• The cylinders are numbered from 0 to 199.
Calculate the total head movement (in
number of cylinders) incurred while servicing
these requests.
 First Come First Serve (FCFS)

• Total head movements incurred while servicing these requests

= (98 – 53) + (183 – 98) + (183 – 41) + (122 – 41) + (122 – 14) +
(124 – 14) + (124 – 65) + (67 – 65)
= 45 + 85 + 142 + 81 + 108 + 110 + 59 + 2
= 632
 First Come First Serve (FCFS)
• Practice Exercise:
• Let us consider the request sequence as 82,
170, 43, 140, 24, 16 and 190 and current
position of head at 50. Calculate the total
head movement.
 First Come First Serve (FCFS)
• Solution:

• Seek time for FCFS = (82-50) + (170-82) + (170-43) + (140-43) + (140

(170-82) + (170-43) + (140-43) + (140-24) + (24-16) + (190-16) = 642
 Shortest Seek Time First (SSTF)
• In this algorithm, the shortest seek time is checked from
the current position and those requests which have the
shortest seek time is served first.
• In simple words, the closest request from the disk arm is
served first.
• It breaks the tie in the direction of head movement.
• Advantages-
• Less Disk Response Time
• Increased Efficiency than FCFS
• Disadvantages-
• There is an overhead of finding out the closest request
• Starvation can occur
 Shortest Seek Time First (SSTF)
• Eg. Consider a disk queue with requests for I/O to
blocks on cylinders 98, 183, 41, 122, 14, 124, 65,
67.
• The SSTF scheduling algorithm is used.
• The head is initially at cylinder number 53 moving
towards larger cylinder numbers on its servicing
pass.
• The cylinders are numbered from 0 to 199.
Calculate the total head movement (in number of
cylinders) incurred while servicing these requests.
 Shortest Seek Time First (SSTF)

• Total head movements incurred while servicing these requests

= (65 – 53) + (67 – 65) + (67 – 41) + (41 – 14) + (98 – 14) + (122 – 98)
+ (124 – 122) + (183 – 124)
= 12 + 2 + 26 + 27 + 84 + 24 + 2 + 59
= 236
 Shortest Seek Time First (SSTF)
• Practice Exercise:
• Let us consider the request sequence as 82,
170, 43, 140, 24, 16 and 190 and current
position of head at 50.
 Shortest Seek Time First (SSTF)
• Solution:

• Seek time for SSTF = (50-43) + (43-24) + (24-16) + (82-16) +

(140-82) + (170-140) + (190-170) = 208
 SCAN
• In this algorithm, the disk arm moves in a particular
direction till the end and serves all the requests in its path,
then it returns to the opposite direction and moves till the
last request is found in that direction and serves all of
them.
• SCAN Algorithm is also called as Elevator Algorithm.
• Advantages-
• Easy Implementation.
• No waiting of requests in the queue.
• Disadvantages-
• It causes long waiting time for the cylinders just visited by
the head.
• It causes the head to move till the end of the disk even if
there are no requests to be serviced.
 SCAN
• Eg. Consider a disk queue with requests for I/O to
blocks on cylinders 98, 183, 41, 122, 14, 124, 65,
67.
• The SCAN scheduling algorithm is used.
• The head is initially at cylinder number 53 moving
towards larger cylinder numbers on its servicing
pass.
• The cylinders are numbered from 0 to 199.
Calculate the total head movement (in number of
cylinders) incurred while servicing these requests.
 SCAN

• Total head movements incurred while servicing these requests

• = (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) +
(183 – 124) + (199 – 183) + (199 – 41) + (41 – 14)
• = 12 + 2 + 31 + 24 + 2 + 59 + 16 + 158 + 27
• = 331
 SCAN
• Practice Exercise:
• Let us consider the request sequence as 82,
170, 43, 140, 24, 16 and 190 and current
position of head at 50.
 SCAN
• Solution:

• Seek time for SCAN = (199-50) + (199-16) =332

 C-SCAN
• This algorithm is the same as the SCAN algorithm.
• The only difference between SCAN and C-SCAN is, it moves in a
particular direction till the last and serves the requests in its path.
• Then, it returns in the opposite direction till the end and doesn't
serve the request while returning.
• Then, again reverses the direction and serves the requests found in
the path.
• Advantages-
• The waiting time for the cylinders just visited by the head is
reduced as compared to the SCAN Algorithm.
• It provides uniform waiting time and better response time.
• Disadvantages-
• It causes more seek movements as compared to SCAN Algorithm.
• It causes the head to move till the end of the disk even if there are
no requests to be serviced.
 C-SCAN
• Eg. Consider a disk queue with requests for I/O to
blocks on cylinders 98, 183, 41, 122, 14, 124, 65,
67.
• The C-SCAN scheduling algorithm is used.
• The head is initially at cylinder number 53 moving
towards larger cylinder numbers on its servicing
pass.
• The cylinders are numbered from 0 to 199.
Calculate the total head movement (in number of
cylinders) incurred while servicing these requests.
 C-SCAN

• Total head movements incurred while servicing these requests

• = (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) +
(183 – 124) + (199 – 183) + (199 – 0) + (14 – 0) + (41 – 14)
• = 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 27
• = 386
 C-SCAN
• Practice Exercise:
• Let us consider the request sequence as 82,
170, 43, 140, 24, 16 and 190 and current
position of head at 50.
 C-SCAN
• Solution:

• Seek time for SCAN =(199-50) + (199-0) + (43-0)

=391
 LOOK
• LOOK Algorithm is an improved version of the SCAN Algorithm.
• Head starts from the first request at one end of the disk and moves
towards the last request at the other end servicing all the requests
in between.
• After reaching the last request at the other end, head reverses its
direction.
• It then returns to the first request at the starting end servicing all
the requests in between.
• Advantages-
• It provides better performance as compared to SCAN Algorithm.
• It does not lead to starvation.
• Disadvantages-
• There is an overhead of finding the end requests.
• It causes long waiting time for the cylinders just visited by the head.
 LOOK
• Eg. Consider a disk queue with requests for I/O to
blocks on cylinders 98, 183, 41, 122, 14, 124, 65,
67.
• The LOOK scheduling algorithm is used.
• The head is initially at cylinder number 53 moving
towards larger cylinder numbers on its servicing
pass.
• The cylinders are numbered from 0 to 199.
Calculate the total head movement (in number of
cylinders) incurred while servicing these requests.
 LOOK

• Total head movements incurred while servicing these requests

• = (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) +
(183 – 124) + (183 – 41) + (41 – 14)
• = 12 + 2 + 31 + 24 + 2 + 59 + 142 + 27
• = 299
 LOOK
• Practice Exercise:
• Let us consider the request sequence as 82,
170, 43, 140, 24, 16 and 190 and current
position of head at 50.
 LOOK
• Solution:

• Seek time for SCAN = (190-50) + (190-16) =314

 C-LOOK
• This algorithm is also the same as the LOOK algorithm.
• The only difference between LOOK and C-LOOK is, it moves in a
particular direction till the last request is found and serves the
requests in its path.
• Then, it returns in the opposite direction till the last request is
found in that direction and doesn't serve the request while
returning.
• Then, again reverses the direction and serves the requests found in
the path.
• Advantages-
• Reduction in waiting time.
• There is no starvation.
• Disadvantages-
• The arm need to be conscious while dealing with the last request.
 C-LOOK
• Eg. Consider a disk queue with requests for I/O to
blocks on cylinders 98, 183, 41, 122, 14, 124, 65,
67.
• The C-LOOK scheduling algorithm is used.
• The head is initially at cylinder number 53 moving
towards larger cylinder numbers on its servicing
pass.
• The cylinders are numbered from 0 to 199.
Calculate the total head movement (in number of
cylinders) incurred while servicing these requests.
 C-LOOK

• Total head movements incurred while servicing these requests

• = (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) +
(183 – 124) + (183 – 14) + (41 – 14)
• = 12 + 2 + 31 + 24 + 2 + 59 + 169 + 27
• = 326
 C-LOOK
• Practice Exercise:
• Let us consider the request sequence as 82,
170, 43, 140, 24, 16 and 190 and current
position of head at 50.
 C-LOOK
• Solution:

• Seek time for C-LOOK = (190-50) + (190-16) +

(43-16) =341