Transcript OperatingSystems-Lecture8

Operating System Concepts and Techniques
Lecture 8
Memory Management-1
M. Naghibzadeh
Reference
M. Naghibzadeh, Operating System Concepts and Techniques, First ed., iUniverse Inc., 2011.
To order: www.iUniverse.com, www.barnesandnoble.com, or www.amazon.com
Memory Management (MM)
Memory management policies and
techniques have tremendously changed
throughout the years
The simplest being single contiguous
partition memory management
The most complex being multilevel-page
table virtual memory with cache
A Brief list follows
2
A Brief list of MM policies
Old policies
Single contiguous partition MM
Static partition MM
Dynamic partition MM
Multiple partition MM
Middle age policies
Segmentation MM
Relocatable partition MM
Page (non-virtual memory) MM
Virtual memory policies
Page-based virtual memory MM
Multilevel page table page-based
virtual memory MM
3
Single contiguous partition MM
MM is divided into two parts
One part for operating system
The other is called user memory
So simple that there is no MM subsystem, loader
takes care of it
Make sure user program does not destroy OS
Many disadvantages
Supports only single-programming
System utilization is very low
Waste of memory for small programs
A program larger than the user’s main memory will not
be able to run
4
Static Partition MM
More than one user partition with fixed sizes
Sizes are different to reduce memory waste and
accept larger programs
Make sure user programs do not interfere and do not
destroy OS
Number of partitions determines degree of
multiprogramming
Advantages
Simple to implement; a table for partitions information
Multiprogramming is possible
the size of runable programs limited to the largest partition size
Memory waste
A program larger than users main memory will not be able to run
5
Dynamic Partition MM
More than one user partition with variable sizes
Sizes are different to reduce memory waste and accept larger
programs
Make sure user programs do not interfere and do not destroy OS
Number
of
partitions
determines
the
degree
of
multiprogramming
At start there is only one big free partition
When new programs are accepted new partitions are created
Upon program completion free neighbor partitions can join
Advantages
Simple to implement; two tables, free and allocated partitions
Multiprogramming is possible
The size of a runable programs limited to the size of user memory
A program larger than users main memory will not be able to run
6
Dynamic Partition Memory waste
There is a smallest memory allocation unit,
usually 1K bytes

A program which is 1025 bytes will be given 2K
bytes, 1023 bytes are wasted in the form of
internal fragmentation
We are not allowed to relocate programs
External fragmentation occurs when all free
memory partitions combined are large enough
to load the coming program into, but these
spaces do not form a contiguous partition and
each one cannot accept the coming program
7
Dynamic Partition Memory waste…
The 50% rule: Without other information, on
the average, the number of free partitions is
half the number of allocated partitions

Remember: adjacent free partitions join, but
adjacent occupied partitions house different
programs
Let C = (average free partition size)/(average program size), then
C
external fragmentation fraction= C  2
8
Partition allocation
First-Fit

Look at the free partitions data structure (not the main
memory itself) and select the first which is as large as the
program
Next-Fit

From partitions data structure, from where the pointer
points, select the first which is as large as the program
Best-Fit

pick a qualified partition whose size is closest to the size of
the program
Worst-Fit

Pick the largest free partition
9
Partition allocation- Buddy syatem
The size of a partition is 2i*m
A partition size of 2i*K could split into two size 2i-1*K
which are called buddies
Remember that any two partition of size 2i*m are not
buddies even if they are adjacent
A complete partition is given to a program
Remember partitions cannot start from any arbitrary
address
A program the size of xK is given a partition of size
2i*K, where 2i  x and i is the smallest such integer
Any two free buddies have to merge
10
Buddy system tree
512M
256M
128M
64M
32M
: Processed
: Allocated
: Available
Figure shows certain state of a small 512 Mega Bytes (MB) main
memory. A black circle represents a partition that has been broken and
no longer exists. Dark circles represent a partition that is occupied by a
program. An unfilled circle represents a free (available) partition
Advantage: easy to find a partition for a program
Disadvantage: Internal fragmentation increases
11
Summary
There are variety of memory management


The simplest, single contiguous memory management
The most complex, multilevel page table page-based virtual
memory with segmentation and cache memory
Older managements are good for special purpose
computer such as embedded control systems and
intelligent machinery electronics
This lecture introduced static and dynamic partition
memory managements
Base register is a central concept to dynamic partition
MM
12
Find out
What the degree of multiprogramming is in your
computer
Practical systems which use single partition MM
If we can have a buddy system in which buddies are
not the same size
In buddy system, why can’t any two adjacent
partitions the size of 2i*K, join to form a partition the
size of 2i+1*K
In what situations worst-fit will perform better than
other partition selection algorithms
13
Any questions?
14