Օպերացիոն համակարգերի ներածություն
Հե՜յ Հաբր։ Ձեր ուշադրությանն եմ ներկայացնում իմ կարծիքով մեկ հետաքրքիր գրականության՝ OSTEP-ի հոդված-թարգմանությունների շարքը։ Այս նյութը բավականին խորը քննարկում է unix-ի նման օպերացիոն համակարգերի աշխատանքը, այն է՝ պրոցեսների, տարբեր ժամանակացույցերի, հիշողության և այլ նմանատիպ բաղադրիչների հետ աշխատանքը, որոնք կազմում են ժամանակակից ՕՀ: Բոլոր նյութերի բնօրինակը կարող եք տեսնել այստեղ . Խնդրում եմ նկատի ունենալ, որ թարգմանությունը կատարվել է ոչ պրոֆեսիոնալ (բավականին ազատ), բայց հուսով եմ պահպանել եմ ընդհանուր իմաստը։
Այս թեմայով լաբորատոր աշխատանք կարելի է գտնել այստեղ.
Այլ մասեր.
Կարող եք նաև դիտել իմ ալիքը =)
Ներածություն Scheduler
Խնդրի էությունը. Ինչպե՞ս մշակել ժամանակացույցի քաղաքականություն
Ինչպե՞ս պետք է նախագծվեն հիմնական ժամանակացույցի քաղաքականության շրջանակները: Որո՞նք պետք է լինեն հիմնական ենթադրությունները: Ինչ չափումներ են կարևոր: Ի՞նչ հիմնական մեթոդներ են օգտագործվել վաղ հաշվողական համակարգերում:
Աշխատանքային ծանրաբեռնվածության ենթադրություններ
Մինչ հնարավոր քաղաքականությունները քննարկելը, նախ մի քանի պարզեցնող շեղումներ անենք համակարգում ընթացող գործընթացների վերաբերյալ, որոնք միասին կոչվում են. ծանրաբեռնվածություն. Աշխատանքային ծանրաբեռնվածության սահմանումը շինարարության քաղաքականության կարևոր մասն է, և որքան ավելի շատ իմանաք ծանրաբեռնվածության մասին, այնքան ավելի լավ քաղաքականություն կարող եք գրել:
Համակարգում ընթացող գործընթացների մասին, որոնք երբեմն նաև կոչվում են, անենք հետևյալ ենթադրությունները Աշխատանք (առաջադրանքներ): Գրեթե բոլոր այս ենթադրությունները իրատեսական չեն, բայց անհրաժեշտ են մտքի զարգացման համար։
- Յուրաքանչյուր առաջադրանք աշխատում է նույն քանակությամբ ժամանակով,
- Բոլոր առաջադրանքները դրված են միաժամանակ,
- Հանձնարարված առաջադրանքն աշխատում է մինչև դրա ավարտը,
- Բոլոր առաջադրանքները օգտագործում են միայն պրոցեսոր,
- Յուրաքանչյուր առաջադրանքի կատարման ժամանակը հայտնի է:
Ժամանակացույցի չափումներ
Ի հավելումն ծանրաբեռնվածության մասին որոշ ենթադրությունների, անհրաժեշտ է նաև մեկ այլ գործիք՝ տարբեր պլանավորման քաղաքականությունների համեմատության համար՝ ժամանակացույցի չափումներ: Չափիչն ընդամենը ինչ-որ բանի չափանիշ է: Կան մի շարք չափումներ, որոնք կարող են օգտագործվել ժամանակացույցերը համեմատելու համար:
Օրինակ, մենք կօգտագործենք չափիչ, որը կոչվում է շրջադարձի ժամանակը (շրջադարձի ժամանակը): Առաջադրանքի կատարման ժամանակը սահմանվում է որպես առաջադրանքի ավարտի ժամանակի և համակարգում առաջադրանքի ժամանման ժամանակի տարբերությունը:
Tturnaround=TCompletion−Tarrival
Քանի որ մենք ենթադրում էինք, որ բոլոր առաջադրանքները գալիս են միաժամանակ, ապա Ta=0 և հետևաբար Tt=Tc: Այս արժեքը բնականաբար կփոխվի, երբ մենք փոխենք վերը նշված ենթադրությունները:
Մեկ այլ չափիչ - արդարություն (ազնվություն, ազնվություն): Արտադրողականությունը և արդարությունը հաճախ հակադիր բնութագրիչներ են պլանավորման մեջ: Օրինակ, ժամանակացույցը կարող է օպտիմալացնել կատարումը, բայց այլ առաջադրանքների կատարմանը սպասելու գնով, այդպիսով նվազեցնելով արդարությունը:
ԱՌԱՋԻՆԸ ԱՌԱՋԻՆ ԴՈՒՐՍՈՒՄ (FIFO)
Ամենատարրական ալգորիթմը, որը մենք կարող ենք իրականացնել, կոչվում է FIFO կամ առաջին գալ (ներս), առաջին սպասարկվել (դուրս գալ). Այս ալգորիթմը մի քանի առավելություն ունի. այն շատ հեշտ է իրագործվում և համապատասխանում է մեր բոլոր ենթադրություններին և բավականին լավ է կատարում աշխատանքը։
Եկեք նայենք մի պարզ օրինակի. Ասենք 3 առաջադրանք է դրվել միաժամանակ. Բայց ենթադրենք, որ A առաջադրանքը մի փոքր շուտ է եկել, քան մյուսները, ուստի այն կհայտնվի կատարման ցուցակում ավելի շուտ, քան մյուսները, ինչպես B-ն՝ C-ի համեմատ: Ենթադրենք, որ դրանցից յուրաքանչյուրը կկատարվի 10 վայրկյան: Որքա՞ն կլինի այս առաջադրանքները կատարելու միջին ժամանակը այս դեպքում:
Հաշվելով արժեքները՝ 10+20+30 և բաժանելով 3-ի, ստանում ենք ծրագրի կատարման միջին ժամանակը, որը հավասար է 20 վայրկյանի։
Հիմա փորձենք փոխել մեր ենթադրությունները։ Մասնավորապես, ենթադրություն 1, և, հետևաբար, մենք այլևս չենք ենթադրի, որ յուրաքանչյուր առաջադրանքի կատարման համար պահանջվում է նույն քանակությամբ ժամանակ: Ինչպե՞ս է հանդես գալու FIFO-ն այս անգամ:
Ինչպես պարզվում է, առաջադրանքների կատարման տարբեր ժամանակները չափազանց բացասական ազդեցություն են ունենում FIFO ալգորիթմի արտադրողականության վրա: Ենթադրենք, որ A առաջադրանքը կատարելու համար կպահանջվի 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 առաջադրանքների ժամանման պահին. դադարեցնել A առաջադրանքի կատարումը և B և C առաջադրանքները դնել մշակման և դրանց ավարտից հետո շարունակել կատարել A գործընթացը: Նման ժամանակացույցը կոչվում է. 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 վայրկյան, քանի որ որևէ այլ խնդիր զբաղեցրել է պրոցեսորը: Դա այնքան էլ հաճելի չէ:
Այսպիսով, մենք կանգնած ենք մեկ այլ խնդրի հետ. ինչպե՞ս կարող ենք ստեղծել ժամանակացույց, որը զգայուն է արձագանքման ժամանակի նկատմամբ:
Կլոր Robin
Այս խնդիրը լուծելու համար մշակվել է ալգորիթմ Կլոր Robin (RR): Հիմնական գաղափարը բավականին պարզ է. առաջադրանքները գործարկելու փոխարեն, մինչև դրանք ավարտվեն, մենք առաջադրանքը կաշխատենք որոշակի ժամանակահատվածով (կոչվում է ժամանակի հատված), այնուհետև հերթից կանցնենք այլ առաջադրանքի: Ալգորիթմը կրկնում է իր աշխատանքը մինչև բոլոր առաջադրանքները ավարտվեն: Այս դեպքում ծրագրի գործարկման ժամանակը պետք է լինի այն ժամանակի բազմապատիկը, որից հետո ժամանակաչափը կդադարեցնի գործընթացը: Օրինակ, եթե ժմչփն ընդհատում է գործընթացը յուրաքանչյուր x=10ms, ապա գործընթացի կատարման պատուհանի չափը պետք է լինի 10-ի բազմապատիկ և լինի 10,20 կամ x*10:
Դիտարկենք մի օրինակ. ABC առաջադրանքները միաժամանակ ժամանում են համակարգ և դրանցից յուրաքանչյուրը ցանկանում է աշխատել 5 վայրկյան: SJF ալգորիթմը կավարտի յուրաքանչյուր առաջադրանքը մյուսը սկսելուց առաջ: Ի հակադրություն, RR ալգորիթմը գործարկման պատուհանով = 1s կանցնի առաջադրանքների միջով հետևյալ կերպ (նկ. 4.3).
(Նորից SJF (Վատ արձագանքման ժամանակի համար)
(Round Robin (Լավ է արձագանքման ժամանակի համար)
RR ալգորիթմի միջին արձագանքման ժամանակը (0+1+2)/3=1 է, մինչդեռ SJF (0+5+10)/3=5:
Տրամաբանական է ենթադրել, որ ժամանակի պատուհանը շատ կարևոր պարամետր է RR-ի համար, որքան փոքր է այն, այնքան բարձր է արձագանքման ժամանակը: Այնուամենայնիվ, դուք չպետք է այն չափազանց փոքր դարձնեք, քանի որ համատեքստի փոխարկման ժամանակը նույնպես դեր կխաղա ընդհանուր կատարման մեջ: Այսպիսով, կատարման պատուհանի ժամանակի ընտրությունը սահմանվում է OS ճարտարապետի կողմից և կախված է այն առաջադրանքներից, որոնք նախատեսվում է կատարել դրանում: Համատեքստի փոխարկումը միակ սպասարկման գործողությունը չէ, որը ժամանակ է վատնում. գործող ծրագիրը գործում է շատ այլ բաների վրա, օրինակ՝ տարբեր քեշերի վրա, և յուրաքանչյուր փոխարկիչով անհրաժեշտ է պահպանել և վերականգնել այս միջավայրը, որը կարող է նաև շատ պահանջել: ժամանակ.
RR-ն հիանալի ժամանակացույց է, եթե մենք խոսում էինք միայն արձագանքման ժամանակի չափման մասին: Բայց ինչպե՞ս կվարվի առաջադրանքի կատարման ժամանակի չափումը այս ալգորիթմի հետ: Դիտարկենք վերը նշված օրինակը, երբ A, B, C-ի գործառնական ժամանակը = 5s է և հասնում է միաժամանակ: A առաջադրանքը կավարտվի 13-ին, B-ին՝ 14-ին, C-ին՝ 15-ին, իսկ շրջադարձի միջին ժամանակը կլինի 14 վրկ: Այսպիսով, RR-ն շրջանառության չափման ամենավատ ալգորիթմն է:
Ավելի ընդհանուր ձևով, RR տիպի ցանկացած ալգորիթմ արդար է, այն հավասարապես բաժանում է պրոցեսորի ժամանակը բոլոր գործընթացների միջև: Եվ այսպիսով, այս ցուցանիշները մշտապես հակասում են միմյանց:
Այսպիսով, մենք ունենք մի քանի հակադրվող ալգորիթմներ, և միևնույն ժամանակ դեռ մի քանի ենթադրություն է մնացել, որ առաջադրանքի ժամանակը հայտնի է, և որ առաջադրանքը օգտագործում է միայն պրոցեսորը:
I/O-ի հետ խառնում
Նախ, եկեք հանենք 4-րդ ենթադրությունը, որ գործընթացը օգտագործում է միայն պրոցեսորը, բնականաբար, դա այդպես չէ, և գործընթացները կարող են մուտք գործել այլ սարքավորումներ:
Այն պահին, երբ որևէ գործընթաց պահանջում է I/O գործողություն, գործընթացը մտնում է արգելափակված վիճակ՝ սպասելով I/O-ի ավարտին: Եթե I/O ուղարկվում է կոշտ սկավառակ, ապա նման գործողությունը կարող է տևել մինչև մի քանի ms կամ ավելի երկար, և պրոցեսորն այս պահին անգործուն կմնա: Այս ընթացքում ժամանակացույցը կարող է զբաղեցնել պրոցեսորը ցանկացած այլ գործընթացով: Հաջորդ որոշումը, որը ժամանակացույցը պետք է կայացնի, այն է, թե երբ գործընթացը կավարտի իր I/O-ն: Երբ դա տեղի ունենա, տեղի կունենա ընդհատում, և ՕՀ-ն պատրաստի վիճակի կդնի գործընթացը, որը կանչել է I/O:
Դիտարկենք մի քանի առաջադրանքների օրինակ: Նրանցից յուրաքանչյուրը պահանջում է 50 մս պրոցեսորի ժամանակ: Այնուամենայնիվ, առաջինը մուտք կգործի I/O յուրաքանչյուր 10ms-ում (որը նույնպես կկատարվի յուրաքանչյուր 10ms-ում): Իսկ B պրոցեսը պարզապես օգտագործում է 50ms պրոցեսոր առանց I/O-ի:
Այս օրինակում մենք կօգտագործենք STCF ժամանակացույցը: Ինչպե՞ս կվարվի ժամանակացույցը, եթե դրա վրա գործարկվի այնպիսի գործընթաց, ինչպիսին A-ն է: Նա կանի հետեւյալը՝ սկզբում ամբողջությամբ կմշակի Ա պրոցեսը, հետո կմշակի Բ-ն։
Այս խնդրի լուծման ավանդական մոտեցումը Ա գործընթացի յուրաքանչյուր 10 ms ենթաառաջադրանքը որպես առանձին առաջադրանք դիտարկելն է: Այսպիսով, STJF ալգորիթմից սկսելիս ընտրությունը 50 մվ առաջադրանքի և 10 մվ առաջադրանքի միջև ակնհայտ է։ Այնուհետև, երբ A ենթաառաջադրանքը ավարտվի, B պրոցեսը և I/O կգործարկվեն: I/O-ի ավարտից հետո ընդունված կլինի նորից սկսել 10ms պրոցեսը A պրոցեսը B-ի փոխարեն: Այս կերպ հնարավոր է իրականացնել համընկնումը, որտեղ պրոցեսորն օգտագործվում է մեկ այլ գործընթացի կողմից, մինչ առաջինը սպասում է գործընթացին: I/O. Եվ արդյունքում համակարգը ավելի լավ է օգտագործվում. այն պահին, երբ ինտերակտիվ գործընթացները սպասում են I/O-ին, պրոցեսորի վրա կարող են իրականացվել այլ պրոցեսներ։
Oracle-ն այլևս չկա
Այժմ փորձենք ազատվել այն ենթադրությունից, որ առաջադրանքի կատարման ժամանակը հայտնի է։ Սա ընդհանուր առմամբ ամենավատ և ամենաանիրատեսական ենթադրությունն է ամբողջ ցուցակում: Իրականում, միջին սովորական ՕՀ-ում ՕՀ-ն ինքը սովորաբար շատ քիչ բան գիտի առաջադրանքների կատարման ժամանակի մասին, այդ դեպքում ինչպե՞ս կարող եք ժամանակացույց կառուցել՝ առանց իմանալու, թե որքան ժամանակ կպահանջվի առաջադրանքի կատարման համար: Միգուցե մենք կարող ենք օգտագործել որոշ RR սկզբունքներ այս խնդիրը լուծելու համար:
Լրիվ
Մենք դիտարկեցինք առաջադրանքների ժամանակացույցի հիմնական գաղափարները և դիտարկեցինք ժամանակացույցների 2 ընտանիք: Առաջինը սկզբում սկսում է ամենակարճ առաջադրանքը և դրանով իսկ մեծացնում շրջադարձի ժամանակը, իսկ երկրորդը հավասարապես բաժանվում է բոլոր առաջադրանքների միջև՝ մեծացնելով պատասխանի ժամանակը: Երկու ալգորիթմներն էլ վատն են, որտեղ մյուս ընտանիքի ալգորիթմները լավն են: Մենք նաև նայեցինք, թե ինչպես կարող է CPU-ի և I/O-ի զուգահեռ օգտագործումը բարելավել կատարումը, բայց չլուծեցինք ՕՀ-ի խորաթափանցության խնդիրը: Եվ հաջորդ դասում մենք կանդրադառնանք պլանավորողին, որը նայում է անմիջական անցյալին և փորձում է գուշակել ապագան: Եվ դա կոչվում է բազմամակարդակ հետադարձ կապի հերթ:
Source: www.habr.com