comp.lang.ada
 help / color / mirror / Atom feed
* Complexity of protected objects
@ 2002-02-25 16:28 tony gair
  2002-02-25 16:45 ` Marin David Condic
                   ` (2 more replies)
  0 siblings, 3 replies; 21+ messages in thread
From: tony gair @ 2002-02-25 16:28 UTC (permalink / raw)



I'm considering using a protected object to store an AVL tree and also to
write and read files,
normally I would have used tasks for this, but I wish to experiment
slightly.

J Barnes recommends that  protected objects be as small as possible, so
being a little
bloody minded I want to see what the limits are for protected objects ,
I would be very interested to see unusual protected objects people have
created, which
do things protected objects were not designed for (is this an oxymoron?).






^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-25 16:28 Complexity of protected objects tony gair
@ 2002-02-25 16:45 ` Marin David Condic
  2002-03-03  1:11   ` Robert Dewar
  2002-02-25 17:35 ` Jim Rogers
  2002-02-25 22:01 ` Ted Dennison
  2 siblings, 1 reply; 21+ messages in thread
From: Marin David Condic @ 2002-02-25 16:45 UTC (permalink / raw)


"tony gair" <tonygair@nespamtome.btinternet.com> wrote in message
news:a5dont$dh9$1@helle.btinternet.com...
>
> J Barnes recommends that  protected objects be as small as possible, so
> being a little
> bloody minded I want to see what the limits are for protected objects ,

The usual reason for this is that since a protected object is going to
create what amounts to a "critical section" you don't want to spend any more
time in one than you have to. One thread running through a long protected
object's code is going to block out other threads from accessing it - hence
the "keep it short" advice.

I don't know of any natural limitations that would make it A Bad Thing to
have a very large protected object. AFAIK, its only a concern for how long
it will block execution of other tasks that limit size. The rest would be
whatever limitations your compiler may impose.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/





^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-25 16:28 Complexity of protected objects tony gair
  2002-02-25 16:45 ` Marin David Condic
@ 2002-02-25 17:35 ` Jim Rogers
  2002-02-28 22:09   ` Nick Roberts
  2002-03-03  0:32   ` Robert Dewar
  2002-02-25 22:01 ` Ted Dennison
  2 siblings, 2 replies; 21+ messages in thread
From: Jim Rogers @ 2002-02-25 17:35 UTC (permalink / raw)


Using a protected object to read and write files is a clear
violation of the intention and recommendations for proctected
objects. Protected objects should be non-blocking. I/O is
always potentially blocking.

You even have some potential blocking issues when storing an
AVL tree. If you dynamically allocate your AVL tree nodes you
have the possibility of running out of memory. This will either
result in a blocking situation, or a potential loss of data
in the AVL tree.

I would be inclined to use a simple protected buffer object to
communicate with one or more tasks for the reading and writing,
and another task to store the AVL tree. Protected operations allow
you to design a degree of asynchronisity into your system. They are
not expected to replace tasks for all uses.

Jim Rogers

tony gair wrote:

> I'm considering using a protected object to store an AVL tree and also to
> write and read files,
> normally I would have used tasks for this, but I wish to experiment
> slightly.
> 
> J Barnes recommends that  protected objects be as small as possible, so
> being a little
> bloody minded I want to see what the limits are for protected objects ,
> I would be very interested to see unusual protected objects people have
> created, which
> do things protected objects were not designed for (is this an oxymoron?).
> 
> 
> 
> 




^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-25 16:28 Complexity of protected objects tony gair
  2002-02-25 16:45 ` Marin David Condic
  2002-02-25 17:35 ` Jim Rogers
@ 2002-02-25 22:01 ` Ted Dennison
  2002-03-03  1:08   ` Robert Dewar
  2 siblings, 1 reply; 21+ messages in thread
From: Ted Dennison @ 2002-02-25 22:01 UTC (permalink / raw)


"tony gair" <tonygair@nespamtome.btinternet.com> wrote in message news:<a5dont$dh9$1@helle.btinternet.com>...
> J Barnes recommends that  protected objects be as small as possible, so
> being a little
> bloody minded I want to see what the limits are for protected objects ,

I've generally found that to be good advice. In particular, my PO's
always seem to end up just being specialized semaphores or locks, no
matter how grandiose I start out planning to make them. Things just
work a lot better that way.

-- 
T.E.D.
Home     -  mailto:dennison@telepath.com (Yahoo: Ted_Dennison)
Homepage -  http://www.telepath.com/dennison/Ted/TED.html



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-25 17:35 ` Jim Rogers
@ 2002-02-28 22:09   ` Nick Roberts
  2002-02-28 23:32     ` Dale Stanbrough
                       ` (2 more replies)
  2002-03-03  0:32   ` Robert Dewar
  1 sibling, 3 replies; 21+ messages in thread
From: Nick Roberts @ 2002-02-28 22:09 UTC (permalink / raw)


On Mon, 25 Feb 2002 17:35:45 GMT, Jim Rogers
<jimmaureenrogers@worldnet.att.net> strongly typed:

>Using a protected object to read and write files is a clear
>violation of the intention and recommendations for proctected
>objects. Protected objects should be non-blocking. I/O is
>always potentially blocking.

It's perhaps a little sweeping to say "I/O is always potentially blocking".
There may be certain rare cases where this is not so. But it will certainly
always be so for reading or writing files, in practice.

>You even have some potential blocking issues when storing an
>AVL tree. If you dynamically allocate your AVL tree nodes you
>have the possibility of running out of memory. This will either
>result in a blocking situation, or a potential loss of data
>in the AVL tree.

I would suggest this is being ultra-cautious. In practice, dynamic memory
allocation tends to be considered an 'honourary' non-blocking operation
(even though this does actually fly in the face of the reality). It is
certainly better to avoid any dynamic allocation in a protected subprogram
if you easily can.

Remember, you need to consider the practical consequences of a protected
subprogram being blocked; the RM95 can only say what behaviour is or isn't
guaranteed by all conforming Ada 95 implementations.

In the case of running out of memory (for dynamic allocation), you may
consider this to be a rare event, and a show-stopper anyway, and so not
worth worrying about (in terms of how badly it may obstruct other tasks). I
hasten to add that in some applications this attitude would be reckless.

Consider, for example, virtual memory. Depending on the peculiarities of
the Ada implementation and the target execution environment, it may be that
the execution of a protected subprogram could cause a virtual memory 'page
fault' at any point in its execution. Such page faults will typically cause
I/O activity to occur (to swap a page in, swap a page out, allocate a page
on secondary storage, or whatever). But I/O is 'potentially blocking'.
Disaster! Well no, not really; as long as the 'block' does not last too
long. Similar comments apply to pre-emptive scheduling environments and so
on.

>I would be inclined to use a simple protected buffer object to
>communicate with one or more tasks for the reading and writing,
>and another task to store the AVL tree. Protected operations allow
>you to design a degree of asynchronisity into your system. They are
>not expected to replace tasks for all uses.

Agreed.

Tony Gair wrote:
>>(is this an oxymoron?).

Well, I admire the shapeless solidity of the question.

;-)

-- 
Nick Roberts



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-28 22:09   ` Nick Roberts
@ 2002-02-28 23:32     ` Dale Stanbrough
  2002-03-01  5:45       ` Jim Rogers
  2002-03-03  0:59       ` Robert Dewar
  2002-03-01 17:42     ` Jeffrey Carter
  2002-03-03  0:54     ` Robert Dewar
  2 siblings, 2 replies; 21+ messages in thread
From: Dale Stanbrough @ 2002-02-28 23:32 UTC (permalink / raw)


Jim Rogers wrote:

> Using a protected object to read and write files is a clear
>violation of the intention and recommendations for proctected
>objects. Protected objects should be non-blocking. I/O is
>always potentially blocking.

Why is this? I see this as being a piece of programming advice,
- it's not a good idea to hold locks for a long time - but is 
there any more to it than that? Are there some other consequences
of scheduling than that?

Dale
------------ And now a word from our sponsor ------------------
Do your users want the best web-email gateway? Don't let your
customers drift off to free webmail services install your own
web gateway!
--  See http://netwinsite.com/sponsor/sponsor_webmail.htm  ----



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-28 23:32     ` Dale Stanbrough
@ 2002-03-01  5:45       ` Jim Rogers
  2002-03-03  0:59       ` Robert Dewar
  1 sibling, 0 replies; 21+ messages in thread
From: Jim Rogers @ 2002-03-01  5:45 UTC (permalink / raw)


Dale Stanbrough wrote:

> Jim Rogers wrote:
> 
> 
>>Using a protected object to read and write files is a clear
>>violation of the intention and recommendations for proctected
>>objects. Protected objects should be non-blocking. I/O is
>>always potentially blocking.
>>
> 
> Why is this? I see this as being a piece of programming advice,
> - it's not a good idea to hold locks for a long time - but is 
> there any more to it than that? Are there some other consequences
> of scheduling than that?


It is good to understand why "it's not a good idea to hold locks
for a long time". The first reason that comes to my mind is the
need to avoid live locks and dead locks in your system.

Note that this is an entirely different issue from queueing up
protected entry calls because the entry guard is closed. Protected
entries are used to communicate state as well as data between tasks.

Blocking actions belong in separate tasks. Unless you are using
FSU threads this should allow other tasks to procede while one
task is blocked. Blocking during communication between tasks
often has a cascading effect throughout a system.

Jim Rogers




^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-28 22:09   ` Nick Roberts
  2002-02-28 23:32     ` Dale Stanbrough
@ 2002-03-01 17:42     ` Jeffrey Carter
  2002-03-03  1:06       ` Robert Dewar
  2002-03-03  0:54     ` Robert Dewar
  2 siblings, 1 reply; 21+ messages in thread
From: Jeffrey Carter @ 2002-03-01 17:42 UTC (permalink / raw)


Nick Roberts wrote:
> 
> On Mon, 25 Feb 2002 17:35:45 GMT, Jim Rogers
> <jimmaureenrogers@worldnet.att.net> strongly typed:
> 
> >Using a protected object to read and write files is a clear
> >violation of the intention and recommendations for proctected
> >objects. Protected objects should be non-blocking. I/O is
> >always potentially blocking.
> 
> It's perhaps a little sweeping to say "I/O is always potentially blocking".
> There may be certain rare cases where this is not so. But it will certainly
> always be so for reading or writing files, in practice.

ARM 9.5.1 says

Certain language-defined subprograms are potentially blocking. In
particular, the subprograms of the language-defined input-output
packages that manipulate files (implicitly or explicitly) are
potentially blocking.

Thus, I/O as always potentially blocking because the language defines it
as such.

-- 
Jeffrey Carter



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-25 17:35 ` Jim Rogers
  2002-02-28 22:09   ` Nick Roberts
@ 2002-03-03  0:32   ` Robert Dewar
  1 sibling, 0 replies; 21+ messages in thread
From: Robert Dewar @ 2002-03-03  0:32 UTC (permalink / raw)


Jim Rogers <jimmaureenrogers@worldnet.att.net> wrote in message news:<3C7A75F2.30503@worldnet.att.net>...
> Using a protected object to read and write files is a 
> clear violation of the intention and recommendations for 
> proctected objects. Protected objects should be 
> non-blocking. I/O is always potentially blocking.

Please prove this *from the RM*. Potentially blocking is
a technical term defined in the RM, it does NOT necessarily
correspond to the informal notion of some action in the
operating system which blocks execution and causes task
switching, so whether I/O is forbidden is something you
will have to check with the vendor of the compiler you
are using, and will depend on what kind of I/O you are
doing and how.

> You even have some potential blocking issues when storing 
> an AVL tree. If you dynamically allocate your AVL tree 
> nodes you have the possibility of running out of memory. 
> This will either result in a blocking situation, or a 
> potential loss of data in the AVL tree.

Again, I don't see your point, there is nothing at all to
stop a protected subprogram from doing dynamic allocation.
 
> 
> tony gair wrote:
> > do things protected objects were not designed for (is 
> > this an oxymoron?).


An oxymoron is the juxtaposition of contrasting terms for
literary effect, e.g. "deafening silence". I see nothing
literary here,

yes, yes, I know, the term has been so badly misused, that
some dictionaries by now recognize the degradation of this
beautiful word to simply mean contradiction in terms :-)



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-28 22:09   ` Nick Roberts
  2002-02-28 23:32     ` Dale Stanbrough
  2002-03-01 17:42     ` Jeffrey Carter
@ 2002-03-03  0:54     ` Robert Dewar
  2 siblings, 0 replies; 21+ messages in thread
From: Robert Dewar @ 2002-03-03  0:54 UTC (permalink / raw)


nickroberts@ukf.net (Nick Roberts) wrote in message news:<3c7e7c60.8192226@news.cis.dfn.de>...
> On Mon, 25 Feb 2002 17:35:45 GMT, Jim Rogers

> It's perhaps a little sweeping to say "I/O is always 
> potentially blocking". There may be certain rare cases 
> where this is not so. But it will certainly
> always be so for reading or writing files, in practice.

Again this is wrong, and is based on the very common misunderstanding
that the technical term "potentially
blocking" corresponds to the OS/notion of the current
task being blocked. It does not!

The point is that *for a very particular kind of implementation
approach*, you will want to make this
correspondence, so in this environment (typically a
low level implementation on a monoprocessor), you will
want to make the correspondence, and the provision in the
RM allows you to do so.

But in more typical environments, e.g. working on top of
an operating system, or real time executive, there is absolutely no
requirement to restrict what can be done
in protected subprograms, and in practice may implementations do not
do so.


> Consider, for example, virtual memory. Depending on the 
> peculiarities of the Ada implementation and the target 
> execution environment, it may be that the execution of a 
> protected subprogram could cause a virtual memory 'page 
> fault' at any point in its execution. Such page faults 
> will typically cause I/O activity to occur (to swap a 
> page in, swap a page out, allocate a page on secondary 
> storage, or whatever). But I/O is 'potentially blocking'.

Now the full scale of the confusion hits. Of *COURSE* it
is the case that a memory read is NOT potentially blocking
in the RM sense, even if in practice in some operating
systems it might cause a context switch.


> Agreed.
> 
> Tony Gair wrote:
> >>(is this an oxymoron?).
> 
> Well, I admire the shapeless solidity of the question.
> 

Now there is a *true* oxymoron, very nice, quite poetic :-)



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-28 23:32     ` Dale Stanbrough
  2002-03-01  5:45       ` Jim Rogers
@ 2002-03-03  0:59       ` Robert Dewar
  1 sibling, 0 replies; 21+ messages in thread
From: Robert Dewar @ 2002-03-03  0:59 UTC (permalink / raw)


Dale Stanbrough <dale@cs.rmit.edu.au> wrote in message news:<dale-1C20CF.10324101032002@its-aw-news.its.rmit.edu.au>...
> Jim Rogers wrote:
> Why is this? I see this as being a piece of programming 
> advice, - it's not a good idea to hold locks for a long 
> time - but is 
> there any more to it than that? Are there some other 
> consequences
> of scheduling than that?

It's amazing! The entire thread here is wandering off into
irrelevance based on this pervasive notion that potentially
blocking exactly matches the OS notion.

I wish the RM had used the term "grubnoxious" instead of
"potentially blocking" to avoid this confusion.

Here's the deal. If you are using the approach to implementing PT's
that completely avoids locks and
depends on ceiling priority, then you really must avoid
thread switches that could allow someone else to get into
the eggshell.

But if you are in fact using locks, there is no reason at
all to be worried about context switches. Yes, of course
the programmer will have to avoid deadlock in this case,
just as they would have to with tasks, but that's a different level of
concern entirely.

In fact GNAT works perfectly fine, as expected, if you
do blocking operations within PT's



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-01 17:42     ` Jeffrey Carter
@ 2002-03-03  1:06       ` Robert Dewar
  2002-03-03  6:53         ` Jeffrey Carter
  0 siblings, 1 reply; 21+ messages in thread
From: Robert Dewar @ 2002-03-03  1:06 UTC (permalink / raw)


Jeffrey Carter <jeffrey.carter@boeing.com> wrote in message news:<3C7FBD74.D434411E@boeing.com>...


> Certain language-defined subprograms are potentially blocking. In
> particular, the subprograms of the language-defined input-output
> packages that manipulate files (implicitly or explicitly) are
> potentially blocking.
> 
> Thus, I/O as always potentially blocking because the 
> language defines it as such.

Umm, I am afraid our syllogistic apparatus is malfunctioning here. The
predicate said (I will
shout to make sure no one else misses it) LANGUAGE-DEFINED
input-output packages.

It is entirely wrong to assume this says something about
all I/O. The point is that if the implementation introduces
non-language defined I/O, then it will have to decide whether it is PB
or not (in GNAT such I/O is not defined
to be PB).

Even if you do language defined I/O that *is* PB, let's read the RM to
see what happens if you do a PB action in
a PT:

8   During a protected action, it is a bounded error to invoke an
operation that is potentially blocking.  The following are defined to
be potentially blocking operations:

17   If the bounded error is detected, Program_Error is raised.  If
not detected, the bounded error might result in deadlock or a (nested)
protected action on the same target object.

Now of course this means that any program doing PB operations in a PT
has an implementation dependent
effect, so most certainly you need to check that it
will work on the implementation you are using, and
the code is non-portable (since it might not work
on lock-free implementations for instance).



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-25 22:01 ` Ted Dennison
@ 2002-03-03  1:08   ` Robert Dewar
  2002-03-04  9:33     ` Dmitry A. Kazakov
  0 siblings, 1 reply; 21+ messages in thread
From: Robert Dewar @ 2002-03-03  1:08 UTC (permalink / raw)


dennison@telepath.com (Ted Dennison) wrote in message news:<4519e058.0202251401.27b95bb0@posting.google.com>...
> I've generally found that to be good advice. In particular, my PO's
> always seem to end up just being specialized semaphores or locks, no
> matter how grandiose I start out planning to make them. Things just
> work a lot better that way.



This is MUCH too restrictive, it is perfectly reasonable
to have a large complex data structure as a protected type
where the operations on it ensure that consistency is
maintained by doing related updates in a non-interruptible
manner.



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-02-25 16:45 ` Marin David Condic
@ 2002-03-03  1:11   ` Robert Dewar
  2002-03-03  4:13     ` Dale Stanbrough
  0 siblings, 1 reply; 21+ messages in thread
From: Robert Dewar @ 2002-03-03  1:11 UTC (permalink / raw)


"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:<a5dpnv$p6n$1@nh.pace.co.uk>...
> I don't know of any natural limitations that would make 
> it A Bad Thing to have a very large protected object. 
> AFAIK, its only a concern for how long
> it will block execution of other tasks that limit size.

There are none
 
> The rest would be
> whatever limitations your compiler may impose.

A compiler that imposes arbitrary limits on the complexity
of protected types is broken (of course in specialized
subsets, like Ravenscar, such restrictions may serve a
specific purpose).

Remember that the key point about protected objects is the
ceiling priority protocol, which ensures that higher priority tasks
can still freely interrupt the lower priority tasks inside a PO with a
lower CP. Thus it is
quite reasonable to use complex PO's with a low CP for
communication between low priority tasks without any
danger of intefering with high priority tasks (even in
an implementation that has no locks).



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-03  1:11   ` Robert Dewar
@ 2002-03-03  4:13     ` Dale Stanbrough
  2002-03-03 19:50       ` Robert Dewar
  0 siblings, 1 reply; 21+ messages in thread
From: Dale Stanbrough @ 2002-03-03  4:13 UTC (permalink / raw)


Robert Dewar wrote:

> Remember that the key point about protected objects is the
> ceiling priority protocol, which ensures that higher priority tasks
> can still freely interrupt the lower priority tasks inside a PO with a
> lower CP.

Just to clarify - the sentence above seems to imply that a low
priority task inside a PO can be forceably removed from the PO
by a higher priority task that want the -same- PO.

Of course this is impossible (if you want correct programs!). 
The reason you have POs is so that you can atomically modify
the state of an object. If you kick a task out 1/2 through, the
invariants for he PO (or the object it is protecting) could
easily be left in a corrupt state. Ceiling priority protocal
allows the high priority task to ensure it will be the -next-
task to get access to the PO, and to ensure that low priority 
tasks "hurry up and get out of the way" when working inside
a PO.

On the other hand if the higher priority task is resources
other than the PO used by the low priority tasks, then I agree.


> Thus it is
> quite reasonable to use complex PO's with a low CP for
> communication between low priority tasks without any
> danger of intefering with high priority tasks (even in
> an implementation that has no locks).

Another name for POs/semaphores are "bottlenecks". If you
want to increase the natural parallelism of a program, you
should make the code inside them as short as possible.


Dale



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-03  1:06       ` Robert Dewar
@ 2002-03-03  6:53         ` Jeffrey Carter
  2002-03-03 19:36           ` Robert Dewar
  0 siblings, 1 reply; 21+ messages in thread
From: Jeffrey Carter @ 2002-03-03  6:53 UTC (permalink / raw)


Robert Dewar wrote:
> 
> Jeffrey Carter <jeffrey.carter@boeing.com> wrote in message news:<3C7FBD74.D434411E@boeing.com>...
> 
> > Certain language-defined subprograms are potentially blocking. In
> > particular, the subprograms of the language-defined input-output
> > packages that manipulate files (implicitly or explicitly) are
> > potentially blocking.
> >
> > Thus, I/O as always potentially blocking because the
> > language defines it as such.
> 
> Umm, I am afraid our syllogistic apparatus is malfunctioning here. The
> predicate said (I will
> shout to make sure no one else misses it) LANGUAGE-DEFINED
> input-output packages.

Actually it said subprograms of language-defined input-output packages
that manipulate files. On the other hand, I think that covers all the
language-defined I/O packages, and most of their subprograms.

Yes, I was slightly imprecise, and should have written "Language-defined
I/O is always potentially blocking", but as the start of the discussion
referred to calling Ada.Text_IO operations from protected operations, I
didn't think the additional qualification was necessary.

-- 
Jeff Carter
"I wave my private parts at your aunties."
Monty Python & the Holy Grail



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-03  6:53         ` Jeffrey Carter
@ 2002-03-03 19:36           ` Robert Dewar
  2002-03-04 20:04             ` Jeffrey Carter
  0 siblings, 1 reply; 21+ messages in thread
From: Robert Dewar @ 2002-03-03 19:36 UTC (permalink / raw)


Jeffrey Carter <jrcarter@acm.org> wrote in message news:<3C81C852.395A160A@acm.org>...
> but as the start of the discussion
> referred to calling Ada.Text_IO operations from protected 
> operations, I
> didn't think the additional qualification was necessary.

But it did not do so! The first message in this thread
simply talked about reading and writing files, without
any hint of how it should be done.

The bottom line here is that if you want to do input output
from a protected object, you need to check with the details
of the implementation to see what will happen. It might be
just fine to use Text_IO (it would be in GNAT), or it might
be fine to use an interfaced C library routine, or perhaps
there is something specifically intended for this purpose.
Most certainly you are in implementation dependent territory here, but
that's not necessarily terrible at all.



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-03  4:13     ` Dale Stanbrough
@ 2002-03-03 19:50       ` Robert Dewar
  0 siblings, 0 replies; 21+ messages in thread
From: Robert Dewar @ 2002-03-03 19:50 UTC (permalink / raw)


Dale Stanbrough <dstanbro@bigpond.net.au> wrote in message news:<dstanbro-DD061F.15085703032002@mec2.bigpond.net.au>...
> Robert Dewar wrote:
> 
> > Remember that the key point about protected objects is 
> > the ceiling priority protocol, which ensures that 
> > higher priority tasks can still freely interrupt the 
> > lower priority tasks inside a PO with a lower CP.
> 
> Just to clarify - the sentence above seems to imply that 
> a low priority task inside a PO can be forceably removed 
> from the PO by a higher priority task that want the 
> -same- PO.

Of course not. It seems that you are not understanding
ceiling priority protocol at all here. The lower priority
task entering the PO immediately raises the priority to
the ceiling priority of that PO. The only interruption
allowed is by a higher priority task, i.e. whose priority
is, as in my message, higher priority than the ceiling
priority of the PO. But such a task is not allowed to
enter that PO (since you cannot call a PO if your priority
is higher than the ceiling priority).

This is absolutely fundamental to the operation of protected objects.
It also depends on run-till-blocked
semantics as required by Annex D, since you also cannot
time slice to an equal priority task if you are relying
on a lock-less implementation of PO's.

In fact most implementations do use locks and all these
considerations, including the worrying about PB operations
are irrelevant. 

> Ceiling priority protocal
> allows the high priority task to ensure it will be the 
> task to get access to the PO, and to ensure that low 
> priority  tasks "hurry up and get out of the way" when 
> working inside a PO.

Ah, I think I know your confusion, the above para makes
zero sense, but if you replace "Ceiling priority protocol"
by "Priority inheritance" it does make sense. I think you
are mixing up these two concepts.

> On the other hand if the higher priority task is 
> resources other than the PO used by the low priority 
> tasks, then I agree.

Well in that case you agree, because the ONLY time that
a task inside a PO can be preempted is by a task which
by definition cannot use the PO!

> Another name for POs/semaphores are "bottlenecks". If you
> want to increase the natural parallelism of a program, 
> you should make the code inside them as short as 
> possible.

Nope! That's much too crude a rule. The issue is contention
and minimizing context switching time.

The two things necessary for meeting strict performance
criteria in a hard real time application are

a) ensuring that high priority tasks that need immediate
control get immediate control (more properly, analyzing
carefully the maximum latency)

b) minimizing unnecessary context switching to decrease
overall system overhead

Keeping code in PO's short is neither necessary nor sufficient to
ensure that these goals are met.

Suppose you have three tasks in the system, two tasks
at low priority, and one at high priority.

The low priority tasks have no specific deadlines, but they
have a lot of computing to do, and it is important to minimize system
overhead. The high priority task must always be able to immediately
preempt.

Assume only one processor.

Assume we have a PO shared between the low priority tasks,
i.e. its ceiling priority is greater than or equal to that
of the low priority tasks, but lower than the high priority task.

In this situation the PO *can not* be a bottleneck, and there is
absolutely no loss from putting as much processing as you like in the
PO, providing you avoid blocking.

The bottom line in the design of real time systems is that
you have to control the entire behavior of the system, and
do a proper analysis. Trying to replace this with simplistic rules is
not a good idea. I always like the
results of RMA, because they are such a good antidote to
the myth of "obvious common sense" (it is so obvious that
more urgent tasks be given higher priority, right? :-)



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-03  1:08   ` Robert Dewar
@ 2002-03-04  9:33     ` Dmitry A. Kazakov
  2002-03-04 16:44       ` Ted Dennison
  0 siblings, 1 reply; 21+ messages in thread
From: Dmitry A. Kazakov @ 2002-03-04  9:33 UTC (permalink / raw)


On 2 Mar 2002 17:08:06 -0800, dewar@gnat.com (Robert Dewar) wrote:

>dennison@telepath.com (Ted Dennison) wrote in message news:<4519e058.0202251401.27b95bb0@posting.google.com>...
>> I've generally found that to be good advice. In particular, my PO's
>> always seem to end up just being specialized semaphores or locks, no
>> matter how grandiose I start out planning to make them. Things just
>> work a lot better that way.
>
>This is MUCH too restrictive, it is perfectly reasonable
>to have a large complex data structure as a protected type
>where the operations on it ensure that consistency is
>maintained by doing related updates in a non-interruptible
>manner.

Theoretically, yes. Practically, I have observed the same effect as
Ted Dennison pointed out. There are too many reasons why it does not
work, sigh. One of them is that protected types are not tagged. As a
result, very often one fails to use PO as the base for that large
complex data structore. Instead of that one has a PO with an access
discriminant pointing to some class wide. Slowly but steadily all the
functionality flows into that tagged type and in the end the PO
degrades to a simple lock.

Regards,
Dmitry Kazakov



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-04  9:33     ` Dmitry A. Kazakov
@ 2002-03-04 16:44       ` Ted Dennison
  0 siblings, 0 replies; 21+ messages in thread
From: Ted Dennison @ 2002-03-04 16:44 UTC (permalink / raw)


dmitry@elros.cbb-automation.de (Dmitry A. Kazakov) wrote in message news:<3c833afb.435853953@News.CIS.DFN.DE>...
> On 2 Mar 2002 17:08:06 -0800, dewar@gnat.com (Robert Dewar) wrote:
> 
> >dennison@telepath.com (Ted Dennison) wrote in message news:<4519e058.0202251401.27b95bb0@posting.google.com>...
> >> I've generally found that to be good advice. In particular, my PO's
> >> always seem to end up just being specialized semaphores or locks, no
> >> matter how grandiose I start out planning to make them. Things just
> >> work a lot better that way.
> >
> >This is MUCH too restrictive, it is perfectly reasonable
> >to have a large complex data structure as a protected type
> >where the operations on it ensure that consistency is
> >maintained by doing related updates in a non-interruptible
> >manner.
> 
> Theoretically, yes. Practically, I have observed the same effect as
> Ted Dennison pointed out. There are too many reasons why it does not
> work, sigh. One of them is that protected types are not tagged. As a
> result, very often one fails to use PO as the base for that large
> complex data structore. Instead of that one has a PO with an access
> discriminant pointing to some class wide. Slowly but steadily all the
> functionality flows into that tagged type and in the end the PO
> degrades to a simple lock.

I usually end up with a slighly specialized lock or semaphore, but
otherwise this is exactly right. Another prime mover in that direction
is the effect that Dale pointed out elsewhere in this thread:

"Another name for POs/semaphores are "bottlenecks". If you
want to increase the natural parallelism of a program, you
should make the code inside them as short as possible."

Robert seems to read me as saying that this was a law enforced from
above, but I never said that. Its a law in the same way Gravity is a
law. :-)

-- 
T.E.D.
Home     -  mailto:dennison@telepath.com (Yahoo: Ted_Dennison)
Homepage -  http://www.telepath.com/dennison/Ted/TED.html



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Complexity of protected objects
  2002-03-03 19:36           ` Robert Dewar
@ 2002-03-04 20:04             ` Jeffrey Carter
  0 siblings, 0 replies; 21+ messages in thread
From: Jeffrey Carter @ 2002-03-04 20:04 UTC (permalink / raw)


Robert Dewar wrote:
> 
> Jeffrey Carter <jrcarter@acm.org> wrote in message news:<3C81C852.395A160A@acm.org>...
> > but as the start of the discussion
> > referred to calling Ada.Text_IO operations from protected
> > operations, I
> > didn't think the additional qualification was necessary.
> 
> But it did not do so! The first message in this thread
> simply talked about reading and writing files, without
> any hint of how it should be done.

Now I've had to go to Google Groups to see how my memory is doing, and
of course Dewar is correct. But without any qualification on how to read
and write files, I think we should treat such posts to cla as referring
to language-defined I/O.

-- 
Jeffrey Carter



^ permalink raw reply	[flat|nested] 21+ messages in thread

end of thread, other threads:[~2002-03-04 20:04 UTC | newest]

Thread overview: 21+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2002-02-25 16:28 Complexity of protected objects tony gair
2002-02-25 16:45 ` Marin David Condic
2002-03-03  1:11   ` Robert Dewar
2002-03-03  4:13     ` Dale Stanbrough
2002-03-03 19:50       ` Robert Dewar
2002-02-25 17:35 ` Jim Rogers
2002-02-28 22:09   ` Nick Roberts
2002-02-28 23:32     ` Dale Stanbrough
2002-03-01  5:45       ` Jim Rogers
2002-03-03  0:59       ` Robert Dewar
2002-03-01 17:42     ` Jeffrey Carter
2002-03-03  1:06       ` Robert Dewar
2002-03-03  6:53         ` Jeffrey Carter
2002-03-03 19:36           ` Robert Dewar
2002-03-04 20:04             ` Jeffrey Carter
2002-03-03  0:54     ` Robert Dewar
2002-03-03  0:32   ` Robert Dewar
2002-02-25 22:01 ` Ted Dennison
2002-03-03  1:08   ` Robert Dewar
2002-03-04  9:33     ` Dmitry A. Kazakov
2002-03-04 16:44       ` Ted Dennison

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox