User:Millosh/Internet and Programming for Linguists/The Big Picture/Keeping processes

The kernel's scheduler takes care of dividing processes in time. Your operating system also has to divide them in space, so that processes can't step on each others'; working memory. Even if you assume that all programs are trying to be cooperative, you don't want a bug in one of them to be able to corrupt others. The things your operating system does to solve this problem are called memory management.

Each process in your zoo needs its own area of memory, as a place to run its code from and keep variables and results in. You can think of this set as consisting of a read-only code segment (containing the process's instructions) and a writeable data segment (containing all the process's variable storage). The data segment is truly unique to each process, but if two processes are running the same code Unix automatically arranges for them to share a single code segment as an efficiency measure.

Virtual memory: the simple version

Efficiency is important, because memory is expensive. Sometimes you don't have enough to hold the entirety of all the programs the machine is running, especially if you are using a large program like an X server. To get around this, Unix uses a technique called <a name="vm"> virtual memory. It doesn't try to hold all the code and data for a process in memory. Instead, it keeps around only a relatively small working set; the rest of the process's state is left in a special swap space area on your hard disk.

Note that in the past, that "Sometimes" last paragraph ago was "Almost always" — the size of memory was typically small relative to the size of running programs, so swapping was frequent. Memory is far less expensive nowadays and even low-end machines have quite a lot of it. On modern single-user machines with 64MB of memory and up, it's possible to run X and a typical mix of jobs without ever swapping after they're initially loaded into core.

Virtual memory: the detailed version

Actually, the last section oversimplified things a bit. Yes, programs see most of your memory as one big flat bank of addresses bigger than physical memory, and disk swapping is used to maintain that illusion. But your hardware actually has no fewer than five different kinds of memory in it, and the differences between them can matter a good deal when programs have to be tuned for maximum speed. To really understand what goes on in your machine, you should learn how all of them work.

The five kinds of memory are these: processor registers, internal (or on-chip) cache, external (or off-chip) cache, main memory, and disk. And the reason there are so many kinds is simple: speed costs money. I have listed these kinds of memory in decreasing order of access time and increasing order of cost. Register memory is the fastest and most expensive and can be random-accessed about a billion times a second, while disk is the slowest and cheapest and can do about 100 random accesses a second.

Here's a full list reflecting early-2000 speeds for a typical desktop machine. While speed and capacity will go up and prices will drop, you can expect these ratios to remain fairly constant — and it's those ratios that shape the memory hierarchy.

Disk

Size: 13000MB Accesses: 100KB/sec

Main memory

Size: 256MB Accesses: 100M/sec

External cache

Size: 512KB Accesses: 250M/sec

Internal Cache

Size: 32KB Accesses: 500M/sec

Processor

Size: 28 bytes Accesses: 1000M/sec

We can't build everything out of the fastest kinds of memory. It would be way too expensive — and even if it weren't, fast memory is volatile. That is, it loses its marbles when the power goes off. Thus, computers have to have hard disks or other kinds of non-volatile storage that retains data when the power goes off. And there's a huge mismatch between the speed of processors and the speed of disks. The middle three levels of the memory hierarchy (internal cache, external cache, and main memory) basically exist to bridge that gap.

Linux and other Unixes have a feature called virtual memory. What this means is that the operating system behaves as though it has much more main memory than it actually does. Your actual physical main memory behaves like a set of windows or caches on a much larger "virtual" memory space, most of which at any given time is actually stored on disk in a special zone called the swap area. Out of sight of user programs, the OS is moving blocks of data (called "pages") between memory and disk to maintain this illusion. The end result is that your virtual memory is much larger but not too much slower than real memory.

How much slower virtual memory is than physical depends on how well the operating system's swapping algorithms match the way your programs use virtual memory. Fortunately, memory reads and writes that are close together in time also tend to cluster in memory space. This tendency is called locality, or more formally locality of reference — and it's a good thing. If memory references jumped around virtual space at random, you'd typically have to do a disk read and write for each new reference and virtual memory would be as slow as a disk. But because programs do actually exhibit strong locality, your operating system can do relatively few swaps per reference.

It's been found by experience that the most effective method for a broad class of memory-usage patterns is very simple; it's called LRU or the "least recently used" algorithm. The virtual-memory system grabs disk blocks into its working set as it needs them. When it runs out of physical memory for the working set, it dumps the least-recently-used block. All Unixes, and most other virtual-memory operating systems, use minor variations on LRU.

Virtual memory is the first link in the bridge between disk and processor speeds. It's explicitly managed by the OS. But there is still a major gap between the speed of physical main memory and the speed at which a processor can access its register memory. The external and internal caches address this, using a technique similar to virtual memory as I've described it.

Just as the physical main memory behaves like a set of windows or caches on the disk's swap area, the external cache acts as windows on main memory. External cache is faster (250M accesses per sec, rather than 100M) and smaller. The hardware (specifically, your computer's memory controller) does the LRU thing in the external cache on blocks of data fetched from the main memory. For historical reasons, the unit of cache swapping is called a line rather than a page.

But we're not done. The internal cache gives us the final step-up in effective speed by caching portions of the external cache. It is faster and smaller yet — in fact, it lives right on the processor chip.

If you want to make your programs really fast, it's useful to know these details. Your programs get faster when they have stronger locality, because that makes the caching work better. The easiest way to make programs fast is therefore to make them small. If a program isn't slowed down by lots of disk I/O or waits on network events, it will usually run at the speed of the smallest cache that it will fit inside.

If you can't make your whole program small, some effort to tune the speed-critical portions so they have stronger locality can pay off. Details on techniques for doing such tuning are beyond the scope of this tutorial; by the time you need them, you'll be intimate enough with some compiler to figure out many of them yourself.

The Memory Management Unit

Even when you have enough physical core to avoid swapping, the part of the operating system called the memory manager still has important work to do. It has to make sure that programs can only alter their own data segments — that is, prevent erroneous or malicious code in one program from garbaging the data in another. To do this, it keeps a table of data and code segments. The table is updated whenever a process either requests more memory or releases memory (the latter usually when it exits).

This table is used to pass commands to a specialized part of the underlying hardware called an MMU or memory management unit. Modern processor chips have MMUs built right onto them. The MMU has the special ability to put fences around areas of memory, so an out-of-bound reference will be refused and cause a special interrupt to be raised.

If you ever see a Unix message that says "Segmentation fault", "core dumped" or something similar, this is exactly what has happened; an attempt by the running program to access memory (core) outside its segment has raised a fatal interrupt. This indicates a bug in the program code; the core dump it leaves behind is diagnostic information intended to help a programmer track it down.

There is another aspect to protecting processes from each other besides segregating the memory they access. You also want to be able to control their file accesses so a buggy or malicious program can't corrupt critical pieces of the system. This is why Unix has file permissions which we'll discuss later.

How does my computer store things in memory?

You probably know that everything on a computer is stored as strings of bits (binary digits; you can think of them as lots of little on-off switches). Here we'll explain how those bits are used to represent the letters and numbers that your computer is crunching.

Before we can go into this, you need to understand about the word size of your computer. The word size is the computer's preferred size for moving units of information around; technically it's the width of your processor's registers, which are the holding areas your processor uses to do arithmetic and logical calculations. When people write about computers having bit sizes (calling them, say, "32-bit" or "64-bit" computers), this is what they mean.

Most computers (including 386, 486, and Pentium PCs) have a word size of 32 bits. The old 286 machines had a word size of 16. Old-style mainframes often had 36-bit words. The AMD Opteron, Intel Itanium, and the Alpha from what used to be DEC and is now Compaq have 64-bit words.

The computer views your memory as a sequence of words numbered from zero up to some large value dependent on your memory size. That value is limited by your word size, which is why programs on older machines like 286s had to go through painful contortions to address large amounts of memory. I won't describe them here; they still give older programmers nightmares.

Numbers

Integer numbers are represented as either words or pairs of words, depending on your processor's word size. One 32-bit machine word is the most common integer representation.

Integer arithmetic is close to but not actually mathematical base-two. The low-order bit is 1, next 2, then 4 and so forth as in pure binary. But signed numbers are represented in twos-complement notation. The highest-order bit is a sign bit which makes the quantity negative, and every negative number can be obtained from the corresponding positive value by inverting all the bits and adding one. This is why integers on a 32-bit machine have the range -2³¹ to 2³¹ - 1. That 32nd bit is being used for sign; 0 means a positive number or zero, 1 a negative number.

Some computer languages give you access to unsigned arithmetic which is straight base 2 with zero and positive numbers only.

Most processors and some languages can do operations in floating-point numbers (this capability is built into all recent processor chips). Floating-point numbers give you a much wider range of values than integers and let you express fractions. The ways in which this is done vary and are rather too complicated to discuss in detail here, but the general idea is much like so-called ‘scientific notation’, where one might write (say) 1.234 * 10²³; the encoding of the number is split into a mantissa (1.234) and the exponent part (23) for the power-of-ten multiplier (which means the number multiplied out would have 20 zeros on it, 23 minus the three decimal places).

Characters

Characters are normally represented as strings of seven bits each in an encoding called ASCII (American Standard Code for Information Interchange). On modern machines, each of the 128 ASCII characters is the low seven bits of an octet or 8-bit byte; octets are packed into memory words so that (for example) a six-character string only takes up two memory words. For an ASCII code chart, type ‘man 7 ascii’ at your Unix prompt.

The preceding paragraph was misleading in two ways. The minor one is that the term ‘octet’ is formally correct but seldom actually used; most people refer to an octet as byte and expect bytes to be eight bits long. Strictly speaking, the term ‘byte’ is more general; there used to be, for example, 36-bit machines with 9-bit bytes (though there probably never will be again).

The major one is that not all the world uses ASCII. In fact, much of the world can't — ASCII, while fine for American English, lacks many accented and other special characters needed by users of other languages. Even British English has trouble with the lack of a pound-currency sign.

There have been several attempts to fix this problem. All use the extra high bit that ASCII doesn't, making it the low half of a 256-character set. The most widely-used of these is the so-called ‘Latin-1’ character set (more formally called ISO 8859-1). This is the default character set for Linux, HTML, and X. Microsoft Windows uses a mutant version of Latin-1 that adds a bunch of characters such as right and left double quotes in places proper Latin-1 leaves unassigned for historical reasons (for a scathing account of the trouble this causes, see the demoroniser page).

Latin-1 handles western European languages, including English, French, German, Spanish, Italian, Dutch, Norwegian, Swedish, Danish. However, this isn't good enough either, and as a result there is a whole series of Latin-2 through -9 character sets to handle things like Greek, Arabic, Hebrew, Esperanto, and Serbo-Croatian. For details, see the ISO alphabet soup page.

The ultimate solution is a huge standard called Unicode (and its identical twin ISO/IEC 10646-1:1993). Unicode is identical to Latin-1 in its lowest 256 slots. Above these in 16-bit space it includes Greek, Cyrillic, Armenian, Hebrew, Arabic, Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Thai, Lao, Georgian, Tibetan, Japanese Kana, the complete set of modern Korean Hangul, and a unified set of Chinese/Japanese/Korean (CJK) ideographs. For details, see the Unicode Home Page.