Compare the storage needed to keep track of free memory using a bitmap versus a

Question

Compare the storage needed to keep track of free memory using a bitmap versus
a linked list. The 4 GB (4096 MB) memory is allocated into units of size n bytes. For
the linked list, assume that memory consists of an alternating sequence of segments
and holes, each 96KB long. Also, assume each node in the linked lists requires a 64-
bit memory address, a 16-bit length field and a 32-bit next-node field (14 bytes in size
total). How many bytes of storage are required for each method? Which is better, in
which cases? Discuss the implications of the size of the allocation unit, i.e., what is
the effect of n.

Explanation / Answer

Dear..... The bit map needs 1 bit per allocation unit. ( 4GB = 2^32, 96 kB = ). with 2^32/n allocation unit (bits), this is ( 2^32/2^3)/n = 2^29/n bytes. The Linked list has 2^32/96KB nodes. each of 8 bytes( 4 bytes for memeory address, 2 bytes length and 2 bytes next-node filed) for a total of 2^32/96KB nodes * 2^3 bytes. For small n, the linked list is better. For large n, the bit map is better. The cross over point can be calculated by solving equation:     2^29/n bytes = 2^19, n = 2^10 bytes. so, if n < 1KB, linked list is better, and n > 1KB, bit map is better. The assumption about segments and holes alternating every 96KB is very unrealistic. and if segments and holes are 96 kB then, need n <= 96KB   .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.