Công việc ngắn nhất trước tiên (SJF): Ví dụ ưu tiên, không ưu tiên

Lập kế hoạch đầu tiên cho công việc ngắn nhất là gì?

Công việc ngắn nhất đầu tiên (SJF) là thuật toán trong đó tiến trình có thời gian thực hiện nhỏ nhất sẽ được chọn cho lần thực hiện tiếp theo. Phương pháp lập kế hoạch này có thể được ưu tiên hoặc không được ưu tiên. Nó làm giảm đáng kể thời gian chờ trung bình cho các tiến trình khác đang chờ thực thi. Hình thức đầy đủ của SJF là Công việc ngắn nhất trước tiên.

Về cơ bản có hai loại phương pháp SJF:

SJF không ưu tiên
SJF ưu tiên

Đặc điểm của lập kế hoạch SJF

Nó gắn liền với mỗi công việc như một đơn vị thời gian hoàn thành.
Phương pháp thuật toán này hữu ích cho việc xử lý theo kiểu hàng loạt, trong đó việc chờ đợi công việc hoàn thành là không quan trọng.
Nó có thể cải thiện thông lượng quy trình bằng cách đảm bảo rằng các công việc ngắn hơn được thực hiện trước, do đó có thể có thời gian quay vòng ngắn.
Nó cải thiện sản lượng công việc bằng cách cung cấp các công việc ngắn hơn, cần được thực hiện trước, hầu hết có thời gian quay vòng ngắn hơn.

SJF không ưu tiên

Trong lập lịch không ưu tiên, khi chu trình CPU được phân bổ cho tiến trình, tiến trình sẽ giữ nó cho đến khi đạt đến trạng thái chờ hoặc kết thúc.

Hãy xem xét năm tiến trình sau, mỗi tiến trình có thời gian bùng phát và thời gian đến riêng.

Hàng đợi xử lý	Thời gian bùng nổ	Thời gian đến
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Bước 0) Tại thời điểm = 0, P4 đến và bắt đầu thực thi.

Bước 1) Tại thời điểm = 1, Quá trình P3 đến. Tuy nhiên, P4 vẫn cần 2 đơn vị thực thi để hoàn thành. Nó sẽ tiếp tục thực hiện.

Bước 2) Tại thời điểm =2, tiến trình P1 đến và được thêm vào hàng đợi. P4 sẽ tiếp tục thực hiện.

Bước 3) Tại thời điểm = 3, tiến trình P4 sẽ kết thúc quá trình thực thi của nó. Thời gian nổ của P3 và P1 được so sánh. Quá trình P1 được thực thi vì thời gian bùng nổ của nó ít hơn so với P3.

Bước 4) Tại thời điểm = 4, tiến trình P5 đến và được thêm vào hàng đợi. P1 sẽ tiếp tục thực hiện.

Bước 5) Tại thời điểm = 5, tiến trình P2 đến và được thêm vào hàng đợi. P1 sẽ tiếp tục thực hiện.

Bước 6) Tại thời điểm = 9, tiến trình P1 sẽ kết thúc quá trình thực thi của nó. Thời gian bùng nổ của P3, P5 và P2 được so sánh. Quá trình P2 được thực thi vì thời gian bùng nổ của nó là thấp nhất.

Bước 7) Tại thời điểm = 10, P2 đang thực thi và P3 và P5 đang ở hàng đợi.

Bước 8) Tại thời điểm = 11, tiến trình P2 sẽ kết thúc quá trình thực thi của nó. Thời gian nổ của P3 và P5 được so sánh. Quá trình P5 được thực thi vì thời gian bùng nổ của nó thấp hơn.

Bước 9) Tại thời điểm = 15, tiến trình P5 sẽ kết thúc quá trình thực thi của nó.

Bước 10) Tại thời điểm = 23, tiến trình P3 sẽ kết thúc quá trình thực thi của nó.

Bước 11) Hãy tính thời gian chờ trung bình cho ví dụ trên.

Wait time 
P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14

Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

SJF ưu tiên

Trong Lập kế hoạch SJF ưu tiên, các công việc được đưa vào hàng đợi sẵn sàng khi chúng đến. Một tiến trình có thời gian bùng nổ ngắn nhất sẽ bắt đầu thực thi. Nếu một quy trình có thời gian bùng nổ thậm chí ngắn hơn xuất hiện thì quy trình hiện tại sẽ bị loại bỏ hoặc được ưu tiên thực thi và công việc ngắn hơn sẽ được phân bổ chu kỳ CPU.

Hãy xem xét năm quá trình sau đây:

Hàng đợi xử lý	Thời gian bùng nổ	Thời gian đến
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Bước 0) Tại thời điểm = 0, P4 đến và bắt đầu thực thi.

Hàng đợi xử lý	Thời gian bùng nổ	Thời gian đến
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Bước 1) Tại thời điểm = 1, Quá trình P3 đến. Tuy nhiên, P4 có thời gian nổ ngắn hơn. Nó sẽ tiếp tục thực hiện.

Bước 2) Tại thời điểm = 2, quá trình P1 đến với thời gian bùng nổ = 6. Thời gian bùng nổ lớn hơn P4. Do đó, P4 sẽ tiếp tục thực hiện.

Bước 3) Tại thời điểm = 3, tiến trình P4 sẽ kết thúc quá trình thực thi của nó. Thời gian nổ của P3 và P1 được so sánh. Quá trình P1 được thực thi vì thời gian bùng nổ của nó thấp hơn.

Bước 4) Tại thời điểm = 4, tiến trình P5 sẽ đến. Thời gian bùng nổ của P3, P5 và P1 được so sánh. Quá trình P5 được thực thi vì thời gian bùng nổ của nó là thấp nhất. Quá trình P1 được ưu tiên.

Hàng đợi xử lý	Thời gian bùng nổ	Thời gian đến
P1	Còn lại 5 trên 6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Bước 5) Tại thời điểm = 5, tiến trình P2 sẽ đến. Thời gian bùng nổ của P1, P2, P3 và P5 được so sánh. Quá trình P2 được thực thi vì thời gian bùng nổ của nó là ít nhất. Quá trình P5 được ưu tiên.

Hàng đợi xử lý	Thời gian bùng nổ	Thời gian đến
P1	Còn lại 5 trên 6	2
P2	2	5
P3	8	1
P4	3	0
P5	Còn lại 3 trên 4	4

Bước 6) Tại thời điểm =6, P2 đang thực thi.

Bước 7) Tại thời điểm =7, P2 kết thúc việc thực hiện. Thời gian bùng nổ của P1, P3 và P5 được so sánh. Quá trình P5 được thực thi vì thời gian bùng nổ của nó ngắn hơn.

Hàng đợi xử lý	Thời gian bùng nổ	Thời gian đến
P1	Còn lại 5 trên 6	2
P2	2	5
P3	8	1
P4	3	0
P5	Còn lại 3 trên 4	4

Bước 8) Tại thời điểm =10, P5 sẽ kết thúc việc thực thi. Thời gian nổ của P1 và P3 được so sánh. Quá trình P1 được thực thi vì thời gian bùng nổ của nó ngắn hơn.

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

Bước 10) Tại thời điểm =23, P3 kết thúc việc thực thi.

Bước 11) Hãy tính thời gian chờ trung bình cho ví dụ trên.

Wait time 
P4= 0-0=0
P1=  (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14

Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

Ưu điểm của SJF

Dưới đây là những lợi ích/ưu điểm của việc sử dụng phương pháp SJF:

SJF thường được sử dụng để lập kế hoạch dài hạn.
Nó làm giảm thời gian chờ đợi trung bình theo thuật toán FIFO (First in First Out).
Phương pháp SJF đưa ra thời gian chờ trung bình thấp nhất cho một tập hợp quy trình cụ thể.
Nó phù hợp cho các công việc chạy theo đợt, trong đó thời gian chạy được biết trước.
Đối với hệ thống lập kế hoạch dài hạn theo đợt, có thể lấy được ước tính thời gian bùng nổ từ bản mô tả công việc.
Đối với Lập kế hoạch ngắn hạn, chúng ta cần dự đoán giá trị của thời gian bùng nổ tiếp theo.
Có lẽ là tối ưu về thời gian quay vòng trung bình.

Nhược điểm/Nhược điểm của SJF

Dưới đây là một số nhược điểm/nhược điểm của thuật toán SJF:

Thời gian hoàn thành công việc phải được biết trước nhưng khó có thể đoán trước được.
Nó thường được sử dụng trong hệ thống hàng loạt để lập kế hoạch dài hạn.
SJF không thể được thực hiện cho lập lịch CPU trong thời gian ngắn. Đó là vì không có phương pháp cụ thể nào để dự đoán độ dài của đợt bùng nổ CPU sắp tới.
Thuật toán này có thể gây ra thời gian quay vòng rất dài hoặc bị chết đói.
Yêu cầu kiến thức về thời gian một quy trình hoặc công việc sẽ chạy.
Nó dẫn đến tình trạng đói không làm giảm thời gian quay vòng trung bình.
Thật khó để biết độ dài của yêu cầu CPU sắp tới.
Thời gian đã trôi qua phải được ghi lại, điều này sẽ gây ra nhiều chi phí hơn cho bộ xử lý.

Tổng kết

SJF là thuật toán trong đó tiến trình có thời gian thực hiện nhỏ nhất sẽ được chọn cho lần thực hiện tiếp theo.
Lập kế hoạch SJF được liên kết với mỗi công việc như một đơn vị thời gian để hoàn thành.
Phương pháp thuật toán này hữu ích cho việc xử lý theo kiểu hàng loạt, trong đó việc chờ đợi công việc hoàn thành là không quan trọng.
Về cơ bản có hai loại phương pháp SJF 1) SJF không ưu tiên và 2) SJF ưu tiên.
Trong lập lịch không ưu tiên, khi chu trình CPU được phân bổ cho tiến trình, tiến trình sẽ giữ nó cho đến khi đạt đến trạng thái chờ hoặc kết thúc.
Trong Lập kế hoạch SJF ưu tiên, các công việc được đưa vào hàng đợi sẵn sàng khi chúng đến.
Mặc dù một quy trình có thời gian bùng nổ ngắn bắt đầu, nhưng quy trình hiện tại sẽ bị loại bỏ hoặc được ưu tiên thực thi và công việc nào ngắn hơn sẽ được thực hiện trước tiên.
SJF thường được sử dụng để lập kế hoạch dài hạn.
Nó làm giảm thời gian chờ đợi trung bình theo thuật toán FIFO (First in First Out).
Trong lập lịch SJF, thời gian hoàn thành công việc phải được biết trước nhưng rất khó dự đoán.
Không thể triển khai SJF để lập lịch CPU trong thời gian ngắn. Đó là vì không có phương pháp cụ thể nào để dự đoán độ dài của đợt CPU sắp tới.