Cloud computing

Existem muitas definições de cloud computing na Internet hoje. Sugere-se que a computação em nuvem é simplesmente outro nome para o Software como Serviço (SaaS), modelo que tem sido a vanguarda do movimento web 2.0. Outros dizem que a cloud computing nada mais é do que um novo nome para algumas tecnologias antigas, como virtualização e computação em grade. Na verdade, a computação em nuvem tem um âmbito mais amplo que esses dois conceitos, que são muito específicos. Ela inclui, frequentemente, estas tecnologias (e outras), mas é a estratégia abrangente que define cloud computing.

Acredita-se que no futuro ninguém mais precisará instalar nenhum software em seu computador para desempenhar qualquer tipo de tarefa, pois todos os programas serão acessados através da Internet e essa é a idéia básica da computação em nuvem.

Clusters e grades computacionais

Um aspecto característico da computação de cluster é sua homogeneidade. Na maioria dos casos, os computadores que compõem um cluster são, em grande parte, homogêneos. Isto é, todos tem o mesmo sistema operacional e todos estão conectados à mesma rede. Por comparação, sistemas de computação em grade têm alto grau de heterogeneidade, ou seja, nenhuma premissa é adotada em relação a hardware, sistemas operacionais, redes, domínios administrativos, políticas de segurança e assim por diante.

Grades computacionais são, basicamente, uma coleção distribuída entre diferentes organizações de computadores e recursos de armazenamento mantidos para suprir as necessidades de uma comunidade ou de uma organização virtual. Seus principais componentes são computadores, redes de interligação, sistemas finais específicos, aplicações e servidores.

SaaS (Software as a Service)

Com o surgimento da computação em nuvem e da web 2.0, o software como conhecíamos até hoje, normalmente feito para rodar em determinadas plataformas, com licença de uso, contratos, instalação e manutenção, sofreu algumas modificações e passou a ser chamado de software como um serviço.

Esta visão de software como serviço tornou-se viável com o avanço da Internet, pois tudo passa a ser mais interativo e a comunicação entre o usuário e o software passa a ser mais ampla. Através da computação em nuvem, os desenvolvedores de aplicativos não precisam se preocupar com a distribuição do software, o planejamento e a manutenção dos servidores, o upgrade de hardware, nem mesmo é necessário possuir um servidor próprio, pois os serviços são fornecidos utilizando a estrutura da nuvem. Isso significa que, através da nuvem e utilizando a arquitetura de multiusuários, os desenvolvedores fornecem através da Internet um aplicativo para milhares de clientes, reduzindo os custos para manter o aplicativo.

Para os usuários finais as vantagens também são muitas, como poder utilizar um software sem precisar instalá-lo, sem se preocupar com atualizações, poder utilizar o software em qualquer lugar e hora independente da arquitetura e sistema operacional que o computador possui. Isso também implica em nenhum investimento inicial em servidores ou de licenciamento de software para todas as máquinas.

Hardware as a Service

Não é apenas o software que se torna serviço na nuvem, o hardware também. Para manter os softwares na nuvem é necessária uma boa infra-estrutura, porém manter um servidor não é uma tarefa fácil e, por isso, surgiu o modelo de hardware como um serviço. Esse termo nada mais é do que criar um sistema de “aluguel de máquinas”. Esse mecanismo é impulsionado e amplamente utilizado em empresas onde o foco principal não é T.I., pois consideram que o investimento em servidores é um custo e não um investimento. Estudos também mostram que, na média, a utilização desses servidores gira em torno de 20% e, por isso, alugar ao invés de possuir equipamentos é uma vantagem.

O Hardware também é implementado quase que imediatamente, conforme as necessidades da empresa, seu uso é medido de forma constante e é tudo refletido em uma cota mensal por uso para a empresa. Ou seja, para as empresas utilizarem o HaaS significa aumentar ou diminuir a capacidade computacional em tempo real conforme a necessidade e pagar apenas o que foi utilizado por elas.

Pay as you go

Através dos serviços disponibilizados na nuvem, tanto hardware quanto software, uma empresa pode pagar apenas pelo tempo que utilizar um serviço. Isso implica em uma redução de custo para as empresas, pois não é necessário dispender recursos com sistemas de energia e de resfriamento de equipamentos, nem com manutenção dos servidores e dos softwares, podendo a empresa aplicar seu capital em outras áreas.

Virtualização

Virtualização é a capacidade de criação de instâncias de sistemas operacionais virtualmente (máquinas virtuais), ou seja, com pelo menos uma única máquina podemos ter vários sistemas operacionais rodando ao mesmo tempo, simulando vários servidores. Para a computação em nuvem esse é um conceito extremamente importante, sendo para muitos estudiosos da área uma das bases da cloud computing. A virtualização nos leva inexoravelmente em direção à flexibilização e à cloud computing. Há várias coisas que a virtulização faz para abrir a porta da computação em nuvem e empurrar as organizações para dentro dela. Isso é perceptível, já que são inúmeros os benefícios da virtualização, como a diminuição nos custos de manutenção, devido ao número de máquinas reduzido e a melhora no desempenho das máquinas, pois se a empresa possuir três máquinas que ficam muito tempo ociosas ela pode substituir essas três máquinas por apenas uma.

Funcionamento e anatomia

Seu funcionamento pode parecer abstrato, mas alguns serviços que usamos no dia-a-dia ajudam a exemplificar o que significa este modelo. O e-mail é um deles, pois suas mensagens ficam armazenadas em um servidor alheio, servidor do seu provedor de email, por exemplo, e você pode acessar sua conta com todas as suas mensagens de qualquer lugar por meio da Internet.

Em um sistema de computação em nuvem há uma redução significativa da carga de trabalho nos computadores locais já que eles não precisam mais rodar as aplicações. Em vez disso, a rede de computadores é que faz com que as aplicações funcionem. A demanda por hardware e software no lado do usuário também é diminuida, e a única coisa da qual a máquina do usuário deve ser capaz é rodar o software que proporciona a interface do sistema. Seu funcionamento ocorre de forma que os serviços sejam entregues aos clientes e eles não precisem saber como funciona o mecanismo para entrega desses serviços ou a localidade em que estes serviços estejam fisicamente. Isto é, o funcionamento é transparente aos usuários. Esse funcionamento é análogo ao funcionamento de um cluster ou de um grid.

A nuvem pode ser dividida em camadas que reflitam com precisão as proporções de T.I. em massa no que se refere ao custo, aos requisitos de espaço físico, à manutenção, à administração, à supervisão da gestão e à obsolescência. Essas camadas representam a anatomia geral da nuvem.

Essas camadas são:

     - Applications services – esta é a camada mais familiar para os usuários da nuvem. A função da camada de serviço é hospedar aplicações, que se encaixem no modelo SaaS, que rodam na nuvem e são fornecidos para os usuários conforme as aplicações são solicitadas. Muitas vezes, os serviços oferecidos por essa camada são gratuitos e amplamente utilizados na Internet, como Gmail, Yahoo Mail, Google Calendar, Google Docs, e muitos outros. Porém, também existem muitas aplicações na camada de serviço de aplicativos que são pagos e utilizados, na maioria das vezes, por empresas como IBM Lotus Sametime Unyte, Sugar CRM e WebEX. Em todos estes casos, os pedidos são entregues aos usuários de forma transparente e utilizando o modelo SaaS, ou seja, aliviando os usuários de instalação e manutenção de software;

     - Platform services – nessa camada podemos encontrar a infraestrutura que auxilia a camada superior. Isto inclui serviços como middleware, troca de mensagens, informação, conectividade, e muitos outros, ou seja, os serviços que dão suporte ao funcionamento dos aplicativos. Para que esses serviços sejam altamente escaláveis, a maioria dos serviços oferecidos nessa camada são virtualizados. Como exemplo de serviços nesse setor temos o Amazon Web Services e o Google App Engine. A plataforma de serviços garante aos consumidores que as aplicações da camada superior sejam atendidas de forma a satisfazer as necessidades dos usuários e fornecendo uma infraestrutura de aplicação baseada na demanda;

     - Infrastructure services – na camada mais inferior da nuvem é onde se situam os dispositivos físicos como os servidores, os dispositivos de rede e os discos de armazenamento, que são oferecidos aos consumidores. Tal como acontece na camada acima, a virtualização é um método frequentemente utilizado para fornecer o racionamento na demanda dos recursos. Exemplos de serviço de infra-estrutura incluem o Amazon EC2, Microsoft Azure Plataform, Bluehouse IBM e muitos outros. Nessa camada também conseguimos resolver problemas, como o de equipar de maneira adequada os centros de dados, assegurando o poder de computação quando necessário. Também conseguimos reduzir os custos, já que as técnicas de virtualização são amplamente utilizadas nessa camada e, com isso, os recursos são utilizados de forma mais eficiente.

Sistema de arquivos

Arquivos podem ser vistos como recipientes que contém dados ou como um grupo de registros correlatos. Os arquivos armazenam informações que serão utilizadas, em geral, por programas aplicativos. Os arquivos são implementados através da criação, para cada arquivo no sistema, de uma estrutura de dados composta por registros. O descritor de arquivo é um registro que mantém informações sobre o arquivo, como posição de início e posição de fim.

As informações típicas (atributos) mantidas pelo sistema operacional são:

     1. nome do arquivo;
     2. tamanho (em bytes);
     3. data e hora da criação, do último acesso, da última modificação;
     4. identificação do usuário que criou o arquivo;
     5. listas de controle de acesso;
     6. local do disco físico onde o conteúdo do arquivo foi colocado.

As operações mais comuns relacionadas à manipulação dos arquivos são:

Para controlar e organizar os arquivos, os sistemas de arquivos tem, em geral, os diretórios ou pastas, que podem ser arquivos em muitos sistemas também. Os diretórios podem ser organizados em um único nível (contendo todos os arquivos) ou em múltiplos níveis (diretórios dentro de diretórios).

Um dos principais problemas é como alocar espaço em disco para que os arquivos sejam armazenados de forma eficiente e que permita acesso rápido.

Existem alguns métodos que podem ser utilizados, tais como:

     1. alocação contígua;
     2. alocação com lista encadeada (lista ligada);
     3. alocação com lista usando um índice.

Alocação contígua

Este é o esquema mais simples de alocação de arquivos, onde cada arquivo é armazenado no disco como um bloco contíguo de dados. Neste esquema, em um disco com blocos de 1KB, um pequeno arquivo de 20KB seria armazenado em 20 blocos consecutivos.

Alocação contígua

Principais vantagens:

     1. simples implementação: o controle de onde está cada arquivo no disco é feito por um único número (endereço em disco do 1º bloco);

     2. performance: todo o bloco (arquivo) pode ser lido no disco de uma única vez. É necessário o tempo de somente um seek.

Problemas:

     1. a estratégia só pode ser usada se o tamanho máximo do arquivo for conhecido no momento de
sua criação (devido à necessidade existente em saber o tamanho total do arquivo ou a quantidade de blocos que ele ocupa);

     2. fragmentação do disco: perde-se muito espaço útil com este esquema de alocação. Ao remover um arquivo, a área ocupada pelo mesmo é liberada ocasionando lacunas por todo o disco. Necessidade de compactação (custo alto).

Alocação com lista encadeada

Nesta estratégia de alocação, usamos uma lista encadeada para indicar os espaços ocupados em disco pelo arquivo. Assim, não é mais necessário que o arquivo seja armazenado em posições contíguas do disco. A primeira palavra de cada bloco é usada com um ponteiro para o próximo bloco e o restante do bloco é usado para armazenar as informações (dados) do arquivo.

Alocação com lista encadeada

Principais vantagens:

     1. não se perde espaço por fragmentação externa;

     2. qualquer bloco pode ser utilizado, permitindo que os arquivos cresçam indefinidamente enquanto houver espaço no disco;

     3. a entrada do diretório só precisa armazenar o endereço do 1º bloco do arquivo (em cada bloco
existirá um ponteiro para o próximo bloco do arquivo).

Problemas:

     1. o acesso randômico é lento pois existe a necessidade de percorrer a lista.
     2. a implementação deste método de alocação é mais complicada.

Alocação com lista encadeada usando uma tabela na memória

Para eliminarmos os problemas apresentados no esquema anterior, podemos dispor de uma tabela em memória armazenando os ponteiros para cada bloco do arquivo. Esta tabela recebe o nome de FAT (File Allocation Table) - esquema adotado pelo DOS. Com este esquema o acesso aleatório fica muito mais fácil pois todo o esquema de ponteiros agora fica armazenado em memória, o que é muito mais rápido. O principal problema é o gasto com memória para manter a tabela com as informações. Para um disco de 40GB e blocos de 1KB, a tabela precisará de 40 milhões de entradas. Considerando que cada entrada tem no mínimo 3 bytes, a tabela ocupará um espaço total de 120MB.

Tabela de alocação de arquivos (FAT)

Alocação com lista usando um índice

Busca resolver o problema de ponteiros esparramados pelo disco que a alocação encadeada provoca. Para isso, mantém, por cada arquivo, um índice de blocos que o compõem. Este índice é mantido em um bloco do disco. O diretório possui um ponteiro para o bloco onde está o índice associado a um determinado arquivo.

Este esquema elimina as desvantagens existentes na alocação com lista encadeada: retira os ponteiros de cada um dos blocos e os coloca em uma tabela ou índice na memória. Apesar de o acesso ser randômico também, sua implementação é bem mais simples.

A tabela é armazenada na memória principal e pode ser seguida sem a necessidade de acessar o disco.

Desvantagem: a tabela também deve estar na memória o tempo todo, o que implica em utilização de espaço de memória.

Alocação com lista usando um índice

Inode

A cada arquivo associa-se uma pequena tabela, denominada inode, que lista os atributos e os endereços em discos dos blocos do arquivo. Os primeiros endereços de disco são armazenados no próprio inode. Se o arquivo for pequeno, toda a informação é encontrada diretamente no inode. O conteúdo do arquivo só é transferido do disco para a memória quando o arquivo for aberto (esquema utilizado pelo UNIX).

Inode

Escalonamento de processos

Quando mais de um processo é executável, o sistema operacional deve decidir qual executar primeiro.

Um computador multiprogramado tem vários processos a serem executados simultaneamente, porém, para que todos os processos não tenham acesso à CPU de uma só vez e para que haja uma execução desses processos de forma justa, foi criada uma implementação para organizar tarefas. Esta implementação, ou seja, a parte do sistema operacional que cuida de qual processo será realizado antes ou depois, é chamado de escalonador ou agendador. O algoritmo que o escalonador usa é o algoritmo de escalonamento.

Nos sistemas antigos, que trabalhavam sequencialmente, praticamente estáticos, o algoritmo de escalonamento era bem simples. No caso dos sistemas em lote, era realizada apenas uma tarefa por vez. Com o avanço da informatização, e a necessidade de criação de sistemas mais interativos, foi necessário o desenvolvimento de outros algoritmos mais complexos, não visando somente à organização dos processos seletivamente, mas sim o melhor aproveitamento da CPU.

Tipos de escalonamento

     - Escalonamento preemptivo: tem como objetivo interromper o processo antes mesmo da finalização de sua execução, alternando entre níveis de prioridades. Sua implementação é mais complexa.

     - Escalonamento não-preemptivo: os algoritmos de escalonamento não-preemptivos são simples e mais fáceis de serem implementados, porém, não são adequados para sistemas de propósitos gerais com múltiplos usuários competindo.

Algoritmos de escalonamento

Assegurar que todos os processos recebam sua parte garantida na CPU, manter esta ocupada por 100% do tempo, minimizar o tempo de resposta e maximizar a vazão de serviços em menor intervalo de tempo, são critérios primordiais a serem seguidos para criar um bom algoritmo de escalonamento. Deve-se levar em consideração que o objetivo é de decisão sobre política, e não fornecer um mecanismo.

Escalonamento Round Robin

Também conhecido como escalonamento por alternância circular, o escalonamento Round Robin é um dos algoritmos mais antigos, simples e mais empregados. Os processos são organizados em uma fila e executados seguindo um intervalo de tempo (quantum), e não necessariamente a cada término de sua execução, ou seja, se um processo ainda estiver em execução ao final do quantum, outro processo entra e este vai para o final da fila aguardando a próxima rodada, como podemos ver na figura abaixo.

Agendamento Round Robin. (a) Lista de processos executáveis. (b) Lista de processos executáveis depois de B utilizar todo o seu quantum.

Para obter um melhor desempenho da CPU, a duração do quantum deve ser definida de forma que não seja muito curta nem seja longa demais. Esse cuidado deve-se ao fato de que ao alternar entre um processo e outro, a CPU requer uma quantidade de tempo para administrar: salvar e carregar registradores, etc. Em um intervalo de tempo muito curto ocorrem muitas comutações, ou seja, há muitas alternâncias de processos, o que reduz a eficiência da CPU. Um exemplo seria definir o quantum em 4ms e que o tempo gasto em administração da alternância dure 1ms. Nesse caso vinte por cento da CPU seria gasto em comutações de processos. Em outro caso, se fosse definido um intervalo de tempo de 100ms, mais longo, o tempo seria reduzido a um por cento, porém, significaria ter um tempo de resposta inadequado.

Escalonamento por prioridade

Priorizar os processos, atende justamente a necessidade de otimizar o trabalho da CPU, para tornar o sistema dinâmico, levando em consideração os dados recebidos pelos dispositivos de E/S.

A necessidade de levar em conta fatores externos, conduz ao agendamento de prioridade. A ideia básica é simples e direta: a cada processo é atribuído uma prioridade, e o processo executável com a maior prioridade recebe permissão para executar.

Os processos prontos com prioridades mais altas são escolhidos para utilizar a CPU, mas para evitar que esses processos monopolizem a CPU, são desenvolvidas alternativas que podem diminuir o nível de prioridade. Uma dessas alternativas seria configurar a prioridade como 1/f, onde f é a fração do último quantum que o processo utilizou. Por exemplo, se em um processo de quantum com 100ms levasse 5ms para processar, esse receberia prioridade 20 (vinte), enquanto um processo que executasse 20ms antes de bloquear, teria prioridade 5 (cinco), e um processo que ocupasse todo o quantum, receberia prioridade 1 (um). Outra alternativa seria agrupar classes de prioridades, com quantum definido para cada classe, e com o escalonamento Round Robin operando dentro delas. Um exemplo: em um sistema com quatro classes de prioridade, se existir processos com prioridade quatro, então são executados desconsiderando que haja outros processos de prioridade mais baixa. Se a classe quatro estiver vazia, então são executados os processos de classe três da mesma forma que a anterior e assim por diante.

Certo cuidado deverá ser tomado quanto ao ajuste dos níveis de prioridades mais baixas, podendo estas sofrerem inanição (morrer de fome) por nunca terem a chance de ser executados.

Algoritmo de agendamento com quatro classes de prioridade.

Múltiplas filas

Como visto no item anterior, no escalonamento por prioridade são criadas classes de prioridades, e dentro dessas classes poderia ser implementado o escalonamento Round Robin, puramente. No caso das múltiplas filas, cada classe pode receber uma política de escalonamento diferente, sendo que cada processo não permanece em uma mesma classe de prioridade mesmo que ainda não tenha sido completamente finalizado.

Esse mecanismo otimiza os níveis de prioridades de forma que os processos passam por um tipo de filtragem. Exemplo: um processo que necessita de cem quanta, teria que sofrer cem comutações utilizando o algoritmo Round Robin. Utilizando o mecanismo de múltiplas filas, o processo inicial receberia um quantum, e em seguida, em um processo abaixo, este receberia dois quanta, no próximo receberia quatro quanta e assim sucessivamente.

Atribuindo mais quanta a cada vez que os processos afundam nas classes de prioridade, evita-se que sofram inanição (morram de fome), além de maximizar a realização de processos em menores intervalos de tempo.

Menor serviço primeiro

É um algoritmo em lote que conhece previamente o tempo de execução de cada processo e dá privilégio de execução aos processos de curta duração, melhorando o tempo médio de resposta. No exemplo a seguir, dado um processamento inicial (a) com o tempo de cada processo reconhecido, o mecanismo calcula uma melhor sequência de processamento e então é feita a realocação do menor para o maior tempo (b). Tomando o exemplo de (a) como referência, temos os processos representados pelas letras A, B, C e D e os seus respectivos valores de tempo 8, 4, 4 e 4. Para calcular o tempo médio de execução utiliza-se a seguinte regra: (4A+3B+2C+D) / 4. Substituindo os valores de A, B, C e D, a expressão fica assim: ((4x8) + (3x4) + (2x4) + 4) / 4 = 14. Ordenando do menor para o maior, como o exemplo de (b), a expressão fica da seguinte forma: ((4x4) + (3x4) + (2x4) + 8) / 4 = 11. Neste último cálculo vimos que o tempo médio foi menor, e que a função desse algoritmo é exatamente dar prioridade aos processos de curta duração.

Exemplo de agendamento de job mais curto primeiro.

Escalonamento dirigido à política

Esse tipo de escalonamento faz com que o sistema operacional saiba de quanto tempo é necessário para executar cada operação. Feito isso o sistema operacional pode garantir que n usuários tenham uma porcentagem e atribui o quanto da CPU para cada um em uma proporção 1/n dando a eles a mesma quantidade de tempo de execução.

Dessa forma, torna-se realista prometer ao usuário a ter sua parte da CPU garantida, balanceando todos os recursos.

Havendo processos que utilizem uma quantidade de tempo inferior do que lhe foi atribuído, é feito o aumento do nível de prioridade. O mesmo acontece com processos que tenham utilizado um tempo superior.

Escalonamento em dois níveis

Nem sempre a memória principal é suficiente para comportar todos os processos. Às vezes é preciso manter algumas tarefas no disco. Um processo que esteja parcialmente na memória principal e parcialmente em disco pode comprometer o tempo de resposta, já que o tempo de comutação de processos em disco é muito maior do que o tempo de comutação da memória principal. Para melhorar a comutação em disco, uma solução seria utilizar o escalonamento em dois níveis: nível alto e nível baixo.

Inicialmente, divide-se o processo em subconjuntos, em seguida é feita a escolha de qual desses subconjuntos serão carregados na memória principal temporariamente.

O papel do nível alto tem a função de esvaziar a memória principal quando os processos estiverem em tempo suficiente e carregar os processos que estiverem muito tempo em disco. Enquanto o nível baixo restringe-se aos processos que estão carregados na memória principal e dedica exclusivamente em escolher entre esses processos, o nível alto dedica a fazer o transporte de processos memória ↔ disco.

Processamento paralelo

Classificação de sistemas paralelos

Diversas aplicações procuram lançar mão de multi-processamento para obter melhor performance, a começar pelos próprios sistemas operacionais ou serviços de busca para Internet. Os objetivos do paralelismo podem ser categorizados como:

     - permitir que sistemas munidos de mais de um processador possam acelerar a resolução de um problema de natureza paralelizável;

     - poder executar vários processos simultaneamente (define-se neste caso que processo é um programa em execução);

     - otimizar o tempo ocioso (idle time) das CPUs.

A divisão de processos pode ocorrer tanto ao nível de várias aplicações independentes sendo executadas simultaneamente, bem como uma mesma aplicação dividida em vários threads (thread level paralelism - TLP). 

Toda aplicação paralela pode ser categorizada como sendo de uma das seguintes formas:

     - sistema multi-threaded: um programa que contém mais processos do que o número de processadores disponíveis. Estes sistemas tem como objetivo gerenciar múltiplas tarefas independentes. Um sistema operacional se encontra dentro desta categoria;

     - sistema distribuído: vários processos são executados em várias máquinas, conectadas entre si de alguma forma. Estes processos se comunicam mutuamente através de mensagens;

     - computação paralela: um programa se divide em vários processos para resolver o mesmo problema num tempo menor. Geralmente haverá o mesmo número de processos quanto o de processadores.

Também pode-se categorizar uma aplicação paralela de acordo com o modelo de programação adotado:

     - variáveis compartilhadas: os processos trocam informações entre si através de uma memória compartilhada, numa área comum a todos;

     - troca de mensagens: não há disponibilidade de uma área comum de memória, ou isto não convém para a aplicação (são máquinas diferentes e separadas, por exemplo). Para tanto, a comunicação entre os processos é feita através de envio e recebimento de mensagens;

     - dados paralelos: cada processo executa as mesmas operações sobre diferentes partes do dado distribuído. Este modelo também é conhecido como Single Instruction Multiple Data (SIMD).

Em aplicações de visualização para tempo real, são inúmeros os trabalhos que paralelizam as tarefas. Merecem destaque.

Multi-threading e hyper-threading

Um thread pode ser entendido também como um processo, que pode pertencer a uma aplicação ou a aplicações completamente independentes.

Sistemas com apenas um processador podem gerenciar vários threads simultaneamente através de métodos de Time Slice, concedendo para cada processo uma fatia de tempo da CPU, sendo que este tempo não precisa ser necessariamente o mesmo para cada um. Além disso, cada processo pode conter um nível de prioridade: threads com alta prioridade podem interromper threads com menor prioridade. Entretanto, por melhor que seja o gerenciamento dos threads por parte da aplicação ou do sistema operacional, o Time Slice sempre pode trazer latências, devido a compartilhamento de cache ou dificuldade de gerenciamento entre o trânsito de processos.

Há muitos anos tem-se adotado paralelismo para gerenciamento de vários processos. Entretanto, esta solução costuma ser cara e requer equipamentos especiais, como clusters de CPUs, por exemplo, não sendo adequada para aplicações de usuários padrões, tais como jogos.

O hyper-threading é uma tecnologia que permite que um único processador possa ser visto por uma aplicação ou sistema operacional como dois processadores separados. Isto é possível, devido à arquitetura interna da CPU, que é composta por dois processadores lógicos. Do ponto de vista do software equivale a poder desenvolver uma aplicação para um sistema composto por mais de um processador e do ponto de vista de hardware, significa que instruções são alocadas para partes diferentes da CPU e são executadas individual e simultaneamente. Cada uma destea pode usufruir das suas próprias interrupções, pausas, finalizações, etc. A nível de hardware, no entanto, a CPU consiste em dois processadores lógicos, mas que diferentemente do que processadores duais, compartilham uma série de componentes: recursos do core do processador, cache, barramento de interface, firmware, etc. A arquitetura interna de hyperthreading permite que haja um ganho de até 30% em relação a sistemas de multiprocessamento padrões.

A Intel implementou esta tecnologia de hyper-threading para servidores das séries Xeon e Pentium IV, sendo que já pode ser considerada uma tecnologia barata e acessível.

Paralelismo em pipelines de visualização em tempo real

Um sistema paralelo de visualização em tempo real pode ser dividido em dois métodos: paralelismo temporal e paralelismo espacial.

O paralelismo temporal consiste em modelar o problema semelhantemente a uma linha de produção: cada processo possui a capacidade de resolver uma parte do problema. Uma vez terminada a sua parte, o processo envia os resultados para o processo seguinte e fica disponível para receber novos dados. Neste modelo, pode-se denominar cada processo como sendo um estágio do problema. A resolução completa do problema consiste em percorrer por todos os estágios. O gargalo, neste caso, consiste no estágio que leva mais tempo para ser processado. A configuração ideal para este sistema é ter um processador para cada estágio.

Já o modelo de paralelismo espacial consiste em criar vários processos capazes de fazer a mesma coisa: ganha-se performance distribuindo partes menores do problema para cada processo. Deve-se observar que neste modelo apenas se podem implementar problemas que sejam de natureza paralelizável. Surge neste sistema um problema extra: o programa deve implementar uma função que se encarregue de juntar todos os dados, após terem sido devolvidos por cada processo. Em muitos casos, esta etapa pode inviabilizar a abordagem paralela, pois faz com que se gaste um tempo adicional que antes não era necessário.

Paralelismo e os impostores com relevo

A etapa de pre-warping envolvida num sistema de ibr é apropriada para um estágio que é processado pela CPU e a etapa de texturização é um estágio para a GPU. Tendo em conta que os impostores com relevo constituem apenas parte da modelagem da cena e que a outra parte é descrita através de modelagem geométrica convencional, desenvolveu-se um framework que encara a CPU e a GPU como dois processadores separados e paralelos. Além disso, lançando-se mão de um processador com hyper-threading, vê-se a CPU como uma máquina paralela por si só.

Inicialmente, o sistema modelado é do tipo variáveis compartilhadas: a CPU e a GPU disputam os mesmos recursos. A CPU cuida do estágio de aplicação (framework) e a GPU utiliza estes resultados para realizar os estágios de geometria e rasterização. Há uma dependência temporal entre ambos, pois a GPU necessita dos resultados da CPU para seguir adiante, como se pode ver na próxima figura. Desta maneira, diz-se que o sistema segue o modelo de paralelismo temporal.

Para realizar o pre-warping cria-se um thread. Este processo pode correr em paralelo ao estágio de aplicação da CPU, pois não há dependência de dados. Assim, o thread de pre-warping é visto como um sistema de paralelismo espacial em relação ao processo do framework.

Enquanto o processo de rendering da GPU é do tipo de paralelismo temporal em relação ao framework, o thread de pre-warping é do tipo de paralelismo espacial em relação ao mesmo.

Na modelagem de objetos por impostores com relevo torna-se necessário mais um processo, que é o responsável por gerar dinamicamente novas texturas com relevo. Como o processo de pre-warping precisa destas texturas para ser inicializado, o seu thread correspondente não pode ser disparado enquanto não receber o resultado da nova textura, já pronta. Surge assim um tempo de espera do sistema todo, uma vez que os estágios de geometria e de rasterização da GPU não podem dar início à visualização da textura enquanto este não lhe for enviado. A figura abaixo ilustra esta situação. Vale ressaltar que este tempo de espera da GPU se dá apenas para a visualização do impostor com relevo, uma vez que os objetos geométricos da cena estão sendo tratados independentemente pelo framework e pela GPU.

O processo responsável por gerar uma nova textura com relevo faz com que o tempo necessário para a visualização do impostor com relevo seja aumentado, devido à cadeia de dependências que se cria.

Para solucionar este problema, sugere-se fazer um sistema de previsão de texturas com relevo. A idéia é que, fazendo-se isto, quando a métrica de erro indicar que uma textura com relevo caducou e uma nova textura se tornou necessária, há uma grande probabilidade desta já se encontrar pronta, evitando-se assim o tempo de espera que antes existia. Esta previsão pode ser feita através de uma inferência no vetor velocidade referente ao observador. Também se pode desenvolver uma estrutura de dados que armazena as texturas invalidadas num cache, para poderem ser utilizadas novamente, evitando-se assim um novo cálculo das mesmas. 

Um sistema de previsão é capaz de minimizar o tempo de espera de todo o pipeline para a visualização do impostor com relevo.

Clusters

O que é cluster?

Cluster pode ser definido como um sistema onde dois ou mais computadores trabalham de maneira conjunta para realizar processamento pesado. Os computadores dividem as tarefas de processamento e trabalham como se fossem um único computador.

Histórico

A idéia inicial que conduz ao cluster foi desenvolvida na década de 1960 pela IBM como uma forma de interligar grandes mainframes. Entretanto. O cluster ganhou força até que três tendências convergiram nos anos 80: microprocessadores de alto desempenho, redes de alta velocidade, e ferramentas padronizadas para computação distribuída de alto desempenho.

Uma quarta tendência possível é a crescente necessidade de poder de processamento para aplicações científicas e comerciais unida ao alto custo e à baixa acessibilidade dos tradicionais supercomputadores.

No final de 1993, Donald Becker e Thomas Sterling iniciaram um esboço de um sistema de processamento distribuído construído a partir de hardware convencional como uma medida de combate aos custos dos supercomputadores. No início de 1994, trabalhando no CESDIS, com o patrocínio do projeto HTPCC/ESS, criaram o primeiro cluster desse tipo, o projeto Beowulf.

     - Cluster de 16 processadores DX4 interligados.

Tipos de cluster

Alta disponibilidade (high availability [HA] and failover):

    - estes modelos de clusters são construídos para prover uma disponibilidade de serviços e recursos de forma ininterruptas, através do uso da redundância implícita ao sistema;
     - a ideia geral é que se um nó do cluster vier a falhar (failover), aplicações ou serviços possam estar disponíveis em outro nó;
     - são utilizados para bases de dados de missões críticas, correio, servidores de arquivos e aplicações.

Balanceamento de carga (load balancing):

     - este modelo distribui o tráfego entrante ou requisições de recursos provenientes dos nodos que executam os mesmos programas entre as máquinas que compõem o cluster;
     - todos os nodos estão responsáveis em controlar os pedidos. Se um nó falhar, as requisições são redistribuídas entre os nós disponíveis no momento;
     - este tipo de solução é normalmente utilizado em fazendas de servidores web (web farms);
     - Exemplo: MOSIX (Multicomputer Operating System for UnIX).

Combinação HA & load balancing:

     - combina as características dos dois tipos de cluster, aumentando assim a disponibilidade e a escalabilidade de serviços e recursos;

     - este tipo de configuração de cluster é bastante utilizado em servidores web, de e-mail, de news ou ftp.

Alto desempenho e aplicações:

     - este modelo de cluster aumenta a disponibilidade e a performance para as aplicações, particularmente as grandes tarefas computacionais;
     - uma grande tarefa computacional pode ser dividida em pequenas tarefas que são distribuídas ao redor das estações (nodos), como se fosse um supercomputador massivamente paralelo;
     - estes clusters são usados para computação cientifica ou análises financeiras, tarefas típicas para exigência de alto poder de processamento.

Por que utilizar cluster?

     - quanto mais computadores na rede mais rápida fica sua estrutura;
     - maior agilidade no processamento;
     - componentes de fácil disponibilidade;
     - fácil manutenção: a manutenção geralmente fica por conta do grupo de usuários, que ganha com experiência e economia de recursos;
     - independência de fornecedores de hardware;
     - custos muito baixos;
     - se um computador do sistema parar não é necessário esperar seu conserto para recomeçar seu trabalho;
     - disponibilidade de sistema operacional e ferramentas de apoio gratuitas;
     - uma configuração inicial pode ser facilmente atualizada, sem desperdício do investimento.

Cluster OpenMosix

OpenMosix é uma extensão do kernel do Linux, utilizada para a criação de sistemas simples que utilizam clusters. Faz com que um cluster de computadores se comporte como um grande e único supercomputador, através da utilização de Migração Preemptiva de Processos e Balanceamento Dinâmico de Carga.

A implementação da Migração Preemptiva de Processos é capaz de migrar qualquer processo do usuário, em qualquer instante e para qualquer nó disponível de maneira transparente. Desta forma, se um nó com vários processos (a utilizar um destes dois recursos concorrentemente) detecta que outro nó tem disponibilidade superior, como por exemplo, menor carga de processador/RAM, então o OpenMosix encarrega-se de transladar/migrar um desses processos para esse nó.

Vantagens:

     - escalabilidade: completamente transparente, basta lançar um novo nó na rede sem software ou requisitos adicionais, e será automaticamente adaptado pelo cluster como nó;
     - adaptatividade: a arquitetura de cada nó é completamente indiferente, desde que a versão do OpenMosix seja igual entre nós;
     - não necessita de recompilação das aplicações: qualquer aplicação poderá beneficiar deste sistema sem alterações ao código.

Problemas:

     - algumas aplicações não podem ser migradas;
     - limitações relacionadas a hardware local.

Cluster Beowulf

Software para gerenciamento (escalonamento, status). Ferramentas para comunicação (PVM, MPI).

Conclusão

As tecnologias de Clustering possibilitam a solução de diversos problemas que envolvem grandes volumes de processamento. As aplicações as quais um cluster pode ter são diversas, indo desde a simples melhora no desempenho de um determinado sistema ou a hospedagem de um site, até o processo de pesquisas científicas complexas.

O que realmente chama a atenção, é que todo o processamento pode ser feito de maneira que pareça ser um único computador dotado de alta capacidade. Assim, é possível que determinadas aplicações sejam implementadas em cluster, mas sem interferir no funcionamento de outras aplicações que estejam relacionadas.

Empresas especializadas, centros de pesquisas e universidades costumam estudar este assunto a fundo. Como consequência, existem clusters com até milhares de nós.

Alguns benefícios do Clustering são processamento eficiente, custo baixo, ampla gama de aplicações etc.

Tipos de sistemas operacionais

Sistemas monoprogramáveis (monotarefa)

Os primeiros sistemas operacionais eram tipicamente voltados para a execução de um único programa. Qualquer outra aplicação, para ser executada, deveria aguardar o término do programa corrente. Os sistemas monoprogramáveis, como vieram a ser conhecidos, se caracterizam por permitir que o processador, a memória e os periféricos permaneçam exclusivamente dedicados à execução de um único programa.

Neste tipo de sistema, enquanto um programa aguarda por um evento, como a digitação de um dado, o processador permanece ocioso, sem realizar qualquer tipo de processamento. A memória é subutilizada, caso o programa não a preencha totalmente e os periféricos, como discos e impressoras, estão dedicados a um único usuário, nem sempre utilizados de forma integral.

Comparados a outros sistemas, os sistemas monoprogramáveis ou monotarefa são de simples implementação, não existindo muita preocupação com problemas decorrentes do compartilhamento de recursos, como memória, processador e dispositivos de E/S.

Sistemas multiprogramáveis (multitarefa)

Os sistemas multiprogramáveis, ou multitarefa, são uma evolução dos sistemas monoprogramáveis.

Neste tipo de sistema, por exemplo, enquanto um programa espera por uma operação de leitura ou gravação em disco, outros programas podem estar sendo processados neste mesmo intervalo de tempo. Nesse caso, podemos observar o compartilhamento da memória e do processador. O sistema operacional se preocupa em gerenciar o acesso concorrente aos seus diversos recursos, como memória, processador e periféricos, de forma ordenada e protegida, entre os diversos programas.

A principal vantagem dos sistemas multiprogramáveis é a redução de custos em função da possibilidade de compartilhamento dos diversos recursos entre as diferentes aplicações. Além disso, sistemas multiprogramáveis possibilitam na média a redução total do tempo de execução das aplicações. Apesar de mais eficientes que os monoprogramáveis, são de implementação muito mais complexa.

A partir do número de usuários que interagem com o sistema operacional, podemos classificar os sistemas multiprogramáveis como monousuário ou multiusuário.

Sistemas multiprogramáveis monousuário são encontrados em computadores pessoais e estações de trabalho, onde há apenas um único usuário interagindo com o sistema. Neste caso, existe a possibilidade de execução de diversas tarefas ao mesmo tempo, como a edição de um texto, uma impressão e o acesso à Internet.

Sistemas multiprogramáveis multiusuário são ambientes interativos que possibilitam a diversos usuários conectarem-se ao sistema simultaneamente.

Os sistemas multiprogramáveis ou multitarefa podem ser classificados pela forma com que suas aplicações são gerenciadas, podendo ser divididos em sistemas batch, de tempo compartilhado ou de tempo real. Um sistema operacional pode suportar um ou mais desses tipos de processamento, dependendo de sua implementação.

Sistemas batch

Os sistemas batch foram os primeiros tipos de sistemas operacionais multiprogramáveis a serem implementados na década de 1960. Os programas, também chamados de jobs, eram submetidos para execução através de cartões perfurados e armazenados em disco ou fita, onde aguardavam para ser processados. Posteriormente, em função da disponibilidade de espaço na memória principal, os jobs eram executados, produzindo uma saída em disco ou fita.

O processamento batch tem a característica de não exigir a interação do usuário com a aplicação. Todas as entradas e saídas de dados da aplicação são implementadas por algum tipo de memória secundária, geralmente arquivos em disco. Alguns exemplos de aplicações originalmente processadas em batch são programas envolvendo cálculos numéricos, compilações, ordenações, backups e todos aqueles onde não é necessária a interação com o usuário.

Esses sistemas, quando bem projetados, podem ser bastante eficientes, devido à melhor utilização do processador, entretanto, podem oferecer tempos de resposta longos. Atualmente, os sistemas operacionais implementam ou simulam o processamento batch, não existindo sistemas exclusivamente dedicados a este tipo de processamento.

Sistemas de tempo compartilhado

Os sistemas de tempo compartilhado (time-sharing) permitem que diversos programas sejam executados a partir da divisão do tempo do processador em pequenos intervalos, denominados fatias de tempo (time-slice). Caso a fatia de tempo não seja suficiente para a conclusão do programa, ele é interrompido pelo sistema operacional e substituído por um outro, enquanto fica aguardando por uma nova fatia de tempo. O sistema cria para cada usuário um ambiente de trabalho próprio, dando a impressão de que todo o sistema está dedicado exclusivamente a ele.

Geralmente, sistemas de tempo compartilhado permitem a interação dos usuários com o sistema, através de terminais que incluem vídeo, teclado e mouse. Esses sistemas possuem uma linguagem de controle que permite ao usuário comunicar-se diretamente com o sistema operacional, através de comandos. Desta forma, é possível verificar arquivos armazenados em disco ou cancelar a execução de um programa. O sistema, normalmente, responde em poucos segundos à maioria desses comandos. Devido a esse tipo de interação, os sistemas de tempo compartilhado também ficaram conhecidos como sistemas on-line.

A maioria das aplicações comerciais atualmente é processada em sistemas de tempo compartilhado, pois elas oferecem tempos de resposta razoáveis a seus usuários e custos mais baixos, em função da utilização compartilhada dos diversos recursos do sistema.

Sistemas de tempo real

Os sistemas de tempo real (real-time) são implementados de forma semelhante aos sistemas de tempo compartilhado. O que caracteriza a diferença entre os dois tipos de sistemas é o tempo exigido no processamento das aplicações. Enquanto em sistemas de tempo compartilhado o tempo de processamento pode variar sem comprometer as aplicações em execução, nos sistemas de tempo real os tempos de processamento devem estar dentro de limites rígidos, que devem ser obedecidos, caso contrário, poderão ocorrer problemas irreparáveis.

Nos sistemas de tempo real não existe a idéia de fatia de tempo, implementada nos sistemas de tempo compartilhado. Um programa utiliza o processador o tempo que for necessário ou até que apareça outro mais prioritário. A importância ou prioridade de execução de um programa é definida pela própria aplicação e não pelo sistema operacional.

Esses sistemas, normalmente, estão presentes em aplicações de controle de processos, como no monitoramento de refinarias de petróleo, no controle de tráfego aéreo, no controle de usinas termoelétricas ou nucleares, ou em qualquer aplicação onde o tempo de processamento seja fator fundamental.

Sistemas com múltiplos processadores

Os sistemas com múltiplos processadores caracterizam-se por possuir duas ou mais UCPs interligadas e trabalhando em conjunto. A vantagem deste tipo de sistema é permitir que vários programas sejam executados ao mesmo tempo ou que um mesmo programa seja subdividido em partes, para serem executadas simultaneamente em mais de um processador.

Com múltiplos processadores, foi possível a criação de sistemas computacionais voltados, principalmente, para processamento científico, aplicado, por exemplo, no desenvolvimento aeroespacial, prospecção de petróleo, simulações, processamento de imagens e CAD. A princípio, qualquer aplicação que faça uso intensivo da UCP será beneficiada pelo acréscimo de processadores ao sistema. A evolução desses sistemas deve-se, em grande parte, ao elevado custo de desenvolvimento de processadores de alto desempenho.

Os conceitos aplicados ao projeto de sistemas com múltiplos processadores incorporam os mesmos princípios básicos e os mesmos benefícios apresentados na multiprogramação, além de outras características e vantagens específicas, como escalabilidade, disponibilidade e balanceamento de carga.

Escalabilidade é a capacidade de ampliar o poder computacional do sistema, apenas adicionando novos processadores. Em ambientes com um único processador, caso haja problemas de desempenho, seria necessário substituir todo o sistema por uma outra configuração com maior poder de processamento. Com a possibilidade de múltiplos processadores, basta acrescentar novos processadores à configuração.

Disponibilidade é a capacidade de manter o sistema em operação, mesmo em casos de falhas. Neste caso, se um dos processadores falhar, os demais podem assumir suas funções de maneira transparente aos usuários e suas aplicações, embora com menor capacidade de computação.

Balanceamento de carga é a possibilidade de distribuir o processamento entre os diversos processadores da configuração, a partir da carga de trabalho de cada processador, melhorando, assim, o desempenho do sistema como um todo.

Um fator-chave no desenvolvimento de sistemas operacionais com múltiplos processadores é a forma de comunicação entre as UCPs e o grau de compartilhamento da memória e dos dispositivos de entrada e saída. Em função desses fatores, podemos classificar os sistemas com múltiplos processadores em fortemente acoplados ou fracamente acoplados.

Sistemas fortemente acoplados

Nos sistemas fortemente acoplados (tightly coupled) existem vários processadores compartilhando uma única memória física (shared memory) e dispositivos de entrada e saída sendo gerenciados por apenas um sistema operacional. Em função destas características, os sistemas fortemente acoplados também são conhecidos como multiprocessadores.

Os sistemas fortemente acoplados podem ser divididos em SMP (Symmetric Multiprocessors) e NUMA (Non-Uniform Memory Access). Os sistemas SMP caracterizam-se pelo tempo uniforme de acesso à memória principal, pelos diversos processadores. Os sistemas NUMA apresentam diversos conjuntos, reunindo processadores e memória principal, sendo que cada conjunto é conectado aos outros através de uma rede de interconexão. O tempo de acesso à memória pelos processadores varia em função da sua localização física.

Nos sistemas SMP e NUMA todos os processadores tem as mesmas funções. Inicialmente, os sistemas com múltiplos processadores estavam limitados aos sistemas de grande porte, restritos ao ambiente universitário e às grandes corporações. Com a evolução dos computadores pessoais e das estações de trabalho, os sistemas multitarefa evoluíram para permitir a existência de vários processadores no modelo simétrico. Atualmente, a grande maioria dos sistemas operacionais, como o UNIX e o Windows, implementa esta funcionalidade.

Sistemas fracamente acoplados

Os sistemas fracamente acoplados (loosely coupled) caracterizam-se por possuir dois ou mais sistemas computacionais conectados através de linhas de comunicação. Cada sistema funciona de forma independente, possuindo seu próprio sistema operacional e gerenciando seus próprios recursos, como UCP, memória e dispositivos de entrada e saída. Em função destas características, os sistemas fracamente acoplados também são conhecidos como multicomputadores. Neste modelo, cada sistema computacional também pode ser formado por um ou mais processadores.

Até meados da década de 1980, as aplicações eram tipicamente centralizadas em sistemas de grande porte, com um ou mais processadores. Neste tipo de configuração, os usuários utilizam terminais não inteligentes conectados a linhas seriais dedicadas ou linhas telefônicas públicas para a comunicação interativa com esses sistemas. No modelo centralizado, os terminais não tem capacidade de processamento. Sempre que um usuário deseja alguma tarefa, o pedido é encaminhado ao sistema, que realiza o processamento e retorna uma resposta, utilizando as linhas de comunicação.

Com a evolução dos computadores pessoais e das estações de trabalho, juntamente com o avanço das telecomunicações e da tecnologia de redes, surgiu um novo modelo de computação, chamado modelo de rede de computadores. Em uma rede existem dois ou mais sistemas independentes (hosts), interligados através de linhas de comunicação, que oferecem algum tipo de serviço aos demais. Neste modelo, a informação deixa de ser centralizada em poucos sistemas de grande porte e passa a ser distribuída pelos diversos sistemas da rede.

Com base no grau de integração dos hosts da rede, podemos dividir os sistemas fracamente acoplados em sistemas operacionais de rede e sistemas distribuídos. A grande diferença entre os dois modelos é a capacidade do sistema operacional em criar uma imagem única dos serviços disponibilizados pela rede.

Os Sistemas Operacionais de Rede (SOR) permitem que um host compartilhe seus recursos, como uma impressora ou diretório, com os demais hosts da rede. Um exemplo deste tipo de sistema são as redes locais, onde uma estação pode oferecer serviços de arquivos e impressão para as demais estações da rede, dentre outros serviços.

Enquanto nos SORs os usuários têm o conhecimento dos hosts e seus serviços, nos sistemas distribuídos o sistema operacional esconde os detalhes dos hosts individuais e passa a tratá-los como um conjunto único, como se fosse um sistema fortemente acoplado. Os sistemas distribuídos permitem, por exemplo, que uma aplicação seja dividida em partes e que cada parte seja executada por hosts diferentes da rede de computadores. Para o usuário e suas aplicações é como se não existisse a rede de computadores, mas sim, um único sistema centralizado.

Outro exemplo de sistemas distribuídos são os clusters. Em um cluster existem dois ou mais servidores ligados, normalmente, por algum tipo de conexão de alto desempenho. O usuário não conhece os nomes dos membros do cluster e não sabe quantos são. Quando ele precisa de algum serviço, basta solicitar ao cluster para obtê-lo. Atualmente, sistemas em cluster são utilizados para serviços de bancos de dados e Web, garantindo alta disponibilidade, escalabilidade e balanceamento de carga à solução.

Multiprogramação

Tenta fazer com que a CPU esteja ocupada a maior parte do tempo e os periféricos sejam compartilhados entre os usuários. 

Concorrência

Os sistemas monoprogramáveis subutilizam os recursos do equipamento (processador, memória e periféricos).

Exemplo:

Ao realizar I/O o programa perde o uso do processador, para retornar, após a operação ter sido terminada, para o estado em que se encontrava anteriormente. 

Interrupção

Intervenção do sistema operacional devido à ocorrência de algum evento previsto.

Desvia o fluxo de execução para uma rotina de tratamento da interrupção.

Podem ser geradas a partir:

     - da execução de um programa;

     - do próprio sistema operacional;

     - de algum dispositivo de hardware.

Pode ser:
     - interna (trap ou exceção): deve ser tratada para a execução prosseguir (overflow, divisão por zero). É síncrona, pois a execução com as mesmas entradas de dados implicará no mesmo resultado;

     - externa: gerada pelo S.O. ou pelo hardware (comunicação de periférico à CPU - deve ser atendida). É assíncrona, pois é imprevisível e independente do que estava sendo executado.

Para tratar a interrupção o contexto deve ser salvo.

Cada interrupção possui uma rotina de tratamento, e a associação entre elas é mantida em uma estrutura denominada vetor de interrupção.

As rotinas podem ser escritas pelo programador e evitar o procedimento padrão do Sistema Operacional (overflow).

Se a interrupção externa pode ser desabilitada pelo processador, ela é denominada mascarável e será ignorada, não recebendo tratamento. Caso contrário, ela é chamada não-mascarável e o tratamento será obrigatório.

As interrupções permitiram a implementação da concorrência e por elas o Sistema Operacional sincroniza a execução dos programas dos usuários e controla os periféricos e recursos do sistema.

Operações de E/S

Primeiramente, a UCP executava instruções especiais de E/S, as quais continham informações detalhadas sobre os diversos periféricos (trilhas e setores que poderiam ser lidos ou gravados). Grupo limitado de dispositivos.

O controlador (ou interface) criou a independência entre a UCP e o dispositivos, pois faz a intermediação entre os dois. As características dos dispositivos ficaram a cargo do controlador e as instruções de E/S foram, portanto, simplificadas.

O monitoramento do dispositivo e a transferência de dados entre a UCP e os periféricos evolui conforme as técnicas abaixo:

     - E/S controlada por programa: a UCP inicia a transferência e fica testando o periférico, esperando pelo final da instrução de E/S. Há desperdício de tempo de UCP;

     - polling: o periférico era testado em intervalos de tempo, o que liberava a UCP para a execução de outro(s) programa(s). No caso de existirem muitos periféricos, o sistema interrompe frequentemente o processamento para testar o término exato da operação;

     - E/S controlada por interrupção: a UCP envia um sinal para o controlador que se encarrega de ler o disco e armazenar na memória ou em registradores próprios. Ao término, o controlador sinaliza uma interrupção ao processador que, ao tratá-la, busca os dados. Várias operações de E/S podem ser executadas paralelamente, porém toda transferência de dados entre a memória e os periféricos exige utilização da UCP;

     - técnica de DMA (Direct Memory Access): o controlador recebe informações de onde o dado se encontra, qual o dispositivo de E/S envolvido, posição inicial de memória onde os dados serão lidos ou gravados e o tamanho do bloco de dados. A transferência é realizada pelo controlador (que assume
temporariamente o controle do barramento), utilizando uma área de memória reservada, denominada buffer;

     - canal de E/S: é um processador com capacidade de controle total sobre os dispositivos de E/S (vários controladores), o qual executa um programa de canal (na memória principal) que especifica os dispositivos e os buffers e controla possíveis erros da transferência, sinalizando a UCP ao final da operação;

     - processador de E/S: o canal passou a ter sua própria memória de modo que a intervenção da UCP se tornou mínima.

Buffering

É a utilização de uma parte da memória para transferir dados entre os periféricos e a UCP. Visa minimizar as diferenças de velocidade do processamento da UCP e dos dispositivos.

A unidade lógica é o registro, que é especificado em função do dispositivo (linha de impressora, caracter de teclado) ou da aplicação (registro lógico de um arquivo).

O dispositivo transfere um dado para o buffer e pode iniciar nova leitura. A UCP pode manipular o dado no buffer simultaneamente às leituras do dispositivos.

Na gravação o processo é semelhante, com a UCP colocando dados no buffer.

No buffer podem existir dados lidos mas não processados, ou processados e não gravados.

Spooling

Simultaneous peripheral operation on-line surgiu como opção para um melhor aproveitamento da UCP e dos dispositivos periféricos (final dos anos 50). É utilizado, principalmente, na impressão.

Ao invés de enviar os jobs diretamente para a impressora e ficar esperando o término da impressão para iniciar a execução de outro programa, a UCP envia o job para um arquivo intermediário (no início era uma fita). Este arquivo é, então, impresso, sendo que a ordem de impressão dos jobs é determinada por prioridades atribuídas à eles.

Reentrância

Consiste na capacidade de um código de programa (código reentrante) ser compartilhado, na memória, por diversos usuários, existindo, desse modo, apenas uma cópia carregada. Este código, por razões óbvias, não pode ser alterado.

Cada usuário pode estar em um ponto diverso do programa, manipulando seus próprios dados. Utilitários do sistema como editores, compiladores e link-editores são códigos reentrantes. Alguns sistemas permitem que aplicações dos usuários utilizem reentrância. 

Proteção do sistema

Em ambientes onde muitos usuários compartilham recursos e dados, o sistema operacional deve prover mecanismos que garantam:

     - integridade dos dados de cada usuário: um programa não pode acessar a área de memória do outro (acidentalmente ou não). O mecanismo de gerência de memória determina a forma de controle;
     - compartilhamento de dispositivos de E/S: um programa só pode utilizar um dispositivo de E/S no momento em que o primeiro programa o liberar;
     - compartilhamento de arquivos: o S.O. provê mecanismo de controle de acesso aos arquivos, de modo que as informações do usuário permaneçam consistentes;
     - compartilhamento de UCP: o uso da UCP deve ser compartilhado entre os diferentes programas de maneira rígida, pois é o principal componente do sistema.

Modos de execução

Cada vez que o usuário necessita utilizar um recurso, ele solicita ao Sistema Operacional através de rotinas do sistema (system calls). Essas rotinas, por acessarem os recursos, devem possuir mecanismos de proteção.

O mecanismo mais utilizado nos sistemas multiprogramáveis é chamado modo de execução. Consiste em uma característica que, associada ao programa em execução, determina se ele pode executar certas instruções ou rotinas. O modo corrente é armazenado em um registrador especial da UCP, o qual é verificado pelo hardware, e assim, executa ou não a instrução. 

Existem, basicamente, dois modos de execução:

     - modo usuário: o programa só executa instruções que não afetem diretamente os outros programas (instruções não-privilegiadas);
     - modo supervisor (monitor ou kernel): qualquer instrução pode ser executada, mesmo rotinas do sistema (instruções privilegiadas).

Em uma leitura, por exemplo, o programa solicita ao Sistema Operacional o acesso ao disco. O S.O. verifica se o arquivo pode ser acessado. Se sim, muda o modo de execução para supervisor, realiza a operação de leitura e retorna o modo de execução para usuário, continuando o processamento.

O sistema operacional sempre executa em modo supervisor, pois é responsável pelo compartilhamento dos recursos, e deve possuir esta capacidade.

Processos concorrentes

Em um sistema multiprogramado:
     - processos são concorrentes: vários processos são (virtualmente) executados ao mesmo tempo;
     - processos são assíncronos: executam independentemente;
     - processos compartilham recursos.

Especificação da concorrência em programas

Hierarquia de processos: um grafo de processo é uma árvore cujos nodos correspondem a um processo.
     - uma aresta de um nodo Pi para um nodo Pj significa que Pj foi criado por Pi (Pi é o pai de Pj e Pj é o filho de Pi);
     - cada processo possui um pai, exceto o inicial, cujo pai é ele mesmo;
     - cada processo pai pode ter vários filhos.

A especificação da concorrência em programas pode ser expressa em diversas notações. As mais utilizadas são os comandos FORK e JOIN, e os comandos PARBEGIN e PAREND.

FORK e JOIN

O processo pai executa concorrentemente com o processo filho.

O programa A começa a ser processado e, ao encontrar o comando FORK, cria outro processo (ou subprocesso, ou filho) para a execução do programa B. O comando JOIN determina o ponto onde A sincroniza com B, isto é, o programa A só prossegue, a partir do comando JOIN, quando B terminar.

PARBEGIN e PAREND

O processo pai espera que o processo filho termine.

Os subprocessos contidos após o comando PARBEGIN serão executados concorrentemente, numa ordem imprevisível. O ponto de sincronização é definido pelo comando PAREND, sendo que os comandos a partir dele somente serão executados quando todos os outros já tiverem terminado. Devido à sua facilidade de compreensão e simplicidade, podem ser facilmente adicionados em uma linguagem de alto nível.

Problemas de comunicação entre processos

Em um ambiente com processos concorrentes assíncronos que compartilham recursos, um processo pode afetar ou ser afetado por outro processo.

Exemplo: Spooler de impressão.

P2 afeta o acesso de P1 ao recurso compartilhado. Isto acontece devido ao assincronismo entre P1 e P2.

A necessidade de confiabilidade dos sistemas multiprogramáveis torna extremamente importante a existência de mecanismos que garantam a comunicação entre processos concorrentes e o acesso aos recursos compartilhados, os quais são denominados mecanismos de sincronização entre processos.

O problema do produtor-consumidor representa um tipo de interação comum entre processos concorrentes assíncronos.

Os programas exemplificados a seguir representam a concorrência entre um processo de gravação e um de leitura em um buffer.

A variável contador guarda o número de dados contidos no buffer, ao passo que a variável n determina a capacidade do buffer. A implementação é de uma fila (FIFO), onde novo aponta para o fim da fila e prox para o início. Ao serem compilados os comandos contador++ e contador-- geram as sequências de instruções:

O exemplo a seguir ilustra uma possível execução, cujo resultado não é o esperado. Partindo do princípio que contador = 5 (armazenado em #end), após a execução das duas instruções, o contador deveria permanecer com o valor 5.

Porém, ele indica 4, o que não corresponde a realidade.

Exclusão mútua e seções críticas

A solução para evitar estes problemas de comunicação consiste em impedir que dois ou mais processos tenham acesso a variáveis de memória ao mesmo tempo. Quando um processo estiver acessando uma variável compartilhada, todos os outros que necessitarem dessa mesma variável devem esperar que o primeiro termine o acesso. É este o conceito de exclusão mútua, ou acesso mutuamente exclusivo.

O trecho de programa onde são realizados acessos às variáveis de memória compartilhadas é denominado seção crítica (ou região crítica).

No problema produtor-consumidor:

Para assegurar a exclusão mútua, dois ou mais processos não podem executar simultaneamente seções críticas que acessem as mesmas variáveis compartilhadas.

Toda a vez que o processo for executar sua seção crítica, ele deve executar um protocolo de entrada na seção crítica. Do mesmo modo, ao sair, o processo deverá executar um protocolo de saída da seção crítica.

     BEGIN
          .
          Entra_Seção_Crítica();
          Seção_Crítica;
          Sai_Seção_Crítica();
          .
     END

Estes mecanismos que permitem execução mutuamente exclusiva, devem ser providos pelo Sistema Operacional.

Soluções de hardware para o problema da exclusão mútua

Desabilitação de interrupções

A inibição das interrupções na entrada da seção crítica e a sua ativação na saída da seção crítica é a solução mais simples para a exclusão mútua. Como a mudança de contexto só ocorre através de interrupções, o processo que as desabilitou terá acesso exclusivo garantido.

Cabe notar que funcionamento do sistema pode ser seriamente comprometido caso o processo que desabilitou as interrupções não torne a habilitá-las.

Porém, esta solução só é válida em sistemas monoprocessáveis. Em sistemas multiprocessáveis, dois ou mais processadores podem estar executando processos distintos que queiram executar a mesma seção crítica.

Espera ocupada (instrução Test-And-Set)

Para suportar exclusão mútua, algumas arquiteturas de processador fornecem a instrução TAS (Test And Set).

A instrução TAS:

     · lê uma trava de memória (lock) e atualiza o valor do registrador (R1);
     · escreve a trava de memória (lock) com o conteúdo de um registrador (R1);
     · a leitura e a escrita são realizadas atomicamente, em um único ciclo de barramento (ciclo read-modify-write), ou seja, as instruções executam sem interrupção (indivisíveis).

A implementação da exclusão mútua entre produtor e consumidor com a instrução TAS:

     - enter() testa a variável lock
          se lock = 1 a entrada na seção crítica é permitida
          se lock = 0, espera até que lock = 1

Esta solução é denominada espera ocupada (busy wait) porque realiza uma má utilização de tempo do processador, pois o processo em enter() o mantém desnecessariamente.

Soluções de software para o problema da exclusão mútua

A exclusão mútua soluciona os problemas de comunicação, porém os problemas de sincronização também devem ser atendidos, através dos seguintes fatores:

     - o número de processadores e o tempo de execução dos processos concorrentes devem ser irrelevantes;
     - um processo, fora de sua seção crítica não pode impedir que outros processos entrem em suas próprias seções críticas;
     - um processo não pode permanecer indefinidamente esperando para entrar em sua seção crítica (starvation).

Semáforos

São variáveis especiais usadas para assegurar exclusão mútua, as quais ficam associadas aos recursos compartilhados, indicando quando eles estão sendo acessados por um dos processos concorrentes.

Um semáforo S é uma variável inteira acessada apenas através de duas operações, P(S) (ou wait(S), ou UP(S)) e V(S) (ou signal(S) ou DOWN(S)), que permitem a entrada e saída da seção crítica respectivamente. Essas operações são atômicas em sua totalidade.

Usando semáforos no problema produtor-consumidor:

Inicialmente S = 1

Os semáforos podem ser de dois tipos:

     - semáforos binários: assumem apenas os valores 0 e 1, sendo usados apenas para assegurar exclusão mútua.
     - semáforos contadores: usados para controlar a alocação de recursos.

Os semáforos contadores podem ser utilizado para a implementação da sincronização condicional. Uma vez que, se existe um processo que deve ser notificado sobre a ocorrência de um evento e outro capaz de detectar essa ocorrência, podemos utilizar um semáforo associado ao evento esperado para sincronizar ambos os processos.

Semáforos contadores no problema produtor-consumidor:
     - S, disponíveis e ocupados são variáveis do tipo semáforo

Considerando n (tamanho do buffer) igual à 2, e que o Consumidor é o primeiro a ser executado, vejamos a simulação. Como o buffer está vazio (ocupados = 0), o processo consumidor fica bloqueado.

Após o processo Produtor armazenar o dado no buffer e executar o V(ocupados), o processo Consumidor é liberado pois está apto para ler o dado do buffer.

Inicialmente: S = 1, disponíveis = n, ocupados = 0

Implementação da comunicação entre processos com o uso da notação PARBEGIN/PAREND e da sincronização de processos com semáforos a partir de um grafo:

Monitores

A programação com semáforos é propensa a erros, pois deve ser mantida uma correspondência, na ordem correta, entre as operações P e V nos processos que compartilham um recurso.

Os monitores são oferecidos por certas linguagens de programação e permitem uma melhor estruturação das seções críticas de um programa, tornando mais fácil o desenvolvimento e a correção de programas concorrentes.

Um monitor consiste de um módulo contendo: rotinas, estruturas de dados e variáveis de condição. Sua estrutura típica é mostrada na figura a seguir.

A cada instante, apenas um processo pode estar executando uma rotina do monitor, implementando, automaticamente, a exclusão mútua entre seus procedimentos. Cabe notar que o monitor permite a execução de um procedimento seu, mesmo que um ou mais processos estejam no estado de espera.

     PROGRAM Exemplo;
          MONITOR Região_Crítica;
               VAR X : INTEGER;
               PROCEDURE Soma; BEGIN
                    X := X + 1;
               END;
               PROCEDURE Diminui; BEGIN
                    X := X - 1;
               END;
          BEGIN
               X := 0;
          END;
     BEGIN
          PARBEGIN
               Região_Crítica.Soma;
               Região_Crítica.Diminui;
          PAREND;
     END.

O monitor encapsula as seções críticas (em forma de procedimentos) do programa, portanto:

     - não é necessário controlar a exclusão mútua em cada ponto de acesso ao recurso compartilhado;
     - uso correto dos mecanismos de exclusão mútua (semáforos) a cargo do compilador.

As variáveis de condição são estruturas do tipo fila, onde os processos esperam por algum evento. Duas operações se realizam sobre as variáveis de condição:

     - wait(c): processo passa a esperar na fila da condição c, quando esta impede a continuação da execução;

     - signal(c): desperta o processo esperando na fila da condição c. A instrução signal deve ser a última do procedimento, de modo que o processo abandone imediatamente o procedimento.

O problema produtor-consumidor com monitores:

Problemas de sincronização entre processos

São problemas que surgem na implementação de soluções para os problemas de comunicação e devem ser resolvidos antes destes. Os mais comuns são:

     1. Velocidade de execução dos processos: surge quando o mecanismo de controle implementado desconsidera as instruções dos processos além da seção crítica. No exemplo abaixo, o processo B é bloqueado pelo processo A, mesmo este estando fora de sua seção crítica.

          PROGRAM Velocidades;
               VAR Vez : CHAR;
               PROCEDURE Processo_A; BEGIN
                    REPEAT
                         WHILE (Vez =´B´) DO

                              (* Não faz nada *);
                         Seção_Crítica_A;
                         Vez := ´B´;
                         Processamento_Longo;
                    UNTIL False;
               END;
               PROCEDURE Processo_B; BEGIN
                    REPEAT
                         WHILE (Vez =´A´) DO

                              (* Não faz nada *);
                         Seção_Crítica_B;
                         Vez := ´A´;
                    UNTIL False;
               END;
          BEGIN
               Vez := ´A´;
               PARBEGIN
                    Processo_A;
                    Processo_B;
               PAREND;
          END.

     2. Starvation ou indefinitely postponed (postergação indefinida): ocorre quando dois ou mais processos esperam por um recurso alocado. Na decisão de qual processo ganhará o acesso ao recurso compartilhado, se o Sistema Operacional o fizer de modo aleatório ou através de prioridades, pode ser que um processo nunca seja escolhido. Para resolver este problema utiliza-se um mecanismo de fila, onde o primeiro a chegar é o primeiro a ser atendido (FIFO). 

     3.Sincronização condicional: ocorre quando o recurso não se encontra pronto para ser utilizado, devendo o processo permanecer no estado de espera. Surge em operações onde existam processos gerando informações (produtores) utilizadas por outros processos (consumidores). Como no exemplo do buffer, os processos devem estar sincronizados de forma que um processo não tente gravar dados em um buffer cheio ou ler de um buffer vazio.