Sample questions from previous semester's second exam
- Describe two data structures needed to implement paged virtual
what is needed for a process and what is needed for the OS.
- Show the LRU replacement policy for the following reference
string and three frames of memory. How many page faults occurred.
- Describe how a logical address is converted to a physical address
for a two level page table.
- Briefly describe two advantages of a virtual memory system.
- What does it mean when: a) the logical address space is smaller
than the physical address space; b) the logical address is larger than
the physical address space.
- Suppose a machine has a physical memory of 1M organized as 256 4K
pages. As there are only 256 frames of memory, the frame value could be
stored in a byte. What is the primary disadvantage of storing the frame
number this way. Suggest an alternative that eliminates this
- What would be the primary disadvantage of making the page size a
value that was NOT a power of 2.
- Suppose a 32 bit virtual address is split into four fields: a, b,
c, d. The first three are used for a three level page table. Give a
formula defining the number of pages needed to handle this scheme.
- What is the difference between a physical address and a logical
address and where is each used.
- Explain how shared memory can be implemented in a paging system.
- Main memory of a computer contains 90 frames. Nine identical
programs are running and each references its pages (0123456789) in that
order over and over. What is the page fault rate? If a tenth identical
program is introduced and an LRU page replacement policy is used,
describe what happens and why.
- A system is running with following measure behavior: CPU
utilization 20%; Paging disk 98% Other I/O devices 5%. For each of the
following say whether it will improve CPU utilization
- faster CPU
- bigger paging disk
- increase degree of multi programing
- decrease degree of multi programming
- install more memory
- install a faster disk
- increase page size
- Describe two page replacement algorithms and describe an
advantage and disadvantage of each.
- What information needs to be stored to implement segmentation?
What needs to be stored to implement paging? What is the trade off
between the two?
- Describe how decreasing the page size could result in fewer page
faults (assuming total memory allocated to a process remains constant).
- A group of designers for the Frugal computer Company are thinking
about ways of reducing the size of the backing store (the swap area)
and propose just paging programs text area directly from the disk. Are
there any problems with this?
- What factors might be used in selecting a frame to page out?
- Suppose a computer has a 48 bit virtual address and 16 G physical
memory. How many bytes would be needed for storing the frames of an
inverted page table using 8K pages?
- Describe what hardware is needed to support pure segmentation.
- Describe what hardware is needed to support paging.
- Describe how a single level page table works. Describe how a two
level page tablew works. What is the primary tradeoff between the two?
- A computer has a 32 bit address space and 4K-byte pages. The
program and data segments each occupy one page and the stack occupies
one page. a) How much total memory is required when paging is
implemented with a single level page table?
b) How much total memory is required when paging is implemented with a
two level page table with 10 bits in each part.
- A certain system has 4 G-byte logical addresses and 23 bit
physical address. Paging is implemented with a page size of 2048 bytes.
Describe what an entry in the TLB might look like, including
information needed for various page replacement algorithms. Assume a
single level page table.
- With respect to virtual memory a) Describe internal fragmentation
and how it occurs b) Describe external fragmentation and how it occurs
c) How can internal fragmentation be minimized and what is the trade
off for doing so.
- a) Describe how an inverted page table works. b) Why is its major
advantage? c) What change in memory mapping is required when compared
to a normal page table?
- Describe two disc scheduling algorithms and give a disadvantage
- Describe the idea of program locality. What would be the
consequence if programs did not exhibit locality?
- Describe thrashing. Suggest two ways of reducing thrashing.
- Describe various factors that might be considered in selecting a
page to use when a page fault occurs.
- A student in a compiler design course proposes to write a
compiler extension that outputs lists of page references that can be
used for the optimal page replacement algorithm. Is this possible? Why
or why not?