Lập lịch trình đầ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à một thuật toán trong đó quá trình có thời gian thực hiện nhỏ nhất được chọn cho lần thực hiện tiếp theo. Phương pháp lập lịch trình này có thể là ưu tiên hoặc không ưu tiên. Nó làm giảm đáng kể thời gian chờ đợi trung bình cho các quy 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 Đầu tiên.
Về cơ bản có hai loại phương pháp SJF:
- SJF không dự phòng
- SJF dự phòng
Trong hướng dẫn Hệ điều hành này, bạn sẽ học:
- Lập lịch trình đầu tiên cho công việc ngắn nhất là gì?
- Đặc điểm của Lập kế hoạch SJF
- SJF không dự phòng
- SJF dự phòng
- Ưu điểm của SJF
- Nhược điểm / Nhược điểm của SJF
Đặ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 quá trình xử lý kiểu hàng loạt, trong đó việc chờ đợi các 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, nê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 dự phòng
Trong lập lịch không ưu tiên, một khi chu kỳ CPU được phân bổ để xử lý, quá trình sẽ giữ nó cho đến khi nó đạt đến trạng thái chờ hoặc kết thúc.
Hãy xem xét năm quy trình sau, mỗi quy trình có thời gian bùng nổ và thời gian đến duy nhất của riêng nó.
| Hàng đợi xử lý | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | số 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 hiện.
Bước 1) Tại thời điểm = 1, Quy 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, quá 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, quá trình P4 sẽ kết thúc quá trình thực thi. Thời gian bùng nổ của P3 và P1 được so sánh. Quá trình P1 được thực hiện vì thời gian liên tục của nó ít hơn so với P3.
Bước 4) Tại thời điểm = 4, quá 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, quá 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, quá trình P1 sẽ kết thúc quá trình thực thi. Thời gian bùng nổ của P3, P5 và P2 được so sánh. Quá trình P2 được thực hiện 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 hiện và P3 và P5 đang ở trong hàng đợi.
Bước 8) Tại thời điểm = 11, quá trình P2 sẽ kết thúc quá trình thực thi. Thời gian nổ của P3 và P5 được so sánh. Quá trình P5 được thực hiện vì thời gian bùng nổ của nó thấp hơn.
Bước 9) Tại thời điểm = 15, quá trình P5 sẽ kết thúc quá trình thực thi.
Bước 10) Tại thời điểm = 23, quá trình P3 sẽ kết thúc quá trình thực thi.
Bước 11) Hãy tính thời gian chờ trung bình cho ví dụ trên.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
SJF dự phòng
Trong Lập lịch SJF Preemptive, các công việc được đưa vào hàng đợi sẵn sàng khi chúng đến. Quá trình có thời gian bùng nổ ngắn nhất bắt đầu thực hiện. Nếu một quy trình có thời gian bùng nổ ngắn hơn đến, quy trình hiện tại sẽ bị xóa hoặc được ưu tiên thực thi và công việc ngắn hơn được phân bổ chu kỳ CPU.
Hãy xem xét năm quy trình sau:
| Hàng đợi xử lý | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | số 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 hiện.
| Hàng đợi xử lý | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Bước 1) Tại thời điểm = 1, Quy 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ổ nhiều hơn quá trình P4. Do đó, P4 sẽ tiếp tục thực thi.
Bước 3) Tại thời điểm = 3, quá trình P4 sẽ kết thúc quá trình thực thi. Thời gian bùng nổ của P3 và P1 được so sánh. Quá trình P1 được thực hiện vì thời gian bùng nổ của nó thấp hơn.
Bước 4) Tại thời điểm = 4, quá 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 hiện 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 | 5 trong số 6 là còn lại | 2 |
| P2 | 2 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Bước 5) Tại thời điểm = 5, quá 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 hiện vì thời gian bùng nổ của nó là ít nhất. Quy trình P5 được ưu tiên.
| Hàng đợi xử lý | Thời gian bùng nổ | Thời gian đến |
| P1 | 5 trong số 6 là còn lại | 2 |
| P2 | 2 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 trong số 4 là còn lại | 4 |
Bước 6) Tại thời điểm = 6, P2 đang thực hiện.
Bước 7) Tại thời điểm = 7, P2 kết thúc quá trình thực hiện. Thời gian bùng nổ của P1, P3 và P5 được so sánh. Quy trình P5 được thực thi vì thời gian liên tục của nó ít hơn.
| Hàng đợi xử lý | Thời gian bùng nổ | Thời gian đến |
| P1 | 5 trong số 6 là còn lại | 2 |
| P2 | 2 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 trong số 4 là còn lại | 4 |
Bước 8) Tại thời điểm = 10, P5 sẽ kết thúc quá trình thực thi. Thời gian bùng nổ của P1 và P3 được so sánh. Quá trình P1 được thực hiện vì thời gian bùng nổ của nó ít hơn.
Bước 9) Tại thời điểm = 15, P1 kết thúc quá trình thực hiện. 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 quá trình thực hiện.
Bước 11) Hãy tính thời gian chờ trung bình cho ví dụ trên.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 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 lịch trình dài hạn.
- Nó làm giảm thời gian chờ trung bình qua 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 các quy trình cụ thể.
- Nó thích hợp cho các công việc chạy theo lô, nơi mà thời gian chạy được biết trước.
- Đối với hệ thống lập lịch dài hạn theo lô, có thể thu được ước tính thời gian liên tục từ mô tả công việc.
- Đối với Lập lị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ố hạn chế / 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 sớm hơn, nhưng khó có thể đoán trước được.
- Nó thường được sử dụng trong một hệ thống hàng loạt để lập lịch trình dài hạn.
- SJF không thể được triển khai cho lập lịch CPU trong thời gian ngắn. Đó là bởi 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 lâu hoặc 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 nạn đó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 nên được ghi lại, điều đó dẫn đến nhiều chi phí hơn trên bộ xử lý.
Tóm lược
- SJF là một thuật toán trong đó quá trình có thời gian thực hiện nhỏ nhất được chọ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 quá trình xử lý kiểu hàng loạt, trong đó việc chờ đợi các 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 dự phòng và 2) SJF dự phòng.
- Trong lập lịch không ưu tiên, một khi chu kỳ CPU được phân bổ để xử lý, quá trình sẽ giữ nó cho đến khi nó đạt đến trạng thái chờ hoặc kết thúc.
- Trong Lập lịch SJF Preemptive, 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, quy trình hiện tại bị xóa hoặc được ưu tiên thực thi và công việc ngắn hơn sẽ được thực hiện đầu tiên.
- SJF thường được sử dụng để lập lịch trình dài hạn.
- Nó làm giảm thời gian chờ trung bình qua thuật toán FIFO (First in First Out).
- Trong lập kế hoạch SJF, thời gian hoàn thành công việc phải được biết sớm hơn, nhưng khó có thể đoán trước được.
- SJF không thể được triển khai cho lập lịch CPU trong thời gian ngắn. Đó là bởi 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.