SCAN (elevator algorithm) in Operating Systems - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to describe the direction of the SCAN algorithm.

Operating Systems

The SCAN algorithm moves the disk arm in one [1] until it reaches the end of the disk.

Drag options to blanks, or click blank then click option'

Atrack

Bspeed

Cqueue

Ddirection

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing 'direction' with 'speed' or 'track'.

Thinking the arm moves randomly instead of in a set direction.

The SCAN algorithm moves the disk arm in one direction servicing requests until it reaches the end of the disk.

2fill in blank

medium

Complete the code to explain what happens after the SCAN algorithm reaches the last request in one direction.

Operating Systems

After reaching the end of the disk in one direction, the disk arm [1] and starts servicing requests in the opposite direction.

Drag options to blanks, or click blank then click option'

Areverses

Bstops permanently

Caccelerates

Dignores

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming the arm stops permanently after reaching the end.

Thinking the arm accelerates instead of reversing.

After reaching the end of the disk in one direction, the disk arm reverses and starts servicing requests in the opposite direction.

3fill in blank

hard

Fix the error in the description of the SCAN algorithm's movement.

Operating Systems

The SCAN algorithm moves the disk arm in one direction to service requests, reversing direction at the end of the disk. This is called [1].

Drag options to blanks, or click blank then click option'

ALOOK

BFCFS

CSCAN

DC-SCAN

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing SCAN with FCFS which is first-come, first-served.

Mixing SCAN with LOOK or C-SCAN algorithms.

The SCAN algorithm moves the disk arm in one direction servicing requests and reverses direction at the disk's end. It is also called the elevator algorithm.

4fill in blank

hard

Fill both blanks to complete the SCAN algorithm's behavior description.

Operating Systems

The SCAN algorithm services requests by moving the disk arm towards the [1] end, then reverses direction at the [2] end.

Drag options to blanks, or click blank then click option'

Astart

Bmiddle

Cend

Drandom

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'middle' or 'random' instead of 'start' or 'end'.

Not understanding the arm reverses at the disk's physical ends.

The SCAN algorithm moves the disk arm towards the start end of the disk, then reverses direction at the end end, servicing requests along the way.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension describing SCAN's request servicing.

Operating Systems

serviced = {track: requests[track] for track in range([1], [2], [3]) if track in requests}

Drag options to blanks, or click blank then click option'

Astart_track

Bend_track

Cstep

Drandom_track

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'random_track' which is not valid for range.

Mixing up start and end positions or forgetting the step.

This comprehension collects requests from start_track to end_track moving by step (which can be +1 or -1 depending on direction) to simulate SCAN's servicing order.

Practice

1. What is the main idea behind the SCAN (elevator) disk scheduling algorithm?

easy

A. Requests are served in the exact order they arrive without reordering.

B. The disk arm moves in one direction, servicing requests until it reaches the end, then reverses direction.

C. The disk arm jumps directly to the closest request regardless of direction.

D. The disk arm moves randomly to service requests.

Solution

1. Step 1: Understand SCAN movement

   SCAN moves the disk arm in one direction, serving all requests along the way until it reaches the last track in that direction.

2. Step 2: Direction reversal

   After reaching the end, the arm reverses direction and serves requests on the way back, similar to an elevator moving up and down.

3. Final Answer:

   The disk arm moves in one direction, servicing requests until it reaches the end, then reverses direction. -> Option B

4. Quick Check:

   SCAN = moves one way then reverses [OK]

Hint: Think of SCAN like an elevator moving up and down [OK]

Common Mistakes:

• Confusing SCAN with FCFS (first-come, first-served)
• Thinking SCAN jumps directly to closest request
• Assuming SCAN moves randomly

2. Which of the following correctly describes the order in which SCAN services disk requests?

easy

A. It services the closest request next, regardless of direction.

B. It services requests in the order they arrive without reordering.

C. It services requests by moving the arm in one direction, then reverses at the end.

D. It randomly selects requests to service next.

Solution

1. Step 1: Identify SCAN's servicing order

   SCAN moves the disk arm in one direction, servicing all requests in that path.

2. Step 2: Direction reversal at end

   When the arm reaches the last request or the disk end, it reverses direction and services requests on the return path.

3. Final Answer:

   It services requests by moving the arm in one direction, then reverses at the end. -> Option C

4. Quick Check:

   SCAN = one direction then reverse [OK]

Hint: Remember SCAN moves like an elevator, up then down [OK]

Common Mistakes:

• Confusing SCAN with SSTF (closest request first)
• Assuming SCAN ignores direction
• Thinking SCAN services requests randomly

3. Given the disk requests at tracks [10, 22, 20, 2, 40, 6] and the disk arm currently at track 15 moving towards higher tracks, which request will SCAN service first?

medium

A. Track 20

B. Track 10

C. Track 6

D. Track 2

Solution

1. Step 1: Identify current arm position and direction

   The arm is at track 15 and moving towards higher tracks (upwards).

2. Step 2: Find the closest request in the moving direction

   Requests above 15 are 20, 22, and 40. The closest is track 20.

3. Final Answer:

   Track 20 -> Option A

4. Quick Check:

   SCAN services requests ahead in current direction first [OK]

Hint: Pick closest request ahead in current direction [OK]

Common Mistakes:

• Choosing requests behind current arm position
• Ignoring arm's moving direction
• Picking the closest request overall instead of in direction

4. A disk arm is at track 50 moving towards track 0. The requests are at tracks [10, 20, 30, 40, 60]. Which request will SCAN service next? Identify the error in this reasoning: "Since the arm is moving towards 0, it will service track 60 next because it is the closest."

medium

A. The arm will service track 60 next; no error in reasoning.

B. The arm will service track 20 next; the error is ignoring request order.

C. The arm will service track 10 next; the error is assuming direction matters.

D. The arm will service track 40 next; the error is ignoring the arm's direction.

Solution

1. Step 1: Understand arm direction and position

   The arm is at track 50 moving towards 0 (downwards).

2. Step 2: Identify requests in arm's direction

   Requests below 50 are 10, 20, 30, 40; above 50 is 60.

3. Step 3: Find next request in direction

   The closest request in the moving direction is track 40, not 60.

4. Final Answer:

   The arm will service track 40 next; the error is ignoring the arm's direction. -> Option D

5. Quick Check:

   SCAN respects arm direction when choosing requests [OK]

Hint: Always consider arm direction before picking requests [OK]

Common Mistakes:

• Ignoring arm direction and picking closest request overall
• Assuming SCAN jumps to farthest request
• Confusing SCAN with SSTF

5. A disk arm is at track 50 on a disk with tracks numbered 0 to 199. Requests are at tracks [95, 180, 34, 119, 11, 123, 62, 64]. The arm is moving towards higher tracks. Using the SCAN algorithm, what is the order in which the requests will be serviced?

hard

A. [62, 64, 95, 119, 123, 180, 199, 34, 11]

B. [62, 64, 95, 119, 123, 180, 34, 11]

C. [95, 119, 123, 180, 199, 64, 62, 34, 11]

D. [95, 119, 123, 180, 64, 62, 34, 11]

Solution

1. Step 1: Identify requests above current arm position

   Arm at 50 moving up; requests above 50 are 62, 64, 95, 119, 123, 180.

2. Step 2: Service requests upwards in order

   Requests are serviced in ascending order: 62, 64, 95, 119, 123, 180.

3. Step 3: Reach end of disk and reverse

   SCAN continues to the last track (199) before reversing direction.

4. Step 4: Service remaining requests on return

   On return, service requests below 50 in descending order: 34, then 11.

5. Final Answer:

   [62, 64, 95, 119, 123, 180, 199, 34, 11] -> Option A

6. Quick Check:

   SCAN = up servicing, end, then down servicing [OK]

Hint: Service all requests up, go to end, then service down [OK]

Common Mistakes:

• Skipping the last track before reversing
• Not servicing requests in sorted order
• Ignoring requests on return path