synchronizacja przejazdu przez 1pasmowy most

Witam,

Mam do napisania program:

Na drodze dwukierunkowej północ - południe znajduje się wąski most, przez który w danej chwili mogą, jechać samochody tylko w jednym kierunku. Zsynchronizuj przejazd samochodów jadących z południa i północy tak, aby nie było kolizji i żeby samochód z każdego kierunku mógł w kontu przejechać przez most (czyli żeby nie było zagłodzenie).

Mam w tym momencie pytanie, jak do tego podejśc. Wiem że nie ma mojego wkładu, ale prośba o pomoc i prośba o wszelką pomoc i podpowiedzi związane z rozwiązaniem problemu.

Ja bym to widział jakoś tak:

1. Wątek sterujący ruchem na moście
2. dwa mutexy - po jednym z każdej strony mostu - określające, czy samochody z danej strony mogą jechać
3. dwie kolejki samochodów (kolejne wątki ? ale to chyba niekonieczne)
4. algorytm określający, kiedy można "przełączyć kierunek działania mostu"

Znalazłem rozwiązanie w pascalu jak by ktoś mógł przełożyć to na język C++ był bym bardzo wdzięczny gdyz nie znam jezyka Pascal.

const M = ?; 
P = ?; 
var ac: integer := 0; 
dc: integer := 0;
ap: integer := 0; 
dp: integer := 0; 
CZYT: semaphore := 0; 
PIS: semaphore := 0; 
CHROŃ: binary semaphore := l;
W: binary semaphore := 1; 
process CZYTELNIK (i:1..M) ;
begin
while true do begin
własne_sprawy;
PB(CHROŃ);
ac := ac + 1;
if ap = O then
while dc < ac do begin
dc := dc + 1; 
V(CZYT) 
end; 
VB(CHROŃ);
P(CZYT);
czytanie;
PB(CHROŃ);
dc := dc - 1;
ac := ac - 1;
if dc = O then
while dp < ap do begin
dp := dp + 1;
V(PIS) 
end;
VB(CHROŃ)
end
end;
process PISARZ(i:1..P);
begin
while true do begin
własne.sprawy;
PB(CHROŃ);
ap : = ap + 1;
if ac = O then
while dp < ap do begin
dp := dp + 1; 
V(PIS) 
end;
VB(CHROŃ);
P(PIS);
PB(W);
pisanie;
VB(W);
PB(CHROŃ);
dp := dp - 1;
ap := ap - 1;
if dp = O then
while dc < ac do begin
dc := dc + 1; 
V(CZYT) 
end;
VB(CHROŃ)
end
end;

Skoro nie znasz pascala to napisz swój kod w c++.
Algorytm masz juz podany...

Jak nie umiem paskala to ten algorytm mi sie chyba nie przyda, a z c++ też nie jestem rewelacyjny, chociaż proszę o przerobienie kawałku kodu żebym miał z czego sie wzorować dalej:/

Ale ja nie mówie o tym kodzie pascalowym tylko o slownym opisie algorytmu który masz podany w 2 poście.

[losowa nazwa] napisał(a)

Ja bym to widział jakoś tak:

1. Wątek sterujący ruchem na moście
2. dwa mutexy - po jednym z każdej strony mostu - określające, czy samochody z danej strony mogą jechać
3. dwie kolejki samochodów (kolejne wątki ? ale to chyba niekonieczne)
4. algorytm określający, kiedy można "przełączyć kierunek działania mostu"

IMHO:

2. wystarczy 1 mutex, po prostu: ktora strona go ma w danej chwili, ta aktualnie jedzie. Dwa wprowadzaja niepotrzebne niebezpieczenstwa nieprawidlowej implementacji i zakleszczen. Jesli miales na mysli zobrazowanie dwoch zestawow 'czerownych-zielonych' swiatel z dwoch stron mostu, to para sygnalizatorow czerwono-zielonych swiatel jest pojedynczym muteksem, zas jeden sygnalizator czerwono-zielony jest wykonaniem operacji (try)lock. dwa mutexy moga byc potrzebne, jezeli wprowadzisz kolejny watek - zarzadce mostu - ale wtedy ten drugi mutex nijak ma sie do stron lewej-prawej mostu

3. dwie kolejki to dobra rzecz, ale dla algorytmu duuuuzo lepiej byloby umiescic wszystkie samochody w jednej kolejce z dodatkowa nalepka na samochodzie informujaca w ktora storne on chce jechac. sadze jednak ze powodowalaby potencjalne problemy nieefektywnego uzycia mostu oraz ze bylaby to zbytnia abstrakacja od problemu i tworca zadania faktycznie chcial "widziec" dwie kolejki. odrebne watki dla kolejek nie sa potrzebne, chyba ze na potrzeby testow je dorzucic jako producentow ktorzy asynchronicznie i losowo do-generowaliby nowe samochody do kolejek

1+4) tez sadze ze jeden watek, spokojnie moze byc to nawet watek glowny :) ale 'kiedy przelaczac kierunek ruchu' - fraza moze mylic, zalezy od pomyslu autora - albo niech nadjezdzajace samochody same sie ze soba zgrywają w czasie i 'wspolnie' same 'decyduja', albo narzucac czas arbitralnie z zewnatrz - wtedy mozna smialo mowic o takim algorytmie

A nie można prościej?
Na starcie czerwone na południe, zielone na północ. Po czasie t czerwone w obu kierunkach (t dowolne > 0), po czasie t_p zielone na południe, czerwone na północ (czas t_p na tyle duży by samochody opuściły most), itd.
Jeśli będzie ruch tylko w jednym kierunku, to samochody będą zapewne niepotrzebnie stały, ale w sformułowaniu zadania nic nie ma o optymalizacji. Dla optymalizowania trzeba by mieć informacje o natężeniu ruchu w obu kierunkach albo "pętle indukcyjne" w szosie informujące o aktualnej długości kolejek.

moim zdaniem, w problemie brakuje określenia ile samochodów most może obsłużyć jednocześnie (oczywiście jadących w jednym kierunku) - jest to związane z czasem przejazdu jednego auta. Jeśli ta wartość wynosi 1 to nie ma co kombinować jeden mutex jedna kolejka i po sprawie. Sprawa się komplikuje jeśli na moście może być więcej niż jeden samochód, ponieważ wtedy jest problem efektywnego wykorzystania mostu, przy równoczesnym zapobieganiu zagłodzenia jednej ze stron mostu.

bogdans_niezalogowany napisał(a)

A nie można prościej?
Na starcie czerwone na południe, zielone na północ. Po czasie t czerwone w obu kierunkach (t dowolne > 0), po czasie t_p zielone na południe, czerwone na północ (czas t_p na tyle duży by samochody opuściły most), itd.
Jeśli będzie ruch tylko w jednym kierunku, to samochody będą zapewne niepotrzebnie stały, ale w sformułowaniu zadania nic nie ma o optymalizacji. Dla optymalizowania trzeba by mieć informacje o natężeniu ruchu w obu kierunkach albo "pętle indukcyjne" w szosie informujące o aktualnej długości kolejek.

przelaczanie czasu tak jak na klasycznych swiatlach na kazdym normalnym skrzyzowaniu prowadzi wprost do modelu rozwaizania ktore nazwalem "wprowadzeniem zewnetrzenego zarzadcy", i takie konkretnie rozwiazanie bedzie mialo efekt uboczny ktory nazwalem "nieefektywnym wykorzystaniem mostu"

wszystko co MarekR22 mowi tez jest prawda - ale po zrewidowaniu pierwotnego opisu zadania ...chyba budujemy statek kosmiczny w odpowiedzi na proste zadanie wprowadzajace studenta do zagadnien synchronizacji :)