Class Notes (1,100,000)
CA (630,000)
UW (20,000)
CS (1,000)
CS246 (100)

review review of notes

Computer Science
Course Code
Peter Buhr

This preview shows pages 1-2. to view the full 6 pages of the document.
University of Waterloo
Midterm Examination Model Solution
Fall, 2008
1. (10 total marks)
The OS/161 addrspace structure shown below describes the address space of a running OS/161 process.
The virtual page size is 4096 bytes (0x1000 bytes) 64K bytes (216 bytes). Assume that OS/161 gives
each process a stack segment consisting of 16 pages, ending at virtual address 0x7fffffff.
Note: On the original exam, the page size was given as 4K bytes. With that page size, the answer
for each virtual address in part (a) is INVALID VIRTUAL ADDRESS and the answer for each physical
address in part (b) is UNMAPPED PHYSICAL ADDRESS. The answers shown below are for a page size of
struct addrspace {
/* text segment */
vaddr_t as_vbase1 = 0x05800000; /* virtual base address */
paddr_t as_pbase1 = 0x10400000; /* physical base address */
size_t as_npages1 = 0x20; /* number of pages */
/* data segment */
vaddr_t as_vbase2 = 0x20000000; /* virtual base address */
paddr_t as_pbase2 = 0x00400000; /* physical base address */
size_t as_npages2 = 0x1a0; /* number of pages */
/* stack segment */
paddr_t as_stackpbase = 0x10800000; /* physical base address */
a. (5 marks)
For each of the following virtual addresses, indicate which physical address the virtual address
maps to. Also indicate whether the virtual address falls into the text segment, the data segment,
or the stack segment. If the virtual address is not part of any segment, write INVALID VIRTUAL
ADDRESS instead. Use hexadecimal notation for physical addresses.
0x20ffaa60 0x013faa60 (data segment)
0x05960006 0X1056006 (text segment)
b. (5 marks)
For each of the following physical addresses, indicate which virtual address maps to that address.
Also indicate whether that virtual address falls into the text segment, the data segment, or the
stack segment. If no virtual address maps to the specified physical address, write UNMAPPED
PHYSICAL ADDRESS instead. Use hexadecimal notation for virtual addresses.
0x1081f3f0 0x7ff1f3f0 (stack segment)
0x01dd0890 0x219d0890 (data segment)
CS350 1 of 6

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

2. (10 marks)
An OS/161-like operating system is being designed to use round robin scheduling of threads. The
hardware includes a timer device which will generate interrupts at a rate of Tinterrupts per second.
The desired scheduling quantum is Qseconds. You may assume that 1/T divides evenly into Q, i.e.,
that the product QT is a positive integer.
Your task is to write two kernel functions that will form part of the round robin scheduler implemen-
tation. These two functions are:
OnTimerInterrupt():This function will be invoked by the timer interrupt handler each time there is
a timer interrupt. This function should decide whether the currently-running thread’s quantum
has expired and, if it has expired, this function should cause that thread to yield the processor,
so that a new thread can begin its quantum.
OnDispatch():This function will be invoked each time a thread is dispatched by the scheduler. It can
be used to indicate that the new thread’s quantum is beginning.
Write these two functions below in C-like pseudo-code. You may declare and use any global or local
variables you need. You may also call any of the OS/161 thread functions (e.g., thread sleep(),
thread yield(),thread exit()) that you need. You may also refer to the constants Qand Tin your
These functions need not be complicated, so keep your implementations as simple as possible. Overly
complicated solutions may be penalized.
int RemainingTicks; /* global. Initial value unimportant. */
OnTimerInterrupt() {
RemainingTicks = RemainingTicks - 1;
if (RemainingTicks == 0) {
thread yield();
OnDispatch() {
RemainingTicks = Q*T;
CS350 2 of 6
You're Reading a Preview

Unlock to view full version