6-bo‘lim
Rejalashtirish algoritmlari
Protsessor vaqti qanday taqsimlanadi, FCFS, SJF, Round Robin va ustuvorlik algoritmlari, Linux CFS va nice qiymati.
Ushbu bo‘lim mundarijasi
Bir protsessor, yuzlab jarayon. Kim qachon ishlaydi? Bu savolga rejalashtiruvchi (scheduler) javob beradi.
Muammo #
Rejalashtirish maqsadlari #
| Maqsad | Ma'nosi | Kim uchun muhim |
|---|---|---|
| Adolat | Har kimga o'z ulushi | Barcha foydalanuvchilar |
| Javob vaqti | Tugma bosilgach tez javob | Interaktiv dasturlar |
| O'tkazuvchanlik | Vaqt birligida ko'proq ish | Serverlar |
| Kutish vaqti | Navbatda kam turish | Paket ishlar |
| Ochlikdan saqlash | Hech kim mangu kutmasin | Hammasi |
| Samaradorlik | Protsessor bo'sh turmasin | Tizim |
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 #
#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;
}
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 #
#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;
}
Ish Davomiylik Kutdi
--------------------------------
B 3 0
C 3 3
A 24 6
--------------------------------
O'rtacha kutish: 3.00 birlik
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.
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 #
#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;
}
Bajarilish tartibi: A B C A A A A A
Ish Tugadi
--------------------
A 30
B 7
C 10
| Kvant | Natija |
|---|---|
| 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 #
#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;
}
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
1997-yilda Mars Pathfinder marsoxodi Marsda qayta-qayta o'chib yona boshladi. Sabab - ustuvorlik inversiyasi:
- Past ustuvorlikdagi vazifa umumiy resursni qulfladi;
- Yuqori ustuvorlikdagi vazifa o'sha resursni so'radi va kutdi;
- O'rta ustuvorlikdagi vazifalar past ustuvorlikdagini ishlashga qo'ymadi;
- 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 #
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 #
nice -n 10 ./ogir_hisob # past ustuvorlik bilan ishga tushirish
renice -n 5 -p 1234 # ishlayotgan jarayonni o'zgartirish
#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;
}
Joriy nice qiymati: 0
Yangi nice qiymati : 5
Ustuvorlik pasaydimi? ha
nice | Ma'nosi |
|---|---|
| -20 | Eng yuqori ustuvorlik |
| 0 | Odatiy |
| +19 | Eng past ustuvorlik |
Oddiy foydalanuvchi nice qiymatini faqat oshira oladi (ya'ni
ustuvorlikni pasaytira oladi).
Uni pasaytirish uchun root huquqi kerak:
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 #
chrt -m
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
| Sinf | Kim uchun |
|---|---|
SCHED_OTHER | Odatiy jarayonlar (CFS) |
SCHED_BATCH | Fon hisoblari - interaktivlik kerak emas |
SCHED_IDLE | Faqat tizim bo'sh turganda |
SCHED_FIFO | Real vaqt - o'zi to'xtaguncha ishlaydi |
SCHED_RR | Real vaqt - kvant bilan aylanadi |
SCHED_DEADLINE | Muddat kafolati bilan |
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
sleepyoki bloklanish bilan
ishlating.
Ko'p yadroli tizimlar #
#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;
}
Yadrolar aniqlandi : ha
Ko'p yadrolimi? : ha
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.
taskset -c 0,1 ./dastur # faqat 0 va 1-yadroda ishlasin
numactl --hardware # NUMA tugunlarini ko'rish
Algoritmlarni taqqoslash #
| Algoritm | Adolat | Javob vaqti | Ochlik xavfi | Amalda |
|---|---|---|---|---|
| FCFS | Yaxshi | Yomon | Yo'q | Oddiy navbatlarda |
| SJF | Yomon | Yaxshi | Bor | Nazariy |
| Round Robin | Yaxshi | Yaxshi | Yo'q | Interaktiv tizim |
| Ustuvorlik | Yomon | O'zgaruvchan | Bor | Real vaqt |
| CFS | Juda yaxshi | Yaxshi | Yo'q | Linux |
- FCFS dasturini yozib, ishlar tartibini o'zgartiring.
- SJF ni yozib, o'rtacha kutish vaqti farqini ko'ring.
- Round Robin da kvantni 1, 4 va 10 qilib natijani solishtiring.
- Ustuvorlik algoritmida ochlik holatini yarating.
nicebilan dastur ustuvorligini pasaytiring.topdaNIustunini kuzating.- Ikki og'ir hisob dasturini bir vaqtda ishga tushiring va
topda ko'ring. - Biriga
reniceqilib, protsessor ulushi o'zgarishini kuzating. chrt -mbilan rejalashtirish sinflarini ko'ring.tasksetbilan 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.
niceqiymatini oddiy foydalanuvchi faqat oshira oladi.- Real vaqt sinflari butun tizimni qotirishi mumkin.
Keyingi bo'limda umumiy ma'lumotni himoya qilishni - sinxronizatsiyani ko'ramiz.
O‘qish tarixini saqlamoqchimisiz?
Tizimga kirsangiz, tugatgan bo‘limlaringiz saqlanadi va qoldirgan joyingizdan davom etasiz.
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.