Ro-ràdh gu siostaman-obrachaidh
Hi Habr! Bu mhath leam sreath de artaigilean a thoirt nad aire - eadar-theangachadh de aon litreachas inntinneach nam bheachd-sa - OSTEP. Tha an stuth seo a’ beachdachadh gu domhainn air obair shiostaman obrachaidh coltach ri unix, is e sin, obair le pròiseasan, diofar chlàran, cuimhne, agus co-phàirtean eile den aon seòrsa a tha a’ dèanamh suas OS ùr-nodha. Chì thu an stuth tùsail uile an seo . Thoir an aire gun deach an eadar-theangachadh a dhèanamh gu neo-phroifeasanta (gu math saor), ach tha mi an dòchas gun do ghlèidh mi am brìgh coitcheann.
Gheibhear obair-lann air a’ chuspair seo an seo:
Pàirtean eile:
Faodaidh tu cuideachd sùil a thoirt air an t-sianal agam aig =)
Ro-ràdh don Scheduler
Tha brìgh na trioblaid: Mar a leasaicheas tu poileasaidh clàr-ama
Ciamar a bu chòir na frèaman poileasaidh clàr-ama bunaiteach a dhealbhadh? Dè na prìomh bhun-bheachdan a bu chòir a bhith ann? Dè na slatan-tomhais a tha cudromach? Dè na dòighean bunaiteach a chaidh a chleachdadh ann an siostaman coimpiutaireachd tràth?
Bun-bheachd uallach obrach
Mus bruidhinn sinn mu phoileasaidhean a dh’ fhaodadh a bhith ann, dèanamaid an-toiseach beagan adhartasan nas sìmplidhe mu na pròiseasan a tha a’ ruith san t-siostam, ris an canar còmhla eallach obrach. Tha a bhith a’ mìneachadh an eallach obrach na phàirt dheatamach de phoileasaidhean togail, agus mar as motha a bhios fios agad mun eallach obrach, ’s ann as fheàrr am poileasaidh as urrainn dhut a sgrìobhadh.
Dèanamaid na barailean a leanas mu na pròiseasan a tha a 'ruith san t-siostam, ris an canar uaireannan cuideachd obraichean (tasdan). Cha mhòr nach eil na barailean sin uile fìor, ach tha iad riatanach airson leasachadh smaoineachaidh.
- Bidh gach gnìomh a’ ruith airson an aon ùine,
- Tha na gnìomhan uile air an suidheachadh aig an aon àm,
- Bidh an obair ainmichte ag obair gus an tèid a chrìochnachadh,
- Chan eil a h-uile gnìomh a’ cleachdadh ach CPU,
- Tha fios air àm ruith gach gnìomh.
Metrics Clàr-ama
A bharrachd air cuid de bharailean mun luchd, tha feum air inneal eile airson coimeas a dhèanamh eadar diofar phoileasaidhean clàraidh: metrics clàr-ama. Chan eil ann an meatrach ach tomhas de rudeigin. Tha grunn mheatairean ann a dh'fhaodar a chleachdadh gus coimeas a dhèanamh eadar clàran-ama.
Mar eisimpleir, cleachdaidh sinn meatrach ris an canar àm tionndaidh (ùine tionndaidh). Tha an ùine tionndaidh gnìomh air a mhìneachadh mar an eadar-dhealachadh eadar an ùine crìochnachaidh gnìomh agus an ùine ruighinn gnìomh san t-siostam.
Tturnaround=Crìochnachadh - Tarruing
Leis gun do ghabh sinn ris gun do ràinig a h-uile gnìomh aig an aon àm, an uairsin Ta = 0 agus mar sin Tt = Tc. Bidh an luach seo ag atharrachadh gu nàdarra nuair a dh'atharraicheas sinn na barailean gu h-àrd.
Slat-tomhais eile - cothromachd (cothromachd, onair). Tha cinneasachd agus cothromachd gu tric an aghaidh feartan ann am planadh. Mar eisimpleir, faodaidh an clàr-ama coileanadh a bharrachadh, ach aig cosgais feitheamh ri gnìomhan eile a ruith, agus mar sin a’ lughdachadh cothromachd.
A' CHIAD ANN AN CIAD A-MHÀIN (FIFO)
Is e FIFO no an algorithm as bunaitiche as urrainn dhuinn a chuir an gnìomh thig an toiseach (a-steach), an toiseach seirbheis (a-mach). Tha grunn bhuannachdan aig an algairim seo: tha e gu math furasta a bhuileachadh agus bidh e a’ freagairt air na barailean againn uile agus a’ dèanamh an obair gu math.
Bheir sinn sùil air eisimpleir shìmplidh. Canaidh sinn gun deach 3 gnìomhan a shuidheachadh aig an aon àm. Ach gabhamaid ris gun do ràinig gnìomh A beagan nas tràithe na càch, agus mar sin nochdaidh e air an liosta cur gu bàs nas tràithe na an fheadhainn eile, dìreach mar B an coimeas ri C. Gabhamaid ris gun tèid gach fear dhiubh a chuir gu bàs airson 10 diogan. Dè an ùine chuibheasach a bhios ann airson na gnìomhan sin a choileanadh sa chùis seo?
Le bhith a 'cunntadh nan luachan - 10 + 20 + 30 agus a' roinneadh le 3, gheibh sinn ùine cur gu bàs cuibheasach a 'phrògraim co-ionann ri 20 diogan.
A-nis feuchaidh sinn ri ar barailean atharrachadh. Gu sònraichte, barail 1 agus mar sin cha bhith sinn a’ gabhail ris tuilleadh gu bheil gach gnìomh a’ toirt an aon ùine ri chur an gnìomh. Ciamar a choileanas FIFO an turas seo?
Mar a thionndaidh e, tha diofar amannan gnìomh gnìomh a ’toirt droch bhuaidh air cinneasachd algairim FIFO. Gabhamaid ris gun toir gnìomh A 100 diog airson a chrìochnachadh, agus bheir B agus C fhathast 10 diogan an urra.
Mar a chithear bhon fhigear, bidh an ùine chuibheasach airson an t-siostam (100+110+120)/3=110. Canar a’ bhuaidh seo ris buaidh convoy, nuair a bhios cuid de luchd-cleachdaidh geàrr-ùine de ghoireas a’ ciudha às deidh neach-cleachdaidh trom. Tha e coltach ris an loidhne aig a’ bhùth ghrosaireachd nuair a tha neach-ceannach air do bheulaibh le cairt làn. Is e am fuasgladh as fheàrr air an duilgheadas a bhith a 'feuchainn ris a' chlàr airgid atharrachadh no fois a ghabhail agus anail a tharraing gu domhainn.
An obair as giorra an toiseach
A bheil e comasach dòigh air choireigin fuasgladh fhaighinn air suidheachadh coltach ri pròiseasan cuideam trom? Gu cinnteach. Canar seòrsa eile de phlanadh risAn obair as giorra an toiseach (SJF). Tha an algairim aige cuideachd gu math prìomhadail - mar a tha an t-ainm a’ ciallachadh, thèid na gnìomhan as giorra a chuir air bhog an toiseach, aon às deidh a chèile.
Anns an eisimpleir seo, bidh toradh a bhith a’ ruith nan aon phròiseasan na leasachadh ann an ùine chuibheasach a’ phrògraim agus bidh e co-ionann ri 50 an àite 110, a tha faisg air 2 uair nas fheàrr.
Mar sin, airson a’ bharail a chaidh a thoirt seachad gun ruig a h-uile gnìomh aig an aon àm, tha e coltach gur e an algairim SJF an algairim as fheàrr. Ach, chan eil coltas reusanta air na barailean againn fhathast. An turas seo bidh sinn ag atharrachadh barail 2 agus an turas seo smaoinich gum faod gnìomhan a bhith an làthair aig àm sam bith, agus chan ann aig an aon àm. Dè na duilgheadasan a dh’ fhaodadh seo leantainn?
Smaoinicheamaid gu bheil gnìomh A (100c) a’ tighinn an toiseach agus a’ tòiseachadh air a cur gu bàs. Aig t = 10, ruigidh gnìomhan B agus C, agus bheir gach fear dhiubh 10 diogan. Mar sin 's e an ùine cur gu bàs cuibheasach (100+(110-10)+(120-10))3 = 103. Dè dh'fhaodadh an neach-clàraidh a dhèanamh gus an suidheachadh a leasachadh?
An ùine as giorra airson a chrìochnachadh an toiseach (STCF)
Gus an suidheachadh a leasachadh, tha sinn a’ fàgail a-mach barail 3 gun tèid am prògram a chuir air bhog agus gun ruith e gus an tèid a chrìochnachadh. A bharrachd air an sin, bidh feum againn air taic bathar-cruaidh agus, mar a shaoileadh tu, cleachdaidh sinn timer stad a chur air obair ruith agus tionndadh co-theacsa. Mar sin, faodaidh an neach-clàraidh rudeigin a dhèanamh an-dràsta tha gnìomhan B, C a’ ruighinn - stad air coileanadh gnìomh A agus gnìomhan B agus C a chuir an sàs agus, às deidh an crìochnachadh, leantainn air adhart leis a’ phròiseas A. Canar clàr-ama mar sin ris STCFno Iob Preemptive An toiseach.
Is e toradh a’ phlanair seo an toradh a leanas: ((120-0)+(20-10)+(30-10))/3=50. Mar sin, bidh an leithid de chlàr-ama a’ fàs eadhon nas fheàrr airson ar gnìomhan.
Ùine Freagairt Metric
Mar sin, ma tha fios againn air àm ruith nan gnìomhan agus nach bi na gnìomhan sin a’ cleachdadh ach CPU, is e STCF am fuasgladh as fheàrr. Agus aon uair anns na h-amannan tràtha, dh'obraich na h-algorithms sin gu math. Ach, bidh an neach-cleachdaidh a-nis a’ caitheamh a’ mhòr-chuid den ùine aice aig a’ phort-adhair agus an dùil ri eòlas eadar-ghnìomhach buannachdail. Mar sin rugadh meatrach ùr - ùine freagairt (freagairt).
Tha an ùine freagairt air a thomhas mar a leanas:
Tresponse=Tfirstrun−Tarraing
Mar sin, airson an eisimpleir roimhe, is e an ùine freagairt: A = 0, B = 0, C = 10 (abg = 3,33).
Agus tha e a 'tionndadh a-mach nach eil an algairim STCF cho math ann an suidheachadh far an ruig 3 gnìomhan aig an aon àm - feumaidh e feitheamh gus an tèid na gnìomhan beaga a chrìochnachadh gu tur. Mar sin tha an algairim math airson a’ mheatrach ùine tionndaidh, ach dona airson a’ mheatrach eadar-ghnìomhachd. Smaoinich nam biodh tu nad shuidhe aig ceann-uidhe a’ feuchainn ri caractaran a thaipeadh a-steach do neach-deasachaidh agus gum feumadh tu feitheamh barrachd air 10 diogan oir bha gnìomh eile a’ gabhail an CPU. Chan eil e glè thaitneach.
Mar sin tha duilgheadas eile romhainn - ciamar as urrainn dhuinn clàr-ama a thogail a tha mothachail air ùine freagairt?
Cruinn Robin
Chaidh algorithm a leasachadh gus an duilgheadas seo fhuasgladh Cruinn Robin (RR). Tha am beachd bunaiteach gu math sìmplidh: an àite a bhith a 'ruith ghnìomhan gus an tèid an crìochnachadh, bidh sinn a' ruith a 'ghnìomh airson ùine sònraichte (ris an canar slice ùine) agus an uairsin gluaisidh sinn gu gnìomh eile bhon ciudha. Bidh an algairim ag ath-aithris a chuid obrach gus an tèid a h-uile gnìomh a chrìochnachadh. Anns a 'chùis seo, feumaidh ùine ruith a' phrògraim a bhith na iomadachadh den ùine às deidh sin cuiridh an timer stad air a 'phròiseas. Mar eisimpleir, ma chuireas timer stad air pròiseas a h-uile x = 10ms, bu chòir meud na h-uinneige coileanadh pròiseas a bhith iomadaidh de 10 agus a bhith 10,20 no x * 10.
Bheir sinn sùil air eisimpleir: bidh gnìomhan ABC a’ ruighinn aig an aon àm san t-siostam agus tha gach fear dhiubh airson ruith airson 5 diogan. Cuiridh an algairim SJF crìoch air gach gnìomh gu crìoch mus tòisich e air fear eile. An coimeas ri sin, thèid an algairim RR le uinneag tòiseachaidh = 1s tro na gnìomhan mar a leanas (Fig. 4.3):
(SJF A-rithist (Droch airson Àm Freagairt)
(Round Robin (Math airson ùine freagairt)
Is e an ùine freagairt cuibheasach airson an algairim RR (0+1+2)/3=1, agus airson an SJF (0+5+10)/3=5.
Tha e loidsigeach a bhith den bheachd gu bheil an uinneag ùine na paramadair fìor chudromach airson RR; mar as lugha a tha e, is ann as àirde an ùine freagairt. Ach, cha bu chòir dhut a dhèanamh ro bheag, oir bidh pàirt aig àm atharrachadh co-theacsa ann an coileanadh iomlan cuideachd. Mar sin, tha an roghainn ùine uinneag cur gu bàs air a shuidheachadh le ailtire an OS agus bidh e an urra ris na gnìomhan a thathar an dùil a chuir gu bàs ann. Chan e atharrachadh co-theacsa an aon obair seirbheis a bhios a’ caitheamh ùine - bidh am prògram ruith ag obair air tòrr rudan eile, mar eisimpleir, diofar caches, agus le gach suidse feumar an àrainneachd seo a shàbhaladh agus ath-nuadhachadh, a dh’ fhaodadh tòrr a ghabhail cuideachd. uair.
Tha RR na dheagh chlàr-ama mura robh sinn a’ bruidhinn ach mu dheidhinn tomhas ùine freagairt. Ach ciamar a bhios meatrach ùine tionndaidh gnìomh gad ghiùlan fhèin leis an algairim seo? Beachdaich air an eisimpleir gu h-àrd, nuair a tha an ùine-obrachaidh A, B, C = 5s agus ruighinn aig an aon àm. Thig Gnìomh A gu crìch aig 13, B aig 14, C aig 15sg agus bidh an ùine tionndaidh cuibheasach 14sg. Mar sin, is e RR an algairim as miosa airson a’ mheatrach tionndaidh.
Ann an teirmean nas fharsainge, tha algairim seòrsa RR sam bith cothromach; bidh e a’ roinn ùine CPU gu cothromach eadar a h-uile pròiseas. Agus mar sin, tha na slatan-tomhais sin daonnan a 'strì ri chèile.
Mar sin, tha grunn algorithms eadar-dhealaichte againn agus aig an aon àm tha grunn bharailean air fhàgail - gu bheil fios air an ùine gnìomh agus nach eil an gnìomh a’ cleachdadh ach an CPU.
A 'measgachadh le I/O
An toiseach, bheir sinn air falbh barail 4 nach bi am pròiseas a’ cleachdadh ach an CPU; gu nàdarra, chan eil seo fìor agus faodaidh pròiseasan faighinn gu uidheamachd eile.
Cho luath ‘s a dh’ iarras pròiseas sam bith gnìomhachd I / O, thig am pròiseas a-steach don staid dùinte, a ’feitheamh ris an I / O a chrìochnachadh. Ma thèid I/O a chuir chun chlàr cruaidh, faodaidh an leithid de dh’ obair suas ri grunn ms no nas fhaide a thoirt, agus bidh am pròiseasar leisg aig an àm seo. Rè na h-ùine seo, faodaidh an clàr-ama am pròiseasar a ghabhail thairis le pròiseas sam bith eile. Is e an ath cho-dhùnadh a dh’ fheumas an neach-clàraidh a dhèanamh nuair a chuireas am pròiseas crìoch air an I/O aige. Nuair a thachras seo, bidh briseadh ann agus cuiridh an OS am pròiseas ris an canar an I / O anns an staid deiseil.
Bheir sinn sùil air eisimpleir de ghrunn dhuilgheadasan. Feumaidh gach fear dhiubh 50ms de ùine CPU. Ach, gheibh a’ chiad fhear cothrom air I/O gach 10ms (a thèid a chur gu bàs cuideachd gach 10ms). Agus tha pròiseas B dìreach a’ cleachdadh pròiseasar 50ms às aonais I/O.
San eisimpleir seo cleachdaidh sinn clàr-ama STCF. Ciamar a bhios an neach-clàraidh gad ghiùlan fhèin ma thèid pròiseas mar A a chuir air bhog air? Nì e na leanas: an toiseach obraichidh e a-mach pròiseas A gu tur, agus an uairsin pròiseas B.
Is e an dòigh thraidiseanta airson an duilgheadas seo fhuasgladh a bhith a’ làimhseachadh gach fo-ghnìomh 10 ms de phròiseas A mar ghnìomh air leth. Mar sin, nuair a thòisicheas tu leis an algairim STJF, tha an roghainn eadar gnìomh 50 ms agus gnìomh 10 ms follaiseach. An uairsin, nuair a bhios fo-obair A deiseil, thèid pròiseas B agus I/O a chuir air bhog. Às deidh an I/O a chrìochnachadh, bidh e àbhaisteach tòiseachadh air pròiseas 10ms A a-rithist an àite pròiseas B. San dòigh seo, tha e comasach tar-tharraing a chuir an gnìomh, far a bheil an CPU air a chleachdadh le pròiseas eile fhad ‘s a tha a’ chiad fhear a ’feitheamh ris an Tha mi/o. Agus mar thoradh air an sin, tha an siostam air a chleachdadh nas fheàrr - an-dràsta nuair a tha pròiseasan eadar-ghnìomhach a 'feitheamh ri I / O, faodar pròiseasan eile a chuir gu bàs air a' phròiseasar.
Chan eil an Oracle tuilleadh
A-nis feuchaidh sinn ri cuidhteas fhaighinn den bharail gu bheil fios aig àm ruith na h-obrach. Is e seo sa chumantas am beachd as miosa agus as neo-phractaigeach air an liosta gu lèir. Gu dearbh, anns an OS àbhaisteach àbhaisteach, mar as trice chan eil mòran fios aig an OS fhèin mu àm cur an gnìomh nan gnìomhan, agus mar sin ciamar as urrainn dhut clàr-ama a thogail gun fhios dè cho fada ‘s a bheir e an obair a choileanadh? Is dòcha gum b’ urrainn dhuinn cuid de phrionnsapalan RR a chleachdadh gus an duilgheadas seo fhuasgladh?
An toradh
Choimhead sinn air na beachdan bunaiteach mu bhith a’ clàradh ghnìomhan agus choimhead sinn air 2 theaghlach de luchd-clàraidh. Bidh a 'chiad fhear a' tòiseachadh a 'ghnìomh as giorra an toiseach agus mar sin a' meudachadh an ùine tionndaidh, agus tha an dàrna fear air a reubadh eadar a h-uile gnìomh gu cothromach, a 'meudachadh na h-ùine freagairt. Tha an dà algorithm dona far a bheil algorithms an teaghlaich eile math. Choimhead sinn cuideachd air mar as urrainn cleachdadh co-shìnte de CPU agus I / O coileanadh a leasachadh, ach cha do dh ’fhuasgail sinn an duilgheadas le clairvoyance OS. Agus anns an ath leasan seallaidh sinn ri dealbhaiche a bhios a’ coimhead ris an àm a dh’ fhalbh agus a’ feuchainn ri ro-innse mun àm ri teachd. Agus canar ciudha fios-air-ais ioma-ìre ris.
Source: www.habr.com