sexta-feira, agosto 31, 2007

Desenvolvendo Software para Sistemas Embarcados

Um dos motivos dos posts estarem ficando espaçados são alguns problemas que tenho enfrentado no desenvolvimento de software para um par de sistemas embarcados. São dispositivos baseados em micro-controladores e além, das dificuldades normais de software, existe sempre a possibilidade de um problema no hardware (no projeto ou na montagem).

Embora não possa entrar nos detalhes (para não comprometer a confidencialidade do meu cliente), existem alguns pontos que dá para compartilhar com a minha dupla de leitores habituais.

Circuito de Baixo Consumo

Os dispositivos para os quais estou escrevendo software são alimentados a bateria não recarregável e o consumo precisa ser bastante baixo para garantir uma duração de meses a anos.

São necessários vários cuidados para reduzir o consumo. Por exemplo, é comum a presença nos circuitos de vários resistores ligados entre um pino do micro-controlador e terra ou a alimentação (como os famosos pull-down e pull-up para garantir o nível do sinal quando ninguém mais está colocando um sinal no circuito), estes resistores precisam ter valor elevado e, sempre que possível, o micro-controlador deve colocar no pino o mesmo sinal que na outra ponta do resistor.

Os micro-controladores costumam possuir diversos modos de operação, permitindo desligar parte do circuito interno para economizar bateria. No caso do micro-controlador usado em um dos dispositivos, o modo mais econômico desliga tudo exceto a memória. Para chegar à autonomia de anos é preciso manter o micro-controlador dormindo a maior parte do tempo. Se, por exemplo, em cada segundo executar por 5 ms com consumo de 10 mA e ficar dormindo o resto do tempo com consumo de 1 uA (microAmpere), uma bateria alcalina de 1000mAh vai durar mais de 2 anos.

O único jeito de acordar este micro-controlador é gerando um sinal de reset através de um circuito externo (no caso um timer de baixíssimo consumo e alguns sensores). Desta forma o reset passa a ser parte normal da operação, o que torna o software um pouco estranho. Como conseqüência, é preciso distinguir o reset de acordar do reset real (o power-on). Como a memória Ram é mantida mesmo com o processador parado, isto não é muito complicado.

O problema é como forçar um power-on. Como o consumo do micro-controlador dormindo é baixíssimo, a energia contida nos capacitores do circuito é suficiente para manter a Ram por muito tempo. A simples conexão da minha serial de debug consegue manter o circuito funcionando.

Pinos em Aberto

Falando em resistores de pull-up e pull-down, tive um par de problemas sérios num outro projeto onde alguns destes resistores foram esquecidos na montagem.

Neste caso o nível destes pinos fica indefinido. Pior ainda, ele acaba sendo influênciado pelos sinais próximos. Em um dos casos era um teclado em matriz, onde você coloca um sinal nas linhas, lê o resultado nas colunas e descobre quais teclas estão apertadas. Uma das colunas estava sem o resistor e a leitura quando não tinha tecla apertada acabava dependendo do que estava sendo colocado nas linhas. Sem entender direito o que estava acontecendo, eu acabei alterando a minha rotina de varredura até achar uma forma na qual (por acaso) eu conseguia ler sempre o valor correto na coluna.

Depurando Sem Serial

No segundo dispositivo é usado um micro-controlador muito simples e de baixo custo. Tão simples, que nem UART tem. Para fazer comunicação serial, é preciso ficar subindo e descendo por software o sinal de um pino para cada bit (com o timing correto). Para complicar, a memória de programação lotou rapidamente. O micro-controlador tem capacidade de depuração in-circuit, porém o código gerado para debug era grande demais. O que sobrou para debug foi um led e um pino livre do processador.

A minha principal ferramenta de debug foi um osciloscópio. O modelo disponibilizado pelo cliente não possui tela, ele é usado conectado a um PC, o que permite gravar imagens das formas de onda.

No início foi meio estranho, mas este tipo de depuração tem a vantagem de permitir ver graficamente o andamento do software ao longo do tempo. Como o osciloscópio tem dois canais, dá para ver a relação entre acontecimentos assíncronos. E é claro que dá para medir com precisão o tempo entre eventos.

Existe mais entre o VCC e o Terra que se possa imaginar

Quando estamos programando em baixo nível, pensamos muito em binário: é 0 ou 1. No hardware, entretanto, existe muita coisa entre o 0 e 1 (e às vezes até fora dele).

Um dos bugs mais complicados foi a perda esporádica da Ram no reset, no dispositivo onde isto não devia ocorrer. Esporádica quer dizer: às vezes ocorre seguidamente em um minuto e em outras fica horas sem ocorrer. Perda quer dizer que algum bit na Ram virava.

Após vários dias penando, apelei para o osciloscópio e observei o sinal ao lado no reset. À primeira vista, parece normal, porém a curva de subida me pareceu muito longa. Conversando com o projetista do hardware descobri que um capacitor estava acidentalmente com valor errado (um erro de digitação); arrancando o infeliz o sinal passou a subir "instantaneamente" e o problema subiu.

Aparentemente a subida gradual do sinal ocasionalmente confundia o processador. Algo parecido com a execução paranormal de código.

quarta-feira, agosto 22, 2007

Minha nova impressora: Samsung SCX-4200

Atualmente as impressoras são um periférico bastante comum, custando uma pequena parcela do preço de um microcomputador.


Nos anos 80, quando comprei os meus primeiros micros, a coisa não era bem asim. Minha primeira impressora, comprada nos meados dos anos 80, foi uma Grafix 80 F/T, uma impressora matricial copiada da Epson.

Não apenas cara, era lenta e barulhenta. Mesmo equipada posteriormente com "kit near letter quality" (uma troca de firmware para dar mais de uma passada em cada linha deslocando ligeiramente os pontos), a qualidade de impressão era bastante baixa. A acentuação era obtida imprimindo o acento por sobre a letra (uma vírgula no caso do c cedilha). Cheguei a fazer um programa para escrever texto usando o modo gráfico para obter uma qualidade melhor, porém era terrivelmente lento.

No final dos anos 80 começaram a surgir as impressoras laser, mas o custo estava fora do alcance das pessoas físicas (e até de empresas pequenas).


A grande virada foi o surgimento da impressora de jato de tinta. Minha segunda impressora foi um HP Deskjet 500 comprada em 93.

Embora ainda fosse cara e monocromática, fornecia qualidade e velocidade bem razoáveis. Rapidamente os antigos fabricantes de impressora passaram para o negócio de vender tinta e vender as impressora a preços extremamente baixos.

Minhas impressoras seguintes, Epson, foram brindes da assinatura de jornal.

Por outro lado, à medida em que o preço caia, caia também a durabilidade. Tanto a Grafix como a Deskjet 500 duraram cerca de 10 anos. Já as Epson ficaram longe da metade disso, apesar de muito menos usadas. As impressoras a jato de tinta atuais são também praticamente descartáveis, o preço de um conserto é de pelo menos metade do de uma impressora nova e o resultado não costuma ser bom.

Com a quebra das Epsons, foi hora de procurar uma nova opção. Cansado também do meu velho e lento scanner, resolvi dar uma olhada nas multifuncionais. Inicialmente estava pensando em uma jato de tinta da Epson, mas a Samsung SCX-4200 acabou me fascinando. Por um preço bem razoável (R$ 549, em 10x no cartão) deu para realizar o velho sonho de ter uma impressora laser. É claro que isto significa deixar de lado as cores.

O custo do tonner é outra preocupação. O preço de um original é maior que metade de impressora (genéricos e remanufaturados saem mais em conta). Por outro lado, o toner que vem na impressora deve durar 1000 páginas e um de reposição 3000 páginas, Pelo meu consumo atual de papel só vou precisar comprar tonner daqui a uns 2 anos, o que é mais ou menos o que dura uma jato de tinta.

Avaliação da Samsung SCX-4200



A SCX-4200 é uma impressora multifuncional de tamanho médio e com aspecto tradicional, semelhante a uma fotocopiadora.
Uma vantagem em relação às impressoras de jato de tinta mais baratas é que o papel fica em uma gaveta. Além de ter uma boa capacidade (250 folhas), isto evita o papel ficar curvado e sujo.
Como é costume nas multifuncionais, um painel permite o uso como copiadora independente do microcomputador
Apesar da pausa inicial para aquecimento (cerca de 30 segundos), a impressão é muito boa e rápida. Nas primeiras vezes é até estranho, pois a folha impressa não fica toda para fora da impressora, ficando a sensação de que a impressora ainda não terminou.

O scanner também é bem mais rápido que o meu antigo (que conectava na paralela e segurava o micro nos longos minutos para transferir a imagem).

Em resumo, estou (até o momento) muito satisfeito com este equipamento.

sexta-feira, agosto 10, 2007

Algorítmos de Ordenação - parte VII

Vamos ver neste post o primeiro exemplo, que é um programa Windows para demonstração dos algorítmos.

A Interface Com o Operador

Para visualizar as chaves sendo ordenadas usei bolinhas coloridas que representam os números de 0 a 99. A cor varia conforme a chave do vermelho até o azul.

Um conjunto de radio buttons é usado para selecionar o algorítmo. Botões permitem embaralhar as chaves, executar a ordenação ao o final e executar a ordenação passo a passo. Outros dois botões permitem ver o diálogo Sobre e encerrar o programa.

Um listbox é usado para apresentar algumas mensagens de acompanhamento durante a ordenação.




O Código

Como originalmente eu pretendia enviar este programa para um site americano, os comentários e os nomes de variáveis e rotinas estavam em inglês. Refiz os comentários em português, mas mantive variáveis e rotinas com nomes em inglês, espero que isto não atrapalhe muito o entendimento.

A maior parte do código tem a ver com programação Windows. A tela do programa nada mais é que uma caixa de diálogo, com as chaves sendo desenhadas "na raça" (vide a rotina DrawKeys).

A decisão de permitir executar passo a passo complicou um pouco o programa. A rotina de ordenação é rodada em um thread separado do resto do programa. A cada passo a rotina de ordenação gera uma mensagem para avisar que concluiu o passo e aguarda a interface com o usuário (UI) sinalizar em um evento que a ordenação pode prosseguir. Isto foi aproveitado para segurar a execução (usando um timer do Windows), para dar um efeito visual melhor.

O conceito de passo não é muito rigoroso e varia bastante de um algorítmo para outro, portanto as velocidades de execução não são muito representativas.

As ordenações em si estão nas rotinas BubbleSort, ShellSort, HeapSort e QuickSort. Não foi feito esforço em otimizar o código; no caso do QuickSort é usado o elemento à esquerda como elemento de partição.

O projeto para o Microsoft VC 6, os fontes e o executável podem ser baixados daqui.

Na última parte vamos ver um programa de ordenação de arquivos, para execução por linha de comando sob Windows ou Linux. Isto é, supondo que eu ache tempo e consiga fazer. Até lá!

quinta-feira, agosto 09, 2007

Blogando às cegas

Desde a semana passada não consigo acessar diretamente o blogspot do trabalho. Como pode ser visto no link abaixo, o problema é razoavelmente generalizado nos usuários Speedy:

http://www.googlediscovery.com/2007/08/04/blogspot-esta-fora-do-ar-para-usuarios-speedy/

Ao que tudo indica o problema ocorre para determinadas combinações de IP nas duas pontas (o IP do Speedy no trabalho é fixo e tenho problemas também com o site www.advantech.com que tem IP parecido com o blogspot). Usando um proxy anônimo (daqueles que esconde o seu IP), tudo funciona.

Vamos ver quanto tempo demora para o problema ser solucionado.

quarta-feira, agosto 08, 2007

As Piores Desculpas na Informática

A lista abaixo é uma tradução/adaptação da que está aqui, o autor original é desconhecido.

Livros de Julho

Apesar da correria no trabalho, consegui ler dois livros em julho.

Harry Potter and The Deathly Hallows - J. K. Rowling

Graças à eficiência da Livraria Cultura, recebi o livro na manhã do dia 21 (dia mundial de lançamento). A conclusão da série do Harry Potter é um livro daqueles que você não consegue largar, concluí a leitura no próprio fim de semana (outro fator adicional era evitar ficar sabendo o final antecipadamente).

Ao contrário do livro final de A Series of Unfortunate Events, DH não deixa nada vago. É evidente o esforço da autora em esclarecer os místerios pendentes, quase todos os personagens que passaram nos outros livros ganham pelo menos uma menção ao longo do último volume. Como esperado, vários personagens morrem. Diversas teorias dos fãs se confirmaram e diversas outras não. Com tudo isto se chega a um final plenamente satisfatório. A crítica maior é sobre o depois do confronto final entre Harry e Voldemort, espero não estar entregando muito ao dizer que como muito fãs considero a autora exageradamente otimista. Mesmo assim, um livro imperdível.

Para quem ainda tiver dúvidas sobre o destino dos personagens após o último capítulo, a autora tem dado mais detalhes em entrevistas.

O livro (em inglês) pode ser encontrado facilmente em livrarias.

A For Andromeda - Fred Hoyle e John Elliot

Fred Hoyle foi um famoso astrônomo e autor do clássico The Black Cloud. Já comentei um outro livro dele, The Fifth Planet. A história deste livro foi escita em 1961 para uma série da BBC e tem vários elementos em comum The Black Cloud. Um rádio telescópio capta uma transmissão vinda de Andromedra, que se descobre ser o projeto de um computador e um programa para ser rodado nele. Construído o computador e executado o programa, ele se revela ser uma espécie de inteligência artificial.

Embora vários aspectos sejam anacrônicos (como a preocupação com a guerra fria), o livro é muito interessante e a idéia de se transmitir inteligência e vida através de sinais de rádio é no mínimo intrigante.

Infelizmente este livro está atualmente esgotado, a Amazon possui apenas exemplares oriundos de sebos.

terça-feira, agosto 07, 2007

Algorítmos de Ordenação - Parte VI

HeapSort

Este é o meu algorítmo preferido, apesar de ser pouco utilizado. O seu ponto chave é que tanto o tempo médio como o pior caso são proporcionais a N log(N).

Na prática, o tempo do HeapSort varia muito pouco com os dados sendo ordenados. Isto significa que se ele for rápido suficiente com um amostra de tamanho N, ele será rápido quaisquer que forem os dados de tamanho N que você jogar nele,

A idéia por trás do HeapSort é a mesma do torcedor do time eliminado num torneio "mata-mata". Olhando na figura abaixo, é claro que o time Amarelo é o campeão, mas quem é o segundo melhor? Não é preciso fazer um novo torneio completo, os candidatos são somente quem perdeu para o campeão (Marrom, Azul e Verde). O truque no HeapSort é usar uma estrutura de árvore para "lembrar" o resultado das comparações anteriores.

No HeapSort uma estrutura de árvore binária é obtida sem utilizar memória adicional guardando os dados de forma que
  • o pai da chave no índice k está no índice k/2
  • os filhos da chave no índice k estão nos índices 2*k e 2*k+1
Quando os filhos são sempre menores ou iguais aos pais, a estrutura é chamada de heap. A figura abaixo mostra um exemplo.

O HeapSort tem dois passos. No primeiro, transformamos os dados de entrada em um heap. Isto é feito partindo do topo e descendo a árvore movendo para cima os filhos que forem maiores que os seus pais. No final do primeiro passo, a primeira posição contém a maior chave. Entramos então no segundo passo, onde trocamos a primeira chave com a que está na última posição (colocando-a assim na sua posição final) e ajeitamos o heap para que a primeira posição contenha a maior chave das restantes. Este procedimento é repetido até que todas as chaves estejam na sua posição final.

O HeapSort não é particularmente rápido para N pequeno, mas para N grande é muito bom. O QuickSort é mais rápido na maioria das vezes, mas existe sempre o pior caso espreitando na esquina.

O HeapSort não requer memória adicional e não é estável.

Na próxima parte: o primeiro exemplo.

segunda-feira, agosto 06, 2007

Algorítmos de Ordenação - Parte V

QuickSort - Ordenação por troca de partições

Este algorítmo foi inventado por C. A. R. Hoare em 1962 e é provavelmente o mais popular algorítmo de ordenação. Ele é rápido, mas também um pouco manhoso.

A idéia básica do algorítmo é selecionarmos uma das chaves (o elemento de partição) e re-arranjamos os dados para que as chaves à esquerda do elemento de partição sejam anteriores a ela (mas não necessariamente em ordem) e as chaves à direita sejam posteriores. Repetimos o processo para as duas partições e assim por diante, até que as partições tenham um único elemento; neste ponto todos os dados estão ordenados.

Por exemplo, vamos supor que nossas chaves são [6909 6508 6407 6412 6512] e escolhemos o 6508 como elemento de partição. Um possível particionamente é [6407 6412] 6508 [6909 6512].

Uma maneira simples de particionar N chaves K1, K2 ... Kn é selecionar a primeira delas como elemento de partição e percorrer as chaves a partir das duas pontas, trocando de lado os elementos quando necessário. Para isto usamos dois índices, um partindo da segunda chave (i) e o outro partindo da última (j). Avançamos i até acharmos uma chave maior que K1 (que portando deve ir para a direita) e recuamos j até acharmos uma chave menor que K1 (que deve ir para a esquerda). Neste ponto, temos duas chaves que estão em lados errados; nós as trocamos de lugar. Quando i alcançar j, trocamos de lugar Kj com K1, encerrando a partição.

A figura abaixo mostra uma ordenação pelo QuickSort.

O QuickSort em ação

O QuickSort tem uma natureza recursiva: após o particionamento nós usamos o mesmo algorítmo para ordenar as duas partições. Existem várias razões para não codificar o QuickSort como uma rotina recursiva:
  • Chamadas a rotinas tem um overhead alto: os parâmetros precisam ser colocados na pilha do processador, um novo stack frame precisa ser criado para os parâmetros locais, etc.
  • Chamadas a rotinas podem consumir uma quantidade razoável de espaço na pilha; esta quantidade não está totalmente sob o nosso controle.
  • Se a pilha ficar cheia, provavelmente não conseguiremos encerrar o programa de uma forma limpa.
O que devemos fazer é codificar o QuickSort de uma forma iterativa ao invés de recursiva, gerenciando nós mesmos a pilha. A questão chave é: qual o tamanho desta pilha? Na prática, esta pilha é bem pequena, desde que coloquemos nela primeiro a partição maior e depois a menor. Desta forma, na iteração seguinte começamos com a partição menor, que por sua vez gerará um número menor de subpartições. No pior caso, a cada vez as partições serão quebradas em duas subpartições de igual tamanho, portanto o tamanho da partição é dividido continuamente por dois (mais precisamente, o tamanho diminui um pouco mais, pois o elemento de partição não entra em nenhuma das duas subpartições). Portanto, com uma pilha com k elementos podemos ordenar 2k chaves. Ou, olhando pelo outro lado, para ordenar N chaves precisamos de uma pilha com log2(N) elementos. Por exemplo, para ordenar um milhão de chaves basta uma pilha com 20 elementos! Cada elemento na pilha contém apenas dois inteiros (os índices do início e fim da partição a ordenar), portanto não ocupam muito espaço.

O tempo médio do QuickSort é proporciona a N log(N). Infelizmente, o pior caso é proporcional a N2. Não apenas isto, escolhendo o elemento de partição da forma que descrevemos, o pior caso é quando as chaves já estão ordenadas! Neste caso, cada passo reduz o tamanho da partição de apenas uma chave (já que todas as outras serão maiores que ela). Muitas sugestões foram dadas sobre como tornar o pior caso mais improvável. Basicamente, devemos escolher melhor o nosso elemento de partição. Algumas maneiras típicas são:
  • escolher aleatoreamente
  • escolher a mediana dos elementos no inicio, fim e meio da partição
  • escolher a mediana de uma amostra das chaves
Todos estes aperfeiçoamentos aumentam o processamento, portanto o tempo médio irá aumentar. O pior caso continua sendo proporcional a N2, porém será mais difícil ele acontecer na prática.

Outro aperfeiçoamento que pode ser feito no QuickSort (e em outros) é usar um algorítimo mais simples (como a inserção direta) quando o número de elementos na partição for menor que um limite. Como já vimos, algorítimos mais simples costumam ser mais rápidos para N pequenos.

O QuickSort não é estável.

Na próxima parte vamos examinar o meu algorítmo preferido. Em seguida, nas duas partes finais, vamos finalmente ver código!