Županijsko natjecanje 2016. godine za 3. i 4. razred Srednje Škole - 2. zadatak

Većina računala, osim radne memorije, na samom procesoru sadrži relativno malenu, ali vrlo brzu priručnu memoriju (takozvani cache) u koju procesor privremeno sprema dijelove radne memorije kojima često pristupa.

Pretpostavimo da se radna memorija računala sastoji od 2 gibibyte-a odnosno 2^31 byte-a adresiranih brojevima od 0 do 2^31 − 1. Memorija je podijeljena u blokove veličine 64 byte-a – svaki blok počinje na adresi djeljivoj s brojem 64.

Priručna memorija se sastoji od m blokova označenih brojevima 0 do m − 1. Svaki blok priručne memorije također sadrži točno 64 byte-a. Na početku rada računala svi blokovi priručne memorije su prazni. Pretpostavimo da u nekom trenutku naredba želi pročitati vrijednost byte-a na adresi x, to se vrši na sljedeći način:

1. Ukoliko se u priručnoj memoriji već nalazi blok koji sadrži adresu x onda se vrijednost čita iz tog bloka priručne memorije.

2. Ukoliko se u priručnoj memoriji ne nalazi blok koji sadrži adresu x onda se cijeli blok B koji sadrži adresu x najprije čita iz radne memorije i prebacuje u priručnu memoriju, a zatim se vrijednost čita iz tog bloka priručne memorije kao u slučaju 1. Blok B se prebacuje u priručnu memoriju na sljedeći način:

   (a) Ukoliko priručna memorija nije puna, odabire se prvi po redu slobodni blok priručne memorije i u njega se kopira blok B.

   (b) Ukoliko je priručna memorija puna, iz priručne memorije se najprije izbacuje jedan blok te se na njegovo mjesto kopira blok B. Blok koji će se izbaciti se bira tako da se za svaki blok u priručnoj memoriji razmatra posljednja naredba koja je iz njega čitala, te se izabere onaj blok za koji je ta posljednja naredba bila najdalje u prošlosti.

Slučaj 1. se naziva pogodak priručne memorije, a slučaj 2. promašaj priručne memorije.

Zadan je niz memorijskih adresa koji se redom čitaju. Potrebno je za svaku za svaku adresu odrediti je li se dogodio pogodak ili promašaj te iz kojeg je bloka priručne memorije pročitana tražena vrijednost.

ULAZNI PODACI

U prvom redu nalaze se prirodni brojevi m i n (m ≤ 50, n ≤ 1000) broj blokova priručne memorije i broj adresa. U k-tom od sljedećih n redova nalazi se jedan cijeli broj xk (0 ≤ xk < 2^31) – k-ta adresa.

IZLAZNI PODACI

Potrebno je ispisati n redova. U k-tom redu potrebno je ispisati ispisati ili “pogodak b” ili “promasaj b”, gdje je b redni broj bloka priručne memorije iz kojeg je pročitana k-ta adresa.

PRIMJERI TEST PODATAKA

ulaz

4 9
64
345
123
312
433
452
123
63
98

izlaz

promasaj 0
promasaj 1
pogodak 0
promasaj 2
promasaj 3
promasaj 1
pogodak 0
promasaj 2
pogodak 0

ulaz

2 4
11
111
22
222

izlaz

promasaj 0
promasaj 1
pogodak 0
promasaj 1

ulaz

3 6
16
55
354
783
1024
653

izlaz

promasaj 0
pogodak 0
promasaj 1
promasaj 2
promasaj 0
promasaj 1

ulaz

1 2
11
1111

izlaz

promasaj 0
promasaj 0

Objašnjenje

Pojašnjenje prvog primjera: Sljedeća tablica opisuje sadržaj blokova privremene memorije nakon svake pročitane adrese. Zauzeti blokovi su označeni početnom i završnom adresom bloka radne memorije koji sadrže, dok su prazni blokovi označeni s ε: