Thuật toán lập kế hoạch FCFS: Chương trình ví dụ là gì
Nathaniel Brooks
Phương pháp đến trước được phục vụ trước là gì?
Đến trước phục vụ trước (FCFS) là một thuật toán lập lịch của hệ điều hành, tự động thực hiện các yêu cầu và quy trình được xếp hàng đợi theo thứ tự đến của chúng. Đây là thuật toán lập lịch CPU dễ dàng và đơn giản nhất. Trong loại thuật toán này, các tiến trình yêu cầu CPU trước sẽ được phân bổ CPU trước. Điều này được quản lý bằng hàng đợi FIFO. Hình thức đầy đủ của FCFS là First Come First Serve.
Khi tiến trình đi 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à khi CPU rảnh rỗi, nó sẽ được gán cho tiến trình ở đầu hàng đợi.
Đặc điểm của phương pháp FCFS
- Nó hỗ trợ thuật toán lập kế hoạch không ưu tiên và ưu tiê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 kế hoạch FCFS
Một ví dụ thực tế của phương pháp FCFS là mua vé xem phim tại quầy bán vé. Trong thuật toán lập lịch này, một người được phục vụ theo cách thức xếp hàng. Người đến trước sẽ mua vé trước rồi mới đến người tiếp theo. Điều này sẽ 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, quy 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
Đây là một ví dụ về năm quá trình đến vào những thời điểm khác nhau. Mỗi quá trình có thời gian bùng nổ khác nhau.
| Quy trình xét duyệt | 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 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.
| Quy trình xét duyệt | 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 |
Bước 3) Tại thời điểm = 2, P1 đến và được giữ trong hàng đợi.
| Quy trình xét duyệt | 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 |
Bước 4) Tại thời điểm = 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.
| Quy trình xét duyệt | 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 |
Bước 6) Tại thời điểm =5, P2 đến và được giữ trong hàng đợi.
| Quy trình xét duyệt | 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 |
Bước 7) Tại thời điểm 11, P3 hoàn thành việc thực thi.
Bước 8) Tại thời điểm = 11, P1 bắt đầu thực thi. Nó có thời gian bùng nổ là 6. Nó hoàn thành việc thực hiện ở khoảng thời gian 17
Bước 9) Tại thời điểm = 17, P5 bắt đầu thực thi. Nó có thời gian bùng nổ là 4. Nó hoàn thành việc thực thi tại thời điểm = 21
Bước 10) Tại thời điểm = 21, P2 bắt đầu thực thi. Nó có thời gian bùng nổ là 2. Nó hoàn thành việc thực hiện ở khoảng thời gian 23
Bước 11) 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
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
Thời gian chờ trung bình
= 40/5= 8
Ưu điểm của FCFS
Dưới đây là những ưu/lợi ích của việc sử dụng thuật toán lập lịch FCFS:
- Dạng đơn giản nhất của một Thuật toán lập lịch CPU
- Dễ lập trình
- Đầu tiên đến trước được phục vụ
Nhược điểm của FCFS
Dưới đây là những nhược điểm/nhược điểm của việc sử dụng thuật toán lập lịch FCFS:
- Đây là thuật toán lập lịch CPU không được ưu tiên, vì vậy sau khi tiến trình được phân bổ cho CPU, nó sẽ không bao giờ giải phóng CPU cho đến khi thực thi xong.
- Thời gian chờ đợi trung bình cao.
- Các quy trình ngắn ở phía sau hàng đợi phải đợi quy trình dài ở phía trước kết thúc.
- Không phải là một 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.
Tổng kết
- Định nghĩa: FCFS là một thuật toán lập lịch của hệ điều hành, tự động thực hiện các yêu cầu và quy trình được xếp hàng đợi theo thứ tự chúng đến
- Nó hỗ trợ lập kế hoạch không ưu tiên và ưu tiên
- thuật toán.
- FCFS là viết tắt của Đến trước phục vụ trước.
- Một ví dụ thực tế của phương pháp FCFS là mua vé xem phim tại quầy bán vé.
- Đây là dạng đơn giản nhất của thuật toán lập lịch CPU
- Đây là thuật toán lập lịch CPU không được ưu tiên, vì vậy sau khi tiến trình được phân bổ cho CPU, nó sẽ không bao giờ giải phóng CPU cho đến khi thực thi xong.
