Shortest job first scheduling là gì?

Lập lịch công việc ngắn nhất trước (shortest job first scheduling) là một thuật toán lập lịch (scheduling algorithm). Trong đó tiến trình (process) có thời gian thực thi (execution time) nhỏ nhất được chọn cho lần thực thi tiếp theo. Phương pháp lập lịch trình này có thể là ưu tiên (preemptive scheduling) hoặc không ưu tiên (non-preemptive scheduling). Nó làm giảm đáng kể thời gian chờ (waiting time) trung bình cho các tiến trình khác đang chờ thực thi.

Lập lịch công việc ngắn nhất trước (shortest job first scheduling) có các đặc điểm sau:

• Nó được gắn với mỗi công việc (job) như một đơn vị thời gian để hoàn thành.
• Phương pháp thuật toán này hữu ích cho quá trình xử lý hàng loạt (batch processing), trong đó việc chờ đợi các công việc hoàn thành là không quan trọng.
• Nó có thể cải thiện thông lượng (throughput) của tiến trình bằng cách đảm bảo rằng các công việc ngắn hơn được thực hiện trước, do đó có thể có thời gian quay vòng (turnaround time) ngắn.

Bên dưới là bảng các tiến trình và thời gian đến, thời gian thực thi:

Thời gian chờ của mỗi tiến trình như sau:

Thời gian chờ trung bình: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25

Về cơ bản có hai loại lập lịch công việc ngắn nhất trước (shortest job first scheduling): lập lịch công việc ngắn nhất trước không ưu tiên (non-preemptive shortest job first scheduling) và lập lịch công việc ngắn nhất trước có ưu tiên (preemptive shortest job first scheduling). Xem thêm hai loại này để hiểu rõ.