Download - 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
Fundamentos del Software
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
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
Definicin de Bit
Bit: unidad mnima de informacin
Codifica informacin: 1 bit: 0 1 2 bits: 00, 01, 10 11
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
False
3
2n de bits = elementos Log2 elementos = n de bits 10
True
Fundamentos del Software
Tema 1. Sistema de Cmputo
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)
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 4
1 Terabyte (TB) = 210 GB =/= 1 Terabit (Tb)1 Petabyte (PB) = 210 TB =/= 1 Petabit (Pb)
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
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,
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 5
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.
Fundamentos del Software
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.
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 6
-
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica
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)
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 7
A= A + M[17]
Ensamblador y lenguaje mquina:ADD A, M(17) 11000 001 0001 001111
Fundamentos del Software
Tema 1. Sistema de Cmputo
Hardware (Soporte Fsico)
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 8
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
Firmware
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 9
Fundamentos del Software
Tema 1. Sistema de Cmputo
Software (Soporte Lgico)
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 10
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
Definiciones Bsicas [Stal05] (pp.55)
Programas de Aplicacin
Programador
Usuario Final
1.1 Componentes de un Sistema de Cmputo1.1 Componentes de un Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Hardware
Sistema Operativo
Utilidades y Herramientas
Diseador del SO
11
Fundamentos del Software
Tema 1. Sistema de Cmputo
Arquitectura de un Sistema
1.2 Capa Hardware1.2 Capa Hardware
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 12
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
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).
1.2 Capa Hardware1.2 Capa Hardware
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
o Puntero de pila (SP).o Registro de instruccin (IR).o Registro de estado (bits informativos).
13
Fundamentos del Software
Tema 1. Sistema de Cmputo
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.
1.2 Capa Hardware1.2 Capa Hardware
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
ejecucin de instrucciones.
Se denomina ciclo de instruccin al procesamiento requerido por una nica instruccin.
InicioLeer siguiente
instruccin
Ejecutar la
instruccinParada
14
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 15
Fundamentos del Software
Tema 1. Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 16
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 17
Fundamentos del Software
Tema 1. Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 18
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 19
Fundamentos del Software
Tema 1. Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 20
-
Fundamentos del Software
Tema 1. Sistema de Cmputo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 21
Fundamentos del Software
Tema 1. Sistema de Cmputo
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.
1.2 Capa Hardware1.2 Capa Hardware
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 23
Acceso Directo a Memoria (Direct Access Memory, DMA).
Fundamentos del Software
Tema 1. Sistema de Cmputo1.2 Capa Hardware1.2 Capa Hardware
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 24
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.
-
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica
E/S Dirigida por Interrupciones.Evento que interrumpe el flujo normal de ejecucin producido por un elemento externo al procesador. Es un evento asncrono.
Tcnicas de Comunicacin de E/S
1.2 Capa Hardware1.2 Capa Hardware
Problema: En transferencias considerables de memoria a
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 25
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.
Fundamentos del Software
Tema 1. Sistema de Cmputo1.2 Capa Hardware1.2 Capa Hardware
Tcnicas de Comunicacin de E/S
Ciclo de instruccin con interrupciones.
Interrupciones inhabilitadas
Fase de bsqueda Fase de ejecucin Fase de Interrupcin
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 26
InicioLeer siguiente
instruccin
Ejecutar la
instruccin
Parada
Comprobacin de
interrupcin del
procesoInterrupciones habilitadas
-
Fundamentos del Software
Tema 1. Sistema de Cmputo1.2 Capa Hardware1.2 Capa Hardware
Tratamiento de Interrupciones Vectorizadas
CPUDispositivoInterrupcin Salto
i Tabla de vectores de interrupcin
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 27
Cdigodel SO
MemoriaPrincipal
. . .
. . .
Cdigo de usuario
Rutina de serviciode interrupcin i
.......................................
...........................
ide interrupcin
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica
Tratamiento de Interrupciones Vectorizadas [Stal05] (pp. 23. Fig. 1.10)
1.2 Capa Hardware1.2 Capa Hardware
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 28
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
-
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica
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)
1.2 Capa Hardware1.2 Capa Hardware
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 29
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica
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)
1.2 Capa Hardware1.2 Capa Hardware
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 30
-
Fundamentos del Software
Tema 1. Sistema de Cmputo1.2 Capa Hardware1.2 Capa Hardware
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 31
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).
Fundamentos del Software
Tema 1. Sistema de Cmputo1.2 Capa Hardware1.2 Capa Hardware
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 32
Cualquier acceso a los dispositivos desde un programa de usuario se har mediante peticiones al SO.
-
Fundamentos del Software
Tema 1. Sistema de Cmputo1.2 Capa Hardware1.2 Capa Hardware
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 33
Fundamentos del Software
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.
Utilidades y Herramientas
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 34
Hardware
Sistema Operativo
Utilidades y Herramientas
-
Fundamentos del Software
Tema 1. Sistema de Cmputo1.3 El Sistema Operativo1.3 El 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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 35
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.
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica1.3 El Sistema Operativo1.3 El Sistema Operativo
El SO como interfaz Usuario/Computadora
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 3636
Ejecucin de programas (cargador de programas y ejecucin de stos).
Acceso a dispositivos de E/S (cada dispositivo requiere su propio conjunto de instrucciones).
-
Fundamentos del Software
Tema 1. Sistema de Cmputo1.3 El Sistema Operativo1.3 El Sistema Operativo
El SO como interfaz Usuario/Computadora
(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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 37
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).
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica1.3 El Sistema Operativo1.3 El Sistema Operativo
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 38
El SO frecuentemente cede el control y depende del procesador para volver a retomarlo.
-
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica1.3 El Sistema Operativo1.3 El Sistema Operativo
El SO como Administrador de Recursos
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 39
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.
Fundamentos del Software
Tema 1. Sistema de Cmputo1.3 El Sistema Operativo1.3 El Sistema Operativo
El SO como Administrador de Recursos
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 40
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.
-
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica1.3 El Sistema Operativo1.3 El Sistema Operativo
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 41
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.
Fundamentos del Software
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 42
Gestin de comunicaciones. Navegadores de internet. Respaldo de seguridad. Recuperacin de archivos eliminados. Antivirus. Salvapantallas. Interfaz grfica.
-
Fundamentos del Software
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 43
Intrpretes. Enlazadores. Cargadores/Montadores.
-
Fundamentos del Software
1er Curso de Grado en Ingeniera Informtica
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 2
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
2.1.1 Concepto de multiprogramacin
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 3
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.
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Ejemplo de multiprogramacin
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 4
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Implementacin de Procesos Tpica[Stal05] (Fig. 2.8)
2.1 2.1 ComponentesComponentes de un SO de un SO multiprogramadomultiprogramado
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 8
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.
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Como consecuencia de qu situaciones se entremezclan las trazas de los procesos y las trazas del SO? Ejemplo
9
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Concepto de traza de ejecucin
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 10
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Concepto de traza de ejecucin
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 11
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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.
2.1 2.1 ComponentesComponentes de un SO de un SO multiprogramadomultiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 12
Solicitudes de E/S.Gestin de procesos.Gestin de memoria.
Se implementan a travs de una trampa o interrupcin software.
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
open()...
int 0x80. . .
open()...
int 0x80. . .
TrampaTrampaModo
usuario
Programa de usuariomain(). . .
open(fd, ). . .
main(). . .
open(fd, ). . .
Biblioteca
12
7
Llamadas al Sistema
2.1 2.1 ComponentesComponentes de un SO de un SO multiprogramadomultiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.1 2.1 ComponentesComponentes de un SO de un SO multiprogramadomultiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Para ello hace uso de cinco estados: EjecutndosePreparado (listo para ejecutarse)BloqueadoNuevoFinalizado
14
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
2.1.3 Modelo de cinco estados de los procesos
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
FinalizadoNuevo
Preparado Ejecutndose
Desasignacin de CPU
Admitido El proceso termin
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 15
Preparado Ejecutndose
BloqueadoEspera por
E/S o sucesoFin de E/So suceso
Planificacin
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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.
2.1 Componentes de un SO multiprogramado2.1 Componentes de un SO multiprogramado
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Creacin de un proceso: Inicializacin de PCB
Asignar identificador nico al proceso Asignar un nuevo PCB Asignar memoria para el programa asociado Inicializar PCB:
2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Modo ncleo (kernel). El programa (SO) que se ejecuta en este modotiene acceso a todos los recursos de la mquina
19
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Una interrupcin Una excepcin Una llamada al sistema
21
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Una interrupcin Una excepcin Una llamada al sistema
23
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.2 Descripcin y control de procesos2.2 Descripcin y control de procesos
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Concepto de Hebra
2.3 Hebras (hilos)2.3 Hebras (hilos)
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 26
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.3 Hebras (hilos)2.3 Hebras (hilos)
FinalizadoNuevo
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Finalizado
27
Nuevo
Preparado Ejecutndose
Bloqueado
Desasignacin de CPU
Espera porE/S o suceso
Fin de E/So suceso
Admitido
Planificacin
El proceso termin
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Ventajas de las hebras
2.3 Hebras (hilos)2.3 Hebras (hilos)
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 28
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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.
2.3 Hebras (hilos)2.3 Hebras (hilos)
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
al mismo proceso.
Facilitan la comunicacin entre hebras pertenecientes al mismo proceso.
Permiten aprovechar las tcnicas de programacin concurrente y el multiprocesamiento simtrico.
29
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
arbitrario de la memoria.
30
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Carga absoluta Reubicacin
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
Programa Fuente
Compilador(y Encuadernador)
ProgramaX
Programa Fuente
Compilador(y Encuadernador)
Programa0
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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.
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
1000
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
MOVE A, 100
0
M
Programa ejecutable con direcciones lgicas
Memoria Principal
1000 + M
MOVE A, 1100
32
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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.
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
bCPU
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Memoria Principal
b + M
MOVE A, 100
CPU
DireccinLgica
+DireccinFsica
Hardware
R.Baseb
33
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Ejemplo de mapa de memoria de un proceso
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
Cabecera
Fichero EjecutableNmero mgico
Contador de programa inicial
Tabla de secciones
Cdigo
....................
0
1000
5000Secciones
Mapa de memoria
Cdigo
0
4000
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Datos con valor inicial
Tabla de smbolos
. . . . . . . . . . . . . . . .
8000
Secciones Datos con valor inicial5000 Datos sin valor inicial
PilaArgumentos del programa
0
35
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Problema de la fragmentacin de memoria
2.4 Gestin bsica de memoria2.4 Gestin bsica 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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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:
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
comentaremos son: Paginacin Segmentacin
37
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
mismo tamao, denominados pginas Los marcos de pgina contendrn pginas de los procesos
38
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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 Gestin bsica de memoria2.4 Gestin bsica de memoria
2.4.1 Paginacin
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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 Gestin bsica de memoria2.4 Gestin bsica de memoria
2.4.1 Paginacin
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Tabla de marcos de pgina, usada por el S.O. y contiene informacin sobre cada marco de pgina
40
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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)
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Modo de acceso autorizado a la pgina (bits de proteccin)
41
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Esquema de traduccin
DESPLAZAMIENTON. paginaDireccin virtual
RBTPN. de marco proteccin
noAcceso autorizado?
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
m DESPLAZAMIENTODireccin real
m rw
TABLA DE PAGINAS
si excepcinviolacin de privilegios
42
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
requiere dos accesos a memoria, uno a la tabla de pginas y otro a memoria.
43
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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:
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Esquema de traduccin con TLB
CPU
MemoriaFsica
p d m d
TLB
AciertoTLB
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fsica
Tabla de pginas
m
TLB
N pginaN marco
FalloTLB
45
Fundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
S2
S3
S4
S4
S3
S1
Espacio deusuario
Memoriafsica
46
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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,
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
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
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
una direccin lgica, es legal si s < STLR (suele almacenarse en el PCB del proceso)
48
-
Fundamentos del Software
Tema 2. Introduccin a los Sistemas OperativosFundamentos del Software
Tema 2. Introduccin a los Sistemas Operativos
Esquema de traduccin
dN. SegmentoDireccin virtual
Acceso autorizado?
D. base tamao proteccin.
si
nod > tExcepcin
acceso indebidoRBTS
2.4 Gestin bsica de memoria2.4 Gestin bsica de memoria
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOSDEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
69
Diagrama de estadosDiagrama de estados
FinalizadoNuevo
Preparado Ejecutndose
Bloqueado(s)Bloqueado(s)
Interrupcin
Espera porE/S o suceso
Fin de E/So suceso
Admitido
Planificacin
EstadoTransicin
70
Ej.: Proceso en primer planoEj.: Proceso en primer plano% gcc programa.c
FinalizadoNuevo
Preparado Ejecutndose
Bloqueado
Interrupcin
Espera porE/S o suceso
Fin de E/So suceso
Admitido
Planificacin
gcc
shell
% _
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
71
Ej.: Proceso de fondoEj.: Proceso de fondo
FinalizadoNuevo
Preparado Ejecutndose
Bloqueado
Interrupcin
Espera porE/S o suceso
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)
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
switch_context(P1,P2)
Llamada 2Llamada 1
j
SP
k
ic
PCB2PCB1Contexto kernel
Contexto usuarioResto informacin
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
switch_context(P1,P2)
Llamada 2Llamada 1
r
SP
s
mc
PCB2
n+1,i,j,k
PCB1Contexto kernel
Contexto usuarioResto informacin
c+i
t,v,x,yl,n,o,p
Invoca aswitch_context
Mquina en modo kernel
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
switch_context(P1,P2)
Llamada 2Llamada 1
r
SP
s
mc
PCB2
n+1,i,j,k
PCB1Contexto kernel
Contexto usuarioResto informacin
c+i
t,v,x,yl,n,o,p
s_c salvacontexto
kernel
Mquina en modo 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.
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
switch_context(P1,P2)
Llamada 2Llamada 1
x
SP
y
v
t
PCB2PCB1Contexto kernel
Contexto usuarioResto informacin
c+i,m,r,s
n+1,i,j,k
t,v,x,yl,n,o,p
c
Mquina en modo kernel
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
switch_context(P1,P2)
Llamada 2Llamada 1
x
SP
y
v
t
PCB2PCB1Contexto kernel
Contexto usuarioResto informacin
c+i,m,r,s
n+1,i,j,k l,n,o,p
c
Mquina en modo kernel
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
switch_context(P1,P2)
Llamada 2Llamada 1
o
SP
p
n
t
PCB2PCB1Contexto kernel
Contexto usuarioResto informacin
c+i,m,r,s
n+1,i,j,k l,n,o,p
c
El kernel reponeel contexto de usuario
Mquina en modo kernel
8 - reanudamos ejecucin de P28 - reanudamos ejecucin de P2
CPU
j
l PC
Otro
sre
gist
ros
l
. . .
Proceso 2
Proceso 1
switch_context(P1,P2)
Llamada 2Llamada 1
o
SP
p
n
t
PCB2PCB1Contexto kernel
Contexto usuarioResto informacin
c+i,m,r,s
n+1,i,j,k
c
Mquina en modo usuario
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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.
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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.
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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.
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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.
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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).
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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.
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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.
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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
-
Fundamentos del SoftwareTransparencias Complementarias Tema 2 Sistemas Operativos
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
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.
-
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
Jos Antonio Gmez HernndezDpto. Lenguajes y Sistemas Informticos - Universidad de Granada
-
Fundamentos del Software1er Curso de Grado en Ingeniera Informtica
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS 1
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
4
Definicin de Compilador
3.2 Construccin de Traductores
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
5
Definicin de Intrprete
3.2 Construccin de Traductores
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
6
Esquema de Traduccin
3.2 Construccin de Traductores
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
7
Definicin de Gramtica
3.2 Construccin de Traductores
La complejidad de la verificacin sintctica depende del tipo de gramtica que define el lenguaje.
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
8
Ejemplo
3.2 Construccin de Traductores
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
10
Anlisis Lxico. Funcin Principal y Conceptos [Aho08] (pp.109-145)
3.3 Fases de Traduccin
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
11
Anlisis Lxico. Funcin Principal y Conceptos. Ejemplo 1
3.3 Fases de Traduccin
Token Descripcin informal Lexemas de ejemploIF Caracteres i, f ifELSE Caracteres e, l, s, e elseOP_COMP < | > |
-
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
13
Anlisis Lxico. Funcin Principal y Conceptos. Error Lxico.
3.3 Fases de Traduccin
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
14
Anlisis Lxico. Especificacin de los Tokens (1/4)
3.3 Fases de Traduccin
Patrones de los tokens expresiones regulares
-
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
15
Anlisis Lxico. Especificacin de los Tokens (2/4)
3.3 Fases de Traduccin
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
16
Anlisis Lxico. Especificacin de los Tokens (3/4)
3.3 Fases de Traduccin
Tambin se define la siguiente notacin taquigrfica para la representacin de expresiones regulares:
-
DEPARTAMENTO DE _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
17
Anlisis Lxico. Especificacin de los Tokens (4/4)
3.3 Fases de Traduccin
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
18
Anlisis Lxico. Reconocimiento de Tokens.
3.3 Fases de Traduccin
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 _______________________________________
LENGUAJES Y SISTEMAS INFORMTICOS
Fundamentos del SoftwareTema 3. Compilacin y Enlazado de Programas
19
Anlisis Lxico. Reconocimiento de Tokens. Generador de AL (LEX)
3.3 Fases de Traduccin
Especificacin de los smbolos mediante expresiones regulares
Acciones
Generador de Analizadores de Lxico
Program