OPERATING SYSTEMS PRINCIPLES

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.

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.)

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-address register 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,
whereas 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).

Memory allocation Algorithms

1. First-fit: search the list of available memory and allocate the first block that is big enough.
2. Best-fit: search the entire list of available memory and allocate the smallest block that is big
enough.
3. Worst-fit: search the entire list of available memory and allocate the largest block. (The
justification for this scheme is that the leftover block produced would be larger and potentially
more useful than that produced by the best-fit approach.)

Example: Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each
of the First-fit, Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in
order)? Which algorithm makes the most efficient use of memory?

1. First-fit:
1. 212K is put in 500K partition
2. 417K is put in 600K partition
3. 112K is put in 288K partition (new partition 288K = 500K - 212K)
4. 426K must wait
2. Best-fit:
1. 212K is put in 300K partition
2. 417K is put in 500K partition
3. 112K is put in 200K partition
4. 426K is put in 600K partition
3. Worst-fit:
1. 212K is put in 600K partition
2. 417K is put in 500K partition
3. 112K is put in 388K partition
4. 426K must wait

MEMORY MANAGEMENT TECHNIQUES

a. Dynamic loading vs Dynamic linking

Dynamic loading is concerned with loading the subroutines of a program as and when required during
run-time, instead of loading all the subroutines at once before the program execution starts. This is
useful in efficient memory usage since many subroutines may not be called at all.

Dynamic linking is concerned with linking library routines at run-time instead of combining them with
the executable program code before the program execution starts i.e. static linking. To achieve this, a
small code call 'stub' is inserted in the program code wherever library routine is required. The stub
contains information about where to find the routine if it is not already in the main memory, and how to
load it into the main memory. If the library routine is already present in the main memory then the the
stub replaces itself with the address of the routine and executes it. So, like dynamic loading, dynamic
linking also helps in efficient memory usage.

Dynamic loading refers to mapping (or less often copying) an executable or library into a process's
memory after is has started. Dynamic linking refers to resolving symbols - associating their names with
addresses or offsets - after compile time.

b. External Vs Internal Fragmentation

External Fragmentation - The free space (whether disk, DRAM, NVRAM etc) is fragmented in way
that there is possibly sufficient free space to satisfy an allocation request, but the free space is not
arranged in a contiguous fashion. This usually happens when the free space is interspersed with the
allocated space.

Let's say F represents 1 KB of free space, and A represents some amount of allocated space. If a new
user request is 3 KB, our space container has sufficient free space, but is not contiguous. So, effectively
the free space is fragmented and is represented by multiple fragments in different locations as opposed
to one big chunk/hole of free space

Internal Fragmentation - The free space is again sort of fragmented, but is not at all usable. For
example, to satisfy an allocation request of 9 KB, we allocate 16 KB to the user. Although the need is of
9 KB, the extra 7 KB we allocated contributes to space wastage. It is literally free space, but is internal
to an allocated region. Hence, it is not usable for new requests.

Fragmentation in the context of Memory Management

A program needs to be loaded into memory before the CPU can start executing the instructions in the
program. This running instance of a program/binary is called as a process. It sits in main memory
(DRAM), and CPU runs it by fetching instructions and data from the main memory.

So, it is clear that the process needs to be allocated some space in DRAM, and this is done through some
allocation strategy/algorithm.

Contiguous Memory Allocation: In this scheme, the process occupies a contiguous space in DRAM --
starting at some physical address S, and occupying all the region upto some physical address E. Over a
period of time after considerable amount of process swapping (in/out of memory from/to disk) has been
done by the operating system for processes of various sizes, the space in DRAM can get fragmented
(externally).

When this happens, we see a situation similar to what I explained above. The OS Loader needs to load a
new program into memory into some free space region enough to satisfy the memory requirements of
the process. To support multi-programming, multiple processes are already sitting in DRAM within their
respective allocated regions. If the free space is fragmented, the loader may not find space large enough
for the new process.

A process currently in the memory has to be swapped out to disk to make space for the new process
(Note that this is not done by the loader).

Contiguous memory allocation strategy can lead to internal fragmentation as well. When we allocate
large chunk of space in DRAM to a process with lesser size requirements, the additional space given to
the process is wasted space. It is internal to the allocated region, the process that owns it probably
doesn't need it, and it can't be utilized to service future allocation requests.

Non-Contiguous Memory Allocation: Paging is a common scheme that does not demand contiguous
allocation of memory region to the entire process. In paging, DRAM is divided into blocks (aka frames)
of equal size (determined by the hardware, typically 4 KB). The process is allocated memory in the form
of multiple pages, where the granularity of allocation is fixed at frame size. Moreover, frames to a
process can be allocated anywhere in the main memory. It doesn't to follow the last allocated frame.
Wherever there is a free frame, it can be allocated to the process.
This solves the problem of external fragmentation. How ? Because every single allocation is equal to the
size of physical memory frame. There is no need for contiguous allocation of free frames to the process,
and so the operating system doesn't have to care whether a given number of free frames are contiguous
or not.

"If there is a free frame, just allocate to the process".

But, this can suffer from internal fragmentation. Assuming size requirements of a process is 97 KB.
Operating System allocated 25 free frames to the process. The last frame allocated has an internally
fragmented free space worth 3 KB.

c. Memory Segmentation

Segmentation is a memory management scheme that supports programmer’s view of memory. A logical-
address space is a collection of segments. A segment is a logical unit such as: main program, procedure,
function, method, object, global variables, stack, and symbol table. Each segment has a name and
length. The addresses specify both the segment name and the offset within the segment.

Memory segmentation is the division of a computer's primary memory into segments or sections. In a
computer system using segmentation, a reference to a memory location includes a value that identifies a
segment and an offset (memory location) within that segment. Segments or sections are also used in
object files of compiled programs when they are linked together into a program image and when the
image is loaded into memory.

Segments usually correspond to natural divisions of a program such as individual routines or data tables
so segmentation is generally more visible to the programmer than paging alone. Different segments may
be created for different program modules, or for different classes of memory usage such as code and
data segments. Certain segments may be shared between programs.

Segmentation without paging

Associated with each segment is information that indicates where the segment is located in memory—
the segment base. When a program references a memory location the offset is added to the segment base
to generate a physical memory address.
An implementation of virtual memory on a system using segmentation without paging requires that
entire segments be swapped back and forth between main memory and secondary storage. When a
segment is swapped in, the operating system has to allocate enough contiguous free memory to hold the
entire segment. Often memory fragmentation results in there being not enough contiguous memory even
though there may be enough in total.
Segmentation with paging
Instead of an actual memory location the segment information includes the address of a page table for
the segment. When a program references a memory location the offset is translated to a memory address
using the page table. A segment can be extended simply by allocating another memory page and adding
it to the segment's page table.
An implementation of virtual memory on a system using segmentation with paging usually only moves
individual pages back and forth between main memory and secondary storage, similar to a paged non-
segmented system. Pages of the segment can be located anywhere in main memory and need not be
contiguous. This usually results in a reduced amount of input/output between primary and secondary
storage and reduced memory fragmentation
Virtual Memory
Virtual Memory is the separation of user logical memory from physical memory.
This separation allows an extremely large virtual memory to be provided for programmers when only a
smaller physical memory is available. Virtual memory makes the task of programming easier because
the programmer need not worry about the amount of physical memory, or about what code can be placed
in overlays; she can concentrate instead on the problem to be programmed.
In addition to separating logical memory from physical memory, virtual memory also allows files and
memory to be shared by several different processes through page sharing.
The sharing of pages further allows performance improvements during process creation.
Virtual memory is commonly implemented as demand paging. It can also be implemented in a
segmentation system. One benefit of virtual memory is efficient process creation.
d. Paging

Paging is a memory management scheme by which a computer stores and retrieves data from secondary
storage for use in main memory. In this scheme, the operating system retrieves data from secondary
storage in same-size blocks called pages. Paging is an important part of virtual memory implementations
in modern operating systems, using secondary storage to let programs exceed the size of available
physical memory.

{Paging is a memory management scheme that permits the physical address space of a process to be
noncontiguous.

It avoids the considerable problem of fitting the various sized memory chunks onto the backing store,
from which most of the previous memory-management schemes suffered. When some code fragments or
data residing in main memory need to be swapped out, space must be found on the backing store. The
fragmentation problems discussed in connection with main memory are also prevalent with backing
store, except that access is much slower so compaction is impossible.

Physical memory is broken down into fixed-sized blocks, called frames, and logical memory is divided
into blocks of the same size, called pages. The size of a page is a power of 2, the typical page table size
lying between 1K and16K. It is important to keep track of all free frames. In order to run a program of
size n pages, we find n free frames and load program pages into these frames. In order to keep track of a
program’s pages in the main memory a page table is used.}

Page Faults

When a program tries to reference a page not currently present in RAM, the processor treats this invalid
memory reference as a page fault and transfers control from the program to the operating system. The
operating system must:

1. Determine the location of the data on disk.

2. Obtain an empty page frame in RAM to use as a container for the data.
3. Load the requested data into the available page frame.
4. Update the page table to refer to the new page frame.
5. Return control to the program, transparently retrying the instruction that caused the page fault.
When all page frames are in use, the operating system must select a page frame to reuse for the page the
program now needs. If the evicted page frame was dynamically allocated by a program to hold data, or if
a program modified it since it was read into RAM (in other words, if it has become "dirty"), it must be
written out to disk before being freed. If a program later references the evicted page, another page fault
occurs and the page must be read back into RAM.

Page Replacement Algorithms

a. FIFO Page Replacement

The simplest page-replacement algorithm is a FIFO algorithm. A FIFO replacement algorithm associates
with each page the time when that page was brought into memory. When a page must be replaced, the
oldest page is chosen. Notice that it is not strictly necessary to record the time when a page is brought in.
We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue.
When a page is brought into memory we insert t at the tail of the queue.

b. Optimal Algorithm

An optimal page-replacement algorithm has the lowest page fault rate of all algorithms, and will never
suffer from the Belay’s algorithm. This algorithm is simply to replace the page that will not be used for
the longest period of time. Use of this algorithm guarantees the lowest possible page-fault rate for a
fixed number of frames.

c. LRU Page Replacement

If we use the recent past as an approximation of the near future, then we will replace the page that has
not been used for the longest period of time. This approach is the least recently used algorithms.

An LRU page replacement may require substantial hardware assistance. The problem is to determine an
order for the frames defined by the time of last use. (Read more on this)