Mutual Exclusion Algprithm

[kangkan_14]

Can anyone tell me what is "mutual exclusion" and give a simple algorithm for it??

[apines]

In concurrent programming (using threads) you might have a resource that you cannot have it being accessed simultaneously.

For example, imagine that you have a linked list, and you want to remove a node from it. Imagine that in the middle of the removal, when not all the pointers are reattached, you have a context switch and another thread is accessing the linked list. The other thread does not know that the list is in a mess, and continues as usual. In order to avoid such scenarios, you need to to put the code that has to be completed without interruption inside what is called a critical section. In our example, lets create a global boolean variable that is true when someone is using the linked list. Thread A wants to delete a node, so it declares the variable as true, to indicate all the other threads not to use the linked list. After that, thread A continues with the node removal. If a context switch occurs in the middle, to thread B, thread B will first check the the variable is false - if its true, it will sleep until it becomes true, and then will continue with what it wanted to do to the resource. When thread A is done with the node deletion, it will change the variable back to false, letting other threads use the resource.

This is a very simple scenario. Few keywords that you might want to look for regarding mutual exclusion are lock or mutex (http://en.wikipedia.org/wiki/Lock_(computer_science)) and semaphore (http://en.wikipedia.org/wiki/Semaphore_(programming)).

[Dhruv Gairola]

mutual exclusion is best exemplified by the readers and writers problem (this is a standard textbook scenario taught in universities). if ur dealing with mutex, you have to know this first.

http://en.wikipedia.org/wiki/Readers-writers_problem