Describe both internal and external fragmentation problems encountered in a contiguous memory allocation scheme.
Answers
Fragmentation in general
External Fragmentation - The free space (whether disk, DRAM, NVRAM etc) is fragmented in way that there is possibly sufficient free space to satisfy an allocation request, but the free space is not arranged in a contiguous fashion. This usually happens when the free space is interspersed with the allocated space. The below diagram does not represent an array. I am just trying to depict the external fragmentation problem. Let's say F represents 1 KB of free space, and A represents some amount of allocated space.
If a new user request is 3 KB, our space container has sufficient free space, but is not contiguous. So, effectively the free space is fragmented and is represented by multiple fragments in different locations as opposed to one big chunk/hole of free space.
[ A, F, F, A, A, A, A, A, F]
Internal Fragmentation - The free space is again sort of fragmented, but is not at all usable. For example, to satisfy an allocation request of 9 KB, we allocate 16 KB to the user. Although the need is of 9 KB, the extra 7 KB we allocated contributes to space wastage. It is literally free space, but is internal to an allocated region. Hence, it is not usable for new requests.
Fragmentation in the context of Memory Management
A program needs to be loaded into memory before the CPU can start executing the instructions in the program. This running instance of a program/binary is called as a process. It sits in main memory (DRAM), and CPU runs it by fetching instructions and data from the main memory.
So, it is clear that the process needs to be allocated some space in DRAM, and this is done through some allocation strategy/algorithm.
Contiguous Memory Allocation : In this scheme, the process occupies a contiguous space in DRAM -- starting at some physical address S, and occupying all the region upto some physical address E. Over a period of time after considerable amount of process swapping (in/out of memory from/to disk) has been done by the operating system for processes of various sizes, the space in DRAM can get fragmented (externally).
When this happens, we see a situation similar to what I explained above. The OS Loader needs to load a new program into memory into some free space region enough to satisfy the memory requirements of the process. To support multi-programming, multiple processes are already sitting in DRAM within their respective allocated regions. If the free space is fragmented, the loader may not find space large enough for the new process.
A process currently in the memory has to be swapped out to disk to make space for the new process (Note that this is not done by the loader).
Contiguous memory allocation strategy can lead to internal fragmentation as well. When we allocate large chunk of space in DRAM to a process with lesser size requirements, the additional space given to the process is wasted space. It is internal to the allocated region, the process that owns it probably doesn't need it, and it can't be utilized to service future allocation requests.
Non-Contiguous Memory Allocation : Paging is a common scheme that does not demand contiguous allocation of memory region to the entire process. In paging, DRAM is divided into blocks (aka frames) of equal size (determined by the hardware, typically 4 KB). The process is allocated memory in the form of multiple pages, where the granularity of allocation is fixed at frame size. Moreover, frames to a process can be allocated anywhere in the main memory. It doesn't to follow the last allocated frame. Wherever there is a free frame, it can be allocated to the process.
I hope this will help you
If not then comment me
Answer:
comparison between PCL and usb