Sistemas Operativos I - Departamento de Engenharia ...dei.isep.ipp.pt/~llf/docs/Processos-V.pdf · 5 05/06 Sistemas Operativos I Maria João Viamonte / Luis Lino Ferreira 9 ... A

1

Sistemas Operativos I

ProcessosMaria João Viamonte / Luis Lino FerreiraFevereiro de 2006

05/06Sistemas Operativos I

Maria João Viamonte / Luis Lino Ferreira 2

Processo

“Fluxo de actividade autónomo que executa um conjunto de acções que são determinadas por um programa”

2



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



Processo

Portanto, um processo contém:Código executávelDados (variáveis globais)Estado do Processador (registos, stack, program counter)Ficheiros abertosTempo de UCP consumido

3



O Sistema Operativo

Um SO multi-tarefa deve:Alternar a execução de processos de forma a maximizar a utilização da UCPFornecer tempo de resposta razoávelAlocar recursos a processosSuportar a criação de processos pelo utilizadorSuportar a comunicação entre processos



Criar Processos

O que faz o SO para criar processos:Constrói estruturas de dadosAloca espaço de endereçamento

Por ex.:Quando o utilizador abre uma sessão de shellQuando gerado por outro processo…

4



Terminar Processos

Algumas razões para terminar um processo:

Tempo excedidoFalta de memóriaUso de instrução privilegiada…



Modelo Simples

ready running

despacho

pausa

entra sai

(a) Diagrama de transição de estado

UCPdespacho

pausa

entra sai

(b) Possível implementação

fila

5



Problemas com o Modelo Simples

Um processo que não está em execução estará sempre pronto a executar?

NãoPode 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



Modelo Mais Elaborado

terminatedready running

despacho

admissão libertado

(a) Diagrama de transição de estado

new

waiting

interrompidoeventoocorre espera

evento

6



Modelo Mais Elaborado

despacho

interrompido

sai

(a) Possível implementação

fila dos prontosUCP

fila evento 2

fila evento 1 espera evento 1

espera evento 2

ocorre evento 1

ocorre evento 2

admissão



Primitivas de Despacho

7



Primitivas de Despacho

NewO processo está a ser criado

ReadyO processo está pronto para ser executado

RunningO código referente a um processo está a ser executado

Sistemas multi-processador podem executar vários processo em paralelo, um em cada processador



Primitivas de DespachoWaiting

O processo está à espera que um evento específico ocorra (por ex. operação de I/O ou recepção de um sinal)

TerminatedO processo finalizou a sua execução

Nota:Em máquinas com apenas uma UCP só um processo pode estar no estado runningPode haver vários processos no estado ready e no estado waiting

8



Processos

Nota: Os estados definidos atrás apenas representam os casos mais habituais num SOA 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



Comutação de Processos

Para maximizar a UCP há que ter sempre um processo em execuçãoIsto implica:

Troca de processos em execuçãoA operação que permite retirar um processo em execução e substitui-lo por outro, implica saber:Onde o processo está localizadoOs atributos do processo

9



Comutação de Processos

Como é representado um processo?Imagem do processo:

ProgramaDadosPilhas(s)Atributos



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:

Identificação do processoInformação de estado do processadorInformação de controle do processo

10



Identificação do Processo

Composta por identificadores numéricos que incluem:

Identificador do processo (PID)Identificador do processo que o criouIdentificador do utilizador



Informação de Estado do Processador

Contida nos registos do processador:Registos visíveis pelo utilizadorRegistos de controle de estadoApontadores de pilha

11



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)PrioridadeSuporte ao escalonamento (por ex. há quanto tempo está à espera)Evento (por ex. identificação do evento que o processo está à espera)



Informação de controle do processo (2)

Estrutura dos dados (por ex. relação pai-filho)Comunicação entre processosPrivilégios (por ex. tipos de instruções que podem ser executadas)Gestão da memória

Valores do registo base e limiteponteiro para a tabela de páginas

Propriedade e uso de recursos (por ex. ficheiros abertos)

12



Process Control Block (PCB)



Exemplos

Lançar ProcessosUma forma de lançar processos é executar comandos numa shell

Exemplo: > lsA shell cria um novo processo que executa o programa ‘ls’, espera que termine e volta a aceitar comandos

Exemplo: > ls &A shell cria um novo processo que executa o programa ‘ls’ e retorna imediatamente para aceitar comandosO processo é lançado em background

13



Exemplos

Consultar ProcessosO comando ps mostra os processos existentes:

Exemplo: > psPID: identificador do processoTTY: terminalSTAT: 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



ExemplosParar ou suspender Processos

O comando kill permite enviar um sinal assíncrono ao processo

Exemplo: > kill 143Existem combinações de teclas que enviam sinais específicos:

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

14



Exemplos

Redireccionar entradas e saídasCada processo tem os seguintes canais de comunicação:

Stdin ‘standard input’ – entrada de dadosStdout ‘standard output’ – saída de dados normalStderr ‘standard error’ – saída de dados de erro

É 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’:

> ls | grep lista



Sugestão de Estudo

Ver de que forma é implementada a estrutura PCB em LINUX

Sugestão: utilizar a Web para procurar a informaçãoVer o Livro “Understanding the Linux kernel”editado pela O’ReillyVerificar quais as diferenças para aquilo que foi descrito

15



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 contextoA comutação entre dois processos faz-se:

Salvaguarda do estado do processo que perde a UCP;Restauração do estado do processo que ganha a UCP



Comutação entre Processos

16



Escalonamento

Um dos objectivos da multi-programação é a maximização da utilização da UCPO escalonador tem como objectivo decidir qual o próximo processo a ser executado em função dos seus parâmetros

Note-se que em sistema mono-processadorapenas pode ser executado um processo de cada vez



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

17



Filas de EscalonamentoReady 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 executadosDevice queue – lista dos PCBs dos processos àespera dum dispositivo I/O

Exemplo: Disk unit 0 queue




Processos no estado de Waiting

Processo emite um pedido de

I/O

Processo cria um novo sub-

processo

Processo removido em

consequência de uma interrupção

18




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 deviceO tempo que o escalonador tinha atribuído ao processo (time slice) termina e consequentemente ser colocado na fila dos readyo processo pode criar um novo processo, ficando à espera que ele termine e consequentemente ser colocado na fila dos waitingo processo pode ser removido da UCP em consequência duma interrupção, transitando para a Ready queue



EscalonadoresUm processo migra entre várias filas de escalonamento durante o seu tempo de vidaO SO deve seleccionar processos destas filas com base em algum método ou algoritmoHá três tipos de escalonadores:

curto prazomédio prazolongo prazo

Os processos podem ser caracterizados como ou: 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çãoUCP-bound process – despende mais tempo a fazer cálculos na UCP; consequentemente, há poucos UCP bursts de longa duração

19



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 boundEscalonador de longo-prazo é invocado com pouca frequência (segundos, minutos) ⇒ (pode ser lento)Escalonador de longo-prazo controla o grau de multiprogramaçãoUtilizado essencialmente em sistema batchPode estar ausente (por ex: no Linux e no Windows)



Escalonadores

Escalonador de curto-prazo (ou escalonador da UCP):

Selecciona que processos devem ser executados de seguida e reserva, consequentemente, a UCPEscalonador de curto-prazo é invocado com bastante frequência(milli-segundos) ⇒ (ser rápido)Exemplos:

LinuxWindows

20



EscalonadoresEscalonador 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



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 filhoOs processos filhos podem criar outros processos, criando uma árvore de processos

21



Árvore de Processos (UNIX)



Criação de Processos

Diferente hipóteses de implementação Modos de execução:

Pai e filho(s) executam concorrentementePai espera até que o(s) filho(s) terminem

Ocupação da memóriaO filho duplica o espaço do paiO filho carrega um novo programa

Partilha de recursos:Pai e filho(s) partilham todos os recursosFilho(s) partilham um subconjunto dos recursos do paiPai e filho(s) não partilham quaisquer recursos

22



Criação de Processos (UNIX)

A chamada ao sistema fork() cria um processo novo

O pai e o filho executam concorrentementeO 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

Ficheiro abertosObjectos para comunicação inter-processosEtc.



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 reservadosA tarefa atribuída ao filho não é mais necessáriaO pai está a terminar o que obriga os filhos a terminar

23



Processo Cooperativos

Os processos podem ser classificados como:Independentes: não afecta nem é afectado pela execução de outros processosCooperativos: interagem com outros processos de modo a executar uma tarefa, pelo que afectam e podem afectar outros processos



Processo CooperativosRazões para a cooperação

Partilha de informaçãoDe modo a requerer serviços a outros processos

PerformanceO programa é partido em vários processos executadas em paralelo (vários processadores)

ModularidadeSeparar o programa em módulos diferentes. Por ex. separar a interface gráfica das rotinas do programa

ConveniênciaPor ex. de modo a que seja possível realizar várias tarefas em simultâneo

24



Paradigma Produtor/Consumidor

O processo produtor produz informaçãoO processo consumidor consome essa informaçãoA comunicação entre os processo pode ser feita através de:

Unbounded-buffer: o buffer utilizado para a troca de dados não têm qualquer limite de tamanhoBounded-buffer: o buffer utilizado para a troca de dados têm um tamanho limitado




Solução com bounded-bufferDados em memória partilhada:#define BUFFER_SIZE 10Typedef struct {

. . .} item;item buffer[BUFFER_SIZE];int in = 0; //pos. de escritaint out = 0; //pos. de leitura

25




Produtor

item nextProduced;

while (1) {while (((in + 1) % BUFFER_SIZE) == out)

; /* do nothing */buffer[in] = nextProduced;in = (in + 1) % BUFFER_SIZE;

}

Resto inteiro da divisão

Próximo item a ser produzido



Solução pouco eficiente dado que o consumidor fica em espera activa!!!


Consumidor

item nextConsumed;

while (1) {while (in == out)

; /* do nothing */nextConsumed = buffer[out];out = (out + 1) % BUFFER_SIZE;

}

Próximo item a ser consumido

Se in==out significa que não existem elementos no buffer

26



Comunicação entre Processos

Através de mensagensPermite a comunicação entre processos através das primitivas de mensagens:

send(): envia mensagemreceive(): recebe mensagem



Comunicação entre ProcessosDirecta

Os processos têm que explicitamente indicar o destino ou a fontesend(p, msg), p processo de destinoreceive(q, msg), q processo fonte

PropriedadesA ligação entre os pares é estabelecida automaticamente A ligação está associada apenas a dois processosA ligação pode ser unidireccional ou bidireccional

27



Comunicação entre Processos

IndirectaAs mensagens são enviadas para caixas de correio send(mailboxA, msg), coloca uma mensagem na caixa de correio Areceive(mailboxA, msg), lê uma mensagem na caixa de correio A

PropriedadesNão existe ligação entre processos, apenas ligação à caixaA caixa de correio pode estar associada a mais do que 1 processoA caixa de correio pode ser unidireccional ou bidireccional



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

As primitivas podem ser bloqueantes (blocking) ou não bloqueantes (nonblocking)As primitivas bloqueantes são também classificadas como síncronasAs primitivas não bloqueantes são também classificadas como assíncronas

28



BufferingFila de mensagens associadas a uma ligação; é implementada numa das três formas:

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á saturadaCapacidade ilimitada – comprimento infinito. O emissor nunca espera



Comunicação entre Máquinas Diferentes

Mecanismos (alguns exemplos)SocketsRemote Procedure Calls.NetCorbaCOMDDE

29

Sistemas Operativos I

ProcessosMaria João Viamonte / Luis Lino FerreiraFevereiro de 2006



Gestão de Processo

Existem comandos para:Lançar novos processosConsultar processosParar ou suspender processosRedireccionar entradas e saídas de processos

30



Process Control Block

Estado do processoDe acordo com a máquina de estados definida anteriormente

Program CounterIndica o endereço da próxima instrução que iráser executado pelo processo

Registos da UCPO número e tipo dos registos depende da UCP (por ex: acumuladores, stack pointers, flags...)




Informação de escalonamentoPrioridadeApontadores para as filas de escalonamentoOutros parâmetros

Informação sobre a memória Áreas de memória utilizáveis pelo processo

31




Informação de monitorizaçãoTempo de UCP gastoLimites para o processoNúmero do processo

Informação de I/OLista de dispositivos de I/O atribuídos ao processoLista de ficheiros abertos

Documents

Sistemas Operativos I - Departamento de Engenharia ...dei.isep.ipp.pt/~llf/docs/Processos-V.pdf · 5 05/06 Sistemas Operativos I Maria João Viamonte / Luis Lino Ferreira 9 ... A