Multitasking Howto

This little HowTo is intended to show, how to set up a multitasking environment for a custom OS. If you have questions: don't hesitate to drop me a mail.
For the beginning: you will of course need several Knowledge like how to handle linked Lists or BinaryTrees, which I won't cover in this text. I will show you the basics of a stack-based multitasking subsystem.
Multitasking on a single processor machine: to switch between a bunch of processes in a quick manner: each of them posesses for either a certain time or until it gives it up - the CPU.
First, lets define the process structure: it covers the essential informations about a process and is the MAIN element an operating system uses to handle processes.

typedef struct {
          uint_t prozess_esp;    //actual position of esp
          uint_t prozess_ss;     //actual stack segment.
          uint_t prozess_kstack; //stacktop of kernel stack
          uint_t prozess_ustack; //stacktop of user stack
          uint_t prozess_cr3;
          uint_t prozess_number;
          uint_t prozess_parent;
          uint_t prozess_owner;
          uint_t prozess_group;
          uint_t prozess_timetorun;
          uint_t prozess_sleep;
          uint_t prozess_priority;
          uint_t prozess_filehandle;
          console_t *prozess_console;
          memtree_t *vmm_alloc; //memory management info concerning the process 
                         //- all its allocated virtual memory
          uchar_t prozess_name[32];
        } prozess_t;

You see in this segment five very important fields: esp,ss,kstack,ustack,cr3 - these, especially esp, are accessed via the low-level asm-routines. esp holds the actual position of the KERNEL-ESP of the actual process, which has been interrupted by any isr or system call. The asm stub stuffs the esp-adress in this field.
We also need a TSS: in this system wide available structure, the processor finds the Kernel stack of the interrupted process in the esp0-field. Upon each task switch this field has to be updated to the according kernel-stack adress of the NEXT process. This may even be the LAST process. The stack switching method doesn't care about it. Here is a definition of a tss.
TSS in C:

typedef struct {
       ushort_t backlink, __blh;
       uint_t esp0;
       ushort_t ss0, __ss0h;
       uint_t esp1;
       ushort_t ss1, __ss1h;
       uint_t esp2;
       ushort_t ss2, __ss2h;
       uint_t cr3;
       uint_t eip;
       uint_t eflags;
       uint_t eax, ecx, edx, ebx;
       uint_t esp, ebp, esi, edi;
       ushort_t es, __esh;
       ushort_t cs, __csh;
       ushort_t ss, __ssh;
       ushort_t ds, __dsh;
       ushort_t fs, __fsh;
       ushort_t gs, __gsh;
       ushort_t ldt, __ldth;
       ushort_t trace, bitmap;
      } tss_t;

Next, we need the proper routines for the ISR's:

%macro REG_SAVE 0
      ;save all registers in the kernel-level stack of the process and switch to the kernel stack
        cld
        pushad
        push ds
        push es
        push fs
        push gs
        mov eax,[p] ;put the adress of the struct of CURRENT PROCESS in eax.(the CONTENT of pointer p)
        mov [eax],esp ;save esp in the location of esp in the CURRENT PROCESS-STRUCT.
        lea eax,[kstackend] ; switch to the kernel's own stack.
        mov esp,eax
        %endmacro

        %macro REG_RESTORE_MASTER 0
        mov eax,[p] ;put adress of struct of current process in eax.
        mov esp,[eax] ;restore adress of esp.
        mov ebx,[eax+8];put content of the k-stack field into ebx.
        mov [sys_tss+4],ebx ;update system tss.
        mov al,0x20
        out 0x20,al
        pop gs
        pop fs
        pop es
        pop ds
        popad
        iretd
        %endmacro

 ;and here is an example isr.
 [EXTERN timer_handler]
 [GLOBAL hwint00]
        hwint00:
          REG_SAVE
          call timer_handler
          REG_RESTORE_MASTER

As the comments should show:

• You take the current process' structure, put its adress into eax, and access/update the corresponding fields: esp is the actual esp - it is on the structs first position, so no offset is needed. For the other fields you have to add the offset to the adress in eax.
• You also have to update the esp0 field in the system tss.
• This done, you tell the cpu, where the kernelstack for the process it has to run next is located.
• Upon interrupt, it takes this adress as its esp and every other popping/pushing is done on this stack. After having pushed all the relevant hardware states on the kernel-stack of the process, you have to save the position of esp after the last popped register into the structures esp-field.
• Upon leaving the isr, it takes the new ESP value from the current-process-structure, replaces the value in the esp0 field of the tss with the adress of the top of the new kstack, and then pops off all the registers and returns to the process. If it is a user-process, the two last items popped off upon iret are user-stack-segment and user-stack.

It is really not that difficult to get started, this stack based task switching. But of course, you have to fill in the kstack of a new process with the proper values for it starts off with exactly what is located on the kstack to be popped off, when the process is first scheduled for execution.
Why do you need to fill in the esp0 field of the tss at every task switch: It is mainly because a user process which runs at dpl3 (User Level), can enter kernel space (=dpl0 - system level) by issuing an interrupt or accessing a call gate. I 'd rather prefer the software interrupt approach. The thing looks like this:

• intXX:Dpl3->Dpl0 - cpu switches to stack indicated in tss.esp0.
• iret: dpl0->dpl3 - cpu pops off register values before iret.
  iret itself restores eflags,cs,eip,userstack segment,user stack adress.

These userspace-kernelspace-userspace transitions happen at every interrupt - be it software be it hardware interrupt.
So, lets have a look on how to fill in at least the process structure and the kstack.

prozess_t *task_anlegen(entry_t entry,int priority){
        //various initialization stuff may be done before reaching the below described operations.

        //filling in the kstack for start up:
        uint_t *stacksetup; //temporary pointer - will be set to the
                          //kstacktop and afterwards saved in esp of proc structure.

      ...
        stacksetup=&kstacks[d][KSTACKTOP];
        *stacksetup--;
        *stacksetup--=0x0202;
        *stacksetup--=0x08;
        *stacksetup--=(uint_t)entry; //This is the adress of the process' entry point (z.b. main());
        *stacksetup--=0;    //ebp
        *stacksetup--=0;    //esp
        *stacksetup--=0;    //edi
        *stacksetup--=0;    //esi
        *stacksetup--=0;    //edx
        *stacksetup--=0;    //ecx
        *stacksetup--=0;    //ebx
        *stacksetup--=0;    //eax
        *stacksetup--=0x10; //ds
        *stacksetup--=0x10; //es
        *stacksetup--=0x10; //fs
        *stacksetup=  0x10; //gs

 //filling in the struct.
        processes[f].prozess_esp=(uint_t)stacksetup;
        processes[f].prozess_ss=0x10;
        processes[f].prozess_kstack=(uint_t)&kstacks[d][KSTACKTOP];
        processes[f].prozess_ustack=(uint_t)&stacks[d][USTACKTOP];

You put the Values onto the kstack in the order in which they would be pushed onto the it by an isr. the last position of stacksetup, you stuff into the esp field. This is a really straight forward thing.
The Entry point of your process is the adress of the process' main function. This is the adress to which eip is set upon iret to this process after it's ben scheduled for it's first execution.
Now, I'll show you a little example of scheduling to round it off a little. Basically, this scheduler just moves the processes around in the queue in round robin manner. Also I'll show a little isr.

//global pointer to current task:
      prozess_t *p;

      //the isr:
      void timer_handler(void){
        if(task_to_bill->prozess_timetorun>0){
   task_to_bill->prozess_timetorun--;
          if(task_to_bill->prozess_timetorunprozess_timetorunprozess_timetorun=10;//refill timeslice.
   //remove process from the head of the queue.
          proz=remove_first_element_from_queue(&roundrobin_prozesse,0);
   //put the element to the rear of the queue.
          add_element_to_queue_rear(&roundrobin_prozesse,proz);
        }
 //pick the process at the head of any queue. (f. ex. round robin queue)
 //and put it in p.
        choose_prozess(irq);
      }

So, it fits together: At each timer interrupt, the current process p's state is saved. then, the isr decrements the process timeslice by one. If there isn't any timeslice left, the process is put to the end of the queue by the scheduler and the next one is to be started: it is then located in p from where the isr-stub takes the relevant values and restores the process' state - and starts/restarts it.
You have to keep in mind at any time, that the operating system is event driven. Interrupts are events, as well as system calls. the operating system reacts to them and carries out the requested operations or methods necessary to satisfy devices which have triggered an event.You can also perform task switches upon receipt of an event (irq/software int/exception).
Below, you'll find some definitions.
convenient definitions:

typedef uchar_t  unsigned char;  // -->Length: 8 bit
      typedef ushort_t unsigned short; // -->Length: 16 bit
      typedef uint_t   unsigned int;   // -->Length: 32 bit
      typedef ulong_t  unsigned long;  // -->Length: 64 bit
      typedef void (*entry_t)(void);

And remember: Keep it simple!