Research tools - laptops for the Internet and handhelds for mobile usability testing

isham research

The Paging Game

by Jeff Berryman, University of British Columbia, 1972

 

The Paging Game was written by Jeff Berryman when he was working on project MAC, specifically one of the virtual memory systems. The version best known to IBM and MVS sites from the mid-1970s onwards is first, followed by the original and one of the many other versions:

*** RULES ***

  1. Each player gets several million *things*.
  2. Things are kept in *crates* that hold 4096 things each. Things in the same crate are called *crate-mates*.
  3. Crates are stored either in the *workshop* or in the *warehouse*. The workshop is almost always too small to hold all the crates.
  4. There is only one workshop, but there may be several warehouses. Everybody shares them.
  5. Each thing has its own *thing number*.
  6. What you do with a thing is to *zark* it. Everybody takes turns zarking.
  7. You can only zark your own things, not anybody else's.
  8. Things may only be zarked when they are in the workshop.
  9. Only the *Thing King* knows whether a thing is in the workshop or in a warehouse.
  10. The longer a thing goes without being zarked, the *grubbier* it is said to become.
  11. The way to get things is to ask the Thing King. He only gives out things in crates. This is to keep royal overhead down.
  12. The way to zark a thing is to give its thing number. If you give the number of a thing that happens to be in the workshop, it gets zarked right away. If it is in a warehouse, the Thing King moves the crate containing your thing 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 gets zarked and you never even know that it wasn't in the workshop all along.
  13. Each player's stock of things has 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 number as one of yours.

 

*** NOTES ***

  1. Traditionally, the Thing King sits at a large, segmented table and is attended by pages (the so-called "table pages") whose jobs it is to help the king remember where all the things are and to whom they belong.
  2. One consequence of Rule 13 is that everybody's thing numbers will be similar from game to game, regardless of the number of players.
  3. 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.
  4. 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.
  5. Sometimes even the warehouses get full. The Thing King then has to start piling things on the dump out back. This makes the game slow because it takes a long time to get things off the dump when they are needed in the workshop. A forthcoming change in the rules will allow the Thing King to select the grubbiest things in the warehouses and send them to dump in his spare time, thus keeping the warehouses from getting too full. This means that the most infrequently-zarked things will end up in the dump so the Thing King won't have to get things from the dump so often. This should speed up the game when there are lots of users and the warehouses are getting full.

Long Live the Thing King!

And here is something close to the original version, from the Project MAC manual.

THE PAGING GAME

Project MAC Computer Systems Research Division

 

*** RULES ***

  1. Each process gets several million *bytes*.
  2. Bytes are kept in *pages* that hold 4096 bytes each. Bytes on the same page have *locality of reference*.
  3. Pages are stored either in *memory* or on the *disk*. The memory is almost always too small to hold all the pages.
  4. There is only one memory, but there may be several disks. Everybody shares them.
  5. Each byte has its own *virtual address*.
  6. What you do with a byte is to *reference* it. Everybody takes turns referencing.
  7. You can only reference your own bytes, not anybody else's.
  8. Bytes may only be referenced when they are in the memory.
  9. Only the *VM Manager* knows whether a byte is in the memory or on a disk.
  10. The longer a byte goes without being referenced, the *older* it is said to become.
  11. The way to get bytes is to ask the VM Manager. He only gives out bytes in pages. This is to keep overhead down.
  12. The way to reference a byte is to give its virtual address. If you give the address of a byte that happens to be in the memory, it gets referenced right away. If it is on a disk, the VM Manager moves the page containing your byte into the memory. If there is no room in the memory, he first finds the oldest page in the memory, whether it be yours or somebody else's, and packs it off with the rest of the page to a disk. In its place he puts the page containing your byte. Your byte gets referenced and you never even know that it wasn't in the memory all along.
  13. Each process's stock of bytes has the same virtual addresses as everybody else's. The VM Manager always knows who owns what byte and whose turn it is, so you can't ever accidentally reference somebody else's byte even if it has the same virtual address as one of yours.

 

*** NOTES ***

  1. Traditionally, the VM Manager uses a large, segmented table and "page tables" whose jobs it is to help the king remember where all the bytes are and to whom they belong.
  2. One consequence of Rule 13 is that everybody's virtual address will be similar from game to game, regardless of the number of processs.
  3. The VM Manager has a few bytes of his own, some of which move back and forth between memory and disk just like anybody else's, but some of which are just too heavyily used to move out of the memory.
  4. With the given set of rules, oft-referenced bytes tend to get kept mostly in the memory, while little-referenced bytes stay mostly on a disk.
  5. Sometimes even the disks get full. The VM Manager then has to start piling bytes on the dump out back. This makes the computer slow because it takes a long time to get bytes off the dump when they are needed in the memory. A forthcoming change in the rules will allow the VM Manager to select the grubbiest bytes in the disks and send them to dump in his spare time, thus keeping the disks from getting too full. This means that the most infrequently-referenceed bytes will end up in the dump so the VM Manager won't have to get bytes from the dump so often. This should speed up the game when there are a lot of processs and the disks are getting full.

Long Live the VM Manager!

Yet another version:

The Paging Game

  1. Each player gets several million THINGS.
  2. THINGS are kept in CRATES that hold 4096 things each. THINGS in the same crate are called CRATE-MATES.
  3. Crates are stored either in the WORKSHOP or a WAREHOUSE. The workshop is almost always too small to hold all the crates.
  4. There is only one workshop but there may be several warehouses. Everybody shares them.
  5. Each thing has its own THING NUMBER.
  6. What you do with a thing is to ZARK it. Everyone takes turns zarking.
  7. You can only zark your things, not anybody else's.
  8. Things can only be zarked when they are in the workshop.
  9. Only the THING KING knows whether a thing is in the workshop or in a warehouse.
  10. The longer a thing goes without being zarked, the GRUBBIER it is said to become.
  11. The way you get things is to ask the Thing King. He only gives out things in multiples of eight. This is to keep the royal overhead down.
  12. 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 the 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 knew that it wasn't in the workshop all along.
  13. 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.
  14. When you want to zark a thing which is not in the workshop, the Thing King makes you wait while he packs the crate into the workshop. In the meantime, he lets somebody else have a turn zarking. The Thing King puts you to sleep and stops your watch while you are waiting so you won't mind the wait.
  15. THE OBJECT OF THE GAME is to get all your zarking done as fast as possible. Since you can't tell how long it's taking you to zark your things, you use certain methods which, you are assured, will enable you to zark in the minimum amount of time. You take these on faith, since you can't find out how long you took until you get out of the warehouse and look at a clock. This is the Thing King's Royal Religion.
  16. If the players are trying to zark many more things than will fit in the workshop, the Thing King gets so busy packing crates back and forth that the whole game slows down. This state of Royal affairs is called JUGGLING because of the way the crates are always moving about up in the air. When this happens, the game is more for a Fool than for the Thing King.

NOTES:

  1. 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.
  2. One consequence of Rule 13 is that everybody's thing numbers will be similar from game to game, regardless of the number of players.
  3. 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.
  4. 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.
  5. Sometimes even the warehouses get full. The Thing King then has to start piling things on the dump out back. This makes the game slower because it takes a long time to get things off the dump when they are needed in the workshop. A forthcoming change in the rules will allow the Thing King to select the grubbiest things in the warehouses and send them to the dump in his spare time, thus keeping the warehouses from getting too full. This means that the most infrequently-zarked things will end up in the dump so the Thing King won't have to get things from the dump so often. This should speed up the game when there are a lot of players and the warehouses are getting full.
  6. The Paging Game is NOT zero sum. It is possible to win while helping everybody else to win. In fact, everybody loses a little because it takes longer to zark your things than it would if you had the warehouse to yourself. This is made up for by the fact that players with only a couple of crates can use the Royal workshop without having to pay rent on the whole workshop. In addition, players who have more crates than will fit can play, although the Thing King charges them extra steep rents. The Thing King charges you rent only for the part of the workshop you use, and only for the time when you are awake.
  7. As a consequence of rules 15 and 16, there are GOOD PLAYERS and BAD PLAYERS. Good players are those who keep the faith and follow the precepts of the Royal Religion, which requires them to keep their most often zarked things together in the same crates to minimize the movement of crates and avoid juggling. Bad players are those who keep their things scattered all over the place in different crates and never zark two things in the same crate in succession, except by accident. This is known as LISPING.
  8. Under the present rules, bad players pay the same rent as good players. This is the Royal Charity.
  9. Good players tend to win, especially if all the other players are good. Bad players not only lose, but keep all the other players from winning. Hiss the villain and cheer the hero.