|
Thoughts from Thorkil
|
Do you have a topic you'd like Thorkil to write about? Click
here to send a request. |
Tasking and Priority
Inversion in Ada
When writing tasking applications you face the
problem of assigning priorities to tasks. You may choose to let all
tasks have the same priority, but by doing so you forfeit the
possibility of assuring that some tasks are more crucial than
others.
Many embedded systems are based on a regular
processing scheme, where the crucial tasks must complete their
processing within a fixed period of time. In other words a subset of
the tasks must all complete their regular activity within a
specified deadline for the total system to be fully operational. The
remainder of tasks may be allowed to complete their activities
infrequently, as remaining time allows.
Of course the sum of processing time for the crucial
tasks within each time frame should not exceed this time frame, but
even if say 70% of the time frame is required, fluctuations in the
processing speed may mean that in some time frames the time spending
is above and in others below the 70%. To allow for such variations
the crucial task time spent should not saturate the available time
frequently, as this would leave virtually no time for the non
crucial tasks. If this occurs and the time frame is a fixed entity,
the solutions are to use a faster processor that allows more
processing to occur, or to reconsider the crucial task set and maybe
allow some tasks to complete within two or more frames.
The key issue is controlling the execution pattern.
The fixed time frame model can be implemented by a simple kernel
that for each activity outlines the frequency of which it has to
run. Interrupts arriving within a time frame must be recorded and
passed to the activity, when it is its turn to run. Such a
sequential scheme can work, but obviously has some constraints,
especially when it comes to external events. Also a long running
activity must split itself in to subactivities that never exceed the
allocated time. Setting up the needed activity tables is difficult
and the interaction between activities must be very rigid.
In Ada you would use the tasking concept and assign
the activities priorities according to their importance - the
crucial tasks get high priorities, the less important low. Since the
Ada tasking model allows task preemption, higher priority tasks will
be scheduled to execute, when they need to, and the priority tasks
will run in the spare time. Tasks may even be set up to respond to
interrupts.
This sounds like the ideal model for an embedded
system, but there is a snake in paradise and that is the fact that
all these tasks depend upon each other in various ways - they may
need to share common resources such as buffers and they may need to
communicate with other tasks.
Common resources can be shared safely through the
use of semaphores: if you need access to a common buffer you ask for
the semaphore, await the grant, do what you have to do, and release
the semaphore again. In very time critical cases the semaphore can
consist of disabling interrupts at entry and enabling at exit, which
effectively will shut any other tasks out, including interrupts, but
if the disable time is unpredictable it may have severe impacts on
the system behavior, as interrupts may be lost or high priority
tasks prevented from being scheduled, when no timer interrupts occur
to set them going.
Task communication uses entry calls and accepts.
Via the select construct several entry calls, accepts and delays (timeouts) may be
combined, allowing more flexibility. There are rules for priority
boosting in the rendezvous-code, the priority being the
higher of the caller and callee. Interrupts may also be allowed to
perform a smaller set of entry calls.
Common for this interaction between tasks is that
control is transferred from the caller to the called task and that
the caller is suspended, until the rendezvous is completed, possibly
with transfer and handling of data in both directions.
Ada places no rules as to which task entries you are
allowed to call, so a high priority task may call an entry in a low
priority task, and this is where the problem of priority
inversion can occur, that is when the highest priority task is
not executing, when it could.
Some simple examples illustrate the problem. We
require three tasks High, Middle, and Low with priorities according
to their names. At a point in the processing High and Middle have
suspended themselves and are not running, so Low executes and grabs
a semaphore S for a buffer access. Low gets S and then Middle wakes
up and preempts Low, which is still sitting on S. Shortly after High
wakes up, preempts Middle and tries to grab S, but must wait for Low
to release S. Middle is now the only executing task and may continue
forever, locking Low from releasing S and set High going.
The same effect can be established if Low is about
to enter an accept, but prevented from getting there by Middle. Then
High gets in and tries to make an entry call to Low, but must wait,
because Low is not ready to accept, and again Middle is happily the
only executing task.
It may be argued that the design is bad and that
High should never attempt to call Low, or at least put a time-out on
the call, but often it is important that the Low activity is set
going, so designing the way out is not so simple.
In such a system it is very difficult to say
something definite about tasks meeting their deadlines, because
priority inversion may destroy the picture, even if all the crucial
task processing is possible within a time frame and there is extra
time available.
To resolve this problem we have to bend the rules of
Ada83 slightly in two ways:
The first is to insert calling tasks in priority
order rather than FIFO for the called task. This will ensure that
we favor the high priority tasks among those waiting to be
processed in another task.
The second is to boost the priority of the task we
are calling or the locking task of a semaphore to the priority of
the caller, when this is higher. The called task is now
temporarily in the crucial task set and can therefore reach the
accept or release-of-semaphore point sooner, as no middle tasks
can block it out. Once the point is reached for the called task it
may now engage with the awaiting High task after which its
priority drops to normal again.
With this technique - and provided that all tasks
are well behaved and allow other tasks to run at regular intervals -
the crucial tasks=
deadlines can be met, and the whole system still benefits from
immediate responses to interrupts and safe task communication.
Ada83 requires FIFO queuing policy, but violating
this makes sense in an actual system. The priority boosting is a
convenient implementation technique that does not violate the Ada
tasking model. From a runtime perspective the priority based queuing
takes longer than the simple FIFO, but usually the queues are not
expected to be long, so it does not matter that much, whereas the
priority boosting incurs more task scheduling as task are raised and
lowered in priority more frequently. The overall system performance
on the other hand gets much more predictable.
The DACS-Ada83 system offers the Rate Monotonic
Scheduling (RMS) tasking model which implements the above
described techniques, as well as the normal Ada tasking model, which
in many cases fulfills the overall system needs, despite of
occasional priority inversions.
SCORE-Ada95 supports that you may select your
preferred queuing policy, as well as implements priority ceiling
to be used with Ada95's protected objects to secure
nonpreemptible processing of shared data. The SCORE-Ada95 tasking
runtime system comes in two flavors: one that uses FIFO queuing the
Ada83 way, and one the uses priority based queing as well as rate
monotonic scheduling behavior.
Many DDC-I customers have benefited from the use of
the Ada83 tasking models offered and thereby proven that Ada is a
suitable language for complex embedded applications and that the
resulting systems perform as anticipated. Some DACS-80x86 tasking
variants have additionally been verified to conform to FAA level A
standards.
 |
About the Author
Thorkil Bjørn Rassmussen has worked with DDC-I for over 20
years. He has a Master of Science, Computer Science, from
University of Copenhagen. Thorkil has substantial experience
with all of the DACS tools and is the key individual
involved in all FAA certifications for the DACS product
line. Thorkil lives with his wife Jane and two children
Jonas and Tine, just outside of Copenhagen, Denmark.
|
[
Back to Top ]
The
Power of Gratitude
By Linda Rising
risingl@acm.org
www.lindarising.org
I’m just back from what has become an annual September in
Scandinavia, where I attended an international conference called
JAOO. I enjoy this conference because it gives me a chance to see
Denmark again. My husband, Karl Rehmer, and I lived there for a year
in 2000-2001. I notice changes in each return—some are more
provocative than others! For instance, Halloween seems to be making
more of an impact. I see more pumpkins and more costumes. Soon
little Scandinavian trick ‘r treat’ers will be knocking on the
doors in Copenhagen! I don’t see any evidence that the other
popular fall holiday is making any inroads. Unfortunately,
Thanksgiving seems to be typically American. Yet, some research I’ve
been reading indicates that this practice of giving thanks has
enormous potential to help us, in our daily lives, in our teams, and
in our organizations.
As faithful readers of this column know, I have a book coming
out, written with my good friend, Mary Lynn Manns, Fearless Change:
Patterns for Introducing Change: http://www.awprofessional.com/title/0201741571.
One of our most important patterns is "Just Say Thanks."
It’s a surprising pattern, not only because it seems so obvious
(but isn’t, of course, like many patterns), but also because I
keep learning about how powerful it is.
It seems obvious that expressing appreciation would make the
recipient feel good, but now we are learning that the giver also
benefits! I was surprised to learn that a considerable number of
researchers are investigating what makes people happy. Some of this
research is looking at the impact of gratitude.
Students of religion and philosophy have been writing about
gratitude for ages. These writers seem to agree that gratitude is a
key element in the life of those who espouse any religion or
philosophy.
A noble person is mindful and thankful of the favors he
receives from others. The Buddha
The essence of all beautiful art, all great art, is gratitude.
Friedrich Nietzsche
Gratitude is not only the greatest of virtues, but the parent
of all the others. Cicero
Dr. Robert Emmons of the University of California, Davis and Dr.
Michael McCullough of the University of Miami are just two of the
many psychologists who are conducting experiments in this area.
Here are some of their results:
-
In an experimental comparison, those who kept
gratitude journals on a weekly basis exercised more regularly,
reported fewer physical symptoms, felt better about their lives as
a whole, and were more optimistic about the upcoming week compared
to those who recorded hassles or neutral life events.
-
A related benefit was observed in the realm of
personal goal attainment: Participants who kept gratitude lists
were more likely to have made progress toward important personal
goals (academic, interpersonal and health-based) over a two-month
period compared to subjects in the other experimental conditions.
-
A daily gratitude intervention (self-guided
exercises) with young adults resulted in higher reported levels of
the positive states of alertness, enthusiasm, determination,
attentiveness, and energy compared to a focus on hassles or a
downward social comparison (ways in which participants thought
they were better than others). There was no difference in levels
of unpleasant emotions reported in the three groups.
-
Participants in the daily gratitude condition were
more likely to report having helped someone with a personal
problem or having offered emotional support to another, relative
to the hassles or social comparison condition.
-
In a sample of adults with neuromuscular disease, a
21-day gratitude intervention resulted in greater amounts of high
energy positive moods, a greater sense of feeling connected to
others, more optimistic ratings of one’s life, and better sleep
duration and sleep quality, relative to a control group.
Some of the observations from these scientists based on
scientific surveys:
-
Grateful people report higher levels of positive
emotions, life satisfaction, vitality, optimism, and lower levels
of depression and stress. The disposition toward gratitude
appears to enhance pleasant feeling states more than it diminishes
unpleasant emotions. That is, grateful people do not deny or
ignore the negative aspects of life.
-
People with a strong disposition toward gratitude
have the capacity to be empathic and to take the perspective of
others. Grateful people are rated as more generous and more
helpful by people in their social networks.
-
Grateful people are more likely to acknowledge a
belief in the interconnectedness of all life and a commitment to
and responsibility to others.
-
Grateful individuals place less importance on
material goods; they are less likely to judge their own and others
success in terms of possessions accumulated; they are less envious
of wealthy persons; and are more likely to share their possessions
with others relative to less grateful persons.
-
The experience of indebtedness is less likely to lead
to a desire to approach or make contact with others relative to an
experience of gratefulness. Thus, indebtedness tends to be an
aversive psychological state that is distinct from gratitude.
It’s true that while religious scholars and philosophers have
been interested in the topic of gratitude for ages, the appearance
of scientific studies in this area is relatively new. For most of
us, this virtue is something we associate with admonitions from
parents or grandparents to be "thankful for our
blessings."
Here’s a little more detail on one of the studies. The
researchers divided several hundred people into three groups. The
subjects in each group were instructed to keep a different type of
journal. One group simply recorded daily events. The second group
recorded daily hassles (this group kept busy, right?). The third
group listed things they were grateful for.
What do you think would have happened if you had been in one of
these groups? Here are the results—some you might have expected
and some you might find surprising. The last group (the grateful
group) reported more alertness and optimism and more progress toward
goals. These people also felt more loved. One suggested hypothesis
for this last result is that when you’re appreciative and kind,
other people mirror that back. As readers of an earlier column might
remember, there is an influence principle at work when you give
something to another person (yes, even appreciation). There is a
tendency for us to want to give something back.
Research on grateful people also finds that they report more of a
sense of the interconnectedness of all life. What’s encouraging
about this is that even if we can’t change the world, we can
always change ourselves.
The hopeful thing about all this research is that anyone can do
it, that is, we can all get better at appreciating what goes on in
our lives. By writing things they were grateful for in their lives,
subjects would become more aware of just how many things there were
in this category. By focusing on this aspect of their lives, they
would become more in tune with the interconnectedness in life.
I’m recalling a story about a married couple celebrating their
50th wedding anniversary. The husband, when asked for any
secrets for such a long relationship, replied, "Give and take—but
mostly give!" Surely this giving has to include giving thanks.
Thanking spouses, thanking other family members, thanking team
members and others in our organizations. How important is that?
I don’t want to stop you from buying a copy of Fearless Change—but
here are some stories from the pattern "Just Say Thanks."
A friend of mine was laid off from a large company where he had
worked nearly 30 years. I saw him after his last day and he said
that the worst thing about the experience was that no one, not
even his boss, had come by to say they would miss him or that they
appreciated his work. I thought about my last day when I was laid
off. I recall a constant stream of people coming by to share a
brief story— how something I had done or said had influenced
their life for the better—how I had made a difference for them
and the company. I don't remember sadness on that day but an
overwhelming gladness at having had the chance to work in that
company with those people— and all they did was just say
"Thanks!"
***
I was a team leader at a large satellite telecom company. As
each phase of the project was completed, I wrote personal,
printed hardcopy letters to the supervisors of everyone who
contributed (they were all contractors), expressing my
appreciation for their effort. The trickle down benefit was
amazing. The contractors were surprised and delighted to be
treated well and even complimented, and consequently the
barriers between the company I worked for and the contractors
came down, at least in this area. Such expressions have a big
pay off over the long term.
Think about it. Just taking a little time to appreciate those
around you. It’s such a small investment. And, there are,
according to our researchers, not only no side-effects, but the
possibility of incredibly huge returns.
I benefit (quite often, I might add) when others/things are
simply doing their job. When I experience this and respond with
thanks, my world changes. Try it. Go through one whole day, saying
"thank you" to everything and everyone who does
something that serves you in any way.
This is so simple! It involves simply focusing on all that others
do for you, for you personally, for you as a member of a family, for
you as member of a team, for you as a member of an organization.
"Just Say Thanks" to all those people for all they do for
you.
Even though the book has been published, I still collect stories.
If you try this pattern and want to share your experience, please
send it along. Here are my thanks in advance! Thanks!!!
 |
About the Author
http://www.lindarising.org
risingl@acm.org
Linda Rising has a Ph.D. from Arizona
State University in the area of object-based design metrics.
Her background includes university teaching as well as work
in industry in telecommunications, avionics, and strategic
weapons systems. She is the author of numerous articles and
has published three books: Design Patterns in
Communications, The Pattern Almanac 2000, and A Patterns
Handbook. She is currently writing a book with Mary Lynn
Manns: Fearless: Introducing New Ideas into Organizations, to appear in September 2004. |
[
Back to Top ]
|
