We do multitasking

I try to alternate articles about OS development in general and OS-specific articles. This article is a general plan. Although, of course, I will give examples from the Phantom code.



In principle, the implementation of the multitasking mechanism itself is a fairly simple thing. By her own. But, firstly, there are subtleties, and secondly, it must cooperate with some other subsystems. For example, the same implementation of synchronization primitives is very closely related to the implementation of multitasking. There is also an unbanal connection with the subsystem of servicing interrupts and exceptions. But more about that later.



To begin with, there are two fairly few related modules - the actual task switching subsystem (context) subsystem and the scheduling subsystem. We will hardly discuss the second one today, just describe briefly.

')

Sheduler is a function that answers the question "which thread to give the processor right now." Everything. The simplest sheduler simply goes through all the threads (but, of course, ready for execution, not stopped) in a circle (RR algorithm). The real sheduler takes into account priorities, the behavior of the thread (interactive get more than the computational), affinity (on which processor the thread worked last time), etc., while being able to combine several classes of priorities. Typically, this is a real-time class (if there is at least one thread of this class - it works), a time-sharing class and an idle class (it gets the processor only if the two previous classes are empty, that is, there are no threads ready for execution).



On this for now about the sheduler finish.



Let us turn to the actual subsystem, which is able to take away the processor from one thread and give it to another.



Again, let's start with a simple one. Multitasking is cooperative and preamptive.



Cooperative is extremely simple - every thread from time to time honestly and deliberately "gives" the processor, calling the yield () function.



In reality, it is rarely used, but cooperative is at the heart of every pre-emptive multitasking. Strictly speaking, all pre-emptive multitasking is reduced to using a timer interrupt to take away the processor from the user thread and then quite cooperatively, "hands", switch to another thread.



The very same cooperative multitasking is based on only one function. The function that all threads called at the same time.



In this place it is necessary to ponder a little bit. This is true: from the point of view of all the threads of the system except the one that is now working (for simplicity, consider the single-processor system), they all called the context switching function and were suspended in it. In the middle of it. The working thread (itself, or by force through an interrupt) will also call this function when the time comes to “give up” the processor. This call will cause the calling thread to stop, and the context switch function will return to another thread. (The one chosen by the sheduler).



A little later, we will look at the entire context switch code, but now it’s the very core, actually switching between threads.



Reference to the implementation for Intel 32 bit



I cleaned the code a bit for simplicity:



// called and returns with interrupts disabled

/* void phantom_switch_context(

phantom_thread_t *from,

phantom_thread_t *to,

int *unlock );

*/

ENTRY(phantom_switch_context)



movl 4(%esp),%eax // sw from (store to)



movl (%esp),%ecx // IP

movl %ecx, CSTATE_EIP(%eax)

movl %ebp, CSTATE_EBP(%eax)



// we saved ebp, can use it.

movl %esp, %ebp

// params are on bp now



pushl %ebx

pushl %edi

pushl %esi

movl %cr2, %esi

pushl %esi



movl %esp, CSTATE_ESP(%eax)



// saved ok, now load



movl 8(%ebp),%eax // sw to (load from)



movl CSTATE_ESP(%eax), %esp



popl %esi

movl %esi, %cr2

popl %esi

popl %edi

popl %ebx



movl CSTATE_EIP(%eax), %ecx

movl %ecx, (%esp) // IP



// now move original params ptr to ecx, as we will use and restore ebp

movl %ebp, %ecx



movl CSTATE_EBP(%eax), %ebp



// Done, unlock the spinlock given



movl 12(%ecx),%ecx // Lock ptr

pushl %ecx

call EXT(hal_spin_unlock)

popl %ecx



// now we have in eax (which is int ret val) old lock value



ret





The function takes three arguments - from which thread we switch to which thread we switch to, which spinlock to unlock after switching.



Its meaning is extremely simple. We add all (important) state of the processor onto the stack, then we write the position of the stack pointer in a special structure field that describes the current thread. Then we take out the position of the stack pointer from the structure for the new thread, restore the stack pointer and remove the processor state of the new thread from the stack. Everything, after that, the function will return to the new thread.



Before that, we will heat the spinlock that the previous thread passed to us - as we can see, we will heat it strictly after the switch, that is, when the old thread is already stopped - this is important for the implementation of synchronization primitives and for supporting multiprocessing. (If we unlock the spinlock before switching, another processor may try to activate the thread, which we have not yet fully deactivated.)



What we have considered is the very heart of the implementation. But this function is not directly called (it generally implements only the architecture-dependent part of the code), but it is called from the phantom_thread_switch () wrapper.



See code phantom_thread_switch ().



What happens in the wrapper. Let's go in steps.



Let us make sure that we are not in the context of an interrupt (interruptions cannot be suspended, the integrity of the processor's hardware state is violated) and that the thread subsystem is generally activated. We prohibit guaranteed interrupts. This is what we really do not need now.

  assert_not_interrupt(); assert(threads_inited); int ie = hal_save_cli(); 

Let's lock the common context switch spinlock. In fact, it could be done per CPU, but for peace of mind, there is only one context switch at a time. We remove from the structure of the description of the thread a link to the spinlock, which must be unlocked after the switch - it was passed to us by the synchronization primitive. Zero the link inside the structure so that the spinlock is not unlocked again.

  hal_spin_lock(&schedlock); toUnlock = GET_CURRENT_THREAD()->sw_unlock; GET_CURRENT_THREAD()->sw_unlock = 0; 

We will take the last “tick” from the current thread - the interval of work on the processor planned for it. This is for the sheduler, so now I will not go into the details. We ask the scheduler, to whom to give the processor. Remember who was the current thread. Let us make sure for the order that the sheduler was not crazy and did not suggest that we run a thread that does not have the right to work (non-zero sleep_flags).

  // Eat rest of tick GET_CURRENT_THREAD()->ticks_left--; phantom_thread_t *next = phantom_scheduler_select_thread_to_run(); phantom_thread_t *old = GET_CURRENT_THREAD(); assert( !next->sleep_flags ); 

In order not to engage in bullshit, we will check if the same thread will have to be started, if the same one - just finish the exercise, noting this event in the statistics.

  if(next == old) { STAT_INC_CNT(STAT_CNT_THREAD_SAME); goto exit; } 

We will remove the new thread from the queue of threads that are ready for execution (it is in it that the scheduler is looking for applicants for staging on the processor). In fact, there are several queues, but these are details - we will remove them from all.



If the old thread is not blocked, then, on the contrary, we will put it in the queue (this is where the global schedlock is useful to us) so that it can claim to be placed on the processor in the future. (If it is locked, the one who unlocks will return it to its queue.)

  t_dequeue_runq(next); if(!old->sleep_flags) t_enqueue_runq(old); 

Then everything is hard. It should be clearly understood that after calling phantom_switch_context we are working in another thread, we have OTHER VALUES of LOCAL VARIABLES . In particular, the next variable, in which the pointer to the handle of the thread that we start is stored, after the start of the thread will contain an invalid value. Therefore, we will correct the global variable that stores knowledge of which thread is currently working before switching, and not after. (Actually, it is also possible afterwards, but from another variable. :)



Next we allow software interrupts before the actual switching, and prohibit them after. This is necessary because it is the pre-emptive context switching that occurs precisely from software interrupts, and a certain protocol for working with them must be guaranteed. I will tell it separately, the moment is really thin.

  // do it before - after we will have stack switched and can't access // correct 'next' SET_CURRENT_THREAD(next); hal_enable_softirq(); phantom_switch_context(old, next, toUnlock ); hal_disable_softirq(); 

Next - remember, all local variables have changed the value. For peace of mind, I do not use them anymore (although, in fact, I could - I just need to understand what they contain), and again I find out “who I am” - which thread is running. Firstly, I tell her on which processor she “woke up”, secondly, the architectural-specific context recovery function is triggered after the switch.

  phantom_thread_t *t = GET_CURRENT_THREAD(); t->cpu_id = GET_CPU_ID(); arch_adjust_after_thread_switch(t); 

For Intel, this specific function restores the configuration of the top of the stack when switching to nuclear mode:

  cpu_tss[ncpu].esp0 = (addr_t)t->kstack_top; 

It is needed if the thread returns to user mode after a context switch - interrupts and system calls from user mode lead to hardware switching of the stack by the processor, and for each thread such a stack is individual, of course.



There are also subtleties that I did not mention. For example, traditionally on Intel, when restoring the state of the processor, the floating point registers and SSE are not restored — instead, they set the flag to prohibit access to them. If the thread code actually tries to use these registers, an exception will occur, which will restore the state of these registers. They are quite weighty, but not very widely used, and this optimization makes sense.



Now about the start of the thread. To create a new thread, you need to be able to ... return from phantom_switch_context ()!



This means that you need to “collect” on the stack of a new thread such a picture that occurs when it is inside phantom_switch_context () at the point where we switched the stack pointer to a new thread. In this case, the return address from phantom_switch_context () must be the address of the function, which, firstly, will do what it does after switching the thread phantom_thread_switch (), secondly, it will finish initializing the thread, and, finally, will call the function that should be executed under the new thread.



In this article, we did not consider the pre-emptivity itself - exactly how the processor is “weaned off” from the old thread, and who calls phantom_thread_switch () when. But this is a separate article .