\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 Solutions\\
Computer Architecture and Operating Systems\\September 16, 1995}
\author{}
\date{}
\maketitle
\vspace*{-0.8in}
\begin{enumerate}
\item Average memory access time $=$ Hit time $+$ miss rate $*$
            miss penalty.\\
      CPU Time $=$ IC $*$ (CPI$_{execution}$ + mem. acc./instr.
      $*$ miss rate $*$ miss penalty) $*$ cycle time\\
      Using these equations,
      \begin{center}
      \begin{tabular}{|l|c|c|}
      \hline\hline
      Organization & Avg. mem. access time & CPU Time per instr.\\
      \hline
      Direct Mapped & 14.6 ns & 18.44 ns\\
      2-way set associative & 14.77 ns & 18.53 ns\\
      4-way set associative & 14.72 ns & 18.42 ns\\
      \hline\hline
      \end{tabular}\\
      \end{center}

      From the table, Direct Mapped cache has the smallest average
      memory access time and the 4-way set associative cache results in
      the best CPU performance.
\item \begin{enumerate}
      \item Let $i$ be the clock cycle in which data is stored in the 
	    unit from which forwarding may be needed. Forwarding logic is 
	    needed
	    \begin{enumerate}
	    \item From EX to EX possibly forwarding in $i+1$, $i+2$ and
	          $i+3$.
	    \item From EX to DF possibly forwarding in $i+1$, $i+2$ and
          	  $i+3$.
	    \item From DS to EX possibly forwarding in $i+3$.
	    \end{enumerate}
      \item Increase in CPI due to {\em predict taken} strategy\\
	    $= 0.2(0.7*2+0.3*3) = 0.46$\\
            Increase in CPI due to {\em predict not taken} strategy\\
	    $= 0.2(0.3*0+0.7*3) = 0.42$\\
	    Therefore, {\em predict not taken} strategy is better.
      \item CPI $= 1.5 + 0.05(10+5) = 2.25$.
      \end{enumerate}
\item We need 10 disks for a storage capacity of 10 GB.\\
      Time taken per disk for one I/O access\\
      $=$ overhead $+$ seek time $+$ rotational delay $+$ transfer
      time\\
      $= 1+5+8+2 = 16$ ms.\\
      Effective transfer rate (4KB transferred in 16 ms) $= 0.25$ MB/s.\\
      Therefore, one string can effectively support all 10 disks.\\
      A disk can support the initiation of $\lceil \frac{1000}{16}\rceil 
	       = 63$ I/O operations per second.\\
      Therefore, one disk controller can effectively support all 10
      disks.\\
      The I/O design consists of one I/O bus, one Disk controller and
      String and 10 disks.\\
      Cost of the I/O system $=1000+3000+10*2000 = \$24,000$.\\
      Peak performance $=0.25*10 = 2.5$ MB/s.\\
      Performance to Cost ratio $=0.104$ MB/s/\$1000.
\item Nested monitors could cause deadlock. If a process currently
      running in monitor A requests monitor B and another process
      currently running in monitor B requests monitor A, then deadlock
      occurs. Approaches to avoid the problem:
      \begin{enumerate}
      \item If a process currently running in one monitor requests
            another monitor that is not immediately available, then the
	    process should relinquish the monitor in which it is
	    running, until it can get both.
      \item Ordering of resources always prevents deadlock. We can
            specify a predetermined order among the monitors and require 
	    that the monitors be requested in that order.
      \end{enumerate}
\item Let $S_1$ and $S_2$ be two binary semaphores both initialized to
      zero. To implement ADA tasking\\

      \hspace*{1in}\begin{tabular}{ccc}
      \underline{\bf Task A} & \hspace*{1in} & \underline{\bf Task B}\\
      \vdots & & \vdots\\
      DOWN($S_1$) & & Task A.$P(\ldots)$\\
      $P(\ldots)$ & & UP($S_1$)\\
      UP($S_2$) & & DOWN($S_2$)\\
      \vdots & & \vdots\\
      \end{tabular}
\item \begin{enumerate}
      \item $0\leq P(\Delta)\leq |\omega| \Rightarrow 0\leq F(\Delta)
            \leq 1$.
      \item Any page in a window of size $\Delta$ is also present in a
            window of size $\Delta+1$. Hence, $W(i,\Delta) \subseteq
	    W(i,\Delta+1)$.
      \item Define $v(i,\Delta) = \left\{
	           \begin{array}{ll}
	            1 & i^{th} {\rm page} \notin W(i-1,\Delta)\\
                    0 & i^{th} {\rm page} \in W(i-1,\Delta)\\
                   \end{array}\right.$\\\\

            \noindent$\begin{array}{lcl}
            F(\Delta) & = & \frac{P(\Delta)}{|\omega|}
		       = \frac{1}{|\omega|}\sum_{i=1}^{|\omega|}v(i,\Delta)\\\\
	    & = & \frac{1}{|\omega|}\left[\sum_{i=1}^{|\omega|}W(i,\Delta+1)
                            -\sum_{i=1}^{|\omega|}W(i-1,\Delta)\right]\\\\
            & = & \frac{1}{|\omega|}\sum_{i=1}^{|\omega|}
	    \left[W(i,\Delta+1)-W(i,\Delta)+W(i,\Delta)-W(i-1,\Delta)\right]\\\\
            & = & \frac{1}{|\omega|}\sum_{i=1}^{|\omega|}W(i,\Delta+1)
		  -\frac{1}{|\omega|}\sum_{i=1}^{|\omega|}W(i,\Delta)
		  +\frac{1}{|\omega|}W(\omega,\Delta)\\\\
            & \approx & W(\Delta+1) - W(\Delta)\\\\
            \end{array}$
      \end{enumerate}
\item Large disk sectors are good because we can obtain more data with
      the same seek time, thus reducing the effect of seek time. However,
      since the last sector of the file may not be totally used, large
      disk sectors cause wastage of storage space (fragmentation).

      With small disk sectors, less space is wasted due to
      fragmentation. But, since more sectors are needed to store the
      data, the table containing information about all sectors belonging
      to the file will be large. Also, the effect of seek time is
      enhanced.
\item Suppose that some processor $p_i$ is starved and let $v$ be the
      node of the tree closest to the root reached by it. There are at
      most two processors competing to gain access to the parent of $v$
      ($p_i$ and perhaps another processor that gained access to $v$'s
      sibling). Therefore, by the no starvation property of the two
      processor algorithm, $p_i$ will eventually gain access to $v$'s
      parent. This leads to a contradiction to the assumption that $v$
      is the node closest to the root reached by $p_i$.

      No starvation property implies no deadlock. If there is a
      deadlock, none of the processors will be able to enter the
      critical section. This means that every processors starves, thus
      violating the no starvation property.
\end{enumerate}
\end{document}
