Paging technique in memory menagement.ppt

Paging technique in memory menagement.

1. Memory Management
Ch.8

2. Mem. Manegment
Methods
(/strategies)
Continuous
Allocation
Multiple-partition
method
(Fixed-partition
allocation)
(variable size
method)
Paging
(Basic Method)
Hierarchical Page Hashed Page Inverted Page
Segmentation

3. Exercise 8.1
Explain the difference between internal and
external fragmentation.

4. Exercise 8.16
Given five memory partitions of 100 KB, 500
KB, 200 KB, 300 KB, and600 KB (in order),
how would each of the first-fit, best-fit, and
worst-fit algorithms place processes of 212
KB, 417 KB, 112 KB, and 426 KB (in order)?
Which algorithm makes the most efficient
use of memory?

5. Paging Hardware (fig 8-7)

6. Paging Example (fig 8-9)
Given:
N=2 bits
M=4 bits
Page size=4 B
Physical mem. Size=32 B
# of pages= 8 pages
>>How to convert from logical address to physical
address in paging???
Physical address = base address+ offset
= (frame # * frame size) + offset

7. PagingArithmetic Laws
Page size = frame size
Logical address space (/size) = 2
m
Physical address space (/size) = 2
x
(where xis the number of bits in physical
address)
Logical address space (/size) = # of pages ×page size
Physical address space (/size) = # of frames ×frame size
Page size= frame size= 2
n
# of pages= 2
m-n
# of entries (records)in page table = # of pages
(# of frames = # of pages) »» »» »» In Inverted paging ONLY
>>How to convert from logical address to physical address in paging???
Physical address = base address+ offset
= (frame # * frame size) + offset

8. Consider a logical address space of 64
pages of 1024 words each, mapped onto a
physical memory of 32 frames.
a. How many bits are there in the logical
address?
b. How many bits are there in the physical
address?
Exercise 8.14

9. Consider a logical address space of 32
pages of 1024 words each, mapped onto a
physical memory of 16 frames.
a. How many bits are required in the logical
address?
b. How many bits are required in the physical
address?
Exercise 8.22

10. Exercise 8.19
Assuming a 1-KB page size
What are the page numbersand offsetsfor the
following address references (provided as decimal
numbers)
d. 256a. 2375
e. 16385b. 19366
c. 30000

11. Address generated by CPU is divided into:
–Page number (p)–used as an index into a pagetablewhich
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 size2
n
page number page offset
p
d
m -n
n
Address Translation Scheme (paging)

12. Solution steps (Ex. 8.19)
1.Convert logical address: DecimalBinary
2.Split binary address to 2 parts (page # , Offset)
-offset: ndigits (where 2
n
=page size in bytes)
-page#:m-ndigits )where 2
m
=size in bytes of logical
address space)
3.Convert offset& page#: Binary Decimal

13. Convert : Decimal Binary
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
2
10
2
11
2
12
2
13
2
14
2
15
1248163264128256512102420484,0968,19216,38432,768

14. Exercise 8.19-solution
Offset
(decimal)
Page#
(decimal)
Offset
(10bits)
(binary)
Page#
(6bits )
(binary)
Logical address
(binary)
Logical
address
(decimal)
327201 0100 01110000 100000 1001 0100 01112375
9341811 1010 01100100 100100 1011 1010 011019366
304290100110000011101011101010011000030000
256001000000000000000000000100000000256
1160000000001010000010000000000000116385
Page size =2
n
=1024B= 2
10
B
#of bits in offset part (n)=10

15. Exercise 8.10
Consider a paging system with the page table stored in
memory.
a. If a memory reference takes 200 nanoseconds, how
long does a paged memory reference take?
b. If we add TLBs, and 75 percent of all page-table
references are found in the TLBs, what is the
effective memory reference time?(Assume that
finding a page-table entry in the TLBs takes zero
time, if the entry is there.)

16. Effective access time law
Effective access time =
∑ [probability of the case ×access time of this case]
Where (∑ probability of all cases =100%)

17. Paging Hardware With TLB(fig:8-11)

18. Exercise 8.8
On a system with paging, a process cannot
access memory that it does not own; why?
How could the operating system allow
access to other memory?
Why should it or should it not?

19. Exercise 8.15
Consider the hierarchical paging scheme used
by the VAX architecture.
How many memory operations are performed
when an user program executes a memory
load operation?

20. Address-Translation Scheme

21. Two-Level Page-Table Scheme

22. Exercise 8.6
What is the purpose of paging the page
tables?

23. Consider a computer system with a 32-bit
logical address and 4-KB page size . The
system supports up to 512MB of physical
memory. How many entries are there in each
of the following:
a. A conventional single-level page table
b. An inverted page table
Exercise 8.18

24. Exercise 8.21
Consider the following segment table:
Segment BaseLength
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
What are the physical addresses for the following logical
addresses?
a. 0,430
b. 1,10
c. 2,500
d. 3,400
e. 4,112
there is a typing error in this
row in book

25. Segmentation
>>How to convert from logical address to physical address in segmentation???
IF (offset ≤ limit) then
Physical address= base address+ offset
Else
Trap (address error)

26. Exercise 8.7
Explain why it is easier to share a reentrant
module using segmentation than it is to do so
when pure paging is used.

27. Exercise 8.17
Describe a mechanism by which one
segment could belong to the address space
of two different processes.

28. Exercise 8.11
1.Compare paging with segmentationwith
respect to the amount of memory required
by the address translation structures in
order to convert virtual addresses to
physical addresses.

29. Exercise 8.2
Compare the main memory organization
schemes ofcontiguous-memory allocation,
pure segmentation, and pure paging with
respect to the following issues:
a. external fragmentation
b. internal fragmentation
c. ability to share code across processes

30. Exercise 8.5
Consider the Intel address translation schemeshown in
Figure 8.22.
a.Describe all the steps that the Intel 80386 takes in
translating a logical address into a physical address.
b. What are the advantages to the operating system of
hardware that provides such complicated memory
translation hardware?
c. Are there any disadvantages to this address-
translation system? If so, what are they? If not, why
is it not used by every manufacturer?

31. Logical to Physical Address Translation in
Pentium

32. Fig 8-22: Intel Pentium Segmentation

33. Pentium Paging Architecture