Blog literacki, portal erotyczny - seks i humor nie z tej ziemi
Do spisu tresci tematu 3
3.2.4 Zestawy semaforow
Spis tresci
Ogolne cechy
Struktury danych
Funkcja semget ()
Funkcja semop ()
Funkcja semctl ()
Funkcja wewnetrza sem_exit ()
Bibliografia
Spis rysunkow
Najwazniejsze struktury
Struktury uniewaznien
Usuwanie z kolejki operacji wstrzymanych
Naglowek zestawu semaforow
Ogolne cechy
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.
Struktury danych
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 */
Funkcja semget
int sys_semget
(key_t klucz, int ilosc_semaforow,
int flagi)
Sprawdz poprawnosc danych.
W zaleznosci od tego czy bedzie twozony 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.
Funkcja semop ().
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.
Funkcja semctl
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.
Smierc procesu
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).
Bibliografia
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.
Autorzy: Dionizy Borun i Piotr Fetras