Menemukan Kebuntuan

18

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,amasing-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,amasing-masing.


http://pastebin.com/vMYRZxtW

Keluaran false


http://pastebin.com/V5MVgNgS

Keluaran true

Jalan buntu di utas 1,2,3 saat mencoba b,d,amasing-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.

rorlork
sumber
Saya hanya mengasumsikan ini, tetapi akan lebih baik untuk mengklarifikasi bahwa tindakan dari masing-masing utas (mulai dari utas) dijalankan secara paralel dan sesuai dengan waktu sistem yang sama
Pengoptimal
1
Tindakan dijalankan secara bersamaan, tetapi waktu di mana setiap tindakan dijalankan tidak dapat diasumsikan. Bisa terjadi bahwa utas benar-benar berjalan ketat satu demi satu atau sepenuhnya disisipkan. Bisa jadi bagian pertama dari utas 1 dijalankan, kemudian utas 2 dijalankan seluruhnya, lalu utas 1 menjalankannya adalah paruh kedua. Dan seterusnya. Saya telah memperbarui pertanyaan untuk menjelaskannya.
rorlork
1
Ah baik-baik saja, jadi tugasnya adalah untuk mencari tahu yang diberikan kombinasi yang mungkin dari kali menjalankan thread, apakah kebuntuan mungkin.
Pengoptimal
Ya, maaf, saya tidak berpikir itu bisa meninggalkan keraguan. Sebenarnya dalam contoh terakhir ini ditunjukkan karena utas 2 tidak mencoba menggunakan sumber daya dsampai nanti.
rorlork
1
@ rmcn, Anda yakin :)tidak semestinya palsu dan :(benar?
Tyilo

Jawaban:

4

Python 2 - 227

Pada dasarnya memastikan tidak ada loop 'prioritas'. Sebagai contoh dalam tes kedua, utas pertama memiliki a(b)prioritas dan utas kedua memiliki b(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.

from itertools import*
import re
f=lambda t:any(re.search(r"(.)((.)\3)+\1",''.join(p))for i in product(*[[m.group(1)+m.group(2)for m in re.finditer(r"(\w).*(\w).*\2.*\1",e,16)]for e in t.split('---')])for p in permutations(i))
KSab
sumber
Jawaban ini salah untuk pastebin.com/V5MVgNgS
Tyilo
@ Tyilo Ini menghasilkan True untuk saya; bagaimana tepatnya Anda menjalankannya?
KSab
oh itu hanya membaca satu baris untuk saya. Bagaimana Anda menjalankannya?
Tyilo
@ Tyilo Saya mengubah format menjadi fungsi yang mengambil string multiline sebagai input
KSab
5

Python - 586 539 524 501 485 byte - 8 = 477

Tingkat lekukan:

1: 1 space
2: 1 tab
3: 1 tab + 1 space
4: 2 tabs

-

import sys
V=set()
t=[[[]]]
for r in sys.stdin:
 r=r.strip()
 if'---'==r:t.append([[]])
 else:v=r[1:];V.add(v);l=t[-1][-1];t[-1].append(l+[v]if'+'==r[0]else filter(lambda x:x!=v,l))
s=lambda l:s(l[1:])+map(lambda x:(l[0],x),l[1:])if 1<len(l)else[]
E=reduce(set.union,map(lambda x:set(sum(map(s,x),[])),t),set())
for v in V:
 k=set();q=[v]
 while 0<len(q):
    u=q.pop(0)
    if u in k:continue
    k.add(u)
    for x,y in E:
     if u==x:
        if y in k:print':(';sys.exit()
        else:q.append(y)
print':)'
Tyilo
sumber
1
Gunakan ;untuk menggabungkan garis yang indentasi untuk menyimpan karakter. Demikian juga, buat pernyataan Anda satu garis.
isaacg
@isaacg dan kartu as, Terima kasih! Saya pikir saya memperbaikinya sebanyak yang saya bisa menggunakan tips Anda.
Tyilo
BTW jika Anda tidak keberatan for r in sys.stdinfor r in sys.stdin.readlines()
mem
@ace Saya tidak melihat perilaku yang berbeda antara hanya menggunakan sys.stdinatau sys.stdin.readlines(), jadi saya telah mengubahnya, terima kasih lagi.
Tyilo
Anda dapat menghapus spasi di antara printdan':)'
user12205