Monitor (sinxronizatsiya) - Monitor (synchronization)

Yilda bir vaqtda dasturlash (parallel dasturlash deb ham ataladi), a monitor imkon beradigan sinxronizatsiya konstruktsiyasi iplar ikkalasiga ham ega bo'lish o'zaro chiqarib tashlash va ma'lum bir shartning yolg'on bo'lishini kutish (blokirovka qilish) qobiliyati. Monitorlarda, shuningdek, boshqa iplarga ularning holati bajarilganligi to'g'risida signal berish mexanizmi mavjud. Monitor a dan iborat muteks (qulf) ob'ekt va holat o'zgaruvchilari. A shart o'zgaruvchisi asosan ma'lum bir shartni kutayotgan iplar konteyneridir. Monitorlar eksklyuziv kirishni tiklash va o'z vazifalarini davom ettirishdan oldin ba'zi bir shartlar bajarilishini kutish uchun eksklyuziv kirishdan vaqtincha voz kechish mexanizmini ta'minlaydi.

Ning yana bir ta'rifi monitor a ipdan xavfsiz sinf, ob'ekt, yoki modul a atrofida o'ralgan muteks usul yoki o'zgaruvchiga bir nechta xavfsiz kirishga ruxsat berish uchun ip. Monitorning o'ziga xos xususiyati shundaki, uning usullari bajariladi o'zaro chiqarib tashlash: Vaqtning har bir nuqtasida, ko'pi bilan bitta ip har qanday birini bajarishi mumkin usullari. Bir yoki bir nechta shart o'zgaruvchilaridan foydalanib, u shuningdek, iplarning ma'lum bir sharoitda kutish qobiliyatini ta'minlay oladi (shu bilan yuqoridagi "monitor" ta'rifidan foydalaniladi). Ushbu maqolaning qolgan qismida ushbu "monitor" ma'nosi "zararli xavfsiz ob'ekt / sinf / modul" deb nomlanadi.

Monitorlar tomonidan ixtiro qilingan Har bir Brinch Xansen[1] va C. A. R. Hoare,[2] va birinchi bo'lib amalga oshirildi Brinch Xansenniki Bir vaqtda Paskal til.[3]

O'zaro chiqarib tashlash

Oddiy misol sifatida bank hisobvarag'ida operatsiyalarni amalga oshirish uchun havfsiz ob'ektni ko'rib chiqing:

monitor sinfi Hisob qaydnomasi {    xususiy int balans: = 0 o'zgarmas balans> = 0 ommaviy usul mantiqiy chekinmoq (int miqdor) old shart miqdori> = 0 { agar qoldiq yolg'onni qaytarish        } boshqa {qoldiq: = qoldiq - miqdor haqiqiy qaytish        }    }    ommaviy usul depozit (int miqdor) old shart summa> = 0 {qoldiq: = qoldiq + summa}}

Ulanish xavfsiz ob'ektning usulini bajarayotganda, deyiladi egallamoq ob'ekt, uni ushlab turish orqali muteks (qulf). Buni amalga oshirish uchun ipdan xavfsiz narsalar amalga oshiriladi vaqtning har bir nuqtasida, ko'pi bilan bitta ip ob'ektni egallashi mumkin. Dastlab qulfdan chiqarilgan qulf har bir ommaviy usulning boshida qulflanadi va har bir ommaviy usuldan har qaytishda qulfdan chiqariladi.

Usullardan birini chaqirgandan so'ng, ip o'z usulini bajarishni boshlashdan oldin boshqa biron bir ish zarrachasi xavfsiz ob'ekt usullarini bajarguncha kutishi kerak. E'tibor bering, ushbu o'zaro istisno qilmasdan, hozirgi misolda, ikkita ip pulni yo'qotishiga yoki sababsiz pul topishiga olib kelishi mumkin. Masalan, hisobdan 1000ni olib qo'ygan ikkita ipning ikkalasi ham to'g'ri qaytishi mumkin, shu bilan balans faqatgina 1000 ga pasayishiga olib keladi, quyidagicha: avval ikkala yo'nalish ham joriy balansni oladi, uni 1000 dan katta topadi va undan 1000ni olib tashlaydi; ikkala ip ham muvozanatni saqlaydi va qaytadi.

The sintaktik shakar "monitor class" yuqoridagi misolda har bir funktsiya bajarilishini mutekslarga o'rash orqali kodning quyidagi asosiy ko'rinishini amalga oshiradi:

sinf Hisob qaydnomasi {    xususiy qulflash myLock xususiy int balans: = 0 o'zgarmas balans> = 0 ommaviy usul mantiqiy chekinmoq (int miqdor) old shart miqdori> = 0 {myLock.acquire () harakat qilib ko'ring {            agar qoldiq yolg'onni qaytarish            } boshqa {qoldiq: = qoldiq - miqdor haqiqiy qaytish            }        } nihoyat {myLock.release ()}} ommaviy usul depozit (int miqdor) old shart miqdori> = 0 {myLock.acquire () harakat qilib ko'ring {qoldiq: = qoldiq + summa} nihoyat {myLock.release ()}}}

Vaziyat o'zgaruvchilari

Muammoni hal qilish

Ko'pgina ilovalar uchun o'zaro chiqarib tashlash etarli emas. Amalga oshirishga urinayotgan mavzular qandaydir holat kutguncha kutilishi kerak P to'g'ri tutadi. A kutish bilan band pastadir

esa emas( P ) qil o'tish

ishlamaydi, chunki o'zaro istisno boshqa har qanday ipni monitorga kirishiga to'sqinlik qiladi, chunki bu shartni bajaradi. Monitorning qulfini ochadigan, ma'lum vaqtni kutadigan, monitorni qulflaydigan va holatni tekshiradigan tsikl kabi boshqa "echimlar" mavjud P. Nazariy jihatdan, u ishlaydi va tiqilib qolmaydi, ammo muammolar paydo bo'ladi. Kerakli darajada kutish vaqtini hal qilish qiyin, juda kichik va ip protsessorni cho'chqaga aylantiradi, juda katta bo'ladi va u javob bermasa kerak. P sharti to'g'ri bo'lganda (yoki) ipga signal berish usuli kerak mumkin edi haqiqat).

Case study: klassik cheklangan ishlab chiqaruvchi / iste'molchi muammosi

Klassik o'xshashlik muammosi cheklangan ishlab chiqaruvchi / iste'molchi, unda a navbat yoki halqa buferi maksimal hajmdagi vazifalar, bir yoki bir nechta iplar navbatga vazifalarni qo'shadigan "ishlab chiqaruvchi" iplar va boshqa bir yoki bir nechta iplar "iste'molchi" qatorlar bo'lib, vazifalarni navbatdan chiqaradi. Navbat xavfli emas deb taxmin qilinadi va u bo'sh, to'la yoki bo'sh va to'liq o'rtasida bo'lishi mumkin. Navbat har doim topshiriqlarga to'la bo'lsa, demak, biz ishlab chiqaruvchilarning iplarini blokirovka qilishimiz kerak. Boshqa tomondan, har doim navbati bo'sh bo'lganida, biz ishlab chiqaruvchilar tomonidan qo'shilganligi sababli, ko'proq vazifalar mavjud bo'lguncha, biz iste'molchilarga kerak bo'ladi.

Navbat qatorlar o'rtasida birgalikda foydalaniladigan ob'ekt bo'lgani uchun unga kirish huquqini olish kerak atom, chunki navbatni an qo'yish mumkin nomuvofiq holat navbat davomida, hech qachon iplar orasida bo'lmasligi kerak. Shunday qilib, navbatga kiradigan har qanday kod a ni tashkil qiladi muhim bo'lim bu o'zaro chiqarib tashlash bilan sinxronlashtirilishi kerak. Agar navbatga kiradigan kodning muhim bo'limlarida kod va protsessor ko'rsatmalari bo'lishi mumkin bo'lsa intervalgacha o'zboshimchalik bilan kontekst kalitlari bir xil protsessordagi iplar orasidan yoki bir nechta protsessorlardan bir vaqtning o'zida ishlaydigan iplardan iborat bo'lsa, unda mos kelmaydigan holatni yuzaga chiqarish xavfi mavjud poyga shartlari.

Sinxronizatsiya qilinmasdan noto'g'ri

Achchiq yondashuv kodni loyihalashtirishdir band-kutish va sinxronizatsiya yo'q, bu kodni poyga shartlariga bo'ysundiradi:

global RingBuffer navbat; // Vazifalar uchun xavfli bo'lgan qo'ng'iroq-bufer.// Har bir ishlab chiqaruvchi ish zarrachalarini aks ettiruvchi usul:jamoat usul ishlab chiqaruvchi() {    esa (to'g'ri) {        vazifa myTask = ...; // Ishlab chiqaruvchi qo'shilishi kerak bo'lgan yangi vazifani bajaradi.        esa (navbat.to'liq()) {} // Navbat to'lmaguncha band bo'ling-kuting.        navbat.enqueue(myTask); // Vazifani navbatga qo'shing.    }}// Iste'molchilarning har bir ishini aks ettiruvchi usul:jamoat usul iste'molchi() {    esa (to'g'ri) {        esa (navbat.isEmpty()) {} // Navbat bo'sh bo'lguncha band - kuting.        myTask = navbat.dequeue(); // Vazifani navbatdan olib tashlang.        doStuff(myTask); // O'chib, topshiriq bilan biron bir narsani bajaring.    }}

Ushbu kod jiddiy muammoga ega, chunki navbatga kirish to'xtatilishi va boshqa qatorlarning navbatga kirishlari bilan bog'lanishi mumkin. The navbat va navbat usullar, ehtimol, navbatning a'zosi o'zgaruvchilarini yangilash bo'yicha ko'rsatmalarga ega, masalan, uning kattaligi, boshlanishi va tugash joylari, navbat elementlarini belgilash va taqsimlash va boshqalar. queue.isEmpty () va navbat .isFull () usullar ushbu umumiy holatni ham o'qiydi. Agar ishlab chiqaruvchilarni / iste'molchilarning iplarini ro'yxatdan o'tkazish / dekektsiya qilish uchun qo'ng'iroqlar paytida o'zaro bog'lanishiga ruxsat berilsa, unda navbatning mos kelmaydigan holati poyga sharoitlariga olib kelishi mumkin. Bundan tashqari, agar bitta iste'molchi navbatdagi iste'molchining "kutish" holatidan chiqib, "kutish" deb chaqirishi orasida navbatni bo'sh qoldirsa, ikkinchi iste'molchi bo'sh navbatdan o'chirishga urinib, xatoga olib keladi. Xuddi shu tarzda, agar prodyuser boshqa prodyuserning "kutish" kutishidan chiqib, "kutish" chaqiruvi orasida navbatni to'liq to'ldirsa, ikkinchi prodyuser xatoga olib keladigan to'liq navbatni qo'shishga harakat qiladi.

Spin-kutish

Yuqorida aytib o'tilganidek, sinxronlashtirishga erishish uchun sodda yondashuv "spin-kutish", unda kodning muhim bo'limlarini himoya qilish uchun muteks ishlatiladi va band-kutish har doim ham band-kutish tekshiruvi o'rtasida qulf olinadi va qo'yib yuboriladi.

global RingBuffer navbat; // Vazifalar uchun xavfli bo'lgan qo'ng'iroq-bufer.global Qulflash navbat; // Vazifalarning qo'ng'iroq-buferi uchun muteks.// Har bir ishlab chiqaruvchi ish zarrachalarini aks ettiruvchi usul:jamoat usul ishlab chiqaruvchi() {    esa (to'g'ri) {        vazifa myTask = ...; // Ishlab chiqaruvchi qo'shilishi kerak bo'lgan yangi vazifani bajaradi.        navbat.sotib olmoq(); // Ishni kutish uchun dastlabki tekshirish uchun qulfni oling.        esa (navbat.to'liq()) { // Navbat to'lmaguncha band bo'ling - kuting.            navbat.ozod qilish();            // Boshqa iplar uchun imkoniyat berish uchun qulfni vaqtincha tushiring            // iste'molchi topshiriqni bajarishi uchun uni ishga tushirish uchun queueLock kerak.            navbat.sotib olmoq(); // "queue.isFull ()" ga keyingi qo'ng'iroq uchun qulfni qayta sotib oling.        }        navbat.enqueue(myTask); // Vazifani navbatga qo'shing.        navbat.ozod qilish(); // Keyingi vazifani qo'shish uchun bizga yana kerak bo'lguncha navbat qulfini tashlang.    }}// Iste'molchilarning har bir ishini aks ettiruvchi usul:jamoat usul iste'molchi() {    esa (to'g'ri) {        navbat.sotib olmoq(); // Ishni kutish uchun dastlabki tekshirish uchun qulfni oling.        esa (navbat.isEmpty()) { // Navbat bo'sh bo'lguncha band - kuting.            navbat.ozod qilish();            // Boshqa iplar uchun imkoniyat berish uchun qulfni vaqtincha tushiring            // ishlab chiqaruvchi vazifani qo'shishi uchun quueLock-ni ishga tushirish kerak.            navbat.sotib olmoq(); // "queue.isEmpty ()" ga keyingi qo'ng'iroq uchun qulfni qayta sotib oling.        }        myTask = navbat.dequeue(); // Vazifani navbatdan olib tashlang.        navbat.ozod qilish(); // Navbatdagi vazifani echish uchun yana kerak bo'lguncha navbat qulfini tashlang.        doStuff(myTask); // O'chib, topshiriq bilan biron bir narsani bajaring.    }}

Ushbu usul mos kelmaydigan holat yuzaga kelmasligini kafolatlaydi, lekin keraksiz band kutish tufayli CPU resurslarini isrof qiladi. Navbat bo'sh bo'lsa ham va ishlab chiqaruvchilarning iplari uzoq vaqt davomida qo'shadigan narsaga ega bo'lmasa ham, iste'molchilar har doim keraksiz kutishmoqda. Xuddi shu tarzda, iste'molchilar o'zlarining dolzarb vazifalarini bajarishda uzoq vaqt to'sib qo'yilgan bo'lsa ham va navbat to'la bo'lsa ham, ishlab chiqaruvchilar doimo kutish bilan band. Bu behuda mexanizm. Buning uchun ishlab chiqaruvchilarning navbatlarini to'liq bo'lmaguncha blokirovka qilish usuli va iste'molchilarning navbatlarini bo'sh bo'lmaguncha blokirovka qilish usuli kerak.

(N.B .: Mutekslarning o'zi ham bo'lishi mumkin spin-qulflar qulfni olish uchun band kutish bilan bog'liq, ammo sarf qilingan protsessor resurslarining bu muammosini hal qilish uchun biz taxmin qilamiz navbat spin-lock emas va blokirovka qilish uchun navbatning o'zi to'g'ri ishlatadi.)

Vaziyat o'zgaruvchilari

Qaror - foydalanish holat o'zgaruvchilari. Kontseptual ravishda shart o'zgaruvchisi - bu monitor bilan bog'liq bo'lgan navbat, bu esa biron bir shart amalga oshishini kutishi mumkin. Shunday qilib har bir shart o'zgaruvchisi v bilan bog'langan tasdiqlash Pv. Ulanish shart o'zgaruvchisini kutayotgan paytda, bu ip monitorni egallaydi deb hisoblanmaydi va shuning uchun monitorning holatini o'zgartirish uchun boshqa iplar monitorga kirishi mumkin. Aksariyat turdagi monitorlarda ushbu boshqa iplar shart o'zgaruvchiga signal berishi mumkin v bu tasdiqni ko'rsatish Pv hozirgi holatga to'g'ri keladi.

Shunday qilib, shart o'zgaruvchilari bo'yicha uchta asosiy operatsiya mavjud:

  • Kutmoq sm, qayerda v shart o'zgaruvchisi va m a muteks (qulf) monitor bilan bog'liq. Ushbu operatsiyani tasdiqlash uchun kutish kerak bo'lgan ip tomonidan chaqiriladi Pv davom etishdan oldin to'g'ri. Ip kutib turganda, u monitorni egallamaydi. "Kutish" operatsiyasining vazifasi va asosiy shartnomasi quyidagi bosqichlarni bajarishdan iborat:
    1. Atomik:
      1. muteksni qo'yib yuboring m,
      2. ushbu ipni "yugurish" dan -ga o'tkazing viplarning "kutish navbatida" ("kutish navbatida") va
      3. bu ipni uxla. (Kontekst boshqa satrga sinxron tarzda uzatiladi.)
    2. Ushbu mavzu keyinchalik xabardor qilingan / signallangan (quyida ko'rib chiqing) va qayta tiklangandan so'ng, avtomatik ravishda mutex-ni qayta sotib oling m.
    1a va 1b bosqichlari har qanday tartibda sodir bo'lishi mumkin, odatda 1c ulardan keyin sodir bo'ladi. Ip uxlab yotgan paytda vnavbat kutish, navbatdagi navbat dastur hisoblagichi bajarilishi 2-bosqichda, "kutish" funktsiyasi o'rtasida /subroutine. Shunday qilib, ip uxlaydi va keyinchalik "kutish" operatsiyasining o'rtasida uyg'onadi.
    1-bosqichda bajariladigan operatsiyalarning atomligi, ularning orasidagi ustun ipni almashtirishidan kelib chiqadigan poyga sharoitlaridan qochish uchun muhimdir. Agar atom bo'lmaganida yuzaga kelishi mumkin bo'lgan bitta nosozlik rejimi bu o'tkazib yuborilgan uyg'onish, unda ip bo'lishi mumkin vuxlash navbatida va muteksni qo'yib yuborishdi, lekin ipning uyqu holatiga o'tishidan oldin o'tkazgichni almashtirish tugmasi paydo bo'ldi va signal / xabar berish operatsiyasi deb nomlangan boshqa bir oqim (pastga qarang) v birinchi ipni orqaga qaytarish vnavbat. Ko'rib chiqilgan birinchi ipni qaytarish bilanoq, uning dastur hisoblagichi 1c bosqichida bo'ladi va u uxlab qoladi va yana uyg'onishi mumkin emas, bu o'zgarmaslikni yoqib qo'yishi kerak edi. vuxlaganda uxlash navbatida. Boshqa poyga shartlari 1a va 1b bosqichlarining tartibiga bog'liq va kontekstni almashtirish joyiga bog'liq.
  • signal v, shuningdek, nomi bilan tanilgan xabar berish v, buni tasdiqlash uchun ip bilan chaqiriladi Pv haqiqat. Monitorning turiga va amalga oshirilishiga qarab, bu bir yoki bir nechta iplarni ko'chiradi v"tayyor navbatga" navbatdagi uyqu yoki uni bajarish uchun boshqa navbat. Muteksni chiqarishdan oldin "signal" / "xabar berish" operatsiyasini bajarish eng yaxshi amaliyot deb hisoblanadi m bilan bog'liq v, lekin kod bir vaqtning o'zida mos ravishda ishlab chiqilgan va ipning bajarilishiga bog'liq bo'lsa, ko'pincha signal berishdan oldin qulfni bo'shatish ham qabul qilinadi. Tarmoqni amalga oshirishga qarab, bu buyurtma rejalashtirishning ustuvor natijalariga ega bo'lishi mumkin. (Ba'zi mualliflar[JSSV? ] Buning o'rniga signal berishdan oldin qulfni bo'shatishni afzal ko'rishni ma'qullang.) Tarmoqni amalga oshirish ushbu buyurtma bo'yicha har qanday maxsus cheklovlarni hujjatlashtirishi kerak.
  • translyatsiya v, shuningdek, nomi bilan tanilgan xabardor qilish v, c ning kutish navbatidagi barcha iplarni uyg'otadigan shunga o'xshash operatsiya. Bu kutish navbatini bo'shatadi. Odatda, bir nechta predikat shartlari bir xil shart o'zgaruvchisi bilan bog'liq bo'lsa, dastur talab qilinadi translyatsiya o'rniga signal chunki noto'g'ri holatni kutayotgan ip uyg'onishi mumkin va keyin darhol to'g'ri bo'lgan holatni kutib turgan ipni uyg'otmasdan darhol uxlab qoladi. Aks holda, agar predikat sharti unga bog'liq bo'lgan shart o'zgaruvchisi bilan bittadan bo'lsa, unda signal ga qaraganda samaraliroq bo'lishi mumkin translyatsiya.

Loyihalash qoidasi bo'yicha bir nechta shartli o'zgaruvchilar bir xil muteks bilan bog'lanishi mumkin, aksincha emas. (Bu birdan ko'pga yozishmalar.) Buning sababi predikat Pv monitorni ishlatadigan barcha iplar uchun bir xil va vaziyat o'zgarishiga olib kelishi mumkin bo'lgan yoki uni o'zgartirishga olib keladigan o'qish mumkin bo'lgan boshqa barcha iplardan o'zaro chiqarib tashlanishi bilan himoyalangan bo'lishi kerak, lekin har xil iplar bo'lishi mumkin bir xil muteksdan foydalanishni talab qiladigan bir xil o'zgaruvchida boshqa shartni kutmoqchi bo'lganlar. Ishlab chiqaruvchi-iste'molchi misolida yuqorida tavsiflangan, navbat noyob muteks ob'ekti bilan himoyalangan bo'lishi kerak, m. "Ishlab chiqaruvchi" iplar blokirovka yordamida monitorda kutishni xohlaydi m va shart o'zgaruvchisi navbat to'la bo'lmaguncha blokirovka qiladi. "Iste'molchi" iplari bir xil muteks yordamida boshqa monitorda kutishni xohlaydi m ammo boshqa shart o'zgaruvchisi navbat bo'sh bo'lmaguncha blokirovka qiladi. Xuddi shu shart o'zgaruvchisi uchun har xil mutekslarga ega bo'lish (odatda) hech qachon mantiqqa to'g'ri kelmaydi, ammo bu klassik misol, nima uchun ko'pincha bir xil muteks yordamida bir nechta shart o'zgaruvchilariga ega bo'lish mantiqiy ekanligini ko'rsatadi. Bir yoki bir nechta shart o'zgaruvchilari (bir yoki bir nechta monitorlar) tomonidan ishlatiladigan muteks ham buni bajaradigan kod bilan bo'lishishi mumkin emas agar mavjud bo'lsa, vaziyat o'zgaruvchilardan foydalaning (va shunchaki uni kutish / uzatish operatsiyalarisiz oladi / chiqaradi) muhim bo'limlar bir vaqtda ma'lumotlarda ma'lum bir shartni kutishni talab qilmang.

Foydalanishni kuzating

Monitorning to'g'ri ishlatilishi quyidagilardan iborat:

sotib olmoq(m); // Ushbu monitorning qulfini sotib oling.esa (!p) { // Biz kutayotgan shart / predikat / tasdiq haqiqat emas ...	Kutmoq(m, Rezyume); // Ushbu monitorning blokirovkasi va holati o'zgaruvchisini kuting.}// ... Kodning muhim qismi bu erda ...signal(cv2); -- Yoki -- xabardor qilish(cv2); // cv2 cv bilan bir xil yoki boshqacha bo'lishi mumkin.ozod qilish(m); // Ushbu monitorning qulfini bo'shating.

Aniqroq aytganda, bu xuddi shu psevdokod, lekin nima bo'layotganini yaxshiroq tushuntirish uchun ko'proq sharhlar bilan:

// ... (oldingi kod)// Monitorga kirish haqida.// Bir vaqtning o'zida bog'langan maslahat mutexini (qulfini) sotib oling// mavzular o'rtasida taqsimlanadigan ma'lumotlar, // hech qanday ikkita ipni oldindan aralashtirib bo'lmaydigan bo'lishini ta'minlash uchun// muhim bir vaqtda turli yadrolarda bir vaqtning o'zida ishlang// bir xil ma'lumotni o'qiydigan yoki yozadigan bo'limlar. Agar boshqasi bo'lsa// ip bu muteksni ushlab tursa, u holda uxlab qoladi// (bloklangan) va m uyqu navbatiga qo'yilgan. (Muteks "m" bo'lmasligi kerak// spin-lock.)sotib olmoq(m);// Endi biz qulfni ushlab turibmiz va holatini tekshirib ko'rishimiz mumkin// birinchi marta.// Biz birinchi marta while tsikli shartini yuqoridagilardan keyin bajaramiz// "acquire", biz so'raymiz: "Shart / predikat / tasdiq mavjudmi// biz allaqachon ro'y berishini kutayapmizmi? "esa (!p()) 	// "p" har qanday ifoda (masalan, o'zgaruvchan yoki 		// function-call) holatini tekshiradigan va		// mantiqiy qiymatga baho beradi. Buning o'zi juda muhimdir		// bo'lim, shuning uchun siz qulfni ushlab turishingiz kerak *		// ushbu "while" tsikl shartini bajarish!				// Agar bu "while" sharti birinchi marta tekshirilayotgan bo'lsa,// keyin biz savol berayapmiz: "Endi buni ishlatadigan yana bir mavzu// monitor menga xabar berdi va meni uyg'otdi va men kontekstga o'tdim// biz qaytib kelishini kutgan shart / predikat / tasdiqni qaytarib oldik// uyg'onganimdan va qayta sotib olgan vaqtim orasida to'g'ri// ushbu kutishning oxirgi takrorlanishida "kutish" chaqiruvi ichidagi qulf yoki// shartning yana yolg'onga aylanishiga sabab bo'lganmi?// shu vaqt ichida buni soxta uyg'onishga aylantirmoqdamisiz?{	// Agar bu tsiklning birinchi takrorlanishi bo'lsa, unda javob bo'ladi	// "yo'q" - shart hali tayyor emas. Aks holda, javob:	// keyingisi. Bu soxta uyg'onish edi, boshqa biron bir voqea sodir bo'ldi	// avval va shartning yana yolg'on bo'lishiga sabab bo'ldi va biz qilishimiz kerak	// yana kuting.	Kutmoq(m, Rezyume);		// Har qanday yadrodagi boshqa biron bir ishning bajarilishini vaqtincha oldini olish		// m yoki cv bo'yicha operatsiyalar.		// qo'yib yuborish (m) // "m" blokirovkasini atomik ravishda chiqarish		// // ushbu bir vaqtda olingan ma'lumotlardan foydalangan holda kod		// // ishlashi mumkin, ushbu mavzuni cv-ga ko'chiring		// // kutish uchun navbat, bu haqda xabar beriladi		// // shart paydo bo'lgandan keyin		// // rost va ushbu mavzuni uxlang. Qayta yoqing		// // boshqa mavzular va yadrolar 		// // m va cv bo'yicha operatsiyalar.		//		// Ushbu yadroda kontekst tugmasi paydo bo'ladi.		//		// Kelajakda biz kutayotgan holat paydo bo'ladi		// true va ushbu monitor (m, cv) dan foydalanadigan boshqa bir oqim ham bajaradi		// ushbu mavzuni uyg'otadigan signal / xabarnoma yoki a		// xabar beringBu bizni uyg'otadi, ya'ni bizni olib chiqib ketishdi		// cv kutish navbatining.		//		// Shu vaqt ichida boshqa iplar shartni keltirib chiqarishi mumkin		// yana yolg'onga aylanadi, yoki shart bir yoki bir nechtasini o'zgartirishi mumkin		// marta, yoki bu haqiqat bo'lib qolishi mumkin.		//		// Ushbu mavzu ba'zi bir yadrolarga qaytarilgan.		//		// sotib olish (m) // qulf "m" qayta sotib olinadi.			// Ushbu tsiklning takrorlanishini tugating va "while" tsikli holatini qayta tekshiring	// predikat hali ham to'g'ri ekanligiga ishonch hosil qiling.	}// Biz kutayotgan shart haqiqat!// Biz hali ham qulfni monitorga kirishdan oldin yoki undan ushlab turibmiz// "kutish" ning oxirgi bajarilishi.// Kodning muhim qismi bu erda joylashgan bo'lib, u bizning predikatimizga ega// rost bo'lishi kerak.// Ushbu kod cv-ning holatini yolg'onga keltirishi va / yoki boshqa shart o'zgaruvchilarga aylanishi mumkin '// predicates true.// Qaysi shart o'zgaruvchiga qarab qo'ng'iroq qiling / xabar bering yoki xabar bering// predikatlar (mutex m bilan o'rtoqlashadiganlar) haqiqatga aylangan yoki haqiqat bo'lishi mumkin,// va ishlatilayotgan monitorning semantik turi.uchun (cv_x yilda cvs_to_notify) {	xabar berish(cv_x); -- Yoki -- xabardor qilish(cv_x);}// Bir yoki bir nechta iplar uyg'otildi, lekin ular urinishi bilanoq bloklanadi// sotib olish m.// Mutexni qo'yib yuboring, shunda xabardor qilingan iplar (lar) va boshqalar o'zlarining muhim qismlariga kirishi mumkin// bo'limlar.ozod qilish(m);

Cheklangan ishlab chiqaruvchi / iste'molchi muammosini hal qilish

Vaziyat o'zgaruvchilaridan foydalanishni joriy qilib, keling, uni qayta ko'rib chiqish va klassik cheklangan ishlab chiqaruvchi / iste'molchi muammosini hal qilish uchun ishlataylik. Klassik echim - navbatdagi bitta qulfni taqsimlaydigan ikkita shartli o'zgaruvchini o'z ichiga olgan ikkita monitordan foydalanish:

global o'zgaruvchan RingBuffer navbat; // Vazifalar uchun xavfli bo'lgan qo'ng'iroq-bufer.global Qulflash navbat;  	// Vazifalarning qo'ng'iroq-buferi uchun muteks. (Spin-qulf emas.)global Rezyume navbatEmptyCV; 	// Navbat kutayotgan iste'molchilar uchun yo'nalishlar o'zgaruvchisi 				// bo'sh bo'lmaslik.                        	// Unga bog'liq bo'lgan qulf "queueLock" dir.global Rezyume navbat .FullCV; 		// Navbatni kutayotgan ishlab chiqaruvchi iplar uchun shart o'zgaruvchisi 				// to'liq bo'lmaslik. Unga tegishli qulf ham "queueLock" dir.// Har bir ishlab chiqaruvchi ish zarrachalarini aks ettiruvchi usul:jamoat usul ishlab chiqaruvchi() {    esa (to'g'ri) {        vazifa myTask = ...; // Ishlab chiqaruvchi qo'shilishi kerak bo'lgan yangi vazifani bajaradi.        navbat.sotib olmoq(); // Dastlabki tekshirishni tekshirish uchun qulfni oling.        esa (navbat.to'liq()) { // Navbat to'la emasligini tekshiring.            // Tarmoq tizimini queueLock-ni atomik ravishda chiqaring,            // ushbu mavzuni queueFullCV-ga qo'shib qo'ying va ushbu mavzuni uxlang.            Kutmoq(navbat, navbat .FullCV);            // So'ngra, "kutish" avtomatik ravishda qayta tekshirish uchun "queueLock" ni oladi            // predikat holati.        }                // Navbatning to'liq bo'lmasligini talab qiluvchi muhim bo'lim.        // N.B .: Biz queueLock-ni ushlab turamiz.        navbat.enqueue(myTask); // Vazifani navbatga qo'shing.        // Endi navbatning bo'sh bo'lmasligi kafolatlanadi, shuning uchun iste'molchi ipiga signal bering        // yoki navbatning bo'sh bo'lishini kutib, bloklanishi mumkin bo'lgan barcha iste'molchilar qatorlari:        signal(navbatEmptyCV); -- Yoki -- xabardor qilish(navbatEmptyCV);                // Navbat bilan bog'liq tanqidiy bo'limlarning oxiri.        navbat.ozod qilish(); // Keyingi vazifani qo'shish uchun bizga yana kerak bo'lguncha navbat qulfini tashlang.    }}// Iste'molchilarning har bir ishini aks ettiruvchi usul:jamoat usul iste'molchi() {    esa (to'g'ri) {        navbat.sotib olmoq(); // Dastlabki tekshirishni tekshirish uchun qulfni oling.        esa (navbat.isEmpty()) { // Navbatning bo'sh emasligini tekshiring.            // Tarmoq tizimini queueLock-ni atomik ravishda chiqaring,            // bu qatorni queueEmptyCV-ga qo'shib qo'ying va ushbu mavzuni uxlang.            Kutmoq(navbat, navbatEmptyCV);            // So'ngra, "kutish" avtomatik ravishda qayta tekshirish uchun "queueLock" ni oladi            // predikat holati.        }        // Navbatning bo'sh bo'lishini talab qiladigan muhim bo'lim.        // N.B .: Biz queueLock-ni ushlab turamiz.        myTask = navbat.dequeue(); // Vazifani navbatdan olib tashlang.        // Endi navbatning to'liq bo'lmasligi kafolatlanadi, shuning uchun ishlab chiqaruvchi ipga signal bering        // yoki blokirovka qilinishi mumkin bo'lgan barcha prodyuserlar navbatning to'liq bo'lmasligini kutib:        signal(navbat .FullCV); -- Yoki -- xabardor qilish(navbat .FullCV);        // Navbat bilan bog'liq tanqidiy bo'limlarning oxiri.        navbat.ozod qilish(); // Navbatdagi vazifani echish uchun yana kerak bo'lguncha navbat qulfini tashlang.        doStuff(myTask); // O'chib, topshiriq bilan biron bir narsani bajaring.    }}

Bu ishlab chiqaruvchi va vazifa navbatini taqsimlovchi iste'molchi iplari o'rtasidagi o'zaro bog'liqlikni ta'minlaydi va spin-qulflar yordamida yuqorida aytib o'tilgan yondashuvda ko'rsatilgandek band-kutishdan ko'ra hech qanday aloqasi bo'lmagan iplarni bloklaydi.

Ushbu echimning bir varianti ishlab chiqaruvchilar uchun ham, iste'molchilar uchun ham "queueFullOrEmptyCV" yoki "queueSizeChangedCV" deb nomlangan bitta shartli o'zgaruvchidan foydalanishi mumkin. Bunday holda, shart o'zgaruvchisi bilan bir nechta shartlar bog'liqdir, masalan, shart o'zgaruvchisi alohida iplar tomonidan tekshirilayotgan shartlarga qaraganda kuchsizroq holatni anglatadi. Vaziyat o'zgaruvchisi navbatning to'liq bo'lmasligini kutayotgan iplarni aks ettiradi va bo'sh bo'lmasligini kutayotganlar. Biroq, buni amalga oshirish foydalanishni talab qiladi xabardor qilish shartli o'zgaruvchini ishlatadigan barcha iplarda va odatiy foydalana olmaydi signal. Buning sababi doimiydir signal sharti hali bajarilmagan noto'g'ri tipdagi ipni uyg'otishi mumkin va bu ip to'g'ri tipdagi ip signal bermasdan uxlab qoladi. Masalan, ishlab chiqaruvchi navbatni to'ldirishi va iste'molchining o'rniga boshqa ishlab chiqaruvchini uyg'otishi mumkin va uyg'ongan ishlab chiqaruvchi yana uxlab qoladi. Qo'shimcha holatda, iste'molchi navbatni bo'shatishi va ishlab chiqaruvchining o'rniga boshqa iste'molchini uyg'otishi mumkin va iste'molchi yana uxlab qoladi. Foydalanish xabardor qilish to'g'ri turdagi ba'zi bir iplar muammo bayonotida kutilganidek davom etishini ta'minlaydi.

Faqat bitta shartli o'zgaruvchini ishlatadigan variant va notifyAll:

global o'zgaruvchan RingBuffer navbat; // Vazifalar uchun xavfli bo'lgan qo'ng'iroq-bufer.global Qulflash navbat; // Vazifalarning qo'ng'iroq-buferi uchun muteks. (Spin-qulf emas.)global Rezyume navbat .FullOrEmptyCV; // Navbat biron bir ish zarrachasi uchun tayyor bo'lmaganda uchun bitta shartli o'zgaruvchi                              // - ya'ni navbatning to'liq bo'lmasligini kutayotgan ishlab chiqaruvchilar uchun                               // va navbatning bo'sh bo'lishini kutayotgan iste'molchilarning yo'nalishlari.                              // Unga bog'langan qulf "queueLock" dir.                              // Oddiy "signal" dan foydalanish xavfsiz emas, chunki u bilan bog'liq                              // bir nechta predikat shartlari (tasdiqlar).// Har bir ishlab chiqaruvchi ish zarrachalarini aks ettiruvchi usul:jamoat usul ishlab chiqaruvchi() {    esa (to'g'ri) {        vazifa myTask = ...; // Ishlab chiqaruvchi qo'shilishi kerak bo'lgan yangi vazifani bajaradi.        navbat.sotib olmoq(); // Dastlabki tekshirishni tekshirish uchun qulfni oling.        esa (navbat.to'liq()) { // Navbat to'la emasligini tekshiring.            // Tarmoq tizimini queueLock-ni atomik ravishda chiqaring,            // ushbu mavzuni tarjimai holga yozib qo'ying va uxlang.            Kutmoq(navbat, navbat .FullOrEmptyCV);            // So'ngra, "kutish" avtomatik ravishda qayta tekshirish uchun "queueLock" ni oladi            // predikat holati.        }                // Navbatning to'liq bo'lmasligini talab qiluvchi muhim bo'lim.        // N.B .: Biz queueLock-ni ushlab turamiz.        navbat.enqueue(myTask); // Vazifani navbatga qo'shing.        // Endi navbatning bo'sh bo'lmasligi kafolatlanadi, shuning uchun barcha bloklangan satrlarga signal bering        // shuning uchun iste'molchi mavzusi vazifani bajarishi kerak:        xabardor qilish(navbat .FullOrEmptyCV); // "signal" dan foydalanmang (chunki uning o'rniga boshqa ishlab chiqaruvchini uyg'otishi mumkin).                // Navbat bilan bog'liq tanqidiy bo'limlarning oxiri.        navbat.ozod qilish(); // Keyingi vazifani qo'shish uchun bizga yana kerak bo'lguncha navbat qulfini tashlang.    }}// Iste'molchilarning har bir ishini aks ettiruvchi usul:jamoat usul iste'molchi() {    esa (to'g'ri) {        navbat.sotib olmoq(); // Dastlabki tekshirishni tekshirish uchun qulfni oling.        esa (navbat.isEmpty()) { // Navbatning bo'sh emasligini tekshiring.            // Tarmoq tizimini queueLock-ni atomik ravishda chiqaring,            // ushbu mavzuni tarjimai holga yozib qo'ying va uxlang.            Kutmoq(navbat, navbat .FullOrEmptyCV);            // So'ngra, "kutish" avtomatik ravishda qayta tekshirish uchun "queueLock" ni oladi            // predikat holati.        }        // Navbatning to'liq bo'lmasligini talab qiluvchi muhim bo'lim.        // N.B .: Biz queueLock-ni ushlab turamiz.        myTask = navbat.dequeue(); // Vazifani navbatdan olib tashlang.        // Endi navbatning to'liq bo'lmasligi kafolatlanadi, shuning uchun barcha bloklangan iplarga signal bering        // shunday qilib, ishlab chiqaruvchi ishchi vazifani bajaradi:        xabardor qilish(navbat .FullOrEmptyCV); // "signal" dan foydalanmang (chunki uning o'rniga boshqa iste'molchini uyg'otishi mumkin).        // Navbat bilan bog'liq tanqidiy bo'limlarning oxiri.        navbat.ozod qilish(); // Navbatdagi vazifani echish uchun yana kerak bo'lguncha navbat qulfini tashlang.        doStuff(myTask); // O'chib, topshiriq bilan biron bir narsani bajaring.    }}

Sinxronizatsiya primitivlari

Mutekslarni va holat o'zgaruvchilarini amalga oshirish uchun qo'shimcha ta'minot tomonidan taqdim etilgan sinxronizatsiya ibtidoiyligi talab qilinadi atomlik. Qulflar va holat o'zgaruvchilari ushbu sinxronizatsiya ibtidoiylariga nisbatan yuqori darajadagi mavhumliklardir. Bir protsessorda uzilishlarni o'chirish va yoqish - bu qulflar va shart o'zgaruvchilarning muhim bo'limlari paytida kontekstni almashtirishni oldini olish orqali monitorlarni amalga oshirishning bir usuli, ammo bu juda protsessorda etarli emas. Ko'p protsessorda, odatda maxsus atom o'qish-o'zgartirish-yozish kabi xotiradagi ko'rsatmalar sinovdan o'tgan, taqqoslash va almashtirishva boshqalarga bog'liq bo'lib, nima bo'lishiga qarab ISA beradi. Bu odatda ichki qulf holatining o'zi uchun spin-blokirovkalashni kechiktirishni talab qiladi, ammo bu qulf juda qisqa. Amalga qarab, o'qish-o'zgartirish-yozish bo'yicha atom yo'riqnomasi avtobusni boshqa yadrolarning kirish joylaridan bloklashi va / yoki protsessorda ko'rsatmalarning qayta tartiblanishiga yo'l qo'ymasligi mumkin. Bu erda ish zarrachalar tizimining qismlari va mutexes va Mesa uslubidagi vaziyat o'zgaruvchilaridan foydalanib, psevdokodni amalga oshirishning bir misoli. sinovdan o'tgan va birinchi kelgan siyosat. Bu ishlov berish tizimining qanday ishlashini aks ettiradi, lekin mutekslar va holat o'zgaruvchilariga tegishli qismlarni ko'rsatadi:

Test-and-Set yordamida Mesa-monitorni amalga oshirish namunasi

// Tarmoq tizimining asosiy qismlari:// "ThreadQueue" tasodifiy kirishni qo'llab-quvvatlaydi.jamoat o'zgaruvchan ThreadQueue tayyor navbat; // Tayyor iplar uchun xavfli bo'lmagan navbat. Elementlar (Ip *).jamoat o'zgaruvchan global Ip* joriyThread; // Ushbu o'zgaruvchini yadro uchun qabul qiling. (Boshqalar umumiy).// Spin-blokirovkasini faqat tishli tizimning o'zi sinxronlangan holatida amalga oshiradi.// Bu sinxronizatsiya ibtidoiy sifatida test-and-set bilan ishlatiladi.jamoat o'zgaruvchan global bool threadingSystemBusy = yolg'on;// Kontekstni almashtirishni to'xtatish xizmatining muntazamligi (ISR):// Amaldagi protsessor yadrosida oldindan boshqa mavzuga o'ting.jamoat usul contextSwitchISR() {    agar (testAndSet(threadingSystemBusy)) {        qaytish; // Hozirda kontekstni almashtirish mumkin emas.    }    // Kontekstni o'zgartirishni buzadigan ushbu uzilishning takrorlanmasligiga ishonch hosil qiling:    systemCall_disableInterrupts();    // Amaldagi jarayonning barcha registrlarini oling.    // Program Counter (PC) uchun bizga ko'rsatma joylashuvi kerak bo'ladi    // quyida joylashgan "rezyume" yorlig'i. Ro'yxatdan o'tish qiymatlarini olish platformaga bog'liq va o'z ichiga olishi mumkin    // joriy stek ramkasini, JMP / CALL ko'rsatmalarini va boshqalarni o'qish (tafsilotlar ushbu doiradan tashqarida.)    joriyThread->registrlar = getAllRegisters(); // Registrlarni "currentThread" moslamasida xotirada saqlang.    joriyThread->registrlar.Kompyuter = Rezyume; qayta boshlash; // Keyingi kompyuterni ushbu usulda quyidagi "rezyume" yorlig'iga o'rnating.    tayyor navbat.enqueue(joriyThread); // Ushbu ipni keyinroq bajarish uchun tayyor navbatga qo'ying.        Ip* otherTread = tayyor navbat.dequeue(); // Olib tashlang va tayyor navbatdan navbatdagi ish zarrachasini oling.        joriyThread = otherTread; // Keyingi satrga tayyor bo'lishi uchun joriy oqim yo'naltirgichining global qiymatini o'zgartiring.    // Registrlarni currentThread / otherThread-dan tiklang, shu qatorda boshqa ish zarrachasining saqlangan kompyuteriga sakrab o'ting    // (quyida "rezyume" da). Shunga qaramay, bu qanday amalga oshirilishining tafsilotlari ushbu doiradan tashqarida.    tiklashRegisters(otherTread.registrlar);    // *** Endi "otherThread" (hozir "joriyThread") ishlayapti! Asl ip endi "uxlamoqda". ***    Rezyume; qayta boshlash: // Bu erda kontekstni bu erga almashtirishda boshqa contextSwitch () chaqiruvi kompyuterni o'rnatishi kerak.    // otherThread to'xtagan joyga qayting.    threadingSystemBusy = yolg'on; // Atom topshirig'i bo'lishi kerak.    systemCall_enableInterrupts(); // Ushbu yadroni oldindan yoqishni qayta yoqing.}// Uxlash usuli:// Amaldagi protsessor yadrosida sinxron kontekst qo'yilmasdan boshqa oqimga o'tadi// tayyor navbatdagi joriy ip.// "threadingSystemBusy" ni ushlab turishi va uzilishlarni o'chirib qo'yishi kerak, shunda bu usul// contextSwitchISR () ni chaqiradigan ipni almashtirish taymeri tomonidan to'xtatilmaydi.// Ushbu usuldan qaytib, "threadingSystemBusy" ni tozalash kerak.jamoat usul threadSleep() {    // Amaldagi jarayonning barcha registrlarini oling.    // Program Counter (PC) uchun bizga ko'rsatma joylashuvi kerak bo'ladi    // quyida joylashgan "rezyume" yorlig'i. Ro'yxatdan o'tish qiymatlarini olish platformaga bog'liq va o'z ichiga olishi mumkin    // joriy stek ramkasini, JMP / CALL ko'rsatmalarini va boshqalarni o'qish (tafsilotlar ushbu doiradan tashqarida.)    joriyThread->registrlar = getAllRegisters(); // Registrlarni "currentThread" moslamasida xotirada saqlang.    joriyThread->registrlar.Kompyuter = Rezyume; qayta boshlash; // Keyingi kompyuterni ushbu usulda quyidagi "rezyume" yorlig'iga o'rnating.    // contextSwitchISR () dan farqli o'laroq, biz currentThread-ni qayta readyQueue-ga joylashtirmaymiz.    // Buning o'rniga u allaqachon muteks yoki shart o'zgaruvchisi navbatiga joylashtirilgan.        Ip* otherTread = tayyor navbat.dequeue(); // Olib tashlang va tayyor navbatdan navbatdagi ish zarrachasini oling.        joriyThread = otherTread; // Keyingi satrga tayyor bo'lishi uchun global oqim yo'naltirgichining qiymatini o'zgartiring.    // Registrlarni currentThread / otherThread-dan tiklang, shu qatorda boshqa ish zarrachasining saqlangan kompyuteriga o'tishni    // (quyida "rezyume" da). Shunga qaramay, bu qanday amalga oshirilishining tafsilotlari ushbu doiradan tashqarida.    tiklashRegisters(otherTread.registrlar);    // *** Endi "otherThread" (hozir "joriyThread") ishlayapti! Asl ip endi "uxlamoqda". ***    Rezyume; qayta boshlash: // Bu erda kontekstni bu erga almashtirishda boshqa contextSwitch () chaqiruvi kompyuterni o'rnatishi kerak.    // otherThread to'xtagan joyga qayting.}jamoat usul Kutmoq(Muteks m, Vaziyat o'zgaruvchan v) {    // Har qanday yadrodagi boshqa iplar ushbu ob'ektga kirganda ichki spin-lock    // "ushlab turilgan" va "threadQueue" yoki "tayyorQueue".    esa (testAndSet(threadingSystemBusy)) {}    // N.B .: "threadingSystemBusy" endi to'g'ri.        // threadSleep () uzilib qolmasligi uchun ushbu yadroda uzilishlarni o'chirish uchun tizim chaqiruvi    // contextSwitchISR () ni chaqiradigan ushbu yadrodagi ipni almashtirish taymeri.    // Ushbu ip uxlab qolishi uchun ko'proq samaradorlik uchun tashqi threadSleep () tugmasi bajarildi    // shart o'zgaruvchan navbatga o'tgandan so'ng.    systemCall_disableInterrupts();     tasdiqlash m.o'tkazildi; // (Xususan, ushbu ip uni ushlab turadigan bo'lishi kerak.)        m.ozod qilish();    v.waitingThreads.enqueue(joriyThread);        threadSleep();        // Thread sleeps ... Thread gets woken up from a signal/broadcast.        threadingSystemBusy = yolg'on; // Must be an atomic assignment.    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.        // Mesa style:    // Context switches may now occur here, making the client caller's predicate false.        m.sotib olmoq();}jamoat usul signal(ConditionVariable v) {    // Internal spin-lock while other threads on any core are accessing this object's    // "held" and "threadQueue", or "readyQueue".    esa (testAndSet(threadingSystemBusy)) {}    // N.B.: "threadingSystemBusy" is now true.        // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by    // the thread-switching timer on this core which would call contextSwitchISR().    // Done outside threadSleep() for more efficiency so that this thread will be sleeped    // right after going on the condition-variable queue.    systemCall_disableInterrupts();        agar (!v.waitingThreads.isEmpty()) {        wokenThread = v.waitingThreads.dequeue();        readyQueue.enqueue(wokenThread);    }        threadingSystemBusy = yolg'on; // Must be an atomic assignment.    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.        // Mesa style:    // The woken thread is not given any priority.}jamoat usul translyatsiya(ConditionVariable v) {    // Internal spin-lock while other threads on any core are accessing this object's    // "held" and "threadQueue", or "readyQueue".    esa (testAndSet(threadingSystemBusy)) {}    // N.B.: "threadingSystemBusy" is now true.        // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by    // the thread-switching timer on this core which would call contextSwitchISR().    // Done outside threadSleep() for more efficiency so that this thread will be sleeped    // right after going on the condition-variable queue.    systemCall_disableInterrupts();        esa (!v.waitingThreads.isEmpty()) {        wokenThread = v.waitingThreads.dequeue();        readyQueue.enqueue(wokenThread);    }        threadingSystemBusy = yolg'on; // Must be an atomic assignment.    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.        // Mesa style:    // The woken threads are not given any priority.}sinf Mutex {    himoyalangan o'zgaruvchan bool o'tkazildi = yolg'on;    xususiy o'zgaruvchan ThreadQueue blockingThreads; // Thread-unsafe queue of blocked threads.  Elements are (Thread*).        jamoat usul sotib olmoq() {        // Internal spin-lock while other threads on any core are accessing this object's        // "held" and "threadQueue", or "readyQueue".        esa (testAndSet(threadingSystemBusy)) {}        // N.B.: "threadingSystemBusy" is now true.                // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by        // the thread-switching timer on this core which would call contextSwitchISR().        // Done outside threadSleep() for more efficiency so that this thread will be sleeped        // right after going on the lock queue.        systemCall_disableInterrupts();        assert !blockingThreads.o'z ichiga oladi(joriyThread);        agar (o'tkazildi) {            // Put "currentThread" on this lock's queue so that it will be            // considered "sleeping" on this lock.            // Note that "currentThread" still needs to be handled by threadSleep().            readyQueue.olib tashlash(joriyThread);            blockingThreads.enqueue(joriyThread);            threadSleep();                        // Now we are woken up, which must be because "held" became false.            assert !o'tkazildi;            assert !blockingThreads.o'z ichiga oladi(joriyThread);        }                o'tkazildi = to'g'ri;                threadingSystemBusy = yolg'on; // Must be an atomic assignment.        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.    }                    jamoat usul ozod qilish() {        // Internal spin-lock while other threads on any core are accessing this object's        // "held" and "threadQueue", or "readyQueue".        esa (testAndSet(threadingSystemBusy)) {}        // N.B.: "threadingSystemBusy" is now true.                // System call to disable interrupts on this core for efficiency.        systemCall_disableInterrupts();                assert o'tkazildi; // (Release should only be performed while the lock is held.)        o'tkazildi = yolg'on;                agar (!blockingThreads.isEmpty()) {            Ip* unblockedThread = blockingThreads.dequeue();            readyQueue.enqueue(unblockedThread);        }                threadingSystemBusy = yolg'on; // Must be an atomic assignment.        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.    }}tuzilmaviy ConditionVariable {    o'zgaruvchan ThreadQueue waitingThreads;}

Semafor

As an example, consider a thread-safe class that implements a semaphore.There are methods to increment (V) and to decrement (P) a private integer s.However, the integer must never be decremented below 0; thus a thread that tries to decrement must wait until the integer is positive.We use a condition variable sIsPositive with an associated assertion of.

monitor class Semafor{    xususiy int s := 0    invariant s >= 0    xususiy Vaziyat sIsPositive /* bilan bog'liq s > 0 */    public method P()    {        esa s = 0:            Kutmoq sIsPositive        assert s > 0        s := s - 1    }    public method V()    {        s := s + 1        assert s> 0 signal sIsPositive    }}

Implemented showing all synchronization (removing the assumption of a thread-safe class and showing the mutex):

sinf Semafor{    xususiy o'zgaruvchan int s := 0    invariant s >= 0    xususiy ConditionVariable sIsPositive /* bilan bog'liq s > 0 */    xususiy Mutex myLock /* Lock on "s" */    public method P()    {        myLock.acquire()        esa s = 0:            Kutmoq(myLock, sIsPositive)        assert s > 0        s := s - 1        myLock.release()    }    public method V()    {        myLock.acquire()        s := s + 1        assert s> 0 signal sIsPositive        myLock.release()    }}

Monitor implemented using semaphores

Conversely, locks and condition variables can also be derived from semaphores, thus making monitors and semaphores reducible to one another:

The implementation given here is incorrect. If a thread calls wait() after broadcast() has been called, an originally thread may be stuck indefinitely, since broadcast() increments the semaphore only enough times for threads already waiting.

jamoat usul Kutmoq(Mutex m, ConditionVariable v) {    assert m.o'tkazildi;    v.internalMutex.sotib olmoq();        v.numWaiters++;    m.ozod qilish(); // Can go before/after the neighboring lines.    v.internalMutex.ozod qilish();    // Another thread could signal here, but that's OK because of how    // semaphores count.  If c.sem's number becomes 1, we'll have no    // waiting time.    v.sem.Proberen(); // Block on the CV.    // Woken    m.sotib olmoq(); // Re-acquire the mutex.}jamoat usul signal(ConditionVariable v) {    v.internalMutex.sotib olmoq();    agar (v.numWaiters > 0) {        v.numWaiters--;        v.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)    }    v.internalMutex.ozod qilish();}jamoat usul translyatsiya(ConditionVariable v) {    v.internalMutex.sotib olmoq();    esa (v.numWaiters > 0) {        v.numWaiters--;        v.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)    }    v.internalMutex.ozod qilish();}sinf Mutex {    himoyalangan boolean o'tkazildi = yolg'on; // For assertions only, to make sure sem's number never goes > 1.    himoyalangan Semafor sem = Semafor(1); // The number shall always be at most 1.                                          // Not held <--> 1; held <--> 0.    jamoat usul sotib olmoq() {        sem.Proberen();        assert !o'tkazildi;        o'tkazildi = to'g'ri;    }        jamoat usul ozod qilish() {        assert o'tkazildi; // Make sure we never Verhogen sem above 1.  That would be bad.        o'tkazildi = yolg'on;        sem.Verhogen();    }}sinf ConditionVariable {    himoyalangan int numWaiters = 0; // Roughly tracks the number of waiters blocked in sem.                                // (The semaphore's internal state is necessarily private.)    himoyalangan Semafor sem = Semafor(0); // Provides the wait queue.    himoyalangan Mutex internalMutex; // (Really another Semaphore.  Protects "numWaiters".)}

Qachon signal happens on a condition variable that at least one other thread is waiting on,there are at least two threads that could then occupy the monitor:the thread that signals and any one of the threads that is waiting. In order that at mostone thread occupies the monitor at each time, a choice must be made. Two schools of thought exist on how best toresolve this choice. This leads to two kinds of condition variables which will be examined next:

  • Blocking condition variables give priority to a signaled thread.
  • Nonblocking condition variables give priority to the signaling thread.

Blocking condition variables

The original proposals by C. A. R. Hoare va Per Brinch Hansen uchun edi blocking condition variables. With a blocking condition variable, the signaling thread must wait outside the monitor (at least) until the signaled thread relinquishes occupancy of the monitor by either returning or by again waiting on a condition variable. Monitors using blocking condition variables are often called Hoare-style monitors or signal-and-urgent-wait monitorlar.

A Hoare style monitor with two condition variables a va b. After Buhr va boshq.

We assume there are two queues of threads associated with each monitor object

  • e is the entrance queue
  • s is a queue of threads that have signaled.

In addition we assume that for each condition variable v, there is a queue

  • v.q, which is a queue for threads waiting on condition variable v

All queues are typically guaranteed to be fair and, in some implementations, may be guaranteed to be birinchi bo'lib birinchi bo'lib chiqdi.

The implementation of each operation is as follows. (We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.)

enter the monitor:    enter the method    agar the monitor is locked        add this thread to e        block this thread    boshqa        lock the monitorleave the monitor:    schedule    qaytish from the methodKutmoq v:    add this thread to v.q    schedule    block this threadsignal v:    agar there is a thread waiting on v.q        select and remove one such thread t from v.q        (t is called "the signaled thread")        add this thread to s        restart t        (so t will occupy the monitor next)        block this threadschedule:    agar there is a thread on s        select and remove one thread from s and restart it        (this thread will occupy the monitor next)    boshqa bo'lsa there is a thread on e        select and remove one thread from e and restart it        (this thread will occupy the monitor next)    boshqa        unlock the monitor        (the monitor will become unoccupied)

The jadval routine selects the next thread to occupy the monitoror, in the absence of any candidate threads, unlocks the monitor.

The resulting signaling discipline is known a "signal and urgent wait," as the signaler must wait, but is given priority over threads on the entrance queue. An alternative is "signal and wait," unda yo'q s queue and signaler waits on the e queue instead.

Some implementations provide a signal and return operation that combines signaling with returning from a procedure.

signal v va qaytish:    agar there is a thread waiting on v.q        select and remove one such thread t from v.q        (t is called "the signaled thread")        restart t        (so t will occupy the monitor next)    boshqa        jadval qaytish from the method

In either case ("signal and urgent wait" or "signal and wait"), when a condition variable is signaled and there is at least one thread on waiting on the condition variable, the signaling thread hands occupancy over to the signaled thread seamlessly, so that no other thread can gain occupancy in between. Agar Pv is true at the start of each signal v operation, it will be true at the end of each Kutmoq v operatsiya. This is summarized by the following shartnomalar. In these contracts, Men is the monitor's invariant.

enter the monitor:    postcondition Menleave the monitor:    precondition MenKutmoq v:    precondition Men    o'zgartiradi the state of the monitor    postcondition Pv va Mensignal v:    precondition Pv va Men    o'zgartiradi the state of the monitor    postcondition Mensignal v va qaytish:    precondition Pv va Men

In these contracts, it is assumed that Men va Pv do not depend on thecontents or lengths of any queues.

(When the condition variable can be queried as to the number of threads waiting on its queue, more sophisticated contracts can be given. For example, a useful pair of contracts, allowing occupancy to be passed without establishing the invariant, is:

Kutmoq v:    precondition Men    o'zgartiradi the state of the monitor    postcondition Pvsignal v    precondition (emas empty(v) va Pv) yoki (empty(v) va Men)    o'zgartiradi the state of the monitor    postcondition Men

See Howard[4] and Buhr va boshq.,[5] ko'proq).

It is important to note here that the assertion Pv is entirely up to the programmer; he or she simply needs to be consistent about what it is.

We conclude this section with an example of a thread-safe class using a blocking monitor that implements a bounded, ipdan xavfsiz suyakka.

monitor class SharedStack {    private const capacity := 10    xususiy int[capacity] A    xususiy int size := 0    invariant 0 <= size va size <= capacity    xususiy BlockingCondition theStackIsNotEmpty /* bilan bog'liq 0 < size va size <= capacity */    xususiy BlockingCondition theStackIsNotFull /* bilan bog'liq 0 <= size va size < capacity */    public method push(int value)    {        agar size = capacity keyin Kutmoq theStackIsNotFull        assert 0 <= size va size < capacity        A[size] := value ; size := size + 1        assert 0 < size va size <= capacity        signal theStackIsNotEmpty va qaytish    }    public method int pop()    {        agar size = 0 keyin Kutmoq theStackIsNotEmpty        assert 0 < size va size <= capacity        size := size - 1 ;        assert 0 <= size va size < capacity        signal theStackIsNotFull va qaytish A[size]    }}

Note that, in this example, the thread-safe stack is internally providing a mutex, which, as in the earlier producer/consumer example, is shared by both condition variables, which are checking different conditions on the same concurrent data. The only difference is that the producer/consumer example assumed a regular non-thread-safe queue and was using a standalone mutex and condition variables, without these details of the monitor abstracted away as is the case here. In this example, when the "wait" operation is called, it must somehow be supplied with the thread-safe stack's mutex, such as if the "wait" operation is an integrated part of the "monitor class". Aside from this kind of abstracted functionality, when a "raw" monitor is used, it will har doim have to include a mutex and a condition variable, with a unique mutex for each condition variable.

Nonblocking condition variables

Bilan nonblocking condition variables (shuningdek, deyiladi "Mesa style" condition variables or "signal and continue" condition variables), signaling does not cause the signaling thread to lose occupancy of the monitor. Instead the signaled threads are moved to the e navbat. There is no need for the s navbat.

A Mesa style monitor with two condition variables a va b

With nonblocking condition variables, the signal operation is often called notify — a terminology we will follow here. It is also common to provide a notify all operation that moves all threads waiting on a condition variable to the e navbat.

The meaning of various operations are given here. (We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.)

enter the monitor:    enter the method    agar the monitor is locked        add this thread to e        block this thread    boshqa        lock the monitorleave the monitor:    schedule    qaytish from the methodKutmoq v:    add this thread to v.q    schedule    block this threadnotify v:    if there is a thread waiting on v.q        select and remove one thread t from v.q        (t is called "the notified thread")        move t to enotify all v:    move all threads waiting on v.q to eschedule :    agar there is a thread on e        select and remove one thread from e and restart it    boshqa        unlock the monitor

As a variation on this scheme, the notified thread may be moved to a queue called w, which has priority over e. See Howard[4] and Buhr va boshq.[5] keyingi muhokama uchun.

It is possible to associate an assertion Pv with each condition variable v shu kabi Pv is sure to be true upon return from Kutmoq v. However, one mustensure that Pv is preserved from the time the notifying thread gives up occupancy until the notified thread is selected to re-enter the monitor. Between these times there could be activity by other occupants. Thus it is common for Pv to simply be to'g'ri.

For this reason, it is usually necessary to enclose each Kutmoq operation in a loop like this

esa emas( P ) qil    Kutmoq v

qayerda P is some condition stronger than Pv. Amaliyotlar notify v va notify all v are treated as "hints" that P may be true for some waiting thread.Every iteration of such a loop past the first represents a lost notification; thus with nonblocking monitors, one must be careful to ensure that too many notifications can not be lost.

As an example of "hinting" consider a bank account in which a withdrawing thread will wait until the account has sufficient funds before proceeding

monitor class Account {    xususiy int balance := 0    invariant balance >= 0    xususiy NonblockingCondition balanceMayBeBigEnough    public method withdraw(int amount)        precondition amount >= 0    {        esa balance < amount qil Kutmoq balanceMayBeBigEnough        assert balance >= amount        balance := balance - amount    }    public method deposit(int amount)        precondition amount >= 0    {        balance := balance + amount        notify all balanceMayBeBigEnough    }}

In this example, the condition being waited for is a function of the amount to be withdrawn, so it is impossible for a depositing thread to bilish that it made such a condition true. It makes sense in this case to allow each waiting thread into the monitor (one at a time) to check if its assertion is true.

Implicit condition variable monitors

A Java style monitor

In Java language, each object may be used as a monitor. Methods requiring mutual exclusion must be explicitly marked with the synchronized kalit so'z. Blocks of code may also be marked by synchronized.

Rather than having explicit condition variables, each monitor (i.e. object) is equipped with a single wait queue in addition to its entrance queue. All waiting is done on this single wait queue and all notify va notifyAll operations apply to this queue. This approach has been adopted in other languages, for example C #.

Implicit signaling

Another approach to signaling is to omit the signal operatsiya. Whenever a thread leaves the monitor (by returning or waiting) the assertions of all waiting threads are evaluated until one is found to be true. In such a system, condition variables are not needed, but the assertions must be explicitly coded. The contract for wait is

Kutmoq P:    precondition Men    o'zgartiradi the state of the monitor    postcondition P va Men

Tarix

Brinch Hansen and Hoare developed the monitor concept in the early 1970s, based on earlier ideas of their own and of Edsger Dijkstra.[6] Brinch Hansen published the first monitor notation, adopting the sinf concept of Simula 67,[1] va navbat mexanizmini ixtiro qildi.[7] Hoare jarayonni qayta boshlash qoidalarini takomillashtirdi.[2] Brinch Hansen created the first implementation of monitors, in Bir vaqtda Paskal.[6] Hoare demonstrated their equivalence to semaforalar.

Monitors (and Concurrent Pascal) were soon used to structure process synchronization in the Solo operating system.[8][9]

Programming languages that have supported monitors include:

A number of libraries have been written that allow monitors to be constructed in languages that do not support them natively. When library calls are used, it is up to the programmer to explicitly mark the start and end of code executed with mutual exclusion. Pthreads is one such library.

Shuningdek qarang

Izohlar

  1. ^ a b Brinch Xansen, Per (1973). "7.2 Class Concept" (PDF). Operatsion tizim tamoyillari. Prentice Hall. ISBN  978-0-13-637843-3.
  2. ^ a b Hoare, C. A. R. (October 1974). "Monitorlar: operatsion tizimni tuzilish kontseptsiyasi". Kom. ACM. 17 (10): 549–557. CiteSeerX  10.1.1.24.6394. doi:10.1145/355620.361161. S2CID  1005769.
  3. ^ Hansen, P. B. (1975 yil iyun). "The programming language Concurrent Pascal" (PDF). IEEE Trans. Dasturiy ta'minot. Ing. SE-1 (2): 199–207. doi:10.1109/TSE.1975.6312840. S2CID  2000388.
  4. ^ a b Howard, John H. (1976). "Signaling in monitors". ICSE '76 Proceedings of the 2nd international conference on Software engineering. International Conference on Software Engineering. Los Alamitos, Kaliforniya, AQSh: IEEE Computer Society Press. 47-52 betlar.
  5. ^ a b Buhr, Peter A.; Fortier, Michel; Coffin, Michael H. (March 1995). "Monitor classification". ACM hisoblash tadqiqotlari. 27 (1): 63–107. doi:10.1145/214037.214100. S2CID  207193134.
  6. ^ a b Xansen, Per Brinch (1993). "Monitors and concurrent Pascal: a personal history". HOPL-II: The second ACM SIGPLAN conference on History of programming languages. History of Programming Languages. New York, NY, USA: ACM. 1-35 betlar. doi:10.1145/155360.155361. ISBN  0-89791-570-4.
  7. ^ Brinch Xansen, Per (1972 yil iyul). "Tarkibiy dasturlash (taklif qilingan qog'oz)". ACM aloqalari. 15 (7): 574–578. doi:10.1145/361454.361473. S2CID  14125530.
  8. ^ Brinch Xansen, Per (1976 yil aprel). "Yakkaxon operatsion tizim: bir vaqtda Paskal dasturi" (PDF). Dasturiy ta'minot - Amaliyot va tajriba.
  9. ^ Brinch Xansen, Per (1977). Bir vaqtda olib boriladigan dasturlarning arxitekturasi. Prentice Hall. ISBN  978-0-13-044628-2.

Qo'shimcha o'qish

Tashqi havolalar