Transcript Chapter 7 Memory Management

Chapter 7
Memory Management
• Basic requirements of Memory
Management
• Memory Partitioning
• Paging
• Segmentation
1
Memory Management
A program must be loaded into
main memory to be executed.
The principal operation of memory
management is to bring processes into
main memory for execution by the
processor.
2
Memory Management
Memory needs to be allocated to ensure
a reasonable supply of ready processes
to consume available processor time
– Otherwise, for much of the time all of the
processes will be waiting for I/O and the
processor will be idle.
3
The need for memory
management
• Memory is cheap today, and getting
cheaper
– But applications are demanding more and
more memory, there is never enough!
• Memory Management involves swapping
blocks of data from secondary storage.
• Memory I/O is slow compared to CPU
– The OS must cleverly time the swapping to
maximise the CPU’s efficiency
4
Memory Management
Requirements
• Relocation
• Protection
• Sharing
• Logical organisation
• Physical organisation
5
Relocation
• The programmer does not know where the
program will be placed in memory when it
is executed,
– it may be swapped to disk and return to main
memory at a different location (relocated)
• But, OS knows because it is managing
memory and is responsible for bringing
this process into main memory
6
Relocation
Addressing
The processor and OS must be
able to translate the memory
references found in the code of
the program into actual physical
memory addresses (to be discussed)
7
Protection
• Processes should not be able to reference
memory locations in another process
without permission.
• Impossible to check absolute addresses at
compile time because the location of a
program in main memory is unpredictable.
• Must be checked at run time by the
processor.
8
Sharing
• Allow several processes to access the
same portion of memory
– Better to allow each process executing the
same program access to the same copy of
the program rather than have their own
separate copy
– Processes that are cooperating on some task
may need to share access to the same data
structure
9
Logical Organization
• Memory is organized linearly (usually)
• In contrast, programs are organized into
modules
– Modules can be written and compiled
independently
– Different degrees of protection can be given to
different modules (read-only, execute-only)
– Modules can be shared among processes
• Segmentation helps here
10
Physical Organization
• Cannot leave the programmer with the
responsibility to manage memory
– Memory available for a program plus its data
may be insufficient
– Programmer does not know how much space
will be available or where the space will be
• The task of moving information between
different levels of memory should be a
system responsibility
11
Partitioning
• An early method of managing memory
– Pre-virtual memory
– Not used much now
• But, it will clarify the later discussion of
virtual memory if we look first at
partitioning
– Virtual Memory has evolved from the
partitioning methods
12
Types of Partitioning
•
•
•
•
•
•
Fixed Partitioning
Dynamic Partitioning
Simple Paging
Simple Segmentation
Virtual Memory Paging
Virtual Memory Segmentation
13
Fixed Partitioning
• Partition memory into regions with
fixed boundaries
• Equal-size partitions
– Any process whose size is less than
or equal to the partition size can be
loaded into an available partition
14
Fixed Partitioning
Problems
• A program may be too big to fit into a
partition
• Main memory use is inefficient.
– Any program, no matter how small, occupies
an entire partition.
– This is results in internal fragmentation
(wasted space internal to a partition).
15
Fixed Partitioning
Solution – Unequal Size Partitions
• Lessen both problems
– But doesn’t solve completely
– Larger programs can be
accommodated
– Smaller programs can be placed in
smaller partitions, reducing internal
fragmentation
16
Fixed Partitioning
Placement Algorithm
• Equal-size
– Placement is trivial: a process can be loaded
into any available partition
• Unequal-size
– Can assign each process to the smallest
partition within which it will fit
– Queue for each partition
–  Processes are assigned in such a way as to
minimize wasted memory within a partition
17
Fixed Partitioning
Placement Algorithm
It is possible that a
partition is unused
even though some
smaller process
could have been
assigned to it
Select the smallest
available partition
that will hold the
process
18
Fixed Partitioning
Remaining Problems
• The number of active processes is limited
by the system
– i.e., limited by the pre-determined number of
partitions
• Partition sizes are preset at system
generation time, small jobs will not use
space efficiently
19
Dynamic Partitioning
• Dynamic partitioning can overcome some
of the difficulties with fixed partitioning
• Partitions are of variable length and
number
• Process is allocated exactly as much
memory as required
20
Dynamic Partitioning
Example
OS (8M)
P2
P1
(14M)
(20M)
Empty (6M)
Empty
P4(8M)
P2
(56M)
(14M)
Empty (6M)
P3
(18M)
• External Fragmentation
– Memory external to all
processes is fragmented and
memory utilization declines
• Can resolve using
compaction
– OS moves processes so that
they are contiguous
–  Time consuming and
wastes CPU time
Empty (4M)
21
Dynamic Partitioning
• Operating system must decide which free
block to allocate to a process
• Best-fit algorithm
– Chooses the block that is closest in size to the
request
–  Worst performer overall
• Since smallest block is found for a process, the
fragment left behind is too small to satisfy other
requests
• Memory compaction must be done more often
22
Dynamic Partitioning
• First-fit algorithm
– Scans memory from the beginning and
chooses the first available block that is large
enough
–  Simplest and fastest
–  May have many process loaded in the front
end of memory such that small free partitions
must be searched over on each subsequent
pass
23
Dynamic Partitioning
• Next-fit
– Scans memory from the location of the last
placement
–  More often allocate a free block at the end
of memory where the largest block is found
• The largest block of free memory is quickly broken
up into smaller blocks
• Compaction is required more frequently
24
Dynamic Partitioning
Allocation
25
Buddy System
• A reasonable compromise to overcome the
disadvantages of both the fixed and dynamic
partitioning schemes
• Entire space available is treated as a single
block of 2U
• If a request of size s where 2U-1 < s  2U
– entire block is allocated
• Otherwise block is split into two equal buddies
– Process continues until the smallest block greater
than or equal to s is generated
26
Buddy System
Example
27
Buddy System
Tree Representation
A binary tree representation of
the buddy allocation immediately
after the Release B request
The leaf nodes
represent the
current
partitioning the
memory
28
Relocation
• The actual (absolute) memory locations
are determined when program is loaded
into memory
• A process may occupy different partitions
which means different absolute memory
locations during execution
– Swapping
– Compaction
29
Addresses
• Logical
– Reference to a memory location independent of the
current assignment of data to memory
– A relative address is expressed as a location relative
to some known point (typically the program origin)
• Physical or Absolute
– The absolute address or actual location in main
memory
A translation must be made from a logical address to a
physical address before memory access can be achieved
30
Relocation
Hardware Support
1. Add the value
in the base
register to the
relative address
to produce an
absolute address
0. Initialize base
and bounds
registers when a
process is
assigned to the
Running state
2. Compare the
resulting address
to the value in
the bounds
register
31
Relocation
Registers Used during Execution
• Base register
– Starting address for the process
• Bounds register
– Ending location of the process
• These values are set when the process is
loaded or when the process is swapped in
32
Relocation
Registers Used during Execution
• The value of the base register is added to
a relative address to produce an absolute
address
• The resulting address is compared with
the value in the bounds register
– If the address is within bounds, instruction
execution may proceed
– Otherwise, an interrupt indicating error is
generated to OS
33
Paging
• Partition memory into small equal fixedsize chunks (frames) and divide each
process into the same size chunks
(pages)
• Pages of process could be assigned to
available frames of memory
• No external fragmentation but little internal
fragmentation consisting of only a fraction
of the last page of a process
34
Paging
Processes and Frames
A.0
A.1
A.2
A.3
D.0
B.0
D.1
B.1
D.2
B.2
C.0
C.1
C.2
C.3
D.3
D.4
OS finds free frames
and loads the pages of
Process A, B & C
Process B is suspended
and is swapped out of
main memory
All of the processes in
main memory are
blocked, and OS brings
in Process D
35
Paging
• Operating system maintains a page table
for each process which contains the frame
location for each page in the process
• Given a logical address (page number,
offset), the processor uses the page table
to produce a physical address
36
Paging
Page Table
page number
frame number
37
Paging
Logical Addresses
• Using a page size that
is a power of 2, a
logical address (page
no., offset) is identical
to its relative address
• Example
•
•
•
•
•
16-bit address
210 =1024-byte page
10-bit offset
6-bit page number
A maximum of 26 =64
pages
38
Paging
Logical to Physical Address Translation
Consider an address of n+m
bits, where the leftmost n bits
are the page no. and the
rightmost m bits are the offset
1. Extract the
page no.
2. Use the page no.
as an index into the
process page table
to find the frame
number, k
3. The physical address is constructed
by appending the offset to k
39
Segmentation
• A program can be subdivided into segments
– Segments may vary in length
– There is a maximum segment length
• Segmentation is similar to dynamic partitioning
– But, a program may occupy more than one partition
• No internal fragmentation but suffers from external
fragmentation (as does dynamic partitioning)
40
Segmentation
• A logical address consists of two parts
– a segment number and
– an offset
• There is a segment table for each process and a
list of free blocks of main memory.
• Each segment table entry would have to give
– the starting address in main memory of the
corresponding segment.
– the length of the segment, to assure that invalid
addresses are not used.
41
Segmentation
Logical Addresses
• There is no simple
relationship between a
logical address (segment
no., offset) and the
physical address
• Example
•
•
•
•
16-bit address
12-bit offset
4-bit segment number
maximum segment size=
212=4096
42
Segmentation
Logical to Physical Address Translation
Consider an address of n + m bits, where
the leftmost n bits are the segment no.
and the rightmost m bits are the offset
1.Extract the
segment no.
2.Use the segment no. as an
index into the process segment
table to find the starting physical
address of the segment
3. If the offset  the length of the
segment, the address is invalid
4.The physical address is the
sum of the starting physical
address of the segment plus
the offset
43