OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 2:14 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 21 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 2:17 am 
Hey everybody. I am troubled with real-time scheduling. All the os books (ok maybe not all of them) are talking about nuclear power plants or medical instrumentations in "Real-Time Scheduling" part. What I need to know is what can a real time schedule be in "our" understanding of real-time scheduling, for example is reading a floppy a real-time task? (I dont think so... Or is it?) How is it implemented in your code? How do you handle soft and hard real-time thingz? Also I think two real-time tasks cannot run in same system, right? I mean say they are unrelated to each other. Thanx.


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 2:43 am 
Offline
Member
Member
User avatar

Joined: Thu Nov 16, 2006 12:01 pm
Posts: 7612
Location: Germany
Ozguxxx wrote:
What I need to know is what can a real time schedule be in "our" understanding of real-time scheduling, for example is reading a floppy a real-time task?


That's a popular misunderstanding. "Real-time" has nothing to do with "real quick". Rather, it is about being able to guarantee that e.g. an interrupt handler will be executed no longer than X after the interrupt was raised. For some crucial applications (like nuclear power plants or medical appliances, or e.g. professional audio equipment, weapon technology etc.), that's a requirement.

Everything else is usually "best effort", or "soft real-time", which is a completely different ballgame.

You can write a really efficient, multimedia-enabled OS without ever touching the issue of hard real-time.

Quote:
How is it implemented in your code?


Check out "Rate Monotonic Scheduling".

Quote:
Also I think two real-time tasks cannot run in same system, right? I mean say they are unrelated to each other.


Wrong.

A real-time task, when starting up, hands the RTOS data on its run-time requirements (periodicity, latency etc.). That's the most obvious difference between hard and "soft" real time: The application must provide this data in a hard real-time environment! The thing is, that is only possible if the hardware and the OS version are known beforehand, i.e. at compile time of the application.

That's why hard real-time is such a special case: You just cannot do it correctly in a generic desktop OS. Hard real time is almost by definition a thing for embedded systems.

The system then decides if it can fulfill the requirements of the application. If yes, there must be no way that guarantee is broken.

With Rate Monotonic Scheduling, a system can guarantee that all requirements are met as long as CPU load does not exceed 69%. (That's why an application must tell the system in advance how much CPU load it adds to the system...)

As long as the guarantee can be given, there's nothing keeping any number of applications from running in real-time, concurrently, on the same hardware.

Unless you are into embedded systems, I'd daresay you can safely forget about hard real-time altogether. AmigaOS, fabled for its efficiency and multimedia capabilities back then, was a simple round-robin priorised scheduler with no concept of real-time...

_________________
Every good solution is obvious once you've found it.


Top
 Profile  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 3:12 am 
OK, so an application passes this data and tell os that I want to be run for example at least 50 milliseconds of every 100 milliseconds to do my job properly, which is a real-time task. Right? I think if this kind of requirement is set than real-time task runs properly. Also what do you mean by cpu load? In my understanding the non-real-time tasks do not put any cpu load, becuase cpu has no responsibility to finish them in some certain amount of time, right? Thanx for link and explanation, I will try to search them...


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 4:56 am 
Offline
Member
Member
User avatar

Joined: Thu Nov 16, 2006 12:01 pm
Posts: 7612
Location: Germany
Ozgunh82 - The Ozguxxx- wrote:
OK, so an application passes this data and tell os that I want to be run for example at least 50 milliseconds of every 100 milliseconds to do my job properly, which is a real-time task. Right?


Correct.

Quote:
Also what do you mean by cpu load?


It should be obvious that a given CPU can only support so many real-time tasks and still satisfy their requirements. If the load on the CPU exceeds a certain limit, it can no longer guarantee that it will have sufficient ressources to handle all requests in time.

Rate Monotinic Scheduling is a scheduling strategy that makes the decision whether the guarantee can be held very easy: With a CPU load < 70%, real-time can be guaranteed. With a CPU load >= 70%, it cannot.

Quote:
In my understanding the non-real-time tasks do not put any cpu load, becuase cpu has no responsibility to finish them in some certain amount of time, right?


They still do add to the CPU load, even if run at lower priority. Those tasks still have to be scheduled, and they put load on the memory management etc. Even if they run at lower priority, the CPU is more busy with them than without them, and so is more likely not able to fulfill the real-time requirements.

Usually, there is no non-real-time software on a real-time system.

_________________
Every good solution is obvious once you've found it.


Top
 Profile  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 9:13 am 
Hey, I have rewritten scheduler to support multiple queue based or priority based scheduling, although it causes serious startvation problems, I hope to fix in some way, I have three priorities: normal, high and real-time. Ill not consider dynamic priority. I will try to do real-time tasks as this rms thing suggests. What do you think about this scheme?


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 12:57 pm 
Offline
Member
Member
User avatar

Joined: Thu Nov 16, 2006 12:01 pm
Posts: 7612
Location: Germany
Ozgunh82 - The Ozguxxx- wrote:
What do you think about this scheme?


Starvation is a show-stopper for a scheduler (as in "must not happen").

If you allow real-time and non-real-time applications on one system, scheduling gets a bit tricky since the non-real-time applications add a system load you cannot determine beforehand. (CPU load might not even be the main issue here, they might still starve the system of other ressources.)

As usual, my question is: What do you want? Why do you consider hard real-time at all, and why would you want to mix it with non-real-time tasks on the same system?

_________________
Every good solution is obvious once you've found it.


Top
 Profile  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 1:05 pm 
Writing a general-purpose real-time OS is a very hard task. Writing a real-time OS for a specific need is much more useful. For instance, most of these questions are solved if you know you need to activate the warhead 20 nanoseconds before impact.


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 1:13 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5964
Location: In a galaxy, far, far away
if what you want to have is better GUI response time, just make sure the display manager will quickly get the control as soon as some user event come ... If you want to prevent one application to 'stick' on the disk/network interface, add a scheduler to the device ...

Hard real time is when you *need* to guarantee that a given task (for instance, reading a sensor) will be performed at least every 10ms and that a sensor trigger will imply a reaction on an actuator within 2ms ... This is for medical equipment, airplanes, embedded car electronic system, nuclear powerplant monitoring and cie. No need to say that in such a case, you hardly need the system to support virtual memory or a GUI.

OS that mix hard real time and usual OS services often make the "'legacy" OS kernel run as a RT task which will be running 30% of the cpu time, as the lowest-priority task ...
Note that on a platform like IA32, even this can be a nuisance, as your "legacy" OS might have programmed a DMA request which will lock the memory access for a too long period, and making the 'hard realtime' task unexpectedly suspended because it must wait for memory access (iirc).

Therefore, most "serious" RT platforms use some deterministic hardware (usually small slow processors like 68HC11 or PIC16F877, and at least having no automatic caching or paging which may make some code sequence behave differently from one run to another), which has a serial line to a PC sending control commands and reading system status, then reporting on a nice GUI running on a legacy OS the operations being done by the RT CPU.

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 2:37 pm 
Here's another example of a real-time system, which I like. Imagine a brewery, with a conveyor belt carrying bottles of beer around the factory. At the end of the line is a machine which puts the lids on. The conveyor belt moves relatively slowly, so that two bottles move under the machine per minute.

However, the timing must be spot-on: if the machine is more than, say, a millisecond too early or too late, the lid will miss the bottle and they will all fall off the conveyor belt.

So the operating system controlling this machine doesn't need to be fast, but its timings must be accurate.


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 4:29 pm 
Hi, firstly I must say that I dont want to deal with hard real-time stuff. I think I will eventually have to deal with real-time tasks while writing some drivers, I dont know a practical example yet but while interfacing with some hardware, driver has to be some kind of synchronized with this hardware, right? So driver should be working properly while not disturbing hardware (I mean we dont want it to lose some info that might not be meaningful when not read in time) and also not disturbing system, that is not disturbing other tasks, I think putting specific scheduler function for specific code might be a good solution but I also want to do this real-time scheduling interface as generic as possible, I mean I dont want to write different code for scheduling every driver. Maybe I am too paranoid about this subject but I at least want to consider what I might expect as a problem in future. I hope I am clear enough. Thanx...


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 5:52 pm 
You mean, "when an interrupt happens, the driver code needs to run right away"? Then that's normal. On a regular OS, interrupt code has priority over all user-mode code. Whatever user mode is doing, interrupts will always get serviced.


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Tue Aug 19, 2003 10:23 pm 
Offline
Member
Member
User avatar

Joined: Thu Nov 16, 2006 12:01 pm
Posts: 7612
Location: Germany
1) Hard real-time is not in any way "faster" than a best-effort scheduling. To the contrary, usually it is slower. It always makes it impossible to use 100% of the CPU power!

2) You don't need hard real-time anywhere in a general purpose OS, not even for drivers. No stock hardware has real-time requirements on its drivers.

Again, unless you are looking at embedded applications, chances are excellent you can just forget about real-time alltogether.

_________________
Every good solution is obvious once you've found it.


Top
 Profile  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Wed Aug 20, 2003 3:24 am 
OK, then it will be just fine to use priority scheduling until I start writing applications for national defense ministry or bottle factory or a nuclear power plant; or more realistically implement a gui right? :) Then how many priorities are enough to run appropriately without causing problems (or more simply how many priorities do you have and why? ;D)


Top
  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Wed Aug 20, 2003 3:41 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5964
Location: In a galaxy, far, far away
huh. So far, the _microkernel_ only has 2 priorities: normal and urgent (response to an event), but the scheduler can decide to implement more levels by ordering the queues the microkernel receives.

I would say between 16 and 32 levels should be enough. Most OSes work with dynamic priorities: the longer a thread/process (whatever your schedulable entity is) has been sleeping, the faster it will recover once it is ready again ...

maybe i should read back what i said here before going further

i also tried to explain the way dynamic priorities work in this previous post.
Hope it'll help

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Real-Time Scheduling
PostPosted: Wed Aug 20, 2003 3:44 am 
Offline
Member
Member
User avatar

Joined: Thu Nov 16, 2006 12:01 pm
Posts: 7612
Location: Germany
Ozgunh82 - The Ozguxxx- wrote:
OK, then it will be just fine to use priority scheduling until I start writing applications for national defense ministry or bottle factory or a nuclear power plant; or more realistically implement a gui right? :)


Again, wrong. ;-) Even a world-class GUI still doesn't have "real-time" requirements. If you press a button, you want the GUI to react as fast as possible, not within the guaranteed limits (which might actually be much longer!).

Making a GUI highly responsive is a matter of preemptability, message handling efficiency, and priorities. It has nothing to do with "real-time".

Quote:
Then how many priorities are enough to run appropriately without causing problems (or more simply how many priorities do you have and why? ;D)


Priorities and how to handle them is a very central point of OS design, and you can't easily tell which is the "right" number of priorities. A dynamic feedback scheduler probably needs more than a static one.

AmigaOS had 2^8 priorities (-128 to 127), of which 2^7 were usable (5 was the priority of the GUI itself, so anything above 4 is effectively killing the system). Of those, about 6-7 were actually used (0 was default, some users bumped tasks to 1 / 2, some decreased priorities to -1 / -2, background tasks ran at -127 or so.)

Windows has a couple of "categories", and tasks in a category can be bumped +/- 2, for a total of about 16-20 priority levels all in all.

I don't know how many priority levels Linux allows, but only three of them are commonly used (nice 0, 1, and 2).

Depending on your scheduler, the priority field will be evaluated quite often. Depending on your scheduling algorithm, you might want to make the field wider than actually necessary, so you don't have to fiddle with bit fields so often.

_________________
Every good solution is obvious once you've found it.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ]  Go to page 1, 2  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: 8infy and 63 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group