Mustaqil ish mavzu: Operatsion tizimlarning jarayonni rejalashtirish algoritmlari

O’zbekiston Respublikasi Axborot Texnologiyalari va

Kommunikatsiyalarini Rivojlantirish Vazirligi

______________________________________________

Muhammad Al-Xorazmiy nomidagi

Toshkent Axborot Texnologiyalari Universiteti.

MUSTAQIL ISH

Mavzu: Operatsion tizimlarning jarayonni rejalashtirish algoritmlari

AKTsKT 651-18

Bajardi: Quralov N

Tekshirdi: Nazarov A

Toshkent 2021

Mavzu: Operatsion tizimlarning jarayonni rejalashtirish algoritmlari

Reja:

1. 
   Birinchi keling birinchi xizmat (FCFS)
   
2. 
   Birinchidan, eng qisqa ish (oldindan belgilanmagan)
   
3. 
   Eng qisqa ish (birinchi darajali)
   
4. 
   Dumaloq-Robin
   
5. 
   Xulosa
   
6. 
   Foydalanilgan adabiyotlar
   

Tizimda ma'lum bir vaqtda turli holatlarda mavjud bo'lgan bir qator jarayonlar mavjud. Ba'zi jarayonlar kutish holatida, boshqalari ish holatida bo'lishi mumkin va hokazo. Hech o'ylab ko'rganmisiz, protsessor bajarilishi uchun ko'plab jarayonlardan bittasini qanday tanlaydi? Ha, siz buni to'g'ri tushundingiz. CPU shu qadar ko'p jarayonlar orasida bajarilishi uchun bitta jarayonni tanlash uchun qandaydir jarayonlarni rejalashtirish algoritmlaridan foydalanadi. Jarayonlarni rejalashtirish algoritmlari samaradorlikni oshirish orqali protsessorlardan maksimal darajada foydalanishda foydalaniladi. Ushbu blogda biz protsessni rejalashtirish uchun protsessor tomonidan ishlatiladigan turli xil jarayonlarni rejalashtirish algoritmlari haqida bilib olamiz.

Birinchi keling birinchi xizmat (FCFS)

Nomidan ko'rinib turibdiki, tayyor holatda birinchi bo'lib keladigan jarayon portlash vaqti yoki ustuvorligidan qat'i nazar, birinchi navbatda protsessor tomonidan amalga oshiriladi. Bu First In First Out (FIFO) navbatidan foydalanish orqali amalga oshiriladi. Xo'sh, nima sodir bo'ladi, agar jarayon tayyor holatga kirsa, u holda bu jarayonning PCB-si navbatning quyruqiga bog'lanadi va protsessor jarayonni navbatning boshidan olib, jarayonlarni bajarishni boshlaydi (o'rganing bu erda PCB haqida ko'proq ma'lumot). Agar protsessor protsessga ajratilgan bo'lsa, u protsessning bajarilishini tugatmaguncha uni qaytarib olish mumkin emas

Yuqoridagi misolda bizda P1, P2 va P3 uchta jarayoni borligini ko'rishingiz mumkin va ular mos holda 0ms, 2ms va 2ms da tayyor holatda kelmoqda. Shunday qilib, kelish vaqtiga asoslanib, P1 jarayoni dastlabki 18 ms uchun bajariladi. Shundan so'ng, P2 jarayoni 7ms davomida bajariladi va nihoyat P3 jarayoni 10ms davomida bajariladi. Bu erda bir narsani ta'kidlash kerakki, agar jarayonlarning kelish vaqti bir xil bo'lsa, u holda CPU har qanday jarayonni tanlashi mumkin.

FCFSning afzalliklari:

Bu eng oddiy rejalashtirish algoritmi va uni amalga oshirish oson.

FCFS ning kamchiliklari:

Ushbu algoritm beparvo emas, shuning uchun jarayonni to'liq bajarishingiz kerak, shundan so'ng boshqa jarayonlarni bajarishga ruxsat beriladi.

O'tkazish qobiliyati samarali emas.

FCFS konveyer ta'siridan aziyat chekadi, ya'ni agar jarayon juda yuqori yorilish vaqtiga ega bo'lsa va u birinchi bo'lib kelsa, u holda juda kam vaqtga ega bo'lgan jarayon tayyor holatda bo'lishidan qat'i nazar, avval bajariladi.

Birinchidan, eng qisqa ish (oldindan belgilanmagan)

FCFS-da biz jarayon juda yuqori yorilish vaqtiga ega ekanligini ko'rdik va u birinchi bo'lib keladi, keyin juda past yorilish vaqti bo'lgan boshqa jarayon o'z navbatini kutishi kerak. Shunday qilib, ushbu muammoni bartaraf etish uchun biz yangi yondashuvni taklif qilamiz, ya'ni eng qisqa ish birinchi yoki SJF.

Ushbu texnikada birinchi navbatda ma'lum bir vaqt ichida minimal yorilish vaqtiga ega bo'lgan jarayon amalga oshiriladi. Bu befarq bo'lmagan yondashuv, ya'ni jarayon o'z ijrosini boshlasa, u to'liq bajariladi va boshqa biron bir jarayon keladi.

Yuqoridagi misolda 0ms da bizda faqat bitta jarayon, ya'ni P2 jarayoni bor, shuning uchun P2 jarayoni 4ms davomida bajariladi. Endi, 4 soniyadan so'ng, ikkita yangi jarayon mavjud, ya'ni P1 jarayoni va P3 jarayoni. P1 ning yorilish vaqti 5ms, P3niki esa 2ms. Shunday qilib, bu ikkalasi orasida birinchi navbatda P3 jarayoni amalga oshiriladi, chunki uning yorilish vaqti P1 dan kam. P3 2 ms uchun bajariladi. Endi 6ms dan keyin bizda ikkita jarayon bor, ya'ni P1 va P4 (chunki biz 6ms va P4 5ms ga teng). Ushbu ikkitasi orasida P4 jarayoni P1ga nisbatan kamroq yorilish vaqtiga ega. Shunday qilib, P4 4ms uchun bajariladi va undan keyin P1 5ms uchun bajariladi. Shunday qilib, ushbu jarayonlarning kutish vaqti va o'zgarishi quyidagicha bo'ladi:

SJFning afzalliklari (imtiyozli bo'lmagan):

Avval qisqa jarayonlar bajariladi.

SJF ning kamchiliklari (oldindan ko'rilmagan):

Qisqa vaqt oralig'idagi jarayonlar tayyor holatda kelsa, bu kutishga olib kelishi mumkin.

Eng qisqa ish (birinchi darajali)

Bu eng qisqa ish birinchi algoritmining oldini olish usuli. Bu erda, har bir lahzada, CPU eng qisqa ishni tekshiradi. Masalan, 0ms vaqt ichida biz eng qisqa jarayon sifatida P1 ga egamiz. Shunday qilib, P1 1ms uchun bajariladi va keyin CPU boshqa jarayon P1 dan qisqa yoki yo'qligini tekshiradi. Agar bunday jarayon bo'lmasa, unda P1 keyingi 1ms davomida bajarishni davom ettiradi va agar P1 dan qisqa protsess bo'lsa, u holda bu jarayon bajariladi. Bu jarayon bajarilmaguncha davom etadi.

Ushbu algoritm birinchi navbatda eng qisqa qolgan vaqt deb ham nomlanadi, ya'ni biz jarayonlarni qolgan eng qisqa vaqtga qarab rejalashtiramiz.

Yuqoridagi misolda, 1ms vaqt ichida ikkita jarayon, ya'ni P1 va P2 mavjud. Jarayon P1 6ms, P2 jarayoni 8ms ni tashkil qiladi. Shunday qilib, birinchi navbatda P1 bajariladi. Bu preventiv yondashuv bo'lgani uchun, biz har doim kvantni tekshirishimiz kerak. 2ms da bizda uchta jarayon bor, ya'ni P1 (5ms qolgan), P2 (8ms) va P3 (7ms). Ushbu uchtadan P1 eng kam yorilish vaqtiga ega, shuning uchun u bajarilishini davom ettiradi. 3ms dan keyin bizda to'rtta jarayon bor, ya'ni P1 (4ms qolgan), P2 (8ms), P3 (7ms) va P4 (3ms). Ushbu to'rttadan P4 eng kam yorilish vaqtiga ega, shuning uchun u bajariladi. Jarayon P4 keyingi uch msni bajarishda davom etadi, chunki u eng qisqa vaqtga ega. 6 msdan keyin bizda 3 ta jarayon mavjud, ya'ni P1 (4ms qolgan), P2 (8ms) va P3 (7ms). Shunday qilib, P1 tanlanadi va bajariladi. Bu vaqtni taqqoslash jarayoni biz barcha jarayonlar bajarilmaguncha davom etadi. Shunday qilib, jarayonlarni kutish va burilish vaqti quyidagicha bo'ladi:

SJFning afzalliklari (imtiyozli):

Avval qisqa jarayonlar bajariladi.

SJF ning kamchiliklari (ustunlik):

Qisqa jarayonlar kelaversa, bu ochlikka olib kelishi mumkin.

Dumaloq-Robin

CPU rejalashtirishning ushbu yondashuvida bizda belgilangan vaqt kvanti mavjud va protsessor protsessga faqat bir vaqtning o'zida shu vaqt uchun ajratiladi. Masalan, agar bizda P1, P2 va P3 uchta jarayoni bo'lsa va bizning vaqt kvantimiz 2ms bo'lsa, unda P1 uchun uning bajarilishi uchun 2ms, keyin P2 ga 2ms, keyin P3 ga 2ms beriladi. Bir tsikldan keyin yana P1 ga 2ms beriladi, keyin P2 ga 2ms beriladi va shunga o'xshash jarayonlar uning bajarilishi tugamaguncha.

Odatda u vaqtni taqsimlash muhitida qo'llaniladi va davra holatida ochlik bo'lmaydi.

Yuqoridagi misolda har bir jarayonga bir burilishda 2ms beriladi, chunki biz vaqt kvantini 2ms qilib oldik. Shunday qilib, P1 jarayoni 2ms davomida bajariladi, keyin P2 jarayoni 2ms davomida, keyin P3 2 ms uchun bajariladi. Shunga qaramay, P1 jarayoni 2ms davomida bajariladi, keyin P2 va boshqalar. Jarayonlarni kutish vaqti va aylanish vaqti quyidagicha bo'ladi:

Dumaloq robinning afzalliklari:

Dumaloq rejimda hech qanday ochlik bo'lmaydi, chunki har bir jarayon uning bajarilishi uchun imkoniyat yaratadi.

Vaqtni taqsimlash tizimlarida ishlatiladi.

Dumaloq robinning kamchiliklari:

Biz bu erda juda ko'p kontekstni almashtirishni amalga oshirishimiz kerak, bu esa protsessorni bo'sh holatda ushlab turadi.

5. 
   Xulosa
   

Men shu mustaqil ishni bajarish vaqtimda juda ko’plab ma’lumotlarga ega bo’ldim, Operatsion tizim ishlash jarayoidagi algoritmlar haqida ba’zi malumotlarga ega bo’ldim, OT ishlash jarayonida qaysi jarayonni biribchi tanlash kerakligini tushunib oldim. Menga bu mustaqil ishni bajarish juda qiziqarli bo’ldi.

5. 
   Foydalanilgan adabiyotlar
   

https://afteracademy.com/blog/process-scheduling-algorithms-in-the-operating-system

https://ziyonet.uz

https://translate.google.com/