SCAN (elevator algorithm) in Operating Systems - Mini Project: Build & Apply

SCAN (Elevator Algorithm) Step-by-Step

📖 Scenario: You are managing a disk drive that needs to service several read/write requests at different track positions. To reduce the total movement of the disk arm, you will simulate the SCAN (elevator) algorithm, which moves the arm in one direction servicing requests until it reaches the end, then reverses direction.

🎯 Goal: Build a simple step-by-step simulation of the SCAN algorithm by creating the request list, setting the initial head position and direction, processing the requests in order, and completing the scan cycle.

📋 What You'll Learn

Create a list of disk requests with exact track numbers

Set the initial head position and direction

Implement the SCAN algorithm logic to order requests

Complete the simulation by showing the final order of serviced requests

💡 Why This Matters

🌍 Real World

Disk scheduling algorithms like SCAN help operating systems reduce the time it takes to read or write data by minimizing the movement of the disk arm.

💼 Career

Understanding SCAN is important for roles in system programming, operating system development, and performance optimization.

1

Create the list of disk requests

Create a list called requests with these exact track numbers: 95, 180, 34, 119, 11, 123, 62, and 64.

Operating Systems

# Create the list of disk requests
# Your code here

Need a hint?

Use square brackets and separate the numbers with commas.

2

Set the initial head position and direction

Create a variable called head and set it to 50. Then create a variable called direction and set it to the string 'up' to indicate the disk arm moves towards higher track numbers first.

Operating Systems

requests = [95, 180, 34, 119, 11, 123, 62, 64]
# Set the initial head position and direction
# Your code here

Need a hint?

Use an integer for head and a string for direction.

3

Implement the SCAN algorithm logic

Create a list called up_list containing requests greater than or equal to head, sorted in ascending order. Create another list called down_list containing requests less than head, sorted in descending order.

Operating Systems

requests = [95, 180, 34, 119, 11, 123, 62, 64]
head = 50
direction = 'up'
# Separate requests into up_list and down_list
# Your code here

Need a hint?

Use list comprehensions with conditions and the sorted() function.

4

Complete the SCAN sequence of serviced requests

Create a list called scan_sequence. If direction is 'up', set scan_sequence to up_list followed by down_list. Otherwise, set it to down_list followed by up_list.

Operating Systems

requests = [95, 180, 34, 119, 11, 123, 62, 64]
head = 50
direction = 'up'
up_list = sorted([r for r in requests if r >= head])
down_list = sorted([r for r in requests if r < head], reverse=True)
# Create scan_sequence based on direction
# Your code here

Need a hint?

Use an if statement to check direction and combine the lists accordingly.