Операциялык системаларга киришүү
Эй Хабр! Мен сиздердин назарыңыздарга менин оюмча бир кызыктуу адабияттын бир катар макала-котормолорун келтиргим келет - OSTEP. Бул материалда Unix сыяктуу операциялык системалардын иши, тактап айтканда, процесстер, ар кандай пландоочулар, эс тутум жана заманбап ОСти түзгөн башка ушул сыяктуу компоненттер менен иштөө абдан терең талкууланат. Бардык материалдардын түп нускасын бул жерден көрө аласыз . Көңүл буруңуз, котормо профессионалдуу эмес (абдан эркин) жасалган, бирок мен жалпы маанини сактап калдым деп ишенем.
Бул тема боюнча лабораториялык иштерди бул жерден тапса болот:
Башка бөлүктөр:
Ошондой эле менин каналымды текшере аласыз =)
Пландаштыруучуга киришүү
Маселенин маңызы: Пландаштыруу саясатын кантип иштеп чыгуу керек
Негизги пландоочу саясаттын негиздери кантип иштелип чыгышы керек? Негизги божомолдор кандай болушу керек? Кандай көрсөткүчтөр маанилүү? Алгачкы эсептөө системаларында кандай негизги ыкмалар колдонулган?
Жумуш жүктөмү
Мүмкүн болгон саясаттарды талкуулоодон мурун, келгиле, адегенде системада иштеп жаткан процесстер жөнүндө бир нече жөнөкөйлөштүрүүнү жасайлы. жумуш жүгү. Жумуштун жүгүн аныктоо саясатты куруунун маанилүү бөлүгү болуп саналат жана иш жүгү жөнүндө канчалык көп билсеңиз, саясатты ошончолук жакшыраак жаза аласыз.
Келгиле, системада иштеп жаткан процесстер жөнүндө төмөнкү божомолдорду жасайлы, кээде ошондой эле деп аталат жумуш (милдеттери). Бул божомолдордун дээрлик бардыгы реалдуу эмес, ой жүгүртүүнүн өнүгүшү үчүн зарыл.
- Ар бир тапшырма бирдей убакытка созулат,
- Бардык милдеттер бир эле учурда коюлат,
- Берилген тапшырма аягына чейин иштейт,
- Бардык тапшырмалар CPU гана колдонот,
- Ар бир иштин иштөө убактысы белгилүү.
Пландаштыруучу метрика
Жүктөө жөнүндө кээ бир божомолдордон тышкары, ар кандай пландаштыруу саясатын салыштыруу үчүн дагы бир курал керек: пландоочу метрика. Метрика бир нерсенин кандайдыр бир көрсөткүчү. Пландоочуларды салыштыруу үчүн колдонула турган бир катар көрсөткүчтөр бар.
Мисалы, биз аталган метриканы колдонобуз айлануу убактысы (айлануу убактысы). Тапшырманы аткаруу убактысы тапшырманы аткаруу убактысы менен системага келүү убактысынын ортосундагы айырма катары аныкталат.
Tturnaround=Tcompletion−Tarrival
Биз бардык тапшырмалар бир убакта келди деп ойлогондуктан, анда Ta=0 жана ошентип Tt=Tc. Жогорудагы божомолдорду өзгөрткөндө бул маани табигый түрдө өзгөрөт.
Дагы бир көрсөткүч - адилеттүүлүк (калыстык, чынчылдык). Өндүрүмдүүлүк жана калыстык пландоодо көбүнчө карама-каршы мүнөздөмөлөр болуп саналат. Мисалы, пландоочу аткарууну оптималдаштырышы мүмкүн, бирок башка тапшырмалардын аткарылышын күтүүнүн баасы менен, ошентип, калыстыкты азайтат.
БИРИНЧИ КИРДИ БИРИНЧИ (FIFO)
Биз ишке ашыра турган эң негизги алгоритм FIFO же деп аталат биринчи келген (кирген), биринчи келген (чыгыш). Бул алгоритм бир нече артыкчылыктарга ээ: аны ишке ашыруу абдан жеңил жана ал биздин бардык божомолдорубузга туура келет жана ишти абдан жакшы аткарат.
Келгиле, жөнөкөй бир мисалды карап көрөлү. Бир убакта 3 милдет коюлду дейли. Бирок, келгиле, А тапшырмасы башкаларга караганда бир аз эртерээк келди дейли, андыктан ал аткаруу тизмесинде С га салыштырмалуу В сыяктуу эле башкаларга караганда эртерээк пайда болот. Алардын ар бири 10 секундада аткарылат деп коёлу. Бул учурда бул тапшырмаларды аткаруу үчүн орточо убакыт канча болот?
Маанилерди санап - 10+20+30 жана 3кө бөлүү менен биз программаны аткаруунун орточо убактысын 20 секундага барабар алабыз.
Эми биздин божомолдорду өзгөртүүгө аракет кылалы. Атап айтканда, 1-болжол менен, демек, биз мындан ары ар бир тапшырманы аткаруу үчүн бирдей убакытты талап кылат деп ойлобойбуз. FIFO бул жолу кандай аткарат?
Көрүнүп тургандай, тапшырманы аткаруунун ар кандай убакыттары FIFO алгоритминин өндүрүмдүүлүгүнө өтө терс таасирин тийгизет. Келгиле, А тапшырмасын аткарууга 100 секунд кетет, ал эми В жана С ар бирине дагы эле 10 секунд кетет деп коёлу.
Сүрөттөн көрүнүп тургандай, системанын орточо убактысы (100+110+120)/3=110 болот. Бул эффект деп аталат конвой эффекти, ресурстун кээ бир кыска мөөнөттүү керектөөчүлөрү оор керектөөчүдөн кийин кезекке турганда. Алдыңда араба толгон кардар турган азык-түлүк дүкөнүндөгү кезек сыяктуу. Маселенин эң жакшы чечими – кассаны алмаштырууга аракет кылуу же эс алып, терең дем алуу.
Эң кыска жумуш биринчи
Кандайдыр бир жол менен оор салмактуу процесстер менен ушундай кырдаалды чечүүгө болобу? Албетте. Пландаштыруунун дагы бир түрү деп аталатЭң кыска жумуш биринчи (SJF). Анын алгоритми да абдан примитивдүү – аты айтып тургандай, эң кыска тапшырмалар биринчи кезекте биринин артынан бири ишке киргизилет.
Бул мисалда, ошол эле процесстерди иштетүүнүн натыйжасы программанын орточо иштөө убактысынын жакшырышы болот жана ал барабар болот 50 ордуна 110, бул дээрлик 2 эсе жакшы.
Ошентип, бардык тапшырмалар бир убакта келет деген божомол үчүн SJF алгоритми эң оптималдуу алгоритм болуп көрүнөт. Бирок, биздин божомолдор дагы эле реалдуу көрүнбөйт. Бул жолу биз 2-болжолду өзгөртөбүз жана бул жолу тапшырмалар бир эле учурда эмес, каалаган убакта болушу мүмкүн деп элестетебиз. Бул кандай көйгөйлөргө алып келиши мүмкүн?
А (100c) тапшырмасы биринчи келип, аткарыла баштаганын элестетелик. t=10 болгондо, B жана C тапшырмалары келет, алардын ар бирине 10 секунд кетет. Ошентип, орточо аткаруу убактысы (100+(110-10)+(120-10))3 = 103. Пландоочу муну жакшыртуу үчүн эмне кыла алат?
Биринчи бүтүрүү үчүн эң кыска убакыт (STCF)
Кырдаалды жакшыртуу үчүн биз программанын ишке киргизилиши жана аягына чейин иштейт деген 3-божомолду калтырабыз. Мындан тышкары, бизге аппараттык колдоо керек болот жана сиз ойлогондой, биз колдонобуз таймер иштеп жаткан ишти үзгүлтүккө учуратууга жана контекстти алмаштыруу. Ошентип, пландоочу B, C тапшырмалары келгенде бир нерсе кыла алат - А тапшырмасын аткарууну токтотуп, В жана С тапшырмаларын иштеп чыгууга коёт жана алар аяктагандан кийин А процессин аткарууну уланта алат. Мындай пландоочу деп аталат. STCFже Биринчи кезектеги жумуш.
Бул пландоочунун натыйжасы төмөнкү натыйжа болот: ((120-0)+(20-10)+(30-10))/3=50. Ошентип, мындай пландоочу биздин милдеттерибиз үчүн дагы оптималдуу болуп калат.
Метрикалык жооп берүү убактысы
Ошентип, эгерде биз тапшырмалардын иштөө убактысын билсек жана бул тапшырмалар CPU гана колдонсо, STCF эң жакшы чечим болот. Ал эми алгачкы мезгилде бир жолу, бул алгоритмдер абдан жакшы иштеген. Бирок, колдонуучу азыр убактысынын көбүн терминалда өткөрөт жана жемиштүү интерактивдүү тажрыйбаны күтөт. Ошентип, жаңы метрика пайда болду - жооп убактысы (жооп).
Жооп убактысы төмөнкүдөй эсептелет:
Tresponse=Tfirstrun-Tarrival
Ошентип, мурунку мисал үчүн жооп убактысы: A=0, B=0, C=10 (abg=3,33) болот.
Ал эми STCF алгоритми бир эле учурда 3 тапшырма келген кырдаалда анчалык жакшы эмес экени көрүнүп турат - ал кичинекей тапшырмалар толугу менен аяктаганга чейин күтүүгө туура келет. Ошентип, алгоритм айлануу убактысынын көрсөткүчү үчүн жакшы, бирок интерактивдүүлүк метрикасы үчүн жаман. Элестетиңиз, эгер сиз терминалда отуруп редакторго символдорду терүүгө аракет кылып жатсаңыз жана 10 секунддан ашык күтүшүңүз керек, анткени CPU башка тапшырманы аткарып жаткан. Бул абдан жагымдуу эмес.
Ошентип, биз дагы бир көйгөйгө туш болдук - жооп берүү убактысына сезимтал болгон пландаштыргычты кантип түзө алабыз?
Робин Раунд
Бул маселени чечүү үчүн алгоритм иштелип чыккан Робин Раунд (RR). Негизги идея абдан жөнөкөй: тапшырмаларды алар аткарылганга чейин аткаруунун ордуна, биз тапшырманы белгилүү бир убакытка (убакыт кесими деп аталат) аткарып, андан кийин кезектеги башка тапшырмага өтөбүз. Алгоритм өз ишин бардык тапшырмалар аткарылмайынча кайталайт. Бул учурда, программанын иштөө убактысы таймер процессти үзгүлтүккө учураткандан кийин убакыттын бир эсе көп болушу керек. Мисалы, таймер процессти ар бир x=10ms үзгүлтүккө учуратса, анда процессти аткаруу терезесинин өлчөмү 10го эселенген жана 10,20 же x*10 болушу керек.
Бир мисалды карап көрөлү: ABC тапшырмалары системага бир эле учурда келип, алардын ар бири 5 секунддан иштөөнү каалайт. SJF алгоритми башкасын баштоодон мурун ар бир тапшырманы аягына чыгарат. Ал эми, ишке киргизүү терезеси = 1s менен RR алгоритми төмөнкүдөй тапшырмаларды аткарат (4.3-сүрөт):
(SJF Кайра (Жооп берүү убактысы үчүн начар)
(Раунд Робин (Жооп берүү убактысы үчүн жакшы)
RR алгоритми үчүн орточо жооп убактысы (0+1+2)/3=1, ал эми SJF үчүн (0+5+10)/3=5.
Убакыт терезеси RR үчүн абдан маанилүү параметр болуп саналат деп болжолдоо логикалык жактан туура, ал канчалык кичине болсо, жооп берүү убактысы ошончолук жогору болот. Бирок, сиз аны өтө кичине кылбашыңыз керек, анткени контекстти алмаштыруу убактысы да жалпы аткарууда роль ойнойт. Ошентип, аткаруу терезесинин убактысын тандоо ОС архитектору тарабынан белгиленет жана анда аткарылышы пландаштырылган милдеттерге жараша болот. Контекстти которуштуруу - бул убакытты текке кетирүүчү жалгыз кызматтык операция эмес - иштеп жаткан программа башка көптөгөн нерселерде, мисалы, ар кандай кэштерде иштейт жана ар бир коммутатор менен бул чөйрөнү сактап жана калыбына келтириш керек, бул дагы көп нерсени талап кылат. убакыт.
Эгерде биз жооп убактысынын метрикасы жөнүндө гана сөз кылсак, RR - эң сонун пландоочу. Бирок бул алгоритм менен тапшырманы аткаруу убактысынын метрикасы кандай болот? Жогорудагы мисалды карап көрөлү, качан A, B, C = 5s иштөө убактысы жана ошол эле учурда келгенде. А тапшырмасы 13, В 14, С 15 секундада аяктайт жана орточо аткаруу убактысы 14 секунд болот. Ошентип, RR жүгүртүү метрикасы үчүн эң начар алгоритм болуп саналат.
Жалпысынан алганда, ар кандай RR тибиндеги алгоритм адилеттүү болуп саналат; ал бардык процесстердин ортосунда CPU убактысын бирдей бөлөт. Ошентип, бул көрсөткүчтөр дайыма бири-бири менен карама-каршы келет.
Ошентип, бизде бир нече карама-каршы алгоритмдер бар жана ошол эле учурда дагы эле бир нече божомолдор бар - тапшырма убактысы белгилүү жана тапшырма CPU гана колдонот.
I/O менен аралаштыруу
Биринчиден, процесс CPU гана колдонот деген 4-божомолду алып салалы; албетте, андай эмес жана процесстер башка жабдууларга кире алат.
Кандайдыр бир процесс I/O операциясын талап кылган учурда, процесс I/O бүтүшүн күтүп, блоктолгон абалга кирет. Эгерде киргизүү/чыгаруу катуу дискке жөнөтүлсө, анда мындай операция бир нече мс же андан да көп убакытка созулушу мүмкүн жана процессор ушул учурда иштебей калат. Бул убакыттын ичинде пландоочу процессорду каалаган башка процесс менен ээлей алат. Пландоочу кабыл алышы керек болгон кийинки чечим - бул процесс өзүнүн киргизүү/чыгарылышын аяктаганда. Бул болгондо, үзгүлтүк пайда болот жана ОС I/O чакырган процессти даяр абалга коет.
Келгиле, бир нече көйгөйлөрдүн мисалын карап көрөлү. Алардын ар бири 50ms CPU убактысын талап кылат. Бирок, биринчиси киргизүү/чыгарууга ар 10 мс сайын жетет (ал да ар 10 мс аткарылат). Ал эми В процесси киргизүү/чыгаруусуз 50 мс процессорду колдонот.
Бул мисалда биз STCF пландоочусун колдонобуз. Эгерде А сыяктуу процесс иштетилсе, пландоочу өзүн кандай аткарат? Ал төмөнкүлөрдү аткарат: адегенде А процессин толук иштеп чыгат, андан кийин Б процессин иштеп чыгат.
Бул маселени чечүүнүн салттуу ыкмасы А процессинин ар бир 10 мс кошумча тапшырмасын өзүнчө тапшырма катары кароо. Ошентип, STJF алгоритми менен баштаганда, 50 мс тапшырмасы менен 10 мс тапшырманын ортосундагы тандоо ачык көрүнүп турат. Андан кийин, А кошумча тапшырмасы аяктагандан кийин, B процесси жана киргизүү/чыгаруу ишке киргизилет. Киргизүү/чыгаруу аяктагандан кийин, В процессинин ордуна 10 мс А процессин кайра баштоо адатка айланган. Ушундай жол менен кайталанууну ишке ашырууга болот, мында CPU башка процесс тарабынан колдонулат, ал эми биринчи процесс күтүүдө. I/O. Натыйжада, система жакшыраак пайдаланылат - интерактивдүү процесстер киргизүү/чыгарууну күтүп турган учурда, процессордо башка процесстерди аткарууга болот.
Oracle азыр жок
Эми тапшырманы аткаруу убактысы белгилүү деген ойдон арылууга аракет кылалы. Бул жалпысынан тизмедеги эң жаман жана реалдуу эмес божомол. Чындыгында, кадимки жөнөкөй ОСте, ОС өзү адатта тапшырмалардын аткарылуу убактысы жөнүндө өтө аз билет, андыктан тапшырманы аткарууга канча убакыт кетээрин билбей туруп кантип пландоочу түзө аласыз? Балким, биз бул көйгөйдү чечүү үчүн RR принциптерин колдоно алабыз?
жыйынтык
Биз тапшырмаларды пландаштыруунун негизги идеяларын карап чыктык жана пландоочулардын 2 үй-бүлөсүн карадык. Биринчиси эң кыска тапшырманы биринчи баштайт жана ошону менен иштин бүтүрүү убактысын көбөйтөт, ал эми экинчиси бардык тапшырмалардын ортосунда бирдей үзүлүп, жооп берүү убактысын көбөйтөт. Башка үй-бүлөнүн алгоритмдери жакшы болсо, эки алгоритм тең жаман. Биз ошондой эле CPU жана киргизүү/чыгаруучуну параллелдүү колдонуу натыйжалуулукту кантип жакшыртаарын карап чыктык, бирок OS кыраакылыгы менен көйгөйдү чечкен жокпуз. Ал эми кийинки сабакта биз жакынкы өткөндү караган жана келечекти болжолдоого аракет кылган пландоочуну карайбыз. Ал эми көп деңгээлдүү пикир кезеги деп аталат.
Source: www.habr.com