How do modern OSs handle the CPU regs of multiple processes?

[Techflash]

How would a modern, multitasking OS, with 10s if not 100s of processes running simultaneously, ESPECIALLY on multicore CPUs, handle the CPU registers state of all of the various processes? The best I can imagine is something like the below code, however it seems like it would be WILDLY inefficient. Depending on how many CPU cycles it's executing per loop, it could be anywhere from completely unusable to Windows 10 running on 2GB of RAM under 3 layers of VirtualBox. Am I just thinking about this completely wrongly and it's actually far simpler than this? Or is it actually like this and it's just really REALLY optimized?
NOTE: This code hasn't actually been tested so I have no idea if it's even syntactically correct, but you can kind of understand what I'm trying to show here, it handles runs code from a process, then pushes the current state of the registers and stack into the struct for that process ID.

Code: Select all

#define MAX_STACK_SIZE_PROC 16384  /* 16K of stack for each process */
#define MAX_PROCESSES       1024
typedef struct {
    #if ARCH=="x86_64"
        uint64_t ...... /* x64 regs */
    #elif ARCH=="x86"
        uint32_t ...... /* x86 regs */
    ...... /* other architectures */
    #endif
} regs_t;

typedef struct {
    uint8_t stack[MAX_STACK_SIZE_PROC]; /* The raw bytes of the stack of the process */
    regs_t registers;
    uint16_t processID;
} processState_t;

processState_t procStates[MAX_PROCESSES];

processState_t runProcess(uint16_t id) {
    processState_t ret;
    ret.processID = id;
    /* Somehow run *x* number of CPU cycles for that process, then stop, likely using timers & interrupts. */
    ret.stack = somehowGetPointerToStackOfProc(id); /* This seems like it wouldn't work with the array above but you can understand the idea */
    ret.registers = getStoredRegistersFromEndOfExecutingProcess(id);
    return ret;
}    
void handleProcess(uint8_t id) {
    /* Somehow restore registers to the state they were at the end of the last cycle of execution with procStates[id].registers */
    procStates[id] = runProcess(id); /* Run the process, and push the state of everything returned by runProcess() back into the array */
    return;
}

int handleAllProcesses() {
    /* Calculate the load that the system is currently under, and if it's so much that we won't have time to manage system stuff like drivers and memory should we try to run the processes more, then return -1 to indicate that we need to start handling the system stuff now and if we still have time later, then handle the processes */
    if (systemLoad() >= 80) {
        return -1;
    }
    for (uint8_t i = 0; i > somehowGetNumberOfRunningProcesses(); i++) {
        handleProcess(i);
    }
    return 0;
}

[rdos]

Generally, registers are per thread, not per process (unless you have no support for threads). You keep registers with the control info for every thread. This actually is regardless if you use one or multiple CPU cores. It's the scheduler that will assign threads to cores and then will load & save register state.

[Octocontrabass]

Am I just thinking about this completely wrongly and it's actually far simpler than this?

Probably. You've got a lot of copying going on, but a typical OS will store per-thread data in a single memory location for the entire lifetime of the thread. When the OS needs to access one of those structures, it uses a pointer.

You've also got the design upside-down. An OS does not "call" programs, it returns to them. The OS itself only runs when it's either called by the program or interrupted by hardware, and both events work roughly the same: the OS saves the usermode registers, does some work (which may include a context switch), restores the usermode registers, and returns.

[BigBuda]

An OS does not "call" programs, it returns to them.

More specifically the kernel, as an actual typical OS is made up of several components and most of them run in userspace and are not part of the kernel. Considering the shell as part of the OS, then the OS (and not the kernel) "calls" programs, in a way, by asking the kernel to begin its execution.

[Techflash]

Ahh, thanks for all the feedback guys. I was just kinda curious how it was actually done traditionally (not that I'm anywhere close to implementing that in my OS, just interested for later).

[rdos]

Personally, I see no difference between user mode and kernel mode code that requests OS services. I'd rather claim that the OS exports some entrypoints that other code can call, and then saves whatever registers the calling convention requires. The specific user mode state is typically saved by the processor as part of the ring switch. Ring switches often use special instructions like syscall and then these stubs needs to decode calls & dispatch + save whatever registers need to be saved. In 32-bit protected mode, it's also possible to use call-gates from user mode which transparantly goes to some entry-point in kernel. The server code doesn't need to know who called it.

[Crono]

All modern x86-64 kernels use lapicTimer to switch from one process to another. In assembly its ~200 instructions to preserve regs of interrupted thread, find next to run thread (you dont make decision which one is next to run in lapicTimer), and restore new process regs. For each thread everything is stored in predefined location - easy to retrieve. It super ligtning speed for CPU.
If you want make distinction betw ring0 process and ring3 - you can, but you dont have to.
LapicTimer is used because its per CPU, and all threads it picks are local to CPU.

You should forget about such a thing as scheduler FOR NOW. The thing is cpus are very fast and if you put a round-robin selection of processes into LapicTimer - you’ll be all set.
You should forget about multi-cpu when it comes to distributing processes FOR NOW - because modern single core will handle any load at your level of os development. BUT you must develop everything using locks as it was multi-cpu - saves a ton of time later.

Lastly more interesting LapicTimer implementations are ~500 assembly instructions. Sometimes its simply tons of sanity check - under which conditions LapicTimer was trigerred. Still lightning speed considering stuff you can put in there with ints disabled. LapicTimer should not be used to sync anything with real time.

During process switch in LapicTimer you can check if timers are due to fire and do premature switch to these processes - no need for a scheduler if you respect high precision but large timeout increments. You can generate sessionID (a random #) - tons of applications.

[immibis]

You've also got the design upside-down. An OS does not "call" programs, it returns to them. The OS itself only runs when it's either called by the program or interrupted by hardware, and both events work roughly the same: the OS saves the usermode registers, does some work (which may include a context switch), restores the usermode registers, and returns.

From a theoretical perspective, I think you've got it upside-down. Consider what a "call" is: a jump with an expectation of coming back to the current point later. It doesn't actually matter whether the instruction you use to accomplish it is named CALL or RET. And if your scheduler looks like this:

Code: Select all

while(true) {
  runProcess(getBestProcess());
}

then the scheduler is so much simpler to understand!

[Crono]

When it comes to multicore cpus - each cpu has its own set of local processes that do not move betw cores too often. Thus its single cpu design to handle. The more powerful cpu - the more you can afford to move more often, but RDOS here were pushing for very long time that more moving more problems. This could be right but only because kernel knows nothing about those, not that it should.

Linux is ring0 microkernel because it switches cr3 on every syscall. Due to widely known cache bugs. Imagine if ring3 does the same via syscall with new cr3 physical without kernel knowing about new process in kernel undestanding. Because ring3 knows that those processes mean and how to arrange them.

And, when user input devices tells there is a packet for GUI - process switch must be instantanious, otherwise user will think whole OS is slow becausecmouse is slow. Dev driver needs to know screen resolution and desired mouse refresh rate to minimize switching.

[Octocontrabass]

From a theoretical perspective, I think you've got it upside-down. Consider what a "call" is: a jump with an expectation of coming back to the current point later. It doesn't actually matter whether the instruction you use to accomplish it is named CALL or RET.

But user mode programs call the kernel. It doesn't make sense to use "call" in both directions.

And if your scheduler looks like this [...] then the scheduler is so much simpler to understand!

Your scheduler may be easier to understand, but you're trading that for additional complexity in your kernel's entry/exit points. Are you sure that's a good trade?

[eekee]

From a theoretical perspective, I think you've got it upside-down. Consider what a "call" is: a jump with an expectation of coming back to the current point later. It doesn't actually matter whether the instruction you use to accomplish it is named CALL or RET.

But user mode programs call the kernel. It doesn't make sense to use "call" in both directions.

It's relatively uncommon, but there are examples of calling in both directions, most notably coroutines.

I think the whole thing could be seen as a state machine; the thread of execution is either in user state or kernel state, but I don't think I like that. I'd prefer to see syscalls as calls, but the scheduler is a separate abstract concept to me. I'm fine with implementing it with RET or anything else.

Edit: RET from the scheduler might be easiest to think of as returning from the timer interupt which called the scheduler.

[xeyes]

And if your scheduler looks like this:

Code: Select all

while(true) {
  runProcess(getBestProcess());
}

then the scheduler is so much simpler to understand!

Does runProcess() return when the app is done? What if it is preempted?

I guess people tend to say return because of the flexiblility of IRET (and to a lesser degree, far return) on x86.

[nullplan]

I guess people tend to say return because of the flexiblility of IRET (and to a lesser degree, far return) on x86.

It is the same on many architectures. My beloved PowerPC has "rfi" (return from interrupt), and that instruction is used twice for each syscall and interrupt. Because someone decided that all exceptional conditions ought to turn off the MMU, so the first-level exception handlers have to find a kernel stack to write their info to and then use "rfi" to turn on the MMU again and transition to the kernel handler in the same instruction. And then afterwards it uses "rfi" to return to the user space code.

However, this is a detail. I tend to see execution on a CPU as something in which userspace resides on the topmost stack frame. Any interrupt or syscall transitions to kernel space and pushes the outermost stack frame onto the kernel stack (on PowerPC this just happens in software while the MMU is off, but that is incidental), and finally the CPU will return back to userspace. Scheduling means switching stacks, and the lowlevel switch function does nothing but saving the non-volatile registers before doing so. On thread exit the same thing happens, except the task is marked with a flag that means it will never be scheduled in again. And on startup, initialization does partly entail constructing an initial task stack. The funny thing is, you never need to clean up the stack entirely when running the userspace task for the first time: Just construct an IRET frame and perform an IRET (or maybe just SYSRET), and next time the kernel is called, stack starts over at the place named in the TSS.

[immibis]

But user mode programs call the kernel. It doesn't make sense to use "call" in both directions.

Your scheduler may be easier to understand, but you're trading that for additional complexity in your kernel's entry/exit points. Are you sure that's a good trade?

Yes, you have two levels of calling, really. Imagine an algorithm like a DFS with an explicit stack. Then you call doSomeDfsWork and it does some processing using that stack. It makes sense to say that node processing "recurses", and it also makes sense to say you are calling doSomeDfsWork, and the two kinds of calls are orthogonal and happen on different stacks and everything is completely okay with that.

Does it make sense to implement a scheduler as that loop? Maybe not literally, but I think it's fun to imagine it that way. As a conceptual model it answers a bunch of questions about scheduling, like what state to create a process in, what happens if it destroys itself while running, and how scheduling interacts with syscalls.

[rdos]

But user mode programs call the kernel. It doesn't make sense to use "call" in both directions.

Your scheduler may be easier to understand, but you're trading that for additional complexity in your kernel's entry/exit points. Are you sure that's a good trade?

Yes, you have two levels of calling, really. Imagine an algorithm like a DFS with an explicit stack. Then you call doSomeDfsWork and it does some processing using that stack. It makes sense to say that node processing "recurses", and it also makes sense to say you are calling doSomeDfsWork, and the two kinds of calls are orthogonal and happen on different stacks and everything is completely okay with that.

Does it make sense to implement a scheduler as that loop? Maybe not literally, but I think it's fun to imagine it that way. As a conceptual model it answers a bunch of questions about scheduling, like what state to create a process in, what happens if it destroys itself while running, and how scheduling interacts with syscalls.

I see the scheduler as an event handler, not some sequential code that runs in a loop. Additionally, the scheduler runs in the context of random threads (IRQs) or in the context of a thread requesting some scheduler-related action. I also have a load-balancer and IRQ-balancer that runs in a kernel thread, but that's to optimize the system and is not directly connected to scheduling.

IMO, the scheduler should in no way interact with syscalls. The scheduler shouldn't care if a thread runs in kernel mode or user mode, and should not be needed to be informed about switching rings.

Debug-wise, it's far superior to load & store registers in the thread control block rather than depending on stack contexts. This makes it easy to create a new thread: Create the thread control block, initialize the registers, allocate a kernel stack, and put it into the ready list.