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

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

Критической областью называют секцию программы, которая должна выполняться с исключительным правом доступа к разделяемым данным, на которые имеются ссылки в этой программе. Процесс, готовящийся войти в критическую область, может быть задержан, если любой другой процесс в это время выполняется в подобной критической области. Одним из средств, позволяющих программистам или компиляторам надежно организовывать критические области, являются семафоры или замки (блокировки). В машинах с распределенной памятью (например, Intel Hypercube) для синхронизации вычислений образом, сходным с замками и семафорами в машинах с общей памятью, используются сообщения. Конечно, замки и сообщения не исключают друг друга, так как возможно представить себе гибридные машины, в которых оба средства синхронизации могут быть использованы одновременно.

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

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