17 Memory Management

Mary Anitha Rajam

 

20.1  Introduction

 

Any program that must be executed must be brought into the main memory and placed within a process for it to run. If there is enough space in main memory, more than one process can be placed in the main memory. To increase the system performance, several processes must be kept in memory. The processes must share the memory. There are different ways to manage the main memory. In this module we learn what is meant by memory management, why memory management is needed and different issues related to memory management.

 

20.2  Background 

 

The main memory consists of a large array of words or bytes. The CPU fetches the instructions from the memory based on the value of the program counter and executes them. In an instruction-execution cycle, an instruction is first fetched from memory. The instruction is decoded. If needed, operands are also fetched. After execution of the instructions, the results may be stored back in the memory.

 

Since the main memory is not large enough to accommodate all the active processes at the same time, the processes that are not in the main memory are kept in the backing store or the disk. This collection of processes on the disk that are waiting to be brought into memory to run the program are placed in an input queue. One of these processes is selected and loaded into the main memory and is executed. After termination of the process, the main memory space allocated to the process is freed.

 

User programs go through several steps before being run. The addresses in source program are represented in symbolic form (say, variable count in the program). The compiler will bind these addresses to relocatable addresses (15 bytes from the beginning of this module). Theses addresses will range from 0 to a maximum for that particular process. The loader will turn these addresses into absolute addresses (74001). For example, the relocatable address 0 can be loaded into address 74001 in the memory.

 

20.3  Binding of Instructions and Data to Memory 

 

Address binding of instructions and data to memory addresses can happen at three different stages, compile time, load time and execution time.

 

•  Compile time: If memory location in which the process will be placed in main memory is known a priori, absolute code can be generated. But the code must be recompiled if starting location of the process changes.

 

•  Load time: If the memory location of the process is not known at compile time, binding is delayed until load time. Here, relocatable code is generated. The actual memory locations are known only when the process is loaded into memory.

 

•  Execution time: If the process can be moved during its execution from one memory segment to another, binding is delayed until run time. This needs hardware support for address maps (e.g., base and limit registers). This is used by most general-purpose operating systems.

 

20.3  Logical vs. Physical Address Space 

 

When a program is compiled, relocatable addresses are generated. These addresses range from 0 to a maximum. These addresses comprise the logical address space. When the program is placed in the physical memory, iit need not be placed in the same address as that of the logical address. The addresses where the program is placed in the physical memory comprise the physical address space. Thus, the logical address is generated by the CPU and is also referred to as virtual address. The physical address is the address seen by the memory unit. The logical and physical addresses are the same in compile-time and load-time address-binding schemes; logical (virtual) and physical addresses differ in execution-time address-binding

 

20.4  Memory-Management Unit (MMU) 

 

Since the logical address and the corresponding physical address may be different, there is a need for a memory management unit that maps the logical address to physical address. The user program deals with logical addresses; it never sees the real physical addresses. Only the memory-mapping hardware converts the logical addresses to physical addresses. There are many memory management schemes available like paging, segmentation and paged segmentation.

 

We now look at a simple MMU scheme and understand how the mapping is done from the logical address to the physical address (Figure 20.1). The starting address from where the process is loaded in the main memory is kept in a relocation register. The value in the relocation register is added to every address generated by a user process at the time it is sent to memory. The resultant value is the physical address. Say, a process is loaded in the main memory from address 14000. This value (14000) is stored in the relocation register. If the logical address is 346, then the physical address will be 14000+346 = 14346.

Figure 20.1 Dynamic relocation using a relocation register (Source: [1])

 

Thus, logical addresses range from 0 to max and physical addresses range from R+0 to R+max, where R is the starting address of the process in physical memory. The user thinks that the process runs in locations 0 to max and supplies logical addresses. Logical addresses are converted to physical addresses before they are used.

 

20.5  Dynamic Loading 

 

In our discussion so far, the entire program and data of a process must be in physical memory for the process to execute. The size of a process is limited to the size of physical memory. To obtain better memory-space utilization, we can use dynamic loading. With dynamic loading, a routine is not loaded until it is called. All routines are kept on disk in a relocatable load format. Only the main program is loaded. When a routine is called, the calling routine checks if the called routine is already loaded. If not, the relocatable linking loader is called to load the routine. The loader updates the program’s address table. Control is passed to the newly loaded routine. This results in better memory-space utilization; unused routine is never loaded. This kind of loading is useful when large amounts of code are needed to handle infrequently occurring cases, say, error routines. Some types of errors may occur very rarely, but still the code for handling these types of errors should be a part of the program. If a particular type of error does not occur, the code for handling that error will not be used, and hence, that part of the program need not be loaded into memory at all. No special support from the operating system is required and can be implemented through program design. Users should design their programs in a modular way for this to work. The operating system may provide library routines to implement dynamic loading.

 

20.6  Dynamic Linking 

 

In dynamic linking, linking of library routines is postponed until execution time. For each library-routine reference, a stub is included in the executable image. The stub is a small piece of code which is used to locate the appropriate memory-resident library routine. When the stub is executed, it replaces itself with the address of the routine, and executes the routine. Dynamic linking is particularly useful for libraries

 

20.7   Swapping 

 

Any process that is currently being executed needs to be kept in main memory. A process may move between running state and waiting state, many times during its lifetime. When the process is in waiting state, the process is not using the CPU and hence need not be kept in main memory. When one process is in waiting state, another process can use the CPU and the process that is currently using the CPU is kept in main memory. When there are many active processes, all processes cannot be accommodated in the main memory, since the size of main memory is small. Therefore, processes that are not executing currently can be swapped temporarily out of main memory to a backing store, and then brought back into memory for continued execution. The backing store is a fast disk large enough to accommodate copies of all memory images for all users. This moving out and moving in of processes is called swapping (Fig. 20.2).

 

Suppose round-robin scheduling is the CPU scheduling algorithm used. A time slice is allotted to each process. Suppose there are 10 processes that are using the CPU in a round-robin manner. The process whose time slice is completed is swapped out, if there is no enough space  in  the main  memory, and the next process is brought in.  If  priority-based scheduling is used, a low-priority process is swapped out to bring in a high-priority process. This moving out is called as roll out and moving in is called as roll in.

 

In swapping, the major part of the swap time is transfer time, that is, the time required to transfer the process to from the main memory to the disk. The total transfer time is directly proportional to the amount of memory swapped. Modified versions of swapping are found on many systems, i.e., UNIX, Linux, and Windows.

Fig. 20.2 Schematic View of Swapping (Source: [1])

 

20.8   Contiguous Memory Allocation

 

The main memory must accommodate both the operating system and the various user processes. We therefore need to allocate different parts of the main memory in the most efficient way possible. This section will explain one common method called contiguous memory allocation.

 

The main memory is usually divided into two partitions:

–  Resident operating system, usually held in low memory with interrupt vector

–  User processes then held in high memory

 

In contiguous memory allocation, each process is contained in a single contiguous section of memory.

 

20.8.1  Single-partition allocation 

 

In this scheme, the main memory is considered as a single big partition. Processes are brought into the main memory and can be placed at any free space in the main memory. The starting address where the process is placed in remembered, say, in a relocation-register. The relocation-register scheme is used to protect user processes from each other, and from changing operating-system code and data. The relocation register contains the value of the smallest physical address of the process. Another register called the limit register is maintained which contains the range of logical addresses (highest logical address) – each logical address must be less than the limit register.

 

Any address that is generated by the CPU is checked with the contents of the limit register. The address generated must be less than the contents of the limit register. If it is less, then the address generated is added with the contents of the relocation register to get the physical address (Fig. 20.3). If the logical address generated by the CPU is not less than the value in the limit register, then a trap is given to the operating system, indicating that the address generated is an illegal address.

Fig. 20.3 Hardware Support for Relocation and Limit Registers

 

20.8.2  Multiple-partition allocation

 

In multiple-partition allocation, the main memory can be divided into several fixed sized partitions. When a partition is free, a process is selected from the input queue and is loaded to the free partition.

 

It is also possible to have variable-sized partitions. The memory is looked at as one large hole – block of available memory. When a process arrives, it is allocated memory from a hole large enough to accommodate it. When a process terminates, the space is freed and is added to the set of holes. As memory space for processes are allocated and freed, in due course of time, there will be a lot of holes of various sizes scattered throughout the memory. The operating system maintains information about: a) allocated partitions b) free partitions (hole).

 

Consider the example shown in Figure 20.4. Initially, process 5, process 8 and process 2 are present in the main memory. Process 8 terminates and a hole is created. Process 9 is brought into the memory. Then process 10 is brought into the memory.

Fig. 20.4 Example of contiguous memory allocation

 

20.8.3  Dynamic Storage-Allocation roblem

 

When there is a list of free holes, how to satisfy a request of size n from the list of free holes.

There are three ways in which the request can be satisfied, first-fit, best-fit and worst-fit.

  • First-fit: Allocate the first hole that is big enough– Search to find the hole can start from the beginning or from where the previous search ended
  • Best-fit: Allocate the smallest hole that is big enough. In this case, it is necessary to search the entire list, unless ordered by size. This produces the smallest leftover hole that is large enough to accommodate the incoming process.
  • Worst-fit: Allocate the largest hole. In this case also, it is necessary to search the entire list. The search produces the largest leftover hole.

 

The problem with these allocation algorithms is that these suffer from external fragmentation. Since processes are allocated and de-allocated space, in due course of time it is possible that there will be free memory space that is not contiguous. The total free memory space exists to satisfy a request,  but it  is not contiguous.  This is called external fragmentation. External fragmentation can be reduced by compaction. In compaction, memory contents are shuffled to place all free memory together in one large block. Compaction is not possible if relocation is static and is done at assembly or load time. Compaction is possible only if relocation is dynamic, and is done at execution time.

 

5.3 Summary

 

A process should be kept in main memory during execution. We learnt what the difference is between a logical address and a physical address. Dynamic loading and linking are possible.

 

We learnt what is meant by swapping of processes, what contiguous memory allocation is and the issues related to contiguous memory allocation.

 

References

  1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.