Multitarefa

Vamos fazer mais uma visita à D. Maria e ver como é que ela se vai entendendo com a gestão da sua cozinha. Parece que entretanto a D. Maria chegou à conclusão que ainda podia rentabilizar mais a sua cozinha, pois percebeu que havia partes das suas receitas que se podiam executar separadamente e em paralelo.

Numa receita de carne estufada com batatas, por exemplo, a preparação da carne, a preparação do refogado, a preparação de um conjunto de acessórios que seriam confecionados com a carne e a preparação das batatas, podiam ser executados em paralelo, por forma a estarem todas prontas quando se juntassem no tacho, que ficaria depois em lume brando durante um determinado período de tempo.

Mas ela não conseguia fazer tudo ao mesmo tempo.

Então resolveu contratar mais pessoas e, em cada receita, depois de a dividir em tarefas separadas, entregá-las às diferentes funcionárias. Gerou-se a confusão na cozinha, pois rapidamente começaram a andar sempre a chocar umas com as outras, sendo mais o tempo perdido nisso do que o ganho em rentabilização.

Decidiu então dividir a cozinha em partes autónomas para cada uma dessas pessoas e comprar mais recursos para o conjunto das cozinhas.

Não havia dúvidas. Começou de imediato a poder executar muito mais rapidamente as receitas e em consequência poder aceitar mais trabalho, que aliás não lhe faltava. A coisa foi de tal forma que a D. Maria até passou a fazer só a preparação e gestão dos processos e sua divisão em partes. E o negócio ia de vento em popa.

O que a D. Maria fez foi dividir os processos de confeção em tarefas (threads) e lançá-las em execução paralelamente nas diversas partes da cozinha.

Tarefas ou threads são isto mesmo, até na UCP. O processo lança várias tarefas separadas, que se executam exatamente no mesmo contexto, no mesmo espaço de endereçamento mas com pilhas separadas.

As tarefas contribuem para o aumento da performance do Processo Pai. Dentre as diversas formas por que o podem fazer, destacamos duas a título de exemplo:

• Alterando valores de variáveis globais por via das funções de cada uma, para que o Processo Pai agora possa seguir com o novo valor dessas variáveis, utilizando as operações que as tarefas executaram por ele, em paralelo. Por exemplo no processamento de imagem de um jogo em 3D simulado são inúmeras as variáveis que têm de ser calculadas sem interdependências entre elas e que contribuem para o aspeto final da imagem, razão pela qual as GPU dispõem de centenas de núcleos, tendo algumas até já ultrapassado o milhar.
• Execução paralela de funções do programa que não têm sequência entre si, podendo portanto ser executadas separadamente e em paralelo, contribuindo todas para o fim definido pelo programa. Por exemplo a análise dos milhares de ficheiros de um volume que, em lugar de ser feita uma a uma pelo processo, pode ser feita em paralelo por tantas tarefas quantas a capacidade da UCP permitir.

Por estes dois exemplos fica desde já claro que o ambiente multitarefa é especialmente eficiente em processadores multinucleares.

Cada núcleo, sendo uma UCP autónoma, continua a só poder executar um processo/tarefa de cada vez, pelo que de nada vale ter muitas tarefas se não tivermos o necessário número de núcleos de processamento para as manter com o máximo rendimento.

Evidentemente a afirmação anterior considera o facto de em cada núcleo poderem estar várias tarefas do mesmo processo a executar em ambiente de multiprocessamento, pois cada uma, para esse efeito, é como um processo.

A programação para execução por tarefas consegue tanto melhores resultados quanto mais forem os núcleos de UCP (chips de UCP multinucleares, como por exemplo o i7 da Intel, com 4 núcleos e Hiper-threading em cada núcleo).

Hiper-threading ? O que é isso?

Hiper-threading

Hiper-threading é uma tecnologia desenvolvida pela Intel e primeiramente empregue nos seus processadores Pentium 4 NorthWood.

Hiper-threading consiste na simulação de dois processadores numa só UCP física com um só núcleo, apoiando-se em tempos não utilizados pela UCP resultantes das Bolhas do Pipeline.

Embora a técnica de pipeline tenha sido já abordada no Capítulo sobre a UCP, vamos aqui relembrar o essencial, pois é do resultado da aplicação desta técnica que surge o hiper-threading.

Pipeline é a técnica pela qual uma UCP executa as instruções máquina, não de uma forma estritamente sequencial mas em paralelo, de acordo com os ciclos de clock de cada instrução e a disponibilização de recursos.

Por exemplo, se uma instrução for executada em 4 ciclos de clock, a cada ciclo de clock a UCP inicia uma nova instrução em paralelo com a anterior, utilizando o recurso já abandonado pela primeira.

O resultado ideal e otimista deste método seria ter um total preenchimento dos tempos da UCP, mas tal não é a realidade. Sempre que uma instrução tem que ficar à espera de outra ou a execução de algumas é anulada por existência de saltos, são gerados espaços de tempo não utilizados a que se chamam Bolhas.

São precisamente essas Bolhas de tempos de UCP não utilizados que a tecnologia Hiper-threading utiliza para criar um segundo processador lógico dentro da UCP.

Assim, sobre a Mesma UCP física são criados dois processadores lógicos, cada um com o seu próprio controlador de Interrupções programável e o seu conjunto de registadores, partilhando os restantes recursos da UCP física.

Veremos já de seguida num caso de estudo, o que a arquitetura Nehalem da Intel (um i7, p.e.) criou dentro de um processador, graças à enormidade de transístores que se consegue atualmente colocar num só Chip, com vista à maior rentabilização dos núcleos de processamento, tendo como limite atingir uma operação por ciclo de clock, ou seja, a completa extinção das bolhas.

O tal caminho de que falámos há pouco. Em lugar de aumentar a frequência de vibração da UCP a inteligência deste ser que dá pelo nome de Humano, está a tentar aproveitar na totalidade a atualmente existente. E tem toneladas de trabalho pela frente e possibilidades imensas que se abrem.

Vamos agora utilizar a Figura 1 que representa a execução de 3 tarefas em três situações distintas:

• a) As 3 tarefas são executadas em sequência, cada uma em pipeline, com Hiper-Threading desativado, representando-se as bolhas a cinza.
• b) Com Hiper-Threading ativado mas considerando que não há quaisquer dependências entre as 3 tarefas.
• c) Com Hiper-Threading ativado mas agora com a consideração das seguintes dependências:
  • a instrução 4 da tarefa 2 depende da instrução 4 da tarefa 1,
  • a instrução 3 da tarefa 3 depende da instrução 4 da tarefa 2 e
  • a instrução 11 da tarefa 3 depende da instrução 11 da tarefa 2 que por sua vez depende da instrução 11 da tarefa 1.

As colunas das tabelas do quadro representam os estágios do pipeline, neste caso 4 estágios.

O preenchimento com a decomposição em pipeline e sem Hiper-Threading ativado na situação a) foi feito ao acaso, mas calhou de tal forma que o preenchimento das bolhas na situação b) é total e a redução é de cerca de 45%. Tal também se deve ao facto de termos considerado que não havia qualquer dependência entre as 3 tarefas, isto é, nenhum estágio de nenhuma das tarefas dependia de estágios das outras tarefas.

Na situação c) já considerámos dependências entre algumas instruções entre tarefas, como vem descrito atrás. Verificou-se assim que o número de bolhas aumenta, tendo agora uma redução de tempo total de 30%, apesar da ativação do Hiper-Threading, o que infelizmente se aproxima mais da realidade.

Segundo indicações da Intel, a redução dos tempos de execução graças ao Hiper-Threading é de cerca de 30% em média.

Esta tecnologia ainda hoje está bem viva nos processadores multinucleares da Intel, como por exemplo os i7, que assim disponibilizam até 12 processadores lógicos.

Este tipo de programação é o que vai garantir o aumento de performance no futuro que se prevê para a evolução das UCP. A diminuição do tamanho dos transístores, o facto de os fabricantes de UCP terem deixado de ter no aumento de frequência de vibração da UCP o seu primeiro objetivo e a introdução do conceito de vários núcleos de UCP no mesmo chip, sendo que cada núcleo dispõe de todos os componentes de uma UCP independente, inclusive Caches de nível 1 e 2 próprias, indicam-nos o caminho da paralelização na execução dos programas.

Fizeram exatamente como a D. Maria, quando começou a ter a cozinha cheia e as pessoas a chocarem umas com as outras. Não lhes aumentou a velocidade. Antes encontrou forma de poderem executar simultaneamente as suas tarefas sem entrarem em conflito umas com as outras.

Programação em Multitarefa

Nestas condições é evidente a enorme melhoria de performance de um programa preparado para executar em ambiente Multitarefa.

Só que o desenvolvimento deste tipo de programas é muito complexo exigindo muitos conhecimentos e cuidados especiais. Mas continua a ser a soma das mais elementares simplicidades.

A divisão de um processo em tarefas, mantendo-se o processo também em execução, é consequência de uma forma de programação, muito mais complexa que a normal, pois os problemas de concorrência, que geram situações de inconsistência de dados, podem acontecer com facilidade se não forem devidamente previstos e tratados.

O próprio SO tem um papel desestabilizador nessa inconsistência, pois pode a qualquer momento tirar a UCP a uma das tarefas em execução (suponhamos que essa tarefa tinha acabado de ler o valor de uma variável global para a modificar) e dá-lo a outra tarefa do mesmo processo, que vai precisamente ler a referida variável para tomar determinado tipo de decisões e modificá-la também.

Se isto for possível, quando a anterior tarefa retomar a UCP, vai pegar no valor anterior dessa variável (já o tinha lido antes da 2ª tarefa o modificar), operar sobre ele e escrever o resultado da sua operação.

Quando tal acontece, passamos a ter inconsistência de dados, isto é, uma das operações que afetou a dita variável é nula ou duplicada e o resultado final fica errado.

A execução em tarefas é como a execução de um programa num ambiente distribuído, só que dentro do mesmo computador. Vejamos um exemplo.

Suponhamos que a dita variável era o saldo de um cliente numa conta de um Banco só com um Servidor Central e vários terminais.

O cliente tinha um saldo de 5.000 € e foi ao banco levantar o seu dinheiro. Dirigiu-se ao balcão 1, que o atendeu e começou a executar a tarefa 1.

Entretanto estava no balcão 2 outro cliente para levantar um cheque de 5.000 € que o 1º cliente lhe tinha passado sobre a mesma conta. Foi atendido e esse terminal começou a executar a tarefa 2.

O início das duas tarefas foi quase simultâneo, mas a tarefa 1 começou primeiro. Leu o saldo do cliente, que era de 5.000 € e quando ia executar o passo seguinte, o SO tirou-lhe a UCP e entregou-a à tarefa 2. A tarefa 2 leu o saldo do cliente, que ainda era de 5.000 €, pagou o valor do cheque e aí foi-lhe retirada a UCP.

Entretanto o SO voltou a entregar a UCP à tarefa 1, que vai prosseguir o seu trabalho a partir do ponto onde se encontrava. Para ela o saldo da conta, que tinha acabado de ler, são 5.000 € e como tal vai entregar esse valor ao cliente.

Resultado:

• O cliente titular da conta fica satisfeitíssimo.
• O Banco fica furioso.
• O programador é despedido e processado.

Agora é só uma questão de aumentarmos a escala e vermos o que um insignificante erro, resultante de uma distração ou desconhecimento, pode provocar num programa que se divide em tarefas.

O SO tem intervenção direta em problemas de inconsistência que ele pode gerar ao fazer comutação de tarefas na UCP. O desenvolvimento de algoritmos para o SO, que permitissem ultrapassar todos os possíveis cenários em que a inconsistência pudesse ser gerada, revelou-se de enorme complexidade e morosidade.

Então, os SO passaram a disponibilizar ferramentas de ajuda aos programadores, criando no seu núcleo rotinas que implementam esse tipo de algoritmos sob o seu próprio controlo.

Semáforo e Mutex

O Concurso

O António entrou num concurso que tinha como objetivo despejar água em 3 depósitos que no início estavam rigorosamente vazios, durante um determinado período de tempo.

Para o efeito deveria constituir uma equipa que usaria baldes com capacidade de 5 litros cada. Os baldes eram previamente enchidos numa única torneira, a partir da qual cada elemento da equipa tinha que percorrer um percurso de 50 metros até ao depósito a encher.

No final a equipa vencedora seria aquela que tivesse o melhor rácio, isto é, mais litros despejados por concorrente, devendo saber exatamente a quantidade de água existente nos 3 depósitos, condição que não cumprida daria origem a desclassificação.

Junto às zonzas de enchimento e despejo existia uma pequena zona de espera e ao meio do percurso havia uma zona de descanso.

O acesso às zonas de vazamento e enchimento era feito através das zonas de espera. Nenhuma delas era visível para quem se encontrava no percurso. Para melhor transmitirmos o que imaginámos, juntamos a Figura 2.

As Regras

A organização do concurso criou um conjunto específico de regras com o fim de obrigar a um importante trabalho de planeamento e racionalização:

• Só podia estar um concorrente de cada vez na zona de despejo de cada depósito.
• Mal um concorrente saísse dessa zona, outro que se encontrasse em espera podia avançar.
• Antes de um concorrente começar a despejar carregava num botão que acendia um quadro durante breves segundos e só visível para ele, indicando a quantidade de água no depósito.
• Quando acabava de despejar, o concorrente escrevia a nova quantidade com teclas grandes e de rápido acesso, podendo então partir para novo percurso.
• Porque os concorrentes precisavam de descansar, periodicamente tocava uma buzina e acendia uma luz vermelha num dos depósitos. O concorrente que aí se encontrasse nesse momento, tinha que parar de imediato e retirar-se para a sala de descanso.
• Na sala de descanso, uma luz vermelha com posição idêntica ao depósito indicava-lhe enquanto ligada que ali devia permanecer.
• Este concorrente deveria dirigir-se ao depósito onde tinha sido interrompido, pelo percurso normal, reiniciando a sua tarefa no exato ponto em que tinha sido interrompido.
• A prova tinha que ser feita em silêncio total, sendo expressamente proibida qualquer comunicação entre os concorrentes.
• Em qualquer das zonas de espera não podem estar mais do que 3 concorrentes.
• As zonas de espera, de vazamento e de enchimento não são visíveis para concorrentes no percurso.

A Estratégia

Porque o concurso era um desafio ao planeamento e estratégia, com prémios prestigiantes, o António preparou bem a sua estratégia antes do concurso.

Resolveu que lançaria em simultâneo várias pessoas a encher e vazar os baldes como forma de mais encher os tanques no mesmo período. Mas a situação não era tão simples como isso, pois as regras colocavam vários constrangimentos que ele foi anotando durante os treinos. Para além do facto de que, quanto mais concorrentes estivessem em descanso, pior seria a rentabilidade média.

Rentabilizou ao máximo os tempos de enchimento e calibragem do conteúdo dos baldes, por forma a que a torneira do tanque estivesse sempre aberta e a encher baldes. Por isso só quis dois concorrentes em simultâneo na zona de enchimento: um a encher e outro a calibrar. Quando o que enchia ia calibrar entrava um que estivesse em espera, pois calibrar demorava menos do que encher.

Na zona de despejo a análise era bem mais complexa, mas também havia uma sala de espera com limitações antes desta zona. Era por isso importante pensar bem como iriam funcionar as zonas de espera.

O António começou por estudar os recursos de que dispunha nas zonas de espera. Como esses recursos não eram visíveis a partir do percurso, entendeu que era necessário que os concorrentes em percurso soubessem qual o estado desses recursos antes de lá chegarem.

As zonas de espera ficavam nos topos do percurso e a zona de descanso era uma sala a meio. O simples facto de os concorrentes poderem chegar a essas zonas e só então verificarem que o recurso estava esgotado, obrigando-os a regressar de imediato à sala de descanso, era um desgaste inútil de energias e uma clara obstrução à marcha dos que se encontravam em percurso.

Resolveu então colocar um visor eletrónico no exterior das zonas de espera, que era incrementado por um botão que o concorrente premia à entrada e decrementado da mesma forma à saída. O letreiro era iniciado a 3, sendo decrementado por cada um que entrava e não saía. Quando lá estivessem 3 concorrentes indicava 0 e uma luz verde passava a vermelho, o que significava para os concorrentes em percurso que deviam esperar na sala de descanso antes de se dirigirem para as zonas de espera. Só quando o valor deixasse de ser 0, qualquer um dos concorrentes em espera podia avançar. A estes visores o António chamou Semáforos.

Resolvido o controlo do acesso às zonas de espera, o António virou-se então para a zona de despejo.

Porque sabia que podia ser interrompido a qualquer momento, dividiu a ação de despejo, a ser feita de acordo com as regras, em 3 ações distintas:

• Ler o valor da quantidade de água no depósito.
• Despejar o balde.
• Registar a nova quantidade.

Estas ações tinham, em relação à tarefa de despejo, a propriedade de serem Atómicas, isto é, não decomponíveis em outras ações. Enquanto a tarefa despejo podia ser interrompida pela buzina em qualquer momento entre as ações que a compõem, nenhuma destas podia ser interrompida, pois não era decomponível.

Uma vez o concorrente saído da zona de despejo, outro concorrente avançaria para a mesma, lia o valor da quantidade de água no depósito, despejava o balde e registava a nova quantidade. E outro podia avançar de seguida, e repetir o procedimento.

Entretanto chegava a vez do concorrente interrompido e em descanso regressar à atividade. Quando ele chegasse à zona de despejo, como já tinha feito a leitura e tinha que iniciar exatamente onde tinha acabado, despejava o balde, registava a nova quantidade e partia para novo percurso. Tinha lido 55 Lt., portanto registava 60 Lt. E estava a fazer tudo bem feito.

Só que entretanto, depois de ele ter sido interrompido, já tinham passado pelo depósito outros dois concorrentes e o valor de água que se encontrava no depósito já não era de 55 Lt. mas de 65 Lt. Ao fazer o seu registo ele baralhou tudo e criou uma situação de Inconsistência de Dados, o que iria fazer com que no final não acertassem com a totalidade de água nos depósitos e perdessem o concurso.

O António percebeu que a secção de despejo tinha que ser convertida numa ação atómica, isto é, uma vez iniciada tinha que ser concluída por aquele que a iniciou sem que entretanto pudesse ser iniciada por qualquer outro. O António chamou-lhe Secção Crítica e começou a pensar numa forma de realizar o que tinha concluído.

Então colocou uma luz vermelha por cima de cada depósito, que se acendia quando o concorrente carregava no botão para ler o valor da quantidade de água e que só se desligava quando o concorrente acabava de introduzir a nova quantidade. Era assim como que um semáforo iniciado a 1. Por isso chamou-lhe Semáforo de Exclusão Mútua, mas como achou o nome muito pomposo e complicado de dizer reduziu-o para Mutex ou Trinco.

Desta forma, os concorrentes em espera, ao verem esse concorrente sair da zona de despejo já não avançavam para esse depósito, pois viam a luz vermelha. Quando chegasse a vez de o interrompido iniciar de novo a sua ação, ele dirigia-se diretamente ao depósito de onde tinha saído, pois a luz vermelha não era para ele, concluindo a sua tarefa, apagando a luz e voltando ao percurso.

Com toda esta análise feita o António achou que era altura de testar tudo com treinos, o que também lhe permitiria começar a afinar o número ideal de concorrente a ter em simultâneo. A racionalização era fundamental, pois o vencedor era o que tivesse o melhor rácio.

Mas essa já é uma questão que está fora do objetivo desta história e que o António fez certamente bem, pois ganhou o concurso.

Da Metáfora à Realidade

Ora, as nossas tarefas, que como já vimos são linhas de programação feitas para executarem em paralelo no mesmo processo, vão encontrar durante a sua execução problemas em tudo idênticos aos dos nossos concorrentes.

Os Semáforos e os Mutex são precisamente os nomes das ferramentas que o SO disponibiliza para ajudar a tratar e controlar essas situações.

As tarefas (threads) lançadas por um processo partilham o mesmo espaço de memória, onde cada tarefa terá a sua pilha própria, sendo no entanto comuns tanto o monte como o espaço para dados do programa, as variáveis globais definidas em programa e já criadas em processo de compilação, inicializadas ou não, isto é, com um valor já atribuído ou simplesmente declaradas e portanto com espaço de memória reservado.

Todas as variáveis que são declaradas dentro de um determinado espaço de programa, como pode ser o de uma tarefa ou de alguma ação dentro da tarefa ou mesmo do processo, extinguem-se quando concluída essa ação ou tarefa e não são visíveis em espaços exteriores àqueles em que são criadas. Por isso este tipo de variáveis é habitualmente colocado na pilha, que como acabámos de ver não é partilhada.

Mas as tarefas, porque estão a executar em paralelo ações de um mesmo processo, vão ter necessidade de trabalhar com variáveis globais (a quantidade de água dentro dos depósitos), as que são vistas por todos os atores dentro de um processo e que por isso mesmo se encontram em zonas partilhadas da memória.

É no acesso a esse tipo de variáveis que a concorrência entre tarefas pode gerar situações de inconsistência de dados, sendo por isso chamadas de secções críticas. Há portanto que gerir a forma como as tarefas podem atuar dentro dessas zonas, de forma a não poderem criar situações inconsistentes.

Este controlo tem que ser feito pelos programadores ao desenvolverem os seus programas, definindo quais são as secções críticas e gerindo a forma como as tarefas nelas podem atuar.

Para esse fim o SO disponibiliza ferramentas específicas, o caso do Mutex e dos Semáforos, que quando são criados, fechados, abertos ou extintos, são-no através de chamadas sistema, ou seja, instruções que provocam interrupções que acionam a execução das rotinas do núcleo do SO que lhe estão associadas.

Mas quem tem que decidir onde deve colocar essas ferramentas num programa são os programadores. Quem deve decidir como as deve colocar de forma a evitar a inconsistência mas também de forma a não provocar um bloqueio do programa, são os programadores.

A programação com tarefas é uma programação de nível elevado que requer um conhecimento muito profundo da forma de funcionar destes mecanismos e um cuidado muito grande na sua implementação.

Num programa complexo podem coexistir dezenas ou centenas de semáforos e mutex espalhados pelo mesmo, nas diversas secções críticas, sendo necessário ter sempre presente a forma de atuar de cada uma e a sua possível interferência noutras.

A programação por tarefas é fundamental para qualquer programa complexo que se pretenda eficiente. Como já foi referido noutros Capítulos, a evolução do processamento não passa pelo aumento da frequência das UCP mas sim pela paralelização, como forma de rentabilização dos recursos já existentes.

Essa paralelização é da responsabilidade da UCP no que concerne o tratamento de cada linha de programação em curso, mas é da responsabilidade do programador o fornecimento de linhas de execução em paralelo que possam ser lançadas nos diversos núcleos que as atuais UCP oferecem, não só físicos mas também virtuais, através do Hiper-threading.

Mas cada núcleo tem sua própria cache L1 e L2, onde a mesma variável global pode simultaneamente estar presente. Como é que isto se resolve?

Essa é precisamente a razão pela qual introduzimos o tema da consistência de cache no capítulo sobre cache.

É a ação simultânea do SO, não permitindo diferentes threads simultaneamente na mesma secção crítica e do hardware da UCP, não permitindo que quaisquer dados alterados na cache de um núcleo da UCP possam ser acedidos na cache de qualquer outro núcleo antes de os mesmos serem atualizados, que previnem tal possibilidade.

Resolvemos fazer a introdução deste tema através de uma metáfora, evitando a utilização de programação para esse efeito. Essa programação é já de razoável complexidade e poderíamos não conseguir atingir o objetivo pretendido.

Contamos vir a fazer uma abordagem a linguagens de programação que possa permitir a análise deste tema já através de ações de programação concretas.