Sistemas de Computação 9 - Memória virtual

Bom pessoal, acho que vamos, finalmente, chegar ao fim (pelo menos como eu havia pensado) desta série de artigos sobre os elementos básicos de funcionamento dos sistemas de computação. Este último tópico, sobre memória virtual, vai ser dividido em duas partes. Na primeira parte vamos ver como virtualizar, do ponto de vista dos programas de aplicação, o endereçamento de instruções e operandos na memória via address translation. Na segunda parte vamos ver o algoritmo mais comum para administrar a alocação da memória real aos vários processos em execução sob controle do kernel do sistema operacional: demand paging.

Address translation

Pois bem. Para nossa primeira parte vamos precisar, assim como no caso do compartilhamento do tempo do processador, de uma mãozinha do hardware (e/ou do microcódigo) do processador. Este auxílio vem na forma da automação do processo de address translation, que calcula o endereço real de memória correspondente ao endereço virtual de uma instrução ou operando de instrução (e, em princípio, todas as referências a endereços de instrução ou de operandos de instrução são considerados virtuais).

O espaço de enderaçamento (address space) virtual, conforme visto pelos programas de aplicação, é um bloco contínuo de bytes de memória, cada byte identiicado por um endereço binário. Para efeito de exemplo vamos supor que estamos trabalhando coom um processador com endereços de memória de 32 bits. Então o espaço de endereçamento visualizado pelos programas de aplicação tem a aparência mostrada na figura abaixo (endereços binários expressos pelos seus equivalentes em hexadecimal).

Este address space virtual é dividido logicamente em páginas (pages) de tamanho fixo. No nosso caso de exemplo vamos supor que cada página tenha 4K bytes de tamanho. Então a visão lógica do address space virtual repartido em páginas fica como mostrado na próxima figura.

Então podemos ver que um endereço virtual tem uma estrutura lógica, com os 12 bits menos significativos (correspondentes aos 3 dígitos hexadecimais menos significativos) representando o deslocamento (displacement) em relação ao início da página, e com os 20 bits mais significativos (os 5 dígitos hexadecimais mais significativos) identificando o número da página (page number).

Por questões de ordem prática (minimizar a quantidade de memória usada pelo kernel para representar o mapa da memória virtual, que tende a ser uma tabela esparsa), a maioria dos processadores inclui mais um degrau no processo de address translation, considerando o número da página dividido logicamente em duas partes: número do segmento (segment number) e número da página. Assumindo que, no nosso caso de exemplo, o número da página tenha 12 bits e o número do segmento tenha 8 bits, a estrutura lógica do nosso endereço virtua de exemplo será da seguinte forma:

A memória real (aquela que está fisicamente instalada na máquina e que, geralmente, é bem menor que o address space virtual - 4G bytes no nosso exemplo) também é dividida logicamente em frames (molduras) com o mesmo tamanho das páginas do address space virtual (4K bytes no nosso caso de exemplo).

O objetivo desta estruturação lógica é, obviamente, permitir que haja um "descasamento" entre a localização física real de um byte na memória e a sua localização lógica do ponto de vista do programa de aplicação, e que esta localização física possa ser modificada, mesmo durante a execução do programa.

Para isto o kernel mantém uma tabela inicial chamada tabela de segmentos (segment table) cuja localização (segment table address) é armazenada em um local específico da memória real acessado pelo mecanismo de address translation do hardware. Cada entrada da segment table contém o endereço do início da tabela de páginas (page table) associada àquele segmento do address space virtual. No jargão técnico de programação o conteúdo de cada entrada na segment table é denominado um ponteiro (pointer) para a localização da page table associada ao segmento. No nosso caso de exemplo cada entrada da segment table tem, portanto, 4 bytes (32 bits) de tamanho.

Cada entrada de uma page table, por sua vez, contém o número do frame (frame number) - com 20 bits no nosso caso de exemplo - onde aquela página virtual está fisicamente armazenada. Cada entrada nas page tables tem de acomodar, além do frame number, mais três bits de controle. Então, arredondando para um número inteiro de bytes, no nosso caso exemplo o tamanho de uma entrada na page table é de: 20 bits do frame number + 3 bits de controle + 1 bit de arredondamento = 24 bits (3 bytes). A figura abaixo representa esquematicamente estas estruturas de dados criadas e mantidas pelo kernel.

Então, vejamos quando e como ocorre o processo de address translation. O quando é fácil: sempre que é necessário executar um acesso à memória. Isto corresponde às fases de instruction fetch, operand fetch, result store e load interrupt vector address into program counter, conforme a versão mais recente apresentada no artigo anterior desta série.

O como é assim. Todo endereço virtual é separado nos seus componentes: segment number, page number e displacement. Com estes componentes, e com os demais dados na segment table e nas page tables, efetua-se o cálculo do endereço real conforme mostrado na figura abaixo

Isto nos mostra como o endereço virtual é usado para calcular o endereço real correspondente, mas nada dissemos, ainda, sobre como gerenciar a alocação dos frames da memória real aos diversos processos em execução sob controle do kernel. Este é o papel do algoritmo que veremos a seguir.

Demand paging

Quando o kernel recebe uma requisição para iniciar um processo ele precisa alocar memória para o(s) programa(s) deste novo processo dentro do address space virtual. Isto é feito alocando-se o número apropriado de páginas virtuais livres contíguas nas page tables. Isto pode ser feito localizando-se nas page tabes já criadas entradas com o bit de controle V (valid) igual a zero, significando que aquelas páginas estão inválidas (portanto livres); ou então podem ser acrescentadas novas entradas na segment table (até o limite do tamanho do address space virtual) e suas  respectivas page tables. Em qualquer caso, a partir deste momento estas páginas são consideradas válidas (em uso), e os seus bits V são tornados iguais a 1.

Depois é feita a associação dos frames da memória real às páginas da memória virtual. Para isto o kernel mantém uma lista dos frames livres, conhecida como free list. Para cada página virtual alocada é retirada uma entrada da free list, o seu frame number é colocado na entrada correspondente da page table e o conteúdo da página, caso exista, é copiado para a memória real e para um arquivo externo de baixa latência de acesso (tipicamente em disco magnético) conhecido como arquivo de páginas (page file)

Durante o processo de alocação da memória real pode acontecer de não haver entradas suficientes na free list para satisfazer à necessidade de alocação do novo processo. Esta é uma das situações onde ocorre uma falta de página (page fault). A outra situação onde isto pode ocorrer é durante a sequência normal de execução dos processos, como veremos adiante.

Para solucionar a falta de página o kernel tem que fazer o "reabastecimento" da free list (free list replenishment). Antes de explicar como isto é feito temos que entender o significado e a utilização dos outros dois bits de controle (R e C) nas entradas das page tables.

Toda vez que ocorre uma referência (fetch) a uma instrução ou a um operando contido em uma página, então o seu bit R (reference) é ligado (tornado igual a 1). Periodicamente o kernel desliga (torna iguais a zero) os bits R de todas as páginas. Desta forma páginas que tenham o bit R desligado são páginas que não sofreram referência pelo seu processo pelo menos desde a últia vez em que todos os bits R foram desligados pelo kernel.

Toda vez que ocorre uma alteração (store) do conteúdo de uma página então o kernel liga o seu bit C (change) para indicar que o conteúdo desta página na memória real não é mais igual à sua cópia armazenada no page file. Este bit é desligado sempre que uma página é carregada em um frame de memória real, na alocação inícial dos processos ou na solução do segundo tipo de ocorrência dos page faults.

Assim a estratégia para localizar páginas favoráveis para reabastecer a free list é:

• Liberar (desligando o bit V) primeiro as páginas que tiverem o bit R igual a zero (não referenciadas recentemente) e o bit C igual a zero (não modificadas desde a sua carga na memória real). Como a cópia destas páginas no page file ainda é válida, elas podem ser reaproveitadas sumariamente;
• Se ainda forem necessárias mais páginas que as recuperadas pelo passo anterior, a próxima opção é liberar as páginas que tenham R=0 e C=1. Neste caso antes de reaproveitar o frame é necessário atualizar a cópia da página no page file, porque ela já sofreu alterações;
• Caso sejam necessárias mais páginas ainda, a última opção (e a mais danosa à performance) é selecionar páginas com R=1 e C=1, atualizando a cópia da página no page file antes do reaproveitamento do frame.

 Repare que as páginas liberadas desta forma pertencem a processos ativos. Portanto é provável que, em algum momento futuro, um processo tente acessar uma de sua páginas e ela tenha sido liberada (esteja com o bit V igual a zero). Este é o segundo caso pissível de ocorrência de page fault. Só que, neste caso, só é necessário encontrar um frame livre para acomodar a página faltante. Se a free list estiver vazia então o frame para acomodar a página faltante é selecionado com a mesma estratégia descrita acima.

Porque este algoritmo funciona? Desde que o volume de operações de I/O sobre o page file - conhecidas simplesmente como paging, ou page-in e page-out - não seja muito elevado, então o fato observado experiementalmente é que apenas as páginas mais referenciadas de cada processo (conhecidas como o active page set do processo) tendem a ficar na memória real. Claro que o ideal é que o sistema não tenha que fazer paging. Como isto raramente é viável economicamente (embora o preço decrescente dos chips de memória estejam alterando isto), um dos fatores críticos de performance do sistema é determinar até que ponto é tolerável a ocorrência de paging.

Múltiplos address spaces virtuais e compartilhamento de código

Para terminar este assunto só precisamos abordar dois detalhes.

O primeiro é justamente o que viabiliza a construção de sistemas operacionais onde cada um dos seus "processos" é um ambiente computacional virtual completo. Para isso o que precisamos, essencialmente, é permitir que cada processo acredite ter um address space virtual inteiro só para ele. Para conseguir isso basta criar uma segment table (e page tables associadas) para cada processo, e adaptar o cálculo de address translation a este fato.

O segundo detalhe é que neste tipo de ambiente é muito fácil fazer que múltiplos processos compartilhem segmentos da memória real entre eles. Basta fazer com que as respectivas entradas das segment tables de cada processo apontem para o mesmo conjunto de page tables, ou que entradas de page table de cada processo referenciem o mesmo frame number. Isto é especialmente útil se o sistema tive que executar instâncias de um mesmo programa em múltiplos processos distintos. Neste caso alocam-se páginas distintas para acomodar os operandos de cada instância, enquanto as instruções do programa podem ser mantidas em uma única instância física, mas referenciada como instâncias distintas nas segment e page tables dos processos.

Por ora é só. A menos que alguém tenha algum pedido específico, encerro esta série de artigos sobre sistemas de computação por aqui.

Sistemas de Computação 8 - Compartilhamento do tempo do processador

Muy bueno... pelo que vimos até agora existem alguns mistérios entre as coisas feitas pelo kernel do sistema operacional, e neste post vamos resolver um deles. Se, pelo que vimos da arquitetura Von Neumann e do ciclo fetch-execute, o processador só é capaz de executar um programa de cada vez (com a exceção óbvia das máquinas multiprocessadas e dos processadores com múltiplos núcleos) então como o sistema operacional consegue criar a ilusão de execução simultânea de vários programas?

A resposta é simples. Intercalando no tempo a execução dos vários programas do(s) usuário(s), e fazendo isto tão rápido que, para o observador humano, a aparência é de execução simultânea. Esta técnica é chamada de multitasking (multiprogramação), e o algoritmo mais popular para realizá-la é o time-sharing. Mas este algritmo necessita que o hardware (e/ou o microcódigo) implemente o mecanismo de interrupções (interrupts). Portanto vamos primeiro falar disso.

Interrupções:

Uma interrupção, como o nome indica, é um evento que provoca uma quebra na sequência normal do ciclo fetch-execute, através de um desvio incondicional para uma rotina de tratamento da interrupção (que tem de estar previamente carregada na memória, mas isto é papel do kernel durante a inicialização do sistema operacional) chamada interrupt handler.

A sinalização da interrupção pode ser gerada por algum elemento de hardware (ex.: o controlador de um dispositivo ao término de uma operação de I/O físico), ou pelo próprio programa em execução (este é o modo geral para invocar os serviços da API de system calls do sistema operacional). Cada tipo de interrupção suportado pelo processador possui um interrupt handler associado. Os endereços de memória correspondentes à primeira instrução de cada interrupt handler ficam armazenados em posições contíguas da memória, denominadas interrupt vector (IV).

Mas, para que este esquema possa funcionar, é necessário preservar o estado dos registradores do processador no momento da interrupção (em especial o program counter - PC), para que o programa que foi interrompido possa retornar a executar normalmente daquele ponto em diante. Isto é chamado de salvar o contexto do processo - que é o "apelido" para um programa executando sob o controle do kernel. Existem várias técnicas para salvar o contexto do processo. Por exemplo: usar uma estrutura de dados do kernel chamada stack (pelo que sei os processadores Intel desde o 8086 até o Pentium são assim), ou convencionar que cada rotina alvo de um desvio deve reservar memória e executar o salvamento do contexto da rotina de origem do desvio (como na programação assembly para mainframes IBM /370 e /370-XA. Creio que nas arquiteturas ESA/390 e z-Architecture ainda seja assim).

Ótimo. com todas estas peças no lugar, só precisamos agora mudar um pouquinho o nosso ciclo fetch-execute para incorporar a verificação da ocorrência de interrupções ao final da execução de cada instrução de máquina, tal como mostrado abaixo.

Como vocês podem ver existe também um mecanismo para temporariamente inibir o reconhecimento de interrupções pelo processsador. Isto é feito ligando/desligando bits de habilitação/desabilitação (enable/disable ou mask/unmask) em algum registrador de controle, um bit para cada tipo de interrupção suportada pelo processador. Quem faz uso disto? Tipicamente as rotinas do kernel, ou programas do usuário que invoquem funções ou serviços do sistema operacional que não possam ter sua execução interrompida.

Repare que a desabilitação (ou mascaramento) do reconhecimento de interrupções não elimina a sinalização da ocorrência da interrupção. Limpar a sinalização de interrupções pendentes são outros quinhentos, portanto quando a(s) interrupção(ões) voltarem a ser habilitadas o processador irá reconhecê-la(s).

Ao carregar no PC o endereço da primeira instrução do interrupt handler (contido no IV) temos o equivalente a um desvio incondicional do fluxo de execução para aquele endereço. As instruções de máquina do interrupt handler são executadas, então, da forma usual (podendo ou não, conforme o caso, ser interrompidas também). Cada rotina interrupt handler tem que, obrigatoriamente, como sua última atividade, restaurar o contexto que foi salvo. Isto restaura o valor do PC existente antes da interrupção, e força o retorno do fluxo de execução ao mesmo ponto do programa do usuário. A figura abaixo ilustra isso.

Claro que, além dos registradores, para que o programa do usuário possa retomar a execução normalmente as áreas de memória que contém as suas instruções de máquina e as suas estruturas de dados também tem que ser preservadas, mas isto é problema das funções de gerência da memória virtual do kernel, das quais falaremos em outro post.

Entendido o mecanismo de interrupção? Ótimo... passemos ao algoritmo time-sharing propriamente dito.

Time-sharing

Um processo começa a sua vida quando algum usuário (via interface do usuário) ou programa do usuário (via system call) solicita a execução de um programa. A rotina do kernel invocada para esta função é chamada Loader, e faz o seguinte:

• Invoca as rotinas de gerência da memória virtual para alocar os blocos de memória necessários para acomodar as instruções de máquina e as estruturas de dados do programa solicitado;
• Cria as estruturas de dados para o controle do processo pelo kernel;
• Cria uma entrada para o novo processo na ready queue (fila de processos prontos para execução).

O lugar onde o novo processo entra na ready queue geralmente é definido por critérios de prioridade. Senão o novo processo simplesmente ocupa o último lugar na fila.

O Loader então passa o controle para outra rotina do kernel, chamada dispatcher, que:

• Seleciona o primeiro processo na ready queue;
• Remove o processo selecionado e reorganiza a ready queue (faz a fila andar um passo à frente);
• Calcula, com base na estatística dos períodos anteriores de execução do processo selecionado (se houver, senão é feita uma estimativa inicial) o tempo máximo que este processo receberá do processador. Este intervalo de tempo é chamado time slice do processo, e é sempre um múltiplo inteiro de um intervalo básico denominado quantum (que normalmente depende do modelo do processador utilizado);
• Programa o relógio (clock) do processador para provocar uma interrupção após transcorrido o tempo de duração do time slice calculado;
• Restaura o contexto do processo selecionado.

Após isto o processo selecionado tem o controle do processador até que:

1. O time slice acabe (o que é sinalizado pela clock interrupt programada pelo Dispatcher);
2. O programa ceda voluntariamente o controle do processador. Normalmente isto ocorre como parte do processamento de alguma system call invocada pelo programa, cujo completamento será demorado (ex.: solicitação de operações de I/O);
3. Término (normal ou anormal) da execução do programa.

Em todos os casos o controle do processador é passado para outra rotina do kernel, denominada Scheduler, que faz o seguinte:

• Se  processo perdeu o controle do processador por término (caso 3), então invoca as rotinas de gerência da memória virtual para liberar as áreas de memória associadas ao processo e apaga as esturutras de dados para controle do processo;
• Se o proocesso perdeu o controle do processador por cessão voluntária (caso 2), então verifica se existem pendências para o processo (ex.: o completamento de operação de I/O). Se existirem pendências o processo é colocado na wait queue (fila de espera), senão o processo é colocado de volta na ready queue;
• Se o processo perdeu o controle do processador por término do time slice (caso 1) então o processo é colocado de volta na ready queue.
• Verifica se existem processos na wait queue cujas pendências já tenham sido liberadas (isto ocorre como parte do processamento de outros tipos de interrupção, como I/O interrupts, por exemplo). Os processos que não possuam mais pendências são, então, promovidos para a ready queue.

Então, excluindo as situações de início e término, um processo sempre estará em um entre tês estados: ready, quando o processo está na ready queue, aguardando chegar a sua vez de ganhar um time slice do tempo do processador; running, quando ele tem o controle do processador; ou waiting, quando ele está na wait queue aguardando o comletamento das suas pendências.

A figura abaixo sintetiza todo este algoritmo.

Por enquanto chega. No próximo post desta série (e o último, até onde imaginei tratar deste assunto) vou tratar da gerência da memória virtual pelo kernel. Até lá...

Disponibilidade (1)

Outro dia vi algumas mensagens, em um dos vários grupos de discussão via e-mail que acompanho, dizendo algumas inconsistências sobre o tema disponibilidade. Então vou, modestamente, apresentar os conceitos básicos dasta área.

Em um instante t qualquer um componente ou sistema pode estar em um entre dois estados:

• Disponível (available) - ele é capaz de desempenhar suas funções coforme especificado;
• Indisponível (unavailable) - ele não é capaz de desempenhar suas funções coforme especificado;

Podemos então definir a função X(t) da seguinte forma:

E a questão básica do projeto do componente ou sistema é determinar que características ele deve possuir para satisfazer à condição que, no instante t = T (arbitrário) ocorra que:

onde p é o valor de disponibilidade especificado nos requisitos funcionais do componente ou sistema. Estes requisitos são, muitas vezes, especificados em termos de "número de noves", conforme a tabela abaixo.

As colunas de downtime máximo foram calculadas considerando o valor máximo para o tempo de indisponibilidade (downtime) para atingir o valor de disponibilidade especificado dentro do respectivo horizonte de tempo (o mês foi considerado como sendo de 30 dias).

Temos então mais uma relação fundamental para o cálculo de indisponibilidade. Chamando Ta ao somatório da duração de todos os intervalos de tempo obsrvados para os quais X(t) = 1, e Tu ao somatório da duração de todos os intervalos de tempo observados para os quais X(t) = 0, então a disponibilidade A é dada pela expressão:

Na maioria dos casos os componentes ou sistemas que usamos nos nossos projetos são fornecidos por terceiros. Como saber qual a disponibilidade esperada para eles? Quando o fornecedor indica explícitamente a disponibilidade esperada como uma probabilidade específica ou - o que é mais comum - indicando em qual categoria de "número de noves" o seu produto se encaixa a coisa é mais simples.

Entretanto o mais comum é ser indicado apenas o tempo médio esperado entre duas falhas consecutivas do omponente ou do sistema (mean time between failures - MTBF). Sendo assim, para podermos usar a expressão acima é necessário encontrar qual o valor médio do tempo de reparo esperado para uma falha qualquer (mean time to repair - MTTR). Com estes dois valores temos que:

Observe que o valor do MTBF é determinado pelo fornecedor, mas o valor do MTTR depende totalmente do processo de manutenção onde aquele componente ou sistema estiver inserido. Considere, por exemplo, a tabela abaixo:

Isto mostra que, se queremos realizar projetos de alta disponibilidade, é necessário dar muita atenção ao desenho dos processos de manutenção (em garantia, fora de garantia, com pessoal próprio ou terceirizado, estoque se peças de reposição no local ou não, lights-out operation, etc.).

Até agora viemos falando sobre a disponibilidade de sistemas como um todo, mas como é possível calcular a disponibilidade global de sistemas com vários componentes, supondo conhecidas as disponibilidades esperadas para os componentes individuais? A premissa básica para a resposta que vamos dar para esta pergunta é: as probabilidades de falha dos componentes do sistema são independentes entre si. Se isto não for verdade então é necessário introduzir probabilidades condicionais nos cálculos (o que não vou fazer aqui).

Lembrando que se dois eventos A e B são independentes então:

Sabemos que a disponibilidade esperada para um elemento é a probabilidade que ele funcione a contento quando necessário. Então a probabilidade P(X(T) = 0) que um elemento falhe será dada por:

Se tivermos um sistema formado por dois componentes em série, conforma a figura abaixo:

Este sistema falhará se um ou outro ou ambos os componentes falharem. Colocando isto em termos de probabilidades temos:

Se tivermos um sistema formado por dois componentes em paralelo, conforma a figura abaixo:

Este sistema falhará se ambos os componentes falharem. Então as probabilidades são:

Isto cobre o feijão com arroz do assunto. Sinceramente eu não sei muito bem porque os teóricos desta área ainda insistem nestas expressões para a disponibilidade do todo em função da disponibilidade das partes. Para mim parece muito mais simples trabalhar diretamente com os valores de probabilidade de falha dos componentes para obter a probabilidade de falha do todo, e transformar isto para disponibilidade no final. No próximo (e último) artigo sobre este assunto vamos ver um algoritmo para avaliar a disponibilidade de um sistema complexo.

Sistemas de Computação 7 - Programação e sistemas operacionais

Até agora a única forma que vimos para programar uma máquina Von Neumann é codificar a sequência de instruções de máquina (em binário) em algum meio legível pela máquina (ex.: fitas de papel perfuradas ou cartões perfurados).

A execução do programa ocorre em duas fases: primeiro colocava-se a máquina em modo de carga de programa (program load) e executava-se a leitura das instruções de máquina para o local apropriado da memória; depois carregava-se o endereço da primeira instrução do programa no registrador PC (program counter) e mandava-se iniciar o ciclo fetch-execute a partir daí (program run). Após o término da execução do programa todo o processo tinha que ser repetido para a execução do próximo programa.

Estes dois processos (programação e execução) eram complicados e muito suscetíveis a erros. A solução foi dar um passo de abstração à frente. Na área da programação isto foi feito com o surgimento das primeiras linguagens Assembly, e na execução surgiram os primeiros sistemas operacionais.

Linguagens Assembly

A grande novidade das linguagns Assembly (ou linguagens de segunda geração - sendo as linguagens de máquina a primeira geração) foi permitir que os programadores fizessem uso de referências simbólicas e mnemônicas aos elementos do programa (instruções e operandos). Vejamos um exemplo simples (ver IBM z/Architecture Principles of Operation). Suponhamos que o programador deseje executar a seguinte sequência de operações

1. Carregar no registrador de propósito geral número 2 os 32 bits (4 bytes) localizados a partir do endereço contido no registrador de propósito geral número 12;
2. Crregar no registrador de propósito geral número 3 os 32 bits localizados a partir do endereço contido no registrador de propósito geral número 12 mais 32 bits;
3. Somar os conteúdos dos registradores de propósito geral números 2 e 3 (considerados como números inteiros representados em formato binário com sinal);
4. Armazenar o resultado da soma nos 32 bits localizados a partir do endereço contido no registrador de propósito geral número 12 mais 64 bits.

Em lingugem de máquina esta sequência de quatro instruções seria codificada pela seguinte sequência de bits (expressa pelo seu equivalente hexadecimal):

5820C0005830C0041A235020C008

A mesma sequência de quatro instruções na linguagem Assembly desta arquitetura poderiam ser codificadas da seguinte forma:

       L     R2,0(R0,R12)   R2=addr(R12)

       L     R3,4(R0,R12)   R3=addr(R12)+4

       AR    R2,R3          R2=R2+R3

       ST    R2,8(R0,R12)   addr(R12+8)=R2

Bem melhor. Mas ainda dá pra melhorar. Se o programador adotar nomes simbólicos para as localizações de memória apontadas a partir do endereço contido no registrador de propósito geral 12 (usando instruções Assembly do tipo define storage - mnemônico DS) a sequência de instruções poderia ser da seguinte forma:

           USING *,R12        R12=baseaddr

              ...

  PARCELA1 DS    F            4 bytes

  PARCELA2 DS    F            4 bytes

  SOMA     DS    F            4 bytes

              ...

           L     R2,PARCELA1  R2=PARCELA1

           L     R3,PARCELA2  R3=PARCELA2

           AR    R2,R3        R2=R2+R3

           ST    R2,SOMA      SOMA=R2

Ótimo, só que este avanço não vem de graça. Para gerar a sequência de instruções de máquina correspondente às instruções simbólicas Assembly é necessário um programa de tradução denominado Assembler. O programa escrito pelo programador usando instruções Assembly é denominado programa fonte, que é utilizado como entrada pelo programa Assembler, gerando como saída o programa equivalente em linguagem de máquina, denominado programa objeto.

A prática mostrou que quase todos os programas possuiam seções de código virtualmente idênticas (ex.: rotinas para executar operações de entrada/saída de dados). Além disso, programas comumente compartilhavam descrições de estruturas de dados. A partir destes fatos introduziu-se na linguagem Assembly a possibilidade de incorporar trechos do programa fonte a partir de bibliotecas de código fonte, bem como incorporar sequências já traduzidas de código objeto como parte do programa. Assim o processo de construção de um programa executável passou a ser um processo de duas etapas, como mostrado na figura abaixo.

Este modelo geral para a criação dos programas executáveis persiste até hoje. A única diferença é que o programa fonte agora é escrito em outras linguagens, mais abstratas (chamadas de terceira geração), e o programa responsável pela tradução do programa fonte para o programa objeto é chamado compilador.

Os compiladores, a propósito, tornaram-se uma forma muito conveniente para garantir que os programas executáveis utilizassem adequadamente os serviços de um novo elemento que surgiu nesta época: o sistema operacional.

Sistemas Operacionais

A primeira motivação para a existência de programas especializados em supervisionar o ambiente de execução dos programas foi a criação da abstração de arquivos, que dá aos programadores primitivas padronizadas para executar operações de entrada e saída de dados (ex.: ler/gravar em fita magnética; imprimir; etc.). Em termos modernos chamaríamos isto de uma API (application programming interface).

Logo também foi notado que o modelo de execução de um programa de cada vez era altamente ineficiente (a diferença entre o tempo de execução de instruções pelo processador e o tempo para execução de operações de entrada/saída de dados cria grandes "buracos" de inatividade do processador). A solução para isto foi criar uma nova camada de abstração entre os programas e a máquina, permitindo que o tempo do processador e a memória pudessem ser compartilhados, criando para cada programa a ilusão de possuir o controle exclusivo da máquina;

Com isso passamos a ter duas "classes" programas em execução: os programas de controle, ou de supervisão, responsáveis pela administração do ambiente virtual de execução; e os programas de aplicação, voltados para a solução dos problemas dos usuários e que executam "encaixotados" no ambiente virtual de execução administrado pelos programas de sistema. Os programas de controle formam o núcleo (kernel) do sistema operacional, e fornecem aos programas de aplicação uma API comumente conhecida como chamadas de sistema (system calls), que inclui a API de arquivos e outras funções básicas (ex.: solicitar execução de programa).

Cada programa em execução gerenciado pelos programas de controle (incluindo aí as estruturas de dados que descrevem o estado do programa de aplicação para os programas de controle) é chamado um processo. desta forma o modelo operacional da máquina, do kernel do sistema operacional e dos processos é como mostrado na figura abaixo.

Nos próximos artigos desta série vamos examinar mais de perto como o kernel executa as funções de compartilhamento do tempo do processador e da memória. Até breve.

Sistemas de numeração 3 - Generalizando a aritmética: soma de dois inteiros

Pois bem. Depois de um intervalo (longo) volto a publicar artigos no blog. Enfim... o assunto de hoje é, continuando a série sobre sistemas de numeração, a generalização dos algoritmos da aritmética para que eles sejam aplicáveis a números expressos em qualquer sistema de numeração posicional baseados no TGE.

Alguém aí deve estar pensando: "peraí... algoritmos da aritmética?" É algoritmos mesmo, porque a aritmética básica trata dos métodos para execução das operações fundamentais. E todos os procedimentos da aritmética são, na essência, operações executadas sobre polinômios. Vamos começar analisando o algoritmo para a soma de dois números inteiros

Conhecidas as representações b-árias dos números naturais X e Y (parcelas), queremos determinar um procedimento para obter a representação b-ária do número natural S (soma) tal que S = X + Y.

Como a operação de soma S das representações é apenas uma "abreviatura" para a soma dos polinômios de representação de X e Y na base b, de acordo com o TGE, cada dígito da representação de S corresponde a um coeficiente do seu polinômio de representação que, por sua vez, é obtido pela soma dos coeficientes dos termos de mesma ordem de grandeza dos polinômios de reprsentação de X e Y. Então:

 

Isto nos dá duas possibilidades para a determinação do coeficiente si:

Este é o caso mais simples. Nesta situação, pelo TGN, existe um algarismo b-ário que corresponde ao valor de si.

Neste caso podemos escrever que

A justificativa para os possíveis valores do fator delta n expressão acima é simples. Basta lembrar que, pelo TGE, todos os coeficientes do polinômio de representação são valores entre zero e b - 1 (inclusive). Agora, substituindo este resultado no termo genérico do polinômio de representação de S temos

Este resultado mostra que este cado para a soma dos termos dos polinômios de representação de X e Y resultam em um termo nesta mesma ordem de grandeza com coeficiente igual a delta, que pode ser representado diretamente por um algarismo b-ário, e um termo na ordem de grandeza imediatamente superior com coeficiente unitário (que também possui algarismo b-ário correspondente). Este segundo termo é o famoso "vai um" a que nos acostumamos ao aprender o procedimento da soma com números decimais (embora não os chamássemos assim) no priimeiro ano do ensino fundamental.

O único fato adicional para a realização de operações de soma é dominar a tabela de resultados da soma de números com um único dígito b-ário. A título de exemplo seguem abaixo as "tabuadas" da soma para os sistemas binário, decimal e hexadecimal.

Infelizmente não existe maneira de aprender a execução do procedimento de soma de dois números inteiros que não envolva decorar (ou, pelo menos, ter à mão) a tabuada da soma para o(s) sistema(s) de numerção desejado(s). A parte boa da história, embora seja difícil de acreditar quando a gente é criança, é que a constante repetição causa a memorização, provavelmente para a vida inteira, desta(s) tabuada(s). O procedimento de soma descrito abaixo é genérico para qualquer sistema de numeração, mas presume o conhecimento (memorizado ou documental) da tabuada da soma para o sistema de numeração utilizado.

Algoritmo para a soma de dois números inteiros:

Supõem-se cohecidas as representações b-árias das parcelas X e Y da soma, e deseja-se obter a representação b-ária de S = X + Y

1. Escreva as representações b-árias de X e Y uma sobe a outra, mantendo alinhamento vertical dos dígitos de mesma ordem de grandeza a partir da menor ordem de grandeza (da direita para a esquerda);
2. Posicione-se na coluna de menor ordem de grandeza;
3. Transporte = 0;
4. Consultando a tabuada da soma b-ária verifique o valor a soma dos dígitos das duas parcelas e do Transporte;
5. A soma obtida no passo (4) tem um único dígito?
   SIM: vá para o passo 6
   NÂO: vá para o passo 9;
6. Escreva o dígito da soma nesta ordem de grandeza usando o algarismo b-ário cujo valor corresponde à soma obtida no passo (4);
7. Transporte = 0
8. Vá para o passo 11;
9. Escreva o dígito da soma nesta ordem de grandeza usando o algarismo b-ário das unidades na soma obtida no passo (4); 
10. Transporte = 1;
11. Ainda existem dígitos de ordem mais alta que a atual em alguma das parcelas?
    SIM: vá para o passo 12
    NÃO: vá para o passo 14;
12. Posicione-se na próxima ordem de grandeza;
13. Vá para o passo 4;
14. Transporte é igual a 1?
    SIM: vá para o passo 15
    NÂO: vá para o passo 16;
15. Escreva o dígito da na ordem de grandeza imediatamente superior usando o algarismo b-ário que representa a quantidade unitária;
16. FIM.

Vejamos exemplos da aplicação deste algoritmo, respectivamente, para somas nos sistemas binário, decimal e hexadecimal.

Muito bem... No próximo artigo desta séria vamos continuar com este assunto, abordando a operação de subtração de números inteiros. Até lá!

Sistemas de Computação 6 - Melhorando a performance

Peo que vimos nos artigos anteriores desta série aprendemos que as instruções de máquina que compõem o programa em execução são executadas de forma sequencial, exceto quando são executadas instruções de desvio (na verdade há outra razão para a quebra da sequência de execução, mas isso é assunto para mais tarde), e cada instrução é executada em uma sequência de passos conhecida como ciclo fetch-execute.

O tempo total de execução de uma instrução será, então, determinado pela soma dos tempos necessários para que ela passe por cada etapa do ciclo fetch-execute. Todas as mudanças de estado lógico dos circuitos da CPU ocorrem em intervalos de tempo fixos, regulados por um relógio (clock). Então já podemos visualizar um caminho óbvio para melhorar a performance da máquina: fazer o relógio "bater" mais rápido, ou seja, aumentar a frequência do clock.

Infelizmente, por razões físicas, existe um limite prático para o aumento da frequência do clock para melhoria da performance. Mas, ainda assim, existe margem para melhorar o desempenho. Uma delas nós vimos no final do terceiro artigo desta série: diminuir o tempo necessário para executar operações de acesso à memória através da criação de uma hierarquia de memórias intermediárias de maior velocidade - os caches de primeiro, segundo e terceiro níveis (L1, L2 e L3). Desta fora podemos melhorar o tempo de execução das etapas de instruction fetch, operand fetch e result store do ciclo fetch-execute (ver o artigo anterior desta série).

Mas ainda existem alguns truques na manga para aumentar o desempenho da máquina. O primeiro deles deriva da observação que os circuitos necessários para a execução de cada fase do ciclo fetch-execute ficam essencialmente ociosos quando outra fase está em execução. Então manter a CPU ocupada com apenas uma instrução de máquina de cada vez é um desperdício de tempo. A técnica de executar paralelamente várias instruções de máquina em estágios diferentes do ciclo fetch-execute é conhecida como pipelining.

Como podemos ver na figura acima, supondo que a passagem de cada instrução por cada fase do ciclo fetch-execute demore exatamente um ciclo do clock (normalmente é mais, e as fases não tem todas a mesma duração, mas esta hipótese serve como exemplo aceitável), para cinco estágios de pipelining, cada um associado a uma das fases do ciclo fetch-execute, obtivemos um ganho de performance tal que em 15 ciclos do clock passamos de 3 para 11 o número de instruções executadas (ainda mais, se considerarmos que ao final do 15º ciclo do clock existirão mais quatro instruções cuja execução ainda não se completou).

O que nos leva naturalmente à pergunta: qual o ganho hipotético de performance pode ser obtido pelo uso de execução das instruções de máquina com pipelining em relação à execução convencional?

Existem duas variáveis chave para tereminar o ganho G do uso do pipelining: o número N de instruções de máquina a executar e o número P de estágios de pipelining. Chamando de t o tempo médio para execução de cada estágio do pipeline, As expressões para o tempo T de execução das N instruções sem pipelining, para o tempo TP de execução das mesmas N instruções com pipelining, e para o ganho de performance G devido ao uso do pipeline são:

Considerando que o número P de estágios do pipeline é uma constante, o ganho máximo teórico de performance Gmax é dado por:

A título de exemplo o gráfico abaixo mostra o comportamento de G em função de N para P = 5.

Vemos então que o ganho real de performance pelo uso do pipelining converge para o ganho máximo teórico mesmo para valores razoavelmente pequenos da sequência de instruções a executar. Porém existem alguns probleminhas ocultos aqui. Considere, por exemplo a seguinte sequência de operações aritméticas, supondo que cada uma delas possa ser representada por uma única instrução de máquina:

A execução da segunda operação depende de conhecermos o resultado da primeira operação, e a execução da terceira operação depende de conhecermos o resultado da segunda operação. Ou seja, execução da segunda operação é dependente da ´primeira, assim como a execução da terceira operação é dependente da segunda. Porém este é um caso onde a dependência surge do fato que o resultado de uma operação é usada como operando de entrada na próxima instrução. Considere agora o caso da construção lógica chamada IF-THEN-ELSE mostrada abaixo na forma de um fluxograma.

Este tipo de construção tipicamente usa instruções de máquina de desvio condicional para a sua implementação no nível de linguagem de máquina. Mas como o valor da expressão lógica (VERDADEIRO ou FALSO) só é conhecido depois da sua interpretação, isto também cria uma dependência entre instruções, porque a próxima instrução a executar depende do valor lógico resultante da avaliação da expressão.


Dependência entre instruções é um problema sério para o pipelining, porque cria uma "bolha" onde a execução de instruções tem que retornar à forma sequencial pura, prejudicando o ganho de performance. A dependência causada por operandos que são resultados em operações anteriores pode ser contornada intercalando-se as instruções dependentes com outras instruções do programa, de forma a dar tempo para que a execução da instrução dependente só comece depois que o resultado da instrução da qual ela depende já seja conhecido. Isto exige que, depois que a sequência das instruções de máquina do programa esteja definida, seja feita uma análise das relações de dependência e que as instruções dependentes que estejam muito próximas daquelas das quais elas dependem sejam reposicionadas. Isto envolve o uso consciencioso de instruções de desvio incondicional e/ou instruções nulas (isto, em si, já é uma curiosidade: como fazer uma instrução de máquina que apenas ocupa tempo do processador mas não executa nada de verdade? Basta codificar uma instrução de desvio condicional com uma condição de desvio que nunca ocorre). Na prática isto é bastante complicado de fazer, por isso normalmente esta tarefa fica a cargo dos compiladores, dos quais trataremos em outro artigo desta série.

Para o caso da dependência do valor lógico os contornos são implementado na Unidade de Controle da CPU, e são conhecidos como previsão de desvios (branch prediction) e execução especulativa (speculative execution). Neste caso, quando existe uma instrução de desvio condicional no código do programa a Unidade de Controle seleciona um dos possíveis resultados para a instrução de desvio e começa a executar aquela sequência de instruções mesmo antes do resultado correto do desvio ser conhecido (daí o nome execução especulativa). Caso o desvio seja mesmo para a sequência de instruções escolhida, então os resultados especulativos são validaddos. Caso contrário eles são descartados e a execução é retomada a partir da sequência correta de instruções apontada pelo desvio condicional (e assume-se o dano da formação de uma "bolha" no pipelining).

Para finalizar este artigo (que já está bem longo) existe mais um aspecto relativo ao pipelining que precisamos observar. Na nossa descrição anterior sobre o tempo de execução das instruções e o ganho do pipelining usamos o tempo médio de duração de cada fase do ciclo fetch-execute (e associamos a cada uma destas fases um estágio do pipeline). Só que, normalmente, a fase execute é a mais demorada de todas, podendo, a depender da instrução, durar mais do que todas as outras fases juntas. Uma maneira de manter o ganho do pipeline nestas circunstâncias é construir a CPU com mais de uma ALU. Veja o exemplo da figura abaixo.

Supondo que a fase execute tem duração média três vezes superior à duração média das outras fases (isto é uma aproximação, claro), uma CPU com uma única ALU torna-se claramente um gargalo para o desemepenho da máquina. Com o acréscimo de duas ALUs o gargalo é removido, e o ganho do pipeliniing é preservado Este tiipo de solução é o início da evolução da construção dos processadores em direção aos atuais chips multicore, mas isso também é assunto para mais tarde

TV 3D sem óculos.

O Ethevaldo Siqueira, comentando os tópicos principais para discussão na CES 2011 elencou dentro da lista a evolução da tecnologia das TVs 3D em direção da eliminação da necessidade do uso de óculos especiais. A questão é: as tecnologias que permitiriam a dispensa dos óculos oferecem uma experiência de uso ao usuário que compense o sobrepreço sempre associado aos gadgets mais recentes do mercado?

Primeiro, para quem não sabe ainda sequer porque os óculos são usados hoje para proporcionar a sensação de profundidade nas imagens de cinema e TV, o fato principal que precisa ser entendido é que quem realmente "enxerga" o mundo exterior é o nosso cérebro, usando para isso um par de imagens formadas na retina de cada um dos olhos e transmitidas pelos nervos ópticos até o cortex visual do cérebro para processamento.

O que é a sensação de profundidade na nossa visão? É a capacidade de distinguir entre objetos próximos e distantes de nós. A chave disto é a capacidade de focar os olhos sobre os objetos de tal forma que o cérebro percebe as duas imagens superpostas como uma só. Para conseguir isso precisamos deslocar o eixo dos olhos, conforme a figura abaixo.

Nosso cérebro interpreta ângulos mais abertos (beta, na figura) como uma maior distância do objeto em relação a nós, e ângulos mais fechados (alfa, na figura) como objetos mais próximos. Isto é conhecido há muito tempo, e é a base para várias aplicações práticas (ex.: análise aerofotogramétrica estereoscópica e medidores ópticos de distância para uso civil e militar). O segredo é como conseguir isto em uma sala de cinema e (o que nos interessa mais) em um aparelho de TV.

Tudo se resume, sempre, a projetar em cada olho imagens sutilmente diferentes. No cinema usa-se o artifício da luz polarizada. Para entender isso (com um pouco de imaginação) imagine uma corda. Se você balança a corda em todas as direções (para cima e para baixo, esquerda e direita e todos os planos intermediários) a onda que se propaga na corda é dita não polarizada. As ondas luminosas comuns do nosso dia a dia (geradas ou refletidas do sol ou de fontes luminosas comuns) são assim, sem polarização. Porém, se você balançar a corda em um único plano, digamos de cima para baixo, a onda que se propaga na corda tem apenas um plano de vibração, portanto é dita poarizada. Com o uso de filtros apropriados podemos selecionar ondas luminosas que se propagam em apenas um plano de vibração, portanto luz polarizada.

Nossos olhos não distinguem entre luz polarizada ou não (o que é uma sorte, neste caso), então o que fazemos no cinema 3D é projetar dois filmes ao mesmo tempo, mas cada fotograma apresenta pequenas diferenças de posição dos objetos, e cada filme é projetada de forma a ter planos de polarização bem diferentes (idealmente 90°). Cada lente do óculos é um polaróide (filtro de polarização) que só deixa passar a luz de um determinado plano de polarização. Sintonizando os polaróides de cada olho com cada um dos dois planos de polarização usados na projeção temos estímulos visuais diferentes para cada olho e presto! sensação visual de tridimensionalidade.

Esta técnica não é muito prática para o uso em TV, mas podemos tirar partido de outras coisas. O sinal de TV gerado por uma transmissora aberta, pela transmissora de TV por assinatura (cabo ou DTH) ou por um aparelho reprodutor (video cassete - ainda existem alguns por aí - DVD ou Blu-Ray) sempre é formado por um certo número de quadros por segundo. O mesmo princípio da ilusão de movimento do cinema. Imagine então duplicar a taxa de transmissão de quadros por segundo e separar os quadros transmitidos em duas sequências de quadros alternados, cada uma delas formando um sinal ligeiramente diferente, e temos o material básico para a tridimensionalidade. O problema é fazer com que cada sequência diferente de quadros atinja cada olho separadamente.

Aí entram os tais óculos. O que eles fazem é sincronizar as lentes, que são pequenos painéis de cristal líquido, para ficarem transparentes e opacos alternadamente. O sinal de sincronismo entre a TV e o óculos pode ser transmitido por fio (argh!) ou via rádio (mais comum e elegante, desde que não haja interferência externa). Mas o efeito final é o desejado: tridimensionalidade.

Chegamos então à questão central: como conseguir o mesmo efeito sem o uso dos óculos? A propósito, isto é chamado autoestereoscopia. Excluindo o uso de holografia (que é uma tecnologia possível, porém ainda longe de ter um preço razoável) existem hoje duas tecnologias competindo pela dominância do mercado: barreiras de paralaxe e telas lenticulares (incluídas aí as soluções de integral imaging). Ambas tem o que eu considero um grande defeito: a percepção de profundidade só ocorre para alguns ângulos de visão em relação à tela. Ainda está um pouco longe a situação ideal de um usuário circundando ao longo da sala e olhando para a tela e tendo a percepção contínua de profundidade e de mudança do ponto de visão da cena.

As apostas dos analistas é que estas tecnologias, que estão chegando ao mercado agora, deverão maturar ao ponto de oferecer uma experiência de uso decente até o final de 2015. E, até lá, talvez algo diferente ainda apareça e venha a dominar o mercado. Quem sabe? Vale a pena acompanhar o desenvolvimento de tecnologias de acompanhamento dos olhos, como esta aqui anunciada algum tempo atrás pela SeeReal Technologies, ou o filtro 3D apresentado pela CubicVue na competição i-Stage 2009.

Ou, quem sabe, algum tipo de exibição volumétrica venha a tornar-se viável em vez das telas planas de hoje em dia. De qualquer forma, eu não gastaria meu suado dinheirinho, ainda, em uma TV 3D que anuncie que ela não precisa de óculos.

Sistemas de Numeração 2 - Conversão de Representação

Considere dois sistemas de numeração posicionais com as seguintes características:

O TGE (ver o post anterior desta série) garante que qualquer número inteiro possui representação nos dois sistemas. Vamos supor que estamos habituados a realizar operações aritméticas com as representações b-árias dos números inteiros (no próximo artigo desta série vamos tratar disso). Então temos duas situações que precisamos analisar:

• Conhecida a representação b-ária de um número inteiro N, como encontrar a sua representação B-ária equivalente?
• Conhecida a representação B-ária de um número inteiro N, como encontrar a sua representação b-ária equivalente?

Vejamos o primeiro problema. Pelo TGE sabemos que N = P(b) = P(B). Dividindo N[b] por B[b] obtemos o quociente q[b] e o resto r[b]. Mas:

E estas operações evidenciam as seguintes equivalências:

Então vemos que a divisão da representação b-ária de N resultou em um quociente e um resto (expressos como números b-ários), onde o resto corresponde ao valor do coeficiente do termo de mais baixa ordem do polinônio de potências de B equivalente a N. Se substituirmos este valor do resto b-ário pelo símbolo de valor equivalente no conjunto dos algarismos do sistema B-ário teremos o dígito de mais baixa ordem da representção B-ária de N.

Repetindo este processo sobre o quociente b-ário obtido na primeira divisão, o resto b-ário nos dá condição de determinar o segundo dígito de mais baixa ordem da representação B-ária de N. E, assim por diante, enquanto o quociente b-ário obtido não for menor que B, obtemos os dígitos restantes da representação B-ária de N, em ordem crescente de grandeza. Quando o quiciente b-ário obtido for menor que B ele representa o dígito de mais alta ordem da representação B-ária de N.

O procedimento (algoritmo) abaixo formaliza a solução para o nosso primeiro problema:

1. Obter N[b], B[b] e Alg(B) - conjunto dos algarismos do sistema B-ário;
2. Considere G - ordem de grandeza - igual a zero;
3. Efetue a divisão de N[b] por B[b];
4. Procure em Alg(B) o símbolo de valor equivalente ao resto obtido no passo 3;
5. Escreva o algarismo obtido no passo 4 como o dígito de ordem B^G da representação B-ária de N;
6. O quociente obtido no passo 4 é menor que B?
   SIM: vá para o passo 10,
   NÃO: vá para o passo 7;
7. Incremente o valor de OG em uma unidade;
8. Atribua a N[b] o valor do quociente encontrado no passo 3;
9. Volte ao passo 3;
10. Procure em Alg(B) o símbolo de valor equivalente ao quociente obtido no passo 3;
11. Incremente o valor de G em uma unidade;
12. Escreva o algarismo obtido no passo 4 como o dígito de ordem B^G da representação B-ária de N.

A título de exemplo, vamos aplicar este algoritmo para obter a representação hexadecimal equivalente do número decimal 95207.

O sistema binário possui uma peculiaridade: todos os termos não nulos dos polinômios de representação dos números neste sistema são potências de dois, porque os coeficientes dos termos do polinômio de representação neste sistema só podem ser zero ou um. Isto permite um algoritmo alternativo para o caso da conversão de números representados no sistema b-ário (lembrando: este é sistema no qual estamos habituados a executar operações aritméticas) para o sistema binário:

1. Obter N[b];
2. Encontre o maior k para o qual 2^k seja menor ou igual a N[b];
3. Considere o dígito de N[2] de ordem 2^k igual a 1;
4. Calcule a diferença N[b] - 2^k;
5. A diferença obtida no passo 4 é igual a zero? SIM: vá para o passo 8,
   NÃO: vá para o passo 6;
6. Atribua a N[b] o valor da diferença obtida no passo 4;
7. Vá para o passo 2;
8. Considere todos os dígitos de N[2] de ordens de grandeza menores que o maior k obtido no passo 2 e diferentes dos valores de k obtidos no passo 2 como iguais a zero.

Vamos exemplificar o uso deste algoritmo obtendo a representação binária equivalente ao mesmo número decimal que usamos no exemplo anterior:

Existe outro caso particular de algoritmo de conversão, usado quando as bases dos sistemas de numeração para os quais desejamos fazer conversões de representação são tais que existe a relação:

Então (não vou fazer a demonstração disto) existe uma relação bijetora entre os elementos do conjunto de algarismos B-ários e o conjunto de todos os arranjos de k elementos, com repetição, que podem ser formados a partir dos elementos do conjunto de algarismos b-ários.

Por exemplo: no caso dos sistemas binário (base 2) e hexadecimal (base 16) temos este tipo de relação, com k = 4, conforme mostrado na tabela abaixo.

O algoritmo para conversão de representações no sistema b-ário para o sistema B-ário é:

1. Obter N[b] e a tabela de correspondência entre algarismos B-ários e grupos de k algarismos b-ários;
2. Se o número de dígitos de N[b] é um múltiplo de k,
   SIM: vá para o passo 4,
   NÃO: vá para o passo 3;
3. Acrescente à esquerda de N[b] o menor número de algarismos b-ários que representam a quantidade nula que sejam suficientes para que o número de dígitos de N[b] torne-se um múltiplo de k;
4. Separe (da esquerda para a direita) os dígitos de N[b] em grupos de k elementos;
5. Substitua cada um dos grupos formados no passo 2 pelos seus algarismos B-ários correspondentes.

Como exemplo, vamos usar este algoritmo e a tabela de correspondência binário-hexadecimal acima para obter  representação hexadecimal equivalente de 10111001111100111[2].

Então: 10111001111100111[2] = 173E7[16], o que é coerente (conforme esperado) com o que já tínhamos visto nos exemplos anteriores.

Passando agora à análise do nosso segundo problema (obter a representação b-ária a partir da representação B-ária). E, já que estamos com a mão na massa, o caso inverso da conversão binário para hexadecimal apresentada acima é um algoritmo que replica os mesmos passos, porém na ordem inversa:

1. Obter N[B] e a tabela de correspondência entre algarismos B-ários e grupos de k algarismos b-ários;
2. Substitua cada algarismo da representação B-ária pelo grupo de k algarismos b-ários correspondente;
3. Elimine evntuais algarismos nulos não significativos.

O próprio exemplo anterior pode ser usado para demonstrar este algoritmo. Basta acompanhar a sequência de operações de baixo para cima.

Para o caso genérico de conversão B-ário para b-ário usamos o seguinte algoritmo:

1. Obter N[B];
2. Escreva o polinômio P(B) conforme o TGE, substituindo os coeficientes e a base das potências pelos seus valores equivalentes b-ários;
3. Execute as operações de potneciação, multiplicação e soma para obter Obter N[b].

Como exemplo da aplicaçõe deste algoritmo vamos executar o caso inverso do primeiro exemplo apresentado acima: obter a representação decimal equivalente de 173E7[16].

E obtemos, como esperado, o valor decimal 95207.

No primeiro artigo desta série elencamos dois assuntoa a tratar. Com este artigo encerramos o assunto conversão de representação. O próximo artigo deverá tratar da generalização dos procedimentos da aritmética para que eles sejam aplicáveis a qualquer sistema de numeração.