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

For et hurtigbuffer- ({\em cache-}) system skal det foretas en vurdering av
styringsstrategiene {\em gjennomskriving med blokkallokering ved skriv}
({\em write-through-with-write-allocate}, WTWA) og {\em skriv tilbake} ({\em
write-back}, WB) mot hverandre.

Anta ingen gjennomlesing (dvs.~ved en sidefeil f\aa r ikke CPU'en sine
data f\o r hele blokken er lest inn i hurtigbufferet). Hver blokk best\aa r
av $b$ ord, som kan overf\o res mellom hovedlageret og hurtigbufferet i l\o
pet av $b+c-1$ tidsenheter, der $c$ er hovedlagerets syklustid oppgitt i
antall ganger hurtigbufferets syklustid. Hurtigbufferets treffrate $h$
antas uavhengig av strategien. Sannsynligheten for at en lagerreferanse er
en {\bf skriv} betegnes med $p_{w}$, og sannsynligheten for at en blokk som
skal erstattes har blitt modifisert (kun interessant i forbindelse med
WB-strategien) betegnes med $p_{m}$. Normalt er $p_{m} > p_{w}$.
\begin{enumerate}
 \item Finn forventningsverdien av den tiden det tar \aa\
       betjene en referanse, uttrykt ved de ovennevnte st\o relsene, for begge
       de to strategiene.

 \item Oppgitt: $p_{w} = 0.16$ og $p_{m} = 0.56$. Hvordan g\aa r det med
       betjeningstiden med de to strategiene n\aa r
       \begin{enumerate}
        \item $h \rightarrow 1$ ?
        \item $h \rightarrow 0$ ?
       \end{enumerate}

 \item Finn et generelt uttrykk som viser n\aa r WTWA er bedre enn WB som en
       funksjon av $h$ og $b$. Anta at $c=10$ og $p_{w}, p_{m}$ som over.

\end{enumerate}
}


\Oppgave{%Problem 5.17, Hwang

Du skal se p{\aa} utf{\o}relsen av to programmer som utf{\o}res
samtidig av to prosessorer med delt minne.  Anta at A, B, C, D er satt til 0 fra
starten av og at {\em Print}-setningen skriver begge argumenter
udelelig, i samme sykel.  Ut-data fra programmene blir en 4-tuppel,
dvs. verdiene til de 4 variablene i rekkef{\o}lge, enten ADBC eller
BCAD. Vi har f{\o}lgende to program, med tilsammen 6 setninger: 

\begin{table}[htb]
\begin{center}
\begin{tabular}{p{3cm}p{3cm}} 
$P_0$: 		& $P_1$: \\
a. $A=1$	& d. $C=1$\\
b. $B=1$	& e. $D=1$\\
c. Print $A,D$	& f. Print $B,C$\\
\end{tabular}
\end{center}
\end{table}

\begin{enumerate}

\item List opp alle utf{\o}relses-rekkef{\o}lger best{\aa}ende av 6
setninger som vil beholde rekkef{\o}lgen av setningene i hvert enkelt
program. 

\item Anta at program-rekkef{\o}lgen blir beholdt, og at alle
minne-aksesser er atomiske, dvs. en skrive-operasjon utf{\o}rt av
\'{e}n prosessor ses umiddelbart av alle de andre prosessorene.  List
alle mulige 4-tuppel av ut-data kombinasjoner.

\item Anta at program-rekkef{\o}lgen blir beholdt, men at
minne-aksesser {\bf ikke} er atomiske, dvs. en skrive-operasjon
utf{\o}rt av \'{e}n prosessor kan bli bufret slik at enkelte andre
prosessorer ikke n{\o}dvendigvis vil kunne observere oppdateringen
umiddelbart.  List alle mulige 4-tuppel av ut-data kombinasjoner. 

\end{enumerate}
}

\end{document}
