Thuật toán này là phiên bản ưu tiên của lập lịch SJF . Trong SRTF, quá trình thực thi có thể bị dừng sau một khoảng thời gian nhất định. Khi xuất hiện mọi quy trình, bộ lập lịch ngắn hạn lập lịch cho quy trình với thời gian liên tục còn lại ít nhất trong danh sách các quy trình có sẵn và quy trình đang chạy.
Các bài viết liên quan:
- Lập kế hoạch Shortest Job First (SJF)
- Từng bước xây dựng một Blog thời trang
- Cách tạo lịch biên tập cho tiếp thị nội dung trong 5 bước đơn giản
- Phân tích chuỗi thời gian Python.
- Lập lịch CPU trong Operating System
- Lập lịch FCFS trong Operating System
Khi tất cả các quy trình có sẵn trong hàng đợi sẵn sàng , Sẽ không có quyền ưu tiên nào được thực hiện và thuật toán sẽ hoạt động như lập lịch SJF . Bối cảnh của quy trình được lưu trong Khối điều khiển quy trình khi quy trình bị xóa khỏi quá trình thực thi và quy trình tiếp theo được lên lịch. PCB này được truy cập vào lần thực thi tiếp theo của quá trình này.
Thuật toán Shortest remaining time first là gì?
Shortest remaining time first(srtf) hay có tên gọi khác là Shortest remaining time, là một phương pháp lập lịch là phiên bản ưu tiên của việc lập lịch tiếp theo cho công việc có thời gian ngắn nhất. Trong thuật toán lập lịch trình này, tiến trình có khoảng thời gian nhỏ nhất còn lại cho đến khi hoàn thành được chọn để thực thi trước.
Thí dụ
Trong Ví dụ này, có năm công việc P1, P2, P3, P4, P5 và P6. Arrival Time và Burst Time của chúng được đưa ra dưới đây trong bảng.
| Xử lý ID | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time | Response Time |
| 1 | 0 | số 8 | 20 | 20 | 12 | 0 |
| 2 | 1 | 4 | 10 | 9 | 5 | 1 |
| 3 | 2 | 2 | 4 | 2 | 0 | 2 |
| 4 | 3 | 1 | 5 | 2 | 1 | 4 |
| 5 | 4 | 3 | 13 | 9 | 6 | 10 |
| 6 | 5 | 2 | 7 | 2 | 0 | 5 |
Waiting Time trung bình = 24/6
Biểu đồ Gantt được chuẩn bị theo Arrival Time và Burst Time được cho trong bảng.
- Vì, tại thời điểm 0, quy trình khả dụng duy nhất là P1 với Burst Time CPU là 8. Đây là quy trình khả dụng duy nhất trong danh sách do đó nó được lên lịch.
- Quá trình tiếp theo đến ở đơn vị thời gian 1. Vì thuật toán chúng tôi đang sử dụng là SRTF là thuật toán phủ đầu, quá trình thực thi hiện tại bị dừng và bộ lập lịch kiểm tra quá trình có thời gian liên tục ít nhất.
Cho đến bây giờ, có hai quy trình có sẵn trong hàng đợi sẵn sàng. Hệ điều hành đã thực thi P1 trong một đơn vị Waiting Time đến nay; thời gian nổ còn lại của P1 là 7 đơn vị. Burst Time của Quy trình P2 là 4 đơn vị. Do đó, tiến trình P2 được lập lịch trên CPU theo thuật toán. - Quá trình tiếp theo P3 đến đơn vị thời gian 2. Tại thời điểm này, việc thực hiện quá trình P3 bị dừng và quá trình có Burst Time còn lại ít nhất được tìm kiếm. Vì quá trình P3 có 2 đơn vị Burst Time nên nó sẽ được ưu tiên hơn các đơn vị khác.
- Quy trình tiếp theo P4 đến ở đơn vị thời gian 3. Tại thời điểm này, bộ lập lịch sẽ dừng việc thực thi P4 và kiểm tra xem quy trình nào có Burst Time ít nhất trong số các quy trình có sẵn (P1, P2, P3 và P4). P1 và P2 đang có thời gian nổ còn lại lần lượt là 7 đơn vị và 3 đơn vị.
- P3 và P4 đang có thời gian nổ còn lại mỗi loại 1 đơn vị. Vì cả hai đều bình đẳng nên việc lên lịch sẽ được thực hiện tùy theo Arrival Time của họ. P3 đến sớm hơn P4 và do đó nó sẽ được lên lịch lại.Quy trình Tiếp theo P5 đến ở đơn vị thời gian 4. Cho đến thời điểm này, Quy trình P3 đã hoàn thành việc thực thi và nó không còn trong danh sách. Bộ lập lịch sẽ so sánh Burst Time còn lại của tất cả các quy trình có sẵn. Vì Burst Time của quá trình P4 là 1, ít nhất trong số tất cả các quá trình nên điều này sẽ được lên lịch.
- Quy trình Tiếp theo P6 đến ở đơn vị thời gian 5, cho đến thời điểm này, Quy trình P4 đã hoàn thành việc thực thi. Chúng tôi có 4 quy trình khả dụng cho đến thời điểm này, đó là P1 (7), P2 (3), P5 (3) và P6 (2). Thời gian Burst của P6 là ít nhất trong số tất cả các P6 do đó được lên lịch. Kể từ bây giờ, tất cả các quy trình đều có sẵn, do đó thuật toán bây giờ sẽ hoạt động giống như SJF. P6 sẽ được thực hiện cho đến khi hoàn thành và sau đó quá trình với thời gian còn lại ít nhất sẽ được lên lịch.
Khi tất cả các quy trình đến nơi, Không có quyền ưu tiên nào được thực hiện và thuật toán sẽ hoạt động như SJF.
Xem thêm Kiểm tra lỗ hổng bảo mật Process Timing
Ví dụ về SRTF GATE 2011
Nếu chúng ta nói về thuật toán lập lịch theo quan điểm GATE, chúng thường hỏi những câu hỏi số đơn giản về việc tìm Waiting Time trung bình và Turn Around Time. Hãy thảo luận về câu hỏi được đặt ra trong GATE 2011 trên SRTF.
Q. Cho biết Arrival Time và Burst Time của 3 công việc trong bảng dưới đây. Tính Waiting Time trung bình của hệ thống.
| Xử lý ID | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time |
| 1 | 0 | 9 | 13 | 13 | 4 |
| 2 | 1 | 4 | 5 | 4 | 0 |
| 3 | 2 | 9 | 22 | 20 | 11 |
Có ba công việc P1, P2 và P3. P1 đến đơn vị thời gian 0; nó sẽ được lên lịch trước cho đến khi quá trình tiếp theo đến. P2 đến 1 đơn vị thời gian. Burst Time của nó là 4 đơn vị, ít nhất trong số các công việc trong hàng đợi. Do đó, nó sẽ được lên lịch tiếp theo.
Tại thời điểm 2, P3 sẽ đến với Burst Time 9. Vì Burst Time còn lại của P2 là 3 đơn vị, ít nhất trong số các công việc hiện có. Do đó, bộ xử lý sẽ tiếp tục thực hiện cho đến khi hoàn thành. Bởi vì tất cả các công việc đã đến nên không có quyền ưu tiên nào được thực hiện ngay bây giờ và tất cả các công việc sẽ được thực hiện cho đến khi hoàn thành theo SJF.
Waiting Time trung bình = (4 + 0 + 11) / 3 = 5 đơn vị
Xem thêm Time trong Go
SRTF với các quy trình chứa CPU và IO Time
Cho đến bây giờ, chúng tôi chỉ xem xét các công việc ràng buộc CPU. Tuy nhiên, quá trình có thể cần một số thao tác IO hoặc một số tài nguyên để hoàn thành việc thực thi. Trong Ví dụ này, chúng tôi đang xem xét, các quy trình ràng buộc IO.
Trong ví dụ, có bốn công việc với ID quy trình P1, P2, P3 và P4 có sẵn. Arrival Time và thời gian hoạt động của CPU được đưa ra trong bảng dưới đây.
| Xử lý ID | Arrival Time | (Burst Time, IO Burst Time, Burst Time) |
| 1 | 0 | (3,2,2) |
| 2 | 0 | (1,3,1) |
| 3 | 3 | (3,1,2) |
| 4 | 6 | (5,4,5) |
Xem thêm Kiểm tra lỗ hổng bảo mật Session Timeout
Chuẩn bị biểu đồ GANTT
Tại thời điểm 0, quá trình P1 và P2 đến. Vì thuật toán chúng tôi đang sử dụng là SRTF, do đó, quá trình với Burst Time ngắn nhất sẽ được lập lịch trên CPU. Trong trường hợp này, nó là P2.
Từ thời điểm 0 đến thời điểm 1, P2 sẽ ở trạng thái chạy.
P2 cũng cần một số thời gian IO để hoàn tất quá trình thực thi. Sau 1 đơn vị thực hiện, P2 sẽ chuyển trạng thái từ chạy sang chờ. Bộ xử lý trở nên tự do để thực hiện các công việc khác. Vì Không có quá trình nào khác khả dụng tại thời điểm này ngoài P1 nên P1 sẽ được thực thi.
Sơ đồ sau minh họa các quá trình và trạng thái tại Thời điểm 1. Quá trình P2 chuyển sang trạng thái chờ và CPU trở thành thần tượng tại thời điểm này.
Từ thời điểm 1 đến 3, vì P2 đang ở trạng thái chờ và không có quá trình nào khác trong hàng đợi sẵn sàng, do đó quá trình khả dụng duy nhất P1 sẽ được thực hiện trong khoảng thời gian này.
Tại thời điểm 3, quá trình P3 đến với tổng thời gian nổ của CPU là 5 đơn vị. Vì Burst Time còn lại của P1 ít hơn nên P3 do đó CPU sẽ tiếp tục thực hiện.
Do đó, P1 sẽ vẫn ở trạng thái chạy từ thời điểm 3 đến thời điểm 4.
Vì P1 là một quá trình ràng buộc IO. Tại thời điểm đơn vị 4, nó sẽ thay đổi trạng thái từ đang chạy sang chờ đợi. Bộ xử lý trở nên miễn phí để thực hiện các công việc khác. Vì P2 cũng có sẵn tại thời điểm 4 vì nó đã hoàn thành hoạt động IO và bây giờ nó cần thêm 1 đơn vị Burst Time CPU. P3 cũng có sẵn và yêu cầu tổng thời gian nổ CPU là 5 đơn vị.
Quá trình có thời gian nổ CPU ít nhất còn lại trong số các quá trình có sẵn sẽ được thực thi. Trong trường hợp của chúng tôi, quy trình như vậy là P2 đòi hỏi 1 đơn vị Burst Time do đó nó sẽ được cấp cho CPU.
Tại thời điểm 5, P2 kết thúc. P1 vẫn ở trạng thái chờ. Tại thời điểm này, quy trình khả dụng duy nhất là P3, do đó nó sẽ được cấp cho CPU.
Từ thời điểm 5 đến thời điểm 6, P3 sẽ ở trạng thái chạy; trong khi đó, P1 vẫn sẽ ở trạng thái chờ.
Tại thời điểm 6, Quy trình P4 đến trong hàng đợi sẵn sàng. P1 cũng đã thực hiện với IO và có sẵn để thực thi. P3 vẫn chưa kết thúc và vẫn cần thêm 2 đơn vị thời gian nổ CPU.
Từ thời điểm 6 đến thời điểm 8, thời gian nổ CPU do tái tạo của Quy trình P3 là ít nhất trong số các quy trình có sẵn, do đó P3 sẽ được cấp cho CPU.
P3 cần một số thao tác IO để hoàn tất quá trình thực thi. Tại thời điểm thứ 8, P3 sẽ chuyển trạng thái từ chạy sang chờ. CPU trở nên tự do để thực thi các quá trình khác. Quá trình P4 và P1 có sẵn trong đó, quá trình có Burst Time còn lại ít nhất sẽ được thực thi.
Từ thời điểm 8 đến thời điểm 9, quá trình P1 sẽ được thực thi.
Tại thời điểm 9, IO của quá trình P3 đã kết thúc và bây giờ nó sẽ ở trạng thái sẵn sàng cùng với P4 đã đợi đến lượt ở đó. Để hoàn thành quá trình thực thi, nó cần thêm 2 đơn vị Burst Time. P1 đang ở trạng thái đang chạy tại thời điểm này trong khi không có tiến trình nào ở trạng thái chờ.
từ thời điểm 9 đến 10, quá trình P1 sẽ được thực thi vì Burst Time CPU còn lại của nó ít hơn khi đó các quá trình P4 và P3 có sẵn trong hàng đợi sẵn sàng.
Tại thời điểm 10, quá trình thực thi P1 kết thúc và bây giờ CPU trở thành thần tượng. Quá trình có Burst Time CPU thấp hơn trong số các quá trình sẵn sàng sẽ có lượt CPU.
Từ thời điểm 10 đến 12, quá trình P3 sẽ được thực thi cho đến khi hoàn thành vì thực tế là Burst Time CPU còn lại của nó là giữa hai quá trình có sẵn. Nó cần thêm 2 đơn vị Burst Time CPU, vì Sẽ không có quá trình nào khác ở trạng thái sẵn sàng, do đó Không có quyền ưu tiên nào được thực hiện và nó sẽ được thực hiện cho đến khi hoàn thành.
Tại thời điểm 12, quá trình P3 sẽ hoàn tất, vì chỉ có một quá trình P4 ở trạng thái sẵn sàng do đó P4 sẽ được cấp cho CPU.
P4 cần 5 đơn vị Burst Time CPU trước khi IO, do đó nó sẽ được thực thi cho đến thời điểm 17 (đối với 5 đơn vị) và sau đó nó sẽ thay đổi trạng thái từ đang chạy sang chờ.
Tại thời điểm 17, Quy trình P4 thay đổi trạng thái của nó từ đang chạy sang chờ đợi. Vì đây là quá trình duy nhất trong hệ thống nên CPU sẽ vẫn là thần tượng cho đến khi P4 khả dụng trở lại.
Tại thời điểm 21, P4 sẽ được thực hiện với hoạt động IO và trở nên khả dụng ở trạng thái sẵn sàng.
Từ thời điểm 21, quá trình P4 sẽ được lên lịch. Vì Không có quy trình nào khác ở trong hàng đợi sẵn sàng, do đó bộ xử lý không có bất kỳ sự lựa chọn nào. Nó sẽ được thực hiện cho đến khi hoàn thành.
Biểu đồ Gantt cuối cùng:
| Xử lý ID | Arrival Time | Tổng thời gian hoạt động của CPU | Completion Time | Turn Around Time | Waiting Time |
| 1 | 0 | 5 | 10 | 10 | 5 |
| 2 | 0 | 2 | 5 | 5 | 3 |
| 3 | 3 | 5 | 12 | 9 | 4 |
| 4 | 6 | 10 | 26 | 20 | 10 |
Waiting Time trung bình = (5 + 3 + 4 + 10) / 4 = 22/4 đơn vị
Xem thêm Cách ép xung CPU AMD Ryzen
