Entwodiksyon nan sistèm operasyon yo
Bonjou, Habr! Mwen ta renmen prezante nan atansyon w yon seri atik-tradiksyon yon sèl literati ki enteresan nan opinyon mwen - OSTEP. Materyèl sa a egzamine byen pwofondman travay sistèm operasyon UNIX, sètadi travay ak pwosesis, pwogramasyon divès kalite, memwa ak lòt konpozan ki sanble ak yon sistèm eksplwatasyon modèn. Ou ka wè orijinal la nan tout materyèl isit la . Tanpri sonje ke tradiksyon an te fèt san pwofesyonèl (byen lib), men mwen espere ke mwen te kenbe siyifikasyon jeneral la.
Ou ka jwenn travay laboratwa sou sijè sa a isit la:
Lòt pati:
Ou ka tcheke tou chèn mwen an nan =)
Entwodiksyon nan Scheduler
Sans nan pwoblèm nan: Ki jan yo devlope yon politik orè
Ki jan yo ta dwe fèt kad politik orè ki kache yo? Ki sa ki ta dwe sipozisyon kle yo? Ki mezi ki enpòtan? Ki teknik debaz yo te itilize nan premye sistèm enfòmatik?
Sipozisyon chaj travay
Anvan nou diskite sou politik posib, ann premye fè kèk digressions senplifye sou pwosesis yo ap kouri nan sistèm nan, ki kolektivman rele kantite travay. Defini kantite travay la se yon pati enpòtan nan règleman bilding yo, epi plis ou konnen sou kantite travay la, se pi bon politik ou ka ekri.
Ann fè sipozisyon sa yo sou pwosesis yo kouri nan sistèm nan, pafwa yo rele tou Travay (travay). Prèske tout sipozisyon sa yo pa reyalis, men yo nesesè pou devlopman panse.
- Chak travay kouri pou menm kantite tan,
- Tout travay yo mete ansanm,
- Travay ki asiyen an ap travay jiskaske li fini,
- Tout travay itilize sèlman CPU,
- Tan an kouri nan chak travay li te ye.
Metris Scheduler
Anplis de kèk sipozisyon sou chaj la, yo bezwen yon lòt zouti pou konpare diferan politik orè: mezi orè. Yon metrik se jis kèk mezi yon bagay. Gen yon kantite mezi ki ka itilize pou konpare pwogramè yo.
Pou egzanp, nou pral itilize yon metrik ki rele tan rotation (tan rediksyon). Tan pou travay la defini kòm diferans ki genyen ant tan fini travay la ak tan arive travay nan sistèm nan.
Tturnaround=Tkonpletman−Arive
Depi nou sipoze ke tout travay yo te rive an menm tan an, Lè sa a, Ta = 0 e konsa Tt = Tc. Valè sa a pral natirèlman chanje lè nou chanje sipozisyon ki anwo yo.
Yon lòt metrik - etidye ekite Règleman (ekite, onètete). Pwodiktivite ak jistis yo souvan karakteristik opoze nan planifikasyon. Pou egzanp, orè a ka optimize pèfòmans, men nan pri a nan ap tann pou lòt travay yo kouri, kidonk diminye jistis.
PREMYE AN PREMYE SOTI (FIFO)
Algorithm ki pi fondamantal ke nou ka aplike yo rele FIFO oswa premye vini (antre), premye sèvi (soti). Algorithm sa a gen plizyè avantaj: li trè fasil pou aplike epi li adapte tout sipozisyon nou yo epi li fè travay la byen.
Ann gade yon egzanp senp. Ann di 3 travay yo te mete ansanm. Men, an n sipoze ke travay A te rive yon ti kras pi bonè pase tout lòt yo, kidonk li pral parèt nan lis ekzekisyon an pi bonè pase lòt yo, jis tankou B relatif a C. Ann sipoze ke chak nan yo pral egzekite pou 10 segonn. Ki tan an mwayèn pral konplete travay sa yo nan ka sa a?
Lè nou konte valè yo - 10 + 20 + 30 epi divize pa 3, nou jwenn tan an mwayèn ekzekisyon pwogram egal a 20 segonn.
Koulye a, ann eseye chanje sipozisyon nou yo. An patikilye, sipozisyon 1 e konsa nou p ap sipoze ke chak travay pran menm kantite tan pou egzekite. Ki jan FIFO pral fè tan sa a?
Kòm li vire soti, diferan tan ekzekisyon travay gen yon enpak trè negatif sou pwodiktivite nan algorithm la FIFO. Ann sipoze ke travay A pral pran 100 segonn pou konplete, pandan ke B ak C ap toujou pran 10 segonn chak.
Kòm ou ka wè nan figi a, tan an mwayèn pou sistèm nan pral (100 + 110 + 120) / 3 = 110. Efè sa a rele efè konvwa, lè kèk konsomatè kout tèm nan yon resous ap keu apre yon konsomatè lou. Se tankou liy lan nan makèt la lè gen yon kliyan devan ou ak yon charyo plen. Pi bon solisyon a pwoblèm nan se eseye chanje kach anrejistre a oswa detann epi respire pwofondman.
Travay ki pi kout an premye
Èske li posib yon jan kanmenm rezoud yon sitiyasyon ki sanble ak pwosesis pwa lou? Sètènman. Yo rele yon lòt kalite planifikasyonTravay ki pi kout an premye (SJF). Algorithm li yo tou se byen primitif - jan non an implique, travay ki pi kout yo pral lanse an premye, youn apre lòt.
Nan egzanp sa a, rezilta a nan kouri menm pwosesis yo pral yon amelyorasyon nan tan an mwayèn pwogram epi li pral egal a 50 olye pou yo 110, ki se prèske 2 fwa pi bon.
Kidonk, pou sipozisyon yo bay ke tout travay yo rive an menm tan an, algorithm SJF a sanble se algorithm ki pi optimal. Sepandan, sipozisyon nou yo toujou pa sanble reyalis. Fwa sa a, nou chanje sipozisyon 2 ak tan sa a imajine ke travay yo ka prezan nan nenpòt ki lè, epi yo pa tout an menm tan an. Ki pwoblèm sa ka mennen?
Ann imajine ke travay A (100c) rive an premye epi li kòmanse egzekite. Nan t=10, travay B ak C rive, chak nan yo pral pran 10 segonn. Se konsa, tan an mwayèn ekzekisyon se (100+(110-10)+(120-10))3 = 103. Kisa pwogramè a ta ka fè pou amelyore sa a?
Pi kout tan pou konplete premye (STCF)
Pou amelyore sitiyasyon an, nou omite sipozisyon 3 ke pwogram nan te lanse epi kouri jiskaske fini. Anplis de sa, nou pral bezwen sipò pyès ki nan konpitè epi, jan ou ta ka devine, nou pral itilize revèy pou entèwonp yon travay kouri ak chanjman kontèks. Kidonk, pwogramè a ka fè yon bagay nan moman travay B, C rive - sispann egzekite travay A epi mete travay B ak C nan pwosesis epi, apre yo fin fini, kontinye egzekite pwosesis A. Yo rele yon pwogramasyon konsa. STCFoswa Travay Prevantif Premye.
Rezilta planifikatè sa a pral rezilta sa a: ((120-0)+(20-10)+(30-10))/3=50. Kidonk, yon pwogramasyon konsa vin pi pi bon pou travay nou yo.
Tan repons metrik
Kidonk, si nou konnen tan an fonksyone nan travay yo e ke travay sa yo sèlman itilize CPU, STCF pral pi bon solisyon an. Ak yon fwa nan tan yo byen bonè, algoritm sa yo te travay byen byen. Sepandan, itilizatè a kounye a pase pi fò nan tan li nan tèminal la epi li espere yon eksperyans pwodiktif entèaktif. Se konsa yon nouvo metrik te fèt - tan repons (repons).
Tan repons lan kalkile jan sa a:
Tresponse=Tfirstrun−Tarrival
Kidonk, pou egzanp anvan an, tan repons lan pral: A=0, B=0, C=10 (abg=3,33).
E i vwar ki sa algorithm STCF pa si bon dan en sitiasyon kot 3 travay i arive anmenmtan – i pou bezwen tann ziska ki bann pti travay i ganny konplete. Se konsa, algorithm la se yon bon bagay pou metrik nan tan rotation, men move pou metrik la entèaktif. Imajine si ou te chita nan yon tèminal ap eseye tape karaktè nan yon editè epi ou oblije rete tann plis pase 10 segonn paske kèk lòt travay t ap pran CPU a. Li pa trè plezan.
Se konsa, nou ap fè fas ak yon lòt pwoblèm - ki jan nou ka bati yon pwogramasyon ki sansib a tan repons?
Round Robin
Yo te devlope yon algorithm pou rezoud pwoblèm sa a Round Robin (RR). Lide debaz la se byen senp: olye pou yo kouri travay jiskaske yo fini, nou pral kouri travay la pou yon sèten peryòd tan (yo rele yon tranch tan) ak Lè sa a, chanje nan yon lòt travay nan keu la. Algorithm la repete travay li jiskaske tout travay yo fini. Nan ka sa a, tan an kouri nan pwogram nan dwe yon miltip nan tan an apre ki revèy la pral entèwonp pwosesis la. Pou egzanp, si yon revèy entèwonp yon pwosesis chak x = 10ms, Lè sa a, gwosè a nan fenèt ekzekisyon pwosesis la ta dwe yon miltip nan 10 epi yo dwe 10,20 oswa x * 10.
Ann gade yon egzanp: travay ABC rive an menm tan nan sistèm nan epi chak nan yo vle kouri pou 5 segonn. Algorithm SJF a pral konplete chak travay anvan yo kòmanse yon lòt. Kontrèman, algorithm RR a ak yon fenèt lansman = 1s pral ale nan travay yo jan sa a (Fig. 4.3):
(SJF ankò (Move pou tan repons)
(Round Robin (bon pou tan repons)
Tan an mwayèn repons pou algorithm RR a se (0 + 1 + 2) / 3 = 1, pandan y ap pou SJF a (0 + 5 + 10) / 3 = 5.
Li lojik pou asime ke fenèt tan an se yon paramèt trè enpòtan pou RR; pi piti li se, se pi gwo tan an repons. Sepandan, ou pa ta dwe fè li twò piti, depi lè chanjman kontèks pral jwe tou yon wòl nan pèfòmans jeneral. Kidonk, chwa nan tan fenèt ekzekisyon fikse pa achitèk OS la epi li depann de travay yo ki te planifye yo dwe egzekite nan li. Chanje kontèks se pa sèlman operasyon sèvis la ki gaspiye tan - pwogram nan kouri opere sou yon anpil nan lòt bagay, pou egzanp, kachèt divès kalite, ak ak chak switch li nesesè pou konsève pou ak restore anviwònman sa a, ki ka pran tou yon anpil nan. tan.
RR se yon bon pwogramè si nou te pale sèlman sou mezi tan repons lan. Men, ki jan metrik tan pou travay la ap konpòte ak algorithm sa a? Konsidere egzanp ki anwo a, lè tan opere A, B, C = 5s epi rive an menm tan. Travay A ap fini nan 13, B nan 14, C nan 15s ak tan an mwayèn nan vire pral 14s. Kidonk, RR se algorithm ki pi mal la pou metrik woulman an.
An tèm pi jeneral, nenpòt algorithm RR-tip jis; li divize tan CPU a egalman ant tout pwosesis. Se konsa, mezi sa yo toujou ap konfli youn ak lòt.
Kidonk, nou gen plizyè algorithm konparan ak an menm tan an toujou gen plizyè sipozisyon ki rete - ke se tan an travay li te ye e ke travay la sèlman itilize CPU a.
Melanje ak I/O
Premye a tout, ann retire sipozisyon 4 ke pwosesis la sèlman itilize CPU a; natirèlman, sa a se pa ka a ak pwosesis yo ka jwenn aksè nan lòt ekipman.
Moman nenpòt pwosesis mande yon operasyon I/O, pwosesis la antre nan eta bloke, ap tann pou I/O fini. Si yo voye I / O nan kondwi a difisil, Lè sa a, yon operasyon konsa ka pran jiska plizyè ms oswa pi long, ak processeur a pral san fè anyen konsa nan moman sa a. Pandan tan sa a, pwogramè a ka okipe processeur a ak nenpòt lòt pwosesis. Pwochen desizyon pwogramè a ap gen pou pran se lè pwosesis la pral konplete I/O li yo. Lè sa rive, yon entèwonp pral rive epi OS la pral mete pwosesis ki rele I/O a nan eta pare a.
Ann gade yon egzanp plizyè pwoblèm. Chak nan yo mande pou 50ms nan tan CPU. Sepandan, premye a pral jwenn aksè I/O chak 10ms (ki pral egzekite tou chak 10ms). Ak pwosesis B tou senpleman itilize yon processeur 50ms san I/O.
Nan egzanp sa a nou pral itilize pwogramasyon STCF la. Ki jan orè a pral konpòte si yon pwosesis tankou A te lanse sou li? Li pral fè bagay sa yo: premye li pral konplètman travay sou pwosesis A, ak Lè sa a, pwosesis B.
Apwòch tradisyonèl la pou rezoud pwoblèm sa a se trete chak sou-tach 10 ms nan pwosesis A kòm yon travay separe. Kidonk, lè w kòmanse ak algorithm STJF, chwa ant yon travay 50 ms ak yon travay 10 ms evidan. Lè sa a, lè sou-tach A fini, pwosesis B ak I/O pral lanse. Apre I/O a fini, li pral nòmal pou kòmanse pwosesis 10ms A ankò olye pou yo pwosesis B. Nan fason sa a, li posib pou aplike sipèpoze, kote CPU a itilize pa yon lòt pwosesis pandan premye a ap tann pou la. I/O. Ak kòm yon rezilta, sistèm nan pi byen itilize - nan moman sa a lè pwosesis entèaktif yo ap tann pou I / O, lòt pwosesis yo ka egzekite sou processeur a.
Oracle la pa gen ankò
Koulye a, kite a eseye debarase m de sipozisyon an ke yo konnen tan an kouri nan travay la. Sa a se jeneralman pi move ak pi ireyèl sipozisyon sou lis la tout antye. An reyalite, nan eksplwatasyon an mwayèn òdinè, eksplwatasyon an tèt li anjeneral konnen trè ti kras sou tan an ekzekisyon nan travay, kidonk ki jan Lè sa a, ou ka bati yon pwogramè san yo pa konnen konbyen tan travay la pral pran pou egzekite? Petèt nou ta ka itilize kèk prensip RR pou rezoud pwoblèm sa a?
Total
Nou te gade lide debaz yo nan orè travay ak gade nan 2 fanmi nan orè. Premye a kòmanse travay ki pi kout la an premye epi konsa ogmante tan an deplasman, pandan y ap dezyèm nan chire ant tout travay egalman, ogmante tan an repons. Tou de algoritm yo se move kote algoritm nan lòt fanmi an bon. Nou te gade tou ki jan itilizasyon paralèl CPU ak I/O ka amelyore pèfòmans, men pa t rezoud pwoblèm nan ak eksplwatasyon OS. Ak nan pwochen leson an nou pral gade nan yon planifikatè ki gade nan tan pase imedya a epi eseye predi lavni an. Epi li rele keu fidbak milti-nivo.
Sous: www.habr.com