Do spisu tresci tematu 3

• Ogolne cechy
• Struktury danych
• Funkcja semget ()
• Funkcja semop ()
• Funkcja semctl ()
• Funkcja wewnetrza sem_exit ()
• Bibliografia

• Najwazniejsze struktury
• Struktury uniewaznien
• Usuwanie z kolejki operacji wstrzymanych
• Naglowek zestawu semaforow

• Zastosowanie: synchronizacja procesow, ochrona zasobow dzielonych np: dostepu do segmentow pamieci dzielonej).
• Pojedyncza instancja tego mechanizmu jest zestaw semaforow (tj tablica pojedynczych semaforow). W angielskich opisach uzywa sie czesto terminu 'set of semafores', jednakze jak pokazuje algorytm semop kolejnosc semaforow w zestawie moze byc istotna, nalezy wiec unikac tlumaczenia slowa 'set' jako zbior.
• Operacje na zestawie wykonywane sa niepodzielnie (eliminacja warunku koniecznego wystapienia blokady - przetrzymywania i oczekiwania - dla zestawu semaforow).
• Mozliwosc testowania i zmiany wartosci pojedynczego semafora.
• Mozliwosc oczekiwania na wartosc semafora rowna zero.
• Opcja operacji nieblokujacych (flaga IPC_NOWAIT).
• Problem: proces opuscil semafor ochrony zasobow i zakonczyl nieoczekiwanie dzialanie - rozwiazanie: struktury uniewaznien umozliwiajace odtworzenie wartosci semafora z przed operacji wykonanych z flaga SEM_UNDO.
• Wartosc inicjalna kazdego semafora jest rowna zero.

• Struktura naglowkowa dla zestawu semaforow -- semid_ds (rys 1) zawierajaca:
• strukture ipc_perm
• pole sem_otime do zapisu czasu ostatniego zakonczenia funkcji semop.
• pole sem_ctime do zapisu czasu ostatniej zmiany w naglowku instancji.
• struct sem *sem_base - tablice semaforow.
• wskazniki do kolejki pending - opis przy funkcji semop
• undo - wskaznik na glowe listy struktur uniewaznien - opis przy funkcji semop
• pole nsems - do przechowywania liczby semaforow w zestawie.
• Semary[SEMMNI] -globalna tablica w przestrzeni adresowej jadra wskaznikow do semid_ds , czyli naglowkow wszystkich istniejacych instancji mechanizmu semaforow
• int used semids - liczba zestawow semaforow w systemie
• int used sems - liczba semaforow w systemie
• struct wait_queue* sem_lock - wskaznik do kolejki procesow spiacych w oczekiwaniu na zakonczenie modyfikacji wejscia tablicy semary przez inny proces.
• sem_seq - patrz IPC ogolnie
• max_semid - najwiekszy uzywany indeks w tablicy semary, tj. przypisany istniejacej instancji mechanizmu.

SEMMNI 128 /* max liczba zestawow */
SEMMSL 32 /* <=512 max liczba semaforow w zestawie */
SEMOPM 32 /* max liczba operacji dla jednego wywolania semop */
SEMVMX 32767 /* max wartosc semafora */

int sys_semget (key_t klucz, int ilosc_semaforow, int flagi)

• Sprawdz poprawnosc danych.
• W zaleznosci od tego czy bedzie tworzony nowy zestaw semaforow wykonaj:
• findkey() lub
• newary()

(funkcje te sa opisane ogolnie w temacie IPC ogolnie)

 findkey (key_t key):

• Przeszukaj tablice wskaznikow do zbioru semaforow od 0 do maksymalnego numeru uzywanego zestawu.(max_semid).
• Jezeli jakas pozycja bedzie w trakcie modyfikacji(IPC_NOID) to zasnij w kolejce sem_lock : (sleep_on (&sem_lock)).
• Zwroc znaleziony index lub -1

newary (key_t klucz, int ilosc_semaforow, int flagi):

• Sprawdz poprawnosc danych.
• Sprawdz czy liczba zbior semaforow nie przekroczy maksymalnej dozwolonej liczby .
• Znajdz wolne miejsce w tablicy wskaznikow do zbiorow semaforow.
• Zaznacz jako modyfikowany(IPC_NOID).
• Alokuj pamiec:
• spojny obszar na naglowek zestawu oraz
• tablice semaforow .
• Wypelnij zerem ( funkcja memset (sma, 0, rozmiar)) .
• Wypelnij strukture praw dostepu (sem_perm) .
• Aktualizuj zmienne globalne
• Przylacz do tablicy nowa strukture
• Jesli jakis proces zasnal przy wywolaniu findkey() to go obudz ( wake_up() ) .
• Zwroc wartosc: indeks + (globalny_licznik)*(max_ilosc_zbioru_semaforow) lub blad.

• Interfejs
• Algorytm
• Funkcja try_semop ()
• Funkcja do_semop ()
• Funkcja update_queue ()
• Wnioski koncowe

Interfejs.

Ponizsza funkcja sluzy do niepodzielnego wykonania wielu operacji na semaforach tego samego zestawu.

int sys_semop (int semid,struct sembuf* tsops, unsigned nsops)

semid - deskryptor zestawu semaforow
nsops - liczba operacji do wykonania na zestawie (0 < nsops < SEMOPM, nie powinna przekroczyc rozmiaru tablicy tsops - system nie wykryje tego bledu i bedzie pobieral informacje z poza tablicy, az strach pomyslec czym to grozi!)
tsops - wskaznik do tablicy operacji na poszczegolnych semaforach zestawu. Pojedyncza operacja jest opisywana struktura sembuf:

struct sembuf {

ushort sem_num; /* numer semafora w zestawie (indeks tablicy sem_base)*/
short sem_op; /* wartosc dodawana do aktualnej wartosci semafora, jesli 0 to czekamy na wartosc semafora = 0 */
short sem_flg /* opcjonalne flagi: SEM_UNDO, IPC_NOWAIT */
}

Pomyslny powrot: 0 (wszystkie operacje z tablicy tsops wykonano poprawnie).
Mozliwe errno: EINVAL, E2BIG, EFAULT, EIDRM, EACCES, EINTR.

Algorytm

• Sprawdz argumenty:
  
• nieujemnosc nsops i semid (return -EINVAL jesli ujemne)
• czy nsops miesci sie w dopuszczalnej liczbie operacji dla jednego wywolania semop (jesli nsops > SEMOPM return -E2BIG)
• czy wskaznik do tablicy operacji tsops nie ma wartosci NULL (-EFAULT jesli tak)
• czy wskazywana przez tsops tablica nalezy do przestrzeni adresowej procesu wolajacego semop (funkcja verify_area ())
• Skopiuj tablice operacji do przestrzeni adresowej jadra (funkcja memcpy_fromfs()) - po to aby w przyszlosci nie trzeba bylo wielokrotnie odwolywac sie do przestrzeni procesu uzytkownika. Tablica tworzona przez jadro ma zawsze rozmiar SEMOPM (zupelnie jakby pamiec byla za darmo!).
• Oblicz indeks tablicy instancji dla semid, jezeli pozycja o tym indeksie jest oznaczona jako IPC_UNUSED lub IPC_NOID (w trakcie modyfikacji) to return -EINVAL.
• Sprawdz waznosc deskryptora semid (return -EIDRM jesli niewazny).
• Przejrzyj tablice operacji od 0 do nsops sprawdzajac czy numer semafora na ktorym ma byc wykonana operacja jest mniejszy od liczby semaforow w zestawie (return -EFBIG jesli znajdziesz wiekszy). Zapamietaj tez na pomocniczych zmiennych czy wystapily jakies flagi SEM_UNDO i operacje inne niz czekanie na wartosc zerowa semafora.
• Sprawdz prawa dostepu (funkcja ipcperms () ), jesli wszystkie operacje oczekuja na 0 to tylko czytania, w p. pzypadku tylko pisania (return -EACCES w przypadku braku odpowiednich praw).
• Wywolaj funkcje wewnetrzna try_semop () ktora orzeka czy wszystkie wyspecyfikowane operacje mozna wykonac od razu, tj. bez oczekiwania:
• Wywolanie try_semop () oddalo wartosc < 0 (kod bledu).
  W takim razie przekaz otrzymany kod bledu dalej jako wartosc powrotu z funkcji semop (). KONIEC
• Jesli pojawily sie jakies operacje z flaga SEM_UNDO, to trzeba sie upewnic czy dla zestawu semaforow semid i procesu ktory wywolal semop istnieje struktura uniewaznien (struct sem_undo) W naglowku procesu przechowywanym w tablicy procesow jest pole semundo bedace wskaznikiem do poczatku listy struktur uniewaznien zwiazanej z tym procesem. Na liscie znajduja sie struktury uniewaznien dla tych zestawow semaforow na ktorych proces wywolal kiedys semop z flaga SEM_UNDO przy ktorejs z operacji. Struktury uniewaznien dla tego samego zestawu takze powiazane sa w liste przez pole id_next , aby mozna bylo je usunac przy usuwaniu zestawu semaforow. Na poczatek tej listy wskazuje pole undo z naglowka zestawu. Pole semadj jest tablica krotkich liczb calkowitych, o rozmiarze rownym rozmiarowi zestawu semaforow (tzw. tablica wartosci dostosowawczych). To tu wlasnie przechowywane sa dla poszczegolnych semaforow zestawu zanegowane sumy wszystkich operacji wykonanych na tych semaforach z flaga SEM_UNDO. Cos w rodzaju bilansu operacji semaforowych wykonanych przez rozpatrywany proces.
  Tak wiec korzystajac ze wskaznika current ->semundo przechodzimy liste struktur uniewaznien zwiazanych z procesem odszukujac strukture dla zestawu o deskryptorze semid. Jezeli taka struktura nie istnieje to alokujemy na nia pamiec (return -ENOMEM jezeli nie udalo sie zaalokowac), na pole semid nowej struktury przypisujemy wartosc semid - parametru wywolania funkcji semop. Nastepnie wstawiamy ja na poczatek obu list; zwiazanej z procesem oraz zwiazanej z zestawem.
• Wywolanie try_semop () zwrocilo 0:
  
• Wywolaj funkcje wewnetrzna do_semop () ktora bezposrednio wykona wszystkie operacje na semaforach zestawu.
• Wywolaj funkcje wewnetrzna update_queue () ktora sprawdzi czy w wyniku ewwentualnych zmian wartosci semaforow w zestawie pewne zawieszone wczesniejsze wywolania semop nie moga zostac zakonczone.
• Return 0. Wczesniejsze implementacje zwracaly wartosc semafora na ktorym wykonano ostatnia z wyspecyfikowanych operacji. Wiazalo sie to z pogwalceniem praw dostepu, gdyz prawa czytania nie musialy byc sprawdzone. KONIEC.
• Wywolanie try_semop () zwrocilo 1:
  Trzeba wstrzymac proces wywolujacy, gdyz nie mozna wykonac wszystkich wyspecyfikowanych operacji w sposob niepodzielny.
• Tworzymy statycznie (przez deklaracje zmiennej queue ) element kolejki pending (struct sem_queue). Kolejka pending sluzy do przechowywania operacji semop wiszacych na danym zestawie, tj. oczekujacych na odpowiednie wartosci semaforow skladowych zestawu. W naglowku zestawu jest wskaznik na pierwszy element tej kolejki (sem_pending) oraz ostatni (sem_pending_last). Kazdy element kolejki ma wskaznik na nastepnika oraz wskaznik na wskaznik do siebie (rys 1).
• Zapisujemy w nim potrzebne informacje: sops - tablica operacji, nsops - liczba operacji, sma - wskaznik do naglowka zestawu, undo - wskaznik do wlasciwej struktury uniewaznien (NULL jezeli nie jest potrzebna), pid - pid aktualnego procesu i wstawiamy do kolejki.
• Wskazujemy na niego wskaznikiem current ->semsleeping z naglowka procesu.
• Zasypiamy wywolujac funkcje wewnetrzna interruptible_sleep_on (&queue->sleeper). Jako parametr podalismy adres pola sleeper utworzonego elementu kolejki pending. Funkcja usypiajaca prawdopodobnie przypisuje na to pole wskaznik do naglowka procesu w kolejce spiacych procesow. Nie mozna tego bylo zrobic wczesniej, poniewaz to dopiero funkcja usypiajaca wstawia proces do kolejki spiacych procesow.
  Proces oczekuje uspiony na taka zmiane wartosci semaforow zestawu, aby mozna bylo wykonac wszystkie operacje z tablicy sops. Jezeli taka zmiana nastapi byc moze zostanie obudzony przez funkcje wewnetrzna update_queue ()
• Proces moze zostac obudzony takze z innego powodu np. przez sygnal. Dlatego po obudzeniu sprawdzamy czy struktura queue zostala usunieta z kolejki pending (pole prev w takim wypadku wskazuje na NULL - rys 3 ). Jezeli tak to znaczy, ze wystapil blad zwiazany z proba wykonania operacji na ktoryms z semaforow zestawu lub tez wszystkie operacje zostaly wykonane pomyslnie . Kod ewentualnego bledu zostal zapisany w polu status struktury queue (inicjalnie 0). Wartosc tego pola zwracamy jako powrot z wywoplania semop. KONIEC.
• Jezeli struktura queue nie zostala usunieta z kolejki pending, to znaczy, ze przyczyna obudzenia procesu byl sygnal. W takim wypadku usuwamy queue z kolejki i zakanczamy semop z kodem bledu -EINTR.

Try_semop ()

int try_semop (struct semid_ds *sma, struct sembuf *sops, int nsops)

Powrot: 1-trzeba czekac, 0- mozna wykonac,<0 - kod bledu.

• Zmienna pomocnicza wynik = 0.
• Dla kolejnych operacji z tablicy sops, do wystapienia pierwszego przypisania na zmienna wynik wykonujemy:
• Sprawdzamy czy wartosc semafora nie przekroczy SEMVMX (wynik = -ERANGE jezeli przekroczy).
• Jezeli operacja jest czekaniem na wartosc semafora = 0 i aktualna wartosc semafora jest rozna od 0, to jezeli jest ustawiona flaga IPC_NOWAIT to wynik = -EAGAIN, w p. przypadku wynik = 1).
• Wykonujemy operacje na semaforze, jezeli wartosc semafora spadla ponizej 0, to jezeli jest ustawiona flaga IPC_NOWAIT to wynik = -EAGAIN, w p. razie wynik = 1.
• Teraz wszystkie wykonane operacje sa cofane !
• Funkcja try_semop zwraca wartosc przypisana na zmienna wynik.

Do_semop ()

int do_semop (struct semid_ds *sma, struct sembuf *sops, int nsops, struct sem_undo *un, int pid)

Powrot: zawsze 0.

• Kolejno wykonywane sa operacje z tablicy sops tj. do aktualnej wartosci semafora o odpowiednim numerze w zestawie dodawana jest wartosc operacji. Ale przedtem jeszcze raz sprawdzamy czy operacje mozna wykonac! Przy czym ewentualne bledy nie sa obslugiwane a jedynie komunikowane za pomoca funkcji printk ("do_semop: race\n"). Wystapienie pierwszego bledu powoduje zalamanie sie funkcji do_semop, ale zwracane jest jakby nigdy nic sie nie stalo 0 ! To chyba troche za malo jak na sytuacje w ktorej system zachowuje sie niedeterministycznie.
  Jezeli operacji towarzyszyla flaga SEM_UNDO to w strukturze uniewaznien un od odpowiedniego pola tablicy semadj odejmujemy wartosc operacji.
  Modyfikujemy pid ostatniego procesu ktory wykonal operacje na semaforze (pole sempid struktury struct sem w tablicy semaforow - rys 1 )
• W naglowku zestawu modyfikujemy czas ostatniej operacji na tym zestawie (na pole sem_otime przypisujemy current_time).

Update queue ()

void update_queue (struct semid_ds * sma)

• Przechodz kolejke operacji semop wstrzymanych na zestawie o naglowku (sma->pending) tak dlugo jak znajdujesz operacje mogace sie natychmiast wykonac (dla kazdego elementu kolejki wywolaj (try_semop()) .
• Jezeli istnieja operacje mogace sie wykonac to je wykonaj (do_semop() )
• Usun z kolejki pending struktury opisujace te operacje ( remove_from_queue (sma,q) )
• Obudz procesy ktore czekaly na zakonczenie tych operacji (wake_up(&q->sleeper))
• Jezeli try_semop zwrocilo blad, to jest on przypisywany na pole q->status i proces takze zostaje obudzony .

Wnioski koncowe

• Jedno wywolanie semop moze zawierac kilka operacji na tym samym semaforze zestawu. Istotna jest wtedy kolejnosc tych operacji w tablicy tsops.
• Kolejka semop-ow wstrzymanych (pending) jest przegladana element po elemencie. Pierwsza znaleziona tablica mogaca sie wykonac jest wykonywana. Tablica o zbyt wyrafinowanych operacjach moze zostac zaglodzona. Semafory sa wiec niezywotne.
• Nie ma zadnego mechanizmu ochrony przed blokada, ani jej wykrywania na poziomie roznych zestawow semaforow.

int sys_semctl (int id. zbioru, int numer_semafora, int komenda, union semun bufor_wywolania)

Komenda:

• IPC_INFO - Informacje globalne (struct seminfo).
• GETVAL - Pobranie wartosc semafora z zbioru.
• SETVAL - Ustawienie wartosci jednego semafora w zbiorze.
• SETALL - Usawienie wartosci calego zbioru semaforow.
• GETALL - Pobranie wartosci calego zbioru semaforow.
• IPC_SET - Zmiana praw dostepu . Funkcja dostepna tylko dla administratora, i wlasciciela zbioru semaforow.
• IPC_RMID -Usuniecie zbioru semaforow.
• Sprawdz prawa dostepu.
• Pobierz naglowek zestawu na zmienna .
• Zamarkuj miejsce w tablicy na wolne( IPC_UNUSED ).
• Przejdz liste uniewaznien ( UNDO ) zwiazana z zestawem i oznacz struktury do usuniecia (un ->semid = -1)
• Przejdz kolejke uspionych procesow (sem_pending) i dla kazdego procesu wykonaj:
• Ustaw status=EIDRM (semafor zostal usuniety).
• Obudzac proces ( wake_up ).
• Zwolnij zarezerwowana pamiec na zbior semaforow.

sem_exit ();

Funkcja wykonywana jest przez funkcje exit() przed zakonczeniem dzialania procesu.

• Jezeli proces jest wstrzymany przez operacje semop() to usun go z kolejki procesow wstrzymanych .
• Jezeli proces posiadal struktury uniewaznien to dla kazdego elementu kolejki wykonaj:
• Znajdz odpowiedni zestaw semaforow (o ile istnieje)
• Wykonaj uniewaznienia.
• Wywolaj update_queue() dla danego zbioru semaforow, gdyz ktos mogl czekac na podniesienie wartosci semafora.
• Usun strukture uniewaznien z obu list(procesu i zbioru semaforow).

• Pliki zrodlowe :
• sem.h
• sem.c
• Literatura :
• M. Bach , "Budowa systemu operacyjnego Unix", WNT, 1995.
• W. Richard Stevens, "Programowanie zastosowan sieciowych w systemie Unix", WNT, 1995.