semaforlar
Ta'rif. Semafor - ma'lum bir resursga bir vaqtning o'zida kirish huquqiga ega bo'lgan foydalanuvchilar (vazifalar, jarayonlar) sonini belgilaydigan sinxronizatsiya ob'ekti. Har bir semafor hisoblagich (semafor qiymati) va kutish navbati (jarayonlar, hisoblagichning ma'lum bir qiymatni qabul qilishini kutayotgan vazifalar) bilan bog'langan. Farqlash:
ikkilik (mantiqiy) semaforlar muhim umumiy resursni himoya qilish uchun o'zaro istisno mexanizmi; bunday semaning hisoblagichining boshlang'ich qiymati 1 ga teng;
hisoblash semaforlari - cheklangan belgilangan miqdordagi vazifalardan ko'p bo'lmagan n tomonidan bir vaqtning o'zida ishlatilishi mumkin bo'lgan resursni himoya qilish uchun o'zaro istisno mexanizmi; bunday semaning hisoblagichining boshlang'ich qiymati n.
Semaforlarda quyidagi elementar amallar aniqlanadi ( boolean semaforlar uchun k = 1 dan past)
semadan k birlik oling , ya'ni . hisoblagichni k ga kamaytiring (agar hisoblagichda k bo'lmasa , u holda bu operatsiya vazifani semaforda kamida k borligini kutish holatiga qo'yadi va uni kutish navbatining oxiriga qo'shadi). bu semafor);
semada bo'lganlarga qaytish , ya'ni . hisoblagichni k ga oshiring (agar semafor boshqa vazifani kutayotgan bo'lsa va unga bitta hisoblagichning yangi joriy qiymatidan ko'p bo'lmasa, uni faollashtirish, kutish navbatdan olib tashlash va joriy vazifani oldindan belgilash mumkin, masalan , agar uning ustuvorligi yuqoriroq bo'lsa);
k birlik olishga harakat qiling (agar hisoblagich > k birlik, keyin undan k birlik oling, aks holda vazifani kutish holatiga o'tkazmasdan semafor band ko'rsatkichini qaytaring);
semaforni tekshiring , ya'ni. hisoblagichning qiymatini oling;
semaforni blokirovka qilish , ya'ni . undan qancha birlik bor bo'lsa, shuncha birlik oling (bir vaqtning o'zida, ba'zan bu operatsiya ikki xil bo'ladi: hozir qancha bo'lsa, shuncha qabul qiling yoki boshlang'ich daqiqada qancha bo'lsa, shuncha qabul qiling, ya'ni mumkin bo'lgan maksimal raqam, ikkinchisi odatda qulf deb ataladi, chunki bunday vazifa resursga mutlaq egalik qiladi);
semaforni ochish , ya'ni . blokirovka qilish buyrug'i bo'yicha ushbu vazifa tomonidan olingan jami birliklarni qaytaring.
Ikkilik semaforlarning mantiqiy tuzilishi ayniqsa sodda. Yaratilganda semafor hisoblagichi 1 ga ishga tushiriladi. Unga kirish uchun ikkita ibtidoiy operatsiya aniqlanadi:
Get(s) - semaforlarni olish (yoki yopish), ya'ni. resurs so'rash; bu amal 1 hisoblagichdan ayiradi;
Qo'yish (lar) - semaforni qaytarish (yoki ochish), ya'ni. resursni chiqarish; bu operatsiya hisoblagichga 1 qo'shadi.
Ushbu operatsiyalar bo'linmas, ya'ni . ularni bajarish vaqtida vazifalarni almashtirish taqiqlanadi. Ish paytida hisoblagichning holati quyidagicha bo'lishi mumkin:
1 - resurs bepul,
0 - resurs band, kutish navbati bo'sh,
m < 0 - resurs band, kutish navbatda \t\ vazifalar mavjud.
Bir misolni ko'rib chiqing.
A.Get - vazifa A resursni egallab oldi,
C.Get - C vazifasi band bo'lgan resursni so'radi, shuning uchun C vazifasi bloklanadi va kutish navbatiga qo'yiladi,
B.Get - B vazifasi band bo'lgan resursni so'radi , shuning uchun B vazifasi bloklanadi va kutish navbatiga qo'yiladi,
A. Pul - vazifa A kutish navbatdagi birinchi vazifaga o'tgan resursni chiqardi, ya'ni. C (bu o'z navbatida faollashtirilgan),
C.Put - vazifa C kutish navbatdagi birinchi vazifaga o'tkazilgan resursni chiqardi, ya'ni. B (bu o'z navbatida faollashadi),
B.Put - B topshirig'i Resursni chiqardi , u Get deb chaqiradigan birinchi vazifaga o'tadi .
Ba'zan shaxsiy yoki shaxsiy semaforlar ko'rib chiqiladi. Bunday sema T vazifasi bilan darhol yopiq holatda yaratiladi . Bunday holda, T vazifasi faqat Get funktsiyasini va boshqa barcha vazifalarni - faqat Put funktsiyasini chaqirish huquqiga ega . Bunday semaforlar yordamida mijoz-server tipidagi vazifalar o'rtasida almashinuvni tashkil qilish oson. Vazifa T) (server) ishga tushirilgandan so'ng darhol Si shaxsiy semaforini yaratadi va funksiyani chaqiradi Si-GetQ . Shunday qilib, u Si semafori chiqarilguncha bloklanadi. Task Ti (mijoz) ishga tushgandan so'ng darhol shaxsiy Si semaforini yaratadi, T topshirig'i bilan birgalikda xotirada ma'lumotlarni tayyorlaydi) va Si .PutQ funksiyasini chaqiradi . Bu T) vazifasini faollashtirishga olib keladi. Task Ti ishlashda davom etadi va Si-GetQ funksiyasini chaqiradi, Si semafori chiqarilgunga qadar blokirovka qiladi - Task T) (server) ma'lumotlarni qayta ishlagandan so'ng Si-PutQ , Si.GetQ funktsiyalarini chaqiradi, Ti (mijoz) vazifasini faollashtiradi va o'zini blokirovka qilish. Quyida mijoz-server o'zaro aloqasini amalga oshirishning boshqa usullarini ko'rib chiqamiz.
Do'stlaringiz bilan baham: |