Multi-tasking without MMU: How?

[technix]

Those STM32F7 chips looks cool: they supports large DRAM blocks and have a QSPI controller with XIP so I can have 128MB RAM and 64MB ROM easily. Now I want to multitask on this. Oh it doesn't have a MMU...

Now how can I multitask without a MMU?

[bzt]

Now how can I multitask without a MMU?

Simple, multitask and MMU are unrelated things.

Imagine that you have two processes A and B. A is loaded at address 0x8000 while B is loaded at 0xF000. When A yields (or a timer interrupt happens), then you save the current instruction pointer (along with other registers) for A. Then you load the instruction pointer (and other registers) for B. The execution continues on B.

This is similar with MMU, the only difference is, that you also save and restore the memory mappings. This means both A and B can be loaded at 0x8000, but that's all. Without MMU, they share the same address space, so their addresses must be different. This is irrelevant from multitasking's point of view, only the number of things to be saved and restored changes.

Cheers,
bzt

[nullplan]

Yep, pretty much what bzt said. Note that running without MMU requires you to use an ABI that provides for position independence (you can just use plain ELF with only PIEs allowed, or run ELF FDPIC), since only one program can ever be in one place in physical memory at a time. And without MMU there is also no memory protection, so you kind of have to hope that nothing steps on other programs' (or even the kernel's) address spaces.

[Solar]

Related: Amiga's LibraryBase for a description of how AmigaOS handled exactly this setup.

[Schol-R-LEA]

One thing I will recommend is considering a Microkernel design¹ for this use. Why? Because it is exactly the scenario for which micro-kernels were originally developed - the primary goal of a micro is not to keep the kernel small, but to provide a layer of separation between the drivers and the kernel proper, so the lack of memory protection isn't as severe a problem.

(I am aware that memory mapping and memory protection are separate issues, but in most systems the two functions are handled by the MMU, and are tightly coupled in their operations. This has been the case for the ARM designs I have studied in the past, IIRC.)

I realize that a micro-kernel may not suit your intended design, but I would still recommend taking a look at the model and see if anything about it is useful to you.

Now, I don't know the CPU in question, but I had the impression that all ARM designs have, at the very least, a high-low separation for the kernel. I am not certain how this is done without an MMU, other than possibly having two separate memory spaces, with a portion of the memory wired directly to the region about 2GB. I am pretty sure this isn't the case, so I can only guess I am mistaken about ARM always having a Supervisor mode separation.

Given that, I am assuming that in this instance, the microcontroller is always running in the equivalent of Supervisor mode, across the whole memory space. I'd have to read up on the specific model to say more.


Footnote
A key part of this - indeed, IMAO the defining property of a micro-kernel - is the replacement of specific system calls with a small set of message-passing system calls (usually just send_msg() and receive_msg() for synchronous messages, and/or mail_msg() and check_mail() for asynchronous) with all other 'system calls' being library wrappers around pre-set messages. In a 'pure' micro, these are the only mechanism for both communicating with the kernel and synchronizing between processes.

This message passing - which at once both narrows the OS interface while at the same time replacing ad-hoc system calls with a general mechanism - is the real means by which the kernel is protected from hanging, and how the risk of addressing errors (as opposed to malicious scribbling over system memory, which there isn't much one can do to prevent without memory protection) is mitigated.

My own opinion is that any system with more systems calls than those four isn't a 'pure' microkernel. However, very few if any modern micro-kernels fit this definition (purity not necessarily being desirable).

[bloodline]

Those STM32F7 chips looks cool: they supports large DRAM blocks and have a QSPI controller with XIP so I can have 128MB RAM and 64MB ROM easily. Now I want to multitask on this. Oh it doesn't have a MMU...

Now how can I multitask without a MMU?

My own kernel project is exactly this, my previous operating system work was on small ARM microcontrollers, without MMU.

The MMU is irrelevant for multitasking; The key is having separate user and supervisor stacks, and a regular (timer) interrupt to handle the task switch. When the system enters an interrupted state, the current running task's CPU state is pushed on it's own stack, then the CPU enters supervisor mode with it's own stack, now it is simple enough to swap the current user stack for the stack of another task and then return from the interrupt. Now the state of the other task will be loaded into the CPU and it will run, until the next task switching interrupt, where the process repeats.

Very importantly you need a more advanced memory allocation function than a simple heap allocator, but nothing that a nice doubly linked list can't provide.

[Solar]

One thing I will recommend is considering a Microkernel design¹ for this use. Why? Because it is exactly the scenario for which micro-kernels were originally developed - the primary goal of a micro is not to keep the kernel small, but to provide a layer of separation between the drivers and the kernel proper, so the lack of memory protection isn't as severe a problem.

Also, the primary drawback of a microkernel -- high cost of frequent context switches -- is a non-issue if you don't have a context to switch and IPC boils down to passing a pointer around.

[nexos]

Also, the primary drawback of a microkernel -- high cost of frequent context switches -- is a non-issue if you don't have a context to switch and IPC boils down to passing a pointer around.

You still need to context switch when messaging, even without an MMU. MMU or no MMU only effects messaging in how data is passed. You just pass a pointer. Then you would context switch to the thread you passed a message. Note that the most expensive part of a context switch, switching address spaces, no longer happens without an MMU. On x86_64, you make address space switches a lot faster with PCID, as the TLB won't be invalidated.

[Solar]

That is what I meant. Whatever task switching you do, it's just the modification of a couple of values / registers. Something that's done in a few cycles. Nothing remotely as involved as switching address space and the TLB going cold.

[bloodline]

One thing I will recommend is considering a Microkernel design¹ for this use. Why? Because it is exactly the scenario for which micro-kernels were originally developed - the primary goal of a micro is not to keep the kernel small, but to provide a layer of separation between the drivers and the kernel proper, so the lack of memory protection isn't as severe a problem.

Also, the primary drawback of a microkernel -- high cost of frequent context switches -- is a non-issue if you don't have a context to switch and IPC boils down to passing a pointer around.

I’m glad we have AmigaOS to demonstrate how effective (And dangerous) this can be
I was always fascinated by Microsoft’s Managed code operating system experiments following this model.

Also, the primary drawback of a microkernel -- high cost of frequent context switches -- is a non-issue if you don't have a context to switch and IPC boils down to passing a pointer around.

You still need to context switch when messaging, even without an MMU. MMU or no MMU only effects messaging in how data is passed. You just pass a pointer. Then you would context switch to the thread you passed a message. Note that the most expensive part of a context switch, switching address spaces, no longer happens without an MMU. On x86_64, you make address space switches a lot faster with PCID, as the TLB won't be invalidated.

Solar was referring to memory context, which doesn’t need to be swapped when task switching in single address space Operating Systems!

What is PCID?

[Solar]

I’m glad we have AmigaOS to demonstrate how effective (And dangerous) this can be

Well, I don't know about "dangerous".

The effect on the AmigaOS software scene was that developers took extra care to properly debug their appications against spurious memory access. Using tools like Valgrind and/or eFence on your projects before release was very common. Because a misbehaved program could easily crash your system, most people took pains not to be "that program" instead on relying on system security to cover for lazy programming. The ones who didn't found their tools and utilities gathering a bad rep in very short order...

So if you didn't run just about everything you found on the 'net, but ran tools that had a good track record, your user experience (not only) with regards to stability easily matched (and, IMHO, exceeded) that of comparable Windows / Linux systems of the time, and quite some time after.

And no-one was under the illusion that your system would be "secure". Today, many users assume that the OS / system will "protect" them even against malicious programs, which is genuinely untrue. I'll quote from the KeePass security FAQ:

"If a bad guy can persuade you to run his program on your computer, it's not your computer anymore".

[bloodline]

I’m glad we have AmigaOS to demonstrate how effective (And dangerous) this can be

Well, I don't know about "dangerous".

The effect on the AmigaOS software scene was that developers took extra care to properly debug their appications against spurious memory access. Using tools like Valgrind and/or eFence on your projects before release was very common. Because a misbehaved program could easily crash your system, most people took pains not to be "that program" instead on relying on system security to cover for lazy programming. The ones who didn't found their tools and utilities gathering a bad rep in very short order...

So if you didn't run just about everything you found on the 'net, but ran tools that had a good track record, your user experience (not only) with regards to stability easily matched (and, IMHO, exceeded) that of comparable Windows / Linux systems of the time, and quite some time after.

And no-one was under the illusion that your system would be "secure". Today, many users assume that the OS / system will "protect" them even against malicious programs, which is genuinely untrue. I'll quote from the KeePass security FAQ:

"If a bad guy can persuade you to run his program on your computer, it's not your computer anymore".

You can probably tell from my Avatar, that I’m not going to say anything bad about AmigaOS, I was just being realistic. By dangerous, I was really referring to the potential for data loss.

But I fundamentally agree that an Operating System which is physically secured by the user doesn’t need the OS to “nanny” the user. This is partly why I am adopting a “no memory protection" model with my current OS project. Actually I’m planning a hybrid approach, I’ll post more when I have a better working example.

[bzt]

Hi,

I've found this asm on one of my archives. It was a participant on a 512-byte contest for fasm. It is a very minimal OS with two tasks and implements multitasking without MMU.
Maybe it's going to be useful to you to understand the concept.

This is partly why I am adopting a “no memory protection" model with my current OS project.

Maybe newcomers not aware, but Microsoft had a research operating system just like that. It did not use any hardware protection, instead relied on "software isolated processes" and strong type checks in the compiler.

Cheers,
bzt

[nexos]

What is PCID?

PCID basically allows multiple PML4s (the equivalent of a page directory in x86_64) to be in the TLB. They are tagged with a tag called a page context identifier that is put it the lower 12 bits of the CR3 register. This means that the TLB isn't invalidated. I believe use of it mitigates Spectre. You can read about it the Intel SDM.

[bloodline]

What is PCID?

PCID basically allows multiple PML4s (the equivalent of a page directory in x86_64) to be in the PML4. They are tagged with a tag called a page context identifier that is put it the lower 12 bits of the CR3 registers. This means that the TLB isn't invalidated. I believe use of it mitigates Spectre. You can read about it the Intel SDM.

This sounds interesting! I’m going to have some fun bed time reading, many thanks for telling me about it!