MODULE-4 Memory Management: Memory management strategies: Background;

Swapping; Contiguous memory allocation; Paging; Structure of page table; Segmentation.

Virtual Memory Management: Background; Demand paging; Copy-on-write; Page
replacement; Allocation of frames; Thrashing.

Memory Management

3.9 Main Memory

3.9.1 Basic Hardware

• Program Execution Needs Memory

A program cannot run directly from disk.
It must be:
1. Brought from disk into main memory
2. Placed inside a process
Only then can the CPU execute it.

• CPU Direct Access

The CPU can directly access only:
• Registers
• Main memory
Register access → 1 CPU cycle
Main memory access → many cycles (slower)

• Cache Memory
Cache is placed between CPU registers and main memory to reduce the access time difference.
It stores frequently used data.

• Memory Protection
To prevent processes from accessing others’ memory or OS memory, hardware-based protection
is required.

• Base Register & Limit Register

These two registers define each process’s allowed memory area.
1. Base Register → starting physical address assigned to the process
2. Limit Register → size of the process’s address space
 Figure 3.8 A base and a limit-register define a logical-address space

They ensure:
• Process can access addresses only within its valid range
• Access outside the range → trap/error

Figure 3.8 (Concept)

Logical address + base register → physical address

Figure 3.9 Hardware address protection with base and limit-registers

Figure 3.9 (Concept)

Hardware checks:
• Is address ≥ base?
• Is address < base + limit?
If yes → valid, otherwise → trap.
3.9.2 Address Binding
• Address binding means mapping logical addresses to physical memory addresses.
• This mapping can occur at three different stages (Figure 3.10):
1) Compile Time Binding
• Used when the exact memory location is known before execution.
• The compiler generates absolute code with fixed physical addresses.
• If the starting address changes → the entire program must be recompiled.

2) Load Time Binding

• Used when memory location is not known during compilation.
• The compiler generates relocatable code.
• Actual physical address is decided during loading into memory.

3) Execution Time Binding

• Used when a process may be moved in memory during execution (e.g., swapping).
• Binding happens during run-time.
• Requires hardware support such as:
o Base register
o Limit register
o Or other address-mapping hardware.

Figure 3.10 Multistep processing of a user-

program

3.9.3 Logical versus Physical Address Space

• Logical address (virtual address) → generated by the CPU.
• Physical address → actual address in memory hardware.
• In compile-time and load-time binding:
→ Logical = Physical (same address).
• In execution-time binding:
→ Logical ≠ Physical (different).
→ Mapping happens at run-time.

Figure 3.11 Dynamic relocation using a

relocation-register

• MMU (Memory Management Unit)

• Hardware that maps virtual → physical addresses (Figure 3.11).
• The value in the relocation register is added to every logical address.
• The user program works only with logical addresses and never sees the physical address.

3.9.4 Dynamic Loading

• Used to improve memory-space utilization.
• A routine is loaded only when it is called, not before.
How it works:
1. All routines stored on disk in relocatable format.
2. Only the main program is initially loaded into memory.
3. When the main program calls a routine, it first checks whether it is loaded.
4. If not loaded → the loader loads it into memory.
5. Control then passes to the newly loaded routine.
Advantages:
1. Unused routines are never loaded.
2. Very useful for code that is rarely needed.
3. Program size may be large, but only the used parts occupy memory.
4. No special OS support required.

3.9.5 Dynamic Linking and Shared Libraries

• Linking is postponed until execution-time (not done at load time).
• Mostly used for system libraries.
Mechanism:
• A stub (small helper code) is placed for each library function.
• When executed, the stub:
1. Checks if the required library routine is already in memory.
2. If not → loads the routine into memory.
3. Replaces itself with the actual address of the routine.
4. Executes the routine.
• Next time the code runs → routine is called directly, with no extra cost.
Shared Libraries:
• All processes share a single copy of the library in memory.
• Libraries can be updated, and all programs automatically use the new version.
• Version information in both program & library prevents incompatibility.

3.10 Swapping
• A process must be in main memory to execute.
• A process can be:
• Swapped out to a backing store (temporary removal)
• Swapped in back to memory when it needs to continue execution.

Backing Store
• A fast disk large enough to store copies of all user processes.
• Acts as temporary storage for swapped-out processes.

Figure 3.12 Swapping of two processes using a disk as a backing-store

Roll Out / Roll In (for Priority Scheduling)

• Used in priority-based scheduling:
• A lower-priority process is swapped out.
• A higher-priority process is loaded into memory and executed.
• After the high-priority process finishes → the lower-priority process is swapped back in
(Figure 3.12).

Swapping & Address Binding

 1. Load-time binding
o Process cannot easily move to a new memory location.
o Swapping is difficult.
2. Execution-time binding
o Physical addresses are calculated during execution.
o Process can be swapped into a different memory location easily.

Swap Time
• Most of the swapping time is transfer time (moving data between memory and disk).
• Transfer time is directly proportional to the size of the memory being swapped.

Disadvantages of Swapping
1. High context-switch time (because swap in/out is slow).
2. Swapping requires the process to be completely idle; hence two solutions:
o i) Never swap a process with pending I/O.
o ii) Perform I/O only into OS buffers, not directly to user memory.

3.11 Contiguous Memory Allocation

• Main memory is divided into two partitions:
• One partition for the resident OS
• One partition for user processes
Defn: Each process occupies one single contiguous block (continuous section) of memory.

3.11.1 Memory Mapping & Protection

Purpose
• To protect:
• The OS from user processes
• User processes from each other

Hardware Used for Protection

1. Relocation Register
o Stores the starting physical address of the process
o Also called the base address
2. Limit Register
o Stores the size (range) of the logical address space
 Figure 3.13 Hardware support for relocation and limit-registers

Rules
• Every logical address generated by the CPU must be:
• < limit register
• Then MMU adds the relocation-register value
• Result = physical address (Figure 3.13)
• Order of Operations
• 1. OS loads the process → sets:
• Relocation register (base address in physical memory)
• Limit register (size of the process’s logical address space)
• These two are set before the process starts running.
• 2. Then the CPU begins executing instructions and generates logical addresses

• If the limit = 10,000 → the process can only generate addresses 0 to 9,999.

3.11.2 Memory Allocation

Two types of memory partitioning:
1. Fixed-sized Partitioning
• Memory is divided into fixed-sized partitions.
• Each partition may contain exactly one process.
• Degree of multiprogramming = number of partitions.
• When a partition is free, a process is
→ selected from the input queue and
→ loaded into the free partition.
• When the process terminates, the partition becomes available for another process.
2. Variable-sized Partitioning
• The OS keeps a table showing
→ which parts of memory are free,
→ which are occupied.
• A hole = a block of available memory.
• Memory normally contains holes of different sizes.
• Initially, all memory is free → one large hole.
• When a process arrives, memory is allocated from a suitable hole.
• Only the required amount is allocated; the remaining part stays free for future use.
 3.

Three Memory allocation strategies for selecting a free hole(based on variable

partitioning)
1. First Fit
• Allocate the first hole that is big enough.
• Searching may start
→ from the beginning, or
→ from where the previous search ended.
2. Best Fit
• Allocate the smallest hole that is big enough.
• Must search the entire list (unless sorted by size).
• Produces the smallest leftover hole.

3. Worst Fit
• Allocate the largest available hole.
• Must search the entire list (unless sorted by size).
• Produces the largest leftover hole.

Example:
 Suppose that we have memory of 1000 KB with partitions of size 150 KB , 200 KB, 250
KB, 100 KB AND 300 KB. Where the processes A and B of size 175 KB and 125 KB
will be loaded, if we used Best fit and Worst fit?
Assuming processes are loaded in the order A (175 KB) then B (125 KB):
Best fit
• A (175 KB) → 200 KB partition (leftover 25 KB)
• B (125 KB) → 150 KB partition (leftover 25 KB)
Worst fit
• A (175 KB) → 300 KB partition (leftover 125 KB)
• B (125 KB) → 250 KB partition (leftover 125 KB)

3.11.3 Fragmentation
Fragmentation is the wastage or loss of memory because we are not able to use the memory or
allocate it effectively.
Two types of fragmentation:
1. Internal Fragmentation
2. External Fragmentation

1) Internal Fragmentation
• Physical memory is divided into fixed-sized blocks.
• A process may get slightly more memory than requested.
• The extra unused memory inside the allocated block is called internal fragmentation.

2) External Fragmentation
• Total free memory is enough, but free spaces are scattered (not contiguous).
• First-fit and best-fit both suffer from external fragmentation.
• 50% rule: For N allocated blocks, about 0.5N is lost as external fragmentation.
 •
• In the above diagram, we can see that, there is enough space (55 KB) to run a process-07
(required 50 KB) but the memory (fragment) is not contiguous.

Solutions to External Fragmentation

1. Compaction
o Rearranges memory so that all free space becomes one large block.
o Possible only if dynamic relocation is supported at execution time.
2. Non-contiguous allocation
o Logical address space can be split across different physical locations.
o Achieved using:
1. Paging
2. Segmentation

Internal External
Feature
Fragmentation Fragmentation
Outside blocks,
Where waste Inside allocated
scattered in
occurs block
memory
Variable-size
Causes Fixed-size partitions
partitions
Memory free
but Yes, inside block Yes, but scattered
unusable?
Use
Solution dynamic/variable- Compaction, paging
size allocation

3.13 Paging
• Paging is a memory-management scheme.
• Allows the physical address space to be non-contiguous.
• Solves the problem of placing variable-sized memory chunks on backing store.
• Traditionally done by hardware, but modern systems integrate hardware + OS.
3.13.1 Basic Method
• Physical memory → divided into fixed-size frames.
• Logical memory → divided into same-size pages.
• When a process executes, its pages are loaded into any free frame in physical memory.
• Backing store is also divided into blocks equal to frame size.
• Page table stores the base address of each page in physical memory.

Figure 3.16 Paging hardware

Figure 3.17 Paging model of logical and physical-memory

Logical → Physical Address Translation
• CPU-generated address is divided into two parts:
1. Page number (p) → index into page table
2. Offset (d) → added to frame’s base address to form the physical address

• Page size = frame size; defined by hardware.

• If logical-address space = 2𝑚 and page size = 2𝑛 :
o High-order (m – n) bits → page number
o Low-order n bits → page offset

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

3.13.2 Hardware Support for Paging

• Each process has its own page table.
• A pointer to the page table is stored in the PCB.
Translation Lookaside Buffer (TLB)
• TLB is associative, high-speed memory.
• Stores a small number of page-table entries.
Working:
• CPU generates logical address → page number sent to TLB.
• TLB Hit:
o Frame number found immediately → memory accessed.
• TLB Miss:
o Page table in memory is accessed to get frame number.
o The page number + frame number is added to the TLB.
• If TLB is full → OS chooses an entry to replace.
• Hit ratio: % of times the page-number is found in TLB.
•
• Advantage: Very fast lookup.
 • Disadvantage: Hardware is expensive.
• Some TLB entries are wired (cannot be removed).
• Some TLBs store ASID (Address Space Identifier) for:
o identifying processes
o protecting each process’s address space.

3.13.3 Protection
• Memory protection is done using protection bits for each frame.
• Protection bits are stored in the page table.
• A protection bit can mark a page as read-write or read-only.
During memory access:
1. Physical address is computed.
2. Protection bit is checked.
3. Write on read-only page → hardware trap (memory protection violation).

Valid–Invalid Bit
• Each page-table entry has a valid/invalid bit.
1. Valid: Page is part of the process’s logical address space.
2. Invalid: Page is not part of the process’s logical address space.
• Illegal memory accesses are detected using this bit.
• OS sets this bit to allow or block access to a page.
Figure 3.20 Valid (v) or invalid (i) bit in a page-table

3.13.4 Shared Pages

Advantage of Paging: Shared Code
1. Paging allows sharing of common code between processes.
2. Re-entrant code (non–self-modifying code) never changes during execution.
3. Multiple processes can run the same code at the same time.
4. Each process still has its own registers and data pages.
5. Data is different for each process, but code pages are shared.
6. Only one copy of the code (e.g., an editor) exists in physical memory.
7. Each process’s page table maps:
o Code pages → same physical frames
o Data pages → different frames
Disadvantage
1. Systems using inverted page tables find shared memory difficult to support.
 Figure 3.21 Sharing of code in a paging environment

3.15 Segmentation
3.15.1 Basic Method
• Segmentation is a memory-management scheme that matches the user’s logical view of
memory. segmentation is designed to keep logically related parts of a process together in
a single segment, such as an entire function, code block, or data structure
• A logical address space is divided into segments.
• Each segment has:
o a name
o a length
• A logical address has 2 parts:
1. Segment number (s)
2. Offset within the segment (d)
 Figure 3.26 Programmer’s view of a program

Typical segments created by a compiler

• Code segment
• Global variables
• Heap
• Stack(s)
• Standard libraries

Each of these becomes a separate segment.

3.15.2 Hardware Support

To convert (segment number, offset) into a physical address, OS uses a segment table.

Each entry in Segment Table contains:

1. Segment-Base
o Starting physical address of the segment.
2. Segment-Limit
o Length of the segment.
 Figure 3.27 Segmentation hardware

Address Translation Steps

Given logical address: (s, d)

1. Check if d < limit[s]

o If not, → trap to OS (segmentation fault).
2. If d is valid:
o Physical Address = base[s] + d

VIRTUAL MEMORY

4.1 Virtual Memory

Why whole program is not needed in memory?
Because many parts are rarely executed, like:
• Error-handling code
• Extra array/list space
• Rarely used features
So loading the entire program wastes memory.

Benefits of loading only part of a program

• More programs can run at the same time.
• Programmers get a large virtual address space → no need for overlays.
• Less I/O → programs run faster.

What is Virtual Memory?

Virtual Memory = Technique that lets a process run even if it is not fully in physical memory.
• Separates logical memory (what program thinks) from physical memory (actual RAM).
• Allows page sharing → multiple processes share code.
• Logical address space can be larger than physical RAM.
 • Implemented using:
1. Demand Paging
2. Demand Segmentation

How memory is viewed?

• Process sees a virtual/logical address space (continuous).
• Actual physical memory uses page frames, which may be scattered (not contiguous).
• The MMU (Memory Management Unit) maps:
logical page → physical frame

✔ Virtual Memory can be bigger than physical RAM.

✔ Only needed pages are loaded into RAM.
✔ MMU uses the page table (memory map) to translate addresses.
✔ Virtual address space = logical view
✔ Physical memory = actual RAM

4.2 Demand Paging

What is Demand Paging?

Demand paging = Load pages only when needed.

Instead of loading the entire process into RAM, OS loads only those pages that the CPU
actually uses.
This reduces memory use and speeds up execution.

How it works
• The full process stays in secondary storage (disk).
• When execution starts, only required pages are brought into memory.
• A lazy swapper/pager loads pages on demand.
Advantages
1. No wasted loading → unused pages stay on disk.
2. Faster loading → fewer pages read.
3. Less physical memory required.

4.2.1 Basic Concepts

Valid–Invalid Bit

Used to track whether a page is:

• valid (1) → page is in memory

• invalid (0) →
o either page not part of process
o or page is valid but currently on disk
 o

Page Fault

Happens when a process accesses a page not in main memory.

Steps in handling a page fault (Figure 4.4):

1. Check if the memory access is valid/invalid.

o If invalid → terminate the process.
2. If valid but page not loaded → bring it in.
3. Find a free frame in RAM.
4. Read the required page from disk into that frame.
5. Update page-table & internal tables.
6. Restart the interrupted instruction.
Pure Demand Paging

• Never bring any page unless needed.

• Might cause many page faults initially, but programs show locality, so performance
becomes good.

Hardware support needed

1. Page Table with valid/invalid bits

2. Secondary memory (swap space) to store pages not in RAM

4.2.2 Performance of Demand Paging

Demand paging affects performance because page faults are very slow compared to normal
memory access.
Probability of page-fault
• Let p = probability of a page-fault
• 0≤p≤1
o p = 0 → perfect, no faults
 o p = 1 → every access faults → worst case
Effective Access Time (EAT)
𝐸𝐴𝑇 = (1 − 𝑝) × memory access time + 𝑝 × page-fault time

Even a small value of p makes EAT very large because page-fault time is huge (milliseconds vs
nanoseconds).

What happens during a page fault? (12 steps)

When a page fault occurs:
1. Trap to OS
2. Save registers + process state
3. Confirm page fault
4. Check if reference is valid & find page on disk
5. Read page from disk into a free frame (wait in device queue → seek → transfer)
6. CPU may switch to another process
7. Disk sends interrupt that I/O is done
8. Save other process state (if step 6 happened)
9. OS recognizes it is disk interrupt
10. Update page table
11. Wait for CPU again
12. Restore registers & resume instruction
Conclusion: Page faults are extremely expensive → performance depends on keeping p small.

4.3 Copy-on-Write (COW)

Copy-on-Write is used during process creation (fork).
Idea
Parent and child share the same pages initially (no copying yet).
But if any process writes to a shared page → OS copies that page first.
Example
• Child tries to modify a stack page.
• Page is marked copy-on-write.
• OS creates a duplicate of that page just for the child.
• Child writes only in its own copy.
• Parent’s page remains unchanged.
Benefit: Saves memory and avoids unnecessary copying.

4.4 Page Replacement

When a page fault occurs and no free frames are available, the OS must replace an existing
page using a page-replacement algorithm.
Popular Page Replacement Algorithms
1. FIFO – Replace the oldest page (first loaded → first removed)
2. Optimal – Replace the page that will not be used for the longest time (theoretical)
3. LRU – Replace the least recently used page
4. LFU – Replace the least frequently used page
4.4.1 Need for Page Replacement
• Multiprogramming increases → memory may be over-allocated
• A page fault occurs
• OS checks the free-frame list → no free frames available (Figure 4.5)
At this point OS has 3 options:
1. Terminate the process (bad idea)
2. Swap out a process (reduce multiprogramming)
3. Do page replacement ✔ (best choice)
So page replacement is needed when all frames are full.

4.4.2 Basic Page Replacement

Basic idea (Figure 4.6):
If no frame is free → choose a frame, free it → bring the needed page into that frame.
Steps of Page Replacement
1. Find location of required page on disk.
2. Find a free frame:
o If free frame exists → use it
o If none → use page-replacement algorithm to select a victim frame
o Write victim frame to disk if needed + update tables
3. Read required page into the freed frame
4. Restart the process
Problem: Double Transfer
If a frame is replaced:
• 1 page goes out (write to disk)
• 1 page comes in (read from disk)
This doubles page-fault time → increases EAT.

Solution: Modify Bit (Dirty Bit)

Each page has a modify bit:
• 1 → Page has been modified → must be written to disk
• 0 → Page NOT modified → skip writing → faster
Advantage:
✔ Reduces page-fault service time
✔ Improves overall performance

Two Major Problems to Solve in Demand Paging

1) Frame Allocation Algorithm
Decides how many frames each process should get.
2) Page Replacement Algorithm
Decides which frame to replace when memory is full.

4.4.3 FIFO Page Replacement

How FIFO works

• Each page remembers when it entered the memory.
• Pages are stored in a FIFO queue.
o Head → oldest page
o Tail → newly inserted page
Replacement rule
✔ Replace the oldest page (the one at the head of the queue).
Example Explanation (Based on Figure 4.7)

Frames: initially empty

1. First 3 pages 7, 0, 1 → all page faults, all loaded.
2. Next page 2 → replaces 7 (oldest).
3. Next page 0 → already in memory → no fault.
4. Page 3 → replaces 0.
5. This continues till the end → 15 total faults.

Advantages
1. Very easy to understand
2. Very easy to implement

Disadvantages
1. Performance is not always good
2. Can suffer from Belady’s anomaly

Belady’s Anomaly
• In FIFO, increasing the number of frames may increase the page-faults (this is
abnormal!).
• Example reference string:
123412512345
o With 3 frames → 9 faults
o With 4 frames → 10 faults
• More frames → more faults (very strange!).
4.4.4 Optimal Page Replacement (OPT)
Working Principle
Replace the page that will not be used for the longest time in the future.
✔ Looks into the future
✔ Always picks the "best" page to remove
✔ Solves Belady’s anomaly

Reference string given.

1. First 3 pages → faults (frames empty)
2. When page 2 comes →
o Page 7 → used at reference 18 (very far)
o Page 0 → used at 5
o Page 1 → used at 14
✔ Replace 7
3. Continuing this way → 9 total faults
FIFO had 15 faults, so optimal is much better.

Advantage
1. Best possible page-fault rate for given frames
(No algorithm can beat OPT)
Disadvantage
1. Cannot be implemented in real OS
→ Because we cannot know the future reference string

4.4.5 LRU Page Replacement (Least Recently Used)

Difference between FIFO, OPT, and LRU
• FIFO → time when page entered memory
• OPT → time when page will be used in future
• LRU → time when page was used in the past (most realistic)

Working Principle
Replace the page that has not been used for the longest time (oldest in terms of usage).
✔ Uses past behavior to predict the future
✔ More practical than OPT
✔ Better than FIFO

Example (Figure 4.10)

• First 5 faults = same as Optimal
• When page 4 is requested:
o Check last-used times of pages in memory
o Page 2 is least recently used
✔ So replace 2
LRU gives 12 page faults (more than OPT but better than FIFO usually).

Implementing LRU
1) Counter Method
• Each page-table entry stores a time-of-last-use
• CPU maintains a logical clock (counter)
• Every memory reference → copy clock value into page’s time field
• Smallest time value = least recently used → replace it

2) Stack Method
• Maintain a stack of page numbers (top = most recent)
• Whenever a page is used → move it to the top
• Bottom of stack = LRU page → replace it
 • Uses doubly linked list

Advantages
✔ Does not suffer from Belady’s anomaly
✔ More accurate than FIFO
✔ Behaves close to OPT
✔ Both LRU and OPT are stack algorithms
Disadvantages
True LRU requires hardware support (not available in most systems)
Maintains counters or linked-lists → expensive

4.4.6 LRU-Approximation Page Replacement

Real LRU is expensive (needs timestamps or linked lists).

So OS uses approximation with reference bits.
How Reference Bit Works
• Each page has a reference bit (0 or 1).
• OS initially sets all to 0.
• Whenever CPU accesses a page → hardware sets its reference bit to 1.
• By checking these bits, OS knows:
o which pages are recently used
o and which are not
This helps OS approximate LRU without full hardware support.

[Link] Additional-Reference-Bits Algorithm

This is a better LRU-approximation using history of last 8 time intervals.
How it works
• Each page gets an 8-bit register (a byte).
• At regular intervals (e.g., every 100 ms), OS:
1. Shifts the register right by 1 position
2. Puts the current reference bit into the leftmost (MSB)
3. Clears the reference bit for next interval
This creates a “history pattern” of usage.
Meaning of patterns
• 00000000 → not used in last 8 intervals → excellent victim
• 11111111 → used in all intervals → very active
• 11000100 is more recent than 01110111
(because MSB bits represent more recent usage)

How page is selected

• Convert each 8-bit pattern to a number
• Smaller number = older = LRU
• If two numbers equal → FIFO tie-break

[Link] Second-Chance Algorithm

This is the simplest LRU-approximation using only 1 bit (reference bit).
Also called Clock Algorithm.
Base
• Works like FIFO, BUT gives pages a second chance.
Procedure
1. Select the oldest page (FIFO pointer).
2. Check its reference bit:
o 0 → replace it (not used recently)
o 1 → give second chance
3. If second chance:
o set reference bit = 0
o move to next page in FIFO order
4. Continue until a page with bit = 0 is found.

Figure 4.12 Second-chance (clock) page-replacement algorithm

Clock Implementation (Figure 4.12)

Pages are arranged in a circular queue.
• Pointer (like clock hand) indicates next page to replace.
• Pointer moves around:
o If reference bit = 1 → clear it, skip it
o If reference bit = 0 → replace it
• New page is inserted at that position.
This makes it efficient and widely used in real OS.

[Link] Enhanced Second-Chance Algorithm (ESC / Improved Clock)

This algorithm improves the basic Second-Chance (Clock) by considering two bits:
1) Reference bit (R)
• 1 → recently used
• 0 → not recently used
2) Modify bit (M)
• 1 → page is dirty (modified)
• 0 → clean page

Four Classes (R, M)

The OS prefers to replace pages in this priority order:
Class R M Meaning Replacement Priority
(0,0) 0 0 Not recently used, clean Best → Replace first
(0,1) 0 1 Not recently used, but modified Needs write → Next best
(1,0) 1 0 Recently used, clean Probably needed again
(1,1) 1 1 Recently used & modified Worst choice

Working Procedure
1. OS scans pages in a circular list (like clock algorithm).
2. It looks for pages in the lowest non-empty class.
3. The first page found in that class is selected as victim.
4. If needed, the OS gives second chances by clearing the reference bit and continuing.
This reduces unnecessary disk writes and improves page replacement efficiency.

4.4.7 Counting-Based Page Replacement

These algorithms use a counter for each page.

1) LFU – Least Frequently Used

Working Principle
• Replace the page with smallest reference count.
• Pages used rarely → lower count → good candidates for replacement.
Problem
If a page was used heavily at start but never later, the count stays high.
So it remains in memory incorrectly, even though it's useless now.
Solution
• Periodically shift counts right (divide by 2).
 • This creates exponentially decaying usage, so OLD usage becomes less important.

2) MFU – Most Frequently Used

Working Principle
• Replace the page with highest count.
Reasoning
• A page with very high count was probably used a lot in the past and is no longer needed
now.
• Pages with low count are probably recently loaded and will be used soon.

Allocation of Frames (Page Frames)

When multiple processes run, the OS must decide how many frames to give each process.
Total frames = limited → must be distributed efficiently.
There are four main methods:

1) Equal Allocation
Each process gets the same number of frames.
Example
Total frames = 12
Processes = 3
Each process gets:
12 / 3 = 4 frames each
Process Frames
P1 4
P2 4
P3 4
Problem
If one process is large, it still gets only 4 frames → more page faults.

2) Proportional Allocation
Frames are allocated based on process size.
Formula
Frames for Pi = (Size of Pi / Total size of all processes) × Total frames
Example
Total frames = 12
Processes:
• P1 = 10 KB
• P2 = 20 KB
• P3 = 30 KB
Total size = 60 KB
So:
• P1 = (10/60) × 12 = 2 frames
• P2 = (20/60) × 12 = 4 frames
 • P3 = (30/60) × 12 = 6 frames
Process Size Frames
P1 10 KB 2
P2 20 KB 4
P3 30 KB 6
Better than equal allocation → Big processes get more frames.

3) Priority Allocation
Frames are allocated based on priority values.
Idea
High-priority process → gets more frames
Low-priority process → gets fewer frames
Example
Total frames = 15
Processes with priority:
Process Priority
P1 5
P2 3
P3 2
Total priority = 10
Frames:
• P1 = (5/10) × 15 = 7 frames
• P2 = (3/10) × 15 = 4 frames
• P3 = (2/10) × 15 = 3 frames
Useful when:
Important processes must run faster.

4) Global vs Local Allocation

A) Local Allocation
• A process can replace only its own frames.
• Each process has fixed frames.
Example
P1 has 4 frames
P1 makes a page fault → must replace one of its own 4 pages only.
Advantage
Good isolation.
Disadvantage
Some processes may suffer if given too few frames.

B) Global Allocation
• A process may choose a victim frame from any process.
• OS manages frames globally.
Example
P1 faults → can replace a page from:
 • P1, or
Global Replacement Local Replacement
Allows a process to a replacement frame from Each process selects from only its own set of
the set of all frames. allocated frames.
A process may happen to select only frames Number of frames allocated to a process does not
allocated to other processes, thus increasing the change.
number of frames allocated to it.
Disadvantage: Disadvantage:
A process cannot control its own page-fault rate. Might prevent a process by not making available
to it other less used pages of
memory.
Advantage:
Results in greater system throughput.
• P2, or
• P3
Advantage
Better overall throughput.
Disadvantage
One process can steal frames → others may thrash.

4.6 Thrashing

Definition

A process is thrashing when it spends more time doing paging (page faults, swapping) than
actual execution.

Why it happens
If a process does not have enough frames, its page-fault rate becomes very high.

This leads to:

• Low CPU utilization

• OS mistakenly thinks CPU is idle → so it adds more processes
• More processes = more demand for frames → even more page faults
• System becomes slow and stuck in a loop

This condition is thrashing.

4.6.1 Causes of Thrashing

Thrashing cycle (very important)

1. A process has too few frames → high page faults

2. High page faults → processes queue up for paging device
3. CPU becomes under-utilized (waiting for I/O)
4. OS thinks: “CPU idle → increase multiprogramming!”
5. OS loads a new process → even fewer frames per process
6. This new process also faults → even longer paging queue
7. System collapses into thrashing

This is shown in Figure 4.13.

How to prevent thrashing

1) Use Local Replacement

• If a process is thrashing, it can only replace its own pages

• It cannot take frames from other processes
• Prevents system-wide thrashing

2) Locality Model

We must give each process frames equal to its locality size.

Locality = group of pages used together.

Examples of localities:

• code segment being executed

 • loop body
• function call
• stack operations

Programs move from one locality to another, and if a process does not have enough frames to
hold the current locality → thrashing occurs.

Handling Pagefault:
1) Working-Set Model (WSS Model)

Idea:
Give each process exactly the number of pages it is actively using right now.

What is a Working Set?

A working set = the set of pages a process has used in the last Δ time (Δ = window size).

Example:
If Δ = 10 memory references
Process references:
2, 3, 4, 3, 5, 2, 4, 6, 4, 3

The working set = {2, 3, 4, 5, 6}, because they appear in the last Δ references.

Why is this useful?

Because:

• These are the pages currently needed

• If all pages in the working set are in memory → few page faults
• If some are missing → thrashing starts

How OS uses it?

For each process Pi:

• Calculate WSSi = number of pages in its working set

• Total demand = ∑ WSSi
• If ∑ WSSi > total frames → system does not have enough memory
• OS must suspend one process → to reduce thrashing

Advantages

• Very accurate
• Prevents thrashing
 • Gives just enough frames

2) Page-Fault Frequency Model (PFF)

Idea:
Control multiprogramming by watching the page-fault rate of each process.

PFF says:

If page-fault rate is high →

• process needs more frames

If page-fault rate is low →

• process has extra frames → OS can take some away

How it works?

OS sets two thresholds:

• Upper limit (too many faults → thrashing zone)

• Lower limit (too few faults → frames wasted)

So:

Page-Fault Frequency Action

Above upper limit Give more frames
Below lower limit Take frames away
Between limits Good → no action