Why paging is slow and how do we make it fast?

The reason why paging is slow

Every time a process accesses a memory location, the CPU must translate the logical address to a physical address using the page table. This translation involves multiple steps:

  • Look Up the Page Table: The CPU must first access the page table to find out which physical frame corresponds to the logical page.
  • Access the Physical Memory: Then, it uses the frame number obtained from the page table to access the actual memory location.

Example:

  • Page Size: 4 KB
  • Logical Address: 6 KB
  • Page Table Entry: 2 (The logical address 6 KB is in page 2)
  • Frame Number: 5 (Page 2 maps to frame 5 in physical memory)

Steps:

  • Access the Page Table: The CPU checks the page table to find out which frame contains the data for page 2. This involves accessing the page table entry for page 2.
  • Access Physical Memory: Once the frame number (5) is known, the CPU accesses the physical memory at frame 5.
  • Total Time: This process involves two memory accesses:
  • One to look up the page table
  • Another to access the actual memory location. 

How do we make paging fast?

The Translation Lookaside Buffer (TLB) is a special, high-speed cache used by the CPU to speed up virtual-to-physical address translation. When a program accesses memory, the CPU needs to translate the virtual address (used by the program) into a physical address (actual location in RAM). The TLB helps reduce the time it takes to perform this translation by storing recent address mappings.

How TLB Works
  • Address Translation: When a process accesses memory, it provides a virtual address.
  • The CPU first checks the TLB to see if the virtual address is already mapped to a physical address in the TLB cache.
  • TLB Hit: If the virtual address is found in the TLB (a "TLB hit"), the corresponding physical address is quickly retrieved from the TLB, and the memory access is fast.
  • TLB Miss: If the virtual address is not in the TLB (a "TLB miss"), the CPU must look up the page table to find the physical address. This involves:
  • Accessing the page table, which may require multiple memory accesses.
  • Once the physical address is found, it is added to the TLB so that future accesses to this address can be handled more quickly.

How does TLB deal with context switching?

The Address Space Identifier (ASID) is a value used to differentiate between different processes or address spaces in the TLB. It helps the TLB keep track of which entries are valid for which process, reducing the need to flush the TLB during context switches. Example of TLB with ASID and Context Switching
  • Initial State: Process P1 is running with ASID = 1. The TLB has entries tagged with ASID = 1, containing mappings for P1’s page table.
  • Context Switch: Process P2 is about to start running with ASID = 2. The ASID in the CPU is updated from 1 to 2.
  • No TLB Flush Needed: The TLB does not need to be cleared because the ASID tags help in distinguishing the entries for P1 and P2.
  • Execution of P2: When Process P2 accesses memory, the TLB checks the ASID and finds that the existing entries are not tagged with ASID = 2. Thus, it results in a TLB miss. The CPU looks up P2’s page table, and the required page table entries are loaded into the TLB with ASID = 2. Subsequent memory accesses by P2 are faster as the TLB now has entries with the correct ASID.


Comments

Post a Comment

Popular posts from this blog

Indexed allocation

Image
  Indexed allocation is a file allocation method used by operating systems to manage how files are stored on disk. The core idea is simple but powerful: instead of storing a file in contiguous blocks or linking blocks one-by-one, the system uses a special index block that contains a list of all the disk block addresses where the file’s data is stored. This removes many limitations of earlier methods like contiguous and linked allocation. In indexed allocation, each file has its own index block . This index block acts like a table of contents. Every entry inside it points to a data block that belongs to that file. When a file is created, the OS allocates an index block and then fills it with pointers to the actual data blocks as the file grows. These data blocks can be located anywhere on the disk , so the file does not need contiguous space. This makes storage much more flexible and avoids external fragmentation. When the system needs to access a particular part of a file, it fir...
Read more

Thrashing

Image
Thrashing occurs in a computer system when the operating system spends a significant amount of time swapping pages in and out of memory, rather than executing actual processes. This typically happens when the system's memory is overcommitted, meaning there are too many processes competing for too little physical memory, leading to frequent page faults. How Memory is Used 1. Initial State: App1 is running, and its two pages are loaded into memory: Frame 1: App1, Page 1 Frame 2: App1, Page 2 Frame 3 and 4 are free. App3's pages are present in swap memory. 2. Switch to App2: Now, you switch to App2, which also requires 2 pages: Frame 3: App2, Page 1 Frame 4: App2, Page 2 Memory is now full with both App1 and App2’s pages. App3's pages are present in swap memory. 3. Switch to App3: You decide to switch to App3, which needs 2 pages as well. Since the memory is full, the system needs to make room: App1’s pages are moved to swap memory: Swap Memory: [App1, Page 1] [App1, Page 2] F...
Read more

Basics of paging

Image
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus helps in handling fragmentation. It involves breaking down memory into fixed-size blocks called pages and frames. The OS typically decides the page size when the system is configured or during the OS design phase. This page size is constant for the entire system and is determined based on considerations such as hardware architecture, efficiency, and the type of applications running. Common page sizes are 4 KB, 8 KB, or 16 KB. Here's a simple explanation with an example: Basic Concepts Page: A fixed-size block of logical memory (virtual memory) used by a process. Frame: A fixed-size block of physical memory (RAM) where a page is mapped. Page Table: A data structure used by the operating system to keep track of the mapping between pages and frames. The Page Table Base Register (PTBR) is a special register in the CPU that holds the starting address of the page table for ...
Read more