Agenda

• Background
• Memory Management Requirements
• Fixed/Static Partitioning
• Variable/Dynamic Partitioning
• Simple/Basic Paging
• Simple/Basic Segmentation
• Segmentation with Paging

10/20/2017 Pushpinder Singh Patheja 1

 Background (1)
1. Input Queue - Program must be brought (from disk)
into memory and placed within a process for it to run.
2. Main memory and registers are only storage CPU
can access directly.
3. Memory unit only sees a stream of addresses +
read requests, or address +
data and write requests.
4. Register access in one CPU clock (or less).
5. Main memory can take many cycles.
6. Cache sits between main memory and CPU registers.
7. Protection of memory required to ensure correct
operation.
2
 Background (2)
1. Memory management is the task carried out by
the OS and hardware to accommodate multiple
processes in main memory.
2. User programs go through several steps before
being able to run.
3. This multi-step processing of the program
invokes the appropriate utility and generates
the required module at each step.

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: If memory location known a priori,

absolute code can be generated; must recompile
code if starting location changes
• Load time: Must generate relocatable code if
memory location is not known at compile time
• Execution time: Binding delayed until run time if the
process can be moved during its execution from one
memory segment to another. Need hardware support
for address maps (e.g., base and limit registers).

4
Multi-step processing of user program (1)

5
Multi-step processing of user program (2)

6
A C Compilation Example

7
Static vs. Load-time Dynamic Linking

The linking of some external modules is done after the creation

of the load module (executable file).
18
 Program vs. Memory sizes
• What to do when program size is larger than the
amount of memory/partition (that exists or can be)
allocated to it?
• There are two basic solutions within real memory
management:
1. Overlays
2. Dynamic Linking (Libraries – DLLs)

19
1. Overlays
1. Keep in memory only the overlay (those data
and instructions) that are needed at any
given phase/time.
2. Overlays can be used only for programs that
fit this model, i.e., multi-pass programs like
compilers.
3. Overlays needs an overlay driver.
4. No special support needed from OS, but
program design of overlays structure is
complex.
20
Overlays for a Two-Pass Assembler
Consider a 2-pass Assembler:
During pass 1, it constructs a Symbol Table.
During pass 2, it generates Machine-Language Code.
Assume size of Components are:
Pass1 (Code Size) = 70K Overlay A Overlay B
Pass2 (File size) = 80K
Symbol Table = 20K
Common Routine = 30K
Overlay Driver = 10K

To load everything at once

require 200K of Memory.
But if only 150K is available
we can NOT run all the
processes.
Thus we define 2 Overlays:
Overlay A = Symbol table + Common Routine + Pass1 = 120K
Overlay B = Symbol table + Common Routine + Pass2 = 130K
Thus Executing everything in 150K.
21
 2. Dynamic Linking
1. Dynamic linking is useful when large amounts of
code are needed to handle infrequently occurring
cases.
2. Routine is not loaded unless/until it is called.
3. Better memory-space utilization; unused routine is
never loaded.
4. Useful when large amounts of code are needed to
handle infrequently occurring cases.
5. Not much support from OS is required –
implemented through program design.

22
Memory-Management Unit (MMU)
• Hardware device that maps logical/virtual address
to real/physical address.

• In MMU scheme, the value in the base (relocation)

register is added to every logical (virtual) address
generated by a user process at the time it is sent
to memory.

• The user program deals with logical/virtual

addresses; it never sees the real/physical
addresses.

33
CPU, MMU and Memory

34
Logical vs. Physical Address Space
• The concept of a logical address space of a program
that is bound to a separate physical address space is
central to proper memory management.
– Logical address – generated by the CPU; also
referred to later as Virtual address.
– Physical address – address seen by the memory
unit; also referred to later as Absolute address.
• Logical and physical addresses are the same at the
end in compile-time and load-time address-binding
schemes.
• Logical (virtual) and physical addresses differ in
execution-time address-binding scheme.
36
Logical vs. Physical Address Space
• Fence Register: Its Protection Hardware, dedicated for the
protection of the hardware.
• Normally its value is fixed in H/W.
• If value FR is fixed in H/W then Compilation can provide us
Absolute Address.
• To relocate the address, it is necessary to recompile the
code to get relocation code.
• FR is now Base/Relocation Register.
FFFF 0000
Free Space Monitor/OS Low Area
Base R
USER Free Space
FR
Monitor/OS USER
High Area
0000 FFFF 40
Relocation Register
• Relative address is the most frequent type
of logical address used in program
modules (i.e., executable files).
• Relocatable modules are loaded in main
memory with all memory references left in
relative form.
• Physical addresses are calculated “on the
fly” as the instructions are executed.
• For adequate performance, the translation
from relative to physical address must by
done by hardware.

42
Dynamic relocation using a relocation register

43
Hardware Support for Relocation and Limit Registers:
Legal User address ranges from 0 to Limit.

44
Swapping
• A process can be swapped temporarily out of memory
to a backing store, and then brought back into memory
for continued execution
• Backing store – fast disk large enough to accommodate
copies of all memory images for all users; must provide
direct access to these memory images
Roll out, roll in – swapping variant used for priority-
based scheduling algorithms; lower-priority process is
swapped out so higher-priority process can be loaded
and executed
Major part of swap time is transfer time; 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)
46
Schematic View of Swapping

47
Contiguous Allocation
• An executing process must be loaded entirely in
main memory (if overlays are not used).
• Main memory is usually split into two (Memory split)
or more (Memory division) partitions:
– Resident operating system, usually held in low memory
partition with interrupt vector.
– User processes then held in high memory partitions.
• Relocation registers used to protect user processes
from each other, and from changing OS code and
data:
– Base register contains value of smallest physical
address.
– Limit register contains range of logical addresses –
each logical address must be less than the limit register.
– MMU maps logical address dynamically.

48
 Real Memory Management Techniques
• Although the following simple/basic memory
management techniques are not used in modern
OSs, they lay the ground for a later proper
discussion of virtual memory:
– Fixed/Static Partitioning
– Variable/Dynamic Partitioning
– Simple/Basic Paging
– Simple/Basic Segmentation

49
Fixed Partitioning
• Partition main memory
into a set of non-
overlapping memory
regions called
partitions.
• Fixed partitions can be
of equal or unequal
sizes.
• Leftover space in
partition, after program
assignment, is called
internal fragmentation. 50
 Comments on Fixed Partitioning
• Main memory use is inefficient. Any program, no
matter how small, occupies an entire partition. This
can cause internal fragmentation.
• Unequal-size partitions lessens these problems but
they still remain ...
• Equal-size partitions was used in early IBM’s
OS/MFT (Multiprogramming with a Fixed number of
Tasks).

55
Variable Partitioning
1. Degree of multiprogramming limited by number of partitions.
2. Variable-partition sizes for efficiency (sized to a given process’
needs).
3. Hole – block of available memory; holes of various size are scattered
throughout memory.
4. When a process arrives, it is allocated memory from a hole large
enough to accommodate it.
5. Process exiting frees its partition, adjacent free partitions combined.
6. Operating system maintains information about:
a) allocated partitions b) free partitions (hole)

56
 CONTIGUOUS
ALLOCATION
HOW DO YOU ALLOCATE MEMORY TO NEW PROCESSES?

First fit - allocate the first hole that's big enough.

Best fit - allocate smallest hole that's big enough.
Worst fit - allocate largest hole.

(First fit is fastest, worst fit has lowest memory utilization.)

 Avoid small holes (external fragmentation). This occurs when there

are many small pieces of free memory.
 What should be the minimum size allocated, allocated in what chunk
size?
 Want to also avoid internal fragmentation. This is when memory is
handed out in some fixed way (power of 2 for instance) and
requesting program doesn't use it all.

61
MEMORY MANAGEMENT COMPACTION
Trying to move free memory to one large block.

Only possible if programs linked with dynamic relocation (base and limit.)

There are many ways to move programs in memory.

Swapping: if using static relocation, code/data must return to same place.

But if dynamic, can reenter at more advantageous memory.

OS OS OS
P1 P1
P1 P2 P3
P3 P2
P2
P3

63
COMPACTION

10/20/2017 Pushpinder Singh Patheja 64

COMPACTION

Moved
600K

10/20/2017 Pushpinder Singh Patheja 65

COMPACTION

Moved Moved 400K

600K

10/20/2017 Pushpinder Singh Patheja 66

COMPACTION

Moved
200K

Moved Moved
600K 400K

10/20/2017 Pushpinder Singh Patheja 67

 Internal/External Fragmentation
There are really two types of fragmentation:
1. Internal Fragmentation –
allocated memory may be slightly larger than
requested memory; this size difference is
memory internal to a partition, but not being
used.
2. External Fragmentation –
total memory space exists to satisfy a size n
request, but that memory is not contiguous.

68
Comments on Variable Partitioning
1. Partitions are of variable length and number.
2. Each process is allocated exactly as much
memory as it requires.
3. Eventually holes are formed in main memory.
This can cause external fragmentation.
4. Must use compaction to shift processes so they
are contiguous; all free memory is in one block.
5. Used in IBM’s OS/MVT (Multiprogramming with a
Variable number of Tasks).

70
Simple/Basic Paging (1)
• Idea: Physical address space of a process can be
noncontiguous; process is allocated physical
memory whenever the latter is available:
– Avoids external fragmentation.
– Avoids problem of varying sized memory chunks.
• Divide physical memory into fixed-sized
chunks/blocks called frames (size is power of 2,
usually between 512 bytes and 16 MB).
• Divide logical memory into blocks of same size
pages.

72
Simple/Basic Paging (2)
• The process pages can thus be assigned to any
free frames in main memory; a process does not
need to occupy a contiguous portion of physical
memory.
• Need to keep track of all free frames.
• To run a program of size n pages, need to find
n free frames and load program.
• Need to set up a page table to translate logical to
physical pages/addresses.
• Internal fragmentation possible only for page at
end of program.

73
Paging Example

4K

Size of the Frame = Size of the Page =

Size of the Block =
1K 8K

74
 PAGING
Address Translation Scheme
Address generated by the CPU is divided into:
– Page number (p) – used as an index into a page table
which contains base address of each page in physical
memory.

– Page offset (d) – combined with base address to

define the physical memory address that is sent to the
memory unit.

4096 bytes = 2^12 – it requires 12 bits to contain the Page offset

p d

76
MEMORY MANAGEMENT PAGING
Permits a program's memory to be physically noncontiguous so it can be
allocated from wherever available. This avoids fragmentation and compaction.

Frames = physical blocks 13 bits

Pages = logical blocks Physical
Address
Size of frames/pages is
defined by hardware
(power of 2 to ease
calculations)
3 9 4 9

HARDWARE
An address is determined by:

page number ( index into table ) + offset

---> mapping into --->
base address ( from table ) + offset.

77
 PAGING
IMPLEMENTATION OF THE PAGE TABLE
– A 32 bit machine can
address 4 gigabytes
which is 4 million pages TLB = Translation Lookaside Buffer
(at 1024 bytes/page).
WHO says how big a
page is, anyway?
– We can use dedicated
registers (OK only with
small tables.)
– We can use a register
pointing to table in
memory (slow access.)
– Can use Cache or
associative memory
– (TLB = Translation
Lookaside Buffer):
Simultaneous
search is fast and
uses only a few
registers.
79
MEMORY MANAGEMENT PAGING
SHARED PAGES

Data occupying one

physical page, but
pointed to by
multiple logical
pages.

Useful for common

code - must be write
protected. (NO
write-able data
mixed with code.)

Extremely useful for

read/write
communication
between processes.

81
INVERTED PAGE TABLE: PAGING
One entry for each real
page of memory.

Entry consists of the virtual

address of the page stored
in that real memory
location, with information
about the process that
owns that page.

Essential when you need to

do work on the page and
must find out what process
owns it.

Use hash table to limit the

search to one - or at most a
few - page table entries.

82
Simple/Basic Segmentation
• Paging division is arbitrary; no natural/logical
boundaries for protection/sharing.
• Segmentation supports user’s view of a program.
• A program is a collection of segments –
logical units – such as:
main program, subprogram,
class, procedure,
function, object, method,
local variables, global variables,
common block, stack,
symbol table, arrays etc..

86
User’s View of a Program

87
Dynamics of Simple Segmentation
• In contrast with paging, segmentation is
visible to the programmer:
– provided as a convenience to organize
logically programs (example: data in one
segment, code in another segment).
– must be aware of segment size limit.
• The OS maintains a segment table for each
process. Each entry contains:
– the starting physical addresses of that
segment.
– the length of that segment (for protection).

90
Example of Segmentation

91
Logical address used in segmentation
• When a process enters the Running state, a
dedicated register gets loaded with the starting
address of the process’s segment table.
• Presented with a logical address (segment number,
offset) = (s, d), the CPU indexes (with s) the
segment table to obtain the starting physical
address b and the length l of that segment.
• The physical address is obtained by adding d to b
(in contrast with paging):
– the hardware also compares the offset d with the length l
of that segment to determine if the address is valid.

93
Segmentation Architecture
• Logical address consists of a two tuple:
<segment-number, offset>,
• Segment table – maps two-dimensional physical
addresses; each table entry has:
– base – contains the starting physical address
where the segments reside in memory.
– limit – specifies the length of the segment.
• Segment-table base register (STBR) points to the
segment table’s location in memory.
• Segment-table length register (STLR) indicates
number of segments used by a program;
segment-number s is legal if s < STLR.
95
Address Translation Architecture

96
Sharing in Segmentation Systems
• Segments are shared when entries in
the segment tables of 2 different
processes point to the same physical
locations.
• Example: the same code of a text
editor can be shared by many users:
– Only one copy is kept in main memory.
• But each user would still need to have
its own private data segment.
98
Shared Segments Example

99
Simple segmentation/paging
comparison (1)
• Segmentation is visible to the programmer
whereas paging is transparent.
• Naturally supports protection/sharing.
• Segmentation can be viewed as commodity
offered to the programmer to logically
organize a program into segments while
using different kinds of protection
(example: execute-only for code but read-
write for data).
101
Simple segmentation/paging
comparison (2)
• Segments are variable-size; Pages are fixed-
size.
• Segmentation requires more complicated
hardware for address translation than paging.
• Segmentation suffers from external
fragmentation. Paging only yields a small internal
fragmentation.
• Maybe combine Segmentation and Paging?

103
 Intel Memory Management
This set of slides is designed to explain the Memory
Management Architecture used by Intel Pentium
processors.
For these slides we will use the Intel document found at:

http://www.intel.com/design/process
or/manuals/253668.pdf
Intel explains this document as a description of the
hardware interface required by an Operating
System in order to implement a Memory
Management.

10/20/2017 Pushpinder Singh Patheja 106

Example: The Intel Pentium

• Supports both segmentation and

segmentation with paging.
• CPU generates logical address
– Given to segmentation unit which
produces linear addresses.
– Linear address given to paging unit:
• Which generates physical address in main
memory.
• Paging units form equivalent of MMU.

107
Logical to Physical Address Translation

108
Intel Pentium Segmentation

109
PAGED SEGMENTATION Segmentation

Combination of paging and

segmentation.

address =
frame at ( page table
base for segment
+ offset into page
table )
+ offset into memory

Look at example of Intel

architecture.

111
Intel Memory Management

This is an overview of the hardware pieces provided by Intel.

It’s what we have to work with if we’re designing an O.S.

112
Three-level Paging in Linux

113
 Intel Memory Management
The memory management facilities of the IA-32 architecture are
divided into two parts:
Segmentation
Segmentation provides a mechanism of isolating individual code,
data, and stack modules so that multiple programs (or tasks) can
run on the same processor without interfering with one another.
When operating in protected mode, some form of segmentation must
be used.
Paging.
Paging provides a mechanism for implementing a conventional
demand-paged, virtual-memory system where sections of a
program’s execution environment are mapped into physical
memory as needed. Paging can also be used to provide isolation
between multiple tasks.
These two mechanisms (segmentation and paging) can be configured
to support simple single program (or single-task) systems,
multitasking systems, or multiple-processor systems that used
shared memory.
114