a micro micro kernel

[earlz]

Ok.. I have been thinking about this extremely small micro kernel.. I mean so small, that it's basically just a framework and the modules make the real kernel...

Goals:
* Able to be scaled down to systems in the 10-100kb RAM range
* Able to be ported(with ease, though not necessarily full featured) to about any arch and system
* Being able to change everything about the kernel except the message passing system(preferably even while running the kernel)
* Nearly everything is optional in the kernel
* Be SMP capable with the proper modules

Ok.. my basic plan: This is how it will go from bootup. (note: Manager refers to Message passing and module management)
1. Gets into kmain from basic execution environment(ie, pmode/long mode/whatever) from bootloader/boilerplate.
2. Kernel initialization module is loaded and executed. This should setup things up for normal operation, such as a GDT; this is not necessary for all archs. Sets a global variable for a function callback in order to initialize this later as a module
3. Loads the manager and sets memory allocated to basic placement malloc
4. Loads the memory management module (which is optional)
5. Loads the task management module
6. Loads the file manager
.... (more modules as specified at compile time)

The message passing will allow communication across modules. All modules will be loaded at ring 0, though there is nothing stopping one to load modules at ring 3 and providing a system call interface to get to the ring 0 manager.

Before disk and filesystem drivers are loaded. Modules will be loaded by a very simple ramdisk, where a fixed loaded address will refer to a module entry point, and the entry point will be passed a struct of function pointers for communicating with the Manager...

Does anyone have criticisms of this or flaws in design or ideas for this?

[NickJohnson]

I'm not sure why you're using a microkernel design here, unless all you care about is the size of the kernel, not the whole system. If you need something to fit in 100KB of RAM, you're not going to be able to do anything fancy like that without a lot more effort. If you want that, MINIX 1.0 already runs on an 8088.

[earlz]

I'm not sure why you're using a microkernel design here, unless all you care about is the size of the kernel, not the whole system. If you need something to fit in 100KB of RAM, you're not going to be able to do anything fancy like that without a lot more effort. If you want that, MINIX 1.0 already runs on an 8088.

why not? I would like to hear why this method will make my kernel image larger(assuming we have a way to prevent static library duplication)

[cyr1x]

I have a layered design.

• Hardware Abstraction Level
  • Paging
  • Interrupts
• Micro-Kernel
  • Scheduler
  • Context + Addressspace ( there are no threads at this level )
• The Core ( this is the high level layer )
  • Threads ( here the threads can have a name, a pid, ...)
  • High-Level VMM ( file-mapping, swapping )
  • ...

Now the thing is, the "Core" can access the Micro-Kernel, but not vice versa, the Micro-Kernel can access the HAL, but again the HAL cannot access the Micro-Kernel.

So what you probably want, is to cut of the "Core". If you want you could run it as a service or so.

[Brendan]

Hi,

why not? I would like to hear why this method will make my kernel image larger(assuming we have a way to prevent static library duplication)

Separating things means implementing extra interface code between the separate things.

Imagine you've got a text editor that consists of 200 KiB of code to handle the user interface (menus, mouse clicks, etc), 200 KiB of code to handle manipulating the document itself (handling inserting/deleting text, loading/saving files, etc), and 100 KiB of code for handling spell checks. It's implemented as a single binary that costs 500 KiB. You split it into 3 separate binaries; and you end up with one 200 KiB piece for the user interface plus 50 KiB of interface code (to talk to the other parts), and one 200 KiB piece for handling document manipulation plus another 50 KiB of interface code, and one 100 KiB piece for the spell checker with another 50 KiB of interface code; and now you've got a modular system that costs 650 KiB.

If there's only one text editor running then modularity costs you an extra 150 KiB. If there's many text editors running at the same time and they all share the same spell checker module, then in this case splitting it up into modules actually does save you some memory. However, for a kernel that won't happen, and splitting things into modules just costs you more RAM.

For efficiency (including RAM usage and performance), the best option is a "one single binary" monolithic kernel where everything you need (and nothing you don't need) is complied into the same binary. This implies using conditional code to select which pieces are needed (which can also mean that configuring and installing the OS can be a nightmare, but that's a different issue). The "next best" step (for efficiency) is a modular monolithic kernel, which is similar to a "one single binary" monolithic kernel except there's a little more interfacing code (and less room for the compiler to optimize, but potentially less configuration/installation hassles too). In this case modules are linked to the kernel itself when they're loaded, and they can use efficient interfaces (e.g. "call near") rather than slower interfaces (e.g. messaging). Things like micro-kernels and nano-kernels are the opposite - you sacrifice efficiency for other benefits (like isolation, fault tolerance, etc).

This is also the main cause of the "monolithic vs. micro-kernel" debate. Monolithic kernels *are* more efficient, but efficiency isn't the reason people use micro-kernels anyway. For example, is it better to have fast device drivers (that can trash the entire OS when they crash) or is it better to have device drivers that run a little slower (that can't trash anything when they crash)? There's no right answer - it depends on the design goals...

However, IMHO there are some things that never make sense (e.g. shifting the scheduler out of the kernel). In these cases you get the disadvantages (worse efficiency caused by slower interfaces) but you don't get any advantages (you're still screwed if it crashes).

There's also something I'd call a "modular micro-kernel", where the kernel is implemented as separate modules (to allow flexibility without losing as much efficiency). For example, you could have a memory manager module, a scheduler module, a messaging module, etc (where they can all use "call near" to talk to each other instead of using slow messaging); and then implement other things like device drivers, file systems, networking, etc outside the kernel (so that if they crash, the kernel itself is protected/isolated and can keep running).

Goals:
* Able to be scaled down to systems in the 10-100kb RAM range

For something that small you'd need to use monolithic kernel; or perhaps something I like to call a "megalithic kernel" where the applications are built into the kernel too (e.g. a single binary blob that contains *everything*).

* Able to be ported(with ease, though not necessarily full featured) to about any arch and system

For micro-kernels, portability is mostly a joke. All of your boot code won't be portable. All of the CPU feature detection and SMP stuff won't be portable. The code that manipulates page directories, page tables, etc won't be portable. The low level kernel API (e.g. SYSCALL) and low level interrupt and exception handling won't be portable. The task switch code (e.g. to save the CPU's state and load the CPU's state) won't be portable. You might have stuff to handle MTRRs, PATs, ISA DMA, APICs, etc, and none of that will be portable either. Once you remove all the non-portable stuff from a micro-kernel you end up with about 500 lines of "glue" that is portable, plus a lot of crappy abstraction layers that do nothing but add bloat and reduce your ability to optimize...

IMHO a better approach is to write separate non-portable micro-kernels that are highly optimized/tuned to each specific architecture; so that you end up with clean code (that isn't stuffed full of "#ifdef ARCH_IA386; #elseif ARCH_ARM; #elseif ARCH_MIPS" stuff to confuse everyone); and provide the same kernel API for all architectures, and write everything else as portable code if it makes sense (e.g. portable code for a PCI device driver does make sense, but portable code for a "80x86 only" floppy driver doesn't).

* Being able to change everything about the kernel except the message passing system(preferably even while running the kernel)
* Nearly everything is optional in the kernel

IMHO it's hard enough to write some pieces of code (e.g. device drivers) when you do know exactly how memory management, interrupts, scheduling, etc works. If you can't assume anything about the memory management, interrupt handling, scheduler, etc then it'd be almost impossible to write anything.

The interfaces between pieces (e.g. the interface between device drivers and the kernel's memory manager, scheduler, etc) *must* be standardized and written down in some sort of specification, so people can rely on things to behave in specific well defined ways. Different pieces of the kernel may implement this standardized interface in entirely different ways, but if all the different implementations don't have the same behavior then nothing will ever be compatible with anything.

Can my device driver use multiple threads? Can my device driver allocate a 2 MiB buffer? How do I tell the kernel to map my device's memory mapped I/O region into my address space? How do I tell the VFS that I'm a device? How do I find out when a file system mounts my device? Where's the relevant specification/s that tells me all of this, including everything I must comply with, and everything that other pieces of code (that I rely on) must comply with?


Cheers,

Brendan

[earlz]

thanks for all of these insights brendon.

taking the scheduler out of the kernel: This is so its possible to change out say a generic preemptive scheduler with something non-portable but that works off a timer interrupt or similar or any OS dever that wants to try their hand at making a scheduler(or testing one) can plug it in and work with their own scheduler... I wish for this to be useful to anyone(if it will ever be "complete") but to be especially useful and easy to low level programmers.

Certain modules(such as memory management and scheduling and HAL) will have set generic specifications that they must use(though they can extend beyond that).. in fact I expect to have a few global specifications on all modules so that they can be self identifying..

and my messaging will be very simple, though have the goal of being very fast(only slightly slower than monolithic designs using just 'call' )

I'll respond to the rest of your post in a while as I must go now.

[AndrewAPrice]

Might I suggest you look at L4? http://www.l4ka.org/

L4:Pistachio is a efficient, cross platform, implementation of L4 written in C. Even if you're writing your own kernel, look at their interface documentation for some interesting ideas.

The way I view it though, a micro-kernel is really just a building block for you to build an OS on top of. In the case of L4, it doesn't know what a VFS or a driver is, it doesn't know what executable format you're using. So to implement an OS on top of the kernel, you must create a standard for how drivers should register themselves (have a driver manager server), how file systems and work, how you load new processes (executable formats?).

So in my view, a microkernel is not a complete OS (though a kernel plays part of it), but a standard defining how the hardware and software interacts together. Then you create an implementation of each component (or allow others to do so) in your standard.

[earlz]

Might I suggest you look at L4? http://www.l4ka.org/

L4:Pistachio is a efficient, cross platform, implementation of L4 written in C. Even if you're writing your own kernel, look at their interface documentation for some interesting ideas.

The way I view it though, a micro-kernel is really just a building block for you to build an OS on top of. In the case of L4, it doesn't know what a VFS or a driver is, it doesn't know what executable format you're using. So to implement an OS on top of the kernel, you must create a standard for how drivers should register themselves (have a driver manager server), how file systems and work, how you load new processes (executable formats?).

So in my view, a microkernel is not a complete OS (though a kernel plays part of it), but a standard defining how the hardware and software interacts together. Then you create an implementation of each component (or allow others to do so) in your standard.

Yes, thats about how I want my kernel to be.. though to take it maybe a step further than even L4 did

[AndrewAPrice]

However, IMHO there are some things that never make sense (e.g. shifting the scheduler out of the kernel). In these cases you get the disadvantages (worse efficiency caused by slower interfaces) but you don't get any advantages (you're still screwed if it crashes).

I agree. I don't understand how some people say you can swap the scheduler at run time, but in what scenario would this be practical? It would only be practical on a single tasking system, because if multiple processes tried to switch the scheduler it would turn into chaos. But in a single tasking system, you might aswell give the application complete control over the timer interrupt since it's the only one running.

Perhaps the scheduler could be a loadable module that can be swapped at run time or specified at boot. Or work out a way that a combination of methods could fit into one. For example, a more realistic solution would be to let an application server tell the kernel what time slices and priorities to assign to processes, as well as group threads/processes together and assign each their own scheduling algorithm. That way a group of processes (e.g. high responsive servers) could use a different algorithm in the scheduler to another group (e.g. process intensive media codecs running in real time) without effecting the other.

[earlz]

Perhaps the scheduler could be a loadable module that can be swapped at run time or specified at boot. Or work out a way that a combination of methods could fit into one. For example, a more realistic solution would be to let an application server tell the kernel what time slices and priorities to assign to processes, as well as group threads/processes together and assign each their own scheduling algorithm. That way a group of processes (e.g. high responsive servers) could use a different algorithm in the scheduler to another group (e.g. process intensive media codecs running in real time) without effecting the other.

Well yes it can be swapped or whatever. You could setup a "scheduling scheduler module" which can manage multiple schedulers(and split timer interrupts between them) though that seems hella complex. It is fully possible with my system, as it is extremely flexible. You really can do anything with the framework I provide.. though your right, it doesn't count really as a full OS

[Brendan]

Hi,

However, IMHO there are some things that never make sense (e.g. shifting the scheduler out of the kernel). In these cases you get the disadvantages (worse efficiency caused by slower interfaces) but you don't get any advantages (you're still screwed if it crashes).

I agree. I don't understand how some people say you can swap the scheduler at run time, but in what scenario would this be practical? It would only be practical on a single tasking system, because if multiple processes tried to switch the scheduler it would turn into chaos. But in a single tasking system, you might aswell give the application complete control over the timer interrupt since it's the only one running.

Part of the problem with swappable schedulers is that schedulers have state. For example, one scheduler might manage several linked lists of "task structures", have its own way of doing CPU load balancing, use task priorities from 0 to 15, and keep track of used CPU time in nanoseconds; while another scheduler might manage a tree of "task structures", use entirely different CPU load balancing, use 4 levels of task priorities from "0:0" to "3:255", and keep track of used CPU time in "jiffies". You can't unload one scheduler and start another scheduler and expect the new scheduler to understand the old scheduler's data; and if you standardize this data (so that one scheduler can use the data from another scheduler) then all of the schedulers will end up being so similar that there's no point swapping from one scheduler to another anyway.

The other thing to consider is why you'd want to swap schedulers while the OS is running. For other things (e.g. device drivers), one of the reasons is fault tolerance - e.g. if a sound card driver crashes, then kill it and automatically replace it with a better sound card driver (or maybe just go without sound). For scheduler's this can't work (if the scheduler crashes you can't switch tasks, and can't assume that any of the existing scheduler's data hasn't become corrupted). Another reason is software upgrades. For e.g. when the next version of the scheduler is released, you might want to replace the current scheduler without having downtime (taking the computer off-line, rebooting, etc). In this case, for a micro-kernel there shouldn't be many software upgrades (because the micro-kernel doesn't include all the device drivers, etc, like a monolithic kernel); and if you can't afford downtime then you should be using redundant systems (e.g. failover) anyway, to minimize the risks of hardware failures, etc and to allow individual computers to be off-line for both software and hardware upgrades.


Cheers,

Brendan

[KurtGollhardt]

Or work out a way that a combination of methods could fit into one. For example, a more realistic solution would be to let an application server tell the kernel what time slices and priorities to assign to processes, as well as group threads/processes together and assign each their own scheduling algorithm. That way a group of processes (e.g. high responsive servers) could use a different algorithm in the scheduler to another group (e.g. process intensive media codecs running in real time) without effecting the other.

Yes. This is the way it's done in many commercial UNIX OSes. Start with a core "micro-scheduler" (sometimes called a "dispatcher") that handles the actual task switching and "owns" the core run queues. Add a set of "scheduling classes" that implement the different rules for managing process priority (static or dynamic)--and map their own range of priority values to a global range supported by the micro-scheduler, when tasks can yield the processor, and so on. Assign a scheduling class to each process or process group.

This adds a bunch of extra complication (including, not least, the design of a sufficiently flexible yet performant interface between the scheduling classes and the micro-scheduler), but if you need to handle a mixed load ("time-sharing" vs [pseudo] "real-time", for example), especially on a server, or you want to be able to experiment with different algorithms, it can be worth it.

The scheduling classes wouldn't need to be swappable in this case, though if you wanted you could let them be loaded dynamically but unloaded or swapped out when there are NO processes assigned to that scheduling class any more. This could facilitate experimentation and debugging without a reconfigure/reboot cycle.

[earlz]

Well I don't want the scheduler in the kernel because I want it to be easily swappable at boot at least. You have some points on not swapping at runtime... But this isn't my problem, individual modules can specify if they are hotswappable or not.. and the scheduler can implement whatever features it wants.. thats the great thing about this. I myself don't have to worry about the whole OS thing, I just have to worry about this tiny framework and implementing modules.. so when I want to do some OS deving, I'm not tackling a huge project, I'm working on one thing at a time.

[Brendan]

Hi,

Well I don't want the scheduler in the kernel because I want it to be easily swappable at boot at least.

A kernel module *is* in the kernel. When you say "not in the kernel" you're actually saying "in user space with insanely slow IPC (involving task switches and address space switches) used for communication". Are you sure that's what you mean?


Cheers,

Brendan

[earlz]

no, I mean "out of the kernel" as in near native speed IPC going from ring 0->0. (my framework doesn't know about userspace)