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
- 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.
- 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.
- 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 Time và Waiting Time được tính bằng công thức sau.
- Turn Around Time = Completion Time – Arrival Time
- 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 ID | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time |
| 0 | 0 | 2 | 2 | 2 | 0 |
| 1 | 1 | 6 | số 8 | 7 | 1 |
| 2 | 2 | 4 | 12 | 10 | 6 |
| 3 | 3 | 9 | 21 | 18 | 9 |
| 4 | 6 | 12 | 33 | 29 | 17 |
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 Time và Waiting Time trong bảng sau, được tính theo công thức,
- Turn Around Time = Completion Time – Arrival Time
- 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 ID | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time |
| 1 | 0 | 40 | 40 | 40 | 0 |
| 2 | 1 | 3 | 43 | 42 | 39 |
| 3 | 1 | 1 | 44 | 43 | 42 |
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 ID | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time |
| 1 | 1 | 40 | 44 | 43 | 3 |
| 2 | 0 | 3 | 3 | 3 | 0 |
| 3 | 0 | 1 | 4 | 4 | 3 |
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 ID | Arrival Time | Burst Time |
| 1 | 0 | 3 |
| 2 | 1 | 2 |
| 3 | 2 | 1 |
| 4 | 3 | 4 |
| 5 | 4 | 5 |
| 6 | 5 | 2 |
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.
- Hiệu quả = ( 6/23 ) X 100%
- Hiệu quả = (1-6 / 23) X 100%
