Лычев А.В. Распределенные автоматизированные системы

Подождите немного. Документ загружается.

Распределенные автоматизированные системы

150

достигнет листового домена, содержащего запрашиваемую сущ-

ность. Адрес, содержащийся в локализующей записи направляю-

щего узла листового домена запрашиваемой сущности, возвра-

щается клиенту, инициировавшему поиск.

При перемещении сущности на другой листовой домен, на-

правляющий узел этого домена посылает своему родительскому

узлу сообщение о появлении в домене новой сущности. Если на

родительском узле идентификатор этой сущности отсутствует,

он пересылает данное сообщение вверх на следующий уровень.

Сообщение о появлении в домене новой сущности пересы-

лается вверх по уровням с узла на узел до тех пор, пока на

очередном направляющем узле не обнаружится идентификатор

перемещенной сущности. Направляющий узел, получив сообщение

о появлении в домене новой сущности, идентификатор которой

на нем уже присутствует, изменяет значение локализующей за-

писи этой сущности на новое и инициирует удаление идентифи-

каторов перемещенной сущности по всей цепочке дочерних уз-

лов вплоть до листового домена, на котором ранее находилась

эта сущность.

Иерархическая служба локализации затрудняет масштаби-

руемость сети вследствие необходимости хранения и обработки

большого количества идентификаторов на корневом направляю-

щем узле.

§ 3. Удаление сущностей, на которые нет ссылок

Если в распределенной системе имеются сущности, на ко-

торые отсутствуют ссылки, или несколько сущностей, взаимно

ссылающихся друг на друга, то они непроизводительно занима-

ют ресурсы системы и по этой причине подлежат удалению. В

локальных ЭВМ критерий возможности удаления сущности осно-

ван на подсчете ссылок на эту сущность.

При создании ссылки на сущность организуется счетчик

ссылок, который увеличивается на единицу при создании каж-

дой новой ссылки на одну и ту же сущность. При уничтожении

каждой ссылки на сущность соответствующий ей счетчик ссылок

уменьшается на единицу. При обнулении счетчика ссылок соот-

ветствующая ему сущность удаляется.

В распределенных системах простой подсчет ссылок при-

водит к проблемам при потерях удаленных ссылок или подтвер-

ждений об изменении состояния счетчика ссылок. Потери вы-

званы низкой надежностью каналов связи. Для решения проблем

при подсчете ссылок в распределенных системах применяют

следующие методы:

1. Взвешенный подсчет ссылок. Каждой вновь создаваемой

сущности присваивается определенный вес (как правило, это

число, равное целой степени числа два). При создании уда-

Распределенные автоматизированные системы

151

ленной ссылки ей присваивается половина веса соответствую-

щей сущности, а вес сущности уменьшается вдвое. При копиро-

вании ссылки вес копируемой ссылки уменьшается вдвое, а ко-

пии присваивается половина начального веса копируемой ссыл-

ки. При создании ссылки на ссылку также вес ссылки, на ко-

торую ссылаются, уменьшается вдвое, а новой ссылке присваи-

вается половина начального веса ссылки, на которую ссылают-

ся. Пример:

Необходимо заметить, что при взвешенном подсчете ссы-

лок сумма весов ссылок равна весу сущности.

При уничтожении ссылки сущности посылается сообщение,

уменьшающее значение её веса на значение веса удаляемой

ссылки. Как только вес сущности становится равным нулю, она

удаляется. Ввиду того, что счетчик веса работает только на

уменьшение, ситуация, когда сущность будет уничтожена при

наличии ссылок на неё, возникнуть не может;

2. Подсчет поколений ссылок. Для каждой ссылки созда-

ется два счетчика – счетчик копий ссылок и счетчик поколе-

ний ссылок. Эти счетчики сводятся в таблицу ссылок, храня-

щуюся на сущности. При создании непосредственной ссылки на

сущность, номер поколения в соответствующем ей счетчике

становится равным единице. При создании копии ссылки, счет-

чик копий скопированной ссылки увеличивается на единицу, а

счетчик поколения копии ссылки увеличивается на единицу от-

носительно скопированной ссылки. При создании ссылки на

ссылку счетчик поколения новой ссылки устанавливается на

единицу большим значения счетчика поколения ссылки, на ко-

торую ссылаются, а счетчик копий обнуляется. В таблице ссы-

лок ведется сквозной подсчет общего числа поколений ссылок

и их копий. При удалении ссылки из таблицы ссылок удаляются

все сведения об удаляемой ссылке. Как только сквозная сумма

общего числа поколений ссылок и их копий становится равной

нулю, сущность уничтожается Пример: В этом примере К – те-

кущее значение счетчика копий ссылок, П – текущее значение

Распределенные автоматизированные системы

152

счетчика поколений ссылок, n – максимальное количество ко-

пий ссылок, m – максимальное количество поколений ссылок;

3. Создание списка ссылок. На сущности создается пол-

ный список ссылок на сущность со следующими идемпотентными

свойствами:

а) Добавление в список ссылки невозможно, если такая

ссылка в списке уже существует;

б) Попытка удаления ссылки, отсутствующей в списке, ни

к чему не приводит.

Достоинство метода – простота сохранения непротиворе-

чивости ссылок при сбоях процессов. Недостаток метода –

плохая масштабируемость системы.

§ 4. Файловые системы ОС РВ QNX

Одной из важнейших точек приложения служб разрешения

имен являются файловые системы. Файловые системы в операци-

онной системе реального масштаба времени реализуют процес-

сы, называемые администраторами ресурсов. Как и все процес-

сы, администраторы ресурсов, реализующие файловые системы,

работают вне микроядра. Прикладные программы используют

файловые системы посредством механизма обмена сообщениями,

которые генерируются с помощью программного интерфейса

POSIX. Каждая файловая система получает свою область в про-

странстве имен, называемую точкой монтирования, и предос-

тавляет свои службы также посредством стандартного про-

граммного интерфейса POSIX. Администраторы ресурсов файло-

вой системы получают точку монтирования и управляют струк-

турой каталогов ниже этой точки. Администраторы ресурсов

также осуществляют проверку прав доступа к файлам. Преиму-

щества управления файловыми системами с помощью администра-

торов ресурсов:

1. Файловые системы можно запускать и останавливать

динамически без перезагрузки системы;

Распределенные автоматизированные системы

153

2. Множество файловых систем могут работать одновре-

менно;

3. Прикладные программы используют одно общее про-

странство имен и единый интерфейс независимо от конфигура-

ции и количества применяемых файловых систем;

4. Обеспечивается прозрачность доступа и местоположе-

ния.

Файловые системы подразделяются на пять классов:

1. Образная файловая система. Специальная файловая

система, которая существует в любой системе и содержит про-

граммные модули, включенные в состав загрузочного образа.

Администратор процессов автоматически преобразует образную

файловую систему в файловую систему в оперативной памяти;

2. Блочная файловая система. Традиционная файловая

система, работающая с блочными устройствами типа жестких

дисков и приводов компакт-дисков. К этому классу относятся

файловые системы QNX4, DOS, CDFS;

3. Файловая система во флэш-памяти. Эта файловая сис-

тема предназначена для устройств с флэш-памятью. К этому

классу относятся файловые системы FFS3, ETFS;

4. Сетевая файловая система. Данная файловая система

предоставляет сетевой доступ к файловым системам, находя-

щимся на удаленных ЭВМ. К этому классу относятся файловые

системы NFS, CIFS (SMB);

5. Виртуальная файловая система. Бывает двух видов:

а) Пакетная файловая система. Этот вид виртуальной

файловой системы отображает клиенту выбранные файлы и ката-

логи в заданном пользователем представлении;

б) Распаковщик. Распаковщик – это менеджер ресурсов,

выполняющий распаковку сжатых файлов для нужд других файло-

вых систем.

Операционная система реального масштаба времени QNX

поддерживает следующие виды файловых систем:

1. Образная файловая система;

2. Файловая система в ОЗУ. Эта файловая система приме-

няется в миниатюрных встраиваемых системах, где не требуют-

ся постоянные запоминающие устройства, а необходима ком-

пактная быстродействующая файловая система с минимальными

функциональными возможностями для временного хранения дан-

ных. В этой файловой системе нельзя создавать каталоги

(папки) и задавать свойства файлов;

3. Файловая система ETFS (Embedded Transaction File

System – встраиваемая транзакционная файловая система). Вы-

соконадежная файловая система, предназначенная для постоян-

ных перезаписываемых запоминающих устройств с полупроводни-

ковой памятью. Файловая система ETFS основана на механизме

транзакций. Каждая операция записи является транзакцией.

Распределенные автоматизированные системы

154

Если в момент выполнения операции случится какой-либо сбой,

старые данные останутся в сохранности. Отказоустойчивость

файловой системы ETFS обеспечивается благодаря реализации

следующих функций:

а) Выравнивание динамического износа. Каждый блок

флэш-памяти допускает ограниченное количество безотказных

циклов стирания, которое, как правило, не превышает 100 ты-

сяч. Файловая система ETFS ведет подсчет количества стира-

ний по каждому блоку памяти для учета их износа при исполь-

зовании и равномерного распределения нагрузки между блока-

ми. Без выравнивания динамического износа среднее время на-

работки флэш-накопителя на отказ составляет десять дней, а

при использовании выравнивания – сорок лет;

б) Выравнивание статического износа. Накопители часто

содержат статичные файлы, используемые только для чтения

(например: файлы программ). При этом остальные блоки флэш-

памяти, в которых хранятся периодически изменяющиеся дан-

ные, будут изнашиваться значительно быстрее блоков, храня-

щих информацию только для чтения. Файловая система ETFS от-

слеживает статичные блоки с низким износом и периодически

перемещает в них динамически изменяемые данные, а информа-

цию только для чтения – на место, где ранее находились ди-

намически изменяемые данные;

в) Выявление ошибок с помощью циклического контрольно-

го кода;

г) Исправление одиночных ошибок с помощью кода Хэммин-

га;

д) Контроль количества операций чтения и автоматиче-

ское обновление. Большинство флэш-накопителей допускают не

более 100 тысяч гарантированных операций чтения подряд, без

обновления данных. Файловая система ETFS производит подсчет

последовательных операций чтения подряд для каждого блока и

до достижения 100 тысяч чтений автоматически обновляет дан-

ные в блоке памяти;

е) Откат транзакций. При запуске или перезагрузке фай-

ловой системы ETFS, она обрабатывает все транзакции и отме-

няет последние начавшиеся перед остановом или перезагрузкой

частично выполненные или неуспешные транзакции. Операция

отката сама является транзакцией, поэтому даже в случае

возникновения сбоя при её выполнении, она будет повторена

после вторичной перезагрузки. Это позволяет системе восста-

навливаться даже после множественных последовательных сбо-

ев;

ж) Атомарные операции с файлами. В отличие от других

файловых систем, где перемещение файла из одного каталога в

другой представляет собой многоэтапную операцию, в файловой

Распределенные автоматизированные системы

155

системе ETFS такое перемещение осуществляется посредством

одной единственной операции записи;

з) Автоматическая дефрагментация файлов. Файловая сис-

тема ETFS следит за уровнем фрагментированности каждого

файла и периодически выполняет его дефрагментацию в фоновом

режиме. Для уменьшения фрагментированности файлов также

применяется буферизация операций;

4. Файловая система QNX4. Файловая система QNX4 имеет

чрезвычайно высокую степень отказоустойчивости благодаря

использованию экстент-ориентированной (extent - пространст-

во) схемы распределения блоков на основе битовой карты, а

также благодаря применению специализированных подписей,

обеспечивающих защиту данных от потерь и возможность быст-

рого восстановления;

5. Файловая система DOS (Disk Operating System - дис-

ковая операционная система). Использование этой файловой

системы обусловлено исключительно соображениями совместимо-

сти с устаревшей средой DOS и средой Windows. В отличие от

классической файловой системы DOS, в операционной системе

QNX предусмотрено обеспечение прозрачности доступа к DOS-

дискам в соответствии с требованиями стандарта POSIX;

6. Файловая система CDFS (Compact Disc File System -

файловая система для компакт-дисков). Это стандартная фай-

ловая система на компакт-дисках, но, также как и в предыду-

щем случае, в операционной системе QNX предусмотрено обес-

печение прозрачности доступа к компакт-дискам в соответст-

вии с требованиями стандарта POSIX;

7. Файловая система FFS3 (Flash File System – файловая

система для флэш-памяти). Драйверы Файловой системы FFS3

реализуют высоконадежную POSIX-подобную файловую систему на

устройствах с флэш-памятью типа NOR. Механизмы функциониро-

вания файловой системы FFS3 подобны механизмам функциониро-

вания файловой системы ETFS, но, в отличие от последней,

она более проста и компактна;

8. Файловая система NFS (Network File System - сетевая

файловая система). Сетевая файловая система NFS обеспечи-

вает клиентам прозрачный доступ к файлам через сеть, обес-

печивая совместимость со многими современными операционными

системами;

9. Файловая система CIFS (Common Internet File System

- общая межсетевая файловая система). Ранее эта файловая

система называлась SMB (Server Message Block - блок сообще-

ний сервера). Во многих современных операционных системах

последнее название так и сохраняется. Файловая система CIFS

предоставляет клиентам прозрачный сетевой доступ к файлам

на SMB-сервере, работающем под управлением операционных си-

тем Windows или UNIX;

Распределенные автоматизированные системы

156

10. Файловая система Ext2. Это стандартная файловая

система операционной системы Linux, но, также как и в слу-

чаях с файловыми системами DOS и CDFS, в операционной сис-

теме QNX предусмотрено обеспечение прозрачности доступа к

разделам Linux в соответствии с требованиями стандарта

POSIX;

11. Виртуальные файловые системы.

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

Ввиду того, что в распределенных системах процессы од-

ной прикладной программы типа «клиент-сервер», работая на

разных ЭВМ сети, выполняют одну общую задачу, синхронизация

процессов между собой играет ключевую роль.

Все автоматизированные системы управления являются

системами реального масштаба времени. Под системой реально-

го масштаба времени понимается такая система, на время ре-

акции которой на внешние события наложены жесткие ограниче-

ния извне. Системы реального масштаба времени могут быть:

1. Мягкая система реального масштаба времени. Превыше-

ние времени реакции мягкой системы реального масштаба вре-

мени на внешние события сверх установленных пределов приво-

дит к снижению эффективности управления. Примером мягкой

системы реального масштаба времени может служить система

продажи железнодорожных или авиационных билетов. Предел

времени реакции системы на внешнее событие – в данном слу-

чае запрос потенциального пассажира о желании приобрести

билет – ограничивается терпением клиента. Если по какой-

либо причине терпение потенциального пассажира заканчивает-

ся раньше, чем кассир выдает ему билет, происходит снижение

эффективности управления – в данном случае, касса теряет

клиента и лишается доли выручки от непроданного билета;

2. Жесткая система реального времени. Превышение вре-

мени реакции жесткой системы реального масштаба времени на

внешние события сверх установленных пределов приводит к фа-

тальным последствиям. Примером жесткой системы реального

масштаба времени может служить система автоматического

управления самолетом (автопилот). Предел времени реакции

системы на внешние события в данном случае определяется

инерционностью летательного аппарата, когда при незаплани-

рованном изменении каких-либо параметров внешней среды или

самого самолета необходимо предпринять парирующие действия

до того, как самолет начнет незапланированно изменять тра-

екторию полета. Если система управления не успеет отрабо-

тать рулями резкий переход летательного аппарата из плотной

воздушной массы в разреженную до того, как самолет начнет

падать, то он упадет и разобьется.

Распределенные автоматизированные системы

157

Все процессы реального масштаба времени требуют син-

хронизации с текущим временем.

§ 1. Синхронизация с текущим временем

Все современные ЭВМ имеют встроенные процессы для под-

счета текущего времени, называемые системными часами ЭВМ.

Точность измерения времени зависит от конкретных задач, ре-

шаемых системой, а также от инерционности управляемых сис-

темой объектов. Чем менее инерционны объекты управления

системы, тем точнее необходимо измерять текущее время. Од-

нако, некоторые процессы (например, в спутниковой навигации

и связи) требуют синхронизации системных часов с Общемиро-

вым временем.

Еще в семидесятые годы прошлого столетия в качестве

эталона времени принималось Гринвичское время, которое рас-

считывалось астрономическими методами в Гринвичской обсер-

ватории, расположенной на нулевом меридиане (Великобрита-

ния). Однако исследования показали, что неравномерность

движения Земли по своей орбите, вызванная влиянием массив-

ных планет Солнечной системы, не позволяет использовать

Гринвичское время для нужд спутниковой навигации и связи.

Спутник, являясь по отношению к Земле, а тем более к мас-

сивным планетам Солнечной системы, объектом микроскопиче-

ских размеров, практически не испытывает их возмущающих

влияний и движется по своей орбите значительно более равно-

мерно, чем Земля вокруг Солнца. Точность определения коор-

динат с помощью искусственного спутника Земли прямо пропор-

циональна точности измерения времени спутниковой системой

навигации. По этой причине возникла необходимость иметь бо-

лее точное время, чем Гринвичское, в частности, более рав-

номерно текущее, не подверженное астрономическим флуктуаци-

ям.

Вышеуказанная проблема была решена с помощью так назы-

ваемых «атомных» часов, работа которых основывается на под-

счете колебаний атома цезия-133. Одна секунда – это время,

за которое атом цезия-133 совершает 9 192 631 770 колеба-

ний. По всему миру были размещены пятьдесят лабораторий,

оснащенных такими часами. Лаборатории расположены таким об-

разом, чтобы взаимно компенсировать влияние гравитации,

вращения Земли вокруг своей оси и вокруг Солнца на работу

часов. Лаборатории производят подсчет времени с помощью по-

добных «атомных» часов и посылают значение времени в Париж

в Международное бюро Мер и Весов. Международное бюро Мер и

Весов усредняет данные этих пятидесяти лабораторий и выдает

для пользователей значение Общемирового времени. Необходимо

заметить, что из-за замедления вращения Земли вокруг своей

Распределенные автоматизированные системы

158

оси и вокруг Солнца средний солнечный день все время удли-

няется, чего нельзя сказать о периоде колебаний атома це-

зия-133. 86 400 секунд общемирового времени на три миллисе-

кунды меньше среднего солнечного дня. Когда разница между

Общемировым и солнечным временем достигает восьмиста милли-

секунд, Международное бюро Мер и Весов объявляет о добавле-

нии так называемой «потерянной» секунды. В частности, «по-

терянная» секунда была добавлена на рубеже 2005 и 2006 го-

дов.

В большинстве развитых стран мира существуют нацио-

нальные службы точного времени, передающие значение общеми-

рового времени и эталонных частот для национальных потреби-

телей. В совокупности эти службы образуют Всемирную службу

точного времени. В России национальной службой точного вре-

мени и частью Всемирной службы точного времени является Го-

сударственная служба Времени и Частоты (ГСВЧ), передающая

значения точного времени и эталонных частот по сети специа-

лизированных радиостанций, разбросанных по всей территории

России, а также по первому каналу телевизионного вещания,

радиостанциям «Радио России» и «Радио Маяк».

По первому каналу телевизионного вещания информация о

текущем значении времени в двоично-десятичном коде и эта-

лонные сигналы частоты 1 МГц передаются непрерывно в соста-

ве каждой шестой строки телевизионного сигнала в течение 24

кадров.

Через сеть звукового вещания радиостанции «Радио Рос-

сии» и «Радио Маяк» в начале каждого часа передается группа

из шести прямоугольных радиоимпульсов с частотой заполнения

1000 Гц. Первые пять импульсов имеют длительность 100 мил-

лисекунд каждый с интервалом 900 миллисекунд, а длитель-

ность шестого импульса определяется в соответствии с выра-

жением τ = (100 + 20h), где h - целочисленное значение ча-

са. Начало шестого импульса соответствует началу целого ча-

са (00 минут, 00 секунд).

В сети ЭВМ нельзя найти две машины с одинаковым сис-

темным временем. В мире не найдется ЭВМ, системное время

которой точно совпадает с данными Всемирной службы точного

времени.

Синхронизацию системных часов всех ЭВМ распределенной

системы осуществляет служба времени, распределенная по всем

машинам системы. Если одна из ЭВМ системы имеет приемник

сигналов Общемирового времени, то эта машина называется

сервером единого времени. В системах, не критичных к ис-

пользованию Общемирового времени, но работающих в реальном

масштабе времени, также используется сервер единого време-

ни, с той только разницей, что он не имеет приемника сигна-

лов Общемирового времени. Но в любом случае задача службы

Распределенные автоматизированные системы

159

времени состоит в синхронизации системных часов всех ЭВМ

системы с сервером единого времени.

Рассмотрим принцип синхронизации системных часов ЭВМ с

текущим временем. Пусть значение текущего времени на сис-

темных часах сервера единого времени равно t, а значение

времени на системных часах рабочей станции равно C(t).

В идеале C(t) = t, то есть

tdC

)(

= 1.

Реально системные часы рабочей станции либо отстают,

либо спешат, то есть 1 – ρ ≤

tdC

)(

≤ 1 + ρ, где ρ – это мак-

симальная скорость дрейфа. Максимальная скорость дрейфа –

это та величина, про которую мы говорим, произнося фразу,

что «мои часы отстают на две минуты в сутки» или «мои часы

спешат на тридцать секунд в неделю». Максимальную скорость

дрейфа можно определить только экспериментально путем на-

блюдений за системными часами конкретной ЭВМ.

Если два процесса хотят гарантировать синхронность

своей взаимной работы не хуже, чем на время δ, то синхрони-

зация часов этих процессов должна производиться не реже,

чем через каждые

единиц времени. Выбор конкретных еди-

ниц времени (секунд, минут, часов и т.д.) зависит от точно-

сти измерения времени в конкретной системе.

Для синхронизации системных часов рабочей станции с

сервером единого времени используются два алгоритма:

1. Алгоритм Кристиана. Периодически, не реже чем через

каждые

единиц времени, каждая рабочая станция посылает

серверу единого времени запрос о текущем времени. Сервер

так быстро, как это возможно, отвечает сообщением, содержа-

щим значение текущего времени. Алгоритм имеет две проблемы:

а) Если системные часы рабочей станции спешат, то зна-

чение текущего времени, полученное от сервера единого вре-

мени, может оказаться меньшим, чем показания системных ча-

сов рабочей станции в этот момент. Эта ситуация может вы-

звать серьезные отказы в процессах, развивающихся эволюци-

онно во времени (например, процесс счисления пути движуще-

гося объекта). Решение данной проблемы заключается в приве-

дении показаний системных часов рабочей станции в соответ-

ствие текущему времени не скачком, а путем искусственного

замедления работы системных часов ЭВМ;

б) Передача сообщений к серверу единого времени и об-

ратно требует определенного промежутка времени, длитель-

ность которого зависит от текущей загрузки сети. Эту за-

держку можно учесть путем фиксации моментов времени посылки

запроса на сервер единого времени Т

и получения ответа о