Hoàng Anh's Blog

Hệ điều hành (Part 5): CPU Synchronization

Ngày đăng: 2026-04-17

Lời mở đầu

Trong hệ điều hành đa chương thì sẽ có rất nhiều Process chạy cùng lúc (Concurrently). Chúng có thể phối hợp và chia sẻ dữ liệu với nhau để thực thi hiệu quả.

Các tiến trình phối hợp Cooperating Process này có thể ảnh hưởng hoặc bị ảnh hưởng bởi các tiến trình khác trong hệ thống. Chúng có thể chia sẻ tài nguyên một cách trực tiếp bằng cách dùng chung một vùng nhớ luận lý bao gồm code và cả data. Hoặc chúng sẽ truyền dữ liệu trung gian thông qua file hoặc các message.

Việc truy cập cùng lúc vào một tài nguyên dùng chung sẽ dẫn đến sự không nhất quán.

Producer-Consumer Problem

Hay còn gọi là bài toán Bounded-Buffer, là bài toán kinh điển trong đồng bộ hóa tiến trình liên quan đến sự không nhất quán nêu trên.

Đơn giản hóa: Một tiến trình sẽ cung cấp thông tin, một tiến trình sẽ tiêu thụ thông tin đó.

Để có thể cho chúng giao tiếp hiệu quả ta sẽ tạo ra một buffer of items đặt trong vùng nhớ dùng chung cho cả 2 tiến trình đó.

Ta sẽ đùng một biến số nguyên gọi là counter để theo dõi số lượng item trong buffer.

Cốt lõi của vấn đề:

Ví dụ: Cho counter = 5

Nếu cả hai cùng thao tác cập nhật biến đếm số lượng dữ liệu (Producer gọi counter++ và Consumer gọi counter-- cùng lúc), kết quả của biến đếm có thể bị sai lệch (ra 4 hoặc 6 thay vì 5).

Để giải quyết, chúng ta cần các công cụ đồng bộ hóa như Semaphore hoặc Monitor.

Critical-Section Problem

Một hệ thống sẽ có các Process khác nhau cùng chạy.

Mỗi Process sẽ có các phân đoạn code khác nhau trong nó. Và chúng đều sẽ có một phân đoạn code gọi là Critical Section.

Cấu trúc chung của một Process điển hình

Đây là phân đoạn mà trong đó các Process sẽ chứa các câu lệnh liên quan đến chỉnh sửa, thay đổi các giá trị tài nguyên chung như biến, files,...

Vấn đề cũng giống như bài toán Producer-Consumer nêu trên. Để giải quyết bài toán này thì ta cần phải đảm bảo ba tiêu chí sau:

  1. Mutual exclusion (Loại trừ tương hỗ)

    • Ý nghĩa: Khi một tiến trình đang thực thi các câu lệnh bên trong miền găng của nó, thì tuyệt đối không có bất kỳ tiến trình nào khác được phép thực thi trong miền găng của chúng.

    • Giải thích thực tế: Điều kiện này giống như một phòng vệ sinh chỉ có một buồng duy nhất. Khi một người đang ở bên trong và chốt cửa, tất cả những người khác bắt buộc phải đứng đợi ở ngoài cho đến khi người đó dùng xong.

  2. Progress (Tính tiến triển / Diễn tiến)

    • Ý nghĩa: Nếu miền găng đang trống (không có tiến trình nào đang dùng) và có một vài tiến trình đang muốn bước vào, thì chỉ những tiến trình không nằm trong "phần còn lại" (remainder section) mới được tham gia vào việc ra quyết định xem ai sẽ là người tiếp theo được vào. Quyết định này không được phép trì hoãn vô thời hạn.

  3. Bounded waiting (Chờ đợi có giới hạn)

    • Ý nghĩa: Phải có một giới hạn cụ thể về số lần các tiến trình khác được phép chen ngang vào miền găng tính từ lúc một tiến trình đã gửi yêu cầu xin vào cho đến khi yêu cầu đó được chấp nhận. Mỗi Process chỉ có số lần hữu hạn đi vào Critical Section.

    • Giải thích thực tế: Điều kiện này nhằm ngăn chặn tình trạng "chết đói tài nguyên" (Starvation). Ví dụ: Nếu tiến trình A đang xếp hàng đợi, thì các tiến trình B, C khác dù có độ ưu tiên cao cũng chỉ được phép vào miền găng một số lần nhất định. Sau số lần đó, bắt buộc phải nhường lượt cho tiến trình A để đảm bảo A không bị bắt đợi mãi mãi.

Giải pháp Semaphore

Đây là giải pháp được Edsger Dijkstra nghĩ ra nhằm giải quyết các vấn đề ở phía trên thông qua một số nguyên đơn giản gọi là Semaphore.

Semaphore là một biến số nguyên dùng để quản lý truy cập tài nguyên dùng chung, thông qua 2 thao tác nguyên tử automic operation là wait() và signal()

Định nghĩa thao tác wait() và signal()

Nói dễ hiểu thì khi bạn đi vệ sinh:

  1. Bạn sẽ chờ cửa mở (gọi hàm wait()).
  2. Kiểm tra xem cửa có mở hay không? (kiểm tra xem S có lớn hơn 0 hay không?).
  3. Sau khi cửa mở thì bạn ngừng chờ, đi vào và đóng cửa lại (giảm biến S đi một đơn vị).
  4. Sau khi bạn đi vệ sinh xong, bạn sẽ phát ra tính hiệu cho người khác chuẩn bị đi vào (gọi hàm signal()) và mở cửa (tăng biến S lên một đơn vị).

Có 2 loại Semaphore:

Áp dụng cho bài toán Producer-Consumer, ta sẽ sử dụng 3 Semaphore khác nhau:

  1. mutex (Binary Semaphore): Khởi tạo bằng 1, đóng vai trò như một chiếc "chìa khóa" khóa bộ đệm lại, đảm bảo tại một thời điểm chỉ có 1 người được truy cập vào bộ đệm.
  2. empty (Counting Semaphore): Khởi tạo bằng n, dùng để đếm số lượng chỗ trống trong bộ đệm.
  3. full (Counting Semaphore): Khởi tạo bằng 0, dùng để đếm số lượng chỗ đã có dữ liệu.
Áp dụng Semaphore giải quyết Producer-Consumer Problem

Hoạt động:

Và ngược lại bên Consumer cũng hoạt động tương tự.

Nhược điểm của Semaphore truyền thống là có thể gây ra tình trạng busy waiting (chờ bận) làm lãng phí CPU vì trong lúc chờ nó sẽ phải dùng vòng lặp while và thực hiện phép toán điều kiện để kiểm tra liên tục.

Tuy nhiên hệ điều hành có thể khắc phục bằng cách chặn (block) tiến trình này và đưa vào hàng đợi waiting thay vì bắt nó lặp liên tục.

Giải pháp Monitor

Monitor là một cấu trúc đồng bộ hóa cấp cao hơn, kết hợp giữa cơ chế loại trừ tương hỗ (mutual exclusion) và các biến điều kiện (condition variables). Khác với Semaphore buộc lập trình viên phải tự quản lý việc khóa/mở thủ công rất dễ lỗi, Monitor tự động đảm bảo chỉ có duy nhất một tiến trình được hoạt động bên trong nó tại một thời điểm.

1. Tính chất:

2. Cú pháp và điều kiện:

Cú pháp của Monitor

Quy tắc truy cập nghiêm ngặt: Các hàm (procedure) bên trong Monitor chỉ được phép sử dụng các biến được khai báo cục bộ bên trong Monitor đó.

Ngược lại, các biến bên trong Monitor chỉ có thể bị thay đổi bởi các hàm của chính Monitor đó. Các tiến trình bên ngoài không thể "chạm" trực tiếp vào dữ liệu này.

Biến điều kiện (Condition Construct): Đây là công cụ cốt lõi giúp Monitor điều phối các tiến trình. Khi khai báo một biến điều kiện (ví dụ: condition x, y;), ta chỉ có thể dùng 2 lệnh với nó:

3. Góc nhìn trực quan về Monitor:

Hình ảnh trực quan về Monitor

  1. Vòng tròn bao quanh (Khối Monitor): Nó đóng vai trò như một bức tường bảo vệ. Bất kỳ thứ gì nằm bên trong vòng tròn này đều được Monitor kiểm soát nghiêm ngặt.

  2. Các thành phần bên trong Monitor:

    • Shared data (Dữ liệu dùng chung): Nằm ở phía trên cùng bên trong Monitor. Đây là các biến, cấu trúc dữ liệu hoặc tài nguyên mà các tiến trình muốn truy cập chung. Các tiến trình bên ngoài tuyệt đối không thể truy cập trực tiếp vào các dữ liệu này.

    • Operations (Các thao tác/Thủ tục): Các khối hình chữ nhật đứng đại diện cho các hàm (functions/methods). Đây là "cửa ngõ" duy nhất để thao tác với shared data. Các tiến trình từ bên ngoài muốn dùng dữ liệu thì bắt buộc phải gọi các hàm này.

    • Initialization code (Mã khởi tạo): Phần dưới cùng chứa các đoạn code dùng để khởi tạo giá trị ban đầu cho các biến shared data khi Monitor vừa được tạo ra.

  3. Hai loại Hàng đợi (Queues): Đây là phần quan trọng nhất để hiểu cách Monitor đồng bộ hóa các tiến trình:

    • Entry queue (Hàng đợi đầu vào):

      • Vị trí: Nằm bên ngoài, chỉ mũi tên đi vào Monitor.

      • Chức năng: Vì Monitor chỉ cho phép 1 tiến trình chạy bên trong nó cùng lúc, nên nếu có nhiều tiến trình cùng lúc gọi các hàm operations, những tiến trình đến sau sẽ phải đứng xếp hàng chờ ở entry queue. Khi tiến trình đang chạy bên trong kết thúc và rời đi, một tiến trình trong entry queue mới được mở cửa cho vào.

    • Queues associated with x, y conditions (Hàng đợi gắn với biến điều kiện x, y):

      • Vị trí: Nằm bên trong Monitor, bên dưới phần shared data.

      • Chức năng: Giả sử một tiến trình đã qua được entry queue, đang chạy ngon lành bên trong Monitor, nhưng đột nhiên phát hiện ra nó chưa thể làm tiếp vì thiếu một điều kiện nào đó (ví dụ: muốn đọc file nhưng file chưa có dữ liệu).

      • Cách xử lý: Nếu nó cứ đứng lỳ ở đó chờ thì các tiến trình khác ở entry queue sẽ bị nghẽn mãi mãi. Do đó, tiến trình này sẽ gọi lệnh wait() để tự chuyển mình vào một trong các hàng đợi điều kiện (x hoặc y), đưa bản thân vào trạng thái ngủ và trả lại quyền truy cập Monitor cho người khác. Khi một tiến trình khác vào Monitor và tạo ra dữ liệu phù hợp, nó sẽ gọi lệnh signal() để đánh thức tiến trình đang ngủ ở hàng đợi x hoặc y kia dậy để chạy tiếp.

Tóm lại: Bạn có thể tưởng tượng Monitor giống như một trạm ATM có cửa bảo vệ.

4. Áp dụng vào giải quyết bài toán Producer-Consumer:

Đoạn code giải quyết bài toán

  1. Khai báo trạng thái:

    • buffer[n]: Kho chứa n sản phẩm.

    • full = 0: Biến đếm số sản phẩm hiện có (ban đầu kho trống = 0).

    • buffer_full và buffer_empty: Hai biến điều kiện để báo hiệu kho đầy/kho rỗng.

  2. Hàm produce_info() (Dành cho người sản xuất):

    • If (full == n) wait(buffer_empty);: Kiểm tra nếu kho đã đầy tràn (n món), Producer lập tức gọi wait() để đi ngủ, chờ đến khi kho rỗng bớt.

    • produce(); full++;: Nếu kho chưa đầy (hoặc vừa được đánh thức), tiến hành sản xuất 1 món và tăng biến đếm lên.

    • signal(buffer_full);: Sau khi tạo ra 1 món hàng mới, gọi signal() để đánh thức Consumer (nếu Consumer đang ngủ vì kho trống): "Có hàng rồi, dậy mua đi!".

  3. Hàm consume_info() (Dành cho người tiêu dùng):

    • if (full == 0) wait(buffer_full);: Kiểm tra nếu kho không có món nào (full = 0), Consumer lập tức gọi wait() để đi ngủ, chờ đến khi có hàng.

    • Consume(); full--;: Nếu có hàng, tiến hành lấy 1 món ra xài và giảm biến đếm đi.

    • signal(buffer_empty);: Sau khi lấy bớt 1 món, kho sẽ có chỗ trống. Gọi signal() để đánh thức Producer (nếu Producer đang ngủ vì kho đầy): "Có chỗ trống rồi, dậy sản xuất tiếp đi!".

  4. Khối code bên dưới cùng:

    • Hai khối Producer() và Consumer() bên ngoài chỉ việc chạy vòng lặp vô hạn while(true) và gọi các hàm của Monitor.
    • Nhờ cơ chế đóng gói và tự động khóa của Monitor, dữ liệu không bao giờ bị sai lệch dù hai bên có chạy nhanh chậm ra sao.

Tài liệu tham khảo


← Quay lại trang chủ