Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Algoritmo para averiguar interbloqueo

2011-04-28T22:23:03Z

Dorellana: /* Algoritmo en Java */

== Algoritmo en C# ==

<source lang="csharp">
int nRecursos;
int nProcesos;
List<List<int>> asignados = new List<List<int>>();
List<List<int>> maximos = new List<List<int>>();
List<int> disponibles = new List<int>();

Random r = new Random();

//Generamos las matrices aleatoriamente
for (int j1 = 0; j1 < nRecursos;j1++)
{
disponibles.Add(r.Next(0, nRecursos));
}
for (int i = 0; i < nProcesos; i++)
{
asignados.Add(new List<int>());
maximos.Add(new List<int>());
for (int j = 0; j < nRecursos; j++)
{
asignados[i].Add(r.Next(0, nRecursos));
maximos[i].Add(r.Next(0, nRecursos));
}
}

bool aux = true;
for (int proc = 0; proc < nProcesos; proc++)
{
aux = true;
for (int recur = 0; recur < nRecursos; recur++)
{
// comprobamos que haya recursos suficientes
aux = (maximos[proc][recur] - asignados[proc][recur] - disponibles[recur]) <= 0;
if (!aux)
{
break;
}
}
if (aux)
{
añadirYeliminar(ref disponibles, ref asignados, proc);
maximos.RemoveAt(proc);
nProcesos--;
proc = -1;
if (nProcesos == 0)
{
Console.WriteLine("Es estado seguro");
Console.ReadLine();
return;
}
}
}
Console.WriteLine("Es interbloqueo");
Console.ReadLine();

}

private static void añadirYeliminar(ref List<int> disponibles, ref List<List<int>> asignados, int proc)
{
for (int k = 0; k < asignados[proc].Count; k++)
{
disponibles[k] += asignados[proc][k];
}
asignados.RemoveAt(proc);
}
</source>

Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente

== Algoritmo en Python ==

<source lang="python">
def comprueba_configuracion(asignados, maximos, disponibles):
finalizados = []
i = 0
while(i < len(asignados)):
if not i in finalizados and puede_progresar(asignados[i], disponibles, maximos[i]):
print('Finaliza P%s\nDisponibles: %s' % (i,disponibles))
libera_recursos(asignados[i], disponibles)
finalizados.append(i) # Marca el proceso Pi como finalizado
i = 0
else:
i += 1

if(len(asignados) == len(finalizados)): # Si todos los procesos finalizan
print('\nEstado seguro para la configuracion de procesos-recursos dada')
else:
print('\nSe produce un interbloqueo')

# Incrementamos la lista de disponibles con los que tenia asignados
def libera_recursos(asignados, disponibles):
for i in range(len(disponibles)):
disponibles[i] += asignados[i]

# Devuelve True si el nº de elementos asignados mas los disponibles son mayores o iguales a los requeridos para continuar
def puede_progresar(asignados, disponibles, maximos):
resultado = True
for i in range(len(maximos)):
if(asignados[i] + disponibles[i] < maximos[i]):
resultado = False
break
return resultado

asignados = [
[1,0,2,1,1],
[2,0,1,1,0],
[1,1,0,1,0],
[1,1,1,1,0]
]
maximos = [
[1,2,2,1,2],
[2,2,2,1,0],
[2,1,3,1,0],
[1,1,2,2,1]
]
disponibles = [0,0,2,1,1]
</source>

Para este ejemplo (visto en clase) la salida sería:

<source lang="python">
>>> comprueba_configuracion(asignados, maximos, disponibles)
Finaliza P3
Disponibles: [0, 0, 2, 1, 1]
Finaliza P2
Disponibles: [1, 1, 3, 2, 1]
Finaliza P0
Disponibles: [2, 2, 3, 3, 1]
Finaliza P1
Disponibles: [3, 2, 5, 4, 2]

Estado seguro para la configuracion de procesos-recursos dada
</source>

== Algoritmo en Java ==
<source lang="java">
public class Comprobaciones {

public static List<Proceso> devuelveLista(List<Proceso> asignados, List<Proceso> necesarios, Disponibles recursos){
List<Proceso> terminados = new ArrayList<Proceso>();
for(int i = 0; i < necesarios.size(); i++){
if(!(terminados.contains(asignados.get(i))) && ejecuta(asignados.get(i), necesarios.get(i), recursos)){
terminados.add(asignados.get(i));
System.out.println("Proceso " + asignados.get(i).getNombre() + " terminado");
for(int j = 0; j < recursos.getDisponibles().size(); j++){
recursos.setDisponible(recursos.getDisponibles().get(j) + asignados.get(i).getRecursosNecesarios().get(j), j);
}
System.out.println("Recursos disponibles: " + recursos.getDisponibles());
i = -1;
}

}
if(terminados.size() == asignados.size()){
System.out.println("Todos los procesos han sido ejecutados sin problemas.");
}
else{
System.out.println("Hay un interbloqueo, no se pueden seguir ejecutando procesos...");
}
return terminados;
}

public static Boolean ejecuta(Proceso asignados, Proceso necesarios, Disponibles disponibles){
// Devuelve True si tiene recursos suficientes...
Boolean ej = true;
for(int i = 0; i < necesarios.getRecursosNecesarios().size(); i++){
if((asignados.getRecursosNecesarios().get(i) + disponibles.getDisponibles().get(i)) < necesarios.getRecursosNecesarios().get(i)){
ej = false;
break;
}
}
return ej;
}

}
</source>
<source lang="java">
public static void main(String[] args) {

List<Proceso> asignados = creaAsignados();
List<Proceso> necesarios = creaNecesarios();
Disponibles disponibles = creaDisponibles();
Comprobaciones.devuelveLista(asignados, necesarios, disponibles);
}
</source>
Resultado:
<pre>
Proceso P4 terminado
Recursos disponibles: [1, 1, 3, 2, 1]
Proceso P3 terminado
Recursos disponibles: [2, 2, 3, 3, 1]
Proceso P1 terminado
Recursos disponibles: [3, 2, 5, 4, 2]
Proceso P2 terminado
Recursos disponibles: [5, 2, 6, 5, 2]
Todos los procesos han sido ejecutados sin problemas.
</pre>
Nota: Las clases lo único que contienen son listas de enteros, y los procesos contienen además los nombres de los mismos.

Algoritmo para averiguar interbloqueo

2011-04-28T15:35:11Z

Dorellana: Añadida implementación en Java

== Algoritmo en C# ==

<source lang="csharp">
int nRecursos;
int nProcesos;
List<List<int>> asignados = new List<List<int>>();
List<List<int>> maximos = new List<List<int>>();
List<int> disponibles = new List<int>();

Random r = new Random();

//Generamos las matrices aleatoriamente
for (int j1 = 0; j1 < nRecursos;j1++)
{
disponibles.Add(r.Next(0, nRecursos));
}
for (int i = 0; i < nProcesos; i++)
{
asignados.Add(new List<int>());
maximos.Add(new List<int>());
for (int j = 0; j < nRecursos; j++)
{
asignados[i].Add(r.Next(0, nRecursos));
maximos[i].Add(r.Next(0, nRecursos));
}
}

bool aux = true;
for (int proc = 0; proc < nProcesos; proc++)
{
aux = true;
for (int recur = 0; recur < nRecursos; recur++)
{
// comprobamos que haya recursos suficientes
aux = (maximos[proc][recur] - asignados[proc][recur] - disponibles[recur]) <= 0;
if (!aux)
{
break;
}
}
if (aux)
{
añadirYeliminar(ref disponibles, ref asignados, proc);
maximos.RemoveAt(proc);
nProcesos--;
proc = -1;
if (nProcesos == 0)
{
Console.WriteLine("Es estado seguro");
Console.ReadLine();
return;
}
}
}
Console.WriteLine("Es interbloqueo");
Console.ReadLine();

}

private static void añadirYeliminar(ref List<int> disponibles, ref List<List<int>> asignados, int proc)
{
for (int k = 0; k < asignados[proc].Count; k++)
{
disponibles[k] += asignados[proc][k];
}
asignados.RemoveAt(proc);
}
</source>

Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente

== Algoritmo en Python ==

<source lang="python">
def comprueba_configuracion(asignados, maximos, disponibles):
finalizados = []
i = 0
while(i < len(asignados)):
if not i in finalizados and puede_progresar(asignados[i], disponibles, maximos[i]):
print('Finaliza P%s\nDisponibles: %s' % (i,disponibles))
libera_recursos(asignados[i], disponibles)
finalizados.append(i) # Marca el proceso Pi como finalizado
i = 0
else:
i += 1

if(len(asignados) == len(finalizados)): # Si todos los procesos finalizan
print('\nEstado seguro para la configuracion de procesos-recursos dada')
else:
print('\nSe produce un interbloqueo')

# Incrementamos la lista de disponibles con los que tenia asignados
def libera_recursos(asignados, disponibles):
for i in range(len(disponibles)):
disponibles[i] += asignados[i]

# Devuelve True si el nº de elementos asignados mas los disponibles son mayores o iguales a los requeridos para continuar
def puede_progresar(asignados, disponibles, maximos):
resultado = True
for i in range(len(maximos)):
if(asignados[i] + disponibles[i] < maximos[i]):
resultado = False
break
return resultado

asignados = [
[1,0,2,1,1],
[2,0,1,1,0],
[1,1,0,1,0],
[1,1,1,1,0]
]
maximos = [
[1,2,2,1,2],
[2,2,2,1,0],
[2,1,3,1,0],
[1,1,2,2,1]
]
disponibles = [0,0,2,1,1]
</source>

Para este ejemplo (visto en clase) la salida sería:

<source lang="python">
>>> comprueba_configuracion(asignados, maximos, disponibles)
Finaliza P3
Disponibles: [0, 0, 2, 1, 1]
Finaliza P2
Disponibles: [1, 1, 3, 2, 1]
Finaliza P0
Disponibles: [2, 2, 3, 3, 1]
Finaliza P1
Disponibles: [3, 2, 5, 4, 2]

Estado seguro para la configuracion de procesos-recursos dada
</source>

== Algoritmo en Java ==
<source lang="java">
public class Comprobaciones {

public static List<Proceso> devuelveLista(List<Proceso> asignados, List<Proceso> necesarios, Disponibles recursos){
List<Proceso> terminados = new ArrayList<Proceso>();
for(int i = 0; i < necesarios.size(); i++){
if(verificarInterbloqueo(asignados, necesarios, recursos)){
System.out.println("Hay un interbloqueo, no se pueden seguir ejecutando procesos...");
break;
}
else{
if(!(terminados.contains(asignados.get(i))) && ejecuta(asignados.get(i), necesarios.get(i), recursos)){
terminados.add(asignados.get(i));
System.out.println("Proceso " + asignados.get(i).getNombre() + " terminado");
for(int j = 0; j < recursos.getDisponibles().size(); j++){
recursos.setDisponible(recursos.getDisponibles().get(j) + asignados.get(i).getRecursosNecesarios().get(j), j);
}
System.out.println("Recursos disponibles: " + recursos.getDisponibles());
i = -1;
}
}
}
if(terminados.size() == asignados.size()){
System.out.println("Todos los procesos han sido ejecutados sin problemas.");
}
return terminados;
}
public static Boolean verificarInterbloqueo(List<Proceso> asignados, List<Proceso> necesarios, Disponibles recursos){
// Devuelve True si hay interbloqueo...
Boolean ib = true;
for(int i = 0; i < necesarios.size(); i++){
if(ejecuta(asignados.get(i), necesarios.get(i), recursos)){
ib = false;
break;
}
}
return ib;
}

public static Boolean ejecuta(Proceso asignados, Proceso necesarios, Disponibles disponibles){
// Devuelve True si tiene recursos suficientes...
Boolean ej = true;
for(int i = 0; i < necesarios.getRecursosNecesarios().size(); i++){
if((asignados.getRecursosNecesarios().get(i) + disponibles.getDisponibles().get(i)) < necesarios.getRecursosNecesarios().get(i)){
ej = false;
break;
}
}
return ej;
}

}
</source>
<source lang="java">
public static void main(String[] args) {

List<Proceso> asignados = creaAsignados();
List<Proceso> necesarios = creaNecesarios();
Disponibles disponibles = creaDisponibles();
Comprobaciones.devuelveLista(asignados, necesarios, disponibles);
}
</source>
Resultado:
<pre>
Proceso P4 terminado
Recursos disponibles: [1, 1, 3, 2, 1]
Proceso P3 terminado
Recursos disponibles: [2, 2, 3, 3, 1]
Proceso P1 terminado
Recursos disponibles: [3, 2, 5, 4, 2]
Proceso P2 terminado
Recursos disponibles: [5, 2, 6, 5, 2]
Todos los procesos han sido ejecutados sin problemas.
</pre>
Nota: Las clases lo único que contienen son listas de enteros, y los procesos contienen además los nombres de los mismos.

Bloque de control de procesos

2011-03-23T08:26:59Z

Dorellana:

Para llevar a cabo la gestión de un proceso, es necesario que el sistema operativo guarde cierta información necesaria. A ésta estructura se le conoce como '''el bloque de control del proceso o PCB (Process Control Block)'''.

El bloque de control de procesos difiere mucho de un sistema a otros pero existen contenidos comunes:

* Identificador del proceso: Identificar de forma unívoca al proceso en el sistema, generalmente se emplea un entero sin signo que se denomina PID (Process IDentifier).

* Estado del proceso para el planificador de procesos (preparado, activo o bloqueado).

* Contexto de la ejecución: valor de los registros del procesador, bits de estados, etc.

* Aspectos relacionados con la administración de memoria, tales como el espacio de direcciones y la cantidad de memoria asignada a un proceso.

* Aspectos relacionados con la administración de ficheros, tales como los ficheros con los que el proceso está actualmente operando.

* En caso de soportar el sistema multiprocesador, los procesadores en los que el proceso puede ejecutarse.

* En el caso de un sistema operativo tipo UNIX, el proceso padre de dicho proceso y la relación de procesos hijos.

* Estadísticas temporales: Tiempo de lanzamiento del proceso, tiempo en estado activo, etc.

En Linux, al PCB se le denomina ''Task Struct'', se puede consultar dicha estructura en:

http://lxr.linux.no/#linux+v2.6.37.2/include/linux/sched.h#L1182

En el núcleo de Minix, al PCB se le denomina ''Process table'', puede consultarse su implementación en el siguiente enlace:

http://www.cise.ufl.edu/~cop4600/cgi-bin/lxr/http/source.cgi/kernel/proc.h

Qué es un Sistema Operativo

2011-03-20T11:18:20Z

Dorellana: /* ¿Que es un Sistema Operativo? */

== ¿Que es un Sistema Operativo? ==
* El programa de programas.

* Gestiona los recursos que ofrece el material (el ''hardware'' del equipo):
** La CPU.
** La Memoria principal
** Los dispositivos de Entrada/Salida, tales como la tarjeta de vídeo, la de red, los dispositivos de almacenamiento masivo (disco duro, memoria flash), los dispositivos USB, teclado, ratón...

* Ofrece un lanzador de aplicaciones, que puede ser de dos tipos:
** Gestor de ventanas: las órdenes se dan con el ratón.
** Intérprete de órdenes/comandos (traducción defectuosa del original inglés ''command'', que significa orden), también llamado ''shell''. Las órdenes se escriben con el teclado.

* Ofrece una interfaz (API) a las aplicaciones para solicitar recursos, el SO hace de intermediario, el programa no accede al hardware directamente a obtener los recursos, sino que se los solicita al SO. Esta interfaz ha de ser estable (es decir, que no cambie con el tiempo) y homogénea.

== Principios de diseño de un buen Sistema Operativo ==

Los aspectos a tener en cuenta respecto a la gestión de recursos son:

* Realizar una gestión eficiente de los recursos
* Coordinar la asignación de los mismos (como un "director de orquesta")
* Hacer un reparto equitativo de ellos
* No permitir que las aplicaciones accedan directamente a los recursos sino que sea a través del sistema operativo.

Respecto a la API, debe:

* Ser estable, no debe cambiar con el tiempo.
* Ser homogénea.
* Ocultar los detalles de bajo nivel de los componentes, ofreciendo una capa de abstracción sobre el material.

Además, otro criterio a tener en cuenta por un buen sistema operativo es la portabilidad, es decir, que soporte diferentes arquitecturas, como por ejemplo la ARM (teléfonos móviles), la x86 de Intel, la SPARC (desarrollada por Sun Microsystems, ahora adquirida por Oracle), la PowerPC (creada por la alianza AIM: Apple-IBM-Motorola)...

Sol-ejer1-planif-procesos

2011-03-20T11:13:57Z

Dorellana: Añadido SJF apropiativo

* FIFO (no apropiativo)

____|_PA_|_PB_|_PC_|_PD_|_PE__|
Datos del _H0_|_0__|_1__|_2__|_3__|_4__|
problema _t__|_5__|_3__|_1__|_6__|_2__|

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador

| | | | | | | | | | | | | | | | | | | | |
PA <___|___|___|___|___> | | | | | | | | | | | | | | |
PB | < | | | |___|___|___> | | | | | | | | | | | |
PC | | < | | | | | |___> | | | | | | | | | | |
PD | | | < | | | | | |___|___|___|___|___|___> | | | | |
PE | | | | < | | | | | | | | | | |___|___|> | | |
Planificador X | | | | X | | X X | | | | | X | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

_____|_PA_|_PB_|_PC_|_PD_|_PE__|
Cálculos __t__|_5__|_3__|_1__|_6__|_2__|
de tiempos __T__|_5__|_7__|_7__|_12_|_13_|
_T/t_|_1__|_7/3|_7__|__2_|13/2|
|
|_> Indice de penalización

* SJF (no apropiativo)

____|_PA_|_PB_|_PC_|_PD_|_PE__|
Datos del _H0_|_0__|_1__|_2__|_3__|_4__|
problema _t__|_5__|_3__|_1__|_6__|_2__|

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador

| | | | | | | | | | | | | | | | | | | | |
PA <___|___|___|___|___> | | | | | | | | | | | | | | |
PB | < | | | | | | |___|___|___> | | | | | | | | |
PC | | < | | |___> | | | | | | | | | | | | | |
PD | | | < | | | | | | | |___|___|___|___|___|___> | | |
PE | | | | < | |___|___> | | | | | | | | | | | |
Planificador X | | | | X X | X | | X | | | | | X | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

_____|_PA_|_PB_|_PC_|_PD_|_PE_|
Cálculos __t__|_5__|_3__|_1__|_6__|_2__|
de tiempos __T__|_5__|_7__|_4__|_14_|_4__|
_T/t_|_1__|_7/3|_4__|_7/3|_2__|
|
|_> Indice de penalización

* SJF (apropiativo)

____|_PA_|_PB_|_PC_|_PD_|_PE__|
Datos del _H0_|_0__|_1__|_2__|_3__|_4__|
problema _t__|_5__|_3__|_1__|_6__|_2__|

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador

| | | | | | | | | | | | | | | | | | | | |
PA <___| | | | | | |___|___|___|___> | | | | | | | | |
PB | <___| |___|___> | | | | | | | | | | | | | | |
PC | | <___> | | | | | | | | | | | | | | | | |
PD | | | < | | | | | | | |___|___|___|___|___|___> | | |
PE | | | | < |___|___> | | | | | | | | | | | | |
Planificador X X X X | X | X | | | X | | | | | X | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

_____|_PA_|_PB_|_PC_|_PD_|_PE_|
Cálculos __t__|_5__|_3__|_1__|_6__|_2__|
de tiempos __T__|_5__|_7__|_4__|_14_|_4__|
_T/t_|11/5|_4/3|_1__|_3/2|_2__|
|
|_> Indice de penalización

* indice de penalizacion (no apropiativo)

____|_PA_|_PB_|_PC_|_PD_|_PE__|
Datos del _H0_|_0__|_1__|_2__|_3__|_4__|
problema _t__|_5__|_3__|_1__|_6__|_2__|

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador

| | | | | | | | | | | | | | | | | | | | |
PA <___|___|___|___|___> | | | | | | | | | | | | | | |
PB | < | | | |___|___|___> | | | | | | | | | | | |
PC | | < | | | | | |___> | | | | | | | | |
PD | | | | < | | | | |___|___|___|___|___|___| | | | | |
PE | | | < | | | | | | | | | | | |___|___|> | |
Planificador X | | | | X | | X X | | | | | X | X | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

_____|_PA_|_PB_|_PC_|_PD_|_PE_|
Cálculos __t__|_5__|_3__|_1__|_6__|_2__|
de tiempos __T__|_5__|_7__|_7__|_12_|_13_|
_T/t_|_1__|_7/3|_7__|_7/6|13/2|
|
|_> Indice de penalización

Criterios de planificación

2011-03-16T07:51:16Z

Dorellana: Añadidos órdenes de complejidad

= Métodos no apropiativos =

El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real.

== Estocástico ==

Se selecciona aleatoriamente el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitibilidad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|

< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

== Por orden de llegada (First In, First Out: FIFO) ==

Se selecciona el proceso por orden de lanzamiento. Su principales ventajas son su facilidad de implementación, y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración presentarán un alto índice de penalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución. Para procesos largos puede presentar un índice de penalización elevado: Si se tienen muchos procesos cortos, el de mayor duración puede quedar en espera indefinidamente. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|

== Basado en índice de penalización ==

Se selecciona el proceso que lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización y elige el de mayor valor. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|

< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|---|xxx|xxx|xxx>
Pe |---|---|---|---|---|---<---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]].

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución. Si hay un proceso en estado preparado que requiere menos tiempo de ejecución, se le asigna el procesador. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|

< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
Planificador |---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__| z = índice de penalización
_z__|_1__|_8/5|_1__|14/8|_1__|

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* Índice estático: Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
* Índice dinámico: Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos.

El orden es siempre O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| p = prioridad estática
_p__|_0__|-20_|_4__|_10_|

< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador

|---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|
Planificador |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_6__|_4__|_6__|_12_| z = índice de penalización
_z__|_3__|_1__|_3__|12/7|

== Turno rotatorio estricto (Round Robin: RR) ==

En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado '''quantum''', tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.

El tamaño del '''quantum''' es fundamental para determinar el comportamiento de este criterio de planificación.
Si el '''quantum''' empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, Si el '''quantuam''' empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos'', puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .

Si un proceso bloquea antes de consumir su '''quantum''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| quantum = 1 unidad de tiempo

< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
Pc |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<xxx|---|---|---|xxx|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|
$ $---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_10_|_5__|_12_| z = índice de penalización
_z__|_5/2|10/4|_5/2|12/7|

== Turno rotatorio con compensación ==

Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su '''quantum''', se reinserta en el 25% de la cola, contando desde el principio.

== Turno rotatorio con quantum dependiente del número de procesos ==

Otra variante se trata de emplear un '''quantum''' proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.

== Colas multinivel ==

Criterios de planificación

2011-03-02T17:15:47Z

Dorellana:

* '''Repetitibilidad''': para cargas de trabajo similares debe haber comportamientos similares
* '''Predecibilidad''': el tiempo de terminación de un proceso para una cierta carga de trabajo debe ser similar
* '''Eficiencia''': una rápida toma de decisiones aumenta el rendimiento
* '''Reducir''' el número de '''conmutaciones''': aumentaría el rendimiento, decrementando la penalización asociada
* Atender '''prioridades'''
* Los tiempos de espera tienen que ser '''aceptables''' (menores a 100 ms), para que el usuario no note "saltos" en la ejecución del programa

Hilos

2011-03-02T17:01:44Z

Dorellana: El planificador tiene que trabajar entre dos procesos si sólo es un procesador

En un sistema basado en '''hilos''', los procesos poseen internamente varias líneas (hilos) de ejecución, en contraposición de la visión clásica de la ejecución lineal.

Dentro de los programas, con frecuencia, aparecen ciertos sectores independientes entre sí. En un sistema con multiprogramación, podemos tomar cada sección como procesos independientes ya que la permutación en el orden de ejecución no altera el resultado final. Si alguna de estas secciones presentase algún estado de bloqueo, se sumaría al tiempo global de todo el proceso. Éste tiempo se vería reducido al encontrarnos en un sistema multiprogramado.

Ésta división en múltiples procesos provoca que en memoria se deba reservar un espacio para cada uno y que tras la consecución de cada uno, haya que reunirse todos los resultados en un único espacio de memoria. Otra opción para evitar este problema es el uso de un espacio de memoria común, pero traería consigo problemas de permisos y protección de memoria.

El concepto de '''hilo''' aparece para arreglar estos problemas:

Las líneas internas del proceso se desarrollan sobre el mismo espacio de memoria (la asignada al proceso original). Al ser líneas de ejecución diferentes, poseen su puntero de instrucción, sus valores para los registros de trabajo y su propia pila. No existe la protección entre las diferentes líneas de ejecución, por lo que una sola línea podría destruir el trabajo de las demás. El buen resultado de las líneas depende del programador.

Al usar un espacio de memoria común, la comunicación entre los hilos es más directa que entre procesos independientes con su propio espacio reservado.

La implantación del concepto de hilo provoca que en el sistema operativo sea necesaria la creación de llamadas al sistema referentes a él, tales como: creación de hilos, destrucción de hilos, suspensión, esperas, etc.

El mismo sistema operativo usa el sistema de hilos para la programación de sus actividades.

Veamos un ejemplo diseñado para un solo procesador:

PA1 | .--- . . .
PA2 | . ---. . .
| . . . .
PB | . . .---.
| . . . .
Pla |--. .--. .
|__.______.__.___.>t

Con multiprocesamiento puedo ejecutar diferentes procesos a la vez. Si tengo uno solo pues lo desdoblo en hilos, usando técnicas de programacion apoyadas en APIS (como POSIX threads).

Llamadas al sistema

2011-02-27T11:09:57Z

Dorellana:

Las llamadas al sistema tienen que ser estables a lo largo del tiempo para garantizar la compatibilidad hacia atras.

= Definiciones =

* Compatibilidad hacia atras (Backward compatibility): El nuevo "comprende" el viejo.

* Compatibilidad hacia delante (Fordward compatibility): El viejo "comprende" el nuevo. Esta compatibilidad no está tan trabajada como su opuesta, ya que no la suelen considerar tan importante.

Usuario:Dorellana

2011-02-21T16:39:30Z

Dorellana: Página nueva: David Orellana Martín

David Orellana Martín