1
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Freddie Mercury
    Nov 1, 2017 at 18:22
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Freddie Mercury
    Nov 1, 2017 at 16:32
  • $\begingroup$ @FreddieMercury I was in the middle of answer and by mistake clicked the submit button $\endgroup$
    – Kishan Kumar
    Nov 1, 2017 at 16:34
  • $\begingroup$ 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. $\endgroup$
    – Freddie Mercury
    Nov 1, 2017 at 16:39
  • $\begingroup$ I get your point. Let me try a different solution. $\endgroup$
    – Kishan Kumar
    Nov 1, 2017 at 16:41
  • $\begingroup$ Agreed. This does not add anything over what the question already states. $\endgroup$
    – Raphael
    Nov 1, 2017 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.