View
218
Download
0
Category
Preview:
Citation preview
Sistemas OperativosEscalonamento e sincronização
Rui Maranhão (rma@fe.up.pt)
Benefícios da Multiprogramação
• maximiza o tempo de utilização do CPU
• utilização do CPU = 1 - pn
• n é o número de processos
• p fracção de tempo em espera por I/O
•
Políticas de escalonamento
• processos competem por recursos
• a política depende dos objectivos do sistema
• as políticas visam
• conveniência: redução dos tempos de resposta, sendo justo para os processos
• eficiência: débito e max utilização do CPU
Critérios de escalonamento
• IO-bound ou CPU-bound
• interactivo ou não
• urgência de resposta (tempo real)
• comportamento recente
• necessidade de periféricos especiais
• por prioridade
Estados de um processo
• em execução
• foi-lhe atribuído CPU
• bloqueado
• o processo está logicamente impedido de prosseguir, porque lhe falta um recurso
• do ponto de visto do SO, transição voluntária
• pronto a executar, aguarda escalonamento
Primitivas de despacho
• bloqueia(evento)
• coloca processo na fila de processos parados à espera do evento
• invoca próximo processo
• liberta(evento) ou liberta(processo, evento)
• se processo não esta a espera de mais eventos, coloca-o na lista de espera
Primitivas de despacho
• próximo_processo()
• selecciona um dos processos existentes na lista de processos prontos a executar
• executa a comutação de contexto
• salvaguarda contexto volátil do processo corrente
• carrega contexto do processo escolhido
Principais decisões
• Qual o próximo processo?
• Quando começa a executar?
• Durante quanto tempo?
Escalonamento de processos
• Se, após lhe ser atribuído o CPU, nunca mais lhe for retirado
• escalonamento cooperativo (non-preemptive)
• ex., windows 3.1, co-rotinas, thread_yield()
• se o CPU lhe for retirado
• escalonamento com desafectação forçada
• ou preemptive
Escalonamento de processos
• escalonamento cooperativo
• sensível as variações de carga
• escalonamento com desafectação forçada
• sistema responde melhor
• comutação de contexto é cara
Escalonamento
• longo-prazo (segundos, minutos) e de curto-prazo (milisegundos)
• CPU-bound: faz pouco uso de I/O; requer muito processamento
• I/O-bound: faz muito uso de I/O
Escalonamento
• os processos prontos são seriados numa fila (ready list)
• lista ligada de apontadores para process control block
• lista pode estar ordenada por prioridades
Escalonamento
• quando um processo é escalonado, é retirado da ready list e posto a executar
• o processo pode perder o CPU
• aparecer um com maior prioridade
• pedido de I/O (bloqueado)
• o quantum expira (pronto)
Escalonamento
• pretende-se maximizar a utilização do CPU tendo em atenção
• tempo de resposta de aplicações interactivas
• utilização de dispositivos I/O
• justiça na distribuição de tempo de CPU
Escalonamento
• Quando escalonar um processo?
• quando um processo passa de a-executar a bloqueado
• quando um processo passa a pronto
• quando se termina uma operação I/O
• quando um processo termina
Escalonamento
• diferentes algoritmos de escalonamento favorecem diferentes optimizações
• tempo de resposta
• máxima utilização de CPU
Objectivos dos algoritmos de escalonamento
• em geral
• equidade, balanceado e forçar que as regras impostas pelo algoritmo são respeitadas
• sistemas de batch
• thoughput, turnaournd time, maximizar utilização do CPU
Objectivos dos algoritmos de escalonamento
• sistemas interactivos
• tempo de resposta e proporcionalidade
• sistemas de tempo real
• tempos de resposta estão pré-definidos, previsibilidade
Algoritmos
• FCFS (first come, first served)
• SJF (shortest job first)
• SRTF (shortest remaining time first)
• preemptive priority scheduling
• RR (round-robin)
• outros algoritmos: lotaria, promessas
FCFS
• a ready list é uma fila FIFO
• o processo é colocado no fim da fila e seleccionado o da frente
• método cooperativo
• nada apropriado para ambientes interactivos
FCFS
• tempo de espera com grandes flutuações dependendo da ordem de chegada e das características dos processos
• simplicidade de implementação
SJF
• escalonar processo mais curto primeiro
• possibilidades
• desafectação forçada - interrompe o processo em execução se aparecer um mais curto
• cooperativo - aguarda terminação do processo em execução mesmo que apareça um mais curto
SJF
• não se consegue calcular a priori o tempo de execução dos processos
• apenas se podem fazer estimativas
• uma combinação de tempos reais e estimativas para fazer futuras previsões
Preemptive priority
• associa uma prioridade a cada processo
• a ready queue é uma fila seriada por prioridades
• escalona sempre o processo de maior prioridade
• se um processo de maior prioridade aparecer, faz a troca de processos
Preemptive priority
• Problema: míngua (starvation)!!
• Solução: evelhecimento
• aumenta a prioridade dos processos pouco a pouco para que sejam executados eventualmente
RR
• dá a cada processo um intervalo de tempo de CPU fixo de cada vez
• quando um processo esgota o seu quantum retira-o do CPU e volta a colocá-lo no fim da fila
• ignorando overheads do escalonamento (quais?), cada um dos n processos terá 1/n do tempo disponível de CPU
RR
• se o quantum for muito grande, RR tende a comportar-se como FCFS
• se o quantum for muito pequeno, então o overhead de mudanças de contexto degrada os níveis de utilização do CPU
• tempo de resposta melhor que o SJF (o quantum é normalmente o SJ)
Avaliação de algoritmos
• Modelo deterministico
• definição da carga tipo: ordem de chegada dos processo, tempos de execução, distribuição CPU/IO, etc. e avaliação analítica do desempenho
• vantagem: simples
• desvantagem: ajuste dos resultados depende directamente dos dados de entrada (necessários vários cenários)
Avaliação de algoritmos
• Teoria de fila de espera
• definição de um modelo matemático do sistema e avaliar segundo a teoria de filas de espera
• desvantagem: muitas simplificações para que o modelo seja tratável
Avaliação de algoritmos
• simulação
• escrever/adoptar/usar um programa que modele o sistema e analisar o desempenho do algoritmo
• tentar obter traços do comportamento de sistemas reais
• desvantagem: tempo de execução longos
Sincronização de processos
Programação concorrente
• a possibilidade de execução “simultânea” leva ao acesso em concorrência a recursos partilhados
• o acesso concorrente pode ser feito a zonas de endereçamento partilhadas
• o acesso concorrente pode resultar na incoerência dos dados/resultados
Cooperação entre processos
• vários processos executam em conjunto uma ou mais tarefas, nos quais
• competem por recursos
• indicam uns aos outros
• ausência/existência de recursos
• ocorrência de acontecimentos
Problema da exclusão mútua
• Qual o problema se for multi-tarefa?
Problema da execução concorrente
Problema...
• em linguagem máquina as acções atómicas são mais elementares
•
Programação concorrente
• para garantir a coerência dos dados é necessário que os processos acedam ordenadamente aos recursos
• o SO fornece um conjunto de mecanismos que permitem os processos sincronizarem-se
Secção crítica
• em programação concorrente sempre que se testam ou se modificam estrutura de dados:
• fazê-lo dentro de uma secção crítica!!
Secção crítica
Secção crítica: Propriedades
• exclusão mútua
• progresso (liveness)
• ausência de deadlocks
• ausência de míngua (starvation)
Secção crítica: Condições
• As seguintes condições são necessárias para uma solução eficiente
• só um processo pode estar dentro da secção crítica
• não se deve assumir valores quanto a velocidade de execução ou #CPUs disponíveis
Secção crítica: Condições
• processos a executar fora da secção crítica não deverá bloquear outros processos
• nenhum processo deverá esperar indefinidamente para entrar na região crítica
Implementações
• algorítmicas
• hardware
• sistema operativo
Proposta #1
• Qual a propriedade não garantida??
Proposta #2
• Qual a propriedade não garantida??
Proposta #3
• Qual a propriedade não garantida??
• Porque motivo é garantida a exclusão mútua
Proposta #4
• Qual a propriedade não garantida??
Algoritmo Peterson
Conclusões sobre soluções algorítmicas
• complexas: alta latência
• só contemplam espera activa
• solução: introduzir implementações de hardware
Soluções com suporte do hardware
• abrir() e fechar() usam instruções especiais oferecidas pelos processadores
• inibição de interruptores
• exchange (xchg no intel IA)
• test-and-set (cmpxchg no intel IA)
Exclusão mútua com inibição de interruptores
• só deve ser usado dentro do SO em secções críticas de pouca duração
• inibição das interrupções impede execução de serviços de sistema
• se o programa não chamar abrir(), as interrupções ficam inibidas e o sistema para
Não funciona em multiprocessadores...
Problema da atomicidade em multiprocessadores
Exclusão mútua com exchange
Exchange em multiprocessadores
Exclusão mútua com test-and-set
Conclusões sobre as soluções de hardware
• oferecem mecanismos básicos
• não podem ser usadas por programas em modo utilizador
• só contemplam espera activa
Regiões críticas
• soluções anteriores não são muito interessantes porque
• acarretam espera activa
• remetem o problema para o código fonte
• só estão disponíveis em kernel mode
• Objectivo: primitvas genéricas, acessíveis no modo utilizador, fornecendo espera passiva
Soluções com suporte do SO
• Primitivas de sincronização
• software trap (interrupção SW)
• comutação para modo núcleo
• estrutura de dados e código de sincronização pertence ao núcleo
• usa suporte de hardware (ex., test-and-set)
• mutex e semáforos
Mutex
• técnica de programação para evitar que processos tenham acesso simultâneo a um recurso partilhado
• em português: trinco?
• outra definição?
Estrutura de dados
Diagrama de estados
Funções do mutex
Funções do mutex
mutex: limitações
• mutex não são suficientemente expressivos para resolver alguns problemas de sincronização
• bloquear tarefas se a pilha estiver cheia
• necessário um controlador de recursos
Semáforos
Semáforos: Primitivas
• s = criar_semafaro(num)
• esperar(s)
• bloqueia o processo se num <= 0
• assinalar(s)
• se houver processos bloqueados, liberta um, senão num++
• primitivas atómicas e podem ser invocadas de processos diferentes
Semáforos: Primitivas
Exemplo
Interface mutex POSIX
int pthread_mutex_init(pthread_mutex_t *m, pthread_mutexattr_t *a);int pthread_mutex_lock(pthread_mutex_t *mutex);int pthread_mutex_unlock(pthread_mutex_t *mutex);int pthread_mutex_trylock(pthread_mutex_t *mutex);int pthread_mutex_timedlock(pthread_mutex_t *mutex, const struct timespec *timeout);
Exemplo:pthread_mutex_t count_lock;pthread_mutex_init(&count_lock, NULL);pthread_mutex_lock(&count_lock);count++;pthread_mutex_unlock(&count_lock);
Interface semáforo POSIX
int sem_init(sem_t *sem, int pshared, unsigned value);int sem_post(sem_t *sem);int sem_wait(sem_t *sem);
Exemplo:sem_t sharedsem;sem_init(&sharedsem, 0, 1);sem_wait(&sharedsem);count++;sem_post(&sharedsem);
Alternativas
• Outras formas de implementar regiões críticas
• sleep/wakeup
• contagem de eventos
• monitores
• mensagens
Exemplos clássicos de problemas de sincronização
Problemas clássicos de sincronização
• algoritmo do barbeiro
• algoritmo dos produtores / consumidores
• jantar dos filósofos
• algoritmo dos leitores / escritores
Recommended