CS643 S12 - 1 March

Here are a few sample questions and explanations having to do with memory management, in preparation for quiz 3 on 7 March.

This question is about memory protection using base and limit registers. For every memory access, the CPU adds the base to the address, ensures that it is less than the limit, and then uses this address to access memory. Below is a diagram of the current state of memory.
```
location  value
      0    17
      1    64
      2    21
      3    38
      4    -1
      5     2
      6    99
      7    32
      8    76
```
Suppose process 1 has base=2 and limit=6.
Likewise, process 2 has base=5 and limit=8.
1. If process 1 tries to read from address 3, what is the result?
  
  The memory management mechanism will add process 1’s base to the address 3, producing 3+2=5. It then checks that this is less than process 1’s limit (5<6), which it is. So it reads the value 2 from address 5.
2. If process 1 tries to read from address 0, what is the result?
  
  Logical address 0 plus base 2 produces physical address 2, which is less than the limit. So it reads the value 21.
3. If process 2 tries to read from address 3, what is the result?
  
  Logical address 3 plus process 2’s base, 5, produces physical address 8. This is not less than process 2’s limit (8≮8), so the memory access is rejected as an error. (The memory management system would issue a kernel interrupt, and the OS would probably be forced to kill the process.)
4. Are processes 1 and 2 properly isolated from one another?
  
  The are not isolated! Physical location 5 is shared by both processes. Process 1 can access it as logical address 3 (and it’s less than the limit of 6). Process 2 can access it as logical address 0.
5. Which of the shown memory locations are free? (They don’t belong to any process.)
  
  Physical locations 0 and 1 are free, as is location 8.
What is the purpose of a page table?

Paging is a more sophisticated memory management mechanism than the base/limit scheme described in the previous question. The memory is partitioned into fixed-size chunks called pages (or, sometimes, frames).

When a process requests to access a logical address, we transform that into the page number. (This is a simple calculation because each page is a fixed size.) Then, we use the page table to tell us where in memory to find that particular page.

This scheme gives us great flexibility; pages do not need to be contiguous in memory, and can be rearranged at will.

I’ll generally use page to refer to a chunk of the logical address space, and frame to refer to the physical address space. That way, we can say that a page is loaded or mounted into a particular frame, and that a page table maps page numbers to frame numbers.
This question is about paging. Suppose that a byte-addressable system uses 20-bit physical addresses, and that 7 of those bits are for the frame number, and the remaining 13 bits for the offset within the frame. Answer the following using whatever units are most convenient (bytes, kilobytes, etc.)
1. What is the size of each frame?
  
  The frame size can be calculated from the above description. We use 13 bits for the offset address within a frame. That means there are 2¹³=8192 possible offsets within a frame. Since the machine is byte-addressable, that means each frame is 8192 bytes, or 8 kilobytes.
  
  You can also arrive at 8 kilobytes by splitting 2¹³ into 2³×2¹⁰. Since 2³=8 and 1 kilobyte is 2¹⁰ bytes, you can directly conclude 8 kilobytes.
2. How many frames are available in physical memory?
  
  Since we use 7 bits in the physical address for the frame number, how many possible frame numbers are there? The answer is 2⁷ = 128.
3. What is the maximum amount of physical memory supported?
  
  This is just the number of frames multiplied by the size of each frame: 128×8192 = 1048576 bytes.
  
  It’s actually much easier if you stick to powers of two! 2⁷×2¹³ = 2²⁰ bytes = 2¹⁰ kilobytes = 2⁰ megabytes = 1 megabyte.
Continuing the previous question, suppose the logical address space of a process contains 16 pages. How many bits are needed to represent a logical address?

There are two steps to this. First, we have to recognize that logical pages and physical frames are the same size, so we’ll still be using 13 bits for the offset within the page.

Since there are 16 pages, how many bits do we need to represent the page number? Four bits, because 2⁴=16.

So the logical address is 4 bits for the page number, plus 13 bits for the offset, so a total of 17 bits.

The question doesn’t ask this, but we can take it a little further. The maximum amount of memory a single process can access (the size of the logical address space) is then 2¹⁷ bytes = 2⁷ kilobytes = 128 kB.