Sistemas Operativos - gsd.inesc-id.ptpjpf/slides-sync-2.pdf · leccionado a disciplina de Sistemas Operativos: Paulo Ferreira, André Zúquete, ... wutilitários para controlo de

Page 1

Paulo Ferreira - INESC/IST 1

SistemasSistemasOperativosOperativos

IST - LEIC - 1ºIST - LEIC - 1º SemestreSemestre


Autoriað estes transparentes:wsão baseados no livro “Fundamentos de Sistemas Operativos”, de José Alves

Marques e Paulo Guedes, Editorial Presença ;wabrodam apenas a primeira parte da matéria, i.e., introdução aos sistemas

operativos, noção de processo, gestão de processos e sincronização;wresultam do esforço de vários docentes do IST que, ao longo de vários anos, têm

leccionado a disciplina de Sistemas Operativos: Paulo Ferreira, André Zúquete,Luís Veiga;wsão disponibilizados livremente para fins didácticos em www.rnl.ist.utl.pt/~ic-so;wserão constantemente melhorados de modo a satisfazer as necessiadades de

aprendizagem dos alunos.

Page 2


Introduçãoð o que é um sistema operativo?wconjunto de programas que servem para gerir e vigiar a execução dos programas de

diversos utilizadores e que promovem a gestão dos recursos de um computador

ð quais os objectivos?winterface com o utilizador simples e fácil de utilizar (máquina virtual)wexploração eficiente dos recursos hardware da máquina (tempo de processamento,

memória volátil e de massa, periféricos de comunicação)


Funções Principais de um Sistema Operativoð gestão da concorrênciawcontrolar diversos fluxos de actividade independentes que se executam “em

paralelo” sem que os mesmos interfiram não intencionalmente

ð partilha de recursos com protecçãowfísicos: processador, memória, discos, periféricos diversoswlógicos: programas de uso geral (editores, compiladores) e bibliotecas partilhadas

por diversos programas

ð gestão de informação persistentewarmazenamento fiável e seguro da informação não volátil em suportes magnéticos,

ópticos, etc.

ð controlo dos gastoswcontabilização e limitação da utilização dos recursos físicos

Page 3


Recursos Físicos (hardware)ð processador (CPU)ð memória volátil (RAM)ð periféricos:wterminaiswdiscoswoutros (diskettes, bandas, CDs, impressoras, scanners, etc.)

ð especiais:winterrupções do processadorwrelógio de tempo realwinstruções privilegiadaswsuporte para memória virtual e protecção de memória


19501946 1960 1970 1980

Tempo Partilhado

Memória Virtual (UNIX)

Sistemas Distribuídos

Multiprogramação (Multics)

Tratamento por Lotes (IBM 7090)

Tratamento por Lotes Rudimentar

Sem Sistema Operativo (UNIVAC, IBM 701, IBM 650)

1ª Geração:Interruptores

e válvulas

2ª Geração:Transístores

3ª Geração:Circuitos integrados

4ª Geração:Computadores pessoais

Evolução histórica

Page 4


Monitor de Controloð permite ao utilizador: carregar programas em memória, editá-los e

verificar a sua execuçãoð cada utilizador tem um determinado tempo atribuído durante o

qual tem o computador apenas para sið resultados dos programas: listagens, fitas perfuradasð monitor é formado por um conjunto de utilitários:winterpretador de linguagem de comandowcompiladorweditor de ligações (linker)wcarregador de programas em memória (loader)wutilitários para controlo de periféricos (consola, leitor de cartões, etc.)

ð desvantagem: computador está parado a maior parte do tempo


Tratamento em Lotes (Batch)ð impessoras, leitores/perfuradores de fita são muito lentosð monitor de controlo: tempo de execução de um programa é

determinado pelas E/Sð solução:wrecolha de dados num computador auxiliar onde os dados são lidos para banda

magnéticawcomputador central lê a banda magnética e escreve resultados numa outra que é

lida pelo computador auxiliar produzindo listagens

ð evolução:wperiféricos executam tarefas autónomas e avisam o processador do fim da sua

execução através de interrupções (comunicação assíncrona)wexecução em paralelo dos programas e das E/S

Page 5


Multiprogramaçãoð mecanismo de interrupções permite multiplexar o processador

entre várias actividades concorrentesð execução concorrente de vários programas:wpermite optimizar a utilização do processadorwex.: P1 acede ao disco e ica bloqueado enquanto o controlador de disco funciona;

durante esse tempo, P2 pode ser executado pelo processadorwimplica mudança de contexto rápida, logo os programas têm de estar em memória

ð memória é limitada:wswapping (guardar P1 em disco e carregar P2 em memória)wimplica código recolocável (numa outra posição de memória)


Tempo Partilhado e Memória Virtualð tempo partilhado:wmultiplexagem entre vários utilizadoreswdivisão do tempo disponível do processadorwsensação de dispôr de um computador apenas para siwimplica considerar novos aspectos: sistemas de ficheiros, protecção dos dados

ð memória virtual:wgestão da memória muito complexa (programas/utilizadores distintos)wespaço de endereçamento virtual muito superior à memória física

Page 6


Sistemas Operativos: tempo virtual e realð tempo virtual:wtempo de execução dos programas não tem relação com o tempo cronológico

exterior ao computador

ð tempo real:wnoção do tempo é relevantewtem como objectivo garantir que o computador pruduz uma resposta a um

acontecimento externo num intervalo de tempo limitado previamente especificado

ð várias gradações de tempo real:wcontrolo de processos industriaiswsistemas transaccionaiswetc.


Critérios de Qualidadeð fiabilidade:wnão existência de erros intrínsecoswtolerância a faltas/falhas nos recursos físicos

ð eficiência:wtempo de resposta nos sistemas de tempo partilhadowtempo de processador aproveitado/desaproveitadowdesempenho - trabalhos/unidade de tempowpartilha dos recursoswdegradação do desempenho com o aumento da carga

ð capacidade/facilidade de manutenção:wconfiguraçãowcorrecção de erroswevolução

Page 7


Gestão de Processos

Gestão de Memória

Comunicação e E/S

Sistema de Ficheiros

Interface do Sistema

Aplicações

Realização


Modelo Computacional

Modelo Computacional

Gestão de Processos

Gestão de Memória

Comunicação e E/S


Gestão de Processose

Sincronização

Gestão de Memória

Comunicação e E/S


ð conjunto de objectos do sistema operativo e operações que ospermitem manipular

Page 8


Gestão de Processos: conceitos de baseð processadorwelemento físico que executa uma acção definida numa instrução máquina

ð processowentidade “activa” no sistema operativo no âmbito da qual é executada uma

sequência de acções determinada por um programa

ð programawsequência de acções, descritas numa determinada linguagem, sem actividade

própria

ð aplicaçãowconjunto de actividades cooperantes a decorrer em um ou mais processos segundo

as directivas de um ou mais programas

ð executável (ficheiro)wbloco de instruções máquina e dados resultantes da tradução (compilação) de um

programa


Processo: abstracção de máquina virtualð espaço de endereçamento:wconjunto de posições de memória a que um programa executado num processo pode

acederwregião de memória onde está o código, os dados e a pilha (stack) do processo

ð reportório de instruções:wcódigo (programa compilado)wtambém designado por imagem

ð contexto de execução:wvalor dos registos do processador e de outras unidades de controlo (memória, etc.)

em cada instante

Page 9


Utilizador 1processo inicial

subprocesso 1

subprocesso 3subprocesso 2


subprocesso 1

subprocesso 3

Gestor de Processos: objectivoð criação e eliminação de processosð suportar a co-existência de processos:watribuição do processador aos processoswtratamento das interrupções da actividade dos processoswfornecimento de mecanismos de sincronização entre processoswlimitação das interferências destrutivas entre processos

ð manutenção de uma hierarquia de processos em curso



subprocesso 1

subprocesso 3subprocesso 2


subprocesso 1

subprocesso 3

Estrutura Hierárquica dos Processosð hierarquia traduz-se por informações que são mantidas no contexto

dos processosð tratamento da relação hierárquica depende dos sistemas:wfim de um processo elimina todos os processos filhoswfim de um processo não altera estado dos processos fihos

ð estrutura hierárquica facilita a criação de processos:wgrande parte do ambiente pode ser herdado

Page 10


Gestor de Processos: modelo computacionalð criação de processoswIdProcesso = CriarProc ( Código, Prioridade, ... )

•IdProcesso - identificador do processo no sistema.•Código - ficheiro executável com o programa a executar pelo processo.•Prioridade - importância relativa do processo no sistema.

ð eliminação de processoswEliminarProc ( IdProcesso )


Concorrênciað competição entre processos no acesso a um recursoð só um processador => pseudo-concorrênciawintercalação ou paralelismo lógico; ilusão de uma concorrência efectiva

ð comutação de processoswo processo a executar é sucessivamente retirado do processador para dar lugar a

outro

ð salvaguarda do contexto de execuçãowquando um processo perde o processador há que guardar um conjunto de

informações (contexto de execução) que possibilitem o seu retorno como se nadativesse acontecido

ð programação concorrentewdesenvolvimento de programas incluindo partes que podem ser executadas em

paralelo

Page 11


t

P2

P1

P3

Tempo real de execução dos processos

t

P2

P1

P3

Utilização do processador

Pseudo-concorrência


Representação de Processosð os programas do núcleo fazem a gestão do “ambiente” onde os

processos são executadosð estes programas manuseiam estruturas de dados que representam a

estrutura física dos processosð cada processo é representado por uma descrição que contém toda a

informação relevante:wcontexto de hardware

• registos do processador (acumulador, uso geral, contador de programa, stack pointer,estado do CPU) e da unidade de gestão de memória

wcontexto de software (permanente e volátil)•identificação•ficheiro executável•prioridade•estado do processo•outras informações (periféricos em uso, ficheiros abertos, directório por omissão,

programa em execução, etc.)

Page 12


Gestão das Interrupções e Excepçõesð mecanismos de comunicação assíncrona entre o sistema e o

processador:winterrupções

•notificações de acontecimentos globais à máquina (não dirigidas a um determinadoprocesso)

•controladas e tratadas exclusivamente pelo núcleo do sistema operativo

wexcepções•notificações de acontecimentos relacionados com um processo e que devem ser

tratadas no seu contexto.•controladas e tratadas pelo sistema operativo e (opcionalmente) pelos processos.

ð processamento de interrupções:winterrupção gestor de interrupções rotina de tratamento/escalonamento

despacho


Funções Sistema (system calls)ð interface aos serviços do sistema operativoð protecção (duas entidades funcionais):wfunção propriamente dita, pertence ao programa do núcleo do sistema operativowrotina de interface que é ligada com o código do utilizador e que usa instruções

especiais (traps) para mudar de modo utilizador para modo sistema

ð vantagens:wpartilha das funções sistema por todos os processoswmodificação transparente do sistema operativo desde que não se altere a interface

ð protecção => não utilização de endereços de memória com dados dosistema operativo

Page 13


Rotina de biblioteca dechamada à função sistema X

Programa do UtilizadorExecutável

Sistema operativo

Agulhagem

Funçãosistema A

Funçãosistema Z

trap

Modo utilizador (não privilegiado)Modo utilizador (não privilegiado)

Modo sistema (privilegiado)Modo sistema (privilegiado)

Chamada a Funções Sistema


Suporte Hardware para a Realização do SOð interrupçõeswcomunicação assíncrona de eventos

ð relógio de tempo realwtemporização das diversas actividades a executar

ð mecanismos de protecçãowevitar a corrupção do código e dados do sistema operativowlimitação das capacidades de endereçamento dos processos

ð gestão de endereçamentowprotecção de blocos de memória principalwpossibilidade de recolocar código e dados na memória principalwdetecção de endereçamentos inválidos

Page 14


Diagrama de Estados de um Processo

EmExecução

Executável Não executável(bloqueado)

Seleccionado peloDespacho

Retirado peloDespacho

Bloquear

Desbloquear


Lista dosLista dosProcessosProcessos

ExecutáveisExecutáveis

Contexto doContexto doprocesso iprocesso i

Contexto doContexto doprocesso i+1processo i+1

Contexto doContexto doprocesso i+2processo i+2

Tabela noTabela noSistemaSistema

OperativoOperativo

Lista dos Processos Executáveis

Page 15


Núcleo do SO: gestão dos processos

Restantes Níveis

Aplicações

Gestão das

Interrupções

Multiplexagem(scheduling)

Sincronização


Multiplexagem do Processadorð despacho:wverifica se o processo em execução é o mais prioritário; caso não seja (preempção):

•guarda o contexto hardware do processo em execução no respectivo descritor•escolhe o processo mais prioritário entre os executáveis•carrega o seu contexto hardware no processador•transfere o controlo para o novo processo (instrução a executar: program counter)

wexecuta o processo em execuçãowé activado sempre que existe a possibilidade de o processador ser comutado:

•quando o processo corrente termina ou fica bloqueado•após uma interrupção ou uma chamada ao núcleo

ð escalonamento (scheduling):wgestor do processadorwcontrola a prioridade dos processos de modo a optimizar a utilização de todos os

recursos do computador

Page 16


Escalonamentoð objectivos:wmaximizar a utilização do processador sem descurar o estado dos restantes

componentes do sistema (memória, periféricos, etc.)wminimizar o custo computacional do algoritmo de escalonamento

ð time-slice:wintervalo de tempo máximo que é atribuído a um processo

ð prioridade:wrepresenta a importância do processo no algoritmo de atribuição do processador

ð preempção:wretira o processador ao processo em execução sempre que um processo mais

prioritário fica executávelwestado do núcleo do sistema operativo tem de estar consistente quando se dá a

preempção


Preempçãoð o que é:wacção de retirar o processador a um processo em execução devido à existência de

outro mais prioritário

ð objectivo:wpermite que os processos mais prioritários reajam rapidamente a um dado

acontecimento (reactividade aos acontecimentos externos)

ð custo:wassociado à mudança de contexto (ex.: um processo só é retirado de execução

depois de ter usado processador durante um tempo mínimo)

ð quando ocore:wna sequência de todas as acções susceptíveis de modificarem o estado dos

processos

ð exemplo (Unix):wquando o processo em execução retorna a modo utilizador e existe um processo

mais prioritário executável

Page 17


ð categorias dos sistemas operativos:wtempo real (tempo de resposta limitado perante eventos externos)wtempo partilhado

ð as políticas não podem ter em conta apenas o uso doprocessador; é necessário ter em conta outros recursos (ex.:memória)

ð teoricamente seria interessante que a função de escalonamentofosse invocada sempre que um recurso do sistema é atribuídoou libertado (memória, prefiféricos, etc.)

ð o problema é que a própria função de escalonamento consomerecursos

Políticas de Escalonamento (1)


Políticas de Escalonamento (2)ð políticas para ambientes de tempo partilhado interactivos:wtempo de execução partilhado:

•tempo de execução contínua limitado a um quantum (time-slice)•lista de processos executáveis é gerida em round-robin•pode conduzir a tempos de resposta elevados em situações de muita carga

wpreempção:•primazia ao processo mais prioritário•indispensável em sistemas de tempo real•despacho é chamado na sequência de todas as acções susceptíveis de modificarem os

estado dos processos

Page 18


Políticas de Escalonamento (3)wmultilista:

•usado em sistemas mistos de tempo partilhado (gestão circular) e tratamento por lotes(gestão baseada na menor duração do trabalho)

•utilização de várias listas consoante o tipo de processos em execução(fundamentalmente segundo o nível de interactividade)

•despacho escolhe sempre um processo da lista mais prioritária

wprioridades dinâmicas:•ajuste da prioridade de acordo com o consumo de recursos (fundamentalmente tempo

de CPU)•processos apenas numa lista que é ordenada em função das prioridades

wquantum variável:•adaptar o valor do quantum ao comportamento dos processos•aumentar o valor do quantum quando o sistema está muito carregado (limitar o custo

dos context-switch e aumentar a probabilidade do processo terminar)•complexidade acrescida no sistema operativo


Gestão Multilista

utiliza o processador



lista de maiorprioridade (menosprocessador usado)

lista demenorprioridade

Page 19


Gestão Multilista com Quantum Variável

Prioridade Máxima tcpu = 0,02 s

Prioridade Média tcpu = 0,25 s

Prioridade Mínima tcpu = 2 s

Despacho


Função dos Mecanismos de Sincronizaçãoð aplicações eficientes implica decomposição em vários processosð potencialmente melhor desempenhoð cooperação:wpermitir a um processo assinalar a um outro o final de uma etapa, de forma a que o

segundo possa prosseguir na execução do algoritmo da aplicação (ex.: reserva debilhete de avião)

ð competição por/gestão de um recurso:wcompetição pela obtenção de um recurso único ou limitado no sistema (o recurso

pode ser um periférico, um ficheiro, zona de memória, etc.)wbloquear os processos consumidores quando não há recursoswassinalar a existência de recursos disponíveis quando há processos bloqueados

ð exclusão mútua:wgarantir a coerência na modificação de variáveis partilhadas (ex., teste e alteração

do valor de uma variável)

Page 20


Exclusão Mútuað não-determinismo:wum processo pode ser interrompido em instantes impossíveis de prever

ð secções críticas:wconjuntos de instrucções que se devem executar de forma atómicawdados partilhados devem ser manipulados no interior de secções críticas que

garantam uma exclusão mútua no acesso aos mesmos

ð sincronização:wcontrolo do não-determinismo entre processos concorrentes

ð mecanismos:wdirectos: funções que actuam directamente sobre o estado dos processoswindirectos: trincos lógicos e semáforos


Alocador de Memória

pilha com descritores dos blocos livres

livre

livre

livre

livre

mapa de memória

Page 21


Alo

cado

r de

Mem

ória

(con

t.)

char

* pe

deM

em()

{ch

ar*

ptr

= 0;

if (t

opo

>= 0

) {pt

r =

pilh

a[to

po];

topo

--;

} retu

rn p

tr;

}

void

dev

olve

Mem

(cha

r* p

tr) {

if (t

opo

< M

AX

_PIL

HA

) {to

po++

;pi

lha[

topo

]= p

tr;

}}

#def

ine

MA

X_P

ILH

A 1

00ch

ar*

pilh

a[M

AX

_PIL

HA

];in

t top

o;

funç

ões/

dado

s par

tilha

dos p

or to

dos o

s pro

cess

os!


Violação de uma Secção Crítica

Processo A (devolveMem) Processo B (pedeMem)

Instr. n topo++;

interrupção => despacho seleciona outro processo (B neste exemplo)

Instr. n

Instr. n+1

ptr = pilha[topo];

topo--;

t

ð conjunto de instruções que se devem executar de forma atómicað estruturas de dados partilhadas devem ser actualizadas no interior duma

secção crítica que garanta a exclusão mútua no acesso às variáveis

Page 22


Exclusão Mútua: solução alg. básica

void procUm() { while (TRUE) { /*testar possibilidade de acesso*/ while (nProc == SEGUNDO) ;

/* secção crítica */ nProc = SEGUNDO; /*permite acesso ao outro proc.*/

} }

void procDois() { while (TRUE) {

while (nProc == PRIMEIRO) ; /* secção crítica */ nProc = PRIMEIRO; /*

} }

enum {PRIMEIRO = 1, SEGUNDO}; enum {FALSE, TRUE}; int nProc = PRIMEIRO

ð processos comutam explicitamente o direito de acesso à secção críticað um processo pode atrasar indefinidamente a entrada do outro na secção críticað o algoritmo só se aplica a dois processosð o processo impedido de entrar fica em espera activað instruções não são indivisíveis


Exclusão Mútua: algoritmo de Dekker

void procUm() {while (TRUE) { P1QuerEntrar = TRUE; /*assinalar tentativa de acesso*/ while (P2QuerEntrar) { /*verificar disponibilidade*/ if (procPrioritario == SEGUNDO) { /*proc. proritario*/ P1QuerEntrar = FALSE; /*desistir temporariamente*/ while (procPrioritario == SEGUNDO); P1QuerEntrar = TRUE;

} }

/* secção crítica */ procPrioritario = SEGUNDO; P1QuerEntrar = FALSE;

}}

void procDois() {while (TRUE) { P2QuerEntrar = TRUE; while (P1QuerEntrar) { if (procPrioritario == PRIMEIRO) { P2QuerEntrar = FALSE; while (procPrioritario == PRIMEIRO); P2QuerEntrar = TRUE;

} } /* secção crítica */

procPrioritario = PRIMEIRO; P2QuerEntrar = FALSE;

} }

enum {PRIMEIRO = 1, SEGUNDO}; enum {FALSE, TRUE}; int procPrioritario = PRIMEIRO, P1QuerEntrar = FALSE, P2QuerEntrar = FALSE;

Page 23


ð vantagens:wnão impõe uma sequência de utilização alternada do recurso partilhado

ð desvantagens:wapenas se aplica a dois processoswo processo impedido de entrar fica em espera activawinstruções não são indivisíveis

Algoritmo de Dekker


Exlusão Mútua: algoritmo de Lamport

int compara(int a, int b) { if (senha[a] < senha[b] || (senha[a] == senha[b] && a < b )) return TRUE; else return FALSE; }

int max() { int maximo=0, i; for (i=0; i < N; i++) if (senha[i] > maximo) maximo = senha[i]; return maximo; }

void proc (int i) {int j;while (TRUE) { /*atribuição da senha*/ escolha[i] = TRUE;

senha[i] = max() + 1; escolha[i] = FALSE;

/*espera até deter a senha de número menos elevado*/ for (j=0; j < N; j++ ) {

while (escolha[j]); while (senha[j] != 0 && compara(j, i));

} /* secção critica */ senha[i] = 0;}

}

#define N 10 enum {FALSE, TRUE}; int senha[ N ]; int escolha[ N ];

Page 24


Soluções Algorítmicas vs.Modelo Computacional

ð são muito complexasð o programador tem uma carga adicional de trabalhoð instruções de linguagens de alto nível não são indivisíveisð o modelo computacional do sistema operativo deve incorporar os

mecanismos necessários à implementação da exclusão mútua:wé mais simples e mais eficaz

ð mecanismos indirectos:wtrincos lógicos: variável booleana partilhada por vários processos que indica se

algum deles está numa determinada secção críticawsemáforos: variável inteira e fila de espera

ð mecanismos directos:wfunções que actuam directamente sobre o estado dos processos


Dis

trib

uido

r de

Mem

ória

com

Tri

nco

char

* pe

deM

em()

{fe

char

(tri

ncoM

em);

ch

ar*

ptr

= 0;

if (t

opo

>= 0

) {pt

r =

pilh

a[to

po];

topo

--;

} abri

r(tr

inco

Mem

);re

turn

ptr

;} vo

id d

evol

veM

em(c

har*

ptr

) {fe

char

(tri

ncoM

em);

if (t

opo

< M

AX

_PIL

HA

) {to

po++

;pi

lha[

topo

]= p

tr;

} abri

r(tr

inco

Mem

);}#d

efin

e M

AX

_PIL

HA

100

char

* pi

lha[

MA

X_P

ILH

A];

int t

opo;

void

fech

ar (i

nt tr

inco

) {

whi

le (t

rinc

o ==

TR

UE

);

tri

nco

= TR

UE

; } vo

id a

brir

(int

trin

co) {

trin

co =

FA

LSE

; }

Page 25


Violação da Sincronização com um Trinco

Processo A: void fechar (int trinco) { while (trinco == TRUE);

rotina de interrupção => despacho

Processo B: void fechar (int trinco) { while (trinco == TRUE); trinco = TRUE; }

execução da secção crítica

interrupção entre iteracções

rotina de interrupção => despacho

Processo A: trinco = TRUE; } execução da secção crítica

interrupção

t

ð trincos lógicos precisamde suporte especial para asua implementação:wteste e atribuição indivisívelwhardware: instrução especialwsistema: inibição das

interrupçõeswmultiprocessador implica

gestão do bus

void fechar (int trinco) { while (trinco == TRUE); trinco = TRUE; }

void abrir (int trinco) { trinco = FALSE; }


Trinco Lógico (lock)ð objectivo: indicar se existe algum processo a utilizar a secção críticað variável booleana partilhada por vários processos que indica se

algum deles está numa determinada secção crítica:wos trincos lógicos precisam de suporte especial para a sua concretização:

•hardware - instrução especial - TSL (Test & Set Lock), Lock, etc.•sistema - inibição de interrupções.

ð espera activa:wum processo que tente fechar um trinco já fechado tem de continuar a tentar essa

operação até conseguir

ð sufocação ou míngua (starvation):wum processo pode ser indefinidamente preterido no acesso a uma região crítica

Page 26


Diagrama de Estados de um Processo

EmExecução


Bloquear

Desbloquear

Espera Activa/Starvation

Retirado pelo Despacho

Seleccionado pelo Despacho


Semáforo (Dijkstra)ð um semáforo é constituído porwuma variável de controlo ss e por uma fila de espera (processos bloqueados)

ð que, para além da atribuição inicial, só pode ser modificada atravésdas primitivaswesperar(s) = wait(s) = p(s)wassinalar(s) = signal(s) = v(s)

ð semântica:wwss negativo ou nulo força o bloqueio do processowwss positivo indica possibilidade de continuar a execução

Page 27


Operações Sobre os Semáforosvoid Esperar () { i = i -1; if (i < 0) { /* aceder ao descritor do processo em causa, retirar de execução e colocar na fila de espera do semáforo */ }}

void Assinalar () { i = i + 1; if (i <= 0) { /* aceder ao primeiro descritor na fila de espera do semáforo e transferir para fila de executáveis */ }}

ð os dados do semáforo são acedidos apenas por funções sistemað os dados do semáforo são acedidos em exclusão mútua

ss <= 0

ss > 0

=> bloqueia processo

=> processo continua


Implementação de Semáforos

fechar(trinco)

i = i - 1;

i < 0 ?aceder ao descritordo processo em causa

retirar o processo de execução e colocar nafila de espera do semáforo

abir(trinco)

Esperar

fechar(trinco)

i = i + 1;

i <= 0 ?retirar o descritor dodo processo da fila deespera do semáforo

colocar o descritor do processo na fila dos executáveis

abir(trinco)

Assinalar

ss <= 0

SS

NN

ss > 0

Page 28


Implementação de Semáforos (cont.)void Esperar () { fechar(trincoSem); i = i - 1; if (i < 0) { /* aceder ao descritor do processo em causa, retirar de execução e colocar na fila de espera do semáforo */ } abrir(trincoSem);}

void Assinalar () { fechar(trincoSem); i = i + 1; if (i <= 0) { /* aceder ao primeiro descritor na fila de espera do semáforo e transferir para fila de executáveis */ } abrir(trincoSem);}


ð objectivo:wexclusão mútua de

processos nas primitivas desincronização

ð implementação:whardware

ð mecanismos de atraso:wespera activa

ð tempo de atraso típico:walguns microsegundos

semáforossemáforos trincostrincos

Comparação de Semáforos e Trincos

ð objectivo:wprimitivas gerais de sincronização

ð implementação:wsoftware

ð mecanismos de atraso:wfila de espera

ð tempo de atraso típico:walguns segundos

Page 29


Sincronização com Semáforosð exclusão mútua no acesso a regiões críticas:wsemáforo: ExcMut, inicialmente: ExcMut = CriarSemáforo (1)wprograma: esperar (ExcMut) ... secção crítica ... assinalar (ExcMut)

ð cooperação:wpermitir a um processo assinalar a outro o final de uma etapa de processamento

para que o segundo prossiga a execução do seu programawrequisito: P1 não passa do ponto L1 antes de P2 chegar a L2wsemáforo: Cont, inicialmente: Cont = CriarSemáforo (0)wcódigo de P1: ... esperar (Cont) L1: ...wcódigo de P2: ... L2: assinalar (Cont) ...

ð gestão de recursos:wimplementar uma política de gestão de recursos que permita:

•bloquear os consumidores na ausência de recursos livres•assinalar a existência de recursos livres a consumidores à espera


Dis

trib

uido

r de

Mem

ória

com

Sem

áfor

o

char

* pe

deM

em()

{es

pera

r(se

mE

xMut

);

char

* pt

r =

0;if

(top

o >=

0) {

ptr

= pi

lha[

topo

];to

po--

;} as

sina

lr(s

emE

xMut

);re

turn

ptr

;} vo

id d

evol

veM

em(c

har*

ptr

) {es

pera

r(se

mE

xMut

);if

(top

o <

MA

X_P

ILH

A) {

topo

++;

pilh

a[to

po]=

ptr

;} as

sina

lar(

sem

ExM

ut);

}#def

ine

MA

X_P

ILH

A 1

00ch

ar*

pilh

a[M

AX

_PIL

HA

];in

t top

o =

MA

X_P

ILH

A;

/* se

mE

xMut

inic

ializ

ado

a 1*

/

Page 30


Dis

trib

uido

r de

Mem

ória

com

Sem

áfor

o (c

ont.)

char

* pe

deM

em()

{es

pera

r(se

mM

em);

e

sper

ar(s

emE

xMut

);

ptr

= pi

lha[

topo

];to

po--

;as

sina

lr(s

emE

xMut

);re

turn

ptr

;} vo

id d

evol

veM

em(c

har*

ptr

) {es

pera

r(se

mE

xMut

);to

po++

;

pilh

a[to

po]=

ptr

;

ass

inal

ar(s

emE

xMut

);

ass

inal

ar(s

emM

em);

}#def

ine

MA

X_P

ILH

A 1

00ch

ar*

pilh

a[M

AX

_PIL

HA

]; in

t top

o =

MA

X_P

ILH

A;

/* se

mE

xMut

inic

ializ

ado

a 1*

//*

sem

Mem

inic

ializ

ado

a M

AX

_PIL

HA

*/


Jantar dos Filósofosð cinco filósofos jantam espargueteð cada filósofo precisa de dois

garfos para comerð existe apenas um garfo por

pessoa (i.e, cinco garfos)ð os filósofos têm lugar fixoð cada filósofo pode usar apenas os

garfos que se encontram à suaesquerda e à sua direita

ð os filósofos têm três estadospossíveis: pensar, pensar comer,comer

1

0

2

3

4

Page 31


Jantar dos Filósofos - solução #define MAX 5 enum {Pensar, PensarComer, Comer}; int estado[MAX]; semaforo semPriv[MAX]; /* inicializado a 0 */ semaforo mutex; /* inicializado a 1 */

void testa (int k) { if ((estado[k] == pensarComer) && (estado[mod(k+1, MAX)] != Comer) && (estado[mod(k-1, MAX)] != Comer)) { estado[k] = Comer; assinalar (semPriv[k]); }}

void filosofo (int i) { for(;;) {

/* pensar */

esperar(mutex); estado[i] = PensarComer; testa(i); assinalar(mutex); esperar(semPriv[i]);

/* comer */

esperar(mutex); estado[i] = Pensar; testa(i+1); testa(i-1); assinalar(mutex); }

int mod (j, max) { if (j == MAX) return 0; if (j == -1) return (MAX-1); return j;}


Lei

tore

s-E

scri

tore

s

voi

d in

icia

Leitu

ra()

{

Esp

erar

(Mut

ex);

if

(em

Escr

ita |

|

(esc

rito

resE

sper

a >

0)) {

leito

resE

sper

a ++

;

A

ssin

alar

(Mut

ex);

Esp

erar

(Lei

tore

s);

Esp

erar

(Mut

ex);

leito

resE

sper

a--;

if (l

eito

resE

sper

a >

0)

A

ssin

alar

(Lei

tore

s);

}

n

Leito

res

++;

A

ssin

alar

(Mut

ex);

}

void

aca

baLe

itura

() {

E

sper

ar(M

utex

);

nLe

itore

s --

;

if (

escr

itore

sEsp

era

> &

&

nLe

itore

s ==

0)

A

ssin

alar

(Esc

rito

res)

;

Ass

inal

ar(M

utex

);}en

um {

FALS

E, T

RU

E};

int n

Leito

res,

leito

resE

sper

a, e

scri

tore

sEsp

era;

int e

mEs

crita

;se

maf

oro

Mut

ex, L

eito

res,

Esc

rito

res;

/* in

icia

lizad

os a

1, 0

, 0 *

/

void

aca

baEs

crita

(){

E

sper

ar(M

utex

);

em

Escr

ita =

FA

LSE;

if

(lei

tore

sEsp

era

> 0)

A

ssin

alar

(Lei

tore

s);

el

se

if

(esc

rito

resE

sper

a >

0)

A

ssin

alar

(Esc

rito

res)

;

Ass

inal

ar(M

utex

);}vo

id in

icia

Escr

ita()

{

Espe

rar(

Mut

ex);

if

(nLe

itore

s >

0 |

|

(leito

resE

sper

a >

0) ||

em

Escr

ita) {

escr

itore

sEsp

era

++;

Ass

inal

ar(M

utex

);

Es

pera

r(Es

crito

res)

;

Es

pera

r(M

utex

);

es

crito

resE

sper

a --

;

}

em

Escr

ita =

TR

UE;

A

ssin

alar

(Mut

ex);

}

Page 32


Impasse ou Interblocagem (deadlock)ð acontece quando as seguintes situações podem ocorrer:wvários processos tentam aceder em exclusivo a diversos recursoswos processos mantêm o acesso aos recursos já adquiridos enquanto esperam a

obtenção de acesso a outroswos recursos não podem ser retirados aos processos que os detêm até serem

completamente utilizadoswexiste uma cadeia circular de processos na qual cada processo possui um ou mais

recursos que são pretendidos pelo processo seguinte

ð soluções:wprevenção:

•aquisição de vários recursos sempre pela mesma ordem•caso falhe a aquisição de um recurso, libertar todos os recursos detidos e recomeçar

wdetecção e eliminação forçada de estados de interblocagem


Interblocagem (deadlock)

t

Processo P1 Processo P2

Esperar(semA)

expira o quantum do processo P1

Esperar(semB)

Esperar(semA)P2 fica bloqueado

Esperar(semB)

P1 fica bloqueado

Page 33


Mecanismos de Sincronização Directosð funções que actuam directamente sobre os estado dos processosð suspensão e reactivação de processos:wsuspender (IdProcesso)wacordar (IdProcesso)

ð a capacidade de suspensão é frequentemente utilizada para realizarmecanismos de atraso que funcionam como uma auto-suspensão:wadormecer (Período)

ð não é de uso geral:winterferência com outros utilizadoreswidentidade do processo só é conhecida em tempo de execução


Mecanismos de Sincronização Directos

EmExecução


Selecionadopelo

Despacho

Preempção

Bloquear

Desbloquear

Suspenso

Acordar

Acordar

Suspender

Suspender

Suspender

Page 34


Controlador de Tarefasð processos:wum processo com funções de relógio - função relogiowum processo controlador - finção controladorwNTAR processos, cada um desempenhando uma determinada tarefa - função tarefa

tarefa 1 tarefa 2 tarefa i tarefa (i+1)

relogio

controlador

NTAR processos:

semPriv semPriv semPriv semPrivsemPriv

assinalar assinalar

adormecer


Controlador de Tarefas (cont.)

void controlador() { for(;;) { esperar(impulso); for (int i = 0; i < NTAR; i++) { tempo[i]--; if (tempo[i] < 0) { tempo[i] = novoIntervalo(); assinalar(iniTarefa[i]); } } }}

define PERIODO 100int tempo[NTAR]; /* inicializado aleatoriamente *//* semaforo impulso inicializado a 0 *//* semaforos iniTarefa[NTAR] inicializados a 0 */

void tarefa (int i) { for (;;) { esperar (iniTarefa[i]); /* executa tarefa */ }}

void relogio () { for (;;) { assinalar(impulso); adormecer(PERIODO);}

Documents

Sistemas Operativos - gsd.inesc-id.ptpjpf/slides-sync-2.pdf · leccionado a disciplina de Sistemas Operativos: Paulo Ferreira, André Zúquete, ... wutilitários para controlo de