Distributed computing



Download 0,86 Mb.
bet6/38
Sana24.04.2022
Hajmi0,86 Mb.
#578449
1   2   3   4   5   6   7   8   9   ...   38
Bog'liq
distcomp

COMMUNICATION REVIEW

  • Basic distributed communication when no shared memory: send/receive.
  • Location transparency: broker or name server or tuple space.
  • Synchrony and asynchrony are both useful (e.g. real-time vs. informational sensors).
  • Other mechanisms are possible

COMMUNICATION BY SHARED MEMORY: beyond locks

  • Framework: Herlihy, Maurice. “Impossibility and Universality Results for
  • Wait-Free Synchronization,” ACM SIGACT-SIGOPS Symposium
  • on Principles of Distributed Computed (PODC), 1988.
  • In a system that uses mutual exclusion, it is possible that one process may stop while holding a critical resources and hang the entire system.
  • It is of interest to find “wait-free” primitives, in which no process ever waits for another one.
  • The primitive operations include test-and-set, fetch-and-add, and fetch-and-cons.
  • Herlihy shows that certain operations are strictly more powerfully wait-free than others.

CAN MAKE ANYTHING WAIT-FREE (at a time price)

  • Don’t maintain the data structure at all. Instead, just keep a history of the operations.
  • enq(x)
  • put enq(x) on end of history list (fetch-and-cons)
  • end enq(x)
  • deq
  • put deq on end of history list (fetch-and-cons)
  • “replay the array” and figure out what to return
  • end deq
  • Not extremely practical: the deq takes O(number of deq’s + number of enq’s) time.
  • Suggestion is to have certain operations reconstruct the state in an efficient manner.

GENERAL METHOD: COMPARE-AND-SWAP

  • Compare-and-swap takes two values: v and v’. If the register’s current value is v, it is replaced by v’, otherwise it is left unchanged. The register’s old value is returned.
  • temp := compare-and-swap (register, 0, i)
  • if register = 0 then register := i
  • else register is unchanged
  • Use this primitive to perform atomic updates to a data structure.
  • In the following figure, what should the compare-and-swap do?

Download 0,86 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   38




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish