Synchronization Patterns using Semaphores

Need for synchronization comes in two cases:

  1. When more than one processor run in parallel and
  2. when a single processor run multiple threads.

Normally the user do not have any idea of which thread runs first, its upto the operating system.

The synchronization of threads can be obtained by message passing or mutual exclusion. If a constraint arrives, we have to do process2 only after the completion of process1, we cannot guarantee it. This decision of scheduling is upto the OS. We can make constraint working by passing message to process2 to block it until process2 gets a message showing process1 is complete.

Use of semaphore is a simple way to achieve synchronization.

Basic Synchronization Patterns

  • Signaling

Signaling is the process of sending a signal to another process saying that it had done something. It make sure that a section of code works only after a section in a different code is completed.

Assume two threads A and B. A contains a statement ‘a’ and B contains a statement ‘b’, first we have to complete ‘a’ and only after that we can do ‘b’. We can do this by using a semaphore whose value is initialized to 0.

This will do the purpose. Even if the second thread run first the first statement is a ‘down’, as the semaphore value is 0, the thread will sleep and for the ‘up’ in thread one.

  • Rendezvous

In rendezvous the constraint is that certain parts of all thread must finish to execute further statements. For example, assume two threads A and B. A have two statements ‘a1’ and ‘a2’ and B have two statements ‘b1’ and ‘b2’. ‘a1’ must be executed first to execute ‘b2’ and ‘b1’ must be executed first to execute ‘a2’.

We can do this by using two semaphores ‘a1’ and ‘b1’ both initialized to 0.

First ‘a1’ in A or ‘b1’ in B is performed. After that A waits for semaphore b1 to get posted or B waits for semaphore a1 to get posted. Only after the post either A or B will get executed. If this is performed carelessly, there is high chance of deadlock to occur.

  • Mutex

This section deals with how synchronization can be obtained by mutual exclusion. Mutex is like a token, the thread holding the mutex currently can get executed, others sleep. At a time only one can hold the token. Mutex are mainly needed when using a shared variable.

In many cases, manipulation on the shared variable cannot be atomic. To make the shared variable atomic we can guard it using a semaphore, which acquires lock when it enters critical section and release after the manipulation of the shared variable.

In the above case ‘count’ is a shred variable on which an increment is performed in both the threads. If the first thread acquires the token second thread cannot enter the critical section and vice versa. In this situation both the thread perform the same operation hence they are called symmetric solution else they are called asymmetric.

  • Multiplex

In the above case only one thread can enter the critical section at a given time. It is useful in many situation, but in many other situations it may be possible for a fixed number of threads to enter critical section and after that it behaves like mutex. This can be implemented using another pattern called multiplex.

In multiplex a fixed number of threads can enter the critical section at any given time. It can be implemented using a semaphore initialized to the total number of threads permitted into the critical section at a time and a flag which counts the number of threads entering the critical section.

Click here to view the full implementation.

Advertisements

About Odol Shinu

I've completed my B Tech in Information Technology in 2010 from Government Engineering College Sreekrishnapuram Palakkad under Calicut University.

Posted on October 26, 2010, in synchronization. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: