OSDev http://osdev.su/ |
|
Вопросы производительности многопоточных сред. http://osdev.su/viewtopic.php?f=5&t=322 |
Страница 1 из 18 |
Автор: | Mr.McD. [ 25 май 2010, 21:26 ] |
Заголовок сообщения: | Вопросы производительности многопоточных сред. |
Доброго времени суток, господа Ось-Девелоперы:) ; Я у вас тут новенький. Вот тоже интересуюсь разного рода разработками. ; ...в основном теоритическими)) Уже пол года борюсь с миниксом, ; и всё бы ничего, да вот написан он для наглядности, а не для работы, ; а основной удар пришёлся какрас по производительности... ; Ясно, что это связано и с его микроядерной архитектурой. ; Все попытки найти информацию по оптимизации и "заточке" оси ; приводят либо к дорогим и тяжёлым стандартам, либо к оптимизации ; на уровне языка. ; Здесь я хотел-бы поднять тему производительности современных систем, ; которая касается не только микроядер, но и всех систем вцелом. ; В качестве старта хочу рассмотреть тему многопоточности, которую поднял ; сегодня утром, после чего решил зарегистрироваться у вас. ; Просьба сильно не бить камнями. Таки вот... * * * * * * * * * * * * * * * * * * * * * * * Допустим, что потоки, занятые решением одной задачи обмениваются данными через общий блок данных (разделяемый объект), и доступ к нему синхронизирован двоичным семафором (мутексом). Если не учитывать потери времени на реализацию IPC и синхронизацию, и принять, что один независимый поток решает задачу за условное время (t), то минимальное время (t.min), за которое потоки решат задачу равно: t.min = n/s; Где: n - общее число потоков, разделяющих процессор. s - число потоков, занятых решением одной задачи. Но если учесть особенность механизма синхронизации, которая заключается в блокировании потока, пытающегося захватить занятый мутекс, то возникает совсем другая картина. Представим обычную ситуацию взаимоисключения. Для простоты представления возьмём очередь из 6-ти потоков, из которых два (А,В) заняты решением одной общей задачи и имеют один общий разделяемый объект (для связи). Допустим, «А» обращается к объекту и захватывает мутекс. В этот момент происходит аппаратное прерывание (таймер), и диспетчер передает управление следующему по списку очереди потоку (например «В»). «В», в свою очередь, желая обратиться к объекту, пытается захватить занятый мутекс, и оказывается заблокирован. Если А для работы с объектом требуется время равное или меньшее предоставленного ему кванту времени, то «В» выйдет из состояния блокировки не раньше, чем пройдёт очередь следующих 4-х потоков, и управление перейдет к «А», который освободит мутекс. tb = n*р; Здесь: tb - время, в течении которого В заблокирован. р - целое число квантов времени, необходимое для работы с объектом. А т.к. скорость работы системы (в данном случае решения задачи) ограничена скоростью самого медленного из её элементов (В), получаем: t.max = t.min + tb*q; q - это показатель того (%), насколько часто один из потоков оказывается в состоянии блокировки, по отношению к общему времени решения задачи. При взаимной блокировке q равно бесконечности. Для примера я использовал простую кольцевую очередь (карусель) с небольшим числом потоков. При приоритетном планировании вероятность блокировок не увеличивается, но если происходит взаимоисключение потока высокого приоритета, потоком с приоритетом пониже, возникает необходимость в изменении очерёдности их исполнения (инверсия приоритета), а это дополнительные расходы времени. Напротив, с увеличением числа потоков растёт время "стояния в очереди", и увеличивается вероятность взаимоисключений. В отличии от "простой модели" реальное поведение системы с полноценной приоритетной многозадачностью и временами нахождения в критических секциях в интервале от долей микросекунд (разделяемая память), до нескольких секунд (устройства ввода-вывода), сложно представить "на бумаге", но очевидно, что потери производительности не просто значительные. Как легко догадаться, для уменьшения потерь вызванных последствиями синхронизации, необходимо сводить вероятность взаимоисключений к нулю. Этого можно достигнуть уменьшая общее количество входов в критические секции, и время нахождения в них. Но если поток может гарантировать гораздо меньшее время нахождения в КС, чем предоставленный ему квант времени, а промежутки между входами намного большие этого кванта, то взаимоисключения становятся невозможны. * * * * * * При работе с буферами обмена возникает ситуация, известная как "проблема потребителя и производителя". Суть её заключается в том, что если один поток "производитель" записывает информацию в буфер быстрей, чем другой читает, возникает момент, когда буфер переполняется, и "производитель", в следствии, блокируется системой до тех пор, пока "потребитель" ни опустошит буфер. Далее блокируется "потребитель". Как видно из контекста выше, блокировки приводят к огромным потерям производительности. Но эту ситуацию нельзя разрешить редкими и быстрыми операциями чтения и записи в буфер. Работа таких потоков выглядит "скачкообразно", а скорость передачи данных через буфер (без учёта простоя в блокировках!) равна скорости самого медленного потока. А если потоки, при этом, имеют разные приоритеты, то блокировка потока с большим приоритетом затягивается на неопределённый срок. На практике ситуация разрешается инверсией приоритетов, притом тогда, когда уже имеет место блокировка. Можно попробовать разрешить ситуацию следующим образом: условно разделить буфер на три части. Нижнюю и верхнюю области назовём "горячими", а центральную, соответственно, "холодной". Каждый раз когда производитель обращается к буферу, он проверяет уровень "наполненности" буфера, после чего записывает в него данные. Если уровень выше некоторого значения (горячая область), то "производитель" обращается к системе с просьбой понизить его приоритет, а приоритет "потребителя" повысить. Аналогично поступает и "потребитель", если видит, что уровень упал. Изменение приоритетов возможно производить до некоторого установленного предела, или до тех пор, пока уровень наполненности буфера не вернётся в "холодную область". При таком подходе исключены блокировки, по причине переполнения или опустошения буфера, а скорость передачи данных становится равной средней скорости потоков, т.к. их скорости "выравниваются". |
Автор: | SII [ 25 май 2010, 23:24 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Mr.McD. писал(а): Допустим, «А» обращается к объекту и захватывает мутекс. В этот момент происходит аппаратное прерывание (таймер), и диспетчер передает управление следующему по списку очереди потоку (например «В»). «В», в свою очередь, желая обратиться к объекту, пытается захватить занятый мутекс, и оказывается заблокирован. Если А для работы с объектом требуется время равное или меньшее предоставленного ему кванту времени, то «В» выйдет из состояния блокировки не раньше, чем пройдёт очередь следующих 4-х потоков, и управление перейдет к «А», который освободит мутекс. Если я правильно понял, то Ваше представление не совсем верное. Если подобная многопоточная задача реализована грамотно, то лишний расход времени будет лишь на обращение к системе и тому подобные накладные расходы: 1. Поток А получил управление и захватил мутекс, поскольку ему что-то там надо было изменить в разделяемой области. 2. Квант времени, выделенный потоку А, в этот момент истёк, и ОС передала управление потоку Б. 3. Поток Б нуждается в захвате этого же мутекса; никакой работы, которую можно выполнять без захвата, у него нет. Поэтому он обращается к ОС с запросом на безусловный захват мутекса. 4. ОС обнаруживает, что мутекс захвачен другим потоком, а значит, немедленно удовлетворить запрос потока Б невозможно. Поэтому она прекращает выполнение потока Б и ставит его в очередь к мутексу. После этого она передаёт управление следующему потоку. 5. Выполняются следующие потоки. Если они хотят получить тот же мутекс, они также немедленно снимаются системой и ставятся в очередь к мутексу. 6. В конце концов управление возвращается потоку А, он делает свои чёрные дела и освобождает мутекс. Обнаружив освобождение, ОС помечает поток Б как готовый к продолжению выполнения. 7. Когда приходит время, система возобновляет выполнение потока Б с точки, где он запросил мутекс, причём в этот момент мутекс уже принадлежит потоку Б. Таким образом, ни одного бесполезного такта процессора не тратится: если потоку непременно требуется захватить этот мутекс, он просто запрашивает его у системы таким образом, чтобы она знала: если прямо сейчас она не может отдать ему мутекс, она должна остановить поток. |
Автор: | Mr.McD. [ 26 май 2010, 00:15 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Спасибо за замечание. С точки зрения параллелизма выполнения потоков, и производительности системы вцелом изменений не происходит. Тут Вы абсолютно правы. Если у нас есть 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 кванта. А если поток А становится причиной того, что В ждёт в очереди "блокированных":), пока пройдет вся очередь "неблокированных", пока А доделает свои чёрные дела и освободит мутекс, после чего можно глянуть - чё он (А) там наделал, уйдет много времени)) А если А и В работают во благо одного процесса, то для процесса это окажется ощутимым. Т.е. увеличится СРЕДНЕЕ время, а ОБЩЕЕ останется прежним.)) |
Автор: | SII [ 26 май 2010, 00:22 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Если необходимо обеспечить высокую скорость прохождения конкретной задачи, ей просто присваивается более высокий приоритет, а величина кванта определяется, исходя из приоритета. Более того, высокоприоритетные задачи могут быть вообще выведены из механизма квантования: они занимают процессор столько времени, сколько считают нужным (и снимаются только тогда, когда переходят в ожидание). В общем, всё зависит от ситуации, но обычно роль играет общая производительность системы, а не скорость выполнения отдельной задачи. |
Автор: | Mr.McD. [ 26 май 2010, 00:44 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Высокий приоритет ещё не даёт право на больший квант времени. Каждому приоритету соответствуе своя очередь к процессору. Ожидать в "очередях" освобождения ресурса(ов) можно НЕ зависимо от приоритета. Общее время - это то время, за которое все процессы (пусть даже в самой приоритетной) очереди сделают круг. А среднее время - это то, за которое процесс нарисует 8 пикселов, обработает 14 килобайт звука и посчитает пи до двухсотой степени. Так, что говоря о важности общёй производительности, Вы, наверное, имели ввиду среднюю)) А что касается отдельного приложения - увольте, но мне кажется что вся ос состоит из "отдельных" приложений, и от их средней скорости работы зависит скорость всей ос вцелом. |
Автор: | Mr.McD. [ 26 май 2010, 01:08 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
А вообще, наш с Вами спор было-бы лучше и проще решить на практике. Вот, как я себе это представляю: Взять простенькую многозадачную/многопоточную ос с открытым исх/кодом. Встроить в планировщик счётчик потоков, приходящих в очередь ожидания. Запустить НЕСКОЛЬКО "тяжёлых" процессов, которые имеют логическое завершение, способны фиксировать время своего исполнения, и способных к IPC и вводу-выводу. НЕ изменяя кванта времени, создавать ситуации взаимных исключений. И сравнивать общее время исполнения всех процессов с показаниями счётчика. Да уж, таки просто....))) |
Автор: | SII [ 26 май 2010, 01:18 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Цитата: Высокий приоритет ещё не даёт право на больший квант времени. Каждому приоритету соответствуе своя очередь к процессору. У Вас однобокое понимание механизмов работы оси. Очередь может быть одна, их может быть много -- и вовсе не обязательно по одной очереди на каждый приоритет. Размер кванта может не зависеть от приоритета, а может и зависеть. В общем, всё зависит от выбранных создателями оси алгоритмов и их реализации. А поэтому Цитата: А вообще, наш с Вами спор было-бы лучше и проще решить на практике. Вот, как я себе это представляю: Взять простенькую многозадачную/многопоточную ос с открытым исх/кодом... сей подход ничего не даст: он позволит разве что оценить кой-какие параметры конкретной оси, и не более того. Ну а ось, хорошая для одного случая, может показывать отвратительные результаты в другом случае. |
Автор: | Mr.McD. [ 26 май 2010, 01:33 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Мне кажется мы немного ушли от темы, и появляется ощущение спора-ради-спора. Возможно, в этом моя вина. И вся проблема в моей манере изложения. Поправлюсь. Алгоритмов планирования миллион! Я не пытаюсь Вас переспорить в теории диспетчеризации или в негласных правилах мутексов. Механизмы их работы мы с Вами представляем одинакого. Я не пытаюсь рушить правила синхронизации придуманые ещё во времена молодости моей бабушки. Я просто хочу сказать, что от перимены мест слоегаемых, в нашем случае, сумма меняется. И было бы очень приятно, если бы Вы попытались поняли смысл моего романса)) и мы могли продолжить обсуждение в этом направлении. Спасибо) |
Автор: | Himik [ 26 май 2010, 13:19 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Mr.McD. писал(а): Я просто хочу сказать, что от перимены мест слоегаемых, в нашем случае, сумма меняется. Формулы правильные. А в чём основной вопрос, не совсем понятно. Если в планировщике ОС правильно работает приоритетность по очерёдности и по размерам квантов, то запрограммированная многопоточная задача будет работать как надо. |
Автор: | Mr.McD. [ 26 май 2010, 14:00 ] |
Заголовок сообщения: | Re: Вопросы производительности многопоточных сред. |
Ладно. Попробую переизложить материал. * * * * * Теория. В многозадачных операционных системах процессам часто бывает необходимо взаимодействовать между собой. И для того, чтобы их взаимодействие было безопасным (не вредило системе вцелом и не зависело от особенностей организации многозадачности в данной системе), ос предоставляет необходимые механизмы. Один из таких механизмов предупреждает опасные ситуации, называемые "гонками" - ситуации исход которых, зависит от скорости взаимодействующих процессов, и результатом, как правило становится потеря данных, совместно используемых этими процессами. Этот механизм называется "механизмамом синхронизации". Далее, мы будем рассматривать один из таких механизмов, в целях моделирования ситуации. "Мутекс" - простой примитив синхронизации, который позволяет находиться в критической секции только одному процессу единовременно. Если процесс обращается, например к совместной области данных, то он захватывает мутекс, и все последующие обращения к отой области другими процессами, будут не допущены. Такие процессы блокируются операционной системой, и помещаются в очередь ожидания некоторого события (в данном случае освобождения мутекса). Но каким-бы простым не казался межанизм, его течение проходит ни совсем гладко для процесса. В часности его работа (механизма) отражается на быстродействии. Представим себе две очереди к процессору (хотя их может быть и больше). 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 процессов, при приоритетной системе планирования при обработке событий в реальном времени, и с инверсией приоритетов.(для простоты можно не учитывать вероятности взаимных блокировок) :) |
Страница 1 из 18 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |