Home
linkedin: (https://www.linkedin.com/in/leonardo-de-oliveira-campos-60225720b/)
Neste trabalho vamos construir um sistema de classificação cujas características nos permitirão observar conceitos importantes como: escalonamento e gestão de memória primária. Neste sistema, vamos considerar duas bases de dados D e T. A base D será utilizada para simular a inicialização, fornecendo assim o conceito de bootstrapping, tal como no sistema operacional.
Já a base T representará os processos a serem executados, cada um produzindo uma série de computações pesadas e necessárias, as quais vamos coordenar utilizando um sistema de escalonamento em dois níveis: mecanismo e política. Além disso, abordaremos o conceito de memória tratando de chavear os processos entre memória primária e processador, claro, tudo de forma simulada para que possamos extrair resultados mensuráveis para avaliação.
Etapa I: Elaboração das tabelas hash para itens e classes. Dado uma linha do arquivo, considerar item as colunas de 0 a n - 1. Considere a coluna n de cada linha como classe. Nessas tabelas é preciso armazenar cada item como chave e seus índices no arquivo como valor. Considere como índice a linha que aquele valor específico aparece. Considere também item específico aquele item pertencente a coluna x. Logo, para itens de mesmo valor, a indexação deve ser feita de forma separada, ou seja, se um item aparece na coluna 1 e 3 com valor 23.4, considere como chave da hash (1, 23.4) e (3,23.4). Repita esse processo para as classes, armazenando como chave sua descrição e como valor suas indexações.
Etapa II: Agora vamos considerar o conteúdo de T. Leia o conteúdo de T em uma Fila em que cada posição detenha uma linha inteira já tokenizada. O tipo Vector do C++ consegue auxiliar vocês nessa tarefa. Depois de carregar todo o conteúdo de T, processar linha a linha. Considere como processar a ação de comparar os itens de T com a tabela hash de itens, selecionando apenas os itens em comum. Feito isso, realize a permutação dos itens comuns de 1 a N, com N definido estaticamente com define diretamente no código. Armazene todas as permutações de uma entrada em T em um segundo Vector.
Etapa III: Para cada permutação encontrada vocês precisam buscar individualmente os valores dos itens em hash, executando em seguida uma interseção desses valores. Se a interseção for não nula, aplique essa na hash de todas as classes. A classe que apresentar um valor de sobreposição maior após processar todas as permutações será apresentada como classe da tarefa em T.
Etapa IV: Elaborar um cache utilizando uma hash para armazenar o resultado das interseções já realizadas. Adote como chave as permutações e como valor o resultado das interseções. Feito isso, modifique o algoritmo para trabalhar da seguinte forma: Para cada nova permutação, buscar em cache se há resultado já processado. Em caso afirmativo, apenas teste as classes para o resultado. Caso contrário, faça toda a computação envolvida.
Etapa V: Como as tarefas em T estão espalhadas não tem como sabermos o quão importante é a cache, uma vez que estamos utilizando apenas uma política do tipo Round Robin para escalonar. Então, sua função é criar uma política que organize melhor as tarefas para a sequência de execução aproveite melhor as computações já realizadas. Para isso, pense em organizar melhor os parâmetros de entrada de forma a encontrar grandes sobreposições de itens similares.
Etapa VI: Vamos implementar uma memória primária para chavear processos. Nesse modelo, uma tarefa não será concluída por completo porque se seu tempo de CPU acabar você a colocará em um espaço de memória para aguardar nova submissão. Vamos analisar nessa etapa os impactos do chaveamento, da organização de memória e suas diferentes hierarquias.
Este software foi produzido em ambiente virtual Linux, assim o meio de compilação utilizado foi o makefile que está na pasta "processos", é um makefile editado para uso pessoal, de forma a utilizar a depuração no processo de confecção e treads para compilações futuras. Vale ressaltar que alguns documentos .txt foram criados para fins de teste, e que não teêm nenhuma importância no montante final dos dados. Tendo essas informações em mente é hora de falar da compilação:
make clean
make
make run
Caso queira registrar a saída do terminal em um arquivo para que fique mais fácil a vistoria dos resultados use o seguinte comando:
make clean && make 2> t.txt
Caso o custo esteja alto para máquina de testes, use o seguinte comando para dividir o processamento em vários núcleos através de treads de compilação:
make j(número de núcleos disponíveis do seu computador)
Para saber a quantidade de núcleos do seu computador basta jogar as informações do seu processador na internet!!!
O código foi produzindo printando todos os dados para o usuário podermos analisar toda iteração do código, entretanto, como é feita uma análise de tempo de execução do código junto ao seu processo de escalonamento comentei todo "cout" do código, assim se quiser visualizar tudo que acontece a cada etapa basta descomentar os "couts". Vale ressaltar também que a primeira opção do menu não mostra as iterações se não descomentar os prints também.
Para resolução da etapa 1 usei um "unoder_map" para ser a hash dos itens D, no qual seria alocados os números como chave e suas aparições como valores.
Menu
Através do menu é possível acessar cada processo individualmente, foi melhor fazer dessa forma para que fosse obtido o resultado visual das iterações entre processos, assim é necessário que o usuário clique em todas as opções em ordem crescente, para que tenha o resultado de cada processo individualmente e seja carregado para os processos subsequêntes, assim se o usuário pular uma opção os processos não estarão carregados para exucição desta. Isso vale para todas as etapas.
Menu
Menu
Menu
Para calcular o tempo de execução do algoritmo que estamos trabalhando usei a biblioteca do C++ 11, está biblioteca é capaz de medir tempo de execução com alta precisão, utilizando o próprio clock da máquina para fazer o cálculo de tempo. Neste link o u´suario pode encontrar mais informações direto da documentação oficial do C++: [https://en.cppreference.com/w/cpp/chrono#std::chrono_library]
Utilização
int main()
{
auto start = std::chrono::steady_clock::now();
//Funções a serem executadas
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
std::cout << "tempo de execução:: " << elapsed_seconds.count() << endl;
}
Com este dado de execução é possível ter um ponto de vista sobre a execução mas não é apenas rodar o medidor de tempo para encontrar o tempo de execução, é necessário rodar o software por 10x e assim tirar a média dos tempos para poder chegar a um tempo convergente.
Se você estiver usando o sistema Linux como SO, também pode optar por uma forma mais simples de calcular. Sugiro que use o time ./a.out no terminal, onde a.out é o executável do seu programa. Esse comando imprime 3 linhas, sendo elas:
- real: Tempo real do começo ao fim da execução;
- sys: Tempo gasto pelo kernel do sistema no processo de execução do seu programa;
- user: Tempo usado no user-mode. É o tempo que seu computador gasta no processo fora do kernel;
Para resolução da etapa 5 mudei a politica de escalonamento do software, a qual era uma FIFO, visto que eu pegava a fila de dados para processar nas combinações e nas intersecções, passei a política para menor trabalho, onde setava a variável na primeira coluna e a percorria pegando todos os valores e assim por diante até percorrer as 4 colunas de dados do banco de dados, depois o software fazia o mesmo processamento já visto nas etapas anteriores.
A imagem 1 acima mostra a etapa das combinações recebendo o "menor trabalho", ou "first job" na função de combinate. A função com o menor job tem um ganho de tempo em relação ao FIFO, entretanto notei que o FIFO faz mais intersecções, talvez pelo método que eu usei para tal, o qual capta uma linha e joga a linha subsequente num SET para que eu pegue as intersecções, assim com o escalonamento "first job" esse método não é tão funcional quanto ao FIFO, visto que pego valorees da mesma coluna.
Para resolução da etapa 6, utilizei tanto as threads para diminuir o custo de processamento das combinações/intersecções quanto criei uma memória "virtual" para que o processamento ficasse mais rápido, fazendo com que o processamento nunca ultrapasse 3 segundos, testando na minha máquina - obviamente -, a computação é cheia de irregularidades devido a mudança de hardwares, entretanto em média os valores foram menores que 3 segundos de processamento, lembrando que estou utilizando os COUT'S para printar os resoltados na tela, sabemos que printar tem um custo físico a máquina, visto que ao printar é dado um tempo padrão ao aparecer na tela, tirando esses pormenores de lado, pude perceber um ganho ao usar 2 threads para fazer as combinações/intersecções. Vale ressaltar que no começo da produção da etapa 6 comecei a uzar um algoritmo semáforo para paralelizar a dinâmica de combinações, entretanto como minha aplicação roda com uma política FIFO o semáforo seria perda de tempo, ele é usual apenas com o first job, no caso do meu software. Assim tirei a parte de consumidor do algoritmo e deixei apenas o produtor para que eu pudesse jogar nas threads, tirando o sleep também, obviamente.
No que tange a memória virtual criada por mim para o software, utilizei de forma que evitasse um estouro "proposital" de memória - pré-definida - assim quando as combinações alcançam 1 segundo de processamento a memória capta todas as informações das combinações feitas até o momento e salva-as em um vector de vector, a fim de usá-las para dar sequência no processamento. Assim o processamento não excede 1 segundo até as combinações, obviamente que a somatória de todos os processos que estão sendo executados no código vão resultar num valor maior que 1.
Na imagem acima é possível ver o tempo como fator de continuidade do processamento, também é possível ver a produção de intersecções. Na imagem abaixo encontras-se o produtor, responsável pelas threads da aplicação.
Com a produção do projeto pude perceber que o escalonamento por colunas foi bem mais rápido do que o FIFO, a diferença é gritante. Já em relação ao tempo de compilação fiz uma tabela com os tempos de compilação, tirei 10 casos de teste para tirar a média e o desvio padrão do software.
| Escalonador | Tempo 1 | Tempo 2 | Tempo 3 | Tempo 4 | Tempo 5 | Tempo 6 | Tempo 7 | Tempo 8 | Tempo 9 | Tempo 10 | Média | Desvio Padrão |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| FIFO | 0.0752393 | 0.10263 | 0.0746101 | 0.0798161 | 0.075061 | 0.081183 | 0.100569 | 0.0860582 | 0.0749308 | 0.0764774 | 0.08265749 | 0.0106 |
| Multiplas Filas | 0.0735228 | 0.0764604 | 0.108182 | 0.073132 | 0.105177 | 0.0730909 | 0.0753045 | 0.0723516 | 0.0738657 | 0.0735181 | 0.0804605 | 0.0139 |
No que tange o custo associado ao uso de threads, há uma oscilação ao aumentar o número de threads, no qual não é algo controlável com o uso de poucos dados. Para entender melhor o problema vamos entrar nas preempções. Em computação, preemptividade é o ato de interromper temporariamente uma tarefa executada por um sistema computacional, sem exigir sua cooperação, e com a intenção de retomar à tarefa posteriormente. Tais mudanças da tarefa executada são conhecidas como trocas de contexto. Normalmente, é realizada por uma tarefa pprivilegiada ou parte do sistema conhecido como escalonador preemptivo, que tem o poder de antecipar, interromper e, posteriormente, retomar outras tarefas no sistema.
Em sistemas operacionais, preemptividade ou preempção é a capacidade de tirar de execução um processo em favor de outro. Esta é uma característica que não é importante apenas nos sistemas operacionais em tempo real. Este tipo de intervenção por parte dos escalonadores dos sistemas operacionias pode ocorrer - embora não seja limitada apenas a isso - otimizar a entrada/saída de dados em tempo real, como é o caso da gravação de áudio. Um exemplo de uma tarefa não-preemptiva é o processamento de interrupções.
Algoritmos preemptivos são mais adequados para sistemas em que múltiplos processos requerem atenção do sistema, ou seja, no caso de sistemas multiusuário interativos (sistemas em tempo repartido) ou em sistema de tempo real. Nestes casos, a preemptividade representa a troca do processo em execução, assim sendo, para que o processador seja retirado de um processo, interrompendo seu trabalho, e designando a outro processo, anteriormente interrompido, é fundamental que ocorra a troca de contexto dos processos. Tal troca exige que todo o estado de execução de um processo seja adequadamente armazenado para sua posterior recuperação, representando uma sobrecarga computacional para realização desta troca e armazenagem de tais dados. Usualmente os algoritmos preemptivos são mais complexos dada a natureza imprevisível dos processos.
Tendo a preemptividade em vista, fica explicado o porquê do tempo de execução ficar oscilando quando há um aumento, controlado, de threads, visto que num sistema preemptivo fica imprevisível o tempo gasto dado a política de escalonamento.
Este foi um trabalho acadêmico do CEFET campus V. Foi de longe o trabalho mais proveitoso que tive ao longo do curso, porque propiciou que eu conhecesse novas funcionalidades da STL e também me fez entender melhor os sistemas operacionais e como eles gerenciam seus processos.
- SistemasOperacionaisModernosTanenbaum4Edio [1]