Semaphore (tin học)
Bách khoa toàn thư mở Wikipedia
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 lập trình (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.
Mục lục |
[sửa] Giới thiệu
Semaphores chỉ có thể được truy nhập bằng cách sử dụng toán tử sau
P(Semaphore s)
{
trong khi chờ s > 0 thì s := s-1;
/* phải là nguyên tố s > 0 được nhận */
}
V(Semaphore s)
{
s := s+1; /* must be atomic */
}
Init(Semaphore s, Integer v)
{
s := v;
}
Chú ý rằng việc tăng biến s không phải là một ngắt và toán tử P cũng không phải là một ngắt sau khi biến s nhận 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 câu lệnh đặc biệt như là kiểm tra và thiết lập (nếu tập lệnh của kiến trúc) 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.
Các tên kinh điển P và V vốn là viết tắt của Hà Lan. Chữ V đứng 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ử)
The canonical names P and V come from the initials of Dutch words. V stands for verhoog, or "increase." Several explanations have been given for P (including passeer "pass", probeer "try", and pakken "grab"), but in fact Dijkstra wrote that he intended P to stand for the made-up portmanteau word prolaag,[1] short for probeer te verlagen, or "try-and-decrease".[2][3] (A less ambiguous English translation would be "try-to-decrease.") This confusion stems from the unfortunate characteristic of the Dutch language that the words for increase and decrease both begin with the letter V, and the words spelled out in full would be impossibly confusing for non–Dutch-speakers.
The value of a semaphore is the number of units of the resource which are free. (If there is only one resource, a "binary semaphore" with values 0 or 1 is used.) The P operation busy-waits (or maybe sleeps) until a resource is available, whereupon it immediately claims one. V is the inverse; it simply makes a resource available again after the process has finished using it. Init is only used to initialize the semaphore before any requests are made. The P and V operations must be atomic, which means that no process may ever be preempted in the middle of one of those operations to run another operation on the same semaphore.
In English textbooks, and in the programming language ALGOL 68, the P and V operations are sometimes called, respectively, down and up. In software engineering practice they are called wait and signal, or take and release, or pend and post.
To avoid busy-waiting, a semaphore may have an associated queue of processes (usually a FIFO). If a process performs a P operation on a semaphore which has the value zero, the process is added to the semaphore's queue. When another process increments the semaphore by performing a V operation, and there are processes on the queue, one of them is removed from the queue and resumes execution.
[sửa] Ứ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.
[sửa] Ví dụ sử dụng
Since semaphores can have a count associated with them, they are usually made use of when multiple threads cooperatively need to achieve an objective. Consider this example:
- We have a thread A that needs information from two databases, before it can proceed. Access to these databases is controlled by two separate threads B, C. These two threads have a message-processing loop; anybody needing their use posts a message into their message queue. Thread A initializes a semaphore S with
init(S,-1). A then posts a data request, including a pointer to the semaphore S, to both B and C. Then A callsP(S), which blocks. The other two threads meanwhile take their time obtaining the information; when each thread finishes obtaining the information, it callsV(S)on the passed semaphore. Only after both threads have completed will the semaphore's value be positive and A be able to continue. A semaphore used in this way is called a "counting semaphore."
Apart from a counting semaphore we also have a "blocking semaphore". A blocking semaphore is a semaphore that is initialized to zero. This has the effect that any thread that does a P(S) will block until another thread does a V(S). This kind of construct is very useful when the order of execution among threads needs to be controlled.
The simplest kind of semaphore is the "binary semaphore", used to control access to a single resource, which is essentially the same as a mutex. A binary semaphore is always initialized with the value 1. When the resource is in use, the accessing thread calls P(S) to decrease this value to 0, and restores it to 1 with the V operation when the resource is ready to be freed.
[sửa] Xem thêm
- Cigarette smokers problem
- Dining philosophers problem
- Readers-writers problem
- Sleeping barber problem
[sửa] Liên kết ngoài
- semaphore.h programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
- A simple in-process semaphore using C#
- J2SE class
- Python Semaphore Objects
- Inter-Process Communication Tutorial
- Citations from CiteSeer
- Description from the Portland Pattern Repository
- The Little Book of Semaphores by Allen B. Downey
