1

Processos e Threads

Capítulo 2

2.1 Processos2.2 Threads (2.2.1 a 2.2.4)2.3 Comunicação interprocessos - IPC (2.3.1 a 2.3.5)2.5 Escalonamento

2

Modelo de processos

(a) Multiprogramação com 4 programas(b) Modelo conceitual de 4 processos sequenciais e

independentes(c) Há somente um programa ativo em cada instante

3

Criação de processos

Principais eventos que causam a criação de processos:

● Iniciação do sistema (boot)● Execução de um sistema de criação de

processos● Pedido de usuário para criação de novo

processo● Início de um job em batch

4

Término de processos

Condições que terminam processos:● saída normal (voluntária)● saída por erro (voluntária)● erro fatal (involuntária)● morte por outro processo (involuntária)

5

Hierarquia de processos

• Processo-pai cria um ou mais processos-filho, que por sua vez podem criar outros processos.

• Este mecanismo forma uma hierarquia.– UNIX chama-a de "process group"

• Windows não possui o conceito de hierarquia.– Todos os processos são criados de forma igual.

6

Estados de um processo

• Estados possíveis para o processo:– em execução– bloqueado (dormindo)– pronto para execução

• Migração entre estados está indicada.

7

Estados de um processo

• Camada inferior de um SO estruturado por processos– cuida de interrupções e de escalonamento.

• Acima dessa camada estão os processos seqüenciais.

8

Implementação de processos

Campos presentes na tabela de processos

9

Implementação de processos

Esqueleto de ações quando ocorre uma interrupção.

10

Modelo de threads

(a) Três processos, cada um com uma thread(b) Um processo com três threads

11

O modelo de threads

(a) Itens compartilhados por todas as threads de um processo.

(b) Itens privativos de cada thread.

12

Modelo de threads

Cada thread tem sua própria pilha.

13

Uso de threads

Um processador de texto com 3 threads.

14

Uso de threads

Um servidor Web com múltiplas threads (multithreaded)

15

Uso de threads

• Esboço do código do servidor Web multithreaded– (a) Thread despachante– (b) Thread trabalhadora

16

Implementação de threads no espaço do usuário

• Exige sistema de execução (run-time system) em cada processo para gerenciar suas threads.• Troca de threads é rápida.• Troca de threads deve ser iniciada pela própria thread em execução (risco de monopolização).• Núcleo só enxerga processos.• Se uma thread for bloqueada, todo o processo também será.

17

Implementação de threads no núcleo• Núcleo enxerga e gerencia as threads de cada processo (run-time system desnecessário).• Troca de threads fica mais lenta, mas ainda é vantajosa em relação a troca de processos.• Não há risco de uma thread tomar todo o tempo alocado a seu processo.• Uma thread pode fazer chamada de sistema bloqueante sem risco de bloquear todo o processo.

18

Comunicação Interprocessos (IPC)

• Na troca de informações entre processos (ou threads), três pontos devem ser analisados:– como a informação deve ser passada,– como minimizar prejuízos causados por

competição entre processos,– como garantir uma seqüência correta de

comunicação quando dependências existem.

19

Condições de corrida

Quando dois processos tentam se comunicar por uma posição de memória compartilhada, problemas podem ocorrer.

20

Região Crítica• Parte do programa que lida com determinado

recurso compartilhado.• Exclusão mútua: só um processo está executando

dentro de uma determinada região crítica.• Condições para prover a exclusão mútua:

– não pode haver dois processos simultaneamente em uma mesma região crítica;

– não é feita nenhuma suposição sobre velocidade ou número de CPUs;

– nenhum processo executando fora de uma região crítica pode bloquear outro processo;

– nenhum processo pode esperar para sempre para poder entrar em uma região crítica desejada.

21

Regiões Críticas

Exemplo de exclusão mútuaem uma certa região crítica.

22

Exclusão mútua com espera ocupada

• Processos que aguardam para entrar em região crítica ficam ocupando CPU.

• Principais técnicas:– desabilitação de interrupções;

• interrupções não funcionariam durante execução da região crítica; riscos de processo dominar sistema;

– variáveis de travamento (lock);• região crítica só é executada se processo encontra sua

trava aberta; durante a execução, trava fica fechada;

– alternância estrita;– solução de Peterson;– instrução TSL (Test and Set Lock).

23

Exemplo de alternância estrita

Processo 0 Processo 1

• Enquanto um processo não tiver usado seu turno para executar a região crítica, o outro processo (talvez mais rápido) não poderá voltar a usá-la.

24

Solução de Peterson

• Processo que não quer usar região crítica não impede o outro de fazê-lo.

25

Uso da instrução de máquina TSL (Test and Set Lock)

• Depende de suporte de hardware (instrução especial indivisível).

• Apesar de ter surgido para resolver conflitos em sistemas multiprocessador (barramento é travado durante execução da instrução), TSL é útil também em sistemas monoprocessador.

26

Exclusão mútua com espera bloqueada• Processos que não conseguirem entrar em suas

regiões críticas (recurso compartilhado já está em uso), são bloqueados e não consomem CPU.– Uso da chamada de sistema sleep( )

• Processo que estava em sua região crítica deve desbloquear um dos processos que estiverem bloqueados aguardando a liberação do recurso compartilhado.– Uso da chamada de sistema wakeup( )

• Solução baseada apenas em sleep e wakeup não funciona corretamente, exigindo o uso de semáforos para garantir a mútua exclusão.– Semáforo é um contador de wakeups.

27

Exclusão mútua com espera bloqueada

Exemplo de condição de corrida no problema produtor-consumidor

28

Exclusão mútua com espera bloqueada

Solução do problema produtor-consumidor com semáforos

29

Escalonamento de processos• SO precisa decidir qual dos processos (ou

threads) prontos para execução deve ter acesso à CPU sempre que há uma mudança de contexto.– É preciso um algoritmo de escalonamento.

• Escalonamento deve minimizar tempo de resposta dos processos interativos e maximizar a eficiência no uso da CPU.– Prioridade, tipo, tamanho, idade etc. dos

processos devem ser levados em conta no escalonamento.

30

Comportamentos de processos

• Rajadas de uso intensivo de CPU se alternam com períodos de espera por dados em operações de E/S.– Processos estão cada vez mais parecidos com o tipo

(b) devido ao aumento da velocidade das CPUs que não é acompanhado pelos dispositivos de E/S.

31

Metas dos algoritmos de escalonamento

• Qualquer sistema:– justiça: todo processo deve receber uma fatia justa

do tempo da CPU– adoção de políticas: confirmação sobre o uso

efetivo das políticas pré-estabelecidas– equilíbrio: manter todas as partes igualmente

ocupadas

• Sistemas batch:– vazão: maximizar número de jobs por hora– prazo: minimizar tempo até a conclusão do job– uso de CPU: manter a CPU ocupada sempre

32

Metas dos algoritmos de escalonamento (cont.)

• Sistemas interativos– tempo de resposta: responder rapidamente às

entradas do usuário– proporcionalidade: atender as expectativas do

usuário quanto ao tempo a ser gasto

• Sistemas de tempo real– cumprimento de prazos: evitar perdas de dados– previsibilidade: evitar perda de qualidade em

sistemas multimídia

33

Algoritmos de escalonamentoem sistemas batch

• First-come first-served– processos ganham CPU na ordem em que chegam e a usam até

terminarem ou serem bloqueados.

• Shortest job first– executar os processos mais curtos primeiro minimiza o tempo médio

de espera total.

• Shortest remaining time first– escalonador escolhe primeiro os processos que estão mais próximos

de terminarem.

• Escalonamento em três níveis de processos na fila de entrada– admissão: controla que processo admitir e processar no sistema;

– CPU: decide que processo poderá ter acesso à CPU;

– memória: decide que processos permanecem em memória principal.

34

Exemplo de escalonamento shortest job first

Tempo de espera médio:(a) T

M = (8+12+16+20) / 4 = 14 unidades

(b) TM

= (4+8+12+20) / 4 = 11 unidades

35

Escalonamento em três níveis

• Além do escalonamento de processos na CPU, há os escalonamentos de admissão e de memória.

36

Algoritmos de escalonamentoem sistemas interativos

• Round-Robin– após término de sua fatia (quantum) de tempo,

processo é removido da CPU e levado para o fim de uma fila de processos prontos.

• Por prioridades– atribui-se prioridades aos processos e executa-se

aquele de maior prioridade primeiro.

• Filas múltiplas– processos organizados em filas que ganham

diferentes números de quanta do SO.

37

Algoritmos de escalonamentoem sistemas interativos (2)

• Shortest process next– estima-se o tempo de execução dos processos e se

dá prioridade àqueles mais curtos.

• Escalonamento garantido– define-se a fração de tempo a que cada processo

terá direito; calcula-se de tempos em tempos a fração de tempo efetivamente gasta; prioriza-se o processo que mais se afasta (para menos) da fração definida.

38

Algoritmos de escalonamentoem sistemas interativos (3)

• Loteria– processos recebem bilhetes para concorrerem a

recursos, como tempo de CPU, por exemplo; processo que for sorteado ganha direito de usar o recurso; processos mais importantes ganham um número maior de bilhetes para terem mais chances (e mais tempo) de usar CPU.

• Parcela justa– tempo de CPU é dividido igualmente entre o

número de usuários (e não de processos), evitando que usuários com muitos processos monopolizem a CPU.

39

Escalonamento Round-Robin

(a) Lista de processos prontos.

(b) Lista de processos prontos após B ter usado a CPU.

40

Escalonamento por prioridades

Cada processo é colocado em uma fila correspondente à sua prioridade pré-definida.

41

Algoritmos de escalonamentoem sistemas de tempo real

• Processos precisam responder a eventos de forma correta e dentro do prazo estabelecido.

• Condição para processos serem escalonáveis em resposta a eventos periódicos: – sejam m eventos periódicos, onde evento i ocorre a

cada Pi segundos gastando Ci segundos por vez;

– processos serão escalonáveis se

1

1m

i

i i

C

P=

≤∑

42

Política X Mecanismode escalonamento

• Separa-se o que pode ser feito de como é feito.– Um processo pode saber qual de suas threads é

importante e precisa ser priorizada. Logo, seria bom deixá-lo ajudar no escalonamento.

• Algoritmo de escalonamento pode ser parametrizado.– O mecanismo do escalonamento fica no núcleo.

• Parâmetros do algoritmo são fornecidos pelos processos.– A política é definida pelos processos.

43

Escalonamento de threadsno nível do usuário

• A troca de threads ocorre dentro do processo sem conhecimento do núcleo.

• Algoritmos de escalonamento definidos pelo sistema de execução (runtime system).

44

Escalonamento de threads no nível do núcleo

• A troca de threads ocorre devido a ação direta do núcleo.• Algoritmos de escalonamento definidos pelo núcleo podem mudar o

contexto de uma thread de um processo para uma thread de outro processo (mudança mais lenta que entre threads do mesmo processo).