Implementacja blokady futex dla systemu MINIX 3

(termin oddawania: 23.01.2012, godz. 23:59)

Futex (czyli fast userspace mutex) to rodzaj szybkiej blokady, która pozwala na rozwiązanie podstawowego problemu wzajemnego wykluczania. Niektóre bardziej złożone typy blokad (np. semafory albo kolejki wiadomości) mogą zostać zaimplementowane z użyciem futeksów. Szybkość futeksa polega na tym, że w przypadku braku rywalizacji o dostęp do blokady nie są wykorzystywane żadne wywołania systemowe.

Twoim zadaniem jest zaimplementować blokadę futex w systemie MINIX 3.

Specyfikacja

Aby skorzystać z blokady futex, trzeba będzie dołączyć plik nagłówkowy sys/futex.h:

#include <sys/futex.h>

Po dołączeniu tego pliku dla programisty dostępny jest następujący interfejs biblioteki:

Interfejs

futex_t
Typ instancji blokady.
int futex_init(futex_t *f)
Funkcja inicjalizująca instancję otwartej blokady.
Wywołanie futex_init na uprzednio zainicjowanej blokadzie ma nieokreślone działanie.
Funkcja zwraca 0 w przypadku sukcesu i wartość niezerową w przypadku porażki lub błędu.
int futex_destroy(futex_t *f)
Funkcja niszcząca instancję blokady i zwalniająca odpowiednie zasoby. Po zniszczeniu, instancja blokady musi być ponownie zainicjalizowana za pomocą futex_init przed ponownym jej użyciem.
Wywołanie futex_destroy na niezainicjowanej bądź zniszczonej blokadzie ma nieokreślone działanie.
Zniszczenie blokady, na której czekają jakieś procesy, powoduje obudzenie tych procesów i wyjście przez nie z funkcji futex_lock zwracając dowolny kod błędu (niezerową wartość).
Można założyć, że każda zainicjalizowana blokada typu futex zostanie kiedyś zniszczona.
Funkcja zwraca 0 w przypadku sukcesu i wartość niezerową w przypadku porażki.
int futex_lock(futex_t *f)
Funkcja zakładająca blokadę na instancję futeksa. W przypadku braku rywalizacji do blokady, funkcja nie wywołuje żadnego wywołania systemowego. W momencie rywalizacji może zostać wywołane odpowiednie wywołanie systemowe, które musi być obsłużone przez serwer IPC. Procesy rywalizujące o blokadę powinny być usypiane - niepotrzebne aktywne oczekiwanie skutkuje obniżeniem oceny!
Jeśli blokada zostanie zniszczona podczas oczekiwania przez proces na jej podniesienie, funkcja futex_lock powinna się zakończyć i zwrócić dowolny kod błędu (niezerową wartość).
Wywołanie futex_lock na niezainicjowanej bądź zniszczonej blokadzie ma nieokreślone działanie.
Funkcja zwraca 0 w przypadku sukcesu i wartość niezerową w przypadku porażki.
int futex_unlock(futex_t *f)
Funkcja zwalniająca założoną blokadę na instancję futeksa. W przypadku braku rywalizacji do blokady, funkcja nie wywołuje żadnego wywołania systemowego. W momencie rywalizacji może zostać wywołane odpowiednie wywołanie systemowe, które musi być obsłużone przez serwer IPC.
Wywołanie futex_unlock na niezainicjowanej, zniszczonej bądź podniesionej blokadzie ma nieokreślone działanie.
Funkcja zwraca 0 w przypadku sukcesu i wartość niezerową w przypadku porażki.

Aby rozjaśnić definicje, został przygotowany przykładowy plik nagłówkowy.

Konieczne jest zaimplementowanie blokady według powyższego interfejsu. Zmiana prototypów powoduje automatyczne uzyskanie 0 punktów za zadanie. Strukturę futex_t można modyfikować do woli!

Zauważ, że blokada typu futex nie musi gwarantować żywotności rozwiązania, a jedynie jego bezpieczeństwo!

Pomocne informacje

Wzorcowe rozwiązanie wymaga użycia funkcji, które w atomowy sposób modyfikują pamięć. Taką funkcją jest np. omawiana na wykładzie instrukcja test-and-set. Funkcje atomowe można umieścić w kodzie na dwa sposoby: jako odpowiednie instrukcje asemblera (funkcja asm), lub skorzystać z wbudowanych w GCC funkcji atomowych. Ze względu na prostotę, omówiony zostanie drugi sposób użycia funkcji atomowych.

Wykorzystanie GCC w MINIX 3

Domyślnym kompilatorem w systemie MINIX jest ACK. Niestety, nie zawiera on implementacji funkcji atomowych, w związku z tym biblioteka zostanie zbudowana z użyciem GCC.

Na początku należy zainstalować GCC poleceniem:

# pkgin install gcc44

Następnie należy ustawić odpowiednią architekturę procesora dla GCC. Aby to zrobić, należy w pliku /usr/src/lib/gnu_build.sh pod linijką:

export CC=gcc

dopisać linijkę:

export CFLAGS="-march=i686"

Teraz trzeba zbudować biblioteki i pliki nagłówkowe dla GCC, czyli w katalogu /usr/src wywołać polecenie:

# make gnu-includes gnu-libraries

Teraz we wszystkich bibliotekach można korzystać z funkcji atomowych wbudowanych w GCC.

Aby przyspieszyć ten proces, został przygotowany domyślny obraz dysku systemu MINIX, zawierający zainstalowany kompilator GCC oraz zbudowane biblioteki w architekturze i686.

Przykładowe programy

Do treści zostały przygotowane przykładowe programy, testujące poprawność zaimplementowanej blokady:

```
basic_test.c
```
Program ten testuje poprawną inicjalizację, zamknięcie, otwarcie i zniszczenie blokady.
```
numbers.c
```
Program ten testuje bezpieczeństwo, dodając do siebie 200000000 jedynek.

Jeśli co najmniej jeden z tych programów nie będzie działał poprawnie, nie można uzyskać więcej niż 5 punktów za zadanie.

Wysyłanie rozwiązania

Rozwiązania należy przesyłać ze swojego konta na komputerze students za pomocą skryptu submit na adres solab(at)mimuw.edu.pl.

Format wysyłanej paczki

Wewnątrz spakowanego archiwum powinien znaleźć się katalog modified/, w którym musi znajdować się drzewo wszystkich zmodyfikowanych plików. Na przykład, jeśli rozwiązanie modyfikuje plik /usr/src/include/minix/com.h, w archiwum musi znajdować się kopia zmodyfikowanego pliku, dostępna pod ścieżką:

modified/usr/src/include/minix/com.h

Aby sprawdzić, czy rozwiązanie zostało prawidłowo spakowane, należy wykorzystać przygotowane skrypty testujące. Ich użycie jest łatwe: wystarczy rozpakować archiwum ze skryptami do katalogu z rozwiązaniem (nie do katalogu modified!), a następnie na czystej instalacji systemu należy wewnątrz archiwum ze skryptami wykonać polecenie:

# make

Skopiuje ono wszystkie zmodyfikowane pliki do odpowiednich katalogów systemowych. Następnie można wykonać polecenie

# make compile

Skompiluje ono na nowo wszystkie biblioteki oraz skompiluje i zainstaluje nową wersję serwera IPC.

Jeśli wszystko się powiedzie i rozwiązanie jest poprawne, to po ponownym uruchomieniu masyzny załączone programy testowe powinny się kompilować za pomocą GCC i uruchamiać bez błędów.

W ramach rozjaśnienia zostało udostępnione przykładowe archiwum, które zawiera rozwiązanie dodające wywołanie systemowe printmessage, znane z pierwszego scenariusza. W archiwum package.tar.gz załączone są skrypty testujące poprawność rozwiązania.

Wysłanie paczki w innym formacie, na którym nie działają skrypty instalujące rozwiązanie w systemie, powoduje automatyczne otrzymanie 0 punktów za zadanie!

Zalecana literatura dodatkowa

Futexes Are Tricky - artykuł Ulricha Dreppera omawiający działanie blokady futex
GCC Atomic Bulitins - lista dostępnych funkcji atomowych w GCC

Pytania

Wszelkie pytania należy kierować do Maćka Wekseja (mw262978(at)mimuw.edu.pl), po wcześniejszym sprawdzeniu FAQ.