Giải thuật điều phối Shortest-Job-First Scheduling (SJF)

Tiếp theo các giải thuật định thời  CPU; First-Come, First-Served Scheduling, Round Robin (RR) hôm nay sinhvientot.net gởi đến bạn giải thuật Shortest-Job-First Scheduling.

Một hướng giải quyết khác cho vấn đề điều phối tiến trình CPU là thuật toán shortest-job-first (SJF). Khi CPU được cấp, nó sẽ đưa vào tiến trình có chiều dài burt time nhỏ nhất để xử lý.

Là một dạng độ ưu tiên đặc biệt với độ ưu tiên p_i = thời_gian_còn_lại(Process_i)

Thuật toán shortest-job-first (SJF) Có thể được cài đặt độc quyền hoặc không độc quyền

Minh họa SJF (không độc quyền)

Nếu trong các tiến trình cần nạp vào có 2 tiến trình giống nhau về burst time, nó sẽ áp dụng thuật toán FCFS ta đã nói ở bài trước để giải quyết vấn đề này.Lấy một ví dụ về SJF, ta có bảng các tiến trình cần nạp vào như hình bên dưới, với quy ước các burst time của lần lượt các tiến trình cần nạp vào có đơn vị đồng nhất là milisecond.

Nếu dùng thuật toán SJF để giải quyết bài toán này, chúng ta sẽ có được lược đồ như hình bên dưới, áp dụng giản đồ Gantt để trình bày.

Như vậy, thời gian chờ của P₁ sẽ là 3 (ms), 16 (ms) đối với P₂, 9 (ms) với tiến trình P₃ và 0 (ms) cho P₄. Từ đó, ta tính được thời gian chờ trung bình sẽ là: (3+16+9+0)/4=7 (ms). Hãy thử so sánh, ta sẽ thấy, nếu dùng FCFS để giải quyết vấn đề này, thì ta sẽ tốn tổng cộng 10.25 ms thời gian chờ trung bình.

Thuật toán SJF đã được chứng minh là sẽ cho ra thời gian chờ trung bình cho các tiến trình cần xử lý với một số con tối thiểu nhất. Bằng cách chuyển cách tiến trình ngắn hơn lên trước các tiến trình tốn thời gian dài, nó đã giảm một cách đáng kể thời gian chờ cho các tiến trình ngắn, kéo theo giảm rõ rệt thời gian chờ trung bình.

Vấn đề khó khăn thực sự đối với giải thuật SJF này đó là việc xác định độ dài tiếp theo cần đưa vào để CPU xử lý. Đối với các hệ thống batch, chúng ta có thể sử dụng thời gian xử lý giới hạn do người dùng chỉ định khi người dùng nạp vào một công việc bất kỳ.

Như vậy, trong trường hợp này, người dùng có thể tự tính toán thời gian giới hạn xử lý một cách chính xác, bởi vì với giá trị càng nhỏ thì tốc độ phản hồi xử lý càng nhanh nhưng giá trị này quá nhỏ cũng có thể gây nên tình trạng lỗi thời gian chờ quá hạn dẫn đến yêu cầu xác nhận lại. Do đó mà SJF thường được dùng trong các bài toán cần xử lý dài hạn nhiều hơn.

Với SJF, thuật toán này đồng thời có thể ở trạng thái ưu tiên (preemtive) hoặc không ưu tiên (nonpreemtive).  Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý.

Có nhiều bạn gặp rắc rối với 2 khái niệm vừa nêu ở trên. Ở đây ta cần phân biệt: preemtive (ưu tiên) tức là thuật toán này thuộc dạng không độc quyền. Có ưu tiên thì tính độc quyền không còn. Nhưng với nonpreemtive – không ưu tiên – tức là độc quyền nắm giữ.

Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý.

Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý.

Lấy ví dụ cho vấn đề này, ta có bảng dữ liệu đầu vào như sau:

Giản đồ Gantt thể hiện kết quả của thuật toán SJF với cơ chế ưu tiên (không độc quyền) như sau:

Ta thấy trong hình, P₁ được bắt đầu ở giây thứ 0, và quan sát dữ liệu đầu vào, ta thấy nó đồng thời cũng là tiến trình duy nhất vào đầu tiên. Tiến trình P_­2 tiến vào ở giây thứ 1. Thời gian đợi cho P₁ là 7 ms, lớn hơn nhiều so với P₂ (P₂ chỉ chiếm 4 ms). Suy rộng ra, ta có tổng thời gian chờ cho ví dụ này là [(10-1) + (1-1) + (17-2) + (5-3)]/4=26/4=6.5 ms.

Nhận xét SJF

– Tối ưu thời gian chờ

– Làm sao biết được thời gian còn lại cần thực thi của một tiến trình

– Không khả thi ?
– Ước lượng – sử dụng thời gian sử dụng CPU ngay trước, dùng qui luật trung bình giảm theo hàm mũ.