Cyflwyniad i Systemau Gweithredu
Hei Habr! Hoffwn dynnu eich sylw at gyfres o erthyglau-cyfieithiadau o un llenyddiaeth ddiddorol yn fy marn i - OSTEP. Mae'r deunydd hwn yn trafod yn eithaf dwfn waith systemau gweithredu tebyg i unix, sef, gwaith gyda phrosesau, amserlenwyr amrywiol, cof, a chydrannau tebyg eraill sy'n ffurfio OS modern. Gallwch weld y gwreiddiol o'r holl ddeunyddiau yma . Sylwch fod y cyfieithiad wedi'i wneud yn amhroffesiynol (yn eithaf rhydd), ond gobeithio i mi gadw'r ystyr cyffredinol.
Gellir dod o hyd i waith labordy ar y pwnc hwn yma:
Rhannau eraill:
Gallwch hefyd edrych ar fy sianel yn =)
Cyflwyniad i'r Trefnydd
Hanfod y broblem: Sut i ddatblygu polisi amserlennu
Sut y dylid cynllunio'r fframweithiau polisi amserlennu sylfaenol? Beth ddylai'r rhagdybiaethau allweddol fod? Pa fetrigau sy'n bwysig? Pa dechnegau sylfaenol a ddefnyddiwyd mewn systemau cyfrifiadurol cynnar?
Rhagdybiaethau Llwyth Gwaith
Cyn trafod polisïau posibl, gadewch i ni yn gyntaf wneud ychydig o wyriadau symleiddio ynghylch y prosesau sy'n rhedeg yn y system, a elwir gyda'i gilydd llwyth gwaith. Mae diffinio'r llwyth gwaith yn rhan hanfodol o bolisïau adeiladu, a pho fwyaf y gwyddoch am y llwyth gwaith, y gorau yw'r polisi y gallwch ei ysgrifennu.
Gadewch i ni wneud y rhagdybiaethau canlynol am y prosesau sy'n rhedeg yn y system, a elwir weithiau hefyd swyddi (tasgau). Nid yw bron pob un o'r rhagdybiaethau hyn yn realistig, ond maent yn angenrheidiol ar gyfer datblygu meddwl.
- Mae pob tasg yn rhedeg am yr un faint o amser,
- Gosodir pob tasg ar yr un pryd,
- Mae'r dasg a neilltuwyd yn gweithio tan ei chwblhau,
- Mae pob tasg yn defnyddio CPU yn unig,
- Mae amser rhedeg pob tasg yn hysbys.
Metrigau Trefnydd
Yn ogystal â rhai rhagdybiaethau am y llwyth, mae angen offeryn arall ar gyfer cymharu gwahanol bolisïau amserlennu: metrigau amserlennu. Dim ond rhyw fesur o rywbeth yw metrig. Mae nifer o fetrigau y gellir eu defnyddio i gymharu amserlenwyr.
Er enghraifft, byddwn yn defnyddio metrig o'r enw amser troi (amser troi). Diffinnir yr amser cyflawni tasgau fel y gwahaniaeth rhwng yr amser cwblhau tasg a'r amser cyrraedd tasg yn y system.
Tturnaround=Cwblhau−Tarrival
Gan ein bod yn tybio bod pob tasg yn cyrraedd yr un pryd, yna Ta=0 ac felly Tt=Tc. Bydd y gwerth hwn yn newid yn naturiol pan fyddwn yn newid y rhagdybiaethau uchod.
metrig arall - tegwch (tegwch, gonestrwydd). Mae cynhyrchiant a thegwch yn aml yn nodweddion gwrthgyferbyniol mewn cynllunio. Er enghraifft, efallai y bydd y trefnydd yn gwneud y gorau o berfformiad, ond ar gost aros i dasgau eraill redeg, gan leihau tegwch.
CYNTAF YN GYNTAF ALLAN (FIFO)
Yr algorithm mwyaf sylfaenol y gallwn ei weithredu yw FIFO neu cyntaf i'r felin (mewn), cyntaf i'r felin (allan). Mae gan yr algorithm hwn nifer o fanteision: mae'n hawdd iawn ei weithredu ac mae'n cyd-fynd â'n holl ragdybiaethau ac yn gwneud y gwaith yn eithaf da.
Gadewch i ni edrych ar enghraifft syml. Gadewch i ni ddweud bod 3 tasg wedi'u gosod ar yr un pryd. Ond gadewch i ni dybio bod tasg A wedi cyrraedd ychydig yn gynharach na'r lleill i gyd, felly bydd yn ymddangos yn y rhestr gyflawni yn gynharach na'r lleill, yn union fel B o'i gymharu â C. Gadewch i ni dybio y bydd pob un ohonynt yn cael ei gyflawni am 10 eiliad. Beth fydd yr amser cyfartalog i gwblhau'r tasgau hyn yn yr achos hwn?
Trwy gyfrif y gwerthoedd - 10 + 20 + 30 a rhannu â 3, rydyn ni'n cael amser gweithredu'r rhaglen gyfartalog sy'n hafal i 20 eiliad.
Nawr, gadewch i ni geisio newid ein rhagdybiaethau. Yn benodol, rhagdybiaeth 1 ac felly ni fyddwn yn cymryd yn ganiataol mwyach bod pob tasg yn cymryd yr un faint o amser i'w chyflawni. Sut bydd FIFO yn perfformio y tro hwn?
Fel mae'n digwydd, mae amseroedd cyflawni tasgau gwahanol yn cael effaith negyddol iawn ar gynhyrchiant algorithm FIFO. Gadewch i ni dybio y bydd tasg A yn cymryd 100 eiliad i'w chwblhau, tra bydd B ac C yn dal i gymryd 10 eiliad yr un.
Fel y gwelir o'r ffigwr, yr amser cyfartalog ar gyfer y system fydd (100+110+120)/3=110. Gelwir yr effaith hon effaith confoi, pan fydd rhai defnyddwyr tymor byr o adnodd yn ciwio ar ôl defnyddiwr trwm. Mae fel y llinell yn y siop groser pan mae cwsmer o'ch blaen gyda chert llawn. Yr ateb gorau i'r broblem yw ceisio newid y gofrestr arian parod neu ymlacio ac anadlu'n ddwfn.
Swydd Byrraf yn Gyntaf
A yw'n bosibl rhywsut datrys sefyllfa debyg gyda phrosesau pwysau trwm? Yn sicr. Gelwir math arall o gynllunioSwydd Byrraf yn Gyntaf (SJF). Mae ei algorithm hefyd yn eithaf cyntefig - fel y mae'r enw'n awgrymu, bydd y tasgau byrraf yn cael eu lansio yn gyntaf, un ar ôl y llall.
Yn yr enghraifft hon, bydd canlyniad rhedeg yr un prosesau yn welliant yn amser gweithredu cyfartalog y rhaglen a bydd yn hafal i 50 yn lle 110, sydd bron i 2 gwaith yn well.
Felly, ar gyfer y rhagdybiaeth a roddir bod yr holl dasgau'n cyrraedd yr un pryd, ymddengys mai'r algorithm SJF yw'r algorithm mwyaf optimaidd. Fodd bynnag, nid yw ein rhagdybiaethau yn ymddangos yn realistig o hyd. Y tro hwn rydym yn newid rhagdybiaeth 2 a'r tro hwn yn dychmygu y gall tasgau fod yn bresennol ar unrhyw adeg, ac nid i gyd ar yr un pryd. Pa broblemau all hyn arwain at?
Dychmygwn mai tasg A (100c) sy'n cyrraedd gyntaf ac yn dechrau cael ei chyflawni. Ar t=10, mae tasgau B ac C yn cyrraedd, a bydd pob un ohonynt yn cymryd 10 eiliad. Felly yr amser gweithredu ar gyfartaledd yw (100+(110-10)+(120-10))3 = 103. Beth allai'r trefnydd ei wneud i wella hyn?
Amser Byrraf i'w Gwblhau yn Gyntaf (STCF)
Er mwyn gwella'r sefyllfa, rydym yn hepgor rhagdybiaeth 3 bod y rhaglen yn cael ei lansio a'i bod yn rhedeg tan ei chwblhau. Yn ogystal, bydd angen cymorth caledwedd arnom ac, fel y gallech ddyfalu, byddwn yn ei ddefnyddio amserydd i dorri ar draws tasg rhedeg a newid cyd-destun. Felly, gall y trefnydd wneud rhywbeth ar hyn o bryd mae tasgau B, C yn cyrraedd - rhoi'r gorau i gyflawni tasg A a rhoi tasgau B ac C i'w prosesu ac, ar ôl eu cwblhau, parhau i weithredu'r broses A. Gelwir amserlennydd o'r fath STCFneu Rhagataliol Job yn Gyntaf.
Canlyniad y cynlluniwr hwn fydd y canlyniad canlynol: ((120-0)+(20-10)+(30-10))/3=50. Felly, mae trefnydd o'r fath yn dod yn fwy optimaidd fyth ar gyfer ein tasgau.
Amser Ymateb Metrig
Felly, os ydym yn gwybod amser rhedeg y tasgau a bod y tasgau hyn yn defnyddio CPU yn unig, STCF fydd yr ateb gorau. Ac unwaith yn y cyfnod cynnar, roedd yr algorithmau hyn yn gweithio'n eithaf da. Fodd bynnag, mae'r defnyddiwr bellach yn treulio'r rhan fwyaf o'i hamser yn y derfynell ac yn disgwyl profiad rhyngweithiol cynhyrchiol. Felly ganwyd metrig newydd - amser ymateb (ymateb).
Cyfrifir yr amser ymateb fel a ganlyn:
Tresponse=Tfirstrun−Tarrival
Felly, ar gyfer yr enghraifft flaenorol, yr amser ymateb fydd: A=0, B=0, C=10 (abg=3,33).
Ac mae'n ymddangos nad yw'r algorithm STCF mor dda mewn sefyllfa lle mae 3 tasg yn cyrraedd ar yr un pryd - bydd yn rhaid aros nes bod y tasgau bach wedi'u cwblhau'n llwyr. Felly mae'r algorithm yn dda ar gyfer y metrig amser gweithredu, ond yn ddrwg i'r metrig rhyngweithedd. Dychmygwch os oeddech chi'n eistedd wrth derfynell yn ceisio teipio cymeriadau i mewn i olygydd ac yn gorfod aros mwy na 10 eiliad oherwydd bod rhyw dasg arall yn cymryd y CPU. Nid yw'n ddymunol iawn.
Felly rydyn ni'n wynebu problem arall - sut allwn ni adeiladu rhaglennydd sy'n sensitif i amser ymateb?
Rownd Robin
Datblygwyd algorithm i ddatrys y broblem hon Rownd Robin (RR). Mae'r syniad sylfaenol yn eithaf syml: yn lle rhedeg tasgau nes eu bod wedi'u cwblhau, byddwn yn rhedeg y dasg am gyfnod penodol o amser (a elwir yn sleisen amser) ac yna'n newid i dasg arall o'r ciw. Mae'r algorithm yn ailadrodd ei waith nes bod yr holl dasgau wedi'u cwblhau. Yn yr achos hwn, rhaid i amser rhedeg y rhaglen fod yn lluosog o'r amser ac ar ôl hynny bydd yr amserydd yn torri ar draws y broses. Er enghraifft, os yw amserydd yn torri ar draws proses bob x=10ms, yna dylai maint y ffenestr gweithredu proses fod yn lluosrif o 10 a bod yn 10,20 neu x*10.
Edrychwn ar enghraifft: mae tasgau ABC yn cyrraedd y system ar yr un pryd ac mae pob un ohonynt eisiau rhedeg am 5 eiliad. Bydd yr algorithm SJF yn cwblhau pob tasg cyn dechrau un arall. Mewn cyferbyniad, bydd yr algorithm RR gyda ffenestr lansio = 1s yn mynd trwy'r tasgau fel a ganlyn (Ffig. 4.3):
(SJF Eto (Drwg am Amser Ymateb)
(Rownd Robin (Da ar gyfer Amser Ymateb)
Yr amser ymateb cyfartalog ar gyfer yr algorithm RR yw (0+1+2)/3=1, tra ar gyfer yr SJF (0+5+10)/3=5.
Mae'n rhesymegol tybio bod y ffenestr amser yn baramedr pwysig iawn ar gyfer RR; po leiaf ydyw, yr uchaf yw'r amser ymateb. Fodd bynnag, ni ddylech ei wneud yn rhy fach, gan y bydd amser newid cyd-destun hefyd yn chwarae rhan mewn perfformiad cyffredinol. Felly, pensaer yr AO sy'n pennu'r dewis o amser y ffenestr weithredu ac mae'n dibynnu ar y tasgau y bwriedir eu cyflawni ynddo. Nid newid cyd-destun yw'r unig weithrediad gwasanaeth sy'n gwastraffu amser - mae'r rhaglen redeg yn gweithredu ar lawer o bethau eraill, er enghraifft, caches amrywiol, a gyda phob switsh mae angen arbed ac adfer yr amgylchedd hwn, a all hefyd gymryd llawer o amser.
Mae RR yn amserlennwr gwych pe baem yn siarad am y metrig amser ymateb yn unig. Ond sut bydd y metrig amser cwblhau tasgau yn ymddwyn gyda'r algorithm hwn? Ystyriwch yr enghraifft uchod, pan fydd amser gweithredu A, B, C = 5s a chyrraedd ar yr un pryd. Bydd Tasg A yn gorffen am 13, B am 14, C am 15s a'r amser gweithredu cyfartalog fydd 14s. Felly, RR yw'r algorithm gwaethaf ar gyfer y metrig trosiant.
Mewn termau mwy cyffredinol, mae unrhyw algorithm math RR yn deg; mae'n rhannu'r amser CPU yn gyfartal rhwng yr holl brosesau. Ac felly, mae'r metrigau hyn yn gwrthdaro'n gyson â'i gilydd.
Felly, mae gennym nifer o algorithmau cyferbyniol ac ar yr un pryd mae yna nifer o ragdybiaethau ar ôl o hyd - bod amser y dasg yn hysbys a bod y dasg yn defnyddio'r CPU yn unig.
Cymysgu ag I/O
Yn gyntaf oll, gadewch i ni ddileu rhagdybiaeth 4 mai dim ond y CPU y mae'r broses yn ei ddefnyddio; yn naturiol, nid yw hyn yn wir a gall prosesau gael mynediad at offer arall.
Yr eiliad y bydd unrhyw broses yn gofyn am weithrediad I / O, mae'r broses yn mynd i mewn i'r cyflwr blocio, gan aros i'r I / O ei gwblhau. Os anfonir I/O i'r gyriant caled, yna gall gweithrediad o'r fath gymryd hyd at sawl ms neu fwy, a bydd y prosesydd yn segur ar hyn o bryd. Yn ystod yr amser hwn, gall y trefnydd feddiannu'r prosesydd gydag unrhyw broses arall. Y penderfyniad nesaf y bydd yn rhaid i'r trefnydd ei wneud yw pryd y bydd y broses yn cwblhau ei I/O. Pan fydd hyn yn digwydd, bydd ymyriad yn digwydd a bydd yr OS yn rhoi'r broses a alwodd yr I / O yn y cyflwr parod.
Gadewch i ni edrych ar enghraifft o nifer o dasgau. Mae angen 50ms o amser CPU ar bob un ohonynt. Fodd bynnag, bydd yr un cyntaf yn cyrchu I/O bob 10ms (a fydd hefyd yn cael ei weithredu bob 10ms). Ac mae proses B yn syml yn defnyddio prosesydd 50ms heb I/O.
Yn yr enghraifft hon byddwn yn defnyddio'r rhaglennydd STCF. Sut bydd y trefnydd yn ymddwyn os bydd proses fel A yn cael ei lansio arni? Bydd yn gwneud y canlynol: yn gyntaf bydd yn gweithio proses A allan yn gyfan gwbl, ac yna'n prosesu B.
Y dull traddodiadol o ddatrys y broblem hon yw trin pob is-dasg 10 ms o broses A fel tasg ar wahân. Felly, wrth ddechrau gyda'r algorithm STJF, mae'r dewis rhwng tasg 50 ms a thasg 10 ms yn amlwg. Yna, pan fydd is-dasg A wedi'i gwblhau, bydd proses B ac I/O yn cael eu lansio. Ar ôl i'r I/O ddod i ben, bydd yn arferol dechrau proses 10ms A eto yn lle proses B. Yn y modd hwn, mae'n bosibl gweithredu gorgyffwrdd, lle mae'r CPU yn cael ei ddefnyddio gan broses arall tra bod yr un cyntaf yn aros am y I/O. Ac o ganlyniad, mae'r system yn cael ei defnyddio'n well - ar hyn o bryd pan fo prosesau rhyngweithiol yn aros am I / O, gellir gweithredu prosesau eraill ar y prosesydd.
Nid yw'r Oracle mwyach
Nawr, gadewch i ni geisio cael gwared ar y rhagdybiaeth bod amser rhedeg y dasg yn hysbys. Yn gyffredinol, dyma'r rhagdybiaeth waethaf a mwyaf afrealistig ar y rhestr gyfan. Mewn gwirionedd, yn yr AO cyffredin cyffredin, ychydig iawn y mae'r OS ei hun yn ei wybod fel arfer am amser cyflawni tasgau, felly sut felly allwch chi adeiladu trefnydd heb wybod pa mor hir y bydd y dasg yn ei gymryd i'w chyflawni? Efallai y gallem ddefnyddio rhai egwyddorion AP i ddatrys y broblem hon?
Cyfanswm
Gwnaethom edrych ar y syniadau sylfaenol o amserlennu tasgau ac edrych ar 2 deulu o amserlenwyr. Mae'r cyntaf yn dechrau'r dasg fyrraf yn gyntaf ac felly'n cynyddu'r amser troi, tra bod yr ail yn cael ei rwygo rhwng pob tasg yn gyfartal, gan gynyddu'r amser ymateb. Mae'r ddau algorithm yn ddrwg lle mae algorithmau'r teulu arall yn dda. Buom hefyd yn edrych ar sut y gall defnydd cyfochrog o CPU ac I/O wella perfformiad, ond ni wnaethom ddatrys y broblem gyda chlirwelediad OS. Ac yn y wers nesaf byddwn yn edrych ar gynlluniwr sy'n edrych i mewn i'r gorffennol agos ac yn ceisio rhagweld y dyfodol. Ac fe'i gelwir yn giw adborth aml-lefel.
Ffynhonnell: hab.com