Օպերացիոն համակարգերի ներածություն
Հե՜յ Հաբր։ Ձեր ուշադրությանն եմ ներկայացնում իմ կարծիքով մեկ հետաքրքիր գրականության՝ OSTEP-ի հոդված-թարգմանությունների շարքը։ Այս նյութը բավականին խորը քննարկում է unix-ի նման օպերացիոն համակարգերի աշխատանքը, այն է՝ պրոցեսների, տարբեր ժամանակացույցերի, հիշողության և այլ նմանատիպ բաղադրիչների հետ աշխատանքը, որոնք կազմում են ժամանակակից ՕՀ: Բոլոր նյութերի բնօրինակը կարող եք տեսնել այստեղ . Խնդրում եմ նկատի ունենալ, որ թարգմանությունը կատարվել է ոչ պրոֆեսիոնալ (բավականին ազատ), բայց հուսով եմ պահպանել եմ ընդհանուր իմաստը։
Այս թեմայով լաբորատոր աշխատանք կարելի է գտնել այստեղ.
Այլ մասեր.
Կարող եք նաև դիտել իմ ալիքը =)
Պլանավորում՝ բազմամակարդակ հետադարձ կապի հերթ
Այս դասախոսության ընթացքում մենք կխոսենք ամենահայտնի մոտեցումներից մեկի մշակման խնդիրների մասին
պլանավորում, որը կոչվում է Բազմաստիճան հետադարձ կապի հերթ (MLFQ): MLFQ ժամանակացույցն առաջին անգամ նկարագրվել է 1962 թվականին Ֆերնանդո Ջ. Կորբատոյի կողմից՝ համակարգով, որը կոչվում է
Համատեղելի ժամանակի փոխանակման համակարգ (CTSS): Այս աշխատանքները (ներառյալ հետագա աշխատանքը
Multics) այնուհետև առաջադրվել են Թյուրինգի մրցանակին: Պլանավորողն էր
այնուհետև բարելավվեց և ստացավ տեսք, որը կարելի է արդեն գտնել
որոշ ժամանակակից համակարգեր:
MLFQ ալգորիթմը փորձում է լուծել 2 հիմնարար համընկնող խնդիր.
Նախ, այն փորձում է օպտիմիզացնել շրջադարձի ժամանակը, որը, ինչպես քննարկեցինք նախորդ դասախոսության ժամանակ, օպտիմիզացված է ամենից շատ հերթի սկզբից սկսելու մեթոդով։
կարճ առաջադրանքներ. Այնուամենայնիվ, ՕՀ-ն չգիտի, թե կոնկրետ գործընթացը որքան ժամանակ կգործի, և սա
անհրաժեշտ գիտելիքներ SJF, STCF ալգորիթմների շահագործման համար: Երկրորդ, MLFQ-ն փորձում է
համակարգը պատասխանատու դարձնել օգտատերերի համար (օրինակ՝ նրանց համար, ովքեր նստում են և
նայեք էկրանին, սպասելով առաջադրանքի ավարտին) և այդպիսով նվազագույնի հասցրեք ժամանակը
արձագանք. Ցավոք սրտի, RR-ի նման ալգորիթմները բարելավում են արձագանքման ժամանակը, բայց չափազանց
վատ ազդեցություն ունենալ շրջադարձային ժամանակի չափման վրա: Այստեղից էլ մեր խնդիրը. Ինչպես նախագծել
ժամանակացույց, որը կհամապատասխանի մեր պահանջներին՝ առանց որևէ բան իմանալու
գործընթացի բնույթն ընդհանրապես: Ինչպես կարող է ժամանակացույցը սովորել առաջադրանքների բնութագրերը,
որը նա սկսում է և այդպիսով ավելի լավ պլանավորման որոշումներ կայացնում:
Խնդիրի էությունը. Ինչպե՞ս պլանավորել առաջադրանքների սահմանումը առանց կատարյալ գիտելիքների:
Ինչպես նախագծել ժամանակացույց, որը միաժամանակ նվազագույնի է հասցնում արձագանքման ժամանակը
ինտերակտիվ առաջադրանքների համար և միևնույն ժամանակ նվազագույնի է հասցնում շրջադարձի ժամանակը առանց իմանալու
առաջադրանքի կատարման ժամանակի իմացությո՞ւնը:
Նշում. սովորում ենք նախորդ իրադարձություններից
MLFQ հերթը համակարգի հիանալի օրինակ է, որը սովորում է
անցյալի իրադարձությունները կանխատեսելու ապագան: Նմանատիպ մոտեցումներ հաճախ են լինում
հայտնաբերվել է ՕՀ-ում (և համակարգչային գիտության շատ այլ ճյուղեր, ներառյալ ճյուղերը
ապարատային կանխատեսումներ և քեշավորման ալգորիթմներ): Նմանատիպ ճամփորդություններ
գործարկվում են, երբ առաջադրանքները վարքային փուլեր ունեն և, հետևաբար, կանխատեսելի են:
Այնուամենայնիվ, դուք պետք է զգույշ լինեք այս տեխնիկայի հետ, քանի որ կանխատեսումները շատ հեշտ են
կարող է սխալ լինել և ստիպել համակարգը ավելի վատ որոշումներ կայացնել, քան
ընդհանրապես առանց գիտելիքի կլիներ:
MLFQ. Հիմնական կանոններ
Եկեք նայենք MLFQ ալգորիթմի հիմնական կանոններին: Եվ չնայած այս ալգորիթմի իրականացումներին
Կան մի քանիսը, հիմնական մոտեցումները նման են.
Իրականացման մեջ, որը մենք կդիտարկենք, MLFQ-ն կունենա մի քանիսը
առանձին հերթեր, որոնցից յուրաքանչյուրը կունենա տարբեր առաջնահերթություն։ Ցանկացած ժամանակ,
կատարման պատրաստ առաջադրանքը մեկ հերթում է: MLFQ-ն օգտագործում է առաջնահերթությունները,
որոշել, թե որ առաջադրանքն է առաջադրվելու կատարման համար, այսինքն. առաջադրանք բարձրագույնի հետ
առաջնահերթությունը (առաջնահերթություն ունեցող հերթից առաջադրանքը) առաջինը կգործարկվի
հերթ.
Իհարկե, տվյալ հերթում կարող է լինել մեկից ավելի առաջադրանք, ուստի
այնպես որ նրանք կունենան նույն առաջնահերթությունը: Այս դեպքում մեխանիզմը կկիրառվի
RR՝ այս առաջադրանքների միջև վազք պլանավորելու համար:
Այսպիսով, մենք հասնում ենք MLFQ-ի երկու հիմնական կանոններին.
- Կանոն 1. Եթե առաջնահերթություն (A) > Առաջնահերթություն (B), առաջադրանքը A կսկսվի (B չի)
- Կանոն 2. Եթե առաջնահերթություն (A) = Առաջնահերթություն (B), A&B-ն սկսվում է օգտագործելով RR
Ելնելով վերը նշվածից՝ MLFQ պլանավորման հիմնական տարրերը
առաջնահերթություններ են։ Յուրաքանչյուրին ֆիքսված առաջնահերթություն տալու փոխարեն
առաջադրանքը, MLFQ-ն փոխում է իր առաջնահերթությունը՝ կախված դիտարկվող վարքագծից:
Օրինակ, եթե առաջադրանքը անընդհատ աշխատանք է տանում պրոցեսորի վրա՝ սպասելով ստեղնաշարի մուտքագրմանը,
MLFQ-ն բարձր կպահի գործընթացի առաջնահերթությունը, քանի որ այդպես է
պետք է գործի ինտերակտիվ գործընթաց: Եթե, ընդհակառակը, խնդիրն անընդհատ ու
Երկար ժամանակահատվածում մեծապես օգտագործում է պրոցեսորը, MLFQ-ն կիջեցնի այն
առաջնահերթություն. Այսպիսով, MLFQ-ն կուսումնասիրի գործընթացների վարքագիծը, երբ դրանք աշխատում են
և օգտագործել վարքագիծ:
Եկեք օրինակ նկարենք, թե ինչ-որ պահի ինչ տեսք կարող են ունենալ հերթերը
ժամանակ, ապա դուք ստանում եք այսպիսի բան.
Այս սխեմայում 2 պրոցեսներ A և B գտնվում են ամենաբարձր առաջնահերթ հերթում: Գործընթացը
C-ն ինչ-որ տեղ մեջտեղում է, իսկ D պրոցեսը գտնվում է հերթի ամենավերջում: Ըստ վերը նշվածի
Համաձայն MLFQ ալգորիթմի նկարագրությունների, ժամանակացույցը կկատարի առաջադրանքներ միայն ամենաբարձր
առաջնահերթությունն ըստ RR-ի, իսկ C, D առաջադրանքները կլինեն առանց աշխատանքի:
Բնականաբար, ստատիկ լուսանկարը չի տա ամբողջական պատկեր, թե ինչպես է աշխատում MLFQ-ն:
Կարևոր է հասկանալ, թե ինչպես է պատկերը փոխվում ժամանակի ընթացքում:
Փորձ 1. Ինչպես փոխել առաջնահերթությունը
Այս պահին դուք պետք է որոշեք, թե ինչպես MLFQ-ն կփոխի առաջնահերթության մակարդակը
առաջադրանքները (և, հետևաբար, առաջադրանքի դիրքը հերթում), քանի որ այն անցնում է իր կյանքի ցիկլի ընթացքում: Համար
սա անհրաժեշտ է ի նկատի ունենալ աշխատանքի ընթացքը. որոշակի քանակություն
ինտերակտիվ առաջադրանքներ կարճ գործարկման ժամանակով (և հետևաբար հաճախակի թողարկում
CPU) և մի քանի երկարատև առաջադրանքներ, որոնք օգտագործում են պրոցեսորն իրենց ամբողջ աշխատանքային ժամանակը, մինչդեռ
Նման առաջադրանքների համար արձագանքման ժամանակը կարևոր չէ: Եվ այս կերպ դուք կարող եք կատարել ձեր առաջին փորձը
իրականացնել MLFQ ալգորիթմը հետևյալ կանոններով.
- Կանոն 3. Երբ առաջադրանքը մտնում է համակարգ, այն տեղադրվում է ամենաբարձրն ունեցող հերթում
- առաջնահերթություն։
- Կանոն 4ա. Եթե առաջադրանքն օգտագործում է իրեն հատկացված ամբողջ ժամանակի պատուհանը, ապա այն
- առաջնահերթությունը կրճատվում է.
- Կանոն 4բ. Եթե առաջադրանքը թողարկում է պրոցեսորը մինչև դրա ժամանակային պատուհանի լրանալը, ապա այն
- մնում է նույն առաջնահերթությամբ։
Օրինակ 1. Մեկ երկարատև առաջադրանք
Ինչպես երևում է այս օրինակում, ընդունելության խնդիրն ամենաբարձրն է
առաջնահերթություն։ 10 ms ժամանակային պատուհանից հետո գործընթացն առաջնահերթ է դառնում
պլանավորող. Հաջորդ անգամ պատուհանից հետո առաջադրանքը վերջնականապես իջեցվում է
ամենացածր առաջնահերթությունը համակարգում, որտեղ այն մնում է:
Օրինակ 2. Կատարել է կարճ առաջադրանք
Այժմ տեսնենք մի օրինակ, թե ինչպես է MLFQ-ն կփորձի մոտենալ SJF-ին: Դրանում
Օրինակ, երկու առաջադրանք՝ A, որը երկարաժամկետ առաջադրանք է անընդհատ
զբաղեցնելով CPU-ն և B-ն, որը կարճ ինտերակտիվ խնդիր է: Ենթադրենք
որ A-ն արդեն աշխատում էր որոշ ժամանակով մինչև B առաջադրանքի ժամանումը:
Այս գրաֆիկը ցույց է տալիս սցենարի արդյունքները: Առաջադրանք Ա, ինչպես ցանկացած առաջադրանք,
CPU-ի օգտագործումը ամենաներքևում էր: Բ առաջադրանքը կհասնի T=100 ժամանակին և կհասնի
տեղադրված ամենաբարձր առաջնահերթ հերթում: Քանի որ դրա շահագործման ժամանակը կարճ է, ուրեմն
այն կավարտվի մինչև վերջին հերթին հասնելը:
Այս օրինակից պետք է հասկանալ ալգորիթմի հիմնական նպատակը. քանի որ ալգորիթմը չի անում
գիտի առաջադրանքը երկար է, թե կարճ, ապա առաջին հերթին ենթադրում է, որ առաջադրանքը
կարճ և դրան տալիս է ամենաբարձր առաջնահերթությունը: Եթե սա իսկապես կարճ խնդիր է, ապա
այն արագ կավարտվի, այլապես եթե երկար գործ է, դանդաղ կշարժվի
առաջնահերթությունը զիջում է և շուտով կապացուցի, որ նա իսկապես երկար խնդիր է, որը չի անում
պատասխան է պահանջում.
Օրինակ 3. Ինչ վերաբերում է I/O-ին:
Հիմա եկեք նայենք I/O օրինակին: Ինչպես նշված է կանոն 4b-ում,
եթե գործընթացն ազատում է պրոցեսորը՝ չօգտագործելով իր ամբողջ պրոցեսորի ժամանակը,
ապա այն մնում է նույն առաջնահերթության մակարդակում: Այս կանոնի նպատակը բավականին պարզ է
- եթե ինտերակտիվ աշխատանքը կատարում է բազմաթիվ I/O գործողություններ, օրինակ՝ սպասում
օգտագործողի ստեղնից կամ մկնիկի սեղմումից, նման առաջադրանքը կազատի պրոցեսորը
հատկացված պատուհանից առաջ։ Մենք չէինք ցանկանա նվազեցնել նման առաջադրանքի առաջնահերթությունը,
և այդպիսով այն կմնա նույն մակարդակի վրա։
Այս օրինակը ցույց է տալիս, թե ինչպես է ալգորիթմը աշխատելու նման գործընթացների հետ՝ ինտերակտիվ աշխատանք B, որին անհրաժեշտ է միայն պրոցեսոր 1ms-ով մինչև կատարումը:
I/O գործընթաց և երկարաժամկետ Job A, որն իր ամբողջ ժամանակը ծախսում է պրոցեսորի օգտագործմամբ:
MLFQ-ն B գործընթացը պահում է ամենաբարձր առաջնահերթությունը, քանի որ այն շարունակվում է
թողարկեք պրոցեսորը: Եթե B-ն ինտերակտիվ խնդիր է, ապա ալգորիթմը հասել է
Ձեր նպատակն է արագ կատարել ինտերակտիվ առաջադրանքները:
Խնդիրներ ընթացիկ MLFQ ալգորիթմի հետ
Նախորդ օրինակներում մենք կառուցեցինք MLFQ-ի հիմնական տարբերակը: Եվ թվում է, թե նա
կատարում է իր աշխատանքը լավ և ազնվորեն՝ արդարացիորեն բաշխելով պրոցեսորի ժամանակը
երկար առաջադրանքներ և թույլ տալ կարճ կամ մեծ ծավալով առաջադրանքներ
արագ աշխատել I/O-ի վրա: Ցավոք, այս մոտեցումը պարունակում է մի քանիսը
լուրջ խնդիրներ.
Նախ, սովի խնդիրը. եթե համակարգն ունի շատ ինտերակտիվ
առաջադրանքները, այնուհետև դրանք կսպառեն պրոցեսորի ամբողջ ժամանակը և, հետևաբար, երկար ժամանակ ոչ մեկը
առաջադրանքը չի հաջողվի կատարել (նրանք սովամահ են):
Երկրորդ, խելացի օգտատերերը կարող էին գրել իրենց ծրագրերն այնպես, որ
խաբել ժամանակացույցին. Խաբեությունը կայանում է նրանում, որ ինչ-որ բան անելը ստիպելու համար
Ժամանակացույցը գործընթացին ավելի շատ ժամանակ է տալիս պրոցեսորին: Ալգորիթմ, որ
վերը նկարագրված բավականին խոցելի է նմանատիպ հարձակումների համար
ավարտվեց, դուք պետք է կատարեք I/O գործողություն (ոմանց համար, անկախ նրանից, թե որ ֆայլը)
և այդպիսով ազատել պրոցեսորը: Նման պահվածքը թույլ կտա ձեզ մնալ նույն վիճակում
հերթը ինքնին և կրկին ստանում է պրոցեսորի ժամանակի ավելի մեծ տոկոս: Եթե դու անես
սա ճիշտ է (օրինակ, գործարկեք պատուհանի ժամանակի 99%-ը նախքան պրոցեսորը թողարկելը),
նման առաջադրանքը կարող է պարզապես մոնոպոլիզացնել պրոցեսորը:
Վերջապես, ծրագիրը կարող է ժամանակի ընթացքում փոխել իր վարքագիծը: Այդ առաջադրանքները
որն օգտագործում էր պրոցեսորը, կարող է դառնալ ինտերակտիվ: Մեր օրինակում նման
առաջադրանքները չեն ստանա այն վերաբերմունքը, որը նրանք արժանի են ժամանակացույցի կողմից, ինչպես մյուսները
(նախնական) ինտերակտիվ առաջադրանքներ.
Հարց հանդիսատեսին. ի՞նչ հարձակումներ կարող են իրականացվել ժամանակացույցի վրա ժամանակակից աշխարհում:
Փորձ 2. առաջնահերթության բարձրացում
Փորձենք փոխել կանոնները և տեսնել, թե արդյոք կարող ենք խուսափել խնդիրներից
ծոմապահություն. Ի՞նչ կարող ենք անել, որպեսզի ապահովենք, որ կապված է
CPU-ի առաջադրանքները կստանան իրենց ժամանակը (նույնիսկ եթե ոչ երկար):
Որպես խնդրի պարզ լուծում՝ կարող եք պարբերաբար առաջարկել
բարձրացնել համակարգում նման բոլոր առաջադրանքների առաջնահերթությունը: Շատ ճանապարհներ կան
Դրան հասնելու համար եկեք փորձենք իրականացնել մի պարզ օրինակ՝ թարգմանել
բոլոր առաջադրանքներին անմիջապես տրվում է ամենաբարձր առաջնահերթությունը, հետևաբար նոր կանոնը.
- Կանոն 5Որոշակի S ժամանակահատվածից հետո համակարգի բոլոր առաջադրանքները տեղափոխեք ամենաբարձր հերթ:
Մեր նոր կանոնը միանգամից երկու խնդիր է լուծում. Նախ՝ գործընթացները
երաշխավորված են, որ սովից չեն մեռնելու. առաջադրանքները, որոնք առաջնահերթություն են, կբաժանվեն
CPU-ի ժամանակը ըստ RR ալգորիթմի և այդպիսով բոլոր գործընթացները կստանան
Պրոցեսորի ժամանակ. Երկրորդ, եթե նախկինում օգտագործված ինչ-որ գործընթաց
միայն պրոցեսորն է դառնում ինտերակտիվ, այն կմնա ամենաբարձրով հերթում
առաջնահերթություն՝ առաջնահերթության միանվագ բարձրացում ստանալուց հետո մինչև ամենաբարձրը:
Դիտարկենք մի օրինակ։ Այս սցենարում դիտարկեք մեկ գործընթաց օգտագործելով
CPU և երկու ինտերակտիվ, կարճ գործընթացներ: Նկարի ձախ կողմում նկարը ցույց է տալիս վարքագիծը առանց առաջնահերթ առաջխաղացման, և այդպիսով երկարատև առաջադրանքը սկսում է սովամահ լինել երկու ինտերակտիվ առաջադրանքների համակարգ հասնելուց հետո: Աջ նկարում առաջնահերթության բարձրացումն իրականացվում է յուրաքանչյուր 50 մս-ում, և այդպիսով բոլոր գործընթացները երաշխավորված են ստանալ պրոցեսորի ժամանակ և պարբերաբար կգործարկվեն: 50ms-ն այս դեպքում վերցված է որպես օրինակ, իրականում այդ թիվը մի փոքր ավելի մեծ է:
Ակնհայտ է, որ S պարբերական աճի ժամանակը ավելացնելը հանգեցնում է
տրամաբանական հարց՝ ի՞նչ արժեք պետք է սահմանել։ Պատվավորներից մեկը
համակարգերի ինժեներ Ջոն Օսթերհաութը համակարգերում նման քանակություններ անվանել է վու-դու
հաստատուն, քանի որ դրանք ինչ-որ կերպ պահանջում էին սև մոգություն՝ ճիշտ լինելու համար
ցուցադրելով. Եվ, ցավոք սրտի, S-ն ունի նման բույր։ Եթե դուք նույնպես սահմանեք արժեքը
մեծ - երկար գործերը կսկսեն սովամահ լինել: Եվ եթե արժեքը չափազանց ցածր եք սահմանել,
Ինտերակտիվ առաջադրանքները չեն ստանա պատշաճ պրոցեսորի ժամանակ:
Փորձ 3. Ավելի լավ հաշվապահություն
Հիմա մենք այլ խնդիր ունենք լուծելու՝ ինչպես չանել
թույլ տալ, որ մեր ժամանակացույցը խաբվի? Այս հնարավորության համար մեղավոր մարդիկ են
4a, 4b կանոնները, որոնք թույլ են տալիս աշխատանքին պահպանել առաջնահերթությունը՝ ազատելով պրոցեսորը
մինչև սահմանված ժամկետի լրանալը. Ինչպե՞ս վարվել սրա հետ:
Այս դեպքում լուծումը կարելի է համարել յուրաքանչյուրի վրա պրոցեսորի ժամանակի ավելի լավ հաշվառում
MLFQ մակարդակ: Ծրագրի օգտագործած ժամանակը մոռանալու փոխարեն
պրոցեսոր հատկացված ժամանակահատվածի համար, այն պետք է հաշվի առնել և պահպանել: հետո
գործընթացը սպառել է իր հատկացված ժամանակը, այն պետք է տեղափոխվի հաջորդ
առաջնահերթության մակարդակը: Հիմա կարևոր չէ, թե ինչպես կօգտագործի գործընթացը՝ ինչպես
անընդհատ հաշվարկելով պրոցեսորի վրա կամ որպես մի շարք զանգեր: Այսպիսով,
4-րդ կանոնը պետք է վերաշարադրվի հետևյալ ձևով.
- Կանոն 4Այն բանից հետո, երբ առաջադրանքը սպառում է իր հատկացված ժամանակը ընթացիկ հերթում (անկախ նրանից, թե քանի անգամ է այն ազատել պրոցեսորը), այդ առաջադրանքի առաջնահերթությունը իջնում է (այն շարժվում է հերթում):
Դիտարկենք օրինակ.
»
Նկարը ցույց է տալիս, թե ինչ է տեղի ունենում, եթե փորձեք խաբել ժամանակացույցին, օրինակ
եթե դա լիներ նախորդ 4a, 4b կանոններով, ապա արդյունքը կստացվեր ձախ կողմում: Շնորհավոր նոր
կանոնը արդյունքն է աջ կողմում: Նախքան պաշտպանությունը, ցանկացած գործընթաց կարող է զանգահարել I/O մինչև ավարտը և
այդպիսով տիրել պրոցեսորին՝ պաշտպանությունը միացնելուց հետո՝ անկախ վարքագծից
I/O, նա դեռ կտեղափոխվի ներքև հերթում և այդպիսով չի կարողանա անազնիվ կերպով
վերցնել պրոցեսորի ռեսուրսները:
MLFQ-ի և այլ խնդիրների բարելավում
Վերոնշյալ բարելավումներով առաջանում են նոր խնդիրներ՝ հիմնականներից մեկը
Հարցեր. ինչպե՞ս պարամետրացնել նման ժամանակացույցը: Նրանք. Որքան պետք է լինի
հերթեր? Որքա՞ն պետք է լինի ծրագրի պատուհանի չափը հերթում: Ինչպես
Ծրագրի առաջնահերթությունը հաճախ պետք է մեծացվի՝ սովից խուսափելու համար և
հաշվի առնել ծրագրի վարքագծի փոփոխությունը. Այս հարցերի պարզ պատասխանը չկա
պատասխան և միայն փորձեր բեռների և հետագա կոնֆիգուրացիայի հետ
պլանավորողը կարող է հանգեցնել որոշակի բավարար հավասարակշռության:
Օրինակ, MLFQ իրականացումների մեծ մասը թույլ է տալիս տարբեր նշանակել
ժամանակային ընդմիջումներ տարբեր հերթերի համար: Սովորաբար բարձր առաջնահերթ հերթեր
նշանակվում են կարճ ընդմիջումներ. Այս հերթերը բաղկացած են ինտերակտիվ առաջադրանքներից,
որոնց միջև անցումը բավականին զգայուն է և պետք է տևի 10 կամ ավելի քիչ
ms. Ի հակադրություն, ցածր առաջնահերթության հերթերը բաղկացած են երկարաժամկետ առաջադրանքներից, որոնք օգտագործում են
CPU. Եվ այս դեպքում երկար ժամանակային միջակայքերը շատ լավ են տեղավորվում (100 մս):
Այս օրինակում կան 2 առաջադրանքներ, որոնք աշխատել են բարձր առաջնահերթության 20-րդ հերթում
ms, բաժանված է 10ms պատուհանների: 40ms միջին հերթում (20ms պատուհան) և ցածր առաջնահերթությամբ
Հերթի ժամանակի պատուհանը դարձավ 40 մս, որտեղ առաջադրանքները ավարտեցին իրենց աշխատանքը:
MLFQ-ի Solaris OS-ի իրականացումը ժամանակի փոխանակման ժամանակացույցների դաս է:
Պլանավորողը կտրամադրի աղյուսակների մի շարք, որոնք սահմանում են ճիշտ այնպես, ինչպես պետք է
գործընթացի առաջնահերթությունը փոխվում է իր կյանքի ընթացքում, ինչ չափս պետք է լինի
հատկացված պատուհանը և որքան հաճախ է անհրաժեշտ առաջադրանքի առաջնահերթությունները բարձրացնելու համար: Ադմինիստրատոր
համակարգերը կարող են փոխազդել այս աղյուսակի հետ և առաջացնել ժամանակացույցի վարքագիծ
այլ կերպ. Լռելյայնորեն այս աղյուսակն ունի 60 հերթ՝ աստիճանական աճով
պատուհանի չափը 20 մվ-ից (բարձր առաջնահերթություն) մինչև մի քանի հարյուր ms (ցածր առաջնահերթություն) և
նաև վայրկյանում մեկ անգամ բոլոր առաջադրանքների խթանմամբ:
Այլ MLFQ պլանավորողները չեն օգտագործում աղյուսակ կամ որևէ կոնկրետ
կանոնները, որոնք նկարագրված են այս դասախոսության մեջ, ընդհակառակը, նրանք հաշվարկում են առաջնահերթությունները՝ օգտագործելով
մաթեմատիկական բանաձևեր. Օրինակ, FreeBSD ժամանակացույցն օգտագործում է բանաձևը
հաշվարկել առաջադրանքի ընթացիկ առաջնահերթությունը՝ հիմնվելով գործընթացի տևողության վրա
օգտագործված պրոցեսոր: Բացի այդ, պրոցեսորի օգտագործումը ժամանակի ընթացքում քայքայվում է և այլն
Այսպիսով, առաջնահերթության բարձրացումը տեղի է ունենում մի փոքր այլ կերպ, քան վերը նկարագրված է: Սա ճիշտ է
կոչվում են քայքայման ալգորիթմներ: 7.1 տարբերակից ի վեր FreeBSD-ն օգտագործում է ULE ժամանակացույցը:
Վերջապես, շատ ժամանակացույցներ ունեն այլ առանձնահատկություններ: Օրինակ՝ ոմանք
ժամանակացույցները վերապահում են ամենաբարձր մակարդակները օպերացիոն համակարգի աշխատանքի համար և այդպիսով
Այսպիսով, օգտվողների ոչ մի գործընթաց չի կարող ստանալ ամենաբարձր առաջնահերթությունը
համակարգ. Որոշ համակարգեր թույլ են տալիս ձեզ օգնելու խորհուրդներ տալ
պլանավորողը կարող է ճիշտ սահմանել առաջնահերթությունները: Օրինակ, օգտագործելով հրամանը գեղեցիկ
դուք կարող եք ավելացնել կամ նվազեցնել առաջադրանքի առաջնահերթությունը և այդպիսով ավելացնել կամ
նվազեցնել ծրագրի՝ պրոցեսորի ժամանակն օգտագործելու հնարավորությունները:
MLFQ: Ամփոփում
Մենք նկարագրել ենք պլանավորման մոտեցում, որը կոչվում է MLFQ: Նրա անունը
կցված է գործողության սկզբունքով - այն ունի մի քանի հերթեր և օգտագործում է հետադարձ կապ
առաջադրանքի առաջնահերթությունը որոշելու համար.
Կանոնների վերջնական ձևը կլինի հետևյալը.
- Կանոն 1Եթե առաջնահերթություն (A) > Առաջնահերթություն (B), առաջադրանքը A կսկսվի (B չի)
- Կանոն 2Եթե առաջնահերթություն (A) = Առաջնահերթություն (B), A&B-ն սկսվում է օգտագործելով RR
- Կանոն 3Երբ առաջադրանքը մտնում է համակարգ, այն տեղադրվում է ամենաբարձր առաջնահերթ հերթում:
- Կանոն 4Այն բանից հետո, երբ առաջադրանքը սպառում է իր հատկացված ժամանակը ընթացիկ հերթում (անկախ նրանից, թե քանի անգամ է այն ազատել պրոցեսորը), այդ առաջադրանքի առաջնահերթությունը իջնում է (այն շարժվում է հերթում):
- Կանոն 5Որոշակի S ժամանակահատվածից հետո համակարգի բոլոր առաջադրանքները տեղափոխեք ամենաբարձր հերթ:
MLFQ-ն հետաքրքիր է հետևյալ պատճառով՝ գիտելիքներ պահանջելու փոխարեն
առաջադրանքի բնույթը նախօրոք, ալգորիթմը ուսումնասիրում է առաջադրանքի անցյալ վարքագիծը և սահմանում
առաջնահերթությունները համապատասխանաբար: Այսպիսով, նա փորձում է նստել միանգամից երկու աթոռների վրա՝ փոքր առաջադրանքների համար (SJF, STCF) հասնել արտադրողականության և ազնվորեն երկար վազել,
CPU-ի բեռնման աշխատանքներ: Հետևաբար, շատ համակարգեր, ներառյալ BSD-ն և դրանց ածանցյալները,
Solaris-ը, Windows-ը, Mac-ն օգտագործում են ալգորիթմի ինչ-որ ձև՝ որպես ժամանակացույց
MLFQ որպես ելակետ:
Լրացուցիչ նյութեր.
- (հաշվարկ)
Source: www.habr.com