Spread Knowledge

CS604 - Operating Systems - Lecture Handout 30

User Rating:  / 0

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems


  • Basic concepts
  • Logical to physical address translation
  • Various techniques for memory management

Basic Concepts

Selection of memory-management method for a specific system depends on many factors especially on the hardware design of the system. Recent designs have integrated the hardware and operating system.
Memory consists of a large array of words or bytes, each with its own address. The CPU fetches instructions from memory according to the value of its program counter and other memory management registers such as segment registers in Intel CPUs. These instructions may cause additional loading from and storing to specific memory addresses.
A typical instruction-execution cycle, e.g., first fetches an instruction from memory, which is then decoded and executed. Operands may have to be fetched from memory.
After the instruction has been executed, the results are stored back in memory. The memory unit sees only a stream of memory addresses; it does not know how they are generated or what they are for (instructions or data).

Memory Hierarchy

The memory hierarchy includes:

  • Very small, extremely fast, extremely expensive, and volatile CPU registers
  • Small, very fast, expensive, and volatile cache
  • Hundreds of megabytes of medium-speed, medium-price, volatile main memory
  • Hundreds of gigabytes of slow, cheap, and non-volatile secondary storage
  • Hundreds and thousands of terabytes of very slow, almost free, and non-volatile Internet storage (Web pages, Ftp repositories, etc.)

Memory Management

The purpose of memory management is to ensure fair, secure, orderly, and efficient use of memory. The task of memory management includes keeping track of used and free memory space, as well as when, where, and how much memory to allocate and deallocate. It is also responsible for swapping processes in and out of main memory

Source to Execution

Translation of a source program in a high-level or assembly language involves compilation and linking of the program. This process generates the machine language executable code (also known as a binary image) for the give source program. To execute the binary code, it is loaded into the main memory and the CPU state is set appropriately. The whole process is shown in the following diagram.

Source to Execution

Address Binding

Usually a program resides on a disk as a binary executable or script file. The program must be brought into the memory it to be executed. The collection of processes that is waiting on the disk to be brought into the memory for execution forms the input queue.
The normal procedure is to select one of the processes in the input queue and to load that process into the memory. As the process is executed, it accesses instructions and data from memory. Eventually the process terminates and its memory space is become available for reuse.
In most cases, a user program will go through several steps–some of which may be optional–before being executed. These steps are shown in the following diagram.
Addresses may be bound in different ways during these steps. Addresses in the source program are generally symbolic (such as an integer variable count). Address can be bound to instructions and data at different times, as discussed below briefly.

  • Compile time: if you know at compile where the process will reside in memory, the absolute addresses can be assigned to instructions and data by the compiler.
  • Load time: if it is not known at compile time where the process will reside in memory, then the compiler must generate re-locatable code. In this case the final binding is delayed until load time.
  • Execution time: if the process can be moved during its execution from one memory segment to another, then binding must be delayed until run time. Special hardware must be available for this to work.

In case of compile and load time binding, a program may not be moved around in memory at run time.

Address Binding

Logical- Versus Physical-Address Space

An address generated by the CPU is commonly referred to as a logical address, where as an address seen by the memory unit–that is, the one loaded into the memory-addressregister of the memory–is commonly referred to as the physical address. In essence, logical data refers to an instruction or data in the process address space where as the physical address refers to a main memory location where instruction or data resides.
The compile time and load time binding methods generate identical logical and physical addresses, where as the execution time binding method results in different physical and logical addresses. In this case we refer to the logical address as the virtual address. The set of all logical addresses generated by a program form the logical address space of a process; the set of all physical addresses corresponding to these logical addresses is a physical address space of the process. The total size of physical address space in a system is equal to the size of its main memory.
The run-time mapping from virtual to physical addresses is done by a piece of hardware in the CPU, called the memory management unit (MMU).

Translation Examples

In the following two diagrams, we show two simple ways of translating logical addresses into physical address. In both case, there is a “base” register which is loaded with the address of the first byte in the program (instruction or data—in case of the second example, separate registers are used to point to the beginning of code, data, and stack
portions of a program). In the first case, the base register is called the relocation register.
The logical address is translated into the corresponding physical address by adding the logical address to the value of the relocation register, as shown below.

Translation Examples

In i8086, the logical address of the next instruction is specified by the value of instruction pointer (IP). The physical address for the instruction is computed by shifting the code segment register (CS) left by four bits and adding IP to it, as shown below.

code segment register

In the following example, we show the logical address for a program instruction and computation of physical address for the given logical address.

  • Logical address (16-bit)
    IP = 0B10h
    CS = D000h
  • Physical address (20-bit)
    CS * 24 + IP = D0B10h

Various techniques for memory management

Here are some techniques of memory management, which are used in addition to the main techniques of memory management such as paging and segmentation discussed later in the course.

Dynamic Loading

The size of a process is limited to the size of physical memory. To obtain better memoryspace utilization, we can use dynamic loading. With dynamic loading, a routine is not loaded until it is called. All routines are kept on a disk in a re-locatable format. The main program is loaded into memory and is executed. When a routine needs to call another
routine, the calling routine first checks to see whether the other routine has been loaded or not. If not, the re-locatable linking loader is called to load the desired routine into the memory and to update the program’s address tables to reflect this change. The control is then passed to the newly loaded routine.
The advantage of dynamic loading is that an unused routine is never loaded. This means that potentially less time is needed to load a program and less memory space is required. However the run time activity involved in dynamic loading is a disadvantage.
Dynamic programming does not require special support from the operating system.

Dynamic Linking and Shared Libraries

Some operating systems support only static linking in which system language libraries are treated like any other object module and are combined by the loader into the binary proper image. The concept of dynamic linking is similar to that of dynamic loading.
Rather than the loading being postponed until execution time, linking is postponed until run-time. This feature is usually used with system libraries. Without this facility, all programs on a system need to have a copy of their language library included in the executable image. This requirement wastes both disk space and main memory. With
dynamic linking, a stub is included in the image for each library-routine reference. This stub is a small piece of code that indicates how to locate the appropriate memory-resident library routine or how to load the library if the routine is not already present. During execution of a process, stub is replaced by the address of the relevant library code and the code is executed .If library code is not in memory, it is loaded at this time This feature can be extended to update libraries. A library may be replaced by a new version and all programs that reference the library will automatically use the new version without any need to be re-linked. More than one version of a library may be loaded into the memory and each program uses its version information to decide which copy of the library to use. Only major changes increment the version number. Only programs that are compiled with the new library version are affected by the incompatible changes incorporated in it. Programs linked before the new library was installed will continue using the older library. This system is also known as shared libraries.
Dynamic linking requires potentially less time to load a program. Less disk space is needed to store binaries. However it is a time-consuming run-time activity, resulting in slower program execution. Dynamic linking requires help from the operating system.
The gcc compiler invokes dynamic linking by default. The -static option allows static linking.