OSDev

для всех
Текущее время: 19 окт 2019, 05:00

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 14 ]  На страницу Пред.  1, 2
Автор Сообщение
СообщениеДобавлено: 05 мар 2013, 00:17 

Зарегистрирован: 18 апр 2010, 15:59
Сообщения: 155
pavia писал(а):
Мое ИХМО от первого.
По крайней мере проблем будет минимум. Ловим прерывание тормозим все ядра/процессоры через IPI. Выполняем планирование в одном потоке. Раскидываем по ядрам задачи.
Эффективность правда маленькая.
А со вторым вариантом вопросов много и проблемы блокировки надо решать.

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

Wikipedia по поводу терминологии говорит следующее:
In computing, cache coherence (also cache coherency) refers to the consistency of data stored in local caches of a shared resource.
Когерентность кэша (англ. cache coherence) — свойство кэшей, означающее целостность данных, хранящихся в локальных кэшах для разделяемого ресурса.
Соответственно под когерентностью кэша понимают механизм обеспечения целостности данных в памяти. Механизм реализуется за счет того, что одна и та же строка памяти может находиться ТОЛЬКО в одном кэше в момент времени. На практике реализуется за счет специального протокола работы системной шины, согласно которому ВСЕ устройства обладающие кэшем используют так называемый модуль слежения (Snooping Agent) который вычитывает ВСЕ транзакции обращения к памяти идущие по системной шине и блокирует транзакцию, если обнаруживает, что запрашиваемая строка памяти уже закэширована в подконтрольном агенту кэше. За этим следует сброс запрашиваемой строки из кэша в память, после чего транзакция разблокируется и данная строка переходит в другой кэш. В результате становится невозможной коллизия, при которой два процессора ОДНОВРЕМЕННО изменили одну и ту же область памяти.
Я полагаю, что я верно использовал термин.
Повторюсь. TLB не когерентен. Соответственно, целостность его содержимого необходимо поддерживать программно.
Himik писал(а):
Не вижу особых вопросов по синхронизации. Переназначил потоку идентификатор процессора и всё, ну и пару вспомогательных параметров, как указатель ядерного стека. Впрочем я не пробовал.

Проблема в том, что у нас единое расписание и единый алгоритм планирования использующий кучу структур данных. Чтобы все это работало корректно, все структуры данных должны оставаться целостными. По этой причине они должны быть защищены блокировками (например спинлоками). При росте количества ядер, с одной стороны возрастает интенсивность зарпросов на перепланирование (банально больше задач блокируются по тем или иным причинам в единицу времени). И с другой стороны процессоры ожидающие перепланирования простаивают большее время ожидая входа в критическую секцию планировщика. Причем заметьте, что они простаивают в холостом цикле, ничего не делая (кроме может быть обработки прерываний), так как чтобы что-нибудь делать они должны получить план от планировщика.
Himik писал(а):
А куда плясать? Балансировка она либо есть, либо нет. Тут либо 1) либо 2) без вариантов.

Плясать в сторону гибридного варианта, то есть совмещения приятного с полезным. По-крайней мере Linux пляшет в этом ритме. Более чем уверен, что большинство остальных операционных систем inductrial quality тоже выбрали этот стиль танца. Вопрос в том, что научиться лучше танцевать и как это сделать.
D-S писал(а):
D-S

В целом поддерживаю ваш ход мыслей. За исключением того, что первая схема в реализации все-таки проще второй. Я бы сказал - топорнее. Но вторая, более элегантная, так как она более эффективная и масштабируемая. Привязка процесса к процессору в западной литературе называется Affinity scheduling. Основной целью такого подхода обычно декларируют увеличение общей производительности системы за счет использования "разогретых" кэшей. Подход опирается на предположение, что если процесс уже выполнялся недавно на данном процессоре, то существует вероятность, что данные необходимые для дальнейшей работы процесса могут все еще быть в кэше процессора. А это значит, что экономится значительное количество тактов, которые бы процессоры пришлось бы потратить, чтобы подтянуть эти данные из памяти.
Himik писал(а):
Есть предположение, что основная проблема балансировки связана с нелинейностью загрузки процессора по времени, когда ядра заняты "скачками". Если измерение после одного тика таймера показало, что некое ядро загружено на 100%, это не значит, что в следующем тике оно будет так же загружено. Имеет смысл накапливать некую статистику загрузки за 2 или более тиков таймера, чтобы принять адекватное решение.

Вы верно мыслите. Вообще в балансировке корень всех зол - неодинаковость задач. Одна задача будет выполняться 30 тактов и заблокируется, другая - выест свой квантум времени до конца и будет насильственно выпилена планировщиком по тику таймера. Поэтому в балансировке стоит другая дилемма: насколько часто нужно производить перепланирование (по крайней мере - глобальное). Чем реже производишь перепланирование, тем меньше накладные расходы на само планирование и тем более разбалансированный план получаешь. И наоборот, чем чаще производишь перепланирование, тем больши накладные расходы на само планирование и меньше разбалансированность системы.
Himik писал(а):
Ещё имеет смысл использовать адаптивный (или как ещё называют интеллектуальный, smart) планировщик. Вот ZarathustrA описал две основных концепции и задался вопросом выбора. А ведь можно динамически применять то один то другой вид планирования в зависимости от текущей загрузки, и таким образом применять обе концепции. В периоды, когда загрузка системы низкая, то можно применять линейное распределение потоков по второму варианту. И лишь при сильной загрузке системы запускать механизм балансировки по первому варианту. При снижении загрузки нужно опять вернуться к линейному распределению.

Вы пляшете в верном направлении! Так держать!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 05 мар 2013, 01:48 

Зарегистрирован: 21 сен 2007, 17:24
Сообщения: 1091
Откуда: Балаково
ZarathustrA писал(а):
Повторюсь. TLB не когерентен. Соответственно, целостность его содержимого необходимо поддерживать программно.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 05 мар 2013, 11:41 

Зарегистрирован: 18 апр 2010, 15:59
Сообщения: 155
Что я понимаю под отсутствием/наличием когерентности.
1) Наличие. Присутствует в кэшах L1, L2, L3 etc. Проявление наличия: при изменении строки данных находящейся в строке физической памяти X, невозможна ситуация при которой процесс a1 на процессоре A1 изменил данные в строке, а процесс a2 на процессоре A2 все еще работает с устаревшей копией данных. Таким образом, все процессы, на всех процессорах всегда оперируют актуальной копией данных.
2) Отсутствие. Присутствует в TLB. Проявление отсутствия: Процесс(вернее поток) a1 на процессоре A1 изменяет свое адресное пространство и заявляет, что странице виртуальной памяти V1 соответствует страница физической памяти P2, в то время как ранее данной странице виртуальной памяти соответствовала страница физической памяти P1. В результате, поток a1 на процессоре A1 обращаясь к странице виртуальной памяти V1 читает пишет данные в страницу физической памяти P2, так как он сбросил свой локальный TLB и тот заполнился актуальными правилами отображения виртуальных страниц на физические. И так как TLB буфер используется процессором как первичный источник правил перевода. В то же самое время, процесс a2 на процессоре A2 не сбросил свой TLB, и соответственно, тот не подхватил актуальные правила отображения из физической памяти (таблицы страниц) и в этом TLB может храниться устаревшее правило перевода, согласно которому странице виртуальной памяти V1 соответствует страница физической памяти P1. А так как TLB - это первичный источник правил перевода для процессора, то будет использоваться именно он, а не актуальная таблица страниц в физической памяти.

В результате: поток a1 и a2 работают в одном и том же адресном пространстве и обращаются к одной и той же области памяти V1 (с точки зрения этих потоков, они работают с одной и той же памятью), однако на самом деле они работают с разной памятью. Один с P1, а второй с P2. И если поток a1 станет ожидать изменения значения глобальной переменной в в данной области памяти, которое должен произвести поток a2, то он будет ждать вечно, даже если поток a2 это изменение уже давно сделал. То есть, оба потока думают, что они выполнили свою часть работы. Это как в случае с почтальоном, получателем письма и почтовым ящиком в двери квартиры. Получатель письма проживающий в квартире #49 регулярно проверяет наличие письма, открывая почтовый ящик изнутри квартиры. Почтальон, приносит письма и ложит в почтовый ящик квартиры с номером указанном на конверте. Все вроде бы ок. Получатель и почтальон выполняют свою работы без халтуры и на 100%. Но письмо никогда не дойдет, если хулиган, или домоуправитель изменит номер квартиры не извещая об этом почтальона. Тот просто будет ложить письма в ящик соседней квартиры.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 18 мар 2013, 17:06 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 963
Откуда: Дагоба
SII,
Категорически :) рекомендую к прочтению главу 4 "Планировщик" из книги Роберта Лава "Разработка ядра Linux" (есть в электронном виде djvu). Описано множество неочевидных подводных камней, разобраны стратегии планировки и даны конкретные примеры. Большинство вопросов и сомнений отпадут.

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

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB