Rate this post

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:

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.

Thí dụ

Trong Ví dụ này, có năm công việc P1, P2, P3, P4, P5 và P6. Thời gian đến và thời gian bùng nổ của chúng được đưa ra dưới đây trong bảng.

Xử lý IDThời gian đếnThời gian bùng nổThời gian hoàn thànhThời gian quay vòngThời gian chờThời gian đáp ứng
10số 82020120
21410951
3224202
4315214
543139610
6527205

                    Thời gian chờ trung bình = 24/6

Biểu đồ Gantt được chuẩn bị theo thời gian đến và thời gian bùng nổ được cho trong bảng.

  1. Vì, tại thời điểm 0, quy trình khả dụng duy nhất là P1 với thời gian bùng nổ 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.
  2. 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ị thời gian cho đến nay; thời gian nổ còn lại của P1 là 7 đơn vị. Thời gian bùng nổ 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.
  3. 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ó thời gian bùng nổ còn lại ít nhất được tìm kiếm. Vì quá trình P3 có 2 đơn vị thời gian bùng nổ nên nó sẽ được ưu tiên hơn các đơn vị khác.
  4. 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ó thời gian bùng nổ í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ị.
  5. 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 thời gian đến 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 thời gian bùng nổ còn lại của tất cả các quy trình có sẵn. Vì thời gian bùng nổ 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.
  6. 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 thời gian chờ trung bình và Thời gian quay vòng. Hãy thảo luận về câu hỏi được đặt ra trong GATE 2011 trên SRTF.

Q. Cho biết thời gian đến và thời gian bùng nổ của 3 công việc trong bảng dưới đây. Tính Thời gian chờ trung bình của hệ thống.

Xử lý IDThời gian đếnThời gian bùng nổThời gian hoàn thànhThời gian quay vòngThời gian chờ
10913134
214540
329222011

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. Thời gian bùng nổ 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 thời gian bùng nổ 9. Vì thời gian bùng nổ 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.

                    Thời gian chờ trung bình = (4 + 0 + 11) / 3 = 5 đơn vị

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. Thời gian đến và thời gian hoạt động của CPU được đưa ra trong bảng dưới đây.

Xử lý IDThời gian đến(Burst Time, IO Burst Time, Burst Time)
10(3,2,2)
20(1,3,1)
33(3,1,2)
46(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 thời gian bùng nổ 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ì thời gian bùng nổ 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ị thời gian bùng nổ 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ị thời gian bùng nổ 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ó thời gian bùng nổ 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ị thời gian bùng nổ. 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ì thời gian bùng nổ 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ó thời gian bùng nổ 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à thời gian bùng nổ 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ị thời gian bùng nổ 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ị thời gian bùng nổ 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ý IDThời gian đếnTổng thời gian hoạt động của CPUThời gian hoàn thànhThời gian quay vòngThời gian chờ
10510105
202553
3351294
4610262010

              Thời gian chờ trung bình = (5 + 3 + 4 + 10) / 4 = 22/4 đơn vị

Leave a Reply

Call now
%d bloggers like this: