Sahifa almashtirish algoritmlari - Operatsion tizimlar

RAM to'ldi, yangi sahifa kerak. Qaysi birini chiqaramiz? Bu tanlov tizim tezligini o'nlab barobar o'zgartirishi mumkin.

Masalaning qo'yilishi #

Noto'g'ri tanlov - keyingi so'rovda yana disk kutish

Sinov satri #

Barcha algoritmlarni bir xil murojaat satrida sinaymiz - bu darslikdagi klassik ketma-ketlik:

Natija

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Ramkalar soni: 3 ta.

FIFO - birinchi kelgan birinchi chiqadi #

#include <stdio.h>

#define RAMKA   3
#define SOROV   20

static const int satr[SOROV] = {
    7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
    0, 3, 2, 1, 2, 0, 1, 7, 0, 1
};

int main(void) {
    int ramka[RAMKA];
    int keyingi = 0;               /* navbatdagi qurbon */
    int xato = 0;

    for (int i = 0; i < RAMKA; i++) {
        ramka[i] = -1;
    }

    printf("So'rov | Ramkalar  | Holat\n");
    printf("-------+-----------+------------\n");

    for (int i = 0; i < SOROV; i++) {
        int sahifa = satr[i];
        int topildi = 0;

        for (int j = 0; j < RAMKA; j++) {
            if (ramka[j] == sahifa) {
                topildi = 1;
                break;
            }
        }

        if (!topildi) {
            ramka[keyingi] = sahifa;
            keyingi = (keyingi + 1) % RAMKA;
            xato++;
        }

        printf("  %2d   | ", sahifa);

        for (int j = 0; j < RAMKA; j++) {
            if (ramka[j] == -1) {
                printf(" . ");
            } else {
                printf("%2d ", ramka[j]);
            }
        }

        printf("| %s\n", topildi ? "topildi" : "XATO");
    }

    printf("\nJami sahifa xatolari: %d / %d\n", xato, SOROV);

    return 0;
}

Natija

So'rov | Ramkalar  | Holat
-------+-----------+------------
   7   |  7  .  . | XATO
   0   |  7  0  . | XATO
   1   |  7  0  1 | XATO
   2   |  2  0  1 | XATO
   0   |  2  0  1 | topildi
   3   |  2  3  1 | XATO
   0   |  2  3  0 | XATO
   4   |  4  3  0 | XATO
   2   |  4  2  0 | XATO
   3   |  4  2  3 | XATO
   0   |  0  2  3 | XATO
   3   |  0  2  3 | topildi
   2   |  0  2  3 | topildi
   1   |  0  1  3 | XATO
   2   |  0  1  2 | XATO
   0   |  0  1  2 | topildi
   1   |  0  1  2 | topildi
   7   |  7  1  2 | XATO
   0   |  7  0  2 | XATO
   1   |  7  0  1 | XATO

Jami sahifa xatolari: 15 / 20

Optimal - kelajakni biluvchi algoritm #

#include <stdio.h>

#define RAMKA   3
#define SOROV   20

static const int satr[SOROV] = {
    7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
    0, 3, 2, 1, 2, 0, 1, 7, 0, 1
};

/* Ramkadagi qaysi sahifa eng uzoq kelajakda kerak bo'ladi? */
static int qurbon_tanlash(const int *ramka, int hozir) {
    int eng_uzoq = -1;
    int tanlangan = 0;

    for (int j = 0; j < RAMKA; j++) {
        int qachon = SOROV + 1;          /* umuman kerak bo'lmasa */

        for (int k = hozir + 1; k < SOROV; k++) {
            if (satr[k] == ramka[j]) {
                qachon = k;
                break;
            }
        }

        if (qachon > eng_uzoq) {
            eng_uzoq = qachon;
            tanlangan = j;
        }
    }

    return tanlangan;
}

int main(void) {
    int ramka[RAMKA];
    int band = 0;
    int xato = 0;

    for (int i = 0; i < RAMKA; i++) {
        ramka[i] = -1;
    }

    for (int i = 0; i < SOROV; i++) {
        int sahifa = satr[i];
        int topildi = 0;

        for (int j = 0; j < band; j++) {
            if (ramka[j] == sahifa) {
                topildi = 1;
                break;
            }
        }

        if (!topildi) {
            if (band < RAMKA) {
                ramka[band++] = sahifa;
            } else {
                ramka[qurbon_tanlash(ramka, i)] = sahifa;
            }

            xato++;
        }
    }

    printf("Optimal algoritm\n");
    printf("Sahifa xatolari: %d / %d\n", xato, SOROV);
    printf("FIFO dan yaxshiroqmi? %s\n", xato < 15 ? "ha" : "yo'q");

    return 0;
}

Natija

Optimal algoritm
Sahifa xatolari: 9 / 20
FIFO dan yaxshiroqmi? ha

Optimal algoritmni amalda qo'llab bo'lmaydi

U kelajakdagi murojaatlarni oldindan bilishni talab qiladi. Haqiqiy tizimda bu ma'lumot yo'q.

Lekin u baribir foydali - etalon sifatida. Har qanday yangi algoritmni baholashda: "Optimalga qanchalik yaqin?" degan savol beriladi.

Bizning satrimizda:

Algoritm	Xatolar
Optimal	9
LRU	12
FIFO	15

LRU Optimalga ancha yaqin - shuning uchun u amalda ishlatiladi.

LRU - eng uzoq ishlatilmagan #

#include <stdio.h>

#define RAMKA   3
#define SOROV   20

static const int satr[SOROV] = {
    7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
    0, 3, 2, 1, 2, 0, 1, 7, 0, 1
};

int main(void) {
    int ramka[RAMKA];
    int oxirgi[RAMKA];             /* oxirgi murojaat vaqti */
    int band = 0;
    int xato = 0;

    for (int i = 0; i < RAMKA; i++) {
        ramka[i] = -1;
        oxirgi[i] = -1;
    }

    for (int i = 0; i < SOROV; i++) {
        int sahifa = satr[i];
        int joy = -1;

        for (int j = 0; j < band; j++) {
            if (ramka[j] == sahifa) {
                joy = j;
                break;
            }
        }

        if (joy >= 0) {
            oxirgi[joy] = i;                    /* yangilaymiz */
            continue;
        }

        xato++;

        if (band < RAMKA) {
            ramka[band] = sahifa;
            oxirgi[band] = i;
            band++;
            continue;
        }

        /* Eng eski murojaatli ramkani topamiz */
        int qurbon = 0;

        for (int j = 1; j < RAMKA; j++) {
            if (oxirgi[j] < oxirgi[qurbon]) {
                qurbon = j;
            }
        }

        ramka[qurbon] = sahifa;
        oxirgi[qurbon] = i;
    }

    printf("LRU algoritmi\n");
    printf("Sahifa xatolari: %d / %d\n", xato, SOROV);
    printf("Optimal (9) va FIFO (15) orasidami? %s\n",
           xato > 9 && xato < 15 ? "ha" : "yo'q");

    return 0;
}

Natija

LRU algoritmi
Sahifa xatolari: 12 / 20
Optimal (9) va FIFO (15) orasidami? ha

LRU nima uchun ishlaydi

U vaqtinchalik lokallik (temporal locality) prinsipiga tayanadi: yaqinda ishlatilgan sahifa yaqin kelajakda ham ishlatilishi ehtimoli yuqori.

Bu haqiqatan dasturlarning tabiatiga mos:

Sikldagi kod qayta-qayta bajariladi;
Funksiya lokal o'zgaruvchilari qisqa vaqtda ko'p ishlatiladi;
Ma'lumot strukturalari guruh-guruh o'qiladi.

Muammo: haqiqiy LRU ni apparatda amalga oshirish qimmat. Har bir xotira murojaatida vaqt tamg'asini yangilash kerak - bu tizimni sekinlashtiradi.

Shuning uchun amalda taqriban LRU ishlatiladi - Clock algoritmi.

Clock (ikkinchi imkoniyat) algoritmi #

Clock - LRU ning arzon taqribi, deyarli barcha OT da ishlatiladi

#include <stdio.h>

#define RAMKA   3
#define SOROV   20

static const int satr[SOROV] = {
    7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
    0, 3, 2, 1, 2, 0, 1, 7, 0, 1
};

int main(void) {
    int ramka[RAMKA];
    int murojaat[RAMKA];           /* R biti */
    int korsatkich = 0;
    int band = 0;
    int xato = 0;
    int aylanish = 0;              /* nechta qadam tashlandi */

    for (int i = 0; i < RAMKA; i++) {
        ramka[i] = -1;
        murojaat[i] = 0;
    }

    for (int i = 0; i < SOROV; i++) {
        int sahifa = satr[i];
        int joy = -1;

        for (int j = 0; j < band; j++) {
            if (ramka[j] == sahifa) {
                joy = j;
                break;
            }
        }

        if (joy >= 0) {
            murojaat[joy] = 1;                  /* apparat qo'yadi */
            continue;
        }

        xato++;

        if (band < RAMKA) {
            ramka[band] = sahifa;
            murojaat[band] = 1;
            band++;
            continue;
        }

        /* Soat strelkasini aylantiramiz */
        while (murojaat[korsatkich] == 1) {
            murojaat[korsatkich] = 0;           /* ikkinchi imkoniyat */
            korsatkich = (korsatkich + 1) % RAMKA;
            aylanish++;
        }

        ramka[korsatkich] = sahifa;
        murojaat[korsatkich] = 1;
        korsatkich = (korsatkich + 1) % RAMKA;
    }

    printf("Clock algoritmi\n");
    printf("Sahifa xatolari : %d / %d\n", xato, SOROV);
    printf("Tashlangan qadam: %d\n", aylanish);
    printf("FIFO (15) dan yomon emasmi? %s\n", xato <= 15 ? "ha" : "yo'q");

    return 0;
}

Natija

Clock algoritmi
Sahifa xatolari : 14 / 20
Tashlangan qadam: 16
FIFO (15) dan yomon emasmi? ha

Clock ni Linux qanday takomillashtirgan

Linux ikki ro'yxatli (active/inactive) LRU ishlatadi:

Ro'yxat	Mazmuni
Active	Yaqinda bir necha marta ishlatilgan sahifalar
Inactive	Bir marta ishlatilgan yoki eskirgan sahifalar

Yangi sahifa inactive ro'yxatiga tushadi. Agar u yana ishlatilsa - active ga ko'tariladi.

Chiqarish har doim inactive ro'yxatining oxiridan boshlanadi.

Bu bir marta o'qiladigan katta fayl (masalan cp bilan nusxalash) butun keshni buzib yuborishining oldini oladi.

Belady anomaliyasi #

#include <stdio.h>

#define SOROV 12

static const int satr[SOROV] = {
    1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
};

static int fifo_xatolari(int ramkalar) {
    int ramka[10];
    int keyingi = 0;
    int xato = 0;

    for (int i = 0; i < ramkalar; i++) {
        ramka[i] = -1;
    }

    for (int i = 0; i < SOROV; i++) {
        int topildi = 0;

        for (int j = 0; j < ramkalar; j++) {
            if (ramka[j] == satr[i]) {
                topildi = 1;
                break;
            }
        }

        if (!topildi) {
            ramka[keyingi] = satr[i];
            keyingi = (keyingi + 1) % ramkalar;
            xato++;
        }
    }

    return xato;
}

int main(void) {
    int uch = fifo_xatolari(3);
    int tort = fifo_xatolari(4);

    printf("FIFO, 3 ramka: %d ta xato\n", uch);
    printf("FIFO, 4 ramka: %d ta xato\n", tort);
    printf("\nRamka ko'paydi, lekin xato ham ko'paydimi? %s\n",
           tort > uch ? "ha - Belady anomaliyasi!" : "yo'q");

    return 0;
}

Natija

FIFO, 3 ramka: 9 ta xato
FIFO, 4 ramka: 10 ta xato

Ramka ko'paydi, lekin xato ham ko'paydimi? ha - Belady anomaliyasi!

Belady anomaliyasi

Ko'proq RAM qo'shsangiz, tizim sekinroq ishlashi mumkin. Bu mantiqqa zid ko'rinadi, lekin FIFO uchun isbotlangan haqiqat.

Sabab: FIFO sahifaning qanchalik kerakligini hisobga olmaydi - u faqat yoshiga qaraydi. Ramka ko'payganda navbat tartibi shunday o'zgaradiki, kerakli sahifalar aynan kerak bo'lishidan oldin chiqarilib ketadi.

Stek algoritmlari (LRU, Optimal) bu anomaliyaga uchramaydi. Ularda quyidagi xossa bor: N ramkadagi sahifalar to'plami har doim N+1 ramkadagi to'plamning qism to'plami bo'ladi.

Bu FIFO ni amalda ishlatmaslikning yana bir sababi.

Thrashing - halokatli holat #

Chegaradan o'tilsa, tizim samaradorligi keskin qulaydi

Thrashing belgilarini tanish

Thrashing - jarayonlar sahifalarni bir-birining qo'lidan tortib oladigan holat. Har biri o'z ishini boshlashi bilan sahifasi chiqarilib ketadi.

Belgilar:

Belgi	Buyruq
CPU bo'sh, lekin tizim "qotgan"	`top` da `%wa` yuqori
Disk to'xtovsiz ishlaydi	`iostat -x 1`
Qattiq sahifa xatolari ko'p	`vmstat 1` da `si`/`so`
Swap to'lgan	`free -h`

Terminal

vmstat 1 3

Natija

procs -----------memory---------- ---swap-- -----io----
 r  b   swpd   free   buff  cache   si   so    bi    bo
 4  9 8123456  51200  2048  98304 4521  3987 18432 15104

si (swap in) va so (swap out) nolga yaqin bo'lishi kerak. Yuqoridagi qiymatlar - klassik thrashing.

Yechim: RAM qo'shish, jarayonlar sonini kamaytirish, yoki xotira sarfini optimallash. Swap ni o'chirish yechim emas - u faqat OOM Killer ni tezlashtiradi.

Ish to'plami (working set) #

#include <stdio.h>

#define SOROV  20
#define OYNA    5              /* ish to'plami oynasi */

static const int satr[SOROV] = {
    1, 2, 1, 2, 1, 2, 7, 8, 9, 8,
    7, 8, 9, 1, 2, 1, 2, 1, 2, 1
};

int main(void) {
    printf("Vaqt | Oyna ichidagi sahifalar | Ish to'plami hajmi\n");
    printf("-----+-------------------------+-------------------\n");

    for (int i = OYNA - 1; i < SOROV; i += 4) {
        int korilgan[16] = {0};
        int hajm = 0;

        for (int k = i - OYNA + 1; k <= i; k++) {
            if (!korilgan[satr[k]]) {
                korilgan[satr[k]] = 1;
                hajm++;
            }
        }

        printf(" %2d  | ", i);

        for (int k = i - OYNA + 1; k <= i; k++) {
            printf("%d ", satr[k]);
        }

        printf("             | %d ta\n", hajm);
    }

    printf("\nIsh to'plami o'zgaruvchan - dastur bosqichlariga bog'liq\n");

    return 0;
}

Natija

Vaqt | Oyna ichidagi sahifalar | Ish to'plami hajmi
-----+-------------------------+-------------------
  4  | 1 2 1 2 1              | 2 ta
  8  | 1 2 7 8 9              | 5 ta
 12  | 9 8 7 8 9              | 3 ta
 16  | 9 1 2 1 2              | 3 ta

Ish to'plami o'zgaruvchan - dastur bosqichlariga bog'liq

Ish to'plami nazariyasi

Ish to'plami - jarayonning oxirgi T murojaatda ishlatgan sahifalari to'plami.

Asosiy qoida: agar jarayonning butun ish to'plami RAM da bo'lsa, u kam sahifa xatosi bilan tez ishlaydi. Agar bo'lmasa - thrashing.

OT shunday siyosat yuritadi:

Har bir jarayonning ish to'plami hajmini baholaydi;
Ularning yig'indisi mavjud ramkalardan ko'p bo'lsa;
Jarayonlardan birini butunlay to'xtatib, xotirasini bo'shatadi (swapping).

Bu "hammaga ozdan" berishdan yaxshiroq: bitta jarayon kutadi, qolganlari normal ishlaydi.

Diagrammadagi 5-momentdagi sakrash - dastur yangi bosqichga o'tgani (masalan fayl o'qishdan hisoblashga). Bunday paytlarda sahifa xatolari vaqtincha ko'payadi - bu normal.

Swap holatini ko'rish #

Terminal

free -h

Natija

               total        used        free      shared  buff/cache
Mem:            15Gi       6.2Gi       1.1Gi       412Mi       8.4Gi
Swap:          4.0Gi       128Mi       3.9Gi

Terminal

cat /proc/sys/vm/swappiness

Natija

`swappiness`	Ma'nosi
`0`	Faqat OOM xavfi bo'lganda swap
`10`	Server uchun tavsiya etiladi
`60`	Odatiy qiymat
`100`	Fayl keshi va anonim xotira teng

Terminal

sudo sysctl vm.swappiness=10

Swap ni butunlay o'chirmang

Ko'p administratorlar "swap sekin, o'chiramiz" deb o'ylaydi. Bu xato.

Swap borligida yadro kamdan-kam ishlatiladigan sahifalarni diskka olib qo'yib, RAM ni fayl keshiga beradi - bu tizimni tezlashtiradi.

Swap bo'lmasa, xotira tugagan zahoti OOM Killer ishlaydi - jarayon ogohlantirishsiz o'ladi.

To'g'ri yondashuv: swap qoldirib, swappiness ni pasaytirish.

Amaliy topshiriq

FIFO simulyatorini yozib, sinov satrida sinang.
Ramkalar sonini 4 ga oshirib, xatolar o'zgarishini kuzating.
Optimal algoritmni amalga oshiring va etalon oling.
LRU yozib, uni Optimal bilan solishtiring.
Clock algoritmini yozing va tashlangan qadamlarni sanang.
Belady anomaliyasini FIFO da takrorlang.
LRU da Belady anomaliyasi yo'qligini tekshiring.
Ish to'plami hajmini har xil oyna uchun hisoblang.
vmstat 1 bilan tizimda swap harakatini kuzating.
swappiness qiymatini ko'ring va ma'nosini tushuntiring.

Xulosa #

RAM to'lganda OT qaysi sahifani chiqarishni tanlashi kerak.
FIFO oddiy, lekin sifatsiz - 15 xato.
Optimal eng yaxshi (9 xato), lekin kelajakni bilish kerak.
LRU amaliy va Optimalga yaqin (12 xato).
Clock - LRU ning arzon taqribi, apparat R bitiga tayanadi.
Linux active/inactive ikki ro'yxatli LRU ishlatadi.
Belady anomaliyasi: FIFO da ramka ko'payib, xato ham ko'payadi.
Stek algoritmlari (LRU, Optimal) bu anomaliyaga uchramaydi.
Thrashing - jarayonlar sahifalarni tortishib, CPU bo'sh qoladi.
Ish to'plami RAM ga sig'sa, dastur tez ishlaydi.
Swap ni o'chirmang - swappiness ni sozlang.

Keyingi bo'limda fayl tizimiga o'tamiz.

Masalaning qo'yilishi #

Sinov satri #

FIFO - birinchi kelgan birinchi chiqadi #

Optimal - kelajakni biluvchi algoritm #

LRU - eng uzoq ishlatilmagan #

Clock (ikkinchi imkoniyat) algoritmi #

Belady anomaliyasi #

Thrashing - halokatli holat #

Ish to'plami (working set) #

Swap holatini ko'rish #

Xulosa #

Xatolik topdingizmi?