Kevin (erf_) wrote,

  • Location:
  • Mood:
  • Music:

rebalancing "The Weight"

Recently my co-workers and I have been picking away at a design issue involving weighting problems in a set of strategy algorithms. I'm not going to bore you non-computery folk with the details, but I'd just like to mention that this discussion indrectly convinced me that The Band's song "The Weight" is about interprocess communication in a load balancing system.

For maximum impenetrability, read this entry aloud in the gentle, cheerful voice of beloved Oberlin CS professor John Donaldson. (Sure, sure. Def'nitely, def'nitely.)

I pulled into Nazareth, was feelin' about half past dead
I just need some place where I can lay my head
"Hey, mister, can you tell me where a man might find a bed?"
He just grinned and shook my hand; "No!" was all he said

This is a nontrivial example of the Starving Philosophers Problem. A thread object (let's call him Bob) wants to release his lock on a memory range so that he can sleep. He asks the mutex handler if he can release his lock. The mutex handler recognizes his handshake, but is deadlocked (for reasons we will explain later), so the thread object is left waiting for its lock to be released.

Take a load off, Annie
Take a load for free
Take a load off, Annie--
and, and, aaaaand
you can put the load right on me.

This dilemma occurs because Bob is on a greedy distributed system in which threading is handled separately on each system. Bob has announced his intention to surrender the lock on system B, but due to latency system A is not aware of this. In fact, another thread (let's call her Annie), on system A, is overburdened, and is asking him for his lock, and is not getting an answer because system B's mutex handler is locked up. Because system A and system B are both in deadlock, their mutex handlers are not able to communicate. Complicating things further is the fact that Bob's mutex is being stored in a memory space in system A that Annie wants to free. Bob is asking Annie to take a load off, so that free can be called, but the mutex handler's logical union check (ANDs on the three lowest bits of the mutex) is not being called, so Annie is unable to redistribute her load to him.

I picked up my bag, I went lookin' for a place to hide;
When I saw Carmen and the Devil walkin' side by side.
I said, "Hey, Carmen, come on, let's go downtown."
She said, "I gotta go, but m'friend can stick around."

Bob times out waiting for his lock to be released, and surrenders the semaphore voluntarily. He tries to background himself("hide" at the operating system level) in order to sleep. He notifies the operating system via two concurrently running listener processes--Carmen, an ordinary event listener, and a "devil" (a daemon process). Unfortunately, Carmen is not expecting a message from Bob at this time, and crashes. The daemon is not expecting a message, either, but being a daemon, it hangs instead of crashing, turning it into a zombie process. The resolution of this issue is trivial.

Take a load off, Annie
Take a load for free
Take a load off, Annie--
and, and, aaaaand
you can put the load right on me.

Bob reenters his execution loop, with no more success than before. Bob and Annie are still deadlocked.

Go down, Miss Moses, there's nothin' you can say
It's just ol' Luke, and Luke's waitin' on the Judgement Day.
"Well, Luke, my friend, what about young Anna Lee?"
He said, "Do me a favor, son, woncha stay an' keep Anna Lee company?"

Miss Moses, an obvious reference the the logger process, goes down, as she is unable to access any of the memory locked by Bob and Annie, and cannot report the system state. The operating system, however, is quite robust, and delegates the thread Luke (which usually sleeps until system shutdown) as a third party to relieve the deadlock by moving Annie's instructions into System A's L1 cache, in a address range we will call ANN-A-L1. The instruction stack is cleared, Annie completes her instruction, and since no one is attempting to access Bob's critical sections, he releases his lock. The problem remains, however, on how to push the instructions stored in ANN-A-L1 back onto the execution stack.

Crazy Chester followed me, and he caught me in the fog.
He said, "I will fix your rack, if you'll take Jack, my dog."
I said, "Wait a minute, Chester, you know I'm a peaceful man."
He said, "That's okay, boy, won't you feed him when you can."

Those of you who are astute but unconventional-thinking system administrators ("Crazy Chester", who fixes server racks) may raise the question of whether this algorithm would really solve the Starving Philosophers Problem, as Bob will not know when to surrender his mutex, and allowing him to release his lock unconditionally after a timeout could be dangerous. The Band asserts that as long as the system designer Does The Right Thing, this is a viable strategy against resource starvation nonetheless. The significance of the dog is unknown.

Catch a cannon ball now, t'take me down the line
My bag is sinkin' low and I do believe it's time.
To get back to Miss Fanny, you know she's the only one.
Who sent me here with her regards for everyone.

In any case, Luke flushes the L1 cache just in time for the deadlock to be resolved. (If available memory is running low and the L1 cache is full, Luke simply pushes the instructions directly onto the instruction stack.) When he is done, he returns control to the main process. All the processes have cake and pie and execute happily ever after. Yay!

The proof for this solution is left as an exercise for the reader.

I kind of want to make a PowerPoint presentation of this entry, with lots of little box-and-arrow diagrams.
Tags: computers, crap, essays, music, work, wtf

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded