Question

Memory Allocation

a) Is it possible to have both internal and external fragmentation with fixed partition memory allocation? How about with dynamic/variable memory partition allocation? Explain. (1 point)

b) Suppose we have 1000K of memory where the first 100K is reserved. Also suppose that the following processes have been allocated memory in the following order:

                P1: 100K, P2: 100K, P3: 25K, P4: 200K, P5: 200K, P6: 75K, P7: 100K.

Create a diagram of memory.

Suppose that P2, P4, and P6 finish and the following processes are on the queue waiting for memory (assume FIFO):

                P8: 150K, P9: 25K, P10: 50K, P11: 25K.

Create a diagram of memory for each of the following algorithms showing how the memory would be allocated:

1. First-Fit ( 1.5 points)
2. Best-Fit (2 points)
3. Worst-Fit. (1.5 points)

Notes:

• Assume that the algorithm starts at the lowest address of memory to determine each new allocation for First-Fit.
• If there is a ‘tie’, that is, two locations in memory where a process could be loaded, use the lower/smaller address.

Answer 1

a) Fixed partition: The system of dividing memory into non-overlapping sizes that are fixed, unmovable and static. As it is contiguous allocation, hence no spanning is allowed. The partitions are made before the execution of the programs.

Fixed partition memory allocation suffers both internal and external fragmentation.

Let us assume memory with fixed partitions of 4MB each and 3 process with 1MB, 2MB, 3MB size are loaded into these partitions.

1MB

3MB(free)

2MB

2MB(free)

3MB

1MB(free)

From the above allocation, it is clearly seen that internal fragmentation exists for these 3 partitions as there is unusable free space exist in every partition.

If a 4^th process with 4MB size cannot be allocated space, even though there exists 6 MB unused space exists, because of contiguous allocation. This is called external fragmentation in fixed size partition.

Variable/Dynamic Partition: Partitions are not made before the execution or during system configure. Partitions are made during run-time based on the process size. So, there will be no internal fragmentation.

But, there exists external fragmentation if some non contiguous, small sized (2MB & 2MB) processes completes execution, the free space can not be utilized for process with 3MB size (because process allocation needs to be contiguous).

b)

Total Memory : 1000 K

Pre-Condition: First 100 K is reserved.

The memory allocation for the given processes is :

Process:	(Res)	P1	P2	P3	P4	P5	P6	P7
Partition Size	100K	100K	100K	25K	200K	200K	75K	100K	100K

Memory diagram after completing P2, P4 and P6 processes:

Process:	(Res)	P1		P3		P5		P7
Partition Size	100K	100K	100K	25K	200K	200K	75K	100K	100K

a) First Fit: (Memory is allocated to first available memory)

For P8: 150 K,

Process	(Res)	P1		P3	P8		P5		P7
Partition Size	100K	100K	100K	25K	150K	50K	200K	75K	100K	100K

For P9: 25K,

Process:	(Res)	P1	P9		P3	P8		P5		P7
Partition Size	100K	100K	25K	75K	25K	150K	50K	200K	75K	100K	100K

For P10:50K, P11:25 K,

Process:

(Res)

P1

P9

P10

P11

P3

P8

P5

P7

Partition Size

100K

100K

25K

50K

25K

25K

150K

50K

200K

75K

100K

100K

b) Best-Fit:

For P8:150K

Process:	(Res)	P1		P3	P8		P5		P7
Partition Size	100K	100K	100K	25K	150K	50K	200K	75K	100K	100K

For P9: 25K,

Process:	(Res)	P1		P3	P8	P9		P5		P7
Partition Size	100K	100K	100K	25K	150K	25K	25K	200K	75K	100K	100K

For P10:50K, P11:25K

Process:

(Res)

P1

P3

P8

P9

P11

P5

P10

P7

Partition Size

100K

100K

100K

25K

150K

25K

25K

200K

50K

25K

100K

100K

c) Worst Fit: (Allocate from long chunk of memory)

For P8:150K

Process	(Res)	P1		P3	P8		P5		P7
Partition Size	100K	100K	100K	25K	150K	50K	200K	75K	100K	100K

For P9: 25K,

Process	(Res)	P1	P9		P3	P8		P5		P7
Partition Size	100K	100K	25K	75K	25K	150K	50K	200K	75K	100K	100K

For P10:50K, P11 25K

Process

(Res)

P1

P9

P11

P3

P8

P5

P7

P10

Partition Size

100K

100K

25K

25K

50K

25K

150K

50K

200K

75K

100K

50K

50K