Chap 7
Chap 7
Chap 7
Chapter 7
1
Memory Management
3
Memory Management Requirements
Relocation
programmer cannot know where the program
will be placed in memory when it is executed
a process may be (often) relocated in main
memory due to swapping
swapping enables the OS to have a larger pool
of ready-to-execute processes
memory references in code (for both
instructions and data) must be translated to
actual physical memory address
4
Memory Management Requirements
Protection
processes should not be able to reference
memory locations in another process without
permission
impossible to check addresses at compile time
in programs since the program could be
relocated
address references must be checked at run
time by hardware
5
Memory Management Requirements
Sharing
mustallow several processes to access a
common portion of main memory without
compromising protection
cooperating processes may need to share
access to the same data structure
better to allow each process to access the same
copy of the program rather than have their own
separate copy
6
Memory Management Requirements
Logical Organization
userswrite programs in modules with different
characteristics
instruction
modules are execute-only
data modules are either read-only or read/write
7
Memory Management Requirements
Physical Organization
secondary memory is the long term store for
programs and data while main memory holds
program and data currently in use
moving information between these two levels of
memory is a major concern of memory
management (OS)
itis highly inefficient to leave this responsibility
to the application programmer
8
Simple Memory Management
In this chapter we study the simpler case where
there is no virtual memory
An executing process must be loaded entirely in
main memory (if overlays are not used)
Although the following simple memory
management techniques are not used in modern
OS, they lay the ground for a proper discussion of
virtual memory (next chapter)
fixed partitioning
dynamic partitioning
simple paging
simple segmentation
9
Fixed Partitioning
Partitions can be of
equal or unequal sizes
10
Fixed Partitioning
any process whose size is less than or equal to a
partition size can be loaded into the partition
if all partitions are occupied, the operating system
can swap a process out of a partition
a program may be too large to fit in a partition.
The programmer must then design the program
with overlays
when the module needed is not present the user
program must load that module into the program’s
partition, overlaying whatever program or data are
there
11
Fixed Partitioning
Main memory use is inefficient. Any
program, no matter how small, occupies an
entire partition. This is called 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)
12
Placement Algorithm with Partitions
Equal-size partitions
If
there is an available partition, a process can
be loaded into that partition
because all partitions are of equal size, it does
not matter which partition is used
Ifall partitions are occupied by blocked
processes, choose one process to swap out to
make room for the new process
13
Placement Algorithm with Partitions
Unequal-size
partitions: use of
multiple queues
assign each process to
the smallest partition
within which it will fit
A queue for each
partition size
tries to minimize
internal fragmentation
Problem: some queues
will be empty if no
processes within a size
range is present
14
Placement Algorithm with Partitions
Unequal-size
partitions: use of a
single queue
When its time to load a
process into main
memory the smallest
available partition that
will hold the process is
selected
increases the level of
multiprogramming at the
expense of internal
fragmentation
15
Dynamic Partitioning
Partitions are of variable length and number
Each process is allocated exactly as much
memory as it requires
Eventually holes are formed in main
memory. This is called external
fragmentation
Must use compaction to shift processes so
they are contiguous and all free memory is
in one block
Used in IBM’s OS/MVT (Multiprogramming
with a Variable number of Tasks)
16
Dynamic Partitioning: an example
20
Replacement Algorithm
21
Buddy System
A reasonable compromize to overcome
disadvantages of both fixed and variable
partitionning schemes
A modified form is used in Unix SVR4 for
kernal memory allocation
Memory blocks are available in size of
2^{K} where L <= K <= U and where
2^{L}= smallest size of block allocatable
2^{U} = largest size of block allocatable
(generally, the entire memory available)
22
Buddy System
We start with the entire block of size 2^{U}
When a request of size S is made:
If 2^{U-1} < S <= 2^{U} then allocate the entire
block of size 2^{U}
Else, split this block into two buddies, each of size
2^{U-1}
If 2^{U-2} < S <= 2^{U-1} then allocate one of the
2 buddies
Otherwise one of the 2 buddies is split again
This process is repeated until the smallest block
greater or equal to S is generated
Two buddies are coalesced whenever both of
them become unallocated
23
Buddy System
25
Buddy Systems: remarks
On average, internal fragmentation is 25%
each memory block is at least 50% occupied
Programs are not moved in memory
simplifies memory management
Mostly efficient when the size M of memory
used by the Buddy System is a power of 2
M = 2^{U} “bytes” where U is an integer
then the size of each block is a power of 2
the smallest block is of size 1
Ex: if M = 10, then the smallest block would be
of size 5
26
Relocation
27
Address Types
A physical address (absolute address) is a
physical location in main memory
A logical address is a reference to a
memory location independent of the
physical structure/organization of memory
Compilers produce code in which all
memory references are logical addresses
A relative address is an example of logical
address in which the address is expressed
as a location relative to some known point
in the program (ex: the beginning)
28
Address Translation
Relative address is the most frequent type
of logical address used in pgm modules
(ie: executable files)
Such modules are loaded in main memory
with all memory references 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
29
Simple example of hardware
translation of addresses
When a process is assigned to the running state, a
base register (in CPU) gets loaded with the
starting physical address of the process
A bound register gets loaded with the process’s
ending physical address
When a relative addresses is encountered, it is
added with the content of the base register to
obtain the physical address which is compared
with the content of the bound register
This provides hardware protection: each process
can only access memory within its process image
30
Example Hardware for Address Translation
31
Simple Paging
32
Example of process loading
33
Example of process loading (cont.)
When process A and C
are blocked, the pager
loads a new process D
consisting of 5 pages
Process D does not
occupied a contiguous
portion of memory
There is no external
fragmentation
Internal fragmentation
consist only of the last
page of each process
34
Page Tables
38
Logical-to-Physical Address
Translation in Paging
39
Simple Segmentation
Each program is subdivided into blocks of
non-equal size called segments
When a process gets loaded into main
memory, its different segments can be
located anywhere
Each segment is fully packed with
instructs/data: no internal fragmentation
There is external fragmentation; it is
reduced when using small segments
40
Simple Segmentation
In contrast with paging, segmentation is
visible to the programmer
provided as a convenience to organize logically
programs (ex: data in one segment, code in
another segment)
must be aware of segment size limit
41
Logical address used in segmentation
When a process enters the Running state, a CPU
register gets loaded with the starting address of
the process’s segment table.
Presented with a logical address (segment
number, offset) = (n,m), the CPU indexes (with n)
the segment table to obtain the starting physical
address k and the length l of that segment
The physical address is obtained by adding m to k
(in contrast with paging)
the hardware also compares the offset m with the length
l of that segment to determine if the address is valid
42
Logical-to-Physical Address
Translation in segmentation
43
Simple segmentation and paging
comparison
Segmentation requires more complicated
hardware for address translation
Segmentation suffers from external fragmentation
Paging only yield a small internal fragmentation
Segmentation is visible to the programmer
whereas paging is transparent
Segmentation can be viewed as commodity
offered to the programmer to organize logically a
program into segments and using different kinds
of protection (ex: execute-only for code but read-
write for data)
for this we need to use protection bits in segment
table entries
44