Acorn Arcade forums: Programming: Pre-emptive Multi-tasking
| |
Pre-emptive Multi-tasking |
| |
Loris (11:11 22/6/2004)
ninj (12:16 22/6/2004)
Loris (13:32 22/6/2004)
ninj (16:10 22/6/2004)
Loris (17:07 22/6/2004)
ninj (17:47 22/6/2004)
mavhc (08:05 23/6/2004)
adrianl (08:50 23/6/2004)
Loris (10:43 23/6/2004)
adrianl (11:44 23/6/2004)
ninj (16:00 23/6/2004)
|
| |
|
Tony Haines |
Message #55969, posted by Loris at 11:11, 22/6/2004 |
 Ha ha, me mine, mwahahahaha
Posts: 1025
|
MrChocky said in a comment on a Drobe article:
In any case, the figures quoted sound extravagant to say the least. Even given the enormous difficulties in implementing PMT, and perhaps resolving some other very hard OS issues. Could someone explain to me why retro-fitting preemptiveness into RiscOS would be so hard?
Here is my naive understanding of the issue:
cooperative MT: do a bit of work then hand back control.
preemptive MT: do what you like and the OS will take back control when it feels like it.
Why couldn't we just turn wimp_polls into a 'hint', and let the OS take control again at regular intervals as well? It is obviously possible to interrupt misbehaving tasks, so why not just do them all?
Wimp_poll[idle]s would be hints because if control was returned within a certain amount of time the task should get a second chance to do some processing.
I suppose there might be problems with some tasks attempting to perform certain things in an 'atomic' manner (where a value could be changed by another task but was relied on to remain constant.
The trivial fix would just keep a list of apps not to interrupt (probably a good idea anyway) like aemulator apparently does.
If there were any such problems which broke a large number of apps, they could be fixed by detecting the start of the sequence (which would probably be an SYS call) and not pre-empting that task until it had wimp-polled. |
| |
 [ Log in to reply ] |
| |
|
ninjah |
Message #55974, posted by ninj at 12:16, 22/6/2004, in reply to message #55969 |
Member
Posts: 288
|
Indeed, PMT has already been implemented for RISC OS - see wimp2. However, that has compatibility issues with a significant minority of software, and the improvement in responsiveness wasn't exactly dramatic. It may be argued that the multitasking system should not reside in the WIMP. Certainly all PMT systems I can think of off the top of my head implement it in the kernel.
As an aside, the way that SpamStamp integrates into the POPstar transport relies on it freezing the machine as it runs. If you suddenly made it multitask it would break, and I expect there are more subtle ways that many programs rely on the environment not changing from one call to Wimp_Poll to the next.
Certainly for an RTOS you'd need to have support in the kernel since even interrupt responses usually have to be multitasked. |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #55977, posted by Loris at 13:32, 22/6/2004, in reply to message #55974 |
Ha ha, me mine, mwahahahaha
Posts: 1025
|
As I understood it wimp2 was an opt-in system, which would at least avoid any compatibility problems I suppose.
However, I wasn't proposing that a third party try to cludge it in. Really I was just wondering if it really would be virtually impossible to retro-fit the architecture into the operating system, if you were, say, Castle, making a whole new version.
I really don't know much about SpamStamp, it sounds like it would break. But presumably this could be fixed either elegantly with a new version of POPstar with an appropriate hook, or inelegantly by adding POPstar to the do-not-preempt list.
Relying on bodges is really not the way to improve an OS. I'm sure SpamStamp is perfectly functional now, and presumably that was the only way to retro-fit its functionality onto POPstar. But I'd rather development was done properly for the future rather than piling hack upon hack. Otherwise we might as well just use Windows.
(Patching old programs to work, and independent hacks to make things work are of course fine.)
About the whole environment thing I guess this is the real question. How much moving around of stuff is there? I suppose we only need to worry about things which are variable, but guaranteed to be the same until the next wimp-poll. Communication between tasks might be another problem area, but I don't know how that works so can't say. |
| |
[ Log in to reply ] |
| |
|
ninjah |
Message #55989, posted by ninj at 16:10, 22/6/2004, in reply to message #55977 |
Member
Posts: 288
|
I think it's a little harsh to describe wimp2 as a cludge - it's a complete rewrite of the WIMP module, which is what I'd expect an OS developer to do, if they decided to implement PMT in the desktop layer.
The SpamStamp issue could be relatively easily resolved by rewriting the mail transport, I think. But that was just an illustration that there is probably a lot of software out there that depends on the way cooperative MT works.
Your point that wimp2 is opt-in is valid, but I'm saying that an OS change would also need to be opt-in. Maintaining a list of programs known to work and patching them via something like Wimp2Patch is too much of a bodge for an OS, so you'd need to write for everyone to rewrite their programs to use the new system.
As for the consistency of the environment between polls, currently nothing can change (since the machine is single-tasking between wimp polls) except for little things that tend to get interrupt driven (like the sound system). With PMT you will (probably) get certain guarantees, such as a guarantee that the memory map won't shift under your feet and maybe that the screen mode won't change. However files, modules, and sprites could all disappear or change. When changing screen mode the system could aguably wait until all apps reach their wimp_poll then freeze them, so they aren't in the middle of a redraw when the mode changes, and can be immediately told to redraw in the new screen mode. However, you can't freeze all the apps just to delete a file - it'd be extremely inefficient. What's probably needed there is a way to lock modules, sprites etc. so they can't be deleted when in use. So you can see how this soon adds up to major changes. Not 'virtually impossible', but maybe 'enormously difficult' for a company like Castle. |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #55998, posted by Loris at 17:07, 22/6/2004, in reply to message #55989 |
Ha ha, me mine, mwahahahaha
Posts: 1025
|
I've never used Wimp2; perhaps my perception of it was adversely affected by other peoples evaluation of it at the time.
The SpamStamp issue could be relatively easily resolved by rewriting the mail transport, I think. But that was just an illustration that there is probably a lot of software out there that depends on the way cooperative MT works. Hopefully there isn't too much which relies on freezing of the computer! But yes, with the points you've raised there will be a fair amount.
...[with a change from cooperative to preemptive MT] files, modules, and sprites could all disappear or change.
...
However, you can't freeze all the apps just to delete a file - it'd be extremely inefficient. So basically you an opt-in system would be the path of least resistance.
If we allowed all legacy apps to cooperatively multi-task in a current API, then new tasks would be able to take portions of one meta-task. Perhaps this is how Wimp2 works.
The thing about apps is that they are so varied.
Some would be happy with just a little time every second or so, some need a little but often, while others want all the processing they can get. In the interests of efficiency programs should retain some degree of cooperativity, being able to sleep for a certain time if they don't need anything, or ask for longer (but perhaps less frequent) slots.
The problem with things moving or disappearing is a serious one for pre-emptive systems. Locking works, but it not perfect - I'm always being told that a file is locked on windows, and it pisses me off. Perhaps more than the 'bane' of cooperativity of waiting for a file to load.
Perhaps there could be an intervening layer for all these sorts of things (basically data).
If a program wants data, it basically requests it, and the actual business of looking after it is handled by the OS. If another program wants to modify it then the program gets informed of the change.
Agreed, this would be basically a whole new operating system, but if a group of geeks, accountants and schoolteachers made one, Castle should be able to.  |
| |
[ Log in to reply ] |
| |
|
ninjah |
Message #56001, posted by ninj at 17:47, 22/6/2004, in reply to message #55998 |
Member
Posts: 288
|
I don't think an opt-in system will work actually, thinking about it. In fact, wimp2 may have proved that. Since you need to freeze the environment while CMT apps run, the responsiveness of a PMT OS can be no better than a CMT OS. That's how wimp2 worked, I think - it appears as a single CMT app which, when it gets run, preemptively runs all apps under its control for a little while, before passing control back to the WIMP. I assume that's what you mean by a meta-task. That's effectively the same as stopping PMT every so often, polling each CMT app once then returning.
If there's a majority of CMT tasks, most of the time PMT isn't running, and you don't get the benefits of a PMT system.
I suppose the question is: will we need a majority of CMT tasks. It depends on whether wimp2's issues were mainly down to the inherent problems with PMT'ing CMT tasks, or whether it was just buggy.
As to your comments about different apps requiring different timeslots, to a degree this can continue to be handled in a similar way to Wimp_PollIdle's mask. It details which types of events an app is interested in, and the app only gets called when that event happens (e.g. one of it's windows is scrolled). You can go further, and apps can inform the system how much time they need (and possibly change this every time they get called). The UNIX 'nice' command lets you set scheduling priority. Even further, a real-time OS lets you set quality of service (QoS) so that if an app really needs so much time so often, the OS *must* let it run that often and for that long.
That's starting to ring an odd bell actually. Did Acorn start to write an RTOS a little while before the workstation division was canned? I might be temped to classify that work along side PB's fabled 3xVIDC graphics system, but it's an interesting aside. I've probably got some docs on it if I knew where my Clan Acorn stuff had gone. I can't remember if it was intended to be compatible with RISC OS as we know it though. |
| |
[ Log in to reply ] |
| |
|
Mark Scholes |
Message #56039, posted by mavhc at 08:05, 23/6/2004, in reply to message #56001 |
Member
Posts: 660
|
How does MacOS 9 running on MacOS X work? I assume OS 9 (the CMT OS) is running as a single task in OS X (the PMT OS) How does it handle file locking etc?
Also it is MacOS 9 running, there's no patching. |
| |
[ Log in to reply ] |
| |
|
Adrian Lees |
Message #56044, posted by adrianl at 08:50, 23/6/2004, in reply to message #56039 |
Member
Posts: 1637
|
What kills the responsiveness of RO is not so much heavy CPU activity (how many RO programs do you know that do heavy number crunching?) but waiting for I/O transfers to complete. From the perspective of a desktop user, the greatest gains would come from being able to still use the desktop whilst one app is loading a large file, or the CD is spinning up, or your web browser is waiting for data to arrive etc.
This may not be enough to promote RO for embedded (RTOS?) systems, but it would be a great improvement for desktop use and would suffer fewer race hazards/reliability problems than general preemption after n ms, no matter what code is currently executing.
ie. task-switch only on Wimp_Poll or an I/O transfer (at well-defined points within the filing systems).
Note that this is still a large amount of work, because task-switching is currently in the Wimp, when it ought to be in the kernel, and because the kernel itself really has (almost) no concept of multiple applications.
Wimp2 is a patch that could never hope to be very reliable, nor to give the full gains possible from preemption. To be done properly, the task-switching needs to be at a lower-level (within, or even beneath the existing RO kernel) and major changes are required to Kernel, WindowManager, FileSwitch and all the filing systems (FileCore, ADFS, DOSFS, CDFS..). TBH it'd probably be easier to reimplement in C at the same time as making them reentrant.
Just my thoughts, though I've thought about this a lot. I even have some code from the years when it seemed there was no hope of anyone else developing RISC OS further. Some of it later found a home in Aemulor which has to implement a fair chunk of the RO kernel (apps, DAs, modules, CLI).
[Edited by adrianl at 09:53, 23/6/2004] |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #56055, posted by Loris at 10:43, 23/6/2004, in reply to message #56044 |
Ha ha, me mine, mwahahahaha
Posts: 1025
|
What kills the responsiveness of RO is not so much heavy CPU activity (how many RO programs do you know that do heavy number crunching?) A few actually. Printing on eg. Ovation Pro does poll, but not enough to actually do anything other than abandon prints where something goes wrong. Image processing is the other main one. ChangeFSI, for instance.
These arn't necessarily productivity inhibitors, since often you'll be waiting for the processing to finish anyway.
...but waiting for I/O transfers to complete. From the perspective of a desktop user, the greatest gains would come from being able to still use the desktop whilst one app is loading a large file, or the CD is spinning up, or your web browser is waiting for data to arrive etc. Definitely.
This may not be enough to promote RO for embedded (RTOS?) systems, but it would be a great improvement for desktop use and would suffer fewer race hazards/reliability problems than general preemption after n ms, no matter what code is currently executing. So basically you could get away with only 'locking' files as they were being accessed.. although actually you'd just avoid returning any data from a file (or whether it existed) until the previous access had completed.
Note that this is still a large amount of work, ... Oh well, nice idea anyway.
...
That's starting to ring an odd bell actually. Did Acorn start to write an RTOS a little while before the workstation division was canned? I remember reading about Acorn making/designing a 'revolutionary' new system where apps could request certain amounts of processing. But nothing came of it. |
| |
[ Log in to reply ] |
| |
|
Adrian Lees |
Message #56057, posted by adrianl at 11:44, 23/6/2004, in reply to message #56055 |
Member
Posts: 1637
|
A few actually. Printing on eg. Ovation Pro does poll, but not enough to actually do anything other than abandon prints where something goes wrong. Image processing is the other main one. ChangeFSI, for instance. OK. Such code could be updated to yield the processor, once preemption was possible (just inserted an OS_Yield SWI call is a lot easier than Wimp_Poll which has to handle the returned messages).
I'm slightly wary of full preemption for reasons other than the issue of race hazards, and that is that it can make the system less predictable in its responsiveness.
One of the nice features of RISC OS is that things always take the same amount of time, whereas random delays can occur at any time with a fully preemptive, virtual memory OS. (Not helped by the fact that once VM, preemption & threading are present, programmers will (ab)use them heavily.)
We don't want to 'throw out the baby with the bathwater' - I'd certainly vote in favour of 'elective VM' (only on certain DAs as requested by certain apps, eg. a database that needs to hold large indexes in memory... and the app can be written to take account of the fact that any memory access to that area could take many seconds)
Perhaps there's a better approach than full PMT vs full CMT.... perhaps what I'm suggesting, and maybe allow preemption during heavy processing, but only if the system stack is empty (a la TaskWindow's behaviour currently).
BTW, when an I/O transfer blocks, the kernel, FileSwitch & FS /are/ threaded which is why you can't task switch currently. (Hence Wimp2 can break up large transfers, but can't avoid stalling completely, because the small fragments can also stall - often the first fragment, o.c.).
So basically you could get away with only 'locking' files as they were being accessed.. No, this has nothing to do with files really. Some file locking is already provided by RO ("File is already open" , but the potential problems of an app making assumptions about a shared resource (eg. 'read file size, allocate buffer, load file into buffer' only to discover that the file is now larger and overflows the buffer) are completely separate, much less serious & often completely ignored by the OS! In practice they don't often occur.
The real problem with preempting any RO app at /any/ time whatsoever, is that part-way through executing module X, a new app gains control and also enters module X. The code in X can't handle two apps callling it 'at the same time' (it's akin to now running the entire system on n processors) and it /will/ fail, but only sometimes and it'll be very hard to reproduce the problem because it depends upon exactly when the switch occurs.
Certain parts of the system must be made to handle preemption (I'd suggest Kernel, WindowManager & Device I/O including Graphics Driver). This will be easier to achieve if preemption occurs only at well-defined points; they need only be altered with preemption in mind, rather than written to be completely reentrant (with all the race hazards, semaphores/mutexes & potential deadlocks that that implies).
Note that this is still a large amount of work, ... Oh well, nice idea anyway.
Less work than full PMT. A lot more work than doing nothing.
I remember reading about Acorn making/designing a 'revolutionary' new system where apps could request certain amounts of processing. But nothing came of it. It was called Galileo and it did indeed sound very interesting. I too have wondered what became of it; how much, if anything, was actually developed. |
| |
[ Log in to reply ] |
| |
|
ninjah |
Message #56076, posted by ninj at 16:00, 23/6/2004, in reply to message #56057 |
Member
Posts: 288
|
Ah, yes. Galileo. Like I said earlier, I'm tempted to put it in the same category as other pronouncements made towards the end of the Workstation division. Thinking about it, Acorn probably wrote far more failed (or prematurely abandoned) OSes than successful ones. Not only was there RiscIx and Arthur, wasn't there another Posix-type OS? And what did the ABC range run?
Anyway, back on topic. Surely the issue of reentrancy could be resolved by not preempting the current app when it's in supervisor or IRQ mode? How much time does the processor actually spend in user mode, as compared to the other modes?
The idea of being able to multitask IO is more interesting. I'd blindly assumed that it was some core limitation of the OS which meant that tasks couldn't multitask through IO, but in fact it's far more obvious. Since RISC OS's CMT doesn't have the opportunity to poll away when a program makes an IO call, it must block until that IO resource returns. Hmm, that would be a pretty major structural change to let the wimp poll if it spots an IO call, seeing as IO calls are usually nothing to do with the wimp - but it'd be a step in the right direction of moving MT to a lower level. |
| |
[ Log in to reply ] |
| |
|
Acorn Arcade forums: Programming: Pre-emptive Multi-tasking |
