Introduction to Operating Systems
Nyob zoo, Habr! Kuv xav nthuav qhia rau koj mloog ib co kab lus-kev txhais lus ntawm ib cov ntaub ntawv uas nthuav hauv kuv lub tswv yim - OSTEP. Cov ntaub ntawv no soj ntsuam heev heev ua hauj lwm ntawm unix-zoo li operating systems, uas yog, ua hauj lwm nrog cov txheej txheem, ntau yam teem sij hawm, nco thiab lwm yam zoo sib xws Cheebtsam uas tsim ib tug niaj hnub OS. Koj tuaj yeem pom tus thawj ntawm tag nrho cov ntaub ntawv ntawm no . Thov nco ntsoov tias qhov kev txhais lus tau ua tsis muaj kev tshaj lij (tseem dawb), tab sis kuv vam tias kuv khaws lub ntsiab lus dav dav.
Lab ua hauj lwm rau cov ncauj lus no tuaj yeem pom ntawm no:
Lwm qhov chaw:
Koj tuaj yeem tshawb xyuas kuv channel ntawm =)
Taw qhia rau Scheduler
Lub ntsiab ntawm qhov teeb meem: Yuav ua li cas los tsim ib txoj cai teem caij
Yuav ua li cas cov txheej txheem teem caij teem caij yuav tsum tau tsim? Dab tsi yuav tsum yog cov kev xav tseem ceeb? Cov kev ntsuas dab tsi tseem ceeb? Dab tsi yog cov txheej txheem yooj yim tau siv hauv cov tshuab xam zauv thaum ntxov?
Workload Assumptions
Ua ntej sib tham txog cov cai muaj peev xwm, cia peb xub ua ob peb qhov yooj yim digressions txog cov txheej txheem khiav hauv qhov system, uas yog hu ua kev ua haujlwm. Kev txhais cov haujlwm ua haujlwm yog ib feem tseem ceeb ntawm kev tsim cov cai, thiab qhov ntau koj paub txog kev ua haujlwm, qhov zoo dua txoj cai koj tuaj yeem sau tau.
Cia peb ua cov kev xav hauv qab no txog cov txheej txheem khiav hauv qhov system, qee zaum kuj hu ua cov hauj lwm (cov haujlwm). Yuav luag tag nrho cov kev xav no tsis yog qhov tseeb, tab sis tsim nyog rau txoj kev loj hlob ntawm kev xav.
- Txhua txoj haujlwm ua haujlwm rau tib lub sijhawm,
- Txhua txoj haujlwm tau teeb tsa ib txhij,
- Lub luag haujlwm uas tau muab ua haujlwm kom txog thaum nws tiav,
- Txhua yam haujlwm tsuas yog siv CPU,
- Lub sijhawm khiav ntawm txhua txoj haujlwm yog paub.
Scheduler Metrics
Ntxiv nrog rau qee qhov kev xav txog kev thauj khoom, lwm yam cuab yeej rau kev sib piv cov cai sib txawv yog xav tau: cov ntsuas ntsuas. Ib tug metric yog ib qho kev ntsuas ntawm ib yam dab tsi. Muaj ntau qhov kev ntsuas uas tuaj yeem siv los sib piv cov sijhawm teem sijhawm.
Piv txwv li, peb yuav siv lub metric hu ua lub sijhawm hloov pauv (lub sijhawm hloov pauv). Lub sijhawm ua haujlwm hloov pauv tau txhais tau tias yog qhov sib txawv ntawm lub sijhawm ua haujlwm tiav thiab lub sijhawm ua haujlwm tuaj txog hauv qhov system.
Tturnaround=Tcompletion-Tarrival
Txij li thaum peb xav tias txhua txoj haujlwm tuaj txog tib lub sijhawm, Ta = 0 thiab yog li Tt = Tc. Tus nqi no yuav hloov pauv thaum peb hloov cov kev xav saum toj no.
Lwm metric - kev ncaj ncees (kev ncaj ncees, ncaj ncees). Kev tsim khoom thiab kev ncaj ncees feem ntau yog tawm tsam cov yam ntxwv hauv kev npaj. Piv txwv li, tus teem sij hawm yuav ua kom zoo dua qhov kev ua tau zoo, tab sis ntawm tus nqi tos rau lwm cov dej num khiav, yog li txo kev ncaj ncees.
UA NTEJ UA HAUJ LWM (FIFO)
Qhov yooj yim tshaj plaws algorithm uas peb tuaj yeem siv tau yog hu ua FIFO lossis thawj tuaj (hauv), thawj zaug (tawm). Qhov algorithm no muaj ntau qhov zoo: nws yooj yim heev rau kev siv thiab nws haum txhua qhov peb xav tau thiab ua haujlwm zoo heev.
Cia peb saib ib qho piv txwv yooj yim. Cia peb hais tias 3 txoj haujlwm tau teeb tsa ib txhij. Tab sis cia peb xav tias txoj haujlwm A tuaj txog me ntsis ntxov dua li lwm tus, yog li nws yuav tshwm sim hauv daim ntawv teev npe ua ntej tshaj lwm tus, ib yam li B txheeb ze rau C. Cia peb xav tias txhua tus yuav raug tua rau 10 vib nas this. Lub sijhawm nruab nrab ntawm cov haujlwm no yuav yog dabtsi?
Los ntawm suav cov txiaj ntsig - 10 + 20 + 30 thiab faib los ntawm 3, peb tau txais qhov nruab nrab qhov kev ua tiav lub sijhawm sib npaug li 20 vib nas this.
Tam sim no cia sim hloov peb qhov kev xav. Tshwj xeeb, kev xav 1 thiab yog li peb yuav tsis xav tias txhua txoj haujlwm yuav siv sij hawm tib lub sijhawm los ua. FIFO yuav ua li cas lub sijhawm no?
Raws li nws hloov tawm, lub sijhawm ua haujlwm sib txawv muaj qhov cuam tshuam tsis zoo rau kev tsim khoom ntawm FIFO algorithm. Cia peb xav tias txoj haujlwm A yuav siv sijhawm 100 vib nas this kom tiav, thaum B thiab C tseem yuav siv sijhawm 10 vib nas this.
Raws li tuaj yeem pom los ntawm daim duab, lub sijhawm nruab nrab rau lub kaw lus yuav yog (100 + 110 + 120) / 3 = 110. Cov nyhuv no hu ua convoy nyhuv, thaum qee cov neeg siv khoom luv luv ntawm cov peev txheej yuav queue tom qab cov neeg siv khoom hnyav. Nws zoo li txoj kab ntawm lub khw muag khoom noj thaum muaj cov neeg siv khoom nyob rau pem hauv ntej ntawm koj nrog lub laub puv. Txoj kev daws teeb meem zoo tshaj plaws yog sim hloov cov ntawv sau nyiaj ntsuab lossis so kom txaus thiab ua pa tob tob.
Txoj hauj lwm luv tshaj ua ntej
Puas muaj peev xwm daws tau qhov xwm txheej zoo sib xws nrog cov txheej txheem hnyav? Muaj tseeb tiag. Lwm hom kev npaj hu uaTxoj hauj lwm luv tshaj ua ntej (SJF). Nws cov algorithm tseem yog qhov tseem ceeb heev - raws li lub npe cuam tshuam, cov haujlwm luv tshaj plaws yuav pib ua ntej, ib qho tom qab.
Hauv qhov piv txwv no, qhov tshwm sim ntawm kev khiav cov txheej txheem tib yam yuav yog ib qho kev txhim kho nyob rau hauv nruab nrab qhov kev pab cuam turnaround lub sij hawm thiab nws yuav sib npaug. 50 ua 110, uas yuav luag 2 npaug zoo dua.
Yog li, rau qhov kev xav tias txhua txoj haujlwm tuaj txog tib lub sijhawm, SJF algorithm zoo li yog qhov zoo tshaj plaws algorithm. Txawm li cas los xij, peb qhov kev xav tseem tsis zoo li qhov tseeb. Lub sijhawm no peb hloov qhov kev xav 2 thiab lub sijhawm no xav txog tias cov haujlwm tuaj yeem tshwm sim txhua lub sijhawm, thiab tsis yog txhua lub sijhawm. Qhov no tuaj yeem ua rau muaj teeb meem dab tsi?
Cia peb xav txog tias txoj haujlwm A (100c) tuaj txog ua ntej thiab pib ua tiav. Ntawm t = 10, cov haujlwm B thiab C tuaj txog, txhua qhov yuav siv sijhawm 10 vib nas this. Yog li lub sijhawm ua haujlwm nruab nrab yog (100+(110-10)+(120-10))3 = 103. Tus teem sijhawm yuav ua li cas los txhim kho qhov no?
Shortest Time-to-Completion First (STCF)
Txhawm rau txhim kho qhov xwm txheej, peb tshem tawm qhov kev xav 3 tias qhov kev pab cuam tau pib thiab khiav mus txog thaum ua tiav. Tsis tas li ntawd, peb yuav xav tau kev txhawb nqa kho vajtse thiab, raws li koj xav tau, peb yuav siv timer los cuam tshuam ib txoj haujlwm khiav thiab kev hloov pauv. Yog li, tus neeg teem sijhawm tuaj yeem ua ib yam dab tsi thaum lub sijhawm ua haujlwm B, C tuaj txog - nres ua haujlwm A thiab muab cov haujlwm B thiab C ua tiav thiab, tom qab lawv ua tiav, txuas ntxiv ua cov txheej txheem A. Cov sijhawm teem sijhawm no yog hu ua STCFlos yog Preemptive Job First.
Cov txiaj ntsig ntawm qhov kev npaj no yuav yog cov txiaj ntsig hauv qab no: ((120-0) + (20-10) + (30-10)) / 3 = 50. Yog li, xws li lub sijhawm teem sijhawm dhau los ua qhov zoo tshaj plaws rau peb txoj haujlwm.
Lub Sijhawm Teb Metric
Yog li, yog tias peb paub lub sijhawm ua haujlwm ntawm cov haujlwm thiab cov haujlwm no tsuas yog siv CPU, STCF yuav yog qhov kev daws teeb meem zoo tshaj plaws. Thiab ib zaug thaum ntxov, cov algorithms ua haujlwm zoo heev. Txawm li cas los xij, tus neeg siv tam sim no siv sijhawm feem ntau ntawm nws lub davhlau ya nyob twg thiab cia siab tias yuav muaj kev sib tham sib tham. Yog li ib tug tshiab metric tau yug los - lub sij hawm teb ( teb).
Lub sij hawm teb yog xam raws li nram no:
Tresponse=Tfirstrun-Tarrival
Yog li, piv txwv yav dhau los, lub sijhawm teb yuav yog: A = 0, B = 0, C = 10 (abg = 3,33).
Thiab nws hloov tawm tias STCF algorithm tsis zoo nyob rau hauv qhov xwm txheej uas 3 txoj haujlwm tuaj txog tib lub sijhawm - nws yuav tsum tau tos kom txog thaum cov haujlwm me me ua tiav. Yog li lub algorithm yog qhov zoo rau lub sij hawm tig rov qab metric, tab sis tsis zoo rau kev sib cuam tshuam metric. Xav txog yog tias koj tau zaum ntawm lub davhlau ya nyob twg sim ntaus cov cim rau hauv tus editor thiab yuav tsum tau tos ntau dua 10 vib nas this vim qee lwm txoj haujlwm tau noj CPU. Nws tsis zoo siab heev.
Yog li peb tau ntsib nrog lwm qhov teeb meem - peb yuav ua li cas thiaj tsim tau lub sijhawm teem sijhawm uas nkag siab rau lub sijhawm teb?
Hloov Plawv Kab Robin
Ib qho algorithm tau tsim los daws qhov teeb meem no Hloov Plawv Kab Robin (RR). Lub tswv yim yooj yim yog qhov yooj yim heev: tsis txhob khiav cov haujlwm kom txog thaum lawv ua tiav, peb yuav khiav txoj haujlwm rau lub sijhawm (hu ua lub sijhawm hlais) thiab tom qab ntawd hloov mus rau lwm txoj haujlwm los ntawm cov kab. Lub algorithm rov ua nws txoj haujlwm kom txog thaum tag nrho cov haujlwm tiav. Hauv qhov no, lub sijhawm khiav ntawm qhov kev zov me nyuam yuav tsum yog ntau lub sijhawm tom qab uas lub sijhawm yuav cuam tshuam cov txheej txheem. Piv txwv li, yog tias tus timer cuam tshuam cov txheej txheem txhua x = 10ms, ces qhov loj ntawm cov txheej txheem ua tiav qhov rais yuav tsum yog ntau yam ntawm 10 thiab yog 10,20 lossis x * 10.
Cia peb saib ib qho piv txwv: ABC cov haujlwm tuaj txog ib txhij hauv lub kaw lus thiab lawv txhua tus xav khiav 5 vib nas this. SJF algorithm yuav ua tiav txhua txoj haujlwm ua ntej pib ua haujlwm. Hauv qhov sib piv, RR algorithm nrog lub qhov rais qhib = 1s yuav mus dhau cov haujlwm raws li hauv qab no (Fig. 4.3):
(SJF dua (Tsis zoo rau lub sijhawm teb)
(Round Robin (Zoo Rau Lub Sijhawm Teb)
Lub sijhawm teb nruab nrab rau RR algorithm yog (0 + 1 + 2) / 3 = 1, thaum rau SJF (0 + 5 + 10) / 3 = 5.
Nws yog qhov xav tau los xav tias lub sijhawm lub qhov rais yog qhov tseem ceeb heev rau RR; qhov me dua nws yog, lub sijhawm teb ntau dua. Txawm li cas los xij, koj yuav tsum tsis txhob ua kom me me, vim tias lub sijhawm hloov pauv tseem yuav ua lub luag haujlwm hauv kev ua haujlwm tag nrho. Yog li, qhov kev xaiv ntawm kev tua lub qhov rais lub sij hawm yog teem los ntawm OS tus kws kes duab vajtse thiab nyob ntawm seb cov hauj lwm uas tau npaj yuav tsum tau ua nyob rau hauv nws. Hloov cov ntsiab lus tsis yog qhov kev pabcuam nkaus xwb uas nkim sijhawm - cov haujlwm khiav haujlwm ua haujlwm ntawm ntau lwm yam, piv txwv li, ntau yam caches, thiab nrog rau txhua qhov kev hloov pauv, nws yog ib qho tsim nyog yuav tau txuag thiab kho qhov chaw no, uas tuaj yeem siv ntau yam. sij hawm.
RR yog tus teem sijhawm zoo yog tias peb tab tom tham tsuas yog hais txog qhov ntsuas lub sijhawm teb. Tab sis yuav ua li cas cov hauj lwm tigaround sij hawm metric coj tus cwj pwm nrog no algorithm? Xav txog qhov piv txwv saum toj no, thaum lub sijhawm ua haujlwm ntawm A, B, C = 5s thiab tuaj txog tib lub sijhawm. Txoj Haujlwm A yuav xaus ntawm 13, B ntawm 14, C ntawm 15s thiab lub sijhawm hloov pauv nruab nrab yuav yog 14s. Yog li, RR yog qhov phem tshaj algorithm rau kev ntsuas qhov ntsuas.
Hauv cov ntsiab lus dav dav, txhua qhov RR-hom algorithm yog qhov ncaj ncees; nws faib lub sijhawm CPU sib npaug ntawm txhua qhov txheej txheem. Thiab yog li, cov kev ntsuas no tsis tu ncua tsis sib haum nrog ib leeg.
Yog li, peb muaj ntau qhov sib txawv algorithms thiab tib lub sijhawm tseem muaj ntau qhov kev xav tau sab laug - tias lub sijhawm ua haujlwm tau paub thiab cov haujlwm tsuas yog siv CPU xwb.
Kev sib xyaw nrog I / O
Ua ntej tshaj plaws, cia peb tshem tawm qhov kev xav 4 tias cov txheej txheem tsuas yog siv CPU; ib txwm, qhov no tsis yog qhov xwm txheej thiab cov txheej txheem tuaj yeem nkag mus rau lwm yam khoom siv.
Lub sijhawm twg cov txheej txheem thov kev ua haujlwm I/O, cov txheej txheem nkag mus rau hauv lub xeev thaiv, tos kom tiav I/O. Yog tias I / O raug xa mus rau lub hard drive, qhov kev ua haujlwm zoo li no tuaj yeem siv sijhawm ntev li ob peb ms lossis ntev dua, thiab lub processor yuav tsis ua haujlwm tam sim no. Lub sijhawm no, tus teem sijhawm tuaj yeem tuav lub processor nrog rau lwm cov txheej txheem. Qhov kev txiav txim tom ntej uas tus neeg teem caij yuav tau ua yog thaum tus txheej txheem yuav ua tiav nws I/O. Thaum qhov no tshwm sim, kev cuam tshuam yuav tshwm sim thiab OS yuav muab cov txheej txheem hu ua I / O rau hauv lub xeev npaj.
Cia peb saib ib qho piv txwv ntawm ntau yam teeb meem. Txhua ntawm lawv xav tau 50ms ntawm CPU lub sijhawm. Txawm li cas los xij, thawj tus yuav nkag mus rau I / O txhua 10ms (uas tseem yuav raug tua txhua 10ms). Thiab cov txheej txheem B tsuas yog siv 50ms processor tsis muaj I / O.
Hauv qhov piv txwv no peb yuav siv STCF teem caij. Tus neeg teem sijhawm yuav coj li cas yog tias tus txheej txheem zoo li A tau pib rau nws? Nws yuav ua raws li hauv qab no: ua ntej nws yuav ua tiav cov txheej txheem A, thiab tom qab ntawd txheej txheem B.
Txoj hauv kev ib txwm los daws qhov teeb meem no yog kho txhua 10 ms subtask ntawm txheej txheem A raws li ib txoj haujlwm cais. Yog li, thaum pib nrog STJF algorithm, kev xaiv ntawm 50 ms txoj haujlwm thiab 10 ms txoj haujlwm yog qhov pom tseeb. Tom qab ntawd, thaum subtask A tiav lawm, txheej txheem B thiab I / O yuav pib. Tom qab I / O ua tiav, nws yuav raug coj los ua kev cai pib 10ms txheej txheem A dua es tsis yog txheej txheem B. Ua li no, nws muaj peev xwm los siv sib tshooj, qhov twg CPU siv los ntawm lwm cov txheej txheem thaum thawj tus tab tom tos. I/O. Thiab yog li ntawd, lub kaw lus siv tau zoo dua - lub sijhawm thaum cov txheej txheem sib tham sib tos rau I / O, lwm cov txheej txheem tuaj yeem ua tiav ntawm lub processor.
Lub Oracle tsis muaj ntxiv lawm
Tam sim no cia peb sim tshem tawm qhov kev xav tias lub sijhawm khiav ntawm txoj haujlwm tau paub. Qhov no feem ntau yog qhov kev xav phem tshaj plaws thiab tsis muaj tseeb tshaj plaws ntawm tag nrho cov npe. Qhov tseeb, hauv qhov nruab nrab ntawm OS, OS nws tus kheej feem ntau paub me ntsis txog lub sijhawm ua tiav ntawm cov haujlwm, yog li koj tuaj yeem tsim lub sijhawm teem sijhawm yam tsis paub tias yuav siv sijhawm ntev npaum li cas los ua haujlwm? Tej zaum peb tuaj yeem siv qee cov ntsiab lus RR los daws qhov teeb meem no?
Qhov no
Peb saib cov tswv yim tseem ceeb ntawm kev teem sijhawm ua haujlwm thiab saib 2 tsev neeg ntawm cov neeg teem sijhawm. Thawj qhov pib ua haujlwm luv tshaj ua ntej thiab yog li ua kom lub sijhawm hloov pauv, thaum lub sijhawm thib ob yog torn ntawm txhua txoj haujlwm sib npaug, ua rau lub sijhawm teb. Ob lub algorithms yog qhov phem qhov twg algorithms ntawm lwm tsev neeg yog qhov zoo. Peb kuj tau saib yuav ua li cas sib npaug ntawm kev siv CPU thiab I / O tuaj yeem txhim kho kev ua tau zoo, tab sis tsis daws teeb meem nrog OS clairvoyance. Thiab nyob rau hauv zaj lus qhia tom ntej peb yuav saib tus neeg npaj uas saib mus rau yav dhau los tam sim ntawd thiab sim twv seb yav tom ntej. Thiab nws yog hu ua multi-level tawm tswv yim queue.
Tau qhov twg los: www.hab.com