| Abreviaturas | Forma de Pensarlo |
|
|
| Proceso | Llegada | Tcpu | Prioridad |
|---|---|---|---|
| P1 | 0 | 9 | 3 |
| P2 | 1 | 5 | 2 |
| P3 | 2 | 3 | 1 |
| P4 | 3 | 7 | 2 |
FCFS (First come first served)
SJF (Shortest Job First)
Round Robin (Timer Variable)
Round Robin (Timer Fijo)
Prioridades
SRTF (Shortest Remaining Time First perteneciente)
Explicación
| job | Llegada | Tcpu | E/S (rec, inst, dur) |
|---|---|---|---|
| P1 | 0 | 5 | (R1, 3, 2) |
| P2 | 1 | 4 | (R2, 2, 2) |
| P3 | 2 | 3 | (R3, 2, 3) |
- rec Nombre del recurso
- inst el instante en donde va a tener que ejecutar la E/S
- dur duración de la E/S
Ejemplo en FCFS
- Primero llegaria el P1, ejecuta 3 rafagas de CPU y su 4ta rafaga es de E/S durante 2 tiempos
- Tenemos una cola por cada recurso distinto
- En caso de tener recursos iguales en distintos procesos, tenemos que esperar a que termine el pricero que se ejecuto para poder ejecutarse.
Estos ejemplos fueron sacados de @agusrnf
FCFS (First come first served)
- No tengo que hacer una cola por cada Recurso?
- Tiene R de donde saca R????
SJF (Shortest Job First)
Round Robin (Timer Variable)
Round Robin (Timer Fijo)
Prioridades
| Job | Llegada | CPU | I/O (rec,ins,dur) | Prioridad |
|---|---|---|---|---|
| 1 | 0 | 9 | (R1, 4, 2) (R2, 6, 3) (R1, 8, 3) | 1 |
| 2 | 1 | 5 | (R3, 3, 2) (R3, 4, 2) | 2 |
| 3 | 2 | 5 | (R1, 4, 1) | 3 |
| 4 | 3 | 7 | (R2, 1, 2) (R2, 5, 3) | 2 |
| 5 | 5 | 5 | (R1, 2, 3) (R3, 4, 3) | 1 |
SRTF (Shortest Remaining Time First perteneciente)
- Primero marcamos todas las llegadas
- La cantidad de columnas es la suma total de los
Tcpu TR=Tfinal-LlegadaTPR=Σ TRn/Cantidad de procesosTE=TR-TcpuTPE=Σ TEn/Cantidad de procesos- Seleccionamos procesos a medida que van llegando, para esto tenemos varias formas
No ApropiativosSe ejecutan hasta el final (Si no hay E/S)FCFSSelecciona los procesos en orden de llegada (El mas viejo)SJFElige el que tiene la siguiente rafaga de CPU mas corta
ApropiativosSe puede cortar la ejecución del procesoRound Robin(RR TV/TF Q=N) Se ejecuta en orden de llegada y si no termino, vuelve a la cola de listosTimer VariableSiempre se ejecutaNtiempos(sino termina antes)Timer FijoCadaNquantumsvoy a cambiar de proceso (un context switch) Esto lo marcamos en el grafico
PrioridadesPor cada prioridad distinta, tenemos una cola nueva- Siempre se descencola el de la cola 1 y 2, si no hay, se descencola el de la cola 3 y 4
- En el instante 2 llega el P2, y como tiene mayor prioridad que el P1(con prioridad 3), se ejecuta primero
- Como el P1 no termino, se vuelve a la cola 3
SRFTEs la versión apropiativa del SJF
- Nro Pagina = Dirección Logica / Tamaño de la Pagina
- Desplazamiento = Dirección Logica % Tamaño de la Pagina
- Dirección Fisica = Base del Frame + Desplazamiento
- Nro Marco = Dirección física / Tamaño del Marco
- Desplazamiento = Dirección física % Tamaño del Marco
- Dirección Logica = (Nro página * Tamaño de página) + Desplazamiento
Ejemplo Si no nos dan los bits para saber si esta en memoria
- Enumeramos todos los marcos y asignamos la pagina con su respectiva direción logica
- El tamaño de pagina es de 512 bytes
- El proceso tiene 2000 bytes por eso llega hastas los 1999 la dirección logica
La fragmentación interna es un tipo de fragmentación que tiene lugar cuando se asigna una memoria más grande a un programa en lugar de la requerida. Fuente
- Fragmentación = Suma de los tamaños de los 4 marcos - Tamaño del archivo
- Fragmentación = 2048 - 2000 = 48 bytes
|
| ||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Indicar las direcciones físicas correspondientes a las siguientes direcciones lógicas
- segmento, pagina, desplazamiento
- (2,1,1) = 1500 + 20 + 1 = 1521
- (1,3,15) = 500 + 60 + 15 = 575
- (3,1,10) = 500 + 120 + 10 = 5130
- (2,3,5) = 1500 + 0 + 5 = 1505
Si se dispone de una espacio de direcciones virtuales de 32 bits, donde cada dirección referencia 1 byte:
- ¿Cuál es el tamaño máximo de un proceso (recordar “espacio virtual”)?
- 2^32 direcciones máximas * 1 byte = 2^ 32 bytes
- 4.294.967.296 bytes
- Si el tamaño de pagina es de 512KB. ¿Cuál es el número máximo de paginas que puede
tener un proceso?
- 4.294.967.296 / 1024 = 4194304 KB
- 4194304 / 512 = 8192
- Si el tamaño de pagina es de 512KB. y se disponen de 256 MB. De memoria real ¿Cuál es el número de marcos que puede haber?
- 256 * 1024 = 262144 KB
- 262144 / 512 = 512
- Si se utilizaran 2 KB. para cada entrada en la tabla de páginas de un proceso: ¿Cuál sería el tamaño máximo de la tabla de páginas de cada proceso?
- 8192 * 2 KB = 16384 KB = 16 MB
|
Asumiendo que: ➢ El tamaño de la página es de 512 bytes ➢ Cada dirección de memoria referencia 1 byte ➢ Los marcos se encuentras contiguos y en orden en memoria (0, 1, 2.. ) a partir de la dirección real 0. |
¿Qué dirección física, si existe, correspondería a cada una de las siguientes direcciones virtuales? (No gestione ningún fallo de página, si se produce)
el bit de control V, que indica si la página se encuentra o no cargada en memoria principal
Usamos las formulas de arriba para la conversión
a) 1052 b) 2221 c) 5499 d) 3101
- Nro Pagina = Dirección Logica / Tamaño de la Pagina
- Desplazamiento = Dirección Logica % Tamaño de la Pagina
- Dirección Fisica = Base del Frame + Desplazamiento
- Nro Pagina = 1052 / 512 = 2
- Desplazamiento = 1052 % 512 = 28
- Page Fault ya que el bit V esta en 0
- Nro Pagina = 2221 / 512 = 4
- Desplazamiento = 2221 % 512 = 173
- Page Fault ya que el bit V esta en 0
- Nro Pagina = 5499 / 512 = 10
- Direccion invalida ya que el nro de pagina es mayor a la cantidad de paginas
- Nro Pagina = 3101 / 512 = 6
- Igual al de arriba
Dada la siguiente tabla de procesos y las páginas que ellos ocupan, y teniéndose 40 marcos en la memoria principal, cuantos marcos le corresponderían a cada proceso si se usa la técnica de Asignación Fija
|
|
Tenemos dos formas de repartir los marcos
| Reparto Equitativo | Reparto Proporcional |
|
|
Considere la siguiente secuencia de referencias a páginas: 1, 2, 15, 4, 6, 2, 1, 5, 6, 10, 4, 6, 7, 9, 1, 6, 12, 11, 12, 2, 3, 1, 8, 1, 13, 14, 15, 3, 8
Si se dispone de 5 marcos. ¿Cuántos fallos de página se producirán si se utilizan las siguientes técnicas de selección de víctima? (Considere una política de Asignación Dinámica y Reemplazo Global)
- Cada vez que hay que alocar una pagina en un marco, se produce un fallo de pagina (page fault) → hard page fault
- ¿Que sucede si es necesario alocar una pagina y ya no hay espacio disponible?
- Se debe seleccionar una pagina victima, para lo cual existen diversos algoritmos
Optimo
Busca que pagina que no se utiliza en el futuro (Una fumada)
Por ejemplo, cuando entra el 4, al marco que es remplazado es el 2, ya que no se vuelve a hacer referencia en un futuro
Segunda Chance (Cola circular con Bit R ó *)
Es igual al fifo (Agarramos el mas viejo) Si la pagina que elegimos tiene el bit R en 1, lo ponemos en 0, y elegimos la siguiente pagina mas vieja
FIFO (Cola circular)
Simplemente remplazo con el marco mas viejo
LRU (Clock)
Elegimos la pagina que no fue referenciada por mas tiempo
Cuando entra el 4, el 2 tiene mas tiempo sin referencias ya que el 1, fue referenciado despues de que entro el 2 y el marco 3 entro despues del marco 2.
Aca tenemos 5 Frames y dejamos el 5to para descarga asincronica, este frame se adecua de acuerdo a las necesidades.
En este ejemplo
- La m significa que cuando es referenciada, se modifica algun valor de esa pagina. Es la misma pagina, pero en ese momento se modifica.
- Cuando la pagina victima es una pagina modificada, damos vuelta y asignamos el frame de la descarga sincronica, a la nueva pagina que se tiene que cargar
- Mientras tanto, esa pagina modificada es cargada al dispositivo de paginación
- Cuando aparece la pagina 5, la pagina victima es la 1
- Pero como la 1 fue modificada, la pagina 5 es cargada en el 5to frame que era el de descarga sincronica
- Y en un instante posterior, marcamos como frame de descarga sincronica al frame 1
- Cuando se tiene que cargar la pagina 7, vemos que la pagina victima, es la pagina 3, como esta fue modificada, por lo tanto el marco 7 va a parar al frame de descarga sincronica que es el 1
Espero haberme explicado bien :D
Supongamos un disco con 6 platos, 2 caras utiles, 1500 pistas por cara y 700 sectores por pista de 256 bytes cada uno. El disco gira a 12600 RPM , tiene un tiempo de posicionamiento (seek) de 2 milisegundos y una velocidad de transferencia de 15 Mib/s (Mebibits por segundo )
Prefijos - Equivalencias
Capacidad
Si queremos calcular la capacidad total del disco, hacemos:
- Tamaño del Disco = #caras * #pistas cara * #sectores pista * tamaño sector
- Tamaño del Disco = 6 * 2 * 1500 * 700 * 256 bytes
- Tamaño del Disco = 3225600000 bytes
- Tamaño del Disco = 3,00407 GiB(Gibibytes)
Ocupación
Si queremos cuantas caras ocupará un archivo de 513 Mibytes almacenado de manera contigua a partir del primer sector de la primer pista de una cara determinada:
1500 * 700 * 256 bytes = 268800000 bytes
513 MiB= 537919488 bytes
537919488 / 268800000 = 2,00118 → 3 caras
Tiempo de acceso
Si queremos saber cuantos milisegundos se tardarían en transferir un archivo almacenado de manera contigua y aleatoria de 4500 sectores
Calculamos los datos que faltan:
Latencia
- 12600 vueltas → 1’ = 60 s = 60000 ms
- 0,5 vueltas → x = 2,3809 ms
Transferencia
- 15 Mibits → 1 s = 1000 ms
- 256 bytes → x
Unificamos unidades
- 15728640 bits → 1000 ms
- 2048 bits → x = 0,1302 ms
Datos obtenidos
- Seek time 2 ms
- Latency time 2,3809 ms
- Tiempo transferencia bloque 0,1302 ms
- #bloques: 4500 → eventualmente se tienen que calcular
Resultados
- Almacenamiento secuencial = seek + latency + tiempo transferencia bloque * #bloques
- Almacenamiento secuencial = 2 + 2,3809 + 0,1302 * 4500 = 590,2809 ms
- Almacenamiento aleatorio = (seek + latency + tiempo transferencia bloque) * #bloques
- Almacenamiento aleatorio = (2 + 2,3809 + 0,1302) * 4500 = 20299,95 ms
- Cantidad de pistas: 200 (0..199)
- Requerimientos en la cola: {98 , 183 , 37, 122, 14, 124, 65, 67}
- Viene de: pista 61
- Ubicación actual del cabezal: pista 53 → derecha-izquierda
FCFS
Atiende los requerimientos por orden de llegada
Movimientos: 640
SSTF
Selecciona el requerimiento que requiere el menor movimiento del cabezal
Movimientos: 235
SCAN
Barre el disco en una dirección atendiendo los requerimientos pendientes en esa ruta hasta llegar a la ultima pista del disco y cambia la dirección. Es importante saber en que pista se está y de que pista se viene para determinar el sentido del cabezal
Movimientos: 236
LOOK
Se comporta igual que el SCAN pero no llega hasta la ultima pista del disco sobre la dirección actual sino que llega hasta el ultimo requerimiento de la dirección actual. Es importante saber en que pista se está y de que pista se viene para determinar el sentido del cabezal
Movimientos: 208
C-SCAN
Se comporta igual que el SCAN pero restringe la atención en un solo sentido. Al llegar a la última pista del disco en el sentido actual vuelve a la pista del otro extremo (salto → no se cuentan los movimientos) y sigue barriendo en el mismo sentido
Movimientos: 187
C-LOOK
Se comporta igual que el LOOK pero restringe la atención en un solo sentido. Al llegar a la ultima pista de los requerimientos en el sentido actual vuelve a la primer pista más lejana del otro extremo (salto → no se cuentan los movimientos) y sigue barriendo en el mismo sentido
Movimientos: 157
- Cantidad de pistas: 100 (0..99)
- Requerimientos en la cola: {55 , 75 , 52PF , 45, 10}. Luego de 30 movimientos {25PF , 60} y luego de 10 movimientos más (40 desde el comienzo de la planificación) entra {90, 10}
- Se se viene de la pista 15
- Se esta atendiendo la pista 20 → izquierda-derecha
FCFS
Movimientos: 334
SSTF
Movimientos: 154
SCAN
Movimientos: 174
LOOK
Movimientos: 154
C-SCAN
Movimientos: 143
C-LOOK
Movimientos: 124