Escalonamento
Prof. Alexandre Monteiro
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Mais uma vez: O que é um SO?

É uma Máquina Estendida
•Oculta os detalhes complicados que têm quer
ser executados
•Apresenta ao usuário uma máquina virtual,
mais fácil de usar

É um Gerenciador de Recurso
•Cada programa tem um tempo com o recurso
- Ex.: compartilhamento de CPU
•Cada programa tem um espaço no recurso
- Ex.: compartilhamento de memória
História dos SO’s

Primeira geração: 1945 - 1955
•Válvulas, painéis de programação

Segunda geração: 1955 - 1965
•transistores, sistemas em lote

Terceira geração: 1965 – 1980
•CIs (circuitos integrados) e multiprogramação

Quarta geração: 1980 – presente
•Computadores pessoais

Hoje: onipresença – computação ubíqua
Mono vs. Multi




SO Monoprogramado/tarefa ou Multiprogramado/tarefa: são os
SO que executam apenas um programa do usuário de cada vez ou
que executam dois ou mais programas aparentemente em
simultâneo. Este é o conceito de Paralelismo Concorrente.
SO Monoprocessamento ou Multiprocessamento: são os SO que
executam vários processos compartilhando memória utilizando
apenas um processador (mono) ou vários (multi) processadores,
este é o conceito de Paralelismo Real.
SO Monousuário ou Multiusuário: o SO controla e considera
apenas um usuário por vez ou o SO identifica usuários diferentes
por suas contas (username e senha) e permite perfis diferentes.
SO Monothread ou Multithread: um processo um thread ou um
processo dividido em vários threads.
Registradores




Registradores de propósito geral: armazena variáveis
importantes e resultados temporários
Contador de Programas: contém o endereço de memória
da próxima instrução a ser buscada. Depois que busca é
atualizado para apontar a próxima instrução.
Ponteiro de Pilha: aponta para o topo da pilha atual na
memória. A pilha contém uma instrução
PSW (program status word – palavra de estado do
programa): contém os bits de códigos de condições de
instruções de comparação, pelo nível de prioridade da CPU.
Conceitos Básicos
Chamadas ao Sistema (System Call)

Modo usuário:
•Aplicações não têm acesso direto aos
recursos da máquina, ou seja, ao hardware;
•Quando o processador trabalha no modo
usuário, a aplicação só pode executar
instruções sem privilégios, com um acesso
reduzido de instruções;
•Por que? Para garantir a segurança e a
integridade do sistema;
7
Conceitos Básicos
Chamadas ao Sistema (System Call)

Modo Kernel:
•Aplicações têm acesso direto aos recursos da
máquina, ou seja, ao hardware;
•Operações com privilégios;
•Quando o processador trabalha no modo
kernel, a aplicação tem acesso ao conjunto
total de instruções;
•Apenas o SO tem acesso às instruções
privilegiadas;
8
Conceitos Básicos
Chamadas de Sistema

TRAP: instrução que permite o acesso ao modo kernel;

Exemplo:
•Instrução do UNIX:
count = read(fd,buffer,nbytes);
Arquivo a ser lido
Bytes a serem lidos
Ponteiro para o Buffer
O programa sempre deve checar o retorno da chamada de
sistema para saber se algum erro ocorreu!!!
9
Chamadas ao Sistema
Endereço
0xFFFFFFFFF
Retorno
TRAP
5 Colocar o código para
read no registrador
6
READ
10
4
Espaço
do
Usuário
Biblioteca do
Procedimento
3
2
1
Incrementa SP 11
Comando read
Empilha fd
Empilha &buffer
Empilha nbytes
Chamada ao
Procedimento
READ
9
Tabela de ponteiros para Chamadas
Kernel
SO
Endereço 0
Dispatch
7
8
Manipulador
de Chamadas
10
Introdução a Processos

Um processo é formado por três partes
•Contexto de Hardware
•Contexto de Software
•Espaço de endereçamento


Estas três partes mantêm todas as informações
necessárias à execução de um programa
Quando um processador troca de processo
caracteriza uma mudança de Contexto de
Execução
Estrutura de um Processo
Processo: Estrutura Detalhada
Estado do Processo

Para haver o compartilhamento da CPU em um sistema
multiprogramável, os processos passam por diferentes
estados ao longo do seu processamento
• A troca de estado ocorre em função de eventos gerados pelo
próprio processo (voluntário) ou pelo SO (involuntário)

Os estados em que um processo pode se encontrar
variam de sistema para sistema mas, de uma maneira
geral, pode-se citar:
• Executando (Running)
• Pronto (ready)
• Bloqueado (blocked) – Também conhecido com Espera (Wait)
• Terminado (exit)
Transições Possíveis entre Estados
PCB - Bloco de Controle do Processo

Algumas informações típicas que o PCB possui são:
• Identificador de processo (pid);
• Estado atual do processo;
• Cópia do conteúdo do registrador contador de programa (PC –
Program Counter);
• Cópia do conteúdo dos demais registradores do processador;
• PID do processo pai (parent process);
• Ponteiro para a pilha;
• Tempo em que o processo iniciou;
• Tempo utilizado do processador;
• Informações sobre diretório raiz e de trabalho.

OBS: Os PCBs de todos os processos residem na
memória principal em uma área exclusiva do SO
Troca de Contexto
Término de Processos
Condições que levam ao término de processos
1.
Saída normal (voluntária)
2.
Saída por erro (voluntária)
3.
Erro fatal (involuntário)
4.
Cancelamento por um outro processo
(involuntário)
18
Threads (ou Processo Leve)

Thread é uma unidade básica de utilização da CPU, que consiste em:
1. Apontador de instruções
2. Conjunto de registradores
3. Espaço de pilha

Uma Thread compartilha com Threads irmãs:
1. Área de código
2. Área de Dados
3. Recursos do SO (coletivamente conhecidos como tarefas)

Um Processo tradicional é equivalente uma tarefa com uma única
Thread.
Interação entre Threads
TCB 1
TCB 2
Ambiente Multithread

Cada thread possui seu próprio contexto de HW, porém
divide o mesmo contexto de SW e espaço de
endereçamento com os demais threads do processo
Thread


Semelhante a processos, threads são implementados
internamente através de uma estrutura de dados
Bloco de Controle de Thread (Thread Control Block - TCB)
•O TCB armazena, além do contexto de HW,
dados exclusivos sobre o thread, como
prioridade e estado de execução
•PCB X TCB ?
Vantagens de Mutithreading



Tempo de criação/destruição de threads é inferior ao
tempo de criação/destruição de processos
Chaveamento de contexto entre threads é mais rápido em
tempo que chaveamento entre processos
Como threads compartilham o descritor do processo que as
contem, elas dividem o mesmo espaço de endereçamento o
que permite a comunicação por memória compartilhada,
sem interação com o núcleo
Comunicação Interprocessos



Os processos podem precisar trocar informações entre eles
ou podem solicitar a utilização de um mesmo recurso
simultaneamente, como arquivos, registros, dispositivos de
E/S e memória.
O compartilhamento de recursos entre vários processos
pode causar situações indesejáveis e, dependendo do caso,
gerar o comprometimento da aplicação.
O Sistema Operacional tem a função de gerenciar e
sincronizar processos concorrentes, com o objetivo de
manter o bom funcionamento do sistema.
Comunicação Interprocesso
Condições de Disputa/Corrida
Dois processos querem ter acesso simultaneamente à memória
compartilhada (Ex: spool de Impressão )
25
Regiões Críticas




Para se evitar uma condição de corrida é preciso definir
métodos que proíba que mais de um processo acesse uma
determinada área de memória compartilhada ao mesmo
tempo.
Esses métodos são conhecidos como exclusão mútua ou
MUTEX (MUTual EXclusion).
A parte do programa no qual o processo acessa memória
compartilhada é chamada seção crítica ou região crítica.
Dessa forma, a solução para se evitar uma condição de
corrida seria organizar os problemas de tal forma que
nenhum de dois ou mais processos estivessem em suas
regiões críticas ao mesmo tempo.
Regiões Críticas (2)
Espera Ativa
Exclusão mútua usando regiões críticas
proposta de exclusão mútua na qual, um processo quando está acessando
sua região crítica, outro processo que deseja entrar também em região
crítica fica aguardando.
27
Algoritmos de Exclusão Mútua

MUTEXES

Semáforo

Monitores

Produtor x Consumidor

Dormir x Acordar

Troca de Mensagens

Barreiras

Jantar dos Filósofos

Barbeiro Sonolento

Leitor xEscritor
Objetivos do Escalonamento





Maximizar a utilização do processador
Maximizar o nº de processos executados por unidade de
tempo (throughput)
Minimizar o tempo total de execução de um processo
(turnaround)
Minimizar o tempo de espera (na lista de processos aptos)
Minimizar o tempo de resposta decorrido entre a requisição
e sua realização
Características de Escalonamento

Justiça (fairness)
• Todos os processos têm chances iguais de uso dos processador

Eficiência
• Taxa de ocupação do processador ao longo do tempo

Tempo de Resposta
• Tempo entre a ocorrência de um evento e o termino da ação
correspondente

Turnaround
• “Tempo de resposta” para usuários em batch
• Minimizar o tempo que usuários batch devem esperar pelo
resultado

Throughput
• No. de “jobs” (processos) executados por unidade de tempo
Situações típicas para execução do
escalonador

Depende se o escalonador é preemptivo ou não- preemptivo, se considera
prioridades ou não:

Sempre que a CPU estiver livre e houver um processo apto para executar

Criação e término de processos

Um processo de mais alta prioridade ficar pronto para executar

Interrupção de tempo
• Processo executou por um período de tempo máximo permitido

Interrupção de E/S

Interrupção de Falta de Página em Memória
• Endereço acessado não está carrego na memória (memória virtual)

Interrupção por erro
Chaveamento de Contexto
(Dispatcher)
Níveis de escalonamento

Longo Prazo

Médio Prazo

Curto Prazo
Diagrama de Escalonamento
Filas de Escalonamento

High-level (Longo Prazo)
• Decide quantos programas são admitidos no sistema
• Aloca memória e cria um processo
• Controla a long-term queue

Short-term (Curto prazo)
• Decide qual processo deve ser executado
• Controla a short-term queue

I/O (Médio prazo)
• Decide qual processo (com I/O) pendente deve ser tratado pelo
dispositivo de I/O
• Controla a I/O queue
Filas de Escalonamento
Short-term
scheduling
Process
request
Longterm
queue
High-level
scheduling
Interrupt
of process
Interrupt
from I/O
Interrupt
Handler
Shortterm
queue
CPU
I/O
I/O
queue
I/O
I/O
queue
I/O
I/O
queue
FIM
I/O scheduling
Algoritmos de Escalonamento

Algoritmos Não-Preemptivos (cooperativos)
• First-In-First-Out (FIFO) ou First-Come-First-Served (FCFS)
• Shortest Job First (SJF) ou Shortest Processo Next (SPN)

Algortimos Preemptivos
• Round Robin (Circular)
• Baseado em Prioridades
• Híbridos
- Partições de Lote (Batch)
- MFQ - Multiple Feedback Queue

Existem outros algoritmos de escalonamento
• High Response Ratio Next (HRRN)
• Shortest Remaining Time (SRT)
• Ect...
Escalonamento


Preemptivo
Permite a suspensão temporária de processos
Quantum ou time-slice: período de tempo durante o qual
um processo usa o processador a cada vez
Preempção
T12
mP1
T11
1
T0
41 51
T22
70
T0
90
121
t
Quantum


Quando uma tarefa recebe o processador, o núcleo ajusta um
contador de ticks que essa tarefa pode usar, ou seja, seu quantum
é definido em número de ticks.
A cada tick, o contador é decrementado; quando ele chegar a
zero, a tarefa perde o processador e volta à fila de prontas.
Troca de Contexto
5 ms
Round Robin



Cada processo recebe um tempo limitado (time slice = quantum) para
executar um ciclo de processador
Fila de processos aptos é circular
Necessita de relógio para delimitar as fatias de tempo (interrupção de
tempo/relógio)
∞) obtem-se o comportamento de um escalonador FIFO.

Se o (quantum =

Tamanho do quantum igual prejudica processos I/O bound (prioridade)
Políticas de Escalonamento
First-In First-Out (FIFO)
Shortest Job First
Shortest Job First



Algoritmo ótimo, fornece o menor tempo médio de espera para um conjunto de
processos
Processos I/O bound são favorecidos
Dificuldade é determinar o tempo do próximo ciclo de CPU de cada processo,
porém:
• Pode ser empregado em processos batch (long term scheduler)
• Prever o futuro com base no passado
Escalonamento em Sistemas Interativos
Um algoritmo de escalonamento com quatro
classes de prioridade
45
Como definir a Prioridade?





Prioridade Estática:
Processo é criado com determinada prioridade e esta é
mantida durante todo o processo.
Prioridade Dinâmica:
Prioridade é ajustada de acordo com o estado de execução
do processo e/ou sistema.
Ex. ajustar a prioridade em função da fração de quantum
que foi realmente utilizada pelo processo.
• q = 100ms
• Processo A = 2ms -> nova prioridade = 1/0.02 = 50
• Processo B = 50ms -> nova prioridade = 1/0.5 = 2