Secondary-Storage Structures
Understanding how data is stored, accessed, and managed on disk systems
Introduction to Secondary Storage
What is Secondary Storage?
Disk is secondary storage used to store data persistently. Unlike primary
memory (RAM), secondary storage retains information even when power is
off.
Data is provided to user programs through I/O requests, which are managed
by the operating system to ensure efficient access and retrieval.
Physical Disk Structure
Understanding the physical organization of magnetic disks is essential for optimizing storage performance.
Platters Tracks
Magnetic disks connected by a spindle that stores data on circular Circular rings on platter surfaces where data is organized
surfaces
Sectors
Each track is further divided into small pieces called sectors. Cylinders
A sector is the smallest unit of storage on a disk Tracks at the same arm position across all platters
(typically 512 bytes or 4096 bytes).
Disk Organization Hierarchy
Cylinder Numbering
Numbered starting with zero, from outermost to innermost cylinder
Track Numbering
Numbered starting with zero, from top track to bottom track
Sector Numbering
Start with zero, arranged counterclockwise from reference position
Device Types by Access Method
Character Devices Block Devices
Devices where data is accessed character by character or byte by Entire blocks of data are accessed or written at once, providing
byte. Data can be written in the form of individual characters or more efficient data transfer for large amounts of information.
bytes.
Example: Magnetic disk, floppy disk, CD
Example: Printer
Magnetic Tape Storage
Magnetic tape provides sequential storage where data is written
and read in a sequence as the tape passes through the read/write
head.
• Entire tape is divided into 9 tracks for storing data
• First 8 tracks contain 8 bits of data
• 9th track contains parity bit for error checking
• Data is stored in the form of records
• Multiple bytes form a single record
Disk Access Time Components
Seek Time
1 Seek time is the time the disk’s read–write head takes to move to the
correct track (cylinder) on the disk where the required data is stored.
Latency Time
2 Latency time (also called rotational latency) is the time taken for the
desired sector on the disk to rotate under the read–write head.
Transfer Time
3
Time spent actually moving data to/from the disk surface
The time taken to move the disk arm to the desired cylinder is called the
____________
a) positioning time
b) random access time
c) seek time
d) rotational latency
Answer: c Seek Time
The time taken for the desired sector to rotate to the disk
head is called ____________
a) positioning time
b) random access time
c) seek time
d) rotational latency
Answer: d Rotational Latency
In _______ information is recorded magnetically on platters.
a) magnetic disks
b) electrical disks
c) assemblies
d) cylinders
Answer: a Magnetic Disks
Disk Scheduling Overview
What is Disk Scheduling?
Objective 1
Disk scheduling is a mechanism for arranging I/O requests in
Minimize response time
order to save unnecessary rotations by the disk arm and disk
pointer.
The operating system takes I/O requests from a queue and Objective 2
processes them one by one. The algorithm used to select which
I/O request is processed first is called a Disk Scheduling
Maximize throughput
Algorithm.
FCFS Disk Scheduling Algorithm-
As the name suggests, this algorithm entertains requests in the order they arrive in the
disk queue.
It is the simplest disk scheduling 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.
Problem-
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.
The total head movement (in number of cylinders) incurred while servicing these requests is
Solution:
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
SSTF Disk Scheduling Algorithm-
•SSTF stands for Shortest Seek Time First.
•This algorithm services that request next which requires least number of head
movements from its current position regardless of the direction.
•It breaks the tie in the direction of head movement.
Advantages-
It reduces the total seek time as compared to FCFS.
It provides increased throughput.
It provides less average response time and waiting time.
Disadvantages-
There is an overhead of finding out the closest request.
The requests which are far from the head might starve for the CPU.
It provides high variance in response time and waiting time.
Switching the direction of head frequently slows down the algorithm.
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. The total head movement (in number of cylinders)
incurred while servicing these requests is _______.
Solution:
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
Practice Problem:
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in
following sequence-
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all
requests if it takes 1 ms to move from one cylinder to adjacent one and shortest seek
time first policy is used?
a)95 ms
b)119 ms
c)233 ms
d)276 ms
SCAN Disk Scheduling Algorithm-
• In the SCAN algorithm the disk arm moves in a particular direction and services the requests coming
in its path and after reaching the end of the disk, it reverses its direction and again services the
request arriving in its path. So, this algorithm works as an elevator and is hence also known as
an elevator algorithm.
Advantages :
• High throughput
• Low variance of response time
Disadvantages of SCAN Algorithm:
• It causes the head to move till the end of the disk even if there are no requests to be serviced.
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. The total head movement (in
number of cylinders) incurred while servicing these requests is _______.
Solution:
Solution:
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
Alternatively:
Total head movements incurred while servicing these requests
= (199 – 53) + (199 – 14)
= 146 + 185
= 331
Practice Question:
Suppose the order of requests are 70, 140, 50, 125, 30, 25, 160 and the initial position of the Read-Write head is 60. And
it is given that the disk arm should move towards the larger value. Find Total head movements.
C-SCAN Disk Scheduling Algorithm-
• Circular-SCAN Algorithm is an improved version of the SCAN Algorithm.
• Head starts from one end of the disk and move towards the other end servicing
all the requests in between.
• After reaching the other end, head reverses its direction.
• It then returns to the starting end without servicing any request in between.
• The same process repeats.
• It causes more head 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.
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. The total head movement (in
number of cylinders) incurred while servicing these requests is _______.
Solution:
Solution:
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
LOOK
• LOOK Algorithm is similar to the SCAN disk scheduling algorithm except for the difference that the
disk arm inspite of going to the end of the disk goes only to the last request to be serviced in front of
the head and then reverses its direction from there only. Thus it prevents the extra delay which
occurred due to unnecessary traversal to the end of the disk.
Advantages
Reduced Unnecessary Movement: The disk arm only goes as far as the last request in each direction, avoiding
travel to the disk’s physical end (unlike SCAN).
Faster Response: Less head movement leads to quicker service for requests.
Suppose the requests to be addressed are- 82,170,43,140,24,16,190 and the Read/Write arm is at
50, and it is also given that the disk arm should move "towards the larger value".
C-LOOK
• Suppose the requests to be addressed are-82,170,43,140,24,16,190 and the Read/Write arm is at 50, and it
is also given that the disk arm should move "towards the larger value"
Selecting a Disk-Scheduling Algorithm
• SSTF is common and has a natural appeal
• SCAN perform better for systems that place a heavy load on the disk.
• Performance depends on the number and types of requests.
• Requests for disk service can be influenced by the file-allocation method.
• The disk-scheduling algorithm should be written as a separate module of the operating system, allowing it to
be replaced with a different algorithm if necessary.
• Either SSTF or LOOK is a reasonable choice for the default algorithm.
A disk rotates at 10000 RPM. Average seek time = 3 ms, sector size = 512 bytes, 600 sectors per track. What is
the average rotational latency?
a) 2 ms
b) 3 ms
c) 4 ms
d) 5 ms
Ans 3 sec.