a. Job1 (100k) f. Job6 (6k)
turnaround: 3 turnaround: 1
b. Job2 (10k) g. Job7 (25k)
turnaround: 1 turnaround: 1
c. Job3 (35k) h. Job8 (55k)
turnaround: 2 turnaround: 2
d. Job4 (15k) i. Job9 (88k)
turnaround: 1 turnaround: 3
e. Job5 (23k) j. Job10 (100k)
turnaround: 2 turnaround: 3
Memory Block | Size |
Block 1 | 50K |
Block 2 | 200K |
Block 3 | 70K |
Block 4 | 115K |
Block 5 | 15K |
A. BEST-FIT ALGORITHM
The best-fit algorithm’s goal is to find a partition from the first block down to the last block in which the job fits the best in terms of lesser internal fragmentation and to be allocated.
The OS will check where it will allocate the first job by searching from the first block down to the last block; it will then compare all the expected internal fragmentations of all the blocks that can accommodate the first job which are blocks two and four; the internal fragmentations will be, in block two, 100K and, in block four, 15K. Obviously, job one will be allocated in block four because it has the least internal fragmentation. After that, the OS will get the next job which is job two. Again, the OS will check the blocks starting from the first block; compares all the internal fragmentations of the blocks that can accommodate job two; then allocates it to the block where it has the least internal fragmentation which is block five having only 5K internal fragmentation. Same process will be given to job 3. It will be allocated in block one creating a 15K internal fragmentation. Job 4 will be allocated at block three creating 55K internal fragmentation. Job 5 will be allocated at block two creating 177K internal fragmentation. And jobs six to ten asynchronously checks the blocks but all are busy so they will have to wait.
After the first turnaround, jobs two and four ends making way for job six that will be allocated at block five creating 9K internal fragmentation and job seven will be allocated at block 3 creating 45K internal fragmentation. Jobs eight to ten will still have to wait.
After the second turnaround, jobs three, five, six and seven ends then job eight will be allocated at block three creating 15K internal fragmentation and job nine will be allocated at block two creating 112K internal fragmentation. The remaining free blocks, blocks one and five, cannot accommodate job ten so it will still have to wait.
After the third turnaround, job one ends and job ten will be allocated at block four creating 15K internal fragmentation.
After the fourth turnaround, job eight ends. After the fifth turnaround, job nine ends. And finally after the sixth turnaround, job ten ends.
B. FIRST-FIT ALGORITHM
The first-fit algorithm’s goal is to find the first available block starting from the first block to allocate the job. The search must always start at the first block.
The OS will find a block where job one is to be allocated. It first checks the first block but block one has only 50K which means it cannot accommodate job one which needs 100K of memory. The OS now checks the second block; block two which has 200K can accommodate job one so the OS allocates job one to block two creating a 100K internal fragmentation. Then the OS fetches the next job which is job two; it will search from the first block; job one can accommodate job two so the OS allocates job two to block one creating a 40K internal fragmentation. The OS fetches job three; it searches from the first block. Block one has the capacity to accommodate job three but block one is still processing job two. Same thing happened on the next block where block two is still processing job one. The OS now checks block three it can accommodate the size of job three plus it is a free block so job three is allocated at block three creating 35K of internal fragmentation. Same process will be made to the remaining jobs. The OS fetches job four; it searches form the first block; all the first three blocks are busy; it reaches block four which can accommodate job four so the OS now allocates job four to block four creating a 100K internal fragmentation. Job five cannot be allocated in the remaining block, block five, so the OS puts job five in the waiting list. Job six can be accommodated by block five so the OS allocates job six to block five creating a 9K internal fragmentation. Jobs seven, eight, nine and ten are all put in the waiting list because all of the blocks are busy.
On the first turnaround, jobs two, four and six ends. The OS fetches the first job in the waiting list which is job five and by the same process; job five is allocated in block one creating an internal fragmentation of 27K.Next, Job seven is allocated in block four creating an internal fragmentation of 90K. Jobs eight, nine and ten are to big for block five so they are still on the waiting list. Block five is now considered an external fragmentation.
On the second turnaround, jobs three and seven ends. Job eight is fetched and is allocated in block three creating an internal fragmentation of 15K. Job nine is allocated in block four creating an internal fragmentation of 27K. Job 10 is fetched but the remaining block, fifth block, cannot accommodate it so it returns to the waiting list. Block five is still considered an external fragmentation.
On the third turnaround, jobs one and five ends. Job ten is finally allocated in block two creating an internal fragmentation of 100K.
On the fourth turnaround, job eight ends. On the fifth turnaround, job nine ends. On the sixth turnaround, job ten ends.
C. WORST-FIT
The worst-fit algorithm is somewhat the “antonym” of best-fit algorithm. It still has the same process as best-fit algorithm: OS fetches the job; computes the expected internal fragmentation of all the blocks that can accommodate the job starting in the first block down to the last block; but rather than allocating a job in a block where it can only create the least internal fragmentation like we did in the best-fit algorithm, worst-fit algorithm allocates a job in the block that has the largest expected internal fragmentation.
We learned in the best-fit algorithm part of this paper that job one can only be accommodated by block two, expecting 100K internal fragmentation, and block four, expecting 15K internal fragmentation. In the worst-fit algorithm, job one will be allocated in block two because it has the most internal fragmentation. With the same process, job two will be allocated in block four creating 105K internal fragmentation. Job three will be allocated in block three creating 35K internal fragmentation. Job four in block one creating 35K internal fragmentation. Job five cannot be accommodated by block five so job five is put in the waiting list. Job 6 however can be accommodate in block five so job five is allocated in block five creating 9K internal fragmentation. Jobs seven to ten are put in the waiting list because there are no available blocks.
On the first turnaround, jobs two, four and six ends. Job five is allocated in block four creating 92K internal fragmentation. Job seven is allocated in block one creating 25K internal fragmentation. Jobs eight to ten cannot be accommodated by block five due to lack of size so they are still put into the waiting list creating block five an internal fragmentation.
On the second turnaround, job three and job seven ends. The OS checks the available blocks, blocks one three and five, if they can accommodate job eight but unfortunately they can’t. Same thing happened on jobs nine and ten so they are all put into the waiting list creating block one, block three and block five as internal fragmentations.
On the third turnaround, job one and job five ends. Job eight is allocated in block two creating an internal fragmentation of 145K. Job nine is allocated in block four creating 26K internal fragmentation. There are no blocks that can accommodate job ten so it is put in the waiting list creating block one, block three and block five internal fragmentations.
On the fourth turnaround, still there are no blocks that can accommodate job ten. On the fifth turnaround, job eight ends making way for job ten to be allocated in block two creating 100K internal fragmentation.
On the sixth turnaround, job nine ends. On the seventh turnaround, nothing happens. On the eight turnaround, job ten ends.
No comments:
Post a Comment