Raymonds algoritmi - Raymonds algorithm - Wikipedia

Raymond algoritmi uchun blokirovka qilishga asoslangan algoritm o'zaro chiqarib tashlash a tarqatilgan tizim. Bu mantiqiy tuzilmani belgilaydi (a K-ary daraxti ) taqsimlangan resurslar to'g'risida. Belgilanganidek, har bir tugun faqat bitta ota-onaga ega, unga belgiga erishish uchun barcha so'rovlar amalga oshiriladi.

Algoritm

Nodal xususiyatlar

  1. Har bir tugunda faqat bitta ota-ona bor, unga qabul qilingan so'rovlar yuboriladi
  2. Har bir tugun a ni saqlaydi FIFO tokenni ko'rgan har safar so'rovlar navbatida;
  3. Agar biron bir tugun imtiyozni boshqa tugunga yo'naltirsa va bo'sh bo'lmagan navbat bo'lsa, u holda so'rov xabarini yuboradi

Algoritm

  1. Agar tugun bo'lsa men (tokenni ushlab turmaslik) unga kirish uchun tokenni olishni xohlaydi muhim bo'lim, u ota-ona tuguniga so'rov yuboradi j.
    • Agar tugun bo'lsa j FIFO bo'sh, tugun j smenalar men uning FIFO navbatiga; j keyin ota-onasiga so'rov yuboradi, k, bu belgini xohlaydi
    • Agar tugun bo'lsa j FIFO navbati emas bo'sh, u shunchaki siljiydi men navbatga
  2. Tugun bo'lganda k tokenga ega va so'rovni qabul qiladi j token yuboradi j va to'plamlar j uning ota-onasi sifatida
  3. Tugun bo'lganda j belgisini oladi k, tokenni oldinga yo'naltiradi men va men navbatidan olib tashlandi j
    • Agar navbat j tokenni yo'naltirgandan so'ng bo'sh emas men, j ga so'rov yuborishi kerak men belgisini qaytarib olish uchun

Eslatma: Agar j tokenni so'rashni xohlaydi va uning navbati emas bo'sh, keyin u o'zini o'z navbatiga qo'yadi. Tugun j uning muhim qismiga kirish uchun belgidan foydalanadi agar token qabul qilinganda u navbatning boshida turadi.

Murakkablik

Raymond algoritmi kafolatlangan O (log n) protsessorlar a ga tuzilgan bo'lsa, muhim bo'limga kirish uchun K-ari daraxt. Bundan tashqari, har bir protsessor ko'pi bilan saqlashi kerak O (log n) bitlar, chunki u kuzatilishi kerak O (1) qo'shnilar.[1]

Adabiyotlar

  1. ^ R. Chou, T. Jonson; Tarqatilgan operatsion tizimlar va algoritmlar; Addison-Uesli, 1997 yil.

Shuningdek qarang