Notes 0008

Memory Management

(read chapter 9 of the dinosaur book; you should also read Intel's architecture reference linked from the links page)

Overall Picture

Most computers have some sort of main memory, or RAM. Various architectures exist that enable various uses of such memory. These notes will provide a brief overview of various approaches.

Introduction

From an application's point of view, when a processor reads some memory at some location, that memory is referenced. Application programmers never worry about how it does this, they just know what to expect. This view works the same under Windows, DOS, and UNIX.

Internally, this memory could be accessed in vastly different ways.

Physical Memory

Every computer has some physical memory. Physical memory is the actual physical hardware that stores memory. Physical memory has its own address space. If you only have 64MB or RAM, you cannot access more than that of physical memory.

Your programs don't usually care how much physical memory exists.

Logical Memory

When your program accesses some variable in memory, the address that you specify is a logical address. It is not an actual 'ram' location. Logical memory has its own address space, which means that when your program accesses logical memory, the system translates logical addresses into physical addresses.

Almost all computers use some sort of logical memory. Even the plain PC uses logical memory. You can access memory via a FFFF:FFFFh address (16 bit segment and 16 bit offset) in real mode DOS programs, yet systems of that era cannot address more than 1mb of physical memory.

The FFFF:FFFFh logical address is mapped to FFFFFh physical memory. Because we're translating a big address space into a relatively small one, some logical addresses will fall onto the same physical address. Thus, there are many ways of accessing the same physical byte.

In DOS, logical addresses have a segment and an offset (we'll talk about them a bit later), but to convert a logical address into a physical address we shift segment by 8 bits to the left, and add it to the offset. What we get is a 20bit address, which is 1mb.

Virtual Memory

There is also a concept of virtual memory. It is similar to logical memory in a sense that it doesn't directly access physical memory, but is quite different.

Given some physical memory, let's say we define some specific location as the start, say address 400. Now, every time we accesses memory using that start, it will add on that start to our memory. We can have many of these base memories, allowing us to have many programs running in whatever address they wish, but yet still all accessing different physical memory.

(ie: this allows us to have 2 programs running at address 123, yet still access different physical memory since they'd have different base).

There are other benefits like restricting the size of memory (for example, we specify the base address and its size, if some program tries to access memory through that base address and goes over the size, the error is flagged and the program is kicked out).

Paging

Paging is another way of abstracting the memory. What paging does is setup a table of memory blocks. Once a request comes in to access memory in some block (or page), the system determines where the memory is (is it loaded, or on the hard drive, etc.) and loads the memory. This allows systems to run many more programs than their physical RAM can accommodate.

The process is a bit more tedious than described here, but that's the overall picture.

Fragmentation

When allocating and freeing memory, we usually get fragmentation problems. Fragmentation means that some memory becomes of unusable size and generally just sits there doing nothing.

For example, it is not very efficient to care about every single byte of memory used, so most systems generalize allocation algorithms to work with sets of bytes, for example, if you request 2 bytes via malloc, you might get 1000. Those extra 998 bytes are just wasted space that you are not using, and the system cannot allocate to anything else.

There are two major types of fragmentation, external and internal fragmentation.

External fragmentation means that after many allocations and frees, free memory becomes broken up into many small unusable pieces. So even though collectively they may represent a large amount of memory, you cannot use it to run any program (programs need contiguous memory, etc.)

Internal fragmentation occurs when say we have 4kb pages, and our program is only using 2 bytes of that page. Most of the page's 4kb memory is considered busy by the system but is not used. So, again, you might have a lot of free memory, yet it is all tied by up internal fragmentation.

© 2006, Particle