problem 5 filozofów z użyciem semaforów

[kwgr]

Mam do napisania teki program z użyciem semaforów i pamięci współdzielonej. Opis problemu jest następujący:

Mamy w nim do czynienia z pięcioma uczonymi, którzy spędzają czas na myśleniu, ale czasem muszą się też posilić. Wtedy zasiadają do stołu, aby pożywić się jedząc spagetti. Problem polega na tym, że na stole znajduje się tylko pięć widelcy, a każdy z myślicieli potrzebuje dwóch, aby móc spożyć potrawę. Spośród całej serii rozwiązań tego ciekawego zadania wybrałem takie, które zapewnia spełnienie podstawowych zasad prawidłowego programu współbieżnego. Wykorzystuje ono semafor lokaja, który dopuszcza do stołu tylko czterech spośród filozofów. W ten sposób nigdy nie dojdzie do blokady, ani też żaden z filozofów nie zostanie zagłodzony. Zobaczmy zatem jakie zmienne potrzebujemy w naszym rozwiązaniu:

oraz kod w języku C#:

Kod: [Zaznacz]

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace PieciuFilozofow
{
    /// 

    /// Klasa rozwiązująca problem pięciu filozofów w wersji bez możliwości zagłodzenia,
    /// ani blokady, czyli przez dopuszczenie do stołu maksymalnie 4 filozofów w danej
    /// chwili, co gwarantuje, że przynajmniej jeden z nich zdobędzie 2 widelce.
    /// Autor: Radosław Iwaszyn
    /// Algorytm na podstawie książki: Z.Weiss, T.Gruźlewski: "Programowanie współbieżne i rozproszone", Warszawa, WNT 1993
    /// 

    class PieciuFilozofow
    {
        static void Main(string[] args)
        {
            PieciuFilozofow pf = new PieciuFilozofow();

            pf.Startuj();
            Thread.Sleep(10000); //czekamy losowy czas
            pf.Zakoncz(); //przerywamy wątki
        }

        private Semaphore[] widelce;  //tablica binarnych semaforów widelce
        private Semaphore lokaj;  //semafor lokaj, który dopuszcza
                                  //co najwyżej 4 filozofów do stołu
        
        private Thread[] filozofowie; //tablica wątków filozofów


        /// 

        /// Konstruktor klasy PieciuFilozofow odpowiedzialny między innymi
        /// za inicjalizację i nadanie nazw wątkom.
        /// 

        public PieciuFilozofow()
        {
            widelce = new Semaphore[5];
            for (int i = 0; i < 5; i++)
            {
                widelce[i] = new Semaphore(1, 1);  //semafory binarne
            }
            lokaj = new Semaphore(4, 4);

            filozofowie = new Thread[5];  
            for (int i = 0; i < 5; i++)
            {
                filozofowie[i] = new Thread(new ThreadStart(Filozof)); //tworzymy wątki
                filozofowie[i].Name = "Filozof " + i; //i nadajemy im nazwy
            }

        }

        /// 

        /// Funkcja uruchamiająca wszystkie wątki.
        /// 

        public void Startuj()
        {
            foreach (Thread t in filozofowie)
            {
                t.Start();
            }
        }


        /// 

        /// Funkcja przerywająca wszystkie wątki
        /// 

        public void Zakoncz()
        {
            foreach (Thread t in filozofowie)
            {
                t.Interrupt();
            }
        }


        /// 

        /// Wątek filozofa, który w nieskończonej pętli myśli przez losowy czas,
        /// a następnie próbuje zdobyć dwa widelce i przez losowy czas je.
        /// 

        public void Filozof()
        {
            try
            {
                int numer = Int32.Parse(Thread.CurrentThread.Name.Split(' ')[1]);
                Random rand = new Random();
                while (true)
                {
                    Console.WriteLine("{0} myśli", Thread.CurrentThread.Name);
                    Thread.Sleep(rand.Next(100, 500)); //losowy czas myślenia

                    lokaj.WaitOne(); //sprawdzamy, czy możemy usiąść do stołu
                    widelce[numer].WaitOne(); //bierzemy lewy widelec
                    widelce[(numer + 1) % 5].WaitOne(); //bierzemy prawy widelec
                    Console.WriteLine("{0} je", Thread.CurrentThread.Name);
                    Thread.Sleep(rand.Next(100, 300)); //losowy czas jedzenia
                    widelce[numer].Release(); //odkładamy lewy widelec
                    widelce[(numer + 1) % 5].Release(); //odkładamy prawy widelec
                    lokaj.Release(); //dopuszczamy kolejnego filozofa do stołu                    
                }
            }
            catch (ThreadInterruptedException)
            { }
        }
    }
}

Czy na podtawie da się napsać program działający w środowisku LINUX w języku C++?

Dzieki. Pozdraiwam.

[Paweł Kraszewski]

Krótka odpowiedź: Tak, da się. Nie, nie rozwiązujemy tu zadań domowych.
Długa odpowiedź: Wytłumaczenie jak było najprawdopodobniej na zajęciach, które przespałeś. Jak tylko ty nie zrozumiałeś (a konsultacje były tylko o pełni księżyca o północy na cmentarzu na drugim końcu Polski), to poproś kolegów z grupy o pomoc. Jak cała grupa nie rozumie, to zgłoście to wykładowcy. Jego zasmarkanym obowiązkiem jest tłumaczyć tak długo aż zrozumiecie. Jak odmówi nie podając logicznego uzasadnienia (np. takiego, że na zajęcia chodziły tylko 3 osoby ze 100), zgłoście dziekanowi.
Krótkie uzasadnienie: jestem byłym wykładowcą, który nigdy nie odmówił wyjaśnienia problemu, jeżeli ktoś czegoś nie rozumiał. W moim interesie było wytłumaczyć na zajęciach na tyle dobrze, żeby nie trzeba było chodzić na konsultacje.
Westchnienie: inni wykładowcy to chyba zauważyli, bo zaczęli przechodzić studenci i prosić o wyjaśnienie innych przedmiotów.
Ostrzeżenie: Nawet nie próbuj uzasadniać swojego nieprzygotowania pracą zawodową. Miałem studentów, którzy zasuwali w robocie cały tydzień a mimo tego przychodzili przygotowani na zajęcia - ewentualnie przychodzili trochę przed zajęciami, żeby się o coś dopytać.

[RyszardLin]

Witam

Hm, może się mylę, ale C# ma swoje korzenie z C++ z pewnymi różnicami - i bez obrazy, ale wystarczy zasiąść przed "słownikiem" i przetłumaczyć kod na C++ i jest program napisany pod Linuxa. Ale chyba ktoś tu jest zbyt leniwy na to - bez obrazy.

Pozdro

[mikolajS.]

Masz gotowy algorytm, ale musisz znaleźć odpowiednie biblioteki (polecam QT4). Będzie jednak sporo różnic w budowie programu.

[kwgr]

Udalo sie napisac taki kod lecz ma problem bo cos nie dziala do konca

Kod: [Zaznacz]

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define semPath "/dev/null"
#define semkeyId 1
#define shmPath "/dev/null"
#define shmkeyId 1

#define memSize 1024

#define numPhil 5
#define right (((i)+1)%numPhil)
#define left ((i - 1 + numPhil)%numPhil)
#define lock (numPhil + 1)

enum {THINKING, HUNGRY, EATING};
char *state;

int downMutex(int i,int semid);
int upMutex(int i, int semid);
void test(int i, int semid);
void acquireFork(int i, int semid);
void releaseFork(int i,int semid);
void philosopher(int i,int semid);

int main(void)
{
	pid_t child;
	int rc, semid, shmid, i, a;
	key_t semkey, shmkey;
	void *shm_addr;
	//struct sembuf operations[2];
	//struct shmid_ds shmid_struct;
	short array[numPhil];
	
	semkey = ftok(semPath,semkeyId);
	if(semkey == (key_t)-1)
	{
		printf("main: ftok() for sem failed!  zwrocilo  (-1) \\n");
		return -1;	
	}
	shmkey = ftok(shmPath,shmkeyId);
	if(shmkey == (key_t)-1)
	{
		printf("main: ftok() for shm failed!  zwrocilo  (-1) \\n");
		return -1;	
	}
	semid = semget(semkey,numPhil, 0644 | IPC_CREAT | IPC_EXCL);
	if(semid == -1)
	{
		printf("main: semget() failed  zwrocilo  (-1) \\n");
		return -1;	
	}	
	for(a = 0;a < numPhil;a++)
	{
		array[a] = 0;
	}

/*    WYWOŁANIE SYSTEMOWE: semctl();                                                          
    PROTOTYP: int semctl ( int semid, int semnum, int cmd, union semun arg );
      ZWRACA: liczba dodatnia jeżeli sukces 
               -1 - błąd: errno = EACCESS ( brak prawa dostępu )
                                  EFAULT ( nieprawidłowy adres wskazywant przez argument arg )
                                  EIDRM ( zestaw został usunięty )
                                  EINVAL ( zestaw nie istnieje lub semid nieprawidłowy )
                                  EPERM (EUID nie ma prawa do cmd w arg)
  				ERANGE ( wartość semafora przekroczona )
    UWAGI: Przeprowadza operacje kotrolne na zestawie semaforów
*/


	rc = semctl(semid, 1, SETALL, array);		//tu funkcja zwraca blad! Powod?
	if(rc == -1)
	{
		printf("main: semctl() initialization failed  zwrocilo  (-1) \\n");
		return -1;	
	}
/*           arg dla wywołania semctl. 
          union semun {
                  int val;                // wartość dla SETVAL 
                  struct semid_ds *buf;   // bufor dla IPC_STAT i IPC_SET 
                  ushort *array;          // tablica dla GETALL i SETALL 
                  struct seminfo *__buf;  // bufor dla IPC_INFO 
                  void *__pad;
          };
*/


	shmid = shmget(shmkey, memSize, 0644 | IPC_CREAT | IPC_EXCL);
	if(shmid == -1)
	{
		printf("main: shmget() failed  zwrocilo  (-1) \\n");
		return -1;
	}
	shm_addr = shmat(shmid, NULL, 0);
	if((int *)shm_addr < 0)
	{
		printf("main: shmat() failed  zwrocilo  (-1) \\n");
		return -1;	
	}	
	printf("ready for client jobs  zwrocilo  (-1) \\n");

	for(i = 0; i < numPhil; i++)
	{
		//printf("loop\\n");
		//child = fork();
		if((child = fork())== -1)
		{
			fprintf(stderr,"\\nfailed to fork  zwrocilo  (-1)  \\n");
			return -1;			
		}
		else if((child = fork())== 0)
		{
			philosopher(i,semid);
			printf("child\\n");
			exit(0);
		}
	}	
	//clean up the environment
	rc = semctl(semid, 0, IPC_RMID,0);
	if(rc == -1)
	{
		printf("main: semctl() remove id failed\\n");
		return -1;
	}
	rc = shmdt(shm_addr);
	if(rc == -1)
	{
		printf("main: shmdt() failed\\n");
		return -1;
	}
	rc = shmctl(shmid, IPC_RMID, 0);
	if(rc == -1)
	{
		printf("main: shmctl() failed\\n");
		return -1;
	}		
	return 0;
}

int downMutex(int i,int semid)
{
	struct sembuf operat;
	operat.sem_num = i;
	operat.sem_op = -1;
	operat.sem_flg = 0;
	semop(semid,&operat,1);
return 0;		//dopisane by tylko nie bylo ostrzezen, do niczego nie wykorzystywane.
}

int upMutex(int i,int semid)
{
	struct sembuf operat;
	operat.sem_num = i;
	operat.sem_op = 1;
	operat.sem_flg = 0;
	semop(semid,&operat,1);
return 0;		//dopisane by tylko nie bylo ostrzezen, do niczego nie wykorzystywane.
}

void test(int i,int semid)
{
	if(state[i] == HUNGRY && state[left] != EATING && state[right] != EATING)
	{
		 state[i] = EATING; 
		 upMutex(i,semid);
	}
}

void acquireFork(int i,int semid)
{
	downMutex(lock,semid);
	state[i] = HUNGRY;
	test(i,semid);
	upMutex(lock,semid);
	downMutex(i,semid);	
}

void releaseFork(int i, int semid)
{
	downMutex(lock,semid);
	state[i] = THINKING;
	test(right,semid);
	test(left,semid);
	upMutex(lock,semid);
}

void philosopher(int i,int semid)
{
	while(1)
	{
 		state[i] = THINKING;
		printf("Phil[%d] : thinking\\n",i);
 		acquireFork(i,semid);
		printf("Phil[%d] : feels hungry",i);
 		state[i] = EATING;
		printf("Phil[%d] : eating\\n",i);
 		releaseFork(i,semid);
	}
}

Ostrzenia zostały wyeliminowane, lecz program się wywala na:

Kod: [Zaznacz]

ready for client jobs  zwrocilo  (-1) 
main: semctl() remove id failed
linia nr 80

Grzie popelnilem blad?