LOOK and C-LOOK variants in Operating Systems - Deep Dive

Overview - LOOK and C-LOOK variants

What is it?

LOOK and C-LOOK are disk scheduling algorithms used by operating systems to decide the order in which disk I/O requests are processed. They improve efficiency by reducing the movement of the disk's read/write head. LOOK moves the head back and forth only as far as the last request in each direction, while C-LOOK moves the head in one direction and then jumps back to the start. These algorithms help speed up data access on hard drives.

Why it matters

Without efficient disk scheduling like LOOK and C-LOOK, the disk head would move unnecessarily long distances, causing delays and slower system performance. This would make computers feel sluggish, especially when many programs request data from the disk at once. These algorithms optimize disk usage, making computers faster and more responsive.

Where it fits

Before learning LOOK and C-LOOK, you should understand basic disk operations and simpler scheduling algorithms like FCFS (First-Come, First-Served) and SCAN. After mastering LOOK and C-LOOK, you can explore more advanced disk scheduling methods and how they integrate with modern storage technologies like SSDs.

Mental Model

Core Idea

LOOK and C-LOOK optimize disk head movement by only traveling as far as needed to serve requests, reducing wasted motion and improving speed.

Think of it like...

Imagine a librarian who only walks along the shelves as far as the last book requested, instead of walking all the way to the end every time. LOOK is like walking back and forth between requested books, while C-LOOK is like walking in one direction to the last requested book, then quickly returning to the start without checking shelves on the way back.

Disk requests: 10, 22, 37, 45, 70, 90

LOOK movement:
Start -> 10 -> 22 -> 37 -> 45 -> 70 -> 90 -> back to start

C-LOOK movement:
Start -> 10 -> 22 -> 37 -> 45 -> 70 -> 90 -> jump to 10 (no backward scanning)

┌─────────────┐
│ Disk Track  │
│ 0           │
│ 10 ●        │
│ 22 ●        │
│ 37 ●        │
│ 45 ●        │
│ 70 ●        │
│ 90 ●        │
│ 100         │
└─────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Disk Scheduling Basics

Concept: Disk scheduling decides the order of servicing disk requests to reduce wait time and head movement.

Disks have a read/write head that moves over tracks to access data. Requests come in for different tracks. Without scheduling, the head moves in the order requests arrive, which can cause a lot of unnecessary movement and slow performance.

Result

Recognizing that scheduling can reduce the total distance the head moves, improving speed.

Understanding that the physical movement of the disk head is a major factor in speed helps explain why scheduling matters.

2

Foundation

Introducing SCAN Algorithm

Concept: SCAN moves the disk head in one direction, servicing requests until it reaches the end, then reverses direction.

Imagine the head moving from the lowest to the highest track, servicing requests along the way, then moving back down. This reduces back-and-forth movement compared to FCFS.

Result

Less total head movement than FCFS, but sometimes the head travels to the end even if no requests are there.

SCAN improves efficiency by grouping requests in one direction but can waste time moving to empty ends.

3

Intermediate

LOOK Algorithm Optimization

🤔Before reading on: Do you think LOOK always goes to the disk's end like SCAN, or stops earlier? Commit to your answer.

Concept: LOOK improves SCAN by stopping the head movement at the last request in each direction instead of the disk's end.

Instead of moving all the way to the last track, LOOK moves only as far as the furthest request in the current direction, then reverses. This avoids unnecessary travel to empty tracks.

Result

Reduced head movement compared to SCAN, leading to faster servicing of requests.

Knowing that LOOK trims unnecessary travel helps understand how small changes can improve performance.

4

Intermediate

C-LOOK Algorithm Behavior

🤔Before reading on: Does C-LOOK move the head back by scanning in reverse or by jumping? Commit to your answer.

Concept: C-LOOK moves the head in one direction only, then jumps back to the start without servicing requests on the return.

The head moves from the lowest to the highest requested track, servicing requests, then quickly returns to the lowest request without scanning backward. This reduces wait times for requests near the start.

Result

More uniform wait times and less wasted movement compared to LOOK.

Understanding the jump-back behavior explains why C-LOOK can be fairer and faster in some cases.

5

Intermediate

Comparing LOOK and C-LOOK

🤔Before reading on: Which algorithm do you think provides more uniform wait times, LOOK or C-LOOK? Commit to your answer.

Concept: LOOK scans back and forth, while C-LOOK only scans in one direction and jumps back, affecting wait times and efficiency.

LOOK can cause longer waits for requests just behind the head's current position because it reverses direction. C-LOOK avoids this by always moving forward and jumping back, balancing wait times better.

Result

C-LOOK often provides more consistent response times, while LOOK may be simpler to implement.

Recognizing trade-offs between fairness and simplicity helps in choosing the right algorithm.

6

Advanced

Performance Impact in Real Systems

🤔Before reading on: Do you think these algorithms matter for SSDs as much as HDDs? Commit to your answer.

Concept: LOOK and C-LOOK optimize mechanical disk head movement, which is less relevant for SSDs but critical for HDDs.

In hard drives, reducing head movement saves time and wear. In SSDs, access times are uniform, so these algorithms have less impact. However, understanding them is key for systems still using HDDs or hybrid storage.

Result

Better system responsiveness and longer disk life on HDDs; less benefit on SSDs.

Knowing hardware differences clarifies when these algorithms are useful.

7

Expert

Algorithm Adaptations and Limitations

🤔Before reading on: Can LOOK and C-LOOK handle dynamically arriving requests efficiently? Commit to your answer.

Concept: LOOK and C-LOOK can be adapted for dynamic request arrivals but have limitations with real-time constraints and very high loads.

In practice, these algorithms may be combined with priority scheduling or replaced by more complex methods in high-demand systems. They assume a static queue during a scan, which may not hold true, causing delays or starvation.

Result

Understanding these limits guides system designers to choose or modify algorithms for specific workloads.

Knowing the assumptions and limits prevents misuse and helps design better disk schedulers.

Under the Hood

LOOK and C-LOOK work by maintaining a queue of pending disk requests sorted by track number. The disk head moves in one direction, servicing requests in order until it reaches the furthest request in that direction (LOOK) or the highest request (C-LOOK). In LOOK, the head reverses direction after the last request; in C-LOOK, it jumps back to the lowest request without servicing tracks on the return. This reduces unnecessary head movement compared to scanning the entire disk.

Why designed this way?

These algorithms were designed to improve upon SCAN by avoiding wasted movement to empty tracks, which was inefficient. The jump-back in C-LOOK was introduced to provide more uniform wait times and reduce delays for requests near the start. Alternatives like FCFS were simpler but slower, while SCAN was better but still had inefficiencies. LOOK and C-LOOK balance complexity and performance for mechanical disks.

┌───────────────┐
│ Request Queue │
│ Sorted by    │
│ Track Number │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ Disk Head Movement Control  │
│                             │
│ LOOK: Move to last request  │
│ then reverse direction      │
│                             │
│ C-LOOK: Move forward to     │
│ last request, then jump back│
└─────────────┬───────────────┘
              │
              ▼
      ┌─────────────┐
      │ Disk Tracks │
      │ 0 - 199     │
      └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does LOOK always scan to the disk's physical end? Commit yes or no.

Common Belief: LOOK always moves the disk head to the very end of the disk before reversing.

Reality: LOOK only moves as far as the last request in the current direction, not to the disk's physical end.

Why it matters: Believing LOOK scans to the end can lead to overestimating its efficiency and misunderstanding its advantage over SCAN.

Quick: Does C-LOOK scan backward when returning to the start? Commit yes or no.

Common Belief: C-LOOK scans backward over tracks when returning to the start position.

Reality: C-LOOK jumps back to the start without scanning or servicing requests on the return path.

Why it matters: Thinking C-LOOK scans backward can cause confusion about its efficiency and fairness properties.

Quick: Are LOOK and C-LOOK equally effective on SSDs? Commit yes or no.

Common Belief: LOOK and C-LOOK improve performance equally on all storage devices, including SSDs.

Reality: These algorithms mainly optimize mechanical head movement, which SSDs do not have, so they offer little benefit on SSDs.

Why it matters: Applying these algorithms blindly to SSDs wastes effort and may complicate scheduling unnecessarily.

Quick: Can LOOK and C-LOOK guarantee no starvation? Commit yes or no.

Common Belief: LOOK and C-LOOK always prevent starvation of disk requests.

Reality: Under heavy or skewed loads, some requests may wait a long time or starve, especially if new requests keep arriving ahead of the head.

Why it matters: Assuming no starvation can lead to poor system responsiveness and unfairness in real workloads.

Expert Zone

1

LOOK's efficiency depends heavily on the distribution of requests; clustered requests near the ends reduce its advantage.

2

C-LOOK's jump back is a logical jump, not physical, but in HDDs it still involves moving the head quickly, which can cause delays.

3

In multi-queue or priority systems, LOOK and C-LOOK can be combined with priority scheduling, complicating their behavior and performance.

When NOT to use

LOOK and C-LOOK are less effective or unnecessary for SSDs due to lack of mechanical movement. For real-time systems requiring strict deadlines, priority-based or deadline-aware schedulers are better. Also, in systems with very high request rates and dynamic arrivals, more adaptive algorithms like FSCAN or N-step SCAN may be preferred.

Production Patterns

In production, LOOK and C-LOOK are often used in traditional HDD-based storage systems and embedded devices where mechanical wear and latency matter. They are sometimes combined with request merging and caching to further optimize performance. Modern OS kernels may implement variants or hybrids depending on workload characteristics.

Connections

Elevator Algorithm

LOOK and C-LOOK are variants of the Elevator algorithm used in disk scheduling.

Understanding the Elevator algorithm helps grasp how LOOK and C-LOOK improve head movement by limiting unnecessary travel.

Real-Time Scheduling

Disk scheduling algorithms like LOOK and C-LOOK contrast with real-time scheduling which prioritizes deadlines over efficiency.

Knowing the difference clarifies when to prioritize fairness and deadlines versus throughput and efficiency.

Supply Chain Logistics

LOOK and C-LOOK resemble routing strategies in logistics where delivery routes are optimized to minimize travel distance.

Recognizing this connection shows how optimization principles apply across computing and physical delivery systems.

Common Pitfalls

#1 Assuming LOOK always scans to disk end causing unnecessary delays.

Wrong approach:

Implementing LOOK to always move head to track 0 or max track before reversing, regardless of requests.

Correct approach:

Implement LOOK to move head only as far as the last request in the current direction before reversing.

Root cause:

Misunderstanding the difference between SCAN and LOOK algorithms.

#2 Treating C-LOOK as scanning backward on return path.

Wrong approach:

Programming C-LOOK to service requests while moving back to the start track.

Correct approach:

Program C-LOOK to jump back to the lowest request without servicing during return.

Root cause:

Confusing C-LOOK with LOOK or SCAN behavior.

#3 Applying LOOK/C-LOOK scheduling to SSDs expecting performance gains.

Wrong approach:

Using LOOK or C-LOOK algorithms in SSD-based systems without considering hardware differences.

Correct approach:

Use simpler or different scheduling methods for SSDs since head movement is not a factor.

Root cause:

Not accounting for hardware characteristics in algorithm choice.

Key Takeaways

LOOK and C-LOOK are disk scheduling algorithms that reduce disk head movement by only traveling as far as needed to service requests.

LOOK moves the head back and forth between the furthest requests, while C-LOOK moves in one direction and jumps back to the start.

These algorithms improve performance on mechanical hard drives by minimizing wasted movement and balancing wait times.

They are less relevant for SSDs, which have no mechanical head movement, and have limitations under dynamic or real-time workloads.

Understanding their design and trade-offs helps in choosing the right disk scheduling method for different storage systems.

Practice

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

easy

A. LOOK moves only in one direction, while C-LOOK moves back and forth.

B. LOOK uses a queue, while C-LOOK uses a stack.

C. LOOK schedules requests randomly, while C-LOOK schedules them sequentially.

D. LOOK moves the disk head back and forth, while C-LOOK moves in one direction and jumps back.

Solution

1. Step 1: Understand LOOK algorithm movement

   LOOK moves the disk head back and forth servicing requests only as far as needed in each direction.

2. Step 2: Understand C-LOOK algorithm movement

   C-LOOK moves the disk head in one direction only and jumps back to the start without servicing requests on the return.

3. Final Answer:

   LOOK moves the disk head back and forth, while C-LOOK moves in one direction and jumps back. -> Option D

4. Quick Check:

   LOOK vs C-LOOK movement = back/forth vs one-way jump [OK]

Hint: LOOK moves back/forth; C-LOOK jumps back after one-way move [OK]

Common Mistakes:

• Confusing direction of head movement
• Thinking C-LOOK moves back and forth
• Mixing up scheduling order

2. Which of the following is the correct way to describe the C-LOOK algorithm's disk head movement?

easy

A. The head moves back and forth servicing all requests.

B. The head moves in one direction and then jumps back to the first request.

C. The head moves randomly to service requests.

D. The head moves in a circular queue servicing requests in order.

Solution

1. Step 1: Identify C-LOOK movement pattern

   C-LOOK moves the disk head in one direction only, servicing requests along the way.

2. Step 2: Understand jump back behavior

   After reaching the last request in that direction, the head jumps back to the first request without servicing on the return.

3. Final Answer:

   The head moves in one direction and then jumps back to the first request. -> Option B

4. Quick Check:

   C-LOOK = one-way move + jump back [OK]

Hint: C-LOOK moves one way, then jumps back to start [OK]

Common Mistakes:

• Assuming head moves back and forth
• Confusing C-LOOK with LOOK
• Thinking head services requests on return jump

3. Given the disk requests at positions [10, 22, 20, 2, 40, 6] and the disk head starting at position 15 moving towards higher numbers, what is the order of servicing requests using the LOOK algorithm?

medium

A. [20, 22, 40, 10, 6, 2]

B. [20, 22, 40, 6, 2, 10]

C. [20, 22, 40, 6, 2]

D. [20, 22, 40, 10, 2, 6]

Solution

1. Step 1: Move head towards higher requests

   Starting at 15, LOOK moves up servicing 20, 22, and 40.

2. Step 2: Reverse direction and service lower requests

   After 40, head moves back down servicing 10, 6, and 2. But LOOK only goes as far as the last request in each direction. Since 10 is before 15, it will be serviced on the return.

3. Step 3: Verify options

   [20, 22, 40, 6, 2] lists only requests serviced in one direction (20, 22, 40) without the return. LOOK services both directions, so [20, 22, 40, 6, 2] is incomplete. [20, 22, 40, 10, 6, 2] includes 10, 6, 2 after 40, which matches LOOK behavior.

4. Final Answer:

   [20, 22, 40, 10, 6, 2] -> Option A

5. Quick Check:

   LOOK = up then down servicing all requests [OK]

Hint: LOOK moves up then down servicing requests in both directions [OK]

Common Mistakes:

• Ignoring requests on return path
• Assuming C-LOOK behavior
• Ordering requests incorrectly

4. Identify the error in this description of the C-LOOK algorithm: "The disk head moves from the lowest to the highest request, then moves back servicing requests on the return path."

medium

A. C-LOOK does not move back to service requests; it jumps back without servicing.

B. C-LOOK services requests randomly, not in order.

C. C-LOOK moves back and forth like LOOK, so the description is correct.

D. C-LOOK only services the lowest request and stops.

Solution

1. Step 1: Understand C-LOOK movement

   C-LOOK moves the head in one direction servicing requests from lowest to highest.

2. Step 2: Check return path behavior

   Unlike LOOK, C-LOOK does not service requests on the return jump; it jumps back to the start without servicing.

3. Final Answer:

   C-LOOK does not move back to service requests; it jumps back without servicing. -> Option A

4. Quick Check:

   C-LOOK jump back skips servicing requests [OK]

Hint: C-LOOK jump back skips servicing requests [OK]

Common Mistakes:

• Assuming servicing on return jump
• Confusing C-LOOK with LOOK
• Misunderstanding head movement direction

5. A disk has requests at positions [5, 15, 25, 35, 45] and the head is currently at position 20 moving towards higher numbers. Using the C-LOOK algorithm, what is the total distance the disk head will move to service all requests?

hard

A. 50

B. 40

C. 35

D. 60

Solution

1. Step 1: Service requests moving up from 20

   The head moves from 20 to 25, then 35, then 45. Distance = 45 - 20 = 25.

2. Step 2: Jump back to lowest request and service upwards

   After 45, the head jumps back to 5 (distance = 45 - 5 = 40, but jump is not counted as movement in C-LOOK). Then it services 5 and 15 moving up. Distance from 5 to 15 = 10.

3. Step 3: Calculate total movement

   Total movement = 25 (upwards) + 10 (from 5 to 15) = 35. But jump back is considered instantaneous (no movement counted). So total movement is 25 + 10 = 35.

4. Step 4: Re-examine options

   Total movement of 35 matches 35.

5. Final Answer:

   35 -> Option C

6. Quick Check:

   C-LOOK counts only servicing moves, jump back ignored [OK]

Hint: Count only servicing moves; ignore jump back distance [OK]

Common Mistakes:

• Counting jump back as movement
• Ignoring requests before head position
• Adding distances incorrectly