Operating Systems and Internetworking: Memory Management and Virtual Memory

Memory Management Overview

UNIVERSITYOF
PORTSMOUTH
Operating Systems and Internetworking
OSI - M30233 (OS Theme)
Week 8- Virtual Memory
UPERCOMPUTERS
OPERATING
GAME
PROCESSOH
APPLICATION
SYSTEMS
INDEPENDENT TIME
MAKE ALMOST TASKS
COMPONENT
INPUT
MULTHISER
WORK E
ALTHOUGH
PHONES
PROVIDES
ALLOCATION ONE
STORAGE
SOFTWARE
FOUND
DEVICE INTERMEDIARY
FUNCTIONS USE
SYSTEM
OPERATE
DIRECTLY
CONTAINS COLLECTION
COMPUTER
INTERRUPTED RESOURCES
GROUP RE
ORDER
MANAGES
COMPUTERS
SCHEDULE
OUTPUT DESIGNED
PROGRAM
EMBEDDED CONSOLES
ACCOUNTING
EFFICIENT EXECUTED
MULTIPLE
Dr Tamer Elboghdadly
Busi
Papol
SERVICES
COMMON
TIME-SHARING
MAY
FUNCTION
HARDWARE
SERVERS
MEMORY DISTRIBUTED
9. FREQUENTLY
ACCESS
PROGRAMS REQUIRE
INCLUDE 3
WEB INTERNETSMemory Management

• Plan:
  . Review main memory, and instructions that access it.
  . Problems using physical addresses
  - Address spaces as an abstraction
  . Virtual memory - concept and implementation

UNIVERSITYOF
PORTSMOUTH
Slide 2 of 39
2

Main Memory Characteristics

Main Memory
. Large area of storage - typically some Gigabytes on a
modern PC.
. Predominantly volatile, Random Access Memory (RAM)
. Values lost when system powered down.
. Each byte has a unique numeric address, and can be
individually read or written by the CPU
. Address is typically a 32-bit or 64-bit binary number.
crucial

UNIVERSITYOF
PORTSMOUTH
Slide 3 of 39
3

Memory Addressing Instructions

Instructions that Address Memory
· Simple example:
MOV EAX, [0x101000]
. Load contents of memory at 0x101000 (decimal 1052672) to register EAX.
. This loads data from memory.
. Code is also stored in memory, and some operations reference
instructions by address:
JMP 0x11000
. Jump to the instruction stored in program memory at 0x11000

UNIVERSITYOF
PORTSMOUTH
Slide 4 of 39
4

Physical Addresses and Multiprogramming

Physical Addresses
. The physical address of a byte of memory is a value between 0 and some
large number, proportionate to size of available RAM.
. If addresses used in instructions like those on the previous slide were
always physical addresses, multiprogramming would be hard.

UNIVERSITYOF
PORTSMOUTH
Slide 5 of 39
5

Relocation Problem Illustration

Relocation Problemt
0
32764
.
CMP
16412
1640816404
16400
16396
16392
16388
JMP 28
16384
0
16380
0
16380
0
16380
:
:
:
ADD
28
CMP
28
ADD
28
MOV
24
24
MOV
24
20
20
20
16
16
16
12
12
12
8
8
8
4
4
4
JMP 24
0
JMP 28
0
JMP 24
0
(b)
(c)
(a)
Program A
Program B
Memory

UNIVERSITYOF
PORTSMOUTH
+Tanenbaum, MOS, Fig 3-2
Slide 6 of 39
6

Challenges with Physical Addresses

Problems using Physical Addresses
. Can automatically edit code to achieve relocation, but still ...
. Different user programs may interfere with one another by using an
address outside their allocated space.
. User programs could read or write data controlled by the operating
system, and crash the system.

UNIVERSITYOF
PORTSMOUTH
Slide 7 of 39
7

Address Spaces Abstraction

Address Spaces
. The address space is a new abstraction for memory.
. A clean way of sharing memory amongst processes.
. Comparable with the thread abstraction, which is an abstraction for sharing CPU
between processes.
. With threads, it is as if each thread is running on its own CPU.
. With address spaces, it is as if each process has a large, private memory,
addressed between 0 and some limit.

UNIVERSITYOF
PORTSMOUTH
Slide 8 of 39
8

Virtual Memory Concept

Virtual Memory
. Modern PCs and comparable processors provide virtual memory.
. Implements a virtual address space for every process, typically from 0 to
(232 - 1) (32 bit processors), or 0 to (264 -1) (64 bit processors).
. All memory addresses embedded in code refer to this virtual address
space, rather than addresses in physical memory.

UNIVERSITYOF
PORTSMOUTH
Slide 9 of 39
9

Virtual Address Space Sizes

Virtual Address Spaces
32-bit
4294967295
4294967294
4294967293
. .
2
1
0

UNIVERSITYOF
PORTSMOUTH
64-bit
18446744073709551615
18446744073709551614
18446744073709551613
.
2
1
0
Slide 10 of 39
10

Virtual Address Space Utilization

Use of Virtual Address Space
. Most processes use only a tiny fraction of their
available virtual address space
. Addresses that are unused by a program simply
have no physical memory assigned to them.
. If processes use more virtual memory than available
physical memory, OS maps some locations of virtual
address space to secondary storage (hard disk).

Virtual memory
(per process)
Physical
memory
Another
process's
memory
RAM
Disk

UNIVERSITYOF
PORTSMOUTH
Slide 11 of 39
11

Implementing Virtual Memory

IMPLEMENTING VIRTUAL MEMORY

UNIVERSITYOF
PORTSMOUTH
Slide 12 of 39

Paging Implementation

Implementing Virtual Memory
. Normally implemented by paging.
. Virtual address space is divided into pages of fixed size (e.g. 4Kbyte).
. At any point in time, any given page is either mapped to a frame of the
same size in physical memory, or unmapped.

UNIVERSITYOF
PORTSMOUTH
Slide 13 of 39
13

Single Page Mapping Example

Mapping Example (Single Page)
· A mapped page (size 4096):
VM page
12287
>
12286
. ..
. ..
. .
.
8193
24577
24576
8192
Virtual
address
Physical
address

UNIVERSITYOF
PORTSMOUTH
Physical
Memory frame
28671
28670
Slide 14 of 39
14

Hardware and Software Support for Virtual Memory

Implementing Virtual Memory
. Needs both hardware and software support.
. Memory Management Unit (MMU) in CPU translates addresses from virtual to
physical, but raises a kind of interrupt (page fault) if address is in an unmapped
page.
. OS deals with this interrupt - e.g. Allocating an available frame, and copying data
between physical memory and backing store (disk) where appropriate.
- Hardware deals with common, easy cases, very quickly; but passes
control to OS if it can't deal with the request. OS does the "hard" part.

UNIVERSITYOF
PORTSMOUTH
Slide 15 of 39
15

Memory Management Unit Function

The Memory Management Unitt
The CPU sends virtual
addresses to the MMU
CPU
package
CPU
Memory
management
unit
Memory
Disk
controller
Bus
The MMU sends physical
addresses to the memory

UNIVERSITYOF
PORTSMOUTH
+Tanenbaum, MOS, Fig 3-8
Slide 16 of 39
16

Page Table Structure

The Page Table
. Each process has its own mapping between pages in its virtual address
space, and frames in the physical memory.
. Mapping is embodied in the page table.
. Page table usually implemented as a data structure, stored in main memory.
· Managed by OS, but interpreted by MMU, so format tied to CPU type.

UNIVERSITYOF
PORTSMOUTH
Slide 17 of 39
17

Page Table Mapping Example

Page Table Mapping Examplet
. This example is for an (unrealistically small)
address space (216 bytes = 64Kbyte),
divided into 4Kbyte frames, mapped to a
32Kbyte physical memory.

Virtual
address
space
60K-64K
X
56K-60K
X
Virtual page
52K-56K
X
48K-52K
X
44K-48K
7
40K-44K
X
36K-40K
5
Physical
memory
address
32K-36K
X
28K-32K
X
28K-32K
24K-28K
X
24K-28K
20K-24K
3
20K-24K
16K-20K
4
16K-20K
12K-16K
0
8K-12K
6
8K-12K
4K-8K
1
4K-8K
OK-4K
2
OK-4K
Page frame

UNIVERSITYOF
PORTSMOUTH
+Tanenbaum, MOS, Fig 3-9
Slide 18 of 39
18

Addressing Example: MOV EAX

12K-16KAddressing Example
- Suppose instruction:
MOV EAX, [8196]
is issued (copy from memory location 8196 to register EAX).
· Virtual address can be broken down as follows:
8196 = 2×4K + 4
. We say this address is offset 4 bytes from the start of page
2.

. Remember 4K = 4096 is the page size.

Virtual
address
space
60K-64K
X
56K-60K
X
Virtual page
52K-56K
X
48K-52K
X
44K-48K
7
40K-44K
X
36K-40K
5
Physical
memory
address
32K-36K
X
28K-32K
X
28K-32K
24K-28K
X
24K-28K
20K-24K
3
20K-24K
16K-20K
4
16K-20K
12K-16K
0
8K-12K
6
8K-12K
4K-8K
1
4K-8K
OK-4K
2
OK-4K
Page frame

UNIVERSITYOF
PORTSMOUTH
Slide 19 of 39
19

Calculating Physical Address

Addressing Example
. To calculate page and offset, divide virtual
address by page size (i.e. by 4K = 4096)
· Page number is integer part of result
· Offset is remainder
. Page 2 is mapped to frame 6, so physical
address is:
6×4K + 4 =24580
(note offset, 4, does not change)

Virtual
address
space
60K-64K
X
56K-60K
X
Virtual page
52K-56K
X<48K-52K
X
44K-48K
7
40K-44K
X
36K-40K
5
Physical
memory
address
32K-36K
X
28K-32K
X
28K-32K
24K-28K
X
24K-28K
20K-24K
3
20K-24K
16K-20K
4
12K-16K
12K-16K
0
8K-12K
6
8K-12K
4K-8K
1
4K-8K
OK-4K
2
OK- 4K
Page frame

UNIVERSITYOF
PORTSMOUTH
Slide 20 of 39
20

Normal Address Translation Process

16K-20KNormal Address Translation
. In the example given the MMU hardware transparently maps address
8196 to 24580.
. Software only "sees" virtual address 8196.
. Memory only "sees" physical address 24580 (this is the address that goes on the
bus).
. Operating system is not involved here - everything done in hardware, so
(quite) fast.
. Provided we have a Translation Lookaside Buffer - see later.

UNIVERSITYOF
PORTSMOUTH
Slide 21 of 39
21

Page Table Implementation Details

Implementation of Page Tablet
1
110000000000100
4
15
000
0
14
000
0
13
000
0
12
000
0
11
111
1
10
000
0
9
101
1
1
Page
table
8
000
0
7
000
0
6
000
0
5
011
1
4
100
1
3
000
1
2
110
1
110
1
001
1
0
010
1
~Present/
absent bit
Virtual page = 2 is used
as an index into the
page table
Outgoing
physical
address
(24580)
Incoming
virtual
address
(8196)

UNIVERSITYOF
PORTSMOUTH
+Tanenbaum, MOS, Fig 3-10
Slide 22 of 39
22

Simple Page Table Structure

12-bit offset
copied directly
from input
to output
UNIVERSITYOF
PORTSMOUTH
0 010000000000100Simple Page Table
. In this example, page table can simply be
an array indexed by page number.
. Each record in array contains frame
number and a present/absent bit.
. In practice, record contains a few more bits -
e.g. the dirty bit records whether this frame
has been modified since it was loaded into
memory.
. More on realistic page table structures later.

1
1 1 0000000000100
15
000
0
14
000
0
13
000
0
12
000
0
11
111
1
10
000
0
9
101
1
Page
8
000
0
table
7
000
0
6
000
0
5
011
1
4
100
1
3
000
1
2
110
1
110
1
001
1
0
010
1
-Present/
absent bit
Virtual page = 2 is used
as an index into the
page table
0 010000000000100
4
Outgoing
physical
address
(24580)
Incoming
virtual
address
(8196)

UNIVERSITYOF
PORTSMOUTH
Slide 23 of 39
23

Page Miss Scenario

12-bit offset
copied directly
from input
to output
A Page Miss
. Now suppose this instruction is issued:
MOV EBX, [32780]
· Virtual address:
32780 = 8.4K + 12
is offset 12 bytes from start of page 8.
. This page is not currently mapped (present
bit is 0).
. This is called a page miss.

1
1 1 0000000000100
15
000
0
14
000
0
13
000
0
12
000
0
11
111
1
10
000
0
101
1
Page
Miss
8
000
0
7
000
O
6
000
0
011
1
100
1
000
1
110
1
110
001
1
010
1
-Present/
absent bit
Virtual page = 2 is used
as an index into the
page table
001 0000000000100
1
Outgoing
physical
address
(24580)
Incoming
virtual
address
(8196)

UNIVERSITYOF
PORTSMOUTH
Slide 24 of 39
24

12-bit offset
copied directly
from input
to output
543210
5
4
3
2
1
0