Transcript Process A - Anvari.Net

Memory Management
COSC513 – Spring 2004
Student Name: Nan Qiao
Student ID#: 104454
Professor: Dr. Morteza Anvari
1
Goals of Memory Management





2
Relocation
Protection
Sharing
Logical Organization
Physical Organization
Relocation

Location of a program is not known until
the program is executed
 Where
the program is loaded depends on what
other programs are in the system
 A program may be swapped out and then back into
a different location

3
Need to be able to execute the program
regardless of where it is loaded
Protection


User processes cannot be allowed to read
or write outside their boundaries
Protection must be done at runtime
 Programs
can be loaded anywhere in memory
 Programs can dynamically allocate memory

Check for valid addresses during address
translation
 Verify
4
that address is within its bound
Sharing

Several processes may need access to the
same data
 Shared
operating system library (i.e. DLL)
 Shared data buffer


More efficient to allow shared access than
to copy the data
Contrary to protection schemes
 Cannot
just allow all processes access to all
memory
5
Logical Structure

A program is typically constructed based
on different types of modules
 i.e.
code, data, stack, heap
 Access to each type may be different (I.e.
read/write/shared/execute)



6
Modules are written and compiled
separately
References are resolved at runtime
Typically implemented with segmentation
Physical Structure

Need the ability to swap between main and
secondary storage
 Secondary
storage is large and non-volatile
 Main memory is fast


Solution: Divide memory into units that can
be moved between disk and memory
Movement is coordinated by user or the OS
 OS
knows current system resources
 OS can perform movement more efficiently
7
Memory Partitioning

Fixed partitioning
 Processes

Dynamic partitioning
 Processes

sized regions of small size
Segmentation
 Large

dynamic regions
Virtual memory
 Uses
8
loaded into variable sized regions
Paging
 Fixed

loaded into regions of fixed size
pages and/or segments
Fixed Partitioning

Memory is divided into a number of fixed
sized partitions
 Equal
sized: all pages are the same
 Unequal sized: small and large pages



The entire process is loaded into
contiguous memory
Advantage: Simple to implement
Disadvantage: Can be wasteful
 Page
9
sizes are determined by the a-priori
Equal Sized Partitions

Load processes into first available region
 Memory
utilization can be low
 Large processes may not fit
Operating System
8M 8M
Process
Too large
Cannot be
loaded
4M Process
8M
2M Process
8M
8M
10M Process
8M
10
Internal
Fragmentation
Unequal Sized Partitions

Load process into:
 Smallest
free region that fits
 Region closest to size (may require waiting)

Advantages
 Accommodates
large and small processes
 May have better utilization than a fixed scheme

Disadvantages
 Memory
utilization low if processes are small
 Limits the number of active processes
11
Unequaled Sized Partitions (example)

Only processes larger than their partitions
waste memory
 Less
internal fragmentation
Operating System
2M 2M
Process
4M 4M
Process
8M 8M
Process
Internal
Fragmentation
12
10M Process
16M
Dynamic Partitioning

Partitions are of variable size
 Allocate



Number of partitions only limited by the
amount of free memory
Load entire process into contiguous
memory
Advantages:
 No

only the amount of memory needed
internal fragmentation
Disadvantages:
 Fragmentation
still possible (external)
 More complex (requires placement scheme)
13
Dynamic Partitioning (example)


Load processes contiguously in memory
Holes are created when processes release
memory
External
Fragmentation
Operating System
8M Process
8M
3M Process
1M Process
Does not
fit
11M Process
7M Process
10M Process
14
1M
32M
24M
21M
20M
9M
2M
2M
Placement Algorithm

The OS must decide which hole to fill when
allocating memory to a process
 Best
fit: Find the smallest hole that satisfies the
allocation
 Worst fit: Use the biggest free region
 First fit: Use the first region in memory that satisfies
the allocation
 Next fit: like first fit, but search starting from the last
allocation
15
Internal Fragmentation




i.e. wasted memory within a partition
Occurs for fixed sized partitions
Occurs when a process does not use the
entire partition
Prevent by dynamically partitioning
 However
16
this causes external fragmentation
External Fragmentation




i.e. wasted memory outside of the partition
Occurs in variable sized partitions
Occurs when holes are not large enough to
hold a new process
Solution:
 Compaction
17
Compaction

Eliminate holes by moving processes
 Copy
operation is expensive
Operating System
8M Process
Operating System
8M
11M Process
3M Process
1M Process
11M Process
7M Process
18
3M Process
1M
32M
7M Process
24M
21M
20M
9M
2M
1M
11M
Disadvantages of Partitioning


Fragmentation is unavoidable
Must load entire process into memory
 Limits


the number of active processes
Solution: use paging and/or segmentation
Why study partitioning
 Historical
reasons
 Paging and segmentation are based on it
 May still be used for dynamic (heap) allocation
19
Paging





20
Memory is divided into small
page frames
Pages of process are loaded
into frames (need not be
contiguous)
Less external fragmentation
Small pages limit internal
fragmentation
Page table translates page
addresses to frames
Frame
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Main Memory
Paging (Example)



21
Load pages into empty
frames
Sufficient frames must
exist for entire process
No compaction needed
(pages can be loaded into
non-contiguous frames)
Frame
0
Main Memory
Process D
A (1)
1
A (2)
Process D
2
Process A
D (3)
3
A (4)
Process D
4
Process B (1)
5
Process B (2)
6
Process B (3)
7
Process B (4)
8
Process B (5)
9
Process B (6)
10
Process C (1)
11
Process C (2)
12
Process C (3)
13
Process C (4)
14
Process D (5)
15
Process D (6)
Page Tables


One page table for each
process
Page table translates
logical addresses to
physical addresses
Process B
Page Frame
0
4
1
5
2
6
3
7
4
8
5
9
22
Process C
Page Frame
0
10
1
11
2
12
3
13
Frame
0
Main Memory
Process D (1)
1
Process D (2)
2
Process D (3)
3
Process D (4)
4
Process B (1)
5
Process B (2)
6
Process B (3)
7
Process B (4)
8
Process B (5)
Process D
9
Process B (6)
Page Frame
0
0
1
1
2
2
3
3
4
14
5
15
10
Process C (1)
11
Process C (2)
12
Process C (3)
13
Process C (4)
14
Process D (5)
15
Process D (6)
Logical to Physical Translation

Translation done in hardware
N bits translated to frame number
 Lower M bits contain offset into page
0 0 0 0 1 0 1 1 0 0
Page Offset
Page 1
0 0 0 0
Logical Address
1 0 1 1 0 0
Frame Number
Page 0 0 1 0
Table 0 0 1 1
Page 2
Page
Number
Page 0
 Upper
Page Offset
Frame
Number
0 0 1 0
23
1 0 1 1 0 0
Physical Address
...
Advantages of Logical Addressing


Logical addressing provides a means for
process relocation
Each process uses the same logical
addresses
 Separate
page tables map logical addresses of
each process to different physical addresses
 Process segments start from a fixed location
 Makes compiling/loading easier
24
Segmentation

Process memory is divided into segments
 One
segment for each type of data
(data,code,stack,heap…)
 Each segment can be loaded anywhere


Segments are of variable size
Address translation is required
 Address
contains segment number and offset
 Must ensure that process does not address beyond
the segment limit
25
Comparing Paging and Segmentation

Size of regions
 Small
and fixed size for paging
 Large and variable size for segmentation

Address translation
 Simple
bit shift for paging
 More complicated addition for segmentation

Advantages
 Paging:
very little fragmentation
 Segmentation: logical structure
26
Combining Paging and Segmentation



Combine to gain advantages of both
A process’s segments consist of a number
of fixed sized pages
Requires two address translations
 First
logical segment to logical page address
 Next logical page to physical page address
27
How Paging/Segmentation Meet
Requirements

Relocation
 Logical
to physical translation allow segments or
pages to be loaded anywhere

Protection
 Address
translation gives hardware an opportunity
to check for valid addresses

Sharing
 Shared
regions can be divided into segments
 Two logical segments can be mapped to one
physical shared segment
28
How Paging/Segmentation Meet
Requirements

Logical Organization
 Program

is divided into segments
Physical Organization
 Pages
are convenient units to swap in and out of
memory
29