...

Sistemas Operativos I

by user

on
Category: Documents
4

views

Report

Comments

Transcript

Sistemas Operativos I
Sistemas Operativos I
Processos
Maria João Viamonte / Luis Lino Ferreira
Fevereiro de 2006
Processo
„
05/06
“Fluxo de actividade autónomo que executa
um conjunto de acções que são
determinadas por um programa”
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
2
1
Conceito de Processo
„
Pode ser definido como:
‰
‰
Uma instância de um programa em
execução
„ No entanto um programa pode ser
constituído por n processos
Unidade de trabalho de um sistema
operativo multi-processo
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
3
Processo
„
Portanto, um processo contém:
‰
‰
‰
‰
‰
05/06
Código executável
Dados (variáveis globais)
Estado do Processador (registos, stack,
program counter)
Ficheiros abertos
Tempo de UCP consumido
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
4
2
O Sistema Operativo
„
Um SO multi-tarefa deve:
‰
‰
‰
‰
‰
Alternar a execução de processos de forma a
maximizar a utilização da UCP
Fornecer tempo de resposta razoável
Alocar recursos a processos
Suportar a criação de processos pelo utilizador
Suportar a comunicação entre processos
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
5
Criar Processos
„
O que faz o SO para criar processos:
‰
‰
„
Por ex.:
‰
‰
‰
05/06
Constrói estruturas de dados
Aloca espaço de endereçamento
Quando o utilizador abre uma sessão de shell
Quando gerado por outro processo
…
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
6
3
Terminar Processos
„
Algumas razões para terminar um
processo:
‰
‰
‰
‰
Tempo excedido
Falta de memória
Uso de instrução privilegiada
…
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
7
Modelo Simples
despacho
entra
ready
running
sai
pausa
(a) Diagrama de transição de estado
entra
fila
despacho
UCP
sai
pausa
(b) Possível implementação
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
8
4
Problemas com o Modelo Simples
„
Um processo que não está em execução
estará sempre pronto a executar?
‰
Não
„
„
Pode estar bloqueado, por ex. à espera de uma
operação de I/O
Pelo que o escalonador não pode
escalonar qualquer um dos processos que
se encontra na fila de espera
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
9
Modelo Mais Elaborado
despacho
libertado
admissão
new
ready
running
terminated
interrompido
evento
ocorre
espera
evento
waiting
(a) Diagrama de transição de estado
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
10
5
Modelo Mais Elaborado
fila dos prontos
despacho
admissão
UCP
sai
interrompido
ocorre evento 1
ocorre evento 2
fila evento 1
fila evento 2
espera evento 1
espera evento 2
(a) Possível implementação
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
11
Primitivas de Despacho
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
12
6
Primitivas de Despacho
„
New
‰
„
Ready
‰
„
O processo está a ser criado
O processo está pronto para ser executado
Running
‰
O código referente a um processo está a ser
executado
„
Sistemas multi-processador podem executar vários
processo em paralelo, um em cada processador
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
13
Primitivas de Despacho
„
Waiting
‰
„
Terminated
‰
„
O processo finalizou a sua execução
Nota:
‰
‰
05/06
O processo está à espera que um evento específico
ocorra (por ex. operação de I/O ou recepção de um
sinal)
Em máquinas com apenas uma UCP só um processo
pode estar no estado running
Pode haver vários processos no estado ready e no
estado waiting
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
14
7
Processos
„
Nota:
‰
‰
Os estados definidos atrás apenas
representam os casos mais habituais num SO
A implementação do modelo de processo pelo
SO pode necessitar de outros estados, como
por ex.:
„
Em LINUX é definido o estado de Zombie para os
processo que já terminaram mas cujos recursos
ainda não foram totalmente libertados
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
15
Comutação de Processos
„
„
Para maximizar a UCP há que ter sempre
um processo em execução
Isto implica:
‰
‰
‰
‰
05/06
Troca de processos em execução
A operação que permite retirar um processo
em execução e substitui-lo por outro, implica
saber:
Onde o processo está localizado
Os atributos do processo
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
16
8
Comutação de Processos
„
Como é representado um processo?
‰
Imagem do processo:
„ Programa
„ Dados
„ Pilhas(s)
„ Atributos
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
17
Representação do Processo
„
„
Cada processo é representado perante o SO
por uma estrutura contendo a sua informação,
o Process Control Block (PCB)
O PCB é o conjunto de atributos do processo
e pode ser dividido em três partes:
‰
‰
‰
05/06
Identificação do processo
Informação de estado do processador
Informação de controle do processo
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
18
9
Identificação do Processo
„
Composta por identificadores numéricos que
incluem:
‰
‰
‰
Identificador do processo (PID)
Identificador do processo que o criou
Identificador do utilizador
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
19
Informação de Estado do
Processador
„
Contida nos registos do processador:
‰
‰
‰
05/06
Registos visíveis pelo utilizador
Registos de controle de estado
Apontadores de pilha
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
20
10
Informação de controle do
processo (1)
„
Estado e escalonamento, de acordo com a
máquina de estados definida anteriormente,
que inclui:
‰
‰
‰
‰
Estado do processo (por ex. ready)
Prioridade
Suporte ao escalonamento (por ex. há quanto
tempo está à espera)
Evento (por ex. identificação do evento que o
processo está à espera)
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
21
Informação de controle do
processo (2)
„
„
„
„
Estrutura dos dados (por ex. relação pai-filho)
Comunicação entre processos
Privilégios (por ex. tipos de instruções que podem ser
executadas)
Gestão da memória
‰
‰
„
05/06
Valores do registo base e limite
ponteiro para a tabela de páginas
Propriedade e uso de recursos (por ex. ficheiros
abertos)
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
22
11
Process Control Block (PCB)
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
23
Exemplos
„
Lançar Processos
‰
Uma forma de lançar processos é executar
comandos numa shell
„
Exemplo: > ls
‰
„
Exemplo: > ls &
‰
‰
05/06
A shell cria um novo processo que executa o programa
‘ls’, espera que termine e volta a aceitar comandos
A shell cria um novo processo que executa o programa
‘ls’ e retorna imediatamente para aceitar comandos
O processo é lançado em background
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
24
12
Exemplos
„
Consultar Processos
‰
O comando ps mostra os processos existentes:
„
Exemplo: > ps
‰
‰
‰
‰
„
PID: identificador do processo
TTY: terminal
STAT: estado do processo
ƒ
- R ‘running’, S ‘sleeping’, D ‘uninterruptible sleep’
TIME: tempo de processador já consumido
O comando ‘top’ mostra estatísticas gerais do sistema
e processos com maior actividade
‰
Exemplo: > top
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
25
Exemplos
„
Parar ou suspender Processos
‰
O comando kill permite enviar um sinal
assíncrono ao processo
„
„
Exemplo: > kill 143
Existem combinações de teclas que enviam
sinais específicos:
‰
‰
‰
05/06
CTRL+C ‘signal interrupt’ (sigint)
CTRL\ ‘signal quit’ (sigquit)
CTRL+Z ‘signal stop’ (sigstop)
ƒ
> bg – coloca o processo suspenso a executar-se
em segundo plano
ƒ
> fg – coloca o processo suspenso a executar-se em
primeiro plano
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
26
13
Exemplos
Redireccionar entradas e saídas
„
‰
Cada processo tem os seguintes canais de comunicação:
„
„
„
‰
É possível direccionar ficheiros para estes canais:
„
„
‰
> ls > resultado.txt
> telnet > script.txt
É também possível direccionar a saída de um processo
para a entrada de outro, através de um ‘pipe’:
„
05/06
Stdin ‘standard input’ – entrada de dados
Stdout ‘standard output’ – saída de dados normal
Stderr ‘standard error’ – saída de dados de erro
> ls | grep lista
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
27
Sugestão de Estudo
„
Ver de que forma é implementada a estrutura
PCB em LINUX
‰
‰
‰
05/06
Sugestão: utilizar a Web para procurar a
informação
Ver o Livro “Understanding the Linux kernel”
editado pela O’Reilly
Verificar quais as diferenças para aquilo que foi
descrito
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
28
14
Comutação entre Processos
„
„
A partilha do processador requer um
mecanismo de comutação de processos, a
que se dá o nome de comutação de
contexto
A comutação entre dois processos faz-se:
‰
‰
05/06
Salvaguarda do estado do processo que perde a
UCP;
Restauração do estado do processo que ganha
a UCP
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
29
Comutação entre Processos
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
30
15
Escalonamento
Um dos objectivos da multi-programação é a
maximização da utilização da UCP
O escalonador tem como objectivo decidir
qual o próximo processo a ser executado em
função dos seus parâmetros
„
„
‰
05/06
Note-se que em sistema mono-processador
apenas pode ser executado um processo de
cada vez
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
31
Filas de Escalonamento
„
As filas de escalonamento permitem ao SO
saber o estado dos processos (PCBs)
„
Existem filas para cada um dos estados,
assim como filas para coordenar o acesso
aos dispositivos de I/O
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
32
16
Filas de Escalonamento
„
„
Ready queue – esta fila
contém os PCBs dos
processos residentes
em memória que estão
no estado ready, isto é
processos que estão
prontos e à espera de
serem executados
Device queue – lista dos
PCBs dos processos à
espera dum dispositivo
I/O
‰ Exemplo: Disk unit 0
queue
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
33
Filas de Escalonamento
Processo emite
um pedido de
I/O
Processo cria
um novo subprocesso
Processo
removido em
consequência de
uma interrupção
Processos no
estado de
Waiting
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
34
17
Filas de Escalonamento
„
Portanto, durante a sua execução de um processo
várias coisas podem acontecer:
‰
‰
‰
‰
o processo pode emitir um pedido I/O, e
consequentemente ser colocado numa fila de I/O device
O tempo que o escalonador tinha atribuído ao processo
(time slice) termina e consequentemente ser colocado na
fila dos ready
o processo pode criar um novo processo, ficando à espera
que ele termine e consequentemente ser colocado na fila
dos waiting
o processo pode ser removido da UCP em consequência
duma interrupção, transitando para a Ready queue
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
35
Escalonadores
„
„
„
Um processo migra entre várias filas de escalonamento durante o seu
tempo de vida
O SO deve seleccionar processos destas filas com base em algum
método ou algoritmo
Há três tipos de escalonadores:
‰
‰
‰
„
curto prazo
médio prazo
longo prazo
Os processos podem ser caracterizados como ou:
‰
‰
05/06
I/O-bound process – despende mais tempo a fazer operações I/O do que
cálculos na UCP; consequentemente, há bastantes UCP bursts de curta
duração
UCP-bound process – despende mais tempo a fazer cálculos na UCP;
consequentemente, há poucos UCP bursts de longa duração
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
36
18
Escalonadores
„
Escalonador de longo-prazo (ou escalonador de
processos):
‰ Selecciona os processos que devem ser levados para
a fila Ready de modo a que existe uma mistura
equilibrada entre processos I/O bound e UCP bound
‰ Escalonador de longo-prazo é invocado com pouca
frequência (segundos, minutos) ⇒ (pode ser lento)
‰ Escalonador de longo-prazo controla o grau de
multiprogramação
‰ Utilizado essencialmente em sistema batch
‰ Pode estar ausente (por ex: no Linux e no Windows)
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
37
Escalonadores
„
Escalonador de curto-prazo (ou escalonador da
UCP):
‰
‰
‰
Selecciona que processos devem ser executados de
seguida e reserva, consequentemente, a UCP
Escalonador de curto-prazo é invocado com bastante
frequência
(milli-segundos) ⇒ (ser rápido)
Exemplos:
„
„
05/06
Linux
Windows
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
38
19
Escalonadores
„
05/06
Escalonador de médio-prazo
‰ Permite remover processos da memória
‰ Mais tarde pode ser retomada a execução destes programas
(Swapping)
‰ Devido a falta de memória ou para uniformizar o conjunto de
processos em execução
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
39
Gestão de Processos com Funções
de Sistema
„
Um processo pode criar outros processos através de
uma chamada ao sistema
‰ create_process()
‰ ou fork()
„
O processo criador é referido como processo pai e o
processo criado é o processo filho
Os processos filhos podem criar outros processos,
criando uma árvore de processos
„
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
40
20
Árvore de Processos (UNIX)
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
41
Criação de Processos
Diferente hipóteses de implementação
„
Modos de execução:
‰
‰
„
Ocupação da memória
‰
‰
„
O filho duplica o espaço do pai
O filho carrega um novo programa
Partilha de recursos:
‰
‰
‰
05/06
Pai e filho(s) executam concorrentemente
Pai espera até que o(s) filho(s) terminem
Pai e filho(s) partilham todos os recursos
Filho(s) partilham um subconjunto dos recursos do pai
Pai e filho(s) não partilham quaisquer recursos
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
42
21
Criação de Processos (UNIX)
A chamada ao sistema fork() cria um
processo novo
„
‰
‰
‰
O pai e o filho executam concorrentemente
O filho duplica o espaço de memória do pai
(mas não pode aceder aos dados do pai)
Pai e filho partilham alguns recursos
„
„
„
05/06
Ficheiro abertos
Objectos para comunicação inter-processos
Etc.
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
43
Terminação de um Processo
„
„
Terminação normal: um processo termina quando acaba a
execução da sua última instrução, e pede ao SO para eliminá-lo
via a chamada ao sistema exit().Nesta altura:
‰ O processo devolve eventualmente dados ao seu progenitor
através da evocação da função wait()
‰ O SO liberta todos os recursos utilizados pelo processo (filho)
Terminação abrupta: o pai pode terminar a execução dos
processos filhos através da chamada ao sistema abort()
‰ Filho excedeu os recursos que lhe foram reservados
‰ A tarefa atribuída ao filho não é mais necessária
‰ O pai está a terminar o que obriga os filhos a terminar
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
44
22
Processo Cooperativos
„
Os processos podem ser classificados como:
‰
‰
Independentes: não afecta nem é afectado pela
execução de outros processos
Cooperativos: interagem com outros processos
de modo a executar uma tarefa, pelo que afectam
e podem afectar outros processos
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
45
Processo Cooperativos
„
Razões para a cooperação
‰
Partilha de informação
„
‰
Performance
„
‰
Separar o programa em módulos diferentes. Por ex. separar a
interface gráfica das rotinas do programa
Conveniência
„
05/06
O programa é partido em vários processos executadas em
paralelo (vários processadores)
Modularidade
„
‰
De modo a requerer serviços a outros processos
Por ex. de modo a que seja possível realizar várias tarefas em
simultâneo
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
46
23
Paradigma Produtor/Consumidor
„
„
„
O processo produtor produz informação
O processo consumidor consome essa
informação
A comunicação entre os processo pode ser
feita através de:
‰
‰
05/06
Unbounded-buffer: o buffer utilizado para a troca
de dados não têm qualquer limite de tamanho
Bounded-buffer: o buffer utilizado para a troca
de dados têm um tamanho limitado
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
47
Paradigma Produtor/Consumidor
„
„
Solução com bounded-buffer
Dados em memória partilhada:
#define BUFFER_SIZE 10
Typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0; //pos. de escrita
int out = 0; //pos. de leitura
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
48
24
Paradigma Produtor/Consumidor
Produtor
item nextProduced;
Próximo item a
ser produzido
while (1) {
Resto inteiro da divisão
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
49
Paradigma Produtor/Consumidor
Consumidor
item nextConsumed;
Próximo item a
ser consumido
while (1) {
Se in==out significa que não
while (in == out)
existem elementos no buffer
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
Solução pouco eficiente dado
que o consumidor fica em
espera activa!!!
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
50
25
Comunicação entre Processos
„
Através de mensagens
‰
Permite a comunicação entre processos através
das primitivas de mensagens:
„
„
05/06
send(): envia mensagem
receive(): recebe mensagem
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
51
Comunicação entre Processos
„
„
Directa
‰ Os processos têm que explicitamente indicar o destino
ou a fonte
‰ send(p, msg), p processo de destino
‰ receive(q, msg), q processo fonte
Propriedades
‰ A ligação entre os pares é estabelecida
automaticamente
‰ A ligação está associada apenas a dois processos
‰ A ligação pode ser unidireccional ou bidireccional
05/06
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
52
26
Comunicação entre Processos
Indirecta
„
‰
‰
‰
As mensagens são enviadas para caixas de correio
send(mailboxA, msg), coloca uma mensagem na caixa de correio
A
receive(mailboxA, msg), lê uma mensagem na caixa de correio A
Propriedades
„
‰
‰
‰
05/06
Não existe ligação entre processos, apenas ligação à caixa
A caixa de correio pode estar associada a mais do que 1
processo
A caixa de correio pode ser unidireccional ou bidireccional
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
53
Sincronização
„
As primitivas de send e receive também podem
servir para sincronizar dois processos, i.e. um
processo pode ficar à espera que exista uma
mensagem na caixa do correio
‰
‰
‰
05/06
As primitivas podem ser bloqueantes (blocking) ou não
bloqueantes (nonblocking)
As primitivas bloqueantes são também classificadas como
síncronas
As primitivas não bloqueantes são também classificadas
como assíncronas
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
54
27
Buffering
Fila de mensagens associadas a uma
ligação; é implementada numa das três
formas:
„
‰
‰
‰
05/06
Capacidade nula – 0 mensagens. O emissor
tem de esperar pelo receptor (rendezvous)
Capacidade limitada – comprimento finito de n
mensagens. O emissor tem de esperar se a
ligação está saturada
Capacidade ilimitada – comprimento infinito. O
emissor nunca espera
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
55
Comunicação entre Máquinas Diferentes
„
Mecanismos (alguns exemplos)
‰
‰
‰
‰
‰
‰
05/06
Sockets
Remote Procedure Calls
.Net
Corba
COM
DDE
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
56
28
Sistemas Operativos I
Processos
Maria João Viamonte / Luis Lino Ferreira
Fevereiro de 2006
Gestão de Processo
„
Existem comandos para:
‰
‰
‰
‰
05/06
Lançar novos processos
Consultar processos
Parar ou suspender processos
Redireccionar entradas e saídas de processos
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
58
29
Process Control Block
„
Estado do processo
‰
„
Program Counter
‰
„
De acordo com a máquina de estados definida
anteriormente
Indica o endereço da próxima instrução que irá
ser executado pelo processo
Registos da UCP
‰
O número e tipo dos registos depende da UCP
(por ex: acumuladores, stack pointers, flags...)
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
05/06
59
Process Control Block
„
Informação de escalonamento
‰
‰
‰
„
Informação sobre a memória
‰
05/06
Prioridade
Apontadores para as filas de escalonamento
Outros parâmetros
Áreas de memória utilizáveis pelo processo
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
60
30
Process Control Block
„
Informação de monitorização
‰
‰
‰
„
Informação de I/O
‰
‰
05/06
Tempo de UCP gasto
Limites para o processo
Número do processo
Lista de dispositivos de I/O atribuídos ao
processo
Lista de ficheiros abertos
Sistemas Operativos I
Maria João Viamonte / Luis Lino Ferreira
61
31
Fly UP