Операциялык системаларга киришүү
Эй Хабр! Мен сиздердин назарыңыздарга менин оюмча бир кызыктуу адабияттын бир катар макала-котормолорун келтиргим келет - OSTEP. Бул материалда Unix сыяктуу операциялык системалардын иши, тактап айтканда, процесстер, ар кандай пландоочулар, эс тутум жана заманбап ОСти түзгөн башка ушул сыяктуу компоненттер менен иштөө абдан терең талкууланат. Бардык материалдардын түп нускасын бул жерден көрө аласыз . Көңүл буруңуз, котормо профессионалдуу эмес (абдан эркин) жасалган, бирок мен жалпы маанини сактап калдым деп ишенем.
Бул тема боюнча лабораториялык иштерди бул жерден тапса болот:
Башка бөлүктөр:
Ошондой эле менин каналымды текшере аласыз =)
Пландоо: Көп деңгээлдүү пикир кезеги
Бул лекцияда биз эң белгилүү ыкмалардын бирин иштеп чыгуу көйгөйлөрү жөнүндө сүйлөшөбүз
пландаштыруу деп аталат Көп деңгээлдүү жооп кайтаруу кезеги (MLFQ). MLFQ пландоочусу биринчи жолу 1962-жылы Фернандо Дж. Корбато тарабынан аталган системада сүрөттөлгөн.
Шайкеш убакыт бөлүшүү системасы (CTSS). Бул эмгектер (анын ичинде кийинки иштер
Multics) кийин Тьюринг сыйлыгына көрсөтүлгөн. Пландоочу болгон
кийин жакшыртылган жана мурунтан эле табууга болот көрүнүшүн алган
кээ бир заманбап системалар.
MLFQ алгоритми бири-бирин кайталаган 2 негизги маселени чечүүгө аракет кылат.
Биринчиден, ал мурунку лекцияда талкуулангандай, эң көп кезектин башында баштоо ыкмасы менен оптималдаштырылган, кайра иштетүү убактысын оптималдаштырууга аракет кылат.
кыска тапшырмалар. Бирок, ОС тигил же бул процесс канча убакытка созуларын билбейт жана бул
SJF, STCF алгоритмдеринин иштеши үчүн зарыл билим. Экинчиден, MLFQ аракет кылат
системаны колдонуучулар үчүн (мисалы, отургандар үчүн жана
тапшырманы аткарууну күтүп жатканда экранды карап) жана ошону менен убакытты азайтыңыз
жооп. Тилекке каршы, RR сыяктуу алгоритмдер жооп берүү убактысын кыскартат, бирок
айлануу убактысынын метрикасына жаман таасирин тийгизет. Демек, биздин көйгөй: Кантип долбоорлоо
биздин талаптарга жооп бере турган пландаштыргыч жана ошол эле учурда эч нерсе билбейт
процесстин мүнөзү, жалпысынан? Пландоочу тапшырмалардын мүнөздөмөлөрүн кантип биле алат?
кайсынысын ишке киргизет жана ошону менен жакшыраак пландаштыруу чечимдерин кабыл алат?
Маселенин маңызы: Кемчиликсиз билимсиз тапшырмаларды коюуну кантип пландаштыруу керек?
Жооп убактысын бир эле учурда азайтуучу пландаштыргычты кантип иштеп чыгуу керек
интерактивдүү тапшырмалар үчүн жана ошол эле учурда билбестен иштөө убактысын азайтат
тапшырманы аткаруу убактысын билүү?
Эскертүү: мурунку окуялардан сабак алуу
MLFQ кезеги үйрөтүлгөн системанын эң сонун үлгүсү
келечекти алдын ала айтуу үчүн өткөн окуялар. Мындай ыкмалар көп кездешет
ОСте табылган (Жана информатиканын башка көптөгөн тармактары, анын ичинде филиалдар
аппараттык болжолдоолорду жана кэш алгоритмдерин). Окшош жөө жүрүштөр
милдеттердин жүрүм-турум фазалары болгондо жана ошону менен алдын ала айтууга болот.
Бирок, бул ыкма менен этият болуу керек, анткени алдын ала айтуу абдан оңой.
туура эмес болуп чыгып, системаны андан да жаман чечимдерди кабыл алууга алып келиши мүмкүн
такыр билимсиз болмок.
MLFQ: Негизги эрежелер
MLFQ алгоритминин негизги эрежелерин карап көрөлү. Жана бул алгоритмдин ишке ашырылышы да
бир нече бар, негизги ыкмалар окшош.
Биз карап чыга турган ишке ашырууда MLFQ бир нечеге ээ болот
өзүнчө кезектер, алардын ар бири ар кандай артыкчылыкка ээ болот. Каалаган убакта,
аткарууга даяр тапшырма ошол эле кезекте турат. MLFQ артыкчылыктарды колдонот,
аткаруу үчүн чуркап кайсы тапшырманы чечүү үчүн, б.а. жогорку менен милдет
биринчи кезекте артыкчылык (жогорку артыкчылыкка ээ кезектеги тапшырма) ишке киргизилет
кезек.
Албетте, белгилүү бир кезекте бирден ашык тапшырма болушу мүмкүн, ошондуктан
ошондуктан алар бирдей артыкчылыкка ээ болушат. Бул учурда механизм колдонулат
Бул милдеттердин арасында ишке киргизүү пландаштыруу үчүн RR.
Ошентип, биз MLFQ үчүн эки негизги эрежеге келет:
- 1-эреже: Приоритет(A) > Приоритет(B) болсо, А тапшырмасы аткарылат (Б иштебейт)
- 2-эреже: Приоритет(A) = Приоритет(B) болсо, A&B RR колдонуп башташат
Жогоруда айтылгандардын негизинде, MLFQ пландаштыруунун негизги элементтери болуп саналат
артыкчылыктар болуп саналат. Ар бирине белгиленген артыкчылык берүүнүн ордуна
тапшырма, MLFQ байкалган жүрүм-турумуна жараша өзүнүн артыкчылыктарын өзгөртөт.
Мисалы, клавиатура киргизүүнү күтүп жатканда CPU дайыма тапшырма токтоп калса,
MLFQ процесстин артыкчылыктуулугун сактап калат, анткени ушундай
интерактивдүү процесс иштеши керек. Эгерде, тескерисинче, милдет дайыма жана
CPU узак убакыт бою интенсивдүү болсо, MLFQ аны төмөндөтөт
артыкчылыктуу. Ошентип, MLFQ процесстердин жүрүм-турумун алар иштеп жаткан учурда изилдейт.
жана жүрүм-турумдарды колдонуу.
Келгиле, бир убакта кезектер кандай болушу мүмкүн экенине мисал келтирели
убакыт, анан сиз мындай нерсени аласыз:
Бул схемада 2 процесс А жана В эң жогорку артыкчылыкка ээ кезекте турат. Процесс
C ортосунда бир жерде, ал эми D процесси кезектин эң аягында. Жогоруда айтылгандарга ылайык
MLFQ алгоритминин сыпаттамасы менен пландоочу тапшырмаларды эң жогорку деңгээлде аткарат
RR боюнча артыкчылык, ал эми C, D тапшырмалары иштебей калат.
Албетте, статикалык сүрөт MLFQ кантип иштээри жөнүндө толук маалымат бербейт.
Бул сүрөт убакыттын өтүшү менен өзгөрөт так түшүнүү үчүн маанилүү.
1-аракет: артыкчылыкты кантип өзгөртүү керек
Бул учурда, сиз MLFQ артыкчылык деңгээлин кантип өзгөртө турганын чечишиңиз керек
тапшырма (ошондуктан тапшырманын кезектеги абалы) анын жашоо циклинде. үчүн
мунун, сиз иш жүрүшүн эстен чыгарбоо керек: белгилүү бир сумма
кыска иштөө убактысы менен интерактивдүү тапшырмалар (ошондуктан тез-тез чыгарылат
CPU) жана процессордун бардык иштөө убактысын колдонгон бир нече узак милдеттерди камтыйт
мындай тапшырмалар үчүн жооп убактысы маанилүү эмес. Ошентип, сиз биринчи аракет кыла аласыз
MLFQ алгоритмин төмөнкү эрежелер менен ишке ашырыңыз:
- Эреже 3: Тапшырма системага киргенде, ал эң көп болгон кезекке коюлат
- артыкчылык.
- Rule4a: Эгерде тапшырма бүтүндөй убакыт терезесин колдонсо, анда ал
- артыкчылык төмөндөйт.
- Rule4b: Эгерде тапшырма процессорду анын убакыт терезеси бүтө электе чыгарса, анда ал
- ошол эле артыкчылык менен кала берет.
1-мисал: Узак мөөнөттүү жалгыз тапшырма
Бул мисалдан көрүнүп тургандай, кабыл алууда тапшырма эң жогору коюлган
артыкчылык. 10ms убакыт терезесинен кийин, процесс артыкчылыктуу түрдө төмөндөйт.
пландоочу. Кийинки жолу терезеден кийин, тапшырма акыры төмөндөйт
системадагы эң төмөнкү артыкчылык, ал ошол жерде кала берет.
2-мисал: Кыска тапшырма алды
Эми келгиле, MLFQ SJFке кандайча жакындаганга аракет кыла турган мисалды карап көрөлү. Анда
Мисалы, эки тапшырма: А, бул дайыма узакка созулган иш
CPU жана B ээлейт, бул кыска интерактивдүү тапшырма. Дейли
Б тапшырмасы келгенде А бир топ убакыттан бери иштеп жүргөнүн.
Бул график сценарийдин натыйжаларын көрсөтөт. А тапшырмасы, бардык тапшырмалар сыяктуу,
CPU колдонуу эң ылдыйда болчу. B тапшырмасы T=100 убагында келет жана келет
эң артыкчылыктуу кезекке коюлган. Иштөө убактысы кыска болгондуктан,
ал акыркы кезекке жеткенге чейин бүтөт.
Бул мисалдан сиз алгоритмдин негизги максатын түшүнүшүңүз керек: алгоритм жок болгондуктан
узак же кыска тапшырманы билет, анда биринчи кезекте ал тапшырманы өзүнө алат
кыска жана ага эң чоң артыкчылык берет. Эгер чындап эле кыска иш болсо, анда
ал тез аткарылат, антпесе ал узак иш болсо, ал жай жылат
биринчи орунда турат жана жакында ал чындап эле узак иш экенин далилдейт
жооп талап кылат.
3-мисал: I/O жөнүндө эмне айтууга болот?
Эми I/O мисалын карап көрөлү. 4б эрежесинде айтылгандай,
эгерде процесс процессор убактысын толук пайдаланбастан процессорду бошотсо,
анда ал ошол эле артыкчылык децгээлинде кала берет. Бул эреженин максаты абдан жөнөкөй.
- эгерде интерактивдүү жумуш көп I/O аткарса, мисалы, күтүү
колдонуучунун баскычтарын же чычканды басып, мындай тапшырма процессорду бошотот
бөлүнгөн терезенин алдында. Мындай приоритеттүү милдетти калтыргыбыз келбейт,
жана ошентип ал ошол эле децгээлде кала берет.
Бул мисал алгоритмдин мындай процесстер менен кантип иштей турганын көрсөтөт - интерактивдүү B тапшырмасы, аны аткаруудан мурун 1 мс гана CPU керек.
I/O процесси жана процессорду ар дайым колдонгон узак жумуш А.
MLFQ B процессин эң жогорку артыкчылыкта сактайт
CPU бошотуу. Эгерде В интерактивдүү тапшырма болсо, анда бул учурда алгоритм жетти
анын максаты интерактивдүү тапшырмаларды тез ишке киргизүү болуп саналат.
Учурдагы MLFQ алгоритми менен көйгөйлөр
Мурунку мисалдарда биз MLFQнун негизги версиясын курганбыз. Анан ал окшойт
өз ишин жакшы жана адилеттүү аткарып, CPU убактысын ортосунда адилет бөлүштүрөт
узун тапшырмалар жана кыска тапшырмаларды же көп жеткиликтүү болгон тапшырмаларды аткарууга мүмкүндүк берет
тез иштетүү үчүн I/O. Тилекке каршы, бул ыкма бир нече камтыйт
олуттуу көйгөйлөр.
Биринчиден, ачкачылык көйгөйү: система көп интерактивдүү болсо
милдеттерди аткаруу үчүн, алар CPU убактысынын баарын жалмап коюшат, ошондуктан бир дагы көп убакыт талап кылынбайт
тапшырманы аткарууга мүмкүнчүлүк болбойт (алар ачка болушат).
Экинчиден, акылдуу колдонуучулар программаларын ушундай кылып жаза алышат
пландоочуну алдоо. Алдамчылык күчкө салып бир нерсе кылууда
процесске көбүрөөк CPU убактысын берүү үчүн пландаштыргыч. Алгоритм ошол
жогоруда сүрөттөлгөн мындай чабуулдарга абдан аялуу болуп саналат: убакыт терезеси иш жүзүндө чейин
кийин, сиз киргизүү/чыгаруу операциясын аткарышыңыз керек (айрымдарга, кайсы файл болбосун)
Ошентип, CPU боштондукка чыгат. Мындай жүрүм-турум ошол бойдон калууга мүмкүндүк берет
кезек өзү жана кайра CPU убактысынын көбүрөөк пайызын алат. Эгерде аткарылса
бул туура (мисалы, процессорду чыгарганга чейин терезе убактысынын 99% иштетүү),
мындай милдет жөн гана процессорду монополизациялай алат.
Акыр-аягы, программа убакыттын өтүшү менен өзүнүн жүрүм-турумун өзгөртө алат. Ошол милдеттерди
CPU колдонгон интерактивдүү боло алат. Биздин мисалда, окшош
тапшырмалар башкаларга окшоп пландоочудан туура мамиле жасабайт
(оригиналдуу) интерактивдүү тапшырмалар.
Аудиторияга суроо: заманбап дүйнөдө пландоочуга кандай чабуулдар жасалышы мүмкүн?
2-аракет: Артыкчылыкты жогорулатуу
Келгиле, эрежелерди өзгөртүүгө аракет кылалы жана көйгөйлөрдөн качсак болобу
ачарчылык. Муну камсыз кылуу үчүн эмне кылсак болот
CPU тапшырмалары өз убактысын алат (узак болбосо да).
Көйгөйдүн жөнөкөй чечими катары сиз мезгил-мезгили менен сунуштай аласыз
системасындагы бардык ушундай милдеттердин артыкчылыктуулугун жогорулатуу. Көп жолдору бар
Буга жетүү үчүн, мисалы, жөнөкөй нерсени ишке ашырууга аракет кылалы: которуу
бардык милдеттерди бир убакта эң жогорку артыкчылыкка, демек, жаңы эреже:
- Эреже5: Бир нече S мезгилинен кийин системадагы бардык тапшырмаларды эң жогорку кезекке өткөрүңүз.
Биздин жаңы эреже бир эле учурда эки маселени чечет. Биринчиден, процесстер
ачка калбоого кепилдик берилет: эң жогорку кезектеги тапшырмалар бөлүшөт
RR алгоритмине ылайык процессордун убактысы жана ошону менен бардык процесстер кабыл алынат
процессордун убактысы. Экинчиден, мурда колдонулган кандайдыр бир процесс болсо
процессор гана интерактивдүү болуп калат, ал эң чоңу менен кезекте калат
бир жолу эң жогорку артыкчылыкка түрткү алгандан кийин артыкчылык.
Мисалга карап көрөлү. Бул сценарийде бир процессти колдонууну карап көрөлү
CPU жана эки интерактивдүү, кыска процесс. Сүрөттүн сол тарабында, фигура артыкчылыктуу күчөтүүсүз жүрүм-турумду көрсөтүп турат, ошондуктан системага эки интерактивдүү тапшырма келгенден кийин узакка созулган тапшырма ачка баштайт. Оң жактагы сүрөттө, ар бир 50 мс приоритеттүү жогорулатуу аткарылат жана ошентип бардык процесстер процессордун убактысын алууга кепилдик берилет жана мезгил-мезгили менен ишке киргизилет. Бул учурда 50ms мисал катары алынган, чындыгында бул сан бир аз жогору.
Мезгил-мезгили менен көтөрүлүү убактысынын S кошулушуна алып келери айдан ачык
логикалык суроо: кандай маанини коюу керек? Татыктуулардын бири
система инженерлери Джон Оустерхоут системалардагы окшош чоңдуктарды voo-doo деп аташкан
туруктуу, анткени алар кандайдыр бир жол менен туура үчүн кара сыйкырды талап кылышкан
таасир. Жана, тилекке каршы, S мындай даамга ээ. Эгер сиз да маанини койсоңуз
чоң - узак милдеттер ачка калат. А эгер сиз аны өтө төмөн койсоңуз,
интерактивдүү тапшырмалар CPU убактысын туура кабыл албайт.
3-аракет: Жакшыраак эсепке алуу
Эми бизде дагы бир маселе бар: кантип чечиш керек
биздин пландоочубузду алдаганга уруксат бересизби? Бул мүмкүндүгү үчүн күнөөлүүлөр болуп саналат
4a, 4b эрежелери, алар процессорду бошотуу менен жумуштун артыкчылыктуулугун сактоого мүмкүндүк берет
белгиленген убакыт аяктаганга чейин. аны менен кантип күрөшүү керек?
Бул учурда чечим ар биринде CPU убактысын жакшыраак эсепке алуу деп эсептесе болот
MLFQ деңгээли. Программа колдонгон убакытты унутуунун ордуна
Бөлүнгөн интервал үчүн процессорду эске алып, аны сактоо керек. Андан кийин
процесс өзүнүн бөлүнгөн убактысын бүтүргөн, аны кийинкиге түшүрүү керек
артыкчылыктуу деңгээл. Эми процесс өз убактысын кандай пайдалана турганы маанилүү эмес - кантип
процессордо же чалуулардын жыйындысы катары тынымсыз эсептөө. Ошентип,
4-эреже төмөнкүдөй редакцияда баяндалсын:
- Эреже4: Тапшырма учурдагы кезекте өзүнүн бөлүнгөн убактысын бүтүргөндөн кийин (ал CPU канча жолу бошотконуна карабастан), мындай тапшырманын артыкчылыктуулугу төмөндөйт (ал кезектен ылдый жылат).
Келгиле, бир мисал карап көрөлү:
»
Сүрөт пландаштыргычты алдаганга аракет кылсаңыз, эмне болорун көрсөтөт
эгерде мурунку 4a эрежелери менен болсо, 4b сол жактагы жыйынтык болмок. Жаңы менен
эреже - натыйжа оң жакта. Коргоодон мурун, ар кандай процесс аяктаганга чейин I/O чакырышы мүмкүн жана
Ошентип, жүрүм-турумуна карабастан, коргоону иштеткенден кийин CPU үстөмдүк кылат
I/O, ал дагы эле кезекке түшүп калат жана ошентип абийирсиз боло албайт
CPU ресурстарын алуу.
MLFQ жакшыртуу жана башка маселелер
Жогорудагы жакшыртуулар менен жаңы көйгөйлөр пайда болот: негизгилеринин бири
суроолор - мындай пландаштыргычты кантип параметрлештирүү керек? Ошол. Канча болушу керек
кезектер? Кезекте турган программанын терезесинин көлөмү кандай болушу керек? Кантип
программасы көп учурда ачарчылыктан жана качуу үчүн артыкчылыктуу болушу керек
программанын жүрүм-турумунун өзгөрүшүн эске алуу үчүн? Бул суроолорго эч кандай жөнөкөй эмес
жооп жана жүктер жана кийинки конфигурациялар менен гана эксперименттер
пландоочу кээ бир канааттандырарлык баланска алып келиши мүмкүн.
Мисалы, көпчүлүк MLFQ ишке ашыруулар башка дайындоого мүмкүндүк берет
ар кандай кезектер үчүн убакыт аралыгы. Жогорку артыкчылыктуу кезектер адатта болот
кыска интервалдар. Бул кезектер интерактивдүү тапшырмалардан турат,
алардын ортосунда өтүү өтө сезгич жана 10 же андан аз болушу керек
Айым. Ал эми, аз артыкчылыктуу кезектер пайдаланган узакка созулган тапшырмалардан турат
CPU. Жана бул учурда, узак убакыт аралыгы абдан жакшы туура келет (100ms).
Бул мисалда жогорку артыкчылыктуу кезекте 2 иштеген 20 тапшырма бар
мс 10 мс терезелерге бөлүнгөн. Орто кезекте 40 мс (20 мс терезе) жана төмөнкү артыкчылыктуу кезекте
тапшырмалар өз ишин аяктаган кезекте убакыт терезеси 40ms болуп калды.
Solaris OS ичинде MLFQ ишке ашыруу убакыт бөлүшүү пландаштыруучулар классы болуп саналат.
Пландоочу таблицалардын топтомун камсыздайт, алар так кандай болушу керектигин аныктайт
анын өмүр бою жараяндын артыкчылыктуу өзгөртүү, өлчөмү кандай болушу керек
терезе бөлүштүрүлөт жана милдеттердин артыкчылыктарын канчалык көп көтөрүү керек. Администратор
система бул таблица менен өз ара аракеттенип, пландоочунун жүрүм-турумун жасай алат
башкача. Демейки боюнча, бул таблицада акырындык менен көбөйүү менен 60 кезек бар
терезе өлчөмү 20ms (жогорку артыкчылык) бир нече жүз мс чейин (төмөнкү артыкчылык), жана
ошондой эле секундасына бир жолу бардык тапшырмаларды күчөтүү менен.
Башка MLFQ пландаштыруучулар үстөлдү же кандайдыр бир конкреттүү колдонушпайт
Бул бөлүмдө сүрөттөлгөн эрежелер, тескерисинче, артыкчылыктарды колдонуп эсептешет
математикалык формулалар. Мисалы, FreeBSDдеги пландоочу формуланы колдонот
жараян канчалык негизинде учурдагы тапшырма артыкчылыкты эсептөө
CPU колдонгон. Мындан тышкары, CPU колдонуу убакыттын өтүшү менен чирип, жана ошентип
Ошентип, артыкчылыкты жогорулатуу жогоруда айтылгандан бир аз башкачараак. Бул ушундай
ажыроо алгоритмдери деп аталат. 7.1 версиясына карата FreeBSD ULE пландоочусун колдонот.
Акыр-аягы, көптөгөн пландоочулар башка өзгөчөлүктөргө ээ. Мисалы, кээ бир
пландаштыруучулар иштөө тутумунун иштеши үчүн жогорку деңгээлдерди сакташат жана ошентип
Ошентип, эч бир колдонуучу процесси эң жогорку артыкчылыкка ээ боло албайт
системасы. Кээ бир системалар жардам берүү үчүн кеңеш берүүгө мүмкүнчүлүк берет
туура приоритетти пландаштыруучу. Мисалы, буйрукту колдонуу жакшы
сиз тапшырманын артыкчылыктуулугун жогорулатып же азайтып, ошону менен көбөйтүп же азайта аласыз
CPU убактысы үчүн программанын мүмкүнчүлүктөрүн азайтат.
MLFQ: Кыскача маалымат
Биз MLFQ деп аталган пландоо ыкмасын сүрөттөп бердик. Анын аты
иштөө принцибинде жыйынтыкталган - ал бир нече кезекке ээ жана пикирди колдонот
бир ишти артыкчылыктуу кылуу.
Эрежелердин акыркы формасы төмөнкүдөй болот:
- Эреже1: Приоритет(A) > Приоритет(B) болсо, А тапшырмасы аткарылат (Б иштебейт)
- Эреже2: Приоритет(A) = Приоритет(B) болсо, A&B RR колдонуп башташат
- Эреже3: Тапшырма системага киргенде, ал эң артыкчылыктуу кезекке коюлат.
- Эреже4: Тапшырма учурдагы кезекте өзүнүн бөлүнгөн убактысын бүтүргөндөн кийин (ал CPU канча жолу бошотконуна карабастан), мындай тапшырманын артыкчылыктуулугу төмөндөйт (ал кезектен ылдый жылат).
- Эреже5: Бир нече S мезгилинен кийин системадагы бардык тапшырмаларды эң жогорку кезекке өткөрүңүз.
MLFQ төмөнкү себептерден улам кызыктуу - билимди талап кылуунун ордуна
Алдын ала тапшырманын мүнөзү, алгоритм тапшырманын мурунку жүрүм-турумун үйрөнүп, топтойт
приоритеттерге жараша. Ошентип, ал бир эле учурда эки отургучка отурууга аракет кылат - кичинекей тапшырмаларды аткарууга жетүү үчүн (SJF, STCF) жана чынчылдык менен узун иштерди аткаруу үчүн,
CPU жүктөө жумуштары. Ошондуктан, көптөгөн системалар, анын ичинде BSD жана алардын туундулары,
Solaris, Windows, Mac пландоочу катары алгоритмдин кандайдыр бир түрүн колдонушат
MLFQ базалык көрсөткүч катары.
Кошумча материалдар:
- (эсептөө)
Source: www.habr.com