spookymulder83
BAN USER- 0of 0 votes
AnswersA program has two functions 'reader_func' and 'writer_func'. The reader_func reads shared data and contains a critical section. The writer_func writes to shared data and contains a critical section.
Reader threads call reader_func. Writer threads call writer_func.
The condition is multiple reader threads can access the critical section at the same time as long as they don't access the critical section along with a writer. Only a single writer thread can access the critical section, i.e. no reader or other writer threads are allowed.
Give the code segment, add code that uses mutexes that controls access to the critical sections so that the shared data is not corrupted and satisfies the give conditions. You can create as many mutexes and global variables as you want. Don't emphasize too much on syntax as to how to acquire and release locks on mutexes. Just use mutex.acquire() and mutex.release() .
Code segment:
- spookymulder83void reader_func() { //critical section } void writer_func() { //critical section }
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Threads
int reader_count = 0; //Keeps track of reader count
Mutex csMutex; //Mutex for the critical section.
Mutex readerMutex; //Mutex for the reader_count access. If you don't have this the reader_count will get corrupted.
void reader_func()
{
readerMutex.acquire();
if(reader_count == 0)
csMutex.acquire();
reader_count++;
readerMutex.release();
//critical section
readerMutex.acquire();
reader_count--;
if(reader_count == 0)
csMutex.release();
readerMutex.release();
}
void writer_func()
{
csMutex.acquire();
//critical section
csMutex.release();
}
1. Store the index of the last element of the array (say in 'last').
2. Let x = rand()%M. x will be in [0,M-1] range. Output arr[x] and replace arr[x] with arr[last]. Do last--.
3. Repeat this step for N times, each time applying the mod operation with dividend one less than in the previous step i.e. rand()%(M-1), rand()%(M-2) and so on.
4. Time: O(N). Space: O(1).
5. In the above algorithm, you will be changing the array contents. If you want to maintain the array in the same state, you can keep track of all the changes you are making to the array and undo them after you printout the N values. This is better than making a copy of the array when M is large.
1. Given an array of size 52 (indexes 0 to 51) we want to shuffle it such that no card will get the same position as previously.
2. Start from the end of the array i.e. at index 51. Generate a random number x between [0,50] using rand() and mod 51 operation. Swap arr[51] and arr[x].
3. Repeat the same step for the rest of the array. That is, in the second step go to index 50. Generate a random number x between [0,49]. Swap arr[50] and arr[x].
4. In the end you come to index 0. You don't have to worry about arr[0] not being swapped as when you were processing at index 1 it would have been definitely been swapped with arr[0].
If I understand your algorithm correctly, when array1 is 1,1 and array2 is 2,2 then x will be 0, but the arrays are not equal.
- spookymulder83 November 16, 2010Check
geeksforgeeks.org/?p=2105
for O(log n) time algorithm.
Its actually ceil(2.58) steps i.e. 3 steps.
For 3^6 you calculate a = (3x3x3) in 2 steps and a x a in 1 step .
Repjudydschultz1234, Android test engineer at Eterno Infotech Pvt Ltd
Spent a weekend researching weebles in Nigeria. My current pet project is developing strategies for how to break someone's ...
Repgladysloweg, Brokerage clerk at Bell Markets
I am Gladys from Defiance city . I am working as a Brokerage clerk with tasks associated with securities such as ...
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.
- spookymulder83 December 17, 20102. 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.