Metodo ROY

  1. Elemento Metodo RoyCódigo de Actividad
  2. Tiempo Mínimo de Comienzo
  3. Tiempo Máximo de Comienzo
  4. Duración de la Actividad

Relación elementos método RoyRelación Comienzo\Comienzo si D<8 (8=Duración de la actividad predecesora)

Tiempo Mínimo = es el mayor de las sumas de los tiempos mínimos anteriores mas el valor del arco.
Tiempo Máximo = elegir la menor (Porque es el tiempo maximo en el que puede acabar un actividad)

Holgura Total (Cuadrado) Diferencia entre los tiempos máximo y mínimo.

Calculo Holgura Total RoyHolgura Libre (Triangulo) El mínimo de (Tiempo mínimo de actividad siguiente – (Tiempo Mínimo de esa actividad+ Valor del Arco))

Calculo de Holgura Libre RoyNunca olvidar esto

Esquema grafo ROYSi n>=D -> Final Comienzo con demora = n-D
Si n<D ->Comienzo Comienzo con demora = n

Las Demoras de Roy
Si el valor del arco es mayor o igual que la duración de la actividad la relacion sera Final Comienzo con demora =n-D
Si el valor del arco es menor que la duración de la actividad la relación sera Comienzo Comienzo con demora = n

Run-Lenght Encoding

La compresión RLE se basa en alacenar las repeticiones c0nsecutivas de los valores que componen un fichero. se usa un contador del numero de repeticiones y el valor que se repite.

Contador de repeticiones – Datos a Repetir

Se puede observar mejor en el siguiente ejemplo:

A A B B B B B C C C C D B B B E F F (18 bytes)

2 A 5 B 4 C 1 D 3 B 1 E 2 F (14 bytes)

Existes formatos que utilizan el Run-Lenght enconding como pueden ser:

  • MacPaint: Usa PackBits (Una variante de Run-Length Encoding) con rangos de valores para el indicador de repeticiones entre [-1,127]
    • Si el valor del indicador de repeticiones esta entre [0,127] indica que los siguientes (indicador de repeticiones +1) bytes son literales
    • Si el valor del indicador de repeticiones esta entre [-127,-1] indica que el siguiente byte se repite (-1*indicador de repeticiones +1 ) veces
    • Veamoslo en el siguiente ejemplo:
    • 5 5 14 14 14 14 14 8 8 8 8 7 3 2 5 5 5
    • [-1] 5 [-4] 14 [-3] 8 [2] 7 3 2 [-2] 5
  • PCX: Utiliza los dos primeros bits de mayor peso de cada byte para diferenciar entre indicadores de repeticiones y datos
    • Si ambos bits son 1 [11XXXXXXX] indica que es un indicador de repeticiones siendo XXXXXX el numero de veces que se repite el siguiente byte
    • Para el resto de los casos [00XXXXXX],[01XXXXXX] y [10XXXXXX]  son valores literales veamoslo en el siguiente ejemplo
    • 5 5 255 254 17 255 255 255 255
    • 11000011 5 11000001 255 1100001 254 17 11000100 255
    • el código 1100001 afecta a los valores 254 17
  • Targa y TIFF

Exame ETC setembro 2009

1)Un procesador manexa unha memoria de 256Mx64. ¿Cál deberia ser o tamaño do rexistro contador de programa, PC?

  • 28
  • 24
  • 32
  • Todas as afirmacións citadas son incorrectas

256M= 2⁸M=2⁸*2²⁰=2²⁰ =2²⁸

2) Dada a seguinte situacion para o 8085:
SP=150h
B-C= 2A65h
D-E= B34Ch
H-L= 4F45h
Despois de realizar as instruccións:
PUSH D; PUSH B; PUSH H;
¿Cal sera o contido da direccion de memoria 014Ch?

  • 4Fh
  • 2Ah
  • 65h
  • Ningunha das respostas anteriores é correcta

Despues de realizar la simulación (Codigo Simulación Stack) el contenido de la memoria es el siguiente:

;<Simulación Stack>
jmp start
;data
;code
start: mvi H,01h
MVI L,50h
SPHL
MVI B,2Ah
mvi C,65h
mvi D,179
mvi E,4Ch
mvi H,4Fh
mvi L,45h
push d
push b
push h
mvi h,01h
mvi l,4Ch
mov a,M
hlt

  • 014F B3 (D)
  • 014E 4C (E)
  • 014D 2A (B)
  • 014C 65 (C)
O sumador binario completo tarda 12ns en facer a suda de 2 operandos de 1 bit. ¿Cánto tardaría un suamdr paralelo para operandos de 32 bits?
120ns
384ns V
284ns
Depende do tempo de propagación do acarreo

3) O sumador binario completo tarda 12ns en facer a suda de 2 operandos de 1 bit. ¿Cánto tardaría un suamdr paralelo para operandos de 32 bits?

  • 120ns
  • 384ns
  • 284ns
  • Depende do tempo de propagación do acarreo

32bits*12ns=384

4) Na instruccion da maquina 8085: MOV M,C ¿Que tipo de direccionamento leva o operando Destino?

  • Directo
  • Indirecto a parella de rexistros
  • Por rexistro
  • Ningunha das respostas anteriores é correcta

O rexistro M obtense pola dirección apuntada por HL

5) O tamaño do Rexistro de estado, de sinalizadores, ou de flags (RF)

  • Ten o mesmo tamaño que o bus de direccions
  • Ten o mesmo tamaño que a palabra que manexa o procesador
  • Ten un tamaño de 2^n, sendo n o número de sinalizadores do RF
  • Ningunha das respostas anteriores é correcta

6) Un procesador A ten unha f=4MHz e un CPI=8 outro procesador B ten unha f=8Mhz e un CPI=4. pon unha X na resposta correcta

  • Ambos teñen a mesma velocidade
  • O procesador A é máis rápido que o B
  • O procesador B é máis rápido que o A
  • Faltan datos para contestar a pregunta
Calculo do numero de instruccions que executa un procesador
Calculo do numero de instruccions que executa un procesador

7)Sabendo que o contido dos rexistros A=7Ah, D=37h, E=7Ch, F=2Eh e que o das posicions de memoria coincida coa parte da sua propia dirección, indicar o contido final de A e F despois de executar a instruccion: LDAX D

  • A=7Ch F=2Eh
  • A=37h F=2Eh
  • A=7Ch F=7Ah
  • Ningunha das respostas anteriores é correcta

8)¿En cal dos seguintes casos, o ancho de palabro ou tamaño das posicions de memoria de control (MC) é maior?

  • Nunha MC microprogramada con secuenciamento explícito
  • Nunha MC microprogramada con secuenciamento implícito
  • É igual en ámbalas dúas
  • Ningunha das respostas anteriores é correcta

No secuenciamento explicito debese de indicar cal sera a  dirección da seguinte instrucción a executar, no implicito non

9)¿Cantos bloques de memoria de 16Kx8 se necesitan para formar unha memoria de 32Kx32?

  • 4
  • 8
  • 16
  • Ningunha das respostas anteriores é correcta

32*32=1024 | 16*8=128 | 1024/128=8

10)Dada a seguinte instruccion da maquina 8085: STA 6B42 ¿Cál será a súa codificación, expresada en notación hexadecimal?

  • 3A6B42h
  • 326B42h
  • 32426Bh
  • Ningunha das respostas anteriores é correcta

Manifiesto «En defensa de los derechos fundamentales en internet»

Ante la inclusión en el Anteproyecto de Ley de Economía sostenible de modificaciones legislativas que afectan al libre ejercicio de las libertades de expresión, información y el derecho de acceso a la cultura a través de Internet, los periodistas, bloggers, usuarios, profesionales y creadores de internet manifestamos nuestra firme oposición al proyecto, y declaramos que…

1.- Los derechos de autor no pueden situarse por encima de los derechos fundamentales de los ciudadanos, como el derecho a la privacidad, a la seguridad, a la presunción de inocencia, a la tutela judicial efectiva y a la libertad de expresión.

2.- La suspensión de derechos fundamentales es y debe seguir siendo competencia exclusiva del poder judicial. Ni un cierre sin sentencia. Este anteproyecto, en contra de lo establecido en el artículo 20.5 de la Constitución, pone en manos de un órgano no judicial -un organismo dependiente del ministerio de Cultura-, la potestad de impedir a los ciudadanos españoles el acceso a cualquier página web.

3.- La nueva legislación creará inseguridad jurídica en todo el sector tecnológico español, perjudicando uno de los pocos campos de desarrollo y futuro de nuestra economía, entorpeciendo la creación de empresas, introduciendo trabas a la libre competencia y ralentizando su proyección internacional.

4.- La nueva legislación propuesta amenaza a los nuevos creadores y entorpece la creación cultural. Con Internet y los sucesivos avances tecnológicos se ha democratizado extraordinariamente la creación y emisión de contenidos de todo tipo, que ya no provienen prevalentemente de las industrias culturales tradicionales, sino de multitud de fuentes diferentes.

5.- Los autores, como todos los trabajadores, tienen derecho a vivir de su trabajo con nuevas ideas creativas, modelos de negocio y actividades asociadas a sus creaciones. Intentar sostener con cambios legislativos a una industria obsoleta que no sabe adaptarse a este nuevo entorno no es ni justo ni realista. Si su modelo de negocio se basaba en el control de las copias de las obras y en Internet no es posible sin vulnerar derechos fundamentales, deberían buscar otro modelo.

6.- Consideramos que las industrias culturales necesitan para sobrevivir alternativas modernas, eficaces, creíbles y asequibles y que se adecuen a los nuevos usos sociales, en lugar de limitaciones tan desproporcionadas como ineficaces para el fin que dicen perseguir.

7.- Internet debe funcionar de forma libre y sin interferencias políticas auspiciadas por sectores que pretenden perpetuar obsoletos modelos de negocio e imposibilitar que el saber humano siga siendo libre.

8.- Exigimos que el Gobierno garantice por ley la neutralidad de la Red en España, ante cualquier presión que pueda producirse, como marco para el desarrollo de una economía sostenible y realista de cara al futuro.

9.- Proponemos una verdadera reforma del derecho de propiedad intelectual orientada a su fin: devolver a la sociedad el conocimiento, promover el dominio público y limitar los abusos de las entidades gestoras.

10.- En democracia las leyes y sus modificaciones deben aprobarse tras el oportuno debate público y habiendo consultado previamente a todas las partes implicadas. No es de recibo que se realicen cambios legislativos que afectan a derechos fundamentales en una ley no orgánica y que versa sobre otra materia.

Este manifiesto, elaborado de forma conjunta por varios autores, es de todos y de ninguno. Si quieres sumarte a él, difúndelo por Internet.

Practica 3 ASO

1. (Kernel Lista) Modifica la cabecera “include/linux/list.h” del kernel para que se pueda

utilizar en un programa de usuario. Escribe un programa que utiliza las funciones de listas enlazadas dentro de list.h para:

  • insertar números aleatorios.
  • recorrer la lista imprimiendo los valores.
  • eliminar un nodo de la lista (utilizando un menú de selección).

2. (Simulador de Procesos) En este problema, queremos estudiar el efecto de diferentes
parámetros relacionado con “timeslice” a diferentes algoritmos de planificación. Escribe un
programa que es simula el comportamiento del gestor de planificación con diferentes valores
de timeslice y para diferentes cargas de cambio de contexto de procesos. Para ello debe
seguir los siguientes pasos:
a) Utilizando su libraría de funciones que ha creado en practicas anteriores, genera los
siguientes datos para procesos que van a querer utilizar el CPU: (i) el PID de cada
procesos, un número aleatorios que representa el tiempo de llegada, y un numero
aleatorio que representa el tiempo total que va a ejecutar en el CPU. Como ejemplo,
los números puede ser como las siguientes:
PID T_llegada            T_total
1        30      0.783560
2         54     17.282004
3         97     32.814522
Que significa que el primer proceso llega a 30 segundos y quiere 0.783560 segundos para ejecutar, el segundo proceso llega a t=54 segundos y necesita 17.28 segundos para ejecutar, ect.
b) Escribe un función que dado los valores generado, es capaz de contar el timeslice y
utilizar planificación de “preemption”, si necesario, para intercambiar procesos cuando
el timeslice de un proceso se agota.
c) Escribe un algoritmo de político “Round Robin”.
d) Escribe un función que calcula el tiempo media de espera y el tiempo media de la tasa de terminar para todos los procesos.
e) Ejecuta su simulación para tiempos de sobrecargo de cambio de contexto de 0, 5, 10, 15, 20 y 25 milisegundos; y por valores de timeslice de: 50, 100, 250, y 500
milisegundos. Hacer gráficos (plots) de lo que encuentras.

Lo primero que tenemos que hacer es copiar la libreria list.h a un archivo nuevo (el kernel de linux no esta en C estándar) y compilar para ver si lo acepta.

Al primer intento nos va a decir que no por las librerías así que tendremos que borrarlas del código

//#include <linux/poison.h>
//#include <linux/prefetch.h>
//#include <asm/system.h>

Volvemos a compilar y tenemos problemas con las variables LIST_POISON esto se produce en las siguientes dos funciones:

  • funcion1

static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
//entry->next = LIST_POISON1;
//entry->prev = LIST_POISON2;
}

  • funcion2

static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n);
//n->next = LIST_POISON1;
//n->pprev = LIST_POISON2;
}

Así  ya nos compila el código.

El uso de las listas del kernel difiere del uso clásico que tenemos en mente.

Diagrama clasico de la estructura de una lista
Diagrama clásico de la estructura de una lista

aquí tenemos el esquema de uso de una kernel list

comportamiento de una kernel list
comportamiento de una kernel list

la principal diferencia es que los enlaces de la lista son una estructura dentro de nuestra estructura, por lo tanto no nos movemos a través de nuestra lista sino que vamos accediendo a partes internas de la lista. El principal problema de utilizar este método es acceder a la estructura que contiene los enlaces, esto se realiza mediante el calculo del offset de un puntero.

/*
* getCustomListPointer — gets the customlist memory address from a listPointer calculating the offsett
* listPointer — a pointer that point a list element
*/

struct customList *getCustomListPointer(struct list_head *listPointer)//DONE
{
void * toret=NULL;
toret=listPointer;
//We use a void pointer because i can’t sobrem problems with pointers aritmetic
toret= (toret – ((unsigned long) &((struct customList *)0)->list));
return toret;
}

Toret es un puntero a  void para evitar problemas en la aritmética de punteros, si este fuera un char puntero -1 seria iguar a puntero -1(tamaño char) por lo que tendríamos problemas de fallo de segmento.

La estructura del código se puede observar en el siguiente esquema:

Organización del simulador de procesos
Organización del simulador de procesos

Existen unos pequeños bugs y características no implementadas en la aplicación

  • El iterador usa variable global que puede sufrir efectos laterales (las funciones copyCustomList tiene el problema arreglado al ser recursivas y utilizar un registro como indicador de fin de recursividad)
  • Habría que mirar el tamaño de una variable void* (si es >1 produce segmentation fault por mal calculo de offset)
  • Añadir elemento y otras funciones no esta implementado solo seria añadir una sucesión de printf y scanf en el código.
  • No esta implementado el paso de parámetros como por ejemplo establecer el numero de procesos que se simularan (cambiar 15000, por una variable en linea 113 de main.c)
Codigo Fuente
Codigo Fuente

Funcionamiento:

La ejecución muestra por pantalla los datos de cada proceso, timeslice y contextChangue según termina cada proceso,  se ha definido un conjunto de 15000 procesos para sacar estadísticas.

Los ejecución recomendada es ./ejecutable> salida.cvs siendo salida.cvs un archivo comma separated values que se importara a mysql para realizar calculos de forma mas sencilla. La definición de la tabla que se usara esta en el siguiente enlace (Database struct Definitión)

Una vez obtenida la salida la importación a MySql se realiza ejecutando un orden similar a esta.

LOAD DATA LOCAL INFILE’/home/luzem/NetBeansProjects/Practica3/dist/Debug/GNU-Linux-x86/salida.csv’
INTO TABLE roundrobin
FIELDS TERMINATED BY ‘,’
LINES TERMINATED BY ‘\n’

Con esto y un conjunto de consultas SQL podemos obtener los datos para procesar en GNUPLOT.

Gráficas

ContextChangue effects
Como Afecta el ContextChangue en la media global

En  la anterior gráfica podremos ver los efectos del incremento del contextChangue sobre el tiempo medio de espera, observando como el impacto es independiente del timeslice.

Tiempo medio de espera
Tiempo medio de espera

El tiempo medio de espera de cada proceso aumenta en función de timeslice y dada que la diferencia entre timeslice y contextchangue es muy alta es el aumento del timeslice quien castiga mas a los tiempos de espera.

En cambio si tenemos en cuenta la media del tiempo total de espera para los conjuntos de timeslice y contextchangue obtenemos la siguiente media

Impacto sobre el la media del tiempo total de espera
Impacto sobre el la media del tiempo total de espera

Cuando el timeslice es muy pequeño el numero de cambios de contexto aumenta penaliza el tiempo total de espera de una forma mas que considerable.

Si extraemos el 15% inicial y el 15% final y calculamos las medias para cada segmento obtenemos las siguiente grafica

Differences between short long process
Differences between short long process

En la anterior gráfica observamos que el impacto sobre la media de tiempo de espera, afecta mayormente a la parte central del conjunto de procesos.

Mejoras:

Utilizar varias listas round robin con diferente timeslice  y mover los elementos customList en función del contador de paradas (timeslice grande para procesos largos y timeslice pequeño para procesos cortos)