Apostila BASE Sistemas Operacionais-Alunos

Embed Size (px)

Citation preview

APOSTILA BASE SISTEMAS OPERACIONAIS

Agradecimentos Copyright 2002-2003, ESAB - Escola Superior Aberta do Brasil. Material cedido para estudos a Turma de Tec. em Anlise e Desenvolvimentos de Sistemas 2012 Prof. Mrcio

Professor Mrcio agrade gentilmente a ESAB e a Professora: Heloisa Cristina Azevedo Sobreira por cederem este Material para estudo acadmico.

CITAO DE MARCAS NOTRIAS

Vrias marcas registradas so citadas no contedo deste mdulo. Mais do que simplesmente listar esses nomes e informar quem possui seus direitos de explorao ou ainda imprimir logotipos, o autor declara estar utilizando tais nomes apenas para fins editoriais acadmicos.

Declara ainda, que sua utilizao tm como objetivo, exclusivamente na aplicao didtica,

beneficiando e divulgando a marca do detentor, sem ainteno de infringir as regras bsicas de autenticidade de

sua utilizao e direitos autorais.

E por fim, declara estar utilizando parte de algunscircuitos eletrnicos, os quais foram analisados em pesquisas de laboratrio e de literaturas j editadas, que se

encontram expostas ao comrcio livre editorial.

Sumrio1- Introduo e Histrico 1.1 Histrico dos Sistemas Operacionais 1.1.1. A Primeira Gerao (1945-1955): Vlvulas e Painis 1.1.2. A Segunda Gerao ( 1955-1965): Transistores e Sistemas Batch 1.1.3 A Terceira Gerao (1965-1980): Cls e Multiprogramao 1.1.3.1 Operao Off-Line 1.1.4. A Quarta Gerao: ComputadoresPessoais 1.1.4.1Buferizao 1.1.4.2Spooling 1.1.4.3Multiprogramao 1.1.4.4Tempo Compartilhado 1.1.4.5.Os Conceitos de Interrupo e Trap 2 Processos 2.1 O Ncleo do Sistema Operacional (Kernel) 2.1.1 Um Resumo das Funes do Ncleo 2.2 EscalonamentodeProcessos 2.2.1 Escalonamento FCFS ou FIFO 2.2.2 Escalonamento Round Robin (RR) 2.2.3 Escalonamento com Prioridades 2.2.4 Multilevel Feedback Queues 2.2.5 Escalonamento com Prazos 2.2.6 Escalonamento Shortest-Job-First (SJF) 2.3 Comunicao Entre Processos (IPC) 2.3.1 Processamento Paralelo 2.3.1.1 Comandos PARBEGIN e PAREND (Dijkstra) 2.3.1.2 Comandos FORK e JOIN (Conway e Dennis) 2.3.2 Excluso Mtua 2.3.3 Regies Crticas 2.3.4 Primitivas de Excluso Mtua 2.3.5 Implementao de Primitivas de Excluso Mtua 2.3.6 Excluso Mtua para N Processos 2.3.7 Semforos 2.3.7.1 Sincronizao de Processos com Semforos 2.3.7.2 A Relao Produtor-Consumidor 2.3.7.3 Semforos Contadores 2.3.7.4Implementando Semforos, P e V 2.3.8 Monitores 2.3.9 Passagem deMensagens 2.4 Deadlocks e Adiamento Indefinido 2.4.1 Exemplos de Deadlocks 2.4.2 Um Deadlock de Trfego 2.4.3 Um Deadlock Simples de Recursos 2.4.4 Deadlock em Sistemas de Spooling 2.4.5 Adiamento Indefinido 2.4.6 Conceitos de Recursos 2.4.7 Quatro Condies Necessrias para Deadlock 2.4.8 Mtodos para Lidar com Deadlocks 2.4.9 Preveno de Deadlocks 2.4.9.1 Negando a Condio Mutual Exclusion 2.4.9.2 Negando a Condio Hold and Wait 4 7 7 9 12 19 20 20 24 25 25 28 30 35 35 36 37 37 39 40 43 43 44 44 45 47 47 48 49 50 51 52 53 54 56 57 58 63 64 64 64 65 65 66 66 68 68 69 70 70

2.4.9.3 Negando a Condio No Preemption 2.4.9.4 Negando a Condio Circular Wait 3 Gerenciamento de Memria 3.1 Conceitos Bsicos 3.1.1 Ligao de Endereos (Address Binding) 3.1.2 Carregamento Dinmico (Dynamic Loading) 3.1.3 Ligao Dinmica 3.1.4 Overlays 3.2 Endereamento Lgico e Endereamento Fsico 3.3 Swaping 3.4 AlocaoContgua de Memria 3.4.1 Alocao com Partio nica 3.5 Memria Virtual 3.5.1 Paginao 3.5.2 Segmentao 3.5.2.1Segmentao com Paginao: 4 Gerenciamento deArquivos 4.1 Arquivos 4.2 Diretrios 4.2.1 Diretrio de Nvel Simples 4.2.2 Diretrio de Dois Nveis 4.2.3 Diretrios em rvores 4.2.6 Diretrios em Grafos Acclicos 4.3 Gerenciamento de Espao Livre em Disco 4.3.1 Mapade Bits 4.3.2 Lista de Blocos Livres 4.3.3 Bloco de Endereos 4.3.4 Tabela de Blocos Contguos 4.4 Alocao de Espao em Disco 4.4.1 Alocao Contgua 4.4.2 Alocao Ligada 4.4.3 Alocao Indexada 4.5Escalonamentodo Disco 4.6 Especificao de Execuo Concorrente 4.6.1 Co-Rotinas 4.6.2 Declarao Cobegin/Coend 4.6.3 Declarao Fork/Join 4.6.4 Declarao de Processos Concorrentes 5 Sistemas Distribudos 5.1 Redes de Computadores 5.1.1 Topologias de Redes 5.1.2 Protocolos de Redes 5.2 Sistemas Operacionais de Redes e Distribudos 5.3 Modelos de Arquiteturas de Sistemas Distribudos 5.3.1 Modelo Cliente e Servidor 5.3.2 Modelo Pool de Processadores 5.3.3 Modelo Integrado 5.4 Tolerncia a Falhas 5.5 Balanceamento de Carga 5.5.1 Balanceamento Esttico 5.5.2 Balanceamento Dinmico 5.6 Migrao de Processos

70 71 72 72 73 75 76 79 77 79 83 83 87 88 93 94 95 96 97 97 98 98 99 100 100 101 101 101 102 102 103 103 105 106 107 107 108 108 110 112 113 113 114 115 116 117 119 120 120 121 122 124

1

- INTRODUO E HISTRICO

Podemos dizer sem receio que um computador sem software no passa de um objeto sem utilidade.No entanto, quando equipado com o software adequado, ele capaz de armazenar, processar e recuperar informao, encontrar erros de sintaxe em textos, executar imensa variedade de jogos eletrnicos e de engajar seu usurio em muitas outras atividades bastante produtivas.O software de um computador pode ser dividido generalizando em duas categorias: os programas do sistema, que gerenciam a operao do prprio computador e os programas de aplicao que resolvem problemas para seus usurios. O mais importante dos programas de sistema o sistema operacional. O que um sistema operacional? O sistema operacional um programa que atua como intermedirio entre o usurio e o hardware de um computador. O propsito de um sistema operacional fornecer um ambiente no qual o usurio possa executar programas.Um dos principais objetivos de um sistema operacional tornar o uso do sistema de computao conveniente. Um segundo objetivo usar o hardware do computador de forma eficiente. Para entendermos melhor o que sistemas operacionais, primeiro precisamos compreender como eles se desenvolveram. O sistema operacional um componente importante para todo o sistema de computao. Um sistema de computao pode ser dividido em quatro componentes: o hardware, o sistema operacional, os programas aplicativos e os usurios. justamente neste segundo item que os sistemas operacionais podem ser bem sucedidos ou no, em despertar interesse para que a indstria de software e os programadores independentes construam programas para determinados sistemas operacionais. Isto justifica parte do sucesso do Microsoft Windows, pois, ao mesmo tempo que ele prov uma interface bastante amigvel com o usurio, para o programador, no to difcil criar um programa com janelas, botes, listas, etc, como seria num sistema operacional como o MS-DOS. Alm disso, os sistemas operacionais da Microsoft rodam no hardware mais popular hoje em dia: os computadores baseados em IBM PC. Computadores modernos possuem um ou mais processadores, memria principal, dispositivos de entrada e sada como discos, fitas, teclado, mouse, monitor, interface de rede, entre outros. Escrever programas que utilizem um computador com esta complexidade de forma eficiente muito difcil e trabalhoso. exatamente neste ponto que entram as funes do sistema operacional: abstrair as particularidades do hardware dos programas,4

fornecendo a eles facilidades para sua operao, tais como: rotinas de acesso a dispositivos diversos; funes de armazenamento de dados como criao de arquivos, leitura e escrita de dados; e rotinas de acesso aos dispositivos de interao com a mquina, como teclado, mouse, monitor, etc. Dada a existncia de softwares como o sistema operacional, os programas normalmente so classificados como software bsico (que inclui o sistema operacional), e softwares de aplicao, que so voltados a resolver problemas dos usurios. Podemos visualizar atravs de um diagrama a integrao entre hardware, software bsico e softwares aplicativos, como mostra a figura 1.1. Figura 1.1 Integrao entre aplicativoSistema Bancrio Compiladores Controle de Estoques Editores

hardware,

software bsico e

software

Jogos Interpretador de comandos (shell)

Programas de Aplicao

Sistema OperacionalLinguagem de Mquina Microprogramao Dispositivos Fsicos

Programas de Sistema (software bsico)

Hardware

Olhando para o diagrama, veremos que o que chamamos dehardware na verdade composto de trs camadas. Nem todas as mquinas seguem este esquema, algumas podem ter uma camada a menos, ou mesmo camadas adicionais, mas basicamente, os

computadores seguem o esquema ilustrado na figura 1.1.No nvel mais inferior, temos os dispositivos eletrnicos em si, como o processador, os chips de memria, controladores de disco, teclado, e outros dispositivos, barramentos, e qualquer dispositivo adicional necessrio para o funcionamento do computador. Um nvel

acima, temos a camada de microprogramao, que de forma geral, so pequenos passos (chamados de microoperaes) que formam uma instruo de processador completa, como ADD, MOV, JMP, etc. O conjunto de instrues do computador chamado de linguagem de mquina, e apesar de ser uma espcie de linguagem, podemos dizer que faz parte do hardware porque os fabricantes a incluem na especificao do processador, para que os programas possam ser escritos. Afinal, de nada adianta uma mquina maravilhosa, se no existir documentao alguma de como ela5

funciona. Assim, as instrues que a mquina entende so consideradas parte integrante do hardware.As instrues tambm incluem, geralmente, operaes que permitem ao processador comunicar-se com o mundo externo, como

controladores de disco, memria, teclado, etc. Como a complexidade para acesso a dispositivos muito grande, tarefa do Sistema Operacional esconder estes detalhes dos programas. Assim, o sistema operacional pode, por exemplo, oferecer aos programas uma funo do tipo LEIA UM BLOCO DE UM ARQUIVO e os detalhes de como fazer isso fica a cargo do sistema operacional. Acima do sistema operacional esto os demais programas utilizados pelo usurio final, mas alguns deles ainda so considerados software bsico, como o sistema operacional. Entre eles podemos citar o shell, que consiste do interpretador de comandos do usurio, ou seja, a interface com o usurio. Nos sistemas operacionais mais recentes, freqentemente o shell uma interface grfica (ou em ingls GUI Graphics User Interface). Raramente, numa interface grfica bem elaborada, o usurio precisa digitar comandos para o computador. A maneira mais comum de executar programas, copiar e mover arquivos, entre outras atividades mais comuns, atravs do uso do mouse. Nos tempos do MS-DOS, o teclado era o dispositivo de entrada dominante, por onde o usurio entrava todos os comandos para realizar suas tarefas do dia a dia. O que muito importante observar quanto ao software bsico que, apesar de que editores (ex: bloco de notas do Windows), compiladores (ex: compilador C no Unix), e interpretadores de comando (ex: command.com ou explorer.exe no Windows) normalmente serem instalados junto como sistema operacional em um computador, eles no so o sistema operacional. Eles apenas utilizam o sistema operacional. Portanto, o shell que normalmente usamos em um sistema operacional nada mais do que um programa que utiliza servios do sistema operacional, mas com a finalidade de permitir que os usurios realizem suas tarefas mais freqentes: executar programas e trabalhar com arquivos. A grande diferena entre o sistema operacional, e os programas que rodam sobre ele, sejam software bsico ou software aplicativo, que o sistema operacional roda em modo kernel (ou supervisor), enquanto os demais programas rodam em modo usurio. Estes dois modos de operao dos processadores dos computadores diferem no fato de que em modo supervisor, um programa tem acesso a todo o hardware, enquanto que os programas que rodam em modo usurio, tem acesso somente a determinadas regies de memria, no podem acessar dispositivos diretamente, e precisam pedir para o sistema operacional quando necessitam de alguma tarefa especial. Isto garante que os programas dos usurios, no acabem por invadir reas de memria do sistema operacional, e acabem por travar o sistema. Isto tambm possibilita que programas de diferentes usurios estejam rodando na mesma6

mquina, de forma que um usurio no consiga interferir nos programas de outro.O Ms-dos domina o mercado das mquinas baseadas nos

processadores da INTEL, mais precisamente o 8088 e seus sucessores, 80286, 80386, 80486, conhecidos tambm por 286, 386 e 486, respectivamente. Apesar da primeira verso do Ms-Dos ter sido um tanto ou quanto primitiva, as verses que se seguiram a ela incorporaram uma srie de caractersticas avanadas, inclusive algumas disponveis no UNIX.

1.1 HISTRICO DOS SISTEMAS OPERACIONAIS Os sistemas operacionais vm evoluindo gradualmente com o passar do tempo. Nas sees seguintes iremos enfocar brevemente tal desenvolvimento. Em razo dos sistemas operacionais estarem historicamente e intimamente ligados s arquiteturas das mquinas nas quais eles rodam, vamos analisar cada uma das sucessivas geraes de computadores e observar as principais caractersticas dos sistemas operacionais que rodavam em tais mquinas. A associao da gerao dos sistemas operacionais gerao dos computadores pode ser discutvel, mas a nica forma estruturada de abordar a questo histrica dos sistemas operacionais. O primeiro computador digital foi projetado pelo matemtico ingls Charles Babbage (1792-1871). sabido que, apesar de Babbage ter gasto toda a sua vida e sua fortuna tentando construir sua "mquina analtica", ele jamais conseguiu atingir seu objetivo, pois seu projeto era inteiramente mecnico e a tecnologia da poca no conseguia produzir as engrenagens de alta preciso de que a mquina precisava para funcionar. Desnecessrio dizer que a mquina analtica no tinha um sistema operacional associado. 1.1.1. A Primeira Gerao (1945-1955): Vlvulas e Painis Aps os infrutferos esforos desenvolvidos por Babbage, quase no houve progresso nesta rea at o incio da Segunda Grande Guerra. Em torno de 1940, Howard Aiken, em Harvard, John Von Neumann, no Instituto de Estudos Avannados de Princeton, J. Presper Eckert e William Nlauchley, na Universidade da Pennsylvania, e Konrad Zuse, na Alemanha, tiveram sucesso na construo de computadores primitivos, baseados em vlvulas. Tais mquinas eram enormes, ocupavam salas imensas e empregavam dezenas de milhares de vlvulas em sua construo. Apesar disso, elas eram muito mais lentas que o mais barato dos computadores pessoais disponveis atualmente. Nesta poca, um nico grupo de pessoas era responsvel pelo projeto, construo, programao, operao e manuteno de cada7

mquina. Toda a programao era feita em cdigo absoluto, muitasvezes atravs da fiao de painis para controlar as funes bsicas da mquina. O conceito de linguagem de programao ainda no existia. Os sistemas operacionais tambm no. O acesso ao

computador por parte do usurio era feito atravs da reserva antecipada de tempo de mquina. Ao chegar sua vez de usar o computador, o usurio fazia sua prpria programao nos painis da mquina e passava a torcer para que nenhuma das 20.000 vlvulas do computador viesse a queimar enquanto ele estivesse trabalhando. Nessa poca os programas processados pelos computadores eram constitudos essencialmente por clculos numricos repetitivos, como por exemplo a gerao de tabelas de funes trigonomtricas. No incio dos anos 50, houve uma sensvel melhora no uso de tais mquinas com o advento do carto perfurado que tornou possvel a codificao de programas em cartes e sua leitura pela maquina. dispensando a programao ,atravs de painis. Os demais procedimentos no tiveram qualquer modificao. Inicialmente, existiu somente o hardware do computador. Os primeiros computadores eram mquinas fisicamente muito grandes que funcionavam a partir de um console, que consiste em um perifrico ou terminal que pode ser usado para controlar a mquina por mtodos manuais, corrigir erros, determinar o estado dos circuitos internos e dos registradores e contadores, e examinar o contedo da memria. O console o meio de comunicao entre o homem e a mquina, ou seja, o meio por onde o operador fornece as entradas e por onde recebe as sadas. O console das primeiras mquinas consistia em chaves pelas quais o operador inseria informaes e por luzes indicativas das sadas, que podiam ser impressas ou perfuradas em uma fita de papel. Com o passar do tempo, o uso de teclados para entrada de dados se tornou comum e a sada passou a ser inicialmente impressa em papel. Posteriormente o console assumiu a forma de um terminal com teclado e vdeo. Nesta poca, os programadores que quisessem executar um programa, deveriam carreg-lo para a memria manualmente atravs de chaves no painel de controle, ou atravs de fita de papel ou cartes perfurados. Em seguida, botes especiais eram apertados para iniciar a execuo do programa. Enquanto o programa rodava, o programador/operador podia monitorar a sua execuo pelas luzes do console. Se erros eram descobertos, o programa precisava ser interrompido, e o programador podia examinar os contedos da memria e registradores, depurando-o diretamente do console. A sada era impressa diretamente, ou ainda perfurada em fita ou carto para impresso posterior. As dificuldades nesta poca eram evidentes. O programador era tambm o operador do sistema de computao. Devido escassez de recursos, a maioria dos sistemas usava um esquema de8

reserva para alocao de tempo da mquina. Se voc quisesse usar o computador, deveria reservar um horrio em uma planilha. Alm disso, este mtodo no era eficiente na utilizao de recursos. Supondo que voc tivesse reservado 1 hora de tempo de computador para executar um programa em desenvolvimento. Se voc tivesse alguns erros desagradveis voc provavelmente noterminaria dentro de 1 hora, e deveria juntar seus resultados e

liberar a mquina para a prxima pessoa da fila. Por outro lado, se o seu programa rodasse sem problemas, voc poderia terminar tudo em 35 minutos e a mquina ficaria ociosa at a prxima reserva de horrio. Como as mquinas nesta poca custavam muito dinheiro, pensou-se em algumas solues para agilizar a tarefa de programao. Leitoras de cartes, impressoras de linha e fitas magnticas tornaram-se equipamentos comuns. Montadores (assemblers), carregadores (loaders) e ligadores (linkers) foram projetados. Bibliotecas de funes comuns foram criadas para serem copiadas dentro de um novo programa sem a necessidade de serem reescritas. Um bom exemplo do uso das bibliotecas de funes sobre as rotinas que executavam operaes de entrada e sada (E/S). Cada novo dispositivo tinha suas prprias caractersticas, necessitando de cuidadosa programao. Uma subrotina especial foi escrita para cada tipo de dispositivo de E/S. Essas subrotinas so chamadas de device drivers (controladores de dispositivos), e sabem como conversar com o dispositivo para o qual foram escritas. Uma tarefa simples como ler um caractere de um disco pode envolver seqncias complexas de operaes especficas do dispositivo. Ao invs de escrever cdigo a cada momento o device driver simplesmente utilizado a partir de uma biblioteca.

1.1.2. A Segunda Gerao ( 1955-1965): Transistores e Sistemas Batch O desenvolvimento do transistor em meados dos anos 50 veio a alterar substancialmente o quadro descrito acima. Com o emprego desta nova tecnologia, os computadores tornaram-se confiveis a ponto de serem comercializados. Nesta poca, passou a haver uma distino muito clara entre as pessoas envolvidas no projeto, na construo, na operao, na programao e na manuteno destas mquinas. Elas eram instaladas em salas isoladas e operadas por pessoal especializado. Somente as grandes empresas e rgos governamentais ou universidades podiam pagar os muitos milhes de dlares necessrios aquisio destas mquinas. Para rodar um job (um programa ou um conjunto de programas), o programador primeiro escrevia seu programa em uma folha de papel (em FORTRAN ou em linguagem de montagem), para depois perfura-lo9

em cartes Depois disso ele entregava a massa de cartes a um dos operadores da mquina para que a mesma fosse processada. Ao final do processamento do programa corrente, um dos operadores ia at a impressora e retirava o relatrio emitido, entregando-o na expedico, onde ele seria mais tarde retirado pelo programador do job. Ento ele, o operador, escolhia uma nova massa de cartes, entre as que haviam sido entregues na recepo, e providenciava os recursos necessrios ao processamento deste novo job. Por exemplo,se tal job precisasse do compilador FORTRAN, o operador deveria

providenciar a leitura da massa de cartes correspondente ao compilador FORTRAN. Grande parte do tempo da mquina era gasto com operadores circulando dentro da sala onde ela estava instalada, providenciando recursos necessrios ao processamento de determinada tarefa. Em vista do alto custo de tais equipamentos, no foi surpresa o fato de se encontrar uma soluo que reduzisse o tempo de mquina desperdiado. A soluo encontrada, denominada de sistema batch (lote), consistia em coletar na recepo um conjunto de jobs e fazer a leitura dos mesmos para uma fita magntica empregando um computador pequeno e relativamente barato, tal como o IBM 1401, que era muito bom na leitura de cartes, na cpia destes cartes em fita e na impresso de resultados. Outras mquinas mais sofisticadas, e conseqentemente mais caras, tal como o IBM 7094, eram empregadas no processamento propriamente dito. Esta situao est ilustrada na Fig. 1.2.

Figura 1.2 Aps cerca de uma hora de coleta de jobs, a fita gravada era rebobinada e levada para a sala do computador, onde era montada em sua unidade de fita. O operador ento carregava um programa especial (o antecessor do atual sistema operacional ), que lia e processava o primeiro job da fita. A sada era gravada numa segunda fita, em vez de ser diretamente impressa. Aps o trmino de cada um dos jobs, o sistema operacional lia e processava automaticamente o prximo. Quando todo o lote tivesse sido processado, o operador removia as fitas de entrada e de sada, colocando na unidade de fita de entrada uma nova fita com outro lote de jobs a serem10

processados, levando a fita de sada para ser impressa off line (sem a interveno do computador principal), com auxlio do 1401.A estrutura de um job tpico aparece na Fig. 1.3. Ele comea com o carto $JOB, que especifica o tempo mximo de processamento em minutos, o nmero da conta onde tal tempo deve ser debitado, e o

nome do programador. A seguir vem o carto $FORTRAN solicitando ao sistema operacional que carregue o compilador FORTRAN na memria principal. A seguir aparecem os cartes do programa a ser compilado , seguidos do carto $LOAD, solicitando ao sistema operacional a carga na memria do programa que acabou de ser compilado. (Os programas compilados eram geralmente escritos em fitas de rascunho, e tinham que ser carregados explicitamente.) O carto seguinte, $RUN, pede que o sistema operacional providencie o processamento do programa que acabou de ser carregado, com o conjunto de dados constante dos cartes seguintes ao $RUN. Finalmente, aparece o carto $END, que marca o final do job.

Figura 1.3

Estes cartes de controle, um tanto ou quanto primitivos, foram os precursores das linguagens de controle e dos interpretadores de comando atuais. Os computadores da segunda gerao eram usados maciamente narealizao de clculos cientficos e de engenharia, tal como a

obteno da soluo de equaes diferenciais parciais. Eles eram normalmente programados em linguagem FORTRAN ou em linguagem de montagem. Os sistemas operacionais tpicos da poca eram o FMS (Fortran Monitor System) e o IBSYS, ambos sistemas operacionais desenvolvidos pela IBM para rodar no 7094. Mais tarde, compiladores para linguagens de alto nvel, como FORTRAN e COBOL, surgiram, facilitando muito a tarefa de programao, que antes era feita diretamente na linguagem da mquina. Entretanto a operao do computador para executar um11

programa em uma linguagem de alto nvel era bem mais complexa. Por exemplo, para executar um programa FORTRAN, oprogramador deveria primeiramente carregar o compilador FORTRAN para a memria. O compilador normalmente era armazenado em fita magntica, e portanto a fita correta deveria ser carregada para a unidade leitora de fitas magnticas. Uma vez que o compilador estivesse pronto, o programa fonte em FORTRAN era lido atravs de uma leitora de cartes e escrito em outra fita. O compilador FORTRAN produzia sada em linguagem assembly que precisava ser montada (assembled), isto , convertida para cdigo de mquina. A sada do

montador era ligada (linked) para suportar rotinas de biblioteca.Finalmente, o cdigo objeto do programa estaria pronto para executar e seria carregado na memria e depurado diretamente no

console, como anteriormente. Podemos perceber que poderia existir um tempo significativo apenas para a preparao da execuo de um job (tarefa). Vrios passos deveriam ser seguidos, e em caso de erro em qualquer um deles, o processo deveria ser reiniciado aps a soluo do problema.

1.1.3 A Terceira Gerao (1965-1980): Cls e MultiprogramaoNo incio doa anos 60, a maioria dos fabricantes de computador tinha

duas linhas de produtos distintas e totalmente incompatveis. De umlado estavam as imensas e poderosas mquinas orientadas a palavra,

adequadas ao processamento cientfico pesado, como o IBM 7094. Do outro lado estavam as mquinas comerciais, orientadas a caracter, como o IBM 1401, utilizado pelos bancos e companhias seguradoras para pesquisar arquivos em fita e para impresso de extensos relatrios. O desenvolvimento e a manuteno de duas linhas de produto completamente independentes representava uma carga bastante pesada para os fabricantes. Alm do mais, muitos de seus clientes precisavam inicialmente de uma mquina pequena, mas com o passar do tempo vinham a necessitar de uma mquina maior, capaz de armazenar uma quantidade maior de informaes e de processar com mais rapidez seus programas antigos, desenvolvidos para a mquina de menor porte. A IBM conseguiu solucionar ambos os problemas de uma nica vez com a introduo do Sistema/360. Tal sistema era composto de uma srie de mquinas, todas elas compatveis em nvel de software, abrangendo a faixa que comecava no 1401, e chegava at aquelas muito mais poderosas que o 7094. Estes computadores s diferiam no preo e na performance (capacidade mxima de memria, velocidade do processador, nmero mximo de dispositivos de entrada/ sada etc.). Uma vez que todas estas mquinas tinham a mesma arquitetura e o mesmo conjunto de instrues bsicas (ao12

menos em teoria), os programas escritos para qualquer uma delas rodavam em qualquer outra. Alm do mais, a srie 360 foi projetada com caractersticas para suportar tanto o processamento cientfico quanto o comercial, fazendo com que uma nica famlia de mquinas viesse a atender s necessidades de toda a faixa de clientes. Nos anos seguintes ao lanamento do 360, a IBM produziu novas mquinas, compatveis com a linha 360, usando tecnologias mais modernas, conhecidas como sries 370, 4300, 30R0 e 3090. O 360 foi a primeira famlia de mquinas a usar circuitos integrados (SSI) em sua fabricao, conseguindo uma relao preo/performance muito melhor do que a das mquinas da segunda gerao, construdas com transistores individuais. A srie foi um sucesso, e a idia da famlia de mquinas compatveis foi logo adotada por todos os demais fabricantes. Os descendentes de tais mquinas esto ainda em uso nos grandes centros de computao da atualidade. A idia da famlia nica de mquinas criou um srio problema. A inteno era que qualquer software, incluindo um sistema operacional, rodasse em todos os modelos da famlia, desde as mquinas pequenas, que vieram substituir as 1401 na tarefa de copiar cartes perfurados para fitas magnticas, at as mquinas maiores, desenvolvidas para substituir as 7094 no processamento de problemas que envolviam clculos matemticos pesados, tais como a previso do tempo. Ele deveria ser adequado tanto para sistemas com poucos perifricos quanto para sistemas com um nmero grande de dispositivos de entrada/sada. Deveria funcionar tanto em ambientes para processamento comercial quanto em ambientes para processamento cientfico. Alm disso tudo o sistema operacional deveria ser eficiente em todas as aplicaes onde fosse utilizado. No h como escrever um software para atender eficientemente a todos estes objetivos conflitantes. O resultado da tentativa foi um sistema operacional enorme e extremamente complexo, duas ou trs ordens de magnitude maior que o FMS. Este sistema operacional era composto de milhes de linhas de cdigo em linguagem de montagem, programado por milhares de pessoas, e continha um sem-nmero de bugs que originaram uma srie incontvel de novos releases na tentativa de corrigi-los. Cada nova verso corrigia um conjunto de bugs, mas introduzia alguns novos, fazendo com que seu nmero permanecesse praticamente constante ao longo do tempo. Um dos projetistas do OS/360, Fred Brooks escreveu um livro bastante interessante (Brooks, 1975), narrando sua experincia no projeto. Apesar da impossibilidade de se apresentar um resumo do livro, basta dizer que sua capa mostrava uma manada de monstros pr-histricos encalhados. A capa do lvro de Silberschatz et al. (1991) muito semelhante capa da obra de Fred Brooks. Apesar do seu tamanho e dos problemas que surgiram em seu desenvolvimento, o OS/360 e os sistemas operacionais similares de terceira gerao produzidos por outros fabricantes atenderam relativamente bem grande maioria de seus usurios. Tais sistemas13

vieram a popularizar vrias tcnicas que no estavam implementadasnos sistemas de segunda gerao. A mais importante destas tcnicas

a multiprogramao . No 7094, quando o job corrente parava para aguardar a concluso de operaes de entrada/sada, o processador tambm permanecia inativo at a concluso da operao. No caso das aplicaes cientficas, as operaes de entrada/sada no so muito freqentes, de tal maneira que o tempo perdido aguardando sua concluso no chega a ser significativa. J no caso do processamento comercial, o tempo de espera por entrada/ sada pode chegar a 80 ou 90 por cento do tempo total de processamento, de maneira que algo precisava ser feito para evitar desperdcio do tempo do processador. A soluo inicial foi dividir a memria em diversas partes, com um job alocado a cada uma delas. Enquanto um job esperava a concluso de sua operao de entrada/sada, um outro job poderia estar utilizando o processador. A idia era manter na memria simultaneamente uma quantidade de jobs suficiente para ocupar o processador 100 por cento do tempo. Deve-se observar que o fato de se manter na memria vrios jobs ao mesmo tempo tornou necessria a utilizao de um hardware especial para proteger cada um dos jobs contra acessos indevidos, provenientes dos demais. O 360 e os demais sistemas de terceira gerao estavam equipados com este hardware, de forma que foi possvel a implementao da multiprogramao nestas mquinas. (fig.1.4)

Figura 1.4 Outra caracterstica importante dos sistemas operacionais de terceira gerao era sua capacidade de ler jobs de carto direto para o disco, to logo a massa de cartes tivesse chegado sala do computador. Desta forma, assim que um job ativo terminasse, o sistema operacional carregaria um novo job na partio livre da memria, proveniente do disco. Esta tcnica foi denominada de SPOOL (Simultaneous Peripheral Operation On Line) e era tambm empregada para as operaes de sada. Com o SPOOL, os 1401 s deixaram de ser necessrios. Apesar de os sistemas operacionais de terceira gerao serem adequados para processamento cientfico pesado e para as aplicaes comerciais, eles ainda eram sistemas batch. A grande automatizao introduzida pelos sistemas de terceira gerao fez com que muitos programadores sentissem saudades da poca da primeira gerao de sistemas quando eles tinham toda a mquina disposio por horas14

a fio, sendo-lhes possvel consertar rapidamente seus programas.Com os sistemas de terceira gerao, o tempo entre a submisso do

job e a disponibilizao de sua sada passou a ser medido em horas, de maneira que o simples esquecimento de uma vrgula poderia fazer com que o programador viesse a perder a metade do dia. ; A vontade de obter bons tempos de resposta pavimentou o caminho que levou ao desenvolvimento dos sistemas com compartilhamento de tempo (timesharing), uma variao dos sistemas multiprogramados, onde cada usurio tinha um terminal on-line sua disposio. Em tais sistemas, se existissem 20 usurios ativos com 17 deles tomando um cafezinho, o processador seria alocado ciclicamente a cada um dos trs jobs que lhe esto requisitando servio. Uma vez que a correo de programas requer usualmente comandos que so executados rapidamente (por exemplo, compile um programa de trs pginas) em vez de comandos cuja execuo demanda grande quantidade de tempo (ordenar um arquivo de 1 milho de registros armazenado em fita), o computador ser capaz de oferecer aos usurios um servio interativo, com tempo de resposta bastante atrativo. Os jobs muito grandes so processados em background, quando o processador estiver livre. O primeiro sistema de compartilhamento de tempo, o CTSS, foi desenvolvido no MIT para um 7094 especialmente modificado (Corbato et al., 1962), porm tais sistemas s ficaram realmente confiveis quando foram desenvolvidos os mecanismos de proteo de memria disponibilizados para a terceira gerao de sistemas. Aps o desenvolvimento do CTSS, o MIT, o Bell Labs e a General Electric (a maior fabricante de computadores da poca) decidiram trabalhar no projeto de um "computador utilitrio", uma mquina que suportasse centenas de usurios simultaneamente, em regime de compartilhamento de tempo. Os projetistas do sistema se inspiraram no modelo de distribuio de energia eltrica-quando voc precisa de eletricidade, basta ligar um fio na tomada e, dentro de certos limites, voc ter tanta eletricidade quanto queira. Os projetistas de tal sistema, denominado MULTICS (MULTiplexed Information and Computing Service), visualizaram uma mquina imensa, fornecendo poder computacional para toda a populao de Boston. Nessa poca, a idia de que mquinas to poderosas quanto o topo da linha da General Electric na poca, o GE-645, seriam vendidas por poucos milhares de dlares somente 20 anos depois, era pura fico cientfica e no foi considerada no projeto do MULTICS. Os parmetros que foram tomados como base no projeto mudaram rapidamente com a evoluo da tecnologia e com o desenvolvimento das tcnicas de integrao de circuitos, levando-o ao fracasso comercial. Apesar disto, o MULTICS introduziu muitas idias excelentes disciplina de projeto de sistemas operacionais, mas sua construo revelou-se bastante complicada. O Bell Labs abandonou o projeto e a General Electric saiu completamente do negcio de computadores. O MULTICS chegou a ser aproveitado em um ambiente de produo no15

prprio MIT e em alguns outros lugares, porm o conceito decomputador utilitrio redundou num completo fracasso. Deve ser observado que o MULTICS teve uma tremenda influncia nos sistemas que foram desenvolvidos depois dele, conforme descrito por Corbato etal., 1972; Corbato and Vyssotsky, 1965; Daley and Dennis,

1968; Organick, 1972; Saltzer, 1974. Um outro fato notvel ocorrido durante a terceira gerao de sistemas foi o fenomenal crescimento experimentado pelos minicomputadores, iniciado com o DEC PDP-1, lanado em 1961. O PDP-1 tinha somente 4K palavras de 18 bits, mas custava a apurar 120.000 dlares (menos de 5 por cento do preo de um 7094), e vendeu mais que chuchu na feira. Para alguns tipos de aplicaes no numricas, sua performance era muitas vezes to boa quanto a do 7094. Nascia a um ovo conceito de mquina que teve como sucessores toda a srie de PDPs, cujo ponto culminante foi o PDP-11, que ao contrrio das mquinas IBM no guardavam compatibilidade entre si. Um dos cientistas do Bell Labs que trabalhou no projeto MULTICS, Ken Thompson, encontrou um pequeno PDP-7 que algum estava usando e escreveu para ele uma verso monousurio do MULTICS. Este trabalho foi o incio do projeto que resultou no desenvolvimento do sistema operacional UNIX, que hoje domina o mercado dos sistemas para minicomputadores e estaces de trabalho. O tempo de preparao de um job era um problema real. Durante o tempo em que fitas eram montadas ou o programador estava operando o console, a UCP (Unidade Central de Processamento) ficava ociosa. Vale lembrar que no passado muitos poucos computadores estavam disponveis e eram muito caros (milhes de dlares). Alm disso, os custos operacionais com energia, refrigerao, programadores, etc., tornava ainda mais cara sua manuteno. Por isso, tempo de processamento tinha muito valor, e os proprietrios dos computadores os queriam ocupados o mximo do tempo possvel. O computador precisava ter um alta utilizao para que o investimento fosse compensado. Uma primeira soluo foi contratar um profissional que operasse o computador. O programador no precisava mais operar a mquina, e assim que um job terminasse, o operador podia iniciar o prximo; no existia a ociosidade de tempo devido reserva de tempo de computador no utilizada. J que o operador tinha mais experincia com a montagem de fitas, o tempo de preparao foi reduzido. O usurio apenas fornecia cartes ou fitas perfuradas contendo o programa, e instrues necessrias para sua execuo. Caso erros ocorressem durante a execuo do programa, o operador emitia uma listagem dos contedos da memria e registradores para que o programador pudesse depurar seu programa. Em seguida o prximo job era posto em execuo, e assim por diante. Alm disso, para reduzir ainda mais o tempo de preparao, jobs com necessidades similares eram agrupados (batched) e16

executados em grupo pelo computador. Por exemplo, supondo que o operador tivesse recebido um job FORTRAN, um COBOL, e outro FORTRAN. Se ele os executasse nessa ordem, ele teria que preparar o job FORTRAN (carregar fitas de compilador, etc.), ento o COBOL, e novamente o FORTRAN. Se ele executasse os dois jobs FORTRAN como um grupo ele prepararia o ambiente FORTRAN apenas uma vez economizando tempo de preparao. Esta abordagem marcou uma poca, onde o processamento em batch (lotes) definiu uma forma de utilizao do computador: os usurios preparavam seus programas e dados, entregavam-nos ao operador do computador, que os agrupava segundo suas necessidades e os executava, produzindo as sadas para serem devolvidas aos respectivos programadores. Mesmo assim, quando um job parava, o operador teria que notar o fato observando no console, determinar porque o programa parou (trmino normal ou anormal), listar contedos de memria se necessrio e ento carregar a leitora de cartes ou de fita de papel com o prximo job e inicializar o computador novamente. Durante a transio entre os jobs, novamente a UCP ficava ociosa. Para resolver este problema, foi desenvolvido um seqenciador automtico de jobs, que consistia em um primeiro sistema operacional rudimentar. Sua funo era controlar a transferncia automtica de um job para outro. Este programa foi implementado sob a forma de um monitor residente, sempre presente na memria da mquina para este fim. Assim que o computador era ligado, o monitor residente era chamado, e transferia o controle para um programa. Quando o programa terminava, ele retornava o controle para o monitor residente, que ia para o prximo programa. Assim, o monitor residente fornecia uma seqncia automtica entre programas e jobs. Para que o monitor residente pudesse saber qual programa deveria ser executado e de que forma, cartes de controle foram introduzidos, de maneira muito semelhante s instrues que os operadores recebiam dos programadores para execuo de seus programas. Assim, alm do programas e dos dados para um job, cartes especiais de controle eram introduzidos entre os cartes de programa e dados do job a executar, como por exemplo: $JOB - Primeiro carto, indicando o incio de um job; $FTN - Executar o compilador FORTRAN; $LOAD - Carregar o programa compilado; $RUN - Executar o programa carregado; $END - Fim do job. Os cartes de incio e fim de job eram geralmente utilizados para contabilizar o tempo de uso da mquina, para que seu tempo de processamento pudesse ser cobrado do usurio. Por isso, s vezes17

incluam parmetros indicando o usurio do job, nome do job, etc. Para distinguir cartes de controle dos demais cartes eranecessrio identific-los com um caractere ou um padro especial no carto. Em nosso exemplo, o smbolo do dlar ($) foi utilizado para

este fim. A linguagem JCL (Job Control Language) da IBM usava duas barras (//) nas primeiras duas colunas. A figura 1.5 ilustra este cenrio.

$ENDdados do programa

$RUN $LOADpgm. a ser compilado

$FTN $JOB

Figura 1.5 - Deck de cartes de um job Um monitor residente tem vrias partes identificveis. Umadelas o interpretador de cartes de controle, responsvel pela

leitura e extrao das instrues dos cartes no instante da execuo. O interpretador de cartes de controle chama um carregador em intervalos para carregar programas do sistema e programas de aplicao para a memria. Dessa forma, um carregador (loader) uma parte do monitor residente. Ambos ointerpretador de cartes de controle e o carregador precisam

executar (E/S), assim o monitor residente tem um grupo de drivers de dispositivo para os dispositivos de do sistema. Freqentemente, os programas de aplicao e do sistema esto ligados (linked) aos mesmos drivers de dispositivo, fornecendo continuidade na sua operao, bem como armazenando espao de memria e tempo de programao. Um esquema de um monitor residente mostrado na figura 1.6 Carregador Seqenciador automtico de jobs Interpretador dos cartes de controle rea do programa do usurio

Monitor Residente

Figura 1.6 - Modelo de memria de um monitor residente18

Sistemas batch utilizando este mtodo funcionavam razoavelmente bem. O monitor residente fornece seqenciamento automtico dos jobs conforme a indicao dos cartes de controle. Quando um carto de controle indica a execuo de um programa, o monitor carrega o programa para a memria e transfere o controle para o mesmo. Quando o programa termina, ele retorna o controle para o monitor, que l o prximo carto de controle, carrega o programa apropriado e assim por diante. Este ciclo repetido at que todos os cartes de controle sejam interpretados para o job. Ento o monitor continua automaticamente com o prximo job. 1.1.3.1 Operao Off-Line

O uso de sistemas batch com seqenciamento automtico de jobs aumentou a performance do sistema. Entretanto, ainda assim a UCP ficava freqentemente ociosa, devido baixssima velocidade dos dispositivos mecnicos em relao aos eletrnicos. Os dispositivos de E/S mais lentos podem significar que a UCP fica freqentemente esperando por E/S. Como um exemplo, um montador ou compilador pode ser capaz de processar 300 ou mais cartes por segundo. Uma leitora de cartes mais rpida, por outro lado, pode ser capaz de ler apenas 1200 cartes por minuto (20 cartes por segundo). Isto significa que montar um programa com 1200 cartes precisa de apenas 4 segundos de UCP, mas 60 segundos para ser lido. Dessa forma, a UCP fica ociosa por 56 dos 60 segundos, ou 93.3% do tempo. A utilizao de UCP resultante de apenas 6.7%. O processo similar para operaes de sada. O problema que, enquanto uma operao de E/S est acontecendo, a UCP est ociosa, esperando que o E/S termine; enquanto a UCP est executando, os dispositivos de E/S esto ociosos. Uma soluo simples era substituir as lentas leitoras de carto (dispositivos de entrada) e impressoras de linha (dispositivos de sada) por unidades de fita magntica. A maioria dos sistemas no final dos anos 50 e comeo dos anos 60 eram sistemas batch cujos jobs eram lidos de leitoras de carto e escritos em impressoras de linha ou perfuradoras de cartes. Ao invs de a UCP ler diretamente os cartes, os cartes eram primeiro copiados para uma fita magntica. Quando a fita estava suficientemente cheia ela era transportada para o computador. Duas abordagens para esta soluo (operao off-line) foram usadas. Dispositivos especficos (leitoras de carto, impressoras de linha) foram desenvolvidos para provocar sada ou entrada direta de fitas magnticas. A outra abordagem foi dedicar um pequeno computador para a tarefa de copiar de e para a fita. Opequeno computador foi um satlite do computador principal.

Processamento satlite foi um dos primeiros casos de mltiplos sistemas de computao trabalhando em conjunto para aumentar a performance.19

A principal vantagem da operao

off-line foi de que o

computador principal no estava mais restrito pela velocidade das leitoras de carto e impressoras de linha, e sim pela velocidade das unidades de fita magntica mais rpidas. Essa tcnica de usar fitas magnticas para todo o E/S podia ser aplicada com qualquer unidade

de equipamento de registro (leitoras e perfuradoras de carto, leitoras e perfuradoras de fitas de papel, impressoras). Alm disso, nenhuma modificao precisa ser feita para adaptar programas de aplicao da operao direta para off-line. Considere um programa que executa em um sistema com uma leitora de cartes acoplada. Quando ele quer um carto, ele chama o driver de dispositivo da leitora de carto no monitor residente. Se a operao de carto est em modo off-line, apenas o driver de dispositivo deve ser modificado. Quando um programa precisa de um carto de entrada, ele chama a mesma rotina de sistema como antes. Entretanto, agora o cdigo para aquela rotina no o driver da leitora de cartes, mas uma chamada para o driver da fita magntica. O programa de aplicao recebe a mesma imagem do carto em ambos os casos. Essa habilidade de executar um programa com dispositivos de E/S diferentes chamada independncia de dispositivo. Independncia de dispositivo torna-se possvel pela existncia de um sistema operacional que determina qual o dispositivo que um programa realmente usa quando faz o pedido de E/S. Programas so escritos para usar dispositivos de E/S lgicos. Cartes de controle (ou outros comandos) indicam como os dispositivos lgicos deveriam ser mapeados em dispositivos fsicos. O ganho real da operao off-line vem da possibilidade de usar mltiplos sistemas leitura-para-fita e fita-para-impressora para uma mesma UCP. Se a UCP pode processar com o dobro da velocidade da leitora, ento duas leitoras trabalhando simultaneamente podem produzir fita suficiente para manter a UCP ocupada. Por outro lado, agora h um atraso mais longo para conseguir executar um job em particular. Ele deve ser lido antes para a fita. Existe o atraso at que jobs suficientes sejam lidos para a fita para preench-la. A fita deve ser ento rebobinada, descarregada, manualmente carregada para a UCP e montada em um drive de fita livre. Alm disso, jobs similares podem ser agrupados em uma fita antes de serem levados para o computador, fazendo com que s vezes um job tenha que esperar seu agrupamento com outros jobs similares em uma fita at que possa ser levado para a UCP. 1.1.4. A Quarta Gerao: Computadores Pessoais Com o desenvolvimento da integrao de circuitos em grande escala (LSI), apareceram chips com milhares de transitores encapsulados em um centmetro quadrado de silcio, nascendo da a idia do computador pessoal. Em termos de arquitetura, os computadores20

pessoais no eram diferentes dos minicomputadores da classe do PDP-1 1. A grande diferena estava no preo. Da mesma forma que os minicomputadores tornaram possvel que um departamento de uma empresa ou de uma universidade adquirisse seu prprio computador, o chip microprocessador tornou isto possvel para pessoas fsicas. Atualmente, os mais poderosos computadores pessoais so denominados estaes de trabalho (workstations). Tais mquinas so usadas nas mais diferentes atividades e usualmente esto conectadas a uma rede pblica ou privada, que permite a troca de informaes entre todas as mquinas ligadas a ela. A grande disponibilidade de poder computacional, levou ao crescimento de uma indstria voltada para a produo de software para estas mquinas. A maioria destes softwares "ameno ao usurio" (user-friendly), significando que eles so voltados para pessoas que no tm nenhum conhecimento de computadores, e mais que isto, no tm nenhuma vontade de aprender nada sobre este assunto. Certamente esta foi uma mudana grande na filosofia de desenvolvimento dos sistemas operacionais. Basta lembrar que a linguagem de controle do OS/360 era to complexa, que diversos livros foram escritos sobre o assunto (por exemplo, Cadow, 1970). Atualmente, dois sistemas operacionais vm dominando o mercado de computadores pessoais e de estaes de trabalho: o Ms-Dos da Microsoft e o UNIX. O UNIX lder no mercado de sistemas para mquinas que no foram desenvolvidas com processadores da lNTEL , especialmente entre aquelas projetadas com os poderosos processadores RISC. Tais mquinas tm usualmente o poder computacional de um minicomputador, apesar de serem mquinas dedicadas a um nico usurio, sendo, portanto, lgico que elas estejam equipadas com um sistema operacional desenvolvido inicialmente para rodar em minicomputadores, como o caso do UNIX. Um desenvolvimento interessante que comeou a tomar corpo em meados dos anos 80 foi o dos sistemas operacionais para redes e o dos sistemas operacionais distribudos. Em uma rede de computadores, os usurios esto conscientes da existncia de um conjunto de mquinas conectadas rede, podendo portanto ligar-se a mquinas remotas e solicitar servios das mesmas. Cada uma destas mquinas roda seu prprio sistema operacional e tem seu prprio usurio (ou usurios). Em contraste, um sistema distribudo faz com que um conjunto de mquinas interligadas aparea para seus usurios como se fosse uma nica mquina com um s processador. Em tais sistemas, os usurios no tomam conhecimento de onde seus programas esto sendo processados ou mesmo onde seus arquivos esto armazenados, pois tudo isto manipulado automtica e eficientemente pelo sistema operacional. Os sistemas operacionais de rede no diferem fundamentalmente daqueles usados em mquinas monoprocessadores. Obviamente, eles precisam de uma interface controladora de rede e de um software21

especfico para gerenciar tal interface, alm de programas quepermitam a ligao de usurios a mquinas remotas e seu acesso a arquivos tambm remotos. Tais caractersticas no chegam a alterar

a estrutura bsica do sistema operacional usado para mquinas com um nico processador. J os sistemas operacionais distribudos precisam de mais do que a simples adio de poucas linhas de cdigo a um sistema usado em mquinas monoprocessadores, pois os sistemas ditos distribudosdiferem dos centralizados em pontos bastante crticos. Por exemplo,

os sistemas distribudos permitem que programas rodem em vrios processadores ao mesmo tempo, necessitando portanto de algoritmos de escalonamento de processador bem mais elaborados, de forma a otimizar o grau de paralelismo disponvel no sistema. Ainda no caso dos sistemas distribudos, os retardos de comunicao na rede podem vir a fazer com que algoritmos do sistema operacional venham a rodar com informaes incompletas, desatualizadas ou at incorretas. Tal situao difere substancialmente dos sistemas com um nico processador nos quais o sistema operacional tem o domnio completo e total do estado de todos os componentes do sistema.

1.1.4.1

Buferizao

Processamento off-line permite a sobreposio de operaes de UCP e E/S pela execuo dessas duas aes em duas mquinas independentes. Se desejamos atingir tal sobreposio em uma nicamquina, comandos devem ser colocados entre os dispositivos e a

UCP para permitir uma separao similar de execuo. Tambm, uma arquitetura adequada deve ser desenvolvida para permitir buferizao. Buferizao o mtodo de sobrepor E/S de um job com sua prpria computao. A idia muito simples. Depois de os dados terem sido lidos e a UCP estar pronta para iniciar a operao nos mesmos, o dispositivo de entrada instrudo para iniciar a prxima entrada imediatamente. Dessa forma, a UCP e o dispositivo de entrada de dados ficam ambos ocupados. Com sorte, no instante em que a UCP est pronta para o prximo item de dado (registro), o dispositivo de entrada ter terminado de l-lo. A UCP pode ento comear o processamento dos novos dados lidos, enquanto o dispositivo de entrada comea a ler os dados seguintes. De forma semelhante isto pode ser feito para a sada. Nesse caso, a UCP cria dados que so colocados em um buffer at que o dispositivo de sada possa receb-lo. Na prtica, raro UCP e dispositivos de E/S estarem ocupados o tempo todo, j que ou a UCP ou o dispositivo de E/S termina primeiro. Se a UCP termina primeiro, ela deve esperar at que o prximo registro seja lido para a memria. importante observar que a UCP no fica o tempo todo ociosa, no mximo o tempo que ficaria se no estivesse sendo utilizada buferizao.22

Por outro lado, se o dispositivo de entrada de dados terminaprimeiro, ele pode tanto esperar como continuar com a leitura do

prximo registro. Neste caso ele s dever parar quando osestiverem cheios. Para que o dispositivo de entrada continue sempre

buffers

trabalhando, normalmente os buffers costumam ter tamanho suficiente para mant-lo sempre ocupado. A buferizao geralmente uma funo do sistema operacional. O monitor residente ou os drivers de dispositivo incluem buffers do sistema de E/S para cada dispositivo de E/S. Assim, chamadas ao driver de dispositivo pelos programas de aplicao normalmente causam apenas uma transferncia do buffer para o sistema. Apesar da buferizao ser de alguma ajuda, ela raramente suficiente para manter a UCP sempre ocupada, j que os dispositivos de E/S costumam ser muito lentos em relao UCP. 1.1.4.2 Spooling

Com o passar do tempo, dispositivos baseados em discos tornaram-se comuns e facilitaram muito a operao off-line dos sistemas. A vantagem que em um disco era possvel escrever e ler a qualquer momento, enquanto que uma fita precisava ser escrita at o fim para ento ser rebobinada e lida. Em um sistema de disco, cartes so diretamente lidos da leitora de cartes para o disco. Quando um job executado, o sistema operacional satisfaz seus pedidos por entrada da leitora de cartes pela leitura do disco. Da mesma forma, quando um job pede a impresso de uma linha para a impressora, esta copiada em um buffer do sistema que escrito para o disco. Quando a impressora fica disponvel, a sada realmente impressa. Esta forma de processamento chamada de spooling (spool = Simultaneous Peripheral Operation On-Line). Spooling utiliza um disco como um buffer muito grande para ler tanto quanto possa dos dispositivos de entrada e para armazenar arquivos de sada at que os dispositivos de sada estejam aptos para receb-los. Esta tcnica tambm muito utilizada para comunicao com dispositivos remotos. A UCP envia os dados atravs dos canais de comunicao para uma impressora remota (ou aceita um job completo de entrada de uma leitora de cartes remota). O processamento remoto feito em sua prpria velocidade sem a interveno da UCP. A UCP apenas precisa ser notificada quando o processamento termina, para que possa passar para o prximo conjunto de dados do spool. A diferena entre buferizao e spooling que enquanto a buferizao sobrepe o processamento de um job com seu prprio E/S, o spooling sobrepe o E/S de um job com o processamento de outros jobs. Assim, a tcnica spooling mais vantajosa do que a buferizao. O nico efeito colateral a necessidade de algum espao em disco para o spool, alm de algumas tabelas em memria.23

Outra vantagem do spooling vem do fato de que a tcnicafornece uma estrutura de dados muito importante, que a lista de jobs. A performance pode ser aumentada, pois os vrios jobs

armazenados no disco podem ser processados em qualquer ordem que o sistema operacional decidir, buscando o aumento de utilizao da UCP (escalonamento de jobs). Quando jobs so lidos diretamente de cartes ou fita magntica, no possvel executar os jobs fora de ordem. 1.1.4.3 Multiprogramao

O aspecto mais importante do escalonamento de jobs a habilidade de multiprogramao. As tcnicas de operao off-line, buferizao e spooling tm suas limitaes na sobreposio de E/S. Em geral, um nico usurio no pode manter tanto UCP e dispositivos de E/S ocupados o tempo todo. A multiprogramao aumenta a utilizao de UCP, pois organiza os vrios jobs de forma que a UCP sempre tenha algo para processar. A multiprogramao funciona da seguinte maneira: inicialmente o sistema operacional escolhe um dos jobs da lista de jobs e comea a execut-lo. Eventualmente, o job deve esperar por alguma tarefa, como a montagem de uma fita, um comando digitado pelo teclado, ou mesmo o trmino de uma operao de E/S. Em um sistema monoprogramado a UCP permaneceria ociosa. Por outro lado, em um sistema multiprogramado, o sistema operacional simplesmente troca e executa outro job. Quando este novo job precisa esperar, a UCP troca para outro job e assim por diante. Em um dado momento, o primeiro job no precisa mais esperar e ganha a UCP. Assim, sempre que existirem jobs a serem processados, a UCP no ficar ociosa. Sistemas operacionais multiprogramados so bastante sofisticados. Para que vrios jobs estejam prontos para executar, necessrio que todos estejam presentes na memria RAM da mquina simultaneamente. Isto acarreta em um gerenciamento de memria para os vrios jobs. Alm disso, se vrios jobs esto prontos para executar ao mesmo tempo, o sistema deve escolher qual deles deve ser executado primeiro. A poltica de deciso de qual job ser executado chamada de escalonamento de UCP. Por fim, o sistema operacional deve garantir que vrios jobs rodando concorrentemente no afetem uns aos outros em todas as fases do sistema operacional, incluindo escalonamento de processos, armazenamento de disco e gerenciamento de memria. 1.1.4.4 Tempo Compartilhado

O conceito de sistemas de tempo compartilhado, tambm chamados de multitarefa, uma extenso lgica de multiprogramao. Neste ambiente, mltiplos jobs so executados simultaneamente, sendo que a UCP atende cada job por um pequeno tempo, um a um em seqncia. Os tempos dedicados para cada job24

so pequenos o suficiente para que os usurios consigam interagircom cada programa sem que percebam que existem outros programas rodando. Quando muitos programas esto sendo executados, a impresso que o usurio tem de que o computador

est lento, pois a UCP tem mais jobs para atender, e portantoaumenta o tempo entre os sucessivos atendimentos para um

determinado job. fcil de entender como funcionam sistemas de tempo

compartilhado quando comparados com sistemas batch. Neste tipo de sistema operacional, um fluxo de jobs separados lido (de uma leitora de cartes, por exemplo), incluindo seus cartes de controle que predefinem o que faz o job. Quando o job termina, seu resultado normalmente impresso, e o prximo job posto em execuo. A principal caracterstica (e desvantagem) deste sistema a falta de interao entre o usurio e o programa em execuo no job. O usurio precisa entregar ao operador o programa que ele deseja executar, incluindo seus dados de entrada. Algum tempo depois (podendo demorar minutos, horas ou mesmo dias), a sada do job retornada. Este tempo entre a submisso do job e seu trmino, chamado de tempo de turnaround, vai depender da quantidade de processamento necessria, tempo de preparao necessrio, e da quantidade de jobs que estavam na fila antes dele ser submetido ao processamento. Existem algumas dificuldades com o sistema batch do ponto de vista do programador ou do usurio. J que o usurio no pode interagir com o job que est executando, o usurio deve indicar os cartes de controle para manipularem todos os resultados possveis. Em um job de mltiplos passos, passos subseqentes podem depender do resultado dos anteriores. A execuo de um programa, por exemplo, pode depender do sucesso da compilao. Pode ser difcil definir completamente o que fazer em todos os casos. Outra dificuldade em um sistema batch que programas devem ser depurados estaticamente, a partir de uma listagem. Um programador no pode modificar um programa quando ele est sendo executado para estudar o seu comportamento, como hoje possvel na maioria dos ambientes de programao. Um sistema de computao interativo (chamado de handson), fornece comunicao on-line entre o usurio e o sistema. O usurio d instrues ao sistema operacional ou para um programa diretamente, e recebe uma resposta imediata. Usualmente, umteclado usado para a entrada de dados e uma impressora ou

monitor de vdeo para a sada de dados. Este tipo de terminal s apareceu algum tempo depois, com o barateamento de componentes eletrnicos neles utilizados. Quanto o sistema operacional termina a execuo de um comando, ele passa a aceitar outros comandos do teclado do usurio, e no mais de uma leitora de cartes. Assim o usurio fornece o comando, espera pela resposta e decide o prximo25

comandos, baseado no resultado do comando anterior. O usuriopode fazer experimentos com facilidade e pode ver resultados

imediatamente.Sistemas batch so bastante apropriados para executar jobs grandes que precisam de pouca interao. O usurio pode submeter

jobs e retornar mais tarde para buscar os resultados; no necessrio esperar seu processamento. Por outro lado, jobs interativos costumam ser compostos por vrias aes pequenas, onde os resultados de cada ao podem ser imprevisveis. O usurio submete o comando e espera pelos resultados. O tempo de resposta deve ser pequeno da ordem de segundos no mximo. Um sistema interativo usado quando necessrio um tempo de resposta pequeno. Conforme j vimos, no incio dos tempos da computao, apesar de primitivos, os sistemas eram interativos. Um novo processamento s comeava aps o operador analisar os resultados do job anterior e decidir que ao tomar. Para aumentar o uso de UCP, sistemas batch foram introduzidos, o que realmente fez com que os computadores ficassem menos tempo ociosos. Entretanto, no havia interatividade nenhuma do usurio ou programador com o sistema. Sistemas de tempo compartilhado foram desenvolvidos para fornecer o uso interativo de um sistema de computao a custos razoveis. Um sistema operacional de tempo compartilhado (timesharing) usa escalonamento de UCP e multiprogramao para fornecer a cada usurio uma pequena poro de tempo de computador. Um sistema operacional de tempo compartilhado permite que muitos usurios compartilhem o computador simultaneamente. J que cada ao ou comando em um sistema de tempo compartilhado tende a ser pequena, apenas uma pequena quantidade de tempo de UCP necessria para cada usurio. Conforme o sistema troca de um usurio para outro, cada usurio tem a impresso de ter seu prprio computador, enquanto na realidade um computador est sendo compartilhado entre muitos usurios. A idia de tempo compartilhado foi demonstrada no incio de 1960, mas j que sistemas de tempo compartilhado so mais difceis e custosos para construir (devido aos numerosos dispositivos de E/S necessrios), eles somente tornaram-se comuns at o incio dos anos 70. Conforme a popularidade destes sistemas cresceu, pesquisadores tentaram combinar os recursos de sistemas batch e de tempo compartilhado em um nico sistema operacional. Muitos sistemas que foram inicialmente projetados como sistemas batch foram modificados para criar um subsistema de tempo compartilhado. Por exemplo, o sistema batch OS/360 da IBM foi modificado para suportar a opo de tempo compartilhado (Time Sharing Option TSO). Ao mesmo tempo, maioria dos sistemas de tempo26

compartilhado foi adicionado um subsistema

batch. Hoje em dia, abatch e de

maioria dos sistemas fornecem ambos processamento

tempo compartilhado, embora seu projeto bsico e uso sejam de um ou de outro tipo. Sistemas operacionais de tempo compartilhado sosofisticados. Eles fornecem um mecanismo para execuo concorrente. Como na multiprogramao, vrios jobs deve ser mantidos simultaneamente na memria, o que requer alguma forma de gerenciamento de memria, proteo e escalonamento de UCP. Como a memria tem tamanho limitado, e em dadas situaes alguns

jobs tero que ser retirados da memria e gravados temporariamenteem disco, para que outros programas possam ser lidos do disco e

postos em execuo na memria. Quando aquele job novamente precisar de continuao em sua execuo, ele ser trazido de volta para a memria. Os primeiros sistemas operacionais para microcomputadores eram muito simples, pois o poder computacional dos primeiros micros era suficiente para atender somente a programas de um nico usurio. Alm do mais, os microcomputadores foram projetados na poca para serem utilizados no mximo por uma pessoa em um determinado momento. Com o passar dos anos, os microcomputadores ganharam poder de processamento equivalente a computadores que ocupavam salas inteiras no passado. Para aproveitar este potencial, os microcomputadores ganharam sistemas operacionais multitarefa, permitindo ao usurio executar mais de uma aplicao por vez, alm de permitir situaes desejveis como imprimir um documento enquanto utilizando o editor de textos. Este processo se chama swapping, e para que isso possa ser feito, o sistema operacional deve fornecer gerenciamento de disco, e um sistema de arquivos on-line, alm de proteo para que jobs no escrevam sobre jobs que foram colocados (swapped) em disco. Hoje, multiprogramao e sistema compartilhado so os temas centrais dos sistemas operacionais modernos. Os sistemas operacionais mais recentes para microcomputadores suportam mltiplos usurios e mltiplos programas rodando concorrentemente em tempo compartilhado. Os sistemas mais conhecidos com essas caractersticas incluem: todas as verses de UNIX para PCs (UnixWare, SCO Unix, Linux, FreeBSD, Xenix, etc); o Microsoft Windows 3.x, Windows NT, e Windows 95; e o IBM OS/2. Apesar de pouco conhecidos, existem ainda alguns sistemas operacionais para PCs que rodam programas feitos para o MS-DOS, mas so multiusurio e multitarefa, como por exemplo o VM/386 e o VirtuOS/386 (produzido por uma empresa brasileira, a Microbase).

27

1.1.4.5

Os Conceitos de Interrupo e Trap

Pode-se dizer que interrupes e traps so as foras que movimentam e dirigem os sistemas operacionais, pois um sistemaoperacional s recebe o controle da execuo quando ocorre alguma

interrupo ao trap.Uma interrupo um sinal de hardware que faz com que o

processador sinalizado interrompa a execuo do programa que vinha executando (guardando informaes para poder continuar, mais tarde, a execuo desse programa) e passe a executar uma rotina especfica que trata da interrupo. Um trap uma instruo especial que, quando executada pelo processador, origina as mesmas aes ocasionadas por uma interrupo (salvamento de informaes para poder continuar, maistarde, a execuo do programa e desvio para uma rotina especfica

que trata do trap). Pode-se dizer que um ocasionada por software.

trap uma interrupo

Interrupes podem ser originadas pelos vrios dispositivos perifricos (terminais, discos, impressoras, etc.), pelo operador (atravs das teclas do console de operao) ou pelo relgio do sistema. O relgio (timer) um dispositivo de hardware que decrementa automaticamente o contedo de um registrador ou posio de memria, com uma freqncia constante, e interrompe a UCP quando o valor decrementado atinge zero. O sistema operacional garante que ocorrer pelo menos uma interrupo (e ele voltar a trabalhar) dentro de um intervalo de tempo t, colocando no relgio um valor que demore t unidades de tempo para ser decrementado at zero. Esta atribuio de valor ao relgio feita imediatamente antes do sistema operacional entregar a UCP para um programa de usurio. Uma interrupo no afeta a instruo que est sendo executada pela UCP no momento em que ela ocorre: a UCP detecta interrupes apenas aps o trmino da execuo de uma instruo (e antes do incio da execuo da instruo seguinte). Os computadores possuem instrues para mascarar (desabilitar, inibir) o sistema de interrupes. Enquanto as interrupes esto mascaradas elas podem ocorrer, mas no so sentidas pelo processador. Neste caso, as interrupes ficam pendentes (enfileiradas) e s sero sentidas quando uma instruo que desmascara as mesmas executada. Conforme j foi dito, os traps so instrues especiais que, quando executadas, originam aes idnticas s que ocorrem por ocasio de uma interrupo. Pode-se dizer que um trap uma interrupo prevista, programada no sistema pelo prprio programador. Uma interrupo, por outro lado, completamente imprevisvel, ocorrendo em pontos que no podem ser prdeterminados.28

Os traps tm a finalidade de permitir aos programas dosusurios a passagem do controle da execuo para o sistema operacional. Por esse motivo tambm so denominados chamadas

do supervisor ou chamadas do sistema (supervisor call ou system call). Os traps so necessrios principalmente nos computadores que possuem instrues protegidas (privilegiadas). Nesses computadores o registrador (palavra) de estado do processador possui um bit para indicar se a UCP est em estado privilegiado (estado de sistema, estado de supervisor, estado mestre) ou no privilegiado (estado de usurio, estado de programa, estado escravo). Sempre que ocorre uma interrupo ou trap, o novo valor carregado no registrador do estado do processador, indica estado privilegiado de execuo. No estado de supervisor qualquer instruo pode ser executada e no estado de usurio apenas as instrues no protegidas podem ser executadas. Exemplos de instrues protegidas so instrues para desabilitar e habilitar interrupes e instrues para realizar operaes de E/S. Operaes que envolvam o uso de instrues protegidas s podem ser executadas pelo sistema operacional, portanto. Quando um programa de usurio necessita executar alguma dessas operaes, o mesmo deve executar um trap, passando como argumento o nmero que identifica a operao que est sendo requerida.

29

2

PROCESSOS

O conceito de processo certamente o conceito mais importante no estudo de sistemas operacionais. Para facilitar o entendimento deste conceito, considere-se um computador funcionando em multiprogramao (isto , tendo vrios programas simultaneamente ativos na memria). Cada programa em execuo corresponde a um procedimento (seqncia de instrues) e um conjunto de dados (variveis utilizadas pelo programa). conveniente ter-se instrues separadas dos dados, pois isso possibilita o compartilhamento do cdigo do procedimento por vrios programas em execuo (neste caso diz-se que o procedimento ereentrante ou puro). Se cada programa em execuo possui uma

pilha prpria, ento os dados podem ser criados (alocados) na prpria pilha do programa. Alm das instrues e dados, cada programa em execuo possui uma rea de memria correspondente para armazenar os valores dos registradores da UCP, quando o programa, por algum motivo, no estiver sendo executado. Essa rea de memria conhecida como registro descritor (ou bloco descritor, bloco de contexto, registro de estado, vetor de estado) e, alm dos valores dos registradores da UCP, contm outras informaes. Assim, em um determinado sistema, cada programa em execuo constitui um processo. Portanto, podemos definir processo como sendo um programa em execuo, o qual constitudo por uma seqncia de instrues, um conjunto de dados e um registro descritor. Num ambiente de multiprogramao, quando existe apenas um processador na instalao, cada processo executado um pouco de cada vez, de forma intercalada. O sistema operacional aloca a UCP um pouco para cada processo, em uma ordem que no previsvel,em geral, pois depende de fatores externos aos processos, que

variam no tempo (carga do sistema, por exemplo). Um processo aps receber a UCP, s perde o controle da execuo quando ocorre uma interrupo ou quando ele executa um trap, requerendo algum servio do sistema operacional. As interrupes so transparentes aos processos, pois o efeitos das mesmas apenas parar, temporariamente, a execuo de um processo, o qual continuar sendo executado, mais tarde, como se nada tivesse acontecido. Um trap, por outro lado, completamente diferente, pois bloqueia o processo at que o servio requerido pelo mesmo, ao sistema operacional, seja realizado. Deve ser observado que um processo uma entidade completamente definida por si s, cujas operaes (instrues executadas) se desenvolvem no tempo, em uma ordem que funo30

exclusiva dos valores iniciais de suas variveis e dos dados lidos durante a execuo.Em um sistema com multiprocessamento (com mais de uma UCP), a nica diferena em relao ao ambiente monoprocessado que o sistema operacional passa a dispor de mais processadores para

alocar os processos, e neste caso tem-se realmente a execuo simultnea de vrios processos. Um sistema monoprocessado executando de forma intercalada N processos pode ser visto como se possusse N processadores virtuais, um para cada processo em execuo. Cada processador virtual teria 1/N da velocidade do processador real (desprezando-se o overhead existente na implementao da multiprogramao). O overhead de um sistema operacional o tempo que o mesmo perde na execuo de suas prprias funes, como por exemplo o tempo perdido para fazer a multiplexao da UCP entre os processos. o tempo durante o qual o sistema no est produzindo trabalho til para qualquer usurio. Tanto no paralelismo fsico (real, com vrias UCP) como no lgico (virtual, uma UCP compartilhada), as velocidades relativas com que os processos acessaro dados compartilhados no podem ser previstas. Isto implica em mecanismos de sincronizao entre processos, como vimos anteriormente com as instrues parbegin/parend. Processos paralelos so denominados concorrentes ou assncronos e, de acordo com o tipo de interao existente entre eles, podem ser classificados como disjuntos (no interativos), quando operam sobre conjuntos distintos de dados, ou interativos, quando tm acesso a dados comuns. Processos interativos podem ser competitivos, se competirem por recursos, e/ou cooperantes, se trocarem informaes entre si. No caso de computaes realizadas por processos interativos, como a ordem das operaes sobre as variveis compartilhadas pode variar no tempo (pois as velocidades relativas dos processos dependem de fatores externos que variam no tempo), o resultado da computao pode no depender somente dos valores iniciais das variveis e dos dados de entrada. Quando o resultado de uma computao varia de acordo com as velocidades relativas dos processos diz-se que existe uma condio de corrida (race condition). necessrio evitar condies de corrida para garantir que o resultado de uma computao no varie entre uma execuo e outra. Condies de corrida resultam em computaes paralelas errneas, pois cada vez que o programa for executado (com os mesmos dados) resultados diferentes podero ser obtidos. A programao de computaes paralelas exige mecanismos de sincronizao entre processos, e por isso sua programao e depurao bem mais difcil do que em programas tradicionais. A maioria das linguagens de programao existentes no31

permite a programao de computaes paralelas, pois de seusprogramas origina um nico processo durante a sua execuo. Tais linguagens so denominadas seqenciais. Linguagens que permitem a construo de programas que originam vrios processos para serem executados em paralelo so denominadas linguagens de programao concorrente. Exemplos deste tipo de linguagem so:

Pascal Concorrente, Modula 2, Ada e outras. A programao concorrente, alm de ser intelectualmente atraente e ser essencial ao projeto de sistemas operacionais, tambm tem aplicaes na construo de diversos outros tipos de sistema importantes. Qualquer sistema que deva atender a requisies de servio que possam ocorrer de forma imprevisvel pode ser organizado, convenientemente, para permitir que cada tipo de servio seja realizado por um dos processos do sistema. Dessa maneira, diversos servios podero ser executados simultaneamente e a utilizao dos recursos computacionais ser, certamente, mais econmica e eficiente. Exemplos de aplicaes deste tipo so sistemas para controle on-line de informaes (contas bancrias, estoques, etc) e controle de processos externos (processos industriais, processos qumicos, rotas de foguetes, etc). Os processos durante suas execues requerem operaes de E/S que so executadas em dispositivos muito lentos que a UCP, pois os dispositivos perifricos possuem componentes mecnicos, que funcionam a velocidades muito inferiores dos dispositivos eletrnicos que funcionam velocidade da luz. Durante o tempo em que um processo deve ficar esperando a realizao de uma operao de E/S, a UCP pode ser entregue a outro processo. Dessa forma, a utilizao dos recursos ser mais completa e, portanto, mais econmica e mais eficiente. Se um processo passa a maior parte do tempo esperando por dispositivos de E/S, diz-se que o processo limitado por E/S (I/O-bound). Se, ao contrrio, o processo gasta a maior parte do seu tempo usando a UCP ele dito limitado por computao (compute-bound ou UCP-bound). Obviamente, processos I/O-bound devem ter prioridade sobre processos UCP-bound. Alm de uma melhor utilizao dos recursos, a multiprogramao permite que as requisies de servio dos usurios sejam atendidas com menores tempos de resposta. Por exemplo, na situao de um job pequeno e prioritrio ser submetido aps um job demorado j ter iniciado a execuo, a multiprogramao far com que o job pequeno seja executado em paralelo e termine muito antes do trmino do job longo. Os sistemas operacionais acionam os dispositivos de E/S atravs de instrues do tipo Start I/O (Iniciar E/S). Se o dispositivo uma unidade de disco, por exemplo, a instruo faz com que um bloco de setores do disco seja lido para a memria principal. Quando o dispositivo termina a operao, ele manda um sinal de interrupo32

para a UCP, indicando que est livre para realizar outra operao. Este sinal faz com que o controle da execuo v para o sistema operacional, o qual pode acionar o dispositivo para executar outra operao, antes de devolver a UCP para um processo de usurio. Durante suas execues os processos dos usurios, ocasionalmente, atravs de traps, fazem requisies ao sistema operacional (para gravar um setor de disco, por exemplo). Recebendo a requisio, o sistema operacional bloqueia o processo (deixa de dar tempo de UCP a ele) at que a operao requerida seja completada. Quando isto acontece o processo desbloqueado e volta a competir pela UCP com os demais processos. Quando um processo est realmente usando a UCP, diz-se que o mesmo est no estado executando (running). Quando est esperando pelo trmino de um servio que requereu, diz-se que est no estado bloqueado (blocked). Quando o processo tem todas as condies para ser executado e s no est em execuo porque a UCP est alocada para outro processo, diz-se que o mesmo est no estado pronto (ready). O sistema operacional mantm uma lista (fila) dos processos que esto prontos, a chamada lista de processos prontos (ready list ou ready queue). O diagrama da figura 2.1 mostra como os estados de um processo podem mudar durante a execuo. executando escalonador interrupo pronto interrupo (concluso do servio) bloqueado trap

Figura 2.1 - Estados sucessivos de um processo no sistema O componente do sistema operacional que, aps oatendimento de uma interrupo ou trap, escolhe o prximo processo

a ser executado denominado escalonador de processos (scheduler) ou despachador de processos (dispatcher).Em geral, um trap faz com que o processo fique bloqueado.

Entretanto, em algumas ocasies especiais, quando o sistema operacional pode atender imediatamente a requisio de servio, o processo pode ser novamente despachado, no ocorrendo o bloqueio. Quando um job admitido no sistema, um processo correspondente criado e normalmente inserido no final da ready list. O processo se move gradualmente para a cabea da ready list, conforme os processos anteriores a ele forem sendo usados pela UCP. Quando o processo alcana a cabea da lista, e quando a33

UCP torna-se disponvel, o processo dado UCP e diz-se que foi feito uma transio do estado ready para o estado running. A transferncia da UCP para o primeiro processo da ready list chamada dispatching, e executada pelo dispatcher (ou escalonador). Este transio de estado pode ser ilustrada da seguinte forma: Dispatch(processname): ready running

Para prevenir que um processo monopolize o sistema acidentalmente ou propositadamente, o S.O. (Sistema Operacional) tem um relgio interno (interrupting clock ou interval timer) que faz com que o processo execute somente por um intervalo de tempo especfico ou quantum. Se o processo voluntariamente no libera a UCP antes de expirar seu intervalo de tempo, o interrupting clock gera uma interrupo, dando ao S.O. o controle novamente. O S.O. torna o processo corrente (running) em pronto (ready) e torna o primeiro processo da ready list em corrente. Estas transies de estado so indicadas como: TimerRunOut(processname): Dispatch(processname): running ready ready running

Se um processo corrente iniciar uma operao de I/O antes de expirar o seu quantum, o processo corrente voluntariamente liberaa UCP (isto , ele se bloqueia, ficando pendente at completar a

operao de I/O). Esta transio de estado : Block(processname): running blocked

Quando terminada a operao que fez com que o estadofique bloqueado, este passa para o estado pronto. A transio que faz

tal operao definida como: WakeUp(processname): blocked ready

Deste modo podemos definir quatro possveis estados de transio: Dispatch(processname): Block(processname): WakeUp(processname): ready running blocked running ready blocked ready TimerRunOut(processname): running

Note que somente um estado de transio inicializado pelo prprio processo a transio Block os outros trs estados de transio so inicializados por entidades externas ao processo.34

2.1

O Ncleo do Sistema Operacional (Kernel)

Todas as operaes envolvendo processos so controladas por uma poro do sistema operacional chamada de ncleo, core, ou kernel. O ncleo normalmente representa somente uma pequena poro do cdigo que em geral tratado como sendo todo o sistema operacional, mas a parte de cdigo mais intensivamente utilizada. Por essa razo, o ncleo ordinariamente reside em armazenamento primrio (memria RAM) enquanto outras pores do sistema operacional so chamadas da memria secundria quando necessrio. Uma das funes mais importantes includas no ncleo o processamento de interrupes. Em grandes sistemas multiusurio, uma constante rajada de interrupes direcionada ao processador. Respostas rpidas a essas interrupes so essenciais para manter os recursos do sistema bem utilizados, e para prover tempos de resposta aceitveis pelos usurios. O ncleo desabilita interrupes enquanto ele responde a uma interrupo; interrupes so novamente habilitadas aps o processamento de uma interrupo estar completo. Com um fluxo permanente de interrupes, possvel que o ncleo mantenha interrupes desabilitadas por um grande poro de tempo; isto pode resultar em respostas insatisfatrias para interrupes. Entretanto, ncleos so projetados para fazer o mnimo processamento possvel para cada interrupo, e ento passar o restante do processamento de uma interrupo para um processo apropriado do sistema que pode terminar de trat-las enquanto o ncleo continua apto a receber novas interrupes. Isto significa que as interrupes podem ficar habilitadas durante uma porcentagem muito maior do tempo, e o sistema torna-se mais eficiente em responder a requisies das aplicaes dos usurios. 2.1.1 Um Resumo das Funes do Ncleo

Um sistema operacional normalmente possui cdigo para executar as seguinte funes: Manipulao de interrupes; Criao e destruio de processos; Troca de contexto de processos; Desacatamento de processos; Suspenso e reanimao de processos; Sincronizao de processos; Intercomunicao entre processos; Manipulao de PCBs; Suporte a atividades de E/S;35

2.2

Suporte alocao e desalocao de armazenamento; Suporte ao sistema de arquivos; Suporte a um procedimentos; mecanismo de chamada/retorno de

Suporte a certas funes do sistema de contabilizao.

Escalonamento de Processos

At agora vimos situaes onde tnhamos dois ou mais processos que poderiam estar executando a qualquer momento. Estes processos poderiam estar executando, bloqueados, ou prontos para serem executados. Uma situao adicional, que vimos mais tarde, foi o estado suspenso. Quando um ou mais processos esto prontos para serem executados, o sistema operacional deve decidir qual deles vai ser executado primeiro. A parte do sistema operacional responsvel por essa deciso chamada escalonador, e o algoritmo usado para tal chamado de algoritmo de escalonamento. Os algoritmos de escalonamento dos primeiros sistemas, baseados em cartes perfurados e unidades de fita, era simples: ele simplesmente deveria executar o prximo job na fita ou leitora de cartes. Em sistemas multi-usurio e de tempo compartilhado, muitas vezes combinados com jobs batch em background, o algoritmo de escalonamento mais complexo. Antes de vermos os algoritmos de escalonamento, vejamos os critrios com os quais eles devem se preocupar: 1. Justia: fazer com que cada processo ganhe seu tempo justo de CPU; 2. Eficincia: manter a CPU ocupada 100% do tempo (se houver demanda); 3. Tempo de Reposta: minimizar o tempo de resposta para os usurios interativos; 4. Tempo de Turnaround: minimizar o tempo que usurios batch devem esperar pelo resultado; 5. Throughput: maximizar o nmero de jobs processados por unidade de tempo. Um pouco de anlise mostrar que alguns desses objetivos so contraditrios. Para minimizar o tempo de resposta para usurios interativos, o escalonador no deveria rodar nenhum job batch (exceto entre 3 e 6 da manh, quando os usurios interativos esto dormindo). Usurios batch no gostaro deste algoritmo, porque ele viola a regra 4.36

Uma complicao que os escalonadores devem levar emconsiderao que cada processo nico e imprevisvel. Alguns

passam a maior parte do tempo esperando por E/S de arquivos, enquanto outros utilizam a CPU por horas se tiverem chance. Quando o escalonador inicia a execuo de um processo, ele nunca sabe com certeza quanto tempo vai demorar at que o processo bloqueie, seja por E/S, seja em um semforo, seja por outro motivo. Para que um processo no execute tempo demais, praticamente todos os computadores possuem um mecanismo de relgio (clock) que causa uma interrupo periodicamente. Freqncias de 50 ou 60 Hz so comuns, mas muitas mquinas permitem que o SO especifique esta freqncia. A cada interrupo de relgio, o sistema operacional assume o controle e decide se o processo pode continuar executando ou se j ganhou tempo de CPU suficiente. Neste ltimo caso, o processo suspenso e a CPU dada a outro processo. A estratgia de permitir ao SO temporariamente suspender a execuo de processos que estejam querendo executar chamada de escalonamento preemptivo, em contraste com o mtodo execute at o fim dos antigos sistemas batch. Como vimos at agora, em sistemas preemptivos um processo pode perder a CPU a qualquer momento para outro processo, sem qualquer aviso. Isto gera condies de corrida e a necessidade de semforos, contadores de eventos, monitores, ou algum outro mtodo de comunicao interprocessos. Por outro lado, uma poltica de deixar um processo rodar enquanto desejar pode fazer com que um processo que demore uma semana para executar deixe o computador ocupado para os outros usurios durante este tempo. 2.2.1 Escalonamento FCFS ou FIFO

Talvez a disciplina de escalonamento mais simples que exista seja a First-In-First-Out - FIFO (o primeiro a entrar o primeiro a sair). Vrios autores referem-se a este algoritmo como FCFS - First-Come-First-Served (o primeiro a chegar o primeiro a ser servido). Processos so despachados de acordo com sua ordem de chegada na fila de processos prontos do sistema. Uma vez que um processo ganhe a CPU, ele roda at terminar. FIFO uma disciplina no preemptiva. Ela justa no sentido de que todos os jobs so executados, e na ordem de chegada, mas injusta no sentido que grandes jobs podem fazer pequenos jobs esperarem, e jobs sem grande importncia fazem jobs importantes esperar. FIFO oferece uma menor varincia nos tempos de resposta e portanto mais previsvel do que outros esquemas. Ele no til no escalonamento de usurios interativos porque no pode garantir bons tempos de resposta. Sua natureza essencialmente a de um sistema batch.

2.2.2

Escalonamento Round Robin (RR) Um dos mais antigos, simples, justos, e mais largamente37

utilizados dos algoritmos de escalonamento o round robin. Cadaprocesso recebe um intervalo de tempo, chamado quantum, durante o qual ele pode executar. Se o processo ainda estiver executando ao final do quantum, a CPU dada a outro processo. Se um processo bloqueou ou terminou antes do final do quantum, a troca de CPU para outro processo obviamente feita assim que o processo bloqueia ou termina. Round Robin fcil de implementar. Tudo que o escalonador tem a fazer manter uma lista de processos runnable (que desejam

executar), conforme a figura 2.2(a). Quando o quantum de um processo acaba, ele colocado no final da lista, conforme a figura 2.2(b).Processo corrente Processo corrente

Prximo processo

Prximo processo

B

F

D(a)

G

A

F

D

G(b)

A

B

Figura 2.2 - Escalonamento Round Robin. (a) Lista de processos a executar. (b) Lista de processos a executar depois de terminado o quantum deB

Assim, o algoritmo round robin semelhante ao FIFO, mas com a diferena de que preemptivo: os processos no executam at o seu final, mas sim durante um certo tempo, um por vez. Executando sucessivamente em intervalos de tempo o job a