Attempted summary of "RT patch acceptance" thread
Quoted 8 lines · Paul E. McKenney
Hello!
Midway through the recent "RT patch acceptance" thread, someone mentioned that it might be good to summarize the various approaches. The following is an attempt to do just this, with an eye to providing a reasonable framework for future discussion.
Thoughts? Errors? Omissions?
Hi Paul,
I haven't yet gone through all your email in detail but it seems very well documented and precise.
I'd like to add some information about your section "7. Migration Within OS". I've now been working for more than a year on a project called ARTiS which precisely implements this approach. A announced was recently posted on the LKML :-) . You can find more information in this tread : http://lkml.org/lkml/2005/5/3/50 as well on our webpage www.lifl.fr/west/artis .
Concerning the QoS, we have been able to obtain hard realtime, at least very firm real-time. Tests were conducted over 8 hours on IA-64 and x86 and gave respectively 105µs and 40µs of maximum latency. Not as good as you have mentioned but mostly of the same order :-)
Concerning the "e. fault isolation", on our implementation, holding a lock, mutex or semaphore will automatically migrate the task, therefore it's not a problem. Of course, some parts of the kernel that cannot be migrated might take a lock, namely the scheduler. For the scheduler, we modified most of the data structures requiring a lock so that they can be accessed locklessly (it's the hardest part of the implementation).
Concerning the weaknesses, one point that you didn't mention is the difficulty to fully load the realtime dedicated CPUs. Tasks tends to migrate more away from the RT CPUs than they come back. In ARTiS, a modification of the load-balancer permits to keep most of the power but there is still probably some loss. Concerning the migration overhead, there must be some, but it's not very big and quite difficult to measure. Actually, the migration itself is light in CPU usage, the problem is that it unschedules the task so that it might take some time before the task is scheduled again (but if there is enough load on the computer, we lose mostly nothing).
Finally, as you pointed out, one major requirement is obiously to have several CPUs. Luckily, SMT and dual core processors are more and more common (ARTiS was succesfully tested on Pentium HT). Still, in the embedded market this is not so usual, so that's a weakeness point if you target very devices. Our implementation is oriented toward big applications that requires both RT properties and high performance (that's why it was developped on IA-64).
That's my 2 cents for your summary :-)
Eric
PS: please CC me when replying to the lkml.
Quoted 8 lines · Eric Piel
Quoted 7 lines · Paul E. McKenney
Hello!
Midway through the recent "RT patch acceptance" thread, someone mentioned that it might be good to summarize the various approaches. The following is an attempt to do just this, with an eye to providing a reasonable framework for future discussion.
Quoted 6 lines
Quoted 1 line
Thoughts? Errors? Omissions?
Hi Paul,
I haven't yet gone through all your email in detail but it seems very well documented and precise.
Thank you, glad you like it!
Quoted 6 lines
I'd like to add some information about your section "7. Migration Within OS". I've now been working for more than a year on a project called ARTiS which precisely implements this approach. A announced was recently posted on the LKML :-) . You can find more information in this tread : http://lkml.org/lkml/2005/5/3/50 as well on our webpage www.lifl.fr/west/artis .
Aaack!!! Don't know how I missed this, will review it and update the document. Hmmm... Checking the date, I plead near-terminal jet lag.
Quoted 4 lines
Concerning the QoS, we have been able to obtain hard realtime, at least very firm real-time. Tests were conducted over 8 hours on IA-64 and x86 and gave respectively 105µs and 40µs of maximum latency. Not as good as you have mentioned but mostly of the same order :-)
Quite impressive! So, does this qualify as "ruby hard", or is it only "metal hard"? ;-)
The service measured was process scheduling, right?
Quoted 6 lines
Concerning the "e. fault isolation", on our implementation, holding a lock, mutex or semaphore will automatically migrate the task, therefore it's not a problem. Of course, some parts of the kernel that cannot be migrated might take a lock, namely the scheduler. For the scheduler, we modified most of the data structures requiring a lock so that they can be accessed locklessly (it's the hardest part of the implementation).
Are the non-migrateable portions of the scheduler small enough that one could do a worst-case timing analysis? Preferably aided by some automation...
Quoted 10 lines
Concerning the weaknesses, one point that you didn't mention is the difficulty to fully load the realtime dedicated CPUs. Tasks tends to migrate more away from the RT CPUs than they come back. In ARTiS, a modification of the load-balancer permits to keep most of the power but there is still probably some loss. Concerning the migration overhead, there must be some, but it's not very big and quite difficult to measure. Actually, the migration itself is light in CPU usage, the problem is that it unschedules the task so that it might take some time before the task is scheduled again (but if there is enough load on the computer, we lose mostly nothing).
One approach would be to mark the migrated task so that it returns to the realtime CPU as soon as it completes the realtime-unsafe operation.
Quoted 7 lines
Finally, as you pointed out, one major requirement is obiously to have several CPUs. Luckily, SMT and dual core processors are more and more common (ARTiS was succesfully tested on Pentium HT). Still, in the embedded market this is not so usual, so that's a weakeness point if you target very devices. Our implementation is oriented toward big applications that requires both RT properties and high performance (that's why it was developped on IA-64).
Another approach is to insert a virtualization layer (think in terms of a very cut-down variant of Xen) that tells the OS that there are two CPUs. This layer then gives realtime service to one, but not to the other. That way, the OS thinks that it has two CPUs, and can still do the migration tricks despite having only one real CPU.
Anyway, interesting approach!
Thanx, Paul
Quoted 6 lines
That's my 2 cents for your summary :-)
Eric
PS: please CC me when replying to the lkml.
Quoted 8 lines · Paul E. McKenney wrote/
Quoted 4 lines
Concerning the QoS, we have been able to obtain hard realtime, at least very firm real-time. Tests were conducted over 8 hours on IA-64 and x86 and gave respectively 105µs and 40µs of maximum latency. Not as good as you have mentioned but mostly of the same order :-)
Quite impressive! So, does this qualify as "ruby hard", or is it only "metal hard"? ;-)
Well, you have to consider that this is still full Linux running. All the best we can do is to not make it crash or hung more than the vanilla kernel, it's still vulnerable to any bug of any driver :-/ In addition, I highly doubt this approach can ever have an implementation were the maximum latency is theoritically proven. The best we have is just measurements of the system running with high loads during very long time.
Quoted 2 lines
The service measured was process scheduling, right?
Yes, on IA64, from the hardware IRQ fireing to process scheduling (on x86 it's from kernel IRQ handling to process scheduling).
Quoted 11 lines
Quoted 6 lines
Concerning the "e. fault isolation", on our implementation, holding a lock, mutex or semaphore will automatically migrate the task, therefore it's not a problem. Of course, some parts of the kernel that cannot be migrated might take a lock, namely the scheduler. For the scheduler, we modified most of the data structures requiring a lock so that they can be accessed locklessly (it's the hardest part of the implementation).
Are the non-migrateable portions of the scheduler small enough that one could do a worst-case timing analysis? Preferably aided by some automation...
Well, ARTiS only modifies the schedule() function but there is probably too much possible interaction to really be able to prove anything (the fact that it's a SMP system doesn't help!).
Quoted 3 lines
One approach would be to mark the migrated task so that it returns to the realtime CPU as soon as it completes the realtime-unsafe operation.
We use a different approach: keep (small) statistics of the task doing often lock and the one that are more "computational". Then we migrate in priority the tasks that don't do locks. Your suggestion could be used at the same time but it might not be so efficient anymore. Additionally, in the current implementation, it's not so easy to know when a task which is running can go back to a RT CPU.
Quoted 5 lines
Another approach is to insert a virtualization layer (think in terms of a very cut-down variant of Xen) that tells the OS that there are two CPUs. This layer then gives realtime service to one, but not to the other. That way, the OS thinks that it has two CPUs, and can still do the migration tricks despite having only one real CPU.
Simulation of an SMP on a UP? This sounds quite heavy but it might be interesting to try :-)
Quoted 2 lines
Anyway, interesting approach!
Thanks,
Eric
Quoted 6 lines · Eric Piel
Quoted 5 lines · Paul E. McKenney wrote/
Quoted 4 lines
Concerning the QoS, we have been able to obtain hard realtime, at least very firm real-time. Tests were conducted over 8 hours on IA-64 and x86 and gave respectively 105µs and 40µs of maximum latency. Not as good as you have mentioned but mostly of the same order :-)
Quoted 8 lines
Quoted 2 lines
Quite impressive! So, does this qualify as "ruby hard", or is it only "metal hard"? ;-)
Well, you have to consider that this is still full Linux running. All the best we can do is to not make it crash or hung more than the vanilla kernel, it's still vulnerable to any bug of any driver :-/ In addition, I highly doubt this approach can ever have an implementation were the maximum latency is theoritically proven. The best we have is just measurements of the system running with high loads during very long time.
Hmmm... Might one make a theoretical proof that assumed the absense of bugs? Wholly unrealistic, I know, but seems like a reasonable question to ask. Besides, isn't theory -supposed- to be wholly unrealistic?
Quoted 3 lines
Quoted 1 line
The service measured was process scheduling, right?
Yes, on IA64, from the hardware IRQ fireing to process scheduling (on x86 it's from kernel IRQ handling to process scheduling).
Cool!
Quoted 8 lines
Quoted 8 lines
Quoted 6 lines
Concerning the "e. fault isolation", on our implementation, holding a lock, mutex or semaphore will automatically migrate the task, therefore it's not a problem. Of course, some parts of the kernel that cannot be migrated might take a lock, namely the scheduler. For the scheduler, we modified most of the data structures requiring a lock so that they can be accessed locklessly (it's the hardest part of the implementation).
Quoted 6 lines
Quoted 3 lines
Are the non-migrateable portions of the scheduler small enough that one could do a worst-case timing analysis? Preferably aided by some automation...
Well, ARTiS only modifies the
schedule()function but there is probably too much possible interaction to really be able to prove anything (the fact that it's a SMP system doesn't help!).
SMP does make it more complex, but not hopeless. If you can bound the number of threads, and if you can guarantee FIFO queuing on locks, then the locks can have bounded wait times. Not that any of the high-performance spinlocks actually have this property...
Quoted 9 lines
Quoted 3 lines
One approach would be to mark the migrated task so that it returns to the realtime CPU as soon as it completes the realtime-unsafe operation.
We use a different approach: keep (small) statistics of the task doing often lock and the one that are more "computational". Then we migrate in priority the tasks that don't do locks. Your suggestion could be used at the same time but it might not be so efficient anymore. Additionally, in the current implementation, it's not so easy to know when a task which is running can go back to a RT CPU.
OK. I suppose you could migrate it back as soon as it returned to user-mode execution. Might or might not be useful. The other approach would be once it dropped all of its locks, but, as you say, this could result in a large number of migrations...
Quoted 8 lines
Quoted 2 lines
Another approach is to insert a virtualization layer (think in terms of a very cut-down variant of Xen) that tells the OS that there are two
CPUs.
Quoted 3 lines
This layer then gives realtime service to one, but not to the other. That way, the OS thinks that it has two CPUs, and can still do the migration tricks despite having only one real CPU.
Simulation of an SMP on a UP? This sounds quite heavy but it might be interesting to try :-)
It can be quite light-weight -- you just have to carefully lie to the OS about what CPU it is running on. And no doubt fix a bunch of places where it makes assumptions about the two CPUs being real CPUs. :-(
Thanx, Paul
Quoted 5 lines
Quoted 1 line
Anyway, interesting approach!
Thanks,
Eric