Binary semaphore problem
Can you reverse the problem?
Instead of giving the producer processes the job of waiting for the consumers to be free, can you give the consumers the job of linking with the next available producer as soon as the consumer is ready for more data?
Disclaimer: I haven't had formal training in this stuff; I'm probably missing something very obvious.
John B
Instead of giving the producer processes the job of waiting for the consumers to be free, can you give the consumers the job of linking with the next available producer as soon as the consumer is ready for more data?
Something like:Writer:* wait(producer semaphore N)* Do your funky stuffReader:* wait(arbitration semaphore)* get the next producer semaphore from the list* rotate the list* signal(arbitration semaphore)* signal(producer semaphore N)* Do your funky stuffDisclaimer: I haven't had formal training in this stuff; I'm probably missing something very obvious.
John B
AnonMike: I can cope with a little busy-waiting ;) As long as the other conditions are met, it's the lesser of 2 evils. Once it's working I can probably add in another semaphore there which wakes up the writer threads when the readers/resources signal it. Which seems to lead to what JohnBSmall said...
JohnBSmall: I sort of see where you're coming from, but I have no high-level list structure to work with, only the implied queuing that comes from waiting on a semaphore, which makes it a bit more difficult to picture mentally.
JohnBSmall: I sort of see where you're coming from, but I have no high-level list structure to work with, only the implied queuing that comes from waiting on a semaphore, which makes it a bit more difficult to picture mentally.
Do you know anything about the implementation of your semaphores? What I am wondering is can you be sure that if writer A does signal(arbitrationSemaphore) will that guarantee that if writer B performed a wait(arbitrationSemaphore) earlier will writer B be woken up? If not there might be a chance that writer A can sneak back into line and possibly reacquire the semaphore before writer B.
Also, for doing the analysis you can simplify it a bit by only considering two processes. This will catch most of the problems and you don't have to worry about riduculous numbers of permutations. Of course this wouldn't hold for a formal proof.
Also, for doing the analysis you can simplify it a bit by only considering two processes. This will catch most of the problems and you don't have to worry about riduculous numbers of permutations. Of course this wouldn't hold for a formal proof.
I am led to believe that the semaphores have a FIFO implementation for determining which process to resume, and that resuming such processes happens immediately if one is waiting. I think it's a reasonable assumption to work with anyway. This is more a theoretical exercise than a practical one.
Quote:Original post by Kylotan
JohnBSmall: I sort of see where you're coming from, but I have no high-level list structure to work with, only the implied queuing that comes from waiting on a semaphore, which makes it a bit more difficult to picture mentally.
My main reasoning was that since you have more producers than consumers, there will always be a producer sitting idle; that gives you an easy way to solve your problem of choosing couplings between producers and consumers - whenever a consumer finishes its job, it can be coupled with the producer that was idle.
That should also share the consumers evenly between producers, since the producers will each be activated in turn.
As regards using a list structure, obviously you can get the same effect in a number of ways using lower level primitives.
Which part are you having difficulty picturing?
John B
Quote:Original post by JohnBSmall
My main reasoning was that since you have more producers than consumers, there will always be a producer sitting idle; that gives you an easy way to solve your problem of choosing couplings between producers and consumers - whenever a consumer finishes its job, it can be coupled with the producer that was idle.
The problem there is that there's no guarantee that the idle producer is going to actually produce any time soon. If you assume that all producers produce at about the same rate and very often, this isn't a problem, but if you generalise it to any frequency and taking any finite length of time, it's no good. The consumer can't make any assumptions on which producer will produce next.
Quote:As regards using a list structure, obviously you can get the same effect in a number of ways using lower level primitives.
Obviously it's possible to implement any sort of data structure out of the basics, but I get the impression that such a thing would be missing the point of the exercise, since the semaphores already provide their own queueing implementation. So it's to be done implicitly (by the order in which processes use 'wait' on a semaphore) rather than by placing anything into an explicit queue or list.
Quote:Original post by Kylotan
The problem there is that there's no guarantee that the idle producer is going to actually produce any time soon. If you assume that all producers produce at about the same rate and very often, this isn't a problem, but if you generalise it to any frequency and taking any finite length of time, it's no good. The consumer can't make any assumptions on which producer will produce next.
Ah, ok - I wasn't sure whether to assume that or not.
John B
Well, I seem to have come up with an algorithm that works in practice; the only problem is, I've just realised that we were never taught how to prove the correctness of a system that uses semaphores. :) Doh.
Quote:
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.
well I'm sure there are lots of fancy ways you could do it but why not like this:
Customer Enters:if(barberOneSleeping){ barberOneSleeping=false; barberOneWorking=true; performHairCut(BarberOne); }else if(barberTwoSleeping){ barberTwoSleeping=false; barberTwoWorking=true; performHairCut(BarberTwo); }else { customerWaiting=true; waitOnBench(Customer);}I'd help you with proving your algorithim works, but I long ago forgot how to do that. :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement