Skip to content

Latest commit

 

History

History
249 lines (152 loc) · 10.6 KB

README.md

File metadata and controls

249 lines (152 loc) · 10.6 KB
Raw

process-escalonator

Codacy Badge Supported Python Version Supported Platforms License Build Status GitHub release codecov

Simulador de execução de processos de um sistema operacional em Python desenvolvido como parte da avaliação da matéria MATA58 - Sistemas Operacionais, do Departamento de Ciência da Computação da Universidade Federal da Bahia, ministrada por Maycon Leone Maciel Peixoto.

Sumário

  1. Situação
  2. Funcionamento
    . Back-end
    . Front-end
  3. Requisitos do trabalho
  4. Entrada
  5. Saída
  6. Convenções adotadas
  7. Adicionais
  8. Uso do programa
    . Requisitos para execução do programa
    . Instalação dos requisitos
    . Execução do programa
  9. Desenvolvimento

📋 Situação

Considere um sistema operacional que implementa o escalonamento de processos. O funcionamento esperado é que esse ambiente tenha N (número previamente informado pelo usuário) processos que podem chegar em tempos distintos para execução. Para cada processo, deve ser informado:

  • Tempo de chegada
  • Tempo de execução
  • Deadline

Para o sistema como um todo deve se informar o tempo do quantum do sistema e o tempo da sobrecarga, na troca de processos, do sistema.

💻 Funcionamento

Esse sistema deve ter:

Back-end

A implementação de todos os algoritmos, tanto de escalonamento quanto de paginação, citados abaixo é obrigatória para avaliação do trabalho

Algoritmos de escalonamento

Algoritmos de substituição de páginas

  • FIFO (First In First Out)
    • Algoritmo baseado na idade das páginas na memória, ou seja, páginas mais antigas serão removidas primeiro.
  • LRU (Least Recently Used)
    • Algoritmo que escolhe preferencialmente páginas antigas e menos usadas para remoção.

Todos os algoritmos acima citados, basicamente funções de ordenação com variados critérios, foram implementados em Python utilizando suas funções built-in por praticidade e facilidade.

Front-end

Esse sistema deve implementar interface gráfica, onde deve-se criar:

  • Gráfico de Gantt para mostrar as execuções dos processos

  • Visualização da CPU e da RAM

  • Deve-se criar o gráfico de uso da RAM e do Disco, mostrando as página presentes em tempo real.

  • Colocar delay para verificar a execução

Para tal utilizamos a biblioteca PyQt5 que nos fornece vários elementos para que compuséssemos a interface e os gráficos pedidos.

☑️ Requisitos do trabalho

  • Cada página tem 4 K de tamanho.

  • A RAM tem 200 K de memória.

  • Crie a abstração de Disco para utilização da memória virtual.

  • Caso ocorra falta de página (page fault), utilize N unidades de tempo para o uso do Disco.

  • O grupo está livre para a criação de qualquer abstração extra que se mostrar necessária.

  • Os processos só executam se todas as suas páginas estiverem na RAM.

📥 Entrada

O usuário deve entrar com um inteiro Q, representando o quantum do sistema, e um inteiro S, representando a sobrecarga do sistema. Além disso deve ser fornecido N, representando o número de processos, inteiros:

  • C, representando o tempo de criação do processo, onde C >= 0;

  • E, representando o tempo de execução do processo, onde E > 0;

  • D, representando o deadline do processo, onde D >= E;

  • B, representando o número de páginas que o processo precisa, onde 0 < B <= 10 , e;

  • P, representando a prioridade do processo, onde P >= 0

Deve ser escolhido um dos algoritmos de escalonamento de processo ofertados

  • FCFS (First Come First Served);
  • SJF (Shortest Job First);
  • RR (Round-Robin);
  • EDF (Earliest Deadline First);
  • SPN (Shortest Process Next);
  • LOT (Loteria);
  • PRIO (Prioridade);

Os três últimos algoritmos foram adicionalmente implementados. Mais informações aqui

Deve ser escolhido um dos algoritmos de paginação:

  • FIFO (First-In First-Out);
  • LRU (Least Recently Used)

📤 Saída

A resposta deve ser dada em função do turn-around médio (tempo de espera + tempo de execução), o gráfico de Gantt correspondente às execuções dos processos, e o estado da RAM, durante a execução dos processos, de acordo o algoritmo de escalonamento e o algoritmo de paginação escolhidos

📌 Convenções adotadas

  • Utilizamos a notação FCFS (First Come, First Served), no código, para nomear o algoritmo de escalonamento de processos e desambiguar da notação FIFO (First In, First Out), utilizada para nomear o algoritmo de paginação, pois embora os dois algoritmos tenham teoricamente o mesmo funcionamento o escopo deles é diferente.

  • Utilizamos uma memória virtual com o dobro de capacidade da memória RAM, ou seja, 400 K

  • A capacidade do disco é o somatório de Bi para i variando de 1 a N, ou seja, assumimos que o disco comporta todas as páginas de todos os processos criados.

  • Em caso de page fault utilizamos teto ((B - A) / W) tiques de clock para uso do disco, onde:

    • A é o número de páginas, desse processo, já alocadas na RAM e;

    • W é a quantidade de páginas, escritas na RAM, por segundo, em nossa implementação, escolhemos o valor de 2 páginas por segundo

  • Para organizar o repositório, foram criadas as pastas:

    • sample: contendo todo o código-fonte criado
    • sample/images: contendo todas as imagens utilizadas na interface gráfica
    • tests/: contendo todos os casos de testes utilizados

    Em prol da organização do ambiente de trabalho, pedimos ao usuário que continue salvando seus casos de teste nessa pasta

    O arquivo test-generator.py é capaz de gerar casos de testes aleatórios. Para saber como usar, digite test-generator.py --help no seu Terminal ou Prompt de Comando

➕ Adicionais

Para acrescentar tanto em conhecimento sobre escalonamento de processos quanto em nota, decidimos implementar os seguintes algoritmos:

  • Escalonamento por prioridades

    • Algoritmo que ordena a fila de prontos pela prioridade do processo, de forma decrescente

    A implementação utilizada, foi a qual a CPU diminui a prioridade do processo à sua metade, após executá-lo: P = P / 2. A fila de prontos é então reordenada pelo critério do algoritmo

  • SPN (Shortest Process Next)

    • Algoritmo similar ao SJF porém preemptivo

  • Escalonamento por loteria

    • Algoritmo preemptivo onde a escolha de processos é aleatória

⚙️ Uso do programa

O programa pode ser utilizado em qualquer plataforma que tenha Python 3.x

É aconselhado a utilizar a release mais recente

Requisitos

Instalação dos requisitos

  • Abra um Terminal ou Prompt de Comando dentro da pasta process-escalonator/:

⚠️ É recomendado que se instale as bibliotecas em um ambiente virtual, evitando conflitos de versões das bibliotecas instaladas localmente no seu computador. Para tal siga as instruções a seguir, de acordo sua plataforma.

  • UNIX:
  python3 -m venv env
  source env/bin/activate  
  pip3 install -r requirements.txt
  • Windows:
  python -m venv env
  env\Scripts\activate
  pip install -r requirements.txt

Caso não queira criar um ambiente virtual, somente dê o comando pip install -r requirements.txt, independentemente da sua plataforma

Execução do programa

Para executar basta dar o comando:

  python sample/InterFace.py

Em plataformas UNIX é bom especificar a versão do Python, já que em algumas o Python 2.x ainda vem como padrão, com o comando:

  python3 sample/InterFace.py

Em plataformas Windows, também é válido dar duplo-clique no arquivo InterFace.py dentro da pasta sample

:octocat: Desenvolvimento

Maiores detalhes e/ou dúvidas sobre o desenvolvimento desse trabalho, considere ver o log desse repositório, ou entrar em contato com os autores listados em AUTHORS