# Binary semaphore problem

This topic is 4976 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok, this is technically related to my university work, so up front I'll say this: I don't want the answer, just general hints regarding the approach that I could find in a text book. Thanks. I have 3 processes that periodically require access to 2 resources, represented by 2 more processes. I need to mediate access between them so that the 3 producer processes do not suffer starvation/deadlock/etc and can be allocated one of the 2 consumer resources (doesn't matter which) as soon as one becomes available. I can't add another process and I can't use any synchronisation primitive except for a binary semaphore. This seems like a producer/consumer problem, but is complicated by having a choice of coupling between each producer and consumer. My initial thought was that I need a semaphore that signifies "at least one of the two consumers is free", but that's not enough because if both are free I need the other to be getting accessed as well. So as soon as I release that semaphore there's a chance someone else will snap up the resource that was just indicated as free. How about using one semaphore as above, which provides mutually exclusive access to 2 boolean globals signifying the availability of the 2 resources, then another semaphore for each of those 2 resources, one of which will get acquired, before the original semaphore is released and the resource is used. Then that resource process will acquire that main semaphore again, set itself to being available, release its own semaphore, and release the main one. Does that sound reasonable? I have a feeling there's a chance of deadlock in there...

##### Share on other sites
I'm not sure if you want hints in how to prove a solution is correct, or if you want strategies for solving problems so I'll provide both.

I believe your approach is reasonable, but not complete. A good way to model synchronization problems is to think of how people behave (e.g. think of how 3 people would share 2 computers). People form queues -- a good way to avoid starvation; people are also able to look first then do (ie they do not have to commit to a course of action) and this is a good way to avoid deadlocks.

Validating that critical sections are not violated should not be too challenging for this case.

For deadlock you probably want to consider two types of cases: can two processes make a grab for a resource and end up with neither receiving it, and can a process requesting a resource prevent another from releasing a resource? Also, in small cases you can probably just consider all possible execution paths.

Also, don't forget to test for starvation. From what I remember you are usually allowed to assume that processes execute at a non-zero speed but with semaphores you are not guaranteed that the first process to wait will be the first to be signalled.

I'm not sure if you want more detail, but from what you said I would rather add more later if you want it. Also, sorry if some of this is just restating stuff you already know.

##### Share on other sites
I would suggest using non-binary semaphores..
that is you create a semaphore with value equal to how many resources you have.
Then you can simply lock it..

You need to make sure that the locked processes are put in a queue on the semaphore, to prevent starvation.

/Nico

##### Share on other sites
I'm reminded of semaphore problem on a university exam involving barbers which i'll adapt to get explain a possible approach.

You have a barber shop, with two barbers and one bench.
If a barber has no customers he's sleeping
If a barber has a customer he's working.
If a barber has no customers and one is waiting on the bench the customer moves to the barber and the barber is working.
If a customer comes in and a barber is sleeping the customer goes and wakes up the barber.
If a customer comes in and both barbers are working then they sit and wait on the bench.

Does looking at your problem and the possibles states for customers and barbers this way help?

##### Share on other sites
Aly - I know how to prove if a solution is correct, but I feel like I'm gonna have to go through a tedious trial and error process of proving mutual exclusion/absence of deadlock/absence of starvation for a large number of permutations for each attempt at the solution. As for queuing, that will be provided intrinsically by the semaphore implementation, thus guaranteeing fairness. The 'look before doing' concept... that was what my overall semaphore was for, to guarantee exclusive access to the current state of the resources before making a decision to ask for one. Maybe the principles from Dekker's algorithm could be applied here, but that was ugly when generalised for 3 processes and 1 resource. No idea if it's even practical for 3 processes and 2 resources.

NicoDeLuciferi - As I said, I have no choice over the use of binary semaphores. In theory I could simulate a counting semaphore with binary ones but I was under the impression that this is a long-winded approach, and still doesn't solve the problem entirely as I still have to decide which of the 2 resources will be given to a requesting process.

TechnoGoth - The 'Sleeping Barber Problem' (not one that was covered on my course, incidentally) is the closest match I could find online before posting this. Unfortunately I can't see exactly how it maps onto my problem - do I have 2 barbers? If so, how do I know which one to 'wake up' without risking waiting forever on Barber 1 while Barber 2 sits idle? That's really the crux of the issue I think. I can't add any extra processes to mediate between the others.

##### Share on other sites
You have to prove it won't deadlock or starve? Sounds like they want you to solve the halting problem.

##### Share on other sites
Quite the opposite, in fact; these processes are potentially going to run forever. I just have to prove that the resources get allocated appropriately and exclusively when requested.

##### Share on other sites
Alright,
but you can fairly simply implement counting semaphores using binary.
By just using 2 semaphores and an integer. But as you said it doesn't

/Nico

##### Share on other sites
You don't say what operations you have on the semaphores and what restrictions there are... For instance can a process release a semaphore when it wasn't the one that acquired it in the first place (I'm assuming yes)? Can you atomically acquire both semaphores at once (I'm assuming no)?

Anyway, my hint is that the solution I came up with used one semaphore to protect the critical piece of information and the other to minimize the amount of time a process spends spinning.

##### Share on other sites
The semaphores are essentially just global booleans, and I get atomic signal and wait instructions to call upon them. Those are the only atomic instructions guaranteed to be available.

My current attempted solution looks like this:
Writing processes:loop    loop        wait(arbitrationSemaphore)        break if reader1Free or reader2Free        signal(arbitrationSemaphore)    end loop    if reader1Free        reader1Free = false        signal(reader1_Start)    else        reader2Free = false        signal(reader2_Start)    signal(arbitrationSemaphore)end loopReading processes (the resources that are being shared):loop    wait(readerN_Start)    DoSomethingCriticalHere    wait(arbitrationSemaphore)    readerNFree = true    signal(arbitrationSemaphore)end loop

arbitrationSemaphore is used as a global lock for the 2 readerNFree variables to ensure they're only altered just after a reader finishes its task, and not between a writer seeing that one of them is true and setting off the appropriate process. The readerN_Start variables are there so that the readers aren't busy-waiting.

Can anyone see any obvious errors with this before I go down the formal verification route?

1. 1
Rutin
25
2. 2
3. 3
4. 4
5. 5

• 10
• 13
• 19
• 14
• 9
• ### Forum Statistics

• Total Topics
632943
• Total Posts
3009347
• ### Who's Online (See full list)

There are no registered users currently online

×