OSDev.org

Hi,


I decided to implement a scheduler, so I first need a mechanism to create and switch tasks. But I am wondering what is the best design for this.

I have considered two different ways for task creation:

• Have a task_create() function, which allocates a stack and puts initial data of the task on the stack.
• Have a task_create() function, which allocates a stack, plus some more memory for the initial data of the task. This way the address of the initial data would be non-variable.

I also don't know which parts of the initial data should be controllable by the task creator.

As for task switching, I am totally lost. I think I will have more clues when task creation will be more clear.


Thanks in advance,
glauxosdever

My OS puts the initial data (which is basically environment variables and command-line arguments) into a buffer on the kernel heap, and a field in the Thread structure contains a pointer to this data. Userspace can use a system call to obtain it; and my libc parses that and split it into the argv and environ arrays.

For task switching, a good way would be to have a runqueue. When a task is first created, add it to the end of a runqueue. The scheduler would just take the task at the front of the runqueue, remove it from the queue and jump to it (by loading its saved registers). Use the PIT or the APIC timer to limit the CPU time for each task; when a timer interrupt is received, you preempt the task: save its registers in the task structure, and put it at the end of the runqueue.

However, if a task wants to sleep (e.g. blocking function), you remove it from the runqueue and do not put it back. You still keep a "task list", so you have a reference to the task. When another task wants to wake it up, it will call a function like wake_task() on the task, and then you put the task at the end of the runqueueu if it is not already in the runqueue.

Hi,


For scheduling I plan on implementing Round Robin (possibly with some improvements).

What I asked, though, was task switching, not scheduling. That is saving the current task's state and loading the next task's state. The issue here is that I can't make up a good design before I decide how to implement task creation.

As for task creation, I think I'll wait for another opinion, so I get a broader perspective. Thank you for your answer anyway, it's part of the perspective.


Regards,
glauxosdever

presumably, your interrupt handler pushes the value of all registers onto the stack so that it can restore them.
so you just copy the saved registers from the stack into the task description, and you've saved the state.
to restore, you load them in the same way your interrupt handler reloads registers from the stack.

I have taken the hardware-based multitasking approach, but a little unorthodox (I think). Whenever a task switch has to occur, my scheduler just writes the pointer to the new task's TSS to the GDT. Then it performs a task switch using a far jump to the GDT TSS descriptor. This way, you are not clogging the GDT and you can have a virtually unlimited amount of tasks.

Yes, I know it is slow. But I just wanted to do it this way. Because of the approach I have taken, it will be fairly easy to replace it with software-based multitasking if I ever want to do so later on.

Hi,


I have not decided anything yet, although the answers were interesting.

I guess I need to understand how does the processor switch from one task to another, from start to finish. Please correct me if I am wrong.

When an interrupt happens, all registers are saved by the interrupt handler. Then, these values are copied to the structure of the previous task and the values from the structure of the next task are copied to the stack (in place of the values of the previous task). At the end, the interrupt handler exits and the new values are stored in the registers.


Thanks in advance,
glauxosdever

glauxosdever wrote:When an interrupt happens, all registers are saved by the interrupt handler. Then, these values are copied to the structure of the previous task and the values from the structure of the next task are copied to the stack (in place of the values of the previous task). At the end, the interrupt handler exits and the new values are stored in the registers.

Yes, this is correct.
The CPU does not do task switches, unless you're using the hardware task switching mechanism, which only works on IA32 (you can't use it in long mode).

Don't even need to copy anything. Just use the current threads own stack to preserve and restore that threads state.

The idea is simple - save the thread context onto the current threads kernel mode stack (its set by the cpu from tss.esp0.) To restore the thread context, just load the saved context from the next threads kernel mode stack back into the registers. Since each thread has its own stack, you can switch between them by just setting tss.esp0 = next_task->kernel_esp.

neon wrote:Don't even need to copy anything. Just use the current threads own stack to preserve and restore that threads state.

The idea is simple - save the thread context onto the current threads kernel mode stack (its set by the cpu from tss.esp0.) To restore the thread context, just load the saved context from the next threads kernel mode stack back into the registers. Since each thread has its own stack, you can switch between them by just setting tss.esp0 = next_task->kernel_esp.

This only works if every thread has its own kernel mode stack, which is one possible design. But another possible design is to have only one kernel mode stack per CPU, and in that case this approach does not work. Instead one would have to save the thread's user mode register state somewhere else, such as a struct thread_state.

neon wrote:Don't even need to copy anything. Just use the current threads own stack to preserve and restore that threads state.

The idea is simple - save the thread context onto the current threads kernel mode stack (its set by the cpu from tss.esp0.) To restore the thread context, just load the saved context from the next threads kernel mode stack back into the registers. Since each thread has its own stack, you can switch between them by just setting tss.esp0 = next_task->kernel_esp.

Then how do you modify the thread's registers, for example for dispatching signals?

mariuszp, the usual way is to make a backup copy (onto the task's user mode stack in an area above the stack pointer) and modify the registers in the task_state and return.

Hi,

glauxosdever wrote:I decided to implement a scheduler, so I first need a mechanism to create and switch tasks. But I am wondering what is the best design for this.

Creating a process is relatively expensive (e.g. likely the single most expensive thing a micro-kernel does) because it involves many things - doing permission checks, creating a virtual address space, creating some sort of "process data structure", creating an initial thread, dealing with/starting some sort of executable loader, etc.

When a high priority thread creates a process (and the new process has a lower priority initial thread), you want to postpone as much of the work involved as possible so that it costs the least of the high priority thread's time. When a low priority thread creates a process (and the new process has a higher priority initial thread), you want to do as much of the work involved as soon as possible so that the new higher priority process is created faster.

Fortunately; this can be relatively simple to achieve: do the least work possible to create the new process' initial thread, then let the scheduler figure out when the new thread gets CPU time when (based on thread priorities, etc), then do all the remaining work after the scheduler decides to give the new process' initial thread some CPU time. Note that this has other benefits - for example, it's easier for a newly created thread to access its own virtual address space (and harder for a thread that belongs to one process to modify things in a completely different process).

Creating a new thread (for an existing process) should follow the same logic - do the least possible, then let scheduler figure out when to switch to the newly created "minimal thread" (based on thread priorities, etc), then finish creating the new thread after scheduler has given it CPU time.

With this in mind; what is the least work you can do to create a new thread before that new thread is first given CPU time (and how much of the work involved can be postponed until after the new thread is given CPU time)?

When the scheduler switches to a thread it needs to load (at least some of) that thread's state - e.g. ESP/kernel stack, and whatever is popped off a thread's kernel stack by the thread switch code (e.g. EIP, etc). This information must exist before switching to the new thread, and therefore whoever created the new thread must create this information in advance. Everything else (e.g. the thread's FPU/MMX/SSE/AVX state, its debugging and performance monitoring state, its user-space state and user-space stack, etc) can be done after the scheduler switches to the new thread; and (if it's an initial thread for a new process) this can include building the rest of the process (building the new process' virtual address space, preparing the executable loader, etc). You'd also have to tell the scheduler that the new "minimal thread" is ready to run (e.g. put it on some sort of scheduler's queue or list maybe).

With this in mind, what you'd want when creating a new thread is a function pointer that points to some function in the kernel that will do the "after thread is given CPU time" part of the new thread's initialisation (so you can have different functions - one for "new thread for existing process", one for "new thread for new process", etc); and a "void *" pointer to a structure containing whatever data that function might need. You'd also want to know the new thread's priority, and which process it belongs to.

This gives you something like:
Where kernel functions that finish creating new threads end up like:

Cheers,

Brendan