OS Fast Slow Learner Ac vity

Topic: Disk Scheduling algorithms and Page replacement strategies.

Disk scheduling
A process needs two types of me, CPU me and IO me. For I/O, it requests the Opera ng
system to access the disk. However, the opera ng system must be fair enough to sa sfy each
request and at the same me, opera ng system must maintain the efficiency and speed of
process execu on. The technique that opera ng system uses to determine the request which is
to be sa sfied next is called disk scheduling.

Some important terms related to disk scheduling:

• Seek Time: When an I/O request is made, the disk arm needs to move to the appropriate
track where the data is located. Seek me represents the me taken for this movement.
• Rota onal Latency: A er reaching the correct track, the disk must wait for the desired
sector to rotate under the read/write head. This wai ng me is known as rota onal
latency.
• Transfer Time: Once the desired sector is under the read/write head, the actual data
transfer occurs. Transfer me is the me taken for this process.
• Disk Access Time: The total me required to complete an I/O request is the sum of seek
me, rota onal latency, and transfer me.
• Disk Response Time: This is the average me spent by each I/O request wai ng for its turn
to be serviced.

Purpose of Disk Scheduling:

The main purpose of disk scheduling algorithm is to select a disk request from the queue of IO
requests and decide the schedule when this request will be processed.
 OS Fast Slow Learner Ac vity

Goal of Disk Scheduling Algorithm:

• Fairness
• High throughout
• Minimal traveling head me

Disk Scheduling Algorithms:

The list of various disks scheduling algorithm is given below. Each algorithm is carrying
some advantages and disadvantages. The limita on of each algorithm leads to the
evolu on of a new algorithm.
• First Come First Serve (FCFS): Simplest disk scheduling algorithm where requests are
serviced in the order they arrive. While fair, it may lead to longer wait mes and inefficient
disk u liza on.
• Shortest Seek Time First (SSTF): Priori zes servicing requests closest to the current
posi on of the disk arm, thereby minimizing seek me. However, it may neglect requests
further away, poten ally leading to starva on.
• SCAN: Also known as the elevator algorithm, SCAN moves the disk arm in one direc on,
servicing requests along the way, un l it reaches the end of the disk, then reverses
direc on. This ensures more uniform wait mes for requests.
• C-SCAN: Similar to SCAN, but a er reaching the end of the disk, the disk arm jumps to the
other end without servicing any requests in between. This further reduces wait mes for
requests.
• LOOK: Similar to SCAN, but instead of reaching the end of the disk, the disk arm reverses
direc on when it reaches the last request in its path. This reduces unnecessary traversal
to the end of the disk.
• C-LOOK: Similar to C-SCAN, it jumps to the other end of the disk a er reaching the last
request in its path, reducing unnecessary traversal and improving overall efficiency.

FCFS (First Come First Serve)

This is the simplest disk scheduling algorithm where requests are serviced in the order they arrive.
While fair, it may lead to longer wait mes and inefficient disk u liza on.
Example:
Suppose the order of request is- (82, 170, 43, 140, 24, 16, 190)
And current posi on of Read/Write head is: 50
 OS Fast Slow Learner Ac vity

Figure 1: FCFS

So, total overhead movement (total distance covered by the disk arm) = (82-50) + (170-82) + (170-
43) + (140-43) + (140-24) + (24-16) + (190-16) = 642

Advantages of FCFS:
• Every request gets a fair chance
• No indefinite postponement

Disadvantages of FCFS:
• Does not try to op mize seek me
• May not provide the best possible service

SSTF (Shortest Seek Time First)

This disk scheduling algorithm selects the request which is closest to the current head posi on
before moving the head away to service other requests. This is done by selec ng the request
which has the least seek me from the current head posi on.
Example:
Suppose the order of request is- (82, 170, 43, 140, 24, 16, 190)
And current posi on of Read/Write head is: 50
 OS Fast Slow Learner Ac vity

Figure 2: SSTF

So, total overhead movement (total distance covered by the disk arm) = (50-43) + (43-24) + (2416)
+ (82-16) + (140-82) + (170-140) + (190-170) = 208 Advantages of Shortest Seek Time First:
• The average Response Time decreases
• Throughput increases

Disadvantages of Shortest Seek Time First:

• Overhead to calculate seek me in advance
• Can cause starva on for a request if it has a higher seek me as compared to incoming
requests
• The high variance of response me as SSTF favors only some requests

SCAN
It is also known as the elevator algorithm. SCAN moves the disk arm in one direc on, servicing
requests along the way, un l it reaches the end of the disk, then reverses direc on. This ensures
more uniform wait mes for requests.
Example:
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”.
 OS Fast Slow Learner Ac vity

Figure 3: SCAN

Therefore, the total overhead movement (total distance covered by the disk arm) is calculated
as = (199-50) + (199-16) = 332 Advantages of SCAN Algorithm:  High throughput
• Low variance of response me
• Average response me

Disadvantages of SCAN Algorithm

• Long wai ng me for requests for loca ons just visited by disk arm

C-SCAN (Circular SCAN)

Similar to SCAN, but a er reaching the end of the disk, the disk arm jumps to the other end
without servicing any requests in between. This further reduces wait mes for requests.
Example:
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”.
 OS Fast Slow Learner Ac vity

Figure 4: C-SCAN

So, the total overhead movement (total distance covered by the disk arm) is calculated as:
= (199-50) + (199-0) + (43-0) = 391 Advantages of C-SCAN Algorithm:
• Provides more uniform wait me compared to SCAN.

Disadvantages of C-SCAN Algorithm

• C-SCAN can lead to longer wai ng mes for requests located just visited by the disk arm.
• The algorithm services requests in one direc on before jumping to the other end, poten ally
delaying the servicing of requests behind the disk arm's path.
• This delay can increase response mes, especially under heavy disk I/O loads

LOOK
LOOK Algorithm is similar to the SCAN disk scheduling algorithm except for the difference that the
disk arm in spite 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 direc on from there only. Thus, it prevents the extra delay
which occurred due to unnecessary traversal to the end of the disk.
Example:
 OS Fast Slow Learner Ac vity

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”.

Figure 5: LOOK

So, the total overhead movement (total distance covered by the disk arm) is calculated as:
= (190-50) + (190-16) = 314 Advantages of LOOK:
• Reduced head movement by reversing direc on at the last request.
• Improved efficiency by avoiding unnecessary traversal to the disk's end.

Disadvantages of LOOK:
• Poten al for uneven wait mes due to gaps between requests.
• Possibility of starva on for requests at the edges of the disk's path.

C-LOOK (Circular LOOK)

Similar to SCAN, but instead of reaching the end of the disk, the disk arm reverses direc on when
it reaches the last request in its path. This reduces unnecessary traversal to the end of the disk.
Example:
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”.
 OS Fast Slow Learner Ac vity

Figure 6: C-LOOK

So, the total overhead movement (total distance covered by the disk arm) is calculated as =
(190-50) + (190-16) + (43-16) = 341

Advantages of C-LOOK:
• Provides more uniform wait mes for requests compared to LOOK.
• Reduces head movement and improves disk performance.

Disadvantages of C-LOOK:
• May s ll encounter uneven request distribu on leading to poten al delays.
• Possibility of starva on for requests at the edges of the disk's path.

Page Replacement
In an opera ng system that uses paging for memory management, a page replacement algorithm
is needed to decide which page needs to be replaced when a new page comes in. Page
replacement becomes necessary when a page fault occurs and there are no free page frames in
memory. However, another page fault would arise if the replaced page is referenced again. Hence
it is important to replace a page that is not likely to be referenced in the immediate future. y. If
no page frame is free, the virtual memory manager performs a page replacement opera on to
replace one of the pages exis ng in memory with the page whose reference caused the page
fault. It is performed as follows: The virtual memory manager uses a page replacement algorithm
 OS Fast Slow Learner Ac vity

to select one of the pages currently in memory for replacement, accesses the page table entry of
the selected page to mark it as “not present” in memory, and ini ates a page-out opera on for it
if the modified bit of its page table entry indicates that it is a dirty page.

Page Fault:
A page fault happens when a running program accesses a memory page that is mapped into the
virtual address space but not loaded in physical memory. Since actual physical memory is much
smaller than virtual memory, page faults happen. In case of a page fault, Opera ng System might
have to replace one of the exis ng pages with the newly needed page. Different page
replacement algorithms suggest different ways to decide which page to replace. The target for all
algorithms is to reduce the number of page faults.
Page Replacement Algorithms:

The three types of Page Replacement Algorithms are:

1. First in First Out (FIFO): The oldest page in memory is evicted, regardless of its usage history.
Simple but may suffer from the "Belady's Anomaly" where increasing the number of frames
can lead to more page faults.
2. Op mal Page Replacement: Evicts the page that will not be used for the longest me in the
future, based on future knowledge. Theore cally op mal but imprac cal due to the need for
future informa on.
3. Least Recently Used (LRU): Evicts the page that has not been accessed for the longest me.
LRU requires maintaining a list of recently accessed pages, which can be computa onally
expensive but effec ve in many scenarios.

First in First out Page Replacement Algorithm

This is the first basic algorithm of Page Replacement Algorithms. This algorithm is basically
dependent on the number of frames used. Then each frame takes up the certain page and tries
to access it. When the frames are filled then the actual problem starts. The fixed number of
frames is filled up with the help of first frames present. This concept is fulfilled with the help of
Demand Paging. A er filling up of the frames, the next page in the wai ng queue tries to enter
the frame. If the frame is present then, no problem is occurred. Because of the page which is to
be searched is already present in the allocated frames. If the page to be searched is found among
the frames then, this process is known as Page Hit. If the page to be searched is not found among
the frames then, this process is known as Page Fault. When Page Fault occurs this problem arises,
then the First in First Out Page Replacement Algorithm comes into picture. The First in First Out
(FIFO) Page Replacement Algorithm removes the Page in the frame which is allo ed long back.
This means the useless page which is in the frame for a longer me is removed and the new page
which is in the ready queue and is ready to occupy the frame is allowed by the First in First Out
Page Replacement.
Example:
 OS Fast Slow Learner Ac vity

Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0 for a memory with

three frames and calculate number of page faults by using FIFO (First in First Out) Page
replacement algorithms.

Figure 7: FIFO page replacement

Number of Page Hits = 8

Number of Page Faults = 12
The Ra o of Page Hit to the Page Fault = 8: 12 - - - > 2: 3 - - - > 0.66
The Page Hit Percentage = 8 *100 / 20 = 40%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 40 = 60%

Op mal Page Replacement Algorithm

This is the second basic algorithm of Page Replacement Algorithms. This algorithm is basically
dependent on the number of frames used. Then each frame takes up the certain page and tries
to access it. When the frames are filled then the actual problem starts. The fixed number of
frames is filled up with the help of first frames present. This concept is fulfilled with the help of
Demand Paging. A er filling up of the frames, the next page in the wai ng queue tries to enter
the frame. If the frame is present then, no problem is occurred. Because of the page which is to
be searched is already present in the allocated frames. If the page to be searched is found among
the frames then, this process is known as Page Hit. If the page to be searched is not found among
the frames then, this process is known as Page Fault. When Page Fault occurs this problem arises,
then the Op mal Page Replacement Algorithm comes into picture. The Op mal Page
Replacement Algorithms works on a certain principle. The principle is: Replace the Page which is
not used in the Longest Dimension of me in future. This principle means that a er all the frames
are filled then, see the future pages which are to occupy the frames. Go on checking for the pages
which are already available in the frames. Choose the page which is at last.
Example:
 OS Fast Slow Learner Ac vity

Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 4, 0 for a memory with

three frames and calculate number of page faults by using Op mal Page replacement algorithms.

Figure 8: Op mal page replacement

Number of Page Hits = 8

Number of Page Faults = 12
The Ra o of Page Hit to the Page Fault = 8: 12 - - - > 2: 3 - - - > 0.66
The Page Hit Percentage = 8 *100 / 20 = 40%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 40 = 60%

Least Recently Used (LRU) Replacement Algorithm

This is the last basic algorithm of Page Replacement Algorithms. This algorithm is basically
dependent on the number of frames used. Then each frame takes up the certain page and tries
to access it. When the frames are filled then the actual problem starts. The fixed number of
frames is filled up with the help of first frames present. This concept is fulfilled with the help of
Demand Paging. A er filling up of the frames, the next page in the wai ng queue tries to enter
the frame. If the frame is present then, no problem is occurred. Because of the page which is to
be searched is already present in the allocated frames. If the page to be searched is found among
the frames then, this process is known as Page Hit. If the page to be searched is not found among
the frames then, this process is known as Page Fault. When Page Fault occurs this problem arises,
then the Least Recently Used (LRU) Page Replacement Algorithm comes into picture. The Least
Recently Used (LRU) Page Replacement Algorithms works on a certain principle. The principle is:
Replace the page with the page which is less dimension of me recently used page in the past.
Example:
Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0 for a memory with
three frames and calculate number of page faults by using Least Recently Used (LRU) Page
replacement algorithms.
 OS Fast Slow Learner Ac vity

Figure 9: LRU page replacement

Number of Page Hits = 7

Number of Page Faults = 13
The Ra o of Page Hit to the Page Fault = 7: 12 - - - > 0.5833: 1
The Page Hit Percentage = 7 * 100 / 20 = 35%
The Page Fault Percentage =
100 - Page Hit Percentage = 100 - 35 = 65%

Conclusion
In conclusion, disk scheduling algorithms and page replacement strategies play crucial roles in
enhancing the performance and efficiency of opera ng systems. Disk scheduling algorithms
determine the order in which disk I/O requests are serviced, aiming to minimize seek me and
maximize throughput.
Page replacement strategies, on the other hand, manage the alloca on of physical memory
efficiently by swapping out pages from main memory to secondary storage when needed.
Through the explora on of various disk scheduling algorithms such as FCFS, SSTF, SCAN, CSCAN,
LOOK, and C-LOOK, as well as page replacement strategies like FIFO, Op mal, LRU, LFU, and NRU,
it becomes evident that each approach has its strengths and weaknesses depending on the
specific system requirements and workload characteris cs. While some algorithms priori ze
fairness and simplicity, others focus on op mizing performance metrics such as response me,
throughput, and resource u liza on.
Similarly, page replacement strategies aim to minimize page faults and improve overall system
performance by intelligently managing the limited physical memory resources.
In prac ce, the selec on of disk scheduling algorithms and page replacement strategies should
be based on a thorough understanding of the system's workload, hardware constraints, and
performance objec ves. By carefully choosing and implemen ng the most appropriate
algorithms and strategies, system designers can effec vely balance compe ng priori es and
 OS Fast Slow Learner Ac vity

op mize the overall performance of the system. Furthermore, ongoing research and
development in this field con nue to drive innova on, leading to the emergence of new
techniques and approaches aimed at further improving the efficiency and responsiveness of
modern compu ng systems.