Bài 4: Chiến Lược điều Phối CPU 1 (FIFO)

First – In – First Out Đúng như tên gọi của nó, bạn có thể hình dung được cách mà chiến lược này thực thi! Nghĩa là, tiến trình nào vào trước thì sẽ được thưc hiện trước.

Cụ thể, khi 1 tiến trình được được đưa vào hàng đợi ready thì PCB (Khối điều khiển tiến trình) sẽ đưa nó vào cuối hàng đợi, nó sẽ đợi các tiến trình phía trên thực thi xong thì mới đến lược nó!

Điều dĩ nhiên sẽ xảy ra là thời gian chờ trung bình chắc chắn sẽ dài, nên chiến lược này thường không được ưu tiên!

Để cho dễ hiểu mình sẽ có ví dụ như sau:

Đề bài: Cho 3 tiến trình P1 P2 P3  Có thời điểm vào Ready List  và thời gian xử lý như sau:

Ta có thời gian vào hàng đợi của từng tiến trình, tại thời điểm 0s, P1 nhẩy vào và đc phục vụ ngay lập tức. Vì do đây là chiến lược FIFO nên P1 sẽ được xử lý cho đến khi hết thời gian làm việc!

Sau thời gian đó thì trong hàng đợi lúc này đã có 2 tiến trình là P2 và P3. Tại thời điểm 2s thì P2 nhảy vào hàng đợi trước P3 nên nó sẽ được phục vụ trước P3. Thời gian xử lý P2: 4s.

Vậy P2 có thời gian chờ cho đến khi được phục vụ là bao nhiêu?

Uhm.. theo tôi nghĩ là 12s sau khi P1 thực hiện xong! Nhưng… đáp án là 10s! What?

Hãy để ý kỹ:

Bạn sẽ thấy vì P2 nó ko vào RL(Ready List, mình sẽ viết tắt là RL cho nhanh) tại thời điểm 0s mà là thời điểm 2s nên ta có đáp án là 10s (WT, Waiting times).

Sau khi P2 hoàn thành nhiệm vụ có thời gian là 4s thì P3 sẽ được phục vụ kế tiếp!

Vậy, các bạn hãy thử đoán xem nó có thời gian chờ là bao nhiêu?

Đúng rồi, nó phải chờ tổng cộng là 13s.

P1 thực hiện 12s  + P2 thực hiện 4s = 16s

Thời gian chờ P3 = 16s – thời điểm vào RL = 13s.

Ok, vậy còn thời gian chờ của P1?

Chính xác 0s (Nó có chờ ai đâu! @@)

Vậy tổng thời gian chờ trung bình cho bài toán này ở chiến lược FIFO là: (0s + 10s + 13s)/3 ~= 8s

Mình sẽ thêm 1 ví dụ khác từ slides mình đã học tại trường:

Ở ví dụ này người ta đã thử thay đổi thứ tự vào hàng đợi của 3 tiến trình P1 P2 P3. Và như vậy đã cho ra kết quả thời gian chờ trung bình đã giảm đáng kể!

Do đó, yếu điểm lớn nhất của giải thuật FIFO (hay còn gọi là giải thuật FCFS) này là khi các tiến trình đầu tiên đi vào hàng đợi và được phục vụ có thời gian làm việc cao thì sẽ dẫn đến thời gian chờ trung bình tăng!

Cũng vì lý do đó mà nó được coi là một giải thuật không được ưu tiên sử dụng nhiều!

Bài tiếp theo chúng ta sẽ xem đến giải thuật Round Robin (RR).

Chia sẻ:

• Twitter
• Facebook

Thích Đang tải...