Multitasking, MMUs, and Microkernels(split from BSOD thread)

[linguofreak]

Responding to Schol-R-Lea in this thread:

Well, keep in mind that this applied to almost every small computer - including several minis - prior to 1990 or so, and still applies to many modern microcontrollers as well - a number of RTOSes don't assume the presence of an MMU, and some don't use it even when present. I know that the original QNX could run on an 8088 with no MMU, for example. I imagine some of the embedded developers here could say more on this.

Strictly speaking, you don't need an MMU to have preemptive multitasking, just a user/kernel mode distinction and somewhere to put the timer interrupt vector, the timer ISR, and the scheduler that user mode can't touch (and you might as well put the rest of the kernel there while you're at it). This could be as simple as a "User address limit" register that sets the highest address accessible in user mode, and that only kernel mode can write to, no address translation is necessary.

Oh, and the first several versions of UNIX ran on PDP-7 and PDP-11 systems with no MMU, as well, though they were quick to adopt it when the KS-11 add-on came around. The lack of an MMU was one of the 'vital parts' from Multics whose absence led to the operating system's punny name, If I am not mistaken.

ISTR reading that the PDP-11/20 had a user/kernel distinction even before it had an MMU, but I may be misremembering. Stories I've heard out of Bell Labs about applications being able to bring down the system early on would indicate that I probably am.

EDIT: Any idea what the difference between the KS-11 and the KT-11 was? In other sources I've heard the MMU for the 11/20 called the KT-11, but Dennis Ritchie's recollections call it the KS-11. I think I've heard that Bell Labs got a fairly early MMU, was the KS the beta version of the KT?

I'm also uncertain about the M68k, I thought I'd heard something about it to the effect that it had separate user and kernel modes before it had an MMU, but I've not heard of the Mac or Amiga using this to prevent userspace programs from scribbling on the kernel (OTOH, I know that the M68k had issues with not preserving enough information to allow a program to be restarted after an exception, which complicated the addition of an MMU, but most cases of a user program trying to scribble on the kernel are going to result in program termination anyway).

Indeed, one of the touted advantages of the microkernel design when people like Tannenbaum started really promoting it was that it "didn't need" hardware memory protection, since it was vastly better at both process isolation (due to using message passing for IPC rather than shared memory sections and manually-managed semaphores) and system stability (since a hung driver could be shut down and restarted without affecting the kernel itself).

But there's nothing to prevent a driver from hanging by doing:

Code: Select all

cli
hlt

In which case the kernel can't restart the driver because execution can't restart until a reset occurs (unless the machine has a watchdog timer hooked to an NMI).

or

Code: Select all

condition=true;
index=0;
while(condition=true)      //Oops! Assignment instead of comparison!
{
    array[index] = func1(param1);
    condition = func2(param2);
    index++;   //Forgot to check that our index doesn't run off the end of the array
}

In which case the driver will hose all of memory (unless it hits an address with nothing attached and gets a bus error, but depending on the exact circumstances, it could easily overwrite the entire kernel with garbage before that happens, or the specific hardware involved may just ignore writes to non-existent memory rather than erroring out).

The first can be prevented with a user/kernel distinction that prevents the execution of privileged instructions, the second can be prevented with a user/kernel distinction and a user address limit register.

You're still vulnerable to a large class of bugs that will clobber the kernel if you don't have at least *some* protection.

My point is that, given that most of the various pre-emptive multitasking systems ever written were on systems with no MMU, saying that they weren't pre-emptive multitasking systems at all is a hard sell.

I'm still going to try to sell it that

My argument is that preemptive multitasking is impossible without an MMU (or at least a user address limit register like I described above). Any "preemptive" multitasking OS on unprotected hardware is in fact doing cooperative multitasking. Now, the cooperation required is passive (don't mess with the kernel), rather than active (hand control back regularly, and while you're at it, don't mess with the kernel), and it makes the task of making the system preemptive easier (you just have to add code to handle the protection hardware, which might be fairly trivial for a user address limit scheme), but it's still cooperation: a program that bugs out can do something uncooperative in its death throes and kill the system, and a program that decides to be actively uncooperative can walk in confidently with a clipboard, and say to the receptionist: "Hi, I'm the new scheduler, could you direct me to the timer interrupt? OK. OK. Down the hallway to the right, left at the hallway with the big sign: 'Interrupt vector table --- Authorized drivers only', then third door on the left? Did I get that right? Thanks!". A few hundred microseconds later, the system is under new management and the old scheduler's family files a police report as he hasn't been seen in three nanodays. Meanwhie, an unidentified core dump is found in a back alley with a gunshot wound to the head.

[iansjack]

I'm also uncertain about the M68k, I thought I'd heard something about it to the effect that it had separate user and kernel mode...

It did indeed (although it was called "supervisor" mode), but it was less than perfect. If featured separate user and supervisor stacks and, obviously, restricted instructions. But it didn't feature memory protection. However, apparently you could emulate this by using a pair of 68000s.

As to whether an OS can be called a pre-emptive multitasking one without memory protection, I'd say that it can (indeed, why bother with the "pre-emptive"; if relying upon correct programming any form of multitasking is at risk). It relies on the user/programmer being sensible, but so does - for example - Linux. A user with root access to a machine running Linux can run any program in kernel mode by making it a loadable module. The same is true for most other OSs. So is Linux a pre-emptive multitasking system for normal users but not for the root user? That doesn't make sense.

In any case, security and multitasking are separate concepts and can't be conflated in this way.

[bzt]

Strictly speaking, you don't need an MMU to have preemptive multitasking, just a user/kernel mode distinction

Strictly speaking you don't need user/kernel mode distinction either for preemption. All you need is a timer interrupt, and an ISR which saves the state and restores another task's state on return. That's all. For example there's Minix 1 (see _clock_int and _restart labels) which is a multi-tasking, preemptive system in real-mode without paging or user/kernel distinction.

You're right though that this is extremely fragile as any process can crash the system by modifying the IVT/ISR. It's better if there's a privileged kernel part, not allowing user space to mess with the interrupt handlers.

Cheers,
bzt

[linguofreak]

I'm also uncertain about the M68k, I thought I'd heard something about it to the effect that it had separate user and kernel mode...

It did indeed (although it was called "supervisor" mode), but it was less than perfect. If featured separate user and supervisor stacks and, obviously, restricted instructions. But it didn't feature memory protection. However, apparently you could emulate this by using a pair of 68000s.

The pair of 68k's wasn't to emulate protection. You had an honest-to-goodness, non-emulated external MMU sitting on the bus translating addresses. If you weren't paging to disk and were doing any swap on a whole-process basis (or not swapping at all), so that any page fault was fatal, you only needed the one 68k. As I understand it, the pair of 68k's was necessary because when the bus error signal was raised in the middle of an instruction, the 68k didn't have enough information saved to reconstruct the CPU state at the beginning of the instruction, so a bus error had to be treated as fatal. This was worked around by having two 68k's, one working on a clock that was leading the other in phase, so that the trailing one could be interrupted before it tried to access the faulting address. The trailing CPU was then able to handle the interrupt without losing information, and they were resynchronized when it returned.

As to whether an OS can be called a pre-emptive multitasking one without memory protection, I'd say that it can (indeed, why bother with the "pre-emptive"; if relying upon correct programming any form of multitasking is at risk).

Cooperative multitasking relies on correct programming in every bit of code on the system. So does preemptive-ish multitasking without memory protection. Full preemptive multitasking only relies on the code running in kernel mode being correct.

It relies on the user/programmer being sensible, but so does - for example - Linux. A user with root access to a machine running Linux can run any program in kernel mode by making it a loadable module. The same is true for most other OSs. So is Linux a pre-emptive multitasking system for normal users but not for the root user? That doesn't make sense.

Any code that root is running in user mode still will segfault if it tries to access kernelspace directly, so I wouldn't say so.

And a site with really strict security requirements could compile a custom kernel with CONFIG_MODULES disabled and all required hardware support compiled in. /boot could be on read-only storage, requiring physical access and a reboot to make any changes.

Of course, then there's the Lovecraftian horror that is DOS-kernel Windows:

DOS programs are, in theory, preemptively multitasked, but Win16 programs aren't: they all reside in one DOS process along with most of Windows, so they can hose that portion of the system by refusing to yield. And DOS processes are mostly, but not entirely, isolated from each other and the system: the mapping for conventional memory up to the point that Windows was loaded is the same in every process, so that all your DOS device drivers are present, but, AFAICT, this whole area is also *user writable* in every process, so that any process can hose it and bring down the whole system. Meanwhile, in Win9x, if I've interpreted what I've read correctly, the Win32 environment was basically implemented as a DPMI client, with each Win32 task being run as a DOS process. Meanwhile, while Win32 programs themselves ran in separate processes, the actual system UI seems to have remained a Win16 component.

[iansjack]

And a site with really strict security requirements could compile a custom kernel with CONFIG_MODULES disabled and all required hardware support compiled in. /boot could be on read-only storage, requiring physical access and a reboot to make any changes.

Yes, you could do that; I would guess that most Linux setups are not configured that way. But I think that anyone except the most anal pedant would still consider Linux to be a pre-emptive multitasking OS. The same applies to other UNIX-like OSs.

[bzt]

Cooperative multitasking relies on correct programming in every bit of code on the system. So does preemptive-ish multitasking without memory protection. Full preemptive multitasking only relies on the code running in kernel mode being correct.

This is true, but...

In any case, security and multitasking are separate concepts and can't be conflated in this way.

...is correct, preemption and security are two separate concepts.

On one side we have multitasking:
- cooperative: the application must willingly give up CPU time by calling yield
- preemptive: the application is interrupted whether it wants it or not

On the other side is security, how this is actually implemented (can the application access the kernel memory?). But this is irrelevant from the multitasking's point of view. A misbehaving (segfaulting etc.) application might be preempted too, that's an implementation detail. And without kernel separation both cooperative and preemptive multitasking can be messed up. With proper protection, the one and only risk to cooperative is not calling yield.

Cheers,
bzt

[Korona]

What's the value of this "can an OS be preemptive without protection" discussion? That's just arguing about the semantics of a word and not really about any technical matter.

[iansjack]

In a precise technology such as computer science the meaning of words is very important. As ever, reading of topics that you think uninteresting is not compulsory.

[Korona]

The meaning of words is local in the literature: each book / article / paper / website will have its own, often slightly incompatible definition. An important skill in computer science (or any other science, for that matter) is the ability to be able to juggle these definitions as needed and to extract relevant details from context. Natural language is necessarily imprecise (even scientific texts) - we willingly omit details to make texts easier to understand. If you want an entirely precise language, look at something like Coq. Yet, nobody writes articles in Coq.

As ever, there is also no need to lecture anyone about computer science methodology.

[linguofreak]

Cooperative multitasking relies on correct programming in every bit of code on the system. So does preemptive-ish multitasking without memory protection. Full preemptive multitasking only relies on the code running in kernel mode being correct.

This is true, but...

In any case, security and multitasking are separate concepts and can't be conflated in this way.

...is correct, preemption and security are two separate concepts.

On one side we have multitasking:
- cooperative: the application must willingly give up CPU time by calling yield
- preemptive: the application is interrupted whether it wants it or not

On the other side is security, how this is actually implemented (can the application access the kernel memory?). But this is irrelevant from the multitasking's point of view. A misbehaving (segfaulting etc.) application might be preempted too, that's an implementation detail. And without kernel separation both cooperative and preemptive multitasking can be messed up. With proper protection, the one and only risk to cooperative is not calling yield.

Let's put my position this way: multitasking and security are separate concepts, but reasonably good security is a prerequisite to preemptive multitasking. On a preemptive-ish system with no memory protection whatsoever, a program that wants to can make the system a cooperative system for its purposes: it can hook the timer interrupt and only pass it on to the kernel if it currently has no work to do. Any application can, at will, delete the "or not" part of "if it wants to or not". Now, you can gain many of the benefits of preemption without security, but you can't be sure of having those benefits.

On the flip side, without memory protection, a cooperative system could be turned into a preemptive-ish system by a rogue application as well: hook the timer interrupt and call the scheduler when it fires.

[eekee]

My argument is that preemptive multitasking is impossible without an MMU (or at least a user address limit register like I described above). Any "preemptive" multitasking OS on unprotected hardware is in fact doing cooperative multitasking.

Korona makes a point that definitions vary, but this is "varying" definitions so far as to render them worthless. The term "cooperative multitasking" is useful to describe the multitasking scheme where the running task must yield in order for other tasks to run. I'm 90% sure some successful systems have been built around this, and I'm not even counting Windows 3. Further, *every* system requires cooperation at some level for smooth running. From windowing system features to realtime facilities -- even if the latter are only present for media playback -- to WebGL exploits there is a broad range of means by which one uncooperative program can foul up the system on even the most modern and widespread operating systems.

Then there's the literal definition of "preemptive multitasking", meaning tasks are preempted -- interrupted -- in order to switch control. The presence or absence of an MMU has nothing at all to do with whether or not tasks are literally preempted, so it cannot be right to point to systems without an MMU and say "That's not preemptive multitasking."

I'm sorry, lingofreak, but as far as I'm concerned, you're just creating confusion because you want one particular term to be extra-special. I've done this once or twice, I learned not to.

[Korona]

I'm sorry, lingofreak, but as far as I'm concerned, you're just creating confusion because you want one particular term to be extra-special. I've done this once or twice, I learned not to.

That is straight to the point. Does it help our communication (i.e., the clarity of our language) to exclude non-protected systems from the set of preemptive systems? Does it make statements about kernels easier to grasp? I don't think so.

[Gigasoft]

DOS programs are, in theory, preemptively multitasked, but Win16 programs aren't: they all reside in one DOS process along with most of Windows, so they can hose that portion of the system by refusing to yield. And DOS processes are mostly, but not entirely, isolated from each other and the system: the mapping for conventional memory up to the point that Windows was loaded is the same in every process, so that all your DOS device drivers are present, but, AFAICT, this whole area is also *user writable* in every process, so that any process can hose it and bring down the whole system. Meanwhile, in Win9x, if I've interpreted what I've read correctly, the Win32 environment was basically implemented as a DPMI client, with each Win32 task being run as a DOS process. Meanwhile, while Win32 programs themselves ran in separate processes, the actual system UI seems to have remained a Win16 component.

Both Windows 9x and the versions leading up to it were implemented as a DPMI client. In Windows 9x there were actually two levels of processes: each DOS session was considered a separate VM, with all of Windows residing in a single VM like before. Then, each 32-bit task was a process within that single VM, and all of the 16-bit tasks resided in the "System" process, if I remember correctly. There was a single instance of KRNL386, GDI and USER which was mapped into every process, along with their 32-bit counterparts, so that any process could call them. Of course, any process could then also freely overwrite global system variables, in fact even things such as the IDT and page table entries.

[linguofreak]

DOS programs are, in theory, preemptively multitasked, but Win16 programs aren't: they all reside in one DOS process along with most of Windows, so they can hose that portion of the system by refusing to yield. And DOS processes are mostly, but not entirely, isolated from each other and the system: the mapping for conventional memory up to the point that Windows was loaded is the same in every process, so that all your DOS device drivers are present, but, AFAICT, this whole area is also *user writable* in every process, so that any process can hose it and bring down the whole system. Meanwhile, in Win9x, if I've interpreted what I've read correctly, the Win32 environment was basically implemented as a DPMI client, with each Win32 task being run as a DOS process. Meanwhile, while Win32 programs themselves ran in separate processes, the actual system UI seems to have remained a Win16 component.

Both Windows 9x and the versions leading up to it were implemented as a DPMI client. In Windows 9x there were actually two levels of processes: each DOS session was considered a separate VM, with all of Windows residing in a single VM like before. Then, each 32-bit task was a process within that single VM, and all of the 16-bit tasks resided in the "System" process, if I remember correctly. There was a single instance of KRNL386, GDI and USER which was mapped into every process, along with their 32-bit counterparts, so that any process could call them.

Wouldn't it be unnecessary to map a copy of KRNL/GDI/USR into every process if every Win32 task was in the System VM? You'd only need to map a copy into every process if Win32 task each resided in a separate process.

Looking at https://en.wikipedia.org/wiki/Win32s , it would seem that your description, except for the last sentence, pertained to Win32s on Windows 3, and then the last sentence applies to full Win32 on Windows 9x, where each Win32 task was mapped into its own address space.

[Gigasoft]

You are mixing up VMs, tasks and address spaces. The way it worked was that drivers would register to be notified of thread switches, and the driver that managed a thread (in this case, VWIN32) was responsible for switching to the correct address space. For Windows threads, this would be the address space belonging to the associated process. The 80000000h to 0bffffffffh range was identical in every Windows process, and contained system DLLs, and every Win16 program in fact resided here too.

VMs were for hardware virtualization. Additional VMs were only created for DOS programs, since Windows programs were supposed to only access hardware through the Windows APIs. So if Windows programs tried to access I/O ports directly, and the driver allowed it, they would get in the way of each other, and moreover, the device would remain in use by the System VM even after the process exited.