Next Previous Contents

6. Multitasking di Linux

6.1 Introduzione

Questa capitolo analizza le strutture dati e funzionamento del Multitasking di Linux

Stati dei Tasks

Un Task Linux puo' esssere in uno dei seguenti stati (come da file [include/linux.h]):

  1. TASK_RUNNING, significa che il Task e' nella "Ready List" (quindi pronto per l'esecuzione)
  2. TASK_INTERRUPTIBLE, Task in attesa di un segnale o di una risorsa (sta' dormendo)
  3. TASK_UNINTERRUPTIBLE, Task in attesa di una risorsa, presente nella ''Wait Queue" relativa
  4. TASK_ZOMBIE, Task senza padre (poi adottato da init)
  5. TASK_STOPPED, Task in modo debugging

Interazione grafica

       ______________     CPU Disponibile   _______________
      |              |  ---------------->  |               |
      | TASK_RUNNING |                     |Vera esecuzione|  
      |______________|  <----------------  |_______________|
                           CPU Occupata
            |   /|\       
In attesa di|    | Risorsa  
una Risorsa |    | Disponibile             
           \|/   |      
    ______________________                     
   |                      |
   | TASK_INTERRUPTIBLE / |
   | TASK-UNINTERRUPTIBLE |
   |______________________|
 
                     Flusso Principale Multitasking

6.2 TimeSlice

Programmazione del PIT 8253

Ogni 10 ms (a seconda del valore di HZ) arriva un IRQ0, che permmette di gestire il multitasking: questo segnale arriva dal PIC 8259 (nell'architettura 386+) connesso a sua volta con il PIT 8253 avente clock di 1.19318 MHz.

    _____         ______        ______        
   | CPU |<------| 8259 |------| 8253 |
   |_____| IRQ0  |______|      |___/|\|
                                    |_____ CLK 1.193.180 MHz
          
// From include/asm/param.h
#ifndef HZ 
#define HZ 100 
#endif
 
// From include/asm/timex.h
#define CLOCK_TICK_RATE 1193180 /* Underlying HZ */
 
// From include/linux/timex.h
#define LATCH ((CLOCK_TICK_RATE + HZ/2) / HZ) /* For divider */
 
// From arch/i386/kernel/i8259.c
outb_p(0x34,0x43); /* binary, mode 2, LSB/MSB, ch 0 */ 
outb_p(LATCH & 0xff , 0x40); /* LSB */
outb(LATCH >> 8 , 0x40); /* MSB */
 

Quindi quello che si fa e' programmare l'8253 (PIT, Programmable Interval Timer) con LATCH = (1193180/HZ) = 11931.8, dove HZ=100 (default). LATCH indica il fattore di divisione frequenza per il clock.

LATCH = 11931.8 fornisce all'8253 (in output) una frequenza di 1193180 / 11931.8 = 100 Hz, quindi il periodo tra 2 IRQ0 e' di 10ms

Quindi il Timeslice si misura come 1/HZ.

Ogni TimeSlice viene sospeso il processo attualmente di esecuzione (senza Task Switching), e viene fatto del lavoro di ''manutenzione'', dopo di che il controllo ritorna al processo precedentemente interrotto.

Linux Timer IRQ ICA

Linux Timer IRQ
IRQ 0 [Timer]
 |  
\|/
|IRQ0x00_interrupt        //   wrapper IRQ handler
   |SAVE_ALL              ---   
      |do_IRQ                |   wrapper routines
         |handle_IRQ_event  ---
            |handler() -> timer_interrupt  // registered IRQ 0 handler
               |do_timer_interrupt
                  |do_timer  
                     |jiffies++;
                     |update_process_times  
                     |if (--counter <= 0) { // if time slice ended then
                        |counter = 0;        //   reset counter           
                        |need_resched = 1;   //   prepare to reschedule
                     |}
         |do_softirq
         |while (need_resched) { // if necessary
            |schedule             //   reschedule
            |handle_softirq
         |}
   |RESTORE_ALL
 

Le Funzioni si trovano:

Note:

  1. La Funzione "IRQ0x00_interrupt" (come le altre IRQ0xXY_interrupt) e' direttamente puntata dalla IDT (Interrupt Descriptor Table, simile all'Interrupt Vector Table del modo reale, si veda Cap 11 per informazioni), cosicche' OGNI interrupt in arrivo al processore venga gestito dalla routine "IRQ0x#NR_interrupt" routine, dove #NR e' il numero dell'interrupt. Possiamo definire queste macro come "wrapper irq handler".
  2. Le wrapper routines vengono eseguite, come anche le "do_IRQ" e ''handle_IRQ_event" [arch/i386/kernel/irq.c].
  3. Dopo di questo, il controllo passa alla routing IRQ ''ufficiale'' (puntata da "handler()"), precedentemente registrata con ''request_irq" [arch/i386/kernel/irq.c]: nel caso IRQ0 avremo "timer_interrupt" [arch/i386/kernel/time.c].
  4. Viene eseguita la "timer_interrupt" [arch/i386/kernel/time.c] e, quando termina,
  5. il controllo torna ad alcune routines assembler [arch/i386/kernel/entry.S].

Descrizione:

Per gestire il Multitasking quindi, Linux (come ogni sistema Unix-like) utilizza un ''contatore'' per tenere traccia di quanto e' stata utilizzata la CPU dal Task.

Quindi, ad ogni IRQ 0, il contatore viene decrementato (punto 4) e, quando raggiunge 0, siamo dobbiamo effettuare un Task Switching (punto 4, la variabile "need_resched" viene settata ad 1, cosicche' nel punto 5 tale valore porta a chiamare la "schedule" [kernel/sched.c]).

6.3 Scheduler

Lo scheduler e' quella parte di codice che sceglie QUALE Task deve venir eseguito di volta in volta.

Ogni volta che si deve cambiare Task viene scelto un candidato.

Segue la funzione ''schedule [kernel/sched.c]''.

|schedule
   |do_softirq // manages post-IRQ work
   |for each task
      |calculate counter
   |prepare_to__switch // does anything
   |switch_mm // change Memory context (change CR3 value)
   |switch_to (assembler)
      |SAVE ESP
      |RESTORE future_ESP
      |SAVE EIP
      |push future_EIP *** push parametro come se facessimo una call 
         |jmp __switch_to (funzione per gestire alcuni registri) 
         |__switch_to()   (si veda dopo per la spiegazione del funzionamento del Task Switching
          ..
         |ret *** ret dalla call usando il nuovo EIP
      new_task

6.4 Bottom Half, Task Queues e Tasklets

Introduzione

Nei classici Unix, quando arriva un IRQ (da un device), il sistema effettua il Task Switching per interrogare il Task che ha fatto accesso al Device.

Per migliorare le performance, Linux posticipa il lavoro non urgente.

Questa funzionalita' e' stata gestita fin dalle prime versioni (kernel 1.x in poi) dai cosiddetti "bottom halves" (BH). In sostanza l'IRQ handler ''marca'' un bottom half (flag), per essere eseguito piu' tardi, e durante la schedulazione vengono poi eseguiti tutti i BH attivi.

Negli ultimi Kernels compare il meccanismo del "Task Queue" piu' dinamico del BH e nascono anche i "Tasklet" per gestire i sistemi multiprocessore.

Lo schema e':

  1. Dichiarazione
  2. Marcatura
  3. Esecuzione

Dichiarazione

#define DECLARE_TASK_QUEUE(q) LIST_HEAD(q)
#define LIST_HEAD(name) \
   struct list_head name = LIST_HEAD_INIT(name) 
struct list_head { 
   struct list_head *next, *prev; 
};
#define LIST_HEAD_INIT(name) { &(name), &(name) } 
 
      ''DECLARE_TASK_QUEUE'' [include/linux/tqueue.h, include/linux/list.h] 

La macro "DECLARE_TASK_QUEUE(q)" viene usata per dichiarare una struttura chiamata "q" per gestire i Task Queue.

Marcatura

Segue lo schema ICA per la "mark_bh" [include/linux/interrupt.h]:

|mark_bh(NUMBER)
   |tasklet_hi_schedule(bh_task_vec + NUMBER)
      |insert into tasklet_hi_vec
         |__cpu_raise_softirq(HI_SOFTIRQ) 
            |soft_active |= (1 << HI_SOFTIRQ)
 
                   ''mark_bh''[include/linux/interrupt.h]

Quindi, ad esempio, quando un IRQ handler vuole posticipare del lavoro, basta che esegua una marcatura con la mark_bh(NUMBER)", dove NUMBER e' un BH precedentemente dichiarato (si veda sezione precedente).

Esecuzione

Vediamo l'esecuzione a partire dalla funzione "do_IRQ" [arch/i386/kernel/irq.c]:

if (softirq_pending(cpu)) 
  do_softirq();

quindi la ''do_softirq.c" [kernel/softirq.c]:

asmlinkage void do_softirq() { 
  int cpu = smp_processor_id(); 
  __u32 pending; 
  long flags; 
  __u32 mask;
  debug_function(DO_SOFTIRQ,NULL);
  if (in_interrupt()) 
    return;
  local_irq_save(flags);
  pending = softirq_pending(cpu);
  if (pending) { 
    struct softirq_action *h;
    mask = ~pending; 
    local_bh_disable(); 
    restart: 
        /* Reset the pending bitmask before enabling irqs */ 
    softirq_pending(cpu) = 0;
    local_irq_enable();
    h = softirq_vec;
    do { 
      if (pending & 1) 
        h->action(h); 
      h++; 
      pending >>= 1; 
    } while (pending);
    local_irq_disable();
    pending = softirq_pending(cpu); 
    if (pending & mask) { 
      mask &= ~pending; 
      goto restart; 
    } 
    __local_bh_enable();
    if (pending) 
      wakeup_softirqd(cpu); 
  }
  local_irq_restore(flags); 
}

"h->action(h);" rappresenta la funzione precedentemente accodata.

6.5 Routines a bassissimo livello

set_intr_gate

set_trap_gate

set_task_gate (non used).

(*interrupt)[NR_IRQS](void) = { IRQ0x00_interrupt, IRQ0x01_interrupt, ..}

NR_IRQS = 224 [kernel 2.4.2]

DAFARE: Descrizione

6.6 Task Switching

Quando avviene?

Il Task Switching e' necessario in molti casi:

Task Switching

                           TRUCCO DEL TASK SWITCHING

 #define switch_to(prev,next,last) do {                                 \
        asm volatile("pushl %%esi\n\t"                                  \
                     "pushl %%edi\n\t"                                  \
                     "pushl %%ebp\n\t"                                  \
                     "movl %%esp,%0\n\t"        /* save ESP */          \
                     "movl %3,%%esp\n\t"        /* restore ESP */       \
                     "movl $1f,%1\n\t"          /* save EIP */          \
                     "pushl %4\n\t"             /* restore EIP */       \
                     "jmp __switch_to\n"                                \
                     "1:\t"                                             \
                     "popl %%ebp\n\t"                                   \
                     "popl %%edi\n\t"                                   \
                     "popl %%esi\n\t"                                   \
                     :"=m" (prev->thread.esp),"=m" (prev->thread.eip),  \
                      "=b" (last)                                       \
                     :"m" (next->thread.esp),"m" (next->thread.eip),    \
                      "a" (prev), "d" (next),                           \
                      "b" (prev));                                      \
} while (0)

Come si puo' notare il trucco sta' nel

Il trucco sta' qui:

  1. ''pushl %4'' che inserisce nello stack il nuovo EIP (del futuro Task)
  2. ''jmp __switch_to'' che esegue la ''__switch_to'', ma che al contrario di una ''call'', ci fa ritornare al valore messo nello stack al punto 1 (quindi al nuovo Task!)

  

     U S E R   M O D E                 K E R N E L     M O D E

 |          |     |          |       |          |     |          |
 |          |     |          | Timer |          |     |          |
 |          |     |  Normal  |  IRQ  |          |     |          |
 |          |     |   Exec   |------>|Timer_Int.|     |          |
 |          |     |     |    |       | ..       |     |          |
 |          |     |    \|/   |       |schedule()|     | Task1 Ret|
 |          |     |          |       |_switch_to|<--  |  Address |
 |__________|     |__________|       |          |  |  |          |
                                     |          |  |S |          | 
Task1 Data/Stack   Task1 Code        |          |  |w |          |
                                     |          | T|i |          |
                                     |          | a|t |          |
 |          |     |          |       |          | s|c |          |
 |          |     |          | Timer |          | k|h |          |
 |          |     |  Normal  |  IRQ  |          |  |i |          | 
 |          |     |   Exec   |------>|Timer_Int.|  |n |          |
 |          |     |     |    |       | ..       |  |g |          |
 |          |     |    \|/   |       |schedule()|  |  | Task2 Ret|
 |          |     |          |       |_switch_to|<--  |  Address |
 |__________|     |__________|       |__________|     |__________|
 
Task2 Data/Stack   Task2 Code        Kernel Code  Kernel Data/Stack

6.7 Fork

Introduzione

La Fork e' usata per creare un nuovo Task.

Si parte dal Task padre, e si copiano le strutture dati al Task figlio.

 
                               |         |
                               | ..      |
         Task Parent           |         |
         |         |           |         |
         |  fork   |---------->|  CREATE |   
         |         |          /|   NEW   |
         |_________|         / |   TASK  |
                            /  |         |
             ---           /   |         |
             ---          /    | ..      |
                         /     |         |
         Task Child     / 
         |         |   /
         |  fork   |<-/
         |         |
         |_________|
              
                       Fork SysCall

Cosa non viene copiato

Il Task appena creato (''Task figlio'') e' quasi identico al padre (''Task padre''), as eccezione di:

  1. PID, ovviamente!
  2. La ''fork()'' del figlio ritorna con 0, mentre quella del padre con il Task del figlio (per distinguerli in User Mode)
  3. Tutte le pagine del figlio sono marcate ''READ + EXECUTE'', senza il diritto "WRITE'' (mentre il padre continua ad avere i diritti come prima) cosicche', quando viene fatta una richiesta di scrittura, viene scatenata una eccezione di ''Page Fault'' che creera' a questo punto un pagina fisicamente indipendente: questo meccanismo viene chiamata ''Copy on Write'' (si veda il Cap.10 per ulteriori informazioni).

Fork ICA

|sys_fork 
   |do_fork
      |alloc_task_struct 
         |__get_free_pages
       |p->state = TASK_UNINTERRUPTIBLE
       |copy_flags
       |p->pid = get_pid    
       |copy_files
       |copy_fs
       |copy_sighand
       |copy_mm // gestisce la CopyOnWrite (I parte)
          |allocate_mm
          |mm_init
             |pgd_alloc -> get_pgd_fast
                |get_pgd_slow
          |dup_mmap
             |copy_page_range
                |ptep_set_wrprotect
                   |clear_bit // marca la pagina read-only              
          |copy_segments // per LDT
       |copy_thread
          |childregs->eax = 0  
          |p->thread.esp = childregs // figlio ritorna 0
          |p->thread.eip = ret_from_fork // figlio ricomincia fall'uscita della fork
       |retval = p->pid // la fork del padre ritorna il pid del figlio
       |SET_LINKS // Il Task viene inserito nella lista dei processi
       |nr_threads++ // variabile globale
       |wake_up_process(p) // Adesso possiamo svegliare il Task figlio
       |return retval
              
                      fork ICA
 

Copy on Write

Per implementare la Copy on Write Linux:

  1. Marca tutte le pagine copiate come READ-ONLY, facendo poi scaturire un Page Fault al primo tentativo di scrittura della pagina.
  2. Il gestore di Page Fault crea una nuova ed indipendente copia della pagina

 
 | Page 
 | Fault 
 | Exception
 |
 |
 -----------> |do_page_fault
                 |handle_mm_fault
                    |handle_pte_fault 
                       |do_wp_page        
                          |alloc_page      // Allocata una nuova pagina
                          |break_cow
                             |copy_cow_page // Copia la vecchia pagina su quella nuova
                             |establish_pte // riconfigura i puntatori della Page Table
                                |set_pte
                            
                    Page Fault ICA
 


Next Previous Contents

Hosting by: hurra.com
Generated: 2007-01-26 17:56:17