Блог

Я пытаюсь понять, как работает теория взаимного исключения.

В нем говорится

Когда такой связанный список используется совместно несколькими потоками выполнения, два потока выполнения могут попытаться удалить два разных узла одновременно, один поток выполнения изменяет следующий указатель узла i-1 , чтобы указать на узел i 1 , в то время как другой поток выполнения изменяет следующий указатель узла i , чтобы указать на узел i 2 .

Здесь запутался:

Хотя обе операции удаления завершаются успешно, желаемое состояние связанного списка не достигается: узел i 1 остается в списке, потому что следующий указатель узла i-1 указывает на узел i 1.

 the desired state of the linked list is not achieved
  

Могу я узнать, что он пытается сказать "because the next pointer of node i-1 points to node i 1." ? Не мог понять.

Рассмотрим связанный список

 A -> B -> C -> D
  

Вы говорите потоку 1 «Эй, удалите B для меня, хорошо?». В то же время вы говорите потоку 2: «Эй, ты можешь удалить C для меня?».

Затем одновременно происходит следующее:

• Поток 1 думает: «Хорошо, я хочу удалить B. Это означает, что я должен указать на C вместо B. «
• Поток 2 думает: «Хорошо, я хочу удалить C. Это означает, что я должен указать B на D вместо C. «

Два потока разделены; они не знают, что делает другой. Таким образом, они оба считают, что их аргументы имеют смысл. И они это делают, но только тогда, когда никто другой не изменяет список одновременно. Результат выглядит следующим образом:

 A -> C -> D
       B -^
  

A больше не указывает на B; вместо этого он указывает на C. Аналогично, B больше не указывает на C; вместо этого он указывает на D .

… и поскольку B больше недоступен, он будет собран как мусор, оставляя это:

 A -> C -> D
  

Мы сказали одному потоку удалить B, а другому потоку удалить C. B исчез, но C все еще в списке. Это не то, что мы ожидали; мы ожидали, что останутся только A и D.

Это очень простой пример того, как могут произойти ужасные ошибки, когда несколько потоков одновременно изменяют одни и те же данные. Вам нужно либо использовать сложные приемы, чтобы заставить его работать, либо использовать «взаимное исключение», то есть ограничивать изменения списка только одним потоком за раз.

В приведенном вами примере, который, я полагаю, изложен в Википедии, отсутствуют некоторые важные детали.

• У нас есть общий ресурс (i-1)->(i)->(i 1)->(i 2)
• У нас есть два потока выполнения, давайте вызовем их T1 и T2 одновременно получим доступ к связанному списку как к общему ресурсу.
• T1 удаляет узел (i) одновременно T2 с удалением узла (i 1)
• Результирующий список был (i-1) -> (i 2) бы, если бы мы выполнили эти шаги последовательно
• Вместо этого мы получаем : (i-1) -> (i 1) -> (i 2)

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