User:Mariuszp/Scheduler Tutorial

In this tutorial I will teach you how to write a scheduler (specifically for x86).

What is a scheduler?

A scheduler is the part of your OS which allows programs to run (seemingly) "at once", without overwriting each others data. The idea is that there is a way to switch between running tasks. This can be done automatically (multi-tasking) or at the user's demand.

This tutorial will not explain paging, but it will explain how to load a simple flat binary file if you want to test your multitasking. For this specific tutorial, you will need to have a timer that generates an interrupt, so we can switch tasks automatically. Program this timer to be at a relatively high speed.

How do schedulers work?

There are many ways to implement a scheduler. The method that was once used by MS-DOS extenders, as well as early Microsoft Windows, was co-operative multi-tasking. Every running process keeps calling a yield() function, which tells the scheduler to switch task. The downside of this is that it is easy to crash your system - if a process doesn't yield(), your system is not able to work any more. Another way you could do it is switch the task when a process uses a system call, which it would do frequently enough, or you could use both at once (ie. a yield system call). You could also allow the user to switch tasks themselves using some key, but for most users, this would ruin the idea of multi-tasking, because to them it would still seem that only one process can run at once.

The method I will explain here is a bit safer. This is called preemptive multi-tasking. You use a hardware timer which actively throws some interrupt, and the interrupt handler will save the process registers and switch the task. For that you can use the PIT, the APIC timer, etc.

Saving register states

First, you need a way to save register states when a task switch happens. There is actually quite a simple way to do this. In my OS, there is a common handler function which dispatches interrupts. Obviously, when the interrupt (IRQ0) is fired, some information (EIP, ESP, etc.) is pushed onto the stack. You can then use PUSHA to push the GPRs on. Please note that in my implementation, regs->esp is the temporary kernel stack, and should not be modified, while regs->useresp is the real value for ESP. My register structure is known by the type registers_t.

Of course, you can implement this any way you want to, just make sure that you can actually save those registers.

Paging...

Let's just assume that the function create_user_pages(x, y) copies the kernel space into a new page directory, and makes the range from x to y user-accessible. We will need this to create page directories for the executables.

Let's do it!

OK, we're ready to start doing some code!

process_t

The process_t structure contains information about a process. Let's define it as follows:

 typedef struct process_struct
 {
     registers_t     regs;
     pagedir_t       *cr3;
     struct process_struct *next;
 } process_t;

The 'regs' field contains the saved state of the processor registers prior to the program interruption. Remember, we need to restore them so that the program doesn't break! If you use paging, the 'cr3' field obviously contains the program's page directory (that doesn't need saving, because it doesn't change - you just set it right at the start).

pqueue & current_proc

pqueue means process queue, and current_proc means, well, current process :D

 process_t *pqueue;
 process_t *current_proc;

When the scheduler is first started, you should set pqueue to some idle task, which basically loops forever. 'pqueue' will be used as the first process, so when we schedule through the whole queue, we start again at pqueue. current_proc will be set to the currently running process.

switch_task

The switch_task() function takes the saved registers_t as the argument, and should be called by the IRQ0 handler.

 volatile void switch_task(registers_t *regs)
 {
   /* copy the saved registers into the current_proc structure */
   memcpy(&current_proc->regs, regs, sizeof(registers_t));
 
   /* now go onto the next task - if there isn't one, go back to the start
      of the queue. */
   if (current_proc->next != NULL) current_proc = current_proc->next;
   else current_proc = pqueue;
 
   /* now hack the registers! */
   memcpy(regs, &current_proc->regs, sizeof(registers_t));
   switch_page_directory(current_proc->cr3);
 };

If you use the method I described above, then by changing the registers on the stack, you can perform a task switch. When the processor performs the POPA and IRET instructions, the "dirty work" will be done for you. Of course, if you use paging, you must also change the page directory to the one that the process uses.

Loading flat binaries

A flat binary executable can only be loaded at one location. So if you move userspace in your OS, software will no more become functional. It is also difficult to implement shared libraries, because all binaries must be loaded at a given location. Let's take 6MB into memory. So, let's define a UCODE_START constant:

 #define UCODE_START 0x600000

Now, create a simple 32-bit flat binary in assembly language:

 ; test.asm
 bits 32
 org 0x600000
 jmp $

Assembler with:

 nasm test.asm -o test.bin -f bin

Now, assuming you can open a file and read its contents into memory, loading a flat binary is really simple:

 void load_bin(uint8_t *data, size_t size)
 {
   /* create the process_t and page directory (if you use paging) */
   process_t *proc = (process_t*) kmalloc(sizeof(process_t));
   proc->cr3 = create_user_pages(UCODE_START, UCODE_START+size);
 
   /* now we must copy the contents of the binary into memory, which involves changing
      the cr3 register if you use paging. If you _don't_ use paging, a memcpy is enough. */
   pagedir_t *temp = current_cr3;
   switch_page_directory(proc->cr3);
   memcpy(UCODE_START, data, size);
   switch_page_directory(temp);
 
   /* now we need to set up registers, of course. */
   proc->regs.cs  = 0x08;
   proc->regs.ds  = 0x10;
   proc->regs.ss  = 0x10;
   proc->regs.eip = UCODE_START;
 
   /* add the new process to the end of the queue. */
   process_t *last = pqueue;
   if (!last)
   {
     pqueue = proc;
     return;
   };
   while (last->next != NULL) last = last->next;
   last->next = proc;
 };

What else?

There are plenty of things you may wish to do.

Executable Formats

Flat binaries have many drawbacks. You could learn to load some other format.