\documentstyle[11pt]{article}
\oddsidemargin=-0.005in
\evensidemargin=-0.005in
\topmargin=-0.7in
%\columnsep=0.25in
\textwidth=6.50in
\textheight=9.0in
\newenvironment{tempspacing}[1]{\begin{trivlist}
\baselineskip=#1
\normalbaselineskip=\baselineskip\item[]}{\end{trivlist}}
\renewcommand{\baselinestretch} {1.2}
\pagenumbering{empty}
\pagestyle{empty}
\thispagestyle{empty}
\begin{document}
\title{\Large\bf \vspace*{-0.5in}Comprehensive Examination\\
Computer Architecture and Operating Systems\\September 16, 1995}
\author{}
\date{}
\maketitle
\vspace*{-0.8in}
\underline{\bf Note:} \begin{itemize}
            \item Start each answer on a fresh sheet of paper. Please
         	  keep your answers brief and to the point. Clearly
		  state any assumption that you make.
            \item You must write your Social Security Number on each
                  answer book. {\bf Do not} write your name.
            \end{itemize}
\begin{enumerate}
\item (10 points)
      You are considering three choices of memory organizations for a
      computer system: Direct Mapped, 2-way set associative and 4-way
      set associative. The following information is given:
      \begin{center}
      \begin{tabular}{|l|c|c|c|}
      \hline\hline
       & Direct Mapped & 2-way set associative & 4-way set associative\\
      \hline
      Clock Cycle Time & 10ns & 10.7ns & 10.9ns\\
      miss rate & 4.6\% & 3.8\% & 3.5\%\\
      miss penalty (in cycles) & 10 & 10 & 10\\
      \hline\hline
      \end{tabular}
      \end{center}
      CPI$_{execution}$ = 1.2\\
      Average memory references per instruction = 1.4\\
      Cache hit time is 1 clock cycle for any cache organization.
      \begin{enumerate}
      \item Which organization results in the smallest average memory
            access time? (5 points)
      \item Which organization results in the best CPU performance? (5 points)
      \end{enumerate}
\item (10 points)
      Consider a simple RISC architecture (such as DLX) where only LOAD
      and STORE instructions access memory. The following pipeline is 
      designed for such a system:

      \begin{tabular}{ll}
      IF & Instruction fetch starts\\
      IS & Instruction fetch completes\\
      RF  & Instruction decode and register fetch; branch target
            computed.\\
          & testing of branch condition begins this cycle;\\
      EX & Execution - effective address or ALU result available;\\
          & testing of branch condition completed.\\
      DF & Memory access starts\\
      DS & Memory access completes.\\
      WB & Write back.\\
      \end{tabular}\\
      Register writes are done in the first half of a clock cycle and 
      the reads in the second half.
      \begin{enumerate}
      \item We would like to eliminate data hazards with forwarding.
            Name which units need to be connected to which other units 
	    with forwarding logic and specify which instructions each 
	    forwarding logic should keep track of. {\bf Do not} waste 
	    time by giving example assembly language sequences or drawing 
	    pipeline flow diagrams. (3 points)
      \item Assume that 20\% of the instructions are conditional branches
            and that 70\% of these are taken. For best CPU performance,
	    should we adopt the {\em predict taken} strategy or the {\em
	    predict not taken} strategy? (4 points)
      \item Assume that the only interrupt that can occur is a data TLB
            miss and 5\% of the instructions cause this interrupt. The
	    interrupt is recognized in the DF stage and takes 10 cycles
	    to service. If the interrupt is precise and the CPI without
	    interrupts is 1.5, what is the CPI with interrupts? (3
	    points)
      \end{enumerate}
\item (10 points)
      Consider the design of an I/O system with a total storage capacity 
      of 10GB. The average size of each disk access is 4KB. The following 
      information is given on the components available to build the I/O 
      system:

      \begin{tabular}{lll}
      \underline{\bf Component} & \underline{\bf Cost} & \underline{\bf Performance}\\
      I/O Bus & \$1000 & Peak bandwidth = 80 MB/s;\\ 
		& & can support 10 disk controllers\\
      Disk controller and String & \$3000 & Peak string bandwidth = 10 MB/s;\\ 
		& &   1 ms overhead per I/O event due to controller;\\
		& &   String can support a maximum of 10 disks\\
      3.5 inch disk & \$2000 & Capacity = 1 GB; Avg. seek time = 5 ms;\\ 
      & & Avg. rotational delay = 8 ms; transfer rate = 2 MB/s\\
      \end{tabular}

      Design the I/O system with maximum possible peak performance.
      What is the performance to cost ratio (in megabytes per second per 
      \$1000) of your design? For convenience, assume that 1 GB = 1000
      MB and 1 MB = 1000 KB. (10 points)
\item (5 points)
      Two monitors are said to be nested if a procedure in one monitor
      can call a procedure in another monitor and vice versa. Is there a
      problem if we allow monitors to be nested? If there is a problem,
      suggest two approaches (other than forbidding the use of nested 
      monitors) to avoid the problem.
\item (5 points)
      In the ADA programming language, processes are called tasks. Let
      {\bf Task A} and {\bf Task B} be two tasks and let $P$ be a
      procedure defined in {\bf Task A}. ADA provides two constructs
      Accept and Call which behave as follows:\\

      \hspace*{1in}\begin{tabular}{cc}
      \underline{\bf Task A} & \underline{\bf Task B}\\
      \vdots & \vdots\\
      Accept $P(\ldots)$ & Call Task A.$P(\ldots)$\\
      \vdots & \vdots\\
      \end{tabular}\\

      {\bf Task A} cannot execute the Accept procedure until {\bf Task
      B} executes the Call procedure. After executing the Call
      procedure, {\bf Task B} must wait until {\bf Task A} executes the
      Accept procedure. After that, both the tasks proceed
      independently. This is called the ADA tasking mechanism. Show how
      the ADA tasking can be implemented using semaphores.
\item (10 points)
      Consider a paging system using the working set model. At any time,
      the system keeps track of a constant number of previous references 
      called the {\em Window}. The working set is the set of distinct
      pages in the window. Define the following:\\
      \begin{tabular}{lcl}
      $\Delta$ & $=$ & Window size\\
      $\omega$ & $=$ & The reference string\\
      $P(\Delta)$ & $=$ & Total number of page faults\\
      $W(i,\Delta)$ & $=$ & Working set size after referencing $i^{th}$
                         page in $\omega$.\\
      $W(\Delta)$ & $=$ & Average working set size $=$ $\frac{1}{|\omega|}
		      \sum_{i=1}^{|\omega|}W(i,\Delta)$\\
      $F(\Delta)$ & $=$ & Average page fault rate $=$
      $\frac{P(\Delta)}{|\omega|}$
      \end{tabular}\\

      Show that for large $\omega$
      \begin{enumerate}
      \item $0\leq F(\Delta) \leq 1$. (2 points)
      \item $W(i,\Delta) \subseteq W(i,\Delta+1)$. (2 points)
      \item $F(\Delta) \approx W(\Delta+1) - W(\Delta)$. (6 points)
      \end{enumerate}
\item (4 points)
      What factors influence the selection of disk sector size? That is,
      why are large disk sectors good? Why are they bad? Why are small 
      disk sectors good? Why are they bad?
\item (6 points)
      A distributed mutual exclusion algorithm is said to obey the 
      {\bf No starvation} property if any processor that is trying 
      to enter the critical section will eventually succeed. Suppose
      that we are given an algorithm that will ensure mutual exclusion
      and no starvation for two processors. We can extend it to $n$
      processors as follows: Place the processors at the leaves of a 
      $n$ node complete binary tree called the tournament tree. To enter 
      the critical section, a processor has to move up to the root of the 
      tree. At every node of the tree, the two processor algorithm is used 
      to select from the two processors that may compete to gain access 
      to it. A processor exits the critical section by returning from
      the root to the leaf corresponding to it. Once a processor gains
      access to a node, another processor can not gain access to it
      until the first processor leaves the node.

      Prove that the $n$ processor distributed mutual exclusion algorithm 
      also obeys no starvation property. Does the no starvation property
      imply no deadlock? Why?
\end{enumerate}
\end{document}
