ALGORITMOS

Un algoritmo es un método para resolver un problema. Aunque la popularización del término ha llegado con el advenimiento de la era informática, algoritmo proviene de Mohammed al-Khowârizmi, matemático persa que vivió durante el siglo IX y alcanzó gran reputación por el enunciado de las reglas paso a paso para sumar, restar, multiplicar y dividir números decimales; la traducción al latín del apellido en la palabra algorismus derivó posteriormente en algoritmo. Euclides, el gran matemático griego (del siglo IV antes de Cristo) que inventó un método para encontrar el máximo común divisor de dos números, se considera con Al-Khowârizmi el otro gran padre de la algoritmia (ciencia que trata de los algoritmos).

Los pasos para la resolución de un problema son:

1. Diseño del algoritmo, que describe la secuencia ordenada de pasos —sin ambigüedades— que conducen a la solución de un problema dado. (Análisis del problema y desarrollo del algoritmo.)

2. Expresar el algoritmo como un programa en un lenguaje de programación adecuado. (Fase de codificación.)

3. Ejecución y validación del programa por la computadora.

Para llegar a la realización de un programa es necesario el diseño previo de un algoritmo, de modo que sin algoritmo no puede existir un programa.

Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que los ejecuta. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siempre el mismo. Así, por ejemplo, en una analogía con la vida diaria, una receta de un plato de cocina se puede expresar en español, inglés o francés, pero cualquiera que sea el lenguaje, los pasos para la elaboración del plato se realizarán sin importar el idioma del cocinero.

En la ciencia de la computación y en la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan sólo un medio para expresar un algoritmo y una computadora es sólo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectúe el proceso correspondiente.

El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación. En esencia, la solución de un problema se puede expresar mediante un algoritmo.

La definición de un algoritmo debe describir tres partes: Entrada, Proceso y Salida. En el algoritmo de receta de cocina citado anteriormente se tendrá:

·       Entrada: ingredientes y utensilios empleados.

·       Proceso: elaboración de la receta en la cocina.

·       Salida: terminación del plato (por ejemplo, cordero).

Ejemplo 1.1

Un cliente ejecuta un pedido a una fábrica. La fábrica examina en su banco de datos la ficha del cliente; si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario, rechazará el pedido.

Redactar el algoritmo correspondiente.

Los pasos del algoritmo son:

     1.      Inicio.
     2.     Leer el pedido.
     3.     Examinar la ficha del cliente.
     4.    Si el cliente es solvente, aceptar pedido; en caso contrario, rechazar
     5.      pedido.
     6.     Fin.

Ver ejemplo y programarlo

https://www.dropbox.com/s/qivgh6r2d0s547m/CLASE.pdf?dl=0

https://www.dropbox.com/s/qptzv559hv93mgs/PROGRAMA.txt?dl=0

Paginación y Segmentación

Los sistemas cuentan con gran capacidad de memoria, pero no es suficiente debido a que las aplicaciones actuales demandan la utilización de altos índices de memoria, generando la escasez de la misma.

Los sistemas operativos cuentan con un administrador de memoria, que es el encargado de llevar un registro acerca de las partes de la memoria que están siendo utilizadas y aquellas que no, con el objetivo de asignar espacio de memorias a los procesos cuando lo necesiten y liberarlas cuando el proceso haya finalizado. 

Es así que los administradores de memoria utilizan diferentes técnicas para el manejo de la memoria, las más conocidas son la paginación y segmentación. Se utilizan estas técnicas con el fin de tener la mayor cantidad posible de memoria que requiera cada proceso, que sea la que necesita ni más pequeña ni más grande.

PAGINACIÓN

 

Es una técnica de manejo de memoria, en la cual el espacio de memoria se divide en secciones físicas de igual tamaño, denominadas marcos de página. Los programas se dividen en unidades lógicas, denominadas páginas, que tienen el mismo tamaño que los marcos de páginas. De esta forma, se puede cargar una página de información en cualquier marco de página. 

Las páginas sirven como unidad de almacenamiento de información y de transferencia entre memoria principal y memoria auxiliar o secundaria. Cada marco se identifica por la dirección de marco, que está en la posición física de la primera palabra en el marco de página.

SEGMENTACIÓN

Otro modo de subdividir el programa es la segmentación. En este caso, el programa y sus datos asociados se dividen en un conjunto de segmentos. No es necesario que todos los segmentos de todos los programas tengan la misma longitud, aunque existe una longitud máxima de segmento. Como en la paginación, una dirección lógica segmentada consta de dos partes, en este caso un número de segmento y desplazamiento. 

Como consecuencia del empleo de segmentos de distintos tamaños, la segmentación resulta similar a la partición dinámica. En ausencia de un esquema de superposición o del uso de memoria virtual, sería necesario cargar en la memoria todos los segmentos de un programa para su ejecución.

La diferencia, en comparación con la partición dinámica, radica en que, con segmentación, un programa puede ocupar más de una partición.

Mientras que la paginación es transparente al programador, la segmentación generalmente es visible y se ofrece como la ventaja para la organización de los programas y datos. 

Normalmente el programador o el compilador asignan los programas y los datos a diferentes segmentos. Para facilitar la programación modular, el programa o los datos pueden ser divididos de nuevo en diferentes segmentos.

Memoria - técnicas de Administración

PARTICIONES ESTÁTICAS

ASIGNACIÓN DE MEMORIA CON PARTICIONES ESTÁTICAS

Con particiones estáticas surgen dos dificultades:

• Un programa puede ser demasiado grande para caber en una partición, por lo tanto si el programa no se ha diseñado mediante superposición, simplemente no se puede ejecutar. De otro modo, podrían estar en memoria aquellos módulos del programa que se necesiten, pero se requeriría que estos módulos sean intercambiados a medida que la ejecución progresa.
• Se malgasta el espacio interno a cada partición cuando el bloque cargado es más pequeño, lo que se conoce como fragmentación interna. Es decir, cualquier proceso por pequeño que sea, ocuparía una partición completa.

ASIGNACIÓN DE MEMORIA CON PARTICIONES ESTÁTICAS

En este ejemplo, partimos de la memoria libre completamente en (a), luego se cargan "P1" [20 MB], (b), "P2" [14 MB] (c) y "P3" [18 MB] (d). Se libera "P2" (e) y se carga "P4" [8 MB] (f), se libera "P1" (g) y se carga nuevamente "P2" [14 MB] (h). Notemos como se van reestructurando las particiones en base al tamaño de los procesos que se van cargando, esto sucede por ser particiones dinámicas.

La asignación de memoria en un esquema con particiones dinámicas, consiste en determinar en qué hueco ubicar un nuevo proceso. Para esto existen tres algoritmos: mejor ajuste, primer ajuste o próximo ajuste.

• Mejor ajuste: consiste en ubicar el proceso en el espacio de memoria que más se ajuste a su tamaño.
• Primer ajuste: consiste en ubicar el proceso en el primer hueco disponible, recorriendo desde el inicio de la memoria, cuyo tamaño sea suficiente para el proceso.
• Próximo ajuste: consiste en ubicar el siguiente hueco disponible, que sea suficientemente grande, a partir de la última asignación de memoria.

Con particiones dinámicas surgen las siguientes dificultades:

• Producto de la entrada y salida de procesos en la memoria, se van generando porciones cada vez más pequeñas de la memoria sin utilizar, lo que se conoce como fragmentación externa.
• Para solucionar este problema se debe recurrir a la compactación de la memoria de manera de eliminar los espacios (huecos) entre procesos. Esto significa que los procesos deben ser reubicados en memoria en forma dinámica.

Memoria - Administración

La memoria es un recurso importante que debe ser cuidadosamente gestionado. A todo programador le gustaría poder contar con una memoria infinitamente grande, infinitamente rápida y que fuese además no volátil, esto es, que no perdiese su contenido en ausencia de energía eléctrica. Pero al no poder contar con algunas de estas caracteristicas han surgido técnicas y algoritmos capaces de administrar de una forma óptima la memoria de nuestra computadora.
¿Qué es la Administración de Memoria?
Es una tarea realizada por el sistema operativo que consiste en gestionar la jerarquía de memoria, en cargar y descargar procesos en memoria principal para que sean ejecutados. Para ello el sistema operativo gestiona lo que se conoce como MMU o Unidad de Administración de Memoria, el cual es un dispositivo hardware que transforma las direcciones lógicas en físicas.
Su trabajo es seguir la pista de qué partes de la memoria están en uso y cuáles no lo están, con el fin de poder asignar memoria a los procesos cuando la necesiten, y recuperar esa memoria cuando dejen de necesitarla, así como gestionar el intercambio entre memoria principal y el disco cuando la memoria principal resulte demasiado pequeña para contener a todos los procesos.

OBJETIVOS DE LA GESTIÓN DE MEMORIA
Ofrecer a cada proceso un espacio lógico propio.
Proporcionar protección entre los procesos.
Permitir que los procesos compartan memoria.
Maximizar el rendimiento del sistema.

REQUISITOS
Reubicación: En un sistema multiprogramado la memoria se encuentra compartida por varios procesos, por lo tanto, los procesos deben ser cargados y descargados de memoria.
Protección: En un sistema con multiprogramación es necesario proteger al sistema operativo y a los otros procesos de posibles accesos que se puedan realizar a sus espacios de direcciones.
Compartición: En ciertas situaciones, bajo la supervisión y control del sistema operativo, puede ser provechoso que los procesos puedan compartir memoria.

Organización Lógica: Tanto la memoria principal como la secundaria presentan una organización física similar, como un espacio de direcciones lineal y unidimensional. Debe existir una cierta correspondencia entre el sistema operativo y el hardware al tratar los datos y los programas de los usuarios de acuerdo a la estructura lógica que ellos presenten.
Organización Física: Debe ser parte de la administración de memoria, la organización del flujo de información entre la memoria principal y la memoria secundaria.

Hilos

Un hilo en un sistema operativo es la caracterictica que permite a una aplicacion realizar varias tareas a la vez concurrentemente, los distintos hilos de ejecucion comparten una serie de recursos tales como el espacio de memoria, los archivos abiertos, situacion de autentificacion. Esta accion permite simplificar el diseño de una aplicacion que debe llevar a cabo distintas funciones simultaneamente.

Los hilos son básicamente una tarea que puede ser ejecutada en paralelo con otra tarea; teniendo en cuenta lo que es propio de cada hilo es el contador de programa, la pila de ejecucion y el estado de la CPU (incluyendo el valor de los registros).

En muchos de los sistemas operativos que dan facilidades a los hilos, es más rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro. Este fenómeno se debe a que los hilos comparten datos y espacios de direcciones, mientras que los procesos, al ser independientes, no lo hacen.

Los hilos presentan estados, los principales de ellos son: Ejecución, Listo y Bloqueado. No tiene sentido asociar estados de suspensión de hilos ya que es un concepto de proceso. En todo caso, si un proceso está expulsado de la memoria principal (ram), todos sus hilos deberán estarlo ya que todos comparten el espacio de direcciones del proceso.

Un ejemplo de aplicación que podría hacer uso de hilos es un servidor, como puede ser un servidor de archivos de una red de área local. Cada vez que llegue una solicitud de un nuevo archivo, se puede generar un nuevo hilo para el programa de gestión de archivos. Puesto que el servidor debe manejar muchas solicitudes, se crearan y destruirán muchos hilos en un corto periodo de tiempo. Si el servidor es un multiprocesador, se pueden ejecutar varios hilos de una misma tarea simultáneamente y en diferentes procesadores. Los hilos son también útiles en los monoprocesadores para simplificar la estructura de los programas que lleven a cabo diversas funciones.


VEAMOS ALGUNAS DIFERENCIAS ENTRE PROCESOS E HILOS

Procesos

El concepto central en un sistema operativo es la idea de proceso.
Ojo: un proceso no tiene por qué estar siempre en ejecución. La vida de un proceso pasa por varias fases, incluyendo la ejecución.

Una analogía: receta de un pastel (el programa), ingredientes (los datos), cocinero (la CPU), la mesa de cocina (la memoria), cada pastel (un proceso), el horno (un dispositivo E/S).

¡Nuestro chef puede tener varios pasteles a medio hacer!

Concurrencia: su ejecución parece simultánea pero, en realidad, la CPU salta de uno a otro (como nuestro sufrido cocinero). Es lo que llamamos sistema operativo multitarea.
Mientras ejecuta un proceso, el otro está en espera.
Cuando hay varias CPUs podemos tener ejecución paralela. Pero cada CPU sólo puede ejecutar un proceso a la vez. Normalmente número de procesos > número de CPUs.

Tipos de procesos
Podemos clasificarlos en función de distintos criterios.

Según su diseño:

Reutilizables: se cargan en memoria cada vez que se usan. Los programas de usuario suelen ser de este tipo.
Reentrantes: se carga una sola copia del código en memoria. Cada vez que se usan se crea un nuevo proceso con su zona de datos propia, pero compartiendo el código.


Según su acceso a CPU y recursos:

Apropiativos: acceden a los recursos y sólo los abandonan de forma voluntaria (mediante instrucción CPU).
No apropiativos: permiten a otros procesos apropiarse de los recursos que ahora poseen.

Los procesos pueden ser cooperantes o independientes, en el primer caso se entiende que los procesos interactúan entre sí y pertenecen a una misma aplicación. En el caso de procesos independientes en general se debe a que no interactúan y un proceso no requiere información de otros o bien porque son procesos que pertenecen a distintos usuarios.


Estados de los procesos

Un proceso puede estar en cualquiera de los siguientes tres estados: Listo, En ejecución y Bloqueado. Los procesos en el estado listo son los que pueden pasar a estado de ejecución si el planificador los selecciona. Los procesos en el estado ejecución son los que se están ejecutando en el procesador en ese momento dado. Los procesos que se encuentran en estado bloqueado están esperando la respuesta de algún otro proceso para poder continuar con su ejecución. Por ejemplo operación de E/S.

Semáforos

Un semáforo es una estructura diseñada para sincronizar dos o más threads o procesos, de modo que su ejecución se realice de forma ordenada y sin conflictos entre ellos.

El por qué no se pueden usar directamente otras estructuras mas clásicas, como por ejemplo usar una variable común para decidir si se puede o no acceder a un recurso, se debe a que estamos en un sistema multitarea: hacer esto implicaría realizar una espera activa (un bucle, comprobando constantemente si la variable está o no a 0, y así saber si podemos seguir ejecutando o no). Por otro lado, puede ocurrir algo mucho peor: supongamos que un proceso comprueba la variable, y ve que el recurso está libre, por lo que procedería a cambiar dicha variable de valor y seguir. Pues bien, si justo después de la comprobacion pero antes de que cambie el valor se conmuta de tarea (puede pasar, pues el sistema operativo puede hacerlo en cualquier momento), y el nuevo proceso comprueba la variable, como todavía no se ha actualizado, creerá que el recurso está libre, e intentará tomarlo, haciendo que ambos programas fallen. Lo peor del caso es que se tratará de un error aleatorio: unas veces fallará (cuando se produzca cambio de tarea en ese punto) y otras no.
Para evitarlo, se idearon los semáforos. Un semáforo básico es una estructura formada por una posición de memoria y dos instrucciones, una para reservarlo y otra para liberarlo. A esto se le puede añadir una cola de threads para recordar el orden en que se hicieron las peticiones.