Symmetrisen moniprosessorikäyttöjärjestelmän suunnittelu reaaliaikasovellutuksiin

DIPLOMITYÖ

Teknillinen korkeakoulu Teknillisen fysiikan osasto

Risto Linturi

Alkulause

Tämä työ on tehty Helsingin teknillisen korkeakoulun Digi- tâa1itekniikan laboratoriossa apul.prof. Iiro Hartimon joh­

dolla ja tekn. lis. Jukka Aspelundin ohjauksella.

Haluan kiittää työni johtajaa ja olijaa jaa heidän osoitta­

mastaan mielenkiinnosta ja saamastani arvokkaasta avusta.

Samoin haluan osoittaa kiitokseni Kauppa- ja Teollisuusmi­

nisteriölle, jonka tuella tutkimus on rahoitettu. Luita tutkimusprojektin osanottajia ja koko Digitaalitekniikan laboratorion henkilökuntaa haluan kiittää aktivoivasta ja miellyttävästä työympäristöstä. Erityisen kiitoksen ansait­

sevat prof. Leo Ojala sekä tekn. lis. Göran Pulkkis.

Edellisten lisäksi haluan kiittää niitä Digitaalitekniikan laboratorion opiskelijoita, jotka ovat työpanoksellaan osal­

listuneet tämän tutkimuksen käytännön toteutukseen.

Risto Linturi

SISÄLLYSLUETTELO

1 JOHDANTO... !

2 TUTKIMUKSEN PUITTEET... 3

2.1 Tutkimusryhmän keskeiset tavoitteet... 3

2.1.1 Oh je Imi s toarkkiteh tuuri tutkimus... 4

2.1.2 Suorituskyky tutkimus... 4

2.1.3 Sovel lutusympär is totu tkimus... 5

2.1.4 Koelaitteiston kehittäminen... 5

2.2 Rinnakkainen tutkimus... 5

2.2.1 C. mmp... 7

2.2.2 G. m*... 9

2.2.3 C. vmp... io 2.2.4 SRI SIFT... 11

2.2.5 F TMP... 12

2.3 Koelaitteiston esittely... 13

2.3.1 Laitteistoarkkitehtuuri... 13

2.3.2 Äänestin... 15

2.3.3 Koelaitteiston puutteet... 17

3 RATKAISUN LÄHTÖKOHDAT... 13

3.1 Tavoitteet ja rajoitukset... 19

3.2 Määritelty ohjelmistoarkkitehtuuri... 20

3.2.1 Ohjelmien yleisrakenne... 21

3.2.2 Tehtävä luokat... 21

3.2.3 Tehtävä lis tat... 22

3.2.4 Käyttö jär jestelmäoperaatiot... 23

4 KÄYTETYT SUUNNITTELUMENETELMÄT... 2 6 4.1 Petri-verkko... 26

4.2 Modifioidut Petri-verkot... 28

4.3 Lokaliteetti Petri-verkko... 29 4.4 ALPN-verkko... 3I

5 SOVELLUTUSOHJELMAKSI MERKKI... 35

6 TÄRKEIMPIEN KÄYTTÖJÄRJESTELMÄTOIMINTOJEN MÄÄRITTELY. 30 6.1 Käyttöjärjestelmän yleinen rakenne... 33

6.2 Tehtävää joi tin... 3g 6.3 Virtuaaliajoitin... 43

6.4 Äänestys... 45

6.5 I/O-järjestelmä... 45

6.6 Reaaliajan ylläpito... 49

6.7 Käytetyt vikastrategiat... 51

6.7.1 Ohjausvirheet... 52

6.7.2 Tulos tusvirheet... 55

7 OHJELMISTON TOTEUTUS... 53

7.1 Ansiot... 5Q 7.2 Puutteet... gl 7.3 Jatkokehittelyn suuntaviivat... 62

8 YHTEENVETO... 64

9 KIRJALLISUUSVIITTEET... 66

LIITTEET:

LIITE 1 Käyttojärjestelmäoperaatioiden kuvaukset LIITE 2 Sovellutusohjelmaesimerkin listaus

LIITE 3 Tehtävääjoittimen listaus LIITE 4 Virtuaaliajoittimen listaus

1. JOHDANTO

Rinnakkaisen prosessoinnin ajatus ei ole uusi. Taloudellisten tekijöiden vuoksi ei sovellutuksia ole aiemmin kuitenkaan ol­

lut kuin harvoilla alueilla. Viime aikainen mikroprosessori- teknologian läpimurto on laajentanut potentiaalisten sovel­

lutusten määrää huomattavasti. Yhä aleneva hinta ja kasvava suorituskyky tekevät tällaisista järjestelmistä tulevaisuudes­

sa vielä halutumpia.

Suorituskyvyn kasvu ei ole ainoa seikka, jonka seurauksena moniprosessorit tarjoavat usein yksiprosessorijärjestelmiä paremman vaihtoehdon. Muita etuja ovat mm. laitteiston ja ohjelmiston parempi modulaarisuus ja laajennettavuus sekä suurempi joustavuus vikatilanteissa ja tietojenkäsittely- tarpeiden muuttuessa.

Suurta turvallisuutta ja luotettavuutta tarvitaan monissa oh­

jaus- ja säätotehtävissä, joissa ohjausjärjestelmän antamat virheelliset tulosteet tai pysähtyminen voivat vaarantaa ih­

mishenkiä tai aiheuttaa suuria taloudellisia vahinkoja. Moni—

prosessorisovellutukset ja erityisesti ns. hybridivarmennetut järjestelmät suovat hyvät mahdollisuudet täyttää sekä korkeat turvallisuus- että luotettavuusvaatimukset. Turvallisuus pe­

rustuu näissä järjestelmissä äänestimeen, jonka kautta kriit­

tiset ohjaukset annetaan usean prosessorin vahvistamina. Luo­

tettavuus aikaansaadaan turvautumalla varayksikoiden käyttöön­

ottoon jos jokin järjestelmän prosessoreista vikaantuu.

Tämän työn tavoitteena on suunnitella käyttöjärjestelmä erää­

seen hybridivarmennettuun monimikroprosessorijärjestelmään.

Pääsoveilutuksina pidetään nopeita prosessinohjauksia, joista esimerkkinä esitetään numeerinen työstökoneen ohjaus. Käyttö­

järjestelmän on tuettava selkeää ohjelmointia sekä mahdollis­

tettava laitteiston sisältämän rinnakkaisuuden ja luotetta- vuusominaisuuksien luonteva käyttö. Lisäksi on turvattava vasteaikojen toteutuminen.

Moniprosessorijärjestelmien suurin haittapuoli on ohjelmoin­

nin hankaluus. Tämä seikka on erittäin merkittävä, kun ote­

taan huomioon, että jo yksiprosessorijärjestelmissä ohjelmoin­

tityö muodostaa projektien kustannuksista selvästi suurimman osan. Huomattavan helpotuksen ohjelmointityöhön toisi mahdol­

lisimman yleiskäyttöinen käyttöjärjestelmä, jonka alaisuudes­

sa voisi unohtaa tekevänsä ohjelmaa moniprosessorille. Ylei­

syys on tärkeä, koska tällöin ohjelmoinnin työläimmän osan kustannukset jakautuvat mahdollisimman usean sovellutuksen kesken

Ohjelmoitaessa korkeaan turvallisuuteen ja luotettavuuteen tähtääviä järjestelmiä on systemaattisiin suunnittelumenetel­

miin kiinnitettävä suurta huomiota. Suurin osa vaikeista vir­

heistä syntyy juuri ohjelmien määrittelyvaiheen ristiriitai­

suuksista, jotka käyvät ilmi vasta testausvaiheessa. Peräk- käisrakenteisen järjestelmän toiminta voidaan tehokkaasti esittää ohjelmakoodina. Rinnakkaiset järjestelmät edellyt­

tävät kuitenkin parempia malleja ohjelma— ja laitteistoviko­

jen ja niiden seurausten havaitsemiseksi.

Tavoitteena tulisi olla tiivis ja täydellinen esitysformalis—

mi, jolla rinnakkaisen järjestelmän ohjaus voidaan määritellä ja mahdollisesti myös analysoida. Analysoinnin edellytyksenä on, että formalismi on esitettävissä algebrallisessa muodos­

sa. On inhimillisten tekijöiden vuoksi tärkeää, että suunnit­

telussa käytetään graafisia menetelmiä. Graafisen ja algebral­

lisen formalismin välillä tulisi olla suora vastaavuus /1/.

Petri-verkkoja /2/ käytetään usein rinnakkaisten järjestel­

mien mallittamiseen. Moniprosessorijärjestelmissä on toimin­

tojen paikallisuus /3/ tärkeä. Paikallisuus on käsitteenä liitettävissä resurssien käytettävyyteen ja saantioikeuksiin.

Paikallisuus on vaikea mallittaa tavanomaisia Petri- verk­

kojen rakenteita käyttäen. Verkkoformalismiin voidaan kuiten­

kin tehdä piirrosteknillisiä muutoksia, jolloin mallit tule­

vat havainnollisemmiksi, mutta eivät kadota arvokkaita ana­

lyyttisiä ominaisuuksia.

2 TUTKIMUKSEN PUITTEET

Suoritettu tutkimus liittyy ympäristöön kolmella eri tavalla.

Läheisin liittymäkohta on projekti, jonka puitteissa tutkimus suoritetaan. Eräänlaisen ympäristön muodostaa muissa tutkimus­

laitoksissa suoritettu rinnakkainen tutkimus. Viimeisenä ja ehkä määräävimpänä ympäristötekijänä on koelaitteisto. Kaik­

kien osittainen tuntemus on välttämätön jäljempänä esitettä­

vien perusteiden ymmärtämiseksi.

2.1 Tutkimusryhmän keskeiset tavoitteet

Helsingin teknillisen korkeakoulun digitaalitekniikan labo­

ratoriossa on tutkittu moniprosessorijärjestelmiä vuodesta 1974 alkaen. Ensimmäinen tutkimuskohde oli hierarkisesti organisoitu MUMI järjestelmä /4/. Vuosina 1979-1980 on labo­

ratoriossa rakennettu koelaitteistoksi symmetrinen monimikro- prosessorijärjestelmä, jossa sekä mikrotietokoneet että jär­

jestelmän väylä ovat standardivalmisteisia. Tämä uC*-järjes- telmä on ollut kuluneen vuoden aikana Suomen Akatemian sekä Kauppa- ja Teollisuusministeriön tukeman tavoitetutkimuksen koelaitteistona.

Projektin nimi on "Monimikroprosessorijärjestelmät ja niiden soveltaminen numeeriseen tyostökoneohjaukseen". Tutkimuksen tavoitteena on sovellutustilanteen suorituskyky— ja luotetta­

vuusvaatimuksia huomioivan monimikroprosessorijärjestelmän ohjelmistokehittelymenetelmän luominen ja tämän menetelmän soveltaminen tyypillisen sorvin numeeriseen ohjaukseen.

Tutkimus jakautuu neljään pääosaan : -Ohjelmistoarkkitehtuuritutkimus -Suorituskykytutkimus

-Sovellutusympäristotutkimus

—Koelaitteiston kehittäminen

2.1.1 Ohjelmistoarkkitehtuuritutkimus

Osatutkimuksen tavoitteena on ollut suunnitella soveltuva oh­

jelmistoarkkitehtuuri sekä vastaava käyttöjärjestelmä. Käyttö­

järjestelmä on suunniteltu siten, että kaikki järjestelmän prosessorit suorittavat sen rutiineja samanarvoisina, joten minkään yksittäisen prosessorin vikaantuminen ei lamauta käyt­

töjärjestelmän toimintaa. Samanarvoisuus ulottuu myös sovellu­

tusohjelman osien suoritukseen. Sovellutusohjelmoijalla on mahdollisuus määritellä, mitkä ohjelman osat ovat niin kriit­

tisiä, että ne tulee varmentaa äänestyksellä. Sovellutusoh- jelmoijan päätettäväksi on samaten jätetty ohjelman eri osien ajallinen painoarvo.

OhjeImistoarkkitehtuuritutkimuksen täyspainoisena osana on kehitetty välineistö, jonka avulla käyttöjärjestelmää ja so­

vellutusohjelmia voidaan mallittaa. Mallien on todettu olevan hyödyllisiä sekä toimintojen oikeellisuuden todentamisessa että havainnollistettaessa järjestelmän toimintaa. Malli poh­

jautuu Petri-verkkoihin.

2.1.2 Suorituskykytutkimus

Osatutkimuksessa on kehitetty kaksi erilaista suorituskykymal—

lia. Ensimmäisen avulla on kartoitettu äänestystapahtuman synkronointiin liittyviä riippuvuussuhteita ja todettu, että tietyissä tilanteissa voidaan äänestyspyyntöjä puskuroimalla saavuttaa merkittäviäkin ajallisia säästöjä/5/. Toinen malli rakentuu suunnitellun käyttöjärjestelmän puitteisiin ja on tarkoitettu sovellutusohjelmien sisäisen synkronoinnin ja ajoitusvaatimusten tarkasteluun /6/. Tämän järjestelmämallin avulla tutkitaan laitteisto— ja ohjelmistoratkaisujen vaiku­

tusta käytettävissä olevaan laskentatehoon ja sen jakautumi­

seen. Esimerkkinä käsitellään erityisesti numeerisesti ohja­

tun sorvin ohjausalgoritmin suoritusta ASMOS- käyttöjärjestel­

män alaisuudessa. Erityistä huomiota kiinnitetään työstöpro­

sessin asettamien reaaliaikavaatimusten toteutumiselle.

Järjestelmämallin avulla tutkitaan, millä rinnakkaisuuden asteella ohjausalgoritmin suoritusnopeus on suurin eri

työstötilanteissa. Systeemiohjelmien kuormituksen suhteelli­

nen lisääminen pienentää suoritusnopeutta, jos algoritmin hajauttaminen rinnakkaisiin osiin viedään liian pitkälle.

2.1.3 Sovellutusympäristötutkimus

Osatutkimuksessa on kartoitettu tyypillisen sorvin laskenta—, tliantarkkailu- ja ohjausalgoritmien ominaisuuksia sekä aika- ja luotettavuusvaatimuksia. Tämä osa on tehty yhdessä Lenin­

gradin Sähköteknillisen instituutin mikroprosessoripohjaiseen työstökoneohjaukseen erikoistuneen työryhmän kanssa. Lisäksi on kehitetty ASMOS—käyttöjärjestelmään soveltuva sovellutus­

ohjelma, joka pyrkii sorvin käyttöturvallisuuden lisäämiseen sekä toimintavirheistä johtuvien seisokkien vähentämiseen.

Virheiden lukumäärää voidaan vähentää kappaleohjeImien kehi- tystä yksinkertaistamalla, ohjauspaneelilta syötettyjen

parametrien ja käskyjen oikeellisuuden tarkastamisella sekä työstökoneen kunnon jatkuvalla tarkkailemisella /7,8/.

2.1.4 Koelaitteiston kehittäminen

itteisto on suurimmalta osaltaan ollut jo valmiina pro­

jektin alkaessa. Projektin kuluessa on laitteistoa testattu ja joitakin osia on paremman toimivuuden vuoksi jouduttu uusi­

maan. Testausta varten on digitaalitekniikan laboratorioon hankittu logiikka—analysaattori sekä emulaattori Intellec—

kehityslaitteistoon.

2.2 Rinnakkainen tutkimus

Moniprosessoriympäristössä algoritmien rinnakkaisuus on vält­

tämättömyys, muutoin voitaisiin hyödyntää vain yhtä prosesso- Tämä voidaan tulkita koskemaan myös varmennettuja järjes­

telmiä, joissa prosessorit suorittavat samaa tehtävää. Näissä­

kin käsittely on rinnakkaista.

Varsinaiset moniprosessorijärjestelmät voidaan Flynnin mukaan jakaa kahteen osaan sen mukaan, suoritetaanko samaa käskysek- venssiä usealle eri datalle (SIMD) vai suoritetaanko samanai­

kaisesti myös eri käskyjä (MIMD). Edellinen voidaan määritel­

lä selkeästi, mutta jälkimmäinen jakautuu vielä useaan osit­

tain päällekkäiseen alaryhmään /9/.

Yleisin kriteerio luokiteltaessa MIMD-järjestelmiä on proses­

sorien keskinäisen liitännän väljyys. Yhteinen muisti sekä yhteinen syöttö/tulostuslaitteisto viittaisivat tämän mukaan lujaan sidokseen ja kommunikoinnin rajoittaminen vain tiet­

tyyn kommunikointikanavaan viittaa väljään sidokseen. Lipovs- kin /3/ mukaan oleellinen ero on kuitenkin siinä, että väljäs-

liitetyllä systeemillä ei ole keskitettyä systemin tilaa, vaan tila muodostuu kunkin prosessorin tilojen "summana".

Perusteluna väitteelleen Lipovski mainitsee mm. muistinhal- 1intayksiköt. Näiden avulla voidaan kunkin prosessorin tila suojata muilta yhtä tehokkaasti kuin erityistä kommunikoin­

tikanavaakin käyttäen, vaikka muisti olisikin laitteistota­

solla kytketty kaikkiin prosessoreihin tasavertaisesti. Tämä asettaa käyttöjärjestelmille entistä suuremman merkityksen vikojen leviämistä estettäessä.

Aiempien jaotteluiden tilalle ehdotetaan lokaalisuuksiin pe­

rustuvaa jaottelua. Lokaalisuus merkitsee varsinaisesti saan- tioikeuksia. Prosessorilla voi olla saantioikeudet tiettyihin oheislaitteisiin, muistiin tai yhteisiin kommunikointikana—

vün» Nämä kuuluvat tällöin kyseisen prosessorin lokaliteet—

t-i-j-1"1, Samat laitteet voivat kuulua muidenkin prosessorien lo—

kaliteettiin. Lokaalisuus voi olla staattista tai dynaamista.

Esimerkiksi muistiavaruuden hallinnassa dynaaminen lokaali—

suus tarkoittaa, että yhteismuistia voidaan tarpeen mukaan jakaa kullekin prosessorille lokaalimuistiksi. Dynaamisen lokaalisuuden hyötynä on suuri joustavuus erilaisten tehtä­

vien suhteen; staattinen lokaalisuus edellyttää laitteistol­

ta vähemmän, lisäksi operaatiot ovat nopeampia. Kumpaakaan ei

voi asettaa yleisesti toisensa edelle vaan molempia voidaan käyttää saman järjestelmän eri osissa.

Moniprosessoritutkimus on viime aikoina ollut voimakasta sel­

västi nähtävissä olevien tehokkuuden ja luotettavuuden kasvun vuoksi. Suurin alan tutkimuskeskus on ollut Carnegie-Mellon yliopisto Yhdysvalloissa kolmen koelaitteiston turvin. Tut­

kimusta on tehty myös muualla ja sovellutuskohteet ovat hyvin vaihtelevia. Seuraavaksi esitetään lyhyt katsaus muutamiin laitteistoihin, niiden ohjelmistoon ja päämotiiveihin.

2.2.1 C.mmp

C.mmp on Carnegie-Mellon yliopiston suunnittelema laitteisto /10/. Se koostuu kuudestatoista PDP-11 minitietokoneesta, jotka liittyvät yhteismuistiin ristiinkytketysti siten, että muisti jakautuu kuuteentoista lohkoon ja muistista luku voi tapahtua yhtäaikaisesti eri lohkoista. Laitteiston maksimi­

suorituskyky on 6 MIPS.

Projektin varsinaisena ansiona on pidettävä suunniteltua käyt­

töjärjestelmää tai käyttöjärjestelmän ydintä Hydraa, jonka ympärille on jo rakennettu useitakin täydellisiä käyttöjärjes­

telmiä .

Hydra ei tarjoa tavanomaisia käyttöjärjestelmän piirteitä, tiedostoja, komentokieltä tai edes ajoitinta. Hydra tarjoaa olosuhteet, joissa käyttäjän on helppo kirjoittaa ohjelmia, j°tka sisältävät nämä ominaisuudet. Perustyökaluna on käytet­

ty niinkutsuttuja oikeuksia; tietyllä ohjelmalla tai ohjelman osalla on oikeudet vain määrättyihin muistialueisiin ja mää­

rättyihin oheislaitteisiin sekä määrättyihin muihin ohjel­

miin. Näillä kutsutuilla ohjelmilla taasen saattaa olla oikeudet joihinkin eri ohjelmiin tai resursseihin. Ohjelmia kutsutaan oikeuksien avulla, varsinaisia osoitteita ei ole käytössä.

Kun ohjelmoija pyrkii sallimaan kullekin ohjelmalohkolle

mahdollisimman vähän oikeuksia, voidaan vikojen leviäminen eristää. Sovellutusohjelmoijalle suodaan mahdollisuus luoda uusia operaatioita ja tietotyyppejä, jotka ovat täysin

tasavertaisia Hydran valmiiksi toteutettujen operaatioiden kanssa. Sovellutusohjelmoijalle on pyritty jättämään

mahdollisimman useat sovellutusohjelmien suoritustapaan liittyvistä päätöksistä. Tämä on eräs olennaisin menetelmä turvattaessa järjestelmän yleiskäyttöisyys.

Päätavoitteina Hydran suunnittelussa on pidetty symmetrisyyt­

tä sekä yleiskäyttöisyyttä. Näiltä osin voitaneen sanoa, että Hydra on vaikuttanut olemassa olevista käyttöjärjestelmistä eniten esiteltävän käyttöjärjestelmän lähtökohtiin ja työtä edeltävässä kirjallisuustutkimuksesta Hydraa koskevat rapor­

tit ovat muodostaneet suuren osan.

C.mmp-projektin jälkitarkastelusta /11/ voidaan luetella seu- raavat ansiot: Suunniteltu moniprosessori on symmetrinen ja tehokkuuteensa nähden edullinen. Hydra on käyttökelpoinen valine, jonka avulla voidaan ohjelmoida käyttöjärjestelmiä tavallisten sovellutusohjelmien tapaan. Hydra on prosesso­

rien suhteen symmetrinen. Toisin sanoen prosessorit suorit­

tavat tarvitsemansa käyttöjärjestelmäoperaatiot riippumatta muista prosessoreista.

Negatiivisia seikkoja on myös myönnetty: Laitteisto ei ole min luotettava kuin olisi toivottu. PDP-11:n pieni osoite- avaruus on osoittautunut haitalliseksi. Tavoitteessa osittaa C.mmp:tä toiminnallisesti erillisiksi laitteistoiksi ei ole onnistuttu. Käyttäjäystävällisyyteen ei ole kiinnitetty riit­

tävästi huomiota.

2.2.2 Cm*

Toinen Carnegie-Mellon yliopiston moniprosessoriprojekti on Cm* /12/. Laitteisto koostuu LSI-11 prosessoreista, jotka on kytketty toisiinsa siten, että kukin prosessori voi puhutella

toistensa paikallismuistia hierarkisesti järjestetyn kytkin- verkon avulla. Verkkoon kytkettyjen prosessorien määrällä ei ole käytännössä ylärajaa. Verkossa muistiin viittaus saattaa kestää eri pituisia aikoja riippuen siitä, kuinka monen sol­

mupisteen kautta muistiin viitataan. Verkko huolehtii kunkin prosessorin saantioikeuksien täyttymisestä. Kuvassa 1 esite­

tään Cm*: n rakenne kun järjestelmässä on viisi prosessoriryh—

mää. Kukin ryhmä voi sisältää kymmenen prosessoria. Oheislait­

teet liittyvät yksittäisiin prosessoreihin.

SS Hriocu/sTZfi

4-> St и ro MOST

Kuva 1 Cm*: n arkkitehtuuri

Käyttöjärjestelmän suunnittelussa on suurin huomio kiinnitet­

ty osoitusmekanismeihin. Tämä onkin luonnollista, kun lait­

teistoarkkitehtuuri poikkeaa tavanomaisesta. Osoitusmekanis—

mien osalta on tavoitteina pidetty seuraavia seikkoja; Osoi- tusmekanismien on tuettava modulaarista ohjelmankehitystä;

ohjelman osia on voitava kääntää toisistaan erillään. Tietora­

kenteiden tulee olla vaihtelevan pituisia. Muisti on kyettävä

suojaamaan laitteisto- ja ohjelraavirheitä vastaan. Ohjelmia ja muistissa olevaa tietoa on pystyttävä puhuttelemaan eri ohjelmista eri nimillä vaikka fyysiset osoitteet ovat samoja.

Cm*:lie on suunniteltu kaksi käyttöjärjestelmää: StarOS ja Medusa. Osoitustavoiltaan Medusa on näistä kahdesta yksin­

kertaisempi. Siinä on päähuomio kiinnitetty tehtävien väli­

sen rinnakkaisuuden aikaansaamiselle. Samaan kokonaisuuteen liittyvät tehtävät allokoidaan prosessoreille, jotka ovat osoituksellisesti mahdollisimman lähellä suoritettavaa ohjel­

makoodia ja toisiaan.

StarOS:ssa tavoitteita on pyritty saavuttamaan käyttämällä segmentoitua osoitusta ja oikeuksia Hydran tavoin. Proses­

sorit puhuttelevat muistia oikeuksien avulla ja muistikyt- kimillä tarkistetaan kunkin prosessorin oikeudet ja kutakin oikeutta vastaava fyysinen osoite; oikeuksia voi luonnolli­

sesti muuttaa ohjelmallisesti, mutta sallitut muutokset on tarkkaan rajattu.

Käyttöjärjestelmät tukevat prosessorien välistä kommunikoin­

tia ns. postilaatikko—operaatioiden avulla. Semaforioperaa—

tiot on toteutettu muistikytkimissä olevalla mahdollisuudel­

la lukita tietyn muistilohkon osoitukset operaation suori­

tuksen ajaksi. Väylien lukitseminen operaation ajaksi olisi järjestelmän kannalta liian raskasta.

2.2.3 C.vmp

C.vmp on suppeimmin raportoitu Carnegie Mellon yliopiston moniprosessoriprojekteista. Suunnittelun päämäärät voidaan esittää seuraavasti /13/:

-Järjestelmän tulee voida jatkaa toimintaansa huolimatta pysyvästä laitteistoviasta.

-Pysyvistä ja tilapäisistä virheistä huolimatta järjestelmä ei saa tuottaa virheellisiä tuloksia.

-Käyttäjälle ei tule olla tarpeellista tietää, että hän ohjelmoi vikasietoista tietokonetta.

-Virheen tulee olla korjattavissa lyhyen ajanjakson sisällä.

-Tosiaikaisissa sovellutuksissa ei laitteiston toiminta saa pysähtyä liian pitkäksi ajaksi.

-Laitteiston tulee kyetä toimimaan siten, että se voidaan huoltaa aktiivisena. Toisin sanoen on voitava poistaa viallinen moduuli ja korvata se toisella toiminnan aikana.

-Kustannusten minimoimiseksi on järjestelmä voitava koota valmiista moduuleista.

-Järjestelmässä on voitava joustavasti valita luotettavan tai suorituskykyisen vaihtoehdon välillä ohjelmallisesti tai käyttäjän toimesta.

Näitä ominaisuuksia on tavoiteltu kuvan 2 mukaisella arkkiteh­

tuurilla, jossa äänestys on toteutettu väylätasolla. Äänestä­

minen tapahtuu aina, kun prosessori puhuttelee väylää. Proses­

sorit voivat suorittaa tehtäviä itsenäisestikin väylä-äänes­

tyksistä riippumatta. Muutoin prosessorit suorittavat samaa ohjelmaa. Äänestysyksikkö muodostaa luotettavuuden kannalta kriittisen osan.

Kuva 2 C

2.2.4 SRI SIFT

SIFT (Software Implemented Fault Tolerance) on lennonohjaus- soveHutuksiin suunniteltu vikasietoinen moniprosessori /14/.

Ilmailualan vaatimukset ohjausyksiköiden luotettavuudelle ovat erittäin tiukat : sallitaan 10E-9 virhettä tunnissa kun yhtäjaksoinen käyttö ilman huoltoa on enintään kymmenen

tuntia. Laitteessa on prosessorit kytketty toisiinsa usean väylän avulla. Prosessori voi lukea muiden prosessorien muistia mutta voi kirjoittaa vain omaa muistiaan.

Tyypillisesti tehtävä suoritetaan useassa moduulissa ja kukin prosessori kirjoittaa tuloksen omaan paikallismuistiinsa.

Tulosta käyttävä prosessori lukee kunkin muistista ehdotuksen ja valitsee niistä enemmistön kannan. Äänestys toteutetaan siis ohjelmallisesti. Ohjelmien tulee toimia synkroonissa toistensa kanssa (50us), jotta tarvittavat tulokset olisivat valmiit äänestyksiin. Ajoittainen uudelleensynkronointi on tarpeen prosessorikorttien kellotaajuuksien pienten poikkea­

mien vuoksi.

Tulostus tapahtuu erillisten moduulien avulla ja syöttö/tulos- tus~toiminnot ovatkin arkkitehtuurin kriittinen osa. Luotetta­

vuus on suurelta osin riippuvainen näiden moduulien toteutuk­

sesta.

2.2.5 FTMP

FTMP (Fault Tolerant Multiprocessor) on edellisen tavoin suun­

niteltu lentokonesovellutuksiin /15/. Järjestelmässä moduulit liittyvät toisiinsa varmennetuilla väylillä ja ne on ryhmitel­

ty kolmikoiksi. Jokaisessa kolmikossa on äänestin, joka valit­

see enemmistön kannan edelleen toimitettavaksi. Kolmikoita ei ole muodostettu kiinteästi vaan ryhmittelyä voidaan ajonaikai­

sesti muuttaa, jos jokin prosessoreista vikaantuu.

Varsinaisesti järjestelmä toteuttaa seuraavassa luvussa tar­

kemmin esiteltävää hybridivarmennuksen periaatetta. Moduulien välinen kommunikointi on sarjamuotoista. Äänestykset suorite­

taan bitti kerrallaan laitteistollisesti täysin synkronoidus­

ta Välttämättä tarvittava yhteinen kellosignaali on kriitti­

nen järjestelmän toiminnan kannalta. Äänestävien ohjelmien erilaisuus ei ole mahdollista.

2.3 Koelaitteiston esittely

Tietokonejärjestelmien laitteisto11isen luotettavuuden ja tur­

vallisuuden lisäämiseksi on olemassa kaksi perusratkaisua:

staattinen ja dynaaminen varmennus. Staattisessa varmennukses­

sa on järjestelmän kokoonpano kiinteä ja virheiden vaikutus poistuu <errannaisuuden ja äänestyksien kautta. Dynaamisessa varmennuksessa voidaan laitteistokokoonpanoa muuttaa sen mu­

kaan, mikä osa vikaantuu.

Voidaan osoittaa, että molempien hyvät puolet saavutetaan hy- (N,S) varmennuksessa /16/. N moduulia muodostaa äänes­

tävän ryhmän ja S moduulia varayksiköiden joukon, joilla vi­

kaantuvat yksiköt voidaan korvata. Uudelleenjärjestely ei eittämättä keskeytä järjestelmän toimintaa.

Erilaisille varmennusmenetelmille voidaan esitellä tarkempi jaottelu ja ominaisuuksien määrittely /17/.

2.3.1 Laitteistoarkkitehtuuri

Sovellutuksissa, joissa Vikasietoisuus ja joustavuus korkean luotetavuuden ja suorituskyvyn välillä on tärkeä, vaikuttaa ilmeiseltä, että moniprosessoriratkaisu olisi soveltuvin. Rin­

nakkaiset tutkimusprojektit tukevat tällaista havaintoa. Ny­

kyiset ratxaisut vaihtelevat laitteistopohjäisestä äänestyk­

sestä ilman varayksiköitä ohjelmallisiin äänestyksiin varayk—

siköin. uC* on uusi yhdistelmä, jonka erilaiset ominaisuudet tarjoavat mahdollisuuden uusien sovellutusten kokeiluun.

uC* perustuu hybridivarmennukseen, jossa äänestäminen on to­

teutettu laitteistolla ja varayksiköiden käyttö pääosin ohjel­

mallisesti. Laitteiston toteutus pohjautuu digitaalitekniikan laboratoriossa MUMI projektin /4/ aikana saatuihin kokemuk­

siin. Laitteiston toteutuksessa on käytetty hyväksi teknolo­

gian nopeaa kehitystä ja mahdollisimman paljon valmiita kort—

tiyksiköitä. Yhteisen aikajaetun väylän käyttö suo tähän hyvät mahdollisuudet.

Tällä hetkellä koelaitteisto perustuu yhden kortin mikrotieto koneisiin, jotka sisältävät kaiken toiminnallisesti tarpeelli set osat: prosessorin, kellon, muistin, ja tarvittavat syöt­

tö/tulostuskanavat sekä liitynnän järjestelmän väylään. Vaih­

toehtoiset kortit sisältävät lisäksi kellopiirejä, tuen suo­

raa muistinsiirtoa varten sekä muita erikoispiirejä. Yhteinen väylä mahdollistaa useiden mikroprosessorien liittymisen sa­

maan järjestelmään tasavertaisina. Väylään voidaan passiivi­

sina komponentteina liittää muistikortteja ym.

Pääpiirteissään uC* koostuu neljästä mikrotietokoneesta, joi­

ta voidaan käyttää itsenäisinä tai suorittamaan yhteistä teh­

tävää. Prosessorit liittyvät äänestinyksikköön ja väylän kautta mahdollisesti passiivisiin lisäyksiköihin. Suurempi

järjestelmä voidaan koota useasta uC*-lohkosta, jolloin loh­

kot liittyvät toisiinsa lisäkorttien välityksellä löyhällä sidoksella.Kuvassa 3 on esitetty koejärjestelmän lohkokaavio.

MULTIBUS

VOTER

PROCESSOR (SBC 80/05) PROCESSOR

(SBC 80/05) (SBC 80/05) PROCESSOR (SBC 80/05)

PROCESSOR

input/output

SYSTEM (SBC 517) COMMON MEMORY

APPROVED OUTPUT

Kuva 3 Koelaitteisto

Prosessorikortteina käytetään Intelin 80/05 kortteja, joissa on keskusyksikkönä 8 bittinen 8085 prosessori, puoli kilota­

vua paikallista RAK-muistia, neljä kiloa ROM-muistia väylälo- yiikka sekä 24 rinnakkaislinjaa, joista 20 on käytössä äänes- tinliitäntää varten.

Yhteisväylänä on aikajakoinen Intelin multibus, joka sallii 1-15 aktiivista prosessoria, isäntää. Aikajaon priorisointia varten on laboratoriossa rakennettu erityinen kytkentä, joka jakaa väylän aikaa neljälle prosessorille kiertävän prioritee­

tin mukaisesti /18,19/. Kiertävä prioriteetti on äänestysti­

lanteissa suorituskyvyn kannalta tärkeä jotta mikään proses­

sori ei jää toisista jälkeen /б/.

Yhteisinuistikortti sisältää tällä hetkellä kuusitoista kilo­

tavua RAM-muistia ja kuusitoista kilotavua ROM- muistia.

Syöttö/tulostuskortti suo mahdollisuudet liittyä keskeytys- pohjaisesti tavanomaisiin oheislaitteisiin.äänestin on lii­

tetty kaikkiin neljään prosessoriin. Vain kolme osallistuu aktiivisesti äänestykseen. Prosessorien jako järjestetään ohjelmallisesti. Kun jokin prosessori vikaantuu voidaan edel­

leen ohjata kolme prosessoria äänestyksiin.

2.3.2. Äänestin

Äänestin on laitteiston kannalta kriittinen osa. Sen vioittu­

minen pysäyttää koko laitteiston toiminnan. Tarkasteltaessa laitteiston luotettavuutta on äänestin sarjassa muiden osien kanssa. Näinollen tulee äänestiinen luotettavuuteen kiinnittää erityistä huomiota. Luotettavuuden lisäämiseen on pyritty minimoimalla komponenttien määrä.

Mikroprosessorien tyypillinen sananpituus on kahdeksan bit­

tiä. On siis luonnollista valita äänestyksen pohjaksi juuri tavu. Tämä lähestymistapa sisältää samalla selviä etuja luo­

tettavuuden kannalta verrattuna bitti kerrallaan tapahtuvaan tarkastukseen /20/.

Äänestimen tilakaavio on esitetty kuvassa 4 /17/. Järjestelmä käynnistyy tilassa 0. Kun ensimmäisellä prosessorilla on ää- nestyspyyntö, se antaa DV—signaalin ja äänestin siirtyy ti­

laan 1. Kun muut prosessorit äänestävät, ja tulokset ovat toi­

sistaan poikkeavia, pysytään tilassa 1. Jos kaksi tulosta on keskenään yhtäpitäviä, siirrytään tilaan 2. Reset-signaalilla päästään kaikista tiloista tilaan 0. Reset—signaalin tulee tällöin tulla ainakin kahdelta prosessorilta. Äänestimestä on tehty tarkempi tilakaavio Petri-verkkoja käyttäen /21/.

P0WER-0N RESET

RESET RESET

AGREEMENT RESULT OUTPUT

Kuva 4 Äänestimen tilakaavio

Äänestimestä saadaan vikatilaston ylläpitämiseksi tietoja kun­

kin prosessorin äänestysvirheistä. Kahdeksan bitin tilarekis­

terissä on kunkinhetkinen tilanne siitä, mitkä prosessorit ovat äänestäneet ja onko jokin tietty prosessori ollut muiden kanssa samaa mieltä. Prosessorit voivat halutessaan lukea tilarekisterin tiedot.Äänestin generoi keskeytyksen kullekin prosessorille, kun kaksi prosessoria on äänestänyt samoin.

Keskeytysrutiinissa prosessorit lukevat tilarekisterin ja suo­

rittavat tilanteen edellyttämät toimenpiteet. Kolmannen pro­

sessorin viipyessä liikaa, toteaa ohjelma tämän virheeksi.

2.3.3. Koelaitteiston puutteet

Laitteisto tulisi suunnitella yhteistyössä käyttöjärjestelmä- suunnittelun kanssa. Edellisen luvun moniprosessorikatsaukses- sa on havaittavissa laitteistojen tukevan käyttöjärjestelmiä erittäin tiiviisti. Edellä esitetyssä koelaitteistossa on tässä valossa havaittavissa joitakin selviä puutteita, joita ilman ei voi ajatella ohjelmoitavan todella vikasietoista käyttöjärjestelmää. Nämä puutteet keskittyvät lähinnä muistin­

hallintaan ja väylän sekä keskeytyspalveluiden valvontaan.

Useimmissa moniprosessorijärjestelmissä ja monissa yksiproses- sorijärjestelmissäkin kiinnitetään käyttöjärjestelmätasolla erittäin paljon huomiota virheiden leviämisen estämiseen.

Yleisin leviämistapa tiukasti kytketyssä systeemissä ja moni- ajoisissa yksiprosessorijärjestelmissä on virheellinen yhteis- muistiin viittaus. Tämä voidaan usein estää rajoittamalla kun­

kin ohjelmanosan kirjoitus- ja lukuoikeuksia. Kun tähän yhdis­

tetään käyttöjärjestelmäkeskeytys virheellisen viittauksen seurauksena, voidaan suurin osa tällaisista virheistä estää.

Käyttöjärjestelmässä ajoitin tarkkailee useita käyttöjärjes­

telmän toimintoja. Ajoittimen toiminta on tällöin kriittinen järjestelmän toiminnan kannalta. Ainoa tapa valvoa perusoh­

jelmiston toimintaa on laitteiston avulla. Väylä on samaten resurssi, jonka varaustilaa voidaan valvoa vain laitteiston avulla. Väylän osalta voitaneen lisäksi todeta, että huomattavasti luotettavampi ratkaisu olisi kolminker­

tainen äänestävä väylä. Koska tämä ratkaisu ei vaikuta ohjelmistoon, ei sitä tarkastella enemmälti.

Suunnitellussa käyttöjärjestelmässä on oletettu, että lait­

teisto tarjoaa puuttuvat piirteet. Ei ole mielekästä tutkia käyttöjärjestelmää, joka on koelaitteistolle paras mutta yleisesti ottaen puutteellinen. Käyttöjärjestelmän suunnit­

telussa ei kuitenkaan pyritty ottamaan kantaa puuttuvien piirteiden toteutustapaan ja suunniteltu virhestrategia on näiltä osin jäänyt avoimeksi.

3 RATKAISUN LÄHTÖKOHDAT

Algoritmien välinen suorituksellinen riippumattomuus on rin­

nakkaisuuden edellytys. Riippuvuusehdot jakavat algoritmit osittain riippumattomiksi; algoritmit voidaan jakaa osiin,

jolloin kussakin osassa on keskinäistä rinnakkaisuutta. Reaa­

limaailman tapahtumat ovat tavallisesti useallakin tasolla rinnakkaisia. Tietokonealgoritmeille voidaan kuitenkin osoit­

taa /22/, että rinnakkaisuus ei ole tehtävän suorituksen kannalta välttämätöntä; kaikki ongelmat, jotka ovat ratkais­

tavissa usealla Turingin koneella ovat ratkaistavissa myös yhdellä Turingin koneella.

Tehtävien suorittamisesta rinnakkaisin algoritmein on saavu­

tettavissa kahdenlaista hyötyä: rinnakkaisia algoritmeja voi­

daan suorittaa samanaikaisesti usealla prosessorilla, jolloin suoritusnopeutta tai luotettavuutta voidaan lisätä. Yksipro- sessoriympäristossäkin voidaan moniohjelmoinnilla saavuttaa suurempaa modulaarisuutta sekä tehtävänläheisyyttä, kun ongel­

ma on selvästi jaettavissa rinnakkaisiin osiin /23/.

Olennaisin vaikeus rinnakkaisuuden aikaansaamisessa on edel­

täjä/seuraaja-suhteiden aiheuttamien synkronointivaatimusten virheetön täyttäminen. Synkronointi osoittautuu usein niin raskaaksi ainakin von Neumanin arkkitehtuurin tietokoneilla, ettei rinnakkaiskäsittelystä saavuteta tavoiteltua hyötyä Varsinaisen rinnakkaiskäsittelyn ohella voidaan moniproses­

sorijärjestelmiä käyttää ohjelmien suorituksen varmentami­

seen. Tähän uC*-laitteisto suo hyvät mahdollisuudet. Tämän tutkimuksen eräänä tavoitteena on tutkia varmentamisen ja suorituskyvyn välistä riippuvuutta; pyritään varmentamaan ohjelmien toiminta kriittisiltä osiltaan äänestimen avulla

ja muilta osin voidaan tehtävät suorittaa rinnakkain.

Nämä vaatimukset luonnollisesti edellyttävät käyttöjärjestel­

mältä suurta joustavuutta ja luotettavuutta, mutta johtavat

sovellutusohjelmien kannalta halutunasteiseen turvallisuuden ja suorituskyvyn väliseen kompromissiin. On erittäin suota­

vaa, että tämä rajanveto on riippumaton käyttöjärjestelmästä.

Tämä lisää käyttöjärjestelmän ja laitteiston yleisyyttä.

3.1 Tavoitteet ja rajoitukset

Tietokonejärjestelmä on selkeimmin määritelty, kun esitetään sen syöttö/tulostus-käyttäytyminen. Tieto-ohjaus /24/ on mene­

telmä, joka sopii hyvin tämänkaltaiseen ajatteluun. Puhdas tieto-ohjaus käskytasolle asti toteutettuna edellyttää lait­

teistolta erityisominaisuuksia ollakseen tehokasta. Tieto-oh­

jauksen simulointi tavanomaisilla suoritusohjatuilla tieto­

koneilla saattaa aiheuttaa useiden satojen konekäskyjen lisä- kuormituksen jokaista operaatiota kohden /25/. Tieto-ohjauk­

sen periaatteita voidaan kuitenkin käyttää tehtävä tai prose—

duuritasolla, edellyttäen, että peräkkäisrakenteiset tehtävät riittävän pitkiä suhteessa lisääntyvään järjestelmäkuor—

mitukseen.

uC*“laitteistolle suunniteltu ensimmäinen ohjelmistoarkkiteh­

tuuri ja sitä tukeva käyttöjärjestelmä uCAOS /26/ jakoi sovel­

lutusohjelman dataverkoiksi keskeytyskäsittelyn mahdollista­

miseksi ja reaaliaikavasteiden parantamiseksi puhtaaseen tie­

to-ohjaukseen verrattuna. Verkot synkronoitiin tavanomaisesti semafoorien avulla mutta dataverkkojen sisäinen synkronointi pohjautui puhtaasti tieto—ohjauksen ohjelmalliseen simuloin­

tiin. Järjestelmä tuki puskuroituja keskeytysohjattuja syöt­

tö/ tulos tus—toiminto ja mutta tehtävien ajoitus ei sallinut poikkeuksia.

Strategia toimii hyvin varsin monissa tehtävissä. Jos sovel­

lutustehtävän asettamat reaaliaikarajoitukset ovat riittävän tiukat, ei vasteaikojen toteutumista voida kuitenkaan taata.

Suunniteltu uusi Käyttöjärjestelmä, ASMOS (A Symmetrie Multi­

tasking Operating System), joka tässä kirjoituksessa kuvataan

pyrkii edellisestä poiketen lähinnä vastaamaan aiotulla sovel­

lutusalueella ominaisiin tiukkoihin reaaliaikavaatimuksiin.

Vasteaikoja parannetaan siten, että osoitetaan virtuaalinen UC*—laitteisto jokaiselle dataverkolle. Tämä tapahtuu siten, että kussakin prosessorissa vuorotellaan eri verkkojen

suoritusta pienin aikavälein. Tällöin voidaan taata jokaisen verkon eteneminen lähes jatkuvasti. Verkkojen keskinäinen synkronointi on toteutettu tavanomaisin semaforein.

Verkkojen sisäistä rakennetta on prosessorien vähäisen mää­

rän ja äänestyksien vuoksi rajattu yhteen rinnakkaiseen ta­

soon vaadittavan kirjanpidon vähentämiseksi. Tämä ei tuo rakenteille varsinaisia rajoituksia, koska uusien verkkojen avulla voidaan saada aikaan useamman tasoista rinnakkaisuut­

ta. Rajoituksien vuoksi puhutaan jatkossa kuitenkin tehtävä- listoista verkkojen sijasta.

Ominaisena piirteenä ASMOS—käyttöjärjestelmässä on pyritty saavuttamaan mahdollisimman suuri luotettavuus ja näin takaa­

maan sovellutusohjelmille mahdollisimman suuri turvallisuus ja luotettavuus. Tämän tavoitteen saavuttamiseksi eräs pää­

asiallinen menetelmä on käyttöjärjestelmän symmetrisyys ja hierarkinen vikastrategia.

3.2 Määritelty ohjelmistoarkkitehtuuri

Ohjelmistoarkkitehtuuri määräytyy selkeimmin sen mukaan, miten sovellutusohjelmoijan tulee ohjelmansa suunnitella.

Tässä kappaleessa esitetään järjestelmä ohjelmoijan näkö­

kulmasta. Kirjallisuustutkimuksen ja ohjelmistoarkkiteh­

tuurin suunnittelun jälkeen tehtiin välittömästi alustava sovellutusohjelmoijan opas tavoitteena, että käyttöjär­

jestelmästä näin tulisi mahdollisimman helppokäyttöinen.

Lopulliseen oppaaseen on jouduttu tekemään verrattain vähän muutoksia, joten ratkaisua voidaan pitää onnistuneena.

3.2.1 Ohjelmien yleisrakenne

Käyttäjän suorittama ohjelmointityö jakautuu kahteen toisis­

taan selvästi erottuvaan osaan: tehtäviin ja tehtävälistoi- hin.

Tehtävät ovat tarkasti peräkkäisrakenteisia PLM- tai assem- bly-kielisiä ohjelmia. Tehtävissä voidaan käyttää liitteenä olevassa sovellutusohjelmoijan oppaassa esitettyjä käyttö- järjestelmäoperaatioita. Tehtäväproseduureihin ei saa liittyä parametreja vaan tehtävien keskinäinen kommunikointi tapahtuu joko käyttöjärjestelmäoperaatioita tai yhteisiä muuttujia hyväksikäyttäen

Tehtävistä kootaan rajoitetusti rinnakkaisrakenteisia tehtä- välistoja, jotka määrittelevät kullakin listalla olevien

tehtävien keskinäisen synkronoinnin ja prioriteetin. Tehtävä- lista aktivoidaan käyttöjärjestelmäoperaation avulla josta­

kin tehtävästä. Järjestelmässä voi olla samanaikaisesti yksi tai useampia aktiivisia tehtävälistoja. Tehtävälistojen vä­

liseen synkronointiin on olemassa valmiit käyttöjärjestelmä- operaatiot .

3.2.2 Tehtäväluokat

Tehtävät voidaan jakaa eri luokkiin niiden tarvitsemien re­

surssien ja kutsumekanismin perusteella. Äänestävät tehtä­

vät, i/o-tehtävät, laskentatehtävät, synkronointitehtävät ja keskeytysaliohjelmat ovat käyttöjärjestelmän tukemat tehtävä- luokat. Kukin tehtävä voi kuulua vain yhteen luokkaan. Luok- kamäärittely suoritetaan tehtävälistoissa liittämällä tehtä­

vän nimen yhteyteen luokan nimi.

Äänestävät tehtävät käynnistetään aina kolmessa reaaliproses- sorissa. Tästä syystä tulee koodin poikkeuksetta olla joko vapaakäyntistä tai muuttujien tulee sijaita paikallismuis- tissa. Äänestäminen suoritetaan käyttöjärjestelmäproseduurin avulla. Proseduuri palauttaa varmennetun äänestystuloksen ja

toteuttaa tarvittavan synkronoinnin eri prosessorien kesken.

On poikkeustapauksissa mahdollista käynnistää jokin tehtävä- lista esimerkiksi vain yhdessä prosessorissa. Tällainen poik­

keus ei ole sallittu listoissa, jotka sisältävät äänestys- tehtäviä .

Jollei tehtävälle varata äänestintä, sille voidaan tehtävä- listassa varata jokin muu resurssi. Käyttäjä määrittelee sovellutusohjelman käyttämät jakamattomat resurssit 1-20.

i/O-tehtävän tyyppiin liitetään kunkin tehtävän käyttämän resurssin numero. i/O-tehtävä tai tavallinen laskentateh­

tävä, jolle ei ole varattu mitään resurssia, se käynnistetään vain yhdessä prosessorissa.

Keskeytysaliohjelmiin hypätään laitteistokeskeytysten tulles­

sa. Keskeytysohjelmia käytetään, jotta sovellutusohjelmoija saisi äänestystehtäville puskuroituna koherentteja syöttö­

tietoja siinä tapauksessa, että syöttö tapahtuu erillisenä kaikille prosessoreille. Muutoin ei voida taata, että syöt­

teet otetaan riittävän samanaikaisesti. Prosessin ohjauksessa tämä voi johtaa prosessorien erimielisyyteen äänestettäessä vaikka varsinaista virhettä ei olisi sattunutkaan /5/.

Synkronointitehtävät on tarkoitettu listan tehtävien keski­

näiseen synkronointiin sekä listojen välisten synkronointi- operaatioiden sijaintipaikoiksi. Synkronointitehtävä suorite­

taan aina jokaisessa listaa suorittavassa prosessorissa, kuitenkin siten, että ennen tehtävän aloitusta kaikkien edeltävien tehtävien suorituksen tulee olla merkitty päät­

tyneeksi. Synkronointitehtävien tulee olla vapaakäyntisiä.

3.2.3 Tehtävälistat

Erilliset tehtävät kootaan tehtävälistöihin, joilla määrätään kullakin listalla olevien tehtävien keskinäinen suoritusjär­

jestys ja prioriteetti. Kunkin tehtävälistän suorituksesta vastaa virtuaalinen uC*—järjestelmä. Taulukossa I on esitetty tehtävälistän yleinen rakenne :

Taulukko I Tehtävälistan yleinen rakenne

$ INCLUDE (STRUCT.DEF) /‘haetaan literally-maaritteet*/

DECLARE listname (length) LISTDEFINITION INCLUDING length LINES,

tasktype.taskname tasktype.taskname tasktype.taskname LISTEND

Parametri length osoittaa tehtävien lukumäärän, listname ja taskname ovat sovellutusohjelmoijan valitsemia nimiä.

Tasktype voi olla jokin seuraavista: SYNCHRONIZE VOTE

10 resource number PLAIN

Ajovaiheessa tehtävälistän sisäinen suoritusjärjestys muodos­

tuu seuraavasti: Käyttöjärjestelmä antaa tehtäviä suoritetta­

vaksi prosessoreille pääsääntöisesti tehtävälistan mukaisessa järjestyksessä. VOTE-tyyppinen tehtävä annetaan kolmelle en­

sin hakeneelle ja synkronointitehtävä kaikille tehtävälistää suorittaville prosessoreille. Synkronointitehtävän suoritus aletaan kun kaikkien edeltävien tehtävien suoritus on päätty­

nyt. Rinnakkain suoritettavat tehtävälistät voidaan synkronoi­

da keskenään tehtävistä kutsuttavien käyttöjärjestelmäoperaa—

tioiden avulla.

3.2.4 Käyttöjärjestelmäoperaatiot

Käyttöjärjestelmä sisältää sovellutusohjelmoijan käytössä ole­

via proseduureja. Proseduurit jakautuvat neljään pääosaan:

tapahtumajärjestykselliseen synkronointiin, äänestämiseen, reaaliajan valvontaan ja ylläpitoon sekä tavanomaisien syöt­

tö/ tulostuslaitteiden tukeen.

Synkronointioperaatiot sisältävät mahdollisuuden käynnistää jokin tehtävälista sekä määrätä tälle listalle asetettavan virtuaaliprosessorin laskentateho. Käynnistys ja laskentate­

hon asetukset ovat paikallisia kullekin prosessorille joten operaatiot tulee suorittaa jokaisessa prosessorissa. Tämä ta­

pahtuu luonnollisimmin jos operaatiot suoritetaan aina synk- ronointitehtävissä. Poikkeuksen tälle muodostaa, jos tehtävä- listassa on jokin muita selvästi raskaampi tehtävä. Tällöin voidaan vastaavan virtuaaliprosessorin tehoa tehtävän alussa olevalla operaatiolla kasvattaa. Jos kasvun halutaan olevan tilapäinen tulee laskentatehoa jälleen laskea tehtävän lopus­

sa.

Synkronointioperaatioihin kuuluvat tavanomaiset semafori- operaatiot, joiden vaikutukset riippuvat olennaisesti siitä, sijaitsevatko semaforit paikallis- tai yhteismuistissa ja, minkä tyypin tehtävästä operaatiota kutsutaan. Vektoreiden jakamattomiin siirtoihin varattu operaatio voitaneen lukea synkronointiin liittyviksi.

Äänestykseen on käytettävissä kaksi operaatiota. Tavanomai­

sesti käytetty suo mahdollisuuden asettaa tavu äänestimeen ja odottaa vahvistettua tulosta. Äänestin odottaa kahta yhtäpitä­

vää tulosta ennenkuin tavu syötetään ulos. Operaatio palaut­

taa ohjauksen kutsujille kun kaikki kolme prosessoria ovat äänestäneet. Jos kolmas äänestys viipyy laukeaa äänestimen aikavalvonta. Toinen äänestysoperaatio on tarkoitettu keskey- tysohjelmien käytöön kriittisissä tilanteissa. Operaatio

keskeyttää meneillään olevan äänestyksen ja keskeytysäänes- tyksen jälkeen palauttaa aiemmat arvot äänestimeen palauttaen samalla ohjauksen keskeytysohjelmalle.

Reaaliaikaan liittyvät operaatiot mahdollistavat prosesso­

rien ylläpitämän reaaliajan synkronoinnin, tehtävän keskeyt­

tämisen määrätynpituisen viiveen ajaksi sekä aikavalvonnan asettamisen. Jos aikavalvontaa ei poisteta ennen ajan lop—

puunkulumista aiheuttaa käyttöjärjestelmä keskeytyksen käyt­

täjän määrittelemään valvontarutiiniin.

Syöttö/tulostus—laitteiden tukiohjelmisto toimii puskuroi­

tujen rivipohjäisten siirtojen pohjalta. Tulostettaessa siirretään rivi välittömästi puskuriin, josta se taustapro—

sessoinnin avulla siirretään tulostuslaitteelle. Syöttölait- t-ei.lta voidaan myös lukea rivi kerrallaan, jos puskuriin on syötetty kokonainen rivi. Muutoin operaatio odottaa tausta- prosessorin täyttäessä rivin loppuun. Reikänauhanluki jan ollessa kyseessä pyrkii taustaprosessi pitämään puskurin

jatkuvasti täytenä kytkemällä sitä sopivasti päälle ja pois.

Käyttöjärjestelmä huolehtii kaikkien synkronointiin liitty­

vien taulukoiden ja muuttujien initialisoinnista järjestelmää käynnistettäessä. Operaatiot alustavat itseänsä toiminnal­

lisesti tämän jälkeen.

4 KÄYTETYT SUUNNITTELUMENETELMÄT

Kun Petri ensi kerran esitti paikkojen ja siirtymien verkkon­

sa /27/, oli tarkoituksena lähestyä rinnakkaisuutta täysin idealisoimattomassa muodossa. Myöhemmin Petri-verkkojen todel­

lisia käyttömahdollisuuksia esitettiin useissa kirjoituksissa /28,29,30/. häistä innostuneena useat ryhmät pyrkivät käyttä­

mään Petri-verkkoja kunnianhimoisempiin tavoitteisiin. Mones­

sa tapauksessa tämä johti kuitenkin käytännön kannalta liian yksityiskohtaisiin kuvauksiin ja monet tutkijat luopuivat verkoista. Menetelmiä on kuitenkin kehitetty /31/ ja muunnel­

tu. Käyttökelpoisia sovellutuksia on ollut ainakin seuraavil- la alueilla /32/: kemialliset prosessit, lakitiede, tuotanto­

linjat, tietokoneverkot, käyttöjärjestelmät, digitaaliset järjestelmät ym.

Tässä kirjoituksessa esitellään kehitetty Petri-verkkojen mo­

difikaatio, joka soveltuu yleisesti moniprosessorijärjestel­

mien ja rekursiivisen laskennan kuvaukseen. Formalismi esite­

tään yleisessä muodossa, jotta yhteydet muuhun Petri-verkko- tutkimukseen tulisivat selkeästi esille. Käyttöjärjestelmän mallittamiseen käytetään vain modifikaation pientä osajouk­

koa, eikä näinollen tämän luvun täydellinen ymmärtäminen ole jatkon kannalta välttämätöntä. Formaalit määritelmät esitel­

lään, jotta kuvauksien täsmällisyys tulisi selväksi. Lisäksi Petri“verhoista on useita eri versioita ja vain täsmällisistä määritelmistä käy ilmi, mitä analyyttisiä menetelmiä verkkoi­

hin voidaan soveltaa. Sivumäärä!sten rajoitusten vuoksi edel­

lytetään lukijan tutustuneen aiemmin Petri—verkkoihin. Muis­

tin virkistämiseksi esitetään kuitenkin pääseikat uudelleen.

4.1 Petri-verkko

Petri—verkko muodostuu kahdesta peruselementistä : paikoista ja siirtymistä. Paikka voidaan yhdistää siirtymään nuolella.

Nuolen suunnasta riippuen on kyseessä joko siirtymän syöttö- tai tulostuspaikka. Paikoissa voi olla merkkejä. Kuvassa 5 on

eräs Petri-verkko. Paikat esitetään ympyröinä ja siirtymät lyhyinä pysty— tai poikkiviivoina. Merkki esitetään paikassa olevana pisteenä. Merkkien sijoittelua verkossa sanotaan merkinnäksi.

Verkon dynaamisia ominaisuuksia kuvataan siirtämällä merkkejä (1. muuttamalla merkintää) seuraavien sääntöjen mukaisesti:

^ siirtymä on virittynyt, jos sen jokaisessa syöttopai—

kassa on nuolia vastaava määrä merkkejä 2 virittynyt siirtymä voi laueta

3 kustakin syöttöpäikasta poistetaan nuolia vastaava määrä merkkejä laukeamisen yhteydessä sekä lisätään tulostuspaikkoihin merkit vastaavasti

Kuvan 5a ylin siirtymä on virittynyt, alempi ei ole. Tämän siirtymän laukeamisesta seuraa kuvan 5b merkintä.

ГЛгкГЛ »LO

O d>H>±,

Kuva 6« erilaisia kontrollirakenteita Petri-verkoilla esitet­

tynä : peräkkäis—, rinnakkais—, ehto— ja toistorakenne

Petri-verkko voidaan määritellä formaalisti /33/:

Petri-verkko on viisikko P№=(P,T,I,O,M0), jossa:

P = [д » % , ...,pj ; paikkojen joukko T = £t, , tå ,...,tM) ; siirtymien joukko

I : PxT'"'« N ; syottofunktio (siirtymiin tulevat nuolet) O : PxT^ N ? tulostusfunktio (lähtevät nuolet)

M,, : P~ N ; alkumerkintä.

Syottofunktio ja tulostusfunktio voidaan vastaavasti esittää matriiseina l(t,p) ja O(t.p). Merkintä esitetään vektorina M(p). Siirtymä on viritetty jos Vp : M(p) > I(tvp).

Viritetyn siirtymän t, laukaisu merkinnästä M tuottaa uuden merkinnän M'

Vp: M'(p) = M(p) + O(t^p) - Kt^p)

Merkintä M on saavutettavissa, jos on olemassa sellainen lau- kaisusekvenssi, joka johtaa alkumerkinnästä merkintään M.

Verkko on rajoitettu, jos jokaisessa saavutettavissa olevassa merkinnässä on kutakin paikkaa kohden vähemmän kuin k+1 merk­

kiä, kun k on mielivaltainen kokonaisluku. Jos k=l sanotaan verkkoa turvalliseksi. Petri-verkko voidaan myös määritellä turvalliseksi lisäämällä viritetylle siirtymälle laukeamiseni—

to, jolloin siirtymä ei voi laueta/ jos johonkin tulostuspaik- kaan tulisi enemmän kuin yksi merkki.

Petri-verkkojen analysointia on tutkittu runsaasti. Kevyt esimerkki analysoinnista on viitteessä /32/. Viitteet /31,33/

tarkastelevat analysointia matemaattisesti vaativammin.

4.2 Modifioidut Petri-verkot

Useita sovellutuksia varten on Petri-verkkoja laajennettu eri tavoin. Tavoitteena on joko suurempi kuvausvoima tai tiiviim­

pi esitysformalismi ja läheisempi vastaavuus sovellutuskohtee­

seen. Varsin pienellä lisäyksellä, ns. inhibiittorinuolella voidaan verkon kuvausvoima kasvattaa Turing-koneiden luokkaan /34/. Tällöin niillä voidaan ratkaista kaikki ratkaistavissa

olevat ongelmat (periaatteessa). Inhibiittorinuoli estää siir­

tymän laukeamisen, jos vastaavassa paikassa on vähintään yksi merkki. Yleensä inhibiittoria ei kuitenkaan käytetä, koska se ratkaisevasti vaikeuttaa verkon ominaisuuksien analysointia.

Merkkeihin voidaan liittää yksilöllisiä ominaisuuksia. Täl­

löin puhutaan useimmiten väreistä. Riippuen siitä, miten vä­

rit vaikuttavat viritysehtöihin voidaan ne joskus palauttaa yleisiin Petri-verkkoihin /35/. Tämä muunnettavuus on tärkeä, koska näin voidaan käyttää hyväksi Petri-verkoille saatuja analyyttisiä tuloksia , mm. verkkojen elävyyden ja rajoittu­

neisuuden tutkimiseksi.

Laajempi esitys Petri-verkoista, näiden eri aliluokista ja laajennuksista on viitteessä /36/. Suomen kielellä on Petri- verkkoja esitelty kahdessa eri kirjoituksessa /37,38/.

4.3 Lokaliteetti Petri-verkko

Tietokonejärjestelmät yleensä ja moniprosessorijärjestelmät erityisesti koostuvat usein monesta samanlaisesta tai

samantapaisesta alijärjestelmästä, jotka voidaan toteuttaa samoin tai samanlaisin osin. Näiden osien toiminta ei aina ole itsenäistä, vaan tarvitsee keskinäistä synkronointia.

Petri-verkot ovat hyvä väline mallitettaessa rinnakkaisten järjestelmien ohjausta, mutta toiminnallisten osien samankal­

taisuutta ei voida hyödyntää tehokkaasti. Tämä haitta voidaan välttää sellaisella muunnetulla formalismilla, jossa samanta­

paiset verkon osat voidaan yhdistää sovittujen sääntöjen mu­

kaisesti päällekkäin. Seuraavassa esitetään eräs tällainen formalismi ensin yleisessä muodossaan, ja tämän jälkeen eri­

koistapauksena edelleen tiivistetyssä muodossa. Tiivistetylle muodolle ei esitetä formaalia määritelmää, koska se halutaan käsittää vain piirrosteknillisenä muunnoksena tavallisista Petri-verkoista. Muunnosalgoritmi tavallisiin Petri-verkkoi­

hin esitetään.

Lokaliteetti Petri-verkko on kuusikko LPLÎ= ( P, T, L, I, О, M0 ) , jossa

р = [P, , Р2 , . . ., pj ; Т = {t, , tj_ » • • • » t«] ? L = , Ljl « • • • » lg) *

I : PxTxL'-'* N ; O : PxTxL^N

Me : PXL^ N ;

paikkojen joukko siirtymien joukko lokaliteettien joukko syöttöfunktio

tulostusfunktio alkumerkintä Siirtymä tj on virittynyt jos ja vain jos

v<V Vlk : Жрг1к> il(Pl.tj.lk>

Virittyneen siirtymän tj laukeamisesta merkinnässä M syntyy uusi merkintä M' siten, että :

Vp., VI k M'(p.,lk) =M(p.,lk) -Oip-.tj ,lk) - Kp-.tj ,ik)

LPM on turvallinen, jos siirtymä tj ei laukea, kun : s

3p. : ^(M<p.AK> ♦ 0<p. #t j »lk> - I(p.,t.,lk>) >1

-Myöhemmissä malleissa tarkastellaan vain turvallisia verkkoja.

-LPN on Petri-verkon laajennus siten, että jos /l/=1 niin LPN=PN.

Jatkossa ei algebrallista notaatiota enää käytetä. Tarkoitus oli lähinnä tuoda esille kuvauksen täsmällisyys. Tässä yhtey­

dessä on lisäksi syytä korostaa , että vastaaville notaatioil­

le on kehitetty erittäin runsaasti analyyttisiä tuloksia, joiden soveltaminen ei tuota mitään teoreettisia vaikeuksia.

Teknillisen korkeakoulun Digitaalitekniikan laboratoriossa on lisäksi parhaillaan kehitteillä analyyttisiä välineitä Petri- verkko jen tutkimiseen. Tulokset ovat helposti sovellettavissa

myöhemmin esiteltävien mallien formaaliin analysointiin. Tämä on ollut eräs päätavoitteita notaatiota kehiteltäessä.

Kuvassa 7 on esimerkkki eräästä yleisestä LPN-verkosta. Kaa­

riin liitetyt numerot vastaavat lokaliteetteja, ja merkkejä vastaavat lokaliteettimerkinnällä varustetut ympyrät. Laukea- misehtojen mukaisesti voi esimerkiksi alaoikealla oleva

siirtymä laueta. Merkin lokaliteetti vaihtuu ykköseksi ja seuraavaan paikkaan tulee näin kaksi ykköstä. Jos toinen näistä laukaisee ylemmän kahdesta mahdollisesta siirtymästä, tulee tulostuspaikkaan kakkosen lisäksi kolmonen ja seuraava siirtymä virittyy jne.

Kuva 7 esimerkki yleisestä LPN-verkosta

Sekä yleinen että turvallinen LPN on helppo muuntaa vastaa­

vaksi Petri-verkoksi. Sellaisissa sovellutuksissa , joissa paikallisuudella on suuri merkitys saadaan LPN-verkkojen käytöllä huomattavasti tiiviimpiä kuvauksia. Yksinkertainen muunnosformalismi on kuitenkin tärkeä, jotta säilytetään Petri-verkkojen analyyttiset ominaisuudet.

4.4 ALPN-verkko

ASMOS-käyttöjärjestelmän ja uC*: n tapauksessa ei tarvita kuin kaksi eri lokaliteettityyppiä, paikallinen tietylle prosesso­

rille tai yhteinen. LPN sinänsä tarjoaa mahdollisuudet huomat­

tavasti monipuolisempaan saantioikeuksien kuvaukseen. Symmet—

risyydestä on kuitenkin hyötyä, ja kuvausformalismia voidaan edelleen tiivistää. Kuvassa 8 on eräs Petri—verkko kuvattuna LPN-formalismi11a ja ALPN-formalismi11a, jossa Petri-verkko- jen symmetrisyys voidaan useissa tapauksissa hyödyntää vielä tarkemmin. Mitään yksinkertaista tapaa edetä LPN-kuvauksesta ALPM—kuvaukseen ei ole mielekästä esittää. Molemman kuvaus­

tavat ovat mielekkäimmin määriteltävissä esitettäessä muun­

nokset takaisin tavalliseen Petri-verkkoon. LPN-muunnos on ilmeinen algebrallisen esityksen pohjalta, seuraavaksi tar­

kastellaan ALPN-kuvauksen muuntamista takaisin Petri-ver- koksi. Kuvassa 8 on sekä tavallisia paikkoja että kahdella viivalla piirrettyjä ympyröitä. Edellisistä käytetään jatkos­

sa nimitystä tavallinen paikka ja jälkimmäisistä monitasoinen paikka.

Kuva 8 Samaa Petri-verkkoa vastaavat LPN- ja ALPN-kuvaukset.

verkko saadaan piirtämällä useita vastaavia tasoja ja yhdistelemällä näitä. Numerointi poistetaan.

Selkein tapa laajentaa ALPN-verkko (Abbreviated Locality Pet­

ri Net) Petri-verkoksi on piirtää samanlaiset erilliset ver­

kot, niinkutsutut tasot, vastaamaan jokaista lokaliteettia♦

Numeroidut kaaret jätetään kuitenkin piirtämättä. Tämän jäl­

keen yhdistetään eri tasoilla vastaavat tavalliset paikat toi siinsa ja poistetaan kerrannaiset siirtymät. Numeroidut kaa­

ret lisätään vielä numeron osoittamalla tasolla sijaitsevan vastaavan paikan ja kaikilla tasoilla sijaitsevien vastaavien siirtymien välille.

Alkumerkintä osoitetaan pienillä ympyröillä, joiden sisään lokaliteetti on merkitty. Jos lokaliteetin kohdalle on merkit ty "x", on kyseessä merkki joka tasolla. Turvallinen verkko edellyttää, että monitasoisissa paikoissa voi olla vain yksi merkki kutakin tasoa kohden. Tavallisissa paikoissa voi täl­

löin olla vain yksi merkki ja useimmiten lokaliteetin merkit seminen on turhaa. Lokaliteetti on näissä paikoissa useimmi­

ten vakio tai tilanne on muuten symmetrinen muiden tasojen kanssa. Muutoin ei ALPN-verkkoa piirrettäessä voida tavalli­

seen paikkaan tulevien tai lähtevien kaarten numerointia

jättää pois. Jätettäessä lokaliteetti pois käytetään merkkinä pistettä.

Kuva 9 Siirtymän laukeaminen ALPN-verkossa

Kuva 9 havainnollistaa ALPN-verkon suoritusta. Monitasoiset paikat virittävät siirtymän vain, milloin syöttöpaikkojen

merkit ovat samalla tasolla. Numeroidut kaaret käyttäytyvät kuitenkin kuten LPN-verkossa muuttamalla syöttopaikan ja vas­

taavasti myös tulostuspaikan tasoa. Kuvassa on siirtymällä tarvittava syöttömerkintä tasoilla 2 ja 3, mutta turvallisessa verkossa vain tasolla 3 voi laukeaminen tapahtua. Muutoin tu­

lisi paikkaan alava seminal la kaksi merkkiä tasolle 2.

Yksinkertaisen numeroinnin lisäksi kaarilla voidaan käyttää relaatioita. Tällä tavoin voidaan formalismilla kätevästi mallittaa esimerkiksi rekursiivista laskentaa. Rekursiivista kutsua vastaavalle kaarelle laitetaan numeroinniksi -1, joka osoitta, että tulostus tapahtuu yhtä alemmalle tasolle kuin syöttö. Paluukutsua vastaavalle kaarelle taasen asetetaan nu­

meroinniksi +1 jolloin paluu tapahtuu yhtä ylemmälle tasol­

le. Tasojen loppuessa ei kaaria ole.

Rekursiota on yritetty useilla tahoilla mallittaa Petri-verk- kojen avulla. Mallit eivät ole olleet formaalisti analysoita­

vissa. Tämä on toisaalta luonnollista, koska rekursion mallit­

taminen luonteeltaan edellyttää äärettömiä verkkoja. Ei kui­

tenkaan ole otettu huomioon, että käytännön tehtävissä tieto­

koneet ovat aina rajallisia ja olisi vain hyödyllistä kyetä rajaamaan mallissakin rekursiotasojen tai pinon koko. Edellä esitetyllä tavalla rekursiota mallitettaessa saavutetaan kahtaallista etua. Mallitus on yksinkertaista ja jos mallia halutaan analyyttisesti tutkia, voidaan (on pakko) asettaa pinon koolle äärellinen raja. Tarkemmin ei rekursiota tässä tarkastella, koska se ei jatkon kannalta ole välttämätöntä.

Laajemmin Petri-verkkojen yleistyksiä on käsitelty Petrin omassa koulukunnassa Saksan Liittotasavallassa /31/.

5 SOVELLUTUSOHJELMAKSIMERKKI

Työstökone on hyvä esimerkki nopeasta prosessista. Ohjausyksi kölle asetettavat turvallisuus- ja luotettavuusvaatimukset ovat suuret. väärät tulosteet saattavat johtaa suuriin talou­

dellisiin vahinkoihin tai jopa hengenvaarallisiin tilantei­

siin. Käyttökatkoksista on tavallisesti seurauksena työstettä vän kappaleen epäonnistuminen. Edellä mainittujen seikkojen vuoksi voidaan hybridivarmennettua järjestelmää pitää ihan­

teellisena laitteistoarkkitehtuurina /39/.

Työstökonealgoritmien ohjelmistolle asettamat vaatimukset ovat suuret. Koska kysymyksessä on tosiaikainen ohjaus, tulee käyttöjärjestelmän sallia rinnakkaiset prosessit. Tästä huo­

limatta saattaa jonkin tehtävän suoritus vaatia lähes kaiken käytettävissä olevan laskentatehon. Tällainen tehtävä on esimerkiksi kaarevien pintojen rataohjaus. Ajallisesti liian pitkä katko radan ohjauksessa johtaa karkeaan työstöpintaan.

ASMOS-käyttöjärjestelmän voidaan katsoa suoriutuvan yllämai­

nituista vaatimuksista ainakin seuraavaksi esitettävän numee­

risesti ohjatun sorvin tapauksessa.

Sorvia voidaan pitää hyvänä numeeristen työstökoneiden edus­

tajana. Sorvin ohjausohjelma tulkitsee kappaleohjelmaa rivi kerrallaan. Kappaleohjelman rivit on jaettu kenttiin, jolla kullakin on oma merkityksensä. Tietyillä kenttäkoodeilla voidaan määritellä rivin jatkuvan vielä seuraavalle fyysisel­

le riville. Ratapisteiden laskemisen lisäksi on ohjelman suo­

riuduttava terien ohjaamisesta ratapisteeltä toiselle, liik­

keiden valvonnasta, kommunikoinnista ohjauspaneelin kanssa sekä lukuisista kytkentätehtävistä.

Kuvassa 10 esitetään Petri-verkon avulla eräs mahdollinen numeerisesti ohjatun sorvin ajonaikainen ohjelmisto /8/. Ku­

van vaakasuorien siirtymien välissä olevat paikat vastaavat tehtäviä, kolminkertaiset paikat vastaavat äänestystehtäviä ja kolme paikkaa listojen 1 ja 2 välissä vastaavat sanoma- jonoa. Muut paikat, joihin tulee tai lähtee vaakasuora nuoli