Time Complexity: Why virtual memory extends physical memory
O(n)
0
0
Why virtual memory extends physical memory in Operating Systems - Performance Analysis
Understanding Time Complexity
We want to understand how the use of virtual memory affects the time it takes for a computer to access data.
Specifically, how does adding virtual memory change the number of steps the system takes when running programs?
Scenario Under Consideration
Analyze the time complexity of accessing memory with virtual memory management.
function accessMemory(address) {
if (address in physicalMemory) {
return physicalMemory[address];
} else {
page = loadPageFromDisk(address);
physicalMemory[freeFrame] = page;
return page;
}
}
This code checks if the requested data is in physical memory. If not, it loads the data from disk into physical memory.
Identify Repeating Operations
Look at what repeats when accessing memory.
- Primary operation: Checking if data is in physical memory (a quick lookup).
- How many times: Once per memory access.
- Secondary operation: Loading a page from disk if data is missing (much slower).
- How many times: Only when data is not in physical memory, less frequent but costly.
How Execution Grows With Input
As the program uses more memory addresses, the system checks physical memory each time.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 quick checks, few disk loads |
| 100 | 100 quick checks, some disk loads |
| 1000 | 1000 quick checks, more disk loads |
Pattern observation: The number of quick checks grows directly with memory accesses, but disk loads happen less often and depend on memory size.
Final Time Complexity
Time Complexity: O(n)
This means the time to access memory grows linearly with the number of memory requests, mostly due to quick checks in physical memory.
Common Mistake
[X] Wrong: "Virtual memory makes memory access always slow because it uses disk every time."
[OK] Correct: Most memory accesses hit physical memory quickly; disk access happens only when data is missing, so average speed stays fast.
Interview Connect
Understanding how virtual memory affects performance shows you can think about how systems handle large data efficiently, a useful skill in many tech roles.
Self-Check
"What if the physical memory size increases? How would the time complexity of memory access change?"