1. Introducción

¿Qué es Software de sistemas?

Es un Software que hace de puente entre las aplicaciones y el hardware.

Software .- Programas con sus instrucciones, etc.

Sistema .- Relacionado con el control y la gestión de un sistema informático

Los procesadores de lenguajes y los sistemas operativos son un tipo de software.

Es irrelevante para el usuario final, y vital para los programadores.

Aplicaciones y Software de Sistemas

APLICACIONES	SW DE SISTEMAS
Ejecutan una aplicación	Controlan el sistema
Maneja datos de la aplicación	Maneja recursos de la máquina
Da servicio al usuario final	Ofrece servicios al programador y a las aplicaciones
Escrito en lenguaje de alto nivel	Partes en ensamblador
Solo está en ejecución mientras dura la aplicación	Puede ejecutarse durante todo el tiempo que la máquina esté encendida
Aplicación a medida	Siempre es un paquete
Generalmente es un proceso paso a paso	Suele manejar varios procesos simultáneamente

Estas diferencias evolucionan:

Lenguaje C .- Software de Sistemas en Lenguajes de Alto Nivel

Desarrollos de Compiladores o S.O. para proyectos de investigación

Los usuarios del software son:

Aplicaciones .- El usuario final

Software de Sistemas .- Desarrollador de aplicaciones

Es necesario un entorno adecuado.

Tipos de Software de Sistemas

Procesadores de Lenguajes

Permiten que los programas escritos en lenguajes de alto nivel sean ejecutados en una máquina.

El hardware solo entiende instrucciones máquina de bajo nivel.

Caso de los traductores, donde nos encontramos los compiladores y los ensambladores, y de los intérpretes.

Compilador .- Traduce un programa en alto nivel a instrucciones máquina ejecutables por una CPU. Cuando se ejecuta una aplicación, el compilador no está presente. Así un programa escrito en MODULA es imposible de ejecutar. El compilador nos ofrece un puente real entre dos entornos diferentes.

Intérprete .- Traduce y ejecuta sentencia a sentencia un programa. Es un programa que está ejecutándose, toma una sentencia de la aplicación y la ejecuta en la CPU.

Los procesadores de lenguaje crean una Máquina Virtual; el programador obtiene una máquina que entiende Modula o Cobol. El Software de Sistemas ha creado un entorno más sencillo y conveniente que el entorno real.

Sistemas Operativos

Controlan las operaciones de la máquina mientras se ejecutan las aplicaciones. Realiza muchas funciones de gestión de recursos (memoria, discos, seguridad, arranque/parada, etc.). Cuando se arranca una máquina se carga el S.O. y mantiene el control del sistema durante todo el tiempo.

Las aplicaciones manejan su E/S mediante peticiones al S.O., el cual envía las órdenes apropiadas al hardware.

El S.O. ofrece un entorno mucho más simple que la máquina real, Máquina Virtual, algunos S.O.'s ofrecen varias.

Es un claro puente entre el hardware y las aplicaciones.

Protege el acceso directo a la E/S por las aplicaciones, el acceso se produce de forma controlada a través de llamadas al S.O.

Traduce las peticiones de las aplicaciones (system call) a las instrucciones necesarias para acceder al hardware real.

Utilidades

Suelen ser una extensión libre del S.O. Se trata de tareas de bajo nivel; por ejemplo, al copiar un disco completo, sería copiar todos los sectores y pistas. Suelen realizar una única tarea.

Otras clase de Software de Sistemas

Ofrecen algún tipo de función del sistema que no es específica de ninguna aplicación:

• Editores

• Gestores de Bases de Datos

• Programas de ordenación

• Emuladores de pantalla o teleproceso

• Etc.

Necesidad del Software de Sistemas

• Se puede escribir un programa en código máquina

• Aplicaciones de bajo nivel controlan el hardware

• Sin compiladores ni S.O., para llevar los programa a la memoria para su ejecución:

• Cargador (software de sistema) carga los programas del usuario

• Escrito en PROM

• Mediante interruptores

• Sin S.O. solo podemos cargar una sola aplicación

• Programa incrustados (embbebed)

• Una única función (lavadoras, misiles, etc.)

• Sin procesadores de lenguajes

• Programas en ensamblador o lenguaje máquina

• Ventajas:

• Productividad

• Calidad

• Evitar duplicidades de código en las aplicaciones

• Manejo de periféricos

2. Ensambladores

Conceptos básicos sobre ensambladores

La función de un ensamblador es traducir un programa en lenguaje ensamblador al formato interno máquina que se puede ejecutar.

Se supone que un ensamblador es un programa muy simple; pues el lenguaje ensamblador especifica todas las instrucciones máquina, más o menos un reformateo. Sin embargo, realiza muchas más cosas:

• Direccionamiento simbólico

• Macros

• Suelen tener un tamaño parecido a un compilador

• Puede ser un tipo de procesador de lenguajes elaborado

Código fuente .- Lenguaje de entrada que acepta el traductor.

Código objeto .- Código máquina traducido que genera el traductor.

Un ensamblador es un traductor que genera código máquina binario a partir de un código fuente en lenguaje ensamblador.

Un emulador es un programa ejecutándose sobre una máquina que interpreta y ejecuta las instrucciones de un programa escrito para otra máquina.

Lenguaje Ensamblador

Es un método de programación donde cada instrucción máquina es especificada por el programador, pero con varias ayudas en el lenguaje que lo hacen más conveniente que el código máquina puro.

Los lenguajes ensambladores son diferentes para cada máquina:

• Conjunto de instrucciones máquina propio

• Pueden existir similitudes

• Las instrucciones reales deben corresponderse con las de la máquina

• La terminología usada puede variar ligeramente

El formato estándar es una instrucción por línea, que consta de cuatro campos:

Etiquetas .- Opcionales

Código Operación .- Es un campo obligatorio, excepto cuando es una línea de comentarios

Operando .- El número depende de la arquitectura de la máquina

Comentarios .- Opcionales

NEXT LDA TOTAL Para valor final

Características del lenguaje ensamblador

Códigos de operación mnemónicos

• La mayor diferencia entre el código máquina y el lenguaje ensamblador son los mnemónicos

• Los códigos de operación de las instrucciones se representan mediante un nombre corto (mnemónico)

• Se corresponde con su código numérico

LDA 00000001

• Mayor legibilidad

• Operación que realiza cada línea

• El diseño del hardware suele añadir el diseño de su lenguaje ensamblador

Direccionamiento Simbólico

• Posibilidad de referirse a una dirección mediante un símbolo

• Evita utilizar direcciones absolutas

• Cercano al concepto de nombres de variables en los L. A. N.

• Libera al programador de calcular direcciones

• Facilita la modificación de los programas

• Permite la reubicación (o la facilita en gran medida) de los programas; todas las referencias a direcciones simbólicas se deberán ensamblar como relativas al inicio del programa.

Pseudo-instrucciones

• Las pseudo-instrucciones o directivas son órdenes (o información) directamente para el ensamblador

• Nunca se ejecxutan

• Se procesan en tiempo de ensamblado

• Uso:

• Definir la dirección inicial

• Reservar espacio para los datos

• Ordenes para el listado; saltos de página, ...

• Asignar un valor constante a un símbolo

• ORG, EQU, DS, DC, DEFW, DEFS, BSS, MACRO, END

Valores

• Necesidad de poder indicar valores

• Areas de datos inicializadas

CONVRATE DEFW 27

• Valores numéricos:

1CH, X'1C', H1C

00011100B

• Tipos de datos, sólo una posibilidad de representación de los datos

Expresiones

REC - 1

LDA TOTAL + 8

TOTAL - 20C0

Código de LDA - 01

Instrucción: 0120C8

• Suma y resta suele estar soportada

• Multiplicación y división a veces (símbolos absolutos y relativos)

Literales

• Los cálculos que incluyen constantes necesitan tener almacenadas esas constantes

LDA VAR1

MUL CIEN

. . .

. . .

CIEN DEFW 100

• El literal se puede usar donde se necesita un valor

MUL = 100

• El ensamblador se encarga de buscarle las posiciones de memoria que necesite.

• Normalmente, al final del programa

• No se debe confundir con una dirección explícita como operando

MUL 100

Macros

• Unen ciertas secuencias de instrucciones que se repiten frecuentemente

• Evita reescribirlas varias veces

• Concepto general aplicable a todo tipo de lenguajes

• Pseudo-instrucciones

MACRO y END

• Permiten parámetros simbólicos

• Diferencia entre macro y subrutina

• Tiempo de ensamblado contra tiempo de ejecución

• Subrutinas menos código pero menos eficientes

• Las macros repiten su código cada vez, pero no tienen prólogo/epílogo de las subrutinas

MACRO

INCR &LOC, &VAL

LDA &LOC

ADD =&VAL

STO &LOC

MEND

• El programador puede utilizar una nueva instrucción del tipo

INCR total, 4

• El ensamblador la sustituye por

LDA TOTAL

ADD =4

STO TOTAL

Ensamblado Condicional

Funciones de un ensamblador

Un ensamblador es como un software que traduce código fuente en lenguaje ensamblador a código máquina.

Existe un proceso de traducción, sobre todo para manejar las direcciones simbólicas, macros, literales y otros.

Traducción de Códigos de Operación

Los códigos de operación mnemónicos deben ser reemplazados por sus códigos de operación numéricos. Se suele emplear una Tabla de Instrucciones (constante).

Las instrucciones de máquinas reales suelen tener tamaños diferentes. A veces, un mismo código para varias cosas.

Asignación de direcciones

Debe determinar las direcciones reales donde se cargará cada instrucción. Se usa un contador de direcciones.

• Al pirncipio de un programa se asigna un valor inicial al contador de direcciones (ORG)

• Se incrementa con el tamaño de cada instrucción explorada

• Cuando el programador usa el símbolo “ * “, el ensamblador utiliza el valor actual de su contador de direcciones

El valor del contador de direcciones puede ser una dirección absoluta o relativa al comienzo del programa,

• Código reubicable

• Necesidad de reubicación por parte del enlazador o del cargador

Resolución de direcciones simbólicas

Debe reemplazar los símbolos que aparecen como operando en las instrucciones, y utilizar la dirección numérica real correspondiente.

Se suele realizar en la segunda pasada consultando la Tabla de Símbolos.

Conversión de constantes a binario

Todos los valores definidos son valores decimales, caracteres, etc. Se deben evaluar y calcular un valor binario que se inserte en el código ejecutable.

Evaluación de expresiones

Evaluar las expresiones y calcular un valor binario que se pueda insertar en el código.

Asignación de almacenamiento a literales

Se deben asignar posiciones de memoria a los literales; calcular su valor y almacenar en la dirección que se le asigna. También se debe insertar el valor de su dirección en las instrucciones que lo utlizan.

Cálculo de los campos de dirección

Cualquier expresión utilizada en un campo de operando se debe calcular. Según los tipos de direccionamiento utilizado se calcula la Dirección Efectiva (D.E.) del operando.

El valor necesario para calcular la dirección real donde está almacenado el dato se inserta en el código generado.

LDA 2000 (DE: 2000)

LDA* 2000 (DE: 2000 + IX)

Expansión de Macros

Las instrucciones que componen una macro se deben insertar en el código cada vez que aparezca una referencia a la macro. Esto incluye las sustituciones de los parámetros simbólicos.

Como se incluyen nuevas instrucciones, se deben realizar todas las funciones descritas para cada instrucción que compone la macro.

Tareas varias

• Mensajes de error

• Listados de código fuente y código objeto en octal/hexadecimal

• Generar un fichero en el código objeto

Mecánica de un Ensamblador

Se realizan varias pasadas por el código fuente (se lee éste de principio a fin varias veces). La información se recoge en cada pasada, en un conjunto de tablas.

Se usará en la pasada final para general el código objeto. La primera pasada lee el código fuente original. Las siguientes pueden volver a leerlo o utilizar algún formato de código intermedio.

La mayoría de los ensambladores realizan dos pasadas. Cuando realizan expansión de macros suelen realizar una pasada previa para dicha expansión.

Primera pasada

• Examinar las instrucciones

• Incrementar el Contador de Posiciones de Memoria

• Construir la Tabla de Símbolos

• Construir la Tabla de Literales

Segunda pasada

• Utilizar la tabla de símbolos

• Generar el Código Objeto Completo

Tabla de Símbolos

• Nombre de todos los identificadores

• Sus direcciones (valores)

Es posible realizar un ensamblador de 1 paso:

• Prohibir referencias futuras

• Mantener simultáneamente todo el código objeto que se construye en memoria (modificable)

• Examinar el código hasta encontrar la definición del símbolo y continuar por donde iba

• Otras técnicas

Ejemplo

* Ejemplo de programa en ensamblador

* Subrut. que saca por impresora A-Z

ORG 2000H Dir. Inicial

LDI `A' Carc. Inicial

NEXT OUT 2 Salida

STO CHARVAL Salva

SUB ='Z' Es la Z?

JZ EXIT Si es Z, fin

LDA CHARVAL Ingr. Char

ADD =1 Sig. Char

JUMP NEXT Continuar

EXIT JUM* 0 Termina

***** Datos *****

CHARVAL DEFW 0 Valor Carac.

END

• Tabla de símbolos

NEXT 2003

CHARVAL 201C

EXIT 2018

• Tabla de literales

`Z' 201E

1 2020

• Código generado (dirección inicial 2000H)

• 09 00 41

2003 32 00 02

• 02 20 1C

• 04 20 1E

200C 23 20 18

200F 01 20 1C

2012 02 20 20

• 21 20 03

2018 A1 00 00 Por salto indexado

201B 00

201C 00 00

201E 00 5ª

• 00 01

Cuestiones prácticas

• La tabla de símbolos es el corazón del ensamblador

• Un ensamblador eficiente tendrá un acceso eficiente a su T.S.

• 50 símbolos (programa pequeño)

• 1.000 símbolos (programa grande)

• Ordenación alfabética; búsqueda binaria

• Tablas Hash

• Listado de referencias cruzadas

• Listado tabla de símbolos

Enlazadores y Cargadores

Programación Modular

En programas grandes (+100.000 líneas) es conveniente no tener que recompilar todo el programa cuando se realizan pequeños cambios. Por esta razón se encuentran separados en módulos compilables que se integran para su ejecución.

El proceso de integrar varios módulos para formar un único programa ejecutable se denomina enlazado (linking) o edición de enlaces (linkage editing). Los enlaces entre módulos suelen estar basados en las llamadas a procedimientos externos.

La compilación es independiente para cada módulo. Estos módulos son integrados por el enlazador o editor de enlaces antes de su ejecución.

Es un diseño estructurado mediante técnicas de ingeniería software. Estas son sus ventajas:

• Mayor facilidad en los cambios

• Varios programadores pueden escribir simultáneamente diferentes módulos

• Las distintas funciones del programa se pueden separar y aislar, evitando los efectos laterales

• Reutilización de módulos comunes

• Diferentes lenguajes de programación en diferentes módulos

• Depuración por módulos. Pruebas independientes y posterior integración

La mayoría de los traductores no generan un código ejecutable (cargar y ejecutar). Crean un código objeto reubicable; es un formato procesable por un editor de enlaces (MS-DOS: ficheros .OBJ).

El editor de enlaces genera un módulo cargable; en MS-DOS los ficheros .COM o .EXE. Se trata de un fichero con los mismos bits que se cargarán en la memoria RAM para su ejecución.

Ensamblado para reubicación

Al final, hay que unir todos los módulos para generar un único programa objeto reubicable.

El problema es que no se conoce la posición definitiva en memoria de los módulos dentro del programa principal. Esta depende del origen asignado al primer módulo y de los tamaños de todos los módulos que le preceden.

La solución podría consistir en ensamblar todos los módulos juntos; pero resulta muy ineficaz y habría que repetir reiteradamente el trabajo de ensamblar módulos no modificados.

Entonces, encontramos la solución en ensamblar sólo aquellos módulos que han sido modificados. Para ello es necesario un programa enlazador o montador.

Un enlazador compacta todos los módulos, procura que todas las referencias del programa global sean correctas. El ensamblador deberá preparar los módulos objetos para facilitar el trabajo del enlazador.

El problema de la reubicación reside en que posicionar un código en una dirección de memoria determinada se reduce a sus posiciones absolutas. Por esta razón hay que ensamblar los módulos como si empezaran en la posición cero (0), y construir una Tabla con todas las Direcciones Absolutas (TDA).

El cargador o el enlazador, una vez conocido el origen real X del programa o del módulo, incrementan en X todas las direcciones de la TDA.

Los ensambladores suelen poder generar tanto código absoluto como código reubicable. Así tenemos:

• Ensambladores absolutos

• Ensambladores relativos

Si existe una pseudo-instrucción ORG se comportan como ensambladores absolutos. Si, por el contrario, no aparece, se supone que no se conoce el origen, se ensambla con origen cero y se geenera una TDA.

Pseudo-instrucciones EXPORT e IMPORT

Los problemas de la programación modular son la reubicación y las referencias externas (un módulo necesita utilizar datos o código de otros módulos).

El ensamblador no puede generar completa la Tabla de Símbolos y se produce un error de programación. Para evitarlo hay que usar las pseudo-instrucciones EXPORT e IMPORT.

EXPORT .- Se especifican todos los nombres simbólicos de un módulo que serán referenciados por otros módulos.

IMPORT .- Se identifican todas las referencias externas de un módulo:

• Permite reconocer una referencia externa

• No se puede completar la Tabla de Símbolos

El enlazador resolverá las referencias externas. El ensamblador dejará el trabajo preparado creando dos tablas adicionales:

• Tabla de Símbolos Importados (TSI)

• Tabla de Símbolos Exportados (TSE)

Tabla de Símbolos Importados (TSI)

• Una anotación por cada aparición de un símbolo importado

• Nombre simbólico

• Dirección relativa dentro del módulo

• Tipo

Tabla de Símbolos Exportados (TSE)

• Nombre simbólico

• Valor de la dirección

• Tipo

Programa Enlazador

El objetivo es convertir uno o más módulos en un único módulo ejecutable. Sus funciones son reubicar y resolver las referencias externas.

Necesita que el ensamblador genere para cada módulo la siguiente información:

• Indicación de módulo absoluto (o reubicable)

• Dirección de carga (solo módulos absolutos)

• TDA, Tabla de Direcciones Absolutas

• TSI, Tabla de Símbolos Importados

• TSE, Tabla de Símbolos Exportados

Necesita que usuario le informe de los módulos que se deben enlazar y de las direcciones absolutas deseadas.

Primera función: Generar todas las direcciones absolutas

Para determinar la dirección de comienzo del módulo:

• Existe una sentencia ORG y es un módulo absoluto

• Indicación explícita del usuario al enlazador

• Dirección final del módulo anterior

Segunda función: Proceder a la reubicación del módulo, conocida la dirección inicial

Se deben incrementar en el valor de la dirección inicial del módulo todas las direcciones absolutas de su TDA; así como todas las direcciones de símbolos exportados que están en su TSE (puede hacerlo el cargador).

Una vez realizada la reubicación de todos los módulos, se conoce la dirección absoluta de todos los símbolos exportados.

Para resolver las referencias externas se genera una Tabla Global de Símbolos Exportados (TGSE):

• Uniendo todas las TSE

• La TGSE debe estar bien estructurada pues se realizarán numerosas búsquedas sobre ella

• Hay que comprobar que no existen referencias externas no resueltas

Para resolver las referencias externas de cada módulo se toman las entradas de su TSI y se busca su dirección absoluta en la TGSE; si no existe se da un error.

Tercera función: Copiar todos los módulos en un solo bloque ejecutable

Debe ser manejable por el cargador para proceder a su ejecución; generalmente, se crea un nuevo fichero con extensión de ejecutable (.EXE, .COM, etc.).

Fichero ejecutables

Fichero ejecutable con una única dirección de comienzo

• Es necesario almacenar una imagen exacta del contenido de la memoria principal para la ejecución del programa.

• Se añade únicamente una cabecera con la dirección inicial y su longitud.

• Método muy sencillo

• Genera ficheros innecesariamente grandes

Fichero ejecutable con dirección por palabra

• Se almacena cada palabra efectiva del ejecutable con su dirección

• Permite eliminar las zonas intermedias no usadas

• Añade demasiada cantidad de información sobre las direcciones

Fichero ejecutable con división en bloques con dirección de comienzo

• Dividir el ejecutable en pequeños bloques con direcciones sucesivas

• Añadir la dirección inicial y la longitud de cada bloque

Librerías de programas

Existen librerías generales, matemáticas, de entrada/salida, etc.

Una serie de módulos ensamblados de forma reubicable dan mayor trabajo al enlazador. Este busca los módulos externos en todos los ficheros del sistema con extensión de librería (.lib) y en los ficheros especificados explícitamente.

Programa cargador

Su objetivo es leer un fichero ejecutable almacenado en memoria auxiliar (DD, Cinta, etc.) y traspasarlo a la memoria principal para su ejecución. Debe ser compatible con el formato de salida generado por el enlazador.

Para poder cargar los programas en diferentes zonas de memoria, el cargador reubicador necesita de una Tabla General de Direcciones Absoluta generada por el enlazador combinando la TDA y la TSI de los módulos.

Para que un programa se ejecute, se necesita que el contador de programa apunte a la primera instrucción ejecutable.

5. Sistemas operativos

Introducción

Genéricamente un sistema operativo, S.O. realiza principalmente dos funciones:

Compartir los recursos

Suministrar una máquina virtual o extendida

Gestión de los recursos

Un S.O. debe compartir los recursos del computador entre un número de usuarios simultáneos del sistema. El objetivo es incrementar la disponibilidad del sistema, y al mismo tiempo maximizar la utilización de los recursos compartidos.

Los recursos que se comparten son:

Procesadores

Memoria

E/S

Datos

La importancia de cada recurso depende de su coste. Actualmente hay un decremento de los costes, pero siempre existen recursos escasos.

Máquina virtual

Trata de transformar el hardware en una máquina más fácil de utilizar. Algunas áreas donde la máquina virtual difiere del hardware son:

E/S

Memoria

Sistema de ficheros

Protección y manejo de errores

Interacción con programas

Control de los programas

La naturaleza exacta de una máquina virtual depende de la aplicación en la cual será usada. Su diseño también estará fuertemente influenciado por el uso al que se destine el sistema. Los Sistemas de Propósito General son un problema.

Tipos de Sistemas Operativos

S.O. Mono-Usuario

Ofrecen un máquina virtual para un único usuario

Apropiados para sistemas dedicados a una sola función (CP/M, MS-DOS, ...)

Objetivos:

Lenguaje de comandos fácil de usar

Sistema de ficheros simple

Facilidades de E/S para terminal, disco e impresora

Actualmente, muchos microordenadores soportan multi-tareas

Control de Procesos (Tiempo Real)

Control por parte de un sistema computador de un proceso industrial

La característica común de estas aplicaciones es el feedback:

Recibe entradas desde el proceso controlado

Calcula una respuesta para mantener la estabilidad del sistema

Inicia el mecanismo para dar dicha respuesta

Problema .- Hay un tiempo crítico en el cual se debe dar la respuesta

Su principal función es suministrar la máxima exactitud con la mínima intervención del operador, y si el hardware falla, fallos seguros

Sistemas de Consultas de Ficheros

Sistemas con un gran conjunto de datos, o base de datos, que se consulta para obtener información

Respuesta en un tiempo corto (<1minuto)

Capacidad de modificación de los datos para actualizaciones

Ejemplos: Sistemas de gestión empresarial, sistemas médicos, etc.

El acceso a la información no debe implicar conocimientos (hardware o software) de la organización de la base de datos

El S.O. debe facilitar el acceso a los datos, la respuesta

Sistemas de Procesamiento de Transacciones

Base de datos que se modifica constantemente (reservas de líneas aéreas, operaciones bancarias, etc.)

Necesidad de actualización instantánea de la base de datos

Problema: Accesos simultáneos y limitaciones en el tiempo de respuesta

Deben ser transparentes para el usuario individual

El S.O. debe resolverlos dando la impresión al usuario de que es el único en el sistema

Sistemas de Propósito General

Sistemas con un gran número de usuarios que realizan una gran variedad de tareas

Se diseñan para manejar un flujo continuo de trabajo en la forma de trabajos (jobs) que se ejecutarán en el computador

Cada trabajo realiza una tarea específica para un determinado usuario y, típicamente, ejecuta uno o más programas

Debe tener un gran número de programas de utilidades (software sistemas)

Debe manejar una amplia variedad de periféricos

Suministrar y controlar estas facilidades, junto con la organización del flujo de trabajo, son las funciones genéricas de un S.O. de propósito general

Sistemas Batch .- Cuando un trabajo entra en el computador el usuario no tiene ya más contacto con el trabajo hasta que este termina y, típicamente, ejecuta uno o más programas

Sistemas multi-acceso o interactivos .- El usuario puede ejecutar uno o más programas tecleando en el terminal; y utilizarlo para monitorizar y controlar la ejecución de sus programas

La mayoría de los sistemas operativos combinan ambos modos de operación:

Modo Interactivo .- Desarrollo de programas y preparación de documentos

Modo Batch .- Tareas rutinarias no interactivas y trabajos con un gran tiempo de ejecución

Funciones y Características de un Sistema Operativo

Funciones de un S.O. Un poco de historia

El punto de partida fue la máquina sola (hardware), es decir, la CPU, la memoria, los periféricos E/S. Sin el software la carga y la ejecución de programas eran realizadas por el usuario.

Algunos ejemplos son los computadores con procesamiento por lotes, con entradas por tarjetas perforadas, con salida por impresora. Las actividades realizadas por el operador para cada trabajo eran:

Poner las tarjetas del programa fuente en el lector

Inicializar un programa de lectura de tarjetas

Arrancar un compilador que compile el programa fuente

Poner las tarjetas de datos en el lector

Iniciar la ejecución del programa compilado

Recoger los resultados de la impresora

La velocidad de la máquina venía determinada por las pulsaciones del operador y su velocidad alimentando los periféricos.

Job Control Language

Primera Mejora .- Automatizar carga, lectura, compilación y ejecución

Funciones Operador .- Cargar las tarjetas y recoger los resultados en la impresora

Precio Pagado .- Dedicar recursos a un programa de control de trabajos

Necesidad de tarjetas de control

El programa de control debe ser capaz de:

Interpretar un lenguaje de control de trabajos (job control language)

Manejar los errores de un trabajo para que no afecten a los siguientes

Velocidad Máquina .- Velocidad E/S

Off-Lining

Mejora .- Realizar toda la E/S sobre cintas magnéticas

La conversión de tarjetas perforadas a cinta se realiza en un ordenador satélite de bajo coste

La transferencia de las cintas magnéticas se hace a mano

Precio .- Conjunto de rutinas para codificación y empaquetado de datos en cinta magnética

Como la cinta es un medio de almacenamiento serie, no existía el concepto de planificación de trabajos

Interrupciones y canales

Mejora .- Eliminar la dependencia de E/S. Solapar E/S con procesamiento.

Dos características HW: Canal e Interrupciones

Un canal es un dispositivo que controla uno o más periféricos, realizando las transferencias de datos entre Memoria y los Periféricos con una mínima intervención de la CPU

Una interrupción es una señal que transfiere el control de la CPU a una posición fija, salvando simultáneamente el valor previo del CP.

Una interrupción desde un canal le indica a la CPU que la transferencia de datos ha terminado

Permiten leer trabajo desde cualquier tipo de dispositivo y ejecutarlos de uno en uno en cualquier orden

Precio .- Rutina de Manejo de Interrupciones; Planificador (scheduler)

El planificador sirve para decidir cuál de los trabajos seleccionados en el disco será el siguiente en ejecutarse

Mitad 60. Single-Stream Batch Monitor

Multiprogramación

Mejora .- Ejecutar varios programas simultáneamente

Es posible mantener varios programas al mismo tiempo en memoria dividiendo el tiempo de CPU entre ellos en función de los recursos que cada uno necesita

Objetivo .- Conseguir una utilización óptima de los recursos

Precio .- Control de los Recursos y la protección de los trabajos

Principios 70. Multi-Stream Batch Monitor

Multi-Acceso

Mejora .- Permitir interacción entre usuario y ordenador; muy importante en el desarrollo y la depuración de programas

Aceptar entradas desde terminales remotos, sistema multi-acceso

Precio .- Control y protección de usuarios simultáneos

Principios 70 - Mediados 70. Multi-Acceso + Multi-Programación

Nuevas facilidades - Redes de ordenadores

Sistemas con varios S.O. simultáneamente

Facilidades de comunicación entre ordenadores

Redes de ordenadores. S.O. distribuidos

Un sistema operativo debe realizar las siguientes funciones:

Secuenciamiento de trabajos

Interpretación de un lenguaje de control

Manejo de errores

Manejo de E/S

Manejo de interrupciones

Planificación (scheduling)

Control de recursos

Protección

Multi-Acceso

Adicionalmente:

Ofrecer un buen interfaz con el usuario (usuario)

Permitir contabilidad de los recursos (administrador)

Características de un Sistema Operativo

Concurrencia

Concurrencia es la existencia simultánea de varias actividades

Ejemplos .-

Solapamiento E/S y procesamiento CPU

Coexistencia de varios programas en Memoria Principal

Problemas .-

Conmutación entre actividades

Protección de una actividad frente a los efectos de otras

Sincronización entre actividades mutuamente dependientes

Compartir recursos

Actividades concurrentes pueden necesitar compartir recursos o información

Motivos

Coste .- No tiene sentido suministrar todos los recursos a todos los usuarios por separado

Aprovechar el trabajo realizado .- Usar programas y rutinas de otros

Datos compartidos .- Usar los mismos datos para diferentes programas, posiblemente de varios usuarios

Evitar redundancias .- Compartir una única copia de un programa (editor, compilador, ...)

Problemas

Asignación de recursos

Acceso simultáneo a datos

Ejecución simultánea de programas

Protección contra corrupción de datos y programas

Almacenamiento a largo plazo

Necesidad de datos y programas compartidos implica la necesidad de almacenar la información a largo plazo

Evita almacenamiento en medios externos

Problemas .-

Facilidad de acceso

Protección contra interferencias (maliciosas o no)

Protección contra fallos del sistema

Tratar sucesos no determinísticos

Un S.O. debe ser determinístico en el sentido que un mismo programa que se ejecuta con los mismos datos debe producir siempre el mismo resultado

Indeterminado, debe responder a sucesos que ocurrirán en un orden no predecible

Peticiones de recursos, errores de ejecución, interrupciones de los periféricos, ...

Un S.O. debe diseñarse para tratar cualquier secuencia de eventos

Características deseables

Eficiencia

Dificultad para encontrar un único criterio que la mida

Criterios

Tiempo medio entre trabajos por lotes

Tiempo de CPU no usado

Tiempo de espera para trabajos por lotes

Tiempo de respuesta en sistemas multiacceso

Utilización de recursos

“throughput, jobs/h”; velocidad de trabajo en terminales

No se pueden satisfacer simultáneamente

Coste recursos humanos vs. Coste recursos materiales

Confiabilidad

Idealmente, un S.O. libre de errores y capacidad de tratar todas las posibles contingencias

Práctica, nunca es posible

Mantenibilidad

Debe ser posible mantener el S.O.

Mejorándolo

Corrigiendo errores

El S.O. debe ser:

Modular

Interfaces entre módulos claramente definidos

Bien documentado

Pequeño tamaño

El espacio que ocupa el S.O. es un espacio perdido para las aplicaciones

Gran tamaño aumenta las posibilidades de errores y de tiempo de desarrollo

Programas, Procesos y Procesadores

Procesadores

Un proceso puede llevarse a cabo gracias a un Agente en el cual se ejecuta el programa asociado a este proceso, un procesador.

Un procesador ejecuta un proceso; un proceso se ejecuta en un procesador

Un procesador es algo en lo que se ejecutan instrucciones:

Hardware

Hardware + Software

Concurrencia

Ocurre con la activación de varios procesos al mismo tiempo.

Concurrencia verdadera. N procesadores y N procesos concurrentes,

Concurrencia aparente. Si hay menos procesadores que procesos; conmutación en un procesador de un proceso a otro

Un procesador debe almacenar cierta información:

Sobre el proceso que se está ejecutando

Antes de poder conmutar a otro proceso

Debe ser suficiente par permitir la reanudación del proceso posteriormente

El procesamiento es concurrente; si se realizara una foto del sistema completo se encontrarían varios procesos entre su punto de entrada y su punto de salida, concurrencia verdadera y aparente.

Procesos No Deterministas

Proceso como secuencia de acciones que pueden ser interrumpidas entre cualquier paso. Estas interrupciones ocurren en un orden impredecible.

Una interrupción debe ir asociada con el almacenamiento de la información necesaria para reanudar el proceso interrumpido.

Un proceso es una secuencia de acciones (dinámico). Un programa es una secuencia de instrucciones (estático). Un procesador es un agente para ejecutar un proceso.

No determinista y concurrencia: Interrupción de procesos entre acciones y conmutación de procesos en el procesador.

Se da la necesidad de mantener la información suficiente sobre los procesos para que éstos puedan reanudarse en momentos posteriores.

Procesos concurrentes

omunicación entre procesos

Los procesos en un sistema computador no actúan aislados. Deben cooperar para alcanzar los objetivos deseados y deben competir por los recursos del sistema

Cooperación y competición: comunicación entre procesos

Exclusión mutua

Sincronización

Interbloqueo

Semáforos

Signal(s)

Efecto: Incrementar el valor del semáforo `S' en uno; la operación de incremento debe ser una operación

rementar(S)

Signal(s)

Incrementar(s)

val(sem) = C(sem) + ns(sem) - nw(sem)

val(sem) es el valor del semáforo sem

C(sem) es su valor inicial

ns(sem) es el número de operaciones signal sobre él

nw(sem) es el número de operaciones wait sobre él

Por definición,

val(sem) >= 0

Se deriva la importante relación

nw(sem) <= ns(sem) + C(sem)

que cumple la igualdad estricta si:

val(sem) = 0

Exclusión mútua

Protección frente a accesos simultáneos a recursos no compartibles

Prevenir que los procesos ejecuten concurrentemente las zonas del programa donde se accede al recurso

Sección crítica.- esas zonas del programa

Exclusión mutua de recursos mediante exclusión mutua de las secciones críticas

Exclusión mutua de una sección crítica.

Encerrándola con wait y signal

wait(mutex);

critical section

signal(mutex);

Donde mutex es el nombre de un semáforo y su valor inicial es 1

Formalmente.

nw(mutex) <= ns(mutex) + 1

Como máximo un proceso puede estar dentro de la sección crítica; la entrada se prohibe solo si otro proceso está ya dentro

Un proceso es detenido solo si el valor de mutex es 0

nw(mutex) = ns(mutex) + 1

Ejemplo

Programa Proceso A

. . .

wait(mutex);

añadir elemento a la cola;

signal(mutex);

. . .

. . .

Programa Proceso B

. . .

. . .

wait(mutex);

quitar elemento de la cola;

signal(mutex);

. . .

. . .

Ejemplo sin semáforos

while puerta = CERRADA do

op_nula;

puerta := CERRADA;

sección crítica

puerta := ABIERTA;

La razón se debe en la separación de la pregunta por la puerta abierta y la operación de cerrar puerta

Los semáforos evitan dificultades similares porque wait y signal son operaciones indivisibles

Existen microprocesadores con instrucciones máquinas de TEST AND SET absolutamente indivisibles

Sincronización

Proceso A no puede pasar de un punto L1 hasta que otro proceso B no haya alcanzado un punto L2

Programa Proceso A

. . .

L1: wait(sem_sync);

. . .

. . .

Programa Proceso B

. . .

L2: signal(sem_sync);

. . .

. . .

donde sem_sync es un semáforo con valor inicial 0.

Formalmente:

nw(sem_sync) <= ns(sem_sync)

lo cual implica que A no puede pasar de L1 antes de que B pase por L2.

Caso de los productores - consumidores

Un conjunto de procesos productores y un conjunto de procesos consumidores

que se comunican por medio de un buffer

dentro del cual los productores depositan items

y los consumidores extraen estos items

Proceso Productor .- produce item - deposita item en el buffer

Proceso Consumidor .- consume item - extrae item del buffer

Buffer de capacidad limitada, máximo N items de igual tamaño

Los problemas aparecen cuando el buffer está lleno o está vacío

0 <= d - e = N

El problema es la protección contra accesos simultáneos al buffer

Programa Productor

repeat indefinidamente

begin

producir item;

wait(s_lleno);

wait(sem_buff);

depositar item en buffer;

signal(sem_buff);

signal(s_vacio);

end

Programa consumidor

repeat indefinidamente

begin

wait(s_vacio);

wait(sem_buff);

extraer item del buffer;

signal(sem_buff);

signal(s_lleno);

consumir item;

end

Sincronización mediante semáforos s_lleno y s_vacio, que se inicializan a N y 0 respectivamente. Exclusión mutua mediante semáforo sem_buff que se inicializa a 1.

Semáforos de Sincronización

nw(s_lleno) <= ns(s_lleno) + N

nw(s_vacio) <= ns(s_vacio)

Observando el orden de las operaciones de los programas tenemos que:

ns(s_vacio) <= d <= nw(s_lleno)

ns(s_lleno) <= e <= nw(s_vacio)

y por tanto

d <= nw(s_lleno)

<= ns(s_lleno) + N

<= e + N

similarmente

e <= nw(s_vacio)

<= ns(s_vacio)

<= d

combinando ambas

e <= d <= e + N

Interbloqueo (deadlock)

Puede ocurrir cuando varios procesos compiten por un mismo recurso

Ejemplo .- Procesos A y B que utilizan los semáforos x e Y cuyos valores iniciales son 1 en ambos casos

Programa Proceso A

. . .

wait(X)

. . .

wait(Y)

. . .

. . .

Programa Proceso B

. . .

wait(Y)

. . .

wait(X)

. . .

. . .

La compartibilidad de un semáforo está determinada por su valor inicial

Si el valor es n (n>1), el semáforo puede compartirse por n procesos

Si el valor es 1, el semáforo no se puede compartir

Otro ejemplo más complejo: productor - consumidor invirtiendo el orden de las operaciones wait del consumidor

wait(sem_buff);

wait(s_vacio);

extraer item del buffer;

signal(sem_buff);

signal(s_lleno);

Interbloqueo puede ocurrir como resultado de una secuencia de operaciones wait en un orden incorrecto

Monitores

La utilización indisciplinada de los semáforos facilita el que se produzcan errores:

Un programador puede fácilmente colocar operaciones wait y signal en los lugares equivocados

O puede olvidar ponerlos donde o cuando debe. Ejemplo: datos compartidos que no se protegen con wait-signal

Construcciones en lenguajes de programación que:

Obliguen al programador a declarar datos/recursos compartidos explícitamente

Y que impongan la exclusión mutua en el acceso a los mismos

Un monitor consta de:

Los datos que son un objeto compartido

Un conjunto de procedimientos que pueden ser invocados para acceder al objeto

Un trozo de programa que inicializa el objeto (este programa se ejecuta únicamente una vez, cuando se crea el objeto)

Ejemplo .- Un buffer para el paso de datos entre un proceso productor y un proceso consumidor

El espacio para el buffer y su puntero

Dos procedimientos, depositar y extraer

Un troza de programa que inicialice los punteros al comienzo del buffer

Un lenguaje que incorpore monitores. Un compilador debe asegurar que los procedimientos de cada monitor se implementan como secciones críticas mutuamente excluyente, generando operaciones wait y signal. La responsabilidad de la exclusión mutua pasa del programador al compilador.

El diseñador de S.O. obtiene la ventaja de restringir todas las operaciones sobre objetos compartidos a un conjunto de procedimientos bien definidos y con la seguridad de que estas operaciones son mutuamente excluyentes.

La sincronización con propósitos distintos a la exclusión mutua siguen siendo responsabilidad del programador.

Núcleo del sistema

El principal interfaz entre el hardware básico de la máquina y el S.O. lo ofrece el núcleo del sistema, que debe suministrar un entorno en el cual puedan existir los procesos:

Manejador de interrupciones

Conmutación de procesos

Mecanismos para la comunicación entre procesos

Prestaciones hardware esenciales

Mecanismo interrupciones

Actividades E/S solapadas con procesamiento en la CPU

Interrumpir cuando termina la transferencia E/S

Un mecanismo interrupción que por lo menos salve el valor del CP del proceso interrumpido y transfiera el control a una posición conocida de memoria

Rutinas interrupción .- Determinan la fuente de la interrupción y la tratan de manera adecuada

Protección memoria

Proteger la memoria usada por un proceso de accesos no autorizados de otros procesos

Mecanismos de protección en el direccionamiento hardware de la memoria

Conjunto de instrucciones privilegiadas

Instrucciones reservadas para uso exclusivo del S.O.

Funciones típicas que realizan:

Habilitar/Deshabilitar Interrupciones

Conmutación de procesos

Acceso registros usados por el hardware de protección de memoria

Entrada/Salida

Parada y control del procesador

Mayoría de computadores operan en más de un modo, típicamente en dos modos:

Modo supervisor .- Pueden usarse las instrucciones privilegiadas

Modo usuario .- No pueden usarse las instrucciones privilegiadas

El cambio de modo usuario a supervisor se realiza automáticamente

Un proceso de usuario llama al S.O. para ejecutar alguna función que necesita utilizar instrucciones privilegiadas (system call)

Se produce una interrupción

Ocurre un error en un proceso de usuario (interrupciones internas o traps). P.E.- Intento de ejecutar una instrucción privilegiada

El cambio de supervisor a usuario se produce ejecutando una instrucción privilegiada

Reloj tiempo real

Para poder implementar cualquier política de planificación y poder controlar los recursos del sistema es esencial contar con un reloj hardware para generar interrupciones a intervalos fijos de tiempo real

Perfil del núcleo

El núcleo consta de tres partes:

El Manejador de Interrupciones de Primer Nivel (MIPN)

El despachador (dispatcher) o Planificador de bajo nivel

Dos procedimientos o rutinas que implementan las primitivas wait y signal

Es la parte del S.O. más dependiente de la máquina. Típicamente, se escribía en lenguaje ensamblador.

Representación de procesos

Estructura de datos con información acerca del proceso. La representación física de los procesos en el sistema viene dada por el descriptor de proceso (bloque de control o vector de estado).

El descriptor de proceso es una zona de memoria que contiene toda la información relevante acerca del proceso:

Identificación (nombre proceso)

Estado

Otras informaciones: Punteros memoria y recursos, punteros a colas diversas, zona reserva registros, etc.

Estados de un proceso

Ejecución .- Si un procesador está ejecutando sus instrucciones

Preparado .- Podría utilizar un procesador si alguno estuviera disponible

Espera o bloqueado .- No puede utilizar un procesador aunque alguno estuviera disponible. Generalmente, está esperando que ocurra algún suceso que le permita continuar

El estado de un proceso es la información clave para el despachador cuando tiene que asignar el procesador

Almacenar toda la información que hay que salvar cuando el proceso pierde el control del procesador:

Valores de los registros

Valores de cualquier registro utilizado en el direccionamiento de memoria

El formato de esta parte del descriptor depende del hardware

Descriptor de Proceso hardware, entorno volatil del proceso .- Sub-conjunto de las facilidades del sistema compartidas y modificables que son accesibles al proceso

Estructura de procesos .- Unión de todos los Descriptores de Procesos del sistema; una lista simple encadenada

Tabla Central del Sistema .- Aparece la Estructura de Procesos; es la estructura de datos básica del S.O. y desde la que accede a las diversas estructuras que posee

Manejador de Interrupciones

El Manejador de Interrupciones de Primer Nivel (MIPN) es responsable de responder a todas las excepciones del sistema; éstas son las siguientes:

Interrupciones .- Sucesos externos asíncronos. Señal externa que le llega al procesador y que hace que el computador altere su flujo de ejecución de instrucciones

Traps o interrupciones SW .- Sucesos internos síncronos. Errores y system calls

Las funciones del MIPN son:

Determinar la fuente de interrupción

Iniciar el servicio de la interrupción

Siempre que se entra al MIPN se para a modo supervisor. En cuanto al hardware debe salvar como mínimo el contador de programa.

También deben salvarse los registros que utilice el MIPN, si no lo hace el hardware lo debe hacer el MIPN como su primera operación; una alternativa será un conjunto extra de registros.

La determinación de la fuente de interrupción será más o menos fácil dependiendo del hardware:

HW distinga entre las distintas fuentes y se salte a distintas posiciones de memoria según la fuente

HW solo indica interrupción, SW realizará una secuencia de tests sobre los distintos flags de estado de las posibles fuentes HW

Métodos intermedios

Interrupciones con prioridad

Normalmente, las interrupciones se deshabilitan cuando se cede el control al MIPN

Asegura que los valores de registros salvados no se machacan si ocurre otra interrupción

Nuevas interrupciones quedan pendientes

Problema: interrupciones con prioridades

El MIPN deshabilita las interrupciones con igual o menor prioridad

Tratamiento de una interrupción

El MIPN llama a una Rutina de Tratamiento de Interrupción (RTI) apropiada al tipo de interrupción recibida.

Conviene que sean cortas

La RTI realiza unas pocas acciones y el resto las deja para un proceso que se ejecutará en modo usuario posteriormente

Cuando ocurre una interrupción puede cambiar el estado de algún proceso

Espera Preparado

Las RTI son las encargadas de modificar el campo de estado del descriptor del proceso afectado

Es posible que el proceso que estaba en ejecución pierda el control de la CPU

Misión del dispatcher

Despachador

Se trata de un Planificador de Bajo Nivel, cuya función es asignar la CPU entre los distintos procesos del sistema.

Es llamado cuando el proceso en ejecución no puede continuar o cuando se sospecha que existe otro proceso que aprovecharía mejor el procesador:

Después de una interrupción que cambia el estado de un proceso

Después de una system call cuyo resultado sea que el proceso en ejecución queda temporalmente imposibilitado para continuar

Después de un error cuyo resultado es la suspensión del proceso en ejecución mientras se trata el error

Estos son todos casos especiales de excepciones. El despachador se invoca después de todas las excepciones.

Operaciones

Si el proceso en ejecución es el más adecuado para ejecutarse le devuelve el control en el punto salvado por la interrupción y termina

Si no es el más adecuado, salva el contexto volátil del proceso en su descriptor

Recupera el contexto volátil del proceso seleccionado para ejecutarse

Transfiere el control al nuevo proceso seleccionado, en la posición indicada por el CP recuperado

El proceso más adecuado para ejecutarse:

Ordenar todos los procesos preparados según algún tipo de prioridad

La asignación de prioridades en el planificador de alto nivel

Ejemplo

Cola proceso

Cola ordenada por prioridades creciente de modo que el siguiente proceso elegible esté el primero de la cola

RTI que modifica estado proceso

Introducir el descriptor del proceso en la cola en la posición adecuada

Problema

Proceso nulo

Alternativas

Varias clases de procesos ejecutables

Resumen

Mecanismo interrupción

Salvar CP

Salvar otros registros (opcional)

Llamar MIPN

MIPN

Salvar registro que utiliza (si no se salvaron)

Identificar interrupción (ayudado por hardware)

Llamar a una RTI

RTI

Atender la interrupción

Posibilidad de modificar el estado de un proceso

Despachador

¿Conmutación de proceso? Si no, continuar con el proceso en ejecución

Salvar contexto volátil del proceso en ejecución

Recuperar contexto volátil del proceso en la cola

Transferir control al nuevo proceso

Implementación wait y signal

Hay que implementar algún mecanismo de comunicación entre procesos, para ello se emplean las operaciones wait y signal. Las cuales se incluyen en el núcleo porque:

Deben estar disponibles para todos los procesos

Su resultado puede ser bloquear un proceso, provocando una llamada al dispatcher

Una RTI puede despertar un proceso mediante la ejecución de signal sobre el mismo semáforo donde el proceso ejecutó un wait

Bloquear y desbloquear

La operación wait implica un bloqueo potencial del proceso, y signal la liberación de un proceso

Implementación mediante una cola asociada a cada semáforo

wait(s)

if s<>0 then s:=s-1

else añadir proceso cola y

estado proceso = ESPERA

signal(s)

if cola VACIA then s:=s+1

else quitar proceso cola y

estado proceso = PREPARADO

Encolar y desencolar

Para saber qué proceso se quita de la cola después de un signal, hay que conocer su estructura:

Primero Entrar, Primero salir (FIFO)

Por prioridades

Diferentes semáforos pueden tener diferentes tipos de organización de cola

Asignación del procesador

wait y signal pueden alterar el estado de un proceso

Si lo modifican se debe llamar al dispatcher

Por simplicidad, aunque no se modifique el estado de ningún proceso, siempre se llama al disptacher; éste debe reanudar el proceso en ejecución que será el primero en la cola

Indivisibilidad

wait y signal deben ser operaciones indivisibles

necesidad de alguna clase de operación de cierre

Implementar la operación de cierre

Deshabilitando las interrupciones

Instrucción de Test and Set

Instrucción para intercambiar el contenido de dos posiciones de memoria

Los dos mecanismos de cierre mediante instrucciones especiales provocan una espera ocupada

Diferencias entre wait/signal y operaciones de cierre

	wait y signal	Lock y Unlock
Propósito	Sincronización Genérica procesos	Exclusión Mutua de procesos desde wait/signal
Nivel Implementación	Software	Hardware
Mecanismo Retardo	Colas	Espera Ocupada/ Inhibir Interrupciones
Tiempo Retardo Típico	Varios segundos	Varios microsegundos

Gestor de memoria

El siguiente nivel después del Núcleo es el Gestor de Memoria. Es necesario cuando un proceso que no tiene asignada algo de memoria apenas puede realizar pocas cosas o ninguna.

Objetivos

Reubicación

Memoria debe ser compartida

El programador no conoce donde se cargará su programa; no puede escribir sus programas en términos de direcciones absolutas

La memoria asignada a los programas no permanece fija durante toda la ejecución

No puede realizar la reubicación al cargar

Puede ser necesario mover los programa en memoria

La región de memoria asignada a un proceso puede cambiar durante el tiempo de vida del proceso

S.O. responsable de transformar las direcciones usadas por el programador a las direcciones físicas asignadas al proceso

Protección

Ningún proceso tiene permitido modificar el contenido de las posiciones de memoria asignadas a otro proceso

Las comprobaciones en Tiempo de Compilación no sirven; hay lenguajes que permiten cálculos de direcciones dinámicamente en tiempo de ejecución

Todas las referencias de memoria generadas por un proceso deben ser comprobadas en tiempo de ejecución

Compartir la memoria

Existen ocasiones donde varios procesos deben acceder a las mismas posiciones de memoria

Gestor de Memoria debe permitir accesos controlados a las áreas de memoria compartida

Organización Lógica

Espacio de direcciones lineal o de una dimensión; reflejo del hardware pero no de la forma en que se escriben los programas

Mayoría de programas son estructurados; referencian distintas áreas de datos modificables o no modificables

Segmentación del espacio de direcciones

Codificarlos independientemente

Referencias entre segmentos se pasan a tiempo de ejecución

Darles diferentes grados de protección

Crear mecanismos mediante los cuales se puedan compartir los segmentos entre varios procesos

Organización física

Históricamente, dos niveles de almacenamiento

Compromiso entre velocidad/coste

Acceso M.P. varios nanosegundos

Acceso discos varios milisegundos

Unicamente la información en M.P. es accesible directamente por la CPU

Transferencias de Información entre Memoria Principal y Memoria Secundaria

Responsabilidad del Programador : Overlays

Compiladores pueden generar automáticamente el código para los overlays; en muchos casos les falta información

Si hay reubicación dinámica es imposible hacerlo

La responsabilidad de mover información entre los dos niveles de memoria debe ser del S.O.

Memoria Virtual

Es un mecanismo de transformación de direcciones; convierte las direcciones usadas por el programador en las correspondientes posiciones de memoria física realmente asignadas al programa durante su ejecución.

Las direcciones virtuales son referenciadas por el programa al ejecutarse o utilizadas por el programador. Las direcciones reales son posiciones de memoria disponibles en la memoria principal.

El espacio de direcciones virtuales (o Espacio de Direcciones), N, viene dado por el conjunto de direcciones virtuales que pueden ser referenciadas por un proceso.

El espacio de direcciones reales (o Espacio de Memoria), M, se da por el rango de posiciones de memoria en el sistema computador.

El mecanismo de transformación se puede poner como:

f : N M

El espacio de memoria es generalmente lineal, y su tamaño viene dado por la cantidad de Memoria Principal incluida en la configuración.

El espacio de direcciones no necesita ser lineal, generalmente es de dos dimensiones; y su tamaño puede ser mayor, igual o menor que el del Espacio de Memoria.

Suele permitir al programador utilizar un rango de direcciones diferentes al real; el programador ve una memoria virtual con características diferentes a las de la memoria real.

Implementación de memoria virtual

Registros base y límite

La reubicación y la protección se pueden conseguir con un mecanismo simple de registros base y límite

Cuando un proceso se carga en memoria la dirección de la posición más baja que usa se pone en un registro base

Todas las direcciones del programa se interpretan como relativas a este registro base

f(a) = B + a

a Dirección del programa

B Dirección base del proceso

Para la reubicación hay que mover el proceso y dar el nuevo valor al registro base

Para la protección se añade un segundo registro que contendrá la dirección de la posición más allá que puede utilizar el proceso, el registro límite

La transformación de direcciones se realiza según el siguiente esquema

if a<0 then Violacion Memoria

a':= B + a

if a'>limite then Violacion Memoria

a' es la posicion solicitada

El problema es el tiempo consumido en las operaciones, los registros deben implementarse en hardware rápido

Una alternativa es usar longitud en lugar de la dirección limite'

if a<0 OR a>longitud

then Violacion Memoria

a' := B + a

a' es la posicion solicitada

Paginación

Con el Método Registros Base-Límite, el Espacio de Direcciones es necesariamente menor o igual que el Espacio de Memoria

Es necesario que la Memoria Virtual sea mayor que la memoria física disponible

Almacenamiento de nivel uno .- La memoria secundaria aparece como una extensión de la memoria principal (1.960, Universidad Manchester - Atlas)

Este almacenamiento puede realizarse mediante una técnica denominada paginación

Paginación

El Espacio de Direcciones Virtuales se divide en páginas de igual tamaño (p.e.: 512 bytes)

La Memoria Principal también se divide en marcos de páginas del mismo tamaño que las páginas

Los marcos de páginas se dividen entre los procesos actualmente presentes en el sistema; en un instante determinado, un proceso tendrá unas pocas páginas residentes en Memoria Principal (página activa) y el resto residentes en la Memoria Secundaria (página inactiva)

El mecanismo de paginación tiene dos funciones

Realizar la operación de transformación de direcciones

Transferir las páginas entre Memoria Secundaria y Memoria Principal

Los bits de mayor orden de las direcciones se interpretan como un número de página

Los de menor orden como un desplazamiento, en bytes, dentro de la página

Páginas de 2n bytes: los n bits de menor peso de las direcciones representan el desplazamiento y el resto el número de página

Estos cálculos son función exclusiva del hardware y son transparentes al programador, éste solo sabe que puede programar en un gran espacio de direcciones secuenciales

La transformación de direcciones se realiza por medio de una Tabla de Páginas donde

La entrada p-ésima contiene la posición p' del marco de página donde reside la página p

El desplazamiento, b, se le suma a p' para obtener la posición requerida

La transformación se puede poner como:

f(a) = f(p,b) = p' + b

donde

a Dirección de programa

p Número de página

b Desplazamiento

y si z es el tamaño de página, entonces:

p = parte entera (a/z)

b = resto (a/z)

Las referencias a una página que no está presente en Memoria Principal se conocen como fallo de página; esto provoca que el mecanismo de paginación inicie la transferencia de la página solicitada desde la Memoria Secundaria a la Memoria Principal y que se actualice adecuadamente la Tabla de Páginas

En el bit de presencia, para cada entrada, se indica si la página está o no presente en Memoria Principal

Si el bit de presencia no está activo, es necesario conocer la posición de la página en Memoria Secundaria (en la misma Tabla o en otra diferente)

El problema es cuando no existe ningún marco de página vacío cuando ocurre un fallo de página, por lo que alguna página debe moverse a Memoria Secundaria para poder cargar la nueva página

El Algoritmo de Cambio de Páginas se basa en diversas informaciones sobre las páginas

Es necesario que cada entrada de la Tabla de Páginas contenga unos pocos bits cuya información podría ser

Cuántas veces ha sido referenciada la página

El tiempo de la última referencia a la página

Bit de modificación indicando se la página ha sido modificada (escrita)

Estas informaciones las mantiene el hardware. Así como realiza las operaciones de transformación de direcciones; excepto cuando ocurre un fallo de página que será el S.O. el encargado de buscar la página solicitada en la Memoria Secundaria y, si es necesario, elegir la página que hay que quitar de Memoria Principal

El tiempo necesario para cada referencia a memoria es doble debido a la necesidad de acceder primero a la Tabla de Páginas

Tabla de Páginas en un conjunto de Registros de alta velocidad de acceso

Memoria Asociativa, búsqueda simultánea en paralelo

Gran cantidad de Memoria Principal que puede ocupar la propia Tabla de Páginas

Puede reducirse al número de páginas realmente usadas y acceder mediante hashing en lugar de mediante indexación

Incremento en el tiempo de acceso a memoria de algunas referencias

Tiempo de cálculo de la función de hash

Si existen colisiones en alguna entrada, se deben realizar más de una entrada mediante la función de hash

Segmentación

Refleja la división lógica entre datos y código

Divide el espacio de direcciones en segmentos, cada segmento se corresponde con un procedimiento, módulo o conjunto de datos

La forma más simple es asignar a cada segmento un par de registros base-límite; esto implicaría pocos segmentos por razones económicas y no realiza ningún tipo de protección

Usar un gran número de segmentos y referenciarlos por los nombres dados por el programador; el espacio de direcciones tendrá dos dimensiones: nombre segmento y dirección

La dirección virtual se da como (s, a) donde

s número del segmento

a dirección dentro del segmento

En la Tabla de Segmentos para cada proceso, la entrada s-ésima contiene posición base y longitud (descriptor segmento)

La operación de transformación será

Extraer la dirección de programa (s, a)

Usar s como índice de la tabla de segmento

Si a<0 or a>1 entonces Violación de memoria

(b+a) es la posición buscada

Protección .- Conjunto de Bits de Protección que especifican los modos de acceso a cada segmento; estos bits pueden ser diferentes en cada descriptor

Compartir segmentos .- Solo se necesita tener un descriptor del segmento en la tabla de segmentos de cada proceso que lo comparte

Diferencias con la paginación

El propósito de la Segmentación es la división lógica del espacio de direcciones; el propósito de la Paginación es la división física de la memoria para implementar el almacenamiento de nivel - uno

Las páginas son de un tamaño fijo determinado por la arquitectura de la máquina; los segmentos pueden ser de cualquier tamaño determinado por el usuario

La transformación de las direcciones la realiza el hardware en la paginación; la división entre segmentos y desplazamiento es puramente lógica

Un desbordamiento de un byte en una página incrementa automáticamente el número de página; en el caso de desbordamiento en un segmento se produce una Violación de Memoria

La principal complicación es que para programas grandes no es posible mantener todos los segmentos en la Memoria Principal, resulta más complicado si se comparte la memoria (multiprocesamiento)

La solución reside en emplear paginación o sustituir segmentos completos en memoria

Segmentación paginada .- Cada segmento consta de varias páginas y posee su propia Tabla de Páginas

La entrada de la Tabla de Segmentos apuntará a la tabla de Páginas de cada segmento

La operación de transformación de direcciones consistirá en

extraer la dirección de programa (s,a)

usar s como indice de la tabla de segmento

si la entrada s esta vacia entonces crear una nueva Tabla de Pagina (vacia); en otro caso, extraer la direccion de la Tabla de Paginas

separar la direccion de desplazamiento a, en un numero de pagina, p, y un desplazamiento, d, dentro de la pagina

usar p como un indice de la Tabla de Paginas

si a<0 or a>1 entonces Violacion Memoria

(b+a) es la posicion buscada

Si no se emplea Paginación, un fallo de segmento provocará que el segmento solicitado se traiga completo a la Memoria Principal

Ventajas del uso de páginas

No se necesita tener completamente en Memoria Principal los segmentos

Las páginas de un mismo segmento pueden ocupar posiciones que no sean contiguas

Ejemplo .- Intel 80386, segmentos paginados. Unidad paginación y Unidad segmentación separadas

Estrategias de asignación de memoria

Básicamente las estrategias de gestión de memoria se dividen en tres grandes grupos:

Estrategias de sustitución .- qué información será retirada de la memoria principal

Estrategias de búsqueda .- cuando la información será cargada en memoria

Estrategias de colocación .- donde se colocará la información en memoria principal

Las estrategias de sustitución y de colocación son diferentes para sistemas paginados y no paginados. Tamaño fijo de las páginas frente al tamaño variable de los bloques de información en sistemas no paginados.

Estrategias de colocación en sistemas no paginados

Cada cierto tiempo los segmentos (bloques de información) son insertados o sacados de la memoria

Cuando el sistema está en equilibrio, la memoria tendrá trozos ocupados con información y otros vacíos

Cualquier estrategia de colocación debe mantener una lista de las posiciones y tamaños de todos los huecos sin asignar, lista de huecos

La tarea será decidir qué hueco se usa y actualizar la lista de huecos después de cada inserción

Si el segmento que hay que poner en Memoria Principal es menor que el hueco encontrado, se pone en las posiciones más bajas del hueco creando un único hueco de menor tamaño

Minimizar la fragmentación

Si es mayor que cualquier hueco disponible, mover los segmentos en memoria para crear un hueco de suficiente tamaño

Algoritmos .- El tamaño de los huecos lo designaremos por x1, ..., xn

Mejor encaja .- La lista de huecos se ordena según tamaños crecientes x1 " x2 " ... " xn. Si s es el tamaño del segmento, buscar el hueco i más pequeño que cumpla s " x i

Peor encaja .- La lista de huecos se ordena según tamaños decrecientes, x1 " x2 " ... " xn. Colocar el segmento en el primer hueco de la lista, es decir, en el más grande

Primero encontrado .- La lista se ordena según las direcciones base de los segmentos; se busca el menor hueco que cumpla s " x i , es decir, el primero que se encuentre donde quepa el segmento

Primero encontrado con rotación .- Es una variación del anterior donde la posición de la cabecera de la lista va avanzando cíclicamente un elemento después de cada búsqueda; evita la existencia de un gran número de huecos pequeños al principio de la memoria, lo cual consume mucho tiempo de búsqueda

Buddy (compañero) .-

Los tamaños de los segmentos deben ser potencias de 2, s = 2i, para algún i menor que un límite k

Se mantienen listas separados de huecos para cada tamaño 21, 22, ..., 2i, ..., 2k

Un hueco se quita de la lista (i+1) dividiéndolo en dos huecos de tamaño mitad que se ponen en la lista (i)

Dos huecos contiguos en la misma lista (i) crearán un único hueco de la lista (i+1)

Se implementa mediante un procedimiento recursivo

procedure coger_hueco(i)

begin

if i=k+1 then fallo;

if lista-i vacia then

begin

coger_hueco(i+1);

dividir hueco en dos

`compañeros';

ponerlos en la lista-i

end;

coger el primer hueco en la lista-i

end

Fragmentación

Un problema común a todas las estrategias de colocación es la fragmentación

La memoria se va dividiendo en huecos cada vez más pequeños que no se pueden utilizar en la práctica

Necesidad de compactación de la memoria, mover todos los segmentos hacia una parte de la memoria y crear un único hueco del tamaño máximo posible

Estrategias de colocación en sistemas paginados

Poner p páginas en Memoria Principal consiste únicamente en buscar p marcos de páginas libres; posiblemente usando una estrategia de sustitución

Existe fragmentación interna, debido a que el tamaño solicitado por un proceso no suele ser un múltiplo exacto del tamaño de página

Una parte del último marco de página asignado estará generalmente desperdiciado. Como media se desperdiciará la mitad del tamaño de página por segmento presenta en memoria

Estrategias de sustitución en sistemas paginados

Decidir que bloques de información serán relegados a la Memoria Secundaria cuando no se encuentre espacio suficiente para un nuevo bloque

Idealmente, se desearía sustituir las páginas que tardarán más en ser referenciadas

Algoritmo irrealizable

Inferir del comportamiento pasado, los posibles comportamientos futuros

Las páginas que no han sido modificadas no es necesario transferirlas de nuevo a Memoria Secundaria

Los algoritmos más comunes de sustitución son:

Menos recientemente usada (LRU; Less Recently Used) .- Sustituir la página que se ha usado menos recientemente; necesita almacenar la secuencia de accesos a todas las páginas

Menos frecuentemente usada (LFU; Less Frecuently Used) .- Sustituir la página que se ha usado menos frecuentemente durante un intervalo de tiempo; problema con las últimas páginas cargadas

FIFO (First In First Out) .- Sustituir la página más antigua en memoria; almacenar los tiempos de carga de cada página.

Problema con página antiguas que se usan mucho;

p.e.: S.O.

Asociar a cada página dos bits de información

Bit R de referencia, se activará cuando la página se lee o escribe; cuando se referencia

Bit M de modificación, se activará cuando se escribe en una página

No usada recientemente (NRU; No Recently Used) .- Aproximación simple al LRU, retira una página de la clase de numeración inferior, eligiéndola al azar dentro de dicha clase

- Clase 0 R=0 M=0 - Clase 2 R=1 M=0

- Clase 1 R=0 M=1 - Clase 3 R=1 M=1

Cuando se carga una nueva página R y M serán cero. En cada interrupción de reloj todos los bits R se hacen cero

FIFO Modificado o FIFO R-M .- Inspecciona los bits R y M y aplica FIFO a la clase de numeración inferior

Segunda Oportunidad .- Otra variación del algoritmo FIFO. Examina la página más antigua

Si R=0 la sustituye

Si R=1, hace R=0, la coloca como la página más nuev ay examina la siguiente

Si todas tienen R=0 quita la más antigua

Páginas al azar

Estrategias de sustitución en sistemas no paginados

Objetivo .- Sustituir el segmento o bloque de información que será menos referenciado en el futuro inmediato

Son aplicables las mismas estrategias que en sistemas paginados

Diferencia porque no todos los segmentos ocupan la misma cantidad de memoria

El tamaño del segmento influirá en la decisión del segmento que se sustituirá

Algoritmo más simple .- Sustituir el segmento cuyo tamaño unido a los posibles huecos contiguos a él, dejen libre el suficiente espacio de memoria para el nuevo segmento

Si existen varios segmentos que cumplen la condición anterior; se puede usar uno de los algoritmos de sistemas paginados, p.e.- LRU

Si no existe ninguno, elegir el menor conjunto de segmentos contiguos que dejen libre suficiente espacio de memoria

La elección por tamaño puede quitar segmentos que se referenciarán inmediatamente

LRU y algo de compactación cuando sea necesario

Tamaño del segmento, referencias futuras y compactación producirán algoritmos complejos

Estrategias de búsqueda

Objetivo .- Determinar cuando mover un bloque de información desde la memoria secundaria a la memoria principal

Por demanda

En anticipación

Las estrategias de demanda son más fáciles de implementar

Cuando se produce un fallo de página/segmento se genera una petición de búsqueda del nuevo bloque

Las estrategias de anticipación se basan en las predicciones del comportamiento futuro de los programas

La naturaleza de la construcción de programas

Inferir del comportamiento pasado de un proceso

Operación en un contexto .- En cualquier intervalo de tiempo un programa tiende a operar dentro de un módulo lógico particular

Principio de localidad (Denning, 1970)

Las referencias de un programa tienden a estar agrupadas dentro de un reducido número de posiciones de memoria y estas posiciones solo tienden a cambiar intermitentemente

Propiedad empírica (observada) más que teórica

Nunca está garantizada pero es probable

Durante un intervalo de tiempo, un proceso tiende a concentrar sus referencias en un subconjunto determinado de páginas

Localidad temporal .- Las posiciones referenciadas recientemente tienen una alta prioridad de ser referenciadas próximamente

Localidad espacial .- Las posiciones de memoria cercanas a las posiciones referenciadas recientemente es muy probable que también sean referenciadas

Modelo del conjunto de trabajo

El modelo del conjunto de trabajo del comportamiento de los programas (Denning, 1968) es un intento de explicar el rendimiento de los sistemas paginados en un entorno de multiprogramación

Los procesos para ejecutarse correctamente deben tener su conjunto de trabajo en memoria principal. Si el grado de multiprogramación rebasa un cierto nivel se produce trasiego continuo entre memoria secundaria y memoria principal.

Un proceso necesita un cierto número mínimo de páginas, llamado conjunto de trabajo, residentes en memoria principal, antes de poder usar efectivamente el procesador.

Para evitar el trasiego el grado de multiprogramación no debe ser mayor que el nivel para el cual todos los procesos pueden mantener su conjunto de trabajo en memoria principal.

Basado en el Principio de Localidad; en un instante de tiempo dado, t,

w(t,h) = { página i | página i E N y página i aparece en las últimas h referencias }

Las páginas del conjunto de trabajo cambian lentamente.

Estrategia de sustitución

Ejecutar un proceso si y solo si su conjunto de trabajo está completo en memoria principal

Y nunca sustituir una página que forme parte del conjunto de trabajo de un proceso

Implica una relación entre la Gestión de Memoria y la Gestión del Procesador.

Conclusión .- El verdadero conjunto de trabajo de un proceso es el conjunto de páginas que deben estar en memoria principal para que el proceso se ejecute eficazmente.

Los conjuntos de trabajo son transitorios y el siguiente conjunto de trabajo del proceso puede diferir sustancialmente del anterior.

Ejemplo de implentación

La mayoría de las estrategias están basadas en el sentido común y en la experiencia

Elección basada en una simulación con una mezcla de los trabajos típicos del sistema

Podemos añadir al entorno volátil del descriptor de cada proceso

Una copia del contenido de los registros base y límite

O un puntero a su tabla de segmentos

O un puntero a su tabla de páginas

Si el sistema es no paginado, introduciendo en la tabla central la lista de huecos libres

Entrada y Salida

Es una de las áreas más sórdidas del diseño del S.O., pues existen gran variedad de dispositivos periféricos que pueden diferir en:

Velocidad .- Diferencias de varios órdenes de magnitud en la velocidad de transferencia de datos (1M cps - 1 cps)

Unidad de transferencia .- Caracteres, words, bytes, bloques o registros

Representación de datos .- Codificación de diferentes formas, incluso en el mismo dispositivo

Operaciones permitidas .- Clase de operaciones que pueden realizar; p.e.: entrada o salida

Condiciones de error .- Los fallos pueden tener causas diversas

Objetivos de diseño

Independencia de código de caracteres

No es deseable que el programador necesite conocer los detalles de los códigos de caracteres utilizados

El sistema E/S debe reconocer diferentes códigos y presentar un único formato estándar al usuario

Independencia del dispositivo

Un programa debería ser independiente de los dispositivos particulares que le pueden ser asignados y del tipo de dispositivo usado para sus E/S

Eficiencia

La E/S suele ser un típico cuello de botella del S.O.

Debe ser lo más eficiente posible

Tratamiento uniforme de los dispositivos

Manejar todos los dispositivos de manera uniforme

Difícil en la práctica

La independencia del código de caracteres implica la existencia de una representación interna de todos los caracteres uniforme

Código de caracteres interno

Traducción .- inmediatamente después de la entrada; e, inmediatemante antes de la salida

La independencia de los dispositivos implica que un programa debe trabajar sobre dispositivos virtuales

Streams (Atlas), files (Unix), o data sets (IBM)ç

La asociación de los streams con los dispositivos reales la hace el S.O. basada en cierta información suministrada por el usuario

Especificar solo el tipo de dispositivo

Una lista de descriptores de stream, apuntada desde el descriptor de proceso

La asignación de un dispositivo a un proceso se hace cuando el proceso utiliza la primera vez el correspondiente stream

El proceso abre el stream

El stream se cierra, explícitamente desde el proceso o cuando el proceso finaliza

El sistema de E/S debería ser construido de forma que las características del dispositivo estén claramente asociadas con los dispositivos y no con las rutinas que los manejan (manejadores de dispostivos).

Las características distintivas de cada dispositivo se deben codificar en un descriptor de dispositivo. Este descriptor se utiliza como fuente de información para los manejadores:

Identificación

Instrucciones para operar con el dispositivo

Punteros a las tablas de traducción de caracteres

Status actual: ocupado, libre o caído

Proceso de usuario actual: un puntero al descriptor de proceso que está utilizando actualmente

Todos los descriptores pueden reunirse juntos en una estructura de dispositivos cuya cabecera está en la Tabla Central.

Procedimientos de E/S

DOIO (stream, modo, cantidad, destino, semáforo)

DOIO .- Nombre de un procedimiento E/S del sistema

stream .- número del stream en el que tiene lugar la E/S

modo .- que operación se solicita (opcional, el código de caracteres)

cantidad.- cantidad de datos a transferir

semáforo .- dirección de un semáforo de petición servida el cual será señalizado cuando termina la operación de E/S

DOIO es reentrante y su función consiste en:

Asociar el número de stream con el dispositivo físico apropiado de la lista de descriptores de streams del proceso

Chequear los parámetros consultando la información en el descriptor del stream

Iniciar el servicio de la petición, ensambla los parámetros de la petición en un Bloque de Petición de E/S (IORB) que añade a una cola de bloques similares de otras peticiones

Cola de Peticiones del Dispositivo unida al descriptor del dispositivo y servida por un proceso separado denominado Manejador de Dispositivo

El procedimiento de E/S señala un semáforo de petición pendiente (descriptor del dispositivo) como indicación al Manejador. Este avisará al proceso de usuario que finalizó la operación E/S señalando un semáforo de petición servida (parámetro de DOIO).

La rutina de E/S completa es:

procedure DOIO(stream,modo,cantidad,destino,semaforo)

begin

buscar dispositivo en descriptor del proceso;

chequear parámetros;

if error then salida_con_error;

montar IORB;

insertar IORB en cola peticiones dispositivo;

signal(pet_pendiente)

end;

Manejadores de dispositivo

Es un proceso responsable de tratar las peticiones de un dispositivo. Hay un manejador separado para cada dispositivo

Usar programas compartidos

Diferencias, en las características almacenadas en los descriptores

Su operación es un ciclo continuo durante el cual

Retira un IORB de la cola

Inicia la correspondiente operación E/S

Espera hasta que termina la operación

Lo notifica al proceso origen

El ciclo e una operación de entrada es:

repeat indefinidamente

begin

wait(pet_pendiente);

coger IORB de cola de peticiones;

extraer detalles de la petición;

iniciar operaciones E/S;

wait(op_terminada);

if error then rellenar informacion error;

traducir carácter(es) si es necesario;

transferir datos al destino;

signal(pet_servida);

borrar IORB;

end;

Notas

signal(pet_pendiente) desde el procedimiento E/S cada vez que pone un IORB en la cola

La cola puede tener un algoritmo de selección basada, por ejemplo, en prioridades de E/S

La instrucción de inicio operación E/S puede extraerse de las características en el descriptor

signal(op_terminada) desde la rutina de interrupción

localizar descriptor dispositivo;

signal(op_terminada);

Chequeo de errores, status dispositivo. Errores, se deja la información en la dirección de error indicada en el IORB

Traducción de caracteres según modo en el IORB y las Tablas del Descriptor

Operaciones de salida se coge el dato de la fuente y se traduce antes de las operación

La dirección del semaforo pet_servida se pasa al manejador como un componente del IORB

Es suministrada por el proceso que solicita la E/S como un parámetro del procedimiento de E/S

Desventaja .- Proceso solicitante debe tomar la responsabilidad de la sincronización de sus acciones

Alternativa .- Se da la responsabilidad de sincronización al procedimiento de E/S poniendo el semaforo “pet_servida” local al procedimiento y añadiendo las operaciones

wait(pet_servida);

test direccion error;

El usuario tiene la libertad para continuar en paralelo pero debe detectar el fin de las operaciones de E/S. La responsabilidad está en el S.O. pero se pierde libertad de operación.

Buffering

Las transferencias de entrada las realiza el S.O. en un área de memoria llamada buffer de entrada; el proceso de usuario toma sus datos del buffer y únicamente quedará suspendido si el buffer está vacío.

Las transferencias de salida las realiza el proceso directamente sobre el buffer de salida; el S.O. vaciará el buffer completamente cuando esté lleno.

No evita los casos en los cuales un proceso demanda E/S a una velocidad mayor que la que puede dar el dispositivo. Evita los picos de demanda.

El S.O. asigna espacio para los buffers cuando se abre un stream, y apunta sus direcciones en el descriptor del stream.

El procedimiento de E/S varía ligeramente:

Una petición de entrada extrae el siguiente item del buffer apropiado y lo pasa directamente al proceso

Solo si el buffer está vacío, genera un IORB y señala al manejador

Cuando se abre un stream, se generan suficiente IORB para llenar el buffer

DOBUFFIO(stream,modo,destino)

La cantidad será un solo item

Las esperas por buffer lleno/vacío quedan ocultas en el procedimiento de E/S, no hay necesidad de pasar un semáforo

Tipo, dirección de buffers y semáforos en el descriptor

Dispositivos de fichero

Dispositivos secuenciales .- El nombre es información suficiente para conocer la fuente/destino

Otros dispositivos, tienen la característica de poder seleccionar una zona particular en la que se puede efectuar la transferencia de datos; es necesario especificar qué lugar del medio y no solo su nombre. Cada zona de datos es un fichero.

Dispositivos de fichero o dispositivos con estructura de fichero

Cada fichero tiene un nombre único

Este nombre es utilizado por el S.O. para determinar la posición del fichero en el medio correspondiente

Cada stream tiene que estar asociado con el nombre de un fichero determinado.

DEFINE ENT_1 DISCO3:TESTDATA

Cada vez que se abre un fichero se crea un descriptor de fichero para que contenga la información necesaria para las futuras transferencias:

Dirección del dispositivo

Posición del fichero

El descriptor de fichero añade información extra a la asociación de los streams con los dispositivos físicos.

Spooling

Dispositivos compartidos .- Pueden manejar peticiones sucesivas de diferentes procesos.

Dispositivos no compartidos .- Solo un proceso

Asignación de dispositivos no compartidos

El objetivo es distribuir uniformemente la carga de peticiones y reducir la posibilidad de cuello de botella (SPOOLING) para dispositivos de E/S muy utilizados.

El procedimiento de E/S ejecuta las transferencias sobre un medio intermedio (disco). Para mover los datos entre el disco y el dispositivo requerido se utiliza un proceso especializado llamado spooler.

Ejemplo .- Spooler de impresora

Las salidas por impresora a un fichero; estos ficheros actúan como impresora virtual

Cola de ficheros, esperando su impresión

Función.- coger los ficheros de la cola y enviarlos a la impresora

repeat indefinidamente

begin

wait(algo_al_spool);

coger fichero de cola;

abrir fichero;

repeat until EOF;

begin

DOIO(parametros para lectura disco);

wait(pet_servida de disco);

DOIO(parametros salida impresora);

wait(pet_servida de impresora);

end;

end;

Notas

Buffering datos entre disco e impresora

Semaforo “algo_al_spool” es señalado desde un proceso que cierra un stream de impresora

La cola no tiene por qué ser FIFO, p.e.- ficheros cortos más prioritarios

Igualar la presión de la demanda de periféricos muy utilizados

Reduce la posibilidad de interbloqueo (deadlock)

Relativamente fácil generar varias copias

Necesidad de gran cantidad de espacio de disco

Fuente tráfico en el canal de disco

No es válido para Sistemas de Tiempo Real

Conclusiones

El sistema de E/S es independiente del código de caracteres y del dispositivo físico, tiene un tratamiento uniforme de estos últimos

Se pierde eficiencia; los procedimientos de E/S y los manejadores son generales, pero trabajan más lentos que los especializados

Una mejora en la práctica sería cambiarlo por programas específicos para determinados dispositivos

Sistema de ficheros

Objetivos

Almacenamiento a largo plazo

Almacenamiento en línea

Recuperar información

Almacenar grandes cantidades de datos

Siempre accesible

Sistemas de Propósito General; datos y programas en el sistema (solo terminales)

Compartir la información

Permitir a los usuarios compartir la información

Programas y datos de otros usuarios

Base de Datos General

Software de Sistema; Librerías

Si se comparte, debe estar siempre almacenada

El almacenamiento a largo plazo se realiza en la Memoria Secundaria (discos o cintas)

El sistema de ficheros suministra los medio para organizar y acceder a estos datos

Ficheros de tamaño arbitrario

Colección de datos la cual es considerada como una entidad lógica por el usuario

El fichero en la unidad lógica que almacena y maneja el sistema de ficheros

El medio de almacenamiento está generalmente dividido en bloques; a cada fichero se le asigna el número apropiado de bloques.

Un sistema de fichero debe:

Permitir la creación y borrado de ficheros

Permitir el acceso para lectura y escritura

Realizar automáticamente la gestión del espacio de memoria secundaria

Permitir la referencia a los ficheros contra fallos del sistema

Permitir compartir ficheros entre usuarios que cooperan y protegerlos contra accesos no autorizados

Directorios

El acceso a un fichero no es más que una transformación de su nombre simbólico en una posición física en Memoria Secundaria.

Un directorio de ficheros es una tabla que contiene información sobre las posiciones de los ficheros que incluye algún medio de protección.

Por seguridad se divide el directorio en dos niveles:

Directorio Ficheros Maestro (MFD)

Directorio Ficheros Usuario (UFD)

Seguridad

Chequeo de identidad al nivel de Directorio Maestro (MFD)

Mismo nombre en distintos directorios de usuarios

full name o nombre completo del fichero

Carácter separador

La información en Directorio de Usuario (UFD):

Nombre fichero

Posición física en memoria secundaria

Tipo de fichero (char, binario reubicable, binario ejecutable, librerías, etc.)

Control de acceso

Información administrativa (t. creación, t. última modificación, etc.)

Si extendemos este concepto a una estructura multinivel, cada directorio puede contener ficheros y/o directorios

Usuarios de un proyecto de un departamento

Protección .- chequeo según progresa en el árbol de directorios

Nombre completo, todo el camino (path) y el nombre individual

Longitud del nombre completo: Directorio actual

Seguridad

El problema de seguridad reside en la compartición de ficheros de otros usuarios.

Es necesario un modo de especificar qué usuarios pueden acceder a los ficheros de otro propietario además de especificar qué tipo acceso se permite.

Se asocia a cada fichero un conjunto de privilegios de acceso aplicables a varias clases de usuarios.

Clases de usuarios

El propietario (O)

Miembros de su grupo (G)

Otros o resto del mundo (W)

Privilegios de acceso

Lectura (R)

Escritura (W)

Ejecución (E)

Borrado (D)

Ejemplo: O:RWED,G:RW,W:R

La máscara de protección reside en el UFD del propietario como parte de la entrada de cada fichero. Al propietario le está permitido cambiarlas.

Los usuarios se dividen en grupos, así en su identificación debe incluir su grupo. Surge un problema cuando se desea pertenecer a varios grupos, es necesario un comando de cambio de grupo.

Como alternativa se utiliza la técnica más general, la lista de control de acceso:

Para cada fichero/directorio, información completa acerca de los usuario con tipo de acceso autorizado

Consiste en una o más entradas control acceso, cada una especifica la clase de acceso permitido para un usuario o grupo de usuarios

Sin embargo, aparece otro problema, pues consume una gran cantidad de espacio y hace más lento el acceso a los ficheros. Como ventaja tiene su gran flexibilidad.

Otra técnica es que el propietario permita crear links o enlaces a otros usuarios desde sus UFD a entradas suyas. En UNIX los link van directamente al fichero y no a la entrada del UFD; lo hace indistinguible del original.

Organización de la Memoria Secundaria

Un fichero tiene asignado un conjunto de bloques. Es necesaria alguna técnica de almacenamiento dinámico.

Tipos de Organización de los Bloques de un Fichero:

Ficheros Contiguos

Enlace de Bloques

Mapa de Ficheros

Bloques Indice

Ficheros contiguos

Todos los bloques del fichero están adyacentes

La entrada del UFD apunta al primer bloque y contiene su longitud

Fácil de implementar

Ningún gasto de memoria suplementario

Mucha fragmentación; compactación periódica

Dificultad para borrar o insertar bloques en mitad del fichero

Problema .- Asignar espacio cuando no se conoce el final del fichero

Ventaja .- Acceso aleatorio mediante una simple suma aritmética

Enlace de bloques

Unos pocos bytes de cada bloque se usan como puntero al siguiente bloque del fichero; puntero nulo, (0)

La entrada en el UFD apunta al primer bloque de la cadena de bloques del fichero

Gasto de memoria suplementaria: los bytes de cada puntero

Gran número de accesos al disco para llegar al EOF

Acceso necesariamente secuencial; seguir la cadena

Mapa de ficheros

El estado del disco se registra en un mapa de ficheros o tabla de asignación de ficheros

Cada bloque se representa por una entrada de la tabla o mapa

La entrada en el UFD apunta a la entrada en la tabla para el primer bloque del fichero

Cada entrada del mapa apunta a la posición en el mapa del siguiente bloque del fichero

Gasto de memoria .- Tamaño del mapa de ficheros, depende del tamaño de cada entrada del mapa

Información adicional con un número de identificación único para cada fichero

Se puede incluir un puntero al último bloque de cada fichero

Suele ser necesario almacenar el mapa de ficheros en el propio disco

Para leer N bloques pueden ser necesarios N accesos extras al disco para leer el mapa (que tendrá varios bloques)

Conviene tener los bloques de un mismo fichero cercanos para que estén en el mismo bloque de mapa

Bloques índice

Los punteros de enlace para cada fichero son almacenados en un bloque índice en disco

Si el fichero es grande necesitará varios bloques índice

La entrada en el UFD apuntará al primer bloque índice del fichero

Gasto de memoria .- Un puntero por cada bloque, más la mitad del último bloque índice que no estará lleno

Para ficheros pequeños se podría almacenar un índice primario en la entrada del directorio (UNIX)

Ventaja .- El acceso no tiene que ser secuencial . Nombre del fichero y desplazamiento en el bloque índice

Tiempo de acceso .- Solo consultar el bloque índice (o varios si es muy grande)

Problema .- Insertar o borrar bloques en mitad del fichero

Fin de fichero (EOF)

Con una marca especial, que no puede interpretarse como un dato

Problema en ficheros binarios

Conocer siempre la longitud del fichero

Gestión del espacio libre

Todos los bloques libres como si fueran un único fichero

Ficheros contiguos .- Cada serie de bloques contiguos formarán un fichero libre

Bloque índice .- Lista de bloques libre, pero todas las operaciones se deben realizar por el final de la lista

Enlace bloques y mapa ficheros .- Cadena de Bloques Libres. Las operaciones se pueden realizar en la cabecera o en el final de la cadena

Para borrar N bloques

Bloque índice Borrar N punteros

Resto Sólo dos punteros

Alternativa .- Mapa de Bits

Una zona de memoria donde cada bit representa el estado (ocupado o libre) de cada bloque de Memoria Secundaria

Puede ser grande y será necesario almacenarlo en Memoria Secundaria

Peligroso en caídas del sistema o del disco

Elección del tamaño del bloque

El desperdicio de espacio debido a que algunos bloques no están completamente llenos Bloque pequeño

El desperdicio de espacio debido a los punteros de enlace Bloque grande

La unidad de transferencia de datos entre Memoria Principal y el dispositivo de almacenamiento El bloque debería ser múltiplo de esta unidad

La cantidad de memoria necesaria para cada lectura/escritura en un fichero Bloque índice o el mapa deben estar presentes en memoria principal

Técnicas directas y simples o muy sofisticadas; minimizar el tiempo de búsqueda

Integridad

Es esencial tener un mecanismo adecuado de copias de seguridad (back up) y recuperación de ficheros.

Salvado periódico o masivo

El sistema de ficheros completo se vuelca en un medio auxiliar, generalmente cintas, cada cierto tiempo

Desventajas

El sistema debe ponerse fuera de uso durante el tiempo del volcado de memoria

Lleva mucho tiempo

Salvado incremental

Solo se salva la información que ha cambiado desde la última vez que se realizó

Solo nuevos ficheros creados o modificados y entradas de directorios modificadas

Menor cantidad de información .- Se puede realizar con mayor frecuencia

Se realiza junto con un salvado periódico

Flags que indiquen si el directorio/fichero deben copiarse

Salta todos los ficheros cuyo flag no está activo

Tampoco salva los que están siendo actualizados en el instante del salvado

Desventaja .- Gran cantidad de datos que genera y la dificultad de reconstrucción

Reconstruir a la inversa la secuencia de hechos salvada

Automatizar estos mecanismos

Abrir y cerrar ficheros

El S.O. debe buscar un dispositivo y la posición donde está el fichero almacenado cuando un stream de E/S es asociado a un fichero.

El procedimiento inverso es cerrar un fichero

Explícitamente desde el proceso

Implícitamente cuando termina el proceso

Los procedimientos son:

open(nombre_fich,modo)

close(nombre_fich)

donde:

nombre_fich Nombre simbólico del fichero

modo Tipo de acceso solicitado (Lectura, Escritura o Creación)

Operaciones para abrir un fichero

Buscar la entrada en el directorio del fichero

Verificar que la petición la realiza un proceso perteneciente a un usuario con los privilegios de acceso adecuados

Asegurarse que si el fichero está ya abierto para lectura no se abre para escritura y si lo está en escritura no se puede abrir

Determinar el dispositivo y la localización del fichero; si es nuevo, asignarle memoria

Crear un descriptor de fichero con toda la información sobre el fichero necesaria para las transferencias de datos

La información incluida en el descriptor de fichero será:

Nombre del fichero

Dirección del descriptor de dispositivo en el cual está almacenado el fichero

Posición del primer bloque del fichero

Posición del siguiente bloque que será leído o escrito

Modo de acceso

El descriptor es apuntado desde del descriptor de stream apropiado.

10. Clases de Almacenamiento

Clase de Almacenamiento

El nombre de una variable identifica alguna ubicación física en memoria (o en registro).

La cadena de bits representa el valor de la variable almacenada.

Una clase de almacenamiento determina:

• Si la variable se almacena en memoria o en registro

• Cuándo la variable está activa (su ámbito)

Variables automáticas

La mayoría de las variables.

{

auto int a;

auto int c;

char d='a';

}

Características

• La palabra clave auto (no se utiliza normalmente)

• Declaradas dentro de un bloque de código

• El ámbito es limitado al bloque donde se definen

• Se crean cuando se empieza a ejecutar el bloque

• Se destruyen cuando se termina

• No se ven desde otras funciones

Prácticas

Analizar el siguiente programa

main()

{

int x=1;

{

int y=2;

printf(“%d %d\n”,x,y);

}

{

printf(“%d %d\n”,x,y);

}

}

Analizar el siguiente programa

main()

{

int x=2;

{

int x=3;

printf(“%d\n”,x);

}

{

printf(“%d\n”,x);

}

printf(“%d\n”,x);

}

Modifique el programa anterior mediante funciones

¿Cuál será la salida del siguiente programa?

main()

{

int x=1;

{

func_interna();

}

}

func_interna()

{

printf(“%d\n”,x);

}

Variables externas

Definición

Se definen externamente a cualquier función

Características

• Son variables globales

• Existen durante todo el tiempo de ejecución del programa

• Ocupan la misma zona de memoria todo el tiempo

• Puede usarse el especificador extern para indicar que la variable se encuentra en otro fichero

Prácticas

• Analizar el ámbito de las variables en los siguientes programas. ¿Cuál es su salida?

double x=2.3, y=4.6, z;

main()

{

double f();

z=f(); printf(“%.1f %.1f %.1f\n”, x, y, z);

}

double f()

{

double y,z;

x=y=z=3.0; return(x+y+z);

}

Fichero 1

double v;

main()

{

int i=2;

v=3.0;

printf(“%d %.2f %.2f\n”, i, v, f(v));

}

Fichero 2

double g(double z)

{

return (4.0*z*v);

}

double f(dobule x)

{

return (g(1.0)*x*v);

}

Variables estáticas

Definición

{

static int a=1;

static float d=1.2;

}

Características

• Igual que las variables automáticas en cuanto a su ámbito

• Igual que las variables externas en cuanto a su duración y asignación de memoria

• Permite recordar el valor de una variable local de una función de una llamada a otra

• Su utilización proporciona un mecanismo de privacidad de la variable y una existencia permanente

Prácticas

• Probar el siguiente generador de números aleatorios

#define LIMITE 333

#define FACTOR 25173

#define MODULO 65536

#define INC 13849

#define SEMILLA 17

main()

{

int i;

for (i=0; i<LIMITE; ++i)

if (i%6 == 0)

printf(“\n%12d”,random());

else

printf(“%12d”,random()); printf(“\n\n”);

}

random()

{

static int semilla=SEMILLA; semilla=(FACTOR*semilla+INC)%MODULO; return(semilla);

}

Variables externas estáticas

Definición

static int p

f1()

{

}

f2()

{

}

Características

• Existencia permanente

• Ámbito global, pero sólo en el fichero donde se define

• Permite que una variable sea conocida sólo a un conjunto de funciones

Variables registro

Definición

{

register int i;

...

}

Características

• Las variables registro serán almacenadas en registros del microprocesador, siempre que sea posible

• Candidatos son los contadores de bucles

Prácticas

Construya un programa que cuente el número de espacios, dígitos, letras, líneas, “otros” y total de caracteres de la entrada de texto que se le suministre

Construya un programa que calcule la suma de los N primeros números pares, y la suma de los N primeros números impares.

Construya un programa que genere los N primeros números primos.

5. Estructuras de Control

Sentencias if

Sentencia if

if (expresión)

sentencia

Donde sentencia puede ser una sentencia simple:

sentencia_simple;

o bien una sentencia compuesta:

{

lista_sentencias;

}

if - then - else

if (expresión)

sentencia1

else

sentencia2

if - then - else - if - then - else - ... else

if (expr1)

sent1

else if (expr2)

sent2

......

else if (expr3)

sent3

else

sent_defecto

Sentencias bucle

Bucle while

while (expresión)

sentencia

Bucle do - while

do

sentencia

while (expresión);

Bucle for

for (expr1; expr2; expr3)

sentencia

Sentencia switch

Sintaxis

sent_switch ::= switch (exp) s_list

s_list ::= {et_case:}0+ sent | { {s_list}0+ }

et_case ::= default | case exp_const

Ejemplo

switch(c)

{

case `a':

++a_cnt;

break;

case `b':

++b_cnt;

break;

case `c':

case `C':

++cC_cnt;

break;

default:

++resto_cnt;

}

Argumentos de main

Interfaz

main(int argc, char *argv[])

• La orden echo de Unix

#include <stdio.h>

main(int argc, char *argv[])

{

int i;

printf(“\nargc = %d%9s”, argc, “”);

for (i=0; i<argc; ++i)

printf(“argv[%d] = %s\n%17s”, i, argv[i], “”)

printf(“\n”);

}

11. Estructura

Introducción

struct es el nombre que reciben en C los tipos de datos agregados por otros tipos heterogéneos (como RECORD de PASCAL, etc.).

Una estructura es un conjunto de una o más variables de cualquier tipo que se agrupan bajo un mismo nombre para manejarlas convenientemente.

Se declaran:

struct nombre_etiqueta

{

tipo1 miembro1;

tipo2 miembro2;

......

tipon miembron;

};

Las estructuras ayudan a organizar datos comunicados. En muchas situaciones permiten que un grupo de variables relacionadas se traten como una unidad y no como entidades separadas.

Ejemplo

struct fecha

{

int dia;

int mes;

int anyo;

int dia_anyo;

char nom_mes[4];

};

• struct comienza una declaración de estructura, que es una lista de declaraciones entre llaves, {}.

• El nombre fecha es una etiqueta de estructura (tag). Es opcional y aparece detrás de la palabra struct

• Sirve para utilizar esta clase de estructura en otras declaraciones sin necesidad de escribirla de nuevo.

struct fecha aniver, fin_mes, fiesta_1;

• También se pueden hacer las dos cosas a la vez

struct fecha

{

int dia;

int mes;

int anyo;

int dia_anyo;

char nom_mes[4];

} aniver, fin_mes, fiesta_1;

Las variables que aparecen dentro de las llaves se les denomina miembros de la estructura.

La llave cerrada } donde acaba la lista puede ir seguida de una lista de variables, como cualquier declaración.

En este caso no es necesario poner la etiqueta de estructura:

struct

{

...

} x, y, z;

sintácticamente es análogo a:

int x, y, z;

en el sentido de que ambas declaran x, y, z de un tipo y ambas le asignan un almacenamiento.

Si la declaración no va seguida de ninguna variable no se le asigna ningún espacio; simplemente se describe un patrón de estructura.

Hay que distinguir claramente entre lo que representa la etiqueta (un tipo) y lo que representan las variables que aparecen detrás de la llave (variables del tipo anterior).

Es la misma diferencia que ha entre int y x.

Las estructuras estáticas y externas se pueden inicializar mediante una lista de valores que siguen a la definición.

struct fecha fiesta_2 = {23,12,1990,357,”DIC”};

Las estructuras automáticas no se pueden inicializar. Es igual que la inicialización de los arrays.

Operador miembro de Estructura (.)

Para acceder a un miembro de una estructura son necesarios el nombre de la variable (fiesta_2), el nombre del miembro (anyo) y el operador (.).

La sintaxis es:

nombre_estructura.miembro

El operador (.) conecta el nombre de una estructura y el nombre del miembro.

fiesta_2.anyo%4==0

if(strcmp(aniver.nom_mes,”AGO”)==0)

Ejemplos de uso

struct fecha f;

int es_bisiesto;

es_bisiesto = (f.anyo%4==0)&&(f.anyo%100!=0)

ññ(f.anyo%400==0);

if(strcmp(f.nom_mes,fiesta_1.nom_mes)==0);

f.nom_mes[0] = `F';

f.nom_mes[1] = `E';

f.nom_mes[2] = `B';

f.nom_mes[4] = `\0';

f.nom_mes = `FEB';

Las estructuras se pueden anidar:

struct registro

{

char nombre[MAXNOM];

char direccion[MAXDIR];

long dni;

double salario;

strcut fecha nacimiento;

strcut fecha antigüedad;

};

struct registro empleado;

Para sabe en qué mes nació:

empleado.necimiento.mes

Restricciones de las estructuras

• Los operadores miembro (.) y dirección (&) son los únicos que pueden aplicarse a las estructuras (K&R)

• No pueden ser pasadas o devueltas en funciones (K&R)

• No se pueden copiar enteras (K&R)

ANSI ofrece la posibilidad de comparación, asignación y uso como argumentos y/o retorno de funciones, con paso por valor.

La solución en el C de K&R es el uso de punteros a estructuras, aunque también en el C ANSI son de uso muy frecuente.

struct etiqueta var1, *ptr_st;

ptr_st = &var1;

Si queremos acceder a un miembro de la estructura usando el puntero.

(*ptr_st).miembro1

donde los paréntesis son absolutamente imprescindibles.

Es tan frecuenta esta operación que C ofrece un símbolo especial para la misma:

ptr_st -> miembro1

Estructuras y funciones

Ejemplo .- Función que calcula el día del año

struct fecha f;

main()

{

...

f.dia_anyo = dia_del_anyo(f.anyo,f.mes,f.dia);

...

}

dia_del_anyo(anyo,mes,dia)

int anyo,mes,dia;

{

int num_dia;

...

return(num_dia)

}

Ejemplo .- Usando punteros a estructura

struct fecha antigüedad;

main()

{

...

antigüedad.dia_anyo = dia_del_anyo(&antigüedad);

...

}

dia_del_anyo(ptr_f)

struct fecha *ptr_f;

{

int dia,i,bisiesto;

dia = ptr_f -> dia;

bisiesto = ptr_f -> anyo %4&&...;

for (i=1; i < ptr_f->mes; i++)

dia += dia_tab[bisiesto][i];

return(dia)

}

La asociatividad de `->' y `.' es de izquierda a derecha

p -> q -> miembro

equivale a:

(p -> q) -> miembro

emp.antigüedad.mes

equivale a:

(emp.antigüedad).mes

Estos operadores `.' y `->' tienen la máxima precedencia junto con () y [].

struct

{

int x;

int y;

} *p;

• ++p -> x Incrementa x

• (++p) -> x Incrementa p

• (p++) -> x Incrementa p

• p++ -> x Incrementa p

• *p -> y Obtiene el contenido apuntado por y equivalente a *(p -> y)

• *p -> y++ Incrementa y después de acceder a lo que apuntaba (igual que *p++)

• (*p -> y)++ Incrementa lo apuntado por y

• *p++ -> y Incrementa p después de acceder a lo que apunta y

Ejemplos

struct lapiz /*Declaración de estructura */

{

int dureza;

char fab;

int codigo;

};

struct lapiz 10,11,12; /*Declaración de variables */

Otra forma:

struct

{

int dureza;

char fab;

int codigo;

}10,11,12;

Y otra forma (más incómoda):

struct

{

int dureza;

char fab;

int codigo;

}10;

struct

{

int dureza;

char fab;

int codigo;

}11;

struct

{

int dureza;

char fab;

int codigo;

}12;

main()

{

struct lapiz 10,11,12;

l0.dureza = 2;

l0.fab = `F';

l0.codigo = 482;

l1.dureza = 0;

l1.fab = `G';

l1.codigo = 33;

l2.dureza = 3;

l2.fab = `E';

l2.codigo = 107;

printf(“La dureza del lapiz 0 es %d.\n”, l0.dureza);

printf(“El fabricante del lapiz 1 es %c.\n”, l1.fab);

printf(“El codigo del lapiz 2 es %d.\n”, l2.codigo);

}

Array de estructuras

Declaración

Struct etiqueta_est nombre[dimension]

Ejemplos

main()

{

int i;

struct lapiz l[3];

l[0].dureza = 2;

l[0].fab = `F';

l[0].codigo = 482;

l[1].dureza = 0;

l[1].fab = `G';

l[1].codigo = 33;

l[2].dureza = 3;

l[2].fab = `E';

l[2].codigo = 107;

printf(“Dureza Fabricante Codigo \n\n”);

for (i=0; i<3; i++)

printf(“ %d %c %d\n”,

l[i].dureza, l[i].fab, l[i].codigo);

}

main()

{

struct lapiz l[3], *ptr_l;

l[0].dureza = 2;

l[0].fab = `F';

l[0].codigo = 482;

l[1].dureza = 0;

l[1].fab = `G';

l[1].codigo = 33;

l[2].dureza = 3;

l[2].fab = `E';

l[2].codigo = 107;

printf(“ Dureza Fabricante Codigo\n\n”);

for (ptr_l=1; ptr_l < 1+3; ptr_l++)

printf(“ %d %c %d\n”,

ptr_l->dureza,ptr_l->fab,ptr_l->codigo);

}

Inicialización

struct lapiz

{

int dureza;

char fab;

int codigo;

} l[] = {

{2,'F',482},

{0,'G',33},

{3,'E',107}

};

Las llaves de cada elemento del array se pueden quitar si son variables simples o cadenas.

Una función puede devolver un puntero a una estructura:

struct lapiz bd_lapiz[TAM_TAB];

struct lapiz*busca_tab(codigo)

int codigo;

{

struct lapiz*l_buscado;

int i;

l_buscado = NULL;

for(i=0; i<TAM_TAB&& l_buscado==NULL; i++)

if(bd_lapiz[i].codigo==codigo)

l_buscado = &bd_lapiz[i];

return(l_buscado);

}

Estructuras autorreferenciadas

struct tnode

{

char *word;

int count;

struct tnode*next;

}

Es ilegal una referencia a la propia estructura pero no a un puntero a la propia estructura.

Uniones

Una unión es una variables que puede contener (en momentos diferentes) objetos de tipos y tamaños distintos.

Proporciona una forma de manejar diferentes clases de datos en una misma zona de memoria.

Se utiliza el mismo almacenamiento (dirección de memoria) y el mismo nombre (de etiqueta y de variable) para almacenar variables que pueden ser de diferente tipo.

Se declaran como las estructuras:

union nom_etiq

{

tipo1 miembro_1;

tipo2 miembro_2;

...

tipon miembro_n;

};

Ejemplo .- Tabla de símbolos

union u_tag

{

int ival;

float fval;

char *pval;

}uval;

uval será suficientemente grande como para contener el mayor de los tres tipos de datos.

Cualquiera de estos tipos puede ser asignado a uval y usarse en expresiones. Para usarlo consistentemente el tipo usado debe ser el último almacenado.

Es responsabilidad del programador seguir la pista del tipo que hay realmente almacenado.

Depende de la máquina el resultado de almacenar algo como de un tipo y extraerlo como de otro tipo.

Sintácticamente:

nombre_union.miembro

puntero_union -> miembro

Ejemplo

if(utype == INT)

printf(“%d\n”,uval.ival);

else if(utype == FLOAT)

printf(“%f\n”,uval.fval);

else if(utype == STRING)

printf(“%s\n”,uval.pval);

else

printf(“TIPO ERRONEO %d EN utype.\n”, utype);

struct

{

int utype

union {

int ival;

float fval;

char *pval;

} uval;

} symtab[DIM]

if(symtab[i].utype == INT)

printf(“%d\n”, symtab[i].uval.ival);

Typedef

Es un recurso de C para crear tipos de datos y darles nombres propios. Su sintaxis es:

typedef tipo sinonimo;

permite posteriormente declaraciones de la forma:

sinonimo var;

que es totalmente equivalente a la declaración:

tipo var;

Ejemplo

typedef char * STRING;

STRING s1, s2;

El nombre del tipo definido aparece en la posición del nombre de variable, no a la derecha de la palabra typedef.

typedef struct tnode {

char *word;

int count;

struct tnode *next;

}TREENODE, *TREEPTR;

TREEPTR talloc()

{

char * alloc();

return ((TREEPTR) alloc (sizeof(TREENODE)));

}

8. Funciones de Ficheros

Ficheros

Puntero a FILE; estructura FILE en stdio.h.

Tres ficheros estándares:

Puntero C	Nombre	Conectado
stdin	entrada estándar	al teclado
stdout	salida estándar	a la pantalla
stderr	error estándar	a la pantalla

Una vez que el fichero se abre:

• El sistema proporciona un puntero a FILE

• Que debe usarse en todas las operaciones posteriores

Resumen de funciones

Abrir un fichero

FILE * fopen (char * n_fich, char * modo_fich)

• n_fich nombre del fichero

• modo_fich modo en el que se quiere abrir. Básicamente:

• r lectura

• w escritura

• a añadir

• Retorna un puntero a FILE

• Retorna un ptr nulo si no es posible abrir el fichero

Cerrar un fichero

int fclose (FILE * ptr)

Leer un carácter

int getc (FILE * ptr)

int fgetc (FILE * ptr) #macro

Devolver un carácter a un fichero

int ungetc (char ch, FILE * ptr)

Escribir un carácter en un fichero

int putc (int ch, FILE * ptr)

int fputc (int ch, FILE * ptr) #macro

Leer una cadena desde un fichero

char *fgets(char *s, int n, FILE * ptr)

Escribir una cadena en un fichero

int fputs(char *s, FILE * ptr)

Prácticas

Construya un programa que gire cada una de las líneas de un fichero y después las invierta. El fichero debe recogerse como parámetro, y si no se indica ninguno, se leerá la entrada estándar. La salida se enviará a la salida estándar. El programa debe ser todo lo robusto que se pueda.

7. Funciones de Manejo de Tiras

Leer y escribir tiras

Leer una tira

char *gets (char * s)

• Lee una cadena desde la entrada estándar y la copia en s

• La función copia hasta que encuentra un carácter salto de línea (¡Cuidado con desbordar el tamaño de s!)

• Este carácter se sustituye por un carácter NULO

• Retorna la dirección de s

scribir una tira

int puts (char * s)

• Se copia la tira s en la salida estándar

• El carácter nulo es sustituido por un carácter salto de línea

• Retorna el número de caracteres escritos, (error EOF)

Concatenar tiras

char *strcat(char *tira1, char *tira2)

Ejemplos

main()

{

static char tir1[30]=”Adios mundo”;

static char tir2[10]=”cruel\n”;

printf(“%s”, strcat(tira1,tira2));

}

main()

{

static char tir[30]=”Adios mundo”;

printf(“%s\n”, strcat(tir, “cruel”));

}

Comparar tiras

int strcomp(char *tira1, char *tira2)

• Retorna 0 si las dos tiras coinciden

• En caso contrario retorna la diferencia entre las dos tiras de caracteres.

main()

{

printf(“%d\n”, strcomp(“hola”,”hola”));

printf(“%d\n”, strcomp(“jola”,”hola”));

printf(“%d\n”, strcomp(“hola”,”hola mundo\n”));

}

Copiar tiras

char *strcopy(char *tir1, char *tir2)

main()

{

char tir1[30];

strcopy(tir1, “Hola mundo”);

printf(“%s\n”, tir1);

printf(“%s\n”, strcopy(tir1, “3 2 1”));

}

Calcular la longitud

#include “stdio.h”

main()

{

static char tir1[]=”Pedro Picapiedra”;

static char tir2[30]=”Pablo Marmol”;

printf(“%s %d %d\n”, tir1, strlen(tir1), sizeof tir1);

printf/”%s %d %d\n”, tir2, strlen(tir2), sizeof tir2);

}

Otras funciones

Index (s,c)	Un puntero a la primera ocurrencia de c en s, o Nulo si no se encuentra
atoi(s)	Convertir a entero
Sscanf(s, cntl, arg1, ..)	Leer (“scanf”) desde una tira
Sprintf(s, cntl, arg2, ...)	Escribir (“printf”) a una tira

Prácticas

Escribir una función que devuelva 1 si la cadena que se le pasa es un palíndromo, y 0 si no lo es.

1. Introducción al lenguaje C

El Lenguaje C

El lenguaje de programación C está íntimamente ligado al sistema Unix.

El primer lenguaje fue el BCPL (Richards, 1969), posteriormente apareció el lenguaje B (Johnson y Kernighan, 1973). En 1972 Dennis Rithchie diseñó e implementó el lenguaje C. Un año después Ritchie yThompson reescribieron el núcleo del sistema Unix en lenguaje C.

Más del 90% del código de Unix está escrito en C. Actualmente C se está extendiendo a diferentes entornos. También están apareciendo espectaculares compiladores en el mundo de los ordenadores personales.

Características de C

• Estructuración

• Modularidad

• Flexibilidad

• Portabilidad

• Alto/bajo nivel

• El sistema Unix ofrece varias herramientas para soportar el desarrollo de aplicaciones en C

No podíamos exponer el Entorno de Desarrollo de Unix sin presentar brevemente el lenguaje de programación C.

Apariencia sintáctica de un programa

/*********************************************************/

/* Convertir líneas a mayúsculas */

/*********************************************************/

#include “stdio.h”

#define MAXLINEA 81

/* Longitud máxima de la línea (uno más

para el carácter nulo */

#define CAR_NULO `\0'

/* Byte nulo */

#char linea[MAXLINEA]

/* Array donde se guardará una línea */

/*********************************************************/

/* Función main */

/*********************************************************/

main()

{

char resp;

/* Variable para obtener la respuesta del usr */

void amayu();

/* Función que convierte a mayúsculas */

do

{

printf (“Introduzca una linea (max. %d cars) \n”,

MAXLINEA-1);

gets(linea);

amayu();

printf (“Desea continuar (s/n)? “);

while ((resp=getchar()) == `\n');

}

while (resp != `N' && resp != `n');

}

/*********************************************************/

/* Función para convertir a mayúsculas */

/*********************************************************/

void amayu()

{

for (i=0; linea[i] != CAR_NULO; i++)

{

putchar(toupper(linea[i]));

}

putchar(`\n');

}

Esquema de un programa

Formato de una función:

tipo nombre_funcion(def_argumentos)

{

definicion_de_variable_locales;

sentencias;

}

Entre las funciones aparecen instrucciones para el preprocesador, definiciones de variables, declaración de nuevos tipos de datos, etc.

Comentarios:

/* ....... */

Preprocesador

Se ejecutará automáticamente cuando se compile un programa.

Incluir ficheros:

# include <stdio.h>

Los ficheros cabecera contienen declaraciones de variables, de nuevos tipos, de funciones, etc.

No se puede utilizar este procedimiento para incluir ficheros con código C.

Definir macros:

#define MAXLINEA 81

Ejecución del programa

El programa comienza a ejecutarse por la función main.

Salvo que el programa se interrumpa la ejecución empezará por la primera sentencia de main y terminará por la última.

El anidamiento de funciones se produce en el momento de ejecución del programa.

C de Kernighan-Ritchie y ANSI C

B.W. Kernighan y D.M. Ritchie escirbieron el libro The C Programming Language. Este estándar es conocido popularmente como el C de Kernighan-Ritchie.

El instituto americano ANSI (American National Standars Institute) ha desarrollado un estándar del lenguaje C.

Unix SVV4 y ANSI C

En la versión SVV4 de AT&T de Unix se ha incorporado el sistema de compilación C Edición 5.0. Este sistema incluy compilación ANSI C aunque no obligatoriamente.

En versiones de SVV4 la compilación se supondrá que implícitamente es en modo ANSI.

Algunas características ANSI C

Prototipos de funciones

tipo funcion(tipo1 arg1, ..., tipon argn)

Declaración:

tipo funcion(tipo1, ..., tipon);

Caracteres multibyte

ANSI C permite la utilización de secuencias de bytes en vez de bytes simples para representar caracteres especiales.

Prácticas

Escribir una función que devuelva 1 si la cadena que se le pasa es un palíndromo, y 0 si no lo es.

9. Funciones

Función C

Formato de una función:

tipo nombre_funcion(def_argumentos)

{

definición_de_variables_locales;

sentencias;

}

• Argumentos reales ! Argumentos formales

• C siempre pasa argumentos por valor

• Siempre se hace una copia de los argumentos

• El tipo de los argumentos reales debe concordar con el de los formales

Aunque el compilador hace algunas conversiones, el programador debe indicarlas explícitamente

Pasar Argumentos

Para usar una función necesitamos saber:

¿Cuáles son sus argumentos?

¿Qué resultados retorna?

¿Cuáles son sus efectos laterales?

Pasar valores:

main()

{

int n;

printf(“Valor para n\n”);

scanf(“%d”, &n);

sum_cuadrados(n);

}

void sum_cuadrados(int n)

{

int i, sum=0;

for (i=1; i<=n; ++i)

sum += i*i;

printf(“Resultado %d\n”, sum);

}

Devolver valores

main()

{

int n;

printf(“Valor para n\n”);

scanf(“%d”, &n);

printf(“Resultado %d\n”, sum_cuad(n));

}

int sum_cuad(int n)

{

int i, sum=0;

for (i=1; i<=n; ++i)

sum += i*i;

return(sum);

}

Usar punteros

main()

{

int n;

int resul;

printf(“Valor para n\n”);

scanf(“%d”, &n);

sum_cuad(n, &resul)

printf(”Resultado %d\n”, resul);

}

void sum_cuad(int n, in *ptr_res)

{

int i;

*ptr_res=0;

for (i=1; i<=n; ++i)

*ptr_res += i*i

Efectos laterales

int Result=0;

main()

{

int n;

printf(“Valor para n\n”);

scanf(“%d”, &n);

sum_cuad(n);

printf(“Resultado %d/n”, Result));

}

void sum_cuad(int n)

{

int i;

for (i=1; i<=n; ++i)

Result += i*i;

}

4. Operadores y Conversión deTipo

Precedencia y asociatividad

Resumen de operadores, su precedencia (de mayor a menor) y asociatividad

Prec	Operadores	Símbolos	Asociatividad
1	Llamada a función y selección de campos	() [] . ->	izda dcha
2	Unario	*&-!"++--sizeof	dcha izda
3	Multiplicativos	* / %	izda dcha
4	Aditivos	+ -	izda dcha
5	Desplazamientos	<< >>	izda dcha
6	Relacionales	< > <= >=	izda dcha
7	Igualdad	== !=	izda dcha
8	“and” de bits	&	izda dcha
9	“or” exclusivo de bits	^	izda dcha
10	“or” de bits	|	izda dcha
11	“and” lógico	&&	izda dcha
12	“or” lógico	||	izda dcha
13	Condicional	?:	dcha izda
14	Asignación	= /= *= += -=	dcha izda
15	Coma	,	izda dcha

Prácticas

Evalúe las siguientes expresiones

c=3+8

5/(c=b=4)

6+(c=3+8)

Escriba un programa que convierta un número de segundos en minutos y segundos usando el operador %

Construya un programa que cuente hasta un valor. Utilice el operador `++' en una pregunta while

Conteste cómo se evaluarán las siguientes expresiones

x*y++

*y += 1

*c++

No confunda precedencia con orden de evaluación. Discuta sobre los siguientes ejemplos

y=2; n=3; sig=(y+n++)*6;

printf (“%6d %d\n”, num, num*num++);

resp=num/2+10*(1+num++);

Conversión de tipo

El rango de categoría de mayor a menor:

• double

• float

• long

• int

• short

• char

Las variables y constantes float se convierten a double.

Promoción .- En cualquier operación en la que aparezcan dos tipos diferentes, se promociona la del menor a la del mayor.

Sentencia de asignación

• El resultado final se reconvierte al tipo de la variable a la que se está asignando

• Puede producirse por tanto una promoción, o una pérdida de rango

• Conviene normalmente hacer una conversión explícita “(tipo)”

Prácticas

Analice el siguiente programa

main()

{

char ch;

int i;

float fl;

fl=i=ch='A';

printf(“ch = %c, i = %d, fl = %2.2f\n”, ch, i, fl);

ch = ch + 1;

i = fl + 2 * ch;

fl = 2.0*ch + i;

printf(“ch = %c, i = %d, fl = %2.2f\n”, ch, i, fl);

ch = 2.0e30;

printf(“Ahora ch = %c\n”, ch);

}

¿Cuál es el resultado de las siguientes expresiones?

var_int = 1.8 + 1.9

var_int = (int) 1.6 + (int) 1.9

12. Punteros

Introducción

Un puntero es una variable que contiene la dirección de otra variable.

Los punteros se han comparado con la sentencia goto como una forma maravillosa de crear programas imposibles de entender.

Sin embargo, con cierta disciplina los punteros pueden ser usados para conseguir claridad y simplicidad.

Un puntero tiene un contenido directo:

una dirección

y un contenido indirecto:

el objeto al que apunta

En C no hay punteros, hay punteros a tipos de datos.

Operador &

• El operador unario & da la dirección de un objeto.

• Como un puntero contiene la dirección de un objeto, es posible acceder a ese objeto indirectamente por medio del puntero.

• Sea x una variable entera (int x;) y px un puntero, la sentencia:

px = &x;

asigna la dirección de x a la variable px; decimos ahora que px apunta a x.

• Ejemplo .- Supongamos la variable alfa:

Dirección Valor Nombre

9634 1 alfa

main()

{

int alfa = 1;

printf(“La direccion %u contiene el valor

%d.\n”, alfa, &alfa);

}

Salida

La direccion 9634 contiene el valor 1.

• & solo se puede aplicar a variables o elementos de un array.

• No se puede aplicar a expresiones no constantes

• Ejemplos .- Utilización ilegal de &

&(x+1)

&3

• Tampoco se puede aplicar a variables register.

Operador *

• El operador unario * trata su operando como la dirección de su objetivo, y accede a esa dirección para obtener su contenido

• Ejemplo

int x, y;

int *px;

...

...

px = &x; /* Equivalente a y=x */

y = *px;

Asigna a y el contenido de la dirección apuntada por pc.

• Ejemplo

Dirección Valor Nombre

9364 1 alfa

9370 9364 beta

main()

{

int alfa;

int *beta;

alfa = 1;

beta = &alfa;

printf(“La direccion %u contiene el valor %d.\n”,

&alfa,alfa);

printf(“La direccion %u contiene el valor %d.\n”,

&beta,beta);

printf(“La direccion %u contiene el valor %d.\n”,

*(&alfa),alfa);

}

Salida

La direccion 9364 contiene el valor 1

La direccion 9370 contiene el valor 9364

La direccion 9364 contiene el valor 1

• Los punteros deben declararse, la forma es:

tipo *nombre_ptr;

Ejemplos

double atof(),valor, *ptr_d;

int x, y, *px;

Estas declaraciones nos dicen que si en una expresión aparece atof()o *ptr_d tienen valores double, y si aparecen x, y o *px tienen valores int.

• Además, la declaración de un puntero obliga a que éste apunte a una clase determinada de objeto.

Los punteros pueden aparecer en expresiones:

y = *px + 1;

printf(“%d\n”,*px);

d = sqrt((double)*px);

Pueden ser el lado izquierdo (lvalue) de una asignación:

*px = 0;

*px += 1;

*px ++;

Como son variables, se pueden usar como tales:

int *px, *py;

py = px;

Punteros y Argumentos de Función

En C no existe una forma directa de alterar el valor de una variable de la función que hizo la llamada:

f()

{

int a,b;

...

...

swap_erronea(a,b);

}

swap_erronea(x,y)

int x,y;

{

int temp;

temp = x;

x = y;

y = temp;

}

swap no afecta ni a ni b

Hacerlo mediante punteros:

f()

{

int a,b;

...

...

swap(&a,&b);

...

}

swap(px,py)

int *px, *py;

{

int temp;

temp = *px;

*px = *py;

*py = temp;

}

Arrays

Se declaran con la siguiente sintaxis:

tipo nombre[dimension]

Donde dimension es una expresión constante.

Ejemplo

int ndigitos[10]

Declara ndigitos como un array de 10 enteros

ndigitos[0]ndigitos[1],...,ndigitos[9]

Se usa de elemento en elemento (no tiene meta-operadores):

nombre[indice];

donde:

0 <= indice <= dimension-1

El indicepuede ser cualquier expresión entera. Su resultado significa el elemento (a[i]); en la posición i desde el comienzo o el elemento i+1.

Punteros y arrays

• Si

int *pa;

pa = &a[0];

pone a pa apuntando al elemento cero del array a.

Entonces:

x = *pa;

es equivalente a:

x = a[0];

Operador sizeof

• Sintaxis:

sizeof expresion

sizeof (tipo)

• Da el valor del tamaño, en bytes, de su operando

• Aplicado a un array da el tamaño del array en bytes

• El tamaño se determina a partir de la declaración de los objetos

• Si es un tipo, da el tamaño de ese tipo

• El símbolo para el operador tamaño es la palabra sizeof

• Devuelve el tamaño en bytes de su operando

int i;

sizeof(i);

Producirá el valor 2 (o 4) si un entero ocupa 2 bytes en memoria.

• Si declaramos un array:

char who[7];

la expresión:

sizeof(who)

devolverá el valor 7, suponiendo que un char ocupa un byte en memoria.

• Se puede usar también para determinar el tamaño de cualquier tipo de dato

• Ejemplo

main()

{

printf(“char%d\nint %d\nshort %d\nlong %d\nfloat

%d\ndouble %d\nchar* %d\n”,sizeof(char),

sizeof(int),sizeof(short),sizeof(long),

sizeof(float),sizeof(double),

sizeof(char*));

}

Salida

char 1

int 2

short 2

long 4

float 4

double 8

char* 2

• Se usa frecuentemente para independizar el código del tamaño particular de un tipo de dato en una máquina determinada

• Por definición, pa+1 apunta al siguiente elemento

• pa+i apunta i elementos después

• pa-i apunta i elementos antes

• La definición de sumar 1 a un puntero y toda la aritmética de direcciones, es tal que el incremento tiene una escala: el tamaño de almacenamiento del objeto al que apunta

tipo *pa,i;

pa+i;

sed referencia la dirección:

pa + (sizeof(tipo)*i)

• Si a es un array y p es un puntero, ambos de igual tipo:

tipo *p,a[];

si

p = &a[0];

entonces *(p+i); es equivalente a a[i];

• El nombre de un array (a) es una expresión puntero

• Por definición, a es el nombre de un puntero constante que siempre apunta al primer elemento del array a[0]

• Entonces:

a[i] Elemento i del array

a Puntero constante al elemento 0

a+i Expresión tipo puntero, que apunta al elemento i

• Equivalencias, con diferentes sintaxis:

p = &a[0] ! p = a

&a[i] ! a + i

a[i] ! *(a+i)

*(p+i) ! p[i]

• Un array y su índice se pueden escribir como un puntero y un offset

• Diferencia

• Un puntero es una variable

• Un nombre de array es una constante, no se puede modificar pero sí usar

Operaciones ilegales con arrays

a = p;

a++;

p = &a;

Operaciones válidas con punteros

• Asignar una dirección p=&v; siendo v homogénea

• Referenciar *p; se obtiene el objeto

• Restar dos punteros homogéneos p-q; se obtienen los que caben

• Comparar dos punteros p>q; compara que dirección es mayor, etc.

• Incrementar p++, p+i

• Asignar un entero p=14; en general NO se permite (¿Qué hay en 14?)

• El resto de las operaciones, aunque factibles, son impredecibles

Punteros y arrays como argumentosç

• Cuando se pasa el nombre de un array a una función, lo que se pasa realmente es la posición de comienzo del array

• En la dirección 0000 no hay dato alguno, ningún puntero asignado puede ser 0

• Por convenio, p=0 indica puntero no asignado (NULL)

• Sea la declaración

tipo i,*ptr,a[DIM]

Si se usa como argumento real en una llamada:

i se pasa por valor (se copia) la variable

&i se pasa por valor la dirección de la variable, o sea se pasa por referencia la variable

a[i] se pasa por valor el elemento

a se pasa por valor la dirección de comienzo, o sea se pasa por referencia el array

*p se pasa por valor el objeto

p se pasa por valor el puntero, o sea se pasa por referencia el objeto

&p se pasa por valor la dirección del puntero, o sea se pasa por referencia el puntero

• Dentro de la función llamada este argumento es una variable y por eso un nombre de array argumento es un verdadero puntero

• Ejemplo

main()

{

static char cadena=”Hola”;

int strlen();

printf(“Longitud de cadena es %d\n”,

strlen(cadena));

}

int strlen(s)

char s[];

{

int i;

i=0;

while (s[i]!='\0')

i++;

return(i);

}

Otra forma de escribir la función strlen()

int strlen()

char *s;

{

int n;

for (n=0; *s != `\0'; s++)

n++;

return(n);

}

• Para pasar parte de un array

f(&a[2]);

f(a+2);

Ejercicio

/* a se almacena en la posición 1018 */

/* un int ocupa 2 bytes */

/* ptr1 se almacena en la posición 5590 */

/* ptr2 se almacena en la posición 5596 */

main()

{

static int a[3]={100,200,300}

int *ptr1, *ptr2;

ptr1 = a;

printf(“&ptr1 = %u. ptr1 = %u. *ptr1 = %u\n”,

&ptr1,ptr1,*ptr1);

ptr2 = &a[2];

printf(“&ptr = %u. ptr2 = %u. *ptr2 = %u\n”,

&ptr2,ptr2,*ptr2);

ptr1++;

printf(“&ptr1 = %u. ptr1 = %u. *ptr1 = %u\n”,

&ptr1,ptr1,*ptr1);

ptr2++;

printf(“&ptr2 = %u. ptr2 = %u. *ptr2 = %u\n”,

&ptr2,ptr2,*ptr2);

printf(“ptr2-ptr1 = %u\n”, ptr2-ptr1);

}

¿Cuál es la salida del programa?

Cadenas de caracteres (strings)

Un tipo especialmente frecuente e importante son los arrays de caracteres.

Una constante cadena de caracteres como:

“soy una cadena”

es un array de caracteres. Internamente, el último elemento contiene `\0'.

Se pueden inicializar de una manera especial:

char s[] = “texto”

declara un array de 6 char ya que el último elemento contiene `\0'.

En C no se dispone de operadores propios para cadenas de caracteres que las procesen como una unidad.

Las operaciones comunes de comparación, concatenación, etc. se realizan mediante funciones de librería, que utilizan todas el convenio del NULL (`\0') final.

El acceso a estas cadenas se suele hacer mediante punteros a caracteres.

Ejemplo

char *texto;

entonces:

mensaje = “Hoy hay futbol”;

asigna a mensaje un puntero a los caracteres reales. No es una copia de la cadena; solo están involucrados los punteros.

Punteros a caracteres

strcopy_1(s,t)

char s[],t[];

{

int i=0;

while((s[i] = t[i]) != NULL)

i++;

}

strcopy_2(s,t)

char *s,*t;

{

while((*s = *t) != NULL)

s++;

t++;

}

strcopy_3(s,t)

char *s,*t;

{

while((*s++ = *t++) != NULL)

;

}

strcopy_4(s,t)

char *s,*t;

{

while(*s++ = *t++)

;

}

• Otras combinaciones de * y ++ o - son posibles, aunque menos frecuentes:

*++p

*--p

• Los punteros no son enteros, p++ no siempre incrementa en uno; incrementa el tamaño del objeto apuntado.

• Una función puede devolver como su resultado un puntero.

• Ejemplo .- Función que devuelve un puntero a un carácter

char *strsave(s)

char s[];

{

char *ptr;

...

...

return ptr;

}

Arrays multidimensionales y arrays de punteros

• Declaración de array bidimensional:

tipo nombre[DIM_1][DIM_2];

• Los elementos se almacenan por filas, el índice derecho varía más rápido

Punteros Compuestos

• Inicialización

static int biarray[3][4] = {

{0,1,2,3}

{10,11,12,13}

{20,21,22,23}

};

main()

{

f(biarray);

...

}

f(matriz) /* erronea */

int matriz[];

{...}

f(matriz) /* erronea */

int matriz[][];

{...}

f(matriz) /* correcta */

int matriz[][4];

{...}

Arrays de punteros

Se declaran:

tipo *nombre[DIM];

Se interpreta como nombre es un array de DIM punteros a tipo

• nombre[i] Es un elemento (un puntero)

• *nombre[i] Es el objeto apuntado por el puntero

Ejemplo

main()

{

char *ptrlin[MAXLIN];

leer(ptrlin,...);

escribir(ptrlin,MAXLIN);

}

escribir(ptrlin,num)

char *ptrlin[];

int num;

{

int i;

for(i=0; i<num; i++)

printf(“%s\n”,ptrlin[i]);

}

ptrlin es un array de MAXLIN elementos, cada elemento es un puntero a un char

ptrlin[i] puntero a carácter

*ptrlin[i] accede a un carácter

Como ptrlin es un array, puede tratarse como un puntero. La función escribir puede ponerse:

escribir(ptrlin,num)

char *ptrlin[];

int num;

{

while(--num >= 0)

printf(“%s\n”,*ptrlin++);

}

Existen dos formas parecidas de declarar un array bidimensional:

int a[10][10];

int *b[10];

Es legal poner a[5][5] y b[5][5].

• a tiene asignadas 100 posiciones

• b tiene asignados 10 punteros

Acceso por indirección, no suma y multiplicación.

Filas de diferentes longitudes.

Inicialización de arrays de punteros

• Un ejemplo, función nombre_mes(), devuelve un puntero a una cadena de caracteres conteniendo el nombre del mes n, que se le pasa como argumento

char *nombre_mes(n)

int n;

{

static char *nombre[] = {

“mes ilegal”,

“Enero”,

“Febrero”,

“Marzo”,

“Abril”,

“Mayo”,

“Junio”,

“Julio”,

“Agosto”,

“Septiembre”,

“Octubre”,

“Noviembre”,

“Diciembre”

};

return((n<1||n>12)? name[0];name[n]);

}

Punteros a Funciones

Aunque un función NO es una variabl, C permite definir punteros a funciones, para permitir manipularlos y, más especialmente, pasarlos como parámetros a otras funciones.

Se declaran:

tipo(*nombre)();

establece que nombre es un puntero a una función que devuelve tipo.

Es necesario los paréntesis, ya que:

tipo *nombre()

declara nombre como una función que devuelve un puntero a un entero.

C reconoce una función mediante el para de paréntesis () que siguen al nombre de la función.

Cuando ha reconocido un identificador como una función, si se encuentra de nuevo el nombre SIN paréntesis, evalúa ese nombre como la dirección de la función.

main()

{

int abc();

printf(“La direccion de la funcion abc es %u.\n”,

abc);

}

abc() /* Se almacena en la posición 1310 */

{

}

Salida

La dirección de la función abc es 1310.

Declarar abc en main, antes de usar.

Ejemplo .- Uso de un puntero a una función

main()

{

int abc();

int (*ptr_abc)();

printf(“La direccion de la funcion abc es %u.\n”,

abc);

abc();

ptr_abc = abc;

printf(“El valor de ptr_abc es %u.\n”, ptr_abc);

}

abc() /* Se almacena en la posición 1310 */

{

printf(“ABC!\n”);

}

Salida

La dirección de la funcion abc es 1310.

ABC!

El valor de ptr_abc es 1310.

ABC!

En main estamo declarando abc como una función que devuelve un entero, y ptr_abc como un puntero a una función que devuelve un entero.

La asignación:

ptr_abc = abc

asigna la dirección de abc() al puntero ptr_abc.

No es necesario emplear el operador dirección (&), ya que al quitar los paréntesis de función se supone implícitamente que nos referimos a la dirección de la función.

abc() y (*ptr_abc)() aunque son sentencias diferentes, ambas invocan la misma función.

Ejemplo

main()

{

char *abc();

char *(ptr_abc)();

ptr_abc = abc;

printf(“%s”,abc());

printf(“%s”,(*ptr_abc)());

}

char *abc() /* Se almacena en la posición 1310 */

{

return(“ABC!\n”);

}

Salida

ABC!

ABC!

Declaraciones Barrocas

Declaraciones normales

• int x entero

• int *x puntero a un entero

• int *x[3] array de 3 punteros a enteros

• int (*x)[3] puntero a un array de 3 enteros

• int *x() función que devuelve un puntero a un entero

• int (*x)() puntero a una función que devuelve un entero

Declaraciones curiosas

• int **p puntero a un puntero a un entero

• int (*p[3])[4] array de 3 punteros a arrays de 4 enteros

• int (*p)[3][4] puntero a un array de 3×4 enteros

• char *fp()[3] función que devuelve un puntero a un array de 3 char

• char *fp[3]() array de 3 punteros a función que devuelve un char

• Mayor prioridad si está más cerca del identificador

• [] y () mayor prioridad que *

• Si se usan paréntesis estos prevalecen

3. Tipos de Datos Simples

Constantes

• Constantes enteras

143, 0, -1285

• Constantes “long”

715L, 715l, 123456L, 123456l

• Constantes en octal (precedidas por 0)

07, 0377, 020070

• Constantes en hexa

0x7c, 0xa1b, 0Xa1B

• Constantes “carácter”

`M', `a', `+', `-`

• Tiras: Una secuencia de caracteres entre “ “

Secuencias

• Secuencias de escape

\n salto de línea

\t tabulador

\b retroceso

\r retorno de carro

\f salto de página

\\ barra invertida

\' comilla simple

• Secuencias de escape numéricas

\ddd

\007, \07, \7

Caracteres

La sintaxis para definir variable de un tipo es la siguiente:

tipo id1, id2, ...;

Caracteres

char car;

• Un carácter se guarda como su código dentro del conjunto de caracteres que se esté usando

• Por tanto es posible también tratar numéricamente una variable de tipo char

• Muchas funciones que tratan con caracteres devuelven un entero en situaciones de error

Enteros

Existen tres tipos de variables enteras:

• int

• short

• long

tam_short <= tam_int <= tam_long

Las situaciones habituales que se suelen encontrar son:

tam_short tam_int tam_long

16 16 32

16 32 32

Ejemplos

int var, suma, resto;

short cont;

long i, maximo;

Punto flotante y booleanos

Punto flotante

• Tipos float y double para numeros reales

• La aritmética en punto flotante es realizada en doble precisión

float tasa, integral;

double masa, energia;

Valores Booleanos

• El lenguaje C no dispone de tipos Booleanos

• Falso: el valor 0

• Verdadero: Cualquier valor distinto de cero

#define TRUE 1

#define FALSE 0

6. Tipos de Datos Compuestos

Arrays

Es un tipo compuesto formado por una sucesión de objetos del mismo tipo.

tipo nombre_array [d1][d2]...[dn];

Algunas características importantes de los arrays son:

• Los elementos del array se almacenan consecutivamente en memoria

• El nombre del array es la dirección del mismo

• El nombre del array es una dirección constante

Para acceder a los elementos de un array:

nombre_array [i][j]...[k]

Array de caracteres

• Las tiras son arrays de una dimensión de tipo char

• Una tira en C se termina siempre por un carácter nulo `\0'

• El tamaño reservado para una tira debe tener en cuenta este carácter nulo

• Por ejemplo “a” ocupa dos bytes, uno para `a' y otro para `\0'

Estructuras

En otros lenguajes son conocidas como registros.

Una forma de definir una estructura:

struct

{

tipo1 campo 1;

tipo2 campo 2;

......

}

nombre_estructura;

Para acceder a un campo de la estructura:

nombre_estructura.campoi

Uniones

Similar a una estructura excepto que únicamente uno de sus se usa en cada instante.

La definición de una unión es la siguiente:

union

{

tipo1 campo1;

tipo2 campo2;

......

}

nombre_union;

Para acceder a un campo de una unión se hace igual que en una estructura:

nombre_union.campoi

Punteros

Un puntero es una variable que apunta a un determinado tipo de datos. Su definición:

tipo *nombre_ptr;

Características

• Una variable puntero puede asignarse

• Es quizás uno de los errores más frecuentes de la programación en C, usar un puntero que todavía no ha sido asignado

• Para acceder al contenido referenciado por un puntero:

*nombre_ptr;

• Esta expresión es manejada exactamente igual que una variable de tipo tipo

Prácticas

El siguiente programa muestra algunas diferencias entre arrays y punteros. Analice lo que hace:

char s[]=”Primera ley de Murphy”;

char *p=”Si algo puede fallar, fallará”;

main()

{

char *q=”A que te suena esto?”;

printf(“\n%s:\n%s\n%s\n”, s, p, q);

for (p=q; *q!='\0'; q++)

*q+=1;

printf(“\n%s\n\n”,p);

}

Nota .- Falta una hoja en los apuntes

Prácticas

Si i es un entero y p es un puntero a entero ¿qué imprimirá el siguiente código?

i=3;

p=&i;

printf(“%d %d %d %d”, p, *p+7, **&p, p-(p-2));

Si i y j son enteros, y p y q son punteros a enteros, ¿qué sentencias son ilegales?

p = &i p = &*&i i = (int)p q = &p

*q = &j i = (*&)j i = *&*&j i = *p++ + *q

¿Cuál es la salida del siguiente programa?

#include <stdio.h>

main()

{

char *pc = NULL;

int *pi = NULL;

double *pd = NULL;

printf(“\n%d %d %d\n%d %d &d\n\n”,

(int)(pc+1),(int)(pi+1),(int)(pd+1),

(int)(pc+3),(int)(pi+5),(int)(pd+7)));

}

Escribir un programa que cuente caracteres, palabras y líneas (“word count”).

Aplicaciones

S.O.

HW

CRC

Código

CRC

Código

Código

CRC

Código

Nº Bytes

Dir. Carga

CRC

Nº Bytes

Dir. Carga

Nº Bytes

Dir. Carga

Nº Bytes

Dir. Carga

CRC

Código

Nº Bytes

NOMBRE

Nº Bloques

Tipo

Dir. Carga

Estados Básicos de un Proceso

PAGE NUMBER

p

BYTE NUMBER

b

Program

address

PAGE p

PAGE TABLE

P' + B

P'

Simple addres map for paging