Using an explicit free list instead of an implicit free list

Using an explicit free list instead of an implicit free list changes the allocation time using first-fit placement from linear in the number of Z blocks to linear in the number of W blocks. The correct replacements for Z and W are: Z = total and W = free Z = free and W = total Z = allocated and W = free Z = allocated and W = total Z = total and W = allocated

Solution

Programmers use dynamic memory allocators (like malloc) to acquire memory at run time. Dynamic memory allocators manage an area of process virtual memory known as the heap. Allocator maintains heap as collection of variable sized blocks, which are either allocated or free.

Types of allocators :-

§ Explicit allocator: application allocates and frees E.g., malloc and free in C

§ Implicit allocator: application allocates, but does not free E.g. garbage collection in Java, ML, and Lisp

Methods to keep track of free blocks :-

Method 1: Implicit list using length—links all blocks : Linear time in total number of blocks (allocated and free)

Method 2: Explicit list among the free blocks using pointers : Linear in number of free blocks (instead of all blocks)

Therefore, correct option is 1. Z=total (linear in number of Z blocks using implicit list) and W=free (linear in number of W blocks using explicit list)