Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've been reading about selective mutual exclusion (SME). The idea I got is that if a process competes for its resources against a subset of all the other process instead of competing with all the other processes then I'm facing a SME problem.

1) Can you confirm my definition is right?

Now, the dining philosophers problem is a classic example of this (SME by proximity)

2) In the distributed solution (in which each philosopher competes for both forks against two other philosophers), if instead of 5 philosophers, there were 3 of them, would it still be a SME problem? (I think not, because each philosopher will be competing with all of the others)

3) And in the centralized "conductor" solution, having 5 philosophers, would it still be a SME problem? (I think it would, because although all processes are competing to get to the waiter, each philosopher is only competing with two of the other to get both specified forks)

Finally, in the readers and writers problem (SME by process type)

4) If only 1 reader and 1 writer were allowed, would it still be a SME problem? (I think not, because actually every process will be competing with all the others)

share|improve this question
1  
Note that you can get deadlock with dining philosophers with only two philosophers and two place settings when using the naive procedure. If both sit down and pick up their left fork simultaneously, neither are able to proceed, so even when all philosophers are competing for all resources, deadlock can occur. –  Mark Booth Feb 15 '12 at 13:12
add comment

1 Answer

up vote 1 down vote accepted

1) Can you confirm my definition is right?

Yes. Three or four references I found by searching the web for concurrency "selective mutual exclusion" seem to comply with your understanding: "if a process competes for its resources against a subset of all the other process instead of competing with all the other processes"

2) In the distributed solution (in which each philosopher competes for both forks against two other philosophers), if instead of 5 philosophers, there were 3 of them, would it still be a SME problem? (I think not, because each philosopher will be competing with all of the others)

Most likely it will be a SME, or some gray area flavor of it. Think of the fork laying between "first" and "second" philosophers - "third" philosopher doesn't use it and because of that we've got "subset competition", limited only to first and second one

3) And in the centralized "conductor" solution, having 5 philosophers, would it still be a SME problem? (I think it would, because although all processes are competing to get to the waiter, each philosopher is only competing with two of the other to get both specified forks)

As long as you define forks as shared resources, it will still be SME - because "first" and "third" philosophers won't have shared resources (forks) to compete for.

Though, if you define waiter as a resource (in programming terms this may be viewed as a singleton with contended access - which would be not too great a design I think) - then there would be no SME since all the philosophers would compete for access to that single shared resource.

4) If only 1 reader and 1 writer were allowed, would it still be a SME problem? (I think not, because actually every process will be competing with all the others)

It would not be SME because in case like above, set of processes consists of precisely two (reader and writer), and both need mutually exclusive access to resource: reader can't read while writer writes and writer can't write while reader reads.

For SME to occur in readers and writers, there should be 1) more than one reader - to make a subset that doesn't compete in between itself and 2) at least one writer - to establish a need in mutual exclusion between read and write accesses


  • Bottom line is, to find out about SME one needs to precisely define set of processes and set of resources. And have a solid understanding of mutex of course.
     
    Another point worth keeping in mind is that the purpose of this high-brow looking concept is quite practical indeed. Knowing when some processes have no need to compete for particular resource gives one an opportunity to reduce lock contention by using finer grained locks.
     
    Readers-writers problem is a good example here. If you find out that there are, say, ten readers heavily fighting for an access to some resource when there is no real need in that, addressing this may make your application about ten times faster, go figure.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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