hacker


Ingresar con nombre de usuario, contraseña y duración de la sesión
| Portal Hacker | Editorial | Descargas | Ezine |
Inicio Ayuda Ingresar Registrarse
19 de Noviembre de 2008, 03:23:34
Noticias: Reporte de temas
Para ver este enlace Registrate o Inicia Sesion
> Aqui

+  Foros pOrtal Hacker
|-+  Temas de Interés
| |-+  Sistemas Operativos (Moderador: WaesWaes)
| | |-+  Comprendiendo un SO ---> construccion
0 Usuarios y 1 Visitante están viendo este tema. « anterior próximo »
Páginas: 1 [2] 3 4 Ir Abajo Imprimir
Autor Tema: Comprendiendo un SO ---> construccion  (Leído 2637 veces)
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #15 : 13 de Julio de 2008, 04:46:31 »

Modelo de programacion de una computadora

El modelo de programación a bajo nivel de una computadora se caracteriza por los siguientes aspectos:

Elementos de almacenamiento: En esta sección se consideran aquellos elementos de almacenamiento de la computadora que son visibles a las instrucciones maquina. En esta categoría están incluidos los registros generales, el contador de programa, el puntero de pila, el registro de estado, la memoria principal y el mapa de E/S.

Es muy frecuente que las computadoras incluyan el mapa de E/S dentro del mapa de memoria.
En este caso, se reserva una parte del mapa de memoria para realizar la E/S.


Juego de instrucciones con sus correspondient es modos de direccionamien to: El juego de instrucciones máquina define las operaciones que es capaz de hacer la computadora. Los modos de direccionamien to determinan la forma en que se especifica la identidad de los elementos de almacenamiento que intervienen en las instrucciones máquina.

Secuencia de funcionamiento: Define el modo en que se van ejecutando las instrucciones máquina.

• Un aspecto crucial de las computadoras, que está presente en todas ellas menos en los modelos más simples, es que disponen de más de un nivel de ejecución.
« Última modificación: 14 de Julio de 2008, 11:03:15 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #16 : 13 de Julio de 2008, 04:57:17 »

Niveles de ejecucion

La mayoría de las computadoras actuales presentan dos o más niveles de ejecución. En el nivel menos permisivo, generalmente llamado nivel de usuario, la computadora ejecuta solamente un subconjunto de las instrucciones máquina, quedando prohibidas las demás.

Además, el acceso a determinados registros, o a partes de esos registros, y a determinadas zonas del mapa de memoria y de E/S tambien queda prohibido. En el nivel más permisivo, denominado nivel de núcleo, la computadora ejecuta todas sus instrucciones sin ninguna
restricción y permite el acceso a todos los registros y mapas de direcciones.

Se puede decir que la computadora presenta mas de un modelo de programación. Uno más restrictivo, que permite realizar un conjunto limitado de acciones, y otros más permisivos que permiten realizar un mayor conjunto de acciones. Uno o varios bits del registro de estado
establecen el nivel en el que está ejecutando la máquina. Modificando esto. bits se cambia de nivel de ejecución.

Como veremos más adelante, los niveles de ejecución se incluyen en las computadoras para dar soporte al sistema operativo. Los programas de usuario, por razones de seguridad, no podrán realizar determinadas acciones al ejecutar en nivel de usuario. Por su lado, el sistema operativo, que ejecuta en nivel de núcleo, puede ejecutar todo tipo de acciones.
Típicamente, en el nivel de usuario la computadora no permite operaciones de E/S, ni modificar una gran parte del registro de estado, ni modificar los registros de soporte de gestión de memoria.
« Última modificación: 14 de Julio de 2008, 11:07:03 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #17 : 13 de Julio de 2008, 05:00:43 »

El reloj

El término reloj se aplica a las computadoras con tres acepciones diferentes, si bien relacionadas. Estas tres acepciones son las siguientes:

• Señal que gobierna el ritmo de ejecución de las instrucciones máquina.
• Generador de interrupciones periódicas.
• Contador de fecha y hora.

El oscilador que gobierna las fases de ejecución de las instrucciones máquina se denomina reloj. Cuando se dice que un microprocesado r es de 600 MHz, lo que se está especificando es que el oscilador que gobierna el ritmo de su funcionamiento interno produce una onda cuadrada con una frecuencia de 600 MHz.

La señal producida por el oscilador anterior, o por otro oscilador, se divide
mediante un divisor de frecuencia para generar una interrupción cada cierto intervalo de tiempo.

Estas interrupciones, que se están produciendo constantemente, se denominan interrupciones de reloj o ticks, dando lugar al segundo concepto de reloj. El objetivo de estas interrupciones es, hacer que el sistema operativo entre a ejecutar de forma
sistemática cada cierto intervalo de tiempo. De esta manera, el sistema operativo puede evitar que un programa monopolice el uso de la computadora y puede hacer que entren a ejecutarse programas en determinados instantes de tiempo. Estas interrupciones se producen cada varios milisegundos, por ejemplo cada 20 milisegundos.

La tercera acepción de reloj se aplica a un contador que permite conocer la fecha y la hora. Este contador se va incrementando con cada interrupción de reloj de forma que,
tomando como referencia un determinado instante (p. ej: unix toma las 0 hora de 1de enero de 1970), se puede calcular la hora y fecha en que estamos. En las computadoras actuales esta cuenta
se hace mediante un circuito dedicado que, además, está permanentement e alimentado, de forma que, aunque se apague la computadora, se siga manteniendo el reloj.

En sistemas más antiguos,el sistema operativo se encargaba de hacer esta cuenta, por lo que había que introducir la fecha y
la hora al arrancar la computadora.

« Última modificación: 14 de Julio de 2008, 02:05:10 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #18 : 15 de Julio de 2008, 03:09:14 »

Memoria virtual

Debido a que muchas aplicaciones requieren el acceso a más información que la que se puede mantener en memoria física. Enlos sistemas operativos modernos deve surgir el concepto de memoria virtual, que permite al software usar mas memoria principal de la que realmente posee una computadora.

En un sistema operativo sin memoria virtual, lo que el sistema hace es dividir la memoria principal en pedazos y asigna cada pedazo a cada programa que se este ejecutando en un instante determinado.

en la sigiente imagen se ve que pasa en la memoria principal cuando se ejecuta un solo programa y tambien cuando se ejecutan varios a la vez en un mismo instante.



Como pueden observar la distribucion de la memoria en contigua, es todo un espacio junto, no hay distintos espacios disjuntos por la memoria principal para un mismo programa, eso implica a una complicacion, porque al no poder dividir en segmentos la memoria para un mismo programa, si hay unas celdas que interrumpen el espacio que queramos usar no se va a poder ejecutar el programa ya que no estara cargado en la memoria principal.

En el caso de la memoria virtual no es nesesario que existan estas contiguidades, asi que podesmos dividir en segmentos los espacios que usara la memoria fisica para un misma programa sin problemas.

Concepto de Memoria virtual

La memoria virtual utiliza dos niveles de jerarquia de memoria: la memoria principal y una memoria de respaldo que suele ser el HDD o tambien una memoria expandida.
Sobre la memoria de respaldo se establece un mapa uniforme de memoria virtual. Las direcciones generadas por el procesador se refieren a este mapa virtual, pero, sin embargo, los accesos reales se realiza sobre la memoria principal.

Para su funcionamiento, la memoria virtual exige una gestión automática de la parte de la jerarquía de memoria formada por los niveles de memoria principal y de disco (de eta automatizacion se encarga el sistema operativo con ayuda del hardware).


esta gestión incluye toda la memoria principal y una parte del disco, que sirve de respaldo a la memoria
virtual.


Los aspectos principales en los que se basa la memoria virtual son los siguientes:

  • Las direcciones generadas por las instrucciones máquina, tanto para referirse a datos como a otras instrucciones, están referidas al espacio virtual, es decir, forman parte del mapa de memoria virtual. En este sentido se suele decir que el procesador genera direcciones virtuales
  • Las direcciones generadas por las instrucciones máquina, tanto para referirse a datos como a otras instrucciones, están referidas al espacio virtual, es decir, forman parte del mapa de memoria virtual. En este sentido se suele decir que el procesador genera direcciones virtuales
  • Aunque el programa genera direcciones virtuales, para que éste pueda ejecutarse, han de residir en memoria principal las instrucciones y los datos utilizados en cada momento. Si, por ejemplo, un dato referenciado por una instrucción máquina no reside en la memoria principal es necesario realizar un trasvase de información (migración de información) entre el disco y la memoria principal antes de que el programa pueda seguir ejecutando.
  • Los espacios virtual y físico se dividen en páginas. Se denominan páginas virtuales a las páginas del espacio virtual, paginas de intercambio a las páginas residentes en el disco y marcos de página a los espacios en los que se divide la memoria principal.
  • Cada marco de página es capaz de albergar una página virtual cualquiera, sin ninguna restricción de direccionamien to.
  • Existe una unidad hardware, denominada MMU (Memo Management Unit), que traduce las direcciones virtuales a direcciones de memoria principal. Aplicando lo visto anteriormente, se puede decir que esta traducción se restringe a traducir el número de página virtual en el correspondient e número de marco de página.
    Esta traducción hay que hacerla por hardware dada la alta
    velocidad a la que debe hacerse (una fracción del tiempo de acceso de la memoria principal).
  • Dado que en cada instante determinado solamente reside en memoria principal una fracción de las páginas del programa, la traducción no siempre es posible. Por tanto, la MMU producirá una excepción de fallo de página cuando ésta no esté en memoria principal.

Los fallos de página son atendidos por el sistema operativo (o sea los atiende el software) que se encarga de realizar la adecuada migración de páginas, para traer la página requerida por el programa a un marco de página. Se denomina paginación al proceso de migración necesario para atender los fallos de pagina.

El tamaño del espacio virtual suele ser muy grande. En la actualidad se emplean direcciones de 32, 48 o hasta 64 bits, lo que significa
espacios virtuales de 232, 248 y 264 bytes. Dado que los programas requieren en general mucho menos espacio, una de las funciones que realiza el sistema operativo es la asignación de espacio virtual a los programas para su ejecución. El programa no podrá utilizar todo el
espacio virtual sino que ha de restringirse a la zona o zonas que le asigne el sistema operativo.



La figura muestra que el espacio virtual reservado al programa A puede estar en una única zona o puede estar dividido en varias zonas, que se denominan segmentos.


Tabla de paginas

La tabla de páginas es una estructura de información que contiene la información de dónde residen las páginas de un programa en ejecución. Esta tabla permite, por tanto, saber si una página esta en memoria principal y, en su caso, en que marco específico reside.
Según se ha visto anteriormente, dado que el tamaño del espacio virtual suele ser muy grande, el tamaño de la correspondient e tabla de páginas puede ser muy grande (de millones de elementos). Sin embargo, como hemos visto, el sistema operativo se encarga de asignar a cada programa en ejecución un espacio virtual de tamaño ajustado a su: necesidades. De esta forma, la tabla de páginas queda reducida al valor necesario para que ejecute el programa.


La Figura muestra la solución más sencilla de tabla de páginas de un nivel. En este caso se supone que toda la memoria asignada al programa es contigua. El número de la página virtual se utiliza como índice para entrar en la tabla. Cada elemento de la tabla tiene un bit para indicar si la página está en memoria principal y el número de marco en el que se
encuentra la mencionada página o un valor nulo.



La Figura muestra un ejemplo de traducción para el caso de tabla de paginas de un nivel

Se supone que las página son de 2 KB, por lo que los 11 bits inferiores de la
dirección virtual sirven para especificar el byte dentro de la pagina, mientras que el resto especifican la página virtual, que en este caso es la 5. Entrando en la posición N0 5 de la tabla observamos que la página está en memoria principal y que esta en el marco numero 6.738.
Concatenando el número de marco con los 11 bits inferiores de la dirección virtual se obtiene la dirección de memoria principal donde reside la información buscada.
El mayor inconveniente de la tabla de un nivel es su falta de flexibilidad. Toda la memoria virtual asignada ha de ser contigua (El espacio virtual asignado es contiguo, pero no los marcos de pagina que pertenezcan en un momento dado, ya que estaran dispersos por toda la memoria principal) y la ampliación de memoria asignada solamente puede hacerse final de la existente.

Sin embargo, los programas están compuestos por varios elementos, como son el propio programa objeto, la pila y los bloques de datos. Además, tanto la pila como los bloques de datos han de poder crecer. Por ello, un esquema de tabla de un nivel obliga a dejar grandes huecos de memoria virtual sin utilizar , pero que están presentes en la tabla con el consiguiente
desperdicio de espacio.

Por ello se emplean esquemas de tablas de páginas de más de un nivel. Con este tipo de tabla, la memoria asignada esta compuesta por una serie de bloques de memoria virtual, es decir, por unos segmentos.

Cada segmento está formado por una serie contigua de byte. que puede variar su tamaño, siempre y cuando no choque con otro segmento. La dirección se divide en tres partes.

La primera identifica el segmento de memoria donde esta la información que se desea acceder. Con este valor se entra en una subtabla de segmentos, que contiene un puntero por segmento,
puntero que indica el comienzo de la subtabla de paginas del segmento.

Con la segunda parte de la dirección se entra en la subtabla de páginas seleccionada. Lo que permite obtener el marco en el que está la información
deseada.



Se ha añadido a cada subtabla su tamaño. De esta forma se detectan las llamadas violaciones de memoria, producidas cuando el programa en ejecución intenta acceder una dirección que no pertenezca a los espacios asignados por el sistema operativo.

La ventaja del diseño con varios niveles es que permite una asignación de memoria más flexible que con un solo nivel, puesto que se pueden asignar bloques de memoria virtual disjuntos, por lo que pueden crecer de forma a independiente. Además, la tabla de páginas no tiene espacios vacíos, por lo que ocupa solamente el espacio imprescindible .

Las computadoras actuales suelen proporcionar tablas de varios niveles, algunos llegan hasta cuatro, con lo que se consigue una mayor flexibilidad en la asignación de espacio de memoria.


La Figura muestra un ejemplo de traducción mediante tabla de páginas de dos niveles. El segmento direccionado es el 5, por lo que hay que leer la entrada 5 de la tabla de segmentos.
Con ello se obtiene la dirección donde comienza la tabla de páginas de este segmento. La página direccionada es la 3, por lo que entramos en el elemento 3 de la tabla anterior. En esta tabla encontramos que el marco es el Hex4A24, por lo que se puede formar la dirección física en la que se encuentra la información buscada.


Traduccion de direcciones

La asignación de memoria y, por tanto, la construcción de la tabla de páginas es misión del sistema operativo. Sin embargo, es la MMU la que se encarga de realizar la traducción de las direcciones.

Esta división de trabajo es necesaria puesto que la traducción de direcciones hay que hacerla de forma muy rápida para que no afecte negativamente al tiempo de acceso a la memoria.

Para que una computadora con memoria virtual pueda competir con una sin
memoria virtual, la traducción ha de tardar una fracción del tiempo de acceso a memoria. En caso contrario, sería mucho más rápido y por ende mas económico el sistema sin memoria virtual.

Suponiendo una memoria principal de 100 ns y un traductor de 5 ns, el tiempo de acceso para el caso de memoria virtual es de 105 ns, es decir, un 5 por 100 más lento que en el caso de no tener memoria virtual. Sin embargo, si la traducción tardase 100 ns, la computadora con memoria virtual sería la mitad de rápida, algo que la haría imposible de competir.

La tabla de páginas es una estructura que mantiene el sistema operativo y que
reside en memoria principal (a veces, hay una parte en la propia MMU y otra en memoria principal). Esto parece un contrasentido, puesto que para acceder a memoria hay que traducir la dirección virtual, lo que supone realizar un acceso a memoria por cada nivel que
tenga la tabla de páginas. Según se ha visto, esto suponía un retardo inadmisible en los accesos a memoria. Para resolver este problema se dota a la MMU de una memoria muy rápida que permite hacer la traducción para la mayoría de los casos en una fracción del tiempo que se tarda en acceder a la memoria principal.

nota: La memoria muy rapida incluida en la MMU para realizar la traduccion de direcciones es una memoria asosiativa que se denomina TLB (traslation lookaside buffer) . en esta memoria se encuentran almacenadas las parejas paginas-marco de las paginas mas recientementa accedidas.

En caso de no encontrarse la pagina mas reciente en la TLB, es nesesario acceder a ñla tabla de paginas con el tiempo que esto conlleva.

Por lo tanto la taza de acierto de la MMU debera de ser elevada, para que el tiempo medio efectivo de traduccion sea menor al de acceso a la memoria principal.



Ejemplo de traducciones incorrectas

Finalmente, hay que destacar que la encargada de mantener la información de que página están sucias es la MMU. En efecto, al mismo tiempo que hace la traducción, en caso de que acceso sea de escritura marca a esa pagina como sucia.

nota: La MMU cuando encuentra uan pagina sucia lo guarda en la TLB y luego esta informacion se escribe en la tabla de paginas para que el sistema operativo sepa sobre esto cuando haga la migracion de paginas.

Caso de varios programas activos

Los sistemas operativos permiten que existan varios programas
activos en un mismo tiempo. De estos programas solamente puede haber uno en ejecución en cada instante, encargándose el sistema operativo de ir poniendo en ejecución uno detrás de otro de forma ordenada. Sin embargo, cada uno de los programas ha de tener asignado un espacio de
memoria, por lo que ha de tener su propia tabla de páginas.

La MMU ha de utilizar la tabla de paginas correspondient e al programa que está en ejecución. Para ello, el procesador tiene un registro
identificador de espacio de direccionamien to
(RIED). Este registro contiene la dirección en la cual está almacenada la tabla de índices o segmentos del programa.

Cuando el sistema operativo pone en ejecución un programa ha de actualizar el valor del RIED para que apunte a la tabla de páginas adecuada.


Asignacion de memoria principal y memoria virtual

En un sistema con memoria virtual, un programa en ejecución tiene asignado un espacio virtual, parte del cual reside en unos marcos de pagina de la memoria principal.

El objetivo de la políticas de extracción y de reemplazo que utilice el sistema operativo para hacer la migración de información entre el intercambio y la memoria principal tiene como objetivo conseguir, con el mínimo trabajo posible, que estén en cada momento en memoria
principal las páginas que necesitan los programas en ejecución.

Se denomina conjunto de trabajo (working set) W(k,q) de un programa en ejecución en el intervalo [k;q] al conjunto de páginas referenciadas entre el elemento k y el q de su traza.

Por otro lado, se denomina conjunto residente R(t) a la parte del proceso que está realmente almacenada u memoria principal en el instante t.


El registro RIED permite determinar la tabla de páginas en uso.

Supóngase que en el instante t el programa está por su referencia k y que el conjunto residente R(t) coincide con el conjunto de trabajo W(k,q). Esto significaría que ese programa tiene la garantía de que sus próximas q — k referencias se refieren a pagina: que están en memoria principal, por lo que no se generaría ningún fallo de página.

Dado que el sistema operativo no conoce de antemano cuales van a ser las referencias que generará un programa, ha de basarse en la trayectoria pasada de la ejecución del mismo para mantener un conjunto reciente que sea lo más parecido posible a su futuro conjunto de trabajo, para así minimizar la paginación.


Para ver este enlace Registrate o Inicia Sesion
Paginacion virtual en Windows


Gran parte de este articulo fua extraido de "Sistemas operativos: una vision aplicada."
« Última modificación: 26 de Agosto de 2008, 06:44:39 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #19 : 15 de Julio de 2008, 03:10:06 »

Entrada/Salida

Los mecanismos de E/S de la computadora tiene como objetivo el intercambio de informacion entre los perifericos y la memoria principal o los registros del procesador.

Dentro de lo que es E/S se van a encontrar con varias palabras que parecen similares pero en ciertos casos no lo son, y que ademas dentro de la red se encontraran con definiciones distintas de la misma palabra o incluso distintas palabras haciendo referencia a la misma cosa  Tongue

en fin estas palabras son:

Modulo E/S
Dispositivo E/S
Periferico E/S
Controlador E/S
Unidad E/S

bien veamos...

El modulo es lo mismo que el controlador.
los dispositivos son lo mismo que las unidades.
Los perifericos son el conjunto de:

modulo y dispositivos o modulo y unidades o controlador y dispositivos o controlador y unidades Tongue

ahora vamos a definir estos 3 conceptos.

Dispositivos

Estos son faciles de indentificar, son componentes del hardware capaces de generar un señal de E/S.

existen 4 tipos de dispositivos: de entrada, de salida, mixtos y de memoria masiva auxiliar(estos ultimos entrarian dentro de los mixtos pero yo los considero aparte)

Por ejemplo algunos dispositivos son:

De entrada:

  • Teclado
  • Ratón
  • Lápiz óptico
  • Lector óptico
  • Lector de caracteres imanables
  • Lector de bandas magnéticas
  • Lector de tarjetas "Chip" o inteligentes (Smart Card)
  • Lector de marcas
  • Lector de caracteres manuscritos
  • Lector de códigos de barras
  • Reconocedores de voz
  • "Joystick "o palanca manual de control
  • Digitalizador o tabla gráfica
  • Pantalla sensible al tacto
  • Scanner o rastreadores
  • Web cams

De salida:

  • Impresora
  • Sintetizado de voz
  • Visualizador
  • Trazador de gráficos o "plotter"
  • Monitor
  • Microfilm
  • Instrumentación científica o industrial
  • Parlantes

Mixtos:

  • Terminal interactivo
  • Terminal teletipo
  • Pantalla sensible al tacto
  • Lectora/perforadora de tarjetas
  • Módem
  • Multifuncion

Memoria masiva auxiliar:

  • Cinta magnética
  • Disco magnético
  • Tambor magnético
  • Disco óptico
  • Sistema de CD-ROM
  • DVD- Disco Versátil Digital

Debemos recordar que toda señal de entrada produce una o mas señales de salida

Tambien podemos calificar los dispositivos en locales (Se encuentran cerca de la computadora) y Remotos (Si debido a su situación lejana la conexión hay que realizarla a través de líneas especiales de transmisión son remotos)

Bueno aca hay la descripcion de algunos
Para ver este enlace Registrate o Inicia Sesion
Dispositivos
.

Modulo

El modulo o controlador de E/S es un chip de la
Para ver este enlace Registrate o Inicia Sesion
placa madre
que se encarga de las comunicaciones entre el
Para ver este enlace Registrate o Inicia Sesion
Southbridge
del
Para ver este enlace Registrate o Inicia Sesion
chipset
y otros dispositvos del sistema.

Para que les sea mas sencillo el modulo de E/S recibe la informacion de los dispositivos y la manda a la CPU aunque esto viendolo mas minociosamente en realidad recibe la informacion de los disposotivos luego la manda al Southbridge que sera el encargado de enviarla al
Para ver este enlace Registrate o Inicia Sesion
Northbridge
y recien ahi ira a la CPU.



Como pueden apreciar aca el modulo(controlador) hace de:

Interface con la  CPU y Memoria
Interface a uno o mas Dispositivos

Sin embargo esa es un de sus funciones, tambien se encarga de:

Comunicación con la CPU
Comunicación con el dispositivo
Buffering de datos
Control & Timing
Detección de error

¿que es timing?

no he encontrado una definicion para timing pero esta es muy buena!!

Citar
Timing es la cualidad que hace o quiebra un peleador. Es la habilidad para reconocer y reaccionar inmediatamente a los cambios y oportunidades durante los entrenamientos de sparring o peleas. Por ejemplo, su oponente se tropieza. Usted ve el error, instantáneamente tomando ventaja de ello con una patada o puñetazo. Eso es timing.

Aunque no sea del tema se puede adaptar, el timing vendria a ser le gestion de de las distintas señales de E/S.

Aca les dejo un pequeño grafico para que mas o menos vean como se compone:



Y aca les dejo una imagen de un chipset intel sacada de la wikipedia:




Perifericos

Un periferico es un Dispositivo+Controlador como muestra la figura siguiente



El controlador(modulo) tiene una serie de registros incluidos en el mapa de E/S de la computadora, por lo que se pueden acceder mediante instrucciones de maquina de E/S.

El registro de datos sirve para el intercambio de datos. En él ira cargando el controlador los datos leídos y de él ira extrayendo lo datos para su escritura en el periférico.

Un bit del registro de estado sirve para indicar que el controlador puede transferir una palabra. En las operaciones de lectura esto significa que ha cargado en el registro de datos un nuevo valor, mientras que en las de escritura significa que necesita un nuevo dato.

Otros bits de este registro sirven para que el controlador indique los problemas que ha encontrado en la ejecución de la última operación de entrada/salida.

El registro de control sirve para indicarle al controlador las operaciones que ha de realizar. Los distintos bits de este registro indican distintas accione que ha de realizar el periférico.

El disco magnético

El disco magnético es, para el sistema operativo, el periférico más importante, puesto que sirve de espacio de intercambio a la memoria virtual y sirve de almacenamiento permanente para los programa y los datos, encargándose el sistema operativo de la gestión de este tipo de
dispositivo.

Para entender la forma en que el sistema operativo trata a los discos magnéticos es necesario conocer las características de los mismos, entre las que destacare tres:

Organización de la información, tiempo de acceso y velocidad de transferencia.

La organización de la información del disco se realiza en contenedores de tamaño fijos denominados sectores (tamaños típicos del sector son 256, 512 o 1.024 bytes). Como muestra la  figura a continuacion, el disco se divide en pistas que, a su vez, se dividen en sectores.

Las operaciones se realizan a nivel de sector, es decir, no se puede escribir o leer una palabra o byte individual: hay que escribir o leer de golpe uno o varios sectores.

El tiempo de acceso de estos dispositivos viene dado por el tiempo que tardan en Posicionar el brazo en la pista deseada, esto es, por el tiempo de búsqueda, más el tiempo que tarda la información de la pista en pasar delante de la cabeza por efecto de la rotación del disco, esto es, mas la latencia. Fijense que estos tiempos dependen de la posición de partida y de la posición deseada. No se tarda lo mismo en mover el brazo de la pista 1 a la 2 que de la 1 a la 1.385.

Por ello, los fabricantes suelen dar los valores medios y los peores.
Un sistema de cabeza fija presenta solamente latencia sin tiempo de
sincronización. por tanto, suponiendo que gira a 10.000 rpm, tendrá un tiempo medio de acceso de 3 ms (1/2 revolución).



Dispositivos de bloques y caracteres

El disco magnético requiere que se lea o escriba un bloque de información (uno o varios sectores), por lo que se denomina dispositivo de bloques. Existen otros dispositivos de bloques como las cintas magnéticas, los DVD, los CD y los controladores de red. Todos ellos se caracterizan por tener un tiempo de acceso importante comparado con el tiempo de transferencia de una palabra, por lo que interesa amortizar este tiempo de acceso transfiriendo bastantes palabras.
Otros dispositivos como el teclado se denominan de caracteres. puesto que la operación básica de acceso es de un carácter. Estos dispositivos se cauterizan por ser lentos y por no tener un tiempo de acceso apreciablement e mayor que el tiempo de transferencia de una palabra.

aca un grafico que muestra los tiempode de acceso como para que tengan una idea general:



E/S y concurrencia

Los periféricos son más lentos que el procesador, por ejemplo, durante el tiempo que se tarda en acceder a una información almacenada en un disco, un procesador moderno es capaz de ejecutar varios millones de instrucciones de máquina.
Es, por tanto, muy conveniente que mientras se está esperando a que se complete una operación de E/S el procesador esté ejecutando un programa útil y no un bucle de espera.

Tecnicas de E/S

Las computadoras presentan tres modos básicos de realizar operaciones de E/S:
  • E/S programada
  • E/S por interrupciones
  • E/S por DMA (direct memory access)

La E/S programada exige que el procesador esté ejecutando un programa de E/S, por lo que no existe ninguna concurrencia entre el procesador y la E/S. Sin embargo, en los otros dos modos de E/S el procesador no tiene que estar tendiendo directamente a la E/S, por lo que puede estar ejecutando otro programa. Se dice, entonces, que existe concurrencia entre la E/S y el
procesador. Esta concurrencia permite optimizar el uso del procesador, pero exige que las unidades de control de los periféricos sean más inteligentes, lo que supone que sean más complejas y más caras.

En términos generales, una operación de E/S se compone de tres fases, envío de la orden al periférico, lectura o escritura de los datos y fin de la operación.

La fase de envío de la orden consiste en escribir la orden en los registros del controlador del periférico, operación que puede hacerse mediante unas cuantas instrucciones de salida, Dado que el controlador es un dispositivo electrónico, estas escrituras se pueden hacer a la velocidad de procesador, sin esperas intermedias.

En la fase de transferencia de los datos interviene el periférico, típicamente mucho más lento que el procesador.

Pasemos a explicar cada una de las tecnicas =D

E/S programada

Cuando el procesador está ejecutando un programa y encuentra una instrucción de E/S, ejecuta dicha instrucción, enviando una orden al módulo apropiado de E/S. Con E/S programada, el módulo de E/S llevará a cabo la acción requerida y luego activará los bits apropiados en el registro de estado de E/S. El módulo de E/S no lleva a cabo ninguna otra acción para avisar al procesador. En particular, no interrumpe al procesador. Así pues, es responsabilida d del procesador comprobar periódicamente el estado del módulo de E/S hasta saber que se ha completado la operación.

Con esta técnica, el procesador es el responsable de extraer los datos de la memoria principal cuando va a hacer una salida o poner los datos en la memoria principal cuando se hace una entrada. El software de E/S se escribe de manera tal que el procesador ejecute unas instrucciones que le otorguen el control directo sobre la operación de E/S, incluyendo la comprobación del estado de los dispositivos, el envío de órdenes de lectura o escritura y la transferencia de los datos. Por lo tanto, en el conjunto de instrucciones se incluyen instrucciones de E/S de las siguientes categorías:

• Control: Empleadas para activar un dispositivo externo y decirle qué debe hacer. Por ejemplo, una unidad de cinta magnética puede ser instruida para rebobinar o avanzar un registro.

• Comprobación: Empleadas para comprobar varias condiciones de estado asociadas con un módulo de E/S y sus periféricos.

• Lectura, escritura: Empleadas para transferir los datos entre los registros del procesa- dor y los dispositivos externos.

la desventaja principal de esta técnica: Es un proceso que consume tiempo y que mantiene al procesador ocupado de forma innecesaria.

he aqui un "pedazo de codigo que ayudar a comprender mejor."

Sabiendo que d es el numero de datos a leer

Código:
n=0;
while (n < d) {
     read registro_control;
     if (registro_control = datoDisponible) {
          read registro_datos;
          store en memoria principal;
          n++;
     }
}

A simple vista parece que todo esta bien....pero no.

cuando se llege al numero d de datos a leer se termina la operacion de E/S.

Sin embargo hasta que se disponga del primer dato (datoDisponible) el bucle dara unas cuantas vuletas, y una vez que se lea cuando se cambie el dato dara unas cuantas vueltas mas, debido a que el procesador es mucho mas rapido que los perifericos, el tema es que no dara 5 o 6 vueltas mas, dara millones de vueltas mas.

Se denomina espera activa cuando un programa queda en un bucle hasta que ocurra un evento. La espera activa consume tiempo del procesador, por lo que es muy poco recomendable cuando el tiempo de espera es grande en comparación con el tiempo de ejecución de una instrucción.


E/S diriguida por instrucciones

El problema de la E/S programada es que el procesador tiene que esperar un largo rato a que el módulo de E/S en cuestión esté listo para recibir o transmitir más datos. El procesador, mientras está esperando, debe interrogar repetidamente el estado del módulo de E/S. Como resultado, el nivel de rendimiento del sistema en conjunto se degrada fuertemente.

Una alternativa es que el procesador envíe una orden de E/S al módulo y se dedique a hacer alguna otra tarea útil. El módulo de E/S interrumpirá entonces al procesador para requerir sus servicios cuando esté listo para intercambiar los datos. El procesador ejecuta entonces la transferencia de los datos y reanuda el procesamiento anterior.
Seguidamente veremos cómo funciona esto, en primer lugar desde el punto de vista del módulo de E/S. Para la entrada, el módulo de E/S recibe una orden LEER desde el procesador. El módulo de E/S procede entonces con la lectura de los datos desde el periférico asociado. Una vez que los datos están en el registro de datos del módulo, éste envía una señal de interrupción al procesador a través de una línea de control. El módulo espera entonces a que los datos sean solicitados por el procesador. Cuando se haga esta solicitud, el módulo pondrá los datos en el bus de datos y estará listo para otra operación de E/S.

Desde el punto de vista del procesador, la acción para la entrada es como sigue. El procesador envía una orden LEER. Salva entonces el contexto (el contador de programa y los registros del procesador, por ejemplo) del programa en curso, se sale del mismo y se dedica a hacer otra cosa (por ejemplo, el procesador puede estar trabajando con diferentes programas al mismo tiempo). Al finalizar cada ciclo de instrucción, el procesador comprueba si hubo alguna interrupción. Cuando se produce una interrupción desde el módulo de E/S, el procesador salva el contexto del programa que está ejecutando en ese momento y comienza la ejecución de la rutina de tratamiento de la interrupción. En este caso, el procesador lee la palabra de datos del módulo de E/S y la almacena en la memoria. Luego restaura el contexto del programa que emitió la orden de E/S (o de algún otro programa) y reanuda la ejecución.

La E/S por interrupciones es más eficiente que la E/S programada porque elimina las esperas innecesarias. Sin embargo, la E/S por interrupciones sigue consumiendo una gran cantidad de tiempo del procesador, debido a que cada palabra de datos que va de la memoria al módulo de E/S o del módulo de E/S a la memoria debe pasar a través del procesador.

Casi siempre habrá varios módulos de E/S en un sistema informático, así que hacen falta mecanismos que capaciten al procesador para determinar qué dispositivo causó la interrupción y decidir, en caso de varias líneas de interrupción, cuál debe tratar primero. En algunos sistemas, hay varias líneas de interrupción, de forma que cada módulo de E/S envía una señal por una línea diferente. Cada línea tiene una prioridad diferente.

Otra solución sería habilitar una única línea de interrupción, pero utilizando líneas adicionales para indicar la dirección del dispositivo. De nuevo, a diferentes dispositivos se les asignarán prioridades diferentes.

Podemos deducir que la rutina de interrupción deberá hacer la lectura del dato y su almacenamiento en memoria principal, lo cual conlleva un cierto tiempo del procesador.

En este caso se dice que se hace espera pasiva, puesto que el programa que espera el evento no esta ejecutándose la interrupción se encarga de "despertar" al programa cuando ocurre el evento.

E/S por DMA

La E/S dirigida por interrupciones, aunque es más eficiente que la simple E/S programada, todavía requiere de la intervención activa del procesador para transferir los datos entre la memoria y un módulo de E/S y, además, cualquier transferencia de datos debe recorrer un camino que pasa por el procesador. Así pues, ambas formas de E/S adolecen de dos desventajas inherentes:

1. La velocidad de transferencia de E/S está limitada por la velocidad con la que el procesador puede comprobar y dar servicio a un dispositivo.

2. El procesador participa en la gestión de la transferencia de E/S; debe ejecutarse una se- rie de instrucciones en cada transferencia de E/S.

Cuando se tienen que mover grandes volúmenes de datos, se necesita una técnica más efi-ciente: el acceso directo a memoria (DMA, Direct Memory Access). La función de DMA se puede llevar a cabo por medio de un módulo separado sobre el bus del sistema o puede estar incorporada dentro de un módulo de E/S. En cualquier caso, la técnica funciona como sigue. Cuando el procesador desea leer o escribir un bloque de datos, emite una orden hacia el módulo de DMA, enviándole la información siguiente:

• Si lo que se solicita es una lectura o una escritura
• La dirección del dispositivo de E/S involucrado
• La dirección inicial de memoria desde la que se va a leer o a la que se va a escribir
• El número de palabras a leer o escribir

El procesador continúa entonces con otro trabajo. Habrá delegado la operación de E/S en el módulo de DMA y dicho módulo es el que tendrá que encargarse de ésta. El módulo de DMA transfiere el bloque entero, una palabra cada vez, directamente hacia o desde la memoria, sin pasar por el procesador. Cuando se completa la transferencia, el módulo de DMA envía una señal de interrupción al procesador. De esta manera, el procesador se ve involucrado sólo al inicio y al final de la transferencia.

El módulo de DMA debe tomar el control del bus para transferir los datos con la memoria. Debido a la competencia por la utilización del bus, puede ocurrir que el procesador necesite el bus pero deba esperar.Esto no es una interrupción; el procesador no salva el contexto y se dedica a hacer otra cosa. En su lugar, el procesador hace una pausa durante un ciclo del bus. El efecto general es hacer que el procesador ejecute con más lentitud durante una transferencia de DMA. No obstante, para una transferencia de E/S de varias palabras, el DMA es bastante más eficiente que la E/S programada o la dirigida por interrupciones .

Cuando el módulo de E/S en cuestión es un sofisticado canal de E/S, el concepto de DMA debe tenerse en cuenta con más razón. Un canal de E/S es un procesador propiamente dicho, con un conjunto especializado de instrucciones, diseñadas para la E/S. En un sistema informático con tales dispositivos el procesador no ejecuta instrucciones de E/S. Dichas instrucciones se almacenan en la memoria principal para ser ejecutadas por el propio canal de E/S. Así pues, el procesador inicia una transferencia de E/S instruyendo al canal de E/S para ejecutar un programa en memoria. El programa especifica el o los dispositivos, la zona o zonas de memoria para almacenamiento, la prioridad y la acción que llevar a cabo bajo ciertas condiciones de error. El canal de E/S sigue estas instrucciones y controla la transferencia de datos, informando de nuevo al procesador al terminar.

En la siguiente imagen se puede apresiar un diegrma en bloque de cada tecnica de E/S.



Como podran ver DMA es la mas efectiva, sin embargo es la mas cara y complicada como asi tambien la mas nueva, a contrapunto de la programada que es la mas vieja pero la mas barata y facil.

En fin creo que todas las computadoras actuales usan DMA y no solo un modulo, si no no se justificarian esos procesadores ultra rapidas y multi-nucleo si tendrian que estar esperando en un bucle a un periferico  Tongue

Un aspecto fundamental de esta concurrencia es su explotación. En efecto, de nada sirve descargar al procesador del trabajo de E/S si durante ese tiempo no tiene nada útil que hacer.

Será una función importante del sistema operativo el explotar esta concurrencia la E/S y el procesador, haciendo que este ultimo tenga trabajo útil el mayor tiempo posible.

para finalizar el tema les dejo esta tablita que indica cuando actua el procesador y cuando no.



Una cosa mas que puedo mostrales pero solamente para que tengan una idea visual es como se forma una placa madre, en este caso una INTEL S5000PAL que es de la unica que encontre imagen Tongue

« Última modificación: 04 de Agosto de 2008, 12:13:16 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #20 : 19 de Julio de 2008, 05:59:01 »

E/S & Memoria Virtual

La memoria virtual presenta un problema importante frente a la E/S, el programa que solicita una operación de E/S especifica una variable que determina un buffer de memoria sobre el que se hace la operación.

Para que el controlador del periférico que realiza la operación pueda operar por DMA, el buffer ha de residir en memoria principal.

En caso contrario, se intentaría hacer, por ejemplo, una lectura de unos datos de disco para escribir en una página, que también está en disco, pero el hardware no es capaz de hacer este tipo de operación.

El sistema operativo ha de garantizar que los buffers de usuario sobre los que se hacen operaciones de E/S estén en la memoria principal durante toda la duración de la operación. En especial los marcos afectados no podrán ser objeto de paginación.

En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #21 : 19 de Julio de 2008, 06:07:25 »

Protecciones

Una de las funciones del sistema operativo es la protección de unos usuarios contra otros: ni por malicia ni por descuido un usuario deberá acceder a la información de otro.

La protección hay que comprobarla en tiempo de ejecución, por lo que se ha de basar en mecanismos hardware.

Los mecanismo de proteccion hardware pueden ser del procesador o la memoria

Mecanismos de protección del procesador

Los mecanismos de protección del procesador se basan en los niveles de ejecución del mismo.

En nivel de ejecución de núcleo se pueden ejecutar todas las instrucciones de maquina y se pueden acceder a todos los registros y a la totalidad de los mapas de memoria y de E/S. Sin embargo, en modo usuario se ejecuta un subconjunto de las instrucciones y se limitan los registros y los mapas accesibles.

Uno de los objetivos prioritarios de protección son los periféricos. En efecto, prohibiendo el acceso directo de los usuarios a los periféricos se impide que puedan acceder a la información almacenada por otros usuarios en esos periféricos.

Por esta razón, toda la E/S es accesible solamente en nivel de núcleo, nivel que debe estar reservado al sistema operativo.

Para evitar que un programa de usuario pueda poner el procesador en nivel de núcleo, no existe ninguna instrucción máquina que realice este cambio (Pero se puede argumentar que quien realiza eto son las instrucciones TRAP que cuando hace la interrupcion como efecto indirecto se hace el cambio de nivel de ejecucion y se deja de ejecutar el programa que incluye las instruccion TRAP, pasandose a ejecutar el SO).

Sin embargo, existe la instrucción máquina inversa, que cambia de nivel de núcleo a nivel de usuario. Esta instrucción es utilizada por el sistema operativo antes de dejar que ejecute un programa de usuario.

El mecanismo suministrado por el hardware para que el procesador pase a nivel de núcleo es la interrupción. En efecto, toda interrupción, ya sea interna o externa, tiene como efecto poner al procesador en nivel de núcleo.

Siempre y cuando el sistema operativo se encargue de atender todas las interrupciones y de poner en nivel de usuario procesador antes de lanzar la ejecución de los programas de usuario, se garantiza que solamente sea el sistema operativo el que ejecute en nivel de núcleo.

Mecanismos de protección de memoria

Los mecanismos de protección de memoria deben evitar que un programa en ejecución direccione posiciones de memoria que no le hayan sido asignadas por el sistema operativo.

Una solución empleada en algunas máquinas que no tienen memoria virtual consiste en incluir una pareja de registros valla (limite y base), como los mostrados en la figura de abajo. En esta solución se le asigna al programa una zona de memoria contigua.

Todos los direccionamien tos se calculan sumando el contenido del registro base, de forma que para el programa es como si estuviese cargado a partir de la posición «0» de memoria. Además, en cada acceso un circuito comparador comparara la dirección generada con el valor del registro
limite.

En caso de desbordamiento, el comparador genera una excepción de violación de memoria, para que el sistema operativo trate el tema, lo en la práctica, supone que parará el programa produciendo un volcado de memoria (core dump).


Uso de registros valla.



En los sistemas con memoria virtual existen dos mecanismos de protección de memoria.

Por un lado, en nivel de usuario el procesador no permite acceder más que a una parte del mapa de memoria. Como muestra la figura:


División del mapa de memoria.

Una solución es que en nivel de núcleo se pueda direccional todo el mapa de memoria virtual, mientras que en nivel de usuario solamente se pueda direccional una parte del mapa (por. ej.: las direcciones que empiezan por
«0»).

La MMU generará una excepción de violación de memoria en caso de que en nivel de usuario se genere una dirección no permitida (por. ej.: que empiece por «1»).

Además, una solución bastante frecuente consiste en dotar al procesador de un registro RIED (registro de identificador de espacio de direccionamien to). De esta forma se consigue que cada programa ejecución disponga de su propio espacio virtual, por lo que no puede acceder a los clon espacios de memoria de los otros procesos.

El otro mecanismo se basa en la tabla de páginas.

La tabla de páginas de cada programa en ejecución se selecciona mediante el RIED y especifica los espacios de memoria asignados por el sistema operativo a ese programa. La MMU, al mismo tiempo que realiza la traducción de cada dirección, comprueba que no se sobrepase el límite
de ninguna de las tablas involucradas.

En caso de sobrepasarse, generara una excepción de violación de memoria, para que el sistema operativo realice la acción correctora oportuna.


La tabla de páginas como mecanismo de protección de memoria.

Este articulo fue extraido de "Sistemas operativos: una vision aplicada."
« Última modificación: 26 de Julio de 2008, 06:05:00 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #22 : 30 de Julio de 2008, 12:10:36 »

Segmentos de Memoria

Me parecio interesante comentarles como se llaman los segmentos y darles una pequeña descripcion de cada uno antes de dejar la parte introductoria del curso.

Cuando ejecutamos un programa, la memoria asigna 5 segmentos al mismo.

estos 5 segmentos son:

code segment: como el nombre lo indica es el segmento que contiene el codigo del programa, aca residen las instrucciones en codigo de maquina del programa en ejecucion, este segmento es fijo y de solo escritura.

data segment: Aca se encuentran las variables globales iniciadas en el programa en ejecucion, cuando al principio del programa creamos una variable y le damos un valo se guarda en este segmento.este segmento es de tamaño fijo y se puede escribir sobre el.

bss segment: Aca se van a guardar las variables no inicializadas de el programa en ejecucion, es decir, cuando definimos una variable pero no le damos un valor

Código:
int numero;

lo que en verdad estamos haciendo es guardar un espacion en el segmento bss para esta variable. este segmento es de tamaño fijo y se puede escribir sobre el.

heap segment: Monton, se llama al segmento de memoria reservado para la memoria dinamica. cuando un programador no sabe el valor que va a tener una variable porque va a ser definida por el usuario en tiempo de ejcuccion (tipico caso de un "input") tiene dos opciones, o crea una variable sufucientement e grande para albergar el posible dato de entradao recurre a la memoria dinamica. este segmento no esta definido sino que va variando y se puede escribir sobre el. este segmento crece en el mismo sentido que las direcciones de memoria.

stack segment:este segmento se llama pila se trata de una estructura de datos algo particular la cual podemos meter o apilar (push) o sacar /desapilar (pop) variables de la cima de la pila, esto se usa para las variables locales de las funciones del programa, para almacenar direcciones de retorno de una funcion, etc. este segmento crece en el sentido inverso a las direcciones de memoria, por lo tanto hacia el heap. cuando aumenta la pila disminuye el heap.

para que quede claro el concepto de stack podemos visualizar uno de esos palitos dosde se ponen los cd's, podemos poner cd's arriba y podemos sacr los de arriba, pero no podemos sacar los del medio si no sacamos los de arriba.

tomando como lenguaje JAVA. si queremos insertar un elemento al monticulo seria algo asi:

Código:
public void insertItem(Object k, Object e) throws InvalidKeyException {
    if(!comp.isComparable(k))
        throw new InvalidKeyException("Invalid Key");
    Position z = T.add(new Item(k, e));
    Position u;
    while(!T.isRoot(z)) { // bubbling-up
        u = T.parent(z);
        if(comp.isLessThanOrEqualTo(key(u),key(z)))
             break;
        T.swapElements(u, z);
        z = u;
     }
}

y para eliminar un eliminar un elemento del monticulo seria algo asi:

Código:
public Object removeMin() throws PriorityQueueEmptyException {
    if(isEmpty())
        throw new PriorityQueueEmptyException("Priority Queue Empty!");
    Object min = element(T.root());
    if(size() == 1)
        T.remove();
    else {
        T.replaceElement(T.root(), T.remove());
        Position r = T.root();
        while(T.isInternal(T.leftChild(r))) {
            Position s;
            if(T.isExternal(T.rightChild(r)) || comp.isLessThanOrEqualTo(key(T.leftChild(r)),key(T.rightChild(r))))
                s = T.leftChild(r);
            else
                s = T.rightChild(r);
            if(comp.isLessThan(key(s), key(r))) {
                T.swapElements(r, s);
                r = s;
            }
            else
                break;
        }
    }
}

estos codigos sacados de la wikipedia.

Anexo: Control de procedimientos

Bueno en vista de que me he dado cuenta de que varios siguen el curos me he dignado a anexar algo a la introduccion que no es sumamente util pero para los curiosos, los que quieren saber mas sobre SO y los que quieren saber mas sobre Overflows Tongue este tema les va a gustar.

Empezemos:

Una técnica común para controlar las llamadas a procedimientos y los retornos es usar una pila, en este anexo analizaremos las propiedades básicas de las pilas y su utilización en el control de los procedimientos .

Implementacion de las Pilas

Una pila es un conjunto ordenado de elementos, de los cuales sólo uno puede ser accedido en un momento dado. El punto de acceso se llama cima de la pila. El número de elementos de la pila o longitud de la pila, es variable. Se pueden añadir o eliminar elementos sólo por la cima. Por esta razón, una pila también se conoce como una lista último en entrar, primero en salir (LIFO, Last-In, First-Out), el elemento superior de la pila (al que se lo puede sacar o poner otro encima) se lo suele llamat TOS (Top of Stack)



La figura de arriba muestra las dos operaciones básicas que se pueden llevar a cabo sobre las pilas. Se comienza en algún instante en el que la lista contiene un cierto número de elementos. Una operación METER (PUSH) añade un nuevo elemento a la cima de la pila. Una operación SACAR (POP) quita el elemento de la cima de la pila. En ambos casos, la cima de la pila se desplaza en consecuencia.

La implementación de la pila exige un cierto número de posiciones empleadas para al- macenar los elementos.



En la figura se muestra la implementación mas tipica.

Se reserva en la memoria principal (o en la virtual) un bloque de posiciones contiguas para la pila. La mayor parte del tiempo, el bloque estará parcialmente lleno con los elementos de la pila y el resto permanecerá disponible para su crecimiento. Se necesitan tres direcciones para las operaciones, las cuales se almacenan a menudo en los registros del procesador:

• Un puntero de pila: Contiene la dirección de la cima de la pila. Si se añade un elemento a la pila (METER) o se elimina un elemento de la pila (SACAR), este puntero se incrementa o se decrementa para poder tener la dirección de la nueva cima de la pila.

• Base de la pila: Contiene la dirección del fondo de la pila en el bloque reservado para la misma. Ésta es la primera posición que se utiliza cuando se añade un elemento a una lista vacía. Si se intenta SACAR cuando la pila está vacía, se informará sobre el error.

• Límite de la pila: Contiene la dirección del otro extremo del bloque reservado para la pila. Si se intenta METER cuando la pila está llena, se informará sobre el error.

Llamadas a procedimientos y retornos

Una técnica habitual para gestionar las llamadas a procedimientos y los retornos se basa en el uso de una pila. Cuando el procesador ejecuta una llamada, pone la dirección de retomo en la pila. Cuando ejecuta un retomo, utiliza la dirección que está en la cima de la pila. Aca se encuentra ilustrado el uso de la pila para administrar los procedimientos anidados.





Además de dar la dirección de retomo, a menudo es necesario pasar unos parámetros en las llamadas a procedimientos . Estos podrían pasarse en registros. Otra posibilidad es almacenar los parámetros en la memoria justo antes de la instrucción LLAMAR (CALL). En tal caso, el retomo debe ser a la posición que sigue a los parámetros. Ambos enfoques tienen sus inconvenientes . Si se utilizan los registros, el programa llamado deberá escribirse de modo que se asegure que los registros se usan correctamente. Almacenar los parámetros en memoria dificulta el intercambio de un número variable de parámetros.

Un método más flexible de paso de parámetros es la pila. Cuando el procesador ejecuta una lla- mada, no sólo apila la dirección de retomo, sino también los parámetros que tiene que pasarle al procedimiento llamado. El procedimiento llamado puede acceder a los parámetros en la pila. Al volver, los parámetros de retomo también pueden ponerse en la pila, bajo la dirección de retomo. El conjunto completo de parámetros, incluyendo la dirección de retomo, que se almacena como producto de la invocación de un procedimiento, es conocido como marco de pila (snack frame).



En la figura se muestra un ejemplo. Este se refiere a un procedimiento P en el que se declaran las variables locales x1 y x2 y un procedimiento Q, que puede ser llamado por P y en el que se declaran las variables locales y1 e y2. En la figura, el punto de retorno para cada procedimiento es el primer elemento almacenado en el marco de pila correspondient e. A continuación, se almacena un puntero al comienzo del marco anterior. Esto es necesario si el número o la longitud de los parámetros a almacenar son variables.

Procedimientos reentrantes

Un concepto útil, particularment e en un sistema que da soporte a varios usuarios al mismo tiempo, es el de procedimiento reentrante. Un procedimiento reentrante es aquel en el que sólo una copia del código del programa puede estar compartida entre varios usuarios durante el mismo periodo.
La reentrada tiene dos aspectos clave: El código del programa no puede modificarse a sí mismo y los datos locales para cada usuario se deben almacenar por separado. Un procedimiento reentrante puede ser interrumpido y llamado por un programa y seguir ejecutando correctamente al retornar al procedimiento. En un sistema compartido, la reentrada permite un uso más eficiente de la memoria principal: Aunque se almacena una sola copia del código del programa en la memoria principal, más de una aplicación pueden llamar al procedimiento.
Así, un procedimiento reentrante debe tener una parte permanente (las instrucciones que constituyen el procedimiento) y una parte temporal (un puntero hacia atrás al procedimiento que llamó, así como memoria para las variables locales utilizadas por el programa). Cada caso particular de ejecución de un procedimiento, que se denomina activación, ejecutará el código que está en la parte permanente, pero tendrá su propia copia de las variables locales y de los parámetros. La parte temporal asociada con una activación en particular se conoce como registro de activación.
La forma más conveniente de dar soporte a los procedimientos reentrantes es por medio de una pila. Cuando se llama a un procedimiento reentrante, se puede almacenar en la pila el registro de activación de dicho procedimiento. De esta manera, el registro de activación se convierte en parte del marco de la pila que se crea al LLAMAR al procedimiento.

Cito de la wikipedia lo siguiente:

Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un vector dinámico o inculadas (por separado) la lista de ejecución.

La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.

Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).

Código: (python)
class Stack(object):
    def __init__(self):
        self.stack_pointer = None
 
    def push(self, element):
        self.stack_pointer = Node(element, self.stack_pointer)
 
    def pop(self):
        e = self.stack_pointer.element
        self.stack_pointer = self.stack_pointer.next
        return e
 
    def peek(self):
        return self.stack_pointer.element
 
    def __len__(self):
        i = 0
        sp = self.stack_pointer
        while sp:
            i += 1
            sp = sp.next
        return i
 
class Node(object):
    def __init__(self, element=None, next=None):
        self.element = element
        self.next = next
 
if __name__ == '__main__':
    # small use example
    s = Stack()
    [s.push(i) for i in xrange(10)]
    print [s.pop() for i in xrange(len(s))]

La PilaNV es la pila no vacía, que diferenciamos de la pila normal a la hora de tomar en cuenta errores. El elemento X representa el tipo de valor que puede contener la pila: entero, carácter, registro....

Código: (maude)
fmod PILA-GENERICA {X :: TRIV} is
  shorts Pila{X} PilaNV{X}.
  subsorts PilaNV{X} < Pila{X}.
 
  generadores:
   op crear: -> Pila {X} [ctor].
   op apilar : X$Elt Pila{X} -> PilaNV{X} [ctor].
 
  constructores
   op desapilar : Pila{X} -> Pila{X}.
 
  selectores
   op cima : PilaNV{X} -> X$Elt.
 
  variables
    var P : Pila{X}.
    var E : X$Elt.
 
  ecuaciones
   eq desapilar (crear) = crear.
   eq desapilar(apilar(E, P)) = P.
   eq cima(apilar(E, P)) = E.
endfm

Código: (c++)
#ifndef PILA
#define PILA
 
 
template <class T>
struct Nodo {
    T elemento;
    Nodo<T>* siguiente;
};
 
 
template <class T>
class Pila {
 
private:
    Nodo<T>* ultimo;
    unsigned int elementos;
 
public:
    Pila() {
        elementos = 0;
    }
 
    ~Pila() {
        while (elementos != 0) pop();
    }
 
    void push(const T& elem) {
        Nodo<T>* aux = new Nodo<T>;
        aux->elemento = elem;
        aux->siguiente = ultimo;
        ultimo = aux;
        ++elementos;
    }
 
    void pop() {
        Nodo<T>* aux = ultimo;
        ultimo = ultimo->siguiente;
        delete aux;
        --elementos;
    }
 
    T cima() const {
        return ultimo->elemento;
    }
 
    bool vacia() const {
        return elementos == 0;
    }
 
    unsigned int altura() const {
        return elementos;
    }
 
};
 
 #endif

Fuente: algunas partes fueron extraidas de Stalling William y otras de wikipedia, sin embargo el articulo esta adaptado, modificado y con partes agregadas por mi
« Última modificación: 04 de Agosto de 2008, 11:28:30 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #23 : 31 de Julio de 2008, 11:45:44 »

Fin

Con lo que se vio hasta el momento, doy por finalizada la parta introducturia del tema.

A partir de ahora comenzaria el curso y empezariamos a ver algunos conceptos nuevos y mas fijos a la que queremos, que son los Sistemas Operativos.

Como podran apreciar si la introduccion fue eso, como ser todo el tema....la verdad es un tema muy amplio (obvio que no lo termine y ni creca de los estoy, yo recien me inicio) pero que poco a poco vamos a ir avanzando, y aunque aca solamente se nombre algunas cosas de la que en realidad es esto, voy a explicar lo mas posible y tambien voy a tratar de poner codigos asi se hace un poco mas practico.

Tambien aprobecho para dejarles un pequeño regalo, un programa con codigo abierto, en java que muestra el funcionamiento de la computadora cuando intentamos cargar un archivo o cosas por el estilo.


Para ver este enlace Registrate o Inicia Sesion
http://a.waeswaes.googlepages.com/Sim-X.rar


Comenzemos...
« Última modificación: 16 de Octubre de 2008, 04:23:24 por WaesWaes » En línea


Para ver este enlace Registrate o Inicia Sesion

Java Lover
Estudiando
Para ver este enlace Registrate o Inicia Sesion
Sistemas Operativos

OpenSolaris 2008.05 + Ubuntu 8.04 + Windows XP Pro SP3
Illdan
WaesWaes
Moderador Global
*****
Desconectado Desconectado

Mensajes: 1,797


Consumiras poder hasta que él te consuma


Ver Perfil WWW
« Respuesta #24 : 31 de Julio de 2008, 11:47:33 »