Sistemas Operacionais Processos e Threads Prof. Eduardo Alchieri
Processos
O conceito mais central em qualquer sistema operacional é o processo
Uma abstração de um programa em execução
Um programa por si só não é um processo. Um programa é uma entidade passiva, enquanto o processo é uma entidade ativa Processos são programas em execução, constituidos por: código executável, pilha de execução, estado do processo, prioridade do processo, valor do contador de programa (registrador PC), valor do apontador de pilha (registrador SP), valores de demais registradores
Processos
Processo x Programa
Exemplo: preparação de bolo de aniversário
A receita – programa (algoritmo)
Os ingredientes – dados de entrada
O cozinheiro – processador
Atividade de preparar o bolo (processo)
Caso o filho do cozinheiro for picado por uma abelha – interrupção e chaveamento para um novo processo
Processo de fornecer cuidados médicos: livro de primeiros socorros (programa), remédios (dados de entrada), o cozinheiro (processador) e atividade de cuidar da picada (processo) Quando terminar, volta para o processo de preparar o bolo
Processos (modelo de processos)
Através de processos é possível ter ''operações concorrentes''
Transformam um única CPU em várias CPUs virtuais Pseudoparalelismo: rápida alternância entre os processos na CPU (multiprogramação)
Processos (modelo de processos)
Recursos utilizados por um processo
Memória: um processo precisa de memória para armazenar suas instruções e seus dados CPU: um processo precisa estar de posse da CPU para executar suas instruções Dispositivos: via de regra, um processo precisa realizar alguma tarefa de entrada e saída, em algum dispositivo, como por exemplo receber o valor de uma variável via teclado, ler um disco, etc. Arquivos: um processo, geralmente, precisa gravar ou recuperar alguma informação armazenada em determinado arquivo
Processos (modelo de processos)
Um processo é formado por três elementos básicos:
Contexto de hardware
Contexto de software
Espaço de endereçamento
C o n te x to d e S o f tw a r e
C o n te x t o d e H a rd w a re
Pro g ra m a E sp a ço d e E n d e r e ç a m e n to
Processos (modelo de processos)
Contexto de hardware
O contexto de hardware constituí-se, basicamente, do conteúdo de registradores (PC, SP, etc.) Quando um processo está em execução, o seu contexto de hardware está armazenado nos registradores do processador O contexto de hardware é fundamental para a implementação dos sistema de tempo compartilhado (multiprogramados), no qual os processos se revezam na utilização do processador A troca de um processo por outro na CPU, realizado pelo SO, é denominada Troca de Contexto
Processos (modelo de processos)
S is te m a O p e r a c i o n a l
Contexto de hardware
Na troca de contexto, o SO armazena o conteúdo
P ro ce sso A
P ro ce ss o B
e x e c u ta n d o
S a l v a r e g is tr a d o r e s d o P ro ce ss o A
dos registradores da CPU
C a r r e g a r e g is tr a d o r e s d o P ro ce sso B
e x e c u ta n d o
S a l v a r e g is tr a d o r e s d o P ro ce sso B
C a r r e g a r e g is tr a d o r e s d o P ro ce ss o A
e x e c u ta n d o
Processos (modelo de processos)
Contexto de software
O contexto de software especifica características do processo que influênciam na execução de um programa Composto por 3 grupos de informações:
Identificação
Quotas
PID (Process Identification) – cada processo criado pelo sistema recebe uma identificação única. As informações sobre um processo estão armazenadas na tabela de processos, indexada pelo PID UID (User Identification) – cada processo deve possuir também uma identificação do usuário São os limites de cada recurso do sistema (arquivos, memória, etc) que um processo pode alocar
Privilégios
Definem o que o processo pode ou não fazer em relação ao sistema e aos outros processos
Processos (modelo de processos)
Espaço de endereçamento
Área de memória onde o programa será armazenado, além do espaço para os dados utilizados por ele Cada processo possui seu próprio espaço de endereçamento, que deve ser protegido do acesso dos demais processos
Pilha de execução
Dados Código
Processos (criação de processos)
Principais eventos que causam a criação de um processo
Inicialização do sistema
Na inicialização vários processos são criados
Exemplo: processo para receber requisições de páginas Web
Execução de uma chamada de sistema de criação de processo por um processo em execução
Exemplo: no UNIX a chamada fork
Uma requisição do usuário para criar um novo processo
Processos pais criam processos filhos, que podem criar seus próprios processos filhos e assim por diante
Em sistemas interativos, digitando um comando ou clicando em um ícone
Início de uma tarefa em lote
Em computadores de grande porte, quando o mesmo possui recursos suficientes para executar a tarefa
Processos (término de processos)
Condições que terminam um processo
Saída Normal (voluntária)
Quando terminaram seu trabalho
Saída por erro (voluntária)
Processo descobre um erro fatal
Exemplo: compilar um arquivo que não existe
Erro fatal (involuntária)
Erro causado pelo processo, normalmente erro de programação
Exemplo: divisão por zero, referência para memória inexistente
Cancelamento por um outro processo (involuntária)
Um processo executa uma chamada de sistema dizendo ao SO para cancelar algum outro processo Exemplo: no UNIX a chamada kill
Processos (tipos de processos)
Os processos são classificados de acordo com o tipo de processamento que realizam Existem dois tipos de processos: CPU-bound: um processo é dito CPU-bound quando passa a maior parte do tempo utilizando o processador
I/O-bound:um processo é dito I/O-bound quando passa a maior parte do tempo realizando operações de I/O (E/S)
Períodos de uso de CPU alternados com períodos de espera por operações de E/S
a) Processo CPU-bound b) Processo I/O bound
Processos (estados de processos)
Consiste da atividade atual do processo Há várias formas de representar os estados de um processo, variando o detalhamento dos estados possíveis Segundo Tanembaum
Estados Em execução: o processo tem o controle da CPU (processador) Pronto: aguarda sua vez de usar a CPU Bloqueado: está ocioso e aguarda o ocorrência de algum evento externo
Processos (estados de processos)
Segundo Stallings
Estados Não executando: representa o processo inativo Esta aguardando ser chamdo pelo sistema Esta aguardando a sua vez de usar o processador Execuntando: processo que detém o controle da CPU (processador) durante determinado tempo
Processos (estados de processos)
Segundo Silberschatz
Estados Novo (New): o processo esta sendo criado Executando (running): processo em execução Aguardando (waiting): processo aguardando ocorrer algum evento Pronto (ready): aguardando sua vez de utilizar o processador Terminado (Terminated): processo completou sua execução
Processos (implementação de processos)
Todas as informações sobre um processo são mantidas na tabela de processos A tabela de processos tem campos que dizem respeito: à gerência do processo à gerência da memória à gerência de arquivos A tabela de processos possui uma entrada por processo e os campos nela contidos variam de sistema operacional para sistema operacional
Processos (implementação de processos)
Alguns campos típicos de um processo na tabela
Processos (modelando a multiprogramação)
Usando multiprogramação, a utilização da CPU pode ser aumentada
Com a multiprogramação mais de um processo compete pela CPU, de forma que quando um processo estiver aguardando por algum evento (ex.: E/S) outro processo pode utilizar a CPU
Processos
Escalonamento de Processos
Processos (escalonamento)
Em computadores multiprogramados, muitas vezes múltiplos processos (ou threads) competem pelo CPU ao mesmo tempo
Isso ocorre sempre que dois ou mais processos estão simultaneamente no estado pronto
Nestes casos, quando o CPU se encontrar disponível, deverá ser feita uma escolha sobre qual processo executar
A parte do sistema operacional que faz esta escolha é o escalonador e o algoritmo que ele usa é o algoritmo de escalonamento É tarefa do escalonador também determinar quanto tempo o processo poderá utilizar a CPU O algoritmo de escalonamento define, assim, a política de utilização do processador pelos processos
Processos (escalonamento)
Quando um processo solicita operações bloqueantes (E/S, por exemplo), sua execução fica suspensa até que o evento solicitado ocorra
Se outro processo estiver pronto para execução, o mesmo poderá passar a utilizar a CPU, maximizando a utilização da mesma, melhorando o desempenho percebido do sistema
Execução de 2 processos sem concorrência exec
idle
exec idle
exec
idle
P1 exec
idle
exec
P2
Execução de 2 processos com concorrência exec idle
idle exec
exec idle idle
exec
exec
P2
P1
Processos (escalonamento)
Processos geralmente alternam períodos de utilização da CPU (surtos de computação) com requisições de E/S
a) um processo orientado a CPU
b) um processo orientado a E/S
Processos (escalonamento)
Quando um processo é trocado por outro para execução, o sistema operacional deverá fazer o troca de contexto (ou chaveamento de contexto) para o novo processo em execução Este troca é custosa e as seguintes tarefas são realizadas:
Chaveamento do modo usuário para modo núcleo
O estado atual do processo deve ser salvo
Em muitos sistemas, o mapa da memória (ex.: os bits de referência à memória na tabela de páginas da memória) também deve ser salvo O novo processo precisa ser selecionado (algoritmo de escalonamento) A unidade de gerenciamento da memória (MMU) deve ser carregada com o novo mapa de memória
O novo processo precisa ser iniciado
Além disso, normalmente toda a cache fica inválida
Por isso, todo o cuidado é pouco!
Processos (escalonamento)
Quando escalonar ?
1 – Quando um processo é criado
2 – Quando um processo termina
3 – Quando o termina o tempo de CPU para um processo e o mesmo passa do extado executando para pronto 4 - Quando um processo bloqueia esperando por uma operação de E/S 5 – Quando ocorre a interrupção de E/S, i.e., quando a operação de E/S terminou e o processo que estava bloqueado passa a ficar pronto para execução
Processos (escalonamento)
Os algoritmos de escalonamento podem ser divididos em duas categorias: Não preemptivos: escolhe um processo para executar e, então, o deixa executar até que seja bloqueado ou até que ele voluntariamente libere a CPU Preemptivos: escolhe um processo e o deixa em execução até um tempo máximo fixado. Se ao final deste tempo ainda estiver em execução, o processo será suspenso (vai do estado executando para pronto) e o escalonador escolherá outro processo para executar
Processos (escalonamento)
Como controlar o tempo de execução do processo?
Todo processador moderno possui um clock que gera interrupções em uma freqüência determinada (ex.: 50 Hz) Cada uma destas interrupções é chamada clock tick. O S.O. mantém um contador que é decrementado a cada clock tick Se o contador chegar a 0, o tempo de permanência do processo acabou. O valor inicial deste contador corresponde ao tempo máximo de permanência do processo com a CPU e denomina-se time slice
Processos (escalonamento)
Para ambientes e objetivos diferentes, são necessários diferentes algoritmos de escalonamento. Desta forma, aquilo que deve ser otimizado pelo escalonador não é o mesmo para todos os sistemas Três categorias de algoritmos de escalonamento
Lote Em geral usam algoritmo não preemptivos ou preemptivos com um grande intervalo de tempo para cada processo Interativo
Preempção é essencial para evitar que um processo se aposse da CPU Tempo real
As vezes preempção não é necessária pois processos executam rapidamente e são bloqueados
Processos (escalonamento)
Ao se projetar um escalonador, é importante observar vários critérios que devem estar presentes em um bom algoritmo de escalonamento, estes critérios podem ser diferentes entre as classes de sistemas Para todas as classes:
Justiça: dar a cada processo um porção justa da CPU Aplicação da política: verificar se a política estabelecida esta sendo cumprida (exemplo: que os processos de controle da segurança sejam executados quando quiserem, independente de outros processos estarem presentes) Equilíbrio: manter ocupadas todas as partes do sistema
Processos (escalonamento)
Sistemas em lote:
Tempo de retorno: minimizar o tempo entre a submissão e o término Utilização da CPU: manter a CPU ocupada o tempo todo
Sistemas interativos
Vazão (throughput): maximizar o número de tarefas por hora
Tempo de resposta: responder rápidamente às requisições Proporcianalidade: satisfazer às expectativas dos usuários (ex.: enviar um fax demora mais do que abrir um arquivo)
Sistemas de tempo real
Cumprimento dos prazos: evitar a perda de deadlines Previsibilidade: evitar a degradação da qualidade em sistemas multimídia (ser previsível e regular na exibição de um audio)
Processos (algoritmos de escalonamento)
Ao se projetar um algoritmo de escalonamento, deve-se ter em mente que o comportamento de um processo é imprevisível na maior parte dos casos
Quase nunca se sabe quando um processo irá se bloquear ou terminar a execução, uma vez a execução iniciada
Escalonamento em sistemas em lote
Primeiro a chegar, primeiro a ser servido (FIFO – First In, First Out)
Tarefa mais curta (menor job) primeiro (SJR – Shortest-Job-First)
Próximo de menor tempo restante (SRTF - shortest remaining time next)
Escalonamento em sistemas interativos
Escalonamento por chaveamento circular (round-robin)
Escalonamento por prioridades
Escalonamento por Filas Múltiplas
Escalonamento de tempo real
Processos (algoritmos de escalonamento - FIFO)
Primeiro a chegar, primeiro a ser servido (FIFO – First In, First Out ou ainda FCFS - first come, first served) É um algoritmo de escalonamento não preemptivo, onde a CPU é atribuída aos processos na ordem em que eles a requisitam Quando um processo é bloqueado (espera por E/S) a CPU é alocada ao próximo processo da fila Quando a operação de E/S termina e o processo é desbloqueado, o mesmo vai para o final da fila Algoritmo problemático para sistemas de tempo compartilhado
Cada usuário precisa ter acesso a intervalos frquêntes da CPU
Caso processos muito longos estejam sendo executados, os mesmos podem causar um grande tempo de espera para outros processos
Processos (algoritmos de escalonamento - FIFO)
Exemplo: Processo Tempo de execução P1 24
P2
3
P3
3
Suponha que os processos tenham chegado na ordem: P1, P2, P3. Graficamente: P1 0
P2 24
P3 27
30
Tempo de espera para P1 = 0; P2= 24; P3 = 27
Média do tempo de espera: (0+24+27)/3 = 17
Processos (algoritmos de escalonamento - FIFO)
Agora suponha que os processos tenham chegado na ordem: P2, P3, P1. Graficamente: P2 0
P3 3
P1 6
Tempo de espera para P1 = 6; P2= 0; P3 = 3
Média do tempo de espera: (6+0+3)/3 = 3
Melhor que no caso anterior!
30
Processos (algoritmos de escalonamento - FIFO)
Exercício
Considere o seguinte conjunto de processos Processo P1
Tempo de execução 10
P2
5
P3
2
Represente graficamente sua execução usando o algoritmo FIFO, calcule a média de tempo de espera de execução dos três processos. Considere a ordem de chegada: P1, P2 e P3 Refaça considerando a ordem de chegada P2, P3 e P1. Compare com o resultado anterior.
Processos (algoritmos de escalonamento - SJF)
Tarefa mais curta primeiro (SJR – Shortest-Job-First)
Está associado ao tempo de execução de cada processo
Algoritmo não preemptivo que supõe como previamente conhecidos todos os tempos de execução Os processos são executados de acordo com o tempo necessário para executar sua tarefa
Processos (algoritmos de escalonamento - SJF)
Exemplo Processo
Tempo de Execução
P1
6
P2
8
P3
7
P4
3
Usando o SJF, teremos graficamente a seguinte ordem de execução: P4
0
P1
3
P3
9
P2
16
24
Média do tempo de espera = (3 + 16 + 9 + 0)/4 = 7
Utilizando o FIFO teríamos uma média de (0+ 6 + 14 + 21)/4 = 10,25
Processos (algoritmos de escalonamento - SJF)
Uma dificuldade neste algoritmo é saber o tamanho do próximo processo, mesmo antes de ser admitido. Exemplo: Processo
Tempo de Chegada
Tempo de Execução
P1
0,0
7
P2
2,0
4
P3
4,0
1
P4
5,0
4
Usando o SJF, teremos graficamente a seguinte ordem de execução: P1
0
3
P3
7
P2
8
P4
12
16
Média do tempo de espera = (0 + 6 + 3 + 7)/4 = 4
Melhoraria caso P2 iniciasse sua execução logo após sua chegada?
Processos (algoritmos de escalonamento - SRTF)
Próximo de menor tempo restante (SRTF - shortest remaining time first)
Variável preemptiva do SJF Quando chegar uma tarefa com um tempo de execução menor do que o tempo restante de execução da tarefa que atualmente ocupa a CPU, então a CPU é cedida para a execução da mesma Ocorre a troca do processo que estava na CPU pelo novo processo admitido
Processos (algoritmos de escalonamento - SRTF)
Vejamos no exemplo anterior Processo
Tempo de Chegada
P1
0,0
7
P2
2,0
4
P3
4,0
1
P4
5,0
Usando o SRTF:
0
P2 2
4
P1
Usando o SJF: média de espera de 4 P1
Tempo de Execução
P3 4
0
3
P2 5
P3 7 P4
7
P2
8
P4 12
P1 11
16
Tempo de Espera: P1=(16-7-0); P2=(7-4-2); P3=(5-1-4); P4=(11-4-5)
Média do tempo de espera = (9 + 1 + 0 +2)/4 = 3
16
Processos (algoritmos de escalonamento – SJF e SRTF)
Exercício 1
Considere o seguinte conjunto de processos
Processo
Tempo de Chegada
Tempo de Execução
P1
0,0
4
P2
2,0
10
P3
3,0
3
Represente graficamente sua execução usando os algoritmos SJF e SRTF, calcule a média dos tempos de espera de execução dos três processos para cada um dos algoritmos
Processos (algoritmos de escalonamento – SJF e SRTF)
Exercício 2
Considere o seguinte conjunto de processos
Processo
Tempo de Chegada
Tempo de Execução
P1
0,0
11
P2
4,0
5
P3
6,0
2
Represente graficamente sua execução usando os algoritmos SJF e SRTF, calcule a média dos tempos de espera de execução dos três processos para cada um dos algoritmos
Processos (algoritmos de escalonamento – SJF e SRTF)
Exercício 3
Considere o seguinte conjunto de processos
Processo
Tempo de Chegada
Tempo de Execução
P1
0,0
16
P2
7,0
8
P3
8,0
3
Represente graficamente sua execução usando os algoritmos SJF e SRTF, calcule a média dos tempos de espera de execução dos três processos para cada um dos algoritmos
Processos (algoritmos de escalonamento - RR)
Escalonamento por chaveamento circular (RR – round-robin)
Projetado para sistemas de tempo compartilhado (interativos) Funcionamento similar ao escalonamento FIFO, mas a preempção é suportada A cada processo é atribuído um intervalo de tempo, denominado quantum, no qual ele pode executar
Se, ao final do quantum, o processo ainda estiver executando, a CPU sofrerá preempção e será dada a outro processo Se o processo foi bloqueado ou acabou antes que o quantum tenha decorrido, a CPU é chaveada para outro processo O escalonador mantém uma fila de processo executáveis, e quando um processo usa todo o seu quantum, o mesmo é colocado no final da fila
Processos (algoritmos de escalonamento - RR)
Exemplo Processo
P1
24
P2
3
P3
3
Quantum = 4 milissegundos, ordem de chegada = P1,P2 e P3 P1 0
Tempo de Execução
P2 4
P3 7
P1 10
P1 14
P1 18
P1 22
Média de tempo de espera = (6+4+7)/3 = 5,66
P1 26
30
Processos (algoritmos de escalonamento - RR)
Nenhum processo excede a utilização da CPU por mais de um quantum (quando vários processos estão competindo pela CPU)
Ou termina antes do quantum chegar ao seu limite
Ou é colocado de volta na fila dos processos prontos
O desempenho deste algoritmo depende do tamanho do quantum
Como determinar o tamanho do quantum ?
Muito grande: os processos poderão ter que esperar muito para serem executados Muito pequeno: será perdido muito tempo fazendo troca de contexto
Processos (algoritmos de escalonamento - RR)
Número de trocas de contexto varia de acordo com o tamanho do quantum
Processos (algoritmos de escalonamento - RR)
Exemplo Processo
Tempo de Execução
P1
6
P2
3
P3
1
P4
7
Quantum = 1 milissegundos, ordem de chegada = P1,P2, P3 e P4 P1 P2 P3 P4 P1 P2 P4 P1 P2 P4 P1 P4 P1 P4 P1 P4 P4 0
2
4
6
8
10
12
Média de tempo de espera = (9+6+2+10)/4 = 6,75
14
16
17
Processos (algoritmos de escalonamento - RR)
Exemplo Processo
Tempo de Execução
P1
6
P2
3
P3
1
P4
7
Quantum = 2 milissegundos, ordem de chegada = P1,P2, P3 e P4 P1 P2 P3 P4 P1 P2 P4 P1 P4 P4 0
2
4
6
8
10 12 14 16 17
Média de tempo de espera = (8+7+4+10)/4 = 7,25
Processos (algoritmos de escalonamento - RR)
Variação da média de acordo com o tamanho do quantum
Processo
Tempo
P1
6
P2
3
P3
1
P4
7
Quantum 1 2 3 4 5 6 7
Média 6,75 7,25 6,50 5,00 8,00 6,26 6,26
Processos (algoritmos de escalonamento - RR)
Exercício 1
Considere o seguinte conjunto de processos Processo
Tempo de Execução
P1
10
P2
3
P3
2
P4
6
P5
8
Considere ainda o quantum = 3 milissegundos e ordem de chegada = P 1,P2, P3, P4 e P5 Usando o algoritmo RR, represente graficamente a execução do algoritmo e calcule a média de tempo de espera de execução dos cinco processos
Processos (algoritmos de escalonamento - RR)
Exercício 1
Considere o seguinte conjunto de processos Processo
Tempo de Execução
P1
10
P2
3
P3
2
P4
6
P5
8
Considere ainda o quantum = 1 milissegundos e ordem de chegada = P 1,P2, P3, P4 e P5 Usando o algoritmo RR, represente graficamente a execução do algoritmo e calcule a média de tempo de espera de execução dos cinco processos
Processos (algoritmos de escalonamento - RR)
Exercício 1
Considere o seguinte conjunto de processos Processo
Tempo de Execução
P1
10
P2
3
P3
2
P4
6
P5
8
Considere ainda o quantum = 5 milissegundos e ordem de chegada = P 1,P2, P3, P4 e P5 Usando o algoritmo RR, represente graficamente a execução do algoritmo e calcule a média de tempo de espera de execução dos cinco processos
Processos (algoritmos de escalonamento - Prioridade)
Escalonamento por prioridade
Um número (inteiro) de prioridade é associado a cada processo Esse número pode variar, por exemplo, entre 0 e 7 ou 0 e 5000
Não há consenso em relação a qual seria a maior prioridade, se aquela que se aproxima de 0 ou a que se aproxima do maior número. Ambas são utilizadas Para a nossa disciplina, quanto menor o número, maior é prioridade. Isto é, 0 é prioridade máxima
A CPU é alocada ao processo de maior prioridade e o escalonamento pode ser preemptivo ou não preemptivo
Processos (algoritmos de escalonamento - Prioridade)
As prioridades podem ser:
Estáticas: o processo não pode mudar de prioridade ao longo da execução Dinâmicas: o processo pode mudar de prioridade ao longo da execução
SJF pode ser considerado um caso de escalonamento por prioridade, onde a prioridade é o tempo de execução do processo Neste tipo de escalonamento, pode ocorrer de processos de baixa prioridades nunca executarem
A solução é ir modificando (aumentando ou diminuindo) a prioridade dos processos à medida que os mesmos são executados
Processos (algoritmos de escalonamento - Prioridade)
A prioridade pode ser definida:
Internamente Limite de tempo de uso da CPU Requisição de memória Número de arquivos abertos Etc. Externamente
Importância do processo Departamento solicitante Outros fatores políticos Etc.
Processos (algoritmos de escalonamento - Prioridade)
Exemplo (Escalonamento por prioridade não preemptivo) Processo
Prioridade
P1
3
10
P2
1
1
P3
4
4
P4
5
5
P5
2
2
P2 P5 0 1
P1 3
Tempo de Execução
P3 13
P4 17
22
Média de tempo de espera = (3+0+13+17+1)/6 = 6,8
Processos (algoritmos de escalonamento - Prioridade)
Exercício (Escalonamento por prioridade não preemptivo)
Considere o seguinte conjunto de processos
Processo
Prioridade
Tempo de Execução
P1
3
11
P2
1
2
P3
4
4
P4
5
3
P5
2
5
Represente graficamente sua execução usando o algoritmo de escalonamento por prioridade não preemptivo e calcule a média de tempo de espera de execução dos cinco processos
Processos (algoritmos de escalonamento - Prioridade)
Exemplo (Escalonamento por prioridade preemptivo) Processo
Prioridade
P1
3
0,0
10
P2
1
2,0
1
P3
4
4,0
4
P4
5
5,0
5
P5
2
9,0
2
P1 P2 0
2
Tempo de Chegada
P1 4 5
P5 P1 9
13
P3
Tempo de Execução
P4 17
22
Tempo de Espera: P1=(13-10-0); P2=(3-1-2); P3=(17-4-4); P4=(22-5-5); P5=(11-2-9) Média do tempo de espera = (3 + 0 + 9 + 12+ 0)/5 = 4,8
Processos (algoritmos de escalonamento - Prioridade)
Exercício (Escalonamento por prioridade preemptivo)
Considere o seguinte conjunto de processos Processo
Prioridade
Tempo de Chegada
Tempo de Execução
P1
3
0,0
16
P2
1
3,0
8
P3
4
4,0
3
P4
5
8,0
2
P5
2
12,0
6
Represente graficamente sua execução usando o algoritmo de escalonamento por prioridade preemptivo e calcule a média de tempo de espera de execução dos cinco processos
Processos (algoritmos de escalonamento - Prioridade)
Exercício
Considere o seguinte conjunto de processos Processo
Prioridade
Tempo de Chegada
Tempo de Execução
P1
3
0,0
7
P2
2
3,0
4
P3
1
4,0
3
P4
2
8,0
5
Represente graficamente sua execução usando os algoritmos de escalonamento por prioridade preemptivo e não preemptivo e calcule a média de tempo de espera de execução dos cinco processos
Processos (algoritmos de escalonamento – Filas Múltiplas)
Escalonamento por Filas Múltiplas
Criado para situações em que podem ser classificados grupos distintos de processos
Interativos (foreground)
Batch (background)
Cada um destes grupos pode implementar uma estratégia distinta de escalonamento, ou a combinação de várias delas
Processos (algoritmos de escalonamento – Tempo real)
Escalonamento de Tempo Real
Sistemas de tempo real
São utilizados quando há rigidez no gerenciamento do tempo de execução do processo São exemplos de sistemas de tempo real:
Sistema de controle aéreo
Sistema de piloto automático em uma aeronave
Sistema de controle de segurança em um reator nuclear
Difere dos sistemas de tempo compartilhado:
Tempo compartilhado: resposta o mais rápido possível
Tempo real: resposta sempre no tempo certo
Processos (algoritmos de escalonamento – Tempo real)
Escalonamento de Tempo Real
A computação em tempo real pode ser dividida em dois tipos:
Tempo Real Crítico (Hard real-time)
Há prazos absolutos que devem ser cumpridos Precisa, obrigatoriamente, completar os processos críticos dentro de um período de tempo estabelecido Quando o sistema recebe uma requisição deste tipo pode: (a) aceitar garantindo o término no tempo solicitado. (b) rejeitar, admitindo ser “impossível”
Tempo Real Não Crítico (Soft real-time)
O descumprimento ocasional de um prazo é indesejável, contudo tolerável Os processos críticos precisam receber maior prioridade que os demais, e devem manter essa prioridade até serem finalizados
Processos (algoritmos de escalonamento – Tempo real)
Escalonamento de Tempo Real Um sistema de tempo real é dito escalonável se for possivel realizar todos os eventos em um intervalo limite de tempo Os algoritmos de escalonamento de tempo real podem ser:
Estáticos
Tomam suas decisões de escalonamento antes de o sistema começar a executar Só funciona quando há prévia informação perfeita disponível sobre o trabalho necessário a ser feito e os prazos que devem ser cumpridos
Dinâmicos
Tomam suas decisões em tempo de execução
Threads
Threads
Threads
O modelo de processos estudado supõe o uso de apenas uma thread por processo Cada processo tem o seu espaço de endereçamento e um único thread de controle Contudo, frequentemente há situações em que é desejável ter múltiplos threads de controle no mesmo espaço de endereçamento executando em pseudo paralelo, como se fossem processos separados
Exceto pelo espaço de endereçamento compartilhado Intuitivamente, threads são como processos dentro de outo processo (são linhas/fluxo de execução)
Mas, quando é desejável utilizar mais de uma thread?
Threads
Exemplo 1: Processador de textos
Threads
Exemplo 2: Servidor Web
Threads (modelo clássico)
O modelo de processos é baseado em dois conceitos independentes:
Agrupamento de recursos: espaço de endereçamento, arquivos abertos, etc. (todos os recursos necessários para realizar alguma tarefa). Aglutinar estes recursos na forma de um processo facilita o gerenciamento destes recursos. Execução: representa o thread de execução do processo, o qual contém:
Um contador de programa que aponta para a próxima instrução a ser executada Registradores, que contém as variáveis de trabalho atuais A pilha que traz a história da execução, com uma estrutura para cada rotina chamada mas ainda não terminada
Apesar de threads serem executadas em processos, ambos são conceitos diferentes e podem ser tratados separadamente
Processos são usados para agrupar recursos Threads são as entidades escalonadas para usar a CPU
Threads (modelo clássico)
O modelo de threads permite que múltiplas execuções ocorram no mesmo ambiente de processo, com um grande grau de independência uma da outra Threads (também chamadas de processos leves) são linhas de execução, e compreendem:
Id: identificador da thread
Endereço da próxima instrução a ser executada
Conjunto de registradores em uso
Uma pilha de execução
Threads compartilham com outras threads recursos, como:
Trecho de código
Dados
Arquivos abertos
Multithread é o termo usado para descrever a situação em que é permitido a existência de múltiplos threads em um processo
Threads (modelo clássico)
Uma thread é uma maneira de um programa dividir a si mesmo em duas ou mais tarefas simultâneas Processo simples vs. Multithreads
Threads (modelo clássico)
Processo simples vs. Multithreads
Threads (modelo clássico)
Itens por processo vs. Itens por thread
Threads (vantagens)
Tempo de resposta
Compartilhamento de recursos
Por padrão as threads compartilham: memória e qualquer recurso alocado pelo processo ao qual são subordinadas Não é necessária a alocação de mais recursos no sistema
Economia
Uma aplicação interativa pode continuar sendo executada se parte dela está bloqueada, ou executando uma operação lenta
É mais econômico criar e trocar o contexto das threads
Utilização de arquiteturas multiprocessadas
Cada thread pode ser executada de forma paralela, em processadores distintos
Threads (gerenciamento)
Existem dois modos principais de implementar threads
Threads no espaço de usuário
São admitidas no nível do usuário e gerenciadas sem o suporte do núcleo (kernel)
Threads (gerenciamento)
Existem dois modos principais de implementar threads
Threads no núcleo (kernel)
São admitidas e gerenciadas diretamente pelo sistema operacional Quase todos os sistemas operacionais admitem threads de kernel
Exemplos: Windows XP, Linux, Mac OS X, Solaris
Threads (gerenciamento)
Implementação híbridas
Tenta combinar as vantagens dois dois modos anteriores
Modo usuário: rápida criação e chaveamento entre threads Modo núcleo: o processo todo não é bloqueado pelo bloqueio de uma thread
A idéia é utilizar algumas threads de núcleo e multiplexar threads de usuários sobre elas
O usuário decide quantas threads utilizar, tendo uma maior flexibilidade
Threads (modelos de multithreading)
Modelo N para 1
N threads de usuários para 1 thread do núcleo (thread de sistema) O gerenciamento das threads é realizado pela biblioteca de threads no nível de usuário Se um thread fizer uma chamada ao sistema que bloqueia o processamento, todo o processo será bloqueado
Utilizado em sistemas que não suportam threads em nível de sistema
Alguns sistemas operacionais que suportam este modelo: Solaris e Linux
Threads (modelos de multithreading)
Modelo 1 para 1
Associa cada thread de usuário para 1 thread do núcleo Provê maior concorrência do que o modelo anterior, permitindo que outra thread seja executada quando uma thread faz uma chamada bloqueante Permite que várias threads sejam executadas em paralelo em multiprocessadores Desvantagem: a criação de um thread de usuário é mais rápida do que a criação de uma thread de núcleo Alguns sistemas operacionais que suportam este modelo: versões atuais do Linux, Windows 95/98/NT/2000.
Threads (modelos de multithreading)
Modelo N para M
N threads de usuário para M threads do núcleo O número de threads de núcleo pode ser específico a determinada aplicação ou a determinada máquina Quando um thread realiza uma chamada de sistema bloqueante, o escalonador do sistema operacional pode escolher outra thread do mesmo processo Alguns sistemas operacionais que suportam este modelo: Solaris 2, Windows NT/2000 (com o Pacote ThreadFiber)
Threads (bibliotecas de threads)
Uma biblioteca de thread fornece ao programador uma API (application programming interface) para a criação e gerenciamento de threads Existem duas maneiras de implementar bibliotecas
Fornecer uma biblioteca no espaço do usuário, sem suporte do núcleo Fornecer uma biblioteca no nível do núcleo, com suporte direto do sistema operacional
As três bibliotecas de threads mais comuns são:
POSIX Pthreads (nível de usuário ou de núcleo)
Win32 (nível de núcleo)
Java (no nível de usuário, mas usa sempre a biblioteca do sistema operacional hospedeiro)
Threads (escalonamento de threads)
Em sistemas operacionais que admitem a criação de threads no nível do núcleo, são as threads que são escalonadas, e não os processos As threads em nível de usuário não são conhecidas pelo sistema operacional Nas implementações dos modelos N para 1 ou N para M, a biblioteca de suporte a threads (sistema supervior do processo) escalona as threads em nível de usuário
Esse esquema é conhecido como Escopo de Disputa do Processo (Process Contention Scope – PCS) Pois a disputa pela CPU ocorre entre as threads pertencentes ao mesmo processo
Threads (escalonamento de threads)
As threads no nível do núcleo são escalonadas para o uso da CPU Esse esquema é conhecido como Escopo de Disputa do Sistema (System Contention Scope – SCS) A disputa pela CPU com escalonamento SCS ocorre entre todas as threads no sistema Os sistemas operacionais que utilizam o modelo 1 para 1 (Windows XP, Solaris 9 e Linux) escalonam as threads usando apenas o SCS
Normalmente, o PCS é realizado de acordo com a prioridade, o escalonador seleciona a thread executável com a maior prioridade para execução
As prioridades das threads do usuário são definidas pelo programador
