Реферат: Синхронизация в распределенных системах - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Синхронизация в распределенных системах

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 40 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Синхронизация в распределенных системах К вопросам свя зи процессов , реализуемой путем передачи сообщений или вызовов RPC, тесно примыкают и вопросы синхронизации процессов . Синхронизация необходима процессам для организации совместного использования ресурсов , таких как файлы и ли устройства , а также для обмена данными . В однопроцессорных системах решение задач взаимного исключения , критических областе й и других проблем синхронизации осуществляло сь с использованием общих методов , таких к ак семафоры и мониторы . Однако эти методы не совсем подходят для распределенных си стем, так как все они базируются на использовании разделяемой оперативной памяти . Например , два процесса , которые взаимодействуют , используя семафор , должны иметь доступ к нему . Если оба процесса выполняются на одной и той же машине , они могут им еть совместный доступ к семафору , хранящемуся , например , в ядре , делая системные вызовы . Однако , если процессы выполняются на разных машинах , то этот метод не пр именим , для распределенных систем нужны новые подходы . Алгоритм синхрони зации логических часов В централизова нной однопроцессорной системе , как правил о , важно только относительное время и не важна точность часов . В распределенной си стеме , где каждый процессор имеет собственные часы со своей точностью хода , ситуация резко меняется : программы , использующие время ( н апример , программы , подобные команде make в UNIX, которые используют время создания ф айлов , или программы , для которых важно вр емя прибытия сообщений и т.п .) становятся з ависимыми от того , часами какого компьютера они пользуются . В распределенных системах синхронизация физических часов (показ ывающих реальное время ) является сложной проб лемой , но с другой стороны очень часто в этом нет никакой необходимости : то ес ть процессам не нужно , чтобы во всех м ашинах было правильное время , для них важн о , чтобы оно бы л о везде одинак овое , более того , для некоторых процессов важен только правильный порядок событий . В этом случае мы имеем дело с логическим и часами . Введем для двух произвольных событий отношение "случилось до ". Выражение a ® b читается "a случилось до b" и означает , что все процессы в системе считают , что сначала произошло событие a, а потом - событие b. Отно шение "случилось до " обладает свойством транзи тивности : если выражения a ® b и b ® c истинны , то справедливо и выражение a ® c. Для дв ух событий одног о и того же процесса всегда можно установить отношение "с лучилось до ", аналогично может быть установлен о это отношение и для событий передачи сообщения одним процессом и приемом его другим , так как прием не может произойт и раньше отправки . Однако , если два произвольных события случились в разных процессах на разных машинах , и эти пр оцессы не имеют между собой никакой связи (даже косвенной через третьи процессы ), то нельзя сказать с полной определенностью , какое из событий произошло раньше , а какое позже . Ст авится задача создания такого м еханизма ведения времени , который бы для к аждого события а мог указать значение вре мени Т (а ), с которым бы были согласны все процессы в системе . При этом долж но выполняться условие : если а ® b , то Т (а ) < Т (b). Кроме того , в р емя м ожет только увеличиваться и , следовательно , лю бые корректировки времени могут выполняться т олько путем добавления положительных значений , и никогда - путем вычитания . Рассмотрим алгоритм решения этой задачи , который предложил Lamport. Для отметок вре мени в нем используются события . На рисунк е 3.6 показаны три процесса , выполняющихся на разных машинах , каждая из которых имеет свои часы , идущие со своей скоростью . Ка к видно из рисунка , когда часы процесса 0 показали время 6, в процессе 1 часы показывал и 8, а в процессе 2 - 10. Предполагается , что все эти часы идут с постоянной для себя скоростью . В момент времени 6 процесс 0 посылает со общение А процессу 1. Это сообщение приходит к процессу 1 в момент времени 16 по его часам . В логическом смысле это впо л не возможно , так как 6<16. Аналогично , сообщение В , посланное процессом 1 процессу 2 пришло к последнему в момент времени 40, то есть е го передача заняла 16 единиц времени , что та кже является правдоподобным . Рис . 3.6. Синхронизация логических ч асов а - три процесса , каждый со своими собственными часами ; б - алгоритм синхронизации логических часов Ну а далее начинаются весьма странные вещи . Сообщение С от процесса 2 к процессу 1 бы ло отправлено в момент времени 64, а поступи ло в место назначения в момент времени 54. Очевидно , что это невозможно . Такие ситуаци и необходимо предотвращать . Решение Lampor t 'а вытекает непосредственно из отношени й "случилось до ". Так как С было отправ лено в момент 60, то оно должно дойти в момент 61 или позже . Следовательно , каждое с ообщение должно нести с собой время своег о отправления по часам машины-отправителя . Есл и в ма ш ине , получившей сообщение , часы показывают время , которое меньше вр емени отправления , то эти часы переводятся вперед , так , чтобы они показали время , бо льшее времени отправления сообщения . На рисун ке 3.6,б видно , что С поступило в момент 61, а сообщение D - в 70. Этот алгоритм удовлетворяет сформулированным выше требованиям . Алгоритмы взаимно го исключения Системы , состоящие из нескольких процессов , часто легче прог раммировать , используя так называемые критические секции . Когда процессу нужно читать или мод ифицировать некоторые разделяемые стр уктуры данных , он прежде всего входит в критическую секцию для того , чтобы обеспечи ть себе исключительное право использования эт их данных , при этом он уверен , что ника кой процесс не будет иметь доступа к этому ресурсу о дновременно с ним . Это называется взаимным исключением . В одно процессорных системах критические секции защищаю тся семафорами , мониторами и другими аналогич ными конструкциями . Рассмотрим , какие алгоритмы могут быть использованы в распределенных с истемах . Ц ентрализованный алгоритм Наиболее очевидный и простой путь реа лизации взаимного исключения в распределенных системах - это применение тех же методов , которые используются в однопроцессорных систем ах . Один из процессов выбирается в качеств е координатора (н апример , процесс , выполняю щийся на машине , имеющей наибольшее значение сетевого адреса ). Когда какой-либо процесс хочет войти в критическую секцию , он по сылает сообщение с запросом к координатору , оповещая его о том , в какую критическую секцию он хочет во й ти , и ждет от координатора разрешение . Если в эт от момент ни один из процессов не нах одится в критической секции , то координатор посылает ответ с разрешением . Если же н екоторый процесс уже выполняет критическую се кцию , связанную с данным ресурсом , то ника к ой ответ не посылается ; запрашива вший процесс ставится в очередь , и после освобождения критической секции ему отправля ется ответ-разрешение . Этот алгоритм гарантирует взаимное исключение , но вследствие своей це нтрализованной природы обладает низкой отказо у стойчивостью . Распределенный алгоритм Когда процесс хочет войти в критическ ую секцию , он формирует сообщение , содержащее имя нужной ему критической секции , номер процесса и текущее значение времени . Зате м он посылает это сообщение всем другим процессам . Предполагается , что передача со общения надежна , то есть получение каждого сообщения сопровождается подтверждением . Когда процесс получает сообщение такого рода , его действия зависят от того , в каком состо янии по отношению к указанной в сообщении критическ о й секции он находится . Имеют место три ситуации : 1. Если получатель не находится и н е собирается входить в критическую секцию в данный момент , то он отсылает назад процессу-отправителю сообщение с разрешением . 2. Если получатель уже находится в критическ ой секции , то он не отправляет никакого ответа , а ставит запрос в очередь . 3. Если получатель хочет войти в критическую секцию , но еще не сделал этого , то он сравнивает временную отметку поступившего сообщения со значением времени , которое содержится в ег о с обственном сообщении , разосланном всем другим процессам . Если время в поступившем к нем у сообщении меньше , то есть его собственны й запрос возник позже , то он посылает сообщение-разрешение , в обратном случае он не посылает ничего и ставит поступившее со о бщение-запрос в очередь . Процесс может войти в критическую секцию только в том случае , если он получил ответные сообщения-р азрешения от всех остальных процессов . Когда процесс покидает критическую секцию , он п осылает разрешение всем процессам из своей оче реди и исключает их из очереди . Алгоритм Token Ring Совершенно другой подход к достижению взаимного исключения в распределенных системах иллюстрируется рисунком 3.7. Все процессы систе мы образуют логическое кольцо , т.е . каждый процесс знает номер своей п озиции в кольце , а также номер ближайшего к нему следующего процесса . Когда кольцо инициализи руется , процессу 0 передается так называемый то кен . Токен циркулирует по кольцу . Он перех одит от процесса n к процессу n+1 путем перед ачи сообщения по типу "точка- точка ". Ког да процесс получает токен от своего сосед а , он анализирует , не требуется ли ему самому войти в критическую секцию . Если да , то процесс входит в критическую секцию . После того , как процесс выйдет из кри тической секции , он передает токен дальше п о кольцу . Если же процесс , приня вший токен от своего соседа , не заинтересо ван во вхождении в критическую секцию , то он сразу отправляет токен в кольцо . С ледовательно , если ни один из процессов не желает входить в критическую секцию , то в этом случае токен п росто циркулирует по кольцу с высокой скоростью . Сравним эти три алгоритма взаимного и сключения . Централизованный алгоритм является наи более простым и наиболее эффективным . При его использовании требуется только три сообще ния для того , чтобы процесс вошел и покинул критическую секцию : запрос и сооб щение-разрешение для входа и сообщение об освобождении ресурса при выходе . При использо вании распределенного алгоритма для одного ис пользования критической секции требуется послать (n-1) сообщений-запросов (где n - число п роцессов ) - по одному на каждый процесс и получить (n-1) сообщений-разрешений , то есть всего необходимо 2(n-1) сообщений . В алгоритме Token Ring число сообщений переменно : от 1 в случае , если каждый процесс входил в критическую секцию , до бескон е чно большого числа , п ри циркуляции токена по кольцу , в котором ни один процесс не входил в критичес кую секцию . К сожалению все эти три алгоритма плохо защищены от отказов . В первом слу чае к краху приводит отказ координатора , в о втором - отказ любого проце сса (парад оксально , но распределенный алгоритм оказывается менее отказоустойчивым , чем централизованный ), а в третьем - потеря токена или отказ процесса . Рис . 3.7. Средства взаимного исключе ния в распределенных системах а - неупорядоче нная группа процессов в сети ; б - логическ ое кольцо , образованное программным обеспечением Неделимые транзак ции Все средства синхронизации , которые были рассмотрены ране е , относятся к нижнему уровню , например , се мафоры . Они требуют от программиста детальног о знания алгоритмов взаимного исключения , упр авления критическими секциями , умения предотвраща ть клинчи (взаимные б локировки ), а также владения средствами восстановления после краха . Однако существуют средства синхрониза ции более высокого уровня , которые освобождаю т программиста от необходимости вникать во все эти подробности и позволяют ему ск онцентрировать свое вним а ние на л огике алгоритмов и организации параллельных в ычислений . Таким средством является неделимая транзакция . Модель неделимой транзакции пришла из бизнеса . Представьте себе переговорный процесс двух фирм о продаже-покупке некоторого то вара . В процессе п ереговоров условия д оговора могут многократно меняться , уточняться . Пока договор еще не подписан обеими ст оронами , каждая из них может от него о тказаться . Но после подписания контракта сдел ка (transaction) должна быть выполнена . Компьютерная транзакция по лностью ана логична . Один процесс объявляет , что он хо чет начать транзакцию с одним или более процессами . Они могут некоторое время созда вать и уничтожать разные объекты , выполнять какие-либо операции . Затем инициатор объявляет , что он хочет завершить тран з акцию . Если все с ним соглашаются , то р езультат фиксируется . Если один или более процессов отказываются (или они потерпели кра х еще до выработки согласия ), тогда измене нные объекты возвращается точно к тому со стоянию , в котором они находились до начал а вы п олнения транзакции . Такое сво йство "все-или-ничего " облегчает работу программист а . Для программирования с использованием тра нзакций требуется некоторый набор примитивов , которые должны быть предоставлены программисту либо операционной системой , либо языко м программирования . Примеры примитивов такого рода : BEGIN_TRANSACTION команды , которые следуют за этим примитивом , формируют транзакцию . END_TRANSACTION завершает транзакцию и пытается заф иксировать ее . ABORT_TRANSACTION прерывает транзакцию , во сстанавливае т предыдущие значения . READ читает данные из файла (или друг ого объекта ) WRITE пишет данные в файл (или другой объект ). Первые два примитива используются для определения границ транзакции . Операции между ними представляют собой тело т ранзакции . Либо все они должны быть выполнены , либо ни одна из них . Это может быть системный вызов , библиотечная проц едура или группа операторов языка программиро вания , заключенная в скобки . Транзакции обладают следующими свойствами : упорядочиваемостью , н еделимостью , постоянством . Упорядочиваемость гара нтирует , что если две или более транзакции выполняются в одно и то же время , то конечный результат выглядит так , как е сли бы все транзакции выполнялись последовате льно в некотором (в зависимости от системы ) порядке . Неделимость означает , что когда транзакция находится в процесс е выполнения , то никакой другой процесс не видит ее промежуточные результаты . Постоянство означает , что после фиксации транзакции никакой сб ой не может отменить результатов ее выпол н ения . Если программное обеспечение гарантирует вышеперечисленные свойства , то это означает , ч то в системе поддерживается механизм транзакц ий . Рассмотрим некоторые подходы к реализации механизма транзакций . В соответствии с первым подходом , когд а процесс начинает транзакцию , то он работает в индивидуальном рабочем пространстве , содержащем все файлы и другие объекты , к которым он имеет доступ . Пока транзак ция не зафиксируется или не прервется , все изменения данных происходят в этом рабоч ем пространстве , а не в "реальном ", под которым мы понимаем обычную файловую систему . Главная проблема этого подхода с остоит в больших накладных расходах по ко пированию большого объема данных в индивидуал ьное рабочее пространство , хотя и имеются несколько приемов уменьшения этих рас ходов . Второй общий подход к реализации меха низма транзакций называется списком намерений . Этот метод заключается в том , что модиф ицируются сами файлы , а не их копии , но перед изменением любого блока производится запись в специальный файл - журнал р егистрации , где отмечается , какая транзакция д елает изменения , какой файл и блок изменяе тся и каковы старое и новое значения изменяемого блока . Только после успешной запи си в журнал регистрации делаются изменения в исходном файле . Если транзакция фиксир у ется , то и об этом делается запись в журнал регистрации , но старые значения измененных данных сохраняются . Если транзакция прерывается , то информация журнала регистрации используется для приведения файла в исходное состояние , и это действие на зывается отк а том . В распределенных системах фиксация транза кций может потребовать взаимодействия нескольких процессов на разных машинах , каждая из которых хранит некоторые переменные , файлы , базы данных . Для достижения свойства неделимо сти транзакций в распределенных системах используется специальный протокол , называемый п ротоколом двухфазной фиксации транзакций . Хотя он и не является единственным протоколом такого рода , но он наиболее широко испо льзуется . Суть этого протокола состоит в следую щем . Один из процессов вы полняет функц ии координатора (рисунок 3.8). Координатор начинает транзакцию , делая запись об этом в свое м журнале регистрации , затем он посылает в сем подчиненным процессам , также выполняющим эту транзакцию , сообщение "подготовиться к фик сации ". Когда подч и ненные процессы получают это сообщение , то они проверяют , готовы ли они к фиксации , делают запись в своем журнале и посылают координатору сообщение-ответ "готов к фиксации ". После это го подчиненные процессы остаются в состоянии готовности и ждут от коорди н атора команду фиксации . Если хотя бы один из подчиненных процессов не откликнулся , то координатор откатывает подчиненные транзакции , включая и те , которые подготовились к фиксации . Выполнение второй фазы заключается в том , что координатор посылает команду "фи ксировать " (commit) всем подчиненным процессам . Выполняя эту команду , последние фиксируют изменения и завершают подчиненные транзакции . В резул ьтате гарантируется одновременное синхронное зав ершение (удачное или неудачное ) распределенной транзакции . Рис . 3.8. Двухфазный протокол фиксац ии транзакции
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Видеоигра Pok?mon GO признана самым эффективным средством нетрадиционной контрацепции сезона 2016.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Синхронизация в распределенных системах", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru