28768592 Sistemas Operacionais 1 Notas de Aula

Sistemas Operacionais 1 - Resumo

Prof. Ricardo Pinheiro

23/04/2010

Sumário

1 Introdução 41.1 O que é um Sistema Operacional (SO)? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Funções: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Máquina de Níveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Tipos de Sistemas Operacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 Sistemas Monotarefa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3.2 Sistemas Multitarefa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.2.1 Lote ou Batch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.2.2 Tempo Compartilhado (Time-Share) . . . . . . . . . . . . . . . . . . . . . 61.3.2.3 Tempo Real (Real-Time) . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.3 Multiplas UCP´s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.3.1 Multiprocessadores, ou sistemas fortemente acoplados . . . . . . . . . . . 71.3.3.2 Multicomputadores, ou sistemas fracamente acoplados. . . . . . . . . . . . 8

2 Concorrência 92.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Interrupções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Exceções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Controladoras de E/S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1 No início... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.2 E/S Controlada por Programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.3 Polling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.4 E/S Controlada por Interrupção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.5 DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.5.1 Canal DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.5 Buffering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.6 Spooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.7 Reentrância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.8 Proteção do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Estrutura do sistema operacional 143.1 Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Bibliotecas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2.1 Chamadas do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 Utilitários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.4 Modos de acesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1

SUMÁRIO 2

3.5 Tipos de kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.5.1 Monolítico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.5.2 Camadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.5.3 Máquina Virtual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.5.4 Microkernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Processos e threads 194.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.2 Partes do processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.3 Bloco de controle do processo (PCB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.4 Estados do processo e mudanças de estado . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.4.1 Mudanças de estado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.5 Criação e eliminação de processos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.6 Concorrência dentro de uma aplicação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.7 Tipos de processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.8 Sinais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.9 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.9.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.9.2 Ambientes monothread e multithread . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.9.2.1 Monothread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.9.2.2 Multithread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.9.3 Formas de implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.9.3.1 Threads em Modo Usuário (TMU) . . . . . . . . . . . . . . . . . . . . . . 234.9.3.2 Threads em Modo Kernel (TMK) . . . . . . . . . . . . . . . . . . . . . . . 234.9.3.3 Threads em Modo Híbrido (TMH) . . . . . . . . . . . . . . . . . . . . . . 244.9.3.4 Scheduler activations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5 Sincronização entre processos 255.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 Concorrência no código fonte: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5.2.1 Comandos FORK e JOIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2.1.1 Como funciona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5.2.2 ParBegin e ParEnd (CoBegin e CoEnd) . . . . . . . . . . . . . . . . . . . . . . . . . 265.2.2.1 Como funciona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5.3 Exemplos de problemas de sincronização . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.3.1 Sistema de conta corrente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.3.2 2 processos e 1 variável . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.4 Exclusão Mútua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.4.1 Condição de disputa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.4.2 Região Crítica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.4.3 Exclusão Mútua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.4.4 Situações indesejáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.5 Sincronização condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.6 Soluções para a exclusão mútua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.6.1 Soluções por hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.6.1.1 Desligar as interrupções . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.6.1.2 Instruções test-and-set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

SUMÁRIO 3

5.6.2 Soluções por software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.6.2.1 Algoritmo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.6.2.2 Algoritmo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.6.2.3 Algoritmo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.6.2.4 Algoritmo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.6.2.5 Algoritmo de Dekker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.6.2.6 Algoritmo de Peterson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.7 Semáforos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.7.1 Exclusão mútua com semáforos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.7.2 Sincronização condicional com semáforos . . . . . . . . . . . . . . . . . . . . . . . . 395.7.3 Jantar dos filósofos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.8 Monitores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.9 Troca de mensagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.10 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.10.1 Prevenção de deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.10.2 Detecção de deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.10.3 Correção de deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6 Gerência da UCP 446.1 Escalonamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

6.1.1 Funções básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.1.2 Partes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.1.3 Critérios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.1.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.2 Tipos de Escalonamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.2.1 Não-preemptivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.2.1.1 FIFO (First In First Out) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.2.1.2 SJF (Shortest Job First) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.2.1.3 Cooperativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

6.2.2 Preemptivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.2.2.1 Circular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.2.2.2 Prioridades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.2.2.3 Circular com Prioridades . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.2.2.4 Múltiplas filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.2.2.5 Múltiplas filas com realimentação . . . . . . . . . . . . . . . . . . . . . . 49

6.3 Politicas de Escalonamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.3.1 Tempo Compartilhado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.3.2 Tempo Real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Capítulo 1

Introdução

1.1 O que é um Sistema Operacional (SO)?• Programa.

• Conjunto de rotinas.

• Executado de forma não-seqüencial.

1.1.1 Funções:1. Interação homem-máquina.

2. Gerência de recursos.

3. Administração de usuários da máquina (usuários = programas, pessoas).

1.1.2 Objetivos1. Compartilhar os recursos de forma organizada e protegida.

2. Facilitar o acesso aos recursos.

OBS: Recursos→ UCP, memória, HD ....

1.2 Máquina de Níveis• Computador→ hardware e software como uma coisa só para o usuário.

• 6 níveis:

1. São independentes entre si.

2. A passagem por cada uma é obrigatória.

3. Há uma interface entre as camadas.

4

CAPÍTULO 1. INTRODUÇÃO 5

São eles:Aplicações

Linguagem de MontagemSistema Operacional

Linguagem de máquinaMicroprogramação

Hardware (Lógica Digital)

1.3 Tipos de Sistemas OperacionaisTipos de SO Subtipos

Monotarefa ou Monoprogramável –Multitarefa ou Multiprogramável Batch, ou em lote; Tempo Compartilhado; Tempo Real

Múltiplas UCPs Sistemas fortemente e fracamente acoplados

• Diferem quanto à:

1. Aplicação

2. Hardware empregado

3. Estrutura interna – complexidade

• Desejável:

1. Escalável

2. Rápido

3. Flexível

4. Seguro

5. Tolerante a Falhas

6. Robusto

1.3.1 Sistemas Monotarefa• Um único programa em execução.

• Todos os recursos dedicados a esse programa - desperdício

• Estrutura simples

Ex: MS-DOS, PALM OS


1.3.2 Sistemas Multitarefa• Vários programas em execução.

• Compartilhamento e gerência dos recursos.

• Melhor aproveitamento.

• Estrutura complexa.

• Alguns são multiusuário.

1.3.2.1 Lote ou Batch

• 1º SO multitarefa

• fila de submissão de tarefas

• tarefas não interativas

• Saída em impressora ou disco

• Podem ser eficientes, como também podem ter tempos de resposta longos

• Não são mais usados

1.3.2.2 Tempo Compartilhado (Time-Share)

• Tipo mais comum.

• Conceito de fatia de tempo

• Cada tarefa fica em execução até o tempo acabar, dando lugar a outra

• Tarefas interativas

Ex: UNIX, WINDOWS

1.3.2.3 Tempo Real (Real-Time)

• Semelhante ao sistema time-share, mas não são iguais.

• Tempo de resposta→ dentro de intervalos rígidos.

• Conceito de prioridade→tarefa em execução enquanto não houver outro de mais prioridade do que ele

• Prioridade definida pela aplicação.

• Uso em sistemas de missão critica e controle de processos: refinarias, siderúrgicas, trafego aéreo.


1.3.3 Multiplas UCP´s• Processamento paralelo

• Conceitos:

1. escalabilidade

2. disponibilidade

3. balanceamento de carga

• tendência atual

• Problemas:

1. Necessidade de desempenho

2. Problemas mais caros computacionalmente.

3. ”Lei” de Moore – limite físico.

• Solução:

1. uso de arquiteturas com mais de uma UCP

2. software que tire proveito e escalone entre as UCP´s presentes

• Caracteristicas desejáveis:

1. escalabilidade – alta

2. disponibilidade – alta

3. balanceamento de carga – justo

4. transparência

5. imagem única do sistema

1.3.3.1 Multiprocessadores, ou sistemas fortemente acoplados

• Memória única.

• Tudo gerênciado por um único SO.

• Subdividido em

SMP - Arquitetura simétrica.

NUMA - Acesso Não-Uniforme a Memória.

• Custo de produção mais elevado.


1.3.3.2 Multicomputadores, ou sistemas fracamente acoplados.

• Memória “espalhada”

• Um único SO ou vários

• Cada membro do sistema esta conectado aos outros por um link de dados

• Custo de produção mais baixo.

• Tendência atual

Capítulo 2

Concorrência

2.1 Introdução• Computador - seu uso é caro computacionalmente

• Objetivo: minimizar o desperdício (tempo que a UCP fica parada)

• Momentos de desperdício:

– Frequência da UCP é maior do que a frequência da memória

– Velocidade da UCP é muito maior do que a velocidade de E/S.

– Baixo uso da UCP em si.

• Solução: Manter a UCP o mais ocupada possível, executando instruções de forma concorrente.

Exemplo: Programa pega 100 registros, ordena e grava o resultado:

Operação Uso TempoLer 100 registros: E/S 0,04 s

Ordenar: UCP 0,01 sGravar o resultado: E/S 0,05 s

Total: 0,10 s.Total de uso da UCP: 0,01

0,10 s = 0,1 = 10%.

Concorrência - conjunto de técnicas que permite a UCP passar mais tempo ocupada – desempenhando maistarefas por instante de tempo (throughput).

Abaixo, algumas técnicas de concorrência.

2.2 Interrupções• Durante a execução, eventos inesperados podem ocorrer→Desvio forçado na execução - interrupção.

Características:

• Evento assíncrono.

9

CAPÍTULO 2. CONCORRÊNCIA 10

• Evento é externo ao programa.

• Evento gerado por software ou hardware.

• A interrupção é o fundamento básico de concorrência, usado para a sincronização das rotinas do S. O.,programas, etc.

• Arquitetura IBM-PC: 16 interrupções de hardware, divididas entre 2 controladoras de interrupção (inter-ligadas em cascata):

Exemplo: IRQ1 - relógio (timer); IRQ3 - porta serial 1; IRQ7 - porta paralela; IRQ13 - IDE 1; etc.

• Há a necessidade de termos mecanismos apropriados para cada tipo de interrupção.

• Como são tratadas:

– Rotina de tratamento de interrupção

– Vetor de interrupção

• Como são assíncronos, podem ocorrer várias vezes, o que atrapalha a execução do programa. Por isso,temos 2 tipos de interrupções:

– Mascaráveis – podem ser ignoradas.

– Não-mascaráveis – não podem ser ignoradas.

• Controlador de pedidos de interrupção - Hardware que gerencia as interrupções.

2.3 Exceções• Parecidos com as interrupções, mas diferem nos quesitos:

– Evento interno ao programa.

– Evento síncrono.

– Tratamento é todo via software.

Exemplo: Divisão por zero, buffer overflow, stack overflow, etc.

• Tratamento feito pelo desenvolvedor, ou pelo hardware (em alguns casos).

• Segurança:

– Falhas em programas geram exceções.

– Programação segura.


2.4 Controladoras de E/S

2.4.1 No início...• UCP fala diretamente com os dispositivos de E/S.

• Problema: E/S é muito mais lento do que a memória ou a UCP.

• Introdução do controlador (ou controladora) de E/S:

– Gerência do acesso aos dispositivos de E/S.

– Tira da UCP o trabalho de cuidar dos dispositivos.

– Mais eficiente do que a UCP fazer o controle.

• Problema ainda existe→a transferência de dados entre a memória e dispositivo de E/S é feita pela UCP.

• ”Interferência” da UCP.

• Abaixo, algumas técnicas empregadas.

2.4.2 E/S Controlada por Programa• UCP envia a requisição e move os dados entre a memória e a controladora, aguardando o término da

operação.

• UCP fica “presa”, aguardando o término da operação - nada eficiente.

2.4.3 Polling• UCP envia a requisição, move os dados e é liberada.

• De tempos em tempos, testa para ver se a operação foi concluída.

2.4.4 E/S Controlada por Interrupção• UCP envia a requisição, move os dados, e é liberada.

• Quando a operação for concluída, a controladora gera uma interrupção, avisando à UCP o término daoperação.

• Muito eficiente, mas ainda requer a interferência direta da UCP, fazendo a transferência de dados.

2.4.5 DMA• Acesso direto a memória

• Controladora fala direto com a memória, sem passar pela UCP - apenas no início e no fim da transferên-cia.

• A UCP repassa à controladora a posição inicial da memória a ser lida/escrita, e é liberada.


2.4.5.1 Canal DMA

• Extensão do conceito.

• Diversas “vias” ligando as controladoras da máquina à memória.

• Na arquitetura PC há 8 canais

• Chance de uso de buffers para aumentar ainda mais o desempenho.

2.5 Buffering• Uso de uma área na memória principal, o buffer.

• Velocidade da UCP é muito maior do que a velocidade de E/S.

• Objetivo: acelerar o acesso aos dispositivos de E/S (leitura e gravação).

• Manter UCP e E/S ocupados na maior parte do tempo.

• Registro como unidade de transferência.

2.6 Spooling• Fila de submissão de tarefas - inicialmente em fitas magnéticas.

• Arquivo de spool - usado inicialmente em SO´s do tipo batch.

• Fila: 1º a entrar , 1º a sair (FIFO).

• Seqüencial - uso de discos com acesso direto – spooling mais eficiente.

• Não-sequencial - arquivo no disco.

• Uso no gerenciamento de impressão hoje em dia.

2.7 Reentrância• Mais comum em sistemas multiusuário.

• Vários usuários usando os mesmos programas.

• Problema: Várias cópias do mesmo programa na memória→desperdício.

• Reentrância: capacidade do código-fonte do programa ser executado e compartilhado entre os usuáriosdo sistema.

• Código executável = código reentrante.

• O código deve ter compilado com essa opção.

• Uso mais eficiente da memória e aumento do desempenho do sistema.


2.8 Proteção do Sistema• Sistemas mais novos - mais complexos.

• Necessidade de aumentar a segurança

• É preciso garantir a confiabilidade e integridade de programas e dados

• Situações em que mecanismos de proteção são necessários:

1. áreas reservadas para cada programa e seus dados - evitar a sobreposição dessas áreas.

2. comunicação entre programas de forma sincronizada.

3. Compartilhamento de arquivos no disco

4. Evitar “monopólios” da UCP.

5. Contornar exceções.

• O sistema operacional deve evitar esses problemas com mecanismos de controle.

Capítulo 3

Estrutura do sistema operacional

Um sistema operacional é composto de três partes:

1. Kernel.

2. Bibliotecas.

3. Utilitários.

3.1 Kernel• núcleo do sistema.

• Parte central do sistema operacional.

• oferecem serviços aos usuários.

• execução não-sequencial.

• Principais funções:

1. gerência de processos e threads.

2. gerência de memória.

3. gerência de UCP.

4. gerência de dispositivos de E/S.

5. tratamento de interrupções.

6. tratamento de exceções.

7. suporte a redes.

8. segurança.

9. contabilidade e auditoria do sistema.

• Tipos de kernel: como ele fala com o hardware e software, sua organização interna varia de projeto paraprojeto.

• Ideal é que seja pequeno, rápido, estável e seguro.

14

CAPÍTULO 3. ESTRUTURA DO SISTEMA OPERACIONAL 15

3.2 Bibliotecas• Conjunto de rotinas usadas por programas.

• Fornecem serviços para os programas.

• Contém as chamadaa ao sistema.

3.2.1 Chamadas do sistema• Partes integrantes das bibliotecas.

• Meio organizado e padronizado para acesso ao kernel.

• Forma como o kernel pode ser acessado.

• Esconde a complexidade do acesso para o programador.

• Programa→System Calls→Kernel→Hardware

• Nomes diferentes para a mesma coisa:

1. Windows: API´s

2. Open VMS: System Services

3. UNIX: System Calls

OBS: No Unix, o que determina se um sistema é “padrão UNIX” ou não é se ele segue a especificação dasSystem Calls, criada pelo comitê POSIX.

3.3 UtilitáriosProgramas que auxiliam o funcionamento do sistema operacional.

Exemplos: Compiladores, compactadores, ferramentas de acesso ao disco, etc.

3.4 Modos de acesso• A UCP tem instruções:

1. privilegiadas - tem acesso a todos os recursos, e mal-usadas, podem comprometer o funcionamentodo sistema, gerando instabilidade.

2. não-privilegiadas - não comprometem a estabilidade do sistema operacional.

• Modos de acesso - o que são:

1. Solução implementada em hardware, pela UCP.

2. Acesso ou não à instruções privilegiadas.

3. Informação de qual modo de acesso está salvo em um registrador de estado – PSW.


4. Hoje em dia, os sistemas são montados de forma que o kernel é o único programa que pode estarsendo executado no modo privilegiado.

• Chaveamento de modos, ou mudança de contexto:

1. Mudança entre os estados do processador, do modo privilegiado para o não-privilegiado, e vice-versa.

2. Custa (pouco) tempo à UCP, mas é desejável que esse tempo seja ainda mais minimizado.

3.5 Tipos de kernelAntes, dividiremos entre modo usuário (não-privilegiado) e modo kernel (privilegiado).

3.5.1 Monolítico• Um grande bloco de código, ou dividido em módulos, todos sendo executados no modo kernel.

• Estrutura mais simples.

• Desenvolvimento mais simples.

• A manutenção pode ser complexa, se não for um projeto bem-feito e bem amarrado.

• Simples na estrutura.

• Rápido.

Ex: MS-DOS, Linux.

3.5.2 Camadas• Níveis sobrepostos.

• Há necessidade de passar por todos os níveis para chegar ao kernel.

• Como as camadas são isoladas, facilita a manutenção e a depuração.

• Desempenho prejudicado pela estrutura - muito burocrático.

Ex: Open VMS, MULTICS, Windows 2000

3.5.3 Máquina Virtual• Sistema computacional composto por níveis, onde o nível mais baixo é o hardware.

• Modelo de máquina virtual - nível intermediário entre o hardware e o sistema operacional - gerência demáquinas virtuais.

• Cada máquina virtual oferece uma cópia virtual do hardware, incluindo os modos de acesso, interrupções,dispositivos de E/S, etc.


• Cada máquina virtual é independente das demais, contendo seu próprio sistema operacional, seus pró-prios usuários e suas próprias aplicações.

• Conceito iniciado no VM/370, baseado no OS/370, da IBM (anos 1960).

• Conceito usado também com a linguagem Java - JVM.

• Vantagens:

1. Segurança - Isolamento total das máquinas virtuais.

2. Economia de recursos - mais barato um servidor grande do que vários servidores pequenos.

3. Portabilidade - se o hardware hospedeiro tiver um defeito, basta transferir os arquivos das máquinasvirtuais para outro hardware.

• Desvantagens:

1. Complexidade.

2. Sobrecarga - um hipervisor é complexo e consome muitos recursos do hardware hospedeiro.

3.5.4 Microkernel• Constatação - sistemas atuais ainda são lentos e pesados.

• Microkernel - tornar o núcleo do sistema operacional o menor e mais simples possível.

• Disponibilizar os serviços através de processos a serem executados no nível usuário.

• Cada um desses processos servidores fornecem um recurso específico para o sistema: Gerência de pro-cessos, gerência de arquivos, escalonamento de processos, etc.

• A principal função do kernel então é fazer o diálogo entre os diferentes processos servidores.

• Conceito surgido nos anos 1980, com o sistema operacional Mach, desenvolvido na Universidade Carnegie-Mellon.

• O núcleo do Mach fornece 4 serviços, apenas: Gerência de processos, gerência de memória, comunicaçãopor troca de mensagens e operações de E/S, todas em modo usuário.

• Vantagens:

1. Mais seguro: Se um serviço sair do ar, é recolocado facilmente.

2. Apropriado para computação distribuída: Os serviços podem ser remanejados entre as UCPs.

3. Mais flexível.

4. Mais rápido: com o kernel enxuto, menos código a ser executado.

5. Mais facilmente portado para outras arquiteturas: Menos código no kernel, menos dificuldades parareescrever o kernel para outras plataformas.


• Há controvérsias quanto à afirmação de ser mais rápido (ponto no. 4), pois apesar do kernel ser menor, osistema fará muito mais chamadas e mudanças de modo de acesso, ao acessar os serviços que rodam nomodo usuário.

• Na prática, os sistemas microkernel são interessantes, mas ainda não podem estar disponíveis comercial-mente. Existem alguns sistemas que agregam características do microkernel, mas não são completamentenesse estado.

Exemplos: L4, Amoeba, Exokernel, Minix.

Capítulo 4

Processos e threads

4.1 Introdução• Conceito - base para a implementação de um sistema multiprogramável.

• Um programa deve estar sempre associado a um processo.

• Processo - ambiente no qual um programa é executado.

• O processo é colocado em execução e é tirado caso o sistema operacional necessite fazê-lo.

4.2 Partes do processo• Três partes:

1. Espaço de endereçamento: Área de memória usada pelo processo, onde as instruções e os dados doprograma são armaenados para execução.

2. Contexto de hardware: Registradores gerais e específicos da UCP. Quando um processo está emexecução, o contexto de hardware guarda os registradores do processador. Quando ele é tirado deexecução (mudança de contexto), todos os registradores são salvos no contexto de hardware, paraque o processo seja novamente colocado em execução, a partir do ponto onde parou.

3. Contexto de software: Características e limites dos recursos que podem ser alocados pelo processo.Muitas dessas características são determinadas no momento da criação do processo, enquanto outraspodem ser alteradas durante a sua existência. São três grupos de informações:

– Identificação:

* Número de identificação do processo (PID).

* Nome do usuário que criou o processo (UID).

* Grupo do usuário que criou o processo (GID).

– Quotas: Limites de cada recurso do sistema que um prcoesso pode alocar. Exemplos:

* Número máximo de arquivos abertos simultaneamente;

* Número máximo de operações de E/S pendentes;

* Tamanho máximo do buffer para operações de E/S;

19

CAPÍTULO 4. PROCESSOS E THREADS 20

* Número máximo de processos, subprocessos e threads que podem ser criados.

– Privilégios: Ações que um processo pode fazer em relação a ele mesmo, aos demais processos e aosistema operacional. Exemplos:

* Alterar a prioridade de execução;

* Limites alocados na memória principal e secundária;

* Alterar as prioridades de outros processos;

* Desativar o sistema;

* Alterar regras de segurança;

* Criar outros processos privilegiados;

* Mudar a configuração do sistema.

4.3 Bloco de controle do processo (PCB)• O bloco de controle do processo é uma estrutura de dados, mantida pelo sistema operacional, em área

reservada, onde todas as informações necessárias para manter o processo em funcionamento são arqui-vadas.

• A gerência de processos é feita por chamadas do sistema.

4.4 Estados do processo e mudanças de estado• Três estados:

1. Execução: Sendo executado pela UCP.

2. Prontidão (ou pronto): Aguarda a sua vez para ser executado.

3. Espera: Aguarda pelo fim de um evento externo ou por um recurso para continuar o processamento.

Escalonamento: Conjunto de critérios que definem qual processo será colocado em execução primeiro.

4.4.1 Mudanças de estado• Eventos voluntários ou involuntários podem mudar o estado de um processo:

1. Eventos voluntários: O processo muda por causa de eventos originários de si mesmo.

2. Eventos involuntários: O processos muda por ação do sistema operacional.

• Mudanças:

1. Pronto→ execução: Colocado em execução.

2. Execução → espera: Evento externo, como uma operação de E/S, faz o processo ter seu estadomudado.

3. Espera→ pronto: O evento externo foi concluído. Note que não há como passar direto, de esperapara execução.


4. Execução→ pronto: O término da fatia de tempo que o processo tem o coloca de volta na fila deprontidão.

• Processos no estado de espera ou pronto podem estar na memória virtual, por falta de espaço. Logo, atécnica de swapping consiste em mover processos entre as memórias principal e virtual.

4.5 Criação e eliminação de processos• Dois estados adicionais:

1. Criação→ Criou-se a entrada no PCB, mas o processo ainda não foi colocado na lista de prontidão.É criado por outros processos.

2. Término→ O programa foi finalizado, mas o PCB ainda existe. É eliminado por outros processosou pelo término nortmal da sua execução.

4.6 Concorrência dentro de uma aplicação• Três maneiras:

1. Processos independentes: Um processo cria outros, sem vínculos. É a maneira mais simples.

2. Subprocessos: Um processo cria outros, de forma que estão vinculados hierarquicamente: Se oprocesso-pai é eliminado, os processos-filho também serão. Compartilham quotas.

3. Threads: Ramificações dentro do processo, compartilhando o contexto de software e o espaço deendereçamento. É um modo de gastar menos tempo com criação, escalonamento e eliminação deprocessos.

4.7 Tipos de processo1. Foreground: Execução em primeiro plano, interage diretamente com o usuário, com entrada-padrão

(teclado) e saída-padrão (monitor).

2. Background: Execução em segundo plano, onde não é preciso interagir diretamente com o usuário. Nessecaso, entrada e saída podem ser arquivos, por exemplo.

3. CPU-Bound: Passa a maior parte da fatia de tempo em estado de execução, ou seja, usando a UCPintensamente.

4. I/O-Bound: Passa a maior parte da fatia de tempo em estado de espera, com muitas operações de E/S.

4.8 Sinais• Mecanismo que permite ”avisar” processos de eventos gerados pelo sistema operacional ou por outros

processos.

• Também são usados para comunicação e sincronização entre processos.


• Podem ser associados a temporizadores (eventos associados ao tempo).

Exemplos: Notificação de interrupções e exceções, alarmes de tempo, limites de quotas excedidos, etc.

• Eventos que geram sinais - síncronos ou assíncronos.

• Tratamento do sinal - semelhante ao mecanismo de interupções.

• O sinal está para o processo assim como interrupções e exceções estão para o sistema operacional.

4.9 Threads

4.9.1 Introdução• No início, eram apenas processos.

• Conceito de processo ”leve” (lightweight)→ compartilha o espaço de endereçamento.

• Thread - surge primeiro no sistema operacional Mach, da Universidade de Carnegie-Mellon (1980).

• Ganho de desempenho e flexibilidade, apesar da complexa implementação.

• Aplicações mais complexas - vários trechos de código em execução paralela - para termos comunicaçãoe sincronização de threads deve-se avaliar desempenho, flexibilidade e custo.

• Apesar da dificuldade em desenvolver, compensa devido aos ganhos obtidos.

Exemplos: Windows 2000 e superiores, Linux, Solaris, etc.

4.9.2 Ambientes monothread e multithread4.9.2.1 Monothread

• Cada processo tem apenas um thread.

• Concorrência se dá apenas com processos independentes ou subprocessos.

• Problema - criar, gerenciar e eliminar processos é computacionalmente caro.

• Compartilhar o espaço de endereçamento é complexo, por conta dos mecanismos empregados.

• Processo→Unidade de alocação e de escalonamento.


4.9.2.2 Multithread

• Permite que tenhamos aplicações concorrentes de forma mais eficiente:

– Aumenta o desempenho, por dispensar mecanismos de comunicação dentrod o processo.

– Aumenta a eficiência, por termos menos sobrecarga do sistema como um tyodo - menos processose mais threads.

• Programas associados a threads.

• Os threads sofrem mudança de estado (pronto, espera e execução), e tem seu próprio bloco de controle(o TCB).

• Processo→Unidade de alocação.

• Thread→Unidade de escalonamento.

• O S. O. vê e escalona os threads de cada processo.

4.9.3 Formas de implementação• Pacote de threads - Conjunto de rotinas da biblioteca do sistema operacional par aa implementação de

threads.

• Falta de padrão em sistemas Unix, até o comitê POSIX liberar uma norma para termos threads, os PTh-reads.

4.9.3.1 Threads em Modo Usuário (TMU)

• Implementados pela aplicação.

• O sistema operacional não vê os threads, apenas o proceso como um todo.

• Podemos ter aplicações multithread em ambientes monothread.

• São rápidos e eficientes, por não fazerem acessos ao kernel, e as mudanças de modo de acesso da UCP(usuário-kernel-usuário).

• Uma chamada a um dispositivo de E/S, feita por um thread, coloca todo o processo em estado de espera.

• O tratamento dos sinais também é complexo, pois o processo terá que tratar o sinal e direcioná-lo aothread certo.

4.9.3.2 Threads em Modo Kernel (TMK)

• Implementados pelo kernel.

• O sistema operacional gerencia diretamente os threads de um processo.

• Requer mudanças de modo de acesso, logo tem desempenho degradado - bem mais lentos.

• Chamadas bloqueantes colocam apenas o thread em estado de espera, não todo o processo.

• Podemos ter vários threads de um mesmo processo em execução simultânea, em UCPs diferentes.


4.9.3.3 Threads em Modo Híbrido (TMH)

• Combina as vantagens dos threads em modo usuário (TMU) e em modo kernel (TMK), mas também asdesvantagens.

• Um processo tem vários TMKs, e cada TMK tem vários TMUs.

• O sistema operacional escalona os TMKs, e eles escalonam os TMUs.

• O objetivo é aumentar a flexibilidade, já que apenas os TMKs são escalonados (diminuindo o número demudanças de modo de acesso), mas também traz os problemas das chamadas bloqueantes, entre outras.

4.9.3.4 Scheduler activations

• Os Threads em Modo Híbrido (TMH) tem problemas devido à falta de comunicação entre os threads.

• É desejável unir o melhor das implementações, fugindo dos problemas de cada uma.

• O scheduler activations foi implementado inicialmente na Universidade de Washington, e nessa forma,há uma estrutura de dados que facilita a troca de informações entre o kernel e a biblioteca de threads.Essa estrutura é o scheduler activations.

• O escalonamento é feito pela própria biblioteca, evitando as mudanças de modo de acesso, como porexemplo a ocorrência de uma chamada bloqueante.

• Ambas as partes se comunicam, e trabalham cooperativamente.

Capítulo 5

Sincronização entre processos

5.1 Introdução• Anos 1960: sistemas operacionais multitarefa →surgem as primeiras aplicações que podem funcionar

de maneira concorrente, ou seja: diferentes partes do código do programa podem funcionar simultanea-mente.

– Uso de subprocessos ou threads.

– Escalonamento organizado pelo SO.

– Objetivo: Aumentar o desempenho.

• Esses processos que compõem a aplicação concorrente precisam compartilhar recursos:

Exemplos: Arquivos, registros, dispositivos de E/S, regiões de memória.

• Podem ocorrer situações indesejáveis, que podem até comprometer a execução da aplicação.

• Importante garantir a integridade e a confiabilidade.

• Necessidade das execuções serem sincronizadas, a partir de mecanismos fornecidos pelo sistema opera-cional, para garantir o processamento correto

• A comunicação entre processos pode ser estabelecida usando mecanismos. É necessário que os proces-sos estejam com sua execução sincronizada

Exemplos: (mecanismos de comunicação) Variáveis compartilhadas da memória principal ou trocas demensagens.

5.2 Concorrência no código fonte:

5.2.1 Comandos FORK e JOIN5.2.1.1 Como funciona

• FORK cria um subprocesso B a partir do processo A.

25

CAPÍTULO 5. SINCRONIZAÇÃO ENTRE PROCESSOS 26

Figura 5.1: Sincronização entre processos.

• Eles são concorrentes.

• JOIN sincroniza A com B→ A p´ara e espera o fim da execução de B.

5.2.2 ParBegin e ParEnd (CoBegin e CoEnd)5.2.2.1 Como funciona

• Implementado de formas diferentes em várias linguagens de programação.

• Ao invés de usar BEGIN e END como delimitadores de bloco, usa-se PARBEGIN e PAREND.

– Todos os comandos que estiverem no bloco serão executados de forma concorrente.

* PARBEGIN: Ramifica o código, criando 1 processo para cada comando.

* PAREND: Cria um ponto de sincronização, reunindo todos os processos e seus resultados numprocesso principal.

5.3 Exemplos de problemas de sincronização

5.3.1 Sistema de conta corrente• Atualização do saldo, realizando entradas e saídas.

• 2 processos fazem lançamentos na concta corrente de um cliente.

– Um faz débitos, e outro realiza créditos:

• Suponhamos então, 2 processos (Caixa 1 e Caixa 2) realizando operações na conta desse cliente.


Figura 5.2: PARBEGIN e PAREND.

Algorithm 5.1 Programa de Conta Corrente.Programa Conta Corrente;..Leia (arquivo de contas, registro do cliente);Leia (valor a ser depositado ou retirado);Registro do cliente.Saldo←Registro do cliente.Saldo + valor a ser depositado ou retirado;Grava (arquivo de contas, registro do cliente);...

Caixa Comando Saldo no arquivo Valor Saldo na memória1 Leia (arquivo de contas, ...) 1000 - 10001 Leia (valor a ser depositado ou retirado) 1000 -200 10001 Registro do cliente.Saldo 1000 -200 8002 Leia (arquivo de contas, ...) 1000 - 10002 Leia (valor a ser depositado ou retirado) 1000 +300 10002 Registro do cliente.Saldo 1000 +300 13001 Grava (arquivo de contas, ...) 1000 -200 8002 Grava (arquivo de contas, ...) 1000 +300 1300Logo, temos uma incoerência, já que um caixa quer salvar o valor de 1300, e o outro quer salvar o valor de

800. Qual deles está certo?


5.3.2 2 processos e 1 variável• Processo A: Incrementa uma variável.

• Processo B: Decrementa uma variável.

Algorithm 5.2 Exemplos de código.Processo A:

• Coloca X em Ra.

• Soma 1 a Ra.

• Salva Ra em X.

Processo B:

• Coloca X em Rb.

• Subtrai 1 a Rb.

• Salva Rb em X.

Processo Comando X Ra RbA Carrega 2 2 -A Soma 2 3 -B Carrega 2 - 2B Subtrai 2 - 1A Salva 3 3 -B Salva 3 - 1

Mais uma incoerência, pois X não poderá ter 2 valores, 3 e 1.

5.4 Exclusão Mútua

5.4.1 Condição de disputa• O problema de inconsistência nos dados, devido à falta de sincronização.

5.4.2 Região Crítica• A parte do código-fonte onde é feito o acesso aos recursos compartilhados.

• Objetivo: Obter a exclusão mútua.

• Logo, só um programa pode acessar a sua região crítica por vez.


5.4.3 Exclusão Mútua• A solução mais simples para evitar os problemas de compartilhamento é impedir que 2 ou mais processos

acessem um mesmo recurso simultaneamente.

• Enquanto um processo estiver acessando determinado recurso, todos os demais processos que queiramacessá-lo deverão esperar pelo término da utilização do recurso.

• Acesso de forma ordenada, organizada e individual ao recurso.

• Exclusividade de acesso.

Exemplo: No problema do banco (subseção 5.3.1), basta garantir que o acesso à conta (a região crítica docódigo) seja exclusivo: um espera equanto o outro acessa.

5.4.4 Situações indesejáveis1. Starvation

• Também conhecida como espera indefinida.

• Um dos processos nunca sai da sua região crítica, e o outro "passa fome".

• Pode ocorrer em escalonamentos onde a escolha é aleatória ou com base em prioridades.

• Uma solução é usar filas de pedidos de alocação para cada recurso, e cada uma dessas filas usandoo escalonamento em fila (FIFO).

2. Espera ocupada;

• Toda vez que um processo não consegue entrar na sua região crítica, ele permanece repetidamentetestando uma condição, tentando acessar o recurso.

• Isso continua até o processo ”persistente” conseguir o acesso.

• Problema: Isso consome tempo do processador de forma desnecessária.

3. Um processo sai da região crítica e não deixa que outros entrem.

• Recurso livre, mas ainda ligado a um processo.

5.5 Sincronização condicional• Situação onde o acesso ao recurso compartilhado exige a sincronização de processos vinculada a uma

condição de acesso.

• Essa condição é bloqueante para os processos.

Exemplo: Modelo produtor-consumidor:

• O recurso compartilhado é um buffer de espaço limitado.

• Dois ou mais processos acessam o recurso:


– Produtores - gravam no buffer

– Consumidores - leem o buffer

• Condições:

– Buffer vazio - consumidor espera

– Buffer cheio - produtor espera

Algorithm 5.3 Modelo produtor-consumidor.Programa PA1;Constante

Tamanho do buffer = X;Variáveis

Buffer: vetor de dado (1 a X);D1, D2: dado;Conta: 0..X;

Procedimento Produtor;Início

RepitaProduz Dado (D1);Enquanto conta for igual a X não faça nada;Grava o buffer (Buffer, D1);Incrementa Conta;

Até que seja falso;Fim;Procedimento Consumidor;Procedimento Produtor;Início

RepitaEnquanto conta for igual a 0 não faça nada;Lê o buffer (Buffer, D2);Consome Dado (D2);Decrementa Conta;

Até que seja falso;Fim;Início

Conta←0;Início (em paralelo)

Produtor;Consumidor;

Fim (em paralelo);Fim.

Nesse caso, teremos a espera ocupada.


5.6 Soluções para a exclusão mútua

5.6.1 Soluções por hardware5.6.1.1 Desligar as interrupções

Algorithm 5.4 Desligamento das interrupções do sistema.Início...

Desliga as interrupções do sistema;Entra na Região Crítica;Sai da Região Crítica;Liga as interrupções do sistema;

.

.

.Fim;

• Dessa forma nenhum outro programa interrompe o primeiro.

• Maneira simples.

• Atrapalha a multiprogramação.

• Se o programa não religar as interrupções, trava tudo.

– Clock usa interrupções.

• Múltiplas UCPs - Essa informação (de desligamento e religamento) deve propagar para todas as UCPs.

• Usado às vezes com partes do kernel.

5.6.1.2 Instruções test-and-set

• Instrução especial da UCP.

– Lê a variavel.

– Salva seu conteódo em outra área da memória.

– Grava um novo valor na mesma variável.

• Dessa forma, 1 variável compartilhada pode ser manipulada por 2 processos simultaneamente.

• Uso:

– Usa-se uma variavel booleana.


* Falso = Qualquer processo pode acessar

* Verdadeiro = Processo acessando o recurso.

• Manuseio simples

• Funciona bem com múltiplas UCP .

• Depende dessa instrução existir na UCP.

• Possibilidade de starvation.

5.6.2 Soluções por software• Diversos algoritimos foram pensados ao longo do tempo.

• Uso de uma variável de bloqueio.

– Testa se a região crítica está liberada ao ler essa variável.

5.6.2.1 Algoritmo 1

Algorithm 5.5 Algoritmo 1 para exclusão mútua.Programa Algoritmo 1;Variável

Vez: caracter;Procedimento A;Início

RepitaEnquanto Vez for igual a B não faça nada;Entre na Região Crítica do procedimento A;

Vez←B;Realize o processamento do procedimento A;

Até que seja falso;Fim;Procedimento B;Início

RepitaEnquanto Vez for igual a A não faça nada;Entre na Região Crítica do procedimento B;

Vez←A;Realize o processamento do procedimento B;

Até que seja falso;Fim;Início (em paralelo)

Procedimento A;Procedimento B;

Fim (em paralelo).


• Só funciona com dois processos.

• Acesso alternado.

• Se não alterar a variável de bloqueio, o recurso fica sempre inacessível, que gera starvation.

5.6.2.2 Algoritmo 2

Algorithm 5.6 Algoritmo 2 para exclusão mútua.Programa Algoritmo 2;Variáveis

CA, CB: Booleano;Procedimento A;Início

RepitaEnquanto CB for Verdadeiro não faça nada;CA←Verdadeiro;Entre na Região Crítica do procedimento A;

CA←Falso;Realize o processamento do procedimento A;


RepitaEnquanto CA for Verdadeiro não faça nada;CB←Verdadeiro;Entre na Região Crítica do procedimento B;

CB←Falso;Realize o processamento do procedimento B;


CA←Falso;CB←Falso;Início (em paralelo)


Fim (em paralelo).Fim.

• Substituição da variável de bloqueio por duas variáveis, uma para cada processo.

• Não há necessidade de acessar alternadamente.

• Se houver um problema, o recurso não fica bloqueado, a não ser que a falha seja dentro da região crítica.


5.6.2.3 Algoritmo 3



RepitaCA←Verdadeiro;Enquanto CB for Verdadeiro não faça nada;Entre na Região Crítica do procedimento A;



RepitaCB←Verdadeiro;Enquanto CA for Verdadeiro não faça nada;Entre na Região Crítica do procedimento B;






• O problema do algoritmo anterior consiste em o processo ter algum problema quando está na sua regiãocrítica, e com isso o acesso ao recurso fica travado.

• Uma maneira de resolver o problema do algoritmo anterior é mudar as variáveis CA e CB antes de testarse o recurso está disponível.

• Só que temos um novo problema: ambos os processos podem ficar bloqueados. Se ambos mudarem osvalores das variáveis CA e CB, ninguém entra na sua região crítica e ninguém usa o recurso.

5.6.2.4 Algoritmo 4

• O processo entra na região crítica sem saber se o outro está acessando o recurso.




RepitaCA←Verdadeiro;Enquanto CB for Verdadeiro não faça nada;Início

CA←Falso;{ pequeno intervalo de tempo }CA←Verdadeiro;

Fim;Entre na Região Crítica do procedimento A;CA←Falso;Realize o processamento do procedimento A;


RepitaCB←Verdadeiro;Enquanto CA for Verdadeiro não faça nada;Início

CB←Falso;{ pequeno intervalo de tempo }CB←Verdadeiro;

Fim;Entre na Região Crítica do procedimento B;CB←Falso;Realize o processamento do procedimento B;





• Uma maneira de evitar o bloqueio de ambos é dando a chance de reverter o processo, e alterar novamenteo valor das variáveis CA e CB.

• Pode acontecer que ambos os processos alterem seu estado (variável que marca a entrada na região


critica) para falso, simultaneamente. Ou seja, teremos bloqueio para ambos.

5.6.2.5 Algoritmo de Dekker

• A primeira solução completa para o problema da exclusão mútua.

• Baseada nos algoritmos 5.5 e 5.8 para obter a exclusão mútua entre 2 processos.

• Lógica bastante complexa.

5.6.2.6 Algoritmo de Peterson

• Solução baseada no algoritmo de Dekker.

• Facilmente generalizado para n processos.

• Parecido com o algoritmo 5.7.

• Como funciona:

– Cada processo tem uma variável de estado que sinaliza o desejo de entrar na região crítica.– Uma variável é usada para arbitrar conflitos: a variável cede o uso para outro processo.

• O algoritmo de Dekker e a versão inicial do algoritmo de Peterson garantem a exclusão mútua de 2processos.

• O algoritmo de Peterson foi estendido para o caso de N processos por Hofri (1990).

• Lamport propôs um algoritmo para garantir a exclusão mútua, que é o algoritmo do padeiro.

• Todos ainda sofrem de espera ocupada (seção 2).

• Uma maneira de resolver é usando semáforos (ou monitores) como mecanismos de sincronização.

5.7 Semáforos• Ideia simples para sincronização.

• Conceito proposto pro Dijkstra em 1965

• Semáforo:

– Variável inteira e não negativa.– São vinculados ao recurso compartilhado.– Só pode ser manipulada por 2 instruções.

1. UP - incremento.2. DOWN - decremento.

• 2 tipos:

– binários, ou mutexes (mutual exclusion semaphores): 2 estados.– contadores: n estados.


Algorithm 5.9 Algoritmo de Peterson para exclusão mútua.Programa Algoritmo Peterson;Variáveis

CA, CB: Booleano;Vez: Caractere;

Procedimento A;Início

RepitaCA←Verdadeiro;Vez← ”B”;Enquanto CB for Verdadeiro e Vez for igual a ”B”, não faça nada;Entre na Região Crítica do procedimento A;



RepitaCB←Verdadeiro;Vez←”A”;Enquanto CA for Verdadeiro e Vez for igual a ”A”, não faça nada;Entre na Região Crítica do procedimento B;






5.7.1 Exclusão mútua com semáforos• Semáforo ligado ao recurso compartilhado:

– Semáforo está com 1, sofre um DOWN, e muda para o estado 0. →o processo entra na regiãocrítica.

– Semáforo está com 0, sofre um DOWN (não temos o estado -1)→o processo é mantido em estadode espera.

– Semáforo está com 0, sofre um UP, e muda para o estado 1→o processo sai da região crítica.


Algorithm 5.10 Código fonte comum para exemplos com semáforos.tipo semaforo = registro

valor = inteirofila de espera {lista de processos em espera}

fim;Procedimento DOWN (s: inteiro);Início

Se s=0 então coloca o processo na fila de espera;s–;

Fim;Procedimento UP (s:inteiro);Início

s++;Se tem processo esperando, então coloca em execução;

Fim;

Algorithm 5.11 Exclusão mútua usando semáforos.Programa Semáforo 1;Variável A: Semáforo←1;Procedimento processo A;Início

RepitaDOWN(s);Entra na região crítica de A;UP(s);

até que seja falso;Fim;Procedimento processo B;Início

RepitaDOWN(s);Entra na região crítica de B;UP(s);até que seja falso;

Fim;Início (em paralelo)

Procedimento A;Procedimento A;

Fim (em paralelo);


5.7.2 Sincronização condicional com semáforos• Podemos usar semáforos para lidar com a sincronização condicional.

– Quando um processo solicita uma operação de E/S, ele executa um DOWN no semáforo associadoao recurso, e é colocado em estado de espera até que a operação seja completada.

– Quando a operação termina, a rotina de tratamento da interrupção executa um UP no semáforo,liberando o processo do estado de espera.

5.7.3 Jantar dos filósofos• Problema:

– 5 filósofos, que são os processos.

– 5 pratos, que são as regiões críticas.

– 5 garfos, que são os recursos compartilhados.

• Limitações:

1. O filósofo ou pensa (estado de espera), ou come (entra na região crítica).

2. Para comer, o filósofo precisa de 2 garfos.

• Deadlock

– Ocorre se cada um dos filósofos pegar um garfo.

• Algumas soluções

1. O número de filósofos à mesa é menor do que o número de garfos (neste caso, no máximo 4).

2. Um filósofo só pode pegar um garfo se o outro estiver disponível.

3. O filósofo ímpar pega o garfo da direita e depois da esquerda, e o filósofo par pega o grafo daesquerda e depois da direita.

• Ainda temos o risco de um deadlock. Para evitar, podemos acrescentar um novo semáforo contador,para marcar os lugares começando em 4 (menor do que número de talheres), e dessa forma garantir queteremos sempre mais talhetes do que filósofos à mesa. e fazendo down e up tambem. Dessa forma,teremos sempre mais talheres do que filósofos a mesa.


Algorithm 5.12 Algoritmo de sincronização condicional usando semáforos.Programa Semaforo2;Constante

Tamanho do buffer = 2;Tipo

Tipo de dado = {um tipo qualquer};Variáveis

Vazio: semáforo = Tamanho do buffer;Cheio, evento: semáforo = 0;Mutex: semáforo = 1;Buffer = vetor de tipo de dado (1 a Tamanho do buffer);Dado 1, Dado 2: Tipo de dado;

Procedimento Produtor;Início

RepitaProduz Dado (Dado 1);Down (Vazio);Down (Mutex);Grava no buffer (Dado 1, Buffer);Up (Mutex);Up (Cheio);

Até que seja falso;Fim;Procedimento Consumidor;Início

RepitaDown (Cheio);Down (Mutex);Lê o buffer (Dado 2, Buffer);Up (Mutex);Up (Vazio);Consome Dado (Dado 2);

Até que seja falso;Fim;Início (em paralelo)

Produtor;Consumidor;

Fim (em paralelo).

5.8 Monitores• Mecanismos de sincronização semelhantes aos semáforos, mas de alto nível e estruturados.

– Por quê? Os semáforos são não-estruturados, e qualquer engano por parte do programador podelevar a problemas de sincronização.

• Os monitores são hoje em dia estruturas criadas dentro dos programas, que agregam procedimentos e


Algorithm 5.13 Jantar dos filósofos.Programa filósofo 1;Variáveis

Garfos: vetor(1 a 4) de semaforo =1;i: inteiro;

Procedimento filósofo (i:inteiro);Início

repitapensando;down(garfos(i));down(garfos((i+1) mod 5));comendo;up(garfos(i);up(garfos(i+1) mod 5));

até que seja falso;Fim;Início (em paralelo)

Para i←de 1 ate 5 façafilósofo(i)

Fim (em paralelo).

variáveis, e quem garante a exclusão mútua é o compilador: O programa não tem acesso às variáveis queseriam os semáforos, no caso do monitor.

• As variáveis globais, definidas dentro dos monitores, só são visíveis dentro dessas estruturas.

• Os procedimentos criados dentro dos monitores só são acessíveis através dos mesmos.

• O programa verifica com o S. O. se existe outro processo, gerando uma possível condição de disputa. Seexiste, o programa aguarda a sua vez, ficando numa fila de espera. Se não existe, o programa entra nasua região crítica.

• Várias linguagens já tem estruturas implementadas para lidar com monitores, como Modula-2, Modula-3,Concurrent Pascal, etc.

5.9 Troca de mensagens• Mecanismo de comunicação e sincronização entre processos.

• O uso desse mecanismo dispensa o uso de variáveis compartilhadas, mas exige um canal de comunicação,que pode ser um buffer ou um link de dados.

• As execuções entre os rpocessos comunicantes devem estsr sincronizadas, para manter a relação causa-efeito da comunicação (a mensagem deve chegar ao destino com um tempo maior do que saiu).

• Dois tipos:

1. Comunicação direta


– Mensagem endereçada diretamente ao receptor.– Só há a troca de mensagens, apenas.– É preciso declarar claramente quem envia e quem recebe. Se mudar, tem que mudar dentro do

código.

2. Comunicação indireta

– Uso de uma área compartilhada que faz o papel de "caixa de correio" (mailbox, ou port).– Essa área compartilhada pode ser associada a vários processos.– Os procedimentos passam a endereçar a área compartilhada, e não os processos. Logo, caso

mude o processo, não é preciso fazer alterações no código.

5.10 Deadlock• Processo aguarda um recurso que nunca virá, ou um evento que nunca ocorrerá.

• Devido a isso, ele não libera o recurso que está sob seu uso, e outros processos acabam tendo o mesmoproblema, gerando uma reação em cadeia que cria o que chamamos de espera circular:

1. O Processo A retém o recurso 1 e pede o recurso 2, que está com o Processo B.

2. O Processo B retém o recurso 2 e pede o recurso 3, que está com o Processo C.

3. O Processo C retém o recurso 3 e pede o recurso 3, que está com o Processo A.

• Quatro condições para termos um deadlock:

1. Exclusão mútua - O processo está associado a um recurso.

2. Espera por recurso - Processo no aguardo.

3. Não-preempção - Recurso não pode ser liberado para outros processos fazerem uso.

4. Espera circular - Processo aguarda por um recurso que está associado a outro processo, e por aí vai.

5.10.1 Prevenção de deadlocksObjetivo: Garantir que uma das quatro condições acima não aconteça:

1. Se tirarmos a condição 1, gera inconsistências.

2. Se tirarmos a condição 2, quem tem recursos, tem que liberar para poder pegar novos recursos.

(a) Desperdício, na utilização dos recursos.

(b) Não dá para alocar previamente tudo o que o processo vai usar.

3. Se tirarmos a condição 3, então permitiremos que um recurso seja tirado de um processo caso outroprocesso também precise do recurso. Só que isto pode gerar problemas, como por exemplo o processoter a sua execução interrompida. Também poderemos ter starvation.

4. Se tirarmos a condição 4, cada processo só pode alocar um recurso de cada vez, e para alocar um novo,é preciso liberar o primeiro. Isto restringe severamente o compartilhamento de programas.


• Logo, prevenir o deadlock é possível, mas todas as soluções apresentadas não são nada práticas, e con-sequentemente, não são usadas.

• A maneira mais adotada é usar o algoritmo do Banqueiro (Dikjstra, 1965), onde cada processo informaao sistema operacional qual recurso está usando, qual é o estado, entre outras informações. Assim, oalgorimo define qual é o estado de alocação de um recurso, e com base nisso, previne possíveis deadlocks.

5.10.2 Detecção de deadlocksOs sistemas operacionais mantém estruturaa de dados capazes de armazenar informações do sistema, e iden-tificar cada recurso do sistema, quem os está alocando, entre outras infromações. A estrutura é atualizadacom recursos alocados ou liberados, e observando-a, o sistema pode detectar a espera circular que porventuraocorra.

5.10.3 Correção de deadlocks• Depois da detecção, a correção.

• Quebra da espera circular.

– Elimina-se processos para liberar recursos.

– Só que isto pode gerar instabilidades no sistema - Qual processo deve ser eliminado?

• Rollback - Liberar alguns recursos temporariamente, para depois realocá-los aos processos congelados,continuando de onde parou. Na prática é difícil, pois depende do processos a ser congelado, se dá parapará-lo, por exemplo.

Capítulo 6

Gerência da UCP

6.1 Escalonamento• Processo de seleção de um processo a ser executado, e o conjunto de critérios que definem a fila de

execução do sistema operacional.

6.1.1 Funções básicas• Manter a UCP o máximo ocupada.

• Balancear o uso da UCP entre os processos.

• Maximizar o throughput.

• Dar tempos de resposta razoáveis.

6.1.2 Partes• escalonador (scheduler) – decide.

• dispatcher – executa.

6.1.3 Critérios• uso da UCP – em porcentagem.

• throughput – nº de processos / tempo.

• tempo de UCP.

• tempo de espera.

• tempo de turnaround.

• tempo de resposta.

44

CAPÍTULO 6. GERÊNCIA DA UCP 45

6.1.4 Objetivos• Maximizar uso e throughput.

• Minimizar tempos.

6.2 Tipos de Escalonamento

6.2.1 Não-preemptivos• O processo é executado enquanto quiser

6.2.1.1 FIFO (First In First Out)

• O 1º a entrar na fila é o 1º a ser executado.

• Foi usado em sistemas batch.

• Simples, mas não dá para prever quando o processo termina ou vai para estado de espera.

Exemplo: Temos 3 processos a serem executados, com seus respectivos tempos de processador e ordem deexecução:

Processo Tempo de UCP (em unidades de tempo) OrdemA 10 1B 4 2C 3 3

Figura 6.1: Escalonamento FIFO.

O tempo médio de resposta então, é Tm = 0+10+143 = 24

3 = 8u.t.


6.2.1.2 SJF (Shortest Job First)

• A fila de execução é rearranjada de forma que a ordem de execução seja do processo que gasta menostempo para o processo que usa mais tempo de UCP.

• O tempo médio de resposta é baixo.

• É muito complicado prever quem é o menor de todos.

• Em sistemas interativos, é imprevisível.

Exemplo: Temos os mesmos 3 processos a serem executados, só que agora, a ordem de execução está deacordo com o processo mais rápido para o processo mais lento:


Figura 6.2: Escalonamento SJF.

O tempo médio de resposta então, é Tm = 0+3+73 = 10

3 = 3,3u.t.

6.2.1.3 Cooperativo

• Um processo pode ficar em execução o tempo que quiser.

• Ele voluntariamente volta à fila de prontidão ou interrompe a sua execução, liberando a UCP.

• Foi usado em ambientes operacionais, com o Windows (das versões 1.0 à 3.11.

• Situações indesejadas podem ocorrer, como a não liberação da UCP.

6.2.2 Preemptivos• O sistema operacional interrompe o processo e coloca outro em execução.


6.2.2.1 Circular

• Mais conhecido de todos.

• Muitas variações.

• Conceito de fatia de tempo.

• Não há monopólio de UCP.

• Processos CPU-Bound são privilegiados em detrimento de processos I/O-Bound.

• Problema da escolha de fatia de tempo:

– Se for muito pequena, muitas preempções, e o sistema operacional passa mais tempo escalonandodo que executando.

– Se for muito grande, torna-se um escalonamento FIFO, na prática.

• Uso de uma 2ª fila, de prontidão, para o processo I/O-Bound, que tem preferência para entrar em execuçãodo que os processos CPU-Bound – torna o balanceamento mais equilibrado (fatia de tempo menor).

Exemplo: Temos os mesmos 3 processos a serem executados, com uma fatia de tempo de 2 u.t.:


Figura 6.3: Escalonamento Circular.

O tempo médio de resposta então, é: Tm = 0+2+4+6+8+10+117 = 41

7 = 5,8u.t.

6.2.2.2 Prioridades

• Baseado num valor associado, a prioridade: maior prioridade, melhor lugar na fila de execução.

• Não há preempção por tempo, a mudança é voluntária, ou um processo de prioridade maior vai para oestado de prontidão, e toma o lugar do outro na execução.

• Pode também ser não-preemptivo


• A prioridade pode ser:

– Estática – não muda.

– Dinâmica – muda ao longo do tempo.

• Risco de starvation, o que pode ser evitado com prioridade dinâmica.

Exemplo: Temos os mesmos 3 processos a serem executados:

Processo Tempo de UCP (em unidades de tempo) PrioridadeA 10 2B 4 1C 3 3

Figura 6.4: Escalonamento por prioridades.

O tempo médio de resposta então, é: Tm = 0+3+133 = 16

3 = 5,3u.t.

6.2.2.3 Circular com Prioridades

• Aqui, une-se conceitos de prioridade associada ao processo e fatia de tempo, logo o processo fica emexecução até que:

1. Ocorra uma preempção por :

(a) Tempo(b) Prioridade

2. Ou o processo encerre a sua execução.

• Este escalonamento é amplamente usado, permitindo melhor balanceamento no uso da UCP.

6.2.2.4 Múltiplas filas

• Várias filas de execução, cada uma com uma prioridade.

• Os processos são associados as filas em função de suas características.

• Cada fila pode ter um mecanismo próprio de escalonamento

• Se o processo mudar de comportamento, ele não pode mudar de fila


6.2.2.5 Múltiplas filas com realimentação

• Aqui, os processos podem trocar de fila durante o processamento.

• Mecanismo de ajuste dinâmico, ou adaptativo.

Exemplo: várias filas:

• Escalonamento com fatias de tempo diferentes para cada fila

1. Processos I/O Bound - ficam nas filas com maior prioridade.

2. Processos CPU-Bound - começam na fila de alta prioridade, é executado e “desce” para uma fila demenor prioridade.

• Quanto mais tempo o processo usa da UCP, mais ele cai para filas de menor prioridade.

• Problemas:

1. Se o comportamento do processo mudar (CPU-Bound para I/O-Bound, por exemplo), isso compro-mete o tempo de resposta.

2. Algoritmo muito complexo, e consequentemente, lento.

6.3 Politicas de Escalonamento

6.3.1 Tempo Compartilhado• Processamento interativo, na maioria dos casos.

• Compartilhamento dos recursos de forma equilibrada.

Exemplos:

• FIFO→Processo CPU-Bound leva clara vantagem.

• Circular→Mais equilibrado – depende do tamanho da fatia.

– Muito grande→ vira FIFO.

– Muito pequeno→ fica mais tempo trocando de contexto do que executando o processo.

• Circular com prioridades→Para compensar, associa-se prioridades maiores para os processos I/O-Bound.Fica mais refinado se as prioridades forem dinâmicas – mais adotado hoje em dia.

• Deve-se levar em conta que algumas operações de E/S são mais lentos do que outras

6.3.2 Tempo Real• Algumas aplicações exigem respostas imediatas, ou em intervalo de tempo rígidos.

• Uso de escalonamento por prioridades – prioridade estática.

• Alguns sistemas tem uma taxa de prioridade onde neles ocorre exclusivamente a preempção por priori-dade.

Documents

28768592 Sistemas Operacionais 1 Notas de Aula