Đèn báo hiệu (lập trình)

Trong lĩnh vực khoa học máy tính, đèn báo hiệu là một biến hoặc kiểu dữ liệu trừu tượng giúp kiểm soát truy cập vào tài nguyên chung giữa các tiến trình trong lập trình song song.

Đèn báo hiệu có thể được coi là một cơ chế ghi lại số lượng tài nguyên có sẵn và giúp điều chỉnh truy cập vào tài nguyên một cách an toàn, tránh xung đột (race condition). Nó có thể giúp ngăn chặn các vấn đề như xung đột truy cập và khóa chết, nhưng không đảm bảo hoàn toàn tránh được các vấn đề này. Đèn báo hiệu có thể đếm số lượng tài nguyên (counting semaphore) hoặc chỉ giới hạn trong giá trị 0 và 1 (binary semaphore).

Khái niệm đèn báo hiệu do nhà khoa học Edsger Dijkstra từ Hà Lan phát minh và đã được áp dụng rộng rãi trong nhiều hệ điều hành.

Ý nghĩa và cách cài đặt

Đèn báo đếm có hai thao tác chính, ký hiệu là V và P. Thao tác V tăng giá trị đèn báo S và thao tác P giảm giá trị này. Ý nghĩa chi tiết của chúng được mô tả dưới đây. Dấu ngoặc vuông thể hiện các thao tác nguyên tử, tức là các thao tác không thể bị gián đoạn bởi các tiến trình khác.

function V(semaphore S):
Tăng S một cách nguyên tử
[S ← S + 1]

function P(semaphore S):
repeat:
Trong khi lặp lại, các tiến trình khác có thể thao tác trên đèn báo
[if S > 0:
Giảm S một cách nguyên tử - lưu ý rằng S không thể âm
S ← S - 1
break]

Giá trị của đèn báo S biểu thị số lượng đơn vị tài nguyên có sẵn. Thao tác P chờ đợi cho đến khi tài nguyên được giải phóng, sau đó sẽ chiếm dụng nó. Ngược lại, thao tác V giải phóng tài nguyên khi tiến trình sử dụng đã hoàn thành.

Ví dụ: Bài toán sản xuất/tiêu thụ

Giả sử emptyCount và fullCount là các đèn báo đếm, trong đó emptyCount được khởi tạo với giá trị N và fullCount bằng 0, người sản xuất sẽ thực hiện các thao tác sau:

Sản xuất:
P(emptyCount)
Đặt hàng vào hàng đợi (putItemIntoQueue)
V(fullCount)

Người dùng thực hiện công việc này liên tục:

Tiêu thụ:
P(fullCount)
Lấy hàng từ hàng đợi (item ← getItemFromQueue)
V(emptyCount)

Lưu ý rằng thứ tự các thao tác là rất quan trọng. Ví dụ, nếu nhà sản xuất đặt hàng vào hàng đợi sau khi tăng fullCount, người dùng có thể cố lấy hàng trước khi nó được ghi. Nếu nhà sản xuất đặt hàng vào trước khi giảm emptyCount, nó có thể vượt quá giới hạn của hàng đợi.

Nguồn gốc tên của hàm

Các tên chuẩn P và V có nguồn gốc từ tiếng Hà Lan. V viết tắt cho từ 'verhogen' ('tăng lên'). Có nhiều cách hiểu cho P, bao gồm 'proberen' ('kiểm tra'), 'passeer' ('vượt qua'), 'probeer' ('thử'), và 'pakken' ('bắt'). Tuy nhiên, Dijkstra cho biết ông muốn sử dụng từ ghép 'prolaag', viết tắt của 'probeer te verlagen', nghĩa là 'thử giảm'.

Trong ALGOL 68, nhân Linux, và một số sách giáo khoa tiếng Anh, các thao tác P và V thường được gọi là down và up. Trong thực tế, chúng thường được gọi là wait và signal, acquire và release (Java chuẩn sử dụng cách này), hoặc pend và post. Một số sách sử dụng procure và vacate để phù hợp với viết tắt tiếng Hà Lan ban đầu.

Semaphore và mutex

Mutex về cơ bản giống như semaphore nhị phân và đôi khi được cài đặt theo cách tương tự. Tuy nhiên, 'mutex' thường được sử dụng để mô tả cấu trúc ngăn chặn hai tiến trình cùng thực thi một đoạn mã hoặc truy cập cùng dữ liệu. Khái niệm semaphore nhị phân thường dùng để hạn chế truy cập vào một tài nguyên.

Trong nhiều trường hợp, mutex có khái niệm 'chủ sở hữu': chỉ tiến trình nào khoá mutex mới có quyền mở nó. Ngược lại, semaphore nói chung không có giới hạn này, điều mà ví dụ người sản xuất - người tiêu dùng trên đây phụ thuộc vào.

Áp dụng

Các hệ điều hành thường cung cấp đèn báo như một mẫu để đồng bộ hóa, được sử dụng ở nhiều nơi. Tuy nhiên, xu hướng phát triển ngôn ngữ lập trình là sử dụng các phương pháp đồng bộ hóa có cấu trúc hơn như monitor. Các trừu tượng này thường chứa đèn báo hoặc mutex bên trong nhưng không hiển thị giao diện đèn báo cho lập trình viên. Xu hướng này giúp hạn chế những vấn đề nghiêm trọng và khó chẩn đoán khi đèn báo bị sử dụng sai cách, một nguy cơ được giảm bớt khi đồng bộ hóa được liên kết chặt chẽ với tài nguyên nó điều khiển một cách tự động bởi ngôn ngữ thay vì bằng tay bởi lập trình viên.

• Vấn đề Bữa ăn của các triết gia

Ghi chú

• Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Khái niệm Hệ điều hành (ấn bản 8), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5

Liên kết ngoài

• Về Seinpalen (EWD 74), nơi Dijkstra giới thiệu khái niệm này (bằng tiếng Hà Lan)
• giao diện lập trình semaphore.h - Các Tiêu chuẩn Cơ sở của Tập đoàn Open, Số hiệu IEEE 1003.1
• Cuốn sách nhỏ về Semaphores, của Allen B. Downey
• Khảo sát thực tiễn và có định hướng lịch sử về tính phổ quát của các nguyên thủy đồng bộ hóa Lưu trữ 2011-07-17 tại Wayback Machine, bởi Jouni Leppäjärvi