Thuật toán thang máy Up/Down cơ bản – nền tảng của mọi hệ điều khiển thang máy

Dù nghe đơn giản nhưng Up/Down là bước khởi đầu để hiểu các thuật toán SCAN, LOOK, Collective Control… Vì vậy, đây là bài đầu tiên trong series.

1. Trực giác: thang máy hoạt động như thế nào?

Giả sử có một thang máy và một danh sách request từ hành khách:

• Người trong cabin bấm tầng 5, 9.
• Người ở tầng 3 bấm gọi thang (lên).
• Người tầng 8 bấm gọi thang (xuống).

Thuật toán Up/Down chia logic thành hai pha:

• Đang đi lên (UP mode)

Thang sẽ:

• Ghé tất cả các tầng ở phía trên so với vị trí hiện tại.
• Chỉ dừng nếu tầng đó có request (từ cabin hoặc gọi từ ngoài).
• Bỏ qua những request ở phía dưới (đợi lúc đi xuống).

• Đổi sang đi xuống (DOWN mode)

Khi không còn request nào phía trên, thang sẽ:

• Đổi hướng và bắt đầu đi xuống.
• Ghé các tầng có request phía dưới.

Nhìn chung:

Khi đang di chuyển theo hướng nào thì xử lý mọi request theo hướng đó trước, rồi mới đổi hướng.

2. Quy tắc quyết định (Decision Rules)

Khi thang đang di chuyển, nó dựa trên ba thông tin:

1. Tầng hiện tại.
2. Hướng hiện tại (Up hoặc Down).
3. Danh sách yêu cầu (bấm trong cabin + gọi ngoài).

Quy tắc khi đang đi lên:

• Nếu có tầng cao hơn đang có request → tiếp tục đi lên.
• Nếu không còn request nào phía trên → đổi hướng xuống.

Quy tắc khi đang đi xuống:

• Nếu có tầng thấp hơn đang có request → tiếp tục đi xuống.
• Nếu không còn request nào phía dưới → đổi hướng lên.

3. Ví dụ minh hoạ Up/Down

Giả sử toà nhà 10 tầng. Vị trí thang hiện tại: tầng 4, đang đi lên. Danh sách request:

• Cabin: 7, 9
• Gọi ngoài: tầng 6 (Up), tầng 2 (Down), tầng 8 (Down)

Bước 1: Đang đi lên

Các request phía trên tầng 4 là:

• 6 (Up)
• 7 (Cabin)
• 8 (Down)
• 9 (Cabin)

Thang sẽ xử lý theo thứ tự 5 → 6 → 7 → 8 → 9 (chỉ dừng tại tầng có request).

Lưu ý thú vị:

Tầng 8 bấm “Down” nhưng thang đang đi lên vẫn ghé để đón, vì nó nằm trên đường đi.

Bước 2: Khi lên đến 9

Không còn request nào phía trên → đổi hướng xuống.

Bước 3: Đi xuống

Các request phía dưới:

• 2 (Down)

Thang đi xuống 8 → 7 → 6 → … → 2 và dừng ở tầng 2 để phục vụ request.

4. Ưu điểm & nhược điểm

Ưu điểm

• Siêu dễ cài đặt.
• Hành vi trực quan, dễ dự đoán.
• Thích hợp cho 1 thang máy, tải trung bình.

Nhược điểm

• Không tối ưu tổng quãng đường.
• Dễ gây chờ lâu cho một số tầng (ví dụ đang lên, có người tầng 3 gọi Down thì phải chờ rất lâu).
• Không xử lý tốt khi request dồn từ nhiều hướng.

Nhược điểm này chính là lý do xuất hiện các thuật toán SCAN và LOOK (bài 2), và Collective Control (bài 3).

5. Logic pseudo-code cho Up/Down

while (true):
    if direction == UP:
        if exists request above currentFloor:
            move to next higher floor
            if request at this floor: serve()
        else:
            direction = DOWN
    else:
        if exists request below currentFloor:
            move to next lower floor
            if request at this floor: serve()
        else:
            direction = UP

6. Khi nào nên dùng Up/Down?

• Toà nhà nhỏ hoặc chỉ có 1 thang.
• Số request không quá nhiều.
• Cần behavior đơn giản, dễ debug.

Trong hệ thống lớn hơn, Up/Down thường là “khối xây dựng” của thuật toán phức tạp hơn.

Demo thuật toán thang máy Up/Down cơ bản

Giải thích nhanh demo Up/Down

• Floors: 10 tầng, đánh số từ 0 (dưới cùng) đến 9 (trên cùng).
• Elevator state:
  • elevatorFloor: tầng hiện tại.
  • direction: +1 là UP, -1 là DOWN.
• Requests: mỗi request là một object { floor, dir }:
  • floor: tầng có người gọi.
  • dir: "up" hoặc "down" (chỉ dùng để vẽ mũi tên; Up/Down cơ bản dừng tại mọi request).
• Logic 1 bước (step):
  • Nếu đang đi lên:
    • Nếu còn request phía trên → đi lên thêm 1 tầng.
    • Nếu không còn request phía trên nhưng còn phía dưới → đổi hướng sang DOWN, đi xuống 1 tầng.
  • Nếu đang đi xuống:
    • Nếu còn request phía dưới → đi xuống thêm 1 tầng.
    • Nếu không còn request phía dưới nhưng còn phía trên → đổi hướng sang UP, đi lên 1 tầng.
  • Sau khi di chuyển, nếu có request ở tầng hiện tại → thang dừng và “serve” (xóa request đó).
• Vẽ:
  • Mỗi tầng là một đường ngang + số tầng bên trái.
  • Cabin thang máy là một hình chữ nhật màu xanh chạy lên/xuống.
  • Request chưa xử lý được vẽ bằng chấm và mũi tên Up/Down bên phải.

Tiếp theo trong series

Bài 2 sẽ đến một thuật toán “nâng cấp” trực tiếp từ Up/Down:

→ SCAN & LOOK – thuật toán thang máy trong ổ cứng HDD

Nó giải quyết phần lớn hạn chế của Up/Down, được dùng trong OS và thực tế rất hiệu quả.