Preemptivity: how to take away the processor

This article does not make sense without the previous one, which described the main mechanisms for switching contexts in a multitasking OS .

Here I will tell how cooperative multitasking turns into hostile preamptive.

The essence of this transformation is simple. The machine has a timer, the timer generates interrupts, interrupts suspend the thread code and put the processor in the hands of a multitasking mechanism. It is already quite cooperatively switching the processor to a new thread, as described in the previous article .
')
But, as usual, there are nuances. See the code for intel .

The processor weaning itself is done as part of a normal hardware interrupt, usually by timer and as part of a software interrupt, which is actually the same interrupt, but caused by a special processor instruction. This method of context switching is needed if we (for example, within the synchronization primitive) explicitly stop the thread and don’t want to wait for the timer interrupt to arrive.

Firstly, before weaning on the processor from the poor threads, you need to serve the interrupt itself. The interrupt processor / controller “knows” that the interrupt has begun and needs to be “reassured” by saying that we have completed the service before we switched to another thread. Otherwise, the state of the interrupt controller may be very strange and the system will cease to function intelligibly. And the interrupt handler itself will not be happy if other threads are running for a couple of seconds before it is executed.

Therefore, we first serve the interrupt itself. Then we make sure that it was not nested - that we did not interrupt the service of another interrupt, which should also be completed.

And now, while we are still inside the interrupt service function, but the interrupts themselves have serviced and properly notified the interrupt controller about this (and, of course, the interrupts themselves are globally forbidden), we can check if there is a soft irq request, and if so - serve him.

Here we must understand that in the high-order bits of the variable irq_nest lies the flag of prohibiting the maintenance of software interrupts and the flag of the absence of a request for a software interrupt. That is, if it is zero, then, at the same time, the nesting of requests for hardware interrupts is zero, there is no prohibition on a software interrupt and there is a request for a software interrupt.

if(irq_nest) return; // Now for soft IRQs irq_nest = SOFT_IRQ_DISABLED|SOFT_IRQ_NOT_PENDING; hal_softirq_dispatcher(ts); ENABLE_SOFT_IRQ(); 

Naturally, while we are servicing a software interrupt, the software interrupts themselves are prohibited. At the end of the service we will resolve them again. But - see the previous article - if the current thread is removed from the processor, then we will again allow software interrupts - otherwise the thread to which we switch will never switch back. After all, you need to perform a software interrupt. I hope I did not confuse you.

During thread initialization, the kernel registers a software interrupt handler.

  hal_set_softirq_handler( SOFT_IRQ_THREADS, (void *)phantom_scheduler_soft_interrupt, 0 ); 

This handler, apart from any checks, comes down to calling phantom_thread_switch (), that is, it simply leads to switching to the next thread.

There are two things left. The first is how to explicitly “give away” the processor. For example, when we try to capture an already locked mutex, the thread must be stopped.

To do this, we coax the software interrupt request and request (any, but better - rarely used) hardware interrupt.

 void phantom_scheduler_request_soft_irq() { hal_request_softirq(SOFT_IRQ_THREADS); __asm __volatile("int $15"); } 

As mentioned above, this will cause the phantom_thread_switch function to be called from the software interrupt context.

Secondly: who will request a software interrupt to complete the thread currently running at the end of the allocated processor time slot?

For this there is such a request:

 void phantom_scheduler_schedule_soft_irq() { hal_request_softirq(SOFT_IRQ_THREADS); } 

He is executed here when. Inside a timer interrupt, a special function is called:

 // Called from timer interrupt 100 times per sec. void phantom_scheduler_time_interrupt(void) { if(GET_CURRENT_THREAD()->priority & THREAD_PRIO_MOD_REALTIME) return; // Realtime thread will run until it blocks or reschedule requested if( (GET_CURRENT_THREAD()->ticks_left--) <= 0 ) phantom_scheduler_request_reschedule(); } 

As it is easy to see, it decrements the ticks_left thread variable, and if it counts to zero, it requests thread switching.

The variable ticks_left is set by the scheduler when it selects a thread to start - it writes the number of 10 ms intervals into this variable that the thread will work (if it doesn’t want to stop by itself).

The running time of the sheduler can set a fixed (by serving priorities through the frequency of filing the thread on the processor) or take into account the priority (giving higher priority threads longer intervals).

To this we must add that phantom_scheduler_request_reschedule () can be called by anyone who has decided that it is time to decide who should get onto the processor now.

As an example, this may be appropriate if the current thread unlocks the synchronization primitive on which the thread was blocked with a high (especially realtime) priority.

By itself, this call only sets the flag - the real switching will only be at the end of the interrupt service, as described above.

For completeness, consider the structure of the description of the thread (struct phantom_thread) in detail.

The cpu field contains architecture-specific fields in which the processor state is saved when the thread is stopped. cpu_id is the number of the processor on which the thread was last launched or is running now. tid is just a thread id. owner is used by the phantom object environment to bind an object describing a thread at the application level here. If the thread services the Unix compatibility subsystem - pid stores the number of the Unix process to which the thread belongs. The name is for debugging only.

  /** NB! Exactly first! Accessed from asm. */ cpu_state_save_t cpu; //! on which CPU this thread is dispatched now int cpu_id; int tid; //! phantom thread ref, etc void * owner; //! if this thread runs Unix simulation process - here is it pid_t pid; const char * name; 

ctty - stdin buffer for the thread, used for communication with the graphics subsystem. stack / kstack is the virtual and physical address of the stack segment, respectively for user and kernel mode. start_func and start_func_arg - the entry point to the function ("main") of the thread and the argument of this function.

  wtty_t * ctty; void * stack; physaddr_t stack_pa; size_t stack_size; void * kstack; physaddr_t kstack_pa; size_t kstack_size; void * kstack_top; // What to load to ESP void * start_func_arg; void (*start_func)(void *); 

sleep_flags are signs of a thread falling asleep for one reason or another. If it is not zero, the thread cannot be started (waiting for a mutex, timer, not born, died, etc.). thread_flags - various signs of the thread: the thread serves the Phantom virtual machine, the thread had a timeout of the synchronization primitive, etc.

waitcond / mutex / sem - the thread is sleeping on this primitive, waiting for its release. ownmutex - this thread has locked this mutex; if it dies, it must be released. (For a semaphore, everything, alas, is not obvious.)

sleep_event - used if the synchronization primitive is locked with a timeout - the timer subsystem of the kernel stores the state of the timer request here.

chain - used when placing a thread in the queue if several threads wait for one synchronization primitive.

kill_chain - turn on the scaffold. A special system thread deals with the post-mortem deinitialization of other threads (release of memory, unlocking mutexes, etc.), and this is the line for it.

  u_int32_t thread_flags; // THREAD_FLAG_xxx /** if this field is zero, thread is ok to run. */ u_int32_t sleep_flags; //THREAD_SLEEP_xxx hal_cond_t * waitcond; hal_mutex_t * waitmutex; hal_mutex_t * ownmutex; hal_sem_t * waitsem; queue_chain_t chain; // used by mutex/cond code to chain waiting threads queue_chain_t kill_chain; // used kill code to chain threads to kill //* Used to wake with timer, see hal_sleep_msec timedcall_t sleep_event; 

snap_lock - the thread is in a state in which you cannot take a snapshot.

preemption_disabled - the thread cannot be removed from the processor. In fact, there is almost no sense in this thing, especially in the SMP environment.

death_handler - will be called if the thread has died. atexit.

trap_handler is an analogue of what is called signals in user mode - the function is called if the thread has led to the processor.

  int snap_lock; // nonzero = can't begin a snapshot int preemption_disabled; //! void (*handler)( phantom_thread_t * ) void * death_handler; // func to call if thread is killed //! Func to call on trap (a la unix signals), returns nonzero if can't handle int (*trap_handler)( int sig_no, struct trap_state *ts ); 

The rest is sheduler's machinery. Everything is simple:

priority contains the thread priority (along with the class realtime, normal, idle)

ticks_left - how many “ticks” (10 ms intervals) the thread will work on the processor

runq_chain - if the thread is ready for execution, but not executed, then it is present in the queue for execution.

sw_unlock - contains a pointer to the spinlock, which will be unlocked after removing the thread from the processor, used in the implementation of synchronization primitives.

  u_int32_t priority; /** * How many (100HZ) ticks this thread can be on CPU before resched. * NB! Signed, so that underrun is not a problem. **/ int32_t ticks_left; /** Used by runq only. Is not 0 if on runq. */ queue_chain_t runq_chain; /** Will be unlocked just after this thread is switched off CPU */ hal_spinlock_t *sw_unlock; 

The last bow to add to the picture of the world: there is always a thread in the system (several threads, according to the number of processors), which is placed on the processor, if the scheduler does not find any decent thread work.

This thread does nothing - it executes a processor instruction that stops the processor before receiving an interrupt, and counts the execution time itself. The time of its execution per second allows you to get the percentage of CPU usage, and stopping the processor saves electricity and heat.

Phew Probably for today - everything. Continued here .