Page:The Paging Game.djvu/2

13. Each player's stock of things is numbered in the same range, 1 to 8,000,000. The thing King always knows who owns what thing and whose turn it is, so you can't ever accidentally zark someone else's thing, even if one of your things has the same thing number.

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.
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 from the warehouses to the workshop just like anybody else's, but some 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 one of the warehouses. 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 from the dump when they are needed in the workshop. The Thing King follows a rule that minimizes this delay: When the warehouse begins to get too full, the Thing King uses his spare time to move the grubbiest things in the warehouses out to the dump. This means that the most infrequently zarked things will end up in the dump so that the Thing King won't have to get things from the dump very often. This keeps the game from getting too slow when there are a lot of players and a large number of things to store.

LONG LIVE THE THING KING!

PART II

In Part I we said that paging was a process by which some computer systems, including ours, "stretch" the effective sizes of their memories. We described an imaginary game that was played by the same rules that govern the paging process. In this part we'll list the rules again, this time using computing terms instead of the terms of the game. Compare each paging rule given below with the corresponding game rule.

The Paging System

Rules

1. Any computer job can have up to 8,388,608 bytes of memory at once.
2. Memory is divided into pages of 4096 bytes each.
3. Pages are stored either in the real memory or on a paging device. The real memory is almost always too small to hold all the pages.
4. There is only one real memory (two million bytes of storage) and two principal paging devices (IBM 2301 drum storage units). All the jobs share them.
5. Each byte has an address.
6. What you do to bytes is to reference (i.e., store data in or fetch data from) them. Jobs take turns referencing.
7. Jobs can reference only their own bytes, not anybody else's.
8. Bytes can be referenced only when they're in real memory.
9. Only the operating system (i.e., MTS, the supervisor, and paging-device program) knows whether a byte is in real memory or on the paging device.
10. The longer a byte (or a page) goes without being referenced, the less current it is said to become.
11. The way a job gets bytes is to request them from the system. Memory is allocated in groups of eight bytes (doublewords) to make the system's recordkeeping process easier.
12. The way a job references something is to give its address. Addresses are generally given by making them operands of machine language instructions, contents of hardware registers, etc. At any rate, if a job gives the address of a byte that is in real memory, the reference is completed immediately. If the byte is on a paging device, the system finds the least current page in real memory and writes it onto a paging device. It then reads into real memory the page containing the byte to be referenced. The reference is then completed, just as though nothing special had happened.
13. All jobs' addresses are in the same range. The system knows whose memory is whose and which job is doing the referencing, so that one job cannot reference another job's bytes.

Notes

1. The system keeps track of all the bytes (for a given user) by using one master table, called a segment table, and a bunch of little tables, called page tables.
2. Because of Rule 13, the addresses that a job gets don't depend on the number of jobs currently on the computer.
3. The system has its own storage, some of which migrates from paging devices to real memory and back just like ordinary memory, but some of which, for a variety of good reasons, stays in real storage all the time.
4. Under the above rules, pages that are referenced often tend to stay in real memory, while little-used pages stay on a paging device. This makes efficient use of real storage, which is expensive.
5. Sometimes the available space on the principal paging devices gets full. When this situation threatens, the system uses its un-busy moments to select the least current pages on the principal paging devices and move them to a disk pack. This method of using the disk pack minimizes the