0.4 Định thời biểu cpu  (Page 6/17)

Tn+1 = α tn + (1- α) Tn

Công thức này định nghĩa một giá trị trung bình số mũ. Giá trị của tn chứa thông tin mới nhất; Tn lưu lịch sử quá khứ. Tham số α điều khiển trọng số liên quan giữa lịch sử quá khứ và lịch sử gần đây trong việc đoán. Nếu α=0 thì Tn+1=Tn và lịch sử gần đây không có ảnh hưởng (điều kiện hiện hành được đảm bảo là ngắn); nếu α =1 thì Tn+1=tn và chỉ chu kỳ CPU gần nhất có ảnh hưởng (lịch sử được đảm bảo là cũ và không phù hợp). Thông dụng hơn, α=1/2 thì lịch sử gần đây và lịch sử quá khứ có trọng số tương đương. Giá trị khởi đầu T0 có thể được định nghĩa như một hằng số hay như toàn bộ giá trị trung bình hệ thống. Hình IV.2 dưới đây hiển thị giá trị trung bình dạng mũ với α=1/2 và T0=10.

Để hiểu hành vi của giá trị trung bình dạng mũ, chúng ta có thể mở rộng công thức cho Tn+1 bằng cách thay thế Tn để tìm

Tn+1=α tn+(1-α) α tn-1+…+(1-α)j α tn-j+…+(1-α)n - 1T0

Vì cả hai α và (1- α) là nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có trọng số nhỏ hơn số hạng trước đó.

Giải thuật SJF có thể trưng dụng hoặc không trưng dụng CPU. Chọn lựa này phát sinh khi một quá trình mới đến tại hàng đợi sẳn sàng trong khi một quá trình trước đó đang thực thi. Một quá trình mới có thể có chu kỳ CPU tiêp theo ngắn hơn chu kỳ CPU được để lại của quá trình thực thi hiện tại. Giải thuật SJF trưng dụng sẽ trưng dungj CPU của quá trình đang thực thi hiện tại, trong khi giải thuật SJF không trưng dụng sẽ cho phép quá trình đang thực thi kết thúc chu kỳ CPU của nó. Định thời SJF trưng dụng còn được gọi là định thời thời gian còn lại ngắn nhất trước (shortest-remaining-time-first).

Hình IV‑2 Đoán chiều dài của chu kỳ CPU kế tiếp

Thí dụ, xét 4 quá trình sau với chiều dài của thời gian chu kỳ CPU được cho tính bằng mili giây

Nếu các quá trình đi vào hàng đợi sẳn sàng tại những thời điểm và cần thời gian xử lý được hiển thị trong bảng trên thì thời biểu SJF trưng dụng được mô tả trong lưu đồ Gannt như sau:

Quá trình P1 được bắt đầu tại thời điểm 0, vì nó là quá trình duy nhất trong hàng đợi. Quá trình P2 đến tại thời điểm 1. Thời gian còn lại cho P1 (7 mili giây) là lớn hơn thời gian được yêu cầu bởi quá trình P2 (4 mili giây) vì thế quá trình P1 bị trưng dụng CPU và quá trình P2 được định thời biểu. Thời gian chờ đợi trung bình cho thí dụ này là: ((10-1) + (1-1) + (17-2) + (5-3))/4 = 6.5 mili giây. Định thời SJF không trưng dụng cho kết quả thời gian chờ đợi trung bình là 7.75 mili giây.

Định thời theo độ ưu tiên

Giải thuật SJF là trường hợp đặc biệt của giải thuật định thời theo độ ưu tiên (priority-scheduling algorithm). Độ ưu tiên được gán với mỗi quá trình và CPU được cấp phát tới quá trình với độ ưu tiên cao nhất. Quá trình có độ ưu tiên bằng nhau được định thời trong thứ tự FCFS.

Giải thuật SJF là giải thuật ưu tiên đơn giản ở đó độ ưu tiên p là nghịch đảo với chu kỳ CPU được đoán tiếp theo. Chu kỳ CPU lớn hơn có độ ưu tiên thấp hơn và ngược lại.

Bây giờ chúng ta thảo luận định thời có độ ưu tiên cao và thấp. Các độ ưu tiên thường nằm trong dãy số cố định, chẳng hạn 0 tới 7 hay 0 tới 4,095. Tuy nhiên, không có sự thoả thuận chung về 0 là độ ưu tiên thấp nhất hay cao nhất. Một vài hệ thống dùng số thấp để biểu diễn độ ưu tiên thấp; ngược lại các hệ thống khác dùng các số thấp cho độ ưu tiên cao. Sự khác nhau này có thể dẫn đến sự lẫn lộn. Trong giáo trình này chúng ta dùng các số thấp để biểu diễn độ ưu tiên cao.