C-SCAN (circular SCAN) in Operating Systems - Mini Project: Build & Apply

C-SCAN Disk Scheduling Algorithm Simulation

📖 Scenario: You are working in an operating system team. You need to simulate the C-SCAN disk scheduling algorithm to understand how it manages disk head movement for servicing requests efficiently.

🎯 Goal: Build a Python program that simulates the C-SCAN disk scheduling algorithm. The program will take a list of disk requests and the initial head position, then calculate the order in which requests are serviced and the total head movement.

📋 What You'll Learn

Create a list called requests with exact disk request positions: 95, 180, 34, 119, 11, 123, 62, 64

Create an integer variable called head with the initial head position 50

Create an integer variable called disk_size with the value 200 representing the total number of cylinders

Implement the C-SCAN algorithm logic to service requests in one direction and then jump to the start

Calculate the total head movement in servicing all requests

💡 Why This Matters

🌍 Real World

Disk scheduling algorithms like C-SCAN are used in operating systems to reduce the time the disk head spends moving between requests, improving performance.

💼 Career

Understanding disk scheduling is important for roles in system programming, OS development, and performance optimization.

1

Create the initial data setup

Create a list called requests with these exact values: 95, 180, 34, 119, 11, 123, 62, 64. Also create an integer variable called head and set it to 50.

Operating Systems

# Create the list of disk requests and initial head position
# Your code here

Hint

Use a Python list for requests and assign the exact numbers. Use a simple integer variable for head.

2

Add disk size configuration

Create an integer variable called disk_size and set it to 200 to represent the total number of cylinders on the disk.

Operating Systems

requests = [95, 180, 34, 119, 11, 123, 62, 64]
head = 50
# Create disk_size variable
# Your code here

Hint

Use a simple integer variable named disk_size and assign 200.

3

Implement the C-SCAN algorithm logic

Write code to implement the C-SCAN algorithm: sort the requests, split them into two lists based on the head position, service requests moving upwards, then jump to the start (0), and service remaining requests. Store the service order in a list called seek_sequence.

Operating Systems

requests = [95, 180, 34, 119, 11, 123, 62, 64]
head = 50
disk_size = 200
# Implement C-SCAN logic and create seek_sequence list
# Your code here

Hint

Sort the requests, split into two lists by comparing with head, then append requests from right list, add the jump to end and start, then append left list requests.

4

Calculate total head movement

Calculate the total head movement by summing the absolute differences between the head and the first request in seek_sequence, then between each consecutive request in seek_sequence. Store the result in a variable called total_movement.

Operating Systems

requests = [95, 180, 34, 119, 11, 123, 62, 64]
head = 50
disk_size = 200

requests.sort()

left = [r for r in requests if r = head]

seek_sequence = []

# Service requests on the right of head
for r in right:
    seek_sequence.append(r)

# Jump to the start (0) after reaching the end
seek_sequence.append(disk_size - 1)  # Move to the last cylinder
seek_sequence.append(0)  # Jump to the first cylinder

# Service requests on the left of head
for r in left:
    seek_sequence.append(r)

# Calculate total head movement
# Your code here

Hint

Start from head, add the absolute difference to each request in seek_sequence to total_movement.

Practice

1. What is the main characteristic of the C-SCAN disk scheduling algorithm?

easy

A. The disk arm moves back and forth serving requests in both directions.

B. The disk arm moves in one direction and jumps back to the start without serving requests on return.

C. The disk arm serves requests randomly without any specific order.

D. The disk arm serves only the nearest request to its current position.

Solution

1. Step 1: Understand C-SCAN movement

   C-SCAN moves the disk arm in one direction only, serving requests along the way.

2. Step 2: Identify behavior at the end of the disk

   After reaching the last track, it jumps back to the first track without serving requests during the return.

3. Final Answer:

   The disk arm moves in one direction and jumps back to the start without serving requests on return. -> Option B

4. Quick Check:

   C-SCAN moves one way and jumps back = A [OK]

Hint: Remember: C-SCAN moves one way, then jumps back [OK]

Common Mistakes:

• Thinking C-SCAN moves back and forth like SCAN
• Assuming requests are served during the return jump
• Confusing C-SCAN with random or nearest request scheduling

2. Which of the following is the correct way to describe the jump in C-SCAN?

easy

A. The disk arm jumps back to the first track without serving any requests during the jump.

B. The disk arm stops and waits for new requests before moving.

C. The disk arm reverses direction and serves requests immediately.

D. The disk arm jumps back to the first track and serves requests on the way.

Solution

1. Step 1: Analyze the jump behavior in C-SCAN

   C-SCAN jumps back to the first track after reaching the last track.

2. Step 2: Check if requests are served during the jump

   Requests are not served during this jump; the arm moves quickly without processing.

3. Final Answer:

   The disk arm jumps back to the first track without serving any requests during the jump. -> Option A

4. Quick Check:

   Jump without serving requests = D [OK]

Hint: Jump skips requests, no service during return [OK]

Common Mistakes:

• Assuming requests are served during the jump
• Confusing jump with reversing direction
• Thinking the arm waits before jumping

3. Consider a disk with tracks numbered 0 to 199. The disk arm is currently at track 50 and requests are at tracks 95, 180, 34, and 119. Using C-SCAN, which track will the arm serve immediately after 50?

medium

A. 95

B. 34

C. 119

D. 180

Solution

1. Step 1: Identify requests ahead of current position

   Requests are at 34, 95, 119, 180. Current position is 50. C-SCAN moves forward only, so it serves requests with track numbers greater than 50 first: 95, 119, 180.

2. Step 2: Find the nearest request ahead

   The nearest request ahead is at track 95, so it will be served immediately after 50.

3. Final Answer:

   95 -> Option A

4. Quick Check:

   Next request after 50 going forward = 95 [OK]

Hint: Serve next higher track number after current position [OK]

Common Mistakes:

• Serving requests behind current position before forward ones
• Choosing the closest track number regardless of direction
• Confusing C-SCAN with SCAN which moves back and forth

4. A student wrote that in C-SCAN, the disk arm serves requests while moving back to the first track after reaching the last track. What is wrong with this statement?

medium

A. C-SCAN does not move back to the first track; it reverses direction instead.

B. C-SCAN serves requests randomly, so direction does not matter.

C. C-SCAN serves requests only while moving forward, not during the jump back.

D. C-SCAN serves requests only at the last track.

Solution

1. Step 1: Review C-SCAN jump behavior

   C-SCAN moves forward serving requests, then jumps back to the first track without serving requests during the jump.

2. Step 2: Identify the error in the student's statement

   The student incorrectly said requests are served during the jump back, which is false.

3. Final Answer:

   C-SCAN serves requests only while moving forward, not during the jump back. -> Option C

4. Quick Check:

   Requests served only forward, not on jump = C [OK]

Hint: Requests served only forward, jump is skip [OK]

Common Mistakes:

• Thinking C-SCAN reverses direction instead of jumping
• Assuming requests are served during the jump
• Confusing C-SCAN with SCAN algorithm

5. Given a disk with tracks 0 to 199, the disk arm is at track 150. Requests are at tracks 10, 170, 15, 190, and 30. Using C-SCAN, what is the order in which the disk arm will serve these requests?

hard

A. 30, 15, 10, 190, 170

B. 10, 15, 30, 170, 190

C. 190, 170, 30, 15, 10

D. 170, 190, 10, 15, 30

Solution

1. Step 1: Identify requests ahead of current position 150

   Requests ahead are 170 and 190. C-SCAN serves these first moving forward.

2. Step 2: After reaching last track, jump to start and serve remaining requests

   After 190, the arm jumps to track 0 and serves requests at 10, 15, and 30 in ascending order.

3. Final Answer:

   170, 190, 10, 15, 30 -> Option D

4. Quick Check:

   Serve forward requests, jump, then serve from start = A [OK]

Hint: Serve forward requests first, then jump and serve from start [OK]

Common Mistakes:

• Serving requests behind current position before forward ones
• Serving requests in descending order
• Ignoring the jump and serving requests in wrong order