Nowe posty

xx Dystrybucja pod HP Omen (6)
Wczoraj o 23:30:08
xx [Poradnik] Wyszukiwanie Sterowników (2)
Wczoraj o 21:08:23
lamp Problem z Linux Lite po instalacji (0)
Wczoraj o 19:50:30
xx Ile pingwinów? (1)
Wczoraj o 08:59:24
xx konfiguracja pale moon (0)
2024-03-24, 21:53:42
xx Plasma 6 w Neonie ssie trochę mniej ... (10)
2024-03-23, 02:38:11
xx problem z instalacja sterowników do karty sieciowej (3)
2024-03-18, 18:10:16
xx Plik abc.001 (1)
2024-03-17, 17:48:27
xx Zlecę dopracowanie programu w MatLab (0)
2024-03-13, 15:28:40
xx Linux Mint 21.3 XFCE brak dźwieku po paru minutach (karta muzyczna zintegrowana) (5)
2024-03-12, 23:07:01

Autor Wątek: [C] 5 filozofów  (Przeczytany 3997 razy)

vbv

  • Gość
[C] 5 filozofów
« dnia: 2017-01-18, 19:54:16 »
Witam mam zadanie napisać program 5 filozofów za pomocą semaforów korzystając z treści rozwiązania i nim musze wykonać je:
"W rozwiązaniu wykorzystano 5-el tablice binarnych semaforów sem[5]- każdy semafor jest związany z jednym widelcem i jest inicjowany wartością 1. pseudokod procedury każdego filozofa:
begin
repeat
     myslenie;
     wait(sem[name]);
     wait(sem[(name+1)mod 5]);
     jedzenie;
     signal(sem[name]);
     signal(sem[(name+1)mod 5]);
end

Czy moje rozwiazanie tego problemu jest poprawne? Prosiłbym o ewentualne wskazówki.
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/errno.h>
#include <fcntl.h>

#define N 5 //ilosc semaforow

int alokujSemafor(key_t klucz, int number, int flagi);
void inicjalizujSemafor(int semID, int number, int val);
int waitSemafor(int semID, int number, int flags);
void signalSemafor(int semID, int number);
int zwolnijSemafor(int semID, int number);
void myslenie(int);
void jedzenie(int);

int main()
{
key_t klucz;
int sem;
int i;

//tworzymy N=5 semeforow
sem=alokujSemafor(klucz,N,IPC_CREAT|IPC_EXCL|0666);
for(i=0;i<N;i++)
inicjalizujSemafor(sem,i,1);// inicjalizujemy jedynkami

printf("Semafory gotowe!\n");
fflush(stdout);

for(i=0;i<N;i++)
{
myslenie(i);
waitSemafor(sem,i,0);
waitSemafor(sem,(i+1)%5,0);
jedzenie(i);
signalSemafor(sem,i);
signalSemafor(sem,(i+1)%5);
}
printf("Wykonano poprawnie !\n");
zwolnijSemafor(sem,N);

}

void myslenie(int i)
{
printf("Filozof nr: %d mysli...\n",i+1);
sleep(1);
}

void jedzenie(int i)
{
printf("Filozof nr: %d je...\n",i+1);
sleep(1);
}

int alokujSemafor(key_t klucz, int number, int flagi)
{
   int semID;
   if ( (semID = semget(klucz, number, flagi)) == -1)
   {
      perror("Blad semget (alokujSemafor): ");
      exit(1);
   }
   return semID;
}

void inicjalizujSemafor(int semID, int number, int val)
{
   
   if ( semctl(semID, number, SETVAL, val) == -1 )
   {
      perror("Blad semctl (inicjalizujSemafor): ");
      exit(1);
   }
}

int waitSemafor(int semID, int number, int flags)
{
   int result;
   struct sembuf operacje[1];
   operacje[0].sem_num = number;
   operacje[0].sem_op = -1;
   operacje[0].sem_flg = 0 | flags;//SEM_UNDO;
   
   if ( semop(semID, operacje, 1) == -1 )
   {
      //perror("Blad semop (waitSemafor)");
      return -1;
   }
   
   return 1;
}

void signalSemafor(int semID, int number)
{
   struct sembuf operacje[1];
   operacje[0].sem_num = number;
   operacje[0].sem_op = 1;
   //operacje[0].sem_flg = SEM_UNDO;

   if (semop(semID, operacje, 1) == -1 )
      perror("Blad semop (postSemafor): ");

   return;
}
int zwolnijSemafor(int semID, int number)
{
   return semctl(semID, number, IPC_RMID, NULL);
}

Offline Paweł Kraszewski

  • Administrator
  • Guru
  • *****
  • Wiadomości: 3049
  • Lenistwo jest matką potrzeby = babcią wynalazku
    • Zobacz profil
Odp: [C] 5 filozofów
« Odpowiedź #1 dnia: 2017-01-19, 08:30:16 »
1. Problem filozofów ma w ogóle sens, jeżeli filozofowie są wątkami/procesami. Jak robisz to w chamskiej, jednowątkowej pętli, to tak jakbyś przed jadalnią postawił pana Gienia, który wpuszcza do jadalni jednego filozofa naraz. Z definicji w takiej sytuacji każdy filozof znajdzie swoje widelce od razu i żadne semafory nie są potrzebne.

2. Rozwiązanie z pseudokodu jest mocno naiwne, bo prawie natychmiast dojdzie do zakleszczenia (każdy filozof bierze lewy widelec i zawiesza się w nieskończoność na czekaniu na prawy - który jest wzięty jako lewy przez następnego sąsiada)

3. Z jasno napisanego "5-el tablice binarnych semaforów sem[5]" wynika, że raczej chodziło o zastosowanie zestawu funkcji sem_init/sem_destroy/sem_post/sem_wait i tablicy sem_t sem[5]...

4. W tego typu przykładach zakłada się, że "myślenie" i "jedzenie" trwają losowy czas. Często wystarczy rozkład jednostajny czasu "czynności" między t1 a t2: t = t1+rand()%(t2-t1) - jednak w przypadku modelowania systemów np. telekomunikacyjnych potrzeba użyć bardziej rzeczywistych rozkładów (Poissona, Erlanga, wykładnicze)

5. Podstawy programowania współbieżnego i rozproszonego, rozdział 6.9 (w każdym razie w moim wydaniu).
« Ostatnia zmiana: 2017-01-19, 09:20:08 wysłana przez Paweł Kraszewski »
Paweł Kraszewski
~Arch/Void/Gentoo/FreeBSD/OpenBSD/Specjalizowane customy

vbv

  • Gość
Odp: [C] 5 filozofów
« Odpowiedź #2 dnia: 2017-01-19, 22:21:48 »
A teraz jak?
// plik 5f.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/errno.h>
#include <unistd.h>
#include <sys/shm.h>

int alokujSemafor(key_t klucz, int number, int flagi)
{
   int semID;
   if ( (semID = semget(klucz, number, flagi)) == -1)
   {
      perror("Blad semget (alokujSemafor): ");
      exit(1);
   }
   return semID;
}

void inicjalizujSemafor(int semID, int number, int val)
{
   
   if ( semctl(semID, number, SETVAL, val) == -1 )
   {
      perror("Blad semctl (inicjalizujSemafor): ");
      exit(1);
   }
}

void myslenie(int i)
{
printf("Filozof nr: %d mysli...\n",i+1);
sleep(1);
}

void jedzenie(int i)
{
printf("Filozof nr: %d je...\n",i+1);
sleep(1);
}

int main(int argc,char* argv[])
{
key_t klucz_semafor,klucz_pamiec; //klucz do semaforow i pam. dzielonej
int N=5; //ile razy filozofowie wykonuja petle
int semID; //identyfikator zestawu semaforow
int ilosc_semaforow=5;  //liczba semaforow
int i;
int numer; //numer filozofa
int shmID; //identyfikator pamieci dzielonej
int *widelec; //tablica widelcow

if((klucz_semafor=ftok(".",'A'))==-1)
{
printf("Blad ftok (5f)\n");
exit(1);
}
//dostanie sie do zestawu semaforow
semID=alokujSemafor(klucz_semafor,ilosc_semaforow,IPC_CREAT|0666);
klucz_pamiec=ftok(".",'B');
//dostep do pamieci dzielonej
shmID=shmget(klucz_pamiec,5*sizeof(int),IPC_CREAT|0666);
if(shmID==-1)
{
printf("Blad shm(5f)\n");
exit(1);
}
fflush(stdout);
//przydzielenie pamieci dzielonej
widelec=(int*)shmat(shmID,0,0);
numer=atoi(argv[1]); //pobranie numeru filozofa
for(i=0;i<N;i++)
{
myslenie(i);
//podniesienie widelcow, ustawienie numeru filozofa
widelec[numer]=numer;
widelec[(numer+1)%5]=numer;
jedzenie(i);
//zwolnienie widelcow
widelec[numer]=-1;
widelec[(numer+1)%5]=-1;
printf("Filozof nr: %d konczy\n",numer);
}
}
//plik mainprog.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/errno.h>
#include <unistd.h>
#include <sys/shm.h>

int alokujSemafor(key_t klucz, int number, int flagi)
{
   int semID;
   if ( (semID = semget(klucz, number, flagi)) == -1)
   {
      perror("Blad semget (alokujSemafor): ");
      exit(1);
   }
   return semID;
}

int zwolnijSemafor(int semID, int number)
{
   return semctl(semID, number, IPC_RMID, NULL);
}

void inicjalizujSemafor(int semID, int number, int val)
{
   
   if ( semctl(semID, number, SETVAL, val) == -1 )
   {
      perror("Blad semctl (inicjalizujSemafor): ");
      exit(1);
   }
}

int main(int argc,char* argv[])
{
key_t klucz_semafor,klucz_pamiec; //klucz do semaforow i pam. dzielonej
int N=5; //ile razy filozofowie wykonuja petle
int semID; //identyfikator zestawu semaforow
int ilosc_semaforow=5;  //liczba semaforow
int i;
int numer; //numer filozofa
int shmID; //identyfikator pamieci dzielonej
char bufor[3];
int *widelec; //tablica widelcow

if((klucz_semafor=ftok(".",'A'))==-1)
{
printf("Blad ftok (mainprog)\n");
exit(1);
}
//tworzenie zestawu 5 semaforow
semID=alokujSemafor(klucz_semafor,N,IPC_CREAT|IPC_EXCL|0666);
for(i=0;i<N;i++)
inicjalizujSemafor(semID,i,1);  //inicjalizacja sem. z widelcami o wartosc 1
klucz_pamiec=ftok(".",'B'); //klucz do pam. dzielonej
//tworzenie pamieci dzielonej
shmID=shmget(klucz_pamiec,5*sizeof(int),IPC_CREAT|IPC_EXCL|0666);
if(shmID==-1)
{
printf("Blad shm(mainprog)\n");
exit(1);
}
fflush(stdout);
//przydzielenie pamieci dzielonej
widelec=(int*)shmat(shmID,NULL,0);
for(i=0;i<N;i++)
widelec[i]=-1;
//tworzenie procesow filozofow
for(i=0;i<N;i++)
switch(fork())
{
case -1:
perror("Blad fork(mainprog\n");
exit(2);
case 0:
sprintf(bufor,"%d",i); //przekazanie numeru
execl("./5f","5f",bufor,NULL);
}
for(i=0;i<N;i++)
wait(NULL); //czekanie na zakonczenie procesow filozofow
//zwolnienie zestawu semaforow
zwolnijSemafor(semID,N);
//zwolnienie pamieci dzielonej
shmctl(shmID,IPC_RMID,NULL);
printf("MAINPROG: Koniec!\n");

}

Offline Paweł Kraszewski

  • Administrator
  • Guru
  • *****
  • Wiadomości: 3049
  • Lenistwo jest matką potrzeby = babcią wynalazku
    • Zobacz profil
Odp: [C] 5 filozofów
« Odpowiedź #3 dnia: 2017-01-20, 07:03:03 »
Jest 27 razy gorzej, niż pierwotnie. Teraz masz procesy z pamięcią współdzieloną w ogóle bez jakiejkolwiek synchronizacji.  Jakoś magicznie znikły ci wait/signal...

O ile pierwotne rozwiązanie nie było współbieżne, to było formalnie poprawne (mimo naiwności algorytmu filozofa, przez ich skolejkowanie nie było możliwości zagłodzenia/blokady - ale to NIE był program o który chodziło wykładowcy), to teraz jest mega pi*dolnik.

Doprowadź kod do stanu, że generuje takie wydruki:
Przygotowanie semaforów
Uruchomienie wątków
Filozof 1 wchodzi do jadalni
Filozof 1 myśli
Filozof 2 wchodzi do jadalni
Filozof 2 myśli
Filozof 4 wchodzi do jadalni
Filozof 3 wchodzi do jadalni
Filozof 3 myśli
Czekanie na zakończenie wątków
Filozof 4 myśli
Filozof 5 wchodzi do jadalni
Filozof 5 myśli
Filozof 4 czeka na lewy widelec
Filozof 4 dostał lewy widelec
Filozof 4 czeka na prawy widelec
Filozof 4 dostał prawy widelec
Filozof 4 je
Filozof 1 czeka na lewy widelec
Filozof 1 dostał lewy widelec
Filozof 1 czeka na prawy widelec
Filozof 1 dostał prawy widelec
Filozof 1 je

[....]

Filozof 4 czeka na lewy widelec
Filozof 3 odkłada prawy widelec
Filozof 3 myśli
Filozof 2 dostał prawy widelec
Filozof 2 je
Filozof 4 dostał lewy widelec
Filozof 4 czeka na prawy widelec
Filozof 2 odkłada lewy widelec
Filozof 2 odkłada prawy widelec
Filozof 2 myśli
Filozof 3 czeka na lewy widelec
Filozof 3 dostał lewy widelec
Filozof 3 czeka na prawy widelec
Filozof 2 czeka na lewy widelec
Filozof 2 dostał lewy widelec
Filozof 2 czeka na prawy widelec
Filozof 1 umarł z głodu czekając na prawy widelec
Filozof 5 umarł z głodu czekając na prawy widelec
Filozof 4 umarł z głodu czekając na prawy widelec
Filozof 3 umarł z głodu czekając na prawy widelec
Filozof 2 umarł z głodu czekając na prawy widelec
Wszystkie wątki zakończone
Zniszczenie semaforów

albo
Przygotowanie semaforów
Uruchomienie wątków
Filozof 1 wchodzi do jadalni
Filozof 1 myśli
Filozof 2 wchodzi do jadalni
Filozof 2 myśli
Filozof 4 wchodzi do jadalni
Filozof 3 wchodzi do jadalni
Filozof 3 myśli
Czekanie na zakończenie wątków
Filozof 4 myśli
Filozof 5 wchodzi do jadalni
Filozof 5 myśli
Filozof 4 czeka na lewy widelec
Filozof 4 dostał lewy widelec
Filozof 4 czeka na prawy widelec
Filozof 4 dostał prawy widelec
Filozof 4 je
Filozof 1 czeka na lewy widelec
Filozof 1 dostał lewy widelec
Filozof 1 czeka na prawy widelec
Filozof 1 dostał prawy widelec
Filozof 1 je

[...]

Filozof 5 czeka na lewy widelec
Filozof 5 dostał lewy widelec
Filozof 5 czeka na prawy widelec
Filozof 1 odkłada lewy widelec
Filozof 1 odkłada prawy widelec
Filozof 5 dostał prawy widelec
Filozof 5 je
Filozof 2 dostał lewy widelec
Filozof 2 czeka na prawy widelec
Filozof 1 wychodzi z jadalni
Filozof 3 odkłada lewy widelec
Filozof 3 odkłada prawy widelec
Filozof 3 wychodzi z jadalni
Filozof 2 dostał prawy widelec
Filozof 2 je
Filozof 5 odkłada lewy widelec
Filozof 5 odkłada prawy widelec
Filozof 5 wychodzi z jadalni
Filozof 2 odkłada lewy widelec
Filozof 2 odkłada prawy widelec
Filozof 2 wychodzi z jadalni
Wszystkie wątki zakończone
Zniszczenie semaforów

Do tego będziesz potrzebował:
* rand() + usleep() - do krótkiego, losowego czekania
* sem_init()/sem_destroy() - do tworzenia i niszczenia semaforów
* sem_post() do sygnalizowania
* clock_gettime()+sem_timedwait() do czekania z timeoutem ("Filozof 2 umarł z głodu czekając na prawy widelec"). Możesz użyć po prostu sem_wait(), ale wtedy przy blokadzie program się po prostu zawiesi bez żadnego komunikatu.
* pthread_create() do tworzenia wątków filozofów
* pthread_join() do czekania na zakończenie wątków filozofów.
« Ostatnia zmiana: 2017-01-20, 09:16:05 wysłana przez Paweł Kraszewski »
Paweł Kraszewski
~Arch/Void/Gentoo/FreeBSD/OpenBSD/Specjalizowane customy