Prognyelvek portál

Az interpretáló kernel eredetileg egy-processzoros rendszerekre lett írva, de 1988-ban átírták több-processzorosra.
Ugyanazt a memóriaallokációs sémát használják, mint az egyprocesszoros rendszerek. Adatstruktúrák reprezentálják az ágenseket, a csatornák pedig végig a memóriában maradnak, hogy minden processz hozzáférhessen. A legnagyobb kihívás a processzek közötti egyenletes munkamegosztás megvalósítása.

Ágens implementáció

Program verem
A memóriakiosztást egy rekurzív, szekvenciális eljárások implementálására használt ismert metódus ihlette: dinamikus allokál fix méretű szegmenseket, amiket létezésük alatt nem lehet reallokálni.
Amikor egy ágens vagy egy csatorna aktiválódik, egy aktivációs rekorddal hozzárendel a rendszer egy fix szegmenst. Az aktivációs rekord vagy egy ágens vagy egy csatorna rekordja. A hossza fordítási időben határozódik meg.
Az ágensek szülő-gyermek relációja egy fában tárolódik, amibe minden ágens és csatorna azonnal bekerül a szülő alá. Az inicializáló ágens a gyökere a fának. Minden ágens legalább addig létezik, mint a gyermekei. Az egyes irányított ágon az ágensek és a csatornák a mélyebb szint felől a gyökér felé aktiválódnak és terminálnak. Így az aktivációs rekordok egy fastruktúrájú vermet alkotnak. Problémát jelent ennek a fastruktúrájú veremnem az allokálása lineáris memóriában. Szervezzük a memóriát úgy, mint aktivációs rekordok verme, ez a program verem.
Amikor egy ágens vagy egy csatorna aktiválódik, az aktivációs rekordját tegyük a verem tetejére, és nevezzük aktívnak. Minden ágens kapcsolódik a szülőjéhez és számon tartja, hány aktív al-ágense, és hány belső csatornája van.
Amikor egy ágens passzívvá válik, a belső csatornáit címkézzük "halott"-nak. Amikor az összes gyermek ágense "halott", a passzív ágenst is cimkézzük "halott"-nak.
A program veremnek van egy zárja, ami megakadályozza, hogy szimultán vegyünk ki aktivációs rekordokat. A processzor nem zárolja a vermet, amíg az ágens fut.
Ágens rekordok
Egy ágens-rekord egy p ágenst reprezentál és négy része van:
1. állapot
2. saját változók
3. saját kifejezésverem
4. saját hossz
Az ágens állapota a következő mezőkből áll:
1. fázis: aktív (még nem ért végig), passzív(a gyermek-ágensek terminálására várakozik), vagy halott (ő és a gyermekei is termináltak már)
2. szülő: egy mutató a szülőre
3. gyermek ágensek száma
4. csatorna-lista: mutató egy csatornarekordra, amit a p hozott létre. Ez a feje a listának.
5. lista mutatók: ha p várakozik egy listában, akkor egy-egy mutató mutat az előző és a következő ágensekre
6. regiszterértékek: ha p várakozik egy sorban, akkor ez a mező tartalmazza az utasításszámlálót és a kifejezésverem mutatóját
Készenléti sorok
Egy P processzoron futó ágenst P futó ágensének nevezzük és a yemegfelelő ágensrekordra mutató pointerrel reprezentáljuk. A futásra várakozó ágensek egy FIFO sorban várakoznak. Ezt a sort készenléti sornak nevezzük. Minden processzornak saját készenléti sora van. Többszörös készenléti sorok használata elengedhetetlen a párhuzamos programok végrehajtásához (Brinch Hansen 1988).
Egy P proceszor készenléti sora három részből áll:
1. Egy ágens-sor
2. Sorhossz, ami definiálja, hány ágenst szolgálhat ki P
3. Egy zár, aminek segítségével más processzorok is hozzáférhetnek a sorhoz
A sorban az ágensrekordok kétirányú listát képeznek.
Processzor ütemezés
A program futásának kezdetén az egyik processzor létrehozza és elkezdi végrehajtani az inicializáló ágenst. A többi processzor üresjáratba inicializálódik. Egy üresjáratban lévő processzor folyamatosan ellenőrzi a saját készenléti sorát, míg egy másik processzor le nem állítja vagy a sora nem üres.
Ezen a ponton, egy processzor vagy választ egy futó ágenst a sorból, vagy terminál.
Egy üres sor akkor válik nem-üressé, ha egy másik processzor behelyez egy ágenst a sorba, szem előtt tartva a multiprocesszoros számítás kiegyensúlyozását.
Egy megosztott stop jelzés hatására a multiprocesszoros rendszer vagy megáll, vagy folytatja az ágensek végrehajtását. Ha egy processzor észleli a program terminálását (vagy meghibásodását), akkor stop jelzést ad ki.
Az üresjáratú processzorok kiválasztásának algoritmusa a következő:
1. LOCK a saját sorra
2. while (nem áll le és a saját készenléti sor üres) do
  begin
  UNLOCK a készenléti sor
  késleltetés
  LOCK a saját készenléti sor
  end;
3. if (nem állt le) then
  begin
  Egy ágens kivétele a készenléti sorból és futó ágenssé tenni
  UNLOCK a készenléti sor
  end else begin
  UNLOCK a készenléti sor
  processzor terminálása
  end
A második lépésben a készenléti sor ideiglenes unlockolása lehetővé teszi, hogy más processzor is lockolhassa ugyanazt a sort és betehessen egy ágenst. Ahhoz, hogy elkerülhessük a lockolási konfliktusokat, az üresjáratú processzor a következő ciklussal tartja fel magát:
Delay:
while (nem állt meg és üres a készenléti sor) do
skip
Amikor egy processzor berak egy q ágenst a sorba, végrehajt egy ütemezési algoritmust:
1. Megkeresi a legrövidebb készenléti sort
2. LOCK a sorra
3. Az ágens behelyezése a sorba
4. UNLOCK a sorra
A processzorok megpróbálják úgy elosztani a munkamennyiséget, hogy a készenléti sorok egyforma hosszúak legyenek.
Amikor egy processzor végignézi a készenléti sorokat, hogy megtalálja a legrövidebbet, nem lockolja vagy unlockolja azokat. Ez megakadályozza a fölösleges várakozásait az üresjáratú processzoroknak, amik lockolni szeretnék a soraikat és kiválasztanának egy futó ágenst. Néha tévedésből két processzor ugyanazt a sort választja, de ez csak kicsivel teszi hosszabbá.
A processzor futtatja az adott ágenst, amíg a következő események meg nem történnek:
1. az ágens véget ér
2. az ágens elér egy olyan i/o utasításhoz, amit az adott pillanatban nem tud végrehajtani
3. az ágens elér egy polling utasítást, amit nem tud egyelőre végrehajtani
Ágens aktiválás
Egy futó p ágens 7 lépésben hajt végre egy Q(paraméterek) ágens-utasítást:
1. az aktuális paraméterek kiértékelése a p kifejezés stackjében
2. LOCK a program stackre
3. egy q, új ágensrekord betétele a program stackbe, majd mezőinek inicializálása
4. az aktuális paraméterek kivétele p kifejezésverméből és az értékek hozzárendelése q formális paraméterek részéhez
5. a q ágens folytatása
6. p al-ágenseinek számának növelése 1-el
7. UNLOCK a program stackre
Egy ágens aktiválása során, az inicializálatlan változókat a rendszer nullára állítja, amik egy nil pointert reprezentálnak. Ez lehetővé teszi a kernel számára, hogy észlelje, ha egy ágens nem létező csatornán keresztül próbál kommunikálni.
Ágens terminálás Amikor egy ágens futása végéhez ér, a processzot a következő algoritmust hajtja végre:
1. LOCK a program stackre
2. eleinte legyen p futó ágens és jelöljük passzívnak
3. while (p al-ágensek nélküli passzív ágens) do
  begin
  for (p összes belső csatornájára)
  begin
  LOCK a csatornára
  a csatorna halottnak cimkézése
  UNLOCK a csatornára
  end
  p halottnak cimkézése
  if (p-nek van szülője) then
  begin
  p := p szülője
  p al-ágenseinek száma -= 1 end
  end;
4. while (amíg van halott aktivációs rekord a program stack tetején) do (rekord kivétele)
5. if (program stack üres) then (stop := true)
6. UNLOCK a program stack
7. egy futó ágens kiválasztása
Minden csatornának saját zára van. Az aktivációs rekord első és utolsó mezője definiálja, milyen állapotban van és milyen hosszú az adott ágens (vagy csatorna). Ez az egyezmény leegyszerűsíti a halott rekordok kivételének mechanizmusát a program stackből.

Csatorna implementáció

A csatornák implementálása is megpróbálja ötvözni az egyszerűséget és a hatékonyságot:

a kimenő ágens üzenete köztes buffer használata nélkül másolódik át az input ágens aktivációs rekordjába
két összeillő ágens közötti kommunikációhoz csak egy végrehajtó processzorra van szükség az ágensek közötti könnyebb váltás miatt

Ezeket a szándékokat úgy valósították meg, hogy különálló sorok állnak rendelkezésre az x csatorna minden szimbóluma számára az ABC-ben. Amikor egy ágens készenáll egy si szimbólum küldésére vagy fogadására az x csatornán, megvizsgálja az egyező szimbólumsort, hogy egy kapcsolódó q ágens várakozik-e a kommunikációban való részvételre. Ebben az esetben, p megkapja az input v változó címét és az e output értékét a p és q kifejezés verméből, hozzárendeli e-t v-hez, és folytatja q-t a legrövidebb készenléti sorhoz mozgatva. Akárhogy is, ha p nem talál kapcsolódó ágenst, p belép a szimbólumsorba és vár, míg egy kapcsolódó ágens befejezi a kommunikációt és folytatja p-t.
Mikor egy csatornát kettőnél több ágens használ, az egyiknek képesnek kell lennie felismerni, hogy egy szimbólumsorbeli ágens küld vagy fogad egy megfelelő szimbólumot. Megjegyzendő, hogy egy szimbólumsor nem képes egyszerre inputként és outputként működni. Ez elegendő, hogy egy sort kiegészítsen egy logikai értékkel, ami jelzi, hogy a sorban van-e input vagy output ágens, amennyiben az nem üres. A megoldás, amit használtunk az, hogy minden input és output sort hozzárendeltünk minden szimbólumhoz. A felhasznált memória mindkét esetben azonos: egy word.
A kommunikáló ágensek köröznek a készenléti sor és a csatornák sorai között, amíg nem terminálnak. Mivel minden ágens a legrövidebb készenléti sorba kerül vissza, áttelepülhetnek az egyik processzorról a másikra. Az átköltözést egyszerű megoldani, mivel minden processzor hozzáfér minden memóriában lévő aktivációs rekordhoz és sorhoz.

Csatorna rekordok
Egy csatornarekord egyp ágens által létrehozott x csatornát reprezentál. A csatorna öt részből áll:
1. a csatornaállapot jelzi, hogy x aktív vagy halott
2. a csatornához rendelt zár
3. a csatornapointer, ami összekapcsolja a p által létrehozott csatornarekordokat. A p ágens rekordja tartalmazza a köztes csatornák mutatóinak láncát
4. a csatorna sorok sor-párokból állnak, minden csatorna ABC-beli si szimbólumhoz egy: ágensek sora várakozik arra, hogy az si szimbólumot átküldjék az x csatornán és ágensek sora várakozik az si szimbólumra, hogy kiolvassák az x csatornából. Az ágensek egy két irányban kapcsolt sorban várakoznak. Minden sort egy, a sor elején álló ágensre mutató pointer reprezentál.
5. a csatornarekord hossza
Csatorna aktiválása
Egy p futó ágens egy +c port utasítást hat lépésben hajt végre:
1. a c port-változó címének behelyezése a p kifejezésvermébe
2. LOCK a program stackre
3. a program stackbe egy új csatornarekord helyezése, aktívnak címkézése nyitott zárral, és a csatorna-sorok ürítése
4. a csatornarekordok csatolása a p ágensrekordjához
5. UNLOCK a program stackre
6. a csatorna-mutató hozzárendelése a c változóhoz és a c címének kivétele a p stackjéből
I/O
Amikor egy futó ágens egy c!si(e) output utasításhoz ér, a processzor a következőket teszi:
1. a c csatorna-pointer és az e output-érték behelyezése a kifejezésverembe
2. LOCK a c által jelölt csatornát
3. with (az si szimbólum csatornasorai) do
  if (az si input-sora nem üres) then
  begin
  egy q ágens kivétele at input-sorból
  UNLOCK a csatornára
  a v és c input-változók címének kivétele a q verméből
  az e és c output-változók kivétele a p verméből és hozzárendelése e-hez és v-hez
  a q ágens folytatása
  end else begin
  p behelyezése a kimeneti sorba
  UNLOCK a csatornára
  egy futó ágens kiválasztása
  end
A p futó ágens c?si(v) input utasítását a processzor a következőképpen hajtja végre:
1. a c csatornapointer és a v inputváltozó címének behelyezése a p kifejezésvermébe
2. LOCK a c által mutatott csatornára
3. with (az si szimbólum csatornasorai) do
  if (az si output-sora nem üres) then
  begin
  egy q ágens kivétele a kimeneti sorból
  UNLOCK a csatornára
  a v és c címének kivétele a p verméből
  az e és c értékének kivétele a q stackjéből és hozzárendelése e-hez és v-hez
  a q ágens folytatása
  end else begin
  a p behelyezése az input-sorba
  UNLOCK a csatornára
  egy futó ágens kiválasztása
  end
Polling
A polling magába foglalja a csatorna-sorok ismételt vizsgálatát mindaddig, míg nem talál egy összeillő ágenst. Ez azért különösen fontos, hogy csökkentsük a többletmunkát kontextus váltás és csatorna vizsgálat során, amennyire csak lehet. Használjuk a következő eljárást: ha egy p ágens az összes védett utasítást megvizsgálta egy polling utasításon belül eredménytelenül, p visszatér az aktuális processzor készenléti sorához abban a reményben, hogy egy megfelelő ágens belép egy helyes szimbólumsorba, mielőtt p-nek újra lehetősége lenne megvizsgálnia a saját védett utasításait. Részletesebben, ha egy futó p ágens elér egy védett c!si(e)&B -> SL output utasításhoz, a processzor a következőket hajtja végre:
1. a c, e és B behelyezése a p kifejezés-vermébe
2. LOCK a c által mutatott csatornára
3. with (az si szimbólum csatorna-sorai) do
  if (az si input sora nem üres és B) then
  begin
  a q ágens kivétele az input-sorból
  UNLOCK a csatornára
  a v és c input-változók címének kivétele a q verméből
  a B, e és c kivétele a p verméből és e hozzárendelése v-hez
  a q ágens folytatása
  SL;
  ugrás a polling utasítás végére
  end else begin
  UNLOCK a csatornára
  a B, e és c kivétele a p verméből
  ugrás más védett utasításra
  end
ahol "ugrás más védett utasításra" a következők valamelyike:
1. ha a Gi védett utasítást a szintén védett Gi+1 utasítás követi egyazon polling utasításban, akkor ugorjon Gi+1-re
2. máskülönben beállítja a p utasításszámlálóját a polling utasítás első védett utasítására, visszahelyezi p-t az aktuális processzor készenléti sorába, és választ egy másik futó ágens a készenléti sorból. Amikor ismét a p ágens fut, újra ellenőrzi annak védett utasításait a G1-től kezdve.
Fontos, hogy a védett utasítás vizsgálatának semmilyen hatással nincs, ha nem lehet végrehajtani.
Egy védett input-utasítás végrehajtása hasonló.
Rendszer-csatorna
Egy Joyce program a perifériákkal egy előre definiált csatornán keresztül kommunikál, ez a rendszer-csatorna. Az inicializáló ágens tud ehhez hozzáférni egy kernel által inicializált aktuális paraméteren keresztül. A kommunikációt egy rendszer-függvény valósítja meg, végrehajtva a perifériának megfelelő műveletet. A rendszercsatornának saját LOCK-ja van.

Zárak

Amikor egy processzor szimultán szeretne osztott adatokhoz hozzáférni, lockolja őket egyesével (egyszerre csak egyet), kötött sorrendben, hogy elkerülje a holtpont helyzeteket (Brich Hansen 1973):

a program-verem
egy, az ágens által aktivált csatorna
egy készenléti sor
a rendszer-csatorna

Mivel a rendszer-csatornának van a legalacsonyabb prioritása ezért egy processzor lockolni tudja bármilyen kernel művelet közben és megjeleníti a szignifikáns eseményeket. Mint például egy ágens vagy egy csatorna aktiválódása vagy terminálása esetleg a kommunikáció befejezése. A használt sorok és zárak száma Brinch Hansen teljesítmény kísérletei alapján határozhatjuk meg (1988).

A Joyce programozási nyelv

Implementálás multiprocesszoros rendszerekre

Ágens implementáció

Csatorna implementáció

Zárak