This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
- Wprowadzenie do BACI
- Składnia C--
- Jak używać BACI
- Ćwiczenia
- cobegin
- Problem sekcji krytycznej
- Semafory
- random
- Zadania domowe
Wprowadzenie do BACI
BACI (Ben-Ari Concurrent Interpreter) jest narzędziem do nauki pisania programów wykorzystujących współbieżność. Programy pisze się w C--, uproszczonym dialekcie języka C++, wyposażonym dodatkowo w konstrukcje do wykonywania równoległych procesów i ich synchronizacji. Skompilowany program jest uruchamiany przez interpreter, który symuluje środowisko wieloprocesowe, przeplatając instrukcje z równoległych procesów w sposób losowy (naśladując w ten sposób mechanizm wykonywania równoległych procesów/wątków w systemach operacyjnych).
(Fragmenty poniższego tekstu pochodzą z: https://inside.mines.edu/~tcamp/baci/baci_index.html)
Składnia C--
Konstrukcje kompilatora BACI C-- są podzbiorem konstrukcji kompilatora C++:
- Nie ma plików innych niż standardowe wejście i wyjście:
cout,cin. - Są dostępne tylko proste typy danych C/C++:
intorazchar. Wszystkie zmienne muszą być zadeklarowane na początku bloku kodu, w którym występują. - Jest dostępny typ łańcuchowy
string. BACI posiada wbudowane funkcje operujące na łańcuchach takie jak:stringCopy,stringCompare,stringConcat, itp. - Dostępne są tablice typów prostych. Deklaracje tablic są zgodne ze składnią zwykłego C.
- Dostępne są funkcje i rekurencja. Parametry przekazywane są przez wartość lub przez referencję. Wykonanie rozpoczyna się od wywołania funkcji
main(). - Dostępne są konstrukcje
if-else,switch/case,for,while,do-while,breakorazcontinue. Składnia ich jest zgodna z C/C++.
Jak używać BACI
Na zajęciach z BACI będziemy korzystać z systemu Linux uruchomionego na komputerach lokalnych (nie na maszynach wirtualnych). Programy bacc i bainterp pojawią się maksymalnie 5 minut po uruchomieniu Linuksa w Laboratoriach. Jeśli student zaloguje się wcześniej to nie będzie miał odpowiedniego katalogu w PATH; może wtedy uruchamiać program z pełną ścieżką, np.: /opt/baci/current/bacc.
BACI na maszynie wirtualnej
Jeśli chcesz korzystać z BACI na swojej maszynie wirtualnej, wykonaj poniższe kroki.
Pobierz archiwum z BACI dla Linuksa: https://inside.mines.edu/~tcamp/baci/balnxxe64-2012Oct01.tar.gz
Rozpakuj je poleceniem:
tar xvzf balnxxe64-2012Oct01.tar.gz
Wejdź do rozpakowanego katalogu i dodaj plikom kompilatora i interpretera prawo do wykonywania:
chmod +x bacc
chmod +x bainterp
Aby uruchamianie narzędzi BACI (kompilatora, interpretera, itd) było możliwe w dowolnym katalogu bez konieczności podawania całej ścieżki, rozpakowany katalog należy dodać do zmiennej środowiskowej PATH. W tym celu wykonanaj następujące kroki.
Ustal pełną ścieżkę do rozpakowanego katalogu, np. wywołując polecenie pwd w momencie, gdy katalog ten jest katalogiem roboczym.
Wywołaj polecenie:
nano ~/.bashrc
i na końcu otwartego pliku dodaj:
PATH=$PATH:sciezka
export PATH
gdze sciezka jest ustaloną przed chwilą pełną ścieżką do rozpakowanego katalogu. Zapisz plik i wyjdź.
Zamknij bieżące okno terminala i uruchom kolejne. Sprawdź efekt, wywołując kompilator BACI poleceniem bacc (powinna pojawić się prośba o podanie pliku źródłowego).
Plik z kodem źródłowym BACI C-- musi posiadać rozszerzenie .cm. By wykonać program w BACI, należy wykonać dwa kroki:
- Skompilować plik
.cmby otrzymać plik PCODE (.pco)- Wywołanie:
bacc [flagi_opcjonalne] plik_źródłowy - Flagi opcjonalne:
-hpokazuje pomoc-ctworzy plik obiektowy.pobdo późniejszego zlinkowania
- Wywołanie:
- Uruchomić plik PCODE (
.pco) w interpreterze by wykonać program- Wywołanie:
bainterp [flagi_opcjonalne] plik_pcode - Flagi opcjonalne:
-duruchomienie debuggera-epokaż rekord aktywacji (AR) na wejściu do każdego procesu-xpokaż AR na wyjściu z każdego procesu-tzgłoś zakończenie procesów-hpokaż pomoc-ppokaż instrukcje PCODE w czasie jak są wykonywane
- Wywołanie:
Ćwiczenia
cobegin
W bloku cobegin umieszczamy listę procesów, które mają być uruchomione równolegle. Ich kod znajduje się we wcześniej zdefiniowanych funkcjach. Blok ten nie może być pominięty i musi występować w programie.
Przykład 1
void hello (char id)
{
cout << "Hi! I am a process!" << endl;
cout << "My ID is: " << id << endl;
cout << "Bye!" << endl;
}
main()
{
cobegin {
hello('A'); hello('B'); hello('C');
}
cout << "All processes finished" << endl;
}
Zadanie 1.
Skompiluj i uruchom przykład 1:
bacc zad1.cm
bainterp zad1.pco
Zaobserwuj jak losowo przeplatają się kolejne kroki wykonywania poszczególnych procesów.
Zadanie 2.
Napisz program uruchamiający 2 procesy. Każdy proces w pętli 5 razy inkrementuje zmienną globalną suma. Na końcu program wypisuje wartość zmiennej suma. Uruchom program kilkukrotnie. Jakie sa wyniki działania programu? Dlaczego?
Przyczyną niepożądanego zachowania jest to, że inkrementacja zmiennej suma, która w kodzie C-- stanowi jedną linijkę, w kodzie PCODE zostaje rozbita na mniejsze instrukcje (Wczytaj, Dodaj, Zapisz). Wykonywanie procesu może zostać przerwane po wczytaniu, a przed zapisaniem zmiennej. Jeżeli w tej przerwie w wykonaniu procesu A inny proces B również wczyta wartość zmiennej, to w efekcie zmienna zostanie powiększona tylko raz, a nie dwa razy.
Problem sekcji krytycznej
Podstawowy problem programowania współbieżnego, do którego można sprowadzić wiele zadań związanych z równoległym wykonywaniem procesów, to problem sekcji krytycznej. Można go opisać następująco:
Założenia:
- N procesów konkuruje o dostęp do współdzielonego zasobu (zasobów)
- W każdym procesie jest segment kodu programu, zwany sekcją krytyczną, w którym ma miejsce dostęp do współdzielonego zasobu
Problem: Jak zapewnić, aby w czasie gdy jeden proces wykonuje swoją sekcję krytyczną, żaden inny proces nie miał zgody na wykonanie swojej sekcji krytycznej?
W przypadku programu z przykładu 1, współdzielonym zasobem jest standardowe wyjście, a sekcją krytyczną – fragment kodu wypisujące powitanie procesu na standardowe wyjście. W programie z zadania 2, współdzielonym zasobem jest zmienna suma.
Jednym z mechanizmów rozwiązywania problemu sekcji krytycznej są semafory.
Semafory
Semafory stanowią mechanizm synchronizacji procesów. Semafor można rozumieć jako obiekt strzegący dostępu do zasobu. Semafor jest reprezentowany przez wartość – nieujemną liczbę całkowitą. Jeżeli wynosi ona zero, to zasób jest zajęty i na dostęp do niego proces musi zaczekać. Jeżeli wartość jest większa niż zero, to proces otrzymuje dostęp do zasobu.
Na semaforze (typ danych semaphore) można wykonać trzy operacje:
- Inicjalizacja:
initialsem( semaphore & s, int initial_value ); - Opuszczenie semafora:
wait(semaphore & s) - Podniesienie semafora:
signal(semaphore & s)
Funkcja wait() działa następująco:
- Jeżeli
s == 0, to proces zostaje uśpiony (w oczekiwaniu na podniesienie semafora) - Jeżeli
s >= 1, tos := s-1i proces kontynuuje wykonanie
Funkcja signal() działa następująco:
- Jeżeli
s == 0i są procesy oczekujące (uśpione w funkcjiwait()), to obudź jeden z nich i kontynuuj - Jeżeli nie ma procesów oczekujących, to
s := s+1i kontynuuj
Istotne jest, że wykonanie każdej z tych funkcji jest niepodzielne – nie może zostać przerwane w trakcie wykonywania (tak jak w powyższym problemie z inkrementacją zmiennej). Nasuwa to poboczne pytanie, jak takie semafory są zaimplementowane. W prawdziwych systemach mogą do tego służyć na przykład specjalne instrukcje procesora typu compare-and-swap.
W BACI, oprócz semaforów ogólnych, są też semafory binarne (binarysem), przyjmujące tylko wartości 0 i 1. Semafor binarny jest wystarczający do rozwiązania prostego problemu sekcji krytycznej.
Poniższy przykład pokazuje, jak użyć semaforów do zapewnienia, aby wypisywanie swojego identyfikatora przez procesy z przykładu 2 nie przeplatało się.
Przykład 2
binarysem print_semaphore;
void hello (char id)
{
wait(print_semaphore);
cout << "Hi! I am a process!" << endl;
cout << "My ID is: " << id << endl;
cout << "Bye!" << endl;
signal(print_semaphore);
}
main()
{
initialsem(print_semaphore,1);
cobegin {
hello('A'); hello('B'); hello('C');
}
cout << "All processes finished" << endl;
}
random
BACI zapewnia funkcję do generowania liczb pseudolosowych:
int random(int range);
Funkcja zwraca pseudolosową liczbę całkowitą z zakresu [0, range-1]
Zadanie 3
Skompiluj i uruchom przykład 2. Postaraj się zrozumieć, w jaki sposób poprawiony kod zapewnia prawidłowe działanie programu.
Zadanie 4
Popraw program z zadania 2.
Zadanie 5
W tym programie będą trzy procesy. Dwa z nich generują losową liczbę i zapisują je w globalnych zmiennych (np. liczba1 i liczba2). Trzeci wątek ma za zadanie wypisać ich sumę na standardowe wyjście. Do synchronizacji użyj jednego semafora.
Zadanie 6
Napisz program, który wypisuje na standardowe wyjście kwadraty kolejnych liczb całkowitych od 1 do 40 przy użyciu czterech procesów: procesy powinny naprzemiennie obliczać kolejne wartości, nie powtarzając niepotrzebnie obliczeń, tzn. w praktyce każdy z procesów przeliczy około 10 liczb. Dodatkowo, każdy proces po zakończeniu obliczeń powinien wypisać ile liczb przeliczył.
Zadania domowe
Zadanie domowe 1
Napisz program seq.cm z trzema dowolnymi procesami (np. wypisującymi swoją nazwę) zsynchronizowanymi w taki sposób, aby zawsze najpierw wykonał się proces 1, po nim proces 2, a na końcu proces 3. Wszystkie procesy muszą zostać zainicjowanej w tym samym bloku cobegin!
Zadanie domowe 2
Napisz program prod-cons.cm z dwoma procesami: producentem i konsumentem. Producent "produkuje" 10 losowych liczb z zakresu (0,N-1) (N wybierz dowolnie). Konsument ma za zadanie wypisać te liczby na standardowe wyjście ("skonsumować") w kolejności, w jakiej zostały wyprodukowane. Procesy powinny komunikować się przy użyciu globalnej zmiennej i dwóch semaforów. Jeden semafor będzie sygnalizował konsumentowi, czy w globalnej zmiennej znalazła się już nowa liczba do skonsumowania. Drugi semafor będzie znakiem dla producenta, że ostatnia wartość zapisana w globalnej zmiennej została już skonsumowana i można ją nadpisać kolejną wyprodukowaną liczbą.