Операциялық жүйелермен таныстыру
Эй Хабр! Мен сіздердің назарларыңызға менің ойымша, бір қызықты әдебиеттің аудармалары – OSTEP мақалалар топтамасын ұсынғым келеді. Бұл материалда UNIX тәрізді операциялық жүйелердің жұмысы, атап айтқанда, қазіргі ОЖ құрайтын процестермен, әртүрлі жоспарлаушылармен, жадпен және басқа ұқсас компоненттермен жұмыс өте терең қарастырылады. Мұнда сіз барлық материалдардың түпнұсқасын көре аласыз . Аударма кәсіби емес (өте еркін) жасалғанын ескеріңіз, бірақ мен жалпы мағынаны сақтап қалдым деп үміттенемін.
Осы тақырып бойынша зертханалық жұмысты мына жерден табуға болады:
Басқа бөліктер:
Сондай-ақ менің арнамды мына жерден көре аласыз =)
Жоспарлағышқа кіріспе
Мәселенің мәні: Жоспарлаушы саясатын қалай жасауға болады
Негізгі жоспарлаушы саясат шеңберлері қалай жасалуы керек? Негізгі болжамдар қандай болуы керек? Қандай көрсеткіштер маңызды? Алғашқы есептеу жүйелерінде қандай негізгі әдістер қолданылды?
Жұмыс жүктемесінің болжамдары
Ықтимал саясаттарды талқыламас бұрын, алдымен жүйеде жұмыс істейтін процестер туралы бірнеше жеңілдететін шегіністерді жасайық. жұмыс жүктемесі. Жұмыс жүктемесін анықтау саясаттарды құрудың маңызды бөлігі болып табылады және жұмыс жүктемесі туралы көбірек білсеңіз, саясатты соғұрлым жақсы жаза аласыз.
Жүйеде жұмыс істейтін, кейде сондай-ақ деп аталатын процестер туралы келесі жорамалдар жасайық жұмыс орны (тапсырмалар). Бұл болжамдардың барлығы дерлік шындыққа жанаспайды, бірақ ойдың дамуы үшін қажет.
- Әрбір тапсырма бірдей уақыт көлемінде орындалады,
- Барлық тапсырмалар бір уақытта қойылады,
- Берілген тапсырма аяқталғанша жұмыс істейді,
- Барлық тапсырмалар тек процессорды пайдаланады,
- Әрбір тапсырманың орындалу уақыты белгілі.
Жоспарлаушы көрсеткіштері
Жүктемеге қатысты кейбір болжамдарға қоса, әртүрлі жоспарлау саясаттарын салыстыруға арналған басқа құрал қажет: жоспарлаушы метрикасы. Метрика бір нәрсенің кейбір өлшемі ғана. Жоспарлаушыларды салыстыру үшін пайдалануға болатын бірқатар көрсеткіштер бар.
Мысалы, біз деп аталатын метриканы қолданамыз айналым уақыты (өңдеу уақыты). Тапсырманы орындау уақыты тапсырманың орындалу уақыты мен жүйедегі тапсырманың келу уақыты арасындағы айырмашылық ретінде анықталады.
Tturnaround=TCompletion−Tarrival
Біз барлық тапсырмалар бір уақытта келді деп есептегендіктен, Ta=0 және осылайша Tt=Tc. Бұл мән жоғарыдағы болжамдарды өзгерткен кезде табиғи түрде өзгереді.
Басқа көрсеткіш - әділдік (әділдік, адалдық). Өнімділік пен әділдік жоспарлауда жиі қарама-қарсы сипаттамалар болып табылады. Мысалы, жоспарлаушы өнімділікті оңтайландыруы мүмкін, бірақ басқа тапсырмалардың орындалуын күту құнына, осылайша әділдікті төмендетеді.
БІРІНШІ КІРУ (FIFO)
Біз жүзеге асыра алатын ең негізгі алгоритм FIFO немесе деп аталады бірінші келу (кіру), бірінші қызмет көрсету (шығу). Бұл алгоритмнің бірнеше артықшылығы бар: оны жүзеге асыру өте оңай және ол біздің барлық болжамдарымызға сәйкес келеді және тапсырманы өте жақсы орындайды.
Қарапайым мысалды қарастырайық. Бір уақытта 3 тапсырма қойылды делік. Бірақ А тапсырмасы барлық қалғандарынан сәл ертерек келді делік, сондықтан ол орындалу тізімінде C-қа қатысты B сияқты басқаларына қарағанда ертерек пайда болады. Олардың әрқайсысы 10 секундта орындалады деп есептейік. Бұл жағдайда бұл тапсырмаларды орындаудың орташа уақыты қанша болады?
10+20+30 мәндерін санап, 3-ке бөлгенде, бағдарламаның орындалу уақыты 20 секундқа тең болады.
Енді өз болжамдарымызды өзгертуге тырысайық. Атап айтқанда, 1 болжам және осылайша біз әр тапсырманы орындау үшін бірдей уақытты алады деп есептемейміз. FIFO бұл жолы қалай өнер көрсетеді?
Белгілі болғандай, әртүрлі тапсырмаларды орындау уақыттары FIFO алгоритмінің өнімділігіне өте жағымсыз әсер етеді. А тапсырмасын орындауға 100 секунд кетеді, ал В және С әрқайсысына 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 тапсырмалары келген сәтте бірдеңе жасай алады - А тапсырмасын орындауды тоқтатады және В және С тапсырмаларын өңдеуге қояды және олар аяқталғаннан кейін А процесін орындауды жалғастырады. Мұндай жоспарлаушы деп аталады. STCFнемесе Бірінші кезектегі жұмыс.
Бұл жоспарлаушының нәтижесі келесі нәтиже болады: ((120-0)+(20-10)+(30-10))/3=50. Осылайша, мұндай жоспарлаушы біздің тапсырмаларымыз үшін одан да оңтайлы болады.
Метрикалық жауап беру уақыты
Осылайша, егер біз тапсырмалардың орындалу уақытын білсек және бұл тапсырмалар тек орталық процессорды қолданатын болса, STCF ең жақсы шешім болады. Бір кездері бұл алгоритмдер өте жақсы жұмыс істеді. Дегенмен, пайдаланушы қазір уақытының көп бөлігін терминалда өткізеді және нәтижелі интерактивті тәжірибені күтеді. Осылайша жаңа метрика пайда болды - Жауап беру уақыты (жауап).
Жауап беру уақыты келесідей есептеледі:
Tresponse=Tfirstrun-Tarrival
Осылайша, алдыңғы мысал үшін жауап уақыты: A=0, B=0, C=10 (abg=3,33) болады.
Ал STCF алгоритмі 3 тапсырма бір уақытта келетін жағдайда соншалықты жақсы емес екені белгілі болды - ол шағын тапсырмалар толығымен аяқталғанша күтуге тура келеді. Осылайша, алгоритм айналым уақыты көрсеткіші үшін жақсы, бірақ интерактивтілік метрикасы үшін нашар. Елестетіп көріңізші, сіз терминалда отырып редакторға таңбаларды теруге тырысып, 10 секундтан астам күтуіңіз керек, себебі басқа тапсырма процессорды алып жатыр. Бұл өте жағымды емес.
Сонымен, біз басқа мәселеге тап болдық - жауап беру уақытына сезімтал жоспарлаушыны қалай құруға болады?
Дөңгелек Робин
Бұл мәселені шешу үшін алгоритм жасалды Дөңгелек Робин (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 типті алгоритм әділ болып табылады; ол процессор уақытын барлық процестер арасында бірдей бөледі. Осылайша, бұл көрсеткіштер үнемі бір-бірімен қайшы келеді.
Осылайша, бізде бірнеше қарама-қайшы алгоритмдер бар және сонымен бірге әлі де бірнеше болжамдар қалды - тапсырма уақыты белгілі және тапсырма тек орталық процессорды пайдаланады.
Енгізу/шығарумен араластыру
Ең алдымен, процесс тек орталық процессорды пайдаланады деген 4-болжамды алып тастаймыз; әрине, бұлай емес және процестер басқа жабдыққа қол жеткізе алады.
Кез келген процесс енгізу/шығару әрекетін сұраған кезде, процесс енгізу/шығару әрекетінің аяқталуын күтіп, блокталған күйге өтеді. Егер енгізу/шығару қатты дискіге жіберілсе, онда мұндай операция бірнеше мс-ке дейін немесе одан да көп уақытты алуы мүмкін, ал процессор осы сәтте бос болады. Осы уақыт ішінде жоспарлаушы процессорды кез келген басқа процесспен толтыра алады. Жоспарлаушы қабылдауы керек келесі шешім - бұл процестің енгізу/шығару аяқталуы. Бұл орын алған кезде үзіліс орын алады және ОЖ енгізу/шығару деп аталатын процесті дайын күйге қояды.
Бірнеше есептің мысалын қарастырайық. Олардың әрқайсысы 50 мс процессор уақытын қажет етеді. Дегенмен, біріншісі енгізу/шығаруға 10 мс сайын қол жеткізеді (ол да әрбір 10 мс орындалады). Ал В процесі енгізу/шығарусыз 50 мс процессорды қолданады.
Бұл мысалда біз STCF жоспарлаушысын қолданамыз. А сияқты процесс іске қосылса, жоспарлаушы қалай әрекет етеді? Ол келесі әрекеттерді орындайды: алдымен А, содан кейін В процесін толығымен өңдейді.
Бұл мәселені шешудің дәстүрлі тәсілі А процесінің әрбір 10 мс қосалқы тапсырмасын жеке тапсырма ретінде қарастыру болып табылады. Осылайша, STJF алгоритмінен бастағанда 50 мс тапсырма мен 10 мс тапсырма арасындағы таңдау анық болады. Содан кейін, A қосалқы тапсырмасы аяқталғанда, B процесі және енгізу/шығару іске қосылады. Енгізу/шығару аяқталғаннан кейін В процесінің орнына 10 мс А процесін қайта бастау әдеттегідей болады. Осылайша, процессорды бірінші процесс күткен кезде басқа процесс пайдаланатын қабаттасуды жүзеге асыруға болады. енгізу/шығару. Нәтижесінде жүйе жақсырақ пайдаланылды - интерактивті процестер енгізу/шығаруды күтіп тұрған сәтте процессорда басқа процестерді орындауға болады.
Oracle енді жоқ
Енді тапсырманың орындалу уақыты белгілі деген жорамалдан арылуға тырысайық. Бұл, әдетте, бүкіл тізімдегі ең нашар және ең шынайы емес болжам. Шындығында, қарапайым қарапайым ОЖ-де ОЖ өзі әдетте тапсырмалардың орындалу уақыты туралы өте аз біледі, сондықтан тапсырманың орындалуына қанша уақыт кететінін білмей жоспарлаушыны қалай құруға болады? Мүмкін біз бұл мәселені шешу үшін кейбір RR принциптерін пайдалана аламыз ба?
Нәтиже
Біз тапсырмаларды жоспарлаудың негізгі идеяларын қарастырдық және жоспарлаушылардың 2 тобын қарастырдық. Біріншісі ең қысқа тапсырманы бірінші бастайды және осылайша өңдеу уақытын арттырады, ал екіншісі барлық тапсырмалар арасында бірдей үзіліп, жауап беру уақытын арттырады. Басқа отбасының алгоритмдері жақсы болған жағдайда екі алгоритм де нашар. Біз сондай-ақ процессор мен енгізу/шығаруды параллель пайдалану өнімділікті қалай жақсарта алатынын қарастырдық, бірақ операциялық жүйенің көрнекілігімен мәселені шеше алмадық. Ал келесі сабақта біз жақын өткенге қарап, болашақты болжауға тырысатын жоспарлаушыны қарастырамыз. Бұл көп деңгейлі кері байланыс кезегі деп аталады.
Ақпарат көзі: www.habr.com