top - download
⟦e0669ffa5⟧ Wang Wps File
Length: 40656 (0x9ed0)
Types: Wang Wps File
Notes: TJG Forel`sningsnoter
Names: »4169A «
Derivation
└─⟦2939611b6⟧ Bits:30006177 8" Wang WCS floppy, CR 0350A
└─ ⟦this⟧ »4169A «
WangText
FORM
SIDE ####
TOMOGRAFISSYSTEM
TJG 22/10/83
SYSTEMPROGRAMMERING
FOREL@SNING…02…:…02…S̲Y̲S̲T̲E̲M̲P̲R̲O̲G̲R̲A̲M̲M̲E̲R̲I̲N̲G̲:̲ ̲K̲O̲R̲U̲T̲I̲N̲E̲R̲,̲
P̲R̲O̲C̲E̲S̲S̲E̲R̲,̲ ̲P̲R̲O̲C̲E̲S̲K̲O̲M̲M̲U̲N̲I̲K̲A̲T̲I̲O̲N̲.̲
INDHOLD:…02……02…:…02…1. Problemstilling:
systemprogrammering og multiprogrammer.
2. Semaforer.
3. Korutiner.
4. Korutinemonitor.
5. Processer.
6. Processer og korutiner.
1̲.̲ ̲P̲r̲o̲b̲l̲e̲m̲s̲t̲i̲l̲l̲i̲n̲g̲:̲ ̲s̲y̲s̲t̲e̲m̲p̲r̲o̲g̲r̲a̲m̲m̲e̲r̲i̲n̲g̲ ̲o̲g̲ ̲m̲u̲l̲t̲i̲p̲r̲o̲g̲r̲a̲m̲m̲e̲r̲.̲
…02…En vigtig del af udviklingen af et st]rre programsystem er overvejelserne vedr]rende opdeling
af programsystemet i mindre, mere overskuelige delsystemer. En m>de at opdele programmerne
p> er selvf]lgelig opdeling i procedurer, men for st]rre programsystemer er det mere hensigtsm`ssigt
at implementere programsystemet som e̲t̲ ̲m̲u̲l̲t̲i̲p̲r̲o̲g̲r̲a̲m̲, som kan best> af flere p̲r̲o̲c̲e̲s̲s̲e̲r̲ eller
k̲o̲r̲u̲t̲i̲n̲e̲r̲ (eller begge dele). Implementeringen kan begynde med udviklingen af det helt ba-
sale programmel - en korutinemonitor eller en operativ- systemkerne. Oftest vil man dog benytte
datamaskin- leverand]rens operativsystem. Man skal derfor v`re i stand til at forst> de kommunikations
og synkroniserings- mekanismer, der stilles til r>dighed i et operativsystem og evt. udvikle
mere avancerede mekanismer, der bygger p> de basale begreber, der altid findes i et operativsystem.
Denne form for programmering - udvikling af systemprogrammel - kaldes for s̲y̲s̲t̲e̲m̲p̲r̲o̲g̲r̲a̲m̲m̲e̲r̲i̲n̲g̲.
Systemprogrammering g>r bl.a. ud p>:
* udvikling af b̲a̲s̲i̲s̲p̲r̲o̲g̲r̲a̲m̲m̲e̲l̲, is`r styresystemer,
* udvikling af k̲o̲m̲m̲u̲n̲i̲k̲a̲t̲i̲o̲n̲s̲/̲s̲y̲n̲k̲r̲o̲n̲i̲s̲e̲r̲i̲n̲g̲s̲ m̲e̲k̲a̲- n̲i̲s̲m̲e̲r̲, der bygger p> eksisterende
mekanismer,
* udvikling af specielle "̲s̲e̲r̲v̲i̲c̲e̲s̲y̲s̲t̲e̲m̲e̲r̲"̲ - f.eks. specielle filsystemer, der er
en videreudvikling af eksisterende filsystemer,
* implementering af m̲u̲l̲t̲i̲p̲r̲o̲g̲r̲a̲m̲m̲e̲r̲.
Det er is`r implementering af multiprogrammer og kommunika- tions og synkroniseringsmekanismer,
der omtales i n`rv`rende forel`sningsnoter. Forel`sningsnoterne har bl.a. til form>l at vise
hvordan moderne operativsystemer fungerer.
…02…Et sekventielt program angiver en liste af ordrer som kan eksekveres sekventielt. Udf]relsen
af et sekventielt program kaldes for e̲n̲ ̲p̲r̲o̲c̲e̲s̲. E̲t̲ ̲m̲u̲l̲t̲i̲p̲r̲o̲g̲r̲a̲m̲ indeholder et, to eller flere
sekventielle programmer. Et multiprogram kan implementeres som et s`t af p̲a̲r̲a̲l̲l̲e̲l̲l̲e̲ ̲p̲r̲o̲c̲e̲s̲s̲e̲r̲
eller som et s`t af k̲o̲r̲u̲t̲i̲n̲e̲r̲ som evt. k]rer inden for samme proces. Et multiprogram kan
udf]res ved at processerne skiftes til at k]re p> samme CPU. Denne form for programafvikling
kaldes for m̲u̲l̲t̲i̲p̲r̲o̲g̲r̲a̲m̲m̲e̲r̲i̲n̲g̲ og implementeres af en operativ- systemkerne, der multiplexer
CPU…08…en mellem processerne. Alternativt kunne man dedikere }n CPU til hver proces og bruge
et f`lles internt lager. Denne form for afvikling af multiprogrammer kaldes for m̲u̲l̲t̲i̲p̲r̲o̲c̲e̲s̲s̲i̲n̲g̲.
Endelig kan man afvikle multiprogrammer v.h.a. "d̲i̲s̲t̲r̲i̲b̲u̲e̲r̲e̲t̲ ̲p̲r̲o̲c̲e̲s̲s̲i̲n̲g̲" hvor hver proces
tildeles sin egen datamat (best>ende af CPU og internt lager). Kommunikationen mellem processerne
under- st]ttes i det sidste tilf`lde af et kommunikationsnetv`rk. De 3 m>der at afvikle multiprogrammer
p> er illustreret i fig. 1 og fig. 2.
fig. 1
afvikling af multiprogrammer
a) multiprogrammering b) multiprocessing c) distribueret
processing
MULTIPROGRAMMERING MODULER
MULTIPROCESSING PROCEDURER
DISTRIBUERET PROCESSING KORUTINER
PROCESSER
fig. 2.
systemprogrammering: grundbegreber
Samarbejdet mellem processerne best>r af to former for informationsudveksling:
* p̲r̲o̲c̲e̲s̲k̲o̲m̲m̲u̲n̲i̲k̲a̲t̲i̲o̲n̲ best>r i udveksling af data via buffere; ved proceskommunikationen
vil afsender- processen p>virke eksekvering af modtagerprocessen,
* s̲y̲n̲k̲r̲o̲n̲i̲s̲e̲r̲i̲n̲g̲ er n]dvendig n>r processerne eksekveres med forskellig og ukendt
relativ hastig- hed; synkronisering bruges n>r f.eks. udelelig ad- gang til f`lles
variable skal sikres.
Synkronisering kan betragtes som en udartet form for proces- kommunikation hvor der sendes
en tom databuffer. Synkro- nisering kan forsinke en proces og den kan garantere at en gruppe
operationer bliver udf]rt som }n udelelig operation.
Forst>elsen af multiprogrammer, operativsystemkerner og synkroniseringsmekanismer er af stor
betydning ved konstruktionen af mere komplicerede datamatiske systemer, is`r proceskontrolsystemer,
som if]lge sagens natur m> …86…W …02… …02… …02… …02… …02…
overv>ge flere samtidige begivenheder. Udviklingen af multi- programmer og notationer til
beskrivelse af parallel ud- f]relse af processer har udviklet sig ad to veje:
* p̲r̲o̲c̲e̲d̲u̲r̲e̲l̲ ̲n̲o̲t̲a̲t̲i̲o̲n̲ eksemplificeret ved Concurrent Pascal, bygger p> aktive og passive
objekter (processer og klasser/monitorer). Passive objekter repr`senter f`lles variable
der kan manipuleres via procedurekald, der implementerer synkronisering og sikrer
udelelig adgang til data,
* b̲e̲s̲k̲e̲d̲o̲r̲i̲e̲n̲t̲e̲r̲e̲t̲ ̲n̲o̲t̲a̲t̲i̲o̲n̲, der kan implementeres i laveller h]jniveau sprog bygger
p> "s̲e̲n̲d̲" og "r̲e̲c̲e̲i̲v̲e̲" operationer hvorved processerne kan ud- veksle informationer
i beskedbuffere.
Ved beskedorienteret (eng. message passing) notation kan beskedbuffere udveksles p> to forskellige
m>der:
* d̲i̲r̲e̲k̲t̲e̲ ̲n̲a̲v̲n̲g̲i̲v̲n̲i̲n̲g̲ (eng. direct naming) er en me- tode til proceskommunikation
hvor afsenderprocessen fort`ller hvilken modtagerproces der skal modtage beskedbufferen;
modtagerprocessen kan p> sin side fort`lle hvilken afsenderproces den forventer
at f> beskedbufferen fra; som eksempel p> besked- orienteret notation kan man n`vne
CSP (Communicating Sequential Processes), Gypsy, Plits,
* ved i̲n̲d̲i̲r̲e̲k̲t̲e̲ ̲n̲a̲v̲n̲g̲i̲v̲n̲i̲n̲g̲ udveksles informationer ved at processerne bruger p> forh>nd
aftalte g̲l̲o̲- b̲a̲l̲e̲ n̲a̲v̲n̲e̲ hvor beskedbuffere bliver afleveret og hentet; globale navne
repr`senter beskedsemaforer ogs> kaldet s̲y̲n̲k̲r̲o̲n̲i̲s̲e̲r̲i̲n̲g̲s̲e̲l̲e̲m̲e̲n̲t̲e̲r̲.
Brugen af globale navne og beskedsemaforer repr`senter den mest generelle form for processkommunikation,
der tillader implementering af "mange-til-mange" kommunikation. Forskelle mellem de to former
for beskedbuffer udveksling fremg>r af fig. 3.
fig. 3.
a. direkte navngivning
b. synkroniseringselementer
Tegnet repr`senterer et synkroniseringselement.
De burde v`re klart at brugen af synkroniseringselementer til udveksling af beskedbuffere
repr`senterer den mest generelle (og den f̲a̲r̲l̲i̲g̲s̲t̲e̲) form for proceskommunikation. Det er
den foretrukne form for proceskommunikation og synkronisering, is`r til brug for implementering
af proces- kontrol og datakommunikationssystemer. Denne form for proceskommunikation (og
operativsystemkerner der bygger p> den), betragtes som "de facto" standard for tidstro opera-
tivsystemkerner. Mere avancerede og mere restriktive
begreber som "direkte navngivning beskedudveksling", monitorer og ADA…08…s rendezvous begreber
kan implementeres v.h.a. de mere generelle begreber. Derfor er kendskab til beskedsemaforer
og korutiner (der er en simpel form for processer) en foruds`tning for forst>elsen af nutidens
operativsystemer og brugen af dem ved implementering af mere komplicererede datamatiske systemer.
2̲.̲ ̲S̲e̲m̲a̲f̲o̲r̲e̲r̲.̲
…02…Semaforbegrebet, introduceret af Dijkstra i 1968, var det f]rste fors]g p> at strukturere
synkroniserings- mekanismer. Man kan egentlig p>st>, at alle synkroniserings- mekanismer
der er blevet indf]rt senere, bygger p> semafor- begrebet og implementeres som regel v.h.a.
semaforer, der administreres af en operativsystemkerne. De 2 mest alminde- lige former for
semaforer gennemg>s nedenunder. Der benyttes en Pascal lignende notation.
En semafor implementeres v.h.a. en datastruktur og kan be- skrives ved operationer der udf]res
p> den. Operationerne betegnes normalt "w̲a̲i̲t̲" og "s̲i̲g̲n̲a̲l̲" eller "s̲e̲n̲d̲" og "r̲e̲c̲e̲i̲v̲e̲".
Man kan betragte flg. situation: et st]rre programsystem ]nskes implementeret og afviklet
p> en datamat. Program- systemet ]nskes implementeret som et multiprogram, der be- nytter
sig af procesbegrebet. Processerne har behov for at synkronisere og udveksle data. Dertil
benyttes semaforer, som omtales nedenunder. Operationerne p> semaforer udf]res som procedurekald
til c̲e̲n̲t̲r̲a̲l̲l̲o̲g̲i̲k̲k̲e̲n̲, der implementerer udelelelige operationer p> bl.a. semaforer. Centrallogikken
benytter sig af en r`kke datastrukturer og "variable":
* "ready ̲list" er en liste af processer, der er parate til at k]re,
* "current ̲process" er identifikationen af den k]rende proces.
Desuden benyttes der en datatype "pointer", der kan inde- holde pegepinde til alle datastrukturer
i datamatens interne lager.
Da operationer p> lister er hj]rnestenen i operativsystem- kerner og i en korutineorienteret
centrallogik benyttes der nogle simple (forh>bentlig selvforklarende) procedurekald til listemanipulerende
procedurer, der udf]rer typiske operationer p> lister.
Proceduren "select ̲candidate" medf]rer udskiftning af den k]rende proces med en proces fra
"ready ̲list".
G̲e̲n̲e̲r̲e̲l̲l̲e̲ ̲s̲e̲m̲a̲f̲o̲r̲e̲r̲.̲
t̲y̲p̲e̲ general ̲semaphore = r̲e̲c̲o̲r̲d̲
value : integer;
head : pointer
"pointer to process/corutine
description"
e̲n̲d̲;
p̲r̲o̲c̲e̲d̲u̲r̲e̲ wait(v̲a̲r̲ s:general ̲semaphore);
b̲e̲g̲i̲n̲
i̲f̲ s.value gt 0
t̲h̲e̲n̲
s.value:=s.value-1
e̲l̲s̲e̲
b̲e̲g̲i̲n̲
insert ̲process(s.head, current ̲process);
select ̲candidate()
e̲n̲d̲;
e̲n̲d̲;
p̲r̲o̲c̲e̲d̲u̲r̲e̲ signal(v̲a̲r̲ s:general ̲semaphore);
b̲e̲g̲i̲n̲
i̲f̲ empty(s.head)
t̲h̲e̲n̲
s.value:=s.value+1
e̲l̲s̲e̲
insert ̲process(ready ̲list, first(s.head))
e̲n̲d̲;
Virkningerne af signal/wait kaldene kan beskrives p> f]lgende m>de:
* w̲a̲i̲t̲ - hvis semaforv`rdien er 0, inds`t den kaldende proces bagest i k]en (processen
aktiveres n>r en anden proces har kaldt signal), ellers reduc}r t`lleren med 1,
* s̲i̲g̲n̲a̲l̲ - hvis procesk]en er tom, for]g t`lleren med 1, ellers flyt f]rste proces
fra semaforens procesk] til "ready ̲list".
B̲e̲s̲k̲e̲d̲s̲e̲m̲a̲f̲o̲r̲e̲r̲.̲
t̲y̲p̲e̲ message ̲semaphore = r̲e̲c̲o̲r̲d̲
state : integer;
process ̲queue : pointer;
message ̲queue : pointer
e̲n̲d̲;
message = r̲e̲c̲o̲r̲d̲
next : pointer;
data : array (1..msg ̲size) of integer
e̲n̲d̲;
p̲r̲o̲c̲e̲d̲u̲r̲e̲ receive(v̲a̲r̲ op:message;
…02……02……02… v̲a̲r̲ s:message ̲semaphore);
b̲e̲g̲i̲n̲
i̲f̲ s.state gt 0
t̲h̲e̲n̲
b̲e̲g̲i̲n̲
"message queue is not empty"
remove ̲message(first(s.message ̲queue), op)
s.state:=s.state-1
e̲n̲d̲
e̲l̲s̲e̲
b̲e̲g̲i̲n̲
"message queue is empty"
insert ̲process2(s.process ̲queue, current ̲process,
s.message ̲queue, op);
s.state:=s.state-1;
select ̲candidate()
e̲n̲d̲;
e̲n̲d̲;
p̲r̲o̲c̲e̲d̲u̲r̲e̲ send(v̲a̲r̲ op:message; v̲a̲r̲ s:message ̲semaphore);
b̲e̲g̲i̲n̲
i̲f̲ s.state ge 0
t̲h̲e̲n̲
"process list is empty"
insert ̲message(s.message ̲queue, op)
e̲l̲s̲e̲
"process list is not empty"
insert ̲process3(ready ̲list, first(s.process ̲queue),
first(s.message ̲queue), op);
s.state:=s.state+1
e̲n̲d̲;
Semaforen repr`senteres af en datastruktur, der best>r af flg. elementer:
* p̲r̲o̲c̲e̲s̲s̲k̲]̲ - k]en af processer der venter p> beskeder,
* b̲e̲s̲k̲e̲d̲k̲]̲ - k]en af beskeder der venter p> at blive afhentet,
til ethvert tidspunkt kan der enten v`re beskeder i beskedk]en eller processer i
procesk]en,
* e̲n̲ ̲t̲`̲l̲l̲e̲r̲, der kan antage flg. v`rdier:
t`ller = 0 b>de processog beskedk]en er
tom,
t`ller = 1,2,... procesk]en er tom, beskedk]en
indeholder beskeder,
t`ller =-1,-2,... processk]en indeholder processer
beskedk]en er tom.
Den ovenfor beskrevne semafortype er vist i fig. 4.
fig. 4.
beskedsemaforer
Beskedsemaforer kaldes ogs> for o̲p̲e̲r̲a̲t̲i̲o̲n̲s̲s̲e̲m̲a̲f̲o̲r̲e̲r̲ (opera- tion=besked) eller for synkroniseringselementer.
Besked- semaforer er fuldt ud t̲i̲l̲s̲t̲r̲`̲k̲k̲e̲l̲i̲g̲e̲ til at implementere multiprogrammer: synkronisering
kan opn>s ved at man sender tomme beskedbuffere, kommunikation implementeres via besked-
buffere. Der findes ogs> andre semafortyper, men de to oven- for beskrevne er dog de mest
almindeligt forekommende.
B̲e̲m̲`̲r̲k̲n̲i̲n̲g̲: de viste signal/send operationer er i̲k̲k̲e̲-̲b̲l̲o̲k̲e̲r̲e̲n̲d̲e̲ operationer, dvs. de implementerer
a̲s̲y̲n̲k̲r̲o̲n̲ kommunikation. B̲l̲o̲k̲k̲e̲r̲e̲n̲d̲e̲ signal/send implementerer synkron kommunikation.
Beskedsemaforer kan betragtes som standard synkroniserings og kommunikationsmekanismer i
moderne operativsystemer. Nogle af >rsagerne til, at beskedudvekslingen er s> popul`r, er:
* den er v̲e̲l̲e̲g̲n̲e̲t̲ til s>vel traditionel m̲u̲l̲t̲i̲- p̲r̲o̲g̲r̲a̲m̲m̲e̲r̲i̲n̲g̲ som til m̲u̲l̲t̲i̲p̲r̲o̲c̲e̲s̲s̲i̲n̲g̲
og d̲i̲s̲t̲r̲i̲b̲u̲e̲r̲e̲t̲ ̲p̲r̲o̲c̲e̲s̲s̲i̲n̲g̲,
* den tillader implementering af st]rre program- systemer som et s`t af meget l]st
forbundne a̲s̲y̲n̲k̲r̲o̲n̲t̲ ̲k̲]̲r̲e̲n̲d̲e̲ ̲p̲r̲o̲c̲e̲s̲s̲e̲r̲, en process kan igang- s`tte en operation
hos en serviceproces, forts`tte med at k]re, og afhente resultatet af operationen,
n>r den har behov for det,
* andre velstrukturerede synkroniseringsmekanismer som f.eks. monitorer og rendezvous
kan implementers v.h.a. beskedudveksling.
3̲.̲ ̲K̲o̲r̲u̲t̲i̲n̲e̲r̲.̲
…02…Korutiner er en udvidelse af procedure og subrutine be- greberne. Korutiner er delprogrammer
der kan kalde hinanden - n>r de bliver kaldt forts`tter de fra det sted, de var n>et til.
I eksemplet nedenunder vises 3 korutiner A, B og C. Korutiner afl]ser hinanden v.h.a. af
operationen "r̲e̲s̲u̲m̲e̲". Denne operation kan enten v`re direkte imple- menteret i et h]jere
programmeringssprog, som f.eks. i Simula, eller v`re implementeret som et procedurekald til
en centrallogik, der kaldes for e̲n̲ ̲k̲o̲r̲u̲t̲i̲n̲e̲m̲o̲n̲i̲t̲o̲r̲. A er den f]rste korutine der aktiveres.
c̲o̲r̲u̲t̲i̲n̲e̲ A; c̲o̲r̲u̲t̲i̲n̲e̲ B; c̲o̲r̲u̲t̲i̲n̲e̲ C;
b̲e̲g̲i̲n̲ b̲e̲g̲i̲n̲ b̲e̲g̲i̲n̲
r̲e̲p̲e̲a̲t̲ r̲e̲p̲e̲a̲t̲ r̲e̲p̲e̲a̲t̲
A1 B1 C1
resume(B); resume(C); resume(A);
A2 B2 C2
f̲o̲r̲e̲v̲e̲r̲; f̲o̲r̲e̲v̲e̲r̲; resume(B);
e̲n̲d̲; e̲n̲d̲; C3
f̲o̲r̲e̲v̲e̲r̲;
e̲n̲d̲;
fig. 5.
eksempel : 3 korutiner
A1, A2, B1, B2, C1, C2 og C3 repr`senterer operationer, der udf]res udeleligt. Hvis A aktiveres
som den f]rste korutine f>r man f]lgende sekvens af operationer:
A1 B1 C1 A2 A2 B2 B1 C2 B2 B1 C3 C1 A2 A1 B2 B1 ...
De steder hvor korutiner afl]ser hinanden kaldes v̲e̲n̲t̲e̲- p̲u̲n̲k̲t̲e̲r̲. Et ventepunkt angiver, at
en korutine ikke ]nsker eller ikke kan forts`tte.
Man kan p>st>, at hver korutine implementerer en proces. "resume" svarer til en simpel processynkronisering.
I̲ ̲e̲t̲ k̲o̲r̲u̲t̲i̲n̲e̲s̲y̲s̲t̲e̲m̲ ̲h̲a̲r̲ ̲m̲a̲n̲ ̲p̲>̲ ̲f̲o̲r̲h̲>̲n̲d̲ ̲f̲a̲s̲t̲l̲a̲g̲t̲ ̲a̲l̲l̲e̲ ̲p̲r̲o̲c̲e̲s̲s̲k̲i̲f̲t̲. Korutiner kan derfor betragtes
som parallelle processer, der k]rer s̲y̲n̲k̲r̲o̲n̲t̲. Det klassiske udelelighedsproblem eksisterer
simpelthen ikke i et korutinesystem.
Den skitserede model af et korutinesystem er ret ubrugelig til praktiske anvendelser, og
de fleste korutinesystemer tillader da ogs> flere operationer end bare "resume". I de fleste
korutinesystemer, der underst]ttes i h]jere programmeringssprog kan man ogs> udf]re operationer
som f.eks. "start(corutine)" s>ledes at man kan inds`tte flere korutiner i centrallogikkens
"ready ̲list". Et virkeligt effektivt system opbygges dog f]rst n>r man benytter besked og
generelle semaforer. En "signal" eller "send" operation vil bevirke at en korutine flyttes
til "ready ̲list". En korutine kan aktivere flere korutiner ved at den signalerer til flere
semaforer. En "wait" eller "receive" operation kan blokere en korutine - den bliver indsat
i semaforens procesk]. Derved opn>r man at flere korutiner kan v`re i ventepunkter (og endda
vente p> samme semafor) og der kan ligeledes v`re flere korutiner i "ready ̲list" der kan
k]re. Beskedsemaforer er ogs> en udm`rket mekanisme til implementering af r̲e̲s̲o̲u̲r̲c̲e̲p̲u̲l̲j̲e̲r̲.
Man kan f.eks. h`gte en r`kke buffere (beskedbuffere) p> en beskedsemafor og bruge semaforen
som e̲n̲ ̲b̲u̲f̲f̲e̲r̲p̲u̲l̲j̲e̲:
"initialiseringsprogram initialiserer bufferpuljen p> flg. m>de:"
f̲o̲r̲ i:=1 t̲o̲ no ̲buffers d̲o̲
send(buffer ̲pool, buffer(i));
"korutiner kan bruge bufferpuljen nu"
"korutine 1"
receive(buffer ̲pool, buffer);
"l`g data i bufferen og aktiver korutine 2"
send(op ̲sema, buffer);
"korutine 2"
"korutinen der venter p> data f>r fat i databuffer ved"
receive(op ̲sema, buffer);
"bufferen kan frigives ved"
send(buffer ̲pool, buffer);
Bufferpuljer benyttes meget ofte i forbindelse med ko- rutiner, is`r i forbindelse med proceskontrol.
Dette skyldes, at korutiner i sig selv ikke garanterer at man kan n> at behandle alle data
fra f.eks. et m>leapparat. Ko- rutiner k]rer synkront, dvs. de afl]ser hinanden i et p> forh>nd
fastlagt r`kkef]lge. Benytter man et korutinesystem til proceskontrol, m> man v`re forberedt
p>, at der pludseligt kan komme for mange data til at man kan n> at be- handle dem. Bufferpuljer
og beskedsemaforer udj`vner i dette tilf`lde tdisafh`ngige variationer i inddatam`ngden.
For at anskuelligg]re et korutinesystem der benytter sig af generelle og beskedsemaforer
kan man betragte et meget simpelt system best>ende af 5 korutiner:
p̲r̲o̲d̲u̲c̲e̲r̲ P er en korutine, der p> mystisk vis
fremskaffer data, som afhentes af
i̲n̲p̲u̲t̲t̲e̲r̲ I forbehandler data og afleverer dem til
c̲o̲n̲s̲u̲m̲e̲r̲ C er en korutine der behandler data og
afleverer dem i samme buffer til
o̲u̲t̲p̲u̲t̲t̲e̲r̲ O korutine der efterbehandler data og bruger
f̲i̲l̲s̲y̲s̲ F korutine til opbevaring af det endelige
resultat.
Alle detaljer ang>ende implementering af afbrydelses- behandling og fysiske inddata/uddata
transporter er med vilje udeladt. Strukturen af dette korutinesystem er skitseret i fig.
6.
fig. 6.
korutinesystem - eksempel
Tegnet betegner en beskedsemafor.…86…W …02… …02… …02… …02… …02…
Korutinerne i eksemplet kan implementeres som vist neden- under:
c̲o̲r̲u̲t̲i̲n̲e̲ P;
b̲e̲g̲i̲n̲
r̲e̲p̲e̲a̲t̲
receive(P ̲buf, buffer ̲pool);
"produce data"
send(P ̲buf, P ̲I ̲sema);
f̲o̲r̲e̲v̲e̲r̲;
e̲n̲d̲;
c̲o̲r̲o̲u̲t̲i̲n̲e̲ I;
b̲e̲g̲i̲n̲
r̲e̲p̲e̲a̲t̲
receive(I ̲buf, P ̲I ̲sema);
"use data"
send(I ̲buf, I ̲C ̲sema);
f̲o̲r̲e̲v̲e̲r̲;
e̲n̲d̲;
P> tilsvarende m>de vil man implementere de resterende ko- rutiner. Korutiner implementeres
som regel som uendelige l]kker, hvor korutinen venter p> en besked, behandler data og evt.
sender dem videre til n`ste korutine. Har man brug for at starte og stoppe et korutinesystem
kan man struk- turere beskeder, der derved f>r karakter som operationer, p> flg. m>de:
t̲y̲p̲e̲ operation = r̲e̲c̲o̲r̲d̲
link : pointer;
command : (start,stop,continue);
data : array (1..size) of integer
e̲n̲d̲;
Korutinen kan fortolke data i operationen og udf]re en aktion angivet ved indholdet af kommandofeltet:
r̲e̲p̲e̲a̲t̲
receive(op, sema);
c̲a̲s̲e̲ op.command o̲f̲
start : "initialize processing" ;
stop : "stop processing" ;
continue : "continue processing"
e̲n̲d̲;
f̲o̲r̲e̲v̲e̲r̲;
Som en slags simpel ]velse kan man overveje hvad der sker, hvis korutinesystemet i eksemplet
skal kunne startes og stoppes. Man kan starte alle korutiner ved at man sender startkommandoer
til P ̲I ̲sema, I ̲C ̲sema, osv. P korutinen skal vente p> startkommandoen p> en speciel semafor
P ̲sema. Det er lidt sv`rere at afslutte "evighedsmaskinen". Man skal sende en stopkommando
til P, der sender den videre til I, der ... . Til sidst havner stopkommandoen hos F, der
kan signalere til hovedkorutinen H, der sender start og stop- kommandoer. Hovedkorutinen
venter p> en ekstern begivenhed. N>r den er indtruffet startes der korutinesystemet. N>r
man har "trykket p> knappen" for anden gang sendes der en stop- kommando. N>r svaret fra
F foreligger kan man lukke systemet ned. Systemet er skitseret i fig. 7.
fig . 7. - se n`ste side
fig. 7.
eksemplet - forts`ttelse
Ovenst>ende betragtninger f]rer til konklusionen, at hvis et korutinesystem skal fungere
som et effektivt process- kontrolsystem, skal det kunne h>ndtere a̲f̲b̲r̲y̲d̲e̲l̲s̲e̲r̲. Udvides systemet
i eksemplet med a̲f̲b̲r̲y̲d̲e̲l̲s̲e̲s̲b̲e̲h̲a̲n̲d̲l̲i̲n̲g̲ f>r man et meget simpelt og som regel uhyre effektivt
styresystem. S>danne systemer benyttes i form>lsbundne mini og mikro- datamater der bruges
til proceskontrol.
og "timeslicing" mekanisme. Selve centrallogikken bliver et meget simpelt program - nogen
gange er den p> 100-200 maskininstruktioner. Ved proceskontrol (eller ko- rutineorienterede
styresystemer) bruges normalt }n korutine til hver ekstern begivenhed, eller m>leapparat
der kan for- >rsage begivenheden. Som et simpelt eksempel kan man be- tragte en korutine,
der overv>ger en terminal: n>r der t`ndes for terminalen, signaleres der til en central ko-
rutine, der opdaterer tilstandstabeller.
D̲r̲i̲v̲p̲r̲o̲g̲r̲a̲m̲m̲e̲r̲ kan implementeres som en korutine, der venter p> besked fra en anden korutine,
der har behov for en data- transport. Drivprogrammet vil igangs`tte en operation og vente
p> en semafor, som afbrydelsesprogrammet signalerer til. Denne helt element`re model af et
drivprogram er vist i fig. 8.
fig. 8
model af et drivprogram
Som tidligere n`vnt, h>ndteres variationer i inddatam`ngden i et korutinesystem v.h.a. bufferpuljer.
En vigtig forud- s`tning for at et korutinesystem kan fungere korrekt og op- fylde sit form>l
er at korutiner afl]ser hinanden relativt ofte. For at undg> at langvarige beregninger blokerer
for vigtige korutiner har man i nogle korutinesystemer opera- tionen "reschedule" - et simuleret
ventepunkt - der ind- s`tter den aktive korutine bagest i "ready ̲list". Fejl i ko- rutiner,
f.eks. uendelige l]kker, kan f> systemet til at g> i bagl>s. Som et alternativ eller supplement
til "reschedule" kunne man indf]re en p̲r̲i̲o̲r̲i̲t̲e̲r̲i̲n̲g̲ af korutiner. Udvides dette system med
"timeslicing", s> er man meget t`t p> et egentligt procesorienteret styresystem.
4̲.̲ ̲K̲o̲r̲u̲t̲i̲n̲e̲m̲o̲n̲i̲t̲o̲r̲.̲
…02…Korutinemonitor er centrallogikken i et korutinesystem. En korutinemonitor betjener sig af
korutineposter, der kan v`re erkl`ret p> flg. m>de:
t̲y̲p̲e̲ entry ̲point = absolute ̲program ̲address;
coroutine ̲record = r̲e̲c̲o̲r̲d̲
link : coroutine ̲link;
"pointer to next coroutine ̲record"
context ̲save : context ̲save ̲area;
"machine dependent register save
area"
entry : entry ̲point
"jump address necessary to resume
a corutine"
e̲n̲d̲;
Af andre typedefinitioner kan man n`vne:
t̲y̲p̲e̲ coroutine ̲queue = r̲e̲c̲o̲r̲d̲
first,
last : coroutine ̲link
e̲n̲d̲;
message ̲queue = message ̲link;
De tidligere definerede semaforer kan erkl`res p> flg. m>de:
t̲y̲p̲e̲ general ̲semaphore = r̲e̲c̲o̲r̲d̲
value : integer;
queue : coroutine ̲queue
e̲n̲d̲;
message ̲semaphore = r̲e̲c̲o̲r̲d̲
state : integer;
c ̲queue : coroutine ̲queue;
m ̲queue : message ̲queue
e̲n̲d̲;
og beskedbuffere kan erkl`res p> flg. m>de:
t̲y̲p̲e̲ message ̲buffer = r̲e̲c̲o̲r̲d̲
link : buffer ̲link;
data : array (1..size) of integer
e̲n̲d̲;
Variable "ready ̲list" og "current ̲coroutine" er givet ved:
v̲a̲r̲ ready ̲list : coroutine ̲queue;
current ̲coroutine : coroutine ̲link;
Korutinemonitor kan aktiveres v.h.a. procedurekald i maskinn`re programmeringssprog. Nedenfor
er der angivet de mest typiske korutinemonitor procedureindgange:
i̲n̲i̲t̲i̲a̲l̲i̲s̲e̲r̲i̲n̲g̲s̲p̲r̲o̲c̲e̲d̲u̲r̲e̲r̲:
init ̲coroutine ̲monitor(v̲a̲r̲ c:coroutine ̲record)
"initialiserer korutinemonitor og `ndrer det kaldende program til en korutine"
init ̲coroutine(v̲a̲r̲ c:coroutine ̲record; entry:entry ̲point)
init ̲semaphore(v̲a̲r̲ s:general ̲semaphore; value:integer)
init ̲m ̲sema(v̲a̲r̲ s:message ̲semaphore)
s̲e̲m̲a̲f̲o̲r̲o̲p̲e̲r̲a̲t̲i̲o̲n̲e̲r̲:
signal(v̲a̲r̲ s:general ̲semaphore)
wait(v̲a̲r̲ s:general ̲semaphore)
send(v̲a̲r̲ b:buffer ̲link; v̲a̲r̲ s:message ̲semaphore)
receive(v̲a̲r̲ b:buffer ̲link; v̲a̲r̲ s:message ̲semaphore)
d̲i̲v̲e̲r̲s̲e̲ ̲o̲p̲e̲r̲a̲t̲i̲o̲n̲e̲r̲:̲
reschedule() "simuleret ventepunkt"
remove() "fjerner den kaldende korutine"
5̲.̲ ̲P̲r̲o̲c̲e̲s̲s̲e̲r̲.̲
…02…Ved en proces forst>s udf]relsen af et program. Processerne implementeres p> en datamat af
en operativ- systemkerne. Processerne implementeres af kernen ved at hver proces tildeles
en beskrivelse, der indeholder tilstand- svariable, og pegepinde til de datastrukturer, der
er n]d- vendige for implementeringen af processen. Som eksempler p> de datastrukturer kan
man n`vne "segment ̲tabeller", "page ̲translation ̲tabeller" og andre datastrukturer, der er
forud- s`tningen for at et program kan udf]res som en proces. Procesbeskrivelsen vil indeholde
processens tilstand - k]rende, parat, blokeret, inaktiv, "d]d" - og maskinafh`ngig areal
til opbevaring af registre, s>ledes at en proces kan afbrydes og igangs`ttes p> et vilk>rligt
sted. Den maskin- afh`ngige registeropbevaringsareal kaldes "c̲o̲n̲t̲e̲x̲t̲ ̲s̲t̲o̲r̲a̲g̲e̲" og bruges ved
"c̲o̲n̲t̲e̲x̲t̲ ̲s̲w̲i̲t̲c̲h̲i̲n̲g̲" - processkift, som bruges ved multiprogrammering. Processkift kan skyldes,
at processens tidskvantum er udl]bet - man taler da om "̲p̲r̲e̲e̲m̲p̲t̲i̲o̲n̲"̲.
Udf]relsen af processerne overv>ges af en del af kernen - "p̲r̲o̲c̲e̲s̲s̲ ̲m̲a̲n̲a̲g̲e̲r̲" - der:
* tildeler CPU…08…er til processerne (ved multi- processing),
* multiplexer CPU…08…en mellem processerne (ved multi- programmering),
* flytter procesbeskrivelser mellem lister, der er knyttet til de mulige procestilstande
- flytning sker som resultat af kernekald, der udf]res af andre processer, eller
fordi processens tidskvantum er udl]bet.
Foruden p̲r̲o̲c̲e̲s̲s̲t̲y̲r̲i̲n̲g̲ vil kernen indeholde fasciliteter til:
* p̲r̲o̲c̲e̲s̲s̲k̲o̲m̲m̲u̲n̲i̲k̲a̲t̲i̲o̲n̲ ̲o̲g̲ ̲s̲y̲n̲k̲r̲o̲n̲i̲s̲e̲r̲i̲n̲g̲,
* r̲e̲s̲o̲u̲r̲c̲e̲k̲o̲n̲t̲r̲o̲l̲ og tildeling,
* centraliseret s̲i̲k̲k̲e̲r̲h̲e̲d̲k̲o̲n̲t̲r̲o̲l̲,
* l̲a̲g̲e̲r̲s̲t̲y̲r̲i̲n̲g̲ og allokering,
* styring af a̲f̲b̲r̲y̲d̲e̲l̲s̲e̲r̲ og ydre enheder.
Resourcekontrol har til form>l at holde styr p> kernens "resourcer". Som et eksempel p> en
resource kan man betragte processbeskrivelser. Der findes kun et endeligt antal processbeskrivelser.
Derfor skal en ny proces, der igang- s`ttes, indikere hvor mange nye processer den vil oprette,
s>ledes at der kan reserveres et passende antal tomme procesbeskrivelser.
Sikkerhedskontrol har til hensigt at sikre at fejlbeh`ftede processer ikke ]del`gger hele
systemet. Foruden addresseringsfejl, der forh>bentlig fanges af materiellet, kan processerne
signalere til forkerte semaforer, fors]ge at slette synkroniseringselementer, osv.
Lagerstyringsmekanismer implementerer l̲o̲g̲i̲s̲k̲ ̲a̲d̲r̲e̲s̲s̲e̲r̲u̲m̲ for processerne. Det kan implementeres
via v̲i̲r̲t̲u̲e̲l̲t̲ ̲l̲a̲g̲e̲r̲ (med eller uden d̲e̲m̲a̲n̲d̲ ̲p̲a̲g̲i̲n̲g̲) og/eller via s̲e̲g̲m̲e̲n̲t̲e̲r̲e̲t̲ ̲l̲a̲g̲e̲r̲.
Endelig kan kernen indeholde en symbolsk objektkatalog. Kerneobjekter - som kan v`re lagersegmenter,
synkroniseringselementer, processer - kan altid identi- ficeres af numre, men det er en farlig
metode. Det er at foretr`kke, at de kan identificeres via symbolske navne, s>ledes at man
undg>r at skrive
receive(buf, 2)
men i stedet skriver
receive(buf,"io ̲syncel").
Den ovenfor beskrevne kerne g]r det muligt at implementere e̲t̲ ̲o̲p̲e̲r̲a̲t̲i̲v̲s̲y̲s̲t̲e̲m̲, der f.eks.
kan v`re et terminal- styresystem eller et mere specielt proceskontrolsystem. T̲i̲d̲s̲t̲r̲o̲ ̲e̲g̲e̲n̲s̲k̲a̲b̲e̲r̲
ved et operativsystem er egentlig imple- menteret i kernen. Den skal kunne tillade en p̲r̲i̲o̲r̲i̲t̲e̲r̲i̲n̲g̲
af processerne og g̲a̲r̲a̲n̲t̲e̲r̲e̲ ̲e̲n̲ p̲r̲o̲c̲e̲s̲a̲f̲v̲i̲k̲l̲i̲n̲g̲, der g]r det muligt, at nogle processer meget
hurtigt f>r CPU tid og f>r lov til at k]re i lang tid ved evt. at blokere for processer med
lavere prioritet. Kernen skal ligeledes underst]tte e̲n̲ ̲h̲u̲r̲t̲i̲g̲ ̲f̲o̲r̲m̲ ̲f̲o̲r̲ s̲i̲g̲n̲a̲l̲e̲r̲i̲n̲g̲ via f.eks.
bin`re semaforer. Tidstro systemer skal ligeledes kunne garantere en h̲u̲r̲t̲i̲g̲ ̲b̲e̲h̲a̲n̲d̲l̲i̲n̲g̲ af
afbrydelser inden for n`rmere angivne tids- gr`nser.
Det er vigtigt at huske at e̲t̲ ̲o̲p̲e̲r̲a̲t̲i̲v̲s̲y̲s̲t̲e̲m̲ ̲e̲r̲ ̲e̲n̲ ̲p̲r̲o̲c̲e̲s̲, der opretter og nedl`gger andre
processer. Den f>r tildelt alle systemets resourcer, som den deler ud til sine b]rne- processer.
Den er aktiv i implementeringen af en sikkerheds- kontrol ved at den giver b]rneprocesserne
lov til at "r]re" ved bestemte kerneobjekter.Dette kan ske p> to m>der:
* ved e̲k̲s̲p̲l̲i̲c̲i̲t̲ ̲o̲p̲r̲e̲m̲s̲n̲i̲n̲g̲ af alle objekter som en b]rneproces kan arbejde p>,
eller
* ved at tildele b]rneprocessen e̲t̲ ̲s̲i̲k̲k̲e̲r̲h̲e̲d̲s̲p̲r̲o̲f̲i̲l̲ der bliver sammenlignet med objekternes
sikkerheds- profiler p> udf]relsestidspunktet,
og
* ved at angive h̲v̲i̲l̲k̲e̲ ̲f̲u̲n̲k̲t̲i̲o̲n̲e̲r̲, der kan udf]res p> et objekt.
Nogle systemer vil tillade, at b]rneprocessen igen opretter b]rneprocesser - b]rneprocessen
fungerer s> som et operativ- system for sine b]rneprocesser. P> den m>de kan man opbygge
e̲t̲ ̲o̲p̲e̲r̲a̲t̲i̲v̲s̲y̲s̲t̲e̲m̲ ̲h̲i̲e̲r̲a̲r̲k̲i̲ - se fig. 8. Et klassisk eksempel er RC4000 Multiprogramming System.
fig. 8.
proceshierarki
Der er to afg]rende forskelle mellem korutiner og processer:
* p̲r̲o̲c̲e̲s̲s̲e̲r̲n̲e̲ ̲u̲d̲f̲]̲r̲e̲s̲ ̲p̲a̲r̲a̲l̲l̲e̲l̲t̲, i mods`tning til ko- rutiner, der udf]res "semiparallelt",
* processernes l̲o̲g̲i̲s̲k̲e̲ ̲a̲d̲r̲e̲s̲s̲e̲r̲u̲m̲ er som regel totalt f̲y̲s̲i̲s̲k̲ ̲a̲d̲s̲k̲i̲l̲t̲e̲, s>ledes at
en proces ikke kan, hverken med vilje eller ved et tilf`lde, f> adgang til en anden
proces…08… adresserum; processerne kan ogs> v`re implementeret p> f̲y̲s̲i̲s̲k̲ ̲u̲a̲f̲h̲`̲n̲g̲i̲g̲e̲
datamater.
Den sidste fascilitet plejer at v`re implementeret i materiellet. Kan den sidste betingelse
ikke opfyldes, skal man helst benytte h]jniveau programmeringssprog (som f.eks. Concurrent
Pascal, ADA) for at sikre en korrekt implementering af processer. Der er dog en helt klar
tendens ved udviklingen af moderne datamaskiner: de indeholder meget avancerede fasciliteter
til implementering af adskilte adresseringsrum.
…02…Den mest typiske form for proceskommunikation er den tidligere beskrevne beskedudveksling.
Nogen gange findes der ogs> en "m̲e̲s̲s̲a̲g̲e̲/̲a̲n̲s̲w̲e̲r̲" beskedudveksling - beskeder deles i to grupper
: "messages" og "answers". Processerne kan sende og modtage beskeder og svar. Ofte vil man
ogs> finde meka- nismer til simpel synkronisering - generelle semaforer eller is`r bin`re
semaforer, som ben`vnes "event flags". Besked- udvekslingen v.h.a. synkroniseringselementer
g]r det muligt at opbygge et programsystem som et s`t af asynkront k]rende, l]st fobundne
processer. I og med at processerne udf]res i adskilte fysiske adresserum kr`ves der en anderledes
beskedudveksling end den der blev benyttet i et korutinesystem:
* synkroniseringselementer kan kun m̲a̲n̲i̲p̲u̲l̲e̲r̲e̲s̲ ̲a̲f̲ k̲e̲r̲n̲e̲n̲, processerne har ikke adgang
til semafor- v`rdier,
* beskedudveksling sker ved k̲o̲p̲i̲e̲r̲i̲n̲g̲ af indholdet af beskeder.
Selve "send/receive" kaldene bliver ogs> anderledes: man skal stadigv`k angive adressen p>
beskedbufferen, men synkroniseringselementet identificeres ved et nummer eller ved et symbolsk
navn. Konsekvenserne af disse kendsgerninger bliver, at man af hensyn til effektiviteten
kun kan udveksle relativt sm> beskeder - typisk 8-30 ord - samt at besked- udvekslingen er
relativt tidskr`vende. Meget ofte har man behov for at udveksle betydeligt st]rre datam`ngder
mellem processerne. Til brug for overf]rsel af st]rre datam`ngder tillader kernen i de fleste
tilf`lde, at en del af processernes logiske adresserum er samme fysiske lager- segment, se
fig. 9.
fig. 9.
f`lles lagersegment
Man taler da om f̲`̲l̲l̲e̲s̲s̲e̲g̲m̲e̲n̲t̲e̲r̲. Administrationen af et s>dant segment overdrages til en
serviceproces. En proces kan p> normal vis sende en beskedbuffer til service- processen.
I beskedbufferen angiver processen et ]nske om at bruge en buffer af en given st]rrelse.
Serviceprocessen svarer tilbage med en beskedbuffer, der kan indeholde informationer om at
]nsket kunne im]dekommes og bufferen starter p> en angiven adresse inden for f`llessegmentet.
Man kan selvf]lgelig ogs> f> et negativt svar. Processen kan bruge bufferen til internt brug,
eller den kan overf]re data til en anden proces ved at den sender en beskedbuffer der indeholder
adressen p> bufferen. Til sidst frigives bufferen ved at man sender en passende besked til
serviceprocessen. Ovenst>ende betragtninger er bare et eksempel p> hvordan man implementerer
mere avancerede former for proceskommunikation i et multiprogram, der best>r af asynkront
k]rende processer.
6̲.̲ ̲P̲r̲o̲c̲e̲s̲s̲e̲r̲ ̲o̲g̲ ̲k̲o̲r̲u̲t̲i̲n̲e̲r̲.̲
…02…Gennemgangen af processer og korutiner afsluttes med en sammenligning af de to begreber.
T̲y̲p̲i̲s̲k̲ ̲a̲n̲v̲e̲n̲d̲e̲l̲s̲e̲s̲o̲m̲r̲>̲d̲e̲:
korutinestyresystem : mindre mini og mikrodatamater med begr`nset intern lagerkapacitet,
is`r proceskontrol- anvendelser, d>rlig udnyttelse af CPU tiden, dvs. mange ventepunkter,
"overskud af CPU tid"
procesorienteret styresystem: store datamater, mini og mikrodatamater, lille til meget stor
intern lagerkapacitet, alle anvendelser, effektiv udnyttelse af CPU tiden
K̲o̲m̲m̲u̲n̲i̲k̲a̲t̲i̲o̲n̲:
korutiner: kommunikation via beskedbuffere og generelle semaforer, eller via navn, adresseoverf]rsel
processer: kommunikation via beskedbuffere eller via "message/answer" mekanisme, kopiering
af data
U̲d̲e̲l̲e̲l̲i̲g̲ ̲a̲d̲g̲a̲n̲g̲ ̲t̲i̲l̲ ̲d̲a̲t̲a̲:
korutiner: udelelig adgang til data imellem ventepunkter, hvis koden indeholder ventepunkter
m> man bruge "signal/wait" operationerne
processer: adgang til data bindes til en "message/answer" beskedudveksling
K̲r̲i̲t̲i̲s̲k̲e̲ ̲r̲e̲g̲i̲o̲n̲e̲r̲: (kode der skal udf]res udeleligt)
korutiner: kritiske regioner ligger imellem ventepunkter
processer: den kritiske region bindes til en "message/answer" beskedudveksling
C̲P̲U̲ ̲o̲v̲e̲r̲h̲e̲a̲d̲: (spildtid)
korutiner: meget lille
processer: en st]rrelsesorden st]rre end ved korutiner
A̲d̲r̲e̲s̲s̲e̲r̲u̲m̲:
korutiner: typisk f`lles adresserum
processer: normalt adskilte adresserum, evt. adskilte datamater
Man kan stille sig det sp]rgsm>l: k̲a̲n̲ ̲k̲o̲r̲u̲t̲i̲n̲e̲r̲ ̲b̲r̲u̲g̲e̲s̲ ̲i̲n̲d̲e̲n̲ ̲f̲o̲r̲ ̲e̲t̲ ̲p̲r̲o̲c̲e̲s̲o̲r̲i̲e̲n̲t̲e̲r̲e̲t̲ ̲p̲r̲o̲g̲r̲a̲m̲s̲y̲s̲t̲e̲m̲
̲?̲
Svaret er ja, hvis kernen tillader fuldst`ndig asynkron afvikling af processer, dvs. at en
proces aldrig beh]ver at blive blokeret p> et synkroniseringselement, hvis den ikke ]nsker
det. For at dette kan lade sig g]re m> en proces v`re i stand til at kunne teste om der er
ankommet et svar p> et synkroniseringselement uden at blive blokeret. N>r der fore- ligger
et svar vil udf]relsen af "receive" ikke blokere processen. Har man den mulighed kan man
i̲m̲p̲l̲e̲m̲e̲n̲t̲e̲r̲e̲ ̲e̲n̲ ̲p̲r̲o̲c̲e̲s̲ ̲s̲o̲m̲ ̲e̲t̲ ̲s̲y̲s̲t̲e̲m̲ ̲a̲f̲ ̲k̲o̲r̲u̲t̲i̲n̲e̲r̲. I et s>dant system vil der v`re to slags
ventepunkter:
* ventepunkter der skyldes "wait/receive" operationer udf]rt p> i̲n̲t̲e̲r̲n̲e̲ semaforer,
* ventepunkter der skyldes a̲f̲v̲e̲n̲t̲n̲i̲n̲g̲ ̲a̲f̲ ̲s̲v̲a̲r̲ fra andre processer, dvs. "wait/receive"
udf]rt p> e̲k̲s̲t̲e̲r̲n̲e̲ semaforer og "message/answer" besked- udvekslinger.
Korutinemonitoren skal v`re i stand til at h>ndtere b>de i̲n̲t̲e̲r̲n̲e̲ ̲b̲e̲g̲i̲v̲e̲n̲h̲e̲d̲e̲r̲: signalering
og beskedudveksling via interne semaforer, og e̲k̲s̲t̲e̲r̲n̲e̲ ̲b̲e̲g̲i̲v̲e̲n̲h̲e̲d̲e̲r̲: besked- udveksling via
eksterne synkroniseringselementer. S> l`nge der er korutiner, der kan k]re skal korutinemonitoren
give dem lov til at k]re. Hvis alle korutiner bliver blokeret skal korutinemonitoren afs]ge
eksterne synkroniserings- elementer, uden dog at blive blokeret. N>r der er ankommet et svar
p> et synkroniseringselement, skal korutinemonitoren afs]ge listen af blokerede korutiner,
finde den korutine der skal v`kkes og flytte den til "ready ̲list". En s>ledes op- bygget
proces vil udnytte sit tidskvantum uhyre effektivt. Foruds`tningen for at denne model for
et korutinesystem fungerer er:
* alle kald til eksterne processer g>r via korutine- monitoren,
* synkron proceskommunikation ("send" efterfulgt af "receive") skal kunne omdannes
af korutinemonitoren til ikke blokerende kommunikation.
Betragt hvad der sker n>r korutinemonitoren opfanger "receive" opertaionen udf]rt p> et eksternt
synkroniserings- element: den vil flytte korutinen til "blocked ̲list" og knytte en operation
til den, der fort`ller hvilket synkroniseringselement korutinen venter svar fra. Hvis der
er korutiner der kan k]re, vil den f]rste korutine i "ready ̲list" blive den k]rende korutine.
Hvis ingen korutiner kan k]re vil korutinemonitoren unders]ge om der er kommet en besked
til synkroniseringselementet. Hvis dette er tilf`ldet vil den ventende korutine blive den
k]rende korutine og vil f> udleveret den ankomne besked.
Som et andet eksempel betragt en korutine der igangs`tter en synkron datatransport (noget
i stil med Pascal "write") ved en "message/answer" beskedudveksling med filsystemprocessen.
Korutinemonitoren skal da igangs`tte operationen, flytte korutinen til "blocked ̲list" og
f]rst senere afvente svar fra filsystemet. N>r svaret er ankommet kan korutinen fort- s`tte.
Den sidst beskrevne model for en korutinemonitor er vist i fig. 10.
fig. 10.
korutinesystem inden for en proces
Man kan selvf]lgeligt sp]rge sig selv hvorn>r man har brug for s>danne processer, der indeholder
korutiner. Som typiske anvendelser kan man n`vne s̲e̲r̲v̲i̲c̲e̲p̲r̲o̲c̲e̲s̲s̲e̲r̲, der betjener flere processer
og der indeholder mange ventepunkter. Typiske eksempler er f̲i̲l̲s̲y̲s̲t̲e̲m̲e̲r̲ og d̲a̲t̲a̲b̲a̲s̲e̲r̲. Det
er vig- tigt, at langvarige pauser i udf]relsen af disse processer udnyttes til at behandle
de beskeder, der ophobes p> synkroniseringselementer. En implementering af et filsystem,
der f]rst kan behandle en foresp]gsel, n>r den er f`rdig med foreg>ende foresp]rgsel, kan
v`re ret uheldig. En effektiv serviceproces er i stand til at behandle flere foresp]rgsler
samtidig, og endda behandle flere foresp]rgsler fra samme proces samtidig.
Man kan selvf]lgeligt p>st>, at man netop har processer for at man ikke skal bruge korutiner.
I det ovenfor beskrevne filsystemeksempel kunne man principielt opdele filsystemet i flere
processer, med det resultat at det vil blive et tungt og usmidigt system. Man skal nemlig
ikke overbelaste kernen med for mange proceskommunikationer og for mange proces- skift. Korutineskift
er billig at udf]re og beskedudveksling inden for et korutinesystem er n`sten gratis.
L̲i̲t̲t̲e̲r̲a̲t̲u̲r̲
(1) G.R.Andrews, F.B.Schneider:
Concepts and Notations for Concurrent Programming
Computing Surveys, Vol. 15, No. 1, marts 1983
(2) International Purdue Workshop on Industrial Computer
Systems:
Technical Report no. 8
ikke offentliggjort
(3) P.Wegner, S.A.Smolka:
Processes, Tasks and Monitors: A Comparative Study of
Concurrent Programming Primitives
IEEE Transactions on Software Engineering, Vol. SE-9
No. 4, juli 1983
