Difference between relative and logical address

Question

I'm reading about memory management from a book called Operating Systems. I've studied about this subject before and it was all clear because there were only two types of addresses introduced: Physical & Logical (Physical & Virtual). However, this book seems to introduce three types where it sometimes views two of them as the same, and sometimes as different.

Here's a quote (translated myself, so might not be the best):

At the time of writing a program it is not know at which point in the memory the program will be, which is why symbolic addresses are used (variable names). The process of translating symbolic addresses into physical addresses is called address binding and it can be done at different points in time. If, during the compilation, it is known in which part of the memory the program will be then address binding can be done at that point. Otherwise (the most common case) the compiler generates relative addresses (relative to the start of the part of the memory that the process gets). When executing a program the loader maps relative addresses into physical addresses.

This all seems to be pretty clear. Relative maps to the physical. Here's what comes after:

During process execution, the interaction with memory is done through sequences of reading and writing into memory locations. The CPU either reads instructions or data from the memory or writes data into the memory. Within both of these tasks, the CPU does not use physical addresses but rather logical ones which the CPU generates itself. The set of all logical addresses is called the Virtual Address Space.

This is already confusing as it is. What's the difference between a logical and a relative address? Wherever else I look this up they're never separated. Here comes an even more confusing sentence:

In case the address binding is done at the time of compilation and loading then the virtual address space matches the physical address space.

Earlier on it is stated that address binding is the process of converting symbolic addresses into physical addresses. But then only later on is the concept of relative addresses introduced. And loading is said to be the process of converting relative into physical. So now I'm completely lost here.

Assuming that we have no knowledge of which part of the memory the process is going to take: how does the timeline go? The program is compiled, the variable names (symbolic addresses) are translated into ... relative ones I guess? Then the CPU needs to do some read/write and it uses ... logical ones?

And furthermore, the terms relative and logical seem to be used randomly in the following sections of the book. As if they're the same, but still defined as different.

Could anyone clarify this for me? The perfect answer would be maybe an artificial example of a program timeline. At which point is which address introduced, what is the difference between a logical and a relative address?

Thanks in advance.

Answer 1

A relative address means a distance between two locations or addresses (which can be logical, linear/virtual or physical, which isn't important at this point).

For example, the x86 call and jump instructions have a form that specifies the distance (counted from the byte after the end of the call/jump instruction) to call/jump. That distance is simply added to the instruction pointer register ([R|E]IP) and that's the location where the next instruction will come from (again, I'm ignoring logical, ..., physical for now).

If your program contains a subroutine and calls it using such an instruction, it doesn't matter where the program is located in memory since the distance between two locations of the whole remains the same (things will become more complex if the whole program consists of several moving parts, including one or more libraries, but let's not go there).

Now, let's say your program has a global variable and needs to read it. If there is a memory reading instruction similar to the call instruction described above, you can again use the distance from the instruction pointer to the location of the variable. Prior to the 64-bit x86 CPUs there was no such instruction/mechanism to access data, only calls and jumps could be IP-relative.

In absence of such an IP-relative data addressing mechanism, you need to know the actual address of the variable, which you won't know until the program is loaded into memory for execution. What's done in this case is that the instruction that reads the variable initially receives the address of the variable relative to IP (that of the instruction that reads the variable) or simply the program's start. And that's how the program is stored on disk, with a relative address inside the instruction. Once loaded, but before the program starts execution, the address of the variable in the instruction that reads it is adjusted such that it becomes the actual address and not relative to something (IP or program's start). The further away the program's start is from address 0, the larger adjustment needs to be added to that relative address.

Get the idea?

And now something almost entirely different and unrelated...

In the context of x86 CPUs, there are these kinds of addresses:

• Logical
• Linear/virtual
• Physical

If we go back all the way to the 8086/8088... Actually, if we go even further back to the 8080/8085, all memory addresses are 16-bit, they don't undergo any translation by the CPU and are presented as-is to the memory, hence they're physical (we're not talking about IP/PC-relative call/jump instructions here).

16 bits allow for 64KB of memory. The 8086/8088 extended those 16 bit addresses with another 16 bits to address more than 64KB of memory, but it didn't just widen all registers and addresses from 16 to 32 bits. Instead it introduced special segment registers, which would be used in pairs with those old 16-bit addresses of the 8080/8085. So, a pair of registers such as DS (a segment register) and BX (a regular general-purpose register) could address memory at address DS * 16 + BX. The pair DS:BX is the logical address, the value DS * 16 + BX is the physical address. With this scheme we can access approximately 1MB of memory (just plug in 65535 for both registers).

The 80286 slightly changed the above by introducing the so-called protected mode, in which the physical address was calculated as segment_table[DS] + BX (this allowed to go from 1MB to 16MB), but the idea was still the same.

Next came along the 80386 and widened registers to 32 bits and introduced yet another layer of indirection. The physical address was now, simplifying a bit, page_tables[segment_table[DS] + EBX].

The pair DS:EBX constitutes the logical address, this is what the program manipulates with (e.g. in instruction MOV EAX, DS:[EBX]), this is what it can observe.

segment_table[DS] + EBX constitutes the linear/virtual address (which the program may not always know since it can't see into segment_table[], a table managed by the OS). If page translation isn't enabled, this linear/virtual address is also equal to the final, physical address.

With page translation enabled, the physical address is page_tables[segment_table[DS] + EBX].

What's more to know:

• logical addresses can be more complex, e.g. DS:[EAX + EBX * 2 + 3]
• OSes commonly set up segment_table[] such that segment_table[any segment register]=0, effectively removing the segmentation mechanism out of the picture and ending up with e.g. physical address = page_tables[EAX + EBX * 2 + 3]. While it's not entirely correct to say that in such a set up logical and linear/virtual addresses are the same (EAX + EBX * 2 + 3), it definitely simplifies thinking.

Now, what do these segment and page tables have to do with relative addresses and relocation discussed at the beginning? These tables just let you place your program anywhere in physical memory, often in a very transparent way to the program itself. It doesn't need to know where it's physically at or whether page translation is enabled.

However, there are certain benefits to using page translation, but that's outside of the scope here.