\documentstyle[a4,oving,block]{article-n}
\begin{document}

Oppgave 1

Skriver : Sannsynligheten for at en referanse er en {\bf les} $=p_{r}
          = 1-p_{w}$, og feilraten $f=1-h$.
\begin{enumerate}
 \item Forventningstider:
  \begin{itemize}

   \item WTWA: En referanse kan foreg\aa\ p\aa\ fire i dette henseende ulike
         m\aa ter: {\bf Les} fra blokk som {\em finnes} i h.\ b.\ , {\bf les} fra
         blokk som {\em ikke} finnes i h.\ b.\ , {\bf skriv} til blokk som
         {\em finnes} i h.\ b.\ , og {\bf skriv} til blokk som {\em ikke} finnes
         i h.\ b. Den tiden det tar \aa\ betjene disse fire typene er hhv.\
         $1$, $(b+c-1)+1$, $c$ og $c+(b+c-1)$ hurtigbuffer-sykler. Husk at
         $(b+c-1)$ er den tiden det tar \aa\ overf\o re en blokk mellom h.\ b.\
         og hovedlager. Forventningstiden for en betjening blir da:
         \[ \overline{t}_{WTWA} = p_{r}h\cdot 1 + p_{r}f[(b+c-1)+1] + p_{w}hc
                                + p_{w}f[(b+c-1)+c] \]
         \[ = 1 - p_{w} + (1-h)(b+c-1) + p_{w}c \]

   \item WB: Ved denne strategien spiller det ingen rolle om referansen er en
         {\bf skriv} eller en {\bf les} --- fremgangsm\aa ten blir den samme i
         begge tilfeller : En blokk hentes til h.\ b.\ dersom den ikke er der
         n\aa r den blir referert. Den blokken som skal erstattes av den nye
         m\aa\ dessuten skrives tilbake til hovedlageret dersom den har blitt
         modifisert (sannsynlighet $p_m$). F\aa r dermed kun to distinkte
         tilfeller : Treff eller ikke treff. Ved treff er betjeningstiden lik 1,
         ved bom er betjeningstiden lik $[(b+c-1) + p_m(b+c-1) + 1]$.
         Forventningstiden blir dermed:
         \[ \overline{t}_{WB} = h\cdot 1 + f[(b+c-1) + p_m(b+c-1) + 1] \]
         \[ = 1 + (1-h)(1+p_m)(b+c-1) \]
  \end{itemize}


 \item Sammenlikning for $h \rightarrow 1$ og $h \rightarrow 0$:
  \begin{enumerate}
   \item \[ h \rightarrow 1 \Rightarrow \left\{
            \begin{array}{l}
              \overline{t}_{WTWA} \rightarrow
                          1+p_w(c-1) = 1+0.16(c-1)  \\

              \overline{t}_{WB} \rightarrow 1
            \end{array}  \right. \]

         Alts\aa\ : N\aa r $h \rightarrow 1$ er WB bedre enn WTWA.

   \item \[ h \rightarrow 0 \Rightarrow \left\{
            \begin{array}{l}
              \overline{t}_{WTWA} \rightarrow
                          b+c+p_w(c-1) = b+c+0.16(c-1)  \\

              \overline{t}_{WB} \rightarrow
                          1+(1+p_m)(b+c-1) = b+c+0.56(b+c-1)
             \end{array}  \right. \]

         Alts\aa\ : N\aa r $h \rightarrow 0$ er WTWA bedre enn WB.
  \end{enumerate}
\newpage
 \item Sammenlikning for vilk\aa rlig $h$:

       WTWA er bedre enn WB dersom:

       \[ \overline{t}_{WB} > \overline{t}_{WTWA} \]
       \[ \Updownarrow \]
       \[ 1+(1+p_m)(1-h)(b+c-1) > 1-p_w+(1-h)(b+c-1)+p_wc \]
       \[ \Updownarrow \]
       \[ (1-h)(b+c-1)p_m >p_w(c-1) \]
       \[ \Updownarrow \]
       \[ (1-h) > \frac{p_w}{p_m} \frac{c-1}{b+c-1} \]
       \[ \Updownarrow \]
       \[ \underline{h < 1 - \frac{p_w}{p_m} \frac{c-1}{b+c-1}
                       = 1 - \frac{2.57}{b+9} } \]
\end{enumerate}



Oppgave 2 %Problem 5.17, Hwang

\begin{enumerate}

\item 

N{\aa}r $p$ prosessorer brukes, og hver utf{\o}rer $m_i$ setninger, $i
= 1, ... ,p$, s{\aa} kan det totale antall mulige
utf{\o}relses-rekkef{\o}lger uttrykkes ved formelen:
\[ \frac{(\sum_{i=1}^{p} m_i)!}{\prod_{i=1}^{p}(m_i!)},\]
som er identisk med tallet p{\aa} mulge m{\aa}ter {\aa} flette
elementene fra $p$ sorterte lister.

Setter vi inn for $p = 2$, $m_1 = 3$ og $m_2 = 3$ f{\aa}r vi 20
forskjellige program-rekkef{\o}lger:

{\bf abcdef, abdcef, abdecf, abdefc, adbcef, adbecf, adbefc, adebcf,
adebfc, adefbc, dabcef, dabecf, dabefc, daebcf, daebfc, daefbc,
deabcf, deabfc, deafbc, defabc}.


\item Mulige ut-data kombinasjoner n{\aa}r program-rekkef{\o}lgen
beholdes og vi har atomisk minneaksess:

{\bf 0111, 1011 og 1111}.

\item Her antar vi at program-rekkef{\o}lgen blir beholdt, men at
minne-aksesser {\bf ikke} er atomiske. F{\o}r $c$ blir utf{\o}rt, vil
$A$ ha blitt satt til $1$ av $a$.  Tilsvarende vil $C$ ha blitt satt
til $1$ f{\o}r den er skrevet ut av $f$.   Siden vi har ikke-atomiske
minne-aksesser, vil verdien til $D$ i $c$ og $B$ i $f$ v{\ae}re
usikre. Derfor kan ut-data blit enten $1xx1$ eller $x11x$, avhengig
av program-rekkef{\o}lgen.  

Mulige ut-data kombinasjoner blir:

{\bf 1001, 1011, 1101, 0110, 0111, 1110 og 1111}.

\end{enumerate}

\end{document}


