Já se discutiu anteriormente sobre quebra-cabeças sudoku com um mínimo de dicas. Em 2011-2012, Gary McGuire utilizou 7 milhões de horas do tempo de supercomputação para provar por busca exaustiva que o menor número de dicas que um sudoku válido (solução única) deveria ter é 17. Para quebra-cabeças com pistas rotacionalmente simétricas, o menor número de dicas de um sudoku válido é considerado como sendo 18. Mas não estamos aqui para falar deles; hoje, daremos uma olhada nos quebra-cabeças sem nenhuma dica: o sudoku desnudo. Cada um destes quebra-cabeças veio do livro Naked Sudoku (Philip Riley/Laura Taalman), publicado pela Puzzle Wright Press. Você pode obter mais informações sobre a matemática por trás e relacionada a sudoku no livro Taking Sudoku Seriously, de Jason Rosenhouse/Laura Taalman e publicado pela Oxford University Press. Para saber mais sobre o trabalho de Gary McGuire acerca do problema do número mínimo de dicas, veja o "Sudoku Checker" no site dele. Para dar uma olhada em algumas matemáticas relativas a sudoku sendo investigadas sem computadores, tente o artigo de Elizabeth Arnold, Rebecca Field, Stephen Lucas e eu mesma, chamado: "Minimal Complete Shidoku Symmetry Groups" publicado no Journal of Combinatorial Mathematics and Combinatorial Computing (Novembro de 2013).

Quebra-cabeça 1: Sudoku-produto

Adicionando estruturas à própria grade do quebra-cabeça, pode-se fornecer informação suficiente para que não seja necessária nenhuma dica ao jogo. No sudoku-produto, as regras são as mesmas do sudoku regular (números de 1 a 9 em cada linha e coluna e blocos 3x3), mas além disso não há números repetidos em nenhuma região colorida, e os pequenos números posicionados no topo de cada região indicam qual deve ser o produto resultante dos números escolhidos para aquela região. Dica para começar: 5s e 7s são mais fáceis de poscionar na grade que outros números. Use os fatores de divisibilidade a seu favor.

Quebra-cabeça 2: Sudoku-maior-que

Neste quebra-cabeça mais uma vez damos importância efetiva à posição dos valores numéricos, mas adicionamos uma estrutura de uma maneira diferente: desta vez, indicando quais células são maiores ou menores que suas vizinhas. No sudoku-maior-que aplicam-se as regras usuais do sudoku, mas além disso os sinais de "maior que" indicam qual entre dois números vizinhos é o maior, e os símbolos triangulares "maior que" indicam que um número é mais de uma unidade maior que seu vizinho. Dicas para começar: as células rosas e azuis podem ajudá-lo a posicionar alguns 1s e 9s; a seguir, tente posicionar 2s e 8s e assim por diante.

Quebra-cabeça 3: Sudoku-divisão

Como se fosse um híbrido entre os dois quebra-cabeças anteriores, o sudoku-divisão usa símbolos para indicar quando uma célula é um divisor de seu vizinho, onde A ⊂ B siginfica que "A divide B". Algumas células também estão separadas por um sinal "maior que" para indicar que uma célula é maior que a outra. Uma pergunta de bônus: Este tipo de quebra-cabeça sempre precisará de, ao menos, um sinal "maior que". Porque isso?

Sobre a autora: Laura Taalman é editora da coluna Puzzle Page. Este artigo saiu na revista MAA Focus, na edição de Ago - 2015/Set - 2015.

Solução do Sudoku-produto: abaixo, temos a solução do primeiro quebra-cabeça proposto.



Introdução
O projeto Saguí, sistema operacional de tempo real, foi um dos produtos gerados em um doutorado de 2004, que teve por objetivo a proposição de uma arquitetura de sensores em redes sem fio que tinha como características principais: a flexibilidade, que lhe permitiria adaptar-se às mais variadas aplicações que fizessem uso em algum grau de sensores; o autogerenciamento, que emprestaria à arquitetura a capacidade de monitorar as grandezas físicas sob análise e até mesmo atuaria sobre as mesmas com base em algoritmos e sistemas operacionais de tempo real; a interatividade, que habilitaria a comunicação entre dispositivos para troca de dados ou transmissão de informações ou que possuísse uma interface homem-máquina embutida; e finalmente a preservação de energia, que oferecesse autonomia de operação à arquitetura por longos períodos de tempo sem a necessidade de troca da fonte geradora. A seguir, o detalhamento desse sistema operacional.

O microcontrolador 16F877/A
O microcontrolador é um componente fundamental para o desenvolvimento de uma arquitetura de sensores em redes sem fio. Responsável pelo gerenciamento de todas as funcionalidades existentes no nó, guarda ainda um programa computacional que contém toda a lógica que lhe empresta a capacidade de controle das atividades da plataforma. Diversas características desejáveis e comuns a muitos modelos de microcontroladores foram não apenas consideradas como recursos aderentes aos requisitos de desenvolvimento de um nó sensor como o uso desses dispositivos se tornou um padrão nessa tecnologia. Entre essas características desejáveis, destacam-se:

Para esta pesquisa utilizou-se como microcontrolador da plataforma o modelo PIC16F877/A produzido pela Microchip. Além do fato deste dispositivo conter a maioria das características citadas, alguns fatores determinaram a escolha desse fabricante:

A tabela abaixo apresenta as principais características do PIC16F887/A:

Recursos Funcionais
Arquitetura		RISC de 8 bits
Quantidade de instruções de comando		35
Memória FLASH para programação		8 kbytes
Memória RAM para armazenamento de variáveis		386 bytes
Memória ROM para armazenamento de variáveis		256 bytes
Capacidade máxima de processamento		5 MIPS
Funcionalidades gerenciáveis por interrupção		14
RECURSOS OPERACIONAIS
Temporizadores		3
Comparadores / Módulos PWM		2
Conversores A/D (resolução máxima: 10 bits)		6
Protocolos da Porta Serial Síncrona		I2C e SPI
USART		1
Portas Paralelas		1 de 8 bits
CARACTERÍSTICAS ELÉTRICAS
Tensão de Alimentação (típica)	5 V
Consumo de Corrente Máximo	15 mA[1]

A arquitetura do microcontrolador possui uma CPU (central processing unit, ou unidade central de processamento) e uma ULA (unidade lógica aritmética). A CPU pode ser entendida como o “cérebro” do dispositivo. Ela é a responsável pela correta seleção, decodificação e execução de cada instrução contida na memória de programação. Em operações aritméticas e lógicas, trabalha em conjunto com a ULA, que é uma unidade de 8 bits capaz de executar operações de adição, subtração, deslocamento e lógicas. As 35 instruções de comando, executadas pela CPU, são baseadas em mnemônicos e formam a linguagem assembly que permite a programação do microcontrolador bem como a configuração de seus recursos operacionais. Com estas instruções é possível montar programas que implantem funções matemáticas, filtros digitais ou mesmo um sistema operacional de tempo real completo. A velocidade de processamento do microcontrolador depende do modelo, sendo que para o PIC16F877/A existem versões que rodam a 4, 8, 16 e 20 MHz. Entretanto, deve-se observar que esta frequência de oscilação é a do cristal acoplado externamente ao dispositivo. O ciclo de máquina do microcontrolador opera a 1/4 da velocidade do cristal externo, como se observa na figura a seguir:

Desse modo, para 20 MHz, o ciclo de máquina trabalha a 5 milhões de instruções por segundo, ou MIPS. Dependendo da instrução de comando, ela consome um ou dois ciclos de máquina para ser completamente executada. Na tabela abaixo, temos s relação de comandos mnemônicos do PIC16F877/A, com os respectivos ciclos de máquina consumidos e flags afetados:

CONJUNTO DE INSTRUÇÕES DO PIC16F877/A
Mnemônicos operandos		Descrição	Ciclos	Status afetados
OPERAÇÕES COM REGISTRADORES ORIENTADAS A BYTE
ADDWF	f, d	Soma W e f	1	C, DC, Z
ANDWF	f, d	Operação lógica "E" de W com f	1	Z
CLRF	f	Limpa f	1	Z
CLRFW	-	Limpa W	1	Z
COMF	f, d	Complementa f	1	Z
DECF	f, d	Decrementa f	1	Z
DECFSZ	f, d	Decrementa f, pula se igual a zero	1 (2)
INCF	f,d	Incrementa f	1	Z
INCFSZ	f, d	Incrementa f, pula se igual a zero	1 (2)
IORWF	f, d	Operação lógica "OU" de W com f	1	Z
MOVF	f, d	Move f	1	Z
MOVWF	f, d	Move W para f	1
NOP	-	Nenhuma operação	1
RLF	f, d	Gire f à esquerda através da operação "Leva 1" ('Carry')	1	C
RRF	f, d	Gire f à direita através da operação "Leva 1" ('Carry')	1	C
SUBWF	f, d	Subtrai W de f	1	C, DC, Z
SWAPF	f, d	Permuta registrador em f	1
XORWF	f, d	Operação lógica "OU EXCLUSIVO" de W com f	1	Z
OPERAÇÕES COM REGISTRADORES ORIENTADAS A BIT
BCF	f, b	Limpa bit de f	1
BSF	f, b	Ajusta bit de f	1
BTFSC	f, b	Testa bit de f, pula se igual a zero	1
BTFSS	f, b	Testa bit de f, pula se igual a um	1
OPERAÇÕES DE CONTROLE E LITERAIS
ADDLW	k	Soma literal e W	1	C, DC, Z
ANDLW	k	Operação lógica "E" de literal com W	1	Z
CALL	k	Chama sub-rotina	2
CLRWDT	-	Limpa o temporizador Watchdog	1	TO, PD
GOTO	k	Vá para o endereço	2
IORLW	k	Operação lógica "OU" de literal com W	1	Z
MOVLW	k	Move literal para W	1
RETFIE	-	Retorna de interrupção	2
RETLW	k	Retorna com literal em W	2
RETURN	-	Retorna de sub-rotina	2
SLEEP	-	Fique em modo de hibernação	1	TO, PD
SUBLW	k	Subtrai W de literal	1	C, DC, Z
XORLW	k	Operação lógica "OU EXCLUSIVO" de literal com W	1	Z

Ainda assim, é possível processar um grande número de instruções mnemônicas a cada segundo. Outra característica fundamental deste microcontrolador são as interrupções. Interrupções são eventos aleatórios ou pré-determinados no tempo responsáveis pelo desvio da execução do programa de um determinado ponto para outro, a fim de realizar uma nova tarefa. Os temporizadores, comparadores, PWM (pulse width modulator, ou modulador de largura de pulsos), conversores Analógico/Digitais, porta paralela e o USART (universal synchronous asynchronous receiver transmitter, ou transmissor receptor síncrono assíncrono universal. Protocolo utilizado, por exemplo, nas comunicações de portas seriais RS-232), entre outros, possuem a capacidade de gerar uma interrupção no programa em execução. De fato, o PIC16F877/A possui um total de 14 fontes diferentes de interrupção. A figura abaixo apresenta todos os registradores associados a cada uma das possíveis fontes de interrupção:

 

Para que a CPU saiba exatamente em que posição do programa se encontrava antes de ocorrer a interrupção e voltar para lá após o tratamento da mesma, ela se vale de um mecanismo interno denominado pilha. A pilha é uma estrutura de memória capaz de armazenar até oito endereços de programa distintos, ou seja, até oito posições às quais a CPU deverá retornar, uma a uma, por ordem decrescente de ocorrência. Desse modo, se ocorrerem nove interrupções sem que a CPU chegue a retornar da oitava, a primeira posição da pilha (relativa à primeira interrupção gerada) será apagada para dar lugar à nona. Para o PIC16F877/A não existe a possibilidade de ler as posições de programa armazenadas na pilha e salvá-las em posições da memória, por exemplo. O último recurso a ser comentado é o temporizador Watchdog. O watchdog é um oscilador RC interno ao chip que não exige nenhum componente externo para funcionar. Este circuito trabalha separadamente do oscilador a cristal e gera interrupções mesmo quando o microcontrolador é posto em hibernação pelo comando SLEEP. A temporização do watchdog também é ajustável através de 3 flags. O watchdog seria muito útil não fossem dois fatores:

Em resumo, o watchdog é um circuito cuja idéia é muito boa na teoria, mas de pouca valia na prática.

Teoria de um sistema operacional de tempo real
Define-se como sistema operacional de tempo real, ou SOTR, aquele em que o correto funcionamento computacional não depende apenas de uma lógica correta mas também do momento, ou instante no tempo, em que o resultado é gerado. Em outras palavras, uma resposta atrasada ou adiantada a um evento é uma resposta errada. Note-se que tempo real não significa necessariamente rápido; significa apenas que um determinado sistema tem eventos com restrições de tempo que devem ser respeitados para evitar sua falha [1]. Os sistemas de tempo real lidam com periféricos especiais, tais como sensores e atuadores, para aplicações em automação industrial, controle de tráfego (rodoviário, aéreo), sistemas médicos (radioterapia), entre outros. Muitas vezes a aplicação e o periférico estão fortemente integrados, de tal sorte que o código da aplicação confunde-se com o código que processa a informação gerada pelo periférico [2]. A tecnologia de nós sensores faz uso intensivo de SOTR, onde são gravados na memória de programação do microcontrolador. O gerenciamento de cada periférico de um nó sensor pelo SOTR constitui-se em uma tarefa. Assim, converter o sinal de um sensor analógico para digital pode ser entendido como uma tarefa; transformar o sinal digitalizado em um número decimal, outra tarefa; armazenar o valor obtido em um banco de memória não volátil ou transmitir esse dado para outro nó por radiofrequência ou ainda apresentá-lo em um mostrador de cristal líquido para um usuário, todas são consideradas tarefas para fins de desenvolvimento de SOTR. Mesmo as interrupções geradas pelo hardware do próprio microcontrolador são entendidas como tarefas. Estas tarefas, executadas em uma base temporal, são os referidos eventos com restrições de tempo. Por exemplo, marcar as horas no nó ou efetuar uma leitura no ambiente por um sensor a cada 'X' unidades de tempo. Para realizar estas operações, o sistema possui pelo menos um temporizador implantado em hardware e configurado em software responsável por gerar interrupções com uma dada frequência. O SOTR utiliza esse temporizador como base de tempo para executar suas tarefas [2][5]. As restrições de tempo associadas às tarefas estão na forma de períodos e tempos-limites. O período é o intervalo de tempo entre cada ciclo de tarefas repetitivas ou periódicas e o tempo-limite é o intervalo de tempo máximo ao fim do qual uma tarefa deve estar finalizada, do contrário falhará [1]. Por consequência, o cálculo do período é um parâmetro de projeto importante no desenvolvimento de SOTR e que depende da quantidade total de tarefas periódicas a serem gerenciadas pelo sistema e do tempo limite de cada uma. A estrutura computacional responsável por coordenar os períodos de tempo consumidos por um conjunto de tarefas periódicas bem como determinar que tarefa deve ser executada em um determinado momento é denominada agendador ou scheduler. Uma vez que o requisito básico de um SOTR é a previsibilidade, todas as tarefas e seus requisitos computacionais devem ser conhecidos a priori, sem o quê o scheduler não será capaz de garantir que os tempos-limites do sistema sejam alcançados [3].  Serão abordados dois algoritmos bastante utilizados na determinação do período de tempo de um sistema; o primeiro é chamado de Razão Monotônica [4]. Diz-se que uma tarefa é agendável se a soma de sua preempção, execução e obstrução (ou interrupção) forem menores que o seu tempo-limite; por extensão, um sistema será agendável se todas as tarefas finalizarem com sucesso dentro de seus respectivos limites de tempo. Para verificar se um sistema é ou não agendável, dois testes são aplicados nesse algoritmo: o Limite de Utilização e o Tempo de Resposta. Dado o tempo computacional Ci para a realização de uma tarefa e Ti o período entre execuções da tarefa i, a utilização da CPU por essa tarefa pode ser calculada pela equação:

Para um agendamento baseado na Razão Monotônica, a utilização do processador por n tarefas é dada por:

U(n) converge assintoticamente para ln(2), ou 69%, para n >> 1. O teste do Limite de Utilização oferece uma análise da capacidade de agendamento de um sistema comparando a utilização calculada para um conjunto de tarefas com o total de utilização teórico dessas mesmas tarefas, conforme a inequação abaixo:

Se a inequação acima for satisfeita, todas as tarefas estarão dentro de seus tempos-limites. Se a utilização calculada for maior que 100%, o sistema terá problemas de agendamento das tarefas. Entretanto, se a utilização total estiver entre o limite de utilização e 100%, o teste é inconclusivo, sendo necessário o uso do teste do Tempo de Resposta. Este teste exige o cálculo do tempo de resposta de cada tarefa, de modo que se esse tempo de resposta for menor que o seu correspondente período, o sistema é agendável. A equação abaixo mostra o cálculo do tempo de resposta an de uma tarefa i:

O teste termina quando a_n+1 = a_n. O sistema será agendável se cada tempo de resposta terminar antes de seu tempo-limite. O cálculo do período do sistema deve incluir o somatório de todos os tempos-limites das tarefas periódicas e dos servidores aperiódicos esporádicos através da análise dos algoritmos do limite de utilização e do tempo de resposta, afim de que o sistema seja agendável nessa estrutura. O outro algoritmo bastante utilizado na determinação do período de tempo de um sistema é comumente denominado Executivo Cíclico ou Agendamento Round-Robin [6]. Neste esquema, fatias de tempo são associadas a cada processo em porções iguais, sem prioridade; assim, uma tarefa é executada por completo antes que a próxima entre em execução. Deste modo, não existe o perigo de uma tarefa ficar incompleta pelo início de outra, o que torna impossível a geração de interrupções por hardware pelo microcontrolador durante um período de execução de tarefas. A figura a seguir ilustra este tipo de agendamento:

Muitos SOTR não estão limitados a tarefas periódicas executadas regular e monotonicamente, incluindo também tarefas aperiódicas. Um exemplo de tarefa aperiódica é o pressionar de um botão de teclado para visualização de informações no mostrador de um nó sensor que possua interface homem-máquina. Essa ação é aleatória porque não segue o período de execução das tarefas periódicas gerenciadas pelo scheduler, ou seja, é um evento de ocorrência não previsível. Entretanto, as tarefas aperiódicas podem ser incluídas no modelo de agendamento por razão monotônica pela inclusão de um ou mais servidores aperiódicos esporádicos. Um servidor aperiódico esporádico é uma tarefa conceitual que aloca uma parcela de tempo de execução da CPU depois que um período de execução de tarefas periódicas tenha sido encerrado. A implantação de um servidor aperiódico esporádico transforma um evento aleatório em uma tarefa periódica como outra qualquer. A ordem de execução de um conjunto de tarefas periódicas é determinada em função de suas prioridades. No algoritmo da razão monotônica, quanto menor o tempo de utilização da CPU por uma tarefa, maior a sua prioridade; o quão crítica é uma tarefa em relação à outra não é levado em conta neste algoritmo. Além disso, a execução de uma tarefa é sempre consistente com sua prioridade: uma tarefa de menor prioridade nunca é executada quando outra de maior prioridade está pronta para rodar. Um SOTR preemptivo tem como grande trunfo ser capaz de controlar as interrupções geradas por hardware no momento em que elas ocorrem, definindo que tarefa deve ser executada naquele instante em função de sua prioridade. Para se implantar um sistema preemptivo autêntico, é preciso ser capaz de manipular a pilha do microcontrolador [5].

Visão geral do sistema operacional Saguí
O Saguí foi desenvolvido em assembler, utilizando em sua concepção e construção os conceitos de um sistema operacional de tempo real que mescla características do agendamento por razão monotônica com as do agendamento round-robin, apresentados no tópico anterior. Como o PIC16F877/A não oferece como recurso a manipulação de sua pillha, decorre que o Saguí também não é, de fato, um sistema preemptivo. A execução das tarefas periódicas e aperiódicas é realizada sequencialmente, onde a próxima tarefa só começa quando a anterior termina, dentro de fatias de tempo de 125 milissegundos cada, ajustando-se o temporizador Timer1 do PIC16F877/A, nos moldes do agendamento round-robin. Com isso, a cada segundo um total de 8 interrupções por temporização do Timer1 são disparadas. Ressalte-se que é possível alterar esta base de tempo no Saguí, aumentando ou diminuindo o seu intervalo. Entretanto, é possível atribuir uma "prioridade" às tarefas, executando primeiro aquelas que consomem menor tempo de CPU ou que sejam mais restritivas entre intervalos de execução. Como as fatias de tempo de 125 ms são estabelecidas através de interrupção do Timer1, é preciso que as fontes das interrupções estejam habilitadas; em outras palavras, uma fatia de tempo deve ser suficiente para que sejam executadas, no pior caso, todas as tarefas existentes. Para gerenciar as diversas fontes de interrupções geradas por hardware no microcontrolador, sejam elas periódicas ou aperiódicas, desenvolveu-se uma Rotina do Serviço de Interrupções, ou RSI. A função da RSI é rastrear as interrupções geradas e identificar a origem das mesmas. Uma vez identificada as fontes das interrupções, a RSI passa a informação ao scheduler, que através do agendamento round-robin, começa a verificar qual ou quais tarefas devem ser executadas. Uma vez concluídas as tarefas, respeitado o limite de utilização, o scheduler devolve o controle à RSI, que fica monitorando o estado do Timer1 até que gere uma nova interrupção, repetindo-se todo o ciclo. Desse modo, quanto melhor o cálculo do tempo computacional C consumido por cada tarefa, mais preciso será o cálculo do limite de utilização da CPU, de vital importância para que o sistema como um todo seja agendável, ou seja, opere corretamente. É importante frisar que, durante a execução da RSI, passando pelo scheduler e pela execução das tarefas, até o retorno da RSI, os flags de interrupções do PIC16F877/A ficam habilitados, mas o flag GIE de interrupções globais (responsável por posicionar o ponteiro do programa para o vetor 0x04, que cuida das interrupções) fica desabilitado. Com isso, os eventos que alteram o estado dos flags associados a cada interrupção funcionam ininterruptamente, mas a interrupção propriamente dita, gerada por hardware, permanece inativa. É responsabilidade da RSI identificar e tratar todas as interrupções geradas, e ajustar o estado dos flags associados a cada interrupção ativada, via software.

Detalhamento do sistema operacional Saguí
O cerne do sistema operacional de tempo real Saguí é constituído por dois blocos principais: a rotina do serviço de interrupções e o scheduler, que serão detalhados a seguir. Não é objetivo deste artigo ensinar assembler; parte-se do princípio de que o leitor tenha pleno domínio dessa linguagem e conheça o funcionamento do microcontrolador PIC16F877/A e suas particularidades.

A rotina do serviço de interrupções e o scheduler
Toda vez que ocorre um evento indicativo de uma interrupção no PIC16F877/A, o respectivo flag tem seu estado alterado, indicando a ocorrência do evento que monitora. A rotina do serviço de interrupções do Saguí, indicada pela etiqueta RSI_INI, é acionada a cada estouro do Timer1, que a seu turno dispara o flag associado a este evento (TMR1IF). Logo em seguida, a RSI limpa o flag TMR1IF, deixando o microcontrolador apto a identificar uma nova interrupção por estouro do Timer1 e ajusta o valor do TMR1H para 0xF0, afim de que uma nova interrupção seja disparada nos próximos 125 ms:

RSI_INI
  BCF       STATUS, RP0
  BCF       PIR1, TMR1IF
  MOVLW     0XF0
  MOVWF     TMR1H

Como o sistema operacional Saguí utiliza o agendamento round-robin, onde cada tarefa é executada sequencialmente e sem interrupções, torna-se desnecessário salvar o estado dos registradores de trabalho STATUS e W do microcontrolador. O cálculo do valor armazenado no registrador TMR1H para gerar uma interrupção a cada 125 ms será explicado no próximo tópico: Configuração inicial do PIC16F877/A. A seguir, a RSI inicia a identificação de todas as possíveis fontes de interrupção no microcontrolador, verificando o estado dos respectivos flags nos registradores PIR1 e INTCON:

  BTFSC     INTCON, T0IF
  BSF       TA_APTA0, TMR0_INT
  BTFSC     INTCON, RBIF
  BSF       TA_APTA0, RBIF_INT
  BTFSC     INTCON, INTF
  BSF       TA_APTA0, INTF_INT
  BTFSC     PIR1, PSPIF
  BSF       TA_APTA1, PSIF_INT
  BTFSC     PIR1, ADIF
  BSF       TA_APTA1, ADIF_INT
  BTFSC     PIR1, RCIF
  BSF       TA_APTA1, RCIF_INT
  BTFSC     PIR1, TXIF
  BSF       TA_APTA1, TXIF_INT
  BTFSC     PIR1, SSPIF
  BSF       TA_APTA1, SPIF_INT
  BTFSC     PIR1, TMR2IF
  BSF       TA_APTA1, TMR2_INT

As variáveis TA_APTA0 e TA_APTA1 (criadas no sistema operacional Saguí) servem para indicar quais flags tiveram seus estados alterados por conta de suas interrupções, habilitando tarefas aperiódicas a rodar. O próximo passo da RSI é identificar, entre todas as tarefas periódicas, aquelas que estão aptas a rodar na fatia de tempo corrente:

TP0
  DECFSZ    CT_TP0, F
  GOTO      TP1
  BSF       TP_APTA, 0
TP1
  DECFSZ    CT_TP1, F
  GOTO      TP2
  BSF       TP_APTA, 1
TP2
  DECFSZ    CT_TP2, F
  GOTO      TP3
  BSF       TP_APTA, 2
TP3
  DECFSZ    CT_TP3, F
  GOTO      TP4
  BSF       TP_APTA, 3
TP4
  DECFSZ    CT_TP4, F
  GOTO      TP5
  BSF       TP_APTA, 4
TP5
  DECFSZ    CT_TP5, F
  GOTO      TP6
  BSF       TP_APTA, 5
TP6
  DECFSZ    CT_TP6, F
  GOTO      TP7
  BSF       TP_APTA, 6
TP7
  DECFSZ    CT_TP7, F
  GOTO      SCHEDULER
  BSF       TP_APTA, 7

Neste trecho do programa, testam-se até 8 tarefas periódicas. Cada tarefa contém um contador CT_TP<n>, previamente carregado com o número de períodos (ou seja, a quantidade de fatias de tempo) entre execuções da tarefa. Toda vez que a RSI é acionada, cada um dos contadores das 8 tarefas periódicas é decrementado de um período. Se o contador zerar, o flag da correspondente tarefa periódica apta a rodar é 'setada' na variável TP_APTA<n>. Observe como isto funciona no esquema a seguir:



Na fatia de tempo T+1 as tarefas periódicas P1 e P4 entraram em execução em função do resultado das variáveis CT_TP<n>, e as tarefas aperiódicas A8 e A3 geraram uma interrupção, alterando os respectivos estados de seus flags de controle nos registradores INTCON ou PIR1. Neste intervalo, as tarefas P1 e P4 estavam aptas a rodar e o scheduler as colocou em execução. Na fatia de tempo seguinte, T+2, entraram em execução através do scheduler: as tarefas periódicas P1 e P5, e as tarefas aperiódicas A3 e A8 (que já estavam aptas a rodar no intervalo T+1), e as tarefas aperiódicas A2 e A5 geraram interrupções (a tarefa A2 gerou duas). Isto significa que na próxima fatia de tempo T+3 serão executadas as tarefas periódicas eventualmente aptas a rodar bem como as tarefas aperiódicas A2 (apenas uma vez) e A5. É desse modo que as tarefas aperiódicas são transformadas em servidores aperiódicos esporádicos, que entram no agendamento round-robin como se fossem tarefas periódicas. De fato, à exceção das tarefas periódicas (que dependem todas do Timer1) as demais tarefas são aperiódicas e originam-se de uma das possíveis fontes de interrupção rastreadas no código acima. A faixa preta no início de cada fatia de tempo corresponde ao tempo gasto para processar tanto a RSI quanto o scheduler (latência). Se durante esse ínterim ocorrer alguma interrupção que dispare uma tarefa aperiódica antes da verificação das tarefas aptas a rodar pela RSI, ela será executada na mesma fatia de tempo; do contrário, ela será executada na próxima. O esquema acima funciona corretamente desde que o flag de interrupções globais GIE esteja desabilitado. Depois de verificados todos os contadores das tarefas periódicas, e ajustadas aquelas aptas a rodar, a RSI passa o controle ao scheduler, que iniciará a execução das tarefas:

SCHEDULER
  BTFSC     TP_APTA, 0
  CALL      TP0_EXEC
  BTFSC     TP_APTA, 1
  CALL      TP1_ EXEC
  BTFSC     TP_APTA, 2
  CALL      TP2_ EXEC
  BTFSC     TP_APTA, 3
  CALL      TP3_ EXEC
  BTFSC     TP_APTA, 4
  CALL      TP4_ EXEC
  BTFSC     TP_APTA, 5
  CALL      TP5_ EXEC
  BTFSC     TP_APTA, 6
  CALL      TP6_ EXEC
  BTFSC     TP_APTA, 7
  CALL      TP7_ EXEC
  BTFSC     TA_APTA0, TMR0_INT
  CALL      TA0_ EXEC
  BTFSC     TA_APTA0, RBIF_INT
  CALL      TA1_ EXEC
  BTFSC     TA_APTA0, INTF_INT
  CALL      TA2_ EXEC
  BTFSC     TA_APTA1, PSIF_INT
  CALL      TA3_ EXEC
  BTFSC     TA_APTA1, ADIF_INT
  CALL      TA4_ EXEC
  BTFSC     TA_APTA1, RCIF_INT
  CALL      TA5_ EXEC
  BTFSC     TA_APTA1, TXIF_INT
  CALL      TA6_ EXEC
  BTFSC     TA_APTA1, SPIF_INT
  CALL      TA7_ EXEC
  BTFSC     TA_APTA1, TMR2_INT
  CALL      TA8_ EXEC

Neste trecho de código, o scheduler chama cada uma das 8 tarefas periódicas, bem como as restantes 9 tarefas aperiódicas. O comando CALL desvia o ponteiro do programa para uma etiqueta TP<n>_EXEC periódica ou TA<n>_EXEC aperiódica, que contêm o código de execução da correspondente tarefa:

TP<n>_EXEC
  BCF       TP_APTA, n
  MOVLW     0X03
  MOVWF     CT_TP<n>
  INCLUDE   "TAREFA_PERIODICA_<n>.INC"
  RETURN

TA<n>_EXEC
  BCF       TA_APTA<0/1>, <FLAG>
  BCF       INTCON, RBIF
  INCLUDE   "TAREFA_APERIODICA_<n>.INC"
  RETURN

Para cada tarefa periódica n, limpa-se o correspondente flag indicativo de tarefa apta a rodar na variável TP_APTA e recarrega-se o contador CT_TP<n> (no exemplo, o período da tarefa é de 3 fatias de tempo). De modo análogo, para cada tarefa aperiódica n, limpa-se o correspondente flag indicativo de tarefa apta a rodar em uma das variáveis TA_APTA0 ou TA_APTA1, bem como limpa-se o flag que gerou a interrupção em um dos registradores (INTCON ou PIR1) do microcontrolador (no exemplo, limpou-se o flag RBIF do INTCON). O comando INCLUDE permite inserir um arquivo (com extensão .INC) contendo todo o código para a execução da tarefa propriamente dita. O comando RETURN faz com que o ponteiro do programa volte ao scheduler na linha seguinte ao comando CALL que fez a chamada à respectiva etiqueta. Desse modo, o agendamento round-robin executa as tarefas sequencialmente e sem interrupções. Finalizada a execução de todas as tarefas aptas a rodar em uma determinada fatia de tempo, o scheduler devolve o controle à RSI, conforme segue:

RSI_FIM
  BTFSS     PIR1, TMR1IF
  GOTO      RSI_FIM
  GOTO      RSI_INI

Neste trecho do código, o programa é colocado para verificar o estado do flag TMR1IF do registrador PIR1. Enquanto não houver o estouro do Timer1, o estado lógico do flag TMR1IF mantém-se inalterado e o ponteiro do programa é desviado à etiqueta RSI_FIM. Após o estouro do Timer1, o estado lógico do TMR1IF se altera e o programa é desviado para o início da Rotina do Serviço de Interrupções (etiqueta RSI_INI), recomeçando todo o ciclo.

Configuração inicial do PIC16F877/A
Para que o sistema operacional Saguí funcione corretamente, é necessário configurar tanto o hardware quanto o software do microcontrolador PIC16F877/A. No hardware, além do cristal que faz funcionar o ciclo de máquina do microcontrolador, será necessário incluir outro cristal para operar exclusivamente com o Timer1. Para bases de tempo compatíveis com o Sistema Internacional para medidas de tempo (segundos), será adotado um cristal que opere a 32,768 kHz. Este cristal será conectado aos pinos 15 (RC0/T1OSO/T1CKI) e 16 (RC1/T1OSI/CCP2) do PIC16F877/A, e cada terminal do cristal será ligado à terra por um capacitor de carga de 22pF, conforme consta na recomendação do resumo técnico TB097, da Microchip. O esquema a seguir apresenta o diagrama elétrico desta configuração:

Clique sobre a imagem para ampliar

O resumo técnico TB097 também dá uma sugestão de leiaute da placa de circuito impresso (PCI) para montar o oscilador a cristal para o Timer1 utilizando dispositivos SMD (Surface Mount Devices, ou dispositivos para montagem em superfície). A seguir, configura-se via software os registradores necessários para que o Timer1 responda adequadamente à configuração adotada no hardware:

TMR1_CONFIG
  BSF       STATUS, RP0
  BSF       PIE1, TMR1IE
  BCF       STATUS, RP0
  BCF       PIR1, TMR1IF
  BSF       INTCON, PEIE
  CLRF      TMR1L
  MOVLW     0XF0
  MOVWF     TMR1H
  MOVLW     0X0F
  MOVWF     T1CON
  GOTO      RSI_FIM

A etiqueta TMR1_CONFIG indica o início da configuração do Timer1. Primeiro, seleciona-se o banco 1 (BSF    STATUS,RP0), onde se encontra o registrador PIE1. Neste registrador, 'seta-se' o flag TMR1IE, habilitando a interrupção por estouro do Timer1. Em seguida, seleciona-se o banco 0 (BCF    STATUS,RP0) onde se encontram os demais registradores: o INTCON, onde 'setamos' o flag PEIE, responsável por habilitar toda fonte periférica de interrupção; o PIR1, onde 'setamos' o flag TMR1IF, responsável por indicar o estouro do Timer1; e os registradores do Timer1 operando como temporizador: TMR1H-TMR1L. Estes registradores trabalham conjuntamente, como um único contador de 16 bits. Eles incrementam de 0x0000 até 0xFFFF, quando então há o estouro da contagem (para reiniciarem em 0x0000). É nesse momento do estouro que o flag TMR1IF tem seu estado alterado, indicando o disparo da interrupção por temporização. A contagem máxima (0xFFFF) corresponde a 65.536 em notação decimal. Com um cristal de 32.768 Hz, o Timer1 gerará um estouro a cada 2 segundos, ou seja:

Para gerar uma interrupção a cada 125ms, os registradores TMR1H-TMR1L devem ser configurados com um total de:

Ou seja, ajustando-se os registradores com 61.440 ciclos, é como se já tivesse transcorrido 1,875 segundo, restando 0,125 segundo ou 125ms para a próxima interrupção. Os 61.440 ciclos em notação decimal correspondem a 0xF000 em notação hexadecimal. Então, basta ajustarmos o TMR1H com o valor 0xF0 e o TMR1L com 0x00 (ou usando o mnemônico CLRF, que fornece o mesmo resultado). A partir do momento em que o sistema entra em regime operacional, ou seja, toda vez que a RSI é acionada, basta ajustarmos apenas o valor do TMR1H com 0xF0, pois o TMR1L terá reiniciado a contagem e já estará incrementando após o estouro do Timer1. Finalmente, armazena-se o valor 0x0F no registrador T1CON, responsável pela configuração do Timer1, o que corresponde a 1111 binário. Este registrador contém 6 flags configuráveis, conforme abaixo:

Os flags T1CKPS1 e T1CKPS0 (bits 5 e 4) formam o seletor de pré-escala do clock de entrada do Timer1 (gerado pelo cristal de 32,768 kHz). Estes flags podem assumir os seguintes valores:

• T1CKPS1-T1CKPS0 = 11 → pré-escala de 1:8
• T1CKPS1-T1CKPS0 = 10 → pré-escala de 1:4
• T1CKPS1-T1CKPS0 = 01 → pré-escala de 1:2
• T1CKPS1-T1CKPS0 = 00 → pré-escala de 1:1

Para os flags T1CKPS1-T1CKPS0 foi utilizado o valor 00, o que significa que cada pulso gerado pelo cristal de 32,768 kHz corresponde a um incremento na contagem dos registradores TMR1H-TMR1L. O flag T1OSCEN (bit 3, do controle de habilitação do oscilador do Timer1) é ajustado em 1, ou seja, o oscilador do Timer1 fica habilitado. O flag T1SYNC (bit 2, do controle de sincronização da entrada do clock externo do Timer1) é ajustado em 1, de modo que o Timer1 não sincroniza com a entrada do clock externo (do microcontrolador). O flag TMR1CS (bit 1, do seletor da fonte de clock do Timer1) é ajustado em 1, ou seja, o clock vem do pino RC0/T1OSO/T1CKI, onde está uma das pernas do cristal de 32,768 kHz. Finalmente, o flag TMR1ON (bit 0, que liga o Timer1) é ajustado em 1, habilitando a entrada em operação do Timer1 a partir de seu ajuste. A configuração do T1CON fica:

O que corresponde a 0x0F em hexadecimal. A partir desse momento inicial, o Timer1 começa a contar o tempo e o programa é desviado para a etiqueta RSI_FIM, que fica dentro da rotina do serviço de interrupções (RSI) aguardando o momento em que ocorra um novo estouro do Timer1. Antes, porém, que o temporizador comece a funcionar, é preciso ajustar todos os contadores das tarefas periódicas programadas, afim de que sejam decrementados a cada chamada da RSI. O código a seguir indica como isso é feito:

O início de qualquer programa no PIC16F877/A se dá pelo vetor 0x00, precedido do mnemônico ORG. Observe que a cada contador foi atribuído um número hexadecimal que corresponde ao intervalo de períodos entre execuções das tarefas aos quais estão associados. Dois ou mais contadores podem ter o mesmo valor, como é o caso dos contadores 0 e 3. Haverá um momento, que é o segundo pior caso, em que todas as tarefas periódicas serão executadas em uma mesma fatia de tempo. Esse momento é determinado pelo mínimo múltiplo comum entre os diferentes valores armazenados nos contadores; no exemplo acima, esses valores são: 3, 2, 8, 1, 13 (D em hexadecimal), 7 e 11 (B em hexadecimal), cujo m.m.c. é 24.024 em notação decimal. Ou seja, a cada 24.024 interrupções do Timer1 (ou ainda, a cada 24.024 x 0,125s = 3.003 segundos ou 50 minutos e 3 segundos) todas as 8 tarefas periódicas serão executadas na mesma fatia de tempo. O pior caso é aquele em que todas as tarefas aperiódicas sejam disparadas na 24.023^a interrupção, pois então, exatamente na 24.024^a interrupção todas as tarefas periódicas e aperiódicas estarão aptas a rodar. Para que a execução seja viável, o somatório dos tempos consumidos por cada uma das 17 tarefas mais o tempo de latência (ou seja, o tempo consumido para executar a RSI e o scheduler) tem que ser menor que o intervalo de uma fatia de tempo. É por esse motivo que a fatia de tempo no Saguí pode ser alterada, de modo a acomodar no pior caso a execução de todas as tarefas existentes no sistema. É imprescindível calibrar a fatia de tempo de modo que ela fique (na medida do possível) pouca coisa maior que o somatório dos tempos consumidos pelas tarefas mais o tempo de latência.

Os contadores das tarefas periódicas e os identificadores de tarefas aptas a rodar são todas variáveis criadas especificamente para o Saguí e ocupam um lugar específico dentro do PIC16F877/A, denominado Registradores de Propósito Geral. Os bancos 0, 2 e 3 possuem 96 bytes cada para armazenamento dessas variáveis e o banco 1, 80 bytes. É interessante do ponto de vista da eficiência operacional do sistema que as variáveis sejam criadas no mesmo banco em que estejam os registradores às quais se vinculem. Entretanto, num primeiro momento, criaremos as principais variáveis do Saguí no banco 0, pois o registrador INTCON é acessível em qualquer um dos quatro bancos e o registrador PIR1 é acessível no banco 0. Também os contadores das tarefas periódicas serão criadas no banco 0, o que não impede que se altere suas posições para outros bancos conforme a necessidade. Assim, temos:

As tarefas periódicas/aperiódicas eventualmente podem aplicar cálculos matemáticos para sua consecução; para atender a esta necessidade, lançamos mão de diversas rotinas matemáticas prontas para uso fornecidas pela própria Microchip. Estas rotinas também criam variáveis nos registradores de propósito geral, nas posições de memória 0x20 até 0x4B do banco 0 do microcontrolador. Por este motivo é que as variáveis do Saguí são criadas a partir do endereço 0x4C, no banco 0. Uma última providência é associar os parâmetros atribuídos às interrupções das tarefas aperiódicas a cada um dos bits das variáveis TA_APTA<n>. Assim, para a variável TA_APTA0, temos:

E para a variável TA_APTA1, vem:

Deste modo, o compilador saberá atribuir o parâmetro correto para cada bit, toda vez que for utilizado em uma variável. Com isto, é possível criar quantos parâmetros se queira, facilitando a leitura e qual a aplicação dos bits nas variáveis do sistema.

A fim de manter o sistema como um todo agendável, é necessário ter em conta o exato tempo consumido pela execução completa da RSI e do scheduler; em outras palavras, o tempo de latência. Será considerado o pior caso, ou seja, em que todas as tarefas (periódicas e aperiódicas) estejam aptas a rodar. Todos os mnemônicos utilizados consomem 1 ciclo de máquina para executar, à exceção dos comandos BTFSS, BTFSC e DECFSZ que consomem 2 ciclos de máquina se o teste condicional for verdadeiro e 1 ciclo de máquina se for falso. Os comandos CALL, RETURN e GOTO consomem 2 ciclos de máquina cada. Etiquetas não consomem tempo. As chamadas às tarefas (CALL) e os retornos das mesmas (RETURN) foram levados em conta no tempo consumido pela RSI, mas a execução propriamente dita, não. Somando os ciclos de máquina para o pior caso obtemos um consumo total de 178 ciclos; operando a 5 MIPS, o PIC16F877/A gastará 35,6μs para executar completamente a RSI mais o scheduler. Nestas condições, a latência utiliza 0,02848% dos 125ms disponíveis em uma fatia de tempo.

Limitações do sistema operacional Saguí
Como diz o ditado: "não existe almoço grátis". Esta máxima também vale para o Saguí. A seguir, estão listadas algumas limitações deste sistema operacional, com as quais deve-se lidar:

À exceção destas observações, o sistema operacional Saguí é versátil e atende a uma variada gama de aplicações que faça uso do microcontrolador PIC16F877/A.

Referências bibliográficas
[1] STEWART, D. B. Introduction to Real Time, Embedded Systems Programming: www.embedded.com, 2001.
[2] FARINES, J. M.; FRAGA, J. S.; OLIVEIRA, R. S. Sistemas de Tempo Real: Sistemas Operacionais, Escola de Computa-ção 2000 IME-USP. Palestra.
[3] SPRUNT, B. Aperiodic Task Scheduling for Real-Time Systems, Department of Electrical and Computer Engineering –Carnegie Mellon University, 1990. Tese de doutorado.
[4] FORMAN, N. Rate Monotonic Theory
[5] FARMER, J. A Real-Time Operating System for PIC16/17 Application Note 585, Microchip, 1994.
[6] D. KALINSKY ASSOCIATES A Survey of Task Schedulers White Paper / Introductory Course Reading Assignment: www.kalinskyassociates.com, 2004.