buborék rendezés + fork()

 ( qgepapam | 2006. november 19., vasárnap - 2:38 )

Helló mindenki! OS-ből kaptam egy feladatot:
Készítsen több processzen futó rendező programot. Használja a buborék rendezési algoritmust, de az egyes iterációkat párhuzamosan futassa!
Gondoskodjon róla, hogy az egyes iterációkat végző processzek ne előzhessék meg egymást(SZEMAFOR). A párhuzamosan futó processzek száma legyen megadható, és ennél több processz ne fusson soha.

Ehhez ha valakinek lenne valamilyen ötlete, azt szívesen fogadnám.
A rendezési alg. nem gond, már megvan, csak a fork()-oláshoz nem 'tom, hogy kezdjek hozzá :)

Előre is kössz mindenkinek.

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

Hi
Ha jol sejtem akkor itt nem a buborek rendezes a lenyeg hanem az IPC mechanizmus megvalositasa.

szerintem ird at a topick nevet valami masra ami mutatja hogy mi a feladat.

Az ipc resszel tisztaban vagy valamennyire?

A dolog nagyon egyszerű:
A buborék rendezésben ugye van egy belső ciklus ami végigmegy az elemeken, és ha az i. és az i+1. rossz sorrendben van, akkor megcseréli. Ez előrefelé halad, az i. előtti elemeket nem bántja.
Tehát semmi nem akadályoz meg bennünket abban, hogy ne várjuk meg míg befejezi az összes elemet, hanem egy új szálat indítva rögtön elindítsuk a második belső ciklust is amint lehet.
Tehát miközben az első szál a 3.-4. elemet vizsgálja, a 2. szál már kezdi az 1.-2.-at.

Ez jól hangzik, hiszen n elemet n/2 processzoron kb 2n lépésben rendez, ami lineáris futásidő, és azt szeretjük.
Persze ezért még nem kapunk díjakat, mert kell n/2 processzor, ami rikán van. :)

A gond ott van, hogy el kell kerülni, hogy a később indított szál beérje az előtte haladót, azaz ugyanarra a memóriacímre hivatkozzon.
Itt jön a képbe a szemafor.
A legegyszerűbb megoldás, hogy bevezetünk n szemafort, minden elemhez egyet. Minden szál megszerzi mindkét szemafort amihez hozzá akar nyúlni (mint az étkező filozófusoknál). Cserél ha kell, majd elereszti.
Ha nem egyszerre indítod a szálakat, ezzel biztosítod is a sorrendet.

A feladatból szerintem következik, hogy ezt thread-ekkel kell megoldani, nem pedig processzekkel, pláne ha OS-ből kaptad, és nem mondjuk párhuzamos programozásból. Tehát neked nem a fork kell.
pthreads.h a te barátod, bár én inkább valami magasabb szintű libet keresnék a helyedben, nagymértékben megkönnyíti az életed.

Ennek ellentmond, hogy "az egyes iterációkat végző processzek" van a szövegben. Innentől 3 dolog lehetséges:
a) nem pontosan idézted a szöveget
b) pongyola a szöveg
c) tényleg forkolni kell
Szerintem a 3. a legkevésbé valószínű, szerintem kérdezz rá...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

"A feladatból szerintem következik, hogy ezt thread-ekkel kell megoldani, nem pedig processzekkel"...

Csak kiegészítésként: az a gond a processzekkel, hogy nem közös az adat-szegmensük, hanem fork-oláskor egy másolatot kap minden processz a szülő processz adatairól. Ha viszont tényleg processzekkel kell megoldani, akkor shared memory-t kell használnod. Doksi: man shmget és a libc info oldalai.

"A gond ott van, hogy el kell kerülni, hogy a később indított szál beérje az előtte haladót, azaz ugyanarra a memóriacímre hivatkozzon.
Itt jön a képbe a szemafor.
A legegyszerűbb megoldás, hogy bevezetünk n szemafort, minden elemhez egyet. Minden szál megszerzi mindkét szemafort amihez hozzá akar nyúlni (mint az étkező filozófusoknál). Cserél ha kell, majd elereszti.
Ha nem egyszerre indítod a szálakat, ezzel biztosítod is a sorrendet.
"

- Ez így ebben a formában csak az esetleges konkurrens hozzáférések ellen véd, a processzek ettől még simán megelőzhetik egymást. Trükközni persze lehet, hogy a két elem összehasonlítása majd az esetleges csere után nem mindkét szemafort ereszti el a processz, hanem csak az alacsonyabb elemhez tartozót, majd megszerzi a következő elem szemaforát, csakhát minek, merthogy...

- ... merthogy vegyük észre, hogy n sorbarendezendő elemhez n darab szemafor, továbbá minden egyes összehasonlításhoz egy szemafor megszerzése majd eleresztése azért van akkora overkill, hogy a megoldást ne fogadják el (ha saját hallgatóm állna elő vele, én nem fogadnám el).

Cak azt kell garantálni, hogy az előző iteráció mindig előrébb járjon, mint a következő. Még ha n db. szemafor is van, egyszerre sosincs érvényben több, mint a párhuzamosan futó folyamatok száma. Ez nem akkora overhead...

Hát ha szerinted az rendben van, hogy mondjuk 100k sorbarendezendő elemhez legyártsunk 100k szemafort...

Hát ha szerinted rendben van, hogy egy buborék rendezéshez párhuzamosan fut 100k processz, akkor végülis miért ne (n^2-es algoritmus, és ha az iterációk párhuzamosan futnak, lesz ennyi processz).

Nyilván épeszű határokon belül - és ez nem az a nagyságrend. A feladat nem is oldható meg teljesen párhuzamosan.

"Hát ha szerinted rendben van, hogy egy buborék rendezéshez párhuzamosan fut 100k processz"

Ki mondta, hogy a rendezendő elemek és a rendező processzek száma megegyezik?

A feladat.

"...egyes iterációkat párhuzamosan futassa!"

Ugye nem gondolod komolyan?

Ott kezdődik, hogy szerintetek rendben van-e 100k elemre
a buborékrendezés. Szerintem a 100k szemafor a 100k
processzel együtt egy hülyén kiírt feladatra adott hülye
válasz, azt ennyi...

> Sol omnibus lucet.

A pthread_spin_lock -al csinálnám, az egész gyors, de igazad van, n db szemafor semmiképp nem kellene. Bár a feladat kiírása ezt nem engedi meg, sztem nem az a legjobb megoldás, hogy az egyes iterációkat futtatjuk párhuzamosan.

Nos, én úgy gondolkodtam, hogy felhasználó megad "n" db proceszt("n" legyen max. 10 db), ehhez kell "n" darab szemafor a kölcsönös kizárás miatt. Indul az első processz,
rátöltjük az algoritmust, lép egy rendezést és az eredményt kiirja shm-ba, majd blokkolódik, indul a második processz, olvas shm-ből, rendez, ir shm-be..etc.
Kell még egy STATUS valtozó shm-ben 1->ha van még mit rendezni; 0->ha kész a rendezés, ezt a változót kell figyelni, és ha 0, stdoutra kiirni a rendezett elemeket.

Ez nyilván tárgytól, és felsőoktatási intézménytől is függ.

Pl eltén nem szokatlan, hogy n processzoron futó n elemet rendező algoritmust vizsgálunk, tudva, hogy valós körülmények között ilyen nincs. De ettől még nem értelmetlen.

Ha így nézzük buborékrendezést párhuzamosítani sem egy hatalmas gondolat, de ettől még gyakorlásnak elmegy.

Tehát szerintem a megoldás a feladat kiírásának megfelel.

Röviden megfogalmazva: hülye kérdésre hülye válasz...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o