6-bo‘lim

Rejalashtirish algoritmlari

Protsessor vaqti qanday taqsimlanadi, FCFS, SJF, Round Robin va ustuvorlik algoritmlari, Linux CFS va nice qiymati.

🕑 15 daqiqa o‘qish 📄 1 221 so‘z 👁 1 marta ko‘rilgan
Ushbu bo‘lim mundarijasi
  1. Muammo
  2. Rejalashtirish maqsadlari
  3. FCFS - kelgan tartibda
  4. SJF - eng qisqasi birinchi
  5. Round Robin - aylanma navbat
  6. Ustuvorlik bilan rejalashtirish
  7. Linux CFS - adolatli rejalashtiruvchi
  8. nice - ustuvorlikni o'zgartirish
  9. Rejalashtirish sinflari
  10. Ko'p yadroli tizimlar
  11. Algoritmlarni taqqoslash
  12. Xulosa

Bir protsessor, yuzlab jarayon. Kim qachon ishlaydi? Bu savolga rejalashtiruvchi (scheduler) javob beradi.

Muammo #

Tayyor navbat va bitta protsessor Brauzer tayyor Muharrir tayyor Kompilyator tayyor Musiqa tayyor Protsessor bir vaqtda bitta Rejalashtiruvchi qaror qiladi Kimni tanlash? Qancha vaqtga? Qachon almashtirish?
Yaxshi rejalashtiruvchi bir vaqtda bir necha maqsadni muvozanatlaydi

Rejalashtirish maqsadlari #

MaqsadMa'nosiKim uchun muhim
AdolatHar kimga o'z ulushiBarcha foydalanuvchilar
Javob vaqtiTugma bosilgach tez javobInteraktiv dasturlar
O'tkazuvchanlikVaqt birligida ko'proq ishServerlar
Kutish vaqtiNavbatda kam turishPaket ishlar
Ochlikdan saqlashHech kim mangu kutmasinHammasi
SamaradorlikProtsessor bo'sh turmasinTizim
Maqsadlar bir-biriga zid

Javob vaqtini yaxshilash uchun tez-tez almashtirish kerak. Lekin har bir almashinuv vaqt yeydi - shuning uchun o'tkazuvchanlik pasayadi.

Mukammal algoritm yo'q. Har bir tizim o'z vazifasiga qarab muvozanat tanlaydi:

  • Ish stoli - javob vaqti muhim (sichqoncha qotib qolmasin);
  • Server - o'tkazuvchanlik muhim;
  • Real vaqt - kafolatlangan muddat muhim.

FCFS - kelgan tartibda #

FCFS: kim birinchi kelsa - o'sha birinchi Vaqt: 0 24 27 30 A (24 birlik) B (3) C (3) O'rtacha kutish: (0 + 24 + 27) / 3 = 17 birlik B va C atigi 3 birlik ish uchun 24 birlik kutdi - «konvoy effekti»
Oddiy, adolatli, lekin uzun ish hammani ushlab qoladi
C
#include <stdio.h>

typedef struct {
    char nomi;
    int davomiylik;
} Ish;

int main(void) {
    Ish ishlar[] = {{'A', 24}, {'B', 3}, {'C', 3}};
    int soni = 3;

    int joriy_vaqt = 0;
    int jami_kutish = 0;

    printf("%-6s %-12s %-10s %-10s\n", "Ish", "Davomiylik", "Boshlandi", "Kutdi");
    printf("----------------------------------------\n");

    for (int i = 0; i < soni; i++) {
        printf("%-6c %-12d %-10d %-10d\n",
               ishlar[i].nomi, ishlar[i].davomiylik, joriy_vaqt, joriy_vaqt);

        jami_kutish += joriy_vaqt;
        joriy_vaqt += ishlar[i].davomiylik;
    }

    printf("----------------------------------------\n");
    printf("O'rtacha kutish: %.2f birlik\n", (double) jami_kutish / soni);

    return 0;
}
Natija
Ish    Davomiylik   Boshlandi  Kutdi     
----------------------------------------
A      24           0          0         
B      3            24         24        
C      3            27         27        
----------------------------------------
O'rtacha kutish: 17.00 birlik

SJF - eng qisqasi birinchi #

C
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char nomi;
    int davomiylik;
} Ish;

int qisqa_boyicha(const void *a, const void *b) {
    const Ish *x = a;
    const Ish *y = b;

    return x->davomiylik - y->davomiylik;
}

int main(void) {
    Ish ishlar[] = {{'A', 24}, {'B', 3}, {'C', 3}};
    int soni = 3;

    qsort(ishlar, soni, sizeof(ishlar[0]), qisqa_boyicha);

    int joriy_vaqt = 0;
    int jami_kutish = 0;

    printf("%-6s %-12s %-10s\n", "Ish", "Davomiylik", "Kutdi");
    printf("--------------------------------\n");

    for (int i = 0; i < soni; i++) {
        printf("%-6c %-12d %-10d\n",
               ishlar[i].nomi, ishlar[i].davomiylik, joriy_vaqt);

        jami_kutish += joriy_vaqt;
        joriy_vaqt += ishlar[i].davomiylik;
    }

    printf("--------------------------------\n");
    printf("O'rtacha kutish: %.2f birlik\n", (double) jami_kutish / soni);

    return 0;
}
Natija
Ish    Davomiylik   Kutdi     
--------------------------------
B      3            0         
C      3            3         
A      24           6         
--------------------------------
O'rtacha kutish: 3.00 birlik
SJF matematik jihatdan eng yaxshi

17 birlikdan 3 birlikga tushdi - deyarli olti barobar yaxshilanish.

Isbotlangan: SJF o'rtacha kutish vaqtini minimallashtiradi. Bundan yaxshiroq algoritm yo'q.

Lekin ikkita jiddiy muammosi bor.

SJF ning ikki muammosi

1. Kelajakni bilib bo'lmaydi.

Ish qancha davom etishini oldindan qayerdan bilamiz? Amalda faqat taxmin qilish mumkin - odatda o'tmishdagi xatti-harakatga qarab.

2. Ochlik (starvation).

Uzun ish mangu kutishi mumkin: qisqa ishlar kelib turaveradi va u hech qachon navbatga yetmaydi.

Shuning uchun sof SJF amalda ishlatilmaydi. Uning g'oyasi esa boshqa algoritmlarga singdirilgan.

Round Robin - aylanma navbat #

Round Robin: har kimga teng bo'lak (kvant = 4) A B C A A A A A 0-4 4-7 7-10 10-14 B va C tez tugadi - javob vaqti yaxshilandi Hech kim uzoq kutmaydi, lekin A ning tugash vaqti cho'zildi
Interaktiv tizimlar uchun eng mos algoritm
C
#include <stdio.h>

#define ISHLAR 3
#define KVANT 4

int main(void) {
    char nomlar[ISHLAR] = {'A', 'B', 'C'};
    int qolgan[ISHLAR] = {24, 3, 3};
    int tugadi[ISHLAR] = {0, 0, 0};

    int vaqt = 0;
    int tugagan_soni = 0;

    printf("Bajarilish tartibi: ");

    while (tugagan_soni < ISHLAR) {
        for (int i = 0; i < ISHLAR; i++) {
            if (qolgan[i] <= 0) {
                continue;
            }

            int bolak = (qolgan[i] < KVANT) ? qolgan[i] : KVANT;

            printf("%c ", nomlar[i]);
            vaqt += bolak;
            qolgan[i] -= bolak;

            if (qolgan[i] == 0) {
                tugadi[i] = vaqt;
                tugagan_soni++;
            }
        }
    }

    printf("\n\n%-6s %-12s\n", "Ish", "Tugadi");
    printf("--------------------\n");

    for (int i = 0; i < ISHLAR; i++) {
        printf("%-6c %-12d\n", nomlar[i], tugadi[i]);
    }

    return 0;
}
Natija
Bajarilish tartibi: A B C A A A A A 

Ish    Tugadi      
--------------------
A      30          
B      7           
C      10          
Kvant hajmini tanlash
KvantNatija
Juda kichik (1 ms)Javob tez, lekin almashinuv ko'p - isrof
Juda katta (1 s)Almashinuv kam, lekin javob sekin
Optimal (10-100 ms)Muvozanat

Amaliy qoida: kvant kontekst almashinuvidan kamida 100 barobar uzunroq bo'lsin. Almashinuv 5 mikrosoniya bo'lsa, kvant kamida 0,5 millisekund bo'lishi kerak.

Linux'da kvant qat'iy emas - u yuklamaga qarab moslashadi.

Ustuvorlik bilan rejalashtirish #

C
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char nomi;
    int davomiylik;
    int ustuvorlik;             /* kichik son - yuqori ustuvorlik */
} Ish;

int ustuvorlik_boyicha(const void *a, const void *b) {
    const Ish *x = a;
    const Ish *y = b;

    return x->ustuvorlik - y->ustuvorlik;
}

int main(void) {
    Ish ishlar[] = {
        {'A', 10, 3},
        {'B',  1, 1},
        {'C',  2, 4},
        {'D',  1, 5},
        {'E',  5, 2}
    };

    int soni = 5;

    qsort(ishlar, soni, sizeof(ishlar[0]), ustuvorlik_boyicha);

    int vaqt = 0;
    int jami_kutish = 0;

    printf("%-6s %-12s %-12s %-8s\n", "Ish", "Ustuvorlik", "Davomiylik", "Kutdi");
    printf("------------------------------------------\n");

    for (int i = 0; i < soni; i++) {
        printf("%-6c %-12d %-12d %-8d\n",
               ishlar[i].nomi, ishlar[i].ustuvorlik, ishlar[i].davomiylik, vaqt);

        jami_kutish += vaqt;
        vaqt += ishlar[i].davomiylik;
    }

    printf("------------------------------------------\n");
    printf("O'rtacha kutish: %.2f\n", (double) jami_kutish / soni);

    return 0;
}
Natija
Ish    Ustuvorlik   Davomiylik   Kutdi   
------------------------------------------
B      1            1            0       
E      2            5            1       
A      3            10           6       
C      4            2            16      
D      5            1            18      
------------------------------------------
O'rtacha kutish: 8.20
Ustuvorlik inversiyasi

1997-yilda Mars Pathfinder marsoxodi Marsda qayta-qayta o'chib yona boshladi. Sabab - ustuvorlik inversiyasi:

  1. Past ustuvorlikdagi vazifa umumiy resursni qulfladi;
  2. Yuqori ustuvorlikdagi vazifa o'sha resursni so'radi va kutdi;
  3. O'rta ustuvorlikdagi vazifalar past ustuvorlikdagini ishlashga qo'ymadi;
  4. Natijada yuqori ustuvorlikdagi vazifa mangu kutdi va nazorat tizimi qurilmani qayta ishga tushirdi.

Yechim - ustuvorlikni meros qilish: resursni ushlab turgan vazifa vaqtincha kutayotganning ustuvorligini oladi.

Bu hikoya operatsion tizimlar darsliklarida klassik misolga aylangan.

Linux CFS - adolatli rejalashtiruvchi #

CFS: eng kam ishlagan jarayon tanlanadi Virtual ishlash vaqti (vruntime): Jarayon C 12 ms Jarayon A 45 ms Jarayon B 78 ms ← C eng kam ishlagan demak keyingi navbat uniki Qizil-qora daraxt bilan saqlanadi Eng kichik vruntime ni topish: O(1) - u doim eng chapdagi tugun Qayta joylashtirish: O(log n) Shuning uchun minglab jarayonda ham tez ishlaydi
Algoritmlar darsligidagi daraxtlar aynan shu yerda ishlatiladi
CFS g'oyasi

Completely Fair Scheduler - Linux'da 2007-yildan beri ishlatiladi.

G'oya oddiy: har bir jarayon uchun virtual ishlash vaqti (vruntime) saqlanadi. Rejalashtiruvchi doim eng kam vruntime ga ega jarayonni tanlaydi.

Jarayon ishlagach, uning vruntime i oshadi va u navbatning oxiriga suriladi.

Natija: hech kim boshqalardan ko'p ishlab keta olmaydi. Yangi kelgan jarayon esa darhol navbat oldiga tushadi - shuning uchun interaktiv dasturlar tez javob beradi.

Linux 6.6 dan boshlab uning o'rniga EEVDF algoritmi kelmoqda - u kechikishga (latency) ko'proq e'tibor beradi.

nice - ustuvorlikni o'zgartirish #

Terminal
nice -n 10 ./ogir_hisob      # past ustuvorlik bilan ishga tushirish
renice -n 5 -p 1234          # ishlayotgan jarayonni o'zgartirish
C
#include <stdio.h>
#include <unistd.h>
#include <sys/resource.h>
#include <errno.h>

int main(void) {
    errno = 0;
    int joriy = getpriority(PRIO_PROCESS, 0);

    if (errno != 0) {
        printf("Ustuvorlikni o'qib bo'lmadi\n");
        return 1;
    }

    printf("Joriy nice qiymati: %d\n", joriy);

    /* Ustuvorlikni pasaytiramiz (bu har doim mumkin) */
    if (setpriority(PRIO_PROCESS, 0, joriy + 5) == 0) {
        printf("Yangi nice qiymati : %d\n", getpriority(PRIO_PROCESS, 0));
        printf("Ustuvorlik pasaydimi? ha\n");
    }

    return 0;
}
Natija
Joriy nice qiymati: 0
Yangi nice qiymati : 5
Ustuvorlik pasaydimi? ha
niceMa'nosi
-20Eng yuqori ustuvorlik
0Odatiy
+19Eng past ustuvorlik
Ustuvorlikni faqat pasaytirish mumkin

Oddiy foydalanuvchi nice qiymatini faqat oshira oladi (ya'ni ustuvorlikni pasaytira oladi).

Uni pasaytirish uchun root huquqi kerak:

Terminal
sudo nice -n -10 ./muhim_dastur

Sabab: aks holda har bir foydalanuvchi o'z dasturini eng yuqori ustuvorlikka qo'yib, boshqalarni ochlikda qoldirardi.

Rejalashtirish sinflari #

Terminal
chrt -m
Natija
SCHED_OTHER min/max priority    : 0/0
SCHED_FIFO min/max priority    : 1/99
SCHED_RR min/max priority    : 1/99
SCHED_BATCH min/max priority    : 0/0
SCHED_IDLE min/max priority    : 0/0
SCHED_DEADLINE min/max priority    : 0/0
SinfKim uchun
SCHED_OTHEROdatiy jarayonlar (CFS)
SCHED_BATCHFon hisoblari - interaktivlik kerak emas
SCHED_IDLEFaqat tizim bo'sh turganda
SCHED_FIFOReal vaqt - o'zi to'xtaguncha ishlaydi
SCHED_RRReal vaqt - kvant bilan aylanadi
SCHED_DEADLINEMuddat kafolati bilan
Real vaqt sinflari xavfli
Terminal
sudo chrt -f 99 ./mening_dasturim

SCHED_FIFO dagi jarayon o'zi to'xtaguncha protsessorni tark etmaydi. Agar unda cheksiz sikl bo'lsa - butun tizim qotadi va hatto klaviatura ham javob bermaydi.

Shuning uchun real vaqt ustuvorligini faqat:

  • nima qilayotganingizni aniq bilganda;
  • kodni sinchiklab tekshirgandan keyin;
  • majburiy sleep yoki bloklanish bilan

ishlating.

Ko'p yadroli tizimlar #

C
#include <stdio.h>
#include <unistd.h>

int main(void) {
    long yadrolar = sysconf(_SC_NPROCESSORS_ONLN);

    printf("Yadrolar aniqlandi : %s\n", yadrolar > 0 ? "ha" : "yo'q");
    printf("Ko'p yadrolimi?    : %s\n", yadrolar > 1 ? "ha" : "yo'q");

    return 0;
}
Natija
Yadrolar aniqlandi : ha
Ko'p yadrolimi?    : ha
Ko'p yadroda qo'shimcha muammolar

Bir yadroli tizimda faqat «kimni tanlash» muhim edi. Ko'p yadroda yangi savollar paydo bo'ladi:

1. Yuk muvozanati. Bir yadro band, boshqasi bo'sh turmasin.

2. Kesh yaqinligi (cache affinity). Jarayonni boshqa yadroga ko'chirish uning keshini yo'qotadi - shuning uchun yadro uni imkon qadar bir joyda ushlab turadi.

3. NUMA. Katta serverlarda har bir protsessorning «o'z» xotirasi bor. Boshqa protsessorning xotirasiga murojaat sekinroq.

Terminal
taskset -c 0,1 ./dastur      # faqat 0 va 1-yadroda ishlasin
numactl --hardware           # NUMA tugunlarini ko'rish

Algoritmlarni taqqoslash #

AlgoritmAdolatJavob vaqtiOchlik xavfiAmalda
FCFSYaxshiYomonYo'qOddiy navbatlarda
SJFYomonYaxshiBorNazariy
Round RobinYaxshiYaxshiYo'qInteraktiv tizim
UstuvorlikYomonO'zgaruvchanBorReal vaqt
CFSJuda yaxshiYaxshiYo'qLinux
Amaliy topshiriq
  1. FCFS dasturini yozib, ishlar tartibini o'zgartiring.
  2. SJF ni yozib, o'rtacha kutish vaqti farqini ko'ring.
  3. Round Robin da kvantni 1, 4 va 10 qilib natijani solishtiring.
  4. Ustuvorlik algoritmida ochlik holatini yarating.
  5. nice bilan dastur ustuvorligini pasaytiring.
  6. top da NI ustunini kuzating.
  7. Ikki og'ir hisob dasturini bir vaqtda ishga tushiring va top da ko'ring.
  8. Biriga renice qilib, protsessor ulushi o'zgarishini kuzating.
  9. chrt -m bilan rejalashtirish sinflarini ko'ring.
  10. taskset bilan dasturni bitta yadroga bog'lang.

Xulosa #

  • Rejalashtiruvchi kimni, qancha vaqtga va qachon almashtirish kerakligini hal qiladi.
  • Maqsadlar bir-biriga zid - mukammal algoritm yo'q.
  • FCFS oddiy, lekin uzun ish hammani ushlaydi (konvoy effekti).
  • SJF o'rtacha kutishni minimallashtiradi, lekin kelajakni bilib bo'lmaydi va ochlik xavfi bor.
  • Round Robin har kimga teng kvant beradi - interaktiv tizimlar uchun eng mos.
  • Kvant kontekst almashinuvidan ancha uzun bo'lishi kerak.
  • Ustuvorlik inversiyasi Mars Pathfinder missiyasini deyarli barbod qilgan.
  • Linux CFS eng kam ishlagan jarayonni tanlaydi va qizil-qora daraxtdan foydalanadi.
  • nice qiymatini oddiy foydalanuvchi faqat oshira oladi.
  • Real vaqt sinflari butun tizimni qotirishi mumkin.

Keyingi bo'limda umumiy ma'lumotni himoya qilishni - sinxronizatsiyani ko'ramiz.

Xatolik topdingizmi?

Imlo xatosi, ishlamaydigan kod yoki noto‘g‘ri ma‘lumotni ko‘rsangiz - bizga xabar bering. Har bir xabar administrator tomonidan ko‘rib chiqiladi.