Prévia do material em texto

<p>Recife, 2010</p><p>Infraestrutura de Software</p><p>UNIVERSIDADE FEDERAL RURAL DE PERNAMBUCO (UFRPE)</p><p>COORDENAÇÃO GERAL DE EDUCAÇÃO A DISTÂNCIA (EAD/UFRPE)</p><p>Juliana Regueira Basto Diniz</p><p>Volume 2</p><p>Universidade Federal Rural de Pernambuco</p><p>Reitor: Prof. Valmar Corrêa de Andrade</p><p>Vice-Reitor: Prof. Reginaldo Barros</p><p>Pró-Reitor de Administração: Prof. Francisco Fernando Ramos Carvalho</p><p>Pró-Reitor de Atividades de Extensão: Prof. Delson Laranjeira</p><p>Pró-Reitora de Ensino de Graduação: Profª Maria José de Sena</p><p>Pró-Reitora de Pesquisa e Pós-Graduação: Profª Antonia Sherlânea Chaves Véras</p><p>Pró-Reitor de Planejamento: Prof. Romildo Morant de Holanda</p><p>Pró-Reitor de Gestão Estudantil: Prof. Valberes Bernardo do Nascimento</p><p>Coordenação Geral de Ensino a Distância: Profª Marizete Silva Santos</p><p>Produção Gráfica e Editorial</p><p>Capa e Editoração: Rafael Lira e Italo Amorim</p><p>Revisão Ortográfica: Elias Vieira</p><p>Ilustrações: Juliana Diniz</p><p>Coordenação de Produção: Marizete Silva Santos</p><p>Sumário</p><p>Apresentação ................................................................................................................. 5</p><p>Conhecendo o Volume 2 ................................................................................................ 6</p><p>Capítulo 1 – Escalonamento de Processos ...................................................................... 8</p><p>Escalonamento de Longo Prazo .......................................................................................9</p><p>Escalonamento de Curto Prazo ......................................................................................10</p><p>Escalonamento de Entrada e Saída ...............................................................................10</p><p>Políticas de Escalonamento ...........................................................................................11</p><p>FIFO (First in First out) ..............................................................................................11</p><p>STCF (Shortest Time to Completion First) .................................................................12</p><p>Prioridades ...............................................................................................................12</p><p>Round Robin .............................................................................................................13</p><p>SRTCF (Shortest Remaining Time to Completion First) .............................................15</p><p>Escalonamento em Múltiplas Filas com diferentes Prioridades ....................................15</p><p>Capítulo 2 – Gerenciamento de Memória ..................................................................... 23</p><p>Particionamento da Memória .......................................................................................25</p><p>Particionamento Fixo ...............................................................................................25</p><p>Particionamento Variável .........................................................................................27</p><p>Swapping de Processos..................................................................................................29</p><p>Mapa de bits ............................................................................................................31</p><p>Lista Encadeada .............................................................................................................31</p><p>Capítulo 3 – Memória Virtual ....................................................................................... 36</p><p>Paginação ......................................................................................................................37</p><p>Endereçamento .............................................................................................................39</p><p>Algoritmos de Substituição de Páginas ..........................................................................43</p><p>Segmentação .................................................................................................................45</p><p>Segmentação com Paginação ........................................................................................47</p><p>Considerações Finais .................................................................................................... 52</p><p>Conheça a Autora ........................................................................................................ 53</p><p>5</p><p>Apresentação</p><p>Caro (a) Cursista,</p><p>No primeiro volume, vimos que o sistema operacional possui dois papéis principais dentro do contexto</p><p>computacional. O primeiro deles é atuar como interface entre o usuário e o hardware. O segundo papel refere-se ao</p><p>gerenciamento de recursos. Recursos podem ser de hardware e software. Na função de gerenciamento de recurso,</p><p>verificaremos duas tarefas fundamentais neste capítulo. São elas: escalonamento de processos e gerenciamento de</p><p>memória.</p><p>Iniciaremos o volume 2 abordando o escalonamento de processos, pois está diretamente ligado ao nosso</p><p>primeiro volume quando estudamos os conceitos básicos de processos e arquivos e comunicação inter processos. Em</p><p>seguida, passaremos a estudar o gerenciamento de memória e as suas diversas técnicas: paginação, segmentação e</p><p>paginação com segmentação.</p><p>O objetivo principal deste segundo volume é apresentar o sistema operacional como gerenciador de</p><p>recursos, aprofundando os conceitos de escalonamento de processos e gerenciamento de memória.</p><p>Bons estudos!</p><p>Juliana Regueira Basto Diniz</p><p>Professora Autora</p><p>6</p><p>Infraestrutura de Software</p><p>Conhecendo o Volume 2</p><p>Neste volume, você irá encontrar o Módulo 2 da disciplina Infraestrutura de</p><p>Software. Para facilitar seus estudos, veja a organização deste módulo:</p><p>Módulo 2 − Sistema Operacional como Gerente de Recursos</p><p>Carga Horária do Módulo 2: 20 h/aula</p><p>Objetivo do Módulo 2: Introduzir os conceitos associados à função do sistema</p><p>operacional como gerenciador de recursos, aprofundando aspectos referentes ao</p><p>escalonamento de processos e ao gerenciamento de memória.</p><p>Conteúdo Programático do Módulo 2:</p><p>» Escalonamento de Processos;</p><p>» Gerenciamento de Memória: paginação, segmentação e paginação com</p><p>segmentação.</p><p>7</p><p>Infraestrutura de Software</p><p>Capítulo 1</p><p>O que vamos estudar neste capítulo?</p><p>Neste capítulo, vamos estudar os seguintes temas:</p><p>» Escalonamento de processos;</p><p>» Filas de processos;</p><p>» Políticas de escalonamento.</p><p>Metas</p><p>Após o estudo deste capítulo, esperamos que você consiga:</p><p>» Entender os princípios básicos do escalonamento de processos;</p><p>» Compreender os principais algoritmos de escalonamentos e conhecer as suas</p><p>limitações;</p><p>» Diferenciar as principais filas de processos em diversos níveis.</p><p>8</p><p>Infraestrutura de Software</p><p>Capítulo 1 – Escalonamento de</p><p>Processos</p><p>Vamos conversar sobre o assunto?</p><p>Você já se viu numa situação na qual está com várias atividades para serem</p><p>iniciadas num dado momento, mas você não consegue começá-las todas ao mesmo tempo</p><p>e por isso precisará selecionar qual você poderá começar agora e quais você executará em</p><p>momentos posteriores? Caso positivo, você chegou numa situação onde precisará escalonar</p><p>as tarefas a serem realizadas. Em um primeiro momento, você selecionará dentre todas as</p><p>tarefas ou atividades pendentes que você possui, aquelas que devem ser atendidas com</p><p>mais urgência. Esse é o primeiro escalonamento que você deve fazer. Após selecionar as</p><p>tarefas mais emergenciais, você precisará escolher qual será aquela que começará agora e</p><p>qual a que começará no próximo minuto.</p><p>Você pode montar uma estratégia que agrupa um conjunto de tarefas mais</p><p>emergenciais e iniciar cada uma delas de forma sequencial, mas atender a cada uma em um</p><p>minuto. Ou seja, você desprende 1 minuto com cada tarefa e vai alternando entre as suas</p><p>diversas tarefas até que elas venham a ser concluídas uma a uma.</p><p>Com os sistemas operacionais a situação é semelhante. Os S.Os atuais são</p><p>baseados na multiprogramação, conforme já falamos no volume 1 desta disciplina. Através</p><p>da multiprogramação, múltiplos programas são mantidos na memória. Cada processo</p><p>alterna entre a CPU e a espera</p><p>cópias. Para garantir a</p><p>consistência desses dados é importante manter o original sempre atualizado.</p><p>O espaço de endereçamento do programa é chamado de espaço de endereçamento</p><p>virtual e contém endereços lógicos ou virtuais. O endereço virtual deve ser convertido para</p><p>um endereço real (endereço físico) antes de acessar a memória.</p><p>O espaço de endereçamento lógico de um processo é dividido em páginas lógicas</p><p>de tamanho fixo. O espaço de endereçamento físico, alocado na memória principal,</p><p>também é dividido em pedaços e cada um tem o mesmo tamanho da página, de modo que</p><p>cada partição da memória principal pode armazenar exatamente uma página. Essa partição</p><p>também é chamada de frame ou moldura de página.</p><p>A figura 12 apresenta um esquema geral da paginação. Ela é um exemplo ilustrativo</p><p>que apresenta apenas 8 páginas virtuais e 4 páginas físicas.</p><p>Figura 12 – Esquema geral da Paginação</p><p>A memória virtual, localizada a esquerda da Figura 12, foi dividida em 8 páginas</p><p>lógicas de 4 bytes cada uma, totalizando 32 bytes. Para localizar uma instrução qualquer no</p><p>programa, utiliza-se o endereço lógico que é dividido em duas partes: um número de página</p><p>lógica e um deslocamento dentro dessa página.</p><p>A página física tem o mesmo tamanho que a página lógica, ou seja, 4 bytes. A</p><p>memória física foi dividida em 4 páginas físicas de 4 bytes cada uma, totalizando 16 bytes.</p><p>Os endereços de memória física também podem ser vistos como compostos por duas</p><p>partes: um número de página física e um deslocamento dentro dessa página.</p><p>38</p><p>Infraestrutura de Software</p><p>Observe que há uma correspondência entre a página física e a virtual. Em geral,</p><p>os programas geram endereços virtuais que não entram diretamente no barramento,</p><p>mas passam pela MMU (unidade de gerenciamento de memória, do inglês, Memory</p><p>Management Unit) onde são mapeados em endereços físicos. Note também que como a</p><p>página física e lógica têm o mesmo tamanho, o deslocamento de ambos os endereços são</p><p>iguais, pois a terceira instrução da página física 1 é a terceira instrução da página lógica 0,</p><p>no exemplo da Figura 12. Para realizar essa correspondência, existe a tabela de Páginas, cuja</p><p>função é relacionar os endereços virtuais com os endereços físicos.</p><p>O esquema geral apresentando a unidade de gerenciamento de memória é</p><p>apresentado na Figura 13.</p><p>Figura 13 – Esquema geral do Hardware com a MMU</p><p>Para compreendermos como funciona a paginação, vamos descrever um exemplo.</p><p>Considere um computador que pode gerar endereços de 16 bits. O seu espaço de</p><p>endereçamento virtual é, portanto de 216 posições. Assim, 216 = 26 * 210. Apenas lembrando</p><p>210 = 1K e 26 = 64. Assim 216 = 64K posições. A memória física, por sua vez, tem apenas 32K.</p><p>Dessa forma, um programa pode ter até 64K e somente partes deste programa podem estar</p><p>na memória principal, num determinado momento. Uma cópia completa do programa deve</p><p>ser mantida no disco.</p><p>Vamos considerar que se as páginas e as molduras têm 8K de endereços, então</p><p>concluímos:</p><p>» Com 64K de endereçamento virtual tem-se 8 páginas.</p><p>Como chega-se a 8 páginas?</p><p>São 64K de endereçamento virtual e 8K por cada página, então dividindo-se o</p><p>espaço de endereçamento virtual pelo tamanho da página temos 64K/8K = 8</p><p>páginas.</p><p>» Com 32K de endereçamento físico tem-se 4 molduras.</p><p>Como chega-se a 4 molduras?</p><p>São 32K de endereçamento físico e 8K por cada moldura, então usando o mesmo</p><p>raciocínio que para a página virtual, teremos 32K/8K = 4 páginas.</p><p>Lembre-se que é a MMU que converte o endereço virtual em endereço físico e que</p><p>o tamanho da página é sempre igual ao da moldura. O que vai mudar é o número de páginas</p><p>virtuais em relação ao número de páginas reais, uma vez que o primeiro deve ser muito</p><p>maior que o segundo para que a paginação funcione eficientemente.</p><p>O espaço de endereçamento da memória virtual é a memória de trabalho do</p><p>programador, pois é uma memória bem maior que a principal, capaz de armazenar</p><p>virtualmente qualquer processo. Na prática, o sistema operacional transfere as páginas para</p><p>a memória principal quando referências são feitas a elas.</p><p>39</p><p>Infraestrutura de Software</p><p>Observe a situação do exemplo ilustrada na Figura 14. O processo 1 possui 3</p><p>páginas, no entanto, apenas duas estão carregadas na memória principal. Veja que não é</p><p>mais necessário o programa estar totalmente carregado na memória. Observe ainda que a</p><p>técnica de paginação é bastante similar à implementação de cache utilizando mapeamento</p><p>completamente associativo, assunto abordado em infraestrutura de hardware.</p><p>Figura 14 – Esquema da Paginação</p><p>O impacto imediato do uso da memória virtual é um aumento no espaço de</p><p>endereçamento da máquina. Isto é, a máquina é agora capaz de endereçar um número</p><p>bem maior de palavras. Um endereço deve informar uma página virtual e identificar nesta</p><p>página, qual a palavra a ser acessada.</p><p>Endereçamento</p><p>Como a paginação utiliza endereços lógicos e físicos é necessária uma estrutura de</p><p>dados que relacionam os endereços virtuais com os endereços físicos e a essa estrutura é</p><p>dado o nome de Tabela de Páginas.</p><p>Para compreender o funcionamento da paginação, observe na Figura 15, o formato</p><p>do endereçamento virtual.</p><p>Figura 15 – Formato do Endereço Virtual</p><p>Na Figura 15, o endereço virtual possui 13 bits. Os 3 primeiros bits representam</p><p>o número da página virtual e os 10 bits seguintes representam o deslocamento dentro da</p><p>página. Neste caso, o deslocamento dentro da página é de 32 palavras, pois 0000100000 em</p><p>binário é equivalente a 32 em decimal.</p><p>Neste caso, o número de páginas virtuais é 8, pois os três primeiros bits representam</p><p>o número da página, então 23=8. Perceba que 3 bits são suficientes para endereçar 8 páginas</p><p>virtuais, pois permitem as seguintes combinações em binário:</p><p>40</p><p>Infraestrutura de Software</p><p>Binário Decimal</p><p>000 0</p><p>001 1</p><p>010 2</p><p>011 3</p><p>100 4</p><p>101 5</p><p>110 6</p><p>111 7</p><p>Utilizando este mesmo raciocínio, chegamos ao número máximo de palavras ou</p><p>endereços de página de 210, já que as possibilidades de combinações variam do 0000000000</p><p>ao 1111111111. Transformando este último número em binário para decimal, chegamos a</p><p>1023 e como usamos o 0, temos 1024 endereços dentro da página.</p><p>Observe ainda, apenas a título de ilustração, que o endereço expresso na Figura 15</p><p>retrata a página 7 da memória virtual e o deslocamento de 32.</p><p>Sabemos que a memória principal possui menor número de páginas que a memória</p><p>virtual. Portanto, o formato dos endereços não pode ser igual.</p><p>A memória do exemplo da Figura 15 comporta apenas 4 páginas, portanto, 2 bits</p><p>são suficientes para endereçar as páginas físicas. O formato do endereço virtual pode ser</p><p>observado na Figura 16.</p><p>Figura 16 – Formato do Endereço Físico</p><p>Note que o campo de deslocamento possui o mesmo tamanho para o endereço</p><p>real e o virtual. Isso pode ser observado nas Figuras 15 e 16, pois o campo de deslocamento</p><p>possui a informação 0000100000. Já o campo da página física da Figura 16 é 11, significando</p><p>que a quarta página é a que está sendo referenciada neste endereço.</p><p>Porém, como traduzir o endereço virtual em físico? É necessária uma</p><p>correspondência entre esses endereços. Anteriormente falamos de uma tabela de páginas</p><p>na qual o sistema operacional armazena as informações que relacionam páginas virtuais</p><p>com páginas físicas e ainda indica a localização da página virtual em disco. A Figura 17</p><p>apresenta um exemplo da tabela de páginas.</p><p>41</p><p>Infraestrutura de Software</p><p>Figura 17 – Tabela de Páginas</p><p>Observe que nos primeiros campos de cada linha apresenta-se a página virtual. Em</p><p>seguida, um conjunto de campos apresenta a localização da página no disco, identificando a</p><p>trilha e o setor do disco rígido que contém a página.</p><p>Para concluir, cada linha contém a identificação da página física que corresponde</p><p>à página virtual. Esta localização da página em disco é necessária para carregar a página na</p><p>memória principal, no momento em que a mesma é trazida do disco para a memória e para</p><p>atualizar a página em disco</p><p>quando for modificada e precisar ser reescrita em disco.</p><p>Além disso, outras informações estão presentes na tabela de páginas (vide Figura</p><p>18), pois em cada linha existem bits para identificar as seguintes informações:</p><p>» Presente/Ausente – para indicar se aquela página está na memória física;</p><p>» Desabilitar cache – para indicar se aquela página pode ir para a memória cache;</p><p>» Referenciada – para indicar se aquela página foi referenciada;</p><p>» Modificada – para indicar se aquela página já foi modificada;</p><p>» Proteção – para indicar se a página está protegida.</p><p>Figura 18 – Outras informações na Tabela de Páginas</p><p>Para entender como a tabela de páginas pode ser obtida, veremos um exercício</p><p>resolvido a seguir.</p><p>42</p><p>Infraestrutura de Software</p><p>Aprenda Praticando</p><p>Exercício Resolvido</p><p>1) Considere um sistema de memória virtual conforme apresentado nas Figuras 15 e</p><p>16 do presente capítulo. Suponha que as páginas possuem 1Kbytes. Qual o formato</p><p>do endereço virtual? Qual o tamanho em bytes da tabela de páginas? Assuma que</p><p>cada página possui 1 bit de presença, 3 bits de proteção e um dirty bit. Considere</p><p>ainda que os endereços da memória secundária não estejam armazenados nesta</p><p>tabela.</p><p>Resolução: Observe que na Figura 15, existe um formato de endereço virtual</p><p>que possui 3 bits para representar a página virtual e 10 bits para representar</p><p>o deslocamento em páginas de 1KByte. Portanto, sem fazer nenhum cálculo,</p><p>chegamos à solução do formato do endereço virtual observado na Figura 19.</p><p>Figura 19 – Formato do Endereço Virtual</p><p>Para calcular o tamanho em bytes da tabela de páginas, é necessário conhecer o</p><p>formato do endereço físico também. Sabemos que o deslocamento é o mesmo,</p><p>sendo portanto 10 bits. Pela Figura 16, o número de páginas físicas é 4, sendo</p><p>necessário 2 bits para representá-las (vide Figura 20).</p><p>Figura 20 – Formato do Endereço Físico</p><p>E a tabela de páginas? Vimos que ela precisa conter o número de bits para</p><p>representar a página física e a página virtual, além de alguns bits informativos, que</p><p>de acordo com o enunciado do problema são: 1 bit de presença, 3 bits de proteção</p><p>e um dirty bit, ou seja, são mais 5 bits por cada linha. Também nos foi informado,</p><p>no enunciado, que os endereços da memória secundária não estejam armazenados</p><p>nesta tabela, ou seja, devemos desconsiderar esses campos. Somando-se os 2 bits</p><p>da página física com os 3 bits da página virtual e 5 bits informativos, temos 10</p><p>bits por linha. E quantas linhas essa tabela deverá conter? Uma entrada para cada</p><p>página virtual nesta tabela será necessária e, neste caso, o número de linhas desta</p><p>tabela será o número de páginas virtuais, ou seja, 8. Multiplicando-se 8 por 10 bits,</p><p>a tabela de páginas do exemplo conterá 80 bits.</p><p>43</p><p>Infraestrutura de Software</p><p>Esse foi um exemplo irreal, pois tínhamos um número muito pequeno de páginas</p><p>reais e físicas, porém foi importante para compreender a ideia do uso da tabela de páginas.</p><p>Ficou claro para você? Você terá oportunidade de resolver outros exercícios similares na</p><p>seção de exercícios propostos.</p><p>Agora vamos conversar um pouco sobre o tamanho da página e os seus impactos</p><p>sobre o tamanho da tabela de páginas.</p><p>Páginas grandes significam que os processos serão compostos por menos páginas, o</p><p>que acarretará numa tabela de página menor e um custo menor, impostos pelo mecanismo</p><p>de gerência de memória. Por outro lado, ocasiona um aumento da fragmentação interna</p><p>na última página. Páginas pequenas, por sua vez, significam processos compostos por</p><p>mais páginas, ocasionando o aumento da tabela de páginas e diminuição da fragmentação</p><p>interna na última página.</p><p>De maneira geral, a maioria dos programas acessam com muita frequência apenas</p><p>um número pequeno de páginas, enquanto o restante é muito pouco utilizado. Baseando-</p><p>se nisso, foi criada a TLBs (do inglês Translation Lookaside Buffers), que é um dispositivo</p><p>de hardware utilizado no mapeamento de endereços, sem precisar recorrer à tabela de</p><p>páginas. A TBL é baseada em uma memória cache especial (TLB) composta por um banco de</p><p>registradores encontrando-se dentro da MMU (Memory Management Unit).</p><p>A TLB apresenta um pequeno número de entradas e por isso só comporta o</p><p>armazenamento de um pequeno número de páginas. A ideia é manter uma cópia parcial da</p><p>tabela de páginas que originalmente está armazenada na memória, em registradores.</p><p>A TLB funciona da seguinte maneira: um endereço virtual é passado à MMU para</p><p>que seja verificado se a página que contém o endereço está na TLB. Caso positivo, verifica-</p><p>se que o acesso está permitido, senão gera-se uma falha de proteção. Caso o acesso esteja</p><p>permitido, obtém-se o número da página física. Caso a página que contém o endereço</p><p>virtual procurado não esteja na TLB, é realizada uma verificação na página na tabela de</p><p>páginas e substiutui-se uma das entradas da TLB pela entrada da tabela recém pesquisada.</p><p>Em geral, o uso da TLB tende a melhorar o desempenho no acesso à tabela de</p><p>páginas, pois o tempo de acesso é bem menor que o tempo de acesso à memória RAM</p><p>(lembra-se da pirâmide de hierarquia de memória?). Por outro lado, o custo do uso da TBL é</p><p>elevado (pois utiliza registradores) e o seu tamanho é bastante limitado.</p><p>O módulo de gerenciamento de memória do S.O deve manter controle de áreas</p><p>livres e ocupadas, utilizando mecanismos de proteção para evitar que um processo acesse</p><p>área (páginas) de outros processos. Também é importante que no momento em que a</p><p>memória física esteja totalmente preenchida por páginas, determinar o uso de algum</p><p>algoritmo de substiutuição de páginas. Esse será o assunto que abordaremos na próxima</p><p>seção.</p><p>Algoritmos de Substituição de Páginas</p><p>O primeiro algoritmo que abordaremos é o LRU (do inglês, Least Recent Used),</p><p>cujo princípio é a substituição da página menos recentemente utilizada. Para realizar esta</p><p>associação, são utilizados bits de status para cada página. O S.O cria classes de páginas de</p><p>acordo com os bits referenciado e modificado (vide Figura 18) e escolhe uma das páginas da</p><p>categoria com número mais baixo, no caso de necessidade de uma substituição. A classe 0</p><p>é atribuída às páginas não-referenciadas e não-modificada. A classe 1 é atribuída às páginas</p><p>não-referenciadas, mas modificadas. A classe 2, por sua vez, são as páginas referenciadas</p><p>44</p><p>Infraestrutura de Software</p><p>e não-modificadas. Por fim, a classe 3 é atribuída às páginas referenciadas e modificadas.</p><p>Normalmente, o bit da tabela de páginas identificado como referenciado é configurado a</p><p>cada interrupção do relógio, enquanto que o bit identificado como modificado é configurado</p><p>quando a página é modificada.</p><p>O segundo algoritmo de substituição de páginas que abordaremos aqui será o FIFO</p><p>(do inglês, First in First out). O princípio de funcionamento deste algoritmo baseia-se numa</p><p>lista de páginas mantida pelo S.O, onde a página mais antiga é a primeira a ser substituída e</p><p>a mais recente será a última. No caso de necessidade de substituição, a página mais antiga</p><p>será removida e a nova página colocada no final da lista. O problema imediato encontrado</p><p>nessa abordagem é que existe a possibilidade de remoção de páginas muito referenciadas,</p><p>ainda que estejam há muito tempo na memória.</p><p>Um outro algoritmo para substituição de página é o de segunda chance. Ele é uma</p><p>variação do FIFO no qual o bit referenciado é verificado e a página recebe uma “segunda</p><p>chance”, não sendo, portanto, removida de imediato. O intervalo entre uma “chance”</p><p>e outra pode alterar a página a ser removida. Caso haja a necessidade de substituição,</p><p>o bit referenciado é inspecionado e se for 0 significa que a página não foi referenciada</p><p>recentemente, e pode ser trocada de imediato. Similarmente, se o bit referenciado for 1,</p><p>significa que a página foi referenciada recentemente e a mesma deverá ser passada para o</p><p>final da lista.</p><p>Uma variação do algoritmo de substituição de página de segunda chance é o</p><p>algoritmo do relógio. A sua única diferença em relação ao algoritmo de</p><p>segunda chance</p><p>original é a existência de uma lista circular, utilizada com um “ponteiro” indicando a</p><p>página mais antiga. Caso haja necessidade de substituição de página, o bit referenciado é</p><p>inspecionado e se for 0, significa que a página não foi referenciada recentemente, podendo</p><p>ser trocada de imediato. Caso contrário, se o bit referenciado for 1, ou seja, a página foi</p><p>referenciada recentemente, o ponteiro avança para próxima página.</p><p>Por fim, o algoritmo LFU (do inglês, Least Frequency Used) trabalha com a</p><p>substituição da página menos utilizada. O seu princípio de funcionamento baseia-se no</p><p>fato de que páginas intensamente utilizadas, recentemente, provavelmente serão utilizadas</p><p>a seguir. Assim, a ideia é manter um contador para cada página, que é atualizado a cada</p><p>instrução. Quando houver a necessidade de substituição de página, será descartada aquela</p><p>que for menos utilizada, ou seja, aquela cujo contador é o menor.</p><p>Diante do exposto na presente seção, concluímos o conteúdo sobre a paginação</p><p>fazendo um breve resumo das suas principais características.</p><p>A paginação é uma técnica de implementação de memória virtual que não gera</p><p>fragmentação externa, ou seja, entre partições, uma vez que utiliza partições de tamanhos</p><p>iguais e fixos. O único tipo de fragmentação ocorrido na paginação é fragmentação interna,</p><p>sendo esta restrita apenas a última página.</p><p>No esquema de paginação, o usuário visualiza um espaço de endereçamento</p><p>contíguo, de modo que o processo fica espalhado na memória física, pois as páginas virtuais</p><p>são alocadas em molduras na memória física, implicando na criação de uma tabela de</p><p>páginas. A tabela de páginas é responsável por fazer a correspondência entre as páginas</p><p>virtuais e as molduras na memória principal.</p><p>Na próxima seção, abordaremos uma outra técnica de memória virtual, a</p><p>segmentação.</p><p>45</p><p>Infraestrutura de Software</p><p>Segmentação</p><p>A segmentação, assim como a paginação, é uma técnica de memória virtual, ou</p><p>seja, utiliza a memória secundária como extensão da memória principal e permite carregar</p><p>processos parcialmente.</p><p>Duas maneiras de segmentação são permitidas:</p><p>» Segmentação simples ou por swapping;</p><p>» Segmentação com paginação.</p><p>Na técnica de segmentação simples, um conjunto de segmentos estão na memória</p><p>principal em um certo instante. Se ocorrer uma referência para um segmento que não está</p><p>na memória principal, esse segmento deve ser trazido do disco para a memória principal.</p><p>Você deve estar se perguntando qual a diferença de segmentos para páginas, já que</p><p>na paginação o processo é semelhante apenas substituindo a nomenclatura segmento</p><p>por página. As técnicas são bastante diferentes. Na paginação, as páginas têm tamanhos</p><p>iguais, tanto as físicas quanto as virtuais. Já na segmentação, os segmentos têm diferentes</p><p>tamanhos e constituem múltiplos espaços de endereçamentos lineares.</p><p>Uma outra diferença fundamental é com relação à transparência da técnica. Lembra-</p><p>se da característica transparência que falamos no volume 1? Pois é, ela está aparecendo</p><p>novamente aqui quando falamos que na paginação o programador não precisa saber que</p><p>o sistema usa esta técnica. Já na segmentação, o uso da técnica não é transparente ao</p><p>programador, enquanto que na paginação, a transparência ao programador existe.</p><p>Agora que você já sabe que as técnicas de paginação e segmentação têm diferenças</p><p>fundamentais, vamos conhecer um pouco mais da segmentação simples.</p><p>Na segmentação simples um conjunto de segmentos estão na memória principal</p><p>em um certo instante. Se for feita a referência para um segmento que não está na memória,</p><p>naquele momento, o mesmo deverá ser trazido do disco. Porém pode não haver espaço</p><p>para ele na memória principal e nesse caso, um ou mais segmentos devem ser retirados da</p><p>memória e escritos de volta no disco.</p><p>Esse processo é semelhante à paginação, porém difere em um aspecto essencial</p><p>que é em relação ao tamanho das páginas e dos segmentos: Páginas têm tamanhos fixos e</p><p>segmentos não.</p><p>Na segmentação, ocorre a divisão da memória virtual em espaços de endereçamento</p><p>completamente independentes, os chamados segmentos. Um segmento é uma sequência</p><p>linear de endereços, iniciados de 0 a um máximo permitido, de modo que o programador</p><p>está ciente da existência dos mesmos. Como falamos anteriormente, os segmentos possuem</p><p>tamanhos diferentes que inclusive podem variar durante a execução.</p><p>Na segmentação, o programador pode visualizar a memória composta por múltiplos</p><p>espaços de endereços ou segmentos e ele ou o próprio sistema operacional irá direcionar</p><p>os programas ou dados para diferentes segmentos. Dessa forma, a segmentação apresenta-</p><p>se como uma maneira alternativa de subdividir a memória endereçável, porém de forma</p><p>visível ao programador.</p><p>Dentre as principais vantagens da segmentação, está a divisão do programa em</p><p>módulos (segmentos) com características diferentes. Isso é muito interessante, pois alguns</p><p>demandam mais espaço progressivamente, outros requerem espaço constante, outros</p><p>aumentam e diminuem com o tempo.</p><p>Uma outra vantagem é a proteção do código. Existem alguns procedimentos que são</p><p>de execução exclusiva do sistema operacional e com a segmentação, esses procedimentos</p><p>46</p><p>Infraestrutura de Software</p><p>ficam num espaço de endereçamento separado dos demais programas. Por outro lado, a</p><p>segmentação também permite o compartilhamento de processos, caso seja necessário,</p><p>por exemplo, utilizar um segmento que contenha um programa utilitário ou uma tabela de</p><p>dados que pode ser endereçada por mais de um processo.</p><p>Além disso, como um segmento pode ser construído para conter um conjunto</p><p>de dados ou programas, o programador ou administrador do sistema pode configurar</p><p>privilégios de acesso de maneira conveniente.</p><p>A Figura 20 apresenta o esquema geral da segmentação. Nela, observamos que as</p><p>unidades manipuladas em memória são os segmentos e estes são carregados inteiramente</p><p>para a memória, de maneira similar às partições vistas anteriormente.</p><p>Figura 20 – Esquema geral da Segmentação</p><p>Da mesma maneira que no particionamento variável, a segmentação simples</p><p>ocasionará em fragmentação externa, como podemos observar na Figura 21. Você se lembra</p><p>da fragmentação externa? É um tipo de fragmentação que se dá entre as partições e com</p><p>o passar do tempo vai tendendo a aumentar, pois fragmentos maiores e mais frequentes</p><p>aparecerão na memória principal, de modo que, dificilmente, será encontrado um segmento</p><p>pequeno suficiente para caber nessas frações da memória.</p><p>Figura 21 – Memória Principal ilustrando a Segmentação</p><p>Para minimizar esta fragmentação, o sistema operacional deve decidir em que</p><p>lacuna(fragmento de memória) deve carregar um novo segmento, no momento em que ele</p><p>precisa ser trazido para a memória. Para isso, o S.O precisa manter uma lista atualizada de</p><p>lacunas e utilizar um algoritmo para o gerenciamento dessas lacunas. Existem dois principais</p><p>algoritmos:</p><p>» Best-fit: Procura a menor lacuna que caiba o segmento. Esse algoritmo é aquele</p><p>que melhor apresenta-se em termos de desempenho, pois vai gerar menor</p><p>47</p><p>Infraestrutura de Software</p><p>fragmentação.</p><p>» First-fit: Procura a primeira lacuna que caiba o segmento. Esse algoritmo,</p><p>diferentemente do anterior, é bem mais rápido, pois preza pela agilidade, mas</p><p>penaliza-se em termos de fragmentação, pois não haverá uma busca mais</p><p>elaborada, em relação às lacunas. No primeiro momento, quando uma lacuna for</p><p>encontrada e conseguir comportar o segmento, o mesmo será carregado nesse</p><p>espaço.</p><p>Independentemente do algoritmo utilizado, o S.O precisa realizar a atualização da</p><p>lista de lacunas existentes na memória. Lacunas adjacentes devem ser removidas, formando</p><p>um espaço único. Toda operação de carga e descarga de segmentos deve atualizar a lista.</p><p>Quando a lista atinge um número limite de lacunas, o sistema operacional deve reorganizar</p><p>a memória. Com isto, a lista fica com apenas um espaço contíguo disponível. Essa</p><p>reorganização da memória reduz a fragmentação</p><p>externa. Também é importante lembrar</p><p>que a rotina de reorganização consome recursos de processamento, não podendo ser</p><p>executada com tanta frequência, a fim de se evitar degradação de desempenho.</p><p>Sumarizando, a técnica de segmentação simples traz benefícios quanto à</p><p>modularidade e segurança. Por outro lado, como a memória não é dividida em blocos</p><p>uniformes, já que os segmentos têm tamanhos variáveis, a fragmentação externa não será</p><p>eliminada. Além disso, os segmentos precisam ser carregados inteiramente na memória,</p><p>não cumprindo o requisito mínimo de carga parcial de processos para memória.</p><p>Segmentação com Paginação</p><p>Para superar as limitações impostas pela técnica de segmentação e ao mesmo</p><p>tempo fazer uso dos seus benefícios, foi criada uma técnica de implementação da memória</p><p>virtual que une os benefícios da paginação e da segmentação. Essa técnica é denominada</p><p>segmentação com paginação. Nessa técnica, a memória virtual é dividida em segmentos</p><p>e estes são compostos por um conjunto de páginas. As páginas são as unidades de</p><p>transferência de dados entre a memória principal e a memória virtual, ou seja, a técnica de</p><p>trabalho é semelhante ao esquema da paginação. Em algum momento, algumas páginas</p><p>de um determinado segmento podem estar na memória, enquanto as demais podem</p><p>permanecer no disco.</p><p>A segmentação com paginação necessita também da tabela de páginas, porém</p><p>cada segmento tem a sua própria tabela de páginas.</p><p>A segmentação com paginação foi Inicialmente introduzida no MULTICS, como</p><p>falamos anteriormente, utiliza duas técnicas em conjunto: Paginação e Segmentação. Mas</p><p>por que utilizar a paginação? A paginação possui tamanho de página uniforme e carrega</p><p>para a memória principal apenas partes do programa.</p><p>Para o programador, a implementação de segmentação com paginação é</p><p>transparente. Ele enxerga apenas segmentos, como na segmentação simples. Na prática,</p><p>apenas algumas páginas do segmento em uso estão carregadas na memória. O esquema</p><p>geral da segmentação com paginação está ilustrado na Figura 22.</p><p>48</p><p>Infraestrutura de Software</p><p>Figura 22 – Segmentação com Paginação</p><p>Observe na Figura 22 que a memória virtual está dividida em quatro segmentos,</p><p>numerados de 0 a 3. O primeiro segmento está subdividido em 3 páginas enquanto que</p><p>os segmentos 1 e 2 possuem duas páginas. O último segmento possui apenas uma única</p><p>página. No presente momento, a memória principal contém uma página do segmento 2,</p><p>duas páginas do segmento 0 e uma página do segmento 3.</p><p>Para identificar esses segmentos e suas respectivas páginas, o S.O. utiliza uma</p><p>tabela de descritores. Essa tabela de descritores contém uma referência, por exemplo,</p><p>apontadores (endereços) para as localizações das tabelas de páginas de cada segmento.</p><p>Um esquema geral contendo a tabela de descritores e tabelas de páginas é apresentado na</p><p>Figura 23.</p><p>Mas e o formato do endereço virtual como é que fica, no esquema da segmentação</p><p>com paginação? A primeira parte do endereço contém o número do segmento. O número</p><p>do segmento na tabela de descritores aponta para uma tabela de páginas referente àquele</p><p>segmento. A segunda parte do endereço contém o número da página virtual. Na tabela de</p><p>páginas do segmento solicitado, o S.O procura a página física equivalente àquela página</p><p>virtual. A última parte do endereço virtual contém um conjunto de bits para representar</p><p>o deslocamento dentro da página, também conhecido como offset. O deslocamento é o</p><p>mesmo tanto para página virtual quanto para a página física.</p><p>Figura 23 – Tabelas de descritores e de Páginas</p><p>49</p><p>Infraestrutura de Software</p><p>Figura 24 – Endereço Virtual segmentado e Paginado</p><p>Observe que a última técnica que estudamos (Segmentação com Paginação) une</p><p>os benefícios da paginação e da segmentação. A segmentação traz benefícios quanto à</p><p>modularidade e segurança, por outro lado apresenta problemas de fragmentação externa, já</p><p>que a memória não é dividida em blocos uniformes. Além disso, os segmentos precisam ser</p><p>carregados inteiramente na memória. Com a inclusão das páginas dentro dos segmentos e</p><p>a operacionalização da paginação combinada à segmentação, o problema da fragmentação</p><p>externa é eliminado já que as páginas têm tamanhos iguais e os processos são carregados</p><p>parcialmente para a memória através da carga das páginas.</p><p>Com isso, concluímos o estudo das três técnicas de memória virtual e você poderá</p><p>avaliar sua compreensão em relação aos assuntos abordados através dos nossos exercícios</p><p>propostos, que são apresentados na próxima seção.</p><p>Lista de Exercícios Propostos</p><p>1. Defina o conceito de memória virtual e descreva os métodos para implementação</p><p>deste conceito. Qual a diferença básica entre os processos de segmentação e</p><p>paginação?</p><p>2. Como é feita a tradução de endereços num esquema de paginação? E num esquema</p><p>de segmentação?</p><p>3. Explique o porquê da utilização de Algoritmos de Substituição de Página. Explique</p><p>brevemente cada um deles.</p><p>4. Na sua opinião que vantagens e desvantagens você identifica em cada um dos</p><p>algoritmos citados acima? Qual deles você considera o mais adequado?</p><p>5. Considere um sistema de memória virtual composto de 512 páginas de 2Kbytes o</p><p>qual é mapeado em um espaço de endereçamento físico de 256 Kbytes.</p><p>a) Qual o formato do endereço virtual?</p><p>b) Qual o tamanho em bytes da tabela de páginas? Assuma que cada página</p><p>possui um bit de presença, 3 bits de proteção e um dirty bit. Considere ainda</p><p>que os endereços da memória secundária não estão armazenados nesta tabela.</p><p>6. Considere uma arquitetura com um sistema de memória virtual com as seguintes</p><p>50</p><p>Infraestrutura de Software</p><p>características:</p><p>» Endereço virtual de 40 bits</p><p>» Páginas de 16Kbytes</p><p>» Endereço físico de 36 bits</p><p>a) Qual o layout do endereço virtual?</p><p>b) Qual o layout e tamanho da tabela de páginas em bytes? Assuma que cada</p><p>página possui um bit de presença, 3 bits de proteção e um dirty bit. Considere</p><p>ainda que os endereços da memória secundária não estão armazenados nesta</p><p>tabela.</p><p>c) Suponha que alguém resolveu mudar o tamanho da página para 4 Kbytes. Qual</p><p>o efeito ocasionado na tabela de páginas?</p><p>7. A tabela seguinte descreve a memória virtual de um sistema paginado com páginas</p><p>de 1024 palavras. O endereço virtual é da forma [p,d] onde p refere-se à página</p><p>e d ao deslocamento dentro dela. O endereço virtual [0,514] corresponde a que</p><p>endereço real?</p><p>End. Virtual End. Real</p><p>0 3</p><p>1 -</p><p>2 4</p><p>3 0</p><p>Referências</p><p>STALLINGS, William. Arquitetura e Organização de Computadores. Ed: Prentice Hall</p><p>Brasil, 2008.</p><p>TANENBAUM, Andrew. Sistemas Operacionais Modernos. LTC, Segunda Edição, São</p><p>Paulo: Prentice-Hall, 2003.</p><p>TANENBAUM, Andrew; WOODHULL, Albert. Sistemas Operacionais - Projeto e</p><p>Implementação Ed: Bookman, 2002.</p><p>Vamos Revisar?</p><p>Neste momento, chegamos ao final do terceiro volume, onde estudamos o</p><p>sistema operacional sob o ponto de vista de gerenciador de recursos. No terceiro capítulo,</p><p>concluímos a etapa estudando o princípio de memória virtual e algumas técnicas para</p><p>implementá-la.</p><p>É importante que, ao término deste capítulo, você compreenda os princípios</p><p>51</p><p>Infraestrutura de Software</p><p>básicos da paginação e da segmentação, bem como as diferenças entre ambas. Também</p><p>é interessante conhecer as vantagens de cada uma das técnicas e entender porque uma</p><p>terceira técnica unindo as duas anteriores foi desenvolvida e como ela funciona. Esta técnica</p><p>é a segmentação com paginação e une os principais benefícios das anteriores e obtém</p><p>algumas vantagens por conta disso.</p><p>Agora que você já conhece como o S.O pode gerenciar o processamento das tarefas</p><p>e gerenciar o subsistema de memória, passaremos para um outro volume onde estudaremos</p><p>o S.O como gerenciador de arquivos e de dispositivos de entrada e saída de dados.</p><p>52</p><p>Infraestrutura de Software</p><p>Considerações Finais</p><p>Olá Cursista!</p><p>Espero que você tenha aproveitado este segundo módulo da disciplina</p><p>Infraestrutura de Software.</p><p>No próximo módulo, estudaremos Gerência de Dispositivos (Device drivers</p><p>e</p><p>dispositivos de E/S) e Sistemas de arquivos (arquivos, diretórios e alocação de espaço),</p><p>fechando portando o estudo básico dos sistemas operacionais. Esse estudo é de fundamental</p><p>importância para a compreensão de outras disciplinas que você verá futuramente, como</p><p>Redes de Computadores e Sistemas Distribuídos.</p><p>Você vai perceber a importância dos dispositivos de entrada e saída e a programação</p><p>de baixo nível que os faz interagir com os demais módulos do computador como, por</p><p>exemplo, memória e processador. Tudo isso será tratado no nível do S.O, já que estamos</p><p>caminhando para a conclusão da disciplina de Infraestrutura de Software.</p><p>Aguardamos sua participação no próximo módulo.</p><p>Até lá e bons estudos!</p><p>Juliana Regueira Basto Diniz</p><p>Professora Autora</p><p>53</p><p>Infraestrutura de Software</p><p>Conheça a Autora</p><p>Juliana Regueira Basto Diniz</p><p>Possui graduação em Engenharia Eletrônica pela Universidade Federal de</p><p>Pernambuco, mestrado e doutorado em Ciência da Computação pela Universidade Federal</p><p>de Pernambuco. Atualmente é professora da Universidade Federal Rural de Pernambuco</p><p>(UFRPE), desenvolvendo trabalhos no grupo de Educação a Distância desta universidade.</p><p>Seus temas de interesse em pesquisa são: Sistemas Distribuídos, Computação Ubíqua e</p><p>Ensino a Distância.</p><p>por uma operação de entrada e saída (E/S). Enquanto isso,</p><p>o processador se mantém ocupado e executando um outro processo, enquanto aquele está</p><p>na espera.</p><p>Para realizar essa alternância entre os diversos processos, é necessário realizar</p><p>o escalonamento. O escalonamento de processos é a chave para a multiprogramação. O</p><p>componente do S.O responsável pelo escalonamento é denominado escalonador. A sua</p><p>função é escolher qual deve ser o próximo processo a ser executado.</p><p>Mas em que situações o S.O deve escalonar? E quando houver mais de um</p><p>processo em condições de execução, ou seja, no estado “pronto”, qual o processo deve</p><p>ser selecionado para executar? Normalmente, para tomar essa decisão, o S.O executa um</p><p>algoritmo de escalonamento para determinar que processo deverá utilizar a CPU.</p><p>Observe que não existe apenas um nível de escalonamento. Se analisarmos a</p><p>situação apresentada no início do capítulo, onde você separaria as tarefas emergenciais,</p><p>veremos que há um primeiro escalonamento que é agrupar as tarefas emergenciais.</p><p>Em seguida, dentre as agrupadas como emergenciais, qual é a que deve ser realizada</p><p>inicialmente e qual a que deve ser realizada nos minutos consecutivos? Isso é um outro</p><p>nível de escalonamento.</p><p>Suponha ainda que alguma das tarefas que você estava realizando precisaria</p><p>de uma informação que alguém ficou de lhe passar por telefone. Você telefonou, mas a</p><p>pessoa do outro lado da linha lhe pediu para aguardar uns segundos enquanto ela obtinha a</p><p>informação solicitada. Como você está muito assoberbado de atividades, enquanto aguarda</p><p>a resposta com o telefone no ouvido, está digitando um texto no computador, que era uma</p><p>outra tarefa que você estava realizando e parou para dar o telefonema.</p><p>Veja que nessa situação, você não fica ocioso esperando a informação solicitada no</p><p>9</p><p>Infraestrutura de Software</p><p>telefonema. É isso que o sistema operacional faz enquanto aguarda uma operação de E/S,</p><p>por exemplo. A CPU não fica ociosa esperando o retorno de um dispositivo. Em vez disso, o</p><p>S.O escalona uma outra tarefa que poderá ser realizada, enquanto espera por um retorno</p><p>do dispositivo.</p><p>Dessa forma, podemos dizer que existem 3 níveis de escalonamento num S.O:</p><p>escalonamento de longo prazo, escalonamento de curto prazo e escalonamento de entrada/</p><p>saída que falaremos no decorrer deste capítulo.</p><p>O escalonamento no S.O também pode ser classificado como preemptivo e não-</p><p>preemptivo. Dizemos que o algoritmo de escalonamento é não-preemptivo quando um</p><p>processo executa até liberar a CPU voluntariamente. Já em um algoritmo preemptivo, o S.O</p><p>faz uso de interrupções do relógio para retirar a execução do processo da CPU.</p><p>Em geral, os algoritmos de escalonamento têm versões preemptiva e não-</p><p>preemptiva. Os algoritmos não-preemptivos podem ocasionar problemas, pois um processo</p><p>pode executar durante muito tempo e bloquear a CPU, fazendo com que outros processos</p><p>fiquem impedidos de serem executados. Esse é dos motivos pelo qual os S.O optam por</p><p>utilizar algoritmos preemptivos.</p><p>Os algoritmos de escalonamento precisam ser justos, ou seja, dar oportunidade a</p><p>todos os processos de executarem e utilizarem os recursos necessários. Além disso, uma vez</p><p>que uma política é escolhida, ela deverá ser respeitada. Voltaremos a falar desses algoritmos</p><p>e veremos mais adiante, nesse capítulo, alguns exemplos.</p><p>A seguir, falaremos um pouco sobre os níveis de escalonamento que o S.O realiza.</p><p>Escalonamento de Longo Prazo</p><p>O S.O realiza esse tipo de escalonamento no momento em que o usuário requisita</p><p>a execução de um programa, como por exemplo, um editor de textos. Pode não haver</p><p>espaço na memória para processos adicionais e o S.O, como gerenciador de recursos, tem a</p><p>função de controlar a utilização da memória. O escalonador de longo prazo determina que</p><p>programas podem ser admitidos no sistema para o processamento, controlando o número</p><p>de processos na memória.</p><p>Note que o fato do escalonador de longo prazo selecionar aquele programa não</p><p>significa que ele vai ser executado de imediato. É semelhante a situação de você agrupar as</p><p>tarefas emergenciais que você tem. Não significa que você vai executá-la imediatamente,</p><p>você só agrupou dentre as que você pretende executar em breve.</p><p>Em geral, o escalonador de longo prazo deve tomar as seguintes decisões:</p><p>1. Se pode pegar um ou mais processos adicionais, pois pode não haver disponibilidade</p><p>de memória para novos processos;</p><p>2. Caso novos processos possam ser admitidos, quais serão escolhidos. O critério</p><p>usado poderá incluir prioridade, tempo de execução e requisitos de E/S.</p><p>Para organizar o escalonamento, o sistema operacional trabalha com estruturas de</p><p>dados do tipo fila que contém diversos processos ou jobs. Associada ao escalonador de de</p><p>longo prazo, existe uma fila que recebe o nome de fila de longo prazo (do inglês, long term</p><p>queue). Essa fila contém a lista de todos os jobs que estão esperando para usar o sistema.</p><p>Note que estamos chamando os programas que devem ser executados de jobs</p><p>10</p><p>Infraestrutura de Software</p><p>e não de processos. Essa é uma nomenclatura para diferenciar o programa que está em</p><p>execução daquele que foi selecionado para execução, mas efetivamente ainda não iniciou.</p><p>Um processo é um programa em execução e um job é um programa que foi selecionado</p><p>para execução, mas ainda não começou a executar. Digamos que o job, uma vez iniciado, se</p><p>torna um processo. Como o escalonador de longo prazo atua numa fila onde os programas</p><p>estão desejando ser carregados para memória, eles, em breve, iniciarão a execução, sendo,</p><p>portanto, considerados jobs.</p><p>Escalonamento de Curto Prazo</p><p>Vimos anteriormente que o escalonador de longo prazo decide se novos processos</p><p>podem ser admitidos, baseando-se na capacidade de memória disponível, e que novos</p><p>processos são esses. Sendo assim, existem vários jobs ocupando a memória e aguardando</p><p>sua vez para executar.</p><p>O problema é decidir qual dos jobs deve utilizar o processador e quando isto deve</p><p>acontecer. É neste momento que o escalonador de curto prazo realiza o seu trabalho. Uma</p><p>vez admitido, o job torna-se um processo e é adicionado a uma fila no escalonador. A fila</p><p>recebe o nome do escalonador, sendo chamada de fila de curto prazo (do inglês, short term).</p><p>A fila de curto prazo contém todos os processos em estado “Pronto”. Um desses</p><p>processos poderá utilizar o processador, no momento seguinte. O escalonador de curto</p><p>prazo é o responsável por selecionar um deles.</p><p>Este escalonamento ocorre, em geral, em intervalos muito curtos, devendo ser o</p><p>mais rápido e eficiente possível. O escalonador de curto prazo atua quando:</p><p>» O processo está no estado “Em execução” e comuta para o estado “Em espera”;</p><p>» O processo está no estado “Em execução” e comuta para o estado “Pronto”;</p><p>» O processo está no estado “Em espera” e passa para o estado “Pronto”;</p><p>» O processo termina.</p><p>Veja que esse escalonador é aquele que determina quem será o próximo processo</p><p>a usar a CPU. O escalonador de curto prazo possui um módulo de despacho (do inglês,</p><p>dispatcher) que dá o controle da CPU ao processo selecionado. Nessa tarefa, o escalonador</p><p>realiza a chaveamento de contexto, que já foi citado anteriormente no volume 1.</p><p>Escalonamento de Entrada e Saída</p><p>Vimos que os escalonadores de longo e curto prazo têm objetivos completamente</p><p>diferentes no S.O. Entretanto, é ação de ambos que irá contribuir para a multiprogramação</p><p>e a melhoria de desempenho dos sistemas. Além desses dois escalonadores, o S.O conta</p><p>também com escalonadores de Entrada e Saída (E/S).</p><p>Esses escalonadores possuem a função de decidir que processo deverá acessar</p><p>um dispositivo de E/S. Imagine uma situação na qual mais de um processo tenta acessar</p><p>o mesmo dispositivo de E/S, uma impressora, por exemplo. Se dois processos requerem</p><p>acesso à impressora, ao mesmo tempo, o S.O precisa decidir qual deles será o próximo a</p><p>utilizar a impressora.</p><p>O escalonador de E/S utiliza uma fila de entrada e saída para cada dispositivo de E/S</p><p>11</p><p>Infraestrutura de Software</p><p>ou para um conjunto de dispositivos do mesmo tipo. Os processos que estão nessa fila serão</p><p>selecionados pelo escalonador de E/S e acessarão o dispositivo.</p><p>O esquema genérico dos diversos níveis de escalonamentos realizados pelos S.Os</p><p>estão representados na Figura 1. Observe que na figura foram colocadas 3 filas de E/S onde</p><p>cada uma delas representa um dispositivo.</p><p>Figura 1 – Filas de Escalonamento</p><p>Políticas de Escalonamento</p><p>Agora que você já conhece os níveis de escalonamento do S.O, vamos falar de</p><p>políticas que podem ser empregadas por esses escalonadores no momento de seleção dos</p><p>processos nas suas respectivas filas.</p><p>Como falamos anteriormente, as políticas de escalonamento utilizam algoritmos</p><p>que aparecem nas versões preemptiva e não-preemptiva. Falaremos inicialmente de</p><p>algoritmos não-preemptivos e em seguida passaremos aos preemptivos.</p><p>FIFO (First in First out)</p><p>Esse algoritmo é não preemptivo e baseia-se na estratégia de que o primeiro</p><p>processo a entrar na fila deverá ser o primeiro a ser atendido. O próprio nome do algoritmo</p><p>já sugere isso, pois se traduzirmos First in First out, para o português, significa, primeiro a</p><p>entrar primeiro a sair. O algoritmo também é conhecido por outros nomes como Run until</p><p>done, FCFS (First come first served).</p><p>Esse algoritmo é empregado normalmente em sistemas do tipo lote e, em geral,</p><p>possui um tempo médio de espera alto. Para você entender como ele funciona, vamos</p><p>imaginar 3 processos P1, P2 e P3 que possuem os seguintes tempos estimados de execução:</p><p>» P1 = 24 milisegundos</p><p>» P2 = 3 milisegundos</p><p>» P3 = 2 milisegundos</p><p>Caso eles entram na fila FIFO em ordem crescente, ou seja, primeiro P1, seguido</p><p>de P2 e P3 por último, o tempo médio de espera será: (0 + 24 + 27) ÷ 3 = 17ms. O significa</p><p>isso? P2 esperará 24 ms para ser executado. P3 esperará 27 ms e P1 não esperará nada, pois</p><p>será o primeiro a ser servido já que foi o primeiro a entrar na fila. Como queremos o tempo</p><p>médio de espera, tiraremos uma média aritmética, ou seja, somamos os tempos e dividimos</p><p>12</p><p>Infraestrutura de Software</p><p>por 3, chegando ao resultado 17.</p><p>Esse resultado seria diferente caso a ordem de chegada fosse modificada. Suponha</p><p>que P3 chegou primeiro, seguido de P2 e P1. O tempo médio seria (0+2+3) ÷ 3 = 1,67ms.</p><p>Entendeu? Note que a ordem com que os processos são servidos determina o tempo médio</p><p>de espera, mas em geral, o tempo de espera será alto se os processos que entram primeiro</p><p>tiverem um tempo de duração alto.</p><p>STCF (Shortest Time to Completion First)</p><p>Para superar o problema dos altos tempos de espera que o algoritmo FIFO</p><p>apresenta, foi desenvolvida a política STCF, cuja tradução determina que o job que possui</p><p>menor tempo, dentre os que estão na fila, será aquele selecionado primeiro. Isso pode</p><p>ser determinado pelo número de instruções que o processo tem para executar. Como este</p><p>também é um algoritmo não-preemptivo, uma vez entrando no processador, o processo</p><p>executa até o seu término.</p><p>Esse algoritmo fornece o menor tempo médio de espera possível entre os</p><p>processos ativos, se compararmos com a política FIFO, porém enfrenta problemas com</p><p>relação a dificuldade em se descobrir qual será o tempo que o processo que tiver acesso</p><p>ao processador passará ocupando este recurso. Em geral, essa estimativa é obtida a partir</p><p>de uma média entre os últimos tempos de utilização de processador, nas outras vezes que</p><p>aquele processo foi executado.</p><p>Para este algoritmo, quando o processador estiver livre será alocado um processo</p><p>cujo tempo de execução seja o menor dentre os processos ativos. Vamos analisar um novo</p><p>exemplo sob a ótica desse algoritmo. Imagine quatro processos P1, P2, P3 e P4 que possuem</p><p>os seguintes tempos estimados de execução:</p><p>» P1 = 6 milissegundos</p><p>» P2 = 10 milissegundos</p><p>» P3 = 7 milissegundos</p><p>» P4 = 3 milissegundos</p><p>O P4 será alocado inicialmente, pois tem o menor tempo de execução, seguido</p><p>de P1, P3 e de P2. Neste caso, o tempo médio de espera será (0 + 3+ 9 + 16) ÷ 4 = 7 ms.</p><p>Você sabe calcular quanto seria esse tempo caso fosse usada a política FIFO? É fácil, vamos</p><p>calcular: A fila seria na ordem P1, P2, P3 e P4. O tempo médio de espera seria (0+6+16+23) ÷</p><p>4 = 11,25 ms, sendo portanto, superior ao tempo gasto com a estratégia STCF.</p><p>Dentre as desvantagens dessa estratégia podemos citar a necessidade de se</p><p>conhecer os tempos estimados dos processos. Além disso, se processos com curto tempo</p><p>de duração chegam continuamente, os processos com tempos superiores nunca serão</p><p>escalonados.</p><p>Prioridades</p><p>Cada processo dentro do S.O possui uma prioridade associada a ele que é</p><p>normalmente um número inteiro de 0 a 500. Alguns S.Os utilizam a prioridade 0 como</p><p>a maior e outros utilizam o 0 como a menor. Para atribuir essas prioridades o S.O utiliza</p><p>alguns critérios como, por exemplo, limites de tempo, requisitos de memória, número de</p><p>arquivos abertos, etc. Também podem ser atribuídas por critérios externos ao S.O, como</p><p>por exemplo, a importância do processo, o usuário responsável por sua execução, etc.</p><p>13</p><p>Infraestrutura de Software</p><p>O escalonamento baseado em prioridades irá selecionar processos que sejam</p><p>considerados muito prioritários em detrimento aos demais. Esse tipo de escalonamento</p><p>pode gerar um problema grave que é o impedimento da execução de processos pouco</p><p>prioritários. Tais tipos de problemas podem ser prevenidos fazendo com que as prioridades</p><p>dos processos sejam aumentadas à medida que os processos esperam pela CPU.</p><p>Vamos agora analisar essa política através de um exemplo. Imagine 5 processos que</p><p>comportam-se de acordo com a tabela 1. A segunda coluna refere-se ao tempo estimado de</p><p>execução enquanto que a terceira coluna refere-se à prioridade.</p><p>Tabela 1 – Exemplo</p><p>Processo Tempo de execução Prioridade</p><p>P1 10 ms 4</p><p>P2 1 ms 1</p><p>P3 2 ms 3</p><p>P4 1 ms 5</p><p>P5 5 ms 2</p><p>Supondo que a prioridade maior é 4 e a menor é 1, a ordem de execução será P4,</p><p>P1, P3, P5 e P2. O tempo médio de espera pode ser calculado usando o mesmo raciocínio</p><p>anterior, chegando ao seguinte resultado:</p><p>» Tempo espera médio = (0+1+11+13+18) ÷ 5 = 8,6 ms.</p><p>Observe que o P4, por ser o primeiro da fila, não espera nada. Já o P1 espera o</p><p>tempo levado pelo P4, ou seja, 1 ms. O P3 espera a soma dos tempos de execução de</p><p>P4 com P1, ou seja, 11 ms. O P5, por sua vez, espera a soma dos tempos de P4,P1 e P3,</p><p>chegando a 13ms. Por fim, o P2 espera o equivalente à soma dos tempos de execução dos</p><p>demais processos (18ms). Somando-se todos esses tempos e tirando a média aritmética,</p><p>chegamos ao resultado 8,6 ms.</p><p>Para concluir, podemos dizer que esta política baseia-se na importância do processo</p><p>para o S.O, fazendo com que processos prioritários sejam beneficiados. Entretanto, já</p><p>falamos que isso poderá levar a uma situação onde processos de maior prioridade impedem</p><p>sempre a execução de processos de menor prioridades, prejudicando, portanto, esses</p><p>últimos.</p><p>Agora que já conhecemos três algoritmos não preemptivos, vamos conhecer as</p><p>versões preemptivas dos mesmos.</p><p>Round Robin</p><p>A política de escalonamento Round Robin é a mais comum dentre as utilizadas em</p><p>sistemas preemptivos. Como nós falamos anteriormente, os sistemas preemptivos mudam</p><p>de contexto a cada fatia de tempo, dando lugar a um novo processo. Vimos que essa política</p><p>é mais democrática, tentando atender a vários processos atendendo a cada um deles numa</p><p>fatia de tempo. Quando o processo é suspenso, ele volta para a fila e em breve torna a</p><p>executar numa fatia de tempo futura. É como se houvesse uma fila circular. Com o algoritmo</p><p>utilizado por essa política, o processo que deixa de executar, devido à mudança de contexto</p><p>do S.O, vai para o final da fila tornando a executar quando uma nova fatia de tempo de CPU</p><p>for designada ao processo.</p><p>14</p><p>Infraestrutura de Software</p><p>Esse algoritmo é semelhante ao FIFO, porém numa versão preemptiva. Um esquema</p><p>gráfico da fila de curto prazo pode ser observado na Figura 2. Observe que um processo é</p><p>executado</p><p>numa fatia de tempo, sendo seguidamente suspenso pelo S.O e voltando ao final</p><p>da fila para que em breve retorne ao processador, a partir da instrução seguinte àquela que</p><p>ele havia executado anteriormente.</p><p>Figura 2 – Round Robin</p><p>Essa política foi projetada especificamente para sistema de tempo compartilhado,</p><p>pois reparte uniformemente o tempo do processador entre todos os processos prontos.</p><p>Em geral, essa política apresenta um tempo médio de espera alto. Quando</p><p>existirem muitos processos ativos e de longa duração, os processos de menor duração</p><p>terão seu tempo de resposta degradado porque os processos de maior duração retornarão</p><p>continuamente na fila circular, compartilhando igualmente o processador com os processos</p><p>menores.</p><p>E então, ficou claro para você como funciona essa política? Para ficar mais fácil</p><p>ainda, vamos imaginar o seguinte exemplo:</p><p>Três processos de mesmo tamanho estão em espera para executar. Cada um requer</p><p>60 ms de uma CPU, cuja fatia de tempo é de 10ms. Determine o instante em que cada</p><p>processo conclui a execução. Considere a utilização de round-robin.</p><p>Bem, inicialmente vamos dar nomes aos processos. Chamaremos de P1, P2 e P3</p><p>e vamos imaginar que os três chegam para execução no instante t=0. Cada processo vai</p><p>utilizar a CPU, durante uma fatia de tempo, que no caso deste exemplo é 10 ms. A cada 10</p><p>ms, um novo processo entra em execução e o processo antigo retorna à fila circular.</p><p>O esquema de execução é visualizado na Figura 3. Observe que o processo P1 é o</p><p>primeiro da fila de curto prazo, que tem o seu início no lado esquerdo da figura. No passo</p><p>1, o processo P1 entra em execução saindo da fila de curto prazo. Ele executará por 10 ms,</p><p>ou seja 1/6 do seu tempo total, devendo voltar para o final da fila no passo 2, quando dará</p><p>a vez ao processo P2 (o segundo da fila) que executará pelos próximos 10 ms, seguindo a</p><p>fila circular, dando a vez ao processo P3 que executará pelos 10 ms seguintes, retornando</p><p>ao fim da fila, em seguida. Note que agora será a vez do P1 entrar em execução novamente,</p><p>executando a sua segunda fatia e assim sucessivamente, conforme observamos na Figura 4.</p><p>Figura 3 – Exemplo</p><p>Observe que um processo deve entrar no processador n vezes, onde n é o número</p><p>15</p><p>Infraestrutura de Software</p><p>mínimo de vezes que o processo deve ser escalonado. N é obtido através da divisão do</p><p>tempo de duração do processo/fatia de tempo da CPU. No caso do exemplo, se dividirmos</p><p>60 (duração do processo) por 10 (fatia de tempo) chegaremos a n=6 que é o número de</p><p>vezes que cada processo é escalonado. O esquema fica organizado conforme apresentado</p><p>na Figura 4.</p><p>Perceba que cada processo é escalonado 6 vezes para que os 60 ms de sua duração</p><p>sejam concluídos. Para descobrir qual o instante em que o P1 termina a sua execução, basta</p><p>somar todas as fatias de tempo, considerando que o instante inicial é t=0 ms. Temos então</p><p>que o P1 terminou em t=160 ms, o P2 terminou em t=170 ms e o P3 em t=180 ms.</p><p>Figura 4 – Resultado do Exemplo</p><p>Note que a fatia de tempo que o S.O disponibiliza para executar um processo e</p><p>mudar o contexto irá afetar o seu desempenho. Se essa fatia de tempo for muito grande,</p><p>cada processo recebe mais tempo do que necessita para executar, tornando essa política</p><p>semelhante à política FIFO. Por outro lado, se essa fatia for muito pequena, a troca de</p><p>contexto torna-se uma sobrecarga, de modo que o sistema perde mais tempo trocando o</p><p>processo a ser executado do que, propriamente, executando-os.</p><p>SRTCF (Shortest Remaining Time to Completion First)</p><p>A política que lhe será apresentada agora é uma versão preemptiva da STCF que</p><p>falamos anteriormente. Relembrando, a política STCF é aquela na qual o job que possui</p><p>menor tempo, dentre os que estão na fila, será aquele selecionado primeiro.</p><p>Quando falamos numa política semelhante, porém que trabalhe de forma</p><p>preemptiva, significa que, se chegar um novo processo com tempo estimado de execução</p><p>menor que o processo atualmente em execução, este novo será escalonado, interrompendo,</p><p>portanto, a execução atual.</p><p>Essa política funciona bem para os processos de menor tempo de duração e mais</p><p>novos, pois eles, em geral, tendem a esperar menos tempo. Para os processos de maior</p><p>tempo de duração, essa política acarreta em um tempo de espera grande, já que processos</p><p>menores são escalonados primeiro.</p><p>Escalonamento em Múltiplas Filas com diferentes</p><p>Prioridades</p><p>Quando são utilizadas múltiplas filas com diferentes prioridades, cada fila poderá</p><p>utilizar um algoritmo de escalonamento diferente. Por exemplo, uma fila pode utilizar</p><p>o escalonamento round robin enquanto outra utiliza o FIFO. Cada fila pode possuir uma</p><p>prioridade diferente, de modo que a maior delas comporta-se de maneira prioritária dentre</p><p>as demais e o tempo do processador pode ser compartilhado entre elas. Por exemplo, numa</p><p>16</p><p>Infraestrutura de Software</p><p>situação onde existem 3 filas, cada uma delas pode receber 30% do tempo do processador.</p><p>Uma outra situação possível seria o S.O atribuir 50% do seu tempo para a fila de maior</p><p>prioridade dentre as 3 e 30 e 20%, respectivamente para as duas outras filas.</p><p>Nesse escalonamento com diversas filas com diferentes prioridades, quando um</p><p>processo é direcionado a uma fila, ele deverá permanecer na mesma até sua conclusão.</p><p>Uma variação deste modelo é denominada escalonamento em cascata onde os processos</p><p>podem ser movido entre as filas.</p><p>No escalonamento em cascata, os processos são separados de acordo com</p><p>características de uso da CPU. De maneira geral, esse tipo de escalonamento atende de</p><p>maneira prioritária aos processos interativos.</p><p>Saiba Mais</p><p>Até o momento estudamos diversas políticas de escalonamento e analisamos os</p><p>pontos positivos e negativos das mesmas. Observe que todas elas, preemptivas ou não,</p><p>são limitadas ao uso de uma CPU. Em nenhum momento, trabalhamos com a situação de</p><p>multiprocessamento, onde mais de uma CPU trabalham sob o mesmo S.O. Você deve estar</p><p>se perguntando se essas mesmas políticas são aplicáveis a sistemas multiprocessados. Para</p><p>os sistemas multiprocessados, existem algumas abordagens especiais para o escalonamento.</p><p>O S.O poderá prover filas separadas de processos prontos para executar, de modo</p><p>que cada CPU possua sua própria fila. A desvantagem dessa abordagem é que se uma CPU</p><p>ficar desocupada, devido a inexistência de processos em sua fila, os processos da fila de</p><p>outra CPU não poderão ser realocados àquela que está ociosa. Dessa forma, haverá uma</p><p>CPU ociosa, enquanto as outras podem estar sobrecarregadas com muitos processos.</p><p>Uma segunda abordagem utiliza uma única fila de processos compartilhada por</p><p>todas as CPUs. Nesta abordagem, existem duas possibilidades de funcionamento:</p><p>» Multiprocessamento simétrico, no qual todas as CPUs têm a função de escalonar</p><p>processos. Cada CPU seleciona um processo na fila para execução. É importante</p><p>observar que a fila de processos será um recurso compartilhado, de modo que, o</p><p>seu uso concorrente, por diversos processadores, deve ser sincronizado.</p><p>» Multiprocessamento assimétrico define uma CPU que funcionará como mestre e as</p><p>demais atuarão como escravas. A CPU mestre será responsável pelo escalonamento</p><p>direcionando os processos para execução para as demais CPUs escravas.</p><p>Aprenda Praticando</p><p>Para consolidar os conhecimentos adquiridos sobre escalonamento de processos,</p><p>apresentados por esse capítulo, você poderá acompanhar a resolução do exercício 1,</p><p>conforme descrito a seguir:</p><p>Exercício Resolvido</p><p>Considere a tabela mostrando um conjunto de jobs a serem processados em um</p><p>único processador. Em cada linha está representado o tempo necessário para execução e o</p><p>instante que o processo está pronto para executar. Qual o instante em que o job 3 termina,</p><p>17</p><p>Infraestrutura de Software</p><p>considerando que Round-Robin é utilizado com uma fatia de 100ms?</p><p>Job Tempo necessário (s)</p><p>Instante em que</p><p>está pronto (s)</p><p>1 2 T0</p><p>2 5 T0</p><p>3 1 T0+1</p><p>4 2 T0+2</p><p>Para resolvermos esse exercício, precisamos</p><p>considerar alguns pontos de acordo</p><p>com a tabela fornecida:</p><p>» O instante T0 é o instante inicial;</p><p>» Os jobs 1 e 2 iniciam no instante T0;</p><p>» O job 3 inicia 1 segundo após os jobs 1 e 2;</p><p>» O job 4 inicia 2 segundos após os jobs 1 e 2.</p><p>Lembre-se que 1 segundo equivale a 10 * 100ms = 1.000ms. Para facilitar vamos</p><p>converter 100ms para a unidade segundos dividindo 100/1000 = 0,1 segundos.</p><p>Dessa forma, cada processo vai utilizar a CPU durante uma fatia de tempo, que no</p><p>caso deste exemplo é 0,1 segundos. A cada 0,1 s, um novo processo entra em execução e o</p><p>processo antigo retorna à fila circular.</p><p>O esquema de execução é visualizado na Figura 5. Inicialmente entram na fila</p><p>apenas os jobs 1 e 2. Observe que o job 1 é o primeiro da fila de curto prazo, que tem o seu</p><p>início no lado esquerdo da figura. No passo 1, o job 1 entra em execução saindo da fila de</p><p>curto prazo. Ele executará por 0,1 s, ou seja, precisará entrar na fila 20 vezes para concluir o</p><p>seu tempo total de execução, devendo voltar para o final da fila no passo 2, quando dará a</p><p>vez ao job 2 (o segundo da fila) que executará pelos próximos 0,1 s, seguindo a fila circular.</p><p>O job 2, por sua vez, precisa entrar na fila 50 vezes para concluir a sua execução, já que o</p><p>tempo necessário a sua conclusão é 5 segundos. Até o instante t =T0 + 1 segundo, apenas</p><p>os jobs 1 e 2 estão na fila. Podemos observar a execução dos dois primeiros jobs na Figura 6,</p><p>até o instante t = T0 + 1 segundo.</p><p>Figura 5</p><p>18</p><p>Infraestrutura de Software</p><p>Figura 6</p><p>Note que no instante t= T0 + 1, é o momento em que o job 3 inicia, porém ao</p><p>entrar na fila de curto prazo, ele já encontrará os jobs 1 e 2 que estão em execução, então</p><p>efetivamente, o job 3 só iniciará em T0 + 1,2 segundos e o S.O passa a alternar entre os jobs</p><p>1, 2 e 3, até o instante T0+ 2 segundos, conforme poderemos observar na Figura 7. Nesse</p><p>último instante, o job 4 entra na fila e já encontra os jobs 2, 3 e 1, postergando o seu início</p><p>para T0 + 2,3 segundos.</p><p>Figura 7</p><p>Seguindo a linha do tempo, os 4 jobs continuarão a compartilhar o processador de</p><p>modo que cada um usa o processador por 0,1 segundo por vez. Note que o job 3 precisa</p><p>entrar na fila 10 vezes para concluir a sua execução enquanto que o job 4 precisará entrar</p><p>na fila 20 vezes.</p><p>Vamos agora à pergunta do exercício: qual o instante em que o job 3 termina? Para</p><p>chegarmos a essa resposta, vamos resumir as informações com relação ao número de vezes</p><p>que o job precisa entrar na fila e utilizar o processador:</p><p>Job Vezes que precisa entrar na fila para ser concluído</p><p>1 20 vezes</p><p>2 50 vezes</p><p>3 10 vezes</p><p>4 20 vezes</p><p>Utilizando o mesmo raciocínio, continuamos a observar a linha de tempo da</p><p>execução dos job e verificamos que o job 3 completa as 10 vezes que ele entra na fila no</p><p>instante T0 + 4,6 segundos, conforme podemos observar na Figura 8.</p><p>19</p><p>Infraestrutura de Software</p><p>Figura 8</p><p>Dessa forma, a resposta à pergunta do exercício será T0 + 4,6 segundos, ou seja, 4,6</p><p>segundos após o instante inicial considerado na questão.</p><p>E então, o que achou da questão? Fácil?</p><p>Sugestão: Você pode modificar os tempos de duração e de início de cada job</p><p>e tentar reformular o exercício. Tente fazer isso e repasse para um colega para ver se ele</p><p>consegue resolver. Tente resolver o exercício proposto pelo seu colega e cheque com ele se</p><p>você chegou na resposta correta.</p><p>Agora que você já sabe o que é o escalonamento de processos e conhece diversas</p><p>políticas utilizadas pelos sistemas operacionais para se escalonar, é interessante você tentar</p><p>responder as questões da lista de exercícios propostos, a seguir.</p><p>Lista de Exercícios Propostos</p><p>1. O que significa um sistema operacional ser preemptivo?</p><p>2. Explique como funciona o algoritmo de escalonamento FIFO. Qual a sua versão</p><p>preemptiva? Explique.</p><p>3. Considere a tabela mostrando um conjunto de jobs a serem processados em um</p><p>único processador. Em cada linha está representado o tempo necessário para</p><p>execução e o instante que o processo está pronto para executar. Qual o instante em</p><p>que o job 4 termina, considerando que Round-Robin é utilizado com uma fatia de</p><p>500 ms?</p><p>Job Tempo necessário (s) Instante em que está pronto</p><p>1 2 T0</p><p>2 5 T0</p><p>3 1 T0+1</p><p>4 2 T0+2</p><p>4. Descreva as diferenças entre o escalonamento de curto prazo e longo prazo.</p><p>20</p><p>Infraestrutura de Software</p><p>5. Quais as principais diferenças entre o algoritmo de escalonamento STCF e SRTCF?</p><p>6. Faça um comparativo entre os algoritmos FIFO e STCF.</p><p>7. Faça um comparativo entre os algoritmos Round robin e SRTCF.</p><p>8. Quais as vantagens em se utilizar algoritmos baseados em filas de prioridades?</p><p>9. Em sistemas multiprocessados, quais as possíveis abordagens para o escalonamento</p><p>de processos?</p><p>10. Dez processos de mesmo tamanho estão em espera para executar. Cada um requer</p><p>100 ms de CPU, a fatia de tempo da CPU é de 10 ms. Determine o instante em que</p><p>cada processo conclui a execução. Considere a utilização de round-robin e compare</p><p>com FIFO.</p><p>Atividades e Orientações de Estudo</p><p>Você deverá dedicar, pelo menos, 6 horas de estudo para o Capítulo 1, para</p><p>absorver o conteúdo de forma satisfatória. Você deve se organizar para realizar a leitura dos</p><p>conceitos apresentados no capítulo, compreender os exemplos e exercícios resolvidos e só</p><p>então partir para responder as perguntas da seção Aprenda Praticando. Não esqueça de</p><p>ler a seção Saiba mais, pois os exercícios também referem-se ao que foi apresentado nesta</p><p>seção.</p><p>Através dos fóruns da disciplina, você poderá trocar informações sobre o conteúdo</p><p>no ambiente virtual, com seus colegas, tutores e o professor da disciplina. O trabalho</p><p>integrado de professores, tutores e principalmente o seu, aluno, irá contribuir para um bom</p><p>aproveitamento da disciplina.</p><p>Através de ferramentas como chats, fóruns e e-mail você poderá interagir para</p><p>sanar suas dúvidas e fazê-lo transpor os obstáculos do aprendizado.</p><p>Referências</p><p>STALLINGS, William. Arquitetura e Organização de Computadores. Ed: Prentice Hall</p><p>Brasil, 2008.</p><p>TANENBAUM, Andrew. Sistemas Operacionais Modernos. LTC, Segunda Edição, São</p><p>Paulo: Prentice-Hall, 2003.</p><p>TANENBAUM, Andrew; WOODHULL, Albert. Sistemas Operacionais - Projeto e</p><p>Implementação Ed: Bookman, 2002.</p><p>Vamos Revisar?</p><p>Chegamos ao final deste primeiro capítulo onde pudemos conhecer os princípios que</p><p>norteiam uma das principais tarefas dos sistemas operacionais modernos, o escalonamento</p><p>21</p><p>Infraestrutura de Software</p><p>de processos, bem como o princípio de funcionamento das filas de processos e as principais</p><p>políticas utilizadas no escalonamento.</p><p>É importante que ao término deste capítulo, você compreenda os principais</p><p>algoritmos de escalonamentos e conheça as suas limitações. Também é interessante</p><p>conhecer as principais filas de processos em diversos níveis.</p><p>Agora que você já conhece como o S.O pode gerenciar o processamento das</p><p>tarefas, vale a pena conhecer o gerenciamento de outro recurso importante: o subsistema</p><p>de memória e suas diversas técnicas de gerenciamento, como paginação, segmentação e</p><p>paginação com segmentação.</p><p>22</p><p>Infraestrutura de Software</p><p>Capítulo 2</p><p>O que vamos estudar neste capítulo?</p><p>Neste capítulo, vamos estudar os seguintes temas:</p><p>» Princípios que norteiam o gerenciamento do subsistema de memória;</p><p>» Técnicas de gerenciamento de memória:</p><p>› Paginação;</p><p>› Segmentação;</p><p>› Paginação com Segmentação.</p><p>Metas</p><p>Após o estudo deste capítulo, esperamos que você consiga:</p><p>» Conhecer os princípios básicos do gerenciamento do subsistema de memória</p><p>utilizados pelos sistemas operacionais modernos;</p><p>» Aprender sobre as diversas técnicas de gerenciamento de memória;</p><p>» Compreender as diferenças entre as técnicas estudadas.</p><p>23</p><p>Infraestrutura de Software</p><p>Capítulo 2 – Gerenciamento de</p><p>Memória</p><p>Vamos conversar sobre o assunto?</p><p>O objetivo desde segundo volume do material didático da disciplina de</p><p>Infraestrutura de Software é estudar as funções de gerenciamento de recursos providas pelo</p><p>sistema operacional. No primeiro capítulo, estudamos</p><p>gerenciamento do principal recurso</p><p>do sistema computacional, o processador. Estudamos o escalonamento de processos nos</p><p>seus diversos níveis e as suas respectivas filas.</p><p>Sabemos que o S.O é um software que gerencia todos os recursos da máquina</p><p>que o comporta, e ao mesmo tempo, ele é responsável por criar uma interface entre os</p><p>seus usuários e o hardware. Sabemos que a memória também é um recurso gerenciado</p><p>pelo sistema operacional e que os computadores possuem uma hierarquia que relaciona as</p><p>grandezas custo, tamanho e velocidade das memórias.</p><p>Agora, neste segundo capítulo, chegou o momento de conhecer as técnicas de</p><p>gerenciamento do subsistema de memória utilizadas pelo sistema operacional.</p><p>Para iniciarmos esse estudo, começaremos falando de um módulo do sistema</p><p>operacional que é responsável por essa tarefa que é chamado gerenciador de memória.</p><p>O gerenciador de memória é o componente do sistema operacional responsável pela ação</p><p>de gerenciar tal recurso. Dentre as tarefas desse gerenciador estão o controle das partes</p><p>livres e em uso da memória, a alocação e desalocação da memória para processos e o</p><p>gerenciamento da troca de processos entre a memória e o disco rígido.</p><p>Estudaremos basicamente as técnicas de paginação, segmentação e paginação com</p><p>segmentação.</p><p>Como falamos anteriormente, memória é um dos recursos gerenciados pelo</p><p>sistema operacional. O Gerenciamento de Memória é a tarefa realizada pelo sistema</p><p>operacional que objetiva subdividir e alocar dinamicamente a memória. É a partir dessa</p><p>tarefa de gerenciamento que os sistemas operacionais podem utilizar a multiprogramação.</p><p>Remetendo ao conteúdo abordado na disciplina de Infraestrutura de Hardware,</p><p>lembramos que os computadores possuem uma hierarquia de memória que relacionam as</p><p>grandezas custo, tamanho e velocidade.</p><p>Essa hierarquia apresenta-se como uma pirâmide onde os registradores são as</p><p>memórias representadas no topo. São as memórias mais rápidas, menores e mais caras.</p><p>Abaixo deles estão as memórias do tipo cache, ou seja, são mais lentas que os registradores</p><p>entretanto, maiores e menos custosas. No terceiro nível, estão as memórias chamadas de</p><p>principal, ou seja, são ainda mais lentas, maiores e menos custosas que a memória cache.</p><p>Descendo um nível em direção a base da pirâmide, encontramos os discos rígidos (HDs, Cds,</p><p>DVDs, etc). Essa pirâmide pode ser relembrada na Figura 1.</p><p>24</p><p>Infraestrutura de Software</p><p>Figura 1 – Pirâmide de Hierarquia de Memória</p><p>Para fazer o bom uso de todas as memórias disponíveis no computador, o sistema</p><p>operacional conta com um módulo de software interno denominado Gerenciador de</p><p>Memória. Esse componente é responsável pelo gerenciamento das memórias internas e</p><p>externas. Dentre as diversas tarefas desempenhadas por esse componente, podemos citar:</p><p>» Controle das partes livres e em uso da memória;</p><p>» Alocação e desalocação da memória para processos;</p><p>» Gerenciamento da troca de processos entre a memória e o disco.</p><p>Como citamos anteriormente, a principal motivação para o gerenciamento de</p><p>memória por parte dos sistemas operacionais é permitir a multiprogramação. Vamos</p><p>entender, então, o porquê dessa importância!</p><p>Em sistemas uniprogramados a memória é dividida em 2 partes. A parte do sistema</p><p>operacional e a parte do único programa em execução. Já nos sistemas multiprogramados,</p><p>a memória é compartilhada entre o S.O e uma outra parte disponível para o uso dos</p><p>processos. Essa última deve ser compartilhada entre diversos processos. Cabe ao sistema</p><p>operacional administrar eficientemente a memória com o objetivo de minimizar tempo de</p><p>espera e maximizar a responsividade de cada processo. Mas como ele faz isso?</p><p>Já sabemos que o S.O utiliza os escalonadores para fazer essa multiprogramação</p><p>funcionar eficientemente. Os escalonadores atuam diretamente no processador, mas</p><p>precisa utilizar uma área de trabalho para carregar os processos em execução, em espera e</p><p>no estado pronto para execução. Como ele gerencia essa área de trabalho é exatamente o</p><p>foco do nosso estudo neste capítulo do volume 2 deste material didático.</p><p>Administrar neste caso não é uma tarefa fácil, pois o S.O precisará definir uma</p><p>organização lógica na memória que permite isolar e escalonar vários processos. Durante</p><p>este processo, o primeiro problema que encontramos é a limitação no tamanho da memória.</p><p>Então você pode pensar “ora, mas as memórias estão cada vez maiores! A memória principal</p><p>pode ser expandida e então ser capaz de acomodar mais processos.” É verdade, a tecnologia</p><p>de construção de memórias tem evoluído bastante e hoje se é possível construir memórias</p><p>muito maiores que há 5 anos. Porém não esqueça que os programas requerem cada vez mais</p><p>memória para a sua execução. Vocês lembram quanto consumia um programa aplicativo</p><p>que instalávamos em nosso PC há 5 anos? Com certeza esse programa tinha menos recursos</p><p>que a sua versão atualmente usada, porém consumia menos memória. Uma memória maior</p><p>resulta em processos maiores e não em mais processos.</p><p>25</p><p>Infraestrutura de Software</p><p>Assim, podemos dizer que não adianta aumentar consideravelmente o tamanho</p><p>das memórias para se resolver o problema de alocar mais programas na memória, de modo</p><p>a facilitar a multiprogramação. Não será possível incluir todos os processos na memória. O</p><p>S.O precisa utilizar técnicas que permitam o melhor uso da área destinada aos programas na</p><p>memória e essas técnicas são baseadas no gerenciamento de memória.</p><p>Vamos analisar ainda uma outra situação prática onde o gerenciamento de memória</p><p>se faz necessário. Imagine uma situação, onde todos os processos da memória estão</p><p>aguardando resposta de operações de entrada e saída (E/S) e o processador está disponível</p><p>sendo capaz de pegar mais processos, mas estes já não cabem na memória... Vimos que os</p><p>dispositivos de E/S são mais lentos que a própria CPU e para otimizar os recursos, enquanto</p><p>aguarda o retorno de uma operação de E/S o processador faz uma outra tarefa. Mas se</p><p>todas as tarefas estão no aguardo de respostas de dispositivos de E/S?</p><p>Bem, a solução mais completa deve envolver o compartilhamento da memória</p><p>entre vários processos. Entretanto, para que eles não utilizem porções grandes da memória,</p><p>é interessante permitir que eles sejam apenas parcialmente carregados. Mas qual é a</p><p>quantidade ideal de processos que a memória deve armazenar simultaneamente para que</p><p>um processador fique o máximo ocupado, evitando assim, situações como as do exemplo</p><p>acima?</p><p>Vamos estudar agora algumas técnicas que permitem a divisão da memória em</p><p>partições. Essas técnicas são úteis para o gerenciamento de memória e podem ser utilizadas</p><p>com partições de tamanho fixo ou com tamanhos diferentes.</p><p>Particionamento da Memória</p><p>Para que a memória possa ser utilizada por vários processos, ela é dividida em</p><p>regiões, chamadas de partições. Cada partição é utilizada por apenas um processo, de modo</p><p>que quando ele é trazido para a memória, é alocado na partição disponível.</p><p>Esse particionamento da memória pode ser organizado em partições de tamanho</p><p>fixo ou em partições de tamanho variável.</p><p>Particionamento Fixo</p><p>Na organização com partições fixas, as partições têm tamanhos diferentes,</p><p>porém fixos. Um exemplo da divisão da memória com partições de tamanho fixo pode ser</p><p>observado na Figura 2. Note que a memória está dividida em 2 áreas: a parte referente pelo</p><p>sistema operacional e a parte que deverá ser compartilhada pelos demais processos. As</p><p>partições não possuem o mesmo tamanho, como é possível notar (64K, 192K, 256K, 384K).</p><p>Figura 2 – Particionamento Fixo</p><p>26</p><p>Infraestrutura de Software</p><p>Com essa primeira técnica, é possível acomodar processos com tamanhos distintos</p><p>na memória. Por outro lado, essa técnica traz alguns problemas como, por exemplo, a</p><p>fragmentação interna. Mas o que significa fragmentação interna? Bem, a fragmentação é</p><p>é uma situação na qual a memória fica com pequenos fragmentos livres, tão pequenos ao</p><p>ponto de não conseguir acomodar mais nenhum processo.</p><p>Esses fragmentos são espaços</p><p>livres que são desperdiçados. A questão de ser interna se aplica, uma vez que os espaços</p><p>livres estão localizados dentro dessas partições de tamanho fixo. Mas o que provoca essa</p><p>fragmentação?</p><p>Na maioria dos casos, o processo não irá requerer a quantidade de memória</p><p>oferecida pela partição e dessa forma, há uma subutilização da partição, conforme</p><p>observamos na Figura 3.</p><p>Figura 3 – Fragmentação Interna</p><p>Além disso, quando um processo fica no aguardo por alguma ação externa, como</p><p>por exemplo, uma resposta de um dispositivo de E/S, ele ficará no estado de espera e será</p><p>levado a um espaço na memória secundária enquanto essa resposta não vem. Apenas</p><p>quando ele volta ao estado pronto é que poderá voltar para memória e não necessariamente</p><p>ocupará a mesma partição que antes.</p><p>Essa ação irá introduzir um outro problema que está associado aos endereços de</p><p>memória que armazenam os processos. Processos diferentes vão ficar armazenados em</p><p>endereços diferentes, de modo que, antes do programa ser carregado para a memória, ele</p><p>passa pela etapa de link-edição e neste momento, as suas “partes” são organizadas em um</p><p>único espaço de endereçamento.</p><p>Quando o processo é realocado, os apontadores para os endereços de memória</p><p>que contém as instruções específicas do programa ficarão desatualizados, inviabilizando</p><p>a sua execução. Para evitar que problemas deste tipo ocorram, endereços relativos das</p><p>instruções podem ser utilizados, de modo que todas as instruções de um processo estejam</p><p>referenciadas através de um endereço relativo à primeira instrução do programa que</p><p>representa aquele processo. Sendo assim, no momento em que a realocação acontece, os</p><p>endereços relativos devem ser atualizados de acordo com a partição que irá armazenar o</p><p>programa.</p><p>Para diminuir o problema da fragmentação interna, o S.O pode fazer uso de filas</p><p>de partição de modo que cada processo é alocado na fila para aquela menor partição cujo</p><p>tamanho disponível é compatível com o seu, ou seja, a menor partição que lhe couber.</p><p>O esquema de fila para uso das partições pode ser operado de duas maneiras:</p><p>27</p><p>Infraestrutura de Software</p><p>» Múltiplas filas: cada processo é colocado na fila da menor partição capaz de</p><p>armazená-lo;</p><p>» Única fila: todos os processos são colocados em uma mesma fila.</p><p>No esquema de múltiplas filas, as filas de partições pequenas ficam sempre cheias,</p><p>pois visam minimizar a fragmentação. Uma solução para reduzir esse gargalo nas filas de</p><p>partições pequenas é utilizar o esquema de fila única. Os esquemas de fila para o uso das</p><p>partições são apresentados na Figura 4.</p><p>Figura 4 – Esquema de Filas</p><p>Na próxima seção, veremos uma outra estratégia de particionamento onde a</p><p>alocação da partição é realizada dinamicamente a fim de evitar o desperdício de espaço que</p><p>ocorre na estratégia de particionamento fixo.</p><p>Particionamento Variável</p><p>Essa técnica surgiu como uma forma de superar as dificuldades relativas ao</p><p>desperdício de espaço e a fragmentação interna ocasionada pela técnica de particionamento</p><p>fixo.</p><p>Com o particionamento variável, quando um processo é trazido para a memória,</p><p>o espaço alocado para ele é exatamente a quantidade de memória requerida e não uma</p><p>quantidade maior que a necessária.</p><p>Aparentemente é uma técnica mais eficiente. Entretanto apenas em um primeiro</p><p>momento. Vamos entender o porquê!</p><p>Vamos analisar a Figura 5, que apresenta a execução de 5 processos. No momento</p><p>inicial, a memória só está ocupada pelo sistema operacional. Em seguida, os processos 1,</p><p>2 e 3 entram na memória e o S.O aloca a quantidade de memória exata para comportar</p><p>cada um dos 3 processos. Esta situação é ilustrada no primeiro retângulo da Figura 5, da</p><p>esquerda para a direita. A área hachurada representa o espaço livre.</p><p>28</p><p>Infraestrutura de Software</p><p>Figura 5 – Particionamento Variável</p><p>No segundo momento (representado pelo segundo retângulo da Figura 5),</p><p>o processo 2 é concluído e libera o espaço na memória. Em seguida (representado pelo</p><p>terceiro retângulo da Figura 5), um novo processo (4) entra na memória e o sistema</p><p>operacional o aloca no espaço onde estava o processo 2. Entretanto, o processo 4 precisa de</p><p>menos espaço que o processo 2, de modo que haverá uma sobra de espaço na partição. No</p><p>quarto momento, o processo 1 conclui, restando apenas os processos 3 e 4 em memória e</p><p>liberando uma outra área. Dessa forma, observe que no quinto e último retângulo da Figura</p><p>5, a memória está toda fragmentada. Essa técnica inicia bem, porém com o passar do tempo,</p><p>os processos vão sendo alocados e concluídos e novos processos ocupam aquela área e</p><p>estes últimos, não necessariamente, são do mesmo tamanho dos primeiros, ocasionando</p><p>a fragmentação. Observe ainda que este tipo de fragmentação é diferente do ocorrido no</p><p>particionamento fixo, pois os fragmentos estão fora das partições, sendo este problema</p><p>conhecido, portanto, como fragmentação externa.</p><p>A fragmentação externa é ocasionada pelo surgimento de lacunas, cada vez</p><p>menores, na memória devido ao término ou suspensão temporária da execução dos</p><p>processos. Em um determinado ponto crítico, não é possível escalonar nenhum job para</p><p>aquele espaço. À medida que o tempo passa, a memória torna-se mais e mais fragmentada</p><p>e sua utilização declina. Essa técnica de particionamento inicia bem, mas eventualmente</p><p>chega numa situação onde existem muitos pequenos espaços na memória.</p><p>Uma maneira de tentar resolver esse problema é através de uma técnica conhecida</p><p>por Compactação. Ela baseia-se no deslocamento dos processos na memória, colocando</p><p>toda memória disponível em bloco. Essa ação é realizada periodicamente pelo sistema</p><p>operacional, porém consome tempo de CPU. É uma técnica semelhante à desfragmentação</p><p>de um disco rígido. Você já tentou desfragmentar o HD do seu computador? Normalmente,</p><p>os S.Os disponibilizam um utilitário de desfragmentação de disco. Se você nunca fez isso</p><p>antes, tente fazer e verá que consome um tempo relativamente alto da CPU.</p><p>Veja como a memória do exemplo da Figura 5 ficará após a reorganização, na</p><p>Figura 6.</p><p>Figura 6 – Reorganização da Memória</p><p>29</p><p>Infraestrutura de Software</p><p>Apesar de resolver o problema da fragmentação externa, a reorganização poderá</p><p>acarretar um outro problema, pois as instruções nos processos (lembre-se que processos são</p><p>programas) contêm endereços de memória que representam itens de dados ou endereços</p><p>para instruções de desvio. Como houve o deslocamento, esses endereços não são mais fixos</p><p>e os desvios podem apontar para endereços de memórias que não mais contêm a instrução</p><p>procurada. Note na Figura 7, como ficaria o exemplo anterior, se após a reorganização, os</p><p>endereços utilizados fossem absolutos. O processo 3 acessaria uma posição inválida da</p><p>memória.</p><p>Figura 7 – Memória após Reorganização</p><p>Essa questão pode ser resolvida fazendo uma distinção entre o endereço lógico e o</p><p>físico. Mas o que significam endereços físico e lógico? O endereçamento lógico é expressado</p><p>como a localização relativa ao início do programa. As instruções no programa contêm</p><p>apenas o endereço lógico.</p><p>O endereço físico, por sua vez, é uma localização real na memória principal.</p><p>Quando a CPU executa um processo, ele automaticamente converte da localização física</p><p>adicionando a localização real do início do processo para cada endereço lógico. Sendo assim,</p><p>o S.O trabalhará com os endereços lógicos, resolvendo então os problemas de referência</p><p>ocasionados pela reorganização da memória.</p><p>Após analisarmos duas técnicas de particionamento de memória, podemos</p><p>concluir que ambas não são suficientes para o gerenciamento eficiente da memória, pois</p><p>tais técnicas utilizadas de maneira isolada não permitem que os processos sejam apenas</p><p>parcialmente carregados para memória.</p><p>Dessa forma, continuaremos o nosso estudo abordando um outro conceito que visa</p><p>utilizar a memória secundária como área de apoio para o armazenamento de programas</p><p>durante a sua execução.</p><p>Swapping de Processos</p><p>No início da</p><p>seção anterior, falamos de uma situação na qual a memória estava</p><p>cheia e que todos os processos estavam no estado de espera, aguardando retorno de</p><p>dispositivo de entrada e saída. E então, o que pode ser feito nesses casos para se evitar o</p><p>tempo ocioso do processador?</p><p>O conceito de swapping1 vai ao encontro desta necessidade, pois o seu uso permite</p><p>que o processo seja descarregado (swapped out) da memória principal para a memória</p><p>secundária (disco rígido). No momento em que o processo é levado à memória secundária,</p><p>ele entra em uma fila intermediária, dando oportunidade a outros que estão na fila de curto</p><p>prazo a iniciarem a sua execução.</p><p>Você Sabia?</p><p>1 Você sabia que o</p><p>S.O Windows reserva</p><p>uma porcentagem</p><p>do HD para realizar</p><p>o swapping? Já no</p><p>Linux, o sistema pode</p><p>utilizar uma partição</p><p>específica para esta</p><p>função, melhorando o</p><p>desempenho. Também</p><p>pode ser utilizado um</p><p>arquivo de paginação</p><p>no disco.</p><p>30</p><p>Infraestrutura de Software</p><p>Essa estratégia para gerenciamento de memória é utilizada quando todos os</p><p>processos ativos não cabem na memória principal e são então mantidos em disco. Na ideia</p><p>básica do swapping, o processo é trazido inteiro para a memória principal, utiliza o tempo de</p><p>CPU que lhe é devido e, posteriormente, é armazenado novamente em disco. Um esquema</p><p>geral representando a técnica de swapping é apresentado na Figura 8.</p><p>Figura 8 – Swapping de Processos</p><p>Observe que as filas de longo prazo e intermediária, estudadas no capítulo1,</p><p>apesar de estarem na ilustração armazenadas em disco, não estão necessariamente</p><p>armazenadas no disco. Os processos que estas filas representam é que estão em disco. O</p><p>sistema operacional gerencia a troca de processos entre a memória principal e a secundária,</p><p>conforme ilustrado na Figura 9.</p><p>Observe que, inicialmente, apenas o S.O ocupa a memória principal. O processo A</p><p>é trazido do disco para a memória e outros processos como B e C também são carregados</p><p>para a memória. No terceiro momento, o processo A entra no estado “em espera” e vai</p><p>para a fila intermediária, sendo portanto, levado da memória principal para a secundária,</p><p>liberando espaço para o processo D.</p><p>Figura 9 – Swapping em tempo de execução</p><p>A alocação da memória para cada processo na estratégia de swapping pode ser</p><p>feita de duas formas:</p><p>» Processos de tamanho fixo – não utiliza alocação dinâmica de memória usando</p><p>partições sempre do mesmo tamanho.</p><p>31</p><p>Infraestrutura de Software</p><p>» Processos de tamanho variável - podem precisar de memória “extra” e por isso</p><p>aloca-se uma memória extra, prevendo-se este crescimento (resultado de uma</p><p>alocação dinâmica).</p><p>Quando se utiliza processos de tamanho variável, o S.O precisa usar estratégias</p><p>para monitoramento do uso da memória para realizar o seu gerenciamento. Existem duas</p><p>principais maneiras de se fazer esse monitoramento: Mapa de bits e Lista encadeada.</p><p>Mapa de bits</p><p>No mapa de bits, a memória é dividida em unidades de alocação que podem ser</p><p>palavras ou kilobytes. Para cada unidade de alocação, há um bit no mapa de bits indicando</p><p>se a unidade está em uso ou livre. Esse bit é representado pelo 0, caso a unidade esteja</p><p>livre, e 1, caso a unidade esteja ocupada. O tamanho do mapa de bits depende do tamanho</p><p>da memória e da célula de memória.</p><p>A maior desvantagem dessa estratégia é que para o S.O trazer para a memória</p><p>principal, um processo que ocupa k células, ele terá que procurar por k bits consecutivos</p><p>no mapa e esse processo poderá demandar tempo e consequentemente, recurso de</p><p>processamento. Um exemplo de um mapa de bits pode ser observado na Figura 10.</p><p>Figura 10 – Mapa de Bits</p><p>Observe na Figura 10 que a área hachurada representa uma célula ocupada,</p><p>enquanto que a área branca representa uma célula livre. Caso um processo precise de 10</p><p>células de memória para ser alocado, o S.O deverá procurar no mapa de bits, uma sequência</p><p>de dez bits 0. Para tal, o S.O deverá percorrer a sequência de bits até encontrar.</p><p>Lista Encadeada</p><p>Essa lista encadeada também é uma estratégia utilizada pelo S.O para obter</p><p>informações sobre os segmentos de memória livres e ocupados. O gerenciamento é feito</p><p>mantendo-se listas encadeadas dos segmentos de memória livres a alocadas. Mas o que é</p><p>um segmento? Um segmento é um processo ou um espaço livre entre 2 processos.</p><p>A lista encadeada é ordenada por endereços e tem como vantagem, em relação ao</p><p>mapa de bits, a rápida atualização, à medida que um processo termina ou sai da memória.</p><p>Observe a Figura 11. Cada item (estrutura de dados) da lista possui 4 campos. O</p><p>primeiro representado pelas letras P e V significa a situação de um segmento. P indica que</p><p>está ocupado e V significa que está livre. O segundo campo traz a informação da célula</p><p>32</p><p>Infraestrutura de Software</p><p>inicial. Veja que, para a primeira sequência de 4 células ocupadas, o início é a célula 0 e</p><p>o término é a célula 3, o que significa que temos 4 células ocupadas. Essa informação de</p><p>quantas células estão naquela situação é representada no terceiro campo da estrutura de</p><p>dados da lista. Por fim, o quarto campo contém um apontador para o próximo item da lista</p><p>encadeada.</p><p>Figura 11 – Lista Encadeada</p><p>Para o segundo segmento representado na Figura 11, existem 3 células livres</p><p>iniciando na 4. Então o primeiro campo possui um V (indica que está livre), a posição inicial</p><p>é 4 e possui 3 células nessa situação. Uma curiosidade: Por que usa-se P e V? P representa a</p><p>palavra inglesa “present” que significa presente. E V representa “vacant” ou traduzindo para</p><p>o português, livre.</p><p>Quando um novo processo vai ser trazido para a memória, um algoritmo para</p><p>escolha da partição deve ser executado. Existem dois algoritmos para alocar memória a um</p><p>processo novo:</p><p>» Primeira alocação;</p><p>» Melhor alocação.</p><p>O algoritmo baseado na primeira alocação é extremamente rápido, pois faz uma</p><p>varredura na lista encadeada e ao encontrar a primeira lacuna maior ou igual à quantidade</p><p>de memória requerida pelo novo processo, a aloca para ele. Entretanto, esse algoritmo</p><p>tende a gerar grandes lacunas, uma vez que poderá designar um espaço bem maior que</p><p>aquele requerido pelo processo.</p><p>Por outro lado, o algoritmo da melhor alocação é mais lento, já que percorre toda</p><p>a lista encadeada, procurando a menor lacuna que comporta o novo processo. Como a</p><p>melhor lacuna é procurada, a tendência é que as lacunas sejam cada vez menores.</p><p>Apesar dos conceitos de swapping e particionamento serem bastante úteis aos</p><p>sistemas operacionais, no que se referem a gerenciamento de memória, tais técnicas não</p><p>são suficientes, pois tratam da alocação de processos inteiramente na memória principal.</p><p>Vimos que a existência de memórias maiores não leva necessariamente a um maior número</p><p>de processos, mas sim a processos maiores.</p><p>Dessa forma, os sistemas operacionais evoluíram para o uso de Memória Virtual.</p><p>O princípio fundamental da memória virtual é estender o espaço de endereçamento</p><p>da memória principal com o objetivo de acomodar, mesmo que virtualmente, todos os</p><p>33</p><p>Infraestrutura de Software</p><p>processos de usuário. A extensão se dá através da utilização do espaço em disco.</p><p>Em princípio, o uso da memória virtual resolve os problemas de gerenciamento</p><p>de memória em sistemas operacionais modernos, já que permite o compartilhamento</p><p>da memória por vários processos e permite que processos sejam apenas parcialmente</p><p>carregados na memória. Os detalhes da implementação das técnicas de memória virtual</p><p>serão abordados no capítulo 3 deste volume.</p><p>Saiba Mais</p><p>O Windows XP possui um arquivo de paginação para prover a memória virtual. O</p><p>tamanho padrão para esse arquivo é 3034 MB, porém você poderá alterá-lo na seguinte</p><p>opção : Iniciar -> Meu Computador -> com o botão direito, escolha a opção Propriedades do</p><p>sistema -> escolha a tab Avançado -> escolha o botão Configurações da seção Desempenho</p><p>-> escolha a tab Avançado e a opção para alterar o tamanho do arquivo de paginação no</p><p>disco rígido.</p><p>Aprenda Praticando</p><p>Vamos testar seus conhecimentos</p><p>teóricos através de algumas perguntas propostas</p><p>na lista de exercícios abaixo.</p><p>1) Explique o que significa Gerenciamento de Memória e qual a sua importância para</p><p>a multiprogramação.</p><p>2) Explique o esquema de particionamento. Que problemas podem acontecer</p><p>no esquema de particionamento fixo? Que problemas podem acontecer no</p><p>particionamento variável?</p><p>3) Em que se baseia o swapping de processos?</p><p>4) Com a utilização do swapping são utilizadas duas estratégias para o monitoramento</p><p>do uso da memória. Que estratégias são estas e como elas funcionam?</p><p>5) O que é fragmentação e como a mesma pode ser eliminada ou diminuída?</p><p>6) Defina o conceito de memória virtual.</p><p>7) Explique qual a diferença básica entre a fragmentação externa e a fragmentação</p><p>interna.</p><p>Atividades e Orientações de Estudo</p><p>Você deverá dedicar, pelo menos, 4 horas de estudo para o segundo Capítulo. Esse</p><p>tempo engloba a leitura, resolução dos exercícios e pesquisas propostas nos Fóruns da</p><p>disciplina e postagem de atividades somativas no ambiente virtual.</p><p>De maneira geral, as atividades somativas não envolvem todos os exercícios do</p><p>capítulo, mas é muito importante que você realize todos, inclusive aqueles que não foram</p><p>solicitados pelo professor para a postagem. A diferença é que os outros exercícios que</p><p>34</p><p>Infraestrutura de Software</p><p>não são cobrados como atividades somativas podem ser resolvidos com mais calma até o</p><p>momento da realização da avaliação.</p><p>Através dos fóruns da disciplina, você poderá trocar informações sobre o conteúdo</p><p>do ambiente virtual, com seus colegas, tutores e o professor da disciplina. O trabalho</p><p>integrado de professores, tutores e principalmente o seu, aluno, irá contribuir para um bom</p><p>aproveitamento da disciplina.</p><p>Referências</p><p>STALLINGS, William. Arquitetura e Organização de Computadores. Ed: Prentice Hall</p><p>Brasil, 2008.</p><p>TANENBAUM, Andrew. Sistemas Operacionais Modernos. LTC, Segunda Edição, São</p><p>Paulo: Prentice-Hall, 2003.</p><p>TANENBAUM, Andrew; WOODHULL, Albert. Sistemas Operacionais - Projeto e</p><p>Implementação Ed: Bookman, 2002.</p><p>Vamos Revisar?</p><p>Enquanto o primeiro capítulo abordou o gerenciamento do processador por</p><p>parte do sistema operacional, através do escalonamento de tarefas, este segundo capítulo</p><p>abordou o gerenciamento de um outro recurso gerenciável e muito importante para o</p><p>sistema operacional – a memória.</p><p>Alguns conceitos como particionamento fixo e variável, bem como técnica de</p><p>swapping foram abordadas no presente capítulo. Na abordagem de particionamento fixo,</p><p>as partições têm tamanhos diferentes, porém fixos e um processo é alocado numa partição</p><p>que lhe comporta. Vimos que essa abordagem acarreta problemas de fragmentação interna,</p><p>fazendo com que a memória fique com lacunas dentro das partições. Na abordagem do</p><p>particionamento variável, as partições são alocadas, em tempo de execução, no momento</p><p>em que os processos vão sendo trazidos para a memória. O particionamento variável inicia</p><p>bem, porém leva a situação de fragmentação externa, pois os processos carregados nas</p><p>partições, em diferentes momentos, não possuem o mesmo tamanho, gerando lacunas</p><p>entre as partições já existentes.</p><p>Vimos que existem algumas alternativas para minimizar essa fragmentação</p><p>utilizando técnicas de reorganização da memória.</p><p>Por fim, estudamos o conceito de swapping que baseia-se na reserva de uma área</p><p>em disco para ser utilizada como memória virtual, como apoio à memória principal. Vimos</p><p>ainda que os processos são trazidos do disco para a memória e vice-versa quando mudam</p><p>o seu estado e entram nas diferentes filas do sistema operacional, conforme estudamos no</p><p>capítulo 1.</p><p>Para concluir o nosso estudo sobre o gerenciamento da memória, estudaremos as</p><p>técnicas principais de memória virtual que serão apresentadas no capítulo 3 desde volume.</p><p>35</p><p>Infraestrutura de Software</p><p>Capítulo 3</p><p>O que vamos estudar neste capítulo?</p><p>Neste capítulo, vamos continuar estudando o gerenciamento de memória, porém</p><p>abordaremos as seguintes técnicas para implementar a memória virtual:</p><p>» Paginação;</p><p>» Segmentação;</p><p>» Paginação com Segmentação.</p><p>Metas</p><p>Após o estudo deste capítulo, esperamos que você consiga:</p><p>» Conhecer o princípio de funcionamento da memória virtual;</p><p>» Aprender sobre as principais técnicas de memória virtual.</p><p>36</p><p>Infraestrutura de Software</p><p>Capítulo 3 – Memória Virtual</p><p>Vamos conversar sobre o assunto?</p><p>Estudamos anteriormente que em sistemas monoprogramados a memória é</p><p>dividida em duas partes. A parte do sistema operacional e a parte do único programa em</p><p>execução.</p><p>Os sistemas multiprogramados, por sua vez, têm os seus processos compartilhando</p><p>memória com outros processos. A parte da memória disponível para uso de processos</p><p>deve ser subdividida entre diversos processos. Cabe ao sistema operacional administrar</p><p>eficientemente a memória com o objetivo de minimizar tempo de espera e maximizar a</p><p>responsividade de cada processo.</p><p>No segundo capítulo deste volume, estudamos algumas abordagens de</p><p>gerenciamento de memória tais como, particionamento fixo e variável e a técnica de</p><p>swapping. Verificamos algumas limitações nessas técnicas no sentido de resolver o problema</p><p>de administrar eficientemente a memória, tendo em vista que não permitem que processos</p><p>sejam apenas parcialmente carregados na memória.</p><p>Além disso, a técnica de swapping demanda um grande custo em termos de tempo</p><p>de execução, já que a tarefa de copiar todo o processo da memória para o disco e mais tarde</p><p>de volta para a memória é uma operação demorada.</p><p>Vimos ainda que a memória virtual é um artifício que utiliza uma parte da</p><p>memória secundária como expansão da memória principal para permitir a realização de um</p><p>gerenciamento eficiente. Mas você sabe como surgiu a memória virtual?</p><p>No passado, programadores utilizavam uma técnica chamada de overlay que</p><p>consistia em dividir o programa em partes e administrar a carga e execução das partes. A</p><p>gerência de overlays era realizada pelo programador e era um trabalho bastante custoso.</p><p>Para amenizar este problema, sistemas operacionais que administravam overlays</p><p>automaticamente foram construídos, liberando o programador desta tarefa. Estava assim</p><p>criada a memória virtual.</p><p>A memória virtual permite estender o espaço de endereçamento da memória</p><p>principal com o objetivo de acomodar, mesmo que virtualmente, todos os processos de</p><p>usuário. Como já foi citado, a extensão se dá através da utilização do espaço em disco.</p><p>O programa do usuário pode ser maior que a memória principal. Com a memória</p><p>virtual, a área de memória do programa não fica mais limitada ao tamanho da memória</p><p>física disponível.</p><p>O uso da memória virtual pretende resolver os problemas de gerenciamento de</p><p>memória em sistemas operacionais modernos, já que é necessário compartilhar a memória</p><p>entre vários processos e permitir que processos sejam apenas parcialmente carregados na</p><p>memória.</p><p>Vimos que a técnica de particionamento fixo gera muita perda de memória devido</p><p>à fragmentação. Já a de particionamento variável é mais flexível, porém ainda apresenta um</p><p>certo desperdício de memória em função da fragmentação externa. A fragmentação externa</p><p>acontece devido ao fato de cada programa necessitar uma única área contígua de memória.</p><p>Se cada programa puder ser espalhado por áreas não contíguas de memória, esse problema</p><p>37</p><p>Infraestrutura de Software</p><p>de fragmentação externa seria eliminado. É exatamente nessa proposta que se baseia a</p><p>primeira técnica de memória virtual que estudaremos: a paginação.</p><p>Paginação</p><p>Na paginação, o espaço de endereçamento virtual é dividido em um conjunto de</p><p>páginas, todas do mesmo tamanho e sempre uma potência de 2 (4, 8, 16, 32, ...). Esse</p><p>espaço de endereçamento virtual está localizado na memória secundária, ou seja, no disco</p><p>rígido.</p><p>O disco rígido é essencial para a implementação da memória virtual, pois nele são</p><p>mantidos dados e programas. O programa armazenado no disco é considerado o original</p><p>e as suas partes que são trazidas para a memória são consideradas</p>