C - synchronizace vlaken nad spojovym seznamem

Nevím, jestli je to ideální, ale napadlo mě: Co kdybys zamykal nějakou proměnnou (nejspíš ukazatel), který by představoval položku v seznamu, se kterou pracuje nějaké vlákno? Pak by každé vlákno nejdřív porovnalo ten ukazatel s tím, kam chce přistoupit a případně by se zařadilo do fronty, nebo by mohlo přistoupit k položce, ke které chce, protože s ní žádné jiné vlákno nepracuje.

Tyjo, nejak nemuzu pochopit, jak jsi to myslel. Zkus to konkretne na te strukture ci spojaku. Co myslis tou promennou predstavujici polozku v seznamu?

No záleží, jak to máš přesně implementované, ale řekněme, že vlákno chce pracovat s nějakou položkou v seznamu. Najde ji a ukazatel na ni vloží do nějaké proměnné (ta bude v kritické sekci). A pak s položkou pracuje. Jiné vlákno bude chtít tu stejnou položku, tak si ji najde, ale před tím zkontroluje, jestli ten ukazatel na ni není stejný, jako ten v kritické sekci. Pokud je, tak se zařadí do fronty (my řešili něco podobného s pomocí unixových semaforů). Jak původní vlákno skončí, tak ten ukazatel smaže a pustí jiné vlákno, které čeká třeba na nějakém semaforu. Ale ber to jako úvahu. Nevím, jestli tam nevznikne třeba race condition apod. To chce nad tím sednout a promyslet všechny možnosti..

Jo uz jsem ASI pochopil. Ze do nejake promenne si ulozim strukturu ze spojaku, se kterou chci pracovat. Tim jina vlakna poznaji, ze v te promenne neco je, tak se nad ni zablokuji, dokud nebude volno. To mi ale prijde, ze neresi problem, kdyz mam napr. 10 struktur, jedno vlakno chce ke strukture 3, druhe ke strukture 8. "Promennou" obsadilo vlakno pro strukturu 8, tim padem druhe vlakno, ktere chce ke strukture 3, musi cekat. Je to tak?

Do proměnné si uložíš jen ukazatel na tu strukturu a můžeš ho porovnávat s ukazatelem, kam chceš přistoupit. Pak chce třeba vlákno přistoupit ke struktuře 8, mrkne do kritické sekce, tam je třeba ukazatel na strukturu 3, tak s tou osmičkou může klidně pracovat a zase někde uložit informaci, že s ní pracuje. Asi teda nebude stačit jen jeden ukazatel, ale tolik, kolik je vláken. Možná..

To je vlastne pravda, ze kdyz vim, ze mam 10 vlaken, ze bude vzdy obsazeno max 10 struktur - a to by byl take vyjimecny pripad. Takze nejake uloziste pro 10 ukazatelu, ktere bude soucasne kritickou sekci.

Ano, přesně taková je úvaha A protože se v nich bude vyhledávat asi docela často, můžeš to udělat jako binární vyhledávací strom, jestli víš o co jde.

Co by v tom pripade bylo klicem, resp. hodnotou uzlu?

Hodnota uzlu by byla ukazatel na strukturu a klíč v podstatě cokoliv, aby byl pro každou položku jiný. Třeba vypočítat z hodnoty ukazatele a pak vydělit modulem, aby to bylo číslo jen v nějakém rozsahu apod.

Nebylo by misto implementace binarniho stromu jednodussi projit proste 10ti prvkove pole? :)

Bylo, jen to bude trochu neefektivní.

Každá položka bude mať svoj vlastný zámok, ktorý budeš používať na synchronizáciu práce práve s tou jednou položkou. Okrem toho, budeš mať jeden spoločný zámok pre prácu so zoznamom (pridávanie, uberanie, iterovanie).

Čiže napr.:

struct game{
  int id;
  short active;
  mutex *list_mutex;
  mutex *item_mutex;
  struct player *player1;
  struct player *player2;
  struct game *next;
  struct game *previous;
};

Pri vytváraní prvej položky zoznamu vytvoríš zámok list_mutex, ktorý pri pridávaní ďalších položiek budeš kopírovať tým položkám. Pri vytváraní každej položky si vytvoríš nový zámok item_mutex.

To je lepsi reseni nez jsme vymysleli (kolega vymyslel) predtim... Diky.