Any help on the below would great be looked up upon. i) Assume that you have a d
ID: 3723568 • Letter: A
Question
Any help on the below would great be looked up upon.
i) Assume that you have a demand paged memory. It takes 7.5 milliseconds to service a page fault. The TLB hit rate is 20 percent. The TLB access time is 18 nanoseconds. Memory access time is 100 nanoseconds. The page fault rate is .001. What is the EAT?
ii) Given five memory partitions of 100 KB, 300 KB, 200 KB, 500 KB, and 400 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 200KB, 417 KB, 100 KB, 350 KB and 100 KB (arriving in order)?
Explanation / Answer
i) We are given -
Page fault rate (p) : 0.001
Page fault time : 7.5 ms or 7500000 ns
TLB hit rate (h): 0.2
TLB access time: 18 ns
TLB miss rate (m): 0.8 (1 - TLB hit rate)
Memory access time: 100 ns
The most frequently used pages are kept in the TLB for easy access, so we first search for a page in the TLB. TLB hit rate is the probability that the page we are looking for is present in the TLB. In this case, we only need to fetch the page from TLB which takes TLB access time.
However, TLB miss rate (1 - TLB hit rate) is the probability that the page is not in the TLB.
Here two things can occur - either the page is in the main memory or not (ie. it is in the secondary memory).
a) If the page is not in the main memory, then a page fault occurs. In this case, we have to fetch the page from the disk. This takes the time needed to service a page fault.
b) If the page is in the main memory (this happens (1 - page fault rate) times). Here we need to consider only the main memory access time.
So Effective Access Time = {(Prob. that page is in the TLB) * (TLB access time)} + {(Prob. that page is not in the TLB)[{(Prob. that page is in main memory) * (Main memory access time)} + {(Prob. that page is not in main memory) * (Secondary memory access time)}]}
EAT = (TLB hit rate * TLB access time) + (1 - TLB hit rate) * (([1 - page fault rate] * memory access time) + (page fault rate * sec memory access time))
= (0.2 * 18) + 0.8 * ((1 - 0.001) * 100 + 0.001 * 7500000)
= 3.6 + 0.8 * (99.9 + 7500)
= 3.6 + 0.8 * 7599.9
= 3.6 + 6079.92
= 6083.52 ns
ii) FIRST FIT: place the process in the first memory partition that is big enough to hold that process.
Given memory partitions are - 100KB, 300KB, 200KB, 500KB AND 400KB.
The first process has size 200KB. Since 100KB (first memory partition) is not big enough to hold this process, move on to the second memory partition. This partition has size 300KB and since it is greater than 200KB, we will place this process in the second partition.
Now, remaining memory partitions are - 100KB, (300-200) = 100KB, 200KB, 500KB, 400KB.
The second process has size = 417KB. From the available memory partitions (from left to right), the fourth partition of size 500KB is big enough to hold the second process (417KB). Thus, place the second process here.
Remaining Memory : 100KB, 100KB, 200KB, (500-417) = 83KB, 400KB
Similarly, place the third process of size 100KB in the first memory partition.
Remaining Memory: (100-100) = 0KB, 100KB, 200KB, 83KB, 400KB
Place the fourth process of size = 350KB in the fifth memory partition
Remaining Memory: 0KB, 100KB, 200KB, 83KB, (400-350) = 50KB.
Place the final process of size = 100KB in second memory partition.
Remaining memory: 0KB, (100-100) = 0 KB, 200KB, 83KB, 50KB.
Total memory unutilized = 200+83+50 = 333KB.
BEST FIT: Place the process in the memory partition that would minimize wastage of space and thus, is best to hold a given process. That is, place the process in the smallest partition big enough to hold the process.
Mem : 100KB, 300KB, 200KB, 500KB, 400KB
The first process of size = 200KB will be placed in the third memory partition of size 200KB.
Mem: 100KB, 300KB, (200-200) = 0KB, 500KB, 400KB.
Place the second one in the fourth partition of size 500KB.
Mem: 100KB, 300KB, 0KB, (500-417)=83KB, 400KB.
Place the third process in the first partition of size 100KB.
Mem: (100-100)=0KB, 300KB, 0KB, 83KB, 400KB.
Place the fourth one in the fifth memory partition of size 400KB.
Mem: 0KB, 300KB, 0KB, 83KB, 50KB.
Place the last process in the second partition.
Mem: 0KB, (300-100)=200KB, 0KB, 83KB, 50KB.
Total unutilized memory = 200+83+50 = 333KB.
WORST FIT: Place the process in the largest partition available that can accommodate the process.
Mem: 100KB, 300KB, 200KB, 500KB, 400KB
Place the first process in the fourth partition of size 500KB, since it is the largest available partition to hold a process of size 200KB.
Mem: 100KB, 300KB, 200KB, (500-200)=300KB, 400KB.
Next process of size 417KB is greater than any available memory partition, therefore it cannot be placed in the memory.
Next process will be placed in the fifth memory partition of size 400KB.
Mem: 100KB, 300KB, 200KB, 300KB, (400-100) = 300KB.
Next process of size = 350KB can again not be placed in memory since its size exceeds that of available memory partitions.
Finally, the last process of size 100KB will be placed in the second memory partition (or equivalently in fourth or fifth) because each has a size = 300KB.
Mem: 100KB, (300-100) = 200KB, 200KB, 300KB, 300KB.
Total memory unutilized = 100+200+200+300+300 = 1100KB. Also, two processes could not be placed in any memory partition.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.