OS Lecture-12

Paging and Segmentation

Basic Memory Management Schemes

Memory Management
Schemes (/Strategies)

Contiguous
Paging Segmentation
Allocation

Multiple-partition Conventional
method Variable size Paging Hierarchical Hashed Inverted
(Fixed-partition method Paging Paging Paging
allocation) (basic method)
Memory Management Strategy #2:
Paging
Paging
• Paging is a memory-management scheme that permits the physical
address space of a process to be non-contiguous.

• Because of its advantages, paging in its various forms is commonly

used in most OSs.

• Recent designs have implemented paging by closely integrating the

hardware and OS, especially on 64-bit microprocessors.

• Paging method also used to manage backing store (e.g. hard disk).
Paging: Basic Method
Frame
number
0

1 page 0
page 0 0 1
2
page 1 1 4
3 page 2
page 2 2 3
4 page 1
page 3 3 7
5
Logical Page table
memory 6

7 page 3
Physical
memory
Paging: Basic Method (cont.)
• The basic methodology:
– Breaking physical memory into fixed-sized blocks called frames
– Breaking logical memory into blocks called pages (where frame size=page size)

• When a process is to be executed, its pages are loaded into any available
memory frames from the backing store.

• The backing store is divided into fixed-sized blocks that are of the same
size as the memory frames.

• OS keeps track of free frames.

• Page table translates logical page to physical frame addresses.

• Frame size:
– Defined by hardware
– Should be power of 2
– Usually between 512 byte - 16MB
Paging: Basic Method (cont.)
• Address generated by CPU is divided into:
– Page number (p) – used as an index into a page table which contains
the corresponding frame number

– Page offset (d) – is the displacement within the page.

page number offset offset

page
p d
m-n n

─ Where:
• m = number of bits in logical address ⇒ Size of memory = 2m
• n = number of bits in offset part ⇒ Size of page = 2n
• m - n = number of bits in page number part ⇒ # of pages = 2m-n
Paging Hardware
0
Example Frame #0

4 i
j
Given: n=2 bits, m=4 bits Frame #1 k
l
Page size = 4 bytes, Physical memory = 32 bytes 8 m
n
Convert the logical address (13) to physical address. Frame #2 o
p
12
0 a
1 b 0 5 Frame #3
2 c Page #0
3 d 1 6 16
4 e 2 1 Frame #4
5 f
6 g Page #1
3 2 20 a
7 h b
8 i Page table Frame #5 c
9 j d
10 k Page #2
24 e
11 l f
12 m Frame #6 g
13 n h
14 o Page #3
28
15 p
Frame #7
Logical memory
Physical memory
Example (cont.)
Solution: 0 5
Physical address = base address + offset 1 6
= (frame # * frame size) + offset 2 1
3 2
Logical address = 13 (in decimal) = (1101) in binary Page table

Logical address = 1 1 0 1

⇒ Page # = (11) = 3 , Offset= (01) = 1

By using the page table>>> frame # = 2

∴ Physical address of logical address (13) = (2* 4) + 1= 9

Exercise: Convert the following logical addresses (given in decimal) to physical

for the same example: (0, 4,10,15)
Paging Arithmetic Laws
• Page size = frame size

• Logical address space (/size) = 2m

• Physical address space (/size) = 2x (where x is 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 = 2n

• # of pages= 2m-n

• # of entries (records) in page table = # of pages

• Required number of pages for a process = process size/page size (Rounded

up)
Question-1
On a simple paging system with 256 KB of physical memory, 16 MB of logical
memory, and a page size of 1 KB,
a) how many bits in logical address specify the page number?
b) how many bits in physical address specify the frame number?
c) how many entries are in page table?
d) how many bits are needed to store an entry in the page table (how wide
is the page table)?

e) what is the size of page table?

Question-1 (cont.)
Solution:
a) Size of logical memory = 16 MB = 224 ⇒ Logical address is of 24 bits
Page size = 210 ⇒ d = 10 bits
∴ # of bits to specify page number = 24 - 10 = 14 bits

b) Size of physical memory = 256 KB = 218 bytes ⇒ Physical address is of 18 bits

Frame size = Page size = 210 ⇒ d = 10 bits
∴ # of bits to specify frame number = 18 - 10 = 8 bits

c) # of entries in the page table = # of pages = 214

d) Width of page table entry = # bits to specify frame number = 8 bits = 1 byte

e) Size of page table = # of PT entries * Size of PT entry

= 214 * 1 byte = 24 * 210 * 1 = 16 KB
Question-2
Consider a machine with 64 MB physical memory and a 32 bit virtual
address space. If the page size is 4 KB, what is the approximate size of the
page table?
a) 16 MB
b) 8 MB
c) 2 MB
d) 24 MB

Ans: (c) 2 MB
Frame Allocation Procedure
• When a process arrives in the system to be executed:

– Process size (expressed in pages) is examined. …(i.e. if the process

requires n pages, at least n frames must be available in memory).

– If n frames are available, they are allocated.

– Then, when a page is loaded into a frame, its frame number is put
into the page table for this process…. and so on.
Frame Allocation Procedure (cont.)

Free frames (a) before allocation and (b) after allocation

Fragmentation in Paging
• Paging scheme has NO external fragmentation.. but it has an internal
fragmentation.
• Example:
If process (P1) size= 1030 B , page size= 512 B.. How many pages P1 will
occupied??
− Required # of pages= 1030/512 ≈ 2.01 → 3 pages
− Notice that the last page is almost empty…. (506 bytes are allocated and
unused)……. (Internal fragmentation)….what is the solution??
− Make page size small to reduce the internal fragmentation<<<<<Unsuitable
solution because:
• Page table size will increased…(more memory consumption & moreover head)
• Disk I/O is more efficient when the amount data being transferred is larger

• Generally, page sizes have grown over time as processes, datasets, and main
memory have become larger.
Paging Hardware
Tables Used in Paging Scheme
• Page table:
─ Part of process control block (PCB)
─ Each process has one page table
─ Contains 1 entry per logical page
─ Used to translate logical addresses to physical addresses in software

• OS keep track of physical memory allocation by using a frame table.

• Frame table:
─ Maintained by OS
─ Contains 1 entry per physical frame
• Whether free or allocated
• If allocated  it contains allocation information (Process ID, page#)
Paging Hardware
• The hardware implementation of the page table can be done in several
ways.
• Different methods to implement (/store) the page table(PT):
─ Method 1: Storing PT in dedicated registers:
• The simplest case
• Page table is stored in a set of dedicated, high-speed registers
• Instructions to load/modify PT registers are privileged
• Acceptable solution if page table is small

─ Method 2: Storing whole PT in RAM :

• This method is used if PT is large (common)
• PT stored in main memory
• Base address of PT is stored in page table base register (PTBR)
• Context switch involves changing 1 register only (i.e. fast)
• Two physical memory accesses are needed per user memory access (one for the
page-table entry, one for the byte).
 memory access is slowed by factor of 2 >>> this delay is unacceptable!!
Paging Hardware (cont.)
– Method (3): Use a cache (TLB):
• Use a special, small, fast cache, called a Translation Look-aside Buffer
(TLB).
• The search is fast but the hardware is expensive.
• TLB holds subset of page table entries.
• Each entry in the TLB consists of two parts: a key (page #) and a value
(frame #).
• Input value (logical address (L.A.)) is compared simultaneously with all
keys simultaneously.
– If L.A is found ⇒ TLB hit
» corresponding value (frame #) is returned to calculate physical
address (P.A.)
– If L.A is NOT found ⇒ TLB miss
» Access PT in RAM to get the frame# and then access RAM
» The page # and frame # is added to TLB, so that they will be
found quickly on the next reference.
Paging Hardware with TLB
Paging Hardware with TLB (cont.)
• Hit ratio: percentage of times that a page# is found in TLB
• Effective memory access time: average time for a memory access
(including TLB lookup)
• Example: If [ TLB lookup: 20ns, Memory access time: 100ns, Hit ratio:
80%]… Calculate the effective memory access time.

 If TLB hit >>> it takes (1) TLB access & (1) memory access
Memory access time if TLB hit = 20 + 100 = 120 ns

 If TLB miss >>> it takes (1) TLB access & (1) memory access to read PT &
(1) memory access to access the desired byte
 Memory access time if TLB miss= 20 + 100 + 100 = 220 ns

 Hit ratio =80% >>> So, miss ratio= 20 %

 Effective access time = (0.8 × 120) + (0.2 × 220) = 140ns

Question
Consider a paging hardware with a TLB. Assume that the entire page table
and all the pages are in the physical memory. It takes 10 milliseconds to
search the TLB and 80 milliseconds to access the physical memory. If the TLB
hit ratio is 0.6, the effective memory access time (in milliseconds) is:
a) 120
b) 122
c) 124
d) 118
Memory Protection
and
Shared Pages
Memory Protection in Paging
• Memory protection can be implemented by associating protection
bit with each frame to indicate if read-only or read-write access is
allowed.
– Can also add more bits to indicate page execute-only, and so on.

• Valid-invalid bit attached to each entry in the page table:

– “valid” indicates that the associated page is in the process’ logical
address space, and is thus a legal page.
– “invalid” indicates that the page is not in the process’ logical address
space.
– Or use page-table length register (PTLR).

• Any violations result in a trap to the kernel.

Valid (v) or Invalid (i) Bit In A Page Table
Shared Pages
• Shared code
– One copy of read-only (reentrant) code shared among processes (i.e.,
text editors, compilers, window systems)
– Similar to multiple threads sharing the same process space
– Also useful for interprocess communication if sharing of read-write
pages is allowed

• Private code and data

– Each process keeps a separate copy of the code and data
– The pages for the private code and data can appear anywhere in the
logical address space
Shared Pages Example
Page Table Structure
Page Table Structure
• Hierarchical Paging

• Hashed Page Tables

• Inverted Page Tables

Hierarchical Page Tables
• Break up the logical address space into multiple page tables.

• A simple technique is a two-level page table (appropriate for 32-bit

addresses).

• With a 232 address space and 4K ( 212 ) page sizes

=> 220 entries in the page table.

• At 4 bytes per entry, this amounts to a 4 MB page table, (too large

to reasonably keep in contiguous memory).

• Note that with 4K pages, this would take 1024 pages just to hold
the page table!
Two-Level Page-Table Scheme
• A logical address (on 32-bit machine with 4K page size) is
divided into:
– a page number consisting of 20 bits.
– a page offset consisting of 12 bits.

• Since the page table is paged, the page number is further

divided into:
– a 10-bit page number.
– a 10-bit page offset.
page number offset
p1 p2 d
10 10 12
Two-Level Page-Table Scheme (cont.)
Address-Translation Scheme
Question
• Consider a system using multilevel paging scheme. The page
size is 1 MB. The memory is byte addressable and virtual
address is 64 bits long. The page table entry size is 4 bytes.
Find:
1. How many levels of page table will be required?
2. Give the divided physical address and virtual address.
Solution
Hashed Paged Tables
• Common in address spaces > 32 bits.

• The virtual page number is hashed into a page table.

– This page table contains a chain of elements hashing to the same
location.

• Each element contains (1) the virtual page number (2) the value of
the mapped page frame (3) a pointer to the next element.

• Virtual page numbers are compared in this chain searching for a

match.
– If a match is found, the corresponding physical frame is extracted
Hashed Paged Table
Inverted Page Table
• Rather than each process having a page table and keeping track of all
possible logical pages, track all physical pages.

• One entry for each real page of memory.

• Entry consists of the virtual address of the page stored in that real
memory location, with information about the process that owns that
page.

• Decreases memory needed to store each page table, but increases time
needed to search the table when a page reference occurs.

• Use hash table to limit the search to one — or at most a few — page-table
entries.
– TLB can accelerate access.

• But how to implement shared memory?

– One mapping of a virtual address to the shared physical address.
Inverted Page Table Architecture
Memory Management Strategy #3:
Segmentation
Segmentation
• Users prefer to view memory as a
collection of variable-sized
stack
segments, with no necessary
ordering among segments. Subroutine
Segment 3
• Address space is made up of
variable-sized logical segments e.g. Segment 0 Symbol
table
main function, subroutines, some sqrt
Segment 4
data structures (list, array, stack,
etc.), . . . Main
Segment 1 program
• Segmentation is a memory-
Segment 2
management scheme that
supports the user view of memory. Logical address space
A logical address space is a
collection of segments.
Segmentation (cont.)
• Each segment has a name and a length. The addresses specify both
the segment name and the offset within the segment.

• The user therefore specifies each address by two quantities:

– a segment name …. (replaced by segment # for simplicity)
– an offset

• Logical addresses specify < segment-number, offset >

Segmentation: Hardware
Segmentation: Hardware (cont.)
• Segment Table
– Segment Table used to convert from logical to physical addresses
– Segment table entry = ( segment base, segment limit )
• Base = starting physical address of segment in memory
• Limit = size of segment

• Logical address consist of a two tuple: < segment-number, offset >

• Segment-table base register (STBR) points to the segment table’s location

in memory.

• Segment-table length register (STLR) indicates number of segments used

by a program;
segment number s is legal if s < STLR
Segmentation: Example

stack
1400
Segment 0
Subroutine
Segment 3
Limit base
Segment 0 Symbol 1000 1400
table 400 6300 3200
sqrt 400 4300
Segment 4 Segment 3
1100 3200
Main 1000 4700
4300
Segment 1 Segment 2
program Segment 4700
Segment 2 table
Segment 4

Logical address space 6300

Segment 1
(1) L.A. = <2, 53> ⇒ Segment# = 2, offset = 53
Physical address
Base = 4300, Limit = 400 space
Since 53 < 400 ⇒ P.A. = 4300 + 53 = 4353
Segmentation: Example (cont.)

stack
1400
Segment 0
Subroutine
Segment 3
Limit base
Segment 0 Symbol 1000 1400
table 400 6300 3200
sqrt 400 4300
Segment 4 1100 3200 Segment 3

Main 1000 4700

4300
Segment 1 Segment 2
program Segment 4700
Segment 2 table
Segment 4

Logical address space 6300

Segment 1
(2) L.A. = <0, 1222> ⇒ Segment# = 0, offset = 1222
Physical address
Base = 1400, Limit = 1000 space
Since 1222 > 1000 ⇒ Illegal reference, trap to OS
Fragmentation in Segmentation
• Segmentation suffer from external fragmentation.
Question
Consider the following segment table:

Segment No. Base Length

0 1219 700
1 2300 14
2 90 100
3 1327 580
4 1952 96

Which of the following logical address will produce trap addressing error?
a) 0, 430
b) 1, 11
c) 2, 100
d) 3, 425
e) 4, 95
Paging vs. Segmentation
Paging Segmentation
A page is of the fixed block size. A segment is of variable size.

It may lead to internal fragmentation. It may lead to external fragmentation.

In Paging, the hardware decides the The segment size is specified by the
page size. user.

A process address space is broken into A process address space Is broken in

fixed-sized blocks, which is called differing sized blocks called segments.
pages.
The paging technique is faster for Segmentation is slower than paging
memory access. method.

Page table stores the page data Segmentation table stores the
segmentation data.
Paging vs. Segmentation (cont.)
Paging Segmentation
Paging does not facilitate any sharing of Segmentation allows for the sharing of
procedures. procedures.

Paging fails to distinguish and secure Segmentation can be able to separate

procedures and data separately. secure procedures and data.

Paging address space is one In segmentation, there is the

dimensional availability of many independent
address spaces
In paging, the user just provides a In the segmentation method, the user
single integer as the address, that is specifies the address in two quantities
divided by the hardware into a page (1)segment number, and (2)offset.
number and offset.