Hi,
I'm conducting some research in real-time systems, and require a
*citeable* source that corroborates or refutes the following:
In practice, semaphores are most often used to prevent concurrent
access to some shared data structure (i.e., using a mutex) compared to
their other uses. Furthermore, when mutexes are employed, they are
most often used to prevent concurrent access to a queue (or bounded
buffer).
I'd love a reference to a paper that actually sampled the uses of
semaphores in practice and then categorized each use. If the above
statement is wrong, I'd like to know what the most typical uses of
semaphores actually are, or what the most typical uses of mutexes are.
(I.e., if mutexes are most often used to synchronize access to some
other data structure, what is that data structure?)
Thanks in advance!
William |
Request for Question Clarification by
maniac-ga
on
22 Mar 2004 17:59 PST
Hello Wluebke,
Hmm. It appears you have the two statements backwards but that will
depend on the definitions you are using. Thus, a mutex is used most
often to protect shared (or global) memory and a semaphore is used to
manage a queue or bounded buffer.
This is assuming:
- the "semaphores" you refer to are counting (allow values other than
zero and one) and may allow multiple tasks to manipulate them
- the mutexes (or mutual exclusion) you refer to can only be unlocked
by the task that locks it
If this is correct - please let me know so I can prepare a proper
answer. If not, please clarify your definitions of the terms semaphore
and mutex.
--Maniac
|
Clarification of Question by
wluebke-ga
on
22 Mar 2004 19:58 PST
It is my belief that mutexes are a special case of semaphores and are
implemented in terms of them in today's popular operating systems.
One can use semaphores to synchronize tasks in all kinds of ways,
including producer/consumer problems. However, I'm asserting that
mutexes constitute the majority of the exercise a semaphore
implementation gets. That's the first question. The second question
is: assuming the answer to the first question is true, what are
programmers preventing concurrent access to the most?
|
Request for Question Clarification by
maniac-ga
on
23 Mar 2004 18:41 PST
Hello Wluebke,
A mutex can be implemented as a special case of a semaphore, but often
it is not for performance reasons.
For example:
http://mictlan.sfsu.edu/~dachen/header_files/asm/spinlock_h.htm
has the source code for spinlocks in Linux (for x86 processors).
Scroll down to the defines starting at spin_lock_string and at
read_lock for the examples below. The code is basically
lock
btsl (bit), (lock address)
followed by a test for a non-zero value to do the lock and
lock
btrl (bit), (lock address)
for the unlock. Both of these set / clear a single bit in the long
word. They perform a hard loop instead of sleeping - so they are
simpler than a mutex, but are otherwise similar.
Apparently, the operations (btsl / btrl) are faster than the use of
incl and decl used in read/write locks (multiple readers, single
writers). So in this case, a mutex is implemented differently than a
semaphore.
Having said that - it would be possible to grep the Linux source code
and get a count of the occurences for these different types of
operations and do some basic analysis to determine the type of data
being protected in each case. Would that kind of answer be acceptable?
--Maniac
|
Clarification of Question by
wluebke-ga
on
24 Mar 2004 11:16 PST
You have a good idea, although surveying the Linux kernel isn't ideal
since it isn't a real-time system's task set, and therefore isn't as
applicable for my needs. A perfect survey would sample several
multiprocessor real-time task sets involving synchronization between
some of the tasks. I suspect these are difficult or impossible to
find, as they are often proprietary. I'm very sure that no such
survey has been done in the past, and that was why I was willing to
settle with a survey of synchronization in software in general.
Sorry to make this so difficult...
|
Request for Question Clarification by
maniac-ga
on
24 Mar 2004 16:49 PST
Hello Wluebke,
Hmm. Real time synchronization needs. There are a few alternatives
that come to mind:
- look at a real time executive (e.g., freertos)
- look at a real time application
The first is pretty straight forward - similar to what I suggested
with Linux. It also has the advantage you could check my work. It may
not handle the multiprocessor case however. The second requires access
to code - I have that (for a large real time simulator) but you would
have to take my word for the results. By the way - this large
simulator runs quite well on Linux - scheduling tasks at 80, 40, 30,
20, 10, 5, and 1 Hz (as well as some asynchronous tasks) and has both
shared memory and message passing for synchronization / data exchange
between tasks.
Please advise how to proceed.
--Maniac
|
