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.
Giới thiệu về Lập lịch FCFS
Lập lịch trong hệ điều hành là một quá trình quan trọng quyết định thứ tự và thời điểm các tiến trình được CPU xử lý. Một trong những thuật toán lập lịch đầu tiên và cơ bản nhất được sử dụng trong các hệ điều hành là First-Come, First-Served (FCFS). FCFS hoạt động dựa trên nguyên tắc đơn giản: tiến trình nào đến trước sẽ được xử lý trước. Điều này tạo ra một hệ thống lập lịch minh bạch và dễ dàng hiểu, nơi mỗi tiến trình được xem xét theo thứ tự thời gian chúng yêu cầu CPU.
Thuật toán FCFS có tầm quan trọng lớn trong thiết kế hệ điều hành, đặc biệt là trong các hệ thống đơn giản hoặc các ứng dụng không yêu cầu sự phân biệt đối xử cao giữa các tiến trình. FCFS đảm bảo một quy trình xử lý công bằng, không phân biệt, nơi mỗi tiến trình được xử lý theo thứ tự nó xuất hiện mà không cần xem xét đến độ ưu tiên hay phức tạp của tiến trình đó. Điều này đặc biệt quan trọng trong các môi trường mà sự đơn giản và dễ dàng triển khai là ưu tiên hàng đầu.
Tuy nhiên, mặc dù FCFS có ưu điểm về sự đơn giản và công bằng, nhưng nó có thể không phải là lựa chọn tối ưu trong một số tình huống cụ thể, đặc biệt là trong các hệ thống đa nhiệm nơi mà thời gian phản hồi nhanh là quan trọng. Do đó, trong quá trình phát triển và thiết kế hệ điều hành, việc lựa chọn và tinh chỉnh thuật toán lập lịch phù hợp với nhu cầu cụ thể của hệ thống là cần thiết. FCFS, với tính chất đơn giản và dễ dàng của mình, vẫn giữ một vị trí quan trọng trong lịch sử và cơ bản của lập lịch hệ thống.
Nguyên tắc Cơ bản của Lập lịch FCFS
Lập lịch First-Come, First-Served (FCFS) là một trong những thuật toán lập lịch đơn giản nhất trong hệ thống điều hành. Cơ sở của nó dựa trên nguyên tắc “đến trước, phục vụ trước”. Điều này có nghĩa là các tiến trình sẽ được xử lý theo thứ tự chúng đến và yêu cầu CPU. Không có sự phân biệt hay ưu tiên nào giữa các tiến trình; tiến trình đến đầu tiên sẽ được phục vụ đầu tiên.
Trong lập lịch FCFS, hàng đợi đóng một vai trò quan trọng. Mọi tiến trình đều được thêm vào cuối hàng đợi khi chúng đến. Hệ thống sau đó sẽ xử lý từng tiến trình một, bắt đầu từ tiến trình ở đầu hàng đợi và tiếp tục theo thứ tự đến. Điều này tạo ra một quy trình xử lý tuần tự, nơi mỗi tiến trình phải chờ đợi cho đến khi tất cả các tiến trình trước nó hoàn thành.
Một đặc điểm quan trọng của FCFS là trình tự thực thi dựa hoàn toàn vào thời gian đến của các tiến trình. Điều này có thể dẫn đến hiệu ứng đoàn xe, nơi một tiến trình dài có thể làm chậm toàn bộ hệ thống bằng cách giữ CPU trong một khoảng thời gian dài, trong khi các tiến trình ngắn hơn khác đang chờ đợi. Mặc dù FCFS là một thuật toán dễ hiểu và dễ triển khai, nhưng nó không phải lúc nào cũng hiệu quả trong việc quản lý tài nguyên hệ thống, đặc biệt là trong các môi trường nơi thời gian đáp ứng nhanh là quan trọng.
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%
Xem thêm Kiểm tra lỗ hổng bảo mật Session Timeout
Ưu điểm và Nhược điểm của FCFS
Ưu điểm của FCFS
Thuật toán FCFS, với cơ chế “người đến trước, người phục vụ đầu tiên”, mang lại nhiều ưu điểm trong việc lập lịch hệ thống. Đầu tiên và quan trọng nhất, đó là sự đơn giản của nó. FCFS không yêu cầu tính toán phức tạp hay quản lý dữ liệu phức tạp, làm cho việc triển khai và bảo trì trở nên dễ dàng hơn. Sự đơn giản này cũng làm tăng tính minh bạch trong quá trình lập lịch, nơi mỗi tiến trình được xử lý một cách công bằng dựa trên thời gian đến của nó, không ưu tiên tiến trình nào.
Nhược điểm của FCFS
Tuy nhiên, bên cạnh những ưu điểm, FCFS cũng có những hạn chế đáng kể. Một trong những nhược điểm chính là thiếu tính linh hoạt và không có khả năng ưu tiên. Trong FCFS, mỗi quá trình sẽ chạy đến khi hoàn thành, mà không xem xét đến độ ưu tiên hay cấp độ quan trọng của nó. Điều này có thể dẫn đến tình trạng chết đói (starvation), nơi các tiến trình ngắn nhưng có độ ưu tiên cao bị trì hoãn không cần thiết bởi các tiến trình dài hơn đang chiếm dụng CPU.
Một hạn chế khác của FCFS là hiệu suất thấp. Trong hệ thống FCFS, thời gian chờ đợi trung bình (Average Waiting Time) thường cao hơn so với các thuật toán lập lịch khác. Điều này là do tiến trình dài có thể gây ra hiệu ứng đoàn xe, nơi các tiến trình ngắn bị trì hoãn bởi một tiến trình dài đang xử lý, làm tăng thời gian chờ đợi tổng thể của hệ thống. Mặc dù đơn giản và dễ thực hiện, nhưng trong một số trường hợp, nhất là trong môi trường đa nhiệm yêu cầu thời gian phản hồi nhanh, FCFS có thể không phải là lựa chọn tối ưu.
Tối ưu hóa và Cải thiện Lập lịch FCFS
Mặc dù FCFS có những hạn chế nhất định, nhưng vẫn có những cách thức để tối ưu hóa và cải thiện nó, giảm thiểu nhược điểm và tăng hiệu quả trong môi trường hệ thống.
Một trong những chiến lược để tối ưu hóa FCFS là kết hợp nó với các kỹ thuật ưu tiên. Ví dụ, một hệ thống có thể sử dụng FCFS như là cơ sở, nhưng đồng thời triển khai một hệ thống ưu tiên cho các tiến trình đặc biệt quan trọng hoặc cần thời gian phản hồi nhanh. Điều này cho phép hệ thống duy trì được sự đơn giản của FCFS cho đa số các tiến trình, nhưng vẫn có khả năng xử lý nhanh chóng các tác vụ quan trọng.
Một phương pháp khác là kết hợp FCFS với thuật toán Round Robin trong các môi trường đa nhiệm. Trong cách tiếp cận này, các tiến trình được lên lịch theo FCFS, nhưng mỗi tiến trình chỉ được phép sử dụng CPU trong một khoảng thời gian cố định trước khi quyền kiểm soát được chuyển sang tiến trình tiếp theo. Điều này giúp ngăn chặn hiệu ứng đoàn xe và giảm thời gian chờ đợi cho các tiến trình ngắn.
Về triển vọng trong tương lai, có tiềm năng lớn trong việc cải tiến FCFS bằng cách sử dụng công nghệ học máy và trí tuệ nhân tạo. Các hệ thống có thể học cách dự đoán độ dài của các tiến trình dựa trên dữ liệu lịch sử và điều chỉnh lịch trình tương ứng. Ngoài ra, việc phân tích mô hình sử dụng và yêu cầu của các tiến trình trong thực tế có thể giúp hệ thống tự động điều chỉnh phương pháp lập lịch để đạt hiệu quả cao nhất.
Như vậy, mặc dù FCFS có những hạn chế, nhưng với sự phát triển của công nghệ và các phương pháp tối ưu hóa, nó vẫn có thể trở thành một công cụ lập lịch hiệu quả trong một số tình huống cụ thể, đặc biệt khi được kết hợp với các kỹ thuật lập lịch hiện đại.
