Toshkent axborot texnologiyalari universiteti Dasturiy injinering fakulteti

Toshkent axborot texnologiyalari universiteti

Dasturiy injinering fakulteti
Axborot tizimlarining dasturiy ta’minoti kafedrasi
Real vaqt tizimlari fanidan

1-Laboratoriya ishi

Bajardi: Rahmonov J
Tekshirdi:Primqulov O
1-Topshiriq.
Jurnaldagi tartib nomer asosida round robbin algoritmi yordamida vazifalarni rejalashtiring va o’rtacha kechikish vaqtini toping
Bu yerda P1,P2,P3 va P4 lar jarayonlar navbati. Ularga mos ustundagi sifralar oniy vaqtlarini bildiradi.
15-variant

Variant №	P1	P2	P3	P4	Vaqt bo’lagi
15.	37	40	19	28	10

1. 
   P1 >> 37-10=27 >> 27-10=17 >> 17-10=7
   
2. 
   P2 >> 40 – 10 = 30 >> 30-10=20 >> 20-10=10>> 10-10=0
   
3. 
   P3>> 19-10=9
   
4. 
   P4>>28-10=18 >> 18-10=8
   

P1

P2

P3

P4

P1

P2

P3

P4

P1

P2

P4

P1

P2

0 10 20 30 40 50 60 69 79 89 97 107 114 124
Kutish vaqti ( KV ) = Aylanish vaqti(AV) – Oniy vaqt ( OT )
->
Kutish vaqti P1 = 114-37 = 77 ms
Kutish vaqti P2 = 124-40 = 84 ms
Kutish vaqti P3 = 69-19 = 50 ms
Kutish vaqti P4 = 107-28 = 79 ms
Umumiy kutish vaqti = 77+84+50+79 = 290 ms

O’rtacha kutish vaqti = 290/4 = 72.5 milliseconds

Tugash vaqti P1 = 114ms
Tugash vaqti P2 = 124 ms
Tugash vaqti P3 = 69 ms
Tugash vaqti P4 = 107 ms
Umumiy tugash vaqti UTV = 114+124+69+107= 414 ms
Bundan,
Oʻrtacha tugash vaqti = 414/4= 103.5 ms


2-topshiriq



3-topshiriq
Ustuvorlikni rejalashtirish algoritmi
P1 dan P5 gacha bo'lgan beshta jarayonni ko'rib chiqamiz. Har bir jarayonning o'ziga xos ustuvorligi, bajarilish vaqti va kelish vaqti bor.

Jarayon	Ustuvorlik	Bajarilish vaqti	Kelish vaqti
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

0-qadam) Vaqt=0 bo'lganda, P1 va P2 jarayonlari keladi. P1 P2 dan yuqori ustuvorlikka ega. Bajarish P1 jarayonidan boshlanadi, uning yorilish vaqti 4.

1-qadam) Vaqt=1 bo'lsa, yangi jarayon kelmaydi. Bajarish P1 bilan davom etadi.

2- qadam) 2 -vaqtda yangi jarayon kelmaydi, shuning uchun siz P1 bilan davom etishingiz mumkin. P2 kutish navbatida.

3- qadam) 3 -vaqtda yangi jarayon kelmaydi, shuning uchun P1 bilan davom etishingiz mumkin. P2 jarayoni hali ham kutish navbatida.

4- qadam) 4 -vaqtda P1 o'z bajarilishini tugatdi. P2 bajarishni boshlaydi.

5-qadam) Vaqt= 5 da yangi jarayon kelmaydi, shuning uchun biz P2 bilan davom etamiz.

6-qadam) Vaqt=6 bo'lganda, P3 keladi. P3 ustunlikka ega (2) P2 bilan solishtirganda yuqoriroq (1) ustuvorlikda. P2 oldindan belgilab qo'yilgan va P3 uning bajarilishini boshlaydi.

Jarayon	Ustuvorlik	Bajarilish vaqti	Kelish vaqti
P1	1	4	0
P2	2	3 tadan 1 tasi kutilmoqda	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

7- qadam) 7 -vaqtda yangi jarayon kelmaydi, shuning uchun biz P3 bilan davom etamiz. P2 kutish navbatida.

8-qadam) Vaqt= 8 da yangi jarayon kelmaydi, shuning uchun biz P3 bilan davom etishimiz mumkin.

9-qadam) Vaqt= 9 da yangi jarayon kelmaydi, shuning uchun biz P3 bilan davom etishimiz mumkin.

10- qadam) 10 vaqt oralig'ida yangi jarayon kelmaydi, shuning uchun biz P3 bilan davom etamiz

11-qadam) Vaqt=11 bo'lsa, P4 4 ustuvorlik bilan keladi. P3 yuqoriroq ustuvorlikka ega, shuning uchun u o'z bajarilishini davom ettiradi.

Jarayon	Ustuvorlik	Bajarilish vaqti	Kelish vaqti
P1	1	4	0
P2	2	3 tadan 1 tasi kutilmoqda	0
P3	1	7 tadan 2 tasi kutilmoqda	6
P4	3	4	11
P5	2	2	12

12-qadam) Vaqt=12 bo'lganda, P5 keladi. P3 yuqori ustuvorlikka ega, shuning uchun u bajarishni davom ettiradi.

13-qadam) Vaqt=13 bo'lsa, P3 bajarishni yakunlaydi. Bizda P2, P4, P5 tayyor navbatda. P2 va P5 teng ustuvorlikka ega. P2 ning kelish vaqti P5 dan oldin. Shunday qilib, P2 bajarishni boshlaydi.

Jarayon	Ustuvorlik	Bajarilish vaqti	Kelish vaqti
P1	1	4	0
P2	2	3 tadan 1 tasi kutilmoqda	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

14-qadam) =14 vaqtida P2 jarayoni o'z bajarilishini tugatdi. P4 va P5 kutish holatida. P5 eng yuqori ustuvorlikka ega va ijroni boshlaydi.

15-qadam) =15 vaqtida P5 bajarishni davom ettiradi.

16-qadam) Vaqt= 16 bo'lganda, P5 uning bajarilishi bilan yakunlanadi. P4 - qolgan yagona jarayon. Amalga oshirishni boshlaydi.

17-qadam) =20 vaqtida P5 bajarilishni tugatdi va hech qanday jarayon qolmadi.

18-qadam) Yuqoridagi misol uchun o'rtacha kutish vaqtini hisoblaymiz.
Kutish vaqti = boshlanish vaqti - kelish vaqti + keyingi bajarilish uchun kutish vaqti
P1 = o - o = o
P2 =4 - o + 7 =11
P3= 6-6=0
P4= 16-11=5
Oʻrtacha kutish vaqti = (0+11+0+5+2)/5 = 18/5= 3.6

4-topshiriq
Earliest first deadline
Misol:
P1 va P2 ikkita jarayonni ko'rib chiqamiz
P1 davri p ₁ = 50 bo'lsin, P1 ning ishlov berish vaqti t ₁ = 25 bo'lsin.
P2 davri ₂ davr = 75 bo'lsin, P2 ning ishlov berish vaqti t ₂ = 30 bo'lsin.

Yechim uchun qadamlar:

1. 
   Pf P1 dedlayn muddati oldinroq, shuning uchun P1>P2 bo’ladi
   
2. 
   Dastlab P1 ishlaydi va 25 marta bajariladi
   
3. 
   25 martadan so'ng, P1 bajarilayotganda P2 50 martagacha bajarila boshlaydi.
   
4. 
   Endi (P1, P2) = (100, 75) muddatini solishtirganda, P2 bajarilishda davom etadi.
   
5. 
   P2 55-vaqtda jarayon ishlashni tugatadi.
   
6. 
   P2 bajarila oladigan vaqtda P1 75 vaqtda bajailra boshlaydi.
   
7. 
   Endi (P1, P2) = (100, 150) muddatini yana solishtirsak, P1 bajarilishda davom etadi.
   
8. 
   Yuqoridagi amallarni takrorlanib boradi…
   
9. 
   Nihoyat, 150-da P1 ham, P2 ham bir xil muddatga ega, shuning uchun dedlayngacha bajarilishini davom ettiradi, shundan so'ng P1 bajarila boshlaydi.
   

EDF rejalashtirish algoritmining cheklovlari:

• 
  Vaqtinchalik ortiqcha yuklama muammosi
  
• 
  Resurs almashish muammosi
  
• 
  Samarali amalga oshirish muammosi
  

5-topshiriq
Rate monotonic scheduling algoritmi
Misol uchun, bizda quyidagi uchta vazifadan iborat vazifalar to'plami mavjud

Vazifalar	Chiqarish vaqti (ri)	Bajarish vaqti (Ci)	Yakuniy muddat (Di)	Vaqt davri (Ti)
T1	0	0,5	3	3
T2	0	1	4	4
T3	0	2	6	6

Jadval 1. Vazifalar to'plami
U = 0,5/3 +1/4 +2/6 = 0,167+ 0,25 + 0,333 = 0,75
Protsessordan foydalanish 1 yoki 100% dan kam bo'lganligi sababli, vazifalar to'plamini rejalashtirish mumkin va u yuqoridagi monotonik rejalashtirish algoritmining tenglamasini ham qondiradi.


1-jadvaldagi topshiriqlar to'plamining RM jadvali.
1-jadvalda berilgan topshiriqlar to'plami va RMni rejalashtirish 1-rasmda keltirilgan. Yuqoridagi tushuntirish quyidagicha:

1. 
   RM rejalashtirish algoritmiga ko'ra, qisqaroq muddatga ega bo'lgan vazifa yuqori ustuvorlikka ega, shuning uchun T1 yuqori ustuvorlikka ega, T2 oraliq ustuvorlikka ega va T3 eng past ustuvorlikka ega. t=0 da barcha vazifalar chiqariladi. Endi T1 eng yuqori ustuvorlikka ega, shuning uchun u t = 0,5 gacha birinchi bo'lib bajariladi.
   
2. 
   T=0,5 da T2 vazifasi T3 ga qaraganda yuqoriroq ustuvorlikka ega, shuning uchun u t=1,5 gacha bir martalik birliklar uchun birinchi bo'lib bajariladi. Uni tugatgandan so'ng tizimda faqat bitta vazifa qoladi, ya'ni T3, shuning uchun u o'z bajarilishini boshlaydi va t=3 gacha bajaradi.
   
3. 
   T=3 da T1 chiqadi, chunki u T3 dan yuqoriroq ustuvorlikka ega, shuning uchun u T3 ni oldini oladi yoki bloklaydi va uni t=3,5 gacha bajarishni boshlaydi. Shundan so'ng T3 ning qolgan qismi ishlaydi.
   
4. 
   T=4 da T2 uni chiqaradi va bajarishni yakunlaydi, chunki hozirda tizimda hech qanday vazifa bajarilmaydi.
   
5. 
   T=6 da T1 ham, T3 ham bir vaqtning o'zida chiqariladi, lekin T1 qisqaroq davr tufayli yuqoriroq ustuvorlikka ega, shuning uchun u T3 ni oldindan oladi va t = 6,5 gacha ishlaydi, shundan keyin T3 ishlay boshlaydi va t = 8 gacha ishlaydi.
   
6. 
   t=8 da T2 T3 dan yuqoriroq ustuvorlikka ega, shuning uchun u T3 ni oldini oladi va uning bajarilishini boshlaydi.
   
7. 
   t=9 da T1 yana chiqariladi va u T3 ni oldindan bajaradi va birinchi bo'lib, t=9,5 da T3 qolgan qismini bajaradi. Xuddi shunday davom etmoqda.