Какой алгоритм стоит за сном ()? - PullRequest
40 голосов
/ 06 октября 2008

Теперь я всегда задавался вопросом: как реализовано sleep ()?

Если все дело в использовании API из ОС, то как создается API?

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

Самым известным воплощением sleep () является C (точнее, в библиотеках, которые поставляются с компиляторами C, такими как libc GNU), хотя почти каждый язык сегодня имеет свой эквивалент, но реализация sleep в некоторые языки (например, Bash) - это не то, на что мы смотрим в этом вопросе ...

РЕДАКТИРОВАТЬ: после прочтения некоторых ответов, я вижу, что процесс находится в очереди ожидания. Оттуда я могу угадать две альтернативы, либо

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

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

Ответы [ 8 ]

37 голосов
/ 07 октября 2008

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

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

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

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

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

35 голосов
/ 06 октября 2008

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

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

НТН!

15 голосов
/ 07 октября 2008

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

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

Думайте о процессе - давайте просто поговорим о процессах, а потом перейдем к потокам - как о «том, что операционная система планирует». У процесса есть идентификатор - думайте как целое число - и вы можете думать о нем как о индексе в таблице, содержащей весь контекст этого процесса.

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

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

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

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

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

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

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

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

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

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

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

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

«Событием» может быть что-то вроде: «активировать процесс X» или «пойти туда с дисковым вводом / выводом, потому что оно могло застрять», или «отправить пакет keepalive по этому каналу связи через оптоволоконный канал». там". Что бы ни делала операционная система.

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

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

Просто, да?

10 голосов
/ 07 октября 2008

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

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

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

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

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

9 голосов
/ 06 октября 2008

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

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

8 голосов
/ 06 октября 2008

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

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

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

5 голосов
/ 21 июля 2009

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

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

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

1 голос

glibc 2.21 Linux

Переадресация на системный вызов nanosleep.

glibc является реализацией по умолчанию для C stdlib в большинстве дистрибутивов 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

это какой-то супер СУХОЙ магический формат, проанализированный как:

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.

Это #define s параметров, таких как:

#define SYSCALL_NAME nanosleep

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

#include <syscall-template.S>

Ладно, пока я зайду в игру по расширению макросов.

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

Linux 4.2 x86_64 наносимерный системный вызов

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

Поиск 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 временного уровня

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

...