Adobe Interview Question
Software Engineer / DevelopersCountry: India
Simple use an integer count:
Reader:
{
if(count>=0) //inside critical section
count++;
}
//reader is reading file
{
count--;
notifyAll(); //inside critical section
}
Writer:
will write only if count==0;
count=-1;
Working code:
public class ReaderWriter implements Runnable{
static int count=0;
static Reader r;
static Writer w;
public void run(){
Random ran=new Random();
if(ran.nextInt(2)==1)
r.read();
else
w.write();
}
public static void main(String[] args)
{
ReaderWriter rw=new ReaderWriter();
r=new Reader(rw);
w=new Writer(rw);
Thread[] t=new Thread[20];
for(int i=0;i<20;i++){
t[i]= new Thread(rw);
t[i].start();
}
}
}
class Writer{
ReaderWriter r;
public Writer(ReaderWriter r){
this.r=r;
}
public void write(){
synchronized(r){
while(r.count!=0){
try {
r.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
r.count=-1;
}
try {
TimeUnit.MILLISECONDS.sleep(100);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
//writing file
synchronized(r){
r.count=0;
System.out.println("Written file"+" "+r.count);
r.notifyAll();
}
}
}
class Reader{
ReaderWriter r;
public Reader(ReaderWriter r){
this.r=r;
}
public void read()
{
synchronized(r){
while(r.count==-1){
try {
r.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
r.count++;
}
try {
TimeUnit.MICROSECONDS.sleep(1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
//reading file
synchronized(r){
r.count--;
System.out.println("Read file"+" "+r.count);
if(r.count==0)
r.notifyAll();
}
}
}
consider four state variable protected by lock and two two conditions:
AR: active reader
WR:waiting reader
AW:active writer
WW:waiting writer
Reader() {
lock.Acquired()
while (AW+WW>0) {
WR++
okToRead.Wait(lock);
WR--;
}
AR++
lock.Release()
read file
lock.Acquired()
AR--;
if (AR==0 && WW>0) {
okToWrite.Signal();
}
lock.Release()
}
Writer()
{
lock.Acquired();
while(AW+AR>0) {
WW++
okToWrite.wait(lock)
WW--
}
AW++;
lock.Release();
write to the file
lock.Acquired();
AW--;
if (WW > 0) {
okToWrite.signal(lock);
} else if (WR>0) {
okToRead.signal(lock).
}
lock.Release()
}
}
The below sequence of operations will ensure that p1 begins when p2 ends and vice versa.This is just a crude representation.
P1 P2
Wait Event
Enter Critical Section Wait Event
P1.Read(); Enter Critical Section
Exit Critical Section P2.write();
SignalEvent Exit Critical Section
Signal Event
this is a special case of readers-writers problem where we have only 1 reader and 1 writer.
it is solved using "lightswitch concurrency pattern", i.e. first reader thread which enters the section "turns on the light" (acquires the writer mutex) while the last one which leaves the section "turns the light off" ( releases mutex)
p1:
- Anonymous April 23, 2012Wait Event :
Enter Critical Section :
Exit Critical Section :
Signal Event
P2:
Wait Event :
Enter Critical Section :
Exit Critical Section :
Signal Event