b'\n_START_ARTICLE_\nSemafor (informatyka)\n_START_PARAGRAPH_\nSemafor \xe2\x80\x93 chroniona zmienna lub abstrakcyjny typ danych, kt\xc3\xb3ry stanowi klasyczn\xc4\x85 metod\xc4\x99 kontroli dost\xc4\x99pu przez wiele proces\xc3\xb3w do wsp\xc3\xb3lnego zasobu w \xc5\x9brodowisku programowania r\xc3\xb3wnoleg\xc5\x82ego. Semafory zosta\xc5\x82y po raz pierwszy opisane przez Edsgera Dijkstr\xc4\x99 jako istotne rozwini\xc4\x99cie algorytmu Dekkera._NEWLINE_Typowy semafor implementowany jest jako zmienna typu ca\xc5\x82kowitego. Semafory dzieli si\xc4\x99 na binarne i zliczaj\xc4\x85ce. Semafor binarny mo\xc5\xbce przyjmowa\xc4\x87 warto\xc5\x9bci ca\xc5\x82kowite ze zbioru {0, 1}, zliczaj\xc4\x85cy \xe2\x80\x93 r\xc3\xb3wnie\xc5\xbc wi\xc4\x99ksze ni\xc5\xbc 1. Semafor zliczaj\xc4\x85cy jest licznikiem zestawu dost\xc4\x99pnych zasob\xc3\xb3w. Ka\xc5\xbcdy z nich mo\xc5\xbce by\xc4\x87 zastosowany, by zapobiec wyst\xc4\x85pieniu zjawiska hazardu lub zakleszczenia (chocia\xc5\xbc nie w ka\xc5\xbcdej sytuacji s\xc4\x85 w stanie wyeliminowa\xc4\x87 te problemy, co ilustruje problem ucztuj\xc4\x85cych filozof\xc3\xb3w).\n_START_SECTION_\nImplementacja\n_START_PARAGRAPH_\nSemafory zliczaj\xc4\x85ce s\xc4\x85 dost\xc4\x99pne poprzez stosowanie operacji analogicznych do poni\xc5\xbcszych przyk\xc5\x82ad\xc3\xb3w napisanych w Pascalu. Procedura V inkrementuje semafor S, natomiast procedura P dekrementuje go:_NEWLINE_ procedure V (S : Semaphore);_NEWLINE_ begin_NEWLINE_   (* Operacja atomowa: inkrementacja semafora *)_NEWLINE_   S := S + 1;_NEWLINE_ end;_NEWLINE__NEWLINE_   (* Operacja atomowa: dekrementacja semafora *)_NEWLINE_ procedure P (S : Semaphore);_NEWLINE_ begin_NEWLINE_   (* Ca\xc5\x82a operacja jest atomowa *)_NEWLINE_   repeat_NEWLINE_     Wait();_NEWLINE_   until S > 0;_NEWLINE_   S := S - 1;_NEWLINE_ end;_NEWLINE_Warto\xc5\x9b\xc4\x87 semafora S to liczba jednostek zasobu, na kt\xc3\xb3re nie zg\xc5\x82oszono \xc5\xbc\xc4\x85dania. Je\xc5\xbceli istnieje tylko jeden taki zas\xc3\xb3b, semafor binarny jest u\xc5\xbcywany jako zwyk\xc5\x82a flaga true/false. Operacja P oczekuje i zasypia, dop\xc3\xb3ki zas\xc3\xb3b kontrolowany przez semafor nie stanie si\xc4\x99 dost\xc4\x99pny, gdy natychmiast zg\xc5\x82aszane jest \xc5\xbc\xc4\x85danie oczekuj\xc4\x85cego zasobu. Operacja V jest odwrotna: zwalnia ponownie zas\xc3\xb3b po tym, jak proces przesta\xc5\x82 go u\xc5\xbcywa\xc4\x87._NEWLINE_Koncepcja semafora licz\xc4\x85cego mo\xc5\xbce zosta\xc4\x87 rozszerzona poprzez mo\xc5\xbcliwo\xc5\x9b\xc4\x87 za\xc5\xbc\xc4\x85dania lub zwr\xc3\xb3cenia wi\xc4\x99cej ni\xc5\xbc jednej jednostki od semafora \xe2\x80\x93 technika implementowana w Uniksie. Zmodyfikowane operacje V i P b\xc4\x99d\xc4\x85 wygl\xc4\x85da\xc5\x82y nast\xc4\x99puj\xc4\x85co:_NEWLINE_ procedure V (S : Semaphore; I : Integer);_NEWLINE_ begin_NEWLINE_   S := S + I (* operacja atomowa *)_NEWLINE_ end;_NEWLINE__NEWLINE_ procedure P (S : Semaphore; I : Integer);_NEWLINE_ begin_NEWLINE_   (* ca\xc5\x82a operacja jest atomowa *)_NEWLINE_   repeat_NEWLINE_     Wait();_NEWLINE_   until S >= I;_NEWLINE_   S := S - I;_NEWLINE_ end;_NEWLINE_\xc5\xbbeby unikn\xc4\x85\xc4\x87 zag\xc5\x82odzenia, semafor mo\xc5\xbce mie\xc4\x87 po\xc5\x82\xc4\x85czon\xc4\x85 kolejk\xc4\x99 proces\xc3\xb3w (zwykle typu FIFO). Je\xc5\xbceli proces wykonuje operacj\xc4\x99 P na semaforze, kt\xc3\xb3ry ma warto\xc5\x9b\xc4\x87 0, proces jest dodawany do kolejki semafora. Kiedy inny proces inkrementuje semafor przez wykonanie operacji V i w kolejce znajduj\xc4\x85 si\xc4\x99 inne procesy, jeden z nich jest usuwany z kolejki i wznawia dzia\xc5\x82anie. Kiedy procesy maj\xc4\x85 inne priorytety, kolejka mo\xc5\xbce by\xc4\x87 uporz\xc4\x85dkowana wed\xc5\x82ug priorytet\xc3\xb3w, tak \xc5\xbce proces o najwy\xc5\xbcszym priorytecie jest zabierany z kolejki jako pierwszy._NEWLINE_Aby zagwarantowa\xc4\x87, \xc5\xbce dwa lub wi\xc4\x99cej proces\xc3\xb3w nie zmodyfikuje jednocze\xc5\x9bnie tego samego semafora, operacje, kt\xc3\xb3re faktycznie inkrementuj\xc4\x85 lub dekrementuj\xc4\x85 semafor, s\xc4\x85 okre\xc5\x9blane jako atomowe, co oznacza, \xc5\xbce nie powinny zosta\xc4\x87 przerwane, tak jak poprzez wyw\xc5\x82aszczenie. To wymaganie mo\xc5\xbce zosta\xc4\x87 spe\xc5\x82nione poprzez u\xc5\xbcywanie instrukcji maszynowej, kt\xc3\xb3ra jest w stanie czyta\xc4\x87, modyfikowa\xc4\x87 i zapisywa\xc4\x87 semafor w pojedynczej operacji. Pod nieobecno\xc5\x9b\xc4\x87 takiej instrukcji sprz\xc4\x99towej operacja atomowa mo\xc5\xbce zosta\xc4\x87 zrealizowana poprzez czasowe zawieszenie wyw\xc5\x82aszcze\xc5\x84 lub, co jest mniej po\xc5\xbc\xc4\x85dane, czasowe uniemo\xc5\xbcliwienie przerwa\xc5\x84 systemowych.\n_START_SECTION_\nEtymologia nazw funkcji\n_START_PARAGRAPH_\nOperacj\xc4\x99 wait oznacza si\xc4\x99 r\xc3\xb3wnie\xc5\xbc liter\xc4\x85 P, a signal liter\xc4\x85 V, kt\xc3\xb3re zwykle s\xc4\x85 kojarzone z niderlandzkimi s\xc5\x82owami: passeren (przej\xc5\x9b\xc4\x87), proberen (pr\xc3\xb3bowa\xc4\x87), vrijgeven (zwolni\xc4\x87), verhoog (zwi\xc4\x99ksza\xc4\x87). Jednak\xc5\xbce sam Dijkstra u\xc5\xbcycie liter P i V wyja\xc5\x9bnia\xc5\x82 nieco inaczej. W Algolu 68, j\xc4\x85drze Linux P od Prolaag czyli probeer verlaag (spr\xc3\xb3buj zmniejszy\xc4\x87) oraz V od verhoog (zwi\xc4\x99ksza\xc4\x87). i w niekt\xc3\xb3rych angloj\xc4\x99zycznych ksi\xc4\x85\xc5\xbckach operacje P i V s\xc4\x85 nazwane, odpowiednio, down i up. W praktyce in\xc5\xbcynierii oprogramowania s\xc4\x85 cz\xc4\x99sto nazywane wait i signal, acquire i release (u\xc5\xbcywane w standardowej bibliotece Java), lub pend i post. Czasami bywaj\xc4\x85 te\xc5\xbc nazywane  procure i vacate, aby by\xc5\x82y zgodne z oryginalnymi holenderskimi inicja\xc5\x82ami.\n_START_SECTION_\nAnalogia semafora zliczaj\xc4\x85cego\n_START_PARAGRAPH_\nZa\xc5\x82\xc3\xb3\xc5\xbcmy, \xc5\xbce "zasoby" to stoliki w restauracji a "procesy" to jej klienci. "Semafor" jest reprezentowany przez ma\xc3\xaetre d\xe2\x80\x99h\xc3\xb4tel, kt\xc3\xb3ry jako jedyna osoba decyduje o udost\xc4\x99pnianiu stolik\xc3\xb3w. Ma\xc3\xaetre d\xe2\x80\x99h\xc3\xb4tel liczy w pami\xc4\x99ci wolne stoliki (utables) i zawsze wie kogo umie\xc5\x9bci\xc4\x87 jako pierwszego przy zwolnionym stoliku. Jest on bardzo zaj\xc4\x99ty i skoncentrowany i nikt nie mo\xc5\xbce mu przeszkadza\xc4\x87 w trakcie wykonywania obowi\xc4\x85zk\xc3\xb3w._NEWLINE_Kiedy restauracja rozpoczyna dzia\xc5\x82alno\xc5\x9b\xc4\x87 b\xc4\x99dzie pocz\xc4\x85tkowo pusta. Innymi s\xc5\x82owy "warto\xc5\x9b\xc4\x87" "semafora" b\xc4\x99dzie r\xc3\xb3wna liczbie stolik\xc3\xb3w (tables) w restauracji (czyli  utables=tables). Kiedy kto\xc5\x9b przybywa, ma\xc3\xaetre d\xe2\x80\x99h\xc3\xb4tel umie\xc5\x9bci go (lub j\xc4\x85) przy stoliku i zmniejszy w pami\xc4\x99ci liczb\xc4\x99 wolnych stolik\xc3\xb3w (utables=utables-1). Teraz "warto\xc5\x9b\xc4\x87" "semafora" jest r\xc3\xb3wna liczbie stolik\xc3\xb3w w restauracji minus 1._NEWLINE_Je\xc5\xbceli wielu klient\xc3\xb3w przyb\xc4\x99dzie jednocze\xc5\x9bnie, ma\xc3\xaetre d\xe2\x80\x99h\xc3\xb4tel ulokuje ich przy stolikach w kolejno\xc5\x9bci przybycia zak\xc5\x82adaj\xc4\x85c, \xc5\xbce na sali znajduje si\xc4\x99 wystarczaj\xc4\x85ca liczba stolik\xc3\xb3w, aby zmie\xc5\x9bci\xc4\x87 wszystkich (utables>0). Przybywaj\xc4\x85cy go\xc5\x9bcie z rezerwacjami mog\xc4\x85 zosta\xc4\x87 ulokowani przy stolikach przed innymi, kt\xc3\xb3rzy nie maj\xc4\x85 rezerwacji, gdy\xc5\xbc maj\xc4\x85 przed nimi pierwsze\xc5\x84stwo. Po zaj\xc4\x99ciu kt\xc3\xb3rego\xc5\x9b ze stolik\xc3\xb3w ma\xc3\xaetre d\xe2\x80\x99h\xc3\xb4tel ponownie wyliczy warto\xc5\x9b\xc4\x87 utables=utables-1. Je\xc5\xbceli wszystkie stoliki s\xc4\x85 zaj\xc4\x99te (czyli utables=0), nowo przybywaj\xc4\x85cy go\xc5\x9bcie musz\xc4\x85 poczeka\xc4\x87 w kolejce na zwolnienie stolika._NEWLINE_Je\xc5\xbceli klient zwolni stolik, ma\xc3\xaetre d\xe2\x80\x99h\xc3\xb4tel wyliczy w pami\xc4\x99ci now\xc4\x85 warto\xc5\x9b\xc4\x87 utables=utables+1. Je\xc5\xbceli kolejny go\xc5\x9b\xc4\x87 czeka na stolik i przynajmniej jeden stolik jest dost\xc4\x99pny, ma\xc3\xaetre d\xe2\x80\x99h\xc3\xb4tel ulokuje jego/j\xc4\x85 przy tym stoliku i ponownie wyliczy now\xc4\x85 warto\xc5\x9b\xc4\x87 utables=utables-1. Ostatecznie wszyscy go\xc5\x9bcie opuszcz\xc4\x85 lokal i kolejne obliczenia warto\xc5\x9bci utables dadz\xc4\x85 warto\xc5\x9b\xc4\x87 utables=tables \xe2\x80\x93 restauracja jest znowu pusta.'