Opetating System Memory management

Information about memory management in an operating systems.

1. OS - Memory Management
Memory management is the functionality of an operating system, which handles or
manages primary memory. Memory management keeps track of each and every
memory location either it is allocated to some process or it is free. It checks how
much memory is to be allocated to processes. It decides which process will get
memory at what time. It tracks whenever some memory gets freed or unallocated
and correspondingly it updates the status.
Memory management provides protection by using two registers, a base register
and a limit register. The base register holds the smallest legal physical memory
address and the limit register specifies the size of the range. For example, if the
base register holds 300000 and the limit register is 1209000, then the program can
legally access all addresses from 300000 through 411999.

Instructions and data to memory addresses can be done in following ways
 Compile time -- When it is known at compile time where the process will
reside, compile time binding is used to generate the absolute code.
 Load time -- When it is not known at compile time where the process will
reside in memory, then the compiler generates re-locatable code.

2.  Execution time -- If the process can be moved during its execution from
one memory segment to another, then binding must be delayed to be done
at run time
Dynamic Loading
In dynamic loading, a routine of a program is not loaded until it is called by the
program. All routines are kept on disk in a re-locatable load format. The main
program is loaded into memory and is executed. Other routines methods or
modules are loaded on request. Dynamic loading makes better memory space
utilization and unused routines are never loaded.
Dynamic Linking
Linking is the process of collecting and combining various modules of code and
data into a executable file that can be loaded into memory and executed.
Operating system can link system level libraries to a program. When it combines
the libraries at load time, the linking is called static linking and when this linking is
done at the time of execution, it is called as dynamic linking.
In static linking, libraries linked at compile time, so program code size becomes
bigger whereas in dynamic linking libraries linked at execution time so program
code size remains smaller.
Logical versus Physical Address Space
An address generated by the CPU is a logical address whereas address actually
available on memory unit is a physical address. Logical address is also known a
Virtual address.
Virtual and physical addresses are the same in compile-time and load-time
address-binding schemes. Virtual and physical addresses differ in execution-time
address-binding scheme.
The set of all logical addresses generated by a program is referred to as a logical
address space. The set of all physical addresses corresponding to these logical
addresses is referred to as a physical address space.
The run-time mapping from virtual to physical address is done by the memory
management unit (MMU) which is a hardware device. MMU uses following
mechanism to convert virtual address to physical address.
 The value in the base register is added to every address generated by a
user process which is treated as offset at the time it is sent to memory. For
example, if the base register value is 10000, then an attempt by the user to
use address location 100 will be dynamically reallocated to location 10100.

3.  The user program deals with virtual addresses; it never sees the real
physical addresses.
Swapping
Swapping is a mechanism in which a process can be swapped temporarily out of
main memory to a backing store, and then brought back into memory for continued
execution.
Backing store is a usually a hard disk drive or any other secondary storage which
fast in access and large enough to accommodate copies of all memory images for
all users. It must be capable of providing direct access to these memory images.
Major time-consuming part of swapping is transfer time. Total transfer time is
directly proportional to the amount of memory swapped. Let us assume that the
user process is of size 100KB and the backing store is a standard hard disk with
transfer rate of 1 MB per second. The actual transfer of the 100K process to or
from memory will take
100KB / 1000KB per second
= 1/10 second
= 100 milliseconds

4. Memory Allocation
Main memory usually has two partitions
 Low Memory -- Operating system resides in this memory.
 High Memory -- User processes then held in high memory.
Operating system uses the following memory allocation mechanism.
S.N.
Memory
Allocation
Description
1
Single-partition
allocation
In this type of allocation, relocation-register scheme is used to
protect user processes from each other, and from changing
operating-system code and data. Relocation register contains
value of smallest physical address whereas limit register contains
range of logical addresses. Each logical address must be less
than the limit register.
2
Multiple-
partition
allocation
In this type of allocation, main memory is divided into a number of
fixed-sized partitions where each partition should contain only one
process. When a partition is free, a process is selected from the
input queue and is loaded into the free partition. When the
process terminates, the partition becomes available for another
process.

Fragmentation
As processes are loaded and removed from memory, the free memory space is
broken into little pieces. It happens after sometimes that processes cannot be
allocated to memory blocks considering their small size and memory blocks
remains unused. This problem is known as Fragmentation.
Fragmentation is of two types
S.N. Fragmentation Description
1
External
fragmentation
Total memory space is enough to satisfy a request or to reside a
process in it, but it is not contiguous so it can not be used.
2
Internal
fragmentation
Memory block assigned to process is bigger. Some portion of
memory is left unused as it can not be used by another process.

5. External fragmentation can be reduced by compaction or shuffle memory contents
to place all free memory together in one large block. To make compaction feasible,
relocation should be dynamic.
Paging
External fragmentation is avoided by using paging technique. Paging is a
technique in which physical memory is broken into blocks of the same size called
pages (size is power of 2, between 512 bytes and 8192 bytes). When a process is
to be executed, it's corresponding pages are loaded into any available memory
frames.
Logical address space of a process can be non-contiguous and a process is
allocated physical memory whenever the free memory frame is available.
Operating system keeps track of all free frames. Operating system needs n free
frames to run a program of size n pages.
Address generated by CPU is divided into
 Page number (p) -- page number is used as an index into a page table
which contains base address of each page in physical memory.
 Page offset (d) -- page offset is combined with base address to define the
physical memory address.

Following figure show the paging table architecture.

6. Segmentation
Segmentation is a technique to break memory into logical pieces where each piece
represents a group of related information. For example ,data segments or code
segment for each process, data segment for operating system and so on.
Segmentation can be implemented using or without using paging.
Unlike paging, segment are having varying sizes and thus eliminates internal
fragmentation. External fragmentation still exists but to lesser extent.

7. Address generated by CPU is divided into
 Segment number (s) -- segment number is used as an index into a
segment table which contains base address of each segment in physical
memory and a limit of segment.
 Segment offset (o) -- segment offset is first checked against limit and then
is combined with base address to define the physical memory address.

8. Memory management techniques

Single contiguous allocation
Single allocation is the simplest memory management technique. All the
computer's memory, usually with the exception of a small portion reserved for the
operating system, is available to the single application. MS-DOS is an example of a
system, which allocates memory in this way. An embedded system running a
single application might also use this technique.
A system using single contiguous allocation may still multitask by swapping the
contents of memory to switch among users. Early versions of the Music (Multi-User
System for Interactive Computing) operating system used this technique.
Partitioned allocation
Partitioned allocation divides primary memory into multiple memory partitions,
usually contiguous areas of memory. Each partition might contain all the
information for a specific job or task. Memory management consists of allocating a
partition to a job when it starts and unallocating it when the job ends.
Partitioned allocation usually requires some hardware support to prevent the jobs
from interfering with one another or with the operating system. The IBM
System/360 used a lock-and-key technique. Other systems used base and bounds
registers which contained the limits of the partition and flagged invalid accesses.
The UNIVAC 1108 Storage Limits Register had separate base/bound sets for
instructions and data. The system took advantage of memory interleaving to place
what were called the i bank and d bank in separate memory modules.
Partitions may be either static, that is defined at Initial Program Load (IPL) or boot
time or by the computer operator, or dynamic, that is automatically created for a
specific job. IBM System/360 Operating System Multiprogramming with a Fixed
Number of Tasks (MFT) is an example of static partitioning, and Multiprogramming
with a Variable Number of Tasks (MVT) is an example of dynamic. MVT and
successors use the term region to distinguish dynamic partitions from static ones in
other systems.
Partitions may be relocatable using hardware typed memory, like the Burroughs
Corporation B5500, or base and bounds registers like the PDP-10 or GE-635.
Relocatable partitions are able to be compacted to provide larger chunks of
contiguous physical memory. Compaction moves "in-use" areas of memory to
eliminate "holes" or unused areas of memory caused by process termination in
order to create larger contiguous free areas.

9. Some systems allow partitions to be swapped out to secondary storage to free
additional memory. Early versions of IBM's Time Sharing Option (TSO) swapped
users in and out of a single time-sharing partition.
Paged memory management
Paged allocation divides the computer's primary memory into fixed-size units
called page frames, and the program's address space into pages of the same size.
The hardware memory management unit maps pages to frames. The physical
memory can be allocated on a page basis while the address space appears
contiguous.
Usually, with paged memory management, each job runs in its own address space,
however, IBM OS/VS/2 SVS ran all jobs in a single 16MiB virtual address space.
Paged memory can be demand-paged when the system can move pages as
required between primary and secondary memory.
Segmented memory management
Segmented memory is the only memory management technique that does not
provide the user's program with a 'linear and contiguous address space."
Segments are areas of memory that usually correspond to a logical grouping of
information such as a code procedure or a data array. Segments require hardware
support in the form of a segment table which usually contains the physical address
of the segment in memory, its size, and other data such as access protection bits
and status (swapped in, swapped out, etc.)
Segmentation allows better access protection than other schemes because
memory references are relative to a specific segment and the hardware will not
permit the application to reference memory not defined for that segment.
It is possible to implement segmentation with or without paging. Without paging
support the segment is the physical unit swapped in and out of memory if required.
With paging support the pages are usually the unit of swapping and segmentation
only adds an additional level of security.
Addresses in a segmented system usually consist of the segment id and an offset
relative to the segment base address, defined to be offset zero.
The Intel IA-32 (x86) architecture allows a process to have up to 16,383 segments
of up to 4GiB each. IA-32 segments are subdivisions of the computer's linear
address space, the virtual address space provided by the paging hardware.
The Multics operating system is probably the best known system implementing
segmented memory. Multics segments are subdivisions of the computer's physical

10. memory of up to 256 pages, each page being 1K 36-bit words in size, resulting in a
maximum segment size of 1MiB (with 9-bit bytes, as used in Multics). A process
could have up to 4046 segments.
Dynamic memory allocation

Details
The task of fulfilling an allocation request consists of locating a block of unused
memory of sufficient size. Memory requests are satisfied by allocating portions
from a large pool of memory called the heap. At any given time, some parts of the
heap are in use, while some are "free" (unused) and thus available for future
allocations. Several issues complicate implementation, such as external
fragmentation, which arises when there are many small gaps between allocated
memory blocks, which invalidates their use for an allocation request. The
allocator's metadata can also inflate the size of (individually) small allocations. This
is managed often by chunking. The memory management system must track
outstanding allocations to ensure that they do not overlap and that no memory is
ever "lost" as a memory leak.
Efficiency
The specific dynamic memory allocation algorithm implemented can impact
performance significantly. A study conducted in 1994 by Digital Equipment
Corporation illustrates the overheads involved for a variety of allocators. The
lowest average instruction path length required to allocate a single memory slot
was 52 (as measured with an instruction level profiler on a variety of software).
Implementations
Since the precise location of the allocation is not known in advance, the memory is
accessed indirectly, usually through a pointer reference. The specific algorithm
used to organize the memory area and allocate and deallocate chunks is
interlinked with the kernel, and may use any of the following methods:
Fixed-size-blocks allocation
Fixed-size-blocks allocation, also called memory pool allocation, uses a free list of
fixed-size blocks of memory (often all of the same size). This works well for simple
embedded systems where no large objects need to be allocated, but suffers from
fragmentation, especially with long memory addresses. However, due to the
significantly reduced overhead this method can substantially improve performance
for objects that need frequent allocation / de-allocation and is often used in video
games.

11. Buddy blocks
In this system, memory is allocated into several pools of memory instead of just
one, where each pool represents blocks of memory of a certain power of two in
size. All blocks of a particular size are kept in a sorted linked list or tree and all new
blocks that are formed during allocation are added to their respective memory
pools for later use. If a smaller size is requested than is available, the smallest
available size is selected and halved. One of the resulting halves is selected, and
the process repeats until the request is complete. When a block is allocated, the
allocator will start with the smallest sufficiently large block to avoid needlessly
breaking blocks. When a block is freed, it is compared to its buddy. If they are both
free, they are combined and placed in the next-largest size buddy-block list.
Systems with virtual memory
Virtual memory is a method of decoupling the memory organization from the
physical hardware. The applications operate memory via virtual addresses. Each
time an attempt to access stored data is made, virtual memory data orders
translate the virtual address to a physical address. In this way addition of virtual
memory enables granular control over memory systems and methods of access.
Protection
In virtual memory systems the operating system limits how a process can access
the memory. This feature can be used to disallow a process to read or write to
memory that is not allocated to it, preventing malicious or malfunctioning code in
one program from interfering with the operation of another.
Sharing
Even though the memory allocated for specific processes is normally isolated,
processes sometimes need to be able to share information. Shared memory is one
of the fastest techniques for inter-process communication.
Physical organization
Memory is usually classed by access rate as with primary storage and secondary
storage. Memory management systems handle moving information between these
two levels of memory.