YAMA

Algoritmos de Planificación

Planificación

P1

P2

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Planificación

P1

P2

CPU

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Preplanificación

Nodo1

0

1

3

0

1

3

Nodo2

2

4

2

4

0 1 2 3 4 5 6

Nodo3

5

6

5

6

Transformación

Reducción Local

Reducción Global

WClock - Intuición

Carga = X

Carga = Y

Carga = Z

Turnos

nClock - Elementos Fundamentales

  • Clock (puntero)
  • Reglas (mueve el clock y actualiza la disponibilidad)
  • Función de disponibilidad:

A(w) = Abase + PWL(w)

PWL(w) =

0 si Clock

WLmax - WL(w) si W-Clock

nClock - Inicialización y Funcionamiento

A = 6

B = 0 2 3 5 6

A = 10

B = 0 1 3 4 6

A = 3

B = 1 2 4 5

nClock - Casos Particulares

A = 1

B = 0 2 3 5 6

A = 0

B = 0 1 3 4 6

A = 1

B = 1 2 4 5

Bloque = 1

nClock - Casos Particulares

A = 0

B = 0 2 3 5 6

A = 0

B = 0 1 3 4 6

A = 0

B = 1 2 4 5

Bloque = 1

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 0 1 1

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 2

Nodo2

A = 1

Nodo3

A = 1

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 1 1 1

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 1

0

Nodo2

A = 1

Nodo3

A = 1

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 1 2 1

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 1

0

Nodo2

A = 0

1

Nodo3

A = 1

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 1 2 2

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 1

0

Nodo2

A = 0

1

Nodo3

A = 0

2

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 1 2 2

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 2

0

Nodo2

A = 1

1

Nodo3

A = 1

2

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 1 3 2

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 2

0

Nodo2

A = 0

1

3

Nodo3

A = 1

2

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 2 3 2

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 1

0

4

Nodo2

A = 1

1

3

Nodo3

A = 1

2

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 3 3 2

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

A = 0

0

4

5

Nodo2

A = 1

1

3

Nodo3

A = 1

2

Transformación

Reducción Local

Reducción Global

W-Clock - Ejemplo

Base = 1

Bloques Nodo 1

Bloques Nodo 2

Bloques Nodo 3

WL= 3 3 5

0 4 5

1 2 3 5

0 1 2 3 4

Nodo1

0

4

5

0

4

5

Nodo2

1

3

1

3

Nodo3

2

2

0 1 2 3 4 5

Transformación

Reducción Local

Reducción Global

Carga Final del sistema

WL(w) = Qt(w) + (1 / 2) * Qrg(w) * Qt(Job)

Qt(x) = Cantidad de transformaciones de x

Qrg(x) = Cantidad de reducciones globales de x

¿Preguntas?

Yama - Algoritmos de Planificación - Google Slides