Сокращение конкуренции/блокировки в системе заданий с зависимостями чтения/записи?

Да, это, вероятно, выполнимо.

Во-первых, давайте проигнорируем проблему общего и эксклюзивного доступа и предположим, что все доступы эксклюзивны.

Для каждой зависимости рассматривается атомарный булев, представляющий, используется ли она. Мы накладываем общий порядок на зависимости, т.е. они образуют массив/вектор. Это означает, что задание может объявить свои зависимости через упорядоченный список индексов зависимостей.

Это позволяет заданию атомарно приобретать каждую зависимость по очереди. Если все задания приобретают зависимости в одном и том же порядке, то тупиковые ситуации предотвращаются (именно поэтому мы наложили общий порядок на зависимости). Если одна из зависимостей уже используется, ранее приобретенные зависимости освобождаются снова.

Необходимым примитивом для таких атомарных операций является метод variable.compare_exchange(expected, new), который атомарно устанавливает переменную в новое значение, но только если в данный момент она содержит ожидаемое старое значение.

По сути, мы заменим этот фрагмент кода

lock(dependenciesMtx)
        
if CanRunNode(job)
    PushJobDependencies(job) // Store this job's shared/exclusive dependencies
    LaunchJob(job)
else
    jobsToRepush.push(job)        

unlock(dependenciesMtx)

на что-то вроде:

std::vector<std::atomic<bool>> available_deps = ...;

int dep = 0;
bool ok = true;

// acquire the dependencies in order
for (; dep < job.deps.size(); dep++) {
   ok &= available_deps[job.deps[dep]].compare_exchange(false, true);
   if (!ok) break;
}

if (ok) {
  LaunchJob(job);
} else {
  // release already-acquired dependencies, must use reverse order
  for(; dep >= 0; dep--)
    assert(available_deps[jobs.dep[dep]].compare_exchange(true, false));

  jobsToRepush.push(job);
}

Этот подход можно распространить на общие зависимости, заменив атомарный bool атомарным беззнаковым целым числом, которое подсчитывает задания, имеющие доступ. Тогда у нас будет три класса значений:

• 0: никто в настоящее время не имеет доступа к зависимости
• n (любое другое значение): существует n рабочих мест с общим доступом к этой зависимости
• -1 (или какое-то максимальное значение): кто-то имеет эксклюзивный доступ.

Приобретение общего доступа будет заключаться в увеличении текущего счета, при этом необходимо убедиться, что максимальное значение не будет достигнуто.

Приобретение эксклюзивного доступа будет означать dependency.compare_exchange(0, -1).

Однако не факт, что атомики будут работать лучше.

Прежде всего, атомики имеют различные "порядки памяти", которые вы можете выбирать для каждой операции. В C++ по умолчанию используется наиболее ограничительный и наименее производительный порядок памяти seq_cst, который может быть эмулирован на некоторых платформах с помощью блокировок (которых вы пытаетесь избежать). Возможно, вы сможете значительно повысить производительность, если будете уверены, что сможете обойтись более мягким порядком памяти, таким как acq_rel.

Во-вторых, на практике мьютексы не обязательно медленные. Это зависит от борьбы с блокировками и от выбранной упорядоченности памяти. Подход, основанный на атомиках, вероятно, будет лучше, если задания имеют наборы зависимостей с небольшим перекрытием. Но это определенно стоит проверить в бенчмарке.

Рекомендую посмотреть эти видео для лучшего погружения в вопрос:

Прикрепленное видео 1 - Операционные системы, урок 5: Взаимное исключение. Семафоры. Проблема чтения, записи

Прикрепленное видео 2 - ТПМС 1. Взаимное исключение