Monthly Archives: October 2012

Deadlock Characterization

There are some necessary conditions for deadlock to happen. They are:

1. Mutual Exclusion: Only process at a time can use the resource. Suppose p1 is holding the resource. If another process p2 requests for this resource, p2 is kept waiting. p2 is delayed until resource is released.

2. Hold and Wait: Here the process is holding one resource and it wants to acquire additional resources. These additional resources are held by other processes. So this process holds some resources and waits for other resources to be released.

3. No preemption: Resources cannot be preempted. A process must give away it’s resources voluntarily after it has done it’s job.

4. Circular Wait: Consider p0,p1,p2 all are waiting processes. p0 waits for a resource held by p1, p1 waits for resource held by p2 and p2 waits for resource held by p0.

We could predict deadlocks by using graphs called Resource Allocation Graphs.

Deadlock – Getting Started

Well, I hope the readers have some idea about process synchronization. You may refer my friend’s blog http://priyachalakkal.wordpress.com/tag/semaphores/ to understand about mutual exclusion problem and use of semaphore much clearly.

All-rite! so let’s start with Deadlock. Consider a multiprogramming environment. Here several processes compete for finite number of resources. What if one process P1 waits for a resource R1 which is currently held by some other process P2? P1 enters into a waiting state. There are chances that P1 never enters the ready state since the resources it needs are always occupied by some other process. Such a situation is referred as deadlock.

Silberschatz book explains this with a beautiful example. Consider a system with 3 CD drives and 3 processes. Suppose each of the process holds one of these CD Drives, and they now request for CD Drive held by some other process. Here the 3 processes will be in a deadlock state. Let’s discuss with some more example.

Consider this pthread program.

void *one(void *arg)
{
    pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
  /* D0 $0me Task */

    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);

    pthread_exit(0);
}

void *two(void *arg)
{
    pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
    /* D0 $0me Task */

    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);

    pthread_exit(0)
}

Now assume two threads are created. Both of them have access to both the mutex_locks. Thread1 runs in function ‘one’, thread2 runs in function ‘two’. So, thread_one acquires lock in the order first_mutex and second mutex. Whereas thread_two acquires lock in the order second_mutex and first_mutex. This is an example for deadlock where both keeps waiting to acquire the lock. (thread_1 attempts to lock mutex_one whereas thread_2 attempts to lock mutex_two.)

Lets discussion the Deadlock characterization in the next post.

Insertion Sort

Input: sequence of n nos a1,a2,a3…
Output: permutation of those numbers such that a1′<=a2′<=a3′..
It’s an effective algo for sorting small no of elements.

Find the correct position and the insert it
To find the correct position we compare with the nos already present
Check with each element. The whole array would be sorted after the process. i.e, check with each element and insert it before or after.

So It takes in i/p an array of n elements A[1-n] in sorted order
During insertion, the nos are rearranged within the array and sorted.


void insertion_sort(int unsorted[],int number_of_elements)
{
 int i,j,key;
 for(j=2;j&lt;=number_of_elements;j++)
 {
key=unsorted[j];
i=j-1;
while(i>0 && unsorted[i]>key)
{
unsorted[i+1]=unsorted[i];
i=i-1;
}
unsorted[i+1]=key;
}
}

Just an example
5 | 2 | 4 | 6 | 1 | 3 |
Key = 2 unsorted[j]
unsorted[i]>key, 5>2
unsorted[i+1]=unsorted[i], unsorted[2]=unsorted[1]=5
i=i-1=0, unsorted[i+1]=key=2

2 | 5 | 4 | 6 | 1 | 3 |
2 | 4 | 5 | 6 | 1 | 3 |
1 | 2 | 4 | 5 | 6 | 3 |    in loop. Checks with all previous elements
1 | 2 | 3 | 4 | 5 | 6 |

Complete implementation can be found at https://github.com/sowmyaravidas/Sorting-Algorithms

Selection Sort

Here we find the smallest element in the list and swap it with the first element. Then the second smallest, swapping with second element and so on. This is done till (n-1) times. And number of swaps required is n-1.

5 4 3 2 1
1 4 3 2 5
1 2 3 4 5
1 2 3 4 5
Well, the time complexity is O(n*n) which is same as https://sowmyaravidas.wordpress.com/2012/10/06/bubble-sort/

But selection is better since number of swaps required is less.

void selection_sort(int unsorted[],int number_of_elements)
{
int minimum;
int temp;
int minimum_position;
for(int i=0;i<number_of_elements;i++)
   {
    minimum=unsorted[i];
    for(int j=i+1;j<number_of_elements;j++)
    {
     if(minimum>unsorted[j])
     {
      minimum=unsorted[j];
      minimum_position=j;

      temp=unsorted[i];
      unsorted[i]=unsorted[minimum_position] ;
      unsorted[minimum_position]=temp;
      }
    }
  }
}

Complete implementation of the code can be found at https://github.com/sowmyaravidas/Sorting-Algorithms

Bubble Sort

This is a brute force method of sorting.  Compare the successive elements from position 1 to last. This is one
iteration. Do till (n-1) times.

5 4 3 2 1
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
This is iteration1. So at the end, maximum element moves to the end.

The time complexity of this algorithm is O(n*n).


 void bubble_sort(int unsorted[],int n)
 {
     int temp;
    for(int i=0;i<number_of_elements-1;i++)
    {
       for(int j=0;j<number_of_elements-i-1;j++)
       {
            if(unsorted[j]>unsorted[j+1])
             {
                 temp=unsorted[j];
                 unsorted[j]=unsorted[j+1];
                 unsorted[j+1]=temp;
             }
        }
     }

Complete implementation can be found at https://github.com/sowmyaravidas/Sorting-Algorithms