Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Необходимость синхронизации [ править ]

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

Разветвления и соединения : когда задание достигает точки развилки, оно разбивается на N подзадач, которые затем обслуживаются n задачами. После обслуживания каждое подзадание ожидает завершения обработки всех остальных подзадач. Затем они снова присоединяются и покидают систему. Таким образом, параллельное программирование требует синхронизации, поскольку все параллельные процессы ожидают выполнения нескольких других процессов.

Производитель-Потребитель: в отношениях производитель-потребитель, процесс потребителя зависит от процесса производителя до тех пор, пока не будут произведены необходимые данные.

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

Синхронизация потоков или процессов [ править ]

Рисунок 1. Три процесса одновременно обращаются к общему ресурсу ( критическому разделу ).

Синхронизация потоков определяется как механизм, который гарантирует, что два или более параллельных процесса или потоков не будут одновременно выполнять какой-либо конкретный сегмент программы, известный как критический раздел . Доступ процессов к критическому участку контролируется с помощью методов синхронизации. Когда один поток начинает выполнение критического раздела (сериализованного сегмента программы), другой поток должен дождаться завершения первого потока. Если надлежащие методы синхронизации [1] не применяются, это может вызвать состояние гонки, когда значения переменных могут быть непредсказуемыми и изменяться в зависимости от времени переключения контекста процессов или потоков.

Например, предположим, что существует три процесса, а именно 1, 2 и 3. Все три из них выполняются одновременно, и им необходимо совместно использовать общий ресурс (критический раздел), как показано на рисунке 1. Здесь следует использовать синхронизацию, чтобы избегайте любых конфликтов при доступе к этому общему ресурсу. Следовательно, когда процессы 1 и 2 оба пытаются получить доступ к этому ресурсу, он должен быть назначен только одному процессу за раз. Если он назначен процессу 1, другой процесс (процесс 2) должен дождаться, пока процесс 1 освободит этот ресурс (как показано на рисунке 2).

Рисунок 2 : Процесс доступа к общему ресурсу, если он доступен, на основе некоторой техники синхронизации.

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

Помимо взаимного исключения, синхронизация также касается следующего:

  • тупик , который возникает, когда многие процессы ожидают общий ресурс (критический раздел), который удерживается каким-то другим процессом. В этом случае процессы просто ждут и больше не выполняются;
  • голодание , которое происходит, когда процесс ожидает входа в критическую секцию, но другие процессы монополизируют критическую секцию, и первый процесс вынужден ждать бесконечно;
  • инверсия приоритета , которая происходит, когда процесс с высоким приоритетом находится в критической секции, и прерывается процессом со средним приоритетом. Это нарушение правил приоритета может произойти при определенных обстоятельствах и может привести к серьезным последствиям в системах реального времени;
  • ожидание занятости , которое происходит, когда процесс часто опрашивает, чтобы определить, есть ли у него доступ к критическому разделу. Этот частый опрос отнимает время обработки у других процессов.

Минимизация синхронизации [ править ]

Одна из проблем при разработке алгоритма эксафлопсного масштабирования - минимизировать или уменьшить синхронизацию. Синхронизация занимает больше времени, чем вычисления, особенно в распределенных вычислениях. Снижение синхронизации привлекало внимание компьютерных ученых на протяжении десятилетий. Принимая во внимание, что в последнее время это становится все более серьезной проблемой, поскольку разрыв между улучшением вычислений и задержкой увеличивается. Эксперименты показали, что (глобальные) коммуникации из-за синхронизации на распределенных компьютерах занимают доминирующую долю в разреженном итеративном решателе. [2] Эта проблема привлекает все большее внимание после появления нового эталонного показателя, High Performance Conjugate Gradient (HPCG), [3] для ранжирования 500 лучших суперкомпьютеров.

Классические проблемы синхронизации [ править ]

Вот некоторые классические проблемы синхронизации:

  • Проблема производителя-потребителя (также называемая проблемой ограниченного буфера);
  • Проблема читателей-писателей ;
  • Проблема обедающих философов .

Эти задачи используются для тестирования почти каждой вновь предложенной схемы или примитива синхронизации.

Аппаратная синхронизация [ править ]

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

Однопроцессорная или однопроцессорная система может отключать прерывания , выполняя текущий код без прерывания , что очень неэффективно в многопроцессорных системах. [4]«Ключевая способность, которая нам требуется для реализации синхронизации в многопроцессоре, - это набор аппаратных примитивов с возможностью атомарного чтения и изменения области памяти. Без такой возможности стоимость создания базовых примитивов синхронизации будет слишком высока и будет увеличиваться по мере того, как количество процессоров увеличивается. Существует ряд альтернативных формулировок основных аппаратных примитивов, каждый из которых обеспечивает возможность атомарного чтения и изменения местоположения, вместе с некоторым способом определить, выполнялись ли чтение и запись атомарно. Эти аппаратные примитивы являются основными строительными блоками, которые используются для создания широкого спектра операций синхронизации на уровне пользователя, включая такие вещи, как блокировки и барьеры.. В общем, архитекторы не ожидают, что пользователи будут использовать базовые аппаратные примитивы, но вместо этого ожидают, что эти примитивы будут использоваться системными программистами для создания библиотеки синхронизации, процесс, который часто бывает сложным и запутанным ». [5] Многие современные аппаратные средства предоставляют специальные атомарные аппаратные инструкции путем либо проверки и установки слова памяти, либо сравнения и замены содержимого двух слов памяти.

Стратегии синхронизации в языках программирования [ править ]

В Java , чтобы предотвратить вмешательство потоков и ошибки согласованности памяти, блоки кода помещаются в синхронизированные (lock_object) секции. Это заставляет любой поток получить указанный объект блокировки, прежде чем он сможет выполнить блок. Блокировка автоматически снимается, когда поток, который получил блокировку и затем выполняет блок, покидает блок или входит в состояние ожидания внутри блока. Любые обновления переменных, сделанные потоком в синхронизированном блоке, становятся видимыми для других потоков, когда они аналогичным образом получают блокировку и выполняют блок.

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

Любой объект может использоваться в качестве замка / монитора в Java. Объявляемый объект является объектом блокировки, когда весь метод помечен как synchronized .

В .NET Framework есть примитивы синхронизации. «Синхронизация предназначена для взаимодействия, требуя, чтобы каждый поток или процесс следовал механизму синхронизации перед доступом к защищенным ресурсам (критический раздел) для получения согласованных результатов». В .NET блокировка, сигнализация, облегченные типы синхронизации, спин-ожидание и операции блокировки - это лишь некоторые из механизмов, связанных с синхронизацией. [6]

Реализация синхронизации [ править ]

Spinlock [ править ]

Основная статья: Spinlock

Другой эффективный способ реализации синхронизации - использование спин-блокировок. Перед доступом к какому-либо общему ресурсу или фрагменту кода каждый процессор проверяет флаг. Если флаг сброшен, процессор устанавливает флаг и продолжает выполнение потока. Но если флаг установлен (заблокирован), потоки будут продолжать вращаться в цикле и проверять, установлен ли флаг или нет. Но спин-блокировки эффективны только в том случае, если флаг сброшен для более низких циклов, иначе это может привести к проблемам с производительностью, поскольку тратит много циклов процессора на ожидание. [7]

Барьеры [ править ]

Основная статья: Барьер (информатика)

Барьеры просты в использовании и обеспечивают хорошую отзывчивость. Они основаны на концепции реализации циклов ожидания для обеспечения синхронизации. Рассмотрим три потока, работающих одновременно, начиная с барьера 1. По истечении времени t поток 1 достигает барьера 2, но ему все еще приходится ждать, пока потоки 2 и 3 достигнут барьера 2, поскольку у него нет правильных данных. Как только все потоки достигают барьера 2, все они запускаются снова. По истечении времени t поток 1 достигает барьера 3, но ему придется снова ждать потоков 2 и 3 и правильных данных.

Таким образом, при барьерной синхронизации нескольких потоков всегда будет несколько потоков, которые в конечном итоге будут ждать других потоков, как в приведенном выше примере поток 1 продолжает ожидать потоки 2 и 3. Это приводит к серьезному снижению производительности процесса. [8]

Функция ожидания синхронизации барьера для i- го потока может быть представлена ​​как:

(Wbarrier) i = f ((Tbarrier) i, (Rthread) i)

Где Wbarrier - это время ожидания потока, Tbarrier - это количество прибывших потоков, а Rthread - это скорость поступления потоков. [9]

Эксперименты показывают, что 34% общего времени выполнения тратится на ожидание других более медленных потоков. [8]

Семафоры [ править ]

Основная статья: Семафор (программирование)

Семафоры - это механизмы сигнализации, которые могут позволить одному или нескольким потокам / процессорам получить доступ к разделу. Семафор имеет флаг, с которым связано определенное фиксированное значение, и каждый раз, когда поток хочет получить доступ к секции, он уменьшает флаг. Точно так же, когда поток покидает раздел, флаг увеличивается. Если флаг равен нулю, поток не может получить доступ к разделу и блокируется, если он решает подождать.

Некоторые семафоры допускают только один поток или процесс в разделе кода. Такие семафоры называются двоичными семафорами и очень похожи на Mutex. Здесь, если значение семафора равно 1, потоку разрешен доступ, а если значение равно 0, доступ запрещен. [10]

Математические основы [ править ]

Первоначально синхронизация была концепцией, основанной на процессах, посредством которой на объекте могла быть получена блокировка. Его основное использование было в базах данных. Есть два типа (файловой) блокировки ; только для чтения и чтения-записи. Блокировки только для чтения могут быть получены многими процессами или потоками. Блокировки чтения-записи являются исключительными, так как они могут использоваться только одним процессом / потоком одновременно.

Хотя блокировки были получены для файловых баз данных, данные также распределяются в памяти между процессами и потоками. Иногда одновременно блокируется более одного объекта (или файла). Если они не заблокированы одновременно, они могут перекрываться, вызывая исключение взаимоблокировки.

Java и Ada имеют только монопольные блокировки, потому что они основаны на потоках и полагаются на инструкции процессора сравнения и замены .

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

Примеры синхронизации [ править ]

Ниже приведены некоторые примеры синхронизации для разных платформ. [11]

Синхронизация в Windows [ править ]

Windows обеспечивает:

  • маски прерываний , защищающие доступ к глобальным ресурсам (критическому разделу) на однопроцессорных системах;
  • спин-блокировки , которые предотвращают вытеснение потока спин-блокировки в многопроцессорных системах;
  • диспетчеры , которые действуют как мьютексы , семафоры , события и таймеры .

Синхронизация в Linux [ править ]

Linux предоставляет:

  • семафоры ;
  • спин-блокировка ;
  • барьеры
  • мьютекс
  • Блокировки читателей и писателей для более длинных разделов кодов, которые используются очень часто, но не меняются очень часто.
  • Чтение-копирование-обновление (RCU) [12]

Включение и отключение вытеснения ядра заменили спин-блокировки в однопроцессорных системах. До версии ядра 2.6 Linux отключал прерывание для реализации коротких критических секций. Начиная с версии 2.6 и новее, Linux полностью вытеснен.

Синхронизация в Solaris [ править ]

Solaris предоставляет:

  • семафоры ;
  • переменные состояния ;
  • адаптивные мьютексы , двоичные семафоры, которые реализуются по-разному в зависимости от условий;
  • читатель-писатель замки:
  • турникеты , очередь потоков, ожидающих получения блокировки. [13]

Синхронизация потоков [ править ]

Pthreads - это платформенно-независимый API, который обеспечивает:

  • мьютексы;
  • переменные состояния;
  • читательско-писательские замки;
  • спин-блокировки;
  • барьеры .

Синхронизация данных [ править ]

Основная статья: Синхронизация данных
Рисунок 3: Изменения как от сервера, так и от клиента (ов) синхронизируются.

Совершенно другая (но связанная) концепция - это синхронизация данных . Это относится к необходимости поддерживать согласованность нескольких копий набора данных друг с другом или поддерживать целостность данных , рис. 3. Например, репликация базы данных используется для синхронизации нескольких копий данных с серверами баз данных, которые хранят данные в разных местах. .

Примеры включают:

  • Синхронизация файлов , такая как синхронизация портативного MP3-плеера с настольным компьютером;
  • Кластерные файловые системы , которые представляют собой файловые системы, которые поддерживают данные или индексы согласованным образом во всем вычислительном кластере ;
  • Согласованность кеширования , поддержание синхронизации нескольких копий данных в нескольких кэшах ;
  • RAID , где данные записываются с избыточностью на несколько дисков, так что потеря одного диска не приводит к потере данных;
  • Репликация базы данных , при которой копии данных в базе данных хранятся в синхронизации, несмотря на возможное большое географическое разделение;
  • Ведение журнала - метод, используемый многими современными файловыми системами для обеспечения согласованного и согласованного обновления метаданных файлов на диске.

Проблемы с синхронизацией данных [ править ]

Некоторые из проблем, с которыми может столкнуться пользователь при синхронизации данных:

  • сложность форматов данных;
  • оперативность;
  • безопасность данных;
  • Качество данных;
  • представление.

Сложность форматов данных [ править ]

Форматы данных имеют тенденцию становиться более сложными со временем по мере роста и развития организации. Это приводит не только к созданию простых интерфейсов между двумя приложениями (исходным и целевым), но и к необходимости преобразовывать данные при их передаче в целевое приложение. Инструменты ETL (загрузка с преобразованием извлечения) могут быть полезны на этом этапе для управления сложностями формата данных.

Оперативность [ править ]

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

Безопасность данных [ править ]

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

Качество данных [ править ]

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

Производительность [ править ]

Процесс синхронизации данных состоит из пяти различных этапов:

  • извлечение данных из исходной (или главной, или основной) системы;
  • передача данных ;
  • преобразование данных ;
  • загрузка данных в целевую систему.
  • обновление данных

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

См. Также [ править ]

  • Будущее и обещание , механизмы синхронизации в чисто функциональных парадигмах

Ссылки [ править ]

  1. ^ Gramoli, В. (2015). Больше, чем вы когда-либо хотели знать о синхронизации: Synchrobench, измеряющий влияние синхронизации на параллельные алгоритмы (PDF) . Материалы 20-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования. ACM. С. 1–10.
  2. ^ Shengxin, Чжу и Тунсян Гу и Xingping Лю (2014). «Минимизация синхронизации в разреженных итерационных решателях для распределенных суперкомпьютеров» . Компьютеры и математика с приложениями . 67 (1): 199–209. DOI : 10.1016 / j.camwa.2013.11.008 .
  3. ^ «Тест HPCG» .
  4. ^ Зильбершац, Авраам; Гань, Грег; Гэлвин, Питер Баер (11 июля 2008 г.). «Глава 6: Синхронизация процессов». Концепции операционной системы (Восьмое изд.). Джон Вили и сыновья. ISBN 978-0-470-12872-5.
  5. ^ Хеннесси, Джон Л .; Паттерсон, Дэвид А. (30 сентября 2011 г.). «Глава 5: Параллелизм на уровне потоков». Компьютерная архитектура: количественный подход (пятое изд.). Морган Кауфманн. ISBN 978-0-123-83872-8.
  6. ^ «Синхронизация примитивов в .NET framework» . MSDN, Сеть разработчиков Microsoft . Microsoft . Проверено 23 ноября 2014 года .
  7. ^ Масса, Энтони (2003). Разработка встроенного программного обеспечения с ECos . ISBN Pearson Education Inc. 0-13-035473-2.
  8. ^ а б Мэн, Чен, Пан, Яо, Ву, Джинглей, Тяньчжоу, Пин, Цзюнь Минхуэй (2014). «Спекулятивный механизм барьерной синхронизации». Международная конференция IEEE 2014 г. по высокопроизводительным вычислениям и коммуникациям (HPCC), 6-й Международный симпозиум IEEE 2014 г. по безопасности и защите киберпространства (CSS) и 11-я Международная конференция IEEE 2014 г. по встроенному программному обеспечению и системам (ICESS) .CS1 maint: несколько имен: список авторов ( ссылка )
  9. ^ Рахман, Мохаммед Махмудур (2012). «Синхронизация процессов в многопроцессорных и многоядерных процессорах». 2012 Международная конференция по информатике, электронике и зрению (ICIEV) . С. 554–559. DOI : 10,1109 / ICIEV.2012.6317471 . ISBN 978-1-4673-1154-0.
  10. ^ Ли, Яо, Цин, Кэролайн (2003). Концепции реального времени для встроенных систем . Книги CMP. ISBN 978-1578201242.
  11. ^ Зильбершац, Авраам; Гань, Грег; Гэлвин, Питер Баер (7 декабря 2012 г.). «Глава 5: Синхронизация процессов». Концепции операционной системы (Девятое изд.). Джон Вили и сыновья. ISBN 978-1-118-06333-0.
  12. ^ «Что такое RCU, по сути? [LWN.net]» . lwn.net .
  13. ↑ Мауро, Джим. «Турникеты и наследование приоритета - SunWorld - август 1999» . sunsite.uakom.sk .
  • Шнайдер, Фред Б. (1997). О параллельном программировании . ISBN компании Springer-Verlag New York, Inc. 978-0-387-94942-0.

Внешние ссылки [ править ]

  • Анатомия методов синхронизации Linux на IBM developerWorks
  • Маленькая книга семафоров , Аллен Б. Дауни
  • Необходимость синхронизации процессов