Exclusión mutua:

Acceso de dos procesos a datos modificables de manera concurrente.

Sección crítica:

Cuando un proceso accede a datos compartidos modificables. (Se puede

considerar la reserva de un recurso muy importante para el sistema)

Sección residual:

Todo fragmento de proceso que no necesite acceso exclusivo.

Primitivas de exclusión mutua:

El código correspondiente a la entrada y salida de la sección

crítica debe garantizar el acceso exclusivo a la misma, por lo que se implementa mediante

instrucciones conocidas como primitivas de exclusión mutua. Son operaciones que actúan

evitando que haya más de un proceso ejecutando en su sección crítica.

4 requisitos que debe de cumplir cualquier realización de las primitivas de exclusión

mútua para que funcionen en cualquier máquina (Edsger Dijkstra):

-Debe ser un código software que en ningún momento se vea limitado por el

hardware. Cada instrucción se ejecuta de forma indivisible. Si 2 operaciones se realizan

a la vez el resultado es no-determinista. Si 2 procesadores intentan acceder a una

misma posición de memoria el hardware secuencia los accesos en un orden aleatorio.

-No hacer ninguna suposición acerca de las velocidades relativas de ejecución de los

procesos, salvo que no son cero.

-Un proceso que no está en su sección crítica, no debe impedir que otro proceso

progrese a la suya.

-Equidad: No se debe postergar indefinidamente la entrada de un proceso a su sección

crítica.

Exclusión mutua para 2 procesos

Espera activa:

Si un proceso quiere entrar en la sección crítica y otro proceso la ocupa

entonces pasará a estar en espera activa (consultando a ver si el otro proceso ha

terminado para poder entrar el)

Algoritmo de Dekker:

Es un sistema de espera de turnos por el que los procesos se encolan de

manera que hasta que el que se encuentra en la sección crítica no salga de la misma el

siguiente no podrá pasar. Cuando ambos intentan entrar a la vez se mide por

prioridades. Esto puede llevar a un proceso a la inanición en caso de que otro proceso

intente solicitar acceso a la sección crítica y a este nunca se le asigne cpu por que no

tiene suficiente prioridad. También puede llegar a suceder el término conocido como

dead lock o interbloqueo, o abrazo mortal o espera circular. Viene siendo cuando 2

procesos consultan a la vez el estado del otro y se mantienen en espera uno del otro

sin llegar a finalizar nunca.

Algoritmo de Peterson:

No se da el interbloqueo. Establece una comunicación entre procesos

mediante un contador. En el momento en el que un proceso quiere acceder a la

sección crítica la variable Quiereentrar pasa a ser verdadera y la variable turnoproceso

se actualiza tomando el valor de la variable del otro proceso con el fin de saber la

prioridad, al entrar en espera activa en el momento en el que el otro proceso termina

el valor de turno proceso cambia y le da paso a este. (no soluciona la inanición)

Algoritmo de Lamport:

A cada proceso que llega se le asigna una posición (un nº que define el

orden de entrada). Si 2 procesos llegan a la vez reciben el mismo nº pero se inicia el

proceso con orden de llegada más bajo.

Instrucción TLS (Test&Set Lock):

Lee en un registro el contenido de una dirección de memoria

y carga en ésta un valor distinto de cero.

Semáforos:

Se utilizan para sincronizar procesos. Mantienen a la espera el inicio de un proceso

hasta que sus antecesores.

Planificación de procesos:

Justicia: El algoritmo debe de dar una porción de CPU justa a todos los procesos. Nadie

debe de acaparar CPU o quedar sin servicio.

Productividad: Cantidad de trabajo desarrollada por unidad de tiempo. El objetivo es

maximizar la productividad. Este objetivo es igual a la optimización de la utilización del

procesador (throughput)

Tiempo de respuesta aceptable: En sistemas de tiempo compartido es muy importante

que todos los usuarios tengan un tiempo de respuesta aceptable.

Predecible: El algoritmo debe de obtener resultados de planificación parecidos sea cual

sea la carga del sistema.

Costo extra: El tiempo utilizado en la planificación debe de ser el mínimo posible, ya

que es tiempo inútil para el sistema.

Prioridades: En algunas ocasiones se puede establecer un sistema de prioridades en

función de la importancia de dar servicio a cada trabajo para el sistema completo.

Ocupación de los recursos: Se debe de maximizar el uso de los recursos del sistema.

Aplazamiento indefinido: Se debe de evitar la inanición de los procesos.

Degradación aceptable: El algoritmo debe de degradar su eficacia de forma suave a

medida que sube la carga del sistema siempre sin que ocurra una caída global.

Niveles de planificación:

Planificación a alto nivel: También se le denomina planificación a largo plazo o

planificación de tareas. En este nivel se decide qué usuarios o tareas van a entrar a

competir por la CPU. Es decir, en función de la carga del sistema, se admitirán procesos

nuevos o se eliminarán algunos que ya existen. Por ello se suele denominar también

planificación de admisión.

Planificación a nivel medio: También denomina planificación a medio plazo. En este

nivel se decide sobre los procesos que están compitiendo por la CPU. Cuando la carga

del sistema crece, algunos procesos son suspendidos temporalmente; cuando se

estabiliza, se reanudan los procesos que fueron suspendidos.

Planificación a bajo nivel: También se le denomina planificación a corto plazo o

planificación de procesos. En este punto, el planificador trabaja con los procesos en

espera de ser servidos. Es el que decide el siguiente proceso a ejecutar en la CPU y

durante cuánto tiempo. A este nivel el planificador suele recibir el nombre de

despachador o dispatcher.

Criterios de planificación:

Utilización de la CPU.

Productividad: Se suele definir como el número de trabajos que se completan por

unidad de tiempo. Es un criterio que depende mucho del sistema.

Tiempo de retorno: Es el criterio más importante desde el punto de vista del proceso.

Es el tiempo transcurrido desde que el proceso comienza su ejecución hasta que se

sirve. Incluye el tiempo de ejecución efectiva, el tiempo de espera, tiempos de E/S…

(cuanto más bajo mejor)

Tiempo de espera: El problema del tiempo de retorno es que incluye muchos factores

que no dependen del algoritmo de planificación. Por ello definimos el tiempo de

espera, que incluye únicamente el tiempo que el proceso está esperando a ser servido.

El objetivo es minimizar el tiempo medio de espera. En sistemas en tiempo compartido

es también muy importante mantener dentro de límites razonables la varianza del

tiempo de espera. (Espera la operación de despacho: tiempo de retorno-tiempo de

ejecución)

Tiempo de respuesta: En un sistema interactivo es muy importante mantener un

diálogo constante con el usuario. Por ello, es un criterio a tener en cuenta el tiempo

que tarda el proceso en dar los primeros resultados, aunque luego el proceso tarde

más en completarse. Es importante en los sistemas interactivos.

Algoritmos de planificación

(Instrucciones para resolver algo)

Algoritmo de planificación apropiativo: Existe la posibilidad d que el planificador

desplace de la CPU a un proceso durante una ráfaga de la CPU. El coste de este tipo de

algoritmos es mayor porque incrementa el número de cambios de contexto. Es

necesario también mantener más procesos en memoria.

Algoritmos de planificación no apropiativos: Cuando un proceso que ejecuta el

algoritmo no es desplazado hasta que completa su ráfaga de CPU. Este tipo de

algoritmos pueden dar lugar a que un proceso intensivo en CPU acapare el procesador

en detrimento de los demás procesos del sistema.

Planificación FCFS

(El primero en venir, el primero en ser despachado) No apropiativo

-Tiene un tiempo medio de espera muy alto.

-Efecto convoy: Si hay un proceso que tarda mucho en realizar su ejecución y es el

primero que ha llegado todos los demás procesos (cuya ejecución es menor)

experimentan este efecto puesto que se tienen que mantener a la espera.

Planificación SJF

(Primero el trabajo más corto) No apropiativo

Se le asignan prioridad a los trabajos que se ejecuten con mayor rapidez. Si se ejecutan

igual de rápido se soluciona de forma arbitraria. Este sistema no evita la inanición

porque si aparece un proceso que tarda mucho en ejecutarse no empezará hasta que

los otros procesos terminen y si llegan a la cola procesos más pequeños pasarán por

delante de él.

Existe una versión apropiativa de este algoritmo, el SRTF. Si se está ejecutando un proceso de

mayor tamaño que el que acaba de llegar a la cola, a éste se le quita la CPU y se le asigna al

que acaba de llegar. (Tampoco evita la inanición)

Planificación por prioridades

Se le asigna una prioridad a cada proceso. Si los procesos tienen la misma prioridad se utiliza el

algoritmo FCFS.

Planificación circular

Está diseñado especialmente para sistemas de tiempo compartido. Se define un intervalo de

tiempo («cuanto»), cuya duración varía según el sistema. La cola de procesos es circular. El

planificador la recorre asignando un «cuanto» de tiempo a cada proceso. La organización de la

cola es FIFO. Se implanta mediante un temporizado que genera una interrupción cuando se

agota el «cuanto» de tiempo. Este algoritmo requiere un tiempo de espera relativamente

grande. Sin embargo, garantiza un reparto de la CPU entre todos los usuarios y arroja tiempos

de respuesta buenos.

Planificación multinivel

Existen varias colas. Cada proceso del sistema se sitúa en una cola según sus características.

Cada cola utiliza un algoritmo diferente según las características de los procesos de la misma.

Procesos del sistema (FCFS no apropiativo)

Procesos interactivos (RR)

Procesos interactivos de edición (RR)

Procesos en modo desatendido (FSFS)

Procesos de baja prioridad (FCFS)

Planificación en sistemas multriprocesador

Sistemas heterogéneos: Cada procesador es diferente. En este caso cada proceso que llega al

sistema ha de ejecutarse en un procesador específico, lo que facilita mucho el trabajo de

planificación. Existe una cola para cada procesador, que se gestiona de forma independiente

con cualquiera de los algoritmos ya vistos.

Sistema homogéneo: En este caso existe la posibilidad de compartir la carga de trabajos. Todos

los procesadores toman tareas de una única cola. Es necesaria una programación de la

planificación muy cuidadosa para evitar que un proceso pueda ser seleccionado por dos

procesadores, o que se pierdan trabajos. También se puede encargar un procesador de

planificar el trabajo de los restantes en una estructura maestro-esclavo, en lo que se conoce

como multiprocesamiento asimétrico. Una segunda opción es que cada procesador tenga una

cola independiente, pero esto resulta poco eficiente, puede haber trabajos en espera y

procesadores inactivos.

Modelo de colas: Técnica estadística que intenta encontrar una solución analítica a los

criterios como el tiempo de proceso. Es de una gran complejidad en casos reales,

donde además muchas de las suposiciones pueden estar muy alejadas de la realidad.

Modelo determinista: Se obtienen los valores de tiempos correspondientes a una

carga específica del sistema. Es muy sencillo, pero sólo se puede considerar como una

idea de la tendencia del algoritmo. Puede ser útil, si se evalúan varias cargas de trabajo

significativas.

Simulación: Se reproduce mediante un programa de simulación los principales

elementos del sistema de computación. Se crea una variable que representa el reloj

del sistema. Los datos se generan siguiendo el rastreo, estas se crean registrando las

secuencias de trabajos en un sistema real. Los resultados suelen ser bastante

significativos.

Implantación: La forma más exacta consiste en programar el algoritmo y utilizarlo en

un sistema real. El problema más complicado es el costo de la implantación, y los

problemas derivados de modificar el algoritmo de planificación en un entorno real de

trabajo.