Written and Maintained by Gregory Nacu
 

NEWS, EDITORIALS, REFERENCE

Subscribe to C64OS.com with your favorite RSS Reader
November 10, 2016Programming Theory

A Few Thoughts About Memory Management

If you read through the C64 programmer's reference guide, lovingly referred to as the PRG, a few things stand out as being really out of date. It was published in the early 1980s. There are sections in the PRG that discuss memory management. Their use of this term however should not be confused with what we mean today when we talk about memory management.

There isn't a whole lot of memory in a C64 to start with. The 6510's 16 bit address bus means memory addresses range from $0000 to $FFFF, that's 0 to 65535 in decimal, or 65536 1-byte-big addresses. Divide that number by 1024, the number of bytes in a kilobyte, and you get 64 kilobytes. A familiar number. 64K is not a big number, in computer science terms it's not a lot of space. And so traditionally every program has completely free reign over the entire machine and can do whatever it wants with all the available memory. Actually, not much will change in C64 OS, because that freedom is a strength we don't want to just throw away. But we'll return to this in another post.

What then does the PRG refer to as memory management? Well, that 64K addressing range has to be divided up between RAM, ROM, and I/O. And so different regions of addressing space are grouped together and usually drawn as a simple memory map. It might be shown like this:

+--------------------------------------------+			
| $E000 - $FFFF  KERNAL ROM - 8K             |
|                                            |
|                                            |
|                                            |
+--------------------------------------------+			
| $D000 - $DFFF  I/O - 4K                    |
|                                            |
+--------------------------------------------+			
| $C000 - $CFFF  HI MEM - 4K                 |
| C64 OS hangs out in here.                  |
+--------------------------------------------+			
| $A000 - $BFFF  BASIC ROM - 8K              |
|                                            |
|                                            |
|                                            |
+--------------------------------------------+			
| $8000 - $9FFF  HI BASIC / ROM - 8K         |
|                                            |
|                                            |
|                                            |
+--------------------------------------------+			
| $0801 - $7FFF  LO BASIC - 30K              |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
|                                            |
+--------------------------------------------+			
| $0000 - $0800  SYSTEM, STACK, SCREEN - 2K  |
+--------------------------------------------+			

The blocks are proportionally sized, so an 8K block is twice as tall as a 4K block. And you'll notice zero starts at the bottom and $FFFF is at the top. It's drawn this way because larger numbered addresses are referred to as higher in memory, this is just a convention.

Your typical C64 program needs to manage what memory will be used for what purpose. If you have some graphics data and some sound data and your program's main logic and so on, you need to have regions of contiguous memory into which those pieces fit. Then you have to consider whether or not your program will make use of the BASIC rom, many do not, or the KERNAL rom, more programs use this than the BASIC rom but not all. Part of managing memory in the PRG therefore is about how to use the 3-bits of the 6510's i/o port to instruct the PLA to swap one of these ROMs out and swap in some RAM instead. That's memory management in a nutshell for a typical C64 program, like a game.

This is not what is meant by memory management in a modern computer. A modern computer has lots of memory and the way it takes advantage of all that memory is by allowing lots of programs to run at the same time. But if lots of programs are running at the same time, they have to share memory. And a given program never knows when in the usage cycle it will be loaded in. Maybe 10 other programs were loaded in before it and they are already using a bunch of memory. Maybe there is just one program running that for some reason needs to consume lots and lots of memory just for itself. The point is that you don't know. The role of an operating system is to manage memory, in the sense of controlling what memory is used and what memory is still available.

When a program needs some memory, it doesn't just assume that a range of addresses is available, because it doesn't know. Instead when a program needs some memory it asks the operating system to give it some memory, and when it's done using some memory it tells the operating system that that memory is free again.

As I've said elsewhere on this site, I don't think the C64 (without a SuperCPU) is ideally suited to run multiple applications at the same time. I know it can be done, because there are OS projects out there that do it. But they are more experimental, more proof–of–concept, than they are useful. A C64's resources, RAM and CPU, but also disk i/o speed and screen resolution, are already so limited that for an application to be useful it needs everything it can get. And if you're running more than one application, every application is running on a mere fraction of what a C64 has to offer.

Well, if C64 OS isn't multi–tasking, if multiple programs aren't running at the same time, then they aren't sharing memory, and so, there is no need for a memory manager, right? Wrong. There are many instances and many types of programs that, within that one program, need to work on many pieces of arbitrary length data asynchronously. Whoa, what does that all mean? Well, a lot of interesting use cases open up when you introduce a more modern user interface. Consider the way a BASIC program works on the C64. The PRG, by the way, also shows its age when it describes common user interaction models and how to program for them. These interaction models are old! In BASIC, you have the input statement. It's used to allow the user to put in some data, at a point in the flow of the program when some information is needed. The problem is that while you're in that input mode, you are stuck in that particular input until you are done and press return. And then the program moves on. This type of data input is what I'm calling synchronous. It's synchronized with the stage of the program.

But, if you have a mouse pointer, and you have three text fields, you can click in one text field and type a few words. Then you can click on a different text field and enter a few words there, before clicking back on the first and carrying on there. The field you're putting data into isn't synchronized with the program's internal flow. It's open for you to bounce around asynchronously to various parts of the program, in any order. Arbitrary length data means that the data being worked on has an unknown length. If you have two fields of data, but you don't know how much data is going to go in each one, what do you do? Where do you put those bytes of data as they come in? You could divide your whole memory up into two huge pools, 15K for the first field, 15K for the next. But, that's hugely wasteful if you end up only with a few bytes in each. And it's also hugely wasteful and inopportune if one field needs 1K and the other needs 20K. Input fields are one simple to understand example, but in practice this example might feel a bit strained.

Here's a more practical example of arbitrary length data. Loading a directory from disk, when there is already a program resident in memory. Before you load that directory in, you have no idea how big it's going to be. Mabe it has 5 files, maybe it has 144 files. You don't know. Where do you find the space to store an arbitrarily large amount of data? Well, most C64 programmers haven't bothered. I think this is the reason why it was so common for programs to dump the directory directly into screen memory. It's a chunk of memory that is displayed to the user right away, and as more data comes in the old data just falls off the top of the screen and is actually removed from memory. The way arbitrarily long data is handled here is that it is cropped to a non-arbitrarily big space. But, this is not how a modern user expects to be able to interact with their computer. The reason the typical developer didn't bother to create a structure in memory that could hold a directory, sort it and scroll up and down through it, is because managing the memory required to do that was too difficult and not worth the effort.

Here's my point. Even in a single–task operating system, a memory manager is an essential component in producing a modern experience. This is especially true when loading data that comes from the internet. But it is also true whenever a program is resident in memory at the same time as allowing the user to compose a message, or view a graphic, or parse a file from disk, all of which may very well be happening as part of a single program. Without a memory manager these tasks become very difficult. In my next post, I'll talk about the kind of memory manager I am in the process of writing for C64 OS.