Go primeri iz konkurentnog programiranja – II deo
Sadržaj
Problem čitalaca i pisaca
Nakon što smo u prethodnom delu obradili osnovne mehanizme konkurentnosti jezika Go, sada ćemo rešiti jedan praktični problem. Problem čitalaca i pisaca je opštepoznat problem u računarskim naukama. U sistemu postoji veliki broj procesa koji dele zonu podataka i druge resurse sistema (fajl, blok glavne memorije, grupa registara procesora, …). Neki procesi samo čitaju podatke iz zone i oni se nazivaju čitaocima, dok drugi procesi samo upisuju u zonu podataka i oni se nazivaju piscima. Pri tome, postoje tri uslova koja moraju biti zadovoljena:
- Bilo koji broj čitalaca može istovremeno da čita podatak
- Samo jedan pisac može da upisuje podatak, u datom trenutku.
- Ukoliko pisac upisuje podatak, nijedan čitalac ne može da čita podatak.
Obradićemo dva rešenja ovog problema. Pervo rešenje daje prednost čitaocima, a drugo prednost daje piscima.
Čitaoci imaju prednost
Razmotrićemo dve varijante ovog rešenja. Prva koristi obične mutex-e i promenljive, dok druga varijanta koristi posebnu vrstu mutex-a, koji se zove RWMutex (Read Write Mutex), koji je ugrađen u paket Sync. RWMutex je specijalizovan za ovu vrstu problema i u pozadini radi isto što i prva varijanta, samo sa značajno manje koda, što olakšava posao programeru.
Varijanta 1
Na početku navedemo potrebne pakete i definišemo broj čitalca i pisaca, kao i maksimalno trajanje vremenskog intervala (koliko čitalac ili pisac mogu najduže pristupati podatku).
import (
"fmt"
"math/rand"
"sync"
"time"
)
const NUMBER_OF_READERS = 5
const NUMBER_OF_WRITERS = 5
const MAX_DURATION = 5
Zatim, definišemo globalne promenljive koje ćemo koristiti. Brojač čitalaca readcount, dva mutex-a: x i wsem, promenljivu data koju dele pisci i čitaoci i promenljivu group koja služi za sinhronizaciju.
var (
readcount = 0
x, wsem sync.Mutex
data int32
group sync.WaitGroup
)
Funkcija main postavlja vrednost data promenljive na 1, poziva funkcije readers i writers koje kreiraju čitaoce i pisce, čeka da oni završe i ispisuje konačnu vrednost promenljive data.
func main() {
rand.Seed(time.Now().UnixNano())
data = 1
readers()
writers()
group.Wait()
fmt.Println("Data: ", data)
}
Funkcije readers i writers kreiraju unapred definisan broj čitalaca i pisaca. Kreiraju ih pozivanjem anonimnih funkcija kao gorutine, odnosno kao zadatke koji mogu konkurentno da se izvršavaju. Anonimne funkcije sadrže mehanizme koji obezbeđuje da će tri uslova sa početka članka biti ispunjena.
func readers() {
for i := 1; i <= NUMBER_OF_READERS; i++ {
// reader goroutine
go func(i int) {
group.Add(1)
x.Lock()
readcount++
if readcount == 1 {
wsem.Lock()
}
x.Unlock()
read_unit(i)
x.Lock()
readcount--
if readcount == 0 {
wsem.Unlock()
}
x.Unlock()
group.Done()
}(i)
}
}
func writers() {
for i := 1; i <= NUMBER_OF_WRITERS; i++ {
//writer goroutine
go func(i int) {
group.Add(1)
wsem.Lock()
write_unit(i)
wsem.Unlock()
group.Done()
}(i)
}
}
Proces upisivanja koristi samo mutex wsem za sprovođenje međusobnog isključenja, kako ne bi mogla da se desi situacija da dva pisca pišu u isto vreme. Sve dok jedan pisac pristupa zoni deljenih podataka (kritična sekcija), nijedan drugi pisac ili čitalac ne mogu da joj pristupe. Proces čitanja takođe koristi wsem za sprovođenje međusobnog isključenja. Da bi se omogućilo da više čitalaca može da čita u isto vreme, potrebno je da prvi čitalac koji se pojavi sačeka na wsem ukoliko postoji pisac koji piše u tom trenutku. Ako ne postoji ili ako je izašao iz zone deljenih podataka, taj prvi čitalac zauzima wsem. Kada postoji barem jedan čitalac koji čita, čitaoci koji dolaze ne moraju da čekaju na ulazak. Takođe, kada poslednji čitalac završi sa čitanjem, on otpušta mutex wsem. Globalna promenljiva readcount se koristi za praćenje broja čitalaca, a mutex x se koristi za obezbeđivanje ispravnog ažuriranja promenljive readcount.
U svojoj kritičnoj sekciji, čitalac poziva funkciju read_unit, koja ispisuje pročitan podatak i poziva sleep. Sleep simulira izvršavanje zadataka različitih trajanja i na taj način imitira dešavanja u nekom realnom sistemu. Na kraju, funkcija obaveštava o svom završetku. Na isti način je realizovana i funkcija write_unit, koju poziva pisac u svojoj kritičnoj sekciji, samo što ona menja vrednost promenljive data.
func read_unit(i int) {
n := rand.Intn(MAX_DURATION) + 1
fmt.Println("Reader #", i, " read: ", data, " and sleep for: ", n, " seconds")
time.Sleep(time.Duration(n) * time.Second)
fmt.Println("Reader #", i, " finished")
}
func write_unit(i int) {
data = rand.Int31n(10)
n := rand.Intn(MAX_DURATION) + 1
fmt.Println("Writer #", i, " wrote: ", data, " and sleep for: ", n, " seconds")
time.Sleep(time.Duration(n) * time.Second)
fmt.Println("Writer #", i, " finished")
}
Varijanta 2
Postavka druge varijante se ne razlikuje mnogo od prve. Potreban nam je jedan RWMutex, koji smo nazvali mutex i potrebno je da prilagodimo funkcije readers i writers.
var (
mutex sync.RWMutex
data int32
group sync.WaitGroup
)
Funkcija readers je izmenjena tako da kada čitalac želi da pristupi kritičnoj sekciji, poziva funkciju RLock. Ako postoji neki pisac koji je u kritičnoj sekciji, čitalac će morati da sačeka da on izađe. Kada pisac izađe, čitalac će moći da pristupi kritičnoj sekciji, kao i ostali čitaoci. Kada napusti kritičnu sekciju, čitalac poziva funkciju RUnlock, koja oslobađa mutex.
func readers() {
for i := 1; i <= NUMBER_OF_READERS; i++ {
// reader goroutine
go func(i int) {
group.Add(1)
mutex.RLock()
read_unit(i)
mutex.RUnlock()
group.Done()
}(i)
}
}
Isto važi kada su u pitanju pisci. Oni pozivaju funkcije Lock i Unlock. Te specijalne funkcije obezbeđuju ekskluzivan pristup kritičnoj sekciji. Pisac čeka na svoj red za ulazak, a kada uđe, niko drugi ne može da pristupi dok on ne izađe.
func writers() {
for i := 1; i <= NUMBER_OF_WRITERS; i++ {
// writer goroutine
go func(i int) {
group.Add(1)
mutex.Lock()
write_unit(i)
mutex.Unlock()
group.Done()
}(i)
}
}
Rezultat izvršavanja
user@users-MacBook-Pro examples % go run readers_writers_r_priority.go
Reader # 4 read: 1 and sleep for: 5 seconds
Reader # 1 read: 1 and sleep for: 2 seconds
Reader # 2 read: 1 and sleep for: 1 seconds
Reader # 3 read: 1 and sleep for: 5 seconds
Reader # 5 read: 1 and sleep for: 4 seconds
Reader # 2 finished
Reader # 1 finished
Reader # 5 finished
Reader # 3 finished
Reader # 4 finished
Writer # 5 wrote: 6 and sleep for: 2 seconds
Writer # 5 finished
Writer # 2 wrote: 0 and sleep for: 4 seconds
Writer # 2 finished
Writer # 3 wrote: 1 and sleep for: 4 seconds
Writer # 3 finished
Writer # 4 wrote: 2 and sleep for: 2 seconds
Writer # 4 finished
Writer # 1 wrote: 9 and sleep for: 5 seconds
Writer # 1 finished
Data: 9
Kada jedan čitalac počne pristup zoni podataka, moguće je da čitaoci preuzmu kontrolu nad zonom podataka sve dok postoji barem jedan čitalac koji čita. Zbog toga, može doći do gladovanja pisaca.
Pisci imaju prednost
Sada želimo da napravimo rešenje koje će favorizovati pisce u odnosu na čitaoce.
var (
readcount = 0
writecount = 0
x, y, z, wsem, rsem sync.Mutex
data int32
group sync.WaitGroup
)
U odnosu na prvu varijantu primera, gde čitaoci imaju prednost, za pisce je potrebno dodati mutex rsem, koji sprečava sve čitaoce dok postoji barem jedan pisac koji želi da pristupi zoni podataka. Potrebno je dodati promenljivu writecount koja upravlja podešavanjem mutex-a rsem, i mutex y koji upravlja ažuriranjem promenljive writecount. Za čitaoce je potrebno dodati još jedan mutex jer se ne sme dozvoliti stvaranje dugačkog reda na mutex-u rsem. U suprotnom pisci neće moći da uskoče u red. Zbog toga, samo jedan čitalac može biti u redu za mutex rsem, a ostali čitaoci ulaze u red za mutex z.
func readers() {
for i := 1; i <= NUMBER_OF_READERS; i++ {
// reader goroutine
go func(i int) {
group.Add(1)
z.Lock()
rsem.Lock()
x.Lock()
readcount++
if readcount == 1 {
wsem.Lock()
}
x.Unlock()
rsem.Unlock()
z.Unlock()
read_unit(i)
x.Lock()
readcount--
if readcount == 0 {
wsem.Unlock()
}
x.Unlock()
group.Done()
}(i)
}
}
func writers() {
for i := 1; i <= NUMBER_OF_WRITERS; i++ {
// writer goroutine
go func(i int) {
group.Add(1)
y.Lock()
writecount++
if writecount == 1 {
rsem.Lock()
}
y.Unlock()
wsem.Lock()
write_unit(i)
wsem.Unlock()
y.Lock()
writecount--
if writecount == 0 {
rsem.Unlock()
}
y.Unlock()
group.Done()
}(i)
}
}
Razmotrimo sada različite situacije koje mogu da se dese prilikom izvršavanja.
| Samo čitaoci u sistemu |
|
| Samo pisci u sistemu |
|
| I čitaoci i pisci, prvo čitanje |
|
| I čitaoci i pisci, prvo pisanje |
|
Rezultat izvršavanja
user@users-MacBook-Pro examples % go run readers_writers_w_priority.go
Reader # 1 read: 1 and sleep for: 3 seconds
Reader # 1 finished
Writer # 5 wrote: 3 and sleep for: 1 seconds
Writer # 5 finished
Writer # 1 wrote: 4 and sleep for: 1 seconds
Writer # 1 finished
Writer # 2 wrote: 3 and sleep for: 3 seconds
Writer # 2 finished
Writer # 3 wrote: 1 and sleep for: 3 seconds
Writer # 3 finished
Writer # 4 wrote: 2 and sleep for: 4 seconds
Writer # 4 finished
Reader # 5 read: 2 and sleep for: 2 seconds
Reader # 2 read: 2 and sleep for: 1 seconds
Reader # 3 read: 2 and sleep for: 3 seconds
Reader # 4 read: 2 and sleep for: 4 seconds
Reader # 2 finished
Reader # 5 finished
Reader # 3 finished
Reader # 4 finished
Data: 2
Prilikom pokretanja programa dobili smo treći slučaj iz tabele iznad. U sistemu se prvo pojavio čitalac koji je postavio mutex wsem. U međuvremenu se pojavljuje pisac koji postavlja mutex rsem i da bi ušao u svoju kritičnu sekciju mora da sačeka da čitalac otpusti wsem. Kada dođu ostali čitaoci, jedan od njih će se blokirati na semaforu rsem, a ostali će napraviti red ispred semafora z, dok svi ostali pisci prave red ispred wsem. Kada prvi čitalac završi sa radom, na red dolaze pisci i nijedan čitalac neće moći da dođe na red sve dok poslednji pisac ne otpusti semafor rsem. Na ovaj način smo dali prednost piscima.
Zaključak
U ova dva članka smo pokušali da spojimo lepo i korisno. Videli smo kako se postiže konkurentnost i koje mehanizme konkurentnossti nam pruža programski jezik Go. To smo iskoristili da uradimo par osnovnih primera, ali i da obradimo problem čitalaca i pisaca. Ovaj problem predstavlja osnovu u izučavanju konkurentnosti u računarskim naukama, pogotovu u oblastima kao što su operativni sistemi i baze podataka.
Korisni linkovi
- https://github.com/nikolabojovic97/Go-Concurrent-Programming-Examples
- https://sr.wikipedia.org/sr-el/Problem_čitalaca_i_pisaca
- https://golang.org/pkg/sync/#Mutex
- https://golang.org/src/sync/rwmutex.go
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.
