Các hệ điều hành dùng cách nào để điều phối tiến trình?
#computer_science #operating_system #Wednonquora
Khi ta viết một chương trình nào đó, nó mới chỉ đơn giản là những đoạn code nằm trên ổ cứng. Chỉ khi ta chạy chúng, những đoạn lệnh ấy mới thực sự làm việc với CPU, bộ nhớ… Ta gọi đó là những tiến trình (process).
Hệ điều hành suy cho cùng cũng là một phần mềm, chẳng qua nó có quyền to hơn các phần mềm thông thường, và có quyền cho phép các phần mềm khác chạy theo cách mà nó quyết định.
Ví dụ, bạn là người xếp hàng đi bệnh viện. Hàng người đang đứng giống như hàng đợi tiến trình. Bác sĩ trong phòng là CPU, còn cô điều dưỡng mà gọi số giống như OS vậy. Ví dụ cô ấy đọc tên bạn Mai Trường Sơn, thương binh, được ưu tiên, cho vào trước; hoặc một người đang khám chờ kết quả, cô ấy mời đi ra để cho người khác vào phòng… Những hành động cơ cấu để ai khám trước, khám sau, khám bao lâu ấy, giống như việc điều phối tiến trình.
Nói chung, việc điều phối tiến trình phải đảm bảo sự công bằng, tiến trình nào cũng được thực thi, bởi CPU thì chỉ có một, mà thằng nào cũng muốn được dùng. Ngoài ra, biểu hiện của nó ra phía người dùng là tốc độ phản hồi, sự mượt mà, tốc độ chạy của phần mềm, v.v… Chẳng hạn, người dùng MacOS cảm thấy sự mượt mà hơn Windows, một phần cũng do thuật toán điều phối tiến trình của 2 hệ điều hành này là khác nhau.
Một số thuật toán điều phối CPU cơ bản
[1]
Trước khi vào phần này, mình xin giải thích 1 số thuật ngữ được Việt hoá mà mình sử dụng:
đói (nguyên văn: starvation): tình trạng một tiến trình đợi mãi mà không được dùng tài nguyên, thời gian chờ có thể là vô hạn.
trưng dụng (nguyên văn: preemptive): một tiến trình đang làm việc với tài nguyên, bị buộc phải nhường lại cho tiến trình khác, gọi là trưng dụng tài nguyên. Nghe bất công nhỉ?
Tương tự, ta có không trưng dụng (nguyên văn: non-preemptive): tiến trình nào đang chạy thì chạy hết mới trả lại tài nguyên.
1. first come first serve (FCFS)
Đúng như cái tên, đơn giản thằng nào đến trước thì được chạy trước.
- Dùng hàng đợi FIFO
- Không trưng dụng
- Dễ hiểu, dễ cài đặt
- Hiệu năng kém, thời gian chờ đợi lâu
2. Shortest job next (SJN)
Thuật toán này còn được gọi là Shortest Job First (SJF). Ưu tiên gọi những tiến trình mà thời gian cần dùng CPU còn lại là ngắn nhất (tức là sắp hoàn thành nhất).
- Dùng hàng đợi ưu tiên với độ ưu tiên là thời gian còn lại
- Dễ hiểu, dễ cài đặt
- Không trưng dụng
- Giảm thời gian chờ đợi
- Có thể gây ra đói CPU: nếu nhiều tiến trình mới có thời gian cần thực hiện ngắn, thì tiến trình có thời gian lâu hơn sẽ bị đẩy vô hạn xuống cuối hàng đợi
- Cần biết trước thời gian cần để tiến trình đó hoàn thành
3. Hàng đợi ưu tiên (Priority Based Scheduling)
Mỗi tiến trình được gán cho 1 số chỉ độ ưu tiên. Độ ưu tiên cao thì được thực hiện trước, cùng độ ưu tiên thì FCFS.
- Không trưng dụng
- Độ ưu tiên được xét theo chi phí bộ nhớ, thời gian, hoặc đơn giản là “con ông cháu cha” thì được ưu tiên hoy
- Có thể gây ra đói CPU: tiến trình mới đến có độ ưu tiên cao hơn thì tiến trình có độ ưu tiên thấp có khả năng bị chờ vô hạn
4. Shorest remaining time (srt)
Y hệt SJN, nhưng có trưng dụng: thằng mới đến mà có thời gian ngắn hơn thời gian thằng đang thực thi thì cũng chiếm luôn CPU.
- Có trưng dụng
- Phù hợp với hệ thống ưu tiên độ phản hồi của những tiến trình ngắn
5. Round robin (RR)
Thuật toán này giống kiểu chơi gangbang CPU ấy, ai cũng được một lát rồi đến người tiếp theo, đảm bảo sự công bằng tối đa.
- Có trưng dụng
- Các tiến trình mới đến được thêm vào cuối của hàng đợi vòng tròn
- Một tiến trình chỉ được dùng tối đa liên tiếp một khoảng thời gian nhất định gọi là quantum
- Hết một quantum, nếu chưa xong, nó sẽ lưu lại trạng thái và bị tiến trình kế tiếp trưng dụng, và quay xuống cuối hàng đợi, đợi đến vòng tiếp theo
- Nếu chưa hết quantum mà đã “ra” rồi, thì nhường CPU cho tiến trình kế tiếp
- Công bằng, không bị đói. Có thể xác định trước trường hợp xấu nhất mà một tiến trình phải chờ đợi là bao lâu
- Giảm thời gian chờ, tăng tốc độ phản hồi so với FCFS
- Hiệu năng phụ thuộc rất nhiều vào việc chọn quantum cho phù hợp (thường tính bằng milisecond)
6. Hàng đợi nhiều tầng (Multiple-Level Queues Scheduling)
Đây không phải thuật toán nhất định nào đó, mà nó phép kết hợp các thuật toán trên lại một cách hợp lý. Có nhiều hàng đợi khác nhau được đánh độ ưu tiên, mỗi hàng đợi có thể dùng FCFS, SJN hay RR, tuỳ đặc tính và nhu cầu. Hệ điều hành sẽ chọn tiến trình một cách phù hợp, chuyển tiến trình này sang một hàng đợi khác khi cần v.v…
Tổng kết
Trên đây chỉ là các thuật toán cực kỳ cơ bản, dùng để xây dựng nên các thuật toán được sử dụng trong thực tế.
Bạn thắc mắc hệ điều hành mình đang dùng sử dụng thuật toán nào? Chà, chắc chỉ có ông nào leak code ra thì mới biết được chính xác! Nhưng ta có thể biết được về cơ bản nó được phát triển từ thuật nào nào trong 6 cái trên.
Chẳng hạn, hệ điều hành Windows chủ yếu xây dựng trên thuật toán Round Robin, tuy nhiên nó được nâng lên một tầm cao mới, đảm bảo cho người dùng tình trạng giật lag và not responding rất thường xuyên.
Nhiều hệ điều hành còn sử dụng AI, phân tích thói quen của người dùng, điều chỉnh độ ưu tiên, thay đổi quantum cho phù hợp tình hình… [2]
Giả sử bạn đang tự xây một hệ điều hành cho riêng mình, bạn sẽ chọn thuật toán nào? Bạn muốn ưu tiên cho phần mềm chạy thật nhanh và liền mạch, hay ưu tiên cho các thao tác được phản hồi mượt mà?
Hay bạn không quan tâm lắm, tập trung xây dựng UI/UX và kệ moẹ đám tiến trình (xây dựng hoàn toàn trên kernel có sẵn chẳng hạn).
—–
Mình đang ôn bài thôi ạ, mấy hôm nữa mình thi môn này, viết cái này để ôn lại xíu
Nguồn:
[1] https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm
[2]
https://pdfs.semanticscholar.org/8d73/52c3063fa079eaf0b3b5ae4e990ae4eddaa1.pdf
Bùi Thanh Lâm
