[C#] Problem głodnych filozofów

Kusterek OP · 02-01-2014 16:00

Siema,
muszę zakodzić problem głodnych filozofów (lub czasami też się mówi 'problem pięciu filozofów'). Pokrótce wytłumaczę o co chodzi w tym problemie.
Mamy 5 filozofów przy okrągłym stole. Między każdą parą filozofów jest widelec, więc przy każdym filozofie są 2 widelce. Na samym środku jest miska ze spaghetti i aby ją zjeść trzeba użyć 2 widelców. Filozofowie nie rozmawiają ze sobą i każdy z nich chce się najeść ale oczywiście widelców dla wszystkich nie starcza, ponadto jak każdy weźmie np. lewy widelec to nastąpi zjawisko zakleszczenia. Generalnie trzeba rozwiązac problem tak aby każda się najadł i się nie zagłodził.
Jeżeli coś niejasno przedstawiłem to link tutaj: http://pl.wikipedia.org/wiki/Problem...filozof%C3%B3w

Algorytm może być taki:
1. Rzuć monetę, by wylosować lewą lub prawą stronę
2. Czekaj aż wylosowany widelec będzie wolny i podnieś go
3. Jeśli drugi widelec jest zajęty to odłóż podniesiony widelec i przejdź do kroku 1.
4. Jeśli drugi widelec jest wolny to go podnieś
5. Jedz
6. Odłóż oba widelce

I trzeba to zakodzić współbieżnie aby odbywało się to dla każdego z pięciu filozofów.

Robił ktoś coś podobnego albo może mnie wprowadzić do programowania współbieżnego w C#? ;<

Alex Fortune · 02-01-2014 16:04

Ja bym to zrobil mniejwiecej tak , że tworzysz osobny wątek dla każdego filozofa, losujesz z jakiegoś wątku głównego filozofa ,,startującego", odpalasz go, a potem odpalasz resztę i czekasz grzecznie podnosząc oba widelce kiedy tylko się da :P

Absherr · 02-01-2014 16:33

Wydaje mi się, że losowanie startującego filozofa nie jest potrzebne. Można je odpalić po prostu jeden po drugim.

Kusterek OP · 02-01-2014 22:50

Boże nic nie kminie tej wielowątkowości ;o
może mi ktoś w skrócie podpowiedziec kilka rzeczy?

czym jest lock?
lock daje to, że w danym momencie tylko 1 wątek może przebywać w tym miejscu, czyli to się akurat przyda np. dla widelcow, tak?

@up
ja muszę chyba odpalić ich wszystkich jednocześnie żeby to miało jakikolwiek sens.

@top
kuźwa nie wiem jak to zakodzić

Alex Fortune · 02-01-2014 23:33

Kusterek napisał

Cytat został ukryty, ponieważ ignorujesz tego użytkownika. Pokaż cytat.

Boże nic nie kminie tej wielowątkowości ;o
może mi ktoś w skrócie podpowiedziec kilka rzeczy?

czym jest lock?
lock daje to, że w danym momencie tylko 1 wątek może przebywać w tym miejscu, czyli to się akurat przyda np. dla widelcow, tak?

@up
ja muszę chyba odpalić ich wszystkich jednocześnie żeby to miało jakikolwiek sens.

@top
kuźwa nie wiem jak to zakodzić

Jeśli kod dojdzie do miejsca gdzie jest lock, mutex zostanie założony. Gdy inny wątek w to miejsce trafi, zostanie zatrzymany - do czasu, kiedy poprzedni wątek nie odblokuje tego locka

Kusterek OP · 10-01-2014 14:40

mam problem w losowaniu stron ;s
Zrobiłem klasę mojego wątku, tam metoda run(), gdzie każdy wątek losuje stronę z ktorej chce wziąć widelec. Problem jest taki, że zawsze wybiera mi tą samą stronę, albo wszyscy biorą lewy, albo wszyscy biorą prawy ;s Da sie to jakoś ogarnac? Nawet lock zapodałem ale jest praktycznie tak samo ;s
klasa moich wątków:

Kod :

class MyThreadClass
    {
        bool najedzony;
        int numer;
        int widelec;
        static object zamek = new object();
        public MyThreadClass(int numer)
        {
            najedzony = false;
            this.numer = numer;
        }

        public void Run()
        {
            Console.WriteLine("Rozpoczynam pracę...");
            lock (zamek)
            {
                Random gen = new Random();
                int strona = gen.Next(0, 2);
                switch (strona)
                {
                    case 0:
                        widelec = modulo(numer - 1, 5);
                        break;
                    case 1:
                        widelec = modulo(numer + 1, 5);
                        break;
                }
                //widelec = gen.Next(1, 100);
            }
            Console.WriteLine("Filozof numer: {0}, wylosował widelec numer: {1}", numer, widelec);
            Console.WriteLine("Kończę pracę...");
        }
        int modulo(int a, int b)
        {
            return a < 0 ? a + b : a % b;
        }
    }

a wątki rozpoczynam tak:

Kod :

 MyThreadClass filozofClass0 = new MyThreadClass(0);
            MyThreadClass filozofClass1 = new MyThreadClass(1);
            MyThreadClass filozofClass2 = new MyThreadClass(2);
            MyThreadClass filozofClass3 = new MyThreadClass(3);
            MyThreadClass filozofClass4 = new MyThreadClass(4);
            Thread filozof0 = new Thread(new ThreadStart(filozofClass0.Run));
            Thread filozof1 = new Thread(new ThreadStart(filozofClass1.Run));
            Thread filozof2 = new Thread(new ThreadStart(filozofClass2.Run));
            Thread filozof3 = new Thread(new ThreadStart(filozofClass3.Run));
            Thread filozof4 = new Thread(new ThreadStart(filozofClass4.Run));
            filozof0.Start();
            filozof1.Start();
            filozof2.Start();
            filozof3.Start();
            filozof4.Start();

bercik · 10-01-2014 15:05

http://stackoverflow.com/questions/1...-random-values

W skrócie utwórz sobie zmienną "gen" poza klasą, przed wywoływaniem i przekazuj w parametrze, Random jest pseudolosowy więc po utworzeniu zmiennej zawsze pierwsza wartość będzie taka sama (druga, trzecia i kolejne też), chyba, że podasz jakiegoś seeda do ustawienia losowości - tu już odsyłam do wujka :)

Kusterek OP · 10-01-2014 15:16

bercik napisał

Cytat został ukryty, ponieważ ignorujesz tego użytkownika. Pokaż cytat.

http://stackoverflow.com/questions/1...-random-values

W skrócie utwórz sobie zmienną "gen" poza klasą, przed wywoływaniem i przekazuj w parametrze, Random jest pseudolosowy więc po utworzeniu zmiennej zawsze pierwsza wartość będzie taka sama (druga, trzecia i kolejne też), chyba, że podasz jakiegoś seeda do ustawienia losowości - tu już odsyłam do wujka :)

Kod :

                Random gen = new Random(Guid.NewGuid().GetHashCode());

zalatwilo sprawe ;) dzieki za link

#EDIT
generalnie chyba zjebałem wielowątkowość, wątki powinny chyba korzystać z jednej instancji metody run(). No nie? ;s

Kusterek OP · 10-01-2014 21:40

Zakodziłem program, jednak nie wiem czy chodzi poprawnie i spełnia wszystkie warunki, moze ktos mi sprawdzic?
skorzystałem z pół statycznych typu bool, które reprezentują widelce.

ALGORYTM:
1. Wylosuj stronę z której weźmiesz widelec.
2. Poczekaj 2 sec, jak widelec jest wolny to go podnieś.
3a. Sprawdz czy drugi widelec jest wolny, jeżeli jest to go podnieś.
3b. Jeżeli jest zajęty to odłóż pierwszy widelec i zacznij od nowa.
4. Jak masz 2 widelce w ręku to zjedz i odłóż oba.

KOD:

Kod :

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

namespace fil
{
    class Program
    {
        
        static void Main(string[] args)
        {
            FilozofClassThread filozofClass0 = new FilozofClassThread(0);
            FilozofClassThread filozofClass1 = new FilozofClassThread(1);
            FilozofClassThread filozofClass2 = new FilozofClassThread(2);
            FilozofClassThread filozofClass3 = new FilozofClassThread(3);
            FilozofClassThread filozofClass4 = new FilozofClassThread(4);
            Thread filozof0 = new Thread(new ThreadStart(filozofClass0.Run));
            Thread filozof1 = new Thread(new ThreadStart(filozofClass1.Run));
            Thread filozof2 = new Thread(new ThreadStart(filozofClass2.Run));
            Thread filozof3 = new Thread(new ThreadStart(filozofClass3.Run));
            Thread filozof4 = new Thread(new ThreadStart(filozofClass4.Run));
            filozof0.Start();
            filozof1.Start();
            filozof2.Start();
            filozof3.Start();
            filozof4.Start();
            Console.ReadKey();
        }
    }
    class FilozofClassThread
    {
        static volatile bool[] widelce = new bool[5] { false, false, false, false, false };
        int numer;
        int widelec;
        int drugi_widelec;  
        int wykonanie;
        public FilozofClassThread(int numer)
        {
            this.numer = numer;
            wykonanie = 0;
        }

        public void Run()
        {
            Console.WriteLine("Filozof numer {0} losuje strone", numer);
            Label:
            do
            {
                if (wykonanie > 0)
                    widelce[widelec] = false;
                wykonanie++;
                Random gen = new Random(Guid.NewGuid().GetHashCode());
                int strona = gen.Next(0, 2);
                switch (strona)
                {
                    case 0:
                        widelec = modulo(numer - 1, 5);
                        Console.WriteLine("Filozof numer {0}, wylosowal widelec numer {1}", numer, widelec);
                        Thread.Sleep(2000);
                        if (!widelce[widelec])
                            widelce[widelec] = true;
                        else
                            goto Label;
                        drugi_widelec = modulo(numer + 1, 5);
                        break;
                    case 1:
                        widelec = modulo(numer + 1, 5);
                        Console.WriteLine("Filozof numer {0}, wylosowal widelec numer {1}", numer, widelec);
                        Thread.Sleep(2000);
                        if (!widelce[widelec])
                            widelce[widelec] = true;
                        else
                            goto Label;
                        drugi_widelec = modulo(numer - 1, 5);
                        break;
                }
                
            } while (widelce[drugi_widelec]);

            jedz(numer);


        }
        int modulo(int a, int b)
        {
            return a < 0 ? a + b : a % b;
        }
        void jedz(int numer)
        {
            widelce[widelec] = false;
            widelce[drugi_widelec] = false;
            Console.WriteLine("Filozof numer {0} zjadl spaghetti... uzywajac widelca {1} i {2}",numer,widelec, drugi_widelec);
        }

    }
}

Ewande · 26-01-2014 15:05

Nie wiem, czy to jest aktualne jeszcze, ale ja rozwiązywałem ten problem z użyciem semaforów i korzystając z faktu, że jeżeli w jadalni będzie cały czas maksymalnie 4 filozofów, to nie nastąpi zakleszczenie i przynajmniej jeden z nich będzie mógł zjeść.

Kusterek OP · 26-01-2014 19:44

Juz nie aktualne ale pomysł ciekawy. Tylko w moim poleceniu chodzilo bardziej o zdarzenia w czasie (czego i ja za bardzo nie uwzglednilem) o czym zostalem poinformowany przy oddaniu sprawozdania ;D

Temat: [C#] Problem głodnych filozofów

Narzędzia tematu

Oceń ten temat

[C#] Problem głodnych filozofów

Informacje o temacie

Użytkownicy przeglądający temat

Podobne tematy

[C#] Problem z wydajnością (stara nazwa: [C++] Problem ze wskaźnikami)

Nierozwiązany przez nikogo problem z lagami w laptopie. Problem XXI wieku.

Problem z uruchomieniem minecrafta, jakis problem z java...

[7.6][Problem Z Map Edytem] Problem z mapa

Zakładki

Zakładki

Zasady postowania