二进制信号量与计数信号量

1. Introduction

As a society, we should observe many conventions for living together. Moreover, particular conventions are widespread around the world. For example, a red light is a traffic signal that generally indicates a driver to stop and wait. On the contrary, a green light represents that a driver can go on the road. Through these conventions, a society keeps organized and avoid lots of problems.

Likewise, computer systems must create mechanisms to avoid unexpected errors and catastrophic problems during their execution. One example of such mechanisms is the semaphore variable. These variables manage the access of threads and processes to a given resource available in a computer system. There exist two major categories of these semaphores: binary and counting.

In this tutorial, we’ll understand how binary and counting semaphores operate. First, we’ll have a brief review of semaphores, refreshing our memories on their general characteristics. Thus, we’ll analyze both the binary and counting semaphores categories in particular. Finally, we compare these semaphore categories in a systematic summary.

2. Semaphore Variables

In general, semaphores variables are mechanisms used to control the access of processes or threads to resources. Precisely, these variables aim to synchronize access to shared resources in concurrent systems. To do that, programs that access protected shared resources have a semaphore variable in common.

Programs, in turn, check semaphores before executing portions of code that manipulate protected resources (critical sections), querying if they can immediately enter into a critical code section or must wait for it.

In a technical view, a semaphore consists of an integer value shared among different processes and threads. Positive values in the semaphore indicate how many access units are available to a given critical section. Otherwise, negative values (or zero) represent that the critical section is inaccessible. Moreover, there exist two semaphore operations:

• Wait (P): an operation that decrements the integer value of a semaphore by one. If the integer value becomes negative, the semaphore blocks the entity that executed the wait operation and adds it to the semaphore queue. If not, the entity receives an access unit and can enter in the critical section
• Signal (V): an operation that increments the integer value of a semaphore by one. So, if the integer value was negative before signaling, the access unit is given to the first entity in the semaphore’s queue. On the contrary, the retrieved access unit keeps available in the semaphore

In general scenarios, a process or thread executes a single wait operation to require access to a critical section and a single signal operation to leave it. If it isn’t done, several problems, such as process freezing or crashing, can occur.

3. Binary Semaphores

Binary semaphores are synchronization mechanisms with integer values varying between zero (0) and one (1). Thus, this category of semaphore provides a single access unit to a critical section. It means that only one entity will access the critical section at once.

The following image shows a flowchart with a typical process of an entity accessing a critical section controlled by a binary semaphore:

Binary semaphores, besides synchronizing the accesses to critical sections, also provide mutual exclusion to them. So, it can avoid race conditions from occurring in the critical sections.

However, it is relevant to highlight that, although providing mutual exclusion, binary semaphores aren’t the same as mutexes. Semaphores are, by definition, signaling mechanisms, while mutexes are locking mechanisms.

In this way, mutexes provide mutual exclusion for accessing critical code sections. Binary semaphores, in turn, focus on synchronizing the access to critical sections. Thus, mutual exclusion is the primary goal of mutexes. However, for binary semaphores, it is a consequence of how the synchronization is designed.

So, in practice, a mutex locks a critical section only if exist an entity on it. Semaphores, however, can make a critical section inaccessible even without entities on it. It happens, for example, when some external precondition must be satisfied to enable entities to access a given critical section.

4. Counting Semaphores

*Counting semaphores are synchronization mechanisms with values varying in a range [0,n], where n* is a non-negative integer value greater than one (1). In this way, counting semaphores can make available several access tokens to a given critical section. So, several entities can access the critical section at the same time.

The following image presents a flowchart depicting a usual process of an entity accessing a critical section controlled by a counting semaphore:

We can notice that binary and counting semaphores execute similar operations to synchronize the access to a critical section. The principal difference is that counting semaphores checks a range condition (if there are any of the access tokens available or not). A binary semaphore, in turn, tests a binary condition (if the only access token is available or not).

In this way, executing the wait operation (P) in a binary semaphore or a counting semaphore will result in the same behavior: the entity will wait in a queue till getting an access token. However, executing the signal operation (V) in a binary semaphore with value one (1) will not change its value. In a counting semaphore, in turn, the signal operation in the same conditions will increase the semaphore value to two (2).

5. Systematic Summary

We studied that there exist two categories of semaphores: binary and counting. Both categories employ integer values to synchronize the access to critical sections. Furthermore, both categories have the same operations: wait and signal.

The main difference between binary and counting semaphores is the number of access units made available by them. Binary semaphores have a single access unit. So, it enables a single entity to access a critical section at once (mutual exclusion). Counting semaphores, in turn, have multiple access units provided to different entities simultaneously.

The following table summarizes the differences between binary and counting semaphores:

Binary Semaphore

Counting Semaphore

Synchronization

Yes

Yes

Mutual Exclusion

Yes

No

Access Units

One

Multiple

Internal Value Range

6. Conclusion

In this article, we learned about binary and counting semaphores. First, we outlined the main concepts of semaphores in a brief review. Later, we in-depth analyzed the characteristics of each category of semaphores: binary and counting. At last, we compared the semaphore categories, summarizing their main similarities and differences.

We can conclude that semaphores are crucial mechanisms to keep track and control which entities will access a given critical section. Moreover, as signaling mechanisms, they have particular importance due to enabling entities to execute a signal operation (V) without previously executing a wait operation (P). In such a way, several and heterogeneous processing scenarios can be synchronized by using semaphores.