Clase 090609 Ssoo

aunq podria utilizarse en cualkier otra situacion en dond se presente competencia. en el problema del productor y el consumidor existen dos procesos, uno de ellos inserta elemento en un bufer(productor)y el otro extraer elementos del buffer(consumidor). el buffer de memoria tiene un espacio limitado (100 elementos) y se debe controlar q el productor se detenga cuando ya no haya espacio para insertar elementos y q el consumidor se detenga cuando no haya elementos q extraer en lugar de utilizar una espera ocupada se utilizan la primitivas sleep y wake up. un proceso dormido equivale a decir q el proceso sta bloqueado y como tal no se desperdicia tiempo de cpu, como en el caso cuando esta activo generando una espera ocupada. 0

2

PRODUCTOR

CONSUMIDOR

100 BUFFER

El productor se va dormir x si mismo y lo despierta el consumidor. El consumidor se despierta x si mismo, detecta cuando no hay nada q consumir y lo despierta al productor. #INCLUDE “PROTOTYPE.H” #DEFINE N 100; INT COUNT = 0; VOID PRODUCER(VOID) { INT ITEM; WHILE(TRUE) { PRODUCE – ITEM; IF (COUNT==N) { SLEEP(); } ENTER(&ITEM); COUNT=COUNT+1;

IF (COUNT==1) { WAKE UP(CONSUMER); } } } VOID CONSUMER(VOID) { INT ITEM; WHILE(TRUE) { IF(COUNT==0) { SLEEP(); } REMOVE-ITEM(&ITEM); COUNT=COUNT-1; IF (COUNT==N-1) { WAKE UP(PRODUCER); } CONSUMER-ITEM(&ITEM); } } Tanto el productor como el consumidor se envían a dormir x si mismo. El productor se duerme cuando el buffer esta lleno y el consumidor se duerme cuando el buffer esta vacio. Dado que un proceso bloqueado(dormido) requiere para desbloquearse q ocurra algún evento externo, es decir, algún evento que no depende de si mismo, debe esperar a q otro proceso lo despierte. El productor detectara al consumidor cuando exista algún elemento q consumir y el consumir detectara(desbloqueara) al productor cuando haya alguna casilla vacía en el buffer; es por esto, q el procedimiento wake up requiere de un parámetro(nombre del procedimiento) . PLANIFICACION DE PROCESOS El planificador de proceso pued usar una o varias técnicas diferentes(algoritmo) cada técnica favorece uno o mas de los siguientes criterios: 1. Equidad. a. Dar a cada proceso el mismo tiempo de CPU. 2. Eficacia. a. Mantener la CPU ocupada el 100% del tiempo. 3. Eficiencia. a. Procesar la mayor cantidad de tareas en el menor tiempo(recursos) posible. 4. Tiempo de respuesta(en línea) a. Minimizar el tiempo que esperan los usuarios en línea x sus resultados.

5. Tiempo de retorno(por lotes) a. Minimizar el tiempo q esperan los usuarios por lotes x sus resultados.

TECNICAS DE PLANIFICACION: ROUND ROBIN Mediante esta técnica se determina un intervalo de tiempo de ejecución q se aplica para cada uno d los procesos. Este intervalo de tiempo se denomina QUANTUM, y es exactamente igual para todos los procesos. Cuando se trata de determinar que el tiempo q demoran los procesos en emitir sus resultados, uno de los factores q incide en la demora se denomina ALTERNANCIA ENTRE PROCESOS. Alternancia es el tiempo q se gasta en el traspaso de la CPU de un proceso a otro y este consumo de tiempo generalmente s asumido o descontado del Quantum del proceso q debe ceder la CPU. Ejemplo: EJERCICIO 1: Se tienen dos procesos a y b, a requiere 30 milisegundos del tiempo de ejecución y b requiere 15 milisegundos de tiempo de ejecución. El quantum se ha calculado en 10 milisegundos y se estima q el tiempo de alternancia es de 2 milisegundos. Si se aplica la técnica ROUND ROBIN, después de cuánto tiempo se recibirán los resultados de los procesos¡?¡?¡?¡ A= 30ms Proceso A: 8ms Proceso A: 8ms Proceso A: 14ms B = 15ms Alt: Alt: 2ms 2ms Q = 15ms Proceso B: 8ms Proceso B: 7ms Alt = 2ms Alt: Alt: 2ms 2ms EJERCICIO 2: Se tienen tres procesos A,B Y C. A requiere 60 milisegundos de tiempo de ejecución, B requiere el 75% de A, y C requiere la sumatoria de los dos procesos anteriores. Se estima un quantum de 0,015s y la alternancia es del 0,003s. Aplique ROUND ROBIN, para determinar cuando el usuario recibirá su resultado. 1s=1000ms A= Proceso Proceso Proceso Proceso A: 21ms 60ms A: 12ms A: 12ms A: 12ms B = Alt: 3ms 45ms Alt: 3ms Alt: 3ms Alt: 3ms C = Proceso Proceso Proceso Proceso B: 6ms 105m B: 12ms B: 12ms B: 12ms s Q = Alt: 3ms 15ms Alt: 3ms Alt: 3ms Alt: 3ms

Alt = Proceso 3ms C: 12ms

Proceso C: 27ms

Proceso C: 27ms

Alt: 3ms

Alt: 3ms

Alt: 3ms

PROCESO A Alt = 3ms PROCESO B Alt = 3ms PROCESO C Alt = 3ms -------------PROCESO A Alt = 3ms PROCESO B Alt = 3ms PROCESO C Alt = 3ms -------------PROCESO A Alt = 3ms PROCESO C

Proceso C: 66ms

= 12ms = 12ms = 12ms

= 12ms = 9ms -> finaliza B = 12ms

= 12ms -> finaliza A = 57ms

PROCESO A = 189ms PROCESO B = 159ms PROCESO C = 249ms EJERCICIO 3: Se tiene tres procesos A, B y C. A requiere 100 x 10 -3 s, B requiere 150 x 10 -3 y C la sumatoria de A y B. se estima un quantum de 0,04s y una alternancia de 5ms. Aplique ROUND ROBIN y exprese la respuesta en ms. Q= 40ms A= 100ms B = 150ms C = 250 ms ALT = 5ms --------PROCESO A = 35ms Alt = 5ms PROCESO B = 35ms Alt = 5ms PROCESO C = 35ms Alt = 5ms

-------------PROCESO A Alt = 5ms PROCESO B Alt = 5ms PROCESO C Alt = 5ms -------------PROCESO A Alt = 5ms PROCESO B Alt = 5ms PROCESO C Alt = 5ms -------------PROCESO B Alt = 5ms PROCESO C Alt = 5ms -------------PROCESO B Alt = 5ms PROCESO C

= 35ms = 35ms = 35ms

= 30ms -> finaliza A = 35ms = 35ms

= 35ms = 35ms

= 10ms ->FINALIZA B = 110ms ->FINALIZA C

PROCESO A = 270ms PROCESO B = 465ms PROCESO C = 570ms

COLAS MULTIPLES Este algoritmo sugiere el establecimiento de clases de prioridad (importancia) para los procesos q se están ejecutando, por ejemplo: si un proceso sta en la clase 1, le corresponderá ejecutarse en un quantum; una vez consumido este tiempo si el proceso aun no concluye, se moverá a la siguiente clase y la próxima vez q se ejecute le corresponderán dos quantum. Si aun no termina se moverá a la siguiente clase y le corresponderá cuatro quantum. Cada vez q un proceso cambie de clase el tiempo q le corresponde se duplica con respecto al anterior. Este método se desarrollo para mejorar el rendimiento y como es evidente se deja de lado el concepto de equidad, la mejora del rendimiento se da como producto de la disminución del número de alternancia. Ejercicio 1: A= 30ms B = 15ms Q = 10ms Alt = 2ms

Proceso A: 8ms Alt: 2ms Proceso B: 8ms Alt: 2ms

Proceso A: 18ms Alt: 2ms Proceso B: 7ms Alt: 2ms

Proceso A: 4ms

Proceso A: 12ms Alt: 3ms Proceso B: 12ms Alt: 3ms Proceso C: 12ms Alt: 3ms

Proceso A: 27ms Alt: 3ms Proceso B: 27ms Alt: 3ms Proceso C: 27ms Alt: 3ms

Proceso A: 21ms Alt: 3ms

Proceso A: 35ms Alt: 5ms Proceso B: 35ms Alt: 5ms Proceso C: 35ms

Proceso A: 65ms Alt: 5ms Proceso B: 75ms Alt: 5ms Proceso C: 75ms

Proceso B: 40ms Alt: 5ms

PROCESO A: 53ms PROCESO B: 47ms Ejercicio 2: A= 60ms B = 45ms C = 105ms Q = 15ms Alt = 3ms

Proceso B: 6ms Alt: 3ms Proceso C: 66ms

PROCESO A: 156ms PROCESO B: 165ms PROCESO C: 224ms Ejercicio 3: A= 100ms B = 150ms C = 250ms Q = 40ms Alt = 5ms

Proceso C: 140ms

Alt: 5ms

Alt: 5ms

PROCESO A: 185ms PROCESO B: 390ms PROCESO C: 535ms PLANIFICACION POR PRIORIDAD CICLICA Un esquema muy común es asignar grados de prioridad a cada uno de los procesos que se están ejecutando; Windows utiliza este esquema para su planificación. El proceso q tenga mayor prioridad se ejecutará primero, y el orden de ejecución subsiguiente, dependerá de los grados de prioridad de los demás procesos. Por ejemplo: si se tienen tres procesos, uno con prioridad 100, el segundo con prioridad 150 y el tercero con prioridad 75, el orden de ejecución sería: dos – uno – tres. La asignación de prioridad puede realizarse de dos formas, estática y dinámica. Con prioridad estática un proceso mantiene el mismo grado prioridad, durante toda su existencia. Con prioridad dinámica la prioridad de un proceso varía dependiendo del tiempo transcurrido. Este concepto se creó para evitar que un solo proceso acapare durante mucho tiempo la CPU. PROCESO A: 30ms Proceso C: 70ms PROCESO B: 50ms Alt: 5ms PROCESO C: 70ms Proceso B: 50ms Alt: 5ms Alt: 5ms Proceso A: 30ms PROCESO A: 160ms PROCESO B: 125ms PROCESO C: 70ms PRIMERO EL TRABAJO MAS CORTO Este esquema de planificación favorece el tiempo de retorno, es decir, está diseñado para los usuarios por lotes a diferencia de todos los métodos anteriores, están diseñados para usuarios en línea. Ejemplo: supóngase que existen cuatro procesos A, B, C y D, que requieren tiempos de ejecución de 50, 25, 20 y 35ms respectivamente. La alternancia es de 2ms. Determine en que tiempo se obtendrá resultados aplicando el método primero el trabajo más corto. PROCESO A: 50ms Proceso C: 20ms PROCESO B: 25ms Alt: 2ms PROCESO C: 20ms Proceso B: 25ms PROCESO D: 35ms Alt: 2ms

Alt: 2ms PROCESO PROCESO PROCESO PROCESO

Proceso D: 35ms Alt: 2ms Proceso A: 50ms A: 135ms B: 47ms C: 20ms D: 84ms

PLANIFICACION GARANTIZADA Mediante este esquema se puede establecer un compromiso o acuerdo al respecto del tiempo q la CPU, dedicará a el proceso. Se podría establecer cualquier compromiso, todo depend d las condiciones a las q se desea llegar. Por ejemplo: si existen n procesos, a cada proceso se le dedica 1/n del tiempo del CPU. Planificación de dos niveles RAM

El tamaño de la memoria virtual es proporcional al tamaño de disco duro

HD ALV UC PROCESADOR

MV

MEMORIA VIRTUAL DISCO DURO

Todos los algoritmos o técnicas anteriores, parten del hecho de que todos los procesos están dentro de la memoria principal, pero en la realidad es común que no existe suficiente memoria RAM para que todos los procesos estén ahí; en estos casos se utiliza la memoria virtual, que pretende simular una exposición de la memoria RAM. Aun con esta medida, es necesario recordar q el procesador únicamente puede tomar datos de la RAM y si se desea ejecutar o procesar algo que este en memoria virtual, necesariamente deberá subir a memoria RAM. Todo lo anterior supone que el planificador tome decisiones a niveles diferentes a lo que se denomina alto y bajo nivel. PLANIFICADOR DE ALTO NIVEL Decide cual de los procesos q esta en memoria RAM se ejecutará, cuando y durante q tiempo. PLANIFICADOR DE BAJO NIVEL Decide cual de los procesos q están en memoria virtual deberá subir a RAM y cual de los q esta en RAM, deberán bajar a memoria virtual. Todas las técnicas de planificación pueden combinarse en un sistema operativo

BLOQUEO SE DENOMINA BLOQUEO A LA SUSPENSION O DETENCION DE UN PROCESO, DEBIDO A Q TIENE Q ESPERAR A Q OCURRA ALGUN EVENTO EXTERNO. SI EL PROCESO NO OCURRE NUNCA PASA A DENOMINARSE DEAD LOCK. BLOQUEOS

DEAD LOCK R

PROCESO RECURSO

B

B R

Para que un proceso pueda utilizar un recurso debe seguir el siguiente esquema: 1.- el proceso debe solicitar el recurso. R

A

2.- el proceso debe utilizar el recurso. R

A

3.- EL PROCESO DEBE LIBERAR EL RECURSO. R

A

GRAFICAS DEL ESTADO DEL SISTEMA Mediante la nomenclatura de procesos y recursos, es posible elaborar una grafica que permita determinar el estado del sistema en un momento dado. Obviamente se requiere saber que procesos se están ejecutando, los recursos q le han sido asignados y tmb q recursos están solicitando. Una vez terminada la grafica será posible decir con certeza si el sistema esta bloqueado y q procesos están causando el problema, verificando las siguientes condiciones: 1.- espera circular: todo va en una R Misma dirección

A

A S

2.- condición de posesión y espera Un proceso q posee uno o varios recursos puede bloquearse y solicitar otros recursos. S

R

A

Q

3.- Condición de exclusión mutua Un recurso debe ser poseído por un proceso o debe estar libre. En ningún caso un mismo recurso podrá ser poseído por dos o más procesos.

A

R

B

EJERCICIO 1 PROCE SO

P OSE E

SOLICI TA

A

R

Q

B

Q

R

C

-

S

D

S

R, Q

SI HAY DEAD LOCK PROCESOS BLOQUEADOS: A, B

A

Q

R

S

C B

D

EJERCICIO 2 PROCE SO

P OSE E

SOLICI TA

A

Q

X, T

B

X

-

C

T

Q

D

-

Q, X

A

Q

T

C

SI HAY DEAD LOCK PROCESOS BLOQUEADOS: A, C

X

D

B

EJERCICIO 3 PROCE SO

P OSE E

SOLICI TA

A

X

Z

B

Y

X

C

Z

Y, X

D

-

Y

E

R

-

F

-

Y

G

-

R, Z

H

T

Z

NO HAY DEAD LOCK

X

A

Z

Y

C

H

E

G

LOS PROCESOS BLOQUEADOS SON A, B , C

B

D T

R

F

EJERCICIO 4 PROCE SO

P OSE E

SOLICI TA

A

Z

X

B

X

-

C

-

Z, X

D

Y

T

E

-

T, Y

F

T

R

G

-

R

H

R

Y, X

NO HAY DEAD LOCK

Z

A

X

B

F

C H T

E Y

R

G

LOS PROCESOS BLOQUEADOS SON A, B , C

D