Staticand dynamic approaches
Thereare two basic approaches to memory usage: static and dynamic.
Static memory approaches assume that the addressesdon’t change. This may be a virtual memory illusion, or may be the actualphysical layout. The static memory allocation may be through absolute addressesor through PC relative addresses (to allow for relocatable, reentrant, and/orrecursive software), but in either case, the compiler or assembler generates aset of addresses that can not change for the life of a program or process.
Dynamic memory approaches assume that theaddresses can change (although change is often limited to predefined possibleconditions). The two most common dynamic approaches are the use of stack framesand the use of pointers or handlers. Stack frames are used primarily fortemporary data (such as fucntion or subroutine variables or loop counters).Handles and pointers are used for keeping track of dynamically allocated blocksof memory.
Absolute addressing
Tolook at memory use by programs and operating systems, let’s first examine themore simple problem of a single program with complete control of the computer (suchas in a small-scale embedded system or the earliest days of computing).
Themost basic form of memory access is absolute addressing, in which theprogram explicitely names the address that is going to be used. An address is anumeric label for a specific location in memory. The numbering system isusually in bytes and always starts counting with zero. The first byte ofphysical memory is at address 0, the second byte of physical memory is ataddress 1, the third byte of physical memory is at address 2, etc. Someprocessors use word addressing rather than byte addressing. The theoreticalmaximum address is determined by the address size of a processor (a 16 bitaddress space is limited to no more than 65536 memory locations, a 32 bitaddress space is limited to approximately 4 GB of memory locations). The actualmaximum is limited to the amount of RAM (and ROM) physically installed in thecomputer.
Aprogrammer assigns specific absolute addresses for data structures and programroutines. These absolute addresses might be assigned arbitrarily or might haveto match specific locations expected by an operating system. In practice, theassembler or complier determines the absolute addresses through an orderlypredictable assignment scheme (with the ability for the programmer to overridethe compiler’s scheme to assign specific operating system mandated addresses).
Thissimple approach takes advantage of the fact that the compiler or assembler canpredict the exact absolute addresses of every program instruction or routineand every data structure or data element. For almost every processor, absoluteaddresses are the fastest form of memory addressing. The use of absoluteaddresses makes programs run faster and greatly simplifies the task of compilingor assembling a program.
Somehardware instructions or operations rely on fixed absolute addresses. Forexample, when a processor is first turned on, where does it start? Mostprocessors have a specific address that is used as the address of the firstinstruction run when the processer is first powered on. Some processors providea method for the start address to be changed for future start-ups. Sometimesthis is done by storing the start address internally (with some method forsoftware or external hardware to change this value). For example, on power upthe Motorola 680x0, the processor loads the interrupt stack pointer with thelongword value located at address 000 hex, loads the program counter with thelongword value located at address 004 hex, then starts execution at the frshlyloaded program counter location. Sometimes this is done by reading the startaddress from a data line (or other external input) at power-up (and in thiscase, there is usually fixed external hardware that always generates the samepre-assigned start address).
Anothercommon example of hardware related absolute addressing is the handling oftraps, exceptions, and interrupts. A processor often has specific memoryaddresses set aside for specific kinds of traps, exceptions, and interrupts.Using a specific example, a divide by zero exception on the Motorola 680x0produces an exception vector number 5, with the address of the exceptionhandler being fetched by the hardware from memory address 014 hex.
Somesimple microprocessor operating systems relied heavily on absolute addressing.An example would be the MS-DOS expectation that the start of aprogram would always be located at absolute memory address x100h (hexadecimal100, or decimal 256). A typical compiler or assembler directive for this wouldbe the
ORG directive (for “origin”).Thekey disadvantage of absolute addressing is that multiple programs clash witheach other, competing to use the same absolute memory locations for (possiblydifferent) purposes.
Overlay
So,how do you implement multiple programs on an operating system using absoluteaddresses? Or, for early computers, how do you implement a program that islarger than available RAM (especially at a time when processors rarely had morethan 1k, 2k, or 4k of RAM? The earliest answer was overlay systems.
Withan overlay system, each program or program segment is loaded into the exactsame space in memory. An overlay handler exists in another area of memory andis responsible for swapping overlay pages or overlay segments (both are thesame thing, but different operating systems used different terminology). When aoverlay segment completes its work or needs to access a routine in anotheroverlay segment, it signals the overlay handler, which then swaps out the oldprogram segment and swaps in the next program segment.
Anoverlay handler doesn’t take much memory. Typically, the memory space thatcontained the overlay handler was also padded out with additional routines.These might include key device drivers, interrupt handlers, exception handlers,and small commonly used routines shared by many programs (to save time insteadof continual swapping of the small commonly used routines).
Inearly systems, all data was global, meaning that it was shared by andavailable for both read and writes by any running program (in modern times,global almost always means available to a single entire program, no longermeaning available to all software on a computer). A section of memory was setaside for shared system variables, device driver variables, and interrupthandler variables. An additional area would be set aside as “scratch” ortemporary data. The temporary data area would be available for individualprograms. Because the earliest operating systems were batch systems, only oneprogram other than the operating system would be running at any one time, so itcould use the scratch RAM any way it wanted, saving any long term data tofiles.
Relocatablesoftware
Ascomputer science advance, hardware started to have support for relocatableprograms and data. This would allow an operating system to load a programanywhere convenient in memory (including a different location each time theprogram was loaded). This was a necessary step for the jump to interactiveoperating systems, but was also useful in early batch systems to allow formultiple overlay segments.
Demandpaging and swapping
Overlaysystems were superceded by demand paging and swapping systems. Ina swapping system, the operating system swaps out an entire program andits data (and any other context information).
Ina swapping system, instead of having programs explicitely requestoverlays, programs were divided into pages. The operating system would load aprogram’s starting page and start it running. When a program needed to access adata page or program page not currently in main memory, the hardware wouldgenerate a page fault, and the operating system would fetch therequested page from external storage. When all available pages were filled, theoperating system would use one of many schemes for figuring out which page todelete from memory to make room for the new page (and if it was a data pagethat had any changes, the operating system would have to store a temporary copyof the data page). The question of how to decide which page to delete is one ofthe major problems facing operating system designers.
Programcounter relative
Oneapproach for making programs relocatable is program counter relativeaddressing. Instead of branching using absolute addresses, branches(including subroutine calls, jumps, and other kinds of branching) were based ona relative distance from the current program counter (which points to theaddress of the currently executing instruction). With PC relative addreses, theprogram can be loaded anywhere in memory and still work correctly. The locationof routines, subroutines, functions, and constant data can be determined by thepositive or negative distance from the current instruction.
Programcounter relative addressing can also be used for determining the address ofvariables, but then data and code get mixed in the same page or segment. At aminimum, mixing data and code in the same segment is bad programming practice,and in most cases it clashes with more sophisticated hardware systems (such asprotected memory).
Basepointers
Basepointers (sometimescalled segment pointers or page pointers) are special hardware registers thatpoint to the start (or base) of a particular page or segment of memory.Programs can then use an absolute address within a page and either explicitlyadd the absolute address to the contents of a base pointer or rely on thehardware to add the two together to form the actual effective address ofthe memory access. Which method was used would depend on the processorcapabilities and the operatign system design. Hiding the base pointer from theapplication program both made the program easier to compile and allowed for theoperating system to implement program isolation, data/code isolation, protectedmemory, and other sophisticated services.
Asan example, the Intel 80x86 processor has a code segment pointer, a datasegment pointer, a stack segment pointer, and an extra segment pointer. When aprogram is loaded into memory, an operating system running on the Intel 80x86sets the segment pointers with the beginning of the pages assigned for eachpurpose for that particular program. If a program is swapped out, when it getsswapped back in, the operating system sets the segment pointers to the newmemory locations for each segment. The program continues to run, without beingaware that it has been moved in memory.
Indirection, pointers, and handles
Amethod for making data relocatable is to use indirection. Instead ofhard coding an absolute memory address for a variable or data structure, theprogram uses a pointer that gives the memory address of the variable ordata structure. Many processors have address pointer registers and a variety ofindirect addressing modes available for software.
Inthe most simple use of address pointers, software generates the effectiveaddress for the pointer just before it is used. Pointers can also be stored,but then the data can’t be moved (unless there is additional hardware support,such as virtual memory or base/segment pointers).
Closelyrelated to pointers are handles. Handles are two levels of indirection,or a pointer to a pointer. Instead of the program keeping track of an addresspointer to a block of memory that can’t be moved, the program keeps track of apointer to a pointer. Now, the operating system or the application program canmove the underlying block of data. As long as the program uses the handleinstead of the pointer, the operating system can freely move the data block andupdate the pointer, and everything will continue to resolve correctly.
Becauseit is faster to use pointers than handles, it is common for software to converta handle into a pointer and use the pointer for data accesses. If this is done,there must be some mechanism to make sure that the data block doesn’t movewhile the program is using the pointer. As an example, the Macintosh uses a system where data blocks can only be moved atspecific known times, and an application program can rely on pointers derivedfrom handles remaining valid between those known, specified times.
Stackframes
Stackframes are a methodfor generating temporary variables, especially for subroutines, functions, andloops. An are of memory is temporarily allocated on the system or processstack. In a simple version, the variables in the stack frame are accessed byusing the stack pointer and an offset to point to the actual location inmemory. This simple approach has the problem that there are many hardwareinstructions that change the stack pointer. The more sophisticated and stableapproach is to have a second pointer called a frame pointer. The framepointer can be set up in software using any address register. Many modernprocessors also have specific hardware instructions that allocate the stackframe and set up the frame pointer at the same time. Some processors have aspecific hardware frame pointer register.
Virtualmemory
Virtualmemory is atechnique in which each process generates addresses as if it had sole access tothe entire logical address space of the processor, but in reality memorymanagement hardware remaps the logical addresses into actual physicaladdresses in physical address space. The DEC VAX-11 gets it name fromthis technique, VAX standing for Virtual Address eXtension.
Virtualmemory can go beyond just remapping logical addresses into physical addresses.Many virtual memory systems also include software for page or segment swapping,shuffling portions of a program to and from a hard disk, to give the softwarethe impression of having much more RAM than is actually installed on thecomputer.