Gang Scheduling — xếp lượt cho các nhóm tiến trình

Gang scheduling: một gang gồm nhiều thread phải chạy đồng thời trên nhiều CPU. Hệ có C CPU. Mỗi gang cần need CPU và chạy liên tục dur đơn vị thời gian. Tại một thời điểm chỉ một gang chiếm CPU (mô hình tuần tự đơn giản).

Thuật toán

1. Sắp các gang theo gid tăng dần (hàng đợi FIFO theo gid).
2. Khởi tạo thời điểm t = 0. Duyệt từng gang:
   • Nếu need > C: gang không thể chạy → đánh dấu REJECT.
   • Ngược lại: gang bắt đầu tại t, chiếm CPU trong dur đơn vị → cập nhật t += dur.
3. In gid và thời điểm bắt đầu (hoặc REJECT), cuối cùng in makespan = tổng thời gian.

Ví dụ

C=4. Gang1 need=2 dur=3 → bắt đầu 0, t=3. Gang2 need=4 dur=2 → bắt đầu 3, t=5. makespan=5.