Mutex vs semaphore vs Monitor

Problem

What is the difference between mutex and semaphore?

Solution

Mutexes, monitors and semaphores are all synchronization mechanisms i.e. they are used to mediate access to a shared resource between multiple processes or threads (referred to as processes henceforth).
However, they are used differently:

Mutex

Used to provide mutual exclusion i.e. ensures at most one process can do something (like execute a section of code, or access a variable) at a time.
A famous analogy is the bathroom key in a Starbucks; only one person can acquire it, therefore only that one person may enter and use the bathroom. Everybody else who wants to use the bathroom has to wait till the key is available again.

Mutexes always use the following sequence:

  - SemTake
  - Critical Section
  - SemGive

Here is a simple example:

  Thread A                     Thread B
   Take Mutex
     access data
     ...                        Take Mutex  <== Will block
     ...
   Give Mutex                     access data  <== Unblocks
                                  ...
                                Give Mutex

Monitor
Provides mutual exclusion to an object i.e. at any point in time, at most one process may access any of the object's members/ execute any of its methods. This is ideologically similar to a mutex for an entire OOP instance; no part of the instance can be touched by more than one process at a time. Monitors can provide condition variables which are used for signaling purposes, in addition to "pure" mutual exclusion.

Semaphores

Is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count - the count of keys - is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.

Key difference - Ownership and signalling

Mutex can be released only by thread that had acquired it, while you can signal semaphore from any other thread (or process), so semaphores are more suitable for some synchronization problems like producer-consumer. So, semaphores have no notion of ownership, as any thread can release a semaphore.

Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup.
General Questions:
1. Can a thread acquire more than one lock (Mutex)?
Yes, it is possible that a thread will be in need of more than one resource, hence the locks. If any lock is not available the thread will wait (block) on the lock.
2. Can a mutex be locked more than once?
A mutex is a lock. Only one state (locked/unlocked) is associated with it. However, a recursive mutex can be locked more than once (POSIX complaint systems), in which a count is associated with it, yet retains only one state (locked/unlocked). The programmer must unlock the mutex as many number times as it was locked.
3. What will happen if a non-recursive mutex is locked more than once.
Deadlock. If a thread which had already locked a mutex, tries to lock the mutex again, it will enter into the waiting list of that mutex, which results in deadlock. It is because no other thread can unlock the mutex. An operating system implementer can exercise care in identifying the owner of mutex and return if it is already locked by same thread to prevent deadlocks.
4. Are binary semaphore and mutex same?
No. We will suggest to treat them separately, as it was explained signalling vs locking mechanisms. But a binary semaphore may experience the same critical issues (e.g. priority inversion) associated with mutex. We will cover these later article.
A programmer can prefer mutex rather than creating a semaphore with count 1.
5. What is a mutex and critical section?
Some operating systems use the same word critical section in the API. Usually a mutex is costly operation due to protection protocols associated with it. At last, the objective of mutex is atomic access. There are other ways to achieve atomic access like disabling interrupts which can be much faster but ruins responsiveness. The alternate API makes use of disabling interrupts.
6. What are events?
The semantics of mutex, semaphore, event, critical section, etc… are same. All are synchronization primitives. Based on their cost in using them they are different. We should consult the OS documentation for exact details.
7. Can we acquire mutex/semaphore in an Interrupt Service Routine?
An ISR will run asynchronously in the context of current running thread. It is not recommended to query (blocking call) the availability of synchronization primitives in an ISR. The ISR are meant be short, the call to mutex/semaphore may block the current running thread. However, an ISR can signal a semaphore or unlock a mutex.
8. What we mean by “thread blocking on mutex/semaphore” when they are not available?
Every synchronization primitive will have waiting list associated with it. When the resource is not available, the requesting thread will be moved from the running list of processor to the waiting list of the synchronization primitive. When the resource is available, the higher priority thread on the waiting list will get resource (more precisely, it depends on the scheduling policies).
9. Is it necessary that a thread must block always when resource is not available?
Not necessarily. If the design is sure ‘what has to be done when resource is not available‘, the thread can take up that work (a different code branch). To support application requirements the OS provides non-blocking API.
For example POSIX pthread_mutex_trylock() API. When the mutex is not available the function will return immediately where as the API pthread_mutex_lock() will block the thread till resource is available.

References

• http://stackoverflow.com/questions/62814/difference-between-binary-semaphore-and-mutex
• http://www.geeksforgeeks.org/mutex-vs-semaphore/
• http://www.netrino.com/node/202
  
• http://doc.trolltech.com/4.7/qsemaphore.html

Read More

Atomicity and Atomic operations

Atomic Operation
What is an atomic operation? An idea of atomic operation helps in understanding reentrancy, critical section, thread safety, synchronization primitives, etc… (we will have upcoming articles on each).


Atomicity, Atomic Operation:
In simple terms, atomicity is unbreakability, i.e. an uninterrupted operation. If two users issue a print command, each print should go in single attempt. If the printer driver is sending parts of data from two users, the printout will not be as expected. Hence, the printer driver must send the print command as unbreakable operation from one application at a time (in other words synchronize the access to printer).
Note that the data base terminology on atomicity would be different, yet the concept is same.
With an example we can understand the atomicity in programming well. Consider in a multi-threaded application, a function is incrementing a global/static variable,
count++; // count has permanent storage in RAM
The above statement can be decomposed into, atleast three operations.

1. Fetching count value
2. Incrementing count value
3. Storing the updated value

If a thread executing the function containing the above statement is fetching its value (say 2). It is possible that at this point of execution, the thread can be preempted and another thread may invoke the same function. Consequently, the value of count will be incremented to 3 by that thread. When the former thread is resumed, it still retains the previous value (2), instead of latest value (3), and ends up in writing back 3 again. Infact, the value of count should be 4 due to affect of both the threads.
Such kind of bugs are quite difficult to recreate and locate.
An example of atomic operation is instruction execution, usually an instruction feed to the execution unit can’t be stopped in the middle. Yet, a statement in high level language results in multiple instructions. It is the root cause of non-atomic operations.


References

• http://www.geeksforgeeks.org/g-fact-57/
• http://en.wikipedia.org/wiki/Atomic_action

Read More

Critical section

Critical Section

It is the part of the program where the shared memory is accessed or a critical section is group of instructions/statements or region of code that need to be executed atomically, such as accessing a resource (file, input or output port, global data, etc.).

In concurrent programming, if one thread tries to change the value of shared data at the same time as another thread tries to read the value (i.e. data race across threads), the result is unpredictable.The access to such shared variable (shared memory, shared files, shared port, etc…) to be synchronized. Few programming languages have built in support for synchronization.

It is critical to understand the importance of race condition while writing kernel mode programming (a device driver, kernel thread, etc.). since the programmer can directly access and modifying kernel data structures.

A simple solution to critical section can be thought as shown below,

acquireLock();
Process Critical Section
releaseLock();

A thread must acquire a lock prior to executing critical section. The lock can be acquired by only one thread. There are various ways to implement locks in the above pseudo code.
The three requirements for solving the critical section problem:

Mutual Exclusion:  one process at a time gets in critical section.
(http://en.wikipedia.org/wiki/Mutex)

Progress:  if pi wants to get in critical section and no process is in critical section
                      then pi should be able to progress.

Progress is defined as the following: if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in making the decision as to which process will enter its critical section next. This selection cannot be postponed indefinitely.A process cannot immediately re-enter the critical section if the other process has set its flag to say that it would like to enter its critical section.

Bound wait:  pi should be able to get critical section with some upper waiting time.

Example:
The Producer-Consumer Problem:
Producer:

while(true)
{
    Produce(nextp);
    while(counter == n);   //if buffer is full, wait
    buffer[in] = nextp;
    in = (in + 1) % n;     //mode by n
    counter = counter + 1;
}

Consumer:

while(true)
{
    while(counter == 0);  //if buffer is empty, wait
    nextc = buffer[out];
    out = (out + 1) % n;
    counter = counter - 1;
    Consume(nextc);
}

The problem occurred at sharing the same memory space, counter.
If both read and write counter at same time,  it will cause inconsistent.
e.g. Both got counter = 3
then producer update it into 4 then consumer writes it into 2.

Useful Links:

• http://en.wikipedia.org/wiki/Critical_section
• http://www.geeksforgeeks.org/g-fact-70/
• http://sudhansu-codezone.blogspot.in/2012/01/race-condition-critical-section.html

Read More

Can two threads call a synchronized method and normal method at the same time?

Problem

You are given a class with synchronized method A, and a normal method C. If you have two threads in one instance of a program, can they call A at the same time? Can they call A and C at the same time?

Solution:
Java provides two ways to achieve synchronization: synchronized method and synchronized statement.

• Synchronized method: Methods of a class which need to be synchronized are declared with “synchronized” keyword. If one thread is executing a synchronized method, all other threads which want to execute any of the synchronized methods on the same objects get blocked.
  
  Syntax: method1 and method2 need to be synchronized
  

  public class SynchronizedMethod {
      // Variables declaration
      public synchronized T Method1() {
          // Statements
      }
      public synchronized T method2() {
          // Statements
      }
      // Other methods
  }  
  

  
  T is return type. 
• Synchronized statement: It provides the synchronization for a group of statements rather than a method as a whole It needs to provide the object on which these synchronized statements will be applied, unlike in a synchronized method
  
  Syntax: synchronized statements on "this" object
  

  synchronized(this) {
      // statement 1
      // ...
      // statement N
  }
  

i) If you have two threads in one instance of a program, can they call A at the same time?
Not possible; read the above paragraph.
ii) Can they call A and C at the same time?
Yes. Only methods of the same object which are declared with the keyword synchronized can't be interleaved

References

• http://tianrunhe.wordpress.com/2012/05/04/can-two-threads-call-a-synchronized-method-and-normal-method-at-the-same-time/

Read More

Scheduling method calls in sequence

Problem

Suppose we have the following code:

class Foo {
public:
    A(.....); // If A is called, a new thread will be created 
                // and the corresponding function will be executed.
    B(.....); // same as above
    C(.....); // same as above
}
Foo f;
f.A(.....);
f.B(.....);
f.C(.....);

i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?
ii) Suppose we have the following code to use class Foo We do not know how the threads will be scheduled in the OS:

Foo f;
f.A(.....);
f.B(.....);
f.C(.....);
f.A(.....);
f.B(.....);
f.C(.....);

Can you design a mechanism to make sure that all the methods will be executed in sequence?

Solution

i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?

Semaphore s_a(0);
Semaphore s_b(0);
A {
    //
    s_a.release(1);
}
B {
    s_a.acquire(1); 
    //
    s_b.release(1);
}
C {
    s_b.acquire(1);
    //
}

ii) Can you design a mechanism to make sure that all the methods will be executed in sequence?

Semaphore s_a(0);
Semaphore s_b(0);
Semaphore s_c(1);
A{
    s_c.acquire(1); 
    // 
    s_a.release(1);
}
B{
    s_a.acquire(1); 
    // 
    s_b.release(1);
}
C{
    s_b.acquire(1); 
    // 
    s_c.release(1);
}

Thanks

References

• http://tianrunhe.wordpress.com/2012/05/04/scheduling-method-calls-in-sequence/

Read More

Design a class which provides a lock if no deadlocks

Problem

Design a class which provides a lock only if there are no possible deadlocks.

Solution

Deadlock will occur with a lock only if the locks can be held in a circular fashion; that is, if you define an ordering < on locks such that A < B only if lock A can be held with lock B also held, then<  is not a strict partial ordering. For example, if thread 1 tries to acquire lock A and then lock B, while thread 2 tries to acquire lock B and then lock A, then A < B and B < A, so < is not a strict partial ordering. Indeed, deadlock can occur if threads 1 and 2 each get locks A and B, respectively, then try to acquire the other lock.

So, a class can create a deadlock, by acquiring the control of the entire set of related locks that might be involved in such deadlocks. It can then, for example, require they be taken in some specific order (e.g. alphabetic ordering based on a name associated with each lock, arbitrary unique integers hardcoded in the source).

For our solution, we implement a wait / die deadlock prevention scheme.

Wait-die scheme: It is a non-preemptive technique for deadlock prevention. When transaction T_i requests a data item currently held by T_j, T_i is allowed to wait only if it has a timestamp smaller than that of T_j (That is T_i is older than T_j), otherwise T_i is rolled back (dies)
For example:
Suppose that transaction T₂₂, T₂₃, T₂₄ have time-stamps 5, 10 and 15 respectively. If T₂₂ requests a data item held by T₂₃ then T₂₂ will wait. If T₂₄ requests a data item held by T₂₃, then T₂₄ will be rolled back.
(definition taken from code bank.)

Java code

class MyThread extends Thread {
    long time;
    ArrayList<Resource> res = new ArrayList<Resource>();
 
    public ArrayList<Resource> getRes() {
        return res;
    }
 
    @Override
    public void run() {
        // Run infinitely
        time = System.currentTimeMillis();
        int count = 0;
        while (true) {
            if (count < 4) {
                if (Question.canAcquireResource(this, Question.r[count])) {
                    <span class="skimlinks-unlinked">res.add(Question.r</span>[count]);
                    count++;
                    <span class="skimlinks-unlinked">System.out.println("Resource</span>: ["
                            + Question.r[count - 1].getId()
                            + "] acquired by thread: [" + this.getName()
                            + "]");
                    try {
                        sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            } else {
                <span class="skimlinks-unlinked">this.stop</span>();
            }
        }
    }
 
    public long getTime() {
        return time;
    }
 
    public void setRes(ArrayList<Resource> res) {
        <span class="skimlinks-unlinked">this.res</span> = res;
    }
 
    MyThread(String name) {
        super(name);
    }
}

Thanks
References

• http://tianrunhe.wordpress.com/2012/05/01/design-a-class-which-provides-a-lock-if-no-deadlocks/

Read More

Thread safe and exception safe singleton design pattern

Problem

Implement a singleton design pattern as a template such that, for any given class Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton of type Foo Assume the existence of a class Lock which has acquire() and release() methods How could you make your implementation thread safe and exception safe?

Solution

Here is the code in cpp:

using namespace std;
// Place holder for thread synchronization lock
class Lock {
public:
    Lock() { // placeholder code to create the lock
    } 
    ~Lock() { // placeholder code to deallocate the lock
    } 
    void AcquireLock() { // placeholder to acquire the lock
    } 
    void ReleaseLock() { // placeholder to release the lock
    }
};
 
// Singleton class with a method that creates a new instance 
// of the * class of the type of the passed in template 
// if it does not already exist.
template <class T> class Singleton { 
private:
    static Lock lock;
    static T* object; 
protected:
    Singleton() { }; 
public:
    static T * instance(); 
};
Lock Singleton::lock;
 
T * Singleton::Instance() {
// if object is not initialized, acquire lock 
    if (object == 0) {
        lock.AcquireLock();
// If two threads simultaneously check and pass the first "if"
// condition, then only the one who acquired the lock first
// should create the instance 
        if (object == 0) {
            object = new T; 
        }
        lock.ReleaseLock(); 
    }
    return object; 
}
 
int main() {
// foo is any class defined for which we want singleton access 
    Foo* singleton_foo = Singleton<Foo>::Instance();
    return 0;
}

Thanks

References

• http://tianrunhe.wordpress.com/2012/05/01/thread-safe-and-exception-safe-singleton-design-pattern/

Read More

How to measure the time spent in a context switch

Problem

How can you measure the time spent in a context switch?

Solution

This is a tricky question, but let’s start with a possible solution.

A context switch is the time spent switching between two processes (e.g., bringing a waiting process into execution and sending an executing process into waiting/terminated state). i.e.  it is the computing process of storing and restoring the state (context) of a CPU so that execution can be resumed from the same point at a later time.

There are three potential triggers for a context switch:

Multitasking

Most commonly, within some scheduling scheme, one process needs to be switched out of the CPU so another process can run. This context switch can be triggered by the process making itself unrunnable, such as by waiting for an I/O or synchronization operation to complete. On a pre-emptive multitasking system, the scheduler may also switch out processes which are still runnable. To prevent other processes from being starved of CPU time, preemptive schedulers often configure a timer interrupt to fire when a process exceeds its time slice. This interrupt ensures that the scheduler will gain control to perform a context switch.

Interrupt handling

Modern architectures are interrupt driven. This means that if the CPU requests data from a disk, for example, it does not need to busy-wait until the read is over; it can issue the request and continue with some other execution. When the read is over, the CPU can be interrupted and presented with the read. For interrupts, a program called an interrupt handler is installed, and it is the interrupt handler that handles the interrupt from the disk.

When an interrupt occurs, the hardware automatically switches a part of the context (at least enough to allow the handler to return to the interrupted code). The handler may save additional context, depending on details of the particular hardware and software designs. Often only a minimal part of the context is changed in order to minimize the amount of time spent handling the interrupt. The kernel does not spawn or schedule a special process to handle interrupts, but instead the handler executes in the (often partial) context established at the beginning of interrupt handling. Once interrupt servicing is complete, the context in effect before the interrupt occurred is restored so that the interrupted process can resume execution in its proper state.

User and kernel mode switching

When a transition between user mode and kernel mode is required in an operating system, a context switch is not necessary; a mode transition is not by itself a context switch. However, depending on the operating system, a context switch may also take place at this time. 

The operating system must bring the state information of waiting processes into memory and save the state information of the running process.
So, roughly context switch happens because:

1. User process enters the kernel via system call or a trap (e.g. page fault) and requested data (e.g. file contents) is not yet available, so the kernel puts said user process into sleep state and switches to another runnable process.
2. Kernel detects that given user process consumed its full time quanta (this happens in code invoked from timer interrupt.)
3. Data becomes available for higher current priority process that is presently sleeping (this happens from code invoked from/around IO interrupts.)

In order to solve this problem, we would like to record timestamps of the last and first instruction of the swapping processes. The context switching time would be the difference in the timestamps between the two processes.

Let’s take an easy example: Assume there are only two processes, P1 and P2.
P1 is executing and P2 is waiting for execution. At some point, the OS must swap P1 and P2 — let’s assume it happens at the Nth instruction of P1. So, the context switch time for this would be Time_Stamp(P2_1) – Time_Stamp(P2_N)
Easy enough.

The tricky part is this: how do we know when this swapping occurs? Swapping is governed by the scheduling algorithm of the OS. We can not, of course, record the timestamp of every instruction in the process.
Another issue: there are many kernel level threads which are also doing context switches, and the user does not have any control over them.
Overall, we can say that this is mostly an approximate calculation which depends on the underlying OS. One approximation could be to record the end instruction timestamp of a process and start timestamp of a process and waiting time in queue.
If the total timeof execution of all the processes was T, then the context switch time = T – (SUM for all processes (waiting time + execution time)).

Reference

• http://tianrunhe.wordpress.com/2012/04/29/how-to-measure-the-time-spent-in-a-context-switch/
• http://stackoverflow.com/questions/2368384/write-a-c-program-to-measure-time-spent-in-context-switch-in-linux-os  
• http://en.wikipedia.org/wiki/Context_switch
• http://wiki.osdev.org/Context_Switching
• http://www.linfo.org/context_switch.html
• http://sudhansu-codezone.blogspot.in/2012/01/context-switch.html

Read More

Differences between thread and process

Problem

What’s the difference between a thread and a process?

Solution

Both processes and threads are independent sequences of execution.
Lets focus on difference - process vs threads.

Thread	Process
Threads (of the same process) run in a shared memory space. A thread is the entity within a process that can be scheduled for execution. All threads of a process share its virtual address space and system resources.	Processes run in separate memory spaces.
In addition, each thread maintains exception handlers,  a scheduling priority,  thread local storage,  a unique thread identifier, and  a set of structures the system will use to save the thread context until it is scheduled.	A process has a virtual address space,  executable code,  open handles to system objects,  a security context,  a unique process identifier,  environment variables,  a priority class,  minimum and maximum working set sizes,  and at least one thread of execution.
The thread context includes the thread's set of machine registers, the kernel stack, a thread environment block, and a user stack in the address space of the thread's process. Threads can also have their own security context, which can be used for impersonating clients.	Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads.

A process can be thought of as an instance of a program in execution. Each process is an independent entity to which system resources (CPU time, memory, etc.) are allocated and each process is executed in a separate address space. One process cannot access the variables and data structures of another process. If you wish to access another process’ resources, inter-process communications have to be used such as pipes, files, sockets etc.

A thread uses the same stack space of a process. A process can have multiple threads. A key difference between processes and threads is that multiple threads share parts of their state. Typically, one allows multiple threads to read and write the same memory (no processes can directly access the memory of another process). However, each thread still has its own registers and its own stack, but other threads can read and write the stack memory.

A thread is a particular execution path of a process; when one thread modifies a process resource, the change is immediately visible to sibling threads.

References

• http://tianrunhe.wordpress.com/2012/04/28/differences-between-thread-and-process/
• http://msdn.microsoft.com/en-us/library/windows/desktop/ms681917%28v=vs.85%29.aspx 
• http://stackoverflow.com/questions/200469/what-is-the-difference-between-a-process-and-a-thread

Read More