Homework Assignment #8

Memory Management

  1. Explain the difference between internal and external memory fragmentation. 

    

Internal fragmentation is memory that is allocated to a process but
not used.


External fragmentation is memory that is free (not allocated to any
process) which cannot be allocated to a process because its contiguous
pieces are to small to be usable by any process.

  2. Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each of the First-fit, Bset-fit, and Worst-fit algorithms place processes of size 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory?

    RequestFirst-FitBest-FitWorst-Fit
     100,500,200,300,600100,500,200,300,600100,500,200,300,600
    212100,288,200,300,600100,500,200,88,600 100,500,200,300,388
    417100,288,200,300,183100,83,200,88,600 100,83,200,300,388
    112100,176,200,300,183100,83,88,88,600 100,83,200,300,276
    426wait100,83,88,88,174wait

    Best-Fit is more efficient for this example in the sense that in this case Best-Fit is able to satisfy all requests without waiting while the other algorithms cannot.

  3. A compiler must generate addresses that refer to code (e.g., for function calls or for jumps to the beginning of loops) and addresses that refer to data. In a virtual memory system will these addresses be physical addresses or logical addresses? 

    

Logical addresses.

  4. In a virtual memory system, does the program counter register contain logical addresses or physical addresses of instructions? What about the Memory Address Register? 

    

The program counter will contain logical addresses and the Memory
Address Register must contain physical addresses.

  5. Why is it that, on a system with paging, a process cannot access memory it does not own? How could the operating system allow access to other memory? Why should it or should it not? 

    

The page table for each process specifies where that process's code
and data are. Each address that the process references during
execution is translated by the MMU hardware to a physical address
using that process's page table. Therefore, one process cannot
reference another process's code or data.


An operating system can provide system calls that allow a process to
share its memory with other processes. A physical page frame
can be shared by processes by having entries in each process's page
table point to the same physical page frame. This allows processes to
share data and to be able to communicate efficiently. This should only
be allowed if the owning process permits it. It is important that this
be a system call so that the operating system can verify that the
owning process has granted permission to the other processes to share
the memory and to allow specification of the mode of sharing - read
only, or read-write.

  6. A paging system has a page size of 256 bytes.

    1. What page contains virtual address 2400?
    2. What is the page offset within its page for address 2400?
    3. At what physical address does page frame 5 begin?

    

a. Address 2400 is on page int(2400/256) = 9
b. The page offset on page 9 of address 2400 is 2400 mod 256 = 96
c. Page frame 5 begins at physical address 5 * page_size = 5 * 256 = 1280

  7. Virtual Address Translation. When a virtual address is translated to a physical address, the memory management unit first determines the page number and the page offset and then uses the page table to determine the physical address. Assume the page size is 512 and the page table for a process is given below. For each of the virtual addresses in (a)-(b), determine whether a reference to it will cause a page fault. If the virtual address will not cause a page fault, show the calculation of the corresponding physical address. (Valid bit = 1 means the page is in memory.)

    1. 2560
    2. 2559
     
    Page
    Valid
    Bit
    Page Frame
    Number
    0
    1
    13
    1
    0
    4
    2
    1
    5
    3
    1
    4
    4
    1
    9
    5
    0
    10
    6
    1
    2
      
    Answer:
    1. Page fault.

      Address 2560 is on page int(2560/512) = 5. However, the page table entry for page 5 has valid bit = 0, meaning that page 5 is not currently in memory; i.e., this is a page fault.

    2. 5119.

      Address 2559, on the other hand, is on page int(2559/256) = 4. The page table indicates that page 4 is valid (valid bit = 1) and that page 4 is loaded into physical page frame 9. Also the offset of address 2559 on its page is 2559 mod 512 = 511. So the physical address is:

      physical address = page_frame * page_size + offset
                 = 9 * 512 + 511 = 5119