Алгоритм «Пекарня Лампорта» для безопасного доступа к ресурсам
Lamport's bakery algorithm
Алгоритм пекарни Лампорта: безопасный доступ к общим ресурсам в многопоточных системах. Предотвращает повреждение данных, обеспечивая взаимное исключение потоков.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Логика безопасного совместного использования компьютерных ресурсов
Logic for safely sharing computer resources
Алгоритм пекарни Лампорта — это компьютерный алгоритм, разработанный учёным-компьютерщиком Лесли Лампортом в рамках его длительного исследования формальной корректности параллельных систем, предназначенный для повышения безопасности при использовании общих ресурсов несколькими потоками посредством взаимного исключения. В информатике часто возникает ситуация, когда несколько потоков одновременно обращаются к одним и тем же ресурсам. Повреждение данных может произойти, если две или более нити пытаются записать в одно и то же место в памяти, или если одна нить читает данные из памяти до того, как другая завершит запись. Алгоритм пекарни Лампорта — один из множества алгоритмов взаимного исключения, разработанных для предотвращения одновременного входа конкурирующих потоков в критические участки кода, чтобы исключить риск повреждения данных.
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion. In computer science, it is common for multiple threads to simultaneously access the same resources. Data corruption can occur if two or more threads try to write into the same memory location, or if one thread reads a memory location before another has finished writing into it. Lamport's bakery algorithm is one of many mutual exclusion algorithms designed to prevent concurrent threads entering critical sections of code concurrently to eliminate the risk of data corruption.
Аналогия
Лампорт представил себе пекарню с аппаратом выдачи номеров у входа, чтобы каждому посетителю присваивался уникальный номер. Номера увеличиваются на единицу с каждым входящим посетителем. Глобальный счетчик отображает номер посетителя, которого в данный момент обслуживают. Все остальные посетители должны ждать в очереди, пока пекарь не закончит обслуживание текущего посетителя и не будет отображен следующий номер. Когда посетитель заканчивает покупки и выбрасывает свой номер, кассир увеличивает номер, позволяя обслужить следующего посетителя. Этот посетитель должен взять новый номер из аппарата, чтобы совершить следующие покупки. Согласно аналогии, "посетители" – это потоки, идентифицируемые буквой i, получаемой из глобальной переменной. В силу ограничений компьютерной архитектуры некоторые аспекты аналогии Лампорта требуют незначительной корректировки. Возможно, что несколько потоков получат один и тот же номер n при запросе; этого нельзя избежать (без предварительного решения проблемы взаимного исключения, что и является целью алгоритма). Поэтому предполагается, что идентификатор потока i также служит приоритетом. Меньшее значение i означает более высокий приоритет, и потоки с более высоким приоритетом первыми войдут в критическую секцию.
Lamport envisioned a bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed. When the customer is done shopping and has disposed of his or her number, the clerk increments the number, allowing the next customer to be served. That customer must draw another number from the numbering machine in order to shop again. According to the analogy, the "customers" are threads, identified by the letter i, obtained from a global variable. Due to the limitations of computer architecture, some parts of Lamport's analogy need slight modification. It is possible that more than one thread will get the same number n when they request it; this cannot be avoided (without first solving the mutual exclusion problem, which is the goal of the algorithm). Therefore, it is assumed that the thread identifier i is also a priority. A lower value of i means a higher priority and threads with higher priority will enter the critical section first.
Некритическая секция
Некритическая секция — это часть кода, не требующая исключительного доступа. Она представляет собой вычисления, специфичные для конкретного потока, которые не влияют на ресурсы и выполнение других потоков. Эта часть аналогична действиям, выполняемым после совершения покупки, например, возвращению сдачи в кошелек.
The non critical section is the part of code that doesn't need exclusive access. It represents some thread specific computation that doesn't interfere with other threads' resources and execution. This part is analogous to actions that occur after shopping, such as putting change back into the wallet.