Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Конспект лекцій
Предмет:
Мережеві операційні системи
Частина тексту файла (без зображень, графіків і формул):
Мережні операційні системи (2010)
План-конспект лекцій (Частина 2)
Організація роботи розподілених систем
Розподілена система – це набір взаємодіючих незалежних обчислювальних машин які розглядаються користувачем як єдина система.
У схемі взаємодії клієнта та сервера в розподіленій системі (рис.1): t2 >> t1, де t1 – затримка в середині машини-клієнта, t2 - затримка обміну інформацією між клієнтом та сервером (як елементами розподіленої системи).
Основні проблеми: неможливо в підсистемі B дізнатися про зміну в підсистемі А в той самий момент, а лише через час t2.
Основні аспекти організації роботи розподілених систем:
зв'язок – інформаційна взаємодія, обмін даними, обмін повідомленнями та виклик функцій.
організація – диспетчеризація обчислювальних процесів і розподіл обчислювального навантаження, розподіл мережних ресурсів.
іменування створення та підтримка єдиного простору імен.
синхронізація – забезпечення єдиного системного часу (фізичного та логічного) служби точного часу.
Реплікація та несуперечливість – підтримка достовірності (цілісності спільних даних).
надійність – стійкість для помилок опрацювання відмов та виключних ситуацій.
захист – гарантування безпеки при передачі даних і забезпечення санкціонованого доступу до програм і даних.
Рис.1. Схема взаємодії клієнта та сервера в розподіленій системі
Основні задачі СПЗ розподілених систем:
Поєднання процесів користувачів з ресурсами (власне виконання тої задачі для якої створена система).
Віддалені ресурси – це обчислювальні машини інших користувачів пристрої збереження даних і інформаційні ресурси і так далі.
Прозорість – це спрощення механізмів взаємодії користувацьких процесів за рахунок приховування деталей їх функціонування. Від користувацьких процесів приховується той факт що всі обчислювальні процеси та ресурси в системі фізично розподілені між машинами в системі.
Види прозорості:
прозорість доступу (представлення даних);
прозорість місця розташування;
прозорість реплікації (приховує той факт що працюємо з копією, а не самим ресурсом);
відкритість – надання послуг, сервісів, служб звертання до яких вимагає стандартного синтаксису та семантики. Стандартизовані інтерфейси взаємодії на всіх рівнях моделі OSI.
масштабованість – здатність до розширення розподіленої системи:
масштабованість по розміру – легкість підключення нових користувачів та ресурсів;
географічна масштабованість рознесення користувацьких процесів в просторі;
адміністративна масштабованість – це легкість управління та збору інформації про розподілену систему;
Обмін повідомленнями в розподілених системах
Зв'язок є ключовим питанням в розподілі системи
Message interface – створює свої структури даних які не залежить від application.
Message interface – повідомлення поставляється в buffer звідки в ОС.
Message router – завдання – якомога оптимальніше передати повідомлення.
Класифікація способу обміну інформацією
І. За часом існування повідомлення в системі:
стійкий зв'язок – повідомлення, що передається, зберігається в системі обміну доти поки воно не надійде утримувачу.
нерезидентний зв'язок – повідомлення зберігається в системі доти, доки виконуються процеси, які відправляють та отримують ці повідомлення.
UDP протокол – є втіленням не резидентного зв’язку.
ІІ. За способом організації відправки/прийому повідомлень:
Асинхронний зв’язок – відправник продовжує роботу відразу після відправки
Синхронний зв’язок - відправник блокується до того моменту, поки його повідомлення не дійде одержувачу.
T,S – де T=0 стійкий, T=1 нерезидентний, S=0 асинхронний, S=1 синхронний.
0,0 Стійкий асинхронний зв’язок (системи електронної пошти).
0,1 Стійкий синхронний зв’язок (вимагає більше ресурсів).
1,0 Нерезидентний асинхронний зв’язок (UDP, RPC).
1,1 Нерезидентний синхронний зв’язок з синхронізацією по отриманню.
1,1 Нерезидентний синхронний зв’язок з синхронізацією по обробці.
1,1 Нерезидентний синхронний зв’язок з синхронізацією по відповіді.
Стійкий асинхронний зв’язок в розподілених системах
стійкий зв'язок – повідомлення, що передається, зберігається в системі обміну доти поки воно не надійде утримувачу.
асинхронний зв’язок – відправник продовжує роботу відразу після відправки
Приклад: системи електронної пошти.
Стійкий синхронний зв’язок в розподілених системах
Стійкий зв'язок – повідомлення, що передається, зберігається в системі обміну доти поки воно не надійде отримувачу.
Синхронний зв’язок - відправник блокується до того моменту, поки його повідомлення не дійде одержувачу. СС зв'язок потребує найбільше ресурсів (зав. файлів на віддалений комп’ютер)
Нерезидентний асинхронний зв’язок в розподілених системах
Нерезидентний зв'язок – повідомлення зберігається в системі доти, доки виконуються процеси, які відправляють та отримують ці повідомлення.
Асинхронний зв’язок – відправник продовжує роботу відразу після відправки.НА звязок(UDP,RPC)
Нерезидентний синхронний зв’язок в розподілених системах
(з синхронізацією по отримуванню повідомлення)
Нерезидентний зв'язок – повідомлення зберігається в системі доти, доки виконуються процеси, які відправляють та отримують ці повідомлення.
Синхронний зв’язок - відправник блокується до того моменту, поки його повідомлення не дійде одержувачу.
Нерезидентний синхронний зв’язок з синхронізацією по:
отриманню.
обробці.
відповіді (коли відправник повідомлення блокується до отримання квитанції).
Віддалений виклик процедур (RPC – Remote Procedure Call)
Причина необхідності:
Відсутність потрібної функціональності.
Оптимізація обчислюваного процесу.
Оптимізація комунікаційного навантаження.
Послідовність дій, що реалізує RPC:
Програма клієнта викликає клієнтську заглушку.
Клієнтська заглушка створює повідомлення та викликає локальну ОС (назва процедури, що пересилати? куди? які параметри?).
ОС клієнта відсилає повідомлення віддаленій ОС.
Віддалена ОС передає повідомлення так званій серверній заглушці.
Серверна заглушка розпаковує повідомлення і викликає процедуру на сервері.
Сервер виконує процедуру і повертає результат серверній заглушці.
Серверна заглушка запаковує результат повідомлення і викликає свою локальну ОС.
ОС сервера відсилає повідомлення ОС клієнта.
ОС клієнта отримує повідомлення і передає його клієнтській заглушці.
Клієнтська заглушка розпаковує результат повідомлення і пересилає їх програмі.
Класичним прикладом є SunRPC I DCE RPC.
Віддалений виклик методів (RMI)
Цей механізм з’явився разом з ООП.
На відмінну від RPC замість client stub було створено proxy, а замість server stub створено skeleton.
Використовується у DCOM, java RMI, CORBA.
Поняття реплікації та несуперечливості
Поняття реплікації та несуперечливості включає в себе кешування.
Shared memory – спільна пам’ять.
Репліка (replica) – це копія деяких даних. Як правило кількість копій (реплік) необмежена.
Реплікація – це створення потрібної кількості реплік з метою підвищення продуктивності та надійності роботи системи.
Надійність: в разі виникнення помилки, помилкову копію можна замінити на вірну.
Продуктивність: для великої кількості процесів, що звертаються до одних і тих же даних за рахунок створення персональних копій різко зменшується час доступу. Копія даних розміщується поблизу процесу, що їх використовує.
Ціна, яку потрібно заплатити за підвищення надійності і продуктивності це розв’язання проблеми несуперечливості всіх реплік (копій даних).
Несуперечливість – це цілісність даних.
Кожний раз при змінах копії даних вона (копія) починає відрізнятися від усіх інших. Для забезпечення несуперечливості ці зміни треба перенести у всі інші копії. Як і коли треба переносити ці зміни визначає ціну реплікації.
Протиріччя: Реплікація підвищує продуктивність, а забезпечення несуперечливості зменшує.
Основна вимога до реалізації несуперечливості: операція читання повинна давати однаковий результат для кожної реплікації в часі та «просторі» розподіленої системи.
Ключова ідея підтримки несуперечливості: оновлення всіх реплік відбувається як атомарна операція.
Моделі несуперечливості, орієнтовані на дані
Distributed data store
Модель несуперечливості (consistency model) – це домовленість між процесами та банком даних, яка гарантує несуперечливість даних. Класифікація МН:
Жорстка несуперечливість (strict). Абсолютна впорядкованість у часі всіх звертань до пам’яті.
Лінеаризація. Усі процеси спостерігають (бачать) всі звертання до банку даних в одному і тому самому порядку і ці звертання впорядковані згідно логічного часу.
Послідовна модель. Аналогічно до 2, але звертання не впорядковані у логічному часі.
FIFO. Всі процеси бачать операції запису усіх інших процесів у порядку їх виконання. При цьому різні процеси можуть бачити різні послідовності.
Причинно-наслідкова.Усі процеси бачать усі звертання пов’язані причинно-наслідковими зв’язками в одному і тому самому порядку.
Жорстка синхронізація найточніша.
Лінеаризація менш жорстка.
Найбільш широко використовується послідовна модель.
FIFO і причинно-наслідкова – ослаблені моделі в яких відсутній глобальний контроль, в якій послідовності які операції виконувати.
Моделі несуперечливості, орієнтовані на клієнта
Це специфічний випадок, коли система нечутлива до відносно високого ступеня порушення несуперечливості.
Наприклад: корпоративні СУБД, WWW.
Зазвичай в таких системах досить довго не відбувається зміна даних і всі репліки поступово стають несуперечливими. Ця модель називається потенційною несуперечливістю.
Основні проблеми в цьому випадку виникають з мобільними клієнтами, які час від часу змінюють точку підключення.
Способи організації обчислень в розподілених системах
модель клієнт-сервер
віддалені обчислення(аналог клієнт-серверної моделі з універсальним сервером)
GRID-computing
Однорідні(потужність ~ однакова)
Неоднорідні(різні потужності)
Модель віртуального обчислення
Cloud computing
Паралельна віртуальна машина (PVM)
host pool
Інтерфейс передачі повідомлень (MPI)
1 процес може бути одночасно у декількох групах.
Групи процесів
Перша версія – 95
Остання версія МРІ – 97р.
Концепція адаптивного паралелізму
Ідея: програмі передають повноваження
по створенню необхідної кількості паралельних процесів (з врахуванням ресурсів і задачі)
по вибору: де і коли запускати ці процеси
master-worker
Концепція переносу коду
Концепція переносу коду – на противагу переносу даних, це переміщення виконавчого коду з 1 вузла на інший.
Принципи переносу коду:
Підвищення обчислювальної продуктивності.
Оптимізація мережного трафіка.
Забезпечення гнучкості.
В програмі можна розрізнити сегмент коду, сегмент ресурсів, сегмент виконання.
Моделі переносу коду:
Модель слабкої мобільності (переноситься лише сегмент коду java applets)
Модель сильної мобільності (одночасно переносяться сегмент коду та сегмент виконання)
Перенос коду ініційований відправником
SQL-запит
Перенос коду, ініційований отримувачем коду.
Програмні агенти
Програмні агенти (software agents) – це програма, яка діє цілеспрямовано в умовах нестачі інформації або невизначеності.
Синхронізація в розподілених системах: централізовані служби часу
Кожна машина має свій власний таймер, який час від часу синхронізується з показами глобального годинника. Існують міжнародні глобальні служби часу, які видають стандартний найбільш точний час.
GMT – Grinwich meridian time
UTC – Universal Coordinated Time
Є механізм корегування показів UTC до астрономічного часу.
International Atomac Time
Узагальнена схама централізованої синхронізації
Зовнішній
годинник
Синхронізація в розподілених системах: відмітки часу Лампорта
В логічному часі на відміну від фізичного важлива лише послідовність подій, а не точний час їх виникнення.
а в
t
Предекат Лампорта ставить 1 подію перед іншою.
Всі процеси згідні з тим, що з початку відбулася подія а, а пізніше в. В розподіленій системі це означає:
а і в події, які відбулися в 1 процесі, то
а –>в істина
якщо а - це відправка повідомлення, в – отримання цього повідовлення, то
а –> в істина
Якщо для 2 подій не виконуються умови 1 і 2, то вони називаються паралельними.
Транзитивність:
а –>в в –>с, то а –>с .
Відмітки часу Лампорта – це цілі числа, які ставляться у відповідність події.
Алгоритм Лампорта (присвоєння відміток):
Будь яким двом подіям в 1 процесі призначаються відмітки, різняться хоча б на 1.
Кожне повідомлення супроводжується відміткою Лампорта відправника.
Якщо ця відмітка більша за показ логічного годинника отримувача, то він встановлюється в це значення.
Векторні відмітки часу додатково враховують причинно-наслідкові зв’язки.
Алгоритми голосування в розподілених системах.
В децентралізованих розподілених системах, в яких відсутній зовнішній годинник, виникає потреба у виборі головного годинника між рівними, цей вибір називається – голосування.
Необхідні умови для здійснення голосування:
кожний вузол знає кількість інших вузлів N;
кожний вузол має ідентифікатор (наприклад MAC-адресу);
всі вузли поєднанні між собою каналами зв’язку;
Приклади алгоритмів голосування в розподілених системах:
алгоритм забіяки;
алгоритм голосування на кільці;
рандомізований алгоритм голосування;
Голосування в розподілених системах: алгоритм забіяки.
Усі вузли мають ID і знають ID інших вузлів. Схема вузлів кожний з кожним.
Алгоритм:
Вузол, який претендує на лідерство розсилає усім іншим вузлам, з номерами більшими за його, повідомлення у голосуванні.
Якщо йому ніхто не відповів то він стає лідером і повідомляє про це усім іншим клієнтам. Інакше, якщо він отримав відповідь «ОК» то він не стає лідером.
Агент, який отримав повідомлення про голосування, відсилає агенту який прислав повідомлення, відповідь «ОК» і виконує п.п. 1,2
Характеристика: в такий спосіб буде вибрано вузол-лідер (вузол з найбільшим номером) за скінчений час.
Голосування в розподілених системах: алгоритм голосування на кільці.
Алгоритм:
Всі вузли мають ID і поєднанні в кільце з 2-ома сусідніми вузлами.
Якщо номер отриманий від свого сусіда більший за власний, тоді він пересилає його по кільцю. Якщо свій номер більший, тоді пересилає свій номер по кільцю (іншому з двох сусідніх вузлів).
Якщо вузол отримав свій ID то він лідер в даній групі вузлів і повідомляє інші вузли групи про те що він лідер.
Голосування в розподілених системах: рандомізований алгоритм голосування
Необхідні умови:
Вузли не мають ID.
Всі вузли взаємодіють по одно-направленій кільцевій схемі.
Кількість вузлів N відома усім вузлам.
Опис алгоритму:
Кожен вузол може знаходитись в станах S0 , SR . Якщо вузол перейшов в стан S0, тоді свій номер рівний 0. Якщо в стан SR , тоді номер вибирається випадково в межах [1,N].
Алгоритм виконується циклами по N-тактів. В кожному такті вузол передає свій номер та ном. Отр. від сус. вузл, далі до іншого сусіднього вузла.
Після N-тактів роботи, кожен вузол отримав масив з N-номерів. Якщо в цьому масиві є один номер більший за всі інші номери, тоді вузол під цим номером стає лідером.
Якщо таких найбільших номерів є декілька, то всі вузли з цим номером залишаються в стані SR , а інші вузли переходять в стан S0. І цикл алгоритму продовжується для вузлів в стані SR .
25.Децентралізована синхронізація в розподілених системах
Це варіант, коли зовнішній годинник відсутній і треба за скінченну кількість тактів встановити локальний таймер в одне локальне значення.
Як синхронізувати цілком однакові вузли, які не мають затримки:
Задача синхронізації ланцюжку стрільців(Джона Майхілла)
Децентралізована синхронізація
S0 – початковий стан в якому знаходяться всі вузли; S – стан попередньої готовності.
Агенти між собою обмінюються сигналами з різною «швидкістю»(з якою затр. вузол який передав сигнал передасть повідомлення іншому вузлу)
Крайній вузол відправляє в ланцюжок одночасно 2 сигнали ”а1” та ”а3” при цьому специфічно поводиться крайній вузол, він їх віддзеркалить (після цього крайній вузол при отриманні сигналу ”а” переходить в стан S1).
Всі інші вузли виконують такий алгоритм:
Якщо отриманий 1 сигнал, то передати його далі по ланцюжку;
Якщо отримано 2-ва сигнали то віддзеркалити їх, і передати далі по ланцюжку, а також перейти в стан S;
Якщо даний вузол і 2 його сусіди знаходяться в стані, S то зробити потрібну дію (зробити «постріл»).
26.Іменування ресурсів в розподілених системах: розподілений простір імен
Розподілений простір імен(name spase) - принцип відокремлення адреси (точки доступу) від імені сутності(entity)
name resolution(резолюція імен) – процедура дозволяє по імені отримати точку доступу. Точку доступу можна змінити, а ім’я лишається тим самим(локальне незалежне ім’я).
Простір імен забезпечує:
Службу іменування (додавання, видалення, пошуку імен).
Службу резолюції імен (визначення адреси сутності виходячи з її імені).
Ці дві служби робить так зв. name server (сервер імен)
В розподілених системах внаслідок великої кількості сутностей реалізація простору імен розноситься по декількох серверах.
Як правило створюється ієрархія серверів імен, яку зручно поділити на 3-ри рівні:
а) global – глобальні
б) administrative – адміністративні
в) managerial – управлінські
Принцип ієрархії:
стабільність вмісту скеровуючи таблиць (directory tables) визначає рівень сервера імен.
Реалізація процесу резолюції імен (name resolution):
Ітеративна резолюція;
Рекурсивна резолюція.
27.Ітеративна резолюція імен
ns – name server (сервер імен)
Переваги:
Висока надійність;
Низьке навантаження на сервер імен.
Недоліки:
Великі витрати на взаємодію клієнт-сервер
28.Рекурсивна резолюція імен
ns – name server (сервер імен)
Переваги:
Значно більш ефективне кешування результатів за рахунок того, що якась резолюція вже відбулася;
Зниження витрат на взаємодію клієнта з серверами імен.
Недоліки:
Велике навантаження на сервери імен (внаслідок цього на практиці на глобальному рівні застосовують тільки ітеративну резолюцію).
29.Простір імен DNS(Domain Name System)
DNS – найбільше централізована розподілена служба іменувань.
2 основних завдання:
Пошук IP-адрес окремих хостів (вузлів);
Пошук поштових серверів.
DNS-сервера підтримують розподілену базу відображень ім’я – адреса окрім таблиць відображення.
DNS сервер містить посилання на DNS сервери своїх відображень(під доменів)
Для обслуговування кореневого домена виділено декілька дублюючих один одного DNS серверів, адреса яких широко відома.
В DNS забезпечується повна незалежність іменування від розташування сутностей (хостів і т.д.).
30. Служби розподілених каталогів
Служба каталогів – це система організації великих даних про деякі сутності.
В розподіленому каталозі різні його частини зберігаються на різних серверах.
Приклад: служба каталогів Х.500 (ISO стек протоколів OSI)
Ці служби розрізняють елемент каталогу:
Атрибути
Скорочення
Значення
A-attr
A
x, y, z
B-attr
B
b
C-attr
C
c
Множина всіх записів формує інформаційну базу каталогів. Унікальне ім’я кожного елементу формується як набір всіх його атрибутів та їх значення.
Основні операції: додавання/знищення елементів та пошук елементів.
В службі каталогів Х.500 – реалізовані функції read (пошук по атрибутах), list (список синівських вузлів до даного вузла).
На основі перекриття атрибутів формують ієрархічний простір імен, який називається інформаційним деревом каталогів.
31.Іменування та локалізація мобільних сутностей в розподілених системах
Мобільна сутність – це сутність, яка змінює час від часу свою точку доступу.
Як правило мобільна сутність належить управлінському рівню ієрархії серверів імен.
Вирішення задачі при зміні в мобільній сутності:
1. Змінити відображення пари ім’я – адреса.
2. До тієї пари, яка була додаємо нову пару (додавання символічного лінка).
Недоліки: просте переписання пари, зникає зв'язок в певний момент.
Використання проміжного рівня унікальних ідентифікаторів сутностей.
Служба локалізації – визначає де розміщуються сутність з заданим ідентифікатором.
Прості рішення розсилки ідентифікаторі:
широкомовна розсилка (в невеликих мережах)
передача вказівників, це коли при переміщенні з А в В то в А залишається вказівник на В.
32.Локалізація мобільних сутностей на основі базової точки
Базова точка - фіксоване місце з якого відслідковуються переміщення мобільної сутності.
Як правило базова точка – місце створення або підключення мобільної сутності.
Схема мобільної ІР адресації
В ролі ідентифікатора використовується фіксована адреса мобільного хоста. Точкою доступу виступає контрольна ІР адреса.
33. Ієрархічна служба локалізації мобільних сутностей в розподілених системах
Недолік: на основі БТ є зберігання інформації пари фіксована і біжуча адреса.
Замість одної базової точки використовується набір базових точок організованих в ієрархічну структуру по аналогії з доменною системою імен.
Основна ідея: Оптимізація пошуку за рахунок відображення локальності і мобільності сутностей в доменну структуру. Локалізація зводиться до пошуку по дереву.
Кешування вказівникі – багаторівневе кешування, яке дозволяє пришвидшити пошук мобільної сутності за рахунок використання “географічної” інформації.
23.07.2013 12:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора