How Does a Semaphore Work, When Counting of Available Shared Memory Locations (Bounded

How does a semaphore work, when counting of available shared memory locations (bounded buffer) is used?

1. Three semaphores are needed:

(a) 'full', initialized to zero, used to keep track of how many cells have received a new value.

(b) 'empty', initialized to the size of the buffer, to keep track of the no. of cells not yet filled or

already taken ( read).

(c) 'mutex', a contraction of the phrase mutual exclusion, to ensure only 1 process (producer

or consumer) accesses shared data at a time; i.e. enters its c.r. of code at a time.

2. 'full' and 'empty' are general semaphores meaning they can be 0 or greater.

'mutex' is a binary semaphore, has the value 0 or 1 only. This is initialized to 1, when counting

semaphores are also being used.

3. Each semaphore is a special variable which is more than just an int, although there is a field in the

semaphore which is of type int. A semaphore is usually a struct with two functions or operations

associated with it: down() and up().

4. down() is implemented by a system call and down is similar to sleep(). The steps in a down operation

are as follows:

(a) checks to see if the value of the semaphore > 0:

if yes, the semaphore is decremented by one.

if no, which means the semaphore equals zero, the process doing the down() operation on

the semaphore, goes to sleep BEFORE DECREMENTING the semaphore.

(b) when used with the general semaphore, empty, by a producer process, empty equal to zero

means the buffer is full and the producer must go to sleep and wait.

(c) when used with the general semaphore, full, by a consumer process, full equal to zero

means the buffer is empty and the consumer must go to sleep and wait.

(d) when used with the binary semaphore, mutex, which is always initialized to 1, decrements

mutex to 0, and the process doing the down() operation - either producer or consumer -

enters its critical region of code. If !(mutex > 0), i.e. mutex equals zero, then some other

process is in its critical region, that is accessing the shared data. In that case the process

doing the down must wait. Note: the down() is not complete at this point and when the

process is wakened, it will continue from that point in the down() function, which is to

decrement the semaphore, mutex.

5. up() always increments the value of the semaphore on which it is operating by one.

(a) When a producer does an up() on the full semaphore, it increases by one the number of cells that now have fresh data deposited.

(b) When a consumer does an up() on the empty semaphore, it increases by one the number of cells that are now available to receive new data.

(c) When any type process does an up() on the mutex semaphore, it increases by one the value in

the semaphore, which then becomes 1. However, there could be many processes sleeping on that

semaphore. In that case one process is chosen, perhaps randomly, and wakened. At that point, the

awakened process completes the down() operation that it was doing when it was blocked. The

awakened process immediately decrements the mutex semaphore. Therefore, AFTER AN UP() ON MUTEX, THE VALUE OF THE MUTEX MAY STILL BE ONE, BUT ONE FEWER PROCESS IS WAITING ON IT.

6. Operations are a semaphore MUST BE ATOMIC. Checking the semaphore value, changing the semaphore value, and perhaps putting the process doing the up() or down() operation on the semaphore on the semaphore, are done as one indivisible action. This is possible only in an operating system that supports semaphores; that is contains these special structures, and is done through system calls and in kernel mode.

7. It is possible to simulate semaphores with software by bit manipulation or using Test and Set Lock mechanisms, when they are present in the machine instruction set. Writing programs that do this are beyond the scope of this course.

What is a mutex?

1. A mutex is a simplified version of a semaphore.

2. A mutex is used in problems when counting is not needed. For example, when only 1 memory cell is shared by multiple processes.

3. A mutex has only one state and therefore can be either on or off; i.e. locked or unlocked.

4. A mutex can be used in user space, whenever a Test and Set Lock instruction is available.

5. A mutex is used in a manner similar to a spin lock (see p. 107) but a mutex is usually used with user-level threads, to avoid busy-waiting. This is done by invoking the run-time system procedure 'thread-yield'. (see p. 113) This is an important mechanism in user-level threads, since these threads are not stopped by clock interrupts. That is, the process the thread is in may receive a clock interrupt and block, but when the process is scheduled again, the same thread would continue to run. Remember, this is not the case in kernel threads, which may choose to run a different thread or even a different process after a clock interrupt.