 |
|
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]):
- TASK_RUNNING, significa che il Task e' nella "Ready List" (quindi pronto per l'esecuzione)
- TASK_INTERRUPTIBLE, Task in attesa di un segnale o di una risorsa (sta' dormendo)
- TASK_UNINTERRUPTIBLE, Task in attesa di una risorsa, presente nella ''Wait Queue" relativa
- TASK_ZOMBIE, Task senza padre (poi adottato da init)
- 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:
- IRQ0x00_interrupt, SAVE_ALL [include/asm/hw_irq.h]
- do_IRQ, handle_IRQ_event [arch/i386/kernel/irq.c]
- timer_interrupt, do_timer_interrupt [arch/i386/kernel/time.c]
- do_timer, update_process_times [kernel/timer.c]
- do_softirq [kernel/soft_irq.c]
- RESTORE_ALL, while loop [arch/i386/kernel/entry.S]
Note:
- 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".
- Le wrapper routines vengono eseguite, come anche le "do_IRQ" e ''handle_IRQ_event" [arch/i386/kernel/irq.c].
- 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].
- Viene eseguita la "timer_interrupt" [arch/i386/kernel/time.c] e, quando termina,
- 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':
- Dichiarazione
- Marcatura
- 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:
- quando termina il TimeSlice, dobbiamo scegliere un nuovo Task da eseguire
- quando un Task decide di accedere ad una risorsa, si addormenta e rilascia la CPU
- quando un Task aspetta per una pipe, dobbiamo dare accesso ad un altro Task (che magari sara' quello che scrivera' nella pipe e fara' poi risvegliare il processo).
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:
- ''pushl %4'' che inserisce nello stack il nuovo EIP (del futuro Task)
- ''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:
- PID, ovviamente!
- La ''fork()'' del figlio ritorna con 0, mentre quella del padre con il Task del figlio (per distinguerli in User Mode)
- 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
- sys_fork [arch/i386/kernel/process.c]
- do_fork [kernel/fork.c]
- alloc_task_struct [include/asm/processor.c]
- __get_free_pages [mm/page_alloc.c]
- get_pid [kernel/fork.c]
- copy_files
- copy_fs
- copy_sighand
- copy_mm
- allocate_mm
- mm_init
- pgd_alloc -> get_pgd_fast [include/asm/pgalloc.h]
- get_pgd_slow
- dup_mmap [kernel/fork.c]
- copy_page_range [mm/memory.c]
- ptep_set_wrprotect [include/asm/pgtable.h]
- clear_bit [include/asm/bitops.h]
- copy_segments [arch/i386/kernel/process.c]
- copy_thread
- SET_LINKS [include/linux/sched.h]
- wake_up_process [kernel/sched.c]
Copy on Write
Per implementare la Copy on Write Linux:
- Marca tutte le pagine copiate come READ-ONLY, facendo poi scaturire un Page Fault al primo tentativo di scrittura della pagina.
- 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
- do_page_fault [arch/i386/mm/fault.c]
- handle_mm_fault [mm/memory.c]
- handle_pte_fault
- do_wp_page
- alloc_page [include/linux/mm.h]
- break_cow [mm/memory.c]
- copy_cow_page
- establish_pte
- set_pte [include/asm/pgtable-3level.h]
Next Previous Contents
Hosting by: hurra.com
Generated: 2007-01-26 17:56:17