ADC – Unidad I – Representación de la Información

SISTEMAS NUMERICOS

Los sistemas numéricos son muy importantes en computación, estudiaremos los sistemas en base 2, 8, 10 y 16 que son las que más se utilizan en computación; por supuesto con la relación entre la base 10 que es la que utilizamos los seres humanos.

Sistemas de numeración

Un sistema de numeración es un conjunto de símbolos y reglas que se utilizan para representar y operar con cantidades.

Sistemas Aditivos:

Los sistemas aditivos son aquellos que acumulan los símbolos de todas las unidades, decenas… como sean necesarios hasta completar el número. Una de sus características es por tanto que se pueden poner los símbolos en cualquier orden, aunque en general se ha preferido una determinada disposición. Han sido de este tipo las numeraciones egipcia, sumeria (de base 60), hitita, cretense, azteca (de base 20), romana y las alfabéticas de los griegos, armenios, judíos y árabes.

 

Historia

Sistema Egipcio

Desde el tercer milenio A.C. los egipcios usaron un sistema describir los números en base diez utilizando los jeroglíficos de la figura para representar los distintos ordenes de unidades.

Los siguientes signos jeroglíficos eran usados para representar las diferentes potencias de diez en la escritura de izquierda a derecha.

Valor	1	10	100	1.000	10.000	100.000	1 millón, o infinito
Jeroglífico						o

 

Sistema Griego

El primer sistema de numeración griego se desarrolló hacia el 600 A.C. Era un sistema de base decimal que usaba los símbolos de la figura siguiente para representar esas cantidades. Se utilizaban tantas de ellas como fuera necesario según el principio de las numeraciones aditivas.

<></>

<></>

Para representar la unidad y los números hasta el 4 se usaban trazos verticales. Para el 5, 10 y 100 las letras correspondientes a la inicial de la palabra cinco (pente), diez (deka) y mil (khiloi). Por este motivo se llama a este sistema acrofónico.

 

Los símbolos de 50, 500 y 5000 se obtienen añadiendo el signo de 10, 100 y 1000 al de 5, usando un principio multiplicativo. Progresivamente este sistema ático fue reemplazado por el jónico, que empleaba las 24 letras del alfabeto griego junto con algunos otros símbolos según la tabla siguiente      De esta forma los números parecen palabras, ya que están compuestos por letras, y a su vez las palabras tienen un valor numérico, basta sumar las cifras que corresponden a las letras que las componen. Esta circunstancia hizo aparecer una nueva suerte de disciplina mágica que estudiaba la relación entre los números y las palabras. En algunas sociedades como la judía y la árabe, que utilizaban un sistema similar, el estudio de esta relación ha tenido una gran importancia y ha constituido una disciplina aparte: la kábala, que persigue fines místicos y adivinatorios.

 

Sistemas Híbridos

En estos sistemas se combina el principio aditivo con el multiplicativo.

Sistema Chino

La forma clásica de escritura de los números en China se empezó a usar desde el 1500 A.C. aproximadamente. Es un sistema decimal estricto que usa las unidades y los distintas potencias de 10. Utiliza los ideogramas de la figura

y usa la combinación de los números hasta el diez con la decena, centena, millar y decena de millar para según el principio multiplicativo representar 50, 700 ó 3000. El orden de escritura se hace fundamental, ya que 5 10 7 igual podría representar 57 que 75.

Tradicionalmente se ha escrito de arriba abajo aunque también se hace de izquierda a derecha como en el ejemplo de la figura. No es necesario un símbolo para el cero siempre y cuando se pongan todos los ideogramas, pero aún así a veces se suprimían los correspondientes a las potencias de 10.

 
Aparte de esta forma que podríamos llamar canónica se usaron otras. Para los documentos importantes se usaba una grafía más complicada con objeto de evitar falsificaciones y errores. En los sellos se escribía de forma más estilizada y lineal y aún se usaban hasta dos grafías diferentes en usos domésticos y comerciales, aparte de las variantes regionales. Los eruditos chinos por su parte desarrollaron un sistema posicional muy parecido al actual que desde que incorporó el cero por influencia india en s. VIII en nada se diferencia de este.

Sistema Babilónico

Entre las muchas civilizaciones que florecieron en la antigua Mesopotamia se desarrollaron distintos sistemas de numeración. Muchos siglos A.C. se inventó un sistema de base 10, aditivo hasta el 60 y posicional para números superiores.

 

Para la unidad se usaba la marca vertical que se hacía con el punzón en forma de cuña. Se ponían tantos como fuera preciso hasta llegar a 10, que tenía su propio signo.

 

 

   De este se usaban los que fuera necesario completando con las unidades hasta llegar a 60.

A partir de ahí se usaba un sistema posicional en el que los grupos de signos iban representando sucesivamente el número de unidades, 60, 60×60, 60×60x60 y asi sucesivamente como en los ejemplos que se acompañan.

<></>

<></>

Sistema Maya

Los mayas idearon un sistema de base 20 con el 5 cómo base auxiliar. La unidad se representaba por un punto. Dos, tres, y cuatro puntos servían para 2, 3 y 4. El 5 era una raya horizontal, a la que se añadían los puntos necesarios para representar 6, 7, 8 y 9. Para el 10 se usaban dos rayas, y de la misma forma se continúa hasta el 20, con cuatro rayas.

Hasta aquí parece ser un sistema de base 5 aditivo, pero en realidad, considerados cada uno un solo signo, estos símbolos constituyen las cifras de un sistema de base 20, en el que hay que multiplicar el valor de cada cifra por 1, 20, 20×20, 20×20x20 … según el lugar que ocupe, y sumar el resultado. Es por tanto un sistema posicional que se escribe a arriba abajo, empezando por el orden de magnitud mayor.

Al tener cada cifra un valor relativo según el lugar que ocupa, la presencia de un signo para el cero, con el que indicar la ausencia de unidades de algún orden, se hace imprescindible y los mayas lo usaron, aunque no parece haberles interesado el concepto de cantidad nula. Cómo los babilonios lo usaron simplemente para indicar la ausencia de otro número.

Pero los científicos mayas eran a la vez sacerdotes ocupados en la observación astronómica y para expresar los número correspondientes a las fechas usaron unas unidades de tercer orden irregulares para la base 20. Así la cifra que ocupaba el tercer lugar desde abajo se multiplicaba por 20×18=360 para completar una cifra muy próxima a la duración de un año.

El año lo consideraban dividido en 18 unidad que constaba cada uno de 20 días. Se añadían algunos festivos (uayeb) y de esta forma se conseguía que durara justo lo que una de las unidades de tercer orden del sistema numérico. Además de éste calendario solar, usaron otro de carácter religioso en el que el año se divide en 20 ciclos de 13 días.

 
Al romperse la unidad del sistema éste se hace poco práctico para el cálculo y aunque los conocimientos astronómicos y de otro tipo fueron notables los mayas no desarrollaron una matemática más allá del calendario.

 

Sistema Numérico

Un sistema de numeración es un conjunto de reglas y símbolos que permiten representar de forma única los números. Esta representación posibilita la realización de sencillos algoritmos para la ejecución de operaciones aritméticas.

 

Los sistemas de numeración usados en la actualidad son posiciónales. El valor de una cifra depende tanto de qué dígito es como de la posición que ocupa en el número. Base: Es el número de símbolos distintos que se utiliza para representar un número en un sistema de numeración. Entonces decimos que el sistema de numeración es de esa base. Los símbolos de una determinada base van desde el 0 hasta la base b-1.

Coeficiente: El coeficiente determina el valor de cada símbolo dependiendo de la posición que ocupe con respecto al punto decimal. Por lo tanto a estos sistemas de numeración los llamaremos sistemas de numeración posiciónales, porque el valor de cada cifra dependerá del valor absoluto del símbolo y de la posición relativa que ocupa con respecto al punto decimal.

Los sistemas de numeración actuales como sistemas posiciónales, en que  el valor que representa cada símbolo o cifra, depende de su valor absoluto y de la posición relativa que ocupa la cifra con respecto al resto.

En los sistemas de numeración existe un elemento característico que define el sistema y se denomina base, siendo ésta el número de símbolos que se utilizan para la representación.

Se entiende por base (b) de un sistema de numeración al número de símbolos que se utilizan para la representación. Todos los sistemas usados actualmente usan una base n. En un sistema de numeración de base n existen n símbolos. Al escribir un número en base n, el dígito d en la posición i, de derecha a izquierda, tiene un valor.

La base de un sistema numérico se refiere al número de símbolos básicos usados, los más usuales son:

·         Decimal (10)

·         Binario (2)

·         Octal (8)

·         Hexadecimal (16)

 

Sistema Decimal

Para entender los números binarios y hexadecimales, lo mejor es entender bien cómo funcionan los números decimales.

Cada dígito de un número decimal va en una "posición", y el punto decimal nos dice qué posición es cada una.

La posición justo a la izquierda del punto son las "unidades". Cada vez que nos movemos a la izquierda vale 10 veces más, y a la derecha vale 10 veces menos:

El sistema decimal de numeración también se llama "base 10", porque se basa en el número 10.

En decimal hay diez símbolos (0, 1, 2, 3, 4, 5, 6, 7 , 8, 9), pero fíjate en esto: no hay un símbolo para el "diez". "10" son en realidad dos símbolos juntos, un "1" y un "0":

Valor posicional

Para entender los números decimales primero tienes que conocer la notación posicional.

Cuando escribimos números, la posición (o "lugar") de cada número es importante.

En el número 327:

• el "7" está en la posición de las unidades, así que vale 7 (o 7 "1"s),

• el "2" está en la posición de las decenas, así que son 2 dieces (o veinte),

• y el "3" está en la posición de las centenas, así que vale 3 cientos.

"Trescientos veintisiete"

 

En decimal contamos 0,1,2,3,4,5,6,7,8,9, entonces decimos "me he quedado sin símbolos, así que empiezo otra vez con 0, pero primero voy a añadir 1 a la izquierda".

En decimal contamos 0,1,2,3,4,5,6,7,8,9, entonces decimos "me he quedado sin símbolos, así que empiezo otra vez con 0, pero primero voy a añadir 1 a la izquierda".

 

En el caso de números con decimales, la situación es análoga aunque, en este caso, algunos exponentes de las potencias serán negativos, concreta­mente el de los dígitos colocados a la derecha del separador decimal. Por ejemplo, el número 8245,97 se calcularía como:

 

8 millares + 2 centenas + 4 decenas + 5 unidades + 9 décimos + 7 céntimos

8*10³ + 2*10² + 4*10¹ + 5*10⁰ + 9*10^-1 + 7*10^-2, es decir:

8000 + 200 + 40 + 5 + 0,9 + 0,07 = 8245,97

 

 Sistema Binario

Números binarios Un número binario está hecho sólo de 0s y 1s. Así que cada cifra sólo tiene dos posibilidades: 0 o 1

Bits

En el mundo de los ordenadores "dígito binario" se suele abreviar con la palabra "bit"

Más de un dígito

Así que si un dígito sólo tiene dos valores posibles (como "0" y "1", o "On" y "Off"), ¿cuántas combinaciones hay con 2 o más dígitos binarios?

Doblar cifras binarias

Fíjate también en que cada vez que pones una cifra binaria más, se doblan las posibilidades. ¿Por qué el doble? Porque tienes que tomar todas las posiciones anteriores y hacerlas corresponder con un "0" y un "1" como hicimos antes.

Así que si tienes 5 cosas el total sería 32, con 6 cosas sería 64, etc.

Usando exponentes, esto lo podemos escribir así:

23	22	21	20
2 X 2 X 2 = 8	2 X 2 = 4	2 = 2	1 = 1
Numero Binario
1	0	1	1
1 X 8 = 8	0 X 4 = 0	1 X 2 = 2	1 X 1 = 1
8 + 0 + 2 + 1 = 11
Número Decimal
11

 

Ejemplo:

y para expresar que ambas cifras describen la misma cantidad lo escribimos así:

 

1011₂ = 11₁₀

 

Bit menos significativo

En computación, el bit menos significativo (LSB o Least Significant Bit, en sus siglas en inglés) es la posición de bit en un número binario que tiene el menor valor (el situado más a la derecha). En ocasiones, se hace referencia al LSB como el bit del extremo derecho.

 

 

 Sistema octal

 

El sistema numérico en base 8 se llama octal y utiliza los dígitos ( 0, 1, 2, 3, 4, 5, 6, 7).

El inconveniente de la codificación binaria es que la representación de algunos números resulta muy larga. Por este motivo se utilizan otros sistemas de numeración que resulten más cómodos de escribir: el sistema octal y el sistema hexadecimal. Afortunadamente, resulta muy fácil convertir un número binario a octal o a hexadecimal.

En el sistema de numeración octal, los números se representan mediante ocho dígitos diferentes: 0, 1, 2, 3, 4, 5, 6 y 7. Cada dígito tiene, naturalmente, un valor distinto dependiendo del lu­gar que ocupen. El valor de cada una de las posiciones viene determinado por las potencias de base 8.

Por ejemplo, el número octal 2738 tiene un valor que se calcula así:

83	82	81	80
8 X 8 X 8 = 512	8 X 8 = 64	8 = 8	1 = 1
Numero Octal
2	7	3	0
2 X 512 = 1024	7 X 64 = 448	3 X 8 = 24	0 X 1 = 0
1024 + 448 + 24 + 0 = 1496
Número Decimal
1496

 

2*8³ + 7*8² + 3*8¹  + 0*8⁰ = 2*512 + 7*64 + 3*8 + 0*1 = 1496₁₀

273₈ = 1496₁₀

 

 

 

Sistema Hexadecimal

El sistema hexadecimal, a veces abreviado como hex, es el sistema de numeración posicional de base 16 —empleando por tanto 16 símbolos—. Su uso actual está muy vinculado a la informática y ciencias de la computación, pues los computadores suelen utilizar el byte u octeto como unidad básica de memoria; y, debido a que un byte representa 28 valores posibles, y esto puede representarse como 2^8 = 2^4 \cdot 2^4 = 16 \cdot 16 = 1 \cdot 16^2 + 0 \cdot 16^1 + 0 \cdot 16^0, que, según el teorema general de la numeración posicional, equivale al número en base 16 10016, dos dígitos hexadecimales corresponden exactamente —permiten representar la misma línea de enteros— a un byte.

En el sistema hexadecimal los números se representan con dieciséis símbolos: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E y F. Se utilizan los caracteres A, B, C, D, E y F representando las cantidades decimales 10, 11, 12, 13, 14 y 15 respectivamente, porque no hay dígitos mayores que 9 en el sistema decimal. El valor de cada uno de estos símbolos depende, como es lógico, de su posición, que se calcula mediante potencias de base 16.

El sistema hexadecimal actual fue introducido en el ámbito de la computación por primera vez por IBM en 1963.

Calculemos, a modo de ejemplo, el valor del número hexadecimal 1A3F16:

163	162	161	160
16 X 16 X 16 = 4096	16 X 16 = 256	16 = 16	1 = 1
Numero Hexadecimal
1	A	3	F
1 X 4096 = 4096	10 X 256 = 2560	3 X 16 = 48	15 X 1 = 15
4096 + 2560 + 48 + 15 = 6719
Número Decimal
719

1A3F₁₆ = 1*16³ + A*16² + 3*16¹ + F*16⁰

1*4096 + 10*256 + 3*16 + 15*1 = 6719

1A3F₁₆ = 6719₁₀

 

 Tablas

TABLA DECIMAL, BINARIO, OCTAL, HEXADECIMAL
	108	107	106	105	104	103	102	101	100
Decimal	100.000.000	10.000.000	1.000.000	100.000	10.000	1.000	100	10	1
Binario	28	27	26	25	24	23	22	21	20
	256	128	64	32	16	8	4	2	1
Octal	88	87	86	85	84	83	82	81	80
	16.777.216	2.097.152	262.144	32.768	4.096	512	64	8	1
Hexadecimal	168	167	166	165	164	163	162	161	160
	4.294.967.296	268.435.456	16.777.216	1.048.576	65.536	4.096	256	16	1

 

 

Decimal	Binario	Octal	Hexadecimal
0	0000	0	0
1	0001	1	1
2	0010	2	2
3	0011	3	3
4	0100	4	4
5	0101	5	5
6	0110	6	6
7	0111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F
16	10000	20	10
17	10001	21	11
18	10010	22	12
19	10011	23	13
20	10100	24	14
21	10101	25	15
22	10110	26	16
23	10111	27	17
24	11000	30	18
25	11001	31	19
26	11010	32	1A
27	11011	33	1B
28	11100	34	1C
29	11101	35	1D
30	11110	36	1E
31	11111	37	1F
32	100000	40	20

 

Conversiones

   Conversión decimal a binario

Existen dos maneras de convenir un número decimal entero a su representación equivalente en el sistema binario.

El primer método: en un sistema de posición donde cada dígito decimal tiene un valor basado en su posición relativa al LSB. Cualquier número decimal puede convenirse a su equivalente a binario, simplemente sumando en el número decimal las diversas posiciones que contenga un 1. El número decimal se expresa simplemente como una suma de potencias de 2 y luego los unos y los ceros se escriben en las posiciones adecuadas de los bits. Por ejemplo:

196

27	26	25	24	23	22	21	20
128	64	32	16	8	4	2	1
Numero Decimal 196
X	X	-	-	-	X	-	-
128 + 64 + 4 = 196
1	1	0	0	0	1	0	0
Número Binario
1100100

 

El segundo método: consiste dividir repetidas veces el número entre dos (2) hasta que su cociente sea menor que él

196	2
0	98	2
	0	49	2
		1	24	2
			0	12	2
				0	6	2
					0	3	2
	11000100					1	1	2
							1	0

 

   Conversión decimal a octal

Consiste dividir repetidas veces el número entre ocho (8) hasta que su cociente sea menor que él

196	8
4	24	8
	0	3	8
		3	1
304

 

 Conversión decimal a Hexadecimal

Consiste dividir repetidas veces el número entre diez y seis (16) hasta que su cociente sea menor que él

196	16
4	12	16
	12	0
12-4=C4

 

   Conversión binario a decimal

El sistema de numeración binario es un sistema de posición donde cada dígito binario (bit) tiene un valor basado en su posición relativa al LSB. Cualquier número binario puede convenirse a su equivalente decimal, simplemente sumando en el número binario las diversas posiciones que contenga un 1.

11000100

27	26	25	24	23	22	21	20
1	1	0	0	0	1	0	0
128	64	0	0	0	4	0	0
128+64+0+0+0+4+0+0
196

 

   Conversión binario a octal

 

Los bits del número binario se agrupan en conjuntos de tres comenzando por el LSB. Luego, cada grupo se convierte a su equivalente octal

11000100

21	20	22	21	20	22	21	20
1	1	0	0	0	1	0	0
2+1		0+0+0			4+0+0
3		0			4
304

 

   Conversión binario a hexadecimal

 

Los bits del número binario se agrupan en conjuntos de cuatro comenzando por el LSB. Luego, cada grupo se convierte a su equivalente hexadecimal.

11000100

23	22	21	20	23	22	21	20
1	1	0	0	0	1	0	0
8	4	0	0	0	4	0	0
(8+4) y 4
12 y 4
C4

 

   Conversión octal a decimal

Un número octal puede convenirse fácilmente a su equivalente decimal multiplicando cada dígito octal por su valor posicional.

 

82	81	80
8 X 8 = 64	8 = 8	1 = 1
3	0	4
3 X 64 = 192	0 X 8 = 0	4 X 1 = 4
192+0+4
196

 

   Conversión octal a binario

La conversión de octal a binario se lleva a cabo conviniendo cada dígito octal en su equivalente binario de 3 bits. Por medio de estas conversiones, cualquier número octal se conviene a binario, convirtiéndolo de manera individual.

3		0			4
21	20	22	21	20	22	21	20
1	1	0	0	0	1	0	0
2+1		0+0+0			4+0+0
3		0			4
11000100

 

   Conversión octal a hexadecimal

La conversión de octal a hexadecimal hay que llevar a cabo una etapa intermedia; es decir, pasar el número a decimal o binario y éste, por último, a hexadecimal.

Octal a Binario

3		0			4
21	20	22	21	20	22	21	20
1	1	0	0	0	1	0	0
2+1		0+0+0			4+0+0
3		0			4
11000100

Binario a Hexadecimal

23	22	21	20	23	22	21	20
1	1	0	0	0	1	0	0
8	4	0	0	0	4	0	0
(8+4) y 4
12 y 4
C4

 

   Conversión Hexadecimal a decimal

La conversión se realiza multiplicando el peso de cada posición por el equivalente decimal del dígito de cada posición y sumando los productos.

C4
C	4
161	160
16 X 12	1 X 4
192  + 4
196

 

 

    Conversión Hexadecimal a binario

Al igual que el sistema de numeración octal, el sistema hexadecimal se usa principalmente como método ‘taquigráfico" en la representación de números binarios. Es una tarea relativamente simple la de convertir un número hexadecimal en binario. Cada dígito hexadecimal se convierte en su equivalente binario de 4 bits, basta con sustituir cada valor hexadecimal por los cuatro dígitos binarios equivalentes

C4
C				4
23	22	21	20	23	22	21	20
X	X	-	-	-	X	-	-
1	1	0	0	0	1	0	0
11000100

 

 

    Conversión Hexadecimal a octal

La conversión de hexadecimal a octal hay que llevar a cabo una etapa intermedia; es decir, pasar el número a decimal o binario y éste, por último, a octal.

Hexadecimal a Binario

C4
C				4
23	22	21	20	23	22	21	20
X	X	-	-	-	X	-	-
1	1	0	0	0	1	0	0
11000100

 

Binario a Octal

21	20	22	21	20	22	21	20
1	1	0	0	0	1	0	0
2+1		0+0+0			4+0+0
3		0			4
304

 

Aplicaciones

Colores en hexadecimal

Rojo, verde y azul

Los números hexadecimales se usan en las páginas web para indicar colores. Los colores se definen mezclando cantidades de rojo, verde y azul, cada valor está entre:

0 y 255 (en decimal), o

00 y FF (en hexadecimal)

 

Esto se basa en la idea de que todos los colores se pueden conseguir mezclando rojo, verde y azul (en inglés, "Red, Green, Blue"), así que se llama "sistema de color RGB". También se le llama sistema "aditivo" de color, porque se empieza con el negro y se van añadiendo los tres colores.

Hexadecimales

Los números hexadecimales son "naturales" para los ordenadores, porque manejan números binarios, y cuatro cifras binarias hacen una cifra hexadecimal (lee dígitos binarios):

Decimal:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Binario:	0	1	10	11	100	101	110	111	1000	1001	1010	1011	1100	1101	1110	1111
Hexadecimal:	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F

Dos dígitos hexadecimales juntos (en informática a eso se le llama un "byte") representan uno de 16×16=256 niveles diferentes de color.

16 millones de colores

Como cada uno de los tres colores puede tomar valores de 0 a 255 (256 valores posibles), hay 256×256×256 = 256³ = 16,777,216 combinaciones posibles de colores (y por eso verás que los ordenadores dicen que pueden mostrar "16 millones de colores")

Formato web

El formato o ("notación") que se usa en páginas web es #RRGGBB, donde RR es el valor de la componente roja (usando dos dígitos hexadecimales), GG la componente verde y BB la azul.

 

Ejemplo: un tono de azul sería:

• 64/255 rojo,

• 48/255 verde

• 255/255 azul (el máximo)

Así que en decimal es (64,48,255), que equivale al hexadecimal (40,30,FF) y se escribe #4030FF.

Algunos colores comunes

Color	Decimal (Rojo, verde, azul)	Hexadecimal (#RRGGBB)
Negro	(0, 0, 0)	#000000
Blanco	(255, 255, 255)	#FFFFFF
Rojo	(255, 0, 0)	#FF0000
Verde	(0, 255, 0)	#00FF00
Azul	(0, 0, 255)	#0000FF
Amarillo	(255, 255, 0)	#FFFF00
Cian	(0, 255, 255)	#00FFFF
Magenta	(255, 0, 255)	#FF00FF

 

 

Notas Sistemas Operativos-Modelo de Datos

Las Notas finales de las materias Sistemas Operativos y Modelo de Datos del Periodo 2009-I, ya están publicadas.

http://eduhesc.wordpress.com/tag/notas/

Cualquier inquietud canalizarla mediante el correo electrónico: eduhesc@gmail.com, o través de los comentarios de este blog.

Unidad III – Gestion de Memoria

En un sistema monoprogramado, la memoria principal se divide en dos partes: una parte para el sistema operativo (monitor residente, núcleo) y otra parte para el programa que se ejecuta en ese instante. En un sistema multiprogramado, la parte de “usuario” de la memoria debe subdividirse aún más para hacer sitio a varios procesos. La tarea de subdivisión la lleva a cabo dinámicamente el sistema operativo y se conoce como gestión de memoria.

En un sistema multiprogramado resulta vital una gestión efectiva de la memoria. Si sólo hay unos pocos procesos en memoria, entonces la mayor parte del tiempo estarán esperando a la E/S y el procesador estará desocupado. Por ello, hace falta repartir eficientemente la memoria para meter tantos procesos como sea posible.

REQUISITOS DE LA GESTIÓN DE MEMORIA

Al realizar un estudio de los diversos mecanismos y políticas relacionadas con la gestión de memoria, vale la pena tener en mente los requisitos que se intentan satisfacer: [LIST88] propone cinco requisitos:

• Reubicación
• Protección
• Compartición
• Organización lógica
• Organización física.

Reubicación

En un sistema multiprogramado, la memoria disponible se encuentra normalmente com-partida por varios procesos. En general, el programador no puede conocer por adelantado qué otros programas residirán en memoria en el momento de la ejecución del programa. Además, se busca poder cargar y descargar los procesos activos en la memoria principal para maximizar el uso del procesador, manteniendo una gran reserva de procesos listos para ejecutar. Una vez que un programa haya sido descargado al disco, se limitará a declarar que, cuando vuelva a ser cargado, debe situarse en la misma región de memoria principal que antes.

De este modo, se sabe antes de tiempo dónde debe situarse un programa y hay que permitir que el programa pueda moverse en memoria principal como resultado de un intercambio. Esta situación plantea algunos asuntos técnicos relativos al direccionamiento, tal y como se muestra en la figura 6.1, que representa la imagen de un proceso. Por simplicidad, se supondrá que la imagen del proceso ocupa una región contigua de la memoria principal. Sin duda, el sistema operativo tiene que conocer la ubicación de la información de control del proceso y de la pila de ejecución, así como el punto de partida para comenzar la ejecución del programa para dicho proceso. Puesto que el sistema operativo gestiona la memoria y es responsable de traer el proceso a memoria principal, estas direcciones deben ser fáciles de conseguir. Además, el procesador debe ocuparse de las referencias a memoria dentro del programa. Las instrucciones de bifurcación deben contener la dirección que haga referencia a la instrucción que se vaya a ejecutar a continuación. Las instrucciones que hagan referencia a datos deben contener la dirección del byte o de la palabra de datos referenciada. De algún modo, el hardware del procesador y el software del sistema operativo deben ser capaces de traducir las referencias a memoria encontradas en el código del programa a las direcciones físicas reales que reflejen la posición actual del programa en memoria principal.

Protección

Cada proceso debe protegerse contra interferencias no deseadas de otros procesos, tanto accidentales como intencionadas. Así pues, el código de un proceso no puede hacer referencia a posiciones de memoria de otros procesos, con fines de lectura o escritura, sin permiso. Hasta cierto punto, satisfacer las exigencias de reubicación aumenta la dificultad de satisfacción de las exigencias de protección. Puesto que se desconoce la ubicación de un programa en memoria principal, es imposible comprobar las direcciones absolutas durante la compilación para asegurar la protección. Es más, la mayoría de los lenguajes de programación permiten el cálculo dinámico de direcciones durante la ejecución, generando, por ejemplo, un índice de un vector o un puntero a una estructura de datos. Por tanto, todas las referencias a memoria generadas por un proceso deben comprobarse durante la ejecución para asegurar que sólo hacen referencia al espacio de memoria destinado a dicho proceso. Afortunadamente, como se verá, los mecanismos que respaldan la reubicación también forman parte básica del cumplimiento de las necesidades de protección.

La imagen del proceso de la figura 6.1 ilustra las necesidades de protección. Normalmente, un proceso de usuario no puede acceder a ninguna parte del sistema operativo, tanto programa como datos. De nuevo, el programa de un proceso no puede en general bifurcar hacia una instrucción de otro proceso. Además, sin un acuerdo especial, el programa de un proceso no puede acceder al área de datos de otro proceso. El procesador debe ser capaz de abandonar tales instrucciones en el momento de la ejecución.

Nótese que, en los términos del ejemplo, las exigencias de protección de memoria pueden ser satisfechas por el procesador (hardware) en vez de por el sistema operativo (software). Esto es debido a que el sistema operativo no puede anticiparse a todas las referencias a memoria que hará un programa. Incluso si tal anticipación fuera posible, sería prohibitivo en términos de tiempo consumido el proteger cada programa por adelantado de posibles violaciones de referencias a memoria. Así pues, sólo es posible evaluar la tolerancia de una referencia a memoria (acceso a datos o bifurcación) durante la ejecución de la instrucción que realiza la referencia. Para llevar esto a cabo, el hardware del procesador debe poseer dicha capacidad.

Compartición

Cualquier mecanismo de protección que se implemente debe tener la flexibilidad de permitir el acceso de varios procesos a la misma zona de memoria principal. Por ejemplo, si una serie de procesos están ejecutando el mismo programa, resultaría beneficioso permitir a cada proceso que acceda a la misma copia del programa, en lugar de tener cada uno su propía copia aparte. Los procesos que cooperan en una tarea pueden necesitar acceso compartido a la misma estructura de datos. El sistema de gestión de memoria debe, por tanto, permitir accesos controlados a las áreas compartidas de la memoria, sin comprometer la protección básica. De nuevo, se verá que los mecanismos empleados para respaldar la reubicación forman parte básica de las capacidades de compartición.

Organización Lógica

De forma casi invariable, la memoria principal de un sistema informático se organiza como un espacio de direcciones lineal o unidimensional que consta de una secuencia de bytes o palabras. La memoria secundaria, a nivel físico, se organiza de forma similar. Si bien esta organización refleja fielmente el hardware de la máquina, no se corresponde con la forma en la que los programas están construidos habitualmente. La mayoría de los programas se organizan en módulos, algunos de los cuales no son modificables (sólo lectura, sólo ejecución) y otros contienen datos que se pueden modificar. Si el sistema operativo y el hardware del computador pueden tratar de forma efectiva los programas de usuario y los datos en forma de módulos de algún tipo, se conseguirá una serie de ventajas, tales como:

1. Los módulos pueden escribirse y compilarse independientemente, mientras que el sistema resuelve durante la ejecución todas las referencias de un módulo a otro.

2. Con un escaso coste adicional, pueden otorgarse varios grados de protección (sólo lectura, sólo ejecución) a los distintos módulos.

3. Es posible introducir mecanismos por medio de los cuales los procesos puedan compartir módulos. La ventaja de ofrecer compartición a nivel de módulo es que esto se corresponde con la visión del problema que tiene el usuario y, por tanto, es fácil para el usuario especificar la compartición que desea.

La herramienta que más fácilmente satisface estas necesidades es la segmentación, que es una de las técnicas de gestión de memoria estudiadas en este capítulo.

Organización Física

La memoria del computador se organiza en, al menos, dos niveles: memoria principal y memoria secundaria. La memoria principal ofrece un acceso rápido con un coste relativamente alto. Además, la memoria principal es volátil; esto es, no proporciona almacenamiento permanente. La memoria secundaria es más lenta y barata que la memoria principal y, normalmente, no es volátil. De este modo, una memoria secundaria de gran capacidad puede permitir un almacenamiento a largo plazo de programas y datos, al tiempo que una memoria principal pequeña mantiene los programas y datos de uso actual.

En este esquema a dos niveles, la organización del flujo de información entre la memoria principal y la secundaria tiene un gran interés en el sistema. La responsabilidad de este flujo podría asignarse al programador, pero esto es impracticable e indeseable, debido a dos razones:

1. La memoria principal disponible para un programa y sus datos puede ser insuficiente. En este caso, el programador debe emplear una práctica que se conoce como superposición (overlaying), en la cual el programa y los datos se organizan de tal forma que puede haber varios módulos asignados a la misma región de memoria, con un programa principal responsable del intercambio de los módulos según se necesite. Incluso con la ayuda de herramientas de compilación, la programación superpuesta malgasta el tiempo del programador.

2. En un entorno multiprogramado, el programador no conoce durante la codificación cuánto espacio habrá disponible o dónde estará este espacio.

Resulta claro entonces que la tarea de mover información entre los dos niveles de memoria debe ser responsabilidad del sistema. Esta tarea es la esencia de la gestión de memoria.

CARGA DE PROGRAMAS EN MEMORIA PRINCIPAL

La tarea central de cualquier sistema de gestión de memoria es traer los programas a memoria principal para su ejecución en el procesador. En casi todos los sistemas multiprogramados modernos, esta tarea supone un esquema sofisticado conocido como memoria virtual. La memoria virtual está, a su vez, basada en el uso de una de dos técnicas básicas; segmentación y/o paginación. Antes de ver estás técnicas de memoria virtual, se debe preparar el terreno considerando técnicas más simples que no requieren el uso de memoria virtual. Una de estas técnicas, la partición, se ha venido usando con distintas variantes en algunos sistemas operativos ahora obsoletos. Las otras dos técnicas, la paginación simple y la segmentación simple, no se usan en solitario. No obstante, el estudio de la memoria virtual resultará más sencillo si se consideran en primer lugar estas dos técnicas, sin tener en cuenta la memoria virtual.

Partición fija

En la mayoría de los esquemas de gestión de memoria, se puede suponer que el sistema operativo ocupa una parte fija de memoria principal y que el resto de la memoria está disponible para ser usado por varios procesos. El esquema más sencillo de gestión de la memoria disponible es dividirla en regiones con límites fijos.

Tamaños de Partición

En la figura 6.2 se ofrecen ejemplos de dos alternativas de partición fija. Una posibilidad es emplear particiones de igual tamaño. En este caso, cualquier proceso cuyo tamaño sea menor o igual que el tamaño de la partición puede cargarse en cualquier partición libre. Si todas las particiones están ocupadas y no hay procesos residentes en estado Listo o Ejecutando, el sistema operativo puede sacar un proceso de alguna de las particiones y cargar otro proceso de forma que haya trabajo para el procesador.

Las particiones fijas de igual tamaño plantean dos dificultades:

• Un programa puede ser demasiado grande para caber en la partición. En este caso, el programador debe diseñar el programa mediante superposiciones, para que sólo una parte del programa esté en memoria principal en cada instante. Cuando se necesita un módulo que no está presente, el programa de usuario debe cargar dicho módulo en la partición del programa, superponiéndose a los programas y datos que se encuentren en ella

•El uso de memoria principal es extremadamente ineficiente. Cualquier programa, sin im-portar lo pequeño que sea, ocupará una partición completa. En el ejemplo, puede haber un programa que ocupe menos de 128Kb de memoria y, aún así, ocuparía una partición de 512Kb cada vez que se cargase. Este fenómeno, en el que se malgasta el espacio interno de una partición cuando el bloque de datos cargado sea más pequeño que la partición, se denomina fragmentación interna.

Pueden reducirse, aunque no solventarse, ambos problemas, por medio del empleo de particiones de tamaños distintos, como se muestra en la figura 5.2b. En este ejemplo, los programas de hasta 1Mb pueden alojarse sin superposición. Las particiones menores de 512K permiten alojar programas más pequeños con un desperdicio menor.

Con particiones del mismo tamaño, la ubicación de un proceso en memoria es trivial. Mientras haya alguna partición libre, puede cargarse un proceso en esa partición. Puesto que todas las particiones son de igual tamaño, no importa la partición que se use. Si todas las particiones están ocupadas con procesos que no están listos para ejecutar, uno de esos procesos debe sacarse y hacer sitio para un nuevo proceso. Cuál debe expulsarse es una decisión de planificación; este punto se tratará en el capítulo 8.

Con particiones de distintos tamaños, hay dos maneras posibles de asignar los procesos a las particiones. La forma más simple es asignar cada proceso a la partición más pequeña en la que quepa’. En este caso, hace falta una cola de planificación para cada partición, que albergue los procesos expulsados cuyo destinado es dicha partición (figura 6.3a). La ventaja de este enfoque es que los procesos están siempre asignados de forma que se minimiza la memoria desperdiciada dentro de cada partición.

Sin embargo, aunque esta técnica parece óptima desde el punto de vista de una partición in-dividual, no lo es desde el punto de vista del sistema global. Considérese el caso de la figura 6.2b, por ejemplo, donde no hay procesos con un tamaño comprendido entre 768K y 1M en un determinado instante. En este caso, la partición de 768K permanecerá sin usar, incluso aunque algún proceso más pequeño pudiera haber sido asignado a la misma. Así pues, una solución mejor sería emplear una única cola para todos los procesos (figura 6.3b). Cuando se va a cargar un proceso en memoria principal, se selecciona la partición más pequeña disponible que pueda albergar al proceso. Si todas las particiones están ocupadas, se debe tomar una decisión de intercambio. Puede darse preferencia al intercambio de la partición más pequeña que pueda contener al proceso entrante. También es posible considerar otros factores, tales como priori-dades y preferencia para descargar procesos bloqueados antes que procesos listos.

El uso de particiones de distinto tamaño proporciona cierto grado de flexibilidad a las par-ticiones fijas. Además, ambos tipos de esquema de partición fija son relativamente simples y exigen un software del sistema operativo y una sobrecarga de procesamiento mínimos. Sin embargo, se plantean los problemas siguientes:

• El número de particiones especificadas en el momento de la generación del sistema limita el número de procesos activos (no suspendidos) del sistema.

• Puesto que los tamaños de partición se programan en el momento de la generación del sistema, los trabajos pequeños no hacen un uso eficiente del espacio de las particiones. En un entorno en el que los requisitos básicos de almacenamiento de todos los procesos se conocen de antemano, puede ser una técnica razonable, pero, en la mayoría de los casos, ineficiente.

El uso de la partición fija es casi nulo hoy día. Como ejemplo de un sistema operativo fructuoso que empleaba está técnica se tiene un antiguo sistema operativo de grandes computadores de IBM, el OS/MFT (Multiprogramación con un número Fijo de Tareas).

Partición Dinámica

Para superar algunas de las dificultades de la partición estática, se desarrolló una solución denominada partición dinámica. Otra vez, este enfoque ha sido superado de largo por técnicas de gestión de memoria más sofisticadas. Un sistema operativo importante que empleaba esta técnica fue el antiguo OS/MVT (Multiprogramación con un número Variable de Tareas), para grandes computadores de IBM.

Con la partición dinámica, las particiones son variables en número y longitud. Cuando se trae un proceso a memoria principal, se le asigna exactamente tanta memoria como necesita y no más. En la figura 6.4 se muestra un ejemplo que usa 1MB de memoria principal. Al principio, la memoria principal está vacía, exceptuando el sistema operativo (figura 6.4a). Se cargan los tres primeros procesos, empezando en donde acaba el sistema operativo y ocupando sólo un espacio suficiente para cada proceso (figuras 6.4b, c y d). Esto deja un “hueco” al final de la memoria demasiado pequeño para un cuarto proceso. En algún momento, ninguno de los procesos en memoria está listo. Así pues, el sistema operativo saca al proceso 2 (figura 6.4e), que deja sitio suficiente para cargar un nuevo proceso, el proceso 4 (figura 6.4f). Puesto que el proceso 4 es más pequeño que el proceso 2, se crea otro hueco pequeño. Más tarde, se alcanza un punto en el que ninguno de los procesos que están en memoria principal están listos y el proceso 2, que está en estado Listo, pero suspendido, está disponible. Puesto que no hay suficiente sitio en memoria para el proceso 2, el sistema operativo expulsa al proceso 1 (figura 6.4g) y carga de nuevo el proceso 2 (figura 6.4h).

Como se muestra en el ejemplo, este método comienza bien, pero, finalmente, desemboca en una situación en la que hay un gran número de huecos pequeños en memoria. Conforme pasa el tiempo, la memoria comienza a estar más fragmentada y su rendimiento decae. Este fenómeno se denomina fragmentación externa y se refiere al hecho de que la memoria externa a todas las particiones se fragmenta cada vez más, a diferencia de la fragmentación interna, que se comentó anteriormente.

Una técnica para superar la fragmentación externa es la compactación: De vez en cuando, el sistema operativo desplaza los procesos para que estén contiguos de forma que toda la memoria libre quede junta en un bloque. Por ejemplo, en la figura 6.4h, la compactación produce un bloque de memoria libre de 256K. Este hueco puede ser suficiente para cargar un proceso adicional. La dificultad de la compactación está en que es un procedimiento que consume tiempo, por lo que desperdicia tiempo del procesador. La compactación necesita de la capacidad de reubicación dinámica. Es decir, se debe poder mover un programa de una región a otra de memoria principal sin invalidar las referencias a memoria del programa (véase el Apéndice 6A).

Algoritmo de Ubicación

Puesto que la compactación de memoria consume tiempo, atañe al diseñador del sistema operativo decidir adecuadamente cómo asignar un proceso a memoria (como llenar los huecos). Cuando llega el momento de cargar o traer un proceso a memoria principal y, si hay libre más de un bloque de memoria de tamaño suficiente, el sistema operativo debe decidir cuál asignar.

Los tres algoritmos de ubicación que se pueden considerar son el del mejor ajuste (best-fit), el del primer ajuste (first-fit) y el del siguiente ajuste (next-fit). Todos ellos se limitan a elegir entre los bloques de memoria libres que son mayores o iguales que el proceso a traer. El mejor ajuste elige el bloque de tamaño más parecido al solicitado. El primer ajuste comienza recorriendo la memoria desde el principio y escoge el primer bloque disponible que sea suficientemente grande. El siguiente ajuste recorre la memoria desde el lugar de la última ubicación y elige el siguiente bloque disponible que sea suficientemente grande.

La figura 6.5a muestra un ejemplo de configuración de la memoria después de cierto número de ubicaciones y operaciones de descarga de procesos. El último bloque usado fue de 22Kb, de donde se creó una partición de 14Kb. La figura 6.5b muestra la diferencia entre los algoritmos de ubicación del mejor, primer y siguiente ajuste para una solicitud de 16Kb. El mejor ajuste busca en la lista completa de bloques disponibles y emplea el hueco de 18Kb, dejando un fragmento de 2Kb. El primer ajuste genera un fragmento de 6Kb y el siguiente ajuste origina un fragmento de 20Kb.

Cuál de estos métodos es mejor dependerá de la secuencia exacta de intercambios de procesos que se den y del tamaño de estos procesos. Sin embargo, se pueden hacer algunos comentarios generales (pueden consultarse además [BAYS77], [BREN89] y [SHOR75]). El algoritmo del primer ajuste no sólo es el más sencillo, sino que normalmente es también el mejor y más rápido. El algoritmo del siguiente ajuste tiende a generar resultados algo peores que el del primer ajuste. El algoritmo del siguiente ajuste llevará frecuentemente a la asignación de bloques libres del final de la memoria. El resultado es que el bloque de memoria libre más grande, que suele aparecer al final del espacio de memoria, se divide rápidamente en fragmentos pequeños. Así pues, con el siguiente ajuste hará falta una compactación más frecuente. Por otro lado, el algoritmo del primer ajuste puede poblar el extremo inicial de pequeñas particiones libres que es necesario recorrer en las pasadas siguientes del algoritmo. El algoritmo del mejor ajuste, a pesar de su nombre, proporciona en general los peores resultados. Puesto que este algoritmo busca el hueco más pequeño que cumple con los requisitos, garantiza que el fragmento que se deja es lo más pequeño posible. Aunque cada solicitud de memoria desperdicia siempre la menor cantidad, el resultado es que la memoria principal se llena rápidamente de bloques demasiado pequeños como para satisfacer las solicitudes de asignación de memoria. Así pues, se debe compactar más frecuentemente que con los otros algoritmos.

Algoritmos de Reemplazo

En un sistema multiprogramado con particiones dinámicas, habrá algún momento en el que todos los procesos de memoria principal estén en estado bloqueado y la memoria sea insuficiente, incluso tras la compactación, para un proceso adicional. Para evitar desperdiciar el tiempo del procesador esperando a que un proceso activo se desbloquee, el sistema operativo expulsará uno de los procesos de memoria principal para hacer sitio a un proceso nuevo o un proceso Listo, pero suspendido. Por lo tanto, el sistema operativo debe elegir qué proceso reemplazar. Puesto que el tema de los algoritmos de reemplazo se cubre con mayor detalle en varios esquemas de memoria virtual, se aplazará la discusión de estos algoritmos hasta entonces.

Reubicación

Antes de considerar las formas de solucionar los defectos de las técnicas de partición, se debe aclarar un punto oscuro, que tiene relación con la ubicación de los procesos en memoria. Cuando se emplea el esquema de particiones fijas de la figura 6.3a, se puede esperar que un proceso sea asignado siempre a la misma partición. Es decir, la partición que se selecciona cuando se carga un nuevo proceso será la misma que se emplee siempre para devolver ese proceso a memoria, tras haber sido sacado. En este caso, se puede emplear un cargador sencillo, tal como se describe en el Apéndice 6A: Cuando el proceso se carga por primera vez, todas las referencias relativas a memoria en el código se reemplazan por direcciones absolutas de memoria principal, determinadas por la dirección base del proceso cargado.

En el caso de particiones de igual tamaño y en el caso de una cola única de procesos para particiones de distinto tamaño, un proceso puede ocupar diferentes particiones a lo largo de su vida. Cuando al principio se crea la imagen de un proceso, se cargará en alguna partición de memoria principal. Posteriormente, el proceso puede ser descargado; cuando, más tarde, vuelva a ser cargado, podrá asignársele una partición distinta de la anterior. Esto mismo se cumple con particiones dinámicas. Obsérvese en las figuras 6.4c y 6.4h que el proceso 2 ocupa dos regiones de memoria distintas en las dos ocasiones en las que se le trae a memoria. Es más, cuando se usa compactación, los procesos son desplazados durante su estancia en memoria principal.

Figura 6.6 Soporte de Hardware para la Reubicacion

Considérese ahora un proceso en memoria que incluya instrucciones y datos. Las instrucciones contendrán referencias a memoria de los dos tipos siguientes:

• Direcciones de elementos de datos, empleadas en instrucciones de carga, almacenamiento y en algunas instrucciones aritméticas y lógicas.
• Direcciones de instrucciones, empleadas para bifurcaciones e instrucciones de llamada.

Ahora se demostrará que estas instrucciones no son fijas, sino que cambian cada vez que se intercambia o desplaza un proceso. Para resolver este problema, se realiza una distinción entre varios tipos de direcciones. Una dirección lógica es una referencia a una posición de memoria independiente de la asignación actual de datos a memoria; se debe hacer una traducción a dirección física antes de poder realizar un acceso a memoria. Una dirección relativa es un caso particular de dirección lógica, en el cual la dirección se expresa como una posición relativa a algún punto conocido, habitualmente el comienzo del programa. Una dirección física o dirección absoluta, es una posición real en memoria principal.

Los programas que emplean direcciones relativas en memoria se cargan por medio de car-gadores dinámicos durante la ejecución (véase el estudio del Apéndice 6A). Esto significa que todas las referencias a memoria en el proceso cargado son relativas al origen del programa. Así pues, se necesita en el hardware un medio para traducir las direcciones relativas a direcciones físicas en memoria principal en el momento de la ejecución de la instrucción que contiene la referencia.

Cuando un proceso pasa a estado Ejecutando, se carga con la dirección en memoria principal del proceso un registro especial del procesador, a veces denominado registro base. Existe también un registro límite que indica la posición final del programa; estos valores deben asignarse cuando se carga el programa en memoria o cuando se carga la imagen del proceso. A lo largo de la ejecución del proceso se encuentran direcciones relativas. Estas direcciones incluyen los contenidos del registro de instrucción, las direcciones que aparecen en las instrucciones de bifurcación y llamada, y las direcciones de datos que aparecen en las instrucciones de carga y almacenamiento. Cada una de estas direcciones relativas pasa por dos etapas de manipulación en el procesador.

En primer lugar, se añade el valor del registro base a la dirección relativa para obtener una dirección absoluta. En segundo lugar, la dirección obtenida se compara con el valor del registro límite. Si la dirección está dentro de los omites, se puede proceder con la ejecución de la instrucción. En otro caso, se genera una interrupción al sistema operativo, que debe responder al error de algún modo.

El esquema de la figura 6.6 permite a los programas cargarse y descargarse de memoria a lo largo de la ejecución. También proporciona una medida de protección: Cada imagen de proceso está aislada por el contenido de los registros base y límite, y es segura contra accesos no desea-dos de otros procesos.

Paginación Simple

Tanto las particiones de tamaño fijo como las de tamaño variable hacen un uso ineficiente de la memoria; las primeras generan fragmentación interna, mientras que las segundas originan fragmentación externa. Supóngase, no obstante, que la memoria principal se encuentra particionada en trozos iguales de tamaño fijo relativamente pequeños y que cada proceso está dividido también en pequeños trozos de tamaño fijo y del mismo tamaño que los de memoria. En tal caso, los trozos del proceso, conocidos como páginas, pueden asignarse a los trozos libres de memoria, conocidos como marcos o marcos de página. En este apartado se verá que el espacio malgastado en memoria para cada proceso por fragmentación interna consta sólo de una fracción de la última página del proceso. Además, no hay fragmentación externa.

Continuando con el ejemplo, las cinco páginas del proceso D se cargan en los marcos 4, 5, 6, 11 y 12. La figura 6.8 muestra las distintas tablas de páginas en este instante. Cada tabla de páginas contiene una entrada por cada página del proceso, por lo que la tabla se indexa fácilmente por número de página (comenzando en la página 0). En cada entrada de la tabla de páginas se encuentra el número de marco en memoria, si lo hay, que alberga la página correspondiente. Además, el sistema operativo mantiene una lista de marcos libres con todos los marcos de memoria que actualmente están vacíos y disponibles para las páginas.

Así pues, se puede comprobar que la paginación simple, tal y como se describe, es similar a la partición estática. Las diferencias están en que, con paginación, las particiones son algo más pequeñas, un programa puede ocupar más de una partición y éstas no tienen por qué estar contiguas.

En el ejemplo (figura 6.9b), n=6 y m=10. Para la traducción de direcciones hay que dar los siguientes pasos:

• Obtener el número de página de los n bits más significativos de la dirección lógica.

• Emplear el número de página como índice en la tabla de páginas del proceso para encontrar el número de marco k.

• El comienzo de la dirección física del marco es k x 2^m y la dirección física del byte referenciado es este número más el desplazamiento. No hace falta calcular esta dirección física, sino que se construye fácilmente concatenando el número de marco con el desplazamiento.

Resumiendo, mediante la paginación simple, la memoria principal se divide en pequeños marcos del mismo tamaño. Cada proceso se divide en páginas del tamaño del marco; los procesos pequeños necesitaran pocas páginas, mientras que los procesos grandes necesitarán más. Cuando se introduce un proceso en memoria, se cargan todas sus páginas en los marcos libres y se rellena su tabla de páginas. Esta técnica resuelve la mayoría de los problemas inherentes a la partición.

Segmentación Simple

Otro modo de subdividir el programa es la segmentación. En este caso, el programa y sus datos asociados se dividen en un conjunto de segmentos. No es necesario que todos los segmentos de todos los programas tengan la misma longitud, aunque existe una longitud máxima de segmento. Como en la paginación, una dirección lógica segmentada consta de dos partes, en este caso un número de segmento y un desplazamiento.

Como consecuencia del empleo de segmentos de distinto tamaño, la segmentación resulta similar a la partición dinámica. En ausencia de un esquema de superposición o del uso de memoria virtual, sería necesario cargar en memoria todos los segmentos de un programa para su ejecución. La diferencia, en comparación con la partición dinámica, radica en que, con segmentación, un programa puede ocupar más de una partición y éstas no tienen por qué estar contiguas. La segmentación elimina la fragmentación interna, pero, como la partición dinámica, sufre de fragmentación externa. Sin embargo, debido a que los procesos se dividen en un conjunto de partes más pequeñas, la fragmentación externa será menor.

Mientras que la paginación es transparente al programador, la segmentación es generalmente visible y se proporciona como una comodidad para la organización de los programas y datos. Normalmente, el programador o el compilador asigna los programas y los datos a diferentes segmentos. En aras de la programación modular, el programa o los datos pueden ser divididos de nuevo en diferentes segmentos. El principal inconveniente de este servicio es que el programador debe ser consciente de la limitación de tamaño máximo de los segmentos.

Otra consecuencia del tamaño desigual de los segmentos es que no hay una correspondencia simple entre las direcciones lógicas y las direcciones físicas. De forma análoga a la paginación, un esquema de segmentación simple hará uso de una tabla de segmentos para cada proceso y una lista de bloques libres en memoria principal. Cada entrada de tabla de segmentos tendría que contener la dirección de comienzo del segmento correspondiente en memoria principal. La entrada deberá proporcionar también la longitud del segmento para asegurar que no se usan direcciones no válidas. Cuando un proceso pasa al estado Ejecutando, se carga la dirección de su tabla de segmentos en un registro especial del hardware de gestión de memoria. Para la traducción de direcciones hay que dar los siguientes pasos:

• Extraer el número de segmento de los n bits más significativos de la dirección lógica.
• Emplear el número de segmento como índice en la tabla de segmentos del proceso para encontrar la dirección física de comienzo del segmento.
• Comparar el desplazamiento, expresado por los m bits menos significativos, con la longitud del segmento. Si el desplazamiento es mayor que la longitud, la dirección no es válida.
• La dirección física buscada es la suma de la dirección física de comienzo del segmento más el desplazamiento.

En definitiva, con segmentación simple, un proceso se divide en varios segmentos que no tienen por qué ser del mismo tamaño. Cuando un proceso se introduce en memoria, se cargan todos sus segmentos en regiones de memoria libres y se rellena la tabla de segmentos.

Segmentación

Consecuencias de la Memoria Virtual

La segmentación permite al programador contemplar la memoria como si constara de varios espacios de direcciones o segmentos. Con memoria virtual, el programador no necesita pre-ocuparse de las limitaciones de memoria impuestas por la memoria principal. Los segmentos pueden ser de distintos tamaños, incluso de forma dinámica. Las referencias a memoria constan de una dirección de la forma (número de segmento, desplazamiento).

Esta organización ofrece al programador varias ventajas sobre un espacio de direcciones no segmentado:

1. Simplifica el manejo de estructuras de datos crecientes. Si el programador no conoce a priori cuan larga puede llegar a ser una estructura de datos determinada, es necesario suponerlo a menos que se permitan tamaños de segmento dinámicos. Con memoria virtual segmentada, a cada estructura de datos se le puede asignar a su propio segmento y el sistema operativo expandirá o reducirá el segmento cuando se necesite. Si un segmento necesita expandirse en memoria y no dispone de suficiente sitio, el sistema operativo puede mover el segmento a un área mayor de la memoria principal, si la hay disponible, o descargarlo. En este último caso, el segmento agrandado será devuelto a memoria en la siguiente ocasión.

2. Permite modificar y recompilar los programas independientemente, sin que sea necesario recompilar o volver a montar el conjunto de programas por completo. Esto se puede llevar nuevamente a cabo gracias al uso de varios segmentos.

3. Se presta a la compartición entre procesos. Un programador puede situar un programa de utilidades o una tabla de datos en un segmento que pueda ser referenciado por otros procesos.

4. Se presta a la protección. Puesto que un segmento puede ser construido para albergar un conjunto de procedimientos y datos bien definido, el programador o el administrador del sistema podrá asignar los permisos de acceso de la forma adecuada.

Unidad III – Normalización

Terminología relacional equivalente

Figura : Trabajo (Código, Nombre, Posición, Salario), donde Código es la Clave Primaria

• Regla = tabla o archivo
• Tupla =registro, fila o renglón
• Atributo = columnao campo
• Clave = llave o código de identificación
• Clave Candidata = superclave mínima
• Clave Primaria = clave candidata elegida
• Clave Ajena = clave externa o clave foránea
• Clave Alternativa = clave secundaria
• Dependencia Multivaluada = dependencia multivalor
• RDBMS = Del inglés Relational Data Base Manager System que significa, Sistema Gestor de Base de Datos.
  

Los términos Relación, Tupla y Atributo derivan de las matemáticas relacionales, que constituyen la fuente teórica del modelo de base de datos relacional.

Todo atributo en una tabla tiene un dominio, el cual representa el conjunto de valores que el mismo puede tomar. Una instancia de una tabla puede verse entonces como un subconjunto del producto cartesiano entre los dominios de los atributos. Sin embargo, suele haber algunas diferencias con la analogía matemática, dado que algunos RDBMS permiten filas duplicadas, entre otras cosas. Finalmente, una tupla puede razonarse matemáticamente como un elemento del producto cartesiano entre los dominios.

Claves

Una clave primaria es aquella columna (pueden ser también dos columnas o más) que identifica únicamente a esa fila. La clave primaria es un identificador que va a ser único para cada fila. Se acostumbra poner la clave primaria como la primera columna de la tabla pero esto no tiene que ser necesario, si no es más una conveniencia. Muchas veces la clave primaria es autonumérica.

En una tabla puede que tengamos más de una clave, en tal caso se puede escoger una para ser la clave primaria, las demás claves son las claves candidatas, además es la posible clave primaria.

Una clave foránea es aquella columna que existiendo como dependiente en una tabla, es a su vez clave primaria en otra tabla.

Una clave alternativa es aquella clave candidata que no ha sido seleccionada como clave primaria, pero que también puede identificar de forma única a una fila dentro de una tabla. Ejemplo: Si en un tabla clientes definimos el número de documento (id_cliente) como clave primaria, el número de seguro social de ese cliente podría ser una clave alternativa. En este caso no se usó como clave primaria porque es posible que no se conozca ese dato en todos los clientes.

Una clave compuesta es una clave que está compuesta por más de una columna.

Dependencia funcional

B es funcionalmente dependiente de A.

Una dependencia funcional es una conexión entre uno o más atributos. Por ejemplo si conocemos el valor de FechaDeNacimiento podemos conocer el valor de Edad.

Las dependencias funcionales del sistema se escriben utilizando una flecha, de la siguiente manera:

FechaDeNacimiento —->Edad

Aquí a FechaDeNacimiento se le conoce como un determinante. Se puede leer de dos formas FechaDeNacimiento determina a Edad o Edad es funcionalmente dependiente de FechaDeNacimiento. De la normalización (lógica) a la implementación (física o real) puede ser sugerible tener éstas dependencias funcionales para lograr la eficiencia en las tablas.

Propiedades de la Dependencia funcional

Existen 3 axiomas de Armstrong:

Dependencia funcional Reflexiva

Si “y” esta incluido en “x” entonces x —>y

Si la dirección o el nombre de una persona están incluidos en el CI, entonces con el C.I. podemos determinar la dirección o su nombre.

Dependencia funcional Aumentativa

x—> entonces xz —>yz

CI —–>nombre

ci,dirección—-> nombre,dirección

Si con la c.i. se determina el nombre de una persona, entonces con el C.I.  más la dirección también se determina el nombre o su dirección.

Dependencia funcional transitiva

Dependencia funcional transitiva.

Sean X, Y, Z tres atributos (o grupos de atributos) de la misma entidad. Si Y depende funcionalmente de X y Z de Y, pero X no depende funcionalmente de Y, se dice que Z depende transitivamente de X. Simbólicamente sería:

X —>Y—> Z entonces X—> Z

FechaDeNacimiento —> Edad

Edad —> Conducir

FechaDeNacimiento —> Edad —>Conducir

Entonces tenemos que FechaDeNacimiento determina a Edad y la Edad determina a Conducir, indirectamente podemos saber a través de FechaDeNacimiento a Conducir (En muchos países, una persona necesita ser mayor de cierta edad para poder conducir un automóvil, por eso se utiliza este ejemplo).

Normalización

La normalización es una técnica para diseñar la estructura lógica de los datos de un sistema de información en el modelo relacional, desarrollada por E. F. Codd en 1972. Es una estrategia de diseño de abajo a arriba: se parte de los atributos y éstos se van agrupando en relaciones (tablas) según su afinidad. Aquí no se utilizará la normalización como una técnica de diseño de bases de datos, sino como una etapa posterior a la correspondencia entre el esquema conceptual y el esquema lógico, que elimine las dependencias entre atributos no deseadas. Las ventajas de la normalización son las siguientes:

·        Evita anomalías en inserciones, modificaciones y borrados.

·        Mejora la independencia de datos.

·        No establece restricciones artificiales en la estructura de los datos.

Uno de los conceptos fundamentales en la normalización es el de dependencia funcional. Una dependencia funcional es una relación entre atributos de una misma relación (tabla). Si e son atributos de la relación, se dice que es funcionalmente dependiente de (se denota por) si cada valor de tiene asociado un solo valor de (e pueden constar de uno o varios atributos). A se le denomina determinante, ya que determina el valor de. Se dice que el atributo es completamente dependiente de si depende funcionalmente de y no depende de ningún subconjunto de .

La dependencia funcional es una noción semántica. Si hay o no dependencias funcionales entre atributos no lo determina una serie abstracta de reglas, sino, más bien, los modelos mentales del usuario y las reglas de negocio de la organización o empresa para la que se desarrolla el sistema de información. Cada dependencia funcional es una clase especial de regla de integridad y representa una relación de uno a muchos.

En el proceso de normalización se debe ir comprobando que cada relación (tabla) cumple una serie de reglas que se basan en la clave primaria y las dependencias funcionales. Cada regla que se cumple aumenta el grado de normalización. Si una regla no se cumple, la relación se debe descomponer en varias relaciones que sí la cumplan.

La normalización se lleva a cabo en una serie pasos. Cada paso corresponde a una forma normal que tiene unas propiedades. Conforme se va avanzando en la normalización, las relaciones tienen un formato más estricto (más fuerte) y, por lo tanto, son menos vulnerables a las anomalías de actualización. El modelo relacional sólo requiere un conjunto de relaciones en primera forma normal. Las restantes formas normales son opcionales. Sin embargo, para evitar las anomalías de actualización, es recomendable llegar al menos a la tercera forma normal.

A través del siguiente ejercicio se intenta afirmar los conocimientos de normalización con un ejemplo simplificado de una base de datos para una pequeña biblioteca.

CodLibro	Titulo	Autor	Editorial	NombreLector	FechaDev
1001	Variable compleja	Murray Spiegel	McGraw Hill	Pérez Gómez, Juan	15/04/2005
1004	Visual Basic 5	E. Petroustsos	Anaya	Ríos Terán, Ana	17/04/2005
1005	Estadística	Murray Spiegel	McGraw Hill	Roca, René	16/04/2005
1006	Oracle University	Nancy Greenberg y Priya Nathan	Oracle Corp.	García Roque, Luis	20/04/2005
1007	Clipper 5.01	Ramalho	McGraw Hill	Pérez Gómez, Juan	18/04/2005

Primera forma normal (1FN)

Una relación está en primera forma normal si, y sólo si, todos los dominios de la misma contienen valores atómicos, es decir, no hay grupos repetitivos. Si una relación no está en 1FN, hay que eliminar de ella los grupos repetitivos. Un grupo repetitivo será el atributo o grupo de atributos que tiene múltiples valores para cada tupla de la relación. Hay dos formas de eliminar los grupos repetitivos. En la primera, se repiten los atributos con un solo valor para cada valor del grupo repetitivo. De este modo, se introducen redundancias ya que se duplican valores, pero estas redundancias se eliminarán después mediante las restantes formas normales. La segunda forma de eliminar los grupos repetitivos consiste en poner cada uno de ellos en una relación aparte, heredando la clave primaria de la relación en la que se encontraban.

Una tabla está en Primera Forma Normal sólo si

• Todos los atributos son atómicos. Un atributo es atómico si los elementos del dominio son indivisibles, mínimos.
• La tabla contiene una clave primaria.
• La tabla no contiene atributos nulos.
• Si no posee ciclos repetitivos.

• A través del siguiente ejercicio se intenta afirmar los conocimientos de normalización con un ejemplo simplificado de una base de datos para una pequeña biblioteca.

La tabla mostrada anteriormente no cumple el requisito de la Primera Forma Normal (1NF) de sólo tener campos atómicos, pues el nombre del lector es un campo que puede (y conviene) descomponerse en apellido paterno, apellido materno y nombres.

1NF

CodLibro	Titulo	Autor	Editorial	Apellido Paterno	Apellido Materno	Nombres	FechaDev
1001	Variable compleja	Murray Spiegel	McGraw Hill	Pérez	Gómez	Juan	15/04/05
1004	Visual Basic 5	E. Petroustsos	Anaya	Ríos	Terán	Ana	17/04/05
1005	Estadística	Murray Spiegel	McGraw Hill	Roca		René	16/04/05
1006	Oracle University	Nancy Greenberg	Oracle Corp.	García	Roque	Luis	20/04/05
1006	Oracle University	Priya Nathan	Oracle Corp.	García	Roque	Luis	20/04/05
1007	Clipper 5.01	Ramalho	McGraw Hill	Pérez	Gómez	Juan	18/04/05

Segunda forma normal (2FN)

Una relación está en segunda forma normal si, y sólo si, está en 1FN y, además, cada atributo que no está en la clave primaria es completamente dependiente de la clave primaria.

La 2FN se aplica a las relaciones que tienen claves primarias compuestas por dos o más atributos. Si una relación está en 1FN y su clave primaria es simple (tiene un solo atributo), entonces también está en 2FN. Las relaciones que no están en 2FN pueden sufrir anomalías cuando se realizan actualizaciones.

Para pasar una relación en 1FN a 2FN hay que eliminar las dependencias parciales de la clave primaria. Para ello, se eliminan los atributos que son funcionalmente dependientes y se ponen en una nueva relación con una copia de su determinante (los atributos de la clave primaria de los que dependen).

Continuando con el ejemplo:

La Segunda Forma Normal (2NF) pide que no existan dependencias parciales o dicho de otra manera, todos los atributos no clave deben depender por completo de la clave primaria. Actualmente en nuestra tabla tenemos varias dependencias parciales si consideramos como atributo clave el código del libro.

Por ejemplo, el título es completamente identificado por el código del libro, pero el nombre del lector en realidad no tiene dependencia de este código, por tanto estos datos deben ser trasladados a otra tabla.

2FN

LIbros

CodLibro	Titulo	Autor	Editorial
1001	Variable compleja	Murray Spiegel	McGraw Hill
1004	Visual Basic 5	E. Petroustsos	Anaya
1005	Estadística	Murray Spiegel	McGraw Hill
1006	Oracle University	Nancy Greenberg	Oracle Corp.
1006	Oracle University	Priya Nathan	Oracle Corp.
1007	Clipper 5.01	Ramalho	McGraw Hill

La nueva tabla sólo contendrá datos del lector.

Lectores

CodLector	Paterno	Materno	Nombres
501	Pérez	Gómez	Juan
502	Ríos	Terán	Ana
503	Roca		René
504	García	Roque	Luis

Hemos creado una tabla para contener los datos del lector y también tuvimos que crear la columna CodLector para identificar unívocamente a cada uno. Sin embargo, esta nueva disposición de la base de datos necesita que exista otra tabla para mantener la información de qué libros están prestados a qué lectores. Esta tabla se muestra a continuación:

Prestamos

CodLibro	CodLector	FechaDev
1001	501	15/04/2005
1004	502	17/04/2005
1005	503	16/04/2005
1006	504	20/04/2005
1007	501	18/04/2005

Tercera forma normal (3FN)

Una relación está en tercera forma normal si, y sólo si, está en 2FN y, además, cada atributo que no está en la clave primaria no depende transitivamente de la clave primaria. La dependencia es transitiva si existen las dependencias, siendo, atributos o conjuntos de atributos de una misma relación.

Aunque las relaciones en 2FN tienen menos redundancias que las relaciones en 1FN, todavía pueden sufrir anomalías frente a las actualizaciones. Para pasar una relación de 2FN a 3FN hay que eliminar las dependencias transitivas. Para ello, se eliminan los atributos que dependen transitivamente y se ponen en una nueva relación con una copia de su determinante (el atributo o atributos no clave de los que dependen).

La tabla se encuentra en 3FN si es 2FN y cada atributo que no forma parte de ninguna clave, depende directamente y no transitivamente, de la clave primaria.

Además los atributos no clave deben ser mutuamente independientes y dependientes por completo de la clave primaria. También recordemos que dijimos que esto significa que las columnas en la tabla deben contener solamente información sobre la entidad definida por la clave primaria y, por tanto, las columnas en la tabla deben contener datos acerca de una sola cosa.

En nuestro ejemplo en 2NF, la primera tabla conserva información acerca del libro, los autores y editoriales, por lo que debemos crear nuevas tablas para satisfacer los requisitos de 3NF.

3NF

Libros

CodLibro	Titulo
1001	Variable compleja
1004	Visual Basic 5
1005	Estadística
1006	Oracle University
1007	Clipper 5.01

Autores

CodAutor	Autor
801	Murray Spiegel
802	E. Petroustsos
803	Nancy Greenberg
804	Priya Nathan
806	Ramalho

Editorial

CodEditorial	Editorial
901	McGraw Hill
902	Anaya
903	Oracle Corp.

Aunque hemos creado nuevas tablas para que cada una tenga sólo información acerca de una entidad, también hemos perdido la información acerca de qué autor ha escrito qué libro y las editoriales correspondientes, por lo que debemos crear otras tablas que relacionen cada libro con sus autores y editoriales.

CodLibro	codAutor
1001	801
1004	802
1005	801
1006	803
1006	804
1007	806

CodLibro	codEditorial
1001	901
1004	902
1005	901
1006	903
1007	901

Y el resto de las tablas no necesitan modificación.

CodLector	Paterno	Materno	Nombres
501	Pérez	Gómez	Juan
502	Ríos	Terán	Ana
503	Roca		René
504	García	Roque	Luis

CodLibro	CodLector	FechaDev
1001	501	15/04/2005
1004	502	17/04/2005
1005	503	16/04/2005
1006	504	20/04/2005
1007	501	18/04/2005

Reglas de Codd

Codd se percató de que existían bases de datos en el mercado las cuales decían ser relacionales, pero lo único que hacían era guardar la información en las tablas, sin estar estas tablas literalmente normalizadas; entonces éste publicó 12 reglas que un verdadero sistema relacional debería tener, en la práctica algunas de ellas son difíciles de realizar. Un sistema podrá considerarse “más relacional” cuanto más siga estas reglas.

Regla No. 1 – La Regla de la información

Toda la información en un RDBMS está explícitamente representada de una sola manera por valores en una tabla.

Cualquier cosa que no exista en una tabla no existe del todo. Toda la información, incluyendo nombres de tablas, nombres de vistas, nombres de columnas, y los datos de las columnas deben estar almacenados en tablas dentro de las bases de datos. Las tablas que contienen tal información constituyen el Diccionario de Datos. Esto significa que todo tiene que estar almacenado en las tablas.

Toda la información en una base de datos relacional se representa explícitamente en el nivel lógico exactamente de una manera: con valores en tablas. Por tanto los metadatos (diccionario, catálogo) se representan exactamente igual que los datos de usuario. Y puede usarse el mismo lenguaje (ej. SQL) para acceder a los datos y a los metadatos (regla 4)

Regla No. 2 – La regla del acceso garantizado

Cada ítem de datos debe ser lógicamente accesible al ejecutar una búsqueda que combine el nombre de la tabla, su clave primaria, y el nombre de la columna.

Esto significa que dado un nombre de tabla, dado el valor de la clave primaria, y dado el nombre de la columna requerida, deberá encontrarse uno y solamente un valor. Por esta razón la definición de claves primarias para todas las tablas es prácticamente obligatoria.

Regla No. 3 – Tratamiento sistemático de los valores nulos

La información inaplicable o faltante puede ser representada a través de valores nulos.

Un RDBMS (Sistema Gestor de Bases de Datos Relacionales) debe ser capaz de soportar el uso de valores nulos en el lugar de col