Semaphore (tin học)

Semaphore là một biến được bảo vệ (hay là một kiểu dữ liệu trừu tượng), tạo thành một phương pháp để hạn chế truy nhập tới tài nguyên dùng chung trong môi trường đa chương (multiprogramming). Đây là một phát minh của Edsger Dijkstra và được sử dụng lần đâu tiên trong hệ điều hành THE.
Giá trị của semaphore được khởi tạo bằng số các tài nguyên tương đương được chia sẻ cái mà cài đặt điều khiển. Trong trường hợp đặc biệt, khi mà chỉ có một tài nguyên tương đương được chia sẻ, semaphore được gọi là semaphore nhị phân. Trong trường hợp khái quát, semaphore thường được gọi là biến đếm semaphore.
Semaphore là lời giải kinh điển cho bài toán bữa tối của các triết gia (dining philosophers), mặc dù nó không ngăn được hết các deadlock.

Giới thiệu

Semaphore chỉ có thể được truy nhập bằng cách sử dụng các toán tử sau
P(Semaphore s)
{
  chờ cho đến khi s > 0, rồi s:= s-1;
  /* phải là toán tử nguyên tố (không bị chia cắt) một khi phát hiện được s > 0 */
}

V(Semaphore s)
{
  s:= s+1;   /* phải là toán tử nguyên tố */
}

Init(Semaphore s, Integer v)
{
  s:= v;
}
Chú ý rằng việc tăng biến s không thể bị gián đoạn, và toán tử P cũng không được gián đoạn sau khi nhận ra biến s có giá trị khác 0. Điều này có thể được thực hiện bằng cách sử dụng một lệnh đặc biệt như test-and-set (kiểm tra và thiết lập) nếu tập lệnh của kiến trúc máy hiện hành hỗ trợ nó, hoặc bằng cách bỏ qua các ngắt để ngăn tiến trình khác kích hoạt (đối với các hệ thống chỉ có 1 bộ vi xử lý).
Các cái tên kinh điển P và V xuất phát từ tiếng Hà Lan. Chữ V trong verhoog nghĩa là "tăng". Một vài lời giải thích đưa ra cho chữ P (bao gồm passeer có nghĩa là "vượt qua", probeer có nghĩa là thử, và pakken với nghĩa "nắm lấy"), nhưng thực ra Dijkstra viết rằng ông dùng P để đại diện cho từ tự tạo portmanteau prolaag, là viết tắt của probeer te verlagen, hay "kiểm-tra-để-giảm".This
Giá trị của một semaphore là số đơn vị tài nguyên đang ở trạng thái rỗi. (Nếu chỉ có một tài nguyên, người ta sẽ sử dụng một "semaphore nhị phân" với các giá trị 0 và 1.) Toán tử P đợi (busy waiting) hoặc đang ngủ cho đến khi một tài nguyên hết bận, khi đó, nó lập tức chiếm quyền sử dụng tài nguyên đó. V là toán tử đảo ngược; nó thả một tài nguyên sau khi tiến trình đã sử dụng xong tài nguyên đó. Init chỉ được dùng để khởi tạo semaphore trước tất cả các yêu cầu sử dụng nào. Các toán tử P và V phải có tính chất nguyên tố, nghĩa là không có tiến trình nào có thể chặn giữa quá trình thực hiện một trong các toán tử này để chạy một toán tử khác trên cùng một semaphore đó.
Trong các sách giáo trình tiếng Anh, và trong ngôn ngữ lập trình ALGOL 68, các toán tử P và V thường được gọi lần lượt là down và up. Trong các tài liệu công nghệ phần mềm, các toán tử này được gọi là wait (đợi) và signal (đánh tín hiệu), hoặc take (lấy) và release (thả), hoặc pend (giữ) và post (công bố).
Để tránh tình trạng busy-waiting, một semaphore có thể có một cấu trúc hàng đợi gồm các tiến trình. Nếu một tiến trình thực hiện một thao tác P đối với một semaphore có giá trị 0, tiến trình này được đưa vào hàng đợi của semaphore. Khi một tiến trình khác dùng toán tử V để tăng giá trị của semaphore, và có tiến trình nằm trong hàng đợi, thì một tiến trình trong đó được lấy ra khỏi hàng đợi và tiếp tục chạy.

Ứng dụng semaphore hiện nay

Semaphores còn được sử dụng phổ biến trong các ngôn ngữ lập trình - những ngôn ngữ mà về bản chất không hỗ trợ những dạng khác của sự đồng bộ hóa. Chúng cũng được sử dụng trong các kĩ thuật đồng bộ ban đầu như trong các hệ điều hành. Xu hướng trong sự phát triển của ngôn ngữ lập trình, dường như là hướng vào các dạng cấu trúc đồng bộ hóa, giống như đồng bộ hóa các kênh. Cộng thêm sự không đầy đủ trong cách phân chia với deadlock, semaphore không bảo vệ người lập trình khỏi các lỗi đơn giản trong việc lấy một semaphore - cái mà luôn luôn được thay đổi bởi các tiến trình đồng thời, và cũng quên giải phóng semaphore sau khi lấy ra.