Prev: Possible Solution
Next: Kernel image size
From: Boudewijn Dijkstra on 20 Nov 2009 08:15
Op Fri, 20 Nov 2009 05:19:32 +0100 schreef Ari Okkonen
<ari.okkonen(a)obp.fi>:
> Boudewijn Dijkstra wrote:
>> Op Wed, 18 Nov 2009 17:09:39 +0100 schreef Ari Okkonen
>> <ari.okkonen(a)obp.fi>:
>>> [snip]
>>>
>>> The shared stores with locking operations improve the communication
>>> between tasks.
>> Compared to what? How did you come to this conclusion? Which
>> inter-task communication methods did you investigate?
>>
> An example is a measurement data block in a mechanical or chemical
> process control system. Several measurement tasks update hundreds of
> values in the data block each in own pace. Several control tasks read
> these values in different paces. There will be lots of messages sent
> back and forth if these tasks cannot share the same data store.
> Using messages to transfer and query values seems more complicated
> than just assigning or reading the values, including locking.

Looks can be deceiving. I hope your design process does not base its
conclusions on mere assumptions and hearsay.

>>> Priority ceiling protocol keeps the locking operations simple, avoids
>>> priority inversion, and avoids deadlocks.
>> If you can lock, you can have deadlock. What if a process dies before
>> it has the chance to unlock?
>>
> In the priority ceiling protocol there are no specific locks for the
> resources.
> The priority of the task is raised so much that no other task having
> access to that resource [can] get scheduled. If the task dies, its
> priority has no meaning anymore.
> See e.g.
> http://en.wikipedia.org/wiki/Priority_ceiling_protocol

Your assumption seems to be that process synchronization is achieved by
the scheduler alone, without the addition of explicit locking and
unlocking. What if a process holding a resource has to sleep for a
millisecond or so, giving another process the chance to access that
resource? Havoc would ensue!

So, explicit registration of resource ownership still has to take place.
Refer to my question above.

>> Is it possible that, at any given time, one can determine which source
>> code line or which model element has caused a store to be locked?
>>
> No specific mechanism is planned for that. Anyway it can be done using
> a debugger in a breakpoint.

I don't see how that would help. How do you envision one should debug
performance problems?



--
Gemaakt met Opera's revolutionaire e-mailprogramma:
http://www.opera.com/mail/
(remove the obvious prefix to reply by mail)
From: Ari Okkonen on 24 Nov 2009 17:40
Boudewijn Dijkstra wrote:
> Op Fri, 20 Nov 2009 05:19:32 +0100 schreef Ari Okkonen
> <ari.okkonen(a)obp.fi>:
>> Boudewijn Dijkstra wrote:
>>> Op Wed, 18 Nov 2009 17:09:39 +0100 schreef Ari Okkonen
>>> <ari.okkonen(a)obp.fi>:
>>>> [snip]
>>>>
>>>> The shared stores with locking operations improve the communication
>>>> between tasks.
>>> Compared to what? How did you come to this conclusion? Which
>>> inter-task communication methods did you investigate?
>>>
>> An example is a measurement data block in a mechanical or chemical
>> process control system. Several measurement tasks update hundreds of
>> values in the data block each in own pace. Several control tasks read
>> these values in different paces. There will be lots of messages sent
>> back and forth if these tasks cannot share the same data store.
>> Using messages to transfer and query values seems more complicated
>> than just assigning or reading the values, including locking.
>
> Looks can be deceiving. I hope your design process does not base its
> conclusions on mere assumptions and hearsay.
>
Our design process utilizes experience and experimental coding of
solution choices. About experience:
I have implemented and used both mechanisms. (My history with real-time
started with some maintenance work to Honeywell H1642 time-sharing OS
in 1973. Then I read Per Brinch-Hansen's Operating System Principles
and wrote my first RTOS microkernel for Honeywell H316 in 1974 as a
hobby project. I never gave up real-time/embedded since then.)

Application engineering considerations:

If using shared stores with locking, it is quite easy: 1) lock those
stores you need, 2) read and/or update them, 3) release them

To do the same with messages you have to: 1) define messages for data
queries and updates, 2) write a task or tasks to contain the data and
to answer the messages, 3) prepare for interleaved new events and
server responses (this is explained later),
4) for data writes encode and send messages,
5) for data reads encode and send query messages, define a wait
state for waiting an answer and decode the answer. All operations
including several shared values must be programmed into the
data-containing task in order to keep system-wide consistency.

It is possible that a new event arrives for processing while your
task is waiting a response from a data server task. You have to
implement a mechanism to cope with that. (E.g. SDL has a save-operation
for that issue.)

So, it seems (measured by words, at least) that applying message based
solution is more complex.

Run-time considerations:

First experimental codings suggest that those locking and unlocking
operations are together about 12 simple statements in C plus a scheduler
call in unlock. (Haven't measured clock cycles yet.)

The message solution requires at least 900 clock cycles in ARM 7
including two scheduler calls - switching tasks back and forth.

So, it seems that running message based solution takes more time.

>>>> Priority ceiling protocol keeps the locking operations simple, avoids
>>>> priority inversion, and avoids deadlocks.
>>> If you can lock, you can have deadlock. What if a process dies
>>> before it has the chance to unlock?
>>>
>> In the priority ceiling protocol there are no specific locks for the
>> resources.
>> The priority of the task is raised so much that no other task having
>> access to that resource [can] get scheduled. If the task dies, its
>> priority has no meaning anymore.
>> See e.g.
>> http://en.wikipedia.org/wiki/Priority_ceiling_protocol
>
> Your assumption seems to be that process synchronization is achieved by
> the scheduler alone, without the addition of explicit locking and
> unlocking. What if a process holding a resource has to sleep for a
> millisecond or so, giving another process the chance to access that
> resource? Havoc would ensue!
>
Our kernel is of run-to-completion type. There are no operations
available that can put a process to sleep. Anyway, holding a resource
while sleeping or waiting for something may invite trouble in
hard real-time.

> So, explicit registration of resource ownership still has to take
> place. Refer to my question above.
>
>>> Is it possible that, at any given time, one can determine which
>>> source code line or which model element has caused a store to be locked?
>>>
>> No specific mechanism is planned for that. Anyway it can be done using
>> a debugger in a breakpoint.
>
> I don't see how that would help. How do you envision one should debug
> performance problems?
>
Scenario: A certain high priority response is sometimes late. You have to
find out where time goes in that specific case. The investigation is
quite hardware dependent. You need debugging writes to output ports,
oscilloscopes, and/or logic analyzers - or a good in-circuit emulator.
I don't know any generic software help for that.
Perhaps locking operations could provide a hook where a hardware-dependent
measurement code could be attached.
From: Boudewijn Dijkstra on 7 Dec 2009 07:17
Op Tue, 24 Nov 2009 23:40:22 +0100 schreef Ari Okkonen
<ari.okkonen(a)obp.fi>:
> Boudewijn Dijkstra wrote:
> > Op Fri, 20 Nov 2009 05:19:32 +0100 schreef Ari Okkonen
> > <ari.okkonen(a)obp.fi>:
> >> Boudewijn Dijkstra wrote:
> >>> Op Wed, 18 Nov 2009 17:09:39 +0100 schreef Ari Okkonen
> >>> <ari.okkonen(a)obp.fi>:
> >>>> [snip]
> >>>>
> >>>> The shared stores with locking operations improve the communication
> >>>> between tasks.
> >>> Compared to what? How did you come to this conclusion? Which
> >>> inter-task communication methods did you investigate?
> >>>
> >> An example is a measurement data block in a mechanical or chemical
> >> process control system. Several measurement tasks update hundreds of
> >> values in the data block each in own pace. Several control tasks read
> >> these values in different paces. There will be lots of messages sent
> >> back and forth if these tasks cannot share the same data store.
> >> Using messages to transfer and query values seems more complicated
> >> than just assigning or reading the values, including locking.
> >
> > Looks can be deceiving. I hope your design process does not base its
> > conclusions on mere assumptions and hearsay.
> >
> Our design process utilizes experience and experimental coding of
> solution choices. About experience:
> I have implemented and used both mechanisms. (My history with real-time
> started with some maintenance work to Honeywell H1642 time-sharing OS
> in 1973. Then I read Per Brinch-Hansen's Operating System Principles
> and wrote my first RTOS microkernel for Honeywell H316 in 1974 as a
> hobby project. I never gave up real-time/embedded since then.)
>
> Application engineering considerations:
>
> If using shared stores with locking, it is quite easy: 1) lock those
> stores you need, 2) read and/or update them, 3) release them
>
> To do the same with messages you have to: 1) define messages for data
> queries and updates, 2) write a task or tasks to contain the data and
> to answer the messages, 3) prepare for interleaved new events and
> server responses (this is explained later),
> 4) for data writes encode and send messages,
> 5) for data reads encode and send query messages, define a wait
> state for waiting an answer and decode the answer. All operations
> including several shared values must be programmed into the
> data-containing task in order to keep system-wide consistency.
>
> It is possible that a new event arrives for processing while your
> task is waiting a response from a data server task. You have to
> implement a mechanism to cope with that. (E.g. SDL has a save-operation
> for that issue.)

Or, an event queue.

> So, it seems (measured by words, at least) that applying message based
> solution is more complex.

Indeed. Using messages implies that you think beforehand about your
transactions. It enforces data encapsulation. Defining wait parameters
forces you to think about real-time constraints, something you should also
do when considering resource availability.

If you would just mindlessly lock and unlock without knowing how you are
influencing other tasks, you will (in a sufficiently complex system)
introduce problems at a late stage in the development process, which is
well-known to be an expensive moment to solve errors. Also, a messaging
philosophy forces you to work with a client-server model, which has the
advantages of being easy to distribute and more importantly it promotes
re-use of its loosely coupled elements.

Talking about distributed systems, is ReaGOS able to lock and unlock
remote resources? Or should one rather use a message interface there?

> Run-time considerations:
>
> First experimental codings suggest that those locking and unlocking
> operations are together about 12 simple statements in C plus a scheduler
> call in unlock. (Haven't measured clock cycles yet.)
>
> The message solution requires at least 900 clock cycles in ARM 7
> including two scheduler calls - switching tasks back and forth.

If a lock implies a wait, then also a task switch is needed. In
messaging, the task switching follows the data flow.

> So, it seems that running message based solution takes more time.
>
> >>>> Priority ceiling protocol keeps the locking operations simple,
> avoids
> >>>> priority inversion, and avoids deadlocks.
> >>> If you can lock, you can have deadlock. What if a process dies
> >>> before it has the chance to unlock?
> >>>
> >> In the priority ceiling protocol there are no specific locks for the
> >> resources.
> >> The priority of the task is raised so much that no other task having
> >> access to that resource [can] get scheduled. If the task dies, its
> >> priority has no meaning anymore.
> >> See e.g.
> >> http://en.wikipedia.org/wiki/Priority_ceiling_protocol
> >
> > Your assumption seems to be that process synchronization is achieved
> by
> > the scheduler alone, without the addition of explicit locking and
> > unlocking. What if a process holding a resource has to sleep for a
> > millisecond or so, giving another process the chance to access that
> > resource? Havoc would ensue!
> >
> Our kernel is of run-to-completion type. There are no operations
> available that can put a process to sleep.

Then what happens when trying to lock a resource that is in use? Surely
the process will wait until it is available?

> Anyway, holding a resource
> while sleeping or waiting for something may invite trouble in
> hard real-time.

Yes, but not all operating environments are run-to-completion, synchronous
I/O calls typically involve waiting.

> > So, explicit registration of resource ownership still has to take
> > place. Refer to my question above.



--
Gemaakt met Opera's revolutionaire e-mailprogramma:
http://www.opera.com/mail/
(remove the obvious prefix to reply by mail)
From: Ari Okkonen on 22 Dec 2009 10:43
Boudewijn Dijkstra wrote:
> Op Tue, 24 Nov 2009 23:40:22 +0100 schreef Ari Okkonen
> <ari.okkonen(a)obp.fi>:
>> Boudewijn Dijkstra wrote:
>> > Op Fri, 20 Nov 2009 05:19:32 +0100 schreef Ari Okkonen
>> > <ari.okkonen(a)obp.fi>:
>> >> Boudewijn Dijkstra wrote:
>> >>> Op Wed, 18 Nov 2009 17:09:39 +0100 schreef Ari Okkonen
>> >>> <ari.okkonen(a)obp.fi>:
>> >>>> [snip]
[snip]
>>
>> Application engineering considerations:
>>
>> If using shared stores with locking, it is quite easy: 1) lock those
>> stores you need, 2) read and/or update them, 3) release them
>>
>> To do the same with messages you have to: 1) define messages for data
>> queries and updates, 2) write a task or tasks to contain the data and
>> to answer the messages, 3) prepare for interleaved new events and
>> server responses (this is explained later),
>> 4) for data writes encode and send messages,
>> 5) for data reads encode and send query messages, define a wait
>> state for waiting an answer and decode the answer. All operations
>> including several shared values must be programmed into the
>> data-containing task in order to keep system-wide consistency.
>>
>> It is possible that a new event arrives for processing while your
>> task is waiting a response from a data server task. You have to
>> implement a mechanism to cope with that. (E.g. SDL has a save-operation
>> for that issue.)
>
> Or, an event queue.
>
>> So, it seems (measured by words, at least) that applying message based
>> solution is more complex.
>
> Indeed. Using messages implies that you think beforehand about your
> transactions. It enforces data encapsulation. Defining wait parameters
> forces you to think about real-time constraints, something you should also
> do when considering resource availability.

Yes, true. It is easy to miss the real-time responsiveness, if you don't
know what you are doing. The same is for many other aspects: priorities,
algorithmic complexities, etc.
>
> If you would just mindlessly lock and unlock without knowing how you are
> influencing other tasks, you will (in a sufficiently complex system)
> introduce problems at a late stage in the development process, which is
> well-known to be an expensive moment to solve errors. Also, a messaging
> philosophy forces you to work with a client-server model, which has the
> advantages of being easy to distribute and more importantly it promotes
> re-use of its loosely coupled elements.
>
Exactly. Locking a resource is comparable to disabling interrupts.
You must know what you are doing.
It delays some other response. You must know the affected processes and
ensure that they have slack enough in order not to miss deadlines.
In the design process you could define maximum locking times for the
resources, if needed. - And test them.

Yes, client-server model makes many issues clearer for complex systems.
However, it may make many issues more complex and slow in otherwise simple
systems. The new mutex feature in ReaGOS does not prohibit you to use
client-server arrangements when needed. It allows you to use
straightforward and simple solution where speed and simplicity
are of importance.

> Talking about distributed systems, is ReaGOS able to lock and unlock
> remote resources? Or should one rather use a message interface there?
>
ReaGOS is not a distributed kernel. Messaging is needed between processors.

>> Run-time considerations:
>>
>> First experimental codings suggest that those locking and unlocking
>> operations are together about 12 simple statements in C plus a scheduler
>> call in unlock. (Haven't measured clock cycles yet.)
>>
>> The message solution requires at least 900 clock cycles in ARM 7
>> including two scheduler calls - switching tasks back and forth.
>
> If a lock implies a wait, then also a task switch is needed. In
> messaging, the task switching follows the data flow.
>
When the priority ceiling protocol is used, locking does not imply wait.
You can always lock if you are scheduled. After you have locked, nobody
else that can even think about locking the same resource, cannot be
scheduled. They can be scheduled after you have released the lock.

[For priority ceiling protocol]
>> >> http://en.wikipedia.org/wiki/Priority_ceiling_protocol
>> >
>> > Your assumption seems to be that process synchronization is
>> achieved by
>> > the scheduler alone, without the addition of explicit locking and
>> > unlocking. What if a process holding a resource has to sleep for a
>> > millisecond or so, giving another process the chance to access that
>> > resource? Havoc would ensue!
>> >
>> Our kernel is of run-to-completion type. There are no operations
>> available that can put a process to sleep.
>
> Then what happens when trying to lock a resource that is in use? Surely
> the process will wait until it is available?
>
Referring above, a process that could try to lock the resource is not even
scheduled if the resource is locked (in priority ceiling protocol).

>> Anyway, holding a resource
>> while sleeping or waiting for something may invite trouble in
>> hard real-time.
>
> Yes, but not all operating environments are run-to-completion, synchronous
> I/O calls typically involve waiting.
>
The problem is avoided so that ReaGOS does not support any synchronous calls.
There is no call that can cause waiting.
(That may require re-thinking of some usual design patterns.)
From: Boudewijn Dijkstra on 7 Jan 2010 04:12
Op Tue, 22 Dec 2009 16:43:28 +0100 schreef Ari Okkonen
<ari.okkonen(a)obp.fi>:
> Boudewijn Dijkstra wrote:
> > Op Tue, 24 Nov 2009 23:40:22 +0100 schreef Ari Okkonen
> > <ari.okkonen(a)obp.fi>:
> >> Boudewijn Dijkstra wrote:
> >> > Op Fri, 20 Nov 2009 05:19:32 +0100 schreef Ari Okkonen
> >> > <ari.okkonen(a)obp.fi>:
> >> >> Boudewijn Dijkstra wrote:
> >> >>> Op Wed, 18 Nov 2009 17:09:39 +0100 schreef Ari Okkonen
> >> >>> <ari.okkonen(a)obp.fi>:
> >> >>>> [snip]
> [snip]

Thanks for your explanations. I certainly got the feeling that I've
learned something.


--
Gemaakt met Opera's revolutionaire e-mailprogramma:
http://www.opera.com/mail/
(remove the obvious prefix to reply by mail)
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Possible Solution
Next: Kernel image size