Andrew S. Tanenbaum (OS) Edition 4 Exercise 3 Question 3 (Page No. 254)

Question

A swapping system eliminates holes by compaction. Assuming a random distribution of many holes and many data segments and a time to read or write a $32-bit$ memory word of $4\:nsec$, about how long does it take to compact $4\: GB?$ For simplicity, assume that word $0$ is part of a hole and that the highest word in memory contains valid data.

Answer 1

Total memory addresses$=4\times 2^{30}/4 = 2^{30} \; \text {memory address}$

Compaction time $=\text{(read + write)} \times \text{Number of memory access} \\= 2 \times 4\times 10^{-9}\times 2^{25}  \\= 8 \times 0.033554432 = 0.268435456 = 263.4 \;\text{ms}$

Comments

i think its 2×4×10^(−9)×2^30

this happens when u blindly copy paste the answer without reading the question carefully from stackoverflow
 

Answer 2

This is what I think the logic should be.

For compaction, we need to read and write every addressable unit once. How?

First consideration: Since it says random distribution and says ‘many’ holes and ‘many’ data. I am assuming equal number of holes and data segments.

So we can maintain 2 pointers, the first pointer will point to the hole from LHS and the second pointer will search for data from RHS to be swapped with this newly found hole. So by the time, we have found both the hole and data, we would have completed 2 READ operations. Similarly, we need swap to data and hole content, hence 2 writes. And this will happen for each memory address.

And hence we can say compaction time=(read time+write time) * number of addressable memory units

= (4+4) * $2^{30}$ ns

Please comment down if you think the solution is wrong.