Compaction
Garbage collection is the process of collecting all unused nodes and returning them to available space. This process is carried out in essentially two phases. The first phase is marking phase where all node which is in use is marked. And Second Phase is compaction where all free partitions are made contiguous and merged together which can be allocated according to the needs of the new process.
Compaction is a process of moving all free memory at the one end to form large memory chunk and non-available chunk at other ends. Now this large memory chunk or space can be utilized by new processes.
- Compaction solves the fragmentation problem by moving the all utilized block at one end.
- Basically, compaction reduces the external fragmentation. It shuffles the memory content to place all free memory together to form one larger block.
- It basically combines all empty spaces together and processes.
- This process requires too much CPU utilization.
- Instead of a large number of small free spaces, It combines all of them and forms a big free space that allows new incoming jobs.
- The system also maintains the relocation information. On each new allocation of the job in the memory system takes an image and also after the completion of the job system takes an image.
Example: Consider an array A = [3, 5, -, -, 8, 9], where - represents unused or deleted elements. Compaction would rearrange this array to A = [3, 5, 8, 9, -, -], moving all valid elements to the start of the array and the unused spaces to the end.
Overflow
Overflow is a condition that arises When we want to insert new data into the array data structure but there is no available space in that data structure. It means that there are no any empty list to store a new data, this situation is called overflow.
Example: Suppose we have a array arr = [3,6,1,8,3] of size 5. Trying to insert another element, say 9, would cause an overflow, as there are no available positions in the array.
In programming, handling array overflow might involve creating a larger array and copying the contents of the original array to it, which increases the storage space.
Underflow
Underflow is a condition that arises when we want to delete some data from an array data structure but there are no any data available in that data structure.
It means that given data structure is empty so if empty then there is no any element is available to delete, this situation is called underflow. Underflow is less commonly discussed but is important in the context of data structures like stacks and queues.
Example: Suppose we have an empty arr = []. Trying to remove an element from C would result in underflow, as there are no elements to remove.
In data structures like stacks and queues, underflow can be avoided by first checking if the structure is empty before attempting to remove an element.
Summary
- Compaction is about efficiently using space by rearranging elements in an array.
- Overflow occurs when trying to add an element to a full array.
- Underflow happens when trying to remove an element from an empty array.
Properly managing these situations is crucial in algorithm design and implementation, particularly when dealing with arrays and similar data structures in memory-constrained environments.