Opesys2 04
Opesys2 04
Opesys2 04
Memory Management 1
A user process may reside in any part of the physical
memory. Thus, although the address space of the
computer starts at 0, the first address of the user
process does not need to be 0.
Source
Program
Compiler or compile
Assembler time
Object
Other Module
Object
Modules
Linkage
Editor
Load load
Module time
System
Library
Loader
Dynamically
Loaded
System
Library
Memory Management 2
Addresses in a source program are generally symbolic
(such as LOC or ALPHA). A compiler will typically
bind these symbolic addresses to relocatable addresses
(such as 14 bytes from the beginning of a certain
module). The linker editor or loader will then bind
the relocatable addresses to absolute addresses (such as
18000H). Each binding is a mapping from one address
space to another.
Memory Management 3
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
scheme to work. Most general-purpose operating
systems use this method.
Memory Management 4
LOGICAL AND PHYSICAL ADDRESS SPACE
logical physical
address address
CPU MEMORY
Memory Management 5
The run-time mapping from logical to physical
addresses is done by a hardware device called the
memory-management unit (MMU).
Relocation
Register
14000
logical physical
address address
CPU + MEMORY
346 14346
MMU
Memory Management 6
Notice that the user program never sees the real
physical addresses. The program can create a pointer
to location 346, store it in memory, manipulate it,
compare it to other addresses – all as the number 346.
Only when it is used as a memory address is it
relocated relative to the base register.
Memory Management 7
SWAPPING
OPERATING
SYSTEM
SWAP OUT
PROCESS
P1
PROCESS
P2
SWAP IN
USER
SPACE SECONDARY STORAGE
MAIN MEMORY
Memory Management 8
Take note that the quantum must be sufficiently large
that reasonable amounts of computing are done
between swaps.
Example:
Memory Management 9
Swapping is constrained by other factors as well. A
process to be swapped out must be completely idle.
Memory Management 10
MULTIPLE PARTITIONS
OPERATING
SYSTEM
PROCESS 1
PROCESS 2
PROCESS 3
Memory Management 11
There are two major memory management schemes
possible in handling multiple partitions:
Example:
Example:
As jobs enter the system, they are put into a job queue.
The job scheduler takes into account the memory
requirements of each job and the available regions in
determining which jobs are allocated memory.
Memory Management 12
Example:
0
OPERATING
12K
SYSTEM
USER PARTITION 1 2K
USER PARTITION 2 6K
32K
Memory Management 13
Example:
0
OPERATING
12K
SYSTEM
5 4 3 2 1
USER PARTITION 1 2K
... 7K 7K 3K 2K 5K
USER PARTITION 2 6K
JOB QUEUE
32K
Memory Management 14
One flaw of the best-fit only algorithm is that it forces
other jobs (particularly those at the latter part of the
queue to wait even though there are some free memory
partitions).
Possible Solutions:
Memory Management 15
3. MFT results in internal and external
fragmentation which are both sources of memory
waste.
Memory Management 16
Example:
4 3 2 1
4K
USER PARTITION 2
... 6K 6K 3K 7K
4K
JOB QUEUE
USER PARTITION 3
4K
USER PARTITION 4
I.F. = (10 K - 7 K) + (4 K - 3 K)
= 4K
E.F. = 8K
Therefore:
Memory Management 17
Variable Partitions (MVT)
Example:
Memory Management 18
Example Memory Allocation and Job Scheduling for
MVT
0 0 0
OS OS OS
Job 5
Job 1 Job 1 Job 1 out, Job 5 in after
next 5 time units
90K
100K 100K 100K
Job 4 Job 4
Job 2 out, Job 4 in after
Job 2 5 time units
170K 170K
Memory Management 19
This example illustrates several points about MVT:
Memory Management 20
3. If the hole is too large for a job, the system splits
it into two: the operating system gives one part to
the arriving job and it returns the other the set of
holes.
Memory Management 21
The solution to this problem is compaction. The goal
is to shuffle the memory contents to place all free
memory together in one large block.
Example:
0 0
OS OS
40K 40K
Job 5 Job 5
90K 90K
10 K
100K
Job 4
Job 4
160K
170K Job 3
30 K 190K
200K
Job 3
66 K
230K
26 K
256K 256K
Memory Management 22
PAGING
Memory Management 23
If the size of a process (its logical address space) is 2m,
and a page size is 2n addressing units (bytes or words),
then the high-order m – n bits of a logical address
designate the page number, and the n lower-order bits
designate the page offset. Thus, the logical address is
as follows:
page number page offset
p d
m-n n
Example:
Memory Management 24
The operating system translates this logical address
into a physical address in main memory where the
word actually resides. This translation process is
possible through the use of a page table.
logical physical
address address
Main
CPU p d f d
Memory
p
f
page table
Memory Management 25
Example:
frame
page 0 number 0
0 1
page 1 1 page 0
1 4
2 3
page 2 2
3 7
page 3 3 page 2
Page Table
Logical 4 page 1
Memory
5
7 page 3
Physical
Memory
Memory Management 26
0 a 0
1 b 1
Page 0 Frame 0
2 c 2
3 d 3
4 e 0 5 4 i
5 f 1 6 5 j
Page 1 Frame 1
6 g 6 k
2 1
7 h 7 l
3 2
8 i 8 m
9 j 9 n
Page 2 Page Table Frame 2
10 k 10 o
11 l 11 p
12 m 12
13 n 13
Page 3 Frame 3
14 o 14
15 p 15
Logical 16
Memory 17
Frame 4
18
19
20 a
21 b
Frame 5
22 c
23 d
24 e
25 f
Frame 6
26 g
27 h
28
29
Frame 7
30
32
Physical
Memory
Memory Management 27
Main Memory Size = 32 bytes
A4 A3 A2 A1 A0
A3 A2 A1 A0
page page offset
number
Memory Management 28
logical memory physical memory
0000 a 00000
0001 b 00001
page 0 frame 0
0010 c 00010
0011 d 00011
0100 e 00100 i
0101 f 00101 j
page 1 frame 1
0110 g 00110 k
0111 h 00111 l
1000 i 01000 m
1001 j 01001 n
page 2 frame 2
1010 k 01010 o
page table
1011 l 01011 p
1100 m 00 101 01100
1101 n 01 110 01101
page 3 frame 3
1110 o 10 001 01110
1111 p 11 010 01111
10000
10001
frame 4
10010
10011
10100 a
CPU sends logical address 01 01 10101 b
frame 5
10110 c
That address is translated to 10111 d
physical address 110 01
11000 e
11001 f
frame 6
11010 g
11011 h
11100
11101
frame 7
11110
11111
Memory Management 29
There is no external fragmentation in paging since the
operating system can allocate any free frame to a
process that needs it. However, it is possible to have
internal fragmentation if the memory requirements of a
process do not happen to fall on page boundaries. In
other words, the last page may not completely fill up a
frame.
Example:
Memory Management 30
Each operating system has its own methods for storing
page tables. Most allocate a page table for each
process. A pointer to the page table is stored with the
other register values (like the program counter) in the
PCB. When the dispatcher is told to start a process, it
must reload the user registers and define the correct
hardware page-table values from the stored user page
table.
Memory Management 31
3. Associative Registers
Memory Management 32
Another advantage in paging is that processes can
share pages therefore reducing overall memory
consumption.
Example:
Memory Management 33
SEGMENTATION
Logical Memory
stack
subroutine
symbol
table
Sqrt
main
program
Memory Management 34
Each of these segments is of variable-length; the size is
intrinsically defined by the purpose of the segment in
the program. The user is not concerned whether a
particular segment is stored before or after another
segment. The OS identifies elements within a segment
by their offset from the beginning of the segment.
Example:
Example:
Memory Management 35
The mapping of logical address into physical address is
possible through the use of a segment table.
limit base
CPU (s, d)
true
d < limit ? + to MM
false
Memory Management 36
Example:
1400
segment 0
stack 2400
segment 3
subrouti limit base
ne symbol 0 1000 1400
table 3200
1 400 6300
2 400 4300
segment 0 segment 4 segment 3
3 1100 3200
Sqrt main 4 1000 4700
program 4300
segment 2
SEGMENT 4700
TABLE
segment 1 segment 2 segment 4
5700
segment 1
6700
PHYSICAL
MEMORY
Memory Management 37