Strategie di locking…

Salve gente.

Uno dei filesystem più promettenti per Linux è sicuramente Btrfs che attualmente è stato incluso come “sperimentale” in quello che diverrà il futuro kernel 2.6.29.

Non parlerò di questo filesystem in quanto tale, ma vorrei piuttosto soffermarmi su un dettaglio implementativo dello stesso, per altro brillantemente descritto in un post di LWN.

Btrfs usa una funzione specifica/specializzata per la sincronizzazione dei thread: in particolare tale funzione include un’”inedita” strategia di locking al fine di regolare in maniera efficiente l’accesso ai dati del filesystem (propriamente ad un suo “tree”).

Questa è la funzione:

int btrfs_tree_lock(struct extent_buffer *eb)
{
	int i;

	if (mutex_trylock(&eb->mutex))
		return 0;
	for (i = 0; i < 512; i++)
	{
		cpu_relax();
		if (mutex_trylock(&eb->mutex))
			return 0;
	}
	cpu_relax();
	mutex_lock_nested(&eb->mutex, BTRFS_MAX_LEVEL - btrfs_header_level(eb));
	return 0;
}

Citando, sempre da LWN:

“The lock in question is a mutex, but it is being acquired in an interesting way. If the lock is held by another process, this function will poll it up to 512 times, without sleeping, in the hope that it will become available quickly. Should that happen, the lock can be acquired without sleeping at all. After 512 unsuccessful attempts, the function will finally give up and go to sleep.”

La “novità” sta proprio nel modo particolare con cui il lock viene tentato, a “tre fasi”:

1. il processo/thread che richiede il lock effettua inizialmente un tentativo di acquisizione single-shot.
2. se il tentativo fallisce inizia un polling intenso provando ad acquisire il lock. Se il lock viene acquisito, la procedura esce immediatamente, altrimenti riprova.
3. solo dopo un numero massimo di tentativi falliti (512), il processo/thread si sospende invocando una forma di sleep.

La prima fase, in cui avviene polling intenso, fa uso di un tipo di lock abbastanza semplice nonchè “standard” in ambito kernel chiamato spin lock (o spinlock).

Citando dal Tanenbaum:

“Il testare continuamente una variabile, in attesa che assuma un certo valore, viene detto attesa attiva (busy waiting), che di norma dovrebbe essere evitata, dal momento che porta ad uno spreco del tempo di CPU; essa viene usata solo in quei casi in cui ci si aspetta che il tempo di attesa sia breve. Un lock che usa l’attesa attiva è detto spin lock.”

Quello che mi ha incuriosito e che mi piace della soluzione “3-way” adottata da Btrfs è il fatto che… funzioni.

Tempo fa, dovendo gestire con mio cugino Alberto (che saluto!) un’analoga situazione di locking per l’esame di Progettazione e analisi di algoritmi, avevamo pensato ad una soluzione molto simile a quella sopra citata,… però alla fine l’avevamo provata e scartata.

Il progetto, nell’ambito del cosiddetto Maximum Diversity Problem (MDP), prevedeva l’implementazione di un algoritmo parallelo di tipo branch and bound in cui diversi pthread lavoravano in maniera per lo più indipendente gli uni dagli altri.

Talvolta però i thread necessitavano di “comunicare” fra loro, accedendo ad una sezione critica protetta da un mutex per modificare i dati globali in essa contenuti (es: per registrare nuovi risultati parziali appena ottenuti).

In questo caso il busy waiting introdotto dai tentativi di acquisizione del lock, nonostante le pthread_yield() che avevo opportunamente disseminato (in luogo della chiamata cpu_relax() di Btrfs), risultava in qualche modo penalizzante. Molto penalizzante.

Nota: la chiamata pthread_yield(), disponibile su Linux, non fa parte dello standard Pthread; in MacOSX questa chiamata non è implementata ed al suo posto si usa sched_yield().

Alla fine avevamo optato per usare il truncated binary exponential backoff, l’algoritmo usato per modellare i ritardi nelle ritrasmissioni dei dati a seguito di collisioni nelle reti Ethernet.

Questo algoritmo è davvero semplice e per decriverlo, ancora una volta, mi affido alle parole del “sommo” Tanembaum:

“Invece di un polling continuo si può inserire un loop di ritardo fra i cicli di poll. Inizialmente il ritardo è di una istruzione, se il lock è ancora occupato, il ritardo è raddoppiato a due istruzioni, quindi a quattro, e così via fino a qualche massimo”.

Beh, direi che è tempo di mostrarvi un esempio, scritto appositamente per l’occasione…

Il codice

Il codice di esempi, scritto in C, è relativamente semplice.

Due tentano di acquisire un lock. Il primo che arriva, ottiene il lock ed esegue qualcosa di abbastanza lungo.

L’altro pthread, escluso, nel frattempo prova ad acquisire il lock attendendo via via tempi più lunghi secondo i dettami del’algoritmo TBEB.

/**
 *	FILE: TbebExample.c
 *	AUTHOR: Gian Paolo "JP" Ghilardi (http://rejex.wordpress.com)
 *	LICENSE: released under the terms of GPL v2.0 ("only")
 *	COMPILE: gcc -std=c99 -Wall -pedantic -lpthread -lm -D_GNU_SOURCE
 *	         -D_THREAD_SAFE TbebExample.c TbebLock.c -o TbebExample
 *	PURPOSE: simple example of pthread locking using the
 *	         Truncated Binary Exponential Backoff to model
 *	         waits
 *	VERSION: 1.0 (with templates)
 *
 *	TESTED ON:
 *	- MacOSX 10.5.6 PPC, GCC 4.0.1
 *	- Linux 2.4.18 x86-32, GCC 3.4.6
 *
 *	REFERENCES:
 *	[1]: http://en.wikipedia.org/wiki/Pthread
 *	[2]: http://www.llnl.gov/computing/tutorials/pthreads/
 *	[3]: http://en.wikipedia.org/wiki/Truncated_binary_exponential_backoff
 */

#include "TbebLock.h"

#define NUM_THREADS 2

pthread_t threads[NUM_THREADS];
pthread_mutex_t mutexsum;
pthread_attr_t attr;

// simulates a long job
void simulate_a_long_job(void)
{
	struct timeval t;

	for(long i=0; i<1000000; i++)
	{
		gettimeofday(&t, NULL);
	}
}

// pthread code: executed at pthread startup
void *thread_job(void *thread_id)
{
	int tid = (int)thread_id;

	printf("[%d]: try locking...\n", tid);

	srand((unsigned int) time(NULL));

	pthread_mutex_tbeb_lock(&mutexsum, tid);  // wait until we get the lock
		printf("[%d]: lock acquired!\n", tid);
		simulate_a_long_job();
	pthread_mutex_unlock(&mutexsum);          // lock release
	printf("[%d]: lock released...\n", tid);

	pthread_exit(NULL);
}

int main(int argc, char** argv)
{
	int t;
	int rc;

	printf("TBEB-BASED LOCKING EXAMPLE:\n");
	printf("Simple pthread locking example in C.\n\n");

	// pthread mutex initialization
	pthread_mutex_init(&mutexsum, NULL);
	pthread_attr_init(&attr);
	pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

	// create some threads
	for (t=0; t<NUM_THREADS; t++)
	{
		printf("[M]: creating thread %d\n", t);
		rc = pthread_create(&threads[t], NULL, thread_job, (void *) t);
		if (rc)
		{
			printf("[M]: ERROR cannot create the pthread! (code=%d)\n", rc);
			exit(EXIT_FAILURE);
		}
	}

	// wait for all pthreads to complete
	printf("[M]: joining threads...\n");
	for(t=0; t<NUM_THREADS; t++)
	{
		pthread_join(threads[t], NULL);
	}

	printf("[M]: job done...\n\n");
	pthread_mutex_destroy(&mutexsum);
	pthread_exit(NULL);

	return EXIT_SUCCESS;
}

/**
 *	FILE: TbebLock.c
 *	AUTHOR: Gian Paolo "JP" Ghilardi (http://rejex.wordpress.com)
 *	LICENSE: released under the terms of GPL v2.0 ("only")
 *	VERSION: 1.0 (with templates)
 *
 *	TESTED ON:
 *	- MacOSX 10.5.6 PPC, G++ 4.0.1
 *
 *	NOTE: for more info, please see file TbebExample.c
 */

#include "TbebLock.h"

// simple implementation of the Truncated Binary Exponential Backoff
// (TBEB) algorithm to handle sleep times
inline int tbeb_sleep(int curr_attempt, int thread_id)
{
	int rand_max;       // max slot times to sleep
	int num_slot_times; // random number of slot times to sleep (0 to 2^n-1)

	if(curr_attempt>0 && curr_attempt<=MAX_ATTEMPTS)
	{
		rand_max = (int)pow(2, curr_attempt);
		num_slot_times = rand() % rand_max;
	}
	else // (curr_attempt<=0 || curr_attempt>MAX_ATTEMPTS)
	{
		curr_attempt   = 0; //reset the counter
		rand_max       = 0;
		num_slot_times = 0;
	}

	printf("[%d]: %d slot times (max: %d)\n", thread_id, num_slot_times, rand_max);
	fflush(stdout);

	usleep(MSEC_TO_USEC * MSEC_PER_SLOT * num_slot_times);

	return ++curr_attempt;
}

/*
   simple TBEB-based mutex-locking call. This function
   blocks the caller until lock acquisition succeeds.

   NOTE: it's deliberately similar to the Btrfs locking code
   as described on LWN (http://lwn.net/Articles/313048/,
   "Btrfs aims for the mainline")
 */
int pthread_mutex_tbeb_lock(pthread_mutex_t *to_lock, int thread_id)
{
	int i=0;

	if (pthread_mutex_trylock(to_lock)==0)
	    return 0;
	for(ever)
	{
		i = tbeb_sleep(i, thread_id);
	    if (pthread_mutex_trylock(to_lock)==0)
	    	return 0;
	}
	return 0;
}

/**
 *	FILE: TbebLock.h
 *	AUTHOR: Gian Paolo "JP" Ghilardi (http://rejex.wordpress.com)
 *	LICENSE: released under the terms of GPL v2.0 ("only")
 *	VERSION: 1.0 (with templates)
 *
 *	TESTED ON:
 *	- MacOSX 10.5.6 PPC, G++ 4.0.1
 *
 *	NOTE: for more info, please see file TbebExample.c
 */

#ifndef TBEBLOCK_H_
#define TBEBLOCK_H_
	#include <stdio.h>
	#include <stdlib.h>
	#include <math.h>
	#include <pthread.h>
	#include <time.h>
	#include <unistd.h>
	#include <sys/time.h>

	#define MSEC_PER_SLOT 1    // sleep time in a slot (milliseconds)
	#define MAX_ATTEMPTS  6    // max attempts before resetting
	#define MSEC_TO_USEC  1000 // milliseconds to microseconds (factor)
	#define ever ;;

	int tbeb_sleep(int, int);
	int pthread_mutex_tbeb_lock(pthread_mutex_t *, int);
#endif /* TBEBLOCK_H_ */

L’esempio dal vivo

Nota: per ragioni “fotografiche” ho eseguito il programma con solo 2 thread attivi. Potete ovviamente alzarne il numero a piacere modificando il valore di NUM_THREADS e ricompilando [testato con 5 e 10 thread].

Ciau!