Resumo SO 1¦ GQ - Cap.06

Prévia do material em texto

CAPÍTULO 6:
 
Scheduling de CPU. 
Mas o que danado é Scheduling? 
É a função de selecionar entre os muitos processos na memória e que possuem o status de 
prontos, qual deles será despachado para CPU. 
E em que momentos isso acontece? 
Bem, o Scheduling pode acontecer quando um processo: 
1. Muda de executando para o estado de espera. 
2. Muda de executando para o estado de pronto. 
3. Muda do estado de espera para pronto. 
4. Termina. 
OBS.1: Scheduling ocorrido em 1 e 4 é Não-Preemptivo ou cooperativo. 
OBS.2:
 
Os demais Scheduling são Preemptivos. 
Não entendeu as observações? Sem estresse! Por enquanto saiba que ser Preemptivo é sofrer 
interrupção. E o outro é o oposto disso. Mais adiante entraremos em detalhes. 
Mas para que serve tudo isso? 
Para o seguinte: 
1. Manter a CPU ocupada o máximo possível pelos processos de usuários (Utilização da 
CPU) 
2. Executar um certo número de processos numa certa unidade de tempo (Throughput) 
3. Garantir a execução numa certa faixa de tempo para processos particulares - Batch 
(Turnaround time) 
4. Minimizar o total de tempo que um processo pode ficar a espera na fila de prontos 
( Tempo de espera). 
5. Garantir que o tempo decorrido entre uma requisição e a resposta desta requisição 
seja o mais breve possível ( Tempo de resposta). 
E de forma geral, como isso acontece? 
Da seguinte forma: 
1. O Módulo Dispatcher dá o controle da CPU para o processo selecionado pelo 
Scheduler; 
2. Isto envolve: 
a) Chaveamento de contexto; 
b) Chaveamento para o modo usuário; 
c) Reinicio do processo; 
É interessante saber que o termo Dispatch Latency é designado para se referir ao tempo 
utilizado pelo Dispatcher para realizar o chaveamento entre o processo velho e o novo 
processo. 
E como o SO participa dessa estória? 
Através da utilização de políticas e mecanismos que determinam a ordem de execução dos 
processos, onde: 
POLÍTICA: método através do qual decisões são tomadas. 
MECANISMO: meios através dos quais uma política pode ser atingida. 
ESTRATÉGIAS: 
Preemptiva: significa que um processo poder ser suspenso temporariamente (vai para a fila de 
prontos) e um outro processo ocupa o seu lugar na CPU. 
Não-Preemptiva: É justamente o oposto: chegou na CPU, ele não arreda o pé de lá!!! 
Que tal então conhecermos essas políticas? Vamos lá! 
1. Política First-Come, First-Served (FCFS) 
Em bom português: o primeiro que chega, é o primeiro a ser servido. 
Ex.: 
Atenção: Para demonstrar a ordem de execução dos processos na CPU, utiliza-se um diagrama 
chamado Diagrama de Gantt. 
PROCESSO
 
TEMPO DE EXECUÇÃO
 
P1 24 
P2 3 
P3 3 
 
Suponha que os processos cheguem na seguinte ordem: P1 , P2 , P3 . 
O diagrama de Gantt para este caso é: 
 
- Tempo de espera: P1 = 0; P2 = 24; P3 = 27 
- Tempo médio de espera: (0 + 24 + 27)/3 = 17 
- Não se preocupe agora com esses tempos. Mais adiante entraremos em detalhes. 
 
Ex.2: 
Suponha que os processos cheguem na seguinte ordem P2 , P3 , P1 . 
O diagrama de Gantt é: 
 
- Tempo de espera para P1 = 6; P2 = 0; P3 = 3 
- Tempo médio de espera: (6 + 0 + 3)/3 = 3 
- Neste caso a política é mais adequada do que para o caso anterior. 
- Observa-se o efeito Comboio, quando processos curtos ficam atrás de um processo longo 
2. Shortest-Job-First (SJF): 
Esta política baseia-se na seleção do processo que possui o menor tempo previsto para o seu 
próximo surto de utlização de CPU. 
Possui duas estratégias: 
Não-Preemptiva – Uma vez dada a CPU para o processo ele não pode ser interrompido até 
completar seu surto de utilização da CPU. 
Preemptiva – se um novo processo chegar com um tempo menor que o tempo restante do 
processo corrente em execução, este processo é interrompido. Esta política é conhecida como 
o Shortest-Remaining-Time-First (SRTF). 
SJF é ótimo – pois dá um tempo médio de espera mínimo para um dado conjunto de 
processos. 
Ex.: 
PROCESSO TEMPO DE CHEGADA TEMPO DE SURTO 
P1
 
0
 
7
 
P2 2 4 
P3 4 1 
P4
 
5
 
4
 
a) SJF (Não-Preemptivo): 
 
Tempo médio de espera = (0 + 6 + 3 + 7) / 4 = 4 
b) SJF (Preemptivo): 
 
Tempo de espera médio = (9 + 1 + 0 + 2) / 4 = 3 
3. Round Robin (RR - Revezamento): 
Cada processo recebe uma pequena unidade de tempo para usar a CPU (quantum), 
usualmente entre 10 e 100 milissegundos. Decorrido este tempo, o processo é interrompido e 
retorna para o final da fila de prontos. 
Se existem n processos na fila de prontos e o tempo do quantum é q, então cada processo tem 
1/n de tempo da CPU em pedaços de q unidade a cada vez que precisar de CPU. Nenhum 
processo espera mais do que (n-1)q unidades de tempo. 
Quanto ao desempenho: 
- q grande Þ FCFS (FIFO) 
- q pequeno Þ q deve ser grande o suficiente em relação ao tempo gasto pelo Dispatcher na 
 troca de contexto dos processos, caso contrário overhead será alto. 
Ex.: RR com Tempo de Quantum = 20 
PROCESSO TEMPO DE SURTO 
P1 53 
P2
 
17
 
P3 68 
P4 24 
 
O diagrama de Gantt é: 
 
Normalmente, o tempo de retorno médio é maior que na política SJF, mas o de resposta é 
melhor. 
4. Scheduling por Prioridade: 
A prioridade é um número inteiro associado a cada processo. 
A CPU é alocada para o processo de maior prioridade (menor inteiro =maior prioridade). 
Pode ser Preemptivo ou Não-Preemptivo. 
 
SJF pode ser vista como uma política de prioridade, onde a prioridade é baseada no valor 
previsto para o próximo surto de CPU. 
Problema: Starvation – processos de baixa prioridade podem nunca executar. 
Solução: Aging – Com o tempo, aumentar progressivamente a prioridade do processo. 
SE LIGA NISSO:
 
É interessante aprofundarmos nossos conhecimentos em três conceitos de tempo, muito 
importantes para o Scheduling: 
1) Tempo de Espera: 
É TODO o tempo em que o processo permanece na fila de prontos. 
2) Tempo de Resposta: 
Trata-se do instante em que o processo COMEÇOU a executar, sem contar o tempo 
que ele passou na fila de prontos. 
3) Tempo de Retorno (ou Execução*): 
É o tempo em que o processo TERMINA a execução menos o tempo em que ele 
chegou na fila de prontos. 
*Confirmar se o tempo de execução é realmente sinônimo de tempo de retorno com o 
seu instrutor, pois não conseguimos esclarecer essa dúvida! 
Bom, vamos começar entendendo o tempo de espera através de um exemplo: 
Considere o quadro abaixo: 
PROCESSO TEMPO DE SURTO TEMPO DE CHEGADA 
P1
 
10
 
0
 
P2 1 3 
P3 3 4 
P4
 
1
 
5
 
P5
 
5
 
8
 
Vamos calcular esse tempo, utilizando a política SJF, primeiro sem preempção e depois com 
preempção: 
a) SEM-PREEMPÇÃO: 
Primeiro vamos desenhar o diagrama de Grant. Lembre-se que nesse caso, uma vez 
que o processo começa a executar, ninguém pode tirá-lo de lá. 
Assim: 
 
Ora, se eu quero o tempo que P1 passou na fila de prontos, este logicamente será 0, já 
que ele não esperou nada para ser executado. Já com P2 a estória é outra: note que a 
chegada dele na fila foi no instante 3 mas ele só será servido no instante 10 que é o 
tempo que P1 acaba. Logo ele ficou esperando 7 unidades de tempo na fila (10 – 3). 
E assim vai: P3 espera 8 (12 – 8), P4 é 6 (11 – 5) e P5 é 7 (15 – 8). 
b) COM-PREEMPÇÃO: 
Lembrando novamente: nesse caso, se no momento em que um processo estiver 
executando chegar um outro, o processo em execução é suspenso(volta para fila de 
prontos) para ser retomado posteriormente. 
Para sabermos o tempo de espera aqui é só observamos o tempo que ele executou 
antes de ser suspenso e subtraí-lo do tempo emque o processo retoma a sua 
execução. Compreendeu? 
Mais uma vez o diagrama de Grant: 
 
 
Vamos lá: 
P1 executou até 3 antes de ser suspenso e depois retornou no instante 13, logo sua 
espera foi de 10 (13 -3). Já P2 é 0, pois foi atendido de imediato e não precisou esperar 
nada. O P3 espera 1 (6 -5) e os dois últimos são 0, a exemplo de P2. Muito simples, 
não? 
Da mesma forma, vejamos agora o tempo de resposta: 
Considere o quadro abaixo: 
PROCESSO
 
TEMPO DE SURTO
 
TEMPO DE CHEGADA
 
P1 9 0 
P2 1 1 
P3
 
4
 
4
 
P4 2 5 
P5 6 7 
 
 P1 P2 P4 P3 P5 
0
 
10 11
 
12
 
15
 
20
 
 P1 P2 P3 P4 P3 P3 P5 P1 
 0
 
 3
 
4
 
5
 
 6
 
 7
 
8
 
13
 
20
 
Deixando a teoria já mencionada ainda mais explícita, diríamos que para conhecermos o 
tempo de resposta basta nos perguntarmos qual o instante de chegada do processo e o 
instante em que ele é REALMENTE servido. Tendo assim feito, pegamos esse último e 
subtraímos do primeiro encontrando a reposta (gostou do trocadilho? Hehehe...). 
Vamos observar como ficaria então, no SJF com preempção (não analisaremos aqui o sem-
preempção, já que os valores serão idênticos aos do tempo de espera também sem- 
preempção): 
a) COM-PREEMPÇÃO: 
Diagrama de Gantt: 
O Cálculo dos tempos fica assim: 
P1 = 0 – 0 = 0 
P2 = 1 – 1 = 0 
P3 = 4 – 4 = 0 
P4 = 5 – 5 = 0 
P5 = 16 – 7 = 9 
Ilustremos em nosso último exemplo, o tempo de retorno: 
 Considere o quadro abaixo: 
PROCESSO TEMPO DE SURTO TEMPO DE CHEGADA 
P1 9 - 
P2
 
1
 
-
 
P3 4 - 
P4 2 - 
P5
 
6
 
-
 
Agora utilizaremos as políticas SJF com preempção e Round Robin com quantum igual a 2. 
a) SJF COM-PREEMPÇÃO: 
Bem, nesse caso, como todos os processos chegaram ao mesmo tempo para serem 
executados, o tempo de retorno será o tempo em que eles acabam de serem 
executados. 
 P1 P2 P1 P3 P4 P3 P1 P5 
0
 
3
 
4
 
5
 
6
 
7
 
8
 
13
 
20
 
 
Diagrama de Gantt: 
Logo, como P1 acaba a execução em 22, este é o seu tempo de retorno. Para os 
demais se dará da mesma forma: P2 = 1 ; P3 = 7 ; P4 = 3 ; P5 = 13. 
b) RR com Q = 2: 
Organizando os processos no diagrama: 
P1 = 9 7 5
 
3 
P3 = 4 2
 
P5 = 6 4
 
2 
Mas e se fossem dados os tempos de chegada para cada processo? 
Vejamos então como ficaria: 
PROCESSO TEMPO DE SURTO TEMPO DE CHEGADA 
P1 9 0 
P2
 
1
 
1
 
P3 4 4 
P4 2 5 
P5 6 7 
 
a) SJF COM-PREEMPÇÃO: 
Bem, como falamos antes, o tempo de retorno é o tempo em que o processo ACABOU 
de executar menos o instante de chegada. 
 P2 P4 P3 P5 
0
 
1
 
3
 
7
 
13
 
 P1 
 
22
 
 P1 P2 P3 P4 P5 P1 P3 P5 
0
 
2
 
3
 
5
 
7
 
9
 
11
 
13
 
15
 
 P1 P5 P1 P1 
17
 
19
 
21
 
22
 
Da mesma forma que no SJF, é 
simples ver os tempos de retorno: 
P1 = 22 
P2 = 3 
P3 =13 
P4 = 7 
P5 = 19 
 
Diagrama de Grant: 
 
Organizando os processos no diagrama: 
P1 = 9 8
 
6 
P3 = 4 3
 
P5 = 6 
E os tempos de retorno são: 
P1 = 16 
P2 = 2 -1 =1 
P3 = 10 -4 = 6 
P4 = 7 – 5 = 2 
P5 = 22 – 7 = 15 
 
b) RR com Q = 2: 
Organizando os processos no diagrama: 
Para entendermos como os processos se comportam é preciso sabermos que uma fila de 
prontos é do tipo FIFO(o primeiro a entrar é o primeiro a sair). 
Logo, P1 chega na fila, sai dela (só tem ele) e executa 2 (restam 7). 
P2 já tinha chegado em 1 e ido para a fila. Ele sai e executa até 3 enquanto P1 retorna. 
P2 já era! 
P3 chega em 4, como estamos em 3, P1 volta, executa mai 2 (Restam 5) e P3 fica na fila. 
Em 5 chega P4, como P3 está na frente ele sai excuta 2 (Restam 2) e em seguida P4 e retirado 
da fila e executa 2. 
P4 já era! 
Note que quando P3 sai, é justamente o instante de chegada de P5. Logo, primeiro vai P5 para 
fila e depois P3, ambos atrás de P1. 
 P1 P2 P1 P3 P4 P3 P1 P5 
0
 
1
 
2
 
4
 
5
 
7
 
10
 
16
 
22
 
 P1
 
 P2
 
 P1
 
 P3
 
 P4
 
 P1
 
 P5
 
 P3
 
0
 
2
 
3
 
5
 
7
 
9
 
11
 
13
 
15
 
 P1
 
 P5
 
 P1
 
 P5
 
17
 
19
 
20
 
22
 
 
Seguindo a fila agora, P1 sai e executa mais 2 (Restam 3). Volta para fila e P5 sai e excuta 2 
(Restam 4) e volta. 
P3 entra e executa 2. 
P3 já era! 
P1 sai e executa mais 2 (Restam 1) e volta. 
P5 sai e executa mais 2 (Restam 2) e volta. 
Por fim, P1 sai e executa 1. 
P1 já era! 
Agora sai P5 e excuta seus 2 restantes. 
P5 já era! 
E ai cansou? 
Seja como for, navegar é preciso! ;) 
Fechamos agora exibindo os tempos de retorno: 
P1 = 20 
P2 = 3 -1 = 2 
P3 = 15 – 4 = 11 
P4 =9 – 5 = 4 
P5 = 22 -7 = 15 
DICA:
 
que tal você implementar esses algoritmos? Não tem paciência? Bom... 
Deixa para S.O.II !!! hum..quer saber? Esquece, tô brincando. Você é quem sabe! 
 P3 P5 P1 
 P1 P3 P5
 
 P5 P1 P3 
 P5
 
 P1
 
Abordemos agora, alguns tópicos complementares ao assunto: 
1. Escalonamento por Múltiplas Filas: 
- A fila de prontos é particionada em filas separadas: 
Ex.: 
 foreground (interativo) 
 background (batch) 
- Cada fila tem seu próprio algoritmo de Scheduling: 
Ex.: 
foreground – RR 
background – FCFS 
- Deve ser realizado Scheduling entre as filas: 
- Scheduling de prioridade fixa; isto é, servido todos os processos de foreground então serve-
se os de background. Possibilidade de Starvation. 
- Time slice: cada fila recebe um certo tempo de CPU para distribuir entre os seus processos; 
Por exemplo: 
80% para foreground em RR. 
20% para background em FCFS. 
2. Escalonamento por Múltiplas Filas com Realimentação: 
- Um processo pode ser movido entre as várias filas; 
- Aging
 
pode ser implementado para evitar a estagnação (pesquise!). 
- A política Escalonamento por Múltiplas Filas com Realimentação para ser 
 implementada necessita da definição dos seguintes parâmetros: 
a) Número de filas; 
b) Algoritmos de escalonamento para cada fila; 
c) Métodos usados para determinar quando atualizar os atributos de escalonamento do 
processo; 
d) Métodos usados para determinar qual fila um processo entrará quando aquele 
processo necessitar de serviços; 
 
Ex.: 
 
Três filas: 
Q0 – tempo do quantum 8 millisegundos 
Q1 – tempo do quantum 16 millisegundos 
Q2 – FCFS 
- Scheduling: 
Um novo processo sempre entra em Q0 a qual é administrada no modelo RR. Quandoele 
ganha a CPU, recebe 8 ms. Se não liberar a CPU nestes 8 ms, o processo é movido para a fila 
Q1. 
Em Q1 o processo é outra vez servido e recebe 16 ms adicionais. Se ele mais uma vez não 
liberar a CPU, ele é preemptado e movido para a fila Q2. 
3. Schedule de Múltiplos-Processadores: 
- O Scheduling de CPU é mais complexo quando múltiplas CPUs estão disponíveis; 
- Ambientes multiprocessadores com processadores homogêneos; 
- Compartilhamento de carga; 
- Multiprocessamento Simétrico (SMP) – cada processador encarrega-se de realizar 
 suas próprias decisões de Scheduling; 
- Multiprocessamento Assimétrico – apenas um processador (Mestre) acessa a fila de 
 processos prontos, aliviando a necessidade de compartilhamento de dados; 
4. Schedule de Tempo Real: 
Sistemas de tempo real crítico – requerido quando tarefas devem ser processadas dentro de 
um período de tempo adequado as suas características 
- Reserva de recursos: Exige conhecimento destes por parte do SO. 
Sistemas de tempo real não crítico – requer que processos críticos recebam prioridades 
maiores que os não críticos (estude isso melhor no livro!).; 
- Pode causar alocação injusta, causando Starvation; 
- Os processos de tempo real não podem ter suas prioridades degradadas; 
- Tempo de latência do Dispatch deve ser o mínimo possível; 
5. Schedule de Thread: 
Scheduling Local (usuário) – Como os threads de usuário são criados e geridos pelas próprias 
aplicações e como não há ciência por parte do SO das características desses threads ficam por 
parte da aplicação proprietárias dos threads a tarefa de schedulá-los. 
Scheduling Global (kernel) – Como os threads são criados pelo próprio kernel nada mais 
natural que utilizar o Schedule do próprio kernel que é o global para decidir qual o próximo 
thread associado ao kernel que será selecionado.