segunda-feira, 6 de janeiro de 2014

Escalonador

Especificação


Objetivo: Emular via simulação em computador o comportamento do mecanismo
de escalonamento por múltiplas filas com realimentação implementado no sistema
operacional Windows 2000 através da construção de um programa em linguagem
C/C++ contendo as seguintes características:
Numero de Filas:
- Quatro (high priority, above normal, normal below normal) com valores de
prioridade base de execução variando da maior para a menor. Atribuir fatias de
tempo de processamento de 10, 30, 50 e 70 ut (unidades de tempo) para os
processos pertencentes cada fila respectivamente.
- Todas as filas devem ser do tipo “Filas de Prioridade Relativa Descendente”
(onde cada elemento só entra na fila segundo a ordem de prioridade relativa do
índice, do maior para o menor), indexada segundo as seguintes categorias: timecritical,
highest, above normal, normal, below normal, lowest idleCada
categoria tem associada a si uma fila do tipo FIFO, com tamanho máximo
ilimitado.
Processos:
- Cada processo deve ser composto por uma estrutura contendo um nome (6
caracteres), sua duração total em ut (aleatória, de 200 a 500 unidades de tempo),
a prioridade base de execução associada ao processo (high priority, above
normal, normal ou below normal), a prioridade relativa atual (time-critical, highest,
above normal, normal, below normal, lowest ou idle) o tempo já executado pelo
processo e um vetor de números inteiros aleatórios, indicando em quais unidades
de tempo o processo fará acesso a dispositivos de E/S, qual a duração do acesso
(aleatória, de 100 a 500 ut) e qual o dispositivo ( (1) Disco, CD-ROM, interf.
paralela ou vídeo; (2) Rede, interf. serial; (3)Teclado ou mouse; (4) Som ). O
número de ocorrências do vetor (acessos externos) e o somatório da duração
destas ocorrências indicará se o processo é I/O Bound ou CPU Bound (se o
processo faz uso intensivo da CPU ou de dispositivos de E/S).
Procedimento:
Cada processo é criado com uma categoria base que determina a sua prioridade
básica de execução. Durante o processamento de cada fatia de tempo de um
processo (em qualquer fila), deve-se checar o vetor de acesso a dispositivos de
E/S e interromper o processamento na unidade de tempo e duração indicadas,
retirando o processo da CPU e colocando-o em uma das quatro filas de espera de
E/S diferentes, correspondente aos seguintes pedidos de acesso externo: - Disco,
CD-ROM, iterf. paralela ou vídeo (+1); - Rede, interf. serial (+2); - Teclado ou
mouse (+6); - Som (+8). Considerar que para cada troca de contexto 1ut é
consumida. Enquanto o processo estiver fora da CPU realizando a operação de
E/S, o escalonamento continua com o próximo processo da respectiva fila. Quando
o tempo reservado especificado p/ E/S terminar, reduz-se 1 ut do quantum
disponível para o processo, incrementa-se a sua prioridade segundo o valor
indicado acima e posiciona-se o processo na fila de prioridade base respectiva,
na posição de prioridade relativa adequada.
O processamento se inicia pela fila de maior prioridade e somente passa para as
filas de menor prioridade quando esta fila estiver vazia.
Se um processo de maior prioridade entrar nas filas de escalonamento, executase
a preempção, retirando o processo em execução na CPU, acrescentando-se 1
ut ao tempo de processamento total (correspondente ao tempo utilizado para a
troca de contexto) e coloca-se o processo retirado no início da fila de origem do
mesmo, iniciando então a execução do processo com maior prioridade. O
processo que foi retirado fica com o seu próximo quantum reduzido do número de
unidades já utilizadas antes da preempção.
Uma vez terminado o quantum de processamento alocado, reduz-se a prioridade
do processo e o mesmo é transferido para a fila correspondente. Nenhum
processo pode ter sua prioridade reduzida para um valor inferior ao da sua
prioridade básica original.
Nenhum processo pode aguardar mais do que 300 ut sem ser atendido. Todo
processo que atingir esta marca deverá ter a sua prioridade incrementada para o
valor máximo possível (time-critical, high priority), deixando-o executar por um
quantum de duas vezes o valor normal da fila (20 ut). Depois do término do
quantum o processo tem a sua prioridade restaurada, retornando à fila de origem.
Este ciclo se repete para todas as filas.
A simulação deve continuar até que todos os processos tenham sido totalmente
executados (tenham o seu tempo restante de processamento reduzido a zero).

Simulação:

Para testar o trabalho deve ser criada em um arquivo uma lista de 20 processos,
onde cada dado do processo (nome, prioridade, etc), deve estar separado por
uma vírgula, e cada processo deve estar em uma linha separada. Os processos
devem estar alocados em todas as filas, cinco por fila. Deve se criar um número
aproximadamente igual de processos I/O Bound e CPU Bound, levando-se em
conta para isso o tempo total que o processo passará na fila de I/O c om relação ao
tempo total para a execução do mesmo (p/ex, se o processo passar mais do que
50% do seu tempo total de execução na CPU considere-o como CPU Bound, caso
contrário I/O Bound).
Ler os processos um a um, inserindo-os na fila correspondente com um intervalo
de tempo aleatório entre eles (variando de 1 a 20 ut). Enquanto um novo processo
não é lido, a rotina de escalonamento já deve estar trabalhando, enviando
continuamente processos para a CPU.
Deve-se criar uma interface gráfica adequada, permitindo:
A visualização de todos os processos em todas as filas (inclusive de E/S);
A visualização de todos os tempos de controle (ciclos de execução total,
tempo restante para terminar o processo em execução, quantum restante
do processo que está na CPU, tempo da próxima saída para E/S prevista,
tempos decorridos nas diversas filas de E/S, etc);
Botões para pausar a execução, acelerar e desacelerar os tempos relativos
para visualização das informações (duração real da unidade de tempo).





Relatório:
Código fonte comentado das funções/programas (fora a interface gráfica).
Impressão dos dados do arquivo de teste utilizado, incluindo:
o tempo total previsto para a execução de cada processo (indicando se o
mesmo é I/O Bound ou CPU Bound;
o tempo real utilizado levando em conta o método de escalonamento utilizado;
a somatória de tempo total esperado para a execução de todos os vinte
processos;
o tempo total global real utilizado para a execução de todos os processos.


Bibliográfica Utilizada
Sistemas Operacionais Modernos – Andrew S. Tanenbaum
Borland C Completo e Total – 3 ª Edição Herbet Schildt
Banco de Dados – Fundamentos, Projetos e Implementação
Algoritmos – Teoria e Prática. Thomas H. Cornem – Charles E. Leiserson, Ronald L. Rivest, Cliford Stein


Introdução



Um escalonador de processos é um programa que gerencia, conforme um conjunto de regras pré-estabelecidas, a correta divisão de tempo para que vários processos possam ser executados ao mesmo tempo.

Para fins acadêmicos, desenvolveu-se um escalonador de processos com
4 filas (high priority, above normal, normal e below normal)  e indexadas por 7 filas relatives: timecritical, highest, above normal, normal, below normal, lowest e idle.
Utilizando para isto o armazenamento dos processos em um banco de dados PARADOX.

Os processos são cadastrados em uma tabela e a medida que vão sendo processados os seus dados são imediatamente atualizados com simples comandos de SQL

Graças a esta abordagem o projeto do escalonador reduziu significativamente a complexibilidade de implementação e nos permitiu acompanhar o estado dos processos de forma muito mais clara, apenas visualizando os dados em uma tabela.

O software de escalonamento chamado  “Escalonador” foi construído utilizando o ambiente de desenvolvimento Borland C ++ Builder 6.0 e a base de Dados foi feita em Paradox 6.0 (Driver nativo do BDE da Borland)

Foram Criadas as Seguintes Tabelas:

PROCESSO.DB – Armazena os processos cadastrados
ES.DB – Armazena dados de entradas e saída referenciados sobre o processo.
ESCONFIG.DB – Parametrização nos tempos e descrição dos dados de entrada e saída.
PRIORIDADES.DB – Parametrização de prioridades usadas no escalonador.

Com a utilização de um banco de dados, pode-se criar backup das simulações cadastradas gerando facilmente vários cenários para estudo além do mais como o controle de concorrência é feito pelo banco de dados a tabela pode ser compartilhada por várias instâncias do programa, simulando assim um multiprocessamento de CPU, iremos falar mais adiante neste assunto.

Todos os simuladores desenvolvidos  nos cursos acadêmicos usaram uma modelagem de dados baseados em pilhas, filas e outras estruturas usando classes para representação de dados ou structs, implementando assim um controle indexado e interrativo através de controle de matrizes de ponteiros.

Esta implementação é feita principalmente porque os alunos utilizam o ferramental aprendido em C e C++ para representação destas estruturas, mas pensando em manutenção do programa e a depuração do problema, veríamos que a dificuldade em si não seria o escalonador, mais sim o controle destas estruturas, que neste projeto seriam exaustivamente utilizadas.


Para fugir deste problema e pensando em uma abordagem bem mais simples, optou-se pela fácil manuntenção. Por se tratar de um simulador acadêmico, a performance não seria um problema, pois também a base Paradox não é a mais recomendada, poderíamos ter utilizado SQL Server, mas foi escolhido o Paradox por ser de mais fácil compreensão e implementação no ambiente da Borland.



*1) na verdade os processos são executados por durante pequenas fatias de tempo e como esta troca é tão rápida, o usuário tem a impressão q vários processos estão executando ao mesmo tempo.
**) SQL – Sintaxe Languague Query


A implentação de ponteiros torna difícil a depuração do programa.
Além do mais a utilização do banco de dados nos permitiria realizar tarefas de iteração sobre as estruturas de forma muito mais simples.

Ex1: Quero que o tempo de espera de todos os processos sejam acrescentados.

Update PROCESSO Set TempoEspera = TempoEspera + 10

Ex2: Para saber qual processo esta rodando atualmente na CPU basta que a interface emita a seguinte consulta SQL:

Select * from PROCESSO where CPU = 1

Outro ponto interressante é a organização dos processos em filas, onde por exemplo teríamos que fazer uma matriz indexadas em 3 dimensões 7x4xn onde n seria um ponteiro para uma fila FIFO.
Para não criar 28 tabelas, simplificamos a modelagem e criamos apenas uma tabela chamado PROCESSOS com os seguintes campos:


Campo
Tipo
Descrição
Codigo
Auto-Incremental
Código auto-incremental gerado para o processo, utilizado também como PID.
Ex: 1788
Nome
ALPHA 50
Nome do Processo. Ex: Calc.exe, Notepad.exe, etc.

Duracao
NUMBER 8
Quantidade em tempo de CPU que um processo deverá permanecer em execução
CodigoBase
NUMBER 8
Corresponde ao indexador de prioridade de execução
Sequencia
NUMBER 8
Seqüência de execução, quando criado recebe sempre o MAX()+1
CodigoBaseBackup
NUMBER 8
Copia do indexador de prioridade para que nas operações de subtração de CodigoBase seja respeitado este mínimo
TempoExecutado
NUMBER 8
Tempo que o processo já foi executado pela CPU
TempoEspera
NUMBER 8
Desde que o processo foi criado, q quanto tempo ele já existe? O tempo de Espera deveria se chamar tempo de vida, mas por convenção e resolução do problema de Starvation, preferiu-se este nome
CPU
NUMBER 8
Status do Processo
0         = fora da CPU
1         = dentro da CPU
2         = não existe mais, mantém por histórico, para confecção de relatórios estatísticos.




A criação da tabela simplificou a definição de uma matriz de 3 dimensões onde uma abordagem a priore seria.

1 fila para prioridade base
1 fila para prioridade relativa
1 fila para seqüência

Onde os elementos deveria ser indexados da seguinte forma

Processo[x][y][z].codigo =  teriamos q fazer o autoincremento manualmente
Processo[x][y][z].nome =
Processo[x][y][z].duracao
Processo[x][y][z].codigobase
Processo[x][y][z].sequencia
Processo[x][y][z].codigobasebackup
Processo[x][y][z].tempoexecucao
Processo[x][y][z].tempoespera
Processo[x][y][z].CPU

Por exemplo para aumentar o tempoespera

For(x=0;x<4 o:p="" x="">
   For(y=0;y<7 o:p="" y="">
      For(z=0;z
        Processo[x][y][z].tempoespera = Processo[x][y][z].tempoespera + 1;

Observe q teríamos q controla ainda o TamanhoZ[y] variável.
Esta forma iterativa, poderia ainda ser substituída por matemática de ponteiros, deixando ainda mais complicado a implementação de métodos simples.

Além do mais todos os dados dos processos ficariam na memória, imagine um escalonador com 1.000.000 de registros, so para armazenar a estruturas dos processos consumíramos.


356 megabytes de memória,  fora ainda os dados para ES e controles do próprio programa.

Ainda os processos de iteração com Banco de Dados para pequenos volumes não se percebe muito a performance, a medida que o volume vai crescendo os algoritmos de iteração linear sofrem problemas de pesquisa. Teríamos que mais uma vez pensar em ordenações, pesquisas binárias, Quick Sort etc,  encarrecendo ainda mais o nosso custo de desenvolvimento.

Valendo desse conceito, organizamos os processos numa matriz e atribuímos os seguintes códigos:


Idle
Lowest
Bellow Normal
Above Normal
Normal
Highest
Time Critical
Bellow Normal
1
2
3
4
5
6
7
Normal
8
9
10
11
12
13
14
Above Normal
15
16
17
18
19
20
21
High Priority
22
23
24
25
26
27
28

Fazer um painel deste em um resolução de 1024x768 ficou difícil, então decidimos juntas as prioridades Idle e Lowest diminuindo assim nossa matriz, facilitando assim a visualização.


Idle Lowest
Bellow Normal
Above Normal
Normal
Highest
Time Critical
Bellow Normal
1
2
3
4
5
6
Normal
7
8
9
10
11
12
Above Normal
13
14
15
16
17
18
High Priority
19
20
21
22
23
24

Como o objetivo deste escalonador é monstrar de forma clara o escalonamento,  sem prejudicar os conceitos, a simplificação não afetou o projeto.




Estão foi criada a tabela PRIORIDADES.DB para que os dados do escalonador pudessem ser parametrizados e não mais fixos em código.




PRIORIDADES.DB
Campo
Tipo

Descrição

Codigo
Auto-Incremental
Código auto-incremental gerado pelo BD apenas para controle de cadastro
DESCRICAO
ALPHA 50
Descrição da Fila de Prioridade

PRIORIDADE
NUMBER 8
Este é o código referenciado dentro do programa, não deve ser alterado, ou o mapeado irá ser modificado
CPUTIME
NUMBER 8
Quanto tempo um processo pode ficar executando dentro da CPU
70 – Bellow Normal
50 - Normal
30 – Above Normal
10 – Hight Priority


Dados da Tabela (* apenas por coincidência os códigos são iguais a prioridade)

CODIGO
DESCRICAO

PRIORIDADE

CPUTIME
1
Bellow Normal – Lowest Idle
1
70
2
Bellow Normal – Bellow Normal
2
70
3
Bellow Normal – Above Normal
3
70
4
Bellow Normal – Normal
4
70
5
Bellow Normal - Highest
5
70
6
Bellow Normal – Time Critical
6
70
4
Normal - Lowest Idle
7
50
8
Normal - Bellow Normal
8
50
9
Normal - Above Normal
9
50
10
Normal – Normal
10
50
11
Normal – Highest
11
50
12
Normal - Time Critical
12
50
13
Above Normal – Lowest Idle
13
30
14
Above Normal - Bellow Normal
14
30
15
Above Normal - Above Normal
15
30
16
Above Normal – Normal
16
30
17
Above Normal – Highest
17
30
18
Above Normal - Time Critical
18
30
19
Hight Priority - Lowest Idle
19
10
20
Hight Priority - Bellow Normal
20
10
21
Hight Priority - Above Normal
21
10
22
Hight Priority – Normal
22
10
23
Hight Priority – Highest
23
10
24
Hight Priority - Time Critical
24
10
Assim teríamos a mão a configuração do Escalanador, utilizando uma simples tela de cadastro:



A medida que vamos cadastrando os processos eles vão sendo colocados automaticamente para o escalonador processar, podemos cadastrar qualquer processo mesmo como o escalonador em execução.

Sendo assim acabamos de criar um mecanismo para fácil atualização e recuperação dos dados, que iremos ver, facilitou muito na construção da interface e manutenção do código do programa, assim como a compreensão do problema.

Um simulador também precisa se preocupar também com o sincronismo do tempo, pois o seu tempo é fictício. As batidas do seu clock interno dentro da CPU devem ser processados o tempo de todos os processos devem ser atualizados.

Para esta “difícil” tarefa a única instrução que precisamos emitir é uma simples consulta de atualização SQL.

“Update PROCESSOS set CPU_TIME=CPU_TIME+1”


O que iremos demonstrar neste artigo é que o dado um problema de implementação do escalonador, analisando todas as estruturas de dados envolvidas, abstrai o máximo possível estas definições, simplifiquei alguns pontos e também por um certo desafio, decidi implementar a estrutura usando um banco de dados.


Desenvolvimento




Tendo em vista todos os detalhes da especificação do projeto, comecei a fazer um protótipo simulando as seguintes situações em uma planilha de excel.



A planilha permitiu gerar alguns ensaios para poder montar alguns algoritmos e corrigir alguns erros de definições.

Analisando o problema ficou claro claro que iríamos precisar de uma tabela também para armazenar os dados de ES e que esta deveria ter uma referência para a tabela de processos.


ES.DB
Campo
Tipo

Descrição

Codigo
Auto-Incremental
Código auto-incremental gerado pelo BD apenas para controle de cadastro
PROCESSO
NUMBER 8
Chave estrangeira ( FK )da referência que o processo faz a ES

TEMPO
NUMBER 8
Qual o tempo, dentro do processo a ES deve ser ativada, por Exemplo, se o processo dura 500 unidades de tempo, e deve fazer o vídeo no tempo 100 durante 50 unidades de tempo
TEMPOEXECUTADO
NUMBER 8
Quanto tempo a ES esta sendo executada.

DISPOSITIVO
NUMBER 8
Chave estrangeira ( FK ) da refêrencia que do dispositivo fazendo E/S
SEQUENCIA
NUMBER 8
Sequência que a entrada e saída está sendo executada
CPU
NUMBER 8
Flag se a ES já foi inteiramente processada,
0 = esta aguardando
1 = processando
2 = já foi processada mais mantida por histórico
a ES não fica na CPU ela é um dispositivo independente, esta coluna poderia se chamar por exemplo FLAG_ES, foi mantida este nome apenas pq o código já tinha sido escrito com este termo, no trabalho de revisão poderemos mudar.

TEMPOESPERADO
NUMBER 8

               

ESCONFIG.DB – Configuração nos processos de Entrada e Saída
Campo
Tipo

Descrição

Codigo
Auto-Incremental
Código auto-incremental gerado pelo BD apenas para controle de cadastro
DESCRICAO
ALPHA 50
Descrição da Fila de Prioridade

CPUTIMEADD
NUMBER 8
Quanto a ES finaliza, quanto o processo se ainda estiver em execução deverá receber de acréscimo de prioridade.
1 -  Disco, CD-ROM, Interface Paralela ou vídeo.
2 – Rede ou Interface Serial
6 – Teclado ou Mouse
8 - Som


Com os dados estão em um tabela novas definições podem ser cadastradas assim mesmo como a parametrização das mesmas.


Como ES e CPU são 2 entidades diferentes, cada uma terá seu próprio fluxo de processamento e controle de timer, ambas subordinadas a um timer global.


Visto a quantidade de tabelas envolvidas no Sistema, foi necessária criar interfaces de cadastros simples:




O cadastro de dados de processos através de formulários permite a validação e consistência dos processos.

Usando conceitos de Engenharia de Software foi adotado o modelo MVC para implementação da Interface.




Onde quais alterações por na camada do Broker (SQL) não influenciaria no restante do código.

Outro  ponto positivo em se utilizar o Banco de dados foi a questão de concorrência.
Imagine que se o nosso recurso compartilhado “tabela” for alterado ao mesmo tempo por 2 TIMERS, pode haver um erro de consistência. Implementar este mecanismo em filas seria expendioso e mais uma fez estaríamos reinventando a roda, então o mecanismo do banco de dados controla para nós o problema de concorrência.

Graças a este controle de concorrência poderíamos compartilhar a tabela e abrir várias sessões do escalonador apontando nosso programa para o mesmo local.
Isto iria gerar uma situação onde várias máquinas iriam dividir o mesmo recurso (processos) mais com suas CPU respectivas. Assim poderíamos criar um modelo de multi-processadores.





Cadastros:

Como um dos requisitos do problema era ler os processo de um arquivo, contornamos o problema fazendo uma simples importação para o Banco, lendo de um  arquivo CSV (texto separado por vírgulas).

Quando inserimos um processo, os registros são automaticamente vistos pelo escalonador na sua fila de prioridade, a CPU levará em consideração a sua presença no próximo CLOCK, e respeitará sua prioridade base Relativa e Real inicial quando por exemplo o processo precisar voltar por algum decisão do escalonamento, não ultrapassando este limite mínimo.

A confecção dos Relatórios foram geradas através de simples telas com Grids.

Descrições das Tecnologias Utilizadas.

Borland C++ 6.0 Builder
C++ orientado a objetos utilizando conceitos de MVC.

Persistência dos dados usando o SQL Paradox 6.0 Free

Sistema Operacional Windows NT/2000/XP/2003 necessairo 800KB em disco mínimo de 12 MB memória.

Para instalar o simulador basta rodar o arquivo escalonador.exe e configurar um alias BDPROCESSO no BDE e apontar para base de dados.



O programa é um escalonador de processos para fins acadêmicos quaislquer danos ou execuções não esperadas o autor não se responsabiliza.







Postar um comentário