First fit , Best fit, Worst fit

What is first,best and worst fit? Algorithems of these fits with animations.
Download for animations in slides.

1. Presentation Operating Systems Prepared By: M Shahzeb, M Aamir Ghaffar, Abdullah Ahmad Submitted To: Sir Azeem Ullah Rehan Roll No.’s: 067, 044, 065

2. First Fit (FF) A resource allocation scheme (usually for memory). First Fit fits data into memory by scanning from the beginning of available memory to the end, until the first free space which is at least big enough to accept the data is found. This space is then allocated to the data. Any left over becomes a smaller, separate free space. If the data to be allocated is bigger than the biggest free space, the request cannot be met, and an error is generated.

3. Flow Chart for First fit Start Initialize memory block Initialize memory waste If job <= memory block Allocate job to first fitted partition Job completed Get another job from queue End No Wait for input Yes

4. Algorithm Variable Partitioning FF 50 150 300 350 600 300 25 125 5 50 P1 125 P2 P3 P1 P2 P3 P4 P4

5. Advantages (FF) Disadvantages Simple Tends to produce larger free blocks toward the end of the address space External fragmentation

6. Best Fit (BF) The best fit deals with allocating the smallest free partition which meets the requirement of the requesting process. This algorithm first searches the entire list of free partitions and considers the smallest hole that is adequate. It then tries to find a hole which is close to actual process size needed.

7. Flow chart for best fit Start Initialize memory block Initialize memory waste If job <= memory block Allocate job to smallest partition Job completed Get another job from queue End No Wait for input Yes

8. Algorithm Variable Partitioning b F 50 150 300 350 600 300 25 125 5 50 25 P1 P2 P3 P4 P1 P3 P4 25 This will cause a Error. Will Explain In Words. P2 P1 P2

9. Advantages (BF) Disadvantages External fragmentation Slow allocation Slow deallocation Tends to produce many useless tiny fragments (not really great ) Works well when most allocations are of small size Relatively simple

10. Worst Fit (WF) The algorithm searches for free-space in memory in which it can store the desired information. The algorithm selects the largest possible free space that the information can be stored on (i.e. that is bigger than the information needing to be stored) and stores it there. This is directly opposed to the best fit algorithm which searches the memory in much the same way as before.

11. Flowchart for worst fit: Start Initialize memory block Initialize memory waste If job <= memory block Allocate job to largest partition Job completed Get another job from queue End No Wait for input Yes

12. Algorithm Variable partitioning WF 50 150 300 350 600 125 50 P1 300 P2 P3 P4 25 125 5

13. Algorithm Variable partitioning WF 50 150 300 350 600 125 50 P1 300 P2 P3 P4 25 125 5

14. 50 150 300 350 600 125 50 P1 300 P2 P3 P4 25 125 5 Algorithm Variable partitioning WF

15. 50 150 300 350 600 125 50 P1 300 P2 P3 P4 25 125 5 Algorithm Variable partitioning WF

16. Advantages ( W F) Disadvantages External fragmentation Tends to break large free blocks such that large partitions cannot be allocated Works best if allocations are of medium sizes

17. Thanks For Your Time Allah Hafiz… The End…