Các thuật toán lập lịch hệ điều hành

Bộ lập lịch trình lập lịch trình các quá trình khác nhau được gán cho CPU dựa trên các thuật toán lập lịch cụ thể. Có sáu thuật toán lập lịch quy trình phổ biến mà chúng ta sẽ thảo luận trong chương này -

Lên lịch cho người đến trước, người phục vụ trước (FCFS)
Lập lịch trình ngắn nhất-công việc tiếp theo (SJN)
Lên lịch ưu tiên
Thời gian còn lại ngắn nhất
Lên lịch Round Robin (RR)
Lập lịch hàng đợi nhiều cấp độ

Các thuật toán này là non-preemptive or preemptive. Các thuật toán không ưu tiên được thiết kế để một khi một quá trình đi vào trạng thái đang chạy, nó không thể được ưu tiên cho đến khi nó hoàn thành thời gian được phân bổ, trong khi lập lịch ưu tiên dựa trên mức độ ưu tiên trong đó bộ lập lịch có thể đánh trước một quá trình đang chạy có mức độ ưu tiên thấp bất cứ lúc nào khi mức độ ưu tiên cao quy trình đi vào trạng thái sẵn sàng.

Đến trước phục vụ trước (FCFS)

Công việc được thực hiện trên cơ sở ai đến trước, phục vụ trước.
Nó là một thuật toán lập lịch không phủ đầu, ưu tiên trước.
Dễ hiểu và dễ thực hiện.
Việc triển khai nó dựa trên hàng đợi FIFO.
Hiệu suất kém vì thời gian chờ trung bình cao.

Wait time của mỗi quy trình như sau:

Quá trình	Thời gian chờ: Thời gian phục vụ - Thời gian đến
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Thời gian chờ trung bình: (0 + 4 + 6 + 13) / 4 = 5,75

Công việc ngắn nhất tiếp theo (SJN)

Điều này còn được gọi là shortest job first, hoặc SJF
Đây là một thuật toán lập lịch không ưu tiên, ưu tiên trước.
Cách tiếp cận tốt nhất để giảm thiểu thời gian chờ đợi.
Dễ dàng thực hiện trong các hệ thống Batch, nơi đã biết trước thời gian CPU cần thiết.
Không thể thực hiện trong các hệ thống tương tác mà thời gian CPU cần thiết không được biết trước.
Người xử lý nên biết trước quá trình sẽ mất bao nhiêu thời gian.

Đưa ra: Bảng các quy trình, và thời gian đến, thời gian thực hiện

Quá trình	Thời gian đến	Thời gian thực hiện	Thời gian phục vụ
P0	0	5	0
P1	1	3	5
P2	2	số 8	14
P3	3	6	số 8

Waiting time của mỗi quy trình như sau:

Quá trình	Thời gian chờ
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	14 - 2 = 12
P3	8 - 3 = 5

Thời gian chờ trung bình: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25

Lập lịch dựa trên mức độ ưu tiên

Lập lịch ưu tiên là một thuật toán không ưu tiên và là một trong những thuật toán lập lịch phổ biến nhất trong các hệ thống hàng loạt.
Mỗi quy trình được chỉ định một mức độ ưu tiên. Quy trình có mức độ ưu tiên cao nhất sẽ được thực hiện trước và cứ tiếp tục như vậy.
Các quy trình có cùng mức độ ưu tiên được thực hiện trên cơ sở ai đến trước được phục vụ trước.
Mức độ ưu tiên có thể được quyết định dựa trên yêu cầu bộ nhớ, yêu cầu thời gian hoặc bất kỳ yêu cầu tài nguyên nào khác.

Cho trước: Bảng các quy trình và thời gian đến, thời gian thực hiện và mức độ ưu tiên của chúng. Ở đây chúng tôi đang xem xét 1 là mức độ ưu tiên thấp nhất.

Quá trình	Thời gian đến	Thời gian thực hiện	Sự ưu tiên	Thời gian phục vụ
P0	0	5	1	0
P1	1	3	2	11
P2	2	số 8	1	14
P3	3	6	3	5

Waiting time của mỗi quy trình như sau:

Quá trình	Thời gian chờ
P0	0 - 0 = 0
P1	11 - 1 = 10
P2	14 - 2 = 12
P3	5 - 3 = 2

Thời gian chờ trung bình: (0 + 10 + 12 + 2) / 4 = 24/4 = 6

Thời gian còn lại ngắn nhất

Thời gian còn lại ngắn nhất (SRT) là phiên bản ưu tiên của thuật toán SJN.
Bộ xử lý được phân bổ cho công việc gần nhất để hoàn thành nhưng nó có thể được ưu tiên bởi một công việc sẵn sàng mới hơn với thời gian hoàn thành ngắn hơn.
Không thể thực hiện trong các hệ thống tương tác mà thời gian CPU cần thiết không được biết trước.
Nó thường được sử dụng trong môi trường hàng loạt nơi các công việc ngắn cần được ưu tiên.

Lên lịch Round Robin

Round Robin là thuật toán lập lịch trình quy trình phủ đầu.
Mỗi quy trình được cung cấp một thời gian cố định để thực thi, nó được gọi là quantum.
Khi một quá trình được thực thi trong một khoảng thời gian nhất định, nó sẽ được ưu tiên và quá trình khác sẽ thực thi trong một khoảng thời gian nhất định.
Chuyển đổi ngữ cảnh được sử dụng để lưu trạng thái của các quy trình được ưu tiên trước.

Wait time của mỗi quy trình như sau:

Quá trình	Thời gian chờ: Thời gian phục vụ - Thời gian đến
P0	(0 - 0) + (12 - 3) = 9
P1	(3 - 1) = 2
P2	(6 - 2) + (14 - 9) + (20 - 17) = 12
P3	(9 - 3) + (17 - 12) = 11

Thời gian chờ trung bình: (9 + 2 + 12 + 11) / 4 = 8,5

Lập lịch hàng đợi nhiều cấp độ

Hàng đợi nhiều cấp không phải là một thuật toán lập lịch độc lập. Họ sử dụng các thuật toán hiện có khác để nhóm và lên lịch các công việc có đặc điểm chung.

Nhiều hàng đợi được duy trì cho các quy trình có đặc điểm chung.
Mỗi hàng đợi có thể có các thuật toán lập lịch riêng.
Các ưu tiên được chỉ định cho mỗi hàng đợi.

Ví dụ, các công việc ràng buộc CPU có thể được lập lịch trong một hàng đợi và tất cả các công việc liên kết I / O trong một hàng đợi khác. Sau đó, Process Scheduler sẽ luân phiên chọn các công việc từ mỗi hàng đợi và gán chúng cho CPU dựa trên thuật toán được gán cho hàng đợi.