Expose nondeterminism resulting from the OS thread scheduler

Question

As we all know, modern operating systems have thread schedulers that can pick different orders to schedule your threads based on internal logic which your code is not privy to. Normally you architect your multithreaded code to ensure that this nondeterminism imposed on you does not meaningfully affect your output.

The goal here is the opposite. Produce a program which prints the integers in the interval [0,99] but in an order which will vary from run to run due to the OS thread scheduler.

You must achieve "enough nondeterminism", defined as:

In 10 sequential sets of 10 trials your program must produce at least 9 unique permutations within each trial. You may have a reasonable number of failed sets of trials on either side of the consecutive 10 which succeed.

Or, to put it another way, you need 100 runs of your program where each block of 10 runs has at most two runs which output the same thing.

So, occasionally swapping 98 and 99 won't cut it.

This is a code-golf, so the answer which uses the fewest bytes wins.

Minutiae

• Write your output to stdout, one entry per line
• If you mangle the format by having two threads interleave character writes to stdout (even occasionally) resulting in things like three digit numbers or empty lines, your result is invalid
• The only exception to the above rule is that you may emit a single empty line after printing the last required number (you're welcome)
• If you ever miss or duplicate any required values your result is invalid
• Your program does not need to be nondeterministic on a single core processor (though kudos if it is)
• Your program may use green threads/fibers which are not actually managed by the OS kernel iff it still meets the other requirements of the challenge and the threading system is part of your language or the standard library for your language
• Runtime for your program must be reliably under 5 seconds on a modern processor
• You do not get to specify changes to the environment which happen outside of your program such as waits or settings changes; your program should pass whether run 100ish times back to back or with an hour between each run or 100ish times in parallel (that would probably help actually...)
• You may use a coprocessor such as a GPU or Xeon Phi and its own internal scheduling mechanism for tasks. The rules apply to this the same way they apply to green threads.
• Feel free to provoke the scheduler with all manner of sleeps, yields, and other tricks as long as you obey the rules specified in this post

Banned Operations

The only source of nondeterminism you are allowed to draw on is when the scheduler schedules your threads to run. The following list is not exhaustive, intended only to provides examples of things you are not allowed to do as they admit other sources of nondeterminism.

• Directly or indirectly accessing any sort of PRNG or hardware RNG capability (unless it is as an inherent part of the scheduler).
• Reading in any kind of input (system time, filesystem, network, etc.)
• Reading thread IDs or Process IDs
• Customizing the OS scheduler; you must use a standard OS scheduler from a mainstream OS
• Customizing your green thread/fiber scheduler is also prohibited. This means that if you write a language for this challenge you must use OS threads.

Answer Validation

Preferably an answer would work across all common OSes and modern processors, with kudos awarded proportional to the breadth of support. However, this is not a requirement of the challenge. At a minimum an answer must support one modern SMP processor and modern OS. I'll test leading answers to the extent of my hardware availability.

• If your entry will not produce the required output on an i7 5960x running Windows 10 v1607 x64, specify the environment required
• If it's something I can easily reproduce with VMWare Workstation, provide the exact OS and VM specs
• If it can't be produced in under either of those conditions, record a simultaneous screen capture of the test as described in the header section and a handheld video recording of your screen with your mouse and keyboard interaction (or whatever control scheme your nonstandard computation device uses) clearly visible and post both videos along with your answer and include an explanation of why it works
• Alternately, get a reputable long-standing user (who is not you) with matching hardware to reproduce the result and vouch for you
• If your entry is in an exotic programming language that a typical developer won't be set up to compile/jit/interpret, provide setup instructions
• If you entry depends on a specific version of the JVM/Python interpreter/other, specify which
• If it takes more than 10 minutes of back-to-back runs to get your 10 successful sequential sets of trials in my testing you fail (so don't let the success condition be a freak occurrence, especially if you're near the upper runtime bound)

Answer 1

Perl 6, 27 bytes

await map {start .say},^100

Explanation:

      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.

I hope this satisfies the task. (If not, please let me know).

Testing:

The shell script I used to test sufficient nondeterminism:

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

For me, this outputs:

10 10 10 10 10 10 10 10 10 10 

Setup instructions:

I ran the test with an up-to-date Rakudo Perl 6 on 64bit Linux, though I guess it'll work on other platforms.

The Rakudo download page has setup instructions. I compiled mine from git like this:

git clone [email protected]:rakudo/rakudo.git
cd rakudo
perl Configure.pl --gen-moar --make-install
export PATH="$(pwd)/install/bin/:$PATH"

Try it online:

Or just test it online, using this Try It Online link provided by @b2gills. I checked a few runs and got a different order each time, but haven't had the patience to run it 100 times through that online interface.

Answer 2

bash, 32 28 bytes

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

I ran this 100 times and got 100 different results.

Edit: Saved 4 bytes thanks to @DigitalTrauma.

Answer 3

PowerShell, 54 46 44 39 bytes

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

PowerShell Workflows are not supported in TIO, so you can't try it there. Should work great on your Windows 10 machine though :)

Defines a function p which will output the list of numbers when invoked.

Timing

A single run reliably runs in about 600ms on my machine. The 100 tests defined below finish in under 2 minutes.

Testing

Here's complete code to test it:

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"
    }
}

Output on my machine:

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

Answer 4

GCC on Linux, 47 bytes

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

This gave me different results pretty much every time, having been compiled with gcc (no flags) version 4.9.2. Specifically, I was on 64-bit Debian 8.6 (kernel version 3.16.31).

Explanation

If the fork() returns zero (child process), the value of i is printed, and the loop condition is false, because printf will return a value greater than zero. In the parent process, the loop condition is just i--.