Rate this post

Cho đến bây giờ, chúng tôi đã lên lịch các quy trình theo thời gian đến 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 thời gian bùng nổ của chúng.

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

Trong lập lịch SJF, quy trình có thời gian bùng nổ thấp nhất, trong số danh sách các quy 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 thời gian bùng nổ 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

  1. Thông lượng tối đa
  2. Thời gian chờ và quay vòng trung bình tối thiểu

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

  1. Có thể đau khổ với vấn đề chết đói
  2. 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. Thời gian đến và thời gian bùng nổ của chúng được đưa ra trong bảng dưới đây.

PIDThời gian đếnThời gian bùng nổThời gian hoàn thànhThời gian quay vòngThời gian chờ
117số 870
23313107
3621042
4710312414
59số 821124

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ó thời gian bùng nổ 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ể thời gian bùng nổ 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ó thời gian bùng nổ 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ó thời gian bùng nổ 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) .

         Thời gian chờ trung bình = 27/5

Dự đoán về Thời gian nổ 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à thời gian chờ tối thiểu nhưng vấn đề với thuật toán là không thể biết trước thời gian bùng nổ của CPU.

Chúng tôi có thể ước tính thời gian bùng nổ 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 Thời gian bùng nổ của quá trình từ kích thước của nó. Nếu chúng ta có hai quy trình T_OLDT_New và thời gian bùng nổ 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ó thời gian bùng nổ tương tự là 20 giây là tối đa.

  1. Nếu, P_OLD → 20 KB   
  2. P_New → 21 KB   
  3. BT (P_OLD) → 20 giây  
  4. Sau đó,   
  5. BT (P_New) → 20 giây  

Do đó, trong kỹ thuật này, chúng tôi thực sự dự đoán thời gian bùng nổ của một quy trình mới theo thời gian bùng nổ 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 thời gian bùng nổ 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. Thời gian bùng nổ 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. Thời gian bùng nổ 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ó thời gian bùng nổ 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ị thời gian bùng nổ của quá trình P (i). Gọi τ (n) biểu thị thời gian bùng nổ dự đoán của quá trình Pth. Sau đó, theo tính toán trung bình đơn giản, thời gian bùng nổ dự đoán của quá trình n + 1 sẽ được tính là,

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

Trong đó, 0 <= i <= n và ∑ T (i) là tổng thời gian bùng nổ 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à thời gian bùng nổ thực tế của quá trình thứ n.

  1. τ (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)

Leave a Reply

Call now
%d bloggers like this: