Какое количество стеков есть у потока

1

Глава 16 Стек потока

Иногда система сама резервирует какие-то регионы в адресном пространстве Ва шего процесса. Я уже упоминал в главе 13, что это делается для размещения блоков переменных окружения процесса и его потоков. Еще один случай резервирования ре гиона самой системой — создание стека потока

Всякий раз, когда в процессе создается поток, система резервирует регион адрес ного пространства для стека потока (у каждого потока свой стек) и передает этому региону какой-то объем физической памяти По умолчанию система резервирует 1 Мб адресного пространства и передает ему всего две страницы памяти. Но стандартные значения можно изменить, указав при сборке программы параметр компоновщика /STACK

/STACK. reserve [, commit]

Тогда при создании стека потока система зарезервирует регион адресного про странства, размер которого указан в параметре /STACK компоновщика Кроме того, объем изначально передаваемой памяти можно переопределить вызовом CreateThread или_beginthreadex. У обеих функций есть параметр, который позволяет изменять объем памяти, изначально передаваемой региону стска Если в нем передать 0, систе ма будет использовать значение, указанное в параметре /STACK Далее я исхожу ич того, что стек создается со стандартными параметрами.

На рис. 16-1 показано, как может выглядеть регион стека (зарезервированный по адресу 0x08000000) в системе с размером страниц no 4 Кб Регион стека и вся пере данная ему память имеют атрибут защиты PAGE_READWRITE.

Зарезервировав регион, система передает физическую память двум верхним его страницам. Непосредственно перед тем, как приступить к выполнению потока, сис тема устанавливает регистр указателя стека на конец верхней страницы региона сте ка (адрес, очень близкий к 0x08100000). Это та страница, с которой поток начнет использовать свой стек Вторая страница сверху называется сторожевой (guard page)

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

Допустим, стек потока практически заполнен (как па рис. l6-2) и регистр указа теля стека указывает на адрес 0x08003004. Тогда, как только поток вызовет еще одну функцию, система, по идее, должна передать дополнительную физическую память. Но

когда система передает! память странице по адресу 0x08001000, она делает это уже по-другому Регион стека теперь выглядит, как на рис l6-3

Рис. 16-1. Так выглядит регион стека потока сразу после его создания

Рис. 16-2. Почти заполненный регион стека потока

Рис. 16-3. Целиком заполненный регион стека потока

Как и можно было предполагать, флаг PAGE_GUARD со страницы по адресу 0x08002000 удаляется, а странице по адресу 0x08001000 передается физическая па мять. Но этой странице не присваивается флаг PAGE_GUARD. Это значит, что региону адресного пространства, зарезервированному под стек потока, теперь передана вся физическая память, которая могла быть ему передана. Самая нижняя страница оста ется зарезервированной, физическая память ей никогда не передается. Чуть позже я поясню, зачем это сделано

Передавая физическую память странице по адресу 0x08001000, система выполня ет еще одну операцию генерирует исключение EXCEPTION_STACK_OVERFLOW (в файле WinNT.h оно определено как 0xC00000FD). При использовании структурной обработки исключений (SEH) Ваша программа получит уведомление об этой ситуа ции и сможет корректно обработать ее. Подробнее о SEH см. главы 23, 24 и 25, а так же листинг программы Summation, приведенный в конце этой главы

Если поток продолжит использовать стек даже после исключения, связанного с переполнением стека, будет задействована вся память на странице по адресу 0x08001000, и поток попытается получить доступ к странице по адресу 0x08000000 Поскольку эта страница лишь зарезервирована (но не передана), возникнет исклю чение — нарушение доступа. Если это произойдет в момент обращения потока к сте ку, Вас ждут крупные неприятности. Система возьмет управление на себя и завершит нс только данный поток, но и весь процесс И даже не сообщит об этом пользовате лю; процесс просто исчезнет!

Теперь объясню, почему нижняя страница стека всегда остается зарезервирован ной Это позволяет защищать другие данные процесса от случайной перезаписи Ви дите ли, по адресу 0x07FFF000 (па 1 страницу ниже, чем 0x08000000) может быть передана физическая память для другого региона адресного пространства. Если бы странице по адресу 0x08000000 была передана физическая память, система не суме

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

Стек потока в Windows 98

В Windows 98 стеки ведут себя почти так же, как и в Windows 2000. Но отличия все же есть.

На рис. 16-4 показано, как в Windows 98 может выглядеть регион стека (зарезер вированный с адреса 0x00530000) размером 1 Мб.

16 страниц (65 536 байтов)

Верхняя часть стека (зарезервирована для перехвата обращений к несуществующей области стека)

1 страница (4096 байтов)

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

1 страница (4096 байтов)

Страница с атрибутом PAGE_NOACCESS (заменяет флаг PAGE_GUARD)

6 страниц (24 576 байтов)

Страницы, зарезервированные для перехвата переполнения стека

1 страница (4096 байтов)

Переданная страница с атрибутом PAGE_READWRITE (для совместимости с 16-разрядными компонентами)

247 страниц (1 011 712 байтов)

Страницы, зарезервированные для дальнейшего расширения стека

16 страниц (65 536 байтов)

Рис. 16-4. Так выглядит регион стека сразу после его создания под управлением Windows 98

Во-первых, размер региона на самом дслс 1 Мб плюс 1 28 Кб, хотя мы хотели соз дать стек объемом всего 1 Мб. В Windows 98 система резервирует под стек на 128 Кб больше, чсм было запрошено. Собственно стек располагается в середине этого реги она, а по обеим его границам размещаются блоки по 64 Кб каждый.

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

int WINAPI WinMain(HINSTANCE hinstExe, HINSTANCE, PSTR pszCmdLine, int nGmdShow) <

szBuf[10000] — 0; // обращение к несуществующей области стека

Когда выполняется оператор присвоения, происходит попытка обращения за ко нец стека потока. Разумеется, ни компилятор, ни компоновщик не уловят эту ошибку в приведенном фрагменте кода, по, если приложение работает под управлением Win

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

Второе отличие: в стске нет страниц с флагом атрибутов защиты PAGE_GUARD. Пocкoлькy Windows 98 такой флаг не поддерживает, при расширении стека потока она действует несколько иначе. Она помечает страницу переданной памяти, располагаемой под стеком, атрибутом PAGE_NOACCESS (на рис, 16-4 — по адресу 0х0063Е000). Когда поток обращается к этой странице, происходит нарушение доступа. Система пере хватывает это исключение, меняет атрибут защиты страницы с PAGE_NOACCESS на PAGE_READWRITE и передает память новой «сторожевой» странице, размещаемой сразу за предыдущей.

Третье: обратите внимание на единственную страницу с атрибутом PAGE_READ WRITE по адресу 0x00637000. Она создается для совместимости с 16-разрядной Win dows. Хотя Microsoft нигде нс говорит об этом, разработчики обнаружили, что пер вые 16 байтов cегмента стека 16-разрядной программы содержат информацию о ее стeке, локальной куче и локальной таблице атомарного доступа. Поскольку Win32 приложения в Windows 98 часто обращаются к 16-разрядным DLL и некоторые из этих DLL предполагают наличие тех самых 16 байтов в начале сегмента стека, Microsoft пришлось эмулировать подобные данные и в Windows 98. Когда 32-разрядный код обращается к 16-разрядному, Windows 98 отображает 16-битный селектор процессо ра на 32-разрядный стек и записывает в регистр сегмента стека (SS) такое значение, чтобы он указывал на страницу по адресу 0x00637000. И тогда 16-разрядный код, получив доступ к своим 16 байтам в начале сегмента стека, продолжает выполнение без всяких проблем

По мере роста стека потока, выполняемого под управлением Windows 98, блок памяти по адресу 0x0063F000 постепенно увеличивается, а сторожевая страница сме щается вниз до тех пор, пока не будет достигнут предел в 1 Мб, после чего она исче зает так же, как и в Windows 2000. Одновременно система смещает позицию страни цы, предназначенной для совместимости с компонентами 16-разрядной Windows, и она, в конце концов, попадает в 64-килобайтовый блок, расположенный в начале ре гиона стека. Поэтому целиком заполненный стек в Windows 98 выглядит так, как по казано на рис. 16-5.

16 страниц (65 536 байтов)

Верхняя часть стека (зарезервирована для перехвата обращений к несуществующей области стека)

256 страниц (1 Мб)

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

7 страниц (28 672 байта)

Страницы, зарезервированные для перехвата переполнения стека

1 страница (4096 байтов)

Переданная страница с атрибутом PAGE_READWRITE (для совместимости с 16-разрядными компонентами)

8 страниц (32 768 байтов)

Нижняя часть стека (зарезервирована для перехвата переполнения стека)

Рис. 16-5. Целиком заполненный регион стека потока в Windows 98

Функция из библиотеки С/С++ для контроля стека

Библиотека С/С++ содержит функцию, позволяющую контролировать стек. Трансли руя исходный код программы, компилятор при необходимости генерирует вызовы этой функции. Она обеспечивает корректную передячу страниц физической памяти стеку потока.

Возьмем, к примеру, небольшую функцию, требующую массу памяти под свои локальные переменные:

// здесь что-то делаем с массивом

nValuesjOj = 0; // а тут что-то присваиваем

Для размещения целочисленного массива функция потребует минимум 16 000 байтов стекового пространства, так как каждое целое значение занимает 4 байта. Код, генерируемый компилятором, обычно выделяеттакое пространство в стеке простым уменьшением указателя стека процессора на 16 000 байтов. Однако система не пере даст физическую память этой нижней области стека, пока не произойдет обращения по данному адресу

В системе с размерим страниц по 4 или 8 Кб это могло бы создать проблему. Если первое обращение к стеку проходит по адресу, расположенному ниже сторожевой страницы (как в показанном выше фрагменте кода), поток обратится к зарезервиро ванной памяти, и возникнет нарушение доступа. Поэтому, чтобы можно было спокой но писать функции вроде приведенной выше, компилятор и вставляет в код вызовы библиотечной функции для контроля стека.

При трансляции программы компилятору известен размер страниц памяти, ис пользуемых целевым процессором (4 Кб для x86 и 8 Кб для Alpha). Встречая в про грамме ту или иную функцию, компилятор определяет требуемый для нее объем сте ка и, если он превышает размер одной страницы, вставляет вызов функции, контро лирующей стек.

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

// стандартной библиотеке С «известен» размер страницы в целевой системе

#define PAGESIZE (8 * 1024) // страницы по 8 Кб

#define PAGESIZE (4 * 1024) // страницы по 4 Кб

void StackCheck(int nBytesNeededFromStack) <

// Получим значение указателя стека. В этом месте указатель стека // еще НЕ был уменьшен для учета локальных переменных функции. PBYTE pbStackPfr = (указатель стека процессора);

while (nBytesNeededFromStack >= PAGESIZE) <

// смещаем страницу вниз по стеку — должна быть сторожевой pbStackPtr -= PAGESIZE;

// обращаемся к какому-нибудь байту на сторожевой странице, вызывая // тем самым передачу новой страницы и сдвиг сторожевой страницы вниз pbSTackPtr[0] = 0;

// уменьшаем требуемое количество байтов в стеке nBytesNeededFromStack -= PAGESIZE;

// перед возвратом управления функция StackCheck устанавливает регистр // указателя стека на адрес, следующий за локальными переменными функции

В компиляторе Microsoft Visual C++ предусмотрен параметр, позволяющий конт ролировать пороговый предел числа страниц, начиная с которого компилятор авто матически вставляет в программу вызов функции StackCheck. Используйте этот пара метр, только если Вы точно знаете, что делаете, и если это действительно нужно. В 99,99999 процентах из ста приложения и DLL не требуют применения упомянутого параметра.

Программа-пример Summation

Эта программа, «16 Summation.exe» (см. листинг на рис. 16-6), демонстрирует исполь зование фильтров и обработчиков исключений для корректного восстановления пос ле переполнения стека. Файлы исходного кода и ресурсов этой программы находят ся в каталоге l6-Summation на компакт-диске, прилагаемом к книге. Возможно, Вам придется сначала прочесть главы по SEH, чтобы понять, как работает эта программа. Она суммирует числа от 0 до x, гдеx — число, введенное пользователем. Конечно, проще было бы написать функцию с именемSum, которая вычисляла бы по формуле:

Sum = (x * (x + 1)) / 2;

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

При запуске программы появляется диалоговое окно, показанное ниже.

В этом окне Вы вводите число и щелкаете кнопку Calculate. Программа создает поток, единственная обязанность которого — сложить все числа от 0 до x. Пока он выполняется, первичный поток программы, вызвавWaitForSingleOhject, просит систе му не выделять ему процессорное время. Когда новый поток завершается, система вновь выделяет процессорное время первичному потоку. Тот выясняет сумму, полу чая код завершения нового потока вызовомGetExitCodeThread, и — это очень важно — закрывает свой описатель нового потока, так что система может уничтожить объект ядра «поток», и утечки ресурсов не произойдет.

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

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

Теперь обратимся к суммирующему потоку, Его функция — SumThreadFunc, При создании этого потока первичный поток передает ему в единственном параметреpvParam количество целых чисел, которые следует просуммировать. Затем его функ ция инициализирует переменнуюuSum значением UINT_MAX, т. e. изначально пред полагается, что работа функции не завершится успехом ДалссSumThreadFunc акти визирует SEH так, чтобы перехватывать любое исключение, возникающее при вы полнении потока. После чего для вычисления суммы вызывается рекурсивная функ цияSum.

Если сумма успешно вычислена, SumThreadFunc просто возвращает значение пе ременнойuSum, оно и будет кодом завершения потока. Но, если при выполненииSum возникает исключение, система сразу оценивает выражение в фильтре исключений. Иначе говоря, система вызываетFilterFunc, передавая ей код исключения. R случае переполнения стека этим кодом будет EXCEPTION_STACK_OVERFLOW. Чтобы увидеть, как программа обрабатывает исключение, вызванное переполнением стека, дайте ей просуммировать числа от 0 до 44000.

Моя функция FilterFunc очень проста. Сначала она проверяет, произошло ли ис ключение, связанное с переполнением стека. Если нет, возвращает EXCEPTION_CON TINUE_SEARCH, а если да — EXCEPTION_EXECUTE_HANDLER Это подсказывает сис теме, что фильтр готов к обработке этого исключения и что надо выполнить код в блокеexcept. В данном случае обработчик исключения ничего особенного не делает, просто закрывая поток с кодом завершения UINT_MAX Родительский поток, получив это специальное значение, выводит пользователю сообщение с предупреждением.

И последнее, что хотелось бы обсудить; почему я выделил функцию Sum в отдель ный поток вместо того, чтобы просто создать SEH-фрейм в первичном потоке и вы зыватьSum из его блокаtry. На то есть три причины.

Во-первых, всякий раз, когда создается поток, он получает стек размером 1 Мб. Если бы я вызывал Sum из первичного потока, часть стекового пространства уже была бы занята, и функция не смогла бы использовать весь объем стека. Согласен, моя про грамма очень проста и, может быть, не займет слишком большое стековое простран ство. А если программа посложнее? Легко представить ситуацию, когдаSum подсчи тывает сумму целых чисел от 0 до 1000 и стек вдруг оказывается чем-то занят, — тог да его переполнение произойдет, скажем, еще при вычислении суммы от 0 до 750. Таким образом, работа функцииSum будет надежнее, если предоставить ей полный стек, не используемый другим кодом.

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

И последнее, почему я использую отдельный поток: физическую память, отведен ную под его стек, можно освободить. Рассмотрим такой сценарий: пользователь про сит функцию Sum вычислить сумму целых чисел от 0 до 30 000. Это требует передачи региону стека весьма ощутимого объема памяти. Затем пользователь проводит не

сколько операций суммирования — максимум до 5000 И окажется, что стеку передан порядочный объем памяти, который больше не используется А ведь эта физическая память выделяется из страничною файла Так что лучше бы освободить се и вернуть системе И поскольку программа завершает поток SumThreadFunc, система автомати чески освобождает физическую память, переданную региону стека

[DotNetBook] Стек потока. Его редактирование и клонирование потока

С этой статьей я продолжаю публиковать целую серию статей, результатом которой будет книга по работе .NET CLR, и .NET в целом. Вся книга будет доступна на GitHub (ссылка в конце статьи). Так что Issues и Pull Requests как всегда приветствуются 🙂

Существует область памяти, про которую редко заходит разговор. Однако эта область является, возможно, основной в работе приложения. Самой часто используемой, достаточно ограниченной с моментальным выделением и освобождением памяти. Область эта называется «стек потока». Причем поскольку указатель на него кодируется по своей сути регистрами процессора, которые входят в контекст потока, то в рамках исполнения любого потока стек потока свой. Зачем же он необходим? Давайте вместе окунемся в мир низкоуровневых структур, на основе которых работает все: начиная от DOS программ и заканчивая .NET Framework, установленным поверх Windows 10.

Итак, разберем элементарный пример кода:

В данном коде не происходит ничего примечательного, однако не будем его пропускать, а наоборот: посмотрим на него максимально внимательно.

Примечание

Глава, опубликованная на Хабре не обновляется и возможно, уже несколько устарела. А потому, прошу обратиться за более свежим текстом к оригиналу:

• CLR Book: GitHub, оглавление
• CLR Book: GitHub, глава
• Релиз 0.5.2 книги, PDF: GitHub Release

Когда любой `Method1` вызывает любой `Method2`, то абсолютно любой такой вызов (и не только в .NET, но и в других платформах) осуществляет следующие операции:

1. Первое что делает код, скомпилированный JIT’ом: он сохраняет параметры метода в стек (начиная с третьего). При этом первые два передаются через регистры. Тут важно помнить что первым параметром экземплярных методов передается указатель на тот объект, с которым работает метод. Т.е. указатель `this`. Так что в этих (почти всех) случаях для регистров остается всего один параметр. А для всех остальных — стек;
2. Далее компилятор ставит инструкцию вызова метода `call`, которая помещает в стек адрес возврата из метода: адрес следующей за `call` инструкцией. Таким образом любой метод знает, куда ему необходимо вернуться чтобы вызывающий код смог продолжить работу;
3. После того как все параметры переданы, а метод вызван нам надо как-то понять как стек восстановить в случае выхода из метода если мы не хотим заботиться о подсчете занимаемых нами в стеке байтов. Для этого мы сохраняем значение регистра EBP, который всегда хранит указатель на начало текущего кадра стека (т.е. участка, где хранится информация для конкретного вызванного метода). Сохраняя при каждом вызове значение этого регистра мы тем самым фактически создаем односвязный список стековых кадров. Но прошу заметить что по факту они идут чётко друг за другом, без каких-либо пробелов. Однако для упрощения освобождения памяти из под кадра и для того чтобы можно было отлаживать приложения (отладчик использует эти указатели чтобы отобразить Stack Trace) односвязный список строится;
4. Последнее что надо сделать при вызове метода — выделить участок памяти под локальные переменные. Поскольку компилятор заранее знает сколько ее понадобится, то делает он это сразу, сдвигая указатель на вершину стека (SP/ESP/RSP) на необходимое количество байт;
5. И наконец, на пятом этапе выполняется код метода, полезные операции;
6. Когда происходит выход из метода, то вершина стека восстанавливается из EBP — места, где хранится начало текущего стекового кадра;
7. Далее, последним этапом осуществляется выход из метода через инструкцию `ret`. Она забирает со стека адрес возврата, заботливо оставленный ранее инструкцией `call`, и делает переход по этому адресу.

Также замечу что стек «растет» начиная со старших адресов и заканчивая младшими, т.е. в обратную сторону.

Глядя на все это, невольно приходишь к выводу что если не большинство, то минимум половина всех операций, которыми занимается процессор — это обслуживание структуры программы, а не ее полезной нагрузки. Т.е. обслуживание вызовов методов, проверки типов на возможность привести один к другому, компиляцию Generic вариаций, поиск методов в таблицах интерфейсов… Особенно если мы вспомним что большинство современного кода написано с подходом работы через интерфейсы, разбивку на множество пусть маленьких но выполняющих каждый — свое — методов… А работа при этом часто идет с базовыми типами и приведением типов то к интерфейсному, то к наследнику. При всех таких входящих условиях вывод о расточительности инфраструктурного кода вполне может назреть. Единственное, что я могу вам на это все сказать: компиляторы, в том числе и JIT обладают множеством техник, позволяющим им делать более продуктивный код. Где можно — вместо вызова метода вставляется его тело целиком, а где возможно вместо поиска метода в VSD интерфейса осуществляется его прямой вызов. Что самое грустное, инфраструктурную нагрузку очень сложно замерить: надо чтобы JITter либо какой-либо компилятор вставлял бы какие-то метрики до и после мест работы инфраструктурного кода. Т.е. до вызова метода, а внутри метода — после инициализации кадра стека. До выхода из метода, после выхода из метода. До компиляции, после компиляции. И так далее. Однако, давайте не будем о грустном, а поговорим лучше о том, что мы можем с вами сделать с полученной информацией.

Немного про исключения

Если мы посмотрим внутрь кода методов, то мы заметим еще одну структуру, работающую со стеком потока. Посудите сами:

Если исключение возникнет в любом из методов, вызванных из `Method3`, то управление будет возвращено в блок `catch` метода `Method3`. При этом если исключение обработано не будет, то его обработка начнется в методе `Method1`. Однако если ничего не случится, то `Method3` завершит свою работу, управление перейдет в метод `Method2`, где также может возникнуть исключение. Однако по естественным причинам обработано оно будет не в `Method3`, а в `Method1`. Вопрос такого удобного автоматизма заключается в том что структуры данных, образующие цепочки обработчиков исключений также находятся в стековом кадре метода, где они объявлены. Про сами исключения мы поговорим отдельно, а здесь скажу только что модель исключений в .NET Framework CLR и в Core CLR отличается. CoreCLR вынуждена быть разной на разных платформах, а потому модель исключений там другая и представляется в зависимости от платформы через прослойку PAL (Platform Adaption Layer) различными имплементациями. Большому .NET Framework CLR это не нужно: он живет в экосистеме платформы Windows, в которой есть уже много лет общеизвестный механизм обработки исключений, который называется SEH (Structured Exception Handling). Этот механизм используется практически всеми языками программирования (при конечной компиляции) потому что обеспечивает сквозную обработку исключений между модулями, написанными на различных языках программирования. Работает это примерно так:

1. При вхождении в блок try на стек кладется структура, которая первым полем указывает на предыдущий блок обработки исключений (например, вызывающий метод, у которого также есть try-catch), тип блока, код исключения и адрес обработчика;
2. В TEB потока (Thread Environment Block, по сути — контекст потока) меняется адрес текущей вершины цепочки обработчиков исключений на тот что мы создали. Таким образом мы добавили в цепочку наш блок.
3. Когда try закончился, производится обратная операция: в TEB записывается старая вершина, снимая таким образом наш обработчик из цепочки;
4. Если возникает исключение, то из TEB забирается вершина и по очереди по цепочке вызываются обработчики, которые проверяют, подходит ли исключение конкретно им. Если да, выполняется блок обработки (например, catch).
5. В TEB восстанавливается тот адрес структуры SEH, который находится в стеке ДО метода, обработавшего исключение.

Совсем немного про несовершенство стека потока

Давайте немного подумаем о вопросе безопасности и возможных проблемах, которые чисто теоретически могут возникнуть. Для этого давайте еще раз глянем на структуру стека потока, которая по своей сути — обычный массив. Диапазон памяти, в котором строятся фреймы организован так что он растет с конца в начало. Т.е. более поздние фреймы располагаются по более ранним адресам. Также, как уже было сказано, фреймы связаны односвязным списком. Это сделано потому что размер фрейма не является фиксированным и должен быть «считан» любым отладчиком. Процессор при этом не разграничивает фреймы между собой: любой метод по своему желанию может считать всю область памяти целиком. А если учесть при этом что мы находимся в виртуальной памяти, которая поделена на участки, которые являются реально выделенной памятью, то можно при помощи специальной функции WinAPI по любому адресу со стека получить диапазон выделенной памяти, в которой это«`csharpт адрес находится. Ну а разобрать односвязный список — дело техники:

Это дает нам возможность получить и модифицировать все данные, которые находятся в качестве локальных переменных у методов, которые нас вызвали. Если приложение никак не настраивает песочницу, в рамках которой вызываются сторонние библиотеки, расширяющие функционал приложения, то сторонняя библиотека сможет утащить данные даже если тот API, который вы ей отдаете этого не предполагает. Методика эта может показаться вам надуманной, однако в мире C/C++, где нет такой прекрасной вещи как AppDomain с настроенными правами атака по стеку — это самое типичное что только можно встретить из взлома приложений. Мало того, можно через рефлексию посмотреть на тип, который нам необходим, повторить его структуру у себя, а пройдя по ссылке со стека на объект заменить адрес VMT на наш, перенаправив таким образом всю работу с конкретным экземпляром к нам. SEH, кстати говоря, также вовсю используется для взлома приложений. Через него вы также можете меняя адрес обработчика исключения заставлять ОС выполнить вредоносный код. Но вывод из всего этого очень простой: всегда настраивайте песочницу, когда хотите работать с библиотеками, расширяющими функционал вашего приложения. Я, конечно же имею ввиду всяческие плагины, аддоны и прочие расширения.

Большой пример: клонирование потока

Чтобы запомнить все что мы прочитали до мельчайших подробностей надо зайти к вопросу освещения какой-либо темы с нескольких сторон. Казалось бы, какой пример можно построить для стека потока? Вызвать метод из другого? Магия… Конечно же нет: это мы делаем ежедневно по много раз. Вместо этого мы склонируем поток исполнения. Т.е. сделаем так чтобы после вызова определенного метода у нас вместо одного потока оказалось бы два: наш и новый, но продолжающий выполнять код с точки вызова метода клонирования так как будто он сам туда дошел. А выглядеть это будет так:

Согласитесь, концепт интересный. Конечно же, тут можно много спорить про целесообразность таких действий, но задача этого примера — поставить жирную точку в понимании работы этой структуры данных. Как же сделать клонирование? Для ответа на данный вопрос надо ответить на другой вопрос: что вообще определяет поток? А поток определяют следующие структуры и области данных:

• Набор регистров процессора. Все регистры определяют состояние потока исполнения инструкций: от адреса текущей инструкции исполнения до адресов стека потока и данных, которыми он оперирует;
• [Thread Environment Block](https://en.wikipedia.org/wiki/Win32_Thread_Information_Block) или TIB/TEB, который хранит системную информацию по потоку включая адреса обработчиков исключений;
• Стек потока, адрес которого определяется регистрами SS:ESP;
• Платформенный контекст потока, который содержит локальные для потока данные (ссылка идет из TIB)

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

Когда вызовется MakeFork(), что мы ожидаем с точки зрения стек трейсов? Что в родительском потоке все останется без изменений, а дочерний будет взят из пула потоков (для скорости), в нем будет сымитирован вызов метода MakeFork вместе с его локальными переменными, а код продолжит выполнение не с начала метода, а с точки, следующей после вызова CloneThread . Т.е. стек трейс в наших фантазиях будет выглядеть примерно так:

Что у нас есть изначально? Есть наш поток. Также есть возможность создать новый поток либо запланировать задачу в пул потоков, выполнив там свой код. Также мы понимаем, что информация по вложенным вызовам хранится в стеке вызовов и что при желании мы можем ей манипулировать (например, используя C++/CLI). Причем, если следовать соглашениям и вписать в верхушку стека адрес возврата для инструкции ret, значение регистра EBP и выделить место под локальные (если необходимо), таким образом можно имитировать вызов метода. Ручную запись в стек потока возможно сделать из C#, однако нам понадобятся регистры их их очень аккуратное использование, а потому без ухода в C++ нам не обойтись. Тут к нам на помощь впервые в жизни (лично у меня) приходит CLI/C++, который позволяет писать смешанный код: часть инструкций — на .NET, часть — на C++, а иногда даже уходить на уровень ассемблера. Именно то, что нам надо.

Итак, как будет выглядеть стек потока, когда наш код вызовет MakeFork, который вызовет CloneThread, который уйдет в unmanaged мир CLI/C++ и вызовет метод клонирование (саму реализацию) — там? Давайте посмотрим на схему (еще раз напомню, что стек растет от старших адресов к младшим. Справа налево):

Ну а для того чтобы не тащить всю простыню со схемы на схему, упростим, отбросив то, что нам не нужно:

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

Теперь наша задача — сымитировать запуск метода Fork.CloneThread() в новом потоке. Для этого мы должны в конец его стека потока дописать серию кадров: как будто из делегата, переданного ThreadPool’у был вызван Fork.CloneThread() , из которого через враппер C++ кода managed оберткой был вызван CLI/C++ метод. Для этого мы просто скопируем необходимый участок стека в массив (замечу что со склонированного участка на старый «смотрят» копии регистров EBP, обеспечивающих построение цепочки кадров):

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

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

Но пока не с точки зрения кода. С точки зрения кода нам надо попасть в те методы, которые по только что создали. Самое простое — просто сымитировать выход из метода: восстановить ESP до EBP , в EBP положить то, на что он указывает и вызвать инструкцию ret , инициировав выход из якобы вызванного C++ метода клонирования потока, что приведет к возврату в реальный wrapper CLI/C++ вызова, который вернет управление в MakeFork() , но в дочернем потоке. Техника сработала.

Теперь давайте взглянем на код. Первое что мы сделаем — это возможность для CLI/C++ кода создать .NET поток. Для этого мы его должны создать в .NET:

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

И, наконец, сам метод клонирования (вернее, его .NET часть):

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

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

Метод подготовки к копированию

Описание кода я буду делать блоками. Т.е. единый код будет разбит на части и каждая из частей будет отдельно прокомментирована. Итак, приступим. Когда внешний код вызывает Fork.CloneThread() , то через внутреннюю обертку над неуправляемым кодом и через ряд дополнительных методов если код работает под отладкой (так называемые debugger assistants). Именно поэтому мы в .NET части запомнили адрес переменной в стеке: для C++ метода этот адрес является своеобразной меткой: теперь мы точно знаем какой участок стека мы можем спокойно копировать.

Первым делом, до того как произойдет хоть какая-то операция чтобы не получить запорченные регистры мы их копируем локально. Также дополнительно необходимо сохранить адрес кода, куда будет сделан `goto` когда в дочернем потоке стек будет сымитирован и необходимо будет произвести процеруду выхода из `CloneThread` из дочернего потока. В качестве «точки выхода» мы выбираем `JmpPointOnMethodsChainCallEmulation` и не просто так: после операции сохранения этого адреса «на будущее» мы дополнительно закладываем в стек число 0.

После чего, после `JmpPointOnMethodsChainCallEmulation` мы достаем это число из стека и проверяем: там лежит `0`? Если да, мы находимся в том же самом потоке: а значит у нас еще много дел и мы переходим на `NonClonned`. Если же там не `0`, а по факту `1`, это значит что дочерний поток закончил «дорисовку» стека потока до необходимого состояния, положил на стек число `1` и сделал goto в эту точку (замечу что goto он делает из другого метода). А это значит что настало время для выхода из `CloneThread` в дочернем потоке, вызов которого был сымитирован.

Хорошо, мы убедились что мы все еще мы, а значит надо подготовить данные для дочернего потока. Чтобы более не спускаться на уровень ассемблера, работать мы будем со структурой ранее сохраненных регистров. Достанем из нее значение регистра EBP: он по сути является полем «Next» в односвязном списке кадров стека. Перейдя по адресу, который там содержится мы очутимся в кадре метода, который нас вызвал. Если и там возьмем первое поле и перейдем по тому адресу, то окажемся в еще более раннем кадре. Так мы сможем дойти до managed части CloneThread : ведь мы сохранили адрес переменной в ее стековом кадре а значит прекрасно знаем где остановиться. Этой задачей и занимается цикл, приведенный ниже.

Получив адрес начала кадра managed метода CloneThread , мы теперь знаем сколько надо копировать для имитации вызова CloneThread из MakeFork . Однако поскольку нам MakeFork также нужен (наша задача выйти именно в него), то мы делаем дополнительно еще один переход по односвязному списку: *(int *)curptr . После чего создаем массив под создание стека и сохраняем его простым копированием.

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

Метод восстановления из копии

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

Первым делом мы сохраняем значения рабочих регистров чтобы когда MakeFork завершил свою заботу мы смогли их безболезненно восстановить. Чтобы в дальнейшем минимально влиять на регистры мы выгружаем переданные нам параметры к себе на стек. Доступ к нем будет идти только через SS:ESP что для нас будем предсказуемым.

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

Используя эти данные мы в цикле идем по копии стека и исправляем адреса на их будущие новые положения.

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

Теперь, основная и самая ответственная часть. Когда мы скопируем в конец нашего стека копию диапазона родительского все будет хорошо до момента, когда MakeFork в дочернем потоке захочет выйти (сделать return ). Нам надо указать ему куда он должен выйти. Для этого мы также имитируем вызов самого MakeFork из этого метода. Мы закладываем в стек адрес метки RestorePointAfterClonnedExited , как будто инструкция процессора call заложила в стек адрес возврата, а также положили текущий EBP , сымитировав построение односвязного списка цепочек кадров методов. После чего закладываем в стек обычной операцией `push` копию родительского стека тем самым отрисовав все методы, которые были вызваны в родительском стеке из метода `MakeFork` включая его самого. Стек готов!

Далее поскольку мы также должны восстановить и регистры, восстанивливаем и их самих.

А вот теперь самое время вспомнить тот странный код с закладыванием 0 в стек и проверки на 0 . В этом потоке мы закладываем 1 и делаем дальний jmp в код метода ForkImpl . Ведь по стеку мы находимся именно там, а реально все еще тут. Когда мы туда попадем, то ForkImpl распознает смену потока и осуществит выход в метод MakeFork , который завершив работу, попадет в точку RestorePointAfterClonnedExited , т.к. немного ранее мы сымтировали вызов `MakeFork` из этой точки. Восстановив регистры до состояния «только что вызваны из TheadPool», мы завершаем работу, отдавая поток в пул потоков.

Проверим? Это — скриншот до вызова клонирования потока:

Как мы видим, теперь вместо одного потока внутри MakeFork мы видим два. И оба — вышли из этого метода.

Пара слов об уровне пониже

Если мы заглянем краем глаза на еще более низкий уровень, то узнаем или же вспомним что память на самом деле является виртуальной и что она поделена на страницы объемом 4 Кб. Каждая такая страница может физически существовать или же нет. А если она существует, то может быть отображена на файл или же реальную оперативную память. Именно этот механизм виртуализации позволяет приложениям иметь раздельную друг от друга память и обеспечивает уровни безопасности между приложением и операционной системой. При чем же здесь стек потока? Как и любая другая оперативная память приложения стек потока является ее частью и также состоит из страниц объемом 4 Кб. По краям от выделенного для стека пространства находятся две страницы, доступ к которым приводит к системному исключению, нотифицирующему операционную систему о том что приложение пытается обратиться в невыделенный участок памяти. Внутри этого региона реально выделенными участками являются только те страницы, к которым обратилось приложение: т.е. если приложение резервирует под поток 2Мб памяти это не значит что они будут выделены сразу же. Отнюдь, они будут выделены по требованию: если стек потока вырастет до 1 Мб, это будет означать что приложение получило именно 1 Мб оперативной памяти под стек.

Когда приложение резервирует память под локальные переменные, то происходят две вещи: наращивается значение регистра ESP и зануляется память под сами переменные. Поэтому, когда вы напишете рекурсивный метод, который уходит в бесконечную рекурсию, вы получите StackOverflowException: заняв всю выделенную под стек память (весь доступный регион), вы напоритесь на специальную страницу, Guard Page, доступ к которой вызовет нотификацию операционной системы, которая инициирует StackOverflow уровня ОС, которое уйдет в .NET, будет перехвачено и выбросется исключение StackOverflowException для .NET приложения.

Выводы к разделу

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

Ссылка на всю книгу

• CLR Book: GitHub
• Релиз 0.5.0 книги, PDF: GitHub Release

У каждого потока есть свой стек?

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

да, специфичный для потока стек!, глобальные значения могут использоваться совместно потоком (локальные нет) — Grijesh Chauhan

@GrjeshChauhan Что происходит, когда мы делаем системный вызов из потока? — manav m-n

например, если вы позвоните open() системный вызов для открытия файла. с использованием int f = open() тогда конечно f является локальным для потока. но помните, что файловые дескрипторы являются общими для потоков. Если вы знаете цену f затем вы можете использовать это значение в другом потоке для доступа к тому же файлу (вам не нужно снова открывать) — Grijesh Chauhan

@LidongGuo Нет. Семантика потоков — это то, над чем сотрудничали два комитета. (Интерфейсы несколько различаются, поскольку C явно не может предоставлять «объекты» для потоков, мьютексов и т. д., но семантика идентична.) — James Kanze

1 ответы

Да, у потоков есть свои собственные стеки и собственные стеки ядра (например, linux).

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

ответ дан 21 авг.

Как ядро ​​делает «что нужно делать» без стека? — авакар

Я уточню в своем ответе — Джухван

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

@Potatoswatter Как поток ядра повышает безопасность? Насколько я понимаю, он разработан таким образом для производительности. — Джонатон Рейнхарт

Не тот ответ, который вы ищете? Просмотрите другие вопросы с метками c++ c multithreading pthreads stack or задайте свой вопрос.

Name already in use

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.MD

Различные заметки по изучению устройства операционных систем

Содержание

Что такое процесс

Процесс — это абстракция, реализованная на программном уровне — уровне операционной системы.

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

Элементы процесса:

• адресное пространство
• потоки
• открытые файлы
• дочерние процессы

Просто к слову, адресное пространство — это не только пространство в оперативной памяти (начало адресов и конец), но также может иногда использоваться и виртуальная память. Адресное пространство — это абстрактная вещь, через которую программа может получать доступ к памяти например так: memory[0], не зная к какой памяти вообще обращается, а доступ к оперативной или виртуальной памяти обеспечивают другие вещи.

Что такое поток

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

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

Элементы потока:

• Счётчик команд
• Регистры
• Стек

Почему нужна поддержка множества потоков внутри одного процесса

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

Конечно, можно было бы создать ещё один процесс под задачу, но:

• у процесса будет отдельное адресное пространство и данные
• по вопросам производительности: создание и уничтожение процесса дороже, чем создание потока

Отличие процесса от потока

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

Программа — это набор взаимодейстущих между собой потоков, и может быть, даже процессов.

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

Вывод: процесс — это всего лишь способ сгруппировать взаимосвязанные данные и ресурсы, а потоки — единица выполнения (unit of execution), которая распределяется и выполняется на процессоре. Процессы сменяться на процессоре не могут, сменяются и выполняются на процессоре именно потоки.

Что такое счётчик команд

Счётчик команд (Program counter, Instruction Pointer) — регистр процессора, который хранит адрес ячейки памяти, в которой содержится команда, которую необходимо выполнить следующей.

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

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

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

Состояния потоков (Thread States)

• Выполняемый (Executing) — поток, который выполняется в текущий момент на процессоре
• Готовый (Runnable) — поток ждет получения кванта времени и готов выполнять назначенные ему инструкции. Планировщик выбирает следующий поток для выполнения только из готовых потоков.
• Заблокированный (Waiting) — работа потока заблокирована в ожидании блокирующей операции

Почему создание и уничтожение процессов дороже, чем потоков

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

Что такое многозадачность

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

Для чего нужна многозадачность

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

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

Также, многозадачность позволяет запускать сразу несколько программ на компьютере.

Вытесняющая и кооперативная многозадачность

Существуют вытесняющие и кооперативные алгоритмы планирования:

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

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

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

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

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

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

Что такое Context switch

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

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

Что такое планировщик задач в ОС

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

Как работает планировщик задач

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

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

Алгоритмы планирования зависят от среды выполнения:

• Пакетные системы
• Интерактивная система
• Система реального времени

Вызов планировщика происходит в следующих ситуациях:

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

Далее рассмотрим работу планировщика в описанных выше ситуациях.

Создание нового потока

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

Завершение работы потока

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

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

Возникновение прерывания ввода-вывода

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

Основные алгоритмы планирования в интерактивных системах

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

Если поток к завершению своего кванта все ещё выполняется, то он прерывается принудительно и происходит context switch, позволяя другому потоку поработать.

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

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

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

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

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

Приоритетное планирование бывает статическим и динамическим:

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

Режим ядра и пользователя

• Режим ядра: позволяет иметь доступ ко всей памяти, прямой доступ к аппаратному обеспечению и выполнять любые процессорные инструкции. Если в режиме ядра произойдет ошибка, это может привести к остановке работы всего компьютера, потребовав дальнейшеую перезагрузку, поэтому в ядре предусмотрено несколько уровней доступа и механизмов защиты.
• Режим пользователя: предоставляет доступ только к определенным участкам памяти, а доступ к аппаратному обеспечению ограничен. Все потоки в операционной системе выполняются в режиме пользователя, и если им требуется доступ к аппаратному обеспечению (ввод с клавиатуры, прочитать данные с диска и прочее) или выполнению ограниченной инструкции, они должны обратиться сперва к ядру операционной системы во избежание ошибок. Такие обращения к операционной системе называются system call (syscall). Ошибки в таком режиме не катастрофичны и всегда исправимы.

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

Реализации потоков на уровне ядра и уровне пользователя

Потоки на уровне пользователя

В данной реализации потоки реализованы на пользовательском уровне, а значит, ядру ничего ни о каких потоках не известно. Ядро работает с потоками как с однопоточными процессами. Потоки запускаются поверх системы поддержки исполнения программ (run-time system), которая управляет потоками. Run-time система находится внутри процесса. Также, так как ядру ничего неизвестно о потоках и нет данных о них, процессам придется хранить таблицу потоков (аналогична с таблицей процессов), чтобы отслеживать потоки, которые выполняются внутри процесса. В таблице потоков хранится такая информация о потоках, как: указатель стека, регистр, состояние потока и прочее (все, что нужно для работы потоков, опять же аналогия с процессами).

Достоинства:

• Потоки могут быть реализованы на ОСях (как библиотеки), которые даже не поддерживают потоки (а только процессы).
• Переключение потоков происходит быстрее, так как нет необходимости переключения в режим ядра. Все данные уже есть на стороне пользователя:
  1. Сохранение данных в стек тоже не требуется, данные могут быть сохранены в таблицу потоков (стек находится в таблице потоков, а не в ядре)
  2. Сохранение данных и вызов планировщика — это локальные процедуры и могут быть вызваны сразу с пользовательского уровня. Как итог, переключения в режим ядра вообще не происходит.
• Система поддержки исполнения программ владеет информацией о том, чем занимаются все потоки процесса, поэтому может лучше управлять работой потоков и временем работы каждого потока. Ядро такой информацией не обладает (данная проблема может решиться использованием приоритетов, но это универсальное решение, а в run-time система может быть какая-то другая, специфическая информация, поэтому тут выигрывают потоки на стороне пользователя)

Недостатки:

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

Потоки на уровне ядра

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

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

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

Достоинства

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

Недостатки

• Создание и уничтожение потоков требует более высоких затрат

Что такое зелёный поток? чем он отличается от обычного потока?

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

Операционная система (например, linux) решила, что данный процесс должен запустится. Что это вообще означает, и какие операционная система делает действия в этом месте.

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

19) Создать новый процесс дорого, или дешево с точки зрения ресурсов ОС? Почему так? Как вообще создаются процессы? Откуда они изначально берутся

Создание процесса — дорого. Но вообще это зависит от ОСи. Потому что процесс должен описывать программу полностью: таблицы всех открытых файлов, потоков, адресное пространство. Все это должно инициализироваться. Однако, например, в Unix новый созданный процесс полностью копирует родительский процесс и имеет абсолютно такие же данные, тем самым они не инициализируются снова, поэтому позволяет проделать какие-либо команды перед непосредственным переходом к выполнению процедуры. Только после выполнения процедуры exec() процесс инициализируется новыми данными. В Windows же, новый поток сразу инициализируется новыми данными. Данный пример показывает, что некоторые детали реализации зависят от ОСи.

Все процессы в Unix начинаются с одного стартового — процесса init, который создается во время запуска системы (в Windows есть аналогичный стартовый процесс — System Idle Process). Можно сказать, что в вершине иерархии абсолютно всех процессов в Unix стоит процесс init (в Windows иерархии процессов нет — все процессы равнозначны).

Создать процесс в Unix можно командой fork().

Создать новый поток дорого, или дешево с точки зрения ресурсов ОС? Почему так? Кто создаёт потоки? Откуда первый поток берётся?

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

Создать поток в Unix можно командой pthread_create().

Первый поток, от которого могут быть образованы другие дочерние потоки, создается вместе с созданием процесса и называется main thread.

Пример задачи: Есть программа. Она читает из сокета. Если она будет читать из сокета в 10 потоков, она всегда будет быстрее, чем с 1 потоком?

Да, программа, читающая из 10 сокетов будет быстрее, если распределить работу на 10 потоков, так как, когда 1 поток блокируется на чтении сокета, за счёт осуществления Context Switch, другой поток сможет работать с данными своего сокета, и процессор не будет простаивать (конечно, возможна ситуация, когда все 10 потоков будут заблокированы на своих советах, но это вообще не важно, важно то, что когда нибудь появятся данные на каком-то совете и не надо будет ждать окончания чтения другого).

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

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

Говорится, что такая программа сфокусирована на IO-Bound работе. Context Switch позволяет серьезно повысить производительность работы программы за счет того, что исключается пустое простаивание потока.

Пример задачи: Есть программа. Она считает сумму какого-то большого массива данных. Она всегда будет быстрее в 10 потоков, чем если бы в ней был 1 поток? Объясни почему так?

1. В случае параллельной многозадачности (многоядерной среды): Да, будет быстрее. Можно распределить работу на 10 потоков, назначив каждому потоку вычисление определенного промежутка массива. Каждый поток посчитает свой промежуток и вернет результат, из полученных результатов получится сумма всего массива. Поэтому параллельные вычисления (параллельная многозадачность) активно применяются в науке — ученым нужно много считать много чисел (например, умножение больших матриц). Однако, следует учитывать то, что создав потоков больше, чем ядер, это не принесет никакого увеличения эффективности вычислений, так как параллельно все также работают только столько потоков, сколько есть ядер.
2. В случае псевдопараллельной многозадачности (одноядерной среды): Нет, распределив работу на 10 потоков, вычисление не будет быстрее, а займёт даже больше времени из-за траты времени на переключение потоков (переключение контекста — это около 600-1200 процессорных инструкций, когда обычный процессор делает 12 операций в наносекунду, по меркам процессора — да, context switch действительно стоит дорого, хотя по нашим меркам может казаться что это очень мало).

Говорится, что такая программа сфокусирована на CPU-Bound работе: программа постоянно выполняет что-то, и никогда не может возникнуть ситуации, когда поток заблокируется. Распределение задачи на несколько потоков бесполезно, потому что потоки никогда не будут простаивать, то есть будут готовы выполнять инструкции. Context Switch только ухудшит производительность программы, так как процессор будет тратить время на переключение контекса, когда мог выполнять более полезную работу.

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

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

Основные принципы для избежания потерь и задержек аудио:

1. Нельзя никогда блокировать поток, который воспроизводит аудио
2. Нужно при разработке или использовании алгоритма воспроизведния аудио смотреть не на среднее время выполнения (average case), а на худшее время выполнения алгоритма (worst case)

Что такое примитивы синхронизации, и как это вообще работает? Если бы ты писал свой язык программирования, в твоем языке могли бы появится примитивы синхронизации?

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

Примитивы синхронизации в зависимости от типа примитива преследуют различные задачи:

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

Если бы я писал свой язык программирования, и в нем была поддержка тредов, то да, я бы сделал примитивы синхронизации.

Основные примитивы синхронизации

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

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

Спинлок — это лок, для блокировки которого используется активное ожидание (busy-waiting).

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

Захватить спинлок можно, например, операцией TSL (Test and Set Lock) (блокировка шины памяти, которая запрещает другим потокам получить доступ к памяти).

Пример реализации TSL:

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

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

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

Существуют две операции над семафорами — down и up, которые являются атомарными действиями. Атомарность гарантирует то, что во время выполнения операции одним потоком, никакой другой поток не сможет получить доступ к семафору. Тем самым исключаются состязательные ситуации.

Операция down(): пытается понизить значение семафора на единицу: если значение семафора равно нулю, то поток блокируется, иначе значение декрементируется и поток работает дальше.

Операция up(): повышает значение на единицу и система разблокирует один из заблокированных на данном семафоре потоков, если таковые есть. Разблокированный поток завершает операцию down (при этом значение семафора снова становится нулевым) и продолжает работать дальше.

Рассмотрим задачу производителя и потребителя для большего понимания использования семафора:

Здесь, семафоры full и empty выполняют задачу синхронизации — они гарантируют, что производитель не будет работать, пока не будет свободных слотов (производтель заблокируется на операции down(&empty) ), а покупатель не будет работать, пока не будет доступных для обработки вещей, созданных производителем (покупатель заблокируется на операции down(&full) ), то есть оба не будут работать до наступления какого-либо события.

Семафор mutex выполняет задачу взаимного исключения — он гарантирует, что с буфером не будут работать и производитель, и покупатель одновременно (один из них заблокируется на операции down(&mutex) ).

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

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

Мьютекс может находиться только в одном из двух состояний: заблокированном и незаблокированном.

Существуют две операции с мьютексом:

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

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

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

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

В Java можно объявлять функции как synchronized. Тогда Java гарантирует, что как только один поток приступает к выполнению данной функции, никакой другой поток не сможет вызвать любые другие synchronized методы этого класса.

Монитор и мьютекс — это одно и тоже, или нет?

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

Как выбрать подходящий примитив синхронизации

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

1. Недолгое простаивание стоит меньше, чем вызов планировщика и выполнение Context Switch, то есть смена потоков
2. В случае с мьютексом или семафором потоку придётся снова ждать возможности выполнения, в отличие от потока, который заблокирован на спинлоке: данный поток сможет завершить требуемые операции и потратить свой квант времени полностью.

Семафоры следует применять в следующих ситуациях:

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

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

Когда лучше применять спинлок и что такое недолгое ожидание?

Разработчику требуется оценить куски кода, защищенные спинлоком: вызываются ли блокирующие IO операции в этих областях кода? Это критично, потому что если некоторый поток захватил лок и вызвал блокирующую IO операцию, то это может не позволить ДРУГИМ ПОТОКАМ захватить лок в течение очень долго времени. Эти потоки будут простаивать, так как все они, ожидая разблокировки первым тредом лока, зависят от выполнения этим тредом блокирующей операции, и потоки, заблокированные на спинлоке, могут тратить квант за квантом в ожидании разблокировки спинлока первым потоком. Если используется любая блокирующая IO операция, то следует применить мьютекс, так как при невозможности захвата лока, потокам не придется ждать окончания блокирующей операции, вызванной в треде, который захватил лок.

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

Если есть всего пара инструкций, которые требуется выполнить, тогда зачем тратить около 600-1200 (примерно столько занимает context switch), чтобы выполнить малое количество процессорных инструкций? Лучше немного подождать, а на ожидание уйдет небольшое количество инструкций, и выполнить команды без смены потоков. А при грамотном использовании спинлоком мы знаем, что будем ждать недолго, так как сам код, защищенный спинлоком, — занимает очень маленькое время, так как мы поместили туда маленькое количество инструкций.

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

А операции с примитивами синхронизации — они вообще дорогие? Можно что-то сделать, для того чтобы их не пришлось ипользовать, или их использование было минимальным?

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

Сократить же использование примитивов можно двумя способами:

1. Использовать иммутабельные данные (то есть неизменяемые после создания), такие данные потоко-безопасны и их можно свободно использовать между потоками
2. Когда потоки работают со своими данными, а не общими

Lock-free и Wait-free алгоритмы

Существует non-blocking программирование. Также, существует дальнейшее продолжение в виде lock-free программирования, если гарантируется system-wide прогресс, и wait-free программирования, если гарантируется прогресс каждого потока. То есть: non-blocking lock-free, non-blocking wait-free

Принципы lock-free:

1. Гарантированный system-wide прогресс
2. Если один поток вымещается планировщиком, это не должно помешать выполнению прогресса другими потоками

Принципы wait-free:

1. Гарантированный прогресс каждого потока, то есть прогресс одного потока не должен зависеть от другого, ниже будет пример с cas-лупом где в lock free алгоритме 1 поток, делая прогресс, не дает делать прогресс другим
2. Если один поток вымещается планировщиком, это не должно помешать выполнению прогресса другими потоками

Все wait-free алгоритмы являются lock free алгоритмами, но никакой lock free алгоритм не является wait free алгоритмом.

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

Такие алгоритмы очень сложно писать правильно и тем более wait free. Но wait-free всегда лучше чем lock-free, так как wait free является starvation-free (потоки не простаивают в ожидании бесполезно, а делают какую то работу)

Пример lock-free алгоритма: атомарная операция fetch_add() , реализованная с помощью cas операций (т.е. cas-лупа)

Пусть несколько потоков вызвали эту функцию. Один поток будет крутиться в cas-цикле, и может крутиться даже бесконечно, но если этот поток не смог совершить cas операцию полностью (то есть операция compare and swap вернула false), то значит что какой-то другой поток смог выполнить эту операцию полностью (действительно, какой-то поток смог прочитать и установить значение атомарно, а остальные вернули ошибку из-за race condition) Таким образом, какой-то из потоков гарантированно на каждой итерации выполняет полезную работу, это и называется system-wide прогресс.

Wait free алгоритм же, выполняет свою работу за конечное число шагов, не зависящее от других потоков (в то время как например, если один поток вызвал функцию fetch_add(), количество шагов, за которое она выполнится, будет зависеть от других потоков)

И как противоложный пример спинлока или операции fetch_add реализовнной с помощью cas операций можно привести примитив мьютекс (locked или по другому blocking): Мьютекс — не является lock-free примитивом и не может быть реализован как lock-free именно из-за семантики (есть функция trylock, но в основном так). Пусть 1 поток захватил лок, и по середине работы с критической областью данный поток был вытеснен планировщиком, тогда никакой другой поток не сможет захватить мьютекс, пока первый не высвободит его. Понятно, что:

• Тут не происходит даже system-wide прогресса
• Все потоки пытающиеся захватить мьютекс будут простаивать. Получается, что первый поток неявно заблокировал другие, а это противоречит понятию lock free

Как имплементируются атомарные операции в C++

Если нет поддержки cas-операций на аппаратном уровне, то используется мьютекс , иначе компилятор старается делать атомарные операции lock-free и использует test-and-set и cas-операции . Однако, это не тот мьютекс что в либе std , который описан стандартом, а совершенно другой мьютекс, реализуемый компилятором для того чтобы реализовать атомарные операции языка.

То есть важно провести границу между языком и компилятором. Есть атомарные операции, прописанные в стандарте C++ — они должны быть так или иначе сделаны компилятором, если компилятор заявлен как поддерживающий стандарт 11 плюсов. Но то как они реализованы — за это отвечает компилятор. Есть поддержка cas операций на аппаратном уровне? Отлично, компилятор генерирует lock free алгоритм, используя test-and-set или compare-and-swap операции процессора. Нету поддержки cas операций? Окей, компилятор делает свой blocking примитив — мьютекс, и тут воля компилятора как он его сделает. Стандарт языка только говорит то, что операция должна быть атомарной, но не говорит как реализовывать саму операцию, реализация — дело компилятора. То есть существует семантика (описывается стандартом) и реализация (зависит от компилятора).

Если cas операции на глубоком уровне я увидел и поизучал немного (ну как, более менее понял: Test-and-Set — это команда XCHG на Intel x86, а Compare-and-Swap — lock cmpxchg ), то мьютекс точно нет смысла изучать, ибо он будет зависеть от компилятора, в отличие от аппаратных команд compare and swap и test-and-set , которые компилятор использует напрямую и код lock free алгоритмов будет плюс минус похожий на различных компиляторах.