Storage Keys and Region Boundaries in Multiprogrammed Batch

Single-stream batch wastes the machine because the processor waits for mechanical devices. The obvious fix is to hold two or more jobs in storage at once and let one compute while another waits on a channel. The obstacle is not scheduling. It is that two programs in the same storage can see each other’s data, and a stray address in one job will corrupt the other’s work in a way that is nearly impossible to diagnose after the fact. Multiprogramming only became practical when the hardware could refuse a store.

The System/360 mechanism for that refusal is the storage key, and it is worth studying because it is a protection scheme of a completely different shape from the page-table permissions that later machines use. It has no page tables. It protects fixed-size blocks, and the protection decision is made on every storage reference by comparing a four-bit field against a four-bit field in the program status word.

Seven bits per 2 KB block

Main storage is divided into blocks of 2,048 bytes. Each block has an associated storage key of seven bits: four bits of protection key and three bits of control. The keys are not in the addressable storage the program sees; they live in a separate small array, one entry per block, and they are loaded and read by privileged instructions only.

A reference to storage is checked against the key of the block containing the address, not against the extent of the object being accessed. The four-bit protection key of the block is compared with the four-bit key held in the program status word of the running program. If they match, a store is permitted. If they do not, a store is refused with a protection exception, which is a program check that transfers control to the monitor. Fetches are governed separately: the fetch-protection bit in the block’s key can make the block read-protected, in which case even a matching key cannot read it.

The granularity is the whole design. A block is 2,048 bytes, so the smallest unit of protection is two kilobytes, and any two objects smaller than that which happen to share a block share a key. This is coarse by the standards of a page-based machine with 4 KB pages and per-page permissions, and it is coarser still because the number of distinct keys is sixteen. There are only sixteen protection keys, so at most sixteen mutually isolated domains can exist, regardless of how much storage the machine has.

Sixteen is not an accident. The key has to fit in the program status word next to the other state, and four bits is what the encoding allowed. The consequence is a hard limit on the number of partitions: a system that wants to run more than fifteen jobs concurrently plus the supervisor has to reuse keys, and reuse means the protection is partial.

The instruction that moves data between keys

A protection scheme that only refused stores would be unusable, because a batch job legitimately needs to hand data to the supervisor: it opens a data set, it asks for a record, it passes a buffer address. The mechanism for that is a set of privileged move instructions that ignore the key check on one side.

The move-to-primary instruction stores into a block whose key need not match, and the move-from-primary instruction loads from such a block. Both are privileged, so only the supervisor executes them. The pattern is that a program places a request in its own storage, executes a supervisor call, and the supervisor reads the request with a key-bypassing instruction, performs the operation, and writes the result back with the other. The program never has authority to write outside its own key, and the supervisor has authority to write anywhere.

That asymmetry is the entire security model. Authority is a property of the code being executed, encoded in the program status word, not a property of the data being touched. There is no notion of a per-object owner. Two jobs that share a key can write each other’s storage freely, and the machine will not object.

Partitions: fixed, then variable

The earliest multiprogramming on these machines used fixed partitions. Storage is divided at system generation time into regions of fixed size, each with a key, and each region holds one job at a time. A job that needs less than its region’s size wastes the difference; a job that needs more cannot run at all until an operator or a scheduler changes the configuration.

Fixed partitions are simple and they fail in a specific, predictable way. The arrival rate of jobs is not uniform in size, so the partition sized for the largest job is empty most of the time while smaller jobs queue for a smaller partition. The machine’s utilization is bounded by the mismatch between the size distribution of the workload and the sizes chosen months earlier.

Variable partitions replace fixed boundaries with boundaries computed per job. The monitor allocates a contiguous region sized to the job’s request, and the key is assigned when the region is created. This removes the size mismatch and introduces two new problems.

The first is fragmentation. Regions are allocated and freed in arbitrary order, so the free storage between regions becomes a set of holes whose total size may exceed a waiting job’s requirement while no single hole does. The monitor either waits, which idles the machine, or compacts: it moves resident jobs downward to coalesce the holes. Compaction requires that every address a job holds be adjusted, and on a machine with no relocation hardware a job’s addresses are absolute, so compaction is impossible without rewriting the job’s storage. This is the problem that dynamic address translation solves, and it is why the move to virtual storage was not a convenience but a prerequisite for efficient variable partitioning.

The second is that the key belongs to the block, not to the region. A region of 30 KB spans fifteen blocks, each of which must be given the region’s key at allocation, and the block at the region’s boundary may be shared with an adjacent region if the regions are not block-aligned. Since the block is 2,048 bytes, regions are rounded up to that boundary, and the rounding is wasted storage per region. With a dozen regions the waste is tens of kilobytes, which on a machine of a few hundred kilobytes is a real cost.

What the key does not protect

Four limitations follow from the design, and each has a practical consequence.

The key protects stores and optionally fetches, but it does not protect the supervisor’s control over the machine. A job that can execute a privileged instruction can change its own key or the key of any block. The machine prevents that by making privileged instructions trap, which means the distinction between supervisor state and problem state is the actual security boundary, and the key is a second layer behind it. If a job obtains supervisor state, the keys are irrelevant.

The key does not protect against a program that reads within its own region. A job’s buffer overflow that stays inside its own 2 KB blocks is invisible. This sounds harmless until the overflow is a write past the end of an array into the job’s own code, which is a bug the key cannot detect and which corrupts the program in ways that produce arbitrary behaviour rather than a clean exception.

The key does not survive a shared data set. If two jobs must both update the same file, the file’s buffers are in one job’s region and the other job’s access goes through the supervisor, so the protection is intact but the concurrency problem is not solved. Two jobs updating the same record concurrently need locking, and the key says nothing about locking. This is where multiprogramming forces the introduction of enqueue/dequeue services in the supervisor: protection prevents accidental corruption, and locking prevents logical corruption, and a system needs both.

The key does not make a job’s failure recoverable by itself. When a job takes a protection exception the monitor can terminate it, but the job may have left a data set half-written. Recovery depends on the data set’s own integrity mechanism, which for a sequential file means writing to a new copy and renaming at the end, or taking a checkpoint. Both are described in checkpoint and restart.

Why the coarse scheme survived

A page table with per-page permissions is finer and more flexible, and it arrived on these machines as dynamic address translation, covered in dynamic address translation and the 16 MB line. The storage key did not disappear when it did. Keys were retained alongside translation, because they express something a page table does not: a protection domain that follows the program rather than the address.

A translated address has a page-table entry, and the entry can say “this page is writable by this program.” A keyed address has a block key, and the block key says “this storage belongs to key 7.” The difference shows when storage is reused. With translation, freeing a page means removing the mapping, and the next user gets a fresh mapping. With keys, freeing a block means changing its key, and the next user’s key is set to match. Both work. The key version has the property that a stale address held by a program points at storage whose key no longer matches, so the program’s use of the stale address fails rather than silently reaching the new occupant. That property is worth having, and it is why the mechanism persisted for decades after it was technically superseded.