Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Mejoras en la demora de rotación

2016-01-11T12:57:21Z

Evaramcas1:

Para mejorar los tiempos de espera asociados a la demora de rotación se puede ordenar el acceso a los sectores de peticiones que se encuentren en el mismo cilindro de manera que se pueda acceder a las posiciones una detrás de otra sin tener que dar vueltas de sobra. A continuación, las diferentes estrategias:
==Intercalado de sectores==
Esto se basa en que los tiempos de lectura/escritura y transmisión de los datos no son despreciables, con lo que cuando el dispositivo lee unos datos en un sector, mientras que espera a que se transmitan, el disco ha seguido girando y posiblemente se encuentre en otro sector. Por tanto, si los colocamos consecutivamente tendremos que esperar toda una vuelta para acceder al siguiente. Sin embargo, '''colocándolos de manera alterna''', podemos evitar dar la vuelta completa al disco, y esperar una fracción del disco. Esto puede lograrse partiendo de la numeración natural e insertando un escalado de valor n (o grado n), el cual puede llevarse a cabo durante el formateo o por software en el propio gestor.
Cuando el intercalado es de valor n, significa que hay una distancia de '''n sectores entre los anteriores sectores consecutivos'''.

===Ejemplo===
[[Archivo:Sdf.png]]

Si el intercalado se implementa en el gestor mediante software, se debe utilizar una tabla que convierta la dirección lógica del sector (NLS) en su dirección física (NFS). Esta tabla es dependiente del dispositivo, y por tanto debería estar almacenada en el mismo.

==Ordenación circular==
De manera parecida al método anterior vamos a alterar el orden en que vamos a leer los sectores. Si bien una petición más urgente o más antigua nos interesa satisfacerla antes, se dispondrán al principio del orden de lectura/escritura. Es imprescindible saber la posición inicial del cabezal para saber '''qué sectores se visitarán antes''', y en función de esta, se organiza el orden de peticiones.

===Ejemplo===
[[Archivo:SSOOrot2.jpg]]
==Transferencia de pista completa==
La mayor parte de las veces que se accede a un sector en una pista, '''se accede después''' a otro sector que tenga '''adyacente''' en la pista. Para solucionar este retraso ocasionado por dar una vuelta completa al disco se planea que nada mas llegue el cabezal a la pista deseada empiece a transferir hasta que acabe la pista completa.
Los datos no solicitados '''se guardan en caché''' hasta que en un futuro próximo sean pedidos.
De este modo, nos anticipamos a la petición del sector n+1.
Este método es sólo útil para lectura, ya que es una información que se guarda en memoria.

Mejoras en la demora de rotación

2016-01-11T12:56:12Z

Evaramcas1:

Para mejorar los tiempos de espera asociados a la demora de rotación se puede ordenar el acceso a los sectores de peticiones que se encuentren el mismo cilindro de manera que se pueda acceder a las posiciones una detrás de otra sin tener que dar vueltas de sobra. A continuación, las diferentes estrategias:
==Intercalado de sectores==
Esto se basa en que los tiempos de lectura/escritura y transmisión de los datos no son despreciables, con lo que cuando el dispositivo lee unos datos en un sector, mientras que espera a que se transmitan, el disco ha seguido girando y posiblemente se encuentre en otro sector. Por tanto, si los colocamos consecutivamente tendremos que esperar toda una vuelta para acceder al siguiente. Sin embargo, '''colocándolos de manera alterna''', podemos evitar dar la vuelta completa al disco, y esperar una fracción del disco. Esto puede lograrse partiendo de la numeración natural e insertando un escalado de valor n (o grado n), el cual puede llevarse a cabo durante el formateo o por software en el propio gestor.
Cuando el intercalado es de valor n, significa que hay una distancia de '''n sectores entre los anteriores sectores consecutivos'''.

===Ejemplo===
[[Archivo:Sdf.png]]

Si el intercalado se implementa en el gestor mediante software, se debe utilizar una tabla que convierta la dirección lógica del sector (NLS) en su dirección física (NFS). Esta tabla es dependiente del dispositivo, y por tanto debería estar almacenada en el mismo.

==Ordenación circular==
De manera parecida al método anterior vamos a alterar el orden en que vamos a leer los sectores. Si bien una petición más urgente o más antigua nos interesa satisfacerla antes, se dispondrán al principio del orden de lectura/escritura. Es imprescindible saber la posición inicial del cabezal para saber '''qué sectores se visitarán antes''', y en función de esta, se organiza el orden de peticiones.

===Ejemplo===
[[Archivo:SSOOrot2.jpg]]
==Transferencia de pista completa==
La mayor parte de las veces que se accede a un sector en una pista, '''se accede después''' a otro sector que tenga '''adyacente''' en la pista. Para solucionar este retraso ocasionado por dar una vuelta completa al disco se planea que nada mas llegue el cabezal a la pista deseada empiece a transferir hasta que acabe la pista completa.
Los datos no solicitados '''se guardan en caché''' hasta que en un futuro próximo sean pedidos.
De este modo, nos anticipamos a la petición del sector n+1.
Este método es sólo útil para lectura, ya que es una información que se guarda en memoria.

Mejoras de tiempos de desplazamiento

2016-01-11T11:32:42Z

Evaramcas1:

La mayor parte del tiempo que se tarda en realizar una búsqueda en un disco magnético corresponde al de desplazamiento, es decir, el tiempo que el cabezal tarda en moverse al cilindro en el que se encuentra su objetivo. Si se debe atender varias peticiones, el orden en el que se atienden puede ser tal que el recorrido total sea más corto (aunque también es importante que haya una varianza pequeña y no se les de demasiada preferencia a algunos cilindros). Esta sección recoge varios de los criterios posibles.

== FCFS (por orden de llegada "FIFO") ==

Las peticiones se atienden en el mismo orden en que se reciben. Su inconveniente es que se realizan muchos desplazamientos del cabezal, especialmente si se realizan accesos consecutivos a bloques muy alejados entre sí.

== SSTF (Shortest Seek Time First) ==

También conocido como atención por menor tiempo de búsqueda: Ordena todas las solicitudes y selecciona el lote de las ''n'' primeras. Si no se llega a las ''n'' peticiones tras un tiempo se realiza la búsqueda. Su mayor desventaja es que aplaza las peticiones lejanas indefinidamente cuando ''n'' tiende a infinito (''n'' -> ∞).

== N-SCAN (criterio del ascensor) ==

Se escoge un sentido preferente: ascendente o descendente. El cabezal, en ese sentido, atiende todas las peticiones que puede, una detrás de otra, en orden ascendente/descendente hasta llegar a la última de las peticiones del lote. Luego, el cabezal hace lo mismo en el otro sentido, hasta llegar a la última.

|
| /\ | /\
| / \ | / \
| / \ | / \
___|/______\|/______\__
|

Como se puede observar, el cabezal pasa con más frecuencia por la parte central, y el tiempo máximo que puede tardar en llegar a estas es menor que el de los extremos. Por tanto, hay una descompensación a favor de las partes centrales, que puede ser remediada con el siguiente criterio.

Nota: La gráfica resultante no tiene por qué ser simétrica, dependerá de los sectores a los que accedamos.

Nota2: El número de sectores integrantes de cada lote será el indicado por la N, ejemplo: 3-SCAN, 4-SCAN, etc.

== C-SCAN (Circular-Scan) ==

La primera parte es igual: se escoge un sentido y se van atendiendo las peticiones que se pueden en ese sentido una detrás de otra hasta llegar a la última. Al llegar a la última, en vez de recorrer en el sentido opuesto, el cabezal se mueve a la más lejana en el sentido y vuelve a realizar el recorrido en el sentido preferente. Así se elimina el trato favorable a las partes centrales, con el coste de reducir el tiempo medio de atención del conjunto de peticiones

| |
| /. /. /. |\ .\ .\ .
| / . / . / . ó | \ . \ . \ .
| / . / . / . | \ . \ . \ .
___|/___./___._/___._ ___|___\.__ \.___\._
| |

Algún alma caritativa sube los ejemplos de clase antes del parcial??

No copié los datos, pero eran algo similar a esto:

== Ejemplos ==

Orden de acceso: 3, 80, 15, 45, 1, 79, 4

=== Solución FCFS ===

80 x
| / \ x
| / \ / \
50 / \ / \
| / \ x / \
| / \ / \ / \
20 / x \ / \
| x \ / x
___|/___________________x______________
|
| 3 80 15 45 1 79 4

=== Solución 3-SCAN ===

80 x| |
| / |x |
| / | \ |
50 / | \ |
| / | x |
| / | \ |
20 x | \ |
| x | \ |x
___|/________|_______x|__
|
| 3 15 80|79 45 1|4

SO multiprogramables con particiones variables

2015-12-16T16:45:29Z

Evaramcas1:

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(supone un alto coste de rendimiento) 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 (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia, ya que cuanto mayor sea, menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

* '''Listas de control''': Se usa una lista de nodos ordenada por dirección. Por cada bloque libre u ocupado habrá un nodo con:
** Dirección inicial del bloque
** Tamaño del bloque
** Estado (Libre u ocupado)
** Proceso al que está asignado

= Criterios de asignación =

== Primer ajuste ==

Consiste en asignar el primer hueco disponible que tenga un espacio suficiente para almacenar el programa. La principal desventaja es el reiterado 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.

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:
0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
0-4
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== 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. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:

0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
27-31
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

'''DUDA:'''

Es evidente que cuando llega el P5 se necesitan 7 unidades de memoria, y éstas no están disponibles en el hueco de 27 a 31 (ahí solo hay 5) por lo que da la vuelta, vuelve a comenzar y lo asigna al primero que encuentra, que resulta ser casualmente, el 20-26. --[[Usuario:Ferguatol|fernandoenzo]] 22:14 19 dic 2011 (UTC)

== Mejor ajuste ==

Consiste en asignarle al proceso el hueco con menor desperdicio interno, i.e, el hueco el cual al serle asignado el proceso deja menos espacio sin utilizar. Su mayor inconveniente es su orden de complejidad (orden lineal, ''O(n)'') debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente).
Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante será del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

== Peor ajuste ==

Al contrario que el criterio anterior, se busca el hueco con mayor desperdicio interno, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar, y se corta de él el trozo necesario (así la porción sobrante será del mayor tamaño posible y será más aprovechable). Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste (debido a la longitud de las búsquedas) y la fragmentación no resulta demasiado eficiente.

== 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.

Organización de los huecos en el ajuste rápido:

Punteros a listas Lista de huecos
según tamaño
__________________
| | _____ _____ _____
| 0 < t < 10 |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 10 < t < 20 |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| t < 200 |--->|_____|
|__________________|

== 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. Es un método rápido tanto en la asignación como en la liberación de bloques.
El funcionamiento es el siguiente:
Cuando se necesita un bloque de tamaño T se busca en la lista de la 1ª potencia mayor o igual a T (por ejemplo 2k), si no hay ninguno se busca en la lista de la siguiente potencia (2k+1), si encontramos un bloque libre se retira y se divide por la mitad: una parte se le asigna al proceso y la otra se almacena en la lista de los huecos de tamaño 2k.

''Organización de los bloques:''

__________________
| | _____ _____ _____
| 2^(k+1) |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 2^k |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| 1 |--->|_____|
|__________________|

Debido a la forma de dividir los bloques al liberarse uno de ellos solamente podrá fusionarse con sus compañeros (bloques del mismo tamaño) con los que formará un bloque de tamaño superior.

''Divisiones sucesivas de los bloques:''
_______________________________________________
|0 |8 |
|_______________________|_______________________|
_______________________________________________
|0 |4 |8 |12 |
|___________|___________|___________|___________|
_______________________________________________
|0 |2 |4 |6 |8 |10 |12 |14 |
|_____|_____|_____|_____|_____|_____|_____|_____|
_______________________________________________
|0 | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

=Implementación de ajustes en Java=

Se ha realizado un Anexo con la [[Implementación de ajustes en Java|implementación de los criterios de ajuste en Java]], con un gestor de memoria, sobre el que se implementan los métodos de primer ajuste, siguiente ajuste, mejor ajuste y peor ajuste.

Además, permite la visualización de la memoria en cada momento tanto como listas de control como mapas de bits.

Sol tercera oportunidad

2015-12-14T21:09:33Z

Evaramcas1:

'''2(W)--2(R)--3(R)--1(R)--1(W)--3(W)--4(W)--5(W)--1(R)--1(R)--2(W)--3(R)--4(R)'''

Acceso a fallo de página:
página ___1____ 2_____3_____4___________________
| 2 | | | | |
Pagina 2 | R=1 | | | | X | Cola: 2
|_M=1_|_____|_____|_____|________________|
| | | | | |
Pagina 2 | = | | | | | Cola: 2
|_ _|_____|_____|_____|________________|
| | 3 | | | |
Pagina 3 | = | R=1 | | | X | Cola: 2 - 3
|_ _|_M=0_|_____|_____|________________|
| | | 1 | | |
Pagina 1 | = | = | R=1 | | X | Cola: 2 - 3 - 1
|_ _|_ _|_M=0_|_____|________________|
| | | 1 | | |
Pagina 1 | = | = | R=1 | | | Cola: 2 - 3 - 1
|_ _|_ _|_M=1_|_____|________________|
| = | 3 | 1 | | |
Pagina 3 | | R=1 | R=1 | | | Cola: 2 - 3 - 1
|_ _|_M=1_|_M=0_|_____|________________|
| | | | 4 | |
Pagina 4 | = | = | = | R=1 | X | Cola: 2 - 3 - 1 - 4
|_ _|_ _|_ _|_M=1_|________________|
| 2 | 3 | 5 | 4 | |
Pagina 5 | R=0 | R=0 | R=1 | R=0 | X | Cola: 2 - 3 - 4 - 5
|_M=0_|_M=0_|_M=1_|_M=1_|________________|
| 1 | | | | |
Pagina 1 | R=1 | = | = | = | X | Cola: 3 - 4 - 5 - 1
|_M=0_|_ _|_ _|_ _|________________|
| | | | | |
Pagina 1 | = | = | = | = | | Cola: 3 - 4 - 5 - 1
|_ |_ _|_ _|_ _|________________|
| | 2 | | | |
Pagina 2 | = | R=1 | = | = | X | Cola: 4 - 5 - 1 - 2
|_ _|_M=1_|_ _|_ _|________________|
| | | | 3 | |
Pagina 3 | = | = | = | R=1 | X | Cola: 5 - 1 - 2 - 3
|_ _|_ _|_ _|_M=0_|________________|
| 4 | 2 | 5 | 3 | |
Pagina 4 | R=1 | R=0 | R=0 | R=1 | X | Cola: 5 - 2 - 3 - 4
|_M=0_|_M=1_|_M=0_|_M=0_|________________|

9
Tasa fallos pág = ───── = 0,692307
13

Sol tercera oportunidad

2015-12-14T18:04:32Z

Evaramcas1:

'''2(W)--2(R)--3(R)--1(R)--1(W)--3(W)--4(W)--5(W)--1(R)--1(R)--2(W)--3(R)--4(R)'''

Acceso a
página ___1____ 2_____3_____4___ fallo de página:
| 2 | | | |
Pagina 2 | R=1 | | | | X Cola: 2 -
|_M=1_|_____|_____|_____|
| | | | |
Pagina 2 | = | | | | Cola: 2 -
|_ _|_____|_____|_____|
| | 3 | | |
Pagina 3 | = | R=1 | | | X Cola: 2 - 3
|_ _|_M=0_|_____|_____|
| | | 1 | |
Pagina 1 | = | = | R=1 | | X Cola: 2 - 3 - 1
|_ _|_ _|_M=0_|_____|
| | | 1 | |
Pagina 1 | = | = | R=1 | | Cola: 2 - 3 - 1
|_ _|_ _|_M=1_|_____|
| = | 3 | 1 | |
Pagina 3 | | R=1 | R=1 | | Cola: 2 - 3 - 1
|_ _|_M=1_|_M=0_|_____|
| | | | 4 |
Pagina 4 | = | = | = | R=1 | X Cola: 2 - 3 - 1 - 4
|_ _|_ _|_ _|_M=1_|
| 2 | 3 | 5 | 4 |
Pagina 5 | R=0 | R=0 | R=1 | R=0 | X Cola: 2 - 3 - 4 - 5
|_M=0_|_M=0_|_M=1_|_M=1_|
| 1 | | | |
Pagina 1 | R=1 | = | = | = | X Cola: 3 - 4 - 5 - 1
|_M=0_|_ _|_ _|_ _|
| | | | |
Pagina 1 | = | = | = | = | X Cola: 3 - 4 - 5 - 1
|_ |_ _|_ _|_ _|
| | 2 | | |
Pagina 2 | = | R=1 | = | = | X Cola: 4 - 5 - 1 - 2
|_ _|_M=1_|_ _|_ _|
| | | | 3 |
Pagina 3 | = | = | = | R=1 | X Cola: 5 - 1 - 2 - 3
|_ _|_ _|_ _|_M=0_|
| 4 | 2 | 5 | 3 |
Pagina 4 | R=1 | R=0 | R=0 | R=1 | X Cola: 5 - 2 - 3 - 4
|_M=0_|_M=1_|_M=0_|_M=0_|

10
Tasa fallos pág = ───── = 0,7692307
13

Sol tercera oportunidad

2015-12-14T18:02:52Z

Evaramcas1: