AOS - 28 - KERNEL TASK MANAGEMENT VII

Lecture Info

  • Data: [2019-11-27 mer]

  • Sito corso: link

  • Slides: AOS - 6 KERNEL TASK MANAGEMENT

  • Progresso unità: 7/7

  • Argomenti:

    • Completely Fair Scheduling

    • Kernel Threads

  • Introduzione: In questa lezione abbiamo concluso la trattazione del task management da parte del kernel.

1 Scheduer #3: Completely Fair Scheduling

Per ovviare i problemi del Load Balancing, che derivavano dalla determinazione delle priorità dinamiche basandosi solamente sul tempo di attesa, dalle versioni del kernel >= 2.6.23, è stato introdotto un nuovo schedule, che prende il nome di Completely Fair Scheduling.

Nel Completely Fair Scheduling non abbiamo più delle runqueues, ma, per ogni livello statico di priorità, i threads vengono invece memorizzati all'interno di un red/black tree. Questo ci permette di ordinare i vari threads in base al VCPU (Virtual CPU) time. Più basso è il VCPU e meglio è.

L'ordine ottenuto utilizzando il red/black tree permette di riflettere le priorità dinamiche dei vari threads con una granularità migliore rispetto alla semplice euristica utilizzata dal Load Balancing basata sul waiting time. In altre parole, con questo schema la priorità dinamica dipende molto più da come utilizzo la CPU.

1.1 Basic Concepts

Teoricamente il completely fair scheduling ci dice che se abbiamo \(N\) thread ugualmente importanti, dovremmo cedere a ciascun thread esattamente \(1/N\) del tempo della CPU all'interno di una finestra di tempo. Negli scenari reali questo risultato teorico non può essere ottenuto in quanto:

  • \(N\) è un valore arbitrariamente grande, ma i sistemi operativi moderni hanno una limitazione sulla granularità di tempo che possono offrire ad un dato thread.

  • Non tutti i thread necessariamente hanno la stessa importanza.

Per cercare di ovviare a queste problematiche si introduce il concetto di Virtual CPU usage (VCPU).

1.2 VCPU Advacement

Il virtual CPU usage di un thread è calcolato normalizzando il tempo reale di esecuzione del thread sulla CPU per un peso associato alla schedulabilità del thread. Il peso contiene informazioni sulla priorità, e quindi, fissato l'utilizzo della CPU reale, più il peso è alto, e più sono importante, e più basso sarà il relativo VCPU usage.

I thread che possono essere eseguiti sono ordinati in un red/black tree utilizzando il valore dela VCPU usage. Per fare questo necessitiamo un costo temporale di O(log(N)).Più basso è il VCPU usage, e prima il thread viene eseguita dalla CPU.

Quando nasce un nuovo thread, si assegna al thread appena creato il minimo VCPU usage presente nel red/black tree, e quindi si assegna a lui la possibilità di partire utilizzando la CPU.

2 Kernel Threads

Abbiamo già visto che utilizzando la funzione pthread_create() per creare dei nuovi thread livello user viene utilizzato il servizio del kernel do_fork() . Come facciamo però a creare un thread livello kernel, e quali sono le differenze tra thread lato user e thread lato kernel?

Per creare un thread livello kernel possiamo utilizzare la funzione kernel_thread() , definita nel file kernel/fork.c . Questa funzione a sua volta utilizza una funzione ASM machine-dependant, chiamata arch_kernel_thread() , definita in arch/i386/kernel/process.c . Quest'ultima funzione alla fine chiama la sys_clone() .

Inizialmente appena i thread kernel andavano subito in esecuzione appena creati. Successivamente sono state introdotte delle API per creare dei thread senza mandarli subito in esecuzione. Una delle differenza fondamentale tra i thread lato user e i thread lato kernel, è che i thread applicativi di default ricevono tutti i segnali, che possono essere poi ignorati tramite apposite system calls. I thread lato kernel invece di default non ricevono nessun segnale.

2.1 arch_kernel_thread()

La funzion arch_kernel_thread() è architecture-dependant perché per capire se siamo il child o il parent nel blocco di codice necessitiamo di controllare lo stato della CPU.

In particolare prima di chiamare l'effettiva creazione del thread la funzione salva l'indirizzo di memoria dello stack del parent, e successivamente confronta lo stack del thread con lo stack salvato. Se gli stack sono uguali, allora sono il parent; se sono diversi sono il child.

2.2 Kernel Thread APIs

Per tirare su un kernel demon è possibile utilizzare le seguenti API

  • kthread_create(): Once created, the thread is sleeping. To actually execute the function we have to wake it up explicitly. 

    struct task_struct *kthread_create(int (*function)(void *data), // Function to execute
                                   void *data,                  // Function param
                                   const char name[]);          // Name of thread demon

  • kthread_create_on_cpu(): Same as before but with CPU affinity for the newly created thread aswell. 

    struct task_struct *kthread_create_on_cpu( int (*function)(void *data),
                                           void *data,
                                           unsigned int cpu_id,
                                           const char name[]);

Le caratteristiche della kthread_create sono:

  • Crea un thread ma lo mette a dormire subito.

  • Possiamo uccidere (kill) il thread solamente se il creatore abilità la ricezione di questo segnale. La gestione dei segnali per un thread livello kernel non è quindi automatica, ma deve essere esplicitata completamente dal programmatore.

3 KT-STARTUP-SERVICE

Questo running example mostra la creazione di un kernel demon. 

// take this value from CONFIG_HZ in your kernel config file
#define SCALING (1000)

// 1 lead to daemon thread shutdown 
static int shutdown_daemon = 0;
module_param(shutdown_daemon,int,0660);

static int sleep_enabled = 1;
module_param(sleep_enabled,int,0660);

static int timeout = 1;
module_param(timeout,int,0660);

// Function to be executed by the kernel demon that we will create
// with sys_run_demon().
int thread_function(void *data)
{
  // Update TCB of currently executing thread to be able to receive
  // the SIGKILL and SIGTERM signals.
  allow_signal(SIGKILL);
  allow-signal(SIGTERM);

  DECLARE_WAIT_QUEUE_HEAD(my_sleep_queue);

 begin:

  if(shutdown_daemon) {
    module_put(THIS_MODULE);
    return 0;
  }

  // Go to sleep for timeout*SCALING time. If we wake up for a timer
  // interrupt, check if condition sleep_enabled = 0. If instead we
  // are awaken by signals, check the pending signals.
  wait_event_interruptible_timeout(my_sleep_queue, !sleep_enabled, timeout*SCALING);

  if(signal_pending(current)) {
    printk("%s: demon thread (pid = %d) - killed\n", MODNAME, current->pid);
    module_put(THIS_MODULE);

    return -1;
  }

  goto begin;
}

// Syscall used to create our own kernel demon.
int sys_run_demon(void)
{
  int ret = 1;
  char name[128] = "the_new_demon";
  struct task_struct *the_new_demon;

  if(!try_module_get(THIS_MODULE)) return -1;

  the_new_daemon = kthread_create(thread_function, NULL, name);

  if(the_new_demon) {
    wake_up_process(the_new_demon);
    ret = 0;
  } else {
    module_put(THIS_MODULE);
  }

  return ret;
}

int init_module(void)
{
  // Set sys_run_demon() into syscall table 
}

void cleanup_module(void)
{
  // Cleanup syscall table
}