Ws ze chnica Popołudniowa

Programowanie ws półbie żne w informatyce i nie tylko

dr Marcin Engel

prof. dr hab. Maciej M Sysło

Ze szyt dydaktyczny opracowany w ramach projektu edukacyjne go

— ponadre gionalny program rozwijania kompe tencji

uczniów szkół ponadgimna zjalnych w zakresie technologii
informacyjno-komunikacyjnych (ICT).

Warszawska Wyżs za Szkoła Informa tyki

ul. Lewartowskie go 17, 00 -169 Wars zawa

Projekt graficzny: FRYCZ I WICHA

Wars zawa 2009
Copyright © Wars za wska Wyżs za Szkoła Informatyki 2009
Publikacja nie jes t prze znaczona do sprze da ży.

Instytut Informatyki

Uniwersytet Warszawski

[e-mail]

< 4 >

Informa tyka +

Program współbie żny to zes taw wykonujących się w tym s amym cza sie ,,zwykłych’’ programów. Techniki
współbie żne stosuje się przy tworzeniu wielu współczes nych programów, na przykład opracowują c interfejs
użytkownika, programując gry czy aplikacje sie ciowe. Tworzenie programów współbie żnych wymaga od pro-
gramis ty więks zej dys cypliny i wyobra źni niż pis anie programów s ekwencyjnych. Oprócz zagwarantowania
poprawności pos zczególnych skła dowych programu współbieżnego, trzeba jes zcze dobrze zs ynchronizować
ich działanie ora z prze widzie ć ws zys tkie możliwe scenariusze wykonania . Nie je st to ła twe – przekonamy się,
jak częs to podcza s analizowania programów współbieżnych może za wieś ć na s intuicja!

W trakcie zajęć przedstawimy pods tawowe poję cia programowania współbieżnego. Zdefiniujemy pojęcie pro-
cesu i wyja śnimy, jak mogą być wykonywane programy współbie żne. Powiemy także, jak wsp ółczesne s ys te -
my operacyjne radzą s obie z wykonywaniem wielu zadań na jednym proces orze. Na przykła dzie dwóch kla -
s ycznych problemów współbieżności: wzajemnego wykluczania oraz pię ciu filozofów omówimy poję cia zwią -
zane z analizą programów współbieżnych: przeplot, popra wnoś ć, bezpieczeńs two oraz żywotnoś ć. Przeko-
namy s ię, że z tymi poję ciami ora z problemami s ynchronizacyjnymi spotykamy się na co dzień, na przykład
ucząc się, piekąc cia s to albo obserwując ruch samochodów na ulicach.

Zajęcia będą mia ły formę wykładu, ale w jego trakcie będziemy wspólnie uruchamiać niektóre programy
współbie żne na „wirtualnym komputerze wieloproces orowym”, którego proces orami będą słuchacze.

1. Co to je s t programowanie ws półbieżne........................................................................................................ 5

1.1. Model komputera .................................................................................................................................. 5

1.2. Program s ekwencyjny ............................................................................................................................ 6

1.3. Program współbieżny ............................................................................................................................ 7

1.4. Programy i proces y ................................................................................................................................ 7

1.5. Różne s posoby wykonywania programu współbie żnego ....................................................................... 7

1.6. Znaczenie programowania współbie żnego ............................................................................................ 8

1.7. Jak komputery wykonują programy współbieżne ................................................................................... 9

2 . Kłopot y z programami ws półbieżnymi ....................................................................................................... 10

2.1. Problemy s ynchronizacyjne ................................................................................................................. 10

2.2. Problem z brakiem atomowoś ci ins trukcji ............................................................................................11

2.3. Problem z jednoznaczną modyfikacją zmiennych globalnych .............................................................. 12

3. Wzajemne wykluczanie .............................................................................................................................. 13

4 . Poprawnoś ć programów współbie żnych ................................................................................................... 14

4.1. Własnoś ć bezpieczeńs twa .................................................................................................................. 14

4.2. Własnoś ć żywotnoś ci .......................................................................................................................... 14

4.3. Przykłady braku żywotności ................................................................................................................ 14

5. Podsumowanie ........................................................................................................................................... 17

Literatura

............................................................................................................................................... 18

> Programowa nie współbieżne w informatyce i nie tylko

< 5 >

Na rysunku 1 przeds tawiono obra zek z popularnej gry. Widzimy na nim kilka porus zających się niezale żnie od
siebie łyżwiarzy. Zas tanówmy s ię, w jaki spos ób można zaprogramowa ć taką s cenę.

Rysunek 1.
Obra zek z popularnej gry

Aby się o tym przekonać poczyńmy pewne upras zczające założenia. Przyjmijmy, że lodowisko jes t pros toką -
tem i że jes t podzielone na pola. Znajdują się na nim cztery os oby. Ka żda z nich s toi początkowo nieruchomo
w pewnym polu lodowiska zwrócona twarzą w kierunku wska zanym s trzałką jak na rysunku 2.

Rysunek 2.
Upros zczony schemat gry

Załóżmy, że ka żda z tych osób potrafi:

■

wykonywać jeden krok do przodu przechodząc do kolejne go pola,

■

obra cać się o 90 s topni w prawo lub w lewo.

Przy lodowis ku s toi trener i nadzoruje ruch łyżwiarzy, którzy nie wykonują żadnego kroku a ni obrotu bez jego
wyra źne go polecenia . Lodowisko ze znajdują cymi się na nim łyżwiarzami będzie s tanowić model komputera ,
a trener gra rolę programis ty.

Trener wydaje łyżwiarzom polecenia , na przykład: „Beata , wykonaj jeden krok naprzód”, „Czarek, ob-

róć s ię w lewo”. Możemy myśleć o takich poleceniach jak o ins trukcjach pewnego języka programowania.
Przyjmijmy, że ka żda ins trukcja składa się z dwóch elementów: imienia łyżwiarza ora z polecenia dla tego łyż-
wiarza , które może być jednym z: krok naprzód, obrót w lewo, obrót w prawo. Ins trukcje s ą wykonywane na

< 6 >

Informa tyka +

przeds tawionym modelu komputera powodując przemies zczanie się łyżwiarzy. Przykładowy program w tym
ję zyku programowania może mieć na stępują cą pos tać:

Ania , krok naprzód
Czarek, obrót w lewo
Czarek, krok naprzód
Damian, krok naprzód

Jeżeli wykonamy ten program w s ytuacji początkowej, przeds ta wionej na rys unku 2, to doprowadzi on do koń-
cowego położenia łyżwiarzy jak na rys unku 3.

Rysunek 3.
Pozycja łyżwiarzy p o wykonaniu pros te go programu

Jazda na łyżwach bywa niebezpieczna . Łyżwia rze powinni uwa żać, żeby nie wpa ś ć na bandę ani nie zderzyć
się ze s obą. Ponie wa ż jednak wykonują oni pole cenia trenera , więc za ws zelkie wypadki odpowiada trener. Ta
s ytuacja również dobrze modeluje rze czywis toś ć: komputery pope łniają błędy, ale za wsze są one skutkiem
błę du programis ty.

Budowanie całej s ceny za pomocą takich pros tych poleceń wydawanym poszczególnym łyżwiarzom jes t bar-
dzo pracochłonne. Wygodniej byłoby przygotować krótką choreografie dla ka żdego łyżwiarza i ka zać mu ją
powtarzać. Jednak ze względu na bezpieczeńs two, trener nie może te go zrobić be z doda tkowych narzędzi.
Spróbujmy więc ułatwić mu zadanie wprowadzając do ję zyka je szcze jedną ins trukcję: „jeśli pole przed Tobą
jes t wolne, to wykonaj krok naprzód, w przeciwnym ra zie obróć s ię w lewo”. Tera z chore ografia (czyli program
dla łyżwiarzy) może wyglądać na s tę pująco:

Powtarzaj
Ania , je śli pole przed Tobą jes t wolne, to krok naprzód, w prze ciwnym ra zie obróć się w lewo
Bea ta , jeśli pole prze d Tobą je st wolne, to krok naprzód, w przeciwnym razie obróć się w lewo
Czarek, jeśli pole przed Tobą jes t wolne , to krok naprzód, w przeciwnym ra zie obróć się w le wo
Damian, je śli pole przed Tobą jes t wolne, to krok naprzód, w prze ciwnym ra zie obróć s ię w lewo

Nazwiemy go programem sekwencyjnym, bo poszczególne instrukcje są wykonywane jedna po drugiej. Jeśli pro-
gram ten powtórzymy dużą liczbę ra zy, to uzyskamy scenę z czterema jeżdżącymi wokół lodowiska łyżwiarzami.

Takie rozwią zanie ma jednak pewne wady. Po pierws ze ws zys cy łyżwiarze porus zają się w ten s am sposób.
Trudno byłoby nam zapisa ć w pos taci równie krótkiego co poprze dnio programu s cenę, w której trójka łyżwia -
rzy je ździ wokół lodowiska , a Bea ta krę ci piruet. Po drugie, ws zys cy łyżwiarze jeżdżą w tym s amym tempie.
Z tych powodów s cena nie jes t realis tyczna. Wreszcie programis ta przygotowujący program musi jednocze -
śnie myś leć o ws zys tkich łyżwiarzach. Spróbujmy wię c nie co innego podejś cia do wyre żys erowania scenki.

> Programowa nie współbieżne w informatyce i nie tylko

< 7 >

Przypuś ćmy tera z, że trener przygotowuje program dla jednego łyżwiarza. Program jes t napisany w tym s a-
mym języku programowania, co do tej pory, choć teraz nie trzeba poprzedza ć polecenia imieniem konkretnej
os oby. Przykładowy program dla jedne go łyżwiarza wygląda tera z tak:

Powtarzaj
je śli pole przed Tobą jes t wolne, to krok naprzód, w przeciwnym ra zie obróć się w lewo

Na s tępnie trener ka że ws zystkim łyżwiarzom wykonywać programy, które od niego otrzymali. Je śli wszyscy
otrzymali powyżs zy program, to efekt będzie identyczny (prawie identyczny, ale o tym później), ja k w przy-
pa dku programu s ekwencyjnego. Na czym wię c pole ga różnica?

W przypadku programu sekwencyjnego komputer (czyli lodowis ko) wykonywał w danym momencie tyl-

ko jedno polecenie. „Czarek, krok naprzód” powodowało, że tylko Czarek wykonywał ruch. Innymi s łowy na
komputerze wykonywa ł się tylko je den program. W drugim rozwią zaniu s ytuacja jes t zupe łnie inna . Trener
przygotowuje cztery programy i wręcza je łyżwia rzom, którzy wykonują je je dnocześnie. Takie właś nie wyko-
nanie na zywamy wykonaniem współbieżnym. Dokładniej, wykonanie współbie żne to realizacja kilku (co naj-
mniej dwóch czynności) w taki sposób, że kolejna czynnoś ć rozpoczyna się przed zakończeniem poprzedniej.

Co w opis anej s ytuacji zyskujemy pis ząc zamias t „zwykłego” programu sekwencyjnego program ws pół-

bieżny? Przede ws zys tkim ela stycznoś ć, czyli możliwość łatwej modyfika cji zachowania jednego łyżwiarza
niezale żnie od pozos ta łych. Jeśli chcemy, żeby Beata krę ciła pirue ty po pros tu wręczymy jej inny program do
wykonania , na przykład taki: „powtarzaj: wykonaj obrót w le wo”. Przygotowując program trener może tera z
skupić s ię w danym momencie na roli jednego łyżwiarza nie przejmując się pozos ta łymi. To bardzo wa żna za-
leta! Współczes ne programy komputerowe s ą tworami bardzo złożonymi. Ich tworzenie byłoby niemożliwe,
gdyby programis ta mus iał myśle ć jednocześ nie o ws zys tkich szczegółach. Dla te go wła śnie duże programy
tworzy s ię s topniowo skupiając się na jednym problemie chwilowo ignorując pozos ta łe lub też zakładają c, że
znane s ą już ich rozwią zania .

Kontynuujmy przykład lodowego komputera. Za s tanówmy się tera z, w jaki spos ób taki komputer może wyko-
nywa ć program współbieżny. Zanim to je dnak zrobimy wprowadźmy pewne wa żne i pows zechnie s tos owane
w informa tyce odróżnienie. Informatycy wyra źnie odróżniają pojęcie programu od wykonania programu. Pro-
gram to przepis , cią g ins trukcji, który ma zos tać wykonany. W na szym przykładzie programami były s cenariu-
sze za pis ane na kartkach wrę czanych łyżwiarzom. Wykonanie programu to obiekt dynamiczny zwany proce -
sem. W na s zym przykładzie ka żdy łyżwiarz to osobny proces . Ka żdy proces wykonuje pewien program. Dwa
różne proces y mogą wykonywa ć różne programy, mogą też wykonywać ten s am program. Konkretny program
może być w danej chwili wykonywany prze z wiele procesów lub przez jeden proces . Ka żdy proces pracuje s e -
kwencyjnie, tzn. wykonuje s woje instrukcje jedna po drugiej. W wykonaniu współbieżnym, zgodnie z tym co
powiedzieliś my poprzednio, bierze udział kilka proces ów.

W jaki zatem s posób proces y realizują s woje programy? Pierwsza możliwoś ć to wykonanie a s ynchroniczne.
Wyobra źmy sobie, że trener przygotował programy dla poszczególnych łyżwiarzy i wręczył im je. Łyżwiarze re -
alizują na s tępnie te programy w sposób niezale żny od siebie, ka żdy we własnym tempie. W ten spos ób może -
my uzyskać realnie wyglądającą s cenę. Druga możliwość to wykona nie s ynchroniczne. Aby wytłumaczyć, na
czym ono pole ga zaanga żujemy jes zcze jedną os obę – kierownika lodowiska . Łyżwiarze po otrzymaniu pro-
gramów nie robią nic, czekając na s ygnał od kierownika . Na s ygna ł (kla śnię cie w dłonie) ka żdy łyżwiarz wyko-
nuje jedną ins trukcję s wojego programu. Tak przygotowana s cena bardzo przypomina tę z programu sekwen-
cyjnego: ws zys cy łyżwiarze porus zają się w tym s amym tempie.

Są także inne możliwości. Przypuś ćmy, że kierownik tym razem nie kla szcze, ale wykrzykuje po ko-

lei imiona pos zczególnych łyżwiarzy. Ka żd y z nich po usłys zeniu wła snego imienia wykonuje jedną ins truk-
cję s wojego programu. Kierownik może wywoływa ć cyklicznie wszys tkich łyżwia rzy – wtedy uzyskujemy wy-
konanie przypominające wykonanie s ynchroniczne albo może za ka żdym ra zem podejmować decyzję, który
łyżwiarz ma się porus zyć nie zależnie od tego, co dzia ło się do tej pory. Pows taje wtedy s cenka przypomina -
jąca wykonanie a s ynchroniczne.

< 8 >

Informa tyka +

Przyjrzyjmy się, czym różnią się te dwie os tatnie możliwoś ci od wykonania s ynchronicznego i a s ynchronicz-
ne go. Pierws za najwa żniejs za różnica jes t taka, że w wykonaniu s ynchronicznym i a s ynchronicznym docho-
dziło do jednoczesnych działań wielu łyżwiarzy. Używając fachowego ję zyka powiemy, że je dnocze śnie, czyli
dokładnie w tym s amym czasie wykonuje się wiele procesów. Mówimy wówczas , że je st to wykonanie równo-
ległe . W rozwią zaniu z kierownikiem wybierającym zawodnika , który ma wykonać ruch w danej chwili dzia ła
tylko jeden proces. W dals zym ciągu jednak jes t to wykonanie współbieżne, gdyż działa wiele proces ów i ko-
lejny rozpoczyna się zanim zakończy się pierws zy. Nie jes t to jednak wykonanie równole głe, bo w danej chwi-
li wykonuje się tylko jeden proces. O takim wykonaniu powiemy, że jes t to wykonanie w przeplocie . Na zwa
pochodzi s tą d, że ins trukcje poszczególnych proce sów przeplatają się ze sobą . Sposób przeplotu może być
zaws ze taki s am, je śli kierownik zaws ze wywołuje łyżwiarzy w tej s amej kolejności lub te ż za ka żdym ra zem
inny, jeśli kierownik wywołuje łyżwiarzy w los owej kolejnoś ci. Pojęcie przeplotu jes t bardzo wa żne w progra -
mowaniu współbieżnym i częs to będziemy do niego wracać na tych zaję ciach.

Co je szcze rzuca się w oczy, gdy porównujemy wykonania równoległe z wykonaniami w przeplocie. Wi-

dać, że jeśli łyżwiarze poruszają s ię w przeplocie uzyskujemy s cenę mniej płynną i realną niż przy wykona -
niu równoległym. Ale jeżeli kierownik będzie wywoływa ł łyżwiarzy bardzo s zybko i będą oni s zybko wykony-
wa ć s woje ruchy, na sze oczy prze staną zauwa żać różnicę między wykonaniem równoległym a wywołaniem
w przeplocie i scena odzyska płynnoś ć. Taką wła śnie technikę bardzo czę s te go przeplatania instrukcji po-
s zczególnych proce sów s tos uje się we współczesnych s ys temach operacyjnych.

Tak naprawdę z wykonaniem współbieżnym zarówno równoległym jak i w przeplocie s potyka my się bardzo
częs to w życiu codziennym. Przykładowo ws zys tkie zgromadzone na tej s ali osoby możemy traktować jak pro-
ces y realizujące pewne programy i wykonujące s ię równolegle. Ciekawym przykładem proces ów wykonują -
cych się równolegle s ą s amochody przeje żdżające przez s krzyżowanie. Z wykonaniem w przeplocie spotyka
się ka żdy z na s realizując s woje codzienne obowiązki. Za zwyczaj mamy wiele rzeczy do zrobienie (na przy-
kład uczeń musi przys woić wiedzę z wielu prze dmiotów). Mózg ludzki nie jes t przys tosowany do nadzorowa -
nia wielu czynności jednocześnie, wię c cza sochłonne czynności z reguły dzielimy na e tapy i przeplatamy z in-
nymi obowią zkami. Przykładowo uczeń nie uczy się matema tyki dopóki nie opanuje ca łe go materiału s zkoły
średniej, ale przeplata naukę matema tyki nauką his torii, polskiego czy innych prze dmiotów. W podobny spo-
s ób pos tępuje kucharz przygotowujący obiad złożony z wielu dań.

Dlaczego programowanie współbieżne stało się obecnie wa żną techniką programowania? Kiedy 15 lat temu
przeciętny użytkownik uruchamiał komputer jego oczom uka zywa ł się mniej więcej taki widok. Pows zechnie
s tos owanym wówcza s s ys temem operacyjnym był MS-DOS firmy Micros oft. Komputer oczekiwał na polece -
nie użytkownika , którym mogło być na przykład uruchomienie określonego programu. Proces wykonujący ten
program musiał wykonać s ię do końca zanim użytkownik mógł uruchomić kolejny. Taki s ys tem operacyjny na -
zywa się s ys temem jednozadaniowym. Za tem przecię tny użytkownik nie miał możliwości współbieżnego wy-
konywania programów, więc programiści przygotowujący aplikacje pod s ys tem MS-DOS nie musieli (a nawe t
nie mogli) s tos ować technik programowania współbieżnego. Nie znaczy to jedna k, że techniki te nie były zna-
ne lub niepotrzebne. W tym s amym cza sie is tnia ły również s ys temy umożliwiające uruchamianie wielu pro-
gramów, jednak prze znaczone one były na więks ze komputery. Powodowało to, że umiejętnoś ć programowa -
nia współbieżnego była doś ć ezoteryczna i zarezerwowana dla programis tów s ys temowych (tworzących s ys -
temy operacyjne) i piszących aplikacje na duże ma s zyny.

Od tego cza su jednak wiele s ię zmieniło. Prze de ws zys tkim na s tą pił znaczą cy pos tęp w dziedzinie

s przętu. Porównajmy dla przykładu pa rame try typ owego ws półczesnego komputera i komputera sprze d 15
lat. Szybs zy proce sor umożliwia s zybs ze wykonanie proce s ów. Ka żdy proce s , który jes t wykonywa ny przez
komputer, musi mie ć zarezerwowa ną pamięć na s woje dane. Im wię cej pamię ci tym więcej proces ów moż-
na utworzyć, a s zybki proces or umożliwia s zybkie, nie zauwa żalne dla użytkownika prze plata nie ich wyko-
na nia .

Rozwój sprzę tu to je dnak nie ws zys tko. Ta k napra wdę już 15 la t temu na kompute rze PC, który wów-

cza s był za zwyczaj wypos a żony w proces or 16 MHz, pamię ć 1 MB i dys k twardy o pojemnoś ci 60 MB, moż-
na było wykonywać wiele programów współbieżnie. Potrzebny był je dynie s ys tem ope racyjny, który by to
umożliwia ł – tzw. s ys tem wielozadaniowy. I takie s ys temy zaczę ły się powoli pojawia ć, a je dnym z pierw-
s zych był Linux.

> Programowa nie współbieżne w informatyce i nie tylko

< 9 >

Jak wygląda s ytuacja dzisiaj? Po uruchomieniu komputera widzimy graficzny interfejs jednej z wielu wer-
sji s ys temu Windows , Linux lub innych s ys temów. Po chwili pracy najczę ściej na ekranie je st otwartych wie -
le okienek, na przykład przeglądarka interne towa , edytor tekstu, arkus z kalkulacyjny, kalkulator i inne. Nie
trzeba już zamyka ć jednego programu, aby uruchomić kolejny. Ws półbie żne wykonanie wielu programów jes t
czymś pows zechnym. Co wię cej nawet jedna aplikacja , na przykład arkus z kalkulacyjny może składać s ię
z wielu proces ów. Częs to jeden z nich jes t odpowiedzialny za obs ługę interfejsu użytkownika. Gdy użytkow-
nik zle ci za pomocą mys zki wykonanie jakieś czynnoś ci, to proces ten tworzy nowy proces i zleca mu wykona -
nie polecenia użytkownika , a s am jes t gotowy na przyjmowanie kolejnych pole ceń. Dzięki takiej kons trukcji
oprogramowania aplikacja może reagować na polecenia użytkownika nawe t w cza sie realizacji cza sochłon-
nych obliczeń!

Kolejnym elementem, który powoduje, że obecnie każdy programis ta musi znać pods tawowe techniki progra -
mowania współbieżnego to rozwój sieci, w tym także Internetu.

Odnieśmy teraz różne wykonania programu współbie żnego, przeds ta wione na przykładzie lodowiska , do
wykonania na pra wdziwych komputerach. Jak wiadomo s ercem każdego komputera jes t proce sor. To właś nie
procesor jes t odpowiedzialny za wykonywanie pos zczególnych ins trukcji. Tradycyjnie s kons truowany proce -
sor jes t w s ta nie wykonywać w danej chwili tylko jedną ins trukcję. Natychmia s towym wnioskiem z tego je st
fakt, że komputer może wykonywa ć równolegle tyle ins trukcji, w ile proces orów jes t wyposa żony. Typowe
komputery domowe mają jeden procesor co oznacza, że wykonanie równoległe nie jes t możliwe. (Tak napraw-
dę nawe t w takich komputerach pewne czynnoś ci s ą wykonywane równolegle. Przykładowo karty graficzne
mają odrębne proces ory, które wykonują obliczenia równolegle z proces orem centralnym. Je dnak z perspek-
tywy programis ty nie ma to najczęś ciej znaczenia , dla te go nie rozwa żamy tego). Os tatnio cora z pows ze ch-
niejsze na wet w za s tos owaniach domowych s tały się jednak proce s ory wielordzeniowe. Są to proces ory, któ-
re s ą w stanie wykonywać wiele rozka zów ma s zynowych je dnocze śnie – tyle, ile mają rdzeni. Komputery wy-
posa żone w takie proces ory potrafią wykonywać równolegle tyle proces ów, ile mają rdzeni. Na nich wykona-
nie równoległe jes t w pełni możliwe. Jes zcze inny typ komputerów, na ra zie raczej niespotykanych w zas to-
sowaniach domowych, to komputery z wieloma proce sorami. Różnica między komputerem z jednym proce -
sorem wielordzeniowym a komputerem wieloproces orowym je st dla potrzeb tego wykładu nieis totna , wa żne
jes t jedynie, że komputery wieloprocesorowe także mogą wykonywać wiele procesów równole gle.

No dobrze, ale nawet na komputerze z jednym procesorem można uruchomić wiele proces ów. Jak to się dzieje?
Odpowiedzią jes t wła śnie wykonanie w przeplocie. Funkcję kierownika wybierającego proces , który ma wyko-
nać kolejną instrukcję pełni wtedy s ystem operacyjny, a dokładnie jego moduł zwany modułem szeregującym.
Otóż sys tem operacyjny zapamiętuje informacje o ws zys tkich uruchomionych procesach utrzymując tak zwa-
ną kolejkę proce sów gotowych. Pierwszemu proces orowi w tej kolejce jest przydzielany proces or, to znaczy,
s ys tem operacyjny decyduje, że tera z bę dzie wykonywał się ten właśnie proces. Odpowiada to s ytuacji, w któ-
rej kierownik wybrał łyżwiarza , który ma wykonać kolejny krok. Wykonywany proces nie wykonuje jednak tyl-
ko jednego rozkazu jak w przykładzie z lodowiska , ale wykonuje się przez pewien us talony czas , zwany kwan-
tem cza su. Po up ływie kwantu cza su s ystem operacyjny zapamiętuje s tan wykonywanego procesu, umiesz-
cza go na końcu kolejki proces ów gotowych i przydziela proces or kolejnemu proces owi z kolejki. W ten sposób
procesor wykonuje w danej chwili tylko jeden rozka z naraz, przy czym jes t to rozka z jednego z procesów lub
s ys temu operacyjne go. Gdy kwanty czasu s ą odpowiednio ma łe, to proces y s ą przełączane częs to i ich użyt-
kownicy nie zauwa żają opóźnień. Taki mechanizm na zywa się podziałem cza su. System operacyjny z podzia-
łem czasu gra więc rolę kierownika z nas zego przykładu. W odróżnieniu od dotychcza sowego na szego mode -
lu po wywołaniu łyżwiarza włącza stoper na określony cza s. W tym cza sie kroki wykonuje wybrany łyżwiarz a ż
do chwili, gdy kierownik wywoła kolejnego łyżwiarza. Czas ami mówi się, że s ys tem z podzia łem cza su dos tar-
cza wirtualne procesory. Taki wniosek jes t uza sadniany tym, że z punktu widzenia użytkowników taki s ys tem
nie różni się od s ystemu działającego na komputerze z wieloma , choć odpowiednio wolniejs zymi proces orami.

Przeds tawiony tutaj proces prze łączania proces ów jes t mocno uproszczony. W prawdziwych s ys temach ope -
racyjnych odbywa się to w bardziej złożony sposób. W s ys temie Linux na przykład nie ma jednej kolejki pro-
ces ów gotowych lecz ... ponad 100.

< 10 >

Informa tyka +

Dlaczego w sys temie z podziałem czasu proces dostaje procesor na pewien czas, a nie na wykonanie poje-

dynczego rozkazu? Odpowiedź jest prosta . Wymiana (przełączenie) procesów trwa jakiś czas . Gdyby procesy mo-
gły wykonać tylko jeden rozkaz, to komputer zajmowałby się głównie zapamiętywaniem s tanu proces ów i przełą-
czaniem między nimi i jedynie od czasu do czasu wykonywałby jakąś pożyteczną akcję któregoś procesu.

Wiemy już, że zarówno przy wykonaniu równoległym jak i wykonaniem z pod ziałem cza su mamy do czynie -
nia ze współbie żnoś cią. Czy jes t to je dnak wykonanie s ynchroniczne czy as ynchroniczne? Odpowiedź nie
jes t jednoznaczna . Na poziomie sprzętowym najczęś ciej jes t to wykonanie s ynchronicznie. Funkcję kierow-
nika z nas ze go przykładu z lodowiska pe łni tu zegar s ystemowy. Generuje on impulsu z określoną częs totli-
woś cią, a różne elementy sprzętowe (procesory, pamięci, magis trale) pracują w ich rytm. Im częś ciej tyka ze -
gar, tym częś ciej proces y wykonują rozkazy, a więc tym s zybs ze ich wykonanie. Z punktu widzenia programi-
s ty wykonanie jes t jednak as ynchroniczne. Poza tym proce sory mogą być taktowane zegarami o różnych czę -
s totliwościa ch albo proces y mogą otrzymywać kwanty różnej długości, nie wolno więc założyć nic o s zybko-
ś ciach pracy pos zcze gólnych proces ów, a co za tym idzie o liczbie wykonywanych nara z ins trukcji pos zcze -
gólnych proces ów. Programis ta nie wie, na jakim komputerze będzie wykonywany jego program musi wię c go
tak napis ać, aby działał poprawnie niezale żnie od spos obu wykonania .

Widzieliśmy już, że wprowadzenie współbie żnoś ci może ułatwić programiś cie prace, spowodować, że pro-
gram będzie mia ł leps zą s trukturę, bę dzie czytelniejszy, a prze z to łatwiej bę dzie znale źć w nim ewentualne
błę dy, wprowadzić nową funkcjonalnoś ć lub zmienić pewne jego elementy. Jednak współbie żne wykonanie
wielu procesów wprowadza także nowe problemy – nie spotykane przy programowaniu s ekwencyjnym. Są to
problemy s ynchronizacyjne i komunikacyjne. Skupimy się tutaj jedynie na wybranych problemach z pierw-
s zej z tych grup. Umiejętnoś ć programowania współbieżnego polega w is tocie na zdolności dos trzegania po-
tencjalnych problemów wynikających z interakcji mię dzy proces ami i użycia odpowiednich metod, zapobiega-
jących wystąpieniu niepożądanej s ytuacji. Przedstawmy problem na przykładzie łyżwiarzy. Rozwa żmy przy-
padek, gdy ka żdy łyżwiarz wykonuje wła sny program:

Powtarzaj
jeśli pole przed Tobą jes t wolne, to krok na przód, w przeciwnym ra zie obróć się w lewo

Przyjmijmy dla potrzeb tego przykładu, że proces y wykonują się równolegle w spos ób s ynchroniczny. Je śli
uruchomimy proce s y łyżwiarzy w s ytuacji przeds tawionej na rysunku 2, to ws zys tko przebie gnie pomyślnie
i łyżwiarze wkrótce zaczną je ździć wzdłuż bandy. Jeśli jednak uruchomimy go w s ytuacji przeds tawionej na
rysunku 4, to dojdzie do wypadku.

Rysunek 4.
Sytuacja w grze grożąca wypadkiem

> Programowa nie współbieżne w informa tyce i nie tylko

< 11 >

Ka żdy z łyżwiarzy na dany przez kierownika znak s twierdzi, że może wykonać krok do przodu, bo miejsce
przed nim jes t wolne. Łyżwiarze wykonają więc ten krok i ... wpadną na siebie. Zawiodła s ynchronizacja pro-
ces ów!

Czy do zderzenia mogłoby dojś ć, gdyby proces y wykonywały się równolegle i a s ynchronicznie. Oczy-

wiście tak, bo wykonanie s ynchroniczne je st s zcze gólnym przypadkiem wykonania a s ynchronicznego. A co
w przypadku wykonania w przeplocie? Gdy kierownik wybierze do wykonania łyżwiarza Damiana , to ten
stwierdzi, że przed s obą ma wolne miejs ce i wykona krok do przodu. Gdy tera z Ania usłys zy s woje imię to
stwierdzi, że miejsce przed nią jes t zaję te i obróci się w le wo. Z pozoru ws zys tko wyglą da w porządku. Ale nie -
ste ty tak nie jes t.

Programy najczęś ciej pis ze s ię w wysokopoziomowych językach programowania . Przykładem takiego ję zy-
ka jest wła śnie wprowadzony przez na s język pis ania s cenarius zy dla łyżwiarzy (choć w rzeczywistym ję zy-
ku programowania ins trukcje s ą na znacznie niżs zym poziomie s zczegółowości). Proces or nie rozumie jed-
nak pole ceń ję zyka wys okiego poziomu. Producenci proce sorów wypos a żają je w zes taw bardzo szczegóło-
wych rozka zów. Taki język na zywa się częs to ję zykiem ma s zynowym. Rozka zy s ą bardzo niskopoziomowe,
to znaczy, że programowanie w nich wymaga dużej wiedzy o budowie konkretnego proces ora . Program w ję -
zyku wys okopoziomowym je st kompilowany, czyli tłumaczony na język ma szynowy i dopiero taki przetłuma -
czony (a ponadto jes zcze dodatkowo przygotowany) program może być wykonany na komputerze. Najczę -
ściej jes t tak, że jedna ins trukcja wysokopoziomowa (taka , jak na przykład „je śli pole przed Tobą jes t wolne,
to krok naprzód, w przeciwnym ra zie obróć s ię w lewo”) jes t tłumaczona na wiele rozkazów mas zynowych.
Poniewa ż procesor wykonuje rozka zy a nie ins trukcje, więc wykonanie procesu w s ys temie z podziałem cza-
su może zos tać przerwane po dowolnym rozka zie, a zatem gdzie ś w trakcie wykonania ins trukcji języka wy-
sokie go poziomu. Z tego wynika, że programis ta nie może założyć, że instrukcje, z których buduje program,
są niepodzielne i wykonują s ię od początku do końca. W szczególności łyżwiarz wykonujący ins trukcję „je -
śli pole przed Tobą jes t wolne, to krok naprzód, w przeciwnym ra zie obróć się w le wo” może uznać, że krok do
przodu daje s ię wykonać, ale zanim go wykona inny łyżwiarz może zająć to pole (po uprzednim upewnieniu
się, że jes t ono jes zcze wolne).

Zatem niezależnie od przyjętego modelu wykonania analizowany przez nas program współbieżny może

prowadzić do zderzenia łyżwiarzy. W praktyce programy współbieżne za wsze analizuje s ię tak, jakby były wy-
konywane w przeplocie – w dowolnym przeplocie. Nie wolno przy tym założyć nic na temat niepodzielności in-
strukcji ję zyka, w którym programujemy. Okazuje się , że taki sposób analizy jes t odpowiedni także dla wyko-
nań równole głych. Zatem jeśli chcemy wyka zać, że program jes t niepoprawny, to wys tarczy znaleźć taki prze -
plot albo inaczej scenariusz wykonania , który prowadzi do błędnej s ytuacji. Aby uza s adnić, że program jes t
popra wny, trzeba udowodnić, że będzie dobrze dzia ła ł w ka żdym możliwym przeplocie. Jes t to trudne , b o z re -
guły tych przeplotów jes t nies kończenie wiele. W na s zym przykładzie znale źliśmy scenariusz prowadzący do
s ytuacji błędnej, więc program oka zał się być niepoprawny.

Powie dzieliśmy już, że programowanie współbieżne pole ga na umiejętnoś ci wykrywania s ytuacji prowadzą-
cych do niepożądanego zachowania programu i takim zs ynchronizowaniu procesów, a by uniknąć niepożą-
danej s ytuacji. Jednak częs to zachowanie programów współbieżnych jes t nieintuicyjne i zdarza s ię, że na-
we t doś wiadczony programis ty nie dos trzeże źródła problemu. Co gors za, błąd może w ogóle nie ujawnić się
podcza s tes tów! Wyobra źmy sobie, że uruchamiamy 100 razy na s z program dla łyżwiarzy i za każdym razem
Damian zdą ży wykonać ca łą instrukcję zanim ruch będzie wykonywać Beata. Wówczas błąd nie ujawni się,
a programista zyska pewnoś ć, że program jes t poprawny. Tymcza sem uruchamiając program na innym kom-
puterze, pod innym s ys temem operacyjnym, a nawet po ra z 101. na tym s amym komputerze może dojść do
feralnego przeplotu i program zakończy się błędem. Takie s ytuacje zdarzają s ię doś ć częs to w praktyce. W li-
teraturze opis ano na przykład błąd, który ujawnił s ię tuż przed pierws zym s tartem promu kos micznego. Pole -
ga ł on na tym, że komputer pomocniczy nie otrzymywał danych od komputera głównego. Było to o tyle dziw-
ne, że s ys tem był uprzednio poddany intens ywnym wielodniowym tes tom. Start opóźnił się o dwa dni, tyle
cza su zaję ło programis tom us talenie przyczyny błędu. Oka zało s ię, że b łąd pojawiał się jedynie wówczas ,
gdy moment włączenia jednego komputera trafiał w okno czas owe o s zerokości 15 ms od chwili włączenia
drugie go! Nic dziwne go, że tes ty tego nie wykryły tym bardziej, że nikt nie wyłączał komputera między kolej-
nymi tes tami!

< 12 >

Informa tyka +

Przykłady te poka zują, że powszechna praktyka znajdowania błę dów w programach s ekwencyjnych poprzez
krokowe uruchamianie programu pod kontrolą specjalnego programu uruchomieniowe go (ang. debugger)
w przypadku programów ws półbie żnych nie sprawdza się. Po pierws ze, można nie być ś wiadomym is tnienia
błę du pomimo intens ywnego tes towania. Po drugie , błędny scenariusz może ujawniać się bardzo rzadko i być
trudny do odtworzenia , a to jest niezbędne, żeby wykonać program krok po kroku.

Aby jes zcze dokładniej zilustrować, jak bardzo nieintuicyjne s ą błędy w programach współbieżnych, rozwa ż-
my dwa rze czywis te przykłady. Żyjemy w dobie Internetu, elektroniczne przelewy s ą w dzisiejs zych cza sa ch
codziennością . Przypuś ćmy, że program obsługujący bank, w którym mamy konto, pis ał programis ta zafa -
s cynowany współbieżnością , ale nie do końca zdający s obie s prawę z subtelnoś ci problemów, które trzeba
rozwią zać. Dla upros zczenia przyjmijmy też, że w banku znajduje się tylko nas ze konto, a jego aktualny s tan
jes t utrzymywany w zmiennej saldo. Zmienna to miejs ce w pamięci komputera , w którym jes t prze chowywa -
na pe wna wartoś ć, powiedzmy, że w tym przypadku 5000. Typowe ję zyki programowania zawierają ins truk-
cję przypis ania , która służy do nadania zmiennej pe wnej wartoś ci. Na przykład, jeśli pobieramy z konta kwo-
tę 1000 zł, to w programie realizującym taką operację powinno znaleźć się przypisanie zapis ywane jako sal-
do := saldo – 1000, czyli: od aktualnej wartoś ci zmiennej saldo odejmij 1000 i wynik wpisz znów do zmiennej
saldo (będzie ona wówcza s równa 4000). Podobnie przele w tysiąca złotych na na sze konta zos tanie zreali-
zowany podobnie saldo := saldo + 1000. Program obsługujący konto jes t współbieżny i umożliwia je dnocze -
sne wykonywanie kilku operacji na koncie, na przykład tworząc do obsługi ka żdej opera cji os obny proces . Je -
śli tera z zdarzy się, że w tym s amym cza sie pojawi się zlecenie przelewu na konto tys iąca złotych i pobrania
z tego konta tys iąca złotych, dojdzie do współbieżnego wykonania dwóch procesów, z których jeden zmniej-
s za zmienną saldo o 1000, a drugi zwięks za ją o 1000. I znów z pozoru ws zys tko jes t w porządku. Jaką kwo-
tę mamy na koncie na skutek obu tych operacji? Nie powinno się nic zmienić i w dals zym ciągu powinno to
być 5000. Tymcza sem oka zuje się, że współbieżne wykonanie takich ins trukcji przypis ania może spowodo-
wa ć, że zmienna saldo ma wartoś ć faktycznie 5000, ale równie dobrze może to być 6000 (jeśli ma my s zczę -
ś cie) lub 4000 (jeś li mamy pecha).

Czym jes t spowodowany błąd? Otóż programis ta założył, że przypis anie wykonuje s ię w całości. Wcale

tak być nie musi! Ins trukcja odjęcia wartoś ci 1000 od zmiennej saldo może zos ta ć przetłumaczona na 3 roz-
ka zy ma szynowe:

załaduj saldo do AX
odejmij 1000 od AX
prześlij AX do saldo

Jeśli proces y wykonają się w całości jeden po drugim, to końcowa wartość zmiennej saldo będzie faktycz-
nie równa 5000. Jeśli jednak przed przesłaniem do zmiennej saldo wartoś ci AX przez pierwszy proces , drugi
proces pobierze do BX wartoś ć zmiennej saldo (w dals zym cią gu 5000), to wykona się tylko jedna operacja:
zmniejs zenie albo zwięks zenie w zależnoś ci od tego, który z proces ów jako drugi prześle wartoś ć rejes tru do
zmiennej saldo. Skutki takiego „drobnego” przeoczenia programis ty mogą wię c być doś ć powa żne!

W rzeczywis tości dane o kontach klientów prze chowywane s ą w ba zie danych. Dos tęp do takiej bazy

danych może być realizowany ws półbie żnie , ale wszelkie modyfikacje zapis ów (rekordów) w ba zie s ą wyko-
nywane za pomocą niepodzielnych trans akcji, czyli ciągu operacji, które wykonują się jako jedna niepodziel-
na ca łoś ć.

Podobny (i chyba jes zcze bardziej nieintuicyjny) przykład polega na wielokrotnym zwięks zaniu wartoś ci pe w-
nej zmiennej o 1. Wyobra źmy sobie, że działa ją dwa proces y. Ka żdy z nich pięciokrotnie zwiększa wartość
zmiennej x o 1.

Pytanie: Jeśli początkowo zmienna x miała wartoś ć zero, to jaką wartoś ć będzie miała po zakończeniu

obu proces ów. Narzuca jąca się odpowiedź to 10, bo ka żdy proces pięciokrotnie zwięks zy x o 1, wię c łącznie
x zos tanie zwiększone o 10. Gdy jedna k przypomnimy s obie , że operacja zwięks zania x o 1 nie mus i być nie -
podzielna i może składać się z trzech rozkazów mas zynowych jak w poprzednim przykładzie, to z łatwością
dos trze żemy, że równie dobrze końcową wartoś cią x może być 5 (jeś li oba proces y bę dą wykonywać się „łeb
w łeb”, czyli na przemian po jednym rozka zie ja k w wykonaniu s ynchronicznym). Równie ła two spos trzeżemy,

> Programowa nie współbieżne w informa tyce i nie tylko

< 13 >

że tak naprawdę w zależnoś ci od przeplotu końcową wartoś cią x może być dowolna wartość między 5 a 10.
Ale już zupełnie niezgodna z intuicją jes t pra widłowa odpowiedź na pos tawione pytanie. Końcową wartoś cią
zmiennej x jes t dowolna wartoś ć między 2 a 10. Zachęcam do znalezienia przeplotu, który prowadzi do uzy-
skania na końcu wartości 2.

W podobną, choć nieco bardziej subtelną pułapkę zwią zaną ze ws półbie żnym zwiększaniem pe wnej zmien-
nej, wpadł je den z moich znajomych. Napis ał on pod s ystemem operacyjnym Linux w ję zyku C program, w któ-
rym dzia łało wiele proces ów (a dokładniej były to wątki, które w s ys temie Linux nieco różnią się od procesów,
choć dla na s ta różnica jes t dzis iaj nieis totna). Ka żdy z nich korzys ta ł z tej s amej zmiennej, na zwijmy ją x i za-
wierał ins trukcję x++, która w języku C oznacza zwięks zenie x o 1. Program pomimo tego, co przeds ta wiliśmy
poprzednio, działał poprawnie. Tak się bowiem złożyło, że kompila tor ję zyka C tłumaczył tę ins trukcję na je -
den rozka z ma s zynowy o na zwie s ymbolicznej inc. I ws zystko było dobrze, do chwili ... wymiany komputera
na leps zy. Można sobie wyobra zić, jaka jes t zdroworozs ądkowa reakcja programis ty, który po zakupie nowe -
go s przę tu s twierdza , że program, który dotychcza s działał bez problemu, nagle prze sta ł działać. Jednak po
wymianie płyty głównej program dalej nie działał. Kluczem do rozwią zania zagadki oka za ło się to, że nowy
komputer mia ł proces or wie lordze niowy. Po analizie dokumentacji proces ora oka zało się, że w architekturze
wielordzeniowej większość rozka zów ma s zynowych, w tym rozka z inc, nie jes t już niepodzielnych (nie blo-
kują magis trali). Efektem było „gubienie” niektórych operacji zwięks zenia dokładnie tak, jak w omawianym
przed chwilą przykładzie.

Powyższe dwa przykłady, oprócz trudnoś ci z analizą programów współbieżnych, poka zują jeszcze jedną wa ż-
ną dla programisty rzecz. Nie wolno dopuś cić do ws półbie żne go modyfikowania tej s amej zmiennej przez
wiele proces ów. Zauwa żmy ponadto, że gdyby ins trukcja zwiększania i zmniejs zania zmiennych wykonywa-
ły się w s posób niepodzielny to problemu nie byłoby. Albo innymi słowy, w dowolnym momencie co najwyżej
jeden proces może w tym s amym cza sie wykonywać pewien kluczowy fragment programu. Mówimy, że ten
fragment s tanowi s ekcję krytyczną , a s am problem wła ściwej s ynchronizacji proces ów nosi na zwę proble -
mu wzajemnego wykluczania.

Niektóre problemy s ynchronizacyjne pojawiają s ię tak czę sto w praktyce , że omawia się je na ka żdym wykła -
dzie na temat programowania pod nazwą kla s yczne problemy ws półbie żnoś ci. Problem wzajemnego wyklu-
czania pojawia się bardzo czę sto w codziennych s ytuacjach. Na przykła d w cza sie towarzyskiej, kulturalnej
dyskusji wielu os ób, co najwyżej je dna z nich w danym momencie powinna zabierać głos . Jeśli do komputera
jes t podłączona jedna drukarka , to korzys tać z niej może co na jwyżej je den proces . Fragment programu mo-
dyfikujący zmienną , z której korzys ta wiele proce sów może nara z wykonywać co najwyżej jeden proces (to
os tatnie wymagania można nieco os łabić, ale nie bę dziemy o tym mówić tutaj). Problem wzajemne go wyklu-
czania formułuje się za zwyczaj na przykładzie dwóch proces ów. Ka żdy z nich wykonuje cyklicznie fragment
na zwany tutaj własne sprawy, a nas tępnie fragment na zwany sekcją krytyczną zgodnie z poniżs zym s chema-
tem:

Powtarzaj:
własne spra wy
sekcja krytyczna

Włas ne s prawy jes t fragmentem programu, który nie intere suje nas z punktu widzenia s ynchronizacji Zakła -
da się, że proces może wykonywać wła sne spra wy dowolnie długo, może nawet zakończyć się tam w wyni-
ku błędu. Sekcja krytyczna to fragment wymagający s ynchronizacji. Zakłada się, że ka żdy proce s, który roz-
pocznie jej wykonanie po skończonym czasie ją s kończy (a więc w szczególności nie skończy s ię w niej z błę -
dem). Trzeba ws tawić odpowiedni fragment przed sekcją krytyczną i po sekcji krytycznej tak, aby zapewnić jej
wzajemne wykluczanie.

Rozwią zanie wydaje się pros te. Przeds tawimy go używając pojęć znanych z życia codzienne go. Po-

wiedzmy, że przed sekcją krytyczną stoi s ygnalizator (w programie jes t to po pros tu zmienna przyjmująca jed-

< 14 >

Informa tyka +

ną z dwóch wartoś ci) wyś wietlający ś wia tło zielone, jeśli nikogo nie ma w sekcji krytycznej i czerwone w prze -
ciwnym ra zie. Początkowo ś wiatło jes t oczywiś cie zielone . Proces , który chce wejś ć do sekcji krytycznej naj-
pierw sprawdza ś wiatło. Jeśli jes t zielone to prze łącza go na czerwone i wchodzi do sekcji krytycznej. Jeś li je d-
nak ś wiatło je st czerwone , to proces zatrzymuje s ię i czeka a ż ś wiatło zmieni s ię na zielone. Proce s wycho-
dzący z sekcji krytycznej prze łącza ś wiatło na zielone.

Rozwiązanie to je st jednak niepoprawne. Pierws zy proce s, który będzie chcia ł wejś ć do sekcji krytycz-

nej s pra wdzi ś wia tło. Zobaczy zielone. Jeśli tera z zanim proces zdą ży prze łą czyć ś wiatło, drugi proces zapra -
gnie wejś ć do sekcji krytycznej, to sprawdzi s ygnalizator, zobaczy jes zcze ś wiatło zielone i uzna , że droga wol-
na . Oba proces y prze łą czą ś wiatło na czerwone i spokojnie wykonają sekcję krytyczną. Mamy program, w któ-
rym wbrew wymaganiom, w sekcji krytycznej przebywają dwa proces y.

Rozwią za nia, które nie s pe łniają warunku wzajemne go wykluczania na zywamy rozwią zaniami niebezpiecz-
nym, a sam warunek przebywania w sekcji krytycznej co najwyżej jedne go procesu w tym s amym cza sie – wa -
runkiem bezpieczeńs twa . W ogólnoś ci warunek bezpieczeńs twa to warunek s pecyfikujący s posób s ynchro-
nizacji procesów. Rozwa żmy inne przykłady warunków bezpie czeństwa z życia codziennego. W przypadku
łyżwiarzy porus zających się po lodowisku wła snoś ć bezpie czeńs twa to po pros tu brak zderzeń z innymi łyż-
wiarzami i z bandą. Skrzyżowanie dróg można też traktować jako pewien s ys tem współbieżny. Proces ami s ą
tu samochody (dla upros zczenia przyjmijmy, że przejeżdżają one skrzyżowanie na wpros t i że obie drogi s ą
jednokierunkowe), a własnoś ć be zpieczeńs twa oznacza brak kolizji. Zauwa żmy, że przykłady te dobrze uza -
s adniają na zwę włas noś ć be zpie czeńs twa , gdyż jej brak prowadzi z reguły do groźnej s ytuacji. Podobnie jes t
w przypadku s ys temu komputerowego nie spełniające go wła snoś ci bezpieczeńs twa .

Powróćmy do przykładu wzajemnego wykluczania . Zmodyfikujmy nieznacznie poprzednie rozwią zanie –
nie ch s ygnalizator wyś wietla począ tkowo ś wiatło czerwone. Oka zuje się, że uzyskaliś my rozwią zanie be z-
pieczne! Faktycznie, w sekcji krytycznej przebywa w dowolnej chwili co najwyżej jeden proces . Tak naprawdę
nikt nigdy do niej jednak nie wejdzie. Ewidentnie nie je st to rozwią zanie, które bylibyśmy skłonni zaakcepto-
wać, choć w myś l dotychczas owych rozwa żań jes t ono popra wne.

Aby unikną ć te go typu rozwią za ń mus imy doprecyzować poję cie poprawności programu współbieżne -

go. Już wiemy, że rozwiązanie musi mie ć własnoś ć bezpieczeńs twa . Do tego dokładamy jes zcze wła snoś ć ży-
wotności, która w przypadku wzajemnego wykluczania brzmi tak: „ka żdy proces , który chce wejś ć do sekcji
krytycznej, w końcu do niej wejdzie”. Zauwa żmy, że nie żąda my, aby ka żdy proces w końcu ws zedł do sekcji
krytycznej, ale ograniczamy to żądanie jedynie do tych proces ów, które chcą tego, czyli zakończyły wykona -
nie wła snych spra w. Proces może bowiem nigdy nie zakończyć wła snych spra w, wię c żą danie , żeby ka żdy pro-
ces w końcu wszedł do sekcji krytycznej jes t zbyt s ilne.

W ogólnym przypadku żywotność oznacza , że ka żdy proces , który dotarł do fragmentu programu wy-

magającego s ynchronizacji w końcu przez ten fragment przejdzie . Popatrzmy na inne przykład y. W przypadku
skrzyżowa nia żywotnoś ć oznacza , że ka żdy proces w końcu przez nie przejedzie, w przypadku łyżwiarzy – że
ka żdy z nich w końcu wykona jakiś krok lub obrót.

Czym może przejawia ć się brak żywotnoś ci? w nas zym rozwią zaniu dos zło do zakles zczenia , czyli s ytuacji,
w której nic w s ystemie się nie dzieje. Żaden proces nie wykonuje pożyte cznej pracy, ws zystkie czekają na
zdarzenie , które nigdy nie na s tą pi. Jes zcze lepiej s ytuację zakles zczenie ilus truje nieco inny przykład. Przy-
puśćmy, że w s ystemie dzia łają dwa proces y. Ka żdy z nich w pe wnym momencie potrzebuje do dalszego dzia -
łania dos tęp do drukarki i skanera . Pierws zy proces zgła s za najpierw zapotrzebowanie na skaner. Takie zgło-
s zenia obs ługuje s ys tem operacyjny, który s twierdza , że skaner je st wolny, więc przydziela go pierws zemu
proces owi. Na stępnie drugi proces zgłas za chęć skorzys tania z drukarki. I znów s ys tem stwierdza , że druka r-
ka jes t wolna, więc przydziela ją proces owi. Tera z pierws zy proces prosi o drukarkę i musi czekać, bo drukar-

> Programowa nie współbieżne w informa tyce i nie tylko

< 15 >

kę dos tał drugi proces . Gdy drugi proces popros i o skaner, to również będzie musia ł czekać, bo skaner do-
stał pierws zy proces . Ale pierws zy proces nie zwolni skanera dopóki nie otrzyma drukarki, a drugi proces nie
zwolni drukarki, póki nie otrzyma skanera. Mamy zakles zczenie!

Przykłady zakles zczeń nietrudno znaleźć w życiu codziennym. Przeanalizujmy na przykład artykuł 25 punkt 1
Kodeksu Drogowego: ,,Kierujący pojazdem, zbliżając się do skrzyżowania, jes t obowiązany zachować s zcze -
gólną ostrożnoś ć i us tąpić pierws zeńs twa pojazdowi nadjeżdża jącemu z prawej strony (...)’’. Zatem w s ytu-
acji, gdy do skrzyżowania równorzędnego doje żdżają jednocześnie poja zdy ze ws zystkich czterech wlotów,
mamy zakles zczenie. Żaden poja zd nie może rus zyć, dopóki nie odjedzie ten z prawej strony. Ze względu na
s ymetrię tego układu nikt nigdy z takiego skrzyżowania nie powinien odjechać.

Jes zcze dotkliwiej s ytuację tę widać na rondzie. Kodeks drogowy nie wyróżnia tu konie czności innego

zachowania , więc na rondzie domyś lnie pierws zeńs two mają pojazdy wjeżdżające. Bardzo s zybko może do-
prowadzić to do całkowitego zakorkowa nia skrzyżowania i w konsekwencji zakles zczenia. Szczę śliwie, na
większoś ci tego typu skrzyżowań pod znakiem skrzyżowa nie o ruchu okrę żnym znajduje się równie ż znak
us tąp pierws zeństwa przeja zdu, co powoduje, że pierws zeńs two mają pojazdy znajdujące się już na rondzie.
Ale ... czy to rozwią zuje problem potencjalne go zakle szczenia? Oka zuje się, że nie!

Inny przeja w braku żywotnoś ci jes t znacznie ba rdziej subtelny. O ile zakles zczenie było w pewnym sens ie
globalnym brakiem żywotnoś ci i powodowało przes tój całego s ys temu, o tyle zagłodzenie polega na tym, że
jes t pe wien ,,pechowy’’ proces (lub proces y), które będą w nieskończonoś ć oczekiwać na możliwoś ć wzno-
wienia wykonania .

Rozwa żmy znów przykład skrzyżowania . Za łóżmy, że droga prowadzą ca na ws chód jes t drogą z pierw-

sze ństwem przejazdu. Zgodnie z artykułem 5 Kodeksu Drogowego ,,Uczes tnik ruchu i inna os oba znajdują-
ca się na drodze są obowią zani s tosować s ię do pole ceń i s ygna łów dawanych przez os oby kierujące ruchem
lub upra wnione do jego kontroli, s ygnałów ś wietlnych oraz znaków drogowych (...)”.

Zatem poja zd na rysunku 5, nadjeżdżający drogą z prawej s trony, nie może wjechać na skrzyżowanie,

jeśli zbliżają się do nie go poja zdy jadące drogą nadrzę dną. Jeśli droga ta jes t drogą ruchliwą , to może się zda-
rzyć, że cią gle na skrzyżowanie przybywają nowe poja zdy i ten pojazd nigdy nie przejedzie skrzyżowania . Do-
chodzi do jego zagłodzenia

Rysunek 5.
Możliwe „zagłodzenie” poja zdu nadjeżdżające go ulicą z prawej strony

Bardzo dobrze pojęcia zakles zczenia i zagłodzenia ilus truje inny kla s yczny problem współbieżnoś ci, problem
pięciu filozofów. Je st on przeds tawiany w pos taci na s tępującej anegdoty – patrz rysunek 6. Przy okrągłym

< 16 >

Informa tyka +

s tole siedzi pięciu filozofów. Poś rodku s tołu znajduje się (ciągle uzupełniany) półmisek z rybą. Przed ka żdym
filozofem leży talerz, a mię dzy ka żdymi dwoma talerzami le ży widelec. Tak wię c na s tole znajduje się pięć ta-
lerzy i pię ć widelców. Ka żdy filozof najpierw myś li, a gdy zgłodnieje sięga po oba widelce znajdujące się obok
je go talerza, nakłada s obie rybę, zjada ją , po czym odkłada widelce i wraca do myś lenia itd.

Rysunek 6.
Pięciu myślących filozofów przy stole z rybą (na ś rodku)

Widać, że ka żdy widelec jes t użytkowany prze z dwóch filozofów. Może s ię za tem zdarzyć, że głodny filozof
nie będzie mógł rozpocząć jedzenia natychmias t, bo będzie musiał pocze kać, a ż skończy jeść je go s ąsiad.
Warunek be zpieczeńs twa w przypadku te go problemu wyra ża fakt, że filozof może rozpocząć jedzenie tylko
wte dy, gdy ma oba widelce (znajdujące s ię przy jego talerzu) ora z że w dowolnej chwili ka żdym widelcem je
co najwyżej jeden filozof. Żywotnoś ć oznacza , że ka żdy filozof, który jes t głodny, w końcu bę dzie mógł rozpo-
cząć jedzenie. Zakładamy, że filozof w s kończonym cza sie skończy je dzenie, na tomia s t myślenie może trwać
dowolnie długo i w tym cza sie może zdarzyć się ws zys tko (łącznie z awarią procesu).

Rozwa żmy tera z kilka różnych możliwych zachowań filozofów (czyli programów wykonywanych prze z nich).
Pierws zy s pos ób „dzia łania” filozofa jes t nas tępujący. Gdy tylko zgłodnieje się ga po le wy widelec. Jeśli go
nie ma na s tole (bo używa go są siad ), to filozof czeka . Nas tępnie z lewym widelcem w garści filozof sięga
po prawy. I znów, jeśli widele c jes t zajęty, to filozof musi poczekać. Będąc w pos iadaniu obu widelców filozof
zjada rybę, po czym odkłada widelce na s tół. Za s tanówmy się, czy taki s chemat pos tępowania filozofa jes t
poprawny. Włas ność be zpieczeńs twa jes t zachowana , jednak nie ma żywotnoś ci. Może bowiem zdarzyć się
tak, że ws zyscy filozofowie je dnocze śnie zgłodnieją i ka żdy z nich sięgnie po lewy widelec. Ponie wa ż widelce
znajdują się na s tole, więc ka żdy filozof podniesie lewy widelec. Ale tera z na s tole nie ma już żadnego widel-
ca i wszyscy filozofowie oczekują na prawy widelec. Ponie wa ż żaden z nich nie odda już podnies ionego wi-
delca , wię c mamy zakles zczenie.

Przeanalizujmy teraz nieco inny s chemat działania filozofa. Załóżmy, że głodny filozof sprawdza , czy na stole są
oba potrzebne mu widelce. Jeśli tak, to podnosi je jednocześnie i rozpoczyna jedzenie. Jeśli jednak nie ma choć jed-
nego widelca, to filozof czeka nie podnosząc żadnego widelca. Przyjmujemy przy tym, że sprawdzenie, czy widelce
są na s tole i ich podniesienie jest realizowane w sposób niepodzielny. To założenie gwarantuje spełnienie własno-
ści bezpieczeńs twa. Czy to rozwią zanie jest żywotne? Okazuje się, że nie, choć tym razem nie dojdzie do zaklesz-
czenia. Istnieje jednak s cenarius z, w których dwóch filozofów może „zmówić się” przeciwko trzeciemu siedzące-
mu między nimi. Aby prześledzić ten przeplot ponumerujmy filozofów zgodnie z ruchem wskazówek zegara od 1 do
5 począwszy od filozofa u góry stołu. Najpierw głodnieje filozof numer 1. Ponieważ oba widelce są dostępne, więc
podnosi je i rozpoczyna jedzenie. Następnie głodnieje filozof numer 2 – jego właśnie spróbujemy zagłodzić (sic!).
Poniewa ż nie ma prawego widelca (używa go filozof 1), więc musi poczekać. Następnie głodnieje filozof numer 3.
Oba jego widelce s ą dostępne, więc może rozpocząć jedzenie.

Jeśli tera z filozof numer 1 zakończy jedzenie, to odłoży widelec. Nies tety filozof numer 2 nie może roz-

począć jedzenia, bo nie ma widelca, którym aktualnie je filozof numer 3. Zanim filozof numer 3 odłoży s wo-

> Programowa nie współbieżne w informa tyce i nie tylko

< 17 >

je widelce, znów głodnieje filozof numer 1. I znów filozof numer 2 nie może jeś ć z te go s amego powodu co na
początku: braku prawego widelca. Gdy w dals zym cią gu filozofowie 1 i 3 bę dą jedli na zmianę, to nie pozwo-
lą nigdy najeś ć się filozofowi numer 2. Mamy zatem s cenarius z prowadzący do zagłodzenia filozofa numer 2.

Poprawne rozwiązanie jes t nieco zmodyfikowanym wariantem pierws zym rozwiązania. Zauwa żmy, że do nie -
pożądanej s ytuacji dochodziło wtedy, gdy głodnieli wszyscy filozofowie. Wyobra źmy sobie tera z, że filozof,
który myśli odsuwa się lekko od s tołu. Gdy zgłodnieje, s pra wdza najpierw, czy przy s tole s ą już wszyscy po-
zos tali. Je śli tak, to czeka, a w przeciwnym ra zie przysuwa s ię do s tołu i pos tępuje jak w wariancie pierws zym:
próbuje podnieś ć najpierw lewy, potem prawy widelec, je, odkłada oba widelce. Na s tę pnie ods uwa się od s to-
łu zwalniając miejs ce przy nim i znów rozmyśla .

Rysunek 7.
Możliwy „przeplot” myślenia i jedzenia

Z racji upowsze chnienia się s ys temów wielozadaniowych, sieci, Internetu oraz wzros tu mocy obliczeniowej
współczesnych komputerów programowanie ws półbie żne bardzo zyskało na znaczeniu. Programy ws półbie ż-
ne częs to ma ją leps zą s trukturę niż programy sekwencyjne. Pows tają w sposób bardziej modularny, pozwala-
jąc programiście skupić się na jednym a spekcie rozwią zywanego problemu. Ponadto niektóre algorytmy (na
przykład sortowanie przez s calanie) w spos ób na turalny zapisuje się w pos tacie programu współbie żne go.

Program współbieżny można wykonywać na komputerze wieloprocesorowym, a także na komputerze wyposażo-
nym tylko w jeden proces or. Gdy faktycznie dochodzi do wykonywania kilku czynności w tym s amym czasie mówi-
my o wykonaniu równoległym (możliwym na wielu procesorach lub procesorze wielordzeniowym). Inną techniką re-
alizacji współbieżności jest wykonanie w przeplocie implementowane przez systemy operacyjne z podziałem cza su.

Oprócz zalet techniki programowania mają także wady. Programowanie współbie żne jes t trudne. Programy
współbie żne s ą trudne do analizy. Częs to ich działanie je st nie zgodne z intuicją . Utrudnione jes t również wy-
krywanie i usuwanie błę dów. Błędny s cenarius z może bowiem ujawniać się bardzo rzadko. To z kolei powodu-
je, że trudno jes t go odtworzyć w celu znalezienia błędu podcza s krokowego wykonania programu.

Program współbieżny może mieć wiele scena riuszy wykonań. Popra wnoś ć oznacza brak niepożądanych za-
chowań w żadnym z możliwych przeplotów. Program mus i być be zpieczny, czyli spełniać wszys tkie s tawia -
ne mu wyma gania s ynchronizacyjne ora z żywotny. Ta druga wła snoś ć oznacza , że żaden proces nie oczekuje
w nieskończonoś ć na zajś cie zdarzenia, które pozwoli mu kontynuować dzia łanie.

< 18 >

Informa tyka +

Aby uła twić programis tom tworzenie poprawnych programów ws półbie żnych wymyślono wiele różnych me -
chanizmów s ynchronizacji i metod komunika cji proces ów. Ich omówienie i analiza wykracza je dnak poza za -
kres tych zaję ć.

1. Ben-Ari M., Podsta wy programowania współbie żnego i rozpros zonego. WN-T, Wa rszawa 2009
2. http:// os ilek.mimuw.edu.pl/ inde x.php?title=Programowa nie _współbie żne _i_rozproszone/ PWR_Wykład _1

Nota tki

< 19 >

W projekcie

, poza wykładami i warsztatami,

przewidziano następujące działania:

■

24-godzinne kursy dla uczniów w ramach modułów tematycznych

■

24-godzinne kurs y metodyczne dla nauczycieli, przygotowujące

do pracy z uczniem zdolnym

■

nagrania 60 wykładów informatycznych, prowadzonych

przez wybitnych specjalistów i nauczycieli akademickich

■

konkursy dla uczniów, trzy w ciągu roku

■

udział uczniów w pracach kół naukowych

■

udział uczniów w konferencjach naukowych

■

obozy wypoczynkowo-naukowe.

Szczegółowe informacje znajdują się na stronie projektu