1.

Operating Systems Concepts With Unix / Linux UNIT NO - 3

________________________________________________________________________________________________________
™ MEMORY MANAGEMENT

INTRODUCTION OF MEMORY MANAGEMENT:

We can improve CPU Utilization and speed of computer's response to its
users by allowing various processes to share CPU. But for this we must
keep several processes in memory; i.e. we must be able to share memory as
well. Selection of memory management method for a specific system
depends on many factors, especially on hardware design of system.
Memory is central to the operation of modern computer system. It consists
of a large array of words or bytes, each with its own address. CPU fetches
instruction from memory according to the value of program counter. The
normal procedure is to select one of the processes in the ready queue and
to load that process in memory. As the process is executed, it accesses
instruction and data from memory. Eventually the process terminates and
memory space is declared available.
™ Goals :
Historically, a number of different memory management
techniques have been used, and improved upon, in the operating
system. The principal goals of the operating system's memory
management are:
• To provide memory space to enable several processes to be
executed at the same time.
• To provide a satisfactory level of performance for the system
users.
• To support each program's resources.
• To share memory space between processes.
• To make the addressing of memory space as transparent as
possible for the programmer.
™ Protection :
Processes should not be able to reference the memory for another
process without permission. This is called memory protection, and
prevents some code in one program from interfering with the
operation of other running programs.
™ Sharing :
Even through the memory for different processes is protected from
each other different processes should be able to share information
and therefore access the same part of memory.
™ Memory Compaction :
The technique of relocating all occupied areas of memory to one
end of the memory so as to get one large block of free memory
space is called compaction.
Memory can be compacted under the following conditions:
• As soon as a job terminates
• When a new job cannot be loaded into memory due to
fragmentation
• At fixed time intervals
In the former case, the memory management is implemented directly by
the operating system. This can be done in two ways.
[1]. CONTIGUOUS MEMORY ALLOCATION:
[2]. NON-CONTIGUOUS MEMORY ALLOCATION:
________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
2. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________
CONTIGUOUS MEMORY ALLOCATION:
A programs data and instruction are assumed to occupy a single
contiguous area. The main memory should accommodate both the
operating system and the various user processes. The memory is usually
divided into two partitions, one for the resident operating system, and one
for the user processes. The operating system normally resides in the lower
memory area and the user programs in the higher regions. Contiguous
memory allocation can take place in two different ways.
™ Single-partition allocation:
™ Multi-partition allocation:

ƒ Single-partition allocation (Single Process Monitor):

This is the simplest memory management approach. The entire
memory is divided in two 2 sections – one for the programs of
operating system and the second for the user programs.

Operating System

User Program Fence Register

Figure: - Memory Layout – Single Partitioned allocation

The Operating system keeps track of only the lowest and

highest addresses available for the user programs. The location
of the operating system will be decided by the position of the
interrupt vector. Since the interrupt vector is generally
positioned at the low memory area, Operating system also
resides in the low area. Here, only one process (program)
resides in memory at a time. The process to be executed is
loaded into the free space area of the memory. In general, a part
of the memory space will be unused. Early MS-DOS systems
operated in this way. The main drawback of this allocation is an
External Fragmentation.
• Advantage:
o Simple and easy to implement.
• Disadvantages:
o Lower utilization of CPU.
o Memory wastage.
o Does not support multiprogramming.

ƒ Multi-partition Allocation:
In a multiprogramming environment several program
reside in primary memory at a time and the CPU passes its
control rapidly between these programs. Here the memory can
be divided into a number of separate fixed areas, each of which
can hold one process. When a program terminates, that
partition is free for another program waiting in a queue. The
main disadvantage of this allocation is an internal
fragmentation. There are two types of memory Partition.

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
3. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________
[a]. Fixed/Static Partition
[b]. Variable/Dynamic Partition

Operating System
P1
P2
P3
Free

[a]. Fixed/Static Partition:

Static partition implement the division of memory of
into fragments in a static manner, i.e. The size of each partition
will be fixed and is done in the beginning (during the system
generation process) and remains fixed thereafter. Each block is
allocated to a program. This scheme (called MFT – Multiple
Fixed Tasks) was originally used by the IBM OS/360
Operating system. In this example given below, the user area is
divided into fixed partition of 200K each. Three blocks have
been allocated to the programs P1, P2 and P3. First and fourth
block are free which can be allocated to other waiting
programs.

Operating System
FREE 200K
P1 200K
P2 200K
FREE
200K
P3 200K

Figure: Memory Allocation – Fixed Partition

Once the partitions are defined, operating system keeps track of the status of each
block (free or allocated) using a data structure called the Partition Description Table (PDT), as
shown below

Partition No Start address of partition Status

1 1000 Free
2 1200 Allocated
3 1400 Allocated
4 1600 Free
5 1800 Allocated
Figure: (PDT Partition Description Table)

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
4. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________
• Advantage:
o Simple and easy to implement.
o Less additional hardware required.
o Algorithm used is not very complicated.
• Disadvantages:
o Internal fragmentation of memory (memory
wastage inside the blocks).
o Degree of multiprogramming depends on the
number of partition.

[b]. Variable/Dynamic partition:

Variable partitioning (MVT – Multiple variable tasks),
0K
primarily used in a batch environment, implies the division of
memory of into fragments in a dynamic manner, i.e. the size of
each partitions will be variable depending on the size of the
program. Hence, the size and number of programs will be
decided during the run-time. As the programs enter the system,
they are put in the input queue. The operating system takes into
account of the memory requirements of each program and the
available free memory area to decide which programs are
allocated memory. When a program is allocated space, it is
loaded into the memory and then it can compute for CPU.
When the program terminates, it releases the memory that can
be given to another program. In general at any time, a set of the
free memory area of various sizes are scattered through out the
memory. When a program arrives, these sets of free memory
area are searched to find one that is large enough to satisfy the
request from the program.
40K
Process 5 Process 4 Process 3 Process 2 Process 1 SUPERVISOR

300K 150K 100K 250K 200K USER

640K PROGRAM

0 0 0
SUPERVISOR SUPERVISOR SUPERVISOR
40K 40K 40K Process4 (FREE 50K)
Process1 FREE (200K)
240K 240K 240K
490K Process2 490K Process2 Process2
490K
590K Process3 590K Process3 Process3
590K
640K FREE (50K) 640K FREE (50K) 640K FREE (50K)
0 0
SUPERVISOR SUPERVISOR
40K 40K
Process4 Process4
FREE (300K) Process5
Process3
FREE (150K)
640K FREE (50K) 640K

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
5. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________
Assume that we have 640K main memory available in which 40K is occupied by operating system
program. There are three jobs waiting for memory allocation in a job queue. Applying FCFS scheduling
policy, Process1, Process2 and Process3 can be immediately allocated in memory. Process 4 cannot be
allocated in memory because there is only 600-500 = 50K left for it. Let's assume that after some time
Process1 is terminated, now releasing 200K memory space. After than the control is returned to the process
queue and next Process4 is swapped - in the memory. After than Process2 going to terminated and release
250K free memory areas. 250K included with 50K internal fragmentation. Process5 be put up in released
300K external fragmentations. After the swapping out of Process3 due to termination, at last 100K of
external fragmentation merged and it will be distributed for next processes....

™ Memory Fragmentation :-
Fragmentation means an unusual space in memory areas or in
another word, presence of unusable memory areas in a
computer system. There two types of fragmentation arise in
system memory area...
ƒ Internal Fragmentation:
Internal fragmentation means unused internal area of program
in memory. It arises when memory allocated to a program is
not fully utilized by it.

SUPERVISOR
Program1
Internal Fragmentation
Free
Program2

Program3

ƒ Internal Fragmentation:
After sharing memory for programs, if some part of memory
can go free, called it External fragmentation. It arises when free
memory areas existing in a system are too small to be allocated
to programs. Example of external fragmentation like...
SUPERVISOR
Program1
Program2
External Fragmentation
Free
Program3

™ Memory Fragmentation Handling Techniques:

How To Avoid / Overcome / Eliminate Memory
Fragmentations:
Fragmentation means remain unused area of a memory. This is
already reallocated for specific program. There are some
techniques that can be used to avoid the memory fragmentation
problem.

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
6. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________
ƒ Merging Free Areas OR Memory / Storage Compaction
In this approach memory allocation are changed such that all
free areas can be combined into a single free area called the
merged free area. This is done by combined into a single free
area called the merged free area. This is done by allocating
alternative memory areas to programs and data existing in the
allocated areas of memory. All fresh allocations are made from
the merged free area. In another word, an Operating system
may attempt to combine all free areas into a single free area, or
to combine some adjoining free areas into a free area of larger
size.
0K 0K
SUPERVISOR SUPERVISOR
40K 40K
Process1 Process1
(200K) (200K)
240K 240K
FREE 30K Process2
270K
Process2 (100K)
340K
(100K)
370K After Compaction Process3
FREE 20K (70K)
390K
Process3 410K FREE 50K
(70K)

460K 460K

™ Memory Placement Policy OR Free Partition Allocation

technique
When new processes have to be loaded using the variable partition
scheme. It is necessary to try to select the "best" locations in which
to place them. An algorithms used for this purpose is termed a
placement policy.
There are three types of placement policy:
ƒ Best-Fit Policy:
An incoming process is placed in partition, which is the
smallest free partition with its incoming processes...
ƒ First-Fit Policy:
An incoming process is placed in the first available partition,
which can put up it.
ƒ Worst-Fit Policy:
An incoming process is placed in the partition, which leaves the
maximum amount of unused space – which logically must be
the current largest hole/partition.
In the given policies, Best-Fit and Worst-Fit policies
are considered best. Best-Fit appear that minimum space is
wasted. By contrast, Worst fit doesn't look too promising.
However, worst fit in trying to minimize the unused could
create a hole too small to be useful. So it is not as clear-cut as it
first appears. In the practice, the best fit and first fit generally
prove to be the most effective.

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
7. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________

SUPERVISOR
Program1

Program2
Program6
FREE 100K
Program3 First-Fit
........ 150K
FREE 300K
Best-Fit
READY QUEUE Program4
FREE 200K
Worst-Fit

FREE 400K

NON-CONTIGUOUS MEMORY ALLOCATION:

™ INTRODUCTION:
At any given time, we have a list of available block sizes and the ready
queue. Operating system can order the ready queue according to some
scheduling algorithm. Generally, a set of free partition areas of various
sizes is scattered throughout the memory at any given time. When a
process terminates, it releases its block of memory, which is that
placed back in the set of free partition area. If the new free partition
area to other merged from one larger free partition area. The system
can used dynamic storage allocation method, First Fit, Best Fit, Worst
Fit for allocating memory but this algorithm suffer from external
fragmentation. As process from memory the free memory space is
broken into little pieces.

External fragmentation occurs when enough total memory space exists

to satisfy a request but it is not contiguous. The solution to external
fragmentation is compaction. The idea is memory contains to place all
free memory together in one large block. Compaction is possible only
if reallocation is dynamic & is done
at execution time.
Another solution to external fragmentation is to permit
logical address space of a process to be non-contiguous, allowing a
process to be allocated physical memory. There are two techniques
using non-contiguous memory allocation.
- Paging
- Segmentation
™ LOGICAL AND PHYSICAL ADDRESS:
Base 1400
Register
CPU Memory
+
Logical Address Physical Address
________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
8. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________
A logical address is the address of an instruction
used by a program. it may be obtain using Index, base register or
segment register. A physical address is the effective memory address
of an instruction for data word. That physical address obtains with
Logical Address + Base Register. The run time mapping of virtual
memory (physical) addresses is done by hardware device called
Memory Management Unit (MMU). It makes use of a register called a
base register. The value in the base register is added to every address
generated by any user processes.

™ VIRTUAL MEMORY USING PAGING / PAGING

CONCEPT:
Paging is a memory management scheme that permits a physical
address space of a process to be non-contiguous. Physical memory
is broken into fixed-sized blocks called frames. Logical memory is
also broken into blocks of same size called pages. When a process
is to be executed, its pages are loaded into any available memory
frames from the backing store.

Page
0
Frame
Page 0 Page 0
0 1 1
Page 1 1 1
2
2 1 Page 2
Page 2 3
3 1
Page 1
Page 3
Page Table 4
5
Logical memory
Page 3
6
Physical memory

Figure: paging model of logical & physical memory

Every address generated by CPU is divided into a parts page

number (p) and page offset (d).

Page Number Page Offset

P1 P2 d

The page number is used and index into a page table.

The page table contains the base address of each page in physical
memory. This base address is combining with the page offset to define
the physical memory address that is sent to memory unit. Consider the
example given below.

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
9. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________

Page
0 a 0 0
Frame
1 b
0 i
2 c 4 j 1
3 d
0 5 k
4 e l
1 6
5 f
1 2 1 m
6 g 8
3 2 n
7 h
o 2
8 i Page Table 12
p
9 j 16
2
10 k 3
11 l
20 4
12 m
a
13 n
3 b
14 o
24 c
15 p 5
d
Logical memory e
f
g 6
h

Physical memory

Figure: Paging model of physical or logical memory

When we use paging we have no external fragmentation. Any free

frame can be allocated to a process that needs it. But we may have
some internal fragmentation. Since frames are allocated as units
and memory requirements of a process do not always falls on page
boundaries. The last frame allocated may not be completely full.
The important aspect of paging is the clear distinction between
user's view of memory and actual physical memory. The user
program views that memory as one signal contiguous space,
containing only this one program. In fact the user program is
scattered throughout physical memory, which also holds another
programs. The logical addresses are converted to physical
addresses. This mapping is hidden from user and controlled by
operating system. The process has no way of accessing memory
outside of its page table, and the table includes only those pages
that the process owns.

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
10. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________

Memory protection in a paged environment is accomplished by

assigning protection bits with each frame. One bit can define a
page to be read-write or read only. These bits are kept in page
table. Every reference to memory goes through the page table to
find the correct frame number. Page Table Length Register (PTLR)
can be used which indicates the size of page table. This value is
checked against every logical address to verify that the address is
in the valid range for the process.
Some common techniques for structuring page table are as
follows:
• Hierarchical Paging
When page table becomes large, allocating contiguous
space to page table in main memory may feasible. In this
case we can divide page table into smaller pieces. One way
for this division is two used at two level paging algorithms.
In which page table it also paged as shown below...

0
1

1 .
.
.
.
100
500
.
.
100
. 500
.
.
.
. 708 .

929 708
.
Outer Page Table .
.
.

900 900
.
.

929
.
.
Page of Page Table

Memory

Figure: 2 – Level Page Table Scheme

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
11. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________

™ VIRTUAL MEMORY USING SEGMENTATION

TECHNIQUES:
Segmentation is a memory management skill where a logical
address specifies both segment name and offset within the segment,
where in paging user specifies only single address which is
partition by hardware into page number, all invisible to
programmer.
Each entry of segment table has a segment base and limit segment
base contains physical address of starting where the segment
resides in memory, where segment limit specified the length of the
segment.

Stack 1400
Subroutine Segment 0
Segment 3 2400
Segment 0
Program 1 3200 Segment 3
SQRT 4300
Segment 4 4700 Segment 2

Segment 1 Segment 4
Main Program 5700

Segment 2 6300
Segment 1
6700
SEGMENT TABLE

Limit Base
0
1000 1400
1 400 6300
2 400 4300
3 1100 3200
4 1000 4700

Figure: Segmentation using virtual memory

If the segments are very large, it becomes in convenient or

sometimes impossible to keep them in main memory entirely. Then
we can page the segments so that only those pages that are actually
needed can be kept. The concept is called as segmentation with
paging / page segment. A segment description contains an
indication of whether the segment is in main memory or not. The
address consists of two parts, segment name and address within the
segment.

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
12. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________
When a memory reference occurs following algorithm is carry
out.
- The segment number is used to find the segment description
- A check is made to see if the segment page table is in
memory. If the page table is in memory, it is located. If is
not, a segment fault occurs. If there is a protection
violation, a trap occurs.
- The page table entry for the requested virtual page is used.
If it is in memory, the main memory address of the start of
the page is extracted from page table entry.
- The offset is added to page origin to give the main memory
address where the word is located.
- The read or store finally takes place.

™ Page Fault :
A field in the PMT (Page Map Table) entry of page Pi indicates
whether the page currently exits in memory. If Pi does not exit in
memory when reference ALU declares a missing page interrupt
also called a PAGE FAULT.

Pi Wi

15 479
MR BLOCK OTHER
NO INFO
Add 15 479 # ??

Page Map Table (PMT)

Page Fault

Physical Memory

Page fault information transfer to the virtual memory handler for

necessary action. The following actions are taken by the operating
system in case of page fault occurs.
ƒ If a process refers to a page which is not in physical memory
then an internal table kept with a process to verify whether a
memory valid or invalid.
ƒ If the memory reference to a page of valid but the page is
missing, the process of bringing a page into the physical
memory starts
ƒ Free memory location is identified to bring a missing page
ƒ Restart the instruction that was interrupted due to the missing
page.

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli
 13. Operating Systems Concepts With Unix / Linux UNIT NO - 3
________________________________________________________________________________________________________

Operating System
Page Fault
Memory Reference to a Page
Secondary
CPU PMT Memory
Load Pi Physical Memory

Missing
Restart Instruction
Page is
FREE
Update brought
PMT Free memory location

™ Demand Paging :
All pages of program can be loaded in memory before the program
is initiated. This is called Pre- Loading of Paging. In demand
paging, pages are loaded only on demand not in advanced. It is
similar to paging system with swapping futures. Rather than
swapping the entire program in memory, only those pages are
swapped which are required currently by the system.

` Operating System
Page Fault
Memory Reference to a Page
Secondary
CPU PMT Memory
Load Pi Physical Memory

Restart Instruction Demand

Page is
FREE
Update brought
PMT

Figure: Demand Paging

If page is not in physical memory it means "Page Fault" situation.

If a program during execution never accesses the page, which is
marked "No". The Operating system must arrange to load this page
in memory. Thus a page is loaded on demand (Called Demand
Paging).

________________________________________________________________________________________________________
Kamani Science College (Computer Department), Amreli