Semaphore VS Mutex

Dutch computer scientist, introduced the concept of a binary semaphore into modern programming to address possible race conditions in concurrent programs. His very simple idea was to use a pair of function calls to the operating system to indicate entering and leaving a critical region. 

This was achieved through the acquisition and release of an operating system resource called a semaphore.

P -> To try and lower, 

V -> To raise, To increase

 

With this model the first task arriving at the P(S) [where S is the semaphore] call gains access to the critical region. If a context switch happens while that task is in the critical region, and another task also calls on P(S), then that second task (and any subsequent tasks) will be blocked from entering the critical region by being put in a waiting state by the operating system.

At a later point the first task is rescheduled and calls V(S) to indicate it has left the critical region. The second task will now be allowed access to the critical region.

 

A variant of Dijkstra’s semaphore was put forward by another Dutchman, Dr. Carel S. Scholten. In his proposal the semaphore can have an initial value (or count) greater than one. This enables building programs where more than one resource is being managed in a given critical region. For example, a counting semaphore could be used to manage the parking spaces in a robotic parking system. The initial count would be set to the initial free parking places. Each time a place is used the count is decremented. If the count reaches zero then the next task trying to acquire the semaphore would be blocked (i.e. it must wait until a parking space is available). Upon releasing the semaphore (A car leaving the parking system) the count is incremented by one.

Scholten’s semaphore is referred to as the General or Counting Semaphore, Dijkstra’s being known as the Binary Semaphore.

 inherent dangers associated with using the semaphore

• Accidental release

 a semaphore isn’t correctly acquired but is then released. When the counting semaphore is being used as a binary semaphore (initial count of 1 – the most common case) this then allows two tasks into the critical region.

• Recursive deadlock   

Deadlock :

 Deadlock occurs when tasks are blocked waiting on some condition that can never become true

 

 There are three possible deadlock situations associated with the semaphore:

• Recursive Deadlock

Recursive deadlock can occur if a task tries to lock a semaphore it has already locked. This can typically occur in libraries or recursive functions; for example, the simple locking of malloc being called twice within the framework of a library.

• Deadlock through Death

What if a task that is holding a semaphore dies or is terminated? If you can’t detect this condition then all tasks waiting (or may wait in the future) will never acquire the semaphore and deadlock. To partially address this, it is common for the function call that acquires the semaphore to specify an optional timeout value.

• Cyclic Deadlock (Deadly Embrace)

• Priority inversion

• Semaphore as a signal (for syncronisation not mutual exclusion)

Unfortunately, the term synchronization is often misused in the context of mutual exclusion. Synchronization is, by definition “To occur at the same time; be simultaneous”. Synchronization between tasks is where, typically, one task waits to be notified by another task before it can continue execution (unilateral rendezvous). A variant of this is either task may wait, called the bidirectional rendezvous. This is quite different to mutual exclusion, which is a protection mechanism. However, this misuse has arisen as the counting semaphore can be used for unidirectional synchronization. For this to work, the semaphore is created with a count of 0 (zero).

Note that the P and V calls are not used as a pair in the same task. In the example, assuming Task1 calls the P(S) it will block. When Task 2 later calls the V(S) then the unilateral synchronization takes place and both task are ready to run (with the higher priority task actually running). 

Unfortunately “misusing” the semaphore as synchronization primitive can be problematic in that it makes debugging harder and increase the potential to miss “accidental release” type problems, as an V(S) on its own (i.e. not paired with aP(S)) is now considered legal code.

 Now shall look at how the mutex address most of the weaknesses of the semaphore.

To address the problems associated with semaphore, a new concept was developed during the late 1980’s.

The mutex is similar to the principles of the binary semaphore with one significant difference: the principle of ownership. 

Ownership is the simple concept that when a task locks (acquires) a mutex only it can unlock (release) it. If a task tries to unlock a mutex it hasn’t locked (thus doesn’t own) then an error condition is encountered and, most importantly, the mutex is not unlocked.

 If the mutual exclusion object doesn’t have ownership then, irrelevant of what it is called, it is not a mutex. 

The concept of ownership enables mutex implementations to address the problems discussed in part 1:

1. Accidental release
2. Recursive deadlock
3. Task-Death deadlock
4. Priority inversion
5. Semaphore as a signal

Accidental Release
As already stated, ownership stops accidental release of a mutex as a check is made on the release and an error is raised if current task is not owner.

Recursive Deadlock
Due to ownership, a mutex can support relocking of the same mutex by the owning task as long as it is released the same number of times.

Priority Inversion
With ownership this problem can be addressed using one of the following priority inheritance protocols:

• [Basic] Priority Inheritance Protocol
• Priority Ceiling Protocol

The Basic Priority Inheritance Protocol enables a low-priority task to inherit a higher-priorities task’s priority if this higher-priority task becomes blocked waiting on a mutex currently owned by the low-priority task. The low priority task can now run and unlock the mutex – at this point it is returned back to its original priority.

The details of the Priority Inheritance Protocol and Priority Ceiling Protocol (a slight variant) will be covered in part 3 of this series.

Death Detection
If a task terminates for any reason, the RTOS can detect if that task current owns a mutex and signal waiting tasks of this condition. In terms of what happens to the waiting tasks, there are various models, but two doiminate:

• All tasks readied with error condition;
• Only one task readied; this task is responsible for ensuring integrity of critical region.

When all tasks are readied, these tasks must then assume critical region is in an undefined state. In this model no task currently has ownership of the mutex. The mutex is in an undefined state (and cannot be locked) and must be reinitialized.

When only one task is readied, ownership of the mutex is passed from the terminated task to the readied task. This task is now responsible for ensuring integrity of critical region, and can unlock the mutex as normal.

Mutual Exclusion / Synchronisation
Due to ownership a mutex cannot be used for synchronization due to lock/unlock pairing. This makes the code cleaner by not confusing the issues of mutual exclusion with synchronization.

 

Caveat
A specific Operating Systems mutex implementation may or may not support the following:

• Recursion
• Priority Inheritance
• Death Detection

the mutex is a significantly safer mechanism to use for implementing mutual exclusion around shared resources. Nevertheless, there are still a couple of problems that use of the mutex (in preference to the semaphore) will not solve. These are:

• Circular deadlock
• Non-cooperation

Circular Deadlock
Circular deadlock, often referred to as the “deadly embrace” problem is a condition where two or more tasks develop a circular dependency of mutual exclusion. Simply put, one task is blocked waiting on a mutex owned by another task. That other task is also block waiting on a mutex held by the first task.

Priority Ceiling Protocol

With the Priority Ceiling Protocol (PCP) method each mutex has a defined priority ceiling, set to that of the highest priority task which uses the mutex. Any task using a mutex executes at its own priority – until a second task attempts to acquire the mutex.  At this point it has its priority raised to the ceiling value, preventing suspension and thus eliminating the “hold and wait” condition.

Difference between binary semaphore and mutex

 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. 

They are NOT the same thing. They are used for different purposes!
While both types of semaphores have a full/empty state and use the same API, their usage is very different.

Mutual Exclusion Semaphores
Mutual Exclusion semaphores are used to protect shared resources (data structure, file, etc..).

A Mutex semaphore is "owned" by the task that takes it. If Task B attempts to semGive a mutex currently held by Task A, Task B's call will return an error and fail.

 

Signals

Signals are software interrupts

• Signals are asynchronous events generated by the operating system in response to certain conditions
• Every signal has a name starting SIGxxxx eg. SIGALRM

• All signals are defined in /usr/include/signal.h
• The OS supports a standard set of signals
• Eg Linux has 31 signals

• Provides support for additional application defined signals realtime extensions

Ctrl-C key generates SIGINT

When certain hardware exceptions occur
• Divide by 0(SIGFPE), invalid memory reference(SIGSEGV) etc.
• Exception detected by h/w, kernel is notified, kernel generates the signal and
sends it to the process

• Kill command to send signal to a process
• Kill function to send signal from one process to another

When certain software conditions occur
• SIGPIPE, when there is a write to a pipe with no reader
• SIGALRM, when a software timer expires

SIGKILL and SIGSTOP cannot be caught/ignored by the process.
Can you think of why this is so ?

SIGCHLD sent by child process to parent process

Sample signal handler
#include <stdio.h>
void sig_handler( int );
main( )
{
if( signal( SIGINT, sig_handler) < 0 )
printf( “Error: cannot catch SIGINT\n” );
if( signal( SIGUSR1, SIG_IGN ) < 0 )
printf( “Error: cannot ignore SIGUSR1 );
while(1);
}
void sig_handler( int signo )
{
if( signo == SIGINT )
printf( “SIGINT received\n” );
}

Disposition of signal is the action associated with a signal


• Ignore the signal • SIGKILL and SIGSTOP cannot be ignored

• If certain signals are ignored( such as hardware exceptions), behaviour is undefined
 • Catch the signal
 • Kernel invokes the signal handler function defined in the program
• Else, default action applies, which is one of
• Terminate process and may generate core
• Ignore signal • Stop process

Basic Thread Concepts

Threads

In shared memory multiprocessor architectures, threads can be used to implement parallelism.

A thread is an independent Schedulable entity i.e.

Technically, a thread is defined as an independent stream of instructions that can be scheduled to run as such by the operating system

• To the software developer, the concept of a "procedure" that runs independently from its main program may best describe a thread.
• To go one step further, imagine a main program (a.out) that contains a number of procedures. Then imagine all of these procedures being able to be scheduled to run simultaneously and/or independently by the operating system. That would describe a "multi-threaded" program

Before understanding a thread, one first needs to understand a UNIX process

. A process is created by the operating system, and requires a fair amount of "overhead"

 Processes contain information about program resources and program execution state, including:

• Process ID, process group ID, user ID, and group ID
• Environment    (in which it is running)
• Working directory. (where it is running)
• Program instructions (code seg)  Prog counter
• Registers (??)
• Stack (seg)  Stack Pointer
• Heap (seg) 
• File descriptors  
• Signal actions   
• Shared libraries 
• Inter-process communication tools (such as message queues, pipes, semaphores, or shared memory).

                     UNIX PROCESS

• THREADS WITHIN A UNIX PROCESS

• Threads use and exist within these process resources, yet are able to be scheduled by the operating system and run as independent entities largely because they duplicate only the bare essential resources that enable them to exist as executable code.

• This independent flow of control is accomplished because a thread maintains its own:
  • Stack pointer
  • Registers
  • Scheduling properties (such as policy or priority)
  • Set of pending and blocked signals
  • Thread specific data.

• So, in summary, in the UNIX environment a thread:
  • Exists within a process and uses the process resources
  • Has its own independent flow of control as long as its parent process exists and the OS supports it
  • Duplicates only the essential resources it needs to be independently schedulable
  • May share the process resources with other threads that act equally independently (and dependently)
  • Dies if the parent process dies - or something similar
  • Is "lightweight" because most of the overhead has already been accomplished through the creation of its process.

• Because threads within the same process share resources:
  • Changes made by one thread to shared system resources (such as closing a file) will be seen by all other threads.
  • Two pointers having the same value point to the same data.
  • Reading and writing to the same memory locations is possible, and therefore requires explicit synchronization by the programmer.

A thread is the fundamental unit of execution within an application.

A running application consists of at least one thread.

Each thread has its own stack and runs independently from the application’s other threads.

Threads share the resources used by the application as it runs, such as file handles
or memory, which is why problems can occur.

Data corruption is a common side effect of having two threads simultaneously write data
to the same block of memory.

Threads can be implemented in different ways.

On most systems, threads are created and managed by the operating system
Such threads are often called native or kernel-level threads.

Clone () in Linux

Number of threads that can be executed at any given instant is limited by the number of processors
in the computer,

Operating system will rapidly switch from thread to thread, giving each
thread a small window of time in which to run. This is known as preemptive threading

A cooperative model, on the other hand, requires a thread to explicitly suspend its own execution in order to let other threads run.

Swapping one thread out and another in is referred to as a context switch.

System Threads versus User Threads

A system thread is created and managed by the system. The first (main) thread of an application is a system thread, and the application often exits when the first thread terminates

General Ex: UI
Applications that display user interfaces main thread in such an application is usually called the event thread.
 threads are created to handle time-consuming operations like network access.

thread synchronization =>  data corruption

two fundamental thread synchronization constructs are monitors and semaphores.

DEF :
A thread is a seq of inst executed by a processor for a particular Job. It has its own program start addr hence a prog counter and its own stack space hence Stack pointer.
Each thread has a status {processor registers, PC , SP, all other flags and control registers}

Threads VS Process

Threads Better

1 . Sharing Data Between Threads is easy , where as in process it is not ( create a shared mem or Pipe )
2. Creation : Threads faster, (Context gen lower for threads)

Processs Better
 
Thread Safety In multi threading , functions called should be thread-safe or should be called in Thread-safe manner. (Thread Safety) .  multiprogramming need not bother about this
One to All One bug in a thread (lets say invalid pointer access ) can damage all the threads attached to the process. Why ? Since they are all attached to same address space. Process are more isolated from each other.
VM SPace Each thread fights for Finite Virtual Addr Space of "Host Process". In particular every threads stack and local storage consumes a part of Process virtual Address Space which is unavail for other threads.

Though the Process Addr space is typicaly Huge (3 GB on x86 - 32) , this might be a limitation if a process req large no of threads or a thread req large mem

Gen Process can have a total virtual add space

Other factors
Dealing with Signals in a multi threaded appl ? Desirable to avoid.
All threads  execute same program code
Apart from process data, threads also share other info such as FIle desc, Signal Disposition, current working dir,UID GID etc.. this has both Advs/Disadvs.

Multiplication not with multiplication operator

Problem 1 Efficient way to multiply with 7

 Clue : Use bitwise operator
 << by one bit is multiply by 2
<< by 3 bits is multiply by 8.

Then substract the original number.

int multiplyBySeven(unsigned int n)
{
    /* Note the inner bracket here. This is needed
       because precedence of '-' operator is higher
       than '<<' */
    return ((n<<3) - n);
}

Note: Works only for positive integers only. Same concept can be used for fast multiplication by 9 or other numbers.

Problem 2 Add two numbers without using arithmetic operators 

Sum of two bits can be obtained by performing XOR (^) of the two bits.
Carry bit can be obtained by performing AND (&) of two bits.

int Add(int x, int y)
{
    // Iterate till there is no carry
    while (y != 0)
    {
        // carry now contains common set bits of x and y
        int carry = x & y;
 
        // Sum of bits of x and y where at least one of the bits is not set
        x = x ^ y;
 
        // Carry is shifted by one so that adding it to x gives the required sum
        y = carry << 1;
    }
    return x;
}

Recursive Solution

int Add(int x, int y)
{
    if (y == 0)
        return x;
    else
        return Add( x ^ y, (x & y) << 1);
}