Domenico Cotroneo » 21.Primitive di sincronizzazione nel kernel Linux

Sommario

• Concorrenza e scalabilità nel kernel
• Primitive di sincronizzazione interne al kernel

Motivazioni

Il kernel è esso stesso un programma concorrente.

Possono esserci molteplici flussi di esecuzione in un certo istante.

Per cui, è necessario sincronizzare i flussi di esecuzione che accedono a strutture dati e risorse condivise.

Il problema è più accentuato nei sistemi SMP, ma è presente anche in quelli UP (uniprocessore).

Concorrenza in sistemi UP

Anche se vi è un solo processore, il task attualmente in esecuzione in spazio kernel può essere prelazionato in favore di un altro (kernel preemption).

Un interrupt hardware può arrivare ad ogni istante.

Una bottom half (“interrupt software”) può essere attivata ad ogni istante.

Un task in spazio kernel può volontariamente rilasciare la CPU ad un altro task.

Concorrenza in sistemi SMP

Due o più processori possono eseguire codice del kernel contemporaneamente.

Nei sistemi SMP valgono anche le stesse considerazioni dei sistemi UP.

Codice safe

E’ necessario programmare il codice senza fare assunzioni sul numero di CPU, o sull’occorrenza o meno di eventi.

Il codice kernel è correttamente sincronizzato se è:

• interrupt-safe (sincronizzato con ISR);
• preempt-safe (sincronizzato con altro codice che esegue sulla stessa CPU);
• SMP-safe (sincronizzato con altro codice che esegue su altre CPU).

Codice safe

E’ necessario garantire la sincronizzazione se si accede a dati globali, e altri flussi oltre a quello corrente possono accedervi.

Lo stesso codice può essere chiamato di nuovo su un altro processore, o essere prelazionato.

La memoria della struttura dati può essere de-allocata da altro codice.

Il codice rilascia la CPU, ma le risorse condivise sono ancora in uno stato inconsistente.

I dati sono condivisi tra codice che esegue in process context e codice in interrupt context, o tra più interrupt handler.

In tutti questi casi, occorre utilizzare qualche primitiva di sincronizzazione quando si accede a dati globali.

Errata sincronizzazione

Deadlocks

• Occorre fare attenzione all’ordine con cui un gruppo di lock viene acquisito.
• Alcune funzioni del kernel richiedono di acquisire/rilasciare dei particolari lock prima di essere invocate.

Race conditions

• Evitare che i dati globali su cui si lavora non siano sovrascritti da altri flussi di esecuzione.

Starvation

• Altri flussi di esecuzione attendono per un tempo eccessivamente lungo.

Contese e scalabilità

Una operazione su un dato condiviso (protetto da sincronizzazione) molto lunga può causare contese sui lock.
Occorre scegliere la corretta granularità dei lock, ossia la dimensione dei dati per i quali un lock è utilizzato:

• granularità grossa può causare starvation;
• granularità fine produce complessità e overhead;

Può essere necessario ristrutturare il codice per avere buona granularità.

Contese e scalabilità

La scalabilità è una misura di quanto bene il sistema può crescere.

Ad esempio, nel caso dei SO un algoritmo è scalabile se mantiene buone prestazioni quando aumenta il numero di processi, processori, memoria, … gestiti.

Difficilmente usando 2 CPU si ottengono prestazioni raddoppiate!

La scelta della granularità dei lock influisce sulla scalabilità.

Primitive di sincronizzazione

Il kernel fornisce molteplici meccanismi per la sincronizzazione:

• Operazioni atomiche;
• Spinlock;
• Spinlock read-write;
• Semafori;
• Semafori read-write;
• Condition variables;
• Disabilitazione di interrupt o della prelazione.

La scelta dei meccanismi determina la correttezza e le prestazioni del sistema.

Operazioni atomiche

Le operazioni atomiche sono primitive che accedono a singole variabili ed effettuano delle operazioni predefinite.

Lettura, scrittura, addizione, sottrazione, …

Esse sono implementate usando le primitive fornite dall’hardware laddove disponibili, oppure in software.

Possono essere utilizzate su degli appositi tipi opachi (atomic_t).

Operazioni atomiche

atomic_t v;

/* define v */

atomic_t u = ATOMIC_INIT(0);

/* define u and initialize it to zero */

atomic_set(&v, 4);

/* v = 4 (atomically) */

atomic_add(2, &v);

/* v = v + 2 = 6 (atomically) */

atomic_inc(&v);

/* v = v + 1 = 7 (atomically) */

printk("%d\n", atomic_read(&v));

/* will print "7" */

Operazioni atomiche

Operazioni atomiche

Le operazioni atomiche possono anche essere effettuate su singoli bit.

Sono ad esempio necessarie quando si accede ad un registro hardware.

Il compilatore o la CPU potrebbero “ottimizzare” l’operazione unendola con un’altra scrittura.

Un’altra CPU potrebbe scrivere sulla stessa variabile in memoria.

Le operazioni atomiche su bit accedono ai tipi standard interi.

Operazioni atomiche

unsigned long word = 0;
set_bit(0, &word);
/* bit zero is now set (atomically) */

set_bit(1, &word);
/* bit one is now set (atomically) */

clear_bit(1, &word);
/* bit one is now unset (atomically) */

change_bit(0, &word);
/* bit zero is flipped; now it is unset (atomically) */

/* atomically sets bit zero and returns the previous value (zero) */

if (test_and_set_bit(0, &word)) {

/* never true */

}

/* the following is legal; you can mix atomic bit instructions with normal C */

word = 7;

Operazioni atomiche

Spinlock

Nella maggior parte dei casi, una regione critica contiene più di una singola operazione.

Sono richieste primitive di locking quali spinlock e semafori.

Uno spinlock è un lock esclusivo, tale che:

• se il lock è conteso, il thread effettua una attesa attiva (spin) finché non è libero;
• se il lock è libero, viene atomicamente acquisito e il thread continua l’esecuzione.

Spinlock

L’attesa attiva causa uno “spreco” di CPU.

La CPU non viene usata per fare lavoro utile ma per controllare lo stato del lock.

Tuttavia, se il lock rimane occupato per brevi periodi, l’overhead di uno spinlock è minore di bloccare il thread ed effettuare una coppia di context switch.

E’ conveniente usare spinlock se il lock è occupato per brevi periodi (più efficiente “sprecare” dei cicli di CPU in spin piuttosto che in context switch).

Spinlock: utilizzo

Definiti in <linux/spinloch.h> e <asm/spinlock.h>

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;

spin_lock(&mr_lock);
/* critical region */
spin_unlock(&mr_lock);

Tipicamente, uno spinlock è dichiarato all’interno della struttura dati (e.g., una struct) della quale sincronizza gli accessi.

Spinlock: implementazione

In generale, occorre programmare assumendo che il sistema sia SMP:

• in sistemi SMP, il locking è effettuato tramite un ciclo basato su istruzioni atomiche della CPU (e.g., test-and-set) e disattivando la preemption sulla CPU del thread corrente;
• in sistemi UP, il locking disattiva semplicemente la kernel preemption;
• in sistemi UP senza kernel preemption, il locking non effettua alcuna operazione.

L’implementazione è scelta a tempo di compilazione.

Avvertenza: non si deve chiamare una funzione bloccante mentre si possiede uno spinlock.

Se altro codice kernel tenta di acquisire lo spinlock, si può avere un loop infinito in sistemi UP.

Spinlock ed interrupt

Gli spinlock (a differenza dei semafori) possono essere usati nelle ISR.

In Linux le ISR non sono eseguite in thread dedicati (il loro codice non può essere sospeso e ri-schedulato successivamente) e non sono prelazionabili.

codice interrupt-safe: occorre disabilitare gli interrupt della CPU corrente.

Se lo stesso interrupt capita mentre la sua ISR stava già eseguendo sulla stessa CPU, la nuova ISR andrà in loop infinito sullo stesso spinlock poichè non è prelazionabile.

Non è necessario disabilitare gli interrupt sulle altre CPU.

Spinlock e interrupt

Esistono apposite primitive per acquisire/rilasciare uno spinlock e contestualmente disattivare gli interrupt sulla CPU locale.

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;

spin_lock_irqsave(&mr_lock, flags);
/* critical region ... */
spin_unlock_irqrestore(&mr_lock, flags);

Queste primitive vanno utilizzate se il lock può essere conteso in contesto interrupt.

Altre primitive per spinlock

Esempio

Gestione della tabella delle pagine (kernel 2.6.11): handle_mm_fault()

Si veda per approfondimenti linux/mm/memory.c

Reader-writer spinlock

In alcune circostanze, gli utilizzatori di un lock si comportano come lettori e scrittori.

Ad esempio, una struttura dati “lista” che può essere sia modificata sia scansionata.

Uno scrittore accede in mutua esclusione con altri scrittori o lettori; i lettori non necessitano di mutua esclusione tra loro.

Esistono apposite versioni delle primitive di spinlock con semantica reader-writer.

Reader-writer spinlock: utilizzo

rwlock_t mr_rwlock = RW_LOCK_UNLOCKED;

read_lock(&mr_rwlock);
/* critical section (read only) ... */
read_unlock(&mr_rwlock);

write_lock(&mr_rwlock);
/* critical section (read and write) ... */
write_unlock(&mr_lock);

Avvertenza: non si può acquisire uno spinlock come writer se lo si possiede già come reader!

Avvertenza: in Linux i reader-writer lock possono causare la starvation degli scrittori.

Anche le altre primitive su spinlock hanno una corrispondente primitiva per i reader-writer spinlock.

Semafori

In Linux, i semafori sono “sleeping locks”.

Se il lock è occupato, il thread è posto in una coda di attesa, e un altro thread pronto viene schedulato.

Quando il lock viene liberato, uno dei thread in attesa è riattivato e può acquisire il semaforo.

Un semaforo non è necessariamente esclusivo.

Si evita l’attesa attiva, ma c’è maggiore overhead rispetto agli spinlock.

Semafori

La attesa bloccante nei semafori permette il loro utilizzo laddove gli spinlock non possono essere usati.

Un thread può bloccarsi anche se possiede un semaforo (non causerà il loop infinito di altri thread contendenti).

Questo accade per codice che attende eventi da user-space o dall’hardware, o che alloca memoria.

Inoltre, i semafori sono più convenienti degli spinlock se sono occupati per un periodo non breve.

I semafori non disabilitano la preemtpion.

Tuttavia, non è possibile utilizzare i semafori in contesti in cui non è possibile bloccarsi:

• nel contesto di un interrupt handler;
• quando già si possiede uno spinlock.

Inoltre, l’overhead dei semafori è elevato.

Semafori: utilizzo

Definiti in <asm/semaphore.h>

/* define and declare a semaphore, named mr_sem, with a count of one */
static DECLARE_SEMAPHORE_GENERIC(mr_sem, 1);
/* equivalent to: DECLARE_MUTEX(mr_sem); */

/* attempt to acquire the semaphore ... */
if (down_interruptible(&mr_sem)) {
/* signal received, e.g., EINTR */
/* semaphore not acquired ... */
}
/* critical region ... */

/* release the given semaphore */
up(&mr_sem);

Altre primitive per semafori

Semafori reader-writer

Sono semafori binari (mutex)

static DECLARE_RWSEM(mr_rwsem);

/* attempt to acquire the semaphore for reading ... */
down_read(&mr_rwsem);

/* critical region (read only) ... */

/* release the semaphore */
up_read(&mr_rwsem);

/* attempt to acquire the semaphore for writing ... */
down_write(&mr_rwsem);

/* critical region (read and write) ... */

/* release the semaphore */
up_write(&mr_sem);

Esempio

Gestione della configurazione della porta seriale (kernel 2.6.11): port_sem

Si veda per approfondimenti  linux/drivers/serial/serial_core.c

Disattivazione kernel preemption

Anche se gli spinlock sono già preemption-safe, in alcune circostanze è necessaria la sola disattivazione della preemption su una CPU.

E’ il caso di dati specifici di una certa CPU (e.g., runqueues).

Preemption gestita tramite una variabile intera “preempt_count” (0 se preemption è attiva).

int cpu;
/* disable kernel preemption and set "cpu" to the current processor */
cpu = get_cpu();
/* manipulate per-processor data ... */
/* reenable kernel preemption, "cpu" can change and so is no longer valid */
put_cpu();