First-Come, First-Served Scheduling
Cho đến nay, thuật toán định thời CPU đơn giản nhất là first-come, first-server (FCFS). Hiểu đơn giản nghĩa của thuật toán này là: đến trước, phục vụ trước. Với giải thuật này, nó ứng dụng chế độ nonpreemptive – tức là một tiến trình sẽ chiếm giữ CPU cho đến khi nào nó trả CPU, thông qua phương thức ngắt hay yêu cầu nhập/xuất xuất hiện.
Vậy phương thức thực hiện của FCFS trong máy tính là gì? Chính là cơ chế hàng đợi FIFO Queue (First In First Out). Để hiểu rõ hơn về Queue, bạn bắt buộc phải học qua Cấu trúc dữ liệu & Giải thuật hoặc có thể tìm đọc về cơ chế này trên các tài liệu có sẵn trên mạng.
Nếu để ý, ta sẽ thấy ngay từ tên gọi thì cả 2 giải thuật này đều có chung ý tưởng với nhau: Anh vào trước, anh được phục vụ trước.
Lấy một ví dụ để dễ hình dung vấn đề: ta có ba tiến trình được tuần tự đưa vào với các tên gọi là P1 P2 P3 và Burst time của chúng lần lượt là 24 3 3. Ta có các dữ liệu đầu vào cụ thể như bảng sau:
| Process | Burst time |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
Như vậy, xuất phát từ bên trái, ta sẽ nạp P1 vào để xử lý. Khởi điểm, mốc thời gian luôn luôn mặc định bằng 0. Vì trong dữ liệu đề bài đưa ra thì P1 chiếm 24ms, tức là một đoạn khá lớn. Sau đó, tiến trình tiếp theo sẽ được đưa vào, với burst time của P2 bằng 3, tức là trên giản đồ Gantt, ta lấy 24 + 3 = 27 ms. Sau khi P2 hoàn thành, nó sẽ đưa tiếp P3 vào, và P3 chiếm 3ms nên trên đây, ta lấy tiếp 27 + 3 = 30. Như vậy, giản đồ đã cung cấp cho ta một cái nhìn trực quan nhằm minh họa cụ thể burst time của lần lượt các tiến trình P1 P2 P3.
Bài toán đến đây coi như hoàn thành bước khó khăn. Việc còn lại chỉ là xác định thời gian đợi của từng tiến trình. Cách xác định cũng không có gì phức tạp. Bạn chỉ việc căn cứ vào con số bên trái của từng tiến trình trong giản đồ bên trên.
Như vậy: thời gian đợi lần lượt của P1 P2 P3 là 0 24 27.
Bước cuối cùng của thuật toán, đó là xác định thời gian đợi trung bình của cả quá trình. Xác định con số cuối cùng này, bạn hãy cộng tất cả thời gian đợi của toàn bộ các tiến trình có được, sau đó chia cho tổng số tiến trình.
Nói thì có vẻ rắc rối, ở ngay trong ví dụ này, ta có thời gian đợi trung bình là: (0 + 24 + 27) / 3 = 17.
Nhưng nếu để ý kỹ, thuật toán FCFS này có một đặc điểm đó là chiếm khá lớn thời gian chờ đợi, nếu các tiến trình vào theo tuần tự thời gian khác nhau mà có độ chênh lệch quá lớn. Cụ thể, nếu có sự sắp xếp hoặc thay đổi lại thứ tự vào lần lượt của chúng, biết đâu ta có thể rút ngắn thời gian chờ đợi hơn chăng?
Hãy thử với thứ tự vào của các tiến trình là P2 P3 P1 xem có sự khác biệt nào ở con số cuối cùng ta cần đến không.
Cũng vẫn bắt đầu giản đồ Gantt bằng con số 0, ta nạp P2 vào trước tiên. P2 chiếm 3ms, sau đó tới P3 chiếm 3ms, cho nên trên giản đồ, ta sẽ kết thúc P3 ở vị trí 6ms. Sau đó, ta nạp tiến trình cuối cùng là P1 vào ở mốc 6ms, do P1 chiếm 24ms nên 6 + 24 sẽ bằng 30. Có thể bạn thấy ngay là tổng burst time không có gì thay đổi, nhưng đừng nóng vội.
Ta xác định được thời gian đợi ở lần này của từng tiến trình P2 P3 P1 sẽ là 0 3 6 (căn cứ vào con số bên trái của từng tiến trình).
Cuối cùng, ta xác định thời gian đợi trung bình: (0 + 3 + 6) / 3 = 3.
Con số đã giảm đi rất nhiều so với ban đầu. Như vậy, với thuật toán FCFS thì thời gian đợi trung bình sẽ không phải lúc nào cũng tối ưu nhất cho ta mà còn tùy thuộc vào thứ tự vào của các tiến trình.
Và do thuật toán FCFS này ứng dụng nonpreemptive, nên nó sẽ đặc biệt phiền hà khi sử dụng trong những hệ thống chia sẻ thời gian. Vì mỗi lần thực hiện, nó yêu cầu toàn quyền sử dụng CPU, và điều này sẽ dễ gây nên sự đổ vỡ cho hệ thống nếu có một người dùng nạp quá nhiều tiến trình mà các tiến trình đó có burst time không hề nhỏ trong phiên sử dụng của mình.
thuongvt@hotmail.com
