Memory and storage

Increasing order:

$$\text{bit}<\text{nibble}<\text{byte}<\text{kilobyte}<\text{megabyte}<\text{gigabyte}<\text{terabyte}$$

• $1$ bit $=1$ binary digit ($0$ or $1$)
• $1$ nibble $=4$ bits
• $1$ byte $=8$ bits $=$ one character
• $1$ KB $=1024$ bytes $=2^{10}$ bytes
• $1$ MB $=1024$ KB $=2^{20}=1,048,576$ bytes
• $1$ GB $=1024$ MB $=2^{30}=1,073,741,824$ bytes
• $1$ TB $=1024$ GB $=2^{40}\approx 1.1\times 10^{12}$ bytes

The single sentence that carries the distinction: primary memory holds what the computer is working on, secondary memory holds what it will need later.

RAM — Random Access Memory. The computer's working memory, holding the operating system, running programs and their data. Two defining properties: any location can be accessed directly in the same time as any other (random access), and the contents are lost when power is removed (volatile). It is read/write. Two kinds:

• SRAM — stores each bit in a flip-flop, needs no refreshing, fast but expensive and bulky; used for cache.
• DRAM — stores each bit as charge in a capacitor, must be refreshed thousands of times per second, slower but cheap and dense; used for main memory.

ROM — Read Only Memory. Holds data written once and thereafter only read, and is non-volatile. It contains what the machine needs before any software is available: the BIOS/UEFI and the bootstrap loader that locates and starts the operating system.

Types of ROM.

1. MROM (Masked ROM). Contents fixed during manufacture using a mask. Cannot be changed at all. Cheapest in very large quantities.

2. PROM (Programmable ROM). Supplied blank; the user writes it once with a special device called a PROM programmer or burner, after which it is permanent. Write once, read many.

3. EPROM (Erasable PROM). Can be erased and rewritten, but only wholesale: the whole chip is cleared by exposing it to ultraviolet light through a quartz window, which takes several minutes and requires removing the chip.

4. EEPROM (Electrically Erasable PROM). Erased and rewritten electrically, byte by byte, in place, without removing the chip. Flash memory is a form of EEPROM, and is what pen drives, memory cards and SSDs are made of — which is why a modern BIOS can be updated by software.

The progression across the four is simply increasing ease of rewriting.

Cache memory is a small block of very fast SRAM placed between the CPU and main memory. It holds copies of the data and instructions the CPU has used most recently or uses most often.

How a request is served. When the CPU needs an item it looks in cache first.

• Cache hit — the item is present, and is supplied at cache speed. No RAM access is needed.
• Cache miss — the item is absent, so it must be fetched from the slower main memory. On the way it is also copied into cache, on the expectation that it will be wanted again.

The hit ratio is the fraction of requests that are hits, and it is the figure that decides how much the cache is helping.

Why it works — locality of reference. Real programs do not access memory at random. They exhibit:

• temporal locality — an item used now is likely to be used again shortly (a loop counter, a running total)
• spatial locality — an item near one just used is likely to be needed next (the following instruction, the next element of an array)

Because of this, a small cache holding recent items captures a large share of all accesses.

Why performance improves. RAM access costs the CPU many idle clock cycles; cache access costs very few. If most accesses are hits, the CPU spends most of its time computing rather than waiting. Without cache, a fast processor would sit idle waiting on comparatively slow DRAM, and its speed would be largely wasted.

Levels. L1 is smallest and fastest, inside each core; L2 is larger and slightly slower; L3 is largest and shared between cores — a hierarchy within the hierarchy, for exactly the same reason as the main one.

Organisation of a hard disk. Data sits in concentric tracks on each platter surface; each track is divided into sectors, the smallest addressable unit; the same numbered track on every platter together forms a cylinder.

Access time on an HDD is the sum of three parts:

$$\text{access time}=\text{seek time}+\text{rotational latency}+\text{transfer time}$$

• Seek time — the time for the read/write head to move radially to the correct track. Mechanical, and the largest component.
• Rotational latency — having reached the track, the time waiting for the required sector to rotate under the head. On average half a revolution: at $7200$ rpm one revolution takes $8.33$ ms, so average latency is about $4.17$ ms.
• Transfer time — the time to actually read or write the data once positioned.

Why an SSD is so much faster. It has no head to move and no platter to rotate, so both seek time and rotational latency are zero. This is also why an SSD's performance barely changes when files are scattered, whereas a fragmented HDD slows noticeably.

The hierarchy. From fastest and smallest to slowest and largest:

$$\text{registers}\to \text{cache (L1, L2, L3)}\to \text{main memory (RAM)}\to \text{secondary (SSD, HDD)}\to \text{tertiary (tape, optical)}$$

Moving down the hierarchy, capacity rises and cost per byte falls; access time gets worse. Moving up, everything gets faster and more expensive per byte.

Why not build the whole machine from the fastest memory? Three reasons, and all three would still apply even with unlimited money.

1. Cost. SRAM, the memory used for cache, costs orders of magnitude more per byte than DRAM, which in turn costs far more than flash or magnetic storage. Building a machine with several terabytes of SRAM would put its price beyond any conceivable use.

2. Physics — density and heat. An SRAM cell needs six transistors; a DRAM cell needs one transistor and one capacitor. SRAM is therefore several times larger per bit, so far less of it fits on a chip. It also draws more power and produces more heat, which limits how much can be packed together and cooled.

3. Physics — distance. Even with free, cool, dense fast memory, signals travel at a finite speed. A larger memory occupies more physical space, so its far corners are further from the CPU and take longer to reach. Big memory is slow memory, unavoidably. This is why L1 cache is deliberately kept tiny — a larger L1 would be a slower L1.

Why the hierarchy works anyway. Because of locality of reference, a program at any moment uses only a small fraction of its data. The hierarchy keeps that active fraction near the top and everything else lower down, and moves items up as they are needed. The result is a system whose average access time approaches that of the fast levels while its capacity is that of the slow ones.

Volatility adds a second reason. The fast levels are all volatile. Even if a machine could hold everything in RAM, it would still need non-volatile secondary storage so that data survives being switched off.