Taqsimlangan tizimlarda sinxronizatsiya

---

Taqsimlangan tizimlarda

sinxronizatsiya

---

Odatda, markazlashtirilmagan algoritmlar quyidagi

xususiyatlarga ega.

• Tegishli ma'lumotlar kompyuterlar orasida tarqatiladi.

• Jarayonlar faqat mahalliy ma'lumotlarga asoslanib qaror qabul qiladi.

• Algoritmning qulashiga olib keladigan bitta tanqidiy nuqta bo'lmasligi

kerak.

• Umumiy soat yoki aniq global vaqtning boshqa manbai yo'q.

---

Vaqtni sinxronlashtirish

• 1978 yilda Lamport vaqtni sinxronlashtirish mumkinligini ko'rsatdi va bunday

sinxronizatsiya uchun algoritmni taklif qildi. Biroq, u mutlaq sinxronizatsiya shart

emasligini aytdi. Agar ikkita jarayon o'zaro ta'sir qilmasa, unda ular bir martalik

vaqtga muhtoj emas deb fikr qoldirgan.

• 17-asrda mexanik soatlar ixtiro qilinganidan keyin vaqt astronomik ravishda

o'lchandi. Ikki ketma-ket quyosh orasidagi vaqt osmonning eng yuqori nuqtasiga etib

borgan vaqtga quyoshli kun deyiladi.

• 1948 yilda atom soatlari ixtiro qilinishi bilan quyoshli kunning tebranishidan qat'iy

nazar vaqtni aniq o'lchash mumkin bo'ldi. Hozirda dunyoning turli burchaklarida

joylashgan 50 ta laboratoriyada Cesium-133 nurlanish chastotasi asosida soatlar

mavjud. O'rtacha qiymat 1958 yil 1-iyuldan hisoblab chiqilgan Xalqaro atom vaqti

(TAI).

• Quyosh vaqtidan TAIning kechikishi bir soniya qo'shilishi bilan qoplanadi, farq 800

mikrosaniyadan oshganda. UTC (Universal Coordinated Time) deb nomlangan ushbu

sozlangan vaqt eski standartni (Grinvich o'rtacha vaqti - Astronomik vaqt) o'rnini

egalladi.

---

Vaqtni sinxronlashtirish algoritmlari.

• Ikkita muammo - soat orqaga yurmasligi kerak (tuzatishni amalga oshirish

uchun uni tezlashtirish yoki sekinlashtirish kerak) va vaqt xabarini yuborish

vaqti nolga teng (siz o'tish vaqtini bir necha marta o'lchab, o'rtacha

ko'rsatkichni olishingiz mumkin).

Muvofiqlashtiruvchini tanlash

• Ko'p taqsimlangan algoritmlar jarayonlardan birini muvofiqlashtiruvchi,

tashabbuskor yoki boshqa maxsus rolni bajarishni talab qiladi. Bunday maxsus

jarayonni tanlash koordinatorni tanlash deb nomlanadi.

---

Badass algoritmi

• Agar jarayon muvofiqlashtiruvchi juda uzoq vaqt davomida javob bermasa, u

saylovni boshlaydi. P jarayoni saylovni quyidagicha o'tkazadi:

• P "SAYLOVLAR" xabarini barcha jarayonlarga undan kattaroq raqamlar bilan

yuboradi.

• Agar javob bo'lmasa, u P g'olib deb hisoblanadi va muvofiqlashtiruvchiga

aylanadi.

• Agar jarayonlardan ko'pi javob bersa, u saylovlarni boshqarishni o'z zimmasiga

oladi. P jarayonining saylovda ishtiroki tugaydi.

• Istalgan vaqtda, jarayonni kam sonli hamkasblaridan biri "SAYLOV" xabarini

olishi mumkin. Bunday holda, u "tirik" degan xabarni yuboradi va u tirikligini va

saylovlarni

o'zi

olib

borishini,

keyin

esa

saylovlarni

boshlashini

yuboradi. Binobarin, barcha jarayonlar saylovni to'xtatadi, bundan mustasno -

yangi koordinator. U barchaga o'zining g'alabasi va lavozimga tayinlanishi haqida

"COORDINATOR" xabarini etkazadi.

---

Doira algoritm.

• Algoritm halqadan foydalanishga asoslangan (fizik yoki mantiqiy), ammo

markerisiz. Har bir jarayon doira ro'yxatdagi keyingisini biladi. Jarayon

muvofiqlashtiruvchi yo'qligini aniqlaganida, u "SAYLOVLAR" xabarini

uning orqasidagi jarayonga raqam bilan birga yuboradi. Agar keyingi

jarayon javob bermasa, ish jarayoni topilgunga qadar va hokazo

jarayonga xabar yuboriladi.

• Har bir ish jarayoni xodimlar ro'yxatiga raqam qo'shadi va xabarni aylana

bo'ylab yo'naltiradi. Jarayon ro'yxatda o'z raqamini topganda, u xabar

turini "COORDINATOR" ga o'zgartiradi va u aylana bo'ylab ketadi va

hamma

xodimlar

ro'yxati

va

muvofiqlashtiruvchini

xabardor

qiladi. Davrani tugatgandan so'ng, xabar o'chiriladi.

---

Markazlashtirilgan algoritm

• Barcha jarayonlar koordinatordan tanqidiy qismga kirish uchun ruxsat

so'rashadi va ushbu ruxsatni kutishadi. Koordinator qabul qilingan

buyurtmalar bo'yicha so'rovlarga xizmat qiladi. Ruxsatni olgach,

jarayon tanqidiy qismga kiradi. Uni tark etganda, u bu haqda

koordinatorga xabar beradi. Tanqidiy qismning har bir qismiga

yuborilgan xabarlar soni - 3 ta.

• Algoritmning kamchiliklari bu markazlashtirilgan algoritmning

odatdagi

kamchiliklari

(koordinatorning

ishdan

chiqishi

yoki

xabarlarning haddan tashqari yuklanishi).

---

Doira marker algoritmi

• Barcha jarayonlar mantiqiy halqani tashkil etadi, chunki kim unga

ergashganini bilsa. Marker halqa atrofida aylanadi, bu tanqidiy qismga kirish

huquqini beradi. Belgini olgandan so'ng, jarayon tanqidiy qismga kiradi

(agar u ruxsat olishni kutayotgan bo'lsa) yoki markerni boshqaga

yo'naltiradi. Tanqidiy qismdan chiqqandan so'ng, marker yana yo'naltiriladi,

bo'limni xuddi shu marker bilan qayta kiritishga yo'l qo'yilmaydi.

Muammolar:

• Agar marker yo'qolsa, u qayta tiklanishi kerak. Yo'qotishni aniqlash qiyin

(kelish vaqti noma'lum).

• Agar biron bir jarayon bajarilmasa, algoritm ishlamaydi. Ammo, boshqa

holatlarga qaraganda, tiklash osonroq.

---

Vaqtga asoslangan markazlashtirilmagan algoritm.

Algoritm Rikart-Agrawala deb nomlangan va Lamport taklif qilgan algoritmni

takomillashtirish hisoblanadi. Tizimdagi barcha voqealarni vaqt bo'yicha global

tartiblash talab qilinadi.

• Tanqidiy qismga kirish: Jarayon tanqidiy qismga kirishni xohlasa, u barcha

bo'limlarga so'rov xabari, muhim bo'lim nomi, jarayon raqami va joriy vaqtni o'z

ichiga oladigan so’rov junatadi. So'rovni yuborganingizdan so'ng, jarayon hamma

unga ruxsat berguncha kutadi. Hammadan ruxsat olgandan so'ng, u tanqidiy

bo'limga kiradi.

• So'rovni qabul qilishda jarayonning harakati: Jarayon, belgilangan kritik qismga

nisbatan holatiga qarab, so'rov xabarini olganda, u quyidagi usullardan birini

bajaradi. Agar qabul qiluvchi tanqidiy bo'limda bo'lmasa va unga kirish uchun

ruxsat so'ramasa, u yuboruvchiga "OK" xabarini yuboradi. Agar qabul qiluvchi

tanqidiy bo'limda bo'lsa, u javob bermaydi, lekin so'rovni eslaydi.

• Agar qabul qiluvchi ushbu bo'limga kirish uchun so'rov bergan bo'lsa, lekin uni

kiritmagan bo'lsa, u so'rov vaqtini va boshqa birovning vaqt belgilarini

taqqoslaydi. Belgisi kichik bo'lgan g'olib chiqadi. Agar boshqa birovning so'rovi

g'alaba qozongan bo'lsa, jarayon "OK" xabarini yuboradi. Agar boshqa so'rovda

yorliq bo'lsa, unda javob yuborilmaydi va so'rov eslab qoladi.