EÖTVÖS LÓRÁND TUDOMÁNYEGYETEM TERMÉSZETTUDOMÁNYI KAR
DR. GYARMATI PÉTER
ADAPTÍV VEZÉRLÉS EK OPERÁCIÓS RENDSZEREKBEN. ADIOS
BUDAPEST, 1981.
_________________________________________________________________________________
_________________________________________________________________________________ -2 dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben.
_________________________________________________________________________________
ADAPTÍV VEZÉRLÉSEK OPERÁCIÓS RENDSZEREKBEN.
Tartalomjegyzék
1 2 2.1 2.2 2.3 3 3.1 3.2 3.3 3.3.1 3.3.2 3.3.3 3.4 3.4.1 3.4.2 3.4.2.1 3.4.2.2 3.4.2.3 3.4.2.4 3.4.2.5 3.4.2.6 3.4.3 3.4.3.1 3.4.3.2 3.4.3.3 4 4.1 4.1.1 4.1.1.1 4.1.1.2 4.1.1.3 4.1.1.4 4.1.1.5 4.1.1.6
BEVEZETÉS. 7 AZ ADAPTÍV IRÁNYÍTÁS MODELLJE 9 Szabályozáselméleti motivációk 9 Az optimalitás kritériuma 10 Az adaptáció folyamata és algoritmusai 11 AZ ADAPTÍV IRÁNYÍTÁS ALKALMAZÁSA 14 A rendszer-teljesítmény definiciója 14 Megelözö munkák 15 Az alapmodell és funkciói 17 Az identifikációs (mérési) lépés 18 A döntési (adaptív vezérlési) lépés 20 Az optimalizálási (beavatkozási) lépés 20 Az alapmodell vizsgálata 21 Az adaptív vezérlés folyamata 21 A mérés problémái 24 A mintavételes átlag 28 Az utolsó N esemény átlag 28 Az exponenciálisan súlyozott átlag 29 A mintavételes szórás 29 Az utolsó N esemény szórás 30 Az exponenciálisan súlyozott szórás 31 Döntési algoritmus, optimumkeresési folyamat 32 A mérés kiértékelése 32 Az optimumkeresés folyamata 35 Megjegyzések 40 NÉHÁNY REALIZÁCIÓ 42 Realizálási javaslatok 43 Szélsöséges müködés (trashing) megakadályozása 43 Az I/O terhelés (a virtuális tár kivételével) 43 A CPU terhelése 44 Pufferek, sorok, segéd-tárak telitettsége 44 A központi tár foglaltsága 44 A lapváltási ráta 45 A CPU és I/O egyensúly 45
_________________________________________________________________________________ dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben. -3 -
_________________________________________________________________________________
4.1.1.7 Egyéb 4.1.2 Optimalizáló adaptív szabályozások 4.1.2.1 Beavatkozás elörecsatolással 4.1.2.2 Beavatkozás visszacsatolással 4.1.2.3 Kétparaméteres beavatkozás 4.1.2.4 Szabályozás a kiszolgáló egységen belül 4.2 Példa a programok számának vezérlésével 4.2.1 A költségfunkcionál meghatározása 4.2.2 A mérési funkció 4.2.3 A döntési funkció 4.2.4 A beavatkozási funkció 4.2.5 Szimulációs eredmények és mérési tapasztalatok 4.2.5.1 A modellezés feltételezései 4.2.5.2 A modellezés paraméterei 4.2.5.3 A vizsgálati eredmények értékelése 4.3 Eröforrások dinamikus elosztása a felhasználói programok kiszolgálási igény szerinti átrendezésével 4.3.1 A heurisztikus algoritmus és realizálása 4.3.1.1 A mérési funkció 4.3.1.2 A döntési funkció 4.3.1.3 A beavatkozási funkció 4.3.2 A döntési funkció kiegészítése a túlterhelési állapotú rendszer szabályozására 4.3.3 Továbbfejlesztés az apriori ismeretek adaptív szabályozással történö kiváltására 4.3.4 Mérési eredmények és tapasztalatok 5 ÖSSZEFOGLALÁS 6 IRODALOMJEGYZÉK
Táblázatok és ábrák jegyzéke 1 2 3 4 5 6 7 8 9
ábra ábra ábra ábra ábra ábra ábra ábra ábra
Egyszerü adaptív algoritmus Járulékos adaptív algoritmus Alap modell Kazakevics modell Optimum keresés Identifikáció I. Identifikáció II. Identifikáció III. Identifikáció IV.
12 13 18 22 35 37 37 38 38
_________________________________________________________________________________ -4 dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben.
45 46 46 47 47 47 48 49 51 54 57 57 58 60 62 67 68 69 70 72 73 75 78 87 88
_________________________________________________________________________________
10 11 12 13 14 15 16 17 18 1 2 3 4 5 6 7 8 9 10
ábra ábra ábra ábra ábra ábra ábra ábra ábra táblázat táblázat táblázat táblázat táblázat táblázat táblázat táblázat táblázat táblázat
Beavatkozás elörecsatolással Beavatkozás visszacsatolással Példa elörecsatolással Várakozósoros modell Mintavételezési összefüggések Kiszolgálási összefüggések Válaszadási idö összefüggések Példa kettös beavatkozással Kiszolgálási igény variációk
46 47 48 58 61 63 64 67 74
Kiszolgálási összefüggések Válaszadási idö összefüggések I. munkaösszetétel eredményei II. munkaösszetétel eredményei Az L kiszolgálási és terhelési mátrix Real storage usage analyzis System data set and CPU usage CPU and PD usage FD usage Eredmények összehasonlítása
63 64 65 66 74 80 81 82 83 85
INDEX adaptív, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 21, 32, 41, 42, 45, 47, 58, 61, 63, 64, 65, 66, 67
_________________________________________________________________________________ dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben. -5 -
_________________________________________________________________________________
_________________________________________________________________________________ -6 dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben.
_________________________________________________________________________________
1 BEVEZETÉS. A s zá m ít ógép r en d s zer ek m ü k öd és én ek ir á n yít á s á t az op er á ciós r en d s zer ek lá t já k el. A tech n ik a fejlöd és ével a k ü lön féle ir á n yít á s i fela d a t ok egyr e b on yolu lt a b b á vá ln a k . Ált a lá b a n a zon b a n n em r en d elk ezü n k elegen d ö a p riori is m er et ek k el a m ü k öd és felt ét eleir öl, ezér t a vá lt oza t la n s t r u k t ú r á jú és t öb b n yir e á lla n d ó p a r a m ét er ek k el leír h a t ó ir á n yít á s i a n a lízis és s zin t ézis m ód s zer ek igen n eh ézk es ek , s öt gya k r a n egyá lt a lá n n em a lk a lm a zh a t ók . Az a u t om a t ik u s ir á n yít á s i r en d s zer ek felép ít és én ek a la p vet ö elem e a z elt ér és alapján történö irányítás, a negatív visszacsatolás elve. Mivel a hibajel különféle ellenörizhetetlen hatásokra vonatkozó in for m á ciót fogla l m a gá b a , ezér t ép p en a h ib a jel t ek in t h et ö u n iverz á lis m érté k n ek a b b a n a von a t k ozá s b a n , h ogy a rendszer állapota mennyiben tér el a megkívánt üzemmódtól. E n n ek s zok á s os m ód ú felh a s zn á lá s a a zon b a n t öb b ok b ól k ifolyóla g is n eh ézs égek b e ü t k özik . Tá r olók , k és lelt et ök és egyéb n em lin eá r is elem ek jelen lét e r en d s zer b en k or lá t ozza egy u n iver zá lis m ér t ék felh a s zn á lá s á t , m ivel a z egyéb k én t cs ek ély jelen t öségü p a r a m ét er ek és n on -linearitások leh et s éges h a t á s a it n em is m er ve, k ön n yen m egs zegh et jü k a s ta b ilis m ü ködés szabta határokat. E m ellet t figyelem b e k ell ven n ü n k a zt a t én yt is , h ogy az ir á n yít ot t r en d s zer jellem zöi m ég a z idö fü ggvén y éb e n is v áltoz n a k . J ól ér zék elh et ö a p r ob lém á k s ú lya , k ü lön ös en , h a célu n k n em cs u p á n a z ir á n yít á s , h a n em op tim á lis irá n y ítá s létrehozása. Min d ezek m ia t t elvileg m á s felép ít és ü ir á n yít á s i r en d s zer t k ell k ia la k ít a n i, olya n t , a m ely k ép es t a n u lá s i fela d a t ok a t is megoldani. Az ilyen ta n u ló é s a d a p tív ir á n yít á s n a k a r en d s zer r öl szerezhetö in for m á ció m ér és e és feld olgozá s a a la p já n ú gy k ell vá lt oza t n ia s t r u k t ú r á já t és p a r a m ét er eit , h ogy m ü ködés _________________________________________________________________________________ dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben. -7 -
_________________________________________________________________________________
k özb en ja vít s a s a já t m in ös égi jellem zöit , véger ed m én yb en bizonyos szempontokból optimális mü ködésre törekedve. Az a d a p t ív s za b á lyozá s es et én t eh á t a z a p r ior i is m er et ek h iá n yá t a m ér t in for m á ció céls zer ü feld olgozá s á va l kompenzáljuk. Bármely a d a p t ív ir á n yít á s i r en d s zer m ü k öd és én ek a la p já t it er á ciós a lgor it m u s ok k ép ezik . A t a n u ló a lgor it m u s ok olyan foly a m a tok a t k ép ez n ek , a m e ly ek v a la m ely á tla golt célfü ggvén y szélsö érték é t á lla p ítjá k m eg, egy b en ez a célfü ggvén y n e m más, mint a ta n u lá s - megismerés-- célja. Az a lgor it m u s ok egy os zt á lya a k er es ö t íp u s ú a lgor it m u s ok , a m elyek a lk a lm a zá s á r a olya n es et ek b en va n s zü k s ég, a m ik or a z á t la golt célfü ggvén y a n a lit ik u s a n n em a d ot t . S zá m ít ógép es r en d s zer ek m ü k öd és én ek ir á n yít á s a legt öb b s zör cs a k ilyen adaptív keresö típusú algoritmusok segítségével lehetséges. A cél te h á t a m ü ködést irá n y ító op erációs ren d s z erek m ód os ítá s a , k iegé s z íté s e ily en típ u s ú algoritm u s ok k a l a ren d s z er h a té k on y s á gá n a k ja vítá s a é rd ek éb en . A jelen d is s zer t á ciób a n b e k ívá n om m u t a t n i a z a d a p t ív vezérlési elv alkalmazását operációs rendszerekben, figyelembe véve a gya k or la t i k or lá t ok a t és k on k r ét p éld á k on k er es zt ü l bemutatni a realizálás lehetöségét és elönyeit. A 4 . fejezet b en egy r ea lizá lt a d a p t ív s za b á lyozá s m ü k öd és e és tapasztalatainak leírása is megtalálható. Budapest, 1981. szeptember.
_________________________________________________________________________________ -8 dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben.
_________________________________________________________________________________
5
ÖSSZEFOGLALÁS
(1) Ös s zefogla lva t eh á t m egá lla p ít h a t ó, h ogy a z a d a p t ív s za b á lyozá s b evezet és ével a gép k ih a s zn á lá s a ja vu l, ugyanakkor rövidül az átfutási idö is. (2) Az á lt a lá n os ja vu lá s olym ód on volt elér h et ö, h ogy a z a d a p t ív folya m a t r évén a m ü k öd és r en d jét m in t egy h ozzá iga zít ot t u k a z id öben változó felhasználói igényekhez. (3) Min d en es et b en a s za b á lyozá s b evezet és ével a r en d s zerben t a r t a lék ok is k elet k ezt ek , p ed ig a s za b á lyozá s n élk ü li esetekben a rendszer túlterhelésben, söt szélsöséges (trashing) múködési állapotban volt. (4) Az a d a p t ív s za b á lyozá s s a l m ü ködö r en d s zer is k er ü lh et t ú lt er h elés i á lla p ot b a , ez a zon b a n n em ok ozh a t s zéls öséges m ü ködést, amint azt kimutattuk. (5 ) Felm er ü lh et , h ogy a t ú lt er h elés i á lla p ot b a n a z a d ot t s za b á lyozá s m á r n em k ielégít ö és a r en d s zer b övít és ér e, va gy m a ga s a b b s zin t ü a d a p t ivit á s b evezet és ér e --a t ú lt er h elt s ég felis m er és ér e és a n n a k a la p já n a lk a lm a s b ea va t k ozá s elvégzésére-- van szükség. Ennek a kérdésnek a vizsgálata további kutatások tárgya.
_________________________________________________________________________________ dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben. - 87 -
_________________________________________________________________________________
6 Irodalomjegyzék [1]
Y. Z. CIPKIN: Optimization, adaptation and learning in automatic systems. Computer and Information Sciences. 15-32. oldal Academic Press, 1967, New-York
[2]
Y. Z. CIPKIN: Principles of dinamic adaptation in automatic systems. IFAC 5th World Congress, Paris, 1972.
[3]
J. KIEFER-J. WOLFOWITZ: Stochastic Estimation of the maximum of a regression function. Ann. Math. Stat. 462-466- oldal, 1952.
[4]
H. ROBBINS-S: MONROE: A stochastic approximation method Ann. Math. Stat. 400-407. oldal, 1952.
[5]
B. WIDROW: A statistical theory of adaptation. Pergamon Press, 1963.
[6]
A. FELDBAUM: A duális vezérlés elmélete. Automatika és telemechanika, 1966. No 1,2.
[7]
V: KAZAKEVICS: Az extremális szabályozásról. Automatika és telemechanika. 1966. No 12.
[8]
CSÁKY F.: Korszerú szabályozáselmélet. Akadémia Kiadó, 1970.
[9]
CSÁKY F.: Irányítástechnikai kézikönyv. Mü szaki 1977.
[10]
CSÁKY FD.: Lineáris szabályozási rendszerek analízise. Mü szaki 1977.
_________________________________________________________________________________ - 88 dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben.
_________________________________________________________________________________
[11]
CSÁKY F.: Lineáris szabályozási rendszerek szintézise. Mü szaki 1978.
[12]
AMBRÓZY A.-JÁVOR A.: Mérésadatok kiértékelése. Mü szaki 1976.
[13]
PRÉKOPA A.: Valószínü ségelmélet. Mü szaki 1974.
[14]
KÓSA A.: Optimumszámítási modellek. Mü szaki 1979.
[15]
G: A: KORN: Matematikai kézikönyv mü szakiaknak. Mü szaki 1975.
[16]
P: R: BLEVINS: Aspects of a dynamically adaptive operating systems. Ph.D dissertation. University of Austin. 1972.
[17]
W. A. WOLF: Performance monitors for multiprogramming systems. 2nd symposion on operating system principles 175181. oldal Princeton. 1969.
[18]
V. RAMAMOORTY: The analytic design of a dynamic lookahead and programming segmenting sístems for multiprogrammed computers. ACM National Conference 229-239. Washington, 1966.
[19]
P. DENNING: The working set model for program behaiour. ACM Communications 323-333. vol.11. 1968.
[20]
G. ESTRIN, D. HOPKINS, B. COGGAN, S. D. CROCKER: SNUPER COMPUTER. A computer in instrumentation automation. Proc. AFIPS 1967. Conference 615-656. 1967.
[21]
R. G. HAMLET: Efficient multiprogramming resource allocation and accounting. AXCM Communications 337-343. vol.16. 1973.
_________________________________________________________________________________ dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben. - 89 -
_________________________________________________________________________________
[22]
S. SHERMAN, F. BASKETT, J. C. BROWNE: Trace driven modeling and analysis of CPU in a multiprogramming system. ACM SIGOPS workshop in Cambridge, MA. 1971.
[23]
S. MARSHALL: Dynamic calculation of dispatching priorities under OS/360 MFT. Datamation 93-97. vol.15. 1960.
[24]
F. STEVENS: On overcoming high priority paralisis in multiprogramming system --a case history. ACM Communications. 539-541- vol.11. 1968.
[25]
K. D. RYDER: A heuristic approach to task dispatching. IBM System Journal 189-198. vol.8. 1970.
[26]
G. COFFMAN: Analysis of two time-sharing algoritms designed for limited swapping. Journal of ACM. vol.15. 1968.
[27]
A. J. BERNSTEIN, J. C. SHARP: A policy driven scheduler for a time-sharing system. ACM Communications. 74-78. vol.14. 1971
[28]
L. KLEINROCK: A continuum of time-sharing algoritms. Proc. AFIPS. 453-458- vol.36. 1970.
[29]
A. WOLLISZ: A detailed system overhead including description of priority algoritms for real-time scheduling. Operációs rendszerek elmélete, téli iskola, Visegrád. SZTAKI Közlemények 61-86. vol.18. 1977.
[30]
TÖKE P.: Kötegelt és kollektiv felhasználást támogató dinamikusan adaptív vezérlés. Operációs rendszerek elmélete, téli iskola, Visegrád. SZTAKI Közlemények 87-98. vol.18. 1977.
[31]
GYARMATI P.: Dinamikus eröforráselosztás vegyes üzem esetén. Operációs rendszerek elmélete, téli iskola 1975. SZTAKI Közlemények 201-209. vol.18. 1977.
_________________________________________________________________________________ - 90 dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben.
_________________________________________________________________________________
[32]
G. BERGHOLZ.: Zur analyse des Echtzeitbetriebe von Prozessorrechnersystemen. Operációs rendszerek elmélete téli iskola 1976. SZTAKI Tanulmányok 141-158- vol.69. 1977.
[33]
GYARMATI P.: Feedback controls in the operating systems. Operációs rendszerek elmélete, téli iskola, Visegrád. 1976.
[34]
P. R. BLEVINS, D. V. RAMAMOORTHY: Aspects of q dynamically adaptive operating system. IEEE Transactions on computer 713-735. vol.25. 1976.
[35]
J. LEROUDIER, PARENT: Discrete event simulation modeling of computer systems for performance evaluation. IRIA Laboria, rapport de recherche 1. 77. 1976.
[36]
Y. BARD: Experimental evaluation of systems performance. IBM Systems Journal. 302-314. 1973/3.
[37]
A. BRANDWAJN: A model of time-sharing virtual memory system solved using equvivalence and decomposition method. Acta Informatica 11-48. vol.4. 1974.
[38]
P. J. COUTOIS: Decomposability, insbabilities and saturation in multiprogramming systems. ACM Communicatins 371-377. vol.18. 1975.
[39]
M. BADEL, E. GELENBE, J. LEROUDIER, D. POTIER: Adaptive optimization of a time-sharing systems performance. Proc. of IEEE. 958-965. vol.63. 1975.
[40]
A. BRANDWAJN, J. A. HERNANDEZ: A study of a mechanism for controlling multiprogrammed memory in an interactive systems. Ecole nationale superieure des telecommunications. Paris. 1978.
_________________________________________________________________________________ dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben. - 91 -
_________________________________________________________________________________
[41]
C. E. LANDWEHR: An endogeous priority model of load control in combined batch-interactive computer systems. Symp. on Performance measurement and evaluation. Harvard University of Cambridge Proc. 292-295. 1976.
[42]
Y. BARD: The modelling of some scheduling strategies for an interactive system. Symp. on Performance measurement and evaluation. 113.117. Yorktown Heights. 1977.
[43]
A. GECK: Performance improvement by feedback control of the operating system. Informatik Rechnerabteilung Universitat Karlsruhe. 1978.
[44]
T. STOREY, S. TODD: Performance analysis of large systems. S oftware practice and experience. 363-369. vol.7. 1977.
[45]
P. DENNING, J. BUZEN: Operational analysis of queuing networks. Measueing, modelling and evaluating computer systems. North-holland Publishing Co. 151-172. 1977.
[46]
T. BERETVAS: A simulation model representing the OS/VS2 rel.2. control program. Proc. of a symposium on Operating systems. Springer Verlag. 1974.
[47]
P. GYARMATI: On the adaptiv control of operating systems. Operációs rendszerek elmélete, téli iskola, Visegrád. 1977.
[48]
ed.GYARMATI P.: KSH Rendszertechnikai Közlemények KSH Rendszertechnikai Osztály.
[49]
ed. GYARMATI P.: KSH Üzemeltetési szabályok IBM 370. KSH Rendszertechnikai Osztály.
_________________________________________________________________________________ - 92 dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben.
_________________________________________________________________________________
[50]
J. Y. BABANNEU, et.al.: Automativ and general solution to the adaptation of programs in paging environment. Proc. of 6th ACM symposium on operating systems. 109-116. nov. 1977.
[51]
E. G. COFFMAN, T. A RYAN: A study of storage partitioning using a mathematical model of locality. Comm. of ACM. March. 1972. vol.15. 185-190.
[52]
G. S. SHEDLER: A queuing model of multiprogrammed computer witj a two-level storage system. Comm. of ACM. Jan. 1973. vol.16. 3-8.
[53]
Proceeding of the IBM seminar on virtual machines. Uithoorn, 1972. Belgium. ed: G. Kjellin, IBM Public Sector Industrial Center, Brussels.
_________________________________________________________________________________ dr. gyarmati péter: Adaptív vezérlések operációs rendszerekben. - 93 -
