Bài viết nằm trong series Multi-thread programming in depth
Như tiêu đề bài viết, bài viết này sẽ chỉ ra cách mà OS quản lý thread. Tuy nhiên thì những gì mình viết tới dưới đây sẽ chỉ đủ để nói tới bề nổi của tảng băng chìm về cách OS quản lý thread. Bản thân mình xuất phát là 1 Java Developer song có tìm hiểu về Devops nên có thể mình sẽ có 1 bài viết khác về devops scheduling linux chi tiết sau. Mọi người cùng đón đọc nhé. Giờ thì let's dig in!!!
Khi một thread được khởi tạo, nó sẽ được gắn 1 PID. Đó là nhưng gì ta biết. Thực chất thì để lưu trữ dữ liệu của 1 thread, OS sẽ sử dụng một cấu trúc dữ liệu gọi là Process Control Block. Mỗi PCB sẽ được xác định bởi ProcessId - PID. PCB sẽ bao gồm các thành phần thông tin sau:
- Process ID (PID): Số nguyên xác định định danh của tiến trình.
- State: Trạng thái hiện tại của tiến trình (là một trong các trạng thái ở phần trên)
- Pointer: Con trỏ lưu địa chỉ của tiến trình cha.
- Priority: Độ ưu tiên của tiến trình, giúp cho vi xử lý xác định thứ tự thực hiện.
- Program Counter: Con trỏ lưu địa chỉ của chỉ dẫn tiếp theo giúp cho tiến trình thực thi (là một phép tính hoặc tương tự).
- CPU Registers: Các thanh ghi tiến trình cần sử dụng để thực thi.
- I/O Information: Thông tin về các thiết bị đọc - ghi mà tiến trình cần sử dụng
- Accounting Information: Chứa các thông tin về việc sử dụng CPU như thời gian sử dụng, định danh .... Tại sao lại nhắc tới PCB vì ta sẽ tiếp cận tới nó ở chi tiết dưới đây.
1. Scheduler
Dễ thấy rằng khi bạn bật taskbar manager hoặc top, có rất nhiều chương trình, vô số thread chạy ẩn trong chương trình. Trong khi đó con máy PC 2 cores (processors). Thread nào cũng muốn được thực thi, tranh nhau như vậy thì không ổn?
Nếu tranh thì phân chia thế nào cho fair giữa các thread đây?
Quá phức tạp, thường sẽ ít ai quan tâm tới nó. Nhưng thực chất trong OS sẽ có một khái niệm gọi là Scheduler hay Scheduling Linux. Dịch nôm na ra là bộ lập lịch. Nhiệm vụ của Scheduler là:
- Sắp xếp thread vào hàng đợi.
- Lên kế hoạch và điều khiển các thread và process để thực thi.
OS hay Scheduler quản lý OS qua Process Scheduling Queues (Hàng đợi lập lịch tiến trình). Mỗi trạng thái của thread sẽ có một Queue riêng tương ứng. Khi trạng thái của một tiến trình được thay đổi, PCB của thread sẽ bị xóa liên kết khỏi hàng đợi hiện tại và được chuyển sang hàng đợi trạng thái mới (áp dụng thuật toán danh sách liên kết cơ bản và cơ chế truy xuất theo địa chỉ). Ngoài các hàng đợi theo trạng thái, hệ điều hành còn duy trì một số hàng đợi như:
- Job queue: Hàng đợi lưu trữ mọi tiến trình đang ở trong hệ thống.
- Ready queue: Chứa các tiến trình mới được khởi tạo.
- Device queue: Nếu một tiến trình cần chờ để có thể sử dụng thiết bị I/O thì được đưa vào đây.
Dưới đây là hình ảnh mô ta một tiến trình từ khi bắt đầu cho đến khi rời khỏi CPU
Theo như trên hình, khi một tiến trình rời khỏi Ready queue để bắt đầu thực thi, nó có thể có 4 khả năng xảy ra:
- Request I/O: tiến trình cần xử lý liên quan đến đọc - ghi => Sẽ được chuyển vào Device queue.
- Timeout: tiến trình đã dùng hết thời gian được cấp phép bởi CPU, sẽ được đưa trở lại vào Ready queue để đợi đến lượt tiếp theo.
- Fork child: tiến trình tạo ra tiến trình con để tiếp tục xử lý, thường là các tiến trình phức tạp hoặc cần xử lý đồng thời nhiều công việc.
- Interrupt: tiến trình bị gián đoạn do một vấn đề nào đó đột ngột phát sinh.
2. Context switch
Một khái niệm khác có thể được nhắc tới là Context switch (kỹ thuật chuyển ngữ cảnh). Đây là cơ chế lưu trữ và khôi phục trạng thái hoặc ngữ cảnh của CPU trong PCB. Nó cho phép thực hiện tiến trình được bắt đầu lại từ cùng một trạng thái kết thúc trước đó. Giống như khi ta ghi dữ liệu lên một file, sau đó khi sửa file này ta sẽ tiếp tục với nội dung được lưu trước đó thay vì bắt đầu lại từ đầu. Kỹ thuật này cho phép nhiều tiến trình cùng chia sẻ một CPU. Context switch là một tính năng thiết yếu của hệ điều hành đa nhiệm. Khi bộ lập lịch chuyển CPU từ việc thực thi một tiến trình này sang một tiến trình khác, trạng thái từ tiến trình đang chạy hiện tại được lưu trữ vào PCB. Với lần thực thi tiếp theo, trạng thái cho tiến trình đó được tải từ PCB của chính nó và được sử dụng để thiết lập bộ đếm chương trình, các thanh ghi,... Tại thời điểm đó, tiến trình thứ hai có thể bắt đầu thực thi. Việc tính toán Context switch rất chuyên sâu, vì thanh ghi và trạng thái bộ nhớ phải được lưu và khôi phục lại đúng như giai đoạn thực thi trước đó. Để tránh thời gian chuyển đổi quá lâu, một số hệ thống phần cứng sử dụng hai hoặc nhiều thanh ghi của bộ xử lý để tính toán. Khi tiến trình được chuyển đổi bởi Context switch, các thông tin sau sẽ được lưu trữ để sử dụng: bộ đếm chương trình (Program Counter), thông tin lập lịch (PID), giá trị thanh ghi cơ sở và giới hạn, thanh ghi hiện được sử dụng (CPU registers), trạng thái thay đổi (State), thông tin I/O (I/O Information) và thông tin kế toán (Accounting Information).
Tóm gọn thì Context Switch thực hiện công việc:
- Lưu lại data và state (PCB) của thread trước thời điểm context switch.
- Phục hồi data và state (PCB) được lưu trước đó để thread tiếp tục chạy.
3. Scheduling Algorithm
Có thể thấy tầm quan trọng của Context Switch cũng như effort để lưu trữ PCB. Vậy thì nó ảnh hưởng tới việc phân chia thread thế nào? Liên hệ tới việc điều phối thread vào đúng từng queue tương ứng như nói trên.
Cụ thể, có các scheduling algorithm được scheduler sử dụng như sau:
- Priority: Ưu tiên dựa trên priority. Có thể change priority cho thread với Java hoặc command linux.
- Round-robin: Xử lý lần lượt theo vòng.
- Shortest job next: Ưu tiên thread nào có khối lượng công việc ít nhất.
- Multi-level queue: Sẽ có nhiều queue thay vì một ready queue. Phân chia queue dựa trên các đặc điểm của thread.
- First come first serve: Ưu tiên thread nào đến trước (FIFO)
- Shortest remaining time: Ưu tiên thread nào còn ít công việc nhất.
4. Scheduling Target
Quá trời thuật toán mà Scheduler có thể sử dụng để quản lý thread. Vậy thì thuật toán nào được chọn bởi Scheduler? Qua tìm hiểu thì mình thấy có các tiêu chí sau:
- Maximize fairness: Tối đa sự công bằng giữa các thread, priority và thời gian xử lý ngang nhau.
- Maximize throughput: Tối đa số lượng các thread/process được xử lý trong 1 khoảng thời gian.
- Minimize latency: Giảm thiểu độ trễ, giảm thiểu tần số context switch.
- Minimize waiting time: Giảm thời gian chờ đợi để được thực thi giữa các thread.
To conclude
Mỗi OS khác nhau sẽ có các tiêu chí, mục tiêu để Scheduler lựa chọn thuật toán và quản lý threads. Song là một developer thì khó mà quản lý được thứ tự thực thi của threads. Thôi thì đấy là việc của OS 
Reference
- https://medium.com/geekculture/process-scheduling-in-linux-592028a5d545
- https://docs.kernel.org/scheduler/index.html
- https://opensource.com/article/19/2/fair-scheduling-linux
- https://www.pearsonhighered.com/assets/samplechapter/0/1/3/1/0131181637.pdf
After credit
Như trên mình có đề cập tới các queue tương ứng với trạng thái của thread. Để hiểu rõ hơn thì bài viết sau về chủ đề Vòng đời của thread trong OS. Cùng đón đọc nha.