Многопоточное программирование это процесс в котором

Вступительные испытания в магистратуру / 09.04.01 / Ответы на экзамен / МАГИСТРАТУРА 2017 / Voprosy_po_faylam / 24. Многопоточное программирование. Процесс и потомок выполнения. Средства синхронизации потоков

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

Процесс — это совокупность кода и данных, разделяющих общее виртуальное адресное пространство. Чаще всего одна программа состоит из одного процесса, но бывают и исключения (например, браузер Chrome создает отдельный процесс для каждой вкладки, что дает ему некоторые преимущества, вроде независимости вкладок друг от друга). Процессы изолированы друг от друга, поэтому прямой доступ к памяти чужого процесса невозможен (взаимодействие между процессами осуществляется с помощью специальных средств).

Для каждого процесса ОС создает так называемое «виртуальное адресное пространство», к которому процесс имеет прямой доступ. Это пространство принадлежит процессу, содержит только его данные и находится в полном его распоряжении. Операционная система же отвечает за то, как виртуальное пространство процесса проецируется на физическую память.

Многопоточный режим работы открывает новые возможности для программистов, однако за эти возможности приходится расплачиваться усложнением процесса проектирования приложения и отладки. Основная трудность, с которой сталкиваются программисты, никогда не создававшие ранее многопоточные приложения, это синхронизация одновременно работающих потоков. Для чего и когда она нужна? Однопоточная программа, такая, например, как программа MS-DOS, при запуске получает в монопольное распоряжение все ресурсы компьютера. Так как в однопоточной системе существует только один процесс, он использует эти ресурсы в той последовательности, которая соответствует логике работы программы. Процессы и потоки, работающие одновременно в многопоточной системе, могут пытаться обращаться одновременно к одним и тем же ресурсам, что может привести к неправильной работе приложений.

До появления средств многопоточного (multithreaded — MT) программирования выполнение компьютерных программ состояло из единой последовательности шагов, которые выполнялись процессором компьютера от начала до конца, т.е. синхронно. Такая организация выполнения применялась независимо от того, требовала ли сама задача последовательного упорядочения шагов или допускала разбиение на подзадачи и отдельное их выполнение в программе. В последнем случае подзадачи вообще могли быть независимыми, не связанными никакими причинно-следственными отношениями (а это означает, что результаты одних подзадач не влияют на выполнение других подзадач). Из этого следует вывод, что такие независимые задачи могут выполняться не последовательно, а одновременно. Подобная параллельная организация работы позволяет существенно повысить эффективность решения всей задачи. Изложенные выше соображения лежат в основе многопоточного программирования. Многопоточное программирование идеально подходит для решения задач, асинхронных по своему характеру (т.е. допускающих прерывание работы), требующих выполнения нескольких параллельных действий, в которых реализация каждого действия может быть недетерминированной, иными словами, происходящей в случайные и непредсказуемые моменты времени. Такие задачи программирования могут быть организованы в виде нескольких потоков выполнения или разделены на несколько потоков, в каждом из которых осуществляется конкретная подзадача. В зависимости от приложения в этих подзадачах могут вычисляться промежуточные результаты для последующего слияния и формирования заключительной части вывода.

Компьютерные программы — это просто исполняемые объекты в двоичной (или другой) форме, которые находятся на диске. Программы начинают действовать лишь после их загрузки в память и вызова операционной системой. Процесс — это программа в ходе ее выполнения (в такой форме процессы иногда называют тяжеловесными процессами). Каждый процесс имеет собственное адресное пространство, память и стек данных, а также может использовать другие вспомогательные данные для контроля над выполнением. Операционная система управляет выполнением всех процессов в системе, выделяя каждому процессу процессорное время по определенному принципу. В ходе выполнения процесса может также происходить ветвление или порождение новых процессов для осуществления других задач, но каждый новый процесс имеет собственную память, стек данных и т.д. Вообще говоря, отдельные процессы не могут иметь доступ к общей информации, если не реализовано межпроцессное взаимодействие (interprocess communication — IPC) в той или иной форме.

Потоки (иногда называемые легковесными процессами) подобны процессам, за исключением того, что все они выполняются в пределах одного и того же процесса, следовательно, используют один и тот же контекст. Потоки можно рассматривать как своего рода “мини-процессы”, работающие параллельно в рамках основного процесса или основного потока. Поток запускается, проходит определенную последовательность выполнения и завершается. В потоке ведется указатель команд, позволяющий следить за тем, где в настоящее время происходит его выполнение в текущем контексте. Поток может быть прерван и переведен на время в состояние ожидания (это состояние принято также называть приостановкой (sleeping)), в то время как другие потоки продолжают работать. Такая операция называется возвратом управления (yielding). Все потоки, организованные в одном процессе, используют общее пространство данных с основным потоком, поэтому могут обмениваться информацией или взаимодействовать друг с другом с меньшими сложностями по сравнению с отдельными процессами. Потоки, как правило, выполняются параллельно. Именно распараллеливание и совместное использование данных становятся предпосылками обеспечения координации выполнения нескольких задач. Вполне естественно, что в системе с одним процессором невозможно в полном смысле слова организовать параллельное выполнение, поэтому планирование потоков происходит таким образом, чтобы каждый из них выполнялся в течение какого-то короткого промежутка времени, а затем возвращал управление другим потокам (образно говоря, снова становился в очередь на получение следующей порции процессорного времени). В ходе выполнения всего процесса каждый поток осуществляет свои собственные, отдельные задачи и передает полученные результаты другим потокам по мере необходимости.

Многопоточное программирование

В отличие от многих других языков программирования, Java предлагает встроенную поддержку многопоточного программирования. Многопоточная программа содержит две или более частей, которые могут выполняться одновременно. Каждая часть такой программы называется потоком (thread), и каждый поток задает отдельный путь выполнения. То есть, многопоточность — это специализированная форма многозадачности.

Вы почти наверняка знакомы с многозадачностью, поскольку она поддерживается практически всеми современными операционными системами. Однако существуют два отдельных типа многозадачности: многозадачность, основанная на процессах, и многозадачность, основанная на потоках. Важно понимать разницу между ними. Большинству читателей многозадачность, основанная на процессах, является более знакомой формой. Процесс по сути своей — это выполняющаяся программа. То есть многозадачность, основанная на процессах, представляет собой средство, которое позволяет вашему компьютеру одновременно выполнять две или более программ. Так, например, процессная многозадачность позволяет запускать компилятор Java в то самое время, когда вы используете текстовый редактор. В многозадачности, основанной на процессах, программа представляет собой наименьший элемент кода, которым может управлять планировщик операционной системы.

В среде поточной многозадачности наименьшим элементом управляемого кода является поток. Это означает, что одна программа может выполнять две или более задач одновременно. Например, текстовый редактор может форматировать текст в то же время, когда выполняется его печать — до тех пор, пока эти два действия выполняются двумя отдельными потоками. То есть многозадачность на основе процессов имеет дело с «картиной в целом», а потоковая многозадачность справляется с деталями.

Многозадачные потоки требуют меньше накладных расходов, чем многозадачные процессы. Процессы — это тяжеловесные задачи, каждая из которых требует своего собственного адресного пространства. Межпроцессные коммуникации дорогостоящи и ограничены. Переключение контекста от одного процесса к другому также обходится дорого. С другой стороны, потоки являются облегченными. Они разделяют одно и тоже адресное пространство и совместно используют один и тот же тяжеловесный процесс.

Коммуникации между потоками являются экономными, а переключения контекста между потоками характеризуется низкой стоимостью. Хотя Java-программы используются в средах процессной многозадачности, многозадачность, основанная на процессах, средствами Java не управляется. А вот многопоточная многозадачность средствами Java управляется.

Многопоточность позволяет вам писать очень эффективные программы, которые по максимуму используют центральный процессор, поскольку время ожидания может быть сведено к минимуму. Это особенно важно для интерактивных сетевых сред, в которых работает Java, так как в них наличие ожидания и простоев — обычное явление. Например, скорость передачи данных по сети намного ниже, чем скорость, с которой компьютер может их обрабатывать. Даже ресурсы локальной файловой системы читаются и пишутся намного медленнее, чем темп их обработки в процессоре. И, конечно, ввод пользователя намного медленнее, чем компьютер. В однопоточных средах ваша программа вынуждена ожидать окончания таких задач, прежде чем переходить к следующей — даже если центральный процессор большую часть времени простаивает. Многопоточность позволяет получить доступ к этому времени ожидания и использовать его рациональным образом.

Если вы программировали для таких операционных систем, как Windows, это значит, что вы уже знакомы с многопоточным программированием. Однако тот факт, что Java управляет потоками, делает многопоточность особенно удобной, поскольку многие детали подконтрольны вам как программисту.

Другой взгляд на многопоточность

Вот уже в который раз хочется поднять тему многопоточного программирования. Сейчас я попытаюсь донести мысль, что если посмотреть на эту тему под другим — более простым, как мне кажется, углом, то она не будет казаться такой сложной и неприступной для начинающих. В этой статье будет минимум формализма и известных (и не очень) терминов.

Откуда ноги растут

В начале 2000-х годов наблюдалось замедление скорости роста производительности процессоров. К 2005 году увеличение тактовой частоты процессора практически остановилось. Сейчас мы можем вспомнить 2010 год и выход Intel Core i5—680 с тактовой частотой 3,60 ГГц. Прошло десять лет и сейчас можно приобрести Intel Core i9-10850K с частотой от 3,60 до 5,20 ГГц. Разница, как можно заметить, невелика. Этот пример очень синтетический и примитивный, но он наглядно показывает скорость и направление развития современных процессоров. Конечно, производительность процессора зависит не только от тактовой частоты, а еще и от других параметров — размера и количества кэшей, частоты шины, типа сокета и так далее. И зачастую, особенно на боевых машинах, оказывается, что выгоднее взять процессор с более низкой тактовой частотой.

Что делать?

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

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

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

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

Поток

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

Пусть ядро — это станок на заводе, тогда поток — это рабочий, который за ним работает. У каждого рабочего есть набор задач, которые он должен выполнить — это исходный код. Пока что будем считать, что исходный код исполняется по порядку, это значит, что операция 1 гарантировано выполнится до операции 2, операция 2 до операции 3 и так далее.

int a = 0 // операция 1, выполнится самая первая int b = 0 // операция 2, выполнится после операции 1 a = a + b // операция 3, выполнится после операций 1 и 2 b = a + a // операция 4, выполнится после всех операций

Давайте попробуем решить простую задачу. Какие варианты пар (a, b) возможны после завершения исполнения обоих потоков, положитесь на свою интуицию, стоит рассмотреть даже самые, казалось бы, невозможные варианты:

Ответ

1. Пусть поток 1 выполнился полностью, а поток 2 еще не стартовал. Тогда в результате будет пара (0, 1)
2. Аналогично, поток 2 выполнился полностью, а поток 1 еще не стартовал. Тогда в результате будет пара (1, 0).
3. Во всех остальных случаях (0, 0)
4. Случая (1, 1) быть не может, так как хотя бы один поток перед своим завершением обнулит какую-то переменную.

В итоге получается [ (0, 1), (1, 0), (0, 0) ]

Как вы могли догадаться, понимание результата работы многопоточного кода сводится к рассмотрению всех вариантов его исполнения. В данном случае формально такая модель исполнения называется моделью последовательной консистентности (sequential consistency, SC).

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

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

Ответ

Всего существует 6 вариантов исполнения. 1 — 4 варианты дадут результат (1, 1), 5 вариант даст результат (0, 1), 6 вариант даст результат (1, 0).

Многопоточность была бы простой если бы все закончилось здесь.

Конец?

К сожалению, или к счастью, это еще не конец. На процессорах самых популярных архитектур — x86, Arm, Power PC и Alpha, исполнение предложенного выше примера может быть другим — возможен результат (0, 0).

#include #include int x, y, a, b; void* thread1(void* unused) < x = 1; a = y; return NULL; >void* thread2(void* unused) < y = 1; b = x; return NULL; >int main() < int i = 0; while (1) < x = 0; y = 0; a = 0; b = 0; pthread_t tid1; pthread_attr_t attr1; pthread_t tid2; pthread_attr_t attr2; pthread_attr_init(&attr1); pthread_attr_init(&attr2); pthread_create(&tid1, &attr1, thread1, NULL); pthread_create(&tid2, &attr2, thread2, NULL); pthread_join(tid1, NULL); pthread_join(tid2, NULL); i++; if(a == 0 && b == 0) < break; >> printf("Iterations: %d\n", i); return 0; > 

Код на языке C рано или поздно завершается, хотя в модели SC не должен.

Это не вписывается в модель SC (sequential consistency), поскольку не существует такого исполнения, которое бы привело к результату (0, 0). Выше мы допустили, что «операции с памятью выполняются сразу и без каких-либо задержек». Но для современных процессоров это совсем не так.

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

Сейчас мы разберем (в качестве модели) архитектуру x86.

Кэш для чтения, буфер записи (англ. Store Buffer) для записи — все просто.

1. Процессор всегда читает из кэша
2. Если в кэше такого адреса не найдено, процессор идет в память и копирует его в кэш и читает из кэша.
3. Процессор всегда пишет в буфер записи.
4. При записи нового значения в буфер запись происходит и в кэш.
5. Записи из буфера попадают в память.

Все хорошо, когда мы живем в мире одного ядра. Но когда ядер несколько начинаются вопросы.

Ядро 1 прочитало переменную f в кэш, ядро 2 изменило переменную f. Как ядро 1 узнает о изменении переменной?

Пока что, в нашей модели, никакой синхронизации между ядрами у нас нет. Так и сломался наш пример, возьмем вариант исполнения 1 (во вкладке ответ):

x = 1 // запись попала в буфер записи (не в память) y = 1 // запись попала в буфер записи (не в память) b = x // в кэше потока 2 значения нет, читаем из памяти 0 a = y // в кэше потока 1 значения нет, читаем из памяти 0 В ответе (0, 0)

Мы хотим вернуть нашему примеру исполнение, чтобы он согласовывался с моделью SC — интуитивно понятной моделью.

Барьеры

Для начала хочу затронуть тему инвалидации значений кэша. Чтобы не углубляться, значение в кэше ядра инвалидируется (значение становится «неактульным»), если изменяется (операция записи в store buffer) в другом ядре. Процесс инвалидации определяется протоколом когеренции кэшей (для x86 Intel это MESI), сейчас это не важно. Попробуем ответить на вопрос поставленные выше.

Ядро 1 прочитало переменную f в кэш, ядро 2 изменило переменную f. Как ядро 1 узнает о изменении переменной?

Например в данном случае, переменная f в кэше ядра 1 будет инвалидирована, при изменении в ядре 2. Как только мы попробуем прочитать инвалидированную переменную, чтение будет произведено из памяти (то есть значение будет актуальным).

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

Та же ситуация возникает и с store buffer, процессор записывает данные в память, когда ему будет удобно (но запрос на инвалидацию отправляется мгновенно). Подробнее взаимодействие протокола когеренции кэшей и барьеров я постараюсь раскрыть в следующей статье, а пока картинка.

Понятно, что «удобно» понятие неопределенное и не дает никаких гарантий. А мы хотим их получить. Для таких случаев в процессорах x86 и Arm (а также и в других) предусмотрены специальные инструкции — барьеры памяти.

1. load memory fence — выполнит все накопленные запросы на инвалидацию. Этот барьер гарантирует, что все последующие операции load не будут выполнятся до завершения load memory fence.
2. store memory fence — записать накопленные в буфере записи данные в память. Этот барьер гарантирует, что все последующие операции store не будут выполнятся до завершения store memory fence.

Добавим на рисунок места применения барьеров

Тогда, чтобы исключить результат (0, 0) в нашем примере, нужно придумать, куда и какие именно барьеры поставить (барьер это инструкция, для простоты можно считать его вызовом функции — например store_memory_barrier(), и добавить до/после какой-либо строки).

Замечание-ответ

Простым решением конечно же будет являться такое добавление барьеров. После записи x и y необходимо, чтобы они попали в память. А перед чтением x и y нужно обновить кэш.

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

Окончательный ответ

Попробуем раскрутить простое решение

1) Можем ли мы убрать store barrier? — не можем, тогда значения x и y навечно(в нашей модели) останутся в буфере записи.

2) Можем ли убрать load barrier? — не можем, тогда инвалидация значений значений может еще не произойти (ядро «не увидит» изменения других ядер).

Представляю рабочий вариант(решение через добавление обоих барьеров), который корректно будет исполнятся в любом случае (вариант на процессоре x86).

#include #include int x, y, a, b; void* thread1(void* unused) < x = 1; // store barrier __asm__ __volatile__ ("sfence" . "memory"); // load barrier __asm__ __volatile__ ("lfence" . "memory"); a = y; return NULL; >void* thread2(void* unused) < y = 1; // store barrier __asm__ __volatile__ ("sfence" . "memory"); // load barrier __asm__ __volatile__ ("lfence" . "memory"); b = x; return NULL; >int main() < int i = 0; while (1) < x = 0; y = 0; a = 0; b = 0; // store barrier - для честности эксперимента __asm__ __volatile__ ("sfence" . "memory"); pthread_t tid1; pthread_attr_t attr1; pthread_t tid2; pthread_attr_t attr2; pthread_attr_init(&attr1); pthread_attr_init(&attr2); pthread_create(&tid1, &attr1, thread1, NULL); pthread_create(&tid2, &attr2, thread2, NULL); pthread_join(tid1, NULL); pthread_join(tid2, NULL); i++; // load barrier - для честности эксперимента __asm__ __volatile__ ("lfence" . "memory"); if(a == 0 && b == 0) < break; >> printf("Iterations: %d\n", i); return 0; > 

Код скомпилирован с ключом -O0 (отключение оптимизаций)

Если Вам удалось понять содержимое статьи, то любые другие элементы многопоточного программирования дадутся Вам намного легче.

Конец

Если Вы сталкиваетесь с многопоточностью впервые, скорее всего с первого и даже с третьего раза Вам будет понятно не всё. Для полного понимания нужна практика.

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

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

Многопоточное программирование и его проблемы

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

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

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

Узнай, какие ИТ — профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Павел Симонов
Исполнительный директор Geekbrains

Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов
Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

Получить подборку бесплатно
Уже скачали 25504

Concurrent vs Parallel vs Async

На Stackoverflow есть популярный вопрос: «чем concurrent отличается от parallel в контексте программирования?». Вот мое видение вопроса.

Concurrent — это постановка проблемы. Я хочу, чтобы некоторые части моего кода выполнялись независимо друг от друга, одновременно.

Parallel — это один из способов решения проблемы одновременности, когда задачи выполняются на отдельных процессорах или ядрах параллельно.

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

Скажем, Erlang реализует сразу два подхода к одновременному выполнению задач: он запускает несколько планировщиков, каждый из которых работает на своем процессорном ядре, и распределяет между ними потоки виртуальной машины. Но так как потоков обычно гораздо больше, чем планировщиков, то каждый планировщик внутри себя реализует вытесняющую многозадачность на основе сокращений(reductions). При этом конкретный поток работает абсолютно, идеально синхронно со стороны кода. Я расскажу о планировщике Erlang в деталях в одной из следующих статей. Там все очень интересно.

Для вас подарок! В свободном доступе до 14.01 —>
Скачайте ТОП-10
бесплатных нейросетей
для программирования
Помогут писать код быстрее на 25%
Чтобы получить подарок, заполните информацию в открывшемся окне

Async — вообще совершенно отдельная от многопоточности тема, потому что асинхронное выполнение кода возможно в одном потоке без concurrency. Пример — JavaScript: он однопоточный, он не реализует concurrency, и при этом вы можете отложить выполнение куска кода на потом с помощью петли событий. У нас в блоге есть подробный разбор того, как работает JavaScript.

Ради справедливости нужно заметить, что есть экспериментальные реализации многопоточного движка JavaScript, который реализует concurrency. Вот, взгляните: https://medium.com/@voodooattack/multi-threaded-javascript-introduction-faba95d3bd06

Многозадачность

Я выделяю два основных вида многозадачности.

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

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

Такая многозадачность реализована в Erlang, Go и Haskell.

Кооперативная
Тут все наоборот: потоки сами передают управление другим потокам, когда захотят. В старых ОС были именно такие планировщики. Кооперативная многозадачность реализована во многих языках, например в Python, OCaml, Ruby, Node.js.

Проблема кооперативности очевидна: поскольку управление потоками по сути передается в руки программиста, появляется множество возможностей отстрелить ногу по самое колено.

Дарим скидку от 60%
на обучение «Разработчик» до 14 января
Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей

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

Проблемы планирования задач

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

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

Более сложные варианты — переключать задачи по времени выполнения, или по количеству вызовов функций (по сокращениям). Про сокращения мы еще поговорим позже.

Приоритеты
Теперь второй вопрос: как отсортировать очередь задач, чтобы всем досталось немного времени, и никто не обиделся? Ну, можно вообще не париться, и просто выполнять задачи по очереди: первый зашел, первый вышел (FIFO). Но в таком случае при постоянном притоке задач каждая задача будет вынуждена подождать, пока до нее дойдет очередь.

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

Наконец, можно реализовать систему приоритетов, как это сделано в планировщиках современных ОС.

Языки с реализованными планировщиками решают для себя эти вопросы по-разному, в зависимости от приоритетов разработчиков языка. Скажем, Erlang позиционируется как soft-realtime язык, поэтому он крайне агрессивно и часто переключает контекст, чтобы как можно быстрее дать отработать каждой задаче хотя бы частично.

Только до 11.01
Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней
Список документов:

ТОП-100 площадок для поиска работы от GeekBrains

20 профессий 2023 года, с доходом от 150 000 рублей

Чек-лист «Как успешно пройти собеседование»

Чтобы зарегистрироваться на бесплатный интенсив и получить в подарок подборку файлов от GeekBrains, заполните информацию в открывшемся окне

Общая память

Синхронизация доступа к данным — одна из первых вещей, с которыми столкнется человек, берущийся за многопоточное программирование в низкоуровневых языках. Скажем, C вообще не имеет встроенных примитивов для синхронизации доступа, и вам как минимум потребуется использовать POSIX Semaphores или написать свое решение. В Java есть уже некоторые полезные штуки, но вам все равно придется сперва разобраться в том, как они работают.

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

Для решения этой проблемы применяют блокировки, неблокирующий доступ (CAS) и некоторые особенности конкретных языков.

Блокировки
Блокировки работают очень просто: прежде чем писать в переменную, поток должен захватить семафор. Остальные потоки будут вынуждены ждать, пока семафор не освободится, и лишь потом один из других потоков снова захватит семафор, и так далее. Разумеется, это медленно работает, а также намертво блокирует ожидающие потоки. Кроме того, можно прекрасным образом написать код с взаимными блокировками.

Краевой случай семафора — мьютекс, максимально упрощенный семафор. Главное в нем то, что только один поток в один момент времени может владеть мьютексом. Операционные системы часто имеют свои высокопроизводительные реализации мьютексов — фьютексы в Linux, FAST_MUTEX в Windows. Кроме того, в различных языках есть свои специализированные реализации мьютексов для особых задач.

Не-блокировки
Чтобы избежать части проблем, придумали неблокирующие реализации синхронизации. Одна из них — CAS, compare and set. Я оставлю ссылку, чтобы вы могли почитать о том, как это работает: https://ru.wikipedia.org/wiki/Сравнение_с_обменом. И вот еще вам небольшая презентация: slideshare.net/23derevo/nonblocking-synchronization

Наконец, есть еще один железобетонный способ избежать проблем с синхронизацией: давайте просто запретим потокам писать в общую память. Пусть у каждого потока будет своя куча, где он будет хранить свои данные, а если нужно обменяться информацией — пусть шлет сообщение другому потоку. Такая модель реализована в Go и Erlang, например.

Haskell первым реализовал еще один подход к проблеме синхронизации — STM, software transactional memory. По сути, это реализация транзакционного чтения-записи в общую память, аналогично тому, как устроены транзакции в базах данных. Подробнее можно почитать тут: https://ru.wikipedia.org/wiki/Программная_транзакционная_память

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