OSDev

Доброго времени суток, господа Ось-Девелоперы:)

; Я у вас тут новенький. Вот тоже интересуюсь разного рода разработками.
; ...в основном теоритическими)) Уже пол года борюсь с миниксом,
; и всё бы ничего, да вот написан он для наглядности, а не для работы,
; а основной удар пришёлся какрас по производительности...
; Ясно, что это связано и с его микроядерной архитектурой.
; Все попытки найти информацию по оптимизации и "заточке" оси
; приводят либо к дорогим и тяжёлым стандартам, либо к оптимизации
; на уровне языка.
; Здесь я хотел-бы поднять тему производительности современных систем,
; которая касается не только микроядер, но и всех систем вцелом.
; В качестве старта хочу рассмотреть тему многопоточности, которую поднял
; сегодня утром, после чего решил зарегистрироваться у вас.
; Просьба сильно не бить камнями. Таки вот...

* * * * * * * * * * * * * * * * * * * * * * *

Допустим, что потоки, занятые решением одной задачи обмениваются
данными через общий блок данных (разделяемый объект), и доступ к
нему синхронизирован двоичным семафором (мутексом).
Если не учитывать потери времени на реализацию IPC и синхронизацию,
и принять, что один независимый поток решает задачу за условное время
(t), то минимальное время (t.min), за которое потоки решат задачу равно:

t.min = n/s;

Где:
n - общее число потоков, разделяющих процессор.
s - число потоков, занятых решением одной задачи.

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

Представим обычную ситуацию взаимоисключения. Для простоты представления
возьмём очередь из 6-ти потоков, из которых два (А,В) заняты решением
одной общей задачи и имеют один общий разделяемый объект (для связи).

Допустим, «А» обращается к объекту и захватывает мутекс. В этот момент
происходит аппаратное прерывание (таймер), и диспетчер передает управление
следующему по списку очереди потоку (например «В»). «В», в свою очередь, желая
обратиться к объекту, пытается захватить занятый мутекс, и оказывается
заблокирован. Если А для работы с объектом требуется время равное или
меньшее предоставленного ему кванту времени, то «В» выйдет из состояния
блокировки не раньше, чем пройдёт очередь следующих 4-х потоков, и управление
перейдет к «А», который освободит мутекс.

tb = n*р;

Здесь:
tb - время, в течении которого В заблокирован.
р - целое число квантов времени, необходимое для работы с объектом.

А т.к. скорость работы системы (в данном случае решения задачи) ограничена
скоростью самого медленного из её элементов (В), получаем:


t.max = t.min + tb*q;

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

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

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

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

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

* * * * * *

При работе с буферами обмена возникает ситуация, известная как "проблема
потребителя и производителя". Суть её заключается в том, что если один поток
"производитель" записывает информацию в буфер быстрей, чем другой читает, возникает
момент, когда буфер переполняется, и "производитель", в следствии, блокируется
системой до тех пор, пока "потребитель" ни опустошит буфер. Далее блокируется
"потребитель". Как видно из контекста выше, блокировки приводят к огромным потерям
производительности. Но эту ситуацию нельзя разрешить редкими и быстрыми операциями
чтения и записи в буфер.
Работа таких потоков выглядит "скачкообразно", а скорость передачи данных через
буфер (без учёта простоя в блокировках!) равна скорости самого медленного потока.
А если потоки, при этом, имеют разные приоритеты, то блокировка потока с большим
приоритетом затягивается на неопределённый срок.
На практике ситуация разрешается инверсией приоритетов, притом тогда, когда уже
имеет место блокировка.
Можно попробовать разрешить ситуацию следующим образом: условно разделить буфер на
три части. Нижнюю и верхнюю области назовём "горячими", а центральную, соответственно,
"холодной". Каждый раз когда производитель обращается к буферу, он проверяет уровень
"наполненности" буфера, после чего записывает в него данные. Если уровень выше
некоторого значения (горячая область), то "производитель" обращается к системе с
просьбой понизить его приоритет, а приоритет "потребителя" повысить. Аналогично
поступает и "потребитель", если видит, что уровень упал.
Изменение приоритетов возможно производить до некоторого установленного предела,
или до тех пор, пока уровень наполненности буфера не вернётся в "холодную область".
При таком подходе исключены блокировки, по причине переполнения или опустошения
буфера, а скорость передачи данных становится равной средней скорости потоков, т.к.
их скорости "выравниваются".

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

1. Поток А получил управление и захватил мутекс, поскольку ему что-то там надо было изменить в разделяемой области.
2. Квант времени, выделенный потоку А, в этот момент истёк, и ОС передала управление потоку Б.
3. Поток Б нуждается в захвате этого же мутекса; никакой работы, которую можно выполнять без захвата, у него нет. Поэтому он обращается к ОС с запросом на безусловный захват мутекса.
4. ОС обнаруживает, что мутекс захвачен другим потоком, а значит, немедленно удовлетворить запрос потока Б невозможно. Поэтому она прекращает выполнение потока Б и ставит его в очередь к мутексу. После этого она передаёт управление следующему потоку.
5. Выполняются следующие потоки. Если они хотят получить тот же мутекс, они также немедленно снимаются системой и ставятся в очередь к мутексу.
6. В конце концов управление возвращается потоку А, он делает свои чёрные дела и освобождает мутекс. Обнаружив освобождение, ОС помечает поток Б как готовый к продолжению выполнения.
7. Когда приходит время, система возобновляет выполнение потока Б с точки, где он запросил мутекс, причём в этот момент мутекс уже принадлежит потоку Б.

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

Спасибо за замечание. С точки зрения параллелизма выполнения потоков, и производительности системы вцелом
изменений не происходит. Тут Вы абсолютно правы. Если у нас есть 6 потоков, и при условии, что ни один из них не находится в очереди ожидания события (освобождения мутекса, у-ва в/в и др.) и каждому предоставлен квант времени в 1-ну секунду, то вся очередь пройдёт за 6 секунд. Это факт. И тут я Вами согласен. Но если взглянуть
на выполнение процесса, в рамках которого исполняются потоки А и В, то разница в среднем времени исполнении
задачи процесса (если она не вечный цикл, конечно)) Раньше, в системах пакетной оброботки использовался такой интересный алгоритм планирования: "Самое короткое задание - первое". Напомню в чём его смысл.
Имеем 3 задания:
1. 10 секунд для исполнения.
2. 5 секунд, и
3. 3 секунды

-Общее время исполнения заданий - 18 секунд. С момента старта первое задание исполнится через 10 сек.,
второе через 15 сек., а третье - 18.
-Среднее время выполнения заданий - (10+15+18)/3=14,3 секунды.

А теперь поменяем задания местами: 3-2-1.
Общее время не изменилось, а среднее - (3+8+18)/3=9,7 секунд.

Так и здесь, если поток В идёт следом за потоком А, то на обмен данными между ними уйдёт 2 кванта. А если поток А становится причиной того, что В ждёт в очереди "блокированных":), пока пройдет вся очередь "неблокированных", пока А доделает свои чёрные дела и освободит мутекс, после чего можно глянуть - чё он (А) там наделал, уйдет много времени)) А если А и В работают во благо одного процесса, то для процесса это окажется ощутимым. Т.е. увеличится СРЕДНЕЕ время, а ОБЩЕЕ останется прежним.))

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

Высокий приоритет ещё не даёт право на больший квант времени. Каждому приоритету соответствуе своя очередь к процессору. Ожидать в "очередях" освобождения ресурса(ов) можно НЕ зависимо от приоритета. Общее время - это то время, за которое все процессы (пусть даже в самой приоритетной) очереди сделают круг. А среднее время - это то, за которое процесс нарисует 8 пикселов, обработает 14 килобайт звука и посчитает пи до двухсотой степени. Так, что говоря о важности общёй производительности, Вы, наверное, имели ввиду среднюю))
А что касается отдельного приложения - увольте, но мне кажется что вся ос состоит из "отдельных" приложений, и от их средней скорости работы зависит скорость всей ос вцелом.

А вообще, наш с Вами спор было-бы лучше и проще решить на практике. Вот, как я себе это представляю:
Взять простенькую многозадачную/многопоточную ос с открытым исх/кодом.
Встроить в планировщик счётчик потоков, приходящих в очередь ожидания.
Запустить НЕСКОЛЬКО "тяжёлых" процессов, которые имеют логическое завершение, способны фиксировать время своего исполнения, и способных к IPC и вводу-выводу.
НЕ изменяя кванта времени, создавать ситуации взаимных исключений.
И сравнивать общее время исполнения всех процессов с показаниями счётчика.

Да уж, таки просто....)))

У Вас однобокое понимание механизмов работы оси. Очередь может быть одна, их может быть много -- и вовсе не обязательно по одной очереди на каждый приоритет. Размер кванта может не зависеть от приоритета, а может и зависеть. В общем, всё зависит от выбранных создателями оси алгоритмов и их реализации. А поэтому



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

Мне кажется мы немного ушли от темы, и появляется ощущение спора-ради-спора. Возможно, в этом моя вина. И вся проблема в моей манере изложения. Поправлюсь. Алгоритмов планирования миллион! Я не пытаюсь Вас переспорить в теории диспетчеризации или в негласных правилах мутексов. Механизмы их работы мы с Вами представляем одинакого. Я не пытаюсь рушить правила синхронизации придуманые ещё во времена молодости моей бабушки. Я просто хочу сказать, что от перимены мест слоегаемых, в нашем случае, сумма меняется.
И было бы очень приятно, если бы Вы попытались поняли смысл моего романса)) и мы могли продолжить обсуждение в этом направлении.
Спасибо)

Формулы правильные. А в чём основной вопрос, не совсем понятно.
Если в планировщике ОС правильно работает приоритетность по очерёдности и по размерам квантов, то запрограммированная многопоточная задача будет работать как надо.

Ладно. Попробую переизложить материал.

* * * * *

Теория.
В многозадачных операционных системах процессам часто бывает необходимо взаимодействовать между собой.
И для того, чтобы их взаимодействие было безопасным (не вредило системе вцелом и не зависело от особенностей организации многозадачности в данной системе), ос предоставляет необходимые механизмы.
Один из таких механизмов предупреждает опасные ситуации, называемые "гонками" - ситуации исход которых, зависит от скорости взаимодействующих процессов, и результатом, как правило становится потеря данных, совместно используемых этими процессами.
Этот механизм называется "механизмамом синхронизации". Далее, мы будем рассматривать один из таких механизмов, в целях моделирования ситуации. "Мутекс" - простой примитив синхронизации, который позволяет находиться в критической секции только одному процессу единовременно.
Если процесс обращается, например к совместной области данных, то он захватывает мутекс, и все последующие обращения к отой области другими процессами, будут не допущены. Такие процессы блокируются операционной системой, и помещаются в очередь ожидания некоторого события (в данном случае освобождения мутекса).
Но каким-бы простым не казался межанизм, его течение проходит ни совсем гладко для процесса. В часности его работа (механизма) отражается на быстродействии.
Представим себе две очереди к процессору (хотя их может быть и больше).
1. Очередь Готовых процессов, ожидающих освобождения процессора.
2. Очередь Ожидающих (например, освобождения мутекса) процессов.
У нас есть три процесса, каждый и которых имеет по два потока.
Process 1. (Threads A, B)
Process 2. (Threads C, D)
Process 3. (Threads E, F)
В данном случае, для простоты представления возьмём один процесс. Это несложно изобразить графически.

Очередь 1. A, B, C, D, E, F
Очередь 2. ...

В данном случае очередь 2 пуста (пока), а процессы поступают на исполнение в порядке от A к F.
Допустим "А" пишет в область данных, которую совместно разделяет с "В", и успевает "отдать" мутес ДО завершения истечения своего времени (кванта). У правление переходит к "В", который успешно читает предназначеную для него информацию. Для общения "А" и "В" понадобилось 2 кванта времени.
Смотрим далее:

Очередь 1. A', X, C, D, E, F
Очередь 2. ...B

В данном случае "А" захватил мутекс (штрих над "А"),не успел написать сообщение, как управление перешло к "В".
"В", в свою очередь, ничего не подозревая "по-привычке))" обращается к области данных, но т.к. мутекс занят, высокопривелегированная часть ос (ядро) блокирует "В", и помещает в очередь 2, ожидать освобождения мутекса.
Управление переходит к "С", и т.д. И только после того, как пройдёт вся очередь (C-F), управление перейдёт к "А",
который доделает работу, и освободит мутекс. ОС видит, что мутекс свободен, и переносит "В" обратно в очередь 1 на своё место. Далее управление, наконец-таки), переходит к "В", который так-же "по-привычке" читает предназначеную для него информацию.
То, что для "А" заняло на один такт (квант) времени больше, то для "В" заняло 6! тактов, т.к. пришлось пропустить всю очередь. А т.к. "А" и "В" работают на благо одного процесса (Process 1), в рамках которого происходит обмен данными, то производительность процесса упала в:

Ситуация_плохо / Ситуация_хорошо = (2а+6в)/(1а+1в) = 8/2 = 4 раза.

Потеря производительности касается КАЖДОГО процесса, ограниченного рамками механизмов синхронизации, будь он один, или их восемь миллионов, суперважный он или паразитный. И не зависимо от того, в какой очереди и с каким приоритетом "крутятся" потоки процесса, они способны "тормозить" совмесную работу ПОСТФАКТУМ.
А это значит, что изменение приоритета, и прочие хитрости будут уместны, как "боржоми" на "лысую голову")))

*************

Для тех, кому интересен вопрос производительности в современных (многозадачных!) системах, отсылаю к первому посту, и велком обсуждать, у кого какие мысли и идеи. Тему синхронизации я поднял для СТАРТА. Но их все и не перечислишь сразу.
Особо внимательные могут попробовать решить верхнюю задачку с 50.000 потоками у 117 процессов, при приоритетной системе планирования при обработке событий в реальном времени, и с инверсией приоритетов.(для простоты можно не учитывать вероятности взаимных блокировок) :)