Per ciascun capitolo dovrebbe preparare un numero di...

CAPITOLO 2

Soluzioni agli esercizi del libro:

2) 6

3) Utilizzando i simboli 0, 1 e 2 e considerando che sono necessarie 2 cifre per rappresentare 9

possibilità, è possibile ad esempio la codifica (00-lunedì), (01-martedì), (02-mercoledì), (10-

giovedì), (11-venerdì), (12-sabato), (20-domenica)

4) 10001011, 1000.01

5) 12011, 22112

6) 00010011, 11011010

7) 10101 + 1101 = 100010; 100011 – 10010 = 10001; 10000001 + 10000011 = 00000100 con

overflow

11) Si consideri che 2^10 = 1024 e 2^20 = (2^10)^2 = 1024^2 = 1048576 e che 2^4 = 16 < 20 < 2^5

=32. Per rappresentare in binario 20 milioni di valori è quindi sufficiente utilizzare 5 + 20 = 25 bit.

Poiché ad ogni cifra esadecimale corrispondono 4 bit (2^4 = 16) ne consegue che sono sufficienti

sequenze di 7 cifre esadecimali (25 / 4 = 6.25 da arrotondare a 7)

12) 73; 1001001; 16781313

13) 00100011 + 00010010 = 00110101; 00100011 - 00010010 = 00010001; 01100101 + 00110011

= 10011000 con overflow; 01100101 - 00110011 = 00110010

15) Complemento a 2 binario (a) 0 1011 1111, 10 0111 1101; (b) 0000 0000 1011 1111, 1111 1110

0111 1101. Complemento a 2 ottale: (a) 277, 7175; (b) 000277, 777175. Complemento a 2

esadecimale (a) 0BF, E7D; (b) 00BF, FE7D

Introduzione ai sistemi informatici 5/edDonatella Sciuto, Giacomo Buonanno, Luca Mari Copyright © 2016 – McGraw-Hill Education (Italy) Srl

CAPITOLO 3


4) Una soluzione possibile è basata sull’utilizzo della notazione unaria per i numeri, che prevede di

rappresentare un numero con una sequenza di simboli uguali (ad esempio il simbolo 1) lunga

quanto il numero. I due addendi siano scritti di seguito sul nastro, separati da una loczione vuota

(denotata dal simbolo 0). La macchina, a partire dalla prima locazione del nastro che verrà

cancellata, scorrerà il nastro fino alla locazione vuota di separazione, che sarà sovrascritta con un 1.

A questo punto la macchina tornerà indietro sul nastro fino alla prima locazione vuota per poi

arrestarsi sulla locazione precedente alla prima locazione che contiene il risultato (anche esso

rappresentato nella stessa notazione).

Stato Letto Vai a Scrivi Sposta

S0 1 S1 * Destra

S1 1 S1 1 Destra

S1 * S2 1 Sinistra

S2 1 S2 1 Sinistra

12)

inizio

i <- 0

i < n

fine

NO

SI

leggi N

a)

leggi v[i]

i <- i+1

inizio

fine

leggi N

b)

carica N

valori in v[ ]

usando a)

inizio

Risultato <- 0

Resto <- 0

i <- 1

Resto >=

Divisore

fine

NO

SI

leggi Dividendo

leggi Divisore

c)

j <- 1

Resto <- Resto +

i-esima cifra del

dividendo

Resto >=

j*Divisore

Risultato <-

Risultato*10 + j

Resto <- Resto –

j*Divisore

j <- j + 1

i <- i + 1

i > numero

cifre dividendo

NO

SI

stampa Risultato

stampa Resto


inizio

i <- 0

Somma <- 0

Cont <- 0

i < m

fine

NO

SI

d)

scrivi Cont

scrivi Somma

Cont <- Cont + 1

Somma <- Somma + v[i]

v[i] – 2*[v[i]/2]

= 0

SI

NO

inizio

j <- 0

Cont <- 0

j < n

fine

NO

SI

f)

scrivi Cont

Cont <- Cont + risultato

del passo precedente

j <- j + 1

applica d) alla

j-esima riga di

M[ ][ ]

m: lunghezza nota del

vettore v[ ]

n, m: dimensioni note della

matrice M[ ][ ]

inizio

i <- 0

Cont <- 0

i < n

fine

NO

SI

e)

scrivi Cont

Cont <- Cont + 1

j < m

SI

NO


matrice M[ ][ ]

j < m

j <- j + 1

i <- i + 1

SI

NO

j <- 0

inizio

i < n

fine

NO

SI

g)

temp <- M[i][C1]

M[i][C1] <- M[i][C2]

M[i][C2] <- Temp


matrice M[ ][ ]

leggi C1

leggi C2

i <- 0

i <- i + 1


13) Le due espressioni sono equivalenti: si può partire dalla seconda espressione e considerare che

!a c !a !b c + !a b c. Si ottiene !a c + !a !b !c + a b c !a !b c + !a b c + !a !b !c + a b c. Si può

raccogliere il primo con il terzo termine e il secondo con il quarto. Si ottiene !a !b c + !a !b !c + !a b

c + a b c !a !b (c + !c) + b c (!a + a) !a !b + b c. In alternativa, ragionando in forma tabellare si

ha:

a b c !a!b bc !a!b+bc !ac !a!b!c abc !ac+!a!b!c+abc

F F F T F T F T F T

F F T T F T T F F T

F T F F F F F F F F

F T T F T T T F F T

T F F F F F F F F F

T F T F F F F F F F

T T F F F F F F F F

T T T F T T F F T T

14, 15, 16 e 17)

inizio

N <= 0

fine

NO

SI

leggi Min

14)

Min <- N

inizio

Somma <- N

Max <- N

Min <- N

i <- 1

N <= 0

fine

SI

NO

leggi N

15)

i <- i + 1

N > Max

Somma <-

Si ipotizzi per semplicità

almeno un valore validoSi ipotizzi per semplicità

almeno un valore valido

leggi N

leggi N

Somma + N

Max <- N

NO

stampa Min

stampa Max

stampa Somma/i

N < Min

SI

NO

stampa Min

N < Min Min <- N

NO

SI

SI


16) Si ipotizzi per semplicità inizio

N >= 1

i <- 0

i = 0

leggi N

fine

SI

NO

Somma <-

Somma + x

x > Max

i <- i + 1

Max <- x

NO

stampa Min

stampa Max

stampa Somma/N

x < Min Min <- x

NO

i

SI

< NNO

leggi x

Somma = x

Min = x

Max = x

SI

SI


inizio

leggi Giorno

17)

fine

stampa

errore

Giorno <= 0SI

NO

leggi Mese

Mese <= 0SI

NO

Mese > 12SI

NO

leggi Anno

Anno <= 0SI

NO

Anno divisibile

per 400

SI

NO

Anno divisibile

per 4

Anno divisibile

per 100

NO

SI

SINO

Bisestile

<- 1

Bisestile

<- 0

Mese = 1SI

NO

Mese = 2

NO

Mese = 3

Mese = 4

SI

NO

SI

Mese = 5SI

NO

Mese = 6

SI

NO

Mese = 7

Mese = 8

SI

NO

SI

Mese = 9SI

NO

Mese = 10

SI

NO

Mese = 11SI

NO

SI

NO

NO

Prec <- 0

Ultimo <- 31

Prec <- 31

Ultimo <- 28 +

Bisestile

Prec <- 59

+ Bisestile

Ultimo <- 31

Prec <- 90

+ Bisestile

Ultimo <- 30

Prec <- 120

+ Bisestile

Ultimo <- 31

Prec <- 151

+ Bisestile

Ultimo <- 30

Prec <- 181

+ Bisestile

Ultimo <- 31

Prec <- 212

+ Bisestile

Ultimo <- 31

Prec <- 243

+ Bisestile

Ultimo <- 30

Prec <- 273

+ Bisestile

Ultimo <- 31

Prec <- 304

+ Bisestile

Ultimo <- 30

Prec <- 334

+ Bisestile

Ultimo <- 30

Giorno >

Ultimo

SI

NO

fine

stampa Prec

+ Giorno

Una soluzione migliore si ottiene impiegando un vettore che per ogni mese memorizza le

informazioni relative (Prec e Ultimo): in tal caso la parte destra del diagramma (in cui si valuta il

mese e si impostano Prec e Ultimo) si riduce a un solo blocco azione che lavora sul vettore.


18) E’ sufficiente mettere in OR i termini AND della tabella a cui corrisponde un valore V: !a!b!c +

!a!bc + ab!c + abc. Si noti che i quattro termini differiscono a coppie per una variabile (presente in

forma negata e affermata): pertanto tale variabile non influisce sul risultato e l’espressione si

semplifica in !a!b + ab.


CAPITOLO 4


8)

Problema 1.1

Dati

x, y, d interi

Risoluzione

leggi a e b

d <- a – b

se d > 0

allora

scrivi “max è x”

altrimenti

scrivi “max è y”

fine se

fine

Problema 1.3

Dati

a, b, m interi

Risoluzione

leggi a e b

m <- max(a,b)

finchè ci sono altri numeri da esaminare ripeti

leggi a

m <- max(a, m)

fine ciclo

scrivi “max è m”

fine

Esempio 2

Dati

n, ris, i interi positivi

Risoluzione

leggi n

ris <- 0

i <-0

finchè i < n ripeti

ris <- ris + i

i <- i + 1

fine ciclo

scrivi ris

fine

Problema 5.1

Dati


i, temp, v[n] interi

Risoluzione

i <- 0

finchè i < n/2

temp <- v[i]

v[i] <- v[n-i-1]

v[n-i-1] <- temp

i <- i

fine ciclo

fine

Problema 5.2

Dati

s[m], v[n] simboli

j, i interi

Risoluzione

i <- 0

finchè m < n- i ripeti

j <- 0

finchè v[i+j] = s ripeti

se j=m allora

scrivi “si”

fine

altrimenti

j <- j + 1

fine se

fine ciclo

i <- i + 1

fine ciclo

scrivi “no”

fine

Problema 5.3

Dati

l, i, temp, v[n] interi

Risoluzione

l <- n

finchè l > 1 ripeti

i <- 0

finchè i < l-1 ripeti

se v[i] > v[i+1]

allora

temp <- v[i]

v[i] <- v [i+1]

v[i+1] <- temp

fine se

i <- i+1

fine ciclo

l <- l - 1


fine ciclo

fine


CAPITOLO 5


8) Per ogni simbolo devono essere trasmessi 8 bit. La banda del canale permette 10kbit/secondo,

quindi la sorgente può emettere simboli a una velocità massima di 10/8=1,25ksimboli/secondo.

9) Da quanto detto riguardo gli errori sul canale è sufficiente rilevare errori su un solo bit per

simbolo per rilevare la maggior parte degli errori di trasmissione, risultato ottenibile con l’uso di un

bit di parità. Per ogni simbolo di sorgente servono quindi 9 bit (8+1) e quindi il flusso di sorgente

espresso in bit che il canale deve poter sostenere è di 10 ksimboli/secondo * 9 bit/simbolo = 90

kbit/secondo.

10) Il flusso deve arrivare integro, quindi è necessario innanzi tutto rilevare gli errori e poi

ritrasmettere i blocchi errati in tempo. Semplificando, assumiamo che i pacchetti ritrasmessi non

siano ulteriormente affetti da errore (0,02 * 0,02 = 0,004): è necessario considerare che la sorgente

deve generare il flusso più il 2% che viene ritrasmesso, mentre il canale deve trasportare il flusso, i

bit di parità e il 2% di blocchi ritrasmessi comprensivi di bit di parità. Quindi la sorgente deve

generare 100 kbit/secondo * 1.02 = 102 kbit/secondo e il canale deve poter trasportare (100

kbit/secondo + 100 kbit/secondo / 100 bit/blocco * 1 bit/blocco) * 1.02 = 101 kbit/secondo * 1.02 =

103.02 kbit/secondo.


CAPITOLO 6


5)

IR = MI[PC], PC = PC + 1;

BR[SRC1] = R02, BR[SRC2] = R03, BR[DEST] = R01;

ALU.OR(BR[R02], BR[R03]);

BR[R01] = ALU.

6) ERRATUM: La percentuale di istruzioni del tipo A è 78%. Si consideri una sequenza di N

istruzioni. Il tempo medio di esecuzione di una istruzione senza pipeline è 0.8*30 ns + 0.1*40 ns +

0.1*35 ns = 24 ns+ 4 ns + 3.5 ns = 31.5 ns; il tempo complessivo speso senza pipeline per una

sequenza di N istruzioni è 31.5N. Il tempo complessivo speso per una sequenza di N istruzioni con

pipeline è dato dal tempo speso per la prima istruzione più il tempo speso per le rimanenti N-1

istruzioni nel primo stadio, e quindi è 50 ns + 10*(N–1) ns = (40 + 10N) ns. Il miglioramento è dato

dal tempo speso senza pipeline meno il tempo speso con la pipeline normalizzato al tempo speso

senza pipeline: (31.5N – 40 – 10N) ns / 31.5N ns = 21.5/31.5 – 40/31.5N = 43/63 – 80/63N. Il

valore limite del miglioramento (N ) è 43/63 = 68.25%, quindi il miglioramento richiesto è

possibile e si ottiene quando 31.5N > 3*(40 + 10N) -> 31.5N > 120 + 30N -> 1.5N > 120 -> N > 80.

8) Nel primo caso si ha TA = 0.9 * 2 + 0.1 * 20 = 1.8 + 2.0 = 3.8; nel secondo caso si ha TA = 0.8 *

2 + 0.2 * (0.8 * 4 + 0.2 * 20) = 1.6 + 0.2 * (3.2 + 4.0) = 1.6 + 1.44 = 3.04; nel terzo caso si ha TA =

0.8 * 2 + 0.2 * (x * 5 + (1 – x)* 20) = 1.6 + 0.2 * (20 – 15x) = 5.6 – 3x. La seconda soluzione è

migliore della prima. La terza soluzione è migliore della seconda quando 5.6 – 3x < 3.04, cioè 3x >

2.56, da cui x > 0.8533 (85.33%).

9) Nel primo caso si ha TA = 0.9 * 2 + 0.1 * 8 = 1.8 + 0.8 = 2.6; nel secondo caso si ha TA = 0.8 *

2 + 0.2 * (0.8 * 4 + 0.2 * 8) = 1.6 + 0.2 * (3.2 + 1.6) = 1.6 + 0.96 = 2.56; nel terzo caso si ha TA =

0.8 * 2 + 0.2 * (x * 5 + (1 – x)* 8) = 1.6 + 0.2 * (8 – 3x) = 3.2 – 0.6x. La seconda soluzione è

migliore della prima. La terza soluzione non può essere mai migliore della seconda perché al

massimo arriva a 2.6 (quindi pari alla prima). In pratica la disequazione 3.2 – 0.6x < 2.56 impone

che x > (3.2–2.56)/0.6 = 0.64/0.6 = 1.06, ma x non può essere maggiore di 1 (la frequenza di

successo non può superare il 100%), quindi non c’è nessuna possibilità che la terza soluzione sia

migliore della seconda e potrà al limite (!!) essere uguale alla prima.


CAPITOLO 7


5) Rimangono:

01: start (processo inizia in stato pronto)

03: termina esecuzione (modo kernel)

09: è il primo in coda e tocca a lui (contemporanea a 03 o 10 oppure 17)

10: preempt (quanto di tempo scaduto)

11: è arrivato l’evento atteso (vedi 17)

13: interrupt o SVC (supervisor call)

14: RTI (ritorno da Interrupt/SVC)

17: serve qualcosa dall’esterno (aspetta un evento)

Eliminate: 02 04 05 06 07 08 12 15 16 18 19 20

6) P1 è stato deschedulato perché ha richiesto una operazione che richiede una risorsa esterna e

quindi ha seguito il percorso (5,7); P2 era pronto e ha preso il posto di P1 in esecuzione seguendo il

percorso (2,4); P3 è stato sbloccato dall’arrivo dell’evento esterno che attendeva ed è passato tra i

processi pronti (8)

8) E’ necessario procedere al calcolo della dimensione degli indirizzi: le pagine sono di 512 kByte

ciascuna, quindi sono necessari 19 bit di offset; la memoria fisica è di 2 GByte, quindi sono

necessari 31 bit di indirizzo fisico (di cui 12 vanno ad indicare il numero di pagina fisica e 19

l’offset). Nel caso di una memoria virtuale di 1/2/4 GByte, sono necessari 30/31/32 bit di indirizzo

virtuale (ovvero 11/12/13 per il numero di pagina e 19 per l’offset). Le dimensioni della tabella

delle pagine sono date dal numero di celle (2^bit necessari per il numero di pagine) per il numero di

bit necessario a memorizzare il numero della pagina fisica corrispondente, cioè

1. per una memoria virtuale di 1 GByte: 2^11 celle × 12 bit/cella = 2048 × 12 bit = 24576 bit




Per ciascun capitolo dovrebbe preparare un numero di...

Documents

Transcript of Per ciascun capitolo dovrebbe preparare un numero di...