Semaphore

12 Key excerpts on "Semaphore"

• 

  eBook - ePub

  Beginning Linux Programming

  • Neil Matthew, Richard Stones(Authors)
  • 2011(Publication Date)
  • Wrox

    (Publisher)

  An important step forward in this area of concurrent programming occurred when Edsger Dijkstra, a Dutch computer scientist, introduced the concept of the Semaphore. As briefly mentioned in Chapter 12, a Semaphore is a special variable that takes only whole positive numbers and upon which programs can only act atomically. In this chapter we expand on that earlier simplified definition. We show in more detail how Semaphores function, and how the more general-purpose functions can be used between separate processes, rather than the special case of multi-threaded programs you saw in Chapter 12.

  A more formal definition of a Semaphore is a special variable on which only two operations are allowed; these operations are officially termed wait and signal . Because “wait” and “signal” already have special meanings in Linux programming, we’ll use the original notation:

  • P(Semaphore variable) for wait
  • V(Semaphore variable) for signal

  These letters come from the Dutch words for wait (passeren : to pass, as in a checkpoint before the critical section) and signal (vrijgeven : to give or release, as in giving up control of the critical section). You may also come across the terms “up” and “down” used in relation to Semaphores, taken from the use of signaling flags.

  Semaphore Definition

  The simplest Semaphore is a variable that can take only the values 0 and 1, a binary Semaphore. This is the most common form. Semaphores that can take many positive values are called general Semaphores . For the remainder of this chapter, we concentrate on binary Semaphores.

  The definitions of P and V are surprisingly simple. Suppose you have a Semaphore variable sv . The two operations are then defined as follows:

  P(sv)	If sv is greater than zero, decrement sv . If sv is zero, suspend execution of this process.
  V(sv)	If some other process has been suspended waiting for sv , make it resume execution. If no process is suspended waiting for sv , increment sv .

  Another way of thinking about Semaphores is that the Semaphore variable, sv , is true when the critical section is available, is decremented by P(sv) so it’s false when the critical section is busy, and is incremented by V(sv) when the critical section is again available. Be aware that simply having a normal variable that you decrement and increment is not good enough, because you can’t express in C, C++, C#, or almost any conventional programming language the need to make a single, atomic operation of the test to see whether the variable is true , and if so change the variable to make it false

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Silberschatz's Operating System Concepts

  • Abraham Silberschatz, Peter B. Galvin, Greg Gagne(Authors)
  • 2020(Publication Date)
  • Wiley

    (Publisher)

  First, let’s see how Semaphores can be used. 6.6.1 Semaphore Usage Operating systems often distinguish between counting and binary Semaphores. The value of a counting Semaphore can range over an unrestricted domain. The value of a binary Semaphore can range only between 0 and 1. Thus, binary Semaphores behave similarly to mutex locks. In fact, on systems that do not provide mutex locks, binary Semaphores can be used instead for providing mutual exclusion. Counting Semaphores can be used to control access to a given resource consisting of a finite number of instances. The Semaphore is initialized to the number of resources available. Each process that wishes to use a resource performs a wait() operation on the Semaphore (thereby decrementing the count). When a process releases a resource, it performs a signal() operation (incrementing the count). When the count for the Semaphore goes to 0, all resources are being used. After that, processes that wish to use a resource will block until the count becomes greater than 0. We can also use Semaphores to solve various synchronization problems. For example, consider two concurrently running processes: P 1 with a statement S 1 and P 2 with a statement S 2 . Suppose we require that S 2 be executed only after S 1 has completed. We can implement this scheme readily by letting P 1 and P 2 share a common Semaphore synch, initialized to 0. In process P 1 , we insert the statements S 1 ; signal(synch); 290 Chapter 6 Synchronization Tools In process P 2 , we insert the statements wait(synch); S 2 ; Because synch is initialized to 0, P 2 will execute S 2 only after P 1 has invoked signal(synch), which is after statement S 1 has been executed. 6.6.2 Semaphore Implementation Recall that the implementation of mutex locks discussed in Section 6.5 suffers from busy waiting. The definitions of the wait() and signal() Semaphore operations just described present the same problem.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Patterns for Parallel Software Design

  • Jorge Luis Ortega-Arjona(Author)
  • 2010(Publication Date)
  • Wiley

    (Publisher)

  • Each software component should be able to enter its critical section and modify the shared variable if and only if this access is confirmed to be safe and secure. Any other software component should proceed or wait depending on whether the original component is executing the critical section.

  • The integrity of the values within the shared variable should be preserved during the entire communication.

  Solution

  Use Semaphores for synchronizing access to the critical section associated with a shared variable, process or resource. A Semaphore is a type of variable or abstract data type, normally represented by a non-negative integer and a queue, with the following atomic operations [Dij68]:

  • signal (Semaphore): If the value of the Semaphore is greater than zero, then decrement it and allow the software component to continue, else suspend the software component process, noting that it is blocked on the Semaphore.

  • wait (Semaphore): If there are no software component processes waiting on the Semaphore then increment it, else free one process, which continues at the instruction immediately following its wait ( ) instruction.

  Structure

  Figure 5.1 illustrates the concept of a Semaphore as an abstract data type with a value, a queue pointer and an interface composed of two operations: signal ( ) and wait ( ).

  Figure 5.1 : A diagram representing the Semaphore as an abstract data type

  If Semaphores are available in a programming language, their typical use is as shown in Figure 5.2 .

  Figure 5.2 : Pseudocode for typical use of a Semaphore, synchronizingthe access to shared variables

  Dynamics

  Semaphores are common synchronization mechanisms that can be used in a number of different ways. This section discusses the case in which Semaphores are used for mutual exclusion and synchronization of cooperating software components.

  • Mutual exclusion. Figure 5.3 shows a UML sequence diagram showing three concurrent or parallel software components, A, B and C, which share a data structure. This shared data structure (not shown in the diagram) is protected by a Semaphore sem, which is initialized with a value of 1.

  The software component A first executes wait (sem) and enters its critical section, which accesses the shared data structure. While A stays in its critical section, B, and later C try to enter their respective critical sections for the same shared data structure, executing wait (sem). Note that the three software components can proceed concurrently, but within their critical section only one software component Figure 5.3

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Operating System Concepts

  • Abraham Silberschatz, Peter B. Galvin, Greg Gagne(Authors)
  • 2018(Publication Date)
  • Wiley

    (Publisher)

  That is, when one process modifies the Semaphore value, no other process can simultaneously modify that same Semaphore value. In addition, in the case of wait(S), the testing of the integer value of S (S ≤ 0), as well as its possible modification (S--), must be executed without interruption. We shall see how these operations can be implemented in Section 6.6.2. First, let’s see how Semaphores can be used. 6.6.1 Semaphore Usage Operating systems often distinguish between counting and binary Semaphores. The value of a counting Semaphore can range over an unrestricted domain. The value of a binary Semaphore can range only between 0 and 1. Thus, binary Semaphores behave similarly to mutex locks. In fact, on systems that do not provide mutex locks, binary Semaphores can be used instead for providing mutual exclusion. Counting Semaphores can be used to control access to a given resource consisting of a finite number of instances. The Semaphore is initialized to the number of resources available. Each process that wishes to use a resource performs a wait() operation on the Semaphore (thereby decrementing the count). When a process releases a resource, it performs a signal() operation (incrementing the count). When the count for the Semaphore goes to 0, all resources are being used. After that, processes that wish to use a resource will block until the count becomes greater than 0. We can also use Semaphores to solve various synchronization problems. For example, consider two concurrently running processes: P 1 with a statement S 1 and P 2 with a statement S 2 . Suppose we require that S 2 be executed only after S 1 has completed. We can implement this scheme readily by letting P 1 and P 2 share a common Semaphore synch, initialized to 0. In process P 1 , we insert the statements S 1 ; signal(synch);

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Beginning Linux Programming

  • Neil Matthew, Richard Stones(Authors)
  • 2007(Publication Date)
  • Wrox

    (Publisher)

  The situation is much easier if hardware support, generally in the form of spe- cific CPU instructions, is available to support exclusive access. An example of hardware support would be an instruction to access and increment a register in an atomic way, such that no other instruction (not even an interrupt) could occur between the read/increment/write operations. One possible solution that you’ve already seen is to create files using the O_EXCL flag with the open func- tion, which provides atomic file creation. This allows a single process to succeed in obtaining a token: the newly created file. This method is fine for simple problems, but rather messy and very inefficient for more complex examples. An important step forward in this area of concurrent programming occurred when Edsger Dijkstra, a Dutch computer scientist, introduced the concept of the Semaphore. As briefly mentioned in Chapter 12, a Semaphore is a special variable that takes only whole positive numbers and upon which programs can only act atomically. In this chapter we expand on that earlier simplified definition. We show in more detail how Semaphores function, and how the more general-purpose functions can be used between separate processes, rather than the special case of multi-threaded programs you saw in Chapter 12. A more formal definition of a Semaphore is a special variable on which only two operations are allowed; these operations are officially termed wait and signal. Because “wait” and “signal” already have special meanings in Linux programming, we’ll use the original notation: ❑ P(Semaphore variable) for wait ❑ V(Semaphore variable) for signal These letters come from the Dutch words for wait (passeren: to pass, as in a checkpoint before the critical section) and signal (vrijgeven: to give or release, as in giving up control of the critical section). You may also come across the terms “up” and “down” used in relation to Semaphores, taken from the use of sig- naling flags.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Real-Time Concepts for Embedded Systems

  • Qing Li, Caroline Yao(Authors)
  • 2003(Publication Date)
  • CRC Press

    (Publisher)

  In this chapter ... • Defining Semaphores ................................ 79 • Typical Semaphore Operations ................. 84 • Typical Semaphore Use .............................. 87 • Points to Remember .................................. 95 C h a p t e r 6 S em apho res 6.1 Introduction Multiple concurrent threads of execution within an application must be able to synchro-nize their execution and coordinate mutually exclusive access to shared resources. To address these requirements, RTOS kernels provide a Semaphore object and associated Semaphore management services. This chapter discusses the following: • defining a Semaphore, • typical Semaphore operations, and • common Semaphore use. 6.2 Defining Semaphores A Semaphore (sometimes called a Semaphore token) is a kernel object that one or more threads of execution can acquire or release for the purposes of synchronization or mutual exclusion. When a Semaphore is first created, the kernel assigns to it an associated Semaphore con-trol block (SCB), a unique ID, a value (binary or a count), and a task-waiting list, as shown in Figure 6.1. 79 C hapter 6: S em a p h o r e s Semaphore-Control Block SCB Value Semaphore Name or ID Task-Waiting List ✓ Task 1 Task 2 ■■ ■ Binary or a Count Semaphore tokens are available. Figure 6.1 A Semaphore, its associated parameters, and supporting data structures. A Semaphore is like a key that allows a task to carry out some operation or to access a resource. If the task can acquire the Semaphore, it can carry out the intended opera-tion or access the resource. A single Semaphore can be acquired a finite number of times. In this sense, acquiring a Semaphore is like acquiring the duplicate of a key from an apartment manager—when the apartment manager runs out of duplicates, the manager can give out no more keys. Like-wise, when a Semaphore’s limit is reached, it can no longer be acquired until someone gives a key back or releases the Semaphore.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Real-Time Systems Development

  • Rob Williams(Author)
  • 2005(Publication Date)
  • Butterworth-Heinemann

    (Publisher)

  The applica-tion programmer has to arrange for each critical, exclusive resource to have a dedicated Semaphore protecting it. This is done by calling the operating sys-tem and requesting the allocation of a new Semaphore using: init(sem – 1) . So now, before accessing the critical data protected by sem – 1, all tasks are required to query the relevant Semaphore: wait(sem – 1) . Note that this system call will probably generate task rescheduling, so even if the resource is available, it is not certain that the running task will be allowed to jump straight in and access the data. Should the Semaphore indicate that its asso-ciated resource is not currently free, the requesting task will be swapped out, inserted into the Semaphore waiting queue, and an alternative ready task restored to running. The binary flag Semaphore has been extended to include a counting cap-ability so that it can serve a wider range of needs. With counting Semaphores, the signal() call can be set to increment the Semaphore value, while its wait() partner function carries out a decrement . This enables the Semaphore to maintain a count of items held in a critical buffer, or the current number of resource users. When a task has finished with the critical activity, it is essential that it calls the exit routine: signal(sem – 1) , otherwise the critical resource will be permanently reserved, and denied to other tasks. This can quickly lead to run-time problems, which are not uncommon. Some operating systems offer the alternative of a ‘mutex’ (mutual exclusion) or a ‘Semaphore’. The distinction rests on who is allowed to release a locked resource. In the case of the mutex only the original task that acquired the resource, by requesting the mutex, is permitted to release it. Other tasks will be blocked if they attempt to carry out a mutex – unlock() . While, with a Semaphore, any task is capable of executing a signal() operation to release the resource.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Real-Time Embedded Multithreading Using ThreadX

  • Edward Lamie(Author)
  • 2019(Publication Date)
  • CRC Press

    (Publisher)

  In most cases, counting Semaphores used for mutual exclusion have an initial value of 1, meaning that only one thread can access the associated resource at a time. Counting Semaphores that have values restricted to 0 or 1 are commonly called binary Semaphores. If a binary Semaphore is used, the user must prevent that same thread from performing a get operation on a Semaphore it already controls. A second get would fail and could suspend the calling thread indefinitely, as well as make the resource permanently unavailable. Counting Semaphores can also be used for event notification, as in a producer-consumer application. In this application, the consumer attempts to get the counting Semaphore before “consuming” a resource (such as data in a queue); the producer increases the Semaphore count whenever it makes something available. In other words, the producer places instances in the Semaphore and the consumer attempts to take instances from the Semaphore. Such Semaphores usually have an initial value of 0 and do not increase until the producer has something ready for the consumer. Applications can create counting Semaphores either during initialization or during runtime. The initial count of the Semaphore is specified during creation. An application may use an unlimited number of counting Semaphores. Application threads can suspend while attempting to perform a get operation on a Semaphore with a current count of zero (depending on the value of the wait option). When a put operation is performed on a Semaphore and a thread suspended on that Semaphore, the suspended thread completes its get operation and resumes. If multiple threads are suspended on the same counting Semaphore, they resume in the same order they occur on the suspended list (usually in FIFO order). An application can cause a higher-priority thread to be resumed first, if the application calls tx_Semaphore_prioritize prior to a Semaphore put call

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction to Parallel Programming

  • Steven Brawer(Author)
  • 2014(Publication Date)
  • Academic Press

    (Publisher)

  CHAPTER 14 ^ = Semaphores ^ ^ = ^ = ^ ^ = and Events 14.1 Introduction Up to this point, the parallel programming examples have used just two synchronization functions—barriers and spin-locks. In this chapter, two more common synchronization functions are described—events and sema- phores. Not all four functions are logically independent. All of them may be con- structed, in software, from the spin-lock, and many other synchronization functions, for specific purposes, may also be constructed. Which functions are used in a particular situation depends on the required functionality, on performance issues, and on the style of the programmer. For example, it will be seen that a binary Semaphore is logically equivalent to a spin-lock. If, on a particular computer system, the spin-lock is implemented in hard- ware while the Semaphore is implemented in software, then the spin-lock will be used if performance is an important issue. On the other hand, a Semaphore allows one to create a protected region where more than one process is allowed at any time. Whether one uses the Semaphore, or con- structs a similar functionality from the spin-lock or event, depends on the details of the problem and the programmer's inclination. 347 348 Semaphores and Events 14.2 Semaphores 14.2.1 Description of Semaphores The Semaphore is a generalization of a spin-lock, to provide a more complex kind of mutual exclusion. (Historically, the Semaphore came first.) Unlike the spin-lock, the Semaphore can provide mutual exclusion in a protected region for groups of processes, not just one process at a time. That is, it can protect regions in which groups of processes may enter at any one time. The following functions provide basic Semaphore functionality: integer sem,new_count,sem_value call shared(sem,4) call Semaphore_init(sem,set_count) call Semaphore_wait(sem) call Semaphore_send(sem) call Semaphore__reset ( sem, new_count ) The Semaphore is initialized by calling the subroutine Semaphore__init.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Distributed Computer Systems

  Theory and Practice

  • H. S. M. Zedan(Author)
  • 2014(Publication Date)
  • Butterworth-Heinemann

    (Publisher)

  In particular, this use of P and V ensures both mutual exclusion and absence of deadlock. Also, if the Semaphore implementation is fair and both processes always exit their critical sections, each process eventually gets to enter its critical section. Semaphores can also be used to solve selective mutual exclusion problems. In the latter, shared variables are partitioned into disjoint sets. A Semaphore is associated with each set and used in the same way as mutex above to control access to the variables in that set. Critical sections that reference variables in the same set execute with mutual exclusion, but critical sections that reference variables in different sets execute concurrently. However, if two or more processes require simultaneous access to variables in two or more sets, the programmer must take care or deadlock could result. Suppose that two processes, PI and P2, each require simultaneous accesss to sets of shared variables A and B. Then, PI and P2 will deadlock if, for example, PI acquires access to set A, P2 acquires access to set B, and then both processes 42 Concepts and notations for concurrent programming try to acquire access to the set that they do not yet have. Deadlock is avoided here (and in general) if processes first try to acquire access to the same set (e.g., A), and then try to acquire access to the other (e.g., B). Figure 3 shows how Semaphores can be used for selective mutual exclu- sion and condition synchronization in an implementation of our simple example operating system. Semaphore in mutex is used to implement mutually exclusive access to input buffer and out mutex is used to im- plement mutually exclusive access to output buffer} 2 Because the buffers are disjoint, it is possible for operations on input buffer and output buffer to proceed concurrently.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Extreme C

  Taking you to the limit in Concurrency, OOP, and the most advanced capabilities of C

  • Kamran Amini(Author)
  • 2019(Publication Date)
  • Packt Publishing

    (Publisher)

  private Semaphores anymore.
• Named mutexes : Again, the same POSIX mutexes with the same properties which were explained in Chapter 16 , Thread Synchronization , but now named and can be used throughout the system. These mutexes should be placed inside a shared memory in order to be available to multiple processes.
• Named condition variables : The same POSIX condition variables which we explained in Chapter 16 , Thread Synchronization , but like mutexes, they should be placed inside a shared memory object in order to be available to a number of processes.
In the upcoming sections, we discuss all the above techniques and give examples to demonstrate how they work. In the following section, we are going to discuss named POSIX Semaphores.

Named POSIX Semaphores

As you saw in Chapter 16 , Thread Synchronization , Semaphores are the main tool to synchronize a number of concurrent tasks. We saw them in multi-threaded programs and saw how they help to overcome the concurrency issues.
In this section, we are going to show how they can be used among some processes. Example 18.1 shows how to use a POSIX Semaphore to solve the data races we encountered in examples 17.6 and 17.7 given in the previous chapter, Process Execution . The example is remarkably similar to example 17.6 , and it again uses a shared memory region for storing the shared counter variable. But it uses named Semaphores to synchronize the access to the shared counter.
The following code boxes show the way that we use a named Semaphore to synchronize two processes while accessing a shared variable. The following code box shows the global declarations of example 18.1