Muhammad Al-Xorazmiynomidagi Toshkent AxborotTexnologiyalariUniversiteti
AXBOROT TEXNOLOGIYALARINING DASTURIY TA’MINOTI KAFEDRASI
“Operasion tizimlar” fanidan
MUTAQIL ISH
Bajardi: Abdullajonov Firdavs
Tekshirdi : Ro‘zibayev Ortik
Mavzu: Bankers algoritmi.
Reja:
1. Operatsion tizimda bankers algoritmi 2. Bankers algoritmi
3,Bankers algoriyimiga misollar
4.Xulosa
5.Foydalanilgan adabyotlar
Bankir algoritmi - bu Edsger Dijkstra tomonidan ishlab chiqilgan resurslarni taqsimlash va boshi berk ko'chadan qochish algoritmi bo'lib, u barcha resurslarning oldindan belgilangan maksimal mumkin bo'lgan miqdorlarini taqsimlashni simulyatsiya qilish orqali xavfsizlikni sinovdan o'tkazadi, so'ngra boshqa barcha manbalar uchun yuzaga kelishi mumkin bo'lgan o'lik sharoitlarini tekshirish uchun "s-holat" tekshiruvini o'tkazadi. kutilayotgan faoliyatni, ajratishni davom ettirishga ruxsat berish kerakligi haqida qaror qabul qilishdan oldin.
Algoritm THE operatsion tizimini loyihalash jarayonida ishlab chiqilgan va dastlab (Golland tilida) EWD108 da tasvirlangan.[1] Yangi jarayon tizimga kirganda, u da'vo qilishi mumkin bo'lgan har bir resurs turidagi misollarning maksimal sonini e'lon qilishi kerak; aniqki, bu raqam tizimdagi resurslarning umumiy sonidan oshmasligi kerak. Bundan tashqari, jarayon barcha so'ralgan resurslarni olganida, ularni cheklangan vaqt ichida qaytarishi kerak.
Resurslar
Bankerning algoritmi ishlashi uchun u uchta narsani bilishi kerak:
Har bir jarayon qancha resurs talab qilishi mumkin ("MAX")
Har bir jarayon hozirda har bir resursning qancha qismini egallab turibdi (“ajratilgan”)
Tizimda hozirda mavjud bo'lgan har bir resursdan qanchasi ("MAVJIDA")
Resurslar jarayonga faqat so'ralgan resurslar miqdori mavjud bo'lgan miqdordan kam yoki teng bo'lgan taqdirdagina taqsimlanishi mumkin; aks holda, jarayon resurslar mavjud bo'lguncha kutadi.
Haqiqiy tizimlarda kuzatiladigan resurslardan ba'zilari xotira, semaforlar va interfeysga kirishdir
Bankir algoritmi o'z nomini shundan kelib chiqadiki, bu algoritm bank tizimida bank resurslari tugab qolmasligini ta'minlash uchun ishlatilishi mumkin edi, chunki bank hech qachon o'z pullarini boshqa talablarni qondira olmaydigan tarzda taqsimlamaydi. barcha mijozlarining ehtiyojlari.[2] Banker algoritmidan foydalangan holda, bank mijozlar pul so'raganda, bank hech qachon xavfsiz holatdan chiqmasligini ta'minlaydi. Agar mijozning so'rovi bankni xavfsiz holatda qoldirishga olib kelmasa, naqd pul ajratiladi, aks holda mijoz boshqa mijozning omonatlarini etarli darajada kutishi kerak.
Banker algoritmini amalga oshirish uchun saqlanishi kerak bo'lgan asosiy ma'lumotlar tuzilmalari:]
Tizimdagi jarayonlar soni n, resurs turlari soni m bo‘lsin. Keyin bizga quyidagi ma'lumotlar tuzilmalari kerak bo'ladi:
Mavjud: m uzunlikdagi vektor har bir turdagi mavjud resurslar sonini bildiradi. Mavjud[j] = k bo'lsa, Rj tipidagi resursning ta nusxasi mavjud.
Maks: n × m matritsa har bir jarayonning maksimal talabini belgilaydi. Agar Max[i,j] = k bo'lsa, Pi Rj resurs tipidagi ko'pi bilan k nusxasini so'rashi mumkin.
Ajratish: n × m matritsa hozirda har bir jarayonga ajratilgan har bir turdagi resurslar sonini belgilaydi. Agar ajratish[i,j] = k bo'lsa, u holda Pi jarayoni hozirda Rj tipidagi resursning k nusxasi ajratilgan.
Ehtiyoj: n × m matritsa har bir jarayonning qolgan resurslarga bo'lgan ehtiyojini ko'rsatadi. Agar Need[i,j] = k bo'lsa, vazifani bajarish uchun Pi-ga Rj tipidagi resurs turining yana k nusxasi kerak bo'lishi mumkin.
Eslatma: Need[i,j] = Maks[i,j] - Ajratish[i,j]. n=m-a.
Agar barcha jarayonlar bajarilishini tugatish (tugatish) mumkin bo'lsa, holat (yuqoridagi misolda bo'lgani kabi) xavfsiz hisoblanadi. Tizim jarayon qachon tugashini yoki shu vaqtgacha qancha resurslarni talab qilishini bila olmaganligi sababli, tizim barcha jarayonlar belgilangan maksimal resurslarni olishga harakat qiladi va tez orada tugatiladi deb taxmin qiladi. Bu ko'p hollarda oqilona taxmindir, chunki tizim har bir jarayon qancha davom etishi bilan bog'liq emas (hech bo'lmaganda boshi berk ko'chadan qochish nuqtai nazaridan emas). Bundan tashqari, agar jarayon maksimal resursga ega bo'lmasdan tugasa, bu tizimni faqat osonlashtiradi. Xavfsiz holat, agar u tayyor navbatni qayta ishlasa, qaror qabul qiluvchi hisoblanadi.
Ushbu taxminni hisobga olgan holda, algoritm har biriga maksimal resurslarni qo'lga kiritish va keyin tugatish (resurslarini tizimga qaytarish) imkonini beradigan jarayonlar bo'yicha gipotetik so'rovlar to'plamini topishga urinish orqali davlat xavfsiz yoki yo'qligini aniqlaydi. Bunday to'plam mavjud bo'lmagan har qanday shtat xavfli holat hisoblanadi.
Oldingi misolda keltirilgan holat xavfsiz holat ekanligini har bir jarayon uchun maksimal resurslarga ega bo‘lib, keyin tugatilishi mumkinligini ko‘rsatib ko‘rsatishimiz mumkin.
P1 maksimalga erishish uchun 2 A, 1 B va 1 D ko'proq resurslarga muhtoj
[mavjud manba: ⟨3 1 1 2⟩ − ⟨2 1 0 1⟩ = ⟨1 0 1 1⟩]
Tizimda hali ham 1 A, B yo'q, 1 C va 1 D resurs mavjud
P1 tugaydi, tizimga 3 A, 3 B, 2 C va 2 D resurslarni qaytaradi
[mavjud manba: ⟨1 0 1 1⟩ + ⟨3 3 2 2⟩ = ⟨4 3 3 3⟩]
Endi tizimda 4 A, 3 B, 3 C va 3 D manbalari mavjud
P2 2 B va 1 D qo'shimcha resurslarga ega bo'ladi, so'ngra barcha resurslarini qaytarib, tugatadi
[mavjud manba: ⟨4 3 3 3⟩ − ⟨0 2 0 1⟩ + ⟨1 2 3 4⟩ = ⟨5 3 6 6⟩]
Endi tizimda 5 A, 3 B, 6 C va 6 D manbalari mavjud
P3 1 B va 4 C resurslarini oladi va tugatadi.
[mavjud manba: ⟨5 3 6 6⟩ − ⟨0 1 4 0⟩ + ⟨1 3 5 0⟩ = ⟨6 5 7 6⟩]
Endi tizimda barcha resurslar mavjud: 6 A, 5 B, 7 C va 6 D
Barcha jarayonlar tugatilishi mumkin bo'lganligi sababli, bu holat xavfsizdir
Xavfli holat misoli uchun, agar 2-jarayon boshida 1 birlik B resursga ega bo'lsa, nima bo'lishini ko'rib chiqing.
So'rovlar
Tizim resurslarga so'rovni qabul qilganda, so'rovni berish xavfsiz yoki yo'qligini aniqlash uchun Bankerning algoritmini ishga tushiradi. Xavfsiz va xavfli holatlar o'rtasidagi farq tushunilgandan so'ng, algoritm juda oddiy.
So'rovni qondirish mumkinmi?
Agar yo'q bo'lsa, so'rov imkonsiz va rad etilishi yoki kutish ro'yxatiga qo'yilishi kerak
Tasavvur qiling, so'rov bajarildi
Yangi davlat xavfsizmi?
Agar shunday bo'lsa, so'rovni bajaring
Agar yo'q bo'lsa, so'rovni rad eting yoki uni kutish ro'yxatiga qo'ying
Tizim imkonsiz yoki xavfli so'rovni rad etadimi yoki kechiktiradimi - bu operatsion tizimga xos bo'lgan qaror.
Misol
Oldingi misol bilan bir xil holatdan boshlab, 1-jarayon 2 birlik C resursini talab qiladi.
So‘rovni bajarish uchun C resursi yetarli emas
So‘rov rad etilgan
Boshqa tomondan, C resursining 1 birligi 3 ta so'rov jarayonini qabul qiling.
So'rovni qondirish uchun etarli resurslar mavjud
Tasavvur qiling, so'rov bajarildi
Tizimning yangi holati quyidagicha bo'ladi:
Ushbu yangi davlat xavfsiz yoki yo'qligini aniqlang
P1 2 A, 1 B va 1 D manbalarini olishi va tugatishi mumkin
Keyin P2 2 B va 1 D manbalarini olishi va tugatishi mumkin
Nihoyat, P3 1 B va 3 C resurslarini olishi va tugatishi mumkin
Shuning uchun bu yangi davlat xavfsizdir
Yangi davlat xavfsiz bo'lgani uchun so'rovni bajaring
Yakuniy misol: biz boshlagan holatdan, 2 jarayon B resursining 1 birligini talab qiladi deb faraz qilaylik.
Resurslar yetarli
Agar so'rov bajarilgan bo'lsa, yangi holat quyidagicha bo'ladi:
|
