среда, 23 марта 2016 г.

Полезна ли параллельность?

В каких случаях параллельность исполнения процессов или обслуживания запросов реально может помешать?

Рассмотрим парадокс параллельности обслуживания в разрезе вопроса "А действительно ли это выгодно?". Сравним две ситуации - обслуживание параллельное и обслуживание последовательное.

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

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

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

Пусть выполнение одного запроса на процессоре в монопольном режиме занимает одну единицу времени. В параллельном случае общая мощность процессора распределяется между N запросами и каждый процесс закончит выполнение когда отработает N единиц времени. В итоге получаем что N процессов суммарно ждали (каждый) N единиц времени, итого N*N единиц времени ожидания.

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

В этом случае первый процесс ждет ответа 1 единицу времени, второй ждет пока выполнится первый и свою единицу времени, значит ждет 2 единицы времени, и так далее. N-й процесс ждет результата N единиц времени. В итоге получаем что N процессов суммарно ждут

1 + 2 + 3 + 4 + ... + (N-1) + N = N*(N+1)/2

единиц времени.

Если построить график ожидания, по горизонтали - номер процесса, по вертикали - время ожидания, то в случае параллельного исполнения график всегда будет прямоугольником, а в случае последовательного исполнения - график ломаной, которая стремится к треугольнику при увеличении числа процессов. И площадь графика (интегральное время) стремится к половине площади прямоугольника.

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

Казалось бы, зачем тогда переводить операционные системы с однозадачных и пакетных режимов на многозадачные с вытеснением? По своему опыту скажу, что тот компьютер который у меня был раньше (386-DX-40) под Windows 3.1 по производительности был во многом практичнее чем гораздо более навороченный Pentium-90 под Windows NT. Также существенно, что памяти на обеих машинах было несравнимое количество, трешка лихо летала на восьми мегах. А под NT памяти требовалось в разы больше. Чтобы выполнить то же самое.

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

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

Реально же производительность системы параллельного исполнения можно повысить, если перейти к последовательному исполнению. Полностью переходить даже не обязательно, поскольку последовательное-параллельное - это не черное и белое, и можно организовать множество промежуточных оттенков. В частности, одним из решений является присуждение процессу некоего класса исполнения. Если класс выше - то квант времени ему отводить намного больше чем другим. При этом первыми отстрелятся процессы из группы высокого класса, затем остальные, по мере понижения класса. Либо предоставлять процессор только процессам одного класса, затем другого и так далее. При том, что в итоге процессы нижнего класса не ждут больше чем раньше, но часть процессов выполнится намного быстрее.

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

Риторический вопрос - можно ли внедрить изменение классов обслуживания в реальную систему? Например если есть система рассчетов, отвечающая на запросы и к ней обращаются N пользователей. Теоретически программисты могут повысить общую интегральную производительность в два раза. Просто введя неравенство пользователей. А для некоторых пользователей - и в разы.

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

И, главное, не говорить людям, что некоторые из них в какой-то момент времени стали равнее других ;-))

Комментариев нет:

Отправить комментарий