75.6k views
3 votes
Which of the following programming techniques and data structures in a user-level program) are good for a demand-paging environment, and which are bad? Explain your answer.

i. pointers and linked list
ii. sequential search through an array
iii. Binary tree search.

User MychaL
by
8.1k points

1 Answer

6 votes

Final answer:

Pointers and linked lists can be efficient in a demand-paged environment if data is localized but can lead to page faults if not. Sequential searches through arrays can induce multiple page faults, but may work well for small or localized arrays. Binary tree searches are efficient with balanced trees but can cause increased page faults if the tree is unbalanced.

Step-by-step explanation:

The student asks which programming techniques and data structures are good for a demand-paging environment and which are not. In a demand-paging system, where parts of a program are loaded into memory as needed, certain access patterns can lead to more efficient memory usage.

Pointers and Linked Lists

Using pointers and linked lists can be both good and bad. They are good because they allow dynamic memory allocation, which is efficient for a demand-paged environment where allocating large blocks of contiguous memory can be wasteful. However, they can be bad if the data is not localized, as traversing a linked list may cause frequent page faults if nodes are not stored in sequential pages.

Sequential Search Through an Array

A sequential search through an array can be less efficient in a demand-paging environment because it may access a large range of addresses, leading to multiple page faults. However, if the array fits within a few pages or the elements are accessed in a localized pattern, this technique could work effectively.

Binary Tree Search

A binary tree search can be efficient if the tree is balanced, as fewer levels mean fewer pages are accessed during search operations. However, an unbalanced tree might cause increased page faults due to deeper levels and less localized memory access.

User Gkiokan
by
7.4k points