Module 5 Disk Algo Examples
Uploaded by
Ambika VenkateshModule 5 Disk Algo Examples
Uploaded by
Ambika VenkateshDisk Scheduling Algorithms
• Scheduling: The disk head serves the requests at the front of
the queue, one after the other, until the queue is empty.
• The FCFS algorithm doesn't consider the seek time when
scheduling, so it might involve unnecessary head
movements, leading to potentially longer service times overall.
Prof J V Gorabal ,CSE ATMECE,Mysore
FCFS-Example
• Let's take a disk with 180 tracks (0-179) and the disk queue
having input/output requests in the following order: 81, 110, 38,
156, 68, 172, 92, 10. The initial head position of the Read/Write
head is 45. Find the total number of track movements of the
Read/Write head using the FCFS algorithm.
Prof J V Gorabal ,CSE ATMECE,Mysore
FCFS :Example: HP:45
Prof J V Gorabal ,CSE ATMECE,Mysore
FCFS: THM
THM=(81-45) + (110-81) + (110-38) + (156-38) +
(156-68) + (172-156) + (172-92) + (92-10)
= 36 + 29 + 72 + 118 + 88 + 16 + 80 + 82
THM= 521
Prof J V Gorabal ,CSE ATMECE,Mysore
SSTF( Shortest Seek Time First)
• The SSTF algorithm aims to minimize seek time by
scheduling disk requests based on their proximity to the
current head position. It prioritizes the request closest to the
head, regardless of the direction, leading to potentially faster
service times compared to FCFS.
Prof J V Gorabal ,CSE ATMECE,Mysore
SSTF: How it works
• Calculate seek times: For each request in the queue, calculate the seek
time (absolute difference) from the current head position.
• Select shortest seek: Choose the request with the shortest seek time as
the next to be serviced.
• Update head position: Move the head to the chosen track and repeat
steps 1-2 until all requests are served
Prof J V Gorabal ,CSE ATMECE,Mysore
SSTF: Example
• Let's take an example to understand the SSTF Disk Scheduling
Algorithm. Let's take a disk with 180 tracks (0-179) and the disk queue
having input/output requests in the following order: 87, 110, 50, 172, 67,
156, 39, 15. The initial head position of the Read/Write head is 45 and
will move in the left-hand side direction. Find the total number of track
movements of the Read/Write head using the SSTF algorithm.
Prof J V Gorabal ,CSE ATMECE,Mysore
SSTF : Example : HP:45
Prof J V Gorabal ,CSE ATMECE,Mysore
SSTF : Solution
• THM: (50-45) + (50-39) + (39-15) + (67-15) + (87-
67) + (110-87) + (156-110) + (172-156)
• THM=187
Prof J V Gorabal ,CSE ATMECE,Mysore
Disk Scheduling Algorithm
Elevator Principle Algorithms
• Current direction: The algorithm maintains a current direction (up or
down).
• Serve requests: It serves requests in the current direction until there are no
more remaining.
• Change direction: If there are no more requests in the current direction, it
changes direction and serves requests in the opposite direction, starting with
the closest one.
Prof J V Gorabal ,CSE ATMECE,Mysore
Scan Algorithm
• The SCAN algorithm, also known as the Elevator
algorithm, is a disk scheduling algorithm that aims to
minimize the seek time (movement time) of the disk
head by servicing requests in a specific pattern.
Prof J V Gorabal ,CSE ATMECE,Mysore
How Scan Algo works
• Initial Position: The disk head starts at one end of the disk (say, left or right).
• Direction: The head moves in a chosen direction (left or right) servicing all pending
requests in its path.
• End of Disk: Upon reaching the opposite end, the head reverses its direction and
starts servicing requests again.
• Repeat: This process continues back and forth, scanning the entire disk and servicing
all requests.
Prof J V Gorabal ,CSE ATMECE,Mysore
SCAN-Algo-Example Graph(L-R)
HP:55
THM=(250-55)+(250-15)=430
Prof J V Gorabal ,CSE ATMECE,Mysore
SCAN-Algo -Example Graph-R-L ; HP;55
THM=(55-0)+(240-0)=295
Prof J V Gorabal ,CSE ATMECE,Mysore
C-SCAN
• The C-SCAN algorithm, also known as the Circular
SCAN algorithm, is an improved version of the
SCAN algorithm aimed at minimizing seek time and
ensuring fairer servicing of requests throughout the
disk.
Prof J V Gorabal ,CSE ATMECE,Mysore
C-SCAN -Algo How It Works
Circular Movement: C-SCAN imagines the disk as a circular track,
eliminating the need for unnecessary travel to the opposite
end.
Serving Requests: The head moves in one direction (say, right)
servicing all pending requests in its path.
Reaching the End: Upon reaching the maximum cylinder
number (end of the "circular track"), it jumps directly to the
minimum cylinder number (beginning), servicing any requests
there.
Prof J V Gorabal ,CSE ATMECE,Mysore
CSCAN-Example : Direction-L-R HP:53
(65 - 53) + (98 - 65) + (122 - 98) + (124 - 122) + (183 - 124) + (1
99 - 183) + (199 - 0)
+ (10 - 0) + (40 - 10) =395
Prof J V Gorabal ,CSE ATMECE,Mysore
CSCAN-Example
• Consider, a disk contains 200 tracks (0-199) and the request queue
contains track number 82, 170, 43, 140, 24, 16,190, respectively.
The current position of R/W head is 50, and the direction is
towards the larger value. Calculate the total number of cylinders
moved by head using C-SCAN disk scheduling
Prof J V Gorabal ,CSE ATMECE,Mysore
CSCAN-Example
Prof J V Gorabal ,CSE ATMECE,Mysore
Answer is 391
• THM=(199-50)+(199-0)+(43-0)
• = 391
Prof J V Gorabal ,CSE ATMECE,Mysore
Look Algorithm
• The Look algorithm, also known as SCAN with a single
pass, is a disk scheduling algorithm that aims to minimize
seek time by optimizing head movement. Imagine the disk
head like an elevator moving between requests on the disk
platters. Here's how it works:
Prof J V Gorabal ,CSE ATMECE,Mysore
How it Works?
1. Start with the disk head at its current position.
2. Serve requests in the direction it's currently moving, servicing the
closest request first.
3. Once it reaches the end of the disk in that direction, reverse its
direction, but instead of going all the way back, only serve requests
encountered until the start of the disk.
4. Repeat steps 2 and 3 until no more requests are pending.
Prof J V Gorabal ,CSE ATMECE,Mysore
Look : Example
THM=(240-51)+ (240-15)=414
Prof J V Gorabal ,CSE ATMECE,Mysore
C-Look
• The C-LOOK (Circular LOOK) algorithm is an
enhanced version of the LOOK algorithm, further
improving seek time minimization for disk access.
Here's how it works:
Prof J V Gorabal ,CSE ATMECE,Mysore
How C-Look Algorithm Works
1. Start with the disk head at its current position.
2. Serve requests in the direction it's currently moving, servicing the closest request first.
3. Once it reaches the end of the disk in that direction, instead of reversing and serving the
remaining requests, it jumps directly to the farthest request in the opposite direction.
4. Serve requests encountered in that new direction until it reaches the starting point of the
disk.
5. Repeat steps 2-4 until no more requests are pending.
Prof J V Gorabal ,CSE ATMECE,Mysore
Acts and Laws to Govern Industrial Designs,
Design Rights,
Prof J V Gorabal ,CSE ATMECE,Mysore
C-Look Algorithm
• THM= |(100 – 90)| + |(90 – 40)| + |(40 – 25)| + |(25 – 180)| + |(180 – 135)| = 10 +
50 + 15 + 155 + 45 = 275 Cylinders
