
\documentclass{article}

\setlength{\oddsidemargin}{0.0 in}
\setlength{\evensidemargin}{0.0 in}
\setlength{\textwidth}{7.0 in}

\def\titledquestion#1#2{\section{ {#1} ({#2} pts.)}}
\begin{document}
\titledquestion{We Interrupt This Program}{10}
There has been some confusion surrounding interrupts and handlers.  We are
giving two implementations of the keyboard handler and readchar().  For each
implementation, state which lines of the following code are problematic and 
why.

Assume that we have included all necessary files.

\subsection{5 pts}
\begin{verbatim}
1  #define BUFSIZE 128
2 
3  static int buf[BUFSIZE];
4  static int *head = buf, *tail = buf;
5  static int count = 0;
6  
7  void keyboard_handler() {
8      int sc;
9  
10     sc = inb(KEYBOARD_PORT);
11
12     if (count < BUFSIZE) {
13         *tail = sc;
14         count++;
15         tail++;
16         if (tail == buf + BUFSIZE) tail = buf;
17     }
18 
19     outb(INT_CTL_REG, INT_CTL_DONE);
20 }
21 
22 char readchar() {
23     int sc;
24 
25     if (count > 0) {
26         sc = *head;
27         head++;
28         if (head == buf + BUFSIZE) head = buf;
29         count--;
30     }
31     else return -1;
32 
33     return (char) process_scancode(sc); 
34 }
\end{verbatim}

\clearpage

\subsection{5 pts}
\begin{verbatim}
1  #define BUFSIZE 128
2  
3  static int buf[BUFSIZE];
4  static int ins = 0, rem = 0;
5  
6  void keyboard_handler() {
7      int sc, inp;
8  
9      disable_interrupts();
10 
11     sc = inb(KEYBOARD_PORT);
12 
13     inp = ins;
14     ins++;
15  
16     if (ins == BUFSIZE) {
17         if (rem != 0) ins = 0; 
18         else ins = BUFSIZE - 1;
19     }
20 
21     if (ins == rem) ins = rem - 1;
22     else buf[inp] = sc;
23
24     enable_interrupts();
25     outb(INT_CTL_REG, INT_CTL_DONE);    
26 }
27
28 char readchar() {
29     int sc;
30 
31     if (ins == rem) return -1;
32 
33     sc = buf[rem];
34     rem++;
35     if (rem == BUFSIZE) rem = 0;
36 
37     return (char) process_scancode(sc);
38 }
\end{verbatim}

\newpage
\titledquestion{Building a Question}{10}
At construction sites, there are many workers doing various jobs to complete
the building.  A construction worker needs a hammer, a hard hat, and nails.
At this particular site, the foreman is rather relaxed.  The
hours they work are up to each worker, so they arrive and depart at whatever
time suits them.  In addition, the construction workers often forget to bring
all of their equipment with them so the foreman provides it to them when they
arrive, but he wants the job done quickly so wants to satisfy as many workers
as possible even if some never start working.  When workers depart work,
they will leave some of their equipment behind for other workers to use.  The
foreman would like you to implement the following code using mutexes and
condition variables to allow him to handle his equipment policy.  Nails are not
part of the equipment list, due to their plentiful nature.  You do not need
to worry about exact C syntax or invalid parameters.

\begin{verbatim}
/*
 * This function will be called before any worker arrives.
 * The parameters represent how much equipment the foreman 
 * has at the start of the day.
 */
void init(int hard_hats, int hammers);

/*
 * Workers will call this function when they arrive.
 * The parameters are set to 0 if the worker has this and 
 * 1 if the worker needs this
 * This should return when the worker has all the equipment 
 * he needs.
 */
void arrive(int hh, int hammer);

/*
 * Workers will call this function when they depart.
 * The parameters are what the worker is leaving with 
 * the foreman.
 */
void depart(int hh, int hammer);

\end{verbatim}

\newpage
\titledquestion{Are we dead yet?}{10}
Deadlocks are rather bad to have and can occur in even simple situations.
Learning to characterize a particular situation and recognize what future
patterns will cause is therefore incredibly important.  Given the following
situation of three processes (A B C) and three resources (R S T), for the 
following situations characterize them as safe (having no execution path 
which leads to deadlock), 
unsafe (having some execution paths which lead to deadlock), and will deadlock
(all execution paths lead to deadlock).  To answer the ``Why?'' question in
each part, you may need to draw resource allocation graphs, present safe
sequences, and / or make brief proof-like arguments.  Please make sure you are
concise yet convincing.
The resource manager grants all requests that don't violate mutual exclusion.
\\

\begin{tabular}[b]{|l|c|l|c|l|}
\multicolumn{5}{c}{Process Traces} \\
\cline{1-1} \cline{3-3} \cline{5-5}
Process A && Process B && Process C \\
\cline{1-1} \cline{3-3} \cline{5-5}
request(R) && request(S) && request(T) \\
request(S) && request(T) && request(R) \\
release(S) && release(T) && release(R) \\
release(R) && release(S) && release(T) \\
\cline{1-1} \cline{3-3} \cline{5-5}
\end{tabular}
\\

\begin{tabular}[b]{|l|l|l|}
\multicolumn{3}{c}{Execution Trace:} \\
\hline
Process A & Process B & Process C\\
\hline
request(R)&&\\
\hline
&request(S)&\\
\hline
\end{tabular}

\subsection{3 pts} If, after the execution trace shown above, the next event 
that
happens is process A: request(S), will the system be safe, unsafe or
deadlocked?  Why?

\subsection{3 pts} Assume that, instead of process A: request(S), the third 
event
is process B: request(T), will this system be safe, unsafe or deadlocked?
Why?

\subsection{3 pts} Finally assume that, instead of process B: request(T), the
third event is process C: request(T), will this system be safe, unsafe, or
deadlocked?  Why?

\newpage
\titledquestion{Paging Algorithms}{10}
Given the following memory trace (which is in row--major order:
the first reference is 0x07976e and the second reference is 0x02000d), 
put together a list of which pages will be
in memory after each access under the following algorithms: optimal, LRU,
and FIFO.  Main memory can hold 4 pages and is initially empty.  Addresses
are 24 bit and pages can hold 16k bytes.

\begin{verbatim}
0x07976e 0x02000d 0x039004 0x02c432 0x03f00d
0x07be07 0x023223 0x02f430 0x06f402 0x079e04
0x02f10b 0x038dd0 0x078263 0x06c409 0x03e942
\end{verbatim}

\subsection{2 pts}

Process the list of memory addresses to produce a list of page numbers.

\subsection{5 pts}

Fill in the following table of main memory contents for the three different 
algorithms using the list from part 1.  List the number of the virtual
page or a * for unused.  Mark an X when the reference causes a page fault.

\begin{tabular}[b]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
& \multicolumn{5}{|c|}{FIFO} & \multicolumn{5}{|c|}{LRU} & 
\multicolumn{5}{|c|}{Optimal} \\
\hline
& \multicolumn{4}{|c|}{Frames} & PF & \multicolumn{4}{|c|}{Frames} & PF &
\multicolumn{4}{|c|}{Frames} & PF \\
\hline
1& 1e & * & * &*&X&1e&*&*&*&X&1e&*&*&*&X\\
\hline
2&&&&&&&&&&&&&&&\\
\hline
3&&&&&&&&&&&&&&&\\
\hline
4&&&&&&&&&&&&&&&\\
\hline
5&&&&&&&&&&&&&&&\\
\hline
6&&&&&&&&&&&&&&&\\
\hline
7&&&&&&&&&&&&&&&\\
\hline
8&&&&&&&&&&&&&&&\\
\hline
9&&&&&&&&&&&&&&&\\
\hline
10&&&&&&&&&&&&&&&\\
\hline
11&&&&&&&&&&&&&&&\\
\hline
12&&&&&&&&&&&&&&&\\
\hline
13&&&&&&&&&&&&&&&\\
\hline
14&&&&&&&&&&&&&&&\\
\hline
15&&&&&&&&&&&&&&&\\
\hline
\end{tabular}

For this trace: the number of accesses that don't 
fault in FIFO + accesses that don't fault in LRU = number of accesses that 
don't fault in optimal.

\subsection{3 pts}
LRU is a difficult algorithm to implement in practice, but there are ways to
approximate its behavior (see section 10.4.5 of the book for a one way).
Assume the hardware has only valid and dirty bits (i.e., no reference bits).
How could you modify 
this algorithm to implement LRU?  Why is this not done in practice?

\end{document}
