# 2:1 Mutual exclusion with semaphores

I'm stuck on this semaphore exercise (it's a exam question of a previous exam and I'm studying for that exam):

There are three processes: A, B and C. Process A wants to execute method a(); Process B wants to execute b(); and Process C c();. The Processes are each started once.

The execution of a(); must not overlap with the execution of b(); or c();. However b(); and c(); must always be able to run concurrently. The order of execution must not be forced.

I can use as many semaphores as I want. With every solution I tried so far I always get the case that when e.g. b(); is executing and a(); is waiting, that I will also block c();. The solution is probably simple but I'm too blind to see it.

There's a simple solution which takes advantage of the fact that semaphores naturally allow controlling access to a resource with multiple instances. Model the exclusion as a resource with two instances. A requires both instances while B and C each require one. When A starts, it grabs both instances, preventing B and C from starting. When B or C starts, it grabs one instance, which allows the other to start concurrently, but blocks A.

A:                  B:                  C:
V(S, 2)             V(S, 1)             V(S, 1)
…                   …                   …
P(S, 2)             P(S, 1)             P(S, 1)


This solution works even if the processes run multiple times. A critical ingredient that makes it work is that A atomically excludes both B and C from running.

If you treat B and C's resources as distinguishable, with A requiring both, you run into a classical problem, which is the order of grabbing locks. This problem is similar to the dining philosophers problem. When A starts, it either grabs the B resource first, or the C resource first. Let's say A grabs B, and then tries to grab C. If C is not available, what should happen? If A keeps the B resource then it prevents process B from starting. So A must release B and try again. Since A knows that C is busy, it can wait on C first. In this particular exercise, where the processes only run once, this works. Note that this requires semaphores with a non-blocking “try” operation.

A:                  B:                  C:
lock(B)             lock(B)             lock(C)
if try_lock(C):     …                   …
…                 release(B)          release(C)
release(C)
release(B)
else:
release(B)
lock(C)
lock(B)
…
release(B)
release(C)


If B and C could run multiple times, this strategy wouldn't work: A must never keep one lock while waiting for the other, because that prevents the corresponding process from running again. In this case, I think there's no wait-free solution with only binary semaphores.

• Thank you. I was under the impression that I was only allowed to use binary semaphores, but after checking the class material again I realised I can use something similar to your "try_lock()". We have "multi-sempahore" operations like mP(S1,S2) which will block until it can lock both (when both are unlocked). Nov 1 '17 at 18:22

Use two binary semaphores : x and y.

x will provide mutual exclusion between A and B while y will provide mutual exclusion between A and C.

When A wants to execute a() then it must check that neither of b() and c() is being executed. Thus code for A would be like this:

lock(x)
lock(y)
a()
unlock(y)
unlock(x)


For B code would be like this:

lock(x)
b()
unlock(x)


For C code would be like this

lock(y)
c()
unlock(y)


You may check different execution sequences to verify my answer.

• This will create undesirable blocking under this example: C is in execution locking y, then A arrives (blocking on y, after having locked x), then B arrives, which should be able to run concurrent with C, but is also blocked on x. Nov 1 '17 at 16:32
• @FreddieMercury I was in the middle of answer and by mistake clicked the submit button Nov 1 '17 at 16:34
• Thanks for the answer. Same happened to me while writing the comment. But as far as I understand it the example in my earlier comment still applies. Nov 1 '17 at 16:39
• I get your point. Let me try a different solution. Nov 1 '17 at 16:41
• Agreed. This does not add anything over what the question already states.
– Raphael
Nov 1 '17 at 17:15