10 – Gerência de Memória Show 10.7 EXERCÍCIOS 132) Quais as funções básicas da gerência de memória? 133) Considere um sistema computacional com 40 KB de memória principal e que 134) Suponha que um sistema computacional de 64 KB de memória principal e que 135) Considerando o exercício anterior, se o módulo de 30 KB tivesse seu tamanho 136) Qual a diferença entre fragmentação interna e externa da memória principal? 137) Suponha um sistema computacional com 128 KB de memória principal e que 138) Considerando o exercício anterior, seria possível executar quatro programas 139) Qual a limitação da alocação particionada estática absoluta em relação à alo- 140) Considere que os processos da tabela a seguir estão aguardando para serem PROCESSOS MEMÓRIA
TEMPO Sistemas Operacionais – Lucilia Ribeiro 100 10 – Gerência de Memória 141) Considerando os algoritmos para escolha da partição dinamicamente, concei- 142) Considere um sistema que possua as seguintes áreas livres na memória prin- a) 12 KB b) 10 KB c) 9 KB 143) Um sistema utiliza alocação particionada dinâmica como mecanismo de gerên- 5 KB Programa A 3 KB Programa B 10 KB Livre 6 KB Programa C 26 KB Livre Realize as operações abaixo seqüencialmente, mostrando o estado da memória a) alocar uma área para o programa D que possui 6 KB; 144) O que é swapping e para que é utilizada essa técnica? 145) Por que é importante o uso
de um loader com relocação dinâmica para que a 146) Apresente o mapa de bits e o esquema de listas ligadas para o dois layouts de Sistemas Operacionais – Lucilia Ribeiro 101 10 – Gerência de Memória 147) Considere um sistema com swapping no qual os seguintes buracos estão na 148) Um minicomputador usa o sistema buddy para gerenciar sua memória. Inici- -x- Sistemas Operacionais – Lucilia Ribeiro 102 11 – Memória Virtual 11 Memória Virtual “Nunca deixe o inimigo perceber que você está sangrando.” (James Bond) 11.1 INTRODUÇÃO As implementações vistas anteriormente no gerenciamento de memória se mostra- Memória Virtual é uma técnica sofisticada e poderosa de gerência de memória, on- Outra
vantagem da técnica de memória virtual é permitir um número maior de pro- 11.2 ESPAÇO DE ENDEREÇAMENTO VIRTUAL O conceito de memória virtual se aproxima muito da A memória virtual utiliza abstração semelhante, só cessador manipula apenas posições da memória Como o espaço de endereçamento virtual não tem nenhuma relação direta com os endereços no espaço real, um programa pode fazer referência a endereços virtuais que estejam fora dos limites da memória principal, ou seja, os programas e suas estruturas de dados não estão mais limitados ao tamanho da memória física disponível. Para que isso seja possível, o Sistema Operacional utiliza a memória secundária como extensão da memória principal. Quando um programa é executado, so- mente uma parte do seu código fica residente na memória principal, permanecendo o Sistemas Operacionais – Lucilia Ribeiro 103 11 – Memória Virtual restante na memória secundária até o momento de ser referenciado. Esta condição per- No desenvolvimento de aplicações, a existência dos endereços virtuais é ignorada pe- 11.3 MAPEAMENTO O processador apenas executa instruções e referencia dados residentes no espaço de Nos sistemas atuais, o mapeamento é realizado por hardware juntamente com o Sis- Cada processo tem o seu espaço de en- Caso o mapeamento fosse realizado para Espaço de Tamanho Número Número de entradas Como veremos a seguir, existem Sistemas Operacionais que trabalham
apenas com 11.4 PAGINAÇÃO É a técnica de gerência de memória onde o espaço de endereçamento virtual e o real são divididos em blocos do mesmo tamanho chamados páginas. A definição do tama- nho da página é um fator importante no projeto de sistemas que implementam memó- ria virtual por paginação. O tamanho da página está associado à arquitetura do hardware e varia de acordo com o processador, mas normalmente está entre 512 e 16MB. Páginas Sistemas Operacionais – Lucilia Ribeiro 104 11 – Memória Virtual no espaço virtual são denominadas páginas virtuais, enquanto as páginas no espaço Todo o mapeamento de endereço virtual Nessa técnica, o endereço virtual é forma- Além da informação sobre a localização da Sempre que o processo referencia um en- está ou não na memória principal. Caso Sistemas Operacionais – Lucilia Ribeiro 105 11 – Memória Virtual Sistemas Operacionais – Lucilia Ribeiro 106 11 – Memória Virtual 11.4.1 PAGINAÇÃO MULTINÍVEL las de páginas pode ser um problema. Em uma arquitetura de 32 bits para endereçamen- Uma boa solução para contornar o problema é a utilização de tabelas de páginas Então, baseando-se nos
dados do sistema computacional e no layout da palavra de Sistemas Operacionais – Lucilia Ribeiro 107 11 – Memória Virtual Dessa forma, cada entrada do primeiro nível gerencia 4 MB de espaço e cada entrada A Figura abaixo apresenta um exemplo de funcionamento da MMU para o caso de ta- Como
exemplos práticos de hardware paginação pode-se citar: PDP-11 (paginação de 11.4.2 POLÍTICAS DE BUSCA DE PÁGINAS Determina quando uma página deve ser carregada para a memória. Basicamente, e- Sistemas Operacionais – Lucilia Ribeiro 108 11 – Memória Virtual Na paginação sob demanda, as páginas dos processos são transferidas da memória Na pré-paginação, o sistema
carrega para a memória principal, além da página re- 11.4.3 POLÍTICAS DE ALOCAÇÃO DE PÁGINAS Determina quantas molduras (frames) cada processo pode manter na memória prin- Na política de alocação fixa, cada processo tem um número máximo de molduras Apesar de sua simplicidade, a política de alocação fixa de página apresenta dois pro- Na política de alocação variável, o número máximo de páginas pode variar duran- 11.4.4 POLÍTICAS DE SUBSTITUIÇÃO DE PÁGINAS Em algumas situações, quando um processo atinge o seu limite de alocação de mol- O Sistema Operacional consegue identificar as
páginas modificadas através de um bit A política de substituição de páginas pode ser classificada conforme seu escopo, ou Na política de substituição local, apenas as páginas do processo que gerou a falta Já na política de substituição global, todas as páginas alocadas na memória prin- cipal são candidatas a substituição, independente do processo que gerou a falta de pági- Sistemas Operacionais – Lucilia Ribeiro 109 11 – Memória Virtual na. Na
verdade, nem todas as páginas podem ser candidatas a substituição. Algumas 11.4.5 WORKING SET Apesar de suas diversas vantagens, o mecanismo de memória virtual introduz um sé- O conceito de working set surgiu com o objetivo de reduzir o problema do trashing e O princípio da localidade significa, na prática, que o pro- A partir da observação do princípio da localidade, Peter Dentro da janela do working set, o número de páginas distintas referenciadas é co- O modelo de working set proposto por Denning possibilita prever quais páginas são Sistemas Operacionais – Lucilia Ribeiro 110 11 – Memória Virtual peracional deverá manter as páginas do working set de cada processo residente na me- 11.4.6 ALGORITMOS DE SUBSTITUIÇÃO DE PÁGINAS A melhor estratégia de substituição de páginas seria aquela que escolhesse uma mol- a) ÓTIMO: O melhor algoritmo de troca de páginas é fácil de descrever, mas impos- O algoritmo ótimo simplesmente diz que a página com o maior rótulo deve ser remo- O único problema com este algoritmo é que ele não é realizável. No momento da falta b) FIFO: Para ilustrar seu funcionamento, considere um supermercado que tem pra- Uma possibilidade é descobrir qual dos produtos este supermercado
vem estocando Em algoritmos de substituição de páginas, a mesma idéia pode ser aplicada. O siste- Sistemas Operacionais – Lucilia Ribeiro 111 11 – Memória Virtual c) Segunda Chance: Este algoritmo é uma variação do FIFO, a única diferença é que existe um bit “R” as- d) Relógio: O algoritmo da segunda chance está sempre movendo páginas do início para o final e) NUR (Not Recently Used): Para permitir que o sistema operacional colete estatísticas sobre quais
páginas estão Os bits R e M podem ser usados para construir um algoritmo de paginação simples Quando uma falta de página ocorre, o sistema operacional examina todas as páginas • Classe 0: não referenciada, não modificada • Classe 1: não referenciada, modificada • Classe 2: referenciada, não modificada • Classe 3: referenciada, modificada Ainda que as páginas na classe 1 pareçam, à primeira vista, impossíveis de existir, O algoritmo NRU remove uma página aleatória da classe de numeração mais baixa Sistemas Operacionais – Lucilia Ribeiro 112 11 – Memória Virtual As características principais do NRU é que ele é fácil de entender, eficiente de se
im- f) LRU (Least Recently Used): Uma boa aproximação para o algoritmo ótimo é baseada em uma observação comum Embora o algoritmo LRU seja teoricamente realizável, seu custo é alto. Para imple- Manipular uma lista ligada a toda instrução é proibitivo, até mesmo em hardware. En- Agora vejamos um segundo algoritmo LRU, também em hardware. Para uma máqui- Sempre que uma moldura k for referenciada, o hardware coloca todos os bits da linha Um exemplo do funcionamento deste algoritmo aparece ilustrada na figura para qua- Considerando-se o funcionamento dos algoritmos de substituição de páginas, é possí- Um exemplo de ocorrência da mencionada anomalia encontra-se detalhado na Figura 3.16, onde é utilizado o algoritmo de substituição de páginas FIFO que, inicialmente, é simulado com 3 page frames e apresenta 9 faltas de páginas. Em seguida, é realizada a Sistemas Operacionais – Lucilia Ribeiro 113 11 – Memória Virtual simulação do FIFO com 4 molduras de páginas e é observado que o número de falta de Dessa forma, é possível verificar a presença da anomalia de Belady, pois a memória Após a verificação da anomalia de Belady, muitos estudos foram desenvolvidos e foi Obs.: 1) O LRU é um algoritmo de pilha e não apresenta a anomalia de Belady; 2) O 11.5 SEGMENTAÇÃO É a técnica de gerência de memória Enquanto na técnica de paginação o Na segmentação, os endereços especificam o número do segmento e o deslocamento Sistemas Operacionais – Lucilia Ribeiro 114 11 – Memória Virtual Assim, para mapear um endereço virtual composto pelo par <segmento, deslocamen- A figura apresentada a seguir ilustra o funcionamento do mapeamento de um endere- Os segmentos podem se tornar muito grandes e, às vezes, pode ser impossível man- A seguir, um quadro comparando as técnicas de paginação e segmentação em função 11.6 SEGMENTAÇÃO PAGINADA É a técnica de gerência de memória onde o espaço de endereçamento é dividido em Na visão do programador, sua aplicação continua sendo mapeada em
segmentos de Sistemas Operacionais – Lucilia Ribeiro 115 11 – Memória Virtual 11.7 EXERCÍCIOS 149) Quais os benefícios oferecidos pela técnica de memória virtual? Como este 150) Explique como um endereço virtual de um processo é traduzido para um ende- 151) Por que o mapeamento deve ser feito em blocos e não sobre células individu- 152) Qual a principal diferença entre os sistemas que
implementam paginação e os 153) Diferencie página virtual de página real. 154) Para que serve o bit de validade nas tabelas de página? 155) Apresente o funcionamento binário da MMU de uma máquina hipotética para 156) O que é page fault , quando ocorre e quem controla a sua ocorrência? Como 157)
Descreva como ocorre a fragmentação interna em sistemas que implementam 158) Compare as políticas de busca de páginas apresentadas. 159) Quais as vantagens e desvantagens da política de alocação de páginas variável 160) Um sistema com gerência de memória virtual por paginação possui tamanho Sistemas Operacionais – Lucilia Ribeiro 116 11 – Memória Virtual endereçadas de 0 a 511 e memória real com 10 páginas numeradas de 0 a 9. o Endereço Fixo Conteúdo a) Considere que a entrada da tabela de páginas contém, além do endereço do b) Mostre o conteúdo da tabela de páginas após a página virtual 49 ser carre- c) Como é o formato do endereço virtual deste sistema? 161) Encontre o endereço físico correspondente aos seguintes endereços virtuais: a) 67.219.712 b) 113.819.552 c) 545.591.437 d) 416.219.160 0 Æ 4–8k 0 . Æ 8 – 12 k . Æ 44 – 48 k Sistemas Operacionais – Lucilia Ribeiro 117 11 – Memória Virtual 162) Um Sistema Operacional implementa gerência de memória virtual por pagina- Página Residente Frame a) Qual o endereço físico de uma variável que ocu- 1000 163) Um Sistema Operacional implementa gerência de memória virtual por pagina- a) (307)10 Página Endereço Físico 164) Uma memória virtual
possui páginas de 1024 endereços, existem 8 páginas Página Virtual Página Real a) Faça a lista/faixa de todos os endereços virtuais 165) Porque existe a necessidade de uma política de substituição de páginas? Com- 166) Para que serve o bit de modificação nas tabelas de páginas? 167) Como o princípio da localidade viabiliza a implementação da gerência de me- 168) Por que programas não estruturados estão sujeitos a uma alta taxa de pagina- 169) Cite os principais algoritmos de substituição de
páginas estudados. 118 11 – Memória Virtual 170) Explique o funcionamento do algoritmo de substituição de páginas NUR. 171) Explique o funcionamento do algoritmo de substituição de páginas da segunda 172) Informe a principal desvantagem de se utilizar o algoritmo de substituição de 173) Informe a principal vantagem que o algoritmo do relógio possui sobre o da se- 174) Considere uma máquina com três molduras de página (page frames), as quais 175) Considere uma máquina com quatro molduras de página (page frames), as 176) Considere uma máquina com quatro molduras de página (page frames), as quais estão inicialmente vazias, e uma seqüência de referência às páginas igual a: 0, 1, 2, 3, 0, 1, 4, 1, 2, 3, 1, 4, 5, 4 e 1. Assim sendo, informe, justificando sua resposta, quantas faltas de páginas serão geradas com a utilização de cada um dos algoritmos de substituição de páginas abaixo relacionados: a) FIFO b) LRU c) Segunda Chance 177) Qual é a principal desvantagem de se utilizar no projeto de um sistema pagi- 178) O que é a anomalia de Belady? 179) Considere um sistema com memória virtual por paginação com endereço vir- Página BV BM End. do Frame a) Quantos bits possui o campo desloca- 180) Considere um sistema de memória virtual que implemente paginação, onde o Sistemas Operacionais – Lucilia Ribeiro 119 11 – Memória Virtual 181) Em um sistema de memória virtual que implementa paginação, as páginas Página End. Físico a) Qual o tamanho (em bits) e o formato do endereço virtual? 182) Em um computador, o endereço virtual é de 16 bits e as páginas têm tamanho 183) Um
sistema trabalha com gerência de memória virtual por paginação. Para to- Número BV BM Endereço do
Responda às perguntas abaixo, conside- 5 10 654546 120 6 11 B6B7B0 7 11 999950 8 10 888BB8 9 00 N/A 10 0 0 N/A Sistemas Operacionais – Lucilia Ribeiro 11 – Memória Virtual a) Em quais instantes de tempo ocorrem um page out? 184) Um sistema possui quatro frames. A tabela abaixo apresenta para cada página Frame Carga Referência BR BM a) Qual pagina será substituída utili- 185) Considere um processo com limite de páginas reais igual a quatro e um siste- 186) O que é trashing? -x- Sistemas Operacionais – Lucilia Ribeiro 121 12 – Sistema de Arquivos 12 Sistema de Arquivos “Se o conhecimento pode criar problemas, não é através 12.1 INTRODUÇÃO O sistema de arquivos é a parte do Sistema Operacional mais visível para os usuá- É importante observar que sistemas de arquivos implementam um recurso em soft- 12.2 ARQUIVOS São recipientes que contém dados. Cada arquivo é identificado por um nome e por O Sistema Operacional suporta diversas operações sobre arquivos, como criação, Existe, na prática, uma enorme quantidade de diferentes tipos de arquivos, cada tipo Para o sistema operacional, cada arquivo corresponde a uma seqüência de bytes, cu- Como o conceito de tipo de arquivo é útil para os usuários, muitos sistemas operacio- 12.2.1 MÉTODO DE ACESSO O acesso a arquivos pode se dar de duas maneiras: Seqüencial: o conteúdo do arquivo pode ser lido seqüencialmente,
pedaço a pedaço. Relativo: muitas aplicações não podem ser implementadas como acesso seqüencial, Sistemas Operacionais – Lucilia Ribeiro 122 12 – Sistema de Arquivos 12.2.2 IMPLEMENTAÇÃO DE ARQUIVOS A forma básica de implementar arquivos é criar, para cada arquivo no sistema, um O descritor
de arquivo deve ficar em disco e de preferência na mesma partição do ar- Para tornar mais rápido o acesso aos arquivos, o sistema de arquivos mantém na Quando o processo que está sendo executado faz uma chamada para abrir um arqui- Localiza no disco o descritor de arquivo cujo nome foi fornecido. Caso o arquivo não Verifica se o arquivo solicitado já se encontra aberto. Isso
é feito através de uma Caso o arquivo não esteja aberto, aloca uma entrada livre na TDAA e copia o descri- Uma vez que o descritor do arquivo foi copiado para a memória, verifica se o proces- A partir desse momento, o arquivo está aberto e pode ser acessado. Quando um pro-
As entradas da TDAA armazenam informações que não variam conforme o processo Essas informações não podem ser mantidas na TDAA pois, como vários processos po- No exemplo, o processo 0 acessa o arquivo B através de referências a entrada 1 da Sistemas Operacionais – Lucilia Ribeiro 123 12 – Sistema de Arquivos TAAP do Processo TDAA 0 Pos.Cor.12 Arquivo 0 Pos.Cor.55 1
Leitura/Escrita 1 2 Arquivo 3 TAAP do Processo 4 1 Pos.Cor.10 0 Leitura 2 12.3 MÉTODOS DE ALOCAÇÃO Para o SO, cada arquivo corresponde a uma seqüência de blocos lógicos, numerados 12.3.1 ALOCAÇÃO CONTÍGUA Bloco Físico DISCO Dos métodos que objetivam associar blocos de disco a arquivos existentes, a aloca- Vantagens: Sistemas Operacionais – Lucilia Ribeiro 124 12 – Sistema de Arquivos • Simplicidade de implementação, pois para se acessar todo o arquivo basta que seja • Performance excelente, pois a leitura do arquivo em disco pode acontecer em uma Desvantagens: • O tamanho máximo do arquivo tem que ser conhecido no momento em que ele for • Ocasiona fragmentação no disco. 12.3.2 ALOCAÇÃO COM LISTA LIGADA Neste método, cada bloco físico contém o endereço do próximo bloco físico alocado a Vantagens: • Evita-se a perda de espaço em disco ocasionado pela fragmentação; • Para se acessar todo o arquivo, basta que seja conhecido o endereço de seu primei- Desvantagens: • Acesso randômico lento e difícil de ser implementado DISCO Bloco Físico 0 1 Bloco 3 7 2 3 Bloco 0 8 Descritor 4 Início: 3 5 Bloco 2 1 Tamanho: 6 6 7 Bloco 4 11 8 Bloco 1 5 9 10 11 Bloco 5 -1 12 13 12.3.3 ALOCAÇÃO COM LISTA LIGADA USANDO UM ÍNDICE Com a finalidade de se eliminar os problemas encontrados no caso anterior, nesse Vantagens: • Facilidade para se implementar um acesso randômico rápido, pois as entradas a se- • Para se acessar todo o arquivo basta que a entrada de diretório contenha o endere- Desvantagens: 125 12 – Sistema de Arquivos • Toda a tabela deve estar na memória durante todo o tempo. DISCO DESCRITOR Bloco Físico 0 Tamanho: 5 1 Bloco 3 Índices: 0 3 2 18 3 Bloco 0 25 4 31 5 Bloco 2 47 65 7 Bloco 4 6 8 Bloco 1 7 98 12.4 GERÊNCIA DE ESPAÇO EM DISCO Existem alguns métodos que objetivam associar blocos de disco a arquivos exis- Unidade de alocação muito grande: causará desperdício de espaço dentro da
unidade Unidade de alocação muito pequena: um arquivo de tamanho razoável será composto Obs.: Normalmente, temos blocos de tamanhos que variam de 512 bytes até 2KB. 12.5 CONTROLE DE BLOCOS LIVRES Existem quatro
maneiras mais usuais de se realizar o controle dos blocos não uti- 12.5.1 MAPA DE BITS Cada bloco é representado por 1 bit. Se o bloco estiver livre, o bit será 1; se ele 12.5.2 LISTA ENCADEADA Outra abordagem é encadear os blocos de discos livres, mantendo um ponteiro ao 12.5.3 AGRUPAMENTO Uma
modificação da abordagem de lista livre é armazenar os endereços de n blo- 12.5.4 CONTADORES Outra abordagem é aproveitar o fato de que, em geral, vários blocos contíguos Sistemas Operacionais – Lucilia Ribeiro 126 12 – Sistema de Arquivos 12.6 CONSISTÊNCIA DO SISTEMA DE ARQUIVOS É importante que após uma pane no computador, o seu sistema de arquivos possa O referido programa utilitário realiza, por exemplo, a verificação de consistência 12.6.1 CONSISTÊNCIA EM BLOCOS Neste tipo de verificação, o programa utilitário constrói uma tabela possuindo dois Situações indesejadas possíveis: • Um bloco não possui ocorrência em nenhum arquivo e ele também não apare- Solução: colocar o bloco perdido na lista de blocos livres. • Um bloco aparece duas vezes na lista de blocos livres. Solução: reconstruir a lista de blocos livres. • Um bloco está presente em mais de um arquivo. Solução: alocar um novo bloco e copiar
nele o conteúdo do bloco problemático. Em • Um bloco está presente em um arquivo e também na lista de blocos livres. Solução: remover o bloco da lista de blocos livres. 12.7 PERFORMANCE DO SISTEMA DE ARQUIVOS Sabemos que acessar arquivos localizados em discos é uma tarefa que consome Dentre as técnicas mais utilizadas para diminuir o acesso ao disco, podemos des- 12.7.1 CACHE A cache corresponde a um agrupamento de blocos que pertencem logicamente ao Os algoritmos de substituição de páginas estudados (ótimo, NUR, FIFO,
segunda Problema: Em caso de pane, os blocos que se encontram na cache podem não ser Solução: UNIX: implementa a chamada SYNC, que faz com que todos os blocos que Obs.: Quando o sistema é inicializado, um programa em background realiza uma MS-DOS: implementa a estratégia
write-through, na qual a alteração em um bloco 12.7.2 LEITURA ANTECIPADA DE BLOCOS A segunda técnica para melhorar o desempenho do sistema de arquivos é tentar transferir os blocos para a cache antes que eles sejam necessários para aumentar a taxa de acertos. Sistemas Operacionais – Lucilia Ribeiro 127 12 – Sistema de Arquivos Problema: Tal estratégia só funciona para arquivos que estejam sendo lidos
seqüen- Solução: Para verificar se vale a pena fazer a leitura antecipada, o sistema de arqui- 12.7.3 REDUÇÃO DO MOVIMENTO DO BRAÇO DO DISCO Esta técnica objetiva gravar os blocos que serão mais acessados o mais perto 12.8 EXERCÍCIOS 187) Considerando que a unidade de alocação física é de 2k, o tamanho da memó- 188) Qual a diferença entre fragmentação externa e fragmentação interna? De- 189) Relacione a Tabela de Descritores de Arquivos Abertos (TDAA) e a
Tabela de 190) Cite as vantagens e desvantagens dos métodos de alocação: contígua, enca- 191) Existem alguns métodos que objetivam associar blocos de disco a arquivos e- 192) Considere que o sistema operacional XYZ utiliza contadores para o controle de 26 4 10 7 02 3 193) Partindo agora de um mapa de bits utilizado para controle de blocos livres, -x- Sistemas Operacionais – Lucilia Ribeiro 128 13 – Gerência de Dispositivos 13 Gerência de Dispositivos “A teoria sempre acaba, mais cedo ou mais tarde, assassinada pela experiência.” 13.1 INTRODUÇÃO A Gerência de Dispositivos de entrada/saída é uma das principais e mais complexas As camadas são divididas em dois grupos, onde o primeiro grupo visualiza os diversos 13.2 ACESSO AO SUBSISTEMA DE ENTRADA E SAÍDA O Sistema Operacional deve tornar as operações de E/S o mais simples possível para As operações de E/S devem ser realizadas através de chamadas de sistemas que Sistemas Operacionais – Lucilia Ribeiro 129 13 – Gerência de Dispositivos escrever um programa que manipule arquivos, este- A maneira mais simples de ter acesso a um dispo- Um dos objetivos principais das
chamadas de sis- As operações de E/S podem ser classificadas con- 13.3 SUBSISTEMA DE ENTRADA E SAÍDA O subsistema de E/S é responsável por realizar as funções comuns a todos os tipos Independência de Dispositivos: Cada dispositivo trabalha com unidades de informa- Tratamento de Erros: Normalmente, o tratamento de erros nas operações de E/S é Compartilhamento: Todos os dispositivos de E/S são controlados, com o objetivo de Bufferização:
Essa técnica permite reduzir o número de operações de E/S, utilizando Sistemas Operacionais – Lucilia Ribeiro 130 13 – Gerência de Dispositivos Interface Padronizada: O subsistema de E/S deve oferecer uma interface padronizada 13.4 DEVICE DRIVERS Tem como função implementar a comunicação do subsistema de E/S com os disposi- Por exemplo, na leitura síncrona de um dado em dis- Os
drivers fazem parte do núcleo do Sistema Operacional, sendo escritos geralmente 13.5 CONTROLADORES Sistemas Operacionais – Lucilia Ribeiro São componentes de hardware 131 13 – Gerência de Dispositivos ferência do bloco pode ser realizado pela UCP ou por um controlador de DMA (Acesso De forma simplificada, uma operação de leitura em disco utilizando DMA teria os se- 13.6 DISPOSITIVOS DE ENTRADA E SAÍDA São utilizados para permitir a comunicação entre o sistema computacional e o mundo A transferência de dados pode ocorrer através de blocos de informação ou
caracteres, Os
dispositivos estruturados classificam-se em dispositivos de acesso direto e se- Os dispositivos não-estruturados
(character devices) são aqueles que enviam ou re- 13.7 DISCOS RÍGIDOS Fisicamente, um dis- Sistemas Operacionais – Lucilia Ribeiro 132 13 – Gerência de Dispositivos disco. Essa estrutura é capaz de realizar movimentos de vai-e-vem de maneira que os Do ponto de vista da organização lógica, cada superfície
de um disco é dividida em Outros termos bastante comuns associados a discos rígidos são formatação lógica e 13.7.1 TEMPO DE ACESSO Para
realizar um acesso a um disco rígido, é necessário posicionar o cabeçote de Tacesso = tseek + tlatência + ttransferência Tempo de Seek: tempo de locomoção do braço do disco até o cilindro desejado; Latência Rotacional: tempo para que o setor desejado passe sob a cabeça de leitura; Tempo de Transferência: tempo de transferência propriamente dito. 13.7.2 ENTRELAÇAMENTO (interleaving) É muito comum o acesso a vários setores contíguos em uma trilha do disco. Su- Sistemas Operacionais – Lucilia Ribeiro 133 13 – Gerência de Dispositivos A forma usual para evitar esse problema é realizar um entrelaçamento dos setores Voltando ao exemplo no qual os setores 4 e 5 são lidos, mas agora considerando O melhor fator de entrelaçamento para uma determinada unidade de disco de- 13.7.3 ESCALONAMENTO DO BRAÇO DO DISCO Como já vimos, uma das principais funções do sistema operacional é gerenciar os O tempo necessário a uma operação de entrada e saída com discos é fortemente a) 7.3.1. Primeiro a Entrar, Primeiro a Ser Servido (FCFS) b) 7.3.2. Menor Seek Primeiro (SSF) Neste algoritmo, a próxima requisição a ser atendida será aquela que exigir o menor Requisição: 11, 1, 36, 16, 34, 9 e 12 Seqüência de acesso: 11, 12, 9, 16, 1, 34 e 36 Sistemas Operacionais – Lucilia Ribeiro 134 13 – Gerência de Dispositivos Deslocamento do Braço: 1, 3, 7, 15, 33 e 2 Total Percorrido: 61 Obs.: O SSF reduz quase metade do movimento do braço do disco, quando comparado com o FCFS, porém apresenta tendência em acessar o meio do disco, poden- do levar um pedido de acesso à postergação indefinida. c) 7.3.3. Algoritmo do Elevador (Scan) Como o próprio nome do algoritmo sugere, este faz com que todas as requisições em Requisição: 11, 1, 36, 16, 34, 9 e 12 Seqüência de acesso: 11, 12, 16, 34, 36, 9 e 1 Deslocamento do Braço: 1, 4, 18, 2, 27 e 8 Total Percorrido: 60 d) 7.3.4. Algoritmo C-Scan O algoritmo Scan, imediatamente após inverter a varredura, inicia o atendimento pri- Nesse caso, quando a varredura atinge o último cilindro, o cabeçote é posicionado no Requisição: 11, 1, 36, 16, 34, 9 e 12 Seqüência de acesso: 11, 12, 16, 34, 36, 1 e 9 Sistemas Operacionais – Lucilia Ribeiro 135 13 – Gerência de Dispositivos Deslocamento
do Braço: 1, 4, 18, 2, 35 e 8 194) Explique o modelo de camadas aplicado na gerência de dispositivos 195) Qual a principal finalidade das rotinas de E/S? 196) Quais as diferentes formas de um programa chamar rotinas de E/S? 197) Quais as principais funções do subsistema de E/S? 198) Qual a principal função de um driver? 199) Por que o sistema de E/S deve criar uma interface padronizada com os device 200) Explique o funcionamento da técnica de DMA e sua principal vantagem. 201) Diferencie os dispositivos de E/S estruturados dos não-estruturados. 202) Desenhe um disco com 21 setores e um fator 3 de entrelaçamento. Mostre 203) As requisições do disco chegam ao driver do disco na seguinte ordem dos ci- 204) Monte um quadro mostrando a seqüência do braço, o deslocamento a cada Chegada Requisições -x- Sistemas Operacionais – Lucilia Ribeiro 136 14 – Multimídia 14 Multimídia “A precisão numérica é a própria alma da ciência.” 14.1 INTRODUÇÃO Filmes, fotos e música digitais estão se tornando, cada vez mais, meios comuns de A grande busca do mundo multimídia atualmente, é o vídeo sob demanda, que impli- O servidor de vídeo é um
computador potente que armazena muitos filmes em seu A rede de distribuição entre o usuário e o servidor de vídeo deve ser capaz de trans- Figura: Vídeo sob demanda usando (a) ADSL e (b) TV a cabo A última peça do sistema é a caixa digital, ou set-top box, ou seja, aonde chega o Sistemas Operacionais – Lucilia Ribeiro 137 14 – Multimídia chips especiais para decodificação e descompressão de vídeo. No mínimo, esse tipo de Há
duas características fundamentais que devem ser muito bem entendidas para tra- • Usa taxas de dados extremamente altas. • Requer reprodução em tempo real. As altas taxas de dados resultam da natureza da informação visual e acústica. Os o- Origem Mbps GB/h Dispositivo Mbps Telefone (PCM) 0,064 0,03 Fast Ethernet 100 Música em MP3 0,14 0,06 Disco EIDE 133 Áudio de CD 1,4 0,62 Rede ATM OC-3 156 Filme MPEG-2 (640 x 480) 4 1,76 Disco SCSI UltraWide 320 Câmera digital (720 x 480) 25 11 FireWire 400 TV (640 X 480) 221 97 Gigabit Ethernet 1000 HDTV (1280 X 720) 648 288 Disco SCSI Ultra-160 1280 A segunda exigência que a multimídia impõe sobre um sistema é a necessidade da NTSC é a sigla para National Television Standards Comittee (Comissão Nacional para Nos seres humanos os ouvidos
são mais sensíveis que os olhos; portanto, uma varia- As propriedades de tempo real necessárias para reproduzir multimídia de maneira a- 14.2 ARQUIVOS MULTIMÍDIA Na maioria dos sistemas, um arquivo de
texto comum é formado por uma seqüência Sistemas Operacionais – Lucilia Ribeiro 138 14 – Multimídia Além disso, a maioria dos filmes almeja uma audiência mundial que, na sua maioria, 14.2.1 CODIFICAÇÃO DE ÁUDIO Uma onda sonora (áudio) é uma
onda acústica (de pressão) unidimensional. Quando As ondas de áudio podem ser convertidas para a forma digital
por um CAD (Conver- O intervalo de alcance de freqüência do ouvido humano vai de 20 a 20 mil Hz. O áu- 14.2.2 CODIFICAÇÃO DE VÍDEO O olho
humano funciona do seguinte modo: ao atingir a retina, uma imagem é retida Para entender sistemas de Vídeo é melhor começar com a simples e antiga televisão Embora 25 quadros/s sejam suficientes para capturar movimentos suaves, nessa taxa Vídeo em cores usa o mesmo padrão de varredura do monocromático, só que, em Para permitir que transmissões em cores sejam vistas em receptores em preto-e- Até aqui vimos o vídeo analógico. Agora nos voltaremos para o vídeo digital. A repre- Sistemas Operacionais – Lucilia Ribeiro 139 14 – Multimídia res, que é o suficiente. O olho humano não consegue nem mesmo distinguir essa quanti- Para produzir movimentos suaves, o vídeo digital, assim como o vídeo analógico, de- Em outras palavras, a suavidade do movimento é determinada pelo número de ima- A importância desses dois parâmetros torna-se clara quando consideramos a largura 14.3 COMPRESSÃO DE VÍDEO Agora, deve estar óbvio que manipular material multimídia sem compressão está fora Todos os sistemas de compressão precisam de dois algoritmos: um para comprimir os Esses algoritmos têm certas assimetrias que precisam ser compreendidas. Primeira- Uma segunda assimetria é que o processo codifica/decodifica não é reversível. Ou se- 14.3.1 O PADRÃO JPEG O padrão JPEG (Joint Photographic Experts Goup – grupo conjunto de especialistas Sistemas Operacionais – Lucilia Ribeiro 140 14 – Multimídia fotografias) é importante para multimídia porque, de modo geral, o padrão multimídia O passo 1 da codificação de uma imagem em JPEG é a preparação do bloco. Para São construídas matrizes separadas para Y, I e Q, cada uma com elementos entre 0 e Figura: (a) Entrada de dados RGB. (b) Depois da preparação do bloco. O passo 2 do JPEG é aplicar uma transformação DCT (Discrete Cosine Transforma- Uma vez terminada a DCT, o JPEG passará ao passo 3, que é chamado de quantiza- Um exemplo desse passo é mostrado na Figura abaixo, em que vemos a matriz DCT O passo 4 reduz o valor (0,0) de cada bloco (o primeiro no canto superior esquer- Sistemas Operacionais – Lucilia Ribeiro 141 14 – Multimídia Figura: Computação dos coeficientes DCT quantizados. O passo 5 lineariza os
64 elementos e aplica a codificação run-length a essa lista de Figura: A ordem na qual os valores quantizados são transmitidos Agora temos uma lista de números que representa a imagem (no espaço de trans- O JPEG pode parecer complicado; isso ocorre porque o JPEG é complicado. Ainda as- 14.3.2 O PADRÃO MPEG Finalmente, chegamos ao cerne do que nos interessa: os padrões MPEG (Motion Pic- Para cenas em que a câmara e o fundo sejam estacionários e
um ou dois atores mo- Sistemas Operacionais – Lucilia Ribeiro 142 14 – Multimídia A saída do MPEG consiste em três tipos diferentes de quadros que devem ser proces- I (lntracodificados): Imagens paradas autocontidas codificadas por JPEG. P (Preditivos): Diferença bloco por bloco com o último quadro. B (Bidirecionais): Diferenças entre o último e o próximo quadro. Os quadros I são apenas imagens paradas codificadas pelo JPEG, usando também
o Os quadros P, por outro lado, codificam diferenças entre os quadros. São baseados na Um exemplo da utilidade dos quadros P é
ilustrado na Figura. Nela vemos três qua- Figura: Três quadros consecutivos de vídeo Os quadros B são similares aos quadros P, só que eles permitem que o macrobloco de Para fazer uma codificação do quadro B, o codificador precisa guardar, ao mesmo 14.4 ESCALONAMENTO DE PROCESSOS MULTIMÍDIA Os sistemas operacionais que suportam multimídia diferem dos tradicionais por três 14.4.1 ESCALONAMENTO DE PROCESSOS HOMOGÊNEOS O tipo mais simples de servidor de vídeo é aquele capaz de suportar a exibição de um número fixo de filmes, todos com a mesma taxa de quadros, a mesma resolução de ví- Sistemas Operacionais – Lucilia Ribeiro 143 14 – Multimídia deo, a mesma taxa de dados e outros parâmetros. Sob essas circunstâncias, um algorit- Um modo de conseguir a temporização
apropriada é ter um relógio-mestre que pulse, 14.4.2 ESCALONAMENTO GERAL DE TEMPO REAL Infelizmente trata-se de um modelo raramente aplicável à realidade. O número de Essas considerações levam a um modelo diferente: múltiplos processos competindo Um exemplo do tipo de ambiente com o qual um escalonador multimídia de tempo Figura: Três processos periódicos, cada um exibindo um filme. Também ilustrados na Figura estão dois outros processos, B e C. O processo B execu- ta 25 vezes/s (por exemplo, PAL) e o processo C executa 20 vezes/s (por exemplo, um fluxo NTSC ou PAL mais lento, destinado a um usuário com uma conexão de baixa largu- ra de banda para o servidor de vídeo). O tempo de computação por quadro é mostrado como 15 ms e 5 ms para B e C, respectivamente, apenas para tornar o problema de es- calonamento mais geral do que tê-los todos iguais. Sistemas Operacionais – Lucilia Ribeiro 144 14 – Multimídia O problema do escalonamento agora é como escalonar A, B e C assegurando que eles Algoritmos de tempo real podem ser estáticos ou dinâmicos. Os algoritmos estáticos 14.4.3 ESCALONAMENTO POR TAXA MONOTÔNICA O algoritmo clássico de escalonamento estático de tempo real para processos pre- 1. Cada processo periódico deve terminar dentro de seu período. 2. Nenhum processo é dependente de qualquer outro processo. 3. Cada processo precisa da mesma quantidade de tempo de CPU a cada surto. 4. Quaisquer processos não periódicos não podem ter prazos. 5. A preempção de processo ocorre instantaneamente e sem sobrecargas. O RMS funciona atribuindo a cada processo uma prioridade fixa igual à freqüência de Figura: Um exemplo dos escalonamentos de tempo real RMS e EDF. A Figura acima mostra como o escalonamento por taxas monotônicas funciona para o Na Figura, inicialmente todos os três processos estão prontos para executar. O de Sistemas Operacionais – Lucilia Ribeiro 145 14 – Multimídia Juntos esses processos levam 30 ms para executar e, assim, quando C terminar será a Em t = 80, B fica pronto e executa. Contudo, em t = 90, um processo de prioridade 14.4.4 ESCALONAMENTO PRAZO MAIS CURTO PRIMEIRO Outro algoritmo popular de escalonamento de tempo real é o do prazo mais curto Um exemplo de EDF é visto também na Figura anterior. Inicialmente, todos os três Para dissipar a idéia de que o RMS e o EDF sempre chegam aos mesmos resultados, Figura: Outro exemplo de escalonamento em tempo real RMS e EDF. Para o RMS, as prioridades dos três processos ainda são 33, 25 e 20, já que somente Agora
vejamos como o EDF lida com esse problema. Em t = 30, há uma disputa entre Em t = 90, A fica pronto pela quarta vez. O vencimento do prazo de A é igual ao do Sistemas Operacionais – Lucilia Ribeiro 146 14 – Multimídia preempção. Assim como antes, se não for necessário, é melhor não fazer a preempção; 14.5 PARADIGMAS DE SISTEMAS DE ARQUIVOS MULTIMÍDIA Agora que cobrimos o escalonamento de processos em sistemas multimídia, prosse- Esse modelo não funciona bem para multimídia por causa da necessidade de um Para resolver esses problemas, os servidores de arquivos multimídia usam um para- Figura: (a) Um servidor pull. (b) Um servidor push. 14.5.1 FUNÇÕES DE CONTROLE VCR A maioria dos servidores de vídeo implementa também funções-padrão de controle Sistemas Operacionais – Lucilia Ribeiro 147 14 – Multimídia Contudo, há uma complicação. Para obter um desempenho aceitável, o servidor pode O rebobinamento é bem fácil. Tudo o que o servidor precisa fazer é lembrar que o A compressão complica o movimento rápido para frente ou para trás. Com uma fita 14.5.2 VÍDEO QUASE SOB DEMANDA Ter k usuários assistindo ao mesmo filme impõe, essencialmente, a mesma carga so- A vantagem é que, para um filme de duas horas, são necessários somente 24
fluxos, De certo modo, o vídeo sob demanda é como usar um táxi: você chama e ele vem. O Sistemas Operacionais – Lucilia Ribeiro 148 14 – Multimídia Figura: O vídeo quase sob demanda tem um novo fluxo iniciando em intervalos regulares; No vídeo quase sob demanda, os usuários não têm controles VCR. Nenhum usuário 14.6 ALOCAÇÃO DE ARQUIVOS EM DISCOS Os arquivos multimídia são bastante grandes e com freqüência são escritos somente 14.6.1 ALOCAÇÃO DE UM ARQUIVO EM UM ÚNICO DISCO A exigência mais importante é que os
dados, na forma de fluxos, possam fluir para a No
entanto, uma complicação é a presença de vídeo, áudio e texto. Mesmo que esses Essa organização requer uma E/S adicional de disco para leitura de áudio e texto que Sistemas Operacionais – Lucilia Ribeiro 149 O que é um page fault quando ocorre é quem controla a sua ocorrência como uma elevada taxa de page fault pode comprometer o sistema operacional?Como uma elevada taxa de page fault pode comprometer o sistema operacional? R: O page fault ocorre todas as vezes que um processo faz referência a um endereço virtual pertencente a uma página virtual que não se encontra mapeada em uma página real, ou seja, não está, no momento, na memória principal.
Quem controla o page fault?A ocorrência de um page fault é verificada através do bit de validade presente na ETP da tabela de páginas referente à página virtual e controlada pelo sistema operacional.
O que é um erro de page fault?Uma falta de página ou falha de página (page fault em inglês), no contexto da tecnologia da memória dos computadores, é uma interrupção (ou exceção) disparada pelo hardware quando um programa acessa uma página mapeada no espaço de memória virtual, mas que não foi carregada na memória física do computador.
Quanto ao page fault Assinale a alternativa correta?Questão 9/10 Quanto ao page-fault, assinale a alternativa correta. A Só ocorre em sistemas monoprogramáveis. B Ocorre sempre que o processo referencia um endereço de memória virtual e a página que contém o endereço referenciado não está na memória principal. Você acertou!
|