There are many levels of memory in a computer. In general, there is a tradeoff between memory access time (speed) vs. cost and/or capacity. The different types of memory can be viewed as a hierarchy, with very fast access, but expensive/limited capacity memory at the top, and slow access, but cheap/large capacity memory at the bottom. Here is a list of memory levels, ranked by access time

• Registers
• on-board cache
• cache on a separate chip (SRAM)
• main memory (DRAM)
• magnetic disk
• CD-ROM
• Magnetic tape

Registers

All CPUs have a number of user registers where a program can store data. Access time to registers is the fastest of any memory type, but the number of registers is very limited. Compilers try to optimize programs by storing often used data in registers during the execution of a program. C has a feature which allows a user to suggest to the compiler that a particular variable be stored in a register by declaring it like this:
register x
However, this is not used much because modern compilers are pretty good at guessing what data should be stored in registers.

Cache

The concept of cache memory will come up repeatedly in the remainder of this course. The basic idea is that frequently used data is stored in memory which has faster access. Cache memory is based on the principle of locality. This principle states that programs access a relatively small portion of their address space at any point in time. There are two types of locality.

Temporal locality An item that was recently referenced is likely to be referenced again soon

Spatial locality A program that references a particular address is likely to reference nearby addresses soon.

Most real-world programs display these two principles very strongly. If you look at a large program, at any given time it is likely to be executing inside a loop which accesses only a small number of variables.

Cache memory is based on the principle of Temporal Locality. The idea behind a cache is to store recently used data in a faster (i.e. more expensive/smaller capacity) level of memory on the assumption that it will be used again soon.

There are two types of volatile memory, SRAM (static random access memory) and DRAM (dynamic random access memory). SRAM is faster, but is more expensive. SRAM has a transfer rate as fast as the CPU, and is used in cache memory. DRAM has a transfer rate slower than the CPU and is used in main memory.

Here is a chart from Patterson and Hennessy showing cost and access time by memory type

Memory technology	Typical access time	$ per MByte in 2004
SRAM	0.5-5 ns	$4,000-$10,000 / GB
DRAM	50-70 ns	$100-$200 / GB
Magnetic disk	5-20 million ns	$0.50-$2.00 / GB

Cache memory can either be on the processor chip (Level 1) or on a separate chip (Level 2). L1 cache is faster than L2 cache, but both are faster than ordinary DRAM (main memory). Many processors have two L1 caches, one for data and one for instruction. Modern processors typically have 64KB of L1 instruction cache and 64KB of L1 data cache. L2 cache is typically 512KB or 1 MB.

Caching only works if the program first searches in the cache to see if the data that it is looking for is there. The unit of memory in the cache is the block. If the data that the program needs is in cache, this is called a hit, and if it is not in the cache, this is called a miss (You could have guessed that). The percentage of cache searches which produce hits is called the hit rate.

If the program searches the cache and does not find the data that it is looking for, it has to look in main memory. When this occurs, the contents of the address in main memory are copied to the cache. Not only is this slower, but the program has incurred an additional penalty because it took some time to determine that that data was not in the cache. Thus, caching can only be successful if searching in the cache is substantially faster than accessing data in main memory and the hit rate is high.

Searching the cache has to be implemented in hardware. It makes no sense to have a software implementation of a process that has to be faster than accessing main memory. Even if the search algorithm is implemented in hardware, it has to be fast. One possible mapping strategy for cache memory is direct mapping, in which the address of a particular item in the cache is determined by its address in main memory. For example, we could simply use the main memory address (or one of the fields of the address), modulo the cache size.

Suppose a cache holds 4096 words (cache size is generally a power of 2).

Here is a typical 32 bit memory address in binary. The bits which refer to the cache address are underlined.

01110110 00011001 11001101 10101100

This address would be stored in our cache at address 1101 10101100.

Implementing such an algorithm is hardware is easy. The only problem is that if there happen to be two (or more) addresses that need to be in the cache that have the same values in this field, only one could be cached.

The cache memory has to contain not only the data value, but also a tag containing the rest of the memory address so that the CPU can confirm that that value in the cache is indeed that value that it is looking for. It also needs to have a flag indicating whether or not the address is valid.

Direct mapping as described above is not used much now because of the collision problem. There are two other mapping functions. N-way set associative cache allows each logical address to be stored in any of N slots in the cache. If N is 4, then each address can be stored in one of 4 slots, which means that up to four words (or blocks) with the same cache address can be stored at the same time. The problem of course is the process of finding an address in cache memory becomes more complicated. It has to be done very fast, so the searching is done in parallel, with all N entries searched at the same time. Patterson and Hennessy describe the design of such a circuit.

You can think of direct mapping as an instance of this where N is 1.

The third mapping function is fully associated, in which any value can be stored in any slot in the cache. This is equivalent to N-way associative cache where N is the size of the cache. It takes very complex circuitry to implement this, but it has the highest hit rate.

Cache design issues

There are a number of issues around the design of the cache.

• The size of the cache It should be intuitively obvious to the casual observer that the larger the cache, the better the performance. However, even a small cache will speed up performance dramatically because most programs show very strong temporal locality.

• Block size i.e. how large is each element in the cache. Our examples assumed that each slot in the cache held one word, but many caches will have a larger block size. When the program requests a word which is not in the cache and the cache has to go to main memory to fetch it, more than the single word is transferred. This makes sense because of the principle of spatial locality. If a program recently needed the value at address n, it is likely that it will soon need the value at address n+1.

  Of course, with larger block size, the cache has fewer slots.

• The mapping function We discussed direct mapping above. In direct mapping, the address in the cache is determined by a field in the logical address. It is fast, but the hit rate goes down because if two words which need to be in the cache happen to have the same cache address, only one can be stored.
• The replacement algorithm. If a new block has to be loaded into the cache, it has to replace an already existing block. With direct mapping, this is not an issue, but with N-way set associative caching or fully associative caching, there are several candidates to be replaced. The best strategy is to replace that block which has been least recently used, but this requires keeping track of when each block in cache was last accessed.
• The write policyWith any kind of cache memory, there is an issue of maintaining cache consistency. If the contents of a particular address are copied into cache and then modified in the cache, the contents of the cache and the contents of the actual memory address differ. This means that if that slot in cache memory gets overwritten, the system has to write that new value out to main memory, and this represents additional overhead.

  Cache consistency can also create problems if the system has Direct Memory Access (DMA) in which I/O channels write directly to memory, or if the system has multiple CPUs (with different cache memories).

  Consider this simple sequence of events in which a counter is incremented on a system with two CPUs.

  • Process One on CPU A accesses memory Location L. It copies the value of L, which happens to be 17 to its cache.
  • Process One increments the value of L, setting it to 18. Because L is in cache memory, main memory is not accessed.
  • Process Two, running on CPU B, accesses memory Location L. It copies the value of L (still 17) into its cache.
  • Process Two increments the value of L, setting it to 18. Because L is in cache memory, main memory is not accessed.
  • Process One writes the value of L from cache to main memory. Location L in main memory has the value 18.
  • Process Two writes the value of L from cache to main memory. It also writes the value 18.
  • If this was a counter which counted the number of times that an event occurred, note that the system missed one of these events. The event occurred twice, once in each Process, but the counter was only incremented by 1.

  One solution to this problem is to write cache memory back to main memory whenever its value changes, but if the program is doing a lot of writing, this can largely negate the benefit of using cache memory. The opposite extreme is to only write modified cache back to the main memory when the block is replaced, but that strategy leaves the door open for problems such as the above example.

Memory Management

In order to implement multiprogramming, the code for several different processes has to be in memory at the same time. This introduces some issues regarding memory layout and memory management.

All modern operating systems solve this problem using virtual memory, which will be discussed in detail shortly, but first we will look at some solutions which do not involve virtual memory.

The introduction of multiprogramming resulted in two new problems for the operating system which were not issues when only one process at a time was in memory (monoprogramming). These problems were address relocation and protection.

Address Relocation When the linker is creating an executable file, it has to assign memory addresses for all of the instructions and data. If all programs were loaded at the same address, this would be straightforward, but with multiprogramming, the linker does not know exactly where in memory the process will be loaded, so it does not know the actual physical addresses.

Many modern processor architectures solve this problem by calculating addresses in two parts, a segment base and an offset from this segment base. The instructions and data are divided into segments. Often each function is in its own segment. Each individual instruction or data address is then calculated not as an absolute physical memory address, but as an offset from the base. The segment base is stored in one of the registers.

Thus, when a program is loaded into memory, it is not necessary to recalculate every address in the program, but it is still necessary to calculate the base register values for each segment, based on where in main memory the process happens to be loaded.

Protection If there are several processes loaded into memory at the same time, it is crucial that the operating system prevent one process from accessing data in another process. Usually this could happen only by accident, because one process would not know the address of other processes that happened to be in memory at the same time, but if the kernel is always loaded at the same place in memory, as is customary, it is important to prevent user programs from accessing kernel memory space.

If the architecture supports segmentation, then protection is often implemented by having not only a base register for a segment, but a limit register as well, which represents the highest address in that segment. Whenever a running program accesses an address, its offset is checked to make sure that it is less than the value in the limit register.

Memory management without virtual memory

Consider a simple computer which has 120 units of memory, with addresses 1 .. 120. The bottom 20 units of memory are reserved for the kernel, which leaves 100 units for user processes. Each process has a fixed size which is known when it is loaded, and processes have to be loaded into contiguous memory.

The first process takes up 20 units of memory, and is loaded at addresses 20 - 39. The next process takes up 40 units of memory and is loaded at addresses 40 - 79. The the third process takes up 30 units of memory and is loaded at addresses 80 - 110. Memory now looks like this.

The Process 2 completes, thus freeing up its memory. Process 4, of size 30, is now loaded at address 40. Memory now looks like this.

Process 5, of size 30 needs to be loaded but there is not enough memory, so it is swapped out, waiting for more memory. Process 1 terminates, freeing up its memory. There is now 40 units of available memory, theoretically more than enough to load process 5, but there is no contiguous empty space for it, so it still cannot be loaded.

This demonstrates a problem known as fragmentation. If the operating system uses a simple placement scheme to decide where to place processes in memory, over time, many small holes develop, which reduces the efficiency of memory utilization. There are a number of solutions to the memory placement issue, and each has some strengths and weaknesses.

Memory Management without partitions

The above model used Memory management without partitions. When a new process was created, if there was a large enough unused space in memory, it was loaded, otherwise it was put aside until a large enough segment of memory became available. As we saw, this strategy tends to result in memory fragmentation; lots of small holes which are too small to hold most programs.

If several holes are available, where does the system place the new process? Suppose that a new process of size 20 has been created, and there are three holes in memory, one of size 30 at address 20, one of size 20 at address 60, and one of size 40 at address 100.

Where do we place our new process? Four algorithms have been proposed.

Best fit The best fit algorithm says to place a process in the smallest hole that will accommodate it, on the assumption that this will lead to the least fragmentation. The best fit strategy would place our new process at address 60.

Worst fit The worst fit algorithm places the new process in the largest hole. This would place the new process at address 100.

First fit The first fit algorithm places the new process in the first hole that it finds that is large enough. This would place our new process at address 20. The rationale for this is that in order to implement either of the first two algorithms, it is necessary to search all possible holes, and of course this takes time.

Next fit The next fit algorithm is similar to first fit except that instead of starting at the beginning of the list of holes each time, we start searching where we left off last time, placing the new process in the first hole that we find that is large enough. This is a small improvement over first fit, because with first fit, processes tend to be bunched at the low end of memory.

Research and simulations on these four algorithms do not show large differences in performance between any of them. Worst fit performs somewhat more poorly than the others, as one might predict, but all have the problem of fragmentation over time.

There are two ways that such a memory model might be implemented. One is to maintain a linked list of all of the holes in memory. This list is often called the free list because it is a list of all of the free space in memory.

This list would need to be updated whenever a new process is loaded into one of the holes or a process terminates, thus creating a new hole or making a current hole larger. When a process terminates, it has two neighbors, one above and one below (unless it is the very first process or the very last process). There are four possibilities.

• both neighbors are holes - in this case consolidate the two holes and the space occupied by the process into one large hole
• a hole above a process below - in this case, combine the hole above with the space occupied by the process into a single larger hole
• a hole below, a process above - same as above
• both neighbors are processes. In this case, simply create a new link in the hole linked list.

An alternative data structure is to maintain a bitmap, with a bit corresponding to each allocation unit of memory. If a particular allocation unit is occupied, its bit is set to 1, and if the segment is unoccupied, its bit is set to zero. The smaller the allocation unit, the larger the bitmap has to be. When the memory manager wants to allocate a program of size k units, it has to search the bitmap for a run of at least k unused units, and this can be time consuming.

Compaction

One solution to the problem of fragmentation is to periodically run a program which compacts memory by moving all of the current processes to replace the small holes with one large hole.

The obvious disadvantage of this is that such a program would have to be fairly time consuming. The segment addresses in each process need to be recalculated and changed, and the memory pointers in the Process Control Blocks need to be reassigned to reflect the new addresses of the process.

Fixed Partitions

Another solution to the fragmentation problem is to used partitions of fixed size. There are two models. One is to have all partitions the same size, and a process has to be loaded into contiguous partitions. This prevents a lot of the fragmentation described above, because it is not permitted to have lots of small holes. However, it introduces a new kind of fragmentation. The type of fragmentation described above is called external fragmentation because the holes are outside of any particular partition. If partitions are of fixed size, we can get internal fragmentation, which is defined as holes inside a partition. Suppose that the partitions are all of size 64KB. A process of size 70KB has to be assigned to two partitions, and so the remaining 58KB of the partition are wasted. They are not available for other processes.

Some IBM mainframe computers in the 1960s had fixed partitions but of various sizes. Some partitions were large, others were small.

The buddy system An interesting memory management model which represents a compromise between the fixed partition model and the variable partition model is the buddy system. This is actually used on some linux systems.

Memory blocks are available in sizes 2^K, L ≤ K ≤ U. So 2^L is the smallest block allocated, and 2^U is the largest block allocated (often the size of all available memory).

Initially the entire space for allocation is treated as a single block of size 2^U. If a request of size s where 2^U-1 < s ≤ 2 , then the entire space is allocated. Otherwise the block is split in two equal sized buddies. This process continues until a suitable block is assigned. The system maintains a list of holes of each size 2ⁱ. A hole can be removed from the list if it is split in half. Whenever both buddies of size 2ⁱ become available, they are coalesced into a single block of size 2ⁱ⁺¹ and put on that list.

An example will clarify this. Consider a system with 128K of memory. Initially, all 128K (2¹⁷) are in one partition.

The first process to be loaded is 30K. The one large partition is divided into two partitions of 64K each, and one of these is divided again into two partitions of 32K each. The new process is loaded into one of these two partitions, leaving two empty partitions, one of size 32K and one of size 64K. There are two K of internal fragmentation, that is, memory inside a partition which is not used or usable. The memory layout looks like this.

The next process to be loaded is 12K. The 32K partition is divided into two 16K partitions, and this process is loaded into one of them. Memory now looks like this.

The next process to be loaded is of size 50K, so it is loaded into the 64K partition.

The only remaining empty partition is 16K. The next process to be loaded is of size 20K, but there is no partition large enough, so it has to wait for one of the currently running processes to finish.

Process 1 terminates, freeing up a 32K partition, so Process 4 is loaded here.

Processes 2 and 4 terminate, freeing up their partitions. Because these are adjacent, they can be combined into one large partition of size 64.

The buddy system of memory management results in internal fragmentation, but the advantage is that the small partitions get consolidated over time as processes terminate.

Swapping

The class on process scheduling discussed swapping. Swapping involves removing entire processes from memory, copying them to disk, when the system becomes overloaded. Swapping is done either when there are too many runnable processes so that none of them receive much CPU time, or, more commonly, when there is not enough memory. Swapping is particularly important when there are processes loaded into memory which are spending long periods of time waiting for user input or for other I/O events which occur infrequently. If there are processes waiting to be loaded, it is wasteful to keep a process in memory waiting for an event which is unlikely to occur soon.

The system does not know when these events will occur, but a general rule is that the longer a process has been waiting for an event, the less likely it is that this event will happen soon, so a reasonable swapping stragegy is to look for a process or processes which have been blocked for a long time and swap them out.

Virtual Memory

The memory management strategies for multiprogramming systems described in the previous lesson were based on two assumptions: