## 840 - Deadlock Detection

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 840 - Deadlock Detection

Haven't tried it yet, but in reading the problem description it occurs to me that the output is under-specified. Since this is a red flag problem, there's only one correct answer, but how are the following ambiguities resolved?

1. In which order is a cycle reported?
The cycle X-a-Y-b-X can be reported in 4 ways. Should we choose the alphabetically smalest? Is a-Y-b-X-a smaller than X-a-Y-b-X ?

2. In what order should cycles of the same length be reported? Alphabetically?

3. If a process/resource occurs in more than one cycle, what should we report? The longest? The shortest? All?

More speciffic; what is the output for the following input?

Code: Select all

``````3

2 2 4
Y-a a-X X-b b-Y

2 2 4
Y-a a-Y X-b b-X

2 2 5
Y-a a-X X-b b-X b-Y
``````

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
My output is:
YES
X-b-Y-a-X

YES
X-b-X
Y-a-Y

YES
X-b-Y-a-X

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Did some experimenting myself in the meantime, but kept getting WA. Your output made me see my mistake: I forgot to print "YES" in case there were cycles

Got accepted now. The answers to my questions are:

1. Alphabetically, with 'A' < 'a'.
2. No such case in the input file.
3. No such case in the input file. My AC program also prints the small cycle X-b-X in addition to Adrians output.

Weak problem description IMO, but with a few additions and better input file it could be made much more challenging.

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

### Re: 840 - Deadlock Detection

hi guys

I'm trying this problem and I get wa...
does anyone could post some AC input - output?

thanks.

btw.what is the otuput for

Code: Select all

``````1

2 2 3
I-h
h-q
I-q``````
I think it's not a deadlock...
There is no knowledge that is no power.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

### Re: 840 - Deadlock Detection

I don't understand how this thing could be a deadlock
X-b-X
My AC code does not considered this as a deadlock but in the previous posts it is considered as a deadlock........ Here b is assigned to X and X needs b. How could it be a deadlock?
I think the input set is not good enough for this problem.
May be tomorrow is a better day............

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

### Re: 840 - Deadlock Detection

I did a silly mistake in my code and for that reason my code failed in such a simple test case:

Code: Select all

``````1
2 2 4
Y-a a-X X-b b-Y``````
My code returns "NO".
But I got AC. Don't know why?
May be tomorrow is a better day............