Question

4. Worst-fit is an allocation algorithm that allocates the largest free block to a new job. It is the opposite of the best-fit algorithm. Using the following configuration with jobs arriving in order (Job A, B, C, D) and with blocks shown in order from low order memory to high order memory:

Job List:			Memory Block List:
Job Number	Memory Requested		Memory Block	Memory Block Size
Job A	44K		Block 1	250K
Job B	220K		Block 2	900K
Job C	670K		Block 3	280K
Job D	64K		Block 4	200K
			Block 5	750K

a) Indicate which memory blocks are allocated to each of the arriving jobs.

b) In this chapter we introduced external and internal fragmentation. Explain in your own words which one would be expected in a worst-fit memory allocation scheme

Answer 1

Memory Block	Size	Job#
Block 1	250k
Block 2	900k	Job A
Block 3	280k	Job D
Block 4	200k
Block 5	750k	Job B

Blocks allocation as per above table in the first iteration. Since Job C would take a memory space of 670k it will have to wait until memory space is created. Now since the Job A requires least memory it would be the first one to finish up, so in the next iteration Job C would replace Job A in block 2 and the allocation would look like below:

b) External or Internal Memory Fragmentation for Worst Fit Algorithm

Internal memory fragmentation occurs in case of fixed size partitions while external fragmentation takes place when the memory is dynamically allocated to the process as and when the requests arrive. In case of worst case algorithm, the largest block is assigned to the first arriving job. As can be seen from the example above, Job C had to wait until entire Block 2 got free, while if we see from an elevated level, there was enough space in the entire memory space for Job C to have executed. This results in external fragmentation when worst fit algorithm is applied. Even though presence of free memory is there due to non-consumption of entire memory space by a process, another process has to be kept on hold until an entire block with required memory is available.