AOS - 27 - KERNEL TASK MANAGEMENT VI

• DECLARE_MUTEX(): declares struct semaphor.

  DECLARE_MUTEX(name);
  

• sema_init(): alternative to DECLARE_MUTEX to declare semaphor

   void sema_init(struct semaphore *sem, int val);
  

• down(): try to take a token from the semaphore. If there's no token, go to sleep.

   int down(struct semaphore *sem);
  

• down_interruptible(): try to take a token from the semaphore. If there's no token available, go to an interruptible sleep, which means that we can be awaken by external interrupts.

  int down_interruptible(struct semaphore *sem);
  

• down_trylock(): returns 0 if succeeded. If there is no token does not go to sleep.

  int down_trylock(struct semaphore *sem);
  

• up(): give back token to semaphore, thus possibly waking other threads awaiting their token.

  void up(struct semaphore *sem);
  

Quando lavoriamo modalità kernel dobbiamo stare attenti nell'utilizzo degli spinlock rispetto all'utilizzo lato applicativo. Infatti, mentre gli spinlock lato applicativo permettono solo di ottenere e rilasciare il lock sulla relativa porzione di memoria, lato kernel gli spinlocks possono anche interagire con lo stato del processore.

Per inizializzare uno spinlock possiamo utilizzare le seguenti macro, definite in <linux/spinlock.h> .

spinlock_t m_lock = SPINLOCK_UNLOCKED;
spin_lock_init(spinlock_t *lock);

• Locking API (blocking):

  • spin_lock():

    spin_lock(spinlock_t *lock);
    

  • spin_lock_irq(): takes a lock and makes the processor uninterruptible, which means that it should ingore all maskable interrupts for a time. In order to use this API we must know the state of the CPU we're running on, i.e. if its interruptible or not, in order to restore the CPU to its original state once we remove the lock.

    spin_lock_irq(spinlock_t *lock);
    

  • spin_lock_irqsave(): takes a lock and makes the processor uninterruptible, which means that it should ingore all maskable interrupts for a time. We use the flags parameter to know the CPU-state before taking the spin-lock and thus possibly changing it. We are able to pass the value of flags and obtain the actual CPU-state on it later because this API is actually a macro.

    spin_lock_irqsave(spinlock_t *lock, unsigned long flags);
    

  • spin_lock_bh():

    spin_lock_bh(spinlock_t *lock);
    

• Locking API (non-blocking):

  • spin_is_locked():

    spin_is_locked(spinlock_t *lock);
    

  • spin_try_lock():

    spin_try_lock(spinlock_t *lock);
    

• Unlocking API:

  • spin_unlock():

    spin_unlock(spinlock_t *lock);
    

  • spin_unlock_irqrestore(): remove the lock and restores the CPU-state using the param flags.

    spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags);
    

  • spin_unlock_irq(): remove the lock and possibly changes the CPU-state. This must be used when we already know the CPU-state.

    spin_unlock_irq(spinlock_t *lock);
    

  • spin_unlock_bh():

    spin_unlock_bh(spinlock_t *lock);
    

  • spin_unlock_wait():

    spin_unlock_wait(spinlock_t *lock);
    

Il kernel offre anche dei meccanismi di sincronizzazione che permettono di avere readers concorrenti e writers esclusivi all'interno di sezioni critiche.

Queste API comunque non implementano un meccanismo RCU.

rwlock_t xxx_lock = __RW_LOCK_UNLOCKED(xxx_lock);
unsigned long flags;

read_lock_irqsave(&xxx_lock, flags);
// ...
// critical section that only reads the info
//
// here multiple readers can enter, but not the writer
// ...
read_unlock_irqrestore(&xxx_lock, flags);

write_lock_irqsave(&xxx_lock, flags);
// ...
// read and write exclusive access to the info
//
// here only a single writer can enter
// ...
write_unlock_irqrestore(&xxx_lock, flags);

In tutte le versioni dello schedule, l'idea è sempre quella di assegnare ad ogni thread un numero di ticks, che vengono poi consumati con l'utilizzo della risorsa CPU da parte del thread. Quando un thread termina i suoi ticks, in determinati punti della sua esecuzione va a chiamare la funzione scheduler() per mandare un altro thread in esecuzione.

L'assegnazione dei ticks ai thread viene effettuato in base al concetto di epoca. All'inizio di epoca lo scheduler assegna ad ogni thread un numero di ticks. L'epoca finisce nel momento in cui tutti i thread che si trovano sulla runqueue hanno speso completamente i loro ticks. Al termine di una epoca ne inizia subito un'altra.

Durante una epoca i thread che si trovano nelle waitqueues potrebbero avere dei ticks da spendere. Quando l'epoca finisce, i nuovi ticks assegnati ai thread che si trovano sulla wait-queues devono prendenre in considerazione i ticks rimanenti nell'epoca precedente. Se così non fosse infatti potrei essere unfair per i thread bloccati sulle waitqueues.

La quantità di ticks assegnata ad un dato thread dipende anche dalla priorità del thread stesso.

Le priorità utilizzate nel Perfect Load Sharing erano allineate a quelle definite dallo standard POSIX classico, ovvero il seguente:

<--- higher priority
-20, -19, -18, ..., 0, ...., +18, +19, +20

Abbiamo \(40\) livelli di priorità, in cui \(-20\) è il livello di priorità maggiore, e \(+20\) è il livello di priorità minore. Lo \(0\) è il livello di priorità di default.

Questa priorità è legata al concetto di niceness nei sistemi linux classici. Più è alta la niceness e più favorisco gli altri nell'utilizzo della CPU. La niceness può essere cambiata utilizzando delle system call. Per migliorare la niceness devo girare da root.

La funzione schedule() è scritta utilizzando le seguenti facilities messe a disposizione dal kernel LINUX.

• list_for_each(): Scans a circular list through a cusors. It assumes the element of the list have the field next

  #define list_for_each(pos, head)                                \
    for(pos = (head)->next; pos != (head); pos = pos->next)
  

• list_entry(): Used when we embedd the elements of a list inside a wrapper structure. Given the element of the list, this macro returns the address of the container structure.

  #define list_entry(ptr, type, member)           \
    container_of(ptr, type, member)
  

Graficamente abbiamo

L'esecuzione della funzione schedule() può essere suddivisa in tre fasi distinte, che sono:

1. Controlla lo stato del thread corrente: viene eseguito per capire se dobbiamo necessariamente fermare il thread corrente e toglierlo dalla runqueue.

   // ...
   struct task_struct *prev = current;
   // ...
   
   switch(prev->state) {
   
    case TASK_INTERRUPTIBLE:
      // If there were any signals sent to the thread, do not remove the
      // thread from the run-queue.
      if(signal_pending(prev)) {
        prev->state = TASK_RUNNING;
        break;
      }
   
    default:
      // Remove the TCB of the currently executing thead from the
      // run-queue.
      del_from_runqueue(prev);
   
    case TASK_RUNNING:;
      // Do nothing
    }
   
   // Already executing schedule() call, no need to do it again.
   prev->need_resched = 0;
   

1. Analisi dello stato della unique-runqueue: eseguita per andare a selezionare il prossimo thread da mandare in esecuzione. L'affinità è presa in considerazione. In particolare, per ogni TCB presente nella run-queue è calcolato un valore che prende il nome di goodness value. Il thread con il TCB associato al migliore goodness value è quello viene scelto dallo scheduler. Il valore della goodness è calcolato utilizzando varie informazioni, tra cui la memory view del thread che sta lasciando la CPU.

   repeat_schedule:
   
   next = idle_task(this_cpu); // idle process
   c    = -1000;               // initial best goodness value
   
   list_for_each(tmp, &runqueue_head) {
     p = list_entry(tmp, struct task_struct, run_list);
   
     if(can_schedule(p, this_cpu)) {
       // compute goodness using various info, 
       //
       // see *goodness computation*
       int weight = goodness(p, this_cpu, prev->active_mm);
   
       if(weight > c)
         // update best goodness value so far
         c = weight, next = p;
     }
   }
   

2. Context switch: per iniziare ad eseguire il thread scelto.

Quando tutti i thread presenti nella runqueue terminano i loro ticks (p->counter = 0, for all p in runqueue), lo scheduler riassegna a ciascun thread attivo (sia nelle runqueue e sia nelle waitqueues) un determinato numero di ticks.

La formula utilizza per ri-assegnare il numero di ticks è la seguente:

p->counter = p->counter / 2 + 6 - p->nice / 4      

Il codice che si occupa di fare questo è il seguente

// ...

// Do we need to re-calculate counters?
if(unlikely(!c)) {
  struct task_struct *p;

  spin_unlock_irq(&runqueue_lock);
  read_lock(&tasklist_lock);

  for_each_task(p)
    p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);

  read_unlock(&tasklist_lock);
  spin_lock_irq(&runqueue_lock);

  goto repeat_schedule;
 }

// ...

Notiamo che per il ricalcolo dei ticks non possiamo utilizzare solamente le wait queues, in quanto noi stessi possiamo definire delle wait queues senza dirlo al kernel. Per non complicare la registrazione di eventuali wait queues, per il ricalcolo dei ticks si utilizza il namespace ancestrale in cui si trovano tutti i thread.

Il perfect load sharing scheduler ha le seguenti caratteristiche:

• Una task settata a NON-RUNNABLE viene comunque cercata per calcolare la sua goodness

• I runnable e non-runnable task vengono inseriti in una singola run-queue in ogni data epoca.

• In sistemi SMP/multi-core abbiamo delle possibili performance negative in caso di chiamate successive alla funzione schedule() in caso di heavy system load. Infatti se un CPU-core ha chiamato schedule() , gli altri CPU-cores non possono entrare in schedule() , e sono quindi costretti a fare busy-waiting.

Nel load balancing non abbiamo una mistura tra runnable e non-runnable tasks all'interno della stessa runqueue. Abbiamo quindi una chiara separazione dei runnable tasks su multiple run queues. In questo schema abbiamo quindi una runqueue per CPU-core. Ciascun CPU-core accede alla propria runqueue quando esegue la logica dello scheduler. Eventualmente è possibile che un CPU-core accedere alla runqueue di un altro CPU-core. L'evento di cross-runqueue-access succede nei seguenti casi:

• Il thread da mandare in esecuzione ha una una elevata affinità con un altro CPU-core.

• Il carico del CPU-core corrente è troppo alto, e quindi una CPU che ha poco carico, oppure un demone che girà su una qualche CPU, sposta il carico per cercare di ribilanciare il carico di lavoro sui vari CPU cores.

Il lavoro di ribilanciamento viene effettuato andando a guardare i metadati memorizzati nella head della runqueue per ogni CPU-core.

Un'altra caratteristica di questo scheduler è il fatto che le priorità non sono ottenute andando a guardare all'interno dei TCBs, ma sono conosciute a priori in base alla runqueue in cui quel TCB si trova. Non dobbiamo quindi scorrere la lista per calcolare il thread con la priorità maggiore.

Nell'implementazione linux (kernel >= 2.6) del Load Balancing schedule abbiamo 140 livelli di priorità. A ciascun livello corrisponde una particolare runqueue. La priorità associata ai TCB è quindi assegnata in base al particolare livello in cui vengono inseriti. I 140 livello di priorità sono divisi nel seguente modo:

• I 40 livelli dal 100 al 139 vengono mappati ai classici livelli di priorità UNIX-like.

• I 100 livelli dal 0 al 99 vengono mappati a priorità di livello real-time.

Graficamente,

Per ogni livello in realtà abbiamo due runqueues: una attiva, in cui ci sono i thread da eseguire, e una expired, che contiene i thread che hanno utilizzato i loro ticks. Quando tutti i thread passano dalla active queue alla expired queue, i puntatori delle queue vengono scambiati e si ricomincia da capo.

Quando chiamiamo la funzione wake_up_process() si verifica se l'affinità del thread che stiamo svegliando è compatibile con il CPU-core in cui sta eseguendo. Se la verifica risulta essere positiva, il thread viene messo nella run-queue del CPU-core locale. Se invece la verifica fallisce, è possibile utilizzare la funzione

   void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)

che permette di specificare che si vuole svegliare un thread in modo tale da inserire il relativo TCB nella runqueue associata ad uno specifico CPU-core. In questi casi, dopo aver inserito il TCB di un thread nella run-queue di un altro CPU-core, la CPU che ha inserito il TCB invia un interrupt alla CPU a cui è associata la runqueue in cui è stato inserito il TCB. Quest'ultima esegue un top-half minimale e flagga il thread per andare in pre-emption. Quando il thread prende il controllo, verifica se può andare in pre-emption e chiama la funzione dello scheduler. Così facendo è possibile passare il controllo ad un processo più prioritario.

Nel Load Balancing l'assegnazione dei ticks ai threads è effettuata sulla nozione di "load", ovvero di carico di lavoro.L'informazione sulla load è contenuta in un field all'interno della TCB, ed è strutturato nel seguente modo

struct sched_entity {
  struct load_weight load;
};

struct load_weight {
  // value assigned on the basis of the niceness.
  // used in the calculation of ticks to spend.
  unsigned long weight; 
  u32 inv_weight;
};

// see slides pg 148
static const int prio_to_weight[40];

Un thread non-real-time è caratterizzato da due valori di priorità:

• Priorità statica: Definita dagli utenti (associata alla niceness), indica il livello iniziale in cui il thread apparirà nella runqeueu.

• Priorità dinamica: Viene calcolata utilizzando dei meccanismi di reward o penalty sul valore di base della priorità statica. Essenzialmente più un thread è I/O bound, e più la sua priorità dinamica è alta.

Per i thread real-time invece esiste solo la priorità statica, e quindi il comportamento dei thread real-time non va ad influire nel tempo sul loro livello di priorità.

Il valore che viene visto dallo scheduler() è la priorità dinamica per i thread non-real-time e quella statica per i thread real-time.

L'effetto delle priorità dinamica è che, può succedere, che dati due thread A e B, con A avente priorità statica maggiore di B, può succedere che la priorità dinamica di B diventi più grande di quella di A, e quindi che lo scheduler scelga B al posto di A. Questo fatto poi diventa grave nel momento in cui B tenta di aumentare la sua priorità dinamica fingendo di essere I/O bound, o comunque andando a dormire per un determinato tempo.

Le priorità dinamiche presenti nel Load Balancing ci permettono di implementare dei meccanismi di feedback, in cui i tick assegnati ad un thread dipendono dal comportamento passato del thread stesso. In particolare più un thread è I/O-bound, e più ha una priorità dinamica maggiore.

Il numero di ticks residui per un thread nell'epoca corrente è dato dalla variabile p->time-slice . I kernel offre poi le seguenti APIs per interagire con lo scheduler

• schedule(): Main scheduler function. Schedules highest priority task for execution.

• load_balance(): Check the CPU to see wheter an imbalance exists, and, if so, attempts to move tasks between CPU-cores.

• effective_prio(): Returns effective priority, that is, the dynamic priority based on the static one + eventual rewards/penalties

• recalc_task_prio(): Determines a task's bonus or penalty based on its idle time.

• source_load(): Calculate load of source CPU from which a task could be migrated.

• target_load(): Calculate load of target CPU where a task can be migrated to other CPUs.

Lavorando con delle runqueues che sono specifiche per i vari CPU cores può succedere che un thread chiama la funzione schedule() e viene de-schedulata. Ad un certo punto poi la funzione riprende il controllo. Nel frattempo però potrebbe aver cambiato CPU-core. Abbiamo quindi un thread che esegue una funzione, la funzione schedule() , cross-cpu-cores. Dato che queste funzioni possono avere delle variabili locali identificate dall'ID del CPU-core in cui stiamo eseguendo, dobbiamo stare attenti a come gestiamo il context-switch durante l'esecuzione di una funzione.

Per risolvere questa problematica il programmatore di sistema deve essere aware di questa problematica e deve utilizzare delle specifiche facility per effettuare lo stack refresh esplicito. In particolare le variabili locali vengono esplicitamente ripopolate nella stack dopo che si cambia lo stack per eseguire il nuovo thread nella nuova CPU.

// ...
cpu = smp_processor_id();
rq = cpu_rq(cpu);
rcu_qsctr_inc(cpu);
prev = rq->curr;

// ...

/* the context switch might have flipped the stack from under
   us, hence refresh the local variables. */
cpu = smp_processor_id();
rq = cpu_rq(cpu);

// ...

La runqueue ha la seguente struttura

strut rq {
  // runqueue lock
  spinlock-t lock;

  // nr_running and cpu_load should be in the same cacheline because
  // remote CPUs use both these fields when doing load calculation.
  unsigned long nr_running;
#define CPU_LOAD_IDX_MAX 5
  unsigned long cpu_load[CPU-LOAD_IDX_MAX};

  //...

  struct task_struct *curr, *idle;

  //...

  struct mm_struct *prev_mm;

  //...
};