UNIVERSIDAD NACIONAL DE SAN

AGUSTIN
FACULTAD DE INGENIERIA DE
PRODUCCION Y SERVICIOS
Professional School Computer Science

BASE DE DATOS II

Algoritmos de Planificación de
Peticiones

Students: Teacher:
Barrios Cornejo, Selene Ing. Velazco Paredes
Garcia Diaz, German F. Yuber

Arequipa - Perú
1 Introducción
Cuando la unidad de disco está operando, el disco gira a una velocidad constante.
Para leer o escribir, la cabeza debe ponerse en la pista deseada, al comienzo del sector
pertinente. Si el sistema es de cabezas móviles hay que mover la cabeza para elegir
la pista. Si el sistema es de cabezas fijas, habrá que seleccionar electrónicamente
una de ellas.
Para ellos veremos los siguientes algoritmos que se utilizan para gestionar las
peticiones de acceso a disco que realizan los programas de aplicacioń y el sistema
operativo. Existen 4 algoritmos para gestionar las peticiones de acceso a disco:

• Primero en llegar , primero en ser servido o FIFO

• El mas cercano a la posición actual o SSTF.

• Algoritmo del elevador o SCAN

• Por exploración circular o C-SCAN

2 Planificación FIFO
La implementación de este algoritmo es simple, además, no necesita ningún apoyo
hardware especial, el sistema operativo debe mantener una lista de las páginas que
están en memoria, ordenada por el tiempo que llevan residentes. En el caso de una
estrategia local, se utiliza una lista por cada proceso. Cada vez que se trae una nueva
página a memoria, se pone a1 final de la lista. Cuando se necesita reemplazar, se
usa la página que está al principio de la lista.
Intuitivamente parece que cuantos más marcos de página haya en el sistema,
menos fallos de página se producirán, sin embargo, ciertos patrones de referencias
causan que este algoritmo tenga un comportamiento opuesto.

2.1 Ventajas
• Las solicitudes se procesan en un orden secuencial.

• Es una estrategia justa para todos los procesos.

• Esta técnica se parece mucho a la planificación aleatoria si hay muchos proce-

sos.

3 Planificación SSTF
Este supuesto es la base del algoritmo de tiempo de búsqueda más corto primero
(SSTF, shortest-seek-time-first), que selecciona la solicitud que tiene el menor tiempo
de búsqueda a partir de la posición actual de la cabeza.
 Los patrones de búsqueda SSTF tienden a estar muy relocalizados, dando como
resultado que las pistas internas y externas reciban un servicio pobre, en com-
paración con las pistas del centro. La SSTF es útil en sistemas de procesamiento
por lotes, en los cuales la capacidad de ejecución es lo más importante. Pero la alta
varianza de los tiempos de respuesta (es decir, su falta de predecibilidad) lo hace
inaceptable para los sistemas interactivos.

3.1 Ventajas
• Util en sistemas de procesamiento por lotes

• Mejora sustancialmente el desempeño.

4 Planificación SCAN
El brazo del disco parte de un extremo del disco y se mueve hacia el otro, atendi-
endo las solicitudes a medida que llega a cada cilindro, hasta llegar al otro extremo
del disco. Ahı́, la dirección de movimiento de la cabeza se invierte, y continúa la
atención. La cabeza barre continuamente el disco de un lado a otro.
El algoritmo SCAN también se conoce como algoritmo de elevador, ya que el
brazo del disco se comporta igual que el elevador de un edificio, que atiende primero
todas las solicitudes para subir y luego cambia de dirección para atender las solici-
tudes de bajar.

4.1 Ventajas
• Elimina las discriminaciones de SSTF y tiene menor varianza.

5 Planificación C-SCAN
La planificación SCAN circular (C-SCAN) es una variante de SCAN diseñada para
dar un tiempo de espera más uniforme. Al igual que SCAN, C-SCAN mueve la
cabeza de un extremo del disco al otro, atendiendo las solicitudes en el camino, sólo
que ahora, cuando la cabeza llega al otro extremo, regresa de inmediato al principio
del disco sin atender solicitudes.
En la estrategia C-SCAN, el brazo se mueve del cilindro exterior al interior,
sirviendo a las peticiones con menor tiempo de búsqueda. Cuando el brazo ha
completado su recorrido hacia adentro, salta a la petición más cercana al cilindro
exterior y a continuación reanuda su recorrido hacia adentro procesando peticiones.

5.1 Ventajas
• No discrimina a los cilindros exterior e interior.

• La varianza de los tiempos de respuesta es muy pequeña.

6 Objetivo
• Simular el funcionamiento del brazo de un disco duro en un lenguaje de pro-
gramación.

7 Simulación de planificación FIFO

• La simulación se realizo en C++.

• Se realizo una clase cola y una clase adicional llamada Disco para simulación
mediante uso de archivos.

• El archivo usado es [Link] , el cual fue creado en la misma dirección donde

se guarda el programa y la cual contiene 5 palabras que se extraen del archivo
de acuerdo a los numeros que ingresa el usuario.

• Los numeros ingresados por el usuario son las peticiones que se desencolan y
encolan.

c l a s s Disco
{
private :
string f i l e ;
public :
Disco ( ) ;
s t r i n g obtenerData ( i n t ) ;
};
Disco : : Disco ( )
{

}
s t r i n g D i s c o : : obtenerData ( i n t p o s i c i o n )
{
char cadena [ 1 2 8 ] ;
i f s t r e a m f e ( ” d i s c o . dat ” ) ;

w h i l e ( ! f e . e o f ( ) && p o s i c i o n != 0 ) {
f e >> cadena ;
p o s i c i o n −−;
}
// cout << cadena << e n d l ;

fe . close ();
s t r i n g s t r ( cadena ) ;
return str ;
}
c l a s s Nodo
{
private :
int info ;
Nodo ∗ s i g ;
f r i e n d c l a s s Cola ;
};
c l a s s Cola
{
public :
Nodo ∗ r a i z ;
Nodo ∗ fondo ;
public :
Cola ( ) ;
˜ Cola ( ) ;
void i n s e r t a r ( i n t x ) ;
int extraer ( ) ;
void imprimir ( ) ;
bool vacia ( ) ;
};

i n t main ( )
{
i n t rpt , da ;

D i s c o ∗ d i s c o 0 0= new D i s c o ( ) ;

Cola ∗ c o n s u l t a = new Cola ( ) ;

do
{
cout <<”D i g i t e numero : ” ;
c i n >>da ;
c o n s u l t a −>i n s e r t a r ( da ) ;
cout <<”\nDesea a g r e g a r o t r o elemento ( S i =1/No=0)”;
c i n >>r p t ;
}
w h i l e ( r p t ==1);
do
{
cout<< d i s c o 0 0 −>obtenerData ( c o n s u l t a −>e x t r a e r ())<< e n d l ;
}
w h i l e ( ! ( c o n s u l t a −>v a c i a ( ) ) ) ;
delete consulta ;
}
7.1 Archivo

Cada palabra tiene un número asignado , entonces el usuario ingresa numeros del
1 al 5 a la cola y deacuerdo a esos numeros , la palabra aparece en pantalla y se
extrae de la cola.

7.2 Programa en ejecución

8 Simulación de planificación SSTF

• Se realiza una cola de prioridad en la que tenemos 3 tareas en ejecución Word ,
Excel y Paint .Estas tres tareas se ejecutan en la computadora y estan dirigidas
para tres tipos de personas.

c l a s s Disco
{
public :
Disco ( )
{
 t i p o=rand ()%3+1; // Tipo de programa d e l 1 a l 3
p e r s o n a=rand ()%3+1;
tareas . resize (3);
t a r e a s [ 0 ] = ”Word ” ;
t a r e a s [ 1 ] = ” Excel ” ;
t a r e a s [ 2 ] = ” Paint ” ;
}
//PRIORIDADES PARA LA SIMULACION
int prioridad () const
{
s w i t c h ( t h i s −>t i p o )
{
case 1:
i f ( p e r s o n a==1) r e t u r n 1 ;
i f ( p e r s o n a==2) r e t u r n 2 ;
i f ( p e r s o n a==3) r e t u r n 3 ;
case 2:
return 4;
case 3:
return 5;
default :
break ;
}
}
//VALIDAR DATOS Y VERIFICAR DATOS
s t r i n g toString () const
{
stringstream s ;
s<<”Tipo:”<< t i p o << e n d l ;
s<<”Persona:”<< persona <<e n d l ;

s<<”Tareas :”<< e n d l ;

f o r ( i n t i =0; i <t a r e a s . s i z e ( ) ; i ++)

{
s <<”∗ ”<<t a r e a s [ i ]<< e n d l ;
}

s <<” ”<<e n d l ;
return s . str ( ) ;
}

i n t t i p o ; // 1 URGENTE 2 NORMAL 3 PUEDE ESPERAR

i n t p e r s o n a ; // 1 NINO 2 ADOLESCENTE 3 ADULTO
v e c t o r <s t r i n g > t a r e a s ;
};
//SOBRECARGA DE OPERADORES YA
QUE LA PRIORIDAD ESTA BASADA EN DOS INDICES
b o o l o p e r a t o r <( c o n s t D i s c o& l r , c o n s t D i s c o& r r )
{
return l r . prioridad () > rr . prioridad ( ) ;
}

b o o l o p e r a t o r >( c o n s t D i s c o& l r , c o n s t D i s c o& r r )

{
r e t u r n l r . p r i o r i d a d ()< r r . p r i o r i d a d ( ) ;
}

i n t main ( )
{
p r i o r i t y q u e u e <Disco> c o l a P r i o r i d a d ;
f o r ( i n t i =0; i <6; i ++)
{
c o l a P r i o r i d a d . push ( D i s c o ( ) ) ;
}

w h i l e ( ! c o l a P r i o r i d a d . empty ( ) )
{
cout<<c o l a P r i o r i d a d . top ( ) . t o S t r i n g ( ) ;
c o l a P r i o r i d a d . pop ( ) ;
}
}

9 Programa en funcionamiento
 Se realizo 6 veces la ejecución del programa y obtuvimos los resultados que obten-
emos en pantalla.
• Con prioridad urgente , un niño necesita usar las aplicaciones de Word,Excel
y Paint .
• Con prioridad normal , un adolescente necesita usar las aplicaciones antes
mencionadas y asi.

10 Simulación de planificación SSTF

c l a s s SSF
{
public :
v e c t o r <i n t > L i s t a ;
v e c t o r <i n t > R e s u l t ;
v e c t o r <bool> v i s i t ;
int recorrido ;
i n t tam ;
i n t pos ;
public :
SSF ( i n t x , i n t b ){
r e c o r r i d o =0;
pos=x ;
tam=b ;
f o r ( i n t i =0; i <b−1; i ++){
 v i s i t . push back ( f a l s e ) ;
}
}
v o i d a g r e g a r ( i n t a ){
i f ( tam>=a ){
v i s i t [ a]= t r u e ;
L i s t a . push back ( a ) ; }
cout<<a<<e n d l ;
}
v o i d Mov( ) {
i n t mini =999;
i n t v a l =0;
f o r ( i n t i =0; i <L i s t a . s i z e ( ) + 1 ; i ++){
f o r ( i n t j =0; j <L i s t a . s i z e ( ) ; j ++){
i n t t e s t=L i s t a [ j ] ;
i f ( v i s i t [ t e s t ]== t r u e ){
i f ( mini>=abs ( t e s t −pos ) ) {
v a l=L i s t a [ j ] ;
mini=abs ( L i s t a [ j ]− pos ) ;
}
}
}
v i s i t [ v a l ]= f a l s e ;
R e s u l t . push back ( pos ) ;
pos=v a l ;
r e c o r r i d o+=mini ;
mini =999;
}
r e c o r r i d o=r e c o r r i d o −999;

};
10.1 Programa en ejecución

11 Simulación de planificación C-SCAN

c l a s s CSCAN
{
public :
v e c t o r <i n t > L i s t a ;
v e c t o r <i n t > R e s u l t ;
v e c t o r <bool> v i s i t ;
int recorrido ;
i n t tam ;
i n t pos ;
public :
CSCAN( i n t x , i n t b ){
r e c o r r i d o =0;
pos=x ;
tam=b ;
f o r ( i n t i =0; i <b−1; i ++){
v i s i t . push back ( f a l s e ) ;
}
v i s i t [ pos ]= v i s i t [ 0 ] = v i s i t [ tam−1]= t r u e ;
}
v o i d agregarC ( i n t a ){
i f ( tam>=a ){
v i s i t [ a]= t r u e ;
L i s t a . push back ( a ) ; }
cout<<a<<e n d l ;
}
v o i d MovC( ) {
 f o r ( i n t i=pos ; i <tam+1; i ++){
i f ( v i s i t [ i ]== t r u e ){
R e s u l t . push back ( i ) ;
v i s i t [ i ]= f a l s e ;
}
r e c o r r i d o=r e c o r r i d o +1;
}
f o r ( i n t i =0; i <pos ; i ++){
i f ( v i s i t [ i ]== t r u e ){
R e s u l t . push back ( i ) ;
v i s i t [ i ]= f a l s e ;
}
r e c o r r i d o=r e c o r r i d o +1;
}
}

};
11.1 Programa en ejecución

11.2 Bibliografı́a
• [Link]
• [Link]
• [Link]