2. What is semaphore? What are the possible states? When it comes to a semaphore

Question

Explanation / Answer

A semaphore in its most basic form, is a protected integer variable that can facilitate and restrict access to shared resources in a multi-processing environment. The two most common kinds of semaphores are counting semaphores and binary semaphores. Counting semaphores represent multiple resources, while binary semaphores, as the name implies, represents two possible states (generally 0 or 1; locked or unlocked). Semaphores were invented by the late Edsger Dijkstra. Semaphores can be looked at as a representation of a limited number of resources, like seating capacity at a restaurant. If a restaurant has a capacity of 50 people and nobody is there, the semaphore would be initialized to 50. As each person arrives at the restaurant, they cause the seating capacity to decrease, so the semaphore in turn is decremented. When the maximum capacity is reached, the semaphore will be at zero, and nobody else will be able to enter the restaurant. Instead the hopeful restaurant goers must wait until someone is done with the resource, or in this analogy, done eating. When a patron leaves, the semaphore is incremented and the resource becomes available again. A semaphore can only be accessed using the following operations: wait() and release(). wait() is called when a process wants access to a resource. This would be equivalent to the arriving customer trying to get an open table. If there is an open table, or the semaphore is greater than zero, then he can take that resource and sit at the table. If there is no open table and the semaphore is zero, that process must wait until it becomes available. signal() is called when a process is done using a resource, or when the patron is finished with his meal. The following is an implementation of this counting semaphore (where the value can be greater than 1): wait(Semaphore s){ while (s==0); /* wait until s>0 */ s=s-1; } signal(Semaphore s){ s=s+1; } Historically, wait() was called P (for Dutch “Proberen” meaning to test) and signal() was called V (for Dutch “Verhogen” meaning to increment). The standard Java library instead uses the name "acquire" for P and "release" for V. No other process can access the semaphore when P or V are executing. This is implemented with hardware and code executing in this way, without interruption, is said to be running atomically. If there is only one count of a resource, a binary semaphore is used which can only have the values of 0 or 1. They are often used as mutex locks. Here is an implementation of mutual-exclusion using binary semaphores: do { wait(s); // critical section signal(s); // remainder section } while(1); In this implementation, a process wanting to enter its critical section it has to acquire the binary semaphore which will then give it mutual exclusion until it signals that it is done. ATOMIC OPERATION An operation during which a processor can simultaneously read a location and write it in the same bus operation. This prevents any other processor or I/O device from writing or reading memory until the operation is complete. Atomic implies indivisibility and irreducibility, so an atomic operation must be performed entirely or not performed at all. Init(Semaphore s; Int v){ s=v; }

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.