En la mayoría de los sistemas computacionales existe un solo procesador real. Por lo tanto el núcleo debe asignar el procesador por turnos a los numerosos procesos que pueden estar activos. Hay distintas estrategias para asignar estos turnos, dependiendo del objetivo que se persiga.
Por ejemplo en un sistema de multiprogramación se busca maximizar el tiempo de uso del procesador, mientras que en un sistema de tiempo compartido se busca atender en forma expedita a muchos usuarios que trabajan interactivamente.
La asignación estratégica del procesador a los procesos es lo que se denomina scheduling de procesos. Es estratégica porque se intenta lograr algún objetivo particular como alguno de los que se mencionó más arriba y para ello se usan estrategias que pueden funcionar muy bien en determinados sistemas, pero muy mal en otros. La componente del núcleo que se encarga de esta labor se denomina scheduler del procesador.
Además de scheduling de procesos, también se realiza scheduling de los accesos a disco y para ello existe un scheduler asociado a cada disco. Este scheduler ordena estratégicamente los mútiples accesos a disco de varios procesos con el fin de minimizar el tiempo de acceso.
Para abreviar la notación, cuando se hable de ``el scheduler'' se subentenderá que se trata del scheduler del procesador.
Mientras un proceso se ejecuta puede pasar por distintos estados.
Estos estados se aprecian en la figura 
.
Figure: Estados de un procesos
Un proceso pasa de un estado a otro constantemente y varias veces por segundo. Por ejemplo cuando un proceso está corriendo el scheduler puede quitarle el procesador para entregárselo a otro proceso. En este caso el primer proceso queda listo para ejecutarse. Es decir en cualquier momento, el procesador puede entregarle nuevamente el procesador y quedar corriendo. De este estado el proceso puede leer un comando del terminal y por lo tando quedar en espera de que el usuario invoque alguna acción.
Desde luego el número exacto de estados depende del sistema. Por ejemplo en nSystem un proceso puede pasar por los siguientes estados:
El descriptor de proceso es la estructura de datos que utiliza el núcleo para mantener toda la información asociada a un proceso. Ella contiene:
El núcleo posee algún mecanismo para obtener el descriptor de proceso a partir del identificador del proceso, que es el que conocen los procesos.
La figura muestra el descriptor que usa nSystem. En
nSystem el identificador de tarea es un puntero a este descriptor.
Sin embargo, por razones de encapsulación este puntero se declara del
tipo void * en nSystem.h.
: El descriptor de proceso en nSystem
Durante la ejecución, un proceso pasa por numerosas colas a la espera
de algún evento. Esto se puede observar en la figura
.
Figure: Tránsito de un proceso por distintas colas
Mientras un proceso espera la obtención del procesador, este proceso permanece en una cola del scheduler del procesador. Esta cola puede estar organizada en una lista enlazada simple (cada descriptor de proceso tiene un puntero al próximo descriptor en la cola).
Además de la cola del scheduler del procesador existen la colas de scheduling de disco. El proceso permanece en estas colas cuando realiza E/S.
Cuando un proceso envía un mensaje síncrono a otro proceso que no está preparado para recibirlo, el primer proceso queda en una cola de recepción de mensajes en el descriptor del proceso receptor.
Por último el proceso puede quedar en una cola del reloj regresivo, a la espera de que transcurra un instante de tiempo.
Cambio de contexto (context switch, task switch o process switch) es la acción que efectúa el scheduler cuando transfiere el procesador de un proceso a otro. Para realizar el cambio de contexto, el scheduler debe realizar diversas labores que detallamos a continuación:
Cuando un proceso está corriendo, se utiliza el contador de programa, el puntero a la pila y los registros del procesador real. Al hacer el cambio de contexto, el nuevo proceso que toma el control del procesador usará esos mismos registros. Por ello es necesario resguardar los registros del proceso saliente en su descriptor de proceso. De igual forma, el descriptor del proceso entrante mantiene los valores que contenían los registros en el momento en que perdió el procesador. Estos valores deben ser restaurados en los registros reales para que el proceso funcione correctamente.
El espacio de direcciones del proceso saliente no es el mismo del espacio de direcciones del proceso entrante. En el capítulo sobre administración de memoria veremos como se logra el cambio de espacio de direcciones virtuales.
Usualmente, el núcleo se encarga de contabilizar el tiempo de procesador que utiliza cada proceso. Una variable en el descriptor de proceso indica el tiempo acumulado. En cada cambio de contexto el núcleo consulta un cronómetro que ofrece el hardware de cada computador. El scheduler suma el tiempo transcurrido desde el último cambio contexto al tiempo acumulado del proceso saliente.
Estas labores del scheduler consumen algo de tiempo de procesador y por lo tanto son sobrecosto puro. Cada cambio de contexto puede significar de 1 microsegundo a un milisegundo según el sistema operativo y la ayuda que ofrezca el hardware para realizar eficientemente el cambio de contexto.
Normalmente la componente más cara en tiempo de procesador es la del cambio de espacio de direcciones virtuales. Ahí radica el origen del nombre de procesos livianos. Como los procesos livianos comparten el mismo espacio de direcciones no es necesario cambiarlo durante un cambio de contexto. Por lo tanto pueden ser implementados más eficientemente. En este caso el peso de un proceso corresponde al tiempo de procesador que se consume al realizar un cambio de contexto. A mayor tiempo, mayor peso.
Es importante hacer notar que cuando se produce una interrupción, el hecho de invocar la rutina de atención de la interrupción no es un cambio de contexto. Esto se debe a que el código de la rutina de atención es parte del núcleo y por lo tanto no pertenece a ningún proceso en particular. Para que haya un cambio de contexto es necesario que se pase de la ejecución del código de un proceso a la ejecución del código de otro proceso.
Sin embargo muchos cambios de contexto ocurren durante una interrupción, por ejemplo cuando interrumpe el reloj regresivo. En otros casos, la interrupción no se traduce en un cambio de contexto. Por ejemplo si un disco interrumpe, esto puede significar que el proceso que esperaba esta interrupción se coloca en la cola del scheduler pero no se le transfiere de inmediato el procesador, se continúa ejecutando el proceso interrumpido.
Una ráfaga de CPU es una secuencia de instrucciones que puede ejecutar un proceso sin pasar a un estado de espera. Es decir el proceso no espera un acceso al disco, la recepción de un mensaje, el término de un proceso, etc.
La ejecución de un proceso consta de innumerables ráfagas de CPU.
Empíricamente se ha determinado que la mayoría de las ráfagas toman
pocas instrucciones. Esto se observa gráficamente en la figura
.
Figure: Histograma de la duración de la ráfagas de CPU. El primer
tramo indica el número de ráfagas que duran entre 0 y 1 milisegundo,
el segundo tramo indica las ráfagas de 1 a 2 milisegundos, etc.
El scheduler puede aprovecharse de este hecho empírico para disminuir el sobrecosto de los cambios de contexto. En efecto, al final de una ráfaga el cambio de contexto es inevitable porque el proceso en curso pasa a un modo de espera. Al contrario, los cambios de contexto en medio de una ráfaga son evitables y por lo tanto son sobrecosto puro. Un buen scheduler tratará de evitar los cambios de contexto en medio de una ráfaga corta y solo introducirá cambios de contexto en ráfagas prolongadas, que son las menos.
