Rate this post

Cho đến bây giờ, chúng tôi đã lên lịch các quy trình theo Arrival Time của chúng (trong lập lịch FCFS). Tuy nhiên, thuật toán lập lịch SJF, lập lịch các quá trình theo Burst Time của chúng.

Các bài viết liên quan:

Tóm tắt nội dung

Thuật toán SJF(Shortest Job First)

Shortest Job First (SJF) là một thuật toán lập lịch CPU trong hệ thống máy tính. Thuật toán này sắp xếp các quá trình theo thời gian thực hiện (execution time) từ thấp đến cao và lựa chọn quá trình có thời gian thực hiện ngắn nhất để thực thi trước.

Với SJF, các quá trình mới được đưa vào hàng đợi sẽ được so sánh với các quá trình đang thực thi, và nếu thời gian thực hiện ngắn hơn thì quá trình mới sẽ được thực thi trước. Tuy nhiên, SJF không hoàn toàn công bằng, vì nó có thể dẫn đến tình trạng starvation (quá trình bị đói tài nguyên). Nếu một quá trình có thời gian thực hiện lớn hơn các quá trình khác, nó có thể không được thực thi cho đến khi các quá trình khác đã hoàn thành.

SJF có thể được sử dụng để cải thiện hiệu suất của hệ thống máy tính, đặc biệt là trong các hệ thống có nhiều quá trình có thời gian thực hiện ngắn.

Trong lập lịch SJF, quy trình có Burst Time(thời gian thực thi) thấp nhất, trong số danh sách các tiến trình có sẵn trong hàng đợi sẵn sàng, sẽ được lên lịch tiếp theo.

Tuy nhiên, rất khó dự đoán Burst Time cần thiết cho một quá trình do đó thuật toán này rất khó thực hiện trong hệ thống.

Ưu điểm của SJF

Thông lượng tối đa
Waiting Time và Turn Around trung bình tối thiểu

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

Có thể đau khổ với vấn đề chết đói
Nó không thể thực hiện được vì không thể biết trước thời gian Burst chính xác cho một quá trình.

Có các kỹ thuật khác nhau có sẵn để xác định thời gian nổ CPU của quá trình. Chúng ta sẽ thảo luận chi tiết về chúng sau.

Xem thêm Thuật toán Shortest Remaining Time First (SRTF)

Thí dụ

Trong ví dụ sau, có năm công việc được đặt tên là P1, P2, P3, P4 và P5. Arrival Time và Burst Time của chúng được đưa ra trong bảng dưới đây.

PID	Arrival Time	Burst Time	Completion Time	Turn Around Time	Waiting Time
1	1	7	số 8	7	0
2	3	3	13	10	7
3	6	2	10	4	2
4	7	10	31	24	14
5	9	số 8	21	12	4

Do đó, Không có Quy trình nào đến tại thời điểm 0; sẽ có một vị trí trống trong biểu đồ Gantt từ thời điểm 0 đến 1 (thời điểm mà quá trình đầu tiên đến).

Theo thuật toán, hệ điều hành lập lịch cho quá trình có Burst Time thấp nhất trong số các quá trình có sẵn trong hàng đợi sẵn sàng.

Cho đến nay, chúng ta chỉ có một quá trình trong hàng đợi sẵn sàng, do đó bộ lập lịch sẽ lập lịch trình này cho bộ xử lý bất kể Burst Time của nó là bao nhiêu.

Điều này sẽ được thực hiện cho đến 8 đơn vị thời gian. Cho đến khi chúng tôi có thêm ba quy trình nữa được đưa vào hàng đợi sẵn sàng, do đó bộ lập lịch sẽ chọn quy trình có Burst Time thấp nhất.

Xem thêm Lập lịch Highest Response Ratio Next (HRRN) trong hệ điều hành

Trong số các quy trình được đưa ra trong bảng, P3 sẽ được thực thi tiếp theo vì nó đang có Burst Time thấp nhất trong số tất cả các quy trình có sẵn.

Vì vậy, đó là cách thủ tục sẽ diễn ra trong thuật toán lập lịch trình công việc ngắn nhất (SJF) .

Waiting Time trung bình = 27/5

Dự đoán về Burst Time CPU cho một quá trình trong SJF

Thuật toán SJF là một trong những thuật toán lập lịch tốt nhất vì nó cung cấp thông lượng tối đa và Waiting Time tối thiểu những vấn đề với thuật toán là không thể biết trước Burst Time của CPU.

Chúng tôi có thể ước tính Burst Time của CPU cho một quá trình. Có nhiều kỹ thuật khác nhau có thể được sử dụng để giả định thời gian hoạt động của CPU cho một quá trình. Giả định của chúng tôi cần phải chính xác để sử dụng thuật toán một cách tối ưu.

Có các kỹ thuật sau được sử dụng để giả định thời gian nổ CPU cho một quá trình.

Kỹ thuật tĩnh

Quy trình kích thước

Chúng ta có thể dự đoán Burst Time của quá trình từ kích thước của nó. Nếu chúng ta có hai quy trình T_OLD và T_New và Burst Time thực tế của quy trình cũ là 20 giây và kích thước của quy trình là 20 KB . Chúng tôi biết rằng kích thước của P_NEW là 21 KB . Khi đó, xác suất P_New có Burst Time tương tự là 20 giây là tối đa.

Nếu, P_OLD → 20 KB
P_New → 21 KB
BT (P_OLD) → 20 giây
Sau đó,
BT (P_New) → 20 giây

Do đó, trong kỹ thuật này, chúng tôi thực sự dự đoán Burst Time của một quy trình mới theo Burst Time của một quy trình cũ có kích thước tương tự như quy trình mới.

Xem thêm Kiểm tra lỗ hổng bảo mật Session Timeout

Loại quy trình

Chúng tôi cũng có thể dự đoán Burst Time của quá trình tùy theo loại của nó. Quy trình có thể có nhiều loại khác nhau được định nghĩa như sau.

Quy trình hệ điều hành
Quy trình có thể là một quy trình của hệ điều hành như bộ lập lịch, trình biên dịch, trình quản lý chương trình và nhiều quy trình hệ thống khác. Burst Time của chúng thường thấp hơn, ví dụ, từ 3 đến 5 đơn vị thời gian.Quy trình người dùng
Các quy trình do người dùng khởi xướng được gọi là quy trình người dùng. Có thể có ba loại quy trình như sau.Quy trình tương tác
Các quy trình Tương tác là quy trình tương tác với người dùng theo thời gian hoặc Quá trình thực thi hoàn toàn phụ thuộc vào đầu vào của Người dùng, ví dụ như các trò chơi khác nhau là các quy trình như vậy. Burst Time cần thấp hơn vì chúng không cần CPU trong một khoảng thời gian lớn, chúng chủ yếu phụ thuộc vào tương tác của người dùng với quá trình do đó chúng chủ yếu là các quá trình liên kết IO.Tiến trình tiền cảnh
Các quy trình nền trước là các quy trình được người dùng sử dụng để thực hiện các nhu cầu của họ như MS office, Editors, phần mềm tiện ích, v.v. Các loại quy trình này có Burst Time cao hơn một chút vì chúng là sự kết hợp hoàn hảo giữa các quy trình ràng buộc giữa CPU và IO.Quá trình nền

Các quy trình nền hỗ trợ việc thực thi các quy trình khác. Chúng hoạt động ở chế độ ẩn. Ví dụ, key logger là quá trình ghi lại các phím được nhấn bởi người dùng và các hoạt động của người dùng trên hệ thống. Chúng chủ yếu là các quá trình ràng buộc CPU và cần CPU trong một khoảng thời gian cao hơn.

Xem thêm Priority Scheduling trong Hệ điều hành

Kỹ thuật động

Tính trung bình đơn giản

Trong phép tính trung bình đơn giản, có danh sách n quy trình đã cho P (i) ……. P (n). Gọi T (i) biểu thị Burst Time của quá trình P (i). Gọi τ (n) biểu thị Burst Time dự đoán của quá trình Pth. Sau đó, theo tính toán trung bình đơn giản, Burst Time dự đoán của quá trình n + 1 sẽ được tính là,

τ (n + 1) = (1 / n) ∑ T (i)

Trong đó, 0 <= i <= n và ∑ T (i) là tổng Burst Time thực tế của tất cả các quy trình có sẵn cho đến thời điểm hiện tại.

Trung bình theo cấp số nhân hoặc Lão hóa

Gọi, Tn là Burst Time thực tế của quá trình thứ n.

τ (n + 1) = α. Tn + (1-α). τ (n)

Trong đó, α là độ làm mịn. Giá trị của nó nằm trong khoảng từ 0 đến 1.

Xem thêm Hướng dẫn Hệ điều hành- Operating System( OS)

Operating System

Lập lịch Shortest Job First (SJF)