Kolejki FIFO (lacza nazwane) sluza do komunikacji miedzy procesami opierajacej sie na zasadzie kolejki prostej. Kolejki FIFO, w odroznienu od laczy nienazwanych, umozliwiaja wymiane informacji pomiedzy procesami niespokrewnionymi ze soba. Sa one w budowie i obsludze podobne do systemu plikow. Dostep do nich odbywa sie poprzez funkcje systemowe obslugi plikow.
Kolejki FIFO nie dostarczaja zadnych mechanizmow, ktore umozliwialyby wysylanie komunikatow przeznaczonych dla konkretnych procesow tak jak jest to w przypadku kolejek komunikatow.
Implementacja kolejek FIFO w duzym stopniu korzysta ze stuktur danych dostarczonych przez system plikow.
Kazda kolejki FIFO tak jak plik posiada i-wezel. I-wezel ma w swoich strukturach zapamietane, ze zwiazana jest z nim kolejka FIFO. Posiada takze wskaznik do struktury pipe_inode_info postaci:
struct pipe_inode_info
{
struct wait_queue * wait; /*kolejka
procesow czekajacych na pisanie, czytanie lub procesow bedacych w trakcie
otwierania lacza i oczekujacych na proces po drugiej stronie lacza*/
char * base;/*wskaznik do bufora z
danymi*/
unsigned int
start;/*poczatek danych w buforze*/
unsigned int
len;/*ilosc danych*/
unsigned int
lock;/*zmienna sluzaca do synchronizacji dostepu do stuktur przechowujacych
dane. Rozna od zera oznacza, ze istnieja procesy, ktore pisza lub czytaja
z lacza*/
unsigned int
rd_openers;/*ilosc procesow bedacych w trakcie otwierania lacza
do pisania*/
unsigned int
wr_openers;/*ilosc procesow bedacych w trakcie otwierania lacza
do czytania*/
unsigned int
readers;/*ilosc procesow czytajacych z lacza*/
unsigned int
writers;/*ilosc procesow piszacych do lacza*/
};
Dane do lacza zapisywane sa cyklicznie. Informacja o tym, gdzie rozpocznie sie kolejna operacja czytania lub pisania jest pamietan w i_wezle poprzez stukture pipe_inode_info na zmiennych start i len. Jest to zasadnicza roznica pomiedzy i_wezlem zwiazanym z kolejka FIFO i i_wezlem przeznaczonym dla zwyklego pliku., gdzie informacja ta jest zapisana w tablicy plikow. Gdyby tak bylo w przypadku kolejek FIFO komunikaty bylyby odczytywane i zapisywane w dowolnej kolejnosci, poniewaz kazdy proces mialby inne informacje o poczatku i koncu danych.
W pliku include/linux/limits.h zdefiniowana jest wielkosc bufora przechowujacego dane. Jest to jednoczesnie maksymalny rozmiar komunikatu, ktorego umieszczenie w kolejce bedzie wykonane poprzez tzw. niepodzielna operacje:
#define PIPE_BUF 4096
W i-wezle zwiazanym z kolejka FIFO nie ma wskaznikow na bloki posrednie
i bezposrednie.
Przesylane dane przetrzymywane sa w pamieci operacyjnej wskazywanej przez
pole base ze struktury pipe_inode_info. Rozni sie to opisu kolejek FIFO podanego przez Maurice
J. Bacha w ksiazce "Budowa systemu operacyjnego UNIX ", ktory mowi, ze w kolejkach
FIFO do przechowywania danych wykorzystuje sie bloki bezposrednie.
Istnieje piec funkcji systemowych do obslugi kolejek FIFO:
-mknod - tworzy nowe lacza
-open - otwiera lacze
-write - zapisuje dane do lacza
-read - czyta dane z lacza
-close - zamyka deskryptor zwiazany z laczem
-unlink - zamyka lacze
Przy opisie bledow jakie moga zwracac funkcje bede podawal tylko te bledy, ktore sa bezposrednio zwiazane z laczami.
Funkcja ta sluzy do utworzenia nowej kolejki FIFO.
DEFINICJA: int mknod(nazwa_lacza, prawa_dostepu | S_IFIFO, 0)
WYNIK: 0 w przypadku powodzenia operacji,
-1, gdy blad: errno = EEXIST (kolejka o podanym kluczu istnieje,
wiec niemozliwe jest jej utworzenie)
Pierwszym argumentem funkcji jest nazwa powstajacego lacza. Drugi argument okresla prawa dostepu do lacza. Trzeci argument oznacza pierwszy i drugorzedny numer urzadzenia dla plikow specjalnych. W przypadku kolejek FIFO nie ma on znaczenia.
Implementacja funkcji:
{
sprawdz prawa dostepu,sprawdz czy taki plik istnieje; jezeli tak to zwroc
blad EEXIST,
przydziel nowy i-wezel, wywolaj funkcje fifo_init, ktora inicjuje strukture
pipe_inode_info.
Ta czesc implementacji nalezy do systemu plikow. Dalsza czesc algorytmu
wykonana jest przez funkcje fifo_init.
Funkcja fifo_init:
okresl operacje dopuszczalne na i-wezle (na razie jedyna dopuszczalna
operacja jest open)
inode->i_op = &fifo_inode_operations;
zaznacz, ze i-wezel jest laczem FIFO
inode->i_pipe = 1;
zaznacz, ze nikt nie czyta ani nie pisze z lacza
PIPE_LOCK(*inode)= 0;
Na razie nie przydzielaj pamieci na lacze
PIPE_BASE(*inode)= NULL;
ustal poczatek i rozmiar bufora na 0
PIPE_START(*inode)= PIPE_LEN(*inode)= 0;
zaznacz, ze nikt nie jest w trakcie otwierania lub zamykania lacza
PIPE_RD_OPENERS(*inode)= PIPE_WR_OPENERS(*inode)= 0;
PIPE_WAIT(*inode)= NULL;
zaznacz, ze nie ma czytalnikow ani pisarzy
PIPE_READERS(*inode)= PIPE_WRITERS(*inode)= 0;
}
W tym momencie nie jest jeszcze przydzielana pamiec na bufor wskazywany przez pole base.
Bedzie ona przydzielona przy piewszym wywolaniu funkcji open. Funkcja fifo_init
inicjuje takze pole i_op nowopowstalego i-wezla. Okresla ono jakie operacje mozna wykonywac na i-wezle.
W tym momencie dopuszczalna jest tylko operacja open.
-otwiera lacze.
DEFINICJA: int open(char* nazwa_lacza, int flagi)
WYNIK: 0 w przypadku sukcesu
-1, gdy blad: errno = ENXIO - otwieranie lacza do pisania, gdy nie ma procesow czytajacych
ENOMEM - brakuje pamieci w jadrze
EINTR - w czasie wykonania funkcji proces otrzymal sygnal
Pierwszym argumentem funkcji jest nazwa lacza. Drugi argument okresla
sposob dostepu do lacza.
Argument flagi moze przyjmowac nastepujace wartosci:
-O_WRONLY - otwieranie lacza tylko do pisania
-O_RDONLY - otwieranie lacza tylko do czytania
-O_RDWR - otwieranie lacza do pisania i czytania
-O_NDELAY - okresla czy operacje, ktorych wykonanie nie moze byc natychmiast
wykonane maja byc blokowane. Flaga ustawiona - brak blokowania.
Implementacja:
{
sprawdz prawa dostepu, czy istnieje plik nazwa_lacza, przydziel nowy deskryptor -
ta czesc nalezy do systemu plikow. Dalsza czesc kodu to funkcja fifo_open.
switch( deskryptor otwierany do: ) {
case czytania:
okresl typ deskryptora (na razie sestaw operacji okreslony na i-wezle jest troche inny
od ostatecznego zestawu operacji przydzelanego tutaj. Jednak roznice miedzy nimi sa na
tyle subtelne, ze nie bede ich wyjasnial)
filp->f_op = &connecting_fifo_fops;
Jezeli nie ma zadnych czytelnikow, to obudz spiace procesy-moze sa w srod nich
czytelnicy, ktorzy zasneli w trakcie otwierania lacza
if (!PIPE_READERS(*inode)++)
wake_up_interruptible(&PIPE_WAIT(*inode));
if (open wykonywane z blokowaniem lub jest przynajmniej jeden pisarz) {
zwieksz licznik czytelnikow otwierajacych lacze
PIPE_RD_OPENERS(*inode)++;
while (nie ma czytelnikow) {
if (przyszedl sygnal) return EINTR;
interruptible_sleep_on(&PIPE_WAIT(*inode));spij w kolejce
}
jezeli po obudzeniu sa jacys czytelnicy, ktorzy zasneli w trakcie wykonywnia open
to ich obudz
if (!--PIPE_RD_OPENERS(*inode))
wake_up_interruptible(&PIPE_WAIT(*inode));
}
dopoki sa pisarze, ktorzy usneli w trakcie wykonywania open to poczekaj, az wszyscy
oni sie obudza i dojda do tego miejsca
while (PIPE_WR_OPENERS(*inode))
interruptible_sleep_on(&PIPE_WAIT(*inode));
Jezeli sa czytelnicy do nadaj teskryptorowi pliku pelne prawa czytania. Ta czesc kodu
zawsze wykonana dla open z opcja blokowania.
if (PIPE_WRITERS(*inode))
filp->f_op = &read_fifo_fops;
break;
case pisania:
if (jezeli open jest wykonywane z opcja bez czekania i nie ma czytelnkow)
return (ENXIO);
okresl funkcje dopuszczalne na deskryptorze
filp->f_op = &write_fifo_fops;
jezeli nie bylo do tej pory pisarzy obudz wszystkie spiace procesy. Spac moga zarowno
czytelnicy bedacy w trakcie otwierania lacza jak i czytelnicy probujacy czytac z lacza do
ktorego nikt nie pisze
if (!PIPE_WRITERS(*inode)++)
wake_up_interruptible(&PIPE_WAIT(*inode));
jezeli nie ma czytelnikow
if (!PIPE_READERS(*inode)) {
PIPE_WR_OPENERS(*inode)++; zwieksz ilosc pisarzy bedacych w trakcie otwierania lacza
while (!PIPE_READERS(*inode)) {
if (przyszedl sygnal) return (ERESTARTSYS);
interruptible_sleep_on(&PIPE_WAIT(*inode));
}
jezeli po obudzeniu sa jacys pisarze, ktorzy zaseli w trakcie wykonania open to
ich obudz
if (!--PIPE_WR_OPENERS(*inode))
wake_up_interruptible(&PIPE_WAIT(*inode));
}
jezeli sa czytelnicy, ktorzy zasneli w trakcie wykonania open to poczekaj, az
wszyscy oni sie obudza i dojda do tego miejsca w swoim kodzie
while (PIPE_RD_OPENERS(*inode))
interruptible_sleep_on(&PIPE_WAIT(*inode));
break;
case pisania i czytania:
okreskl funkcje dopuszczalne na deskryptorze
filp->f_op = &rdwr_fifo_fops;
jezeli wczesniej nie bylo czytelnikow to obudz wszystkich spiacych pisarzy
if (!PIPE_READERS(*inode)++)
wake_up_interruptible(&PIPE_WAIT(*inode));
obudz wszystkich pisarzy, ktorzy zasneli wykonujac funkcje open
while (PIPE_WR_OPENERS(*inode))
interruptible_sleep_on(&PIPE_WAIT(*inode));
jezeli wczesniej nie bylo pisarzy to obudz wszystkich spiacych czytelnikow
if (!PIPE_WRITERS(*inode)++)
wake_up_interruptible(&PIPE_WAIT(*inode));
obudz wszystkich czytelnikow, ktorzy zasneli wykonujac open
while (PIPE_RD_OPENERS(*inode))
interruptible_sleep_on(&PIPE_WAIT(*inode));
break;
default:
return EINVAL;jezeli deskryptor nie byl otwierany ani do pisania, ani to czytania,
ani do czytania i pisania to zwroc EINVAL
}
jezeli jest juz przeznaczona pamiec na bufor dla danych to wyjdz z funkcji, jezeli nie
topen jest wykonywane poraz pierwszy lub od czasu powstania lacza bylo ono uzywane a nastepnie
ilosc procesow uzywajacych lacza spadla do zera (w takim przypadku zwalniana jest pamiec
przeznaczona na bufora lacza). W obu przypadkach trzeba przydzielic pamiec.
if (PIPE_BASE(*inode))
return 0;
page = __get_free_page(GFP_KERNEL);
byc moze juz ktos przydzielil pamiec; jezeli tak to zwalniamy to co zaalokowalismy
if (PIPE_BASE(*inode)) {
free_page(page);
return 0;
}
if (!page) return ENOMEM;brakuje nam pamieci
trzeba jeszcze uaktualnic informacje o buforze. Byc moze lacze istnieje juz od dawna, jakies procesy je
urzywaly i potem je zamknely. Jezeli ilosc procesow uzywajacych lacza spadnie do zera to kasowana
jest zawartosc bufora, ale nie sa uaktualniane informacje o poczatku i dlugosci bufora. Trzeba to
zrobic teraz.
PIPE_LOCK(*inode) = 0;
PIPE_START(*inode) = PIPE_LEN(*inode) = 0;
PIPE_BASE(*inode) = (char *) page;
return 0;
}
Warto zwrocic uwage na niesymetryczne zachowanie sie funkcji open w
przypadku, gdy jest ona wywolywana z flago O_NDELAY.
Jezeli jest wywolywana do czytania i nie ma procesow piszacych do lacza,
to powrot z niej nastepuje bez kodu bledu.
Jezeli jest wywolywana do pisania i nie ma procesow czytajacych, to powrot
nastepuje z bledem ENXIO.
- sluzy do zapisywnia danych do lacza.
DEFINICJA: int write(int fd, char* buf, int count)
WYNIK: liczba bajtow skopiowanych do lacza w przypadku sukcesu
-1, gdy blad: errno = EFAULT (zly adres buf)
EINTR (otrzymano sygnal podczas czekania)
EAGAIN (lacze otwarte z opcja bez czekania i nie ma miejsca
do zapisania danych.
EPIPE (nie ma procesu czytajacego z lacza. Proces piszacy otrzymuje
sygnal SIGPIPE. Jezeli go przechwytuje to errno = EPIPE.
Pierwszym argumentem jest numer deskryptora, ktory zwrocila funkcja open. Drugi argument to bufor z danymi do przeslania, a trzeci argument to rozmiar przesylanych danych.
Dzialanie funkcji write zalezy od rozmiaru danych jakie chcemy wpisac do lacza. Jezeli sa one mniejsze od rozmiaru lacza to wpisanie danych bedzie wykonane przez niepodzielna operacje, tzn beda zapisane w calosci. Jezeli natomiast rozmiar danych jest wiekszy od rozmiaru lacza to dane sa dzielone na mniejsze porcje, ktore sa umieszczane w laczu niezaleznie od siebie. Moze to spowodowac przemieszanie danych wpisywanych przez kilka procesow.
Dzialanie funkcji write zalezne takze od ustawienia flagi (z O_NDELAY czy bez) w funkcji open zwracajacej deskryptor fd.
| z O_NDELAY | bez O_NDELAY | |
| nie ma czytelnikow | sygnal SIG_PIPE | sygnal SIG_PIPE |
| wpisujemy mniej danych niz jest miejsca w laczu | liczba zapisanych bajtow = count | liczba zapisanych bajtow = count |
| wpisujemy wiecej danych niz jest miejsca w laczu | jezeli rozmiar danych jest mniejszy od calkowitego rozmiaru lacza to zwracany jest blad EAGAIN wpp zwracana jest ilosc zapisanych bajtow (jezeli jest niezerowa) albo EAGAIN | czeka na wolne miejsce |
Implementacja funkcji:
{
sprawdz prawa dostepu, znajdz i-wezel zwiazany z deskryptorem - tym zajmuje sie system plikow
if (nie ma czytelnikow){
wyslij sygnal SIGPIPE;
return EPIPE;
}
jezeli ilosc danych do wpisania jest mniejsza od rozmiaru lacza, to wpisanie danych ma
byc operacja niepodzielna
if (ilosc danych do wpisania <= PIPE_BUF)
free = count;
else
free = 1; rozmiar danych jest tak duzy, ze nie mozna ich wszystkich jednoczesnie
umiescic w buforze. Bedziemy umieszczac male kawalki, nawet rozmiaru
jednego bajta
while (ilosc danych do wpisania>0) {
while (ilosc wolnego miejsca w laczu < free) lub ktos pisze lub czyta z lacza) {
if (nie ma czytelnikow) {
wyslij sygnal SIGPIPE;
if (zadne dane nie sa zapisane) retrun EEPIPE;
if (jakies dane sa zapisane) return ilosc zapisanych danych. Ta sytuacja mozliwa
tylko w przypadku, gdy ilosc zapisywanych danych>rozmiar bufora
}
if (proces otrzymal sygnal)
if (zadne dane nie sa zapisane) return EINTR;
if (jakies dane sa zapisane) return ilosc zapisanych danych. Ta sytuacja mozliwa
tylko w przypadku, gdy ilosc zapisywanych danych>rozmiar bufora
if (pisanie ma byc wykonane bez blokowania) {
if (zadne dane nie sa zapisane) retrun EAGAIN;
if (jakies dane sa zapisane) return ilosc zapisanych danych. Ta sytuacja mozliwa
tylko w przypadku, gdy ilosc zapisywanych danych>rozmiar bufora
zasnij oczekujac na wolne miejse w buforze
}
PIPE_LOCK(*inode)++;zablokuj dostep do lacza
Zapisz do lacza tyle danych ile sie zmiesci.
Jezeli rozmiar danych wejsciowych <= rozmiarowi lacza to w tym momencie beda zapisane
wszyskie dane. Wpp zostanie zapisana tylko taka czesc danych jaka zmiesci sie w laczu i
bedziemy dalej krecic sie w tej petli.
PIPE_LOCK(*inode)--;oblokuj dostep do i-wezla
Obudz spiace procesy. W szczegolnosci moga tam byc czytelnicy, ktorzy cos odczytaja i
zwolnia miejsce
}
return ilosc zapisanych bajtow;
}
- sluzy do pobierania danych z lacza
DEFINICJA: int read(int fd, char* buf, int count)
WYNIK: 0 w przypadku sukcesu
-1, gdy blad: errno = EFAULT (zly adres buf)
EAGAIN - ustawiona flaga O_NDELAY i nie ma co czytac
EINTR - funkcja przerwana przez sygnal
Znaczenia argumentow sa taki jak w funkcji write, z ta roznica, ze buf oznacza bufor, do ktorego beda zapisywane dane otrzymane z lacza.
Dzialanie funkcji read zalezy od ustawienia flagi (z O_NDELAY czy bez) w funkcji open zwracajacej deskryptor fd.
| z O_NDELAY | bez O_NDELAY | |
| danych do odczytania jest mniej niz danych w laczu | odczytana liczba bajtow = count | odczytana liczba bajtow = count |
| puste lacze | sa pisarze - EAGAIN, nie ma ich - 0 | sa pisarze - czeka na dane, nie ma ich - 0 |
| danych do odczytania jest wiecej niz danych w laczu | odczytana liczba bajtow = ilosci danych w laczu | odczytana liczba bajtow = ilosc danych w laczu |
Implementacja funkcji
{
sprawdz prawa dostepu, znajdz i-wezel zwiazany z deskryptorem - tym zajmuje sie system plikow
if (czytanie bez mozliwosci blokowania) {
if (ktos czyta lub pisze do lacza)
return EAGAIN;
if (lacze jest puste)
if (sa pisarze)
return EAGAIN;
else nie ma pisarzy
return 0;
} else czytanie moze byc blokowane
while (puste lacze lub ktos pisze do lub czyta z lacza) {
if (puste lacze) {
if (nie ma pisarzy)
return 0;
}
if (przyszedl sygnal)
return EINTR;
interruptible_sleep_on(&PIPE_WAIT(*inode));zasnij do czasu, gdy lacze bedzie niepuste i
nikt nie bedzie z niego czytal ani pisal
}
PIPE_LOCK(*inode)++;zablokuj dostep do lacza
przeczytaj dane z lacza. Jezeli w laczu jest mniej danych niz potrzebujesz, przeczytaj tylko tyle i
sie jest
PIPE_LOCK(*inode)--;odblokuj dostep do lacza
wake_up_interruptible(&PIPE_WAIT(*inode));obudz spiace procesy - w szczegolnosci pisarzy
jezeli zostaly przeczytane jakies dane to je zwroc
wpp sprawdz czy sa pisarze. Jezeli sa to zwroc EAGAIN. Jezeli nie ma pisarzy to zwroc 0
}
Nalezy zauwazyc, ze funkcja read nie moze przeczytac wiecej danych niz rozmiar lacza. Dlatego tez, jezeli chcemy odczytac wiecej bajtow niz lacze moze pomiescic, funkcje read trzeba wywolac kilkakrotnie. To jednak moze powodowac, ze nie otrzymamy spojnych danych.
Z przedstawionej implentacji funkcji write i read widac, ze nie zapewniaja
one zywotnosci.
Zalozmy, ze mamy wielu wciaz dochodzacych pisarzy klasy A, ktorzy chca
zapisac dane wielkosci 1/4 rozmiaru bufora, jednego pisarza klasy B, ktory
chce zapisac dane wielkosci 1/2 rozmiaru bufora, jednego czytelnika, ktory
co pewien czas (tzn. na tyle rzadko, zeby funkcja write zdazyla sie w pelni
wykonac) pobiera dane wielkosci 1/4 rozmiaru lacza. Bufor na poczatku jest
pelny. Funkcje read i write powoduja zaglodzenie pisarza klasy B, poniewaz:
po odebraniu przez czytelnika danych zwalnia sie 1/4 bufora, budzeni sa
wszyscy pisarze, ale zapisuje tylko ten, ktoremu uda sie zmiescic swoje
dane, a wiec pisarz klasy A. Znow przychodzi czytelnik i tak w nieskonczonosc.
-zamyka deskryptor lacza
DEFINICJA: int close(int fd)
WYNIK: 0 gdy sukces
-1 gdy blad:
Jedynym parametrem jest deskryptor pliku
Podczas wykonania funkcji close() wykonywane sa te same funkcje co przy
zamykaniu zwyklego pliku, z ta roznica, ze zostaje zmniejszona ilosc czytelnkow
i pisarzy zgodnie z typem deskryptora i budzone sa wszystkie spiace procesy
czekajace na kolejce zwiazanej z laczem. Jak widac z implementacji funkcji
read, jezeli liczba pisarzy spadnie do zera i sa czytelnicy czekajacy na
dane, to wszyscy oni powroca z wywolania funkcji read bez przeczytania
danych.
Jezeli natomiast liczba czytelnikow spadnie do zera i sa pisarze czekajacy
na wolne miejsce w buforze to bedzie im wyslany sygnal SIGPIPE.
Jezeli liczba czytelnikow i pisarzy spadnie do zera tzn liczba dowiazan w i-wezle spadnie do zera, to zostaje wywolana taka procedura, jak w przypadku zwyklego pliku, ktora dodatkowo zwalnia pamiec wskazywana przez pole base struktury pipe_inode_info. Powoduje to utrate wszystkich danych znajdujacych sie w buforze.
-usuwa lacze nazwane
DEFINICJA: int unlink(char* nazwa_lacza)
WYNIK: 0 gdy sukces
-1 gdy blad
Usuwa lacze nazwane. Jezeli w czasie wywolania sa procesy, ktore z lacza korzystaja to zostaje usunieta tylko nazwa lacza z dysku, tak ze juz nowe procesy nie mogo z niego korzystac. Lacze zostanie usuniete, gdy wszystkie procesy korzystajace z niego zamkna deskryptory zwiazane z tym laczem.