Wzajemne wykluczanie

Wirujące blokady

Wirujące blokady są używane tylko w systemach wieloprocesorowych i służą do blokowania zasobów innym procesorom. Z założenia musi w nich występować aktywne czekanie. Ich działanie opiera się na dwóch operacjach: spin_lock i spin_unlock. Spin_lock sprawdza, czy blokada jest otwarta; jeśli tak - zamyka ją (i proces może wejść do sekcji krytycznej); jeśli nie - sprawdza jeszcze raz. Operacja spin_unlock to otwarcie blokady.

Definicje typu spinlock_t i najważniejszych operacji na nim znajduję się w pliku include/asm-i386/spinlock.h. W poniższych fragmentach wycięto instrukcje preprocesora związane w debugowaniem, oraz obsługujące przypadki systemów jednoprocesorowych i nietypowych wieloprocesorowych (PPro SMP, OOSTORE).

typedef struct { volatile unsigned int lock;} spinlock_t;

Jak widać, spinlock_t przypomina atomic_t i. Inicjalizacja wygląda następująco:

#define spin_lock_init(x)	do { (x)->lock = 0; } while(0)

Pętla jest zastosowana w celu przechytrzenia kompilatora - jej znaczenie jest tylko syntaktyczne. Na początku wartość lock jest równa 0. Jest ona zerem wtedy i tylko wtedy, gdy spinlock jest otwarty. Kiedy blokada jest zamknięta, zerowy bit zmiennej lock jest ustawiony. Pozostałe bity są zawsze wyzerowane.

Po tym wstępie pora na kod w asemblerze - implementacja operacji spin_lock.

extern inline void spin_lock(spinlock_t *lock)
{
	__asm__ __volatile__(
		spin_lock_string
		:"=m" (__dummy_lock(lock)));
}

#define spin_lock_string \
		"\n1:\t" \
		"lock ; btsl $0,%0\n\t" \
		"jc 2f\n" \
		".section .text.lock,\"ax\"\n" \
		"2:\t" \
		"testb $1,%0\n\t" \
		"jne 2b\n\t" \
		"jmp 1b\n" \
		".previous"

Ten kod wykona się w następujący sposób:

• zostanie wykonana niepodzielna operacja test and set (btsl) na zerowym bicie (zerowego argumentu, czyli zmiennej lock). Zwróci ona dotychczasową wartość tego bitu i ustawi na 1.

• Jeśli dotychczasową wartością było 1, to znaczy, że blokada jest zamknięta; następuje skok do etykiety 2; tutaj proces aktywnie czeka, aż zerowy bit zmiennej zostanie wyzerowany (stanie się równy pierwszemu); kiedy tak się stanie, następuje powrót do etykiety 1 i czyli ponowna próba przejęcia blokady;

• Jeśli dotychczasową wartością było 0, to znaczy, że blokada była otwarta i można wejść do sekcji krytycznej; w tym wypadku następuje przejście do wykonywania instrukcji umieszczonej za napisem ".previous"jeśli bity były równe, to znaczy, że blokada była zamknięta w momencie wykonywania test and set i należy aktywnie czekać na jej zwolnienie;

Na pozór ten sam efekt możnaby uzyskać zakładając pętlę na atomową instrukcję test and set. W rzeczywistości jednak prowadziłoby to spowolnienia pracy całego komputera. Instrukcja testb jest podczas aktywnego oczekiwania wykonywana na wartości sprowadzonej z pamięci cache procesora. Natomiast wywołanie operacji test and set powoduje zapisanie nowej wartości w pamięci operacyjnej nawet jeśli w rzeczywistości wcale nie zmieniła wartości danego bitu. Dlatego jej ciągłe powtarzanie zwiększałoby (znacznie) obciążenie magistrali i w rezultacie powodowałoby spowolnienie pracy całego komputera.

Operacja spin_unlock, zgodnie z oczekiwaniami, jest jeszcze prostsza.

extern inline void spin_unlock(spinlock_t *lock)
{
	__asm__ __volatile__(
		spin_unlock_string
		:"=m" (__dummy_lock(lock)));
}

#define spin_unlock_string \
	"lock ; btrl $0,%0"

Instrukcja btrl resetuje zerowy bit zmiennej lock i ustawia flagę CF na jego poprzednią wartość. Może to być wykorzystane do debugowania kodu.

Dodatkowo mamy zdefiniowane liczne makra rozszerzające funkcjonalność wirujących blokad. Na przykład spin_lock_irqsave zapamiętuje flagi na podanej zmiennej, blokuje przerwania (cli) i wykonuje operację spin_lock.

#define local_irq_save(x)	__asm__ __volatile__("pushfl ;\
	popl %0 ; cli":"=g" (x): /* no input */ :"memory") 

#define local_irq_restore(x)	__asm__ __volatile__("pushl %0 ;\
	popfl": /* no output */ :"g" (x):"memory") 

#define spin_lock_irqsave(lock,  flags) \
	do { local_irq_save(flags); spin_lock(lock); } while (0) 

#define spin_unlock_irqrestore(lock,  flags) \
	do { spin_unlock(lock); local_irq_restore(flags); } while (0) 

Semafory

Przedstawione fragmenty pochodzą z pliku include/asm-i386/semaphore.h pozbawione są instrukcji związanych z debugowaniem.

struct semaphore {
	atomic_t count;
	int sleepers;
	wait_queue_head_t wait;
};

extern inline void down(struct semaphore * sem)
{
	__asm__ __volatile__(
		"# atomic down operation\n\t"
		LOCK "decl (%0)\n\t"    // --sem->count 
		"js 2f\n"             	
		"1:\n"
		".section .text.lock,\"ax\"\n" 
		"2:\tcall __down_failed\n\t"
		"jmp 1b\n"	
		".previous"	
		:/* no outputs */	
		:"c" (sem)	
		:"memory");
}

Powyższy kod działa jak następuje:

• Zmniejsza licznik przy zablokowanej magistrali (zatem jest to operacja atomowa);

• Sprawdza, czy po zmniejszeniu licznik jest ujemny;

• Jeśli nie, to proces przechodzi dalej (za napis ".previous"), do sekcji krytycznej.

• Jeśli tak, to nie można wejść do sekcji krytycznej; następuje przejście do __down_failed; funkcja ta usypia proces; po przebudzeniu proces wchodzi do sekcji krytycznej.

Podnoszenie semafora:

extern inline void up(struct semaphore * sem)
{
	__asm__ __volatile__(
		"# atomic up operation\n\t"
		LOCK "incl (%0)\n\t"     // ++sem->count 
		"jle 2f\n"
		"1:\n"
		".section .text.lock,\"ax\"\n"
		"2:\tcall __up_wakeup\n\t"
		"jmp 1b\n"
		".previous"
		:/* no outputs */
		:"c" (sem)
		:"memory");
}

Najpierw atomowo zwiększany jest licznik (sem->count). Jeśli po zwiększeniu będzie ujemny lub równy 0, to następuje przejście do globalnej etykiety __up_wakeup, skąd wywoływana jest funkcja budząca pierwszy uśpiony proces z kolejki, napisana w C.