Sistemas Operacionais I

Sistemas Operacionais I

Sistemas Operacionais I

Deadlock:

Um deadlock ocorre quando um processo está esperando alguma evento que nunca ocorrerá. Isto se da por conseqüência do compartilhamento de recursos do sistema entre vários processos, cada processo deve ter acesso a um recurso de forma exclusiva.

Ex. o Processo A possui o Recurso 2, este mesmo processo solicita um outro recurso (Recurso 2) que foi atribuído ao Processo B e este solicita o Recurso 2 que é do Processo 1. O recurso fica atribuído ao processo até que ele acabe, formando assim uma espera circular.

Processo A

Recurso 1

Recurso 2

Processo B

Condições para que ocorra um deadlock:

  • Cada recurso seja alocada a um único processo em um determinado instante;

  • O processo (que já possui um recurso locado) deve estar esperando por outros recursos;

  • O recurso não pode ser liberado do processo;

  • Um processo pode ter que esperar um recurso alocado a um outro processo (espera circular).

Prevenção de um deadlock

  • Ausência de exclusão múltipla (nenhum processo terá que esperar para ter acesso a um recurso;

  • Evitar que processos que já possuam recursos garantidos solicitem um outro recurso(todos os recursos necessários são requisitados antes de começar a execução);

    • desperdício de recursos do sistema;

    • dificuldade para prever todos os recursos a serem solicitados;

    • pode ocorrer starvation(todos os recursos necessários jamais estejam disponíveis no mesmo tempo.

  • Permitir que recursos sejam retirados do processo, caso outro processo esteja solicitando;

    • o processo pode perder todo o processamento;

    • starvation (o processo garante os recursos necessários para a execução e o sistema libera em seguida.

  • Excluir a possibilidade de espera circular(forçar o processo a ter apenas um recurso por vez e quando solicitar outro deve liberar o primeiro).

Detecção do deadlock

A detecção do deadlock permite identificar quais os processos e recursos envolvidos no problema.

O sistema deve manter estruturas de dados capazes de identificar cada recurso do sistema: o processo que está alocando e os processos que estão a espera da liberação do recurso.

Correção do deadlock

A correção pode ser feita: eliminando um ou mais processos envolvidos no deadlock, desalocar os recursos já garantidos por eles (quebrando assim a espera circular).

Gerência de memória:

Na memória principal estão todos os programas e dados que serão executados pelo processador

Memória lógica: é aquela que o processador enxerga, o processo é capaz de acessar.

Memória física: é aquela implementada pelos circuitos integrados de memória, pela eletrônica do computador.

Endereço

Físico

Endereço

Lógico

CPU

Gerenciador de Memória

Memória

Alocação contígua simples

  • A memória principal é dividida em duas partes: uma para o sistema operacional e outra para os programas do usuário;

  • Implementada nos primeiros sistemas operacionais;

  • Ainda é implementada em sistemas monoprogramáveis;

Sistema Operacional

Memória Principal

Área para os programas do usuário

  • Não permite a utilização eficiente do processador e da memória;

  • Apenas 1 usuário pode dispor destes recursos;

  • Caso o programa do usuário não preencha totalmente a memória existe um espaço sem utilização.

Quando o tamanho do programa for maior que a memória disponível utiliza-se a técnica de overlay, programa é dividido em módulos que são executados independentemente na mesma área de memória.

Alocação particionada

Partições fixas

A memória é dividida em tamanhos diferentes, porém fixos.

  • O tamanho da partição é definido na inicialização do sistema;

  • A memória é dividida em uma parte para o uso do sistema operacional e a outra para o uso dos programas do usuário

  • A parte dos usuários é subdividida em partições fixas;

  • Quando um programa deve ser carregado é escolhida uma partição livre, a partição deve ser de tamanho maior ou igual a do programa, se não houver espaço suficiente o programa não é executado.

Sistema Operacional

Partição 1

Memória Principal

Partição 2

Quando os programas não utilizam completamente a partição sobram pequenos fragmentos me memória livre. Que não podem ser ocupadas por nenhum outro programa

Partição 3

Partição 4

Problemas:

  • Desperdício de memória provocado pela fragmentação interna (quando um programa não ocupa totalmente a área da partição esta memória livre não pode ser aproveitada por nenhum outro programa);

  • Não é possível fazer o uso de duas partições para um mesmo processo. Isso gera fragmentação externa(quando temos memória disponível mas ela está em partições diferentes, nenhuma delas é grande o bastante para guardar o programa.

Partições variáveis

O tamanho da partição é ajustado conforme as necessidades exatas do processo

  • O sistema operacional mantém uma lista de lacunas(espaços livres de memória física);

  • Quando um processo é criado, será usada uma lacuna de espaço maior ou igual a do programa;

  • O programa recebe o tamanho exato do programa, o que sobrar é transformado em uma nova lacuna;

  • Não ocorre fragmentação interna (o tamanho da memória alocada é igual ao tamanho do programa);

  • Ocorre fragmentação externa (a medida que as áreas de memória são alocadas e desalocadas pequenos fragmentos de memória são gerados e os fragmentos são pequenos demais para serem utilizados).

Os problemas da fragmentação externa podem ser resolvidos reunindo os espaços livres adjacentes ou realocando todas as partições eliminando espaços livres entre elas, criando uma única área livre contígua.

A escolha da partição ideal

Existem 4 técnicas para realizar esta escolha

1 – First-fit: seleciona a primeira lacuna que encontrar com tamanho suficiente;

2 – Best-fit: seleciona a lacuna que resultar menor sobra de memória livre;

3 – Worst-fit: seleciona a lacuna que resultar a maior sobra;

4 – Circular-fit: semelhante ao Frst-fit, inicia a procura a partir da ultima sobra.

Swpping

Existem algumas situações onde não é possível manter todos os processos na memória.

  • Um processo já alocado na memória faz uma chamada de sistema pedindo mais memória e não existe memória livre contígua a área onde o mesmo está alocado.

  • Um usuário dispara um programa, não existe memória disponível mas é política do sistema atender os pedidos do usuário

Usando a técnica de swapping o sistema operacional escolhe um programa residente que é levado da memória para o disco (swap-out) e retornando posteriormente para a memória(swap-in)

Problemas na utilização do Swapping

  • Grande custo em termos de tempo de execução;

  • Mais aceitável para sistemas batch ou com pouco número de usuários;

  • Pode ser usado tanto em partições fixas como variáveis

  • No momento do swap-in é preciso corrigir os endereços de memória do processo

Paginação

A paginação permite que o programa possa ser espalhado por áreas não contíguas de memória

Características:

  • O espaço de endereçamento lógico de um processo é dividido em páginas lógicas de tamanho fixo;

  • A memória física é dividida em páginas com tamanho fixo, com tamanho igual ao da página lógica;

  • O programa é carregado página a página, cada página lógica ocupa uma página física;

  • As páginas físicas não são necessariamente contíguas;

  • O endereço lógico é inicialmente dividido em duas partes: um número de página lógica e um deslocamento dentro da página;

  • O número de página lógica é usado com índice no acesso a tabela de páginas, de forma a obter o número da página física correspondente;

  • Não existe fragmentação externa;

  • Existe fragmentação interna (se um programa de 500Kb é carregado na memória e as páginas são de tamanho 7Kb, ele será alocado em 71 páginas sobrando 3Kb de fragmentação);

  • Além da localização a tabela de páginas armazena o bit de validade, (1) se a página está na memória e (0) se não está na memória;

  • A transferência das páginas do processo podem ser feitas por demanda, levando apenas o que é necessário para a execução do programa. Ou por paginação antecipada onde o sistema tenta prever as páginas que serão necessárias à execução do programa.

O maior problema do gerenciamento de memória não é decidir que página carregar, mas sim, qual página deve ser removida da memória

Antes de remover uma página o sistema verifica se a mesma foi alterada (bit de modificação), a página é removida e salva na memória secundária. Quando ela for referenciada novamente o sistema a carrega devolta.

Estratégias para realocação de páginas:

1 – Aleatória: não utiliza nenhum critério de seleção, todas as páginas possuem a mesma chance;

2 – FIFO: a página que entrar primeiro vai ser a primeira a sair;

3 – LRU: seleciona a página que está a mais tempo sem ser referenciada;

4 – LFU: seleciona a página menos freqüentemente usada.

Tamanho da página

O problema da fragmentação também é encontrado na paginação, mas ocorre apenas na ultima página usada pelo programa. A fragmentação é conseqüência do tamanho da página, páginas pequenas diminuem a fragmentação mas aumentam o acesso a memória secundária.

Segmentação

Técnica de gerenciamento de memória onde o programa é dividido em segmentos de tamanhos variados, cada um com o seu próprio espaço de endereçamento.

  • A principal diferença entre paginação e segmentação é a alocação de maneira não fixa, o tamanho depende da lógica do programa;

  • O mapeamento é feito através de tabelas de mapeamento de segmentos;

  • Os endereços são compostos por um número de segmento e o deslocamento dentro do segmento. Cada entrada da tabela mantém o endereço físico do segmento, o tamanho do segmento, se ele está ou não na memória.

  • O sistema operacional mantém uma tabela com as áreas livres e ocupadas da memória;

  • Somente segmentos referenciados são transferidos para a memória principal;

  • Ocorre fragmentação externa.

Segmentação por paginação

Cada segmento é dividido fisicamente em páginas, o endereço é formado pelo número do segmento, número da página dentro desse segmento e o deslocamento dessa página

Memória virtual

É a técnica de gerenciamento que combina a memória principal e a secundária dando ao usuário uma idéia de que existe mais memória principal.

  • Desvincula o endereçamento feito pelo programa dos endereços físicos da memória principal;

  • Um programa residente na memória virtual faz referências a endereços virtuais;

  • O endereço virtual é traduzido para o endereço físico através de mapeamento;

  • Os programas podem ser muito maiores que a sua memória física, apenas uma parte do programa está residente na memória em um determinado instante, o restante do programa fica na memória secundária até ser referenciado.

Sistema de arquivos

Um arquivo é constituído de informações logicamente relacionadas, podendo representar programas ou dados.

Um arquivo pode ser entendido como um conjunto de registros definidos pelo sistema de arquivos;

Cada arquivo contém: nome, tipo, tamanho, data e hora do ultimo acesso, data e hora da ultima modificação, identificação do usuário que criou o arquivo, lista de usuários que podem acessar o arquivo.

Organização de arquivos

Consiste no modo em que os arquivos são armazenados internamente.

  • A estrutura dos dados varia conforme o tipo de informação contida no arquivo;

  • A estrutura de arquivos é definida no momento da criação;

  • Sistemas operacionais estabelecem diferentes organizações de arquivo

Tipos de organização

  1. seqüência não estruturada de bytes, o sistema não impõe nenhuma estrutura lógica para os dados;

  2. alguns sistemas operacionais estabelecem diferentes organizações de arquivos onde cada um é visto como um conjunto de registros;

    • seqüencial

    • relativa

    • indexada

Métodos de acesso

A forma de como o conteúdo de um arquivo é acessada

  • Seqüencial – lê os registros na ordem que são gravados;

  • Acesso direto – permite a leitura e gravação de um registro diretamente na sua posição

    • o método é realizado através do número do registro, que é a posição relativa ao início do arquivo;

    • não existe restrições na ordem que os arquivos são lidos ou gravados;

    • só é possível em arquivos de tamanho de registro fixo.

      • O acesso direto pode ser combinado com o acesso seqüencial (acessa diretamente um registro, e a partir deste acessa os demais de forma seqüencial);

      • Acesso indexado – o arquivo possui uma área de índice onde existem ponteiros para os diversos registros. Sempre que uma aplicação desejar acessar o registro, deve especificar qual chave que vai acessar na área de índices dos ponteiros correspondentes;

Diretórios:

É a maneira pela qual o sistema operacional organiza logicamente os diversos arquivos contidos no disco

  • Um diretório é uma estrutura de dados que contém entradas associadas aos arquivos onde estão armazenadas informações como localização física, organização e demais atributos

  • O sistema operacional mantém uma tabela mantendo os descritores de todos os arquivos abertos

  • Enquanto o arquivo é acessado o descritor de arquivo é constantemente necessário, ao termino do acesso o arquivo deve ser fechado liberando espaço da tabela

Alocação de espaço em disco

O sistema operacional mantém um controle de quais áreas ou blocos do disco estão livres.

Uma lista ou tabela identifica os blocos que podem ser alocados, quando um arquivo é removido seus blocos são liberados para a estrutura de espaços livres.

Implementação da alocação de espaço livre

Mapa de bits: Cada entrada da tabela está associada a um bloco do disco representado por um bit (0=livre 1=alocado).

Bloco Físico

0

1

2

3

4

5

6

7

8

Mapa de bits: 0|1|0|1|0|1|0|1|0

Lista encadeada de blocos livres: cada bloco possui uma área de armazenamento do próximo bloco livre. A partir do primeiro bloco livre pode-se ter acesso aos demais de modo seqüencial na lista.

Blocos livres contíguos: O disco pode ser visto como um conjunto de segmentos de blocos livres. É possível manter uma tabela com o endereço do primeiro bloco de cada segmento e o número de blocos livres contíguos que se seguem.

Técnicas de ocupação de espaço

Alocação contígua: Armazena o arquivo em blocos seqüencialmente dispostos no disco.

O sistema localiza um arquivo através do endereço do primeiro bloco e sua extensão em blocos isto exige que exista uma cadeia de n blocos dispostos seqüencialmente no disco.

Estratégias para a alocação (quando existir mais de um segmento livre)

  • First-fir – seleciona o primeiro segmento livre

  • Best-fit – seleciona o menor segmento disponível

  • Worst-fit – seleciona o maior segmento disponível

Problemas: Apresenta o problema de fragmentação (o disco pode ter espaço livre suficiente mas os segmentos não estão contíguos). Este problema pode ser corrigido com a desfragmentação do disco.

Nem sempre é possível determinar, na sua criação, o tamanho definitivo do arquivo sendo assim ocorre uma ociosidade de espaço livre.

Alocação encadeada: O arquivo pode ser organizado como um conjunto de blocos ligados logicamente no disco. Cada bloco deve possuir um ponteiro indicando o bloco seguinte não necessitando que os blocos estejam dispostos seqüencialmente.

Não ocorre a fragmentação de espaços livres, mas ocorre a fragmentação de arquivos.

Problemas: só permite o acesso seqüencial aos blocos do arquivo, desperdiça espaço com os ponteiros.

Alocação indexada: Utiliza a estratégia de manter uma tabela(bloco de índices) com os ponteiros dos blocos ocupados, possibilitando assim um acesso direto a determinado bloco (não precisando fazer uma busca seqüencial).

Comentários