Родитель засыпал навсегда: чего Rust не делает за вас в ядре ОС

[Siemargl]

Rust убирает целый класс ошибок, и это правда. Но он не убирает ошибки порядка синхронизации

Убирает простые ошибки, оставляет сложные. Этого в рекламе не пишут.

Вообще, я ссылочку не вспомню, но есть такая вещь, как "паттерны многопоточного программирования". Найди их и не изобретай велосипед, как в этом посте.

[sciofuturum]

С первой частью согласен, про это и текст.

Про велосипед: я и не говорю, что изобрёл примитив. Перепроверка условия под тем же локом, который держит будильщик, это обычный condvar, так же устроены и Convar, и pthread. Стоило это в статье оговорить.

Интересным было другое: стандартную схему не получилось применить в лоб. Держать лок очереди поперёк проверки нельзя, потому что поиск зомби берёт локи в порядке "дети, потом таблица процессов", а выход процесса наоборот. Вложение замкнуло бы цикл, отсюда и счётчик поколений.

Если знаете готовый паттерн для этого случая, скиньте, правда интересно.

[Siemargl]

Список паттернов на самом деле длинный.

По-моему пример в посте это двухфазная блокировка.

[sciofuturum]

Двухфазная блокировка это про транзакции в БД, там смысл в порядке захвата и освобождения ради сериализуемости. Здесь другое.

По структуре ближе двойная проверка: проверить, взять лок, проверить ещё раз. Но её обычно применяют для ленивой инициализации, а тут перепроверка условия перед сном, то есть по сути condvar. Разница в том, что применить его в лоб мешал порядок блокировок, из-за этого и понадобился счётчик.

[Siemargl]

двухфазная блокировка - два ресурса (у тебя две очереди) - две блокировки

изменения статуса == транзакция

сначала ставятся блокировки, потом меняются данные, блокировки снимаются в обратном порядке

[sciofuturum]

Схема правильная, но она требует единого порядка захвата. У меня два пути уже фиксируют противоположные: поиск зомби берёт children, потом ptable, а выход процесса берёт ptable, потом wait_queue. Обернуть проверку в лок очереди значит потребовать wait_queue в ptable, и получается цикл. Двухфазная блокировка циклы не разрешает, она предполагает, что их нет.

И второе: между проверкой и снятием лока поток должен уснуть. Уснуть, держа лок очереди ожидания, значит заблокировать того, кто придёт будить.

Собственно, поэтому и понадобился счётчик поколений: он даёт ту же атомарность решения, не удерживая ничего поперёк сна.

[TheHost]

мне кажется вы беседуете с ЛЛМком)) будильщик, ё, двоеточее, какой-то несвязный набор слов со стилем явно иишным

[rukhi7]

Упрощённо wait4 делал так:

1. взять лок списка детей, поискать зомби;

2. зомби нет, отпустить лок;

3. взять лок очереди ожидания, поставить себя в очередь, уснуть.

А exit на другом ядре в это же время делал так:

1. выставить состояние Zombie;

2. взять лок очереди ожидания, разбудить того, кто там есть.

штудировать список паттернов действительно странное предложение, когда есть конкретная задача.

Самое простое решение, по моему, завести список зомби-детей (это же списки указателей?), вместо очереди ожидания, если я правильно понимаю задачу. Зомби должен добавлять себя в эту очередь, когда он становится зомби. Самое интересное что он должен получить ссылку (указатель?) на эту очередь от парента видимо при рождении (хотя возможны варианты, например ребенок может уже иметь указатель на структуру с данными парента и достать оттуда то что нужно в любой удобный момент).

Честно говоря я не понял что за очередь ожидания у парента? он же один парент? кто еще может попасть в эту очередь? И при каких условиях?

[sciofuturum]

Про очередь: там ждут потоки, а не процессы. У процесса может быть несколько потоков, и wait4 может вызвать любой из них. Плюс сама очередь это общий примитив ядра, не специальный под wait4. Стоило это в статье пояснить, спасибо.

Про список зомби: он у меня и есть, поиск идёт как раз по списку детей, и ребёнок при выходе публикует своё состояние сам. Но гонку это не убирает. Разверните по шагам: родитель проверил список и увидел пусто, ребёнок добавился и пошёл будить, родитель уснул. Окно то же самое, просто информация теперь лежит в другом месте.

Дело не в том, где хранится факт "есть зомби", а в том, что проверка факта и засыпание не атомарны относительно его публикации. Пока эти два действия не сериализованы с пробуждением, любая структура данных даст ту же дыру. Отсюда и перечитывание условия под локом будильщика.

[rukhi7]

Но гонку это не убирает. Разверните по шагам: родитель проверил список и увидел пусто, ребёнок добавился и пошёл будить, родитель уснул.

это убирает гонку если лок привязан к этой очереди, то есть зомби лочит очередь и парент не может ее прочитать пока лок не снимет тот кто его взял. И наоборот, если парент залочил очередь на чтение, зомби будет ждать эту очередь чтобы сменить состояние и тут вот я тоже не вижу достаточно информации что должно быть после того как парент вызвал wait ... Он должен дождаться же окончания всех чайлдов???

Если так то вообще все стандартно: чайлд удаляет себя из списка детей и добавляет себя в список зомбЕй с соответствующими локами, оба списка принадлежат паренту. Тогда wait должен висеть пока список детей не станет пустым! Но висеть он должен НЕ потребляя процесорного времени! Это просто специальный лок который лочит поток который вызвал такой wait до момента когда список стал пустым. Вот такой конкретный паттерн ищите, если самому не получится додуматься! Это не чайлд будит родителя! Это родитель заблокирован до тех пор пока список чайлдов не опустел! Пока все чайлды не закончились и не стерли себя из списка чайлдов. Что-то в этом роде должно быть, я почти уверен. Эти штуки всегда такие хитрые получаются!

[sciofuturum]

Лок на очереди сериализует доступ к самой очереди. А гонка не там: условие проверяется под локом списка детей, а засыпание идёт под локом очереди ожидания. Это разные локи и разные структуры, и между двумя операциями ничего не удерживается. Удерживать нельзя: порядок захвата у find_zombie и у exit противоположный, вложение замкнёт цикл.

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

И wait4 не ждёт завершения всех детей, он ждёт одного и возвращает его статус. Ждать опустошения списка это другая семантика.

Пробуждать кто-то всё равно должен. Если родитель спит, разбудить его может только тот, кто изменил условие. Альтернатива только опрос в цикле.

[Jijiki]

похоже на интрузивный счетчик ссылок потоков тоесть такая сущность шедулер, которая отслеживает использование памяти(или комбо: память+ссылки),в С++, мне это напомнило

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

[sciofuturum]

Речь была не про управление памятью, а про порядок синхронизации при засыпании.....

[rukhi7]

Ещё раз: система типов Rust к этому не имеет отношения. Здесь нечего проверять на уровне типов

если задача предметной области сформулирована/понята/интерпретирована не правильно, никакая система типов не поможет найти нужное решение, просто потому что даже правильное решение неправильной задачи не будет иметь смысла.

[sciofuturum]

Согласен, и это шире моего тезиса.

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

[kuraga333]

Так какой паттерн тут нужно было применить, товарищи комментаторы?

[say_TT_plz]

Я конечно не системный программист(только учусь), я но я всегда думал, что используется обратный кольцевой буфер для передачи события о завершении родителю. Ну и всякую магию шмагию LAPIC, прерывания то есть.

[si_12345]

Я заметил одну странную вещь, которая к ядрам не имеет отношения
Я на расте сам не пишу, все пишет дипсик
Я формализую математические алгоритмы, которые затем дипсик реализует на расте
И получается так, что однопоточная версия одного и того же алгоритма работает как правило не медленнее многопоточной
Дипсик использует rayon::prelude, std::sync::{Arc, Mutex}, std::thread, file.lock().unwrap() и т.д.

[sciofuturum]

многопоточность не ускоряет автоматически, Mutex вокруг общих данных часто съедает весь выигрыш, а на мелких задачах накладные расходы на потоки больше самой работы.