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