В параллельном программировании одновременный доступ к общим ресурсам может привести к неожиданному или ошибочному поведению. Таким образом, части программы, где осуществляется доступ к общему ресурсу, должны быть защищены способами, которые избегают одновременного доступа. Один из способов сделать это известен как критическая секция или критическая область . В эту защищенную секцию не может войти более одного процесса или потока одновременно; другие приостанавливаются, пока первый не покинет критическую секцию. Обычно критическая секция обращается к общему ресурсу, такому как структура данных , периферийное устройство или сетевое соединение, которое не будет работать правильно в контексте множественного одновременного доступа. [1]
Различные коды или процессы могут состоять из одной и той же переменной или других ресурсов, которые должны быть прочитаны или записаны, но результаты которых зависят от порядка, в котором происходят действия. Например, если переменная x должна быть прочитана процессом A, а процесс B должен записать в переменную x в то же время, процесс A может получить либо старое, либо новое значение x .
Процесс А:
// Процесс A . . b = x + 5 ; // инструкция выполняется в момент времени = Tx . Процесс Б:
// Процесс B . . x = 3 + z ; // инструкция выполняется в момент времени = Tx . В случаях, когда механизм блокировки с более мелкой гранулярностью не нужен, критическая секция важна. В приведенном выше случае, если A необходимо прочитать обновленное значение x , выполнение процесса A и процесса B одновременно может не дать требуемых результатов. Чтобы предотвратить это, переменная x защищена критической секцией. Сначала B получает доступ к секции. Как только B заканчивает запись значения, A получает доступ к критической секции, и переменная x может быть прочитана.
Тщательно контролируя, какие переменные изменяются внутри и вне критической секции, предотвращается одновременный доступ к общей переменной. Критическая секция обычно используется, когда многопоточная программа должна обновить несколько связанных переменных без внесения отдельным потоком конфликтующих изменений в эти данные. В связанной ситуации критическая секция может использоваться для обеспечения того, чтобы к общему ресурсу, например, принтеру, мог получить доступ только один процесс за раз.
Реализация критических секций различается в разных операционных системах.
Критическая секция обычно завершается через конечное время, [2] и поток, задача или процесс должны ждать фиксированное время, чтобы войти в нее ( ограниченное ожидание ). Чтобы гарантировать исключительное использование критических секций, требуется некоторый механизм синхронизации при входе и выходе из программы.
Критическая секция — это часть программы, требующая взаимного исключения доступа.
Как показано на рисунке, [3] в случае взаимного исключения ( mutex ) один поток блокирует критическую секцию, используя методы блокировки, когда ему необходимо получить доступ к общему ресурсу, а другие потоки должны ждать своей очереди, чтобы войти в секцию. Это предотвращает конфликты, когда два или более потоков совместно используют одно и то же пространство памяти и хотят получить доступ к общему ресурсу. [2]
Самый простой способ предотвратить любые изменения управления процессором внутри критической секции — это реализация семафора. В однопроцессорных системах это можно сделать, отключив прерывания при входе в критическую секцию, избежав системных вызовов, которые могут вызвать переключение контекста внутри секции, и восстановив прерывания в их предыдущем состоянии при выходе. При такой реализации любой поток выполнения, входящий в любую критическую секцию в системе, не даст любому другому потоку, включая прерывание, получить время обработки на ЦП, пока исходный поток не покинет свою критическую секцию.
Этот подход грубой силы можно улучшить с помощью семафоров . Чтобы войти в критическую секцию, поток должен получить семафор, который он освобождает при выходе из секции. Другие потоки не могут войти в критическую секцию одновременно с исходным потоком, но могут свободно получить контроль над ЦП и выполнить другой код, включая другие критические секции, защищенные другими семафорами. Блокировка семафоров также имеет ограничение по времени для предотвращения состояния взаимоблокировки, при котором блокировка приобретается одним процессом на бесконечное время, останавливая другие процессы, которым необходимо использовать общий ресурс, защищенный критической секцией.
Обычно критические секции предотвращают миграцию потоков и процессов между процессорами, а также вытеснение процессов и потоков прерываниями и другими процессами и потоками.
Критические разделы часто допускают вложение. Вложение позволяет входить и выходить из нескольких критических разделов с небольшими затратами.
Если планировщик прерывает текущий процесс или поток в критической секции, планировщик либо позволит текущему выполняемому процессу или потоку работать до завершения критической секции, либо запланирует процесс или поток на другой полный квант. Планировщик не перенесет процесс или поток на другой процессор и не запланирует другой процесс или поток для выполнения, пока текущий процесс или поток находится в критической секции.
Аналогично, если прерывание происходит в критической секции, информация о прерывании записывается для будущей обработки, а выполнение возвращается процессу или потоку в критической секции. [4] После выхода из критической секции, а в некоторых случаях и завершения запланированного кванта, ожидающее прерывание будет выполнено. Концепция кванта планирования применяется к « циклическому перебору » и аналогичным политикам планирования .
Поскольку критические секции могут выполняться только на процессоре, на котором они введены, синхронизация требуется только внутри исполняющего процессора. Это позволяет входить и выходить из критических секций практически без затрат. Межпроцессорная синхронизация не требуется. Нужна только синхронизация потока инструкций. [5] Большинство процессоров обеспечивают требуемый уровень синхронизации, прерывая текущее состояние выполнения. Это позволяет критическим секциям в большинстве случаев быть не более чем количеством введенных критических секций на процессор.
Улучшения производительности включают выполнение ожидающих прерываний на выходе из всех критических секций и разрешение планировщику работать на выходе из всех критических секций. Кроме того, ожидающие прерывания могут быть переданы другим процессорам для выполнения.
Критические разделы не должны использоваться в качестве долгосрочного примитива блокировки. Критические разделы должны быть достаточно короткими, чтобы в них можно было входить, выполнять и выходить из них без каких-либо прерываний со стороны оборудования и планировщика.
Критические секции на уровне ядра являются основой проблемы блокировки программного обеспечения .
В параллельном программировании код делится на потоки. Конфликтующие переменные чтения-записи разделяются между потоками, и каждый поток имеет их копию. Такие структуры данных, как связанные списки , деревья и хэш-таблицы, имеют переменные данных, которые связаны и не могут быть разделены между потоками; следовательно, реализация параллелизма очень сложна. [6] Для повышения эффективности реализации структур данных несколько операций, таких как вставка, удаление и поиск, могут выполняться параллельно. При выполнении этих операций могут быть сценарии, когда один и тот же элемент ищется одним потоком и удаляется другим. В таких случаях вывод может быть ошибочным . Поток, ищущий элемент, может иметь попадание, тогда как другой поток может впоследствии удалить его. Эти сценарии вызовут проблемы в работающей программе, предоставляя ложные данные. Чтобы предотвратить это, один из методов заключается в том, чтобы держать всю структуру данных в критической секции, чтобы одновременно обрабатывалась только одна операция. Другой метод заключается в блокировке используемого узла в критической секции, чтобы другие операции не использовали тот же узел. Таким образом, использование критической секции гарантирует, что код выдаст ожидаемые результаты. [6]
Критические разделы также встречаются в коде, который манипулирует внешними периферийными устройствами, такими как устройства ввода-вывода. Регистры периферийного устройства должны быть запрограммированы с определенными значениями в определенной последовательности. Если два или более процессов управляют устройством одновременно, ни один из процессов не будет иметь устройство в требуемом состоянии, и последует некорректное поведение.
Когда на устройстве вывода необходимо создать сложную единицу информации путем выполнения нескольких операций вывода, требуется исключительный доступ, чтобы другой процесс не испортил данные, перемежая свои собственные биты вывода.
В направлении ввода требуется исключительный доступ при чтении сложных данных посредством нескольких отдельных операций ввода. Это предотвращает использование некоторых частей другим процессом, что приводит к повреждению.
Устройства хранения данных предоставляют форму памяти. Концепция критических секций одинаково актуальна как для устройств хранения данных, так и для общих структур данных в основной памяти. Процесс, который выполняет множественный доступ или операции обновления файла, выполняет критическую секцию, которая должна быть защищена соответствующим механизмом блокировки файла.
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ){{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )