Синхронизация (информатика)
 | Эта статья нуждается в дополнительных цитатах для проверки . ( ноябрь 2014 г. ) |
В информатике установления синхронизация — это задача координации нескольких процессов для объединения или связи в определенный момент с целью достижения соглашения или выполнения определенной последовательности действий.
Мотивация
[ редактировать ]Потребность в синхронизации возникает не только в многопроцессорных системах, но и в любых параллельных процессах; даже в однопроцессорных системах. Ниже упомянуты некоторые основные потребности в синхронизации:
Разветвления и соединения . Когда задание достигает точки разветвления, оно разбивается на N подзаданий, которые затем обслуживаются n задачами. После обслуживания каждое подзадание ожидает завершения обработки всех остальных подзаданий. Затем они снова присоединяются и покидают систему. Таким образом, параллельное программирование требует синхронизации, поскольку все параллельные процессы ожидают выполнения нескольких других процессов.
Производитель-потребитель. В отношениях производитель-потребитель процесс-потребитель зависит от процесса-производителя до тех пор, пока не будут получены необходимые данные.
Эксклюзивное использование ресурсов: когда несколько процессов зависят от ресурса и им необходимо получить к нему доступ одновременно, операционная система должна гарантировать, что только один процессор обращается к нему в данный момент времени. Это уменьшает параллелизм.
Требования
[ редактировать ]
Синхронизация потоков определяется как механизм, который гарантирует, что два или более параллельных процесса или потока не выполняют одновременно какой-либо конкретный сегмент программы, известный как критический раздел . Доступ процессов к критической секции контролируется с помощью методов синхронизации. Когда один поток начинает выполнение критического раздела (сериализованного сегмента программы), другой поток должен дождаться завершения первого потока. Если правильные методы синхронизации [1] не применяются, это может вызвать состояние гонки , когда значения переменных могут быть непредсказуемыми и варьироваться в зависимости от времени переключения контекста процессов или потоков.
Например, предположим, что есть три процесса, а именно 1, 2 и 3. Все три из них выполняются одновременно, и им необходимо использовать общий ресурс (критическую секцию), как показано на рисунке 1. Здесь следует использовать синхронизацию, чтобы избегайте любых конфликтов при доступе к этому общему ресурсу. Следовательно, когда процесс 1 и 2 пытаются получить доступ к этому ресурсу, его следует назначить только одному процессу одновременно. Если он назначен Процессу 1, другому процессу (Процессу 2) придется подождать, пока Процесс 1 освободит этот ресурс (как показано на рисунке 2).
Еще одно требование синхронизации, которое необходимо учитывать, — это порядок, в котором должны выполняться определенные процессы или потоки. Например, нельзя сесть в самолет до покупки билета. Аналогично, нельзя проверять электронную почту до проверки соответствующих учетных данных (например, имени пользователя и пароля). Точно так же банкомат не будет предоставлять никаких услуг, пока не получит правильный PIN-код.
Помимо взаимного исключения, синхронизация также касается следующего:
- взаимоблокировка , которая возникает, когда многие процессы ожидают общего ресурса (критического раздела), который удерживается каким-либо другим процессом. В этом случае процессы просто продолжают ждать и больше не выполняются;
- голодание , которое возникает, когда процесс ожидает входа в критическую секцию, но другие процессы монополизируют критическую секцию, и первый процесс вынужден ждать бесконечно;
- инверсия приоритета , которая возникает, когда процесс с высоким приоритетом находится в критической секции, и он прерывается процессом со средним приоритетом. Такое нарушение правил приоритета может произойти при определенных обстоятельствах и может привести к серьезным последствиям в системах реального времени;
- ожидание занятости , которое возникает, когда процесс часто опрашивает, имеет ли он доступ к критическому разделу. Этот частый опрос отнимает время обработки у других процессов.
Минимизация
[ редактировать ]Одной из задач разработки экзафлопсных алгоритмов является минимизация или уменьшение синхронизации. Синхронизация занимает больше времени, чем вычисления, особенно в распределенных вычислениях. Уменьшение синхронизации привлекало внимание ученых-компьютерщиков на протяжении десятилетий. Принимая во внимание, что в последнее время это становится все более серьезной проблемой, поскольку разрыв между улучшением вычислений и задержкой увеличивается. Эксперименты показали, что (глобальная) связь благодаря синхронизации на распределенных компьютерах занимает доминирующую долю в разреженном итеративном решателе. [2] Этой проблеме уделяется все больше внимания после появления новой эталонной метрики — высокопроизводительного сопряженного градиента (HPCG). [3] для составления рейтинга 500 лучших суперкомпьютеров.
Классические задачи
[ редактировать ]Ниже приведены некоторые классические проблемы синхронизации:
- Проблема производителя-потребителя (также называемая проблемой ограниченного буфера);
- Проблема читателей и писателей ;
- Проблема обедающих философов .
Эти задачи используются для проверки почти каждой вновь предложенной схемы или примитива синхронизации.
Аппаратная синхронизация
[ редактировать ]Многие системы обеспечивают аппаратную поддержку кода критической секции .
Однопроцессорная или однопроцессорная система может отключить прерывания , выполняя текущий код без вытеснения , что очень неэффективно для многопроцессорных систем. [4] «Ключевая способность, необходимая нам для реализации синхронизации в мультипроцессоре, — это набор аппаратных примитивов с возможностью атомарного чтения и изменения ячейки памяти. Без такой возможности стоимость создания базовых примитивов синхронизации будет слишком высокой и будет возрастать по мере того, как количество процессоров увеличивается. Существует ряд альтернативных формулировок основных аппаратных примитивов, каждая из которых обеспечивает возможность атомарного чтения и изменения местоположения, а также некоторый способ определить, выполнялись ли эти аппаратные примитивы атомарно. являются основными строительными блоками, которые используются для создания широкого спектра операций синхронизации на уровне пользователя, включая такие вещи, как блокировки и барьеры . В общем, архитекторы не ожидают, что пользователи будут использовать базовые аппаратные примитивы, а вместо этого ожидают, что примитивы будут. использоваться системными программистами для создания библиотеки синхронизации, а этот процесс часто бывает сложным и непростым». [5] Многие современные аппаратные средства предоставляют такие атомарные инструкции, двумя распространенными примерами являются: test-and-set , которая работает с одним словом памяти, и Compare-and-swap , которая меняет местами содержимое двух слов памяти.
Поддержка языков программирования
[ редактировать ]В Java одним из способов предотвращения помех потоков и ошибок согласованности памяти является добавление к сигнатуре метода ключевого слова Synchronized ; в этом случае для обеспечения синхронизации используется блокировка объявляющего объекта. Второй способ — поместить блок кода в раздел Synchronized(someObject){...} , который обеспечивает более детальное управление. Это заставляет любой поток получить блокировку someObject , прежде чем он сможет выполнить содержащийся блок. Блокировка автоматически снимается, когда поток, получивший блокировку, покидает этот блок или переходит в состояние ожидания внутри блока. Любые обновления переменных, выполненные потоком в синхронизированном блоке, становятся видимыми для других потоков, когда они аналогичным образом получают блокировку и выполняют блок. В любой реализации любой объект может использоваться для обеспечения блокировки, поскольку все объекты Java имеют встроенную блокировку или блокировку монитора, связанную с ними при создании экземпляра. [6]
блоки Java Синхронизированные , помимо обеспечения взаимного исключения и согласованности памяти, позволяют передавать сигналы, то есть отправлять события из потоков, которые получили блокировку и выполняют блок кода, тем, которые ожидают блокировки внутри блока. разделы Java Таким образом, синхронизированные сочетают в себе функциональность мьютексов и событий для обеспечения синхронизации. Такая конструкция известна как монитор синхронизации .
также .NET Framework использует примитивы синхронизации. [7] «Синхронизация спроектирована так, чтобы быть совместной, требуя, чтобы каждый поток следовал механизму синхронизации перед доступом к защищенным ресурсам для получения согласованных результатов. Блокировка, сигнализация, облегченные типы синхронизации, ожидания ожидания и взаимосвязанные операции — это механизмы, связанные с синхронизацией в .NET». [8]
целые специализированные языки написаны Многие языки программирования поддерживают синхронизацию, и для разработки встроенных приложений , где строго детерминированная синхронизация имеет первостепенное значение.
Выполнение
[ редактировать ]Спинлок
[ редактировать ]Другой эффективный способ реализации синхронизации — использование спин-блокировок. Прежде чем получить доступ к любому общему ресурсу или фрагменту кода, каждый процессор проверяет флаг. Если флаг сброшен, процессор устанавливает его и продолжает выполнение потока. Но если флаг установлен (заблокирован), потоки будут продолжать вращаться в цикле и проверять, установлен ли флаг или нет. Но спин-блокировки эффективны только в том случае, если флаг сброшен для младших циклов, в противном случае это может привести к проблемам с производительностью, поскольку на ожидание тратится много процессорных циклов. [9]
Барьеры
[ редактировать ]Барьеры просты в реализации и обеспечивают хорошую оперативность. Они основаны на концепции реализации циклов ожидания для обеспечения синхронизации. Предположим, что три потока выполняются одновременно, начиная с барьера 1. По истечении времени t поток 1 достигает барьера 2, но ему все равно приходится ждать, пока потоки 2 и 3 достигнут барьера 2, поскольку у него нет правильных данных. Как только все потоки достигают барьера 2, все они начинаются заново. По истечении времени t поток 1 достигает барьера 3, но ему придется снова ждать потоков 2 и 3 и правильных данных.
Таким образом, при барьерной синхронизации нескольких потоков всегда будет несколько потоков, которые в конечном итоге будут ожидать других потоков, как в приведенном выше примере поток 1 продолжает ожидать потоки 2 и 3. Это приводит к серьезному снижению производительности процесса. [10]
Функция ожидания барьерной синхронизации для i й поток можно представить как:
(Wбарьер)i=f ((Tбарьер)i, (Rthread)i)
Где Wbarrier — время ожидания потока, Tbarrier — количество прибывших потоков, а Rthread — скорость прибытия потоков. [11]
Эксперименты показывают, что 34% общего времени выполнения тратится на ожидание других, более медленных потоков. [10]
Семафоры
[ редактировать ]Семафоры — это механизмы сигнализации, которые могут позволить одному или нескольким потокам/процессорам получить доступ к разделу. Семафор имеет флаг, с которым связано определенное фиксированное значение, и каждый раз, когда поток желает получить доступ к разделу, он уменьшает этот флаг. Аналогично, когда поток покидает раздел, флаг увеличивается. Если флаг равен нулю, поток не может получить доступ к разделу и блокируется, если решит подождать.
Некоторые семафоры допускают только один поток или процесс в разделе кода. Такие семафоры называются бинарными семафорами и очень похожи на мьютексы. Здесь, если значение семафора равно 1, потоку разрешен доступ, а если значение равно 0, доступ запрещен. [12]
Математические основы
[ редактировать ]Синхронизация изначально представляла собой концепцию, основанную на процессах, посредством которой можно было получить блокировку объекта. Его основное использование было в базах данных. Существует два типа блокировки (файлов) ; только чтение и чтение-запись. Блокировки только для чтения могут быть получены многими процессами или потоками. Блокировки чтения-записи являются эксклюзивными, поскольку они могут использоваться только одним процессом/потоком одновременно.
Хотя блокировки были созданы для файловых баз данных, данные также совместно используются в памяти между процессами и потоками. Иногда одновременно блокируется более одного объекта (или файла). Если они не заблокированы одновременно, они могут перекрываться, вызывая исключение взаимоблокировки.
Java и Ada имеют только монопольные блокировки, поскольку они основаны на потоках и полагаются на инструкции процессора сравнения и замены .
Абстрактную математическую основу примитивов синхронизации дает моноид истории . Существует также множество теоретических устройств более высокого уровня, таких как исчисление процессов и сети Петри , которые можно построить поверх моноида истории.
Примеры
[ редактировать ]Ниже приведены некоторые примеры синхронизации для разных платформ. [13]
В Windows
[ редактировать ]Windows обеспечивает:
- маски прерываний , защищающие доступ к глобальным ресурсам (критическому разделу) на однопроцессорных системах;
- спин-блокировки , которые в многопроцессорных системах предотвращают вытеснение потока спин-блокировки;
- динамические диспетчеры [ нужна ссылка ] , которые действуют как мьютексы , семафоры , события и таймеры .
В Linux
[ редактировать ]Linux обеспечивает:
- семафоры ;
- спинлок ;
- барьеры ;
- мьютекс ;
- блокировки чтения-записи для более длинной части кодов, к которым обращаются очень часто, но которые меняются не очень часто;
- чтение-копирование-обновление (RCU). [14]
Включение и отключение вытеснения ядра заменило спин-блокировки в однопроцессорных системах. До версии ядра 2.6 Linux отключал прерывания для реализации коротких критических участков. Начиная с версии 2.6 и более поздних версий Linux является полностью вытесняющим.
В Солярисе
[ редактировать ]Солярис обеспечивает:
- семафоры
- переменные условия
- адаптивные мьютексы — бинарные семафоры, которые реализуются по-разному в зависимости от условий. [15]
- замки чтения-писателя
- турникеты – очередь потоков, ожидающих полученной блокировки [16]
В Pthreads
[ редактировать ]Pthreads — это независимый от платформы API , который обеспечивает:
- мьютексы;
- переменные условия;
- блокировки чтения-записи;
- спинлоки;
- барьеры .
См. также
[ редактировать ]- Фьючерсы и обещания , механизмы синхронизации в чисто функциональных парадигмах
- Барьер памяти
Ссылки
[ редактировать ]- ^ Грамоли, В. (2015). Больше, чем вы когда-либо хотели знать о синхронизации: Synchrobench, измеряющий влияние синхронизации на параллельные алгоритмы (PDF) . Материалы 20-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования. АКМ. стр. 1–10.
- ^ Шэнсинь, Чжу, Тунсян Гу и Синпин Лю (2014). «Минимизация синхронизации в разреженных итерационных решателях для распределенных суперкомпьютеров» . Компьютеры и математика с приложениями . 67 (1): 199–209. дои : 10.1016/j.camwa.2013.11.008 .
- ^ «Бенчмарк HPCG» .
- ^ Зильбершац, Авраам; Ганье, Грег; Гэлвин, Питер Баер (11 июля 2008 г.). «Глава 6: Синхронизация процессов». Концепции операционной системы (Восьмое изд.). Джон Уайли и сыновья. ISBN 978-0-470-12872-5 .
- ^ Хеннесси, Джон Л.; Паттерсон, Дэвид А. (30 сентября 2011 г.). «Глава 5: Параллелизм на уровне потоков». Компьютерная архитектура: количественный подход (Пятое изд.). Морган Кауфманн. ISBN 978-0-123-83872-8 .
- ^ «Внутренние блокировки и синхронизация» . Учебники по Java . Оракул . Проверено 10 ноября 2023 г.
- ^ «Обзор примитивов синхронизации» . Microsoft Learn . Майкрософт . Проверено 10 ноября 2023 г.
- ^ Роуз, Маргарет. «Синхронизация» . Техопедия . Проверено 10 ноября 2023 г.
- ^ Масса, Энтони (2003). Разработка встроенного программного обеспечения с помощью ECos . Pearson Education Inc. ISBN 0-13-035473-2 .
- ^ Jump up to: а б Мэн, Чен, Пан, Яо, Ву, Цзинлэй, Тяньчжоу, Пин, Цзюнь Минхуэй (2014). «Спекулятивный механизм барьерной синхронизации». Международная конференция IEEE по высокопроизводительным вычислениям и коммуникациям (HPCC) 2014 г., 6-й Международный симпозиум IEEE по безопасности и защите киберпространства (CSS) 2014 г. и 11-я Международная конференция IEEE по встраиваемому программному обеспечению и системам (ICES) 2014 г.
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Рахман, Мохаммед Махмудур (2012). «Синхронизация процессов в многопроцессорном и многоядерном процессоре». 2012 Международная конференция по информатике, электронике и зрению (ICIEV) . стр. 554–559. дои : 10.1109/ICIEV.2012.6317471 . ISBN 978-1-4673-1154-0 . S2CID 8134329 .
- ^ Ли, Яо, Цин, Кэролин (2003). Концепции реального времени для встраиваемых систем . Книги КМП. ISBN 978-1578201242 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Зильбершац, Авраам; Ганье, Грег; Гэлвин, Питер Баер (7 декабря 2012 г.). «Глава 5: Синхронизация процессов». Концепции операционной системы (Девятое изд.). Джон Уайли и сыновья. ISBN 978-1-118-06333-0 .
- ^ «Что такое RCU по сути? [LWN.net]» . lwn.net .
- ^ «Адаптивные датчики блокировки» . Документы Оракл .
- ^ Мауро, Джим. «Турникеты и приоритетное наследование – SunWorld – август 1999 г.» . sunsite.uakom.sk .
- Шнайдер, Фред Б. (1997). О параллельном программировании . Springer-Verlag New York, Inc. ISBN 978-0-387-94942-0 .
Внешние ссылки
[ редактировать ]- Анатомия методов синхронизации Linux на IBM DeveloperWorks
- Маленькая книга семафоров , Аллен Б. Дауни
- Необходимость синхронизации процессов
