Hệ điều hành: Process
operation system
1
White

kiennt viết ngày 03/10/2016

Mở đầu

Tôi đang học về Distributed System (hệ thống phân tán). Đây là một lĩnh vực rất hay và khó (đối với tôi). Phần lớn các hệ thống máy tính hiện nay đều được xây dựng trên nền tảng Distributed System. Một trong những yêu cầu để tham gia khoá học về Distributed System đó là phải hiểu rõ về Operating System (hệ điều hành). Điều này hợp lý vì các bài toán của Distributed System đều liên quan tới các bài toán của Operating System nhưng với điều kiện là các tài nguyên nằm ở trên nhiều máy, phân tán với nhau. Ví dụ: một hệ thống Map Reduce sẽ cần có một phần điều phối việc sử dụng tài nguyên (tính toán và lưu trữ), việc điều phối này cũng giống như Scheduler điều phối các Process trên OS. Hệ thống MapReduce cũng sẽ cần có một hệ thống File System để lưu giữ kết quả. Việc xây dựng hệ thống file phân tán (Distributed File System), có khá nhiều điểm giống với việc xây dựng hệ thống file trên OS. Hệ thống phân tán cũng phải giải quyết vấn đề tranh chấp tài nguyên giữa các node, giống như vấn đề tranh chấp dữ liệu/resource của các thread trên OS, mà giải pháp thường là xây dựng một cơ chế locking hiệu quả.

Bài viết này là bài viết đầu tiên trong chuỗi bài về Hệ điều hành mà tôi muốn giới thiệu. Nội dung trong chuối bài được tổng hợp chủ yếu từ cuốn Operating System Concepts Essentials, Second Edition. Nội dung trong bài viết này phần lớn lấy từ chương 3 (Process) và chương 5 (Scheduling) trong sách.

Cách đây hơn 1 năm, tôi có public bài viết về Unix Process, bài viết lần này, tôi muốn tập trung nói tới hai vấn đề: Cách hệ điều hành lưu trữ một Process, và cách các Process nói chuyện với nhau

OS tổ chức Process bằng cách nào?

Mỗi một process được tạo ra bằng lệnh fork từ Process cha. Các process là các thực thể độc lập với nhau, về không gian bộ nhớ, về các tập lệnh của từng Process. Một chương trình (executable program) có thể được chạy nhiều lần, sẽ tạo ra nhiều process khác nhau. Do các process là được phân tách với nhau, nên nếu một process bị crash, thì nó cũng không ảnh hưởng tới process khác (điều này có làm bạn nhớ tới thư viện resque không?)

Một hệ điều hành nếu cho phép nhiều processes được chạy cùng một lúc được gọi là hệ điều hành đa nhiệm. Các hệ điều hành hiện nay, từ mobile cho tới desktop, rồi server đều là các hệ điều hành đa nhiệm. Hệ điều hành đa nhiệm sẽ cho phép rất nhiều Process được chạy cùng với nhau. Ví dụ: trên laptop của bạn hiện giờ, bạn có thể vừa mở slack, vào room #hardcore, vừa mở chrome để đọc bài viết này. Tuy nhiên mỗi một máy tính lại có CPU với số nhân hữu hạn. Thế nên để có thể phân chia thời gian các process sử dụng CPU, hệ điều hành sẽ cần có một cơ chế để điều phối các process này. Thuật toán điều phối process được gọi là thuật toán scheduling, chương trình trong OS để điều phối được gọi là scheduler.

Vậy OS tổ chức các Process như thế nào? Mỗi một process sẽ được biểu diễn bằng một PCB (Process Control Block) trong kernel của OS. Một PCB là một cấu trúc dữ liệu sẽ bao gồm các thông tin sau

  • id của process
  • trạng thái của process (mới khởi tạo, sẵn sàng chạy, đang đợi, ...)
  • các thông tin về scheduling cho process này (VD: độ ưu tiên của process, con trỏ tới scheduling queues ...)
  • thông tin về không gian bộ nhớ của process (để map lên bộ nhớ vật lý của máy, mỗi process là isolate với nhau, nên OS cần lưu trữ thông tin này)
  • các thông tin về con trỏ của chương trình trong process
  • thông tin về các thanh ghi của CPU đối với process này
  • các file descriptors mà Process đang sử dụng

Với những thông tin kể trên, khi process cha fork ra một process con, một PCB sẽ được tạo ra cho Process con. Đối với hệ điều hành Linux, do process con được sử dụng chung các file descriptors với process cha, nên OS sẽ copy con trỏ của list các file descriptors của process cha sang process con.

Việc điều phối các process sẽ bao gồm, việc ngừng process hiện tại lại, lưu lại trạng thái của process này, lựa chọn process tiếp theo sẽ được chạy, load trạng thái của process tiếp theo đó lên, rồi chạy tiếp process tiếp theo. Quá trình này được gọi là Context Switch. Context Switch đôi khi phải phụ thuộc vào phần cứng (ví dụ việc lưu trữ lại trạng thái các thanh ghi mà process đang thực hiện). Context Switch là công việc tốn thời gian (trong bản thân kernel). Đây chính là lý do vì sao bạn thấy rất nhiều bài báo nói về việc sử dụng multithread để handle request trên máy chủ linux có hiệu năng không tốt bằng sử dụng eventloop (trên Linux, thread cũng được lưu trữ bằng một PCB như process).

Có nhiều loại scheduler khác nhau. short-term scheduler là scheduler được chạy thường xuyên,
short-term scheduler sẽ lấy trực tiếp các process trong kernel, và điều phối. long-term scheduler chạy ít thường xuyên hơn, trong hệ thống xử lý batch, hoặc một hệ thống phân tán, khi số lượng task quá lớn, một phần các task sẽ được đẩy xuống lưu trữ ở tầng storage, long-term scheduler sẽ định lý lấy ra các task, load task vào bộ nhớ và điều phối.

Có hai cách để thiết kế thuật toán điều phối các process:

  • cooperative: một process sẽ được sử dụng CPU cho tới khi nó yield quyền sử dụng của nó. Khi đó scheduler sẽ lựa chọn process tiếp theo trong hàng đợi để chạy. yield sẽ được gọi khi Process gọi tới một system call nhất định. Dễ thấy nhất là khi Process gọi tới một lời gọi về IO. Với thuật toán này OS hoàn toàn tin tưởng Process về việc điều phối. Một process sẽ được chạy mãi cho tới khi nó chịu từ bỏ. Cách điều phối cooperative khá là dễ để cài đặt, nhưng cũng dẫn tới việc các process sẽ không được điều phối một cách công bằng.

(nếu bạn nào muốn tìm hiểu chi tiết hơn về thuật toán điêu phối cooperative, có thể đọc thêm bài viết của tôi về cách thư viện asynq sử dụng coroutine để điều phối request. coroutine thực chất là một cách implement process ở user space thay vì kernel space)

  • preemtive: hệ điều hành không tin tưởng vào process hoàn toàn nữa, mà đưa ra một cơ chế riêng, công bằng hơn để điều phối. Một thuật toán điều phối đơn giản là: mỗi một process sẽ được cho phép sử dụng CPU trong một khoảng thời gian, khi hết thời gian này, OS sẽ ngắt process khỏi CPU và chuyển quyền sử dụng sang process khác. Để cài đặt thuật toán preemptive gặp khá nhiều vấn đề trong thực tế. Cụ thể, nếu 2 process cùng sử dụng chung tài nguyên thì sẽ xảy ra tình trạng tranh cháp tài nguyên giữa 2 process này, vậy việc xử lý tranh chấp nên do OS xử lý hay là bản thân mỗi process xử lý. Hay nếu một process đang gọi tới 1 system call của kernel, ví dụ gọi tới 1 IO action, và phải đẩy vào hàng đợi IO, trước khi kịp đẩy vào hàng đợi IO, process lại bị hết thời gian chạy, kernel lại phải đẩy process vào hàng đợi khác, vậy lúc đó process sẽ nằm ở hàng đợi nào...Chi tiết về các thuật toán điều phối preemtive tôi xin dừng lại ở đây, hẹn các bạn ở bài viết kế tiếp.

Nhân nói về thuật toán điều phối, tôi cũng muốn đặt một câu hỏi mở cho các bạn: Với những ngôn ngữ có implement các process ở user space như Go (với goroutine), Erlang (với actor process), các ngôn ngữ này sẽ cần một scheduler như nào? nó là scheduler dạng cooperative hay preemtive?

Tương tác giữa các Process (IPC - inter process communication)

Khi các process chạy cùng nhau trong hệ điều hành, chúng sẽ nảy sinh nhu cầu tương tác với nhau, hoặc tương tác với các process khác trên máy khác (hệ thống phân tán được xây dựng trên việc tương tác giữa các process trên máy khác nhau). Có hai cơ chế chính để hai process tương tác với nhau

shared memory

Các process sử dụng chung một vùng không gian nhớ chung. Việc tương tác giữa hai process sẽ hoàn toàn do việc đọc/ghi trên vùng nhớ chung này. OS không hề can thiệp vào quá trình này, thế nên shared memory là phương pháp nhanh nhất (nhanh về mặt tốc độ) để các process nói chuyện với nhau. Tuy nhiên, nhược điểm của phương pháp này là các process phải tự quản lý việc đọc ghi dữ liệu, và quản lý việc tranh chấp tài nguyên.

Điều gì sẽ xảy ra nếu cả 2 processes cùng ghi vào vùng nhớ chung? Dữ liêu ghi sau sẽ đè lên dữ liệu ghi trước, và có thể dẫn đến sai lệch dữ liệu. Ngoài ra, khi sử dụng shared memory cũng cần tránh việc trỏ tới dữ liệu nằm ngoài vùng nhớ chung, vì không gian nhớ của các process là isolate với nhau.

Thông thường, tôi nghĩ cách tốt nhất để sử dụng shared memory là process cha, tạo ra vùng nhớ chung, rồi ghi dữ liệu vào đó. Các process con đơn thuần chỉ là đọc dữ liệu từ vùng nhớ chung.

message passing

Với message passing, một process có một hộp thư riêng (có thể là mailbox hoặc là port). Các process sẽ tương tác với nhau thông qua việc gửi message tới mailbox của process kia. Và việc này được thực hiện bằng một lời gọi tới system call.
Rõ ràng message passing là chậm hơn shared memory do cần phải có sự can thiệp của kernel, nhưng message passing an toàn và mềm dẻo hơn. Tuỳ vào hệ điều hành và thuật toán message passing mà bạn có thể có nhiều cách để truyền message.

Ví dụ sử dung pipe để làm message passing giữa process cha và con, hoặc sử dụng socket để truyền message giữa các process phân tán.

Đối với việc truyền message giữa hai process trên hai máy khác nhau, lại cần chú ý tới việc: làm sao sender biết được là message đã tới receiver? Nếu không thể biết được, vậy sender sẽ làm gì?
Ở đây có hai chiên thuật cho sender

  • at least one: sender sẽ cứ gửi message tới receiver cho tới khi receiver trả về một ACK cho sender.
  • at most one: khi sender gửi quá nhiều message, làm sao receiver đảm bảo là nó chỉ handle message đúng một lần? để đảm bảo điều này, mỗi message sẽ cần một id, và receiver cần lưu giữ lại danh sách những message nó đã gửi rồi. Nếu lưu giữ toàn bộ tất cả các message thì sẽ vố cùng tốn tài nguyên (về bộ nhớ, về thời gian xử lý), nên một thuật toán chấp nhận được, là receiver chỉ cần lưu giữ lại một tập các message đã được xử lý trong một khoảng thời gian, và kiểm tra xem message mà sender gửi lên đã được xử lý hay chưa).

Kết luận

Process là một trong những đơn vị cơ bản của hệ điều hành và hệ thống phân tán. Bài viết trình bày hai vấn đề cơ bản là các điều phối các processs, cũng như cách để tương tác giữa các process trong hệ điều hành. Hiểu rõ vễ process trong OS sẽ giúp việc tìm hiểu về hoạt động của process trong hệ thống phân tán dễ dàng hơn.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

kiennt

30 bài viết.
267 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
91 18
Mọi chuyện bắt đầu từ nắm 2013 trong quá trình xây dựng chức năng login với Facebook, tôi đã tìm ra một cách để tấn công vào các hệ thống login với...
kiennt viết 2 năm trước
91 18
White
50 4
Trong tuần vừa rồi, mình có đọc chương 7 cuốn sách (Link). Bài viết này nhằm mục đích giúp mình tổng hợp lại những kiến thức đã học được về chương ...
kiennt viết 2 tháng trước
50 4
White
29 5
1. Đặt vấn đề Một trong các vấn đề của một hệ thống backend là bài toán điều phối request tới các nguồn dữ liệu. Xét bài toán với một hệ thống bl...
kiennt viết gần 2 năm trước
29 5
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
30 bài viết.
267 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!