\chapter{Conceitos Básicos}
\label{arquiteturaconceitosbasicos}
\cutname{arquiteturaconceitosbasicos.html}
% livro do Dantas.

%       Mussi 18-08

\section{Arquiteturas Computacionais}
% \subsection{Características das Arquiteturas Paralelas Mais Utilizadas}

A Arquitetura de computadores pode ser definida como a estrutura e a organização dos \textit{hardwares} e se refere ao funcionamento interno de um computador, ou seja, a organização interna de todos os periféricos necessários para a montagem de um sistema computacional.

As arquiteturas serão caracterizadas a partir de componentes cuja nomenclatura é apresentada na figura \ref{fig:blocobasico}. Estes também são os três principais blocos básicos das arquiteturas seqüenciais.

\begin{figure}
	\centering
	\insimg{1}{imagens/bloco-basico-dos-computadores-sequenciais.jpg}

	\caption{Blocos básicos dos computadores seqüenciais}
	\label{fig:blocobasico}
\end{figure}



\subsection{A Classificação de Flynn para Arquiteturas de Computadores}

A inclusão da proposta feita por Flynn (taxonomia de Flynn) em 1966 é, em primeiro lugar, um compromisso com a classificação mais difundida para arquiteturas de computadores.% A nomenclatura definida por esta proposta será utilizada no decorrer do texto.

A proposta se baseia nas combinações possíveis entre uma ou mais seqüências de instruções, atuando sobre uma ou mais seqüências de dados. Decorre daí, quatro classes de computadores:

\begin{itemize}
	
	\item \textbf{S}eqüência de \textbf{I}nstruções, uma \textbf{S}eqüência de \textbf{D}ados (\textbf{SISD}\textbf{-}\textit{Single} \textit{Instruction} \textit{stream} \textit{over}\textit{ a }\textit{Single}\textit{ Data }\textit{stream}): corresponde aos computadores seqüenciais convencionais, nos quais só existe uma única unidade de controle que decodifica seqüencialmente as instruções, que operam sobre um único conjunto de dados.

	\item \textbf{S}eqüência de \textbf{I}nstruções, \textbf{M}últiplas Seqüências de \textbf{D}ados (\textbf{SIMD}\textbf{-}\textit{Single} \textit{Instruction} \textit{stream} \textit{over}\textit{ a }\textit{Multiple}\textit{ Data }\textit{stream}): corresponde aos processadores matriciais. Nestas arquiteturas, diversos elementos processadores são ativados por somente uma unidade de controle. Esta unidade está submetida a um único programa, cujas instruções repassam aos elementos processadores. Os processadores executam, concorrentemente, uma mesma instrução sobre os dados que têm na sua memória local.

	\item \textbf{M}últiplas Seqüências de \textbf{I}nstruções, uma \textbf{S}eqüência de \textbf{D}ados (\textbf{MISD}\textbf{-}\textit{Multiple} \textit{Instruction} \textit{stream} \textit{over}\textit{ a }\textit{Single}\textit{ Data }\textit{stream}): não existem computadores construídos que se enquadrem nesta categoria.
	
	\item \textbf{M}últiplas Seqüências de \textbf{I}nstruções, Múltiplas \textbf{S}eqüências de \textbf{D}ados (\textbf{MIMD}\textbf{-}\textit{Multiple} \textit{Instruction} \textit{stream} \textit{over}\textit{ a }\textit{Multiple}\textit{ Data }\textit{stream}): nesta classe se enquadram os multiprocessadores.
	
\end{itemize}
	
\subsubsection{Arquiteturas de Memória Distribuída}
\label{arqmemodist}

Neste tipo de arquitetura, cada nó tem seu processador, sua unidade de controle e sua memória local (MIMD). Assim, cada nó pode executar, de forma assíncrona, um processo independente sobre seus próprios dados (vide figura \ref{fig:arqmemodist}). Os equipamentos que implementam este tipo de arquitetura também são conhecidos como multicomputadores (\cite{CUL99}, \cite{MOR94}).

A rede de interconexão (vide item \ref{redesinter}) é crítica para o desempenho deste tipo de equipamento. As diversas possibilidades de implementação da rede de interconexão (topologia, latência, contenção, etc.) neste tipo de arquitetura constituem um dos aspectos responsáveis pela falta de padrão no mercado de arquiteturas paralelas.


\begin{figure}
	\centering
	\insimg{1}{imagens/arquitetura-generica-de-multiprocessador-de-memoria.jpg}

	\caption{Arquitetura genérica de multiprocessador de memória}
	\label{fig:arqmemodist}
\end{figure}


A configuração deste tipo de arquitetura é variável. O número de processadores, por exemplo, pode oscilar da casa das dezenas a alguns milhares. Em alguns casos, o crescimento ocorre em potências de 2 (16, 32, 64, 128, etc.) (vide item \ref{hipercubo}).

{\bf Principais aspectos positivos}
\\

\textbf{Tecnologia de compilação}: uma vez que cada nó da arquitetura é uma unidade de processamento autônoma, é possível aproveitar toda esta tecnologia de compilação disponível para programação seqüencial, agregando à mesma os recursos de uma biblioteca para  troca de mensagens entre os nós processadores. São propostas usuais que, utilizando desta premissa, exploram conhecidas linguagens seqüenciais como C ou FORTRAN para programação paralela.


\textbf{Possibilidade de emular outras arquiteturas}: resguardadas as restrições inerentes ao desempenho, é possível à arquitetura de memória distribuída, emular outros paradigmas de controle e de organização de memória. Uma possibilidade usual é o emprego de DSM (\textit{Distributed} \textit{Shared} \textit{Memory} \cite{MIL99}, \cite{PRO98}), através da qual o \textit{software} aplicativo tem a visão de uma memória comum a todos os nós processadores.


\textbf{Compartilhamento de uso}: este tipo de arquitetura permite, de forma bastante flexível, o particionamento e a alocação de subgrupos de processadores à tarefas/usuários.

{\bf Principais aspectos negativos}\\

\label{arqmemodistneg}
\textbf{Custo das comunicações}: em função das características da rede de interconexão utilizada (vide item \ref{redesdesemp}), alguns algoritmos podem ter seu desempenho diminuído. Assim, o processo de planejamento, codificação e geração de código (com a contribuição explícita ou não do programador), precisa considerar aspectos de localidade das comunicações e granulosidade das tarefas, para otimizar a possibilidade de seu particionamento e distribuição aos processadores.

\textbf{Custo de sincronização}: apesar de poderem trabalhar freqüentemente de forma assíncrona, determinados momentos da execução paralela podem exigir um estado conhecido comum, para um grupo de processadores. Para minimizar o possível tempo de espera nos momentos de sincronização, o desenvolvimento de \textit{software} deve contemplar uma distribuição de carga o mais equânime possível (o que nem sempre é viável), e com isso potencializar a utilização dos processadores e aumentar o desempenho global do processamento.

\textbf{Uso ineficiente da memória}: três aspectos concorrem para a sobre-ocupação da memória em arquiteturas de memória distribuída. O primeiro decorre da necessidade de armazenamento temporário das mensagens recebidas até que o processo responsável pela computação possa fazer o devido tratamento. Dependendo  do tamanho e da freqüência destas mensagens, um considerável volume de memória terá de ser destinado para isto. O segundo é conseqüência da necessidade de cópia local do código executável. O terceiro decorre, em função da busca de desempenho, de se fazer a cópia local também das estruturas de dados globais que o algoritmo possa necessitar.

\subsubsection{Arquiteturas de Memória Compartilhada}


Neste tipo de arquitetura todos os nós  têm acesso uniforme a uma única memória comum (vide figura \ref{fig:arqmemocompartilhada}). São também denominados de multiprocessadores simétricos (\cite{CUL99}, \cite{MOR94}). Uma das razões do sucesso comercial deste tipo de arquitetura MIMD, é decorrente da sua flexibilidade de uso. Cada processador da arquitetura pode ser visto como uma máquina seqüencial tradicional; a existência de outros processadores, bem como da memória comum, pode ser abstraída. Uma conseqüência desta característica é a possibilidade de utilizar o \textit{software} seqüencial já existente, praticamente sem nenhuma modificação. Deste modo, o paralelismo além de ser utilizado para melhorar o desempenho de um determinado programa, também pode ser empregado para executar simultaneamente diversos programas seqüenciais do usuário.

Como a memória é um recurso compartilhado, para que a mesma não se transforme em um ponto de estrangulamento da operação da arquitetura, o número de processadores  varia,  tipicamente, entre 4 e 20.



\begin{figure}
	\centering
	\insimg{1}{imagens/arquitetura-generica-de-multiprocessador-de-memoria-compartilhada.jpg}

	\caption{Arquitetura genérica de multiprocessador de memória compartilhada}
	\label{fig:arqmemocompartilhada}
\end{figure}






Uma estratégia para aumentar o desempenho do sistema de memória compartilhada é o uso de uma memória cache entre o processador e a memória comum. A busca de um sistema eficiente para manutenção da coerência de memória neste tipo de arquitetura é um tema complexo e originou diversos trabalhos de pesquisa.

% {\bf Principais aspectos positivos}\\
A utilização destes sistemas propicía vários aspectos positivos como:\\

\textbf{Abstração da localidade do processador}: neste tipo de arquitetura o programador pode abstrair a localidade do processador. Deste modo, a troca de mensagens é sincronizada por um mecanismo de escrita em variáveis comuns. Como a memória é fisicamente compartilhada, isto pode ser feito com elevado desempenho (via de regra maior que os obtidos com as políticas de DSM - \textit{Distributed} \textit{Shared} \textit{Memory}).

\textbf{Semelhante às arquiteturas convencionais}: os multiprocessadores de memória compartilhada usualmente oferecem um ambiente de programação e um sistema operacional bastante semelhante aos das máquinas seqüenciais, o que facilita a adoção da arquitetura enquanto o \textit{software} está sendo adequado para uma execução efetivamente paralela.

\textbf{Facilidade de uso múltiplo}: os processadores podem ser alocados individualmente ou em grupos, para diferentes programas/usuários.

\textbf{Maior compartilhamento dos recursos}: a memória comum facilita o compartilhamento de estruturas de dados globais. Por sua vez, os recursos de entrada/saída e de memória virtual podem ser aproveitados por todos os nós processadores.


Mas também trás como problema da \textbf{pouca} \textbf{escalabilidade}, a política de acesso uniforme à memória faz com que este tipo de arquitetura, tenha como limite um número de processadores em torno de 20. O constante aumento do poder computacional dos processadores, e a conseqüente necessidade destes de maior banda-passante com a memória, contribui para potencializar este aspecto. Esta arquitetura também está sujeita ao custo de sincronização, que afeta as arquiteturas de memória distribuída (vide item \ref{arqmemodistneg}). Entretanto, como o número típico de processadores não é grande, e as comunicações tem um desempenho elevado, a sincronização como um todo pode ser melhor administrada.


\subsubsection{Arquiteturas Síncronas Matriciais}
\label{arqsincm}

Neste tipo de arquitetura, todos os processadores obedecem a uma única unidade de controle. Esta unidade busca e decodifica as instruções do programa e as transmite para os diversos processadores que as executam, utilizando sua própria memória local (SIMD). Assim, a cada ciclo, todos os processadores (menos os que estão intencionalmente inibidos) executam sincronamente uma mesma instrução sobre sua parte dos dados. O paralelismo se dá, portanto, pela manipulação simultânea de diferentes partes do conjunto de dados. Daí sua denominação estar associada aos termos: arquiteturas síncronas e paralelismo de dados (\cite{CUL99}, \cite{MOR94}).

Este tipo de arquitetura exige uma estrutura densa para a rede de interconexão, a fim desta suportar a difusão das instruções a partir do controlador para a matriz de processadores. Esta rede de interconexão também é utilizada para distribuir dados e recolher resultados.

O ambiente para geração de código neste tipo de arquitetura, usualmente, fica localizado em uma estação de trabalho que atua como intermediária (\textit{front}\textit{-}\textit{end}) para a arquitetura. Esta estação acumula as funções de gerenciamento de contas de usuário, o escalonamento das diversas requisições de processamento e o acesso através da rede local de computadores.

As arquiteturas síncronas se mostram vocacionadas para algumas áreas de aplicação, nas quais oferecem uma excelente relação entre desempenho/custo. Destacam-se as áreas de processamento de sinais e imagens, nas quais a aglutinação de \textit{chips}, cada um contendo dezenas de processadores simples e as respectivas memórias (de pequeno tamanho), podem trazer excelentes resultados.


% {\bf Principais aspectos positivos}\\

A Sincronização inerente entre processadores; a natureza do modelo de controle (único e centralizado) garante uma operação passo-a-passo, e os processadores estão conseqüentemente sempre sincronizados.

Diferentemente do que ocorre com as arquiteturas que têm controle distribuído (sejam de memória compartilhada ou não), estas ficam sujeitas as necessidades eventuais de sincronização, as quais costumam introduzir períodos de ociosidade na operação dos processadores.

\begin{figure}
	\centering
	\insimg{1}{imagens/arquitetura-generica-sincrona-matricial.jpg}

	\caption{Arquitetura genérica síncrona matricial}
	\label{fig:arqgenerica}
\end{figure}
\newpage

\textbf{Uso eficiente da memória}: a única memória que precisa acomodar programas é a memória associada ao controlador central; as memórias dos processadores podem ser dedicadas totalmente para dados.

Alguns aspectos negativos desta abordagem são: \textbf{Escalabilidade}; quando o tamanho da matriz de processadores cresce, podem surgir dificuldades de garantir, através de uma rede de interconexão de grandes dimensões, a operação totalmente síncrona dos processadores (este aspecto se potencializa com o crescimento constante do \textit{clock} dos processadores). A \textbf{Ineficiência ante desvios condicionais}; os desvios condicionais dependentes de dados, precisam ser processados independentemente, um após o outro. Esta situação é vista como um dos principais pontos de perda de desempenho desta arquitetura. E a \textbf{Dificuldade de compartilhamento}; uma vez que existe somente uma unidade de controle, a arquitetura somente pode ser utilizada por um programa/usuário de cada vez. Alguns fornecedores facultam a existência de mais de um controlador central (com o decorrente acréscimo de custo), o que permitiria o compartilhamento de recursos.

\subsection{Multiprocessadores}
\label{multiprocessadores}

A arquitetura de multiprocessadores é conhecida como fortemente acoplada, uma vez que os processadores e a memória estão interligados através de um sistema local de interconexão.

Essa arquitetura é caracterizada pelo compartilhamento global de memória pelos diversos processadores do ambiente e é esse compartilhamento global de memória que se torna o gargalo da escalabilidade do ambiente. A escalabilidade em uma configuração multiprocessada varia até algumas centenas de processadores.

\subsection{Multicomputadores}
\label{multicomputadores}

A arquitetura de multicomputadores é conhecida como fracamente acoplada, uma vez que os processadores têm suas próprias memórias locais. Essa arquitetura é caracterizada por ter até milhares de processadores. Não há um compartilhamento forte, sendo as comunicações entre os processos feitas por troca de mensagens entre os processos que estão sendo executados nos processadores.

Um exemplo de uma configuração de multicomputadores é a criação de um cluster com PCs convencionais usando uma rede local \textit{ethernet}. Diferente da configuração de multiprocessadores em que é necessário à utilização de um comutador especial, esse tipo de cluster utiliza peças encontradas em qualquer estabelecimento de informática.

\subsection{Multiprocessadores Simétricos (\textit{Symmetric Multiprocessors - SMP})}
\label{smp}

Estes ambientes são conhecidos como arquiteturas de compartilhamento total, são caracterizadas por até dezenas de processadores compartilhando os mesmos recursos computacionais e rodando um único sistema operacional. Os processadores são considerados simétricos porque têm os mesmos custos para acesso à memória principal.

A utilização de SMP é mais popular do que se imagina. Eeste tipo de máquina  é encontrada facilmente em grande parte das organizações de hoje e também vem ganhando espaço em áreas menores, reflexo da redução de custos destes equipamentos.

Um problema desta arquitetura é sua escalabilidade, pois com o aumento do número de processadores a taxa de colisão de acesso à memória também cresce, sendo  necessário a utilização de soluções de memórias de cache e globais, que serão vistos à frente.

\subsection{ccNUMA}

Na arquitetura SMP não temos uma boa escalabilidade, pois se utiliza normalmente sistemas de interconexão na forma de barramento. Este tipo de interconexão se torna o gargalo do sistema rapidamente. Assim outras opções de interconexão devem ser utilizadas, como a interconexão comutada, que utiliza comutadores (\textit{switches}) como elemento de ligação entre os processadores. Também existem outras soluções de interconexão que podem aumentar a largura de banda, mas é importante deixar claro que qualquer uma destas soluções agrega além de um custo altíssimo, retardo de comunicações entre os processadores e a memória.

Na teoria, uma arquitetura de Acesso Não-Uniforme à Memória (\textit{Non-Uniform Memory Access - NUMA}) é conhecida por sua capacidade de escalar até centenas de processadores.

Máquinas NUMA preservam o modelo de programação simples de configurações SMP, mas com o acréscimo de tempo para acesso a memória global.

A implementação prática de uma máquina NUMA é conhecida como Acesso Não-Uniforme à Memória com Coerência de Cache (\textit{Cache Coherence Non-Uniform Memory Access - ccNUMA}), pois estas já tratam vários problemas de acesso à memória desta arquitetura, como as diferenças de velocidades de acesso à memórias locais e globais, implementando sistemas de tratamento de coerência de cache.

Aplicações como banco de dados, ERP e CRM são aplicações candidatas a rodarem nessa plataforma.

\subsection{Processadores Massivamente Paralelos - MPP}

Máquinas com configuração massivamente paralelas (\textit{Massive Parallel Processors - MPP}), são arquiteturas fracamente acopladas. Computadores que seguem este paradigma são usualmente classificados como multicomputadores, e normalmente um nó deste é um multiprocessador.

Essa arquitetura é caracterizada por milhares de nós computacionais interligados por uma rede de interconexão de alta velocidade. Cada nó pode ser composto por um ou mais processadores, possuindo cache e memórias locais. Cada nó possui também seu próprio sistema operacional, onde as aplicações rodam localmente e se comunicam por sistemas de trocas de mensagens (\ref{trocademensagens}).

A escalabilidade de um MPP é maior do que arquiteturas de memória compartilhada. Os maiores computadores classificados na lista TOP500 \cite{top500} usam este paradigma.

Uma parte importante na configuração MPP é o sistema de interconexão que liga seus vários nós. Entre os principais fatores em consideração na construção destes sistemas de interconexão são, segundo DANTAS \cite{dantas}:
	\begin{itemize}
	\item Topologia;
	\item Algoritmo de roteamento;
	\item Estratégia de comutação;
	\item Controle do fluxo entre nós.
	\end{itemize}

\subsection{Sistemas Distribuídos}

Os sistemas distribuídos, sob o aspecto da arquitetura de máquinas, para a execução de aplicativos, podem ser vistos como configurações com grande poder de escalabilidade, pela agregação dos computadores existentes nas redes convencionais em um sistema único, onde a homogeneidade ou heterogeneidade do conjunto de máquinas, cada uma com seu próprio sistema operacional, permite a formação de interessantes configurações de SMPs, clusters, MPPs e grids computacionais. (\cite{dantas})

Vários aspectos na utilização de ambientes distribuídos têm de ser cuidados, aspectos como segurança, confiabilidade, latência da rede de comunicações, compatibilidades de pacotes de \textit{softwares}, entre outros.

\subsection{Clusters}

As configurações de clusters em termos de arquitetura computacional, podem ser entendidas como uma agregação de computadores de forma dedicada para a execução de aplicações específicas. Normalmente formados por computadores do tipo PC, pertencentes a uma única unidade (ex: laboratório).

A escalabilidade é um fator diferencial nestes ambientes, pois os recursos podem crescer conforme estiverem disponíveis. (\cite{dantas})


\subsection{Grids}

Grids computacionais são uma nova forma de agregar ambientes geograficamente dispersos, com objetivos claros de especificação de qualidade de serviços.
Atualmente, a Internet com uma configuração distribuída de recursos é conhecida como o ambiente que melhor pode demonstrar esse tipo de arquitetura. Em outras palavras, diferentes tipos de aplicativos com diferentes tipos de requerimentos de qualidade (exemplos são a largura de banda, latência de comunicações e \textit{jitter}\footnote{Jitter é uma variação estatística do latência na entrega de dados em uma rede, ou seja, pode ser definida como a medida de variação do atraso entre os pacotes sucessivos de dados}) são tratados de maneira igual. Em adição, os ``serviços WEB" que oferecem serviços para a execução de tarefas de usuários finais são crescentes. Desta forma, o objetivo destas configurações  é voltar toda a potencialidade de recursos e serviços disponíveis para o processamento de tarefas dos usuários pertencentes à configuração de grid (DANTAS \cite{dantas}). Grids computacionais são amplamente discutidos no capítulo \ref{grids} deste trabalho.


\section{Dependabilidade}
\label{dependabilidade}
% \cutname{dependabilidade.html}

Dependabilidade é um termo traduzido literalmente do inglês \textit{dependability} que reúne diversos conceitos que servem de medida, tais como confiabilidade (\textit{reliability}), disponibilidade (\textit{availability}), segurança (\textit{safety}), mantenabilidade (\textit{maintainability}), comprometimento do desempenho (\textit{performability}), e testabilidade (\textit{testability}). Estas são as medidas usadas para quantificar a dependabilidade de um sistema. (\cite{Pradhan})

Assim pode-se dizer que a dependabilidade é uma propriedade dos sistemas computacionais que define a capacidade dos mesmos de prestar um serviço no qual se pode justificadamente confiar (DANTAS \cite{dantas}).

Confiabilidade é a medida mais usada em sistemas em que mesmo curtos períodos de operação incorreta são inaceitáveis. Confiabilidade é uma medida probabilística que não pode ser confundida com disponibilidade. Um sistema pode ser altamente disponível mesmo apresentando períodos de inoperabilidade, desde que esses períodos sejam curtos e não comprometam a qualidade do serviço. \textit{Performability} está relacionada à queda de desempenho provocada por falhas, onde o sistema continua a operar, mas degradado em desempenho. Mantenabilidade significa a facilidade de realizar a manutenção do sistema, ou seja, a probabilidade que um sistema com defeitos seja restaurado a um estado operacional dentro de um período determinado. Restauração envolve a localização do problema, o reparo e a colocação em operação. Finalmente, testabilidade é a capacidade de testar atributos internos ao sistema ou facilidade de realizar certos testes. Quanto maior a testabilidade, melhor a mantenabilidade, por conseqüência, menor o tempo de indisponibilidade do sistema devido a reparos.

A caracterização de dependabilidade envolve ainda um conjunto de conceitos que alguns autores dividem em três grupos: os atributos, os meios pelos quais será alcançada e as ameaças. Nas próximas sessões estes três grupos serão melhores vistos.%, pois são definições importantes para clusters

\subsection{Ameaças}

Um defeito é definido como um desvio da especificação, ou a transição de estado do serviço de um sistema de correto para um serviço incorreto. Deve ser evitado que o sistema apresente defeitos, pois estes não podem ser tolerados.% Define-se que um sistema está em estado errôneo ou em erro se o processamento posterior a partir desse estado pode levar a defeito.

Define-se falha (ou falta) como a causa física ou algorítmica do erro. Falhas estão associadas ao universo físico, erros ao universo da informação e defeitos ao universo do usuário. Assim um \textit{chip} de memória, que apresenta uma falha em um de seus \textit{bits} (falha no universo físico), pode provocar uma interpretação errada da informação armazenada em uma estrutura de dados (erro no universo da informação) e como, resultado o sistema pode negar autorização de embarque para todos os passageiros de um vôo (defeito no universo do usuário). %É interessante observar que uma falha não necessariamente leva a um erro (aquela porção da memória pode nunca ser usada) e um erro não necessariamente conduz a um defeito (no exemplo, a informação de vôo lotado poderia eventualmente ser obtida a partir de outros dados redundantes da estrutura).

\begin{center}
\begin{framed}
$\Rightarrow FALHA \Longrightarrow ERRO \Longrightarrow DEFEITO \Rightarrow$
\end{framed}
\end{center}

O entendimento da relação de dependência entre falhas, erros e defeitos é a base para o conhecimento da ``patologia da falha". Essa relação, como mostrado acima, pode ser utilizada em outros componentes, não apenas físicos, e a sua utilização recursiva ajuda na análise de sistemas em diferentes níveis de abstração. Informações mais detalhadas sobre este tópico podem ser obtidas em DANTAS \cite{dantas}.

\subsection{Meios}
\label{meios}
Os meios da classificação de dependabilidade nos ajudam a trabalhar na prevenção, tolerância, remoção ou previsão das falhas. E tem como objetivo tratar as falhas que podem levar a erros, e que em sua propagação causam defeitos.

\subsubsection{Prevenção de Falhas}

A prevenção de falhas tem por objetivo aumentar a confiabilidade dos sistemas, empregando técnicas de controle de qualidade em projetos e desenvolvimento. Falhas não são facilmente previsíveis, então é preciso estruturar procedimentos para que, caso ocorram, existam formas de reparo a fim de restaurar as condições de serviços. Um exemplo de falha imprevisível é a falha de um componente de \textit{hardware}.


\subsubsection{Tolerância à Falhas}

O paradigma de tolerância à falhas é definido como a capacidade de um sistema apresentar um comportamento bem definido na ocorrência de falhas. %Existem várias estratégias de tolerância à falhas.
As formas básicas de tolerância à falhas são:
\begin{table}[!htb]
\begin{center}
% use packages: array
\begin{tabular}{l|l}\hline
 {\bf Propriedade do Sistema}& {\bf Operacionalidade Garantida} \\ \hline
Operacionalidade não garantida & Segurança garantida \\ \hline
Mascaramento & Defeito seguro (\textit{fail safe}) \\ \hline
Segurança não garantida & Sem mascaramento, Não tolerância \\ \hline
\end{tabular}
\end{center}
\caption{Formas básicas de tolerância à falhas. Fonte DANTAS \cite{dantas}}
\end{table}

A primeira forma se caracteriza pela segurança e operacionalidade garantida, é a que realiza o mascaramento, empregado para encobrir ou ocultar falhas. Neste item o serviço apresentado pelo sistema não deverá ser modificado pela ocorrência de falhas, ou seja, o sistema como um todo não deverá apresentar defeito. Logo o sistema deverá permanecer operacional e em um estado seguro para os usuários e para o meio ambiente. Esta é a forma mais completa de tolerância à falhas, a mais desejada e a de maior custo. Todas as demais formas modificam o serviço prestado pelo sistema na ocorrência de falhas (\cite{dantas}).

A tolerância à falhas consiste, basicamente, em ter \textit{hardware} redundante que entra em funcionamento automaticamente após a detecção de falha do \textit{hardware} principal.

Este texto não tem a intenção de estender demasiadamente a discussão sobre este tema podendo ser melhor visto em DANTAS \cite{dantas}.

\subsubsection{Remoção de Falhas}

Uma solução para a obtenção da dependabilidade é a opção conhecida como remoção de falhas. Esta técnica pode ser aplicada tanto na fase de desenvolvimento como durante o ciclo de vida do sistema. A remoção de falhas na fase de desenvolvimento é realizada através das etapas de verificação, diagnóstico e correção. A verificação dos mecanismos de tolerância à falhas é um importante aspecto de remoção de falhas (\cite{dantas}).

\subsubsection{Previsão de Falhas}

A previsão de falhas é o último meio utilizado para se alcançar a dependabilidade. Esta opção considera uma avaliação do comportamento do sistema com relação à ocorrência e ativação de falhas. Esta abordagem pró-ativa pode subsidiar as modificações para melhorias, tanto estruturais como para melhor eficiência/eficácia dos sistemas.


\subsection{Atributos}

Os atributos de dependabilidade têm naturezas não determinísticas das circunstâncias dos atributos que são: Disponibilidade, Confiança, Segurança, Confidenciabilidade, Integridade, Reparabilidade. Esses atributos usam medidas probabilísticas para gerar seus pesos relativos. Esses pesos são medidos dependendo da aplicação/serviço considerado, assim estes pesos variam sempre, não existindo um padrão (\cite{dantas}).

\begin{itemize}

\item Disponibilidade:\\
	Disponibilidade instantânea é o atributo, definido como a probabilidade de um sistema apresentar um serviço correto, num determinado instante de tempo t.
	Na análise de disponibilidade estamos interessados no comportamento de um sistema em determinados períodos de tempo, ou seja, estamos preocupados em observar a alternância de períodos de funcionamento correto e períodos que o sistema está de reparo. O fator importante é saber a fração de tempo na qual o sistema deverá ter condições de apresentar o serviço de forma correta.

\item Confiabilidade:\\
	É a métrica que avalia, o quanto um sistema pode apresentar um serviço correto continuamente durante um intervalo de tempo t, ou seja, a probabilidade do sistema não apresentar defeito durante o intervalo de tempo considerado.

\item Segurança: \\
	É considerada sob dois aspectos: contra catástrofes e convencional. Contra catástrofes é a probabilidade do sistema apresentar defeito que acarrete conseqüências catastróficas para seus usuários em um intervalo de tempo. E segurança convencional é a probabilidade obtida através da combinação dos atributos: disponibilidade, confidencialidade e integridade, ou seja, a probabilidade de que não ocorra acesso ou manipulação indevida no estado do sistema no intervalo de tempo.

\item Confidenciabilidade: \\
	É a probabilidade de não ocorrer divulgação indevida de informação no intervalo de tempo.

\item Integridade: \\
	É a probabilidade de não ocorrer alterações impróprias de estado em um sistema no intervalo de tempo.

\item Reparabilidade: \\
	Esta métrica avalia o quanto um sistema pode ser restaurado, retornando ao estado de serviço correto em determinado tempo, dado que o mesmo apresentou defeito.
\end{itemize}



\section{Escalonamento}
\label{escalonamento}
% \cutname{escalonamento.html}

Escalonamento é um processo de tomada de decisões que se preocupa com a alocação de recursos limitados para tarefas ao longo do tempo, e possui como meta a otimização de uma ou mais funções-objetivo.% Tais recursos e tarefas podem tomar muitas formas. Os recursos podem ser máquinas em um chão de fábrica, pistas em  um aeroporto, processadores em um sistema de computação, entre outros.
As tarefas podem ser operações em um processo de produção, execução de \textit{software} em um sistema de computação, entre outros. As funções-objetivo também podem ser diversas, como a minimização do tempo médio gasto por uma atividade de montagem de peças em uma máquina de uma linha de produção ou a minimização do tempo de execução de uma tarefa computacional.

Escalonadores de tarefas são componentes de \textit{software} comumente integrados a sistemas operacionais paralelos e/ou distribuídos e que têm como função a distribuição de trabalho computacional para as unidades de processamento integrantes do sistema, de modo a maximizar o desempenho global do processamento realizado, isto é, promover o balanceamento de carga entre as unidades de processamento envolvidas.

Em sistemas homogêneos, o problema de balanceamento de carga pode ser reduzido a uma divisão de um determinado trabalho computacional em $N$ porções iguais e que possam ser distribuídas e executadas por $N$ unidades de processamento do sistema, supostamente idênticas. Neste caso, o problema está fortemente relacionado à maneira de como representar o trabalho computacional a ser processado e a melhor maneira de dividí-lo em várias partes iguais.

Em sistemas heterogêneos, o problema de balanceamento de carga é consideravelmente mais complexo e, nestas circunstâncias, o escalonador de tarefas ganha especial importância. Para que o conjunto heterogêneo de unidades de processamento possa ser utilizado de maneira eficiente, questões como predição e monitoramento de desempenho, passam a integrar o problema de balanceamento de carga.

Isso significa que um bom compromisso, entre o tempo de processamento despendido na busca por uma solução e a qualidade da solução encontrada, deva ser satisfeito, e é no contexto deste compromisso que as principais linhas de desenvolvimento de escalonadores ganham forma: a dos escalonadores estáticos e a dos dinâmicos.

Um importante aspecto dos escalonamentos estáticos é que seu cálculo se faz de maneira totalmente  independente da distribuição das tarefas. O escalonamento é feito em duas etapas: na primeira etapa o cálculo do escalonamento é realizado, ou seja, a atribuição das tarefas às unidades de processamento é definida; no segundo momento, um mecanismo de distribuição de tarefas deve entrar em ação para promover a distribuição previamente calculada.

Uma importante conseqüência deste modelo de escalonamento é a necessidade de se ter informações precisas sobre o sistema considerado. Assim, o bom funcionamento de um escalonamento de tarefas estático, requer uma estimativa precisa do desempenho do sistema em questão e a qualidade deste escalonamento é um resultado direto da precisão com que estas estimativas são obtidas. Nestas circunstâncias, estimativas imperfeitas ou ocorrências de eventos inesperados, que afetem o desempenho do sistema durante a execução das tarefas previamente escalonadas, podem fazer com que seu desempenho global sofra significativos decréscimos.

Apesar desta aparente limitação, o escalonamento estático é largamente utilizado em sistemas paralelos reais, uma vez que sua simplicidade de implementação lhe confere grande robustez e facilidade de manutenção. Nestes sistemas a ocorrência de eventos que afetem significativamente o desempenho do escalonamento é rara e os resultados são freqüentemente satisfatórios.

Em oposição a esta técnica está a dos escalonadores dinâmicos. O escalonamento dinâmico pode ser entendido como a aplicação de sucessivos escalonamentos estáticos sobre estados intermediários de execução da aplicação, à medida que ela é executada. Os momentos em que cada um desses escalonamentos é realizado varia de escalonador para escalonador, mas o aspecto mais importante dos escalonadores dinâmicos, é o que justifica o emprego do termo ``dinâmico", e o fato de o escalonamento ser feito concorrentemente à distribuição e execução das tarefas das aplicações.

Ao produzir-se um escalonamento com essas características, beneficia-se da habilidade em lidar com grande parte das decisões de escalonamento em tempo real, o que eliminam muitos dos problemas do caso estático. Embora as decisões ainda se baseiem em estimativas de desempenho do sistema e, conseqüentemente, estimativas imprecisas ainda podem significar um escalonamento ineficiente. Com isso, as conseqüências de um mau escalonamento não são tão impactantes quanto seriam no caso estático. Assim, atrasos ou adiantamentos no tempo de conclusão de uma determinada tarefa podem ser utilizados em tempo real para o reescalonamento das tarefas restantes a serem executadas. Uma vantagem adicional do fato de seu processamento ser realizado concorrentemente a execução da aplicação escalonada e que isso pode significar economia de tempo global com relação ao caso estático.

Entretanto, os escalonadores dinâmicos possuem seus inconvenientes. Em contrapartida aos escalonadores estáticos, a implementação dos escalonadores dinâmicos é trabalhosa e requer a manipulação e gerência de estruturas de dados freqüentemente complexas. Esse fato torna este tipo de escalonador pesado, sob o ponto de vista da implementação e execução, e menos robusto já que, na eventual ocorrência de uma falha, um grande trabalho de recuperação de estado deverá ser feito.


% Paradigmas de balanceamento de carga

Outro importante aspecto no projeto de escalonadores de tarefas é o paradigma de operação adotado. A existência de diferentes paradigmas advém do fato da implementação do escalonador de tarefas, estar diretamente vinculado às maneiras de como as unidades de processamento do sistema distribuído em questão estejam conectadas entre si, tanto física quanto logicamente. Assim, existe um grande número de paradigmas de balanceamento de carga, emergidos de diferentes topologias de interconexão, cada qual adaptado às características do ambiente computacional no qual foi concebido.
% 
% % Nas subseções a seguir são apresentadas breves descrições dos mais comuns paradigmas de balanceamento de carga.
% 
% 
% 
% % \subsection{estático}
% % 
% % \subsection{dinâmico}
% \subsection{Escalonamento Estático e Dinâmico}
% 
% 
% A diferença entre uma operação de escalonamento estático e dinâmico é que, no primeiro, todos os jobs são conhecidos de antemão. O objetivo é escalonar estes jobs apenas uma vez, sendo este escalonamento fixo, já que não é necessário mudá-lo. Já em um escalonamento dinâmico, o sistema não possui apenas um conjunto de jobs fixo, mas estes chegam ao sistema em pontos assíncronos de tempo, e enquanto novos jobs chegam, outros estão executando. A cada chegada ou saída de um job no sistema, o conjunto de jobs conhecidos muda.
% 
% A simples inserção de um novo job no sistema sem uma revisão do schedule já gerado pode levar a uma deterioração dos resultados deste último, e por isso tal dinamismo leva a questões como o re-escalonamento (rescheduling), onde a preocupação não é gerar um schedule novo a partir do zero, mas alterar o já existente de forma a contemplar o novo job, tentando ser o menos complexo possível nesse procedimento.

\section{Alta Disponibilidade}
\label{altadisponibilidade}
% \cutname{altadisponibilidade.html}

Um sistema computacional é composto por diversos componentes eletrônicos que podem falhar impedindo o acesso a informação. A crescente demanda por sistemas que possam deixar informação disponível para ser acessada, modificada, armazenada pelo maior tempo possível levou fabricantes de \textit{hardware} e desenvolvedores de \textit{software} a pensarem em maneiras de como contornar esses problemas de paradas de sistemas, sejam elas causadas por falhas internas (causadas por mal funcionamento de \textit{hardware}, erros introduzidos por \textit{softwares} ou outras razões de natureza imprevisível, como interferência magnética) ou mesmo paradas programadas para manutenção.

O conceito de alta disponibilidade é caracterizado por um sistema desenhado para impedir perda de um serviço por ele disponibilizado, reduzindo ou gerenciando falhas (mais detalhes em \ref{meios}) bem como minimizando tempo de desligamento planejado para manutenção.

Este conceito não se resume a um \textit{software} específico, mas a um conjunto de mecanismos e técnicas que tem por objetivo detectar, contornar e mascarar falhas que venham a ocorrer ocasionando perda de acessibilidade.

É senso comum na literatura caracterizar a disponibilidade pela probabilidade de um sistema estar acessível em determinado período de tempo. %Com esta caracterização os sistemas são classificados pelo numero de noves que indicam sua disponibilidade:

A Tabela \ref{tabela:disponibilidade} ilustra um dos termos de comparação geralmente utilizado na avaliação de soluções HA: níveis de disponibilidade segundo tempos de indisponibilidade (\textit{downtime}). Excluídos desta tabela, os tempos de \textit{downtime} estimados (geralmente para manutenção ou reconfiguração dos sistemas) que são alheios às soluções e muito variáveis.

\begin{table}
\begin{center}
% use packages: array
\begin{tabular}{p{4cm}|p{4cm}|p{4cm}}
\hline

 \textbf{Disponibilidade (\%)}
&\textbf{\textit{Downtime}/ano}
&\textbf{\textit{Downtime}/mês}
\\ \hline

 95%
 &18 dias 6:00:00
 &1 dia 12:00:00
\\ \hline
 96%
& 14 dias 14:24:00
& 1 dia 4:48:00
\\ \hline
 97%
& 10 dias 22:48:00
& 0 dias 21:36:00
\\ \hline
 98%
& 7 dias 7:12:00
& 0 dias 14:24:00
\\ \hline
 99%
& 3 dias 15:36:00
& 0 dias 7:12:00
\\ \hline
 99,9%
& 0 dias 8:45:35.99
& 0 dias 0:43:11.99
\\ \hline
 99,99%
& 0 dias 0:52:33.60
& 0 dias 0:04:19.20
\\ \hline
 99,999%
& 0 dias 0:05:15.36
& 0 dias 0:00:25.92
\\ \hline
\end{tabular}
\end{center}
\label{tabela:disponibilidade}
\caption{Níveis de Alta Disponibilidade}
\end{table} 

Quanto maior a disponibilidade desejada ao sistema, maior a redundância e custo das soluções, tudo depende do tipo de serviço que se pretende disponibilizar e de outras variáveis intrínsecas ao sistema. Há casos em que o custo do sistema indisponível é muito maior que o custo de desenvolvimento de um ambiente de alta disponibilidade para o mesmo. Informações mais detalhadas sobre este assunto podem ser obtidas na sessão \ref{dependabilidade} deste documento, em DANTAS \cite{dantas} e \textit{softwares} que trabalham a disponibilidade de sistemas serão discutidos no capítulo \ref{clusteraplicacao} também neste documento.

\section{Balanceamento de Carga}
\label{balanceamentodecarga}
% \cutname{balanceamentodecarga.html}

Quando se projeta um sistema computacional, sabe-se a carga média e máxima que este irá suportar. Apartir do momento em que a carga de utilização do sistema começa a se tornar excessiva, é preciso buscar uma solução para o aumento de capacidade do sistema, que pode ser basicamente: i) aquisição de uma máquina de maior capacidade computacional, ii) melhoria de performance do sistema e iii) utilização de sistemas de balanceamento de carga.

Os sistemas de balanceamento de carga são em geral a repartição da execução do serviço por várias máquinas. Estas soluções podem se especializar em pequenos grupos sobre os quais se faz um balanceamento de carga: utilização da CPU, de armazenamento, ou de rede. Qualquer uma delas introduz o conceito de clustering, ou \textit{server farm}, já que o balanceamento será, provavelmente, feito para vários servidores.

Informações sobre a implementação de algumas soluções de balanceamento de carga em Software Livre serão discutidos no capítulo \ref{clusteraplicacao} deste documento.

\section{Redes de Comunicações}
\label{redesdecomunicacao}
% \cutname{redesdecomunicacao.html}
\input{parte3/redes.tex}
% \section{redes de comunicação}
% \subsection{topologia de rede}
% 
% \subsection{protocolos}
% 
% \subsection{Dispositivos de interconexão}
% 
% \subsubsection{Ethernet}
% \subsubsection{myrinet}
% \subsubsection{SCI}
% \subsubsection{infiband}
% \subsubsection{Quadrics}

