### Работа без блокировок: Read-copy-update Невозможно разрешить одновременный доступ для чтения и записи к общим структурам данных без блокировок. В некоторых случаях можно позволить процессу, ведущему запись, обновить структуру данных, даже если ею пользуются другие процессы. Здесь важно обеспечить, чтобы каждый считывающий процесс читал либо старую, либо новую версию данных, но не некую непонятную комбинацию из старой и новой версий. В качестве иллюстрации рассмотрим дерево: X<-A -> B -> C -> D Читатели обходят дерево от корня до листьев. В верхней половине рисунка добавлен новый узел X. Перед тем как сделать этот узел видимым в дереве, мы доводим его до полной готовности: инициализируем все значения в узле X, включая его дочерние указатели. Затем с помощью одной атомарной записи превращаем X в дочерний элемент узла A. Несогласованную версию не сможет считать ни один читатель. В нижней части рисунка последовательно удаляются узлы B и D. Сначала мы перенацеливаем левый дочерний указатель узла A на узел C. Все читатели, попавшие в A, продолжат считывание с узла C и никогда не увидят узел B или D. Иными словами, они увидят только новую версию. В то же время все читатели, находящиеся в этот момент в узле B или D, продолжат чтение, следуя указателям исходной структуры данных, и увидят старую версию. Все будет хорошо, и блокировка вообще не понадобится. Удаление B и D работает без блокировки структуры данных в основном потому, что RCU (Read — Copy — Update, чтение — копирование — обновление) отделяет фазу удаления от фазы восстановления обновления. Но есть и проблема. Пока нет уверенности в полном отсутствии читателей в B или D, мы не можем фактически от них избавиться. Но сколько же должно продлиться ожидание? Мы вынуждены ждать до тех пор, пока эти узлы не оставит последний читатель. RCU обязательно определяет максимальное время, в течение которого читатель может удерживать ссылку на структуру данных. По истечении этого срока память может быть безопасно освобождена. Точнее говоря, читатели получают доступ к структуре данных в области, которая известна как критический раздел чтения (read-side critical section), где может содержаться любой код, поскольку он не заблокирован или не пребывает в режиме ожидания. В этом случае известно максимальное время вынужденного ожидания. А именно нами определяется отсрочка (grace period) в виде любого периода времени, в течение которого известно, что каждый поток будет вне критического раздела для чтения по крайней мере однократно. Поскольку код в критическом разделе для чтения не разрешено блокировать или переводить в режим ожидания, простым критерием будет ожидание до тех пор, пока все потоки не выполнят контекстное переключение. ## Планирование Планировщик - система, которая определяет, какой из процессов или потоков, в состоянии готовности, будет выполняться следующим. Работает по алгоритму планирования. Планировщик наряду с выбором «правильного» процесса должен заботиться также об эффективной загрузке центрального процессора, поскольку переключение процессов является весьма дорогостоящим занятием. Сначала должно произойти переключение из пользовательского режима в режим ядра, затем сохранено состояние текущего процесса, включая сохранение его регистров в таблице процессов для их последующей повторной загрузки. На некоторых системах должна быть сохранена также карта памяти (например, признаки обращения к страницам памяти). После этого запускается алгоритм планирования для выбора следующего процесса. Затем в соответствии с картой памяти нового процесса должен быть перезагружен блок управления памятью. И наконец, новый процесс должен быть запущен. Вдобавок ко всему перечисленному переключение процессов обесценивает весь кэш памяти, заставляя его дважды динамически перезагружаться из оперативной памяти (после входа в ядро и после выхода из него). В итоге слишком частое переключение может поглотить существенную долю процессорного времени, что наводит на мысль: этого нужно избегать. Некоторые планировщики стараются оптимизировать потребление электроэнергии. ## Когда планировать? Cуществуют разнообразные ситуации, требующие вмешательства планировщика. 1. При создании нового процесса необходимо принять решение, какой из процессов выполнять, родительский или дочерний. 2. планировщик должен принять решение, когда процесс завершает работу. Если готовые к выполнению процессы отсутствуют, обычно запускается предоставляемый системой холостой процесс. 3. Когда процесс блокируется в ожидании завершения операции ввода-вывода, на семафоре или по какой-нибудь другой причине, для выполнения должен быть выбран какой-то другой процесс. 4. Планировщик должен принять решение при возникновении прерывания ввода-вывода. Неприоритетный алгоритм планирования выбирает запускаемый процесс, а затем просто дает ему возможность выполняться до тех пор, пока он не заблокируется (в ожидании либо завершения операции ввода-вывода, либо другого процесса), или до тех пор, пока он добровольно не освободит центральный процессор. Приоритетный алгоритм планирования предусматривает выбор процесса и предоставление ему возможности работать до истечения некоторого строго определенного периода времени. Одним из самых старых, простых, справедливых и наиболее часто используемых считается алгоритм циклического планирования. Каждому процессу назначается определенный интервал времени, называемый его квантом, в течение которого ему предоставляется возможность выполнения. Если процесс к завершению кванта времени все еще выполняется, то ресурс центрального процессора у него отбирается и передается другому процессу. Разумеется, если процесс переходит в заблокированное состояние или завершает свою работу до истечения кванта времени, то переключение центрального процессора на другой процесс происходит именно в этот момент. ### Гарантированное планирование Совершенно иной подход к планированию заключается в предоставлении пользователям реальных обещаний относительно производительности, а затем в выполнении этих обещаний. Одно из обещаний, которое можно дать и просто выполнить, заключается в следующем: если в процессе работы в системе зарегистрированы n пользователей, то вы получите 1/n от мощности центрального процессора. ### Лотерейное планирование Основная идея состоит в раздаче процессам лотерейных билетов на доступ к различным системным ресурсам, в том числе к процессорному времени. Когда планировщику нужно принимать решение, в случайном порядке выбирается лотерейный билет, и ресурс отдается процессу, обладающему этим билетом. Применительно к планированию процессорного времени система может проводить лотерейный розыгрыш 50 раз в секунду, и каждый победитель будет получать в качестве приза 20 мс процессорного времени. Более важным процессам, чтобы повысить их шансы на выигрыш, могут выдаваться дополнительные билеты. У лотерейного планирования есть ряд интересных свойств. Например, если появится новый процесс и ему будет выделено несколько билетов, то уже при следующем лотерейном розыгрыше он получит шанс на выигрыш, пропорциональный количеству полученных билетов. Иными словами, лотерейное планирование очень быстро реагирует на изменение обстановки. Взаимодействующие процессы могут по желанию обмениваться билетами. ### Справедливое планирование В этой модели каждому пользователю распределяется некоторая доля процессорного времени и планировщик выбирает процессы, соблюдая это распределение. Таким образом, если каждому из двух пользователей было обещано по 50 % процессорного времени, то они его получат, независимо от количества имеющихся у них процессов. ## Планирование потоков Когда есть несколько процессов и у каждого — несколько потоков, у нас появляется два уровня параллелизма: процессы и потоки. Планирование в таких системах в значительной степени зависит от того, на каком уровне поддерживаются потоки — на пользовательском, на уровне ядра или на обоих уровнях. Сначала рассмотрим потоки на уровне пользователя. Поскольку ядро о существовании потоков не знает, оно работает в обычном режиме, выбирая процесс, скажем, A, и передает процессу A управление до истечения его кванта времени. Планировщик потоков внутри процесса A решает, какой поток запустить, — скажем, A1. Из-за отсутствия таймерных прерываний для многозадачных потоков этот поток может продолжать работу, сколько ему понадобится. Если он полностью израсходует весь квант времени, отведенный процессу, ядро выберет для запуска другой процесс. Теперь рассмотрим случай, когда потоки процесса A выполняют непродолжительную относительно доли выделенного процессорного времени работу, например работу продолжительностью 5 мс при кванте времени 50 мс. Следовательно, каждый из них запускается на небольшой период времени, возвращая затем центральный процессор планировщику потоков. При этом, перед тем как ядро переключится на процесс B,может получиться следующая последовательность: A1, A2, A3, A1, A2, A3, A1, A2, A3, A1. Теперь рассмотрим ситуацию с потоками, реализованными на уровне ядра. Здесь конкретный запускаемый поток выбирается ядром. Ему не нужно учитывать принадлежность этого потока конкретному процессу, но если понадобится, то он может это сделать. Потоку выделяется квант времени, по истечении которого его работа приостанавливается. Если выделен квант 50 мс, а запущен поток, который блокируется через 5 мс, то очередность потоков на период продолжительностью 30 мс может быть следующей: A1, B1, A2, B2, A3, B3, что невозможно получить при таких параметрах на пользовательском уровне. Потоки на уровне пользователя и потоки на уровне ядра различаются в основном производительностью работы. Для переключения потоков, реализованных на уровне пользователя, требуется лишь небольшое количество машинных команд, а для потоков на уровне ядра требуется полное контекстное переключение, смена карты памяти и аннулирование кэша, что выполняется на несколько порядков медленнее. В то же время поток на уровне ядра, заблокированный на операции ввода-вывода, не вызывает приостановку всего процесса, как поток на уровне пользователя. Поскольку ядру известно, что на переключение с потока из процесса A на поток из процесса B затрачивается больше времени, чем на запуск второго потока из процесса A (из-за необходимости изменения карты памяти и обесценивания кэша памяти), то оно может учесть эти сведения при принятии решения.