Memory Allocation a) Is it possible to have both internal and external fragmenta
ID: 3767531 • Letter: M
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.
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:
a) First-Fit
b) Best-Fit
c) Worst-Fit.
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
II. File System Implementation
List three methods of allocating files on magnetic disk as discussed in lecture. For each method, list an advantage, a disadvantage, and draw a diagram showing how a file named x containing 5 blocks would be represented.
Explanation / Answer
Fixed partition: Has internal fragmentation because memory blocks are of fixed size and processes assigned to them may not need the full memory amount. Has no external fragmentation because the fixed blocks are contiguous and internal fragments cannot be allocated to different processes.
Dynamic/variable partition: Has no internal fragmentation because requested memory block is the same size as the memory block assigned. Has external fragmentation because holes formed from switching processes are noncontiguous.
P2, P4, and P6 are finished
1000K
1000K
Reserved 100k
Reserved 100K
P1 : 100K
P1 : 100K
P2 : 100K
100K Free
P3 : 25K
P3 : 25K
P4 : 200K
200K Free
P5 : 200K
P5 : 200K
P6 : 75K
75K Free
P7 : 100K
P7 : 100K
Free 100K
Free 100K
Initial Memory Allocation Diagram
Best Fit Algorithm
Process P8 150K
Process P9 25K
Process P10 50K
Process P11 25K
1000K
1000K
1000K
1000K
Reserved 100K
Reserved 100K
Reserved 100K
Reserved 100K
P1 : 100K
P1 : 100K
P1 : 100K
P1 : 100K
100K Free
100K Free
P10 : 50K
50K Free
P10 : 50K
50K Free
P3 : 25K
P3 : 25K
P3 : 25K
P3 : 25K
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P5 : 200K
P5 : 200K
P5 : 200K
P5 : 200K
75K Free
P9 : 25K
50K Free
P9 : 25K
50K Free
P9 : 25K
50K Free
P7 : 100K
P7 : 100K
P7 : 100K
P7 : 100K
Free 100K
Free 100K
Free 100K
P11 : 25K
75K Free
First Fit Algorithm
Process P8 150K
Process P9 25K
Process P10 50K
Process P11 25K
1000K
1000K
1000K
1000K
Reserved 100K
Reserved 100K
Reserved 100K
Reserved 100K
P1 : 100K
P1 : 100K
P1 : 100K
P1 : 100K
100K Free
P9 : 25K
75K Free
P9 : 25K
75K Free
P10 : 50K
50K Free
P3 : 25K
P3 : 25K
P3 : 25K
P3 : 25K
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P5 : 200K
P5 : 200K
P5 : 200K
P5 : 200K
75K Free
75K Free
P10 : 50K
25K Free
P9 : 25K
50K Free
P7 : 100K
P7 : 100K
P7 : 100K
P7 : 100K
Free 100K
Free 100K
Free 100K
P11 : 25K
75K Free
Worst Fit Algorithm
Process P8 150K
Process P9 25K
Process P10 50K
Process P11 25K
1000K
1000K
1000K
1000K
Reserved 100K
Reserved 100K
Reserved 100K
Reserved 100K
P1 : 100K
P1 : 100K
P1 : 100K
P1 : 100K
100K Free
P9 : 25K
75K Free
P9 : 25K
75K Free
P10 : 50K
50K Free
P3 : 25K
P3 : 25K
P3 : 25K
P3 : 25K
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P5 : 200K
P5 : 200K
P5 : 200K
P5 : 200K
75K Free
75K Free
75K Free
P9 : 25K
50K Free
P7 : 100K
P7 : 100K
P7 : 100K
P7 : 100K
Free 100K
Free 100K
P10 : 50K
50K Free
P10 : 50K
50K Free
2) Three Methods of Memory Allocation are
Contiguous allocation – each file occupies set of contiguous blocks
Advantages
Drawbacks
Linked allocation - Each file a linked list of blocks. Each block also contains pointer to next block. File ends at nil pointer.
Advantages
Disadvantages
FAT (File Allocation Table) variation - Beginning of volume has table, indexed by block number.
Indexed allocation - Each file has its own index block(s) of pointers to its data blocks.
Advantages
Disadvantages
Variation of Indexed Allocation
Comparison to Indexed Allocation
P2, P4, and P6 are finished
1000K
1000K
Reserved 100k
Reserved 100K
P1 : 100K
P1 : 100K
P2 : 100K
100K Free
P3 : 25K
P3 : 25K
P4 : 200K
200K Free
P5 : 200K
P5 : 200K
P6 : 75K
75K Free
P7 : 100K
P7 : 100K
Free 100K
Free 100K
Initial Memory Allocation Diagram
Best Fit Algorithm
Process P8 150K
Process P9 25K
Process P10 50K
Process P11 25K
1000K
1000K
1000K
1000K
Reserved 100K
Reserved 100K
Reserved 100K
Reserved 100K
P1 : 100K
P1 : 100K
P1 : 100K
P1 : 100K
100K Free
100K Free
P10 : 50K
50K Free
P10 : 50K
50K Free
P3 : 25K
P3 : 25K
P3 : 25K
P3 : 25K
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P5 : 200K
P5 : 200K
P5 : 200K
P5 : 200K
75K Free
P9 : 25K
50K Free
P9 : 25K
50K Free
P9 : 25K
50K Free
P7 : 100K
P7 : 100K
P7 : 100K
P7 : 100K
Free 100K
Free 100K
Free 100K
P11 : 25K
75K Free
First Fit Algorithm
Process P8 150K
Process P9 25K
Process P10 50K
Process P11 25K
1000K
1000K
1000K
1000K
Reserved 100K
Reserved 100K
Reserved 100K
Reserved 100K
P1 : 100K
P1 : 100K
P1 : 100K
P1 : 100K
100K Free
P9 : 25K
75K Free
P9 : 25K
75K Free
P10 : 50K
50K Free
P3 : 25K
P3 : 25K
P3 : 25K
P3 : 25K
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P5 : 200K
P5 : 200K
P5 : 200K
P5 : 200K
75K Free
75K Free
P10 : 50K
25K Free
P9 : 25K
50K Free
P7 : 100K
P7 : 100K
P7 : 100K
P7 : 100K
Free 100K
Free 100K
Free 100K
P11 : 25K
75K Free
Worst Fit Algorithm
Process P8 150K
Process P9 25K
Process P10 50K
Process P11 25K
1000K
1000K
1000K
1000K
Reserved 100K
Reserved 100K
Reserved 100K
Reserved 100K
P1 : 100K
P1 : 100K
P1 : 100K
P1 : 100K
100K Free
P9 : 25K
75K Free
P9 : 25K
75K Free
P10 : 50K
50K Free
P3 : 25K
P3 : 25K
P3 : 25K
P3 : 25K
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P8 : 150K
50K Free
P5 : 200K
P5 : 200K
P5 : 200K
P5 : 200K
75K Free
75K Free
75K Free
P9 : 25K
50K Free
P7 : 100K
P7 : 100K
P7 : 100K
P7 : 100K
Free 100K
Free 100K
P10 : 50K
50K Free
P10 : 50K
50K Free