OSDev.org

Hey, I'm currently designing a small general-purpose RTOS (yes, that's basically an oxymoron). I already have throttling priority scheduling, basically, when a task gets in the "earliest" deadline limit (when the task should end after), it starts to give progressively higher priority to that task to ensure that by the time it reaches the "latest" deadline limit (when the task should end before), it will have finished. If the task gets within ((earliest + (latest - earliest) * 3) / 4) [3/4 into the "sweet spot"], the task will have achieved absolute priority to ensure that it has every chance to finish within proper boundaries.

As of now, I've been doing test runs in various virtual machines (BOCHS, QEMU, VBOX, VMWARE VS2) and getting lower and upper limits and then using those as the task limits in the code. But there has to be a way I can figure those out on the fly or without the need to re-compile. I thought about using my VMX code to start a virtual machine, log the timings, then start the "real run" with those timings, but that would *require* VMX support and would not be completely accurate. I don't know of any way to calculate them in the same run as the actual run, any ideas? Or am I even trying to approach this the right way?

Also, how can I figure out how much percentage complete the task is? That's another essential part that the OS would need to know in order to throttle back priority if the task is completing its run too early (before the earliest deadline). I have absolutely no way of doing that presently.

I know this is generally an embedded OS's league, but if feasible, I'd like to continue my little experiment.

What you are attempting to do is called "'best effort", or "soft real-time".

If you want to give guarantees (as in "hard real-time"), your applications must come with detailed run-time data before they are loaded.

01000101 wrote: As of now, I've been doing test runs in various virtual machines (BOCHS, QEMU, VBOX, VMWARE VS2) and getting lower and upper limits and then using those as the task limits in the code.

Could you be clear as to what limits you are trying to set in your scheduler? Are they the computations of the earliest/latest deadlines of the task, based on the requirement of the task?

01000101 wrote: Also, how can I figure out how much percentage complete the task is? That's another essential part that the OS would need to know in order to throttle back priority if the task is completing its run too early (before the earliest deadline). I have absolutely no way of doing that presently.

The OS IMHO has no way unfortunately of finding how much percentage of the task has been completed. A simple method of making the task itself convey the progress to the OS would be to have it increment a counter in it's TCB when it completes an atomic step in its execution; for example, dispatching a simple command to some hardware. The scheduler would read this counter and estimate the completion of the task. Now here if the task doesnt know the exact count that means it's completion, then the scheduler may adaptively determine what is the likely count of completion. Alternatively, preferably, the task would initially convey the completion count.

Having read this post before committing it, I reckon it may seem a wee bit harsh. I wasn't trying to be mean, honest!

Why is this,

small general-purpose RTOS (yes, that's basically an oxymoron)

, an oxymoron? Do you believe the terms "small" and "general purpose RTOS" to be contradictory? I would argue that a small OS would, by definition, lack overbearing or constrictive abstractions which would lead to a wider area of application. Or is it, perhaps, the terms "small general purpose" and "RTOS" you believe to be contradictory. If so, I invite you to look at the Everyman kernel - http://barrywatson.se/?p=3 - which I believe to be proof that a RTOS can be built that is "small general purpose".

Another thing you wrote was

embedded OS's league

. Is it not time that we lay the term "embedded" to bed? Some of us have worked on embedded systems that had over ten 32-bit processors with over a gigabyte of RAM. Can the term embedded really give anything to a technical discussion when it is used as a adjective?

Anyway, yep, it sounds like you are going for soft real-time or even some kind of on-time system (are you trying to minimize finishing jitter?). Are you implementing an algorithm documented somewhere where we can get more info? If you are interested in hard real-time then the blog on website where you can get the Everyman kernel also has articles on how to analyse scheduling and a resource access protocol called Stack Resource Policy (a type of semaphore).

Barry

The OS IMHO has no way unfortunately of finding how much percentage of the task has been completed.

He needs to give the OS the WCET (Worst Case Execution Time). This is the only temporal specification the OS needs. The others, start time and current time, are easily computed by the OS. So, (current time - start time) / WCET = % completion. The completion ratio would be valid for peak load which would be the worst case. At times where the system did not experience peak load the completion ration would be a "safe" calculation. Remember he's talking about real-time. He has a deadline to meet.

This reference could be interesting:

W. Shih, W.S. Liu, J. Chung, and D.W. Gillies. Scheduling tasks with ready times and deadlines to minimize average error. Operating System Review, 23(3), July 1989.

Barry
barrywatson.se

Solar wrote:What you are attempting to do is called "'best effort", or "soft real-time".

Yep, I already knew that, I must have forgot to clarify. Hard real-time would not be remotely practical for a general-purpose OS.

salil_bhagurkar wrote:

01000101 wrote: As of now, I've been doing test runs in various virtual machines (BOCHS, QEMU, VBOX, VMWARE VS2) and getting lower and upper limits and then using those as the task limits in the code.

Could you be clear as to what limits you are trying to set in your scheduler? Are they the computations of the earliest/latest deadlines of the task, based on the requirement of the task?

During task setup, I give the function a worst- and best-case timing (guesses based on previous runs) that the scheduler uses to throttle priority of that task to ensure it completes between those two timings (as it's just as bad to finish a task early as it is late). So yes, they are the computations of earliest/latest deadlines.

bwat wrote:Why is this,

small general-purpose RTOS (yes, that's basically an oxymoron)

, an oxymoron? Do you believe the terms "small" and "general purpose RTOS" to be contradictory? I would argue that a small OS would, by definition, lack overbearing or constrictive abstractions which would lead to a wider area of application. Or is it, perhaps, the terms "small general purpose" and "RTOS" you believe to be contradictory. If so, I invite you to look at the Everyman kernel - http://barrywatson.se/?p=3 - which I believe to be proof that a RTOS can be built that is "small general purpose".

I was pointing out the contradiction between "general-purpose" and "RTOS" as more-than-often a "general-purpose" OS does not contain real-time scheduling as it is necessary and will not provide as much performance as from a non-RT scheduler. Also, I see no mention of the "Everyman" kernel being a general-purpose OS. It just seems to be a very well laid-out real-time kernel. In fact, there's not much information about it at all.

bwat wrote:Another thing you wrote was

embedded OS's league

. Is it not time that we lay the term "embedded" to bed? Some of us have worked on embedded systems that had over ten 32-bit processors with over a gigabyte of RAM. Can the term embedded really give anything to a technical discussion when it is used as a adjective?

I was referring more towards "single-purpose" or non-general-purpose systems where their task is specific (non-general) and requires absolute fixation on one task and completing that task in a predictable manner every run.

bwat wrote:He needs to give the OS the WCET (Worst Case Execution Time).

Yes, that's my problem, finding out this value at run-time or some other relative value for use in the OS.

bwat wrote: This reference could be interesting:
W. Shih, W.S. Liu, J. Chung, and D.W. Gillies. Scheduling tasks with ready times and deadlines to minimize average error. Operating System Review, 23(3), July 1989.

I will check that out!

Hi,

bwat wrote:Having read this post before committing it, I reckon it may seem a wee bit harsh. I wasn't trying to be mean, honest!

Why is this,

small general-purpose RTOS (yes, that's basically an oxymoron)

, an oxymoron? Do you believe the terms "small" and "general purpose RTOS" to be contradictory? I would argue that a small OS would, by definition, lack overbearing or constrictive abstractions which would lead to a wider area of application. Or is it, perhaps, the terms "small general purpose" and "RTOS" you believe to be contradictory. If so, I invite you to look at the Everyman kernel - http://barrywatson.se/?p=3 - which I believe to be proof that a RTOS can be built that is "small general purpose".

I'd assume the oxymoron is between "general-purpose" and "RTOS". For a general purpose OS the average time something takes is important; and for an RTOS the worst case time is important. For example, imagine you've got a choice between one algorithm that always costs 1000 cycles, and a second algorithm that usually takes 500 cycles but on rare occasions might take 2000 cycles. For a RTOS the first algorithm would be considered much better, but for a general purpose OS the second algorithm would be considered much better.


Cheers,

Brendan

Brendan wrote: I'd assume the oxymoron is between "general-purpose" and "RTOS". For a general purpose OS the average time something takes is important; and for an RTOS the worst case time is important. For example, imagine you've got a choice between one algorithm that always costs 1000 cycles, and a second algorithm that usually takes 500 cycles but on rare occasions might take 2000 cycles. For a RTOS the first algorithm would be considered much better, but for a general purpose OS the second algorithm would be considered much better.

Sorry, I cannot let this go. If the deadline was 2001 cycles then both algorithms would be suitable for a real-time system. You didn't mention deadline yet you managed to make a judgement on suitability - that's why I had to reply. You cannot reason about real-time systems without involving the most important temporal specification.

Barry
barrywatson.se

01000101 wrote:

bwat wrote: This reference could be interesting:
W. Shih, W.S. Liu, J. Chung, and D.W. Gillies. Scheduling tasks with ready times and deadlines to minimize average error. Operating System Review, 23(3), July 1989.

I will check that out!

It wont help you - I suggested that reference when I thought you were out after imprecise calculation. I now think you're looking for on-time scheduling. You seem to want to minimize lateness and earliness, that is to say, have your finishing times as close to the deadline as possible.

Barry
barrywatson.se

Hi,

bwat wrote:

Brendan wrote: I'd assume the oxymoron is between "general-purpose" and "RTOS". For a general purpose OS the average time something takes is important; and for an RTOS the worst case time is important. For example, imagine you've got a choice between one algorithm that always costs 1000 cycles, and a second algorithm that usually takes 500 cycles but on rare occasions might take 2000 cycles. For a RTOS the first algorithm would be considered much better, but for a general purpose OS the second algorithm would be considered much better.

Sorry, I cannot let this go. If the deadline was 2001 cycles then both algorithms would be suitable for a real-time system. You didn't mention deadline yet you managed to make a judgement on suitability - that's why I had to reply. You cannot reason about real-time systems without involving the most important temporal specification.

I'm not reasoning about real time systems, I'm reasoning about real time OSs (where an OS is only part of a complete system).

An OS designer (usually) can't know which applications might be developed for their OS, and therefore can't assume anything about what deadlines these applications might have. Without knowing anything about deadlines, you can't assume that either of those algorithms will be suitable, and you can't assume that both won't be suitable, but you can know that one algorithm is more likely to be suitable than another.


Cheers,

Brendan

Would it be okay for the program to give the OS some hints or do you want the OS to figure out the time by itself?

Please, less debate about "general-purpose" vs. "RTOS". I'd really like to hear more about the ability to perform on-time scheduling and/or track the progress of tasks.

I know of no method that would allow the kernel to know ahead-of-time what sane values to use as input for earliest/latest deadlines without running it by hand before and re-compiling with appropriate values, but even this method would fail when on unknown hardware (or even different virtual machines).

Hi,

01000101 wrote:I know of no method that would allow the kernel to know ahead-of-time what sane values to use as input for earliest/latest deadlines without running it by hand before and re-compiling with appropriate values, but even this method would fail when on unknown hardware (or even different virtual machines).

I don't know about hard real time (I'd be very surprised if Solar was wrong when he said "your applications must come with detailed run-time data before they are loaded"), but for soft real time you could cheat.

If you assume that the application receives events and must respond to those events within some time limit; then for the first event sent to the application the OS can give it as much CPU time as possible and measure how long it takes to respond (and if it doesn't respond in time, then the OS couldn't have done anything to make it respond in time anyway). Then the OS can use the time it took to handle the first event as a way to estimate how long it might take to handle the second event, and allow for this length of time (plus a huge margin for error) for the second event. As more events are handled by the application the OS gets a better idea of how long the worst case response time is, and could reduce that huge margin for error down to something reasonably close to the worst case. For e.g. something like "estimated_time = worst_case_so_far + some_constant/events_measured_so_far + another_constant".

Of course you could track the overall worst case time, and also track the worst case time for each specific type of event (as it's likely that different types of events have different characteristics), and then record this information in a file or something and use it next time the application is run.

Note: I'm not convinced finishing early matters too much - use a "oops I finished early" delay before making it known that you're finished if it does matter.


Cheers,

Brendan

Brendan wrote:Note: I'm not convinced finishing early matters too much - use a "oops I finished early" delay before making it known that you're finished if it does matter.

I'm no expert on real-time scheduling but I thought of this too. However, it's not that black and white. It's true that you could finish the task earlier and put the thread to sleep - this would certainly make the workload more bearable if a bunch of tasks were to come along before the earliest deadline for the first one. There might be cases when you actually don't want this to happen - think about multimedia (this is a "general-purpose RTOS", no?). You need to have a flexible enough scheduling policy that would allow both types of situations.

Even with media, I can't picture a scenario where "too quick" would matter. Unless, of course, you're doing absolute timing (like those 286 games that became unplayable on the 386 because they ran too fast).

RT is about being able to serve a contract, repeatedly, reliably, in no more than X milliseconds every Y milliseconds. Whether you put the thread to sleep during its execution to keep it from finishing early or at the end should not matter, ever. IMVHO.