Phương pháp phục vụ trước đến trước là gì?
First Come First Serve (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ự khi đến. Đây là thuật toán lập lịch CPU đơn giản và dễ dàng nhất. Trong loại thuật toán này, các quy trình yêu cầu CPU đầu tiên sẽ được cấp phát 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 quá trình) của nó được liên kết với phần đuôi của hàng đợi và khi CPU trở nên trống, nó sẽ được gán cho tiến trình ở đầu hàng đợi.
Trong hướng dẫn về hệ điều hành này, bạn sẽ học:
- Phương pháp phục vụ trước đến trước là gì?
- Đặc điểm của phương pháp FCFS
- Ví dụ về lập lịch FCFS
- FCFS hoạt động như thế nào? Tính toán thời gian chờ trung bình
- Ưu điểm của FCFS
- Nhược điểm của FCFS
Đặc điểm của phương pháp FCFS
- Nó hỗ trợ thuật toán lập lịch không ưu tiên và ưu tiên trước.
- Công việc luôn được thực hiện trên cơ sở ai đến trước được phục vụ trước.
- Nó rất dễ 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 là khá cao.
Ví dụ về lập lịch FCFS
Một ví dụ thực tế của phương pháp FCFS là mua vé xem phim trên quầy bán vé. Trong thuật toán lập lịch trình này, một người được phục vụ theo cách xếp hàng. Người đến trước xếp hàng mua vé trước rồi đến người tiếp theo. Việc này sẽ tiếp tục cho đến khi người cuối cùng trong hàng mua vé. Sử dụng thuật toán này, quá trình CPU hoạt động theo cách tương tự.
FCFS hoạt động như thế nào? Tính toán thời gian chờ trung bình
Đây là một ví dụ về năm quy trình đến vào những thời điểm khác nhau. Mỗi quy trình có thời gian bùng nổ khác nhau.
| Quá trình | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Sử dụng thuật toán lập lịch FCFS, các quá trình này được xử lý như sau.
Bước 0) Quá trình bắt đầu với P4 có thời gian đến 0
Bước 1) Tại thời điểm = 1, P3 đến. P4 vẫn đang thực hiện. Do đó, P3 được giữ trong một hàng đợi.
| Quá trình | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Bước 2) Tại thời điểm = 2, P1 đến được giữ trong hàng đợi.
| Quá trình | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Bước 3) Tại thời điểm = 3, quá trình P4 hoàn tất quá trình thực thi của nó.
Bước 4) Tại thời điểm = 4, P3, ở vị trí đầu tiên trong hàng đợi, bắt đầu thực hiện.
| Quá trình | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Bước 5) Tại thời điểm = 5, P2 đến và nó được giữ trong hàng đợi.
| Quá trình | Thời gian bùng nổ | Thời gian đến |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | số 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Bước 6) Tại thời điểm 11, P3 hoàn thành quá trình thực thi của nó.
Bước 7) Tại thời điểm = 11, P1 bắt đầu thực hiện. Nó có thời gian bùng nổ là 6. Nó hoàn thành việc thực thi ở khoảng thời gian 17
Bước 8) Tại thời điểm = 17, P5 bắt đầu thực hiện. 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 9) Tại thời điểm = 21, P2 bắt đầu thực hiện. Nó có thời gian bùng nổ là 2. Nó hoàn thành việc thực thi ở khoảng thời gian 23
Bước 10) 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à ư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 thuật toán lập lịch CPU
- Dễ dàng lập trình
- Ai đến trước được phục vụ trước
Nhược điểm của FCFS
Dưới đây là nhược điểm / hạn chế của việc sử dụng thuật toán lập lịch FCFS:
- Nó là một thuật toán lập lịch cho CPU Non-Preemptive, vì vậy sau 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 nó kết thúc quá trình thực thi.
- 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 quá 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ó, FCFS không hiệu quả lắm.
Tóm lược:
- Đị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à xử lý được xếp hàng đợi theo thứ tự đến
- Nó hỗ trợ lập lịch không ưu tiên và ưu tiên trước
- thuật toán.
- FCFS là viết tắt của First Come First Serve
- Một ví dụ thực tế của phương pháp FCFS là mua vé xem phim trên 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
- Nó là một thuật toán lập lịch cho CPU Non-Preemptive, vì vậy sau 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 nó kết thúc quá trình thực thi.