noen som kan hjelpe med en enkel algoritme?

[chris78]

heisann....

 

har slitt med en oppgave en ukes tid, finner ikke en brukbar algoritme, saa naa haaper jeg noen her kan hjelpe litt.

 

problemet er deadlock detection i traader. feks kan man ha 3 traader, som holder en laas hver. hver traad venter ogsaa paa at neste laas skal bli ledig, paa den maaten maa alle vente til evig tid. illustrert slik:

 

a --> l1 --> b --> l2 --> c --> l3 --> a

 

som vi ser her venter a paa laas 1 som holdes av traad b, traad b venter paa laas 2 som holdes av traad c, og c venter paa laas 3 som holdes av traad a.

 

i dette tilfellet er det ikke noe problem aa finne en algoritme for aa detektere deadlock, men jeg trenger en algoritme som funker paa alle kombinasjoner av traader og laaser, ogsaa dersom det er noen utenom deadlock'en, eller om noen traader holder mer enn en laas.

 

jeg vet man kan detektere cycles vha depth first search, men det virker som litt overkill i dette tilfellet, saa hvis noen her har en bra algoritme som er enkel aa programmere, hadde jeg satt pris paa aa faa hoere om den, og gjerne med kode hvis du har det!

 

takk!