Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Usuario:Juarolsal

2015-10-13T21:11:38Z

Juarolsal: Página blanqueada

Usuario:Juarolsal

2015-04-14T13:59:55Z

Juarolsal:

'''Nombre: '''Juan C. Roldán

'''Grado:''' Grado en Ingeniería Informática. Ingeniería del Software

'''Asignatura:''' Sistemas operativos (2012-13)

'''Web:''' [http://juancroldan.com Juan C. Roldán personal webpage]

Usuario:Juarolsal

2014-11-19T00:34:10Z

Juarolsal: Editado mi perfil en esta wiki, dado que es uno de los primeros resultados mostrados en Google al buscar 'juarolsal'

'''Nombre: '''Juan C. Roldán

'''Grado:''' Grado en Ingeniería Informática. Ingeniería del Software

'''Asignatura:''' Sistemas operativos (2012-13)

'''Web:''' [http://www.juarolsal.tk Juarolsal personal webpage]

Implementación de ajustes en Java

2014-04-01T13:11:08Z

Juarolsal: Eliminada mi dirección de contacto (no paraban de enviarme correos)

Algoritmos en Java que implementa los tipos de ajuste vistos en el tema de Administración de memoria. Tiene una clase principal llamada GestionMemoria, que representa al entorno (Administrador de memoria, lista de control, mapa de bits…) y una clase Ajustes que contiene los métodos estáticos equivalentes a cada ajuste:
==Administración de memoria==
Esta es la clase GestionMemoria mencionada.
A la hora de experimentar, el último método, el main(String[] args), es en el que se pueden manipular primitivas como destruyeProceso o creaProceso.
Para cambiar el tipo de ajuste, sólo hay que descomentar y comentar las líneas de código en la función creaProceso.

import java.util.LinkedList; 
import java.util.List; 
 
public class GestionMemoria { 
 // ////////////////////////////////////////////////////////////// 
 // IMPLEMENTACIÓN DE UNIDAD DE GESTIÓN DE MEMORIA EN JAVA /////// 
 // Por Juan Carlos Roldán Salvador ////////////////////////////// 
 // Desarrollado en JavaSE-1.7 /////////////////////////////////// 
 // Modificado por última vez el 3/12/2012 /////////////////////// 
 // ////////////////////////////////////////////////////////////// 
 // 
 // Esta es una implementación funcional de los métodos de primer, 
 // siguiente, mejor y peor ajuste. 
 // En ella se supone una memoria de 32 kB y una gestión mediante 
 // listas de control con ticks de 1 kB. Cada uno de los bloques de 
 // la lista de control es una array de int de 4 valores, que son: 
 // 0: Estado (Un valor de 0 significa libre, un valor de 1 ocupado) 
 // 1: Dirección inicial del bloque 
 // 2: Tamaño (En ticks) 
 // 3: Pid del proceso al que está asignado 
 // 
 // Para cambiar el tipo de ajuste que se aplica solo hay que 
 // comentar/descomentar líneas de código de la función creaProceso. 
 // Se puede cambiar el tamaño del mapa de memoria de 32 a cualquier 
 // otro. 
 // Para ver el estado de la memoria por pantalla se usa la función 
 // imprimeMemoria(). Para crear y destruir procesos se usan las 
 // funciones creaProceso y destruyeProceso, respectivamente. 
 // En la función main (Al final de la clase) hay un ejemplo, con la 
 // creación y destrucción de varios procesos. 
 public static final int LONGITUD_MEMORIA = 32; 
 public static List<int[]> listaControl; 
 public static int[] memoria; 
 public static int ultimoPid; 
 
 /** 
 * Inicia los atributos necesarios para el funcionamiento de la memoria. 
 * 
 */ 
 private static void inicializaMemoria() { 
 listaControl = new LinkedList<int[]>(); 
 memoria = new int[LONGITUD_MEMORIA]; 
 ultimoPid = 0; 
 // Añade una primera entrada a la lista de control, un hueco con el 
 // tamaño de la memoria completa: 
 int[] hueco = { 0, 0, LONGITUD_MEMORIA, 0 }; 
 listaControl.add(hueco); 
 } 
 
 /** 
 * Simula la escritura de datos en la memoria. Guarda los datos en una 
 * array, a modo de mapa de bits. 
 * 
 * @param direccion 
 * - En ticks, posición en que empieza la escritura. 
 * @param tamanyo 
 * - Ticks que se extiende la escritura. 
 * @param dato 
 * - Marca que se pondrá en la memoria, que en un caso real sería 
 * parte del proceso. Por ejemplo, '1' para memoria ocupada y '0' 
 * para memoria vacía. 
 */ 
 private static void escribeMemoria(int direccion, int tamanyo, int dato) { 
 //Escribe el dato 'dato' en las posiciones pertinentes: 
 for (int i = 0; i < tamanyo; i++) { 
 memoria[direccion + i] = dato; 
 // Aquí se puede incluir un delay para simular el acceso a memoria: 
 /* 
 * try { Thread.sleep(3); } catch (InterruptedException e) { 
 * e.printStackTrace(); } 
 */ 
 } 
 } 
 
 /** 
 * Asigna un bloque de memoria a un nuevo proceso. 
 * 
 * @param pid 
 * - Identificador numérico del proceso que se va a crear. El que 
 * la invoque tiene la responsabiidad de evitar que se repita. 
 * @param tamanyo 
 * - Tamaño que necesita el proceso. 
 * @return Devuelve true si se ha podido satisfacer la petición, o 
 * false en caso contrario. 
 */ 
 public static boolean creaProceso(int pid, int tamanyo) { 
 // int hueco = Ajustes.primerAjuste(listaControl, tamanyo); 
 int hueco = Ajustes.siguienteAjuste(listaControl, tamanyo); 
 // int hueco = Ajustes.mejorAjuste(listaControl, tamanyo); 
 // int hueco = Ajustes.peorAjuste(listaControl, tamanyo); 
 boolean res = (hueco != -1); 
 if (res) { 
 int direcc = listaControl.get(hueco)[1]; 
 int[] proceso = { 1, direcc, tamanyo, pid }; 
 int espacioRestante = listaControl.get(hueco)[2] - tamanyo; 
 // Inserta el proceso en el lugar del hueco 
 listaControl.set(hueco, proceso); 
 // Si el proceso es más pequeño que el hueco, inserta un hueco 
 if (espacioRestante > 0) { 
 int[] bloqRestante = { 0, direcc + tamanyo, espacioRestante, 0 }; 
 listaControl.add(hueco + 1, bloqRestante); 
 } 
 escribeMemoria(direcc, tamanyo, 1); 
 } 
 return res; 
 } 
 
 /** 
 * Borra un proceso de la memoria. 
 * 
 * @param pid 
 * - Identificador numérico del proceso que se pretende terminar. 
 * @return Devuelve true si se ha podido satisfacer la petición, o 
 * false en caso contrario. 
 */ 
 public static boolean destruyeProceso(int pid) { 
 // Busca el índice del proceso en la lista de control 
 int indice = 0; 
 for (int[] bloque : listaControl) { 
 indice++; 
 if (bloque[3] == pid) { 
 break; 
 } 
 } 
 indice--; 
 boolean encontrado = (indice != -1); 
 // Si lo ha encontrado, lo borra de la memoria y de la lista de control 
 if (encontrado) { 
 int[] bloqueABorrar = listaControl.get(indice); 
 listaControl.get(indice)[0] = 0; 
 listaControl.get(indice)[3] = 0; 
 escribeMemoria(bloqueABorrar[1], bloqueABorrar[2], 0); 
 fusiona(indice); 
 fusiona(indice - 1); 
 } 
 return encontrado; 
 } 
 
 /** 
 * Fusiona un bloque de memoria de la lista de control con su vecino 
 * posterior, si ambos son bloques libres. 
 * 
 * @param indice 
 * - Posición en la lista de control del primer bloque de la 
 * fusión, siendo el segundo indice + 1. 
 * @return Devuelve true en el caso de que ambos bloques tengan 
 * índices válidos, y estén vacíos, false en caso contrario. 
 */ 
 private static boolean fusiona(int indice) { 
 boolean fusionable = false; 
 if (indice >= 0 && (indice + 1) < listaControl.size()) { 
 fusionable = listaControl.get(indice)[0] == 0 
 && listaControl.get(indice + 1)[0] == 0; 
 } 
 if (fusionable) { 
 int tamanyo = listaControl.remove(indice + 1)[2]; 
 listaControl.get(indice)[2] += tamanyo; 
 } 
 return fusionable; 
 } 
 
 /** 
 * Muestra en pantalla el estado de la lista de control y la memoria. 
 */ 
 public static void imprimeMemoria() { 
 String s = "Lista de control: {[EST-DIR-TAM-PROC]:"; 
 for (int[] bloque : listaControl) { 
 s += "[" + bloque[0] + "-" + bloque[1] + "-" + bloque[2] + "-" 
 + bloque[3]; 
 s += "]"; 
 } 
 s += "}\nMemoria: "; 
 for (int i : memoria) { 
 s += i; 
 } 
 System.out.println(s + "\n"); 
 } 
 
 // Este es el punto de entrada de la implementación.
// Se puede experimentar con las primitivas creadas. 
 public static void main(String[] args) { 
 inicializaMemoria(); 
 
 creaProceso(1, 6); 
 imprimeMemoria(); 
 
 creaProceso(2, 6); 
 imprimeMemoria(); 
 
 creaProceso(3, 8); 
 imprimeMemoria(); 
 
 creaProceso(4, 7); 
 imprimeMemoria(); 
 
 destruyeProceso(2); 
 destruyeProceso(4); 
 creaProceso(5, 7); 
 imprimeMemoria(); 
 
 destruyeProceso(1); 
 creaProceso(6,5); 
 imprimeMemoria(); 
 
 destruyeProceso(5); 
 imprimeMemoria(); 
 
 destruyeProceso(3); 
 destruyeProceso(6); 
 imprimeMemoria(); 
 } 
 
} 

==Ajustes==
Esta es la clase estática que contiene los tipos de ajuste.Se han implementado los métodos de primer ajuste, siguiente ajuste, mejor ajuste y peor ajuste. No está implementado el método de ajuste rápido.

import java.util.*; 
 
public class Ajustes { 
 public static int ultimoBloqueAsignado = 0; 
 
 /** 
 * Implementación del método de primer ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamaño del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int primerAjuste(List<int[]> listaControl, int tamanyo) { 
 int res = 0; 
 for (int[] bloque : listaControl) { 
 if (bloque[0] == 0 && bloque[2] >= tamanyo) { 
 break; 
 } 
 res++; 
 } 
 if (res == listaControl.size()) { 
 res = -1; 
 } 
 return res; 
 } 
 
 /** 
 * Implementación del método de siguiente ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamanyo del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int siguienteAjuste(List<int[]> listaControl, int tamanyo) { 
 int res = ultimoBloqueAsignado; 
 boolean listaRecorrida=false; 
 while (res!=-1) { 
 int bloque[] = listaControl.get(res); 
 if (bloque[0] == 0 && bloque[2] >= tamanyo) { 
 ultimoBloqueAsignado=res; 
 break; 
 } 
 res++; 
 if (res>=listaControl.size()) { 
 if (listaRecorrida) { 
 res=-1; 
 } else { 
 res%=listaControl.size(); 
 listaRecorrida=true; 
 } 
 } 
 } 
 return res; 
 } 
 
 /** 
 * Implementación del método de mejor ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamanyo del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int mejorAjuste(List<int[]> listaControl, int tamanyo) { 
 int i = 0; 
 int menorBloque = -1; 
 int tamMenorBloque = -1; 
 for (int[] bloque : listaControl) { 
 if (bloque[0] == 0 && bloque[2] >= tamanyo 
 && (menorBloque == -1 || bloque[2] < tamMenorBloque)) { 
 menorBloque = i; 
 tamMenorBloque = bloque[2]; 
 } 
 i++; 
 } 
 return menorBloque; 
 } 
 
 /** 
 * Implementación del método de peor ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamanyo del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int peorAjuste(List<int[]> listaControl, int tamanyo) { 
 int i = 0; 
 int mayorBloque = -1; 
 int tamMayorBloque = -1; 
 for (int[] bloque : listaControl) { 
 if (bloque[0] == 0 && bloque[2] >= tamanyo 
 && (mayorBloque == -1 || bloque[2] > tamMayorBloque)) { 
 mayorBloque = i; 
 tamMayorBloque = bloque[2]; 
 } 
 i++; 
 } 
 return mayorBloque; 
 } 
 
 }

Página Principal

2013-01-22T22:37:05Z

Juarolsal: Cambio en el acceso a Segmentación (Para evitar redirecciones dobles)

Bienvenido al wiki de la asignatura de Sistemas Operativos del departamento de Lenguajes y Sistemas Informáticos de la Universidad de Sevilla. ¡Contribuye!

= Novedades y noticias =

* Comienza el curso 2012/2013 --[[Usuario:Pneira|Pneira]] 15:01 28 sep 2012 (UTC)
* Primer control de evaluación continua del grupo GC2 el viernes 9 de noviembre --[[Usuario:Pneira|Pneira]] 16:47 26 oct 2012 (UTC)
* Segundo control de evaluación continua del grupo GC2 el viernes 14 de diciembre --[[Usuario:Pneira|Pneira]] 16:13 28 nov 2012 (UTC)
* Tercer control de evaluación continua del grupo GC2 el viernes 21 de diciembre --[[Usuario:Pneira|Pneira]] 15:10 12 dic 2012 (UTC)
* Notas del grupo de inglés disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/english.txt aquí] --[[Usuario:Pneira|Pneira]] 16:48 11 ene 2013 (UTC)
* Notas de los controles 1, 2 y 3 del grupo GIC2 disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/gic2.pdf aquí]. La revisión es el miércoles después de clase, a partir de las 17h30 --[[Usuario:Pneira|Pneira]] 20:41 11 ene 2013 (UTC)
* Notas del control 1,2,3 y 4 del grupo GIS1 disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/gis1-final.pdf aquí]. --[[Usuario:Pneira|Pneira]] 14:46 16 ene 2013 (UTC)
* Revisión de controles el viernes 18 de enero después del control 4 --[[Usuario:Pneira|Pneira]] 19:16 17 ene 2013 (UTC)
* '''Si quieres que se te tenga en cuenta la posible subida de nota por contribuciones realizadas a la wiki, pincha [[Evaluame mis contribuciones a la wiki|aquí]]'''. --[[Usuario:Pneira|Pneira]] 19:23 17 ene 2013 (UTC)
* Notas del grupo de inglés del control 2, 3 y 4, pincha [http://1984.lsi.us.es/~pablo/notas/english.txt aquí]. --[[Usuario:Pneira|Pneira]] 10:04 18 ene 2013 (UTC)
* Notas provisionales de los controles 1, 2, 3 y 4 del grupo GIC2 disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/ic2-final.pdf aquí]. --[[Usuario:Pneira|Pneira]] 18:53 21 ene 2013 (UTC)

= Unidades didácticas =

A continuación encontrarás las unidades didácticas que forman parte de la asignatura.

== Introducción a los Sistemas Operativos ==

* 1.1. [[Qué es un Sistema Operativo|Qué es un sistema operativo]]
* 1.2. [[Introducción histórica|Breve introducción histórica a los sistemas operativos]]
* 1.3. [[Tipos de Sistemas Operativos|Tipos de sistemas operativos]]

== Fundamentos de Sistemas Operativos ==

* 2.1. [[Organización básica de un ordenador]]
* 2.2. [[Modos de operación de la CPU|Modos de operación de la CPU]]
* 2.3. [[Interrupciones y excepciones|Interrupciones y excepciones]]
* 2.4. [[Arranque del sistema|Arranque del sistema]]
* 2.5. [[Componentes básicos de un sistema operativo|Componentes básicos de un sistema operativo]]
* 2.6. [[Conceptos básicos|Conceptos básicos]]
* 2.7. [[Llamadas al sistema|Llamadas al sistema]]
* 2.8. [[Ejercicios fundamentos Sistemas Operativos|Ejercicios]]

== Modelos de diseño de Sistemas Operativos ==

* 3.1. [[Modelos de Diseño de Sistemas Operativos|Modelos de diseño de sistemas operativos]]
* 3.2. [[Virtualización]]
* 3.3. [[Ejercicios 3|Ejercicios]]

== Procesos ==
* 4.1. [[Multiprogramación|La multiprogramación]]
* 4.2. [[Estados de los procesos|Estados de los procesos]]
* 4.3. [[Planificador de procesos|El planificador de procesos]]
* 4.4. [[Comportamiento de los procesos|El comportamiento de los procesos según el planificador]]
* 4.5. [[Bloque de control de procesos|El bloque de control del proceso]]
* 4.6. [[Conmutación de procesos|La conmutación de procesos]]
* 4.7. [[Hilos|Hilos]]
* 4.8. [[Ejercicios Procesos|Ejercicios]]

== Planificación de Procesos ==
* 5.1 [[Planificación de procesos|La planificación de procesos]]
* 5.2 [[Índices de evaluación|Índices de evaluación de la planificación de procesos]]
* 5.3 [[Criterios de planificación|Criterios de planificación]]
* 5.4 [[Planificadores de sistemas operativos existentes|Planificadores de sistemas operativos existentes]]
* 5.5 [[Planificación de procesos de tiempo real|La planificación de procesos de tiempo real]]
* 5.6 [[Planificación en sistemas multiprocesadores|La planificación de procesos en sistemas multiprocesadores]]
* 5.7 [[Ejercicios otros aspectos de la planificación|Ejercicios]]
* 5.8 [[Ejercicios planificación de procesos|Ejercicios]]

== Concurrencia de procesos ==

* 6.1 [[Concurrencia de procesos|Concurrencia de procesos]]
* 6.2 [[Mecanismos de sincronización|Control optimista y pesimista de la concurrencia]]
* 6.3 [[Cerrojos|Cerrojos]]
* 6.4 [[Ejercicio de concurrencia de procesos|Ejercicios]]

== Semáforos y comunicación ==

* 7.1 [[Semáforos|Semáforos]]
* 7.2 [[Monitores|Monitores]]
* 7.3 [[Mensajería|Mensajería]]
* 7.4 [[Ejercicios sincronización y comunicación|Ejercicios]]

== Interbloqueo ==

* 8.1 [[Definición de interbloqueo|Definición]]
* 8.2 [[Condiciones para el interbloqueo y estrategias de resolución|Modelado y Estrategias]]
* 8.3 [[Algoritmo para averiguar interbloqueo|Algoritmo del banquero]]
* 8.4 [[Ejercicios]]

== Segmentación y paginación ==

* 9.1 [[Introducción|Introducción]]
* 9.2 [[SO multiprogramables con particiones variables|SO multiprogramables con particiones variables]]
* 9.3 [[Segmentación|Segmentación]]
* 9.4 [[Paginación|Paginación]]
* 9.5 [[Sistema combinado|Sistema combinado]]
* 9.6 [[Memoria virtual con multiprogramacion|Memoria virtual con multiprogramación]]
* 9.7 [[Ejercicios administración de memoria contigua|Ejercicios (Administración de memoria contigua)]]
* 9.8 [[Ejemplo de segmentación, paginación y combinado|Ejercicios (Segmentación, paginación y sistemas combinados)]]

== Memoria virtual ==

* 10.1 [[Memoria Virtual|Introducción]]
* 10.2 [[Criterios de reemplazo|Criterios de reemplazo]]
* 10.3 [[Ejercicios memoria virtual|Ejercicios]]

== Entrada/Salida ==

* 11.1 [[EstructuraES|Estructura dispositivo E/S]]
* 11.2 [[GestionES|Modos de gestionar dispositivos E/S]]
* 11.3 [[Diseño modular E/S|Diseño modular E/S]]
* 11.4 [[Ejercicios de Entrada/Salida|Ejercicios]]

== Gestión L/E ==

* 12.1 [[Discos Magnéticos|Discos Magnéticos]]
* 12.2 [[Mejoras de tiempos de desplazamiento|Mejoras de tiempos de desplazamiento]]
* 12.3 [[Mejoras en la demora de rotación|Mejoras en la demora de rotación]]
* 12.4 [[Tipos de errores en discos magnéticos|Tipos de errores en discos magnéticos]]
* 12.5 [[Ejercicios Gestión L/E|Ejercicios]]

== Administración de archivos ==

* 13.1 [[Introducción en la administración de archivos|Introducción en la administración de archivos]]
* 13.2 [[FAT|FAT]]
* 13.3 [[EXT2 |EXT2]]
* 13.4 [[Ejercicios Administración Ficheros|Ejercicios]]

== Anexo ==

Esta sección contiene información interesante pero que no pertenece al temario de la asignatura.

* Todo lo que siempre has querido saber sobre el protocolo SSH está [[SSH|aquí]].

Segmentación

2013-01-22T22:36:08Z

Juarolsal: Segmentacion trasladada a Segmentación: Traslado de 'Segmentacion' a 'Segmentación', debido a que el acento del título va ligado a la página.

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

[[Archivo:Segmentos.png|725px]]

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: Se puede hacer que 2 segmentos se superpongan de manera que compartan direcciones de memoria física con direcciones lógicas diferentes. Para evitar problemas de concurrencia, debe de indicarse explícitamente que una porción de memoria puede ser compartida. De esta manera, procesos diferentes pueden compartir información y código usando la memoria común.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan.

*Gestión compleja, sobretodo por su tamaño variable

*Permite la carga de segmentos a petición, de manera que no se disponga de todos los segmentos en memoria principal, que se puedan descargar a disco (en la zona de intercambio o swap) en base a un cierto criterio (ver [[Intro | Memoria virtual]]). Esta zona de intercambio puede ser:
**Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar
**Un fichero oculto de tamaño fijo o variable dependiendo de la configuración dada por el usuario (Windows).

=Mecanismos=
Los diferentes mecanismos que nos ofrece la segmentación de memoria son los siguientes.
==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio (ver [[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser:

* Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar

* Un fichero oculto de tamaño fijo o variable dependiendo de la configuracion dada por el usuario (Windows).

==Formas de uso de los descriptores==
En cuanto a aspectos materiales, se plantea el problema de que no es habitual que la tabla de segmentos quepa en el dispositivo de traducción (MMU), por lo que se almacena la tabla en memoria, y el MMU contiene su dirección. El problema es que esta técnica hace que el tiempo de acceso se duplique, al haber un primer acceso al MMU y un segundo acceso a la dirección efectiva. Se plantean dos soluciones no excluyentes:
* '''Uso de registros descriptores de segmento en MMU:'''
<blockquote>
En MMU nos encontraremos varios registros que pueden contener descriptores, en los que se copiarán los que se vayan a usar en un futuro inmediato. Hay dos tipos de registros:
*Registros de propósito general:
Registros sobre los que se cargan los próximos descriptores a usar, y dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria (y necesitan más bits para hacer referencia al descriptor)
 - Las que hacen referencia a un descriptor en MMU (y necesitan menos bits para referir al descriptor)
*Registros especializados:
Registros capaces de albergar a un descriptor concreto, como el DS (Para manejo de datos), SS (Para manipulación de pila) o el CS (Para instrucciones de salto y llamadas a rutinas). También existen dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria
 - Las que no hacen referencia a ningún descriptor, y emplean descriptores de MMU, según el tipo de instrucción
</blockquote>

* '''Uso de descriptores en memoria asociativa (Cache):'''
<blockquote>
La MMU contiene una memoria asociativa indexada por número de descriptor. Para cada acceso, se busca en la memoria asociativa el número de descriptor, y si no está, se carga a esta (Si se llena la memoria asociativa se lleva a cabo reemplazo). Este tipo de memoria es transparente, por lo que se puede usar en conjunción con registros descriptores de segmento en MMU.
</blockquote>

=Superposición de segmentos=
Varios segmentos pueden estar parcial o totalmente solapados en memoria. Una dirección física se puede corresponder con múltiples direcciones lógicas. Los segmentos superpuestos pueden tener incluso distintos permisos (segmento 0 y 1 ). Si son totalmente superpuestos se denominan segmentos alias.

Se aplica para implementar la técnica de "copy on write" (animación). Se crea inicialmente un segmento de datos, con permiso de lectura y escritura. Al crear el segmento de COW, este se crea con la misma dirección y tamaño (totalmente solapado), pero nótese que se quita el permiso de escritura en ambos segmentos. Si se intenta escribir en uno de los dos, se produce un fallo de protección. Entonces se copia el segundo segmento sobre una nueva ubicación, actualizándose su dirección y restituyéndose en ambos el permiso de escritura.
Otra aplicación: en un micro que no permita modificar segmento de código, se puede crear un segmento alias de dato para modificarlo.

=Crecimiento de proceso=
Existen dos formas de crecimiento: Asignando nuevos segmentos al proceso, y haciendo crecer algún segmento asignado.
Para crecer un segmento: si hay suficiente espacio libre detrás, se cambia el tamaño en el descriptor; si no hay suficiente espacio: se copia al hueco libre (compactando si es necesario) y se cambia el tamaño ( y dirección base, claro está).
Existe la posibilidad de crecimiento automático, a cada segmento se asocia un atributo "permitir crecer"; Si se sobrepasa el límite en un segmento que puede crecer, el tratamiento de la excepción es el que hará crecer al segmento.
Gracias a la segmentación, todas las direcciones son reubicables.

Discusión:Segmentación

2013-01-22T22:36:08Z

Juarolsal: Discusión:Segmentacion trasladada a Discusión:Segmentación: Traslado de 'Segmentacion' a 'Segmentación', debido a que el acento del título va ligado a la página.

=Características=

*No se redimensionan <<<--------------- ¿No eran de tamaño variable? [[Usuario: JCGarrido|JCGarrido]]

Seguro que se refiere a que una vez creado el segmento del tamaño deseado(lo que quiere decir que son variables) éste se mantiene de tamaño fijo mientras exista, pero tampoco puedo asegurarlo al 100%. ¿Alguien puede aclarar ésto? [[Usuario:Ajaest|ajaest]] 10:06 7 jun 2011 (UTC)

Segmentacion

2013-01-22T22:36:08Z

Juarolsal: Segmentacion trasladada a Segmentación: Traslado de 'Segmentacion' a 'Segmentación', debido a que el acento del título va ligado a la página.

#REDIRECCIÓN [[Segmentación]]

Discusión:Segmentacion

2013-01-22T22:36:08Z

Juarolsal: Discusión:Segmentacion trasladada a Discusión:Segmentación: Traslado de 'Segmentacion' a 'Segmentación', debido a que el acento del título va ligado a la página.

#REDIRECCIÓN [[Discusión:Segmentación]]

Algoritmos de criterios de reemplazo

2013-01-22T22:35:37Z

Juarolsal: Cambiado el enlace de Página Principal#Memoria virtual a Memoria Virtual

= Criterios de reemplazo =

Algoritmos en Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de [[Memoria Virtual|memoria virtual]]. El contenido mínimo que debe tener el script es el siguiente:

<source lang="python">
from collections import deque
from random import choice

class Memoria:
def imprime_cabecera(self):
s = ' '
for i in range(len(self.marcos)):
s+= '___%s___ ' % (i+1)
return s
def __repr__(self):
s = '|'
for programa in self.marcos:
if programa:
s+= ' %s ' % programa
else:
s+= ' '
s+= '|'
s += '\n' + len(s)*'-'
return s

def ejecuta(memoria, secuencia):
fallos = 0
res = memoria.imprime_cabecera()
for programa in secuencia:
hay_fallo = memoria.add(programa)
if hay_fallo:
print(res + ' Fallo de %s!'%programa)
fallos += 1
else:
print(res + ' Acceso a %s'%programa)
res = str(memoria)
print(res)
print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia)))

secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4]
</source>

== Criterio MRU (Most Recently Used) ==

<source lang="python">
class MemoriaMRU(Memoria):
def __init__(self, i):
self.pila = []
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el de lo alto de la pila
indice = self.marcos.index(self.pila.pop())
self.marcos[indice] = False
self.marcos[self.marcos.index(False)] = programa
# Insertamos el programa en la pila actualizando
if programa in self.pila:
self.pila.remove(programa)
self.pila.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m1 = MemoriaMRU(4)
>>> ejecuta(m1, secuencia)
</source>

== Criterio de selección estocástica ==

<source lang="python">
class MemoriaEstocastica(Memoria):
def __init__(self, i):
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Elegimos uno aleatorio
rand = choice(range(len(self.marcos)))
self.marcos[rand] = programa
else:
# Hay un marco vacio
self.marcos[self.marcos.index(False)] = programa
return fallo
</source>

Código de prueba:

<source lang="python">
>>> m2 = MemoriaEstocastica(4)
>>> ejecuta(m2, secuencia)
</source>

== Criterio por orden de carga FIFO ==

<source lang="python">
class MemoriaFIFO(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el primero de la cola
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la cola
if not programa in self.cola:
self.cola.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m3 = MemoriaFIFO(4)
>>> ejecuta(m3, secuencia)
</source>

== Criterio LRU ==

<source lang="python">
class MemoriaLRU(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el primero de la cola
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la cola actualizando
if programa in self.cola:
self.cola.remove(programa)
self.cola.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m4 = MemoriaLRU(4)
>>> ejecuta(m4, secuencia)
</source>

== Criterio LFU ==

<source lang="python">
class MemoriaLFU(Memoria):
def __init__(self, i):
self.marcos = [False] * i
self.contadores = [0] * i

def add(self, programa):
fallo = 0
if not programa in self.marcos:
# Fallo de pagina
fallo = 1
if False in self.marcos:
# Seleccionamos un marco vacio
indice_false = self.marcos.index(False)
self.contadores[indice_false] = 1
self.marcos[indice_false] = programa
else:
# Seleccionamos el de menor contador
indice = self.contadores.index(min(self.contadores))
self.marcos[indice] = programa
self.contadores[indice] = 1
else:
# Exito, incrementamos contador
indice = self.marcos.index(programa)
self.contadores[indice] += 1
return fallo

def __repr__(self):
s = '|'
i = 0
for programa in self.marcos:
if programa:
s+= ' %s {%s} ' % (programa, self.contadores[i])
else:
s+= ' '
s += '|'
i += 1
s += '\n' + len(s)*'-'
return s
</source>

Código de prueba:

<source lang="python">
>>> m5 = MemoriaLFU(4)
>>> ejecuta(m5, secuencia)
</source>

== Criterio de Sustitución por envejecimiento ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

Mejoras en la demora de rotación

2013-01-22T22:27:12Z

Juarolsal: Aclaraciones varias, paréntesis, negritas, ortografía

Para mejorar los tiempos de espera asociados a la demora de rotación se pueden 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.

Paginación

2013-01-22T22:05:24Z

Juarolsal: Deshecha la última edición, alguien ha vuelto a poner el traductor sin tabla de páginas, del que ya se habla en 'tabla de páginas sin memoria', está repe

=Definición=
La paginación es una estrategia de organización de la memoria similar a la segmentación pero con ciertas diferencias, por ejemplo la memoria se considera un espacio continuo dividido en porciones de igual tamaño fijo (frente a la división en segmentos de tamaño variable de la segmentación), a dichas porciones se las conoce como marcos de página o simplemente como páginas.
Las páginas están definidas por un número de página, que identifica de forma única a cada página (dentro del espacio de memoria de un proceso). Cada página se asigna en exclusividad a un proceso.

=Funcionamiento=

Desde el punto de vista de la paginación la traducción de las direcciones de memoria se basa en dos conceptos:

1. El dispositivo traductor divide las direcciones lógicas en 2 partes de la siguiente forma: los n bits más significativos identifican la página mientras que el resto identifica el desplazamiento.

2. Cuando el traductor dinámico de páginas recibe, en una dirección lógica, un número de página este examina una tabla (llamada tabla de páginas) en la cual se relacionan las páginas lógicas con las páginas físicas y obtiene la dirección real (Número de marco) de la siguiente forma:

[[Archivo:Paginas.png]]

Al igual que en la segmentación al intentar acceder a una página ausente se produce un fallo (llamado en este caso '''fallo de página''').

=Otras características=
*Los valores óptimos para las porciones son: en arquitectura de 32 bits es de 4KB, y en arquitectura de 64 bits es de 8KB.
*Los criterios vistos en el tema anterior no se aplican aquí, no tiene sentido hacerlo ya que todas las páginas de memoria son iguales.

==Dispositivo de traducción de direcciones paginadas==
Se dispone de la tabla de páginas de cada proceso en memoria para llevar a cabo la traducción. La tabla de páginas se indexa por número de página.

El dispositivo de traducción de direcciones paginadas debe ser un dispositivo muy rápido, ya que se usa con cada acceso a memoria que se realiza. El tamaño de la tabla de páginas es uno de los aspectos que más influye en el diseño del dispositivo e incluso en la organización de la propia tabla. Otro aspecto relevante es la localización de dicha tabla, la cual puede encontrarse en el traductor o guardada en memoria:
*'''Tabla de páginas en el traductor:'''

Se usa en equipos cuyo espacio de direcciones es de pocas páginas.
El dispositivo de traducción contiene un conjunto de registros organizados como una memoria en los cuales almacena la tabla de páginas.
Dicha página debe sustituirse (lo cual aumenta el tiempo de conmutación) en dos situaciones distintas: al cambiar de proceso y al transferir el control al ss.oo. (en este caso se reduce el tiempo de conmutación utilizando dos tablas separadas, una para los procesos y otra para el ss.oo., las cuales se utilizan dependiendo del modo de uso de la cpu, supervisor o usuario).

*'''Tabla de páginas en memoria:'''

Se usa en equipos con mucha memoria, en los cuales el número de páginas puede llegar a ser muy alto con lo que el tiempo necesario para cargar las páginas en el traductor es demasiado alto.
La tabla de páginas es guardada en la memoria principal y el dispositivo traductor tiene la dirección de comienzo y el tamaño de la tabla, debido a que la tabla está en la memoria principal se necesita, por cada acceso a memoria, un acceso a memoria adicional para obtener el número de página física asociado a la página lógica. Para mantener un tiempo de acceso aceptable se establece una memoria asociativa que conserva las parejas página lógica-página física utilizadas recientemente.

También hay dispositivos traductores que no utilizan tablas de páginas, buscan directamente la información en una memoria asociativa, y si no la encuentran, lanzan una excepción que manejará el sistema operativo. Así, el SO es el responsable de determinar la asociación entre números de página y números de marco, y además de actualizar la memoria asociativa, lo que da cierta flexibilidad.

==Tabla de páginas multinivel==
El objetivo es paginar la tabla de páginas lo que permite que esta no esté cargada completa en memoria y que no ocupe direcciones consecutivas.
En los ss.oo. con tablas de páginas multinivel los números de página se dividen en dos partes: los bits más significativos indican el directorio de páginas correspondiente y con los bits menos significativos el índice del directorio en el que se encuentra la página buscada:

[[Archivo:PaginacionMultinivel.jpg‎ ]]

*'''Tabla de páginas para todo el sistema:''' Es una variante de las tablas de página multinivel, en la que el dispositivo traductor sólo contiene una entrada por cada proceso, indexadas por PID, y una dirección de tabla que contiene las páginas de dicho proceso. Así, ante una conmutación de procesos basta con cambiar de PID.
==Elementos de administración==
La administración es sencilla ya que todas las porciones de memoria son de igual tamaño (se limita a comprobar si hay suficientes marcos libres para ejecutar el proceso).

Se pueden usar:

*'''Tabla de asignación de marcos a procesos:''' Tiene una entrada por marco, que contiene el PID del proceso que lo tiene asignado, o 0, si está libre.
*'''Lista de marcos asignados a procesos:''' Dado que el número de marcos es fijo, se implementa mediante una tabla. Estas listas tienen una entrada por marco. En cada entrada está, o el siguiente marco en la lista, o -1 si el marco es el último. Hay una lista global de marcos libres, y una lista por proceso de marcos ocupados. Para ayudar a la gestión, cada proceso tiene en su PCB los índices del primer y el último marco que tiene asignados.

Discos Magnéticos

2013-01-22T21:58:53Z

Juarolsal: Documentados los recursos multimedia

== Arquitectura de los discos magnéticos ==

Los discos magnéticos están formados por varios discos (desde 2 hasta 7) de material magnético montados sobre el mismo eje, los cuales se mantienen girando a una velocidad constante. Estos discos están recorridos, cada uno, por 2 cabezales magnéticos que no llegan a tocar el disco (están separados unos 3 nanómetros debido a una delgada capa de aire formada por la rotación del disco, de hecho si lo tocan se produce un error conocido como aterrizaje del cabezal) y que leen y escriben datos en el disco creando puntos de campo magnético.

En esta imagen se muestran los componentes de un disco duro magnético:

[[Archivo:componentes_HD_comentados.png]]

= Partes del disco magnético =

La superficie del disco magnético se divide en la siguientes partes:

* Pista (''track'', en inglés): Zona a la que accede el cabezal si este se queda fijo en una posición y el disco sigue girando. Si el cabezal se tratara de un lápiz, la pista sería la zona que el cabezal dibuja sobre el disco (que se trataría de una circunferencia). Hay que tener en cuenta que las pistas más cercanas al centro del disco son de menor tamaño al tener menor radio la circunferencia.
* Sector: Es una subdivisión de una pista (track) en un disco magnético. Cada sector almacena una cantidad fija de datos.
* Cilindro: Conjunto de sectores a los que el conjunto de cabezales pueden acceder desde una posición. Un cilindro está compuesto por un conjunto de sectores.

[[Archivo:cilindro.jpg]][[Archivo:Estructura_disco.png|Estructura de un disco óptico|right]]

= Prestaciones de un disco duro magnético =

Las prestaciones de un disco se pueden medir mediante los siguientes indicadores:

* Capacidad, cantidad de unidades de información que se pueden almacenar en el disco.
* Revoluciones por minuto (RPM), velocidad constante a la que gira el disco magnético.
* Tiempo de arranque del motor, se trata del tiempo que tarda el motor en hacer que el disco comience a girar a velocidad constante.
* Tiempo de accesos, tanto para operaciones de lectura como escritura:
** Tiempo de búsqueda, se trata del tiempo que tarda el cabezal en desplazarse de una pista a otra.
** Demora de rotación, se trata del tiempo que tarda en pasar un sector por delante del cabezal.
** Tiempo de transmisión, se trata del tiempo que toma la transferencia de datos del dispositivo al gestor de dispositivo.

= Recursos multimedia =
Funcionamiento electromecánico de un disco duro:
http://www.youtube.com/watch?v=Wiy_eHdj8kg

Tipos de errores en discos magnéticos

2013-01-20T22:48:40Z

Juarolsal: Aclarada una frase y alterado el orden (Ahora los errores transitorios van antes que los permanentes)

Los errores típicos relacionados con los discos duros magnéticos pueden ser:

* '''Transitorios''': Errores temporales del dispositivo. Por ejemplo, caídas de tensión. La solución consiste en reintentar acceder al dispositivo un nº finito de veces, antes de declarar el error permanente. También existen rutinas de checksum (dispersión, como CRC) para distinguir entre errores transitorios y permanentes.
* '''Permanentes''': La unidad se encuentra mal en algún sentido. No existe forma “tradicional” de acceder a ellos. En los discos magnéticos existen dos estrategias para tratar estos errores:
# Archivo que contiene todos los sectores defectuosos.
# Mantener en una tabla aquellos bloques defectuosos (p.e. FAT).
*Errores de '''programación''': Cuando el error se encuentra en el propio código del ''driver''. La solución pasa por esperar que se ofrezca una nueva versión del ''driver'' que solucione el problema.
*Errores de '''localización''': Tras mover el cabezal a un cilindro, se comprueba que el cabezal no está en el cilindro deseado. Se puede reintentar o recalibrar el cabezal.
*Errores de '''controlador''': El controlador está basado en un microprocesador y por tanto es posible que se bloquee. Si tras resetear no se arregla el problema, es posible que el controlador esté dañado.

Estructura típica de dispositivo E/S

2013-01-20T22:46:13Z

Juarolsal: Añadida una sección acerca del dispositivo DMA

En general, la estructura típica de un dispositivo de entrada/salida está dividida en tres partes:

* '''Adaptador de Entrada/Salida del ordenador, o interfaz del bus:''' Se encarga de traducir las señales al dialecto empleado por el bus del ordenador. Algunos ejemplos de interfaces de este tipo son los buses PCI, PCMCIA, USB, PCI-express o SATA entre muchos otros.
* '''Control del dispositivo, o puerto de lectura/escritura:''' Ofrece una interfaz que es empleada por el gestor de dispositivos para gobernar el dispositivo, que dispone de:
**Registros de órdenes
**Registros de estado
**Registros de lectura/escritura, o alternativamente una pequeña memoria propia.
* '''Adaptador de Entrada/Salida del dispositivo, o interfaz del dispositivo:''' Se encarga de traducir las señales al dialecto empleado por el dispositivo.

Cuanto más elaborado sea el puerto de lectura/escritura, mayor rendimiento se puede llegar a alcanzar, puesto que el gestor de dispositivo será más sencillo (y eso implica menor número de instrucciones a ejecutar en el gestor de dispositivo).

La conexión existente entre el procesador y el dispositivo de E/S queda resumida de la siguiente manera:

[[Archivo:Dispositivos ES.svg|Estructura del dispositivo]]

= Gestor de dispositivos =

El gestor de dispositivo, popularmente conocido por la palabra inglesa ''driver'', es la parte del sistema operativo que se encarga de gobernar un cierto dispositivo o una familia de dispositivos de naturaleza similar. El gestor de dispositivo se trata de una pieza de software que conoce los detalles de bajo nivel del dispositivo. De esta manera el driver hace uso del conjunto de instrucciones que ofrece el puerto de E/S, los registros de estado y de lectura
y escritura, para gobernar el dispositivo. Si el fabricante del dispositivo no ofrece un ''driver'' para un cierto sistema operativo, el dispositivo y los recursos que ofrece no puede ser gestionado por el sistema operativo. Por lo general el fabricante de un dispositivo desarrolla el gestor de dispositivo para los sistemas operativos mayoritarios (i.e. Windows y Linux) para asegurar que su dispositivo alcanza la mayor cuota de usuarios posibles.

Los gestores de dispositivos representan en torno al 70% de los sistemas operativos<ref>Construction of a Highly Dependable Operating System, Proc. 6th European Dependable Computing Conference (EDCC-6), pp. 3-12, Oct. 2006</ref>. Por lo general, en los sistemas operativos monolíticos se ejecutan en el espacio del núcleo del sistema operativo por razones de rendimiento. Por tanto, se ejecutan en modo privilegiado, así un error de programación en un ''driver'' lleve a un cuelgue completo del sistema con casi total seguridad. Se estima que en torno al 85% de cuelgues de Microsoft Windows XP <ref>Recovering Device Drivers, Proc. OSDI '04, pp. 1-16, 2004</ref>se debe a errores de programación en ''drivers''.

No obstante, en sistemas operativos convencionales como Windows, Linux y Mac, existen mecanismos que permiten ejecutar ''drivers'' como procesos de usuario, tal y como sucede en sistemas operativo de tipo micronúcleo. De esta manera, un error de programación no produce el cuelgue del sistema completo. No obstante, dichos gestores de dispositivos se limitan a dispositivos particularmente lentos en los que la tasa de transferencia de datos es baja y los tiempos de respuesta del dispositivo son altos, por ejemplo, los gestores de dispositivos para lectores de tarjetas inteligentes (smartcards, lo que incluye las tarjetas SIM que se emplean en telefonía móvil) en Linux funcionan en espacio de usuario.

==DMA==
'''DMA''' (''Direct memory access'') es un dispositivo capaz de '''transferir datos''' entre la memoria principal y el dispositivo de E/S. El procesador le ordena hacer transferencias, y cuando termina, produce una interrupción.

Pueden estar '''integrados''' tanto en el sistema como en el propio dispositivo.

Frecuentemente son '''multicanal''', por lo que se pueden tener varias transferencias en curso simultáneamente.

Pueden soportar transferencias de memoria a memoria.

==Notas==
<references/>

Estructura típica de dispositivo E/S

2013-01-20T22:36:43Z

Juarolsal: Cambiado 'notes' por 'notas'

Gestión de Entrada/Salida

2013-01-20T22:26:12Z

Juarolsal: Completada la gestión por programa con un fragmento de código de las transparencias (Al no haber un formato code, he usado CSS)

El sistema operativo puede gobernar el dispositivo E/S a través del gestor de dispositivos de tres maneras posibles:

* Gestión de E/S por programas.
* Gestión de E/S por interrupciones.
* Gestión híbrida de E/S.

= Gestión de E/S por programas =

El gestor de dispositivo periódicamente comprueba el estado del dispositivo. Para ello comprueba mediante los registros de estado del puerto de E/S si hay datos provenientes del dispositivo que deben ser tratados.
Un ejemplo de lectura de un único dispositivo sería:
<div style="font-family:Consolas, Courier New, Courier;border:1px dashed #9ab;text-indent: 5%">
configurar_dispositivo();

while(!fin_lectura) {

operacion_cualquiera();

while (!dato_recibido());

leer_dato();
</div>

Es ineficaz en sistemas interactivos, debido a que requiere espera ocupada y resulta engorrosa para atender a varios dispositivos simultáneamente, al implicar establecer prioridades entre estos.

= Gestión de E/S por interrupciones =

Una interrupción por hardware es una señal proveniente de un dispositivo de E/S para notificar al procesador de un cierto evento que debe ser tratado. Por ejemplo, un proceso hace uso de la llamada al sistema ''read'' para solicitar información que se encuentra en disco magnético. Una vez que la información está disponible, la interrupción es empleada para que se ejecute el gestor de dispositivos y obtenga los datos para dicho proceso, que ya están disponibles.

Las interrupciones son un mecanismo que ofrece la arquitectura para conectar los dispositivos de E/S con el procesador. No obstante, los datos provenientes del dispositivo de E/S se obtienen a través del bus.

El dispositivo de E/S emplea una de las líneas de interrupción que conectan al dispositivo con el procesador. Cada una de estas líneas corresponden con un cierto dispositivo o una familia de dispositivos de naturaleza similar. La signación de líneas y dispositivo es estática y sucede en tiempo de arranque, por tanto, no cambia a lo largo del tiempo. En caso de que haya datos a tratar en el dispositivo, se notifica al procesador mediante la línea de interrupción. Ante esto, el planificador debe apartar el proceso que esté en estado activo para conmutar al gestor de dispositivo, el cual realizará el tratamiento de la interrupción, obteniendo los datos del dispositivo de E/S que están pendientes de ser tratados.

Por tanto, por cada interrupción se debe [[Conmutación_de_procesos|conmutar]] al gestor de dispositivos.

Las interrupciones no son reentrantes, esto quiere decir que cuando se está realizando el tratamiento de una interrupción se desactiva temporalmente la notificación por interrupciones. Por tanto, una interrupción se ejecuta hasta fin de tratamiento, y en ningún caso es interrumpida por otra interrupción.

= Gestión de E/S híbrida =

Esta aproximación es la más usada en sistemas operativos modernos, y consiste en emplear una combinación de las soluciones anteriores. En principio, se realiza una gestión por interrupciones, pero ante situaciones de estrés en las que se ofrezca una carga de trabajo muy alta, que pueda llevar a una sobrecarga de conmutaciones, se limita en el tiempo la consulta de datos. Por ejemplo, si la tarjeta de red estuviera saturando el procesador con interrupciones, se puede optar por atenderlas todas juntas periódicamente (En lotes).

Diseño modular E/S

2013-01-20T22:10:13Z

Juarolsal: Reescrita desde cero incluyendo la información que ya estaba, ampliando con las diapositivas, y estructurando de manera más esquemática.

El diseño de software de lectura/escritura nos plantea las siguientes necesidades:
* Modelar un '''diseño por capas o estratos''', dotando de una abstracción que oculte las peculiaridades de los dispositivos a las capas superiores, que deben ofrecer una interfaz homogénea.

* Hacer a los '''programas independientes de los dispositivos''', que no tienen por qué conocer el soporte que manejan. Esto es deseable en cuanto a que el fabricante del dispositivo podría dejar de fabricar el dispositivo, por tanto, el proceso tendría que ser reescrito para soportar el nuevo dispositivo. De igual manera, si el dispositivo para el que está diseñado el proceso que conoce los detalles de bajo nivel no está disponible en el sistema, nuestro proceso quedaría inservible.

* Dar un '''criterio uniforme de denominación''': En sistemas Unix, por ejemplo, se trata a cada dispositivo como a un fichero

* '''Tratamiento de errores''' lo más '''próximo''' posible a su '''origen''': si un estrato detecta un error y puede solucionarlo, lo oculta a los niveles superiores. Si no, informa a nivel superior.

* Forzar a que un '''proceso tenga que pasar por el sistema operativo''', que es quien garantiza que el reparto de recursos es equitativo. Si un proceso dispone de acceso directo a un dispositivo, podría adoptar un comportamiento ''abusón'' de manera que no permitiera a otros procesos emplearlo.

* '''Gestionar el acceso compartido''' a los dispositivos: Por ejemplo, un disco magnético puede ser accedido de forma compartida, mientras que un soporte de cinta, es deseable que no lo sea

La forma de cubrir todas estas necesidades es crear la siguiente abstracción:

[[Archivo:diseño modular.jpg|center|x400px]]

'''Nota''': el SSI es una subrutina de manejo de interrupciones.

Gestión de Entrada/Salida

2013-01-20T21:50:13Z

Juarolsal: Reescrita en su mayor parte la Gestión de E/S híbrida tal y como se vió en clase

El sistema operativo puede gobernar el dispositivo E/S a través del gestor de dispositivos de tres maneras posibles:

* Gestión de E/S por programas.
* Gestión de E/S por interrupciones.
* Gestión híbrida de E/S.

= Gestión de E/S por programas =

El gestor de dispositivo periódicamente comprueba el estado del dispositivo. Para ello comprueba mediante los registros de estado del puerto de E/S si hay datos provenientes del dispositivo que deben ser tratados.

= Gestión de E/S por interrupciones =

Una interrupción por hardware es una señal proveniente de un dispositivo de E/S para notificar al procesador de un cierto evento que debe ser tratado. Por ejemplo, un proceso hace uso de la llamada al sistema ''read'' para solicitar información que se encuentra en disco magnético. Una vez que la información está disponible, la interrupción es empleada para que se ejecute el gestor de dispositivos y obtenga los datos para dicho proceso, que ya están disponibles.

Las interrupciones son un mecanismo que ofrece la arquitectura para conectar los dispositivos de E/S con el procesador. No obstante, los datos provenientes del dispositivo de E/S se obtienen a través del bus.

El dispositivo de E/S emplea una de las líneas de interrupción que conectan al dispositivo con el procesador. Cada una de estas líneas corresponden con un cierto dispositivo o una familia de dispositivos de naturaleza similar. La signación de líneas y dispositivo es estática y sucede en tiempo de arranque, por tanto, no cambia a lo largo del tiempo. En caso de que haya datos a tratar en el dispositivo, se notifica al procesador mediante la línea de interrupción. Ante esto, el planificador debe apartar el proceso que esté en estado activo para conmutar al gestor de dispositivo, el cual realizará el tratamiento de la interrupción, obteniendo los datos del dispositivo de E/S que están pendientes de ser tratados.

Por tanto, por cada interrupción se debe [[Conmutación_de_procesos|conmutar]] al gestor de dispositivos.

Las interrupciones no son reentrantes, esto quiere decir que cuando se está realizando el tratamiento de una interrupción se desactiva temporalmente la notificación por interrupciones. Por tanto, una interrupción se ejecuta hasta fin de tratamiento, y en ningún caso es interrumpida por otra interrupción.

= Gestión de E/S híbrida =

Esta aproximación es la más usada en sistemas operativos modernos, y consiste en emplear una combinación de las soluciones anteriores. En principio, se realiza una gestión por interrupciones, pero ante situaciones de estrés en las que se ofrezca una carga de trabajo muy alta, que pueda llevar a una sobrecarga de conmutaciones, se limita en el tiempo la consulta de datos. Por ejemplo, si la tarjeta de red estuviera saturando el procesador con interrupciones, se puede optar por atenderlas todas juntas periódicamente (En lotes).

Usuario:Juarolsal

2013-01-19T11:07:52Z

Juarolsal:

Juan Carlos Roldán Salvador

Grado en Ingeniería Informática. Ingeniería del Software

Asignatura de Sistemas operativos cursada durante el 2012-2013

Usuario:Juarolsal

2013-01-19T11:07:44Z

Juarolsal: Página creada con 'Juan Carlos Roldán Salvador Grado en Ingeniería Informática. Ingeniería del Software Asignatura de Sistemas operativos cursada durante el 2012-2013'

Juan Carlos Roldán Salvador
Grado en Ingeniería Informática. Ingeniería del Software
Asignatura de Sistemas operativos cursada durante el 2012-2013

Evaluame mis contribuciones a la wiki

2013-01-17T20:27:06Z

Juarolsal: Añadido mi nombre a la página

A continuación, indica tu nombre y apellidos:

* Manuel Pérez Gutierrez
* Juan De Lucas Rodríguez
* Juan Carlos Roldán Salvador

Implementación de ajustes en Java

2013-01-13T16:19:35Z

Juarolsal: Nueva sección

Algoritmos en Java que implementa los tipos de ajuste vistos en el tema de Administración de memoria. Tiene una clase principal llamada GestionMemoria, que representa al entorno (Administrador de memoria, lista de control, mapa de bits…) y una clase Ajustes que contiene los métodos estáticos equivalentes a cada ajuste:
==Administración de memoria==
Esta es la clase GestionMemoria mencionada.
A la hora de experimentar, el último método, el main(String[] args), es en el que se pueden manipular primitivas como destruyeProceso o creaProceso.
Para cambiar el tipo de ajuste, sólo hay que descomentar y comentar las líneas de código en la función creaProceso.

import java.util.LinkedList; 
import java.util.List; 
 
public class GestionMemoria { 
 // ////////////////////////////////////////////////////////////// 
 // IMPLEMENTACIÓN DE UNIDAD DE GESTIÓN DE MEMORIA EN JAVA /////// 
 // Por Juan Carlos Roldán Salvador (juancarlos@sevilla.es) ////// 
 // Desarrollado en JavaSE-1.7 /////////////////////////////////// 
 // Modificado por última vez el 3/12/2012 /////////////////////// 
 // ////////////////////////////////////////////////////////////// 
 // 
 // Esta es una implementación funcional de los métodos de primer, 
 // siguiente, mejor y peor ajuste. 
 // En ella se supone una memoria de 32 kB y una gestión mediante 
 // listas de control con ticks de 1 kB. Cada uno de los bloques de 
 // la lista de control es una array de int de 4 valores, que son: 
 // 0: Estado (Un valor de 0 significa libre, un valor de 1 ocupado) 
 // 1: Dirección inicial del bloque 
 // 2: Tamaño (En ticks) 
 // 3: Pid del proceso al que está asignado 
 // 
 // Para cambiar el tipo de ajuste que se aplica solo hay que 
 // comentar/descomentar líneas de código de la función creaProceso. 
 // Se puede cambiar el tamaño del mapa de memoria de 32 a cualquier 
 // otro. 
 // Para ver el estado de la memoria por pantalla se usa la función 
 // imprimeMemoria(). Para crear y destruir procesos se usan las 
 // funciones creaProceso y destruyeProceso, respectivamente. 
 // En la función main (Al final de la clase) hay un ejemplo, con la 
 // creación y destrucción de varios procesos. 
 // Por favor, contacta conmigo si tienes alguna duda o encuentras algún 
 // error en esta implementación. 
 
 public static final int LONGITUD_MEMORIA = 32; 
 public static List<int[]> listaControl; 
 public static int[] memoria; 
 public static int ultimoPid; 
 
 /** 
 * Inicia los atributos necesarios para el funcionamiento de la memoria. 
 * 
 */ 
 private static void inicializaMemoria() { 
 listaControl = new LinkedList<int[]>(); 
 memoria = new int[LONGITUD_MEMORIA]; 
 ultimoPid = 0; 
 // Añade una primera entrada a la lista de control, un hueco con el 
 // tamaño de la memoria completa: 
 int[] hueco = { 0, 0, LONGITUD_MEMORIA, 0 }; 
 listaControl.add(hueco); 
 } 
 
 /** 
 * Simula la escritura de datos en la memoria. Guarda los datos en una 
 * array, a modo de mapa de bits. 
 * 
 * @param direccion 
 * - En ticks, posición en que empieza la escritura. 
 * @param tamanyo 
 * - Ticks que se extiende la escritura. 
 * @param dato 
 * - Marca que se pondrá en la memoria, que en un caso real sería 
 * parte del proceso. Por ejemplo, '1' para memoria ocupada y '0' 
 * para memoria vacía. 
 */ 
 private static void escribeMemoria(int direccion, int tamanyo, int dato) { 
 //Escribe el dato 'dato' en las posiciones pertinentes: 
 for (int i = 0; i < tamanyo; i++) { 
 memoria[direccion + i] = dato; 
 // Aquí se puede incluir un delay para simular el acceso a memoria: 
 /* 
 * try { Thread.sleep(3); } catch (InterruptedException e) { 
 * e.printStackTrace(); } 
 */ 
 } 
 } 
 
 /** 
 * Asigna un bloque de memoria a un nuevo proceso. 
 * 
 * @param pid 
 * - Identificador numérico del proceso que se va a crear. El que 
 * la invoque tiene la responsabiidad de evitar que se repita. 
 * @param tamanyo 
 * - Tamaño que necesita el proceso. 
 * @return Devuelve true si se ha podido satisfacer la petición, o 
 * false en caso contrario. 
 */ 
 public static boolean creaProceso(int pid, int tamanyo) { 
 // int hueco = Ajustes.primerAjuste(listaControl, tamanyo); 
 int hueco = Ajustes.siguienteAjuste(listaControl, tamanyo); 
 // int hueco = Ajustes.mejorAjuste(listaControl, tamanyo); 
 // int hueco = Ajustes.peorAjuste(listaControl, tamanyo); 
 boolean res = (hueco != -1); 
 if (res) { 
 int direcc = listaControl.get(hueco)[1]; 
 int[] proceso = { 1, direcc, tamanyo, pid }; 
 int espacioRestante = listaControl.get(hueco)[2] - tamanyo; 
 // Inserta el proceso en el lugar del hueco 
 listaControl.set(hueco, proceso); 
 // Si el proceso es más pequeño que el hueco, inserta un hueco 
 if (espacioRestante > 0) { 
 int[] bloqRestante = { 0, direcc + tamanyo, espacioRestante, 0 }; 
 listaControl.add(hueco + 1, bloqRestante); 
 } 
 escribeMemoria(direcc, tamanyo, 1); 
 } 
 return res; 
 } 
 
 /** 
 * Borra un proceso de la memoria. 
 * 
 * @param pid 
 * - Identificador numérico del proceso que se pretende terminar. 
 * @return Devuelve true si se ha podido satisfacer la petición, o 
 * false en caso contrario. 
 */ 
 public static boolean destruyeProceso(int pid) { 
 // Busca el índice del proceso en la lista de control 
 int indice = 0; 
 for (int[] bloque : listaControl) { 
 indice++; 
 if (bloque[3] == pid) { 
 break; 
 } 
 } 
 indice--; 
 boolean encontrado = (indice != -1); 
 // Si lo ha encontrado, lo borra de la memoria y de la lista de control 
 if (encontrado) { 
 int[] bloqueABorrar = listaControl.get(indice); 
 listaControl.get(indice)[0] = 0; 
 listaControl.get(indice)[3] = 0; 
 escribeMemoria(bloqueABorrar[1], bloqueABorrar[2], 0); 
 fusiona(indice); 
 fusiona(indice - 1); 
 } 
 return encontrado; 
 } 
 
 /** 
 * Fusiona un bloque de memoria de la lista de control con su vecino 
 * posterior, si ambos son bloques libres. 
 * 
 * @param indice 
 * - Posición en la lista de control del primer bloque de la 
 * fusión, siendo el segundo indice + 1. 
 * @return Devuelve true en el caso de que ambos bloques tengan 
 * índices válidos, y estén vacíos, false en caso contrario. 
 */ 
 private static boolean fusiona(int indice) { 
 boolean fusionable = false; 
 if (indice >= 0 && (indice + 1) < listaControl.size()) { 
 fusionable = listaControl.get(indice)[0] == 0 
 && listaControl.get(indice + 1)[0] == 0; 
 } 
 if (fusionable) { 
 int tamanyo = listaControl.remove(indice + 1)[2]; 
 listaControl.get(indice)[2] += tamanyo; 
 } 
 return fusionable; 
 } 
 
 /** 
 * Muestra en pantalla el estado de la lista de control y la memoria. 
 */ 
 public static void imprimeMemoria() { 
 String s = "Lista de control: {[EST-DIR-TAM-PROC]:"; 
 for (int[] bloque : listaControl) { 
 s += "[" + bloque[0] + "-" + bloque[1] + "-" + bloque[2] + "-" 
 + bloque[3]; 
 s += "]"; 
 } 
 s += "}\nMemoria: "; 
 for (int i : memoria) { 
 s += i; 
 } 
 System.out.println(s + "\n"); 
 } 
 
 // Este es el punto de entrada de la implementación.
// Se puede experimentar con las primitivas creadas. 
 public static void main(String[] args) { 
 inicializaMemoria(); 
 
 creaProceso(1, 6); 
 imprimeMemoria(); 
 
 creaProceso(2, 6); 
 imprimeMemoria(); 
 
 creaProceso(3, 8); 
 imprimeMemoria(); 
 
 creaProceso(4, 7); 
 imprimeMemoria(); 
 
 destruyeProceso(2); 
 destruyeProceso(4); 
 creaProceso(5, 7); 
 imprimeMemoria(); 
 
 destruyeProceso(1); 
 creaProceso(6,5); 
 imprimeMemoria(); 
 
 destruyeProceso(5); 
 imprimeMemoria(); 
 
 destruyeProceso(3); 
 destruyeProceso(6); 
 imprimeMemoria(); 
 } 
 
} 

==Ajustes==
Esta es la clase estática que contiene los tipos de ajuste.Se han implementado los métodos de primer ajuste, siguiente ajuste, mejor ajuste y peor ajuste. No está implementado el método de ajuste rápido.

import java.util.*; 
 
public class Ajustes { 
 public static int ultimoBloqueAsignado = 0; 
 
 /** 
 * Implementación del método de primer ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamaño del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int primerAjuste(List<int[]> listaControl, int tamanyo) { 
 int res = 0; 
 for (int[] bloque : listaControl) { 
 if (bloque[0] == 0 && bloque[2] >= tamanyo) { 
 break; 
 } 
 res++; 
 } 
 if (res == listaControl.size()) { 
 res = -1; 
 } 
 return res; 
 } 
 
 /** 
 * Implementación del método de siguiente ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamanyo del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int siguienteAjuste(List<int[]> listaControl, int tamanyo) { 
 int res = ultimoBloqueAsignado; 
 boolean listaRecorrida=false; 
 while (res!=-1) { 
 int bloque[] = listaControl.get(res); 
 if (bloque[0] == 0 && bloque[2] >= tamanyo) { 
 ultimoBloqueAsignado=res; 
 break; 
 } 
 res++; 
 if (res>=listaControl.size()) { 
 if (listaRecorrida) { 
 res=-1; 
 } else { 
 res%=listaControl.size(); 
 listaRecorrida=true; 
 } 
 } 
 } 
 return res; 
 } 
 
 /** 
 * Implementación del método de mejor ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamanyo del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int mejorAjuste(List<int[]> listaControl, int tamanyo) { 
 int i = 0; 
 int menorBloque = -1; 
 int tamMenorBloque = -1; 
 for (int[] bloque : listaControl) { 
 if (bloque[0] == 0 && bloque[2] >= tamanyo 
 && (menorBloque == -1 || bloque[2] < tamMenorBloque)) { 
 menorBloque = i; 
 tamMenorBloque = bloque[2]; 
 } 
 i++; 
 } 
 return menorBloque; 
 } 
 
 /** 
 * Implementación del método de peor ajuste. 
 * 
 * @param listaControl 
 * - Lista de control. 
 * @param tamanyo 
 * - Tamanyo del hueco requerido. 
 * @return Devuelve el índice del lugar en el que se encuentra el primer 
 * bloque libre con el que satisfacer la petición, o -1 en el caso 
 * de no haber ninguno disponible. 
 */ 
 public static int peorAjuste(List<int[]> listaControl, int tamanyo) { 
 int i = 0; 
 int mayorBloque = -1; 
 int tamMayorBloque = -1; 
 for (int[] bloque : listaControl) { 
 if (bloque[0] == 0 && bloque[2] >= tamanyo 
 && (mayorBloque == -1 || bloque[2] > tamMayorBloque)) { 
 mayorBloque = i; 
 tamMayorBloque = bloque[2]; 
 } 
 i++; 
 } 
 return mayorBloque; 
 } 
 
 }

SO multiprogramables con particiones variables

2013-01-13T16:07:08Z

Juarolsal: Añadido un acceso al anexo de implementación de ajustes en Java

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

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 ajuste 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 sera 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 ajuste 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 2^k), si no hay ninguno se busca en la lista de la siguiente potencia (2^k+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 2^k.

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

Criterios de reemplazo

2013-01-13T16:00:11Z

Juarolsal: Correcciones ortográficas, párrafos reescritos y añadidos, añadido el critero de 3ª oportunidad y explicada la anomalía de Belady

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 produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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 está cargado en memoria principal.
* Arranque en caliente: se suponen ya cargadas las páginas de los procesos en memoria principal.

== Criterio de página óptima (OPT, MIN) ==

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.

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 |_____|_____|_____|_____|

*[[sol_1|Solución]]

== Criterio de página pésima (MAX)==

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. También implica tener conocimiento de futuro, por lo que no es implementable en la práctica.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico, serviría para aproximar la cota media de la ''tasa de fallos de página''. Consiste en seleccionar una página al azar.

Dado que su implementación es trivial, cualquier algoritmo que de resultados similares a este será un mal criterio, pues seguro que su eficiencia será menor que la de no implementar ningún criterio y seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso. Es una aproximación implementable en la práctica del criterio MAX, pudiendo así compararlo con otros criterios.

*[[sol_3|Solución]]

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

El inconveniente de este criterio es que las páginas más usadas son las que más tiempo deberían permanecer en memoria, y son las más atacadas. No se debe suponer que, si las páginas “dejarán de ser necesarias”, implica que “ya no sean necesarias”.
Además, se produce la anomalía de Belady, efecto que consiste en la posibilidad de tener más fallos de página al aumentar el número de marcos en la memoria física.

*[[sol_5|Solución]]

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

En resumen, el bit R se pondrá a 1 ante cualquier tipo de acceso, y el bit M se pondrá a 1 sólo ante eventos de escritura.

Para seleccionar la página víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:

# R=0, M=0
# R=0, M=1
# R=1, M=0
# R=1, M=1

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la combinación de los criterios FIFO y NRU, pero sin emplear el bit M de NRU. Cuando hay que seleccionar una página víctima, se recorre la lista de páginas por orden de carga en memoria hasta encontrar alguna que tenga el bit R a 0. Durante la iteración, si se encuentra una cuyo bit R valga 1, se pone a 0, se retira de la lista y se añade al final (para darle una segunda oportunidad). Cuando se añade una nueva página, se añade al final de la cola con el bit R a 1.

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada, de manera que para dar la 2ª oportunidad a una página, sólo hemos de poner su bit R a 0 y pasar al siguiente.

*[[sol_reloj|Solución]]

==Criterio de la 3ª oportunidad (Método Multics)==
Es otra variante del criterio NRU, en la que se mantiene una lista ordenanda por orden de carga. Ante una sustitución, la primera candidata es la más antigua.

Si dicha página tiene el bit R a 1, se pone a 0 y se pasa al final de la lista (recibe una segunda oportunidad).

Si dicha página tiene el bit R a 0, existen dos casos:
*Si tiene el bit M a 1, se pone a 0 y se pasa al final de la lista.
*Si tiene el bit M a 0, se selecciona como página víctima.

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el '''orden de acceso''' a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero. Es inviable en la práctica, pues supone mantener contadores de tamaños muy grande, uno por cada página en memoria, y por cada acceso a memoria podría ser necesario ejecutar una rutina que actualice la lista.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

Se tiene un bit R y un contador por cada marco. Cuando una página es cargada a un marco, se carga con su bit R a 1 y su contador inicial a 0. Cuando pasa un período determinado de tiempo (viene dado en el enunciado) se itera sobre toda la lista de páginas, y pueden ocurrir dos cosas:
* '''Si su bit R está a 1''': Se ponen su bit R a cero y su contador se incrementa.
* '''Si su bit R está a 0''': No se hace nada.

Cuando hay que seleccionar una página víctima, se escoge aquella cuyo contador sea más pequeño. En caso de empate, habrá que establecer un criterio de desempate.

*[[sol_9.2|Solución]]

== Sustitución por envejecimiento ==

Se emplea un registro R de N bits, asociado a cada página. Por cada acceso se pone a 1 el bit más significativo. Periódicamente se desplaza hacia la derecha el registro R. La página víctima será la que tenga el menor valor en el registro R (en caso de empate se emplea otro criterio). La información que contienen los bits menos significativos se pierden al realizar desplazamientos. Este criterio permite mantener un historial de acceso a las páginas, para seleccionar como víctima aquella que lleve más tiempo sin ser accedida.

*[[sol_10|Solución]]

= Implementaciones =

En el [[Algoritmos de criterios de reemplazo|Portal de la comunidad]] se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento.
Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --[[Usuario:Alexrdp|Alexrdp]] 16:24 6 jun 2011 (UTC)

Memoria virtual con multiprogramacion

2013-01-13T15:53:15Z

Juarolsal: Nueva sección por completo

Cuando se aplican métodos de memoria virtual en sistemas multiprogramados, surgen nuevos problemas o elecciones de diseño.
==Criterios locales y globales==
A la hora de elegir página víctima, podemos elegirla entre las asignadas al proceso (criterio local), o entre todas las páginas del sistema (Criterio global).
*'''Criterio local:''' Mantiene constante el número de páginas de un proceso cargadas en memoria, y es más eficiente, al operar sólo con las páginas del proceso. Se plantea el problema de determinar el número inicial de marcos.
*'''Criterio local:''' La asignación dinámica de marcos se adapta a las necesidades de los procesos. Se plantea el problema de que el criterio de sustitución favorece al proceso activo, ya que un proceso inactivo puede encontrarse que cuando le llegue el turno, se encuentre sus páginas movidas a memoria.
*'''Criterio mixto:''' Tiene las ventajas de ambos criterios, ya que ante una sustitución, se aplica un criterio local, de manera que el algoritmo de sustitución opera sobre un conjunto menor de marcos, y de forma dinámica, se equilibra el número de marcos entre procesos.
==Modelo del conjunto de trabajo==
Es un modelo que sigue un criterio híbrido y define como conjunto de trabajo el rango de páginas con las que opera un proceso durante una fase de su ejecución. Por ejemplo, puede que al iniciarse un proceso, necesite un rango de 10 o 20 páginas, y que pasado un tiempo, se estabilice, usando únicamente 3 o 4. Su conjunto de trabajo es un rango de páginas que cambia a lo largo del tiempo.

El objetivo es evitar la hiperpaginación, es decir, la sobrecarga debida a un aumento de la frecuencia de fallos de página hasta que se produzca un fallo de página cada pocas instrucciones.

La estrategia tener como máxima la de no retirarle nunca a un proceso una página perteneciente a su conjunto de trabajo.
==Aplicación de frecuencia de fallos de páginas==
Ya que el sistema operativo no puede saber cuál es el conjunto de trabajo de un proceso, se sigue una estrategia aproximada: Asignar dinámicamente el número de marcos en función de la frecuencia de fallos de página, que se limita superior e inferiormente.

Así, nunca habrá procesos con un número excesivo de marcos (Aprovechamiento) ni con menos de los necesarios (Posible hiperpaginación)
==Métodos de reserva==
Una posible decisión de diseño es la de mantener siempre una lista de marcos libres, ya que la memoria virtual funciona mejor si hay marcos libres cuando se produce un fallo de página.

Un demonio de paginación se ejecuta periódicamente, para descargar páginas que no estén en uso aplicando algún criterio de sustitución.

Esta decisión de diseño es discutible en sistemas interactivos, ya que tras periodos de inactividad por parte del usuario, este se puede encontrar con una sobrecarga añadida en la reanudación, al haber muchos procesos cuyas páginas han sido descargadas.
==Carga de páginas por anticipado==
Para evitar fallos de página, se pueden cargar páginas antes de que hagan falta, aplicando criterios de:
*Localidad espacial: Al transferir una página, se transfieren también sus adyacentes.
*Conjuntos de trabajo: En caso de bloqueo, se anotan las páginas que supuestamente pertenecen al conjunto de trabajo, para que al reactivarlo, se carguen todas esas páginas. El sistema operativo Android es un ejemplo de administrador de memoria que aplica esta técnica.

Página Principal

2013-01-13T15:49:52Z

Juarolsal: Añadida la sección de memoria virtual con multiprogramación

Bienvenido al wiki de la asignatura de Sistemas Operativos del departamento de Lenguajes y Sistemas Informáticos de la Universidad de Sevilla. ¡Contribuye!

= Novedades y noticias =

* Comienza el curso 2012/2013 --[[Usuario:Pneira|Pneira]] 15:01 28 sep 2012 (UTC)
* Primer control de evaluación continua del grupo GC2 el viernes 9 de noviembre --[[Usuario:Pneira|Pneira]] 16:47 26 oct 2012 (UTC)
* Segundo control de evaluación continua del grupo GC2 el viernes 14 de diciembre --[[Usuario:Pneira|Pneira]] 16:13 28 nov 2012 (UTC)
* Tercer control de evaluación continua del grupo GC2 el viernes 21 de diciembre --[[Usuario:Pneira|Pneira]] 15:10 12 dic 2012 (UTC)
* Notas del grupo de inglés disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/english.pdf aquí] --[[Usuario:Pneira|Pneira]] 16:48 11 ene 2013 (UTC)
* Notas de los controles 1, 2 y 3 del grupo GIC2 disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/gic2.pdf aquí]. La revisión es el miércoles después de clase, a partir de las 17h30 --[[Usuario:Pneira|Pneira]] 20:41 11 ene 2013 (UTC)

= Unidades didácticas =

A continuación encontrarás las unidades didácticas que forman parte de la asignatura.

== Introducción a los Sistemas Operativos ==

* 1.1. [[Qué es un Sistema Operativo|Qué es un sistema operativo]]
* 1.2. [[Introducción histórica|Breve introducción histórica a los sistemas operativos]]
* 1.3. [[Tipos de Sistemas Operativos|Tipos de sistemas operativos]]

== Fundamentos de Sistemas Operativos ==

* 2.1. [[Organización básica de un ordenador]]
* 2.2. [[Modos de operación de la CPU|Modos de operación de la CPU]]
* 2.3. [[Componentes básicos de un sistema operativo|Componentes básicos de un sistema operativo]]
* 2.4. [[Conceptos básicos|Conceptos básicos]]
* 2.5. [[Llamadas al sistema|Llamadas al sistema]]
* 2.6. [[Ejercicios fundamentos Sistemas Operativos|Ejercicios]]

== Modelos de diseño de Sistemas Operativos ==

* 3.1. [[Modelos de Diseño de Sistemas Operativos|Modelos de diseño de sistemas operativos]]
* 3.2. [[Virtualización]]
* 3.3. [[Ejercicios 3|Ejercicios]]

== Procesos ==
* 4.1. [[Multiprogramación|La multiprogramación]]
* 4.2. [[Estados de los procesos|Estados de los procesos]]
* 4.3. [[Planificador de procesos|El planificador de procesos]]
* 4.4. [[Comportamiento de los procesos|El comportamiento de los procesos según el planificador]]
* 4.5. [[Bloque de control de procesos|El bloque de control del proceso]]
* 4.6. [[Conmutación de procesos|La conmutación de procesos]]
* 4.7. [[Hilos|Hilos]]
* 4.8. [[Ejercicios Procesos|Ejercicios]]

== Planificación de Procesos ==
* 5.1 [[Planificación de procesos|La planificación de procesos]]
* 5.2 [[Índices de evaluación|Índices de evaluación de la planificación de procesos]]
* 5.3 [[Criterios de planificación|Criterios de planificación]]
* 5.4 [[Planificadores de sistemas operativos existentes|Planificadores de sistemas operativos existentes]]
* 5.5 [[Planificación de procesos de tiempo real|La planificación de procesos de tiempo real]]
* 5.6 [[Planificación en sistemas multiprocesadores|La planificación de procesos en sistemas multiprocesadores]]
* 5.7 [[Ejercicios otros aspectos de la planificación|Ejercicios]]
* 5.8 [[Ejercicios planificación de procesos|Ejercicios]]

== Concurrencia de procesos ==

* 6.1 [[Concurrencia de procesos|Concurrencia de procesos]]
* 6.2 [[Mecanismos de sincronización|Control optimista y pesimista de la concurrencia]]
* 6.3 [[Cerrojos|Cerrojos]]
* 6.4 [[Ejercicio de concurrencia de procesos|Ejercicios]]

== Semáforos y comunicación ==

* 7.1 [[Semáforos|Semáforos]]
* 7.2 [[Monitores|Monitores]]
* 7.3 [[Mensajería|Mensajería]]
* 7.4 [[Ejercicios sincronización y comunicación|Ejercicios]]

== Interbloqueo ==

* 8.1 [[Definición de interbloqueo|Definición]]
* 8.2 [[Condiciones para el interbloqueo y estrategias de resolución|Modelado y Estrategias]]
* 8.3 [[Algoritmo para averiguar interbloqueo|Algoritmo del banquero]]
* 8.4 [[Ejercicios]]

== Segmentación y paginación ==

* 9.1 [[Introducción|Introducción]]
* 9.2 [[SO multiprogramables con particiones variables|SO multiprogramables con particiones variables]]
* 9.3 [[Segmentacion|Segmentación]]
* 9.4 [[Paginación|Paginación]]
* 9.5 [[Sistema combinado|Sistema combinado]]
* 9.6 [[Memoria virtual con multiprogramacion|Memoria virtual con multiprogramación]]
* 9.7 [[Ejercicios administración de memoria contigua|Ejercicios (Administración de memoria contigua)]]
* 9.8 [[Ejemplo de segmentación, paginación y combinado|Ejercicios (Segmentación, paginación y sistemas combinados)]]

== Memoria virtual ==

* 10.1 [[Memoria Virtual|Introducción]]
* 10.2 [[Criterios de reemplazo|Criterios de reemplazo]]
* 10.3 [[Ejercicios memoria virtual|Ejercicios]]

== Entrada/Salida ==

* 11.1 [[EstructuraES|Estructura dispositivo E/S]]
* 11.2 [[GestionES|Modos de gestionar dispositivos E/S]]
* 11.3 [[Diseño modular E/S|Diseño modular E/S]]
* 11.4 [[Ejercicios de Entrada/Salida|Ejercicios]]

== Gestión L/E ==

* 12.1 [[Discos Magnéticos|Discos Magnéticos]]
* 12.2 [[MejorasTiempoBusqueda|Mejoras en el tiempo de búsqueda]]
* 12.3 [[Mejoras en la demora de rotación|Mejoras en la demora de rotación]]
* 12.4 [[Tipos de errores en discos magnéticos|Tipos de errores en discos magnéticos]]
* 12.5 [[Ejercicios Gestión L/E|Ejercicios]]

== Administración de archivos ==

* 13.1 [[Introducción en la administración de archivos|Introducción en la administración de archivos]]
* 13.2 [[FAT|FAT]]
* 13.3 [[EXT2 |EXT2]]
* 13.4 [[Ejercicios Administración Ficheros|Ejercicios]]

== Anexo ==

Esta sección contiene información interesante pero que no pertenece al temario de la asignatura.

* Todo lo que siempre has querido saber sobre el protocolo SSH está [[SSH|aquí]].

Sistema combinado

2013-01-13T15:46:19Z

Juarolsal: Añadidas las ventajas y justificación del uso de un sistema híbrido, y un diagrama del funcionamiento de la arquitectura IA32 como ejemplo, extraído de las transparencias

Consiste en combinar la segmentación y la paginación. La idea fundamental consiste en definir segmentos que están compuestos por N páginas. De ahí que reciba el nombre de '''segmentación paginada'''.

Por tanto, cualquier segmento ocupa, como mínimo una página de memoria.

Por una parte, la segmentación proporciona ventajas hacia los procesos: Organización de datos y código, mecanismos de protección, compartición de datos y código, y optimización en el espacio ocupado. Por otra parte, la paginación facilita el uso de la memoria virtual, y genera dispersión en memoria. Además como la paginación es transparente, se puede usar paginación bajo un sistema segmentado sin problema.

Los procesos emplean direcciones lógica de memoria segmentada, que son traducidas a direcciones lógicas páginadas, que a su vez deben de ser traducidas a direcciones físicas. Por tanto, cualquier acceso a memoria supone un total de tres accesos a memoria. Uno para acceder a la tabla de segmentos, otro para acceder a la tabla de páginas y, por último, otro más para acceder a la dirección física. Aquí hay un ejemplo de la arquitectura IA32: <center>
[[Archivo:Arquitecturaia32.jpg]]</center>

Archivo:Arquitecturaia32.jpg

2013-01-13T15:42:43Z

Juarolsal: Imagen de ejemplo del funcionamiento del sistema combinado conocido como arquitectura IA32. Extraída de las transparencias de Sistemas Operativos, del Departamento de Lenguajes y Sistemas Informáticos de la Universidad de Sevilla.

Imagen de ejemplo del funcionamiento del sistema combinado conocido como arquitectura IA32.
Extraída de las transparencias de Sistemas Operativos, del Departamento de Lenguajes y Sistemas Informáticos de la Universidad de Sevilla.

Paginación

2013-01-13T15:38:58Z

Juarolsal: Correcciones ortográficas, frases reescritas, detallado funcionamiento de dispositivos traductores sin tabla de páginas, añadida tabla de páginas para todo el sistema, reescrita elementos de administ.

Segmentación

2013-01-13T15:29:14Z

Juarolsal: Añadidas formas de uso de descriptores, reordenado, adaptado al temario actual

SO multiprogramables con particiones variables

2013-01-13T15:04:16Z

Juarolsal: Cambios en listas de control, y frases reescritas

Condiciones para el interbloqueo y estrategias de resolución

2013-01-13T14:53:55Z

Juarolsal: Corrección de una falta ortográfica

== Condiciones para que se produzca interbloqueo ==

Según [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman], para que se pueda producir un interbloqueo se tienen que dar las siguientes cuatro condiciones:

* '''Exclusión mutua''': cada recurso está asignado a un único proceso de manera exclusiva.
* '''Retención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos y esperar a que se le asignen sin liberar antes alguno de los recursos que ya tenia asignados.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita. Ni siquiera el sistema operativo puede expropiárselo.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

* Omisión
* Detección y recuperación
* Prevención
* Predicción

Que se detallan a continuación.

=== Omisión ===

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

=== Detección y Recuperación ===

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

* ''Grafo de relación recursos-procesos'': Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución. Esta técnica se basa en recorrer el grafo yendo de un nodo a otro, por lo que si se consigue volver al nodo de partida estaremos en un recorrido circular. Para que este tipo de error sea detectado usamos algoritmos de detección, se lanzan cuando se solicita un recurso ocupado, es decir, hay una nueva arista dentro de nuestro grafo y debemos comprobar que no da lugar a un recorrido cíclico.

Un ejemplo de grafo en el que se detecta un ciclo es el siguiente:

[[Archivo:deteccion_ciclo.png]]

* ''Matrices de relación recursos-procesos'': Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución. Se distinguen dos tipos, el '''método mediante matrices binarias de relación''', y el '''método de detección matricial''':

-''Matrices binarias de relación:''
Una matriz binaria de relación es aquella que representa una relación R entre dos conjuntos, en la cual el primero de estos dos tiene múltiples asignaciones a elementos del segundo.

El método consiste en, aplicando matrices binarias de relación, utilizar el cierre transitivo para determinar si algún proceso está relacionado consigo mismo a través de otros, señalando así la existencia de ciclos. El procedimiento sería:

1.- Formar la matriz de espera (W: P->R): Los procesos P están a la espera de recursos R.

2.- Formar la matriz de asignación (A: R->P): Los recursos R están asignados a procesos P.

3.- Formar la matriz de procesos a la espera de procesos (T: WxA): Producto cartesiano de ambas matrices.

4.- Hallar el cierre transitivo de la matriz T: Que se puede obtener, por ejemplo, aplicando el Algoritmo de Warshall (algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución). El algoritmo es el siguiente:

Warshall(T, n){
for (k=1 to n){
for (i=1 to n){
for (j=1 to n){
Tij = Tij ⋁ (Tik ⋀ Tkj)
}
}
}
}

Donde n es la dimensión de la matriz T

5.- Si hay procesos que tengan un 1 en la diagonal principal, forman parte de algún ciclo.

Se trata de un método fácil de implementar, ya que solo se realizan operaciones con matrices y bucles, algo muy sencillo para una máquina. Sim embargo, tiene dos inconvenientes:+
* El número de operaciones a realizar es muy alto teniendo en cuenta el tamaño que pueden alcanzar las matrices de recursos
* Solo se puede usar cuandosolo existe una instancia de cada recurso

-''Detección matricial'':
Método matricial que trata aquellos casos en los que hay múltiples instancias equivalentes de un mismo tipo de recurso. Aísla grupos de procesos que no pueden proseguir la ejecución porque no pueden ver satisfechas sus peticiones pendientes.
Usan un método iterativo que:

1.-Marca procesos cuyas peticiones puedan satisfacerse con el actual vector de recursos disponibles.

2.-Suma al vector de disponibles los recursos asignados a los procesos marcados.

3.-Si todos los procesos están marcados: no hay interbloqueo.

4.-Si en una iteración no se marcan procesos: los procesos que quedan están interbloqueados.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

* ''Eliminación'': El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho proceso, si no es suficiente se eliminarán procesos hasta que se rompa el ciclo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos.Sin embargo, de una manera u otra el trabajo realizado por el proceso se pierde, algo que en algunos casos resulta inadmisible, como en sistemas en tiempo real. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales. Aplicar el criterio de selección y eliminar procesos cuando el número de procesos es relativamente bajo puede solucionar el interbloqueo, pero si se da un bloqueo de por ejemplo, centenares de procesos, es una situación prácticamente inmanejable.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso (durante el tiempo necesario) para deshacer el interbloqueo(hemos de asegurarnos de que el proceso no se desbloquea al romperse el interbloqueo). Por ejemplo, supongamos que el recurso es una impresora: podríamos retirarle la asignación a un proceso P1 cuando este terminase de imprimir una página, asignarle la impresora a otro proceso P2 y volver a asignársela a P1 cuando P2 haya terminado su ejecución. El problema es que este método solo es posible dependiendo de la naturaleza del proceso. Con frecuencia es imposible recuperarse de esta manera ya que los recursos no pueden ser apropiados.

* ''Puntos de conformidad'',''sincronismo'' o ''checkpoints'': Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar, y no todos los recursos permiten almacenar y recuperar su estado. Además, puede darse el caso de que el estado del proceso sea externo al sistema (Como en el caso de una conexión a Base de Datos

=== Prevención ===

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman] estableció como interbloqueo. Dichas estrategias son:

* ''Supresión de exclusión mutua'': Un proceso no puede tener acceso exclusivo a un recurso. No siempre es posible, y puede que lo único que haga sea cambiar el problema de sitio. Es una solución drástica, inviable. Por ejemplo, permitir que dos procesos usaran a la vez una impresora sería caótico.
* ''Supresión de retención y espera'' (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos. El aprovechamiento de recursos puede mejorarse mediante una programación más elaborada, dividiendo la ejecución del proceso en distintas fases y gestionando los recursos para cada una de ellas. Sin embargo, muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse.
* ''Supresión de no apropiación'' (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones.
* ''Supresión de espera circular'' (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos. De esta manera, se ordenan los procesos y se solicitan en ese orden. Por ejemplo: tenemos un proceso A y otro B, de manera que ambos hacen uso de los recursos X e Y. En el siguiente caso, no pedirían los recursos en el mismo orden:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(Y)
|-
| down(Y)||down(X)
|-
| …||…
|-
| up(Y)||up(X)
|-
| up(X)||up(Y)
|}

Si se ejecuta la instrucción down(X) de A, se conmuta a B y se ejecuta down(Y), se producirá un interbloqueo, ya que ambos estarán esperando a que el otro libere el recurso que necesitan.
Sin embargo, si pedimos los recursos siempre en el mismo orden de la siguiente forma:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(X)
|-
| down(Y)||down(Y)
|-
| …||…
|-
| up(Y)||up(Y)
|-
| up(X)||up(X)
|-
|
|}

Se puede comprobar que es imposible que se de un interbloqueo como en el caso anterior, ocurriendo lo mismo con cualquier número de procesos y recursos.

El principal inconveniente radica en que a veces, debido a la variedad y al número de recursos y procesos, es imposible encontrar un orden que satisfaga a todos los procesos.

=== Predicción ===

El sistema operativo observa la evolución que siguen los procesos, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que suceda, adopta una trayectoria de ejecución nueva para los procesos involucrados de manera que se garantice que no va a suceder un interbloqueo.

Archivo:GrafoDeadlock.jpg

2013-01-13T14:47:33Z

Juarolsal: subió una nueva versión de «Archivo:GrafoDeadlock.jpg»: Mejorada la calidad de la imagen, conservando el formato.

Página Principal

2012-12-16T20:20:55Z

Juarolsal: Detallado el tipo de ejercicios en la categoría segmentación y paginación (Había dos entradas con el mismo nombre)

Bienvenido al wiki de la asignatura de Sistemas Operativos del departamento de Lenguajes y Sistemas Informáticos de la Universidad de Sevilla. ¡Contribuye!

= Novedades y noticias =

* Comienza el curso 2012/2013 --[[Usuario:Pneira|Pneira]] 15:01 28 sep 2012 (UTC)
* Primer control de evaluación continua del grupo GC2 el viernes 9 de noviembre --[[Usuario:Pneira|Pneira]] 16:47 26 oct 2012 (UTC)
* Segundo control de evaluación continua del grupo GC2 el viernes 14 de diciembre --[[Usuario:Pneira|Pneira]] 16:13 28 nov 2012 (UTC)
* Tercer control de evaluación continua del grupo GC2 el viernes 21 de diciembre --[[Usuario:Pneira|Pneira]] 15:10 12 dic 2012 (UTC)

= Unidades didácticas =

A continuación encontrarás las unidades didácticas que forman parte de la asignatura.

== Introducción a los Sistemas Operativos ==

* 1.1. [[Qué es un Sistema Operativo|Qué es un sistema operativo]]
* 1.2. [[Introducción histórica|Breve introducción histórica a los sistemas operativos]]
* 1.3. [[Tipos de Sistemas Operativos|Tipos de sistemas operativos]]

== Fundamentos de Sistemas Operativos ==

* 2.1. [[Organización básica de un ordenador]]
* 2.2. [[Modos de operación de la CPU|Modos de operación de la CPU]]
* 2.3. [[Componentes básicos de un sistema operativo|Componentes básicos de un sistema operativo]]
* 2.4. [[Conceptos básicos|Conceptos básicos]]
* 2.5. [[Llamadas al sistema|Llamadas al sistema]]
* 2.6. [[Ejercicios fundamentos Sistemas Operativos|Ejercicios]]

== Modelos de diseño de Sistemas Operativos ==

* 3.1. [[Modelos de Diseño de Sistemas Operativos|Modelos de diseño de sistemas operativos]]
* 3.2. [[Virtualización]]
* 3.3. [[Ejercicios 3|Ejercicios]]

== Procesos ==
* 4.1. [[Multiprogramación|La multiprogramación]]
* 4.2. [[Estados de los procesos|Estados de los procesos]]
* 4.3. [[Planificador de procesos|El planificador de procesos]]
* 4.4. [[Comportamiento de los procesos|El comportamiento de los procesos según el planificador]]
* 4.5. [[Bloque de control de procesos|El bloque de control del proceso]]
* 4.6. [[Conmutación de procesos|La conmutación de procesos]]
* 4.7. [[Hilos|Hilos]]
* 4.8. [[Ejercicios Procesos|Ejercicios]]

== Planificación de Procesos ==
* 5.1 [[Planificación de procesos|La planificación de procesos]]
* 5.2 [[Índices de evaluación|Índices de evaluación de la planificación de procesos]]
* 5.3 [[Criterios de planificación|Criterios de planificación]]
* 5.4 [[Planificadores de sistemas operativos existentes|Planificadores de sistemas operativos existentes]]
* 5.5 [[Planificación de procesos de tiempo real|La planificación de procesos de tiempo real]]
* 5.6 [[Planificación en sistemas multiprocesadores|La planificación de procesos en sistemas multiprocesadores]]
* 5.7 [[Ejercicios otros aspectos de la planificación|Ejercicios]]
* 5.8 [[Ejercicios planificación de procesos|Ejercicios]]

== Concurrencia de procesos ==

* 6.1 [[Concurrencia de procesos|Concurrencia de procesos]]
* 6.2 [[Mecanismos de sincronización|Control optimista y pesimista de la concurrencia]]
* 6.3 [[Cerrojos|Cerrojos]]
* 6.4 [[Ejercicio de concurrencia de procesos|Ejercicios]]

== Semáforos y comunicación ==

* 7.1 [[Semáforos|Semáforos]]
* 7.2 [[Monitores|Monitores]]
* 7.3 [[Mensajería|Mensajería]]
* 7.4 [[Ejercicios sincronización y comunicación|Ejercicios]]

== Interbloqueo ==

* 8.1 [[Definición de interbloqueo|Definición]]
* 8.2 [[Condiciones para el interbloqueo y estrategias de resolución|Modelado y Estrategias]]
* 8.3 [[Algoritmo para averiguar interbloqueo|Algoritmo del banquero]]
* 8.4 [[Ejercicios]]

== Segmentación y paginación ==

* 9.1 [[Introducción|Introducción]]
* 9.2 [[SO multiprogramables con particiones variables|SO multiprogramables con particiones variables]]
* 9.3 [[Segmentacion|Segmentación]]
* 9.4 [[Paginación|Paginación]]
* 9.5 [[Sistema combinado|Sistema combinado]]
* 9.6 [[Ejercicios administración de memoria contigua|Ejercicios (Administración de memoria contigua)]]
* 9.7 [[Ejemplo de segmentación, paginación y combinado|Ejercicios (Segmentación, paginación y sistemas combinados)]]

== Memoria virtual ==

* 10.1 [[Memoria Virtual|Introducción]]
* 10.2 [[Criterios de reemplazo|Criterios de reemplazo]]
* 10.3 [[Ejercicios memoria virtual|Ejercicios]]

== Entrada/Salida ==

* 11.1 [[EstructuraES|Estructura dispositivo E/S]]
* 11.2 [[GestionES|Modos de gestionar dispositivos E/S]]
* 11.3 [[Diseño modular E/S|Diseño modular E/S]]
* 11.4 [[Ejercicios de Entrada/Salida|Ejercicios]]

== Gestión L/E ==

* 12.1 [[Discos Magnéticos|Discos Magnéticos]]
* 12.2 [[MejorasTiempoBusqueda|Mejoras en el tiempo de búsqueda]]
* 12.3 [[Mejoras en la demora de rotación|Mejoras en la demora de rotación]]
* 12.4 [[Tipos de errores en discos magnéticos|Tipos de errores en discos magnéticos]]
* 12.5 [[Ejercicios Gestión L/E|Ejercicios]]

== Administración de archivos ==

* 13.1 [[Introducción en la administración de archivos|Introducción en la administración de archivos]]
* 13.2 [[FAT|FAT]]
* 13.3 [[EXT2 |EXT2]]
* 13.4 [[Ejercicios Administración Ficheros|Ejercicios]]

== Anexo ==

Esta sección contiene información interesante pero que no pertenece al temario de la asignatura.

* Todo lo que siempre has querido saber sobre el protocolo SSH está [[SSH|aquí]].

Condiciones para el interbloqueo y estrategias de resolución

2012-12-10T17:27:26Z

Juarolsal: Corregidos dos errores menores de sintáxis

== Condiciones para que se produzca interbloqueo ==

Según [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman], para que se pueda producir un interbloqueo se tienen que dar las siguientes cuatro condiciones:

* '''Exclusión mutua''': cada recurso está asignado a un único proceso de manera exclusiva.
* '''Retención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos y esperar a que se le asignen sin liberar antes alguno de los recursos que ya tenia asignados.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita. Ni siquiera el sistema operativo puede expropiárselo.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

* Omisión
* Detección y recuperación
* Prevención
* Predicción

Que se detallan a continuación.

=== Omisión ===

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

=== Detección y Recuperación ===

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

* ''Grafo de relación recursos-procesos'': Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.Esta técnica se basa en recorrer el grafo yendo de un nodo a otro, por lo que si se consigue volver al nodo de partida estaremos en un recorrido circular. Para que este tipo de error sea detectado usamos algoritmos de detección, se lanzan cuando se solicita un recurso ocupado, es decir, hay una nueva arista dentro de nuestro grafo y debemos comprobar que no da lugar a un recorrido cíclico.

Un ejemplo de grafo en el que se detecta un ciclo es el siguiente:

[[Archivo:deteccion_ciclo.png]]

* ''Matrices de relación recursos-procesos'': Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución. Se distinguen dos tipos, el '''método mediante matrices binarias de relación''', y el '''método de detección matricial''':

-''Matrices binarias de relación:''
Una matriz binaria de relación es aquella que representa una relación R entre dos conjuntos, en la cual el primero de estos dos tiene múltiples asignaciones a elementos del segundo.

El método consiste en, aplicando matrices binarias de relación, utilizar el cierre transitivo para determinar si algún proceso está relacionado consigo mismo a través de otros, señalando así la existencia de ciclos. El procedimiento sería:

1.- Formar la matriz de espera (W: P->R): Los procesos P están a la espera de recursos R.

2.- Formar la matriz de asignación (A: R->P): Los recursos R están asignados a procesos P.

3.- Formar la matriz de procesos a la espera de procesos (T: WxA): Producto cartesiano de ambas matrices.

4.- Hallar el cierre transitivo de la matriz T: Que se puede obtener, por ejemplo, aplicando el Algoritmo de Warshall (algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución). El algoritmo es el siguiente:

Warshall(T, n){
for (k=1 to n){
for (i=1 to n){
for (j=1 to n){
Tij = Tij ⋁ (Tik ⋀ Tkj)
}
}
}
}

Donde n es la dimensión de la matriz T

5.- Si hay procesos que tengan un 1 en la diagonal principal, forman parte de algún ciclo.

Se trata de un método fácil de implementar, ya que solo se realizan operaciones con matrices y bucles, algo muy sencillo para una máquina. Sim embargo, tiene dos inconvenientes:+
* El número de operaciones a realizar es muy alto teniendo en cuenta el tamaño que pueden alcanzar las matrices de recursos
* Solo se puede usar cuandosolo existe una instancia de cada recurso

-''Detección matricial'':
Método matricial que trata aquellos casos en los que hay múltiples instancias equivalentes de un mismo tipo de recurso. Aísla grupos de procesos que no pueden proseguir la ejecución porque no pueden ver satisfechas sus peticiones pendientes.
Usan un método iterativo que:

1.-Marca procesos cuyas peticiones puedan satisfacerse con el actual vector de recursos disponibles.

2.-Suma al vector de disponibles los recursos asignados a los procesos marcados.

3.-Si todos los procesos están marcados: no hay interbloqueo.

4.-Si en una iteración no se marcan procesos: los procesos que quedan están interbloqueados.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

* ''Eliminación'': El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho proceso, si no es suficiente se eliminarán procesos hasta que se rompa el ciclo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos.Sin embargo, de una manera u otra el trabajo realizado por el proceso se pierde, algo que en algunos casos resulta inadmisible, como en sistemas en tiempo real. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales. Aplicar el criterio de selección y eliminar procesos cuando el número de procesos es relativamente bajo puede solucionar el interbloqueo, pero si se da un bloqueo de por ejemplo, centenares de procesos, es una situación prácticamente inmanejable.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso (durante el tiempo necesario) para deshacer el interbloqueo(hemos de asegurarnos de que el proceso no se desbloquea al romperse el interbloqueo). Por ejemplo, supongamos que el recurso es una impresora: podríamos retirarle la asignación a un proceso P1 cuando este terminase de imprimir una página, asignarle la impresora a otro proceso P2 y volver a asignársela a P1 cuando P2 haya terminado su ejecución. El problema es que este método solo es posible dependiendo de la naturaleza del proceso. Con frecuencia es imposible recuperarse de esta manera ya que los recursos no pueden ser apropiados.

* ''Puntos de conformidad'',''sincronismo'' o ''checkpoints'': Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar, y no todos los recursos permiten almacenar y recuperar su estado. Además, puede darse el caso de que el estado del proceso sea externo al sistema (Como en el caso de una conexión a Base de Datos

=== Prevención ===

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman] estableció como interbloqueo. Dichas estrategias son:

* ''Supresión de exclusión mutua'': Un proceso no puede tener acceso exclusivo a un recurso. No siempre es posible, y puede que lo único que haga sea cambiar el problema de sitio. Es una solución drástica, inviable. Por ejemplo, permitir que dos procesos usaran a la vez una impresora sería caótico.
* ''Supresión de retención y espera'' (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos. El aprovechamiento de recursos puede mejorarse mediante una programación más elaborada, dividiendo la ejecución del proceso en distintas fases y gestionando los recursos para cada una de ellas. Sin embargo, muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse.
* ''Supresión de no apropiación'' (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones.
* ''Supresión de espera circular'' (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos. De esta manera, se ordenan los procesos y se solicitan en ese orden. Por ejemplo: tenemos un proceso A y otro B, de manera que ambos hacen uso de los recursos X e Y. En el siguiente caso, no pedirían los recursos en el mismo orden:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(Y)
|-
| down(Y)||down(X)
|-
| …||…
|-
| up(Y)||up(X)
|-
| up(X)||up(Y)
|}

Si se ejecuta la instrucción down(X) de A, se conmuta a B y se ejecuta down(Y), se producirá un interbloqueo, ya que ambos estarán esperando a que el otro libere el recurso que necesitan.
Sin embargo, si pedimos los recursos siempre en el mismo orden de la siguiente forma:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(X)
|-
| down(Y)||down(Y)
|-
| …||…
|-
| up(Y)||up(Y)
|-
| up(X)||up(X)
|-
|
|}

Se puede comprobar que es imposible que se de un interbloqueo como en el caso anterior, ocurriendo lo mismo con cualquier número de procesos y recursos.

El principal inconveniente radica en que a veces, debido a la variedad y al número de recursos y procesos, es imposible encontrar un orden que satisfaga a todos los procesos.

=== Predicción ===

El sistema operativo observa la evolución que siguen los procesos, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que suceda, adopta una trayectoria de ejecución nueva para los procesos involucrados de manera que se garantice que no va a suceder un interbloqueo.