Konkurentnost jezika Go – II deo

U prvom delu opisali smo osnovne koncepte konkurentnosti jezika Go. U ovom delu ćemo proučiti naprednije koncepte konkurentnosti koji regulišu sinhronizaciju među nitima. U zavisnosti od problema koji rešavate, često može biti potrebno da više niti pristupa deljenim resursima. U takvim situacijama mogu nastati problemi kao što su stanje trke, uzajamna blokada ili gladovanje. Kako bismo smanjili šanse da dođe do navedenih problema, programski jezik Go uvodi jednu novinu koja omogućava nitima da međusobno dele resurse, pomoću tzv. kanala.

Kanali

Kanali, kako sama reč kaže, omogućavaju razmenu podataka između niti pomoću operatora <-

ch <- value // prosleđujemo value kanalu ch
v := <- ch // dobijamo podatak iz kanala i dodeljujemo vrednost promenljivoj

Logično, razmena podataka se odvija u smeru strelice. Kako bismo uopšte mogli da koristimo neki kanal, potrebno je da ga kreiramo pomoću ključne reči make i da naznačimo tip podataka koji će se razmenjivati.

ch := make(chan int)

Strana koja treba da primi podatak čeka sve dok se podatak ne pošalje. Ovaj princip omogućava sinhronizaciju između niti bez semafora ili kondicionih varijabli, kako se to radilo u programskom jeziku kao što je C.

package main

import "fmt"

func sum(s []int, c chan int) {
    sum := 0
    for _, v := range s {
        sum += v
    }
    c <- sum // šaljemo sumu kanalu c
}

func main() {
    s := []int{7, 2, 8, -9, 4, 0}

    c := make(chan int)
    go sum(s[:len(s)/2], c)
    go sum(s[len(s)/2:], c)
    x, y := <-c, <-c // dobijamo rezultate funkcija kroz kanal c

    fmt.Println(x, y, x+y)
}

Rezultat izvršenja programa je -5 17 12.

U prethodnom primeru videli smo kako neki proračun možemo podeliti na više niti, i kako se tek nakon završetka njihovih pojedinačnih proračuna računa konačni rezultat. Analogno prethodnom primeru možemo napisati program koji aproksimira vrednost broja π pomoću metode Monte Carlo.

Monte Carlo metoda radi po principu uzorkovanja. Za rešavanje problema približnog određivanja broja π koristićemo kvadrat i krug upisan u njega. Ukoliko je poluprečnik kruga r, stranica kvadrata je 2r, dakle površina kvadrata je 4r2, dok je površina kruga upisanog u kvadrat r2π. Kako ne znamo površine, moraćemo da ih aproksimiramo nasumičnim izborom tačaka. Nakon n iteracija, odnos ukupnog broja tačaka i broja tačaka u krugu biće jednak približnom odnosu površina, odakle možemo izračunati vrednost π.

package main
 
import (
    "fmt"
    "time"
    "math/rand"
)
 
const n = 1000000 // broj uzoraka po niti
const t = 16 // broj niti
 
func work(c chan float64) { // funkcija koja računa broj π
    s := rand.NewSource(time.Now().UnixNano())
    r := rand.New(s)
    cn := 0
    for i:= 0; i < n; i++{
        x:= r.Float64()
        y:= r.Float64()
       
        if x*x + y*y <= 1{
            cn++
        }
    }
    c <- float64(4) * float64(cn) / float64(n)
}
 
func main() {
    c := make(chan float64)
    var sum float64 = 0
    for i:= 0; i < t; i++{
        go work(c) // startovanje niti
    }
    for i:= 0; i < t; i++{
        sum += <- c // sumiranje rezultata niti
    }
    fmt.Println(sum / t)   // konačni račun
}

Rezultat izvršenja programa je sledeći

3.14159275

Na ovom primeru možemo odlično videti kako, ukoliko na raspolaganju imamo više procesorskih jezgara, možemo rasporediti posao na više niti i dobiti na brzini, ili povećati broj uzoraka i dobiti na tačnosti za isto vreme. Sada ćemo izvršiti testiranje gde ćemo u prvom primeru ceo posao dodeliti jednoj niti, dok ćemo u drugom primeru ukupan broj uzoraka ravnomerno rasporediti na četiri niti. Rezultat testiranja je sledeći:

Real predstavlja stvarno vreme izvršavanja, od pokretanja programa do samog kraja. To uključuje i procesorsko vreme korišćeno od strane drugih procesa i vreme koje je proces proveo u blokadi. Sa druge strane, user predstavlja samo procesorko vreme koje je proces koristio u izvršavanju. Ukoliko je izvršavanje procesa podeljeno na više niti, user predstavlja zbirno vreme izvršavanja svih niti na svim procesorskim jedinicama. Iz priloženog primera možemo videti da smo podelom procesa na četiri niti dobili ubrzanje od skoro četiri puta!

Kanali sa baferom

Ukoliko postoji potreba da kroz neki kanal pošaljemo više podataka, možemo koristiti kanal sa baferom. Sve što treba da uradimo jeste da prilikom kreiranja kanala naznačimo veličinu bafera.

ch := make(chan int, 100)

Kod korišćenja kanala sa baferom treba voditi računa da ne prepunite bafer.

package main

import "fmt"

func main() {
    ch := make(chan int, 2)
    ch <- 1
    ch <- 2
    //ch <- 3 ukoliko otkomentarišemo liniju dobićemo grešku jer smo prepunili bafer
    fmt.Println(<-ch, <-ch)
}

Rezultat izvršenja ovog programa je 1 2.

Naredba Select

Select naredba omogućava niti da osluškuje na više kanala. Program se blokira sve dok neki od kanala nije spreman, nakon čega se preuzimaju podaci sa kanala koji je spreman. Ukoliko je više kanala spremno, kanal se bira metodom slučajnog izbora.

package main

import (
    "fmt"
    "time"
)

func main() {
    c1 := make(chan string) // kreiramo dva kanala
    c2 := make(chan string) // kroz koje će se prenositi podaci tipa string
    
    go fun1(c1) // startujemo
    go fun2(c2) // niti
    
    select{ // select naredba koja osluškuje na dva kanala
        case s1:= <- c1: // slučaj da podatak prvo pristigne sa kanala c1
            fmt.Println(s1)
        case s2:= <- c2: // slučaj da podatak prvo pristigne sa kanala c2
            fmt.Println(s2)
    }
}

func fun1(ch chan string){
    time.Sleep(2 * time.Second)
    ch <- "first function"
}

func fun2(ch chan string){
    time.Sleep(1 * time.Second)
    ch <- "second function"
}

Rezultat izvršenja programa će biti second function, nakon čega se završava program.

Ekskluzivni pristup resursima

Iako su kanali odličan vid komunikacije između niti, ne treba ih koristiti po svaku cenu. Šta ako nam komunikacija uopšte nije potrebna? Šta ako želimo da se osiguramo da samo jedna nit može pristupiti nekoj promenljivoj u određenom vremenskom trenutku? Kod razvoja konkurentnih programa, veoma je bitno osigurati ovakve situacije, kako bismo izbegli stanje trke. Do stanja trke može doći ukoliko više niti pristupa istoj kritičnoj sekciji istovremeno. Princip uzajamnog isključivanja nam omogućava da sprečimo stanje trke. Najjednostavnija struktura koji nam omogućava uzajamno isključivanje jeste mutex (skraćeno od mutual exclusion), binarni semafor, koji može biti otključan ili zaključan. Paket sync nam pruža strukturu Mutex sa svoje dve metode, Lock i Unlock.

Problem filozofa na večeri

null

Jedan od najpoznatijih problema konkurentnog programiranja jeste svakako problem filozofa na večeri. Prvi ga je izložio Dijkstra 1965. godine. Ovaj problem je važan jer odslikava osnovne probleme uzajamnog blokiranja i gladovanja. Pet filozofa živi u kući, gde je za njih postavljen sto. Život svakog filozofa se svodi na razmišljanje i ishranu. Svi filozofi su se složili da su špageti jedina hrana koja im pomaže pri razmišljanju. Zbog nedostatka veštine, svakom filozofu su potrebne dve viljuške kako bi jeo špagete. Potrebno je simulirati ritual koji će omogućti filozofima da jedu. Algoritam mora zadovoljiti uzajamno isključenje (dva filozofa ne mogu koristiti u isto vreme istu viljušku) i mora se izbeći uzajamno blokiranje i gladovanje. Uzajamno blokiranje može nastati, na primer, kada svaki filozof uzme viljušku sa svoje leve strane. Kada posegne za desnom, javlja se tzv. kružno čekanje i nastaje blokada. Jedno od mogućih rešenja:

package main
 
import(
    "fmt"
    "sync"
    "time"
    "math/rand"
)
 
const n = 5 // broj filozofa
var mutex sync.Mutex
var wg sync.WaitGroup
var sticks [n]int // pomoćni niz za sinhronizaciju
 
func getLeftIndex(i int) int{ // funkcija koja vraća indeks leve viljuške iz pomoćnog niza
    if i == 0 {
        return n - 1
    }else{
        return i - 1
    }
}
 
func getRightIndex(i int) int{ // funkcija koja vraća indeks desne viljuške iz pomoćnog niza
    if i == n - 1 {
        return 0
    }else{
        return i + 1
    }  
}
 
func doWork(i int){
    id:= i
   
    for{
        fmt.Printf("Filozof %d misli\n",id)
        time.Sleep(2 * time.Second)
       
        for{
            mutex.Lock() // zaključavamo muteks kako bi obezbedili kritičnu sekciju
           
            if sticks[id] == 2 { // ukoliko imamo viljuške na raspolaganju
                sticks[getLeftIndex(id)]-- // smanjujemo njihov broj
                sticks[getRightIndex(id)]-- // kako bi onemogućili druge da to urade
               
                mutex.Unlock() // otključavamo muteks i napuštamo kritičnu sekciju
               
                fmt.Printf("Filozof %d jede\n",id)
                time.Sleep(1 * time.Second)
               
                mutex.Lock() // zaključavamo mutex kako bi obezbedili kritičnu sekciju
               
                sticks[getLeftIndex(id)]++ // uvećavamo stanje viljuški
                sticks[getRightIndex(id)]++ // kako bi drugi filozofi mogli da im pristupe
               
                mutex.Unlock() // otključavamo muteks i napuštamo kritičnu sekciju
                break              
            }else{
                mutex.Unlock() // ukoliko nismo imali viljuške na raspolaganju otključavamo muteks
                time.Sleep(time.Duration(rand.Intn(n)) * time.Second) // i pauziramo određeno vreme
            }
        }
    }
}
 
func main(){
 
    for i:= 0; i < n; i++{
        sticks[i] = 2 // postavljamo početne vrednosti pomoćnog niza
    }
    wg.Add(1)
    for i:= 0; i < n; i++{
        go doWork(i) // startujemo niti
    }
    wg.Wait()
}

Primer izvršavanja simulacije:

Filozof 4 misli
Filozof 0 misli
Filozof 1 misli
Filozof 2 misli
Filozof 3 misli
Filozof 0 jede
Filozof 3 jede
Filozof 3 misli
Filozof 0 misli
Filozof 4 jede
Filozof 1 jede
Filozof 4 misli
Filozof 1 misli
Filozof 3 jede
Filozof 0 jede

U prethodnim primerima videli smo kako možemo razvijati konkurentne programe u jeziku Go. Naravno, pisanje programa i razvoj aplikacija obuhvata mnogo širu sliku. Programski jezik Go nije savršen. Jedan od glavnih nedostataka jeste nepodržavanje generičkog programiranja. Takođe, koncept objektno-orijentisanog programiranja se u izvesnoj meri razlikuje od nekih tradicionalnih jezika kao što su Java, C# ili C++. Kao relativno mlad jezik, još uvek nema razvijen veliki broj biblioteka koje bi programeru pružile podršku u raznim sferama primene.

Zaključak

Videli smo da je Google-ov tim dok je razvijao programski jezik Go obratio posebnu pažnju na konkurentnost. U ovom članku mogli ste se upoznati sa osnovnim principima konkurentnosti jezika Go. Videli smo da je pisanje konkurentnih programa u jeziku Go jako jednostavno i da raspolaže određenim svojstvima kojima drugi jezici ili biblioteke ne raspolažu. Sledećeg puta kada budete razvijali aplikaciju koja zahteva konkurentno izvršavanje, uzmite u obzir korišćenje jezika Go.

Korisni linkovi

Autor: Nikola Pajovic

Student četvrte godine osnovnih studija informatike na Prirodno-matematičkom fakultetu u Kragujevcu.

Tokom studija bio je polaznik programa praksi u kompanijama Comtrade i Quantox Technology.

Nikola Pajovic

Student četvrte godine osnovnih studija informatike na Prirodno-matematičkom fakultetu u Kragujevcu. Tokom studija bio je polaznik programa praksi u kompanijama Comtrade i Quantox Technology.