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,[1] là viết tắt của probeer te verlagen, hay "kiểm-tra-để-giảm".[2][3].
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.
Ví dụ sử dụng
Do semaphore có thể có con đếm, semaphore thường được dùng khi nhiều luồng (thread) cùng cần đạt được một mục tiêu. Xét ví dụ nếu ta có một luồng A cần thông tin từ hai cơ sở dữ liệu, trước khi nó có thể tiến hành truy nhập, Quyền truy nhập các cơ sở dữ liệu này đang được điều khiển bởi hai luồng riêng biệt B và C. Hai luồng này có một vòng lặp xử lý thông điệp (message-processing loop); ai cần đến chúng sẽ gửi một thông điệp vào hàng đợi thông điệp của chúng. Luồng A khởi tạo một semaphore S với lệnh init(S,-1). Sau đó A gửi một yêu cầu dữ liệu tới cả B và C, kèm theo một con trỏ tới semaphore S. Tiếp theo, A gọi P(S), lệnh này chặn (block) A lại. Trong lúc đó, hai luồng kia tiếp tục lấy thông tin; khi mỗi luồng lấy thông tin xong, nó gọi V(S) đối với semaphore được truyền. Chỉ sau khi cả hai luồng đã hoàn thành, semaphore mới đạt giá trị dương và A mới có thể chạy tiếp. Một semaphore được sử dụng kiểu này được gọi là một "semaphore đếm" (counting semaphore).
Bên cạnh semaphore đếm, ta còn có "semaphore chặn" (blocking semaphore). Đó là loại semaphore được khởi tạo tại giá trị 0. Điều này có hiệu quả là bất cứ luồng nào gọi P(S) sẽ bị chặn cho đến khi một luồng khác chạy V(S). Loại cấu trúc này rất hữu dụng khi cần điều khiển thứ tự thực thi giữa các luồng.
Loại semaphore đơn giản nhất là "semaphore nhị phân", được dùng để điều khiển truy nhập tới một tài nguyên duy nhất, loại này về bản chất không khác mutex. Semaphore nhị phân thường được khởi tạo tại giá trị 1. Khi tài nguyên đang được sử dụng, luồng truy nhập gọi P(S) để giảm giá trị của nó về 0, và khôi phục giá trị 1 bằng toán tử V khi tài nguyên sẵn sàng được thả ra.
Xem thêm
Tham khảo
Liên kết ngoài
