<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.9">
<TITLE>KernelAnalysis-HOWTO: Multitasking di Linux</TITLE>
<LINK HREF="KernelAnalysis-HOWTO-7.html" REL=next>
<LINK HREF="KernelAnalysis-HOWTO-5.html" REL=previous>
<LINK HREF="KernelAnalysis-HOWTO.html#toc6" REL=contents>
</HEAD>
<BODY>
<A HREF="KernelAnalysis-HOWTO-7.html">Avanti</A>
<A HREF="KernelAnalysis-HOWTO-5.html">Indietro</A>
<A HREF="KernelAnalysis-HOWTO.html#toc6">Indice</A>
<HR>
<H2><A NAME="s6">6. Multitasking di Linux</A></H2>
<H2><A NAME="ss6.1">6.1 Introduzione</A>
</H2>
<P>Questa capitolo analizza le strutture dati e funzionamento del Multitasking
di Linux
<H3>Stati dei Tasks</H3>
<P>Un Task Linux puo' esssere in uno dei seguenti stati (come da file [include/linux.h]):
<P>
<OL>
<LI>TASK_RUNNING, significa che il Task e' nella "Ready List" (quindi pronto
per l'esecuzione)</LI>
<LI>TASK_INTERRUPTIBLE, Task in attesa di un segnale o di una risorsa (sta'
dormendo)</LI>
<LI>TASK_UNINTERRUPTIBLE, Task in attesa di una risorsa, presente nella ''Wait
Queue" relativa</LI>
<LI>TASK_ZOMBIE, Task senza padre (poi adottato da init)</LI>
<LI>TASK_STOPPED, Task in modo debugging</LI>
</OL>
<H3>Interazione grafica</H3>
<P>
<PRE>
______________ CPU Disponibile _______________
| | ----------------> | |
| TASK_RUNNING | |Vera esecuzione|
|______________| <---------------- |_______________|
CPU Occupata
| /|\
In attesa di| | Risorsa
una Risorsa | | Disponibile
\|/ |
______________________
| |
| TASK_INTERRUPTIBLE / |
| TASK-UNINTERRUPTIBLE |
|______________________|
Flusso Principale Multitasking
</PRE>
<H2><A NAME="ss6.2">6.2 TimeSlice</A>
</H2>
<H3>Programmazione del PIT 8253</H3>
<P>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.
<P>
<PRE>
_____ ______ ______
| 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 */
</PRE>
<P>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.
<P>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
<P>Quindi il Timeslice si misura come 1/HZ.
<P>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.
<H3>Linux Timer IRQ ICA</H3>
<P>
<PRE>
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
</PRE>
<P>Le Funzioni si trovano:
<P>
<UL>
<LI>IRQ0x00_interrupt, SAVE_ALL [include/asm/hw_irq.h]</LI>
<LI>do_IRQ, handle_IRQ_event [arch/i386/kernel/irq.c]</LI>
<LI>timer_interrupt, do_timer_interrupt [arch/i386/kernel/time.c]</LI>
<LI>do_timer, update_process_times [kernel/timer.c]</LI>
<LI>do_softirq [kernel/soft_irq.c]</LI>
<LI>RESTORE_ALL, while loop [arch/i386/kernel/entry.S]</LI>
</UL>
<P>Note:
<P>
<OL>
<LI>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".</LI>
<LI>Le wrapper routines vengono eseguite, come anche le "do_IRQ" e ''handle_IRQ_event"
[arch/i386/kernel/irq.c].</LI>
<LI>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].</LI>
<LI>Viene eseguita la "timer_interrupt" [arch/i386/kernel/time.c] e,
quando termina,</LI>
<LI>il controllo torna ad alcune routines assembler [arch/i386/kernel/entry.S].</LI>
</OL>
<P>Descrizione:
<P>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.
<P>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]).
<H2><A NAME="ss6.3">6.3 Scheduler</A>
</H2>
<P>Lo scheduler e' quella parte di codice che sceglie QUALE Task deve venir
eseguito di volta in volta.
<P>Ogni volta che si deve cambiare Task viene scelto un candidato.
<P>Segue la funzione ''schedule [kernel/sched.c]''.
<P>
<PRE>
|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
</PRE>
<H2><A NAME="ss6.4">6.4 Bottom Half, Task Queues e Tasklets</A>
</H2>
<H3>Introduzione</H3>
<P>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.
<P>Per migliorare le performance, Linux posticipa il lavoro non urgente.
<P>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.
<P>Negli ultimi Kernels compare il meccanismo del "Task Queue" piu' dinamico
del BH e nascono anche i "Tasklet" per gestire i sistemi multiprocessore.
<P>Lo schema e':
<P>
<OL>
<LI>Dichiarazione</LI>
<LI>Marcatura</LI>
<LI>Esecuzione</LI>
</OL>
<H3>Dichiarazione</H3>
<P>
<PRE>
#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]
</PRE>
<P>La macro "DECLARE_TASK_QUEUE(q)" viene usata per dichiarare una struttura
chiamata "q" per gestire i Task Queue.
<H3>Marcatura</H3>
<P>Segue lo schema ICA per la "mark_bh" [include/linux/interrupt.h]:
<P>
<PRE>
|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]
</PRE>
<P>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).
<H3>Esecuzione</H3>
<P>Vediamo l'esecuzione a partire dalla funzione "do_IRQ" [arch/i386/kernel/irq.c]:
<P>
<PRE>
if (softirq_pending(cpu))
do_softirq();
</PRE>
<P>quindi la ''do_softirq.c" [kernel/softirq.c]:
<P>
<PRE>
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);
}
</PRE>
<P>"h->action(h);" rappresenta la funzione precedentemente accodata.
<H2><A NAME="ss6.5">6.5 Routines a bassissimo livello</A>
</H2>
<P>set_intr_gate
<P>set_trap_gate
<P>set_task_gate (non used).
<P>(*interrupt)[NR_IRQS](void) = { IRQ0x00_interrupt, IRQ0x01_interrupt,
..}
<P>NR_IRQS = 224 [kernel 2.4.2]
<P>DAFARE: Descrizione
<H2><A NAME="ss6.6">6.6 Task Switching</A>
</H2>
<H3>Quando avviene?</H3>
<P>Il Task Switching e' necessario in molti casi:
<P>
<UL>
<LI>quando termina il TimeSlice, dobbiamo scegliere un nuovo Task da eseguire</LI>
<LI>quando un Task decide di accedere ad una risorsa, si addormenta e rilascia
la CPU</LI>
<LI>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).</LI>
</UL>
<H3>Task Switching</H3>
<P>
<PRE>
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)
</PRE>
<P>Come si puo' notare il trucco sta' nel
<P>Il trucco sta' qui:
<P>
<OL>
<LI>''pushl %4'' che inserisce nello stack il nuovo EIP (del futuro
Task)</LI>
<LI>''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!)</LI>
</OL>
<P>
<PRE>
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
</PRE>
<H2><A NAME="ss6.7">6.7 Fork</A>
</H2>
<H3>Introduzione</H3>
<P>La Fork e' usata per creare un nuovo Task.
<P>Si parte dal Task padre, e si copiano le strutture dati al Task figlio.
<P>
<PRE>
| |
| .. |
Task Parent | |
| | | |
| fork |---------->| CREATE |
| | /| NEW |
|_________| / | TASK |
/ | |
--- / | |
--- / | .. |
/ | |
Task Child /
| | /
| fork |<-/
| |
|_________|
Fork SysCall
</PRE>
<H3>Cosa non viene copiato</H3>
<P>Il Task appena creato (''Task figlio'') e' quasi identico al padre (''Task
padre''), as eccezione di:
<P>
<OL>
<LI>PID, ovviamente!</LI>
<LI>La ''fork()'' del figlio ritorna con 0, mentre quella del padre con il
Task del figlio (per distinguerli in User Mode)</LI>
<LI>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).</LI>
</OL>
<H3>Fork ICA</H3>
<P>
<PRE>
|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
</PRE>
<P>
<UL>
<LI>sys_fork [arch/i386/kernel/process.c]</LI>
<LI>do_fork [kernel/fork.c]</LI>
<LI>alloc_task_struct [include/asm/processor.c]</LI>
<LI>__get_free_pages [mm/page_alloc.c]</LI>
<LI>get_pid [kernel/fork.c]</LI>
<LI>copy_files </LI>
<LI>copy_fs</LI>
<LI>copy_sighand</LI>
<LI>copy_mm</LI>
<LI>allocate_mm</LI>
<LI>mm_init</LI>
<LI>pgd_alloc -> get_pgd_fast [include/asm/pgalloc.h]</LI>
<LI>get_pgd_slow</LI>
<LI>dup_mmap [kernel/fork.c]</LI>
<LI>copy_page_range [mm/memory.c]</LI>
<LI>ptep_set_wrprotect [include/asm/pgtable.h]</LI>
<LI>clear_bit [include/asm/bitops.h]</LI>
<LI>copy_segments [arch/i386/kernel/process.c]</LI>
<LI>copy_thread</LI>
<LI>SET_LINKS [include/linux/sched.h]</LI>
<LI>wake_up_process [kernel/sched.c]</LI>
</UL>
<H3>Copy on Write</H3>
<P>Per implementare la Copy on Write Linux:
<P>
<OL>
<LI>Marca tutte le pagine copiate come READ-ONLY, facendo poi scaturire un
Page Fault al primo tentativo di scrittura della pagina da parte del figlio</LI>
<LI>Il gestore di Page Fault crea una nuova ed indipendente copia della pagina
per il Task figlio.</LI>
</OL>
<P>
<PRE>
| 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
</PRE>
<P>
<UL>
<LI>do_page_fault [arch/i386/mm/fault.c] </LI>
<LI>handle_mm_fault [mm/memory.c]</LI>
<LI>handle_pte_fault </LI>
<LI>do_wp_page</LI>
<LI>alloc_page [include/linux/mm.h]</LI>
<LI>break_cow [mm/memory.c]</LI>
<LI>copy_cow_page</LI>
<LI>establish_pte</LI>
<LI>set_pte [include/asm/pgtable-3level.h]</LI>
</UL>
<HR>
<A HREF="KernelAnalysis-HOWTO-7.html">Avanti</A>
<A HREF="KernelAnalysis-HOWTO-5.html">Indietro</A>
<A HREF="KernelAnalysis-HOWTO.html#toc6">Indice</A>
</BODY>
</HTML>
