SCAN (elevator algorithm) in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does the SCAN (elevator) algorithm decide the direction of disk head movement?

The SCAN algorithm moves the disk head in one direction servicing requests until it reaches the end, then reverses direction. What determines the initial direction of the disk head movement?

A It starts moving in the direction of the closest pending request from the current head position.

B It always starts moving towards the lowest track number first.

C It moves randomly either towards the highest or lowest track number.

D It always starts moving towards the highest track number first.

💡 Hint

Think about how the algorithm minimizes seek time by choosing the nearest request direction.

The SCAN algorithm chooses the direction based on the closest pending request to minimize seek time, moving the head towards that direction first before reversing.

🚀 Application

intermediate

Calculate total head movement using SCAN algorithm

Given a disk with 200 tracks (0-199), the disk head is currently at track 50, and the pending requests are at tracks 20, 90, 150, and 180. If the head moves towards the higher track numbers first, what is the total head movement (in tracks) to service all requests using the SCAN algorithm?

A 280 tracks

B 230 tracks

C 260 tracks

D 290 tracks

💡 Hint

Remember the head moves up to the highest request or end, then reverses to service remaining requests.

The head moves from 50 to 180 (130 tracks), then reverses to 20 (160 tracks), totaling 290 tracks.

🔍 Analysis

advanced

Compare SCAN and LOOK algorithms in disk scheduling

Which of the following statements correctly describes a key difference between the SCAN and LOOK disk scheduling algorithms?

A LOOK moves the head to the end of the disk regardless of requests, while SCAN only moves as far as the last request in each direction.

B Both SCAN and LOOK always move the head to the end of the disk before reversing direction.

C SCAN moves the head to the end of the disk regardless of requests, while LOOK only moves as far as the last request in each direction.

D Neither SCAN nor LOOK reverses direction; they both move in a circular pattern.

💡 Hint

Consider how far the head travels in each algorithm relative to pending requests.

SCAN moves the head all the way to the disk's end before reversing, even if no requests exist there. LOOK moves only as far as the last request in the current direction before reversing.

❓ Reasoning

advanced

Why does SCAN algorithm reduce starvation compared to SSTF?

Starvation happens when some requests wait indefinitely. Why does the SCAN algorithm reduce starvation compared to the Shortest Seek Time First (SSTF) algorithm?

A Because SCAN always picks the closest request next, like SSTF, so starvation is the same.

B Because SCAN services requests in a fixed direction order, ensuring all requests are eventually reached.

C Because SCAN ignores requests at the ends of the disk, focusing only on the middle tracks.

D Because SCAN randomly selects requests to service, preventing starvation.

💡 Hint

Think about how SCAN moves the head systematically across the disk.

SCAN moves the head in one direction servicing all requests along the way, so no request is skipped indefinitely, reducing starvation compared to SSTF which can keep picking closer requests and ignore far ones.

📋 Factual

expert

Identify the output of SCAN algorithm with given requests and head position

Consider a disk with tracks numbered 0 to 199. The disk head is at track 100. Pending requests are at tracks 95, 180, 34, 119, and 11. The SCAN algorithm moves towards the lower track numbers first. What is the order in which the requests will be serviced?

A 95, 34, 11, 119, 180

B 95, 34, 11, 180, 119

C 11, 34, 95, 119, 180

D 180, 119, 95, 34, 11

💡 Hint

Remember SCAN moves in one direction servicing requests, then reverses.

The head moves down servicing 95, 34, 11, then reverses and moves up servicing 119, 180.