Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Sol 7

2011-06-06T16:46:00Z

Elopergom:

La lista de paginas a la que se acceden son las siguientes :

2--2--3--1--1--3--4--5--1--1--2--3--4

___1____ 2_____3_____4___
1º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
2º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
3º Acceso | | | | |
Acceso a: | 2 | 3 | | | Nª de fallos: 2 Cola = 2-3
Pagina 3 |_R=1_|_R=1_|_R=0_|_R=0_|
4º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
5º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
6º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-1-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=0_|
7º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 4 | Nª de fallos: 4 Cola = 2-1-3-4
Pagina 4 |_R=1_|_R=1_|_R=1_|_R=1_|
8º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 1-3-4-5
Pagina 5 |_R=1_|_R=0_|_R=0_|_R=0_|
9º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-4-5-1
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
10º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-4-5-1
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
11º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 4 | Nª de fallos: 6 Cola = 4-5-1-2
Pagina 2 |_R=1_|_R=1_|_R=1_|_R=0_|
12º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 3 | Nª de fallos: 7 Cola = 5-1-2-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=1_|
13º Acceso | | | | |
Acceso a: | 4 | 2 | 1 | 3 | Nª de fallos: 8 Cola = 1-2-3-4
Pagina 4 |_R=1_|_R=0_|_R=0_|_R=0_|

--[[Usuario:Fcoramlop|Fcoramlop]] 22:58 4 jun 2011 (UTC)
8
tasa fallos pág = ---- = 0,615
13

- Duda: En el acceso nº6 ¿Por que ponemos el 3 al final de la cola? se supone que solo se hace eso si recorremos la cola y el bit R se encuentra a 1, entonces ponemos el bit a 0 y colocamos la pagina al final de la cola para darle una 2º oportunidad

[[Criterios_de_reemplazo|Volver]]

Sol 7

2011-06-05T15:08:05Z

Elopergom:

Discusión:Sol 6

2011-06-05T14:38:53Z

Elopergom: Dudas sobre el ejercicio

Un par de preguntas sobre el ejercicio:

-¿Por que en el acceso nº 10 se produce un fallo de pagina si esta ya existía?

-¿Por que en el acceso siguiente (el 11) se quita la pagina 2 en vez de la 5 si las dos tienen los mismos bits?

Criterios de reemplazo

2011-06-03T21:36:26Z

Elopergom:

= '''Criterios de reemplazo''' =

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].
El fallo de página se da cuando se accede a una posición de memoria que esta descargada en disco.

nº fallos pág.
tasa fallos pág = -----------------
nº accesos pág.

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

* Arranque en frío : se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno esta cargado en memoria principal.
* Arranque en caliente : se suponen ya cargadas las páginas de los procesos en memoria principal.

==Criterios==
Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4
Suponiendo arranque en frío
___1____ 2_____3_____4___
memoria principal | | | | |
de 4 marcos |_____|_____|_____|_____|

'''1º) Criterio de página óptima :''' este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

[[sol_1|Solución]]

'''2º) Criterio de página pésima :''' este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

[[sol_2|Solución]]

'''3º) Criterio MRU''' ('''M'''ost '''R'''ecently '''U'''sed) ''':''' página más recientemente usada. Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

[[sol_3|Solución]]

'''4º) Criterio de selección estocástica (aleatoria):''' Consiste en seleccionar una página al azar.

'''5º) Criterio por orden de carga FIFO''' : Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola.

Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

[[sol_5|Solución]]

'''6º) Criterio NRU''' ('''N'''ot '''R'''ecently '''U'''sed) ''':''' Ofrece dos bits para cada página:
* bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* bit M : Se pone a 1 si la página es modificada (escritura).
Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

1º- R=0, M=0 .

2º- R=0, M=1 .

3º- R=1, M=0 .

4º- R=1, M=1 .

Claramente deben realizarse periodos de puesta a 0, que no tienen porque ser simultáneamente en R y M.

[[sol_6|Solución]]

'''7º) Criterio de 2ª oportunidad :''' Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Consiste en recorrer la cola hasta encontrar una página con R a 0 y los procesos que vaya encontrando con R a 1 se les pone R a 0 y se les da una segunda oportunidad poniéndolos al final de la cola.

[[sol_7|Solución]]

'''8º) Criterio LRU''' ('''L'''east '''R'''ecently '''U'''sed) ''':''' Criterio en contraposición al MRU. En MRU elegíamos aquella página que hubiéramos utilizado más recientemente (la primera de la pila de acceso) mientras que en LRU elegimos como página víctima lo contrario: La última página de la pila.

'''9º) Criterio del reloj''' ''':''' Igual que el de 2º oportunidad (FIFO + NRU sin bit M) pero mantenemos un puntero a la ultima pagina examinada.

SO multiprogramables con particiones variables

2011-05-29T15:06:28Z

Elopergom:

== Definición ==

En este tipo de sistemas, las particiones para cada proceso se van creando a medida que son asignadas al procesador. Tiene como ventaja principal que evitamos el desperdicio de memoria dentro de cada bloque ya que cada uno está hecho a medida para el proceso que contiene. Por el contrario, una vez que un proceso ha concluido, su partición se queda en desuso y sería necesario aplicar algoritmos de desfragmentación de memoria para poder unificar todas las partes que han quedado libres y así reciclar las particiones que quedaron huérfanas. Otra forma de obtener particiones de mayor tamaño es unificar dos o más huecos adyacentes en uno sólo.

''Ejemplo:''
_ _
|_| P1 = 3KB |_| P1 = 3KB
|_| P2 = 1KB |_| P2 = 1KB
|_| P3 = 6KB => Finaliza P3 => |_| Libre = 6KB
| | | |
|_| P4 = 31KB |_| P4 = 31KB
| | | |
|_| Libre = 21KB |_| Libre = 21KB

Si un nuevo proceso P5 requiriese 24KB de memoria, no podrían serle asignados, ya que los huecos no son contiguos y para disponer de los 27KB libres en total habría que realizar previamente una desfragmentación.

== Elementos de administración ==

* '''Mapas de bits''': Dividiendo la memoria en bloques, se utiliza un bit para representar si dicho bloque está libre o asignado.

* '''Listas de control''': Se almacena en una lista el tamaño de los huecos y las posiciones de memoria entre las que se encuentran comprendidos.

== Criterios de asignación ==

* '''Primer ajuste''': Consiste en asignar el primer hueco disponible que tenga un espacio suficiente para almacenar el programa. Las dos principales desventajas son su alto desperdicio interno, y el elevado uso de las primeras posiciones de memoria. Este último inconveniente repercute negativamente en la circuitería, debido a que se produce un mayor desgaste en dichas posiciones.

* '''Siguiente ajuste''': Se continúa a partir de la posición de la última asignación realizada.Es muy probable que haya un hueco a partir de esa posición, reduciendo la longitud de la búsqueda. De esta forma se resuelve el inconveniente de usar en exceso las primeras posiciones de la memoria.

* '''Mejor ajuste''': Consiste en asignarle al proceso el hueco con menor ajuste interno. Su mayor inconveniente es su orden de complejidad (orden lineal, ''O(n)'')

* '''Peor ajuste''': Al contrario que el criterio anterior, se asigna a cada proceso el hueco con mayor ajuste interno. Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste.

* '''Ajuste rápido''': Mediante listas de control, se agrupan los huecos disponibles según su tamaño (0 < t < 10, 10 < t < 20, etc.). De esta manera, cuando se necesite un hueco, se seleccionarán los del grupo del tamaño que corresponda. En el caso de que haya varios huecos disponibles, se seleccionará uno en base a cualquiera de los criterios anteriores.

* '''Método de los compañeros''': Es una variante del ajuste rápido, en el que los huecos se dividen en potencias de 2: 21, 22, ..., 2k. No es un método usado en la práctica, ya que al realizar redondeos a potencias de 2, se produce un elevado desperdicio interno

SO multiprogramables con particiones fijas

2011-05-29T15:00:20Z

Elopergom:

La memoria se encuentra dividida en particiones, en cada una habrá un proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un procesos necesita mayor memoria que la partición máxima, entonces este no se ejecuta.
*Desperdicio de memoria. Por ejemplo, si los procesos son muy pequeños y las particiones grandes.

=Criterios de asignación=
Se lanza un proceso, y hay que elegir a que partición va (estrategia de espera). Puede haber una cola por partición, o una sola para todas las particiones.

Ej: tenemos los siguientes procesos: m(P1) = 6KB, m(P2) = 1KB, m(P3) = 3KB, m(P4) = 31KB, m(P5) = 30KB;
y una memoria de 64 KB divididos en 4 huecos como sigue:
_____
|_____| H1 = 8KB
|_____| H2 = 8KB
| |
|_____| H3 = 16KB
| |
| |
| | H4 = 32KB
|_____|

*'''Mejor ajuste estático''': se adjudica cada proceso a la menor partición que quepa. Complejidad: O(1)

[[solución mejor ajuste estático|Ver solución]]

*'''Primer ajuste''': cuando una partición queda libre, se asigna el primer proceso que quepa en ella. Complejidad: O(1)

[[solución primer ajuste|Ver solución]]

*'''Mejor ajuste dinámico''': cuando una partición queda libre, se asigna el mayor proceso que quepa en ella. Complejidad: O(nlog(p))

[[solución ajuste dinámico|Ver solución]]

*'''Mejor que quepa con aplazamiento limitado''': Cuando queda una partición libre, se selecciona el mayor proceso que quepa en ella, pero se cuenta el nº de veces que un proceso se aplaza. Si se superan esas '''n''' veces (umbral), se le da paso.

*'''Subparticiones''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= Métodos de colocación en memoria =

*'''Montaje absoluto''': Se asigna una dirección de memoria constante, siendo por tanto este método muy restrictivo. Se utiliza para la carga del sistema operativo.

* '''Carga con reubicación''': Al realizar la carga, se le aplica a las direcciones lógicas del programa un ''offset'' o desplazamiento asociada. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

* '''Reubicación dinámica''': A diferencia de la carga con reubicación, el desplazamiento se asigna en tiempo de ejecución.
** '''Reubicación dinámica parcial''': Es una variante del anterior, en la que existe también un registro límite.

= Mecanismos de protección de memoria =

Es necesario proteger el SO frente a procesos; y proteger a los procesos entre sí.

* '''Ampliación bits de protección'''

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no esta entre esas dos posiciones no se permite el acceso a memoria.

Usuario:Elopergom

2011-05-29T14:55:29Z

Elopergom: Página nueva: Eloy José Pérez Gómez

Eloy José Pérez Gómez

Otro ejemplo

2011-05-29T14:54:39Z

Elopergom: Mal puestos los datos de tiempo de comienzo de 2 procesos (P3 y P7), la solucion creo que es la correcta para estos tiempos.

Ej: tenemos los siguientes procesos: , , , , ;
y una memoria de 64 KB divididos en 4 huecos como sigue:
_____
|_____| H1 = 8KB | m(P1)=6KB | H0(P1)=0 | t(P1)=8
|_____| H2 = 8KB | m(P2)=1KB | H0(P2)=0 | t(P2)=8
| | | m(P3)=3KB | H0(P3)=1 | t(P3)=2
|_____| H3 = 16KB | m(P4)=31KB | H0(P4)=0 | t(P4)=2
| | | m(P5)=30KB | H0(P5)=0 | t(P5)=2
| | | m(P6)=2KB | H0(P6)=0 | t(P6)=2
| | H4 = 32KB | m(P7)=4KB | H0(P7)=2 | t(P7)=2
|_____| | m(P8)=1KB | H0(P8)=0 | t(P8)=2

solución:
>: fin del proceso.

| P1| P1| P1| P1| P1| P1| P1| P1| |
H1|---|---|---|---|---|---|---|---> |
| | | | | | | | | |
| P6| P6| P7| P7| P3| P3| | | |
H2|---|--->---|--->---|---> | | |
| | | | | | | | | |
| P2| P2| P2| P2| P2| P2| P2| P2| |
H3|---|---|---|---|---|---|---|---> |
| | | | | | | | | |
| P4| P4| P5| P5| P8| P8| | | |
H4|---|--->---|--->---|---> | | |
|___|___|___|___|___|___|___|___|___|__>
0 1 2 3 4 5 6 7 8 9 t

Sol-ejer2-planif-procesos

2011-03-22T22:41:30Z

Elopergom:

= Turno rotatorio estricto =

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

PA bloquea por E/S cada 1 unidad de tiempo
PB bloquea por E/S cada 3 unidades de tiempo
< = 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 | | < |---|---| | |---|---| | | |---|---> | | | | |
Planificador X X | 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

_____|_Pa_|_Pb_|_Pc_|
Cálculos __t__|_3__|_5__|_6__|
de tiempos __T__|_10_|_11_|_12_|
_T/t_|3.3_|2.2_|_2__|

Notése que el proceso A no llega a emplear el ''quantum'' que tiene asignado, en ese caso, como indica la [[Criterios_de_planificación|teoría]], se le retira el procesador y el planificador selecciona a otro proceso. Dejar el procesador sin proceso asignado, es decir, ocioso, va contra la lógica del máximo aprovechamiento del procesador. Por ello, he retirado una solución incorrecta que aparecía en esta sección. --[[Usuario:Pneira|Pneira]] 21:15 21 mar 2011 (UTC)

Tengo una duda en este ejercicio, en la unidad de tiempo 6 cuando el planificador activa el proceso Pb, porque motivo solo le asigna una unidad de tiempo?, podria asignarle 2 no? teniendo en cuenta que el quantum = 2. Ademas el proceso B bloquea cada 3 unidades de tiempo, no entiendo porque solo le asigna una unidad y luego activa en la unidad de tiempo 7 el proceso C.

Pues yo diría que es porque se bloquea cada 3, al igual que el A se bloquea a cada unidad. Ya llevaba 1, y con esa actividad, +2 --[[Usuario:PCamino|PCamino]]

= Por prioridades =

Suponiendo que la prioridad de los procesos es la siguiente: A<B<C

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

PA bloquea por E/S cada 1 unidad de tiempo
PB bloquea por E/S cada 3 unidades de tiempo
< = 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 | | <---|---|---|---|---|---> | | | | | | | | | | |
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

_____|_PA_|_PB_|_PC_|
Cálculos __t__|_3__|_5__|_6__|
de tiempos __T__|_15_|_13_|_6_|
_T/t_|__5_|_2.6|_1__|

= Turno rotatorio proporcional al número de procesos =

____|_PA _|_PB_|_PC _|
Datos del _H0_|_0__|_1__|_2__|
problema _t__|_3__|_5__|_6__|

< = 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 | | <---| | |---| | |---|---| |---| |---> | | | | | |
Planificador X X X X X 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_|
Cálculos __t__|_3__|_5__|_6__|
de tiempos __T__|_7__|_12_|_12_|
_T/t_|2.3_|2.4_|_2__|

=============
Observaciones
=============

- Al no existir en el instante de tiempo 0 problemas de concurrencia de procesos, ¿no debería el proceso A tener derecho a sus dos unidades de tiempo de quantum, aunque este solo utilice una unidad de tiempo debido al bloqueo por E/S?. Esto dejaría al procesador con dos procesos en estado preparado (B y C) en el instante de tiempo 2, donde ya se reduciría el quantum a 1 debido a la existencia de 2 o más procesos en estado preparado. ¿Cómo lo veis?

Creo que no, porque ya en el instante 1 hay dos procesos en el planificador, por lo que el quantum ya se reduce.

Cierto, además creo que aunque A no se bloquease, se le seguiría asignando 1 unidad de tiempo en t=1 al proceso B: Entraría el planificador, reduciría el quantum, y al no haber compensación, A pasaría de nuevo al final de la cola del turno rotatorio, dejando el procesador a B, ¿no?

- Duda: En el instante 9 no debería entrar el proceso Pb en vez de seguir el Pc??

Lo dudo, porque el bloqueo de B dura 2 unidades, así que C tiene carta libre.--[[Usuario:PCamino|PCamino]]

- Duda: ¿Por que el proceso C se ejecuta en el instante 11 habiendo sido bloqueado en el 10?,se supone que todos los procesos tienen un tiempo de bloqueo de 2 unidades

Ejercicios otros aspectos de la planificación

2011-03-21T18:08:51Z

Elopergom: Plazo del proceso D erroneo

== Ejercicio de clase sobre SO de tiempo real ==

____|__PA__|_PB__|_PC__|_PD___|
Datos del _H0_|__0___|_1___|_2___|_3*n__|
problema _t__|__2___|_4___|_2___|_1____|
plazo|__3___|_5___|_7___|_3*n+2|
prioridad|__-20_|_0___|_10__|_15___|
(-20 a 19)
UNIX
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
* = el proceso se aborta

| | | | | | | | | | | | | | | | | | | | |
PA <___|___> | | | | | | | | | | | | | | | | | |
PB | < |___|___|___* | | | | | | | | | | | | | | |
PC | | < | | |___|___> | | | | | | | | | | | | |
PD | | | < | * < |___> <___> | <___> | <___> | | | |
Planificador 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_|PD1ª_|PD2ª_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1__|_1__|_1__|
de tiempos __T__|_2__|_*__|_4__|_*__|_2__|_1__|
_T/t_|_1__|_*__|_2__|_*__|_1.5|_1__|
|
|_> Indice de penalización