Муқаддима ба системаҳои оператсионӣ
Салом, Хабр! Мехохам ба диццати шумо як катор макола-тарчимахои як адабиётро пешкаш намоям, ки ба назари ман — ОСТЕП. Дар ин мавод кори системаҳои оператсионии ба unix монанд, яъне кор бо равандҳо, графикҳои гуногун, хотира ва дигар ҷузъҳои шабеҳ, ки ОС-и муосирро ташкил медиҳанд, хеле амиқ омӯхта мешавад. Шумо метавонед асли ҳамаи маводҳоро дар ин ҷо бинед . Лутфан қайд кунед, ки тарҷума ғайрикасбӣ (хеле озодона) анҷом дода шудааст, аммо ман умедворам, ки ман маънои умумиро нигоҳ доштам.
Корҳои лабораторӣ дар ин мавзӯъро дар ин ҷо пайдо кардан мумкин аст:
Қисмҳои дигар:
Шумо инчунин метавонед канали маро дар ин ҷо санҷед =)
Муқаддима ба нақшакаш
Моҳияти масъала: Чӣ тавр таҳияи сиёсати банақшагирӣ
Чаҳорчӯбаҳои асосии сиёсати банақшагириро чӣ гуна бояд тарҳрезӣ кард? Фарзияҳои асосӣ бояд чӣ гуна бошанд? Кадом нишондиҳандаҳо муҳиманд? Кадом усулҳои асосӣ дар системаҳои ҳисоббарории ибтидоӣ истифода мешуданд?
Фарзияҳои сарбории корӣ
Пеш аз баррасии сиёсатҳои имконпазир, биёед аввал дар бораи равандҳое, ки дар система кор мекунанд, як чанд тафсилоти соддакунандаро анҷом диҳем, ки онҳоро ба таври дастаҷамъӣ меноманд. сарбории кор. Муайян кардани сарбории корӣ як қисми муҳими сиёсатҳои сохтмонӣ аст ва ҳар қадаре, ки шумо дар бораи сарбории кор донед, ҳамон қадар сиёсатро беҳтар навишта метавонед.
Биёед тахминҳои зеринро дар бораи равандҳое, ки дар система кор мекунанд, баъзан онро низ даъват мекунем љойњои (вазифаҳо). Қариб ҳамаи ин тахминҳо воқеӣ нестанд, балки барои рушди тафаккур заруранд.
- Ҳар як вазифа барои ҳамон вақт иҷро мешавад,
- Ҳама вазифаҳо дар як вақт гузошта мешаванд,
- Вазифаи гузошташуда то анҷоми он кор мекунад,
- Ҳама вазифаҳо танҳо CPU истифода мебаранд,
- Мухлати ичрои хар як кор маълум аст.
Метрикҳои банақшагирӣ
Илова ба баъзе фарзияҳо дар бораи сарборӣ, асбоби дигар барои муқоисаи сиёсатҳои гуногуни банақшагирӣ лозим аст: метрикаи нақшакаш. Метрик танҳо як андозагирии чизест. Як қатор нишондиҳандаҳо мавҷуданд, ки метавонанд барои муқоисаи нақшакашҳо истифода шаванд.
Масалан, мо як метри номро истифода хоҳем кард вақти гардиш (вақти баргардонидан). Вақти иҷрои вазифа ҳамчун фарқияти байни вақти иҷрои вазифа ва вақти расидани супориш дар система муайян карда мешавад.
Бозгашт = Анҷом - расидан
Азбаски мо фарз кардем, ки ҳама вазифаҳо дар як вақт меоянд, пас Ta=0 ва ҳамин тавр Tt=Tc. Вақте ки мо тахминҳои дар боло зикршударо тағир медиҳем, ин арзиш табиатан тағир меёбад.
Дигар нишондиҳанда - адолат (инсоф, ростқавлӣ). Маҳсулнокӣ ва адолат аксар вақт хусусиятҳои банақшагирӣ ба ҳам мухолифанд. Масалан, банақшагир метавонад иҷроишро оптимизатсия кунад, аммо бо арзиши интизории иҷрои дигар вазифаҳо ва ҳамин тавр адолатро коҳиш медиҳад.
АВВАЛ ДАР АВВАЛ (FIFO)
Алгоритм асоситарине, ки мо онро амалӣ карда метавонем, FIFO ё номида мешавад аввал омада (даромад), аввалин хизмат (берун). Ин алгоритм якчанд афзалиятҳо дорад: татбиқи он хеле осон аст ва он ба ҳамаи тахминҳои мо мувофиқат мекунад ва корро хеле хуб иҷро мекунад.
Биёед як мисоли оддиро дида бароем. Фарз мекунем, ки дар як вақт 3 вазифа гузошта шуд. Аммо биёед фарз кунем, ки вазифаи А каме пештар аз ҳамаи дигарон расид, аз ин рӯ он дар рӯйхати иҷроишҳо нисбат ба дигарон пештар пайдо мешавад, ба мисли B нисбат ба C. Фарз мекунем, ки ҳар кадоми онҳо барои 10 сония иҷро мешаванд. Дар ин ҳолат вақти миёна барои иҷрои ин вазифаҳо чӣ қадар хоҳад буд?
Бо ҳисоб кардани арзишҳо - 10+20+30 ва ба 3 тақсим кардан, мо вақти миёнаи иҷрои барномаро ба 20 сония баробар мекунем.
Акнун биёед кӯшиш кунем, ки тахминҳои худро тағир диҳем. Махсусан, фарзияи 1 ва аз ин рӯ, мо дигар фарз нахоҳем кард, ки ҳар як супориш барои иҷрои якхела вақтро мегирад. FIFO ин дафъа чӣ гуна кор хоҳад кард?
Тавре маълум мешавад, вақтҳои гуногуни иҷрои вазифаҳо ба ҳосилнокии алгоритми FIFO таъсири бениҳоят манфӣ мерасонанд. Фарз мекунем, ки вазифаи А барои анҷом додани он 100 сония вақт лозим аст, дар ҳоле ки B ва C ҳар кадоме 10 сонияро мегиранд.
Тавре ки аз расм дида мешавад, вақти миёнаи система (100+110+120)/3=110 мешавад. Ин таъсир номида мешавад таъсири конвой, вақте ки баъзе истеъмолкунандагони кӯтоҳмуддати захира пас аз истеъмолкунандаи вазнин навбат меистанд. Мисли навбат дар мағозаи хӯрокворӣ, вақте ки дар назди шумо як мизоҷ бо аробаи пур аст. Беҳтарин роҳи ҳалли мушкилот ин аст, ки кӯшиш кунед, ки кассаро иваз кунед ё истироҳат кунед ва чуқур нафас кашед.
Аввалин кори кӯтоҳтарин
Оё имкон дорад, ки чунин вазъиятро бо равандҳои вазнин ҳал кард? Албатта. Навъи дигари банақшагирӣ номида мешавадАввалин кори кӯтоҳтарин (SJF). Алгоритми он низ хеле ибтидоӣ аст - тавре ки аз ном бармеояд, кӯтоҳтарин вазифаҳо паси дигар оғоз карда мешаванд.
Дар ин мисол, натиҷаи иҷроиши ҳамон равандҳо беҳбуди вақти миёнаи коркарди барнома хоҳад буд ва он ба баробар хоҳад буд. 50 ба ҷои 110, ки ин кариб 2 баробар бехтар аст.
Ҳамин тариқ, барои фарзияи додашуда, ки ҳама вазифаҳо дар як вақт меоянд, алгоритми SJF беҳтарин алгоритми беҳтарин ба назар мерасад. Бо вуҷуди ин, тахминҳои мо ҳанӯз воқеӣ нестанд. Ин дафъа мо фарзияи 2-ро тағир медиҳем ва ин дафъа тасаввур мекунем, ки вазифаҳо метавонанд дар ҳама вақт мавҷуд бошанд, на ҳама дар як вақт. Ин ба кадом мушкилот оварда мерасонад?
Биёед тасаввур кунем, ки вазифаи A (100c) аввал меояд ва ба иҷроиш оғоз мекунад. Ҳангоми t=10, вазифаҳои B ва C меоянд, ки ҳар яки онҳо 10 сонияро дар бар мегиранд. Ҳамин тавр, вақти миёнаи иҷро (100+(110-10)+(120-10))3 = 103 аст. Нақшасоз барои беҳтар кардани ин чӣ кор карда метавонад?
Мӯҳлати кӯтоҳтарин барои анҷоми аввал (STCF)
Барои беҳтар кардани вазъият, мо фарзияи 3-ро дар бораи он, ки барнома оғоз шудааст ва то ба итмом мерасад, сарфи назар мекунем. Илова бар ин, мо ба дастгирии сахтафзор ниёз дорем ва, тавре ки шумо гумон мекунед, мо истифода хоҳем кард вақтсанҷ ба кори ичрошаванда халал расондан ва гузариши контекст. Ҳамин тариқ, банақшагир метавонад дар лаҳзаи расидани вазифаҳои B, C кореро анҷом диҳад - иҷрои вазифаи Аро қатъ кунад ва вазифаҳои B ва C-ро ба коркард гузорад ва пас аз анҷоми онҳо раванди Аро идома диҳад. Чунин банақшагир номида мешавад. STCFё Аввалин кори пешгирикунанда.
Натиҷаи ин тарҳрезӣ натиҷаи зерин хоҳад буд: ((120-0)+(20-10)+(30-10))/3=50. Ҳамин тариқ, чунин нақшакаш барои вазифаҳои мо боз ҳам оптималтар мегардад.
Вақти вокуниши метрӣ
Ҳамин тариқ, агар мо вақти иҷрои вазифаҳоро донем ва ин вазифаҳо танҳо CPU-ро истифода мебаранд, STCF беҳтарин роҳи ҳалли он хоҳад буд. Ва як бор дар замонҳои аввал, ин алгоритмҳо хеле хуб кор мекарданд. Бо вуҷуди ин, корбар ҳоло бештари вақти худро дар терминал мегузаронад ва интизори таҷрибаи пурсамари интерактивӣ аст. Ҳамин тариқ, як метрикаи нав таваллуд шуд - вақти вокуниш (ҷавоб).
Вақти ҷавоб ба таври зерин ҳисоб карда мешавад:
Муқовимат = Таърих - расидан
Ҳамин тариқ, барои мисоли қаблӣ, вақти вокуниш чунин хоҳад буд: A=0, B=0, C=10 (abg=3,33).
Ва маълум мешавад, ки алгоритми STCF дар вазъияте, ки дар як вақт 3 вазифа меоянд, он қадар хуб нест - он бояд интизор шавад, ки вазифаҳои хурд пурра иҷро шаванд. Ҳамин тавр, алгоритм барои метрикаи вақти гардиш хуб аст, аммо барои метрикаи интерактивӣ бад аст. Тасаввур кунед, ки агар шумо дар терминал нишастаед, ки ҳарфҳоро ба муҳаррир ворид кунед ва бояд беш аз 10 сония интизор шавед, зеро ягон вазифаи дигар CPU-ро мегирад. Ин хеле гуворо нест.
Пас, мо бо мушкилоти дигар рӯ ба рӯ мешавем - чӣ гуна мо метавонем нақшасозеро созем, ки ба вақти посух ҳассос бошад?
Робин мудаввар
Барои ҳалли ин масъала алгоритме таҳия шудааст Робин мудаввар (RR). Идеяи асосӣ хеле содда аст: ба ҷои иҷро кардани супоришҳо то анҷоми онҳо, мо супоришро дар муддати муайян иҷро мекунем (бо номи вақт бурида мешавад) ва сипас аз навбат ба вазифаи дигар мегузарем. Алгоритм кори худро то анҷоми ҳама вазифаҳо такрор мекунад. Дар ин ҳолат, вақти иҷрои барнома бояд чанд вақт бошад, ки пас аз он вақтсанҷ равандро қатъ мекунад. Масалан, агар таймер равандро ҳар x=10ms қатъ кунад, он гоҳ андозаи равзанаи иҷрои раванд бояд ба 10 баробар бошад ва 10,20 ё x*10 бошад.
Биёед як мисолро дида бароем: Вазифаҳои ABC ҳамзамон ба система меоянд ва ҳар кадоми онҳо мехоҳанд 5 сония кор кунанд. Алгоритми SJF ҳар як вазифаро пеш аз оғози кори дигар анҷом медиҳад. Баръакси ин, алгоритми RR бо равзанаи оғозёбӣ = 1s супоришҳоро ба таври зерин иҷро мекунад (расми 4.3):
(Боз SJF (Бад барои вақти вокуниш)
(Робин даври (Барои вақти вокуниш хуб)
Вақти миёнаи посух барои алгоритми RR (0+1+2)/3=1, дар ҳоле ки барои SJF (0+5+10)/3=5.
Фарз кардан мантиқ аст, ки равзанаи вақт як параметри хеле муҳим барои RR мебошад; ҳар қадар ки он хурдтар бошад, вақти вокуниш ҳамон қадар зиёд мешавад. Аммо, шумо набояд онро хеле хурд кунед, зеро вақти гузариши контекст низ дар иҷрои умумӣ нақш мебозад. Ҳамин тариқ, интихоби вақти равзанаи иҷро аз ҷониби меъмори ОС муқаррар карда мешавад ва аз вазифаҳое, ки дар он иҷро мешаванд, вобаста аст. Гузариш контексти ягона амалиёти хидматрасоние нест, ки вақтро беҳуда сарф мекунад - барномаи иҷрошаванда дар бисёр чизҳои дигар, масалан, кэшҳои гуногун кор мекунад ва бо ҳар як коммутатор ин муҳити зистро ҳифз ва барқарор кардан лозим аст, ки он метавонад миқдори зиёди вақтро талаб кунад. вақт.
RR як нақшаи олӣ аст, агар мо танҳо дар бораи метрикаи вақти вокуниш сухан ронем. Аммо метрикаи вақти иҷрои вазифа бо ин алгоритм чӣ гуна рафтор хоҳад кард? Мисоли дар боло зикршударо дида бароед, вақте ки вақти кори A, B, C = 5s ва дар як вақт меоянд. Вазифаи А дар соати 13, В соати 14, C дар соати 15 сония ба охир мерасад ва вақти миёнаи коркард 14 сония хоҳад буд. Ҳамин тариқ, RR алгоритми бадтарин барои метрикаи гардиш аст.
Ба ибораи умумӣ, ҳама гуна алгоритми навъи RR одилона аст; он вақти CPU-ро дар байни ҳамаи равандҳо баробар тақсим мекунад. Ва аз ин рӯ, ин нишондиҳандаҳо доимо бо ҳамдигар мухолифанд.
Ҳамин тариқ, мо якчанд алгоритмҳои муқобил дорем ва дар айни замон якчанд фарзияҳо боқӣ мондаанд - ки вақти кор маълум аст ва вазифа танҳо CPU-ро истифода мебарад.
Омехта бо I/O
Пеш аз ҳама, биёед фарзияи 4-ро хориҷ кунем, ки раванд танҳо CPU-ро истифода мебарад; Табиист, ки ин тавр нест ва равандҳо метавонанд ба таҷҳизоти дигар дастрасӣ пайдо кунанд.
Лаҳзае, ки ягон раванд амалиёти вуруд/баро талаб мекунад, раванд ба ҳолати басташуда ворид мешавад ва интизори ба итмом расидани В/Х мешавад. Агар воридот ба диски сахт фиристода шавад, он гоҳ ин гуна амалиёт метавонад то якчанд мс ва бештар аз он вақтро дар бар гирад ва протсессори мазкур дар айни замон бекор мемонад. Дар ин муддат нақшасоз метавонад протсессорро бо ягон раванди дигар ишғол кунад. Қарори навбатӣ, ки нақшасоз бояд қабул кунад, ин аст, ки раванд I/O-ро ба анҷом мерасонад. Вақте ки ин рӯй медиҳад, қатъ мешавад ва ОС равандеро, ки I/O-ро даъват кардааст, ба ҳолати омода мегузорад.
Биёед мисоли якчанд вазифаҳоро дида бароем. Ҳар яке аз онҳо 50ms вақти CPU талаб мекунад. Бо вуҷуди ин, аввалинаш ҳар 10 мс ба воридот / баромад дастрас мешавад (он низ ҳар 10 мс иҷро карда мешавад). Ва раванди B танҳо протсессори 50ms-ро бидуни вуруд / баромад истифода мебарад.
Дар ин мисол мо нақшаи STCF-ро истифода хоҳем бурд. Агар дар он раванд ба монанди A оғоз шавад, нақшасоз чӣ гуна рафтор мекунад? Вай чунин корхоро ичро мекунад: аввал процесси А-ро пурра кор карда мебарояд ва баъд процесси Б.
Усули анъанавии ҳалли ин мушкилот ин аст, ки ҳар як зервазифаи 10 мси раванди А ҳамчун вазифаи алоҳида баррасӣ карда шавад. Ҳамин тариқ, ҳангоми оғоз кардани алгоритми STJF, интихоби байни вазифаи 50 ms ва вазифаи 10 ms аён аст. Сипас, вақте ки зервазифаи A анҷом меёбад, раванди B ва I/O оғоз мешавад. Пас аз ба итмом расидани вуруд/берород, ба ҷои раванди B дубора оғоз кардани раванди 10ms A одат мешавад. Бо ин роҳ метавон такрори такрориро амалӣ кард, ки дар он CPU аз ҷониби як раванди дигар истифода мешавад, дар ҳоле ки протсессори аввал интизори он аст. I/O. Ва дар натиҷа, система беҳтар истифода мешавад - дар айни замон, ки равандҳои интерактивӣ интизори вуруд / баромад мебошанд, дар протсессор равандҳои дигарро иҷро кардан мумкин аст.
Oracle дигар нест
Акнун биёед кушиш кунем, ки аз тахмине, ки мухлати ичрои супориш маълум аст, халос шавем. Ин одатан бадтарин ва ғайривоқеӣтарин тахмин дар тамоми рӯйхат аст. Дарвоқеъ, дар ОС-и миёнаи оддӣ, худи ОС одатан дар бораи вақти иҷрои вазифаҳо хеле кам медонад, пас чӣ гуна шумо метавонед нақшасозро бидуни донед, ки иҷрои вазифа чӣ қадар вақт мегирад? Шояд мо метавонем баъзе принсипҳои RR-ро барои ҳалли ин мушкилот истифода барем?
Натиҷа
Мо ба ғояҳои асосии банақшагирии вазифаҳо назар карда, ба 2 оилаи нақшакашҳо назар кардем. Аввалин вазифаи кӯтоҳтаринро оғоз мекунад ва ба ин васила вақти коркардро зиёд мекунад, дуюмӣ бошад, дар байни ҳама вазифаҳо баробар канда мешавад ва вақти ҷавобро зиёд мекунад. Ҳарду алгоритмҳо бад ҳастанд, ки алгоритмҳои оилаи дигар хубанд. Мо инчунин ба он дидем, ки чӣ гуна истифодаи мувозии CPU ва I/O метавонад корҳоро беҳтар кунад, аммо мушкилотро бо равшании OS ҳал накард. Ва дар дарси оянда мо ба нақшакаше, ки ба гузаштаи наздик назар мекунад ва ояндаро пешгӯӣ карданӣ мешавад, дида мебароем. Ва он навбати бисёрсатҳии бозгашт номида мешавад.
Манбаъ: will.com