First-Come, First-Served Scheduling hướng tiếp cận khác

0
174

Trong một bài trước viết về thuật toán định thời dành cho CPU, bạn có thể xem lại tại đây, thì trong đó chúng ta chỉ khảo sát với trường hợp đơn giản nhất. Tức là để đơn giản cho người mới tìm hiểu về CPU Scheduling, thì bài toán trong đó đã quy định thời gian nạp vào cho tất cả các tiến trình được đưa vào đều là ở mili-giây thứ 0.

Đối với thuật toán FCFS này, thì cơ chế nó ứng dụng là FIFO (vào trước, anh sẽ được phục vụ trước), theo quy tắc nonpreemptive (độc quyền chiếm hữu CPU, chỉ trao trả khi nào tiến trình xử lý xong hoặc bị block).

Để nhắc lại một xíu, ta xét ví dụ dưới đây. Nếu nạp 3 tiến trình lần lượt P1 -> P2 -> P3 vào để xử lý, cho biết thời gian xử lý của chúng lần lượt là 24 -> 3 -> 3. Ta sẽ có bảng dữ liệu đầu vào như sau:

Tiến trình Thời gian xử lý
P1 24
P2 3
P3 3

Ta để ý trong ví dụ nhắc lại này, thì ta không nói gì đến thời gian vào Ready list, do đó ta mặc định tự hiểu cả 3 tiến trình đều được cho vào xử lý ở thời điểm là 0 mili-giây.Từ đó, ta biểu diễn thứ tự đó trên giản đồ Gantt như sau:

image002

Như vậy, nếu được hỏi thời gian chờ của tiến trình P2 chẳng hạn, thì trong đây, ta sẽ trả lời là 24 miliseconds. Hoặc giả hỏi thời gian chờ của P3, ta sẽ có câu trả lời chính xác là 27.

Nhưng nếu thay đổi đề bài một chút như bảng dữ liệu ban đầu như sau:

Tiến trình Thời điểm vào Ready queue Thời gian xử lý
P1 0 24
P2 1 3
P3 2 3

Như ta thấy, trong dữ liệu lúc này xuất hiện thêm cả “Thời điểm vào Ready queue” của từng tiến trình. Như vậy, nếu cần minh họa trên giản đồ Gantt, ta sẽ không thay đổi nhiều, nhưng cần phải đọc kĩ đề và phân tích vấn đề. Lúc này thời gian chờ của P1 vẫn là 0, bởi nó vẫn giữ vị trí vào đầu tiên.

Nhưng với P2 thì khác, thời gian nó được đưa vào xử lý là ở mili-giây thứ 1. Tương tự với P3, tới giây thứ 3 nó mới được nạp vào và chiếm 3 miliseconds cần đề xử lý.

image003

Như vậy, thời gian chờ của P1 vẫn là 0, nhưng với P2 thì là: 24-1=23 P1 đã tốn 24 miliseconds xử lý rồi và P2 được nạp vào ở giây thứ 1 chứ không phải xuất phát cùng thời điểm như ví dụ trên là ở giây 0. Cuối cùng, thời gian chờ của P3 ­tính tương tự thì sẽ là 27-2=25 mili-giây.

Nhận xét FCFS

– Đơn giản, dễ cài đặt
– Chịu đựng hiện tượng tích lũy thời gian chờ
+ Tiến trình có thời gian xử lý ngắn đợi tiến trình có thời gian xử lý dài
+ Ưu tiên tiến trình cpu-bounded
– Có thể xảy ra tình trạng độc chiếm CPU
– Không phù hợp với hệ thống tương tác người dùng
VÕ TÌNH THƯƠNG
votinhthuong9@gmail.com

LEAVE A REPLY