Krystian Nowak

Kajetan Rogalski

Informatyka, grupa I-3

Zadanie:

Lotniskowiec z kilkoma pasami startowymi.

Na lotniskowcu znajduje się m pasów startowych, z których korzystają zarówno samoloty startujące jak i lądujące. Pas może być używany tylko w trybie wyłącznym. Każdy samolot funkcjonuje w następującym cyklu: postój, start, lot, lądowanie i znowu postój. W celu wystartowania lub wylądowania samolot musi mieć pewność, że jeden pas jest wolny (nieważne który). Napisać program dla procesu - samolotu, przy zachowaniu priorytetu dla samolotów lądujących wówczas, gdy w powietrzu jest więcej niż k samolotów.

Sposób rozwiązania:

Treść zadania wskazuje, że będziemy mieli do czynienia z wieloma procesami. Do realizacji zadania zdecydowano się wykorzystać dwa narzędzia komunikacji międzyprocesowej - kolejki komunikatów i semafory. Wydzielono jeden osobny proces, który będzie inicjował struktury danych związane z kolejkami i semaforami. Ów proces ustali na początku jaka jest liczba pasów startowych i granica powyżej której rozpatruje się priorytet samolotów lądujących. Proces ten dzieli się (po wykonaniu inicjalizacji) na trzy procesy:

• moduł zajmowania pasa startowego

• moduł zwalniania pasa startowego

• moduł wyświetlania stanu lotniskowca

Na załączonym schemacie (ostatnia kartka) można zauważyć, że z dwoma pierwszymi modułami są skojarzone odpowiednie kolejki komunikatów. Założono bowiem, iż procesy poszczególnych samolotów będą uruchamiane jako osobne programy (z innych konsol). Procesy te po wykonaniu szeregu operacji inicjacyjnych (m.in. przydział unikatowego numeru samolotu plane_id i zwiększeniu licznika samolotów SEM_HOWMANY - wykorzystano tu semafor jako strukturę danych dostępną dla wielu procesów na raz - inkrementację jej wartości zabezpiecza semafor SEM_INIT) wchodzą w nieskończoną pętlę wykonując operacje związane ze startem, lotem, lądowaniem i postojem.

Kolejka ALLOC QUEUE została stworzona dla samolotów wysyłających do lotniskowca żądanie startu lub lądowania. Typ komunikatu jest wykorzystywany jako znacznik priorytetu - mianowicie:

• dla samolotów lądujących jest to RQ_LAND o wartości 1

• dla samolotów startujących RQ_START o wartości 2

Wykorzystując (w module zajmowania) funkcję msgrcv z ujemnym typem komunikatu możemy odczytywać z niej wiadomości uszeregowane nie tylko ze względu na czas przybycia, ale głównie na typ (najpierw RQ_LAND, później RQ_START). Oczywiście należy tam sprawdzać wartość SEM_INAIR (liczba samolotów w powietrzu) i porównywać ze stałą k. W zależności od tego należy wybrać sposób odczytywania - albo klasyczne FIFO (watrość msg_id równa 0) lub wyżej opisaną wersję z priorytetami.

Należy zaznaczyć, iż w komunikacie jako dane jest przekazywany unikalny identyfikator samolotu (plane_id - powstaje od w czasie inicjalizacji działania samolotu)

Również sam moduł zajmowania działa w pętli nieskończonej. Gdy odbierze żądanie przydziału pasa wykonuje operację P(SEM_LINES) czyli usiłuje zająć pas. Gdy mu się to uda przekazuje komunikat do samolotu (kolejką ANSWER QUEUE), iż może on zacząć lądowanie. Jako identyfikator komunikatu wysyła plane_id danego samolotu, aby dany samolot mógł „przefiltrować” inne komunikaty i odebrał tylko te skierowane do siebie. Samolot po przyjęciu wiadomości, a następnie po wylądowaniu wysyła komunikat modułowi zwalniania (przez kolejkę FREE QUEUE), że nie potrzebuje on już dłużej pasa startowego i może on zostać zwolniony. Samolot już nie interesuje się, czy pas został zwolniony czy nie - po prostu wchodzi w stan „postoju”. To moduł zwalniania po odebraniu komunikatu od samolotu zwalnia pas startowy wykonując operację V(SEM_LINES).

Każdy samolot odpowiednio zwiększa lub zmniejsza wartość semafora SEM_INAIR w zależności od tego czy startuje czy ląduje.

Samoloty mają możliwość dynamicznego odłączania się od reszty po przerwaniu programu samolotu - jest to możliwie dzięki zastosowaniu flagi SEM_UNDO przy operacjach na semaforach. Zakończenie pracy programu - lotniskowca powoduje natomiast zakończenie pracy programów - samolotów.

Na temat implementacji:

Wszystkie ważniejsze i wspólne stałe, odwołania do bibliotek i funkcje zawarto w pliku nagłówkowym my.h. Zdefiniowano tu podstawowe operacje na semaforach - P i V oraz dodatkowo get, zwracającą aktualną wartość semafora. Klucze do semaforów i kolejek komunikatów zostały tu wpisane na stałe dla uniknięcia błędów przy ewentualnych zmianach.

Oto plik nagłówkowy z odpowiednimi komentarzami:

#include <errno.h> /* biblioteki */

#include <fcntl.h>

#include <unistd.h>

#include <stdio.h>

#include <signal.h>

#include <stdlib.h>

#include <sys/msg.h>

#include <sys/shm.h>

#include <sys/sem.h>

#include <sys/ipc.h>

/* stałe reprezentujące odpowiednie semafory */

#define SEM_LINES 0 /* liczba wolnych pasów startowych */

#define SEM_INAIR 1 /* liczba samolotów w powietrzu */

#define SEM_HOWMANY 2 /* ogólna liczba samolotów */

#define SEM_INIT 3 /* dodatkowy semafor zapewniający bezpieczną inicjalizację samolotu */

#define FALSE 0 /* stałe BOOLowskie */

#define TRUE 1

/* priorytety */

#define RQ_LAND 1 /* żądanie pozwolenia na lądowanie */

#define RQ_START 2 /* żądanie pozwolenia na start */

#define RQ_FREE 3 /* żądanie zwolnienia pasa */

/* klucze */

#define SEMKEY 911 /* klucze dla semaforów i kolejek komunikatów */

#define ALLKEY 997

#define ANSKEY 998

#define FREKEY 999

struct sembuf sembuf1; /* struktura dla operacji semaforowych */

struct queue_entry /* format wiadomości przekazywanej w kolejce */

{

long mtype;

int plane_id;

} entry;

extern int errno; /* dodatkowa zmienna do analizy ewentualnych błędów */

int sem_id; /* globalny identyfikator dla semaforów */

void blady(int blad) /* procedura obsługi błędów - wyświetlanie */

{

printf("errno is %d and means ",blad);

switch(blad)

{

case EACCES: printf("EACCES error !\n");break;

case EEXIST: printf("EEXIST error !\n");break;

case EIDRM : printf("EIDRM error !\n");break;

case ENOENT: printf("ENOENT error !\n");break;

case ENOMEM: printf("ENOMEM error !\n");break;

case ENOSPC: printf("ENOSPC error !\n");break;

}

}

void oper_P(int sem) /* operacja opuszczenia semafora sem */

{

sembuf1.sem_num=sem;

sembuf1.sem_op=-1; /* sem-- */

sembuf1.sem_flg=SEM_UNDO;

semop(sem_id,&sembuf1,1);

}

void oper_V(int sem) /* operacja podniesienia semafora sem */

{

sembuf1.sem_num=sem;

sembuf1.sem_op=1; /* sem++ */

sembuf1.sem_flg=SEM_UNDO;

semop(sem_id,&sembuf1,1);

}

int oper_Get(int sem) /* operacja uzyskania wartości semafora sem */

{

return semctl(sem_id,sem,GETVAL,0);

}

Poniżej znajduje się plik lotnisko.c

#include "my.h"

union semun semun1; /* unia do operacji inicjalizacyjnych na semaforach */

unsigned short semarray[4];

/* tablica wartości wpisywanych jako początkowe dla semaforów */

int allocq_id; /* identyfikator kolejki ALLOC */

int answerq_id; /* identyfikator kolejki ANSWER */

int freeq_id; /* identyfikator kolejki FREE */

int plane_id; /* unikalny identyfikator samolotu */

int CONST_M; /* liczba pasow startowych */

int CONST_K; /* ograniczenie nakladane na ilosc samolotow w powietrzu */

void tworz_sem(void)

{ /* tworzenie nowego zestawu semaforów */

if((sem_id=semget(SEMKEY,4,0666|IPC_CREAT|IPC_EXCL))==-1)

{

printf("sem_id == -1\n");

blady(errno);

exit(0);

}

semarray[SEM_LINES]=CONST_M; /* inicjalizacja wartości semaforów */

semarray[SEM_INAIR]=0;

semarray[SEM_HOWMANY]=0;

semarray[SEM_INIT]=1;

semun1.array=semarray;

if(semctl(sem_id,0,SETALL,semun1)==-1) /*wpisanie wartości startowych*/

{

printf("semctl error -1\n");

blady(errno);

exit(0);

}

}

void CTRL_C()

/* procedura obsługi sygnału SIGINT - usuwa semafory i kolejki */

{

semctl(sem_id,0,IPC_RMID,0);

msgctl(allocq_id,IPC_RMID,0);

msgctl(answerq_id,IPC_RMID,0);

msgctl(freeq_id,IPC_RMID,0);

printf("Koncze poniewaz nacisnieto CTRL-C\n");

exit(0);

}

int main(int argc, char **argv)

{

if(argc != 3)

{

printf("wlasciwe uzycie\n %s liczba_pasow ograniczenie\n",argv[0]);

exit(1);

}

CONST_M=atoi(argv[1]);/* pobranie wartości z linii poleceń dla K i M*/

CONST_K=atoi(argv[2]);

signal(SIGINT,CTRL_C); /* przejęcie obsługi sygnału */

tworz_sem(); /* utworzenie semaforów */

if(fork()==0)

{

/* moduł zajmowania */ /* utworzenie kolejek ALLOC i ASWER */

if((allocq_id=msgget(ALLKEY,0666|IPC_CREAT|IPC_EXCL))==-1) exit(0);

if((answerq_id=msgget(ANSKEY,0666|IPC_CREAT|IPC_EXCL))==-1) exit(0);

while(TRUE)

{

if(oper_Get(SEM_INAIR)>CONST_K)

/* priorytetowo */

msgrcv(allocq_id,&entry,sizeof(plane_id),(-1)*RQ_START,0);

else

/* bez priorytetów */

msgrcv(allocq_id,&entry,sizeof(plane_id),0,0);

oper_P(SEM_LINES); /* zajęcie pasa */

plane_id=entry.plane_id;

entry.mtype=plane_id;

/* wysłanie potwierdzenia do samolotu plane_id */

msgsnd(answerq_id,&entry,sizeof(plane_id),IPC_NOWAIT);

}

}

if(fork()==0)

{

/* moduł zwalniania */

/* utworzenie kolejki FREE */

if((freeq_id=msgget(FREKEY,0666|IPC_CREAT|IPC_EXCL))==-1) exit(0);

while(TRUE)

{

/* pobieranie żądań zwolnienia pasa... */

msgrcv(freeq_id,&entry,sizeof(plane_id),RQ_FREE,0);

oper_V(SEM_LINES); /* ...i jego zwalnianie */

}

}

while(TRUE)

{

/* moduł wyswietlania */

printf("\n");

printf("Wolnych jest %d pasow startowych\n",oper_Get(SEM_LINES));

printf("W powietrzu jest %d samolotow\n",oper_Get(SEM_INAIR));

printf("Razem jest %d samolotow\n",oper_Get(SEM_HOWMANY));

sleep(1);

}

}

Plik samolot.c

#include "my.h"

int plane_id;

int allocq_id;

int freeq_id;

int answerq_id;

void przerwa(void) /* pomocnicza procedura wyświetlająca numer samolotu */

{

printf("Tu %d ",plane_id);

}

int main(void)

{

if((sem_id=semget(SEMKEY,3,0666))==-1) /* tworzenie semafora */

{

printf("sem_id==-1\n");

blady(errno);

exit(0);

}

if((allocq_id=msgget(ALLKEY,0222))==-1) /* i odpowiednich kolejek */

{

printf("allocq_id==-1\n");

blady(errno);

exit(0);

}

if((freeq_id=msgget(FREKEY,0222))==-1)

{

printf("freeq_id==-1\n");

blady(errno);

exit(0);

}

if((answerq_id=msgget(ANSKEY,0444))==-1)

{

printf("answerq_id==-1\n");

blady(errno);

exit(0);

}

oper_P(SEM_INIT);

oper_V(SEM_HOWMANY); /*zwiększenie liczby samolotów i jednoczesne*/

plane_id= oper_Get(SEM_HOWMANY); /* ustalenie plane_id */

oper_V(SEM_INIT);

/*zabezpieczone SEM_INIT aby kilka samolotów nie miały tego samego plane_id */

while(TRUE)

{

/* główna pętla samolotu */

/* start */

entry.mtype=RQ_START;

entry.plane_id=plane_id;

/* żądanie przydziału pasa starowego do wystartowania */

msgsnd(allocq_id,&entry,sizeof(plane_id),IPC_NOWAIT);

if((msgrcv(answerq_id,&entry,sizeof(plane_id),plane_id,0))==-1)

{ /* jeśli kolejka zlikwidowana to kończymy */

printf("Konczymy...\n\n");

exit(0);

}

przerwa();printf(" startuje\n");

sleep(1);/* startuje */

oper_V(SEM_INAIR); /* zwiększenie liczby samolotów w powietrzu */

entry.mtype=RQ_FREE;

entry.plane_id=plane_id; /* i żądanie zwolnienia pasa startowego */

msgsnd(freeq_id,&entry,sizeof(plane_id),IPC_NOWAIT);

przerwa();printf(" leci\n");

sleep(2); /* leci */

/* lot */

entry.mtype=RQ_LAND;

entry.plane_id=plane_id;

/* żądanie przydziału pasa starowego do wylądowania */

msgsnd(allocq_id,&entry,sizeof(plane_id),IPC_NOWAIT);

msgrcv(answerq_id,&entry,sizeof(plane_id),plane_id,0);

/* po udzieleniu pozwolenia na lądowanie zmniejszenie liczby samolotów w powietrzu */

oper_P(SEM_INAIR);

przerwa();printf(" laduje\n");

sleep(1); /* laduje */

entry.mtype=RQ_FREE;

entry.plane_id=plane_id; /* żądanie zwolnienia pasa startowego */

msgsnd(freeq_id,&entry,sizeof(plane_id),IPC_NOWAIT);

przerwa();printf(" stoi\n");

sleep(2); /* stoi w miejscu */

}

}

Rozważania na temat problemów zakleszczenia i zagłodzenia.

W powyszym zadaniu problem zakleszczenia został wyeliminowany, ponieważ zasób jakim są lotniska są rozdzielane „centralnie” - przez procesy zajmowania i zwalniania. Nie występuje tu sytuacja, w której w jednej chwili proces posiada jednocześnie pas startowy i domaga się innego pasa startowego - jest to niemożliwe. Także kolejki komunikatów nie mają możliwości zakleszczenia się, gdyż np. samolot po wysłaniu żądania przydzielenia pasa startowego czeka jedynie na swoją kolej, prędzej czy później dostanie on wiadomość o przydzieleniu mu pasa. Tu pojawia się inny problem - zagłodzenia. Jednak samoloty wysyłają wiadomości do kolejek FIFO. Nawet jeśli aktualnie przez moduł zajmowania pobierane są żądania samolotów lądujących (wykorzystując priorytet) to i tak ilość samolotów będących w powietrzu po pewnym czasie zmniejszy się i oczekujący samolot na start w końcu zostanie obsłużony (na pewno żaden inny nie „przeskoczy” go w tej kolejce). Owszem, widać tutaj iż przy dużej liczbie samolotów w powietrzu dużo czasu minie zanim samolot chcący startować będzie miał tą możliwość, ale takie są założenia programu i wcale nie oznacza to zagłodzenia lecz tylko dość długie czekanie w specyficznym przypadku.

---