Semaphore
tom...@hotmail.com
semaphore, however, couldn't it be done in a TASK system as well?
Is there a good example on using a semaphore that may clear up my
thinking?
Thanks
Sent via Deja.com http://www.deja.com/
Before you buy.
Andrea Bovo
<tom...@hotmail.com> wrote in message 8rthbb$p9g$1...@nnrp1.deja.com...
> Why are semaphores needed? I have a basic concept of how to use a
> semaphore, however, couldn't it be done in a TASK system as well?
> Is there a good example on using a semaphore that may clear up my
> thinking?
ACM Computing Surveys Vol. 15, No. 1, March 1983
Gregory R. Andrews, Fred B. Schneider
"Concepts and Notations for Concurrent Programming"
Andrea
42Bastian Schick
> Why are semaphores needed? I have a basic concept of how to use a
> semaphore, however, couldn't it be done in a TASK system as well?
Semaphore are (in general) needed when two or more tasks want to access
the same resource (memory, I/O).
But the use of semaphore can/should be avoided as it may lead into a
dead-lock.
The better way is to have a single task that manages the resource.
BTW: In a well designed OSE system (using no legacy code) there is
practically no need for semaphores !
> Is there a good example on using a semaphore that may clear up my
> thinking?
Take a printer-port and two tasks. Both want print.
Taken, both processes are scheduled via time-slices thus, both of them
can print, the result will be messed up.
Now, with a semaphore (a global variable), the current process (A)
checks the semaphore (with disabled interrupts !!!) and if not set, it
sets it.
If the timeslice expires and process B checks the semaphore it is
already set and B suspends itself.
After A finished printing it clears the semaphore and allows B to set it
and start printing.
On a message-base OS (like QNX,OSE) you rather write a process that
handles the printer-port. Any process that wants to print, sends the
printer-process a message which will be queued and the printer process
prints it one by one.
--
42Bastian
-------------------------------
-- ENEA OSE Engineering GmbH --
-- b.sc...@enea.de --
-------------------------------
Marc Warden
> Why are semaphores needed? I have a basic concept of how to use a
> semaphore, however, couldn't it be done in a TASK system as well?
>
> Is there a good example on using a semaphore that may clear up my
> thinking?
>
> Thanks
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
An example of a semaphore? How about a common traffic light. It prevents
(well, would in a perfect world in which they were obeyed) two (or more)
drivers from accessing the same resource (the intersection) at the same
time.
Sincerely,
MarcW
Troy Cauble
: But the use of semaphore can/should be avoided as it may lead into a
: dead-lock.
: The better way is to have a single task that manages the resource.
: BTW: In a well designed OSE system (using no legacy code) there is
: practically no need for semaphores !
Is that task communicating with other tasks?
Isn't a semaphore involved, inside the message queue implementation?
-troy
42Bastian Schick
> : practically no need for semaphores !
>
> Is that task communicating with other tasks?
get a dead-lock.
But sending messages is very easy to trace and debug. Much easier than
checking which process manipulates which semaphore.
> Isn't a semaphore involved, inside the message queue implementation?
No, since the message queue (which is different from *nix queues !) is
handled by the OSE. Of course, there is no dispatch allowed during the
handling of the queue.
Ok, it uses one semaphore, but a hardware-semaphore: Disabling
interrupts (but mostly only those which might result in a task-switch).
But even with a semaphore you have to disable interrupts at a certain
time to be sure no task-switch happens , unless you can use some nice
read-modify-write assembler-commands ("TAS" in 68k,5407).
Gerald Hilderink
"42Bastian Schick" <b.sc...@enea.de> wrote in message
news:39E2CDD8...@enea.de...
>
> > Why are semaphores needed? I have a basic concept of how to use a
> > semaphore, however, couldn't it be done in a TASK system as well?
>
> the same resource (memory, I/O).
>
> dead-lock.
>
> The better way is to have a single task that manages the resource.
>
> practically no need for semaphores !
>
> > thinking?
>
> Taken, both processes are scheduled via time-slices thus, both of them
> can print, the result will be messed up.
> Now, with a semaphore (a global variable), the current process (A)
> checks the semaphore (with disabled interrupts !!!) and if not set, it
> sets it.
> If the timeslice expires and process B checks the semaphore it is
> already set and B suspends itself.
> After A finished printing it clears the semaphore and allows B to set it
> and start printing.
>
> On a message-base OS (like QNX,OSE) you rather write a process that
> handles the printer-port. Any process that wants to print, sends the
> printer-process a message which will be queued and the printer process
> prints it one by one.
>
> 42Bastian
> -------------------------------
> -- ENEA OSE Engineering GmbH --
> -- b.sc...@enea.de --
> -------------------------------
Using semaphores and monitors easily lead to complexity whereby the
behaviour of the software is hard to understand and to trace. As mentioned
above, communication between processes is much simpler to design and to
understand. This does not mean that we don't need semaphores. Semaphores are
needed to establish safe communication between the processes and are best
understood by the processor, not by the designer. Communication is a much
higher-level abstraction that is easier to understand by us. Deadlock is a
design failure that is easier to find and to solve with communication
channels between processes than using semaphores, monitors and/or signals.
Another great thing about these channels is that it has a formal
mathematical foundation, namely CSP, CCS, LOTOS and others. These theories
provide design rules or guidelines for writing reliable concurrent software.
Semaphores and monitors have no formal foundation, they simply work. From
CSP there are several programming languages derived, e.g., Occam, Ada, and
Limbo. Many Universities in Europe and in the United States educate Occam.
Students learn how to build reliable concurrent application without
bothering with the underlying semaphores and monitors. With the concept of
channels you do not need to use semaphores, because they are hidden in the
design patterns of CSP. On our web site http://www.rt.el.utwente.nl/javapp
you can find a CSP for Java library. A CSP for C++ is under construction and
will be released at the end of this year.
Gerald.
Herman
consequently are exhaustively well defined and based on integer
mathematics, not a hard concept at all. Essentially, a semaphore is a
counting 'flag'. A flag is normally thought of as a binary / boolean
condition, while a semaphore can have values greater than 1 and are used
to control complex allocation problems. Consequently, a semaphore is
similar to a Finite State Machine.
Cheers,
Herman
http://www.AerospaceSoftware.com
Pat Rogers
constructs: powerful but unstructured and at a very low level of
abstraction. They have been used extensively because they are very
simple to understand -- but that is not the same as being simple to
use *robustly*. IMHO they are obsolete; the fact that they are still
used is indicative of the immaturity of the field.
<tom...@hotmail.com> wrote in message
news:8rthbb$p9g$1...@nnrp1.deja.com...
> Why are semaphores needed? I have a basic concept of how to use a
> semaphore, however, couldn't it be done in a TASK system as well?
>
> Is there a good example on using a semaphore that may clear up my
> thinking?
>
Mikkel Elmholdt
>
>
> > Why are semaphores needed? I have a basic concept of how to use a
> > semaphore, however, couldn't it be done in a TASK system as well?
>
> the same resource (memory, I/O).
>
> But the use of semaphore can/should be avoided as it may lead into a
> dead-lock.
>
> The better way is to have a single task that manages the resource.
>
> BTW: In a well designed OSE system (using no legacy code) there is
> practically no need for semaphores !
I think this is rather rigid. Using a single semaphore to control access
to a common resource will not result in any deadlock. It is only when
you need access to two or more resources, each protected by a semaphore,
that said problem can occur.
The task approach is architecturally sound, but will inflict a
performance penalty, as you will force a task switch even though the
resource is free. Whether this is a real issue depends on the system.
But I agree that the task approach should be used whereever possible.
--
Mikkel Elmholdt
Data Respons A/S, Denmark
mikkel....@datarespons.dk
http://www.datarespons.com
Pat Rogers
news:39E48481...@vip.cybercity.dk...
<snip>
> The task approach is architecturally sound, but will inflict a
> performance penalty, as you will force a task switch even though the
> resource is free. Whether this is a real issue depends on the
system.
> But I agree that the task approach should be used whereever
possible.
The task approach, by which I think you mean synchronous rendezvous
(Concurrent C and both versions of Ada), is fine if that is
appropriate, but it does as you say involve task switching.
IMHO the "ideal" approach uses both direct thread communication (when
synchronous interaction is appropriate) and indirect
communication/synchronization using non-thread mechanisms. That way
the excessive task switching is avoided. But I don't suggest
semaphores, mutexes or condition variables.
To be concrete, I prefer either monitors (as in Java or Concurrent
Pascal), or better yet, "protected objects" (as in Ada 95). Monitors
increase robustness by automating the locking protocol and by
encapsulating resources behind a high-level procedural interface.
They do have their problems however (such as the nested monitor call
problem as well as the lack of condition synchronization support).
Protected objects in particular are nice because they are extremely
expressive (combining both mutual exclusion and condition
synchronization in a monitor-like construct) and don't involve task
switches. Furthermore, on a bare machine with the full priority model
they will be faster than semaphores because no lock is actually
required.
---
Patrick Rogers Consulting and Training in:
http://www.classwide.com Deadline Schedulability Analysis
pro...@classwide.com Software Fault Tolerance
(281)648-3165 Real-Time/OO Languages
Adam ... does not deserve all the credit; much is due to Eve, the
first woman, and Satan, the first consultant.
Mark Twain
tom...@hotmail.com
that a Semaphore would make it less complex.
Is it common to use only tasks in RTOS's?
Thanks for the previous responses.
Pat Rogers
news:8s2a8p$lh0$1...@nnrp1.deja.com...
> Well, it looks like I was making the system too complex by thinking
> that a Semaphore would make it less complex.
>
> Is it common to use only tasks in RTOS's?
No, you'll also need efficient mechanisms for providing mutual
exclusion and condition synchronization in addition to a means of
expressing threads of control.
Are you sure you need an RTOS? Probably so if the language itself is
not sufficient, but worth asking up front.
Mikkel Elmholdt
>
> "Mikkel Elmholdt" <mikkel....@vip.cybercity.dk> wrote in message
> news:39E48481...@vip.cybercity.dk...
> <snip>
> > The task approach is architecturally sound, but will inflict a
> > performance penalty, as you will force a task switch even though the
> > resource is free. Whether this is a real issue depends on the
> system.
> > But I agree that the task approach should be used whereever
> possible.
>
> The task approach, by which I think you mean synchronous rendezvous
> (Concurrent C and both versions of Ada), is fine if that is
> appropriate, but it does as you say involve task switching.
I (and the prior poster) mean a concept, where a task is set up to guard
a resource. Any access to that resource must go through that task,
typically through a message queue. In this way all access to ther
resource is serialized.
Whether this is the equivalent of Ada synchronous rendezvous I'm not
sure, but it sounds like it.
> IMHO the "ideal" approach uses both direct thread communication (when
> synchronous interaction is appropriate) and indirect
> communication/synchronization using non-thread mechanisms. That way
> the excessive task switching is avoided. But I don't suggest
> semaphores, mutexes or condition variables.
>
> To be concrete, I prefer either monitors (as in Java or Concurrent
> Pascal), or better yet, "protected objects" (as in Ada 95). Monitors
> increase robustness by automating the locking protocol and by
> encapsulating resources behind a high-level procedural interface.
> They do have their problems however (such as the nested monitor call
> problem as well as the lack of condition synchronization support).
> Protected objects in particular are nice because they are extremely
> expressive (combining both mutual exclusion and condition
> synchronization in a monitor-like construct) and don't involve task
> switches. Furthermore, on a bare machine with the full priority model
> they will be faster than semaphores because no lock is actually
> required.
>
Being an ANSI C/C++ programmer I don't quite follow your Ada & C-Pascal
approaches, but I (think that I) have seen a similar pattern i C++. In
effect they are merely nice wrappings of the more basic approaches, but
done right, they can be more efficient, more readable & maintainable and
prevent deadlocks.
But something being faster than a semaphore? No lock required? Que?
Aquiring a free semaphore is typically done in one or two assembly
instructions.
Pat Rogers
> Pat Rogers wrote:
> >
> > "Mikkel Elmholdt" <mikkel....@vip.cybercity.dk> wrote in
message
> > news:39E48481...@vip.cybercity.dk...
> > <snip>
> > > The task approach is architecturally sound, but will inflict a
> > > performance penalty, as you will force a task switch even though
the
> > > resource is free. Whether this is a real issue depends on the
> > system.
> > > But I agree that the task approach should be used whereever
> > possible.
> >
> > The task approach, by which I think you mean synchronous
rendezvous
> > (Concurrent C and both versions of Ada), is fine if that is
> > appropriate, but it does as you say involve task switching.
>
> I (and the prior poster) mean a concept, where a task is set up to
guard
> a resource. Any access to that resource must go through that task,
> typically through a message queue. In this way all access to ther
> resource is serialized.
>
> Whether this is the equivalent of Ada synchronous rendezvous I'm not
> sure, but it sounds like it.
Yes, that's close; the difference is that the message queue is handled
by the underlying runtime system as part of the language semantics (in
both Concurrent C and Ada). As a result the actual syntax is very
high level, with consequent robustness.
That's probably the right idea, although I would worry about
efficiency losses introduced by the wrappers. Having things directly
in the language can offer improvements.
> But something being faster than a semaphore? No lock required? Que?
> Aquiring a free semaphore is typically done in one or two assembly
> instructions.
The Ada 95 Real-Time Systems annex defines a runtime system that fully
supports offline schedulability analysis via preemptive static
priority scheduling and the Immediate Ceiling Priority Protocol.
Everything has a priority, including the synchronization mechanisms.
As a result, on a bare machine under this approach no lock is required
because the priorities preclude race conditions on the mechanisms.
These mechanisms encapsulate the data, hence no race conditions on the
data.
The Ada 95 tasking system with the RTS annex is designed for maximum
efficiency on a bare machine. I know a person that targeted Ada to RT
Linux, and got approximately 98% utilization of the machine using
tasks and protected objects.
News Zonnet
"Herman" <aero...@AerospaceSoftware.com> wrote in message
news:39E46912...@AerospaceSoftware.com...
> Semaphores were 'invented' by the Dutch mathematician Prof Dijkstra and
> consequently are exhaustively well defined and based on integer
> mathematics, not a hard concept at all. Essentially, a semaphore is a
> counting 'flag'. A flag is normally thought of as a binary / boolean
> condition, while a semaphore can have values greater than 1 and are used
> to control complex allocation problems. Consequently, a semaphore is
> similar to a Finite State Machine.
>
> Cheers,
>
> Herman
> http://www.AerospaceSoftware.com
>
Still, the semaphore has no formal mathematical foundation!
Although a semaphore can be described in mathematical terms it is not a
fundamental algebraic concept. Fundamental algebraic concepts are events
(communication events, termination events, etc.), process, parallel
operator, sequential operator, choice operator, timeout operator, exception
operator, and others, as defined in untimed CSP and in timed CSP. With these
fundamental primitives we can describe, compute and analyse semaphores or
monitors. Also, Petri-nets is a formal technique to analyse semaphores and
monitors. Finite state machines are formal as well but they only express
states and transitions. FSMs should be used for describing your flow of
control and not synchronization. Describing synchronization adds an extra
dimension (e.g. thread states and queuing states) to your other state charts
which lets it easily explode. To solve synchronization in FSMs I use events
in state transitions that synchronize with other events on other state
transitions of parallel FSMs.
Gerald.
42Bastian Schick
> Is it common to use only tasks in RTOS's?
Hmm, what is it you realy want to know ?
Depending of the (RT)OS you are using, you need or you don't need
(acutally should not use) semaphore.
If you use a multitasking (RT)OS, you sure will split your problem into
simple single tasks.
Same with a multi-threaded language, you'll be good advised to use
threads when ever it makes sense.
But then again, there is no global answer wheter to use an (RT)OS and
how to design an application.