UNIVERSIDAD PERUANA LAS AMERICAS – ESCUELA …

“Año de la Integración Nacional y el Reconocimiento de Nuestra Diversidad”

UNIVERSIDAD NACIONAL DE UCAYALI

FACULTAD DE INGENIERÍA DE SISTEMAS Y DE

INGENÍERIA CIVIL

ESCUELA PROFESIONAL DE INGENÍERIA DE SISTEMAS

MANUAL DE SISTEMAS

OPERATIVOS

ELABORADO POR :

Ing. RIVERA ECHEGARAY, Luis Alberto

PUCALLPA – PERÚ

2012

UNIVERSIDAD PERUANA LAS AMERICAS – ESCUELA PROFESIONAL DE INGENIERIA DE SISTEMAS MANUAL DE SISTEMAS OPERATIVOS

2

Ingº Rivera Echegaray

Contenido INTRODUCCIÓN ........................................................................................................................ 6

ORIENTACIÓN METODOLÓGICA ......................................................................................... 6

Estructura de un sistema operativo ......................................................................................... 8

Introducción a los sistemas operativos ................................................................................... 8

1.1. Sistema Operativo (SO). .................................................................................................... 8

1.2. El hardware y el software: la arquitectura de von Neuman ......................................... 9

1.3. Funciones de los sistemas operativos. ......................................................................... 11

1.4. Historia de los sistemas operativos. .............................................................................. 12

1.4.1 La primera generación (1945-1955): ........................................................................... 13

1.4.2 La segunda generación (1955-1965). ......................................................................... 13

1.4.3 La tercera generación (1965-1980). ............................................................................ 14

1.4.4 La cuarta generación (a partir de 1980). .................................................................... 15

1.5 Estructura del sistema operativo. .................................................................................... 15

1.5.1 Sistemas monolíticos. .................................................................................................... 15

1.5.2 Sistemas por capas. ....................................................................................................... 16

1.6 Máquinas virtuales ............................................................................................................. 17

1.7 Modelo cliente-servidor. .................................................................................................... 18

Resumen .................................................................................................................................... 18

LECTURA: HISTORIA DE MINIX .......................................................................................... 18

Glosario ...................................................................................................................................... 21

Gestión de procesos ................................................................................................................ 21

Sumario ...................................................................................................................................... 21

Procesos .................................................................................................................................... 22

2.1 Procesos ............................................................................................................................. 22

2.1.1 Contador de programa ................................................................................................... 22

2.2 Estados de un proceso. .................................................................................................... 23

2.2.1 Transiciones de estado. ................................................................................................ 24

2.3 Operaciones sobre los procesos. .................................................................................... 25

2.4 Tabla de procesos. ............................................................................................................ 25

2.5 Comunicación entre procesos. ........................................................................................ 25

2.5.1 Condiciones de competencia. ...................................................................................... 26

2.5.3 Exclusión mutua. ........................................................................................................ 27

2.5.4 Sección critica. ................................................................................................................ 27


3


2.5.5 Ejercicios propuestos. .................................................................................................... 28

3.1 Planificación de procesos. ................................................................................................ 29

3.1.1 Definición de planificador. ............................................................................................. 29

3.2 Tipos planificación. ............................................................................................................ 29

3.3 criterios de la planificación. .............................................................................................. 30

3.3.1 Cálculo del tiempo de retorno ....................................................................................... 30

3.3.2 Cálculo del tiempo de espera ....................................................................................... 30

3.4 Planificación apropiativa y no apropiativa ...................................................................... 30

3.5. Algoritmos de planificación.............................................................................................. 31

3.5.1 Primero en llegar primero en ser servido (FCFS, first come first served) ............. 31

3.5.2 Turno rotatorio (RR, round robin) ................................................................................. 32

3.5.2.1 Características ............................................................................................................. 33

3.5.3 Siguiente el trabajo más corto (SJN, shortest job next) ........................................... 36


3.5.4 Menor tiempo restánte (SRT, shortest remaining time) ........................................... 38

3.5.4.1 Características: ............................................................................................................ 38

3.5.5 Planificación por prioridad ............................................................................................. 40



ADMINISTRACIÓN DE LA MEMORIA ................................................................................. 45

Administración de la memoria ................................................................................................ 45

4.1 Definición ............................................................................................................................. 46

4.2 Asignación de almacenamiento contiguo y no contiguo .............................................. 46

4.3 Asignación contigua de memoria para un solo usuario ............................................... 47

4.3.1 Protección de memoria .................................................................................................. 48

4.3.2 Reasignación de direcciones ........................................................................................ 49

4.3.3 Intercambio ...................................................................................................................... 49

4.4 Multiprogramación. ............................................................................................................ 50

4.4.1 Multiprogramación con particiones fijas (MFT). ......................................................... 50

4.4.3 Una sola cola de trabajo ................................................................................................ 51

4.4.4 Fragmentación interna. .................................................................................................. 52

4.4.5 Fragmentación externa .................................................................................................. 52

4.5 Multiprogramación con número variables de tareas(MVT). ........................................ 53

4.5.1 Compactación ................................................................................................................. 55


4


4.5.2 Técnicas de asignación de memoria ........................................................................... 55

4.5.2.1 Primer Ajuste (First Fit) .............................................................................................. 56

4.5.2.2 Siguiente ajuste (Next-Fit). ........................................................................................ 56

4.5.2.3 Mejor ajuste (Best Fit). ............................................................................................... 57

4.6 Asignación no contigua de memoria ............................................................................... 57

4.6.1 Paginación. ...................................................................................................................... 57

4.6.2 Páginas compartidas. .................................................................................................... 60

4.6.3 Segmentación. ................................................................................................................ 61

Memoria virtual ......................................................................................................................... 65

5.1. Memoria virtual .................................................................................................................. 65

5.2. Paginación bajo demanda. .............................................................................................. 65

5.3.1. Primero en entrar, primero en salir (FIFO, First In First Out) ................................. 67

5.3.2. Anomalía de belady ...................................................................................................... 69

5.3.3 Reemplazo Óptimo ......................................................................................................... 70

5.3.4. Menos recientemente utilizada (LRU, Least Recently Used) ................................. 72

5.3.5. Reloj................................................................................................................................. 74

5.3.6. Algoritmo de Pila ........................................................................................................... 76

5.3.6.1 Distancia de la cadena ............................................................................................... 76

5.3.6.2 Predicción de la tasa de fallos de página ................................................................ 76

Dispositivos de entrada y salida y planificación del disco .................................................. 78

Dispositivos de entrada E/S y planificación de discos ........................................................ 78

6.1. Dispositivos de entrada/salida ........................................................................................ 78

6.2. Dispositivos externos ....................................................................................................... 81

6.3. Módulo de e/s (controladora) .......................................................................................... 81

6.4. Funciones de los módulos de e/s. .................................................................................. 82

6.4.1. Control y temporización. ............................................................................................... 82

6.4.2. Comunicación con el procesador ................................................................................ 82

6.4.3. Comunicación con los dispositivos ............................................................................. 82

6.4.4. Almacenamiento temporal ........................................................................................... 82

6.4.5. Detección de errores ..................................................................................................... 83

6.5. Técnicas para entrada/salida .......................................................................................... 83

6.5.1. E/S programada ............................................................................................................. 83

6.5.2. E/S dirigida por interrupciones .................................................................................... 83

6.5.3. Acceso directo a la memoria (dma): ........................................................................... 84


5


Discos y planificación de disco ............................................................................................... 85

7.1. Discos duros ...................................................................................................................... 85

7.1.1. Capacidad de un disco ................................................................................................. 86

7.1.2. Correspondencia entre sectores físicos y lógicos de un disco. ............................. 87

7.2. Algoritmos de planificación de discos ............................................................................ 88

7.2.1. Primero en llegar, primero en ser servido (FCFS, first come first served) ........... 89

7.2.2. Primero el más cercano a la posición actual (SSTF, shortest seek time first) .... 90

7.2.3. Exploración (algoritmo del ascensor - scan) ............................................................. 92

7.2.4. Exploración circular (c- scan) ...................................................................................... 94

Gestión de archivos ................................................................................................................. 96

Gestión de archivos ................................................................................................................. 96

8.1 Gestión de archivos ........................................................................................................... 96

8.2 Archivos ............................................................................................................................... 96

8.2.1 Estructura de un archivo. .............................................................................................. 97

8.2.2 Tipos de acceso archivo ................................................................................................ 98

8.2.3 Atributos de archivos ..................................................................................................... 99

8.2.4 Operaciones con archivos ............................................................................................. 99

8.3 Directorio ........................................................................................................................... 100

8.3.1 Operaciones con directorios ....................................................................................... 100

8.3.2 Organización de directorios ........................................................................................ 100

8.3.3 Rutas de acceso ........................................................................................................... 101

8.3.3.1 Referencias Absolutas.............................................................................................. 101

8.3.3.2 Referencias Relativas ............................................................................................... 101

8.4 Asignación del espacio de almacenamiento ............................................................... 102

8.4.2 Asignación enlazada .................................................................................................... 103

8.4.3 Asignación enlazada con índice ................................................................................. 105

8.4.4 Nodos-i ........................................................................................................................... 106

8.5 Derecho de acceso .......................................................................................................... 107

Bibliografía ............................................................................................................................... 108


6


INTRODUCCIÓN

El presente Manual cubre los temas desarrollados en el curso de Sistemas

Operativos correspondiente al quinto ciclo de la carrera de Ingeniería de

Sistemas de la Universidad Nacional de Ucayali, por lo que se distribuye de

acuerdo a las unidades correspondientes al silabo.

Esta asignatura de formación profesional especializada de naturaleza teórico

practico, tiene como propósito que el estudiante maneje en un nivel de

competencia los conceptos y funcionamiento de un sistema operativo, para lo

cual el alumno llevara en la parte practica el sistema operativo GNU /Linux,

Unix, Mac, y Windows con los algoritmos que se representa a cada sistema

operativo, se usara la distribución Ubuntu 12.04 por presentar las mejores

condiciones para el aprendizaje de los fundamentos de los sistemas operativos.

ORIENTACIÓN METODOLÓGICA

Este Manual está compuesto por dos partes, parte teórica y parte práctica (guía

de Aprendizaje), La parte teórica está compuesta por las unidades de cinco

unidades las cuales a su vez se dividen en lecciones. Cada una de las

lecciones desarrolla las bases teóricas necesarias para entender el tema,

ejercicios resueltos y ejercicios propuestos. Cada unidad además, presenta un

resumen, una lectura, un glosario de términos, una autoevaluación así como la

bibliografía y los enlaces web correspondiente a la unidad.

La primera unidad contiene los conceptos de un sistema operativo, partes,

evolución y la estructura interna de un sistema operativo; la segunda unidad la

gestión de procesos, en la tercera unidad la gestión de la memoria, en la cuarta

Unidad los dispositivos de entrada y salida y planificación de discos, finalmente

en la quinta unidad, la gestión de archivos.

El objetivo de este libro es que el alumno sea capaz de comprender el

funcionamiento de un sistema operativo, su diseño, entender los procesos, la

gestión de memoria, el manejo de archivos.

El Manual puede ser usado muy fácilmente por los alumnos que se están

iniciando en sistemas operativos, comprender los principios de los sistemas

operativos, y también ver como estos principios se ponen en la práctica en los

sistemas operativos reales.


7


El objetivo de este Manual es que el alumno sea capaz de comprender e iniciar

su aprendizaje en la administración de los sistemas Operativos a través de

conocimientos de Algoritmos avanzados en la cual el Sistema Operativo los

usa, manejo de ficheros y comprender el uso de los comandos en modo shell.

El Manual puede ser entendido fácilmente por aquellos lectores que inician en

el manejo de un sistema operativo. Cada lección explica detalladamente los

conceptos de los comandos, complementado con ejemplos prácticos. Al final

de cada unidad encontrara un modelo de autoevaluación (ejercicios

propuestos) donde el alumno será capaz de resolverlos.


8


Estructura de un sistema operativo

Sumario

La unidad tiene como propósito que el estudiante comprenda el funcionamiento

de una computadora desde el punto de vista plataforma hardware, valorando la

relevancia que tiene un sistema operativo para su desarrollo académico y

profesional. Contiene:

· Introducción a los sistemas operativos, partes de un sistema operativo.

· Evolución, historia de los sistemas operativos.

· Estructura interna de un sistema operativo.

Introducción a los sistemas operativos

1.1. Sistema Operativo (SO).

Un Sistema operativo es un conjunto de programas que se encuentran

ordenados y relacionados entre sí, estos contribuyen a que la computadora

lleve a cabo correcta y eficientemente su trabajo, el sistema operativo controla

la ejecución de los programas de aplicación, permite un acceso eficiente a

recursos compartidos, actúa como interfaz entre las aplicaciones del usuario y

el hardware y ofrece servicios a los programas de aplicación del usuario.

Por lo general una computadora es considerada como parte dura o solo

Hardware, está por sí misma no realiza ningún trabajo. Es por esto que

requiere del software que le permita procesar, almacenar y recuperar

información. El software que trabaja sobre el computador se clasifica en dos

grandes grupos

- Programas del sistema: controlan operaciones de la computadora

- Programas de Aplicación herramientas para el usuario, pudiendo ser

este un diseñador o un usuario final.


9


Un sistema operativo puede ser visto también como unas colecciones

organizadas de extensiones software del hardware, consistentes en rutinas de

control que hacen funcionar al computador y proporcionan un entorno para la

ejecución de programas. Además, estos programas utilizan las facilidades

proporcionadas por el sistema operativo para obtener acceso a recursos del

sistema informático como el procesador, archivos y dispositivos de

entrada/salida (E/S). De esta forma, el SO constituye la base sobre la cual

pueden escribirse los programas de aplicación, los cuales invocaran sus

servicios por medio de llamadas al sistema.

Por otro lado, los usuarios pueden interactuar directamente con el SO a través

de ordenes concretas. En cualquier caso, el SO actúa como interfaz entre los

usuarios/aplicaciones y el hardware de un sistema informático. A nivel interno,

un SO actúa como gestor de los recursos del sistema informático tales como el

Procesador, la memoria, los archivos y los dispositivos de E/S. En esa función,

el SO mantiene actualizada la información relativa al estado de sistemas que

soportan la ejecución concurrente de programas, el SO resuelve las peticiones

conflictivas de recursos de manera que preserve la integridad del sistema y al

hacerlo intenta optimizar el rendimiento final.

1.2. El hardware y el software: la arquitectura de von Neuman

La arquitectura Von Neuman consta de 3 componentes básicos: memoria

principal, unidad central de proceso y dispositivos de entrada/salida. La unidad

central de proceso, está constituida por la unidad logica-matematica, la unidad


10


de control y un conjunto de registros. Los componentes básicos mencionados

se encuentran interconectados para llevar a cabo la función principal del

computador, que consiste en la ejecución de las sentencias que forman los

procesos. Se tienen cuatro elementos estructurales principales.

· Memoria principal: Comúnmente conocida como memoria RAM. En ella se

encuentran los programas a ejecutar, los datos de entrada y los resultados.

La memoria está formada por un conjunto de celdas idénticas que pueden ser

accedidas de forma aleatoria mediante los distintos registros de

direccionamiento. Esta memoria es normalmente volátil y también se conoce

como memoria real.

· La unidad logica-matematica permite efectuar un conjunto de operaciones

aritméticas y lógicas de los datos. Estos datos, que pueden proceder de

memoria principal o ser el resultado de operaciones previas, se almacenaran

en los registros de entrada de que esta unidad dispone. El resultado de la

operación, así como la información relativa al estado de terminación de la

misma, quedaran almacenados en los correspondientes registros.

· La unidad de control es la que se encarga de hacer funcionar al conjunto,

para lo cual lleva a cabo las siguientes funciones:

Lee de memoria las instrucciones que forman el programa.

Interpreta cada instrucción leída.

Lee los datos de memoria referenciados por la instrucción.

Ejecuta la instrucción.

Almacena el resultado de cada instrucción.

· La unidad de Entrada/Salida se encarga de realizar la transferencia de

información entre la memoria (o los registros) y los periféricos. La E/S se puede

efectuar bajo el gobierno de la unidad de control (E/S programada) o de forma

independiente (DMA). El transporte de datos se realiza, pues, entre el

computador y su entorno exterior. Dicho entorno consta de una gran variedad

de dispositivos externos que incluye a los dispositivos de memoria secundaria,

los equipos de comunicación y los terminales.

Se debe mencionar también que los sistemas informáticos disponen de un

conjunto de elementos de interconexión (buses de datos). Estos elementos

están constituidos por mecanismos que permiten la comunicación entre los


11


componentes que conforman el sistema informático, es decir, su función es la

de interconectar procesadores, memoria principal y módulos de E/S.

1.3. Funciones de los sistemas operativos.

Un sistema operativo actúa como interfaz entre la máquina, los programas de

Aplicaciones y el usuario. El sistema operativo también se encarga de

Gestiónar Los recursos del sistema informático para obtener un uso óptimo del

mismo.

Un sistema operativo debe hacer que la interacción del usuario o de los

programas de aplicación con el computador resulte sencilla y fácil y debe

construirse de modo que permita el desarrollo efectivo, la verificación y la

introducción de nuevas funciones en el sistema y, a la vez, no interferir en los

servicios ya proporcionados. El Hardware y el Software que se utilizan para

proveer al usuario de aplicaciones pueden contemplarse de forma estratificada

o jerárquica. Este usuario final no tiene que preocuparse de la arquitectura del

computador y contempla el sistema informático en términos de aplicaciones.

Estas aplicaciones pueden construirse con un lenguaje de programación y son

desarrolladas por los programadores de aplicaciones.

Si se tuviera que desarrollar un programa de aplicación con un conjunto de

instrucciones totalmente responsables del control del hardware, dicho

programa tendría una tarea abrumadora y compleja. Para facilitar esta tarea, se

ofrecen una serie de programas de sistema. Algunos de estos programas

implementan funciones muy utilizadas que ayudan a la creación de

aplicaciones de usuario, la gestión de archivos y el control de los dispositivos

de E/S. El programa de sistema más importante es el sistema operativo.

El sistema operativo oculta al programador los detalles del hardware y le

proporciona una interfaz cómoda para utilizar el sistema y actúa como

mediador, ofreciendo al programador y a los programas de aplicación un

conjunto de servicios y utilidades que faciliten su tarea.

De forma resumida el sistema operativo ofrece servicios en las siguientes

áreas: Creación de programas: El sistema operativo ofrece una gran variedad

de servicios como los editores y depuradores (debuggers), para ayudar al

programador en la creación de programas. Normalmente, estos servicios están

en forma de programas de utilidad que no forman realmente parte del sistema


12


operativo, pero que son accesibles a través de él o Ejecución de programas:

Para ejecutar un programa es necesario realizar un cierto número de tareas.

Las instrucciones y los datos deben cargarse en memoria principal, los archivos

y los dispositivos de E/S deben inicializarse y deben prepararse otros recursos.

El sistema operativo administra todas estas tareas por el usuario.

o Acceso a los dispositivos de E/S: Cada dispositivo de E/S requiere un

conjunto propio y peculiar de instrucciones o señales de control para su

funcionamiento. El sistema operativo, ayudado por los manejadores o drivers

de dispositivo tiene en cuenta estos detalles de forma que el programador

pueda pensar en forma de lecturas y escrituras simples desde o hacia el

dispositivo.

o Acceso controlado a los archivos: El sistema operativo se ocupa del formato

de los archivos y del medio de almacenamiento. En el caso de sistemas de

varios usuarios trabajando simultáneamente, es el sistema operativo el que

brinda los mecanismos para controlar que el acceso a los archivos se lleve a

cabo de una forma correcta.

Acceso al sistema: En el caso de un sistema compartido o público, el

sistema Operativo controla el acceso al sistema como un todo y a los

recursos específicos del sistema. Las funciones de acceso deben

brindar protección a los recursos y a los datos ante usuarios no

autorizados y debe resolver conflictos en la propiedad de los recursos.

Detección y respuesta a errores: Cuando un sistema informático está en

funcionamiento pueden producirse varios errores. El sistema operativo

debe dar una respuesta que elimine la condición de error con el menor

impacto posible sobre las aplicaciones que están en ejecución.

Contabilidad: Un sistema operativo debe recoger estadísticas de

utilización de los diversos recursos y supervisar parámetros de

rendimiento tales como el tiempo de respuesta.

1.4. Historia de los sistemas operativos.

Los sistemas operativos han evolucionado durante muchos años, han estado

de manera muy estrecha vinculados con la arquitectura de las computadoras

en las que se ejecutan, según las generación es de computadoras se pueden


13


encontrar que clase de sistemas operativos usaban. La primera computadora

digital verdadera fue diseñada por el matemático inglés Charles Babbage

(1792-1871) llamada “maquina analítica”, la cual era totalmente mecánica y no

tenía sistema operativo.

1.4.1 La primera generación (1945-1955):

Caracterizada por la construcción de computadoras utilizando tubos de vacío y

Tableros de conmutación. A mediados de la década de 1940, Howard Aiken en

Harvard, John Von Neumann en el Institute for Advanced Study en Princeton, J.

Presper Eckert y William Mauchley en la University of Pennsylvania y Konrad

Zuse en Alemania, entre otros, lograron construir maquinas calculadoras

usando tubos de vacío. Estas máquinas eran enormes, y ocupaban cuartos

enteros con miles de tubos de vacío lo que consumía gran cantidad de potencia

y energía eléctrica, En esas épocas, un grupo de personas diseñaba, construía,

Programaba, operaba y mantenía a cada máquina, la programación se

realizaba en lenguaje de maquina absoluto, a menudo alambrando tableros de

conmutación para controlar las funciones básicas de la máquina. No existían

los lenguajes de programación de ningún tipo. Más adelante a principios de la

década de 1950, la rutina había mejorado un poco con la introducción de las

tarjetas perforadas, era posible escribir programas en tarjetas e introducirlas

para ser leídas con un mecanismo rudimentario de entrada/salida de datos

compuesta por ejes y mesas agujereadas por donde pasaban los ejes que

activaban determinados mecanismos.

1.4.2 La segunda generación (1955-1965).

Caracterizada por la construcción de computadoras utilizando transistores y

sistemas por lotes, la introducción del transistor a mediados de la década de

1950 permitió mejoras significativas en los sistemas informáticos de la época.

Estas máquinas se encerraban en cuartos de computadora con

acondicionamiento de aire especial (Sistemas de refrigeración para protección),

En ese entonces solo algunas empresas y las dependencias del gobierno o

universidades, podían solventar el costo de muchos millones de dólares para

mantenerlas en operación.


14


Para ejecutar una tarea (un programa o serie de programas), un programador

escribía primero el programa en papel en lenguaje FORTRAN o ensamblador y

luego lo perforaba en tarjetas. Después, llevaba el grupo de tarjetas al cuarto

de entrada de datos y lo entregaba a uno de los operadores para que pase las

tarjetas y ejecute el programa, al terminar la rutina de ejecución se imprimían

los resultados, tomando tiempos considerables el acceso de un lugar a otro.

1.4.3 La tercera generación (1965-1980).

Esta generación utilizaba circuitos integrados y multiprogramación para definir

la arquitectura de la computadora, a inicios de los 60, la mayoría de los

fabricantes de computadoras construían computadoras científicas a gran

escala que se usaban para cálculos numéricos en ciencias e ingeniería y

computadoras comerciales orientadas hacia los caracteres, por tanto las rutinas

de manejo eran diferentes para cada una. En esta generación aparece la

multiprogramación la cual consiste en la división de la memoria en varias

secciónes, con un trabajo distinto en cada partición, mientras un trabajo estaba

esperando que terminara sus procesos de Entrada /Salida de datos, otro podía

estar usando la CPU. Al tener en la memoria principal varios trabajos a la vez,

la CPU podía mantenerse ocupada casi todo el tiempo lográndose un alto

rendimiento.

Otra de las características de esta generación es que el sistema operativo

podía cargar un trabajo nuevo del disco en la partición que habida quedado

vacía y ejecutarlo. Esta técnica se llama SPOOLING (“operación simultanea de

Periféricos en línea”) y también se usaba para la salida.

En esta generación se desarrolla el concepto de tiempo compartido, nacido del

mismo concepto de multiprogramación, en la que cada usuario tiene una

terminal en línea y a cada uno se le asigna un tiempo de uso del sistema según


15


Sus necesidades. También se debe mencionar la aparición de MULTICS del

cual más adelante nacería UNIX.

1.4.4 La cuarta generación (a partir de 1980).

Aparecen las computadoras personales basados en circuitos integrados a gran

escala (LSI), chips que contienen miles de transistores en un cm2 de silicio,

nació la era de la computadora personal, donde el software era amistoso con el

usuario, lo que significa que estaba dirigido a usuarios que no solo no sabían

nada de computación, sino que además no tenían necesidad de aprender

complicados procedimientos. Los sistemas operativos que dominaron las

computadoras personales y las estaciones de trabajo eran el MS-DOS de

Microsoft y UNIX. MS-DOS, luego aparece el entorno gráfico y los sistemas

operativos de red.

1.5 Estructura del sistema operativo.

Las principales estructuras de un sistema operativo pueden reducirse a cuatro

diseños; sistemas monolíticos, los sistemas por capas, las máquinas virtuales y

los sistemas cliente-servidor.

1.5.1 Sistemas monolíticos.

Esta estructura consiste en que no hay estructura definida. El sistema operativo

se escribe como una colección de procedimientos, cada uno de los cuales

puede invocar a cualquiera de los otros cuando necesita hacerlo. Cuando se

usa esta técnica, cada procedimiento del sistema tiene una interfaz bien

definida en términos de parámetros y resultados, esta organización sugiere una

estructura básica para el sistema operativo:

Un programa principal que invoca el procedimiento de servicio

solicitado.

Un conjunto de procedimientos de servicio que llevan a cabo las

llamadas al sistema.

Un conjunto de procedimientos de utilería que ayudan a los

procedimientos

de servicio.


16


En este modelo, para cada llamada al sistema hay un procedimiento de servicio

que se ocupa de ella. Los procedimientos de utilería hacen cosas que varios

procedimientos de servicio necesitan, como obtener datos de los programas de

usuario. Esta división de los procedimientos se realiza en tres capas.

1.5.2 Sistemas por capas.

Esta estructura consiste en organizar el sistema operativo como una jerarquía

de capas, cada una construida sobre la que está abajo de ella. Se pueden

definir los siguientes nieles:

Nivel inferior de gestión del procesador, el cual comparte la CPU entre

procesos, se encarga de la Sincronización entre procesos, la

conmutación de la CPU y la gestión de interrupciones.

Nivel de gestión de memoria, se encarga de repartir la memoria entre

procesos y tiene como función la asignación y liberación de memoria y el

control de acceso a la misma.

Nivel superior de gestión de procesos, donde se realiza la gestión de

procesos, acá se crea y destruyen los procesos, se intercambian los

mensajes entre procesos y se inician y detienen los procesos.

Nivel de gestión de dispositivos, se realiza la gestión de las E/S en

función de los dispositivos existentes, se creación los procesos de E/S,

se asigna y liberan los dispositivos de E/S y se planifica la E/S.

Nivel de gestión de la información, se encarga de Gestionar el espacio

de nombres lógicos y la protección de la información. Acá se crean y


17


destruyen los archivos y directorios, se realiza la apertura y cierre de

archivos, lectura y escritura de archivos y protección de acceso.

1.6 Máquinas virtuales

IBM produjo un sistema totalmente diferente, el cual se basaba en una

observación: un sistema de tiempo compartido ofrece (1) multiprogramación y

(2) una maquina extendida con una interfaz más cómoda que el hardware solo.

La esencia de una máquina virtual consiste en separar por completo estas dos

funciones. El corazón del sistema, conocido como monitor de máquina virtual,

se ejecuta en el hardware solo y realiza la multiprogramación, proporcionando

no una, sino varias máquinas virtuales a la siguiente capa superior. Sin

embargo, a diferencia de otros sistemas operativos, estas máquinas virtuales

no son máquinas extendidas, con archivos y otras características bonitas; más

bien, son copias exactas del hardware solo, incluido el modo de kernel/usuario,

E/S, interrupciónes y todo lo demás que la maquina real tiene.


18


1.7 Modelo cliente-servidor.

Esta estructura está basada en implementar la mayor parte de las funciones del

sistema operativo en procesos de usuario. Para solicitar un servicio, como leer

un bloque de un archivo, un proceso de usuario (ahora llamado proceso cliente)

envía la solicitud a un proceso servidor, el cual realiza el trabajo y devuelve la

respuesta. Lo único que el kernel hace es manejar la comunicación entre los

clientes y los servidores. Al dividir el sistema operativo en partes, cada una de

las cuales solo se encarga de una parte del sistema, como el servicio de

archivos, de procesos, de terminales o de memoria, cada parte puede ser

pequeña y manejable.

Resumen

En esta primera unidad se presenta todos los conceptos básicos necesarios

que el estudiante debe conocer de los sistemas operativos, su evolución,

comprender la estructura interna y funcionamiento de un sistema operativo.

LECTURA: HISTORIA DE MINIX

(Obtenido de: Sistemas Operativos: Diseño e Implementación - 2da Edición

Andrew S. Tanenbaum – Albert S. Woodhull 1988) Cuando UNIX era joven

(Versión 6), era facil conseguir el código fuente, bajo licencia de AT&T, y se

estudiaba mucho. John Lions, de la University of New South Wales en

Australia, incluso escribió un librito que describía su operación, línea por línea

(Lions, 1996). Este librito se usó (con permiso de AT&T) como texto en muchos

cursos universitarios de sistemas operativos. Cuando AT&T libero la Versión 7,

comenzó a darse cuenta de que UNIX era un producto comercial valioso, así

que entrego la Versión 7 junto con una licencia que prohibía el estudio del

código fuente en cursos, a fin de evitar poner en peligro su situación de secreto

comercial.

Muchas universidades simplemente abandonaron el estudio de UNIX e

impartieron solo teoría. Desafortunadamente, cuando solo se ensena teoría el

estudiante adquiere una visión desbalanceada de como se ve realmente un

sistema operativo.

Los temás teóricos que suelen cubrirse con gran detalle en cursos y libros

sobre sistemas operativos, como los algoritmos de planificación, en la práctica


19


realmente no son tan importantes. Los temas que en verdad son relevantes,

como E/S y sistemas de archivos, generalmente se descuidan porque no hay

mucha teoría al respecto. A fin de remediar esta situación, uno de los autores

de este libro (Tanenbaum) decidió escribir un nuevo sistema operativo desde

cero que fuera compatible con UNIX desde el punto de vista del usuario, pero

completamente distinto en su interior. Al no utilizar ni una sola línea del código

de AT&T, este sistema evita las restricciones de la licencia, así que puede

usarse en clase o para estudio individual, De esta forma, los lectores pueden

disectar un sistema operativo real para ver que hay dentro, tal como los

estudiantes de biología disecan ranas. El nombre MINIX significa mini-UNIX

porque es lo suficientemente pequeño como para poderlo entender a pesar de

no ser un guru.

Además de la ventaja de eliminar los problemas legales, MINIX tiene otra

ventaja respecto a UNIX: se escribió una década después de UNIX y tiene una

estructura más modular. El sistema de archivos de MINIX, por ejemplo, no

forma parte del sistema operativo, sino que se ejecuta como programa de

usuario. Otra diferencia es que UNIX se diseñó de modo que fuera eficiente;

MINIX se diseñó pensando en que fuera comprensible (hasta donde puede ser

comprensible cualquier programa que ocupa cientos de páginas). El código de

MINIX, por ejemplo, incluye miles de comentarios.

MINIX se diseñó originalmente de modo que fuera compatible con UNIX

Versión 7 (V7). Se usó como modelo esta versión a causa de su sencillez y

elegancia. A veces se dice que la Versión 7 no solo represento una mejora

respecto a sus predecesores, sino también respecto a todos sus sucesores.

Con la llegada de POSIX, MINIX comenzó a evolucionar hacia el nuevo

estándar, al tiempo que mantenía la compatibilidad hacia atrás con los

programas existentes. Este tipo de evolución es común en la industria de las

computadoras, pues ningún proveedor desea introducir un sistema nuevo que

ninguno de sus clientes existentes podrá usar sin grandes convulsiones. La

versión de MINIX Sue se describe en este libro se basa en el estándar POSIX

(a diferencia de la versión descrita en la primera edicion, que se basaba en V7).

Al igual que UNIX, MINIX se escribió en el lenguaje de programación C y se

pretendía que fuera fácil transportarlo a diversas computadoras. La


20


implementación inicial fue para la IBM PC, porque esta computadora se usa

ampliamente.

Subsecuentemente se llevo a las computadoras Atari, Amiga, Macintosh y

SPARC.

Acorde con la filosofía de que “lo pequeño es hermoso”, MINIX originalmente

no requería siquiera un disco duro para ejecutarse, lo que lo ponía al alcance

del presupuesto de muchos estudiantes (aunque puede parecer asombroso

ahora, mediados de la década de 1980 cuando MINIX vio por primera vez la

luz, los discos duros aun eran una novedad de precio elevado). Al crecer MINIX

en funcionalidad y tamaño, llego al punto en que se hizo necesario un disco

duro, pero en concordancia con la filosofía de MINIX basta con una partición de

30 megabytes. En contraste, algunos sistemas UNIX comerciales ahora

recomiendan una partición de disco de 200 MB como mínimo indispensable.

Para el usuario medio sentado ante una IBM PC, ejecutar MINIX es similar a

ejecutar UNIX. Muchos de los programas básicos, como cat, grep, is, make y el

shell están presentes y desempeñan las mismas funciones que sus

contrapartes de UNIX. Al igual que el sistema operativo mismo, todos estos

programas de utilería fueron reescritos completamente desde cero por el autor,

sus estudiantes y algunas otras personas dedicadas.

En todo este libro se usara MINIX como ejemplo. No obstante, casi todo lo que

se diga acerca de MINIX, a menos que se refiera al código en si, también

aplica a UNIX. Muchos de estos comentarios también aplican a otros sistemas.

Esto debe tenerse siempre presente al leer el manual.

Como acotación, es posible que unas cuantas palabras acerca de LINUX y su

relación con MINIX sean de interés para algunos lectores. Poco después de

liberarse MINIX, se formó un grupo de noticias de USENET para hablar de el.

En pocas semanas, este grupo tenía 40000 suscriptores, la mayor parte de los

cuales quería agregar enormes cantidades de nuevas capacidades a MINIX a

fin de hacerlo más grande y mejor (bueno, al menos más grande). Cada día,

varios cientos de ellos ofrecían sugerencias, ideas y fragmentos de código. El

autor de MINIX resistió con éxito esta arremetida durante varios años, a fin de

mantener a MINIX lo suficientemente pequeño y aseado como para que los

estudiantes lo entendieran.


21


Gradualmente, la gente comenzó a convencerse de que su posición era

inamovible.

Finalmente, un estudiante finlandés, Linus Torvalds, decidió escribir un clon de

MINIX que pretendía ser un sistema de producción con abundantes

capacidades, más que una herramienta educativa. Así fue como nació LINUX.

Glosario

Sistema operativo: Conjunto de programas relacionados entre sí.

Programas del sistema: Controla la operación del computador.

Programas de aplicación: Herramientas para el usuario final.

Sistema lotes: Ejecuta un conjunto de instrucciones sin la intervención del

operador.

Operación fuera de línea: El trabajo de un periférico no requiere la conexión al

computador para recibir instrucciones.

Multiprogramación: Ejecución alterna de varios programas en el procesador.

Tiempo compartido: Extensión natural de la multiprogramación.

Cliente servidor: Es un núcleo o kernel muy pequeño, que envuelve un

conjunto de procesos de usuario que implementa los servicios

correspondientes al sistema operativo.

Gestión de procesos

Sumario

La unidad tiene como propósito que el estudiante identifique y comprenda los

procesos, estados de los procesos, comunicación de procesos y planificación

del procesador, valorando la relevancia que tiene los procesos en los sistemas

computacionales modernos. Contiene:

Procesos

Planificación del procesador


22


Procesos

2.1 Procesos

Concepto central de cualquier sistema operativo. Un proceso es un programa

en ejecución que se apoya en datos, recursos, un estado (en cada momento) y

un programa.

En realidad la CPU alterna entre los procesos. Esta alternancia se llama

multiprogramación.

Todas las computadoras modernas hacen varias cosas al mismo tiempo. A la

vez que ejecuta un programa del usuario, una computadora puede leer de un

disco e imprimir en un terminal o impresora.

En sistemas de multiprogramación la CPU alterna de programa en programa,

en un esquema de seudo paralelismo, es decir que la CPU ejecuta en cierto

instante un solo programa, intercambiando muy rápidamente entre uno y otro.

Los procesos se componen:

Programa

Recursos

Estado

Datos

Contador de programa

2.1.1 Contador de programa

Registro que almacena en cada momento la dirección de la memoria de la

siguiente instrucción a ejecutar por el procesador.

El contador de programa (PC) apunta a códigos de distintos programas que

son parte de distintos procesos, como se muestra a continuación


23


2.2 Estados de un proceso.

El estado de un proceso es la situación real en la que se encuentra un proceso

en un determinado tiempo. Los estados de los procesos son internos al sistema

Operativo y transparente al usuario. Para los usuarios su proceso siempre

estará en ejecución.

Los Estados de los Procesos son:

Ejecución: cuando un proceso tiene el control del procesador.

Preparado: proceso que está preparado para ejecutarse, en cuanto

se le dé la oportunidad.

Bloqueado: Procesos que no pueden ejecutarse de momento por

necesitar algún recurso no disponible.

Terminado: Cuando un proceso ha terminado su ejecución pasa a

ser un proceso terminado.

1. Planificador elige este proceso

2. Proceso que está en ejecución y acaba su quantum


24


3. Proceso Bloqueado en espera de datos

4. Los datos están disponibles

5. El proceso termina

2.2.1 Transiciones de estado.

A los cambios de un proceso a lo largo de su existencia se denomina transición

de estado, que son los siguientes:

Comienzo de la ejecución: el proceso es encolado en la cola de

preparados.

Paso a estado de ejecución : se ejecuta el primer proceso de la cola de

preparados.

Paso a estado de bloqueado: Proceso que esta en ejecución y solicita

una operación de E/S será pasado a estado de bloqueado.

Paso a estado de preparado: se produce por las siguientes causas:

Orden de ejecución del programa.

Proceso que está en ejecución y acaba su quantum.

Proceso bloqueado por una operación de E/S y este termina.

Paso ha estado terminado: termina un proceso y sale del sistema.

Aquellos procesos que no están ejecutándose o que están bloqueados tienen

que guardarse en una cola, como se muestra


25


2.3 Operaciones sobre los procesos.

Crear proceso.- se produce con la orden de ejecución del programa y

suele necesitar varios argumentos como el nombre y prioridad.

Destruir un proceso.- se trata de la orden de eliminación del proceso

con la cual el sistema operativo destruye su PCB.

Suspender un proceso.- Paraliza un proceso para ser reanudado

posteriormente. Suele utilizarse de un mal funcionamiento o sobrecarga

del sistema.

Reanudar un proceso.- trata de activar un proceso que ha sido

previamente suspendido.

Cambiar de prioridad a un proceso. A un proceso se le puede

aumentar o disminuir su prioridad.

Despertar un proceso.- Es una forma de desbloquear un proceso,

bloqueado por alguna causa.

2.4 Tabla de procesos.

Para manejar la información de todos los procesos, el sistema operativo

maneja una tabla de procesos, la que contiene una entrada por la información

de cada proceso, a cada una de estas entradas en la tabla de procesos se le

conoce con el nombre de PCB (Process Control Block), como muestra la tabla.

2.5 Comunicación entre procesos.

Los procesos necesitan comunicarse entre ellos a través de compartir espacios

de memoria, ya sea variables compartidas o buffer.


26


2.5.1 Condiciones de competencia.

El almacenamiento compartido podrá estar en memoria principal o en un

archivo compartido. Para ver cómo funciona en la práctica la comunicación

entre procesos, consideremos un ejemplo de un spooler de impresión.

Imaginemos que el directorio spooler tiene un gran número de entradas

numeradas por 0, 1, 2, 3…. Cada una de las cuales puede almacenar el

nombre de un archivo.

Existen dos variables compartidas: out, in

out apunta hacia el siguiente archivo por imprimir

in apunta hacia la siguiente entrada libre.

En un cierto instante, las entradas del 0 al 1 están vacías (los archivos

ya se imprimieron), las entradas del 2 al 3 están ocupadas y esperan su

turno para la impresión.

Proceso_A ( )

{

.......

imprimir_File (in, fileA); //ocurre la Interrupción

in = in + 1;

.....

}

Proceso_B ( )

{


27


.......

imprimir_File (in, fileB);

in = in + 1;

.....

}

Se ejecuta el proceso A y se imprime en la casilla 4 el archivo Fila A, al ocurrir

una interrupción se ejecuta proceso B.

Al ejecutar el proceso B, se imprime file B en la casilla 4 (destruyendo Fila A),

luego se incrementa in en una unidad obteniendo in=5, acabando la ejecución

del proceso B, se ejecuta el proceso A.

Al reanudar la ejecución del proceso A, desde el punto donde fue interrumpido,

se incrementa in en una unidad, obteniendo in=6.

El archivo fileA nunca se imprime y la ranura 5 queda vacía.

Explicación de la secuencia de ejecución :

imprimir_File (in, fileA); => in = 4 (ocurre una interrupción y se ejecuta PB)

imprimir_File (in, fileB); => in = 4 proceso B acaba

in = in + 1; => in = 5

in = in + 1; => in = 6 ( se ejecuta proceso A)

Las situaciones en las que dos o más procesos leen o escriben en ciertos datos

Compartidos, y el resultado final depende de quién ejecuta que y en qué

momento, recibe el nombre de condiciones de competencia.

2.5.3 Exclusión mutua.

Forma de garantizar si un proceso utiliza una variable o algún recurso

compartido, ningún otro proceso lo podrá utilizar. Por lo tanto, cuando un

proceso genera la exclusión mutua, estará ingresando para ejecutar su sección

crítica.

2.5.4 Sección critica.

Parte del código de un programa en la que se hace acceso al recurso

compartido se denomina sección critica.

Por lo tanto, nos concentraremos en encontrar una correcta solución para un

proceso que requiera ingresar para ejecutar su sección critica, y que garantice


28


la exclusión mutua con otros procesos. Para ello se debe de cumplir 4

condiciones:

Dos procesos no pueden estar al mismo tiempo dentro de sus secciones

criticas.

No se puede hacer suposiciones sobre la velocidad o número de

procesadores.

Ningún proceso que se ejecute fuera de su sección critica puede

bloquear a otros procesos.

Ningún proceso debe de esperar eternamente para ingresar a su

sección crítica.

2.5.5 Ejercicios propuestos.

1.- Los procesos P1, P2, P3, P4 se encuentran listos para ingresar el nombre

del archivo, en el orden en que aparecen, a la cola de impresión.

Para poder escribir su nombre en la cola de impresión los procesos deben de

seguir el siguiente algoritmo.

a.- Leer ingreso

b.- Escribir nombre del proceso en la casilla = al valor de ingreso

c.- Ingreso++

d.- Fin

• El proceso 1 (P1), se ejecuta primero y sale del sistema. Durante la

ejecución del P2, luego que el citado proceso escribe su nombre en la

casilla, se produce una interrupción debido a una llamada al sistema.

• El P3 inicia su ejecución, luego se ejecuta P3, P4 y luego el P2.

Cuál es el valor de la variable ingreso al final de la ejecución de los

procesos?

Cual es el valor de la variable salida al final de la ejecución de todos

los procesos?

El nombre del archivo que se ubicara en la posición 5 de la cola de

impresión?

El nombre del archivo que se ubicara en la posición 7 de la cola de

impresión?


29


3.1 Planificación de procesos.

Se refiere a la tara de Gestiónar la compartición de la cpu entre dos o más

procesos listos para ejecutarse, entonces el sistema debe de decidir quién se

ejecuta primero y por cuanto tiempo, esa parte del sistema operativo que toma

la decisión de procesamiento se denomina planificador, el cual emplea

algoritmos de planificación.

3.1.1 Definición de planificador.

Parte del Sistema Operativo que decide cuando un proceso se debe ejecutar

en primer término, utilizando un algoritmo de planificación.

3.2 Tipos planificación.

Tenemos tres tipos de planificación

Largo plazo.- Decide añadir nuevos procesos al conjunto de procesos a

ejecutar, también es invocado cada vez que un proceso termina y

abandona el sistema.

Mediano plazo.- Se encarga de manejar los procesos que

temporalmente fueron suspendidos, ya sea en la cola de listo o

bloqueados

Corto plazo.- determina que proceso de la cola de listo ejecutara la cpu.


30


3.3 criterios de la planificación.

Los criterios ha tener en cuenta a la hora de elegir o diseñar un algoritmo de

planificación:

Equidad: reparto equitativo del procesador.

Eficiencia: optimizar el uso del procesador.

Tiempo de Respuesta: Minimizar el tiempo de respuesta para os

usuarios Interactivos.

Rendimiento: Maximizar el número de trabajos procesadas por hora.

Tiempo de retorno: tiempo que tarda en ejecutarse un proceso

concreto.

Tiempo de espera: tiempo que un proceso espera en la cola de

procesos listos para ejecutarse.

3.3.1 Cálculo del tiempo de retorno

Se calcula mediante la diferencia del tiempo de retorno con el tiempo de inicio.

TRETORNO = TFIN - TINICIO

3.3.2 Cálculo del tiempo de espera

Se calcula mediante la diferencia del tiempo de retorno con el tiempo de

ejecución.

TESPERA = TRETORNO - TEJECUCIÓN

3.4 Planificación apropiativa y no apropiativa

La planificación es no apropiativa, cuando un proceso nunca abandona la cpu,

permitiendo que un proceso se ejecute hasta su finalización. La planificación es

apropiativa, cuando un proceso usa la cpu durante un intervalo de tiempo y el

Planificador los interrumpe en forma temporal, permitiendo que otro proceso se

apropie de la cpu. La planificación apropiativa es utilizada en sistemas de

tiempo compartido, y las no apropiativas en sistemas en batch.


31


3.5. Algoritmos de planificación

Los diferentes algoritmos de planificación son: FCFS, RR, SJN, SRT,

PRIORIDAD, FB.

Para el estudio de las diferentes políticas de planificación, utilizaremos como

ejemplo la tabla 3.4

3.5.1 Primero en llegar primero en ser servido (FCFS, first come first

served)

El procesador ejecuta cada proceso hasta que termina; por tanto, los procesos

que entren en cola de procesos preparados permanecerán encolados de

acuerdo con su tiempo de llegada a la cola de procesos listo hasta que les

toque su ejecución.

Este método también de le conoce con el nombre de FIFO “primero en entrar,

primero en salir” (FIFO, First Input First Output).

La figura 3.5 muestra la lista de procesos ejecutables, de acuerdo al orden de

llegada al sistema, primero se ejecuta el proceso A, acaba y sale del sistema,

luego se ejecuta el proceso B acaba y sale del sistema y asi sucesivamente.

3.5.1.1 Características.

o Es útil para trabajos en lotes.

o Algoritmo simple y fácil de llevar a la práctica.

o Es una planificación no apropiativa.

o Es justa, aunque los procesos largos hacen esperar a los cortos.

o Es una política predecible.


32


o Tiempo promedio de espera tiende a ser largo.

Ejemplo, de acuerdo a la tabla 3.4, hallar el tiempo final, el tiempo de retorno, el

tiempo de espera utilizando el algoritmo FCFS.

Solución:

Los procesos se posesionan en la cola de procesos listos de acuerdo con su

tiempo de llegada como muestra la figura 3.6

Primero se ejecuta el proceso A, finalizando en el instante 3 y sale del sistema,

luego se ejecuta el proceso B, finalizando en el instante 9 (se suma tiempo de

ejecución ) y asi sucesivamente como se muestra Figura 3.6.

3.5.2 Turno rotatorio (RR, round robin)

El algoritmo es cíclico, cada proceso tiene asignado un reparto equitativo del

tiempo del procesador, llamado quantum (q), que varía entre 10 y 100 mseg.

Para la ejecución se ejecuta de acuerdo a FCFS, pero se le asigna un

quantum de tiempo, si transcurrido el quantum el proceso no ha terminado,

pasa a ocupar el último lugar en la cola, concediéndose el procesador al


33


siguiente proceso. Esta interrupción periódica continúa formándose una rueda

de procesos que serán ejecutados cíclicamente hasta que termine.

3.5.2.1 Características

Se utiliza para tiempo compartido, garantizando tiempo de respuesta

razonable para usuarios interactivos.

Es una planificación apropiativa

El rendimiento del algoritmo depende mucho del tamaño del quantum, si

es muy corto, se alternan demasiados procesos, pero si es muy largo

esto puede causar una respuesta lenta a las solicitudes interactivas

breves.

Un quantum cercano a 100 mseg es con frecuencia un compromiso

razonable


Tiempo de espera utilizando el algoritmo RR ( q=3).


34



35



36


3.5.3 Siguiente el trabajo más corto (SJN, shortest job next)

El algoritmo SJN necesita conocer a priori el tiempo de ejecución de los

procesos. El algoritmo SJN, consiste en seleccionar de la cola de listo, el

proceso con menor tiempo de ejecución.

Para obtener el tiempo de procesador que necesita cada proceso, se puede

obtener por información proporcionada por el propio usuario, por el programa,

basándose en la historia anterior, etc.


Se utiliza en trabajos por lotes.

Es una planificación no apropiativo.

El tiempo de espera aumenta de acuerdo con la longitud de los

procesos, pero el tiempo medio de espera con respecto a otras políticas

es óptimo.

Es poco predecible

No es justa con los procesos largos.

Resulta difícil de poner en práctica por los datos que necesita para

realizarse la planificación.


tiempo de espera utilizando el algoritmo SJN.


37



38


3.5.4 Menor tiempo restánte (SRT, shortest remaining time)

El algoritmo SRT es una mezcla del método SJN, el planificador cambia el

proceso que está en ejecución cuando un proceso nuevo se añade a la cola de

listo, con un tiempo de ejecución menor que el proceso que esta ejecutándose

en ese momento, por consiguiente este nuevo proceso se apodera de la cpu.

3.5.4.1 Características:

Es una variante del SJN para hacerla apropiativa

Puede ser injusta, ya que un proceso corto puede echar a uno largo que

este haciendo uso del procesador y que además esté terminado

Presenta una mayor sobrecarga

Es muy eficiente


tiempo de espera utilizando el algoritmo SRT.


39



40


3.5.5 Planificación por prioridad

El algoritmo de prioridad consiste en seleccionar para ejecutar el proceso de la

cola de listo que tenga máxima prioridad.


41


Cada proceso tiene asociada una prioridad, las prioridades pueden ser

asignadas de la siguiente forma:

Estática: no cambian su valor.

Dinámica: asignada por el sistema, cambian de valor.

Cuando las prioridades son fijas, puede surgir el problema de inanición, que

implica que un proceso puede estar esperando indefinidamente sin llegar a

ejecutarse.

Para evitar este problema, se puede aumentar la prioridad a los procesos que

lleven un determinado tiempo esperando para ser ejecutados en cada

interrupción de reloj.


Es utilizada en tiempo compartido

Es una planificación apropiativa

Puede producir inanición


tiempo de espera utilizando el algoritmo prioridad ( máxima =1).


42



43


3.5.6 COLAS MÚLTIPLES CON REALIMENTACION (FB feedback)

La forma de ejecutarse es parecido al algoritmo RR, con la diferencia que RR

los trabajos permanecen asignados a una sola cola desde que entra al sistema,

FB permite que un trabajo pase de una cola a otra.


44


En el algoritmo FB un trabajo que entra en la cola de preparados se sitúa en la

cola 0, para lo cual recibe un quantum de tiempo fijo para toda la cola, si no

acaba durante ese plazo pasa al final de la cola 1.

Si la cola 0 esta vacia, entonces el trabajo que encabeza la cola 1 recibe un

quantum de tiempo, si no termina durante ese plazo es situado al final de la

cola 2. Asi sucesivamente un proceso va cambiando de cola hasta que termine.

Todos los trabajos que entran por primera vez se sitúa en la cola 0.


Soporta bien la sobrecarga.

Es una planificación apropiativa.

Es muy adaptable a las necesidades del sistema, ya que cada cola

puede ser Gestiónada de forma diferente.


tiempo de espera utilizando el algoritmo FB.


45


ADMINISTRACIÓN DE LA MEMORIA

La unidad tiene como propósito que el estudiante identifique y comprende el

funcionamiento de la de memoria, evalúa y aplica con eficiencia los algoritmos

de sustitución de página, valorando la relevancia de estos conocimientos y

algoritmos para su desarrollo académico y profesional. Contiene:

Memoria, partición estática, partición dinámica

Técnicas de asignación de memoria

Memoria virtual

Algoritmos de sustitución de página

Administración de la memoria

La memoria es uno de los recursos importantes de la computadora, hoy en día

casi todas los sistemas de cómputo tienen un alta capacidad de memoria

principal hasta alcanzar valores de gigabytes, sin embargo nunca hay suficiente


46


memoria principal para albergar todos los programas y estructuras de datos

que necesitan los procesos activos y el sistema operativo (Stalling, 2001).

4.1 Definición

La memoria es un elemento del computador que permite almacenar

información.

Esta información puede consistir en programas y datos que deben de residir en

la memoria principal para poderlos ejecutar o hacer referencia a ellos.

El sistema operativo posee un administrador de memoria, el cual cumple las

Siguientes tareas:

Tener un registro de los componentes de memoria que se estén

utilizando y aquellas que no.

Administrar el intercambio entre memoria principal y el disco, cuando

la primera se llena.

En el funcionamiento de una computadora podemos considerar la memoria

como el recurso central, ya que el procesador, y los dispositivos de

entrada/salida acceden a ella para leer y/o grabar información.

La memoria puede ser considerada como una sucesión de bytes o palabras,

cada una con su propia dirección.

4.2 Asignación de almacenamiento contiguo y no contiguo

En los primeros sistemas de cómputo el almacenamiento es contiguo, el

programa ocupa un único bloque contiguo de memoria.

En el almacenamiento no contiguo sus programas se dividen en varias páginas

o segmentos que no necesitan ser contiguos.


47


4.3 Asignación contigua de memoria para un solo usuario

Modo de trabajo en el que solamente un proceso utiliza el procesador siendo

además, el único existente en la memoria principal, de tal forma que hasta que

no termine su trabajo no cederá el control al siguiente programa.

El programa debe añadir el código para realizar el control de los dispositivos de

entrada/salida del computador. Es una forma de utilización ineficaz de la

memoria y se obliga a un conocimiento profundo del hardware utilizado.

Muy pronto el código de entrada /salida se consolido en un sistema de

entrada/salida (input/output control system IOCS). Los usuarios ya no tenían

que escribir el código sino que llamaban a las rutinas IOCS para realizar el

trabajo y acelerar el proceso de codificación. IOCS es considerado el comienzo

del concepto actual de sistemas operativos.

La memoria se divide en dos secciones:

En la primera, se carga el sistema operativo, el cual controla los

dispositivos del computador.

En la segunda, se carga el proceso de un solo usuario, el cual solicita

los servicios al sistema operativo cuando lo requiere.

Ejemplo. Si se dispone de 128kb de memoria principal, el sistema operativo

utiliza 32K, .que espacio quedara disponible si un programa de 64K se va a

ejecutar?

El algoritmo verifica si el tamaño del proceso es mayor que el tamaño de la

memoria, entonces el proceso no se puede ejecutar, en caso contario el

proceso si se puede ejecutar.

Procedimiento Monitor

Si tamaño (proceso) > tamaño (memoria) entonces

Escribir (“no se puede ejecutar proceso”)

Sino


48


Asignar (memoria)

Asignar (procesador)

Ejecutar (proceso)

Liberar (memoria)

Fin_si

FinProcedimiento

En este modo de gestión de memoria se presenta una ventaja:

Los algoritmos de implementación son simples y fácilmente entendibles

por los usuarios y como desventaja se observa dos casos:

o Memoria desperdiciada

o Restricción en el tamaño de los procesos

4.3.1 Protección de memoria

Se debe de proteger la zona del sistema operativo contra cualquier intento de

acceso (accidental o malicioso) por parte del programa del usuario. Esta

protección se realiza con un registro límite que es suministrado por el

hardware.

Cada dirección (instrucción o dato), generado por el programa del usuario, se

compara con una dirección limite o separadora permitiendo el acceso o no a

memoria.

Si la dirección del programa del usuario es mayor o igual que el registro limite

se permite el acceso a memoria principal; en caso contrario la dirección es una

referencia ilegal a la memoria del sistema operativo, la referencia se intercepta

y se genera un trap al sistema operativo (error de direcciónamiento).

Procedimiento protecionDeMemoria

L = registro limite

Si dirección (usuario) >= L entonces

Asignar (memoria)


Ejecutar (proceso)

Liberar (memoria)

Sino

Escribir (“Error de direcciónamiento”)


49


Fin_si

FinProcedimiento

4.3.2 Reasignación de direcciones

Un dispositivo especial de hardware intercepta cada dirección lógica generada

por un programa y le sumara el contenido del registro límite para obtener la

dirección física correspondiente.

El registro limite indica la dirección a partir del cual se cargara el programa del

usuario.

Tenemos dos tipos de direcciones:

La dirección lógica: en el intervalo 0 a max - 1

La dirección física: en el intervalo 0 + L a L+ max - 1

Donde L= registro limite

4.3.3 Intercambio

El desarrollo de dispositivos rápidos de almacenamiento secundario (discos)

hizo posible mejorar la utilización de la memoria.

Cuando un programa es cargado en memoria queda a la espera de una nueva

Orden, el sistema operativo, lo descarga (swap-out) en dispositivos rápidos de

Almacenamiento secundario, en su lugar cargara el de otro usuario (swap-in)

traído de dicho dispositivo.


50


4.4 Multiprogramación.

Permite el acceso al procesador de varios procesos alternadamente,

repartiendo el tiempo entre todos ellos, según diversas técnicas.

El grado de multiprogramación está limitado por el número de particiónes

o regiones.

Cuando una partición queda libre, se selecciona un programa de la cola

y se carga en la región libre; cuando acaba, la region queda libre para otro

programa.

Hay dos técnicas de gestión de memoria:

Multiprogramación con un número fijo de tareas (MFT).

Multiprogramación con un número variables de tareas (MVT).

4.4.1 Multiprogramación con particiones fijas (MFT).

Se divide la memoria en “n” partes, del mismo o diferentes tamaños. Esta

operación se realiza al iniciar el sistema por el operador, con valores

predefinidos o ingresado explícitamente, quedando inamovible hasta que se

apague el equipo.

Cambiar el tamaño de las particiones requiere detener y arrancar

nuevamente el sistema.

Este esquema se utilizó, en el sistema operativo IBM OS /360 con MFT,

en los grandes mainframe de IBM, actualmente en desuso.

Hay dos enfoques con particiones fijas: colas de entradas independientes para

cada partición y una sola cola de trabajo.

4.4.2 Colas de entrada independiente para cada partición


51


Por ejemplo, si se dispone de una computadora de 1024 kb, el sistema

operativo utiliza 128 kb, se tiene tres particiónes de 128 kb, 256 kb y 512 kb

Supongamos que llega los siguientes trabajos: 500 kb, 120 kb, 450 kb, 100 kb,

400 kb, 250 kb, 200 kb, 110 kb, 80 kb.

Cada trabajo es asignado a una partición más pequeña pero capaz de

contenerlo, puesto que no es deseable desperdiciar un trabajo pequeño, en

una partición grande, entonces 500 kb, es asignado a la partición 3, 120 kb es

asignado a la partición 1, etc.

4.4.3 Una sola cola de trabajo

Un proceso que se encuentra al frente de la cola, se asigna a la partición libre

más pequeña pero capaz de contenerlo.

Con respecto a la protección de memoria se debe de proteger la memoria

contra accesos no deseados, para cada partición, se utiliza 2 registros límites,

que apuntan al límite inferior y superior de cada partición, de tal manera que las

direcciónes generadas por un proceso debe de estar entre estos límites.


52


Procedimiento ProteccionDeMemoria

Li = limite inferior

Ls =limite superior

Si dirección (usuario) >= Li and dirección (usuario) <=Ls entonces

Asignar (memoria)


Ejecutar (proceso)

Liberar (memoria)

Sino

Escribir (“error de direcciónamiento”)

Fin_si

FinProcedimiento

4.4.4 Fragmentación interna.

Ocurre cuando un proceso no ocupa toda la memoria asignada. Un trabajoque

precise "Y" kb de memoria puede ejecutarse en una partición de "X" kb, donde

X>=Y. La diferencia entre estos dos números (X-Y) es la fragmentación interna,

que es la memoria interna respecto a una partición que no se utiliza.

Por ejemplo, un trabajo de 200 kb, se encuentra en una partición de 256 kb, se

desperdicia 56 kb (256 - 200), esta diferencia se denomina fragmentación

interna.

4.4.5 Fragmentación externa

La fragmentación externa se produce cuando una partición permanece

disponible y no se utiliza por ser demásiado pequeña para cualquier trabajo

que se halle en espera.

Por ejemplo, supongamos que tenemos los trabajos de 500 kb, 120 kb, 400

kb, 110 kb.


53


500 kb es asignado a la partición 512 kb, obteniendo una fragmentación interna

de 12 kb, 120 kb es asignado a la partición de 128 kb, obteniendo una

fragmentación interna de 8 kb y la partición 256 kb permanece disponible, pero

es pequeño para el trabajo de 400 kb, entonces se produce una fragmentación

externa.

Como ventaja de la multiprogramación con particiones fijas tenemos lo

siguiente:

La administración es relativamente simple

Protección entre procesos se puede realizar mediante el registro

base y la longitud de la partición.

Y como desventajas:

Se hace una mala utilización de la memoria debido a la poca

flexibilidad del Método

Es complicado correr programas más grandes que el tamaño de la

partición

4.5 Multiprogramación con número variables de tareas(MVT).

El problema del MFT, consiste en definir particiones de tamaño adecuado para

todos los trabajos que se debe de tratar, los diseñadores de sistemas

operativos decidieron una mejora evidente que consiste en permitir que las

particiones varíen dinámicamente.

Cuando se arranca el sistema a medida que van apareciendo los trabajos en la

cola, se van asignando sucesivas particiones hasta que la memoria se

complete, aunque siempre aparece una pequeña fragmentación externa (parte

final de la memoria).


54


Conforme van apareciendo los trabajos, exploramos el conjunto de huecos, si

el hueco es demasiado grande se divide en dos:

Uno para el proceso a cargar.

y la otra es un nuevo hueco.

Cuando acaba un trabajo, libera su bloque de memoria, se devuelve al conjunto

de huecos, si el hueco es adyacente a otro se puede fusionar para formar un

hueco mayor.

Supongamos que tenemos 1024 k de memoria disponible y un sistema

operativo de 128 kb

Se han asignado los trabajos 1, 2 y 3, nos queda libre una partición de 196 kb,

pero es pequeña, para el trabajo en espera de 250 kb, produciéndose una

fragmentación externa.

Como ventaja de la MVT:

Define bloques de tamaño requerido

Termina la fragmentación interna


55


Permite un mejor uso de la memoria.

Y como desventaja:

Fragmentación externa

Como solución al problema de la fragmentación existe lo siguiente:

4.5.1 Compactación

Una solución al problema de la fragmentación es la compactación. El objetivo

es desplazar el conjunto de huecos en un hueco grande.

Ahora todo el almacenamiento libre esta contiguo. Se consume recursos del

sistema que podrían utilizarse en forma productiva.

El sistema debe de retener todas sus actividades mientras se realiza la

compactación.

La compactación implica reubicar los trabajos que están en el almacenamiento.

Ejemplo de compactación:

4.5.2 Técnicas de asignación de memoria

Puesto que la compactación de memoria consume tiempo, el sistema operativo

debe de decidir adecuadamente como asignar un proceso a memoria (como

llenar los huecos).

Existen cuatro técnicas de asignación de memoria: primer ajuste, siguiente

ajuste, mejor ajuste, peor ajuste.

Haremos uso de dos tablas para el desarrollo de ejercicios:


56


4.5.2.1 Primer Ajuste (First Fit)

El gestor de memoria inicia la búsqueda desde el principio de la tabla y usa el

primer hueco que encuentre que sea suficientemente grande como para

satisfacer la petición, permitiendo disminuir el tiempo invertido en analizar la

tabla de área libre.

Usando la tabla 4.2 y tabla 4.3 realizar el primer ajuste.

Solución:

Al asignar memoria queda de la siguiente manera:

El proceso P1, utiliza la primera partición, de 35 kb, quedando disponible 5Kb.

El proceso P2, utiliza la partición de 17 kb, quedando disponible 3K.

4.5.2.2 Siguiente ajuste (Next-Fit).

Es una variante del primer ajuste, iniciando la búsqueda desde donde se quedó

la última asignación, supongamos que el último bloque asignado es 17 kb.

Usando la tabla 3.2 y tabla 3.3 realizar el siguiente ajuste.

Solución:


El proceso P1, utiliza la partición de 45 k, quedando disponible 15Kb.


57


El proceso P2, utiliza la primera partición de 15 kb, quedando disponible 1 Kb.

4.5.2.3 Mejor ajuste (Best Fit).

Busca toda la tabla de regiones libres y elige el hueco que mejor se adapte a la

petición y deje la menor cantidad posible de espacio sin utilizar.


Solución:

Asignar memoria queda de la siguiente manera:

El proceso P1, utiliza la partición de 30 kb, no queda espacio disponible.

El proceso P2, utiliza la partición de 17 kb, quedando disponible 3 Kb.

4.5.4.4 Peor Ajuste (Worst Fit)

Barre toda la lista y usa el espacio más grande posible.


Solución:


El proceso P1, utiliza la partición de 54 kb, quedando disponible 24 kb.

El proceso P2, utiliza la partición de 45 kb, quedando disponible 31 kb.

4.6 Asignación no contigua de memoria

Asigna memoria en forma discontinua

4.6.1 Paginación.

La paginación es una técnica de gestión que permite asignar memoria en forma

Discontinua. La memoria lógica, se divide en bloques del mismo tamaño

denominado página. La memoria física se divide en bloques del mismo tamaño

denominado marcos de página o celdas.


58


Cuando hay que ejecutar un programa, se cargan sus páginas en cualquier

marco disponible y se define la tabla de página para traducir las páginas de

usuario en marcos de memoria.

En un instante dado, algunos de los marcos de memoria están en uso y otras

están libres, el sistema operativo mantiene una lista de marcos libres.

Cada trabajo en memoria tiene su propia tabla de página. Existe fragmentación

interna, los trabajos no ocupan un tamaño múltiplo del tamaño de la página.

Elimina la fragmentación externa, ya que cualquier marco libre es asignado a

un trabajo que lo necesite.

El tamaño de página, es una potencia de 2 que varía entre 512 y 8192 bytes y

viene definido por el hardware.

Mencionaremos algunos tamaños de página para los diferentes sistemas


59


El cálculo del tamaño de marcos de página se obtiene dividiendo el tamaño de

la memoria física, entre el tamaño de página FI= tamaño de la memoria física /

tamaño de página Dentro del programa, cada dirección lógica consta de un

número de página y de un desplazamiento dentro de la página. Dado una

dirección lógica (número de página, desplazamiento), el hardware de

paginación emplea la tabla de página para obtener la dirección física (número

de marco, desplazamiento). La tabla de página tiene una entrada para cada

página, el dato np, se utiliza como un índice en la tabla de página para obtener

el marco correspondiente.

La dirección física se obtiene:

DF = tp[np] * p + d

Calculo de np:

np = DL div p

Calculo de d:

d = DL Mod p

Dónde:

DF = dirección física.

DL = dirección lógica

np = número de página

d = desplazamiento

div =division entera

mod = residuo

La dirección lógica (número de página, desplazamiento), se expresa en

potencias de 2.

Tamaño de dirección lógica: 2m bits

Tamaño de páginas: 2n bits


60


La dirección lógica es de m bits, el desplazamiento es de n bits, y el número de

página es de (m-n) bits.

Dirección lógica

Si tenemos direcciones de 16 bits, el tamaño de página es de 1 kb= 1024 bytes

= 210 bytes, se necesitan 10 bits para el desplazamiento y 6 bits para el

número de página.

El programa podrá tener como máximo 26= 64 páginas de 1kb cada uno

Ejemplo

La tabla de página indica que la página 2 tiene asociado el marco número 4, el

tamaño de página es de 1 Kb. Cual es la dirección física para la dirección

virtual (2,326) dado en el formato (número de página, desplazamiento).

Solución:

p = 1kb =1024 bytes

DL = (2, 326) entonces np = 2, d=326

DF = tp (np)*p+d = tp(2)*1024+ 326

DF = 4*1024+326

4.6.2 Páginas compartidas.

Una ventaja de la paginación es la posibilidad de compartir programas de uso

corriente. Esto es particularmente importante en un sistema de tiempo

compartido.

Consideremos un sistema que soporta 20 usuarios, cada uno de los cuales

utiliza un editor de texto. Si el editor de texto consiste de 40 kb de código y 5 kb


61


de espacio para datos, necesitamos 900 kb para soportar a los 20 usuarios, es

decir:

Sin compartir el editor:

Espacio total = 20*40 +5*20 = 900 kb

Tan solo hace falta mantener una copia del editor de texto en la memoria

principal, cada tabla de página del usuario hace referencia a la misma copia

física del editor, pero las páginas de los datos lo hacen en celdas diferentes

Entonces para soportar a los 20 usuarios precisamos solamente una copia del

editor (40 kb) más 20 copias de espacio de 5k de usuario, es decir:

Al compartir el editor:

Espacio total = 40 +5*20 = 140 kb

El espacio total requerido ahora es de 140 kb en lugar de 900 kb, un ahorro

significativo.

También pueden utilizarse otros programas muy utilizados: compiladores,

Ensambladores, sistema de base de datos, etc.

Supongamos que un editor ocupa 4 páginas, cada tabla de página, del usuario

hace referencia a la misma copia física del editor, pero las páginas de los datos

lo hacen en celdas diferentes.

4.6.3 Segmentación.

La segmentación es otra forma de dividir el programa. Un programa y sus datos

asociados se dividen en un conjunto de segmentos de diferentes tamaños,

aunque existe una longitud máxima del segmento.


62


La segmentación elimina la fragmentación interna. Existe fragmentación

externa pero en grado menor.

Dentro del programa cada dirección lógica consta de un número de segmento y

de un desplazamiento dentro del segmento, el hardware de segmentación

emplea la tabla de segmento para obtener la dirección física.

Para obtener la dirección física hay que seguir los siguientes pasos:

Obtener el número de segmento de la tabla de segmento que actúa

como un índice para obtener la dirección física del comienzo del

segmento.

Comparar el desplazamiento de la dirección lógica con la longitud del

segmento, si el desplazamiento es mayor que la longitud ocasiona un

error de direccionamiento.

La dirección física es la suma de la dirección del comienzo del segmento

más el desplazamiento. Es decir:

DF = base + d

Con respecto a la dirección lógica (número de segmento, desplazamiento) se

expresa en potencias de 2.

Supongamos:

Tamaño de dirección lógica: 2m bits

Tamaño de segmento: 2n bits

Con respecto al tamaño de un programa, si tenemos direcciónes lógicas de m

bits, el desplazamiento es de n bits, el número de segmentos es de (m-n) bits.

El programa tiene como máximo un tamaño de segmento de 212 = 4096 bytes.

Ejemplo

Sean 4 segmentos numerados del 0 al 3, los segmentos están almacenados en

la memoria física como se indica:


63


Ejemplo:

A que direcciones físicas corresponden las siguientes direcciónes virtuales?:

(0,200) (3, 150) (1, 800) El formato corresponde a (número de segmento,

desplazamiento).

Una referencia al segmento 0

(0, 200) se transforma en

DF = base del segmento + desplazamiento = 600 + 200 = 800


(3, 250) se transforma en

DF = base del segmento + desplazamiento = 150 + 250 = 400


(1,800) ocasiona un error de direccionamiento ya que el segmento 1

tiene una longitud de 600.

La compartición se realiza a nivel de segmento, por tanto, cualquier información

puede compartirse definiéndose como un segmento.

Pueden compartirse varios segmentos, de modo que es posible compartir un

programa compuesto de varios segmentos.


64


4.7 Ejercicios propuestos

1. Sea un sistema Gestionado por particiones múltiples de tamaño variable con

los siguientes tamaños de espacio en orden de memoria: 11k, 5k, 22k, 16k, 7k,

9k, 12k y 15k . cual es el espacio que se elige si se solicitan en forma sucesiva

segmentos de:

a) 12k b) 10k

Con el método del primer ajuste, repita ahora la pregunta con el siguiente

ajuste (suponiendo último bloque asignado de 5kb), el mejor ajuste, el peor

ajuste.

2. Sea un sistema por particiones múltiples con una sola cola de trabajo, tiene

tres particiones de 128 kb, 256 kb y 512 kb. Como queda la cola de trabajo

suponiendo que llega tres trabajos 500 kb, 120 kb, 400 kb, 110.


65


Memoria virtual

Los gestores de la memoria virtual proporciona una gran cantidad de memoria

primaria, liberando al programador de preocuparse de las limitaciones de la

memoria.

La memoria virtual trabaja copiando información desde la memoria secundaria

a la primaria actualizando la tabla de página sin la intervención del

programador (Garay nutt, 2004).

5.1. Memoria virtual

La Memoria virtual es una técnica de gestión que, combina hardware y

software, permite la ejecución de programas parcialmente cargados en

memoria real. El sistema operativo mantiene aquellas partes del programa que

se utilicen en cada momento en la memoria principal y el resto permanece en el

disco, aumentando el grado de multiprogramación al requerir menos memoria

real.

Para implementar la Memoria virtual suele emplearse las siguientes técnicas:

- Gestión de memoria por páginas.

- Gestión de memoria por segmentos.

5.2. Paginación bajo demanda.

La paginación bajo demanda es el sistema de memoria virtual más corriente, su

funcionamiento es similar a un sistema de paginación con intercambio, los

programas residen en un dispositivo de intercambio, la memoria auxiliar.

Cuando queremos ejecutar un programa lo cargamos a memoria principal.

Cuando el programa trata de acceder a una página que no se ha llevado a

memoria se produce un fallo de página.

El hardware de paginación traduce la dirección del usuario en una dirección

física utilizando una tabla de página que tiene asociado una columna bit de

validez donde:

v = valido (la página esta en memoria principal)

i = invalido (la página esta en memoria auxiliar).


66


Pasos para un tratamiento de fallos de página

1.- Se detecta que la página no está en memoria.

2.- Se produce una interrupción.

3.- Se busca la página en almacenamiento secundario (disco).

4.- Se busca un marco libre.

5.- Se actualiza la tabla de página.

6.- Reiniciar la instrucción

A

A B

5.3. Algoritmos de reemplazo de página

Existen varios algoritmos de reemplazo de página. FIFO, Remplazo optimo,

LRU, pilas, reloj.


67


Objetivo de cualquier algoritmo de reemplazo, es obtener la menor tasa de

fallos de página posible. La tasa de fallos de página se obtiene dividiendo la

longitud de la cadena de referencia con el número de fallos de página.

t = w / nroFallos

donde:

t = tasa de fallos de página

nroFallos = número de fallos de página

w = longitud de la cadena

5.3.1. Primero en entrar, primero en salir (FIFO, First In First Out)

Reemplaza la página que lleva más tiempo en memoria, es decir sustituye la

página más antigua.

Ejemplo, la cadena de referencia 8, 1, 2, 3, 1, 4, 1, 5, 3, 1. Determina el número

de fallos de página cuando m = 3 y m=4.

Para m=3


68


Se observa que al aumentar el número de marcos, el número de fallos

disminuye.

Como funciona fifo cuando m=3

• Inicialmente las tres celdas están vacías. Las tres primeras referencias (8, 1,

2) generan fallos de página y se cargan en estas celdas vacias.

• En la cuarta referencia (3), no esta en memoria, se produce un fallo de

página, las páginas que están en memoria {8, 1, 2} o La página 8 es la más

antigua, entonces la página 3, reemplaza a la página 8.

• La quinta referencia (1), se encuentra en memoria, no tenemos fallos de

página.

• En la sexta referencia (4), no esta en memoria, se produce un fallo de página

las páginas que están en memoria {3, 1, 2} o La página 1 es la más antigua,

entonces la página 4, reemplaza a la página 1

• En la séptima referencia (1), no esta en memoria, se produce un fallo de

página las páginas que están en memoria {3, 4, 2} o La página 2 es la más

antigua, entonces la página 1, reemplaza a la página 2

• En la octava referencia (5), no esta en memoria, se produce un fallo de página

las páginas que están en memoria {3, 4, 1} o La página 3 es la más antigua,

entonces la página 5, reemplaza a la página 3


69


• En la novena referencia (3), no esta en memoria, se produce un fallo de

página las páginas que están en memoria {5, 4, 1} o La página 4 es la más

antigua, entonces la página 3, reemplaza a la página 4

• La décima referencia (1), se encuentra en memoria, no tenemos fallos de

página.

• Algoritmo sencillo de entender e implementar

• Inconvenientes:

Rendimiento del algoritmo pobre. Páginas frecuentemente usadas

pueden ser sustituidas

Se puede producir la Anomalía de Belady: aumento del número de fallos

de página al aumentar el número de marcos

5.3.2. Anomalía de belady

Al aumentar el número de marcos, el número de fallos disminuye, se muestra

un contraejemplo, que al aumentar el número de marcos, el número de fallos

aumenta, este contraejemplo se conoce como anomalía de belady.


70


f4 = 10 (número de fallos de página, cuando hay 4 celdas)

Observamos que al aumentar el número de marcos, el número de fallos

aumenta.

5.3.3 Reemplazo Óptimo

Se reemplaza la página que va a tardar más tiempo en ser usada, cuando hay

dos o más páginas lejanas se aplican fifo.

La tasa de fallos de página es la más baja posible


71


f3= 6

Cómo funciona el reemplazo optimo

a. A la cadena de referencia le damos numeración: 1, 2, 3, 4,….

Para ubicar la página más lejana.

b. Inicialmente la memoria está vacía, con lo que habrá 3 fallos de

página hasta llenarla

c. En la cuarta referencia (3), no esta en memoria se produce un

fallo de página, las páginas que están en memoria {8, 1, 2}.

d. A partir de la posición 4, vemos las posiciones de las páginas que

están en memoria, vemos la posición de la primera página 8, la

posición de la primera página 1, la primera posición de la página

2, si una página no se encuentra es la más lejana.

e. La página 8 no se encuentra (la página que no se encuentra es la

más lejana)

o La página 1 en la posición 5 ( la primera que encuentre)

o La página 2 no se encuentra (la página que no se encuentra es

la más lejana)

o Tenemos 2 páginas lejanas, 8 y 2, aplicando fifo, la página que

sale es la página 8 que es la más antigua.

Nota, la página 1 está en las posiciones 5, 7, 10 se elige la primera que

es 5.

f. La quinta referencia (1), se encuentra en memoria, no tenemos

fallos de página.


72


g. La sexta referencia (4), no está en memoria se produce un fallo

de página, las páginas que están en memoria {3, 1, 2}

o La página 3 se encuentra en la posición 9

o La página 1 en la posición 7( la primera que encuentre)


la más lejana)

o La página 2 es la más lejana, entonces la página 4, reemplaza a

la página 2

Nota.- La página 1, está en la posiciones 7, 10. Se elige la primera, que es la

Posición 7.

h. La séptima referencia (1), se encuentra en memoria, no tenemos

fallos de página.

i. La octava referencia (5), no está en memoria se produce un fallo

de página, las páginas que están en memoria {3, 1, 4}

o La página 3 se encuentra en la posición 9

o La página 1 en la posición 10


la más lejana)

o La página 4 es la más lejana, entonces la página 5, reemplaza a

la página 4

j. La novena referencia (3), se encuentra en memoria, no tenemos

fallos de página.

k. La décima referencia (1), se encuentra en memoria, no tenemos

fallos de página.

Es el mejor algoritmo de reemplazo de página, pero difícil de implementar, el

sistema operativo no tiene forma de saber a cuál de las páginas se hará

referencia.

5.3.4. Menos recientemente utilizada (LRU, Least Recently Used)

El LRU selecciona la página para ser reemplazada de entre aquellas con un

número máximo de marcos de página hacia atras. Carece de la anomalia de

Belady. Para reemplazar la página se retrocede según el número de marcos

indicado, por ejemplo si el número de marcos es 3, se retrocede tres páginas


73


que deben de ser diferentes, sino se sigue retrocediendo hasta obtener 3

marcos diferentes.

Ejemplo: sea la cadena de referencia 8, 1 , 2, 3, 1, 4, 1, 5, 3, 1 determinar el

Número te fallos de página cuando m=3

Cómo funciona el reemplazo lru

• Inicialmente la memoria está vacía, con lo que habrá 3 fallos de página hasta

llenarla.

• En la cuarta referencia (3), no está en memoria se produce un fallo de página,

las páginas que están en memoria {8, 1, 2}.

Las páginas que están en memoria y la página que va entrar 3

8 1 2 3

o La página 2, se utilizó más recientemente y justo antes que ella se empleó la

página 1, la página 8 se utilizó menos recientemente que hay que remplazarla

entonces la página 3, reemplaza a la página 8.

En otras palabras se retrocede tres celdas, las celdas deben de ser diferentes.

• La quinta referencia (1), se encuentra en memoria, no tenemos fallos de

página.

• En la sexta referencia (4), no está en memoria se produce un fallo de página,



2 3 1 4

o La página 1, se utilizó más reciente1ente y justo antes que ella se empleo la


74


página 3, la página 2 se utilizó menos recientemente que hay que reemplazarla

o Entonces la página 4, reemplaza a la página 2.

• La septima referencia (1), se encuentra en memoria, no tenemos fallos de

página.

• En la octava referencia (5), no esta en memoria se produce un fallo de página,



1 4 1 5

o La página 1, se utilizó más reciente1ente y justo antes que ella se empleo la

página 4, la página 1 es la misma página anterior, entonces la página 3, se

utilizó menos recientemente que hay que reemplazarla.


• En la novena referencia (3), no está en memoria se produce un fallo de

página, las páginas que están en memoria {5, 1, 4}

o La página 5, se utilizó más reciente1ente y justo antes que ella se empleó la

página 1, la página 4, se utilizó menos recientemente que hay que

reemplazarla.

8 2 3 4


• La décima referencia (1), se encuentra en memoria, no tenemos fallos de

página.

Ponerlo en la práctica es difícil, ya que el sistema debe contabilizar de alguna

forma, el tiempo que se produce cada referencia a memoria para poder

clasificar las páginas según su uso.

5.3.5. Reloj

Un puntero va recorriendo los distintos marcos de página, se asocia a cada

marco un bit adicional, llamado bit en uso ( 0 o 1). Cuando se introduce una

página el bit en uso se pone en 0 (R = 0).

Cuando se accede a una página que esta en memoria no se avanza

puntero y Considerar:

Si R = 0 entonces se cambia a 1( R=1)

Si R = 1 entonces queda igual ( R = 1)


75


• Si se produce un fallo de página se analiza el R al que apunta el puntero

Si R =0, se reemplaza la página y avanza una posición el puntero

Si R = 1, se cambia a R=0 y se avanza el puntero hasta encontrar R = 0


número te fallos de página cuando m=3

Como funciona reloj:

Inicialmente la memoria está vacía

La primera referencia (8), es fallo de página y se coloca 80, en la

primera celda y avanza puntero a la siguiente celda.

La segunda referencia (1), es fallo de página y se coloca 10, en la

segunda celda y avanza puntero a la siguiente celda.

La tercera referencia (2), es fallo de página y se coloca 20, en la tercera

celda y avanza puntero a la siguiente celda, como puntero llego al final,

se ubica en la primera celda.

La cuarta referencia (3), es fallo de página, se analiza el R al que apunta

el puntero, como R =0, se reemplaza la página y avanza el puntero.

La página que sale es 8 y entra la página 3.

La Quinta referencia (1), esta en memoria, no se avanza puntero, y

considerar:

Si R=0, se cambia a 1 (R=1).

La sexta referencia (4), es fallo de página, se analiza el R al que apunta

el puntero, como R =1, se cambia a R=0, y avanza puntero y ahora el

R=0, entonces la página 4 reemplaza a la página 2.


76


La séptima referencia (1), se encuentra en memoria, no se avanza

puntero y considerar:

Si R=0, se cambia a 1 (R=1).

La octava referencia (5), es fallo de página, se analiza el R, al que

apunta el puntero, como R=0, se reemplaza la página y avanza

puntero. La página que sale es 3 y entra la página 5.

La novena referencia (3), es fallo de página, se analiza el R al que

apunta el puntero, como R = 1, se cambia R = 0, y se avanza puntero

y ahora R= 0, entonces la página que sale es 4 y entra la página 3.

La décima referencia (1), se encuentra en memoria, no se avanza

puntero y como R=0, se cambia a 1 (R=1).

5.3.6. Algoritmo de Pila

Otra forma de implementar el LRU, consiste en mantener una pila de número

de página.

En la parte superior de la pila esta siempre la página utilizada más

recientemente y en la parte inferior la página utilizada menos recientemente.

5.3.6.1 Distancia de la cadena

Se determina por la posición en que se encuentra una referencia en la fila

anterior Si una referencia no se encuentra se pone infinito.

5.3.6.2 Predicción de la tasa de fallos de página

Una de las propiedades de la distancia de la cadena es su utilidad para

predecir el número de fallos de página que se podrían ocurrir con

memoria de tamaños diversos.

El algoritmo analiza la distancia de la cadena, página a página, lleva un

registro:

El número de veces que aparece el 1

El número de veces que aparece el 2, etc.

Sea:

Ci el número de ocurrencias de i

Calculemos el vector F según la fórmula:


77


Donde:

FM = Número de fallos de página que aparecen con M celdas

C¥ = Número de veces que aparece en la distancia de la cadena.


número te fallos de página cuando m=4.

Se pone cuatro parcos en la memoria principal y 4 en memoria secundaria.


78


Dispositivos de entrada y salida y planificación del disco

Sumario

La unidad tiene como propósito que el estudiante identifique y comprenda el

funcionamiento de los periféricos y planificación del disco, valorando la

relevancia que tiene la programación estructurada y modular. Contiene:

Dispositivos de entrada / salida

Planificación del disco.

Dispositivos de entrada E/S y planificación de discos

Cuando hablamos de entradas y salidas nos referimos a las diferentes señales

de comunicación que son recibidas y enviadas por unidades funcionales de un

sistema de procesamiento de datos informáticos. Estas señales E/S son

utilizadas por diferentes interfaces para establecer la comunicación y pasarse

argumentos entre sí. Son utilizados por los diferentes periféricos para enviar y

recibir datos desde/hacia la CPU.

Los procesos de entrada/salida han evolucionado a lo largo del tiempo,

inicialmente la CPU (microprocesador) controlaba directamente los dispositivos

periféricos y con ello todo el proceso de entrada/salida, más adelante se añade

una controladora de dispositivo de E/S, con lo cual la CPU utiliza E/S

programada según la controladora,

a partir de este desarrollo se incorporan interrupciones y más adelante la

controladora de E/S recibe el control directo del DMA (Acceso Directo a

Memoria), se transfieren datos hacia/desde la memoria sin usar CPU. Las

nuevas arquitecturas incorporan un procesador separado con un conjunto de

instrucciones especializadas para E/S. La CPU central le ordena al procesador

de E/S la ejecución de un programa de E/S en la memoria principal, hoy en día

podemos encontrar controladoras de E/S que poseen su propia memoria local

funcionando como un computador independiente.

6.1. Dispositivos de entrada/salida

Un dispositivo de entrada/salida es utilizado por personas y diversos sistemas

informáticos entre Hardware y Software. Los dispositivos de E/S se pueden

agrupar clasificar en:


79


Dispositivos de interfaz de usuario. Estos dispositivos permiten la

comunicación entre los usuarios y la PC. en este grupo se incluyen

todos los dispositivos que sirven para proporcionar comunicación

efectiva con el usuario, tanto para entrada de datos (ratón, teclado, etc.)

como para salida (impresoras, pantalla, etc.), del mismo modo existen

dispositivos más complejos que permiten la entrada y salida de datos a

la vez, tales como un escaner, lectores de huella digital, lectores de cinta

magnética, instrumentos musicales digitales, etc.

Dispositivos de almacenamiento. Se usan para proporcionar

almacenamiento no volátil de datos y memoria. Su función primordial es

abastecer de datos y almacenamiento a los programas que se ejecutan

en la CPU.

Dispositivos de comunicaciones o red. Permiten conectar a la PC con

otras computadoras a través de una red. Los dos tipos de dispositivos

más importantes de esta clase son los modem, para comunicación vía

red telefónica, y las tarjetas de interfaz a la red, para conectar la

computadora a una red de área local (LAN).

Un computador no está formado solo por la CPU y la memoria principal, la

funcionalidad de una PC se obtiene de la comunicación con el mundo exterior.

Esto se realiza a través del subsistema de entrada/salida (módulos de E/S). La

misión principal de este subsistema es la adaptación de los dispositivos

externos para su conexión al bus del sistema. Estos dispositivos por lo general

utilizan velocidades de transmisión de datos menores al de la memoria y la

CPU, por lo cual es necesario amortiguar esa diferencia de velocidades a

través del subsistema de e/s. La imagen siguiente muestra una estadística de

velocidades de los dispositivos más utilizados.

Por lo general la gran variedad de periféricos existentes no hacen posible

incorporar todos los programas necesarios para controlar la diversidad de

dispositivos dentro del procesador, los formatos y tamaños de datos de los

periféricos en su mayoría son diferentes a los utilizados por el computador a los

que se conectan, por lo cual se hace necesario realizar una instalación

adicional de los controladores a utilizar (Drivers).


80


Una de las funciones principales de un Sistema Operativo es el control de

todos los dispositivos de E/S de la computadora. El sistema operativo debe

controlar el funcionamiento de todos los dispositivos de para alcanzar los

siguientes objetivos:

Facilitar el manejo de los dispositivos de E/S, ofreciendo una interfaz

entre los dispositivos y el resto del sistema que sea sencilla y fácil de

utilizar.

Proporcionar dispositivos virtuales que permitan conectar cualquier tipo

de dispositivo físico sin que sea necesario modificar el sistema de E/S

del Sistema Operativo.

Permitir la conexión de nuevos dispositivos de E/S, reconociendo de

forma automática su instalación (plug&play).


81


6.2. Dispositivos externos

Elementos que permiten la transferencia de información entre la CPU y el

mundo exterior. Funcionan a modo de interface transformando la información

asíncrona y analógica del mundo exterior a la información síncrona y codificada

del computador (señal digital)

6.3. Módulo de e/s (controladora)

Elemento que permiten la conexión de un dispositivo externo al bus del

sistema.

Los términos “controlador”, “procesador de E/S” y “módulo de E/S” son

equivalentes desde el punto de vista funcional, los controladores son módulos

de E/S muy sencillos que tienen el hardware necesario para que funcione el

dispositivo externo. Los procesadores de E/S son auténticos procesadores con

un juego especializado de instrucciones orientado a operaciones de E/S, que

son programados por la CPU, permitiendo un funcionamiento autónomo. Un

dispositivo externo conectado a un módulo de E/S se denomina dispositivo

periférico o simplemente periférico. En resumen el módulo de E/S realiza la

interfaz entre el procesador y la memoria y realiza la interfaz entre uno o más

periféricos. Módulo de E/S


82


6.4. Funciones de los módulos de e/s.

Entre las principales funciones de los módulos de entrada y salida, se puede

mencionar:

6.4.1. Control y temporización.

Esta función es necesaria para coordinar el tráfico entre dispositivos internos

y externos, a modo de ejemplo podemos describir el control de la transferencia

de datos desde un dispositivo externo al procesador con la siguiente secuencia

de pasos:

P1. El procesador pregunta por el estado del dispositivo

P2. El módulo de E/S devuelve el estado del dispositivo

P3. Si el dispositivo está listo, el procesador solicita la transferencia al módulo

de E/S

P4. El módulo de E/S obtiene los datos

P5. Los datos se transfieren del módulo de E/S al procesador

6.4.2. Comunicación con el procesador

Esta función involucra que se realicen operaciones de decodificación de

órdenes, decodificación de datos, la emisión de señales de información de

estado de los procesos y reconocimiento de direcciones.

6.4.3. Comunicación con los dispositivos

Se permite el paso de ordenes (señales de ejecución desde y hacia un

dispositivo), se emiten señales de información de estado y señales de datos

que viajan desde y hacia un dispositivo.

6.4.4. Almacenamiento temporal

Los módulos de E/S almacenan en memorias temporales (Buffer), los datos

que entran a la CPU, salen a los diferentes dispositivos y viceversa. Estos

datos se envían en ráfagas rápidas desde la memoria al módulo de E/S y

después se envían al periférico a la velocidad de éste (de igual modo el

proceso inverso), del mismo modo los datos se almacenan para no mantener

ocupada a la memoria en una operación de transferencia lenta (evitar una

caída en el rendimiento)


83


6.4.5. Detección de errores

Los diferentes módulos de E/S, manejan señales que describen errores

debidos a defectos mecánicos o eléctricos y errores en la transmisión de

información, para lo cual hacen uso de códigos de detección de errores.

6.5. Técnicas para entrada/salida

6.5.1. E/S programada

En esta técnica la CPU tiene el control absoluto de la operación de E/S, se

encarga de iniciar y llevar a cabo la transferencia de datos desde y hacia la

CPU con los dispositivos del sistema, en esta técnica la CPU se dedica por

completo a realizar la estas operaciones, realiza la comprobación de estado

como la transferencia y la inicialización, aunque el hardware a utilizar en

mínimo, es considerado poco eficiente ya que el procesador debe atender

operaciones de E/S y operaciones de usuario en secuencia, llegándose a

obtener baja performance en la mayoría de los casos.

6.5.2. E/S dirigida por interrupciones

Esta técnica hace uso de una línea especial (bus) conectada a la CPU y al

módulo de E/S, de tal manera que el controlador le indica a la CPU cuando

esta preparada para transferir datos (se genera una interrupción a la CPU), con

la cual se activa la línea de interrupción. El funcionamiento puede ser descrito

de la siguiente forma:

El procesador ejecuta instrucciones de un programa. Al finalizar cada

instrucción comprueba si se ha producido una interrupción.

En caso afirmativo se guarda el estado actual del programa (contador

del programa y registros) y se salta a ejecutar la rutina de servicio

correspondiente.

La rutina de servicio efectúa las operaciones apropiadas en la E/S para

realizar la transferencia de datos solicitada.

Al finalizar la rutina de servicio se recupera el estado de la CPU y se

continua ejecutando el programa que se estaba ejecutando antes de la

interrupción.

Se emite una orden de E/S.


84


El procesador continua con la ejecución de las instrucciones.

El módulo de E/S lo interrumpe cuando completa su trabajo.

6.5.3. Acceso directo a la memoria (dma):

Para esta técnica un módulo de DMA controla el intercambio de datos entre la

memoria principal y el dispositivo de E/S, para este fin se transfiere un bloque

de datos directamente hacia/desde la memoria enviándose una interrupción

cuando los datos fueron transferidos, en este proceso la CPU solo participa al

inicio y al final de la acción por lo cual libera de carga de trabajo a la CPU.

Las razones por las cuales las computadoras utilizan modelos de

entrada/salida se deben a que la mayoría de los dispositivos son muy lentos en

comparación con la memoria y la CPU, por esta razón se usa

multiprogramación para aprovechar los tiempos de espera y se realizan

intercambios para introducir más procesos listos para la ejecución , estas

técnicas buscan mejorar la eficiencia en el desempeño total de la computadora,

sin embargo se debe mencionar que el área que ha recibido más atención en

este tema es el disco duro, ya que su rapidez no ha evolucionado de la misma

manera que la velocidad de las CPUs y las memorias principales.

Otro punto a tomar en cuenta es la Gestión de dispositivos, se requiere que

todos sean Gestionados uniformemente con rutinas de bajo nivel, de tal

manera que los procesos contemplen los dispositivos en términos de funciones

generales (leer, escribir, abrir, cerrar, etc.)


85


Discos y planificación de disco

Los dispositivos de almacenamiento es importante en los sistemas operativos

actuales y probablemente seguirá siendo durante algunas décadas.

7.1. Discos duros

Físicamente constituidos por varios platos giratorios, unidos por un eje común,

que gira a una velocidad de 360 r.p.m si es diskette y si es disco duro gira a

1500 r.m.p o más. Sobre cada plato existe una cabeza de lectura-escritura,

cuyo conjunto esta unido por un eje móvil denominado brazo.

El brazo se mueve a fin de acercar o alejar las cabezas del centro de los platos

hacia el borde. Cada plato está dividido en pistas concéntricas. El conjunto de

pistas a la misma altura en cada plato se denomina cilindro.

Cada pista esta subdividida a su vez en sectores y cada sector tiene un bloque

de información. Todas las pistas contienen el mismo número de sectores, este

número suele ser entre 8 y 32.


86


Para obtener acceso a un sector de datos en un disco de cabeza móvil es

necesario realizar tres operaciones:

· Tiempo de búsqueda: Tiempo necesario para mover el brazo hasta el cilindro

buscado.

· Tiempo de latencia o Retraso Rotacional: Tiempo necesario para que el

sector adecuado rote debajo del cabezal.

· Tiempo real de transferencia: Tiempo que tarda en realizarse la transferencia

de todos los bytes contenidos en el sector.

7.1.1. Capacidad de un disco

Tendremos que averiguar cuantos sectores tiene el disco y despues multiplicar

la cifra obtenida por el tamaño del sector. Asi:

número. sectores = número. caras * número. cilindros * sectores / pista


87


tamaño del disco = número.sectores * tamaño del sector

Ejemplo:

Dada una estructura de disco de doble cara con 80 cilindros y 18 sectores por

pista y un tamaño de sector de 512 bytes. Se pide determinar la capacidad del

disco.

Solución:


2 * 80 * 18 = 2880 bytes

La capacidad del disco en Kb sera:

2880 * 512 bytes * kb /1024 bytes = 1440 Kb

1kb = 1024 bytes

Capacidad de un diskette de 5 . (formato antiguo no utilizado en la actualidad)


2 * 40 * 8 = 640 bytes


640 * 512 bytes * kb /1024 bytes = 320 Kb

Capacidad de un diskette de 3 . (formato aun utilizado en algunos sistemas)


2 * 80 * 9 = 1440 bytes


1440 * 512 bytes * kb /1024 bytes = 720 Kb

7.1.2. Correspondencia entre sectores físicos y lógicos de un disco.

A. Dada la correspondencia entre sectores físicos y lógicos, se trata de

determinar la dirección física del número de sector lógico 1230.

B. De forma análoga se desea determinar cual es el número de sector lógico

asociado a la dirección física (34, 0, 6).

Solución:

Las direcciones físicas tienen la siguiente estructura: (número. Cilindro,

número. Cara, número. Sector)

Para obtener la dirección física hacemos lo siguiente:

Calculo del número de caras y número de sector:

número.cara= DL div sector/pista = 1230 Div 18 = 68

número.sector = DL Mod sector/pista= 1230 Mod 18 = 6


88


· Esto quiere decir que con la dirección lógica 1230 se han podido “llenar” 68

caras y se está referenciando el séptimo sector (ya que empezamos a

numerarlos a partir de cero) de la sexagésima novena cara.

Calculo del número de cilindro y número de caras:

número.cilindro= número.caras div número.caras/cilindro

número.caras = número.caras Mod número.caras/cilindro

68 div 2 = 34

68 mod 2 = 0

· Esto se interpreta como que hemos podido “completar” 34 cilindros y estamos

en la primera cara del trigésimo quinto cilindro.

Por tanto, la dirección física pedida es: (34, 0, 6 )

Es decir, cilindro 34, cara 0, sector 6.

Dirección lógica para la dirección física (34, 0, 6).

Suponiendo direcciónes físicas de la forma (i, j, k), basta con aplicar la formula:

nb = k + sector/pista*(j+caras/cilindro*i) = 6 + 18*(0+2*34) = 6+ 18*(68) =6+

1224 = 1230

El número de bloque lógico es: 1230

Donde:

nb= número de bloque lógico

7.2. Algoritmos de planificación de discos

En los sistemas de computación multiprogramados, se encuentran varios

procesos en ejecución los cuales pueden estar generando peticiones

simultaneas de acceso de lectura o escritura de registros en discos, si mientras

se realiza un acceso de lectura o escritura llegan más peticiones, el disco debe

de mantenerlas en una cola de espera.

La planificación de disco se encarga de atender las peticiones pendientes,

buscando minimizar el desplazamiento del brazo del disco y por tanto el tiempo

de servicio de la petición.

Algunos algoritmos que se pueden utilizar para planificar dicha petición son:

FCFS, SSTF, SCAN, C-SCAN.


89


7.2.1. Primero en llegar, primero en ser servido (FCFS, first come first

served)

o Se sirven las solicitudes en el orden en que llegan, es decir primera solicitud

que llega, es la primera que se atiende.

o Al llegar una petición su lugar en la cola es fijo, de acuerdo al orden de

llegada.

o Es justa, una petición no puede ser desplazada por la llegada de otra de

mayor prioridad o aunque llegue una petición para el mismo cilindro donde está

localizado la cabeza de lectura- escritura.

o Es aceptable cuando la carga del disco es ligera, cuando la carga es pesada,

aumenta los tiempos de respuesta, ya que el brazo del disco se mueve muy

ineficientemente, ya que las peticiones pueden tener direcciónes en el disco

muy alejadas de otras.

Ejemplo, si se esta haciendo peticiones sobre los sectores de las pistas

(cilindro):

Q= 1, 36, 17, 34, 10 y 13

La cabeza de Lectura-escritura se encuentra en la pista 12.

Solución:

La forma de resolver es colocar en una recta numérica las pistas, comenzamos

en la pista 12, que es la cabeza de lectura-escritura, se moverá 11 pistas hacia

la 1, que es la primera pista en llegar, luego se moverá 35 pistas hacia la 36,

que es la segunda pista en llegar, y así sucesivamente como se muestra en la

figura 1. La cabeza se moverá 109 pistas


90


Explicación:

Cilindro actual 12, cilindro a servir 1 (el primero de la cola), su diferencia

12-1 =11

Cilindro actual 1, cilindro a servir 36 ( el segundo de la cola), su diferencia

1 - 36 = 35 (valor absoluto)

Y asi sucesivamente se va calculando los siguientes desplazamientos.

Otra forma de resolver:

o Colocar en cada paso el cilindro actual, el cilindro a servir y el

desplazamiento. El desplazamiento se calcula con la diferencia en valor

absoluto, entre cilindro actual y el cilindro a servir, como se muestra en la tabla

7.2.2. Primero el más cercano a la posición actual (SSTF, shortest seek

time first)

o El brazo del disco se mueve en cualquier dirección a la petición que requiere

un movimiento mínimo.

o Es un algoritmo muy eficaz, pero la forma de atender las peticiones pueden

postergar indefinidamente algunas de ellas (inanicion).

o Supongamos que entre dos peticiones que se encuentra en la cola 40 y 68 y

que se acaba de atender a la 40, se apresta atender a la 68, pero en el preciso

instante llega una peticion a la 48, que se atiende de inmediato, luego llega

más peticiones cercanas a la ultima peticion, el sistema atendera las nuevas

aplazando el servicio a la peticion 68.

o Cuando hay carga fuerte de trabajo, tienden a haber solicitudes de todos los

cilindros, lo que llevara que en promedio el brazo permanezca en el centro del

disco. Esto origina que las solicitudes de los extremos no sean atendidas hasta

que la carga disminuya.


91



(cilindro):

Q= 1, 36, 17, 34, 10 y 13


Solución:

La forma de resolver es colocar en una recta numérica las pistas El

desplazamiento se calcula mediante la diferencia menor en valor absoluto de

dos pistas más cercano al cilindro actual. El desplazamiento nos indica la

dirección a seguir, como nos muestra la figura . La cabeza se moverá 62 pistas.

Explicación:

Calculamos entre las pistas 10 y 13, cual es la más cercana al cilindro actual

(12).

12 – 10 = 2

12 - 13 = 1 (valor absoluto)

Escogemos la distancia menor que es 1, entonces el sstf se mueve hacia la

derecha, y así se va buscando la diferencia menor entre dos pistas más

cercanas al cilindro actual.


o Colocar el cilindro actual, en los cilindros a servir colocar asterisco en el

cilindro actual, el desplazamiento se calcula mediante la diferencia en valor

absoluto entre el cilindro actual, y las pistas más cercanas al cilindro actual,

escogiendo la diferencia minima.

Por ejemplo en la primera línea del siguiente cuadro, el cilindro actual es 12, y

en los cilindros a servir colocar * en lugar de 12, el desplazamiento calculamos


92


entre las pistas 10 y 13, cual es la más cercana al cilindro actual (12),

escogemos la distancia menor.

12-13= 1 (valor absoluto)

12-10= 2

Entonces la diferencia menor es 1, entonces el movimiento es hacia la derecha.

o En cada paso no considerar el cilindro servido

o Repetir los pasos 1 y 2, hasta dar servicio a todas las pistas, como nos

muestra la tabla.

7.2.3. Exploración (algoritmo del ascensor - scan)

o El brazo del disco se mueve de un extremo al otro extremo del disco,

atendiendo todas las peticiones que van en ese sentido, cambia de dirección

solo cuando no hay más peticiones que atender en la dirección actual, al volver

se sirven todas del sentido contrario.

o También se le conoce con el nombre del algoritmo del ascensor, por que un

ascensor continua en una dirección hasta que no haya más solicitudes

pendientes y después cambia de dirección.

o Su desventaja es que no es justo, ya que no sirve las peticiones en el orden

que llegaron, además de que las peticiones en los extremos interior y exterior

tendrán un tiempo de respuesta un poco mayor.

Si no nos dicen su dirección aplicaremos SSTF


(cilindro):

Q= 1, 36, 17, 34, 10 y 13


93



Solución:

La forma de resolver es colocar en una recta numérica las pistas, Como no nos

dan la dirección de movimiento aplicamos sstf, y el movimiento es hacia la

derecha, entonces nos movemos hacia el otro extremo atendiendo las

solicitudes que encuentra a su paso al volver se atiende las solicitudes que

faltan, como se muestra en la figura . La cabeza se moverá 59 pistas.

Total movimiento = 1+ 4+ 17+ 2+ 26 + 9 = 59 pistas

Explicación:

Empezamos por las pista 12, que es la cabeza de lectura-escritura y le damos

servicio a las pistas 13, 17, 34 y 36 calculando sus desplazamientos, como

hemos llegado al extremo, regresamos al otro extremo atendiendo a las pistas

que falta 10 y 1. No se atiende a la pista 12, ya que se le dio servicio.


Colocar la dirección del cilindro, los cilindros por servir y el

desplazamiento.

El desplazamiento cuando la dirección del cilindro es ascendentemente se

calcula mediante la diferencia del último cilindro por servir con la cabeza de

lectura-escritura.

El desplazamiento cuando la dirección del cilindro es descendentemente se

calcula mediante la diferencia del ultimo cilindro por servir y el primer cilindro de

la recta numérica, como se muestra en la tabla 6.4.


94


7.2.4. Exploración circular (c- scan)

Es una variación del algoritmo anterior, con la única diferencia que al

llegar a un extremo, el brazo del disco regresa al otro extremo sin

atender ninguna petición y luego reinicia su barrido hacia adentro

procesando solicitudes.

La ventaja es que se elimina la discriminación de las estrategias

anteriores contra los cilindros más interiores y exteriores.


(cilindro):

Q= 1, 36, 17, 34, 10 y 13


Solución:

La forma de resolver es colocar en una recta numérica las pistas, el movimiento

es igual que el SCAN, hacia la derecha, entonces nos movemos hacia el otro

extremo atendiendo las solicitudes que encuentra a su paso al volver se

regresa al otro extremo, sin atender ninguna petición, luego reinicia su barrido

hacia adentro procesando las solicitudes que falta, como se muestra en la

figura. La cabeza se moverá 34 pistas.

Explicación:

Empezamos por la pista 12, que es la cabeza de lectura-escritura y le damos

servicio a las pistas 13, 17, 34 y 36 calculando sus desplazamientos, como

hemos llegado al extremo, regresamos al otro extremo sin atender ninguna

petición, entonces su desplazamiento es cero, luego reinicia su barrido hacia

adentro, atendiendo a las pistas que falta 1 y 10. No se atiende a la pista 12, ya

que se le dio servicio.


95



Colocar ascendentemente, los cilindros por servir y el desplazamiento se

calcula mediante la diferencia del último cilindro por servir con la cabeza

de lectura escritura.

Colocar descendente la dirección del ultimo cilindro por servir con el

sector cero, no realiza ningún desplazamiento por lo tanto el

desplazamiento es cero.

Colocar ascendentemente, los cilindros que faltan servir y el

desplazamiento se calcula mediante la diferencia de la pista anterior a la

lectura-escritura inicial con el cilindro cero (cero). Como se muestra en la

tabla.

La tabla 6.6 nos muestra un consolidado de los diferentes métodos de

planificación de disco

El algoritmo c-scan es el más utilizado actualmente. Se usa en todas en UNIX,

LINUX y WINDOWS, debido a que da el mejor rendimiento a sistemas muy

cargados.


96


Gestión de archivos

Sumario

La unidad tiene como propósito que el estudiante identifique y comprende el

funcionamiento de la Gestión de archivos, evalúa y aplica con precisión y

eficiencia los métodos de acceso a archivos, valorando la relevancia de estos

conocimientos y algoritmos para su desarrollo académico y profesional.

Contiene:

Archivos, operaciones

Directorios

Métodos de acceso

Gestión de archivos

La Gestión de archivos se encarga principalmente de la administrar el espacio

de almacenamiento secundario, sobre todo el espacio en el disco. (Deitel,

1990) Los programadores han usado archivos para guardar la información en

los dispositivos de almacenamiento desde los primeros días de la informática.

(Gary nutt, 2004).

8.1 Gestión de archivos

La Gestión de archivo es un componente importante de cualquier sistema

operativo,

que implementa la abstracción de archivos, directorios para organizar archivos,

la asignación de espacio de almacenamiento.

8.2 Archivos

Los archivos permiten el almacenamiento de la información, con la finalidad de

poder leerla y escribirla en el tiempo.

El sistema operativo permite asignar un nombre a un archivo en el momento de

su creación y debe de tener nombre único, cada sistema operativo define sus

propias reglas:.

Caracteres que son válidos y caracteres que no


97


Longitud de los nombres puede ser variable. Por ejemplo ms_dos utiliza

8 caracteres como máximo, unix y GNU/Linux utiliza 4096 caracteres

como máximo para nombrar a los archivos.

Distinción entre mayúsculas y minúsculas. El ms-dos si hace distinción

entre mayúsculas y minúsculas, mientras que unix y GNU/Linux, no hace

distinción.

Por ejemplo ALUMNOS y alumnos para el ms-dos es el mismo archivo,

mientras que para el unix y GNU/Linux son dos archivos diferentes.

Nombres reservados o especiales.

Manejo de extensiones como parte del nombre. En ms-dos un archivo

solo puede tener una extensión y debe de tener como máximo tres

letras. En GNU/Linux y Windows, un archivo puede tener cualquier

número de extensiones y de cualquier tamaño.

Ejemplos

device.map

e2fs_stage1_5

grub.conf

jfs_stage1_5

menu.lst

splash.xpm.gz

8.2.1 Estructura de un archivo.

Cualquier programa de aplicación lee información de uno o más archivos,

procesa los datos y escribe el resultado en uno o más archivos, las

aplicaciones operan sobre los datos, se apoyan en la estructura de un archivo.

La estructura de un archivo indica cómo se organiza la información en su

interior:

Serie no estructurada de bytes: El Sistema Operativo no maneja en

realidad ninguna estructura al interior del archivo; todos son bytes

adyacentes.

Registros de longitud Fija o Bloques: El Sistema Operativo lee y

escribe siempre los archivos en unidades llamadas registros.


98


Árbol de registros: Conjunto de registros de diferente longitud,

organizados en forma de árbol ordenado por una llave (key). Permite

búsquedas rápidas.

8.2.2 Tipos de acceso archivo

El tipo de acceso a un archivo puede ser secuencial o aleatorio.

Acceso Secuencial:

Los datos se almacenan de forma consecutiva y no es posible leer un registro

directamente, es decir para leer el registro n hay que leer los n-1 registros

anteriores.

Los archivos secuenciales se utilizan con mayor frecuencia en aplicaciones de

procesos en lotes.

El acceso secuencial es más antiguo ya que proviene de la limitación de las

cintas magnéticas.

Acceso Aleatorio:

Permite una mayor rapidez de acceso, al leer o escribir un registro concreto, sin

necesidad de leer todos los registros anteriores. Los archivos de acceso directo

permiten operaciones tanto de lectura o escritura a cualquier parte del archivo

en cualquier momento. En C++ la forma de hacer posible el acceso directo es

usando la función seek para situarnos en cualquier punto del archivo y poder

efectuar una operación de lectura o escritura.

El proceso puede leer los registros en cualquier orden utilizando dos métodos

para determinar el punto de inicio de la lectura:

• read da la posición en el archivo con la cual iniciar.

• seek establece la posición de trabajo pudiendo luego leerse el archivo

secuencialmente.

Modelan adecuadamente discos duros.

El acceso aleatorio es más flexible, imprescindible hoy en día para muchísimas

aplicaciones.

Los sistemas operativos, hoy en día brindan acceso aleatorio, el cual permite

un acceso secuencial sin ningún problema.


99


8.2.3 Atributos de archivos

Junto con el nombre de cada archivo, es necesario registrar cierta información

adicional:

Fecha y hora de creación.

Usuarios con acceso a los archivos y tipo de acceso permitido para

ellos.

Tamaño actual.

Fecha y hora del último acceso.

Si se requiere hacerle un backup.

Si es ejecutable.

8.2.4 Operaciones con archivos

El sistema operativo se puede manipular como una unidad, proporcionando

servicios para crear, modificar, abrir, etc. archivos. Mencionaremos algunos

servicios:

Crear: El archivo se crea sin datos.

Eliminar: Eliminación un archivo con todo su contenido.

Abrir: Un archivo debe de abrirse antes de usarse para hacer referencias

a el.

Cerrar: Cuando un archivo ya no se utiliza debe de cerrarse para evitar

cualquier otra referencia al archivo en tanto no se le abra otra vez.

Copiar: Se crea otra version del archivo con un nuevo nombre.

Renombrar: Cambia el nombre de un archivo.

Los elementos individuales de la información dentro de un archivo se

pueden manipular con operaciones tales como:

Leer: Lee datos de un archivo, desde la posición actual.

Escribir: Transfiere información de un proceso a un archivo. El tamaño

del archivo puede aumentar (agregado de registros) o no (actualización

de registros).

Buscar: Cambia la posición actual, en un archivo de acceso aleatorio, a

la indicada. Las siguientes lecturas o escrituras usaran la nueva posición

como punto de partida.

Eliminar: Elimina un elemento de información de un archivo.


100


Modificar: altera un elemento de información ya existente de un archivo.

8.3 Directorio

Los archivos se organizan en directorios, un directorio es un conjunto de

archivos y otros sub-directorios asociados lógicamente. El gestor de archivos

proporciona a los usuarios un conjunto de operaciones para administrar un

directorio, como crear, eliminar, abrir, etc.

8.3.1 Operaciones con directorios

Crear: Se crea un directorio vacío.

Copiar: Crea un duplicado de un directorio existente.

Eliminar: Elimina un directorio que este vacio.

Renombrar: Cambia el nombre de un directorio.

8.3.2 Organización de directorios

Los directorios se organizan de la siguiente manera:

Directorio único: Si existen muchos usuarios y estos eligen los mismos

nombres de archivos, los conflictos y confusiones pronto harán que el

sistema no pueda funcionar.

Un directorio por usuario: El sistema habilita un solo directorio por

usuario.

Diferentes usuarios pueden tener archivos con igual nombre.

Un árbol de directorio por usuario: El sistema permite que cada usuario

tenga tantos directorios como necesite, respectando una jerarquía

general.


101


8.3.3 Rutas de acceso

Para las organizaciones tipo árbol, se utilizan:

8.3.3.1 Referencias Absolutas

Consta de la ruta de acceso desde el directorio raíz hasta el archivo.

Los componentes de la ruta de acceso se separan mediante algún carácter

llamado “separador”.

En Linux se utiliza el carácter /, el directorio raíz del cual cuelgan todos los

archivos y directorios

8.3.3.2 Referencias Relativas

Se utiliza junto con el concepto de directorio de trabajo o directorio activo. Se

especifica la ruta de acceso a partir de este punto.


102


El archivo carta.txt se encuentra en /home/luis

La ruta absoluta hacia carta.txt /home/luis/carta.txt

El archivo carta.txt se encuentra en /home/luis

Si nos encontramos en /home

La ruta relativa hacia carta.txt luis/carta.txt

Una ruta es absoluta si el primer carácter es un /, sino es relativo

8.4 Asignación del espacio de almacenamiento

Los archivos, como colección de datos al almacenarse en el sistema de

archivos se organizan como colecciones de bloques. Las diferentes formas de

estas organizaciones dan lugar a los siguientes esquemas:

– Asignación contigua o adyacente

– Asignación enlazada

– Asignación enlazada con índice

– Nodos-i

8.4.1 Asignación contigua o adyacente

Todos los bloques que constituyen el archivo se ubican en forma adyacente en

el disco.

El directorio contiene los nombres de los archivos, la dirección del bloque inicial

y el número de bloques que ocupa.

Es necesario declarar el tamaño del archivo al momento de su creación, los

usuarios muchas veces hacen una estimación excesiva en el tamaño de los

archivos, ocasionando una pérdida de espacio en el disco.


103


La implementación sencilla, para cada archivo se registra la dirección del inicio

del bloque y la longitud del bloque.

El tiempo de acceso muy rápido para transferencias completas de archivos, se

lee en una sola operación, puesto que todos los bloques están contiguos en el

disco.

Se produce fragmentación externa del disco, haciendo difícil encontrar bloques

contiguos de espacio de tamaño suficiente, aunque se puede compactar el

disco para eliminar la fragmentación.

Por ejemplo, si el disco maneja unidades de almacenamiento de 1K, un archivo

de 30 K tendrá asignados 30 bloques consecutivos.

8.4.2 Asignación enlazada

La lista enlazada de bloques usa apuntadores entre un conjunto de bloques

físicos que componen el archivo. Cada bloque contendrá un puntero al

siguiente bloque de la cadena. Los bloques pueden estar ubicados en cualquier

parte del disco.

El directorio contiene los nombres de los archivos, la dirección del bloque inicial

y el número de bloques que ocupa (longitud del archivo).

El tamaño del archivo varia en forma dinámica, se asigna bloques a medida

que crece el archivo, si el archivo decrece libera sus bloques sobrantes y otro

archivo puede utilizarlo al incorporarlo en su lista enlazada.

Los bloques que componen el archivo tiene dos partes: un apuntador al

siguiente bloque y un bloque de datos

Por ejemplo, el archivo A de seis bloques que empieza con el bloque 24 puede

continuar con el bloque 2, luego con el 7, 15, 17 y 19. Cada bloque contiene un

puntero al bloque siguiente.


104


Se puede obtener toda la secuencia de bloques conociendo solo el puntero al

primer bloque del archivo.

Uso efectivo para archivos secuenciales. Para buscar un bloque de un archivo,

tenemos que recorrer la lista desde el principio del archivo hasta encontrar el

bloque, de aquí que no podamos soportar el acceso directo a archivos con

asignación enlazada.

Elimina la fragmentación externa, porque solo se necesita un bloque a la vez.


105


8.4.3 Asignación enlazada con índice

Consiste en utilizar el esquema anterior, pero manteniendo los punteros que

forman la lista enlazada en una estructura aparte de los bloques. Esta es una

tabla o índice, que se mantiene en memoria principal.

El directorio del usuario contiene el nombre del archivo y el bloque de inicio.

Cada entrada en la tabla contiene el número de bloque del siguiente bloque del

archivo, así es posible localizar todos los bloques de un archivo siguiendo las

entradas en la tabla. Un valor NULL en la tabla, determina la última entrada de

un archivo.

La asignación enlazada con índice soporta tanto el acceso secuencial como el

acceso directo a los archivos Dado que el índice es una estructura aparte, su

acceso es más sencillo. Todo el índice está contenido en memoria, por tanto,

es posible seguir la cadena que forma el archivo sin tener que realizar accesos

adicionales al disco.

El tener toda la tabla en memoria para discos de gran tamaño, puede consumir

cantidad considerable de dicha memoria.


106


8.4.4 Nodos-i

Consiste en asociar a cada archivo una pequeña tabla, denominada nodo-i

(nodo índice), que contiene información clave de un archivo necesaria para el

sistema operativo.

Se usa asignación enlazada con índice para seguir la pista de cada archivo,

con parte del índice almacenada en el nodo-i del archivo.

En unix, cada nodo tiene 13 apuntadores, los 10 primeros apuntadores apuntan

directamente a los 10 primeros bloques de datos del archivo, si el archivo es

mayor de 10 bloques la dirección undécima del nodo-i apunta a un bloque

indirecto simple, si el archivo contiene más bloques, la dirección duodécima del

nodo-i apunta bloques indirectos dobles, si el archivo contiene aún más

bloques, la dirección decimotercera del nodo-i apunta a un bloque indirecto

triple.

En unix la longitud de un bloque es de 1Kb y cada bloque puede albergar un

total de 256 direcciones de bloques, por lo tanto, el tamaño máximo de un

archivo usando este esquema se aproxima a los 16 Gbytes.

1Kb = 1024 bytes

1Mb= 1024 Kb

1Gb = 1024 Mb

En Linux el tamaño de bloque es de 4K


107


8.5 Derecho de acceso

Normalmente a los usuarios o grupo de usuarios se les concede ciertos

derechos de acceso a los archivos.

Se les puede asignar a los usuarios los siguientes derechos a cada archivo:

Ejecución, lectura, adición, actualización, borrado.


108


Bibliografía

Carretero Pérez, Jesús, Garcia carballeria, Félix, Pérez Costoya,

Fernando.

Deitel, H (1990) Sistemas Operativos. EUA Addison Wesley

Iberoamericana S.A.

James L. Peterson(1993) Sistemas Operativos, Conceptos

fundamentales. España, Editorial Reverte S.A.

Stallings, William (1997) Sistemas Operativos, 2de. Madrid, Prentice

Hall.

Sistema operativos una visión ampliada, Mc-Graw Hill/Interamericana

S.A.

Sistemas Operativos - Parte Teórica Marco Antonio Coral Y. y otros

Tanenbaum, Andrew S (1993) Sistemas Operativos Modernos. México,

Prentice Hall Hispanoamericana, S.A

UNIVERSIDAD PERUANA LAS AMERICAS – ESCUELA …

Documents

Transcript of UNIVERSIDAD PERUANA LAS AMERICAS – ESCUELA …