operating system

Question

Consider a user level threading library that multiplexes $N > 1$ user level threads over $M \geq 1$ kernel threads. The library manages the concurrent scheduling of the multiple user threads that map to the same kernel thread internally, and the programmer using the library has no visibility or control on this scheduling or on the mapping between user threads and kernel threads. The $N$ user level threads all access and update a shared data structure. When (or, under what conditions) should the user level threads use mutexes to guarantee the consistency of the shared data structure?

(A) Only if $M > 1$
(B) Only if $N \geq M$
(C) Only if the $M$ kernel threads can run in parallel on a multi-core machine.
(D) User level threads should always use mutexes to protect shared data.

Answer 1

I think the answer should be D. Let me try to explain

Consider that below is the code to be executed (a,b,c are shared variables)

1. if(a < 5) 
2. {
3.    b = a;
4.    a = a + 1;
5.    Print (a,b)
6. }

Now coming to options,

A) Only if M > 1

Let us assume M (Number of kernel threads) are "1". Since the user threading library multiplexes N threads over M threads, so in this case, all N threads would be multiplexed (read attached) to a single kernel thread. If above code runs in parallel, and only one of them running at a time (since only one kernel thread), then also, without the use of mutexes, the result would be incorrect.

Let N = 3, and Threads be A, B, C.

Thread A may have just executed line 3, and before it could execute line 4, it was interrupted and Thread B is scheduled. Thread B would execute till line 6 and then Thread A would be scheduled again. Now, since 'a' is already incremented by Thread B, the incorrect value of 'a' is stored in 'b' (remember as per code, 'b' should hold value of 'a' just before it was incremented).

So, clearly here mutexes are needed even if M  = 1

B) Only if N ≥ M

Meaning N (Number of user threads) greater than or equal to M (Number of kernel threads).

Even if the number of user threads are less than kernel threads, then also mutexes would be needed as any parallel execution would lead to incorrect result of our code execution

C) Only if the M kernel threads can run in parallel on a multi-core machine.

Even if they cannot run in parallel, like in Option A, where there is just one kernel thread, we would need mutuxes.

(D) User level threads should always use mutexes to protect shared data.

Indeed. We would need to use mutexes to protect shared data irrespective of values of M or N.