Go primeri iz konkurentnog programiranja – I deo

U seriji od dva članka ćemo obraditi osnovne principe konkurentnog programiranja u programskom jeziku Go. Prvi deo se osvrće na pojmove konkurentnosti i paralelizma, kao i na dva demonstrativna primera u kojima se prikazuje upotreba osnovnih mehanizama za postizanje konkurentnosti u Go-u, dok će drugi deo biti posvećen klasičnom problemu čitalaca i pisaca.

Link sa koga možete preuzeti primere: Go-Concurrent-Programming-Examples. Ohrabrujem sve čitaoce da preuzmu primere i sami isprobaju, naprave neke izmene i uporede rezultate.

Konkurentno programiranje

Konkurentnost kao pojam u računarskim naukama je osobina koja se kosi sa tradicionalnim, sekvencijalnim pristupom u programiranju i izvršavanju programa. Konkurentnost je sposobnost da se program ili algoritam razbije na delove koji mogu nezavisno da se izvršavaju. Rezultat izvršenja programa je uvek isti, bez obzira da li on koristio sekvencijalni ili konkurentan pristup. Konkurentan pristup nam omogućava da postignemo iste rezultate za kraći vremenski rok, poboljšamo performanse i efikasnost programa.

go concurrent programming

Sa benefitima koje donosi konkurentno programiranje, dolazi i velika odgovornost. Treba imati na umu da program razbijamo na delove koji će se ponašati kao zasebni procesi u sistemu. Ti procesi će deliti resurse (memoriju, U/I uređaje, itd.). Neki procesi će zavisiti od drugih procesa, pa je zbog toga na programeru da pomoću različitih mehanizama kao što su semafori, obezbedi ispravno upisivanje i čitanje u deljenu memoriju i spreči probleme kao što su gladovanje i uzajamna blokada.

Konkurentnost i paralelizam

Koncept konkurentnosti se često meša sa konceptom paralelizma i obrnuto. Kod paralelnog programiranja, najčešći problem je ubrzanje zahtevnih izračunavanja koja se javljaju kod računarskih simulacija (vremenska prognoza, simulacije ponašanja nekih materijala pod određenim uslovima, itd.). Ubrzanje se postiže tako što se jedan program pokreće na više različitih procesora u nekom višeprocesorskom sistemu. Svaka instanca programa ponaša se kao zaseban proces, koja je odgovorna za svoj deo posla. Procesi međusobno komuniciraju preko interfejsa za razmenu poruka (npr. MPI – Message Passing Interface), koji služi za upravljanje komunikacijama izmedju procesa i za njihovu sinhronizaciju.

go concurrent programming

Paralelno izvršavanje nije moguće u sistemu sa jednim procesorom, jer nije moguće preklapanje procesa tj. izvršavanje više procesa na jednom procesoru. Nasuprot paralelizmu, konkurentni procesi mogu da se prepliću tokom izvršavanja i na taj način se stiče utisak istovremenog rada. Zbog toga, procesi mogu podjednako da napreduju sa svojom obradom u sistemu sa jednim procesorom.

Konkurentnost u Go programskom jeziku

Pored Go-a, u većini viših programskih jezika konkurentnost se postiže na nivou niti. Konkurentnost u Go-u je sposobnost da se više funkcija izvršava nezavisno jedna od druge. Takva funkcija se naziva gorutina i ona je u osnovi pojednostavljena nit, koja je veoma jeftina sa stanovišta potrošnje resursa. Kada se funkcija pokrene kao gorutina, ona se tretira kao nezavisna jedinica posla koja će se rasporediti i izvršiti na nekom logičkom procesoru. Go raspoređivač je zadužen za preslikavanje logičkih procesa u niti operativnog sistema, na kojima će se gorutine izvršavati. Da bi gorutine mogle međusobno da komuniciraju, koriste se kanali. Kroz kanal gorutine mogu da šalju i primaju podatke u vidu strukturiranih poruka.

go concurrent programming

Cevovod (Pipeline)

Primer cevovoda će nam pomoći da razumemo koncept gorutina i kanala.

Pipeline ili cevovod je koncept koji se svakodnevno sreće u računarstvu, ali i u realnom životu. Taj koncept je zamišljen tako da se neki posao podeli u etape ili nivoe. Svaka etapa ima svoju ulogu u obradi i izlaz jedne etape predstavlja ulaz u sledeću. Najčešća analogija koja se koristi je proizvodnja automobila.

Zamislimo da se proizvodnja autmobila sastoji od ugradnje motora koja traje 20 minuta, ugradnje enterijera koja traje 15 minuta i monitaranja točkova za šta treba 10 minuta. Kada bi za sve to bila zadužena jedna stanica u proizvodnji, ona bi proizvodila jedan automobil za upupno 45 minuta. Ali, ako u fabriku instaliramo jednu proizvodnu traku na kojoj se nalaze tri stanice, gde prva ugrađuje motor u šasiju, druga ugrađuje enterijer i treća montira točkove, da li nam za proizvodnju jednog automobila treba 45 minuta? Šta smo onda time dobili? Tačno je da za proizvodnju jednog autmobila treba 45 minuta, ali sa trake će na svakih 20 minuta silaziti novi automobil. Čim se u prvu šasiju ugradi motor, traka se pomera, šasija dolazi na deo za ugradnju enterijera, a na traku može da se donese nova šasija u koju će krenuti da se ugrađuje motor.

Sada kada smo to malo pojasnili, pogledaćemo primer koji kvadrira brojeve i koji se sastoji od tri nivoa.

Prvi nivo, gen, predstavlja funkciju koja prima listu parametara int tipa i vraća kanal istog tipa. Funkcija gen pokreće anonimnu funkciju kao gorutinu. Funkcija se pokreće kao gorutina uz pomoć ključne reči go. Gorutina upisuje argumente funkcije gen u odlazni kanal out. Kada završi sa upisivanjem, zatvara kanal.

func gen(nums ...int) <-chan int {
    out := make(chan int)
    go func() {
        for _, x := range nums {
            out <- x
        }
        close(out)
    }()
    return out
}

Drugi nivo, sq, je funkcija koja prima promenljive int tipa kroz kanal koji je prosleđen kao argument funkcije, pa pokreće anonimnu funkciju kao gorutinu. Ta funkcija čita int promenljive, kvadrira ih i upisuje u odlazni kanal out sve dok se ne zatvori dolazni kanal in. Kada se on zatvori, to označava da su sve vrednosti primljene i da neće biti novih. Kada gorutina unutar funkcije sq pošalje poslednji kvadrirani broj, ona će zatvoriti svoj izlazni kanal out.

func sq(in <-chan int) <-chan int {
    out := make(chan int)
    go func() {
        for x := range in {
            out <- x * x
        }
        close(out)
    }()
    return out
}

Poslednji nivo predstavlja main funkcija koja pokreće pipeline, pozivajući funkciju sq koja kao argument prima rezultat funkcije gen kada se njoj proslede vrednosti 2, 3, 4 i 5. Main nakon toga prima kvadrirane vrednosti i ispisuje ih na ekran.

func main() {
    for x := range sq(gen(2, 3, 4, 5)) {
        fmt.Println(x)
    }
}

Rezultat izvršavanja

user@users-MacBook-Pro examples % go run pipeline.go
4
9
16
25

Lookup zahtevi

Za kraj ćemo uporediti dva jednostavna praktična primera. Prvi predstavlja tradicionalni, sekvencijalni pristup, dok drugi predstavlja konkurentni pristup. U oba slučaja želimo da pošaljemo niz „lookup“ zahteva, koji su u stvari najobičniji HTTP GET zahtevi. U prvom primeru, zahteve šaljemo sekvencijalno tj. šaljemo prvi, čekamo da stigne odgovor, pa šaljemo drugi i tako dok ne pošaljemo sve zahteve. Kod drugog primera, svaki zahtev ćemo pokrenuti kao gorutinu, odnosno kao zasebne niti koje mogu konkurentno da se izvršavaju. Izmerićemo vremena koja su bila potrebna za izvršenje pojedinačnih zahteva, kao i ukupno vreme izvršavanje programa.

Sekvencijalni pristup

Na početku uvozimo potrebne pakete i definišemo URL adrese kojima ćemo poslati zahteve.

import (
    "fmt"
    "net/http"
    "time"
)

var URLS = [...]string{
    "https://www.google.com/",
    "https://www.bing.com/",
    "https://www.youtube.com/",
}

U main funkciji pored ispisa, merimo vreme potrebno da se program izvrši, jedna for petlja prolazi kroz sve URL adrese i poziva funkciju lookup_seq. Ona šalje HTTP GET zahtev i meri vreme od trenutka slanja do trenutka primanja odgovora i to ispisuje na ekran.

func lookup_seq(url string) {
    start := time.Now()      
    http.Get(url)             
    end := time.Now()       
    duration := end.Sub(start)
    fmt.Println(url, "time: ", duration)
}

func main() {
    fmt.Println("Sequential time tracking...")
    start := time.Now() 

    for _, url := range URLS {
        lookup_seq(url)
    }

    end := time.Now()         
    duration := end.Sub(start) 
    fmt.Println("Sequential execution: ", duration)
}

Konkurentni pristup

Naredni primer je gotovo identičan prethodnom primeru, sem kanala koji smo dodali kako bismo znali kada su sve gorutine završile sa radom. Kanal kreiramo kao kanal za slanje bool vrednosti, koji je baferovanog tipa tj. ima svoju dužinu i ponaša se kao bafer. Njegova dužina će biti ista kao i dužina niza URLS.

var URLS = [...]string{
    "https://www.google.com/",
    "https://www.bing.com/",
    "https://www.youtube.com/"
}

var channel = make(chan bool, len(URLS))

Funkciju lookup_seq ćemo zameniti istom funkcijom drugog imena, lookup_con. Jedina razlika između ove dve funkcije je u tome što lookup_con upisuje true u kanal kada završi sa obradom zahteva.

func lookup_con(url string) {
    start := time.Now()        
    http.Get(url)              
    end := time.Now()          
    duration := end.Sub(start) 
    channel <- true            
    fmt.Println(url, "time: ", duration)
}

Funkciju lookup_con pokrećemo kao gorutinu u main funkciji. Nakon toga imamo jednu for petlju u kojoj čitamo vrednosti iz kanala. Iz kanala želimo da pročitamo onoliko vrednosti koliko šaljemo zahteva. Pošto je čitanje iz kanala blokirajuća operacija, main funkcija neće moći da nastavi dok svi zahtevi ne budu obrađeni.

func main() {
    fmt.Println("Concurrent time tracking...")
    start := time.Now() 

    for _, url := range URLS {
        go lookup_con(url)
    }

    for i := 0; i < len(URLS); i++ { 
        <-channel
    }

    end := time.Now()          
    duration := end.Sub(start) 
    fmt.Println("Concurrent execution: ", duration)
}

Rezultat izvršavanja

user@users-MacBook-Pro examples % go run lookup_sequential.go
Sequential time tracking...
https://www.google.com/ time:  428.207136ms
https://www.bing.com/ time:  320.21381ms
https://www.youtube.com/ time:  309.863884ms
Sequential execution:  1.058362055s
user@users-MacBook-Pro examples % go run lookup_concurrent.go
Concurrent time tracking...
https://www.youtube.com/ time:  416.746641ms
https://www.google.com/ time:  416.823749ms
https://www.bing.com/ time:  504.166452ms
Concurrent execution:  504.246784ms

Kao što smo očekivali, vreme koje je potrebno da se izvrše svi zahtevi sekvencijalno, jednako je sumi pojedinačnih vremena izvršavanja zahteva, dok je kod konkurentnog slanja zahteva ukupno vreme izvršavanja približno vremenu zahteva koji je najduže trajao. Možemo uočiti i redosled izvršavanja zahteva. Sekvencijalni pristup je ispoštovao redosled definisan u kodu, dok su kod konkurentnog zahtevi uređeni u rastućem poretku trajanja izvršenja pojedinačnih zahteva.

Iako su se dva zahteva izvršavala duže kod konkurentnog pristupa nego kod sekvencijalnog, dok je samo jedan bio brži, postigli smo ubrzanje malo veće od dva puta za samo tri zahteva.

Eksperimentalno ćemo poslati pedeset pojedinačnih zahteva, najposećenijim sajtovima na svetu u trenutku pisanja članka (izvor https://www.similarweb.com/top-websites/) i uporediti rezultate.

Sequential execution: 35.64911537s

https://www.rakuten.co.jp/ time: 5.604411745s
Concurrent execution: 5.605023524s

Sekvencijalnom pristupu je trebalo 35,6 sekundi, a konkurentnom samo 5,6 sekundi. Ovaj put smo ostvarili ubrzanje malo veće od šest puta za pedeset zahteva. I ponovo je vreme konkurentnog izvršavanja približno najdužem izvršavanju pojedinačnih zahteva.

Napomena

Prilikom isprobavanja ovog primera preporučuje se pokretanje programa nekoliko puta i upoređivanje rezultata. Takođe je potrebna stabilna internet konekcija, pošto to može uticati na rezultat izvršavanja.

Šta nas očekuje u drugom delu

U drugom delu nas očekuje jedan od najčešćih problema u oblasti konkurentnog programiranja, problem čitalaca i pisaca. Rešićemo ovaj problem na više načina, videćemo prednosti i mane pojedinačnih rešenja. Takođe, videćemo koji mehanizam nam Go omogućava za rešavanje ovog problema.

Korisni linkovi

Autor: Nikola Bojovic

Student informatike na Prirodno-matematičkom fakultetu u Kragujevcu.

Polaznik Edit letnje škole programiranja i različitih radionica iz oblasti preduzetništva kao što su Business Youth Forum, StartupDrill i Startapidemija.

Nikola Bojovic

Student informatike na Prirodno-matematičkom fakultetu u Kragujevcu. Polaznik Edit letnje škole programiranja i različitih radionica iz oblasti preduzetništva kao što su Business Youth Forum, StartupDrill i Startapidemija.