Panimula sa Mga Operating System
Hello, Habr! Nais kong ipakita sa iyong pansin ang isang serye ng mga artikulo-pagsasalin ng isang panitikan na kawili-wili sa aking opinyon - OSTEP. Malalim na sinusuri ng materyal na ito ang gawain ng mga operating system na katulad ng unix, ibig sabihin, gumagana sa mga proseso, iba't ibang mga scheduler, memorya at iba pang katulad na mga bahagi na bumubuo sa isang modernong OS. Maaari mong makita ang orihinal ng lahat ng mga materyales dito . Pakitandaan na ang pagsasalin ay ginawa nang hindi propesyonal (medyo malaya), ngunit sana ay pinanatili ko ang pangkalahatang kahulugan.
Ang gawain sa laboratoryo sa paksang ito ay matatagpuan dito:
Iba pang parte:
Maaari mo ring tingnan ang aking channel sa =)
Panimula sa Scheduler
Ang kakanyahan ng problema: Paano bumuo ng isang patakaran sa scheduler
Paano dapat idisenyo ang pinagbabatayan na mga balangkas ng patakaran ng scheduler? Ano ang dapat na pangunahing pagpapalagay? Anong mga sukatan ang mahalaga? Anong mga pangunahing pamamaraan ang ginamit sa mga unang sistema ng pag-compute?
Mga Assumption sa Workload
Bago talakayin ang mga posibleng patakaran, gumawa muna tayo ng ilang nagpapasimpleng digression tungkol sa mga prosesong tumatakbo sa system, na kung saan ay sama-samang tinatawag workload. Ang pagtukoy sa workload ay isang kritikal na bahagi ng pagbuo ng mga patakaran, at kung mas marami kang alam tungkol sa workload, mas mahusay ang patakaran na maaari mong isulat.
Gawin natin ang mga sumusunod na pagpapalagay tungkol sa mga prosesong tumatakbo sa system, kung minsan ay tinatawag din trabaho (mga gawain). Halos lahat ng mga pagpapalagay na ito ay hindi makatotohanan, ngunit kinakailangan para sa pag-unlad ng pag-iisip.
- Ang bawat gawain ay tumatakbo para sa parehong dami ng oras,
- Ang lahat ng mga gawain ay itinakda nang sabay-sabay,
- Gumagana ang nakatalagang gawain hanggang sa matapos,
- Ang lahat ng mga gawain ay gumagamit lamang ng CPU,
- Alam ang oras ng pagtakbo ng bawat gawain.
Mga Sukatan ng Scheduler
Bilang karagdagan sa ilang mga pagpapalagay tungkol sa pag-load, kailangan ng isa pang tool para sa paghahambing ng iba't ibang mga patakaran sa pag-iiskedyul: mga sukatan ng scheduler. Ang sukatan ay ilang sukat lamang ng isang bagay. Mayroong ilang mga sukatan na maaaring magamit upang ihambing ang mga scheduler.
Halimbawa, gagamit tayo ng panukat na tinatawag oras ng turnaround (oras ng turnaround). Ang oras ng turnaround ng gawain ay tinukoy bilang ang pagkakaiba sa pagitan ng oras ng pagkumpleto ng gawain at ang oras ng pagdating ng gawain sa system.
Tturnaround=Tcompletion−Tarrival
Dahil ipinapalagay namin na ang lahat ng mga gawain ay dumating sa parehong oras, pagkatapos ay Ta = 0 at kaya Tt = Tc. Ang halagang ito ay natural na magbabago kapag binago natin ang mga pagpapalagay sa itaas.
Isa pang sukatan - pagkakapantay-pantay (pagkamakatarungan, katapatan). Ang pagiging produktibo at pagiging patas ay kadalasang magkasalungat na katangian sa pagpaplano. Halimbawa, maaaring i-optimize ng scheduler ang pagganap, ngunit sa halaga ng paghihintay para sa iba pang mga gawain na tumakbo, kaya binabawasan ang pagiging patas.
FIRST IN FIRST OUT (FIFO)
Ang pinakapangunahing algorithm na maaari nating ipatupad ay tinatawag na FIFO o unang pumasok, unang nagsilbi (lumabas). Ang algorithm na ito ay may ilang mga pakinabang: napakadaling ipatupad at umaangkop ito sa lahat ng aming mga pagpapalagay at ginagawa nang maayos ang trabaho.
Tingnan natin ang isang simpleng halimbawa. Sabihin nating 3 gawain ang itinakda nang sabay-sabay. Ngunit ipagpalagay natin na ang gawain A ay dumating nang medyo mas maaga kaysa sa lahat ng iba, kaya ito ay lalabas sa listahan ng pagpapatupad nang mas maaga kaysa sa iba, tulad ng B na nauugnay sa C. Ipagpalagay natin na ang bawat isa sa kanila ay isasagawa sa loob ng 10 segundo. Ano ang magiging average na oras upang makumpleto ang mga gawaing ito sa kasong ito?
Sa pamamagitan ng pagbibilang ng mga halaga - 10+20+30 at paghahati sa 3, nakukuha namin ang average na oras ng pagpapatupad ng programa na katumbas ng 20 segundo.
Ngayon subukan nating baguhin ang ating mga pagpapalagay. Sa partikular, ang pagpapalagay 1 at sa gayon ay hindi na namin ipagpalagay na ang bawat gawain ay tumatagal ng parehong dami ng oras upang maisagawa. Paano gaganap ang FIFO sa oras na ito?
Sa lumalabas, ang iba't ibang oras ng pagpapatupad ng gawain ay may lubhang negatibong epekto sa pagiging produktibo ng FIFO algorithm. Ipagpalagay natin na ang gawain A ay tatagal ng 100 segundo upang makumpleto, habang ang B at C ay tatagal pa rin ng 10 segundo bawat isa.
Tulad ng makikita mula sa figure, ang average na oras para sa system ay magiging (100+110+120)/3=110. Ang epektong ito ay tinatawag epekto ng convoy, kapag ang ilang panandaliang mamimili ng isang mapagkukunan ay pumila pagkatapos ng isang mabigat na mamimili. Parang linya sa grocery kapag may customer sa harap mo na may laman na cart. Ang pinakamahusay na solusyon sa problema ay subukang baguhin ang cash register o magpahinga at huminga ng malalim.
Pinakamaikling Trabaho Una
Posible bang malutas ang isang katulad na sitwasyon sa mga proseso ng mabibigat na timbang? tiyak. Isa pang uri ng pagpaplano ang tinatawagPinakamaikling Trabaho Una (SJF). Ang algorithm nito ay medyo primitive - tulad ng ipinahihiwatig ng pangalan, ang pinakamaikling gawain ay unang ilulunsad, isa-isa.
Sa halimbawang ito, ang resulta ng pagpapatakbo ng parehong mga proseso ay isang pagpapabuti sa average na oras ng turnaround ng programa at ito ay magiging katumbas ng 50 sa halip na 110, na halos 2 beses na mas mahusay.
Kaya, para sa ibinigay na pagpapalagay na ang lahat ng mga gawain ay dumating sa parehong oras, ang SJF algorithm ay tila ang pinakamainam na algorithm. Gayunpaman, ang aming mga pagpapalagay ay hindi pa rin makatotohanan. Sa pagkakataong ito ay binago natin ang palagay 2 at sa pagkakataong ito ay isipin na ang mga gawain ay maaaring naroroon anumang oras, at hindi lahat sa parehong oras. Anong mga problema ang maaaring humantong sa?
Isipin natin na ang gawain A (100c) ay unang dumating at nagsisimulang isagawa. Sa t=10, dumating ang mga gawain B at C, na ang bawat isa ay aabot ng 10 segundo. Kaya ang average na oras ng pagpapatupad ay (100+(110-10)+(120-10))3 = 103. Ano ang maaaring gawin ng scheduler para mapabuti ito?
Pinakamaikling Oras-Unang Pagkumpleto (STCF)
Upang mapabuti ang sitwasyon, inalis namin ang pagpapalagay 3 na ang programa ay inilunsad at tumatakbo hanggang sa makumpleto. Bilang karagdagan, kakailanganin namin ang suporta sa hardware at, tulad ng maaari mong hulaan, gagamitin namin timer upang matakpan ang isang tumatakbong gawain at paglipat ng konteksto. Kaya, ang scheduler ay maaaring gumawa ng isang bagay sa sandaling dumating ang mga gawain B, C - itigil ang pagpapatupad ng gawain A at ilagay ang mga gawain B at C sa pagproseso at, pagkatapos ng kanilang pagkumpleto, ipagpatuloy ang pagpapatupad ng proseso A. Ang nasabing scheduler ay tinatawag na STCFo Preemptive Job Una.
Ang resulta ng planner na ito ay ang sumusunod na resulta: ((120-0)+(20-10)+(30-10))/3=50. Kaya, ang naturang scheduler ay nagiging mas optimal para sa ating mga gawain.
Oras ng Pagtugon ng Sukatan
Kaya, kung alam natin ang oras ng pagpapatakbo ng mga gawain at ang mga gawaing ito ay gumagamit lamang ng CPU, ang STCF ang magiging pinakamahusay na solusyon. At minsan sa mga unang panahon, gumana nang maayos ang mga algorithm na ito. Gayunpaman, ginugugol na ngayon ng user ang karamihan ng kanyang oras sa terminal at inaasahan ang isang produktibong interactive na karanasan. Kaya't ipinanganak ang isang bagong sukatan - oras ng pagtugon (tugon).
Ang oras ng pagtugon ay kinakalkula tulad ng sumusunod:
Tresponse=Tfirstrun−Tarrival
Kaya, para sa nakaraang halimbawa, ang oras ng pagtugon ay magiging: A=0, B=0, C=10 (abg=3,33).
At lumalabas na ang algorithm ng STCF ay hindi napakahusay sa isang sitwasyon kung saan 3 mga gawain ang dumating sa parehong oras - kakailanganin itong maghintay hanggang sa ganap na makumpleto ang mga maliliit na gawain. Kaya't ang algorithm ay mabuti para sa sukatan ng oras ng turnaround, ngunit masama para sa sukatan ng interactivity. Isipin kung nakaupo ka sa isang terminal na sinusubukang mag-type ng mga character sa isang editor at kailangang maghintay ng higit sa 10 segundo dahil may ibang gawain na kumukuha ng CPU. Ito ay hindi masyadong kaaya-aya.
Kaya tayo ay nahaharap sa isa pang problema - paano tayo makakabuo ng isang scheduler na sensitibo sa oras ng pagtugon?
Round Robin
Ang isang algorithm ay binuo upang malutas ang problemang ito Round Robin (RR). Ang pangunahing ideya ay medyo simple: sa halip na patakbuhin ang mga gawain hanggang sa makumpleto ang mga ito, patakbuhin namin ang gawain para sa isang tiyak na tagal ng panahon (tinatawag na time slice) at pagkatapos ay lumipat sa isa pang gawain mula sa pila. Inuulit ng algorithm ang gawain nito hanggang sa makumpleto ang lahat ng gawain. Sa kasong ito, ang oras ng pagpapatakbo ng programa ay dapat na isang maramihang oras na pagkatapos ay maaantala ng timer ang proseso. Halimbawa, kung ang isang timer ay nakakaabala sa isang proseso tuwing x=10ms, ang laki ng window ng pagpapatupad ng proseso ay dapat na isang multiple ng 10 at 10,20 o x*10.
Tingnan natin ang isang halimbawa: Ang mga gawain sa ABC ay sabay-sabay na dumarating sa system at bawat isa sa kanila ay gustong tumakbo nang 5 segundo. Kukumpletuhin ng SJF algorithm ang bawat gawain hanggang sa matapos bago magsimula ng isa pa. Sa kabaligtaran, ang RR algorithm na may launch window = 1s ay dadaan sa mga gawain tulad ng sumusunod (Larawan 4.3):
(SJF Muli (Masama para sa Oras ng Pagtugon)
(Round Robin (Magandang Para sa Oras ng Pagtugon)
Ang average na oras ng pagtugon para sa RR algorithm ay (0+1+2)/3=1, habang para sa SJF (0+5+10)/3=5.
Lohikal na ipagpalagay na ang time window ay isang napakahalagang parameter para sa RR; mas maliit ito, mas mataas ang oras ng pagtugon. Gayunpaman, hindi mo dapat gawin itong masyadong maliit, dahil ang oras ng paglipat ng konteksto ay magkakaroon din ng papel sa pangkalahatang pagganap. Kaya, ang pagpili ng oras ng window ng pagpapatupad ay itinakda ng arkitekto ng OS at depende sa mga gawain na binalak na maisakatuparan dito. Ang paglipat ng konteksto ay hindi lamang ang operasyon ng serbisyo na nag-aaksaya ng oras - ang tumatakbong programa ay nagpapatakbo sa maraming iba pang mga bagay, halimbawa, iba't ibang mga cache, at sa bawat switch kinakailangan upang i-save at ibalik ang kapaligiran na ito, na maaari ring tumagal ng maraming oras.
Ang RR ay isang mahusay na scheduler kung pinag-uusapan lang natin ang sukatan ng oras ng pagtugon. Ngunit paano gagana ang sukatan ng oras ng turnaround ng gawain sa algorithm na ito? Isaalang-alang ang halimbawa sa itaas, kapag ang oras ng pagpapatakbo ng A, B, C = 5s at dumating sa parehong oras. Ang Gawain A ay magtatapos sa 13, B sa 14, C sa 15s at ang average na oras ng turnaround ay magiging 14s. Kaya, ang RR ay ang pinakamasamang algorithm para sa sukatan ng turnover.
Sa mas pangkalahatang mga termino, ang anumang RR-type na algorithm ay patas; hinahati nito ang oras ng CPU nang pantay sa lahat ng mga proseso. At sa gayon, ang mga sukatang ito ay patuloy na sumasalungat sa isa't isa.
Kaya, mayroon kaming ilang magkakaibang mga algorithm at sa parehong oras ay mayroon pa ring ilang mga pagpapalagay na natitira - na ang oras ng gawain ay kilala at na ang gawain ay gumagamit lamang ng CPU.
Hinahalo sa I/O
Una sa lahat, tanggalin natin ang pagpapalagay 4 na ang proseso ay gumagamit lamang ng CPU; natural, hindi ito ang kaso at ang mga proseso ay maaaring ma-access ang iba pang kagamitan.
Sa sandaling humiling ang anumang proseso ng operasyon ng I/O, papasok ang proseso sa naka-block na estado, naghihintay na makumpleto ang I/O. Kung ang I/O ay ipinadala sa hard drive, ang naturang operasyon ay maaaring tumagal ng hanggang ilang ms o mas matagal pa, at ang processor ay magiging idle sa sandaling ito. Sa panahong ito, maaaring sakupin ng scheduler ang processor sa anumang iba pang proseso. Ang susunod na desisyon na kailangang gawin ng scheduler ay kung kailan makukumpleto ng proseso ang I/O nito. Kapag nangyari ito, magkakaroon ng interrupt at ilalagay ng OS ang proseso na tumawag sa I/O sa ready state.
Tingnan natin ang isang halimbawa ng ilang mga gawain. Ang bawat isa sa kanila ay nangangailangan ng 50ms ng oras ng CPU. Gayunpaman, maa-access ng una ang I/O tuwing 10ms (na isasagawa din tuwing 10ms). At ang proseso B ay gumagamit lamang ng 50ms processor na walang I/O.
Sa halimbawang ito gagamitin namin ang STCF scheduler. Paano kikilos ang scheduler kung ang isang proseso tulad ng A ay inilunsad dito? Gagawin niya ang mga sumusunod: una niyang ganap na isagawa ang proseso A, at pagkatapos ay iproseso ang B.
Ang tradisyunal na diskarte upang malutas ang problemang ito ay upang ituring ang bawat 10 ms subtask ng proseso A bilang isang hiwalay na gawain. Kaya, kapag nagsimula sa STJF algorithm, ang pagpili sa pagitan ng 50 ms na gawain at isang 10 ms na gawain ay halata. Pagkatapos, kapag nakumpleto ang subtask A, ilulunsad ang proseso B at I/O. Matapos makumpleto ang I/O, magiging kaugalian na na simulan muli ang 10ms process A sa halip na proseso B. Sa ganitong paraan, posibleng ipatupad ang overlap, kung saan ang CPU ay ginagamit ng isa pang proseso habang ang una ay naghihintay para sa I/O. At bilang isang resulta, ang sistema ay mas mahusay na ginagamit - sa sandaling ang mga interactive na proseso ay naghihintay para sa I/O, ang iba pang mga proseso ay maaaring isagawa sa processor.
Wala na ang Oracle
Ngayon subukan nating alisin ang pag-aakala na ang oras ng pagpapatakbo ng gawain ay kilala. Sa pangkalahatan, ito ang pinakamasama at hindi makatotohanang pagpapalagay sa buong listahan. Sa katunayan, sa karaniwang ordinaryong OS, ang OS mismo ay karaniwang kakaunti ang nalalaman tungkol sa oras ng pagpapatupad ng mga gawain, kaya paano ka makakagawa ng isang scheduler nang hindi nalalaman kung gaano katagal ang gawain upang maisagawa? Marahil ay maaari nating gamitin ang ilang mga prinsipyo ng RR upang malutas ang problemang ito?
Kabuuan
Tiningnan namin ang mga pangunahing ideya ng pag-iiskedyul ng gawain at tumingin sa 2 pamilya ng mga scheduler. Sinisimulan muna ng una ang pinakamaikling gawain at sa gayon ay pinapataas ang oras ng turnaround, habang ang pangalawa ay napunit sa pagitan ng lahat ng mga gawain nang pantay-pantay, na nagpapataas ng oras ng pagtugon. Ang parehong mga algorithm ay masama kung saan ang mga algorithm ng ibang pamilya ay mabuti. Tiningnan din namin kung paano mapapabuti ng magkatulad na paggamit ng CPU at I/O ang pagganap, ngunit hindi nalutas ang problema sa OS clairvoyance. At sa susunod na aralin, titingnan natin ang isang tagaplano na tumitingin sa kagyat na nakaraan at sinusubukang hulaan ang hinaharap. At tinatawag itong multi-level na feedback queue.
Pinagmulan: www.habr.com