VEČOPRAVILNO OKOLJE ZA DELO V REALNEM ČASU NA RAČUNALNIKU IBM-PC INFORMATICA 2/88 UDK 681.3.014 Vido Vouk Jure Ferbežar Andrej Brodnik Institut »Jožef Stefan« This article presents a multl tasking environment for the MS-DOS operating system on the IBH-PC computer. Real tirae scheduler was developed using real time clock interrupts to perforro process scheduling. Interprocess ccnunication is impleroented using semaphores and message exchange. All the support routines for the multi-tasking real-time environment are packed in a single module which offers all the routines needed to handle process manipulation, process synchronization and interprocess data exchange. All the software is developed using Logitech Modula-2 environment. članek opisuje osnovno okolje za pisanje veiopravilnih programov na raiunalniku IBM-PC pod operacijsklzn sistemom MS-DOS. V ta namen smo razvili razporejevalnik procesorskega časa, ki uporablja urine prekinitve. Za medprocesno slnhronizacijo smo uporabili semaforje in izmenjavo sporočil. Uporabniku je na voljo modul podprogramov, ki nudi vse potrebne podprograme za delo v veiprocesorskemu okolju. V roodulu so podprogrami za ustvarjanje, poganjanje, ustavljanje in izloianje ter podprogrami za nadzor procesov, podprogrami za komunikacijo med procesi (send, receive) in podprogrami za sinhronizacijo (uait, signal) in ustrezni dodatni podprogrami za ustvarjanje, nadzor in izlotanje semaforjev. Vsa programska oprema je napisana v programskem jeziku modula-2. 1. OVOD Raiunalniki zdruiljivi z IBM-PC so pri nas vedno pogostejži in tudi niso pretirano dragi . žal pa ti računalniki ne nudijo podpore v vesopravilnem okolju. Ker se zaradi nizke cene vedno več potroinikov odloča za ta tip raftunalnika, so razvijalci prisiljeni poiskati, oziroma izdelati ftimbolj univerzalna orodja za izdelavo zahtevnejsih aplikacij. V tem članku predstavljeni razporejevalnik procesorskega časa predstavlja eno od takih orodij. žal zaradi omejenosti operacijskega sistema MS-DOS iz flčka ni mogote narediti Ferrarija. 1.1 PROCESI Proces lahko definlramo kot asinhrono aktivnost, naprlmer izvajanje programa na centralni procesorski enoti CPE /H0L78/. S preprostim razmislekom ' lahko pridemo do zakljuska, . da je proces lahko v poljubnem tcenutku opazovanja le v enem od dveh moinih stanj IZVRšLJIV NEIZVRSLJIV Opisani stanji •lahko zaradi lažjega razmiiljanja razdelimo naprej na naslednja podstanja: IZVRSLJIV NEIZVRSLJIV TRENUTNI PRIPRAVLJEN PREKINJEN čAKAJOč SPEč SPREJEMAJOč Privzeminio, da imamo ve6 procesov. Vsi procesi iz skupine IZVRSLJIV imajo pravico do izvajanja na poljubnem CPE. V poljubnem trenutku pa se dejansko izvaja eden (na eno procesorskero sistemu) ali N procesov (na N procesorskem sistemu). Procese, ki se izvajajo, imenujemo TRENUTNI. Vsl ostall procesi, ki imajo pravico do izvajanja, pa se ne izvajajo zaradi pomanjkanja prostih procesorjev, so v stanju PRIPRAVLJEN. Procesi iz skupine NEIZVRšLJIV so zatasno ustavljeni in niroajo pravice do procesorja, čeprav bi kak procesor bil prost ali celo brez dela. Ti procesi so ustavljeni in iakajo na nek zunanji dogodek, ki jih zbudi in jih prestavi v skupino IZVRšLJIVIH procesov. Dogodki, ki jih zbudijo ln prestavijo v drugo skupino, so razlifini glede na stanje v katerem so zaustavljeni . Slika 1.1 prikazuje možna stanja procesov in .dogodke, ki vplivajo na prehode roed stanji. K sliki 1.1 rooramo dodati tudi kratek komentar. Iz slike je razvidno, da klic podprograma CREATE ustvari nov proces in ga postavi v stanje PREKINJEN. Vpraftanje, ki se pojavi je, kaj se zgodi s procesom, ki ga ielimo odstranlti iz naiega okolja. Klic KILL odstrani proces ne glede na to kje se je nahajal pred klicem. Proces nepreklicno izgine iz okolja.Pred odstranltvijo sprosti vse zasedene zmogljivosti v sistemu. 1.2 SINHRONIZACIJA Za sinhronizacijo procesov v večprocesornih okoljih uporabljamo razlitne tehnike. Ookaiemo lahko, da so vse tehnike funkcionalno enakovredne /FIL84/, vendar so v 95 prekine, da dodeli procesor drugemu procesu. Vsakerou procesu dolotimo nek doloien ias, ko lahko teče, ne da bi ga prekinili. Po izteku tega Sasa damo v izvajanje na tem procesorju nek drug proces. -? 2. IZVEDBA 2.1 PROGRAMSKO OKOLJE Razporejevalnik iasa smo razvili za IBM-PC zdruiljiv računalnik. Za modulo-2 smo se odloiili, ker je visji programski jezik /WIR85/, ki ima vse potrebne konstrukte za delo na strojnem nivoju in obenem osnovno podporo za delo z več procesi. Tako je razvoj in vzdrievanje programske opreme relativno preprosto. Vsa programska oprema razporejevalnika je napisana v Logitech Moduli-2/86 pod operacijskim sistemom MS-DOS 3.20. Slika 1.1 Stanja procesov ln prehodi med stanji razllčnih izvedbah različno primerne. Razporejevalnik opisan v tem članku za sinhronizacijo uporablja semaforje /DIJ75/ ln izroenjavo sporočil /JON87/. 1.2.1 SEMAFORJI Kot sta pokazala /DIJ75/ in /HAN73/ lahko vse probleme sinhronizacije reiimo s P in V setnaf or jema . V nasi izvedbi razpore jevalnika smo uporabili spložne (itevne) semaforje. ToreJ je binarni semafor v nažem razporejeva.lniku le posebna obllka sploSnega semaforja. 1.2.2 IZMENJAVA SPOROčIL Izmenjava sproiil (message exchange) je poseben mehanizem, kl omogoča procesu da prenese pripravljeno sporoiilo drugemu procesu. Izmenjava sporosil je obenem poseben mehanizem sinhronizacije. Glavna razllka med seroaforji in izmenjavo sporotil je v tem, da mora biti za vsak klic WAIT(sem) ustrezen klic SIGNAL(sem), v prlmeru izmenjave sporočil pa to ni nujno. Izinenjava sporoiil je za sinhronizacijo preprostejža posebno kadar proces ne ve vnaprej koliko sporočil bo dobil in kateri procesi jih bodo poslali. Ta način sinhronizacije je uporabljen v CSP /HOA85/, moduli-2 /WIR85/ ln v programskero jeziku OCCAM /JON87/. Dokažroo lahko, da je možno lzvesti izmenjavo sporoiil samo s semaforji ln obratno /FIL84/. 1.3 RAZPOREJANJE PROCESOV Nata nadaljna razlaga bo zadevala enoprocesorske ' sisteme. Pospložitev na veiprocesorske sisteme je očitna. Iluzijo vzporednega izvajanja več procesov na eno ali veiprocesorskemu sistemu lahko dosežemo s preklaplJanjem . procesorja (procesorjev) med veS procesi. če hočemo zagotoviti, da bodo procesi enakopravno izkoriSčali dane procesorske zmoglJivosti v sisterau, moramo uvesti razsodnika, ki odloia, kdaj bo kateri od procesov zaiel z izvajanjem, kdaj bo izvajal svojo kodo ln kdaj bo prenehal z delom, da bi prepustil procesor naslednjetnu uporabniku. Ta razsodnik je razporejevalnik procesorskega časa. Razporejevalnik odlota kateri proces lahko zasede procesor in ga potem tudi lahko 2.2 UVOD Razporejevalnik je zasnovan na primeru razporejevalnika za RT-11 /BRO87/. Za razliko podobnih razporejevalnikov, ki delujejo sinhrono /COL87/, nas razporejevalnik omogoia delo v realnem fasu. Informacljo o preteienem času dobi od prekinitev, ki jih generira ura. Urine preklnitve so relativno pogoate. te bi razporejevalnik ob vsaki urini prekinitvi pregledal vse strukture, bl bll odziv sicer izjemno dober, vendar bl bila uiinkovitost takega sistema zelo majhna, saj bi se tak sistem vesino časa ukvarjal sam s seboj. Tako ob vsaki urini prekinltvi razporejevalnik pregleda 'le nekatere strukture, medtem ko spložni pregled stanja procesov naredi le na določeno itevilo urinih prekinitev.- Uglaževanje izvedemo eksperimentalno. Razporejevalnik odlota, kateri od procesov bo dobil pravico do izvajanja svoje kode. Razporejevalnik ga tudi prekine med izvajanjem in to tako, da se proces tega ne zaveda. Razporejevalnik shrani vse potrebne podatke o procesu v lokalni•pomnilnik , tako da lahko v poljubnem trenutku ponovno zaiene prekinjeni proces. Proces nadaljuje z izvajanjem v točki v kateri je bil prekinjen. Med delom smo naleteli na ves težav. Najveijo ~~težavo je predstavl jala sama zasnova operacljskega sistema. MS-DOS 3.20 je eno uporabniski eno opravilni operacijski-sistem, tako da nobeden od sistemskih klicev ni prekinljiv. To teiavo smo poskučali zaobiti z uporabo nedokumetirane lastnosti operacijskega sistema /LOG85/, ki s posebno zastavico oznaii kdaj je v kritiftnem odseku. Vendar se ta režitev med izdatnim testiranjem ni izkazala kot dovalj zanesljiva, ker tudi nekateri podprograml v moduli-2 niso prekinljivi. Ta problem smo resili tako, da smo celotni klic DOSa označili kot kritiini odsek. ^ Celoten sistem je sestavljen iz treh funkcionalno ldčenih niodulov: jedro, semaforji in izmenjava sporočil. Jedro omogoča delo nad procesi (ustvarjanje, prekinitev procesa), modul semaforjev omogoča delo s semaforji (ustvarjanje, SIGNAL, . WAIT) modul za izmenjavo sporočil pa omogoča klice SEND in RECEIVE. Ker je nas sistem namenjen tudi uporabi v povsem realnih aplikacijah, so vsi trije moduli skriti v oklepajočera modulu, ki zunanjemu uporabniku onernogoča dostop do kritičnih ukaznih in podatkovnih struktur. Iz modula navzven so iznesene le funkcije, ki so potrebne za učinkovito uporabo sistema. Uporabnik nima nobene možnosti, da bi z 96 nepravilno ali nepazljivo uporabo porušil konsistentnost sistema. V dodatku A je podan definicijski modul nažega razporejevalnika, iz katerega je razvidno, katere podatkovne in ukazne strukture ter klici so uporabniku na voljo. 2.3 PODATKOVNE STRUKTURE Za učinkov1tejse delo razporejevalnika smo raorali dobrien del prekinitvenih podprogramov zaroenjati s svojimi novo napisanimi, ki uporabljajo konstrukte iz razporejevalnika. Podatkovne strukture izven modula niso vidne /BRO87/. Osnovne enote, s katerimi uporabnik lahko upravlja, so procesi, semaforji in sporočlla. Z njimi operira preko klicev podprogramov in tako vpliva na tek procesov. Vsi podprogrami so monitorji /HAN75/. 2.3.1 PROCESI Osnovna enota v sistemu je proces. Proces je v moduli-2 izvajanje podprograma brez parametrov /HIR85/ in /LOG86/. V nažem sistemu smo definicijo razžirili z naslednjimi parametrl : - lme - interno ime - iivljenjski prostor - prioriteta Ime je sestavljeno iz niza alfanumeričnih znakov. Namenjeno je le uporabniku. Ob zahtevi za ustvaritev procesa jedro preveri pravllnost parametrov in ustvari proces. Priredi mu interno ime, ki ga vrne uporabniku. Vsi nadaljni klici za delo z ustvarjenim procesom uporabljajo le interno ime. življenski prostor opredeljuje velikost procesu prlrejenega delovnega pomnilnika /LOG86/. Prioriteta je pomemben parameter, ki opisuje nujnost izvajanja danega procesa. Večja vrednost predstavlja večjo prioritetg. V osnovni izvedbi nažega sistema velja, da se vedno izvaja tisti proces, ki ima najvižjo prioriteto. Kadar je takih procesov veft, si ti procesi enakopravno delijo procesor med seboj (round robin). Naslednje izvedbe sistema omogočajo drugaine načine razporejanja /VMS82/. Vsak proces opredeljuje spremenljivka stanja (prim. slika 1.1). Kot smo omenili, se lahko proces v danem trenutku nahaja le v natanko enem stanju. Kratek opis stanj: TRENUTNI (CURRENT): Ker je IBM-PC enoprocesorski slstem je lahko v poljubnera trenutku le en TRENUTNI proces. Ta proces izvaja svojo kodo. če sam ne klifte nobenega od podprogramov, ki bi mu lahko spremenil status PrReady) *) PROCEDURE PKILL (pid : tPid) : tProcStatus; (* Deletes a process and releases its resources (PrFree) ») PROCEDURE PSUSPEND (pid : tPid) : tProcStatus; (* Suspends a process (PrReady or PrCurr --> PrSusp) *) PROCEDURE PSETPRIO (pid : tPid; prio : tPrio) : tProcStatus; (* Change process priority *) PROCEDURE PGETPID (name:ARRAY OF CHAR; VAR pid : tPid) : tProcStatus; (* returns process id (Pid) of process NAME *) PROCEDURE PGETSTAT (pid : tPid; VAR statblock:tStatBlock) : tProcStatus; (• returns process status inforroaton *) PROCEDURE PGETCURR () : tPid; (* retucns process own process id *) PROCEDORE PSLEEP (time : CARDINAL):tProcStatus; (• Sleep for time ticks (PrCurr --> PrSleep) *) PROCEDURE PRECEIVE (VAR what:ADDRESS; VAR who:tPid): tProcStatus; (* Receive a message from anybody (conditional PrCurr --> PrRec) * PROCEDURE PSEND (whom:tPid; what:ADDRESS) : tProcStatus; (* Send a message to a process *) PROCEDURE SCREATE (name:tSemNatne; VAR sem:tSemaphore; count:CARDINAL): tSemStatus; (* Create a new seropahore and return its ID in sen *) 99 PROCEDURE SINIT (sem:tSemaphore; count:CARDINAL) : tSemStatus; {* Init a Semaphore to initial value count *) PROCEDURE SDELETE (sem:tSemaphore) : tSemStatus; (* Delete a semaphore *) PROCEDURE SWAIT (sem:tSemaphore) : tSemStatus; (* Wait for a semaphore (PrCurr --> PrHait) * ) PROCEDORE SSIGNAL (sem:tSemaphore) : tSemStatus; (• Signal on semaphore sem *) PROCEDURE SSTATUS (sem:tSemaphore) : tSemStatus; {* Get Semaphore status information *) PROCEDURE SGETSID (name:tSemName;VAR sero : tSemaphore;count:CARDINAL) : t.SemStatus; (• Get the ID of semaphore name *) END PROCESS. DODATEK B (DINING PHILOSOPHERS) MODULE SPAGHETTI; FROM PROCESS IMPORT PCREATE, PRESUME, PSLEEP, PSUSPEND, PGETCURR, PRECEIVE, PSEND, PKILL, PSETPRIO, tPid-, tProcStatus, cPriol, cPrio2, Port, SCREATE, SWAIT, SSIGNAL, SDELETE, tSemName, tSemStatus, tSemaphore, CURSOR, HRITEI, WRITE; FROM InOut IMPORT HriteString, HriteCard, HriteLn, WriteHex; FROM Break IMPORT EnableBreak; FROM Strlngs IMPORT Concat; FROM SYSTEM IMPORT GETREG, ADDRESS, WORD, BYTE, INBYTE, OUTBYTE, CODE; FROM Keyboard IMPORT KeyPressed, Read; FROH Devices IMPORT SavelnterruptVector, RestorelnterruptVector; FROM MyRandom IMPORT Random; TYPE tPhil = [0...4]; VAR Pidl,pid2,pid3,pid4,pid5 : tPid; procstat, status: tProcStatus; chn,I,J: INTEGER; w: WORD; konec : BOOLEAN; ch: CHAR; vec: ADDRESS; MODULE FORKS [7]; IMPORT tSemaphore, tPhil, tProcStatus, tSeroStatus, SWAIT, SCREATE, SSIGNAL, tSemName, Concat, PSLEEP; EXPORT PICKUP, PUTDOWN; TYPE tNumOfFork = [0..2]; VAR . numOfForks : ARRAY tPhil OF tNumOfFork; ready : ARRAY tPhil OF tSemaphore; semstat : tSeroStatus; i : INTEGER; tmp : tSemName; PROCEDURE PICKUP (phil : tPhil); VAR left, right : tPhil; BEGIN IF (numOfForks[phil] < 2) THEN semstat := SWAIT (ready[phi1]) END; right := phil; left := (phll + 1) MOD 5; DEC(numOfForks[left] ); DEC(numOfForks[right ] ) ; END PICKUP; 100 PROCEDURE PUTDOHN (phil : tPhil); VAR left, right : tPhil; BEGIN right := phil; left := (phil + 1) MOD 5; INC(numOfForks[left]); INC(numOfForks[right]) ; IF numOfForks[left] = 2 THEN semstat := SSIGNAL (ready[left]); END; IF numOfForks[right] = 2 THEN semstat := SSIGNAL (ready[right ] ) ; END; END PUTDOWN; BEGIN (• FORKS *) FOR i := 0 TO 4 DO CASE i OF 0 : tmp := 'Bacon' | 1 : tmp := 'Sokrates' | 2 : tmp := 'Aristoteles' | 3 : ttnp := 'Nietsche' | i : tmp := 'Hegel ' END (* case *); semstat := SCREATE (tmp, ready[i], 0); numOfForks[i] := 2; (* forks initialization «) END; END FORKS; PROCEDURE First; VAR timesEaten : CARDINAL; BEGIN timesEaten := 0; LOOP PICKUP(O); HriteString ('Bacon eating '); WriteCard(timesEaten, 5); HriteLn; INC(timesEaten); PUTDOWN(0); procstat := PSLEEP (Random(lO) ); END; END First; PROCEDURE Second; VAR timesEaten : CARDINAL; BEGIN timesEaten := 1; LOOP PICKUP(l); WriteString ('Sokrates eating '); WriteCard(timesEaten, 5); VJriteLn; INC(timesEaten); PUTDOWN(1); procstat := PSLEEP (Random(lO) ); END; END Second; PROCEDURE Third; VAR timesEaten : CARDINAL; BEGIN timesEaten := 1; LOOP PICKUP(2); HriteString (•Aristoteles eating '); WriteCard(timesEaten, 5); UriteLn; INC(timesEaten); PUTDOWN(2); procstat := PSLEEP (Random(lO) ); END; END Third; 101 PROCEDURE Fourth; VAR timesEaten : CARDINAL; BEGIN timesEaten := 1; LOOP PICKUP(3); HriteString ('Nietsche eating •); WriteCard(timesEaten, 5); WriteLn; INC(timesEaten) ; POTDOWN(3); procstat := PSLEEP (Random(lO) ); END; END Fourth; PROCEDURE Fifth; VAR timesEaten s CARDINAL; BE6IN timesEaten : = 1; LOOP PICKUPU); HriteString ('Hegel eating '); WriteCard(timesEaten, S); HriteLn; INC(timesEaten); PUTDOWN(4); procstat := PSLEEP (Random(lO) ); END; END Fifth; BEGIN EnableBreak; status status status status status status status status status status st.at.us PSETPRIO(PGETCURR(),cPrio2); PCREATE(First,8OOH,'Bacon',pidl,cPriol); PCREATE(Second,800H, 'Sokrates',pid2,cPriol); PCREATE(Third, 800H, " PCREATE(Fourth,800H, " PCREATE(Fifth,80OH,"Hegel•,pid5,cPriol PRESUME(pidl); PRES0ME(pid2); PRESUME(pid3); PRESUME(pid4); PRESUME(pidB); konec := FALSE; LOOP Port; status := PSLEEP(18); IF KeyPressed() THEN EXIT; END; END; (* LOOP «) status := PKILL(PGETCURR()); WriteString('END - Philosophers' END SPAGHETTI.