Simplified Computer(CS): escalonamento algorithms, FCFS, SJP, Round-Robin [was: Help]

Question

regbrz 0 Newbie Poster

20 Years Ago

Hello,

I am with problems I need to Implement urgent a Simplified Computer (CS). This computer will receive as entrance parameter the configuration of duration and it arrives of processes, according to example to proceed.

Process
1
2
3
Arrival
1
2
3
Duration
5
2
4

After receiving the configurations of the processes, CS will owe emular/simular the escalonamento and execution of these processes, and, at the end of the execution CS should exhibit the time of return and of wait of each process (Silberschatz), according to the table to proceed:

Process Return Waits

Its CS should be capable to work the escalonamento algorithms, FCFS, SJP, Round-Robin.

Could anybody help me?

algorithm-pseudocode c

2 Contributors
3 Replies
230 Views
20 Hours Discussion Span
Latest Post 20 Years Ago Latest Post by Salem

Dani AI

Generated 7 Months Ago

Short, practical plan to get arrival times and both SJF variants working (building on code and 's suggestion to use a central process table + per-algorithm functions).

data model: add an arrival and completion field to each process record and keep a remaining value (initially equal to burst). Computing results after the run is simple and reliable:

turnaround = completion - arrival
waiting = turnaround - burst

simulation pattern to handle arbitrary arrivals (works for FCFS, RR, non-preemptive SJF and preemptive SJF/SRTF): keep a global time now, maintain a ready set = all processes with arrival <= now and not finished. If ready is empty, advance now to the next arrival. Otherwise select the next process according to the policy and run it for the correct interval (for RR: min(quantum, remaining); for SRTF: either 1 tick or up to next arrival/finish). Event-driven SRTF (avoid per-tick loops) sketch:

now = 0
while (unfinished processes) {
  move arrivals with arrival <= now into ready
  if ready empty: now = next_arrival; continue
  p = ready process with smallest remaining
  next_arrival = time of next process that hasn't arrived (or INF)
  run_time = min(p.remaining, next_arrival - now)
  p.remaining -= run_time
  now += run_time
  if p.remaining == 0: p.completion = now; remove from ready
}

practical pitfalls and fixes related to the posted code

RR: when granting a slice, add actual run_time to the running process and only that amount to elapsed time; do not assume every non-running job waited a full quantum each pass — instead compute waiting from completion time (formula above).
Preemptive SJF: preempt immediately when a newly arrived job has smaller remaining time.
Efficiency: for small class projects a linear scan of ready is OK; for larger input use a min-heap keyed on remaining time.

compile/test notes

Fix the comment/extra-semicolon warnings pointed out (nested / / and stray semicolons will confuse compilers).
Test incrementally: FCFS with arrivals, then RR with quantum edge-cases, then non-preemptive SJF, then SRTF. Print arrival, burst, completion, waiting, turnaround to verify results.

All 3 Replies

Salem 6,009 Posting Sage

20 Years Ago

So what's the question?

How to read the file?

One thing to work on is some kind of process table, and 3 functions (doFCFS, doRoundRobin etc) which work on that process table.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

regbrz 0 Newbie Poster · Answer 1 · 2006-05-01T07:33:19+00:00

Look the code below, he is considered that the processes arrive in the instant 0, and I need you make them to consider the arrival in aleatory times, that is to say, time of different arrival.
And precise to implement the SJF preemptive and not preemptive.

/* Simulador de Escalonamento de Processos*/
#include <stdio.h>
#include <stdlib.h>
/* Estrutura */
struct processos {
    int id;                   /* Identifição do processo*/              
 int surto;                /* Tempo de duração do processo*/
    int prioridade;           
    int execucao;             /* Tempo de execução do processo*/
    int espera;               /* Tempo de espera do processo*/
    struct processos *prox;
};
/* Declarações de Protótipo de função */
struct processos *init_processos (int id, int surto, int prioridade);
void fcfs (struct processos *proc);
void listprocs (struct processos *proc);
void prioridade (struct processos *proc);
void rr (struct processos *proc, int quantum);
void sjf (struct processos *proc);
 
int main (void) {
    
    struct processos *plist, *ptmp;
    plist       = init_processos(1, 10, 3);
    plist->prox = init_processos(2,  1, 1); ptmp = plist->prox;
    ptmp->prox  = init_processos(3,  2, 3); ptmp = ptmp->prox;
    ptmp->prox  = init_processos(4,  1, 4); ptmp = ptmp->prox;
    ptmp->prox  = init_processos(5,  5, 2);
    /* Simulações executadas*/
    listprocs(plist);
    fcfs(plist);
    sjf(plist);
    prioridade(plist);
    rr(plist, 1);
    
    while (plist != NULL) {
        ptmp = plist;
        plist = plist->prox;
        free(ptmp);
    };
    return(0);
};
/* Inicialização de entrada da lista de processos*/
struct processos *init_processos (int id, int surto, int prioridade) {
    struct processos *proc;
 proc = (struct processos*)malloc(sizeof(struct processos)); 
  if (proc == NULL) {
        printf("Erro Fatal: Falha Alocacao de memoria.\nFinalizar.\n");
        exit(1);
    };
    proc->id = id;
    proc->surto = surto;
    proc->prioridade = prioridade;
    proc->execucao = 0;
    proc->espera = 0;
    proc->prox = NULL;
    return(proc);
};

/* Escalonamento FCFS - o primeiro que chega 
/* é o primeiro a sair, ou seja, será executado primeiro */
void fcfs (struct processos *proc) {
    int tempo = 0, inicio, fim;
  struct processos *tmp = proc;
  printf("\tEscalonamento FCFS\n");
    printf("\n");
  while (tmp != NULL) {
    inicio = tempo;
    tempo += tmp->surto;
    fim = tempo;
    printf("Processo: %d\tSurto: %d\tEspera: %d\tRetorno: %d\n", tmp->id, tempo, inicio, fim);
    tmp = tmp->prox;
  };
    printf("\n\n");
};

/* Listando Processos */
void listprocs (struct processos *proc) {
  struct processos *tmp = proc;
  printf("\tListagem de Processos\n");
  printf("\n");
  while (tmp != NULL) {
    printf("Processo: %d\tPrioridade: %d\tSurto: %d\n", tmp->id, tmp->prioridade, tmp->surto);
    tmp = tmp->prox;
  };
  printf("\n\n");
 };
/* Simulação de Processos por Prioridade
 * Obs: O processo de menor valor de prioridade obtem
 * prioridade maior na fila de processos */
void prioridade (struct processos *proc) {
  int tempo, inicio, fim, maior;
  struct processos *copia, *tmpsrc, *tmp, *maiorprimeiro;
  printf("\tEscalonamento por Prioridade\n");
   printf("\n");
  
     /* Replicando Lista de Processos */
  tmpsrc = proc;
  copia = tmp = NULL;
  while (tmpsrc != NULL) {
    if (copia == NULL) {
    copia = init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
    tmp = copia;
    } else {
    tmp->prox = init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
    tmp = tmp->prox;
    };
    tmpsrc = tmpsrc->prox;
  };
  /* Programa Principal */
  tempo = 0;
  while (copia != NULL) {
    
          /* Localiza o proximo processo */
    maiorprimeiro = NULL;
    maior = copia->prioridade;
    tmp = copia->prox;
    tmpsrc = copia;
    while (tmp != NULL) {
    if (tmp->prioridade < maior) {
      maior = tmp->prioridade;
      maiorprimeiro = tmpsrc;
    };
    tmpsrc = tmp;
    tmp = tmp->prox;
    };
     if (maiorprimeiro == NULL) {
    /* Verifica se o primeiro processo possui maior prioridade */
    inicio = tempo;
    tempo += copia->surto;
    fim = tempo;
    printf("Processo: %d\tSurto: %d\tEspera: %d\tRetorno: %d\n", copia->id, tempo, inicio, fim);
    tmpsrc = copia->prox;
    free(copia);
    copia = tmpsrc;
    } else {
    /* Verifica se o primeiro processo não possui maior prioridade */
    tmp = maiorprimeiro->prox;
    inicio = tempo;
    tempo += tmp->surto;
    fim = tempo;
    printf("Processo: %d\tSurto: %d\tEspera: %d\tRetorno: %d\n", tmp->id, tempo, inicio, fim);
    maiorprimeiro->prox = tmp->prox;
    free(tmp);
    };
  };
  printf("\n\n");
};
/* Escalonamento Round-Robin */
void rr (struct processos *proc, int quantum) {
  int jobsremain, passes;
  struct processos *copia, *tmpsrc, *tmp, *slot;
  printf("\tEscalonamento Round-Robin - Quantum: %d)\n", quantum);
  printf("\n");
  tmpsrc = proc;
  copia = tmp = NULL;
  while (tmpsrc != NULL) {
    if (copia == NULL) {
    copia = init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
    tmp = copia;
    } else {
    tmp->prox = init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
    tmp = tmp->prox;
    };
    tmpsrc = tmpsrc->prox;
  };
  /* Programa rotina de análise de prioridade  */
  jobsremain = 2;
  slot = NULL;
  while (jobsremain) {
    jobsremain = 0;
    /* Seleciona o próximo processo efetuando sua alocação */
    if (slot == NULL) {
    slot = copia;
    jobsremain = 2;
    } else {
    passes = 0;
    do {
      if (slot->prox == NULL) {
        passes++;
        slot = copia;
      } else {
        slot = slot->prox;
      };
    } while (passes <= 3 && slot->surto == slot->execucao);
    if (passes <= 3) {
      jobsremain = 2;
    };
    };
    /* Executa um ciclo */
    tmp = copia;
    while (tmp != NULL) {
    if (tmp->surto > tmp->execucao) {
      if (tmp == slot) {
        tmp->execucao += quantum;
      } else {
        tmp->espera += quantum;
      };
    };
    tmp = tmp->prox;
    };
  };
  /* Exibe os resultados e elimina as replicações */
  tmp = copia;
  while (tmp != NULL) {
    printf("Processo: %d\tSurto: %d\tEspera: %d\tRetorno: %d\n", tmp->id, tmp->surto, tmp->espera, tmp->execucao + tmp->espera);
    tmpsrc = tmp;
    tmp = tmp->prox;
    free(tmpsrc);
  };
  printf("\n");
};

/* Escalonamento SJF*/
void sjf (struct processos *proc) {
  int tempo, inicio, fim, shortest;
  struct processos *copia, *tmpsrc, *tmp, *beforeshortest;
  printf("\tEscalonamento SJF\n");
  printf("\n");
  /* Lista de processos é replicada */
  tmpsrc = proc;
  copia = tmp = NULL;
  while (tmpsrc != NULL) {
    if (copia == NULL) {
    copia = init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
    tmp = copia;
    } else {
    tmp->prox = init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
    tmp = tmp->prox;
    };
    tmpsrc = tmpsrc->prox;
  };
  tempo = 0;
  while (copia != NULL) {
    /* Encontra o proximo processo*/
    beforeshortest = NULL;
    shortest = copia->surto;
    tmp = copia->prox;
    tmpsrc = copia;
    while (tmp != NULL) {
    if (tmp->surto < shortest) {
      shortest = tmp->surto;
      beforeshortest = tmpsrc;
    };
    tmpsrc = tmp;
    tmp = tmp->prox;
    };
    /* Executa processo e remove ráplica da lista de processos */
    if (beforeshortest == NULL) {
    /* Aloca o primeiro processo caso o mesmo seja menor */
    inicio = tempo;
    tempo += copia->surto;
    fim = tempo;
    printf("Processo: %d\tSurto: %d\tEspera: %d\tRetorno: %d\n", copia->id, tempo, inicio, fim);
    tmpsrc = copia;
    copia = copia->prox;
    free(tmpsrc);
    } else {
    /* Aloca o primeiro processo caso não haja 
                /*ocorrencia de outro menor 
                */
    tmp = beforeshortest->prox;
    inicio = tempo;
    tempo += tmp->surto;
    fim = tempo;
    printf("Processo: %d\tSurto: %d\tEspera: %d\tRetorno: %d\n", tmp->id, tempo, inicio, fim);
    beforeshortest->prox = tmp->prox;
    free(tmp);
    };
  };
     printf("\n\n");
};

Will it be that can help me? I will be very grateful.

Salem 6,009 Posting Sage · Answer 2 · 2006-05-01T12:29:48+00:00

Help with what?
Are you expecting people to just take your code and debug it for you and hand it back to you? That's not likely to happen.

I mean, if you have a specific question like
- why doesn't this line compile, or
- why does it crash with some type of input, or
- I don't understand how to...
Then that's fairly easy to answer.

You seem to have the bulk of the code there, and on superficial inspection it seems to be doing the right thing.

You could clean up the warnings a bit I suppose

$ gcc -W -Wall -ansi -pedantic -O2 bar.c
bar.c:42: warning: ISO C does not allow extra ‘;’ outside of a function
bar.c:58: warning: ISO C does not allow extra ‘;’ outside of a function
bar.c:61:1: warning: "/*" within comment
bar.c:75: warning: ISO C does not allow extra ‘;’ outside of a function
bar.c:87: warning: ISO C does not allow extra ‘;’ outside of a function
bar.c:148: warning: ISO C does not allow extra ‘;’ outside of a function
bar.c:212: warning: ISO C does not allow extra ‘;’ outside of a function
bar.c:260:17: warning: "/*" within comment
bar.c:272: warning: ISO C does not allow extra ‘;’ outside of a function

Simplified Computer(CS): escalonamento algorithms, FCFS, SJP, Round-Robin [was: Help]

Dani AI

Recommended Answers Collapse Answers

All 3 Replies

Recommended Answers