В информатике синхронизация — это задача координации нескольких процессов для объединения или согласования в определенной точке с целью достижения соглашения или выполнения определенной последовательности действий.
Необходимость синхронизации возникает не только в многопроцессорных системах, но и для любого вида параллельных процессов; даже в однопроцессорных системах. Ниже перечислены некоторые из основных потребностей синхронизации:
Форки и объединения : Когда задание достигает точки разветвления, оно разделяется на N подзаданий, которые затем обслуживаются n задачами. После обслуживания каждое подзадание ждет, пока все остальные подзадания не закончат обработку. Затем они снова объединяются и покидают систему. Таким образом, параллельное программирование требует синхронизации, поскольку все параллельные процессы ждут выполнения нескольких других процессов.
Производитель-потребитель: в отношениях производитель-потребитель процесс потребителя зависит от процесса производителя до тех пор, пока не будут получены необходимые данные.
Эксклюзивное использование ресурсов: когда несколько процессов зависят от ресурса и им необходимо получить к нему доступ одновременно, операционная система должна гарантировать, что только один процессор получает к нему доступ в определенный момент времени. Это снижает параллелизм.
Синхронизация потоков определяется как механизм, который гарантирует, что два или более параллельных процесса или потока не будут одновременно выполнять определенный сегмент программы, известный как критический раздел . Доступ процессов к критическому разделу контролируется с помощью методов синхронизации. Когда один поток начинает выполнять критический раздел (сериализованный сегмент программы), другой поток должен ждать, пока первый поток не завершит работу. Если не применяются надлежащие методы синхронизации [1] , это может привести к состоянию гонки , когда значения переменных могут быть непредсказуемыми и меняться в зависимости от времени переключения контекста процессов или потоков.
Например, предположим, что есть три процесса, а именно 1, 2 и 3. Все три из них выполняются одновременно, и им необходимо совместно использовать общий ресурс (критическую секцию), как показано на рисунке 1. Синхронизация должна использоваться здесь, чтобы избежать любых конфликтов при доступе к этому общему ресурсу. Следовательно, когда Процесс 1 и 2 оба пытаются получить доступ к этому ресурсу, он должен быть назначен только одному процессу за раз. Если он назначен Процессу 1, другой процесс (Процесс 2) должен ждать, пока Процесс 1 освободит этот ресурс (как показано на рисунке 2).
Другим требованием синхронизации, которое необходимо учитывать, является порядок, в котором должны выполняться определенные процессы или потоки. Например, нельзя сесть в самолет, не купив билет. Аналогично, нельзя проверить электронную почту, не проверив соответствующие учетные данные (например, имя пользователя и пароль). Точно так же банкомат не предоставит никаких услуг, пока не получит правильный PIN-код.
Помимо взаимного исключения, синхронизация также решает следующие проблемы:
Одной из проблем проектирования алгоритмов exascale является минимизация или уменьшение синхронизации. Синхронизация занимает больше времени, чем вычисления, особенно в распределенных вычислениях. Уменьшение синхронизации привлекало внимание компьютерных ученых на протяжении десятилетий. В то время как в последнее время это становится все более значимой проблемой, поскольку разрыв между улучшением вычислений и задержкой увеличивается. Эксперименты показали, что (глобальные) коммуникации из-за синхронизации на распределенных компьютерах занимают доминирующую долю в разреженном итеративном решателе. [2] Эта проблема привлекает все большее внимание после появления новой контрольной метрики, высокопроизводительного сопряженного градиента (HPCG), [3] для ранжирования 500 лучших суперкомпьютеров.
Ниже приведены некоторые классические проблемы синхронизации:
Эти задачи используются для проверки практически каждой новой предлагаемой схемы синхронизации или примитива.
Многие системы обеспечивают аппаратную поддержку критического раздела кода.
Однопроцессорная или однопроцессорная система может отключить прерывания , выполнив текущий код без вытеснения , что очень неэффективно в многопроцессорных системах. [4] «Ключевая возможность, которая нам требуется для реализации синхронизации в многопроцессорной системе, — это набор аппаратных примитивов с возможностью атомарного чтения и изменения местоположения памяти. Без такой возможности стоимость создания базовых примитивов синхронизации будет слишком высокой и будет увеличиваться по мере увеличения числа процессоров. Существует ряд альтернативных формулировок базовых аппаратных примитивов, все из которых предоставляют возможность атомарного чтения и изменения местоположения, а также некоторый способ узнать, были ли чтение и запись выполнены атомарно. Эти аппаратные примитивы являются основными строительными блоками, которые используются для создания широкого спектра операций синхронизации на уровне пользователя, включая такие вещи, как блокировки и барьеры . В целом, архитекторы не ожидают, что пользователи будут использовать базовые аппаратные примитивы, но вместо этого ожидают, что примитивы будут использоваться системными программистами для создания библиотеки синхронизации, процесс, который часто является сложным и запутанным». [5] Многие современные аппаратные средства предоставляют такие атомарные инструкции, два распространенных примера: test-and-set , которая работает с одним словом памяти, и compare-and-swap , которая меняет местами содержимое двух слов памяти.
В Java одним из способов предотвращения помех потокам и ошибок согласованности памяти является добавление к сигнатуре метода префикса с ключевым словом synchronized , в этом случае блокировка объявляющего объекта используется для обеспечения синхронизации. Второй способ — обернуть блок кода в раздел synchronized(someObject){...} , который обеспечивает более точное управление. Это заставляет любой поток получить блокировку someObject , прежде чем он сможет выполнить содержащийся в нем блок. Блокировка автоматически снимается, когда поток, получивший блокировку, покидает этот блок или переходит в состояние ожидания внутри блока. Любые обновления переменных, сделанные потоком в синхронизированном блоке, становятся видимыми для других потоков, когда они аналогичным образом получают блокировку и выполняют блок. Для любой реализации любой объект может использоваться для предоставления блокировки, поскольку все объекты Java имеют внутреннюю блокировку или блокировку монитора, связанную с ними при создании экземпляра. [6]
Синхронизированные блоки Java , в дополнение к включению взаимного исключения и согласованности памяти, включают сигнализацию — т. е. отправку событий из потоков, которые получили блокировку и выполняют блок кода, тем, которые ожидают блокировки внутри блока. Синхронизированные разделы Java, таким образом, объединяют функциональность как мьютексов , так и событий для обеспечения синхронизации. Такая конструкция известна как монитор синхронизации .
.NET Framework также использует примитивы синхронизации. [7] «Синхронизация разработана как кооперативная, требующая, чтобы каждый поток следовал механизму синхронизации перед доступом к защищенным ресурсам для получения согласованных результатов. Блокировка, сигнализация, облегченные типы синхронизации, spinwait и заблокированные операции — это механизмы, связанные с синхронизацией в .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, (Rнить)i)
Где Wbarrier — время ожидания потока, Tbarrier — количество прибывших потоков, а Rthread — скорость прибытия потоков. [11]
Эксперименты показывают, что 34% общего времени выполнения тратится на ожидание других, более медленных потоков. [10]
Семафоры — это сигнальные механизмы, которые позволяют одному или нескольким потокам/процессорам получать доступ к разделу. У семафора есть флаг, имеющий определенное фиксированное значение, связанное с ним, и каждый раз, когда поток хочет получить доступ к разделу, он уменьшает флаг. Аналогично, когда поток покидает раздел, флаг увеличивается. Если флаг равен нулю, поток не может получить доступ к разделу и блокируется, если он выбирает ожидание.
Некоторые семафоры допускают только один поток или процесс в разделе кода. Такие семафоры называются двоичными семафорами и очень похожи на Mutex. Здесь, если значение семафора равно 1, потоку разрешен доступ, а если значение равно 0, доступ запрещен. [12]
Синхронизация изначально была концепцией на основе процесса, посредством которой можно было получить блокировку на объекте. Ее основное применение было в базах данных. Существует два типа блокировки (файла) : только для чтения и для чтения и записи. Блокировки только для чтения могут быть получены многими процессами или потоками. Блокировки чтения и записи являются исключительными, так как они могут использоваться только одним процессом/потоком одновременно.
Хотя блокировки были получены для файловых баз данных, данные также совместно используются в памяти процессами и потоками. Иногда одновременно блокируется более одного объекта (или файла). Если они не блокируются одновременно, они могут перекрываться, вызывая исключение взаимоблокировки.
В Java и Ada предусмотрены только исключительные блокировки, поскольку они основаны на потоках и полагаются на инструкцию процессора «сравнить и обменять» .
Абстрактная математическая основа для примитивов синхронизации задается моноидом истории . Существует также множество теоретических устройств более высокого уровня, таких как исчисления процессов и сети Петри , которые могут быть построены поверх моноида истории.
Ниже приведены некоторые примеры синхронизации для разных платформ. [13]
Windows обеспечивает:
Linux обеспечивает:
Включение и выключение вытеснения ядра заменило спин-блокировки на однопроцессорных системах. До версии ядра 2.6 Linux отключал прерывания для реализации коротких критических секций. Начиная с версии 2.6 и более поздних версий, Linux полностью вытесняет.
Solaris обеспечивает:
Pthreads — это платформенно-независимый API , который обеспечивает:
{{cite journal}}: CS1 maint: multiple names: authors list (link){{cite book}}: CS1 maint: multiple names: authors list (link)