Paparkan nondeterminisme yang dihasilkan dari penjadwal thread OS

10

Seperti yang kita semua tahu, sistem operasi modern memiliki penjadwal thread yang dapat memilih pesanan yang berbeda untuk menjadwalkan thread Anda berdasarkan logika internal yang kode Anda tidak rahasia untuk. Biasanya Anda merancang kode multithreaded Anda untuk memastikan bahwa nondeterminisme yang dikenakan pada Anda tidak mempengaruhi output Anda secara bermakna.

Tujuannya di sini adalah sebaliknya. Menghasilkan program yang mencetak bilangan bulat dalam interval [0,99] tetapi dalam urutan yang akan bervariasi dari satu menjalankan ke menjalankan karena penjadwal thread OS.

Anda harus mencapai "cukup nondeterminisme", didefinisikan sebagai:

Dalam 10 set 10 percobaan berurutan, program Anda harus menghasilkan setidaknya 9 permutasi unik dalam setiap percobaan. Anda mungkin memiliki sejumlah percobaan yang gagal di kedua sisi berturut-turut 10 yang berhasil.

Atau, dengan kata lain, Anda perlu 100 kali menjalankan program Anda di mana setiap blok 10 berjalan memiliki paling banyak dua kali jalan yang menghasilkan hal yang sama.

Jadi, sesekali bertukar 98 dan 99 tidak akan memotongnya.

Ini adalah , jadi jawaban yang menggunakan byte paling sedikit menang.

Detel

  • Tulis output Anda ke stdout, satu entri per baris
  • Jika Anda memotong-motong format dengan membuat dua utas karakter interleave menulis ke stdout (bahkan kadang-kadang) menghasilkan hal-hal seperti tiga angka digit atau baris kosong, hasil Anda tidak valid
  • Satu-satunya pengecualian untuk aturan di atas adalah Anda dapat memancarkan satu baris kosong setelah mencetak nomor yang diperlukan terakhir (sama-sama)
  • Jika Anda pernah kehilangan atau menduplikasi nilai yang diperlukan, hasil Anda tidak valid
  • Program Anda tidak perlu bersifat non -deterministik pada prosesor inti tunggal (meskipun pujian jika ya)
  • Program Anda dapat menggunakan benang / serat hijau yang sebenarnya tidak dikelola oleh kernel OS jika masih memenuhi persyaratan lain dari tantangan dan sistem threading adalah bagian dari bahasa Anda atau pustaka standar untuk bahasa Anda
  • Runtime untuk program Anda harus andal di bawah 5 detik pada prosesor modern
  • Anda tidak bisa menentukan perubahan pada lingkungan yang terjadi di luar program Anda seperti menunggu atau perubahan pengaturan; program Anda harus lulus apakah menjalankan 100ish kali kembali ke belakang atau dengan satu jam antara setiap kali menjalankan atau 100ish kali secara paralel (yang mungkin akan membantu sebenarnya ...)
  • Anda dapat menggunakan coprocessor seperti GPU atau Xeon Phi dan mekanisme penjadwalan internalnya sendiri untuk tugas. Aturan berlaku untuk ini dengan cara yang sama mereka berlaku untuk utas hijau.
  • Jangan ragu untuk memprovokasi penjadwal dengan segala macam tidur, hasil, dan trik lainnya selama Anda mematuhi aturan yang ditentukan dalam posting ini

Operasi yang Dilarang

Satu-satunya sumber nondeterminisme yang diizinkan untuk Anda gunakan adalah ketika penjadwal menjadwalkan utas Anda untuk dijalankan. Daftar berikut ini tidak lengkap, dimaksudkan hanya untuk memberikan contoh hal-hal yang tidak boleh Anda lakukan karena mereka mengakui sumber nondeterminisme lainnya.

  • Secara langsung atau tidak langsung mengakses segala jenis kemampuan PRNG atau perangkat keras RNG (kecuali jika itu merupakan bagian yang melekat dari penjadwal).
  • Membaca dalam segala jenis input (waktu sistem, sistem file, jaringan, dll.)
  • Membaca ID utas atau ID Proses
  • Menyesuaikan penjadwal OS; Anda harus menggunakan penjadwal OS standar dari OS mainstream
  • Menyesuaikan penjadwal benang / serat hijau Anda juga dilarang. Ini berarti bahwa jika Anda menulis bahasa untuk tantangan ini, Anda harus menggunakan utas OS.

Jawab Validasi

Lebih disukai jawaban akan bekerja di semua OS umum dan prosesor modern, dengan pujian yang diberikan sebanding dengan luasnya dukungan. Namun, ini bukan persyaratan tantangan. Minimal jawaban harus mendukung satu prosesor SMP modern dan OS modern. Saya akan menguji jawaban terkemuka sejauh ketersediaan perangkat keras saya.

  • Jika entri Anda tidak akan menghasilkan output yang diperlukan pada i7 5960x yang menjalankan Windows 10 v1607 x64, tentukan lingkungan yang diperlukan
  • Jika itu sesuatu yang saya dapat dengan mudah mereproduksi dengan VMWare Workstation, berikan spesifikasi OS dan VM yang tepat
  • Jika tidak dapat diproduksi di dalam salah satu dari kondisi tersebut, rekam tangkapan layar secara simultan dari pengujian seperti yang dijelaskan di bagian header dan rekaman video genggam layar Anda dengan interaksi mouse dan keyboard (atau skema kontrol apa pun yang tidak standar perhitungan Anda penggunaan perangkat) terlihat jelas dan memposting kedua video beserta jawaban Anda dan sertakan penjelasan tentang mengapa video itu berfungsi
  • Sebagai alternatif, dapatkan pengguna lama yang memiliki reputasi baik (yang bukan Anda) dengan perangkat keras yang sesuai untuk mereproduksi hasil dan menjamin Anda
  • Jika entri Anda menggunakan bahasa pemrograman eksotis yang tidak dapat diatur oleh pengembang tipikal untuk dikompilasi / jit / interpretasikan, berikan instruksi pengaturan
  • Jika entri Anda tergantung pada versi khusus juru bahasa JVM / Python / lainnya, tentukan yang mana
  • Jika diperlukan lebih dari 10 menit berturut-turut berjalan untuk mendapatkan 10 uji coba berurutan yang sukses dalam pengujian saya, Anda gagal (jadi jangan biarkan kondisi sukses menjadi kejadian yang aneh, terutama jika Anda berada di dekat bagian atas terikat runtime)
Techrocket9
sumber
4
-1 untuk "Jika saya bosan ....". Saya akan mengatakan secara spesifik berapa lama waktu yang dibutuhkan.
Rɪᴋᴇʀ
@ EasterlyIrk Ia juga mengatakan 'andal di bawah lima detik pada CPU modern'
Pavel
@Pavel bukan itu yang saya maksud. 10 percobaan yang berhasil tidak terkait dengan 5 detik.
Rɪᴋᴇʀ
@EasterlyIrk Cukup adil, sekarang 10 menit.
Techrocket9
@ Techrocket9 keren, downvote dibatalkan.
Rɪᴋᴇʀ

Jawaban:

4

Perl 6 , 27 byte

await map {start .say},^100

Penjelasan:

      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.

Saya harap ini memenuhi tugas. (Jika tidak, tolong beritahu saya).

Pengujian:

Skrip shell yang saya gunakan untuk menguji nondeterminisme yang cukup:

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

Bagi saya, ini output:

10 10 10 10 10 10 10 10 10 10 

Instruksi pengaturan:

Saya menjalankan tes dengan Rakudo Perl 6 terbaru di Linux 64bit, meskipun saya kira itu akan bekerja pada platform lain.

The halaman download Rakudo memiliki instruksi setup. Saya mengkompilasi milik saya dari git seperti ini:

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

Cobalah online:

Atau coba saja secara online, gunakan tautan Try It Online yang disediakan oleh @ b2gills. Saya memeriksa beberapa kali dan mendapat urutan yang berbeda setiap kali, tetapi belum memiliki kesabaran untuk menjalankannya 100 kali melalui antarmuka online itu.

seseorang
sumber
Divalidasi pada Windows 10 x64 pada i7 5960x dengan Rakudo Perl versi 2016.11
Techrocket9
4

bash, 32 28 byte

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

Saya menjalankan ini 100 kali dan mendapat 100 hasil yang berbeda.

Sunting: Disimpan 4 byte berkat @DigitalTrauma.

Neil
sumber
Anda mengalahkan saya untuk itu. Sebenarnya milik saya sedikit lebih pendek for i in {0..99};{ echo $i&}, tetapi Anda memposting lebih dulu - Anda dapat menerimanya :)
Digital Trauma
Inilah cara Anda dapat mengujinya di TIO. Ini menjalankan 10 script, menangkap output dari setiap run, mereka md5 output dari setiap run. Kita dapat melihat md5 berbeda setiap kali. MD5 disortir untuk membuat duplikat potensial terlihat.
Trauma Digital
@DigitalTrauma Tidak berdokumen tapi bagus!
Neil
1
Yap - ada tip untuk ini.
Trauma Digital
Menariknya, ini gagal mencapai "nondeterminisme yang cukup" ketika dijalankan di bash-on-windows resmi Microsoft pada E5-2699 v4, tetapi ia bekerja di VM Workstation RHEL dengan 4 core pada mesin yang sama sehingga ia dapat lewat.
Techrocket9
2

PowerShell , 54 46 44 39 byte

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

Alur Kerja PowerShell tidak didukung di TIO, jadi Anda tidak dapat mencobanya di sana. Seharusnya bekerja dengan baik pada mesin Windows 10 Anda :)

Menentukan fungsi pyang akan menampilkan daftar angka saat dipanggil.

Pengaturan waktu

Satu menjalankan andal berjalan di sekitar 600 ms pada mesin saya. 100 tes yang ditentukan di bawah selesai dalam waktu kurang dari 2 menit.

Pengujian

Berikut kode lengkap untuk mengujinya:

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 pada mesin saya:

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
briantis
sumber
Menariknya, ini membutuhkan waktu 51 detik per dijalankan pada kotak E5-2699 v4 saya, tetapi hanya 0,7 detik pada laptop i5-5200U saya. Ini mencapai tingkat nondeterminisme yang diperlukan pada laptop saat datang di bawah 5 detik maks, sehingga berlalu. Tampaknya, penjadwal PowerShell tidak bermain dengan baik dengan banyak core dan tugas pendek.
Techrocket9
Dan butuh 58 detik pada i7 5960x
Techrocket9
Hm ... 74 detik pada laptop i5-6300U. Mungkin ini masalah dengan Windows 10 atau PowerShell 5.1, karena i5-5200U adalah satu-satunya mesin yang diuji tidak menjalankan Win10 (menjalankan 8.1).
Techrocket9
@ Techrocket9 aneh, saya menguji pada Win10, PS 5.1. Di ISE sekalipun.
briantis
2

GCC di Linux, 47 byte

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

Ini memberi saya hasil yang berbeda hampir setiap kali, telah dikompilasi dengan gcc(tanpa bendera) versi 4.9.2. Secara khusus, saya menggunakan Debian 8.6 64-bit (kernel versi 3.16.31).

Penjelasan

Jika fork()mengembalikan nol (proses anak), nilai idicetak, dan kondisi loop salah, karena printfakan mengembalikan nilai lebih besar dari nol. Dalam proses induk, kondisi loop tepat i--.

Dan Getz
sumber
Sama seperti jawaban bash. Deterministik di windows, tetapi lewat di Linux (dalam hal ini Debian).
Techrocket9