Maekawas algoritmi - Maekawas algorithm - Wikipedia

Maekavaning algoritmi uchun algoritmdir o'zaro chiqarib tashlash a tarqatilgan tizim. Ushbu algoritmning asosini har qanday sayt faqat boshqa saytlarning pastki qismidan ruxsat olish uchun kerak bo'lgan yondashuv kabi kvorum tashkil etadi.

Algoritm

Terminologiya

• A sayt Maekavaning algoritmini boshqaradigan har qanday hisoblash moslamasi
• Muhim bo'limga kirishni istagan har qanday so'rov uchun:
  • The sayt so'rovi muhim bo'limga kirishni talab qiladigan sayt.
  • The qabul qiluvchi sayt so'rov yuboradigan saytdan so'rov olayotgan har qanday boshqa sayt.
• ts unga muvofiq tizimning mahalliy vaqt tamg'asini bildiradi mantiqiy soat.

Algoritm

Sayt talab qilinmoqda:

• So'raladigan sayt ${ displaystyle P_ {i}}$ xabar yuboradi ${ displaystyle { text {request}} (ts, i)}$ uning kvorum to'plamidagi barcha saytlarga ${ displaystyle R_ {i}}$.

Qabul qiluvchi sayt:

• Qabul qilgandan keyin ${ displaystyle { text {request}} (ts, i)}$ xabar, qabul qiluvchi sayt ${ displaystyle P_ {j}}$ bo'ladi:
  • Agar sayt ${ displaystyle P_ {j}}$ ajoyib narsa yo'q ${ displaystyle { text {grant}}}$ xabar (ya'ni, a ${ displaystyle { text {grant}}}$ e'lon qilinmagan xabar), keyin sayt ${ displaystyle P_ {j}}$ yuboradi a ${ displaystyle { text {grant}} (j)}$ saytga xabar ${ displaystyle P_ {i}}$.
  • Agar sayt ${ displaystyle P_ {j}}$ ajoyib narsaga ega ${ displaystyle { text {grant}}}$ so'rovdan yuqori ustuvorlikka ega jarayon bilan xabar, keyin sayt ${ displaystyle P_ {j}}$ yuboradi a ${ displaystyle { text {bajarilmadi}} (j)}$ saytga xabar ${ displaystyle P_ {i}}$ va sayt ${ displaystyle P_ {j}}$ saytdan so'rovni navbatga qo'yadi ${ displaystyle P_ {i}}$.
  • Agar sayt ${ displaystyle P_ {j}}$ ajoyib narsa bor ${ displaystyle { text {grant}}}$ so'rovga qaraganda pastroq ustuvorlikka ega jarayon bilan xabar, keyin sayt ${ displaystyle P_ {j}}$ yuboradi ${ displaystyle { text {inquire}} (j)}$ Hozirda sayt tomonidan muhim bo'limga kirish huquqi berilgan jarayonga xabar ${ displaystyle P_ {j}}$. (Ya'ni, eng zo'rlari bo'lgan sayt ${ displaystyle { text {grant}}}$ xabar.)
• Qabul qilgandan keyin ${ displaystyle { text {inquire}} (j)}$ xabar, sayt ${ displaystyle P_ {k}}$ bo'ladi:
  • A yuboring ${ displaystyle { text {hosil}} (k)}$ saytga xabar ${ displaystyle P_ {j}}$ agar va faqat sayt bo'lsa ${ displaystyle P_ {k}}$ oldi ${ displaystyle { text {bajarilmadi}}}$ boshqa saytdan xabar yoki agar bo'lsa ${ displaystyle P_ {k}}$ boshqa saytga rentabellikni yuborgan, ammo yangisini olmagan ${ displaystyle { text {grant}}}$.
• Qabul qilgandan keyin ${ displaystyle { text {hosil}} (k)}$ xabar, sayt ${ displaystyle P_ {j}}$ bo'ladi:
  • A yuboring ${ displaystyle { text {grant}} (j)}$ so'rov navbatining yuqori qismida so'rovga xabar. Yuqoridagi so'rovlar eng ustuvor ahamiyatga ega ekanligini unutmang.
  • Joy ${ displaystyle P_ {k}}$ uning so'rov navbatiga.
• Qabul qilgandan keyin ${ displaystyle { text {release}} (i)}$ xabar, sayt ${ displaystyle P_ {j}}$ bo'ladi:
  • O'chirish ${ displaystyle P_ {i}}$ uning so'rov navbatidan.
  • A yuboring ${ displaystyle { text {grant}} (j)}$ so'rov navbatining yuqori qismida so'rovga xabar.

Muhim bo'lim:

• Sayt ${ displaystyle P_ {i}}$ a olish bo'yicha muhim bo'limga kiradi ${ displaystyle { text {grant}}}$ barcha saytlardan xabar ${ displaystyle R_ {i}}$.
• Muhim bo'limdan chiqqandan so'ng, ${ displaystyle P_ {i}}$ yuboradi a ${ displaystyle { text {release}} (i)}$ barcha saytlarga xabar ${ displaystyle R_ {i}}$.

Kvorum to'plami (${ displaystyle R_ {x}}$):
Kvorum to'plami quyidagi xususiyatlarga rioya qilishi kerak:

1. ${ displaystyle forall i , forall j , [R_ {i} bigcap R_ {j} neq emptyset]}$
2. ${ displaystyle forall i , [P_ {i} in R_ {i}]}$
3. ${ displaystyle forall i , [| R_ {i} | = K]}$
4. Sayt ${ displaystyle P_ {i}}$ to'liq tarkibida mavjud ${ displaystyle K}$ so'rov to'plamlari

Shuning uchun:

• ${ displaystyle | R_ {i} | geq { sqrt {N-1}}}$

Ishlash

• Tarmoq xabarlari soni; ${ displaystyle 3 { sqrt {N}}}$ ga ${ displaystyle 6 { sqrt {N}}}$
• Sinxronizatsiya kechikishi: 2 ta xabarni tarqatish kechikmoqda
• Algoritm himoya qilinmasdan turib blokirovka qilishi mumkin.^[1][2]

Shuningdek qarang

• Lamportning non ishlab chiqarish algoritmi
• Lamportning taqsimlangan o'zaro chiqarib tashlash algoritmi
• Ricart-Agrawala algoritmi
• Raymond algoritmi

Adabiyotlar

• M. Maekava, "Markazlashtirilmagan tizimlarda o'zaro istisno qilish uchun A √N algoritmi", ACM

Kompyuter tizimidagi operatsiyalar, jild. 3., yo'q. 2., 145-159 betlar, 1985 y.

• Mamoru Maekava, Artur E. Oldehoeft, Rodni R. Oldehoeft (1987). Operatsion tizimlar: Kengaytirilgan tushuncha. Benjamin / Cummings Publishing Company, Inc.
• B. Sanders (1987). Taqsimlangan o'zaro chiqarib tashlash algoritmlarining axborot tarkibi. Kompyuter tizimlarida ACM operatsiyalari, jild. 3, № 2, 145-59 betlar.