1. Semaphores
When two or more processes or threads share some common data, the final result of the shared data may depend on which process executes first and precisely when. This is commonly referred as the race condition problem. For example, two processes both increment a shared counter. At the assembly language level, each process would have code for counter increment like the following:
LOAD R1, M(counter);// load the counter value to register R1
INC R1;// increment the register R1
STORE R1, M(counter);// store the result back to counter
Assume the current value of the counter is 8. Then after both processes complete their counter increment operations, we expect the counter has value 10, no matter which process is executed first. But when the two processes are executed concurrently the resultant value of the counter may be 9, instead of correct value 10. Here is how it may happen. Let’s say the first process (P1) executes the LOAD instruction and so R1 is equal to 8, then P1 proceeds to increment R1 to 9. Before P1 executes the STORE instruction to store the result back to the counter, it is preempted by the other process (P2) (because P1’s time quantum is used up, for example). P2 executes its LOAD instruction, since the modified value by P1 has not been stored back to the counter yet, so R1 is 8. (Note: P1 and P2 have their own contexts, when P2 starts its execution it has its own R1 through context switch.) P2 proceeds to increment R1 by 1 and stores its value, which is 9, to the counter. Later when P1 gets the CPU it executes the STORE instruction which stores its R1 value, which is 9, to the counter. Thus, the counter has incorrect value 9, instead of correct value 10.
In this section we will introduce a process synchronization mechanism called semaphores that may be used to solve the above-mentioned problem and we will discuss different applications of semaphores.
1.1 The Definition of Semaphores
E. W. Dijstra proposed semaphores in 1965 as a mechanism for process synchronization. A semaphore is a non-negative integer with two access primitives, called P and V operations, which are the only way for processes or threads to access the semaphore. The V operation is to increment the value of the semaphore by 1 and the P operation is to decrement the value of the semaphore by 1 as soon as the resulting value would be non-negative. The two operations are indivisible or atomic. For the V operation to be indivisible its execution must not be interrupted by any P or V operations executed by other processes on the same semaphore. For the P operation, there are two separate execution branches based on the condition to be checked. Logically it can be modeled as follows:
Figure 1 The execution branches of the P operation.
The indivisibility of the P operation means that the execution from A to B or from A to C cannot be interrupted by any other P or V operations performed on the same semaphore. The indivisibility property of the P and V operations is necessary to guarantee the correctness for the intended purpose of semaphores. If they were not indivisible, then the value of the semaphore would a variable shared by processes that perform P and V operation on it. Then the same exact race condition problem described above may occur on this semaphore.
We want to note here that the indivisibility of the P and V operations are only applicable to P and V operations that access the same semaphore. A P operation (or a V operation) on semaphore S1 may be interrupted by a P or V operation performed on a different semaphore S2.
It also be noted that the P operation may be interrupted when it goes from point C to A, i.e., interruption is allowed to occur before the operation tests the value of the semaphore again after a failed test.
Often people use wait and signal for P and V, respectively. Another pair of names for P and V is down and up, respectively.
Semaphores often are further divided into binary semaphores and general semaphores. A binary semaphore is one whose initial value is 1, and a general semaphore is one whose initial value can be any nonnegative integer. Binary semaphores are sometime referred as mutual exclusion locks, or simply, mutex.
1.2 Implementation of Semaphores
In the above definition the P operation uses busy waiting to wait for the semaphore value to be changed (A to C and back to A may be considered as a while loop.). Busy waiting is not desirable in any real system since it wastes CPU time. Most implementations of semaphores in today’s operating systems put the calling process to a waiting queue designated to the semaphore if the P operation cannot be completed. When a V operation is executed, a waiting process, if any, is awaken up and moved to ready state. This type implementation may be modeled as follows for the P and V operations.
Figure 2 Implementation of the P operation.
Figure 3 Implementation of the V operation.
For both operations the execution sequences from A to B or from A to C must be indivisible for P and V operations performed on the same semaphore.
1.3 The POSIX Semaphore API
IEEE Standard for Information Technology: Portable Operating System Interface (POSIX) defines a standard operating system interface and environment to support application portability at the source code level. One of its amendments is Real Time Extension, which defines the interface and environment for real-time applications. One of the services specified in the extension is semaphore. POSIX Rea-time Extension defines the following semaphore functions in the syntax of the C programming language and this set of function has been implemented by many real-time operating systems including BrickOS.
Function Signature / Descriptionint sem_init (sem_t *sem, int pshared, unsigned int value) / Initialize a semaphore.
int sem_wait (sem_t *sem) / Wait for semaphore (blocking).
int sem_trywait (sem_t *sem) / Wait for semaphore (non-blocking).
int sem_post (sem_t *sem) / Post a semaphore.
int sem_getvalue (sem_t *sem, int *sval) / Get the semaphore value.
int sem_destroy (sem_t *sem) / Destroy a semaphore.
The header <semaphore.h>, which must be provided by the operating system if it conforms to the POSIX Real-time Extension, defines the data type sem_t to represent semaphores. sem_init()initializes the semaphore of semwith the initial value. The pshared parameter is ignored in BrickOS[1]. sem_wait() peforms the wait operation on semaphore sem and if the value of sem is less than one, the calling thread is blocked. sem_trywait()does the same as sem_wait()except it returns with error EAGAIN when the value of the semaphore is less than one. The former is commonly called blocking wait and the latter non-blocking wait. sem_post()performs the signal operation of semaphore. sem_getValue()returns the current value of the semaphore sem. sem_destroy()destroys the semaphore sem.
1.4 Applications of Semaphores
Semaphores are most commonly used for mutual exclusion to solve the race condition problem. They have also been used in other applications. One such application is to enforce certain execution sequences among statements/functions in different processes. Another application is to use semaphores as counters to represent the number of available system resources. In this section we will take a look of the three applications of semaphores.
1.4.1 Mutual Exclusion
The question is how to solve the race condition problem introduced at the beginning part of this document. We can use a semaphore (sem) with initial value 1 and modify the increment operation part as follows:
sem_wait(sem);
LOAD R1, M(counter);// load the counter value to register R1
INC R1;// increment the register R1
STORE R1, M(counter);// store the result back to counter
sem_post(sem);
Since the semaphore’s initial value is 1, the first process (P1) will decrement the semaphore’s value by 1 and proceed to carry out its increment counter operation. If P2 tries to increment the counter it must execute its sem_wait on the same semaphore. Since the semaphore’s value is 0 now, P2 will have to wait. When P1 completes its increment operation, it executes the sem_post, which would awaken P2. When P2 continues its execution at a later time, it will increment the semaphore value based on the modified value by P1.
1.4.2 Enforcing Execution Sequences
Semaphores may be used for process synchronization in two different ways. One is to enforce execution sequence among processes. For example, if we want the statements among the following three processes to be executed in the order depicted in Figure 4 An example of enforced execution sequence.
T1T2T3Figure 4 An example of enforced execution sequence.
We may use three semaphores (sem1, sem2, and sem3) with initial value 0 for all to enforce the execution sequence as follows:
T1T2T3
.
S1S2
sem_post(sem1);sem_wait(sem1);sem_post(sem2);
sem_wait(sem2);
S3
sem_post(sem3);
sem_wait(sem3);
S4
If T1 executes S1 and T3 executes S2 before T2’s S2, sem1 and sem2 would have both value 1 when T2 tries to execute S3. Thus T2 will pass the two wait operations on sem1 and sem2 and then proceeds to execute S3. However, if T2 tries to execute S3 before either T1 or T3 executes its post operation on sem1 or sem2, T2 would have to wait on the semaphore sem1 or sem2, respectively. The same is true for the execution order between S3 and S4. Thus the execution sequence is enforced by the three semaphores.
1.4.3 Resource Counters
Semaphores may also be used for system resource control. For example, suppose there are three printers to be shared by multiple threads. To ensure a printer is only being used by one thread, we can use a semaphore to control the allocation of the printers. The printer semaphore is initialized three, the number of available shared system resources, in this case, printers.
sem_t pntr_sem;sem_t mutex;
int main() {
sem_init(&pntr_sem, 0, 3);
sem_init(&mutex, 0, 1);
execi(thread_fun, …);
execi(thread_fun, …);
}
void thread_fun() {
printer = allocate();
// use printer
deallocate(printer);
}
int allocate() {
sem_wait(&pntr_sem);
sem_wait(&mutex);
int printer = get_printer();
sem_post(&mutex);
return printer;
}
void deallocate(int printer) {
sem_wait(&mutex);
release_printer(printer);
sem_post(&mutex);
sem_post(&pntr_sem);
}
Question: why semaphore mutex is needed in the above example?
1.5 Object-Oriented Implementation of Semaphores
In this section we will show how to implement semaphores as objects in BrickOS and C++ and also in the LeJOS environment.
1.5.1 BrickOS and C++
Here is the source code of Semaphore.H. It encapsulates the low level details of semaphore operation and provides an object-oriented interface.
//file name: Semaphore.H#include <semaphore.h>
class Semaphore {
private:
sem_t sem;
public:
Semaphore() { Semaphore(1); }
Semaphore(int val) {
sem_init(&sem, 0, val);
}
int wait() {
return sem_wait(&sem);
}
int trywait() {
return sem_trywait(&sem);
}
int signal() {
return sem_post(&sem);
}
int getValue() {
int value;
sem_getvalue(&sem, &value);
return value;
}
void destroy() {
sem_destroy(&sem);
}
~Semaphore() {
sem_destroy(&sem);
}
};
The following program, using the Semaphore.H file defined above, creates two threads, which populate the same 10-element array with a given value. When the semaphore operations are commented out, the resultant array contains 3, 3, 3, 3, 3, 3, 5, 5, 5. That implies that two threads were accessing the array at the same time. When the semaphore operations are kept, the resultant array contains either all 3’s, by the first thread, or all 5’s by the second thread.
// filename: critical-sec.C#include <config.h>
#include <conio.h>
#include <unistd.h>
#include <stdlib.h>
#include <dlcd.h>
#include <sys/tm.h>
#include "Semaphore.H"
int thread1(int argc, char** argv);
int thread2(int argc, char** argv);
class Shared {
private:
int shared[10];
public:
Shared(int x) {
for (int i=0; i<10; i++) shared[i] = x;
}
void set(int idx, int y) {
shared[idx] = y;
}
void print() {
for (int i=0; i<10; i++) {
lcd_int(shared[i]);
sleep(2);
lcd_clear();
sleep(1);
}
}
};
Shared shared(10);
Semaphore *mutex;
int value1 = 3;
int value2 = 5;
int main(int argc, char **argv)
{
tid_t pid1, pid2;
mutex = new Semaphore(1);
pid1 = execi(&thread1, 0, 0, 15, DEFAULT_STACK_SIZE);
lcd_int(pid1);
pid2 = execi(&thread2, 0, 0, 15, DEFAULT_STACK_SIZE);
lcd_int(pid1);
sleep(1);
cputs("before");
sleep(5);
shared.print();
cputs("after");
}
int thread1(int val, char** ptr) {
lcd_int(mutex->getValue());
mutex->wait();
lcd_int(mutex->getValue());
for (int i=0; i<10; i++) {
shared.set(i, value1);
msleep(10-i);
lcd_int(value1);
}
mutex->signal();
lcd_int(mutex->getValue());
sleep(2);
return 0;
}
int thread2(int val, char** ptr) {
lcd_int(mutex->getValue());
mutex->wait();
lcd_int(mutex->getValue());
for (int i=0; i<10; i++) {
shared.set(i, value2);
msleep(5+i);
lcd_int(value2);
}
mutex->signal();
lcd_int(mutex->getValue());
sleep(2);
return 0;
}
The above example uses the semaphore class, which is defined in Section 1.5. It first defines a semaphore object named mutex with initial value 1. To perform a wait or signal operation on mutex, it uses the C++ member function syntax: mutex->wait() or mutex->signal().
1.5.2 LeJOS and Java
The Java programming language does not support semaphore; instead it supports a higher-level abstraction mechanism for solving the race condition problem. The mechanism is called monitors, or synchronized objects in Java terminology. Java also provides wait() and notify() and nottifyAll() methods for thread synchronization. The wait() method of Java puts the calling thread to waiting state until a notify() or notifyAll() is executed on the same synchronized object in which the wait() was called. The following shows how to implement semaphores in Java. Since word wait is a reserved word in Java, we choose another pair of names down and up for semaphore’s wait and signal, respectively. In this implementation, semaphores are synchronized objects with a private integer for semaphore’s value. The down() operation checks the value. If the value is less than one, the calling thread is put to waiting state, otherwise the value is decremented by 1 and the down() operation returns. The up() operation increments the semaphore value by 1 and then notifyAll all waiting threads, if any. Because the down() and up() operations are synchronized methods, so the Java Virtual Machine guarantees their mutual exclusion.
class Semaphore {private int value;
Semaphore(int value) {
if (value < 0) throws
new IllegalArgumentException(value + “<0”);
this.value = value;
}
public synchronized down() throws InterruptedException {
while (value < 1) wait();
value = value –1;
}
public synchronized void up() {
value = value + 1;
notifyAll();
}
};
1.6 More on Semaphores
Let us use a more realistic example for the race condition problem and how to use semaphores to solve the problem. From this example we will also see how dangerous it may be if semaphores are not used properly, and we will introduce a new high level process synchronization mechanism, monitors.
First let us define a class for bank accounts. Each account has a balance, a withdraw method, and a deposit method. Such a class may be defined as shown in Figure 5 in Java-like syntax. To keep our focus on synchronization, we assume all the accounts only deal with integral amount of dollars.
1 class Account {2 private int balance;
3
4 public int withdraw(int amount) {
5 if (balance < amount )
6 return –1;
7 balance = balance – amount;
8 return amount;
9 }
10 public void deposit(int amount) {
11 balance = balance + amount;
12 }
13 };
Figure 5 Bank account class.
As in any real banking applications, a user account may be accessed at the same time by two different owners, withdrawing from or depositing to the account. Suppose we have a checking account with a balance of $1000 and two owners of the account may withdraw from it at the same time. The two withdrawals by the two owners would be translated to two processes or threads both of which execute the withdraw method at the same time. Let’s say owner 1 tries to withdraw $500 and owner 2 $600. Since the balance of the account is only $1000, not enough for both withdrawals, one process should have the –1 returned from withdraw. If owner 1 withdraws successfully, the correct remaining balance should be $500, and if owner2 successfully, it should be $400. But since there is no synchronization on the access to this account, it is possible that in mid of the execution of withdraw for owner1, the process for owner 2 preempts and executes. When that happens, the balance may become negative. Here is how it may happen: Process 1 for owner 1 is executing line 5 of withdraw, finding the condition is false (there is enough fund for the withdrawal); it proceeds to line 7 to make the deduction. Right before line 7 is started, Process 1 runs out of its allocated time quantum (assume the round-robin scheduling) and so it is preempted. Process 2 of owner 2 executes and passes line 5 since the current balance is still $1000, then it proceeds to make the $600 deduction, and then returns. When Process 1 later resumes its execution, it continues from line 7. Now the balance, after the successful withdrawal by owner 2, is only $400. But Process 1 is not aware of this since it has passed its balance test at line 5 before the preemption. So it unknowingly deducts $500 from the account and then returns. Now the balance becomes -$100. From the design of the withdraw method, it is obvious that the balance should never become negative. The execution sequence of the above race condition can be depicted in Figure 6.
Process1 process 2withdraw(500)
if (balance < amount) is false
preempted
withdraw(600)
. . . if (balance <amount) false
balance= $1000-$600=$400
. . . return;
. . .
preempted
resumes
balance = $400 - $500
= -$100
return;
Figure 6 Race condition with two withdrawals.
From the above example, we can see that the withdraw method must be executed mutually exclusively when it called by multiple processes/threads. To solve the problem demonstrated in the above example, we can add a semaphore with initial value 1 to the Account class and insert down and up operations to ensure the mutual exclusion. Please note that the call to the up method on line 8 is necessary. If line 8 were not there, a process/thread may never release the semaphore if the balance is not enough for a withdrawal since it would return from withdraw without calling the up method on the semaphore.
1class Account {2 private int balance;
3 private Semaphore mutex(1);
4
5 public int withdraw(int amount) {
6 mutex.down();
7 if (balance < amount ) {
8 mutex.up();
9 return –1;
10 }
11 balance = balance – amount;
12 mutex.up();
13 return amount;
14 }
15 public void deposit(int amount) {
16 balance = balance + amount;
17 }
18};
There are two other scenarios of concurrency in this banking example. Owner 1 could withdraw while owner 2 deposit, and owner 1 deposits and so does owner2. One may argue that the deposit method does not need to be executed mutually exclusively with withdrawals and other deposits since deposit have only one statement with an implicit assumption that one statement would be executed with no interruption. The assumption is true if the one statement is a single machine-level instruction since most today’s computers do not allow hardware interruption until current instruction is completed. In our example, the statement is written in a high-level programming language and it is very likely to be compiled into three machine-level instructions as follows where balance and amount are memory locations where the two variables are stored:
1LOAD R1, M(balance);// load balance to register R1
2ADD R1; M(amount);// add amount to register R1
3STORE R1, M(balance);// store the result back to balance
References
9/27/2018 -- 10:53 AM1/12
[1]pshared is used for multiple processes to share the same semaphore. Since BrickOS does not support processes, so this option is not applicable and is ignored.