Код, приведенный ранее, все еще использует две блокировки, хотя и умеренно. Что позволит нам реализовать полностью не блокирующую очередь, которую смогут использовать несколько поставщиков и потрбителей одновременно? Для заинтригованных, готовых разобраться в тонкостях и деталях читателей, приведу ссылки на две ключевые работы, заслуживающие внимания.
В 1996 г. Michael и Scott опубликовали работу (M. Michael and M. Scott. "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms"), описывющую два варианта реализации очереди с внутренней синхронизацией. Один из вариантов действительно не блокирующий, другой использует блокировку для поставщиков и еще одну для потребителей, подобно примеру в статье. В 2003 Herlihy, Luchango и Moir показали на проблемы масштабируемости в подходе Michael и Scott представили свою собственную реализацию без блокировок (M. Herlihy, V. Luchango and M. Moir. "Obstruction-Free Synchronization: Double-Ended Queues As an Example").
Особенностью описанных подходов является необходимость использования операции сравнить-и-обменять двойной ширины (так же известной как "DCAS"), способной обрабатывать указатель и целый счетчик атомарно. Это достаточно проблемтично, потому что не все платформы имеют операцию DCAS, особенно широко распространенные процессоры, которым потребуется к тому же 128 битный CAS (Мы можем заставить это заработать и для 64 бит через героические попытки исхитриться обокрасть 64 битное пространство, допуская, что большинсво операционных систем сегодня на самом деле не используют все 64 бита адреса и возможно удасться ухватить пару-тройку битов не заметно. Тем не менее это крайне хрупкое и непортируемое решение, и нет гарантий что и другим людям, тем же разработчикам вашей ОС, не пришла в голову идея умыкнуть пару бит в этом бешенном 64 битном мире, и гонка за них уж началась. В действительности, провернуть подобный трюк вам удасться только если операционная система это вы, ну или ваш лучший друг). В дополнение, потребуется и корректно работающий инициализатор пустого списка.
В 1996 г. Michael и Scott опубликовали работу (M. Michael and M. Scott. "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms"), описывющую два варианта реализации очереди с внутренней синхронизацией. Один из вариантов действительно не блокирующий, другой использует блокировку для поставщиков и еще одну для потребителей, подобно примеру в статье. В 2003 Herlihy, Luchango и Moir показали на проблемы масштабируемости в подходе Michael и Scott представили свою собственную реализацию без блокировок (M. Herlihy, V. Luchango and M. Moir. "Obstruction-Free Synchronization: Double-Ended Queues As an Example").
Особенностью описанных подходов является необходимость использования операции сравнить-и-обменять двойной ширины (так же известной как "DCAS"), способной обрабатывать указатель и целый счетчик атомарно. Это достаточно проблемтично, потому что не все платформы имеют операцию DCAS, особенно широко распространенные процессоры, которым потребуется к тому же 128 битный CAS (Мы можем заставить это заработать и для 64 бит через героические попытки исхитриться обокрасть 64 битное пространство, допуская, что большинсво операционных систем сегодня на самом деле не используют все 64 бита адреса и возможно удасться ухватить пару-тройку битов не заметно. Тем не менее это крайне хрупкое и непортируемое решение, и нет гарантий что и другим людям, тем же разработчикам вашей ОС, не пришла в голову идея умыкнуть пару бит в этом бешенном 64 битном мире, и гонка за них уж началась. В действительности, провернуть подобный трюк вам удасться только если операционная система это вы, ну или ваш лучший друг). В дополнение, потребуется и корректно работающий инициализатор пустого списка.
Это была завершающая часть статьи. Буду очень рад, если данный перевод тем или иным образом помог вам или натолкнул на какие-то мысли. В дальнейшем я планирую продолжать практику перевода статей. Возможно, кому-то может показаться что я понапрасну трачу время, потому что знание английского языка для программиста является самим собой разумеющимся, но таким образом мне хотелось бы попробовать сформировать традицию рускоязычного профессионального журнала, так и не появившегося за все это время.
Оставайтесь на линии ;)
Оставайтесь на линии ;)
Комментариев нет:
Отправить комментарий