Universidad Tecnológica Nacional
Facultad Regional La Rioja
Técnicas Digitales III
- 2022-
Clase Anterior
● Clases con encuentros presenciales
⇨A distancia o en aula → Lunes de 21:00 a 23:00
⇨Videoconferencia l: [Link]
⇨Videoconferencia II: [Link]
● Clases con encuentros no presenciales
⇨Autogestionadas en campus virtual
⇨[Link]
24/04/23 Ing. Ricardo F. Maldonado 2
Introducción al Sistema Operativo
(Linux)
● Gestión de proceso.
– Procesos y tareas
– Estructura general de un proceso
– Estados de un proceso en un S.O.
– Tabla de procesos
– Comandos ps y top
– Conceptos de concurrencia
24/04/23 Ing. Ricardo F. Maldonado 3
Scheduling de procesos
●
Un sistema con un procesador, puede ejecutar un único proceso. Si hay más
procesos, el resto tendrá que esperar hasta que esté libre.
●
El objetivo de la multiprogramación es tener algún proceso en ejecución en
todo momento (maximizar el uso de la CPU).
●
El objetivo del tiempo compartido es que los procesos usen cpu con la
frecuencia mas elevada posible (simula paralelismo).
●
El process scheduler es el encargado de determinar el proceso (de varios)
para la ejecución.
24/04/23 Ing. Ricardo F. Maldonado 4
Estados de un proceso
Dormido
Esperando
Nuevo
Bloqueado
Ejecución
Listo
Zombie
Zombie Terminado
24/04/23 Ing. Ricardo F. Maldonado 5
Estados de un proceso
Dentro del kernel de Linux, todos los
procesos activos se representan
mediante una lista doblemente
enlazada de estructuras de tareas.
El kernel mantiene un puntero al
proceso que se está ejecutando
actualmente en el sistema.
24/04/23 Ing. Ricardo F. Maldonado 6
Listas
●
Una lista es una estructura de datos que entre sus ventajas, tal como la
flexibilidad para el intercambio de nodos o su facilidad en el
ordenamiento, tiene la posibilidad de tener un tratamiento de las
estructura de datos pila o cola con mínimos recursos de programación
struct nodo{
head info N queue struct nodo * sig;
struct nodo * ant;
struct PCB info;
}
N info struct nodo * head;
struct nodo * queue;
Struct nodo * nuevo;
24/04/23 Ing. Ricardo F. Maldonado 7
Listas
●
Una lista es una estructura de datos que entre sus ventajas, tal como la
flexibilidad para el intercambio de nodos o su facilidad en el
ordenamiento, tiene la posibilidad de tener un tratamiento de las
estructura de datos pila o cola con mínimos recursos de programación
head info1 N queue
[Link]= NULL;
[Link] = nuevo;
[Link] = queue;
N info2 queue = nuevo;
info3
nuevo
nuevo=(nodo *)malloc(sizeof(nodo));
24/04/23 Ing. Ricardo F. Maldonado 8
Listas
●
Una lista es una estructura de datos que entre sus ventajas, tal como la
flexibilidad para el intercambio de nodos o su facilidad en el
ordenamiento, tiene la posibilidad de tener un tratamiento de las
estructura de datos pila o cola con mínimos recursos de programación
head
info1 queue
Aux= head;
Head= [Link];
[Link] = NULL;
N info2
info3 N
aux
24/04/23 Ing. Ricardo F. Maldonado 9
Listas
●
Una lista es una estructura de datos que entre sus ventajas, tal como la
flexibilidad para el intercambio de nodos o su facilidad en el
ordenamiento, tiene la posibilidad de tener un tratamiento de las
estructura de datos pila o cola con mínimos recursos de programación
head
N info1 queue
Aux= head;
Head= [Link];
[Link] = NULL;
N info2
info3 N
aux
24/04/23 Ing. Ricardo F. Maldonado 10
Scheduler - Dispatcher
24/04/23 Ing. Ricardo F. Maldonado 11
Scheduler – Planificador de procesos
Es el algoritmo encargado de planificar el orden en los cuales se debe ordenar los
turnos en que se ejecutarán los procesos a partir de una política predefinida que le
permita cumplir con objetivos: por ejemplo:
●
Ejecutar todos los procesos la misma cantidad de tiempo (tengan tiempo de cpu)
●
Minimizar el tiempo ocupado en:
– La espera por cpu → desde que ingresó hasta que comienza su ejecución
– La respuesta → desde que ingreso hasta que culminó la tarea
– El retorno → tiempo en que termina la ejecución de la tarea.
●
Maximizar el uso de cpu
●
Maximizar la productividad
24/04/23 Ing. Ricardo F. Maldonado 12
Scheduler – Planificador de procesos
Tiempo de llegada
Tiempo 0 Tiempo de inicio Tiempo de fin
tarea tarea tarea
T espera =T inicio −T llegada
N N
T retorno=T fin −T 0 1 1
TEM = ∑ Ti espera TRM = ∑ Ti retorno
N 1 N 1
24/04/23 Ing. Ricardo F. Maldonado 13
Scheduler – Planificador de procesos
Los algoritmos que implementa un scheluder que cumplen con las políticas
definida anteriormente son:
●
Primero en llegar, primer en ser atendido FIFO
●
Primero el trabajo mas corto SJF
●
Primero el que de mayor prioridad
●
Round robin con quantum
●
Primero el de tiempo restante mas corto SRTF
24/04/23 Ing. Ricardo F. Maldonado 14
Algoritmo FIFO
Proceso Ráfagas LLegada TA espera =7−2=5 TA retorno =10
A [3] 2 TBespera =12−4=8 TBretorno =13
B [1] 4
C [3] 0
TC espera =0−0=0 TC retorno =3
D [4] 1 TD espera =3−1=2 TD retorno=7
E [2] 3
TEespera =10−3=7 TEretorno =12
[3] [4] [3] [2] [1]
C D A E B
24/04/23 Ing. Ricardo F. Maldonado 15
Algoritmo FIFO
C
TEM =4,4 [ut ]
D D D TRM =9[ut ]
A A A
E E E
B B B
24/04/23 Ing. Ricardo F. Maldonado 16
Algoritmo SJF
C
D D D
A A A
E E
B B B
TEM =2,6 [ut ]
TRM =7,2[ut ]
24/04/23 Ing. Ricardo F. Maldonado 17
Algoritmo con prioridad
Proceso Ráfaga LLegada Prioridad
A [3] 2 2
B [1] 4 3 TEM =4 [ut ]
C [3] 0 1
D [4] 1 3 TRM =6 [ut ]
E [2] 3 4
C
D D D
A A A
E E E
B B B
24/04/23 Ing. Ricardo F. Maldonado 18
Algoritmo Round Robin
Proceso Ráfagas LLegada
A [3] 2
B [1] 4 TEM =5,4 [ut ]
C [3] 0
quantum
D [4] 1 TRM =9[ut ]
E [2] 3
C
D D D D D
A A A
E E E
B B B
24/04/23 Ing. Ricardo F. Maldonado 19
Algoritmo SRTF
Proceso Ráfagas LLegada
A [7] 0
B [4] 2
TEM =3,75[ut ]
C [3] 3
D [2] 5
TRM =7,75[ut ]
A A A
B B
C C C
D D D
24/04/23 Ing. Ricardo F. Maldonado 20
Diseño de Algoritmo
●
Se debe registrar el tiempo de ejecución (el tiempo total)
– Programar timers
– Asignar un tiempo de ejecución
●
Se debe definir la/s política/s para decidir la designación de cpu
– tiempo de ejecución
– prioridad
– quantum
– tiempo restante
24/04/23 Ing. Ricardo F. Maldonado 21
Diseño de Algoritmo
●
Definir la política de desempate (misma prioridad o tiempos)
– orden de llegada
– continuar proceso en ejecución
– Al proceso nuevo
●
Determinar el instante en que se debe decidir
– llegada de un proceso
– quantum
24/04/23 Ing. Ricardo F. Maldonado 22
Algoritmos Apropiativos
●
Aquellos algoritmos que en su implementación necesiten que otro
proceso o el mismo proceso en ejecución pueda suspender la
ejecución de un proceso en curso y ser desalojado de la cpu; es un
algoritmo apropiativo (preemptive).
– El algoritmo fifo no es no apropiativo
– El algoritmo round robin es apropiativo
– El algoritmo SJF puede ser implementado con ambas estrategias.
●
Es conveniente modularizar la tarea de decisión de encolado; con la
tarea de puesta en ejecución y desalojo de procesamiento. A esta
última se le puede asignar la actualización del BRP (dispatcher)
24/04/23 Ing. Ricardo F. Maldonado 23
Algoritmo SJF – apropiativo
Proceso Ráfagas LLegada
A [3] 2
B [1] 4
C [3] 0
C C C D [4] 3
E [2] 1
E E
A A A
D D D
B B B
TEM =2,6 [ut ] TRM =7,2[ut ]
24/04/23 Ing. Ricardo F. Maldonado 24
CONCURRENCIA
24/04/23 Ing. Ricardo F. Maldonado 25
Concurrencia
●
Dos o más eventos cuyo orden es “no determinista”, esto es,
no se puede predecir el orden relativo en que ocurrirán.
●
Cuando procesos (o también dos hilos) independientes entre sí,
se ejecutan simultáneamente → son concurrentes y en esa
ejecución “ocurren cosas” (problemas).
●
El kernel brindan a cada proceso, “la ilusión” de tener un
hardware dedicado y el programador no tiene que pensar en la
competencia por recursos ni la cooperación entre ellos.
24/04/23 Ing. Ricardo F. Maldonado 26
Problema del Jardín Ornamental
“Un jardín se abre al público para que todos puedan apreciar sus
fantásticas rosas, arbustos y plantas acuáticas. Por supuesto, se cobra una
módica suma de dinero a la entrada para lo cual se colocan dos
molinetes, uno en cada una de sus dos entradas. Se desea conocer
cuánta gente ha ingresado, así que se instala dos sensores en ambos
molinetes a una computadora: estos envían una señal cuando una persona
ingresa al jardín.
Es importante notar que los molinetes se comportan en paralelo e
independientemente: los eventos que generan no tienen un orden
predecible. Es decir, que cuando se escriba el software no se sabe
en qué momento llegará cada visitante ni qué molinete utilizará.”
Se simulará un experimento en el que 20 visitantes ingresan por cada
molinete Al final de la simulación deberá haber 40 visitantes contados pero
muchas veces “no se corresponde con la realidad”.
24/04/23 Ing. Ricardo F. Maldonado 27
Problema del “Jardín Ornamental”
int cuenta=0;
proceso molinete1() {
if(cuenta<20)
cuenta = cuenta+1;
}
Código
proceso molinete2() {
Ficticio
if(cuenta<20)
cuenta = cuenta +1;
}
24/04/23 Ing. Ricardo F. Maldonado 28
Problema del Jardín Ornamental
main() {
cuenta = 0;
/* Lanzar ambos procesos concurrentemente*/
concurrentemente {
molinete1();
molinete2();
} Código
/* Esperar a que ambos finalicen */ Ficticio
esperar(molinete1);
esperar(molinete2);
printf("Cuenta: %d\n", cuenta);
}
24/04/23 Ing. Ricardo F. Maldonado 29
Análisis
1. cuenta = 0
2. molinete1: LEE (mov $cuenta,%rax → ax=0, cuenta=0)
3. INC (add $1,%rax → ax=1, cuenta=0)
4. GUARDA (mov %rax,$cuenta → ax=1, cuenta=1)
El sistema operativo decide cambiar de tarea, suspende torniquete1 y
continúa con molinete2.
4. molinete2: LEE (mov $cuenta,%rax → ax=1, cuenta=1)
5. INC (add $1,%rax → ax=2, cuenta=1)
6. GUARDA (mov %rax,$cuenta → ax=2, cuenta=2)
El sistema operativo decide cambiar de tarea, suspende torniquete2 y
continua con molinete1.
24/04/23 Ing. Ricardo F. Maldonado 30
Análisis
1. cuenta = 0
2. molinete1: LEE (mov $cuenta,%rax → ax=0, cuenta=0)
3. INC (add $1,%rax → ax=1, cuenta=0)
El sistema operativo decide cambiar de tarea, suspende molinete1 y
continúa con molinete2.
4. molinete2: LEE (mov $cuenta,%rax → ax=0, cuenta=0)
5. INC (add $1,%rax → ax=1, cuenta=0)
6. GUARDA (mov %rax,$cuenta → ax=1, cuenta=1)
El sistema operativo decide cambiar de tarea, suspende molinete2 y
continua con molinete1.
7. molinete1: GUARDA (mov %rax,$cuenta ax=1, cuenta=1)
24/04/23 Ing. Ricardo F. Maldonado 31
Algunos Conceptos
●
Operación atómica garantiza el traramiento como una “sóla unidad de
ejecución”, o fallará completamente, sin resultados o estados parciales
observables por otros procesos o el entorno. Esto no necesariamente implica
que el sistema no retirará el flujo de ejecución en medio de la operación,
sino que el efecto de que se le retire el flujo no llevará a un comportamiento
inconsistente.
●
Condición de carrera (Race condition) Categoría de errores de
programación que involucra a dos procesos que fallan al comunicarse su
estado mutuo, llevando a resultados inconsistentes. Ocurre típicamente por
no considerar la no atomicidad de una operación
●
Sección (o región) crítica El área de código que requiere ser protegida de
accesos simultáneos donde se realiza la modificación de datos compartidos.
24/04/23 Ing. Ricardo F. Maldonado 32
Algunos Conceptos
●
Recurso compartido Un recurso al que se puede tener acceso desde
más de un proceso. En muchos escenarios esto es un variable en
memoria (como cuenta en el jardín ornamental), pero podrían ser
archivos, periféricos, etcétera.
●
Dado que el sistema no tiene forma de saber que instrucciones (o
áreas del código) deben funcionar de forma atómica, el programador
debe asegurar la atomicidad de forma explícita, mediante la
sincronización de los procesos.
●
El sistema no debe permitir la ejecución de parte de esa área en dos
procesos de forma simultánea (sólo puede haber un proceso en la
sección crítica en un momento dado).
24/04/23 Ing. Ricardo F. Maldonado 33
Aplicar estos conceptos
¿Y qué tiene que ver esto con el problema del jardín?
●
En el planteo hay un recurso compartido que es “cuenta”,
por tanto, el código que modifica a cuenta constituye una
sección crítica y la operación cuenta = cuenta + 1 debe
ser una operación atómica.
●
La secuencia de eventos que se mostró es una condición
de carrera: el molinete2 presume un estado (cuenta = 0)
que no es el mismo que conoce el molinete1 (cuenta = 1).
24/04/23 Ing. Ricardo F. Maldonado 34
¿cual es la solución?
1) No utilizar multitarea (trivial)
2) Suspender la multitarea durante la sección crítica
3) Utilizar una bandera
4) Manejar la bandera con instrucciones atómicas
5) Utilizar turnos
6) Indicar la intención de entrar a la sección crítica
7) El algoritmo de Peterson
24/04/23 Ing. Ricardo F. Maldonado 35
¿cual es la solución?
Suspender la multitarea en la sección crítica
El problema es que cualquier usuario podría
hacer un programa que deshabilite las
disable(); //Suspender interrupciones y lo suspenda.
●
Expone detalles que deberían estar oculto.
cuenta = cuenta + 1;
●
Si el procesamiento de la sección crítica
enable(); es “lenta” para resolver, puede provocar
sobre-escritura de buffer en periférico.
●
No funciona para sistemas distribuidos, ni
siquiera para sistemas multinúcleo o
multiprocesador, ya que las interrupciones
se deshabilitan en un solo núcleo.
24/04/23 Ing. Ricardo F. Maldonado 36
¿cual es la solución?
Utilización de una bandera
int bandera = FALSE;
La bandera también es un /* Torniquete 1 */
recurso compartido: lo único if (bandera) wait;
que ha cambiado es el lugar bandera = TRUE;
de la sección crítica. cuenta = cuenta + 1;
La solución funcionaría si se Bandera = FALSE;
pudiera garantizar que la /* Torniquete 2 */
secuencia de operaciones se if (bandera) wait;
realizara atómicamente bandera = TRUE;
cuenta = cuenta + 1;
Bandera = FALSE;
24/04/23 Ing. Ricardo F. Maldonado 37
¿cual es la solución?
Manejar la bandera con instrucciones atómicas
Se puede permanecer mucho
int bandera; tiempo en el ciclo (alta prioridad),
While(!++bandera){ impidiendo que otro proceso
bandera--; decremente la bandera.
} Algunas arquitecturas no
// Sección crítica permiten instrucciones atómicas
cuenta = cuenta + 1; para acceder a la ram (ninguna
bandera--; arquitectura tipo RISC).
24/04/23 Ing. Ricardo F. Maldonado 38
¿cual es la solución?
Utilizando Turnos while (turno != 1) {
“Equivale a tener un solo esperar();
molinete”. }
/* Sección crítica */
Un proceso que no está en la
cuenta = cuenta + 1;
sección crítica puede obligar a
turno = 2;
que otro proceso espere mucho
while (turno != 2) {
tiempo para ingresar a la sección
esperar();
crítica.
}
/* Sección crítica */
cuenta = cuenta + 1;
turno = 1;
24/04/23 Ing. Ricardo F. Maldonado 39
¿cual es la solución?
Indicar la intención de entrar a la sección crítica
b1 = 1;
if(b2) esperar();
/* Sección crítica */
cuenta = cuenta + 1; Pueden bloquearse mutuamente:
b1 = 0; si el proceso 1 coloca su bandera
en 1 y luego se cambia el control
b2 = 1; al proceso 2, el cual también
if (b1) esperar(); colocará su bandera en 1
cuenta = cuenta + 1;
b2 = 0;
24/04/23 Ing. Ricardo F. Maldonado 40
¿cual es la solución?
El algoritmo de Peterson
int band1, band2, quien;
Las banderas indican qué proceso
band1=1; quien=2; puede ejecutar y un turno por si
if (band2 && (quien==2))
ambos procesos quieren entrar a
esperar();
la vez.
cuenta = cuenta + 1;
band1=0; Si un proceso detecta que el otro
... fue el primero en actualizar el
band2=1;quien=1; turno, entonces lo deja pasar.
if (band1 && (quien==1))
esperar();
cuenta = cuenta + 1;
band2=0;
24/04/23 Ing. Ricardo F. Maldonado 41
¿cual es la solución?
●
Un proceso puede consumir mucho procesador para esperar que otro
cambie una bandera lo cual, en un sistema con manejo de prioridades,
puede resultar inconveniente para el desempeño global (espera activa
o spinlocks).
●
El algoritmo de Peterson sirve únicamente cuando hay dos procesos
que compiten para acceder a una región crítica.
●
Estas soluciones fallan en equipos multiprocesadores, pues aparecen
problemas de coherencia de caché.
24/04/23 Ing. Ricardo F. Maldonado 42
¿cual es la solución?
●
Una forma de abordar estos problemas es forzar cambios
de contexto en esos puntos mediante primitivas del
lenguaje o del sistema operativo (p. ej.: sleep o yield).
●
No es una solución general.
Los sistemas operativos o lenguajes deben proveer la forma
de darle una solución al problema mediante los
denominados mecanismos de sincronización
24/04/23 Ing. Ricardo F. Maldonado 43
Programación
24/04/23 Ing. Ricardo F. Maldonado 44
Generar un nuevo proceso
Mediante el uso de fork(): al ejecutarse desde el programa principal,
crea una copia idéntica del programa y los datos estáticos.
Si fork() se ejecuta con éxito devuelve:
●
Devuelve al padre: variables
– el PID del proceso hijo
– -1 en caso de error
●
Devuelve al hijo:
– el valor 0
24/04/23 Ing. Ricardo F. Maldonado 45
Procesos desde fork()
El hijo generado por fork, hereda el código del padre con la asignación
de la variables pero en espacios diferentes e independientes.
24/04/23 Ing. Ricardo F. Maldonado 46
Parentesco de procesos td3305.c
td3305.c
int main(int argc, char *argv[]){
pid_t pid;
printf("El proceso padre es (%d)...\n",getpid());
pid=fork();
printf("-> Luego del fork el proceso es (%d)\
n",getpid());
if(pid < 0) exit(1);
if(!pid)
printf("[%d] es hijo de [%d] \n",getpid(), getppid());
else
printf("[%d] es el padre y [%d]\
es elabuelo\n", getpid(), getppid());
return 0;
}
24/04/23 Ing. Ricardo F. Maldonado 47
Proceso desde fork()
Ambos códigos son idénticos (el hijo surge del padre) y
la ejecución del hijo comienza luego del fork
24/04/23 Ing. Ricardo F. Maldonado 48
Procesos desde fork()
El valor de pid es quién determina que parte del código
va a ejecutarse a partir del if
24/04/23 Ing. Ricardo F. Maldonado 49
Misma función para dos procesos td3306.c
td3306.c
void relacion(void);
void relacion(void){
int main(){ printf("Función en: [%p] ",relacion);
pid_t pid; printf("proceso: (%d)\n", getpid());
printf("PID del padre (%d)\ }
n",getpid());
pid=fork();
if(pid<0) exit(1);
if(!(pid))
relacion();
else
relacion();
return 0;
}
24/04/23 Ing. Ricardo F. Maldonado 50
¿que sucede en este código? td3307.c
td3307.c
¿Cual sería el valor de las variables?
24/04/23 Ing. Ricardo F. Maldonado 51
Impredictibilidad de la ejecución td3308.c
td3308.c
void proceso(char *);
int main(int argc, char *argv[]){
pid_t pid;
if(!(pid=fork()))
proceso("HIJO");
else
proceso("PADRE");
return 0;
}
void proceso(char *v){
int i;
clock_t ini=clock();
for(i=0;i<10;i++)
printf("%s obtiene %X \n",v,rand());
printf("Fin del proceso %s con %ld tics\n",v,clock()-ini);
}
24/04/23 Ing. Ricardo F. Maldonado 52
¿Como se ejecutaría esta función? td3309.c
td3309.c
void proceso(char *v){
int i,t;
clock_t ini=clock();
for(i=0;i<10;i++){
t=rand()%T;
printf("%s trabaja %d(seg)\n",v,t);
sleep(t);
}
printf("Fin del proceso %s con %ld
tics\n",v,clock()-ini);
}
24/04/23 Ing. Ricardo F. Maldonado 53
Hiper loops Proceso02.c
Proceso02.c
void infinito(pid_t v){
if(!v)printf("Hijo\n");
else printf("Padre\n");
while(1){
if(!v) putchar('H');
else putchar('P');
putchar(13);
}
}
24/04/23 Ing. Ricardo F. Maldonado 54
Ejemplo Proceso03.c
Proceso03.c
int main() {
pid_t pid;
pid = fork();
printf("Ingreso al proceso %d \n",getpid());
if(pid){
printf("Rojo...");sleep(1);
}else{
printf("Verde...");sleep(2);
}
printf("Salgo del proceso %d \n",getpid());
return 0;
}
¿quien se ejecuta primero: sleep o printf?
¿que sucede con sleep(0.99)?
24/04/23 Ing. Ricardo F. Maldonado 55
Ejemplo Proceso03.c
Proceso03.c
int main() {
pid_t pid;
pid = fork();
printf("Ingreso al proceso %d \n",getpid());
if(pid)
While(1) printf("Rojo...");sleep(1);
else
while(1) printf("Verde...");sleep(2);
printf("Salgo del proceso %d \n",getpid());
return 0;
}
¿quien se ejecuta primero: sleep o printf?
¿que pasa con sleep(0.99)?
24/04/23 Ing. Ricardo F. Maldonado 56
¿Preguntas?
¿Consultas?
¿Comentarios?
¿Aportes?
29/08/22 Ing. Ricardo F. Maldonado 57
