Introdução aos Sistemas Operacionais · Aula 01 •Introdução aos Sistemas Operacionais 1...

Aula01

• IntroduçãoaosSistemasOperacionais

1

IntroduçãoaosSistemasOperacionais

• Definição

• Oqueé?

• Exemplos

• MáquinasdeNíveis

Prof. Marco Câmara

2

Definição

• “...umconjuntoderoHnasexecutadaspeloprocessador,deformasemelhanteaosprogramasdosusuários.”

• “...OSOtemporobjeHvofuncionarcomoumainterfaceentreousuárioeocomputador,tornandosuauHlizaçãomaissimples,rápidaesegura”.– FrancisMachadoeLuizPauloMaia

Prof. Marco Câmara

3

Definição

• “...éumprogramaqueatuacomointermediárioentreousuárioeohardwaredeumcomputador.”

• “...devepropiciarumambientenoqualousuáriopossaexecutarprogramasdeformaconvenienteeeficiente”.– Silberschatz,GalvineGagne

Prof. Marco Câmara

4

OqueéumSistemaOperacional?

• OqueéumS.O.?– Funções

– Responsabilidades• Transparência

– Simplificação

• Gerência– ComparHlhamento– OHmização

• Encapsulamento– EsconderDetalhes

Prof. Marco Câmara

5

OqueéumSistemaOperacional?

• Primeiroscomputadores– Programaçãocomplexa

• Exigiagrandeconhecimentodohardwareedelinguagemdemáquina

– Solução:• SistemasOperacionais

– Encapsulamento» Interaçãosetornoumaisfácil,confiáveleeficiente.

Prof. Marco Câmara

6

Exemplos(computadorespessoais)

• Windows(Windows10)

• MacOSX10.11(ElCapitan)

• Linux(Ubuntu,RedHat,SuSE)

• Unix(FreeBSD,SCOUnix,HP-UX,SunOS)

Prof. Marco Câmara

7

Exemplos(smartphones)

• Android

• IoS

• WindowsPhone

Prof. Marco Câmara

8

Exemplos(outrosambientes)

• Worksta-onsdeaplicaçãoespecífica

• Servidores

• EletrodomésHcos(SOembarcados)

• Computadoresdegrandeporte(mainframes)

Prof. Marco Câmara

9

Exemplos

• Quaisasprincipaisdiferenças?– Quemconhecemaisdeumsistemaoperacional?

– Apresentardiferenças.

Prof. Marco Câmara

10

Aula02

11

HistóricodeSOs

• PrimeiraGeração(1945-1955)

– Primeiroscomputadores

– ENIAC(ElectronicNumericalIntegratorandComputer)• RealizaçãodecálculosbalísHcos

– UHlizaçãodeválvulas• ENIAC

– 18.000válvulas

– ProgramaçãoemlinguagemdemáquinaProf. Marco Câmara

12

HistóricodeSOs

• PrimeiraGeração(1945-1955)– Ausênciadesistemaoperacional– EDVAC(ElectronicDiscreteVariableAutomaHcComputer)

– Usuários• Universidadeseórgãosmilitares

– UNIVAC• Censoamericanode1950

Prof. Marco Câmara

13

HistóricodeSOs

• SegundaGeração(1956-1965)– Criaçãodostransistores

• Aumentonavelocidadedoprocessamento• Dimensãodoscomputadores

– CriaçãodasmemóriasmagnéHcas

• Acessomaisrápidoaosdados

– Primeiraslinguagensdeprogramação:• AssemblyeFORTRAN

Prof. Marco Câmara

14

HistóricodeSOs

• SegundaGeração(1956-1965)– Cartãoperfurado– Processamentobatch

• Processamentodelotedeprogramas

– SOcomconjuntoderoHnasparaoperaçõesdeEntradaeSaída(IOCS)

– Conceito:• IndependênciadosdisposiHvos

Prof. Marco Câmara

15

HistóricodeSOs

• TerceiraGeração(1966-1980)– Monitordevídeoedoteclado

• Interação• TimeSharing

– SurgimentodosistemaoperacionalUNIX(linguagemC)

– Primeirosmicrocomputadores

Prof. Marco Câmara

16

HistóricodeSOs

• TerceiraGeração(1966-1980)– IntroduçãodosCircuitosIntegrados

•Menorcustoedimensão• Performance

– MulHprogramação• ComparHlhamentodamemóriaprincipal• PrimiHvascombloqueio

– Sinaiseinterrupções

Prof. Marco Câmara

17

HistóricodeSOs

• QuartaGeração(1981-1990)– Aperfeiçoamentodoscircuitosintegrados

– SurgimentodosPC’sedoDOS• SubsHtuiçãodoCP/M

– Estaçõesdetrabalho(monousuárias)•MulHtarefa

– MulHprocessadores

– Sistemasoperacionaisderedeedistribuídos.Prof. Marco Câmara

18

HistóricodeSOs

• QuintaGeração(1991-2007)– Arquiteturacliente-servidor

– Processamentodistribuído• MulHprocessadoresnãoconvencionais

– Linguagemnatural;

– Segurança,gerênciaedesempenhodoSOedarede

– Consolidaçãodossistemasdeinterfacesgráficas• Interaçãocomusuáriosmaisflexível

Prof. Marco Câmara

19

MáquinadeNíveis

• Computadorcomomáquinadeníveisoucamadas:– Nível2-Aplicações;

– Nível1–SistemaOperacional;

– Nível0–Hardware.

Prof. Marco Câmara

Usuários

20

Nível0(Hardware)

• DisposiHvosFísicos;

• Microprogramação;

• LinguagemdeMáquina.

Prof. Marco Câmara

21

Níveis1e2-So:ware

• SistemaOperacional;

• LinguagensdeProgramação

– CompiladoreseInterpretadores;

– MáquinasVirtuais(Java);

– AmbientesdeDesenvolvimento.

• Aplicações.

Prof. Marco Câmara

22

ConceitosdeHWeSW

Prof. Marco Câmara

23

Conceitos

• Hardware– Trêssubsistemasbásicos:

• UnidadeCentraldeProcessamento;• Memóriaprincipal;• DisposiHvosdeentradaesaída.

– Subsistemassãotambémchamadosdeunidadesfuncionais;

– Implementaçõespodemvariaradependerdaarquitetura.

Prof. Marco Câmara

24

ModelodeComputador

Entrada SaídaProcessamento

Memória

Prof. Marco Câmara

25

ModelodeComputador

• Execuçãodeprogramas– ProgramaarmazenadoemdisposiHvodeE/S

– Cargadoprogramanamemória(SO)

– Execuçãodasinstruções(umaauma)naCPU

Dispositivo de E/S

Memória Principal

CPU

Prof. Marco Câmara

26

CPU

• Controlacadaunidadefuncionaldosistema

• Execuçãodasinstruçõesdosprogramas

– AritméHcas

– Comparação

– Movimentação

Prof. Marco Câmara

27

CPU

• ConjuntodeInstruções

– InstruçõesdemáquinasdisponíveisnaCPU

– TiposequanHdadevariamdeacordocomaCPU

– CompaHbilidadedeprogramas

– RISCxCISC

Prof. Marco Câmara

28

CPU

• Desempenhodeprocessadores– Dependede:

» Conjuntodeinstruçõesdisponível

» clock

»Númerodenúcleos

– Benchmark»Usadoparacompararprocessadoresdiferentes

» Códigosespecíficospodemprivilegiarumdeterminadoproduto!

Prof. Marco Câmara

29

Memória(definição)

• Externa(storage)– ArmazenaarquivosdoSO,AplicaçõeseDados;

– Estante?

• PrincipalouInterna– Provêoespaçodetrabalho(mesa?)

30

MemóriaPrincipal

• Armazenainformações(bits)

– Programas(instruções)– Dados

• Compostaporváriasunidadesdeacesso– Bit,ByteePalavra;

– Posiçõesdememória.

Prof. Marco Câmara

31

Memória-Endereçamento

Cadaposiçãodememóriatemumendereçowsico

Referênciaúnicadeumaposiçãodememória

0 1 2 3 . . . . . .

m-1

0000 11111010 01000000 00001111 11110000 1111

0000 1011

Endereço Conteúdo: Instrução ou Dado

tamanho da célula: 8 bits

número de posições de

memória endereçáveis:

m

Prof. Marco Câmara

32

Memória-Tipos

• Fisicamente,existemdoisHpos:– RAM,oumemóriadeleituraeescrita

• EstáHcaXDinâmica;

• Amaiscomumenteespecificadaemanipulada;

• Definidabasicamentepelacapacidadeebarramento(performance).

– ROM• EPROM,EEPROM,Flash

33

TiposdeRAM

• SRAM(Sta-cRAM)– Construída com semicondutores;– Usa circuitos flip-flop para

armazenar cada bit de memória, logo mantém as informações enquanto existir fonte de energia;

– Muito rápida; – Cara e complexa (6 transistores),

logo não é usada em grandes volumes.

• DRAM(DynamicRAM)– Armazena cada bit em um

capacitor conectado a UM transistor;

– O capacitor perde carga rapidamente, logo a memoria precisa ser “lembrada”;

– Simples e de baixo custo, compõe o maior volume da memorial usada nos computadores atuais.

34

Memória-Operação

• InterligaçãoMemória-Processador– Registradoresdeusoespecífico:

•MemoryAddressRegister-MAR-REM

•MemoryDataRegister-MDR-RDM

Prof. Marco Câmara

35

Memória-Operação

• OperaçãodeLeituradaMemória– CPUarmazenaendereçodacélulaaserlidanoMAR

– CPUgerasinaldecontroleindicandoqueaoperaçãoédeleituradamemória

– Memóriarecuperainformaçãoarmazenadanaposiçãoendereçadaecolocanobarramentodedados,chegandoaoMDR

Prof. Marco Câmara

36

Memória-Operação

OperaçãodeGravaçãonaMemória– CPUarmazenaendereçodacélulaasergravadanoMAR

– CPUarmazenaainformaçãoasergravadanoMDR

– CPUgerasinaldecontroleindicandoqueaoperaçãoédegravaçãonamemória

– Memóriaarmazenainformaçãodobarramentodedadosnaposiçãoendereçada

Prof. Marco Câmara

37

MemóriaCache

• MemóriaCache– Memóriadealtavelocidade

– LocalizadaentreCPUeMemóriaPrincipal

– Aumentodedesempenhocomcustorazoável

– Algoritmo•Hitrate-taxadeacertos

– Interna(L1,ouprimária)xExterna(L2,ousecundária)

Prof. Marco Câmara

38

Memória

Prof. Marco Câmara

Per

form

ance

& C

usto

Capacidade

39

DisposiHvosdeE/S

• DisposiHvodeE/S

– Comunicaçãocommeioexterno

– MemóriaSecundáriaeInterfaceHomem-Máquina

• Barramentos– Conjuntodefiosparalelos

– InterligaCPU,PeriféricoseMemóriaPrincipal

Prof. Marco Câmara

40

Barramentos

• BarramentodeDados– NúmerodebitsporoperaçãodeE/SouacessoàMemória

– Processadoresde8,16,32ou64bits

– FluxoBi-direcional(leitura/gravação)

• BarramentodeEndereços– CapacidadedeArmazenamento=2n

– FluxoUni-direcional(CPU®MEMouE/S)Prof. Marco Câmara

41

Barramentos

• BarramentodeControle– Diversossinaisdecontrole

• Read/Write

• ControledeInterrupções

– FluxoUniouBi-direcional(dependedosinaldecontrole)

Prof. Marco Câmara

42

ConceitosdeSo|ware

Prof. Marco Câmara

43

ConceitosdeSo|ware

• Tradução– Necessidadedecodificarinstruçõesparamáquina

– Evolução• Programaçãoviapainéis

• Linguagensdeprogramação

– LinguagensdeProgramação• MaiorindependênciadoHW

• Maiorfacilidadededesenvolvimento/manutenção

Prof. Marco Câmara

44

Tradução

• LinguagensdeMontagem(Assembly)– Mnemônicosassociadosàsinstruçõesdoprocessador

– Específicaparacadaprocessador

– Montadores(Assembler)

Prof. Marco Câmara

45

Tradução

Programa Fonte

Programa Objeto

Tradutor

Linguagem de Montagem

Módulo Objeto

Montador

Linguagem de Alto Nível

Módulo Objeto

Compilador

Módulo Objeto

Programa Executável

Linker

Módulo Objeto

Módulo Objeto

Prof. Marco Câmara

46

Tradução

• LinguagemdeAltoNível– Semrelaçãodiretacomoprocessador

– Transportabilidade

– Pascal,Fortran,Cobol,VB,Java

– Compiladores

– Interpretadores

– CasoespecialdoJava:JVM

Prof. Marco Câmara

47

Tradução

• MódulosObjeto– Códigodemáquinanãoexecutável

– Referênciasamódulosexternosnãoresolvidas

• MódulosExecutáveis– Códigosdemáquinaexecutáveis

– Linkers• Bibliotecas

• RelocaçãoProf. Marco Câmara

48

ConceitosdeSo|ware

• Loader-Carregador

– Cargadoprogramanamemóriaparaexecução

– AbsolutoxRelocável

• Debugger-Depurador– Pesquisadeerrosdelógica

– Rastreamento

Prof. Marco Câmara

49

ConceitosdeSo|ware

• LinguagemdeControle– ComunicaçãoUsuáriocomoSO

• CaracterxGráfica

– InterpretadordeComandos-Shell

– ArquivosdeComandos

Prof. Marco Câmara

50

ConceitosdeSo|ware

• LinguagemdeMáquina– InstruçõesdoProcessador

• AcessoaosRegistradores/Memória

•Modosdeendereçamento

• Tiposdedados

Prof. Marco Câmara

51

ConceitosdeSo|ware

• LinguagemdeMáquina

– Programaemlinguagemdemáquina• Totalmentecodificadoembinário

• DiretamenteprocessadopelaCPU

• Nãorequertraduçãoourelocação• Nãopodeserexecutadoemoutrosprocessadores

Prof. Marco Câmara

52

ConceitosdeSo|ware

• Microprogramação– Cadainstruçãoemlinguagemdemáquinatemummicroprogramaassociado

– Omicroprogramaéformadoporváriasmicroinstruções

– Microinstruçõessãoexecutadaspelohardware

– ArquiteturaCISC

– Processadoresmicroprogramáveis• Aceitamnovasinstruções-novosmicroprogramas

Prof. Marco Câmara

53

MáquinadeNíveis

Dispositivos Físicos

Microprogramação

Aplicativos

UtilitáriosSistema Operacional

Linguagem de Máquina

Hardware

Programas Aplicativos

Programas do SO: Compiladores, Shell,

Editores de Texto

Prof. Marco Câmara

54

TiposdeSistemasOperacionais

• Monoprogramáveis/Monotarefa

• MulHprogramáveis/MulHtarefa

• MulHprocessados

Prof. Marco Câmara

55

TiposdeSistemasOperacionais

• SistemasMonoprogramáveis/Monotarefa– Todosrecursosdosistemadedicadosaumatarefa

– Execuçãodeprogramasseqüencialmente

– Usadonosprimeiroscomputadoresdegrandeporte

– Usadonosprimeiroscomputadoresdepequenoporte• SistemasMonousuário

Prof. Marco Câmara

56

TiposdeSistemasOperacionais

• SistemasMonoprogramáveis/Monotarefa– Sub-uHlizaçãodosrecursosdosistema

• ProcessadorXOperaçõesdeE/S

•Memória

• DisposiHvosdeE/S

– Implementaçãosimples

• Semrecursosdeproteção

Prof. Marco Câmara

57

TiposdeSistemasOperacionais

• SistemasMulHprogramáveis/MulHtarefa– RecursosdosistemacomparHlhadospordiversastarefas

– Execuçãodeprogramasconcorrentemente• AumentodaproduHvidade

• Reduçãodecustos• SuporteaSistemasMulHusuário

– ComparHlhamentonauHlizaçãodosrecursosdosistema• ProcessadorXOperaçõesdeE/S

• Memória

• DisposiHvosdeE/SProf. Marco Câmara

58

TiposdeSistemasOperacionais

• SistemasMulHprogramáveis/MulHtarefa– Implementaçãocomplexa

• Gerenciamentodosacessosconcorrentesaosrecursos

• Recursosdeproteção

– SistemasMonousuárioXMulHusuário•Mainframes

• ComputadoresPessoaiseEstaçõesdeTrabalho

Prof. Marco Câmara

59

TiposdeSistemasOperacionais

• SistemasMulHprogramáveis/MulHtarefa– SistemasdeTempoReal

• SemelhanteaosSistemasdeTempoComparHlhado

• Limitesrígidosparatempoderesposta

• SemfaHadetempo• Níveisdeprioridade

• Controledeprocessos(Indústrias,TráfegoAéreo)

Prof. Marco Câmara

60

TiposdeSistemasOperacionais

• MulHtarefa– ColaboraHva

• Windows95,98• NãoexistefaHadetempo

– PreempHva• Windows10eServer,Linux,MacOS,...• ExistefaHadetempo• Preempção

Prof. Marco Câmara

61

TiposdeSistemasOperacionais

• SistemasMulHprocessados– SistemascommaisdeumaCPUinterligada

• Execuçãosimultâneadeprogramas

• Supredificuldadenodesenvolvimentodeprocessadoresmaisrápidos

• IdealparasistemasquenecessitamusointensivodeCPU– Processamentocien�fico

Prof. Marco Câmara

62

TiposdeSistemasOperacionais

• SistemasMulHprocessados

– CaracterísHcas• MulHprogramação

– Aplicadaacadaprocessador• Escalabilidade

– Aumentodacapacidadecomputacional

• Reconfiguração– Tolerânciaàfalhaemalgumprocessador

• Balanceamento– Distribuiçãodecargadeprocessamento

Prof. Marco Câmara

63

TiposdeSistemasOperacionais

• SistemasMulHprocessados

– Classificação• Emfunção:

– daformadecomunicaçãoentreCPUs– dograudecomparHlhamentodamemóriaeE/S

• SistemasFortementeAcoplados– ProcessadorescommúlHplosnúcleos,porexemplo.

• SistemasFracamenteAcoplados– ServerCluster,porexemplo.

Prof. Marco Câmara

64

TiposdeSistemasOperacionais

• SistemasMulHprocessados– SistemasFortementeAcoplados

• ProcessadorescomparHlhamumúnicamemória– EspaçodeEndereçamentoÚnico– ÚnicoSO

MemóriaCPU

Dispositivos de E/S

CPU

Dispositivos de E/S

Prof. Marco Câmara

65

TiposdeSistemasOperacionais

• SistemasMulHprocessados– SistemasFracamenteAcoplados

» SistemasdeComputaçãoindependentes,masconectados(mulHcomputadores)

◆ ProcessamentoDistribuído◆ SOdeRede(SOR)XSODistribuído(SOD)

Memória CPU

Dispositivos de E/S

Memória CPU

Dispositivos de E/S

Link de Comunicação

Prof. Marco Câmara

66

TiposdeSistemasOperacionais

• MulHprocessamento

– Computadoresvistosoriginalmentecomomáquinasseqüenciais• Execuçãoseqüencialdasinstruçõesdoprograma

– SistemasMulHprocessados

• Paralelismo-Simultaneidade• Execuçãodeváriastarefasousub-tarefas

Prof. Marco Câmara

67

DefiniçãodeProcesso

• Umprogramaemexecução

• NãoéomesmoquePrograma(enHdadeestáHca)

– Programaéocódigoexecutável

– Processoéocódigoexecutando

• EnHdadedinâmica

– Ex.:Aexecuçãodeprog.exe3vezesgera3processosdisHntosdomesmoprograma

Prof. Marco Câmara

68

AmbientedeumProcesso

• Todoprocessoprecisater:

– Seçãodetexto

• Códigoexecutável

– Seçãodedados

• Variáveis,estruturas

– Pilhadoprocesso

• Parâmetrosetc

– Registradores,incluindoPC,SP,BPetc.

Prof. Marco Câmara

69

Conceitos

• ParaqueosprocessosexecutememambientemulHprogramado,existeagerênciade:

– ComparHlhamentodaCPU,dememória,E/Setc

• Nomenclatura

– SistemasBatch• Job

– SistemasdeTempoComparHlhado

• Tarefa(on-line)

Prof. Marco Câmara

70

EstadosdoProcesso

• Mudançasdeestadoduranteaexecução:– Iniciando

• Oprocessoestásendocriado– SOAlocaMemória,Contexto(BCP)

Ex.:OusuárioclicanumarquivoexecutávelnoExplorerouexecutaviaCMD

– Executando• Instruçõesdoprocessoestãosendoexecutadas

– Bloqueado• Oprocessoestáesperandoalgumeventoexterno

Prof. Marco Câmara

71

EstadosdoProcesso

• Mudançasdeestadoduranteaexecução:– Pronto

• Oprocessoestáaguardandochancedeserexecutadonoprocessador

– Terminando

• Oprocessoestáfinalizandosuaexecução

Prof. Marco Câmara

72

EscalonamentodeProcessos

Prof. Marco Câmara

InícioPronto

Bloqueado

Execução

Terminado

73

ControledeProcesso

• BlocodeControledeProcesso(BCP)– ÁreadeMemóriaalocadapeloSOparagerenciarprocessos

– Mantéminformaçõessobreoprocesso• Estadodoprocesso

• RegistradoresdaCPU,incluindooPC• Informaçõesparaescalonamento

• Informaçõesparagerenciamentodememória

• Informaçõesdecontabilização

• InformaçõessobreoperaçõesdeE/S

• PonteirosparaArquivos,SocketetcProf. Marco Câmara

74

Aula03

75

TrocadeContexto

• Preempção

– AçãodereHrarumprocessodaCPUaqualquerinstanteerestaurá-locomosenadaHvesseocorrido

• SuportadoporInterrupções(comopeloCLOCK)epeloBCP– Ex.:PreempçãoportempodeQuantum– PreempçãoporI/O,Prioridadeetc.

• Tempodatrocaéconsideradooverhead

• TempodependedesuportedehardwareecomplexidadedoSO

Prof. Marco Câmara

76

EscalonamentodeProcessos

• Manutençãodefilasparacontroledosprocessos

– FiladeProcessos–todosprocessosnosistema

– FiladePronto–processosprontos

– FilasdeBloqueado-processosaguardandoE/SdedisposiHvo(interrupção)ousinal• MúlHplasFilas–umapordisposiHvo

– FiladeDisco,FiladeCD,FiladeTeclado,deRede

– BCPefetuaoencadeamentonasfilas

– ProcessospassamporváriasfilasProf. Marco Câmara

77

Escalonadores

• Classificaçãodeprocessos:– I/O-BOUND–IntensivamenteconsumidordeE/S

• PassamaistempofazendooperaçõesdeE/SdoqueuHlizandoaCPU– ProcessosComerciais

– CPU-BOUND–IntensivamenteconsumidordeCPU• PassamaistempoefetuandocálculosdoqueE/S

– ProcessosCien�ficos/MatemáHcos

– Híbrido

Prof. Marco Câmara

78

Escalonadores

• CombinaçãoadequadadeprocessosCPUeI/OBOUNDmelhoraodesempenhoeflexibilidadedosistema– ProcessointeraHvo(Ex.:InternetExplorer)

• TipicamenteI/OBound

Prof. Marco Câmara

79

AlgoritmodeEscalonamentodeCPU

• AlgoritmodoS.O.quedeterminaqualopróximoprocessoaocuparaCPU– ExecutadoquandoocorreestourodeQuantumouinterrupçãodoprocesso(I/O,Evento,Sinaletc.)ouoprocessoacaba;

• CritériosmudamcomcaracterísHcasdosProcessos– Batch,CPUBound,I/OBound,InteraHvos

Prof. Marco Câmara

80

MetasdoEscalonamento

• Eficiência– ManteraCPUocupada100%dotempo

• Throughput– Maximizaronúmerodeprocessos(tarefas,jobs)executadosemumdadointervalodetempo

• Turnaround– Minimizarotempodeumprocessonosistema,desdeseuinícioatéotérmino• Tempomédiodeexecução• FundamentalaprocessosBatch Prof. Marco Câmara

81

MetasdoEscalonamento

• Igualdade

– TodoProcessotemdireitodeocuparaCPU

• Tempoderesposta

– MinimizarotempodecorridoentreasubmissãodeumpedidoearespostaproduzidanumprocessointeraHvo

Prof. Marco Câmara

82

ConflitoentraMetas

• Atenderaumametapodeprejudicaroutra– QualqueralgoritmodeescalonamentofavoreceráumHpodeprocesso(CPUBound,I/OBound,TempoReal,etc)emdetrimentodeoutros

– Opropósitoprecisasergeral

Prof. Marco Câmara

83

TiposdeEscalonamento

– Escalonamentonão-preempHvo• EscalonamentoCooperaHvo;

• ProcessomantémaCPUatéterminarouE/S;

• Nãorequerrecursosespeciaisdehardware– NãoexisteQuantum(devoluçãovoluntáriadocontroleaoS.O.)

• NocasodoWindows,uHlizadoatéaversão3.x.

– EscalonamentopreempHvo• RequertemporizadornaCPU(faHadequantumouUsodoclock);

• RequersuportedoSOparacoordenaracessoadadoscomparHlhadosdeformaconsistente(proteção).

Prof. Marco Câmara

84

FreqüênciadeprocessosporduraçãodesurtodeCPU

Prof. Marco Câmara

85

EscalonamentoFIFO

• FirstComeFirstServed(FCFS,FIFO,PEPS)

– NãopreempHvo

Processo Início Duração (ut)

P1 0 24

P2 0 3

P3 0 3

Prof. Marco Câmara

86

EscalonamentoFIFO

• Ordemdechegadadosprocessos:

P1,P2,P3

• DiagramadeGan�

P1 P2 P3

24 27 300

Prof. Marco Câmara

87

EscalonamentoFIFO

• Temposdeespera P1=0

P2=24

P3=27

Dica:TempodeEsperaéotempoqueoprocessopassanoestadodePronto.

• Tempomédiodeespera

(0+24+27)/3=17

Throughput = 0,1 (3/30)

Prof. Marco Câmara

P1 P2 P3

24 27 300

88

EscalonamentoFIFO

• Temposdesaída P1=24

P2=27

P3=30

• Tempomédiodesaída(24+27+30)/3=27

Prof. Marco Câmara

P1 P2 P3

24 27 300

89

EscalonamentoSJF

• Outraordemdechegada

P2,P3,P1

• DiagramadeGan�

P1P3P2

63 300

Prof. Marco Câmara

90

EscalonamentoSJF• FIFOordenado(SJF/MPP)

– MenorProcessoPrimeiro

• Menortempodeexecução

• Temposdeespera

TEP1=6;TEP2=0;TEP3=3

• Tempomédiodeesperamelhora

(6+0+3)/3=3

• Tempomédiodeesperanãoémínimo

– Podevariarmuito(comossurtosdeCPU)

• EfeitoComboio

– ProcessosI/OboundesperamporCPUboundProf. Marco Câmara

P1P3P2

63 300

91

EscalonamentoSJF

• TemposdesaídaP1=30;P2=3;P3=6

• Tempomédiodesaídamelhora (30+3+6)/3=13

• Tempomédiodesaídanãoémínimo– Podevariarmuito(comossurtosdeCPU)

Prof. Marco Câmara

P1P3P2

63 300

92

EscalonamentoSJF

• Shortest-Job-First(MenorJobPrimeiro)– Deveriaser“próximosurtodeCPUmenorprimeiro”

PID Início Duração de surto

P1 0 6P2 0 8

P3 0 7

P4 0 3

Usado para Processos batch. Sua execução diária permite determinar seu tempo total.

Prof. Marco Câmara

93

EscalonamentoSJF

• Temposdeespera

P1=3;P2=16;P3=9;P4=0

P1 P3 P2

3 160

P4

9 24

Prof. Marco Câmara

94

EscalonamentoSJF

• Tempomédiodeesperamelhora

(3+16+9+0)/4=7

ParaFIFO,nestasituação,seria10,25=(0+6+14+21)/4

• Tempomédiodeesperaémínimo

– Algoritmoconsideradoó'mo

Prof. Marco Câmara

P1 P3 P2

3 160

P4

9 24

95

EscalonamentoSJF

• Problema:determinaçãoexatadaduraçãodopróximosurtodeCPUéimpossível– SJFéusadoparaescalonamentodejobsemsistemasbatch• UsuárioespecificaotempodeCPUdojob

– EmescalonamentodeCPUéusadaesHmaHva• Baseadanaduraçãodossurtosanteriores

– Médiaexponencial

Prof. Marco Câmara

96

PreempçãoemSJF

• NãopreempHvo– ProcessousaCPUatécompletarsurto

• PreempHvo– Novoprocessoprontocomsurtoprevisto(TA)

– Temporestanteprevistoparaoprocessoemexecução(TB)

– SeTA<TB⇒preempçãoporprioridade

– Shortest-Remaining-Time-First(SRTF)Prof. Marco Câmara

97

PreempçãoemSJF

Processo Instante de chegada Duração de surto

P1 0 7

P2 2 4

P3 4 1

P4 5 4

Prof. Marco Câmara

98

PreempçãoemSJF

• SJFnãopreempHvo– Tempodeesperamédio=(0+6+3+7)/4=4

• TEP1=0 TEP2=6(8-2)

• TEP3=3 TEP4=7

P1 P3 P2

73 160

P4

8 12

Prof. Marco Câmara

99

PreempçãoemSJF

• SJFnãopreempHvo– Tempodesaídamédio=(7+10+4+11)/4=8

• TSP1=7 TSP2=10

• TSP3=4 TSP4=11

P1 P3 P2

7 160

P4

8 12

Prof. Marco Câmara

100

SRTFPreempHvo-TabeladeEstados

Prof. Marco Câmara

101

SJFPreempHvo

• Qualotempomédiodeespera?

• Qualotempomédiodesaída?

102

EscalonamentoRoundRobin

Prof. Marco Câmara

103

EscalonamentoRoundRobin

• Round-Robin(revezamentocircular)

– MétodoanHgoemuitosimples;

– CadaprocessorecebeumafaHadetempo(Quantum),eéescalonadoseguindoaordemdeumafilacircular;

– SistemaPreempHvo-InterrupçãodoClock

– SeoQuantumacabarantesdotérminodoprocesso(preempção),ouseomesmoforbloqueado,oprocessovaiparaofinaldafila.

Prof. Marco Câmara

104

EscalonamentoRoundRobin

• Resultados�picos:

– Eliminaproblemasdestarva-on;

– Tempodeesperamédioélongo;

– TempodesaídamaiorqueSJF;

– TempoderespostamelhorqueSJF;

– Quantumgrande->FIFO;

– Quantumpequeno->Baixaeficiênciadevidoaoexcessodetrocasdecontexto.

Prof. Marco Câmara

105

EscalonamentoRoundRobin

• Análisedaeficiência

– Comquantumqen+1processosprontos:• Tempomáximodeespera:n*q

• Umexemplo– Suponhaumafiladeprontocom100processos,Quantumde

100ms(valor�pico);

– UmprocessointeraHvoexecuta,fazumarequisição,vaiparabloqueadoedeláparaofimdafila

• QuandoarespostaseráentregueaousuáriodoprocessointeraHvo?

Prof. Marco Câmara

106

EscalonamentoporPrioridade

• Cadaprocessotemumaprioridade

– Númerointeirodentrodelimites(0a7/0a4095)

– Menor(oumaior)número⇒maiorprioridade

• Empate⇒RoundRobin,FCFS

• Starva-on–Estagnação

– Bloqueioportempoindefinido

– Soluções:

• Decrementaprioridadeacadacicloemexecução;

• aging(envelhecimento)

Prof. Marco Câmara

107

EscalonamentoporPrioridade

• Prioridade– Definidainternaouexternamente;– EstáHcaouDinâmica;– AlgunsSO(Unix)permitemdefinirprioridadeaumprocesso(comandonice);

– SOpode,porexemplo,aumentarprioridadedeprocessosI/OBound;•Ex:Prioridade=1/fraçãoQuantumuHlizada

– SJF:casoespecialdeprioridade?

• Pode-seclassificarprocessosporclassesdeprioridade,e,dentrodecadaclasse,usaroutroalgoritmodeescalonamento.

Prof. Marco Câmara

108

EscalonamentoporMúlHplasFilas

– EscalonamentopreempHvoentrefilas

• Prioridadefixa:sóatendefilasmenosprioritáriasseasdemaisesHveremvazias

• Timeslice80%paraforegroundcomRRe20%parabackgroundcomFIFO

Prof. Marco Câmara

109

EscalonamentoporMúlHplasFilas

Prof. Marco Câmara

110

EscalonamentoporMúlHplasFilas

• FilascaracterizadaspelossurtosdeCPUdosprocessos

– I/OboundeinteraHvoscommaisprioridade• PassamamaiorpartedotempoBloqueados

– Processospodemmudardefila

– Agingpodeserfacilmenteimplementado

• AlgoritmopreempHvo

Prof. Marco Câmara

111

EscalonamentocomMúlHplosProcessadores

• EscalonamentodeCPUmaiscomplexo

– ExistemsistemascombarramentodeE/SprivaHvodedeterminadoprocessador

• Váriasfilasdeprocessosprontos– Possibilidadededesperdícioderecursos

Prof. Marco Câmara

112

EscalonamentocomMúlHplosProcessadores

• Únicafiladeprocessosprontos– SymmetricMul-processing(SMP)

• Cadaprocessadorfazseuescalonamento

• ComparHlhamentodeestruturasdedadosdoSO– Sincronização

– AssymmetricMul-processing

• Escalonamentonoprocessadormestre

Prof. Marco Câmara

113

EscalonamentodeTempoReal

• SistemasdetemporealcríHco– Limitesrígidosdetempo– SOgaranteexecuçãonotempoourejeita– Exigeso|wareespecialehardwarededicado

114

EscalonamentodeTempoReal

• Sistemasdetemporealnão-críHco– ProcessoscríHcoscomprioridade

• Geradesbalanceamentodosistema– SuportedoSO

• Escalonamentocomprioridade• NãodegradaçãodaprioridadedosprocessoscríHcos• Latênciadecargapequena

– ChamadasaosistemaeoperaçõesdeE/S– Pontosdepreempçãoseguros– TodoKernelpreemp�vel(sincronização)– Protocolodeherançadeprioridade

115

EscalonamentodeTempoReal

• DispatchLatency– DescreveaquanHdadedetempoqueumsistemagastapararesponderàrequisiçãodeumprocesso

– Otempoderesposta(TR)totalconsisteem:• TRdeInterrupção• Dispatchlatency• TRdaaplicação

116

EscalonamentodeTempoReal117

SincronizaçãodeProcessos

• Éumproblemainerenteàgestãoderecursos;

– AcessosimultâneoarecursosqueprecisamsercomparHlhados;

– Podegerarstarva-on,dead-lockouinconsistência.

118

SincronizaçãodeProcessos

• Starva-on– PolíHcadeescalonamentoisolaumoumaisprocessos,quenuncasãoescalonados;

– AlgoritmosespecíficospermitemotratamentodesteHpodefalha.

119

SincronizaçãodeProcessos

• Dead-Lock– ProcessoP1bloqueiarecursoR1paraseuuso;

– ProcessoP2bloqueiarecursoR2paraseuuso,eébloqueadoaguardandoliberaçãodeR1;

– ProcessoP1ébloqueadoaguardandoR2.

120

SincronizaçãodeProcessos

• Inconsistência:– Doisoumaisprocessosacessamamesmabasededados,ealteramdadossimultaneamente;

– Exemplos:• ProcessoAtotalizaocampoXdetodososregistros,enquantoqueoProcessoBalteraoconteúdoderegistrosjácontabilizadospeloProcessoA->Somainconsistente?

• Processosquemanipulaminformaçõesdeformacoordenadasãointerrompidosnomeiodeumaatualização.Dadosinconsistentes?

121

SincronizaçãodeProcessos

• Problemasclássicos

– Produtor/Consumidor;

– Ojantardosfilósofos.

122

SincronizaçãodeProcessos

• Produtor/Consumidor

– DoisprocessoscomparHlhamumbufferdetamanholimitado

• Oprocessoprodutor:

– Produzumdado

– Inserenobuffer

– Voltaagerarumdado

• Oprocessoconsumidor:

– Consomeumdadodobuffer(umporvez)

123

SincronizaçãodeProcessos

• Produtor/Consumidor

• Oproblemaé:

• ComogaranHrqueoprodutornãoadicionarádadosnobufferseesteesHvercheio?

• ComogaranHrqueoconsumidornãovairemoverdadosdeumbuffervazio?

• Asoluçãonãoétrivial,poisosprocessospodemserinterrompidos!Oqueaconteceriase,antesdeconcluiroincrementodeumcontador,oprocessofosseinterrompido,eocontadorfossedecrementadopelooutroprocesso?

124

SincronizaçãodeProcessos

• Ojantardosfilósofos

– Hácincofilósofosemtornodeumamesa;

– Umgarfoécolocadoentrecadafilósofo;

– Cadafilósofodeve,alternadamente,refleHrecomer;

– Paraqueumfilósofocoma,eledevepossuirdoisgarfos

– Osdoisgarfosdevemseraqueleslogoasuaesquerdaeasuadireita;

– OgarfosomentepodeserpegosenãoesHveremusopornenhumoutrofilósofo;

– Apóscomer,ofilósofodeveliberarogarfoqueuHlizou;

– UmfilósofopodesegurarogarfodasuadireitaouodasuaesquerdaassimqueesHveremdisponíveis,massópodecomeçaracomerquandoambosesHveremsobsuaposse.

125

Sincronização-ExclusãoMútua

• ComotrataroacessoarecursosglobaiscomparHlhados,cominstruçõesintercaladaspeloescalonador,foradocontroledoprogramador?

• Acessorealizadodeformaatômica

ModelodePrograma:

{***

SeçãoNãoCríHca;

ProtocoloDeEntrada;

SeçãoCríHca;

ProtocoloDeSaída;

****

}

126

Sincronização-ExclusãoMútua

• AsessãocríHcaéumtrechodocódigoquedeveserexecutadodeformaatômica,semaintercalaçãocomoutroprocesso;

• Metas:

• APENASUMprocesso/threadestaránasuasessãocríHcadecadavez,ouseja,deveráserexecutadosobexclusãomútua;

• Umprocesso/threadnãopodeserinterrompidoouentraremloopdentrodosprotocolosdeentrada/saídaounasessãocríHca;

• Nenhumprocesso/threadforadasessãocríHcapodebloquearoutroprocesso/thread;

127

ThreadsConcorrentes

• Thread1 ...

while(chave==0); chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 1

Ex

PrBl

T1

T2

128

ThreadsConcorrentes

• Thread1

... while(chave==0); chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 0

Ex

PrBl

T1

T2

129

ThreadsConcorrentes

• Thread1 ... while(chave==0);

chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 0

Ex

PrBl

T1

T2

PreempçãoPortempo

130

ThreadsConcorrentes

• Thread1 ...

while(chave==0); chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

A thread 2 vai passar todo o tempo de quantum testando se chave = 0.

Chave = 0

Ex

PrBl

T2

T1

131

ThreadsConcorrentes

• Thread1

... while(chave==0); chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 0

Ex

PrBl

T1

T2

132

ThreadsConcorrentes

• Thread1 ... while(chave==0);

chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 1

Ex

PrBl

T1

T2

133

ThreadsConcorrentes

• Thread1 ...

while(chave==0); chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 1

Ex

PrBl

T1

T2

PreempçãoPortempo

134

ThreadsConcorrentes

• Thread1

... while(chave==0); chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 1

Ex

PrBl

T2

T1

135

ThreadsConcorrentes

• Thread1 ... while(chave==0);

chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 0

Ex

PrBl

T2

T1

136

ThreadsConcorrentes

• Thread1 ...

while(chave==0); chave=0; RC chave=1; ...

⬥ Thread 2 ... while (chave = = 0); chave = 0; RC chave = 1; ...

Chave = 0

Ex

PrBl

T2

T1

137

Sleep-WakeUp

• Inseriroutraapresentação

138

Deadlock139

Deadlock

• Apreocupaçãocomaexecuçãosimultâneadeprocessosfez,napráHca,queumprocessoaguardasseotérminodaexecuçãodeoutro;

• Masoqueacontecequandodoisoumaisprocessosaguardamumpelosoutros?

140

Deadlock

Processo 1 Processo 2

Recurso A

Recurso B

141

DeadLock

• Condiçõesnecessárias:1. ExclusãoMútua;2. PosseeEspera;3. NãoPreempção;4. EsperaCircular.

• Ocorrênciaprecisasersimultânea– Seaomenosumanãoocorrer,nãohaveráDeadLock

142

DeadLock

• Condiçõesnecessárias:1. ExclusãoMútua;

•Apenasumprocessoporvezpodealocaremanipularumrecurso

2. PosseeEspera;3. Não-Preempção;4. EsperaCircular.

143

DeadLock

• Condiçõesnecessárias:1. ExclusãoMútua;2. PosseeEspera;

•Umprocesso,depossedeumrecurso,podesolicitarnovosrecursos

3. Não-Preempção;4. EsperaCircular.

144

DeadLock

• Condiçõesnecessárias:1. ExclusãoMútua;2. PosseeEspera;3. Não-Preempção;

•Umrecursonãopodeserremovidoexplicitamentedoprocesso

4. EsperaCircular.

145

DeadLock

• Condiçõesnecessárias1. ExclusãoMútua;2. PosseeEspera;3. Não-Preempção;4. EsperaCircular.

• OcorreCICLOnoGRAFOdealocação

146

DeadLock

• Comousarrecursos:1. SolicitarRecursoaoS.O.2. SeoRecursoesHverLIVRE

ALOCARRECURSO3. Senão:

BLOQUEARPROCESSO4. ApósUso:

LIBERAPROCESSO

147

Soluções

– Ignoraroproblema(“AlgoritmodoAvestruz”);• Linux,Unix,Windows

– DetectareRecuperar;

– Evitardinamicamentesuaocorrência,comalocaçãocuidadosaderecursos;

– ImpediroDeadlockatravésdanegaçãodepelomenosumadas4condiçõesnecessáriasparasua

ocorrência.

148

DetectareRecuperar

• DetecçãocomumrecursodecadaHpo– MontarGrafo

• Sehouverciclo->DEADLOCK

– AnalisargraudemulHprogramação• Taxadebloqueioetempodeespera

• Comorecuperar?– Extermínio;– VoltaaoPassado.

• DetecçãoXRecuperação

149

DetectareRecuperar

• Extermínio– Mataumprocessonociclo;– Critériodeescolhadoprocesso:

• Aleatório;• Prioridade;• TempodeCPU;• NúmerodeRecursosAlocados.

150

DetectareRecuperar

• VoltaaoPassado– Rollbackemprocessodocicloatéliberarorecurso

• P1---|R2|------|------|R1|------|-------|----• P2---|------|R1|------|------|R2|-------|----• P2éalvo

– DesfazerP2atéantesdealocarR1•Custo?•Quemimplementa?Ex.SGBD

151

ComoEvitarDeadlock

• AlgoritmodoBanqueiro– EmprésHmoXReserva

– Qualo$queobancoempresta?– EstadoSeguro

• ProbabilidadedeDeadlock=0%

• VetoreseMatrizes– VetordeRecursosExistentes(VRE);– VetordeRecursosDisponíveis(VRD);– MatrizdeRecursosAlocados(MRA);– MatrizdeRecursosRequisitados(MRR);– MatrizdeRecursosPossivelmenteNecessários.

152

ImpedirDeadlock

• ExclusãoMútua– Impressora

• FiladeImpressão-Finita• Problema:eseafilaencher?

– Retardaroproblema

• PosseeEspera– Requisitartodososrecursospossivelmentenecessáriosnumsópassoeantecipadamente

• Atomicidade:oualocatodosounenhum– Problemas:

• PodealocarrecursosquenãoserãouHlizados;• PodeatrasaremfunçãodademoraparaliberaçãoderecursosquenãoserãouHlizadosdeimediato;

• S.O.precisamanterquanHdadealtaderecursosdomesmoHpoparamanterconcorrência.

153

ImpedirDeadlock

• PosseeEspera– Priorizarrecursos,numerando-os;– Requisitarrecursosporordemdeprioridade;– Wait-Die(WD)nãopreempHvo

• QuandoPquerrecursoalocadoaQ,eleesperaseformaisvelho.Casocontrário,Pmorre;

– Wound-Wait(WW)preempHvo• QuandoPquerrecursoalocadoaQ,eleaguardaapenasseformaisnovo.Casocontrário,Qmorre;

– Problemas:• PodealocarrecursosquenãoserãouHlizados;• PodeatrasaremfunçãodademoraparaliberaçãoderecursosquenãoserãouHlizadosdeimediato.

154

GerênciadeMemória

• ProgramassóexecutamseesHveremnamemóriaprincipal;

• FunçõesdoGerenciadordeMemória:– Controlaralocaçãodeprocessos;

• Novosprocessos;• MúlHplosprocessos;• Términodeprocesso;• Crescimentoediminuição

– DadosePilha

155

GerênciadeMemória

• Modelos– ParHções

• EstáHcas(Fixas)• Dinâmicas(Variáveis)

– Swapping – Paginação– Segmentação

156

GerênciadeMemória

• EndereçoLógicoXFísico– Problema:

• Usuáriocriaprograma.Ex.:prog1.c• OCompiladorgeracódigointermediário

– Cl–cprog1.c» prog1.obj

• EssecódigogeraExecutável?– Nãoépossívelencontraroendereçodafunçãosoma().

#include <stdio.h>

void main() { int x; x = soma (10, 20); printf("X = %d", x); }

157

GerênciadeMemória

• EndereçoLógicoXFísico– Problema:

• Usuáriocriaprograma.Ex.:soma.c• OCompiladorgeracódigointermediário

– Cl–csoma.c» soma.obj

• EssecódigogeraExecutável?– Nãoépossívelencontraroendereçodeiníciodeexecução➔ main().

int soma(int x, int y) { return x + y; }

158

GerênciadeMemória• EndereçoLógicoXFísico

– Comogerarprog1.exe?•Compilando-oseligando-os:Clprog1.csoma.c

• EndereçoLógicoXFísico– Todoprocessoreferenciaendereçológico– Ocompiladornãosabeondeoprogramavai

executarnamemória• Logo,seuprimeiroendereçoé0• Oquesignificachamarsoma()?

– ExecutarumCALLparaseuendereçodememória» Endereçológico

159

AlocaçãodeMemória

• AlocaçãoCon�gua– Divisãodamemória

• SOresidente– Códigoedados(tabeladevetores,buffers,etc)

• Processosdeusuários– Proteção

• Registradorderelocação:menorendereço• Registradordelimite:maiordeslocamento• Cadaprocessotemseusvalores(trocadecontexto)

160

GerênciadeMemória

• AlocaçãoCon�guaSimples– ParHçãoFixa– Implementadanosprimeirossistemaseaindausadanosmonoprogramáveis (monotarefa);

– Memóriaédivididaemduasáreas:• SistemaOperacionaleprocessodousuário;

– Usuárionãopodeusarumaáreamaiordoqueadisponível;

– Semproteção.

161

GerênciadeMemória

• AlocaçãoCon�guaSimples

Sistema Operacional

Área para Processo

do usuário

Memória Principal Registrador Base

Registrador de proteção delimita as áreas do sistema operacional e do usuário; Sistema verifica acessos à memória em relação ao endereço do registrador.

Registrador Limite

162

GerênciadeMemória

• AlocaçãoCon�guaSimples

Sistema Operacional

Área para Processo

do usuário

0

800K

1024K Nesse modelo, o SO foi carregado na memória alta. Se o processo faz referência ao endereço real 2050, ele lhe pertence. Registrador Base = 0K Registrador Limite = 800K

Suponha que prog1.c executando referencie o endereço lógico 100. Qual o endereço físico? Resp: 0K + 100

Nesse caso, o endereço lógico coincide com o físico.

163

GerênciadeMemória

• AlocaçãoCon�guaSimples

Sistema Operacional

PROG1.C

0

800K

1024K O maior endereço lógico referenciável por PROG1.C é 800K -1, pois além disso a aplicação invadiria o espaço reservado para o SO.

O espaço de endereços de PROG1.C é [0, 800K)

164

GerênciadeMemória

• AlocaçãoCon�guaSimples

Sistema Operacional

Área para Processo

do usuário

0

300K

1024K Nesse modelo, o SO foi carregado na memória baixa.

Registrador Base = 300K Registrador Limite = 724K

Suponha que PROG1.C referencie o endereço lógico 100, por exemplo. Nesse caso, o endereço físico seria 300K + 100.

O endereço lógico NÃO coincide com o físico.

165

GerênciadeMemória

• AlocaçãoCon�guaSimples

Sistema Operacional

PROG1.C

0

300K

1024K O maior endereço lógico referenciável por PROG1.C é [724K -1], pois além disso ele sairia da memória.

O espaço de endereços físicos de PROG1.C é [300K, 1024K)

O espaço de endereços físicos do SO é [0, 300K)

166

AlocaçãodeMemória

CPU

Registrador de LIMITE (Tamanho da Partição)

Registrador de relocação (BASE)

Memória

EL < LIMITE +endereço

lógico sim

não

endereço físico

exceção: erro de endereçamento

167

AlocaçãodeMemória

CPU

LIMITE 200K BASE

300K

5000 < 200K +EL = 5000 sim

não

5000 + 300K

exceção: erro de endereçamento

SO

P1

150K

300K

500K

Processo P1 ➔ BASE = 300K e LIMITE = 200K

168

AlocaçãoCon�guaSimples

• Processosdeusuáriolimitadospelotamanhodamemóriaprincipaldisponível.

• Solução:– Dividiroprogramaemmódulosoupartes;– PermiHrexecuçãoindependentedecadamódulo,usandoamesmaáreadememória;

– Técnica:Overlay(sobreposição);

169

AlocaçãoCon�guaSimples

• Permiteaoprogramador“expandir”oslimitesdamemóriaprincipal;

• Overlay–ÁreadememóriacomumondemóduloscomparHlhammesmoespaço;

PROG.EXE 200KB

Cadastro.OVL 400KB

Relatório.OVL 350KB

Manutenção.OVL 420KB

170

ParHçõesFixas

• Evoluçãodossistemasoperacionaisdemandouusodamemóriaporváriosusuáriossimultaneamente;

• Memóriafoidivididaemáreasdetamanhofixo:parHções;– TamanhodasparHçõeseraestabelecidonoboot,emfunçãodo

tamanhodosprogramas;– ReparHcionamentodemandavanovobootcomanova

configuração.

• TiposdeAlocaçãoParHcionada:– AlocaçãoParHcionadaEstáHca:

• AbsolutaeRelocável;– AlocaçãoParHcionadaDinâmica.

171

EspaçodeEndereçamento

• EndereçoLógicoouVirtual– GeradopelaCPU– Espaçodeendereçamentológico

• EndereçoFísico– Enviadoàmemória

• CarregadonoREM(RegistradordeEndereçodeMemória)

– Espaçodeendereçamentowsico

172

EspaçodeEndereçamento

• MapeamentodoEspaçoVirtualparaFísico– Sóénecessárioseaassociaçãoéfeitaemtempodeexecução

– Usuáriotrataendereçoslógicos,nuncawsicos– Suportedehardware:MMU

•MemoryManagementUnit• Exemplo:Registradorderelocação

173

CPUMemória

Registrador de relocação

14000

+

MMU

endereço lógico

346

endereço físico

14346

EspaçodeEndereçamento

174

TécnicasdeGerenciamento

• CargaDinâmica– RoHnasnãosãocarregadasatéseremchamadas• RoHnasdeexceçãopodemnãoserchamadas

– MelhoruHlizaçãodoespaçodememória– NãoénecessáriosuportedoSO

175

TécnicasdeGerenciamento

• LigaçãoDinâmica– Aplica-seàsbibliotecasdosistema

• LigaçãoEstáHca– Todosmódulosfazempartedaimagemgerada

176

TécnicasdeGerenciamento

• LigaçãoDinâmica– BibliotecascomparHlhadas

• Trechodecódigo(stub)indicacomolocalizarnamemóriaoucarregardodisco– Endereçoficaarmazenadoparafuturasreferências

• Economiadeespaçoemdiscoenamemória• Atualizaçãodasbibliotecassemnovalinkedição

– RequersuportedoSO• Acessoaendereçosforadoslimitesdoprocesso

177

TécnicasdeGerenciamento

• Overlays– Sobreposiçãodedadoseinstruçõesdesnecessários

– Permitequeumprocessosejamaiorqueoespaçoalocadoaele

– Complexaresponsabilidadepassadaaoprogramador• Eventualsuportedecompiladores

178

AlocaçãodeMemória

• AlocaçãoParHcionadaEstáHca– ParHçõesFixas– SOs mulHprogramáveis–Ambientebatch – ParHções

• Porçõesdememóriadetamanhofixo• ControlaograudemulHprogramação

– TamanhodaparHçãoestabelecidonafasedeinicializaçãodosistema(boot)

– SOmantémFiladeEntradaeTabeladeParHções

179

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K2 174K 150K3 324K 250K4 574K 450K

SO

P1

10K

P2

40K

P3

70K

P4

110K

P5

130K

P6

180K

P7

260K

P8

300K

180

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P1 10K2 174K 150K

3 324K 250K4 574K 450K

SO

P1

P2

40K

P3

70K

P4

110K

P5

130K

P6

180K

P7

260K

P8

300K

181

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P1 10K2 174K 150K P2 40K3 324K 250K4 574K 450K

SO

P1

P2

P3

70K

P4

110K

P5

130K

P6

180K

P7

260K

P8

300K

182

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P1 10K2 174K 150K P2 40K3 324K 250K P3 70K4 574K 450K

SO

P1

P2

P3

P4

110K

P5

130K

P6

180K

P7

260K

P8

300K

183

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P1 10K2 174K 150K P2 40K

3 324K 250K P3 70K4 574K 450K P4 110K

SO

P1

P2

P3

P4

P5

130K

P6

180K

P7

260K

P8

300KA alocação ocorreu por ordem do Escalonador,

sem avaliação da ocupação de memória.

184

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K2 174K 150K3 324K 250K4 574K 450K

SO

P1

10K

P2

40K

P3

70K

P4

110K

P5

130K

P6

180K

P7

260K

P8

300KComo seria a alocação pelo Gerenciador de

Memória?

185

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K2 174K 150K3 324K 250K4 574K 450K

SO

P1

10K

P2

40K

P3

70K

P4

110K

P5

130K

P6

180K

P7

260K

P8

300K

186

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P2 40K2 174K 150K

3 324K 250K4 574K 450K

SO

P2

P1

10K

P3

70K

P4

110K

P5

130K

P6

180K

P7

260K

P8

300K

187

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P2 40K2 174K 150K P5 130K3 324K 250K4 574K 450K

SO

P2

P5

P1

10K

P3

70K

P4

110K

P6

180K

P7

260K

P8

300K

188

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P2 40K2 174K 150K P5 130K3 324K 250K P6 180K4 574K 450K

SO

P2

P5

P6

P1

10K

P3

70K

P4

110K

P7

260K

P8

300K

189

AlocaçãodeMemória

Tabela de Partições

Partição Base Limite Processo ID Tamanho Processo

0 0K 124K SO 124K1 124K 50K P2 40K2 174K 150K P5 130K

3 324K 250K P6 180K4 574K 450K P8 300K

SO

P2

P5

P6

P8

P1

10K

P3

70K

P4

110K

P7

260KA alocação ocorreu por ordem do Gerenciador de

Memória, sem avaliação da ocupação do Escalonador.

190

• Osproblemasserepetem:– SeogerenciadordememóriapriorizaamelhoralocaçãodaparHção,oqueacontecerácomprocessosmuitopequenos,dadoquenafilasempreexistemmaiores?• Inanição

– QuaisseriamasestratégiasparasoluçãodaInanição?

AlocaçãodeMemória191

SO

50K

150K

250K

450K

P1

10K

P2

40K

P370K

P4110K

P5130K

P6180K

P7260K

P8300K

• Múltiplas Filas • Quando P6 acabar, a partição

ficará ociosa. • Pode ocorrer de uma partição

ficar livre, enquanto outra tem muitos processos.

AlocaçãodeMemória192

• Filaúnicacomaging– Determina-seumcontadordesaltosKi(paracada

processoi)eumaconstanteN(idademáxima);– TodavezqueumaparHçãoficarlivre

• Procura-sepeloprocessoquedeixaomenorespaçodesperdiçado;

• Senafila,antesdele,houverumprocessoquecaibanamesmaparHção,incrementamosKi;

•SeKi=N,Pideveserexecutado,independentedotamanhodaparHção.

AlocaçãodeMemória193

EstratégiasdeAlocação

– Escolhadoblocoquedeveseralocadoaoprocesso– Váriosalgoritmospossíveis

• First-fit(Performance?)– Alocaprimeiroblocosuficientementegrande– Nãoprecisapesquisartodosblocos

• Best-fit(OcupaçãodeMemória?)– Alocaomenorblocosuficientementegrande– Precisapesquisartodosblocos

» AlternaHva:ordenaçãodosblocosportamanho– Geraomenorblocodememóriarestante

•Worst-fit(Realocação?)– Alocaomaiorbloco– Precisapesquisartodosblocos

» AlternaHva:ordenaçãodosblocosportamanho– Geraomaiorblocodememóriarestante

194

– Comoavaliar?– Simulação!

• First-fitebest-fituHlizammelhoramemória• First-fitémaisrápida

EstratégiasdeAlocação195

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória Processo

Bloco 1 (50k) Bloco 2 (200K) Bloco 3 (70K) Bloco 4 (115K) Bloco 5 (15K)

Tempo: -1

EstratégiasdeAlocação-BestFit196

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Bloco 2 (200K) Bloco 3 (70K) Bloco 4 (115K) Processo 1 Bloco 5 (15K)

Alocado

EstratégiasdeAlocação-BestFit

Tempo: 0

197

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Bloco 2 (200K) Bloco 3 (70K) Bloco 4 (115K) Processo 1 Bloco 5 (15K) Processo 2

AlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 0

198

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória Processo

Bloco 1 (50k) Processo 3 Bloco 2 (200K) Bloco 3 (70K) Bloco 4 (115K) Processo 1 Bloco 5 (15K) Processo 2

AlocadoAlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 0

199

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Processo 3 Bloco 2 (200K) Bloco 3 (70K) Processo 4Bloco 4 (115K) Processo 1 Bloco 5 (15K) Processo 2

Alocado – 15K em 70K !

AlocadoAlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 0

200

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Processo 3 Bloco 2 (200K) Processo 5Bloco 3 (70K) Processo 4Bloco 4 (115K) Processo 1 Bloco 5 (15K) Processo 2

Alocado – 23K em 200K !

AlocadoAlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 0

Alocado – 15K em 70K !

201

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória Processo

Bloco 1 (50k) Processo 3 Bloco 2 (200K) Processo 5Bloco 3 (70K)Bloco 4 (115K) Processo 1 Bloco 5 (15K)

AlocadoConcluído !

AlocadoConcluído !Alocado

EstratégiasdeAlocação-BestFit

Tempo: 1

202

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Processo 3 Bloco 2 (200K) Processo 5Bloco 3 (70K)Bloco 4 (115K) Processo 1 Bloco 5 (15K) Processo 6

AlocadoConcluído !

AlocadoConcluído !Alocado

Alocado

EstratégiasdeAlocação-BestFit

Tempo: 1

203

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Processo 3 Bloco 2 (200K) Processo 5Bloco 3 (70K) Processo 7Bloco 4 (115K) Processo 1 Bloco 5 (15K) Processo 6

AlocadoConcluído !

AlocadoConcluído !Alocado

AlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 1

204

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória Processo

Bloco 1 (50k) Bloco 2 (200K)Bloco 3 (70K)Bloco 4 (115K) Processo 1 Bloco 5 (15K)

Concluído !Concluído !

AlocadoConcluído !Concluído !

Concluído !Concluído !

EstratégiasdeAlocação-BestFit

Tempo: 2

205

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Bloco 2 (200K)Bloco 3 (70K) Processo 8Bloco 4 (115K) Processo 1 Bloco 5 (15K)

Concluído !Concluído !

AlocadoConcluído !Concluído !

Concluído !Concluído !

Alocado

EstratégiasdeAlocação-BestFit

Tempo: 2

206

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Bloco 2 (200K) Processo 9Bloco 3 (70K) Processo 8Bloco 4 (115K) Processo 1 Bloco 5 (15K)

Concluído !Concluído !

AlocadoConcluído !Concluído !

Concluído !Concluído !

Alocado

EstratégiasdeAlocação-BestFit

Tempo: 2

Alocado

207

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória Processo

Bloco 1 (50k) Bloco 2 (200K) Processo 9Bloco 3 (70K) Processo 8Bloco 4 (115K) Bloco 5 (15K)

Concluído !Concluído !

Concluído !Concluído !Concluído !

Concluído !Concluído !

AlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 3

208

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Bloco 2 (200K) Processo 9Bloco 3 (70K) Processo 8Bloco 4 (115K) Processo 10Bloco 5 (15K)

Concluído !Concluído !

Concluído !Concluído !Concluído !

Concluído !Concluído !

AlocadoAlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 3

209

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Bloco 2 (200K) Processo 9Bloco 3 (70K)Bloco 4 (115K) Processo 10Bloco 5 (15K)

Concluído !Concluído !

Concluído !Concluído !Concluído !

Concluído !Concluído !

Concluído !AlocadoAlocado

EstratégiasdeAlocação-BestFit

Tempo: 4

210

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória Processo

Bloco 1 (50k) Bloco 2 (200K)Bloco 3 (70K)Bloco 4 (115K) Processo 10Bloco 5 (15K)

Concluído !Concluído !

Concluído !Concluído !Concluído !

Concluído !Concluído !

Concluído !Concluído !Alocado

EstratégiasdeAlocação-BestFit

Tempo: 5

211

Processos Tamanho TurnaroundProcesso 1 100k 3Processo 2 10k 1Processo 3 35k 2Processo 4 15k 1Processo 5 23k 2Processo 6 6k 1Processo 7 25k 1Processo 8 55k 2Processo 9 88k 3Processo 10 100k 3

Bloco Memória ProcessoBloco 1 (50k) Bloco 2 (200K)Bloco 3 (70K)Bloco 4 (115K) Bloco 5 (15K)

Concluído !Concluído !

Concluído !Concluído !Concluído !

Concluído !Concluído !

Concluído !Concluído !Concluído !

EstratégiasdeAlocação-BestFit

Tempo: 6

212

AlocaçãoCon�gua

• FragmentaçãoExterna– Ocorrequandoosprogramasterminam– Nãoháespaçolivrecon�guosuficiente

Memória Principal

Sistema Operacional

Processo C

Processo A

4 KB

3 KB

1 KB

1 KB

2 KB

D6 KB

213