Какой алгоритм стоит за sleep ()?

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

(забавная мелочь: в старых реализациях unix существовала очередь для процессов, для которых был вызван fork (), но для которых не был вызван дочерний процесс созданный. Она, конечно же, называлась очередь вилок.)

ХТ!

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

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

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

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

Процессы тратят много времени на сон (то есть ожидание)

Процесс тратит большую часть своего времени на ожидание. Например, процесс, считывающий или записывающий данные на диск, будет тратить много времени на ожидание поступления данных или подтверждения их наличия на диске. ОС люди используют термины "ожидание" и "спящий" (и "заблокированный") несколько взаимозаменяемы-все это означает, что процесс ожидает чего-то, прежде чем он сможет продолжить свой веселый путь. Это просто сбивает с толку, что OS API sleep() использует базовые механизмы ОС для спящих процессов.

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

Процессы и планирование

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

Планирование:

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

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

Каждый тик приводит к прерыванию работы операционной системы.

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

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

"событие "может быть чем-то вроде" разбудить процесс X", или" пойти пнуть дисковый ввод-вывод вон там, потому что он, возможно, застрял", или"отправить пакет keepalive по той ссылке fibrechannel вон там". Все, что должна была сделать операционная система.

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

В случае спящего процесса он просто делает процесс снова запускаемым.

Просто, да?

Многозадачная операционная система имеет компонент под названием планировщик, этот компонент отвечает за предоставление процессорного времени потокам, вызов sleep говорит ОС не предоставлять процессорное время этому потоку в течение некоторого времени.

См. http://en.wikipedia.org/wiki/Process_states для получения полной информации.

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

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

2. Уровень ядра. когда ОС не нужно ничего делать прямо сейчас, она выполняет команду "hlt". эта инструкция ничего не делает, но она никогда не заканчивается сама по себе. Конечно, аппаратное прерывание обслуживается нормально. Проще говоря, основной цикл ОС выглядит так (с очень-очень далекого расстояния):

   allow_interrupts ();
   while (true) {
     hlt;
     check_todo_queues ();
   }
   

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

Я ничего не знаю о Linux, но могу рассказать вам, что происходит в Windows.

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

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

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

Классически, на x86 это был Intel 8253 или 8254 "программируемый интервальный таймер". В ранних ПК это был отдельный чип на материнской плате, который мог быть запрограммирован процессором для утверждения прерывания (через "программируемый контроллер прерывания", другой дискретный чип) после заданного интервала времени. Функциональность все еще существует, хотя теперь она является крошечной частью гораздо большего. больший кусок схемы материнской платы.

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

Glibc 2.21 Linux

Переходит к системному вызову nanosleep.

Glibc является реализацией по умолчанию для C stdlib на большинстве дистрибутивов Linux desktop.

Как его найти: первый рефлекс:

git ls-files | grep sleep

Это содержит:

sysdeps/unix/sysv/linux/sleep.c

И мы знаем, что:

sysdeps/unix/sysv/linux/

Содержит специфику Linux.

В верхней части этого файла мы видим:

/* We are going to use the `nanosleep' syscall of the kernel.  But the
   kernel does not implement the stupid SysV SIGCHLD vs. SIG_IGN
   behaviour for this syscall.  Therefore we have to emulate it here.  */
unsigned int
__sleep (unsigned int seconds)

Так что если Вы доверяете комментариям, мы в основном закончили.

В внизу:

 weak_alias (__sleep, sleep)

Который в основном говорит:__sleep == sleep. Функция использует nanosleep через:

result = __nanosleep (&ts, &ts);

После greppingg:

git grep nanosleep | grep -v abilist

Мы получаем небольшой список интересных событий, и я думаю, что __nanosleep определяется в:

sysdeps/unix/sysv/linux/syscalls.list 

На линии:

nanosleep   -   nanosleep   Ci:pp   __nanosleep nanosleep

Который представляет собой какой-то Супер Сухой магический формат, разбираемый:

sysdeps/unix/make-syscalls.sh

Затем из каталога сборки:

grep -r __nanosleep

Приводит нас к: /sysd-syscalls который является тем, что make-syscalls.sh порождает и содержит:

#### CALL=nanosleep NUMBER=35 ARGS=i:pp SOURCE=-
ifeq (,$(filter nanosleep,$(unix-syscalls)))
unix-syscalls += nanosleep
$(foreach p,$(sysd-rules-targets),$(foreach o,$(object-suffixes),$(objpfx)$(patsubst %,$p,nanosleep)$o)): \
        $(..)sysdeps/unix/make-syscalls.sh
    $(make-target-directory)
    (echo '#define SYSCALL_NAME nanosleep'; \
     echo '#define SYSCALL_NARGS 2'; \
     echo '#define SYSCALL_SYMBOL __nanosleep'; \
     echo '#define SYSCALL_CANCELLABLE 1'; \
     echo '#include <syscall-template.S>'; \
     echo 'weak_alias (__nanosleep, nanosleep)'; \
     echo 'libc_hidden_weak (nanosleep)'; \
    ) | $(compile-syscall) $(foreach p,$(patsubst %nanosleep,%,$(basename $(@F))),$($(p)CPPFLAGS))
endif

Это похоже на часть файла Makefile. git grep sysd-syscalls показывает, что он включен в:

sysdeps/unix/Makefile:23:-include $(common-objpfx)sysd-syscalls 

compile-syscall похоже, что ключевая часть, поэтому мы находим:

# This is the end of the pipeline for compiling the syscall stubs.
# The stdin is assembler with cpp using sysdep.h macros.
compile-syscall = $(COMPILE.S) -o $@ -x assembler-with-cpp - \
                   $(compile-mkdep-flags)

Обратите внимание, что -x assembler-with-cpp является вариантом gcc.

Это #defines параметры, такие как:

#define SYSCALL_NAME nanosleep

И затем использовать их по адресу:

#include <syscall-template.S>

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

Я думаю, что это создает файл posix/nanosleep.o, который должен быть связан вместе с всё.

Linux 4.2 x86_64 nanosleep syscall

Использует планировщик: это не занятый сон.

Поиск ctags:

sys_nanosleep

Приводит нас к kernel/time/hrtimer.c:

SYSCALL_DEFINE2(nanosleep, struct timespec __user *, rqtp,

hrtimer расшифровывается как таймер высокого разрешения. Отсюда основная линия выглядит так:

• hrtimer_nanosleep
• do_nanosleep
  • set_current_state(TASK_INTERRUPTIBLE); который является прерывистым сном
  • freezable_schedule();, который вызывает schedule() и позволяет другим процессам run
• hrtimer_start_expires
• hrtimer_start_range_ns
• задача: достичь уровня синхронизации arch/x86

Несколько статей об этом:

• https://geeki.wordpress.com/2010/10/30/ways-of-sleeping-in-linux-kernel/
• http://www.linuxjournal.com/article/8144