Как можно сравнивать и заменять для взаимного исключения без ожидания для любой общей структуры данных?
Будучи новичком в многопоточности и мьютексах, я начинал изучать википедию. Я наткнулся на эту часть:
CAS может использоваться для достижения взаимного исключения без ожидания для любой общей структуры данных путем создания связанного списка, где каждый узел представляет желаемую операцию, которая должна быть выполнена. Затем CAS используется для изменения указателей в связанном списке во время вставки нового узла. Только один процесс может быть успешным в его CAS; все другие процессы, пытающиеся добавить узел одновременно, должны будут повторить попытку. Каждый процесс может затем сохранить локальную копию структуры данных и, пройдя по связанному списку, может выполнить каждую операцию из списка в своей локальной копии.
Теперь я понимаю основную концепцию CAS, где мы в основном используем атомарную операцию, которая сравнивает значение с заранее заданным значением, и, если оно совпадает, мы меняем их местами. Но я не смог понять, что здесь означает «связанный список желаемых операций»?
И почему все процессы следуют одному и тому же связанному списку операций?
Решение
Связанный список содержит операции над общей структурой данных.
Например, если у меня есть стек, он будет манипулировать с помощью толчков и всплывающих окон. Связанный список будет представлять собой набор толчков и щелчков в псевдо-общем стеке. Каждый поток, совместно использующий этот стек, на самом деле будет иметь локальную копию, и, чтобы добраться до текущего общего состояния, он будет проходить по связанному списку операций и применять каждую операцию к своей локальной копии стека. Когда он достигает конца связанного списка, его локальная копия содержит текущее состояние (хотя, конечно, оно может стать устаревшим в любое время).
В традиционной модели у вас будут какие-то блокировки вокруг каждого толчка и удара. Каждый поток будет ждать, чтобы получить блокировку, затем сделать push или pop, а затем снять блокировку.
В этой модели каждый поток имеет локальный снимок стека, который он синхронизирует с представлением стека другими потоками, применяя операции в связанном списке. Когда он хочет манипулировать стеком, он вообще не пытается манипулировать им напрямую. Вместо этого он просто добавляет свою операцию push или pop в связанный список, так что все другие потоки могут / будут видеть эту операцию, и все они могут оставаться в синхронизации. Затем, конечно, он применяет операции в связанном списке, и когда (например) появляется всплывающее окно, он проверяет, какой поток запросил всплывающее окно. Он использует всплывающий элемент, если и только если это поток, который запросил эту конкретную популярность.
Другие решения
Других решений пока нет …