AOS - 25 - KERNEL TASK MANAGEMENT IV

La struttura del thread control block è definita nel file include/linux/sched.h . I campi più importanti sono riportati a seguire, anche se notiamo che nelle versioni più recenti sono state modificati qualche campi e aggiunti degli altri.

struct task_struct
{

  // Variabile che può essere modificata sia in modo sincrono sia in
  // modo asincrono.
  volatile long state; 

  // Pointer to the memory view of the thread.  
  struct mm_struct *mm; 

  pid_t pid;  // Thread ID

  // Process group, all thread's of a process share the same group. In
  // recent version its called tgid.
  pid_t pgrp; 

  //...


  // Modified by top-half of timer interrupts. Checked by the thread
  // at given conciliation points during execution.
  // 
  // In modern releases this has become
  // a bit inside a bitmask.
  volatile long need_resched;
  
  //...

  // Number of residual LAPIC-T ticks.
  long counter;

  // niceness: higher level means less ticks.  
  long nice;    

  unsigned long policy; 
}

Per gestire un thread necessitiamo di due buffer: un TCB e una stack area livello kernel. A seconda della versione del kernel abbiamo una gestione diversa del TCB.

La macro current è utilizzata per ritornare l'indirizzo di memoria del TCB attualmente in esecuzione sul CPU-core. Questa macro si basa sul fatto che le pagine di memoria del kernel in cui sono collocate le informazioni relative alla TCB sono allineate in memoria tramite il buddy allocator. Dato che il calcolo della macro current dipende dallo stack pointer del thread, un cambiamento di stack pointer porta anche al cambiamento nella risoluzione della macro current.

Il modo in cui viene calcolato l'indirizzo dipende dalla versione del kernel utilizzata:

• kernel <= 2.6 (old style): Si mascherano i primi \(13\) bit per ottenere l'indirizzo iniziale delle pagine allocate, in cui è presente il TCB.

• 2.6 < kernel < 4.9 (new style): Si mascherano i primi 13 bit per ottenere l'indirizzo iniziale delle pagine allocate, in cui è presente la struttura thread_info . Si utilizza il puntatore salvato nel campo task della struttura thread_info per accedere al TCB.

• kernel >= 4.9 (very new style): current non è più una macro ma è un puntatore che punta ad una per-CPU memory. Il puntatore viene aggiornato ogni volta che un CPU-reschedule viene eseguito. In questo modo non necessitiamo di allineare in memoria la stack kernel utilizzata per il thread.

  struct task_struct;
  
  DECLARE_PER_CPU(struct task_struct *, current_task);
  
  static __always_inline struct task_struct *get_current(void) {
    return this_cpu_read_stable(current_task)
      }
  
  #define current get_current()
  

Il campo state della struttura TCB mantiene informazioni sullo stato corrent del processo/thread. I valori del campo state sono definiti in include/linux/sched.h e sono i seguenti

#define TASK_RUNNING           0
#define TASK_INTERRUPTIBLE     1
#define TASK_UNINTERRUPTIBLE   2
#define TASK_ZOMBIE            4

Tutti i TCB che sono memorizzati nella run-queue devono mantenere il valore TASK_RUNNING .

É possibile definire una wait queue tramite la seguente macro, definita in include/linux/wait.h

DECLARE_WAIT_QUEUE_HEAD(queue)

Per utilizazare le wait queues il kernel poi offre le seguenti APIs

• Sleep APIs:

  • interruptible_sleep_on(): The TCB of the calling thread is no more scanned by the scheduler untill it is dequeued or a signal kills the process/thread. Being sleep interruptible means that the TCB can be hit by a signal, and thus can be woken up by a signal.

    void interruptible_sleep_on(wait_queue_head_t *q);
    

  • sleep_on(): In this case we go to sleep and signals are don't care events.

    void sleep_on(wait_queue_head_t *q);
    

  • interruptible_sleep_on_timeout():

    void interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout);
    

  • sleep_on_timeout(): time here is measured in jiffies .

    void sleep_on_timeout(wait_queue_head_t *q, long timeout);
    

• Wake APIs:

  • wake_up(): wake up all process that were sleeping in a given wait-queue

    void wake_up(wait_queue_head_t *q);
    

  • wake_up_interruptible(): wake up all process that were sleeping in a given wait-queue and that were marked as interruptible.

    void wake_up_interruptible(wait_queue_head_t *q);
    

  • wake_up(): wake up a specific thread whose TCB is pointed by p.

    void wake_up(struct task_struct *p);
    

Notiamo che le API per la gestione del wake-up o è poco selettiva, o è estremamente selettiva.

Il thundering herd effect succede quando devo risvegliare tutti i thread che si trovano in una data wait queue solo per farne accedere uno alla risorsa e far bloccare nuovamente tutti gli altri. In questo caso molto tempo della CPU viene investito solo per risvegliare e addormentare i vari thread.

Un esempio documentato di questo effetto è stato studiato da Mindcraft sul comportamento del Web servers.

Le APIs delle waitqueues devono anche preoccuparsi di togliere il TCB dalla runqueue una volta che si è ritornati dalla funzione di schedule().

In particolare abbiamo la seguent dinamica per il linking/unlinking dei TCB nella runqueue e nelle varie waitqueues.

Lo schema che viene implementato dalle wait event queues è il seguente:

Più in dettaglio:

1. Entriamo e facciamo il check della condizione.

2. Se il check è vero ritorniamo subito.

3. Altrimenti ci togliamo dalla run-queue e ci mettiamo a dormire.

4. Ad un certo punto torno sulla run queue. Se sono tornato sulla run queue perché qualcuno mi ha segnalato, allora ritorno.

5. Se non sono stato segnalato, devo verificare se la condizione è verificata.

Notiamo che con questo schema non è possibile perdere dei risvegli.

Supponiamo infatti di trovarci nella seguente situazione: qualcuno cerca di fare una update su una condizione, e poi porta il TCB del thread che sta in wait su quella condizione nella run-queue. É possibile che queste attività possano essere invertite? Ovvero, è possibile che l'update della condizione non sia osservabile quando eseguo la sezione critica che porta il TCB del thread interessato nella run queue?

La risposta a questa domanda è no, non è possibile, in quanto la sezione critica utilizzata delle istruzioni read-modify-and-write che serializzano gli accessi alla memoria.

In questo esempio si implementa un servizio che stampa informazioni sul CPU-core in cui il servizio sta girando e sul numero di context-switch effettuati fino a quel momento.

Per implementare questo servizio dobbiamo associare ad ogni thread dei metadati. Questi metadati devono essere utilizzati da due system calls: una system call che fa il setup dei metadati, e un'altra che gli legge. Abbiamo poi bisogno di inserire una k-prob-ret nello scheduler() .

Il problema fondamentale da risolvere per implementare questo servizio è capire dove andare a memorizzare questi metadati per ogni thread. A tale fine notiamo che non è possibile inserire i dati nel TCB, in quanto il TCB è una struttura molto compatta, e quindi dovrei cambiare la sua definizione e ricompilare il kernel per implementare una soluzione del genere.

L'idea è quella di inserire questi metadati sullo stack del kernel associato al thread, subito dopo la zona associata alla thread_info .

Vogliamo implementare un servizio di sincronizzazione tra thread. In particolare abbiamo dei thread che possono chiamare una sys call per andare a dormire e dei thread che possono chiamare un'altra sys call per risvegliare i thread andati a dormire.

Più thread possono andare a dormire ma solo uno si risveglia quando chiamiamo la apposita system call. Il thread che si risveglia è il thread che è andato a dormire per primo.

Per implementare questo servizio possiamo scegliere due possibili strade:

1. Abbiamo una wait queue condivisa da ogni thread. La chiamata bloccante non fa altro che prendere il riferimento a questa wait queue e accodare il TCB del thread chiamante, mentre la chiamata sbloccante prende il primo elemento della coda e lo sveglia. Questa soluzione però necessita l'allocazione di memoria esterna. Inoltre, chi alloca la wait queue?

2. Utilizziamo sempre la zona di memoria nello stack del thread subito dopo la zona del thread_info. Qui inseriamo una wait queue per ogni thread, e colleghiamo le wait queues tra loro per formare una lista. Abbiamo poi un puntatore condiviso tra tutti i thread che punta all'inizio di questa coda.

   Anche se questa soluzione non richiede l'allocazione di memoria esterna, potrebbe però portare alla perdità degli wake-ups. Queste segue dal fatto che, dopo aver risvegliato un thread tramite la wake_up(), anche se il thread svegliato viene riportato nella run-queue, non sappiamo quando quest'ultimo verrà eseguito, e quindi quando rimuoverà se stesso dalla nostra lista di sleeping threads. Nella concorrenza quindi un altro thread potrebbe effettuare la wake_up(), e, in questo caso, è possibile che trovi la stessa entry di prima.

Andiamo quindi a mostrare una implementazione della seconda soluzione.

Per iniziare definiamo quindi i parametri del modulo

// param to choose if threads can sleep or not
static int enable_sleep = 1;
module_param(enable_sleep,int,0660);

// param to show how many threads are still sleeping 
unsigned long count __attribute__ ((aligned (8)));;
module_param(count,long,0660);

La struct che vogliamo embeddare nella zona del kernel stack del thread invece è la seguente

typedef struct _elem{
  struct task_struct *task;     
  int pid;
  int awake;
  struct _elem * next;
} elem;

Inoltre abbiamo le seguenti variabili globali

elem head = {NULL, -1, -1, NULL};
elem *list = &head;
spinlock_t queue_lock;

Segue quindi una discussione delle due syscall implementate dal modulo.