Quiz 3

CS 418, Fall 2006

Name:______

  1. Operating systems have a number of major subsystems, including process management, file system management, and main memory management (usually referred to simply as memory management). What is the main task of the operating system in managing main memory?

Placing multiple processes in main memory for concurrent execution. This requires organizing main memory and keeping track of which processes are in main memory, where they are located in main memory, which parts of main memory are occupied, and which are used, how to replace existing processes with new processes in main memory, and so forth.

  1. In olden days, one approach to memory management in multiprogramming operating systems was to place simultaneouslya number of different complete processes in RAM, each in its own contiguous space in RAM, and then to switch among the different processes as each was give time to run. Describe one major drawbackin this approach to memory management.
    There are a number of major drawbacks to this approach. You were required to only give one, such as the fact that processes had to be no larger than the amount of main memory available, fragmentation of memory could leave many small blocks in which no ready-to-run process could fit, programmers and compilers had to write programs that were relocatable, and others
  2. How does paged virtual memory management solve the drawback you identified in 2?
    Paged virtual memory allows processes to be constructed to have size as large as the address size of the computer permits, whether there is that much RAM or not. External fragmentation is not an issue, as all processes are divided into equally-sized pages and only recently used pages continue to exist in noncontiguous page frames in RAM (internal fragmentation occurs in the last page of each process, but this does not cause other processes from being loaded into RAM). And compilers and programmers do not need to be aware of any aspects of main memory; programs are written and compiled to virtual address space.
  3. What is the translation lookaside buffer (TLB)?
    The TLB is a processor hardware cache of recently used virtual pages and their corresponding real frame addresses in RAM.
  4. Describe how the TLB works as associative memory when presented with a virtual address to translate into a physical address (this is just what the TLB does when presented with a virtual address, not what the entire memory management unit does).
    When a virtual address needs to be resolved, the processor presents the virtual address to the TLB. As associative memory, the TLB compares this virtual address simultaneously with all virtual memory slots in the TLB. Thus, if the virtual memory address is found, the corresponding frame address stored with that virtual memory address is produced in one step (but only if the “valid” bit of the TLB for that entry is set).
  1. There are four page replacement algorithm types that are discussed in the book for OS use in paged virtual memory management. Discuss a major strength and a major weakness of each in the spaces provided below.
    optimal
    strength
    The optimal algorithm replaces pages in RAM that will either not be accessed again or whose next access time is the longest of all of the pages currently in RAM.
    weakness
    Impossible to implement as it would require a pre-knowledge of which pages will be accessed at which times in the future. Instead, the optimal algorithm can be used as a basis against which other algorithms can be measured for efficiency (by looking in retrospect after an experiment has been run how the optimal algorithm would have replaced pages).
    least recently used (LRU)
    strength
    Probably near optimal. The page in RAM that is the least recently used is likely not to be used in the near future and thus may well be the one that the optimal algorithm would replace.
    weakness
    Very inefficient to implement. Every page access would require a time stamp to be placed in the page tables and for the process. This would require a lot of intervention on the part of the hardware and/or operating system.
    first in first out (FIFO)
    strength
    Relatively easy to implement. The OS just needs to keep a queue of pages placed in RAM according to the order in which the page faults occur.
    weakness
    Likely to be very inefficient. The order in which pages are brought into RAM will likely have little correlation with which pages will be accessed next. For example, a small but long running program may have its code in only one page. This page should not be swapped out as its time slices expire because it will be needed again as soon as this process is allowed to run again, but likely would be in a FIFO scheme.
    clock (approximation of LRU)
    strength
    Probably the best of the bunch since it approximates LRU and yet can be efficiently implemented because only one bit (in the scheme discussed in the book) is used to indicate whether the page has been recently used (not an entire time stamp). It does work well in practice.
    weakness
    Is still quite imperfect since only one bit is used to approximate LRU.
  1. Describe how the LRU-approximating clock algorithm works to determine which page to replace in a memory frame when a new page must be loaded.Assume that along with each memory frame the OS keeps a modified bit and a recently used bit.
    The OS keeps a circular queue of page frame addresses. Assuming that all frames are in use, the OS looks through the frames from the current head of queue pointer looking for a frame, both of whose modified bit and least recently used bit are not set. If such a frame is found, it can be overwritten with the new page by the OS. The OS must then set the page bits in the page table for the process whose page was overwritten to indicate that the page is not in RAM. The TLB will be set automatically when the new page is placed in RAM. If no such frame is found in the page frame queue, the OS makes another pass through the queue setting all recently used bits to 0. If it finds a frame with used bit 0 and modified bit 1, it will replace that page (being sure to write the modified page it throws out to disk. If it reaches the front of the queue once again without finding such a pair, it repeats its first step, and possibly the second step. At this point, all of the LRU bits are 0, but there is a remote possibility that all modified bits are still 1. Thus the algorithm will either pick the first frame from the front of the queue whose used and modified bits are both 0, or it will get all the way through the queue again without finding such a frame and pick the frame at the head of the queue for replacement.(which will have used bit 0 and modified bit 1) In this case it must write the page in the frame to memory, as it has been modified. (see page 360 in the book).
  2. Suppose that the PC contains hexadecimal address 00002608. Suppose further that the operating system is a paged virtual system designed around 4K pages, and a 2-level page table.

Describein general termsthe steps the hardware performs in loading the correct instruction into the IR. Be sure to consider the three scenarios that could happen in retrieving the proper instruction and placing it into the IR. Also, be precise with respect to how the address 00002608 is used for this purpose. Notice that this is not a walkthrough, because there is nothing to walk through. Thus you are to describe the steps that are taken so that it is clear that you know how you would do a walkthrough if asked.
The virtual address 00002608 will be presented to the MMU. The virtual page in which this address is found is 00002; the offset in this page of the addressed byte is 608. The TLB is presented with page address 00002. If there is a hit, the frame of the address in memory will be returned immediately by the TLB, and which point 608 will be added to this frame address to get the physical page address by the hardware. If there is no TLB hit, the hardware uses the page table register value to locate the page directory in RAM for this process. The first 10 bits of the virtual address (10 zeros in this case) are used as the offset into this directory table and (if the valid bit is set for that entry) its contents are used as the address in RAM of the page table for this address. The second 10 bits of the virtual address (in this case a 0000000010, or 2) are used as the offset into this page table. Its entry (if the valid bit is set) is the frame address in RAM of the page. The frame address is thus added to the virtual page address offset (608) to create the actual address in RAM. Note that the address in the directory table is also a virtual address that would need to be resolved. If at any point the valid bit is not set in the directory or page table, a page fault is generated by the MMU. This causes the processor to do its usual thing to return control to the OS.

The next two questions refer to the following diagrams. Assume that paged virtual memory is being used with pages of size 4K and that there is a single page table rather than a two-level page table. Finally assume that each page table entry is five bytes in length, with the first bit being a “modified (dirty)” bit, the second bit being a “valid (present)” bit, and the remaining bits the frame address.

TLB
Dirty / Valid / Virtual Page Address / Physical Frame Address
0 / 1 / C000B / 00A00
0 / 1 / C000A / 000FA
0 / 1 / 00000 / 000A0
0 / 0 / 00001 / 0FFFF
0 / 1 / CE000 / AF000
Main Memory / PTR
Real addresses / CE000000
00000000
0000100A / 4
0000A00A / 11
000FA512 / 10
0FFFF00A / 3
A00A00A / 40
AF000000 / 0 1 0000A
AF000001 / 6
AF000005 / 0 1 C000B
C000A512 / 5
C000B000 / 70
C000B00A / 15
FFFFFFFF
  1. Suppose that the instruction load r0, C000A512 is executed. What gets loaded into r0?
    10, because the virtual page address C000A gets a TLB hit to frame 000FA, which when the virtual page offset 512 is appended to it results in real memory address 000FA512. At this address in RAM we find 10.
  2. Suppose that the instruction load r0, 0000100A is executed. What gets loaded into r0?
    15, because the virtual page address 00001 is presented to the TLB, and although there is a hit, the valid bit is 0, meaning that this entry in the TLB is invalid. Thus, the hardware must run through the page table scheme. The PTR register is used. Its address is virtual, so CE000 is presented to the TLB. There is hit with frame AF000. The offset in the PTR is 000, so the frame address of the page table in RAM is AF000000. To get to the proper entry in the page table we note that the virtual address we are seeking is 0000100A, Since this is a one level page table and the page size is 4K, the last three hex digits, 00A, refer to the byte offset in a 4k page, and the first five hex digits, 00001, are the virtual page address (which corresponds to the offset into the page table where the frame address will be found. So, we are seeking offset 1 in the page table we just resolved to be at frame AF000000 in RAM. Since each table entry takes up five bytes, entry 1 must be five bytes from the start of this frame at AF000005. There we find the proper frame address for this page, which is C000B. Since its valid bit is set, the virtual page we are resolving is in RAM starting at C000B. Appending the virtual page offset 00A to this yields C000B00A, where we find 15.