Menemukan Kebuntuan
Ketika memprogram aplikasi multithreading kita harus berhati-hati untuk menghindari kebuntuan berbagai utas saat mengakses sumber daya bersama. Sebuah kebuntuan terjadi ketika upaya thread untuk mengakses sumber daya yang terkunci di thread lain pada saat yang sama bahwa benang lainnya sedang mencoba untuk mengakses sumber daya dikunci oleh yang pertama. Ini adalah kasus sederhana, tetapi bisa menjadi lebih kompleks dengan rantai sumber daya yang lebih lama.
Tantangan
Anda harus menulis sebuah program atau fungsi yang dapat mendeteksi situasi jalan buntu yang mungkin dalam daftar sumber daya yang diakses oleh setiap utas. Ini adalah kode-golf, jadi jawaban tersingkat dalam byte menang.
Setiap utas dimulai pada saat yang sama, tetapi setelah itu mereka dapat berjalan pada setiap kombinasi interleaving. Jika ada 2 benang dengan 4 tindakan masing-masing, itu bisa dijalankan sebagai (di mana masing-masing nomor adalah tindakan yang diambil oleh benang dengan id itu) 1,1,1,1,2,2,2,2
, 2,2,2,2,1,1,1,1
, 1,2,1,2,1,2,1,2
, 1,1,2,2,2,2,1,1
, atau kombinasi lain yang mungkin.
Memasukkan
Anda akan menerima, melalui STDIN, parameter fungsi, atau alternatif terdekat, daftar string. Setiap string akan berada dalam format +a
-b
. Setiap string ini mewakili penguncian ( +
) / unlocking ( -
) sumber daya oleh utas. Antara setiap utas akan menjadi ---
pemisah. Dijamin bahwa utas tidak akan mencoba untuk mengunci sumber daya yang sudah dikunci, dan bahwa semua utas secara eksplisit akan membuka semua sumber daya yang telah dikunci sebelum keluar. Berikut ini adalah contoh untuk diperagakan:
+a # Lock resource a
+b # Lock resource b
-a # Unlock resource a
-b # Unlock resource b
--- # Thread separator
+b # Lock resource b
-b # Unlock resource b
Keluaran
Output harus palsu jika input tidak mengandung kemungkinan kebuntuan, dan jujur jika berisi kemungkinan kebuntuan. Sebagai contoh:
true
false
1
0
semua hasil yang valid, tetapi segala sesuatu yang didefinisikan dengan jelas sebagai kebenaran / kepalsuan akan diterima.
Contohnya
+a
-a
---
+a
-a
Keluaran: false
+a
+b
-b
-a
---
+b
+a
-a
-b
Keluaran true
Jalan buntu saat mencoba mendapatkan b,a
masing-masing untuk utas1,2
+a
+b
-a
-b
---
+a
+b
-b
-a
Keluaran false
+a
+b
-b
-a
---
+b
+c
-c
-b
---
+c
+a
-a
-c
Keluaran: true
Jalan buntu di utas 1,2,3 saat mencoba mengakuisisi b,c,a
masing-masing.
Keluaran false
Keluaran true
Jalan buntu di utas 1,2,3 saat mencoba b,d,a
masing-masing.
Tentu saja ini bisa menjadi jauh lebih kompleks, dengan lebih banyak utas, lebih banyak sumber daya untuk masing-masing, dan seterusnya, tetapi saya percaya tes ini mencakup dasar-dasarnya.
Bonus
Karena sangat menyedihkan ketika Anda menemukan situasi kebuntuan saat menulis sebuah program, ada bonus -8 byte untuk jawaban yang dihasilkan :(
dan :)
masing-masing sebagai kebenaran / kepalsuan.
d
sampai nanti.:)
tidak semestinya palsu dan:(
benar?Jawaban:
Python 2 - 227
Pada dasarnya memastikan tidak ada loop 'prioritas'. Sebagai contoh dalam tes kedua, utas pertama memiliki
a(b)
prioritas dan utas kedua memilikib(a)
prioritas.Saya berpikir untuk menulis ulang ini dalam Pyth karena saya pikir itu akan bekerja dengan baik dengan semua operasi itertools, tetapi mengubah regex akan membutuhkan beberapa pekerjaan jadi untuk sekarang saya akan memposting ini dan mungkin mencoba untuk mengubahnya dan mengirim jawaban lain nanti.
sumber
Python -
586539524501485 byte - 8 = 477Tingkat lekukan:
-
sumber
;
untuk menggabungkan garis yang indentasi untuk menyimpan karakter. Demikian juga, buat pernyataan Anda satu garis.for r in sys.stdin
for r in sys.stdin.readlines()
sys.stdin
atausys.stdin.readlines()
, jadi saya telah mengubahnya, terima kasih lagi.print
dan':)'