Interleaving, race condition и взаимоисключения

Давайте временно отвлечемся от операционных систем, процессов и нитей исполнения и поговорим просто об некоторых “активностях”. Под активностями мы будем понимать последовательное выполнение некоторых действий, направленных на достижение определенной цели. Активности могут иметь место в программном и техническом обеспечении, в обычной деятельности людей и животных. Мы будем разбивать активности на некоторые неделимые или атомарные операции. Например, активность “приготовление бутерброда” можно разбить на следующие атомарные операции:

    1. Отрезать ломтик хлеба.
    2. Отрезать ломтик колбасы.
    3. Намазать ломтик хлеба маслом.
    4. Положить ломтик колбасы на подготовленный ломтик хлеба.

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

Пусть имеется две активности

P: a b c
Q: d e f,

где a, b, c, d, e, fатомарные операции. При последовательном выполнении активностей мы получаем следующую последовательность атомарных действий: