SPIN-LOCK - Meziprocesorový zámek

Jedním z nejobtížnějších problémů, které musí operační systém řešit, je synchronizace činnosti více procesorů. Nemusí se přitom jednat fyzicky o několik procesorů, mohou to být i vícejádrové procesory nebo procesory se sdílenými funkcemi.

Nejstarší známou synchronizací částí kódu je řešení kolize mezi obsluhou přerušení a hlavním kódem. Tento souběh může nastat i u systému s jedním procesorem.

Například - program načte jednou instrukcí vyšší slovo čítače času, poté další instrukcí nižší slovo (jedná se o příklad, procesor x86 by jinak načetl DWORD jednou operací, ale podobný problém by vznikl čtením QWORD). Mezi těmito 2 instrukcemi přijde přerušení od systémového časovače, jehož obsluha obsah čítače času inkrementuje a to tak, že se nižší slovo změní z hodnoty 0FFFFh na 0 a vyšší slovo z hodnoty 123h na 124h. Hlavní kód tedy v tomto případě nenačte původní hodnotu 123FFFFh ani novou hodnotu 1240000h, ale obdrží nesprávný údaj 1230000h. Tuto situaci řeší zákaz přerušení, instrukce CLI, kterou může být kritický úsek kódu uzamknut.

Zpravidla funkce nepoužívají spárované instrukce CLI a STI pro zákaz a povolení přerušení, protože mohou být volány z míst, kde bylo přerušení již zakázáno. Proto je na začátku funkce uchován registr příznaků (který obsahuje příznak povolení přerušení), instrukcí CLI přerušení zakázáno a na konci funkce je registr příznaků opět obnoven. Tím je přerušení opět povoleno, pokud bylo povoleno před voláním funkce.

Nejnižší úrovní, kterou musí operační systém řešit, je synchronizace přístupu procesorů k paměti. Při sdílení paměti mezi více procesory (nebo více jádry procesoru) může nastat případ, kdy více procesorů provádí současně nějakou operaci se stejným paměťovým místem, jednotlivé úkony se překryjí a dojde tak k nesprávnému výsledku či vyhodnocení operace.

Například dva procesory dekrementují čítač pomocí instrukce "DEC [pamet]" a testují, kterému z procesorů se podařilo dosáhnout nulového stavu čítače:

CPU1	CPU2
načte obsah paměťové proměnné (hodnota = 1)	-
-	načte obsah paměťové proměnné (hodnota = 1)
dekrementuje načtené číslo (hodnota -> 0)	-
-	dekrementuje načtené číslo (hodnota -> 0)
uloží novou hodnotu čísla (hodnota = 0)	-
-	uloží novou hodnotu čísla (hodnota = 0)

V tomto příkladu souběhu byla proměnná 2x dekrementována, přitom se ale její hodnota změnila z 1 na 0 a oba procesory se domnívají, že dosáhly hodnoty 0 čítače.

Instrukce, jejichž provedení je nepřerušitelné a provedou se najednou celé (neovlivněné jiným procesorem), označujeme jako atomické operace. Není-li operace atomická a hrozí-li nebezpečí souběhu procesorů, můžeme během jejího provádění uzamknout sběrnici pomocí prefixu LOCK, který zajistí atomičnost instrukce. Instrukce XCHG automaticky uzamyká sběrnici a nevyžaduje použití prefixu LOCK.


%define	SMP				; flag-enable symetric multiprocessors

; ------------- Macro - CPU instruction lock (only SMP mode)

%macro		LOCKSMP 0
%ifdef	SMP
		lock			; CPU instruction lock
%endif
%endmacro

Při překladu jádra Litosu lze zvolit zjednodušenou variantu překladu (MINI), která nezajišťuje podporu více procesorů. Podporu více procesorů umožní přepínač SMP. Makro LOCKSMP lze použít na místech, kde je potřeba uzamknout sběrnici procesoru, zámek je použit pouze v případě, že je povolena podpora více procesorů. Příklad použití prefixu lock bude patrný v následujícím popisu meziprocesorového zámku spin-lock.

Vyšší úrovní, kde může nastat souběh více procesorů, jsou datové struktury sdílené mezi procesory. Uzamknutí sběrnice prefixem LOCK zabrání souběhu procesorů pouze po dobu jedné instrukce, nezabrání však modifikaci datových struktur pomocí více instrukcí. K tomuto účelu slouží meziprocesorové zámky. Jejich funkce spočívá v tom, že před přístupem ke kritickým oblastem procesor uzamkne zámek (nastaví příznak, že přistupuje ke kritické oblasti) a po ukončení přístupu zámek opět odemkne. Pokud jiný procesor chce přistupovat současně ke stejné oblasti dat, zjistí že zámek je již uzamknutý a poté opakovaně cykluje v testovací smyčce až do doby, než je zámek opět odemknut (od toho je odvozen jeho název, spin-lock = "točící se zámek").

Při použití zámku spin-lock je potřeba pamatovat na to, že nesmí být uzamknut současně jedním procesorem dvakrát, jinak procesor skončí v nekonečné čekací smyčce. Proto je potřeba před uzamknutím zámku spin-lock zakázat přerušení, aby nedošlo k pokusu o uzamknutí zámku stejným procesorem z obsluhy přerušení.

Meziprocesorový zámek je potřeba odlišovat od zámků mezi procesy, které jsou běžné při programování aplikací. Zámek mezi procesy během čekání na uvolnění zámku necykluje na místě, ale předá řízení operačnímu systému, který čekací čas využije k jiným činnostem nebo přejde do stavu spánku. Obsluha meziprocesorového zámku musí být rychlá (protože se jedná o velmi krátké úseky v jádru operačního systému), během této doby by bylo neefektivní přecházet k jiným činnostem.


SPINLOCK_size	EQU	4		; size of spin-lock

Strukturu meziprocesorového zámku spin-lock tvoří proměnná typu double-word. Z proměnné je sice využíván pouze nejspodnější bit 0, ale velikost proměnné je zachována jednak kvůli kompatibilitě a jednak kvůli zarovnání položek ve strukturách. Je-li bit 0 zámku vynulován, je zámek odemknut. Je-li bit 0 nastaven, zámek je uzamknut některým procesorem.


%define		SPINLOCK  dd	0	; macro - initialized spin-lock

Makro SPINLOCK vytvoří inicializovaný spin-lock. Makro nepoužívá žádný parametr.


; ------------- Macro - initialize spin-lock (%1 = pointer)

%macro		LOCK_Init 1
%ifdef	SMP
		and	dword [%1],byte 0 ; initialize spin-lock
%endif
%endmacro

Pomocí makra LOCK_Init lze zámek inicializovat. Parametrem makra je ukazatel na popisovač zámku. Proměnná zámku se nastaví na hodnotu 0, což je příznak vypnutého stavu zámku.


; ------------- Macro - lock spin-lock (%1 = pointer or address)

%macro		LOCK_Lock 1
%ifdef	SMP
%%L1:		lock			; CPU instruction lock
		bts	dword [%1],0	; try to lock spin-lock
		jc	%%L1		; next try to lock spin-lock
%endif
%endmacro

Makro LOCK_Lock slouží k uzamknutí zámku. Je použita instrukce BTS, která nejdříve otestuje bit 0 zámku a nastaví podle jeho stavu stavový bit CF (stav CY pokud byl bit 0 nastaven a stav NC pokud nebyl nastaven) a potom bit 0 zámku nastaví. Instrukce používá prefix LOCK, který zajistí uzamknutí sběrnice během provádění instrukce, aby nenastal souběh s jiným procesorem. Pokud byl zámek před testem již uzamknut (tj. stav CY), procesor se vrací a cyklicky ve smyčce neustále testuje uvolnění zámku a pokouší se zámek sám uzamknout. Pokud nebyl zámek zamknut (tj. stav NC), zajistí instrukce BTS uzamknutí zámku a funkce může pokračovat dále.

Uzamykací funkce se mírně liší od obvykle používaných variant zámků v jiných operačních systémech. Především během čekání na uvolnění zámku není volána obvyklá SSE2 instrukce "pause" ("rep nop"), která má sloužit k odlehčení procesoru během čekání. Dále je i během čekání vyvolávána instrukce s prefixem LOCK, což vede k častému uzamykání sběrnice a tedy ke snížení výkonu ostatních procesorů. Důvodem pro obě zjednodušení je to, že zámek se používá k uzamykání kritických sekcí jádra systému, které jsou skutečně velmi krátké a rychlé a je tudíž velmi malá šance výskytu souběhu více procesorů, přednost má proto snaha o maximalizaci rychlosti kódu pro případ, že souběh nenastane.


; ------------- Macro - try to lock spin-lock, returning CY
; %1 = pointer or address, returns CY = cannot lock

%macro		LOCK_TryLockC 1
%ifdef	SMP
		lock			; CPU instruction lock
		bts	dword [%1],0	; try to lock spin-lock
%else
		clc			; wihout SMP locked OK
%endif
%endmacro

Pomocí makra LOCK_TryLockC lze zámek uzamknout v případě, že není uzamknut. Pokud je zámek již uzamknut jiným procesorem, funkce nečeká, ale navrátí příznak chyby CY. Navrátí-li příznak NC, zámek byl úspěšně uzamknut.


; ------------- Macro - try to lock spin-lock
; %1 = pointer or address, %2 = address to jump if spin-lock cannot be locked

%macro		LOCK_TryLock 2
%ifdef	SMP
		lock			; CPU instruction lock
		bts	dword [%1],0	; try to lock spin-lock
		jc	%2		; spin-lock was already locked
%endif
%endmacro

Pomocí makra LOCK_TryLock lze zámek uzamknout v případě, že není uzamknut. Pokud je zámek již uzamknut jiným procesorem, funkce nečeká, ale pokračuje skokem na adresu předanou jako druhý parametr makra.


; ------------- Macro - unlock spin-lock (%1=pointer or address, saves FLAGS)

%macro		LOCK_Unlock 1
%ifdef	SMP
		mov	byte [%1],0	; unlock spin-lock
%endif
%endmacro

Makro LOCK_Unlock odemkne zámek. Ukazatel na zámek je předán jako parametr makra.