<!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">Next</A>
<A HREF="KernelAnalysis-HOWTO-5.html">Previous</A>
<A HREF="KernelAnalysis-HOWTO.html#toc6">Contents</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>
<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.</LI>
<LI>Il gestore di Page Fault crea una nuova ed indipendente copia
della pagina</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">Next</A>
<A HREF="KernelAnalysis-HOWTO-5.html">Previous</A>
<A HREF="KernelAnalysis-HOWTO.html#toc6">Contents</A>
</BODY>
</HTML>
