RSS

Semafory — niedoceniany środek synchronizacji

Liczba odsłon: 661

Programis­ta two­rzą­cy apli­ka­cję wie­lo­wąt­ko­wą lub wie­lo­pro­ce­so­wą ma do dys­po­zyc­ji wie­le róż­nych me­cha­niz­mów syn­chro­ni­za­cji jed­no­czes­ne­go do­stę­pu do za­so­bów. Jednymi z rza­dziej sto­so­wa­nych, a częs­to bar­dzo przy­dat­nych środ­ków syn­chro­ni­zo­wa­nia do­stę­pu są se­ma­fo­ry.

Podstawo­wym za­da­niem se­ma­fo­ra jest ogra­ni­cza­nie licz­by użyt­kow­ni­ków za­so­bu. Być mo­że to jest przy­czy­ną je­go rzad­kie­go wy­ko­rzys­ta­nia: częs­to pro­gra­mi­ście bar­dziej za­le­ży na wy­kry­wa­niu mo­men­tu, w któ­rym za­sób nie jest uży­wa­ny, a nie (co umoż­li­wia­ją se­ma­fo­ry) mo­men­tu, w któ­rym jest w peł­ni (do gra­nic) wy­ko­rzy­sta­ny. Krótko mó­wiąc, se­ma­for jest licz­ni­kiem zmie­rza­ją­cym od pew­nej war­toś­ci do ze­ra (któ­re­go nie mo­że prze­kro­czyć).

Operacje na se­ma­fo­rze

Do se­ma­fo­rów sto­su­ją się na­stę­pu­ją­ce ope­rac­je ele­men­tar­ne:

Semafor ja­ko mu­teks

W szcze­gól­nym przy­pad­ku, gdy li­mit war­toś­ci se­ma­fo­ra wy­no­si je­den, se­ma­for jest funkcjo­nal­nym od­po­wied­ni­kiem mu­tek­su (ang. mutex). Semafor ta­ki do­pusz­cza tyl­ko jed­ne­go użyt­kow­ni­ka za­so­bu, wstrzy­mu­jąc wszyst­kich po­zo­sta­łych.

Ponie­waż mu­teks jest struk­tu­rą prost­szą niż se­ma­for, sto­so­wa­nie se­ma­fo­rów w ro­li mu­tek­sów jest nie­opty­mal­ne i nie­uza­sad­nio­ne.

Semafor ja­ko śro­dek syn­chro­ni­za­cji we­wnątrz­pro­ce­so­wej

Semafor bez okreś­lo­nej naz­wy sta­je się środ­kiem syn­chro­ni­za­cji we­wnątrz­pro­ce­so­wej. Istnieje we­wnątrz prze­strze­ni adre­so­wej pro­ce­su i mo­że być wy­ko­rzys­ty­wa­ny pod wa­run­kiem zna­jo­moś­ci adre­su struk­tu­ry opi­su­ją­cej go, lub je­go uni­ka­to­we­go iden­ty­fi­ka­to­ra. Z te­go po­wo­du nie na­da­je się do prze­ka­zy­wa­nia go in­nym pro­ce­som: na­wet, gdy­by uda­ło się prze­słać im adres struk­tu­ry, był­by on bez­war­to­ścio­wy w in­nej prze­cież prze­strze­ni adre­so­wej.

Wykorzy­sta­nie we­wnątrz­pro­ce­so­we umoż­li­wia sys­te­mo­wi ope­ra­cyj­ne­mu sto­so­wa­nie wie­lu opty­ma­li­zac­ji. W naj­prost­szym przy­pad­ku se­ma­for we­wnątrz­pro­ce­so­wy skła­da się z sek­cji kry­tycz­nej (blo­ku­ją­cej do­stęp wie­lu wąt­ków jed­ne­go pro­ce­su do wspól­ne­go za­so­bu) oraz licz­ni­ka. System opera­cyj­ny mo­że też wy­ko­rzys­tać me­cha­nizm ope­rac­ji nie­po­dziel­nych (ato­mo­wych), by bez­po­śred­nio mo­dy­fi­ko­wać i po­rów­ny­wać stan licz­ni­ka se­ma­fo­ru bez an­ga­żo­wa­nia po­waż­niej­szych środ­ków syn­chro­ni­za­cyj­nych i wpro­wa­dza­nia zbęd­ne­go na­rzu­tu.

Semafor ja­ko śro­dek ko­mu­ni­kac­ji mię­dzy­pro­ce­so­wej

Semafor mo­że zo­stać stwo­rzo­ny w for­mie glo­bal­nej. W ta­kim przy­pad­ku jest iden­ty­fi­ko­wa­ny al­bo za po­mo­cą glo­bal­nie uni­ka­to­we­go iden­ty­fi­ka­to­ra licz­bo­we­go (uch­wy­tu, ang. handle), al­bo za po­mo­cą uni­ka­to­wej naz­wy na­da­nej pod­czas two­rze­nia obiek­tu se­ma­fo­ra.

Identyfi­ka­tor se­ma­fo­ra mo­że być w ta­kim przy­pad­ku prze­ka­zy­wa­ny mię­dzy pro­ce­sa­mi, a sam se­ma­for mo­że słu­żyć do za­rzą­dza­nia do­stę­pem wie­lu pro­ce­sów do wspól­ne­go za­so­bu. Niesie to ze so­bą im­pli­ka­cje wy­daj­noś­cio­we: obiekt se­ma­fo­ra nie mo­że być w ta­kim przy­pad­ku za­rzą­dza­ny we­wnętrz­nie przez sam pro­ces (za po­mo­cą ope­rac­ji nie­po­dziel­nych), tyl­ko mu­si być za­pi­sa­ny w pa­mię­ci try­bu jąd­ra (do­stęp­nej w prze­strze­niach adre­so­wych wszyst­kich pro­ce­sów). Sprawia to rów­nież, że od­czyt i mo­dy­fi­ka­cja pól struk­tu­ry opi­su­ją­cej se­ma­for mu­szą od­by­wać się za po­śred­nic­twem uprzy­wi­le­jo­wa­nych funk­cji sys­te­mo­wych, wy­wo­ły­wa­nych z przej­ściem mię­dzy­warst­wo­wym. Zwiększa to koszt akwi­zy­cji lub zwol­nie­nia se­ma­fo­ra z po­je­dyn­czych cyk­li ze­ga­ro­wych do se­tek lub ty­się­cy cyk­li.

Dziele­nie se­ma­fo­ra przez wie­le pro­ce­sów po­wo­du­je po­ja­wie­nie się sze­re­gu dy­le­ma­tów nie­obec­nych w przy­pad­ku syn­chro­ni­za­cji we­wnątrz­pro­ce­so­wej. Semafor mię­dzy­pro­ce­so­wy mu­si być prze­de wszyst­kim od­por­ny na awa­ryj­ne za­koń­cze­nie pra­cy przez je­den z pro­ce­sów-klien­tów: je­że­li pro­ces uległ awarii w cza­sie, gdy ko­rzy­stał z se­ma­fo­ra, wspól­ny za­sób chro­nio­ny se­ma­fo­rem mógł zo­stać usz­ko­dzo­ny lub wpro­wa­dzo­ny w nie­zna­ny lub nie­sta­bil­ny stan. Rozwią­za­niem jest in­for­mo­wa­nie każ­de­go z pro­ce­sów ocze­ku­ją­cych na ten sam se­ma­for, że zwol­nie­nie za­so­bu (i wzno­wie­nie pra­cy ocze­ku­ją­ce­go na ten za­sób pro­ce­su) na­stą­pi­ło w efek­cie awarii jed­ne­go z użyt­kow­ni­ków. Procesy mo­gą zigno­ro­wać ten syg­nał i ko­rzy­stać z za­so­bu bez zmian lub – je­że­li sytu­acja ta­ka fak­tycz­nie mog­ła do­pro­wa­dzić do za­bu­rze­nia sta­nu za­so­bu – przer­wać ope­ra­cję lub za­koń­czyć swo­ją pra­cę w imię chę­ci za­cho­wa­nia sta­bil­noś­ci pra­cy.

Jeszcze po­waż­niej­szym prob­le­mem jest za­koń­cze­nie pra­cy pro­ce­su, któ­ry spo­wo­do­wał utwo­rze­nie se­ma­fo­ra. W za­leż­noś­ci od im­ple­men­tac­ji mo­że to spo­wo­do­wać za­koń­cze­nie pra­cy wszyst­kich pro­ce­sów ko­rzy­sta­ją­cych z te­go se­ma­fo­ra lub po­zos­ta­wie­nie se­ma­fo­ra w pa­mię­ci aż do mo­men­tu, gdy za­koń­czy pra­cę ostat­ni ko­rzy­sta­ją­cy z nie­go pro­ces. W tym dru­gim przy­pad­ku jed­nak ist­nie­je ry­zy­ko, że wciąż ist­nie­ją­cy se­ma­for bę­dzie bro­nił do­stę­pu do nie­istnie­ją­ce­go już za­so­bu, rów­nież ob­słu­gi­wa­ne­go przez za­koń­czo­ny pro­ces.

Implemen­ta­cja se­ma­fo­rów w sys­te­mie Win­dows

W sys­te­mie Win­dows utwo­rze­nie se­ma­fo­ra wy­ma­ga wy­wo­ła­nia funk­cji:

HANDLE sem = CreateSemaphore(NULL, init, max, NULL);

gdzie init okre­śla po­cząt­ko­wy stan licz­ni­ka se­ma­fo­ra (w za­kre­sie od 0 do max), a max — li­mit war­toś­ci licz­ni­ka. Tak utwo­rzo­ny se­ma­for jest nie­naz­wa­ny, mo­że być za­tem iden­ty­fi­ko­wa­ny je­dy­nie za po­mo­cą uch­wy­tu (uży­cie uch­wy­tu w in­nym pro­ce­sie nie­po­tom­nym wy­ma­ga uży­cia funk­cji DuplicateHandle()).

Aby stwo­rzyć se­ma­for naz­wa­ny, wy­star­czy po­dać naz­wę ja­ko ostat­ni pa­ra­metr, na przy­kład:

HANDLE sem = CreateSemaphore(NULL, 10, 10, TEXT("Semafor1"));

Od te­go mo­men­tu in­ne pro­ce­sy mo­gą uzys­ki­wać do­stęp do naz­wa­ne­go se­ma­fo­ra, wy­wo­łu­jąc po pros­tu funk­cję OpenSemaphore() z po­da­ną naz­wą se­ma­fo­ra:

HANDLE sem = OpenSemaphore(SYNCHRONIZE | SEMAPHORE_MODIFY_STATE,
                           FALSE, TEXT("Semafor1"));

Niezależnie od te­go, czy pro­ces sam stwo­rzył se­ma­for, czy uzys­kał do nie­go do­stęp za po­mo­cą DuplicateHandle() czy OpenSemaphore(), uzys­ka­ny uch­wyt mu­si zo­stać zwol­nio­ny za po­mo­cą CloseHandle().

Aby do­ko­nać akwi­zy­cji za­so­bu (zmniej­sze­nia war­toś­ci licz­ni­ka se­ma­fo­ra o je­den), na­le­ży wy­wo­łać funk­cję ocze­ki­wa­nia na do­stęp­ność obiek­tu:

DWORD x = WaitForSingleObject(sem, INFINITE);

Zwraca ona war­tość WAIT_OBJECT_0 je­że­li za­sób zo­stał za­blo­ko­wa­ny (a war­tość licz­ni­ka se­ma­fo­ra zmniej­szo­na o je­den), WAIT_ABANDONED, je­że­li se­ma­for zo­stał zwol­nio­ny na sku­tek awarii jed­ne­go z je­go użyt­kow­ni­ków, lub WAIT_TIMEOUT, je­że­li mi­nął do­zwo­lo­ny czas ocze­ki­wa­nia na akwi­zy­cję za­so­bu (po­da­wa­ny ja­ko ostat­ni pa­ra­metr funk­cji WaitForSingleObject(); war­tość INFINITE ozna­cza ocze­ki­wa­nie bez koń­ca). Inne war­toś­ci in­for­mu­ją o błę­dzie wy­wo­ła­nia funk­cji.

Aby zwol­nić za­sób i z po­wro­tem zwięk­szyć war­tość licz­ni­ka se­ma­fo­ra, na­le­ży wy­wo­łać funk­cję ReleaseSemaphore():

ReleaseSemaphore(sem, 1, NULL);

Zamiast war­toś­ci 1 moż­na po­dać in­ną, o ja­ką ma być zwięk­szo­ny stan licz­ni­ka se­ma­fo­ra (jed­nak je­dy­nym spo­so­bem zmniej­sze­nia war­toś­ci licz­ni­ka o wię­cej niż 1 jest wy­wo­ła­nie WaitForSingleObject() w pęt­li).

Implemen­ta­cja se­ma­fo­rów w sys­te­mie Linux

System Linux za­wie­ra po stro­nie ko­du użyt­kow­ni­ka im­ple­men­tac­ję se­ma­fo­rów zgod­ną ze stan­dar­dem POSIX. Rozdziela ona za­sad­ni­czo se­ma­fo­ry naz­wa­ne i nie­na­zwa­ne.

Aby stwo­rzyć ano­ni­mo­wy se­ma­for, na­le­ży za­de­kla­ro­wać struk­tu­rę ty­pu sem_t i wy­wo­łać funk­cję sem_init():

sem_t sem;
sem_init(&sem, 0, init);

Wartość 0 ozna­cza, że se­ma­for ma być prze­zna­czo­ny wy­łącz­nie do użyt­ku we­wnątrz­pro­ce­so­we­go. Aby moż­li­we by­ło ko­rzy­sta­nie z nie­go do ce­lów syn­chro­ni­za­cji mię­dzy­pro­ce­so­wej, na­le­ży umieś­cić zmien­ną sem w blo­ku pa­mię­ci współ­dzie­lo­nej i użyć war­toś­ci 1 w miej­sce 0. Wartość init, jak w przy­pad­ku sys­te­mu Win­dows, okre­śla po­cząt­ko­wą war­tość licz­ni­ka se­ma­fo­ra; w prze­ci­wień­stwie jed­nak do sys­te­mu Win­dows, nie ma moż­li­woś­ci okre­śle­nia li­mi­tu war­toś­ci se­ma­fo­ra.

Aby do­ko­nać akwi­zy­cji za­so­bu i zmniej­sze­nia war­toś­ci licz­ni­ka se­ma­fo­ra, na­le­ży użyć jed­nej z dwóch funk­cji. Funkcja sem_wait() wstrzy­mu­je dzia­ła­nie pro­gra­mu tak dłu­go, aż moż­li­we sta­nie się uzys­ka­nie do­stę­pu do za­so­bu. Z kolei funk­cja sem_trywait() do­ko­nu­je akwi­zy­cji za­so­bu tyl­ko w przy­pad­ku, gdy jest to na­tych­miast moż­li­we; w prze­ciw­nym ra­zie pro­gram jest na­tych­miast wzna­wia­ny, jed­nak funk­cja zwra­ca war­tość EAGAIN ozna­cza­ją­cą, że za­sób nie zo­stał prze­ję­ty i na­le­ży po­no­wić pró­bę.

Gdy wą­tek za­koń­czy ko­rzy­sta­nie z chro­nio­ne­go za­so­bu, wy­wo­ła­nie funk­cji sem_post() umoż­li­wia zwięk­sze­nie war­toś­ci licz­ni­ka se­ma­fo­ra o je­den i do­pusz­cze­nie ocze­ku­ją­cych wąt­ków do za­so­bu. Z kolei funk­cja sem_destroy() nisz­czy se­ma­for pod wa­run­kiem, że ża­den z wąt­ków nie ocze­ku­je na zwol­nie­nie za­so­bu (w ta­kim przy­pad­ku efekt ope­rac­ji mo­że być nie­prze­wi­dy­wal­ny).

Utworzenie naz­wa­ne­go se­ma­fo­ra, wy­ko­rzys­ty­wa­ne­go przez wie­le pro­ce­sów, prze­bie­ga cał­ko­wi­cie od­mien­nie. Stworze­nie se­ma­fo­ra na­stę­pu­je w efek­cie wy­wo­ła­nia:

sem_t *sem = sem_open("/var/lock/Semafor1", O_CREAT);

Natomiast po­zo­sta­łe pro­ce­sy za­miast O_CREAT po­da­ją war­tość 0:

sem_t *sem = sem_open("/var/lock/Semafor1", 0);

Zamknię­cie se­ma­fo­ra otwar­te­go przez pro­ce­sy-kli­en­ty na­stę­pu­je w efek­cie wy­wo­ła­nia funk­cji sem_close(). Proces two­rzą­cy se­ma­for nisz­czy go wy­wo­łu­jąc do­dat­ko­wo funk­cję sem_unlink(), po­bie­ra­ją­cą ja­ko pa­ra­metr już nie adres struk­tu­ry, lecz naz­wę se­ma­fo­ra. Oczywiś­cie ko­rzy­sta­nie z naz­wa­ne­go se­ma­fo­ra od­by­wa się za po­mo­cą po­zna­nych już wcześ­niej funk­cji sem_wait(), sem_trywait() oraz sem_post().

Wadą po­wyż­sze­go roz­wią­za­nia jest brak li­mi­tu war­toś­ci se­ma­fo­ra. Twórcy inter­fej­su za­ło­ży­li, że pra­wid­ło­wo pi­sa­ne opro­gra­mo­wa­nie zaw­sze zwal­nia se­ma­for ty­le ra­zy, ile ra­zy do­ko­ny­wa­ło akwi­zy­cji za­so­bu, a więc stan se­ma­fo­ra nig­dy nie prze­kro­czy war­toś­ci po­cząt­ko­wej. Jest to za­ło­że­nie sen­sow­ne, jed­nak nie zaw­sze moż­na za­gwa­ran­to­wać po­praw­ność opro­gra­mo­wa­nia. Pewnym spo­so­bem stwier­dze­nia, czy stan se­ma­fo­ra nie prze­kro­czył za­ło­żo­nej war­toś­ci gra­nicz­nej jest wy­ko­rzys­ta­nie funk­cji sem_getvalue(), zwra­ca­ją­cej aktu­al­ną war­tość licz­ni­ka se­ma­fo­ra. W po­łą­cze­niu z me­cha­niz­mem aser­cji umoż­li­wia to we­ry­fi­ko­wa­nie po­praw­noś­ci wer­sji uru­cho­mie­nio­wej pro­gra­mu, bez utra­ty wy­daj­noś­ci wer­sji fi­nal­nej.


Oj, zwłaszcza kierowcy przejeżdżający przez tory często niedoceniają semaforów. ;)
Jedyne, co bym dodał, to tylko to, że jeśli jest możliwe stworzenie szybkiego systemu, dla którego problem synchronizacji można rozwiązać inaczej (zamiast blokować wątek/proces, np. zgrupować zapytania i rozpatrzyć później), chyba lepiej jest tak to zrobić. Chyba że jest to zbyt skomplikowane, za bardzo zaciemnia kod lub można pogodzić się z odrobiną czekania.