# Andrew S. Tanenbaum (OS) Edition 4 Exercise 3 Question 11 (Page No. 255)

25 views

Consider the following C program:

int X[N];
int step = M; /* M is some predefined constant */
for (int i = 0; i < N; i += step) X[i] = X[i] + 1;
1. If this program is run on a machine with a $4-KB$ page size and $64$-entry $TLB,$ what values of $M$ and $N$ will cause a $TLB$ miss for every execution of the inner loop?
2. Would your answer in part $(a)$ be different if the loop were repeated many times? Explain.

So you know that the page size is 4 Kbytes. So if there is an array lets say of infinite length. You are accessing it from 0 to infinity in a for loop. The first access of the array X will cause a TLB miss and load the first TLB. then for next 4095 accesses, it will not be missed because it is present in the TLB( remember this is because the Page size is 4096 = 4KB ) So then the next address is X which will cause a TLB miss. Thus you see that for every 4096 address increments you will have a TLB miss. So we are sure that M = 4096/sizeof(int).

Now you also know that you have 64-entry TLB cache. So after 64 entries of TLB are loaded, you will have a full TLB. To load the 65th entry, you will have to remove the first entry. So you need the size of 64 * 4096 = 256 KBytes, to fully utilize the TLB cache. However you want to have a TLB cache miss for every step. So for 64 entry TLB cache you need array size which will be equivalent to 65 entries. Thus N = 65 * 4096 / sizeof(int).

## Related questions

1
70 views
Write a program that can be used to compare the effectiveness of adding a tag field to $TLB$ entries when control is toggled between two programs. The tag field is used to effectively label each entry with the process id. Note that a nontagged $TLB$ can be ... your simulation behaves as expected for a simple (but nontrivial) input example. Plot the number of $TLB$ updates per $1000$ references.
How can the associative memory device needed for a $TLB$ be implemented in hardware, and what are the implications of such a design for expandability?
A computer whose processes have $1024$ pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is $5\: nsec.$ To reduce this overhead, the computer has a $TLB,$ which holds $32$ (virtual page, physical page frame) pairs, and can do a lookup in $1\: nsec.$ What hit rate is needed to reduce the mean overhead to $2\: nsec?$
You are given the following data about a virtual memory system: The $TLB$ can hold $1024$ entries and can be accessed in $1$ clock cycle $(1\: nsec).$ A page table entry can be found in $100$ clock cycles or $100\: nsec.$ The average page replacement time is $6\: msec.$ ... by the $TLB\:\: 99\%$ of the time, and only $0.01\%$ lead to a page fault, what is the effective address-translation time?