Thuật toán lập kế hoạch ưu tiên: VÍ DỤ ưu tiên, không ư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 loại phương pháp lập lịch này, CPU đã được phân bổ cho một quy trình cụ thể. Quá trình khiến CPU bận rộn sẽ giải phóng CPU bằng cách chuyển 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 các nền tảng phần cứng khác nhau. Đó là bởi vì nó không cần phần cứng đặc biệt (ví dụ: bộ hẹn giờ) 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ố lượng thấp hơn, mức độ ưu tiên cao hơn.
Trong loại thuật toán lập lịch này, nếu có một quy trình mới hơn có mức độ ưu tiên cao hơn quy trình hiện đang chạy thì quy trình hiện đang chạy sẽ được ưu tiên.

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

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

Quy trình xét duyệt	Ư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 = 0, Quá trình P1 và P2 đến. P1 có mứ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 bùng nổ là 4.

Bước 1) Tại thời điểm = 1, không có tiến trình mới nào đến. Việc 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 thứ 3, 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. Quá 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 = 5, không có tiến trình mới nào xuất hiện nên chúng ta tiếp tục với P2.

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

Quy trình xét duyệt	Ư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 thứ 7, không có tiến trình mới nào xuất hiện nên chúng ta tiếp tục với P3. P2 đang trong hàng đợi.

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

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

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

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

Quy trình xét duyệt	Ư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) Vào thời điểm = 12, P5 đến. P3 có mứ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 = 13, P3 hoàn thành việc thực thi. Chúng ta có P2,P4,P5 trong hàng đợi sẵn sàng. P2 và P5 có mức độ ưu tiên như nhau. Thời gian đến của P2 là trước P5. Vì vậy P2 bắt đầu thực thi.

Quy trình xét duyệt	Ư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 =14, tiến trình P2 đã hoàn tất quá trình thực thi của nó. P4 và P5 đang ở trạng thái chờ. P5 có mức ưu tiên cao nhất và bắt đầu thực thi.

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

Bước 16) Tại thời điểm = 16, P5 kết thúc việc thực thi. P4 là quá trình duy nhất còn lại. Nó bắt đầu thực hiện.

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

Bước 18) 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 = o - o = o
P2 =4 - o + 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 việc sử dụng phương pháp lập kế hoạch ưu tiên:

Phương pháp lập kế hoạch dễ sử dụng
Các tiến trình được thực thi trên cơ sở mức độ ưu tiên nên 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 từng quy trình có thể được xác định 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/nhược điểm của việc lập kế hoạ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.

Tổng kết

Lập lịch ưu tiên là một phương pháp lập lịch cho các quy 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.
Trong Lập kế hoạch ưu tiên ưu tiên, các nhiệm vụ hầu hết được phân công theo mức độ ưu tiên của chúng.
Trong phương pháp lập lịch ưu tiên không ưu tiên, CPU đã được phân bổ cho một quy trình cụ thể.
Các tiến trình được thực thi trên cơ sở mức độ ưu tiên nên mức độ ưu tiên cao không cần phải chờ lâu giúp tiết kiệm thời gian
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.

Bạn có thể thích: