Algorithms for efficient use of memory

We have this assignment from Operating System. I'm not sure though if it is correct but from what I have learned, here are my answers :)

1. Given 5 memory partitions of 100KB, 500KB, 200KB, 300KB, and 600 KB (in order). How would each of the first-fit, best-fit and worst -fit algorithms place processes of 212KB, 417KB, 112KB, and 426KB (in order) ?

 =======================================

This exercise is what we call memory allocation, where it is the process of assigning blocks of memory on request. There is this allocator that receives memory from the OS in a small number of large blocks. It must divide up to be able to satisfy the requests for smaller blocks. Also, it should make any returned blocks available for reuse.

So first, the definition or process or how to do the First-fit, Best-fit and worst-fit algorithms are the following:

First-fit -> the allocator keeps a list of free blocks, also know as the free list.

1.  If it receives a request for memory, it first scans along the list for the first block that is large enough to satisfy this request. 
2. Then if this chosen block is larger than what is requested, it splits and 
3. the remainder is added to the list as another free block.

In recycling free blocks, there is a choice as to where to add the blocks to the free list -- effectively in what order the free list is kept.

Best-fit -> where the allocator places a process in the smallest block of unallocated memory in which it will fit.

* the problem in Best-fit is that it has an expensive search of the entire free list to be able to find the best hole. Also, it leads to fragmentation - creation of lots of little holes that aren't enough to satisfy any requests.

Worst-fit -> memory manager places process in the largest block of unallocated memory available.

*Problem is that this will create the largest hole after the allocations. It is an another process that can use the hole created as a result of external fragmentation

Credit to these Sources:
http://www.memorymanagement.org/articles/alloc.html
http://stargazer.bridgeport.edu/sed/projects/cs503/Spring_2001/kode/os/memory.htm#bestfit

===================
Answer to assignment:

1) 5 memory partitions: 100KB, 500KB, 200KB, 300KB, and 600KB (in order)

 Processes: 212KB, 417KB, 112KB, and 426KB (in order)

a) First-fit

·         Process 212KB will be placed in the 300KB partition then the memory partition split. From 300 KB partition, there will be a 212KB partition and 88KB (300KB-212KB) memory partition.

·         Process 417KB will be placed in the 500KB partition then memory partition splits into two, 417KB partition and 83KB(500KB-417KB) new partitions.

·         Process 112KB will be placed in the 200KB partition then splits into new memory partition, 112KB and 88KB(200KB-112KB) partition.

·         Process 426KB will be placed in the 600KB partition then splits into new memory partition, 426KB and 174KB (600KB-426KB) partition.

b) Best-fit

·         Process 212KB will be placed in the 300KB memory partition

·         Process 417KB will be placed in the 500KB memory partition

·         Process 112KB will be placed in the 300KB memory partition

·         Process 426KB will be placed in the 600KB memory partition

c) Worst-fit

·         Process 212KB will be placed in the 500KB memory partition

·         Process 417KB will be placed in the 600KB memory partition

·         Process 112KB will be placed in the 200KB memory partition

·         Process 426KB will wait.