Rate this post

Thuật toán lập lịch trình First come first serve (FCFS) chỉ đơn giản là lên lịch công việc theo Arrival Time của họ. Công việc nào đến trước trong hàng đợi sẵn sàng sẽ lấy CPU trước. Arrival Time của công việc càng ít thì công việc nhận được CPU càng sớm. Lập lịch FCFS có thể gây ra vấn đề chết đói nếu Burst Time của quá trình đầu tiên là lâu nhất trong số tất cả các công việc.

Các bài viết liên quan:

Ưu điểm của FCFS

  • Đơn giản
  • Dễ dàng
  • Người đến trước, người phục vụ đầu tiên

Nhược điểm của FCFS

  1. Phương pháp lập lịch trình không có tính ưu tiên, quá trình sẽ chạy đến khi hoàn thành.
  2. Do tính chất không phủ đầu của thuật toán, vấn đề chết đói có thể xảy ra.
  3. Mặc dù nó dễ thực hiện, nhưng nó có hiệu suất kém vì Avg Waiting Time cao hơn so với các thuật toán lập lịch trình khác.

Xem thêm Thuật toán lập lịch trong Disk FCFS

Thí dụ

Hãy lấy một ví dụ về thuật toán lập lịch FCFS. Trong lịch trình sau, có 5 quy trình với ID quy trình P0, P1, P2, P3 và P4 . P0 đến tại thời điểm 0, P1 tại thời điểm 1, P2 tại thời điểm 2, P3 đến tại thời điểm 3 và Quy trình P4 đến tại thời điểm 4 trong hàng đợi sẵn sàng. Các quy trình và Arrival Time và Burst tương ứng của chúng được đưa ra trong bảng sau.

Turn Around TimeWaiting Time được tính bằng công thức sau.

  1. Turn Around Time   =  Completion Time  – Arrival Time   
  2. Waiting Time   =  Turn Around Time  – Thời gian liên tục   

Avg Waiting Time được xác định bằng cách tổng Waiting Time tương ứng của tất cả các quá trình và chia tổng cho tổng số quá trình.

Process IDArrival TimeBurst TimeCompletion TimeTurn Around TimeWaiting Time
002220
116số 871
22412106
33921189
4612332917

              Avg Waiting Time = 31/5

             (Biểu đồ Gantt)

Hiệu ứng đoàn xe trong FCFS

FCFS có thể bị ảnh hưởng bởi hiệu ứng đoàn nếu Burst Time của công việc đầu tiên là cao nhất trong số tất cả. Giống như trong cuộc sống thực, nếu một đoàn xe đang đi qua đường thì những người khác có thể bị chặn lại cho đến khi nó vượt qua hoàn toàn. Điều này cũng có thể được mô phỏng trong Hệ điều hành.

Xem thêm Lập lịch Highest Response Ratio Next (HRRN) trong hệ điều hành

Nếu CPU nhận được các quá trình có Burst Time cao hơn ở đầu trước của hàng đợi sẵn sàng thì các quá trình có Burst Time thấp hơn có thể bị chặn, có nghĩa là chúng có thể không bao giờ nhận được CPU nếu công việc đang thực hiện có Burst Time rất cao. Điều này được gọi là hiệu ứng đoàn xe hoặc chết đói .

Thí dụ

Trong ví dụ, Chúng tôi có 3 quy trình được đặt tên là P1, P2 và P3 . Thời gian Burt của quá trình P1 là cao nhất.

Turn Around TimeWaiting Time trong bảng sau, được tính theo công thức,

  1. Turn Around Time   =  Completion Time  – Arrival Time 
  2. Waiting Time   =  Turn Around Time – Thời gian liên tục   

Trong kịch bản đầu tiên, Quá trình P1 đến ở vị trí đầu tiên trong hàng đợi mặc dù; Burst Time của quá trình là cao nhất trong số tất cả. Vì, thuật toán Lập lịch biểu, chúng tôi đang theo sau là FCFS, do đó CPU sẽ thực thi Quy trình P1 đầu tiên.

Trong lịch trình này, Avg Waiting Time của hệ thống sẽ rất cao. Đó là vì hiệu ứng đoàn xe. Các quy trình khác P2, P3 phải đợi đến lượt trong 40 đơn vị thời gian mặc dù Burst Time của chúng rất thấp. Lịch trình này bị chết đói.

Process IDArrival TimeBurst TimeCompletion TimeTurn Around TimeWaiting Time
104040400
213434239
311444342

         Avg Waiting Time = 81/3

Trong kịch bản thứ hai, Nếu quá trình P1 đã đến cuối cùng của hàng đợi và các quá trình khác P2 và P3 sớm hơn thì vấn đề chết đói sẽ không có ở đó.

Ví dụ sau cho thấy độ lệch trong Waiting Time của cả hai kịch bản. Mặc dù độ dài của lịch trình là 44 chiếc nhưng Waiting Time sẽ ít hơn trong lịch trình này.

Process IDArrival TimeBurst TimeCompletion TimeTurn Around TimeWaiting Time
114044433
203330
301443

         Avg Waiting Time = 6/3

Xem thêm Priority Scheduling trong Hệ điều hành

Chi phí của FCFS 

Trong các ví dụ trên, chúng tôi giả định rằng tất cả các quá trình chỉ là các quá trình ràng buộc CPU. Chúng tôi cũng đã bỏ qua thời gian chuyển đổi ngữ cảnh.

Tuy nhiên, nếu thời gian được thực hiện bởi bộ lập lịch trong chuyển đổi ngữ cảnh được xem xét thì Avg Waiting Time của hệ thống sẽ tăng lên, điều này cũng ảnh hưởng đến hiệu quả của hệ thống.

Chuyển đổi ngữ cảnh luôn là một công việc cần thiết. Ví dụ sau mô tả hiệu quả sẽ bị ảnh hưởng như thế nào nếu thời gian chuyển đổi ngữ cảnh được xem xét trong hệ thống.

Thí dụ

Trong ví dụ sau, chúng ta đang xem xét năm quy trình P1, P2, P3, P4, P5 và P6. Arrival Time và thời gian Burst của họ được đưa ra bên dưới.

Process IDArrival TimeBurst Time
103
212
321
434
545
652

Nếu thời gian chuyển đổi ngữ cảnh của hệ thống là 1 đơn vị thì biểu đồ Gantt của hệ thống sẽ được lập như sau.

Cho δ = 1 đơn vị;

Hệ thống sẽ mất thêm 1 đơn vị thời gian (chi phí) sau khi thực hiện mọi quy trình để lên lịch cho quy trình tiếp theo.

  1. Hiệu quả = ( 6/23 ) X 100%   
  2. Hiệu quả = (1-6 / 23) X 100%   

Xem thêm Kiểm tra lỗ hổng bảo mật Session Timeout

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now