Процесс - объект, владеющий памятью и другими ресурсами, но не выполняющий код. Поток - динамический объект, он может быть создан в процессе выполнения кода приложения и может быть удален по ходу выполнения. У процесса может быть несколько одновременно существующих потоков, выполняющих различные фрагменты кода. ОС планирует время процессоров между потоками, и для нее не имеет значение, какому процессу принадлежит тот или иной поток. Говоря о потоках в операционной системе, будем рассматривать общую схему, опуская многие детали, основываясь на стратегии распределения процессорного времени, характерной для ОС Windows. Эта стратегия носит название "вытесняющая приоритетная многозадачность". Многозадачность в данном контексте означает, что планировщик ОС, распределяет время процессора между многими потоками, присутствующими в ОС.
Приоритетность означает, что потоки могут иметь разные приоритеты. В этом случае из двух потоков, готовых к выполнению, на выполнение будет выбран тот, у кого больше приоритет. Более того, если в процессе выполнения потока появился готовый к выполнению поток с большим приоритетом, то выполнение текущего потока будет приостановлено, даже если не истек отведенный ему квант времени. Когда на дороге появляется президентский кортеж, то все участники дорожного движения останавливаются и ждут, пока кортеж не проедет. Все потоки распределяются по группам приоритетности, потоки из одной группы могут быть выбраны на выполнение только в том случае, если нет готовых к выполнению потоков в группах с высшей приоритетностью.
Значит ли это, что могут быть "обиженные" приложения с низким приоритетом, до выполнения которых никогда не дойдет очередь? Это не так. ОС старается никого не обидеть. Если некоторое приложение долго не выполнялось, то ОС временно повышает его приоритет, так что и оно начнет выполняться.
Вытесняющая многозадачность характеризует стратегию планирования для потоков с одинаковым приоритетом. Все потоки в одной группе выстраиваются в очередь. Каждому из них в соответствии с очередью отводится на выполнение некоторый квант времени процессора. По истечении этого кванта поток переводится в состояние "готовность" независимо от его желания продолжить работу, и в состояние "выполнение" переводится следующий по очереди поток. Эту стратегию иногда называют "каруселью". Карусель сделала несколько оборотов, остановилась, все выходят, и места занимают следующие желающие прокатиться, ожидающие с нетерпением своей очереди.
На Рис. 2.1 показаны возможные состояния потока и переходы из одного состояния в другое.
Рис. 2.1.Состояния потока и переходы между ними
После создания потока и должной инициализации поток переходит в состояние "готовность", занимая в своей группе приоритетности место в конце очереди". Планировщик ОС в соответствии с описанной стратегией выбирает поток, переводя его в состояние "выполнение". По истечении отведенного кванта времени поток возвращается в состояние "готовность", становясь в хвост очереди в своей группе приоритетности. Из состояния "выполнение" поток может перейти в другие состояния и до завершения отведенного кванта времени. В состояние "готовность" он может перейти, если появился поток с большим приоритетом. В состояние "завершение" поток переходит, выполнив свою работу, завершив выполнение отведенного ему фрагмента кода. В состояние "ожидание" поток может перейти, если его дальнейшее выполнение возможно только после наступления некоторого события (например, ему требуются данные, а устройство компьютера, выполняющее ввод этих данных, еще не завершило свою работу). Из состояния "ожидание" поток может перейти в состояние "готовность", если наступило событие, ожидаемое потоком. За время жизни потока он многократно проходит цикл {готовность} -> {выполнение} -> {ожидание} -> {готовность}, иногда минуя переход в состояние "ожидания".
Для понимания картины в целом нужно помнить, что весь процесс вычислений на компьютере управляется событиями. Каждый поток во время своего выполнения многократно прерывается, уступая свое место другому потоку. События, приводящие к приостановке выполнения потока, могут быть асинхронными по отношению к его работе, - они могут произойти в любой момент выполнения потока. Такие события называются прерываниями. Синхронные события, связанные с тем, что по тем или иным причинам выполнение потока становится невозможным, называются исключениями или исключительными ситуациями. Типичными примерами исключительных ситуаций являются такие ситуации, как попытка деления целого числа на ноль или попытка чтения записи несуществующего файла.
Прерывания инициируются аппаратурой компьютера, чаще всего таймером и устройствами ввода-вывода. ОС в очень коротком цикле рассматривает все возникшие прерывания и должным образом их обрабатывает. Когда возникает прерывание от таймера, то ОС при его обработке из кванта времени, отводимого выполняемому потоку, вычитает время, равное интервалу таймера. Если отводимое потоку время исчерпано, поток снимается с выполнения, переходя в состояние "готовность". Когда устройство ввода заканчивает выполнение очередного задания, оно инициализирует аппаратное прерывание, свидетельствующее о завершении работы. Обрабатывая это прерывание, ОС может перевести некоторый поток из состояния "ожидания" в состояние "готовности", поскольку выполнена его заявка на ввод данных.
У исключений, связанных с самим потоком, более широкий спектр. Потоку, например, может понадобиться ввод внешних данных. Поток не может непосредственно обратиться к устройству ввода. Устройство одно, а потоков много. Поэтому поток вызывает соответствующий системный сервис. С точки зрения ядра ОС возникло исключение. При его обработке поток переводится в режим "ожидания", и начинает работать поток, содержащий соответствующий сервис, который анализирует загруженность устройства, формирует новую заявку для устройства, ставя ее в очередь.
Причина исключения может быть как аппаратной, так и программной. Деление на ноль, это, конечно же, программная ошибка. Исключения, связанные с тем, что не прочитаны требуемые внешние данные, могут быть связаны как со сбоем аппаратуры, так и с неверно заданными адресами в программе. Если письмо не доставлено, то виноватой может быть почтовая служба, а возможно вы послали письмо "на деревню дедушке".
Поток может сам инициировать исключение, уведомляя, например, ОС о том, что он "засыпает" на некоторое фиксированное время. Обрабатывая это прерывание, ОС переводит поток в состояние "ожидание". При обработке одного из очередных прерываний по таймеру, когда завершается время "сна", указанное потоком, поток переводится из состояния "ожидание" в состояние "готовность". Поток может перейти в состояние "ожидание" и по другим причинам, возникающим в ходе выполнения программного кода, например, ожидая завершения работы другого потока. Примеры того, как всем этим может управлять С# программист, будут рассмотрены позднее.
Современные компьютеры, настольные и портативные имеют несколько процессоров. Практически все продающиеся сегодня компьютеры, предназначенные для индивидуального использования, имеют от двух до четырех ядер. Это позволяет организовать параллельное выполнение фрагментов кода в одном приложении, ускоряя его работу. Для этого в приложении создаются несколько потоков, параллельно работающих, каждый в отдельном ядре процессора. Иногда удается при N ядрах примерно в N раз уменьшить общее время работы приложения. Но, конечно, это возможно не для всякого приложения, а если и возможно, то требует усилий со стороны программиста. Многопоточный параллельный алгоритм сложнее однопоточного последовательного алгоритма. Сложнее становится и отладка. Нужны ли программисту дополнительные сложности? Хотим мы того или нет, но параллельное программирование становится одним из важнейших направлений развития современного программирования. Современные суперкомпьютеры имеют сотни тысяч процессоров. Высокопроизводительные вычисления, требующие распараллеливания алгоритмов, становятся реальностью. Использовать многоядерный компьютер только для последовательных алгоритмов неэффективно, - все равно, что использовать телескоп в качестве лупы для чтения убористого текста.
Конечно, ведутся работы по автоматическому распараллеливанию последовательного алгоритма, ориентированного на выполнение одним процессором. Но возможности здесь ограничены. В большинстве случаев самому программисту приходится разрабатывать параллельный алгоритм своей задачи, позволяющий эффективно использовать возможности современных компьютеров. Новая техника со многими процессорами требует новых программ со многими потоками, новых программ для кластеров и суперкомпьютеров.
Операционная система работает с процессами и потоками и ей необходимо хранить информацию об этих объектах. Каждый процесс хранит код приложения и данные, создаваемые в процессе выполнения приложения. С данными работает поток, выполняя программный код. Эти данные могут быть локальными для потока, созданы в потоке и используются только одним потоком. Но у процесса может быть несколько потоков, в этом случае существуют данные процесса, глобальные для потока, обеспечивающие взаимодействие между потоками.
Когда потоки процесса работают последовательно, например в случае одного процессора, то особых проблем не возникает, поскольку не возникают конфликты при выполнении операций чтения и записи. Тем не менее, при работе с глобальными данными программисту приходится быть крайне аккуратным, убеждаясь, что изменение данных в одном потоке не вредит работе с этими данными в другом потоке. Сложнее ситуация, когда потоки работают параллельно. В этом случае возможны конфликты, например, два потока одновременно пытаются изменить одни и те же данные. В этом случае большое внимание приходится уделять средствам синхронизации потоков при работе с данными. О синхронизации, гонке данных, блокировках и клинчах вкратце говорилось в первой главе. Примеры появятся в последующих главах.
Еще одна проблема с данными состоит в том, что поток может в любой момент быть прерванным, перейти в состояние "ожидание" или "готовность", а потом вновь продолжить свою работу в прерванной точке. Для поддержки такой возможности ОС использует объект, называемый контекстом потока. Он включает локальные данные потока, счетчик, указывающий на команду, с которой необходимо начать прерванное выполнение, другую служебную информацию, необходимую для корректного продолжения прерванной работы.
Есть еще одна проблема, связанная с данными, используемыми потоком. Дело в том, что команды процессора делятся на две группы - команды, выполняемые в привилегированном режиме, и команды, выполняемые в пользовательском режиме. Команды в привилегированном режиме могут выполнять только системные программы, составляющие ядро операционной системы. Эти системные сервисы могут вызываться потоком по ходу выполнения программного кода. Данные о потоке, используемые ядром ОС, хранятся отдельно от данных, используемых в пользовательском режиме.
В адресном пространстве ОС для каждого процесса в момент его создания выделяется специальный блок памяти, называемый EPROCESS, хранящий системную информацию о процессе. Еще один блок с системной информацией - PEB (Process Environment Block) хранится в адресном пространстве самого процесса. В страницах виртуального адресного пространства процесса хранится код приложения и данные, необходимые для работы. Данные хранятся в памяти, называемой стеком (stack) и кучей (heap). Куча создается в момент создания процесса. У процесса может быть несколько куч. Код приложения может храниться частично в закрытых страницах, частично разделяемых страни
цах памяти. Разделяемые страницы двух или более процессов могут отображаться на одни и те же страницы реальной оперативной памяти. За счет этого несколько процессов могут использовать один и тот же программный код в оперативной памяти. Разные приложения могут использовать одну и ту же библиотеку классов - DLL, расположенную в оперативной памяти без дублирования. Понятно, что это не касается данных, данные у каждого процесса свои. Для хранения данных процесса операционная система выделяет защищенные страницы, так что никакой процесс не может получить доступ к данным другого процесса. Есть исключение из этого правила, когда организуется взаимодействие между процессами, но эту ситуацию мы рассматривать не будем.
В адресном пространстве ОС для каждого потока в момент его создания выделяется специальный блок памяти, называемый TPROCESS, хранящий системную информацию о потоке, а в адресном пространстве процесса создается блок с системной информацией - TEB (Thread Environment Block). Для каждого потока создается контекст потока. Уже говорилось, что в ходе работы процессора компьютера с большой частотой происходит смена потоков - пользовательских и системных. Процессор прекращает выполнять один поток и начинает выполнять другой поток. Процесс переключения называется переключением контекстов. Понятно, что, если в любой момент выполнение потока может быть прервано, а затем продолжено через некоторое время, то контекст потока должен содержать всю информацию, необходимую для продолжения вычислений в точке прерывания. Поэтому контекст потока включает все локальные данные потока, адрес команды в программном коде, с которой продолжится вычисление, состояние всех системных регистров в момент прерывания, состояния всех файлов, с которыми работал поток.
Кроме локальных данных поток работает с данными, общими для приложения в целом. Всем потокам одного процесса, доступны общие данные. При параллельной работе потоков возникает необходимость в синхронизации работы потоков для обеспечения корректной работы с данными. Ответственность за корректную работу потоков лежит на программисте. Дальнейшая часть этой главы и будет посвящена вопросам работы с потоками в программах на C#.
Под циклом будем понимать цикл типа while, рассматривая цикл типа for как частный случай. Будем также полагать, что с каждым циклом связана предшествующая ему некоторая инициализирующая часть Init, содержащая группу операторов. Инициализациянеобходима для обеспечения корректной работы цикла, после ее завершения должно выполняться предусловие цикла и стать истинным инвариант цикла.
С каждым циклом связывается одна или несколько переменных, называемых параметрами цикла, изменяющих свое значение при каждом выполнении тела цикла. В цикле for изменение параметров цикла осуществляется в заголовке цикла. В цикле whileизменение параметров цикла выполняется явно в теле цикла.
Для простоты будем полагать, что тело цикла может содержать только операторы присваивания, условные операторы, составныеоператоры и операторы цикла. Мы полагаем, что цикл не содержит операторов вызова процедур и вызова функций с побочным эффектом.
Обозначим через V - множество переменных цикла. Сюда входят все переменные, встречающиеся в теле цикла, и параметры цикла, заданные в заголовке цикла for. Множество V представим как два непересекающихся подмножества:
В множество входят переменные, которые могут изменять свое значение в ходе выполнения тела цикла. В это множество входят, например, параметры цикла. В множество входят переменные, которые сохраняют постоянное значение на всех итерациях в ходе выполнения цикла.
Аналогично обозначим через E - множество выражений, встречающихся в цикле. Множество E представим как два непересекающихся подмножества:
В множество входят выражения, которые содержат только константы и переменные из . Независимо от итерации, на которой вычисляется значение этих выражений, результат вычислений будет один и тот же.
Время выполнения каждой программы определяется двумя используемыми в ней механизмами - циклами и рекурсией. Программа без циклов и рекурсивных вызовов на современных компьютерах будет выполняться практически мгновенно. Тема рекурсии останется вне нашего рассмотрения, нас будут интересовать программы с циклами.
Если программа работает недопустимо медленно, то возникает вопрос, как ускорить ее выполнение? Основным приемом является выбор эффективного алгоритма, дающего решение исходной задачи. Классическим примером может служить задача сортировки массивов. Если необходимо сортировать большое число массивов с малым числом элементов, то вполне допустимы простые методы сортировки со сложностью . Когда n велико, такие методы становятся неэффективными, и следует применять методы со сложностью . Если элементы сортируемого массива принадлежат небольшому числу классов (двум - четырем классам), то следует применять методы, имеющие сложность O(n). Примером может служить массив персон, который нужно отсортировать по полу, разделив мужчин и женщин. Другим примером является сортировка новых учеников школы Хогвартс из романа о Гарри Поттере, где сортирующая шляпа делила учеников в зависимости от их свойств на четыре класса. Такую сортировку можно выполнить за линейное время.
Выбор наилучшего алгоритма определяется не только задачей, но и архитектурой компьютера, на котором эта задача будет решаться.Алгоритм должен наилучшим образом использовать ресурсы компьютера. Алгоритм, наилучший для компьютера с одним процессором, может быть далеко не лучшим на компьютере с множеством процессоров, поскольку не будет использовать возможности распараллеливания вычислений. Распараллеливание вычислений во многом определяется возможностью распараллеливания циклов, что и будет основной темой рассмотрения в данной главе. Но прежде давайте рассмотрим более простую тему, также связанную с циклами, и имеющую ту же цель - ускорить выполнение циклов нашей программы.
..Чистка цикла
Под чисткой цикла понимается избавление тела цикла от тех вычислений, которые можно выполнить один раз в инициализирующей части цикла, сохраняя эквивалентность результата выполнения цикла. Чистку цикла сведем к чистке выражений и чистке операторов цикла
Рассмотрим вначале чистку выражений. Пусть expr - некоторое выражение из Е, встречающееся в теле цикла, и subexpr - некоторое его подвыражение. Если подвыражение subexpr принадлежит множеству , то выражение expr можно упростить. Для этого достаточно определить в Init локальную переменную loc, тип которой совпадает с типом subexpr, задать оператор присваивания loc = subexpr, затем заменить в выражении expr подвыражение subexpr переменной loc. Эту замену можно осуществить во всех вхождениях subexpr, встречающихся в выражениях из Е. Предполагается, конечно, что такая замена корректна, - subexpr не содержит вызовов функций с побочным эффектом и вхождение в expr таково, что замена subexpr на (loc) не меняет значения выражения expr.
Заметьте, что замена подвыражений локальными переменными является весьма полезным приемом, даже в тех случаях, когда вычисление подвыражения невозможно вынести из цикла. Упрощение выражений облегчает отладку, повышает надежность программы, а при наличии нескольких вхождений позволяет ускорить вычисление выражения.
Рассмотрим теперь чистку операторов. Оператор stat может быть вынесен из тела цикла и включен в конец инициализирующей части Init при условии, что все переменные этого оператора принадлежат множеству и все выражения принадлежат множеству . Заметьте, наше определение множества не исключает включения в него переменных, входящих в левые части операторов присваивания и, следовательно, получающих значения в теле цикла. Но на такие переменные накладываются дополнительные условия. Во-первых, получаемые ими значения должны быть результатом вычисления выражений из множества . Во-вторых, эти переменные используются в выражениях только после получения ими значений в результате присваивания.
Хороший оптимизирующий компилятор может выполнять чистку цикла. Мой анализ показал, что этого нельзя сказать как о компиляторе C#, включенном в состав Visual Studio 2010, так и о JIT компиляторе, входящем в состав Framework .Net 4.0.
Вот простой пример, демонстрирующий отсутствие автоматической чистки цикла компиляторами в C# программах:
static void Main(string[] args)
{
double a1 = 0.5, a2 = 0.1, a3 = -1.5;
double x = 2.0, y = 0;
int n = 100000;
DateTime start, finish;
start = DateTime.Now;
for (int i = 0; i < n; i++)
{
y = (1 + 2*(a1* Math.Pow(x, 3) +
a2 * Math.Pow(x, 2) + a3 * Math.Pow(x, 3)) -
5 * (a1* Math.Pow(x, 3) +
a2 * Math.Pow(x, 2) + a3 * Math.Pow(x, 3)) +
3 * (a1* Math.Pow(x, 3) +
a2 * Math.Pow(x, 2) + a3 * Math.Pow(x, 3))) /
(Math.Sin(a1* Math.Pow(x, 3) +
a2 * Math.Pow(x, 2) + a3 * Math.Pow(x, 3)) *
Math.Sin(a1* Math.Pow(x, 3) +
a2 * Math.Pow(x, 2) + a3 * Math.Pow(x, 3)) +
Math.Cos(a1* Math.Pow(x, 3) +
a2 * Math.Pow(x, 2) + a3 * Math.Pow(x, 3)) *
Math.Cos(a1* Math.Pow(x, 3) +
a2 * Math.Pow(x, 2) + a3 * Math.Pow(x, 3)));
}
finish = DateTime.Now;
Console.WriteLine(" y = " + y);
Console.WriteLine("Время вычислений в тиках = " +
(finish.Ticks - start.Ticks));
}
Нетрудно видеть, что для рассматриваемого цикла все переменные, кроме параметра цикла, принадлежат множеству , а все выражения принадлежат множеству . В цикле многократно встречается подвыражение, принадлежащее , так что его вычисление можно вынести из тела цикла. Более того, сам оператор присваивания можно также вынести из тела цикла в инициализирующую часть, после чего тело цикла не будет содержать операторов, так что хороший оптимизирующий компилятор может удалить оператор цикла. Продолжая оптимизацию, можно заметить, что оператор присваивания можно заменить эквивалентным оператором
y = 1;
Однако ничего подобного не происходит. Если проанализировать IL код, построенный компилятором C# для версии Release с включенным флажком оптимизации кода, то можно видеть, что построенный код содержит несколько сотен ячеек и многократно выполняет одни и те же действия. Вот некоторый фрагмент этого кода:
К сожалению, оптимизацию этого кода не выполняет и JIT компилятор, работающий на заключительном этапе. Приведу время, затраченное на выполнение программы:
Таблица 3.1. Время вычислений как функция от длины цикла
n
10 000
100 000
1 000 000
T (тиках)
410 023
4 340 249
38 422 197
Как видите, эта простая программа, которая в результате правильной оптимизации сводится к присвоению переменной некоторой константы и должна выполняться мгновенно, занимает неоправданно много ресурсов компьютера, как памяти, так и времени работы процессора. К сожалению, приходится еще раз констатировать, подобную оптимизацию должен выполнять сам программист, поскольку существующий компилятор с ней не справляется.
..Распараллеливание цикла
Цикл допускает распараллеливание, если множество процессоров компьютера, одновременно выполняя тело цикла для всех значений его параметров, дают результат, эквивалентный результату, полученному при последовательном выполнении цикла одним процессором. В этом случае говорят, что итерации цикла независимы. Так что цикл допускает распараллеливание, если итерации цикла независимы. Если цикл может быть распараллелен, то при наличии нескольких процессоров появляется потенциальная возможность ускорить выполнение алгоритма за счет того, что процессоры будут выполнять тело цикла параллельно.
Приведенное выше определение распараллеливания неконструктивно. Условия, при выполнении которых цикл может быть распараллелен, достаточно сложны. Мы ограничимся рассмотрением примеров, для каждого из которых будем пояснять, почему тот или иной цикл может или не может быть распараллелен.
Цикл допускает распараллеливание, если множество процессоров компьютера, одновременно выполняя Потоки операционной системы Windows - это низкоуровневый механизм, позволяющий операционной системе реализовать параллельные вычисления. Благодаря потокам, ОС организует как мультипрограммную работу - одновременное выполнение нескольких программ, так и параллельные вычисления - одновременное выполнение нескольких фрагментов кода одной и той же программы. Подробнее об этом уже говорилось во "Процессы и потоки в операционной системе" .
В "Параллельные алгоритмы" , где рассматривались алгоритмы и возможности распараллеливания вычислений, отмечалось, что не всякий алгоритм допускает возможность его параллельного вычисления. Алгоритмы, допускающие распараллеливание, являются, как правило, более сложными, чем последовательные алгоритмы. Но даже в том случае, когда алгоритм потенциально допускаетраспараллеливание вычислений, реализация этой потенциальной возможности является непростой задачей для программиста.
Параллельные вычисления являются важной ветвью современного программирования. Уже созданы и продолжают появляться средства высокого уровня абстракции, облегчающие тяжелую работу программиста, разрабатывающего параллельные программы. В данной главе мы рассмотрим ряд средств, позволяющих создавать на языке C# параллельные программы, которые на многоядерном компьютере выполняются эффективнее (быстрее), чем на одноядерном компьютере. Наше рассмотрение начнется с класса Thread, в котором потоки представлены объектами этого класса.
входят переменные, которые могут изменять свое значение в ходе выполнения тела цикла. В это множество входят, например, параметры цикла. В множество 
входят переменные, которые сохраняют постоянное значение на всех итерациях в ходе выполнения цикла.
входят выражения, которые содержат только константы и переменные из 
. Когда n велико, такие методы становятся неэффективными, и следует применять методы со сложностью 
. Если элементы сортируемого массива принадлежат небольшому числу классов (двум - четырем классам), то следует применять методы, имеющие сложность O(n). Примером может служить массив персон, который нужно отсортировать по полу, разделив мужчин и женщин. Другим примером является сортировка новых учеников школы Хогвартс из романа о Гарри Поттере, где сортирующая шляпа делила учеников в зависимости от их свойств на четыре класса. Такую сортировку можно выполнить за линейное время.