The Deadlock Empire is mine!! Bwa ha ha ha!

[beth_leonard]

I gave up playing mindless games like Candy Crush and 2048 for lent. So I found this instead:
https://deadlockempire.github.io/#menu

I remember tracking down a bug in a program at HP that was essentially the problem in the #5 "Deadlock" challenge. Our code hadn't changed in weeks, yet our regression tests were failing to complete about every 10 days, and I eventually tracked down why. I still remember the elation of figuring it out a decade and a half later. And yes, I did figure it out while in the shower. It's where engineers get our best thinking in.

--Beth

Comments

[altamira16.livejournal.com]

I can't figure out the boss battle. Threading is still a little outside my grasp, but I think that I have some vague understanding of it.

[beth_leonard]

You have to get both threads into the inner sanctum critical section at the same to win.
There are two fortress.wait commands in Thread 0, so you have to run Thread 1 through twice to up the counter enough times prior to trying to do anything on Thread 0.

Then, in order to get through thread 1, you have to run thread 1 to just before executing the "if" statement, at this point, darkness and evil will both be 1.

Next, you have to run thread 0 twice and stop after you've done "darkness++" but before "evil++" so that darkness is 3 and evil is 2. Now the check on the if statement of thread 1 can succeed. Enter the if statement on thread 1 before upping evil to 3 on thread 0.

Do evil++ on thread 0 and pass through the two fortress.Wait() calls that you set up earlier.

Now, you just have to be careful about the Monitor timing:

Enter the sanctum on Thread 0.
Thread 1 will now be blocked.
Wait in the sanctum on Thread 0, which releases the lock, allowing Thread 1 to go.
Enter and Pulse the sanctum on Thread 1, unblocking Thread 0.
Enter the sanctum on Thread 0 (during the expanded wait command).
Exit the sanctum on Thread 1, unblocking thread 0, and enter the critical section.
Now you're unblocked in thread 0 and can enter the critical section there too.

You win! They even have a nice comment form for you to fill out. I gave them some nice feedback.
--Beth
[Edit: forgot a 0]

[altamira16.livejournal.com]

The world needs to return to sequential programming. Clearly, I am not a parallel wizard.

[beth_leonard]

Basically, if you are doing anything complicated, you need to go all the way and use something like Paxos. Mutexes and semaphores are nice, but what do you do when the process you're waiting on to release their mutex catches fire, literally? While you may be able to provably work out the code for 3 mutexes, when you have 100,000 of them, you're nearly guaranteed to get deadlock eventually. My friend recommends using the Go language for parallelism, but I haven't learned it yet. If it's still popular in about a decade when I start thinking about going back to work, I'll take the time to learn it.

--Beth