36 fragmentaio nnd pageconcepts

1. 1
•Fragmentation
•Paging concepts
Storage Management

2. 2
HOME PREVIOUS TOPIC NEXT
PREVIOUS QUESTION PAPERS FOR OS
CPP TUTORIALS

3. 3
Recap
In the last class, you have learnt
Multiple partition allocation
Allocation of memory

4. 4
Objectives
On completion of this class, you will be able to
know
• Fragmentation
- External
- Internal
• Paging concepts

5. 5
Free Space
0k
4k
16k
64k
128k
Multiprogramming with Fixed Partitions
•Divide memory into n
(possible unequal)
partitions
•Problem:
–Fragmentation
OS
P1
P2
P3
Memory

6. 6
External Fragmentation
•Enough total memory
exists to satisfy a
request
•But not contagious
•Results in external
fragmentation
•Ex: Process size
P1=600K, P4= 700K,
P3=300K, P5= 500K
Free Space
400k
1000k
1700k
2560k
2000k
2300k
Operating
System
P1
P4
P3
560K
0k
Memory

7. 7
Internal
fragmentation
(cannot be
reallocated)
P1
P2
Free Space
18,464
Bytes
P3
OS
Fixed Partitions
Ex. A Hole Size is
18,464 bytes
Process P3 request
is 18,462 bytes
Allocate the request
Hole of two bytes is
left (Internal
Fragmentation)
Memory

8. 8
Fragmentation
•Disadvantage
–Block of free memory between two process can not
be used for executing the process
–Which end of the free block is allocated (top or
bottom)
–If all free blocks of memory were together several
more process can be executed

9. 9
How Bad Is Fragmentation?
•Statistical arguments - Random sizes
•First-fit, Best-fit, Worst-fit
•Given N allocated blocks
•0.5*N blocks will be lost because of fragmentation
•Known as 50% RULE

10. 10
Solution to External Fragmentation
Compaction
Shuffle memory contents to place all free memory
together in one large block as shown in slide no. 11
Compaction is not always possible
If relocation is static and is done at assembly or
load time compaction is not possible

11. 11
Solution to External Fragmentation
Compaction is possible only if relocation is
dynamic and is done at execution time
I/O problem
Latch job in memory while it is involved in I/O
Do I/O only into OS buffers

12. 12
Solution to External Fragmentation
•Compaction
Monitor Job 3 FreeJob 5 Job 6Job 7 Job 85
Monitor Job 3 FreeJob 5 Job 6Job 7 Job 86
Monitor Job 3 FreeJob 5 Job 6Job 7 Job 87
Monitor Job 3 FreeJob 5 Job 6Job 7 Job 88
Monitor Job 3 FreeJob 5 Job 6Job 7 Job 89

13. 13
Internal fragmentation
Want to also avoid internal fragmentation?
Memory is handed out in some fixed way (Power
of 2 for instance)
and requesting program doesn't use it all

14. 14
Storage Management Problems
•Fixed partitions suffer from
–Internal fragmentation
•Variable partitions suffer from
–External fragmentation
•Compaction suffers from
–Overhead

15. 15
Paging
•Possible solution to the external fragmentation is
use of Paging scheme
•Paging avoids the problem of fitting varying-sized
memory chunks on to backing store
•We don’t need to assign contiguous memory
chunks
•Internal fragmentation can only occur on the last
page assigned to a process

16. 16
Paging
•Logical address space of a process can be
noncontiguous
•Process is allocated to physical memory whenever
the latter is available
•Divide physical memory into fixed-sized blocks called
frames
–Ex: size is power of 2, between 512 bytes and 8,192 bytes
•Divide logical memory into blocks of same size
called pages

17. 17
•Keep track of all free frames
•To run a program of size n pages, need to find n
free frames and load program
•Set up a page table to translate logical to
physical addresses
•Internal fragmentation
Paging

18. 18
Paging Hardware

19. 19
Address Translation Scheme
•Address generated by CPU is logical address
–is divided into two parts as shown in next slide
–Page number (p) – used as an index into a page table
which contains base address of each page in physical
memory
–Page offset (d) – combined with base address to
define the physical memory address that is sent to the
memory unit
–for given logical address space 2
m
and page size

2
n
page number page offset
p d
m - n n

20. 20
Paging Hardware
p d f d
Logical
address
Physical
address
CPU
Physical
Memory
Page table
p

21. 21
Paging Model of Logical and Physical
Memory

22. 22
Paging Model of Logical and Physical
Memory
•Example: mapping of user view of memory to
physical memory
–Page size of 4 bytes
–Physical memory of 32 bytes ( 8 pages )
–Logical address 0, page 0, offset 0
–Indexing into page table, we get page 0 is in frame 5
–Logical address 0 maps to physical address
20(=(5X4)+0)

23. 23
Paging Example
32-byte memory and 4-byte pages

24. 24
Summary
In this class, you have learnt
•Fragmentation
•Paging concepts

25. 25
Frequently Asked Questions
1.What is external fragmentation?
2.What is internal fragmentation?
3.Define a page and a frame
4.Explain the paging hardware with a neat
diagram

26. 26
Quiz
1. Enough total memory exists to satisfy a
request but not contagious results in
a) External fragmentation
b) Internal fragmentation
C) None

27. 27

2.Shuffling memory contents to place all free
memory together in one large block is called
a) Fragmentation
b) Hole
c) Compaction
d) None
Quiz

28. 28
Quiz
3. Fixed partitions suffer from
a) External fragmentation
b) Internal fragmentation
c) Compaction
d) None

29. 29
Quiz
4. Variable partitions suffer from
a) External fragmentation
b) Internal fragmentation
c) Compaction
d) None

30. 30
Quiz
5. Possible solution to the external fragmentation is
to use
a) Compaction
b) Paging scheme
C) None

31. 31
6. ___________used as an index into a page
table
a) Page offset
b) Hole
c) Page number (p)
d) None
Quiz

32. Other subject materials
•Web designing
•Micro processors
•C++ tutorials
•java
home

33. 33
Quiz
7. ______________combined with base address to
define the physical memory address
a) Page number
b) Page offset (d)
c) Compaction
d) None

34. 34
8. Divide physical memory into fixed-sized blocks
called
a) External fragmentation
b) Frames
c) Compaction
d) None
Quiz