Thuật toán lập lịch ưu tiên: Có quyền ưu tiên, không có quyền ưu tiên

Lập kế hoạch ưu tiên là gì?

Lên lịch ưu tiên là một phương pháp lập lịch trình dựa trên mức độ ưu tiên. Trong thuật toán này, bộ lập lịch sẽ chọn các tác vụ để làm việc theo mức độ ưu tiên.

Các quy trình có mức độ ưu tiên cao hơn nên được thực hiện trước, trong khi các công việc có mức độ ưu tiên ngang nhau được thực hiện theo vòng tròn hoặc FCFS. Mức độ ưu tiên phụ thuộc vào yêu cầu bộ nhớ, yêu cầu thời gian, v.v.

Các loại lập kế hoạch ưu tiên

Lập lịch ưu tiên được chia thành hai loại chính:

Lập lịch trước

Trong Lập kế hoạch ưu tiên, các nhiệm vụ hầu hết được giao với mức độ ưu tiên của chúng. Đôi khi điều quan trọng là phải chạy một tác vụ có mức độ ưu tiên cao hơn trước một tác vụ có mức độ ưu tiên thấp hơn khác, ngay cả khi tác vụ có mức độ ưu tiên thấp hơn vẫn đang chạy. Nhiệm vụ có mức độ ưu tiên thấp hơn sẽ được giữ trong một thời gian và tiếp tục lại khi nhiệm vụ có mức độ ưu tiên cao hơn hoàn thành việc thực thi.

Lập kế hoạch không ưu tiên

Trong phương pháp lập lịch này, CPU được phân bổ cho một tiến trình cụ thể. Tiến trình nào chiếm dụng CPU sẽ giải phóng CPU bằng cách chuyển đổi ngữ cảnh hoặc kết thúc. Đây là phương pháp duy nhất có thể được sử dụng cho nhiều nền tảng phần cứng khác nhau. Đó là vì nó không cần phần cứng đặc biệt (ví dụ: bộ đếm thời gian) như lập lịch ưu tiên.

Đặc điểm của lập kế hoạch ưu tiên

• Một thuật toán CPU lập lịch trình dựa trên mức độ ưu tiên.
• Nó được sử dụng trong Operahệ thống ting để thực hiện các quy trình hàng loạt.
• Nếu hai công việc có cùng mức độ ưu tiên là SẴN SÀNG, nó sẽ hoạt động trên một ĐẾN TRƯỚC, ĐƯỢC PHỤC VỤ TRƯỚC cơ sở.
• Trong lập lịch ưu tiên, một số được gán cho mỗi quy trình cho biết mức độ ưu tiên của nó.
• Số càng thấp thì mức độ ưu tiên càng cao.
• Trong loại thuật toán lập lịch này, nếu một tiến trình mới xuất hiện có độ ưu tiên cao hơn tiến trình đang chạy hiện tại, thì tiến trình đang chạy hiện tại sẽ bị tạm dừng.

Ví dụ về lập kế hoạch ưu tiên

Hãy xem xét năm tiến trình sau từ P1 đến P5. Mỗi tiến trình có mức độ ưu tiên, thời gian thực thi và thời gian đến riêng biệt.

Quy trình	Ưu tiên	Thời gian bùng nổ	Thời gian đến
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Bước 0) Tại thời điểm t = 0, Tiến trình P1 và P2 xuất hiện. P1 có độ ưu tiên cao hơn P2. Quá trình thực thi bắt đầu với tiến trình P1, có thời gian thực thi là 4.

Bước 1) Tại thời điểm t = 1, không có tiến trình mới nào đến. Quá trình thực thi tiếp tục với P1.

Bước 2) Tại thời điểm 2, không có tiến trình mới nào xuất hiện nên bạn có thể tiếp tục với P1. P2 đang trong hàng chờ.

Bước 3) Tại thời điểm 3, không có tiến trình mới nào đến, vì vậy bạn có thể tiếp tục với P1. Tiến trình P2 vẫn đang trong hàng chờ.

Bước 4) Tại thời điểm thứ 4, P1 đã thực hiện xong. P2 bắt đầu thực thi.

Bước 5) Tại thời điểm t = 5, không có tiến trình mới nào đến, vì vậy chúng ta tiếp tục với P2.

Bước 6) Tại thời điểm t = 6, P3 đến. P3 có độ ưu tiên cao hơn (1) so với P2 có độ ưu tiên (2). P2 bị gián đoạn và P3 bắt đầu thực thi.

Quy trình	Ưu tiên	Thời gian bùng nổ	Thời gian đến
P1	1	4	0
P2	2	1 trên 3 đang chờ xử lý	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Bước 7) Tại thời điểm 7, không có tiến trình mới nào đến, vì vậy chúng ta tiếp tục với P3. P2 đang trong hàng chờ.

Bước 8) Tại thời điểm t = 8, không có tiến trình mới nào đến, vì vậy chúng ta có thể tiếp tục với P3.

Bước 9) Tại thời điểm t = 9, không có tiến trình mới nào xuất hiện, vì vậy chúng ta có thể tiếp tục với P3.

Bước 10) Ở khoảng thời gian 10, không có tiến trình mới nào xuất hiện, vì vậy chúng ta tiếp tục với P3.

Bước 11) Tại thời điểm t = 11, P4 đến với độ ưu tiên 4. P3 có độ ưu tiên cao hơn nên nó tiếp tục thực thi.

Quy trình	Ưu tiên	Thời gian bùng nổ	Thời gian đến
P1	1	4	0
P2	2	1 trên 3 đang chờ xử lý	0
P3	1	2 trên 7 đang chờ xử lý	6
P4	3	4	11
P5	2	2	12

Bước 12) Tại thời điểm t = 12, P5 đến. P3 có độ ưu tiên cao hơn nên nó tiếp tục thực thi.

Bước 13) Tại thời điểm t = 13, P3 hoàn thành quá trình thực thi. Ta có P2, P4, P5 trong hàng đợi sẵn sàng. P2 và P5 có cùng độ ưu tiên. Thời gian đến của P2 trước P5, vì vậy P2 bắt đầu thực thi.

Quy trình	Ưu tiên	Thời gian bùng nổ	Thời gian đến
P1	1	4	0
P2	2	1 trên 3 đang chờ xử lý	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

Bước 14) Tại thời điểm t = 14, tiến trình P2 đã hoàn thành quá trình thực thi. P4 và P5 đang ở trạng thái chờ. P5 có độ ưu tiên cao nhất và bắt đầu thực thi.

Bước 15) Tại thời điểm t = 15, P5 tiếp tục thực thi.

Bước 16) Tại thời điểm t = 16, tiến trình P5 đã hoàn thành quá trình thực thi. Chỉ còn lại tiến trình P4. Nó bắt đầu thực thi.

Bước 17) Tại thời điểm t = 20, tiến trình P4 đã hoàn tất quá trình thực thi và không còn tiến trình nào hoạt động nữa.

Bước 18) Chúng ta hãy tính thời gian chờ trung bình cho ví dụ trên.

Thời gian chờ = thời gian bắt đầu – thời gian đến + thời gian chờ cho đợt tiếp theo

P1 = 0 - 0 = 0
P2 = 4 - 0 + 7 = 11
P3 = 6 - 6 = 0
P4 = 16 - 11 = 5
Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6

Ưu điểm của lập lịch ưu tiên

Dưới đây là những lợi ích/ưu điểm của phương pháp lập lịch ưu tiên:

• Phương pháp lập lịch dễ sử dụng.
• Các tiến trình được thực thi dựa trên mức độ ưu tiên, do đó các tiến trình có mức độ ưu tiên cao không cần phải chờ lâu, giúp tiết kiệm thời gian.
• Phương pháp này cung cấp một cơ chế tốt, trong đó tầm quan trọng tương đối của mỗi quy trình có thể được xác định một cách chính xác.
• Thích hợp cho các ứng dụng có yêu cầu về thời gian và tài nguyên biến động.

Nhược điểm của lập lịch ưu tiên

Dưới đây là những nhược điểm/hạn chế của việc lập lịch ưu tiên:

• Nếu cuối cùng hệ thống gặp sự cố, tất cả các quy trình có mức độ ưu tiên thấp sẽ bị mất.
• Nếu các tiến trình có mức ưu tiên cao chiếm nhiều thời gian của CPU thì các tiến trình có mức ưu tiên thấp hơn có thể bị ngừng hoạt động và bị trì hoãn trong một thời gian không xác định.
• Thuật toán lập lịch này có thể khiến một số quy trình có mức độ ưu tiên thấp phải chờ đợi vô thời hạn.
• Một tiến trình sẽ bị chặn khi nó sẵn sàng chạy nhưng phải đợi CPU vì một số tiến trình khác hiện đang chạy.
• Nếu một quy trình mới có mức độ ưu tiên cao hơn tiếp tục xuất hiện trong hàng đợi sẵn sàng thì quy trình đang ở trạng thái chờ có thể phải chờ trong một khoảng thời gian dài.

Câu Hỏi Thường Gặp