can you please answer 4a and 4b.... a. The example code below shows a pair of pr

Question

can you please answer 4a and 4b....

a. The example code below shows a pair of processes (one reader, one writer) that use semaphores to allow (i) multiple reader processes to run simultaneously, while also ensuring (ii) the writer process can only enter its critical section if no readers are executing. Assuming the two semaphores and rwSem and rcSem are initialized to 1, and rdCnt is initialized to 0, explain how the two semaphores enable conditions (i) and (ii) above. Reader process do { down (rcSem): rdCnt++: if (rdCnt = 1) down (rwSem): up (rcSem): /* read shared data */down (rcSem): rdCnt --: if (rdCnt == 0) up (rcSem): } while (true): Writer process do { down (rwSem): /* write shared data up (rwSem): } while (true): b. Consider a multithreaded bank software package in which the following function is used to transfer money. Assume that the program contains a global of locks, locks [], with one entry per account number, such that locks [1] is the lock for account number i. void transfer money (int arc_acct, int dest_acct, int amt) { locks (arc_acct]. lock();//Lock account sending money lock [dest_acct]. lock ();//Lock account receiving money locks [dest_acct].unlock(): locks [arc_acct].unlock (): Explain how this function can deadlock if called in multiple threads, and rewrite (in pseudo-code or actual code) the function to remove the deadlock condition.

Explanation / Answer

4a.

Reader process:

Reader requests the entry to critical section.
If allowed:
it increments the count of number of readers inside the critical section. If this reader is the first reader entering, it locks(down) the "rwSem" semaphore to restrict the entry of writers if any reader is inside.
It then, signals(up) "rcSem" semaphore as any other reader is allowed to enter while others are already reading.
After performing reading, it exits the critical section. When exiting, it checks if no more reader is inside, it signals the semaphore "rwSem" as now, writer can enter the critical section.
If not allowed, it keeps on waiting.

Writer process:

Writer requests the entry to critical section.
If allowed i.e. down() gives a true value, it enters and performs the write. If not allowed, it keeps on waiting.
It exits the critical section.

Thus, the mutex "rwSem" is queued on both readers and writers in a manner such that preference is given to readers if writers are also there. Thus, no reader is waiting simply because a writer has requested to enter the critical section.

Recall that calling down()on a semaphore with value < 1 causes the calling process to block, thus implying that a process can lock access to a critical section when it acquires a semaphore with value 1 and decrements it to 0. Another process requesting that same semaphore cannot proceed until the original process calls up() to increment the semaphore. Therefore:

(i) The semaphore rcSem controls access to the critical sections of the reader process. Those critical sections only involve access to the shared rdCnt variable, which tracks the number of readers and is necessary to determine when the writer process can access its critical section. However, since each reader process increments rcSem prior to actually reading data, multiple processes can be in the reading section simultaneously.

(ii) The semaphore rwSem controls access to the critical section of the writer process—the editing of data, during which no other process should access the shared data. Locking and unlocking access in the writer process is relatively straightforward. In the reader process, the value of rdCnt determines when the writer is locked out of or allowed access to its critical section. The writer only needs to be locked out when the first reader enters—not for every reader—so rwSem is decremented only if rdCnt is 1. Likewise, the writer will be given access once all readers are done, so rwSem is incremented only if rdCnt is 0.

4b.

Deadlock can occur if two threads access the same accounts, with each account used
as the source in one thread and the destination in the other—for example, if thread 1 calls
transfer_money(1, 2, 1000) and thread 2 calls transfer_money(2, 1, 500).

If each thread obtains its source account lock before the other obtains its destination account
lock, deadlock will occur, since neither thread releases any locks until after it has both. In the
specific example above, that could happen with the following statement interleaving:
T1: locks[1].lock(); // Thread 1 acquires locks[1]
T2: locks[2].lock(); // Thread 2 acquires locks[2]
T1: locks[2].lock(); // Thread 1 blocks
T2: locks[1].lock(); // Thread 2 blocks

A valid solution should resolve one of the two preventable conditions: hold and wait or circular
wait. Resolving hold and wait means the thread should release all locks if it can’t acquire both,
as shown in the pseudo-code below that replaces the two lock() calls in the original function:

while (both locks not acquired) {
locks[src_acct].lock(); // Lock src account
if (locks[dest_acct].lock() fails) // Try to lock dest
locks[src_acct].unlock(); // Release src on
} // failure

To resolve circular waiting, impose an order on the locks so that all threads acquire locks in the
same order. The solution below always acquires the lowest-numbered lock first:

if (src_acct < dest_acct) {
locks[src_acct].lock();
locks[dest_acct].lock();
}
else {
locks[dest_acct].lock();
locks[src_acct].lock();
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.