/Race Conditions – III

Race Conditions – III

As promised on the previous part, I shall talk about semaphores on this post.

In order to set some history preliminaries about semaphores, I’ll begin with some history.
As stated in the previous post, sleep and wakeup method to multiplex over a resource had a flaw which has been indicated in the producer consumer problem.

due to that problem Edsger W. Dijkstra has came up with semaphores which is in simple way, an integer. It is used to count the wakeups and sleeps calls issued in order to not have a lost call. A semaphore has two special operations which are called up() and down() or wakeup() and sleep() or wait() and signal(). as up and down state each operation does an increment and decrement respectively over a semaphore.
till this point I haven’t shown how a semaphore could be used to enable multiplex operations over a resource. It’s almost similar to the wakeup() and sleep() operations, but on semaphores you can operate over more than one resource, since semaphore is a counter.

a semaphore can take the values from 0 and up, but not negative. and for that if a process executes a down over a semaphore when the semaphore value is 0, It is blocked until another process issues an up. therefore we can say that a semaphore is used to count how many available slots or sub-resources can be used from a resource.

Suppose we have processes P1~P8, with an array of size 4. every process sets a slot of that array to value keep the its slot of the array reserved for few cycles. here we will have a bounded resource to value 4. so here a semaphore can take a value 0~4.

on some point free_slots will equal 0 and used_slots will equal 4, say P5 on this point execute and try to down the free_slots semaphore. Of course if such an operation is executed free_slots will equal -1 which is not acceptable, so the process is blocked until another process who has reserved an array slot up the free_slots semaphore after releasing an entry. in order to semaphore operations to be valid and not suffer critical region overlapping, both down and up operations need to be atomic to avoid scheduling issues mentioned on first part. sadly this isn’t the case. but such operations are implemented on system calls with interrupts disabled to avoid overlapping on critical regions.

A better example on semaphore is to apply it on the problem it came to solve, which in this case is the producer consumer.

free_slots and busy_slots represent empty array slots that a producer can use and full array slots that consumer can use. a mutex here can be also called a binary semaphore is used to lock a critical region like the previous example so producer and consumer wouldn’t access the resource at same time.