1. 4.4. Planificación en POSIX
1.1. Establece una serie de políticas de planificación, aplicables a procesos e hilos, que deben implementar cualquier sistema operativo que ofrezca esta interfaz.
1.2. Cada proceso o hilo lleva asociada una política de planificación y una prioridad.
1.3. Estos parámetros se pueden modificar mediante los servicios correspondientes.
1.4. POSIX especifica que cada implementación debería ofrecer un rango de, al menos, 32 niveles de prioridad.
1.5. Las políticas de planifiación disponibles en POSIX son:
1.5.1. FIFO
1.5.1.1. Permite el desalojo.
1.5.2. RR
1.5.2.1. Dispone de una rodaja de tiempo para ejecución.
1.5.3. OTHER
1.5.3.1. El comportamiento dependerá de cada implementación
2. 4.5. Planificación en Linux
2.1. Este ha estado evolucionando e innovando permanentemente a lo largo de la historia y lo seguirá haciendo.
2.2. Los primeros planificadores de Linux usaron diseños mínimos, obviamente no enfocados en arquitecturas masivas con muchos procesadores.
2.3. A pesa de que Linux fue desarrollado como un experimento de sistema operativo de escritorio, lo encontramos ahora en servidores, teléfonos, pequeños dispositivos integrados, etc.
2.4. 4.5.1. Primeras Versiones
2.4.1. 4.5.1.1. Versión 0.96
2.4.1.1. Daba buena respuesta a las tareas con muchas operaciones de entrada y salida, pero sin ser injusto con las orientadas a la CPU.
2.4.1.2. Era un planificador basado en prioridades dinámicas que utilizaban rodajas de tiempo y desalojo, pero no utilizaba colas.
2.4.2. 4.5.1.2. Versión 1.2
2.4.2.1. A partir de la serie 1.2 se incorporó una cola circular para la administración de las tareas listas para ejecutar, dejando atrás al conjunto sin orden de las versiones anteriores.
2.4.2.2. Era eficiente para agregar y quitar procesos y se valía de un candado para proteger la estructura.
2.4.3. 4.5.1.3. Versión 2.0.33
2.4.3.1. En cada proceso se almacenaba su propia política de planificación dentro de su PCB, en su variable policy.
2.4.3.2. La política de planificación podía ser normal o de tiempo real.
2.4.3.2.1. Los procesos de tiempo real tenían una prioridad más alta que los otros procesos.
2.4.3.3. En la variable policy del PCB, la prioridad que el planificador le daba la proceso se guardaba.
2.4.3.4. El planificador se ejecutaba desde distintos lugares en el núcleo.
2.4.4. 4.5.1.4. Versión 2.2
2.4.4.1. La serie 2.2 de Linux Introdujo el concepto de clases de planificación.
2.4.4.2. Permitió políticas de planificación para tareas de tiempo real, tareas no desalojables y tareas que no eran de tiempo real.
2.4.4.3. También incluyó soporte para multiprocesamiento simétrico.
2.4.5. 4.5.1.5. Versión 2.4
2.4.5.1. Dividía el tiempo en períodos.
2.4.5.2. Dentro de un período las tareas podían ejecutar hasta agotar su rodaja de tiempo.
2.4.5.3. Si una tarea no utilizaba toda su rodaja de tiempo, este agregaba la mitad del tiempo restante no consumido al siguiente período.
2.4.6. 4.5.1.6. Versión 2.6.8.1
2.4.6.1. La base funcional sobre la cual se apoya el algoritmo la dan dos estructuras de datos:
2.4.6.1.1. Cola de ejecución
2.4.6.1.2. Arreglos de Prioridad
2.4.6.2. Su trabajo consistía en elegir para ejecutar a la tarea que esté primera en este arreglo de prioridad activo y a medida que se les van acabando sus rodajas de tiempo se las va moviendo al otro arreglo de prioridad.
2.4.6.3. Las primeras 100 posiciones en la lista e la cola de ejecución están reservadas para las tareas de tiempo real.
2.5. 4.5.2. Versiones Recientes
2.5.1. 4.5.2.1. Versión 2.6.21
2.5.1.1. En el caso de los núcleos de la serie 2.6, el usuario podía elegir entre 100, 250, 300 o 1000 Hz.
2.5.1.2. Las frecuencias más altas implican atender más rápidamente a las interrupciones y una mejor interactividad del sistema a expensas de una mayor sobrecarga en el sistema.
2.5.1.3. Este problema fue solucionado en el núcleo 2.6.21, implementando as así llamadas tics dinámicas.
2.5.1.4. Ofreció una resolución de nanosegundos en lugar de milisegundos.
2.5.2. 4.5.2.2. Versión 2.6.23
2.5.2.1. Utiliza el planificador CFS.
2.5.2.2. CFS modela a una CPU multitarea ideal y precisa sobre el hardware real.
2.5.2.3. No utiliza rodajas de tiempo en el sentido convencional, calcula rodajas de tiempo para una tarea determinada justo antes de que sea planificada para su ejecución.
3. 4.6. Planificación en Windows
3.1. Windows implementa un sistema de planificación con desalojo basado en prioridades.
3.1.1. El hilo ejecutable con la mayor prioridad es el elegido para ejecutar.
3.1.1.1. Cuando un hilo es seleccionado para ejecutar, lo hace durante una cantidad de tiempo que ya conocemos como quantum.
3.1.1.2. Ejecutará durante ese lapso de tiempo que le está permitido ejecutar hasta que a otro hilo en el mismo nivel de prioridad se le dé turno para ejecutar.
3.1.1.3. Los valores de quantum pueden variar de un sistema a otro y de un proceso a otro, por tales motivos:
3.1.1.3.1. Indicaciones en la configuración del sistema.
3.1.1.3.2. Procesos en primer o segundo plano.
3.1.1.3.3. Uso de objetos de trabajo para alterar el quantum.
3.2. 4.6.1. Niveles de Prioridad
3.2.1. Windows utiliza 32 niveles de prioridad:
3.2.1.1. 16 niveles de tiempo real (16 hasta 31)
3.2.1.2. 15 niveles variables (desde 1 hasta el 15)
3.2.1.3. Un nivel de sistema, el cero, reservado para el hilo de página cero.
3.2.2. Los niveles de prioridad de los hilos se asignan desde dos perspectivas diferentes:
3.2.2.1. Desde la API de Windows
3.2.2.2. Desde el núcleo de Windows
3.3. 4.6.2. Base de Datos del Activador
3.3.1. Su objeto es llevar el registro de todos los procesos, hilos y sus propiedades y para tomar decisiones de planificación, el núcleo usa este conjunto de estructuras de datos,
3.3.2. Leva el registro de qué hilos están esperando para ejecutar y qué procesadores están ejecutando qué hilos.
3.3.3. El procesador tiene asociadas un conjunto de 32 colas, una por nivel de prioridad y cada una contiene punteros a los hilos en ese nivel de prioridad y que están en estado listo para ejecutar.
4. 4.7. Práctica con Linux
4.1. POSIX proporciona planificación basada en prioridades.
4.1.1. Estas prioridades pueden ser modificadas dinámicamente mediante servicios específicos.
4.2. Linux implementa el esquema de planificación definido en las extensiones de tiempo real de POSIX. Existen tres formas de planificar un proceso.
4.2.1. SCHED_FIFO
4.2.1.1. Un proceso con este tipo de planificación tiene asociada una prioridad estática.
4.2.2. SCHED_RR
4.2.2.1. Igual que SCHED_FIFO, pero con una política de Round Robin para los procesos de igual prioridad.
4.2.3. SCHED_OTHER
4.2.3.1. Es la política de planificación clásica de UNIX: un Round Robin con mayor quantum a los procesos que menos CPU han consumido recientemente.
4.3. 4.7.1. Cambio de Contexto
4.3.1. Linux implementa el sistema de archivos proc, que es como una especie de mapa de estructuras de datos en memoria, expresados como si fueran archivos.
4.3.2. El comando top provee una vista de la actividad el procesador en tiempo real.
4.3.3. Muestra un listado de los procesos más intensivos en CPU en el sistema, y puede proveer una interfaz interactiva para la manipulación de procesos. Las columnas son:
4.3.3.1. PID
4.3.3.1.1. El identificador de proceso de cada tarea.
4.3.3.2. USER
4.3.3.2.1. El nombre de usuario del propietario del proceso.
4.3.3.3. PRI
4.3.3.3.1. La prioridad del proceso.
4.3.3.4. NI
4.3.3.4.1. El valor nice del proceso. Los valores negativos tienen la prioridad más alta.
4.3.3.5. SIZE
4.3.3.5.1. El tamaño del código del proceso más los datos más el espacio de pila, en kilobytes.
4.3.3.6. RSS
4.3.3.6.1. Cantidad total de memoria física usada por el proceso, en kilobytes
4.3.3.7. SHARE
4.3.3.7.1. La cantidad de memoria compartida usada por el proceso.
4.3.3.8. STAT
4.3.3.8.1. El estado del proceso
4.3.3.9. %CPU
4.3.3.9.1. La porción del proceso del tiempo de CPU desde la última actualización de la pantalla, expresada como porcentaje del tiempo total de CPU por procesador.
4.3.3.10. %MEM
4.3.3.10.1. La porción del proceso de la memoria física
4.3.3.11. COMMAND
4.3.3.11.1. El nombre del comando que generó el proceso.
5. VICTOR EMMANUEL PAZ CALDERÓN
6. 4.1. Conceptos
6.1. 4.1.1. Supuestos Subyacentes
6.1.1. Hay un grupo de procesos ejecutables que compiten por la CPU.
6.1.2. Los procesos son independientes y compiten por los recursos.
6.1.3. El trabajo del planificador es el de distribuir el preciado recurso de la CPU a los diferentes procesos de manera justa y de una manera que optimice algún criterio de rendimiento.
6.2. 4.1.2. Características
6.2.1. Los procesos e hilos no son todos iguales.
6.2.1.1. Pero es típico que ejecuten durante un cierto tiempo.
6.2.1.2. Luego realicen alguna operación de entrada o salida.
6.2.1.3. Después ejecutar por un cierto tiempo más, y así finalizar.
6.2.2. Los procesos se caracterizan por tener ráfagas de CPU intercaladas con ráfagas de entrada y salida.
6.2.3. De los procesos que realizan muchos cálculos y muy poca entrada o salida, con ráfagas largas de CPU, son orientados a la CPU.
6.2.4. Los que realizan muchas operaciones de entrada y salida con ráfagas cortas de CPU son orientados a la entrada y salida.
6.3. 4.1.3. Contexto
6.3.1. Cuando el núcleo decide ejecutar un proceso o hilo diferente, ordena al hardware almacenar el contexto del mismo.
6.3.2. Una vez llevada a cabo esta operación, se carga el contexto de otro proceso desde su propia área de almacenamiento.
6.3.3. Se limpian las cachés, se cambian el mapa de memoria virtual y se reanuda la ejecución del código de este proceso recién cargado.
6.3.4. El tiempo requerido para realizar un cambio de contexto está determinado por cuántos registros de la CPU necesitan ser preservados y restablecidos.
6.4. 4.1.4. Desalojo
6.4.1. Significa que el sistema operativo mueve un proceso del estado ejecutando al estado listo, sin que el proceso o hilo lo haya solicitado.
6.4.2. Sin desalojo, diremos que el sistema implementa la política de ejecutar hasta finalizar.
6.5. 4.1.5. Colas
6.5.1. Es una lista lineal en la que se hacen todas las inserciones y supresiones en un extremo.
6.5.2. El sistema operativo organiza colas para administrar las solicitudes a los recursos compartidos.
6.5.3. Hay colas para la planificación del uso de la CPU y también colas para el uso de dispositivos.
6.5.4. Son utilizadas para ordenas los requerimientos que varios procesos pueden tener sobre un dispositivo especifico
6.6. 4.1.6. Criterios
6.6.1. Maximizar el uso de la CPU, para que se mantenga ocupada el mayor tiempo posible.
6.6.2. Maximizar el rendimiento, es decir, el número de procesos que se ejecutan por unidad de tiempo.
6.6.3. Minimizar el rendimiento de retorno, que es el tiempo transcurrido desde que el proceso ingresa hasta que termina.
6.6.4. Minimizar el tiempo de espera, que es el tiempo que el proceso está en la cola de listos.
6.6.5. Minimizar el tiempo de respuesta.
6.7. 4.1.7. Notación de Landau
6.7.1. Una cola superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito y se utiliza la notación de Landau.
6.7.2. Esta notación nos da una idea acerca de cuánto tiempo usará un algoritmo.
7. 4.2. Tipos de Planificación
7.1. El planificador está muy relacionado con los distintos estados de un proceso.
7.2. Largo Plazo
7.2.1. Determina qué procesos o hilos se admiten en la cola de listos y cuáles pueden competir por los recursos.
7.3. Mediano Plazo
7.3.1. Se ocupa de la suspensión de procesos y es el que decide qué procesos en estado bloqueado dejan de estar en memoria principal para pasar a estar en memoria secundaria.
7.4. Corto Plazo
7.4.1. Decide de entre todos los procesos en estado listo, cuál es el que ejecutará a continuación y durante cuánto tiempo luego del que está ejecutando en ese momento.
8. 4.3. Algoritmos de Planificación
8.1. Estos algoritmos tratan sobre la decisión de elegir a cuál de los procesos que están en la cola de listos se le asignará la CPU.
8.2. 4.3.1. FCFS (First-Come, First-Serve)
8.2.1. Es el algoritmo primero en llegar, primero en ser atendido.
8.2.2. El tiempo promedio de espera puede ser largo.
8.2.3. 4.3.1.1. El Efecto Convoy
8.2.3.1. Es una situación indeseable que puede ocurrir cuando se mezcla un proceso orientado a la CPU con procesos orientados a la entrada y salida.
8.3. 4.3.2. SJF (Shortest-Job-First)
8.3.1. Es el algoritmo primero el trabajo más corto.
8.3.2. Es un algoritmo no expulsivo que intenta subsanar el efecto convoy eligiendo, de entre los procesos que están en la cola de listos, a aquel aue tenga el tiempo de procesamiento más corto.
8.3.3. En caso de empate, se puede usar el algoritmo FCFS, un algoritmo diseñado para los primeros ambientes de procesamiento por lotes.
8.3.4. 4.3.2.1. SRPT (Shortest-Remaining-Processing-Time)
8.3.4.1. Puede transformarse en expropiativo.
8.3.4.2. Es óptima para minimizar el tiempo medio de respuesta.
8.3.4.3. Es el primero el que tenga el menor tiempo restante.
8.4. 4.3.3. Por Prioridad
8.4.1. Se le asocia un valor a cada proceso que representa su prioridad y se le asigna la CPU al proceso de la cola de listos que tenga la mayor.
8.4.2. Los valores asociados a la prioridad pueden estar en un rango fijo, de 0 a n, según cada sistema.
8.4.2.1. También lo determina cada sistema si el número más bajo es lamás alta o la más baja prioridad.
8.4.3. La prioridad puede ser:
8.4.3.1. Fija
8.4.3.1.1. Ese valor no varía en el ciclo de vida del proceso.
8.4.3.2. Variable
8.4.3.2.1. Ese valor puede cambiar dinámicamente de manera tal ue haya factores.
8.5. 4.3.4. RR (Round-Robin)
8.5.1. En los sistemas de tiempo compartido se utiliza mucho esta planificación que le asigna a cada proceso de la cola de .listos un intervalo de tiempo CPU llamado rodaja de tiempo.
8.5.2. Los procesos van tomando la CPU por turnos y por el tiempo que indique este.
8.5.3. Al cumplirse el tiempo, el proceso es desalojado mediante una interrupción y retornado a la cola de listos.
8.6. 4.3.5. Colas Multiniveles
8.6.1. 4.3.5.1. MLQ
8.6.1.1. Intenta diferenciar entre distintos tipos de trabajo.
8.6.1.2. Divide cola de procesos listos en varias colas. Una por cada tipo de trabajo.
8.6.1.3. El criterio de asignación está en función de alguna propiedad del proceso.
8.6.2. 4.3.5.2. MLFQ
8.6.2.1. Presenta baja carga de planificación pero es poco flexible, por que los procesos quedan asignados de forma permanente a una cola.
8.6.2.2. Se implementaron originalmente en el sistema CTSS.
8.6.2.3. Su objetivo era dar buena respuesta al usuario interactivo a costa del usuario no interactivo que realizaba extensos cálculos intensivos.
8.6.2.4. Está definido por los parámetros:
8.6.2.4.1. El número de colas
8.6.2.4.2. El algoritmo de planificación de cada cola.
8.6.2.4.3. El algoritmo de planificación entre las distintas colas.
8.6.2.4.4. El método usado para determinar cuándo pasar un proceso a una cola de prioridad más baja.
8.6.2.4.5. El método usado para determinar cuándo pasar un procesos a una cola de prioridad más alta.
8.6.2.4.6. El método usado para determinar en qué cola introducirá un proceso cuando haya que darle servicio.