Numericals
Question 1
Consider the memory partitions of size 100 KB, 500 KB, 200 KB, 300 KB, 600 KB ( in
order). These partitions need to be allocated to four processes of sizes 212 KB, 417 KB, 112
KB and 426 KB in that order.
Perform the allocation of processes using-
First Fit Algorithm
Best Fit Algorithm
Worst Fit Algorithm
Which algorithm performs better in terms of memory usage.
Solution
Using MFT
First Fit (Searching free partition from current position / 1st position )
Partitions Process allocated Internal
Fragmentation
100 KB
500 KB 212 KB 500-212=288 KB
200 KB 112 KB 200-112=88 KB
300 KB
600 KB 417 KB 600-417=183 KB
Process with 426 KB waits
Total Internal Fragmentation = 288 + 88 + 183 = 559 KB
External Fragmentation = 100 + 300 = 400 KB
Best Fit
Partitions Process allocated Internal
Fragmentation
100 KB
500 KB 417 KB 500-417=83 KB
200 KB 112 KB 200-112=88 KB
300 KB 212 KB 300-212=88 KB
600 KB 426 KB 600-426=174 KB
Total Internal Fragmentation = 83+88+88+174= 433 KB
External Fragmentation = 100 KB
Worst Fit
Partitions Process allocated Internal
Fragmentation
100 KB
500 KB 417 KB 83 KB
200 KB
300 KB 112 188 KB
600 KB 212 KB 600-212=388 KB
Process with 426 KB waits
Total Internal Fragmentation = 83+188+388=659 KB
External Fragmentation = 100 + 200 = 300 KB
Using MVT
First Fit (Searching free partition from current position)
Partitions Process Holes Process Holes
allocated allocated
100 KB
500 KB 212 KB 500-212=288
KB
200 KB
300 KB
600 KB 417 KB 600-417=183 112 KB 183-112=71 KB
KB
Process with 426 KB waits
External Fragmentation = 100 + 288 + 200 + 300 + 71 = 959 KB
First Fit (Searching free partition from 1st position)
Partitions Process Holes Process Holes
allocated allocated
100 KB
500 KB 212 KB 500-212=288 112 KB 288-112=176
KB KB
200 KB
300 KB
600 KB 417 KB 600-417=183
KB
Process with 426 KB waits
External Fragmentation = 100 + 176 + 200 + 300 + 183 = 959 KB
Best Fit
Partitions Process allocated Holes
100 KB
500 KB 417 KB 500-417=83 KB
200 KB 112 KB 200-112=88 KB
300 KB 212 KB 300-212=88 KB
600 KB 426 KB 600-426=174 KB
External Fragmentation = 100 + 83 + 88 + 88 + 174 = 533 KB
Worst Fit
Partitions Process Holes Process Holes
allocated allocated
100 KB
500 KB 417 KB 500-417=83
KB
200 KB
300 KB
600 KB 212 KB 600-212=388 112 KB 388-112=276
KB KB
Process with 426 KB waits
External Fragmentation = 100 + 83 + 200 + 300 + 276 = 959 KB
Question 2
Consider a logical address space of 32 pages of 1024 words each, mapped onto a physical
memory of 64 frames.
i. How many bits are there in the logical address?
ii. How many bits are there in the physical address?
Since page size=frame size=1024 words
Logical address space = 32 x 1024 = 25 x 210 =215 words. So 15 bits are needed to designate
each logical address.
Physical address space = 64 x 1024 = 26 x 210 = 216 words. So 16 bits are needed to designate
each physical address.
Question 3
Given 16 bits logical address, find the following:
a) No. of bits required to designate page no. and no. of bits to designate page offset
when mapping a logical address to physical address
b) Total number of pages
c) Total number of offsets in each page
(a) 16 bits logical address implies m=16, page size= 2 KB= 2x 210 = 211 (n=11)
No. of bits required to designate page no. = (m - n) = (16 - 11) = 5
No. of bits required to designate page offset = n =11.
(b) Total no. of pages= 25=32
(c) Total number of offsets in each page=211 (0 to 211 – 1)
Question 4
If page size=2048 bytes and process size=72,766 bytes, then compute the following:
(a) Number of pages needed for a process to be allocated.
(b) Internal fragmentation.
(a) Total no. of pages = process size / page size = 72766 / 2048 =35.53 = 36 pages
(b) Internal fragmentation =
Method 1
35 pages occupy 35 x 2048 =71680 bytes
36th page occupies 72766 – 71680 = 1086 bytes. So internal fragmentation = 2048 –
1086 =962 bytes
Method 2
(36 x 2048) – 72766 = 73728 – 72766 = 962 bytes
Question 5
Consider a logical address space of 31 KB and a page of size 2 KB. Answer the following
giving explanation:
(a) Total no. of pages required to handle the logical address of size 31 KB.
(b) Total internal fragmentation assuming a frame of size 2 KB.
(a) 31 / 2 =15.5 = 16 pages
(b) 15 frames are full and 16th frame has 1 KB. So internal fragmentation= 1 KB
Question 6
Assuming a 1-KB page size, what are the page numbers and offsets for the following
address references (provided as decimal numbers):
3085
42095
365
42095
Given Page size =1 KB=1024 bytes
Method 1
(a) 3085 / 1024 quotient represents page no and remainder represents page offset
Page no 3, page offset = 13
Method 2
Find binary equivalent of 3085 = 110000001101
Page size =1 KB=1024 bytes= 210 bytes => n=10
3085 = 11 0000001101
(11)2 = (3)10
(0000001101)2 = (13)10
Page no=3, page offset=13
Question 7
Consider a computer system with a 32-bit logical address and 4 KB page size. The system
supports up to 512 MB of physical memory. Find the total no. of pages (entries) in page
table and the total no. of frames in physical memory.
Total no. of pages = logical address space / page size
= 232 / (22x210) = 220
Total no. of frames = physical address space / frame size
frame size=page size=4 KB
Total no. of frames =(29 x 220) / (22 x 210) = 217
Question 8
If one page table entry occupies 32 bits and frame size = 4 KB, Compute size of physical
memory.
Page table entry contains base address of page in memory (i.e. frame address). Since frame
address is specified by 32 bits, therefore total no. of frames = 232
Physical memory size = total no. of frames x frame size = 232 x 4 KB = 232 x 22 x 210 =244 = 16
TB (Tera Bytes)
Question 9
Consider the following segment table:
Segment Base Length
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
What are the physical addresses for the following logical addresses?
a. 0,430
b. 1,10
c. 2,500
d. 3,400
e. 4,112
(a) Logical address= <0, 430>
n Computation of physical address (PA):
n Segment number 0 is valid.
n Offset 430 < 600. So PA= base+offset = 219 + 430 = 649.
(b) Logical address = <1,10>
n Segment number 1 is valid.
n Offset 10 < 14. So PA= base+offset = 2300 + 10 =2310
(c) Logical address = <2, 500>
n Segment number 2 is valid.
n Offset 500 > 100. Error: offset has exceeded the limit size. So PA can not be
computed.