Sistemas Operacionais 1

Sistemas Operacionais Unidade Dois

Prof. Flávio Márcio de Moraes e Silva

Conceito de Processo 

Processo – um programa em execução 



Organizados em vários processos seqüenciais

Um processo inclui: 

Contador de programa



Registradores (pilha)



Variáveis (seção de dados)

Sistemas Operacionais

Prof. Flávio Márcio

2

Estados de Processos 

A medida em que o programa executa, seu estado muda:  

  

Novo: O processo está sendo criado Pronto: O processo está esperando para ser atribuído a um processador Em execução: Instruções estão sendo executadas Em espera: O processo espera por um evento Encerrado: O processo terminou sua execução

Sistemas Operacionais

Prof. Flávio Márcio

3

Estados de Processos

novo

encerrado

2 pronto

em execução 3

4 em espera

Sistemas Operacionais

Prof. Flávio Márcio

1

4

Transição de Estado 

Transição 1 





Ocorre quando um processo descobre que não pode prosseguir

Transições 2 e 3 

São causadas pelo escalonador de processo



O processo não precisa tomar conhecimento que foi interrompido



Dispatcher = responsável pela reposição de contexto (voltar valores dos registradores na transição 3)

Transição 4 

Ocorre quando acontece um evento externo pelo qual um processo estava aguardando

Sistemas Operacionais

Prof. Flávio Márcio

5

Bloco de Controle de Processos 

Informação associada com cada processo 

Contador de Programa



Pilha de execução



Registradores da CPU



Estado do processo (apto, executando, bloqueado,etc)



Informações de escalonamento de CPU (tempo de processador, prioridade)



Informações de gerência de memória



Informações de status de I/O



Informações de arquivos abertos

Sistemas Operacionais

Prof. Flávio Márcio

6

Threads 

Processos são baseados em dois conceitos independentes: agrupamento de recursos e execução 



Threads são úteis quando há a necessidade de separá-los

Um thread (ou processo leve) é uma unidade básica de utilização da CPU. Consiste em: 





Contador de programa: para manter o controle da próxima instrução a ser executada Conjunto de registradores: contêm suas variáveis atuais de trabalho Pilha: traz o histórico de execução, e uma estrutura para cada processo chamado e não retornado

Sistemas Operacionais

Prof. Flávio Márcio

7

Threads 



Um thread compartilha com outros threads do mesmo processo: 

Seção de código



Seção de dados



Recursos do SO

Um processo tradicional ou pesado é igual a uma tarefa com apenas um thread

Sistemas Operacionais

Prof. Flávio Márcio

8

Threads 

Em uma tarefa com múltiplos threads, enquanto um thread servidor está bloqueado e esperando, um segundo thread na mesma tarefa pode executar 





Cooperação entre múltiplos threads na mesma tarefa confere maior produção (throughput) e performance Aplicações que requerem o compartilhamento de um buffer comum se beneficiam da utilização de threads

Exemplos: 



Um navegador Web pode ter um thread exibindo uma imagem enquanto outro recupera dados na rede Um editor de textos pode ter um thread lendo caracteres do teclado enquanto outro faz a verificação ortográfica

Sistemas Operacionais

Prof. Flávio Márcio

9

Threads 

Vantagens 

Capacidade de Resposta: tarefas podem ser executadas enquanto outras esperam por recurso



Compartilhamento de Recursos: facilita acesso



Economia: alocar memória e recursos para a criação de um processo novo é caro



Utilização de arquiteturas paralelas

Sistemas Operacionais

Prof. Flávio Márcio

10

Processos com um ou Vários Threads

Sistemas Operacionais

Prof. Flávio Márcio

11

Escalonamento: Conceitos Básicos 

A utilização máxima de CPU é obtida através de multiprogramação. Com um só processador, nunca haverá mais de um processo em execução



Quando dois ou mais processos estão na situação de pronto, o SO deverá fazer a escolha de qual processo será executado 

Escalonador é a parte do SO que escolhe processo



Utiliza algoritmos de escalonamento



A troca de processo é “cara” para a CPU

Sistemas Operacionais

Prof. Flávio Márcio

12

Comportamento do Processo 

Todo processo alternam surtos de uso da CPU com requisições de E/S



Tipos de surtos 

Orientado a CPU 



Orientado a E/S 



Passam a maior parte do tempo utilizando a CPU Passam a maior parte do tempo realizando E/S

A medida que a velocidade dos processadores aumentam os processos tendem a ficar orientados a E/S

Sistemas Operacionais

Prof. Flávio Márcio

13

Critérios de Escalonamento 

É fundamental o SO saber o momento certo de escalonar um processo



Decisões de escalonamento de CPU ocorrem quando o processo: 1. 2. 3. 4.

Muda do estado de execução para espera Muda do estado de execução para pronto Muda do estado de espera para pronto Termina



Escalonamento não-preemptivo um processo só perde a CPU por vontade própria (término ou chamada de sistema 1 e 4).



Escalonamento preemptivo o processo em execução pode perder a CPU para outro e maior prioridade (2 e 3).

Sistemas Operacionais

Prof. Flávio Márcio

14

Critérios de Escalonamento 

Características para comparação de algoritmos:  







Utilização de CPU: manter a CPU o mais ocupada possível Throughput: quantidade de processos que completam sua execução por unidade de tempo Tempo de retorno: quantidade de tempo para executar um processo Tempo de espera: quantidade de tempo que um processo gasta na fila de processos prontos Tempo de resposta: quantidade de tempo gasto entre a requisição e a produção da primeira resposta

Sistemas Operacionais

Prof. Flávio Márcio

15

Critérios de Escalonamento 

Máxima utilização de CPU



Máximo throughput



Mínimo tempo de retorno



Mínimo tempo de espera



Mínimo tempo de resposta

Sistemas Operacionais

Prof. Flávio Márcio

16

Algoritmos de Escalonamento 

Primeiro a chegar é servido (FIFO) 

Exemplo:

Processo

Duração de Surto

P1 24 P2 3 P3 

3

Suponha que os processos chegam na ordem: P1 , P2 , P3 O diagrama para o escalonamento é: P1 0

P2 24

P3 27

30



O tempo de espera para P1 = 0; P2 = 24; P3 = 27



O tempo de espera médio: (0 + 24 + 27)/3 = 17

Sistemas Operacionais

Prof. Flávio Márcio

17

Algoritmos de Escalonamento 

Primeiro a chegar é servido (FIFO) 

Suponha que os processos cheguem na ordem: P2 , P3 , P1



O diagrama para o escalonamento é: P2 0

P3 3

P1 6

30



O tempo de espera para P1 = 6; P2 = 0; P3 = 3



O tempo de espera médio : (6 + 0 + 3)/3 = 3



Muito melhor que o anterior



Efeito Comboio: pequenos processos atrás de longos processos

Sistemas Operacionais

Prof. Flávio Márcio

18

Algoritmos de Escalonamento 

Escalonamento job mais curto primeiro (SJF) 



Associa a cada processos o tamanho do seu próximo surto de CPU. Usa estes valores para escalonar o processo com o menor tempo Dois esquemas: 





Não-preemptivo – uma vez que a CPU é dada ao processo, não pode ser retirada até completar seu surto Preemptiva – se um novo processo chegar com um tempo de surto de CPU menor que o tempo restante do processo sendo executado, é feita a troca. Este esquema é conhecido como Menor-temporestante-primeiro (SRTF)

SJF é ótimo – sempre dá o mínimo tempo médio de espera para o conjunto de processos

Sistemas Operacionais

Prof. Flávio Márcio

19

Algoritmos de Escalonamento  

Escalonamento job mais curto primeiro (SJF) Exemplo Processo Chegada Tempo Surto P1

0.0

P2



2.0

4

P3

4.0

1

P4

5.0

4

SJF (não-preemptivo) P1

0 

7

7

P4

P2

P3

8

12

16

Tempo médio de espera = (0 + 7 + 8 + 12)/4

Sistemas Operacionais

Prof. Flávio Márcio

20

Algoritmos de Escalonamento  

Escalonamento job mais curto primeiro (SJF) Exemplo Processo Chegada Tempo Surto P1

0.0

P2



2.0

4

P3

4.0

1

P4

5.0

4

SJF (preemptivo) P1

0 

7

P2

2

P3

4

5

P1

P4

P2

7

11

16

Tempo médio de espera = (0 + 2 + 4 + 7)/4

Sistemas Operacionais

Prof. Flávio Márcio

21

Algoritmos de Escalonamento  

Escalonamento por prioridade Um número de prioridade (inteiro) é associado com cada processo



A CPU é alocada para o processo com maior prioridade (menor valor ≡ maior prioridade)



SJF é um escalonamento por prioridade, onde a prioridade é dada pelo tempo de surto



Problema: Starvation – processos com baixa prioridade podem nunca serem executados



Solução: Envelhecimento (Aging) – a prioridade aumenta com o tempo

Sistemas Operacionais

Prof. Flávio Márcio

22

Algoritmos de Escalonamento 

Round Robin (RR) 





Cada processo recebe uma pequena unidade de tempo de CPU (quantum), geralmente 10-100 ms. Após este tempo, o processo é retirado e inserido no fim da fila de prontos Se existirem n processos na fila de prontos e o quantum for q, cada processo terá 1/n de tempo de CPU em parcelas de no máximo q unidades de tempo por vez. Nenhum processo esperará mais que (n-1)q unidades de tempo Não precisa esperar até o final do quantum 

Quando um processo termina outro processo utiliza a CPU imediatamente

Sistemas Operacionais

Prof. Flávio Márcio

23

Algoritmos de Escalonamento 

Round Robin (RR) 

Desempenho 

q grande ⇒ FIFO



q pequeno ⇒ q deve ser grande em relação ao tempo de troca de contexto, ou o overhead será muito alto 

Se q possui 4ms e o tempo de chaveamento é 1ms, o resultado será péssimo

Sistemas Operacionais

Prof. Flávio Márcio

24

Algoritmos de Escalonamento  

Round Robin (RR) -> q = 20 Exemplo Processo Tempo de Surto P1 P2 P3 P4



O diagrama é: P1 0



53 17 68 24

P2 20

P3 37

P4 57

P1 77

P3

P4

97 117

P1

P3

P3

121 134 154 162

Tipicamente, maior média de retorno que SJF, mas melhor resposta

Sistemas Operacionais

Prof. Flávio Márcio

25

Algoritmos de Escalonamento 

Fila Multiplas 

A fila de prontos é particionada em filas separadas:  



Cada fila tem seu próprio algoritmo de escalonamento, por exemplo:  



primeiro plano (interativo) segundo plano (batch)

primeiro plano – RR segundo plano – FIFO

Deve haver escalonamento entre as filas 



Escalonamento de prioridade fixa: primeiro plano pode ter prioridade sobre o segundo plano. Possibilidade de starvation Fatia de tempo: cada fila recebe uma certa quantidade de tempo de CPU que pode ser escalonada entre seus processos. Por exemplo, 80% para primeiro plano em RR e 20% para o segundo plano em FIFO

Sistemas Operacionais

Prof. Flávio Márcio

26

Algoritmos de Escalonamento 

Fila Multiplas com Realimentação 



Um processo pode passar de uma fila para outra. O envelhecimento pode ser implementado desta maneira O escalonador de Filas Múltiplas com realimentação é definido pelos seguintes parâmetros: 

número de filas



algoritmos de escalonamento para cada fila







método usado para determinar a promoção de um processo a uma fila de maior prioridade método usado para determinar quando rebaixar um processo método usado para determinar em qual fila o processo deve entrar quando precisar de serviço

Sistemas Operacionais

Prof. Flávio Márcio

27

Algoritmos de Escalonamento 

Fila Multiplas com Realimentação 



Três filas: 

Q0 – quantum 8 ms



Q1 – quantum 16 ms



Q2 – FCFS

Escalonador 



Um novo job entra na fila Q0 servido por FCFS. Quando recebe CPU, o job tem 8 ms. Se não terminar em 8 ms, o job é removido para Q1. Em Q1 o job é servido por FCFS e recebe 16 ms adicionais. Se ainda não terminar, é transferido para Q2.

Sistemas Operacionais

Prof. Flávio Márcio

28

Sincronização de Processos 



Processos podem compartilhar armazenamentos em comum, onde cada um pode ler e escrever Problema 









Imagine que um spool tenha um vetor quem contém os nomes de arquivos a serem impressos Esse vetor possui duas variáveis: out – aponta para o próximo arquivo a ser impresso e in – aponta para a próxima posição vaga no vetor Um processo A ler a próxima posição livre (in) e é escalonado pela CPU Um processo B ler a próxima posição livre, armazena o arquivo e incrementa in O processo A armazena o arquivo a ser impresso e incrementa in 

O arquivo de impressão do processo B é perdido

Sistemas Operacionais

Prof. Flávio Márcio

29

Regiões Críticas 

O que fazer para evitar condições de disputa? 



Exclusão mútua: assegurar que processos sejam impedidos de usar uma variável ou arquivo compartilhado que já estiver em uso por outro processo

Região crítica 

Parte do código em que há acesso à memória compartilhada

Sistemas Operacionais

Prof. Flávio Márcio

30

Regiões Críticas 

Uma boa solução deve satisfazer: 1. Nunca dois processos podem estar simultaneamente em suas regiões críticas 2. Nada pode ser afirmado sobre velocidade ou sobre o número de CPUs 3. Nenhum processo executado fora da sua região crítica pode ser bloqueado por outros processos 4. Nenhum processo deve esperar eternamente para entrar em sua região crítica

Sistemas Operacionais

Prof. Flávio Márcio

31

Exclusão Mútua com Espera Ociosa 

Desabilitando interrupções 



Problema dessa abordagem 



O processo desabilita todas as interrupções logo após entrar em sua região crítica e reabilita-as antes de sair

Processos de usuário podem desabilitar interrupções e nunca reabilitá-las

Há casos que é necessários que o núcleo do SO desabilite alguma interrupção 

Enquanto estiver alterado variáveis ou listas

Sistemas Operacionais

Prof. Flávio Márcio

32

Exclusão Mútua com Espera Ociosa 

Variáveis de impedimento 

Exemplo: 





Se uma variável lock estiver marcada como 0 o processo entra na região crítica e a altera para 1 Se a variável lock estiver marcada como 1 o processo espera

Essa idéia não funciona 

Antes de alterar a variável para um o processo a lê como 0 e é escalonado pela CPU. Assim outro processo pode ler a variável como 0, alterá-la para 1 e entrar na região crítica

Sistemas Operacionais

Prof. Flávio Márcio

33

Exclusão Mútua com Espera Ociosa 

Alternância Obrigatória  



Baseada na seqüência lógica antecessor/sucessor Alterna o acesso à região crítica entre dois processos

Desvantagem  



Teste continuo do valor da variável compartilhada Se um processo falha o outro jamais entra na região crítica Viola a regra 2 se a parte não critica de um processo for outro B A muito maior que a do Processo

Processo while (TRUE){ while (turn!=0); // lock() região_critica turn=1; // unlock() } Sistemas Operacionais

while (TRUE){ while (turn!=1); // lock() região_critica turn=0; // unlock() }

Prof. Flávio Márcio

34

Exclusão Mútua com Espera Ociosa 

Solução de Paterson 

Antes de usar as variáveis compartilhadas, cada processo chama enter_region com seu próprio número de processo (0 ou 1)



Essa chamada fará com que ele fique esperando até que seja seguro entrar



Após usar as variáveis compartilhadas, o processo chama leave_region

Sistemas Operacionais

Prof. Flávio Márcio

35

Exclusão Mútua com Espera Ociosa 

Solução de Paterson

#define FALSE 0 #define TRUE 1 #define N 2 //número de processos int turn; //de quem a vez int interested[N]; //todos os valores iniciados com 0 void enter_region(int process) { //processo é 1 ou 0 int other; //número do outro processo other = 1 – process; //o outro processo interested[process] = TRUE; //mostra quem você está interessado turn = process; //altera o valor de turn while (turn==process && interested[other]==TRUE); //comando nullo } void leave_region(int process) { //processo: quem está saindo interested[process] = FALSE; //indica a saída da região crítica } Sistemas Operacionais

Prof. Flávio Márcio

36

Exclusão Mútua com Espera Ociosa 

A instrução TSL (Test and Set Lock) 



Proposta que requer auxílio de hardware

TSL RX, LOCK 

Copia o conteúdo da variável de memória LOCK no registrador RX e então armazena um valor diferente de zero no endereço de memória LOCK  

enter_region: TSL reg, lock Se LOCK > 0, seção crítica ocupada CMP reg, #0 JNE enter_region RET

Se LOCK = 0, seção crítica livre

leave_region: MOVE lock, #0 RET Sistemas Operacionais

Prof. Flávio Márcio

37

Semáforos 

Utiliza uma variável inteira (o semáforo) para controla o acesso ao recurso compartilhado 





Primitivas do semáforo 





O valor zero indica que nenhum sinal de acordar está pendente Um valor positivo N indica o número de sinais pendentes Down – Chamada quando o processo deseja acessar o recurso compartilhado Up – Chamada quando o processo deseja liberar o recurso compartilhado

As operações Down e Up são executadas de forma atômica sobre o semáforo

Sistemas Operacionais

Prof. Flávio Márcio

38

Semáforos 

Problema do produtor-consumidor 

Necessita 3 semáforos 

1 para garantir a exclusão mútua 



1 para bloquear os produtores o quando a fila estiver cheia (sem slots disponíveis) 



mutex – regição crítica: Usados para implementar exclusão mútua. Também chamados de binários (assumem apenas 0 e 1)

full – buffer cheio

1 para bloquear os consumidores o quando a fila estiver vazia (sem itens na fila) 

Sistemas Operacionais

empty – buffer vazio

Prof. Flávio Márcio

39

Semáforos define N 100 semaphore mutex=1; semaphore full=0; semaphore empty=N; void producer(void) { int item; while(1) { item=produz_item(); down(&empty); down(&mutex); insere_item(item); up(&mutex); up(&full); } }

Sistemas Operacionais

void consumer(void) { int item; while(1) { down(&full); down(&mutex); item=remove_item(); up(&mutex); up(&empty); consome_item(item); } }

Prof. Flávio Márcio

40