Синхронизация. Физические часы. Алгоритмы синхронизацации времени, алгоритм Кристина. Алгоритм Беркли

Стратегии борьбы.

Условия возникновения

Дедлок. Условия возникновения. Стратегии борьбы.

Взаи́мная блокиро́вка (англ. deadlock) — ситуация в многозадачной среде или СУБД, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами.

1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (которые при этом обычно удерживаются другими процессами).

3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи.

1. Предотвратить

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

o Неограниченное выделение ресрсов

o Предварительное выделение ресурсов

o Перераспределение ресурсов (вариант Иерархическое выделение ресурсов)

Вариант решения- алгоритм Банкира:

1. Банкиру поступает запрос от клиента на получение кредита

2. Банкир проверяет, приводит ли этот запрос к небезопасному состоянию.

3. Банкир в зависимости от этого дает или отказывает в кредите.

2. Обойти

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

3. Распознать ситуацию

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

Синхронизация процессов — приведение двух или нескольких процессов к такому их протеканию, когда определённые стадии разных процессов совершаются в определённом порядке, либо одновременно.

Измерение времени основано на циклических изменениях: cмена темного периода и светлого, вращение земли вокруг солнца. Периодичность смены темного периода и светлого - это день (оборот земли вокруг оси), один оборот вокруг солнца - это год.

Физические часы – солнечные, водяные, механические, электронные и тд

Алгоритмы синхронизации часов
При функционировании системы желательно, чтобы локальное время отдельного ПК соответствовало физическому времени. Необходимо синхронизировать локальные часы, соблюдая порядок событий. При синхронизации часов существуют две проблемы:

1. Часы нельзя перевести назад, это может нарушить последовательность событий.
   Надо замедлять часы, увеличив период приращения значения времени (например, с 10 до 11 мс).
2. Ненулевое время прохождения сообщения
   Надо многократно замерять время прохождения сообщений с показаниями часов и выбрать минимальное.

Алгоритм Кристиана. Периодически каждый узел посылает эталонному запрос его текущего времени. Эталонный узел максимально быстро отвечает на этот запрос. Но следует помнить, что между отправкой сообщения эталоном и его получением узлом проходит некоторое время, которое непостоянно и зависит от текущей загрузки сети передачи данных. Для оценки этого времени Кристиан предложил принимать время передачи ответа как половину времени между отправкой запроса и получением ответа. Для повышения точности следует производить серию таких замеров.

Достоинства: простота реализации, высокая эффективность в небольших сетях и сетях с малой загрузкой: поскольку в системе присутствует источник точного времени и синхронизация производится по нему, то время в системе в целом соответствует реальному.

Недостатки: требует внешнего источника точного времени, не имеет встроенной защиты от перевода часов в обратную сторону, некорректно работает в сетях с резкими скачками загрузки сети, не позволяет корректно устанавливать время в случае, если запрос и ответ передаются по разным маршрутам (требуется разное время для передачи данных сообщений).

Для случая, когда такой источник времени отсутствует:

Алгоритм Беркли. Данный алгоритм предназначен для случая, когда источник точного времени отсутствует. Сервер времени опрашивает все узлы для выяснения их текущего времени, усредняет это значение и рассылает команды на установку нового значения времени либо замедление часов.

Достоинства: простота реализации, высокая эффективность для систем, некритичных к отклонениям по времени.

Недостатки: требуется выделенный узел –сервер времени, поскольку источник точного времени отсутствует, а за общесистемное время принимается усредненное время узлов, оно может иметь мало общего с реальным временем, узлы с замедленным для коррекции временем (все еще некорректным) оказывают влияние на общесистемное время.

Дата добавления: 2015-04-23