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

Ответ 1

"Обновление" к вопросу показывает некоторое непонимание того, как работают современные ОС.

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

По сути, ядро ​​пытается честно распределить процессорное время, останавливая процессы, которые слишком долго работают на процессоре. Для упрощенного изображения предположим, что никакому процессу не разрешено использовать процессор более 2 миллисекунд. Таким образом, ядро ​​установило бы таймер на 2 миллисекунды, и пусть процесс будет запущен. Когда таймер запускает прерывание, ядро ​​получает контроль. Он сохраняет текущее состояние текущего процесса (регистры, указатель команд и т.д.), И элемент управления не возвращается к нему. Вместо этого другой процесс выбирается из списка процессов, ожидающих получения CPU, а процесс, который был прерван, переместился в обратную сторону очереди.

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

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

Ответ 2

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

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

НТН!

Ответ 3

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

Какой процесс:

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

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

Процессы проводят много времени сна (ожидание a.k.a.)

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

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

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

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

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

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

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

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

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

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

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

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

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

Простой, да?

Ответ 4

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

Ответ 8

glibc 2.21 Linux

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

glibc - это стандартная реализация для stdlib на большинстве Linux-дистрибутивов Linux.

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

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

который представляет собой некоторый супермагистральный формат DRY, обработанный:

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 [email protected] -x assembler-with-cpp - \
                   $(compile-mkdep-flags)

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

Параметры #define, такие как:

#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() и позволяет запускать другие процессы
• hrtimer_start_expires
• hrtimer_start_range_ns
• TODO: достичь уровня времени arch/x86

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

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