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.
Do'stlaringiz bilan baham: |