Thuật toán SCAN & LOOK – “thuật toán thang máy” trong OS & thực tế

Đây cũng chính là trực giác cốt lõi của hai thuật toán rất nổi tiếng trong hệ điều hành khi điều khiển đầu đọc ổ cứng:

• SCAN – hay còn gọi là Elevator Algorithm.
• LOOK – phiên bản “thông minh hơn” của SCAN.

Cả hai đều có thể hiểu như thuật toán thang máy, và ứng dụng được cho cả việc điều khiển thang thật lẫn tối ưu hoá vị trí đầu đọc đĩa.

1. Ôn lại bối cảnh: ta đang giải bài toán gì?

Giả sử ta có một thang máy (hoặc đầu đọc ổ cứng) và một trục tuyến tính các vị trí:

• Thang máy: tầng 0 → tầng 9 (10 tầng).
• Ổ cứng: track 0 → track N.

Hệ thống nhận liên tục các request:

• “Đến tầng 7”, “đến tầng 3”, “đến tầng 9”…

Mục tiêu là sắp xếp thứ tự phục vụ sao cho:

• Giảm tổng quãng đường đi.
• Tránh đảo hướng liên tục.
• Tránh để một số vị trí chờ “cả đời” (starvation).

SCAN & LOOK là hai cách đơn giản nhưng hiệu quả để làm việc này.

2. Thuật toán SCAN – quét từ đáy lên nóc rồi quay lại

SCAN đúng nghĩa là thuật toán “thang máy”:

• Thang chọn một hướng (ví dụ lên).
• Đi một mạch tới tận tầng biên của toà nhà (tầng thấp nhất hoặc cao nhất), kể cả khi không còn request nào phía trước.
• Trên đường đi, nếu gặp tầng có request thì dừng lại để phục vụ.
• Tới biên rồi mới quay đầu, đi ngược lại.

Trực giác: thay vì cứ quay đầu theo request, thang đi “quét” đều toàn bộ trục theo vòng đi – về. Điều này giúp:

• Giảm số lần đổi hướng.
• Giảm nguy cơ một vùng nào đó bị “bỏ quên” rất lâu.

Ví dụ: Toà nhà 10 tầng (0–9), thang ở tầng 2, đang đi lên. Request ở các tầng: 3, 5, 7. Thuật toán SCAN sẽ:

1. Đi từ 2 lên 3 → 4 → 5 → 6 → 7 → 8 → 9.
2. Dù request chỉ đến 7, nó vẫn đi tới tầng 9 (nóc).
3. Sau khi đến 9, mới quay đầu đi xuống 8 → 7 → … → 0.

Điều quan trọng: biên (0 và 9) là “cứng”, không phụ thuộc vào vị trí request.

3. Thuật toán LOOK – chỉ đi tới request xa nhất theo hướng hiện tại

LOOK là phiên bản “tiết kiệm” hơn của SCAN:

• Thang vẫn chọn một hướng và đi quét.
• Nhưng chỉ đi đến request xa nhất theo hướng đó, không nhất thiết đến tầng biên toà nhà.
• Khi không còn request nào phía trước, nó đổi hướng ngay lập tức.

Trở lại ví dụ trên:

• Thang từ tầng 2 đang đi lên, request: 3, 5, 7.
• LOOK sẽ đi 2 → 3 → 4 → 5 → 6 → 7 rồi quay đầu tại 7.
• Không cần lên tận 9 nếu không ai cần.

Như vậy:

Thuật toán Up/Down ở bài 1 thực ra rất gần với LOOK: thang chỉ đổi hướng khi không còn request theo hướng hiện tại.

4. Khi nào dùng SCAN, khi nào dùng LOOK?

• SCAN:
  • Phù hợp khi ta muốn “quét” đều toàn bộ trục (vd: đầu đọc ổ cứng, robot quét kho).
  • Dễ tính toán, ít đổi hướng, predictable.
• LOOK:
  • Giảm quãng đường “thừa” vì không ép đi đến biên.
  • Thực tế nhiều hệ thống thang/disk hiện đại dùng biến thể kiểu LOOK.

5. Demo SCAN & LOOK – so sánh trực quan

Demo dưới đây cho phép bạn:

• Chọn SCAN hoặc LOOK.
• Thêm request tại các tầng.
• Cho thang chạy từng bước hoặc tự động.
• Quan sát cách thang đổi hướng và tầng nó ghé.

Giải thích nhanh demo SCAN & LOOK

• Số tầng: 10 tầng, đánh số từ 0 (dưới cùng) đến 9 (trên cùng).
• Trạng thái thang máy:
  • elevatorFloor: tầng hiện tại.
  • direction: +1 là UP, -1 là DOWN.
• Danh sách request: mảng requests, mỗi phần tử là một số nguyên floor – tầng cần ghé.
• SCAN:
  • Nếu đang lên: luôn tăng tầng +1 cho đến khi gặp tầng trên cùng (9), bất kể phía trên còn request hay không.
  • Chỉ khi chạm tầng 9 mới đổi hướng xuống; tương tự, đi xuống tới tầng 0 rồi mới quay đầu.
• LOOK:
  • Nếu đang lên: chỉ đi lên nếu còn request ở phía trên.
  • Nếu không còn request nào phía trên nhưng còn phía dưới → đổi hướng xuống ngay (không bắt buộc lên tới tầng 9).
  • Tương tự cho chiều xuống.
• Vẽ:
  • Mỗi tầng là một đường ngang + label “Tầng i” bên trái.
  • Cabin thang là một hình chữ nhật màu xanh, di chuyển dọc theo trục.
  • Request chưa phục vụ được vẽ bằng chấm màu cam ở cạnh phải trục.