Thuật toán lập kế hoạch FCFS: Chương trình ví dụ là gì
Nathaniel Brooks
⚡ Tóm tắt thông minh
Thuật toán lập lịch FIFO (First Come First Serve) chạy các tiến trình theo đúng thứ tự chúng đến hàng đợi sẵn sàng, sử dụng phương pháp FIFO đơn giản không ưu tiên, khiến nó trở thành thuật toán lập lịch CPU dễ thực hiện nhất đối với một hệ điều hành.
Phương pháp đến trước được phục vụ trước là gì?
Đến trước phục vụ trước (FCFS) FCFS là một thuật toán lập lịch hệ điều hành tự động thực thi các yêu cầu và tiến trình được xếp hàng theo thứ tự chúng đến. Đây là thuật toán lập lịch CPU dễ nhất và đơn giản nhất. Trong loại thuật toán này, tiến trình yêu cầu CPU trước sẽ được cấp phát CPU trước. Điều này được quản lý bằng hàng đợi FIFO. FCFS là viết tắt của First Come First Serve (Đến trước được phục vụ trước).
Khi một tiến trình vào hàng đợi sẵn sàng, PCB (Khối điều khiển tiến trình) của nó được liên kết với phần cuối của hàng đợi. Vì vậy, khi CPU rảnh, nó sẽ được gán cho tiến trình ở đầu hàng đợi.
Đặc điểm của phương pháp FCFS
Các đặc điểm chính của phương pháp "Ai đến trước được phục vụ trước" được liệt kê dưới đây:
- Nó là một không ưu tiên Thuật toán lập lịch, sao cho một tiến trình giữ CPU cho đến khi hoàn thành thời gian thực thi của nó.
- Công việc luôn được thực hiện theo nguyên tắc ai đến trước được phục vụ trước.
- Nó rất dễ dàng để thực hiện và sử dụng.
- Phương pháp này có hiệu suất kém và thời gian chờ đợi chung khá cao.
Ví dụ về lập lịch FCFS
Một ví dụ thực tế về phương pháp FCFS là việc mua vé xem phim tại quầy vé. Trong thuật toán lập lịch này, người ta được phục vụ theo thứ tự trong hàng đợi. Người đến đầu tiên trong hàng đợi sẽ mua vé trước, sau đó đến người tiếp theo. Quá trình này tiếp tục cho đến khi người cuối cùng trong hàng đợi mua vé. Sử dụng thuật toán này, tiến trình CPU hoạt động theo cách tương tự.
FCFS hoạt động như thế nào? Tính thời gian chờ đợi trung bình
Để hiểu cách thuật toán lập lịch cho các tiến trình, đây là một ví dụ về năm tiến trình đến vào các thời điểm khác nhau. Mỗi tiến trình có một khoảng thời gian thực thi khác nhau.
| Quy trình | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Sử dụng thuật toán lập lịch FCFS, các quy trình này được xử lý như sau.
Bước 1) Quá trình bắt đầu với P4, có thời gian đến là 0.
Bước 2) Tại thời điểm = 1, P3 đến. P4 vẫn đang thực thi. Do đó, P3 được giữ trong hàng đợi.
Bước 3) Tại thời điểm t=2, P1 đến và được giữ trong hàng đợi.
Bước 4) Tại thời điểm t=3, tiến trình P4 hoàn tất quá trình thực thi của nó.
Bước 5) Tại thời điểm = 4, P3, PXNUMX đầu tiên trong hàng đợi, bắt đầu thực thi.
Bước 6) Vào thời điểm t=5, P2 đến và được xếp vào hàng chờ.
Bước 7) Vào thời điểm t=11, P3 hoàn thành quá trình thực thi của nó.
Bước 8) Tại thời điểm t=11, P1 bắt đầu thực thi. Nó có thời gian thực thi tức thời là 6, vì vậy nó hoàn thành việc thực thi ở khoảng thời gian 17.
Bước 9) Tại thời điểm t=17, P5 bắt đầu thực thi. Nó có thời gian thực thi tức thì là 4, vì vậy nó hoàn thành việc thực thi tại thời điểm t=21.
Bước 10) Tại thời điểm t=21, P2 bắt đầu thực thi. Nó có thời gian thực thi tức thời là 2, vì vậy nó hoàn thành việc thực thi ở khoảng thời gian 23.
Bước 11) Bây giờ, chúng ta hãy tính thời gian chờ trung bình cho ví dụ trên.
Waiting time = Start time - Arrival time
P4 = 0 – 0 = 0
P3 = 3 – 1 = 2
P1 = 11 – 2 = 9
P5 = 17 – 4 = 13
P2 = 21 – 5 = 16
Thời gian chờ trung bình = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8
Ưu điểm của FCFS
Dưới đây là những ưu điểm và lợi ích của việc sử dụng thuật toán lập lịch FCFS:
- Đây là dạng đơn giản nhất của một Thuật toán lập lịch CPU.
- Việc lập trình rất dễ dàng.
- Nó tuân theo nguyên tắc đơn giản: ai đến trước được phục vụ trước.
Nhược điểm của FCFS
Dưới đây là những nhược điểm và hạn chế của thuật toán lập lịch FCFS:
- Đây là thuật toán lập lịch CPU không ưu tiên, vì vậy một khi tiến trình đã được cấp phát cho CPU, nó sẽ không bao giờ giải phóng CPU cho đến khi hoàn thành việc thực thi.
- Thời gian chờ đợi trung bình khá cao.
- Các tiến trình ngắn ở cuối hàng đợi phải chờ tiến trình dài ở đầu hàng đợi hoàn thành.
- Đây không phải là kỹ thuật lý tưởng cho các hệ thống chia sẻ thời gian.
- Vì tính đơn giản của nó nên FCFS không hiệu quả lắm.
