Oppgave 1

Skriver : Sannsynligheten for at en referanse er en les = p_{r} = 1 − p_{w}, og feilraten f = 1 − h.

a) Forventningstider:

• WTWA: En referanse kan foregå på fire i dette henseende ulike måter: Les fra blokk som finnes i h. b. , les fra blokk som ikke finnes i h. b. , skriv til blokk som finnes i h. b. , og skriv til blokk som ikke finnes i h. b. Den tiden det tar å 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 å overføre en blokk mellom h. b. og hovedlager. Forventningstiden for en betjening blir da:

\overline{t}_{W T W A} = p_{r}h · 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

• WB: Ved denne strategien spiller det ingen rolle om referansen er en skriv eller en les — fremgangsmåten blir den samme i begge tilfeller : En blokk hentes til h. b. dersom den ikke er der når den blir referert. Den blokken som skal erstattes av den nye må dessuten skrives tilbake til hovedlageret dersom den har blitt modifisert (sannsynlighet p_{m}). Få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}_{W B} = h · 1 + f[(b + c − 1) + p_{m}(b + c − 1) + 1]
= 1 + (1 − h)(1 + p_{m})(b + c − 1)

b) Sammenlikning for h → 1 og h → 0:

(a)

h → 1 ⇒ \{ \begin{matrix}\overline{t}_{W T W A} → 1 + p_{w}(c − 1) = 1 + 0.16(c − 1) \\ \overline{t}_{W B} → 1 \end{matrix}

Altså : Når h → 1 er WB bedre enn WTWA. (b)

h → 0 ⇒ \{ \begin{matrix}\overline{t}_{W T W A} → b + c + p_{w}(c − 1) = b + c + 0.16(c − 1) \\ \overline{t}_{W B} → 1 + (1 + p_{m})(b + c − 1) = b + c + 0.56(b + c − 1) \end{matrix}

Altså : Når h → 0 er WTWA bedre enn WB. c) Sammenlikning for vilkårlig h:

WTWA er bedre enn WB dersom:

\overline{t}_{W B} > \overline{t}_{W T W A}
⇕
1 + (1 + p_{m})(1 − h)(b + c − 1) > 1 − p_{w} + (1 − h)(b + c − 1) + p_{w}c
⇕
(1 − h)(b + c − 1)p_{m} > p_{w}(c − 1)
⇕

(1 − h) > \frac{p_{w}}{p_{m}} \frac{c − 1}{b + c − 1}

⇕

\underline{h < 1 − \frac{p_{w}}{p_{m}} \frac{c − 1}{b + c − 1} = 1 − \frac{2.57}{b + 9}}

Oppgave 2

a) Når p prosessorer brukes, og hver utfører m_{i} setninger, i = 1, ..., p, så kan det totale antall mulige utførelses-rekkefølger uttrykkes ved formelen:

\frac{(∑_{i=1}^{p} m_{i})!}{∏_{i=1}^{p}(m_{i}!)},

som er identisk med tallet på mulge måter å flette elementene fra p sorterte lister. Setter vi inn for p = 2, m_{1} = 3 og m_{2} = 3 får vi 20 forskjellige program-rekkefølger: abcdef, abdcef, abdecf, abdefc, adbcef, adbecf, adbefc, adebcf, adebfc, adefbc, dabcef, dabecf, dabefc, daebcf, daebfc, daefbc, deabcf, deabfc, deafbc, defabc.

b) Mulige ut-data kombinasjoner når program-rekkefølgen beholdes og vi har atomisk minneaksess: 0111, 1011 og 1111.

c) Her antar vi at program-rekkefølgen blir beholdt, men at minne-aksesser ikke er atomiske. Før c blir utført, vil A ha blitt satt til 1 av a. Tilsvarende vil C ha blitt satt til 1 fø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ære usikre. Derfor kan ut-data blit enten 1xx1 eller x11x, avhengig av program-rekkefølgen. Mulige ut-data kombinasjoner blir: 1001, 1011, 1101, 0110, 0111, 1110 og 1111.