Solving Reader-Writer Problem

I know may be i bored you with basic semaphores and semaphore problems;but I hope it will be useful for the people who are just introducing with them.

Reader Writer Problem with Semaphores:

If one process is reading an object , other processes can read it too ;but they can not write or modify this object .
Generally the case is like that:
While Writing -> Can't write or read the object
While Reading->Can read ;but can not modify the object.

Shared Data:

semaphore mutex , wrt;
int readcount;

//Initially
mutex=1 , wrt =1, readcount=0;

Writer:

wait(wrt);//wrt-- , wrt=0;
writeToFile();//...Writing is performed
signal(wrt);//wrt++ , wrt=1;

While wrt=1 the writing process can be done by other processes.
While wrt=0 the other processes can not write to the object.

The reader process is a bit more complex.

Reader:

wait(mutex);//mutex--, mutex=0
readcount++;// readcount=1
if(readcount==1)
{wait(wrt);}
signal(mutex);

readTheObject();//...Reading is performed

wait(mutex);
readcount--; // readcount=0;
if(readcount==0) //Check if the reading is performed
signal(wrt);
signal(mutex);

The codes between wait(mutex) and signal(mutex) are the places where we don't want other processes access to avoid ambiguousness.

An Example about how this code works:
1 2 3
Reader1:readcount=1,wrt=0,readcount=1 .
Reader2:readcount=2,wrt=0, readcount=0,wrt=1.
Writer: writing, writing is finished.

Solving Producer - Consumer Problem with Semaphores

This problem also known as bounded buffer problem.Here is its solution with binary semaphores:

Pseudocode:

Semaphore full , empty , mutex;
full=0;
empty=n;//n=number of resouces
mutex=1;
//s is a semaphore
Wait(s):
while(s<=0) do nothing;
s--;
Signal(s):
s++;

Producer():
produce_item();
Wait(empty);//empty--, n-1
Wait(mutex);//mutex=0
enter_Item();// We added item to the buffer
Signal(mutex);//mutex=1;
Signal(full);//full++;

Consumer():
wait(full); //full--
wait(mutex);//mutex--
remove_item();//removed item from the buffer
signal(mutex);// signal++
signal(empty);//empty++
consume_item();

The area between wait(mutex) and signal(mutex) also known as protected area because of mutual exclusion , when a process want to access its CS it can't.

Bakery Algorithm

Bakery algorithm is an algorithm for multiprocessing units which share the same resouces that i discovered while i was studying for my OS exam.Here is some information about it:

Definiton of the problem:
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Dr Leslie Lamport which is intended to improve the robustness of multiple thread-handling processes by means of mutual exclusion.

it is common for multiple threads to simultaneously access the same resources. They either try to write into the same memory location, or one thread reads a location before another has finished writing into it. This is undesirable as it can end in hazardous loss

Algorithm to solve the problem:

• Notation <= lexicographical order (ticket # , process id #)

1. (a , b)<(c,d) if (a)<(c) or if a=c and (b)<(d). Here we compare the process numbers and the values.The process which has a less process will access the resource.If they are same we will compare the values.
2. max (a0,…, an-1) is a number, k, such that k ≥ ai for i - 0, …, n – 1

Shared data

boolean choosing[n];
int number[n];
Data structures are initialized to false and 0 respectively

The pseudocode:

do {
choosing[i] = true;
number[i] = max(number[0], number[1], …, number [n – 1])+1;
choosing[i] = false;
j=0;
while(j is smaller than n)
while (choosing[j]) ;
while ((number[j] != 0)&& ( (number[j],j)<(number[i],i)) }
j++;
}
critical section
number[i] = 0;
reminder section}while (1);