Enkonduko al Operaciumoj
Hej Habr! Mi ŝatus atentigi vin serion da artikoloj-tradukoj de unu interesa literaturo laŭ mi - OSTEP. Ĉi tiu materialo diskutas sufiĉe profunde la laboron de Unikso-similaj operaciumoj, nome, laboro kun procezoj, diversaj planiloj, memoro kaj aliaj similaj komponantoj kiuj konsistigas modernan OS. Vi povas vidi la originalon de ĉiuj materialoj ĉi tie . Bonvolu noti, ke la traduko estis farita senprofesie (sufiĉe libere), sed mi esperas, ke mi konservis la ĝeneralan signifon.
Laboratorio pri ĉi tiu temo troveblas ĉi tie:
Aliaj partoj:
Vi ankaŭ povas kontroli mian kanalon ĉe =)
Enkonduko al Scheduler
La esenco de la problemo: Kiel evoluigi planan politikon
Kiel la subestaj planigaj politikaj kadroj estu desegnitaj? Kio devus esti la ŝlosilaj supozoj? Kiuj metrikoj estas gravaj? Kiuj bazaj teknikoj estis uzitaj en fruaj komputiksistemoj?
Supozoj de Laborŝarĝo
Antaŭ ol diskuti eblajn politikojn, ni unue faru kelkajn simpligajn digresojn pri la procezoj kurantaj en la sistemo, kiuj estas kolektive nomitaj laborŝarĝo. Difini la laborkvanton estas kritika parto de konstruado de politikoj, kaj ju pli vi scias pri la laborkvanto, des pli bona estas la politiko, kiun vi povas skribi.
Ni faru la sekvajn supozojn pri la procezoj kurantaj en la sistemo, foje ankaŭ nomataj laborpostenojn (taskoj). Preskaŭ ĉiuj ĉi tiuj supozoj ne estas realismaj, sed estas necesaj por la evoluo de penso.
- Ĉiu tasko funkcias por la sama kvanto de tempo,
- Ĉiuj taskoj estas fiksitaj samtempe,
- La asignita tasko funkcias ĝis sia kompletigo,
- Ĉiuj taskoj uzas nur CPU,
- La rultempo de ĉiu tasko estas konata.
Scheduler-Metrikoj
Aldone al iuj supozoj pri la ŝarĝo, necesas alia ilo por kompari malsamajn planpolitikojn: horarmetriko. Metriko estas nur iu mezuro de io. Estas kelkaj metrikoj, kiuj povas esti uzataj por kompari horarojn.
Ekzemple, ni uzos metrikon nomitan turniĝotempo (tempo de turniĝo). La taskorenda tempo estas difinita kiel la diferenco inter la taskokompleta tempo kaj la taska alventempo en la sistemo.
Tturnaro=Tkompletigo−Alveno
Ĉar ni supozis, ke ĉiuj taskoj alvenis samtempe, tiam Ta=0 kaj tiel Tt=Tc. Ĉi tiu valoro nature ŝanĝiĝos kiam ni ŝanĝas la suprajn supozojn.
Alia metriko - justeco (justeco, honesteco). Produktiveco kaj justeco ofte estas kontraŭstaraj trajtoj en planado. Ekzemple, la planisto povas optimumigi efikecon, sed koste de atendado de aliaj taskoj por funkcii, tiel reduktante justecon.
UNUA ENENUNUA ELIR (FIFO)
La plej baza algoritmo, kiun ni povas efektivigi, nomiĝas FIFO aŭ unua enveni (en), unue servita (el). Ĉi tiu algoritmo havas plurajn avantaĝojn: ĝi estas tre facila por efektivigi kaj ĝi kongruas kun ĉiuj niaj supozoj kaj faras la laboron sufiĉe bone.
Ni rigardu simplan ekzemplon. Ni diru, ke 3 taskoj estis fiksitaj samtempe. Sed ni supozu, ke tiu tasko A alvenis iom pli frue ol ĉiuj aliaj, do ĝi aperos en la ekzekutlisto pli frue ol la aliaj, same kiel B rilate al C. Ni supozu, ke ĉiu el ili estos plenumita dum 10 sekundoj. Kio estos la averaĝa tempo por plenumi ĉi tiujn taskojn en ĉi tiu kazo?
Nombrinte la valorojn - 10+20+30 kaj dividante per 3, ni ricevas la averaĝan programtempon de ekzekuto egala al 20 sekundoj.
Nun ni provu ŝanĝi niajn supozojn. Aparte, supozo 1 kaj tiel ni ne plu supozos, ke ĉiu tasko bezonas la saman tempon por plenumi. Kiel FIFO agos ĉi-foje?
Kiel ĝi rezultas, malsamaj taskaj ekzekuttempoj havas ekstreme negativan efikon al la produktiveco de la FIFO-algoritmo. Ni supozu, ke tasko A daŭros 100 sekundojn por plenumi, dum B kaj C ankoraŭ daŭros 10 sekundojn ĉiu.
Kiel videblas el la figuro, la averaĝa tempo por la sistemo estos (100+110+120)/3=110. Ĉi tiu efiko nomiĝas konvoja efiko, kiam iuj mallongperspektivaj konsumantoj de rimedo vidos post peza konsumanto. Estas kiel la vico ĉe la nutraĵvendejo, kiam estas kliento antaŭ vi kun plena ĉaro. La plej bona solvo al la problemo estas provi ŝanĝi la kason aŭ malstreĉiĝi kaj spiri profunde.
Plej Mallonga Laboro Unue
Ĉu eblas iel solvi similan situacion kun pezaj procezoj? Certe. Alia tipo de planado nomiĝasPlej Mallonga Laboro Unue (SJF). Ĝia algoritmo ankaŭ estas sufiĉe primitiva - kiel la nomo implicas, la plej mallongaj taskoj estos lanĉitaj unue, unu post la alia.
En ĉi tiu ekzemplo, la rezulto de rulado de la samaj procezoj estos plibonigo en la averaĝa programa tempodaŭro kaj ĝi estos egala al 50 anstataŭ 110, kiu estas preskaŭ 2 fojojn pli bona.
Tiel, por la antaŭfiksita supozo ke ĉiuj taskoj alvenas en la sama tempo, la SJF-algoritmo ŝajnas esti la plej optimuma algoritmo. Tamen niaj supozoj ankoraŭ ne ŝajnas realismaj. Ĉi-foje ni ŝanĝas supozon 2 kaj ĉi-foje imagu, ke taskoj povas ĉeesti iam ajn, kaj ne ĉiuj samtempe. Al kiuj problemoj ĉi tio povas konduki?
Ni imagu, ke tasko A (100c) alvenas unue kaj komencas esti plenumita. Je t=10, taskoj B kaj C alvenas, ĉiu el kiuj daŭros 10 sekundojn. Do la averaĝa ekzekuttempo estas (100+(110-10)+(120-10))3 = 103. Kion povus fari la planisto por plibonigi ĉi tion?
Plej Mallonga Tempo-al-Kompletiga Unue (STCF)
Por plibonigi la situacion, ni preterlasas supozon 3, ke la programo estas lanĉita kaj funkcias ĝis kompletigo. Krome, ni bezonos aparataron subtenon kaj, kiel vi povas supozi, ni uzos tempigilo interrompi kurantan taskon kaj kuntekstoŝanĝo. Tiel, la planisto povas fari ion en la momento kiun taskoj B, C alvenas - ĉesu plenumi taskon A kaj meti taskojn B kaj C en prilaboradon kaj, post ilia kompletigo, daŭrigi ekzekuti procezon A. Tia planilo nomiĝas STCFaŭ Antaŭzorga Laboro Unue.
La rezulto de ĉi tiu planilo estos la sekva rezulto: ((120-0)+(20-10)+(30-10))/3=50. Tiel, tia planilo fariĝas eĉ pli optimuma por niaj taskoj.
Metrika Responda Tempo
Tiel, se ni scias la rultempon de la taskoj kaj ke ĉi tiuj taskoj nur uzas CPU, STCF estos la plej bona solvo. Kaj unufoje en la fruaj tempoj, ĉi tiuj algoritmoj funkciis sufiĉe bone. Tamen, la uzanto nun pasigas la plej grandan parton de sia tempo ĉe la terminalo kaj atendas produktivan interagan sperton. Tiel nova metriko naskiĝis - respondtempo (respondo).
La respondtempo estas kalkulita jene:
Tresponse=Tfirstrun−Tarrival
Tiel, por la antaŭa ekzemplo, la respondtempo estos: A=0, B=0, C=10 (abg=3,33).
Kaj montriĝas, ke la STCF-algoritmo ne estas tiel bona en situacio, kie 3 taskoj alvenas samtempe - ĝi devos atendi ĝis la malgrandaj taskoj estas tute finitaj. Do la algoritmo estas bona por la turna tempometriko, sed malbona por la interagado metriko. Imagu, se vi sidus ĉe terminalo provante tajpi signojn en redaktilon kaj devi atendi pli ol 10 sekundojn ĉar iu alia tasko okupas la CPU. Ĝi ne estas tre agrabla.
Do ni alfrontas alian problemon - kiel ni povas konstrui planilon kiu estas sentema al respondtempo?
Ronda Robin
Algoritmo estis evoluigita por solvi ĉi tiun problemon Ronda Robin (RR). La baza ideo estas sufiĉe simpla: anstataŭ ruli taskojn ĝis ili finiĝos, ni rulos la taskon dum certa tempodaŭro (nomata tempotranĉo) kaj poste ŝanĝos al alia tasko de la vico. La algoritmo ripetas sian laboron ĝis ĉiuj taskoj estas kompletigitaj. En ĉi tiu kazo, la rultempo de la programo devas esti oblo de la tempo post kiu la tempigilo interrompos la procezon. Ekzemple, se tempigilo interrompas procezon ĉiun x=10ms, tiam la grandeco de la proceza ekzekutfenestro devus esti oblo de 10 kaj esti 10,20 aŭ x*10.
Ni rigardu ekzemplon: ABC-taskoj alvenas samtempe en la sistemon kaj ĉiu el ili volas funkcii dum 5 sekundoj. La SJF-algoritmo kompletigos ĉiun taskon antaŭ ol komenci alian. Kontraste, la RR-algoritmo kun lanĉa fenestro = 1s trairos la taskojn jene (Fig. 4.3):
(SJF Denove (Malbona por Responda Tempo)
(Round Robin (Bona Por Responda Tempo)
La meza respondtempo por la RR-algoritmo estas (0+1+2)/3=1, dum por la SJF (0+5+10)/3=5.
Estas logike supozi ke la tempofenestro estas tre grava parametro por RR; ju pli malgranda ĝi estas, des pli alta la respondtempo. Tamen, vi ne faru ĝin tro malgranda, ĉar kunteksta ŝanĝa tempo ankaŭ ludos rolon en ĝenerala agado. Tiel, la elekto de ekzekutfenestra tempo estas fiksita de la OS-arkitekto kaj dependas de la taskoj, kiuj estas planitaj por esti efektivigitaj en ĝi. Ŝanĝi kuntekston ne estas la sola serva operacio, kiu malŝparas tempon - la rula programo funkcias en multaj aliaj aferoj, ekzemple, diversaj kaŝmemoroj, kaj per ĉiu ŝaltilo necesas konservi kaj restarigi ĉi tiun medion, kiu ankaŭ povas preni multe da tempo.
RR estas bonega planilo se ni parolus nur pri la responda tempometriko. Sed kiel kondutas la metriko de la tempo de la tasko kun ĉi tiu algoritmo? Konsideru la ekzemplon supre, kiam la funkciada tempo de A, B, C = 5s kaj alvenas samtempe. Tasko A finiĝos je 13, B je 14, C je 15s kaj la averaĝa tempodaŭro estos 14s. Tiel, RR estas la plej malbona algoritmo por la spezometriko.
En pli ĝeneralaj esprimoj, ĉiu RR-speca algoritmo estas justa; ĝi dividas la CPU-tempon egale inter ĉiuj procezoj. Kaj tiel, ĉi tiuj metrikoj konstante konfliktas unu kun la alia.
Tiel, ni havas plurajn kontrastajn algoritmojn kaj samtempe restas ankoraŭ pluraj supozoj - ke la taskotempo estas konata kaj ke la tasko nur uzas la CPU.
Miksi kun I/O
Antaŭ ĉio, ni forigu la supozon 4, ke la procezo nur uzas la CPU; kompreneble, ĉi tio ne estas la kazo kaj procezoj povas aliri aliajn ekipaĵojn.
En la momento, kiam iu procezo petas I/O-operacion, la procezo eniras la blokitan staton, atendante ke la I/O kompletigus. Se I/O estas sendita al la malmola disko, tiam tia operacio povas daŭri ĝis pluraj ms aŭ pli longe, kaj la procesoro estos senaktiva ĉi-momente. Dum ĉi tiu tempo, la planisto povas okupi la procesoron per iu ajn alia procezo. La sekva decido, kiun la planisto devos fari, estas kiam la procezo kompletigos sian I/O. Kiam tio okazas, interrompo okazos kaj la OS metos la procezon kiu vokis la I/O en la pretan staton.
Ni rigardu ekzemplon de pluraj problemoj. Ĉiu el ili postulas 50ms da CPU-tempo. Tamen, la unua aliros I/O ĉiun 10ms (kiu ankaŭ estos efektivigita ĉiun 10ms). Kaj procezo B simple uzas 50ms procesoron sen I/O.
En ĉi tiu ekzemplo ni uzos la STCF-planilon. Kiel la planisto kondutos se procezo kiel A estas lanĉita sur ĝi? Li faros la jenon: unue li plene ellaboros procezon A, kaj poste procezon B.
La tradicia aliro por solvi ĉi tiun problemon estas trakti ĉiun 10 ms subtaskon de procezo A kiel apartan taskon. Tiel, kiam oni komencas kun la STJF-algoritmo, la elekto inter 50 ms tasko kaj 10 ms tasko estas evidenta. Tiam, kiam subtasko A estas kompletigita, procezo B kaj I/O estos lanĉitaj. Post kiam la I/O finiĝos, estos kutime komenci la 10ms-procezon A denove anstataŭ la procezo B. Tiamaniere, estas eble efektivigi interkovron, kie la CPU estas uzata de alia procezo dum la unua atendas la I/O. Kaj kiel rezulto, la sistemo estas pli bone utiligita - en la momento kiam interagaj procezoj atendas I/O, aliaj procezoj povas esti efektivigitaj sur la procesoro.
La Orakolo ne plu ekzistas
Nun ni provu forigi la supozon, ke la rultempo de la tasko estas konata. Ĉi tio estas ĝenerale la plej malbona kaj plej nereala supozo en la tuta listo. Fakte, en la averaĝa ordinara OS, la OS mem kutime scias tre malmulte pri la ekzekuttempo de taskoj, do kiel vi povas konstrui planilon sen scii kiom longe daŭros la tasko por plenumi? Eble ni povus uzi kelkajn RR-principojn por solvi ĉi tiun problemon?
La rezulto
Ni rigardis la bazajn ideojn de taskoplanado kaj rigardis 2 familiojn de planistoj. La unua komencas la plej mallongan taskon unue kaj tiel pliigas la respondan tempon, dum la dua estas disŝirita inter ĉiuj taskoj egale, pliigante la respondtempon. Ambaŭ algoritmoj estas malbonaj kie algoritmoj de la alia familio estas bonaj. Ni ankaŭ rigardis kiel paralela uzo de CPU kaj I/O povas plibonigi rendimenton, sed ne solvis la problemon kun OS-klarvido. Kaj en la sekva leciono ni rigardos planiston, kiu rigardas en la tujan pasintecon kaj provas antaŭdiri la estontecon. Kaj ĝi nomiĝas multnivela sugesta atendovico.
fonto: www.habr.com