Microsoft Interview Question
Software Engineer / Developers/* Algorithm: //assuming writer thread has the highest priority i.e. readers wont enter CS if writer is waiting for access to CS
* reader_func():
* if writer thread not waiting then proceed
* if less than max_readers atomically increment semaphoreVar
* enter CS
* acquire semaphoremutex.
* decrement, check if writer is waiting and semaphoreVar==0.
* if yes then notify writer
* release semaphoremutex
* else
* max_readers already in CS so try later
* else
* writer thread waiting so try after it is done
*
* writer_func():
* acquire semaphoremutex
* if semaphoreVar!=0 then requestFlag; [release semaphoremutex and wait on condition variable]
* when notified acquire semaphoremutex
* process CS
* release semaphoremutex
*/
int MAX_READERS = 10 /*max readers 10*/ , cSem = 0 /*counting semaphore*/;
volatile bool requestCS = false; //this flag is used by writer to request CS.
WaitCondition waitForReadersExit; //condition variable which is invoked when readers==0.
Mutex semMtx; //mutex for atomically operating on cSem variable
void reader_func()
{
if(!requestCS){ //if writer thread not waiting then proceed
if(testAndIncrement(cSem,MAX_READERS)){ //if cSem less than MAX_READERS then increment it atomically proceed
//Critical Section processing
semMtx.acquire();
--cSem;
if(requestCS && cSem==0) //if writer requested CS and no readers are in CS then
waitForReadersExit.notify(semMtx);//unlock semMtx and notify writer
else
semMtx.release();
}else{
//max readers in CS. Try later
}
}else{
//writer has placed request, wait till writer is done.
}
}
void writer_func()
{
semMtx.acquire();
if(cSem!=0){
requestCS = true;
waitForReadersExit.wait(semMtx) //unlocks 'semMtx' and waits on the condition variable
}
//critical section
requestCS = false;
semMtx.release();
}
//atomically test and increment semaphore variable
bool testAndIncrement(semVar,MAX_READERS){
semMtx.acquire();
if(MAX_READERS>semVar){
++semVar; semMtx.release(); return true;
}semMtx.release();
return false;
}
1. The interviewer wanted me to discuss the pros and cons of my solution. Given a scenario where there will be lots of readers and few writers, the writers might not acquire a lock on csMutex at all give the way the code is written. There will always be bunch of readers accessing the critical section and all writers will have to most likely wait forever. So the above code favors the readers.
2. How would you change the above code to favor the writers? Whenever a writer is waiting, come up with a mechanism that won't allow any more readers into the critical section or acquire the lock. The existing readers will be allowed to finish and the last reader will release the lock. Once this is done the waiting writer will acquire the lock and do its task.
3. You can also put a limit on the number of readers that can access the critical section. Once in a while or when a writer is waiting, change the limit to 0 so that no new reader can acquire the lock thereby allowing a writer to acquire the lock on the mutex.
4. GekkoGordan's code handles this case. Good.
gekko's code is good. But it won't handle multiple writers because if multiple writers are waiting on a single variable and all are notified and only one proceeds into Critical section. after that the other writers would have equal priority as readers because requestCS is set to false by first writer. So changing the requestCS variable to a counting variable will assure all writers are done before readers proceed.
woow..I saw other comments from gekko to be sarcastic, funny and criticizing but he does know how to answer problems. hmmm...
nice solution
class ReaderWriterLock
{
Mutex noReader;
Mutex noWriter;
Mutex countMutex;
unsigned int readers;
public:
void AcquireReader()
{
noWriter.Acquire();
countMutex.Acquire();
if (++readers == 1)
noReader.Acquire();
countMutex.Release();
noWriter.Release();
}
void ReleaseReader()
{
countMutex.Acquire();
if (--readers == 0)
noReader.Release();
countMutex.Release();
}
void AcquireWriter()
{
noReader.Acquire();
noWriter.Acquire();
}
void ReleaseWriter()
{
noWriter.Release();
noReader.Release();
}
};
Mutex writerRequestMutex;
bool writerRequest=false;
int readerCount=0;
const int Max_Readers = 10;
void read_func()
{
writerRequestMutex.lock();
while(writerRequest!=false && readerCount>=Max_Readers)
{
writerRequestMutex.unlock();
doSleep();
writerRequestMutex.lock();
}
readerCount++;
writerRequestMutex.unlock();
//critical section
writerRequestMutex.lock();
readerCount--;
writerRequestMutex.unlock();
if(readerCount==0)
writerRequestMutex.wake();
}
void write_func()
{
writerRequestMutex.lock();
while(readerCount!=0)
{
writerRequest=true;
writerRequestMutex.wait();
}
//critical section
writerRequest=false;
writerRequestMutex.unlock();
}
Slight mistake: in the write_func you should set writerRequest=true before the lock and then wait on the lock. No need for while loop:
void write_func()
{
writerRequest=true; // This should let readers relinquish the lock and goto sleep
writerRequestMutex.lock();
// critical section
writerRequest = false;
writerRequestMutex.unlock();
}
Also there is no wake function on a mutex (as you indicated in your code)
/* Reader-writer lock */
int reader_ctr=0;
void reader_func() {
mutex_acquire(&reader);
reader_ctr++;
if(reader_ctr==1) mutex_acquire(&writer);
mutex_release(&reader);
//critical section
mutex_acquire(&reader);
reader_ctr--;
if(reader_ctr==0) mutex_release(&writer);
mutex_release(&reader);
}
void writer_func() {
mutex_acquire(&writer);
//critical section
mutex_release(&writer);
}
- spookymulder83 December 17, 2010