Примењени дистрибуирани системи

Циљ и исход предмета

Увод у концепте и принципе пројектовања у конструкцији конкурентних и дистрибуираних система. По завршетку курса, студент је у стању да: покаже знање и разумевање различитих модела конкурентних система као и модела и архитектура дистрибуираних система; поседује чврсту основу у концептима и принципима пројектовања конкурентних и дистрибуираних система; пројектује и имплементира софтвер у дистрибуираном окружењу.

Теоријска настава

Терминологија и класификација. Узајамно искључивање. Конкурентни објекти. Конкурентност и коректност. Модели конзистентности. Услови за прогрес. Spin-Lock. Test-and-Set (TAS). TTAS. Експоненцијални Backoff. CLH и MSC Queue Lock. Композитни кључ. Кластери и хијерархијски кључеви. Монитори. Семафори. Баријере. Баријере са променом парности. Баријере са комбинационим и статичким стаблом. Баријере са детекцијом завршетка. Трансакциона меморија. Трансакције и атомичност. Софтверска и хардверска трансакциона меморија. Мултипроцесорско распоређивање. Расподела оптерећења. Модел дистрибуираног извршавања. Модели комуникационих мрежа. Глобално стање дистрибуираног система. Пресеци код дистрибуираног израчунавања. Логичко време. Систем логичких часовника. Скаларно време. Векторско време. Матрично време. Синхронизација физичких часовника. Глобално стање и алгоритми за његово снимање. Алгоритми за FIFO и не-FIFO канале. Снимање стања у системима са каузалном испоруком. Налажење конзистентних глобалних снимака. Основни дистрибуирани алгоритми. Синхронизатори. Избор лидера. Редослед порука и групна комуникација. Дистрибуирано узајамно искључивање. Дистрибуирана дељена меморија. Договор и консензус. Детекција отказа.

Практична настава

Имплементације синхронизационих примитива и кључева. Креирање и контрола рада нити. Конкурентни алати. Резервоари нити. Синхронизација. Произвођач – потрошач. Читаоци и писци. Критичне секције. Петерсонов алгоритам. Филтер алгоритам. Лампортов пекарски алгоритам. Spin-Lock и конфликт. Семафори и баријере. Прекид рада и узајамно блокирање нити. GUI – примери конкурености. Дистрибуирани системи и бродкаст. Имплементација векторских часовника. Диференцијална техника. Техника директне зависности. Адаптивна техника. Проблеми у снимању глобалног стања. Алгоритми за FIFO канале. Chandy–Lamport и Spezialetti–Kearns алгоритам. Venkatesan инкрементални алгоритам. Helary таласни синхронизациони метод. Алгоритми за не-FIFO канале. Lai–Yang и Li алгоритам. Mattern алгоритам. Алгоритми за дистрибуирано узајамно искључивање. Лампортов алгоритам. Ricart–Agrawala и Singhal алгоритам. DHT и Chord.