Virtual memory management is a system used by operating systems (OS) to efficiently manage and allocate memory resources to processes. It enables a computer to compensate for physical memory shortages by temporarily transferring data from random access memory (RAM) to disk storage. This process invoRead more
Virtual memory management is a system used by operating systems (OS) to efficiently manage and allocate memory resources to processes. It enables a computer to compensate for physical memory shortages by temporarily transferring data from random access memory (RAM) to disk storage. This process involves paging and segmentation, two key techniques.
Paging
Paging divides the virtual memory into fixed-sized blocks called pages and the physical memory into blocks of the same size called frames. The OS keeps track of all pages and their corresponding frames through a page table. When a process needs to access data not currently in physical memory, a page fault occurs, prompting the OS to fetch the required page from the disk and load it into a free frame in physical memory. This approach allows non-contiguous memory allocation, reducing fragmentation and optimizing memory usage.
Segmentation
Segmentation, in contrast, divides the memory into variable-sized segments based on the logical divisions of a program, such as functions, arrays, and data structures. Each segment has a unique identifier and a segment table to manage its base address and length. This method aligns more closely with the logical organization of a program, making it easier to implement protection and sharing of memory. However, it can lead to external fragmentation.
Many modern OSs use a combination of both techniques, known as segmented paging, to leverage the benefits of both systems. This combined approach segments the memory and then applies paging within each segment, offering the logical structure of segmentation with the efficient memory use of paging.
See less
Dynamic Programming (DP) Dynamic Programming solves problems by breaking them into smaller, overlapping subproblems. It solves each subproblem once, stores the results, and uses these stored results to solve larger problems efficiently. Think of it like building a Lego model: build small pieces firsRead more
Dynamic Programming (DP)
Dynamic Programming solves problems by breaking them into smaller, overlapping subproblems. It solves each subproblem once, stores the results, and uses these stored results to solve larger problems efficiently. Think of it like building a Lego model: build small pieces first, save them, then assemble the final model.
Example: Climbing stairs with 1 or 2 steps at a time. To find the number of ways to reach the top, combine the ways to get to the previous two steps, storing each result to avoid recalculating.
Divide-and-Conquer
Divide-and-Conquer splits a problem into smaller, independent subproblems, solves each separately, and then combines their solutions. It’s like cutting a pizza into slices, eating each slice, and then combining them in your tummy. This approach gives you an optimal solution for each subproblem, but not necessarily the best global solution in all cases.
Example: Sorting a list with Merge Sort: split the list into two, sort each half, then merge them into a sorted list.
Key Differences
- Subproblems:
- DP: Overlapping subproblems, solved once.
- Divide-and-Conquer: Independent subproblems, solved separately.
- Storage:
- DP: Stores subproblem solutions.
- Divide-and-Conquer: Doesn’t typically store solutions.
- Approach:
- DP: Bottom-up.
- Divide-and-Conquer: Top-down, optimal at each step but not always globally optimal.
See less