Операциялық жүйелермен таныстыру
Эй Хабр! Мен сіздердің назарларыңызға менің ойымша, бір қызықты әдебиеттің аудармалары – 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 бақыланатын әрекетке байланысты басымдылығын өзгертеді.
Мысалы, егер тапсырма пернетақтадан енгізуді күту кезінде процессорда үнемі тоқтап қалса,
MLFQ процестің басымдылығын жоғары сақтайды, себебі осылай
интерактивті процесс жұмыс істеуі керек. Егер, керісінше, тапсырма үнемі және
процессор ұзақ уақыт бойы қарқынды болса, MLFQ оны төмендетеді
басымдық. Осылайша, MLFQ жұмыс істеп тұрған процестердің әрекетін зерттейді
және мінез-құлықтарды қолданады.
Кезектер қандай болуы мүмкін екеніне мысал келтірейік
уақыт, содан кейін сіз келесідей нәрсені аласыз:
Бұл схемада 2 процесс А және В ең жоғары басымдылықпен кезекте тұр. Процесс
C ортасында бір жерде, ал D процесі кезектің ең соңында. Жоғарыда айтылғандарға сәйкес
MLFQ алгоритмінің сипаттамасында жоспарлаушы ең жоғары тапсырмаларды ғана орындайды
RR сәйкес басымдық, ал C, D тапсырмалары жұмыссыз болады.
Әрине, статикалық сурет MLFQ қалай жұмыс істейтіні туралы толық суретті бермейді.
Уақыт өте суреттің қалай өзгеретінін дәл түсіну маңызды.
1-әрекет: басымдықты қалай өзгертуге болады
Осы кезде MLFQ басымдық деңгейін қалай өзгертетінін шешу керек
тапсырма (және осылайша тапсырманың кезектегі орны) оның өмірлік циклі кезінде. Үшін
осының ішінде сіз жұмыс процесін есте сақтауыңыз керек: белгілі бір сома
қысқа жұмыс уақыттары бар интерактивті тапсырмалар (және осылайша жиі шығарылады
CPU) және процессорды барлық жұмыс уақытында пайдаланатын бірнеше ұзақ тапсырмалар
мұндай тапсырмаларға жауап беру уақыты маңызды емес. Осылайша сіз бірінші әрекетті жасай аласыз
MLFQ алгоритмін келесі ережелермен орындаңыз:
- 3-ереже: Тапсырма жүйеге енген кезде ол ең жоғары кезекке қойылады
- басымдық.
- 4a ережесі: Тапсырма оған бөлінген барлық уақыт терезесін пайдаланса, онда ол
- басымдық төмендейді.
- 4b ережесі: Тапсырма уақыт терезесі біткенге дейін процессорды шығарса, онда ол
- бұрынғы басымдықта қалады.
1-мысал: Ұзақ орындалатын жалғыз тапсырма
Бұл мысалда көріп отырғаныңыздай, қабылдау кезінде тапсырма ең жоғары болып қойылған
басымдық. 10 мс уақыт терезесінен кейін процесс басымдылыққа төмендетіледі.
жоспарлаушы. Келесі терезеден кейін тапсырма ақырында төмендетіледі
жүйедегі ең төменгі басымдық, ол сол жерде қалады.
2-мысал: Қысқа тапсырма алды
Енді MLFQ SJF-ке қалай жақындауға тырысатынының мысалын көрейік. Осыда
мысалы, екі тапсырма: А, бұл үнемі ұзаққа созылатын тапсырма
қысқаша интерактивті тапсырма болып табылатын процессор мен В-ны алады. Айталық
В тапсырмасы келген кезде А біраз уақыт жұмыс істеп тұрған.
Бұл график сценарийдің нәтижелерін көрсетеді. А тапсырмасы, кез келген тапсырма сияқты,
процессорды пайдалану ең төменгі жағында болды. В тапсырмасы T=100 уақытында келеді және болады
бірінші кезектегі кезекке қойылады. Жұмыс уақыты қысқа болғандықтан,
ол соңғы кезекке жеткенше аяқталады.
Бұл мысалдан сіз алгоритмнің негізгі мақсатын түсінуіңіз керек: өйткені алгоритмде жоқ
ұзақ немесе қысқа тапсырманы біледі, содан кейін ол ең алдымен тапсырма деп есептейді
қысқа және оған ең жоғары басымдық береді. Егер бұл шынымен қысқа тапсырма болса, онда
ол тез орындалады, әйтпесе бұл ұзақ тапсырма болса, ол баяу қозғалады
басымдыққа ие болады және жақын арада оның шынымен де ұзақ жұмыс емес екенін дәлелдейді
жауап беруді талап етеді.
3-мысал: енгізу/шығару туралы не деуге болады?
Енді енгізу/шығару мысалын қарастырайық. 4b ережесінде көрсетілгендей,
егер процесс процессор уақытын толық пайдаланбай процессорды шығарса,
содан кейін ол бұрынғы басымдық деңгейінде қалады. Бұл ереженің мақсаты өте қарапайым.
- егер интерактивті тапсырма енгізу/шығару әрекеттерін көп орындаса, мысалы, күту
пайдаланушы пернелерін немесе тінтуірді басу арқылы мұндай тапсырма процессорды босатады
бөлінген терезенің алдында. Біз мұндай бірінші кезектегі міндетті назардан тыс қалдырғымыз келмейді,
және осылайша ол бұрынғы деңгейде қалады.
Бұл мысал алгоритмнің мұндай процестермен қалай жұмыс істейтінін көрсетеді - интерактивті тапсырма В, оны орындау алдында процессор тек 1 мс қажет.
Енгізу/шығару процесі және процессорды үнемі пайдаланатын ұзақ жұмыс А.
MLFQ B процесін жалғастыруда ең жоғары басымдылықта сақтайды
процессорды босатыңыз. Егер В интерактивті тапсырма болса, онда бұл жағдайда алгоритмге жетті
оның мақсаты - интерактивті тапсырмаларды жылдам іске қосу.
Ағымдағы MLFQ алгоритміне қатысты мәселелер
Алдыңғы мысалдарда біз MLFQ негізгі нұсқасын жасадық. Және ол сияқты
өз жұмысын жақсы және әділ орындап, процессордың уақытын арасында әділ бөледі
ұзақ тапсырмаларды және қысқа тапсырмаларды немесе көп қол жетімді тапсырмаларды орындауға мүмкіндік береді
жылдам өңдеу үшін енгізу/шығару. Өкінішке орай, бұл тәсіл бірнеше қамтиды
күрделі мәселелер.
Біріншіден, аштық мәселесі: жүйеде көптеген интерактивті болса
тапсырмалар, олар процессордың барлық уақытын жұмсайды, осылайша бірде-бір ұзақ емес
тапсырманы орындауға мүмкіндік болмайды (олар аштықта).
Екіншіден, ақылды пайдаланушылар өз бағдарламаларын осылай жаза алады
жоспарлаушыны алдау. Алдау – күштеу үшін бірдеңе істеу
процесске көбірек уақыт беру үшін жоспарлаушы. Алгоритм бұл
Жоғарыда сипатталған мұндай шабуылдарға өте осал: уақыт терезесі іс жүзінде бұрын
бітсе, енгізу/шығару әрекетін орындау керек (кейбіреулерге, қай файлға қарамастан)
және осылайша процессорды босатыңыз. Мұндай мінез-құлық сізге бұрынғы қалпында қалуға мүмкіндік береді
кезектің өзі және қайтадан CPU уақытының үлкен пайызын алады. Жасалса
бұл дұрыс (мысалы, процессорды шығармас бұрын терезе уақытының 99% іске қосыңыз),
мұндай тапсырма процессорды жай ғана монополиялауы мүмкін.
Ақырында, бағдарлама уақыт өте келе өзінің әрекетін өзгерте алады. Сол тапсырмалар
процессорды пайдаланған интерактивті болуы мүмкін. Біздің мысалда ұқсас
тапсырмалар басқалар сияқты жоспарлаушыдан тиісті ем қабылдамайды
(түпнұсқа) интерактивті тапсырмалар.
Аудиторияға сұрақ: қазіргі әлемде жоспарлаушыға қандай шабуылдар жасалуы мүмкін?
2-әрекет: басымдылықты арттырыңыз
Ережелерді өзгертуге тырысайық және қиындықтардан аулақ бола алатынымызды көрейік
аштық. Бұл байланысты қамтамасыз ету үшін не істей аламыз
CPU тапсырмалары өз уақытын алады (тіпті ұзақ болмаса да).
Мәселенің қарапайым шешімі ретінде сіз мерзімді түрде ұсына аласыз
жүйедегі барлық осындай міндеттердің басымдылығын арттыру. Көптеген жолдар бар
Бұған жету үшін мысал ретінде қарапайым нәрсені жүзеге асыруға тырысайық: аудару
барлық тапсырмалар бірден жоғары басымдыққа, демек, жаңа ереже:
- 5-ереже: Кейбір S кезеңінен кейін жүйедегі барлық тапсырмаларды ең жоғары кезекке ауыстырыңыз.
Жаңа ережеміз бірден екі мәселені шешеді. Біріншіден, процестер
аштан өлмеуге кепілдік беріледі: ең жоғары кезектегі тапсырмалар бөліседі
RR алгоритміне сәйкес процессор уақыты және осылайша барлық процестер алынады
процессор уақыты. Екіншіден, бұрын қолданылған процесс
тек процессор интерактивті болады, ол ең жоғары кезекте қалады
бір рет ең жоғары басымдыққа күшейту алғаннан кейін басымдық.
Мысал қарастырайық. Бұл сценарийде қолданатын жалғыз процесті қарастырыңыз
Орталық процессор және екі интерактивті, қысқа процесс. Суреттегі сол жақта сурет басымдықты күшейтусіз әрекетті көрсетеді және осылайша жүйеге екі интерактивті тапсырма келгеннен кейін ұзақ жұмыс істейтін тапсырма аштыққа ұшырай бастайды. Оң жақтағы суретте әрбір 50 мс сайын басымдықты арттыру орындалады және осылайша барлық процестер процессор уақытын алуға кепілдік береді және мерзімді түрде іске қосылады. Бұл жағдайда 50 мс мысал ретінде алынған, шын мәнінде бұл сан біршама жоғары.
Периодтық көтерілу уақытының S қосылуы әкелетіні анық
логикалық сұрақ: қандай мәнді орнату керек? Лайықтылардың бірі
Жүйе инженерлері Джон Оустерхоут жүйелердегі мұндай шамаларды ву-ду деп атады
тұрақты, өйткені олар қандай да бір жолмен дұрыс болу үшін қара магияны қажет етті
экспозиция. Және, өкінішке орай, S мұндай дәмге ие. Егер сіз де мәнді орнатсаңыз
үлкен - ұзақ міндеттер аштыққа ұшырайды. Егер сіз оны тым төмен орнатсаңыз,
интерактивті тапсырмалар процессордың тиісті уақытын алмайды.
3-әрекет: жақсырақ бухгалтерлік есеп
Енді бізде шешетін тағы бір мәселе бар: қалай болмайды
жоспарлаушымызды алдауға рұқсат етесіз бе? Бұл мүмкіндікке кінәлілер
4a, 4b ережелері процессорды босату арқылы тапсырманың басымдылығын сақтауға мүмкіндік береді
берілген уақыт біткенге дейін. Онымен қалай күресуге болады?
Бұл жағдайда шешімді әрқайсысында CPU уақытын жақсы есепке алу деп санауға болады
MLFQ деңгейі. Бағдарлама пайдаланылған уақытты ұмытудың орнына
бөлінген интервал үшін процессор, сіз оны ескеріп, сақтауыңыз керек. Кейін
процесс өзінің бөлінген уақытын аяқтады, оны келесіге төмендету керек
басымдық деңгейі. Енді процесс өз уақытын қалай пайдаланатыны маңызды емес - қалай
процессорда немесе қоңыраулар жиынтығы ретінде үнемі есептеу. Осылайша,
4-ереже мынадай редакцияда жазылсын:
- 4-ереже: Тапсырма ағымдағы кезекте өзінің бөлінген уақытын пайдаланғаннан кейін (ол процессорды қанша рет босатқанына қарамастан), мұндай тапсырманың басымдылығы төмендейді (ол кезекте төмен жылжиды).
Мысал қарастырайық:
»
Суретте жоспарлаушыны алдауға тырысқанда не болатыны көрсетілген
егер ол алдыңғы 4a, 4b ережелерімен болса, сол жақтағы нәтиже алынады. Жаңа құтты болсын
ереже - нәтиже оң жақта. Қорғау алдында кез келген процесс аяқталмай тұрып енгізу/шығару шақыруы мүмкін және
осылайша мінез-құлыққа қарамастан қорғауды қосқаннан кейін процессорға үстемдік етеді
Енгізу/шығару, ол әлі де кезекте тұрады және осылайша адалдық таныта алмайды
процессор ресурстарын иемдену.
MLFQ жақсарту және басқа мәселелер
Жоғарыда көрсетілген жақсартулармен жаңа мәселелер туындайды: негізгілерінің бірі
сұрақтар - мұндай жоспарлаушыны қалай параметрлеуге болады? Анау. Қанша болуы керек
кезектер? Кезекте бағдарлама терезесінің өлшемі қандай болуы керек? Қалай
аштықты болдырмау үшін бағдарламаға жиі басымдық беру керек және
бағдарламаның мінез-құлқының өзгеруін есепке алу керек пе? Бұл сұрақтардың қарапайымдылығы жоқ
жауап және тек жүктемелермен және кейінгі конфигурациямен эксперименттер
жоспарлаушы кейбір қанағаттанарлық теңгерімге әкелуі мүмкін.
Мысалы, MLFQ енгізулерінің көпшілігі әртүрлі тағайындауға мүмкіндік береді
әртүрлі кезектерге арналған уақыт аралықтары. Әдетте жоғары басымдылықтағы кезектер болады
қысқа интервалдар. Бұл кезектер интерактивті тапсырмалардан тұрады,
олардың арасында ауысу өте сезімтал және 10 немесе одан аз уақытты алуы керек
Ханым. Керісінше, басымдылығы төмен кезектер пайдаланатын ұзақ орындалатын тапсырмалардан тұрады
ОРТАЛЫҚ ЕСЕПТЕУІШ БӨЛІМ. Және бұл жағдайда ұзақ уақыт аралығы өте жақсы сәйкес келеді (100 мс).
Бұл мысалда жоғары басымдылық 2 кезекте жұмыс істеген 20 тапсырма бар
мс 10 мс терезелерге бөлінген. Ортаңғы кезекте (40 мс терезе) және төмен басымдылық кезекте 20 мс
Тапсырмалар өз жұмысын аяқтаған кезде кезек уақыты терезесі 40 мс болды.
Solaris ОЖ жүйесінде MLFQ іске асыру уақытпен бөлінген жоспарлаушылар класы болып табылады.
Жоспарлаушы кестелер жинағын қамтамасыз етеді, олар дәл қалай істеу керектігін анықтайды
оның өмір сүру барысында процестің басымдылығын өзгерту, мөлшері қандай болуы керек
Бөлінетін терезе және тапсырмалардың басымдықтарын қаншалықты жиі көтеру керек. Әкімші
жүйе осы кестемен әрекеттесіп, жоспарлаушының әрекетін жасай алады
басқаша. Әдепкі бойынша, бұл кестеде біртіндеп ұлғаюы бар 60 кезек бар
терезе өлшемі 20 мс (жоғары басымдық) бірнеше жүз мс дейін (ең төменгі басымдық) және
сонымен қатар секундына бір рет барлық тапсырмаларды күшейту арқылы.
Басқа MLFQ жоспарлаушылары кестені немесе қандай да бір ерекшелікті пайдаланбайды
осы тарауда сипатталған ережелер, керісінше, басымдықтарды пайдалана отырып есептейді
математикалық формулалар. Мысалы, FreeBSD ішіндегі жоспарлаушы формуланы пайдаланады
процестің қаншалықты екеніне байланысты ағымдағы тапсырманың басымдылығын есептеу
процессорды пайдаланды. Сонымен қатар, процессорды пайдалану уақыт өте келе шіріп кетеді және осылайша
Осылайша, басымдықты арттыру жоғарыда сипатталғаннан біршама ерекшеленеді. Бұл осылай
ыдырау алгоритмдері деп аталады. 7.1 нұсқасы бойынша FreeBSD ULE жоспарлаушысын пайдаланады.
Ақырында, көптеген жоспарлаушылардың басқа мүмкіндіктері бар. Мысалы, кейбір
жоспарлаушылар операциялық жүйенің жұмысы үшін жоғары деңгейлерді сақтайды және осылайша
Осылайша, ешбір пайдаланушы процесі ең жоғары басымдыққа ие бола алмайды
жүйесі. Кейбір жүйелер сізге көмектесу үшін кеңес беруге мүмкіндік береді
жоспарлаушыға дұрыс басымдық беру. Мысалы, пәрменді пайдалану жақсы
тапсырманың басымдылығын арттыруға немесе азайтуға және осылайша көбейтуге немесе азайтуға болады
бағдарламаның CPU уақытының мүмкіндігін азайтады.
MLFQ: Түйіндеме
Біз MLFQ деп аталатын жоспарлау тәсілін сипаттадық. Оның есімі
жұмыс істеу принципінде жасалған – оның бірнеше кезегі бар және кері байланысты пайдаланады
тапсырмаға басымдық беру.
Ереженің соңғы нысаны келесідей болады:
- 1-ереже: Приоритет(A) > Приоритет(B) болса, А тапсырмасы орындалады (В орындалмайды)
- 2-ереже: Приоритет(A) = Приоритет(B) болса, A&B RR арқылы басталады
- 3-ереже: Тапсырма жүйеге кіргенде, ол ең жоғары басым кезекке қойылады.
- 4-ереже: Тапсырма ағымдағы кезекте өзінің бөлінген уақытын пайдаланғаннан кейін (ол процессорды қанша рет босатқанына қарамастан), мұндай тапсырманың басымдылығы төмендейді (ол кезекте төмен жылжиды).
- 5-ереже: Кейбір S кезеңінен кейін жүйедегі барлық тапсырмаларды ең жоғары кезекке ауыстырыңыз.
MLFQ келесі себептермен қызықты - бұл туралы білімді талап етудің орнына
тапсырманың сипатын алдын ала, алгоритм тапсырманың өткен тәртібін үйренеді және орнатады
сәйкес басымдықтар. Осылайша, ол бірден екі орындыққа отыруға тырысады - кішігірім тапсырмаларды орындауға (SJF, STCF) қол жеткізуге және ұзақ тапсырмаларды адал орындауға,
CPU жүктеу тапсырмалары. Сондықтан көптеген жүйелер, соның ішінде BSD және олардың туындылары,
Solaris, Windows, Mac жоспарлаушы ретінде алгоритмнің қандай да бір түрін пайдаланады
MLFQ базалық көрсеткіш ретінде.
Дополнительные материалдар:
- (есептеу)
Ақпарат көзі: www.habr.com