Unidad 4 - Multiprocesadores - 2da Parte

Vista previa del material en texto

Multicomputadores y
Multiprocesadores
Unidad 4:
Segunda Parte
Ing. Carlos A. Afranllie
La diferencia básica entre consistencia de memoria y
coherencia de caché es que la primera determina
cuándo un valor escrito puede ser visto por una
lectura, y la segunda indica qué valores deberían
poder ser devueltos por una lectura (sin indicar
cuándo).
El problema de la coherencia de caché aparece en el
momento en que introducimos la caché en la jerarquía
de memoria de los procesadores que forman parte de
un multiprocesador.
Coherencia de caché
Propiedad fundamental
“La memoria debe proporcionar un conjunto de
direcciones para almacenar valores, y cuando se lea una
de estas direcciones debe devolver el último valor escrito
en ella.”
En el caso de usar varios procesadores, nos gustaría poder basarnos
en la misma propiedad cuando dos procesos se ejecuten sobre
diferentes procesadores de tal forma que el resultado de ejecutar
un programa que usa varios procesos sea el mismo
independientemente de si los procesos se ejecutan o no en
diferentes procesadores físicos.
Coherencia de caché
En los sistemas multiprocesador se disponen de varios
niveles de caché asociados a cada procesador. Esta
organización es esencial para obtener un buen
desempeño.
Sin embargo, esto ocasiona el problema conocido como
coherencia de caché…
Pueden existir varias copias del mismo dato
simultáneamente en cachés diferentes y, si los
procesadores actualizan sus copias, puede producirse una
visión inconsistente de la memoria.
Coherencia de caché
El problema de la coherencia de las cachés
Ejemplo 1: Supongamos dos procesadores, cada uno con su caché,
conectados a una memoria compartida. Supongamos que ambos
procesadores acceden a una misma posición X en memoria
principal. La figura muestra los contenidos de las cachés y memoria
principal asumiendo que ninguna caché contiene inicialmente la
variable que vale 1. También se asume una caché write-through
Coherencia de caché
Ejemplo de un multiprocesador sin coherencia de caché
Coherencia de caché
Los datos pueden ser modificados y guardadados en la 
caché
¿Qué pasa si otro procesador quiere esos datos?
¡El procesador
lee los datos 
antiguos!
El Problema de la Coherencia de caché
Ejemplo 2:
El Problema de la Coherencia de caché
1) Write-updated o write broadcast: Mediante este protocolo se
mantienen actualizadas las copias del dato (bloque de memoria)
en las cachés del resto de procesadores.
2) Write-invalidate: Mediante este protocolo se pretende asegurar
que el que escribe tiene la exclusividad del dato (bloque de
memoria), haciendo que el resto de procesadores invaliden su
copia y no puedan tener copias desactualizadas. El dato (bloque
de memoria) es actualizado en memoria cuando es flushed /
reemplazado de la caché o lo pide otro procesador. Con este
protocolo, el dato (línea de caché con el bloque de memoria
donde está el dato) tiene unos bits de estado para indicar
exclusividad, propiedad y si ha sido modificado (dirty).
Protocolos de escritura
• Protocolos de sondeo “Snoopy”:
Para sistemas basados en un único bus, con un
número no demasiado grande de procesadores,
cada uno con su caché.
• Protocolos basados en directorios:
Para sistemas más complejos con varios buses o
varias subredes con un gran número de nodos
procesadores.
Mecanismo hardware
• Observan la actividad del bus y ejecutan,
mediante brodcasts, los pasos necesarios para
mantener la coherencia.
• Costoso en términos de ancho de banda, sobre
todo en redes multistage. Quien escribe avisa
con un broadcast (a todos).
• Todos los procesadores sondean el bus para
detectar modificaciones que le incumban.
Sistemas de Sondeo (Snoopy)
Tipos de protocolos:
• Write-update o write-broadcast o actualizar en
escritura: se basa en asegurar que un procesador tiene
acceso exclusivo a un dato antes de que acceda a él. Esto
se consigue invalidando todas las líneas de todas las
cachés que contengan un dato que está siendo escrito en
ese momento.
• Write-invalidate o invalidar en escritura: actualiza todas
las copias de las cachés cuando se escribe un determinado
dato. Este protocolo se llama actualizar en escritura.
Sistemas de Sondeo (Snoopy)
Protocolos para medios compartidos
• Protocolos de invalidación: Invalidan todas las
copias del bloque que existan en el resto de las
memorias cache, y dejan por lo tanto una única
copia, la que se ha modificado.
• Protocolos de actualización: Actualizan todas
las copias del bloque, enviando a través del bus
el nuevo valor de la palabra modificada.
Sistemas de Sondeo (Snoopy)
Protocolos de Invalidación
• Protocolo de 3 estados (MSI)
• Protocolo de 4 estados Illinois (MESI)
• Protocolo de 4 estados Berkeley (MOSI)
Sistemas de Sondeo (Snoopy)
Estados de los bloques en la memoria cache
y señales de control
• I Inválido (invalid): Un bloque está en estado I si la
información que contiene no es válida; es lo mismo que
si no estuviera en la cache (un fallo de cache).
• E Exclusivo (exclusive, reserved): Un bloque está en
estado E si se trata de la única copia en todas las caches
del multiprocesador y si además su contenido es el
mismo que el del bloque en memoria principal, es decir,
es coherente.
Sistemas de Sondeo (Snoopy)
Estados de los bloques en la memoria cache
y señales de control
• MModificado (modified, dirty, exclusive rd/wr): Un bloque en
estado M es la única copia existente en el multiprocesador, pero
no está actualizado en memoria principal: se ha escrito en la cache
pero no en memoria principal (write-back).
• S Compartido (shared, shared rd only): Existen (o pueden existir)
múltiples copias de dicho bloque en el resto de las caches del
multiprocesador, y todas las copias son iguales entre sí y,
normalmente, iguales con la copia de memoria principal
(coherentes).
Sistemas de Sondeo (Snoopy)
Estados de los bloques en la memoria cache
y señales de control
• O Propietario (owner, shared dirty): Existen (o pueden existir)
múltiples copias de dicho bloque en el resto de las caches del
multiprocesador, pero, aunque entre ellas son iguales, el bloque
no está actualizado en memoria principal. La copia en estado O
será la encargada, en su momento, de actualizar la memoria
principal y mantener así la coherencia (por ejemplo, al ser
reemplazada). El resto de copias, si existen, se encuentran en
estado S (atención, esas copias no son coherentes con memoria
principal).
Sistemas de Sondeo (Snoopy)
1. Acciones del procesador local
PR: processor read: Se lee una variable (en un bloque de
datos). Si el bloque está en la cache (acierto), no hay que
hacer nada; pero si no está (fallo) hay que generar una
petición de lectura de ese bloque (BR, bus request).
PW: processor write: Se escribe en una variable (un bloque
de cache). En general, hay que avisar a los otros
procesadores, para que actualicen el estado de dicho
bloque en su cache: INV (invalidar) o BC (actualizar), en
función del tipo de protocolo. Además, si ha sido un fallo,
hay que pedir el bloque de datos correspondiente.
Estados de los bloques en la
memoria cache y señales de control
2. Acciones que se observan en el bus
BR: bus read: Un procesador quiere leer una palabra y se
ha producido un fallo en su cache (no está). Tienen por
tanto que conseguir el bloque correspondiente, y para ello
se genera esta petición (BR en el bus de control, y la
dirección en el bus de direcciones). Todos los snoopy
locales tienen que considerar esta señal para adecuar el
estado del bloque (si tienen una copia del mismo).
Estados de los bloques en la
memoria cache y señales de control
2. Acciones que se observan en el bus
INV: invalidate [ en los protocolos de invalidación ]: Se
escribe una palabra en la cache y, por tanto, hay que
eliminar todas las copias de dicho bloque. Se envía al bus
de control la señal INV y al bus de direcciones la dirección
del bloque a anular. Todos los snoopy tienen que responder
adecuadamente a la señal, anulando, en su caso, la copia
del bloque.Estados de los bloques en la
memoria cache y señales de control
2. Acciones que se observan en el bus
BC: broadcast [ en los protocolos de actualización ]: Se
escribe una palabra en la cache, por lo que hay que
actualizar todas las copias de dicha variable. Se activa la
señal BC en el bus de control, y se pone la dirección de la
variable en el de direcciones y nuevo valor en el de datos).
Todos los snoopy tienen que responder adecuadamente a
la señal, actualizando, en su caso, la variable
correspondiente.
Estados de los bloques en la
memoria cache y señales de control
3. Otras señales de control
BW: bus write: Un procesador va escribir un bloque entero de
datos en memoria principal. Esto va a ocurrir en los casos en los
que la política de escritura sea write-back, cuando es necesario
actualizar datos o en los reemplazos de bloques modificados.
BW*: Un procesador va a escribir una palabra en memoria
principal (estamos usando por tanto WT). Esta señal de control no
es estrictamente necesaria, ya que puede utilizarse para ello la
señal INV (o BC), porque al escribir la memoria principal también
hay que invalidar (o actualizar) el resto de copias (usaremos el *
para indicar una transferencia de sólo una palabra).
Estados de los bloques en la
memoria cache y señales de control
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Acción Est. P1 Est. P2 Est. P3 Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P3 escribe U I - M Bus RdX MP
P1 lee U S - S Bus Rd C3
P2 lee U S S S Bus Rd MP
P3 escribe U I I M Bus RdX MP
P1 escribe U M I I Bus RdX MP ó C3
P1 escribe U M I I - C1
P1 lee U M I I - C1
P3 lee U S - S Bus Rd C1
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 3 estados MSI
Protocolo de 3 estados MSI
Fallos y aciertos de escritura y lectura
Fallo de lectura
Caché que tiene el Fallo Otras cachés
I -> S
S (1 o más) -> S
M (solo 1) -> S
Fallo de escritura
Caché que tiene el Fallo Otras cachés
I -> M
S (1 o más) -> I
M (solo 1) -> I
Acierto de lectura
Caché que tiene el Acierto Otras cachés
S -> S S (1 o más) -> S
M -> M -
Acierto de escritura
Caché que tiene el Acierto Otras cachés
S -> M S (1 o más) -> S
M -> M -
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Acción Est. P1 Est.
P2
Est. P3 Acc. Bus Datos
x
P1 lee U E - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 escribe U M - I Bus RdX MP
P2 escribe U I M I Bus RdX C1
P3 lee U I S S Bus Rd C2
P1 lee X E - - Bus Rd MP
P1 lee X E - - - C1
P1 escribe X M - - - C1
P1 escribe X M - - - C1
P1 lee X M - - - C1
P3 lee X S - S Bus Rd C1
P1 lee X S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MESI
Protocolo de 4 estados MESI
Fallos y aciertos de escritura y lectura
Fallo de lectura Fallo de escritura
Acierto de lectura Acierto de escritura
Caché que tiene el Fallo Otras cachés
I -> E -
I -> S
S (2 o más) -> S
M (solo 1) -> S
E (solo 1) -> S
Caché que tiene el Fallo Otras cachés
I -> E -
I -> M
S (2 o más) -> I
M (solo 1) -> I
E (solo 1) -> I
Caché que tiene el Acierto Otras cachés
S -> S S (2 o más) -> S
M -> M -
E -> E -
Caché que tiene el Acierto Otras cachés
S -> M S (2 o más) -> I
M -> M -
E -> M -
Carlos
Rectángulo
En el Protocolo de 4 estados Berkeley (MOSI), la caché
de datos incluye dos bits de estado que indican uno de
los cuatro siguientes estados:
•Modificado (M): La línea de caché ha sido escrita
una o más veces por el propietario, y la copia de
la caché es la única en el sistema (por lo tanto
inconsistente con el resto de copias).
• Propietario (Owner): Los datos que han sido
escritos por el propietario, los comparte con
las otras cachés que los solicitan, las cuales
se encuentran en SL.
• Compartida (Shared): La línea de caché, es
consistente con la copia del propietario.
• Inválida (I): La línea no se encuentra en la caché
o no es consistente con la copia en memoria.
Protocolo de 4 estados MOSI
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
P3 escribe U I - M - C3
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
P3 escribe U I - M - C3
P2 lee U I S O Bus Rd C3
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
P3 escribe U I - M - C3
P2 lee U I S O Bus Rd C3
P2 escribe U I M I Bus RdX C2
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
P3 escribe U I - M - C3
P2 lee U I S O Bus Rd C3
P2 escribe U I M I Bus RdX C2
P1 escribe U M I I Bus RdX C2
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
P3 escribe U I - M - C3
P2 lee U I S O Bus Rd C3
P2 escribe U I M I Bus RdX C2
P1 escribe U M I I Bus RdX C2
P3 lee U O I S Bus Rd C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
P3 escribe U I - M - C3
P2 lee U I S O Bus Rd C3
P2 escribe U I M I Bus RdX C2
P1 escribe U M I I Bus RdX C2
P3 lee U O I S Bus Rd C1
P1 lee U O I S - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Acción Est.
P1
Est.
P2
Est.
P3
Acc. Bus Datos x
P1 lee U S - - Bus Rd MP
P3 lee U S - S Bus Rd MP
P1 lee U S - S - C1
P3 escribe U I - M Bus RdX C3
P3 lee U I - M - C3
P3 escribe U I - M - C3
P2 lee U I S O Bus Rd C3
P2 escribe U I M I Bus RdX C2
P1 escribe U M I I Bus RdX C2
P3 lee U O I S Bus Rd C1
P1 lee U O I S - C1
P1 escribe U M I I - C1
Acciones Procesador 1
Acciones Procesador 3
Acciones Procesador 2
Protocolo de 4 estados MOSI
v
v
v
M
O
S
Protocolo de 4 estados MOSI
Fallos y aciertos de escritura y lectura
Fallo de lectura Fallo de escritura
Acierto de lectura Acierto de escritura
Caché que tiene el Fallo Otras cachés
I -> S
S (1 o más) -> S
M (solo 1) -> O
O (solo 1) -> O y
S (1 o más) -> S
Caché que tiene el Fallo Otras cachés
I -> M
S (1 o más) -> I
M (solo 1) -> I
O (solo 1) -> I y
S (1 o más) -> I
Caché que tiene el Acierto Otras cachés
S -> S
S (1 o más) -> S
O (solo 1) -> O y
S (1 o más) -> S
M -> M -
O -> O S (1 o más) -> S
Caché que tiene el Acierto Otras cachés
S -> M
S (1 o más) -> I
O (solo 1) -> I y
S (1 o más) -> I
M -> M -
O -> M S (1 o más) -> I
Multiprocesadores
Continuará…