Trong lĩnh vực quản lý tài nguyên và lập kế hoạch cho các tiến trình trong hệ thống máy tính, giải thuật định thời Shortest Job First (SJF) là một trong những giải thuật quan trọng nhất. SJF tập trung vào việc thực hiện các tiến trình có thời gian thực thi ngắn nhất trước tiên để tối ưu hóa thời gian đáp ứng và hiệu suất hệ thống. Trong bài viết này, chúng ta sẽ tìm hiểu về giải thuật SJF và cách triển khai nó trong mã nguồn.
Giải thuật định thời Shortest Job First (SJF)
Giải thuật SJF dựa trên nguyên tắc sắp xếp các tiến trình theo thời gian thực thi ngắn nhất. Tiến trình có thời gian thực thi ngắn hơn sẽ được ưu tiên thực hiện trước. Cụ thể, quy trình hoạt động của giải thuật SJF bao gồm các bước sau:
Bước 1: Sắp xếp các tiến trình
Ví dụ về danh sách tiến trình:
| Job | Arrival Time | Burst Time |
|---|---|---|
| A | 0 | 6 |
| B | 1 | 8 |
| C | 2 | 7 |
| D | 3 | 3 |
| E | 4 | 10 |
| F | 5 | 5 |
Như vậy, có thể thấy thứ tự thời gian thực hiện các tiến trình theo thứ tự tăng dần là: D->F->A->C->B->E
Bước 2: Thực hiện tiến trình
Bắt đầu thực hiện các tiến trình theo thứ tự đã sắp xếp. Các tiến trình được đưa vào hàng đợi theo arrival time. Ở cùng 1 thời điểm nếu có hơn 1 tiến trình khả dụng thì tiến trình nào có thời gian thực thi ngắn nhất sẽ được thực hiện trước. Trong trường hợp có nhiều tiến trình có cùng thời gian thực thi ngắn nhất, ta có thể sử dụng giải thuật First-Come, First-Served (FCFS) để quyết định thứ tự thực hiện.
Bước 3: Cập nhật thời gian
Khi một tiến trình hoàn thành thực hiện, cập nhật thời gian và tiến trình tiếp theo có thời gian thực thi ngắn nhất sẽ được chọn để thực hiện tiếp.
Cụ thể được mô tả ở bảng sau:
| Time | Job | Note |
|---|---|---|
| 0 | A | Job A là tiến trình đầu tiên khởi chạy |
| 1 | A | Job B vào hàng đợi, nhưng do burst time của B là 8 > burst time còn lại của A là 5 (A đã chạy đc 1 giây) nên sẽ ưu tiên thực hiện A trước |
| 2 | A | Job C vào hàng đợi, nhưng do burst time của C là 7 > burst time còn lại của A là 4 (A đã chạy đc 2 giây) nên sẽ ưu tiên thực hiện A trước |
| 3 | A | Job D vào hàng đợi, tuy burst time của D là 3 = burst time còn lại của A là 3 (A đã chạy đc 3 giây) nhưng A đến trước nên sẽ ưu tiên thực hiện A trước (First come first served) |
| 4 | A | Job E vào hàng đợi, nhưng do burst time của E là 10 > burst time còn lại của A là 2 (A đã chạy đc 4 giây) nên sẽ ưu tiên thực hiện A trước |
| 5 | A | Job F vào hàng đợi, nhưng do burst time của F là 5 > burst time còn lại của A là 1 (A đã chạy đc 5 giây) nên sẽ ưu tiên thực hiện A trước |
| 6 | D | Job A hoàn thành ở giây thứ 6, Trong số các job đang nằm ở hàng đợi (BCDEF) Thì D có burst time ngắn nhất => Thực hiện D |
| 9 | F | Job D hoàn thành ở giây thứ 9, Trong số các job đang nằm ở hàng đợi (BCEF) Thì F có burst time ngắn nhất => Thực hiện F |
| 14 | C | Job F hoàn thành ở giây thứ 14, Trong số các job đang nằm ở hàng đợi (BCE) Thì C có burst time ngắn nhất => Thực hiện C |
| 21 | B | Job C hoàn thành ở giây thứ 21, Trong số các job đang nằm ở hàng đợi (BE) Thì B có burst time ngắn nhất => Thực hiện B |
| 29 | E | Job B hoàn thành ở giây thứ 29, Trong số các job đang nằm ở hàng đợi (E) Thì E có burst time ngắn nhất => Thực hiện E |
| 39 | Hoàn thành |
Kết luận
Giải thuật định thời Shortest Job First (SJF) là một giải thuật quan trọng trong lĩnh vực quản lý tiến trình và tối ưu hóa thời gian đáp ứng hệ thống. Bằng cách ưu tiên các tiến trình có thời gian thực thi ngắn nhất, SJF có thể cải thiện hiệu suất và thời gian đáp ứng của hệ thống. Trên cùng với việc triển khai mã nguồn minh họa, bạn có thể hiểu rõ hơn về cách SJF hoạt động và cách áp dụng nó trong các ứng dụng thực tế.
