Re: cooperative multitasking scheme
From: Jonathan Kirwan (jkirwan_at_easystreet.com)
Date: 09/27/04
- Next message: John Harlow: "Re: ATX power supply power switch"
- Previous message: R Adsett: "Re: cooperative multitasking scheme"
- In reply to: R Adsett: "Re: cooperative multitasking scheme"
- Next in thread: Paul Keinanen: "Re: cooperative multitasking scheme"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 27 Sep 2004 05:24:56 GMT
On Mon, 27 Sep 2004 00:16:09 -0400, R Adsett <radsett@junk.aeolusdevelopment.cm>
wrote:
>In article <7c7el05vht17d916l1ng0h1e9jqa264dsp@4ax.com>,
>jkirwan@easystreet.com says...
>> On Sun, 26 Sep 2004 22:31:45 +0300, Paul Keinanen <keinanen@sci.fi> wrote:
>>
>> >On Sun, 26 Sep 2004 18:03:37 GMT, Jonathan Kirwan
>> ><jkirwan@easystreet.com> wrote:
>> >
>> >>>Pre-emption requires a timer? I understand time-slicing would but surely
>> >>>you can do preemption w/o a timer. Useful yes. Necessary?
>> >>
>> >>The basic essence of preemption is that there must be some method by which the
>> >>operating system gains momentary control of the CPU, without cooperation by the
>> >>current process.
>> >
><snip>
>> Regarding the preemptive parts of what you are talking about, for example the
>> serial line interrupt or timer interrupt, you can indeed do what you are saying.
>> In fact, one often does. A low-level serial interrupt may mean that a buffer
>> goes from empty to not-empty and a process may be waiting on this event. Or the
>> incoming serial character may be posted to a process as a message, causing it to
>> "wake up." So, please don't misunderstand me here. I'm not suggesting that a
>> timer is the ONLY way that an operating system may preempt a process.
>>
>> I'm just saying that in the absence of interrupts from hardware functional units
>> other than a timer, a timer will be needed in order to round-robin processes of
>> equal priority (where implemented) or where priorities aren't specifically used.
>>
>> But you are right in the sense that preemption can reasonably come from other
>> sources. Sorry about not making that clear.
>I think that the question I was trying to ask. I didn't see where timers
>were needed to make a system preemptive.
Generally, you'll need timers for embedded operating systems. Almost every such
system I've worked on required some kind of precision timing mechanism for
certain kinds of processing. So it's almost always a good idea to plan for
that. Using a timer is almost second nature to me, because I almost always
implement sleep queues even when the system is running cooperatively and not
preemptively. In cooperative systems, where I choose not to use preemption at
all, the action of the timing event is to move the process from the sleep queue
to the ready queue but not to yank control to the new process, even if it has a
higher priority.
>Needed for time-slicing at a single priority, but the only systems I've used
>that used timeslicing are larger systems (mainframes, workstations, desktops)
>although I know they are used in some embedded systems.
I use simple round-robin in preemptive embedded systems, often enough, where I
don't really see a need for (or cannot afford the cost of) a priority system. A
process does NOT have to use its entire slice, you know. For example, if I have
a process to (1) update the display, (2) scan and poll a keyboard input, (3)
handle RS-232 parsing and query response, and (4) performs rather lengthy
computations on inputs and then updates an output; then I may use no priorities
at all but still use preemption so that I avoid excessively frequent use of
switch() calls. If the O/S preempts every 20ms, for example, it may switch to
the keyboard polling task, which may already be sitting in a scanning loop that
just moves the scan line to the next one, checks for anything to do, and if
nothing just calls switch() inside the loop before continuing again. In this
way, that process gives up any remaining time in its slice, voluntarily, because
it knows that there is nothing to do now. (The keyboard does not, in this case,
generate any hardware interrupt events at all.) But the task that performs the
long calculations doesn't need to salt those calculations with frequent switch()
calls, because the 10ms timeout will interrupt an in-progress calculation to
ensure that some time goes back to the polling keyboard routine every so often.
Probably a somewhat weak example, but perhaps it makes the idea clear enough for
you to construct a better one in mind.
>On the other hand every embedded system I've dealt with required a timer
>whether it was pre-emptive, cooperative or just a big loop. While I can
>imagine systems (preemptive or otherwise) that don't need a timer, I keep
>wanting to add timeouts to deal with issues like corrupted data and
>broken communication lines. And the systems that don't require timeouts
>seem to require pacing.
I very much appreciate having a sleep queue. A timer advances the time and may
move a process from the sleep queue to the ready queue and is needed for that
purpose, if you want any reasonable chance at having regular intervals for
processes. On DSPs, I've used as fine-grained timing specs for a process as
2us, with no more than 100ns restart jitter. Decent for much work.
>Mostly I was just wondering if I'd missed a subtle point that forced pre-
>emptive systems to have a timer, or maybe a definition that was different
>than I expected.
Hopefully, I relaxed your worries about that.
Jon
P.S. By the way, just by way of possible interest, here's the configuration
header for the O/S I wrote for tiny embedded processors with scarce RAM.
Mainly, I'm adding this so you can read the comments which explain some things
it does:
/*
File: config.h
Author: Jonathan Dale Kirwan
Creation Date: Fri 24-Jan-2003 11:42:28
Last Modified: Sun 16-Nov-2003 12:37:21
Copyright 2003, Jonathan Dale Kirwan, All Rights Reserved.
DESCRIPTION
This file defines the normal compile-time configuration criteria for the
operating system and some general symbolic constants used throughout. For
those configuration parameters requiring a yes/no answer, set them to zero
for no or to disable them and any non-zero value for yes (preferably 1.)
In addition, this file provides the type/size of certain key items in the
operating system; such as the size of the sleep and semaphore counters.
TARGET COMPILER
This module is designed to be compiled with general purpose C compilers.
MODIFICATIONS
Original source.
*/
#ifndef SYS_KERNEL_DECL
/* SYS_RTCLOCK
--------------------------------------------------------------------------
Whether or not to include a real-time clock for the operating system is
the central decision a user must make, in configuring this operating
system. A real-time clock is not necessary, but without it time doesn't
advance on its own, so there is no possibility for automatically moving
processes from the sleep queue to the ready process queue or for pre-
empting the currently running process. Without the real-time clock as a
resource, there is no determinism for sleeping processes, no round robin
sharing of CPU time, and no pre-emptive relinquishing of the CPU by a
lower priority process to a higher priority process - it all becomes a
matter of process co-operation.
Making a real-time clock available has a price to pay. Some CPU time is
used by the clock event handler each time the clock interrupts the CPU.
If the clock is operated too rapidly the time spent in its event handler
can consume nearly 100% of the CPU time, leaving almost nothing left for
normal process operations. So be careful about deciding the interval.
It also uses up a hardware timer resource, which may be scarce or used for
something else more important to the application. Further, any kind of
interrupt handling may require some non-portable feature in C (a #pragma,
for example, to designate a function as an interrupt function) or else
some assembly language and linker support in order to properly locate code
at the right 'vector address.'
So, enable this feature if either automatic movement of sleeping processes
to the ready process queue or pre-emption of the currently running process
is needed. If co-operating processes are sufficient to get the job done,
this feature can be disabled.
*/
#ifndef SYS_RTCLOCK
#define SYS_RTCLOCK (1)
#endif
/* SYS_SLEEPQ
--------------------------------------------------------------------------
Whether or not providing a real-time clock enables automatic movement of
sleeping processes, a user may choose to support the sleep queue. A sleep
queue is simply a place for processes waiting until some period of time
has expired. Processes are added into the sleep queue, in an order
determined by the delay they specify.
If the real-time clock is available, a counter for the top process in the
sleep queue is decremented and, when it reaches zero, the top process is
moved from the sleep queue to the ready process queue. If there are any
processes immediately following it in the sleep queue, which also have a
zero counter, they are also moved at this time. (This does not cause a
rescheduling event, so moving higher priority sleeping processes to the
ready process queue doesn't preempt the currently running process.)
Supporting a sleep queue without a real-time clock is a bit unusual -- as
normally there is no automatic change in their counters and no automatic
motion of processes from the sleep queue to the ready process queue unless
the currently running process to perform these functions as it deems them
appropriate. The behavior of the operating system, in this case, is to
automatically start the top entry in the sleep queue when there are no
remaining processes running (the last running process puts itself to sleep
or else waits on a semaphore or message.) This can actually be useful in
cases where no preemption is desired but where some processes should run
more frequently than others when cooperatively switching, using the delta
time sleep queue as a way of achieving that process shuffling.
(If you are curious about how this may be achieved, consider the idea of
four processes where P1 should run 4 out of 8 switches, P2 should run 2
out of 8, P3 should run 1 out of 8, and P4 should run 1 out of 8. If a
delta sleep time for P1 is given as 1, a delta time for P2 as 2, a delta
time for P3 as 4 and a delta time for P4 as 4 and then these processes use
this associated value to sleep on when they want to cooperatively switch
away, then the arrangement will work as desired.)
There is a secondary effect to specifying support for sleep queues. A
sleep queue requires a counter for each process to support timing their
motion back to the ready process queue. This will increase the RAM
requirements. For systems with very little RAM, this must be a
consciously considered decision.
*/
#ifndef SYS_SLEEPQ
#define SYS_SLEEPQ (1)
#endif
/* SYS_PRIORITIES
--------------------------------------------------------------------------
Enabling process priorities allows the operating system to organize the
ready process queue by process priority. Disabling this feature means
that all processes have, in effect, the same priority. The operating
system doesn't prevent processes with equal priority -- processes of the
same priority are simply added into the ready process queue after all
processes of equal or higher priority.
Process priorities have their expected impact when preemption isn't turned
on -- nothing takes place until the current process attempts to resume a
process (sleeping, waiting on a semaphore, or waiting on a message) with a
higher priority, tries to change the priority of another ready process to
a value higher than its own, or else tries to cooperatively reschedule.
It is only at these times that the operating system may switch to a higher
priority process.
There is a secondary effect when enabling process priorities. The process
priority feature requires adding a priority value for each process to
support sorting them in the ready process queue. This will increase the
RAM requirements. For systems with very little RAM, this must be a
consciously considered decision.
*/
#ifndef SYS_PRIORITIES
#define SYS_PRIORITIES (1)
#endif
/* SYS_MESSAGING
--------------------------------------------------------------------------
Messages provide a method of unsynchronized process coordination. They
are particularly useful, in contrast to semaphores, when a process
doesn't know how many messages it will receive, when they will be sent, or
which processes will send them.
These messages are posted directly to the process and are not of the type
which are left at rendezvous points, since this operating system is
designed for very small RAM requirements. Processes do not block when
sending messages and only the first message sent to a process is retained,
if several messages are sent to it before it can receive them.
Enabling this feature allocates room in each process node to hold the
latest message as well as code space for the support routines (of course.)
*/
#ifndef SYS_MESSAGING
#define SYS_MESSAGING (1)
#endif
/* SYS_QUANTUM
--------------------------------------------------------------------------
Set this to zero in order to disable pre-emption of the currently running
process. Any positive value will enable the feature and specify the
number of real-time clock ticks required in order to generate a
rescheduling event. A negative value has 'undefined' meaning.
Enabling pre-emption and the real-time clock allows the operating system
to automatically select higher priority processes in the ready process
queue and allows round robin sharing of CPU time for processes with equal
priority. Without these features, the only way a higher priority process
can get control is if the currently running process voluntarily requests
rescheduling.
The real-time clock is required for automatic action by the operating
system. Without the real-time clock, the quantum of the currently running
process isn't automatically updated and thus cannot expire -- so the
operating system cannot automatically generate a rescheduling event.
Enabling pre-emption this way, without the real-time clock, is permitted
but it isn't very useful.
A secondary effect of enabling pre-emption is that a memory location is
allocated for the remaining quanta available to the currently running
process. It's only a small addition, but on memory starved systems it may
be important.
*/
#ifndef SYS_QUANTUM
#define SYS_QUANTUM (25)
#endif
/* SYS_PLIMIT
--------------------------------------------------------------------------
This value sets a limit on the number of allowable processes. Naturally,
this affects the required RAM used to support them, as each process
requires a queue node to keep track of which queue the process is in as
well as space for process-specific state information. This value must be
positive and probably greater than 1.
*/
#ifndef SYS_PLIMIT
#define SYS_PLIMIT (20)
#endif
/* SYS_SLIMIT
--------------------------------------------------------------------------
This value sets a limit on the number of distinct semaphore queues
supported by the operating system. A zero value disables semaphore
support, entirely.
Semaphores provide a simple method of process coordination, often used to
synchronize their actions or cooperate in sharing common resources. Each
semaphore consists of an integer count, conceptually, with wait(s) calls
decrementing the count and signal(s) calls incrementing it. If the
semaphore count goes negative due to a wait(s) call, the process is
suspended or delayed. In that case, the next signal(s) call will release
exactly one suspended process. Semaphores are a synchronized method of
process coordination, essentially requiring one wait(s) for each signal(s)
call.
Each semaphore queue requires a small amount of RAM for a queue head and
tail node.
*/
#ifndef SYS_SLIMIT
#define SYS_SLIMIT (10)
#endif
/* SYS_DLINKEDQ
--------------------------------------------------------------------------
The system queues may be configured as either singly linked lists or
doubly linked lists. Enabling the doubly linked lists provides a faster
response from the operating system when moving processes from one queue to
another. But it does so at the expense of an extra link in RAM for each
queue node.
This is essentially a space versus speed option. Normally, doubly linked
lists are desired. But if RAM is very tight, disabling this option could
help. The amount of help will depend on the size of the qnode pointers
(usually 1 byte) and the number of processes and queues. As I said, it is
not a lot, but there are times when every byte counts.
*/
#ifndef SYS_DLINKEDQ
#define SYS_DLINKEDQ (1)
#endif
/* sys_status_t, SYS_FAIL, SYS_SUCCESS
--------------------------------------------------------------------------
Operating system function calls often return a success/fail status result.
*/
typedef int sys_status_t;
#define SYS_FAIL (0)
#define SYS_SUCCESS (1)
/* sys_priority_t, SYS_PRIORITY_MIN, SYS_PRIORITY_MAX, SYS_PRIORITY_DEFAULT
PRIORITY_MAXKEY
--------------------------------------------------------------------------
Configure as appropriate for process priority support. These may use
either signed or unsigned types, as desired.
SYS_PRIORITY_MIN and SYS_PRIORITY_MAX aren't used for more than some error
checking, when calling system functions to set process priorities. Just
make sure they are in the valid range of sys_priority_t and, of course,
that the minimum value is less than the maximum value. The only other
requirement is that PRIORITY_MAXKEY be greater than SYS_PRIORITY_MAX.
PRIORITY_MAXKEY is used for the tail entry in queues, so it needs to be
unique and larger than the greatest possible priority value.
SYS_PRIORITY_DEFAULT is only used when creating processes and shouldn't be
relied on.
*/
#if SYS_PRIORITIES != 0
typedef signed char sys_priority_t; /* process priorities */
#define SYS_PRIORITY_MIN (-100) /* minimum allowed priority */
#define SYS_PRIORITY_MAX (100) /* maximum allowed priority */
#define SYS_PRIORITY_DEFAULT (0) /* default priority, when created */
#define PRIORITY_MAXKEY (127) /* larger than highest priority */
#endif
/* sys_sleeptimer_t, SYS_SLEEP_MAXKEY
--------------------------------------------------------------------------
Configure as appropriate for the dynamic range needed by the sleep queue.
These values won't be allowed negative and are measured in timer ticks, so
it's probably better to keep them as unsigned values. (But signed values
will not harm anything.)
Remember that we are talking about timer ticks here, not seconds (unless
your timer ticks away according to second intervals.)
*/
#if SYS_SLEEPQ != 0
typedef unsigned char sys_sleeptimer_t; /* delta-time value */
#define SLEEP_MAXKEY (255) /* larger than any valid delay */
#endif
#define SYS_KERNEL_DECL
#endif /* #ifndef SYS_KERNEL_DECL */
- Next message: John Harlow: "Re: ATX power supply power switch"
- Previous message: R Adsett: "Re: cooperative multitasking scheme"
- In reply to: R Adsett: "Re: cooperative multitasking scheme"
- Next in thread: Paul Keinanen: "Re: cooperative multitasking scheme"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
