Quesitons about kernel design and direction for a newbie

[Scoopta]

Over the last couple years I've been developing my first kernel that's actually kind of gotten somewhere(that is it's more than hello kernel). I have a lot of the low level stuff implemented(memory allocator, elf loader etc) and I thought going with a microkernel design might be a fun idea but just trying to get my head around the architecture required to put the scheduler into userspace is hurting my brain, of course every part of the journey up till now has hurt my brain. I've been struggling with whether or not I should struggle through and stick to a microkernel design given everything up to this point(and probably beyond) has been a struggle, if I should scrap it and go with a monolithic design which would arguably be easier to implement, or if I should compromise and put the scheduler in kernel space while putting the rest of the drivers in user space. Any thoughts from those with more experience or others that have been here before? My current idea is basically set a timer which will preempt into kernel space and then the kernel will pass off to my scheduler process, maybe that design is inherently flawed and I just don't see it yet. Thanks for any advice/input.

[nullplan]

Basically, a scheduler consists of a voluntary entry point (where tasks go that want to shed their time slice), an involuntary entry point (where tasks go that did not yield), a task picker, and a task switcher. Of these, only the task picker can possibly be implemented in user space. So the common design in microkernels is that all entry points to the scheduler eventually lead to it asking the task picker what task(s) to run next, and then switching to those. Or you might just as well not bother putting that small part into userspace and just implement everything in kernel space. It really is your call to make.

I've been struggling with whether or not I should struggle through and stick to a microkernel design [or] if I should scrap it and go with a monolithic design

You and your quaint little categories. There is no need to stick to any one design philosophy, except maybe to appease Andrew Tanenbaum. And he's busy, he won't look at your kernel. I would suggest just going with whatever works. If you have deviated from the pure theory at one point, then either it does not matter to you, and you can leave it as it is, or it does matter to you, then you can fix it once you have a handle on everything. Start with a version that works, then refine it to one that follows your ideals. Yes, asking a userspace process a question while implementing a scheduler is a bit of a brain-bender. So write a version that works and then see if you can get it to do a thing you want. And remember, you can always read source from other operating systems. Other people have faced and overcome the same issues before, and there is no reason to do it all over again if you can just learn from them. That is part of the reason for open-source code.

[deadmutex]

For your first kernel, it would probably be better to develop a monolithic kernel. If you wish, you can later add in support to have some of your drivers in userspace (like the keyboard driver, for example). But a microkernel requires a deep understanding of OS design in order to get it to work as part of an entire operating system. That's because you end up exporting most of the complexity from kernel space to user space, with the additional headache of having to worry about how your services will communicate with each other and transfer data (as opposed to simply calling a function and passing pointers).

[Scoopta]

Basically, a scheduler consists of a voluntary entry point (where tasks go that want to shed their time slice), an involuntary entry point (where tasks go that did not yield), a task picker, and a task switcher. Of these, only the task picker can possibly be implemented in user space. So the common design in microkernels is that all entry points to the scheduler eventually lead to it asking the task picker what task(s) to run next, and then switching to those. Or you might just as well not bother putting that small part into userspace and just implement everything in kernel space. It really is your call to make.

I've been struggling with whether or not I should struggle through and stick to a microkernel design [or] if I should scrap it and go with a monolithic design

You and your quaint little categories. There is no need to stick to any one design philosophy, except maybe to appease Andrew Tanenbaum. And he's busy, he won't look at your kernel. I would suggest just going with whatever works. If you have deviated from the pure theory at one point, then either it does not matter to you, and you can leave it as it is, or it does matter to you, then you can fix it once you have a handle on everything. Start with a version that works, then refine it to one that follows your ideals. Yes, asking a userspace process a question while implementing a scheduler is a bit of a brain-bender. So write a version that works and then see if you can get it to do a thing you want. And remember, you can always read source from other operating systems. Other people have faced and overcome the same issues before, and there is no reason to do it all over again if you can just learn from them. That is part of the reason for open-source code.

Yeah, my initial plan was to put the task picker in user space. Basically something like APIC preempts into the kernel -> kernel switches execution the user space scheduler -> selects next task -> tells kernel to switch to it. So I definitely seem to be on the right track, I almost feel like that's way too many context switches just to change from one process to another. My kernel is running in long mode and is using syscall/sysret for the switches but even then it seems wastefully inefficient. As you said, maybe there isn't really a point to putting any of the scheduler in userspace at all.

For your first kernel, it would probably be better to develop a monolithic kernel. If you wish, you can later add in support to have some of your drivers in userspace (like the keyboard driver, for example). But a microkernel requires a deep understanding of OS design in order to get it to work as part of an entire operating system. That's because you end up exporting most of the complexity from kernel space to user space, with the additional headache of having to worry about how your services will communicate with each other and transfer data (as opposed to simply calling a function and passing pointers).

I've also been playing with this idea and I mainly picked a microkernel because it sounded cool more than for any "religious" reason. That being said I'm not shy to lots of suffering...this is my first kernel and I've taken a rather unconventional approach so far. That is to say I decided very early on not to have any IBM PC legacy stuff in it, kernel starts in and runs entirely in long mode with proper paging setup, requires UEFI to boot, uses the APIC for timing(still have to figure out calibration for this, probably ACPI timer) etc. Not to mention the fun that's going to come as I need block drivers, keyboard drivers, etc. That decision alone has made development a lot more grueling and difficult than it otherwise would be but at least it's mostly just spending hours reading and understand specifications and then implementing them as opposed to trying to design some well crafted message passing system capable of supporting a microkernel. Honestly even once I get past the scheduler I'm still not entirely sure how to, for example, build an FS driver which will call into the block drivers in a separate process and then keep track of who returns where and the scheduling around that. Having to I guess flag a task as relying on the results of another task before I can resume execution on that and then donating a tasks timeslice to the task it's dependent on. I guess the other option would be to make all the message passing asynchronous, which sounds equally brain bending and complex. Honestly a microkernel seems to get more and more complex the more and more I think about all the nitty gritty details. I guess I'm just trying to decide if it's a massive amount of extra suffering compared to the already immense amount of difficulty in building my own kernel.

[deadmutex]

Yeah, my initial plan was to put the task picker in user space. Basically something like APIC preempts into the kernel -> kernel switches execution the user-space scheduler -> selects next task -> tells kernel to switch to it. So I definitely seem to be on the right track, I almost feel like that's way too many context switches just to change from one process to another. My kernel is running in long mode and is using syscall/sysret for the switches but even then it seems wastefully inefficient. As you said, maybe there isn't really a point to putting any of the scheduler in userspace at all.

The 4 user/kernel switches + 2 context switches is a problem that microkernels have in general. You'd have the same issue if you were to put the page fault handler or IRQ handlers in user-space. A well-designed IPC system (not necessarily message passing) can mitigate the performance penalty.

Honestly even once I get past the scheduler I'm still not entirely sure how to, for example, build an FS driver which will call into the block drivers in a separate process and then keep track of who returns where and the scheduling around that.

If using synchronous message passing, then here's one way to do it with RPC calls: in addition to having send() and receive(), you'd also have send_and_wait() which sends a request to a server and immediately waits for a reply. If the recipient isn't ready to receive then the sender blocks and the kernel sends a message to the scheduler. If, on the other hand, the recipient is already waiting to receive a request from the sender, then the kernel sets the sender to receive a reply from the recipient and then switches to the recipient, donating the remaining timeslice. Once the request has been serviced, the server sends a reply back to the sender and the kernel resumes execution of the sending thread. So, a client does a send_and_wait() to the FS driver and the FS driver does a send_and_wait() to the block driver. Then the block driver sends a response to the FS driver and the FS driver sends a response to the client. A lot of switching is involved, which is why IPC design is so important.

For user-mode scheduling in microkernels, you might find this paper helpful.

Stoess, J. Towards Effective User-Controlled Scheduling for Microkernel-Based Systems, ACM SIGOPS Operating Systems Review, Volume 41, Issue 4, Jul 2007, pp 59-68. https://doi.org/10.1145/1278901.1278910

[nullplan]

Yeah, my initial plan was to put the task picker in user space. Basically something like APIC preempts into the kernel -> kernel switches execution the user space scheduler -> selects next task -> tells kernel to switch to it. So I definitely seem to be on the right track, I almost feel like that's way too many context switches just to change from one process to another. My kernel is running in long mode and is using syscall/sysret for the switches but even then it seems wastefully inefficient. As you said, maybe there isn't really a point to putting any of the scheduler in userspace at all.

STOP! Go back to start and remember your first principles: First make it work, then make it work fast. The system you have right now is the worst possible one, because it does not exist yet. Any scheduler at all, even if it takes a full second to complete a process switch, is better than that (on the principle that something is better than nothing). So just go back and implement your design, and then figure out how to make it better.

Software development is essentially a learning process, less engineering and more "throwing stuff at the wall to see what sticks". The important part is that implementing something will teach you about the challenges associated with that thing, which details require more consideration, etc. So just build it and see what questions remain unanswered. And never optimize before measuring. Programmers are notoriously bad at anticipating performance. Just try it, it probably won't be that bad.

[vvaltchev]

Over the last couple years I've been developing my first kernel that's actually kind of gotten somewhere(that is it's more than hello kernel). I have a lot of the low level stuff implemented(memory allocator, elf loader etc) and I thought going with a microkernel design might be a fun idea but just trying to get my head around the architecture required to put the scheduler into userspace is hurting my brain, of course every part of the journey up till now has hurt my brain. I've been struggling with whether or not I should struggle through and stick to a microkernel design given everything up to this point(and probably beyond) has been a struggle, if I should scrap it and go with a monolithic design which would arguably be easier to implement, or if I should compromise and put the scheduler in kernel space while putting the rest of the drivers in user space. Any thoughts from those with more experience or others that have been here before? My current idea is basically set a timer which will preempt into kernel space and then the kernel will pass off to my scheduler process, maybe that design is inherently flawed and I just don't see it yet. Thanks for any advice/input.

My advice is to keep the scheduler and basic memory management in the micro-kernel itself. It's way simpler and faster than trying to put even the scheduler in user space. Also, that's exactly what most of the microkernels do. Then, you might consider implementing filesystems and drivers in user space, if you want.

But, if I have to be completely honest, I'd say that it would make sense to me trying first to have something working using the simplest model possible (monolithic kernel) and then, step by step, modify it in a way that parts of it run in userspace. This way you'll have:

- More time to learn hands-on the typical OS problems before getting into microkernels

- A stable system to play with, while you'll be working on increasing the complexity of its architecture.
Probably, you'll have some automated tests as well at this point.

- A sense of reward given by the results so far: starting with the 4th gear in will lead you to so many problems that you might demotivate yourself.

Vlad

[nexos]

I'm developing a microkernel as well. And have spent many hours thinking about the design. Although its all on paper at the moment (I'm currently redesigning my build system), I can give you a few recommendations.

First, read books about OS theory. No, I'm not talking about ast's books. My personal favorite is Uresh Vahalia's Unix internals. It will make theory make sense.

Second, don't start with clumsy algorithms then use good ones. You'll have a mess.

Third, implement the scheduler and memory manager in the kernel. No microkernel implements scheduling in user space. Implementing memory management in user space will make you very confused when designing it. Note that the process manager should go in user space, and parts of the memory manager as well, but not the whole thing.

Fourth, plan your algorithms. I have been planning my algorithms for nearly 6 months now! Be sure to especially plan your IPC system.

One more thing, look into the "One kernel stack per CPU" approach. If done right, it could improve performance (less context switches).

[Scoopta]

The 4 user/kernel switches + 2 context switches is a problem that microkernels have in general. You'd have the same issue if you were to put the page fault handler or IRQ handlers in user-space. A well-designed IPC system (not necessarily message passing) can mitigate the performance penalty.

I didn't even think about handling IRQs in userspace O_O...think I'll pass on that one.

If using synchronous message passing, then here's one way to do it with RPC calls: in addition to having send() and receive(), you'd also have send_and_wait() which sends a request to a server and immediately waits for a reply. If the recipient isn't ready to receive then the sender blocks and the kernel sends a message to the scheduler. If, on the other hand, the recipient is already waiting to receive a request from the sender, then the kernel sets the sender to receive a reply from the recipient and then switches to the recipient, donating the remaining timeslice. Once the request has been serviced, the server sends a reply back to the sender and the kernel resumes execution of the sending thread. So, a client does a send_and_wait() to the FS driver and the FS driver does a send_and_wait() to the block driver. Then the block driver sends a response to the FS driver and the FS driver sends a response to the client. A lot of switching is involved, which is why IPC design is so important.

For user-mode scheduling in microkernels, you might find this paper helpful.

Stoess, J. Towards Effective User-Controlled Scheduling for Microkernel-Based Systems, ACM SIGOPS Operating Systems Review, Volume 41, Issue 4, Jul 2007, pp 59-68. https://doi.org/10.1145/1278901.1278910

Hmmm, that's an interesting idea, I might mess with that. I think part of my problem is I was originally approaching it a bit too conventionally? Not sure if that's the right word. What I mean by that is instead of having EVERYONE send messages I was trying to come up with a way to basically return to the caller instead of just telling the receiver who the caller is and having them simply send a message back. So the flow I've been trying to work around in my head is something like process sends to FS driver, FS driver sends to block driver, and then block driver RETURNS to FS driver and the kernel has to figure out who that return goes to and such...I think I was massively over-complicating this by trying to add a return mechanism.

STOP! Go back to start and remember your first principles: First make it work, then make it work fast. The system you have right now is the worst possible one, because it does not exist yet. Any scheduler at all, even if it takes a full second to complete a process switch, is better than that (on the principle that something is better than nothing). So just go back and implement your design, and then figure out how to make it better.

Software development is essentially a learning process, less engineering and more "throwing stuff at the wall to see what sticks". The important part is that implementing something will teach you about the challenges associated with that thing, which details require more consideration, etc. So just build it and see what questions remain unanswered. And never optimize before measuring. Programmers are notoriously bad at anticipating performance. Just try it, it probably won't be that bad.

...I uhhhh am not exactly over-planning. The system I described is KINDA what my current kernel actually does...just without the working scheduler bit. That is, the kernel currently sets up the APIC for preemption, it currently jumps into a userspace scheduler on preemption, that userspace scheduler then goes back into the kernel. The bit I haven't figured out is the message passing and stuff around actually getting it to schedule in userspace hence the main question. I'm very much a fan of writing without much forethought...maybe a bit too much lol.

My advice is to keep the scheduler and basic memory management in the micro-kernel itself. It's way simpler and faster than trying to put even the scheduler in user space. Also, that's exactly what most of the microkernels do. Then, you might consider implementing filesystems and drivers in user space, if you want.

But, if I have to be completely honest, I'd say that it would make sense to me trying first to have something working using the simplest model possible (monolithic kernel) and then, step by step, modify it in a way that parts of it run in userspace. This way you'll have:

- More time to learn hands-on the typical OS problems before getting into microkernels

- A stable system to play with, while you'll be working on increasing the complexity of its architecture.
Probably, you'll have some automated tests as well at this point.

- A sense of reward given by the results so far: starting with the 4th gear in will lead you to so many problems that you might demotivate yourself.

Vlad

I've thought about doing this a bit but I'm a bit worried I'll get into a situation where modifying the monolithic kernel to be more dependent on userspace servers will be incredibly difficult because I fail to design my drivers in a way that allows for easy removal from kernel space.

I'm developing a microkernel as well. And have spent many hours thinking about the design. Although its all on paper at the moment (I'm currently redesigning my build system), I can give you a few recommendations.

First, read books about OS theory. No, I'm not talking about ast's books. My personal favorite is Uresh Vahalia's Unix internals. It will make theory make sense.

Second, don't start with clumsy algorithms then use good ones. You'll have a mess.

Third, implement the scheduler and memory manager in the kernel. No microkernel implements scheduling in user space. Implementing memory management in user space will make you very confused when designing it. Note that the process manager should go in user space, and parts of the memory manager as well, but not the whole thing.

Fourth, plan your algorithms. I have been planning my algorithms for nearly 6 months now! Be sure to especially plan your IPC system.

One more thing, look into the "One kernel stack per CPU" approach. If done right, it could improve performance (less context switches).

...that's...an awfully lot of planning in contrary to one of the other posts here lol...I uhhh, jumped into my kernel right away. As noted I've actually already implemented pieces of the userspace scheduler, I just have gotten a bit stuck with how to actually make it schedule and not play ping pong with the kernel as the only process in ring 3 and wasn't sure how to best approach its design.

[vvaltchev]

I've thought about doing this a bit but I'm a bit worried I'll get into a situation where modifying the monolithic kernel to be more dependent on userspace servers will be incredibly difficult because I fail to design my drivers in a way that allows for easy removal from kernel space.

I understand that. Just, I'm personally very comfortable with heavy refactoring: once I have something that works and tests to validate it, it's actually pretty fun for me to modify it even in a long series of almost "mechanical" steps. But yeah, I've noticed that other people prefer don't like that approach.

EDIT: fix typos.

[nexos]

...that's...an awfully lot of planning in contrary to one of the other posts here lol...I uhhh, jumped into my kernel right away. As noted I've actually already implemented pieces of the userspace scheduler, I just have gotten a bit stuck with how to actually make it schedule and not play ping pong with the kernel as the only process in ring 3 and wasn't sure how to best approach its design.

I probably went slightly overboard with planning . A ring 3 scheduler is not a good idea. You should implement your core scheduling functions in kernel, because scheduling is very performance critical.

Some OSes have a kernel schedule Lightweight Processes (LWPs) and a threads library in user space multiplex so called "user threads" on these LWPs. This approach can have great performance if done right, it just is very complex.

[Korona]

IMHO it doesn't make a lot of sense to plan an entire system in advance, especially if you don't have any experience in OSdev. You will make mistakes anyway, even when planning. You will also not really know what needs planning and how to plan efficiently if you don't have any experience.

You will arrive at a good design faster if you first do mistakes, before you invest time into extensive planning.

[vvaltchev]

IMHO it doesn't make a lot of sense to plan an entire system in advance, especially if you don't have any experience in OSdev. You will make mistakes anyway, even when planning. You will also not really know what needs planning and how to plan efficiently if you don't have any experience.

You will arrive at a good design faster if you first do mistakes, before you invest time into extensive planning.

I totally agree: top-down design works only if you have plenty of experience with a particular class of problems and a deep theoretical and practical understanding. Sure, studying a lot OS theory will help, but it's not enough IMHO. In my case, no book, no matter how technical it was could answer all of my the questions. I had to learn an incredible amount of things on the field.

[nexos]

I had to learn an incredible amount of things on the field

True, and experience can be the best teacher, but OS things didn't start to make sense to me until I read the theory. I had to put an effort into investigating how SMP scheduling works (which is where I got stuck with my earlier kernels ) before it made sense. Same goes for microkernel IPC. When it comes to hardware stuff, I do agree, reading the manuals gives you direction, but really, hardware stuff won't make sense until you implement it. But with something such as multitasking, those who don't understand it are bound to reinvent it - poorly.

Of the 6 months, much of that time was spent trying to create the best build system, and plan out every possible thing I might want to do. I then realized I was wasting time that I could be spending writing an OS .

[Scoopta]

I probably went slightly overboard with planning . A ring 3 scheduler is not a good idea. You should implement your core scheduling functions in kernel, because scheduling is very performance critical.

Just a bit...yeah, maybe I will. Part of me wants to go full monolithic just because I feel like I might actually make progress. I might try some of the other ideas here first before I give up on a microkernel though.

EDIT: I'm aware you're not implying I give up on a microkernel, just simply advising I don't put the scheduler in ring 3