Fixed partitioning suffers from internal fragmentation because some processes may use less memory than the fixed partition size. Dynamic partitioning suffers from external fragmentation because the memory "holes" left between two partitions may be too small for another process to use. Compaction is used in a system with dynamic partitioning to place all of the partitions in a contiguous range of memory. The effect of this is to combine all the small holes into one larger hole.

With paging, a process is divided into a large number of small, fixed size pages. These pages are then placed into frames of main memory, each of which is the size of a page. The main improvement over fixed partitioning is that the pages of the process do not need to be contiguous in main memory. In addition, internal fragmentation is reduced because there is only fragmentation on the last page of the process and the pages are small. The cost of these improvements is the overhead of needing a page table for each process.

In a system that uses pure paging, the logical address is divided into a page number and an offset. The page number is used as an index into the page table for the running process; the corresponding entry contains the frame number that the page is mapped to. The offset is added to the frame number to form a physical address.

      In a system that uses pure segmentation, the logical address is divided into a segment number and an offset. The segment number is used as an index into the segment table for the running process; the corresponding entry contains a segment base and length. The segment base is the beginning of the segment of memory that the process is mapped into and the length gives the length of this segment. If the offset is greater than the segment length, a segmentation error occurs. Otherwise, the offset is added to the segment base to form a physical address.

Locality is important because a virtual memory system keeps only a small subset of a process image in memory at any given time. If locality holds, then many memory references will refer to this subset and the process will be able to run normally. However, if locality doesn't hold, then memory references will not map to a valid physical address. When this happens, a memory fault occurs and the missing data will need to be loaded from secondary storage. The process will run slowly because secondary storage is much slower than main memory.

A page fault occurs when a reference is mapped to a page that is not currently in main memory. When this happens, the process is suspended and the operating system takes control. If main memory is full, then a page must be replaced. Once an empty frame is found, the operating system schedules an I/O operation to bring in the page. After the page is brought in, and the page table updated, the process can be started again.

      Thrashing occurs when a system spends more time swapping than running a process. The operating system can avoid thrashing by reducing the number of processes that are in memory, i.e. by swapping some out.

      The advantage of having a fixed resident set means that no other process can take frames away from you. However, this has to take into account the maximum need of a process and so it may waste memory. The advantage of having a dynamic resident set means the number of frames dedicated to a process can grow or shrink over time, more closely matching its needs. Of course, there is more overhead involved with this approach.

      A fixed size resident set implies a local replacement policy. Any time a process needs a new page, one of its own pages must be replaced.

      Having a variable resident set allows the operating system to do either local or global replacement. Doing local replacement means that the process always replaces one of its own frames and the resident set size can be increased or decreased separately by the operating system. Doing global replacement means the process can automatically increase its resident set by choosing to replace someone else's page with its own. It may also have its resident set decreased when someone else chooses one of its pages.

      Precleaning may decrease the page fault rate if the operating system is able to bring in pages in advance of them being used by a process. This may be particularly effective at the time the process is first loaded.

Problems

      The shaded areas are allocated blocks; the white areas are free blocks. The next three memory requests are for 40M, 20M, and 10M. Indicate the starting address for each of the three blocks using the indicated placement algorithms:

         1. First-fit

     * The 40 M block fits into the second hole, with a starting address of 80M.

                * The 20M block fits into the first hole, with a starting address of 20M.

                * The 10M block is placed at location 120M.

         2. Best-fit

 The three starting addresses are 230M, 20M, and 160M, for the 40M, 20M, and 10M blocks, respectively.

3. Next-fit. Assume the most recently added block is at the beginning of memory.

The three starting addresses are 80M, 120M, and 160M, for the 40M, 20M, and 10M blocks, respectively.

         4. Worst-fit

 The three starting addresses are 80M, 230M, and 360M, for the 40M, 20M, and 10M blocks, respectively.

a.       Show the results of the following sequence in a figure similar to Figure 7.6: Request 70; Request 35; Request 80; Return A; Request 60; Return B; Return D; Return C.

Figure 1

b.      2. Show the binary tree representation following Return B.

Figure 2

a.       If the block is of size 4, what is the binary address of its buddy?

            If the block is of size 4, the binary address of its buddy is 011011110100

b.      2. If the block is of size 16, what is the binary address of its buddy?

If the block is of size 16, the binary address of its buddy is 011011100000.

a.       How many bits are in a logical address?

The number of bytes in the logical address space is (216 pages) * (210 bytes/page) = 226 bytes. Therefore, 26 bits are required for the logical address.

b.      How many bytes in a frame?

A frame is the same size as a page, 210 bytes.

c.       How many bits in the physical address specify the frame?

The number of frames in main memory is (232 bytes of main memory)/(210 bytes/frame) = 222 frames. So 22 bits is needed to specify the frame.

d.      How many entries in the page table?

There is one entry for each page in the logical address space. Therefore there are 216 entries.

e.       How many bits in each page table entry? Assume each page table entry includes a valid/invalid bit.

In addition to the valid/invalid bit, 22 bits are needed to specify the frame location in main memory, for a total of 23 bits.

a.       How many levels of page tables are required?

Virtual memory can hold (232 bytes of main memory)/( 210 bytes/page) = 222 pages, so 22 bits are needed to specify a page in virtual memory. Each page table contains (210 bytes per page table)/(4 bytes/entry) = 28 entries. Thus, each page table can handle 8 of the required 22 bits. Therefore, 3 levels of page tables are needed.

b.      What is the size of the page table at each level? Hint: One page table size is smaller.

Tables at two of the levels have 28 entries; tables at one level have 26 entries. (8 + 8 + 6 = 22).

c.       The smaller page size could be used at the top level or the bottom level of the page table hierarchy. Which strategy consumes the least number of pages?

 Less space is consumed if the top level has 26 entries. In that case, the second level has 26 pages with 28 entries each, and the bottom level has 214 pages with 28 entries each, for a total of 1 + 26 + 214 pages = 16,449 pages. If the middle level has 26 entries, then the number of pages is 1 + 28 + 214 pages = 16,641 pages. If the bottom level has 26 entries, then the number of tables is 1 + 28 + 216 pages = 65,973 pages.

      Virtual Page Number          Page Frame      Time Loaded    Time Referenced          R Bit    M Bit

      2    0          60        161      0          1

      1    1          130      160      1          0

      0    2          26        162      1          0

      3    3          20        163      1          1

      A page fault to virtual page 4 has occured at time 164. Which page frame will have its contents replaced for each of the following memory management policies? Explain why in each case.

a.       FIFO (first-in-first-out)

            Frame 3 since it was loaded the longest ago at time 20.

b.      LRU (least recently used)

            Frame 1 since it was referenced the longest ago at time 160.

c.       Clock

            Clear R in Frame 3 (oldest loaded), clear R in Frame 2 (next oldest loaded), victim Frame is 0 since R=0.

d.      Optimal (Use the following reference string.)

            Replace the page in Frame 3 since the virtual page number 3 (in Frame 3) is used furthest in the future.

e.       Given the aforementioned state of memory just before the page fault, consider the following virtual page reference string: 4,0,0,0,2,4,2,1,0,3,2. How many page faults would occur if the working set policy with LRU were used with a window size of 4 instead of a fixed allocation? Show clearly where each fault would occur.

            There are 6 faults, indicated by *:

            (Window) - {working set}

            -----------------------

            (1 2 0 3) - {2 1 0 3}

            (2 0 3 4) - {2 0 3 4}*

            (0 3 4 0) - {0 3 4}

            (3 4 0 0) - {0 3 4}

            (4 0 0 0) - {0 4}

            (0 0 0 2) - {0 2}*

            (0 0 2 4) - {0 2 4}*

            (0 2 4 2) - {0 2 4}

            (2 4 2 1) - {2 4 1}*

            (4 2 1 0) - {2 4 1 0}*

            (2 1 0 3) - {2 1 0 3}*

            (1 0 3 2) - {2 1 0 3}

a.       If a memory reference takes 200 ns, how long does a paged memory reference take?

400 nanoseconds. 200 to get the page table entry, and 200 to access the memory location

.

b.      Now we add an MMU that imposes an overhead of 20 ns on a hit or a miss. If we assume that 85% of all memory references hit in the MMU TLB, what is the Effective Memory Access Time (EMAT)?

There are two cases. First, when the TLB contains the entry required, we have 20 ns overhead on top of the 200 ns memory access time. Second, when the TLB does not contain the item, we have an additional 200 ns to get the required entry into the TLB:

            (220 * 0.85) + (420 * 0.15) = 250 ns

c.       Explain how the TLB hit rate affects the EMAT.

The higher the TLB hit rate is, the smaller the EMAT is, because the additional 200 ns penalty to get the entry into the TLB contributes less to the EMAT.

a.       What is the maximum size of each segment?

            (8 entries in the page table) x 2K = 16K.

b.      What is the maximum logical address space for the task?

            (16 K) x 4 segments per task = 64K.

c.       Assume that an element in physical location 00021ABC is accessed by this task. What is the format of the logical address that the task generates for it? What is the maximum physical address space for the system?

We know the offset is 11 bits since the page size is 2K. The page table for each segment has eight entries, so it needs 3 bits. That leaves 2 bits for the segment number. So the format of the address is 2 bits for segment number, 3 bits for page number, and 11 bits for offset.

 The physical address is 32 bits wide total, so the frame number must be 21 bits wide. Thus 00021ABC is represented in binary as:

            Frame                           Offset

            0000 0000 0000 0010 0001 1 | 010 1011 1100

            The maximum physical address space is 232 = 4 GB.

 Note that the virtual address space is only 16 bits wide: 11 for the offset, 3 for the page number, and 2 for the segment number. This means a process cannot logically address the entire 4GB space ... it is limited to only 64K.

      What is the maximum acceptable page-fault rate if we want the system to have an effective memory access time of 200 nanoseconds?

      EMAT = 200ns = X(100ns) + (1-X)(.70(20ms + 100ns) + .3(8ms + 100ns))

           = 100X + (1-X)(16.4ms)

           = 100X - 16,400,000X + 16,400,000

      X = 16399800/163999000

        = .9999939024

      Therefore the maximum acceptable page-fault rate is (1-X) = .00061%.