2008-10-06 31 views
39

Ahora hay algo que siempre me he preguntado: ¿cómo se implementa sleep()?¿Cuál es el algoritmo detrás de sleep()?

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

¿Todo se reduce a utilizar un 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 de C, como la libc de GNU), aunque casi todos los idiomas tienen su equivalente, pero la implementación en algunos idiomas (piense en 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 núcleo se despierta el proceso a su debido tiempo, o
  2. cada vez que se permite que el núcleo de un segmento de tiempo, se sondea el reloj para comprobar si es hora de despertar 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"?

Respuesta

35

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

El kernel no tiene "permitido" un intervalo 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 kernel 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 suspensión es simplemente no en la cola de cosas a la espera de la 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.

+0

IIRC, 10 ms es un intervalo de tiempo típico para los procesos de Linux. Linux puede adelantarse a los procesos en el medio de su segmento de tiempo de 10 ms para lograr una precisión del temporizador mucho mejor que esa. (Antes de que Linux implementara el derecho preferente de compra, algunas personas compilaban su núcleo con 'HZ = 1000' en lugar de' HZ = 100', para obtener jips de 1ms. Véase, por ejemplo, http://serverfault.com/questions/377947/1000- hz-linux-kernel-necessary-if-i-have-tickless-and-high-resolution-timer. Las CPU multi-core han hecho que esto sea mucho menos importante, también, ya que el bloqueo necesario para SMP hace que el respaldo preventivo sea mucho más económico . Y a menudo hay un núcleo libre –

+0

, esta es una buena respuesta, pero el lector también debe entender que solo porque está en la fila para dormir, no está obligado por el tiempo que pidió. Por ejemplo, si se ha suscrito a una señal y la señal se recibe mientras está en la cola de espera, el proceso puede recuperar el tiempo de CPU más rápido. Los eventos de espera de E/S (seleccione ...) tienen un efecto similar. Consulte EINTR errno, que puede devolver la suspensión de Linux. – Eric

35

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:. De más edad implementaciones de UNIX, había una cola de procesos para los cuales tenedor habían sido llamados(), pero para las que no se había creado el proceso hijo Por supuesto, fue llamado la cola tenedor.)

HTH!

+3

Suenas como el autor! –

+0

¿Hay una estructura de datos del núcleo llamada cola de espera en qué núcleo (s)? – EJP

+0

Me enteré en Solaris. –

9

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.

8

No sé nada de Linux, pero puedo decir 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 máquina CPU especial para realizar 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.

9

hay al menos dos niveles diferentes para responder esta pregunta.(Y un montón de otras cosas que se confunden con ella, no voy a tocarlos)

  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. kernel level. 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 bucle principal de un sistema operativo es el siguiente (desde muy muy lejos):

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

    los manejadores de interrupciones simpy añadir 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.

+0

Bien puesto. El nivel de aplicación se explica en: http://stackoverflow.com/a/33639161/895245 –

12

Quizás la tarea 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é . planificador no, cómo funciona la cola del temporizador de esperar que esto sea útil

¿Qué es un proceso:

Piense en un proceso de - vamos a hablar acerca de los procesos, y llegar a las discusiones más tarde - como "el. 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 de hardware (registros, contenido de la unidad de administración de memoria, otro estado del hardware) que, cuando se carga en la máquina, permitirá que el proceso "se ejecute". Hay otros componentes del contexto: listas de archivos abiertos, estado de los manejadores de señal y, lo que es más importante aquí, cosas que el proceso está esperando.

Procesos pasan mucho tiempo durmiendo (también denominado de espera)

Un proceso pasa gran parte de su tiempo de espera. 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 a la espera de otras cosas: paquetes de red para llegar, eventos de selección de ventana o un temporizador para caducar, por ejemplo.

Procesos y Scheduling

Procesos que están esperando se dice que son no ejecutable. 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 coloca el proceso en la cola de ejecución, que realmente no es una cola; es más un montón de todos los procesos que, si el sistema operativo decidiera hacerlo, podría ejecutarse.

Scheduling:

el sistema operativo decide, a intervalos regulares, que procesa debe 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).

The Timer Queue Una computadora tiene un temporizador dentro. Hay muchas maneras en que esto se puede implementar, pero la manera clásica se llama un 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 marca da como resultado 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 deben tratarse", 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 activación X", o "ir a la E/S de disco de patada, porque puede haberse atascado", o "enviar un paquete keepalive en ese enlace de fibrechannel Por ahí". 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 vez. 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 vuelva a ejecutarse.

Simple, ¿eh?

4

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

Clásicamente, en x86 era 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 el Kernel puede implementar la multitarea preventiva.

1

glibc 2.21 Linux

remite a la llamada nanosleep sistema.

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

Así que si confía en los comentarios, que se realizan básicamente.

En la parte inferior:

weak_alias (__sleep, sleep) 

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

result = __nanosleep (&ts, &ts); 

Después greppingg:

git grep nanosleep | grep -v abilist 

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

sysdeps/unix/sysv/linux/syscalls.list 

en la línea :

nanosleep - nanosleep Ci:pp __nanosleep nanosleep 

la que se algún formato magia Super Dry analizado por:

sysdeps/unix/make-syscalls.sh 

Luego, desde el directorio de construcció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 se parece a la parte clave, por lo que nos 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 [email protected] -x assembler-with-cpp - \ 
        $(compile-mkdep-flags) 

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

Este #define s parámetros como:

#define SYSCALL_NAME nanosleep 

y luego usarlos en:

#include <syscall-template.S> 

OK, esto es por lo que voy a entrar en el juego de expansión de la macro por ahora.

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 planificador: no es un sueño ocupado.

ctags búsqueda:

sys_nanosleep 

nos lleva a kernel/time/hrtimer.c:

SYSCALL_DEFINE2(nanosleep, struct timespec __user *, rqtp, 

hrtimer alta la resolución del temporizador.A partir de ahí la línea principal se parece a:

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

Unos artículos al respecto:

+0

No lo haría gastar tanta parte de la respuesta hablando de cómo 'sleep (3)' se implementa sobre 'nanosleep (2) 'por glibc. Eso no es t la parte interesante, IMO. Tal vez pase una oración sobre eso en la parte superior, luego tal vez regrese a la ubicación de un archivo fuente glibc en la parte inferior de la respuesta. Por cierto, un paso simple en un depurador, o el uso de 'strace' para rastrear llamadas al sistema para un programa de prueba, habría sido una manera más fácil de descubrir que' sleep 'de glibc usa 'nanosleep'. Sin embargo, no le ahorraría el problema de pasar por la fuente si quiere ver el código fuente de la capa de traducción real. –

+0

@PeterCordes ¡tienes razón! Me estoy preparando para algún día hackear glibc y satisfacer mi curiosidad. –

Cuestiones relacionadas