Suzuki-Kasami algoritmi - Suzuki–Kasami algorithm - Wikipedia

The Suzuki-Kasami algoritmi[1] a nishon asoslangan algoritm erishish uchun o'zaro chiqarib tashlash yilda tarqatilgan tizimlar. Tokeni ushlab turish jarayoni unga kirishga qodir bo'lgan yagona jarayondir muhim bo'lim.

Bu uchun o'zgartirish Ricart-Agrawala algoritmi[2] unda muhim bo'limga erishish uchun REQUEST va REPLY xabari ishlatiladi. ammo bu algoritmda ular katta yoshdagi vizani va boshqa muhim tugunni bitta tugmachaga bitta PRIVILEGE xabarini yuborish orqali boshqa tugunga topshirish usulini joriy qildilar. Shunday qilib, imtiyozga ega bo'lgan tugun muhim bo'limdan foydalanishi mumkin va agar u bo'lmasa, u qila olmaydi. Agar jarayon o'zining muhim bo'limiga kirishni xohlasa va unda belgi bo'lmasa, u tizimdagi barcha boshqa jarayonlarga so'rov xabarini uzatadi. Tokenga ega bo'lgan jarayon, agar u hozirda muhim bo'limda bo'lmasa, u holda belgini so'rov jarayoniga yuboradi. Algoritm xabarlarning buyurtmadan tashqariga chiqishiga imkon berish uchun ortib borayotgan So'rov raqamlaridan foydalanadi.

Algoritm tavsifi

Ruxsat bering jarayonlarning soni. Har bir jarayon butun son bilan aniqlanadi .

Ma'lumotlar tuzilmalari

Har bir jarayon bitta ma'lumot tuzilishini saqlaydi:

  • qator (So'rov raqami uchun), qaerda oxirgi olingan So'rov raqamini saqlaydi

Token ikkita ma'lumotlar tuzilishini o'z ichiga oladi:

  • qator (oxirgi so'rov raqami uchun), qaerda eng so'nggi so'rovlar sonini saqlaydi buning uchun nishon muvaffaqiyatli berildi
  • token kutayotgan jarayonlar identifikatorini saqlaydigan navbat Q

Algoritm

Muhim bo'limni (CS) so'rash

Jarayon qachon CS-ga kirishni xohlaydi, agar unga belgi bo'lmasa, u:

  • uning tartib raqamini oshiradi
  • tizimdagi barcha jarayonlarga yangi tartib raqamini o'z ichiga olgan so'rov xabarini yuboradi

CS-ni chiqarish

Jarayon qachon CS-ni tark etadi, u:

  • to'plamlar belgisiga teng . Bu uning so'rovidan dalolat beradi qatl etildi
  • har bir jarayon uchun belgi navbatida emas , u qo'shiladi ga agar . Bu jarayonni ko'rsatadi bajarilmagan so'rovi bor
  • agar token navbati bo'lsa ushbu yangilanishdan so'ng bo'sh emas, jarayon identifikatorini ochadi dan va belgini yuboradi
  • aks holda, bu belgini ushlab turadi

So'rov qabul qilindi

Jarayon qachon dan so'rov oladi tartib raqami bilan , u:

  • to'plamlar ga (agar , xabar eskirgan)
  • agar jarayon belgisi bor va u CS-da emas va agar bo'lsa (bajarilmagan so'rovni ko'rsatib), u ma'lumotni ishlashga yuboradi

CS-ni bajarish

Jarayon tokenni qo'lga kiritgandan so'ng CS ga kiradi.

Ishlash

  • Yoki yoki CS-ni chaqirish uchun xabarlar (agar jarayonda belgi bo'lsa, xabar yo'q; aks holda so'rovlar va javob berish)
  • Sinxronizatsiya kechikishi yoki ( so'rovlar va javob berish)

Algoritm bo'yicha eslatmalar

  • CS-ga hozirda tokenni ushlab turgan saytgina kirish huquqiga ega
  • KSni tayinlash bilan bog'liq barcha jarayonlar
  • Barchaga yuborilgan xabarlarni so'rang tugunlar
  • Eskirgan so'rovlarni kuzatib borish uchun foydalaniladi
  • Ular har bir saytda mustaqil ravishda rivojlanadilar

Algoritmning asosiy dizayn masalalari:

  • Hozirgi talablardan eskirgan so'rovlarni aytib berish
  • Keyingi belgini qaysi saytga olishini aniqlash

Adabiyotlar

  1. ^ Ichiro Suzuki, Tadao Kasami, Taqsimlangan o'zaro chiqarib tashlash algoritmi, Kompyuter tizimlarida ACM operatsiyalari, 3-jild, 4-son, 1985 yil noyabr (344 - 349 betlar)
  2. ^ Rikart, Glen va Ashok K. Agrawala. "Kompyuter tarmoqlarida o'zaro istisno qilishning optimal algoritmi. "ACM 24.1 aloqalari (1981): 9-17.