Scheduling algorithm (SCAN, LOOK) in LLD - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to select the initial direction for the SCAN algorithm.

LLD

direction = [1]  # Choose initial head movement direction

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

A"down"

B"up"

C"right"

D"left"

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing a direction unrelated to disk tracks like 'up' or 'down'.

The SCAN algorithm moves the disk head initially towards the right (higher track numbers) or left (lower track numbers). Commonly, it starts moving right.

2fill in blank

medium

Complete the code to find the next request to service in the LOOK algorithm.

LLD

next_request = min([r for r in requests if r > current_head], default=[1])

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

A-1

BNone

C0

Dcurrent_head

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or -1 which may be valid track numbers and cause errors.

In LOOK, if no requests are ahead, min returns None to indicate no next request in that direction.

3fill in blank

hard

Fix the error in the code that updates the head position after servicing a request in SCAN.

LLD

current_head = [1]  # Update head to the serviced request

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

Anext_request

Brequests.pop()

Crequests[0]

Dcurrent_head + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using requests.pop() which removes but may not be the correct request.

Incrementing head by 1 regardless of request location.

The head should move to the position of the serviced request, which is stored in next_request.

4fill in blank

hard

Fill both blanks to complete the condition that reverses direction in SCAN when no requests remain in current direction.

LLD

if not any(r [1] current_head for r in requests):
    direction = [2]

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

A>

B<

C"left"

D"right"

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators or wrong direction strings.

If no requests are greater than the current head, the direction reverses to left.

5fill in blank

hard

Fill all three blanks to complete the LOOK algorithm's main loop for servicing requests.

LLD

while requests:
    if direction == [1]:
        next_request = min([r for r in requests if r > current_head], default=None)
    else:
        next_request = max([r for r in requests if r < current_head], default=None)
    if next_request is None:
        direction = [2] if direction == [1] else [1]
        continue
    current_head = [3]
    requests.remove(next_request)

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

A"right"

B"left"

Cnext_request

Dcurrent_head

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing direction strings, not updating head correctly, or reversing direction incorrectly.

The LOOK algorithm moves right or left depending on direction, reverses when no requests remain in that direction, and updates the head to the next request.

Practice

1. What is the main difference between the SCAN and LOOK disk scheduling algorithms?

easy

A. SCAN stops at the last request in the direction, LOOK goes to the disk edge

B. LOOK moves the head randomly, SCAN moves sequentially

C. LOOK stops at the last request in the direction, SCAN goes to the disk edge

D. SCAN only moves in one direction, LOOK moves back and forth

Solution

1. Step 1: Understand SCAN behavior

   SCAN moves the disk head to the end of the disk in one direction, servicing requests along the way.

2. Step 2: Understand LOOK behavior

   LOOK moves the disk head only as far as the last request in the current direction, then reverses.

3. Final Answer:

   LOOK stops at the last request in the direction, SCAN goes to the disk edge -> Option C

4. Quick Check:

   LOOK stops early, SCAN goes to edge [OK]

Hint: LOOK stops at last request, SCAN goes to disk edge [OK]

Common Mistakes:

• Confusing which algorithm stops at disk edge
• Thinking LOOK moves randomly
• Assuming SCAN moves only one way

2. Which of the following is the correct order of servicing requests using the SCAN algorithm if the head starts at 50 and requests are at [10, 20, 35, 70, 90] with disk size 100?

easy

A. 50 -> 70 -> 90 -> 35 -> 20 -> 10

B. 50 -> 70 -> 90 -> 100 -> 35 -> 20 -> 10

C. 50 -> 35 -> 20 -> 10 -> 0 -> 70 -> 90

D. 50 -> 90 -> 70 -> 35 -> 20 -> 10

Solution

1. Step 1: SCAN moves towards higher end first

   Starting at 50, SCAN moves up servicing 70 and 90, then reaches disk edge 100.

2. Step 2: SCAN reverses direction

   After reaching 100, it moves down servicing 35, 20, and 10.

3. Final Answer:

   50 -> 70 -> 90 -> 100 -> 35 -> 20 -> 10 -> Option B

4. Quick Check:

   SCAN goes to edge 100 before reversing [OK]

Hint: SCAN always goes to disk edge before reversing [OK]

Common Mistakes:

• Not including disk edge in the path
• Reversing direction too early
• Skipping requests on the way

3. Given the LOOK algorithm with head starting at 40 and requests at [10, 20, 35, 70, 90], what is the order of servicing requests if the head moves towards higher track numbers first?

medium

A. [40, 90, 70, 35, 20, 10]

B. [40, 70, 90, 100, 35, 20, 10]

C. [40, 35, 20, 10, 70, 90]

D. [40, 70, 90, 35, 20, 10]

Solution

1. Step 1: LOOK moves towards higher requests first

   Starting at 40, it services 70 and 90, stopping at last request 90.

2. Step 2: LOOK reverses direction

   Then it moves down servicing 35, 20, and 10, stopping at last request in that direction.

3. Final Answer:

   [40, 70, 90, 35, 20, 10] -> Option D

4. Quick Check:

   LOOK stops at last request, no disk edge [OK]

Hint: LOOK stops at last request, no disk edge [OK]

Common Mistakes:

• Including disk edge in LOOK path
• Reversing direction too early
• Skipping requests on the way

4. Identify the error in this SCAN algorithm implementation snippet where the head moves from 30 to 90 with requests at [20, 40, 60, 80]:

requests = [20, 40, 60, 80]
head = 30
for track in range(head, 100):
    if track in requests:
        print(f"Servicing {track}")
for track in range(head-1, -1, -1):
    if track in requests:
        print(f"Servicing {track}")

medium

A. The first loop should go to 101, not 100

B. The first loop should include the head position

C. The second loop should start from head, not head-1

D. The second loop should start from 99, not head-1

Solution

1. Step 1: Check range end in first loop

   range(head, 100) goes from 30 to 99 (exclusive end), missing disk edge at 100.

2. Step 2: Confirm disk convention

   As per standard problems (disk size 100 includes edge 100), first loop should be range(head, 101) to reach 100.

3. Final Answer:

   The first loop should go to 101, not 100 -> Option A

4. Quick Check:

   range exclusive, edge 100 needs 101 [OK]

Hint: Range end exclusive, use 101 for disk edge 100 [OK]

Common Mistakes:

• Confusing inclusive vs exclusive range ends
• Starting second loop incorrectly
• Assuming head position is included twice

5. You have a disk with size 200 tracks and requests at [10, 50, 120, 180]. The head is at 100 and moves using LOOK algorithm. What is the total head movement if the head moves towards lower track numbers first?

hard

A. 260 tracks

B. 160 tracks

C. 180 tracks

D. 120 tracks

Solution

1. Step 1: Initial direction to lower tracks

   Lower requests: 50, 10. Path: 100 -> 50 (50 tracks), 50 -> 10 (40 tracks). Subtotal: 90.

2. Step 2: Reverse direction to higher tracks

   Higher requests: 120, 180. Path: 10 -> 120 (110 tracks), 120 -> 180 (60 tracks). Subtotal: 170.

3. Step 3: Total head movement

   90 + 170 = 260 tracks.

4. Final Answer:

   260 tracks -> Option A

5. Quick Check:

   Sum of |current - next| over servicing sequence [OK]

Hint: Sum distances in servicing order: 100-50-10-120-180 [OK]

Common Mistakes:

• Including disk edges in LOOK movement
• Adding extra distances beyond last requests
• Misordering request servicing