صفحه 1:
Memory Management
Chapter 7
صفحه 2:
Memory Management
° Subdividing memory to
accommodate multiple
processes
° Memory needs to be allocated
to ensure a reasonable supply
of ready processes to consume
available processor time
صفحه 3:
Memory Management
Requirements
° Relocation
~ Programmer does not know where the
program will be placed in memory
when it is executed
~ While the program is executing, it may
be swapped to disk and returned to
main memory at a different location
(relocated)
~ Memory references must be translated
in the code to actual physical memory
address
صفحه 4:
يط سس وي
لجنس بس ورين ‘arma
ين
=
co —|
Figure 7.1 Addressing Requirements for a Process
صفحه 5:
Memory Management
Requirements
* Protection
~ Processes should not be able to reference
memory locations in another process
without permission
~ Impossible to check absolute addresses at
compile time
Must be checked at rum time
~ Memory protection requirement must be
satisfied by the processor (hardware)
rather than the operating system (software)
* Operating system cannot anticipate all of the
memory references a program will make
صفحه 6:
Memory Management
Requirements
° Sharing
~ Allow several processes to access
the same portion of memory
~ Better to allow each process
access to the same copy of the
program rather than have their
own separate copy
صفحه 7:
Memory Management
Requirements
۰ Logical Organization
~ Programs are written in modules
~ Modules can be written and
compiled independently
~ Different degrees of protection
given to modules (read-only,
execute-only)
~ Share modules among processes
صفحه 8:
Memory Management
Requirements
° Physical Organization
~ Memory available for a program
plus its data may be insufficient
* Overlaying allows various modules to
be assigned the same region of
memory
~ Programmer does not know how
much space will be available
صفحه 9:
Fixed Partitioning
° Equal-size partitions
~ Any process whose size is less than
or equal to the partition size can be
loaded into an available partition
~ If all partitions are full, the
operating system can swap a
process out of a partition
- ۸۵ program may not fit in a partition.
The programmer must design the
program with overlays
صفحه 10:
Fixed Partitioning
° Main memory use is inefficient.
Any program, no matter how
small, occupies an entire
partition. This is called internal
fragmentation.
صفحه 11:
Operating Sytem ‘Operating System
3M 3M
2
aM 4M
om
aM
aM
aM
1"
1"
pM
aM
1"
tow
sM
(a) Equal-size partitions (Unequal size partitions
11
Figure 7.2 Example of Fixed Partitioning of a 64-Mbyte Memary
صفحه 12:
Placement Algorithm
with Partitions
° Equal-size partitions
~ Because all partitions are of equal size, it
does not matter which partition is used
* Unequal-size partitions
~ 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
12
صفحه 13:
13
(by Single quewe
New
(One proces queue per partition
Figure 73. Memory Assignment for Fixed Partitioning
New
صفحه 14:
Dynamic Partitioning
° Partitions are of variable length
and number
° Process is allocated exactly as
much memory as required
° Eventually get holes in the
memory. This is called external
fragmentation
* Must use compaction to shift
processes so they are contiguous
and all free memory is in one block
14
صفحه 15:
©
0
as
0
1
Figure 7.4 The Effect of Dynamic Partitioning
15
صفحه 16:
Dynamic Partitioning
Placement Algorithm
° 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
process, the smallest amount of
fragmentation is left
~ Memory compaction must be done more
often
16
صفحه 17:
Dynamic Partitioning
Placement Algorithm
° First-fit algorithm
~ Scans memory form the beginning
and chooses the first available
block that is large enough
~ Fastest
~ May have many process loaded in
the front end of memory that must
be searched over when trying to
find a free block
صفحه 18:
Dynamic Partitioning
Placement Algorithm
° Next-fit
~- Scans memory from the location of
the last placement
~ More often allocate a block of
memory at the end of memory
where the largest block is found
~ The largest block of memory is
broken up into smaller blocks
- Compaction is required to obtain a
large block at the end of memory
18
صفحه 19:
19
DD same
Ci sewn
Figure 7.8. Example Memory Configuration Before
and After Allocation of 16 Mbyte Block
صفحه 20:
Buddy System
° Entire space available is treated as
a single block of 2¥
° If a request of size s such that 2¥!
<s <= 2", entire block is allocated
~ Otherwise block is split into two equal
buddies
~ Process continues until smallest block
greater than or equal to s is
generated
20
صفحه 21:
21
۳۳۲999 مس
مور
Reps 20K
Request
Request 86K [REDER Ea] 2 ee
Rekase B [A= REKE-feK] 25685 1 ۳۰2565 ۲-2868 [
دسر
[ 208 1 02200 اک 1285۴105 12] 5 75 اممعاز
[ 28568 ۳۰2868 1 2568 | 1285 [۰1218] 6 اعم
Release E 2 [22252 1 OK
Figure 7.6 Example of Buddy System
صفحه 22:
22
Figure 7.7 Tree Representation of Buddy System
1"
256K
صفحه 23:
Relocation
When program loaded into memory the
actual (absolute) memory locations are
determined
A process may occupy different
partitions which means different
absolute memory locations during
execution (from swapping)
Compaction will also cause a program
to occupy a different partition which
means different absolute memory
locations
23
صفحه 24:
Addresses
* Logical
~ Reference to a memory location independent
of the current assignment of data to memory
~ Translation must be made to the physical
address
° Relative
~ Address expressed as a location relative to
some known point
* Physical
~ The absolute address or actual location in
main memory
24
صفحه 25:
Pressing
‘main mmr
Figure 7.8 Hardware Support for Relocation
25
صفحه 26:
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
صفحه 27:
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 not within
bounds, an interrupt is generated
to the operating system
صفحه 28:
Paging
° Partition memory into small equal fixed-
size chunks and divide each process
into the same size chunks
° The chunks of a process are called
pages and chunks of memory are called
frames
* Operating system maintains a page
table for each process
~ Contains the frame location for each
page in the process
~ Memory address consist of a page
number and offset within the page
28
صفحه 29:
Assignment of Process
Pages to Free Frames
صفحه 30:
Assignment of Process
Pages to Free Frames
Figure 7.9 Assignment of Process Pages to Free Frames
صفحه 31:
Page Tables for
Example
۰ عه 0 ers 17
1 1 1 1 14
2 208 209 2۳۶ سب یز
3 Process B يك i list
Process A page table ProcessC 4 LIZ
page table page table Process D
paige table
Figure 7.10 Data Structures for the Example of Figure 7.9 at Time Epoch (f)
31
صفحه 32:
Segmentation
° All segments of all programs do
not have to be of the same length
° There is a maximum segment
length
° Addressing consist of two parts -
a segment number and an offset
° Since segments are not equal,
segmentation is similar to
dynamic partitioning
صفحه 33:
Logical adress = Logical adress
eine athe «1502 0 م
1 4
5 i
8 14
k
7 8
دوه ae
Figure 7.11 Logical Addresses
33
صفحه 34:
جوا او ۱6
اس از # و ناگ
]01010101011 [6 12:12 ]2101111121110[
ee
Process
page tale
ی
]0151812121010121212151212111210[
0
(ay Paging
34
صفحه 35:
عت كلانه میا ۱
۳ سي ااه
1010101210 16 12 1011|11 11116 101010[
متس تسا مت
e اس سول
سیخ
[0]010]1[6101018] 1211 191610 6]011]
16-bit physical adress
Segamentation )(
Figure 7.12 Examples of Logical-to-Physical Address ‘Translation
35