Fundamentos del Software UGR

UNIVERSIDAD DE GRANADA

Grado en Ingeniera

Informtica FUNDAMENTOS DEL

SOFTWARE

Curso: 2011/2012 Clase: Primero - Grupo: B

Aviso legal: los archivos estn sujetos a derechos de propiedad intelectual y su titularidad corresponde a los usuarios que los han subido a SWAD. Esto es solo una

recopilacin de toda la asignatura impartida en la UGR.

TEORA

Curso: 2011/2012 Clase: Primero - Grupo: B

Fundamentos del Software

1er Curso de Grado en Ingeniera InformticaTema 1. Sistema de CmputoTema 1. Sistema de Cmputo

Contenidos

1.1 Componentes de un Sistema de Cmputo.1.1.1 Definiciones Bsicas.1.1.2 Registros del Procesador.1.1.3 Ejecucin de Instrucciones. Tipos de

Instrucciones.1.2 Capa Hardware.

1.2.1 Estructura de un Ordenador.1.2.2 Tcnicas de Comunicacin de E/S.

1.3 El Sistema Operativo.

Objetivos

Conocer los elementos principales de un Sistema de Cmputo.

Disponer los elementos de la parte hardware. Conocer el software ms prximo a la capa hardware: el Sistema Operativo.

Conocer las principales utilidades software que se utilizan en un sistema de cmputo.

DEPARTAMENTO DE _______________________________________

LENGUAJES Y SISTEMAS INFORMTICOS 1

1.3 El Sistema Operativo.1.4 Utilidades del Sistema.

Bibliografa bsica

[Prie06] A. Prieto, A. Lloris, J.C. Torres, Introduccin a la Informtica, McGraw-Hill, 2006

[Stal05] W. Stallings, Sistemas Operativos, Aspectos Internos y Principios de Diseo (5 Edicin). Pearson

Education, 2005

[Carr07] J. Carretero, F. Garca, P. de Miguel, F. Prez, Sistemas Operativos (2 Edicin), McGraw-Hill, 2007

23-Sep-2011


Tema 1. Sistema de Cmputo

Definiciones Bsicas [Prie06] (pp.1-7)

Informtica, Computador, Bit, Instruccin u Orden, Programa, Lenguaje de Programacin. Lenguaje Mquina. Hardware (soporte fsico) y Firmware. Software (soporte lgico).

1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo

DEPARTAMENTO DE _______________________________________

LENGUAJES Y SISTEMAS INFORMTICOS

Sistema Informtico.

2



Definicin de Bit

Bit: unidad mnima de informacin

Codifica informacin: 1 bit: 0 1 2 bits: 00, 01, 10 11


DEPARTAMENTO DE _______________________________________


False

3

2n de bits = elementos Log2 elementos = n de bits 10

True



Mltiplos del bit y Unidades

1 Byte (B) = 8 bits (b)

1 Kilobyte (KB) = 210 B =/= 1 Kilobit (Kb)1 Megabyte (KB) = 210 KB =/= 1 Megabit (Mb)1 Gigabyte (GB) = 210 MB =/= 1 Gigabit (Gb)


DEPARTAMENTO DE _______________________________________


1 Terabyte (TB) = 210 GB =/= 1 Terabit (Tb)1 Petabyte (PB) = 210 TB =/= 1 Petabit (Pb)



Cambio de base: binario, octal, hexadecimal [Prie06] (Apndice A. pp.767)

Binario: 000, 001, 010, 011, 100, 101, 110, 111 Octal: 00, 01, 02, 03, 04, 05, 06, 07, 10, 11, 12, 13, 14, ... Decimal: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, Hexadecimal: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 0A, 0B, 0C, 0D, 0E, 0F, 10, 11,


DEPARTAMENTO DE _______________________________________


Nbase 10 = digito0xbase0 + digito1xbase1 + + digitonxbasen

Para obtener el nmero en otra base: dividir hasta llegar a 1 y tomar los restos y el ltimo cociente de la divisin.


1er Curso de Grado en Ingeniera Informtica

Instrucciones vs. Datos

Instruccin: conjunto de smbolos insertados en una secuencia estructurada o especfica que el procesador interpreta y ejecuta.

Datos: Smbolos que representan hechos, condiciones, situaciones o valores. Elementos de informacin.


DEPARTAMENTO DE _______________________________________




Lenguaje natural:Suma lo que hay en A con lo que tiene la posicin 17 de una secuencia de valores.

Lenguaje de programacin de alto nivel:

Instrucciones vs. Datos (cont)


DEPARTAMENTO DE _______________________________________


A= A + M[17]

Ensamblador y lenguaje mquina:ADD A, M(17) 11000 001 0001 001111



Hardware (Soporte Fsico)


DEPARTAMENTO DE _______________________________________




Firmware


DEPARTAMENTO DE _______________________________________




Software (Soporte Lgico)


DEPARTAMENTO DE _______________________________________




Definiciones Bsicas [Stal05] (pp.55)

Programas de Aplicacin

Programador

Usuario Final


DEPARTAMENTO DE _______________________________________


Hardware

Sistema Operativo

Utilidades y Herramientas

Diseador del SO

11



Arquitectura de un Sistema

1.2 Capa Hardware1.2 Capa Hardware

DEPARTAMENTO DE _______________________________________




Registros del Procesador [Stal05] (pp.11-13)

Registros visibles para el usuario.

Registros de control y estadoo Contador de programa (PC).o Puntero de pila (SP).


DEPARTAMENTO DE _______________________________________


o Puntero de pila (SP).o Registro de instruccin (IR).o Registro de estado (bits informativos).

13



Ejecucin de Instrucciones [Stal05] (pp.14-17)Procesar una instruccin consta de dos pasos:

1. El Procesador lee (busca) instrucciones de la memoria, una cada vez.2. El Procesador ejecuta cada instruccin.

La ejecucin de un programa consiste en repetir el proceso de bsqueda y ejecucin de instrucciones.


DEPARTAMENTO DE _______________________________________


ejecucin de instrucciones.

Se denomina ciclo de instruccin al procesamiento requerido por una nica instruccin.

InicioLeer siguiente

instruccin

Ejecutar la

instruccinParada

14



DEPARTAMENTO DE _______________________________________




DEPARTAMENTO DE _______________________________________




DEPARTAMENTO DE _______________________________________




Ejecucin de Instrucciones [Stal05] (pp.14-17) Ejemplo 1.

1. El contador del programa (PC) tiene 300, la direccin de la primera instruccin.

2. Los primeros 4 bits (dgitos en hexadecimal) en el registro de instruccin (IR) indica que el acumulador (AC) ser cargado desde memoria. Los siguientes 12 bits (tres dgitos en hexadecimal) indican la direccin, 940.


DEPARTAMENTO DE _______________________________________


940.3. La siguiente instruccin (5941) ser captada desde la

direccin 301. El PC se incrementa.4. El anterior contenido del AC y el contenido de la

direccin 941 se suman y el resultado se almacena en el AC.

5. La siguiente instruccin (2941) ser captada desde la direccin 302. El PC se incrementa.

6. El contenido del AC se aloja en la direccin 941.

22


Tema 1. Sistema de Cmputo1.2 Capa Hardware1.2 Capa Hardware

Ejecucin de Instrucciones [Stal05] (pp.34-37)Qu sucede cuando un programa desea comunicarse con algn dispositivo de E/S?

Comunicaciones de E/S

Hay tres tcnicas para llevar a cabo las operaciones de E/S:

E/S Programada. E/S Dirigida por Interrupciones.

DEPARTAMENTO DE _______________________________________


Acceso Directo a Memoria (Direct Access Memory, DMA).



Tcnicas de Comunicacin de E/S

E/S Programada. El procesador encuentra una instruccin con la E/S. Se genera un mandato al mdulo de E/S apropiado.

El procesador adopta un papel activo mientras se atiende la instruccin de E/S y comprueba peridicamente el estado de la ejecucin del mdulo de E/S hasta que comprueba que

DEPARTAMENTO DE _______________________________________


la ejecucin del mdulo de E/S hasta que comprueba que ha finalizado la operacin.

Problema: El procesador pasa mucho tiempo esperando la finalizacin del mdulo de E/S y el sistema se degrada gravemente.

Solucin: Mientras se atiende al mdulo de E/S, el procesador pueda continuar con trabajo til.



E/S Dirigida por Interrupciones.Evento que interrumpe el flujo normal de ejecucin producido por un elemento externo al procesador. Es un evento asncrono.



Problema: En transferencias considerables de memoria a

DEPARTAMENTO DE _______________________________________


Problema: En transferencias considerables de memoria a dispositivo o viceversa conlleva un uso excesivo del procesador.

Solucin: Acceso Directo a Memoria. En un solo mandato se genera todo lo necesario para realizar la transferencia de informacin de memoria al dispositivo o viceversa.




Ciclo de instruccin con interrupciones.

Interrupciones inhabilitadas

Fase de bsqueda Fase de ejecucin Fase de Interrupcin

DEPARTAMENTO DE _______________________________________


InicioLeer siguiente

instruccin

Ejecutar la

instruccin

Parada

Comprobacin de

interrupcin del

procesoInterrupciones habilitadas



Tratamiento de Interrupciones Vectorizadas

CPUDispositivoInterrupcin Salto

i Tabla de vectores de interrupcin

DEPARTAMENTO DE _______________________________________


Cdigodel SO

MemoriaPrincipal

. . .

. . .

Cdigo de usuario

Rutina de serviciode interrupcin i

.......................................

...........................

ide interrupcin



Tratamiento de Interrupciones Vectorizadas [Stal05] (pp. 23. Fig. 1.10)


El controlador de disp. u

otro sistema hardware

genera una interrupcin

El procesador termina

la ejecucin de la

instruccin actual

El procesador indica el

Salva el resto de la

informacin de estado

del proceso

Procesa la interrupcin

DEPARTAMENTO DE _______________________________________


El procesador indica el

reconocimiento de la

interrupcin

El procesador apila

PSW y el PC en la pila

de control

El procesador carga un

nuevo valor en el PC

basado en la interrupcin

Restaura la

informacin de estado

del proceso

Restaura los valores

PSW y PC



Acceso Directo a Memoria (DMA, Direct Access Memory). Realizada por un mdulo separado conectado en el bus del sistema o incluida en un mdulo de E/S. til cuando el procesador desea leer o escribir un bloque de datos.

Tcnicas de Comunicacin de E/S [Stal05] (pp.34-37)


DEPARTAMENTO DE _______________________________________




Definicin de excepcin: Evento inesperado generado por alguna condicin que ocurre durante la ejecucin de una instruccin (ejemplo, desbordamiento aritmtico, direccin invlida, instruccin privilegiada, etc.). Es un evento sncrono.

Excepciones [Stal05] (pp.34-37)


DEPARTAMENTO DE _______________________________________




Proteccin [Carr07] (pp.4)

Funcionamiento en Modo Dual. Qu ocurre si un programa accede a la memoria donde se alojan los vectores de interrupciones? Qu pasa si las modifica?

Solucin: El procesador dispone de diferentes modos de ejecucin de instrucciones:

Instrucciones privilegiadas (modo supervisor/kernel): Aquellas cuya

DEPARTAMENTO DE _______________________________________


Instrucciones privilegiadas (modo supervisor/kernel): Aquellas cuya ejecucin puede interferir en la ejecucin de un programa cualquiera o programa del SO (ejemplo, escribir en el puerto de un dispositivo).

Instrucciones no privilegiadas (modo usuario): Aquellas cuya ejecucin no presenta ningn problema de seguridad para el resto de programas (ejemplo, incrementar un contador).



Proteccin de los Dispositivos de E/S [Carr07] (pp.25-28)

Los dispositivos de E/S son recursos que han de estar protegidos (ejemplo, los archivos, las impresoras, )

Cmo se consigue? Las instrucciones mquina para acceso a los dispositivos de E/S no pueden ejecutarse en modo usuario: son privilegiadas.

DEPARTAMENTO DE _______________________________________


Cualquier acceso a los dispositivos desde un programa de usuario se har mediante peticiones al SO.



Proteccin de Memoria

Cada programa en ejecucin requiere de un espacio de memoria.

Objetivo: Hay que proteger la zona de memoria asignada y la memoria en la que est el cdigo del sistema operativo (tabla de vectores de interrupcin, rutinas de tratamiento de cada interrupcin).

DEPARTAMENTO DE _______________________________________



Tema 1. Sistema de Cmputo1.3 El Sistema Operativo1.3 El Sistema Operativo

El Sistema Operativo [Stal05] (cap.2, pp.53-104)

Un SO es un programa o conjunto de programas que controla la ejecucin de los programas de aplicacin y que acta como interfaz entre el usuario de una computadora y el hardware de la misma.


DEPARTAMENTO DE _______________________________________


Hardware

Sistema Operativo




El SO como interfaz Usuario/Computadora

Presenta al usuario una mquina abstracta ms fcil de programar que el hardware subyacente:

Oculta la complejidad del hardware. Da tratamiento homogneo a diferentes objetos de bajo nivel (archivos,

procesos, dispositivos, etc.).

DEPARTAMENTO DE _______________________________________


procesos, dispositivos, etc.).

Una aplicacin se puede expresar en un lenguaje de programacin y la desarrolla un programador de aplicaciones.

Es ms fcil programar las aplicaciones en lenguajes de alto nivel que en el lenguaje mquina que entiende el hardware.


1er Curso de Grado en Ingeniera Informtica1.3 El Sistema Operativo1.3 El Sistema Operativo


Un SO proporciona normalmente utilidades en las siguientes reas:

Desarrollo de programas (editores de texto, compiladores, depuradores de programas).

Ejecucin de programas (cargador de programas y ejecucin de stos).

DEPARTAMENTO DE _______________________________________


Ejecucin de programas (cargador de programas y ejecucin de stos).

Acceso a dispositivos de E/S (cada dispositivo requiere su propio conjunto de instrucciones).




(cont.)

Acceso al sistema (En sistemas compartidos o pblicos, el SO controla el acceso y uso de los recursos del sistema: Shell, Interfaz grfico).

Deteccin y respuesta a errores (tratamiento de errores a nivel software y

DEPARTAMENTO DE _______________________________________


Deteccin y respuesta a errores (tratamiento de errores a nivel software y hardware).

Contabilidad (estadsticas de uso de los recursos y medida del rendimiento del sistema).



El SO como Administrador de Recursos

Un computador es un conjunto de recursos y el SO debe gestionarlos y para ello posee un mecanismo de control en dos aspectos:

Las funciones del SO actan de la misma forma que el resto del software, es decir, son programas ejecutados por el procesador.

DEPARTAMENTO DE _______________________________________


El SO frecuentemente cede el control y depende del procesador para volver a retomarlo.




Por lo tanto:

El SO Dirige al procesador en el uso de los recursos del sistema y en la temporizacin de la ejecucin de otros programas.

Una parte del cdigo del SO se encuentra cargado en la memoria principal

DEPARTAMENTO DE _______________________________________


Una parte del cdigo del SO se encuentra cargado en la memoria principal (kernel y, en ciertos momentos, otras partes del SO que se estn usando). El resto de la memoria est ocupada por programas y datos de usuario.




Por lo tanto: (cont.)

La asignacin de la memoria principal la realizan conjuntamente el SO y el hardware de gestin de memoria del procesador.

El SO decide cundo un programa en ejecucin puede usar un dispositivo

DEPARTAMENTO DE _______________________________________


El SO decide cundo un programa en ejecucin puede usar un dispositivo de E/S y tambin el acceso y uso de los ficheros. El procesador es tambin un recurso.



Caractersticas deseables en un Sistema Operativo

Comodidad en el uso.

Eficiencia: Existen ms programas que recursos. Hay que repartir los recursos entre los programas

Facilidad de Evolucin: Un SO importante debe evolucionar en el tiempo por

DEPARTAMENTO DE _______________________________________


Facilidad de Evolucin: Un SO importante debe evolucionar en el tiempo por las siguientes razones:

Actualizaciones del hardware y nuevos tipos de hardware. Mejorar y/o aportar nuevos servicios. Resolucin de fallos.


1er Curso de Grado en Ingeniera Informtica1.4 Utilidades del Sistema1.4 Utilidades del Sistema

Programas de Servicio del SO [Prie06] (Cap.13, seccin 13.1, pp.518-520)

Se trata de un conjunto de programas de servicio que, en cierta medida, pueden considerarse como una ampliacin del SO:

Compactacin de discos. Compresin de datos. Gestin de comunicaciones.

DEPARTAMENTO DE _______________________________________


Gestin de comunicaciones. Navegadores de internet. Respaldo de seguridad. Recuperacin de archivos eliminados. Antivirus. Salvapantallas. Interfaz grfica.


1er Curso de Grado en Ingeniera Informtica1.4 Utilidades del Sistema1.4 Utilidades del Sistema

Herramientas Generales

Su misin es facilitar la construccin de las aplicaciones de los usuarios, sea cual sea la naturaleza de stas, tales como:

Editores de texto. Compiladores. Intrpretes.

DEPARTAMENTO DE _______________________________________


Intrpretes. Enlazadores. Cargadores/Montadores.



Contenidos

2.1 Componentes de un Sistema Operativo (SO) multiprogramado.

2.1.1 Sistemas multiprogramados y de tiempocompartido.2.1.2 Concepto de proceso.2.1.3 Modelo de cinco estados de los procesos.

2.2 Descripcin y control de procesos.2.2.1 Bloque de control de proceso (PCB).2.2.2 Control de procesos.

Objetivos

Conocer los elementos necesarios para implementar la multiprogramacin en un sistema operativo (SO).

Conocer el concepto de proceso y el modelo de cinco estados de los procesos.

Conocer el uso que realiza el SO del apoyo hardware e integrarlo en el modelo de cinco estados.

Conocer el concepto de hebra (hilo), su modelo

Tema 2. Introduccin a losTema 2. Introduccin a losSistemas OperativosSistemas Operativos

DEPARTAMENTO DE _______________________________________


Bibliografa bsica[Stal05] W. Stallings, Sistemas Operativos, Aspectos Internos y Principios de Diseo (5 Edicin).

Pearson Education, 2005

[Carr07] J. Carretero, F. Garca, P. de Miguel, F. Prez, Sistemas Operativos (2 Edicin), McGraw-Hill, 2007

1

2.2.2 Control de procesos.2.3 Hebras (hilos)2.4 Gestin bsica de memoria.

2.4.1 Paginacin2.4.2 Segmentacin

Conocer el concepto de hebra (hilo), su modelo de cinco estados y su utilidad.

Conocer la gestin bsica de memoria que realiza el SO.

3-Nov-2010


Tema 2. Introduccin a los Sistemas Operativos

2.1.1 Concepto de multiprogramacin [Stall05] (pp. 5867)

2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado

DEPARTAMENTO DE _______________________________________




2.1.1 Concepto de multiprogramacin


Trabajo 1 Trabajo 2 Trabajo 3

Tipo de trabajo Computacin pesada Gran cantidad de E/S Gran cantidad de E/S

Duracin 5 minutos 15 minutos 10 minutos

Memoria requerida 50 MB 100 MB 75 MB

Necesita disco? NO NO SI

DEPARTAMENTO DE _______________________________________


Necesita terminal? NO SI NO

Necesita impresora? NO NO SI

Trabajo1 utiliza mucho la CPU, Trabajo2 y Trabajo3 utilizan mucho los perifricos de E/S.



Ejemplo de multiprogramacin


DEPARTAMENTO DE _______________________________________




Monoprogramacin Multiprogramacin

Uso del procesador 20% 40%

Uso de memoria 33% 67%

Uso de disco 33% 67%

Uso de impresora 33% 67%

Ejemplo de multiprogramacin


DEPARTAMENTO DE _______________________________________


Uso de impresora 33% 67%

Tiempo transcurrido 30 minutos 15 minutos

Productividad 6 trabajos/hora 12 trabajos/hora

Tiempo de respuesta medio 18 minutos 10 minutos

5



2.1.2 Concepto de proceso [Stal05] (pp. 68-71]

Un programa en ejecucin. Una instancia de un programa ejecutndose en un ordenador La entidad que se puede asignar o ejecutar en un procesador. Una unidad de actividad caracterizada por un solo flujo de ejecucin, un


DEPARTAMENTO DE _______________________________________


estado actual y un conjunto de recursos del sistema asociados.

Un proceso est formado por:Un programa ejecutable.Datos que necesita el SO para ejecutar el programa.

6



Bloque de Control de Proceso (PCB, Process Control Block) [Stall05] (pp. 108-120)

Identificador de proceso, (PID, del ingls Process IDentificator)

Contexto de ejecucin: Registros del procesador Memoria donde reside el programa

2.1 2.1 ComponentesComponentes de un SO de un SO multiprogramadomultiprogramado

Identificador

Estado

Prioridad

Contador de programa

Punteros de memoria

Datos de contexto

DEPARTAMENTO DE _______________________________________


Memoria donde reside el programa Informacin relacionada con recursos del sistema Estado. En que situacin se encuentra el proceso

en cada momento (modelo de estados) Ms informacin

7

Datos de contexto

Informacin de estado de E/S

Informacin de auditora



Implementacin de Procesos Tpica[Stal05] (Fig. 2.8)


Esta implementacin permite ver al proceso como una estructura de datos.

El estado completo del proceso en un instante dado se almacena en su

DEPARTAMENTO DE _______________________________________


un instante dado se almacena en su contexto.

Esta estructura permite el desarrollo de tcnicas potentes que aseguren la coordinacin y la cooperacinentre los procesos.



Concepto de traza de ejecucin

Una traza de ejecucin es un listado de la secuencia de intrucciones de programa que realiza el procesador para un proceso

Desde el punto de vista del procesador se entremezclan las trazas de ejecucin de los procesos y las trazas del cdigo del sistema operativo

Como consecuencia de qu situaciones se entremezclan las trazas de


DEPARTAMENTO DE _______________________________________


Como consecuencia de qu situaciones se entremezclan las trazas de los procesos y las trazas del SO? Ejemplo

9





DEPARTAMENTO DE _______________________________________






DEPARTAMENTO DE _______________________________________




Llamadas al Sistema

Es la forma en la que se comunican los programas de usuario con el SO en tiempo de ejecucin.

Son solicitudes al SO de peticin de servicio.

Ejemplos de llamadas al sistema:Solicitudes de E/S.


DEPARTAMENTO DE _______________________________________


Solicitudes de E/S.Gestin de procesos.Gestin de memoria.

Se implementan a travs de una trampa o interrupcin software.



open()...

int 0x80. . .

open()...

int 0x80. . .

TrampaTrampaModo

usuario

Programa de usuariomain(). . .

open(fd, ). . .

main(). . .

open(fd, ). . .

Biblioteca

12

7

Llamadas al Sistema


DEPARTAMENTO DE _______________________________________


Rutina de serviciode la llamada Manejador de llamadas al sistema

TrampaTrampaModoKernel

Sistema Operativo3 4

5

6system_call:...sys_open()...ret_from_sys_call():...iret

sys_open() {...

...

}

sys_open() {...

...

}

13



2.1.3 Modelo de cinco estados de los procesos

El modelo de cinco estados trata de representar las actividades que el SO lleva a cabo sobre los procesos: Creacin TerminacinMultiprogramacin


DEPARTAMENTO DE _______________________________________


Para ello hace uso de cinco estados: EjecutndosePreparado (listo para ejecutarse)BloqueadoNuevoFinalizado

14



2.1.3 Modelo de cinco estados de los procesos


FinalizadoNuevo

Preparado Ejecutndose

Desasignacin de CPU

Admitido El proceso termin

DEPARTAMENTO DE _______________________________________



BloqueadoEspera por

E/S o sucesoFin de E/So suceso

Planificacin



Transiciones entre estados

Nuevo Preparado. El PCB est creado y el programa est disponible en memoria.

Ejecutndose Finalizado. El proceso finaliza normalmente o es abortado por el SO a causa de un error no recuperable.

Preparado Ejecutndose. El SO (planificador CPU) selecciona un proceso paraque se ejecute en el procesador.


DEPARTAMENTO DE _______________________________________


Ejecutndose Bloqueado. El proceso solicita algo al SO por lo que debe esperar.

Ejecutndose Preparado. Un proceso ha alcanzado el mximo tiempo de ejecucin ininterrumpida.

Bloqueado Preparado. Se produce el evento por el cual el SO bloque al proceso.

Preparado (o Bloqueado) Finalizado. Terminacin de un proceso por parte de otro.

16



2.2.1 Descripcin de procesos: PCB

Identificadores: Del proceso, del padre del proceso, del usuario, Contexto de registros del procesador: PC, PSW, SP, Informacin para control del proceso:

Estado del proceso. (modelo de estados) Parmetros de planificacin

2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos

DEPARTAMENTO DE _______________________________________


Parmetros de planificacin Evento que mantiene al proceso bloqueado Cmo acceder a la memoria que aloja el programa asociado al proceso Recursos utilizados por el proceso

17



Creacin de un proceso: Inicializacin de PCB

Asignar identificador nico al proceso Asignar un nuevo PCB Asignar memoria para el programa asociado Inicializar PCB:


DEPARTAMENTO DE _______________________________________


Inicializar PCB: PC: Direccin inicial de comienzo del programa SP: Direccin de la pila de sistema Memoria donde reside el programa El resto de campos se inicializan a valores por omisin

18



2.2.2 Control de procesos: modos de ejecucin del procesador

Modo usuario. El programa (de usuario) que se ejecuta en este modoslo se tiene acceso a: Un subconjunto de los registros del procesador Un subconjunto del repertorio de instrucciones mquina Un rea de la memoria


DEPARTAMENTO DE _______________________________________


Modo ncleo (kernel). El programa (SO) que se ejecuta en este modotiene acceso a todos los recursos de la mquina

19



Cmo utiliza el SO el modo de ejecucin?

El modo de ejecucin (incluido en PSW) cambia a modo kernel, automticamente por hardware, cuando se produce: Una interrupcin Una excepcin Una llamada al sistema


DEPARTAMENTO DE _______________________________________


Seguidamente se ejecuta la rutina del SO correspondiente al eventoproducido

Finalmente, cuando termina la rutina, el hardware restauraautomticamente el modo de ejecucin a modo usuario

20



Control de procesos: cambio de contexto (cambio de proceso)

Un proceso en estado Ejecutndose cambia a otro estado y un procesoen estado Preparado pasa a estado Ejecutndose

Cundo puede realizarse? Cuando el SO pueda ejecutarse y decidallevarlo a cabo. Luego solamente como resultado de: Una interrupcin


DEPARTAMENTO DE _______________________________________


Una interrupcin Una excepcin Una llamada al sistema

21



Pasos en un cambio de contexto

1) Salvar los registros del procesador en el PCB del proceso queactualmente est en estado Ejecutndose

2) Actualizar el campo estado del proceso al nuevo estado al que pasa e insertar el PCB en la cola correspondiente

3) Seleccionar un nuevo proceso del conjunto de los que se encuentran


DEPARTAMENTO DE _______________________________________


3) Seleccionar un nuevo proceso del conjunto de los que se encuentranen estado Preparado (Scheduler o Planificador de CPU)

4) Actualizar el estado del proceso seleccionado a Ejecutndose y sacarlo de la cola de listos

5) Cargar los registros del procesador con la informacin de los registrosalmacenada en el PCB del proceso seleccionado

22



Control de procesos: cambio de modo

Se ejecuta una rutina del SO en el contexto del proceso que se encuentra en estado Ejecutndose

Cundo puede realizarse? Siempre que el SO pueda ejecutarse, luegosolamente como resultado de: Una interrupcin


DEPARTAMENTO DE _______________________________________


Una interrupcin Una excepcin Una llamada al sistema

23



Pasos en un cambio de modo

1) El hardware automticamente salva como mnimo el PC y PSW y cambia a modo kernel.

2) Determinar automticamente la rutina del SO que debe ejecutarse y cargar el PC con su direccin de comienzo.

3) Ejecutar la rutina. Posiblemente la rutina comience salvando el resto


DEPARTAMENTO DE _______________________________________


3) Ejecutar la rutina. Posiblemente la rutina comience salvando el restode registros del procesador y termine restaurando en el procesador la informacin de registros previamente salvada.

4) Volver de la rutina del SO. El hardware automticamente restaura en el procesador la informacin del PC y PSW previamente salvada.

24



2.3 Concepto de Hebra

El concepto de proceso (tarea) tiene dos caractersticas diferenciadas que permiten al SO:

Controlar la asignacin de los recursos necesarios para la ejecucin de programas.

La ejecucin del programa asociado al proceso de forma intercalada con otros programas.

2.3 Hebras (hilos)2.3 Hebras (hilos)

DEPARTAMENTO DE _______________________________________


El concepto de proceso (tarea) y hebras asociadas se basa en separar estas dos caractersticas:

La tarea se encarga de soportar todos los recursos necesarios(incluida la memoria).

Cada una de las hebras permite la ejecucin del programa de forma independiente del resto de hebras.

25



Concepto de Hebra


DEPARTAMENTO DE _______________________________________




Modelo de cinco estados para hebras

Las hebras debido a su caracterstica de ejecucin de programas presentan cinco estados anlogos al modelo de estados para procesos:

Ejecutndose Preparado (listo para ejecutarse) Bloqueado Nuevo Finalizado


FinalizadoNuevo

DEPARTAMENTO DE _______________________________________


Finalizado

27

Nuevo


Bloqueado

Desasignacin de CPU

Espera porE/S o suceso

Fin de E/So suceso

Admitido

Planificacin

El proceso termin



Ventajas de las hebras


DEPARTAMENTO DE _______________________________________




Ventajas de las hebras Menor tiempo de creacin de una hebra en un proceso ya creado que la

creacin de un nuevo proceso.

Menor tiempo de finalizacin de una hebra que de un proceso.

Menor tiempo de cambio de contexto (hebra) entre hebras pertenecientes al mismo proceso.


DEPARTAMENTO DE _______________________________________


al mismo proceso.

Facilitan la comunicacin entre hebras pertenecientes al mismo proceso.

Permiten aprovechar las tcnicas de programacin concurrente y el multiprocesamiento simtrico.

29



2.4 Carga absoluta y reubicacin [Stall05] (pp. 308-327)

Carga absoluta. Asignar direcciones fsicas (direcciones de memoriaprincipal) al programa en tiempo de compilacin. El programa no esreubicable.

Reubicacin. Capacidad de cargar y ejecutar un programa en un lugararbitrario de la memoria.

2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria

DEPARTAMENTO DE _______________________________________


arbitrario de la memoria.

30



Carga absoluta Reubicacin


Programa Fuente

Compilador(y Encuadernador)

ProgramaX

Programa Fuente

Compilador(y Encuadernador)

Programa0

DEPARTAMENTO DE _______________________________________


S.O.Memoria Principal

X

N

ProgramaEjecutable

X

Ndirecciones absolutas

Cargador

S.O.Memoria Principal

Y

Y+M

ProgramaEjecutable

0

Mdirecciones lgicas o relativas

CargadorOHardware

31



Reubicacin esttica

El compilador genera direcciones lgicas (relativas) de 0 a M. La decisin de dnde ubicar el programa en memoria

principal se realiza en tiempo de carga. El cargador aade la direccin base de carga a todas las

referencias relativas a memoria del programa.


1000

DEPARTAMENTO DE _______________________________________


MOVE A, 100

0

M

Programa ejecutable con direcciones lgicas

Memoria Principal

1000 + M

MOVE A, 1100

32



Reubicacin dinmica

El compilador genera direcciones lgicas (relativas) de 0 a M. La traduccin de direcciones lgicas a fsicas se realiza en

tiempo de ejecucin luego el programa est cargado con referencias relativas.

Requiere apoyo hardware.


bCPU

DEPARTAMENTO DE _______________________________________


Memoria Principal

b + M

MOVE A, 100

CPU

DireccinLgica

+DireccinFsica

Hardware

R.Baseb

33



Espacios para las direcciones de memoria

Espacio de direcciones lgico. Conjunto de direcciones lgicas (o relativas) que utiliza un programa ejecutable.

Espacio de direcciones fsico. Conjunto de direcciones fsicas (memoria principal) correspondientes a las direcciones lgicas del programa en un instante dado.

Mapa de memoria de un ordenador. Todo el espacio de memoria


DEPARTAMENTO DE _______________________________________


Mapa de memoria de un ordenador. Todo el espacio de memoria direccionable por el ordenador. Normalmente depende del tamao del bus de direcciones.

Mapa de memoria de un proceso. Estructura de datos (que reside en memoria) que indica el tamao total del espacio de direcciones lgico y la correspondencia entre las direcciones lgicas y las fsicas.

34



Ejemplo de mapa de memoria de un proceso


Cabecera

Fichero EjecutableNmero mgico

Contador de programa inicial

Tabla de secciones

Cdigo

....................

0

1000

5000Secciones

Mapa de memoria

Cdigo

0

4000

DEPARTAMENTO DE _______________________________________


Datos con valor inicial

Tabla de smbolos

. . . . . . . . . . . . . . . .

8000

Secciones Datos con valor inicial5000 Datos sin valor inicial

PilaArgumentos del programa

0

35



Problema de la fragmentacin de memoria


SO 148 k

896 k

SO 148 k

576 k

Proceso 1 320 k

SO 148 k

352 k

Proceso 1 320 k

Proceso 2 224 k

SO 128 k

268 k

Proceso 1 320 k

Proceso 2 224 k

Proceso 3

84 k

DEPARTAMENTO DE _______________________________________


84 k

SO 148 k

268 k

Proceso 1 320 k

224 k

Proceso 3

64 k

SO 148 k

268 k

Proceso 1 320 k

Proceso 4 128 k

Proceso 3

64 k

96 k

SO 148 k

268 k

320 k

Proceso 4 128 k

Proceso 3

64 k

96 k

SO 148 k

268 k

230 k

Proceso 4 128 k

Proceso 3

64 k

96 k

Proceso 590 k

36



Solucin a la fragmentacin de memoria [Stall05] (pp. 340-358) Trocear el espacio lgico en unidades ms pequeas: pginas (elementos

de longitud fija), o segmentos (elementos de longitud variable). Los trozos no tienen por qu ubicarse consecutivamente en el espacio fsico. Los esquemas de organizacin del espacio lgico de direcciones y de

traduccin de una direccin del espacio lgico al espacio fsico que comentaremos son:


DEPARTAMENTO DE _______________________________________


comentaremos son: Paginacin Segmentacin

37


Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software


2.4.1 Paginacin

El espacio de direcciones fsicas de un proceso puede ser no contiguo La memoria fsica se divide en bloques de tamao fijo, denominados

marcos de pgina. El tamao es potencia de dos, de 0.5 a 8 Kb El espacio lgico de un proceso se divide conceptualmente en bloques del

mismo tamao, denominados pginas


DEPARTAMENTO DE _______________________________________

LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________


mismo tamao, denominados pginas Los marcos de pgina contendrn pginas de los procesos

38




Las direcciones lgicas, que son las que genera la CPU se dividen en nmero de pgina (p) y desplazamiento dentro de la pgina (d)

p d


2.4.1 Paginacin

DEPARTAMENTO DE _______________________________________



Las direcciones fsicas se dividen en nmero de marco (m, direccin base del marco donde est almacenada la pgina) y desplazamiento (d)

m d

39




Cuando la CPU genere una direccin lgica ser necesario traducirla a la direccin fsica correspondiente, la tabla de pginas mantiene informacin necesaria para realizar dicha traduccin. Existe una tabla de pginas por proceso

Tabla de marcos de pgina, usada por el S.O. y contiene informacin


2.4.1 Paginacin

DEPARTAMENTO DE _______________________________________



Tabla de marcos de pgina, usada por el S.O. y contiene informacin sobre cada marco de pgina

40




Contenido de la tabla de pginas

Una entrada por cada pgina del proceso:

Nmero de marco (direccin base del marco) en el que est almacenada la pgina si est en MP

Modo de acceso autorizado a la pgina (bits de proteccin)


DEPARTAMENTO DE _______________________________________



Modo de acceso autorizado a la pgina (bits de proteccin)

41




Esquema de traduccin

DESPLAZAMIENTON. paginaDireccin virtual

RBTPN. de marco proteccin

noAcceso autorizado?


DEPARTAMENTO DE _______________________________________



m DESPLAZAMIENTODireccin real

m rw

TABLA DE PAGINAS

si excepcinviolacin de privilegios

42




Implementacin de la Tabla de Pginas

La tabla de pginas se mantiene en memoria principal El registro base de la tabla de pginas (RBTP) apunta a la tabla de pginas (suele almacenarse en el PCB del proceso) En este este esquema cada acceso a una instruccin o dato requiere dos accesos a memoria, uno a la tabla de pginas y otro a


DEPARTAMENTO DE _______________________________________



requiere dos accesos a memoria, uno a la tabla de pginas y otro a memoria.

43




Bfer de Traduccin Adelantada (TLB)

El problema de los dos accesos a memoria se resuelve con una cach hardware de consulta rpida denominada bfer de traduccin adelantadao TLB (Translation Look-aside Buffer) El TLB se implementa como un conjunto de registros asociativos que permiten una bsqueda en paralelo De esta forma, para traducir una direccin:


DEPARTAMENTO DE _______________________________________



De esta forma, para traducir una direccin:1 Si existe ya en el registro asociativo, obtenemos el marco2 Si no, la buscamos en la tabla de pginas y se actualiza el TLB con

esta nueva entrada

44



Esquema de traduccin con TLB

CPU

MemoriaFsica

p d m d

TLB

AciertoTLB


DEPARTAMENTO DE _______________________________________


Fsica

Tabla de pginas

m

TLB

N pginaN marco

FalloTLB

45



2.4.2 Segmentacin

Esquema de organizacin de memoria que soporta mejor la visin de memoria del usuario: un programa es una coleccin de unidades lgicas -segmentos-, p. ej. procedimientos, funciones, pila, tabla de smbolos, matrices, etc.

S1 S1


DEPARTAMENTO DE _______________________________________


S2

S3

S4

S4

S3

S1

Espacio deusuario

Memoriafsica

46




Tabla de Segmentos

Una direccin lgica es una tupla:

La Tabla de Segmentos aplica direcciones bidimensionales definidas por el usuario en direcciones fsicas de una dimensin. Cada entrada de la tabla tiene los siguientes elementos (aparte de presencia,


DEPARTAMENTO DE _______________________________________



de la tabla tiene los siguientes elementos (aparte de presencia, modificacin y proteccin):

base - direccin fsica donde reside el inicio del segmento en memoria.

tamao - longitud del segmento.

47




Implementacin de la Tabla de Segmentos

La tabla de segmentos se mantiene en memoria principal.El Registro Base de la Tabla de Segmentos (RBTS) apunta a la tabla de segmentos (suele almacenarse en el PCB del proceso)El Registro Longitud de la Tabla de Segmentos (STLR) indica el nmero de segmentos del proceso; el n de segmento s, generado en una direccin lgica, es legal si s < STLR (suele almacenarse en el


DEPARTAMENTO DE _______________________________________



una direccin lgica, es legal si s < STLR (suele almacenarse en el PCB del proceso)

48




Esquema de traduccin

dN. SegmentoDireccin virtual

Acceso autorizado?

D. base tamao proteccin.

si

nod > tExcepcin

acceso indebidoRBTS


DEPARTAMENTO DE _______________________________________



S + dDireccin real

si

noAcceso autorizado?

Excepcinviolacin de privilegios

S t

TABLA DE SEGMENTOS

rw

49

Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos

Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada

Ejemplo estados/transicionesCambio de procesoPlanificacin

22 Procesos y hebrasProcesos y hebras


68

Idea de implementacinIdea de implementacin

Multiplexamos la CPU en el tiempo, hacemos creer a cada proceso que es nico en la mq.

Programa

CPU

memo

ria

CPU

Programa

CPU

memo

ria

Ejecutndose

Programa

Programa

Mquina_1 Mquina_2

Estado Mq_2Estado Mq_1+

Proceso 1

Programa

Cargamosestado en CPU



69

Diagrama de estadosDiagrama de estados

FinalizadoNuevo


Bloqueado(s)Bloqueado(s)

Interrupcin


Fin de E/So suceso

Admitido

Planificacin

EstadoTransicin

70

Ej.: Proceso en primer planoEj.: Proceso en primer plano% gcc programa.c

FinalizadoNuevo


Bloqueado

Interrupcin


Fin de E/So suceso

Admitido

Planificacin

gcc

shell

% _



71

Ej.: Proceso de fondoEj.: Proceso de fondo

FinalizadoNuevo


Bloqueado

Interrupcin


Fin de E/So suceso

Admitido

Planificacin

gcc

shell

cat

% gcc programa.c &% cat file.txt

72

Cambio de contextoCambio de contexto

P1 P2

switch_context(P1,P2) switch_context(P2,P1)

switch_context()

callreturn

1

2

3

4

M. UsuarioM. Kernel

en detalle, a continuacin

(a)



Ilustracin del cambio de contexto: supuestosIlustracin del cambio de contexto: supuestos

Suponemos dos procesos:P1 esta ejecutando la instruccin n que es una llamada al sistema.P2 se ejecut anteriormente y ahora esta en el estado preparado esperando su turno.

Convenio:Cdigo del SOEstructura de datosFlujo de controlSalvar estructuras de datosInstruccin i-sima a ejecutar

1 - P1 ejecuta n1 - P1 ejecuta nMemoria

CPU

j

n+1 PC

Otro

sre

gist

ros

n

. . .

Proceso 2

Proceso 1

switch_context(P1,P2)

Llamada 2Llamada 1

j

SP

k

ic

PCB2PCB1Contexto kernel

Contexto usuarioResto informacin

t,v,x,yl,n,o,p

int c

Mquina en modo usuario



2 - Salva contexto usuario y ejecuta fon kernel

2 - Salva contexto usuario y ejecuta fon kernel

Memoria

CPU

j

n+1 PC

Otro

sre

gist

ros

n

. . .

Proceso 2

Proceso 1


Llamada 2Llamada 1

j

SP

k

ic



t,v,x,yl,n,o,p

SalvacontextoUsuario

yejecutacdigokernel

Mquina en modo kernel

3 - Parar proceso, invoca a cambio_contexto3 - Parar proceso, invoca a cambio_contexto

Memoria

CPU

j

c+i+1 PC

Otro

sre

gist

ros

n

. . .

Proceso 2

Proceso 1


Llamada 2Llamada 1

r

SP

s

mc

PCB2

n+1,i,j,k

PCB1Contexto kernel


c+i

t,v,x,yl,n,o,p

Invoca aswitch_context




4 - Cambio_contexto()salva contexto kernel4 - Cambio_contexto()salva contexto kernel

Memoria

CPU

j

c+i+1 PC

Otro

sre

gist

ros

n

. . .

Proceso 2

Proceso 1


Llamada 2Llamada 1

r

SP

s

mc

PCB2

n+1,i,j,k

PCB1Contexto kernel


c+i

t,v,x,yl,n,o,p

s_c salvacontexto

kernel


Cmo estamos?Cmo estamos?

Llegados a este punto P1 esta detenido, congelado y nos disponemos a reanudar, descongelar, a P2 (que previamente habamos parado en algn instante anterior).Es decir, estamos en el punto marcado como (a) en la transparencia 18.



5 - Repone contexto kernel de P25 - Repone contexto kernel de P2

Memoria

CPU

j

t PC

Otro

sre

gist

ros

n

. . .

Proceso 2

Proceso 1


Llamada 2Llamada 1

x

SP

y

v

t



c+i,m,r,s

n+1,i,j,k

t,v,x,yl,n,o,p

c


6 - El kernel termina la fon que inicio de P26 - El kernel termina la fon que inicio de P2

Memoria

CPU

j

t PC

Otro

sre

gist

ros

n

. . .

Proceso 2

Proceso 1


Llamada 2Llamada 1

x

SP

y

v

t



c+i,m,r,s

n+1,i,j,k l,n,o,p

c




7 - Finalizada fon, retorna a modo usuario7 - Finalizada fon, retorna a modo usuario

Memoria

CPU

j

l PC

Otro

sre

gist

ros

n

. . .

Proceso 2

Proceso 1


Llamada 2Llamada 1

o

SP

p

n

t



c+i,m,r,s

n+1,i,j,k l,n,o,p

c

El kernel reponeel contexto de usuario


8 - reanudamos ejecucin de P28 - reanudamos ejecucin de P2

CPU

j

l PC

Otro

sre

gist

ros

l

. . .

Proceso 2

Proceso 1


Llamada 2Llamada 1

o

SP

p

n

t



c+i,m,r,s

n+1,i,j,k

c

Mquina en modo usuario



83

PlanificacinPlanificacin

Planificador: definicin y tipos.Algoritmos de planificacin:

FIFOSJFPrioridadesRound-robinColas mltiples

84

Planificadores de procesosPlanificadores de procesos

Planificador - mdulo del SO que controla la utilizacin de un recurso.Planificador a largo plazo (o de trabajos) -selecciona procesos que deben llevarse a la cola de preparados.Planificador a corto plazo (o de la CPU) -selecciona al proceso que debe ejecutarse a continuacin, y le asigna la CPU.



85

Caractersticas de los planificadoresCaractersticas de los planificadores

Planificador a corto plazo: se invoca con mucha frecuencia (del orden de mseg.) por lo que debe ser rpido en su ejecucin.

Planificador a largo plazo: se invoca con menor frecuencia (segundos o minutos) por lo que puede se lento.Controla el grado de multiprogramacin(n de trabajos en memoria principal).

86

Planificador a medio plazoPlanificador a medio plazo

En algunos SOs, p. ej. tiempo compartido, es a veces necesario sacar procesos de memoria (reducir el grado de multiprogra-macin) por cambios en los requisitos de memoria, y luego volverlos a introducir (intercambio -swapping). El planificador a medio plazo se encarga de devolver los procesos a memoria.Es un mecanismo de gestin de memoria que acta como planificador.



87

Rfagas de CPURfagas de CPU

La ejecucin de un proceso consta de ciclos sucesivos rfagas de CPU-E/S.Procesos acotados por E/S - muchas rfagas cortas de CPU.Procesos acotados por CPU - pocas rfagas largas de CPU.Procesos de Tiempo-real ejecucin defi-nida por (repetidos) plazos (deadline). El procesamiento por plazo debe ser conocido y acotado.

88

Cundo planificar?Polticas de planificacinCundo planificar?Polticas de planificacin

Las decisiones de planificacin pueden tener lugar cuando se conmuta del :1. Estado ejecutndose a bloqueando.2. Estado ejecutndose a preparado.3. Estado bloqueado a preparado.4. Estado ejecutndose a finalizado.Es decir, siempre que un proceso abandona la CPU, o se inserta un proceso en la cola de preparados.



89

Polticas de planificacinPolticas de planificacin

Planificacin apropiativa (preemptive): El SO puede quitar la CPU al proceso. Casos 2 y 3.Planificacin no apropiativa (no preemptive): No se puede retirar al proceso de la CPU, este la libera voluntariamente al bloquearse o finalizar. Casos 1 y 4.La eleccin entre ambas depende del comportamiento de la aplicacin y del diseo que queramos hacer del sistema.

90

Apropiacin frente a No-apropiacinApropiacin frente a No-apropiacin

La apropiacin nos asegura que un trabajo no bloquea a otro igualmente importante.Cuestiones a tener en cuenta:

Cundo apropiar? en tiempo de interrupcin?Tamao de la fraccin de tiempo? Afecta al tiempo de respuesta y a la productividad.



91

Apropiacin frente a No apropiacinApropiacin frente a No apropiacin

La planificacin no apropiativa requiere que los trabajos invoquen explcitamente al planificador.Un trabajo errneo puede tirar el sistema.Simplifica la sincronizacin de hebras/procesos.

92

Criterios de planificacinCriterios de planificacin

Utilizacin -mantener la CPU tan ocupada como sea posible.Productividad n de procesos que completan su ejecucin por unidad de tiempo.Tiempo de retorno -cantidad de tiempo necesaria para ejecutar un proceso dado.Tiempo de espera -tiempo que un proceso ha estado esperando en la cola de preparados.Tiempo de respuesta -tiempo que va desde que se remite una solicitud hasta que se produce la primera respuesta (no salida).



93

Mtricas de planificacinMtricas de planificacin

Mxima utilizacin.Mxima produccin.Mnimo tiempo de retorno.Mnimo tiempo de espera.Mnimo tiempo de respuesta.

La eleccin depende del tipo de aplicaciones y el uso del SO. En la mayora de los casos, algunos de

estos criterios son contrapuestos.

94

Primero en Llegar, Primero en ser Servido (FIFO)Primero en Llegar, Primero en ser Servido (FIFO)

Para los procesos de la tabla, construimos el Diagrama Gantt.Tiempos de espera:

P1= 0P2= 24P3= 27

Tiempo medio de espera (te medio ): (0+24+27)/3 = 17

Proceso T. rfaga T. llegada

P1P2P3

2433

000

P1 P2 P3

a)

b)

0 24 27 30



95

Efecto escoltaEfecto escolta

Si cambiamos el orden de ejecucin de los procesos, temedio es mejor:

(6+0+3)/3 = 3Efecto escolta - los procesos cortos esperan a los largos.

P1P2 P3

0 3 6 30

Tiempos de espera:P1= 6P2= 0P3= 3

96

Primero el Ms Corto (SJF)Primero el Ms Corto (SJF)

Se planifica al proceso cuya siguiente rfaga es la ms corta. Tiene dos versiones:

No apropiativa el proceso en ejecucin no se apropia hasta que complete su rfaga.Apropiativa o Primero el de tiempo restante menor (SRTF) un proceso con rfaga ms corta que el tiempo restante del proceso en ejecucin, apropia al proceso actual.



97

Caractersticas de SJFCaractersticas de SJF

Minimiza el te medio para un conjunto dado de procesos (no as, el tiempo de respuesta).Se comporta como un FiFo, si todos los procesos tienen la misma duracin de rfaga.Actualmente se utilizan variantes de este algoritmo para planificacin de procesos en tiempo-real.

98

Ejemplo de SJFEjemplo de SJF

SJF (no apropiativo)

Proceso T. Rfaga T. llegadaP1P2P3P4

7414

0245

P1 P3P2

P4

SRTF (apropiativo)

P1 P2P3

P2 P4 P1

0

0

7 8

2 4 5 7 11

12

16

16

te medio = (0+6+3+7)/4= 4

te medio = (9+1+0+2)/4= 3



99

Planificacin por prioridadesPlanificacin por prioridades

No todos los procesos son iguales, asocia-mos a cada proceso un nmero entero que indique su importancia, y damos la CPU al proceso con mayor prioridad.Puede ser:- apropiativo o no apropiativo.

- esttico o dinmico.Inanicin -los procesos de baja prioridad pueden no ejecutarse nunca.Envejecimiento -incremento de prioridad con el paso del tiempo.

100

Planificacin Round-robin (RR)Planificacin Round-robin (RR)

A cada proceso se le asigna un quantum de CPU (valores tpicos 50-120 ms). Pasado este tiempo, si no ha finalizado ni se ha bloqueado, el SO apropia al proceso y lo pone al final de la cola de preparados.Recordad que se controla el tiempo del quantum mediante el reloj.



101

Caractersticas de RRCaractersticas de RR

Realiza una asignacin imparcial de la CPU entre los diferentes trabajos.Tiempo de espera medio:

bajo si la duracin de los trabajos vara.Malo si la duracin de los trabajos es idntica.

El rendimiento depende del tamao de q:q grande FIFO.q pequeo mucha sobrecarga si q no es grande respecto a la duracin del cambio de contexto.

102

Ejemplo de RR con q = 20Ejemplo de RR con q = 20

El diagrama de Gantt es

Proceso T. Rfaga T. llegadaP1P2P3P4

53176824

0000

Tpicamente, tiene un mayor tiempo deretorno que SRTF, pero mejor respuesta.

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162



103

Colas mltiplesColas mltiples

La cola de preparados se fracciona en varias colas; cada cola puede tener su propio algoritmo de planificacin. Ahora, hay que realizar una planificacin entre colas. Por ejemplo:

Prioridades fijas entre colas.Tiempo compartido - cada cola obtiene tiempo de CPU que reparte entre sus procesos.

104

EjemplosEjemplos

Procesos batch

Cola2 FIFO

Cola1 con RR

CPU

1. Por prioridades: procesos interactivos primero.

2. Tiempo compartido: 80% CPU Cola1, y 20% para Cola2.

Procesos interactivos



105

Colas mltiples con realimentacinColas mltiples con realimentacin

Como el anterior, pero ahora un proceso puede moverse entre varias colas. As, puede implementarse envejecimiento.Parmetros que definen el planificador:

Nmero de colas.Algoritmo de planificacin para cada cola.Mtodos utilizados para determinar:

Cuando ascender de cola a un proceso.Cuando degradar de cola a un proceso.Cola de entrada de un proceso que necesita servicio.

106

Ejemplo:Ejemplo:

Suponemos un sistema con tres colas:Q0 RR con q=8 milisegundos.Q1 RR con q=16 milisegundos.Q2 - FIFO.

Planificacin:1. Un trabajo entra en Q0; sino acaba en 8ms se mueve a Q1. 2. En Q1recibe 16 ms adicionales. Si an no ha finalizado, es apropiado y3. llevado a Q2, hasta que finaliza.



Ejemplo estados/transicionesCambio de procesoPlanificacin

22 Procesos y hebrasProcesos y hebras


Fundamentos del Software1er Curso de Grado en Ingeniera Informtica

DEPARTAMENTO DE _______________________________________


Bibliografa bsica

[Aho08] A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, Compiladores. Principios, Tcnicas y Herramientas (2 Edicin). Addison Wesley, 2008.

[Prie06] A. Prieto, A. Lloris, J.C. Torres, Introduccin a la Informtica (4 Edicin), McGraw-Hill, 2006

[Carr07]

[Levi00]

J. Carretero, F. Garca, P. de Miguel, F. Prez, Sistemas Operativos (2 Edicin), McGraw-Hill, 2007

J. R. Levine, Linkers & Loader. Morgan Kaufman, 2000. Disponible en http://www.iecc.com/linker/

Contenidos3.1 Lenguajes de Programacin.3.2 Construccin de Traductores.3.3 Proceso de Compilacin

3.3.1 Anlisis Lxico.3.3.2 Anlisis Sintctico.3.3.3 Anlisis Semntico.3.3.4 Generacin y Optimizacin de Cdigo.

3.4 Intrpretes.3.5 Modelos de Memoria de un Proceso.3.6 Ciclo de Vida de un Programa.3.7 Bibliotecas.3.8 Automatizacin del Proceso de Compilacin.

Objetivos

Justificar la existencia de los lenguajes de programacin.Conocer el proceso de traduccin.Diferencia entre compilacin e interpretacin.Conocer el proceso de enlazado de programas.Conocer las diferencias entre enlace esttico y dinmico.

Tema 3. Compilacin y Enlazado deProgramas

19-Ene-2011

DEPARTAMENTO DE _______________________________________


Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas

2

Concepto de Lenguaje de Programacin [Prie06] (pp. 581-583)

3.1 Lenguajes de Programacin

Lenguaje de programacin es un conjunto de smbolos y de reglas para combinarlos, que se usan para expresar algoritmos.

Caractersticas: Son independientes de la arquitectura fsica del computador. Una sentencia en un lenguaje de alto nivel da lugar, tras el proceso de traduccin, a

varias instrucciones en lenguaje mquina. Algo expresado en un lenguaje de alto nivel utiliza notaciones ms cercanas a las

habituales en el mbito en que se usan.

Lenguaje de Alto Nivel

Lenguaje Ensamblador

Lenguaje Mquina

A=B+CLDA 0,4,3LDA 2,3,3ADD 2,0STA 0,5,3

021404031403143000041405

DEPARTAMENTO DE _______________________________________



3

Definicin de Traductor

3.2 Construccin de Traductores

Traductor es un programa que recibe como entrada un texto en un lenguaje de programacin concreto y produce, como salida, un texto en lenguaje mquina equivalente.

Entrada lenguaje fuente, que define a una mquina virtual.Salida lenguaje objeto, que define a una mquina real.

La forma en la que un programa escrito para una mquina virtual es posible ejecutarlo en una mquina real puede ser:

Compilador. Intrprete.

DEPARTAMENTO DE _______________________________________



4

Definicin de Compilador


Compilador traduce la especificacin de entrada a lenguaje mquina incompleto y con instrucciones mquina incompletas necesidad de un complemento llamado enlazador.

Enlazador (linker) realiza el enlazado de los programas completando las instrucciones mquina necesarias (aade rutinas binarias de funcionalidades no programadas directamente en el programa fuente) y generando un programa ejecutable para la mquina real.

Especificacin en lenguaje no mquina

Programas Objetos

Especificacin en lenguaje Mquina

Compilador

Enlazador

DEPARTAMENTO DE _______________________________________



5

Definicin de Intrprete


Intrprete lee un programa fuente escrito para una mquina virtual realiza la traduccin de manera interna y ejecuta una a una las instrucciones obtenidas para la mquina real.

No se genera ningn programa objeto equivalente al descrito en el programa fuente.

Intrprete Carga y Ejecuta

Carga e Interpreta orden a orden

Especificacinen lenguaje no mquina

Datos Resultados

DEPARTAMENTO DE _______________________________________



6

Esquema de Traduccin


Generador de cdigoT(InsL1) InsL2

Programa fuente L1(G1)

Programa objeto L2(G2)

Analizador SintcticoObtener P en funcin de la

gramtica G1

Analizador SemnticoP = {Ins1, Ins2Insn}L1

Verificacin lxica y sintctica:Comprobar P L1(G1)

Verificacin semntica:Comprobar validez de significado

DEPARTAMENTO DE _______________________________________



7

Definicin de Gramtica


La complejidad de la verificacin sintctica depende del tipo de gramtica que define el lenguaje.

DEPARTAMENTO DE _______________________________________



8

Ejemplo


Dada la gramtica siguiente:

Y el texto de entrada: id+id*(id-(id/id))Usando las reglas de formacin gramatical, se obtendra una representacin que valida la construccin del texto de entrada verificacin sintctica correcta.

DEPARTAMENTO DE _______________________________________



9

Fases en la construccin de un traductor [Aho08] (pp.4-12)

3.3 Fases de Traduccin

Analizador Lxico

Analizador Sintctico

Analizador Semntico

Generador de Cdigo Intermedio

Optimizador de Cdigo Intermedio

Generador de Cdigo

Optimizador de Cdigo

Fase de AnlisisLxico-Sintctico-Semntico

Fase de SntesisGeneracin y Optimizacin

Tabla de Smbolos

DEPARTAMENTO DE _______________________________________



10

Anlisis Lxico. Funcin Principal y Conceptos [Aho08] (pp.109-145)


AnalizadorLxico

Analizador Sintctico

token

Obtener sig. token

Programafuente

Hacia el Anlisis Semntico

Tabla de Smbolos

Funcin: Leer los caracteres de la entrada del programa fuente, agruparlos en lexemas (palabras) y producir como salida una secuencia de tokens para cada lexema en el programa fuente.

Conceptos que surgen del Analizador Lxico: Lexema o Palabra: Secuencia de caracteres del alfabeto con significado propio. Token: Concepto asociado a un conjunto de lexemas que, segn la gramtica del

lenguaje fuente, tienen la misma misin sintctica. Patrn: Descripcin de la forma que pueden tomar los lexemas de un token.

DEPARTAMENTO DE _______________________________________



11

Anlisis Lxico. Funcin Principal y Conceptos. Ejemplo 1


Token Descripcin informal Lexemas de ejemploIF Caracteres i, f ifELSE Caracteres e, l, s, e elseOP_COMP < | > |

DEPARTAMENTO DE _______________________________________



13

Anlisis Lxico. Funcin Principal y Conceptos. Error Lxico.


En muchos lenguajes de programacin, se cubren la mayora de los siguientes tokens:

Un token para cada palabra reservada (if, do, while, else Los tokens para los operadores (individuales o agrupados). Un token que representa a todos los identificadores tanto de variables como de

subprogramas. Uno o ms tokens que representan a las constantes (nmeros y cadenas de

literales). Tokens para cada signo de puntuacin (parntesis, llaves, coma, punto, punto y FRPDFRUFKHWHV

Error lxico: Acontecer cuando el carcter de la entrada no tenga asociado a ninguno de los patrones disponibles en nuestra lista de tokens (ej: carcter extrao en la formacin de una palabra reservada: while)

DEPARTAMENTO DE _______________________________________



14

Anlisis Lxico. Especificacin de los Tokens (1/4)


Patrones de los tokens expresiones regulares

DEPARTAMENTO DE _______________________________________



15



DEPARTAMENTO DE _______________________________________



16



Tambin se define la siguiente notacin taquigrfica para la representacin de expresiones regulares:

DEPARTAMENTO DE _______________________________________



17



Dada la gramtica mostrada anteriormente, los patrones que van a definir a los tokens seran los que muestra la tabla de la derecha:

Token Patrn

ID [a-zA-Z]([a-zA-Z]|[0-9])*ASIGN

IF ifTHEN thenPARIZQ

PARDER

OPBIN _-__

DEPARTAMENTO DE _______________________________________



18

Anlisis Lxico. Reconocimiento de Tokens.


El Anlisis Lxico es un reconocedor de los patrones que se especifican. Aunque se ver en otras asignaturas, los Autmatas Finitos son mquinas de estados capaces de reconocer estos lenguajes.

Cada patrn es reconocido por un Autmata Finito.

Sea P1 | P2 | | Pn los patrones que deber reconocer, se le asociar a cada patrn un AF.

DEPARTAMENTO DE _______________________________________



19

Anlisis Lxico. Reconocimiento de Tokens. Generador de AL (LEX)


Especificacin de los smbolos mediante expresiones regulares

Acciones

Generador de Analizadores de Lxico

Program

Fundamentos del Software UGR

Documents

Transcript of Fundamentos del Software UGR