Processos: modo computacional

A multi programação consiste na execução em pseudoparalelismo de vários programas na mesma máquina, onde os vários fluxos de execução são multiplexados no tempo, cada fluxo é designado por processo.

Os elementos principais que constituem um processo são um espaço de endereçamento, que normalmente se divide numa região para o código, outra para a pilha e outra para os dados globais e alocados dinamicamente (heap). Cada processo tem um estado que pode ser salvaguardado e posteriormente reposto, de forma a permitir a comutação entre processos. Um processo tem ao seu dispor um reportório de operações, que consiste nas instruções máquina do processador e nas operações exportadas pelo sistema operativo (chamadas de sistema).

O modelo de segurança baseia-se no isolamento entre processos, o que significa que os processos não podem interferir uns com os outros e na existência de um utilizador que é o dono do processo, em função do qual são definidas as acções que o processo pode executar sobre os restantes recursos do sistema operativo, uma vez que estes acessos são sempre mediados pelo núcleo.

Os processos organizam-se normalmente de forma hierárquica, em que um processo ao criar outro estabelece uma relação de pai-filho nessa hierarquia. Algumas informações são herdadas do processo pai para os processos filhos.

pid_t fork(void)- chamada ao sistema para a criação de um novo processo

1- Quando um processo invoca a chamada ao sistema fork() o sistema operativo vai executa-la em modo protegido (modo sem restrições de execução)

2- O Sistema Operativo verifica se o processo que invoca o fork() ainda não esgotou o número máximo de processos filhos e em caso afirmativo executa o fork()

3- O processo inicial é duplicado (estruturas de dados do núcleo, zonas de memória, etc..) e ao novo processo é atribuído um novo PID

4- O novo processo integra a lista de processos candidatos a usar o  CPU

5- O Sistema Operativo retorna o PID do filho ao Pai e zero ao filho. A execução de cada um destes processos é retornada na instrução seguinte ao fork()

Um processo pode ser visto como objecto, com propriedades e operações. As propriedades fundamentais são um identificador, o ficheiro com o programa executável, o seu espaço de endereçamento, prioridade, estado de execução, processo pau, canais de E/S, ficheiros abertos quotas de utilização de recursos, contexto de segurança e ambiente utilizador

As operações definem a interface do sistema operativo para manipular processos e incluem operações para criar um novo processo auto – terminar, para eliminar outro processo, para esperar pela terminação de outro processo, para suspender a execução de um processo, ou auto suspender-se e para ler o estado do processo.

            A operação sobre processos que se desvia mais do modelo computacional genérico é a operação de criação de processos Unix (fork), que cria um novo processo absolutamente idêntico ao processo pai. Para o processo filho executar um programa diferente do pai, é necessário que este invoque uma segunda função (exec) que altera o programa a ser executado.

exec():
Quando um processo invoca a chamada ao sistema execxx o núcleo do Sistema Operativo vai reescrever as zonas de memória associadas ao processo (filho zona estática e dinâmica de dados e código) com a informação existente no ficheiro executável indicado como parâmetro. A execução do processo é iniciado no main() do novo código.

Em Unix, o tratamento das excepções e de acontecimentos assíncronos tem particular importância. Os signals são muito semelhantes ao modelo de rotinas assíncronas e foram a ideia original desta extensão ao modelo de programação estruturado. Os acontecimentos assíncronos podem ser analisados a um processo em execução através da activação de um signal. Os acontecimentos susceptíveis de gerarem um signal tem origens muitos diversas, e são referenciados num ficheiro de texto (signal.h) que indica o respectivo nome lógico e o valor inteiro que é usado para codifica-lo internamente no núcleo.

Organização do Sistema Operativo

O sistema operativo é usualmente composto por três entidades: o núcleo, as bibliotecas de chamadas sistema e os processos de sistema.

O núcleo implementa o mecanismo de base do sistema operativo. Em particular, a gestão dos processos, da memória, dos ficheiros, das E/S e a comunicação entre processos.

O funcionamento do núcleo é fortemente influenciado por mecanismos de hardware que permitem garantir o seu funcionamento seguro. A segurança do sistema operativo advém da existência de um isolamento entre os processos dos utilizadores, e entre estes e o núcleo do sistema operativo.

O isolamento é garantido pela gestão da memória que só permite determinadas posições de memória sejam acessíveis por um utilizador. Mas como o funcionamento do núcleo tem de ser partilhado por todos os processos é forçado que exista um mecanismo não controlado directamente pelos programas utilizador para gerir estas alterações do espaço de endereçamento.

Esta componente de hardware gere a dualidade de execução do processador em modo de utilizador e modo núcleo: o modo utilizador restringe o acesso a determinadas posições de memória e certas instruções que podem ultrapassar o isolamento como as que interagem directamente como os periféricos ou com as instruções; em modo núcleo não existem tais restrições, sendo este o modo que o núcleo do sistema operativo se executa.

As chamadas sistema são implementadas por um função que invoca a excepção (trap) que transfere o controlo para o núcleo e automaticamente coloca o processador no modo de execução núcleo.

No núcleo é feita a escolha do código apropriado que implementa a chamada ao sistema em causa. No final da chamada, a instrução de retorno de interrupção devolve o controlo para a função de biblioteca que, por sua vez retorna para o código do utilizador.

Os processos sistema executam funções que podem ser delegas em processos autónomos, de forma a reduzir a complexidade do núcleo ou aumentar a sua robustez. Estes processos executam-se em modo utilizador mas pertencem ao sistema operativo pelo que tem privilégios de administrador, contudo, para invocar funções do sistema tem de o fazer através das chamadas ao sistema, o que é menos eficiente do que se a execução fosse directamente do núcleo.

Uma organização do núcleo em camadas generaliza o conceito de protecção entre modo núcleo e modo utilizador, dividindo o núcleo em várias camadas que implementam diferentes funcionalidades e obrigando as camadas mais externas a invocar funções das camadas internas através do mecanismo semelhante aos das chamadas do sistema.

Chamadas de sistemas

-> fork()
pid_t fork(void)- chamada ao sistema para a criação de um novo processo

1- Quando um processo invoca a chamada ao sistema fork() o sistema operativo vai executa-la em modo protegido (modo sem restrições de execução)
2- O Sistema Operativo verifica se o processo que invoca o fork() ainda não esgotou o número máximo de processos filhos e em caso afirmativo executa o fork()
3- O processo inicial é duplicado (estruturas de dados do núcleo, zonas de memória, etc..) e ao novo processo é atribuído um novo PID
4- O novo processo integra a lista de processos candidatos a usar o CPU
5- O Sistema Operativo retorna o PID do filho ao Pai e zero ao filho. A execução de cada um destes processos é retornada na instrução seguinte ao fork()

->exit()
void exit(int estado)

1- Quando um processo invoca a chamada exit() o núcleo do Sistema Operativo recolhe todos os recursos associados com o processo em causa
2- No entanto, o núcleo do Sistema Operativo preserva o código de finalização enviado como argumento da chamada exit() para terminar a sua recolha pelo processo que termina
3- Só se perde referência completa a um processo desde o seu pai recolher o seu código de finalização

-> exec():

Quando um processo invoca a chamada ao sistema execxx o núcleo do Sistema Operativo vai reescrever as zonas de memória associadas ao processo (filho zona estática e dinâmica de dados e código) com a informação existente no ficheiro executável indicado como parâmetro. A execução do processo é iniciado no main() do novo código

-> wait()

1-Verifica se contêm algum filho a executar (caso falhe, retorna <0)
2- Verifica se algum filho terminou
3- Se nenhum dos filhos terminou o processo fica bloqueado até que algum destes termine
4- Recolhe o estado do primeiro processo filho que terminar
5- Retorna o PID do processo que terminou

-> waitpid()

Contêm um comportamento semelhante á chamada wait(), no entanto bloqueia somente para aguardar por um PID especifico(passado como argumento) termine.

Como abordar um Problema? Dividir para Conquistar

Projectar o  programa antes de programá-lo

Nunca comece a programar a partir do nada. Deve-se sempre esquematizar alguns pseudo-códigos explicando o que o seu programa vai fazer (em um nível mais elevado) antes de começar a programar.

Quando se começa a escrever um programa sem ter pensado nele antes, fica difícil visualizá-lo como um todo. Criando um rascunho prévio do programa, podem aparecer várias abordagens do problema e as dificuldades ficam mais fáceis de serem superadas. Esquematizar o programa ajudar a fixar exactamente o que se deseja e economiza-se bastante tempo em frente ao monitor na tentativa de escrever um programa que cumpra o desejado.

Escreva um código legível

Escrever um código legível é muito importante para facilitar o entendimento de um programa. Até para o próprio criador do código. Um programa claro e auto-explicativo fica mais difícil  de se perder e torna muito mais fácil a depuração.

Comente seu código enquanto escreve, não depois

Comentários são ferramentas muito úteis para tornar o código mais legível. É interessante comentar tudo que não seja muito claro. Não comente algo que seja óbvio (p/ ex.: "i := 0 { Atribui ovalor 0 à variável i }" ). Comente algo como: "x:= 40 - Lenght(frase)/2 { x recebe a posição para frase ficar centralizada }".

Em programas muito grandes ou complicados, é interessante criar um cabeçalho comentado em cada função, definindo exactamente o que espera-se que ela faça, quais suas entradas e quais suas saídas. O pseudo-código rascunhado pode ser muito útil para isso. Agindo assim, não se precisa ler diversas linhas de código para saber o que uma função faz.

É recomendável que se escreva os comentários enquanto se escreve o programa, pois é menos provável que se escreva alguma coisa útil ou significativa depois. Escreva enquanto programa e seus comentários serão muito mais completos.

Utilize funções e procedimentos curtos e objectivos

Evite sempre funções/procedimentos grandes que englobem todo tipo de processamento. Separe algoritmos distintos em suas próprias funções/procedimentos. Projecte a  sua grande função/procedimento em várias pequenas, de forma que seu programa fique mais fácil de ler e entender.

Dessa forma, cada parte do seu programa fica bem definida e torna-se muito mais fácil escrevê-lo, pois pode-se fazê-lo passo a passo. Dessa forma, a cada parte que se termina, pode-se verificar se ela está correta. Além disso a localização de um problema no programa também fica facilitada, pois ele se restringirá a um bloco menor de código.

Conclusão:

Lembre-se que a maior parte do tempo que se gasta programando é corrigindo e modificando código existente. Relativamente pouco tempo é realmente utilizado para adicionar coisas novas. Isso significa que você gastará muito tempo lendo o seu código, então faz sentido gastar algum tempo aprendendo a escrever um código legível. Código legível é fácil de escrever, fácil de depurar e fácil de manter. Você realmente sai ganhando!

Guia prático para resolução de problemas de programação 

1) Entender o problema

Estar certo de que tenha entendido o problema;
* O que é a entrada?
* O que é a saída?

2) Resolver o problema à mão

Resolva pequenas instâncias do problema à mão;
* O que acontece?
* Pensar  em casos variados;
* Pense em como (qual algoritmo) você utilizou para resolver o problema.

3) Definir o algoritmo

* Defina precisamente o algoritmo a ser utilizado
* Rascunhe as etapas do programa

4) Programar

* Como escrever o algoritmo na linguagem utilizada?
* Que estrutura de dado utilizar?
* Divida o programa em partes menores;

* Escreva um programa de fácil leitura;
* Pense nos casos patológicos.

4) Depurar

* Explique o programa para si mesmo;
* Por que funciona?
* A leitura de dados está sendo feita correctamente?
* Variáveis inicializadas?
* Verificar casos patológicos;
* Localizar o erro restringindo os blocos de códigos (cercando o erro)
* Comandos e loops aninhados correctamente?

Filas prioritária( Algoritmos e estruturas de dados 1)

filas prioritárias
->estrutura de dados linear
->tipo de dados
    abstracto (ADT) com as seguintes prioridades:
* supostas operações de - inserção( de um novo elemento na fila)
                -remoção do elemento que esta na cabeça  da fila isto é, o elemento maior  prioridade,tipicamente o elemento com maior de chave

API da fila prioritária(PG-Priority Queue)

void insert QP(PQueu *pq,int elemento)
int DelMaxPQ(PQueu*pq)


exemplo: os seguintes n=8, a chegar por esta ordem á fila
5,2,7,3,1,8,6,4



3 Implementações de possíveis PQ:
a)Usar um vector não ordenado
    - quando chega um elemento é colocado no final do vector(custo 1-constante)
    - quando queremos remover o maior elemento temos fazer n comparações para determinar o maior elemento

b)Usar um vector ordenado
- quando chega um novo elemento é feita a fusão ordenada com o vector ordenado já  existente(inserção tem custo linear)
- remoção com custo, constante-1

c)Binary Heap
- implementar uma árvore binária balanceado usando um vector

ex: árvore binária
- estrutura de dados não linear em que casa elemento tem: 0,1, ou 2 filhos
-existe uma só raiz na árvore
-> A árvore binária satisfaz as seguintes condições
   - todos os niveis estão completamente preenchido excepto o ultimo nível que pode estar parcialmente preenchido

-> Para uma Binary Heap
que implemente uma fila prioritária(PQ) sem elementos repetidos, dado qualquer elemento da árvore binária ele tem que ser sempre maior que os seus filhos (0,1, ou 2 filhos)

->nuance de implementação vamos deixar a posição 0 do vector da raiz aparece na posição 1
-> Dado um elemento da posição(índice) k o seu pai esta na posição k/2(divisão inteiro)
->os filhos do elemento de índice k estão nas posições 2*k e 2*k+1

Algoritmo de Pesquisa Binária

Para a implementação da pesquisa binária num vector V de N valores inteiros ordenados de uma forma crescente, adopta-se o seguinte algoritmo:

Função  Pesquisa_Binária(V,N,X)
{   
  1.Inicializar a  pesquisa e inicializar variáveis
        ini=1;
        fim=N;
2. Percorrer o vector para encontrar o elemento
      Do While   ini <= fim
                meio= INT((ini+fim)/2)

                 if  X <V[meio]
                    then fim= meio-1
                 else   if x> V[meio]
                        then ini= meio+1;
                                 else   write("elemento encontrado")
                                       return (meio)
3. Percorreu todo o vector e não encontrou o elemento
  return (0)

Pesquisa Binária

Pesquisa Binária

A estratégia a adoptar neste algoritmo passa por comparar o elemento que procuramos com o valor do elemento armazenado no meio do vector.

* Se esse elemento for menor que o elemento do meio, então conclui-se que, se o elemento estiver presente no  vector , ele estará na primeira parte do mesmo.

* Se o elemento a pesquisar for maior, então estará na segunda parte do vector. Logicamente que se for igual, estará encontrado o elemento do vector e a pesquisa ficará concluída.

*  Se o elemento estiver estiver num das partes do vector, repete-se o procedimento considerando apenas a parte que restou e compara-se o elemento a procurar com o elemento de armazenado no meio dessa parte.

Em suma:
Há 3 tipos de comparações entre o elemento X a pesquisar e o valor v[i] que representa o valor posicionado no meio da estrutura de dados:


     -> Se o X= V[i] então a pesquisa é bem sucedida. A pesquisa termina.

     -> Se o X <V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que procedem V[i], ou seja na primeira metade da lista.

     -> Se X> V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que sucedem V[i], ou seja na segunda metade da lista