Friday, January 8, 2010

Multithreading Basics

Process : In computing, a process is an instance of a computer program, consisting of one or more threads, that is being sequentially executed by a computer system.

Thread : A thread is defined as an independent stream of instructions that can be scheduled to run by the operating system. Threads are popular way to improve application through parallelism. The CPU switches rapidly back and forth among the threads giving illusion that the threads are running in parallel. Each thread has its own stack. Since thread will generally call different procedures and thus a different execution history. This is why thread needs its own stack.A thread has its own program counter (PC), register set, and a stack space. Threads are not independent of one other like processes as a result threads shares with other threads their code section, data section, OS resources such as open files and signals.


User Level Threads: They do not interact with the Kernal for their creation , they are created by user level libraries , the kernel does not see them as a separate threads and doesn't schedule them for execution it is all internal to the process the threads belong to. The advantages of these threads are their context switching are fast, and they can be implemented on an OS that doesn't support multithreading , The disadvantage is that if a thread gets blocked the whole process is blocked.



Kernel Level Threads: These threads are created and managed by system calls to the OS kernel. The Kernel maintains a thread table and are responsible for their scheduling.  The advantage of kernel level threads are that if a thread blocks the whole process is not blocked because the other threads belonging to the process are still running. And the disadvantage of this is that they are comparatively slower than user level threads.


Starvation : This term specifies that when a process is waiting for a resource to complete but never receives that resource. Starvation leads to deadlock and livelock(which is a special case when the processes keeps changing their state).

Deadlock : When two or more process are waiting for each other to release a resource or when more than two processes are waiting for resources held by each other in a circular chain. For example think that there are two process are running (ProcessA and ProcessB) and there are two resources (ResourceX and ResourceY), now ProcessA is holding ResourceX and to complete it requires ResourceY and ProcessB is holding ResourceY and to complete it requires ResourceX , so both the process are waiting for each other for the resource it requires to complete and as a result none of them complete , this is a deadlock.

A real life example is suppose two person are drawing lines on pages and there is one pencil and one ruler , now one of the person takes the pencil and is waiting for the ruler to draw the line whereas on the other hand the other person has the ruler and is waiting for the pencil.


Livelock: It is similar to a deadlock and occurs when two or more processes continually change their state in response to changes in the other processes. A real-world example of livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they both repeatedly move the same way at the same time.

 
Priority Inversion: When a high priority process is waiting for a resource that is held by a low priority process.

Race Condition: When two or more threads or processes are simultaneously trying to update a shared resource the final state of the resource is unpredictable. For example, let us assume that two threads T1 & T2 are trying to update the value of a global integer by 1. From our perspective the following sequence of steps should take place.

1. Int i = 0 (value in memory).
2. T1 reads the value of i from memory and loads it into the register1 (reg1 = 0).
3. T1 increments the value of reg1 to 1.
4. T1 sets the value of i in memory to reg1 (i = reg1) , so now the value of i in memory is 1.
5. T2 reads the value of i from memory and loads it into the register2 (reg2 = 1).
6. T2 increments the value of reg2 to 2.
7. T2 sets the value of i in memory to reg1 (i = reg2) , so now the value of i in memory is 2.
8. Int i = 2 (value in memory).


but as the sequence is unpredictable as both the threads run simultaneously, for example see the sequence below.


1. Int i = 0 (value in memory).
2. T1 reads the value of i from memory and loads it into the register1 (reg1 = 0).

3. T2 reads the value of i from memory and loads it into the register2 (reg2 = 0).
4. T1 increments the value of reg1 to 1.
5. T2 increments the value of reg2 to 1.
6. T1 sets the value of i in memory to reg1 (i = reg1) , so now the value of i in memory is 1.
7. T2 sets the value of i in memory to reg1 (i = reg2) , so now the value of i in memory is 1.
8. Int i = 1 (value in memory).


we get the wrong value as the final outcome , this is due to race condition.


Critical Section:  A critical section is a piece of code that access a shared resource and must not be executed by more than thread at a time.


Semaphore : A semaphore restricts the number threads that can simultaneously access a shared resource.A binary semaphore is similar to mutex.

Mutex :  Mutex is an object that is used to synchronize access to a shared resource using locking and unlocking mechanisms.

Condition Variable : A condition variable is used to synchronize to execution of threads via the thread notification mechanism (wait & notify).


No comments:

Post a Comment

Followers

About Me