multithreaded programs are the hardest ones to write.

[jiml8]

The goal: establish a queue that is a ring (no beginning and no end, when you traverse it either forward or backwards you eventually return to where you start). This ring is dynamic; entries are being created and destroyed for it continually, at rates that may easily exceed 100/sec. The typical queue entry will persist for several seconds to several minutes, and will be changed typically whenever any of its subsidiary rings experiences a change.

Each queue entry has within it the hooks to hang three other ring queues. The head queue may have a couple of thousand entries, so there may be as many as several thousand total queues, each of which is shared among a minimum of three threads (with no defined maximum number of threads but probably not to exceed about 10), and each with its own particular access locking requirements. Each of these three queues may or may not exist at any given time. These queues, when they exist, ordinarily will each experience changes (addition and subtraction of entries) at the expected rate of around 100/sec or so.

There is no limit (other than physical RAM) to how large any of these rings can become.

This program sits in the heart of a communications system; packets flow through this program at data rates that can reach 100 MB/sec pretty easily. If the program deadlocks or crashes, a major communications network dies.

The task: Write this program with appropriate locking so that parallelism is maximized, deadlocks never occur, and the program never crashes. Along the way, read, store, and modify as required Level 2 and Level 3 information for each packet, in a fashion that is dictated by information found in Level 4. All queues must expand or shrink as required, and must be created and destroyed as appropriate.

It's been fun. I think it is all working now though. At least, it hasn't crashed for the last few hours...

[isadora]

Jim, my compliments for your very clearly explanation.
It gave me a good visualization of what happens under the hood.
Complex and indeed very complicated to make it work, as the goal intended.

Thanks for this insight.

[jiml8]

Well thanks.

I really am just patting myself on the back, though. This has been quite the complicated effort, I am pleased with the outcome, and I am just releasing it for live testing in a real network.