Ifihan si Awọn ọna ṣiṣe
Hey Habr! Emi yoo fẹ lati mu si akiyesi rẹ lẹsẹsẹ awọn nkan-awọn itumọ ti awọn iwe ti o nifẹ ninu ero mi - OSTEP. Ohun elo yii n jiroro ni jinna iṣẹ ti awọn ọna ṣiṣe bi unix, eyun, ṣiṣẹ pẹlu awọn ilana, awọn oluṣeto oriṣiriṣi, iranti, ati awọn paati ti o jọra miiran ti o jẹ OS ode oni. O le wo atilẹba ti gbogbo awọn ohun elo nibi . Jọwọ ṣakiyesi pe a ṣe itumọ naa lainiṣiṣẹ (ni ọfẹ), ṣugbọn Mo nireti pe MO ni itumọ gbogbogbo mọ.
Iṣẹ lab lori koko yii le ṣee ri nibi:
Awọn ẹya miiran:
O tun le ṣayẹwo ikanni mi ni =)
Ifihan to Scheduler
Kokoro ti iṣoro naa: Bii o ṣe le ṣe agbekalẹ eto imulo iṣeto kan
Bawo ni o yẹ ki a ṣe apẹrẹ awọn ilana imulo iṣeto iṣeto? Kini o yẹ ki o jẹ awọn arosinu bọtini? Awọn metiriki wo ni o ṣe pataki? Awọn imọ-ẹrọ ipilẹ wo ni a lo ni awọn eto iširo kutukutu?
Iṣeduro Iṣeduro
Ṣaaju ki o to jiroro awọn eto imulo ti o ṣeeṣe, jẹ ki a kọkọ ṣe awọn digressions irọrun diẹ nipa awọn ilana ti n ṣiṣẹ ninu eto, eyiti a pe ni apapọ. fifuye iṣẹ. Itumọ fifuye iṣẹ jẹ apakan pataki ti awọn eto imulo ile, ati pe diẹ sii ti o mọ nipa iṣẹ ṣiṣe, eto imulo ti o dara julọ ti o le kọ.
Jẹ ki a ṣe awọn igbero wọnyi nipa awọn ilana ti nṣiṣẹ ninu eto, nigbakan tun pe ise (awọn iṣẹ-ṣiṣe). Fere gbogbo awọn arosinu wọnyi kii ṣe ojulowo, ṣugbọn jẹ pataki fun idagbasoke ti ero.
- Iṣẹ kọọkan nṣiṣẹ fun iye akoko kanna,
- Gbogbo awọn iṣẹ-ṣiṣe ti ṣeto ni akoko kanna,
- Iṣẹ-ṣiṣe ti a yàn ṣiṣẹ titi di ipari rẹ,
- Gbogbo awọn iṣẹ-ṣiṣe lo Sipiyu nikan,
- Akoko ṣiṣe ti iṣẹ-ṣiṣe kọọkan ni a mọ.
Awọn Metiriki Iṣeto
Ni afikun si diẹ ninu awọn arosinu nipa ẹru naa, ohun elo miiran fun ifiwera awọn eto imulo iṣeto oriṣiriṣi nilo: awọn metiriki iṣeto. Metiriki jẹ iwọn diẹ ninu nkan kan. Awọn metiriki nọmba kan wa ti o le ṣee lo lati ṣe afiwe awọn oluṣeto.
Fun apẹẹrẹ, a yoo lo metric ti a npe ni akoko iyipada (akoko iyipada). Akoko iyipada iṣẹ-ṣiṣe jẹ asọye bi iyatọ laarin akoko ipari iṣẹ-ṣiṣe ati akoko dide iṣẹ-ṣiṣe ninu eto naa.
Tturnaround=Ipari-Idede
Niwọn bi a ti ro pe gbogbo awọn iṣẹ-ṣiṣe de ni akoko kanna, lẹhinna Ta = 0 ati bayi Tt = Tc. Yi iye yoo nipa ti yi nigba ti a ba yi awọn loke awqn.
Metiriki miiran - didara (iṣotitọ, otitọ). Isejade ati ododo nigbagbogbo jẹ awọn abuda atako ni igbero. Fun apẹẹrẹ, oluṣeto le mu iṣẹ ṣiṣe pọ si, ṣugbọn ni idiyele ti nduro fun awọn iṣẹ ṣiṣe miiran lati ṣiṣẹ, nitorinaa dinku ododo.
NI KỌKỌ NI IJADE AKOKO (FIFO)
Algoridimu ipilẹ julọ ti a le ṣe ni a pe ni FIFO tabi kọkọ wọle (wọle), akọkọ ṣiṣẹ (jade). Algoridimu yii ni awọn anfani pupọ: o rọrun pupọ lati ṣe ati pe o baamu gbogbo awọn arosinu wa ati ṣe iṣẹ naa daradara.
Jẹ ki a wo apẹẹrẹ ti o rọrun. Jẹ ki a sọ pe awọn iṣẹ-ṣiṣe 3 ṣeto ni akoko kanna. Ṣugbọn jẹ ki a ro pe iṣẹ-ṣiṣe A ti de diẹ diẹ sii ju gbogbo awọn miiran lọ, nitorina o yoo han ninu akojọ ipaniyan ni iṣaaju ju awọn miiran lọ, gẹgẹbi B ti o ni ibatan si C. Jẹ ki a ro pe kọọkan ti wọn yoo wa ni pipa fun 10 aaya. Kini yoo jẹ akoko apapọ lati pari awọn iṣẹ-ṣiṣe wọnyi ninu ọran yii?
Nipa kika awọn iye - 10 + 20 + 30 ati pinpin nipasẹ 3, a gba akoko ipaniyan eto apapọ ti o dọgba si awọn aaya 20.
Bayi jẹ ki ká gbiyanju lati yi wa awqn. Ni pataki, arosinu 1 ati nitorinaa a ko ni ro pe iṣẹ-ṣiṣe kọọkan gba iye akoko kanna lati ṣiṣẹ. Bawo ni FIFO yoo ṣe ni akoko yii?
Bi o ti wa ni jade, awọn akoko ipaniyan iṣẹ-ṣiṣe oriṣiriṣi ni ipa odi pupọ lori iṣelọpọ ti FIFO algorithm. Jẹ ki a ro pe iṣẹ-ṣiṣe A yoo gba iṣẹju-aaya 100 lati pari, lakoko ti B ati C yoo tun gba iṣẹju-aaya 10 kọọkan.
Gẹgẹbi a ti le rii lati nọmba naa, akoko apapọ fun eto naa yoo jẹ (100+110+120)/3=110. Ipa yii ni a npe ni convoy ipa, nigbati diẹ ninu awọn onibara igba kukuru ti awọn oluşewadi kan yoo ti isinyi lẹhin ti olumulo ti o wuwo. O dabi laini ni ile itaja itaja nigbati alabara kan wa niwaju rẹ pẹlu ọkọ ayọkẹlẹ kikun. Ojutu ti o dara julọ si iṣoro naa ni lati gbiyanju lati yi iforukọsilẹ owo pada tabi sinmi ati simi jinna.
Iṣẹ ti o kuru ju
Ṣe o ṣee ṣe lati bakan yanju ipo kanna pẹlu awọn ilana iwuwo iwuwo? Dajudaju. Miiran iru ti igbogun ti a npe niIṣẹ ti o kuru ju (SJF). Algoridimu rẹ tun jẹ alakoko - bi orukọ ṣe tumọ si, awọn iṣẹ ṣiṣe ti o kuru julọ yoo ṣe ifilọlẹ ni akọkọ, ọkan lẹhin ekeji.
Ni apẹẹrẹ yii, abajade ti nṣiṣẹ awọn ilana kanna yoo jẹ ilọsiwaju ni akoko iyipada eto apapọ ati pe yoo jẹ dogba si 50 dipo 110, eyi ti o jẹ fere 2 igba dara.
Bayi, fun arosinu ti a fi fun pe gbogbo awọn iṣẹ-ṣiṣe de ni akoko kanna, SJF algorithm dabi ẹnipe algorithm to dara julọ. Sibẹsibẹ, awọn arosinu wa ko tun dabi ẹni pe o jẹ otitọ. Ni akoko yii a yipada arosinu 2 ati ni akoko yii fojuinu pe awọn iṣẹ-ṣiṣe le wa ni eyikeyi akoko, kii ṣe gbogbo ni akoko kanna. Awọn iṣoro wo ni eyi le ja si?
Jẹ ki a fojuinu pe iṣẹ-ṣiṣe A (100c) de akọkọ ati bẹrẹ lati ṣiṣẹ. Ni t=10, awọn iṣẹ-ṣiṣe B ati C de, ọkọọkan wọn yoo gba iṣẹju-aaya 10. Nitorinaa akoko ipaniyan apapọ jẹ (100+(110-10)+(120-10))3 = 103. Kini oluṣeto le ṣe lati mu eyi dara si?
Akoko Kuru ju-lati Ipari Ni akọkọ (STCF)
Lati le mu ipo naa dara, a yọkuro arosinu 3 pe eto naa ti ṣe ifilọlẹ ati ṣiṣe titi di ipari. Ni afikun, a yoo nilo atilẹyin ohun elo ati, bi o ṣe le gboju, a yoo lo aago lati da gbigbi a nṣiṣẹ-ṣiṣe ati o tọ yipada. Nitorinaa, oluṣeto le ṣe nkan ni akoko awọn iṣẹ-ṣiṣe B, C de - da iṣẹ ṣiṣe A duro ati fi awọn iṣẹ-ṣiṣe B ati C sinu sisẹ ati, lẹhin ipari wọn, tẹsiwaju ṣiṣe ilana A. Iru oluṣeto ni a pe STCFtabi Job Preemptive First.
Abajade oluṣeto yii yoo jẹ abajade atẹle yii: ((120-0)+ (20-10)+ (30-10))/3=50. Nitorinaa, iru oluṣeto bẹ paapaa dara julọ fun awọn iṣẹ ṣiṣe wa.
Metric Idahun Time
Bayi, ti a ba mọ akoko ṣiṣe ti awọn iṣẹ-ṣiṣe ati pe awọn iṣẹ-ṣiṣe wọnyi lo Sipiyu nikan, STCF yoo jẹ ojutu ti o dara julọ. Ati ni ẹẹkan ni awọn akoko ibẹrẹ, awọn algoridimu wọnyi ṣiṣẹ daradara daradara. Sibẹsibẹ, olumulo ni bayi lo pupọ julọ akoko rẹ ni ebute ati nireti iriri ibaraenisepo ti iṣelọpọ. Nitorinaa a bi metiriki tuntun kan - akoko idahun (idahun).
Akoko idahun jẹ iṣiro bi atẹle:
Tresponse=Tfirstrun-Idede
Nitorinaa, fun apẹẹrẹ iṣaaju, akoko idahun yoo jẹ: A=0, B=0, C=10 (abg=3,33).
Ati pe o wa ni pe STCF algorithm ko dara ni ipo kan nibiti awọn iṣẹ-ṣiṣe 3 de ni akoko kanna - yoo ni lati duro titi awọn iṣẹ-ṣiṣe kekere yoo pari patapata. Nitorinaa algorithm dara fun metiriki akoko iyipada, ṣugbọn buburu fun metiriki ibaraenisepo. Fojuinu ti o ba joko ni ebute kan ti o n gbiyanju lati tẹ awọn ohun kikọ sinu olootu ati nini lati duro diẹ sii ju awọn aaya 10 nitori iṣẹ-ṣiṣe miiran n gba Sipiyu naa. Ko dun pupo.
Nitorinaa a dojukọ iṣoro miiran - bawo ni a ṣe le kọ oluṣeto ti o ni itara si akoko idahun?
Yika Robin
A ṣe agbekalẹ algorithm kan lati yanju iṣoro yii Yika Robin (RR). Ero ipilẹ jẹ ohun ti o rọrun: dipo ṣiṣe awọn iṣẹ ṣiṣe titi ti wọn yoo fi pari, a yoo ṣiṣẹ iṣẹ naa fun akoko kan (ti a pe ni bibẹ akoko) ati lẹhinna yipada si iṣẹ-ṣiṣe miiran lati isinyi. Algoridimu tun iṣẹ rẹ ṣe titi gbogbo awọn iṣẹ-ṣiṣe yoo fi pari. Ni idi eyi, akoko ṣiṣe ti eto naa gbọdọ jẹ pupọ ti akoko lẹhin eyi ti aago yoo da ilana naa duro. Fun apẹẹrẹ, ti aago ba da ilana kan duro ni gbogbo x=10ms, lẹhinna iwọn ti window ipaniyan ilana yẹ ki o jẹ ọpọ ti 10 ati pe o jẹ 10,20 tabi x*10.
Jẹ ki a wo apẹẹrẹ: Awọn iṣẹ-ṣiṣe ABC de nigbakanna ninu eto ati ọkọọkan wọn fẹ lati ṣiṣẹ fun iṣẹju-aaya 5. SJF algorithm yoo pari iṣẹ-ṣiṣe kọọkan ṣaaju bẹrẹ miiran. Ni idakeji, algorithm RR pẹlu window ifilọlẹ = 1s yoo lọ nipasẹ awọn iṣẹ-ṣiṣe gẹgẹbi atẹle (Fig. 4.3):
(SJF Lẹẹkansi (Buburu fun Akoko Idahun)
(Round Yika (O dara Fun Akoko Idahun)
Akoko idahun apapọ fun algorithm RR jẹ (0+1+2)/3=1, lakoko fun SJF (0+5+10)/3=5.
O jẹ ohun ọgbọn lati ro pe window akoko jẹ paramita pataki pupọ fun RR; ti o kere si, akoko esi ga ga julọ. Sibẹsibẹ, o yẹ ki o ko jẹ ki o kere ju, niwọn igba ti akoko iyipada ọrọ yoo tun ṣe ipa ninu iṣẹ ṣiṣe gbogbogbo. Nitorinaa, yiyan akoko window ipaniyan ti ṣeto nipasẹ ayaworan OS ati da lori awọn iṣẹ ṣiṣe ti a gbero lati ṣiṣẹ ninu rẹ. Yiyipada ipo kii ṣe iṣẹ iṣẹ nikan ti o padanu akoko - eto ṣiṣiṣẹ ṣiṣẹ lori ọpọlọpọ awọn ohun miiran, fun apẹẹrẹ, ọpọlọpọ awọn caches, ati pẹlu iyipada kọọkan o jẹ dandan lati fipamọ ati mu agbegbe yii pada, eyiti o tun le gba pupọ. aago.
RR jẹ oluṣeto nla ti a ba sọrọ nikan nipa metiriki akoko idahun. Ṣugbọn bawo ni metiriki akoko iyipada iṣẹ-ṣiṣe yoo ṣe pẹlu algorithm yii? Wo apẹẹrẹ loke, nigbati akoko iṣẹ ti A, B, C = 5s ati de ni akoko kanna. Iṣẹ-ṣiṣe A yoo pari ni 13, B ni 14, C ni 15s ati pe akoko iyipada apapọ yoo jẹ 14s. Nitorinaa, RR jẹ algorithm ti o buru julọ fun metiriki iyipada.
Ni awọn ofin gbogbogbo diẹ sii, eyikeyi iru algorithm iru RR jẹ itẹ; o pin akoko Sipiyu ni dọgbadọgba laarin gbogbo awọn ilana. Ati nitorinaa, awọn metiriki wọnyi ni ija nigbagbogbo pẹlu ara wọn.
Nitorinaa, a ni ọpọlọpọ awọn algoridimu iyatọ ati ni akoko kanna ọpọlọpọ awọn arosinu tun wa - pe akoko iṣẹ-ṣiṣe jẹ mimọ ati pe iṣẹ-ṣiṣe nikan lo Sipiyu.
Dapọ pẹlu I/O
Ni akọkọ, jẹ ki a yọ arosinu 4 kuro pe ilana naa nlo Sipiyu nikan; nipa ti ara, eyi kii ṣe ọran ati awọn ilana le wọle si ohun elo miiran.
Ni akoko ti ilana eyikeyi ba beere iṣẹ I/O kan, ilana naa wọ inu ipo dina, nduro fun I/O lati pari. Ti a ba fi I/O ranṣẹ si dirafu lile, lẹhinna iru iṣẹ bẹẹ le gba to awọn ms pupọ tabi ju bẹẹ lọ, ati pe ero isise naa yoo wa laišišẹ ni akoko yii. Lakoko yii, oluṣeto le gba ero isise naa pẹlu eyikeyi ilana miiran. Ipinnu atẹle ti oluṣeto yoo ni lati ṣe ni igba ti ilana naa yoo pari I/O rẹ. Nigbati eyi ba ṣẹlẹ, idalọwọduro yoo waye ati OS yoo fi ilana ti a pe ni I/O sinu ipo imurasilẹ.
Jẹ ki a wo apẹẹrẹ ti awọn iṣẹ-ṣiṣe pupọ. Ọkọọkan wọn nilo 50ms ti akoko Sipiyu. Sibẹsibẹ, akọkọ yoo wọle si I/O ni gbogbo 10ms (eyiti yoo tun ṣe ni gbogbo 10ms). Ati ilana B nìkan nlo ero isise 50ms laisi I/O.
Ninu apẹẹrẹ yii a yoo lo oluṣeto STCF. Bawo ni oluṣeto yoo ṣe ti o ba ṣe ifilọlẹ ilana bii A lori rẹ? Oun yoo ṣe atẹle naa: akọkọ yoo ṣiṣẹ ilana A patapata, lẹhinna ilana B.
Ọna ibile lati yanju iṣoro yii ni lati tọju iṣẹ-ṣiṣe 10 ms kọọkan ti ilana A gẹgẹbi iṣẹ-ṣiṣe lọtọ. Nitorinaa, nigbati o bẹrẹ pẹlu algorithm STJF, yiyan laarin iṣẹ-ṣiṣe 50 ms ati iṣẹ-ṣiṣe 10 ms jẹ kedere. Lẹhinna, nigbati iṣẹ-ṣiṣe A ba ti pari, ilana B ati I/O yoo ṣe ifilọlẹ. Lẹhin ti I / O pari, yoo jẹ aṣa lati bẹrẹ ilana 10ms A lẹẹkansi dipo ilana B. Ni ọna yii, o ṣee ṣe lati ṣe imuse ni lqkan, nibiti Sipiyu ti lo nipasẹ ilana miiran lakoko ti akọkọ n duro de I/O. Ati bi abajade, eto naa dara julọ lati lo - ni akoko nigbati awọn ilana ibaraenisepo n duro de I / O, awọn ilana miiran le ṣee ṣe lori ero isise naa.
Oracle ko si mọ
Nisisiyi ẹ jẹ ki a gbiyanju lati yọkuro ero pe akoko ṣiṣe ti iṣẹ-ṣiṣe ni a mọ. Eyi jẹ gbogbogbo ti o buru julọ ati arosinu ti ko daju julọ lori gbogbo atokọ naa. Ni otitọ, ni apapọ OS arinrin, OS funrararẹ nigbagbogbo mọ diẹ diẹ nipa akoko ipaniyan ti awọn iṣẹ ṣiṣe, nitorinaa bawo ni o ṣe le kọ oluṣeto kan laisi mimọ bi iṣẹ ṣiṣe yoo ṣe pẹ to lati ṣiṣẹ? Boya a le lo diẹ ninu awọn ilana RR lati yanju iṣoro yii?
Abajade
A wo awọn imọran ipilẹ ti iṣeto iṣẹ-ṣiṣe ati wo awọn idile 2 ti awọn oluṣeto. Ni igba akọkọ ti bẹrẹ iṣẹ-ṣiṣe ti o kuru ju akọkọ ati bayi mu akoko iyipada pọ si, nigba ti keji ti ya laarin gbogbo awọn iṣẹ-ṣiṣe ni deede, npo akoko idahun. Awọn algoridimu mejeeji jẹ buburu nibiti awọn algoridimu ti idile miiran dara. A tun wo bii lilo ibaramu ti Sipiyu ati I/O le mu iṣẹ dara si, ṣugbọn ko yanju iṣoro naa pẹlu OS clairvoyance. Ati ninu ẹkọ ti o tẹle a yoo wo oluṣeto kan ti o wo inu ohun ti o kọja lẹsẹkẹsẹ ti o gbiyanju lati sọ asọtẹlẹ ọjọ iwaju. Ati pe o pe ni isinyi esi ipele pupọ.
orisun: www.habr.com