cooperative multitasking scheme

Hi y'all

Quick but not so easy question (it may spawn a considerable thread...) We need to develop a cooperative multitasking kernel for various embedded platforms (See the implications and the complications?). One requirement is that c-functions should serve as "tasks". (Notably, these tasks perform very simple functions, e.g. polling push buttons, occasionally updating a display, polling an adc, and a whole slew of other things that are definitely not time critical.) The question is, how should cpu time be distributed, given the following: Task 1: Priority 1 Task 2: Priority 1 Task 3: Priority 1 Task 4: Priority 1 Task 5: Priority 4 Task 6: Priority 8 Should it be: T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum or: T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum or perhaps another scheme that does the assigned priorities right? A pointer would be very nice too, apart from an interesting discussion. None of us has a formal education in these matters... We are at a moderate loss...

Thanks in advance

Waldemar

Reply to
Marco Bleekrode
Loading thread data ...

There are so many RTOSes out there that are already written, to me it makes no sense to write one from scratch.

Reply to
Paul J. Bosselaers

So true, nothing is more fun then re-inventing the wheel, however... the requirement is that it has to be absolutely system independent, and furthermore, real time is not an issue! But it has to have a small footprint, no resource management, no i/o scheduling, whatsoever... just the bare "switch"...

"Paul J. Bosselaers" schreef in bericht news:T4e3d.463636$%_6.381885@attbi_s01...

Reply to
Marco Bleekrode

You must first define what you want priority to mean.

Should all priority 1 task run in preference to any priority 2 tasks, should all priority 2 tasks run in preference to any priority 3 tasks etc.

Are you just trying to give a bias toward higher priority tasks such that each level has certain percentage of the CPU time. Maybe all priority 1 tasks form a group that has 50% of the CPU time, all priority 2 tasks have

25% of the CPU time, all priority 3 tasks have 10% etc

Are you trying to improve the way tasks use CPU time based on how long they sleep (maybe increasing the priority of tasks if they are not ready to run so that they receive quicker attention when they are ready to run).

You really need to know what you want the priority system to achive before you look at ways of implementing your schedular. In some systems I have found it adiquate to use simple round robin with no prority, others have required just 2 levels and others 16. Sometimes trying to be too clever is really counter productive and you end up with a lot of wasted CPU time as the schedular does a lot of work just to return to the same task that last active.

Try writing a simulation to get a better feel for how the tasks interact withing the priority system.

If in doubt keep it simple!

Regards Sergio Masci

formatting link

Reply to
Sergio Masci
[...]

Quite impossible to say, from your problem description. I would actually suggest, for this particular case:

T6 T5 T6 T4 T6 T5 T6 T3 T6 T5 T6 T2 T6 T5 T6 T1

I.e.: distribute not just the 8 calls of Task 6, but also the 4 calls of T5 evenly.

As another reply already stated, what should be done strongly depends on what you want "priority" to mean, and what the requirements of your tasks are, in terms of minimum, average, and maximum time allowed between executions, and what their behaviour is in terms of time consumption per (cooperative) call of each task's function.

Then you should definitely get yourself some textbooks before you proceed. I've found Pont's "Patterns for Time-Triggered Embedded Systems" quite helpful, although it spans a rather large arc, and scheduling algorithms are only one aspect it covers.

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply to
Hans-Bernhard Broeker

and since you said in a reply to another poster:

the problem becomes much simpler. First, to be system independent we cannot use any timers so the key becomes what you define as priority. Assuming this means 'each time round the loop, do,if the highest priority task is ready to run then run it, else try the next highest prioity task, while there are tasks untried' then this is fairly easy to code.

Ian

--
Ian Bell
Reply to
Ian Bell

How independent? Without any code changes at all? That is hard to imagine.

A very simple completely self-contained cooperative multi-tasking manager can be written in about 100 lines of assembler code. I know because I have done it. This is hardly the size package that established RTOS vendors are interested in selling. You might have a hard time buying such a small package of functionality without bringing alone a lot of what you don't need. The only thing my cooperative multi-tasker does is manage separate stack pointers for each task. When any task calls suspend(), the next task is executed from its saved PC and saved stack pointer. A few registers are saved as well. I can't imagine doing this without some concession to the differences between processors. In particular, if the processer doesn't have the ability to save the call stack (like low-end PICs), it would be impossible, unless you restricted the tasks so that they could only call suspend from the top level of their call stack - the same level at which they received control. If you are interested in a x86 multi-tasker, I can send you the source code. (Is does not implement priority, though. You would have to implement that some other way.)

-Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

Reply to
Robert Scott

Your requirement is not clear to me. Why complicate a homebrew cooperative multitasker with priorities? If the "tasks" are performing "polling" of I/O, then basically the tasks are doing nothing but "waiting" (on an event) & so priority ranking of tasks may be unnecessary. Unless you're designing a control system, in typical systems the tasks are just sitting there waiting for an event, such as an operator pushing a key or a door to operate a reed switch. Even in motor controllers, the majority of software execution is initiated at the sample rate.

Also by keeping the "RTOS" simple, it makes it much easier to test and validate it for its intended use. By introducing priorities you increase the use cases that you need to test by several orders of magnitude -- bear in mind that it'll also make the (software) system more susceptible to deadlock.

Ken.

+====================================+ I hate junk email. Please direct any genuine email to: kenlee at hotpop.com
Reply to
Ken Lee

Various?

In any case, it's the features you need to describe well, I suppose.

That's fine and I've done that many times. This probably means (unless you limit the time of C function) that you need to accept a variable number of parameters. What I've done before is to make the return address point to the kill() function, so that the process self-kills when it finally returns. That may not be what you want, but it's one way of handling things. And I also placed (copied) the parameters sent to the create() function into the process stack. That way, when the function starts, it has access to the parameters in the usual way (assuming that the parameters are passed via the stack, which is not always the case -- sometimes registers are used for a few parameters.)

Keep in mind that various C compilers will not always use the same conventions, even on the same processor technologies, so your cooperative switch() may need to handle things differently on your 'various' platforms. But it's really trivial code, so having several incarnations isn't hard to do.

Since you said this is "cooperative" I want to clarify that I take this to mean "as opposed to pre-emptive." This means that your 'push button polling' or 'display updating' will only take place when some other process gives up the CPU to allow those processes to run -- the processor will not grab the CPU away without first cooperating, if you keep this 'cooperative' in nature. That can be just fine for your application or it can be a real problem. You will need to decide that.

Priorities are usually not so relevant in cooperative systems. When I use cooperative methods, it's usually just a matter of switching to the next process to give up a little time and that process, when it decides to, gives it up yet again for the next, and so on. By 'salting' each process with switch() calls at appropriate places, things work well without any priorities involved.

If you honestly want priorities in cooperative switching, keep in mind that the current process still doesn't yield up the CPU until it cooperates to do so, regardless of priorities, since there is no pre-emption going on to allow the O/S to yank away the CPU from the lower priority process. Probably not much of a problem, since the only way a higher priority process would take place would be if the current process raises the priority of another process or creates a new process of higher priority and, either way, the O/S can take control at that 'cooperative' point, I suppose.

I've not used priorities without also supporting pre-emption, so I cannot say I fully appreciate why you need them. Probably, the scheme you use should be based on what you decide is important to you, not on my opinion, since you are writing this for your own use.

Read Douglas Comer's Operating System Design: The XINU Approach. Very clear and easy for neophyte O/S designers to use as a leg-up.

I should add that, at its core, a simple cooperative O/S does not require queues or semaphores or priorities, etc. Heck, you don't even have to support a variable number of processes -- just a fixed set. If so, just some modest initialization code to set up the few stacks (if even that) and a single switch() function that runs only a very few lines in assembly to save the current register context, switch stacks, and then restore the saved context. I've done this in as little as perhaps 20 assembly lines and almost no C code at all, in a few cases. It's really not very hard. Of course, you are suggesting that you want to use any c function to start a process so you will need a create() call and there will be more code involved. But as long as it stays cooperative it won't be very difficult.

Best of luck, Jon

Reply to
Jonathan Kirwan

I agree.

I've been writing and using cooperative schedulers for a very long time in applications ranging from 4-axis bomb disposal machines to embedded web servers. I have never has to implement priority, although there have been a few occasions in which it would have been useful.

The tools we use instead of priority are a timebase mechanism (multiple slaved timers), and occasionally an event triggering mechanism within the scheduler. Our interrupt mechanics are completely separate from the tasker. The design has been implemented on CPUs ranging from 2 MHz Z80 to 200 MHz ARM.

Our design objectives have always been to get the highest *useful* CPU work under heavy load. Under these conditions the scheduler/OS is *all* wasted cycles, so you should keep it as simple/fast as possible. Under light load, the scheduler overhead matters much less.

You certainly have to learn to use a lightweight cooperative scheduler, but the benefits in resource constrained systems can be impressive.

Steohen

-- Stephen Pelc, snipped-for-privacy@INVALID.mpeltd.demon.co.uk MicroProcessor Engineering Ltd - More Real, Less Time

133 Hill Lane, Southampton SO15 5AF, England tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691 web:
formatting link
- free VFX Forth downloads
Reply to
Stephen Pelc

[Stuff Snipped]

Hi,

Have a look at "Multi-C" from MiX software. The book that accompanies the software discusses the basics of multi-threading and I think they basically implement what you want.

formatting link

Regards Anton Erasmus

Reply to
Anton Erasmus

Very, very, very independent...

Thanks for the offer, but alas... Assembler is not what I would call system independent. Nope, it has to be C and that's hard... Right now I have a prototype compiling flawlessly in Metrowerks Codewarrior HC08, Imagecraft AVR, and HiTech for the PICC. The ìnterface seems clean enough and the code is fairly predictable in its behaviour...

Waldemar

"Robert Scott" schreef in bericht news: snipped-for-privacy@news.provide.net...

Reply to
Waldemar

Priority in this particular case determines the order in which a task receives control over the cpu as well as the number of times within the period it takes to execute all tasks that are actively competing for cpu control.

Nope, just the other way around, but that is IMHO not relevant.

Well, an excact percentage cannot easily be determined, since we deal with a cooperative multitasker. In fact, a low priority task could simply block the whole kaboodle by going into an infinite loop (Remember e.g. Windows 3.x?) It's up to the programmer to design tasks in such a way that they give up cpu control after they've done their thing. Furthermore, it's the programmer's responsibilty to assign priorities such that more important functions are executed more often...

Indeed, a waiting task does not actively compete for cpu time, but it gets a priority boost. The same goes for a suspended or delaying task. In fact the schedulder is an attempt to mimich the behaviour of it's pre-emptive brethren...

Thanks for your input

Waldemar

Reply to
Waldemar

If you were given the order to implement the scheme you outlined, implement it as is.

If you are supposed to serve the keyboard and LCD in a multitasking system, dont try to make them fit your multitasking scheduler. Rather make the scheduler fit the keyboard and LCD requirements!

A human operator wont type more than 5-10 keys per second. Therefore keyboards usually are polled at 50 Hz rate, or similar. Install a timer interrupt or task at this rate, and give the rest of the CPU to whatever other task wants it. It makes no sense to poll the keyboard more often, just because your scheduling algorithm decides that its time for priority level X.

The LCD, unless its a controller-less type, isnt a multitasking item either. Usually, when a task produces LCD output, it can be visualized immediately. Delaying it only makes sense when the task cannot take a break from what its doing. In simple devices, such tasks are implemented as interrupt functions that modify status variables, which then are visualized in the main loop. Such loops dont need to run at high rate either, a) because LCDs dont visualize at more than 5-10 Hz anyways, and b) because human operators can not percieve the data when its updated faster. Numeric data for example should be stable for at least 1/2 sec, preferably more.

You see, depending on your application, the LCD is best served within the very task that produces the output (using its CPU time instead of a separate LCD task), or in a task with fixed timing (eg 1 Hz). No priority scheduling needed either.

I could go on, but Im not designing your product. You should analyse exactly what the tasks are supposed to do, and when and why. The implementation then becomes obvious, and Im almost sure that it wont involve priority-scheduling at all. You probably can do completely without multitasking, using just interrupts and the main loop. Or you do just two tasks, one for the hard work and one for the MMI, and assign absolute priority either to the MMI if you can, or to the hard work task when there is no way around it (no priority scheduling either).

Marc

Reply to
jetmarc

Does it allow tasks to give up control at various levels in the call stack? If so, then the multi-tasker must be able to manage separate stacks for each task. There is no C primitive that deals directly with switching stacks, unless it is something akin to longjump(). Does your C-only multi-tasker use longjump() to implement stack switching?

On the other hand, if you impose the rule that a task may give up control only if it is at the top of its call stack, then perhaps a multi-tasker can be written in C only. You would only need a list of function pointers, which are supported in C. But all the tasks would share a single call stack. In most of the applications that I have worked on, that would be a serious restriction.

My offer of the x86 assembler code was not meant as something you would use directly, but merely as an aide to seeing what minimum functionality is required in a cooperative multi-tasker.

-Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

Reply to
Robert Scott

"Robert Scott" schreef in bericht news: snipped-for-privacy@news.provide.net...

To answer your first question, yup, it does allow that through the use of setjmp()/longjmp(). Calls like Wait(), Stop(), etc. utilize the longjmp() to pass control back to the scheduler. However, there's no way to get back to the point right after the call to e.g. Wait(). It's up to the task to remember what it did just before it invoked the Wait(). As to your second remark/question... Well, actually one doesn't have to manage separate stacks in this case, because when a task gives up control of the cpu, either through a normal return or through the use of a longjmp(), the stack is cleaned up to the point where this task was invoked by the scheduler. But you can manipulate the stack pointer through the use of setjmp(). After its initial call (when it returns 0), the jmp_buf structure is filled with the program counter and the stack pointer. At that stage you may assign a different value to the stack pointer, i.e. the address of some byte array to serve as the task's private stack. Nope, no stack switching. I could have done that, but I decided against it, given the fact that most 8 bit microcontrollers have only limited amounts of RAM. I left other ramifications for what they were...

That is indeed what I did... pointer to functions... Actually, this isn't much of a limitation, not for the kind of applications I have in mind... Think of educational purposes (push a button, flash a light), thermometer, nothing fancy...

I understand that, thanks again.

BCNU

Waldemar

Reply to
Waldemar

Tried to parse this several times and I' still not sure I understand. So, combining it now with an earlier comment:

If I gather what you are saying, it's a new use of the term 'priority' to which I haven't been exposed. But I can see the utility in the idea, if I gather where you are going.

Do you mean that, given the above list of 6 tasks, there are 8+4+4*1 = 16 total switch events before it repeats? So that you want to execute T6 8 times out of

16, T5 4 times out of 16, and t1 through T4 each 1 time out of 16?

If so, and if I'm generally understanding you, then I think you'll need to come up with your own algorithm on this. I don't believe there is a standard here.

One suggestion that comes to mind would be to use a delta queue arrangement with integer deltas. When a process is inserted into the queue, it is inserted based on an assigned delta value for that process, as in:

void insert( pid_t proc, int delta ) { for each process (p) currently in the queue, (may be zero) if p.delta

Reply to
Jonathan Kirwan

One man's restriction is another man's salvation...

I've built this sort of runtime before, one which operates many tasks on one stack, with a recursively invokable scheduler (ie a call like "yield"). It was an incredibly delightful way to debug what was, on the target, a fully concurrent distributed system. Debugger support for multitasking schemes with multiple switchable stack or register contexts, where it even exists, is just nowhere near as easy to deal with.

The necessary restriction is an ordinary strict priority scheme - assign each task a priority number and allow tasks to wait only on tasks of higher priority. (This is easy with message-passing, probably so with other schemes).

The nice thing about this arrangement is that the restrictions which eliminate stack contention in the monolithic cooperative environment also happen to eliminate deadlock in the distributed concurrent environment. It's always nice to kill two birds with one stone. Particularly when you can determine that the birds are indeed dead with nothing more than static analysis ;)

The other portable choice is to insist that all task functions run for only a short time, and not provide preemption or a yield() type of call. This is, of course, the usual "while(1)" scheduler. Calling

*this* a restriction is in the eye of the beholder; the world is full of systems that run this way.
--
Grant Taylor
Embedded Linux Consultant
 Click to see the full signature
Reply to
Grant Taylor

The rules out implementing several tasks of equal priority, or else it imposes an unnatural allocation of CPU time just to stay within the rules of the game. Another programmer I knew worked for months on a cooperative multitasking scheme that used a single stack. No matter how he tried to order things, there were always cases of the stack getting messed up. He eventually gave up and implemented several stacks. Then everything worked beautifully.

-Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

Reply to
Robert Scott

That's not saying anything. You say "priority is determined", but that's not what I asked about: it's not how you choose the priorities, but what the scheduler is supposed to *do* with them that you have design. That's what the "meaning" of a priority is.

And you can't generally control two independent aspects (order of calling, and CPU usage) by a single number. Actually in a cooperative scheduler the priority cannot possibly control CPU usage --- that's why it's called "cooperative". If a task forgets to give up the CPU, it'll have it forever. Priorities have nothing to do with that, and they can't.

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply to
Hans-Bernhard Broeker

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.