Semaphore (programming)
For other uses, see Semaphore.
In Computer Science, Semaphore is a protected variable or object data type, which constitutes the classic method governing access to shared resources, such as shared memory in a parallel programming environment. Counting Semaphore is not a closed / open flag of a single resource, but a counter of a group of available resources. It was invented by Edsger Dijkstra. There is a classic solution to prevent race conditions in the semining dining philisophers problems, although they do not stop resource barriers.
introduction
Access to semaphors is possible only by using the following functions. Those who have been marked as Atomic should not be interrupted (i.e., if the system has determined that the program is now "turn", then do not stop it in the middle of these instructions Should be explained), this is explained below.
P(Semaphore s) //Acquire Resource { wait until s > 0, then s := s-1; /* Testing and decrementing s must be atomic to avoid race conditions* / }
V(Semaphore s) //Release Resource { s := s+1; /*Must be atomic*/ }
Init (Semaphore s, Integer v) { s := v; }
Note that the increment of the variable s should not be interrupted and if the value of s is greater than 0, interference should not be generated in Work P. This is a special instruction, such as test-and-set (if the structure Can be done by ignoring the interrupts to prevent the activation of the other processes being activated by the use of the instructions group.)
The value of a semaphore equals the number of vacant units in the resource. (If there is only one resource, then a "binary semaphore" with 0 and 1 values is used.) Task P remains busy-waiting (uses its turn to do nothing) or perhaps by then Sleeps remain (tells the system not to give any turn), unless a resource is available and then immediately claims on a resource. V is the opposite; It only provides resources when the process is used by the process. Init is used for initialization only to make semaphore before any request is made. Work should be P and V atomic, which means that any process to perform any other work on the same semaphore should never be stopped between those tasks.
Formal names, the origin of P and V, are from the first letters of the Dutch words, V means verhogen, or "increase." P has been interpreted for various interpretations (proberen for "test", "passage (Pass, "" passeer "," attempt "," checker "and" catch "pakken), but in fact Dijkstra has written that his intention of P was to create the word-prolaag, which the probeer te verlagen, or" try-and- Is a short form of "try-and-decrease" (a less ambiguous and more accurate translation) Try this to be a "try-to-decrease". This confusion arises due to the fact that the words used for both increase and decrement in Dutch And the full form of these words will be impossible to be misleading to non-Dutch speakers.
In programming language ALGOL 68, functions in the Linux kernel and in some English textbooks, P and V are called, respectively, down and up. In the method of software engineering, they are often called wait and signal, or acquire and release (used in standard Java libraries), or pend and post. In some books, these are called procure and vacate to match the original Dutch initials.
In order to avoid busy-waiting, there may be an associated queue of processes in the semaphore (usually first-in, first-out). If a process performs a P function on such a semaphore If the value is zero, then this process is added to the semaphore cue. When another process enhances the semaphore by functioning V and the processes are present in the Q, one of them is removed from the Q and its implementation restarts. When the priorities of procedures are different, the Q can be placed in the order of priority, so that the highest priority process should be taken first by the Q. Congruence
Believe that the 'resources' are public toilets toilets and 'procedures' seeking access to toilets are those people who are standing in a queue and waiting for any toilets to be available, or they There are people who are already using toilets. A person sitting outside the toilet takes care of how many toilets are available at this time and who should go inside after this.
The number of empty toilets is the value of semaphores, which tells the number of available vacant resources (toilets). When a process (person) wants to access the toilet, the semaphore (in charge) will tell him that he has to wait in the queue or he can use toilets. If the toilet is empty then that person (process) receives access and the number of vacant toilets is reduced to 1 (P or down work). This means that the number of empty toilets has decreased to 1. If the number of empty toilets is 0, then the person (process) will have to wait in the queue till it becomes empty (i.e. the process will have to sleep till s). Once the person uses toilets (The process completes the work with a resource), the next person can use it. This means that the number of empty toilets has increased by 1 now (this is the same as calling V or up work). Now the value of s is greater than 0 and the person waiting is sleeping Process) can now access the toilet (resource).
The process of seeking available toilets (checking whether the resource is empty), updating the number of empty toilets (resources) and wait in line should not be interrupted by any other process. Atomic work is called.
This queue is a first-in first-out quote, which means that the first person standing in the queue will get the opportunity to use empty toilets first. However, if the person standing in another place in the queue used toilets Wants to do it immediately (if the priority of a process is high), then the queue can be arranged.
The concept of counting semaphore can be expanded by demanding more than one 'unit' from semaphore or returning it. Actually UNIX semaphore works like this. Modified P and V functions are operated as follows:
P(Semaphore s, integer howmany) { wait until s >= howmany; s:=s - howmany; /*must be atomic operation*/ }
V(Semaphore s, integer howmany) { s:=s + howmany; /*must be atomic*/ }
To understand why this is better than calling the simple version of P to 'howmany' times, consider the following problem. We assume that you have a pool of N resources Which we call a fixed size buffer. Possibly, you will want to use a counting semaphore to keep track of available buffers, which is initialized by N. When a process wants to allocate a buffer, so He calls P on the semaphore and receives a buffer. If no buffers are available, then a process waits until another process releases a buffer and calls V over the semaphore.
Believe that there are two processes, which want to get buffers K & lt; N and L & lt; N in such a way that K + L> is N. Its simple implementation will be that the first process calls the Simple Decrementing Variant to the K bar on the semaphore, and it will call the simple subtraction conversion of P by the second process to the semaphore L times. However, due to this method, the deadlock (Deadlock) can be generated: Imagine that the operating system allows the first process to be executed. Then, when the first process has only got control of Z buffers (such that Z In the modified version of semaphore, the first process will demand k buffers (or more purely, semaphore units), which will be received by an atomic function, after which NM units will remain in semaphore.Then the second process Will come, which will reduce the semaphore to NKL and since it is a negative number, so will wait. When the first process frees the buffers and increases the semaphore, then as soon as If the semaphore reaches 0, it means that L is available in the collection, the second process can start and all of its buffers can be received. It should be noted that the number of buffers available in the Semaphore Count collection is not necessary. Check the S & gt; = 0 condition twice and wait for it. It is necessary to guarantee that the various processes involved in the waiting list of semaphores should not interfere with each other's requests: a process does not change the calculation of the semaphore That is, unless it is the next process in Q. In the real implementation, this work is done without activating the waiting process for the intermediate stage. Semaphors used today by programmers Semaphore use is still popular in programming languages which do not internally support other forms of synchronization. They are the initial mechanism of synchronization in many operating systems. However, the inclination of development of programming languages is towards more structured forms of synchronization, such as monitors (though these advanced structures use semaphore in the background). In addition to their inadequacy to deal with the breakdown of the semester (multi-resources), the programmer does not save the mistakes made by a process that has already been taken by a process and forgot to release the semaphore that has been taken. Examples of experiment Since a calculation is associated with semaphores, so they can be used at a time when multiple threads need to meet together to achieve any purpose. Consider this example: There is a need to get information from two databases before a thread named A goes ahead. Access to these databases is controlled by two separate threads B and C. These two threads have a message-processing loop; Anyone who wants to use any of these databases, sends a message in the message queue of the related thread. Thread A initializes the semaphore by init (s, -1). Then A, sending a data request to B and C, involving a pointer to the semaphore S. A then calls P (S), which stops. During that time, the remaining two threads take the time needed for them to receive the information; When each thread completes the task of obtaining the information, then it calls the V (S) to the semaphore sent. Only after the completion of both threads the semaphore value will be positive and A will be able to move forward. Thus, the semaphore used to be called is called "Counting Semaphore". In addition to the counting semaphore, there is also a "blocking semaphore". Blocking semaphore is a semaphore, which is initialized with 0. The effect of this is that any thread that works on the semaphore, is blocked. Hardware support The use of semaphores generally requires hardware support to guarantee the aomicity of those tasks, which it requires. Computer machine languages of the computer typically include those instructions, which are specially The semaphore is prepared keeping in mind. These special instructions complete the Read-Modify-Write cycle in memory, which is not only uninterruptible, but also any other processor or input / output device By removing all the other works being done in the same location in memory. Special instructions guarantee that using them a semaphore method can test and alter any semaphore in single, atomic work. Binary semaphor versus muttex A mutex is a binary semaphore, which usually includes additional features like proprietary or priority inversion protection. Differences in mutex and semaphore are dependent on the operating system. Use of mutex is only intended to be done in mutual exclusion and binary semaphores are designed for use in both event notification and mutual exclusion. Also see them
wiki
Comments
Post a Comment