OSDev

Что правда ты писал? )))

Вот для меня тоже открыт. Было бы интересно поговорить и послушать о планировании в многопроцессорной/многоядерной системе. Можно конечно подсмотреть, но лучше самостоятельно прийти к каким-то заключениям, а потом проверить, совпадает ли это с существующими реализациями или нет. Хотя мы для автора топика до конца не раскрыли суть планирования даже в однопроцессорной/одноядерной системе. Пустились в какие-то идеологические споры, причем каждый остался при своем мнении. Хотя конечно алгоритмы планирования несколько связаны с тем, о чем здесь шел спор, но все же. Я имею достаточно хороший планировщик (на мой взгляд ;) ) для одноядерной системы, но с принципами планирования в многоядерной системе я совершенно не знаком. Вопросов масса... Начать хотя бы с того, что лучше: навешать обработку прерываний на одно ядро или распределить "равномерно" по всем? Всегда ли BIOS вешает SMI на загрузочное ядро? Если так, то дополнительные ядра освобождены от работы в SMM? Если одно ядро простаивает, нужно ли забирать готовый поток из runqueue занятого ядра? Какой поток, какого ядра? Нужно ли пытаться realtime-потоки распределять "равномерно" по всем ядрам? Не проще ли просто очередной создаваемый поток связывать с ядром, имеющим на момент запуска наименьшее кол-во ассоциированных с ним потоков, и больше не переводить этот поток на какое-либо другое ядро? И т.д.

Видимо ваш смайлик меня зацепил.
Вчера наткнулся на ссылку http://citforum.ru/operating_systems/reliable_os/
Цитирую своими словами - ядро Миникс хорошее потому-что на супер быстром компьютере не тормозит.
А ещё я вчера открыл Таненбаума. Которого до этого не открывал. Немного почитал понял что пользы мало или очень мало, поэтому закрыл и снова отправил пылиться на дальнюю полку.

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


Конечно проще. Но мне казалось мы ищем лучше. Как по мне второй самый простой вариант это сделать чередование и оставить привязку на откуп пользовательскому процессу. Как развитие идеи конечно разделить потоки на те, которые можно переключать, а какие не целесообразно. Думаю из статистике можно определить.

На самом деле равномерно распределять, пока не обдумывал. Есть просто волевое решение делать вытесняющую многозадачность. Минусы пока не вижу только плюсы. А в вытесняющей многозадачности равномерного быть не может.

По поводу всего выше сказанного. Еще это все надо пересмотреть с учётом приоритетов. Во общем не завидная задачка получается.

Читал давно в том числе и упомянутую статью. Честно говоря, не произвела особого впечатления. Опусы Таненбаума меня почему-то больше раздражают, чем вдохновляют...

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

Ну, я слово "равномерно" каждый раз писал в кавычках. В одноядерной системе я опираюсь на приоритеты и приоритетные классы (поток более приоритетного класса незамедлительно вытесняет другие; внутри приоритетного класса приоритет влияет только на максимальное время непрерывной работы и др. ресурсы, закрепленные за потоком). Судя по всему, делать многоядерный планировщик нужно на основе конкретного одноядерного, хотя все равно нужно начинать с каких-то простых фундаментальных принципов, присущих многоядерному планированию.

В общем любые, пусть и простые, идеи приветствуются.

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

С какого бока я только к этому не подходил... 1) максимальная независимость каждого ядра, полноценная очередь выполнения для каждого ядра, строгая привязка потока к конкретному ядру; 2) единая очередь выполнения, но исполнитель не один, а несколько.

Разве ж он такое напишет? :)


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


Думаю, надо, но обязательно только со сбором статистики. Если какое-то ядро занято как минимум двумя потоками, работающими длительное время, или это потоки реального времени, то один из них следует перенести на свободное ядро. Скоротечные потоки лучше, видимо, не трогать, – сами уйдут.


Проще, но явно хуже. И, кстати, хорошо, если ядро заточено под быстрый перенос потока с ядря на ядро.


Не знаю, может быть ты что-то под вытесняющей многозадачностью понимаешь другой, но мне ка-ца, что это даже вопрос не планирования ресурсов, а общей надёжности системы. В надёжной системе нельзя полагаться на то, что все потоки совестливые и никто не захватит ЦПУ насовсем. Удивительно, как Novell Netware ухитрялась выжить в условиях невытесняющей многозадачности. В общем, надёжная ОС общего применения обязана быть с вытесняющей многозадачностью.


Думаю, общие принципы следующие:
1. Каждый процессор (ядро) имеет свою очередь задач.
2. Свободный процессор забирает нагрузку у других процессоров.
3. Перегруженный процессор (более одного процесса реального времени) раскидывает критичную нагрузку на другие процессоры.
4. Всё планирование исходит из того, что перенос процесса с ядра на ядро может оказаться затратным (межпроцессорное взаимодействие + наполнение кэша другого процессора).

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.
<<< OS Boot Tools. >>>

Поглядел на википедию. Блин там определение не правильное. Где то в 2008 было правильное.
Вытесняющая многозадачность это такой вид планирования при котором задача с большем приоритетом вытесняют остальные задачи.

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

По поводу надёжности и вытесняющий многозадачности. Дело в том что когда мы имеем такое что один поток с большим приоритетом завис или просто долго работает, то второе ядро не должно обрабатывать поток с меньшим приоритетом, если есть поток с большим приоритетом, но привязанный к другому ядру. Иначе критически важный поток просто не получит нужную обработку.

Нет-нет, ТАМ как-раз ПРАВИЛЬНОЕ определение :)
В твоём случае стоит говорить о вытесняющих приоритетах, но не о вытесняющей многозадачности.
О приоритетах. Мне не нравится прямолинейный алгоритм, когда задачи с более низким приоритетом выполняются только в том случае, если нет задач с более высоким (вытеснение). Я думаю, задачи надо разбивать на классы, как минимум нескольких уровней:
1. Реального времени;
2. Интерактивные;
3. Нормальные;
4. Фоновые.
Вот между классами есть вытеснение, т.е. задачи более высокого класса вытесняют более низкий класс, и то, я не стал бы полностью вытеснять интерактивные (в системах с пользовательским интерфейсом).
А в рамках одного класса должны быть уровни приоритета, так что задачи с бОльшим приоритетом получают бОльшую долю ЦПУ, но всё равно не вытесняют остальные задачи полностью.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.
<<< OS Boot Tools. >>>

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

Прям как в винде.

Так я тоже думаю, что хуже, но не могу убедительно ответить на вопрос: "Почему хуже?" Понятно, что если нужно переносить поток с одного ядра на другое, то лучше это делать как можно быстрее.


1. Видимо, так.
2. Да, но требует уточнения: вы сами говорили, что однозначно нужно забирать тяжеловесный поток (высокоприоритетный). А вот если таковых нет, брать легковесный (один или даже несколько) или уходить в спячку, пока тебя не нагрузит и не разбудит другое ядро?
3. Требует серьезного уточнения. Ядро может и не само этим заниматься. Раз мы уже сошлись на том, что очередь выполнения для каждого ядра своя, это может сделать выводящее из ожидания высокоприоритетный поток ядро, который может быть закреплен и за другим ядром. Оно просто проверяет, выполняет ли уже ядро, за которым был закреплен выходящий из ожидания поток, другой высокоприоритетный поток. Если да, то пытается перевести выходящий поток на другое ядро, которое спит или обрабатывает менее приоритетные потоки. Кстати вопрос, нужно ли считать актуальной информацию о "родном" ядре для потока, который не находится ни в одной очереди выполнения? Какое ядро является более подходящим для дальнейшей работы потока: 1) на котором он выполнялся до перехода в состояние ожидания ("родное" ядро); 2) которое вывело его из состояния ожидания?
4. Да, только каковы критерии того, эффективнее перевести поток на другое ядро или проще его придержать на текущем ядре?

Не согласен. Вытесняющая многозадачность - это противоположность кооперативной многозадачности. Т.е. если ядро забирает управление у потока (по таймеру), когда он сам явно не обращается к ядру, то это уже вытесняющая многозадачность. А то что вы говорите, это вытесняющая многозадачность на основе приоритетов.

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

Во-во. Тоже интересный вопрос, не нужно ли оставить небольшую форточку при выполнении более приоритетных потоков для менее приоритетных, чтобы не перекрывать последним полностью кислород.