Traffic light (informatics)

A semaphore is a special variable (or abstract data type) that is the classical method of restricting or allowing access to shared resources (for example, a system storage resource or system variables). source code) in a multiprocessing environment (in which several processes will be running concurrently). They were invented by Edsger Dijkstra in 1965 and were first used in the operating system THEOS^{[citation needed]}.

Library analogy

Suppose a library has 10 identical study rooms, to be used by one student at a time. Students must request a room at reception if they wish to use a study lounge. If there are no free rooms, students wait at the counter until someone gives up a room. When a student has finished using a room, the student must return to the counter and indicate that a room is free.

In the simplest implementation, the front desk clerk only knows the number of free rooms available, which they only know correctly if all students actually use their room as long as they've checked in and return them when they're done. When a student requests a room, the receptionist decreases this number. When a student frees a room, the receptionist increases this number. The room can be used for as long as you want, so it is not possible to reserve rooms in advance.

In this scenario, the reception counter represents a counting semaphore, the rooms are the resource, and the students represent processes/threads. The value of the semaphore in this scenario is initially 10, with all rooms empty. When a student requests a room, they are granted access and the semaphore value is changed to 9. After the next student arrives, it is reduced to 8, then 7, and so on. If someone requests a room and the current value of the semaphore is 0, they are forced to wait until a room is released (when the count increases from 0). If one of the rooms has been vacated, but there are multiple students waiting, then any method can be used to select who will occupy the room (such as FIFO or flipping a coin). And, of course, a student should inform the receptionist about releasing her room only after actually leaving her; otherwise, there may be an awkward situation where said student is in the process of leaving the room (she is putting away her textbooks, etc.) and another student enters the room before she leaves.

Operations

Semaphores can only be manipulated using the following operations (this is the hot-wait code):

Start(Semaphor s, Entero v)
{
S = v;
!

Which will initialize the semaphore variable s to an integer value v.

P(Semaforo s)
{
if(s/2003/0)
s = s-1;
else
wait();
!

Which will keep the one governed by the traffic light on standby if it has a value less than or equal to null.

V(Semaphorus s)
{
if(!processes_blocked)
s = s+1;
else
signal();
!

These instructions can be modified to avoid active waiting, making the operation P sleep the same process that executes it if it cannot decrement the value, while the operation V wakes up a process that is not the one that executes it. In a more understandable pseudo-language, the P operation is often called "wait" or "wait" and operation V "signal" or "signal".

The reason for the names of these functions, V and P, have their origin in the Dutch language. "Verhogen" means to increase and "Try" try, although Dijkstra used the made-up word prolaag [1], which is a combination of probeer te verlagen (try to decrease). The value of the semaphore is the number of units of the resource that are available (if there is only one resource, a "binary semaphore" whose initial value is 1 is used).

Value verification and modification, as well as the possibility of going to sleep (locking) are done together, as a single and indivisible atomic action. The operating system guarantees that when starting an operation with a semaphore, no other process can access the semaphore until the operation is terminated or blocked. This atomicity is absolutely essential to solve synchronization problems and avoid race conditions.

If there are n resources, the semaphore will be initialized to number n. Thus, each process, when requesting a resource, will verify that the value of the semaphore is greater than 0; If so, there are free resources, then it will hoard the resource and decrease the value of the semaphore.

When the semaphore reaches the value 0, it means that all the resources are being used, and the processes that want to request a resource must wait for the semaphore to be positive, that is: one of the processes that are using the resources will have done with it and increment the semaphore with a signal or V(s).

Start is used to initialize the semaphore before requests are made to it, and takes an integer as its argument. The P operation, when a resource is not available, stops execution by waiting active (or sleeping) until the value of the semaphore is positive, in which case it is immediately reclaimed by decrementing it. V is the reverse operation: it makes a resource available after the process has finished using it. The operations P and V must be indivisible (or atomic), which means that each of the operations must not be interrupted in the middle of its execution.

The operation V is sometimes called up the semaphore (up) and the operation P is known also as lower the semaphore (down), and are also called signal and wait or drop and take.

To avoid active waiting, a semaphore may have an associated process queue (usually a FIFO queue). If a process performs a P operation on a semaphore that has a value of zero, the process is stopped and added to the semaphore queue. When another process increments the semaphore using the V operation and there are processes in the associated queue, one of them (the first one that entered a FIFO queue) is removed and its execution is resumed.

Applications

Semaphores are used to allow access to different parts of programs (called critical sections) where variables or resources that must be accessed in a special way are manipulated. Depending on the value with which they are initialized, more or fewer processes are allowed to use the resource simultaneously.

A simple type of semaphore is binary, which can take only the values 0 and 1. They are initialized to 1 and are used when only one process can access a resource at a time. They are essentially the same as mutexes. When the resource is available, a process accesses it and decreases the value of the semaphore with the P operation. The value then remains at 0, which means that if another process tries to decrease it, it has to wait. When the process that decremented the semaphore performs a V operation, some waiting process begins to use the resource.

To make two processes run in a predetermined sequence, a semaphore initialized to 0 can be used. The process that should run first in the sequence performs the V operation on the semaphore before the code that should be executed after the other process. This executes the P operation. If the second process in the sequence is scheduled to run before the other, doing P will sleep until the first process in the sequence goes through its V operation. This mode of use is called signaling (signaling), and is used for a process or thread to let another know that something has happened.

Example of use

Semaphores can be used for different purposes, including:

• Implement mutual exclusion closures or locks
• Barreras
• Allow a maximum of N threads (hylos) to access a resource, initializing the semaphore in N
• Notification. Starting the traffic light in 0 can be used for communication between threads about the availability of a resource

In the following example, n processes are created and executed that will try to enter their critical section every time they can, and they will always succeed one at a time, thanks to the use of the semaphore s initialized to 1. It has the same function than a lock.

number of processes */
variable semaphorus s; /* statement of the entire value semaphorous variable*/
Start (s,1) /* Start a semaphore of name s with value 1 */

void P (int i) {
while (cert) {
P(s) * In binary lights, the right thing is to put a P(s) before entering
the critical section, to restrict the use of this code region */
/* CRIC SECTION */
V(s) /* After the critical section, we put the traffic light back to 1 for another
process can use it */
* RESTO THE CODE */
!
!

int main() {
Start-processes(P(1), P(2),...,P(n));
!