Bell Labs och CSP Trådar

Original: https://swtch.com/~rsc/thread/

Russ Cox
[email protected]
Inledning

Denna sida är en del av den historia av samtidig programmering, fokuserar på en viss härstamning Hoare språk för att kommunicera sekventiella processer (CSP) [1] [1a]. Samtidig programmering i denna stil är intressant för skäl inte av effektivitet, men av klarhet. Det är, det är ett stort misstag att tro att bara för samtidig programmering som ett medel för att öka prestanda, exempel, för att överlappa disk i/O-begäranden, för att undvika fördröjning av prefetching resultat förväntas frågor, eller för att dra fördel av flera processorer. Sådana fördelar är viktiga, men inte relevant för denna diskussion. Efter alla, de kan realiseras i andra format, till exempel asynkron händelsestyrd programmering. Istället är vi intresserade av samtidig programmering eftersom det ger en naturlig abstraktion som kan göra att vissa program mycket enklare.

Vad detta är inte

De flesta datavetenskap studenter är tvungna att läsa Andrew Birrell “En Introduktion till Programmering med Trådar.” Den SRC trådar modell är den som används av de flesta tråd paket som finns tillgängliga. Problemet med alla dessa är att de är alltför låg nivå. Till skillnad från kommunikation primitiva tillhandahålls av Hoare, primitiver i den SRC stil gängning modul måste kombineras med andra tekniker, oftast delat minne, för att kunna användas effektivt. I allmänhet, programmerare tenderar att inte bygga sin egen högre-nivå konstruktioner, och är kvar frustrerad av att behöva betala uppmärksamhet till en sådan låg nivå detaljer.

För tillfället, tryck Birrell s handledning ur ditt sinne. Detta är en annan tråd modell. Om du närmar dig det som en annan tråd modell, du kanske tycker att det är mycket lättare att förstå.

att Kommunicera Sekventiella Processer

1978 fanns det många förslag till metoder för kommunikation och synkronisering i samband med planeringen multiprocessors. Delat minne var den mest gemensamma anmälningssystem och semaforer, kritiska områdena, och skärmar var bland de synkronisering mekanismer. C. A. R. Hoare riktar sig både frågor med ett enda språk primitiva: synkron kommunikation. I Hoare är CSP språk, processer kommunicerar genom att skicka eller ta emot värden från namngivna ej buffrad-kanaler. Eftersom kanalerna är ej buffrad, skicka operation kvarter tills det värde som har överförts till en mottagare, vilket ger en mekanism för synkronisering.

En av Hoare exempel på detta är att formatera 80-kolumn-kort för utskrift på en 125-kolumn skrivaren. I sin lösning, en process läser ett kort i taget, skicka isär innehållet tecken-för-tecken i en andra process. Denna andra process monterar grupper av 125 tecken, skicka grupper till den linje som skrivaren. Det låter trivialt, men i avsaknad av buffrat i/O-bibliotek, som är nödvändiga bokföring som är inblandade i en enda process lösning som är betungande. I själva verket är buffrat i/O-bibliotek är egentligen bara encapsulations av dessa två typer av processer för att exportera den enda karaktär kommunikationsgränssnitt.

Som ett annat exempel, som Hoare krediter till Doug McIlroy, anser generation av alla primtal mindre än en promille. Sikten av Eratosthenes kan simuleras genom en rörledning av processer att köra följande pseudocode:

s = få ett nummer från vänster granne
print p
loop:
n = få ett nummer från vänster granne
om p inte delar n)
skicka n till höger granne

En genererande process kan mata siffrorna 2, 3, 4, …, 1000 i den vänstra änden av ledningen: den första processen i linje eliminerar multiplar av 2, den andra eliminerar multiplar av 3, den tredje eliminerar multipler av 5, och så vidare:

Den linjära pipeline arten av de exempel som hittills är misrepresentative av den allmänna karaktären av CSP, men även begränsad till linjär rörledningar, den modell som är ganska kraftfull. Strömmen har varit kraftfullt framgår av framgång av filter-och-pipeline strategi för vilka Unix-system är välkänt [2] Ja, rörledningar före Hoare papper. I en intern Bell Labs promemoria daterad den 11 oktober, 1964, Doug McIlroy lekte med idéer som skulle bli Unix rörledningarna: “Vi bör ha ett visst sätt av koppling program som trädgårdsslang–skruv i ett annat segment när det blir nödvändigt att massage data på ett annat sätt. Detta är det sätt på IO.” [3]

Hoare är kommunicerande processer är mer generella än vanliga Unix-skal rörledningar, eftersom de kan anslutas i valfri mönster. I själva verket, Hoare ger som exempel en 3×3 matris av processer något som prime-sil som kan användas för att multiplicera en vektor med en 3×3-kvadratisk matris.

Naturligtvis Unix-rör mekanism kräver inte den linjära layout, endast shell syntax gör. McIlroy rapporter lekte med syntax för en skal med allmän vvs tidigt men som inte gillar syntax tillräckligt för att genomföra det (personlig kommunikation, 2011). Senare skal gjorde stödja vissa begränsade former av icke-linjära rörledningarna. Rochkind är 2dsh stöder dags, Tom Duff ‘ s rc stöder träd.

Hoare språket var nytt och inflytelserik, men saknar ett par viktiga aspekter. Den största bristen är att obuffrat kanaler som används för kommunikation är inte första klassens objekt: att de inte kan lagras i variabler, som skickas som argument till funktioner, eller skickas över kanaler. Som en följd av detta, kommunikation struktur måste vara fast samtidigt som att skriva program. Därför måste vi skriva ett program för att skriva ut de första 1000 primes snarare än den första n primtal, och att multiplicera en vektor med en 3×3 matris i stället för en nxn matrisen.

Panorera och Promela

1980, knappt två år efter Hoare papper, Gerard Holzmann och Rob Pike skapat en protokollanalysator kallad pan som tar en CSP dialekt som indata. Pan ‘ s CSP dialekt hade sammanslagning, urval, och looping, men inga variabler. Även så, Holzmann rapporter som “Pan fick sitt första fel i en Bell Labs data-switch control protocol den 21 November 1980. “[14]. Att dialekten kan mycket väl ha varit den första CSP språk på Bell Labs, och att det verkligen har gett Gädda med erfarenhet av att använda och implementera en CSP-liknande språk, sin första av många.

Holzmann s protokoll-analysator utvecklats till Spin model checker och dess Promela språk, som har första-klass-kanaler på samma sätt som Newsqueak (qv).

Newsqueak

Rör sig i en annan riktning, Luca Cardelli och Rob Pike utvecklat idéerna i CSP i Gnissla mini-språk [4] för att generera kod användargränssnitt. (Detta Gnissla skiljer sig från den som Gnäller Smalltalk genomförande.) Gäddan som senare utökades Gnissla i fullfjädrat programmeringsspråk Newsqueak [5][6] som födde Plan 9 är Alef [7] [8], Inferno ‘ s Limbo [9], och Google ‘ s Go [13]. Den huvudsakliga semantiska nytta av Newsqueak över Gnissla är att Newsqueak behandlar kommunikationskanaler som första klassens objekt: till skillnad från i CSP och Gnäller kanaler kan att lagras i variabler, som skickas som argument till funktioner, och som sänds i kanalerna. Detta i sin tur gör att den programmatiska byggandet av kommunikation struktur, vilket möjliggör skapandet av mer komplexa strukturer än vad som skulle vara rimligt att design av sidan. I synnerhet, Doug McIlroy visat hur kommunikation av Newsqueak kan användas för att skriva elegant program för att manipulera symbolisk makt serien [10]. Liknande försök i traditionella språk tenderar att smutsen i bokföring. På ett liknande sätt, Rob Pike visat hur kommunikation kan användas för att bryta sig ur den gemensamma händelse-baserad programmering modell, skriva en samtidig window system [11].

Wikipedia

Alef [7] [8] var ett språk som är designad av Phil Fobier att tillämpa Newsqueak idéer till en fullfjädrad system programmeringsspråk. Alef har två typer av vad vi har kallat processer: procs och trådar. Programmet är organiserat i en eller flera procs, som är delat minne operativsystem processer som kan vara förebyggande syfte planerat. Varje fil innehåller en eller flera uppgifter, som tillsammans planerat coroutines. Observera att varje uppgift som är tilldelad en viss proc: de gör inte migrera mellan procs.

Den huvudsakliga användningen av procs är att ge sammanhang som kan blockera för i/O-oberoende av de viktigaste uppgifter. (Plan 9 har inte väljer du samtal, och även på Unix-du behöver flera procs om du vill överlappa beräkning med icke-nätverks i/O.) Acme-papper [12] har en fin kort diskussion av procs och trådar, vilket gör föreläsningsanteckningar om Plan 9 window system, som också nämns nedan.

Limbo

Inferno operativsystem är ett Plan 9 spinoff som är avsedd för set-top-boxar. Dess programmeringsspråk, Limbo [9], var starkt påverkad av Alef. Det bort skillnaden mellan procs och uppgifter, för att på ett effektivt sätt med bara procs, även om de var av lättare vikt än vad de flesta människor tror av processer. Alla parallellitet företrädesrätt. Det är intressant att trots detta, språket ger inget riktigt stöd för låsning. Istället kanal kommunikation ger normalt tillräckligt för synkronisering och uppmuntrar programmerare att ordna så att det alltid finns en tydlig ägare för varje bit av data. Explicit låsning är onödiga.

Libthread

Tillbaka i Plan 9 världen, Alef kompilatorer visade sig vara svårt att upprätthålla en så Plan 9 var portas till att allt fler arkitekturer. Libthread skapades ursprungligen för att hamnen Alef-program till C, så att den Alef kompilatorer kan vara pensionerad. Alef är procs och uppgifter kallas procs och trådar i libthread. bruksanvisningen är den slutgiltiga referens.

Öppna

Rob Pike och Ken Thompson flyttat in på Google och placeras CSP i mitten av Gå språket‘s samtidighet stöd.

Komma Igång

För att få en känsla för modellen, särskilt hur processer och trådar interagera, det är värt att läsa Alef Användarhandbok [8]. De första trettio bilder av den här presentationen är en bra introduktion till hur Alef-konstruktioner finns representerade i C.

De bästa exemplen på kraften i CSP-modellen är McIlroy och Gädda papper som nämns ovan [10] [11].

Rob Pike ‘ s hemsida innehåller föreläsningsanteckningar från en kurs på samtidig programmering: inledning, och bilder om de två ovan nämnda papper: kisa och linux. Den sista av de tre är ett bra exempel på hur Plan 9 program brukar använda procs och uppgifter.

Rob Pike gav en tech talk på Google som ger en bra introduktion (57 minuters video).

Rob Pike hälften av sin 2010 Google i/O prata med Russ Cox visar hur man använder kanaler och samtidighet för att genomföra en lastbalansering arbete management system.

för ytterligare information

John Reppy har tillämpat samma idéer till ML, producera Samtidiga ML. Han använde KML för att bygga, bland annat eXene flertrådig (icke-händelse-driven) X Window System toolkit.

> Referenser

[1] C. A. R. Hoare, “Kommunicera Sekventiella Processer,” Communications of the ACM 21(8) (augusti 1978), 666-677.

[1a]C. A. R. Hoare, Kommunicera Sekventiella Processer. Prentice Hall, Englewood Cliffs, New Jersey, 1985.

[2] Michael S. Mahoney, ed., Unix Oral History-Projekt, Släppa 0: Början

[3] M. Douglas McIlroy, inre Bell Labs memorandum, oktober 1964.

[4] Luca Cardelli och Rob Pike, “Gnissla: ett Språk för att Kommunicera med Möss,” datorgrafik, 19(3) (juli 1985: SIGGRAPH ’85 Förfaranden), 199-204.

[5] Rob Pike, “Genomförandet av Newsqueak,” Programvara-Övning och Erfarenhet, 20(7) (från juli 1990), 649-659.

[6] Rob Pike, “Newsqueak: ett Språk för att Kommunicera med Möss,” datavetenskap Teknisk Rapport 143, AT&T Bell Laboratories, Murray Hill, 1989.

[7] Phil Fobier, “Alef Language Reference Manual,” i Plan 9 programmerarhandboken: Volym Två, AT&T, Murray Hill, 1995.

[8] Bob Flandrena, “Alef Users’ Guide,” i Plan 9 programmerarhandboken: Volym Två, AT&T, Murray Hill, 1995.

[9] Dennis M. Ritchie, “Limbo Programmeringsspråk,” i Inferno programmerarhandboken, Volym 2, Vita Nuova Holdings Ltd., York, 2000.

[10] M. Douglas McIlroy, “Vindögd på Power-Serie,” Programvara-Övning och Erfarenhet, 20(7) (från juli 1990), 661-683.

[11] Rob Pike, “En Samtidig Window System,” Datorer, 2(2) 133-153.

[12] Rob Pike, “Acme: Ett Användargränssnitt för Programmerare,” Talan av Vintern 1994 USENIX Konferensen, 223-234.

[13] golang.org “Gå Programmeringsspråk”.

[14] Gerard Holzmann, “Spin Rötter”.

[15] Gerard Holzmann, “Promela Språk Referens”.

Leave a Reply

Your email address will not be published. Required fields are marked *