CASE STUDY 5

CASE STUDY # 5

There are many methods for free space allocation. One of this is the Best-fit memory allocation. Best-fit memory allocation on a fixed partition memory is the kind of memory allocation wherein a job to be allocated will search from the top block to the bottom for the smallest partition that fits the job. The job will then be allocated to the block that will have the least internal fragmentation or wasted memory.

In the situation given, Job 1 which has a size of 100k, and a turnaround of 3, will search from block 1 to block 5. The job does not fit in block 1 for it only has 50k of memory, in block 2 (200k), there is an internal fragmentation of 100k, in block 3 (70k), the job does not fit, in block 4 (115k), the internal fragmentation is 15k, and in block 5 (15k), the job does not fit. The job will then be allocated to the block which has the least internal fragmentation which is the block 4. Job 2 with a size of 10k will have 40k internal fragmentation in block 1. In block 2, job 2 will have an internal fragmentation of 190k, 60k in block 3, block 4 is already busy and 5k in block 5. Job 2 will have the least internal fragmentation in block 5; therefore job 2 will be allocated to block 5. Next on the queue is job 3 with a size of 35k. Job 3 will have 15k internal fragmentation in block 1, 165k in block 2, 35k in block 3, block 4 and 5 are already busy. The least internal fragmentation is in block 1. Thus, job 3 will then be allocated to block 1. Next is job 4 with a size of 15k. Block 1 is busy by job 3, job 4 will have internal fragmentation of 185k in block 2, 55k in block 3, and blocks 4 and 5 are already busy with jobs 1 and 2 respectively. Thus, with an internal fragmentation of 55k, job 4 will be allocated to block 3. For job 5 with a size of 23k, block 1 is already busy by job 3, block 2 will have an internal fragmentation of 177k, and block 3, 4, and 5 are already busy by jobs 4, 1 and 2 respectively. Thus, job 5 will be allocated to block 2. The memory is now full. This is the first turnaround for the jobs, and the last for jobs 2 and 4. As the second turnaround starts, blocks 3 and 5 will now be free, and the second turnaround starts for jobs 1, 3, and 5. For job 6 with a size of 6k, blocks 1 and 2 are still busy, in block 3, the internal fragmentation is 64k, block 4 is busy, and block 5 will have 9k internal fragmentation. Thus, job 6 will be allocated to block 5. For job 7, with a size of 25k, blocks 1 and 2 are full, block 3 will have 45ik internal fragmentation, and blocks 4 and 5 are full, thus job 7 will be allocated to block 3. As the next turnaround starts, blocks 1, 2, 3 and 5 will now be free and this marks the last turnaround for job 1. Job 8 with a size of 55k will not fit in block 1, will have 145k internal fragmentation in block 2, 15k in block 3, block 4 is still busy, and block 5 cannot cater job 8. Therefore, job 8 will be allocated to block 3. Job 9 with a size of 88k will not fit in block 1, have 112k internal fragmentation in block 2, blocks 3 and 4 are busy, and block 5 will not be enough for job 9. Therefore, job 9 will be allocated to block 2. Job 10 has a size of 100k, and though blocks 1 and 5 are free, job 10 will not fit in either of them. Thus, job 10 will be in the waiting list. As the next turnaround starts, block 4 will now be free and this marks the last turnaround for job 8, and the second for job 9. Job 10 with a size of 100k will not fit in block 1, blocks 2 and 3 are still busy, block 4 will have 15k internal fragmentation, and in block 5, job 10 will not fit. Thus, job 10 will be allocated to block 4. There are no more jobs in the queue; therefore, the turnaround is ended. For the next turnaround, block 3 will be free, and this marks the last turnaround for job 9 and the second for job 10. As the turnaround ends, job 9’s turnaround will now end. The next turnaround will be the last turnaround for job 10 and thus, all the blocks will be freed as it ends.

The other method for free space allocation is First-fit memory allocation. In this method, the job will search from the top block down to the last and allocate the first block of memory that fits the job’s size. As for the given situation, the set of jobs will be allocated to the given fixed-partitioned memory using First-fit memory allocation. For the first turnaround, job 1 with a size of 100k and a turnaround of 3 will search from the top block down to the last for the first block that will fit for it. Block 1 with a memory size of 50k cannot cater job 1. Block 2 with a memory size of 200k will allocate job 1 since it is the first block of memory that fits the job’s size. Job 2 with a size of 10k and a turnaround of 1 will be allocated to block 1 since block 1’s memory size is 50k. As for job 3 which had a size of 35k and a turnaround of 2, block 1 is already busy with job 2, and block 2 is also busy with job 1. Block 3 is free and has a size of 70k, enough to cater job 3. Therefore, job 3 will be allocated to block 3. As for job 4 with a size of 15k and a turnaround of 1, blocks 1, 2, and 3 are busy. Block 4 with a size of 115k will allocate job 4. Job 5, with a size of 23k will not be allocated to any other block for this turnaround since the remaining block, which is block 5 only has 15k of memory. So, job 5 will be moved to the waiting list. Job 6 with a size of 6k and a turnaround of 1, blocks 1, 2, 3, and 4 are already busy. Block 5 with a size of 15k will allocate job 6. Since all the partitions are busy, the first turnaround will now end and all other jobs will be moved to the waiting list. Thus marks the end of the turnaround for jobs 2, 4 and 6. The next turnaround marks the second turnaround for job 1 and the last for job 3. Blocks 1, 4 and 5 are now free. Then job 5 with a size of 23k and a turnaround of 2 will be allocated to block 1 since it has 50k of memory. As for job 7 with a size of 25k and a turnaround of 1, blocks 1, 2 and 3 are busy with jobs 5, 1 and 3 respectively. Block 4 is free and has a size of 115k, enough to allocate job 7. Job 8 has a size of 55k, but blocks 1-4 are busy and block 5 has insufficient memory for it. Thus, it will wait for the next turnaround for a possible sufficient block of memory for it. The case is same with jobs 9 and 10, since its sizes are 88k and 100k respectively. As this turnaround ends, blocks 3 and 4 will be free. The next turnaround marks the last turnaround for jobs 1 and 5. As for job 8 with a size of 55k and a turnaround of 2, blocks 1 and 2 are still busy, and block 3 has a memory of 70k, enough for it. Thus, it will allocate Job 8. For job 9, with a size of 88k and a turnaround of 3, blocks 1-3 are busy, and block 4 with a size of 115k will allocate job 9. Job 10 with a size of 100k will no longer be allocated for this turnaround and will wait for the next since the remaining free block has insufficient memory for it. As this turnaround ends, jobs 1 and 5’s turnarounds will also end. For the next turnaround, this marks the second turnaround for job 9 and the last for job 8. Blocks 1, 2 and 5 are free. For job 10, with a size of 100k and a turnaround of 3, block 5, having 50k of memory will be insufficient for it. Block 2 has 200k of memory, thus job 10 will be allocated to block 2. There are no more waiting jobs. As this turnaround ends, job 8’s turnaround will end. The next turnaround will be the last for job 9 and the second for job 10. The end of this turnaround will also mark the end for job 9’s turnaround. The start of the next turnaround will be the last of job 10’s turnaround, and blocks 1, 3, 4 and 5 are free. The end of this turnaround also marks the end for job 10’s turnaround.

Another method for free space allocation is the Worst-fit memory allocation. In this method, the job will search from the top block down to the last and will be allocated to the block with the largest internal fragmentation or wasted memory space. In the given situation, the first turnaround will begin. For job 1 with a size of 100k and a turnaround of 3, it will not fit in block 1(50k), fits in block 2(200k) with an internal fragmentation of 100k,does not fit in block 3(70k), fits in block 4(115k) with an internal fragmentation of 15k, and does not fit in block 5(15k). Block 2(200k), having an internal fragmentation of 100k, being the largest internal fragmentation, will allocate memory for job 1. Job 2, with a size of 10k and a turnaround of 1, fits in block 1(50k) with 40k internal fragmentation, block 2 is already busy, fits in block 3(70k) with an internal fragmentation of 60k, fits in block 4(115k) with an internal fragmentation of 105k, and fits in block 5(15k) with 5k internal fragmentation. Block 4 will allocate job 2, being the block with the largest internal fragmentation. Job 3 with a size of 35k and a turnaround of 2, fits in block 1(50k) with an internal fragmentation of 15k, block 2 is busy, fits in block 3(70k) with 35k of internal fragmentation, block 4 is busy, and does not fit in block 5(6k). Thus, job 3 will be allocated to block 3. Job 4 with a size of 15k and a turnaround of 1, fits in block 1(50k) with an internal fragmentation of 35k, blocks 2, 3 and 4 are already busy, and fits in block 5(15k) with 0 internal fragmentation. Job 4 will now be allocated to block 1. Job 5 with a size of 23k, with blocks 1-6 already busy and block 5(15k) having insufficient memory size for it, will wait for the next turnaround. Job 6 with a size of 6k will be allocated to block 5(15k) since blocks 1-5 are busy. Since all the partitions are busy, the other jobs will no longer be allocated for this turnaround. This turnaround’s end will also mark the end for the turnarounds of jobs 2, 4 and 6. The next turnaround will be the second for job 1 and the last for job 3. Blocks 1, 4 and 5 are free. Job 5 with a size of 23k and a turnaround of 2, fits in block 1(50k) with an internal fragmentation of 27k, blocks 2 and 3 are busy, fits in block 4(115k) with an internal fragmentation of 92k, and will not fit in block 5(15k). Thus, job 5 will be allocated to block 4. Job 7 with a size of 25k and a turnaround of 1, will fit in block 1(50k) with an internal fragmentation of 25k, blocks 2-5 are busy and does not fit in block 5(15k). Hence, job 7 will be allocated to block 1. Job 8 has a memory of 55k, with the given situation that blocks 1-4 are busy and block 5 is insufficient, will wait for the next turnaround. Same with job 9 (88k) and job 10 (100k). The end of this turnaround will mark the end of the turnaround for jobs 7 and 3. The start of the next turnaround will mark the last turnaround for jobs 1 and 5. Blocks 1, 3 and 5 are free. Job 8 with a size of 55k and a turnaround of 2 will not fit in block 1(50k), block 2 is busy, fits in block 3(70k) with an internal fragmentation of 15k, block 4 is busy, and block 5 is insufficient. Thus, job 8 will be allocated to block 3. Job 9 with a size of 88k will not fit in block 1(50k), blocks 2-4 are busy, and will not fit in block 5(15k). Hence, job 9 will wait for the next turnaround. Job 10 with a size of 100k will also wait for the next turnaround since no other block fits its required size. This turnaround’s end will also be the end of jobs 1 and 5’s turnaround. The next turnaround will mark the last turnaround for job 8. Blocks 1, 2, 4, and 5 are free. Job 9 with a size of 88k and a turnaround of 3 will not fit in block 1(50k), fit in block 2(200k) with an internal fragmentation of 112k, block 3 is busy, fit in block 4(115k) with an internal fragmentation of 27k, but will not fit in block 5(15k). Therefore, job 9 will be allocated to block 2. Job 10 with a size of 100k and a turnaround of 3, will not fit in block 1(50k), blocks 2 and 3 are busy, fit in block 4(115k) with an internal fragmentation of 15k, but will not fit in block 5(15k). So, job 10 will be allocated to block 4. There are no more jobs to be allocated. When this turnaround ends, the turnaround for job 8 also ends. The start of the next turnaround will be the second turnaround of jobs 9 and 10. When the turnaround ends and start anew, that will be the final turnaround for jobs 9 and 10, and thus ending that turnaround results to the completion of the execution of the jobs for that certain program.