Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web servers, web development, networking and security services. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Bell laboratorije i CSP teme


Uvod

Ova strana predstavlja deo istorije paralelnog programiranja, sa fokusom na jednu osobitu vrstu Hoareovog jezika za komunikaciju sekvencijalnih procesa (CSP)(1)(1a). Paralelno programiranje, na ovaj način, je zanimljivo ne sa aspekta efikasnosti, već jasnoće. To jest, često se greši, smatrajući da je jedini značaj paralelnog programiranja, poboljšanje performansi, npr., zahteva za preklapanje I/O na disku, smanjivanje čekanja unapred datim odgovorima na očekivana pitanja, ili korišćenje prednosti više procesora. Te prednosti jesu važne, ali nisu relevantne za ovu diskusiju. Na kraju krajeva, mogu se ostvariti na druge načine, kao što je asinhrono event-driven programiranje. Umesto toga, zanimamo se za paralelno programiranje zato što omogućuje prirodnu apstrakciju, koja neke programe može učiniti znatno jednostavnijim.

Šta sve ovo znači

Većina studenata informatike prisiljena je da čita "Uvod u programiranje sa temama" Andrew Birell-a.Model SRC tema upotrebljen je u većini trenutno raspoloživih paketa tema. Problem sa svim ovim je taj što su na suviše niskom nivou. Za od primitivne komunikacije koju obezbeđuje Hoare, primitivnosti u SRC načinu sastavljanja modula moraju se kombinovati sa ostalim tehnikama, obično podeljenom memorijom, radi efektne upotrebe. Sve u svemu, programeri se ne mogu baviti sopstvenim konstrukcijama višeg nivoa, već ostaju isfrustrirani potrebom da obraćaju pažnju na tako nevažne detalje.

Izbacite za trenutak Birellov tutorijal iz glave. Ovo je drugačija tema modela. Ukoliko joj priđete kao drugačijoj temi modela, uskoro bi je mogli smatrati jednostavnijom za razumevanje.

Komunikacija sekvencijalnih procesa

Od 1978. predlagane su mnoge metode u cilju komunikacije i sinhronizacije u kontekstu programiranja multiprocesora. Podeljena memorija bila je najčešći mehanizam za komunikaciju, a semafori, kritične regije i monitori bili su među mehanizmima za sinhronizaciju. C:A:R: Hoare je oba slučaja označio jednom prostom jezičkom naredbom: Sinhrona komunikacija. U Hoareovom CSP jeziku, procesi međusobno komuniciraju slanjem i primanjem vrednosti kroz označene razbaferovane kanale. Budući da su kanali razbaferovani, šalji operacija se blokira dok se vrednosti prenose do risivera, što obezbeđuje mehanizam sinhronizacije.

Jedan od Hoareovih primera je reformisanje kartica sa 80 kolona, za štampanje na štampaču sa 125 kolona. Tako, jedan procesor čita samo jednu karticu, šaljući rastavljen sadržaj, karakter po karakter, drugom procesoru. Taj drugi procesor sastavlja grupe od pd 125 karaktera i šalje ih štampaču. Ovo zvuči prosto, ali odsustvu baferisanih I/O biblioteka, neophodno čuvanje, umešano u jednoprocesno rešenje, je tegobno. Zapravo, I/O biblioteke su ustvari samo objedinjene ove dve vrste procesa, koji izvoze jednokarakterni komunikaciju interfejsa.

Kao drugi primer, za koji Hoare ima da zahvali Doug Mcllroy-u, uzimamo u obzir sakupljanje svih prostih brojeva, manjih od hiljadu. Erastotenovo sito se može simulirati cevovodom procesa koji izvršavaju sledeći pseudokod:
p = get a number from left neighbor
print p
loop:
    n = get a number from left neighbor
    if (p does not divide n)
        send n to right neighbor
Proces sakupljanja može pohraniti brojeve 2,3,4,...,1000, u levi kraj cevovoda: prvi proces na redu eliminiše umnoške sa 2, drugi eliminiše umnoške sa 3, treći eliminiše umnoške sa 5, i tako dalje.



Priroda linearnosti cevovoda kod ovih primera do sada je loše predstavljala opštu prirodu CSP-a, ali čak i tako ograničen na linearne cevovode, model je prilično moćan. Snaga je u potpunosti demonstrirana uspehom filter-i-cevovod pristupa, po kome je Unix operativni sistem dobro poznat. Zapravo, cevovodi su ranijeg datuma od Hoareovog časopisa. U internom memorandumu Bell laboratorija, datiranom na 11 Oktobar 1964., Doug Mcllroy se poigravao idejama koje će kasnije postati Unixov cevovod: "Trebalo bi da postoji način da nastavljamo programe, kao što je baštensko crevo-zavrnuto na drugi segment, kada postane neophodno slanje podataka na drugi način. Ovo je takođe I/O način."(3)

Hoareovi procesi komunikacije su više opšti, nego tipični Unix shell cevovodi, pošto ih je moguće povezati u proizvoljne obrasce. Zapravo, Hoare kao primer daje 3x3 matricu procesa, nešto poput glavnog sita koje se može upotrebiti za umnožavanje vektora sa 3x3 kvadratnom matricom.

Otuda, mehanizam Unix cevi ne zahteva linearnu postavku, već to shell sintaksa traži. Mcllroy prijavljuje poigravanje sa sintaksom za ljusku kao opštim cevovodom, još ranije, ali je i dalje ne simpatiše dovoljno da bi je implementirao(lična komunikacija, 2011.). Kasnije ljuske su podržale neke ograničene oblike nelinearnih cevovoda. Rochkind-ova 2dsh podražava predivo; Tom Duff-ova podaržava drveće.

Hoareov jezik bio je inovativan i tečan, ali sa nedostatkom nekoliko ključnih aspekata. Glavni defekt je taj što razbaferovani kanali korišćeni za komunikaciju nisu prvoklasni objekti: ne mogu se skladištiti u promenljivima, ne prolaze kao argumenti funkcijama, niti se mogu poslati na drugi kraj kanala. Kao rezultat ovoga, struktura veza mora se ispraviti u toku pisanja programa. Otuda moramo pisati program za štampanje prvih 1000 prostih brojeva, pre nego prvih n, i pomnožiti vektor sa 3x3 matricom, radije nego sa nxn matricom.

Pan i Promela

1980., jedva dve godine nakon Hoareovog časopisa, Gerard Holzmann i Rob Pike stvorili su analizator protokola, nazvan Pan, koji CSP dijalekt prihvata kao unos. Panov CSP dijalekt imao je , povezivanje u lanav, selektovanje i vezivanje omče, ali ne i promenljive. I pored toga, Holzmann prijavljuje da je "Pan pronašao svoju prvu grešku u kontrolnom protokolu razmene podataka Bell laboratorija, od 21. Novembra 1980." (14) Lako je moguće da je taj dijalekt bio prvi CSP jezik u Bell laboratorijama, i svakako je omogućio Pikeu sticanje iskustva, upotrebom i implementacijom kao-CSP jezika, njegovog prvog od mnogih.

Holzmannov analizator protokola razvio se u Spin model potvrđivač, kao i njegov Promela jezik, koji uključuje prvoklasne kanale na isti način kao i Newsqueak(q.v.).

Newsqueak

Krećući se u različitim pravcima, Luca Cardelli i Rob Pike razvijaju ideje iz CSP-a u Squeak-mini-jezik (4) za generisanje koda-korisničkom interfejsu (ovaj Squeak se razlikuje od Squeak Smalltalk implementacije). Pike kasnije proširuje Squeak u potpuno pokriveni jezik za programiranje, Newsqueak (5) (6), koji rađa Alef, Plan-a 9(7) (8), Limbo, inferna (9) i Google- ov Go (13). Glavna semantička prednost Newsqueaka nad Squeakom je ta što Newsqueak tretira kanale komunikacije kao prvoklasne objekte: Za razliku od CSP-a i Squeaka, kanali se mogu skladištiti u promenljivima, mogu proći kao argumenti funkcijama i mogu se slati na drugi kraj kanala.Ovaj zaokret omogućuje programsku konstrukciju strukture komunikacija, dozvoljavajući na taj način, stvaranje kompleksnijih struktura od onih koje bi bilo razumno praviti ručno. Još preciznije, Doug Mcllroy je demonstrirao kako se komunikacijska postrojenja Newsqueaka mogu zaposliti da pišu elegantne programe za manipulisanje simboličnim tokovima moći (10). Slični pokušaji tradicionalnim jezicima se zaglibljuju u knjigovođstvu. Na sličan način je Rob Pike demonstrirao kako se komunikacijska postrojenja mogu uposliti na provaljivanju iz uobičajenih modela programiranja, zasnovanih na događaju, pišući paralelni prozorski sistem (11).

Alef

Alef (7) (8) je bio jezik koji je Phil Winterbottom dizajnirao tako da primeni ideje Newsqueaka na potpuno pokriven sistemski jezik za programiranje. Alef ima dva tipa onoga što zovemo procesi: proks i teme. Program je organizovan u jedan ili više proksa, koji su procesi operativnog sistema sa podeljenom memorijom i mogu se unapred planirati. Svaki proks sadrži jedan ili više zadataka, koji su im kooperativno dodeljeni. Primećujemo da je svaki zadatak dodeljen naročitom proksu: proksi ih ne razmenjuju među sobom.

Glavna upotreba proksa je omogućavanje konteksta koji može blokirati I/O nezavisno od glavnih zadataka (Plan 9 nema odabrani poziv, čak i u Unixu vam je potrebno više proksa ukoliko želite da preklopite kompjutiranje sa I/O van mreže). U časopisu Acme (12) postoji fina kratka diskusija o proksima i temama, kao što su zabeleške sa predavanja o Plan 9 prozor sistemu , takođe kasnije pomenute.

Limbo

Inferno, operativni sistem Plana 9, je spinof namenjen setu top-boksova. Njegov programski jezik, Limbo (9), bio je pod velikim uticajem Alefa. Uklonio je razliku između proksa i zadataka, efektno ostavljajući samo prokse, budući da su, kao procesi, manjih težina nego što većina ljudi misli. Ceo paralelizam je preventivan. Zanimljivo je da uprkos ovome, ovaj jezik ne obezbeđuje stvarnu podršku zaključavanju. Umesto toga, veze kanala karakteristično obezbeđuju dovoljnu sinhronizaciju i ohrabruju programere da podese tako da je uvek jasno ko je vlasnik bilo kog dela podataka. Eksplicitno zaključavanje nije neophodno.

Libthread

Natrag u svet Plana 9, ispostavlja se da je teško održavati kompajlere Plana 9, budući da je Plan 9 prebačen u najviše građevine. Libthread je zapravo stvoren da prebaci Alef programe u C, kako bi se povukli Alefovi kompajleri. Alefovi proksi i zadaci nazivaju se proksi i teme, u Libthreadu. Manual page je konačna referenca.

Go

Rob Pike i Ken Thompson prelaze na Google i smeštaju CSP u centar konkurentske podrške Go-jezika .

Započinjanje

Da bi razumeli model rada, naročito kako procesi i teme uzajamno deluju, korisno je pročitati Alefov vodič za korisnike (8). Prvih trideset slajdova ove prezentacije dobar su uvod u to kako su Alefove konstrukcije predstavljene u C-u.

Najbolji primeri moći CSP modela su Mcllroy-evi i Pike-ovi, ranije pomenuti, časopisi (10) (11).

Rob Pikeova naslovna strana sadrži napomene sa kursa o paralelnom programiranju: uvod i slajdovi o već pomenutim časopisima: squinting i window sistem . Poslednji od tri, daje dobar primer na koji način programi Plana 9, karakteristično, koriste prokse i zadatke.

Rob Pike je dao tehnički razgovor na Google-u koji daje dobar uvod (57- ominutni video snimak).

Polovina Pike-ovih razgovora sa Russ Coxom o I/O Google- a u 2010. , prikazuje kako koristiti kanale i Go-ovu konkurenciju za implementaciju balansiranja opterećenjem sistema za upravljanje.

Povezani Izvori

John Reppy je primenio iste ideje na ML, stvarajući Paralelni ML . Koristio je CML za izgradnju, između ostalog, exene , multitematski (non-event-driven) X Window pribor za rad.



Published (Last edited): 05-09-2012 , source: http://swtch.com/~rsc/thread/