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

Trong khoa học máy tính, đèn báo là một biến được bảo vệ hoặc một kiểu dữ liệu trừu tượng tạo ra sự trừu tượng hoá đơn giản nhưng hữu dụng để kiểm soát truy cập của nhiều tiến trình đến một tài nguyên chung trong môi trường lập trình song song.

Một cách nhìn về đèn báo là một bản ghi có bao nhiêu đơn vị của một tài nguyên có thể sử dụng, gắn với các tác vụ điều chỉnh bản ghi đó một cách an toàn (nghĩa là không tạo ra race condition) khi yêu cầu hoặc giải phóng các đơn vị và đợi đến khi một đơn vị rảnh rỗi nếu cần. Đèn báo là một công cụ hữu ích để chống race condition và khoá chết, tuy nhiên việc sử dụng nó không đảm bảo rằng chương trình không gặp phải các vấn đề trên. Đèn báo cho phép một số lượng tuỳ ý tài nguyên gọi là đèn báo đếm (counting semaphore) trong khi đèn báo bị giới hạn trong giá trị 0 và 1 được gọi là đèn báo nhị phân (binary semaphores).

Khái niệm đèn báo được phát minh bởi nhà nghiên cứu người Hà Lan Edsger Dijkstra, and the concept has found widespread use in a variety of operating systems.

Library analogy

Suppose a library has 10 identical study rooms, intended to be used by one student at a time. To prevent disputes, students must request a room from the front counter if they wish to make use of a study room. When a student has finished using a room, the student must return to the counter and indicate that one room has become free. If no rooms are free, students wait at the counter until someone relinquishes a room.

Since the rooms are identical, the librarian at the front desk does not keep track of which room is occupied, only the number of free rooms available. When a student requests a room, the librarian decreases this number. When a student releases a room, the librarian increases this number. Once access to a room is granted, the room can be used for as long as desired, and so it is not possible to book rooms ahead of time.

In this scenario the front desk represents a semaphore, the rooms are the resources, and the students represent processes. The value of the semaphore is initially 10. When a student requests a room he is granted access and the value of the semaphore is changed to 9. After the next student comes, it drops to 8, then 7 and so on. If someone requests a room when it is 0, they are forced to wait. When multiple people are waiting, they will either wait in a queue, or use Round-robin scheduling and race back to the counter when someone releases a room (depending on the nature of the semaphore).

Important observations

When used for a pool of resources, a semaphore does not keep track of which of the resources are free, only how many there are. Some other mechanism (possibly involving more semaphores) may be required to select a particular free resource.

Processes are trusted to follow the protocol. Fairness and safety are likely to be compromised (which practically means a program may behave slowly, act erratically, hang or crash) if even a single process acts incorrectly. This includes:

• requesting a resource and forgetting to release it,
• releasing a resource that was never requested,
• holding a resource for a long time without needing it, or
• using a resource without requesting it first.

Even if all processes follow these rules, multi-resource deadlock may still occur when there are different resources managed by different semaphores and when processes need to use more than one resource at a time, as illustrated by the dining philosophers problem.

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

Đèn báo đếm được trang bị hai thao tác, kí hiệu là V và P. Thao tác V tăng đèn báo S và thao tác P giảm nó. Ý nghĩa của chúng được giải thích bên dưới. Ngoặc vuông chỉ ra các thao tác nguyên tử, nghĩa là các thao tác không thể chia nhỏ dưới góc nhìn của các tiến trình khác.

function V(semaphore S):
    Atomically increment S
    [S ← S + 1]

function P(semaphore S):
    repeat:
        Between repetitions of the loop other processes may operate on the semaphore
        [if S > 0:
            Atomically decrement S - note that S cannot become negative
            S ← S - 1
            break]

Giá trị của đèn báo S là số đơn vị của tài nguyên còn rỗi. Thao tác P chờ đợi tích cực hoặc ngủ cho đến khi tài nguyên được bảo vệ trở nên rảnh rỗi, khi đó nó ngay lập tức yêu cầu. Thao tác V ngược lại: làm cho tài nguyên rảnh rỗi trở lại sau khi một tiến trình đã sử dụng xong.

Many operating systems provide efficient semaphore primitives which mean that one waiting process is awoken when the semaphore is free. This means that processes do not waste time checking the semaphore value and context switching unnecessarily.

The counting semaphore concept can be extended with the ability to claim or return more than one "unit" from the semaphore. a technique implemented in UNIX. The modified V and P operations are as follows:

function V(semaphore S, integer I):
    [S ← S + I]

function P(semaphore S, integer I):
    repeat:
        [if S >= I:
            S ← S - I
            break]

To avoid starvation, a semaphore has an associated queue of processes (usually a first-in, first out). If a process performs a P operation on a semaphore that 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. When processes have different priorities the queue may be ordered by priority, so that the highest priority process is taken from the queue first.

If the implementation does not ensure atomicity of the increment, decrement and comparison operations, then there is a risk of increments or decrements being forgotten, or of the semaphore value becoming negative. Atomicity may be achieved by using a machine instruction that is able to read, modify and write the semaphore in a single operation. In the absence of such a hardware instruction, an atomic operation may be synthesized through the use of a software mutual exclusion algorithm. On uniprocessor systems, atomic operations can be ensured by temporarily suspending preemption or disabling hardware interrupts. This approach does not work on multiprocessor systems ở đó nó is possible for two programs sharing a semaphore to run on different processors at the same time. To solve this problem in a multiprocessor system a locking variable can be used to control access to the semaphore. The locking variable is manipulated using a test-and-set-lock (TSL) command.

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

In the Producer-consumer problem, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size N. Obviously the consumer has to wait for the producer to produce something if the queue is empty. Perhaps more subtly, the producer has to wait for the consumer to consume something if the buffer is full.

The problem is easily solved if we model the queue as a series of boxes which are either empty or full, and regard empty boxes as one type of resource and full boxes as another type of resource. The producer "removes" an empty box and then "creates" a full one, whilst the consumer does the reverse.

Cho emptyCount và fullCount là các đèn báo đém, và emptyCount được khởi tạo bằng N trong khi fullCount bằng 0, người sản xuất thực hiện lặp lại công việc sau:

produce:
    P(emptyCount)
    putItemIntoQueue(item)
    V(fullCount)

Người sử dụng lặp đi lặp lại công việc sau:

consume:
    P(fullCount)
    item ← getItemFromQueue()
    V(emptyCount)

Lưu ý rằng thứ tự các phép toán là quan trọng. Ví dụ, nếu người sản xuất đặt hàng vào hàng đợi sau khi tăng fullCount, người sử dụng có thể cố lấy hàng trước khi nó được ghi. Nếu người 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 hàm

Các tên chuẩn P và V xuất phát từ chữ cái đầu của từ tiếng Hà Lan. V là viết tắt của verhogen ("tăng lên"). Có nhiều giải thích cho P, bao gồm proberen - "kiểm tra", passeer - "vượt qua", probeer - "thử", and pakken for "bắt". Tuy nhiên, Dijkstra viết rằng ông định sử dụng từ ghép prolaag, viết tắt cho 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 and V thường được gọi lần lượt là down và up. Trong thực hành, chúng thường được gọi là wait và signal, acquire và release (thư viên chuẩn của Java sử dụng cách này), hoặc pend và post. Một vài cuốn sách sử dụng procure và vacate để phù hợp với viết tắt ban đầu bằng tiếng Hà Lan.

Đèn báo và mutex

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

Trong nhiều trường hợp một mutex có khái niệm "chủ": duy nhất tiến trình khoá mutex được quyền mở nó. Ngược lại đèn báo nói chung không đặt ra ràng buộc này, điều mà ví dụ người sản xuất - người tiêu dùng ở trên dựa vào.

Sử dụng

Bản mẫu:Refimprove section Đèn báo được nhiều hệ điều hành cung cấp như là một mẫu đồng bộ hoá và được sử dụng ở nhiều nơi. Tuy nhiên xu hướng phát triển các ngôn ngữ lập trình là các cách đồng bộ hoá có cấu trúc hơn, như là monitor. Những sự trừu tượng hoá này thường chứa đèn báo hoặc mutex bên trong những không thể hiện giao diện của đèn báo ra đối với lập trình viên. Xu hướng này được khuyến khích mở những vấn đề nghiêm trọng và khó chuẩn đoán khi đèn báo bị sử dụng không đúng cách, một nguy cơ được giảm thiểu rất nhiều khi sự đồng bộ hoá được gắn chặt với tài nguyên mà nó điều khiển một cách tự động bởi ngôn ngữ thay vì bằng tay bởi người lập trình.

Xem thêm

• Cigarette smokers problem
• Bài toán Bữa ăn của triết gia
• Readers-writers problem
• Sleeping barber problem
• Producers-consumers problem
• Mutex
• Reentrant mutex, which can "count" but in a different manner to a counting semaphore.

Ghi chú và tham khảo

• Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (ấn bản 8), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5 

Liên kết ngoài

• Over Seinpalen (EWD 74), in which Dijkstra introduces the concept (in Dutch)
• semaphore.h programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
• The Little Book of Semaphores, by Allen B. Downey
• A pragmatic, historically oriented survey on the universality of synchronization primitives, by Jouni Leppäjärvi