Quartz 🪬

CPU Scheduling Algorithms

5 min read

First come First Served (FCFS)

Đặc điểm:

  • Sử dụng một hàng đợi FIFO.
  • Tiến trình nào đến trước sẽ được cấp phát CPU trước.
  • Điều phối theo cơ chế non-preemptive.
  • Thường được sử dụng trong các batch systems.

Ưu điểm:

  • Đơn giản, dễ cài đặt.
  • Ưu tiên các tiến trình CPU-bounded.

Nhược điểm:

  • Đôi khi có những tiến trình sử dụng ít CPU nhưng vẫn phải chờ rất lâu (Starvation). Nếu có một tiến trình bị lỗi vòng lặp vô tận thì có thể độc chiếm CPU và hệ thống lúc đó sẽ bị treo.
  • Không thể dùng cho các hệ thống chia sẻ thời gian (Time-Sharing System).

Round-robin (RR)

Đặc điểm:

  • Chỉ cho phép các tiến trình sử dụng CPU trong một khoảng thời gian Q cố định.
  • Hệ thống cung cấp CPU cho các tiến trình theo thứ tự xoay vòng, do đó mỗi tiến trình không phải đợi quá lâu.
  • Sử dụng cơ chế preemptive.
  • Hiệu quả của thuật toán phụ thuộc rất nhiều vào việc xác định Q.

Nếu có 2 tiến trình cùng đến hàng đợi tại một thời điểm thì sẽ xử lý như thế nào?

Trả lời: tiếp tục thực thi tiến trình đang được sử dụng CPU. Cách làm này giúp giảm chi phí chuyển đổi ngữ cảnh.

Ưu điểm:

  • Dễ dàng cài đặt do không phụ thuộc vào thời gian sử dụng CPU của các tiến trình.
  • Giải quyết được tình trạng starvation vì các tiến trình được luân phiên sử dụng CPU.
  • Có response time tốt nhất.
  • Nếu biết trước có N tiến trình ở trong hàng đợi, hệ thống có thể giả định được response time cho một tiến trình bất kỳ là N x Q.
    • Từ thông tin này, hệ điều hành có thể tự điều chỉnh giá trị của Q sao cho tối ưu nhất.
    • Tuy nhiên, cần lưu ý rằng điều này chỉ đúng trong điều kiện lý tưởng của thuật toán và không bị ảnh hưởng bởi các nhân tố khác của hệ thống chẳng hạn như thời gian nhập xuất.

Nhược điểm:

  • Tốn nhiều thời gian để thực hiện context switch.
  • Việc xác định Q sao cho thuật toán hoạt động hiệu quả là không hề đơn giản.
  • Không có sự ưu tiên cho những tác vụ quan trọng.

Priority

Đặc điểm:

  • Mỗi tiến trình sẽ được gán với một số đại diện cho độ ưu tiên. Số càng thấp thì độ ưu tiên càng cao.
  • Độ ưu tiên thường được gán ngầm định dựa vào bộ nhớ hay thời gian mà tiến trình cần sử dụng. Tuy nhiên, độ ưu tiên cũng có thể được gán tường minh bởi người dùng.
  • Sử dụng cả hai cơ chế điều phối là non-preemptive và preemptive.
  • Thường được sử dụng trong các batch systems.

Ưu điểm:

  • Các tác vụ quan trọng được ưu tiên.

Nhược điểm:

  • Những tiến trình có độ ưu tiên thấp có thể gặp phải tình trạng starvation.

Các tiến trình với độ ưu tiên thấp có thể chờ vô hạn.

Giải pháp: tăng độ ưu tiên theo thời gian. Cách làm này được gọi là aging.

Shortest Job First (SJF)

Đặc điểm: dựa trên cả hai cơ chế là non-preemptive và preemptive:

  • Với cơ chế non-preemptive: chọn các tiến trình từ ready list có thời gian sử dụng ngắn nhất. Tiến trình khi được thực thi sẽ không nhường CPU cho bất kỳ các tiến trình nào khác cho dù các tiến trình đó có thời gian sử dụng CPU ít hơn.
  • Với cơ chế preemptive, SJF trở thành SRTF (shortest remaining time first): tiến trình đang được thực thi có thể ưu tiên cho tiến trình có thời gian dùng CPU ngắn nhất được sử dụng trước.

Ưu điểm:

  • Tối ưu được thời gian chờ.
  • Thường được sử dụng cho điều phối dài hạn.

Nhược điểm:

  • Scheduler cần biết được thời gian sử dụng CPU của tiến trình.
  • Có thể kéo dài turnaround time hoặc gây ra starvation.
  • Không thể sử dụng cho điều phối ngắn hạn do không có cách nào biết được thời gian sử dụng CPU của tiến trình.

Multilevel Queue

Hàng đợi của các tiến trình được phân thành hai loại: dành cho các tiến trình foreground và dành cho các tiến trình background. Mỗi hàng đợi sẽ sử dụng một thuật toán điều phối riêng:

  • Foreground dùng RR.
  • Background dùng FCFS.

Cần phải điều phối giữa các hàng đợi với nhau:

  • Theo độ ưu tiên cố định (fixed priority): chẳng hạn như là xử lý các tiến trình foreground trước rồi mới đến các tiến trình background. Có khả năng xảy ra Starvation.
  • Chia thời gian (time slice): mỗi hàng đợi sẽ được cung cấp một khoảng thời gian sử dụng CPU. Ví dụ:
    • Foreground queue dùng 80% thời gian của CPU.
    • Background queue dùng 20% thời gian của CPU.

[CPU Scheduling]]

Resources

Backlinks