Main Memory OS

Chapter 8: Main Memory
Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013
Chapter 8: Memory Management
 Background
 Swapping
 Contiguous Memory Allocation
 Segmentation
 Paging
 Structure of the Page Table
Operating System Concepts – 9th Edition 8.2 Silberschatz, Galvin and Gagne ©2013
Objectives
 To provide a detailed description of various ways of organizing memory hardware
 To discuss various memory-management techniques, including paging and segmentation
 To provide a detailed description of the Intel Pentium, which supports both pure segmentation
and segmentation with paging
Background
 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.)
Background
 Program must be brought (from disk) into memory and placed within a process for it to be run
 Main memory and registers are only storage CPU can access directly
 Memory unit only sees a stream of addresses + read requests, or address + data and write requests
 Register access in one CPU clock (or less)
 Main memory can take many cycles, causing a stall
 Cache sits between main memory and CPU registers
 Protection of memory required to ensure correct operation
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.
Base and Limit Registers
 A pair of base and limit registers define the logical address space
 CPU must check every memory access generated in user mode to be sure it is
between base and limit for that user
Hardware Address Protection with Base and Limit Registers
Binding of Instructions and Data to Memory
 Address binding of instructions and data to memory addresses can
happen at three different stages
1. 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.
2. 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.
3. 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.
Multistep Processing of a User Program
Logical vs. Physical Address Space
 The concept of a logical address space that is bound to a
separate physical address space is central to proper memory
management
 Logical address – generated by the CPU; also referred to as virtual address
 Physical address – address seen by the memory unit
Logical vs. Physical Address Space
 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
scheme
 Logical address space is the set of all logical addresses generated

by a program
 Physical address space is the set of all physical addresses

generated by a program
Memory-Management Unit (MMU)
 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).
 To start, consider simple scheme where the value in the relocation

register is added to every address generated by a user process at the
time it is sent to memory
 Base register now called relocation register
Dynamic relocation using a relocation register
Overlays
 To enable a process to be larger than the amount of
memory allocated to it, we can use overlays. The idea of
overlays is to keep in memory only those instructions and
data that are needed at any given time. When other
instructions are needed, they are loaded into space
occupied previously by instructions that are no longer
needed.
Overlays: Example
Overlays
Swapping
 A process needs to be in the memory to be executed. A
process, however, can be swapped temporarily out of
memory to a backing store, and then brought back into
memory for continued execution.
 Multiprogramming environment with a round robin CPU

scheduling algorithm.
Swapping
 Backing store is a fast disk large enough to accommodate
copies of all memory images for all users; it must provide
direct access to these memory images.
 The system maintains a ready queue of all processes whose

memory images are on the backing store or in memory and
are ready to run.
 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
Schematic View of Swapping
Contiguous Allocation
 The main memory must accommodate both operating system and the
various user spaces. Thus memory allocation should be done
efficiently.
 The memory is usually divided into two partitions: one for the
resident operating system and one for the user processes.
 The operating system normally placed in the low memory
 User processes then held in high memory
 It is desirable to have several user processes residing in the

memory at the same time. In contiguous memory allocation, each
process is contained in a single contiguous section of memory.
Single Process Systems
 In this technique, only one

process is intended to run at one Free Space
time.
 In general a part of memory will

Main
USER
be unused
Memory
PROCESS
(RAM)
OS
Single Process Allocation
Fixed Partition Memory
1000 K 1000 K
 In this technique, memory is divided

into number of fixed size areas, each Partition # 3
which can hold one process. 400 K
 Typically the partitions would be 600K
setup with a range of partition sizes. Main

Memory
Partition #2
(RAM)
300 K
300 K
Partition # 1
200 K
100 K
OS
0K
Fixed Partition Allocation
Fixed Partition Memory
 Wastage of memory within the apace 1000 K
allocated to a process is known as

Internal Fragmentation Partition # 3
400 K C
Process
300 K
 Draw Backs
600K
1. Can prevent a process being run
due to unavailable of sufficient
Partition # 2
size partition 300 K B
Process
200 K
2. Internal Fragmentation waste
space, could accommodate 300 K
another process Partition # 1
Process
200 K A
150 K
100 K
OS
Variable Partition Memory
1000 K
 In this technique, processes are 975 K
loaded in consecutive areas until the Available
ProcessSpace
D
memory is filled or more likely the 225 K
remaining space is too small to 750 K
accommodate another process.
Process C
300 K
450 K
Process B
200 K
250 K
Process A
150 K
100 K
OS
1000 K
 When a process terminates the space 975 K
occupied is freed and become Free
Available
Process Space
250 K D
available for the loading of new 225 K
process 750 K
 A New Process E of size 300K Process C

300 K
arrives but we can not load it even
though system have 450K Total Free 450 K
Space
Free B
Process
200 K
 The wastage of space in this fashion 250 K
is known as External Process A
150 K
Fragmentation 100 K
OS
1000 K
 Possible Solution 975 K
Free
1. Coalescing of Holes Available Space
250 K
2. Compaction of Holes
750 K
Process C
300 K
450 K
Free
200 K
250 K
Process A
150 K
100 K
OS
1000 K
1. Coalescing of Holes: A Process 975 K
adjacent to one or more holes will Free
Available Space
250 K
terminate and free its space
allocation. This results in two or 750 K
three adjacent holes which can then Three Holes Coalesce
be viewed and utilized as a single Total Free Space
Process C
hole 300 K
750 K
450 K
 As in this case Process C will be
Free
terminated to make Three- 200 K
Holes-Coalesce
250 K
Process A
150 K
100 K
OS
1000 K
2. Compaction of Holes: The other 975 K
possibility is to physically moving Free
Available Space
250 K
the resident process about the
Free Space
memory in order to close up the 450 K 750 K
holes and hence bring the free space
into a single large block Process C
300 K
450 K
Process C
FreeK
300
200 K
250 K
Process A
150 K
100 K
OS
Storage Placement Policies
 When new processes have to be loaded it is necessary to try to
select the best location in which to place them by keeping in
mind that try to provide maximum overall throughput for the
system.
 An algorithm used for this purpose is termed as placement

policy. A number of such policies have been devised
1. Best Fit
2. First Fit
3. Worst Fit
Storage Placement Policies
1. Best Fit: An incoming process is placed in a hole in which it
fits mostly tightly
2. First Fit: An incoming process is placed in the first available

hole which can accommodate it
3. Worst Fit: an incoming Process is placed in the hole which

leaves the maximum amount of unused space
Example: Storage Placement Policies
Available Memory
slots
100 K
300 K
200 K
400 K
Best Fit ? Worst Fit ? First Fit ?
Available Memory
slots
100 K
300 K
Best Fit 200 K
400 K
Best Fit ?
Available Memory
slots
100 K
300 K
200 K
Worst fit 400 K
Worst Fit ?
Available Memory
slots
100 K
First Fit 300 K
200 K
400 K
First Fit ?
A variable partition memory system has following holes sizes in the given order
20 K
A new process is to be loaded of size 25 K which
hole size would be filled using Best Fit ? Worst 15 K
Fit ? First Fit ?
40 K
60 K
10 K
25 K
A variable partition memory system has following holes sizes in the given order
20 K
A new process is to be loaded of size 25 K which
hole size would be filled using Best Fit ? Worst 15 K
Fit ? First Fit ?
First Fit 40 K
Worst Fit 60 K
10 K
Best Fit 25 K
Paging
 Paging is a memory management scheme that permits the
physical address space of a process to be noncontiguous.
 Avoids external fragmentation
Paging
 Each Process is divided into number  The memory space
A1
of fixed size chunks called Pages A2
is also viewed as a
set of page frames
A3
of the same size
Process A A4
B1
A1
Process B B2
A2
B3
A3
B1 B4
A4
B2 B5
B3 Process C C1
B4 C2
C1
B5 C3
C2
C3
Paging
A1 A1 A1
A2 A2 A2
A3 A3 A3 Frames do not
A4 A4 A4 need to be
B1 -- D1 Contiguous
B2 -- D2
B3 -- D3
B4 -- E1
B5 -- E2
C1 C1 C1
C2 C2 C2
C3 C3 C3
-- E3
-- E4
--
Binary Basics
1. Using 1 Bit we can represent 2^1 i.e 2 memory locations
.
2. Using 2 bits, we can represent 2^2 i.e. 4 memory locatio
ns.
3. Using 3 bits, we can represent 2^3 i.e. 8 memory locatio
ns.
Therefore, if we generalize this,

 Using n bits, we can assign 2^n memory locations.
 n bits of address → 2 ^ n memory locations
Binary Basics
Address Translation Scheme
 If the size of the logical address space is 2 m, and a page size is 2n
bytes
 Then the high-order m− n bits of a logical address designate the page

number, and the n low-order bits designate the page offset
 Logical Address generated by CPU is divided into:
 Logical address space can be defined as the size of the

process. The size of the process should be less enough
so that it can reside in the main memory.
 Logical Address generated by 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
 Here logical address space is 2m and page size is 2n
page number page offset
p d
m-n n
Physical Address: Physical address space in a system can

be defined as the size of the main memory. It is really
important to compare the process size with the
physical address space. The process size must be less
than the physical address space.
Physical Address
The physical address of the location referenced by (p, d) is computed by

appending d at the end of f, as shown below:
page number page offset
f d
Paging
 The size of a page is a power of 2, the typical page size lying between
1K (210) and 16K (214).
 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.
Paging Hardware
Paging Hardware
Paging Model of Logical and Physical Memory
Paging Example
0 n =2 and m=4
0 16 byte Logical Memory
1 32-byte Physical Memory

Page Size 4-byte pages
1 2
3
2
3
5
Free Frames
Before allocation After allocation
Examples of Pageing
Consider a logical address space of 8 pages of 1024 words mapped into

memory of 32 frames.
1.How many bits are there in the logical address ?

2.How many bits are there in physical address ?
1) Logical address will have

3 bits to specify the page number (for 8 pages) .
10 bits to specify the offset into each page (2 10 =1024 words) = 13 bits.
2) Physical address will have

For (25) = 32 frames of 1024 words each (Page size = Frame size)
We have 5 + 10 = 15 bits.
Implementation of Page Table
 In the CPU registers: This is OK for small process address spaces and
large page sizes. It has the advantage of having effective memory
access time about the same as memory access time.
 In the main memory: A page table base register (PTBR) is needed to

point to the page table. With page table in main memory, the effective
memory access time get doubled which is not acceptable because it
would slow down program execution by a factor of two.
 The standard solution to this problem is to use a special, small, fast

lookup hardware cache called a translation look-aside buffer (TLB).
The TLB is associative, high-speed memory. t is typically between 32
and 1,024 entries in size.
Paging Hardware With TLB
Effective Access Time
 The percentage of times that the page number of interest is found in the
TLB is called the hit ratio.
 An 80-percent hit ratio, for example, means that we find the desired
page number in the TLB 80 percent of the time.
 If it takes 100 nanoseconds to access memory, then a mapped-memory

access takes 100 nanoseconds when the page number is in the TLB.
 If we fail to find the page number in the TLB then we must first access
memory for the page table and frame number (100 nanoseconds) and
then access the desired byte in memory (100 nanoseconds), for a total
of 200 nanoseconds.
 To find the effective memory-access time, we weight the case
by its probability:
effective access time = 0.80 × 100 + 0.20 × 200

= 120 nanoseconds
 In this example, we suffer a 20-percent slowdown in average

memory-access time (from 100 to 120 nanoseconds).
 For a 99-percent hit ratio we have
effective access time = 0.99 × 100 + 0.01 × 200

= 101 nanoseconds
 This increased hit rate produces only a 1 percent slowdown in

access time.
Shared Pages
 Shared code
 One copy of read-only (reentrant or non-self-modifying) code shared
among processes (i.e., text editors, compilers, window systems)
 Similar to multiple threads sharing the same process space
 Also useful for interprocess communication if sharing of read-write
pages is allowed
 Private code and data

 Each process keeps a separate copy of the code and data
 The pages for the private code and data can appear anywhere in the
logical address space
Shared Pages
 Consider a system that supports 40 users, each of whom executes a text
editor. If the text editor consists of 150 KB of code and 50 KB of data
space, we need 8,000 KB to support the 40 users.
 By Using shared Pages Technique, Each user’s page table maps onto
the same physical copy of the editor, but data pages are mapped onto
different frames.
 Thus, to support 40 users, we need only one copy of the editor (150 KB),
plus 40 copies of the 50 KB of data space per user. The total space
required is now 2,150 KB instead of 8,000 KB — a significant savings
Shared Pages Example
Segmentation
 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 a length. The addresses specify both
the segment name and the offset within the segment.
Segmentation
 An example of the logical address space of a process with
segmentation is shown below.
Logical View of Segmentation
1
4
1
3 2
4
user space physical memory space
Logical View of Segmentation
Segment Table Architecture
 Each entry of a segment table has a base and a
segment limit.
 The segment base contains the starting

physical address where the segment resides in
memory
 The segment limit specifies the length of the

segment.
Segmentation Architecture
 There are two more registers, relevant to the concept of segmentation:
 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, and

 offset, d, is legal if d < limit.
Segmentation Hardware
Segmentation Hardware
Protection in Segmentation
 Consider the following segment table
Protection in Segmentation
 The bits associated with each entry in the segment table, for the
purpose of protection are:
 Validation bit : if the validation bit is 0, it indicates an illegal segment

 Read, write, execute bits
Issues with Segmentation
 Segmentation may then cause external fragmentation (i.e. total memory
space exists to satisfy a space allocation request for a segment, but
memory space is not contiguous), when all blocks of memory are too
small to accommodate a segment.
 In this case, the process may simply have to wait until more memory (or
at least a larger hole) becomes available or until compaction creates a
larger hole
End of Chapter 8
Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013

Main Memory OS

Uploaded by

Copyright:

Available Formats

Main Memory OS

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Main Memory OS

Uploaded by

Copyright:

Available Formats

Chapter 8: Main Memory

 To discuss various memory-management techniques, including paging and segmentation

 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

 Register access in one CPU clock (or less)

 Main memory can take many cycles, causing a stall

 Cache sits between main memory and CPU registers

 Protection of memory required to ensure correct operation

 The task of memory management includes keeping track of used

 It is also responsible for swapping processes in and out of main

 Logical address – generated by the CPU; also referred to as virtual address

 Physical address – address seen by the memory unit

 Logical and physical addresses are the same in compile-time

 Logical address space is the set of all logical addresses generated

 Physical address space is the set of all physical addresses

 To start, consider simple scheme where the value in the relocation

 Base register now called relocation register

 Multiprogramming environment with a round robin CPU

 The system maintains a ready queue of all processes whose

 Roll out, roll in – swapping variant used for priority-based

 It is desirable to have several user processes residing in the

 In this technique, only one

 In general a part of memory will

 In this technique, memory is divided

 Typically the partitions would be 600K

setup with a range of partition sizes. Main

allocated to a process is known as

 A New Process E of size 300K Process C

 An algorithm used for this purpose is termed as placement

2. First Fit: An incoming process is placed in the first available

3. Worst Fit: an incoming Process is placed in the hole which

Best Fit ? Worst Fit ? First Fit ?

Best Fit 200 K

Worst fit 400 K

First Fit 300 K

 Avoids external fragmentation

Therefore, if we generalize this,

 Then the high-order m− n bits of a logical address designate the page

 Logical address space can be defined as the size of the

 Here logical address space is 2m and page size is 2n

page number page offset

Physical Address: Physical address space in a system can

The physical address of the location referenced by (p, d) is computed by

page number page offset

 In order to run a program of size n pages, we find n free frames and

 In order to keep track of a program’s pages in the main memory a

0 16 byte Logical Memory

1 32-byte Physical Memory

Before allocation After allocation

Consider a logical address space of 8 pages of 1024 words mapped into

1.How many bits are there in the logical address ?

1) Logical address will have

2) Physical address will have

 In the main memory: A page table base register (PTBR) is needed to

 The standard solution to this problem is to use a special, small, fast

 If it takes 100 nanoseconds to access memory, then a mapped-memory

effective access time = 0.80 × 100 + 0.20 × 200

 In this example, we suffer a 20-percent slowdown in average

effective access time = 0.99 × 100 + 0.01 × 200