Mudanças entre as edições de "ADS29009-2019-1"

De MediaWiki do Campus São José
Ir para navegação Ir para pesquisar
Linha 352: Linha 352:
 
*Implementação do Simulador a Eventos Discretos para Fila MM1
 
*Implementação do Simulador a Eventos Discretos para Fila MM1
 
*Geração de Números Randômicos na Simulação
 
*Geração de Números Randômicos na Simulação
 +
 +
==Material de Referência==
 +
 +
https://www.dropbox.com/s/c221v4hlfdrpc1n/GeracaoNumerosRandomicosSimulacao.pdf?dl=0
 +
 +
<!--
 +
<syntaxhighlight lang=c>
 +
//Basead em http://stdcxx.apache.org/doc/stdlibug/2-2.html#225
 +
 +
#include <queue>
 +
#include <iostream>
 +
#include <cstdlib>
 +
#include <math.h>
 +
#include <queue>
 +
 +
 +
#define IDLE 0
 +
#define ACTIVE 1
 +
#define MAX_EVENTS 10
 +
#define MAX_SIMTIME 100
 +
 +
//==================================================================
 +
// classes evento e simulação - base para o desenvolvimento da simulação
 +
//==================================================================
 +
 +
class event {
 +
public:
 +
  // Construct sets time of event.
 +
  event (double t) : time (t)
 +
    { }
 +
 +
  // Execute event by invoking this method.
 +
  virtual void processEvent () = 0;
 +
 +
  const double time;
 +
};
 +
 +
 +
class simulation {
 +
public:
 +
  simulation () : simtime (0), eventQueue ()
 +
  {
 +
    num_events = 0; 
 +
  }
 +
  void run ();
 +
  void  scheduleEvent (event * newEvent) {
 +
    eventQueue.push (newEvent);
 +
  }
 +
  double simtime;
 +
protected:
 +
  int num_events;
 +
  class eventComparator {
 +
    public:
 +
    bool operator() (const event * left, const event * right) const {
 +
      return left->time > right->time;
 +
    }
 +
  };
 +
  std::priority_queue<event*,
 +
                      std::vector<event *, std::allocator<event*> >,
 +
                      eventComparator> eventQueue;  //fila de eventos
 +
};
 +
 +
void simulation::run () {
 +
 +
  while (! eventQueue.empty () && simtime < MAX_SIMTIME) { //enquanto exisitr eventos na fila de eventos
 +
 +
    event * nextEvent = eventQueue.top (); //captura evento no topo da fila
 +
    eventQueue.pop ();  //retira evento da fila
 +
    simtime = nextEvent->time;  //ajusta tempo de simulação
 +
    nextEvent->processEvent ();  //processa evento
 +
    delete nextEvent;  //remove evento
 +
  }
 +
}
 +
 +
//===================================================================
 +
// Gerador de números randômicos baseado na técnica linear congruente
 +
//===================================================================
 +
 +
#define PAR_A 1103515245
 +
#define PAR_C 12345
 +
#define PAR_M 2147483648
 +
 +
class mRND {
 +
  public:
 +
  void seed(unsigned long s)
 +
  {
 +
    _seed = s;
 +
  }   
 +
  unsigned long get_m(){return _m;};
 +
  int rnd()
 +
  {
 +
    return (_seed = (_a * _seed + _c) % _m);
 +
  }
 +
  mRND(unsigned long s, unsigned long parA, unsigned long parC, unsigned long parM) : _seed(s), _a(PAR_A), _c(PAR_C), _m(PAR_M)
 +
  {
 +
  }
 +
  mRND(unsigned long s) : _seed(s), _a(PAR_A), _c(PAR_C), _m(PAR_M)
 +
  {
 +
  }
 +
  mRND() : _seed(0), _a(PAR_A), _c(PAR_C), _m(PAR_M)
 +
  {
 +
  }
 +
  protected:
 +
  unsigned long _a, _c;
 +
  unsigned long _m, _seed;
 +
};
 +
 +
class rngExp {
 +
public:
 +
    rngExp(double vseed, double vlambda);
 +
    double exp1();
 +
    double exp2();
 +
private:
 +
    unsigned int seed;
 +
    double lambda;
 +
    class mRND rng;
 +
};
 +
 +
 +
rngExp::rngExp(double vseed,  double vlambda) : rng(vseed), seed(vseed), lambda(vlambda)
 +
{
 +
}
 +
 +
double rngExp::exp1() {
 +
  double r = ((double)rand_r(&seed) / (RAND_MAX));
 +
  return  (-(1/lambda) * (log(1 - r)));
 +
}
 +
 +
double rngExp::exp2() {
 +
  double r = ((double)rng.rnd() / rng.get_m());
 +
  return  (-(1/lambda) * (log(1 - r)));
 +
 +
}
 +
 +
 +
 +
 +
class simuladorFilas : public simulation {
 +
public:
 +
  simuladorFilas (unsigned seed_arrival, double lambda_arrival, unsigned seed_dep, double lambda_dep) :
 +
      rngArrival(seed_arrival, lambda_arrival), rngService(seed_dep, lambda_dep), server_state(IDLE)
 +
    { }
 +
  rngExp rngArrival,
 +
        rngService;
 +
  int getServerState(){return server_state;};
 +
  int setServerState(int state){server_state=state;};
 +
  void pushQueue(event *x){myqueue.push(x);};
 +
  bool emptyQueue(){return myqueue.empty();}
 +
  int  sizeQueue(){return myqueue.size();}
 +
  class event *getFrontAndPopQueue(){
 +
      event *p = myqueue.front();
 +
        myqueue.pop();
 +
      return p;
 +
  }
 +
private:
 +
  std::queue<event*> myqueue;
 +
  int server_state;
 +
 +
}oSimulador(10,70,15,100);
 +
 +
 +
//===================================================================
 +
//Customização dos eventos e do simulador
 +
//===================================================================
 +
 +
 +
class standardArrival : public event {
 +
public:
 +
  standardArrival(standardArrival *p): event(p->time)
 +
    {
 +
      enqueueTime = p->enqueueTime;
 +
    }
 +
  standardArrival (double creationTime)
 +
    : event (creationTime)
 +
    { }
 +
  virtual void processEvent ();
 +
protected:
 +
    double enqueueTime;
 +
    class standardArrival* clone() { return new standardArrival(this); }
 +
};
 +
 +
class standardService : public event {
 +
public:
 +
  standardService (double t)
 +
    : event (t)
 +
    { }
 +
  virtual void processEvent ();
 +
};
 +
 +
 +
void standardArrival::processEvent ()
 +
{
 +
  std::cout << "ARRIVAL: processando evento no tempo " << time  << '\n';
 +
    if (oSimulador.getServerState()==IDLE) {
 +
        oSimulador.setServerState(ACTIVE);
 +
        oSimulador.scheduleEvent (new standardService(oSimulador.rngService.exp2()+oSimulador.simtime));
 +
    } else {
 +
        enqueueTime = oSimulador.simtime;
 +
        oSimulador.pushQueue(this->clone());
 +
    }
 +
    oSimulador.scheduleEvent (new standardArrival(oSimulador.rngArrival.exp2()+oSimulador.simtime));
 +
}
 +
 +
 +
void standardService::processEvent () {
 +
  std::cout << "SERVICE:processando evento no tempo " << time  << '\n';
 +
  if (oSimulador.emptyQueue()) {
 +
    oSimulador.setServerState(IDLE);
 +
  } else{
 +
    class standardArrival *p = (class standardArrival *) oSimulador.getFrontAndPopQueue();
 +
    delete p;
 +
    oSimulador.scheduleEvent (new standardService(oSimulador.rngService.exp2()+oSimulador.simtime));   
 +
  }
 +
}
 +
 +
 +
int main () {
 +
 +
  // Inicializar aqui a fila de eventos
 +
  double t;
 +
 +
 +
  for (int i=0;i<300;i++) {
 +
    std::cout  << oSimulador.rngService.exp2() << " ";   
 +
  }
 +
  std::cout << '\n';
 +
 +
 +
  //oSimulador.scheduleEvent (new standardArrival (t=t+fRand(1.0,10.0)));
 +
  oSimulador.scheduleEvent(new standardArrival(oSimulador.rngArrival.exp2()+oSimulador.simtime));
 +
  // Executar simulador
 +
  oSimulador.run ();
 +
 +
  std::cout << "Tamanho fila " << oSimulador.sizeQueue() << '\n';
 +
  return 0;
 +
}
 +
</syntaxhighlight>
 +
-->
  
 
==Ainda Tarefa 6==
 
==Ainda Tarefa 6==

Edição das 17h01min de 1 de abril de 2019

AULA 1 - Dia 26/07/2018

  • Apresentar e Discutir Plano de Ensino
  • Conceitos em ADS

Plano de Ensino

SLIDES DA AULA

ATIVIDADE 1

PARTE 1

O código abaixo permite estimar o tempo de execução do programa (processo) para executar um determinado loop. Modificar o programa e gerar um gráfico mostrando a média do tempo de execução para uma faixa de 1 até 100 processos. Discutir o resultado. Postar no SIGAA um mini-relatório com:

  • objetivo do experimento
  • dados do PC utilizado (número de cores);
  • código modificado;
  • gráfico tempo médio x número de processos;
  • discussão do resultado.

//Modificado de https://www.geeksforgeeks.org/measure-execution-time-with-high-precision-in-c-c/

  1. include <sys/time.h>
  2. include <sys/types.h>
  3. include <sys/wait.h>
  4. include <unistd.h>
  5. include <stdio.h>


int main() { 

   long int i;
   double tempo_bloco; 
   int status;
   pid_t pid;

   for (i=0;i<23;i++) {
   	if (fork()==0) {
   		struct timeval start, end; 
   
   		gettimeofday(&start, NULL); 
  
               for (i=0; i<10000000000L; i++)  {  // loop de interesse
               } 
   		gettimeofday(&end, NULL);   

   		tempo_bloco = (end.tv_sec - start.tv_sec) * 1e6; 
   		tempo_bloco = (tempo_bloco + (end.tv_usec -  
                             start.tv_usec)) * 1e-6; 

   		printf("Tempo = %lf\n", tempo_bloco);
   		exit(0); 
   	}
   }
   while ((pid = wait(&status))>0); //espera por todos os filhos terminarem

} </syntaxhighlight>

PARTE 2

Projetar um experimento para verificar se o mecanismo nice (usando setpriority()) funciona conforme o esperado. Use o programa acima como base. Defina:

  • os objetivos do experimento
  • métricas
  • parâmetros
  • fatores
  • Apresente e discuta os resultados.

Incluir a PARTE 2 no relatório do experimento.

AULA 2 - Dia 18/02/2019

  • Continuação da Aula anterior: Conceitos Básicos de ADS
  • ATIVIDADE 1

AULA 3 - Dia 20/02/2019

  • Medição em Redes

Medição Ativa e Passiva em Redes

  • Referência:

Survey Sobre Medição em Redes

  • Slides: Medição Ativa - Iperf

https://www.dropbox.com/s/38qy76phjob7a3o/Medi__oEmRedes.pdf?dl=0

ATIVIDADE 2

Implemente um experimento usando o iperf para:

  • determinar a vazão máxima entre PC1 e PC3 usando o protocolo UDP;
  • descobrir a janela "ótima" do TCP para maximizar a vazão entre PC1 e PC2;

Use a seguinte configuração do netkit:

  1. Definição das máquinas

R1[type]=router PC1[type]=generic PC2[type]=generic PC3[type]=generic

  1. Definição dos roteadores padrão

PC1[default_gateway]=10.0.0.254 PC2[default_gateway]=10.0.1.254 PC3[default_gateway]=10.0.1.254

  1. Definição das interfaces do roteador

R1[eth0]=lan0:ip=10.0.0.254/24:rate=10000 R1[eth1]=lan1:ip=10.0.1.254/24:rate=10000

  1. Definição das interfaces dos PCs

PC1[eth0]=lan0:ip=10.0.0.1/24:rate=10000 PC2[eth0]=lan1:ip=10.0.1.2/24:rate=10000 PC3[eth0]=lan1:ip=10.0.1.3/24:rate=10000 </syntaxhighlight>

ATIVIDADE 3 - Questionário Medição Ativa x Passiva em Redes

1.Explique a diferença entre medição ativa e passiva em redes.

2.Liste os benefícios advindos da a aquisição de dados/avaliação de desempenho derivado da medição ativa ou passiva.

3.Descreva como o SNMP e RMON podem ser usados no contexto de medição em redes.

4.Apresente brevemente as sete métricas de desempenho IP proposta pela IETF (IP Performance Metrics - IPPM)

5.Em medição passiva existem problemas associados ao sigilo de dados. Discuta que problemas são estes e como podem ser contornados.

6.Em medição ativa normalmente se usa o conceito de "probes". Explique o que é e discuta características desejáveis de uma pacote probe. Discuta também o conceito de intrusão neste contexto.

7.Explique como é formado o tempo de retardo (delay) fim-a-fim na comunicação de dados.

8.Explique como é computada a capacidade de um caminho (fim-a-fim) de comunicação.

9.Qual conceito de banda disponível ("Available bandwidth"). Discuta a técnica PPTD (ou SLOPS ou TOPS). Faça um esquema/procedimento inicial de como pode ser usada esta técnica em um experimento real de medição de banda disponível.

Outras Referências

https://www.caida.org/publications/papers/2003/bwestmetrics/


AULA 4 - Dia 26/02/2019

Objetivos

  • Discussão da Atividade 1: Definição do experimento, métricas, caracterização da carga de trabalho, parâmetros e fatores
  • Medição Ativa e Passiva: Continuação


Links Interessantes


AULA 5 - Dia 13/03/2019

Objetivos

  • Sumarização de Dados
  • Confiança Estatística

https://www.dropbox.com/s/yrcsrmfbcukatwz/ConfiancaEstatisticav1.pdf?dl=0


TAREFA 4

  • Exercícios dos slides conforme repassado em aula: data limite => 23/03/2019


AULA 6 - Dia 20/03/2019

Objetivos

  • Sumarização de Dados
  • Confiança Estatística

Exercício (TAREFA 5)

O código abaixo permite melhor enteder o conceito de Intervalo de Confiança (IC). Uma amostra de tamanho 33 é extraída de uma população normal com média e desvio padrão conhecidos. O IC é calculado para um nível de confiança de 95%.

1)Implemente um código adicional para que seja realizada 10000 computações (coleta de amostras - cada amostra com 33) de IC e para que seja verificado se o nível de confiança está sendo respeitado.

2) Pesquisar no matlab o equivalente a função norminv para a distribuição T-student. Aplicar o programa para resolver os intervalos solicitados no slide da aula (exemplo da fila).

3) Construir uma função para comparar dois sistemas baseando-se no intervalo de confiança. Serão fornecidos dois vetores com as medições (pareadas), bem como o nível de confiança desejado. A função deve retornar se existe (V) ou não diferença significativa para o nível de confiança desejado.


%code adapted from http://www2.cs.siu.edu/~qcheng/Teaching%20Software/Matlab%20Tutorials.pdf

n=33; % *Linha 1: simula o tamanho da amostra (por exemplo, 4 repetições de uma simulação do omnet)* pm=12; ps=10; % *Linha 2: parâmetros de uma população normal: média 12 e desvio 10* alfa=0.05; num_exp=100% *Linha 3: 1-alfa determina o nível de confiança figure; hold on; % Linha 4: prepara uma figura* for i=1:num_exp ; % Linha 5: Cada loop simula um experimento: a retirada de 100 conjuntos de amostras de tamanho n * 

 x=pm+ps*randn(n,1);  % *Linha 6: retira as n observações da população. Em x estão n amostras*
 mx=mean(x); % *Linha 7: faz a média das n amostras*
 zcr=norminv(1-alfa/2,0,1);  % *Linha 8 modificado código original - determina a referência superior para confiança de 0.05 - inversa da normal padrão*
 sem=ps/sqrt(n);  % *Linha 9: desvio padrão da média amostral*
 me=zcr*sem; % *Linha 10: margem de erro para computação do intervalo de confiança*
 CI1= mx-me;    % Linha 11: limite inferior do intervalo de confiança*
 CI2= mx+me;   % Linha 12: limite superior do intervalo de confiança*
 plot(i*ones(1,n), x, 'k.','markersize',5); % Linha 13: plotagem do intervalo*
 plot(i*ones(1,2),[CI1, CI2],'g+') % show CI * Linha 14: plotagem do intervalo* 
 if pm<CI1 || pm>CI2  % Linha 15: intervalos que não contém a média da população!! *
   plot(i,pm,'r*','markersize',10)  %*Linha 16: ressaltado em vermelho*
 end  % *Linha 17*

end % Linha 18 xlabel('numero do experimento') % *Linha 19* ylabel('observacoes ') % *Linha 20* title(['95% CI:',num2str(mx,3),'\pm',num2str(me,3)]), shg % *Linha 21* </syntaxhighlight>


AULA 7 - Dia 26/03/2019

Objetivos

  • Introdução a Simulação com Eventos Discretos
  • Simulação de Fila MM1 usando um Simulador Implementado em C/C++

Material de Referência

TAREFA 6

  1. Adaptar o código de tratamento de uma fila MM1 simples, conforme colocado no slide para um formato de um simulador de eventos discretos com filas. Use o código abaixo como apoio.
//Basead em http://stdcxx.apache.org/doc/stdlibug/2-2.html#225

#include <queue>
#include <iostream>
#include <cstdlib>

//==================================================================
// classes evento e simulação - base para o desenvolvimento da simulação
//==================================================================

class event {
public:
  // Construct sets time of event.
  event (double t) : time (t)
    { }

  // Execute event by invoking this method.
  virtual void processEvent () = 0;

  const double time;
};


class simulation {
public:
  simulation () : simtime (0), eventQueue () 
    {}
  void run ();
  void  scheduleEvent (event * newEvent) {
    eventQueue.push (newEvent);
  }
  double simtime;
protected:
  class eventComparator {
    public:
    bool operator() (const event * left, const event * right) const {
      return left->time > right->time;
    }
  };
  std::priority_queue<event*,
                      std::vector<event *, std::allocator<event*> >,
                      eventComparator> eventQueue;  //fila de eventos 
};

void simulation::run () {

  while (! eventQueue.empty ()) { //enquanto exisitr eventos na fila de eventos

    event * nextEvent = eventQueue.top (); //captura evento no topo da fila
    eventQueue.pop ();  //retira evento da fila
    simtime = nextEvent->time;  //ajusta tempo de simulação
    nextEvent->processEvent ();  //processa evento
    delete nextEvent;  //remove evento
  }
}

//===================================================================
//Customização dos eventos e do simulador
//===================================================================

class standardArrival : public event {
public:
  standardArrival (double t)
    : event (t)
    { }
  virtual void processEvent ();
};

void standardArrival::processEvent () {
  std::cout << "processando evento no tempo " << time  << '\n';
}

class simuladorFilas : public simulation {
public:
  simuladorFilas ()
    { }
 
} oSimulador;

// from https://stackoverflow.com/questions/2704521/generate-random-double-numbers-in-c

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

int main () {

  // Inicializar aqui a fila de eventos
  double t;

  oSimulador.scheduleEvent (new standardArrival (t=fRand(1.0,10.0)));
  oSimulador.scheduleEvent (new standardArrival (t=t+fRand(1.0,10.0)));
  oSimulador.scheduleEvent (new standardArrival (t=t+fRand(1.0,10.0)));

  // Executar simulador
  oSimulador.run ();


  return 0;
}

AULA 8 - Dia 01/04/2019

Objetivos

  • Implementação do Simulador a Eventos Discretos para Fila MM1
  • Geração de Números Randômicos na Simulação

Material de Referência

https://www.dropbox.com/s/c221v4hlfdrpc1n/GeracaoNumerosRandomicosSimulacao.pdf?dl=0


Ainda Tarefa 6

  • Na fila MM1 passada em aula, a distribuição dos tempos de chegada e dos tempos de serviço seguem uma distribuição exponencial. Na atividade 6 foi solicitado converter o código do simulador MM1 para uma estrutura de simulador a eventos discretos. Resta realizar esta geração randômica.

Para tanto, vamos seguir o método da função inversa da seguinte forma: (1) Implementar uma classe de geração randômica uniforme segundo o método do polinômio congruente; (2) Implementar uma classe de geração exponencial que se utiliza da classe anterior e implementa a função inversa (ver slides) (3) Incorporar esta implementação no código do simulador.

  • Implementar uma Classe de Geração de Números Randômicos a partir de uma distribuição exponencial usando o método da função inversa. Usar o método de polinômio congruente linear para geração da distribuição uniforme.

Código do Matlab para entendimento do método linear congruente

Código Matlab de Apoio

%parâmetros a=7^5; c=0; x0=1; m=2^31-1; % zerar xn xn=zeros(20000,1); %gerar numeros for i=1:10000 

 xn(i)=mod(a*x0+c,m);
 x0=xn(i);

end % ajustar para gerar entre 0 e 1 un=xn/m; % plotar histograma hist(un(1:10000),10); </syntaxhighlight>

Disponível em “https://wiki.sj.ifsc.edu.br/index.php?title=ADS29009-2019-1&oldid=156289”