The Thing King
I hope the previous post explained virtual memory adequately, but I must admit I held back a much better explanation, which I first saw in Expert C Programming. It wasn’t written by the book’s author, Peter van der Linden, but rather by Jeff Berryman in 1972. Here goes:
The Thing King and the Paging Game
This note is a formal non-working paper of the Project MAC Computer Systems Research Division. It should be reproduced and distributed wherever levity is lacking, and may be referenced at your own risk in other publications.
Rules
- Each player gets several million things.
- Things are kept in crates that hold 4096 things each. Things in the same crate are called crate-mates.
- Crates are stored either in the workshop or the warehouses. The workshop is almost always too small to hold all the crates.
- There is only one workshop but there may be several warehouses. Everybody shares them.
- Each thing has its own thing number.
- What you do with a thing is to zark it. Everybody takes turns zarking.
- You can only zark your things, not anybody else’s.
- Things can only be zarked when they are in the workshop.
- Only the Thing King knows whether a thing is in the workshop or in a warehouse.
- The longer a thing goes without being zarked, the grubbier it is said to become.
- The way you get things is to ask the Thing King. He only gives out things by the crateful. This is to keep the royal overhead down.
- The way you zark a thing is to give its thing number. If you give the number of a thing that happens to be in a workshop it gets zarked right away. If it is in a warehouse, the Thing King packs the crate containing your thing back into the workshop. If there is no room in the workshop, he first finds the grubbiest crate in the workshop, whether it be yours or somebody else’s, and packs it off with all its crate-mates to a warehouse. In its place he puts the crate containing your thing. Your thing then gets zarked and you never know that it wasn’t in the workshop all along.
- Each player’s stock of things have the same numbers as everybody else’s. The Thing King always knows who owns what thing and whose turn it is, so you can’t ever accidentally zark somebody else’s thing even if it has the same thing number as one of yours.
Notes
- Traditionally, the Thing King sits at a large, segmented table and is attended to by pages (the so-called “table pages”) whose job it is to help the king remember where all the things are and who they belong to.
- One consequence of Rule 13 is that everybody’s thing numbers will be similar from game to game, regardless of the number of players.
- The Thing King has a few things of his own, some of which move back and forth between workshop and warehouse just like anybody else’s, but some of which are just too heavy to move out of the workshop.
- With the given set of rules, oft-zarked things tend to get kept mostly in the workshop while little-zarked things stay mostly in a warehouse. This is efficient stock control.
Long Live the Thing King!
Update: Alex pointed out the difficulties of measuring grubbiness in a comment below.
February 4, 2009 at 10:12 am | Filed Under Culture, Internals
Subscribe to blog
Comments
15 Responses to “The Thing King”
Leave a Reply
I own that book, and I have to say it is one of the best books on memory and programming (even though specific to C) I’ve ever read. Great blog!
Except the king can hardly tell which crate is the grubbiest.
If a crate is in the workshop already, simply zarking a thing in it won’t un-grubify the crate.
So all he has to go by is how long ago the crate was brought back from the warehouse.
Sometimes he does a little trick, he pretends the crate is away at the warehouse but actually it in the workshop. If someone tries to zark a thing in that crate, the king can tell that the crate is quite in demand.
@R Caloca: I love the anecdotes and style on that book. Has that playful hacker attitude, very nice read.
@Alex: HAHAHAH. Brilliant.
Amazingly, I was just thinking about this story yesterday–I had read it back in the early 80s and was trying to remember the details. Thanks for posting it!
Great post! I like the analogy game.
From now on I’ll start using the new terms: crates, workshop, zarking and grubby when corresponding with our lead developer
Great one indeed. Like Radu, and unlike the late Edsger Dijkstra (as exposed vehemently in his famous ‘On the Cruelty of Really Teaching Computer Science’*), I also believe analogies often help a lot.
* http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1036.html (this was written in 1988, BTW)
Bruno, I agree with you on that one. Though analogies cannot be applied everywhere (especially in new, radical fields of science like Quantum Mechanics) we shouldn’t just discount their power, especially in the early stages of learning a new discipline.
Notes 2009.04.14…
Notes for yesterday ended up in a JIRA comment…
Notes 2009.04.14 database growth per net bandwidth…
Notes for yesterday ended up in a JIRA comment…
Loved this story in the 70s.
Recently I was telling a recent graduate (EE) about ancient large mainframes. He asked me what computers were used for in those days.
Just wanted to mention that in rule 12 it says:
“he first finds the grubbiest crate in the workshop … and packs it off with all its crate-mates to a warehouse”. Since he is talking about a crate and crates don’t have crate-mates, the phrase “with all its crate-mates” should be deleted.
Guess I’m obsessive.
Eric
Hello Gustavo,
great articles. Thanks for the crystal clear explanation.
Please write as much as you can. share your knowledge
I feel truly thankful to people like you
Wish i could have a teacher like you
keep on writing …for all of us
bye
Great Great
Awesome Awesome
its so nice , i have to say it twice
I work With SBS , performance has never been my forte . This explains things really well .
wow. I’m at a loss for words at the content of your blog.
Truly great stuff – not just this post, but all of them. Kudos !
Alex: There is another trick. Each location in the warehouse is equipped with a small candle, and whenever a thing within the crate residing in that location is zarked, the candle is lit. The Thing King can periodically arrange to have one of the table pages blow out some of the candles. If a candle remains unlit for some time, the things within that crate are obviously not in demand.
[...] original disponÃvel em: http://duartes.org/gustavo/blog/post/the-thing-king Tags: Cada Coisa, Coisas Texto, Notas Tradicionalmente, Sua Coisa [+] Share & Bookmark [...]