Keskustelu: Yleinen keskustelu: Datavaraston säikeistys

Kyselisin teidän mielipidettä tuosta miten toteuttasin säikeistyksen omalle datavarasto-luokalle. Ideana sillä on että luokalla on dynaaminen taulukko "vektori" samankokoisia palasia. Käyttötarkoitus voi olla esim Minecraft-tyylinen pelimaailma, tai ei sen tarvitse olla edes peli ylipäätään. Struktuuri on tällanen:

TDataBlock = record
  data: PByte;
  compressed: TMemoryStream;
  useTime: cardinal;
end;

Eli blokki voi pitää sisällään datan käytettävässä muodossa data-pointterin kautta, tai sitten pakattuna streamiin. Varasto-luokka pakkaa automaattisesti kaikki blokit joita ei ole käytetty viimeiseen 15 sekuntiin (aika konfiguroitavissa). Näin muistinkäyttö pysyy alhaisena vaikka kartta näennäisesti voi olla valtava, ja kerralla ladattuna keskusmuistiin.

Noh, ylläoleva toimii nykyään hyvin, mutta ajattelin lisätä säikeet. On tullut mieleen vähintään 2 eri ratkaisumallia enkä viittis lähteä koodaamaan ennen kun on mietitty loppuun asti mikä on parempi. Kun pääohjelma tarvitsee dataa eikä sitä ole purettu, niin:
1) Kuten nykyään, ohjelma purkaa sen heti, palauttaa pointterin, ja tuhoaa pakatun streamin. Tämä tapa tulee aina olemaan vaihtoehtoisesti mahdollinen.
2) Palauttaa pointterin jos on purettu, muuten luo palaselle uuden säikeen joka purkaa datan. Vasta joku seuraavista kutsuista palauttaa pointterin dataan, kunhan säie lopettaa toimintansa.
3) Kuten 2), mutta varasto pitää yllä esim 8:aa säiettä datan purkaamiseen ja pakkaamiseen. Jokaisella säikeellä on jono pakkaus/purku-tehtäviä. Varasto-luokka jakaa tehtävät vaan vuoronperään jokaiselle tasaisesti.

Tällä hetkellä alkaa tuntua siltä että 2) olis paras vaihtoehto. Ongelma mikä siinä on (jos nyt sekään on ongelma) että säikeiden määrä voi kasvaa suureksi, teoriassa. Luulisin että käytännössä määrä ei olisi suuri, ellei pelaajia ole tuhansia eri puolilla karttaa. Jos jokainen pysyy vain paikallaan niin mitään datan purkamista ei tapahdu... Toisaalta datan pakkaamista voi tapahtua netti-paketteja varten.

No päädyin koodaamaan vaihtoehdon 2. Mutta sillä ehdolla että jos olemassaolevia säikeitä on jo 100, niin toimitaan vaihtoehdon 1) tavalla ja tehdään pakkaus/purku heti paikalla.

Jos kielessä on jo valmis tuki thread pooleille, niin ne olisivat luultavasti hyvä ja helppo ratkaisu. Tämä vastaisi hyvinkin lähelle tuota vaihtoehtoa 3. Ja vaikkei valmista tukea olisikaan, niin silti sellaisen käyttöä kannattaa harkita.

Käytännössä siis olisi vakiomäärä säikeitä (esimerkiksi 1/suoritinydin) ja jono tehtäviä (pakkaus- ja purkutehtäviä), joita kukin säie suorittaa sitä mukaa kun ehtii ja hakee jonosta uuden tehtävän aina kun edellinen on valmis.

http://en.wikipedia.org/wiki/Thread_pool_pattern

Tuo 1/suoritinydin on ehkä vähemmän triviaali toteuttaa ja toisaalta jos prosessori tukee esim. hyperthreadingia niin saattaa olla turhan pienikin määrä.

Turha luoda kauheaa määrää säikeitä, koska jos joka säikeelle ei riitä omaa ydintä, joudutaan vaihtamaan samassa ytimessä säikeiden välillä ja tämä on raskas operaatio verrattuna hyvin toteutettuun omaan microtask järjestelmään, jossa yksi säije suorittaa jonossa sille annetut tehtävät.

Tuo Samin ratkasu kuulostaa hyvältä. En tullut ajatelleeksi että jono voi olla yhteinen. Pitää vaan olla varovainen siinä miten toteuttaa tuon, että uutta tehtävää ei anneta kahdelle säikeelle yhtäaikaa. On parasta että säie hakee itse uuden työn jonosta jotta nukkumista jää vähemmän, eikä niin että joku jonon-hallinta jakaa niitä jos säikeeltä loppui hommat. Jonon vois esim lukita boolean-muuttujalla siinä kun työtä jaetaan, ja toinen säie vaan yrittää hakua uudestaan "jonkun ajan päästä". (Mitä tuolla lie tarkotan... sleep(1) odottais liian kauan)

Laitan että ohjelmoija saa päättää montako työsäiettä tehdään, mutta käytän itse kahta. Luulisi riittävän quad-corellekin. Toinen seikka on jono itse, joka vois olla yksisuuntainen linkitetty lista. Tiedossa olisi ensimmäinen ja viimeinen alkio kuitenkin. Näin ei tarvitse luoda vakiomittasta tai dynaamisesti muuttuvaa taulukkoa.

Kielelläkin näyttäis olevan jotain keinoja hakea CPU:n lukumäärä
http://forum.lazarus.freepascal.org/index.php?topic=4098.0

Varmistat vaan, että sekä tuottajat (pakkaus- ja purkutehtäviä jonoon laittavat säikeet), että kuluttajat (suorittajasäikeet) ovat synkronoituja keskenään. Käytännössä tämä hoituu sillä, että koodissa on ns. kriittisiä lohkoja, joita ainoastaan yksi säie saa olla suorittamassa kerrallaan.

Pseudona tähän tapaan. jono on jaettu resurssi, joka voi olla enintään yhden säikeen hallussa kerrallaan (ainoastaan yksi säie saa olla suorituksessa kerrallaan synchronized-lohkon sisällä). Luonnollisesti odotus keskeyttää säikeen suorituksen ja sallii muiden säikeiden mennä kriittisen lohkon sisälle.

Jono jono;

Tuottajat:
tuota tehtävä
synchronized(jono) {
	lisää tehtävä jonoon
	kerro mahdollisille odottajille, että jonoon on tullut tehtävä
}

Kuluttajat:
synchronized(jono) {
	while (jonossa ei ole tehtäviä) {
		odota, kunnes tuottaja herättää
	}
	ota tehtävä jonosta
}
suorita tehtävä

Hyödyllistä luettavaa asian tiimoilta:
- Tuottaja-kuluttajaongelma (Producer-consumer problem): useita tuottajia ja kuluttajia käyttävät samaa jaettua puskuria.
- Säikeistystä Lazaruksella: http://wiki.freepascal.org/Multithreaded_Application_Tutorial
- Mutex (mutual exclusion)
- Monitor synchronization

Tuon "odota, kunnes tuottaja herättää" sijaan voisin pysäyttää säikeen kokonaan aina kun tehtävä on tehty, ilman vapauttamista. Tehtävän antaja saa käynnistää säikeen uudelleen itse. Luin että suspend/resume toiminta on nykyään "deprecated", joten Terminate/Start ajanee saman asian. Mietin vaan että onko se raskas operaatio, verrattuna silmukkaan joka ei tee mitään muuta kuin kysyy while-ehtoa. Tuo tehtävänjako-funktio voi käydä kertaalleen läpi kaikki työsäikeet funktion lopuksi, jotta failanneet kyselijätkin sais hommia heti jos niitä on. (Toisaalta ehkä joku toinen threadi voi lopettaa toimintansa juuri samaan aikaan ja jäädä ilman... Taas tilanne jolla tilastollinen todennäköisyys luokkaa 0.00000000001%)

edit: While työsäikeessä on parempi. Tosin se voisi pysäyttää säikeen Terminate:lla jos työjono on kokonaan tyhjä.

Saa nyt nähdä lähdenkö kirjottamaan koodin uusiks :p Ei ole enää niin yksinkertanen. Tuo nykynen versio ei ole toistaseks käyttänyt enempää kuin kahta säiettä muutenkaan. Toiseks, koko karttaa ladatessa ja tallentaessa en käytä säiettä. Mutta vastaisen varalle näitä on hyvä miettiä.