Tasking Techniques - Opinions?

Tasking Techniques - Opinions?

[Steve Doiel]

Over the years I have used a number of real time operating systems
(or kernal's).  Those systems made use of "semaphores," "events,"
"mutexes," "tasks," "queues," and other synchronization or tasking
primatives.  The terminology differs in terms of what exactly an
"event" is, but the concepts are similar.

I have read what John Barnes has to say about tasks and protected
types in "Programming in Ada 95."  It appears that the tools for
creating and synchronizing tasks in Ada are simple, but it leaves
me wondering about the best techniques to use to perform the job
at hand.

For example:
I am working on a communications subsystem.  In this subsystem
various tasks produce packages of data that are to be transmitted
using BSD sockets on TCP/IP.

In the current implementation, one module maintains a free pool
of packet buffers.  Access to the free pool is done using a
protected type.  A second module contains a protected type that
contains a FIFO of packet buffers (the send queue).  A third
module contains a "send task" that is in a short loop that
removes entries from the send queue, transmits the data out the
socket and then returns the packet buffer to the free pool.

In the above description the gory details of how the socket
initially gets set up, what happens when a socket goes away,
and other error handling are left out to keep the discussion
simple.

Now the question:
Is this a reasonable implementation?  Or is there a better
approach?

I am making almost no use of Ada's "rendevous," and am leaning
more toward using protected types to pass data through queues.

Is this poor practice?  I understand that with Ada 83 this
was not an option, but still wonder if this is the best
approach.

Opinions?

Steve Doiel
steved@pacifier.com

Re: Tasking Techniques - Opinions?

[Tom Moran]

> A third
> module contains a "send task" that is in a short loop that
> removes entries from the send queue, transmits the data out the
> socket and then returns the packet buffer to the free pool.
What does this task do if there's nothing to send?  Does it sit and eat
CPU or is there some way it can go to sleep and be awakened when there's
work to do, or is it always busy and my question is irrelevant?

Re: Tasking Techniques - Opinions?

[Steve Doiel]

In article <3394EC73.3011@bix.com>, tmoran@bix.com says...
>
>> A third
>> module contains a "send task" that is in a short loop that
>> removes entries from the send queue, transmits the data out the
>> socket and then returns the packet buffer to the free pool.
>What does this task do if there's nothing to send?  Does it sit and eat
>CPU or is there some way it can go to sleep and be awakened when there's
>work to do, or is it always busy and my question is irrelevant?

The send queue remove operation is contained within an entry to a
protected type that has a guard condition causing the task to pend
if the queue is empty.
 

Re: Tasking Techniques - Opinions?

[Jon S Anthony]

In article <5n2hjr$ohm$1@news.pacifier.com> steved@pacifier.com (Steve Doiel) writes:

> In the current implementation, one module maintains a free pool
> of packet buffers.  Access to the free pool is done using a
> protected type.  A second module contains a protected type that
> contains a FIFO of packet buffers (the send queue).  A third
> module contains a "send task" that is in a short loop that
> removes entries from the send queue, transmits the data out the
> socket and then returns the packet buffer to the free pool.
...
> Now the question:
> Is this a reasonable implementation?  Or is there a better
> approach?

Sounds pretty reasonable to me.  There are a couple of bits that you
haven't mentioned.  What populates the send queue?  How does the send
task know there is anything in the queue?

This could be done by using another task which populates the send
queue and then signals the send task that there is something to do (it
is waiting on a "start working" entry).  The send task removes and
sends stuff until the queue is empty and then goes back to waiting.
This might not happen, as the populator task should be able to
continue adding stuff (it would only signal the send task if the queue
were empty).  Which brings up another point: some sort of flow control
in case the populator is faster than the sender.

Anyway, sounds basically on the right track.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Tasking Techniques - Opinions?

[bsanden]

On 4 Jun 1997 01:49:47 GMT, steved@pacifier.com (Steve Doiel) wrote:

>For example:
>I am working on a communications subsystem.  In this subsystem
>various tasks produce packages of data that are to be transmitted
>using BSD sockets on TCP/IP.
>
>In the current implementation, one module maintains a free pool
>of packet buffers.  Access to the free pool is done using a
>protected type.  A second module contains a protected type that
>contains a FIFO of packet buffers (the send queue).  A third
>module contains a "send task" that is in a short loop that
>removes entries from the send queue, transmits the data out the
>socket and then returns the packet buffer to the free pool.
>
>In the above description the gory details of how the socket
>initially gets set up, what happens when a socket goes away,
>and other error handling are left out to keep the discussion
>simple.
>
>Now the question:
>Is this a reasonable implementation?  Or is there a better
>approach?
>
>I am making almost no use of Ada's "rendevous," and am leaning
>more toward using protected types to pass data through queues.
>
>Is this poor practice?  I understand that with Ada 83 this
>was not an option, but still wonder if this is the best approach.
>
>Opinions?
>
Sounds perfectly reasonable to me. Ada 83 forced many more tasks into
the designs than were actually justified by real concurrency. The
protected objects have made this much more palatable. Letting tasks
communicate via shared objects is also the traditional way of doing
these things. 




Prof. Bo Sanden
Colorado Technical University 
4435 N. Chestnut Street
Colorado Springs, CO 80907-3896
Email: bsanden@acm.org
Http://www.isse.gmu.edu/faculty/bsanden

Re: Tasking Techniques - Opinions?

[Samuel A. Mize]

bsanden@acm.org wrote:
> On 4 Jun 1997 01:49:47 GMT, steved@pacifier.com (Steve Doiel) wrote:
...
> >In the current implementation, one module maintains a free pool
> >of packet buffers.  Access to the free pool is done using a
> >protected type.  A second module contains a protected type that
> >contains a FIFO of packet buffers (the send queue).  A third
> >module contains a "send task" that is in a short loop that
> >removes entries from the send queue, transmits the data out the
> >socket and then returns the packet buffer to the free pool.
...
> Sounds perfectly reasonable to me. Ada 83 forced many more tasks into
> the designs than were actually justified by real concurrency. The
> protected objects have made this much more palatable. Letting tasks
> communicate via shared objects is also the traditional way of doing
> these things.

Absolutely true.  However, do be aware that protected types have
significant overhead -- not as much as task rendezvous, but on the
order of ten times a procedure call.

If speed is of the essence, AND protected objects are slowing your
system too much, you may need to look at "atomic" variables (see
pragma Atomic).  For instance, a circular buffer using a reader and
a writer index, where each task needs only read access to the other's
index.  The issues to address in this case:

1 Protected objects give you easy concurrency protection.  Home-rolled
  concurrency protection is hard to get totally right.

2 If one task has to wait for the other -- for instance,if the circular
  buffer is full so the writer has to wait -- you have to determine how
  to make it wait (or do something else for a while), and how to make
  sure that the other task gets a chance to run and consume something
  from the buffer.  You get that for free with protected entries.

3 Depending on your compiler/implementation, atomic variables may
  take almost as much time as protected.  Do some timing tests.

Point 1 is the big motivator.  Getting concurrency totally right is
really really hard.

So, in general, use protected objects.

If speed is critical AND protected objects are slowing it down
too much, AND atomic variables are faster on your system, consider
a more-traditional shared-data approach using atomic objects.

Sam Mize

--
-- Samuel Mize           (817) 619-8622               "Team Ada"
-- Hughes Training Inc.  PO Box 6171 m/s 400, Arlington TX 76005

Re: Tasking Techniques - Opinions?

[Jon S Anthony]

In article <3395A448.41C6@magellan.bgm.link.com> "Samuel A. Mize" <smize@magellan.bgm.link.com> writes:

> Absolutely true.  However, do be aware that protected types have
> significant overhead -- not as much as task rendezvous, but on the
> order of ten times a procedure call.

I find this surprising. On what do you base this 10X figure?

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Tasking Techniques - Opinions?

[Samuel A. Mize]

Jon S Anthony wrote:
> In article <3395A448.41C6@magellan.bgm.link.com> "Samuel A. Mize" <smize@magellan.bgm.link.com> writes:
> 
> > Absolutely true.  However, do be aware that protected types have
> > significant overhead -- not as much as task rendezvous, but on the
> > order of ten times a procedure call.
> 
> I find this surprising. On what do you base this 10X figure?

It surprised me too, and forced me to redesign data-sharing
in some real-time code.  (Measure everything, early.  Thank
heaven we DID.)

As Tom Quiggle of SGI pointed out to me in email, Ada semantics
surround a protected call with a lot of required processing:
a) deferral of abortion/asynchronous transfer of control (ATC)
   for the current task
b) acquisition of of a mutex
c) execution of the protected actions
d) release the mutex
e) re-enable abortion/ATC
f) check for pending abort/ATC

Some of this will be system calls, which take longer than
simple procedure calls on most systems I know of.  In a
multi-processor environment, those system calls will have to
coordinate between processors, which takes even more time.

Sam Mize

--
-- Samuel Mize           (817) 619-8622               "Team Ada"
-- Hughes Training Inc.  PO Box 6171 m/s 400, Arlington TX 76005

Re: Tasking Techniques - Opinions?

[Robert Dewar]

Jon says

<<> Absolutely true.  However, do be aware that protected types have
> significant overhead -- not as much as task rendezvous, but on the
> order of ten times a procedure call.
 
I find this surprising. On what do you base this 10X figure?
>>

surprisingly low? or suprisingly high? The difference will vary widely. If
taking the necessary lock requires a kernel call, as it does when running
over some OS's, then the factor of 10 will be wildly optimistic. Protected
types were designed to be efficient on bare hardware, their implementation
over operating stystems is often disappointingly inefficient.

Re: Tasking Techniques - Opinions?

[Jon S Anthony]

In article <dewar.865692193@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Jon says
> 
> <<> Absolutely true.  However, do be aware that protected types have
> > significant overhead -- not as much as task rendezvous, but on the
> > order of ten times a procedure call.
>  
> I find this surprising. On what do you base this 10X figure?
> >>
> 
> surprisingly low? or suprisingly high? The difference will vary widely. If

Actually, I was thinking "high".

> taking the necessary lock requires a kernel call, as it does when running
> over some OS's, then the factor of 10 will be wildly optimistic. Protected
> types were designed to be efficient on bare hardware, their implementation
> over operating stystems is often disappointingly inefficient.

OK, that makes good sense.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Tasking Techniques - Opinions?

[Robert A Duff]

In article <5n2hjr$ohm$1@news.pacifier.com>,
Steve Doiel <steved@pacifier.com> wrote:
>Now the question:
>Is this a reasonable implementation?  Or is there a better
>approach?
>
>I am making almost no use of Ada's "rendevous," and am leaning
>more toward using protected types to pass data through queues.

If you don't need the "extra" functionality of rendezvous (which is
quite often true), then it's perfectly reasonable to use protected
types, and never use rendezvous.  That is, declare all of your tasks
without any entries.

- Bob