process-escalonator

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

• FCFS (First Come First Served)

  • Um algoritmo de escalonamento para estruturas de dados do tipo fila.

• SJF (Shortest Job First)

  • Um algoritmo de escalonamento que ordena os processos por tempo de execução de forma crescente.

• Round Robin

  • O nome do algoritmo vem do princípio onde cada pessoa pega um compartilhamento de algo igual por vez.

• EDF (Earliest Deadline First)

  • Um algoritmo que escolhe na fila de prontos o processo que tenha o prazo de vencimento mais curto

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 B_i 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

• Ter o Python versão 3.x instalado na sua máquina
• Ter o pip instalado
• Instalar as bibliotecas listadas em requirements.txt

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

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