Վերջերս չօգտագործված (NRU) էջի փոխարինման ալգորիթմ

Օպերացիոն համակարգերը օգտագործում են Not Recently Used (NRU) էջի փոխարինման ալգորիթմը որպես էջի փոխարինման հիմնարար մարտավարություն հիշողությունը կառավարելու համար: Դրա հիմնական նպատակն է գտնել և հեռացնել հիշողությունից այն էջերը, որոնք երկար ժամանակ մուտք չեն գործել:

Այս հոդվածում մենք կքննարկենք NRU էջի փոխարինման ալգորիթմը, դրա դասերը, ներգրավված քայլերը, օգտագործման դեպքերը և նաև դրա առավելությունները:

NRU ալգորիթմի դասեր

Ելնելով դրանց օգտագործման կամ հղման բիթից՝ NRU ալգորիթմով էջերը բաժանվում են չորս դասերի.

Դաս 0− Քանի որ դրանք բեռնված են հիշողության մեջ, էջերը չեն կարող հղում կատարել (մուտք գործել) կամ փոփոխել (գրել):

Դաս 1− Էջեր, որոնք փոփոխության են ենթարկվել հիշողության մեջ բեռնվելիս, բայց չեն հղում կատարել:

Դաս 2− Էջեր, որոնք օգտագործվել են որպես հղումներ, բայց չեն փոխվել:

դաս 3− Փոփոխված և մեջբերված էջերը ընկնում են տակ:

Յուրաքանչյուր էջի հղման բիթը սովորաբար պարբերաբար զրոյացվում է՝ օգտագործելով NRU մեթոդը՝ օգտագործելով ժամացույց կամ ժամանակաչափ սարք: Մեթոդը վերլուծում է հիշողության յուրաքանչյուր էջը, նախքան ժամացույցի յուրաքանչյուր ցուցիչի կամ ժամանակաչափի ընդհատման վրա հեռացնելու համար ընտրելը՝ յուրաքանչյուր էջ դասակարգելով իր հղումների հիման վրա և փոփոխելով բիթերը:

NRU-ում ընտրության ընթացակարգը ենթադրում է փնտրել ամենացածր համարակալված ոչ դատարկ դասը և պատահականորեն հեռացնել էջը այդ դասից: Մեթոդը առաջնահերթություն է տալիս վերջերս չօգտագործված էջերի հեռացմանը` ընտրելով ամենացածր համարակալված դասը, ավելացնելով քիչ կարևոր կամ քիչ հաճախ օգտագործվող կայքերը հեռացնելու հնարավորությունը:

Երբ ավելի բարդ ալգորիթմները, ինչպիսիք են ամենաքիչ վերջերս օգտագործվածը (LRU) անիրագործելի են իրականացման սահմանափակումների պատճառով, հատկապես սահմանափակ ռեսուրսներով համակարգերում, NRU-ն ողջամտորեն հիմնական և արդյունավետ էջի փոխարինման մեխանիզմ է, որը կարող է օգտագործվել: Կարևոր է նկատի ունենալ, որ NRU-ն հաշվի չի առնում էջի հղումները, և որ նրա պատահական վտարման քաղաքականությունը միշտ չէ, որ կարող է լավագույն արդյունք տալ:

Քայլեր NRU ալգորիթմում

Հետևյալ քայլերը հիմք են հանդիսանում այն բանի, թե ինչպես է աշխատում NRU (Վերջերս չօգտագործված) էջի փոխարինման մեխանիզմը

• Հիշողության յուրաքանչյուր էջի վրա տրվում է հղման բիթ (R) և փոփոխված բիթ (M): Սովորաբար, էջի աղյուսակի յուրաքանչյուր մուտքը պարունակում է այս մասերը:

• Ալգորիթմը սկսում է NRU-ի ընտրության ընթացակարգը կանոնավոր ընդմիջումներով կամ ի պատասխան նշված իրադարձությունների (օրինակ՝ ժամացույցի տիկերը կամ ժամանակաչափի ընդհատումները):

• Հիմնվելով նրանց R և M բիթերի վրա՝ ալգորիթմը դասավորում է հիշողության մեջ եղած բոլոր էջերը հետևյալ չորս դասերից մեկի մեջ.

  Դաս 0− Էջերն ունեն R և M 0 արժեքներ:

  Դաս 1− Էջերն ունեն R=0 և M=1:

  2-րդ դաս− տարիք, որտեղ R=1 և M=0:

  Դաս 3− Էջեր, որտեղ R և M-ը հավասար են 1-ի:

• Ալգորիթմով ընտրվում է էջը վտարման համար էջերի դասակարգումից հետո: Այն սկսվում է ամենացածր թվով դասը փնտրելով, որը դատարկ չէ: Ալգորիթմը նպաստում է դասին ավելի քիչ թվով էջերով, երբ կան բազմաթիվ դասեր: Օրինակ, 0 դասը կընտրվեր, եթե և՛ 0, և՛ 1 դասը էջեր ունենային:

• Ծրագիրը պատահականորեն ընտրում է էջ՝ նշանակված դասից հեռացնելու համար: Դա կարելի է անել՝ պատահականորեն ընտրելով էջը դասի բոլոր էջերի վրա կրկնելուց հետո կամ օգտագործելով պատահական թվերի գեներատոր:

• Անհրաժեշտության դեպքում փոխարինող էջը կարող է բեռնվել, երբ ընտրված էջը հեռացվի հիշողությունից: Համապատասխան փոփոխություն է կատարվում համապատասխան էջի աղյուսակի մուտքագրում:

• Ի վերջո, հաջորդ ընտրության ցիկլին պատրաստվելու համար հիշողության մնացած բոլոր էջերը մաքրվում են իրենց հղման բիթերը (R) (սահմանված է 0):

NRU-ն փորձում է ջնջել այն էջերը, որոնք ավելի քիչ հավանական է, որ անհրաժեշտ լինեն մոտ ապագայում՝ պարբերաբար սկանավորելով և հեռացնելով այն էջերը, որոնք դեռ պետք է օգտագործվեն (այսինքն՝ ունենալով 0-ի հղման բիթ): NRU-ն հաշվի չի առնում էջի հղումների հաճախականությունը, ինչը որոշ հանգամանքներում կարող է հանգեցնել ոչ իդեալական կատարման:

Ահա NRU ալգորիթմի հոսքի աղյուսակը–

Օգտագործեք NRU էջի փոխարինման ալգորիթմի դեպքեր

Եկեք ուսումնասիրենք գործառնական համակարգերում ոչ հարակից տեղաբաշխման որոշ օգտագործման դեպքեր:

• Փոփոխական չափի գործընթացներ − Ոչ հարակից բաշխումը հատկապես օգտակար է, երբ գործ ունենք տարբեր չափերի գործընթացների հետ: Այն թույլ է տալիս հիշողությունը տարածել մի քանի շրջանների միջև՝ հնարավորություն տալով արդյունավետ օգտագործել առկա հիշողությունը:

• Հիշողության դինամիկ կառավարում − Ոչ հարակից տեղաբաշխումը հնարավորություն է տալիս հիշողության դինամիկ կառավարումը՝ թույլ տալով հիշողությունը բաշխել և տեղաբաշխել՝ ի պատասխան գործողությունների մեկնարկի կամ դադարեցման: Այս ճկունությունը կարևոր է այն միջավայրերում, որտեղ գործընթացները փոփոխվող հիշողության պահանջներ ունեն:

• Հիշողության արդյունավետ օգտագործում − Ոչ հարակից տեղաբաշխումն ապահովում է հիշողության արդյունավետ օգտագործումը` բաշխելով հիշողության բլոկները` ըստ գործընթացների իրական կարիքների: Այն կանխում է հիշողության վատնումը՝ յուրաքանչյուր գործընթացի համար հատկացնելով միայն անհրաժեշտ քանակությամբ հիշողություն:

• Կտրատման կառավարում − Թեև ոչ հարակից բաշխումը կարող է մեծացնել արտաքին մասնատումը, այն օգնում է նվազեցնել ներքին մասնատումը: Ներքին մասնատումը տեղի է ունենում, երբ հատկացված հիշողության բլոկները դատարկ կամ մասամբ օգտագործված տարածք ունեն: Գործընթացների հատուկ կարիքների հիման վրա հիշողության բլոկների տեղաբաշխմամբ՝ ներքին մասնատումը նվազագույնի է հասցվում:

• Մեծ տվյալների շտեմարանների կառավարում − Ոչ հարակից բաշխումը շահավետ է, երբ գործ ունենք տվյալների մեծ հավաքածուների հետ, որոնք չեն կարող տեղավորվել մեկ հարակից հիշողության բլոկի մեջ: Հիշողությունը մի քանի ոչ հարակից բլոկներում տեղաբաշխելու ունակությունը թույլ է տալիս գործընթացներին աշխատել ընդարձակ տվյալների հետ՝ առանց սպառելու առկա հիշողության ռեսուրսները:

• Վիրտուալ հիշողության համակարգեր − Ոչ հարակից տեղաբաշխումը հիմնարար տեխնիկա է, որն օգտագործվում է վիրտուալ հիշողության համակարգերում: Այն թույլ է տալիս օպերացիոն համակարգին ճկուն կերպով քարտեզագրել տրամաբանական հասցեները ֆիզիկական հասցեներին՝ հնարավորություն տալով գործընթացներին մուտք գործել հիշողություն ոչ հարակից ձևով:

• Բազմակի ծրագրավորման միջավայրեր − Բազմածրագրավորման միջավայրերում, որտեղ միաժամանակ մի քանի գործընթացներ են աշխատում, ոչ հարակից տեղաբաշխումն օգնում է արդյունավետ կերպով տեղաբաշխել հիշողության բլոկները տարբեր գործընթացներին: Յուրաքանչյուր գործընթացին կարող է վերագրվել հիշողություն՝ ելնելով իր հատուկ պահանջներից, ինչը թույլ է տալիս հիշողության օպտիմալ օգտագործումը:

• Իրական ժամանակի համակարգեր – Ոչ հարակից բաշխումը կարող է օգտակար լինել իրական ժամանակի համակարգերում, որտեղ գործընթացներն ունեն ժամանակի խիստ պահանջներ: Այն թույլ է տալիս հիշողության բաշխումը և տեղաբաշխումը դինամիկ կերպով՝ հնարավորություն տալով գործընթացներին արդյունավետորեն կառավարել իրենց հիշողության ռեսուրսները՝ միաժամանակ համապատասխանելով խիստ ժամանակային սահմանափակումներին:

  Օգտագործելով ոչ հարակից տեղաբաշխում, օպերացիոն համակարգերը կարող են բավարարել գործընթացների հիշողության տարատեսակ կարիքները, խթանել հիշողության արդյունավետ օգտագործումը և ապահովել ճկունություն, որն անհրաժեշտ է տարբեր աշխատանքային ծանրաբեռնվածության և տվյալների չափերի համար:

NRU էջի փոխարինման ալգորիթմի առավելությունները

Որոշ հանգամանքներում NRU (ոչ վերջերս օգտագործված) էջի փոխարինման մեխանիզմն առաջարկում է մի շարք առավելություններ: Ահա NRU ալգորիթմի մի քանի առավելություններ–

Պարզություն − NRU-ն համեմատաբար հեշտ իրագործելի էջի փոխարինման մեթոդ է: Օրինակ, NRU-ի պարզությունը կարող է օգնել ներկառուցված համակարգերին կամ հին սարքավորումներին հիշողության սահմանափակումներով:

Հազվադեպ այցելվող էջերի նախապատվությունը − NRU-ն առաջնահերթություն է տալիս հազվադեպ այցելվող էջերի հեռացմանը: NRU-ն կարող է օգնել ապահովել, որ ավելի քիչ օգտագործվող էջերը առաջին հերթին հեռացվեն՝ տարածք ստեղծելով ավելի ակտիվորեն օգտագործվող էջերի համար, մի համակարգում, որտեղ որոշակի հավելված կամ տվյալների հավաքածու հազվադեպ է օգտագործվում, սակայն պահանջում է զգալի քանակությամբ հիշողություն:

Արագ հարմարվողականություն մուտքի օրինաչափությունների փոփոխմանը − Արագ հարմարվողականությունը փոփոխվող մուտքի օրինաչափություններին հնարավոր է դարձնում NRU-ն, որն առաջարկում է դա անելու պարզ տեխնիկա: Սա թույլ է տալիս ալգորիթմին փոփոխել, թեև կոպիտ կերպով, իր վտարման որոշումները՝ կախված մուտքի ամենավերջին օրինաչափություններից:

Պատահական վտարում − Որպեսզի ընտրի, թե որ էջը պետք է հեռացվի յուրաքանչյուր դասից, NRU-ն օգտագործում է պատահական ընտրության տեխնիկա: Բացի այդ, այն կարող է վտարումները դարձնել ավելի քիչ կանխատեսելի՝ ավելի դժվարացնելով վնասակար ծրագրերի համար օգտվել վտարման որոշակի օրինաչափություններից:

Եզրակացություն

NRU (Վերջերս օգտագործված) էջերի փոխարինման տեխնիկան պարզ է, պահանջում է փոքր ծախսեր և թույլ է տալիս առաջնահերթություն տալ հազվադեպ օգտագործվող էջերը հեռացնելու համար: Այն կառուցելու համար պարզ ալգորիթմ է, որը հարմար է դարձնում նվազագույն ռեսուրսներով կամ հանգամանքներով համակարգերի համար, որոնցում ավելի բարդ ալգորիթմներն անիրագործելի են: Պարբերաբար վերակայելով հղման բիթերը՝ NRU-ն կարող է հարմարվել մուտքի օրինաչափությունների փոփոխմանը: Պատահականացումն օգտագործվում է նաև էջի հեռացման ժամանակ՝ վտարման բեռը տարածելու և կանխատեսելիությունից խուսափելու համար: