On 01.07.2013 19:08, Edek wrote:
> Część teraz...
>
> Dnia pamiętnego Mon, 01 Jul 2013 18:24:17 +0200, Michoo wyjmując peta
> oznajmił:
>

>> Co do samego algorytmu - potrzebne są trzy stany:
>> przed_inicjalizacją, w_trakcie, po_inicjalizacji, nie da się tego zrobić
>> na JEDNEJ fladze binarnej, można by użyć dwóch(i wprowadzić odpowiednie
>> poprawki), ale po co?
>
> Nie, jest potrzebna monotonicznie rosnąca liczba, nie trzy stany. Mi
> to zajęło z pół godziny żeby dojść dlaczego: spróbuj zastąpić
> monotonicznie rosnącą stanami i albo udowodnij poprawność
> albo udowodnij że jest problem.

#define START_VALUE 2
#define BEING_INITIALIZED 1
#define INIT_DONE 0

/* PRECONDITION:
*once == START_VALUE
*/

void fast_pthread_once( fast_pthread_once_t *once, void (*func)(void) )
{
/*01*/ if ( *once != INIT_DONE ) {
/*02*/ check( pthread_mutex_lock(&mu) == 0 );
/*03*/ if ( *once == START_VALUE ) {
/*04*/ *once = BEING_INITIALIZED;
/*05*/ check( pthread_mutex_unlock(&mu) == 0 );
/*06*/ (*func)();
/*07*/ check( pthread_mutex_lock(&mu) == 0 );
/*08*/ *once = INIT_DONE;
/*09*/ check( pthread_cond_broadcast(&cv) == 0 );
/*10*/ } else {
/*11*/ while ( *once != INIT_DONE ) {
/*12*/ check( pthread_cond_wait(&cv, &mu) == 0 );
/*13*/ }
/*14*/ }
/*15*/ check (pthread_mutex_unlock(&mu) == 0);
/*16*/ }
}

Wszystkie zapisy i odczyty (poza linią 01) są chronione muteksem. Tak więc:
A) w lini 01 może zostać albo odczytana wartość początkowa, wartość z
linii 04 lub 08
- w przypadku odczytu INIT_DONE pomijamy cały blok - inicjalizacja
została już wykonana
- w przypadku odczytu innej wartości rozpoczynamy blok synchronizowany B

B) w linii 03 może zostać albo odczytana wartość początkowa, wartość z
linii 04 lub 08
- w przypadku wartości innej niż START_VALUE oczekujemy w liniach 11,12
na zakończenie inicjalizacji [*] (deadlock przy wywołaniu rekurencyjnym)
- w przypadku wartości START_VALUE zmieniamy ją na BEING_INITIALIZED i
kończymy blok synchronizowany - od tego momentu żaden wątek w 01 ani 03
nie odczyta wartości START_VALUE
- Po zakończeniu inicjalizacji zapisujemy *once = INIT_DONE i wybudzamy
wątki czekające w linii 12 - od tego momentu nie zostanie odczytana inna
wartość niż INIT_DONE

Czekające wątki po kolei kończą oczekiwanie 12->11->15.

[*] Jeżeli wartość zmieniła się na INIT_DONE po odczycie w linii 01 ale
przed otrzymaniem muteksu to nie czekamy w linii 12 tylko kończymy na 15.

Pisane na szybko więc co przeoczyłem?

> Ja potrafię to drugie.
>
Poproszę.

--
Pozdrawiam
Michoo