Engenharia Software

INTRODUÇÃO

Neste trabalho será abordada toda a matéria do 3º Semestre, dentro deste contexto serão apresentados os conceitos de listas lineares, FIFO, FILO, seus apontadores, ordens de inclusão, exclusão e pesquisa. Definirei também os conceitos de alocação simplesmente encadeada, alocação duplamente encadeada, com representações gráficas das duas.

Em relação a banco de dados, definirei os conceitos das propriedades ACID de uma transação e sua importância para um SGBD; e serão apresentadas duas ferramentas para se fazer ORM, bem como a explanação sobre o que é ORM e seus paradigmas.

No

que tange a UML será mostrado os conceitos de polimorfismo e herança, bem como exemplos que os representem em diagramas de classe.

LISTAS LINEARES

Lista Linear é a estrutura que permite representar um conjunto de dados afins, de forma a preservar a relação de ordem linear de seus elementos.

Exemplos diários de listas lineares:

- Letras de uma palavra

- Palavras de uma frase

- Pessoas esperando ônibus

fifo

As listas são amplamente utilizadas em programação para implementar filas de espera. Em uma fila de tipo FIFO os elementos vão sendo colocados na fila e retirados (ou processados) por ordem de chegada. A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

Como exemplo de aplicação para filas, pode-se citar a fila de processos de um sistema operacional. Nela, é estabelecido um tempo a ser usado por cada um dos processos. Se durante a execução de um processo o tempo passa de a, este é posto na fila e o processo seguinte é executado. Se o processo seguinte não terminar de ser executado no tempo, ele é posto na fila e o processo subsequente é executado, e assim por diante até todos os processos serem executados.

Aplicações FIFO

Os algoritmos FIFO's são comumente usados em circuitos eletrônicos de buffer e controle de fluxo, que vai desde o hardware até o software. Na forma de um hardware o FIFO consiste basicamente de um conjunto de ler e escrever ponteiros, armazenamento e lógica de controle. Armazenamento pode ser SRAM, flip-flops, fechos ou

qualquer outra forma adequada de armazenamento. Para o FIFO, de tamanho não trivial, uma SRAM de porta dupla geralmente é utilizada quando uma porta é usada para a escrita e a outra para leitura.

O FIFO síncrono aonde o mesmo clock é usado para leitura e escrita. Um FIFO assíncrono utiliza diferentes relógios para leitura e escrita. Uma aplicação comum de um FIFO assíncrono utiliza um código de Gray (código binário refletido), ou qualquer unidade de código à distância, para ler e escrever os ponteiros para garantir a geração de bandeira confiável. Uma nota mais preocupante é que se deve necessariamente usar a aritmética de ponteiro para gerar bandeiras para implementações assíncronas FIFO. Por outro lado, pode-se usar a abordagem de um balde "de fuga" ou a aritmética de ponteiro para gerar bandeiras nas implementações síncronas FIFO.

Exemplos de sinalizadores de status FIFO incluem: cheios, vazios, quase cheio, quase vazio, etc.

Vantagens e Desvantagens do FIFO

* Vantagens:

* O mais simples entre os processos de escalonamento;

* Todos os processos tendem a serem atendidos.

* Desvantagens:

* Muito sensível à ordem de chegada;

* Se processos maiores chegarem primeiro aumentarão o tempo médio de espera;

* Não garante um tempo de resposta rápido;

* Não é eficiente em sistemas de tempo compartilhado;

* Não é eficiente em sistemas em tempo real.

filo

Em ciência da computação, a FILO (First In, Last Out, que em português significa primeiro a entrar, ultimo a sair) refere-se a estruturas de dados do

tipo pilha. É equivalente a LIFO, que significa Last In, First Out.

O conceito de pilha é amplamente utilizado na informática, como, por exemplo, durante a execução de um programa, para o armazenamento de valores de variável local a um bloco e também para conter o endereço de retorno do trecho de programa que chamou a função ou procedimento atualmente em execução.

Usam-se os termos push e pop para denominar a inserção e remoção de elementos da pilha, respectivamente. Usa-se o termo top para consultar o elemento do topo da pilha, sem o remover.

Uma pilha é uma lista linear na qual o primeiro elemento a entrar é o último elemento a sair. Ela possui apenas uma entrada, chamada de topo, a partir da qual os dados entram e saem dela.

ALOCAÇÃO SIMPlISmente Encadeada

A maneira mais simples de acomodar uma lista linear em computador é através da utilização de um vetor. A representação por vetor explora a sequencialidade da memória de tal forma que os nós de uma lista sejam armazenados em endereços contíguos, ou igualmente distanciados um do outro.

X1 X2 X3 X4 X5 X6 Xn-1 Xn

Exemplos de algoritmos para as operações de inserção e retirada de um elemento numa pilha com alocação contígua:

VARIÁVEIS: TOPO (índice que indica a última posição ocupada)

MÁXIMO (variável cujo valor representa o tamanho do vetor)

VALOR (elemento incluído/retirado)

INICIO INSERIR

SE TOPO = MAXIMO ENTÃO

“OVERFLOW”

SENÃO

TOPO := TOPO + 1

VETOR[TOPO] := VALOR

FIM SE

FIM

INICIO RETIRAR

SE TOPO = 0 ENTÃO

“UNDERFLOW”