MegaByte & Linux
Linux
Привет, МегаБайт. Я тут покопался с новой легковесной моделью параллелизма для системного модуля ядра, подумал, может у тебя есть какие-нибудь идеи или свежие мысли. Что думаешь, как сделать планировщик детерминированным, но при этом сохранить код аккуратным?
MegaByte
Конечно. Суть в том, чтобы назначить каждому потоку фиксированный приоритет и разрешить планировщику обрабатывать только один поток с каждым приоритетом одновременно. Так ты получишь детерминированность – никаких гонок за приоритетом. Держи логику планировщика в небольшом, отдельном модуле, предоставь понятный API для модулей ядра и используй блокируемые очереди для рабочих задач. А для счётчиков полагайся на атомарные операции. Так код остаётся чистым, и ты избежишь обычных проблем с блокировками.
Linux
Звучит неплохо – фиксированные диапазоны снижают непредсказуемость. Только будь внимателен к инверсии приоритетов, если задача из нижнего диапазона удерживает общий ресурс; может быть, добавь простую схему старения или механизм повышения приоритета без блокировок? И, да, чистый API – это отлично, но убедись, что границы модуля хорошо документированы, чтобы добавляющие свои диапазоны разработчики не сломали ядро планировщика. Какие у тебя мысли по поводу реализации очередей без блокировок?
MegaByte
Вот что я думаю: Для этого подойдёт однопоточный кольцевой буфер с атомарными указателями на начало и конец. Размер лучше сделать кратным степени двойки, замаскировать индексы, а в ячейках буфера хранить указатель на рабочий элемент. Продюсер просто записывает элемент и атомарно увеличивает указатель на начало, а консьюмер читает из указателя на конец и атомарно его увеличивает. Никаких мьютексов, никаких циклов CAS, только несколько атомарных операций. Если нужна многопоточность, переходи на очередь Michael-Scott – там используй compare-and-swap на указатель на конец, но это немного увеличит накладные расходы. Главное – держать структуру данных маленькой, чтобы она помещалась в строках кэша, и избегать ложного разделения.
Linux
Отлично, приём с кольцевым буфером хорошо влияет на кэш и всё довольно просто. Только удостоверься, что невыраженные записи не позволят компилятору менять порядок записи так, что сломается представление потребителя. Возможно, стоит добавить барьер памяти после увеличения указателя головы, чтобы гарантировать видимость записи. Что касается части с Михаилом и Скоттом, то простой спин-лок на указателе хвоста может быть хорошим компромиссом, если нет сильной конкуренции. Хороший план — дай знать, как прототип получится.
MegaByte
Сначала настрою кольцевой буфер, потом добавлю забор после столкновения с головой, а затем сделаю прототип небольшого спин-лока для хвостовой части очереди MS. Думаю, прототип будет готов к концу недели – как только увижу реальные цифры пропускной способности, дам знать.