Section 6 Solutions

Solutions

1. Preemption

Q1: When the program switches to executing thread one for the first time, where does it begin running?

A1: It starts at the beginning of thread_run (since it has never run before).

Q2: When the program first switches back to executing the main thread, where does it resume?

A2: It resumes in yield right after the context switch that switched away from the main thread to thread two. It then returns from yield and goes back to timer_interrupt_handler, which then returns to main (at which point interrupts are re-enabled).

Q3: Why is it important that interrupts be disabled when the handler is run?

A3: The timer interrupt handler—literally called timer_interrupt_handler here—is invoked with interrupts disabled. In general, interrupt handlers need to be invoked with interrupts being disabled so it itself isn’t interrupted. That would expose the system to a scenario when a chain reaction of interrupts prompt an unbounded number of interrupt handlers to be invoked before any one of them finishes.

Q4: The program calls intr_enable(true) at the start of the other threads' function to re-enable interrupts. Why is that needed? What happens if that line is removed? Why? Give it a try to test your hypothesis.

A4: The timer handler is invoked with interrupts disabled. However, as a result, the very first time the main thread context switches into thread #2, the thread_run routine is called with interrupts disabled, thereby preventing that call to thread_run from being interrupted unless it explicitly re-enabled interrupts. If that line is removed, the initial thread would run for about 500,000 microseconds and then be preemptively yielded to thread #2 by a timer interrupt, at which point thread #2 would be uninterruptible—what’s to stop it?-and run forever.

2) Virtual Memory Review

Q5: With virtual memory, we say that there are now two views of memory. What is meant by that, and how do those views differ?

A5: With virtual memory, the view of memory from a program (its virtual address space) is different from the actual layout of memory (the physical address space). The program thinks it has exclusive access to memory starting at 0 and going onwards, but that is likely not what its actual memory layout looks like; the OS could place its memory in various different places, and will translate between those virtual and physical locations.

Q6: What are the benefits of the OS translating from virtual to physical addresses, as opposed to just having physical addresses?

A6: It's useful for many reasons, including; the OS can prevent rogue memory accesses, it can choose to allocate the memory space in a different way from how the program thinks it is laid out, it can even move some memory to disk without the program knowing and move it back later if the program still needs it.

Q7: In a base and bound implementation, let's say a process has base = 4000 and bound = 200. For each of the following memory accesses, are they valid? And if so, what physical address would they really access?

  • accessing virtual address 0
  • accessing virtual address 50
  • accessing virtual address 300

A7: The first two are valid, but the third is not - becuase it's >= bound. The first one would really access physical address 4000 + 0 = 4000, and the second one would really access physical address 4000 + 50 = 4050.

Q8: Let's say the OS decides to move that process's reserved physical memory somewhere else; specifically, the OS copies it from base 4000 to base 2000. They also give the process more memory, updating its bound to bound 500. How would the outcome of the memory accesses above change? (Cool note: the process itself has no idea its physical memory was moved, and all it needs to do to access the additional memory we've given it is to refer to those larger virtual addresses. Pretty neat!).

A8: Now, all 3 are valid because they are all < bound. The first one would now really access physical address 2000 + 0 = 2000, the second one would really access physical address 2000 + 50 = 2050, and the third one would really access physical address 2000 + 300 = 2300.

Extra: Implementing Base-and-bound Translation

Task: implement the translate method and test it by running the provided test program, which attempts to access 3 addresses, the first two of which are valid, and the third of which is invalid and should cause a crash.

A4: a solution could look something like this:

char *VirtualMemory::translate(const VirtualPointer& p) {
  if (p.offset >= bound) {
    cerr << "memory violation - accessing invalid offset " << p.offset << endl;
    raise(SIGSEGV);
    return nullptr;
  } else {
    return base + p.offset;
  }
}

Checkoff Questions

  1. [Q1] The thread cycle program calls intr_enable(true) at the start of the other thread functions to re-enable interrupts. Why is that needed? What happens if that line is removed? Why?

    • The timer handler is invoked with interrupts disabled. However, as a result, the very first time the main thread context switches into thread #2, the thread_run routine is called with interrupts disabled, thereby preventing that call to thread_run from being interrupted unless it explicitly re-enabled interrupts. If that line is removed, the initial thread would run for about 500,000 microseconds and then be preemptively yielded to thread #2 by a timer interrupt, at which point thread #2 would be uninterruptible—what’s to stop it?-and run forever.

  2. [Q2] Why is it useful to have separate virtual and physical addresses, with the OS intercepting them to translate, as opposed to just having physical addresses?

    • It's useful for many reasons, including; the OS can prevent rogue memory accesses, it can choose to allocate the memory space in a different way from how the program thinks it is laid out, it can even move some memory to disk without the program knowing and move it back later if the program still needs it.

  3. [Q3] If a process has base 1000 and bound 500, is accessing offset 50 valid? If so, what physical address would it really be accessing?

    • Yep - it would really access physical address 1000 + 50 = 1050.