45214 Datamaskinarkitektur - Øvinger 1995

Løsning 5

Oppgave 1

Skriver : Sannsynligheten for at en referanse er en les , 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, , c og hurtigbuffer-sykler. Husk at er den tiden det tar å overfø re en blokk mellom h. b.\ og hovedlager. Forventningstiden for en betjening blir da:

  

  

• 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 ). Få r dermed kun to distinkte tilfeller : Treff eller ikke treff. Ved treff er betjeningstiden lik 1, ved bom er betjeningstiden lik . Forventningstiden blir dermed:

  

  

b) Sammenlikning for og :

1. 

   Altså : Nå r er WB bedre enn WTWA.

2. 

   Altså : Nå r er WTWA bedre enn WB.

c)Sammenlikning for vilkå rlig h:

WTWA er bedre enn WB dersom:

Oppgave 2

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

som er identisk med tallet på mulge måter å flette elementene fra p sorterte lister.

Setter vi inn for p = 2, og 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.