Exponer el no determinismo resultante del programador de subprocesos del sistema operativo

10

Como todos sabemos, los sistemas operativos modernos tienen programadores de subprocesos que pueden elegir diferentes órdenes para programar sus subprocesos en función de la lógica interna de la cual su código no está al tanto. Normalmente, usted crea su código multiproceso para asegurarse de que este no determinismo impuesto sobre usted no afecte significativamente su salida.

El objetivo aquí es lo contrario. Produzca un programa que imprima los enteros en el intervalo [0,99] pero en un orden que variará de una ejecución a otra debido al programador de subprocesos del sistema operativo.

Debe lograr "suficiente no determinismo", definido como:

En 10 series secuenciales de 10 pruebas, su programa debe producir al menos 9 permutaciones únicas dentro de cada prueba. Es posible que tenga un número razonable de series de pruebas fallidas a cada lado de los 10 consecutivos que suceden.

O, para decirlo de otra manera, necesita 100 ejecuciones de su programa donde cada bloque de 10 ejecuciones tiene como máximo dos ejecuciones que generan lo mismo.

Por lo tanto, intercambiar ocasionalmente 98 y 99 no lo cortará.

Este es un , por lo que gana la respuesta que utiliza la menor cantidad de bytes.

Minucias

  • Escriba su salida en stdout, una entrada por línea
  • Si altera el formato haciendo que dos hilos intercalen las escrituras de caracteres en stdout (incluso ocasionalmente) resultando en números de tres dígitos o líneas vacías, su resultado no es válido
  • La única excepción a la regla anterior es que puede emitir una sola línea vacía después de imprimir el último número requerido (de nada)
  • Si alguna vez omite o duplica cualquier valor requerido, su resultado no es válido
  • Su programa no necesita ser no determinista en un solo procesador central (aunque felicitaciones si es así)
  • Su programa puede usar hilos / fibras verdes que en realidad no son administrados por el kernel del sistema operativo si aún cumple con los otros requisitos del desafío y el sistema de hilos es parte de su idioma o la biblioteca estándar para su idioma
  • El tiempo de ejecución para su programa debe ser confiablemente inferior a 5 segundos en un procesador moderno
  • No puede especificar cambios en el entorno que suceden fuera de su programa, como esperas o cambios en la configuración; su programa debe pasar si se ejecuta 100 veces consecutivas o con una hora entre cada ejecución o 100 veces en paralelo (eso probablemente ayudaría en realidad ...)
  • Puede usar un coprocesador como una GPU o Xeon Phi y su propio mecanismo de programación interno para las tareas. Las reglas se aplican a esto de la misma manera que se aplican a los hilos verdes.
  • Siéntase libre de provocar al programador con todo tipo de durmientes, rendimientos y otros trucos siempre que obedezca las reglas especificadas en esta publicación

Operaciones prohibidas

La única fuente de no determinismo a la que puede recurrir es cuando el planificador programa sus hilos para que se ejecuten. La siguiente lista no es exhaustiva, solo tiene la intención de proporcionar ejemplos de cosas que no está permitido hacer, ya que admiten otras fuentes de no determinismo.

  • Accediendo directa o indirectamente a cualquier tipo de PRNG o capacidad de RNG de hardware (a menos que sea como parte inherente del programador).
  • Lectura en cualquier tipo de entrada (hora del sistema, sistema de archivos, red, etc.)
  • Lectura de ID de hilo o ID de proceso
  • Personalizar el planificador del sistema operativo; debe usar un programador estándar del sistema operativo de un sistema operativo principal
  • También está prohibido personalizar su programador de hilo / fibra verde. Esto significa que si escribe un idioma para este desafío, debe usar hilos del sistema operativo.

Validar respuesta

Preferiblemente, una respuesta funcionaría en todos los sistemas operativos comunes y los procesadores modernos, con felicitaciones proporcionales a la amplitud del soporte. Sin embargo, este no es un requisito del desafío. Como mínimo, una respuesta debe admitir un procesador SMP moderno y un SO moderno. Probaré las principales respuestas en la medida de mi disponibilidad de hardware.

  • Si su entrada no produce la salida requerida en un i7 5960x con Windows 10 v1607 x64, especifique el entorno requerido
  • Si es algo que puedo reproducir fácilmente con VMWare Workstation, proporcione las especificaciones exactas del sistema operativo y VM
  • Si no se puede producir en cualquiera de esas condiciones, grabe una captura de pantalla simultánea de la prueba como se describe en la sección del encabezado y una grabación de video portátil de su pantalla con la interacción del mouse y el teclado (o cualquier esquema de control de su computación no estándar usos del dispositivo) claramente visibles y publique ambos videos junto con su respuesta e incluya una explicación de por qué funciona
  • Alternativamente, obtenga un usuario de buena reputación (que no sea usted) con hardware compatible para reproducir el resultado y responder por usted
  • Si su entrada está en un lenguaje de programación exótico que un desarrollador típico no configurará para compilar / jit / interpretar, proporcione instrucciones de configuración
  • Si su entrada depende de una versión específica del intérprete de JVM / Python / otro, especifique qué
  • Si se necesitan más de 10 minutos consecutivos para obtener sus 10 series secuenciales de pruebas exitosas en mis pruebas, fracasará (así que no permita que la condición de éxito sea una ocurrencia extraña, especialmente si está cerca de la parte superior tiempo de ejecución limitado)
Techrocket9
fuente
44
-1 para el "Si me aburro ....". Yo diría que especifique exactamente cuánto tiempo puede tomar.
Rɪᴋᴇʀ
@EasterlyIrk También dice 'confiablemente menos de cinco segundos en una CPU moderna'
Pavel
@Pavel eso no es a lo que me refiero. Las 10 pruebas exitosas no están relacionadas con los 5 segundos.
Rɪᴋᴇʀ
@EasterlyIrk Bastante justo, ahora son 10 minutos.
Techrocket9
@ Techrocket9 genial, downvote rescindido.
Rɪᴋᴇʀ

Respuestas:

4

Perl 6 , 27 bytes

await map {start .say},^100

Explicación:

      map {          },^100  # Iterate over the range 0..99, and for each of number:
           start             # Send the following task to a thread pool of OS threads:
                 .say        # Print the number, followed by a newline.
await                        # Wait until all tasks have completed.

Espero que esto satisfaga la tarea. (Si no es así, por favor hágamelo saber).

Pruebas:

El script de shell que utilicé para probar suficiente no determinismo:

#!/usr/bin/bash
for i in {1..10}; do
    set=""
    for j in {1..10}; do
        set="${set}$(perl6 nondet.p6 | tr '\n' ',')\n"
    done
    permutations="$(echo -e "$set" | head -n -1 | sort | uniq | wc -l)"
    echo -n "$permutations "
done

Para mí, esto produce:

10 10 10 10 10 10 10 10 10 10 

Instrucciones de configuración:

Ejecuté la prueba con un Rakudo Perl 6 actualizado en Linux de 64 bits, aunque supongo que funcionará en otras plataformas.

La página de descarga de Rakudo tiene instrucciones de configuración. Compilé el mío de git así:

git clone git@github.com:rakudo/rakudo.git
cd rakudo
perl Configure.pl --gen-moar --make-install
export PATH="$(pwd)/install/bin/:$PATH"

Pruébalo en línea:

O simplemente pruébelo en línea, usando este enlace Pruébelo en línea provisto por @ b2gills. Revisé algunas ejecuciones y obtuve un orden diferente cada vez, pero no tuve la paciencia para ejecutarlo 100 veces a través de esa interfaz en línea.

smls
fuente
Validado en Windows 10 x64 en un i7 5960x con Rakudo Perl versión 2016.11
Techrocket9
4

bash, 32 28 bytes

for i in {0..99};{ echo $i&}

Ejecuté esto 100 veces y obtuve 100 resultados diferentes.

Editar: Guardado 4 bytes gracias a @DigitalTrauma.

Neil
fuente
Me ganaste a eso. En realidad, el mío es un poco más corto for i in {0..99};{ echo $i&}, pero publicaste primero, puedes tomarlo :)
Digital Trauma
Aquí hay una forma de probarlo en TIO. Esto hace 10 ejecuciones del script, capturando la salida de cada ejecución, md5ing la salida de cada ejecución. Podemos ver que los md5 son diferentes cada vez. Los md5 se ordenan para hacer posibles duplicados aparentes.
Trauma digital el
@DigitalTrauma ¡Indocumentado pero agradable!
Neil
1
Sí, hay un consejo para esto.
Trauma digital el
Curiosamente, esto no logra "suficiente no determinismo" cuando se ejecuta en el bash-on-windows oficial de Microsoft en un E5-2699 v4, pero funciona en una VM RHEL Workstation con 4 núcleos en la misma máquina para que pase.
Techrocket9
2

PowerShell , 54 46 44 39 bytes

workflow p{foreach -p($i in 0..99){$i}}

Los flujos de trabajo de PowerShell no son compatibles con TIO, por lo que no puede probarlo allí. Sin embargo, debería funcionar muy bien en su máquina con Windows 10 :)

Define una función pque generará la lista de números cuando se invoque.

Sincronización

Una sola ejecución se ejecuta de manera confiable en aproximadamente 600 ms en mi máquina. Las 100 pruebas definidas a continuación terminan en menos de 2 minutos.

Pruebas

Aquí hay un código completo para probarlo:

workflow p{foreach -p($i in 0..99){$i}}
#workflow p{foreach($i in 0..99){$i}}
# uncomment above to prove testing methodology does detect duplicates

1..10 | % {
    $set = $_
    Write-Host "Set $set of 10"
    1..10 | % -b {
        $runs = @()
    } -p {
        $run = $_
        Write-Host "-- Run $run of 10 in set $set"
        $runs += "$(p)"
    } -e {
        Write-Host "-- There were $(10-($runs|Get-Unique).Count) duplicate runs in set $set"
    }
}

Salida en mi máquina:

Set 1 of 10
-- Run 1 of 10 in set 1
-- Run 2 of 10 in set 1
-- Run 3 of 10 in set 1
-- Run 4 of 10 in set 1
-- Run 5 of 10 in set 1
-- Run 6 of 10 in set 1
-- Run 7 of 10 in set 1
-- Run 8 of 10 in set 1
-- Run 9 of 10 in set 1
-- Run 10 of 10 in set 1
-- There were 0 duplicate runs in set 1
Set 2 of 10
-- Run 1 of 10 in set 2
-- Run 2 of 10 in set 2
-- Run 3 of 10 in set 2
-- Run 4 of 10 in set 2
-- Run 5 of 10 in set 2
-- Run 6 of 10 in set 2
-- Run 7 of 10 in set 2
-- Run 8 of 10 in set 2
-- Run 9 of 10 in set 2
-- Run 10 of 10 in set 2
-- There were 0 duplicate runs in set 2
Set 3 of 10
-- Run 1 of 10 in set 3
-- Run 2 of 10 in set 3
-- Run 3 of 10 in set 3
-- Run 4 of 10 in set 3
-- Run 5 of 10 in set 3
-- Run 6 of 10 in set 3
-- Run 7 of 10 in set 3
-- Run 8 of 10 in set 3
-- Run 9 of 10 in set 3
-- Run 10 of 10 in set 3
-- There were 0 duplicate runs in set 3
Set 4 of 10
-- Run 1 of 10 in set 4
-- Run 2 of 10 in set 4
-- Run 3 of 10 in set 4
-- Run 4 of 10 in set 4
-- Run 5 of 10 in set 4
-- Run 6 of 10 in set 4
-- Run 7 of 10 in set 4
-- Run 8 of 10 in set 4
-- Run 9 of 10 in set 4
-- Run 10 of 10 in set 4
-- There were 0 duplicate runs in set 4
Set 5 of 10
-- Run 1 of 10 in set 5
-- Run 2 of 10 in set 5
-- Run 3 of 10 in set 5
-- Run 4 of 10 in set 5
-- Run 5 of 10 in set 5
-- Run 6 of 10 in set 5
-- Run 7 of 10 in set 5
-- Run 8 of 10 in set 5
-- Run 9 of 10 in set 5
-- Run 10 of 10 in set 5
-- There were 0 duplicate runs in set 5
Set 6 of 10
-- Run 1 of 10 in set 6
-- Run 2 of 10 in set 6
-- Run 3 of 10 in set 6
-- Run 4 of 10 in set 6
-- Run 5 of 10 in set 6
-- Run 6 of 10 in set 6
-- Run 7 of 10 in set 6
-- Run 8 of 10 in set 6
-- Run 9 of 10 in set 6
-- Run 10 of 10 in set 6
-- There were 0 duplicate runs in set 6
Set 7 of 10
-- Run 1 of 10 in set 7
-- Run 2 of 10 in set 7
-- Run 3 of 10 in set 7
-- Run 4 of 10 in set 7
-- Run 5 of 10 in set 7
-- Run 6 of 10 in set 7
-- Run 7 of 10 in set 7
-- Run 8 of 10 in set 7
-- Run 9 of 10 in set 7
-- Run 10 of 10 in set 7
-- There were 0 duplicate runs in set 7
Set 8 of 10
-- Run 1 of 10 in set 8
-- Run 2 of 10 in set 8
-- Run 3 of 10 in set 8
-- Run 4 of 10 in set 8
-- Run 5 of 10 in set 8
-- Run 6 of 10 in set 8
-- Run 7 of 10 in set 8
-- Run 8 of 10 in set 8
-- Run 9 of 10 in set 8
-- Run 10 of 10 in set 8
-- There were 0 duplicate runs in set 8
Set 9 of 10
-- Run 1 of 10 in set 9
-- Run 2 of 10 in set 9
-- Run 3 of 10 in set 9
-- Run 4 of 10 in set 9
-- Run 5 of 10 in set 9
-- Run 6 of 10 in set 9
-- Run 7 of 10 in set 9
-- Run 8 of 10 in set 9
-- Run 9 of 10 in set 9
-- Run 10 of 10 in set 9
-- There were 0 duplicate runs in set 9
Set 10 of 10
-- Run 1 of 10 in set 10
-- Run 2 of 10 in set 10
-- Run 3 of 10 in set 10
-- Run 4 of 10 in set 10
-- Run 5 of 10 in set 10
-- Run 6 of 10 in set 10
-- Run 7 of 10 in set 10
-- Run 8 of 10 in set 10
-- Run 9 of 10 in set 10
-- Run 10 of 10 in set 10
-- There were 0 duplicate runs in set 10
briantista
fuente
Curiosamente, esto lleva 51 segundos por ejecución en mi caja E5-2699 v4, pero solo .7 segundos en mi computadora portátil i5-5200U. Alcanza el grado requerido de no determinismo en la computadora portátil mientras llega a menos de 5 segundos como máximo, por lo que pasa. Aparentemente, el planificador de PowerShell no funciona bien con muchos núcleos y tareas cortas.
Techrocket9
Y tarda 58 segundos en el i7 5960x
Techrocket9
Hm ... 74 segundos en una computadora portátil i5-6300U. Tal vez sea un problema con Windows 10 o PowerShell 5.1, ya que el i5-5200U es la única máquina entre las probadas que no ejecuta Win10 (está ejecutando 8.1).
Techrocket9
@ Techrocket9 raro, estaba probando en Win10, PS 5.1. En ISE sin embargo.
briantist
2

GCC en Linux, 47 bytes

main(i){for(i=99;fork()?i--:!printf("%d\n",i););}

Esto me dio resultados diferentes casi siempre, después de haber sido compilado con gcc(sin banderas) la versión 4.9.2. Específicamente, estaba en Debian 8.6 de 64 bits (versión del kernel 3.16.31).

Explicación

Si fork()devuelve cero (proceso hijo), ise imprime el valor de y la condición del bucle es falsa, porque printfdevolverá un valor mayor que cero. En el proceso padre, la condición del bucle es justa i--.

Dan Getz
fuente
Igual que la respuesta bash. Determinista en Windows, pero pasa Linux (en este caso Debian).
Techrocket9