PAGING

PAGING:

Non-contiguous (physical) memory allocation - place process wherever memory is available.

Divide physical memory into fixed-sized blocks called frames (size is power of 2, usually between 512 - 8Kbytes).

Divide logical memory into blocks of same size called pages. When a process is executed, load its pages from storage into any available frames.
PAGE SIZES:
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.
ADDRESS TRANSLATION:
Virtual/logical address generated by CPU divided into:

Page number (p) - index into a page table which contains base address of each page in physical memory.

Page offset (d) - combined with base address to get physical memory address sent to the memory unit.

Logical address space = 2m ,page size = 2n.
FRAGMENTATION WITH PAGING:
No external fragmentation - any free frame can be allocated to any page (process).

Internal fragmentation remains - last frame may not be full.

Worst case a process needs n pages plus 1 byte; On average 0.5 page wasted per process; small page sizes are desirable - can reduce swapping.
SMALL AND LARGE PAGES:
Small pages implies more pages (larger page table/overhead).

To reduce size of page table - larger pages: Disk I/O is more efficient when larger data is transferred.
SEPARATION OF LOGICAL AND PHYSICAL MEMORY:
User does not and should not know where their data goes.

Translation (page table) is hidden by the OS, no way of addressing memory outside of the page table.
FRAME TABLE:
Tracks each physical page frame - free/allocated, if allocated, to which page of which process.

PAGE TABLE REGISTERS:
Page-table base register (PTBR) points to the page table and Page-table length register (PTLR) indicates its size.

Changing page table requires only changing PTBR. Reduces context switch time.

Every access requires two memory accesses - one for the page table and one for the data/instruction (slow by a factor of 2!)
TRANSLATION LOOK ASIDE BUFFER:(TLB)
A fast cache memory in CPU containing (page #, frame #) pairs for recently accessed page table entries (cannot be too large).

Parallely search Associative cache (fast, but very expensive).
ACCESS TIME WHEN PAGE IS IN MEMORY:
Associative Lookup = time unit.

Hit ratio - percentage of times that a page number is found in the associative registers; related to num. of associative registers.

MEMORY PROTECTION:
Implemented by associating protection bit with each frame - define a page to be read/write or read only.

Additionally Valid/invalid bit used in each entry of page table indicating whether the associated page is in the process' logical address space, and is thus a legal page.


Some of the advantages and disadvantages of paging are:

• advantages:
• Paging Eliminates Fragmentation
• Multiprogramming is supported
• Overheads that come with compaction during relocation are eliminated
• disadvantages :
• Paging increases the price of computer hardware, as page addresses are mapped to hardware
• Memory is forced to store variables like page tables
• Some memory space stays unused when available blocks are not sufficient for address space for jobs to run