Questa capitolo analizza le strutture dati e funzionamento del Multitasking di Linux
Un Task Linux puo' esssere in uno dei seguenti stati (come da file [include/linux.h]):
______________ CPU Disponibile _______________
| | ----------------> | |
| TASK_RUNNING | |Vera esecuzione|
|______________| <---------------- |_______________|
CPU Occupata
| /|\
In attesa di| | Risorsa
una Risorsa | | Disponibile
\|/ |
______________________
| |
| TASK_INTERRUPTIBLE / |
| TASK-UNINTERRUPTIBLE |
|______________________|
Flusso Principale Multitasking
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
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:
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]).
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
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':
#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.
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).
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.
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
Il Task Switching e' necessario in molti casi:
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:
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
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
Il Task appena creato (''Task figlio'') e' quasi identico al padre (''Task padre''), as eccezione di:
|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
Per implementare la Copy on Write Linux:
| 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