GLAVA 8. DISPETCHERIZACIYA PROCESSOV I EE VREMENNYE HARAKTERISTIKI V sisteme razdeleniya vremeni yadro predostavlyaet processu resursy cent- ral'nogo processora (CP) na interval vremeni, nazyvaemyj kvantom, po isteche- nii kotorogo vygruzhaet etot process i zapuskaet drugoj, periodicheski pereu- poryadochivaya ochered' processov. Algoritm planirovaniya processov v sisteme UNIX ispol'zuet vremya vypolneniya v kachestve parametra. Kazhdyj aktivnyj pro- cess imeet prioritet planirovaniya; yadro pereklyuchaet kontekst na process s naivysshim prioritetom. Pri perehode vypolnyayushchegosya processa iz rezhima yadra v rezhim zadachi yadro pereschityvaet ego prioritet, periodicheski i v rezhime zada- chi pereustanavlivaya prioritet kazhdogo processa, gotovogo k vypolneniyu. Informaciya o vremeni, svyazannom s vypolneniem, nuzhna takzhe i nekotorym iz pol'zovatel'skih processov: ispol'zuemaya imi, naprimer, komanda time poz- volyaet uznat', skol'ko vremeni zanimaet vypolnenie drugoj komandy, komanda date vyvodit tekushchuyu datu i vremya sutok. S pomoshch'yu razlichnyh sistemnyh funk- cij processy mogut ustanavlivat' ili poluchat' vremennye harakteristiki vy- polneniya v rezhime yadra, a takzhe stepen' zagruzhennosti central'nogo processo- ra. Vremya v sisteme podderzhivaetsya s pomoshch'yu apparatnyh chasov, kotorye posy- layut CP preryvaniya s fiksirovannoj, apparatno-zavisimoj chastotoj, obychno 50-100 raz v sekundu. Kazhdoe postuplenie preryvaniya po tajmeru (chasam) ime- nuetsya tajmernym tikom. V nastoyashchej glave rassmatrivayutsya osobennosti reali- zacii processov vo vremeni, vklyuchaya planirovanie processov v sisteme UNIX, opisanie svyazannyh so vremenem sistemnyh funkcij, a takzhe funkcij, vypolnyae- myh programmoj obrabotki preryvanij po tajmeru. 8.1 PLANIROVANIE VYPOLNENIYA PROCESSOV Planirovshchik processov v sisteme UNIX prinadlezhit k obshchemu klassu plani- rovshchikov, rabotayushchih po principu "karuseli s mnogourovnevoj obratnoj svyaz'yu". V sootvetstvii s etim principom yadro predostavlyaet processu resursy CP na kvant vremeni, po istechenii kotorogo vygruzhaet etot process i vozvra- shchaet ego v odnu iz neskol'kih ocheredej, reguliruemyh prioritetami. Prezhde chem process zavershitsya, emu mozhet potrebovat'sya mnozhestvo raz projti cherez cikl s obratnoj svyaz'yu. Kogda yadro vypolnyaet pereklyuchenie konteksta i voss- tanavlivaet kontekst processa, process vozobnovlyaet vypolnenie s tochki pri- ostanova. 8.1.1 Algoritm Srazu posle pereklyucheniya konteksta yadro zapuskaet algoritm planirovaniya vypolneniya processov (Risunok 8.1), vybiraya na vypolnenie process s naivys- shim prioritetom sredi processov, nahodyashchihsya v sostoyaniyah "rezervirovaniya" i "gotovnosti k vypolneniyu, buduchi zagruzhennym v pamyat'". Rassmatrivat' pro- cessy, ne zagruzhennye v pamyat', ne imeet smysla, poskol'ku ne buduchi zagru- zhen, process ne mozhet vypolnyat'sya. Esli naivysshij prioritet imeyut srazu nes- kol'ko processov, yadro, ispol'zuya princip kol'cevogo spiska (karuseli), vy- biraet sredi nih tot process, kotoryj nahoditsya v sostoyanii "gotovnosti k vypolneniyu" dol'she ostal'nyh. Esli ni odin iz processov ne mozhet byt' vybran dlya vypolneniya, CP prostaivaet do momenta polucheniya sleduyushchego preryvaniya, kotoroe proizojdet ne pozzhe chem cherez odin tajmernyj tik; posle obrabotki etogo preryvaniya yadro snova zapustit algoritm planirovaniya. 232 +------------------------------------------------------------+ | algoritm schedule_process | | vhodnaya informaciya: otsutstvuet | | vyhodnaya informaciya: otsutstvuet | | { | | vypolnyat' poka (dlya zapuska ne budet vybran odin iz pro-| | cessov) | | { | | dlya (kazhdogo processa v ocheredi gotovyh k vypolneniyu)| | vybrat' process s naivysshim prioritetom iz zagru-| | zhennyh v pamyat'; | | esli (ni odin iz processov ne mozhet byt' izbran dlya | | vypolneniya) | | priostanovit' mashinu; | | /* mashina vyhodit iz sostoyaniya prostoya po prery- | | /* vaniyu | | */ | | } | | udalit' vybrannyj process iz ocheredi gotovyh k vypolne- | | niyu; | | pereklyuchit'sya na kontekst vybrannogo processa, vozobno- | | vit' ego vypolnenie; | | } | +------------------------------------------------------------+ Risunok 8.1. Algoritm planirovaniya vypolneniya processov 8.1.2 Parametry dispetcherizacii V kazhdoj zapisi tablicy processov est' pole prioriteta, ispol'zuemoe planirovshchikom processov. Prioritet processa v rezhime zadachi zavisit ot togo, kak etot process pered etim ispol'zoval resursy CP. Mozhno vydelit' dva klas- sa prioritetov processa (Risunok 8.2): prioritety vypolneniya v rezhime yadra i prioritety vypolneniya v rezhime zadachi. Kazhdyj klass vklyuchaet v sebya ryad zna- chenij, s kazhdym znacheniem logicheski associirovana nekotoraya ochered' proces- sov. Prioritety vypolneniya v rezhime zadachi ocenivayutsya dlya processov, vygru- zhennyh po vozvrashchenii iz rezhima yadra v rezhim zadachi, prioritety vypolneniya v rezhime yadra imeyut smysl tol'ko v kontekste algoritma sleep. Prioritety vy- polneniya v rezhime zadachi imeyut verhnee porogovoe znachenie, prioritety vypol- neniya v rezhime yadra imeyut nizhnee porogovoe znachenie. Sredi prioritetov vy- polneniya v rezhime yadra dalee mozhno vydelit' vysokie i nizkie prioritety: processy s nizkim prioritetom vozobnovlyayutsya po poluchenii signala, a proces- sy s vysokim prioritetom prodolzhayut ostavat'sya v sostoyanii priostanova (sm. razdel 7.2.1). Porogovoe znachenie mezhdu prioritetami vypolneniya v rezhimah yadra i zadachi na Risunke 8.2 otmecheno dvojnoj liniej, prohodyashchej mezhdu prioritetom ozhida- niya zaversheniya potomka (v rezhime yadra) i nulevym prioritetom vypolneniya v rezhime zadachi. Prioritety processa podkachki, ozhidaniya vvoda-vyvoda, svyazan- nogo s diskom, ozhidaniya bufera i indeksa yavlyayutsya vysokimi, ne dopuskayushchimi preryvaniya sistemnymi prioritetami, s kazhdym iz kotoryh svyazana ochered' iz 1, 3, 2 i 1 processa, sootvetstvenno, v to vremya kak prioritety ozhidaniya vvoda s terminala, vyvoda na terminal i zaversheniya potomka yavlyayutsya nizkimi, dopuskayushchimi preryvaniya sistemnymi prioritetami, s kazhdym iz kotoryh svyazana ochered' iz 4, 0 i 2 processov, sootvetstvenno. Na risunke predstavleny takzhe urovni prioritetov vypolneniya v rezhime zadachi (*). YAdro vychislyaet prioritet processa v sleduyushchih sluchayah: 233 --------------------------------------- (*) Naivysshim znacheniem prioriteta v sisteme yavlyaetsya nulevoe znachenie. Ta- kim obrazom, nulevoj prioritet vypolneniya v rezhime zadachi vyshe priorite- ta, imeyushchego znachenie, ravnoe 1, i t.d. * Neposredstvenno pered perehodom processa v sostoyanie priostanova yadro naznachaet emu prioritet ishodya iz prichiny priostanova. Prioritet ne za- visit ot dinamicheskih harakteristik processa (prodolzhitel'nosti vvo- da-vyvoda ili vremeni scheta), naprotiv, eto postoyannaya velichina, zhestko ustanavlivaemaya v moment priostanova i zavisyashchaya tol'ko ot prichiny pere- hoda processa v dannoe sostoyanie. Processy, priostanovlennye algoritmami nizkogo urovnya, imeyut tendenciyu porozhdat' tem bol'she uzkih mest v siste- me, chem dol'she oni nahodyatsya v etom sostoyanii; poetomu im naznachaetsya bolee vysokij prioritet po sravneniyu s ostal'nymi processami. Naprimer, process, priostanovlennyj v ozhidanii zaversheniya vvoda-vyvoda, svyazannogo s diskom, imeet bolee vysokij prioritet po sravneniyu s processom, ozhida- yushchim osvobozhdeniya bufera, po neskol'kim prichinam. Prezhde vsego, u pervo- go processa uzhe est' bufer, poetomu ne isklyuchena vozmozhnost', chto kogda on vozobnovitsya, on uspeet osvobodit' i bufer, i drugie resursy. CHem bol'she resursov svobodno, tem men'she shansov dlya vozniknoveniya vzaimnoj blokirovki processov. Sisteme ne pridetsya chasto pereklyuchat' Prioritety vypolneniya Urovni prioritetov Processy v rezhime yadra | +----------------------+ | | Process | +--+ | | podkachki |-+ | | Ne dopuskayushchie +----------------------+ +--+ | |Ozhidanie vvoda-vyvoda,| +--+ +--+ +--+ | preryvaniya | svyazannogo s diskom |-+ +-+ +-+ | | +----------------------+ +--+ +--+ +--+ | | Ozhidanie | +--+ +--+ | | bufera |-+ +-+ | | +----------------------+ +--+ +--+ | | Ozhidanie | +--+ | | indeksa |-+ | | +----------------------+ +--+ | +----------------------+ | | Ozhidanie vvoda s ter-| +--+ +--+ +--+ +--+ | | minala |-+ +-+ +-+ +-+ | | Dopuskayushchie +----------------------+ +--+ +--+ +--+ +--+ | | Ozhidanie vyvoda na | | preryvaniya | terminal | | +----------------------+ | | Ozhidanie zaversheniya | +--+ +--+ | | potomka |-+ +-+ | v +----------------------+ +--+ +--+ Porogovyj prioritet +----------------------+ ^ | Uroven' zadachi 0 | | +----------------------+ +--+ +--+ +--+ +--+ | | Uroven' zadachi 1 |-+ +-+ +-+ +-+ | | +----------------------+ +--+ +--+ +--+ +--+ | | - | | | - | | +----------------------+ +--+ Prioritety vypolneniya | Uroven' zadachi n |-+ | v rezhime zadachi +----------------------+ +--+ Risunok 8.2. Diapazon prioritetov processa 234 kontekst, blagodarya chemu sokratitsya vremya reakcii processa i uvelichitsya proizvoditel'nost' sistemy. Vo-vtoryh, bufer, osvobozhdeniya kotorogo ozhi- daet process, mozhet byt' zanyat processom, ozhidayushchim v svoyu ochered' za- versheniya vvoda-vyvoda. Po zavershenii vvoda-vyvoda budut vozobnovleny oba processa, poskol'ku oni byli priostanovleny po odnomu i tomu zhe adresu. Esli pervym zapustit' na vypolnenie process, ozhidayushchij osvobozhdeniya bu- fera, on v lyubom sluchae snova priostanovitsya do teh por, poka bufer ne budet osvobozhden; sledovatel'no, ego prioritet dolzhen byt' nizhe. * Po vozvrashchenii processa iz rezhima yadra v rezhim zadachi yadro vnov' vychis- lyaet prioritet processa. Process mog do etogo nahodit'sya v sostoyanii priostanova, izmeniv svoj prioritet na prioritet vypolneniya v rezhime yad- ra, poetomu pri perehode processa iz rezhima yadra v rezhim zadachi emu dol- zhen byt' vozvrashchen prioritet vypolneniya v rezhime zadachi. Krome togo, yad- ro "shtrafuet" vypolnyayushchijsya process v pol'zu ostal'nyh processov, otbi- raya ispol'zuemye im cennye sistemnye resursy. * Prioritety vseh processov v rezhime zadachi s intervalom v 1 sekundu (v versii V) pereschityvaet programma obrabotki preryvanij po tajmeru, po- buzhdaya tem samym yadro vypolnyat' algoritm planirovaniya, chtoby ne dopus- tit' monopol'nogo ispol'zovaniya resursov CP odnim processom. V techenie kvanta vremeni tajmer mozhet poslat' processu neskol'ko prery- vanij; pri kazhdom preryvanii programma obrabotki preryvanij po tajmeru uve- lichivaet znachenie, hranyashcheesya v pole tablicy processov, kotoroe opisyvaet prodolzhitel'nost' ispol'zovaniya resursov central'nogo processora (ICP). V versii V kazhduyu sekundu programma obrabotki preryvanij pereustanavlivaet znachenie etogo polya, ispol'zuya funkciyu poluraspada (decay): decay(ICP) = ICP/2; Posle etogo programma pereschityvaet prioritet kazhdogo processa, nahodyashchegosya v sostoyanii "zarezervirovan, no gotov k vypolneniyu", po formule prioritet = (ICP/2) + (bazovyj uroven' prioriteta zadachi) gde pod "bazovym urovnem prioriteta zadachi" ponimaetsya porogovoe znachenie, raspolozhennoe mezhdu prioritetami vypolneniya v rezhimah yadra i zadachi. Vysoko- mu prioritetu planirovaniya sootvetstvuet kolichestvenno nizkoe znachenie. Ana- liz funkcij perescheta prodolzhitel'nosti ispol'zovaniya resursov CP i priori- teta processa pokazyvaet: chem nizhe skorost' poluraspada znacheniya ICP, tem medlennee prioritet processa dostigaet znachenie bazovogo urovnya; poetomu processy v sostoyanii "gotovnosti k vypolneniyu" imeyut tendenciyu zanimat' bol'shoe chislo urovnej prioritetov. Rezul'tatom ezhesekundnogo perescheta prioritetov yavlyaetsya peremeshchenie processov, nahodyashchihsya v rezhime zadachi, ot odnoj ocheredi k drugoj, kak poka- zano na Risunke 8.3. Po sravneniyu s Risunkom 8.2 odin process pereshel iz ocheredi, sootvetstvuyushchej urovnyu 1, v ochered', sootvetstvuyushchuyu nulevomu urov- nyu. V real'noj sisteme vse processy, imeyushchie prioritety vypolneniya v rezhime zadachi, pomenyali by svoe mestopolozhenie v ocheredyah. Pri etom sleduet ukazat' na nevozmozhnost' izmeneniya prioriteta processa v rezhime yadra, a takzhe na ne- vozmozhnost' peresecheniya porogovoj cherty processami, vypolnyayushchimisya v rezhime zadachi, do teh por, poka oni ne obratyatsya k operacionnoj sisteme i ne perej- dut v sostoyanie priostanova. YAdro stremitsya proizvodit' pereschet prioritetov vseh aktivnyh processov ezhesekundno, odnako interval mezhdu momentami perescheta mozhet slegka var'iro- vat'sya. Esli preryvanie po tajmeru postupilo togda, kogda yadro ispolnyalo kriticheskij otrezok programmy (drugimi slovami, v to vremya, kogda prioritet raboty CP byl povyshen, no, ochevidno, ne nastol'ko, chtoby vosprepyatstvovat' 235 preryvaniyu dannogo tipa), yadro ne pereschityvaet prioritety, inache emu prish- los' by nadolgo zaderzhat'sya na kriticheskom otrezke. Vmesto etogo yadro zapo- minaet to, chto emu sleduet proizvesti pereschet prioritetov, i delaet eto pri pervom zhe preryvanii po tajmeru, postupayushchem posle snizheniya prioriteta rabo- ty CP. Periodicheskij pereschet prioriteta processov garantiruet provedenie strategii planirovaniya, osnovannoj na ispol'zovanii kol'cevogo spiska pro- cessov, vypolnyayushchihsya v rezhime zadachi. Pri etom konechno zhe yadro otklikaetsya na interaktivnye zaprosy takih programm, kak tekstovye redaktory ili prog- rammy formatnogo vvoda: processy, ih realizuyushchie, imeyut vysokij koefficient prostoya (otnoshenie vremeni prostoya k prodolzhitel'nosti ispol'zovaniya CP) i poetomu estestvenno bylo by povyshat' ih prioritet, kogda oni gotovy dlya vy- polneniya (sm. [Thompson 78], str.1937). V drugih mehanizmah planirovaniya kvant vremeni, vydelyaemyj processu na rabotu s resursami CP, dinamicheski iz- menyaetsya v intervale mezhdu 0 i 1 sek. v zavisimosti ot stepeni zagruzki sis- temy. Pri etom vremya reakcii na zaprosy processov mozhet Prioritety vypolneniya Urovni prioritetov Processy v rezhime yadra | +----------------------+ | | Process | +--+ | | podkachki |-+ | | Ne dopuskayushchie +----------------------+ +--+ | |Ozhidanie vvoda-vyvoda,| +--+ +--+ +--+ | preryvaniya | svyazannogo s diskom |-+ +-+ +-+ | | +----------------------+ +--+ +--+ +--+ | | Ozhidanie | +--+ +--+ | | bufera |-+ +-+ | | +----------------------+ +--+ +--+ | | Ozhidanie | +--+ | | indeksa |-+ | | +----------------------+ +--+ | +----------------------+ | | Ozhidanie vvoda s ter-| +--+ +--+ +--+ +--+ | | minala |-+ +-+ +-+ +-+ | | Dopuskayushchie +----------------------+ +--+ +--+ +--+ +--+ | | Ozhidanie vyvoda na | | preryvaniya | terminal | | +----------------------+ | | Ozhidanie zaversheniya | +--+ +--+ | | potomka |-+ +-+ | v +----------------------+ +--+ +--+ Porogovyj prioritet +----------------------+ +--+ ^ | Uroven' zadachi 0 |-+ |<- - - - - -+ | +----------------------+ +--+ - | | | +--+ +--+ +--+ ++-+ | | Uroven' zadachi 1 |-+ +-+ +-+ + + | | +----------------------+ +--+ +--+ +--+ +--+ | | - | | | - | | +----------------------+ +--+ Prioritety vypolneniya | Uroven' zadachi n |-+ | v rezhime zadachi +----------------------+ +--+ Risunok 8.2. Perehod processa iz odnoj ocheredi v druguyu sokratit'sya za schet togo, chto na ozhidanie momenta zapuska processam uzhe ne nuzhno otvodit' po celoj sekunde; odnako, s drugoj storony, yadru prihoditsya chashche pribegat' k pereklyucheniyu kontekstov. 236 8.1.3 Primery dispetcherizacii processov Na Risunke 8.4 pokazana dinamika izmenenij prioritetov processov A, B i C v versii V pri sleduyushchih dopushcheniyah: vse eti processy byli sozdany s per- vonachal'nym prioritetom 60, kotoryj yavlyaetsya naivysshim prioritetom vypolne- niya v rezhime zadachi, preryvaniya po tajmeru postupayut 60 raz v sekundu, pro- cessy ne ispol'zuyut vyzov sistemnyh funkcij, v sisteme net drugih processov, gotovyh k vypolneniyu. YAdro vychislyaet poluraspad pokazatelya ICP po formule: Vremya Process A Process B Process C | Prioritet ICP - Prioritet ICP - Prioritet ICP 0 --+-- - - | 60 0 - 60 0 - 60 0 | 1 - - | 2 - - | ­ - - | ­ - - 1 --+-- 60 - - | 75 30 - 60 0 - 60 0 | - 1 - | - 2 - | - ­ - | - ­ - 2 --+-- - 60 - | 67 15 - 75 30 - 60 0 | - - 1 | - - 2 | - - ­ | - - ­ 3 --+-- - - 60 | 63 7 - 67 15 - 75 30 | 8 - - | 9 - - | ­ - - | ­ - - 4 --+-- 67 - - | 76 33 - 63 7 - 67 15 | - 8 - | - 9 - | - ­ - | - ­ - 5 --+-- - 67 - | 68 16 - 76 33 - 63 7 | - - | - - Risunok 8.4. Primer dispetcherizacii processov ICP = decay(ICP) = ICP/2; a prioritet processa po formule: prioritet = (ICP/2) + 60; Esli predpolozhit', chto pervym zapuskaetsya process A i emu vydelyaetsya kvant vremeni, on vypolnyaetsya v techenie 1 sekundy: za eto vremya tajmer posylaet sisteme 60 preryvanij i stol'ko zhe raz programma obrabotki preryvanij uveli- chivaet dlya processa A znachenie polya, soderzhashchego pokazatel' ICP (s 0 do 60). 237 Po proshestvii sekundy yadro pereklyuchaet kontekst i, proizvedya pereschet prio- ritetov dlya vseh processov, vybiraet dlya vypolneniya process B. V techenie sleduyushchej sekundy programma obrabotki preryvanij po tajmeru 60 raz povyshaet znachenie polya ICP dlya processa B, posle chego yadro pereschityvaet parametry dispetcherizacii dlya vseh processov i vnov' pereklyuchaet kontekst. Procedura povtoryaetsya mnogokratno, soprovozhdayas' poocherednym zapuskom processov na vy- polnenie. Teper' rassmotrim processy s prioritetami, privedennymi na Risunke 8.5, i predpolozhim, chto v sisteme imeyutsya i drugie processy. YAdro mozhet vygruzit' process A, ostaviv ego v sostoyanii "gotovnosti k vypolneniyu", posle togo, kak on poluchit podryad neskol'ko kvantov vremeni dlya raboty s CP i snizit ta- kim obrazom svoj prioritet vypolneniya v rezhime zadachi (Risunok 8.5a). CHerez nekotoroe vremya posle zapuska processa A v sostoyanie "gotovnosti k vypolne- niyu" mozhet perejti process B, prioritet kotorogo v tot moment okazhetsya vyshe prioriteta processa A (Risunok 8.5b). Esli yadro za eto vremya ne zaplanirova- lo k vypolneniyu lyuboj drugoj process (iz teh, chto ne pokazany na risunke), oba processa (A i B) pri izvestnyh obstoyatel'stvah mogut na nekotoroe vremya okazat'sya na odnom urovne prioritetnosti, hotya process B popadet na etot uroven' pervym iz-za togo, chto ego pervonachal'nyj prioritet byl blizhe (Risu- nok 8.5v i 8.5g). Tem ne menee, yadro zapustit process A vperedi processa B, poskol'ku process A nahodilsya v sostoyanii "gotovnosti k vypolneniyu" bolee dlitel'noe vremya (Risunok 8.5d) - eto reshayushchee uslovie, esli vybor proizvo- ditsya iz processov s odinakovymi prioritetami. V razdele 6.4.3 uzhe govorilos' o tom, chto yadro zapuskaet process na vy- polnenie posle pereklyucheniya konteksta: prezhde chem perejti v sostoyanie prios- tanova ili zavershit' svoe vypolnenie process dolzhen pereklyuchit' kontekst, krome togo on imeet vozmozhnost' pereklyuchat' kontekst v moment perehoda iz rezhima yadra v rezhim zadachi. YAdro vygruzhaet process, kotoryj sobiraetsya pe- rejti v rezhim zadachi, esli imeetsya gotovyj k vypolneniyu process s bolee vy- sokim prioritetom. Takaya situaciya voznikaet, esli yadro vyvelo iz sostoyaniya priostanova process s prioritetom, prevyshayushchim prioritet tekushchego processa, ili esli v rezul'tate obrabotki preryvaniya po tajmeru izmenilis' prioritety vseh gotovyh k vypolneniyu processov. V pervom sluchae tekushchij process ne mo- zhet vypolnyat'sya v rezhime zadachi, poskol'ku imeetsya process s bolee vysokim prioritetom vypolneniya v rezhime yadra. Vo vtorom sluchae programma obrabotki preryvanij po tajmeru reshaet, chto process ispol'zoval vydelennyj emu kvant vremeni, i poskol'ku mnozhestvo processov pri etom menyayut svoi prioritety, yadro vypolnyaet pereklyuchenie konteksta. 8.1.4 Upravlenie prioritetami Processy mogut upravlyat' svoimi prioritetami s pomoshch'yu sistemnoj funkcii nice: nice(value); gde value - znachenie, v processe perescheta pribavlyaemoe k priori- tetu processa: prioritet = (ICP/konstanta) + (bazovyj prioritet) + (znachenie nice) Sistemnaya funkciya nice uvelichivaet ili umen'shaet znachenie polya nice v tabli- ce processov na velichinu parametra funkcii, pri etom tol'ko superpol'zovate- lyu dozvoleno ukazyvat' znacheniya, uvelichivayushchie prioritet processa. Krome to- go, tol'ko superpol'zovatel' mozhet ukazyvat' znacheniya, lezhashchie nizhe oprede- lennogo poroga. Pol'zovateli, vyzyvayushchie sistemnuyu funkciyu nice dlya togo, chtoby ponizit' prioritet vo vremya vypolneniya intensivnyh vychislitel'nyh ra- bot, "udobny, priyatny" (nice) dlya ostal'nyh pol'zovatelej sis- 238 +---------+ +---------+ +---------+ ^ 60 +---------+ +---------+ +----B----+ | +---------+ +---------+ +---------+ | +---------+ +----B----+ +----A----+ Bolee +---------+ +---------+ +---------+ vysokij +---------+ +----A----+ +---------+ priori- +---------+ +---------+ +---------+ tet +----A----+ +---------+ +---------+ | +---------+ +---------+ +---------+ | (a) (b) (v) +----B----+ +-A-----B-+ +----B----+ 60 +----A----+ +---------+ +---------+(process +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ (g) (d) (e) Risunok 8.5. Planirovanie na osnove kol'cevogo spiska i prio- ritety processov temy, otsyuda nazvanie funkcii. Processy nasleduyut znachenie nice u svoego ro- ditelya pri vypolnenii sistemnoj funkcii fork. Funkciya nice dejstvuet tol'ko dlya vypolnyayushchihsya processov; process ne mozhet sbrosit' znachenie nice u dru- gogo processa. S prakticheskoj tochki zreniya eto oznachaet, chto esli administ- ratoru sistemy ponadobilos' ponizit' prioritety razlichnyh processov, trebuyu- shchih dlya svoego vypolneniya slishkom mnogo vremeni, u nego ne budet drugogo sposoba sdelat' eto bystro, krome kak vyzvat' funkciyu udaleniya (kill) dlya vseh nih srazu. 8.1.5 Planirovanie na osnove spravedlivogo razdela Vysheopisannyj algoritm planirovaniya ne vidit nikakoj raznicy mezhdu pol'- zovatelyami razlichnyh klassov (kategorij). Drugimi slovami, nevozmozhno vyde- lit' opredelennoj sovokupnosti processov, naprimer, polovinu seansa raboty s CP. Tem ne menee, takaya vozmozhnost' imeet vazhnoe znachenie dlya organizacii raboty v usloviyah vychislitel'nogo centra, gde gruppa pol'zovatelej mozhet po- zhelat' kupit' tol'ko polovinu mashinnogo vremeni na garantirovannoj osnove i s garantirovannym urovnem reakcii. Zdes' my rassmotrim shemu, imenuemuyu "Planirovaniem na osnove spravedlivogo razdela" (Fair Share Scheduler) i re- alizovannuyu na vychislitel'nom centre Indian Hill firmy AT&T Bell Laboratories [Henry 84]. Princip "planirovaniya na osnove spravedlivogo razdela" sostoit v delenii sovokupnosti pol'zovatelej na gruppy, yavlyayushchiesya ob®ektami ogranichenij, nak- ladyvaemyh obychnym planirovshchikom na obrabotku processov iz kazhdoj gruppy. Pri etom sistema vydelyaet vremya CP proporcional'no chislu grupp, vne zavisi- mosti ot togo, skol'ko processov vypolnyaetsya v gruppe. Pust', naprimer, v sisteme imeyutsya chetyre planiruemye gruppy, kazhdaya iz kotoryh zagruzhaet CP na 25% i soderzhit, sootvetstvenno, 1, 2, 3 i 4 processa, realizuyushchih schetnye zadachi, kotorye nikogda po svoej vole ne ustupyat CP. Pri uslovii, chto v sis- teme bol'she net nikakih drugih processov, kazhdyj process pri ispol'zovanii tradicionnogo algoritma planirovaniya poluchil by 10% vremeni CP (poskol'ku 239 vsego processov 10 i mezhdu nimi ne delaetsya nikakih razlichij). Pri ispol'zo- vanii algoritma planirovaniya na osnove spravedlivogo razdela process iz per- voj gruppy poluchit v dva raza bol'she vremeni CP po sravneniyu s kazhdym pro- cessom iz vtoroj gruppy, v 3 raza bol'she po sravneniyu s kazhdym processom iz tret'ej gruppy i v 4 raza bol'she po sravneniyu s kazhdym processom iz chetver- toj. V etom primere vsem processam v gruppe vydelyaetsya ravnoe vremya, pos- kol'ku prodolzhitel'nost' cikla, realizuemogo kazhdym processom, zaranee ne ustanovlena. Realizaciya etoj shemy dovol'no prosta, chto i delaet ee privlekatel'noj. V formule rascheta prioriteta processa poyavlyaetsya eshche odin termin - "priori- tet gruppy spravedlivogo razdela". V prostranstve processa takzhe poyavlyaetsya novoe pole, opisyvayushchee prodolzhitel'nost' ICP na osnove spravedlivogo razde- la, obshchuyu dlya vseh processov iz gruppy. Programma obrabotki preryvanij po tajmeru uvelichivaet znachenie etogo polya dlya tekushchego processa i ezhesekundno pereschityvaet znacheniya sootvetstvuyushchih polej dlya vseh processov v sisteme. Novaya komponenta formuly vychisleniya prioriteta processa predstavlyaet soboj normalizovannoe znachenie ICP dlya kazhdoj gruppy. CHem bol'she processornogo vremeni vydelyaetsya processam gruppy, tem vyshe znachenie etogo pokazatelya i nizhe prioritet. V kachestve primera rassmotrim dve gruppy processov (Risunok 8.6), v od- noj iz kotoryh odin process (A), v drugoj - dva (B i C). Predpolozhim, chto yadro pervym zapustilo na vypolnenie process A, v techenie sekundy uvelichivaya sootvetstvuyushchie etomu processu znacheniya polej, opisyvayushchih individual'noe i gruppovoe ICP. V rezul'tate perescheta prioritetov po istechenii sekundy pro- cessy B i C budut imet' naivysshie prioritety. Dopustim, chto yadro vybiraet na vypolnenie process B. V techenie sleduyushchej sekundy znachenie polya ICP dlya pro- cessa B podnimaetsya do 60, tochno takoe zhe znachenie prinimaet pole gruppovogo ICP dlya processov B i C. Takim obrazom, po istechenii vtoroj sekundy process C poluchit prioritet, ravnyj 75 (sravnite s Risunkom 8.4), i yadro zapustit na vypolnenie process A s prioritetom 74. Dal'nejshie dejstviya mozhno prosledit' na risunke: yadro po ocheredi zapuskaet processy A, B, A, C, A, B i t.d. 8.1.6 Rabota v rezhime real'nogo vremeni Rezhim real'nogo vremeni podrazumevaet vozmozhnost' obespecheniya dostatoch- noj skorosti reakcii na vneshnie preryvaniya i vypolneniya otdel'nyh processov v tempe, soizmerimom s chastotoj vozniknoveniya vyzyvayushchih preryvaniya sobytij. Primerom sistemy, rabotayushchej v rezhime real'nogo vremeni, mozhet sluzhit' sis- tema upravleniya zhizneobespecheniem pacientov bol'nic, mgnovenno reagiruyushchaya na izmenenie sostoyaniya pacienta. Processy, podobnye tekstovym redaktoram, ne schitayutsya processami real'nogo vremeni: v nih bystraya reakciya na dejstviya pol'zovatelya yavlyaetsya zhelatel'noj, no ne neobhodimoj (nichego strashnogo ne proizojdet, esli pol'zovatel', vypolnyayushchij redaktirovanie teksta, podozhdet otveta neskol'ko lishnih sekund, hotya u pol'zovatelya na etot schet mogut byt' i svoi soobrazheniya). Vysheopisannye algoritmy planirovaniya vypolneniya proces- sov prednaznacheny special'no dlya ispol'zovaniya v sistemah razdeleniya vremeni i ne godyatsya dlya uslovij raboty v rezhime real'nogo vremeni, poskol'ku ne ga- rantiruyut zapusk yadrom kazhdogo processa v techenie fiksirovannogo intervala vremeni, pozvolyayushchego govorit' o vzaimodejstvii vychislitel'noj sistemy s processami v tempe, soizmerimom so skorost'yu protekaniya etih processov. Dru- goj pomehoj v podderzhke raboty v rezhime real'nogo vremeni yavlyaetsya nevygru- zhaemost' yadra; yadro ne mozhet planirovat' vypolnenie processa real'nogo vre- meni v rezhime zadachi, esli ono uzhe ispolnyaet drugoj process v rezhime yadra, bez vneseniya v rabotu sushchestvennyh izmenenij. V nastoyashchee vremya sistemnym programmistam prihoditsya perevodit' processy real'nogo vremeni v rezhim yadra, chtoby obespechit' dostatochnuyu skorost' reakcii. Pravil'noe reshenie etoj prob- lemy - dat' takim processam vozmozhnost' dinamicheskogo protekaniya (drugimi slovami, oni ne dolzhny byt' vstroeny v yadro) s predostavleniem sootvetstvuyu- 240 Vremya Process A Process B Process C | Prio- In- Grup-- Prio- In- Grup-- Prio- In- Grup- | ritet divi- po- - ritet divi- po- - ritet divi- po- | dual. voe - dual. voe - dual. voe | ICP ICP - ICP ICP - ICP ICP 0 --+-- - - | 60 0 0 - 60 0 0 - 60 0 0 | 1 1 - - | 2 2 - - | ­ ­ - - | ­ ­ - - 1 --+-- 60 60 - - | 90 30 30 - 60 0 0 - 60 0 0 | - 1 1 - 1 | - 2 2 - 2 | - ­ ­ - ­ | - ­ ­ - ­ 2 --+-- - 60 60 - 60 | 74 15 15 - 90 30 30 - 75 0 30 | 16 16 - - | 17 17 - - | ­ ­ - - | ­ ­ - - 3 --+-- 75 75 - - | 96 37 37 - 74 15 15 - 67 0 15 | - 16 - 1 16 | - 17 - 2 17 | - ­ - ­ ­ | - ­ - ­ ­ 4 --+-- - 75 - 60 75 | 78 18 18 - 81 7 37 - 93 30 37 | 19 19 - - | 20 20 - - | ­ ­ - - | ­ ­ - - 5 --+-- 78 78 - - | 98 39 39 - 70 3 18 - 76 15 18 | - - | - - Risunok 8.6. Primer planirovaniya na osnove spravedlivogo razdela, v ko- torom ispol'zuyutsya dve gruppy s tremya processami shchego mehanizma, s pomoshch'yu kotorogo oni mogli by soobshchat' yadru o svoih nuzh- dah, vytekayushchih iz osobennostej raboty v rezhime real'nogo vremeni. Na segod- nyashnij den' v standartnoj sisteme UNIX takaya vozmozhnost' otsutstvuet. 8.2 SISTEMNYE OPERACII, SVYAZANNYE SO VREMENEM Sushchestvuet neskol'ko sistemnyh funkcij, imeyushchih otnoshenie k vremeni pro- tekaniya processa: stime, time, times i alarm. Pervye dve imeyut delo s glo- bal'nym sistemnym vremenem, poslednie dve - s vremenem vypolneniya otdel'nyh processov. Funkciya stime daet superpol'zovatelyu vozmozhnost' zanosit' v global'nuyu nie global'noj peremennoj. Vybiraetsya vremya iz etoj peremennoj s pomoshch'yu funkcii time: 241 time(tloc); gde tloc - ukazatel' na peremennuyu, prinadlezhashchuyu processu, v kotoruyu zano- sitsya vozvrashchaemoe funkciej znachenie. Funkciya vozvrashchaet eto znachenie i iz samoj sebya, naprimer, komande date, kotoraya vyzyvaet etu funkciyu, chtoby op- redelit' tekushchee vremya. Funkciya times vozvrashchaet summarnoe vremya vypolneniya processa i vseh ego potomkov, prekrativshih sushchestvovanie, v rezhimah yadra i zadachi. Sintaksis vy- +------------------------------------------------------------+ | #include | | #include | | extern long times(); | | | | main() | | { | | int i; | | /* tms - imya struktury dannyh, sostoyashchej iz 4 elemen- | | tov */ | | struct tms pb1,pb2; | | long pt1,pt2; | | | | pt1 = times(&pb1); | | for (i = 0; i < 10; i++) | | if (fork() == 0) | | child(i); | | | | for (i = 0; i < 10; i++) | | wait((int*) 0); | | pt2 = times(&pb2); | | printf("process-roditel': real'noe vremya %u | | v rezhime zadachi %u v rezhime yadra %u | | potomki: v rezhime zadachi %u v rezhime yadra %u\n",| | pt2 - pt1,pb2.tms_utime - pb1.tms_utime, | | pb2.tms_stime - pb1.tms_stime, | | pb2.tms_cutime - pb1.tms_cutime, | | pb2.tms_cstime - pb1.tms_cstime); | | } | | | | child(n); | | int n; | | { | | int i; | | struct tms cb1,cb2; | | long t1,t2; | | | | t1 = times(&cb1); | | for (i = 0; i < 10000; i++) | | ; | | t2 = times(&cb2); | | printf("potomok %d: real'noe vremya %u v rezhime zadachi %u| | v rezhime yadra %u\n",n,t2 - t1, | | cb2.tms_utime - cb1.tms_utime, | | cb2.tms_stime - cb1.tms_stime); | | exit(); | | } | +------------------------------------------------------------+ Risunok 8.7. Primer programmy, ispol'zuyushchej funkciyu times 242 zova funkcii: times(tbuffer) struct tms *tbuffer; gde tms - imya struktury, v kotoruyu pomeshchayutsya vozvrashchaemye znacheniya i koto- raya opisyvaetsya sleduyushchim obrazom: struct tms { /* time_t - imya struktury dannyh, v kotoroj hranitsya vremya */ time_t tms_utime; /* vremya vypolneniya processa v rezhime zadachi */ time_t tms_stime; /* vremya vypolneniya processa v rezhime yadra */ time_t tms_cutime; /* vremya vypolneniya potomkov v rezhime zadachi */ time_t tms_cstime; /* vremya vypolneniya potomkov v rezhime yadra */ }; Funkciya times vozvrashchaet vremya, proshedshee "s nekotorogo proizvol'nogo momen- ta v proshlom", kak pravilo, s momenta zagruzki sistemy. Na Risunke 8.7 privedena programma, v kotoroj process-roditel' sozdaet 10 potomkov, kazhdyj iz kotoryh 10000 raz vypolnyaet pustoj cikl. Process-ro- ditel' obrashchaetsya k funkcii times pered sozdaniem potomkov i posle ih zaver- sheniya, v svoyu ochered' potomki vyzyvayut etu funkciyu pered nachalom cikla i posle ego zaversheniya. Kto-to po naivnosti mozhet podumat', chto vremya vypolne- niya potomkov processa v rezhimah zadachi i yadra ravno summe sootvetstvuyushchih slagaemyh kazhdogo potomka, a real'noe vremya processa-roditelya yavlyaetsya sum- moj real'nogo vremeni ego potomkov. Odnako, vremya vypolneniya potomkov ne vklyuchaet v sebya vremya, zatrachennoe na ispolnenie sistemnyh funkcij fork i exit, krome togo ono mozhet byt' iskazheno za schet obrabotki preryvanij i pe- reklyuchenij konteksta. S pomoshch'yu sistemnoj funkcii alarm pol'zovatel'skie processy mogut inici- irovat' posylku signalov trevogi ("budil'nika") cherez kratnye promezhutki vremeni. Naprimer, programma na Risunke 8.8 kazhduyu minutu proveryaet vremya dostupa k fajlu i, esli k fajlu bylo proizvedeno obrashchenie, vyvodit sootvet- stvuyushchee soobshchenie. Dlya etogo v cikle, s pomoshch'yu funkcii stat, ustanavliva- etsya moment poslednego obrashcheniya k fajlu i, esli ono imelo mesto v techenie poslednej minuty, vyvoditsya soobshchenie. Zatem process s pomoshch'yu funkcii signal delaet rasporyazhenie prinimat' signaly trevogi, s pomoshch'yu funkcii alarm zadaet interval