¿Cuál es el algoritmo detrás de sleep()?

algorithm

Question

Ahora hay algo que siempre me he preguntado: ¿cómo se implementa sleep ()?

Si todo se trata de usar una API del SO, ¿cómo se hace la API?

¿Todo se reduce a usar código de máquina especial en la CPU? ¿Esa CPU necesita un coprocesador especial u otro artilugio sin el cual no puedas dormir ()?

La encarnación más conocida de sleep () está en C (para ser más preciso, en las bibliotecas que vienen con compiladores C, como la libc de GNU), aunque casi todos los idiomas actuales tienen su equivalente, pero la implementación de sleep en algunos idiomas ( pensar Bash) no es lo que estamos viendo en esta pregunta ...

EDITAR: Después de leer algunas de las respuestas, veo que el proceso se coloca en una cola de espera. A partir de ahí, puedo adivinar dos alternativas, ya sea

1. se establece un temporizador para que el kernel active el proceso a su debido tiempo, o
2. cada vez que se le permite al kernel un intervalo de tiempo, consulta el reloj para verificar si es hora de activar un proceso.

Las respuestas solo mencionan la alternativa 1. Por lo tanto, pregunto: ¿cómo se comporta este temporizador? Si se trata de una interrupción simple para que el kernel active el proceso, ¿cómo puede el kernel pedirle al temporizador que "me despierte en 140 milisegundos para que pueda poner el proceso en estado de ejecución"?

Answer 1

Esencialmente, sí, hay un "artilugio especial", y es importante para mucho más que solo dormir ().

Clásicamente, en x86 este fue un Intel 8253 u 8254 "temporizador de intervalo programable". En las primeras PC, se trataba de un chip separado en la placa base que la CPU podía programar para activar una interrupción (a través del "Controlador de interrupción programable", otro chip discreto) después de un intervalo de tiempo preestablecido. La funcionalidad aún existe, aunque ahora es una pequeña parte de una gran parte del circuito de la placa base.

El SO todavía hoy programa el PIT para reactivarlo regularmente (en versiones recientes de Linux, una vez cada milisegundo por defecto), y así es como Kernel puede implementar multitareas preventivas.

Answer 2

Hay una estructura de datos del núcleo llamada cola de espera. Es una cola de prioridad. Cada vez que se agrega un proceso a la cola de espera, se calcula el tiempo de expiración del proceso que se va a despertar más tarde y se establece un temporizador. En ese momento, el trabajo caducado se elimina de la cola y el proceso reanuda la ejecución.

(trivia divertida: en las implementaciones anteriores de Unix, había una cola para los procesos para los que se había llamado a fork (), pero para los cuales no se había creado el proceso hijo. Por supuesto, se llamaba la cola de espera ).

HTH!

Answer 3

La "actualización" de la pregunta muestra algunos malentendidos sobre cómo funcionan los sistemas operativos modernos.

El kernel no tiene "permitido" un segmento de tiempo. El kernel es lo que da cortes de tiempo a los procesos del usuario. El "temporizador" no está configurado para reactivar el proceso de suspensión: está configurado para detener el proceso en ejecución.

En esencia, el núcleo intenta distribuir de manera equitativa el tiempo de CPU al detener los procesos que están en la CPU demasiado tiempo. Para una imagen simplificada, digamos que ningún proceso puede usar la CPU más de 2 milisegundos. Entonces, el kernel establecería el temporizador a 2 milisegundos, y dejaría que el proceso se ejecutara. Cuando el temporizador dispara una interrupción, el kernel obtiene el control. Guarda el estado actual del proceso en ejecución (registros, puntero de instrucción, etc.) y no se devuelve el control. En su lugar, se selecciona otro proceso de la lista de procesos que esperan recibir CPU, y el proceso que se interrumpió pasa al final de la cola.

El proceso de dormir simplemente no está en la cola de cosas que esperan CPU. En cambio, está almacenado en la cola para dormir. Cada vez que Kernel obtiene la interrupción del temporizador, se comprueba la cola de espera y los procesos cuyo tiempo se ha transferido a la cola de "espera de la CPU".

Esto es, por supuesto, una gran simplificación. Se necesitan algoritmos muy sofisticados para garantizar la seguridad, la equidad, el equilibrio, priorizar, evitar la inanición, hacerlo todo rápido y con la mínima cantidad de memoria utilizada para los datos del kernel.

Answer 4

No sé nada sobre Linux, pero puedo decirte lo que sucede en Windows.

Sleep () hace que el segmento de tiempo del proceso finalice inmediatamente para devolver el control al sistema operativo. Luego, el sistema operativo configura un objeto kernel de temporizador que se señala después de que transcurra el tiempo. El sistema operativo no dará ese proceso más tiempo hasta que se señale el objeto kernel. Incluso entonces, si otros procesos tienen una prioridad mayor o igual, aún puede esperar un poco antes de permitir que el proceso continúe.

El sistema operativo utiliza un código de CPU especial para hacer el cambio de proceso. Esas funciones no se pueden acceder por código de modo de usuario, por lo que se accede estrictamente por llamadas de API en el sistema operativo.

Answer 5

Quizás el trabajo principal de un sistema operativo es ocultar la complejidad de una pieza de hardware real del escritor de la aplicación. Por lo tanto, cualquier descripción de cómo funciona el sistema operativo corre el riesgo de volverse realmente complicado, realmente rápido. En consecuencia, no voy a tratar con todos los "qué pasaría si" y sí peros "que un sistema operativo real tiene que tratar. Voy a describir, a un alto nivel conceptual, qué es un proceso, qué el planificador lo hace, cómo funciona la cola del temporizador. Afortunadamente esto es útil.

¿Qué es un proceso?

Piense en un proceso, solo hablemos de procesos y lleguemos a los hilos más tarde, como "lo que el sistema operativo programa". Un proceso tiene una ID, piense en un entero, y puede pensar en ese entero como un índice en una tabla que contiene todo el contexto de ese proceso.

El contexto es la información del hardware (registros, contenido de la unidad de administración de memoria, otro estado del hardware) que, cuando se carga en la máquina, permite que el proceso "funcione". Existen otros componentes del contexto: listas de archivos abiertos, estado de los manejadores de señal y, lo que es más importante, cosas que el proceso está esperando .

Los procesos pasan mucho tiempo durmiendo (también conocido como espera)

Un proceso pasa mucho tiempo esperando. Por ejemplo, un proceso que lee o escribe en el disco pasará mucho tiempo esperando que lleguen los datos o que se confirme que está fuera del disco. Los usuarios de sistemas operativos usan los términos "esperar" y "dormir" (y "bloquear") de forma intercambiable, lo que significa que el proceso está esperando que algo suceda antes de que pueda continuar de manera feliz. Es confuso que la API del sistema operativo sleep () pase a utilizar los mecanismos subyacentes del sistema operativo para los procesos inactivos.

Los procesos pueden estar esperando otras cosas: paquetes de red para llegar, eventos de selección de ventana o un temporizador para caducar, por ejemplo.

Procesos y programación

Se dice que los procesos que están esperando son no ejecutables . No van a la cola de ejecución del sistema operativo. Pero cuando ocurre el evento que el proceso está esperando, hace que el sistema operativo mueva el proceso del estado no ejecutable al ejecutable. Al mismo tiempo, el sistema operativo pone el proceso en la cola de ejecución, que en realidad no es una cola, es más un montón de todos los procesos que, si el sistema operativo decide hacerlo, podría ejecutarse.

Programación:

el sistema operativo decide, a intervalos regulares, qué procesos deberían ejecutarse. El algoritmo por el cual el sistema operativo decide hacerlo se llama, algo sin sorpresa, el algoritmo de programación. Los algoritmos de programación varían desde dead-simple ("todo el mundo puede funcionar durante 10 ms, y luego se ejecuta el siguiente tipo en la cola") hasta mucho más complicado (teniendo en cuenta la prioridad del proceso, la frecuencia de ejecución, los plazos de ejecución, dependencias entre procesos, bloqueos encadenados y todo tipo de otro tema complicado).

La cola del temporizador Una computadora tiene un temporizador dentro. Hay muchas maneras en que esto se puede implementar, pero la manera clásica se llama temporizador periódico . Un temporizador periódico marca a intervalos regulares: en la mayoría de los sistemas operativos actuales, creo que esta tasa es 100 veces por segundo, 100 Hz, cada 10 milisegundos. Usaré ese valor en lo que sigue como una tasa concreta, pero sé que la mayoría de los sistemas operativos que valen la pena se pueden configurar con diferentes tics, y muchos no usan este mecanismo y pueden proporcionar una precisión del temporizador mucho mejor. Pero yo divago.

Cada tic resulta en una interrupción en el sistema operativo.

Cuando el SO maneja esta interrupción de temporizador, incrementa su idea de tiempo del sistema en otros 10 ms. Luego, mira la cola del temporizador y decide qué eventos de esa cola necesitan ser tratados.

La cola del temporizador realmente es una cola de "cosas que necesitan ser tratadas", que llamaremos eventos. Esta cola se ordena por tiempo de caducidad, los eventos más cercanos primero.

Un "evento" puede ser algo así como, "proceso de despertador X", o "ir a la E / S de disco de patada allí, porque puede haberse atascado", o "enviar un paquete de keepalive en ese enlace de fibrecanal". Lo que sea que el sistema operativo deba haber hecho.

Cuando tiene una cola ordenada de esta manera, es fácil administrar la eliminación de llamadas. El sistema operativo simplemente mira el encabezado de la cola y disminuye el "tiempo de expiración" del evento en 10 ms cada tic. Cuando el tiempo de caducidad va a cero, el SO dequeue ese evento y hace lo que sea necesario.

En el caso de un proceso de inactividad, simplemente hace que el proceso pueda ejecutarse nuevamente.

Simple, ¿eh?

Answer 6

Un sistema operativo multitarea tiene un componente llamado programador, este componente es responsable de dar tiempo de CPU a los hilos, llamar a dormir le dice al sistema operativo que no le dé tiempo de CPU a este hilo durante un tiempo.

ver http://en.wikipedia.org/wiki/Process_states para más detalles.

Answer 7

hay al menos dos niveles diferentes para responder esta pregunta. (y muchas otras cosas que se confunden con él, no los tocaré)

1. un nivel de aplicación, esto es lo que hace la biblioteca C Es una llamada a un sistema operativo simple, simplemente le dice al sistema operativo que no conceda tiempo de CPU a este proceso hasta que haya pasado el tiempo. El sistema operativo tiene una cola de aplicaciones suspendidas y algo de información sobre lo que están esperando (por lo general, en tiempo o en algunos datos).

2. nivel del kernel cuando el sistema operativo no tiene nada que hacer en este momento, ejecuta una instrucción ''hlt''. esta instrucción no hace nada, pero nunca termina sola. Por supuesto, una interrupción de hardware se atiende normalmente. En pocas palabras, el ciclo principal de un sistema operativo se ve así (desde muy muy lejos):

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

   los manejadores de interrupciones simpy agregan cosas a las colas de tareas pendientes. El reloj de tiempo real está programado para generar interrupciones ya sea periódicamente (a una tasa fija), o a algún tiempo fijo en el futuro cuando el próximo proceso desea ser despertado.

Answer 8

glibc 2.21 Linux

Reenvía a la nanosleep sistema nanosleep .

glibc es la implementación predeterminada para C stdlib en la mayoría de las distribuciones de escritorio de Linux.

Cómo encontrarlo: el primer reflejo es:

git ls-files | grep sleep

Este contiene:

sysdeps/unix/sysv/linux/sleep.c

y sabemos que:

sysdeps/unix/sysv/linux/

contiene los detalles de Linux.

En la parte superior de ese archivo vemos:

/* 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)

Entonces, si confías en los comentarios, básicamente terminamos.

En el fondo:

 weak_alias (__sleep, sleep)

que básicamente dice __sleep == sleep . La función usa nanosleep través de:

result = __nanosleep (&ts, &ts);

Después de greppingg:

git grep nanosleep | grep -v abilist

obtenemos una pequeña lista de sucesos interesantes, y creo que __nanosleep se define en:

sysdeps/unix/sysv/linux/syscalls.list 

en la línea:

nanosleep - nanosleep Ci:pp __nanosleep nanosleep

que es un formato mágico super DRY analizado por:

sysdeps/unix/make-syscalls.sh

Luego, desde el directorio de compilación:

grep -r __nanosleep

Nos lleva a: /sysd-syscalls que es lo que make-syscalls.sh genera y contiene:

#### 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

Parece parte de un Makefile. git grep sysd-syscalls muestra que está incluido en:

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

compile-syscall parece a la parte clave, por lo que encontramos:

# 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)

Tenga en cuenta que -x assembler-with-cpp es una opción de gcc .

Estos parámetros de #define como:

#define SYSCALL_NAME nanosleep

y luego usarlos en:

#include <syscall-template.S>

OK, esto es lo más lejos que voy a ir en el juego de macro expansión por el momento.

Creo que esto genera el archivo posix/nanosleep.o que debe estar vinculado junto con todo.

Linux 4.2 x86_64 nanosleep syscall

Utiliza el programador: no es un sueño ocupado.

Ctags de búsqueda:

sys_nanosleep

Nos lleva a kernel/time/hrtimer.c :

SYSCALL_DEFINE2(nanosleep, struct timespec __user *, rqtp,

hrtimer significa Temporizador de Alta Resolución. A partir de ahí, la línea principal se ve así:

• hrtimer_nanosleep
• do_nanosleep
  • set_current_state(TASK_INTERRUPTIBLE); que es sueño interrumpible
  • freezable_schedule(); que llama a schedule() y permite que se ejecuten otros procesos
• hrtimer_start_expires
• hrtimer_start_range_ns
• TODO: alcanzar el nivel de sincronización arch/x86

Algunos artículos al respecto:

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