# Recent questions tagged paging

1 vote
1
A CPU generates $32$-bit virtual addresses. The page size is $4$ KB. The processor has a Translation Look-aside Buffer (TLB) which can hold a total of $128$ page table entries and is $4$-way set associative. The minimum size of the TLB tag is $\text{11 bits}$ $\text{13 bits}$ $\text{15 bits}$ $\text{20 bits}$
1 vote
2
In a paging system, it takes $30$ ns to search translation Look-a-side Buffer (TLB) and $90$ ns to access the main memory. If the TLB hit ratio is $70\%$, the effective memory access time is : $48$ ns $147$ns $120$ns $84$ns
3
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.
4
Write a program that simulates a toy paging system that uses the $\text{WSClock}$ algorithm. The system is a toy in that we will assume there are no write references (not very realistic), and process termination and creation are ignored (eternal life). The ... per $1000$ memory references. Explain what is needed to extend the program to handle a page reference stream that also includes writes.
5
Write a program that simulates a paging system using the aging algorithm. The number of page frames is a parameter. The sequence of page references should be read from a file. For a given input file, plot the number of page faults per $1000$ memory references as a function of the number of page frames available.
6
Plot a histogram and calculate the mean and median of the sizes of executable binary files on a computer to which you have access. On a Windows system, look at all .exe and .dll files; on a UNIX system look at all executable files in /bin, /usr/bin, ... assumption about the size of a page table entry. Assume that all programs are equally likely to be run and thus should be weighted equally.
7
Virtual memory provides a mechanism for isolating one process from another. What memory management difficulties would be involved in allowing two operating systems to run concurrently? How might these difficulties be addressed?
8
Can you think of any situations where supporting virtual memory would be a bad idea, and what would be gained by not having to support virtual memory? Explain.
9
We consider a program which has the two segments shown below consisting of instructions in segment $0,$ and read/write data in segment $1.$ Segment $0$ has read/execute protection, and segment $1$ has just read/write protection. The memory system is a demand- paged virtual memory system ... $16$ Fetch from segment $1,$ page $4,$ offset $28$ Jump to location in segment $1,$ page $3,$ offset $32$
10
When segmentation and paging are both being used, as in $MULTICS,$ first the segment descriptor must be looked up, then the page descriptor. Does the $TLB$ also work this way, with two levels of lookup?
11
Explain the difference between internal fragmentation and external fragmentation. Which one occurs in paging systems? Which one occurs in systems using pure segmentation?
12
A machine-language instruction to load a $32-bit$ word into a register contains the $32-bit$ address of the word to be loaded. What is the maximum number of page faults this instruction can cause?
13
A group of operating system designers for the Frugal Computer Company are thinking about ways to reduce the amount of backing store needed in their new operating system. The head guru has just suggested not bothering to save the program text in the swap area at all, but just ... conditions, if any, does this idea work for the program text? Under what conditions, if any, does it work for the data?
1 vote
14
It has been observed that the number of instructions executed between page faults is directly proportional to the number of page frames allocated to a program. If the available memory is doubled, the mean interval between page faults is also doubled. Suppose that a normal instruction ... which time it gets $15,000$ page faults, how long would it take to run if twice as much memory were available?
15
A computer provides each process with $65,536$ bytes of address space divided into pages of $4096$ bytes each. A particular program has a text size of $32,768$ bytes, a data size of $16,386$ bytes, and a stack size of $15,870$ bytes. Will this program fit in the ... were $512$ bytes, would it then fit? Each page must contain either text, data, or stack, not a mixture of two or three of them.
16
One of the first timesharing machines, the $DEC\: PDP-1,$ had a (core) memory of $4K\: 18-bit$ ... drum. The drum could start writing (or reading) at any word, rather than only at word $0.$ Why do you suppose this drum was chosen?
17
You have been hired by a cloud computing company that deploys thousands of servers at each of its data centers. They have recently heard that it would be worthwhile to handle a page fault at server A by reading the page from the RAM memory of some other server rather than its local disk drive. How could that be done? Under what conditions would the approach be worthwhile? Be feasible?
1 vote
18
How long does it take to load a $64-KB$ program from a disk whose average seek time is $5\: msec,$ whose rotation time is $5 msec,$ and whose tracks hold $1\: MB$ for a $2-KB$ page size? for a $4-KB$ page size? The pages are spread randomly around the disk and the number of cylinders is so large that the chance of two pages being on the same cylinder is negligible.
19
A student in a compiler design course proposes to the professor a project of writing a compiler that will produce a list of page references that can be used to implement the optimal page replacement algorithm. Is this possible? Why or why not? Is there anything that could be done to improve paging efficiency at run time?
1 vote
20
A machine has $48-bit$ virtual addresses and $32-bit$ physical addresses. Pages are $8\: KB.$ How many entries are needed for a single-level linear page table?
21
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?
22
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?$
23
Below is an execution trace of a program fragment for a computer with $512-byte$ pages. The program is located at address $1020,$ and its stack pointer is at $8192\:\:($the stack grows toward $0).$ Give the page reference string generated by this ... Subtract the immediate constant $16$ from the stack pointer Compare the actual parameter to the immediate constant $4$ Jump if equal to $5152$
24
A computer has $32-bit$ virtual addresses and $4-KB$ pages. The program and data together fit in the lowest page $(0–4095)$ The stack fits in the highest page. How many entries are needed in the page table if traditional (one-level) paging is used? How many page table entries are needed for two-level paging, with $10$ bits in each part?
25
Section $3.3.4$ states that the Pentium Pro extended each entry in the page table hierarchy to $64$ bits but still could only address only $4\: GB$ of memory. Explain how this statement can be true when page table entries have $64$ bits.
26
Suppose that a machine has $438-bit$ virtual addresses and $32-bit$ physical addresses. What is the main advantage of a multilevel page table over a single-level one? With a two-level page table, $16-KB$ pages, and $4-byte$ entries, how many bits should be allocated for the top-level page table field and how many for the next level page table field? Explain.
1 vote
27
Suppose that a machine has $48-bit$ virtual addresses and $32-bit$ physical addresses. If pages are $4\: KB$, how many entries are in the page table if it has only a single level? Explain. Suppose this same system has a $TLB$ (Translation Lookaside Buffer ... and it sequentially reads long integer elements from an array that spans thousands of pages. How effective will the $TLB$ be for this case?
A machine has a $32-bit$ address space and an $8-KB$ page. The page table is entirely in hardware, with one $32-bit$ word per entry. When a process starts, the page table is copied to the hardware from memory, at one word every $100\: nsec.$ If each process runs for $100\: msec$ (including the time to load the page table), what fraction of the $CPU$ time is devoted to loading the page tables?
If an instruction takes $1\: nsec$ and a page fault takes an additional $n\: nsec,$ give a formula for the effective instruction time if page faults occur every $k$ instructions.
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; If this program is run on a machine with a $4-KB$ page size and $64$-entry $TLB,$ what values ... $TLB$ miss for every execution of the inner loop? Would your answer in part $(a)$ be different if the loop were repeated many times? Explain.