ApostilaSO-2008

Prévia do material em texto

Sistemas Operacionais - 1/2008
Prof.: Leonardo Vianna
	
	
Sistemas Operacionais
Professor Leonardo Vianna
2008
Capítulo 1
Introdução
Um sistema operacional (SO) é um programa que age como intermediário entre o usuário do computador e o seu hardware, com o propósito de oferecer ao usuário um ambiente no qual possa executar programas de forma conveniente e eficiente. Dessa forma, o primeiro objetivo de um sistema operacional é tornar o sistema computacional conveniente para uso e fazer com que os recursos do sistema sejam utilizados de maneira eficiente.
1.1) O que é um Sistema Operacional?
O Sistema Operacional (SO) é um componente fundamental de (praticamente) todos os sistemas computacionais. Um Sistema Computacional pode ser dividido em quatro componentes fundamentais: o hardware, o SO, os programas de aplicação e, por último, os usuários (Figura 1.1).
· Hardware: fornece os recursos básicos da máquina. São eles: CPU (Central Processing Unit ( Processador), Memórias e Dispositivos de Entrada/Saída (I/O – Input/Output).
· Usuários: tentam encontrar, com o auxílio do sistema computacional, a solução para um determinado problema. Podem ser pessoas ou até mesmo outros computadores.
· Programas de Aplicação: definem como os recursos (hardware) do sistema computacional serão utilizados para a resolução de um problema requisitado pelo usuário. Exemplos: compiladores, sistemas de banco de dados, jogos e editores de texto.
· Sistema Operacional: controla e coordena o uso do hardware entre os vários programas de aplicação para os diversos usuários do sistema computacional.
Deve-se observar que o SO, por si próprio, não executa nenhuma tarefa. Ele simplesmente oferece um ambiente no qual outros programas podem realizar seus trabalhos. Ele pode ser visto como um distribuidor de recursos aos diversos programas e usuários do sistema computacional, de acordo com suas necessidades e requisições.
De uma maneira geral, não há uma definição de sistemas operacionais aceita universalmente. Uma outra definição bem comum é que o SO é o programa que está a todo momento sendo executado no sistema computacional (usualmente denominado kernel), sendo todos os demais programas considerados de aplicação.
De certa forma, é mais fácil definir sistemas operacionais pelo que eles fazem do que pelo que eles são: oferecer conveniência e eficiência ao usuário.
1.2) Os primeiros sistemas
Os primeiros computadores eram máquinas enormes (fisicamente) operadas a partir de uma console. O programador, que também era o operador da máquina, escrevia seu programa e o operava diretamente através da console. Primeiro, o programa devia ser carregado manualmente para memória. Durante a execução do programa, o programador podia monitorá-la. Se algum erro ocorresse, o programador podia cancelar a execução, analisar os conteúdos de memória e registradores.
Os dispositivos de entrada comuns eram leitoras de cartões e unidades de fita, enquanto os dispositivos de saída mais encontrados consistiam em impressoras de linha, unidades de fita e perfuradoras de cartões.
Por exemplo, para executar um programa em Pascal, o programador precisava primeiro carregar o compilador Pascal, normalmente armazenado em uma fita magnética. Feito isso, precisava-se ler o programa a ser executado, para que este fosse traduzido para linguagem de máquina. O primeiro passo da tradução consistia no compilador Pascal ler o programa instrução por instrução (através de cartões perfurados) e gerar uma imagem do programa em assembly. Após isso, era necessário carregar o assembler (também em fita magnética) que traduziria o programa em assembly para, finalmente, o programa em linguagem de máquina. Torna-se óbvio o quanto era caro tal processo! Em outras palavras, o setup time era um grande problema.
Deve-se observar que o setup time tão elevado trazia grandes problemas na utilização do sistema. Por exemplo, enquanto fitas eram colocadas na leitora ou enquanto o programador operava a console, a CPU permanecia ociosa. Uma vez que na época, poucos eram os computadores disponíveis, ter a CPU “parada” era realmente um grande problema (econômico). Quando um computador era desenvolvido, milhões de dólares eram investidos, logo, sempre se esperava uma utilização máxima de seus recursos.
Uma primeira solução foi a contratação de um operador que, por ter mais experiência, poderia manipular os recursos de forma mais ágil, diminuindo o setup time. Dessa forma, o usuário (o programador) não interagia diretamente com o sistema computacional. Ao invés, ele preparava um programa e o entregava ao operador, sob a forma de cartões perfurados. Algum tempo depois era gerada a saída que consistia no resultado do programa (e um dump de memória e registradores no caso de erros), todas essas informações recolhidas pelo operador e entregues mais tarde ao programador que analisaria a execução do programa. Uma vez finalizada a execução de um programa, o operador poderia seguir imediatamente para a execução do próximo programa, sempre visando a otimização no uso dos recursos da máquina.
A segunda solução encontrada (melhorando ainda mais a primeira) para acelerar o processamento consistiu em os operadores reunirem os programas em lotes com necessidades semelhantes e os executarem como um grupo. Assim, os programadores deixavam seus programas com o operador que os classificava em lotes e, à medida que o computador ficava disponível, executava cada lote ou batch. Daí a denominação de sistemas batches.
Com certeza, tais melhorias reduziram bastante o setup time. Porém, ainda existiam problemas. Por exemplo, quando a execução de um programa parava, o operador teria que analisar a console, determinar o porquê do término da execução (normal ou anormal – erros?), fazer um dump de memória se necessário, e iniciar a execução do próximo programa. Durante essa transição, a CPU permanecia ociosa.
A solução foi obtida através da implementação do seqüenciamento automático de processos (( programa em execução), gerando, assim, o primeiro sistema operacional. Na verdade, o que era feito antes pelo operador passou a ser realizado pela própria máquina, através de um fragmento de software sempre em memória denominado Monitor Residente (Figura 1.2).
Quando o computador era ligado, o Monitor Residente era chamado, e este transferia o controle da máquina para o primeiro programa a ser executado. Ao terminar a execução do programa que detinha a CPU, o controle era retornado ao Monitor Residente, que alocava a CPU ao próximo programa e assim sucessivamente até atender a todos os programas.
Neste ambiente de execução, a CPU muitas vezes ainda fica ociosa porque as velocidades dos dispositivos mecânicos de E/S são inferiores às dos dispositivos eletrônicos. 
O advento da tecnologia de discos permitiu que o sistema operacional mantivesse todos os processos em um disco, em vez de em uma leitora de cartões. Com acesso direto a vários processos, o escalonamento de processos poderia ser executado para utilizar recursos e realizar tarefas de forma eficiente. O aspecto mais importante do escalonamento de processos é a capacidade de multiprogramação. Um único processo não pode, em geral, manter a CPU e/ou os dispositivos de E/S ocupados em todos os momentos. A multiprogramação aumenta a utilização da CPU organizando processos de forma que a CPU sempre tenha um processo para executar (ou quase sempre).
A idéia da multiprogramação é a seguinte: em determinado instante, o sistema operacional mantém vários processos carregados em memória, esperando para serem executados (Figura 1.3). O SO então escolhe um dos processos para executar segundo algum critério. Quando a execução deste processo terminar ou for interrompida, o SO escolhe dentre os processos que estão em memória o próximo a ser executado. Este procedimento é repetido até que todos os processos do sistema sejam executados.
A multiprogramação é o primeiro exemplo onde o SO toma decisões para o usuário. Os SOs multiprogramáveis são, portanto, bastante sofisticados.Todos os processos que entram no sistema são mantidos no pool de processos (ou fila de entrada). Esse pool consiste em todos os processos residentes no disco aguardando alocação na memória principal. Se vários processos estiverem prontos para serem carregados na memória e não houver espaço suficiente para todos o SO deverá fazer a escolha de quem será carregado. Essa tomada de decisão é chamada de escalonamento de processos. Escolhido o processo, o SO o carrega na memória para que possa ser executado. Porém, uma vez que vários processos podem estar em memória a espera da utilização da CPU, o SO deve tomar outra decisão: escolher qual processo em memória irá receber a posse da CPU, ou seja, será executado. Esta decisão é conhecida como escalonamento de CPU.
Os sistemas batches multiprogramáveis forneciam um ambiente no qual os vários recursos do sistema eram utilizados de maneira eficiente, porém não permitiam a interação dos usuários com o sistema computacional. 
A técnica time-sharing (ou multitasking (multitarefa) ou tempo compartilhado) é uma extensão da multiprogramação onde vários programas são executados "simultaneamente", havendo interação entre o usuário e o processo. Isso acontece porque a CPU executa vários processos alternadamente, mas como essas trocas ocorrem com alta freqüência, é possível que os usuários interajam com seus programas durante sua execução. Um sistema computacional interativo permite a comunicação direta entre o usuário e o sistema, contrapondo-se aos sistemas batches. O usuário passa instruções ao SO ou a um programa diretamente e espera por resultados imediatos. Um sistema time-sharing permite que vários usuários compartilhem os recursos da máquina simultaneamente. Uma vez que cada comando nesse sistema tende a levar pouco tempo, apenas um pequeno tempo de CPU é necessário para cada processo. Dessa forma, como o chaveamento é feito rapidamente, é dada a cada usuário a impressão de que ele tem sua própria máquina.
A evolução dos sistemas continua até os dias atuais e vários sistemas, com características próprias, têm sido definidos, como, por exemplo, sistemas paralelos, sistemas distribuídos e sistemas de tempo real.
Capítulo 2
Estruturas do Sistema Computacional
Antes de iniciar o estudo das principais características dos sistemas operacionais, faz-se necessária uma visão geral da estrutura do sistema computacional. Isso porque o SO tem como uma de suas principais funções assegurar o funcionamento correto do sistema computacional e fazer com que programas de usuário não interfiram na execução de outros programas e até mesmo do SO.
2.1) Operação do Sistema Computacional
De uma forma geral, um sistema computacional consiste de uma CPU e um determinado número de controladores de dispositivos conectados via barramento comum que serve para acessar uma memória compartilhada (Figura 2.1). Cada controlador de dispositivo é responsável pelo funcionamento de um tipo específico de dispositivo (por exemplo, discos, monitores, teclados, etc.). Tanto a CPU quanto os controladores (que são pequenos “processadores” – PPU - peripheral processing units) podem executar concorrentemente, competindo por ciclos de memória. Dessa forma, para garantir uma ordenação nos acessos à memória compartilhada, há também um controlador de memória com a função de sincronizar o acesso a este dispositivo.
Para um computador iniciar sua execução, ele precisa executar um programa especial. Esse programa inicial, chamado de bootstrap, tende a ser simples. Ele inicializa todos os aspectos do sistemas, desde registradores até controladores e conteúdos de memória. Além disso, o bootstrap deve saber carregar o SO e iniciar sua execução. Para alcançar essa meta, o programa deve localizar e carregar na memória principal o kernel do SO. O SO em seguida inicia a execução do primeiro processo e espera a ocorrência de algum evento, que usualmente é sinalizada através de uma interrupção de hardware ou software. O hardware pode disparar uma interrupção a qualquer momento enviando um sinal à CPU, através do barramento do sistema. O software, por sua vez, pode disparar uma interrupção através da execução de uma operação especial conhecida por chamada de sistema (system call).
Existem vários tipos de eventos que podem disparar uma interrupção, como, por exemplo, o término de uma operação de E/S, uma divisão por zero, violação de memória, ou ainda a requisição de algum serviço do SO. Para cada tipo de interrupção, existe uma rotina responsável para o tratamento da interrupção.
Quando a CPU é interrompida, ela pára o que está fazendo e transfere sua execução para um local fixo da memória. Este local usualmente contém o endereço inicial no qual se encontra a rotina de tratamento da interrupção. Tal rotina executa e, ao terminar, a CPU volta a executar o que estava antes da interrupção. 
Interrupções consistem em uma importante parte da arquitetura de computadores. Cada projeto de computador possui seu próprio mecanismo de interrupções, mas várias funções são comuns. A interrupção deve transferir o controle da CPU para sua rotina de tratamento. Uma vez que há um número pré-definido de rotinas de tratamento, estas são armazenadas em um local específico de memória, de modo a facilitar o acesso e agilizar a execução da rotina. Este local consiste em regiões contíguas de memórias, de modo a formar um vetor, o vetor de interrupções. A arquitetura de interrupções também deve salvar o endereço da instrução interrompida.
Os SOs modernos são baseados em interrupções. Se não houver processos para executar, nenhum dispositivo de E/S ao qual fornecer e nenhum usuário a ser atendido, o SO permanecerá parado, a espera da ocorrência de algum evento. Os eventos são quase sempre sinalizados por uma interrupção ou um trap. Trap, ou exceção, é uma interrupção gerada por software causada por um erro (por exemplo, a divisão por zero ou acesso inválido à memória), ou por um pedido específico de um programa de usuário para que um serviço do SO seja executado.
Usualmente, interrupções são desabilitadas enquanto uma interrupção estiver sendo executada, postergando a ocorrência de quaisquer possíveis interrupções até o momento em que a atual tenha sido tratada pelo SO. 
2.2) Estruturas de Armazenamento
Para que um computador consiga realizar a sua única função, a de processar, faz-se necessário que os programas a serem executados estejam na memória principal. A memória principal é o único dispositivo de armazenamento que a CPU pode acessar diretamente e consiste em um vetor de palavras, cada qual com seu próprio endereço. A comunicação entre a CPU e a memória principal se dá através de uma série de leituras e escritas em determinados endereços.
Tipicamente, o ciclo de execução de uma instrução possui os seguintes passos, respeitando a arquitetura Von Neumann:
· Busca em memória da instrução a ser executada seguida de seu armazenamento no registrador de instrução (IR). Para isto, deve-se utilizar um outro registrador, o contador de instruções (PC), que guarda o endereço da próxima instrução a ser executada e é atualizado a cada busca.
· Decodificação da instrução, determinando a operação a ser realizada e os operandos a serem manipulados. Se necessário, devem ser buscados em memória os operandos especificados na instrução.
· Definida a operação e em posse dos operandos, a instrução pode ser finalmente executada.
· Caso algum resultado seja gerado, este deve ser retornado à memória.
O ideal seria que os programas e os dados residissem permanentemente em memória. Porém, isso não é possível por duas razões:
1) De uma forma geral, a memória principal é muito pequena para armazenar permanentemente todos os programas e dados necessários;
2) A memória principal é volátil, o que significa que perde todo o seu conteúdo quando perde a alimentação de energia.
Portanto, os computadores possuem o que chamamos de memória secundária como uma extensão da memória principal. Logo, a principal exigência é que este tipo de memória, secundária,seja capaz de armazenar uma grande massa de dados permanentemente.
Além desses tipos de memória, há outras duas formas de armazenamento no sistema computacional:
· Registradores – memória de tamanho reduzido, porém de altíssima velocidade, localizada dentro da CPU;
· Cache – utilizada para aumentar o desempenho na interação CPU-memória.
Observação: por questão de nomenclatura, começaremos a chamar a memória principal de simplesmente memória. Os demais tipos de memória serão, por sua vez, definidos como memória secundária, cache e registradores.
2.3) Hierarquia de Armazenamento
Os vários dispositivos de armazenamento existentes em um sistema computacional podem ser organizados de forma hierárquica (Figura 2.2) de acordo com suas velocidades e seus custos. Os níveis mais altos são caros, porém rápidos. À medida que descemos a pirâmide, o custo por bit diminui, porém sua velocidade de acesso aumenta. 
Além dos parâmetros velocidade e custo, também deve ser considerada a volatilidade. O armazenamento volátil perde o seu conteúdo quando é interrompida a energia para o dispositivo. Na hierarquia da Figura 2.2, todos os dispositivos acima dos discos consistem em memórias voláteis.
O projeto de um sistema de memória completo deve balancear todos esses fatores: ele só vai usar memória cara quando necessário, fornecendo ao mesmo tempo a maior quantidade possível de memória não-volátil barata.
Caches podem ser instaladas quando, entre dois componentes, for detectada disparidade em relação a tempo de acesso e taxa de transferência.
( Caching
Caching é um importante princípio de sistemas de computadores, tanto em hardware quanto em software. A informação manipulada no sistema é normalmente mantida em algum meio de armazenamento, como a memória principal. À medida que a informação é referenciada, ela é copiada para um dispositivo mais rápido, a cache. Dessa forma, quando determinada informação é requisitada, checa-se primeiro se ela se encontra na cache. Caso se encontre, a informação armazenada na cache é utilizada; caso contrário, a memória principal é acessada em busca da informação, mas uma cópia sua é armazenada na cache, considerando a possibilidade de ser acessada novamente no futuro. Esse mecanismo tende a diminuir bastante os tempos de acesso, em especial entre a CPU e a memória principal.
( Operação em Modo Dual
Para garantir a correta operação do sistema computacional, é necessário proteger o SO e todos os outros programas e seus dados de qualquer programa que possa estar executando de forma não-apropriada. E essa proteção deve ser estendida a qualquer recurso do sistema que possa ser compartilhado por mais de um processo.
A estratégia utilizada para esta proteção é feita via hardware (dentro da CPU), através da utilização de apenas um bit, que fará a distinção entre a execução do SO e a execução de programas de usuários. Esse bit é o mode bit que, dependendo do valor armazenado, definirá dois modos de execução: modo supervisor, indicando que o SO está executando, e modo usuário, caso um programa do usuário esteja sendo executado.
Ao executar o booting, o hardware inicia em modo supervisor. O SO é então carregado e começa então a execução de programas do usuário, já em modo usuário. Sempre que uma interrupção ocorrer, o hardware troca o mode bit para modo supervisor para que, dessa forma, o SO possa tomar as devidas providências para o tratamento do evento.
Ainda visando a proteção dos programas sendo executados, algumas instruções de máquina são classificadas como instruções privilegiadas, pois suas execuções podem causar danos aos programas caso não sejam manipuladas de forma cuidadosa. Com esta classificação, tais instruções só podem ser executados em modo supervisor, ou seja, só podem ser executadas pelo SO. Se um programa do usuário (modo usuário) tentar executar uma dessas instruções, ela não é executada e é considerada um acesso ilegal e ocorre um trap. 
Capítulo 3
Processos
Os primeiros sistemas computacionais permitiam a execução de apenas um programa em cada instante. Este programa tinha total controle do sistema e tinha acesso a todos os recursos da máquina. Atualmente, os sistemas computacionais permitem que diversos programas sejam carregados em memória e executados concorrentemente. Essa evolução exigiu maior controle e maior compartilhamento entre os diversos programas. Essas necessidades resultaram na noção de um processo que consiste simplesmente em um programa em execução. 
Embora o objetivo principal de qualquer sistema computacional seja servir às necessidades do usuário, através da execução de seus programas, ele também precisa cuidar das várias tarefas de sistema que devem ser executadas para garantir o bom funcionamento do sistema computacional. Isso significa dizer que, a todo momento, existem processos do usuário e processos do sistema necessitando serem executados, ou seja, utilizar CPU. “Chaveando” a CPU entre os processos de maneira bem cuidadosa, o SO pode tornar a máquina mais produtiva, mais eficiente.
3.1) O Conceito de Processo
Um obstáculo à discussão de SOs é que existe dificuldade em denominar todas as atividades da CPU. Um sistema batch executa jobs, enquanto um sistema time-sharing executa programas de usuário ou tarefas. Mesmo em um sistema monousuário, um usuário pode executar vários programas de uma vez. Mesmo se o usuário só puder executar um programa de cada vez, o SO poderá precisar dar suporte a suas próprias atividades, como gerência de memória. Em muitos aspectos, todas essas atividades são semelhantes e, por isso, chamamos todas de processos.
3.1.1) O Processo
Informalmente, um processo é um programa em execução. Sua execução deve ser seqüencial, respeitando a ordem das instruções definidas pelo programa. Isto é, em dado instante, no máximo uma de suas instruções estará sendo executada.
Um processo compreende mais do que o código de programa e sua atividade instantânea. Inclui também uma pilha do processo contendo dados temporários (parâmetros para sub-rotinas, endereços de retorno, variáveis temporárias, etc.) e uma sessão de dados (variáveis globais).
Devemos enfatizar que um programa por si próprio não consiste em um processo; um programa é uma entidade estática, armazenada em um arquivo em disco e um processo é uma entidade dinâmica, com, por exemplo, o PC apontando para a próxima instrução a ser executada e um conjunto de recursos associados.
3.1.2) Estados do Processo
À medida que o processo executa, ele muda de estado e este é definido, em parte, pela sua atividade corrente. Um processo, em determinado instante, pode estar em um dos cinco estados a seguir e a Figura 3.1 apresenta o diagrama de transição destes estados:
· Novo: o processo acabou de ser criado;
· Em execução: suas instruções estão sendo executadas. Obs.: apenas um processo pode estar nesse estado a cada instante.
· Em espera ou Suspenso: o processo está esperando que um evento ocorra, normalmente o término de uma E/S.
· Pronto: o processo está pronto para utilizar a CPU.
· Terminado: o processo terminara sua execução.
3.1.3) Bloco de Controle do Processo (PCB)
Cada processo é representado no SO pelo seu bloco de controle (Process Control Block – PCB), que fica armazenado na memória do SO. Ele possui diversas informações associadas ao processo, incluindo:
· O estado do processo.
· O PC indicando a próxima instrução do processo a ser executada.
· Os valores de alguns registradores da CPU: acumuladores, registradores de uso geral, stack pointer, bits de estado (essas informações são salvas quando um evento ocorre para que seja possível continuar a execução do processo posteriormente, de forma correta – Figura 3.2). 
· Informações para escalonamento de CPU: prioridade, filas de escalonamento, etc..
· Informações para gerência de memória: registradores base, limite, ou tabelas de página ou de segmentos.
· Informações para tarifação: tempo de CPU, limites de tempo, número da conta, número do processo, etc..
· Informações de estado de E/S: pedidosde E/S, dispositivos alocados ao processo, lista de arquivos abertos, etc..
3.2) Escalonamento de Processos
O objetivo principal da multiprogramação está na tentativa de ter sempre um processo em execução no sistema, maximizando dessa forma a utilização de CPU. O objetivo dos sistemas time-sharing é chavear a CPU entre os processos tão freqüentemente de modo a permitir que os usuários interajam com todos os seus programas durante suas respectivas execuções, dando a impressão de que todos estão sendo executados ao mesmo tempo. Mas a verdade é: se há apenas uma CPU no sistema computacional, nunca haverá mais de um processo executando em determinado instante. Se há mais processos necessitando do processador, estes terão que esperar até que a CPU se torne novamente livre e seja reescalonada pelo SO a outro processo.
3.2.1) Filas de Escalonamento
Os processos que chegam ao sistema para iniciar a sua execução são colocados na fila de processos (ou fila de entrada). Essa fila é composta por todos os processos em disco que esperam por carga na memória principal. Os processos residentes em memória que estão prontos, porém esperando pela utilização da CPU, se encontram na fila de prontos, formada pelos PCBs de tais processos. Além dessas filas, existem outras gerenciadas pelo SO, como, por exemplo, uma fila para cada dispositivo de E/S, onde são mantidos os PCBs dos processos que precisam utilizar o dispositivo em questão.
Um processo recém carregado na memória é colocado inicialmente na fila de prontos e fica aguardando até que o SO o selecione para usar a CPU. Durante o uso da CPU, um dos seguintes eventos pode ocorrer:
· O processo faz um pedido de E/S e é colocado na fila do dispositivo (entra no estado de espera);
· O processo cria um subprocesso e espera pelo término da execução deste (entra no estado de espera);
· A CPU é retirada do processo por causa de uma interrupção e ele é colocado de volta na fila dos prontos (Figura 3.3).
3.2.2) Escalonadores
Ao longo de sua execução, um processo migra pelas diversas filas do sistema. O SO deve selecionar processos destas filas segundo alguma filosofia. Tal seleção é realizada pelo escalonador apropriado.
Em um sistema batch, há normalmente mais processos submetidos do que processos executados imediatamente. Tais processos são colocados em um spooling de entrada (no disco) onde aguardam por carga em memória. Quem seleciona um desses processos, no instante que houver memória livre, é o LTS (long-term scheduler, escalonador de longo prazo ou, simplesmente, escalonador de processos).
O STS (short-time scheduler, escalonar de curto prazo ou escalonado de CPU) seleciona um dos processos da fila dos prontos para usar a CPU (note que nem todos os processos que estão na memória estão prontos). 
A diferença principal entre esses dois escalonadores está na freqüência que executam. O escalonador de CPU deve selecionar um novo processo freqüentemente. Portanto, o escalonador de CPU deve ser muito rápido. 
O escalonador de processos, por outro lado, executa menos freqüentemente, pois pode haver intervalos de minutos entre a chegada e partida de processos no sistema. O escalonador de processos controla o grau de multiprogramação, isto é, o número de processos em memória, e só precisa ser executado quando algum processo deixa o sistema. Por isso, este escalonador pode consumir mais tempo de CPU do que o escalonador de CPU.
É importante que o escalonador de processos proceda uma seleção bem cuidadosa. Em geral, os processos são possíveis de classificar como CPU Bound ou I/O Bound. Um processo I/O Bound gasta mais tempo realizando E/S do que efetivamente utilizando a CPU. Por sua vez, um processo CPU Bound raramente faz requisições de E/S, se dedicando mais à utilização da CPU. Dessa forma, é importante que o escalonador de processos consiga uma mistura de processos dos dois tipos, para garantir uma melhor utilização dos recursos do sistema. Se todos os processos são I/O Bound, a fila dos prontos estará quase sempre vazia e o escalonador de CPU terá pouco a fazer. Por outro lado, se todos os processos são CPU Bound, as filas de dispositivos estarão quase sempre vazias. Em ambos os casos, o sistema estará desbalanceado.
Alguns sistemas operacionais, especialmente os que possuem memória virtual, têm um escalonador adicional, o escalonador de médio prazo (medium-term scheduler – MTS). A idéia da utilização do MTS (Figura 3.4) é que algumas vezes pode ser vantajoso remover alguns processos da memória, reduzindo o grau de multiprogramação. Em algum instante posterior, cada processo é carregado de volta na memória e sua execução é retomada do ponto que parou. Essa técnica é chamada de swapping. O MTS é responsável por fazer swap in e swap out dos processos. O swapping pode se mostrar necessário para realizar a desejada mistura de processos ou ainda para atender uma requisição extra de memória por parte de algum processo, sendo necessário, dessa forma, liberar memória.
3.2.3) Troca de Contexto
Chavear a CPU de um processo para outro exige salvar o contexto do processo que tinha o controle da CPU e carregar o contexto do processo que agora ganhou o direito de usá-la. Essa ação tem o nome de troca de contexto e é feita pelo SO. O tempo da troca de contexto é puro overhead, uma vez que nenhum sistema realiza alguma função útil quando realiza esta operação e varia de uma arquitetura para outra, devendo ser minimizado.
Capítulo 4
Escalonamento
de CPU
Escalonamento de CPU é a base de sistemas operacionais multiprogramáveis. Através do chaveamento da CPU entre os processos que estão em memória prontos para executar, o SO pode tornar o sistema computacional mais produtivo.
4.1) Conceitos Básicos
O objetivo da multiprogramação é ter sempre algum processo executando no sistema computacional, maximizando assim a utilização da CPU.
O escalonamento de CPU é uma função fundamental de qualquer SO. Praticamente todos os recursos do sistema devem ser escalonados antes de serem usados. E a CPU, por ser um dos principais recursos do sistema, seu escalonamento é de suma importância.
4.1.1) CPU e I/O Burst Cycle
O escalonamento de CPU depende da seguinte propriedade sobre processos: a execução de um processo é uma sucessão de execuções em CPU e espera por E/S. A execução começa com um período CPU burst (utilização de CPU), que é seguido por um período I/O burst (espera por uma E/S). Esses períodos se repetem, até que o último período CPU burst termina com a chamada de sistema terminate.
A duração de cada período CPU burst varia de processo para processo e de computador para computador. Existe um grande número de períodos CPU burst curtos e um pequeno número de períodos CPU burst longos. Um programa I/O bound tem todos os períodos CPU burst curtos. Um programa CPU bound tem alguns períodos CPU burst longos. A escolha do algoritmo de escalonamento de CPU apropriado considera essa característica. 
4.1.2) Escalonador de CPU
Sempre que a CPU fica livre, o SO seleciona um processo, entre os que estão na fila de prontos, para executar. Essa seleção é feita pelo STS (escalonador de CPU). 
Deve-se observar que a fila de prontos não é necessariamente uma fila FIFO (First-in First-out). Podem existir outros critérios (como, por exemplo, o de prioridades) de ordenação dos processos. O que deve se ter em mente é que o que fica armazenado nas filas são os PCBs dos processos, e não os próprios processos.
4.1.3) Preempção
O escalonamento de CPU pode se dar em 4 situações distintas:
i. Um processo faz uma chamada de sistema e tem que esperar (o SO tem que selecionar outro processo).
ii. Ocorre uma interrupção (o processo vai para a fila de prontos e o SO trata a interrupção).
iii. O processo é colocado na fila de prontos pelo SO, depois de tratar uma interrupção (o processo terminou uma E/S).
iv. O processo faz a chamada de sistema terminate (o SO tem que selecionar outro processo).
Quando o escalonador executa somente nos casos i e iv, então é dito que o escalonamento énão preemptivo (preempção ( interrupção). Nesse caso, o processo só perde a CPU se fizer uma chamada de sistema (o SO trata interrupções e devolve a CPU a o processo que a detinha antes da interrupção).
Quando o escalonador executa nos quatro casos, então é dito que o escalonamento é preemptivo.
4.1.4) Dispatcher (Módulo Despachante)
Outro componente envolvido no escalonamento de CPU é o dispatcher. Este é o módulo do SO que realmente dá a CPU ao processo escolhido pelo escalonador de CPU. Ele deve executar muito rapidamente as seguintes operações:
· Trocar o contexto;
· Mudar o mode bit para modo usuário; e
· Desviar para o endereço do programa do usuário (o valor do PC contido no respectivo PCB).
4.2) Critérios de Escalonamento
Diferentes algoritmos de escalonamento de CPU possuem diferentes propriedades. Para escolher um deles para ser empregado em um SO específico, é preciso poder compará-los.
Diferentes critérios podem ser usados para comparar tais algoritmos. Dependendo do critério usado, a determinação do melhor algoritmo pode variar. Os critérios utilizados incluem:
· Utilização de CPU: se a CPU é cara, então desejamos mantê-la ocupada o maior tempo possível. Em um sistema real, essa taxa pode variar de 40 % a 90 %;
· Throughput (vazão): se a CPU está ocupada, isto significa que há processo sendo executado. O throughput é o número médio de processos que são executados (terminados) por unidade de tempo;
· Turnaround time: é o intervalo de tempo desde a submissão do processo até seu término (tempo de espera por carga na memória + espera na fila de prontos + espera por E/S + tempo de CPU);
· Tempo de espera: é o tempo que o processo fica na fila de prontos;
· Tempo de resposta (em sistemas interativos): é o tempo que o sistema leva para dar a resposta a uma requisição do usuário.
Uma vez escolhido o critério para comparação, geralmente deseja-se otimizá-lo. Então é desejável maximizar, por exemplo, a utilização da CPU e o throughput, e minimizar o turnaround time, o tempo de espera e o tempo de resposta. Em alguns casos, são as médias que são otimizadas, em outros os valores mínimos e os máximos (caso queiramos garantir que todos os usuários tenham sempre um bom serviço). Em sistemas interativos, porém, é melhor minimizar a variação do tempo de resposta.
4.3) Algoritmos de Escalonamento
Escalonamento de CPU lida com o problema de decidir qual processo que se encontra na fila de prontos ganhará a posse da CPU. Para isto, há uma variedade de algoritmos de escalonamento, que se diferem no critério adotado em tal seleção. 
4.3.1) Algoritmo FCFS (First-Come, First-Served)
É o algoritmo de escalonamento mais simples: a CPU é dada ao processo que chegou mais cedo na fila de prontos, classificando-se como não-preemptivo.
A implementação do FCFS é feita gerenciando-se uma fila FIFO. Quando o processo chega na fila de prontos, seu PCB é colocado no final da fila. A CPU, ficando livre, é então alocada ao primeiro processo da fila dos prontos, que é retirado da fila. Essa estratégia é de fácil implementação e entendimento. Porém, o desempenho do FCFS é muito baixo. Por exemplo, consideremos 3 (três) processos cujos próximos CPU burst são conhecidos (em unidades de tempo – u.t.): P1 = 24, P2 = 3 e P3 = 3. Todos chegam na fila dos prontos no instante 0. Se a ordem de chegada é P1, P2 e P3, então temos a seguinte situação:
O tempo de espera médio – TEM – é: (0+24+27)/3 = 17 u.t.. Mas se a ordem de chegada dos processos na fila de prontos fosse P2, P3 e P1, teríamos:
O TEM passa a ser: (6+0+3)/3 = 3 u.t.. Esta redução é substancial. Podemos dizer então que o tempo de espera médio, nesse tipo de escalonamento, geralmente não é mínimo e varia substancialmente se os tempos CPU burst variarem muito.
Além disso, consideremos também o FCFS na situação dinâmica na qual temos um processo CPU bound e vários processos I/O bound. Em um dado momento, o processo CPU bound ganha controle da CPU, e a retém. Durante esse tempo, todos os outros processos terminam de fazer E/S e estão na fila de prontos. Enquanto esperam, todas as filas de E/S estão vazias e os dispositivos ociosos, caracterizando desbalanceamento do sistema. O processo CPU bound termina seu ciclo CPU burst e faz E/S. Todos os demais processos, que são I/O bound e, portanto, possuem períodos CPU burst muito curtos, executam e voltam para as filas de E/S, deixando a CPU ociosa. O ciclo pode se repetir causando o que chamamos de efeito comboio (convoy effect). Em outras palavras, é como se todos os processos esperassem que um grande processo “largasse” a CPU. Esse efeito provoca a má utilização da CPU e dos dispositivos. Utilização essa que seria melhorada se os processos de ciclos CPU burst menores ganhassem a CPU primeiro.
4.3.2) Algoritmo SJF (Shortest Job First)
O SJF pode ser preemptivo ou não-preemptivo. Ele associa a cada processo a duração do próximo CPU burst. Quando a CPU fica disponível, ela é dada ao processo de menor próximo CPU burst. Se dois processos têm CPU burst de mesma duração, então o FCFS é usado. Note que o termo mais apropriado seria shortest next CPU burst, uma vez que o escalonamento é realizado considerando o tempo do próximo CPU burst e não sobre a duração total do processo.
Vejamos o exemplo. Consideremos 4 (quatro) processos cujos próximos CPU burst são conhecidos (em unidades de tempo – u.t.): P1 = 6, P2 = 8, P3 = 7 e P4 = 3. Podemos calcular o tempo de espera médio se a ordem de chegada é P1, P2, P3 e P4.
O TEM é: (3+16+9+0)/4 = 7 u.t.. Se estivéssemos utilizando o FCFS, este tempo aumentaria para 10,25 u.t..
O SJF é ótimo por fornecer um tempo de espera mínimo para um conjunto de processos. Porém, a dificuldade é conhecer a duração do próximo período CPU burst dos processos.
Embora o SJF seja ótimo, o escalonador de CPU associado não é implementável: não há como conhecer a duração do próximo CPU burst. O que se tenta fazer é uma previsão desse valor, isto é, podemos imaginar que o próximo período será semelhante ao anterior. É escolhido então o processo com menor próximo CPU burst estimado.
No SJF preemptivo, ou shortest remaining time first – SRTF, sempre que um processo chega à fila dos prontos, a execução do processo é parada, já que o novo processo pode ter próximo CPU burst menor que o “resto” daquele que está em execução. Nesse caso, somente o “resto” do processo entra na fila, e o SO pode escolher um novo processo para executar, ou continuar executando o anterior.
Consideremos um exemplo com 4 (quatro) processos para ilustrar o SJF preemptivo: P1 = 8, P2 = 4, P3 = 9 e P4 = 5. Podemos calcular o tempo de espera supondo que P1 chega a fila dos prontos no instante 0, P2 no 1, P3 no 2 e P4 no instante 3.
O tempo de espera médio é: ((10-1) + (1-1) + (17-2) + (5-3))/4 = 6,5 u.t.. Se o SJF não preemptivo é usado, esse valor aumenta para 7,75 u.t..
4.3.3) Algoritmo de Prioridades
SJF é um caso particular do algoritmo de escalonamento de prioridades (a prioridade é o inverso do próximo CPU burst). Uma prioridade é associada a cada processo, e a CPU é dada ao processo de maior prioridade. Processos com mesma prioridade são tratados na ordem FCFS. Pode ser preemptivo e não preemptivo.
Prioridades vão, por exemplo, de 0 a 7 ou de 0 a 4095; isto é, compreendem uma faixa de números adequada (em geral, a prioridade 0 é a mais alta).
Consideremos 5 (cinco) processos aonde todos chegam na fila dos prontos no instante 0, na ordem P1, P2, P3, P4 e P5. Esses processos têm respectivamente CPU burst de 10, 1, 2, 1 e 5. Suas prioridades são, respectivamente, 3, 1, 3, 4 e 2. Usando o escalonamento de prioridades, o tempo de espera médio é de 8,2 u.t..
As prioridades podem ser definidas interna ou externamente. Se definidas internamente, podem ser baseadas, por exemplo, no tempo limite, necessidade de memória, número de arquivos abertos, ou na taxa média entre período I/O burst e CPU burst. As prioridades definidas externamente são definidas através de critérios externos ao SO, tais como o valor da contado usuário.
O maior problema desse algoritmo é o que denominamos blocking ou starvation, que pode fazer com que um processo de baixa prioridade espere indefinidamente por CPU na fila dos prontos. Em outras palavras, se o escalonamento de CPU for por prioridade, em sistemas muito ocupados, o alto fluxo de processos de alta prioridade na fila de processos pode impedir que processo de prioridade mais baixa ganhe controle da CPU. Nesse caso, duas coisas podem ocorrer: o processo de baixa prioridade executa às 02:00 h da manhã, quando a carga fica reduzida, ou o sistema cai, e todos os processos de baixa prioridade são perdidos.
A solução para starvation dos processos de baixa prioridade é uma técnica chamada aging, na qual a prioridade aumenta gradualmente à medida que o processo permanece no sistema sem conseguir usar a CPU.
4.3.4) Algoritmo Round-Robin - RR
É um algoritmo preemptivo, projetado especialmente para sistemas time-sharing. É similar ao FCFS, mas existe preempção. Uma pequena unidade de tempo (quantum ou time-slice) é definida (normalmente, de 10 a 100 ms). A fila dos prontos é tratada como uma fila circular, e a CPU é alocada para cada processo por um período que pode durar até um quantum.
A fila dos prontos é organizada de modo FIFO. Novos processos e processos que perdem controle da CPU entram no final da fila. O escalonador escolhe o primeiro processo da fila dos prontos. Antes de dar o controle da CPU ao processo selecionado, o SO carrega o timer com o valor do quantum.
Quando um processo ganha o direito de usar a CPU, duas coisas podem ocorrer:
· O CPU burst do processo é menor do que um quantum, e o processo libera a CPU voluntariamente;
· O CPU burst do processo é maior do que um quantum, e o timer provoca uma interrupção e o SO coloca o PCB do processo no final da fila dos prontos, e o escalonador de CPU escalona o primeiro processo da fila para receber a CPU.
Freqüentemente, o tempo de espera médio fornecido por este algoritmo é longo. Consideremos 3 (três) processos cujos próximos CPU burst são: P1 = 24, P2 = 3 e P3 = 3. Se a ordem de chegada é P1, P2 e P3, e o quantum de 4 u.t., temos a seguinte situação:
O tempo de espera médio é de 17/3 = 5,66 u.t..
O desempenho do RR depende da duração do quantum. Se o quantum for grande, torna-se FCFS. Se, por outro lado, for muito pequeno, o SO vai gastar mais tempo de CPU fazendo troca de contexto do que executando os programas do usuário (e a troca de contexto é puro overhead). Consideremos, por exemplo, um processo de CPU burst de 10 u.t.. Na Figura, observamos que quanto menor é o quantum, maior é o número de trocas de contexto.
4.3.5) Algoritmo de Múltiplas Filas
Esse algoritmo foi criado para ambientes nos quais os processos são facilmente classificados em grupos diferentes. Por exemplo, foreground (interativos) e background (batch). Estes dois tipos de processos possuem diferentes necessidades de tempos de resposta e, portanto, podem apresentar diferentes necessidades de escalonamento. Além disso, podem ser definidas prioridades sobre determinado tipo de processo; os foregrounds, por exemplo, possuírem maio prioridade.
O algoritmo de múltiplas filas parte a fila de prontos em diversas filas (Figura 4.2). Cada fila pode ter uma política de escalonamento diferente. Deve existir também um escalonamento entre as filas, que geralmente é um baseado em prioridades fixas. Uma outra possibilidade é dar uma fatia de tempo (time-slice) a cada uma das filas.
4.3.6) Algoritmo de Múltiplas Filas com Realimentação
No algoritmo anterior, os processos não mudam de fila. O algoritmo de múltiplas filas com realimentação permite que isso ocorra. O objetivo aqui é separar processos com características CPU burst diferentes. Por exemplo, se um processo usa muita CPU, é movido para filas de prioridade mais baixa, deixando processos I/O bound e interativos em fila de maior prioridade. De modo análogo, um processo que espera por longo período de tempo em fila de prioridade baixa pode ser movido para uma fila de prioridade maior.
Por exemplo, considere três filas, numeradas de 0 a 2 (Figura 4.3). O escalonador primeiro executa todos os processos da fila 0 (a de maior prioridade). Quando esta fica vazia, executa os da fila 1. Os processos da fila 2 só são executados se as filas 0 e 1 estiverem vazias. Se um processo chega na fila 0, interrompe a execução de um processo de fila 1 ou 2. Um processo que chega na fila 1 interrompe um da fila 2 (isso pode causar starvation se não for devidamente tratado).
Em geral, o escalonador desse tipo é definido pelos seguintes parâmetros:
· O número de filas;
· O algoritmo para cada fila;
· Um método para determinar quando um processo deve ser posto na fila de maior prioridade, evitando, por exemplo, o starvation;
· Um método para determinar quando um processo deve ser posto na fila de menor prioridade;
· Um método para determinar em qual fila o processo inicia.
Este é o algoritmo de escalonamento mais geral (pode ser configurado para qualquer sistema) e é o mais complexo. É necessário, porém, selecionar valores de todos os parâmetros para obter um bom escalonamento. 
Capítulo 5
Gerência de Memória
Anteriormente, vimos como a CPU pode ser compartilhada por um conjunto de processos. Como conseqüência do escalonamento de CPU, podemos aumentar tanto a utilização da CPU quanto a velocidade de resposta às requisições do usuário. Porém, para obtermos este aumento de performance, é necessário ter vários processos simultaneamente em memória; isto é, é necessário compartilhar memória.
5.1) Conceitos Básicos
A memória é uma grande array de palavras ou bytes, cada qual com seu próprio endereço. A CPU busca instruções na memória de acordo com o valor armazenado no PC e tais buscas podem ocasionar buscas adicionais de dados ou ainda armazenamento de resultados em determinados endereços de memória.
Mas quais são os passos envolvidos na execução de uma instrução? De maneira breve, podemos citar os seguintes passos:
1) Busca da instrução em memória;
2) Decodificação da instrução que pode ocasionar a busca de operandos em memória;
3) Após a instrução ser executada, os resultados podem ser retornados para a memória.
5.2) Address Binding (Relocação de endereços)
Como visto anteriormente, deve-se distinguir, por suas características próprias, o significado de programa e o de processo. O programa reside em disco como um arquivo binário executável. Para que ele seja executado, ele deve ser carregado na memória e, então, passa a ser chamado de processo. Dependendo do tipo de gerência de memória adotada, o processo pode “pular” do disco para a memória e vice-versa durante a sua execução.
O procedimento normal é selecionar um processo da fila de entrada e carregá-lo na memória para iniciar a competição pela utilização da CPU. À medida que o processo executa, ele acessa instruções e dados na memória. Eventualmente, o processo termina sua execução e a memória por ele ocupada é então liberada e um novo processo pode ser carregado e executado nesta região.
A maioria dos sistemas operacionais permite que um processo de usuário resida em qualquer parte da memória física. Porém, embora o espaço de endereçamento físico inicie no endereço 00000, não há nada que force que o processo do usuário seja carregado neste endereço (00000). Isto é, o primeiro endereço do processo não é, em geral, o endereço 00000 da memória, o que acarreta a relocação dos endereços (address binding).
Na maioria das vezes, o programa passa por diversas etapas (algumas opcionais), até ser efetivamente executado, como pode ser visto na Figura 5.1. Os endereços podem ser representados de diversas formas durante estas etapas:
· No programa fonte, endereços geralmente são simbólicos (como i, j, nome, etc.) ( as conhecidas variáveis.
· O compilador associa esses endereços simbólicos a endereços relocáveis (por exemplo, 14 bytes a partir do início do módulo).
· O link-editor ou o loader, por sua vez, associam esses endereços relocáveis a endereçosabsolutos de memória (como, 74014).
Cada tipo de binding consiste no mapeamento de um espaço de endereçamento em outro. Neste caso, um mapeamento de endereços lógicos em endereços físicos.
A associação de endereços de memória a instruções e dados, dependendo do sistema computacional, pode ser feita em:
· Tempo de compilação: se em tempo de compilação é conhecido o endereço inicial de memória onde o programa irá executar, então o código absoluto pode ser gerado durante a compilação. Porém, se em algum momento posterior, o endereço inicial for alterado, será necessária a recompilação do programa.
· Tempo de carga: se em tempo de compilação não é conhecido o endereço inicial da região de memória onde o programa irá executar, então o compilador gera código relocável, e a associação de endereços e dados a endereços de memória (binding) é postergada até o tempo de carga (se o endereço inicial mudar, então não será necessário recompilar todo o programa).
· Tempo de execução: se o processo pode ser movido de uma parte da memória para outra durante a sua execução, então a associação de endereços deve ser feita em tempo de execução (nesse caso, é necessário hardware de relocação).
5.3) Carga Dinâmica
Para obter uma melhor utilização do espaço de memória, podemos utilizar a carga dinâmica. Nesse caso, uma rotina só é carregada quando é chamada. Todas as rotinas são mantidas em disco em formato relocável e só serão carregadas no momento que forem referenciadas.
O programa principal é carregado na memória e executado. Quando uma rotina chama outra rotina, ela verifica se a rotina chamada já foi carregada. Se não, tal rotina deve ser carregada na memória e as estruturas de dados atualizadas de modo a refletir a nova situação. O controle então é transferido para a rotina recém-carregada.
A vantagem desta técnica é que determinada rotina só será carregada se realmente for necessária, sendo particularmente útil quando uma grande quantidade de código for necessária para tratar situações não muito freqüentes, como o tratamento de erros. Neste caso, embora o programa possa ser muito grande, a parte que é realmente utilizada pode ser muito menor, fazendo com que menos memória seja necessária.
Carga dinâmica não requer suporte especial do sistema operacional. Fica sob a responsabilidade do usuário fazer seus programas tomando vantagem dessa técnica.
5.4) Link Dinâmico (DLL)
Até pouco tempo, a maioria dos sistemas operacionais suportava apenas o link estático, onde as bibliotecas das linguagens são tratadas como qualquer módulo objeto e são “linkadas” ao programa objeto a fim de gerar o executável.
Conceitualmente, o link dinâmico é semelhante à carga dinâmica. Porém, ao invés da carga ser postergada, o que é postergado até o tempo de execução é a link-edição. Sem essa facilidade, todos os programas são obrigados a ter uma cópia de rotinas de biblioteca usadas no próprio módulo executável, o que ocasiona um alto consumo de espaço em disco e também de memória.
Para cada referência a determinada rotina de biblioteca, é incluído um stub no executável. Stub é um pequeno código que indica como localizar uma rotina de biblioteca residente em memória ou ainda como carregá-la se ela ainda não estiver em memória.
Quando o stub é executado, ele se substitui pelo endereço da rotina, e a executa. Na próxima vez que a rotina for chamada, ela será executada diretamente, sem nenhum custo para o link dinâmico.
Com esta técnica, todos os processos que utilizam, por exemplo, a biblioteca Biblio1, acabam por acessar a mesma cópia, ao invés de cada processo ter tal cópia incorporada em seu código.
Ao contrário da carga dinâmica, o link dinâmico já requer uma ajuda adicional do sistema operacional. 
5.5) Sobreposições (Overlays)
Os sistemas operacionais iniciais exigiam que o programa estivesse todo em memória antes de iniciar a sua execução o que fazia com que o tamanho do processo fosse limitado ao tamanho da memória. Porém, se um processo for maior do que a memória física, então, algumas vezes, a técnica conhecida como overlays pode ser usada.
A idéia é manter na memória somente instruções e dados que são necessários em dado momento. Se outras instruções são necessárias, são carregadas em endereços anteriormente ocupados por instruções não mais necessárias.
Para exemplificar o funcionamento desta técnica, consideremos um assembler que executa em dois passos (Figura 5.2). Durante o passo 1, ele constrói a tabela de símbolos. Então, no passo 2, o código de máquina é gerado. Dessa forma, é possível separar seu código em subpartes que incluem: passo 1 (70 K), passo 2 (80 K), tabela de símbolos (20 K) e rotinas comuns aos 2 passos (30 K). Deve-se observar que esses valores (tamanho de cada subparte) são apenas para exemplificar. 
Com tais valores, o total de memória para carregar o assembler é de 200 K. Se tivermos apenas 150 K, o processo não poderá ser executado.
Se a técnica de overlays é usada, então o passo 2 pode ser carregado na mesma região ocupada anteriormente pelo passo 1, uma vez que são códigos totalmente independentes. É preciso, então, acrescentar um pequeno código (driver de overlay) para que a carga do passo 2 possa ser realizada. Dessa forma, a última instrução do passo 1 faz um jump para o início desse código adicional que carrega o passo 2, sobrescrevendo o passo 1 ali antes carregado.
5.6) Swapping
Como visto várias vezes anteriormente, um processo precisa estar na memória para que possa ser executado. É possível, porém, retirá-lo da memória temporariamente (swap out) para a memória de apoio (backing store), que, em geral, é um disco, e mais tarde trazê-lo de volta para continuar sua execução (swap in) (Figura 5.3).
Por exemplo, suponha um ambiente com multiprogramação no qual o algoritmo de escalonamento RR é usado. Quando o quantum se esgota, o gerente de memória pode fazer swap out do processo e swap in de outro para a memória que ficou livre. Nesse meio tempo, o escalonador de CPU aloca um outro quantum para um outro processo em memória. Quando cada processo esgota seu quantum, é trocado (swapped) por outro processo. Idealmente, o gerente de memória faz o swapping rápido o suficiente, de modo a existir sempre um processo na memória, pronto para executar, quando o escalonador de CPU desejar reescaloná-la. O quantum também deve ser grande o suficiente para que uma quantidade razoável de computação seja feita entre trocas sucessivas.
Uma variação do swapping é usada para escalonamento baseado em prioridades. Se um processo de maior prioridade chega à fila de entrada, então o gerente de memória pode fazer swap out de um processo de prioridade mais baixa, a fim de carregar e executar o processo de maior prioridade. Quando o processo de maior prioridade terminar sua execução, o de menor sofre swap in e pode então continuar sua execução. Essa variação do swapping é chamada roll-out, roll-in.
Normalmente um processo que sofreu swap out, sofre swap in para a mesma região de memória ocupada anteriormente. Essa restrição está condicionada ao momento da associação de endereços à região de memória (address binding). Se a associação é feita em tempo de compilação ou em tempo de carga, então o processo não pode ser movido para regiões diferentes da original para que a relocação de endereços não necessite ser refeita. Se a associação de endereços é feita em tempo de execução, então outras regiões de memória podem ser usadas para fazer swap in do processo.
O swapping exige memória de apoio que deve ser grande suficiente para conter imagens de memória de todos os usuários e deve permitir acesso direto a estas imagens; por esse motivo, os discos são utilizados na implementação desta memória.
Deve-se observar que agora a fila dos prontos passa a ser constituída por todos os processos que estão prontos para execução e cujas imagens se encontram na memória de apoio ou na principal. Sempre que o escalonador de CPU decide executar um processo, ele chama o dispatcher que verifica se o processo escolhido encontra-seem memória ou não. Se não estiver em memória e não existir memória livre, então o dispatcher faz swap out de algum processo em memória e, em seguida, swap in do processo desejado. Depois, restaura registradores e passa o controle para o processo selecionado (o tempo necessário para a troca de contexto aumenta).
Existe ainda uma outra restrição no swapping. O problema surge se for feito swap out de um processo com E/S pendente. Como os dispositivos trabalham de forma assíncrona, quando um pedido for atendido, haverá tentativa de usar memória agora pertencente a outro processo (o que sofreu swap in na região de memória do anterior), o que acarretará alguma forma de erro. Existem duas soluções para este problema: nunca fazer swap out de processos com E/S pendente, ou executar E/S em buffers do SO. Nesse último caso, a transferência do buffer do sistema para o processo só se dá quando este voltar à memória (swap in).
5.7) Alocação Contígua de Memória
A memória principal tem que acomodar tanto o sistema operacional quanto os programas do usuário. Para isso, a memória é usualmente dividida em duas partes: uma só para o SO e a outra para os programas de usuário. Geralmente, o SO fica nos endereços mais baixos de memória uma vez que é lá que se encontra o vetor de interrupção.
5.7.1) Partição Única
A técnica de gerência de memória mais simples é a ausência de gerência. O usuário tem controle sobre toda a máquina e total flexibilidade para usar a memória da forma que desejar. Esta técnica é simples, sem custo e não requer hardware especial para gerência de memória, uma vez que não existe SO. Por outro lado, as desvantagens incluem ausência de serviços, de tratamento de interrupções e não existe seqüenciamento de jobs (é usado somente em sistemas dedicados).
A próxima técnica mais simples consiste em particionar a memória em duas regiões: uma para o SO e outra para o programa do usuário. Dessa forma, o SO deve ser protegido de acesso ilegal e tal proteção é feita pelo hardware.
Outro problema a ser considerado é a carga do processo de usuário. Embora o espaço de endereçamento físico comece em 0, o primeiro endereço do programa do usuário começa no endereço contido no registrador base, que, em geral, não é o endereço 0. Se esse valor é conhecido em tempo de compilação, o código absoluto pode ser gerado durante a compilação. Porém, se o endereço inicial da partição do usuário mudar, então será necessário recompilar todo o programa.
Como alternativa, o compilador gera código relocável, e a ligação de instruções e dados a endereços de memória (relocação de endereços) é postergada até o tempo de carga.
Em ambos os casos, o endereço inicial da região de memória na qual o programa executa não pode ser alterado durante a execução do programa (isso pode ser desejável se código transiente do SO estiver presente).
Existem duas formas para a solução desse problema:
· Carregar o processo do usuário nos endereços mais altos (todo o espaço de memória não utilizado fica no meio e tanto o SO como o programa do usuário podem se expandir).
· Fazer a relocação de endereços em tempo de execução.
O programa do usuário gera endereços lógicos. O hardware apresentado converte tais endereços nos endereços físicos correspondentes. Dessa forma, torna-se possível movimentar o programa de usuário na memória em tempo de execução e apenas alterar o conteúdo do registrador base.
Se o endereço lógico do programa for de 0 a max, seus endereços físicos correspondentes serão RB+0 a RB+max, onde RB é o conteúdo do registrador base.
Nota: o SO pode acessar endereços físicos diretamente em modo supervisor. Porém, todas as informações passadas pelo programa do usuário para o SO devem ser relocadas pelo SO.
5.7.2) Múltiplas Partições
Em sistemas multiprogramáveis, diversos processos residem em memória e a CPU é chaveada entre eles. O problema então está em alocar memória para os diversos processos que estão na fila de entrada esperando para serem levados para a memória.
A técnica de gerência de memória conhecida por múltiplas partições nos permite trabalhar tanto com número fixo quanto variável de tarefas.
No primeiro deles, a memória é dividida em um número de regiões ou partições de tamanho fixo. Cada uma delas pode conter exatamente um processo o que faz com que o grau de multiprogramação fique limitado ao número de partições.
Quando uma partição torna-se livre, então um processo da fila de entrada é selecionado e carregado nesta partição. Quando o processo termina, a partição se torna novamente disponível para que outro processo possa ser carregado. Deve-se observar que, uma vez que o tamanho das partições é fixo, o número de partições é sempre o mesmo, o que caracteriza esta técnica como multiprogramação com número fixo de tarefas (MFT).
A generalização desta técnica é conhecida como multiprogramação com número variável de tarefas (MVT). Nesta técnica, o SO mantém uma tabela indicando quais as partes da memória estão livres e quais estão ocupadas. Inicialmente, a memória é um único bloco livre. Quando um processo chega na fila de entrada, o LTS (escalonador de longo prazo) busca um bloco de memória livre capaz de contê-lo. Se esse bloco existir, é alocada memória suficiente para o processo, e o restante do bloco é mantido disponível para necessidades futuras (em qualquer instante, existem blocos de memória livre de diversos tamanhos espalhados) (Figura 5.6).
A alocação dinâmica de memória utiliza três estratégias distintas para satisfazer a necessidade de n palavras de uma lista de regiões de memórias livres. A lista de regiões livres de memória é pesquisada para alocar uma região, segundo:
· First-fit: aloca a primeira região capaz de conter o programa (a busca termina assim que a primeira região é encontrada e pode ser iniciada pelo início da lista ou a partir de onde a pesquisa anterior terminou – é mais rápida).
· Best-fit: aloca a menor região capaz de conter o programa (a lista precisa ser toda pesquisada a menos que seja mantida ordenada por tamanho de região – produz a menor região resto).
· Worst-fit: aloca a maior região livre disponível (a lista precisa ser toda pesquisada a menos que seja mantida ordenada por tamanho de região – produz a maior região resto).
As três técnicas provocam a fragmentação externa, isto é, a medida que os processos são carregados na memória e removidos, a memória fica partida em pequenos pedaços. A fragmentação externa está presente se existe memória total suficiente para atender um pedido, mas essa memória não forma um único bloco.
Como diversos processos residem na memória simultaneamente, é preciso um hardware para proteção de memória, de modo que a execução de um não interfira na execução de outros. Deve-se cuidar para que um processo de usuário não invada a memória do SO nem regiões de memória alocadas aos outros processos de usuário.
Como pode ser visto na Figura 5.7, o hardware de proteção de memória utiliza os registradores base e limite, possibilitando a relocação de endereços em tempo de execução. O registrador base contém o menor endereço físico e o registrador limite contém o tamanho do programa. Desse modo, cada endereço lógico é dinamicamente relocado pela soma do valor contido no registrador base com o endereço lógico.
Quando o escalonador de CPU seleciona um processo para ser executado, o dispatcher carrega os registradores base e limite com os valores corretos, contidos no PCB.
Como cada endereço gerado pela CPU é manipulado pelo hardware de proteção de memória, um processo em execução não pode acessar endereços que não pertençam ao seu espaço de endereçamento, o que caracterizaria violação de memória.
Um outro problema encontrado nessa e nas técnicas de gerência anteriores consiste na fragmentação interna, pois regiões de memórias de pequenos tamanhos podem não ser devolvidas para lista de regiões livres, quando da carga de um programa. Isso ocorre pois pequenas regiões (2 bytes, por exemplo) não são úteis e acabam por retardar a pesquisa das regiõeslivres.
À medida que programas chegam ao sistema, eles são colocados na fila de entrada. O LTS leva em conta as necessidades de memória de cada processo e a quantidade de memória disponível para determinar a que processos serão dadas as regiões livres. Quando a memória é alocada para o processo, este é carregado na memória e, se necessário, é relocado. Nesse instante, ele passa a competir pela utilização da CPU. Quando o processo termina sua execução, a área de memória por ele ocupada é liberada e, então, o escalonador de processos pode selecionar um outro processo da fila de entrada.
Assim, em qualquer instante, deve existir a lista dos tamanhos dos blocos de memória livres e a fila de entrada, esta podendo estar ordenada conforme o algoritmo de escalonamento adotado. O LTS aloca memória para os processos da fila até que a necessidade do primeiro processo da fila não possa mais ser satisfeita. Nesse instante, este escalonador pode esperar até que haja memória para o processo, ou passar a examinar os próximos processos da fila de entrada para verificar se a necessidade de um processo de menor prioridade pode ser satisfeita.
A utilização de memória da MVT é geralmente melhor que na MFT. A fragmentação interna se existir é pequena, mas a fragmentação externa é considerável. No pior caso, pode existir um fragmento entre cada dois processos.
A compactação é uma solução para a fragmentação já que seu objetivo é arrumar o conteúdo da memória de forma a ter-se toda a memória livre em um único bloco. Porém, a compactação só é possível se a relocação dinâmica (em tempo de execução) é usada. Nesse caso, o programa é mudado de lugar e o registrador base é alterado.
Quando a compactação é possível, é preciso determinar seu custo. O algoritmo de compactação mais simples move todos os processos para uma das extremidades da memória, o que pode se apresentar muito caro. Também é possível mover apenas alguns processos de modo a minimizar o número de palavras copiadas na memória durante a compactação. Se a MVT for usada associada ao swapping, o código adicional para a compactação fica reduzido.
Capítulo 6
Paginação
A paginação é uma solução para a fragmentação externa, pois permite que a memória de programas seja não contínua, ou seja, a memória livre é alocada para o programa qualquer que seja a sua localização. 
6.1) Princípios Básicos
Nesta técnica, a memória é dividida em blocos de tamanho fixo chamados de frames e a memória lógica (o programa) é divida em blocos chamados de páginas. Obs.: O tamanho da página é igual ao do frame.
Quando um programa chega para executar, suas páginas são carregadas em quaisquer frames livres. Cada endereço gerado pela CPU é composto por duas partes: o número da página (p) que indexa a tabela de páginas (TP), e o deslocamento dentro dessa página (d). A TP contém o endereço base de cada página na memória. A posição na TP indexada por p contém o endereço base do frame (f). Combinando f com d, o hardware de paginação produz o endereço físico de memória (Figura 6.1).
O tamanho da página (e do frame) é geralmente uma potência de 2 (varia de 512 B a 8 KB), evitando assim a divisão para a obtenção de p e d. Se a página tem tamanho 2n, os n bits menos significativos do endereço lógico indicam o deslocamento d e os bits restantes indicam o número da página (p).
A paginação é uma forma de relocação dinâmica, pois cada endereço lógico é mapeado, por meio do hardware, em algum endereço físico. Usando paginação, não há fragmentação externa, isto é, qualquer frame livre pode ser alocado a um processo que dele necessite. Existe, no entanto, alguma fragmentação interna, pois a última página pode não estar completamente cheia (em média, a fragmentação é de meia página por programa).
A fragmentação interna aponta que o tamanho da página deve ser pequeno, mas isso obriga uma TP grande o que aponta para o tamanho da página grande. Acessos eficientes a disco também apontam para páginas grandes. Normalmente, as páginas possuem 2 ou 4 KB.
Cada processo tem sua própria tabela de páginas que é salva no PCB pelo SO quando o processo perde o controle da CPU. Quando um programa deseja executar, suas páginas são carregadas em quaisquer frames livres e sua TP é preenchida de forma a refletir o carregamento (Figura 6.2). 
Uma vez que o SO controla o mapeamento de endereços lógicos em físicos, ele precisa manter o controle dos frames livres (e a quantidade de frames livres). Essas informações são mantidas numa estrutura de dados chamada de tabela de frames. A tabela de frames possui uma entrada para cada frame, onde está indicado:
· Frame livre ou ocupado.
· Se ocupado, com qual página e de qual processo.
O SO mantém uma cópia da TP para cada programa e deve cuidar que todos os endereços lógicos usados como parâmetros de E/S sejam traduzidos em endereços físicos.
6.2) Implementação da TP
No caso mais simples, a TP é implementada em registradores dedicados e o dispatcher os recarrega como qualquer outro registrador. Instruções para carregar ou modificar os registradores da TP são privilegiadas, portanto só o SO pode alterar o mapeamento de memória.
Como todo acesso à memória passa pela TP, então o desempenho é a maior preocupação. Essa solução de ter a TP em registradores é satisfatória se a tabela for razoavelmente pequena.
Se a TP cresce muito (maior que 256 entradas, por exemplo) é preciso mantê-la em memória, e um único registrador na CPU (Page Table Base Registrer - PTBR) aponta para a TP. Isso reduz o tempo necessário para a troca de contexto, já que não é necessário recarregar todos os registradores da TP, apenas o PTBR.
O problema é que para acessar um endereço da memória do usuário, são necessários dois acessos à memória: um à TP e o outro ao endereço propriamente dito (o tempo de acesso à memória é dobrado), o que em muitos casos é intolerável. Para a solução desse problema, é usado um tipo de memória chamada memória cache.
A cache é uma memória de alta velocidade. Cada registrador da cache tem dois campos: a chave e o valor. Quando um item é apresentado à cache, esse item é comparado simultaneamente com todos os campos chave. Se o item é igual a alguma chave, o valor correspondente a essa chave é devolvido. A cache é rápida, porém cara, e tem em geral de 8 a 2048 entradas (Figura 6.3).
A cache é usada com a TP da seguinte forma:
· Somente algumas entradas da TP são mantidas na cache. Quando um endereço lógico é gerado pela CPU, o nº da página (p - o item) é enviado para a cache. Se p é igual a algum campo chave da cache, então f (que está no campo valor correspondente) é devolvido imediatamente e usado para gerar o endereço físico (apenas 10% a mais de tempo é consumido).
· Se p não está presente na cache, então é necessário acessar a TP em memória e obter o f, que é usado para o acesso à memória desejado, e atualizar a cache para posterior uso (isso pode requerer substituição).
Na troca de contexto, é preciso que a cache seja esvaziada para garantir que o próximo processo a usar a CPU não obtenha algum f do processo anterior.
Considerando, por exemplo, a taxa de acerto como sendo 80% (é chamada de taxa de hit) dos acessos, e que 20ns são gastos para pesquisar a cache, e que 100ns são gastos para acessar a memória, então se ocorre hit, um acesso à memória consome 120ns. Se ocorre um miss, então são gastos 220ns (100 + 20 + 100). Portanto, 120ns são gastos para acessar a memória em 80% dos casos, e em 20% dos casos são gastos 220ns.
Para determinar o tempo efetivo de acesso à memória usamos a taxa de hit: tempo efetivo de acesso à memória = 0,80 ( 120 + 0,20 ( 220 = 140ns.
O acesso à memória, no exemplo, passou de 100ns para 140ns (portanto, piorou em 40%).
6.3) Proteção
Cada frame pode ter bits associados para exprimir o tipo de proteção. Normalmente esses bits são mantidos na TP. Por exemplo, bits read/write ou read only. A cada referência à memória, a TP é acessada para geração do endereço físico, e simultaneamente a violação da proteção é verificada (se a proteçãofor violada, ocorre um trap). Pode haver também um bit para garantir execute only.
Existe um outro bit de proteção associado a cada entrada da TP, que indica se a página é válida ou inválida: o bit de validade. Uma página é inválida se o programa tem um nº de páginas menor que o máximo possível permitido (nº de entradas na TP). Em outras palavras, o hardware intercepta qualquer acesso a páginas inválidas (Figura 6.4).
A última página do programa em geral é menor que o frame e acessos a endereços do frame que contém a última página e que não pertencem ao programa não têm proteção. Esses endereços correspondem à fragmentação interna.
Como grande parte dos processos usa somente uma pequena parte dos endereços que podem ter (têm um nº pequeno de páginas), é dispendioso criar TP com todas as entradas possíveis para cada processo.
Alguns processadores possuem o page table length register – PTLR – que contém o nº de páginas do processo em execução. A cada p gerado, p é comparado com o PTLR e qualquer acesso inválido provoca trap.
6.4) Páginas Compartilhadas
Uma das vantagens da paginação é a possibilidade de vários processos compartilharem código comum (importante em time sharing). Para compartilhar código, é necessário que esse seja reentrante (ou código puro), isto é, não modifique a si próprio.
Nesse caso, apenas uma cópia do programa é mantida em memória física, e diversas TP mapeiam os mesmos frames. Os dados de cada um dos processos que compartilham código são mantidos em frames independentes (correspondem a páginas não compartilhadas). Compartilhar páginas evita que múltiplas cópias de programas muito usados sejam mantidas em memória (Figura 6.5).
Capítulo 7
Memória Virtual
Memória Virtual (MV) é a técnica de gerência de memória que permite a execução de processos que não estão inteiramente carregados na memória. A maior vantagem do uso da MV é a possibilidade de executar programas maiores que a memória física de modo transparente ao programador (na técnica de overlays, isto não ocorre). As principais desvantagens da técnica recaem na queda do desempenho (devido ao acesso a disco) e na implementação mais difícil.
7.1) Conceitos Básicos
Ao examinar um programa real, vemos que na maior parte dos casos o programa, durante a sua execução, não precisa estar todo em memória. Por exemplo, observamos que:
1) Suas rotinas para tratamento de erros raramente são utilizadas.
2) Vetores, matrizes, tabelas, etc. são muitas vezes declarados com um número maior de elementos do que o realmente usado.
3) Certas opções/condições que, na prática, nunca ou raramente ocorrem.
Mesmo que todas as partes do programa sejam necessárias em dada execução, não o serão ao mesmo tempo.
A habilidade de executar programas parcialmente carregados na memória produz benefícios como:
1) O tamanho do programa não fica restrito ao tamanho da memória (o espaço de endereçamento virtual pode ser maior que o real).
2) Um maior número de programas pode ser executado em um dado momento (nesse caso, a utilização da CPU e o throughput aumentam, porém o tempo de resposta tende a diminuir).
3) É necessário menos E/S para fazer swapping de programas do usuário.
Em outras palavras, executar programas que não estão inteiramente na memória traz benefícios tanto para o usuário como para o sistema. Com a MV, o programador não precisa preocupar-se com o tamanho da memória física, nem usar a técnica de overlays. A MV é geralmente implementada por meio da paginação sob demanda - PSD.
7.2) Paginação sob Demanda
É semelhante à paginação associada ao swapping. Os processos residem na memória secundária (disco). No lugar de fazer swap-in do programa inteiro para a memória, a MV usa o swapper preguiçoso que só carrega uma página na memória quando um dos seus endereços é referenciado. Como o swapper manipula apenas páginas (não o programa inteiro), ele às vezes é chamado de pager.
Na PSD, é necessário distinguir que páginas estão em memória e que páginas estão em disco. Para isso, é usado o bit de validade que indica se determinada página é ou não válida. Aqui, o bit setado como válido significa que a página associada está em memória e que o acesso é legal. Por outro lado, se o bit está setado como inválido, pode significar ou que a página associada não está em memória ou ainda que o acesso é ilegal (Figura 7.1).
Cada bit de validade é marcado como inválido pelo SO, na criação do processo (alguns sistemas mantêm na TP no lugar de f o endereço de disco que contém a página inválida).
A cada endereço gerado, o hardware verifica o bit de validade:
1) Se é válido, o acesso se dá normalmente como na paginação.
2) Se é inválido, então ocorre um trap chamado de page fault.
O SO trata page fault da seguinte forma (Figura 7.2):
1) Verifica na TP se o acesso é válido ou se é tentativa de violação de proteção de memória.
2) Se o acesso é inválido, o processo é terminado; se é válido, é preciso trazer a página para a memória.
3) É buscado e alocado um frame livre (na lista de frames livres) para conter a página em questão.
4) O disco é programado para realizar a cópia da página para o frame alocado em 3.
5) Quando a leitura termina, a TP é atualizada.
6) A instrução que provocou o page fault é reiniciada (o processo pode agora acessar a página como se ela sempre estivesse na memória).
É possível iniciar a execução de um processo sem que nenhuma de suas páginas esteja em memória. Quando ocorre a tentativa de fazer a busca da primeira instrução do processo, então ocorre um page fault.
A PSD pura nunca traz uma página (nem a primeira) para a memória até que esta seja referenciada. Além do software adicional, o hardware de suporte à PSD é quase o mesmo usado na paginação e no swapping:
1) TP com bit de validade.
2) Memória secundária: em geral um disco de alta velocidade, chamado de swap device, para conter as páginas que não estão em memória (a fração do disco usada com essa finalidade é denominada de backing store).
Algumas restrições são impostas ao hardware. A principal é que é preciso reiniciar a execução da instrução que causou o page fault. Isto é, se o trap ocorre na busca da instrução, é preciso fazer a busca outra vez; se ocorre durante a busca de um operando, é preciso fazer a busca da instrução e do operando outra vez (reiniciar a execução da instrução).
O pior caso é quando o page fault se dá durante a escrita do resultado, porém o esforço necessário é sempre menor que a execução de uma instrução inteira. O problema arquitetural ocorre quando a execução de uma única instrução modifica diversos endereços. Por exemplo, no IBM 360/370, a instrução move character - MVC - pode copiar até 256 bytes de uma região para outra. Outro exemplo é o PDP-11, onde um registrador índice é auto-incrementado (ou decrementado) automaticamente durante a execução de algumas instruções.
Logo, não basta ter hardware de paginação e swapping para que a PSD seja implementada em um sistema computacional. É preciso examinar cuidadosamente o efeito da execução de cada instrução, do conjunto de instruções e resolver situações semelhantes às examinadas (IBM 360/370 e PDP-11).
7.3) Substituição de Páginas
Até esse instante, quando da ocorrência de um page fault, sempre existe um frame livre para carregar a página necessária. A questão é: quantos processos podem estar em execução para garantir que sempre teremos um frame livre, já que não é possível saber antecipadamente quantos frames serão necessários para cada programa?
Se limitarmos o grau de multiprogramação de modo que todos consigam carregar todas as suas páginas, teremos uma subutilização (já que alguns deles não precisarão de todas), deixando muitos frames sem uso.
Por outro lado, se imaginarmos que cada processo usa, por exemplo, apenas a metade de suas páginas e aumentarmos o grau de multiprogramação pode ocorrer que todos os processos precisem de todas as suas páginas, resultando em over-allocating de memória.
Se deixarmos que o over-allocating ocorra, então quando ocorre um page fault,