Apostila Faina

INTRODUO AOS SISTEMAS OPERACIONAISMaurcio F. Magalhes 1 Eleri Cardozo 2 Agosto de 1992 Luis F. Faina 3

1 2

Faculdade de Engenharia Eltrica e de Computao UNICAMP Faculdade de Engenharia Eltrica e de Computao UNICAMP 3 Departamento de Informtica - UFU

Sumrio1 INTRODUO 1.1 O que um Sistema Operacional ? . . . . . . . . 1.2 Histria dos Sistemas Operacionais . . . . . . . . 1.3 Conceitos Bsicos em Sistemas Operacionais . . 1.4 O Sistema Operacional UNIX . . . . . . . . . . 1.5 Uma Viso Geral do Sistema Operacional UNIX 1.6 Arquitetura do Sistema Operacional UNIX . . . . 3 3 4 6 8 9 16 23 23 28 30 33 35 40 49 49 51 59 62 64 75 75 80 85 90 94

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

2 PROCESSOS 2.1 Introduo . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Escalonamento de Processos . . . . . . . . . . . . . . . . . 2.3 Gerenciamento de Processos no Sistema Operacional UNIX 2.4 Escalonamento de Processos no Unix . . . . . . . . . . . . 2.5 Controle de Processos no UNIX . . . . . . . . . . . . . . . 2.6 Comunicao e Sincronizao Inter-processos no UNIX . . . 3 SISTEMA DE ARQUIVOS 3.1 Interface do Sistema de Arquivos . . . . . . . 3.2 Projeto do Sistema de Arquivos . . . . . . . . 3.3 Conabilidade do Sistema de Arquivos . . . . 3.4 Desempenho do Sistema de Arquivos . . . . 3.5 O Sistema de Arquivos do UNIX (System V)

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

4 GERENCIAMENTO DE MEMRIA 4.1 Gerenciamento de Memria Sem Permuta ou Paginao . 4.2 Swapping (Permuta) . . . . . . . . . . . . . . . . . . . 4.3 Memria Virtual . . . . . . . . . . . . . . . . . . . . . . 4.4 Algoritmos de Troca de Pgina . . . . . . . . . . . . . . 4.5 Gerenciamento de Memria no UNIX . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

5 ENTRADA/SADA 101 5.1 Princpios do Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.2 Princpios do Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

1

DCA-FEEC-UNICAMP5.3 5.4 5.5

Introduo aos Sistemas Operacionais

2

Discos RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Discos Rotativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Entrada/Sada no UNIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 119 119 122 126 131

6 TPICOS ESPECIAIS 6.1 Padronizao em Sistemas Operacionais 6.2 Processos Leves (Threads) . . . . . . . 6.3 Arquitetura de Microprocessadores . . . 6.4 Intel 80386 . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Captulo 1

INTRODUOProgramas computacionais (ou software) constituem o elo entre o aparato eletrnico (ou hardware) e o ser humano. Tal elo se faz necessrio dada a discrepncia entre o tipo de informao manipulada pelo homem e pela mquina. A mquina opera com cadeias de cdigos binrios enquanto o homem opera com estruturas mais abstratas como conjuntos, arquivos, algoritmos, etc. Programas computacionais podem ser grosseiramente divididos em dois tipos: programas do sistema, que manipulam a operao do computador; programas aplicativos, que resolvem problemas para o usurio. O mais importante dos programas do sistema o sistema operacional, que controla todos os recursos do computador e proporciona a base de sustentao para a execuo de programas aplicativos.

1.1 O que um Sistema Operacional ?A maioria de usurios de computador tm alguma experincia com sistemas operacionais, mas difcil denir precisamente o que um sistema operacional. Parte do problema decorre do fato do sistema operacional realizar duas funes bsicas que, dependendo do ponto de vista abordado, uma se destaca sobre a outra. Estas funes so descritas a seguir.

1.1.1 O Sistema Operacional como uma Mquina VirtualA arquitetura (conjunto de instrues, organizao de memria, E/S e estrutura de barramento) da maioria dos computadores a nvel de linguagem de mquina primitiva e difcil de programar, especicamente para operaes de entrada e sada. prefervel para um programador trabalhar com abstraes de mais alto nvel onde detalhes de implementao das abstraes no so visveis. No caso de discos, por exemplo, uma abstrao tpica que estes armazenam uma coleo de arquivos identicados por nomes simblicos. O programa que esconde os detalhes de implementao das abstraes o sistema operacional. A abstrao apresentada ao usurio pelo sistema operacional simples e mais fcil de usar que o hardware original.

3

DCA-FEEC-UNICAMP


4

Nesta viso, a funo do sistema operacional apresentada ao usurio como uma mquina estendida ou mquina virtual que mais fcil de programar que o hardware que a suporta.

1.1.2 O Sistema Operacional como um Gerenciador de RecursosUm computador moderno composto de vrios subsistemas tais como processadores, memrias, discos, terminais, tas magnticas, interfaces de rede, impressoras, e outros dispositivos de E/S. Neste ponto de vista, o sistema operacional tem a funo de gerenciar de forma adequada estes recursos de sorte que as tarefas impostas pelos usurios sejam atendidas da forma mais rpida e convel possvel. Um exemplo tpico o compartilhamento da unidade central de processamento (CPU) entre as vrias tarefas (programas) em sistemas multiprogramados. O sistema operacional o responsvel pela distribuio de forma otimizada da CPU entre as tarefas em execuo.

1.2 Histria dos Sistemas OperacionaisOs sistemas operacionais tm evoludo com o passar dos anos. Nas prximas sees vamos apresentar de forma sucinta este desenvolvimento.

1.2.1 A Primeira Gerao (1945-1955): Vlvulas e PlugsAps muitos esforos mal sucedidos de se construir computadores digitais antes da 2a guerra mundial, em torno da metade da dcada de 1940 alguns sucessos foram obtidos na construo de mquinas de clculo empregando-se vlvulas e rels. Estas mquinas eram enormes, ocupando salas com racks que abrigavam dezenas de milhares de vlvulas (e consumiam quantidades imensas de energia). Naquela poca, um pequeno grupo de pessoas projetava, construia, programavam operava e dava manuteno em cada mquina. Toda programao era feita absolutamente em linguagem de mquina, muitas vezes interligando plugs para controlar funes bsicas da mquina. Linguagens de programao eram desconhecidas; sistemas operacionais idem. Por volta de 1950 foram introduzidos os cartes perfurados aumentando a facilidade de programao.

1.2.2 A Segunda Gerao (1955-1965): Transistores e Processamento em BatchA introduo do transistor mudou radicalmente o quadro. Computadores tornaram-se conveis e difundidos (com a fabricao em srie), sendo empregados em atividades mltiplas. Pela primeira vez, houve uma separao clara entre projetistas, construtores, operadores, programadores e pessoal de manuteno. Entretanto, dado seu custo ainda elevado, somente corporaes e universidades de porte detinham recursos e infraestrutura para empregar os computadores desta gerao. Estas mquinas eram acondicionadas em salas especiais com pessoal especializado para sua operao. Para rodar um job (programa), o programador produzia um conjunto de cartes perfurados (um carto por comando do programa), e o entregava ao operador que dava entrada do programa no computador. Quando o computador completava o trabalho, o operador devolvia os cartes com a impresso dos resultados ao programador.

DCA-FEEC-UNICAMP


5

A maioria dos computadores de 2a gerao foram utilizados para clculos cientcos e de enge nharia. Estes sistemas eram largamente programados em FORTRAN e ASSEMBLY. Sistemas operacionais tpicos 1 eram o FMS (Fortran Monitor Systems) e o IBSYS (IBMs Operating Systems).

1.2.3 A Terceira Gerao (1965-1980): Circuitos Integrados e MultiprogramaoNo incio dos anos 60, a maioria dos fabricantes de computadores tinha duas linhas distintas e incompatveis de produtos. De um lado, havia os computadores cientcos que eram usados para clculos numricos na cincia e engenharia. Do outro, haviam os computadores comerciais que executavam tarefas como ordenao de dados e impresso de relatrios, sendo utilizados principalmente por instituies nanceiras. A IBM tentou resolver este problema introduzindo a srie System/360. Esta srie consistia de mquinas com mesma arquitetura e conjunto de instrues. Desta maneira, programas escritos para uma mquina da srie executavam em todas as demais. A srie 360 foi projetada para atender tanto aplicaes cientcas quanto comerciais. No foi possvel para a IBM escrever um sistema operacional que atendesse a todos os conitos de requisitos dos usurios. O resultado foi um sistema operacional (OS/360) enorme e complexo comparado com o FMS. A despeito do tamanho e problemas, o OS/360 atendia relativamente bem s necessidades dos usurios. Ele tambm popularizou muitas tcnicas ausentes nos sistemas operacionais de 2a gerao, como por exemplo a multiprogramao. Outra caracterstica apresentada foi a capacidade de ler jobs dos cartes perfurados para os discos, assim que o programador os entregasse. Dessa maneira, assim que um job terminasse, o computador iniciava a execuo do seguinte, que j fra lido e armazenado em disco. Esta tcnica foi chamada spool (simultaneous peripherical operation on line), sendo tambm utilizada para a sada de dados. O tempo de espera dos resultados dos programas reduziu-se drasticamente com a 3a gerao de sistemas. O desejo por respostas rpidas abriu caminho para o time-sharing, uma variao da multiprogramao onde cada usurio tem um terminal on-line e todos compartilham uma nica CPU. Aps o sucesso do primeiro sistema operacional com capacidade de time-sharing (o CTSS) desenvolvido no MIT, um consrcio envolvendo o MIT, a GE e o Laboratrio Bell foi formado com o intuito de desenvolver um projeto ambicioso para a poca: um sistema operacional que suportasse centenas de usurios on-line. O MULTICS (MULTiplexed Information and Computing Service) introduziu muitas idias inovadoras, mas sua implementao mostrou-se impraticvel para a dcada de sessenta. O projeto MULTICS inuenciou os pesquisadores da Bell que viriam a desenvolver o UNIX uma dcada depois.

1.2.4 A Quarta Gerao (1980-): Computadores Pessoais e Estaes de TrabalhoCom o desenvolvimento de circuitos LSI, chips contendo milhares de transistores em um centmetro quadrado de silcio, surgiu a era dos computadores pessoais e estaes de trabalho. Em termos de arquitetura, estes no diferem dos minicomputadores da classe do PDP-11, exceto no quesito mais importante: preo. Enquanto os minicomputadores atendiam companhias e universidades, os computadores pessoais e estaes de trabalho passaram a atender usurios individualmente.1

Que eram capazes de gerenciar apenas um job por vez

DCA-FEEC-UNICAMP


6

O aumento do potencial destas mquinas criou um vastssimo mercado de software a elas dirigido. Como requisito bsico, estes produtos (tanto aplicativos quanto o prprio sistema operacional) necessitavam ser amigveis, visando usurios sem conhecimento aprofundado de computadores e sem inteno de estudar muito para utiliz-los. Esta foi certamente a maior mudana em relao ao OS/360 que era to obscuro que diversos livros foram escritos sobre ele. Dois sistemas operacionais dominaram o mercado: MS-DOS para os computadores pessoais e UNIX para as estaes de trabalho. O prximo desenvolvimento no campo dos sistemas operacionais surgiu com a tecnologia de redes de computadores: os sistemas operacionais de rede e distribudos. Sistemas operacionais de rede diferem dos sistemas operacionais para um simples processador no tocante capacidade de manipular recursos distribudos pelos processadores da rede. Por exemplo, um arquivo pode ser acessado por um usurio num processador, mesmo que sicamente o arquivo se encontre em outro processador. Sistemas operacionais de rede provem ao usurio uma interface transparente de acesso a recursos compartilhados (aplicativos, arquivos, impressoras, etc), sejam estes recursos locais ou remotos. Sistemas operacionais distribudos so muito mais complexos. Estes sistemas permitem que os processadores cooperem em servios intrnsecos de sistemas operacionais tais como escalonamento de tarefas e paginao. Por exemplo, num sistema operacional distribudo uma tarefa pode migrar durante sua execuo de um computador sobrecarregado para outro que apresente carga mais leve. Contrrio aos sistemas operacionais de rede que so largamente disponveis comercialmente, sistemas operacionais distribudos tm sua utilizao ainda restrita.

1.3 Conceitos Bsicos em Sistemas Operacionais1.3.1 ProcessosUm conceito fundamental em sistemas operacionais o de processo ou tarefa. Um processo (s vezes chamado de processo sequencial) basicamente um programa em execuo. Ele uma entidade ativa que compete por recursos (principalmente CPU) e interage com outros processos. Em um instante qualquer, um processo est em um determinado estado. Estes estados podem ser: executando (usando a CPU para executar as instrues do programa); bloqueado (aguardando recursos 2 no disponveis no momento); ativo (aguardando apenas CPU para executar). Um processo em execuo passa por um sequncia de estados ordenados no tempo. Um processo possui duas importantes propriedades: o resultado da execuo de um processo independe da velocidade com que executado; se um processo for executado novamente com os mesmos dados, ele passar precisamente pela mesma sequncia de instrues e fornecer o mesmo resultado.2

Que no CPU.

DCA-FEEC-UNICAMP


7

Estas propriedades enfatizam a natureza sequencial de um processo. O processo sequencial denido pelo resultado de suas instrues, no pela velocidade com que as instrues so executadas.

1.3.2 Sistemas Multitarefas e MultiusuriosComo j mencionado, um programa em execuo chamado de processo ou tarefa. Um sistema operacional multitarefa se distingue pela sua habilidade de suportar a execuo concorrente de processos sobre um processador nico, sem necessariamente prover elaborada forma de gerenciamento de recursos (CPU, memria, etc). Sistemas operacionais multiusurios permitem acessos simultneos ao computador atravs de dois ou mais terminais de entrada. Embora frequentemente associada com multiprogramao, multitarefa no implica necessariamente em uma operao multiusurio. Operao multiprocessos sem suporte de multiusurios pode ser encontrado em sistemas operacionais de alguns computadores pessoais avanados e em sistemas de tempo-real.

1.3.3 MultiprogramaoMultiprogramao um conceito mais geral que multitarefa e denota um sistema operacional que prov gerenciamento da totalidade de recursos tais como CPU, memria, sistema de arquivos, em adio ao suporte da execuo concorrente dos processos. Em uma mquina podemos ter o conjunto de processos sendo executados de forma serial ou de forma concorrente, ou seja, os recursos presentes na mquina podem ser alocados a um nico programa at a concluso de sua execuo ou esses recursos podem ser alocados de modo dinmico entre um nmero de programas ativos de acordo com o nvel de prioridade ou o estgio de execuo de cada um dos programas. No caso de um computador no qual o sistema operacional usado permite apenas a monoprogramao, os programas sero executados instruo-a-instruo, at que seu processamento seja concludo. Durante a sua execuo, o programa passar por diversas fases, alterando momentos em que se encontra executando ou bloqueado aguardando, por exemplo, a concluso de uma operao de entrada/sada de dados (normalmente lenta, se comparada velocidade de execuo das instrues por parte do processador). Atravs do uso da multiprogramao possvel reduzir os perodos de inatividade da CPU e consequentemente aumentar a ecincia do uso do sistema como um todo. O termo multiprogramao denota um sistema operacional o qual em adio ao suporte de mltiplos processos concorrentes, permite que instrues e dados de dois ou mais processos disjuntos estejam residentes na memria principal simultaneamente. O nvel de multiprogramao presente em um sistema pode ser classicado como integral ou serial. A multiprogramao dita integral caso mais de um processo possa se encontrar em execuo em um dado instante, enquanto que no caso da serial apenas um processo se encontra em execuo a cada instante, sendo a CPU alocada aos processos de forma intercalada ao longo do tempo. Uma vez que a maioria dos computadores apresenta apenas uma unica CPU, a multiprogramao serial encontrada com mais frequncia.

DCA-FEEC-UNICAMP


8

1.3.4 MultiprocessamentoEmbora a maioria dos computadores disponha de uma nica CPU que executa instrues uma a uma, certos projetos mais avanados incrementaram a velocidade efetiva de computao permitindo que vrias instrues fossem executadas ao mesmo tempo. Um computador com mltiplos processadores que compartilhem uma memria principal comum chamado um multiprocessador. O sistema que suporta tal congurao um sistema que suporta o multiprocessamento.

1.3.5 Interpretador de Comandos (Shell)O interpretador de comando um processo que perfaz a interface do usurio com o sistema operacional. Este processo l o teclado a espera de comandos, interpreta-os e passa seus parmetros ao sistema operacional. Servios como login/logout, manipulao de arquivos, execuo de programas, etc, so solicitados atravs do interpretador de comandos.

1.3.6 Chamadas de Sistema (System Calls)Assim como o interpretador de comandos a interface usurio/sistema operacional, as chamadas do sistema constituem a interface programas aplicativos/sistema operacional. As chamadas do sistema so funes que podem ser ligadas com os aplicativos provendo servios como: leitura do relgio interno, operaes de entrada/sada, comunicao inter-processos, etc.

1.4 O Sistema Operacional UNIXDada sua larga aceitao, o sistema operacional UNIX ser utilizado como referncia neste curso. O sistema dividido em duas partes: programas e servios: shell, mail, vi, date, etc; ncleo (kernel): Prov suporte aos programas e servios. Desenvolvido nos Laboratrios da Bell em meados da dcada de setenta, o sistema UNIX inicialmente atendia as necessidades especcas do grupo de Cincia da Computao da Bell. A razo da aceitao do UNIX explicada pelos atributos abaixo: escrito em linguagem de alto nvel, o que facilita seu transporte para diferentes plataformas; interface simples para com o usurio (shell); fornece primitivas que permitem o desenvolvimento de programas complexos a partir de programas mais simples; estrutura hierrquica de arquivos; formatao de arquivos baseada no conceito de stream (cadeia) de bytes; interfaceamento simples e consistente com os dispositivos perifricos;

DCA-FEEC-UNICAMPmultiusurio/multiprogramado;


9

esconde a arquitetura do harware, permitindo que um programa execute em mltiplas plataformas.

1.5 Uma Viso Geral do Sistema Operacional UNIX

outros programas aplicativos

man nroff cpp

sh a.out

Ncleo comp cc as Hardware

find

make

who date wc ed grep

ld vi

outros programas aplicativos

Figura 1.1: Arquitetura do sistema operacional UNIX Programas interagem com o ncleo atravs da evocao de um conjunto bem denido de chamadas de sistema. Muitos destes programas so denominados comandos. O conjunto de chamadas do sistema e os algoritmos internos que implementam estas chamadas formam o corpo do ncleo. A organizao do ambiente UNIX pode ser vista na forma de camadas conforme mostrado na gura 1.1.

1.5.1 Sistema de ArquivosO sistema de arquivos do UNIX caracterizado por: estrutura hierrquica;

DCA-FEEC-UNICAMP


10

tratamento consistente dos dados de arquivo; facilidade na criao/eliminao de arquivos; crescimento dinmico de arquivos; proteo aos dados dos arquivos; tratamento dos dispositivos perifricos como arquivos de dados. O sistema de arquivo organizado na forma de rvore conforme pode ser visto no exemplo da gura 1.2./

usr

tmp

etc

pub

dev

bin

5bin

5include 5lib

hosts passwd exportfs

emacs tex

X11

tty00

tty01

sh ed vi

Figura 1.2: Organizao hierrquica do sistema de arquivos Ainda com relao a esta gura temos: / > raiz; no-folhas > diretrios de arquivos; folhas > diretrios ou arquivos regulares ou arquivos especiais de dispositivos. A localizao de um arquivo na hierarquia pode ser na forma absoluta ou relativa. Na forma absoluta utiliza-se o caracter / no incio do endereo para indicar a raiz, enquanto no caso relativo inicia-se o caminho com o nome do arquivo que tem o diretrio atual como o ponto de partida do endereo. Os programas no ambiente UNIX no possuem nenhum conhecimento sobre o formato interno no qual o ncleo armazena os dados de arquivo. Os dados so fornecidos pelo UNIX como um stream (cadeia) de bytes, cabendo aos programas interpretarem o seu conteudo. Este tratamento estende-se tambm aos diretrios, ou seja, estes so vistos como arquivos regulares. O acesso aos arquivos controlado pelas permisses de acesso associadas a cada arquivo. No caso, temos os seguintes tipos de permisses: leitura, escrita e execuo, para os seguintes tipos de usurios: proprietrio do arquivo, grupo de usurios ou qualquer outro usurio. Uma caracterstica importante do UNIX o fato de que os programas acessam os dispositivos perifricos com a mesma sintaxe utilizada para o acesso aos arquivos regulares. Os dispositivos tambm so protegidos da mesma forma que os arquivos regulares.

DCA-FEEC-UNICAMP


11

O cdigo abaixo ilustra o programa copy que copia o contedo de um arquivo para outro. /* #include #include #include char buffer[512]; void copy(old, new) int old, new; { int count; while((count = read(old, buffer, sizeof(buffer))) > 0) write(new, buffer, count); } */

main(argc, argv) int argc; char *argv[]; { int fdold, fdnew; if(argc != 3) { printf("Uso: copy f1 f2\n"); exit(1); } /* abre arquivo para leitura */ fdold = open(argv[1], O_RDONLY); if(fdold == -1) /* erro no open */ { printf("Impossivel abrir %s\n", argv[1]); exit(1); } /* cria arquivo novo */ fdnew = creat(argv[2], 0666); if(fdnew == -1) /* erro no creat */ { printf("Impossivel criar %s\n", argv[2]);

DCA-FEEC-UNICAMPexit(1); } /* chama copy */ copy(fdold, fdnew); exit(0); } /*


12

*/

1.5.2 Ambiente de ProcessamentoUm programa um arquivo executvel, e um processo uma instncia do programa em execuo. No UNIX vrios processos podem executar simultneamente, sendo que vrias instncias de um mesmo programa podem existir ao mesmo tempo no sistema. o programa abaixo ilustra os comandos fork, execl, wait e exit (implcito) utilizados na criao e sincronizao de processos. /* #include #include #include main(argc, argv) int argc; char *argv[]; { int pid; struct timeval tv1, tv2; double t1, t2; pid = fork(); /* fork */ if(pid == 0) execl(argv[1], NULL); /* processo filho */ gettimeofday(&tv1, NULL); /* processo pai continua ... */ t1 = (double)(tv1.tv_sec) + (double)(tv1.tv_usec)/ 1000000.00; wait(NULL); /* sincroniza com o termino do filho */ gettimeofday(&tv2, NULL); t2 = (double)(tv2.tv_sec) + (double)(tv2.tv_usec)/ 1000000.00; printf("\nO tempo de execucao de %s eh: %lf\n", argv[1], (t2 - t1)); } /* */ */

DCA-FEEC-UNICAMP


13

Uma das caractersticas marcantes do UNIX que este no suporta, no nvel do ncleo, muitas das funes que fazem parte dos ncleos de outros sistemas operacionais. No caso do UNIX, estas funes so, em geral, programas no nvel do usurio. O exemplo de programa mais destacado neste caso o programa shell que o responsvel pela intepretao dos comandos do usurio. Na maior parte das vezes o shell executa o comando fork e o processo lho executa o comando solicitado atravs da chamada exec. As palavras restantes na linha de comando so tratadas como parmetros do comando. O shell aceita trs tipos de comandos: arquivo executvel produzido por compilao; arquivo executvel contendo uma sequncia de linhas de comando do shell; comando interno do shell. O shell normalmente executa um comando sincronamente, ou seja, espera o trmino do processo associado ao comando antes da leitura de uma nova linha de comando. Tambm possvel a execuo assncrona do comando. Neste caso, o shell l e executa a prxima linha de comando sem esperar o trmino do processo associado ao comando anterior, o qual executa em background. Como o shell um programa que se situa no nvel do usurio, no fazendo parte do ncleo, fcil modic-lo para um ambiente particular.

1.5.3 Modularidade no Ambiente UNIXO ambiente tem como losoa permitir aos usurios o desenvolvimento de programas pequenos e modulares que possam ser usados como blocos primitivos na construo de programas mais complexos. a) redirecionamento de entrada/sada (E/S) : os processos possuem, convencionalmente, acesso a trs tipos de arquivos padro: entrada, sada e erro. Processos que so executados a partir de um terminal possuem, tipicamente, o terminal como arquivo de entrada, sada e erro. Estes arquivos podem ser redirecionados independentemente. Ex: ls : lista todos os arquivos do diretrio corrente na sada padro; ls > output : redireciona a sada padro para o arquivo chamado output no diretrio atual; mail mjb < carta : faz com que o programa mail (correio eletrnico) leia o contedo da mensagem do arquivo carta, e no do terminal. b) pipe : permite que um uxo de dados seja estabelecido entre um processo produtor e um processo consumidor. Processos podem redirecionar a sua sada padro para um pipe a ser lido por outro processo que tenha redirecionado a sua entrada padro para o mesmo pipe. Ex: grep main a.c b.c c.c : lista as ocorrncias da palavra main nos arquivos a.c, b.c e c.c; grep main a.c b.c c.c j wc -l : submete a sada do comando anterior a um utilitrio que conta o nmero de linhas de um arquivo (wc, opo -l).

DCA-FEEC-UNICAMP


14

1.5.4 Servios do Sistema OperacionalDentre os servios suportados pelo ncleo temos: controle de execuo dos processos: criao, terminao, suspenso, comunicao entre processos; escalonamento (ordem de acesso CPU) de processos; alocao de memria principal para execuo dos processos. Caso a memria esteja escassa, o ncleo move temporariamente processos da memria primria para a secundria 3 ; alocao de memria secundria para armazenamento/recuperao eciente dos dados do usurio (este servio constitui o sistema de arquivos); acesso controlado aos dispositivos perifricos tais como terminais, tas, discos, redes, etc. O ncleo fornece estes servios de forma transparente. Ex: o ncleo deteta que um dado arquivo um arquivo regular ou um dispositivo, mas esconde esta distino dos processos do usurio; o ncleo formata os dados em um arquivo para ns de armazenamento interno, entretanto, este formato escondido do usurio, sendo retornado para este um stream no formatado de bytes.

1.5.5 Aspectos do HardwareA execuo dos processos do usurio no ambiente UNIX dividida em 2 nveis: usurio e ncleo. Quando um processo executa uma chamada do sistema, o modo de execuo do processo muda do modo usurio para o modo ncleo. As diferenas entre estes 2 modos so: processos no modo usurio podem acessar as suas instrues e dados, mas no as instrues e dados do ncleo ou de qualquer outro processo. Processos no modo ncleo podem acessar endereos do ncleo ou do usurio; algumas instrues so privilegiadas e resultam em erro quando executadas no modo usurio. Interrupes e Excees O UNIX permite que dispositivos tais como perifricos de E/S ou o relgio do sistema interrompam a CPU assincronamente. Geralmente, o hardware dene prioridades para os dispositivos de acordo com a ordem na qual as interrupes devero ser atendidas caso ocorram simultaneamente. Uma condio de exceo refere-se ocorrncia de um evento no esperado provocado pelo processo. Alguns destes eventos podem ser: endereamento ilegal da memria, execuo de instruo privilegiada, diviso por zero, etc.3

Esta transferncia pode ser do processo completo (swapping), ou de segmentos do processo (paginao).

DCA-FEEC-UNICAMP


15

As excees podem ser caracterizadas como algo que ocorre no meio da execuo de uma instruo, onde o sistema tenta reiniciar a instruo aps tratar a exceo. No caso das interrupes, estas podem ser consideradas como se ocorressem entre a execuo de duas instrues, sendo que o sistema continua a executar a partir da prxima instruo aps tratar a interrupo. O UNIX utiliza um mesmo mecanismo para manipular as condies de interrupo e exceo. Nveis de Execuo do Processador O ncleo necessita muitas vezes impedir a ocorrncia de interrupes durante a execuo de atividades crticas. Exemplo: o ncleo no deve aceitar interrupo do disco enquanto estiver operando sobre listas ligadas, isto porque o tratamento da interrupo pode interferir na atualizao dos apontadores provocando inconsistncias. Normalmente, os computadores possuem instrues privilegiadas que permitem denir o nvel de execuo do processador. A atribuio do nvel de execuo do processador em um determinado valor mascara a interrupo daquele nvel e dos nveis inferiores (tornando habilitadas as de nveis superiores). Na gura 1.3, caso o ncleo mascare a interrupo do disco, todas as interrupes, exceto a do relgio e dos erros da mquina, so impedidas.Erros de Hardware Prioridade Alta Relgio Disco Dispositivos de Rede Terminais Prioridade Baixa Interrupo de Software

Figura 1.3: Nveis de interrupo denidas pelo UNIX

Gerenciamento de Memria O ncleo reside permanentemente na memria principal, assim como, os processos em execuo (ou pelo menos parte deles). Quando da compilao, so gerados endereos no programa que representam variveis e instrues. O compilador gera estes endereos para uma mquina virtual como se nenhum outro programa fosse executar simultaneamente na mquina real. Quando da execuo do programa, o ncleo aloca espao na memria principal atravs do mapeamento do endereo virtual no endereo fsico da mquina. Este mapeamento depende das caractersticas do hardware da mquina.

DCA-FEEC-UNICAMP


16

1.6 Arquitetura do Sistema Operacional UNIXUma viso mais detalhada da arquitetura do ncleo do UNIX mostrada na gura 1.4.Programas do usurio bibliotecas

traps Nvel do usurio Nvel do ncleo

interface das chamadas de sistema

subsistema de arquivos

comunicao interprocessos

subsistema de controle de processos buffer cache

escalonador

gerenciamento de memria caractere bloco

drivers de dispositivos

controle do hardware Nvel do ncleo Nvel de hardware hardware

Figura 1.4: Arquitetura do ncleo do sistema operacional UNIX Os programas em linguagem de mquina podem evocar chamadas ao sistema diretamente, isto , sem o uso da biblioteca. Por sua vez, os programas em linguagem de alto nvel realizam as chamadas como se estivessem evocando funes ordinrias, cabendo biblioteca mapear estas chamadas de funes nas primitivas necessrias para acessar o sistema operacional. Outras bibliotecas permitem um uso mais sosticado das chamadas ao sistema (exemplo: biblioteca de E/S). A gura 1.4 divide as chamadas ao sistema em chamadas ao sub-sistema de arquivos e ao subsistema de controle dos processos. O sub-sistema de arquivos acessa os dados nos arquivos atravs

DCA-FEEC-UNICAMP


17

de um mecanismo de bufferizao que, atravs da interao com os drivers de dispositivos de E/S orientados a bloco, regula o uxo de dado entre o ncleo e os dispositivos de armazenamento secundrio. Os dispositivos de E/S orientados a bloco so dispositivos de armazenamento de acesso randmico. O sub-sistema de arquivo interage diretamente com dispositivos que no so do tipo bloco (terminais, por exemplo). Neste caso, no h a interveno do mecanismo de bufferizao. Os sub-sistemas de arquivo e de controle dos processos interagem quando do carregamento de um arquivo na memria para execuo. O mdulo de gerenciamento da memria controla a alocao de memria, ou seja, caso em um determinado instante o sistema no possua memria fsica suciente para todos os processos, o ncleo move-os entre a memria fsica e a memria secundria de modo a que todos os processos possuam as mesmas chances de execuo. Duas polticas so normalmente utilizadas: permuta (swapping) e paginao. O mdulo de escalonamento aloca a CPU aos processos, os quais executam at o instante em que liberam a CPU para aguardar um recurso, ou ento, so preemptados porque a execuo excedeu o quantum de tempo disponvel para o processo. Neste caso, o escalonador escolhe o processo pronto de maior prioridade. Ainda com relao aos processos, existem vrias formas de comunicao entre estes, variando desde a sinalizao assncrona de eventos at a transmisso sncrona de mensagens entre processos.

1.6.1 Introduo aos Conceitos do SistemaUma Viso do Sistema de Arquivos A representao interna de um arquivo dado por um inode. Este contm uma descrio do layout no disco do arquivo de dado, assim como outras informaes tais como: proprietrio do arquivo, permisses de acesso e instantes de acesso. Todo arquivo possui um inode, o qual alocado quando da sua criao, podendo possuir, entretanto, vrios nomes, todos mapeados no mesmo inode. Cada um destes nomes denomina-se link. Os inodes so armazenados no sistema de arquivos e so lidos em uma tabela de inodes (em memria) quando da manipulao dos respectivos arquivos. Duas outras estruturas de dados so importantes: tabela de arquivo (TA) e tabela descritora de arquivo do usurio (TDAU), sendo que TA uma estrutura global ao ncleo enquanto uma TDAU criada para cada processo. Quando da criao/abertura de um arquivo, o ncleo associa uma entrada de cada uma das tabelas ao inode correspondente ao arquivo, permitindo que as entradas destas trs estruturas -TA, TDAU e inode- mantenham o estado do arquivo, assim como, os direitos de acesso ao arquivo. TA mantm o offset, no arquivo correspondente, do prximo byte a ser lido/escrito, assim como, os direitos de acesso do processo; TDAU identica todos os arquivos abertos para o processo. A gura 1.5 ilustra o uso das tabelas TDAU, TA e de inodes. Note um link onde dois campos na TDAU apontam para o mesmo campo na TA.

DCA-FEEC-UNICAMPTDAU

Introduo aos Sistemas OperacionaisTA Tabela de Inodes

18

Figura 1.5: Estruturas de dado do sistema de arquivos O ncleo retorna um descritor de arquivo quando das chamadas open e create, o qual corresponde a um ndice na TDAU. Quando da execuo de um write ou um read, o ncleo utiliza o descritor de arquivo para acessar a TDAU e atravs desta alcanar a TA e o inode do arquivo onde, atravs deste ltimo, o ncleo encontra o dado no arquivo. Esta arquitetura dos dados permite vrios nveis de acesso compartilhado ao arquivo. Uma instalao pode possuir vrias unidades fsicas de disco, cada uma delas contendo um ou mais sistemas de arquivo. O ncleo relaciona-se com os sistemas de arquivo de um ponto de vista lgico ao invs de tratar com discos. Cada dispositivo lgico identicado por um nmero do dispositivo lgico. A converso entre os endereos do dispositivo lgico (sistema de arquivo) e os endereos, no dispositivo fsico (disco) realizada pelo driver do disco. Um sistema de arquivos consiste de uma sequncia de blocos lgicos, cada um contendo qualquer mltiplo de 512 bytes. O tamanho de um bloco lgico homogneo dentro do sistema de arquivos podendo, entretanto, variar para diferentes sistemas de arquivo em uma dada congurao. Blocos maiores representam um aumento na taxa de transferncia dos dados entre a memria e o disco. Entretanto, blocos maiores demandam mais espao em memria para manipul-los. Um sistema de arquivos possui a seguinte estrutura (ver gura 1.6):bloco de boot super bloco lista de inodes blocos de dados

Figura 1.6: Estrutura do sistema de arquivos bloco de boot : contm o cdigo do bootstrap que lido na mquina quando da partida do sistema operacional; super-bloco : descreve o estado de um sistema de arquivo; lista de inodes : tem o seu tamanho denido quando da congurao do sistema de arquivos. Um dos inodes corresponde raiz do S.A. atravs deste inode que a estrutura de diretrios do sistema acessada;

DCA-FEEC-UNICAMP


19

bloco de dados : contm arquivos e dados administrativos. Um bloco de dados s pode pertencer a um nico arquivo do sistema. Processos Um processo corresponde execuo de um programa e consiste de um conjunto de bytes que a CPU interpreta como instruo de mquina, dado e pilha. O processo executa uma sequncia de instrues que auto-contida e que no salta para um outro processo. Ele l e escreve seus dados nas suas reas de dado e pilha, mas no pode ler ou escrever nas reas de dado e pilha de outro processo. Os processos comunicam com outros processos e com o resto do sistema atravs de chamadas de sistema. Do ponto de vista prtico, um processo em UNIX uma entidade criada pela chamada fork. Exceto o primeiro, qualquer outro processo criado atravs da chamada fork. O processo que chamou o fork identicado como processo pai e o que acabou de ser criado identicado como processo lho. Todo processo tem um nico pai mas pode ter vrios lhos. O ncleo identica cada processo atravs de um nmero denominado process ID (PID). No caso do processo lho, ele recebe como retorno aps a execuo do fork o valor 0, enquanto o processo pai recebe um valor diferente de 0 que corresponde ao PID do lho. Atravs do teste do valor retornado pelo fork, um processo pode distinguir se ele o processo pai ou o processo lho e, em consequncia, tomar a ao correspondente. O processo 0 um processo especial criado quando da iniciao do sistema (boot). Aps criar o processo 1, conhecido como init, o processo 0 torna-se o processo swapper. O processo 1 ancestral de qualquer outro processo no sistema, possuindo uma relao especial com estes, relao esta que ser discutida nos captulos subsequentes. Um arquivo executvel gerado quando da compilao de um programa consiste das seguintes partes: um conjunto de cabealhos que descrevem os atributos dos arquivos; o texto do programa; representao em linguagem de mquina dos dados que possuem valor inicial e uma indicao de quanto espao o ncleo necessita alocar para os dados sem valor inicial, denominado bss; outras sees tais como informaes sobre a tabela de smbolos. O ncleo carrega um arquivo executvel, gerado pelo compilador, durante a execuo de uma chamada exec, consistindo o processo carregado de trs partes: texto, dado e pilha. As regies de texto e dado correspondem s sees do texto e dados iniciados e no-iniciados (bss). A pilha criada automaticamente e o seu tamanho ajustado dinamicamente pelo ncleo em tempo de execuo. Um quadro (frame) da pilha contm os parmetros para a funo chamada, suas variveis locais e os dados necessrios (apontador de pilha e contador de programa) para recuperar o quadro anterior na pilha. Como um processo no UNIX pode executar em 2 modos, ncleo ou usurio, utiliza-se uma pilha separada para cada modo. O lado esquerdo da gura 1.7 mostra a pilha do usurio para o programa copy quando da chamada de sistema write.

DCA-FEEC-UNICAMP


20

variveis locais end. do quadro 2 end. de retorno apos chamada do write parmetros do write (new, buffer, count) variveis locais (count) end. do quadro 1 end. de retorno aps chamada do copy parmetros do copy (old, new) variveis locais (fdold, fdnew) end. do quadro 0 end. de retorno aps chamada do main parmetros do main (argc, argv) Pilha do Usurio

direo do crescimento da pilha

quadro 3 call write

quadro 2 call copy

quadro 1 call main quadro 0 incio

processamento da chamada white Pilha do Ncleo quadro 0 interface das chamadas de sistema

Figura 1.7: Estado das pilhas para o programa copy Cada chamada de sistema possui uma entrada na biblioteca de chamadas de sistema, a qual codicada em assembler, contendo instrues especiais (traps) que, quando executadas, provocam uma interrupo resultando em um chaveamento no hardware para o modo ncleo passando a utilizar a pilha do ncleo. A construo da pilha do ncleo ocorre nos mesmos moldes da construo da pilha no modo usurio. Todo processo possui uma entrada na tabela de processos (TP) do ncleo e a cada um alocada uma rea U que contm dados privados manipulados somente pelo ncleo. A TP aponta para uma tabela de regies do processo (pregion), cujas entradas apontam para entradas na tabela de regio. Uma regio uma rea contgua de um espao de endereo do processo, tal como: texto, dado e pilha. As entradas na tabela de regio descrevem os atributos da regio, ou seja, se a regio contm texto ou dado, se uma regio compartilhada ou privada e se o contedo da regio encontra-se em memria. O nvel extra de encadeamento, ou seja, da pregion para a tabela de regio, permite que processos independentes compartilhem regies de memria. Quando um processo evoca a chamada exec o ncleo aloca regies para o texto, dado e pilha do processo que est sendo criado, aps liberar as regies antigas do processo que estava executando.

DCA-FEEC-UNICAMP


21

Quando um processo evoca fork o ncleo duplica o espao de endereo do processo antigo permitindo, quando possvel, que processos compartilhem regies ou, caso contrrio, fazendo uma cpia da regio. Quando um processo evoca exit o ncleo libera as regies que o processo estava usando. A gura 1.8 ilustra as estruturas de dados associadas ao controle dos processos.pregion rea U Tabela de Regies

memria primria Tabela de Processos

Figura 1.8: Estruturas de dados associadas ao controle dos processos A entrada na tabela de processos e a rea U contm informaes de controle e status sobre o processo. A rea U pode ser vista como uma extenso da entrada do processo na tabela de processos. Campos importantes da tabela de processos: campo de estado; identicadores dos usurios que possuem o processo; um conjunto descritor de evento quando o processo est bloqueado. A rea U contm informaes que descrevem o processo e que so acessadas somente durante a execuo do processo. Os campos mais importantes so: apontador para o campo na TP do processo em execuo; descritores de arquivo para todos os arquivos abertos; parmetros internos de E/S; limites de tamanho do processo e arquivo. Contexto de um Processo O contexto de um processo o estado denido pelo seu texto correspondendo aos valores das suas variveis globais e estruturas de dado, os valores dos registros de mquina usados, os valores armazenados no seu slot na tabela de processos e na rea U e o contedo das suas pilhas de usurio e ncleo. Quando o ncleo decide executar um novo processo realiza-se uma mudana de contexto. Quando da realizao de uma mudana de contexto o ncleo salva informaes sucientes de modo a que posteriormente ele possa recuperar o contexto do processo anterior e continuar a sua

DCA-FEEC-UNICAMP


22

execuo. Da mesma forma, quando da mudana do modo usurio para o modo ncleo, o ncleo salva as informaes necessrias para que o processo possa retornar ao modo usurio e continuar a execuo. Neste ltimo caso, temos uma mudana de modo e no de um chaveamento de contexto. Estados do Processo A vida de um processo pode ser representada por um conjunto de estados (gura 1.9): executando no modo usurio; executando no modo ncleo; pronto; bloqueado (dormindo).

1

Executando em Modo Usurio

chamada de sistema ou interrupo

retorno

Executando em Modo Ncleo

interrupo/retorno 2

escalonado aguardando evento 3 evento Pronto

4

Bloqueado

Figura 1.9: Estados de um processo O ncleo protege a sua consistncia permitindo chaveamento de contexto apenas quando o processo transita do estado executando no modo ncleo para o modo bloqueado. O ncleo tambm eleva o nvel de execuo do processador quando da execuo de regies crticas de modo a impedir interrupes que possam provocar inconsistncias em suas estruturas de dados. O escalonador de processo realiza, periodicamente, a preempo de processos executando no modo usurio de forma a que os processos no monopolizem a CPU.

Captulo 2

PROCESSOS2.1 IntroduoNo captulo anterior denimos o conceito de processo, bem como algumas generalidades sobre como o sistema operacional UNIX gerencia processos. Neste captulo, avanaremos no estudo de processos, analisando problemas de concorrncia, escalonamento e comunicao inter-processos.

2.1.1 Modelo de ProcessosA maioria dos computadores modernos so capazes de realizar diversas atividades em paralelo. Enquanto roda um programa do usurio, o computador pode ler um disco ou utilizar a impressora. Em sistemas multiprogramados, a CPU comutada de programa a programa em perodos da ordem de milisegundos, dando ao usurio a impresso de paralelismo. O gerenciamento de atividades paralelas difcil de ser implementado com ecincia. Entretanto, projetistas de sistemas operacionais ao longo dos anos vm desenvolvendo modelos objetivando tornar esta tarefa mais simples. No modelo mais empregado atualmente, todos os programas executveis no computador, muitas vezes incluindo subsistemas do sistema operacional, esto organizados na forma de processos. Conceitualmente, cada processo tem uma prpria CPU virtual (tabela armazenando contedo de registradores, contador de programa, etc). A posse da CPU real passada periodicamente de processo a processo. O sistema pode ser visto como uma coleo de processos sendo executados em pseudo paralelismo. 1 Conforme denido anteriormente, a habilidade de executar mltiplos programas numa nica CPU denomina-se multiprogramao. Em sistemas multiprogramados, a velocidade de execuo de um processo funo da quantidade de processos competindo pela CPU. Isto implica que o tempo de execuo de um processo varia a cada nova execuo, dependadendo da carga da mquina. Assim sendo, processos no devem ser programados com consideraes intrnsecas de tempo. Quando so requeridas consideraes de tempo real, medidas especiais devem ser tomadas para se assegurar que estas iro ocorrer.1

Paralelismo real obtido apenas com a utilizao de mltiplas CPUs.

23

DCA-FEEC-UNICAMP


24

2.1.2 ConcorrnciaEm muitos sistemas operacionais, processos frequentemente compartilham outros recursos alm da CPU. Por exemplo, durante uma chamada de sistema um processo pode ter acesso a uma tabela mantida pelo ncleo. Neste caso, o ncleo deve inibir a comutao da CPU para outro processo, at que todas as operaes na tabela forem efetuadas. Caso contrrio, a tabela fatalmente assumiria um estado inconsistente onde apenas algumas alteraes foram processadas. Em situaes como a exemplicada acima, a tabela denida como um recurso compartilhado, e a parte do cdigo que o manipula como uma regio crtica. A execuo de uma regio crtica deve ser um procedimento controlado a m de evitar que os recursos compartilhados atinjam estados inconsistentes.

2.1.3 Regies CrticasA chave para prevenir problemas em reas compatilhadas proibir que mais de um processo leia ou escreva dados compartilhados ao mesmo tempo, ou seja, deve-se garantir a mtua excluso. Se for garantido que nenhum par de processos esteja executando ao mesmo tempo uma regio crtica delimitando um mesmo recurso compartilhado, inconsistncias so evitadas. 2 Embora este quesito evite inconsistncias, o mesmo no garante ecincia na utilizao dos recursos compartilhados. Para assegurarmos uma boa soluo, necessrio que: dois processos no estejam simultaneamente dentro de suas regies crticas referentes ao mesmo recurso compartilhado (garantia de mtua excluso); a garantia de mtua excluso se d independente da velocidade relativa dos processos ou nmero de CPUs; nenhum processo executando fora de regies crticas bloqueie outro processo; nenhum processo espere um tempo arbitrariamente longo para executar uma regio crtica (ou sofra estarvao). Vrios algoritmos de controle visando garantir as propriedades acima foram propostos. Estes algoritmos so classicados segundo o modo com que esperam pela autorizao de entrada numa regio crtica: espera ocupada (competindo pela CPU durante a espera) ou bloqueada (no competindo pela CPU). Todo algoritmo de mtua excluso possui, invariavelmente, duas partes (implementadas como duas funes distintas). A primeira funo evocada quando o processo deseja iniciar a execuo de uma regio crtica. Quando esta funo retorna, o processo est apto a executar a regio crtica. No nal da execuo, o processo evoca a segunda funo, anunciando que a regio crtica j foi executada. Esta segunda funo, via de regra, provoca o retorno da primeira funo em outro processo.2 Note que regies crticas delimitando diferentes recursos podem ser executadas por diferentes processos ao mesmo tempo.

DCA-FEEC-UNICAMP


25

Para permitir que regies crticas que acessam recursos compartilhados distintos possam ser executadas ao mesmo tempo, cada recurso compartilhado possui um identicador (via de regra um nmero inteiro). Assim sendo, as duas funes que compem o algoritmo de garantia de mtua excluso possuem este identicador como parmetro.

2.1.4 Mtua Excluso Com Espera OcupadaNesta seo analisaremos vrias propostas para garantir excluso mtua nas regies crticas, no permitindo que mais de um processo possam manipular um recurso compartilhado ao mesmo tempo. Em todas, o processo que est tentanto acessar uma regio crtica em execuo por outro processo permanece em espera ocupada, isto , competindo pela CPU mas sem avanar no seu processamento. Por esta razo, os mtodos que empregam espera bloqueada so os mais utilizados na prtica. Desabilitar Interrupes A soluo mais simples o mtodo de desabilitar todas as interrupes quando se est entrando na regio crtica, e reabilit-las ao sair. Esta proposta no muito atrativa, pois d ao processo usurio poder de desabilitar todas as interrupes, inclusive aquelas que permitem o ncleo reassumir a CPU. Caso o processo no as reabilite por algum motivo, o sistema operacional jamais reassume o controle do harware. Em outro aspecto, conveniente para o sistema operacional desabilitar interrupes durante algumas instrues, enquanto est atualizando variveis internas. Assim, desabilitar interrupes uma soluo til para o sistema operacional, no para processos de aplicao. Variveis LOCK Uma segunda tentativa leva-nos a uma soluo por software. Considere uma varivel simples e compartilhada 3 LOCK, inicialmente igual a 0. Quando um processo deseja entrar em sua regio crtica ele primeiro testa o LOCK. Se for 0, o processo altera para 1 e executa a regio crtica. Se for 1 ele espera at que seja 0. Embora parea uma boa soluo, o que ir ocorrer se ambos testam uma varivel de valor 0 ao mesmo tempo ? Alternncia Estrita Esta proposta dene uma varivel TURN, inicialmente 0. Ela indica quem deve esperar e quem pode entrar na seo crtica. Se TURN for 0, o processo 0 pode entrar na regio crtica. Ao sair, deve passar o valor de TURN para 1. Quando TURN 1 o processo 1 pode entrar na seo crtica. Ao sair passa o valor de TURN para 0. 4 Este algoritmo garante a mtua excluso. Entretanto, os processos estritamente se alternam na posse do recurso compartilhado. Isto faz com que um processo necessite aguardar o acesso a um recurso compartilhado por todos os demais at que chegue novamente a sua vez. O que ocorre quando o nmero de acessos for diferente entre os processos ?3 4

Uma para cada recurso compartilhado. Este algoritmo facilmente generalizado para

N processos, N > 2.

DCA-FEEC-UNICAMPSoluo de Peterson


26

Obtida pela combinao das idias de variveis LOCK e TURN, criando-se tambm uma soluo por software para o problema. Esta soluo evita os problemas individuais das solues anteriores, mas pouco utilizada na prtica por utilizar espera ocupada. Instruo TSL Esta proposta requer uma pequena ajuda do hardware. Ela utiliza a instruo TSL (Test and Set Lock) presente em muitos processadores. Esta instruo permite a implementao de variveis LOCK cujo teste e atualizao so atmicos (em outas palavras, a instruo TSL indivisvel mesmo frente a interrupes de hardware).

2.1.5 Mtua Excluso com Espera BloqueadaSero apresentados a seguir alguns mecanismos de garantia de mtua excluso que bloqueiam os processos quando tentam executar uma regio crtica ocupada. So mais ecientes que os anteriores, posto que processos bloqueados no competem pela CPU. Sleep e Wakeup Um dos mtodos mais simples constitue-se do par sleep e wakeup. sleep uma chamada de sistema que muda o estado de um processo em execuo para bloqueado. Um processo bloqueado volta a tornar-se ativo quando outro o desbloqueia atravs da chamada wakeup. O mtodo o mesmo que emprega variveis LOCK operadas por instrues TSL, exceto que quando a varivel apresenta valor 1, o processo executa sleep. O processo que altera o valor de LOCK para 0 ao sair da regio crtica o responsvel por ativar um processo bloqueado (via wakeup). Infelizmente, com o emprego de apenas sleep e wakeup fcil demonstrar e existncia de um estado onde todos os processos encontram-se bloqueados. Esta situao denominada deadlock. Semforos So variveis inteiras que contam o nmero de vezes que a operao wakeup tenha sido realizada. Duas operaes, DOWN e UP (generalizaes de sleep e wakeup) so denidas. A operao DOWN verica se o valor do semforo for maior que 0. Se o for, decrementa o valor e continua. Se o valor 0, o processo bloqueado. A operao UP incrementa o valor do semforo. Se um ou mais processos estiverem bloqueados sobre aquele semforo, um deles escolhido pelo sistema para completar a operao DOWN (emitindo-lhe um wakeup). As operaes com semforos so atmicas ou indivisveis, implementadas com instrues TSL. Contadores de Evento Um outro tipo de varivel de sincronizao entre processos. Trs operaes so denidas para um contador de evento (E): READ(E) : retorna o valor corrente de E;

DCA-FEEC-UNICAMP


27

ADVANCE(E) : incrementa atomicamente E; AWAIT(E,v) : bloqueia at que E v.

Note que os contadores de eventos nunca decrescem e partem sempre de 0. Contadores de evento so mais convenientes que semforos para problemas to tipo produtor-consumidor com buffer limitado. Monitores Semforos e contadores de evento tornam simples a proteo de recursos compartilhados. Entretanto, uma simples troca na ordem da chamada das primitivas pode gerar uma situao de deadlock. Em suma, a utilizao de semforos e contadores de eventos deve se processar com extrema cautela. Monitores so uma proposta de mecanismo de sincronizao de alto nvel. Um monitor uma coleo de procedimentos, variveis e estruturas de dados agrupados em um bloco. Os processos podem acessar os procedimentos do monitor mas no suas estruturas internas. Monitores tm uma caracterstica importante: somente um processo pode estar ativo 5 no monitor em um dado instante (garantindo portanto a mtua excluso). Monitores constituem-se em um conceito de linguagem de programao, ou seja, o compilador reconhece que os monitores so especiais e pode manusear as chamadas do monitor diferentemente de outras chamadas. Esta uma das desvantagens de monitores: precisam de linguagens de programao que os incorpore. A concluso que monitores, apesar de elegantes na manuteno de mtua excluso, de aplicao restrita, pois raras so as linguagens de programao que os incorporam.

2.1.6 Comunicao Inter-processosMuitos autores consideram os mecanismos de mtua excluso apresentados acima como formas de processos se comunicarem. Entretanto, preferimos considerar tais mecanismos como de sincronizao inter-processos, usando o termo comunicao apenas quando ocorrer intercmbio de informao entre processos. Sincronizao so procedimentos de controle, normalmente usados para garantir mtua excluso, e utilizados para geranciar a competio entre os processos. Comunicao, por sua vez, visa promover a cooperao entre os processos. Passagem de Mensagem Este mtodo de comunicao entre processos usa duas chamadas de sistema: send e receive. send(destino, mensagem) : envia mensagem a um processo destino. receive(fonte, mensagem) : recebe mensagem de um processo fonte. Destino e fonte de mensagens so buffers alocados pelos processos para ns de envio e recepo de mensagens. Mensagens so estruturas tipadas ou no cujo contedo interpretado unicamente pelos processos emissor e receptor da mensagem.5

Executando qualquer um de seus procedimentos.

DCA-FEEC-UNICAMPCompartilhamento de Dados


28

Processos podem se comunicar atravs do compartilhamento de uma rea comum onde dados podem ser escritos por um e lidos por outro processo. O acesso a esta rea comum deve ser disciplinado por um mecanismo de mtua excluso (tipicamente semforos) ou tornando as instrues de leitura e gravao atmicas. Duas primitivas so necessrias: STORE(posio, dado) : grava dados numa certa posio; FETCH(posio, dado) : acessa dados de uma certa posio. Chamada de Procedimentos Remotos Chamada de procedimentos remotos (ou RPC) uma forma mais estruturada de troca de mensagens entre processos servidores e clientes. Um processo servidor dispe de um conjunto de servios que um processo cliente evoca como se evocasse um procedimento local. O cliente indica o servio desejado ao servidor, passando parmetros para sua execuo, se for o caso. Recebida a requisio, esta processada pelo servidor 6 que retorna os resultados ao cliente. O envio e recepo de parmetros e retornos se d por troca de mensagens. Uma biblioteca de RPC possui duas primitivas bsicas: REGISTER_RPC(servio) : utilizada por servidores para anunciar que servios esto aptos a processar; CALL_RPC(servio, parmetros, resultados) : utilizada por clientes para evocar servios.

2.2 Escalonamento de Processos2.2.1 IntroduoQuando mais de um processo est ativo (pronto para executar), cabe ao sistema operacional decidir qual ter a posse da CPU. A parte do sistema operacional que toma esta deciso chamada escalonador e o algoritmo utilizado o algoritmo de escalonamento. Vrios critrios devem ser observados por um algoritmo de escalonamento: 1. progresso: garatir que cada processo tenha acesso CPU; 2. ecincia: manter a CPU ocupada praticamente 100% do tempo; 3. tempo de resposta: minimizar o tempo de resposta na execuo dos processos, principalmente os interativos (editores, planilhas, etc); 4. tempo de espera: minimizar o tempo de espera de servios no interativos (compilao, impresso, etc); 5. vazo: maximizar o nmero de processos executados por hora.6

Ou colocada numa la de espera.

DCA-FEEC-UNICAMP


29

importante observar que alguns desses objetivos so contraditrios. Se um algoritmo favorece o escalonamento de processos interativos certamento estar comprometendo os no interativos. Vejamos agora alguns algoritmos de escalonamento.

2.2.2 Algoritmos de EscalonamentoEscalonamento Round Robin Este o mais antigo e simples algoritmo de escalonamento. Cada processo executado por um intervalo de tempo (quantum). Se o processo ainda estiver executando ao nal do quantum, ele suspenso e a CPU alocada a outro processo. Se o processo acabar ou for bloqueado antes do nal do quantum, a CPU tambm passada a outro processo. A nica questo a ser analisada o tamanho do quantum. Se for muito pequeno, diminui a ecincia da CPU, pois a alocao da CPU para outro processo implica num certo overhead. Se for muito grande, degrada a resposta para os processos interativos. Algoritmos com Prioridades O algoritmo Round Robin faz a considerao que todos os processos so de igual importncia. Certas aplicaes, como controle de processos industriais, demandam um algoritmo de escalonamento com prioridades. A idia bsica que cada processo tem uma prioridade e processos com prioridades superiores devem ser executados primeiro. Para prevenir que processos de alta prioridade executem indenidamente, o escalonador, via de regra, diminui a prioridade dos processos com o aumento de seu respectivo tempo de execuo. Mltiplas Filas Este um algoritmo que dene classes com prioridades. Processos na classe de menor prioridade so executados por um quantum. Processos na classe seguinte, por dois quanta. Na prxima classe por 4 quanta, e assim por diante. Quando um processo utiliza todos os quanta a ele alocados, o mesmo interrompido e sua classe tem a prioridade diminuda. Este algoritmo diminui o nmero de comutaes da CPU entre os processos ativos. Tarefas Pequenas Primeiro Este algoritmo designado para aplicaes no interativas, onde o tempo mdio de execuo conhecido a priori. O algoritmo dene que as tarefas menores devem ser executadas primeiro. Prova-se que esta poltica minimiza o tempo mdio de espera dos Jobs. Algoritmo Policy-Driven Este algoritmo particiona a CPU de forma equnime entre os usurios (no entre os processos). O algoritmo dene que se existirem n usurios ligados ao sistema, e cada usurio dever receber 1/n do poder da CPU. Para isto, o sistema deve manter informaes do tempo de CPU que cada usurio j disps desde que entrou no sistema, e do instante de tempo que cada usurio ligou-se ao sistema.

DCA-FEEC-UNICAMPEscalonamento em Dois Nveis


30

At agora foi considerado que todos os processos residem em memria primria. Entretanto se esta memria for insuciente, processos ativos podem ser armazenados temporariamente em memria secundria (tipicamente disco). O meio mais prtico para controlar a comutao de processos denir dois nveis de escalonamento. Um escalonador de baixo nvel se restringe a troca de processos que esto na memria primria no momento. Um escalonador de alto nvel decide sobre a troca dos processos entre as memrias primria e secundria.

2.3 Gerenciamento de Processos no Sistema Operacional UNIXNo captulo 1 introduzimos o conceito de processo, como so criados e como o sistema operacional os mantm. Neste captulo detalharemos mais a estruturao de processos no UNIX e apresentaremos como processos so controlados, escalonados e se comunicam.

2.3.1 Transies de EstadoNa gura 1.9 apresentamos um diagrama de estados simplicado onde um processo podia se encontrar em 4 estados: executando em modo usurio, executando em modo ncleo, pronto e bloqueado (dormindo). A rigor, um processo no UNIX apresenta 9 estados (gura 2.1): 1. Executando em modo usurio; 2. Executando no modo ncleo; 3. Pronto para execuo (aguardando apenas CPU) e residindo em memria primria; 4. Bloqueado (dormindo) e residindo em memria primria; 5. Pronto para execuo, mas residindo em memria secundria (aguardando swapping); 6. Bloqueado (dormindo) e residindo em memria secundria; 7. O processo est saindo do modo ncleo e retornando ao modo usurio, quando ocorre uma mudana de contexto e o processo perde a CPU; 8. O processo acabou de ser criado e est em transio para pronto; 9. O processo executou um exit, no mais existe, mas seu registro mantido at que seja enviado ao processo pai seu cdigo de retorno e outras estatsticas. Vejamos o que tipicamente ocorre a partir da criao de um processo. Aps executado um fork, so criados para o novo processo um campo na tabela de processos, sua rea U e apontadores para sua pregion. O processo encontra-se no estado 8. Dependendo da disponibilidade ou no de memria primria, o processo move-se, respectivamente, para os estados 3 ou 5. Assuma que o processo deslocou-se para o estado 3 (pronto em memria primria). O escalonador seleciona ento o processo para executar, movendo-o para o estado 2 (executando em modo ncleo), onde a chamada fork ser

DCA-FEEC-UNICAMP

Introduo aos Sistemas OperacionaisExecutando em Modo Usurio 1 escalonado chamada de sistema ou interrupo

31

retorno

7

9 exit Executando em Modo Ncleo perda da CPU 2 interrupo/retorno

"Preemptado"

Terminado

escalonado aguardando evento Bloqueado em Memria 3 evento Pronto em Memria memria abundante

4

"swap out"

"swap out"

"swap in"

8

fork

memria escassa Bloqueado em Memria Secundria evento 6 5 Pronto em Memria Secundria

Figura 2.1: Diagrama completo de transio de estados para processos completada para este processo, retornando 0. A partir da, o processo entra em execuo no modo usurio, processando suas instrues uma a uma. Expirado seu quantum de CPU, uma interrupo de relgio faz com que o processo retorne ao modo ncleo novamente. Terminado o tratamento da interrupo, o escalonador pode decidir alocar a CPU a um outro processo, movendo este para o estado 7. Este estado equivalente ao estado 3 como mostra a linha pontilhada na gura 2.1. Esta distino feita para enfatizar que um processo tem a CPU tomada somente quando est apto a retornar para o modo usurio, diferente do estado 3 onde deve voltar ao modo ncleo para completar uma chamada de sistema. A eventual execuo de uma chamada de sistema faz com que o processo abandone o modo usurio (estado 1) e continue sua execuco no modo ncleo (estado 2). Suponha que o processo requeira uma operao de E/S do disco. O ncleo coloca o processo no estado 4 (dormindo em memria) at que o processo seja noticado que a operao de E/S se completou (mais precisamente, quando a operao se completa, o hardware interrompe a CPU, cujo tratamento da interrupo resulta no acordar do processo). Se ao ser desbloqueado o processo ainda estiver residindo em memria primria, o mesmo posto no estado 3, aguardando CPU.

DCA-FEEC-UNICAMP


32

Entretanto, se durante sua permanncia no estado 4 o ncleo necessitar de espao na memria primria, o processo sofre swapping, sendo removido da memria primria e armazenado em memria secundria (tipicamente disco). Neste caso, o processo atinge o estado 6 (dormindo em memria secundria). Uma vez completada a operao de E/S com o processo no estado 6, este transita para o estado 5 (pronto em memria secundria). Quando o swapper escolhe o processo para aloc-lo novamente em memria primria, este volta para o estado 3. No estado 3, quando o escalonador volta a atribuir a CPU ao processo, o mesmo atinge o estado 2 onde completa a chamada de sistema e volta ao estado 1, executando no modo usurio. Quando um exit executado pelo processo, o mesmo transita, via estado 2, para seu estado terminal (9), permanecendo neste estado at que o processo pai seja noticado. Algumas observaes sobre o diagrama de transio de estados apresentado na gura 2.1: uma vez criado, as transies de estado de um processo dependem exclusivamente do sistema operacional; um processo pode forar a entrada no modo ncleo atravs da execuo de uma chamada de sistema, mas a sada deste estado foge ao seu controle; um processo pode atingir o estado 9 sem explicitamente evocar um exit: traps aritmticos como diviso por zero e overows, ou de segmentao como referncia a posies invlidas de memria, podem forar compulsoriamente o trmino do processo.

2.3.2 Descritores de ProcessosA tabela de processos e a rea U descrevem o estado dos processos. A primeira uma estrutura mantida pelo ncleo com os seguintes campos: o estado do processo; a localizao da rea U e do prprio processo, seja na memria primria ou secundria, bem como o tamanho do processo; o identicador do usurio (UID), isto , o dono processo; o identicador do processo (PID), nico durante toda a vida do processo; eventos aguardados pelo processo quando no estado bloqueado (dormindo); parmetros de escalonamento, utilizados para decidir quais processos transitaro entre estados de execuo nos modos usurio e ncleo; sinais enviados ao processo, mas ainda no tratados; marcas de tempo como tempo total CPU, despertadores armados pelo processo, etc, alm de recursos consumidos do ncleo (estes parmetros so utilizados no cmputo da prioridade de escalonamento do processo). A rea U de um processo armazena as seguintes informaes:

DCA-FEEC-UNICAMP


33

um ponteiro de volta ao respectivo ndice na tabela de processos; privilgios que o processo dispe, de acordo com o seu UID; tempos de execuo nos modos usurio e ncleo; ponteiros para os gerenciadores de sinais denidos pelo processo; o terminal de login associado ao processo, caso exista; um campo de erro, armazenando os erros gerados por chamadas de sistema; parmetros de I/O, tais como endereo de dados a serem transferidos, tamanho destes dados, destino, etc; o diretrio corrente e o diretrio raiz; descritores de arquivos abertos pelo processo; limites (tamanho mximo de pilha, arquivos, etc); permisses (modos de acesso atribuidos durante a criao de arquivos).

2.4 Escalonamento de Processos no UnixO escalonamento de processos no UNIX segue um algoritmo de meio termo entre prioridades e Round Robin. necessrio enfatizar que tal algoritmo tem o objetivo de compartilhar a CPU de forma equnime entre mltiplos usurios (sendo portanto orientada ao time-sharing). Tal algoritmo inadequado para aplicaes que requeiram o cumprimento estrito de restries temporais, como impostas por aquelas ditas de tempo real pesadas (hard real-time). O ncleo divide os processos segundo duas classes de prioridades: prioridades em modo ncleo (altas), referentes a processos bloqueados no estado 4 ou 5; prioridades em modo usurio (baixas), referentes a processos prontos no estado 7. A gura 2.2 mostra as classes de prioridades adotadas. Prioridades em modo ncleo so subdivididas em dois grupos. O primeiro grupo, de elevada prioridade, constituido de processos bloqueados a espera de swapping, E/S em disco, buffers de cache e inodes. Quando acordados, estes processos completam suas respectivas chamadas de sistema ininterruptamente (visando a rpida liberao de recursos do ncleo, tais como buffers). O segundo grupo, de prioridade mais baixa que o primeiro, constitui-se de processos bloqueados a espera de entrada de terminal, sada em terminal e terminao de processo lho. Tais processos podem ser interrompidos, pois estes estados de bloqueio no demandam grandes recursos do ncleo. Finalmente, processos aguardando apenas CPU (estado 7) so dispostos segundo um certo nmero de nveis de prioridade (este nmero dependente da particular implementao). Processos numa mesma classe de prioridade so dispostos numa la, como representado na gura 2.2 pelos crculos interligados.

DCA-FEEC-UNICAMPprioridades em modo ncleo


34

Nveis de Prioridade swapper no passvel de interrupo aguardando E/S em disco aguardando buffer aguardando inode aguardando entrada de terminal passvel de interrupo limiar de prioridade em modo ncleo nvel de usurio 0 nvel de usurio 1 aguardando sada em terminal

processos

Escalonamento por Prioridades aguardando trmino do proc. filho Escalonamento Round Robin

nvel de usurio N prioridades em modo usurio

Figura 2.2: Classes de prioridades para ns de escalonamento de processos O algoritmo de escalonamento do UNIX processado segundo o seguinte esquema. Quando ocorre uma interrupo do hardware: caso a interrupo acorde um ou mais processos com prioridade de modo ncleo, aloque a CPU quele de mais alta prioridade; caso contrrio, se uma mudana de contexto se zer necessria, aloque a CPU ao processo de mais alta prioridade dentre as de modo usurio. Em existindo mais de um processo apto a executar no mesmo nvel, a seleo se d segundo a poltica Round Robin. Pode-se observar que o escalonamento de processos no UNIX se d em duas direes: por prioridades na vertical, e por Round Robin na horizontal (para processos de mesma prioridade). Outras caractersticas importantes do algoritmo de escalonamento do UNIX: 1. As prioridades no modo ncleo dependem apenas do evento aguardado pelo processo. 2. Processos transitando do modo ncleo para o modo usurio, tem seu nvel de prioridade rebaixado em relao sua posio inicial. Esta penalidade, por utilizar recursos do ncleo,

DCA-FEEC-UNICAMP


35

visa evitar o monoplio da CPU pelos processos que utilizam chamadas de sistema de forma frequente. 3. A cada intervalo de tempo (tipicamente um segundo), as prioridades em modo usurio so recomputadas. Processos que se utilizaram recentemente da CPU so penalizados em benefcio dos processos que no a utilizaram.

2.5 Controle de Processos no UNIXO controle de processos se divide em duas atividades: instanciao (criao) e interrupo de processos.

2.5.1 Instanciao de ProcessosO mecanismo bsico de criao de processos no UNIX a chamada de sistema fork. A gura 2.3 ilustra o que ocorre quando um processo executa esta chamada de sistema. Um novo elemento na tabela de processos mantida pelo ncleo criado; a rea U criada imagem da rea U do processo pai; uma tabela de regio criada com reas de pilha e dados copiadas do processo pai, e rea de texto compartilhada com o processo pai. A pilha mantida pelo ncleo copiado tambm. Como pode-se observar na gura, a cpia da rea U faz com que todos os descritores de arquivo permaneam ativos para o processo lho. A cpia das regies de dados e pilhas faz com que toda a histria de execuo do processo pai (valores de variveis, retorno de funes, etc) seja herdada pelo processo lho. Uma alternativa de instanciao de processos a famlia exec de chamadas de sistema. Uma chamada exec utiliza os recursos do processo que a executou para instalar um novo processo. Diferente do fork, o processo que executa uma chamada exec deixa de existir. exec tem como parmetros o arquivo executvel e dados a serem passados ao novo processo, sendo por este obtidos na funo main atravs dos argumentos argc e argv. Basicamente, uma chamada exec libera as regies de memria relativas a texto, dados e pilha alocadas pelo processo executor da chamada, instalando novas regies para o novo processo. O campo na tabela de processos mantida pelo ncleo e a regio U permanecem inalterados. A pilha mantido pelo ncleo refeito para o novo processo. Isto signica que a histria do processo antigo perdida, mas o PID e descritores de arquivo por ele abertos permanecem vlidos. 7 . Fica claro agora uma das utilidades da chamada fork: criar um novo processo sem que o processo que o criou tenha sua execuo terminada. Exemplo: /* int pid, fd1, fd2; char arg1[16], arg2[16]; ... fd1 = open("arq1", O_RDONLY, 0);7 Entretanto, a nica maneira do novo processo conhecer o valor destes descritores atravs da passagem de parmetros via argc e argv.

*/

DCA-FEEC-UNICAMP

Introduo aos Sistemas Operacionaisprocesso pai rea U pregion arquivos abertos Tabela de Arquivos

36

dados do pai

diretrio corrente diretrio raiz

pilha do pai

pilha do ncleo

texto (compartilhado) processo filho rea U pregion arquivos abertos dados do filho diretrio corrente diretrio raiz Tabela de Inodes

pilha do filho

pilha do ncleo

Figura 2.3: A execuo de uma chamada de sistema fork. fd2 = open("arq2", O_RDONLY, 0); sprintf(arg1, "%d", fd1); sprintf(arg2, "%d", fd2); pid = fork(); if(pid == 0) { /* processo filho */ execlv("prog2", arg1, arg2, NULL); /* se passar por aqui, execv falhou */ printf("execlv falhou !"); exit(0); } /* processo pai continua */

DCA-FEEC-UNICAMP... /*


37

*/

No exemplo acima, o programa executa um fork, deixando a cargo do lho a execuo do novo processo. Os descritores de arquivo fd1 e fd2 so passados como argumento para o novo programa. Capturando estes argumentos, o novo programa capaz de executar operaes nos respectivos arquivos sem reabr-los. /* /* prog1 */ main(argc, argv) int argc; char *argv[]; { int fd1, fd2; /* acessa descritores abertos pelo executor do exec */ sscanf(argv[1], "%d", &fd1); sscanf(argv[2], "%d", &fd2); ... } /* */ */

2.5.2 Interrupo de ProcessosProcessos no UNIX podem ter sua execuo alterada assincronamente por ao de um outro processo (ou do usurio, atravs do shell). Esta ao referida como o envio de um sinal. Sinais podem ser enviados a um processo para notic-lo: de uma requisio de mudana de estado (ex: morte de um processo via kill -9); do trmino do processo lho; da corrncia de excees (ex: trap aritmtico); de situaes irrecuperveis (ex: recursos exauridos durante o processamento de um exec); da ocorrncia de erros inesperados (ex: utilizao de um pipe quebrado); do disparo de despertadores de tempo (ex: retorno da chamada sleep); de interrupes oriundas de terminais (ex:

"C );

de interrupes para ns de depurao (ex: ocorrncia de um breakpoint).

DCA-FEEC-UNICAMPsinal SIGHUP SIGINT SIGILL SIGFPE SIGKILL SIGSEGV SIGSYS SIGALRM SIGSTOP SIGCONT SIGCHLD

Introduo aos Sistemas Operacionaissignicado hang-up interrupo instruo ilegal (trap) exceo aritmtica (trap) trmino forado violao de segmentao (trap) argumento invlido em chamada de sistema alarme de relgio suspeno da execuo continuao da execuo mudane status de proceso lho .

38

Tabela 2.1: Exemplos de sinais no UNIX System V Sinais so explicitamente enviados a processos atravs da chamada de sistema kill. kill tem como parmetros o PID do processo ao qual o sinal se destina; e o tipo de sinal. Existem em torno de 30 tipos de sinais no UNIX System V, sendo os mais importantes mostrados na tabela 2.1. Processos podem apresentar as seguintes reaes a sinais: o processo compulsoriamente terminado; o processo bloqueado at a ocorrncia de um sinal de desbloqueio; o processo ignora o sinal; o processo captura o sinal. Sinais so armazenados na tabela de processos mantida pelo ncleo, sendo a ao correspondente ao sinal tomada quando o processo passa da execuo de modo ncleo para modo usurio. Para cada sinal denido um comportamento default para o proceso que o recebe. Em geral, este comportamente simplesmente o trmino do processo. Um processo pode alterar o comportamento default frente a ocorrncia de um dado sinal atravs da chamada de sistema signal. signal possui dois parmetros: o nmero do sinal (denido em signal.h); e a ao a ser executada quando do recebimento deste sinal. A ao pode possuir trs valores: 0 : o processo terminado quando receber o sinal; 1 : o sinal ignorado; endereo vlido de funo : A funo chamada assincronamente quando da ocorrncia do sinal. Esta funo dita gerenciador do sinal para o processo. Exemplo: capturar interrupes de teclado. Quando o usurio executa um "C , um sinal do tipo SIGINT enviado ao processo que est executando em foreground. O comportamento default para este sinal o trmino do processo. Suponha um programador precavido que deseje a conrmao

DCA-FEEC-UNICAMP


39

que o "C no foi acidental. O cdigo abaixo ilustra esta situao: /* /* gerenciador para SIGINT */ int ger() { int c; printf("Tem certeza que quer abortar [s/n] ? "); c = getchar(); if(c == s) exit(0); } */

main() { signal(SIGINT, ger); ... } /* */

Todas as vezes que um SIGINT for enviado ao processo, a funo ger chamada assincronamente, solicitando conrmao do trmino da execuo. Caso o usurio responda n, a funo retorna e o programa continua normalmente. A maneira como o ncleo processa sinais descrita sucintamente a seguir. Quando um sinal enviado a um processo (pelo ncleo ou por outro processo), o ncleo simplesmente ativa o campo correspondente ao sinal na tabela de processos. Neste campo est localizado tambm o gerenciador do sinal (denido pelo processo ou default). No momento que um processo passa do modo ncleo para o modo usurio, o ncleo verica se existe sinais enviados ao processo e ainda no tratados. Caso exista, o ncleo executa os seguintes passos: 1. Salva o contador de programa e o stack pointer do processo. 2. Caso o processo no dena um gerenciador para o sinal, executa a ao default. Caso contrrio, prossiga. 3. Associa temporariamente a ao default para o sinal. 4. Cria um novo quadro na pilha como se o processo estivesse evocando o gerenciador neste momento. 5. Direciona o contador de programa para o endereo da rotina gerenciadora do sinal e atualiza o stack pointer para levar em conta o aumento da pilha causado pela chamada do gerenciador.

DCA-FEEC-UNICAMP


40

O passo 3 merece um comentrio adicional. Ele existe para evitar que uma rajada de sinais ocasione um stack overow pelo empilhamento de mltiplas chamadas do gerenciador (caso o intervalo de ocorrncia dos sinais seja menor que o tempo de execuo do gerenciador). Entretanto, durante a execuo da rotina gerenciadora, o processo ca numa condio vulnervel, pois a ao default que ser executada face a ocorrncia de um novo sinal de mesmo tipo.

2.6 Comunicao e Sincronizao Inter-processos no UNIXNesta seo descreveremos trs mecanismos de comunicao inter-processos (pipes, mensagens e memria compartilhada), e um de sincronizao inter-processos (semforos). Pipes so disponveis em qualquer verso de UNIX, enquanto os demais esto presentes apenas nas verses compatveis com o System V.

2.6.1 PipesO mecanismo original de comunicao inter-processos so os chamados pipes. Em geral, pipes so empregados para estabelecer comunicao entre processos pai e lho. Um pipe um canal unidirecional de comunicao, isto , a informao ui numa nica direo. Para estabelecer-se comunicao bidirecional, so necessrios dois pipes. Pipes podem ser vistos como um buffer conectando dois processos. Um processo escreve dados num dos lados do buffer, enquanto o outro l estes dados no lado oposto. Esta forma de comunicao pode ser obtida com o emprego de arquivos em disco. A diferena bsica que pipes so bloqueantes, isto , a gravao em um pipe cheio ou a leitura em um pipe vazio causa o bloqueio do processo. Pipes so implementados pelo ncleo como um sistema de arquivos. Cada pipe tem um inode associado, sendo que o ncleo aloca blocos de dados medida que dados vo sendo escritos no pipe (desalocando-os medida que so lidos). Pipes so criados com a chamada de sistema pipe. A chamada retorna dois descritores de arquivos, sendo o primeiro para leitura e o segundo para gravao. Esta chamada, em geral, se processa antes de ocorrer um fork. Se a comunicao for no sentido pai ! lho, o processo pai fecha o primeiro descritor (com a chamada close), e o lho o segundo. A partir da, o pai executa chamadas write no segundo descritor e o lho read no primeiro. Um segundo pipe pode ser empregado para a comunicao no sentido inverso, atentando-se para o fechamento correto dos descritores que no sero empregados pelo processo. Aps o nal da sesso de comunicao, os lados abertos do pipe tambm so fechados a m de liberar os recursos a ele associados pelo ncleo. Exemplo: enviar um string do processo pai para o processo lho. /* main{} { int fd[2]; char buff[32]; */

DCA-FEEC-UNICAMP


41

if(pipe(fd) == -1) {perror("pipe"); exit(0);} if(fork() != 0) { /* PAI */ close(fd[0]); strcpy(buff, "oi filho !"); write(fd[1], buff, strlen(buff) + 1); close(fd[1]); exit(0); } else { /* FILHO */ close(fd[1]); read(fd[0], buff, 32); printf("%s", buff); close(fd[0]); exit(0); } /* */

2.6.2 MensagensTroca de mensagens um mecanismo de comunicao mais exvel que pipes. Enquanto um pipe um canal sncrono e unidirecional, mensagens so canais tanto sncronos quanto assncronos e bidirecionais. Para o envio e recepo de mensagens, cria-se um port de comunio. Ports so identicados por um nmero inteiro. A chamada de sistema msgget cria um port, retornando seu identicador local. O primeiro parmetro uma chave atribuida ao port, seu identicador global. O segundo parmetro so opes relativas a criao, acesso, etc. Via de regra, msgget retorna um port dado seu identicador global, criando-o caso tal port inexista. O ncleo mantm uma tabela de ports, e mensagens enviadas a ports so enleiradas, sendo recebidas na ordem que foram enviadas. A comunicao bidirecional, posto que, de posse de um identicador local de port, um processo pode tanto enviar quanto receber mensagens neste port. Mensagens so enviadas com a chamada de sistema msgsnd. A chamada possui quatro parmetros: o identicador do port para o qual a mensagem deve ser enviada; a estrutura que contm a mensagem; seu tamanho em bytes; e a opo de envio assncrono (retornando um cdigo de erro caso no exista espao para o ncleo armazenar a mensagem no port). A opo default o envio sncrono, onde o processo bloqueia ante a impossibilidade de armazenamento da mensagem no port. Estruturas contendo mensagens devem ser denidas como structs contendo dois campos: um inteiro (tipo da mensagem); e uma cadeia de bytes (o contedo da mensagem). Exemplo: struct mensagem { int tipo; /* tipo da mensagem */

DCA-FEEC-UNICAMPchar conteudo[1024]; };

Introduo aos Sistemas Operacionais/* conteudo da mensagem (1K max.) */

42

A recepo de mensagens se d atravs da chamada de sistema msgrcv. Cinco parmetros so necessrios: o identicador local do port; a estrutura onde a mensagem ser copiada; o tamanho mximo em bytes alocados pela estrutura; o tipo de mensagem desejada; e opo de recebimento assncrono (retornando um cdigo de erro caso o port no contenha mensagem do tipo especicado). Uma quarta chamada de sistema, msgctl, empregada para obter e alterar o status de ports. Possui trs parmetros: o identicador local do port; o tipo de operao e o endereo da estrutura com as informaes de entrada ou retorno, de acordo com a ao explicitada no segundo parmetro.

2.6.3 Memria CompartilhadaUma outra forma de comunicao disponvel no UNIX o compartilhamento de um espao virtual. Este espao criado via chamada de sistema shmget. shmget possui trs parmetros: um identicador global da regio compartilhada, o tamanho da regio em bytes; e opes de controle (criao e acesso). Como msgget, esta chamada retorna um identicador local da regio, criando-a caso inexista. Uma vez acessada, um processo associa a regio compartilhada em seu prprio espao de endereamento. Para tal, utiliza-se a chamada de sistema shmat que possui trs parmetros: o identicador local da regio compartilhada, o endereo local que apontar para a regio; e parmetros de controle (se a regio deve ser considerada de leitura apenas, por exemplo). O procedimento inverso, isto , a desassociao de uma regio compartilhada de um endereamento local se d com a chamada de sistema shmdt. Esta chamada possui um nico parmetro: o endereo local previamente associado a uma regio compartilhada. Finalmente, a chamada shmctl empregada para obter e alterar o status de uma regio compartilhada (permisses, desativao, etc). similar a msgctl. Deve-se observar que o mecanismo de memria compartilhada no necessita operaes especiais para a manipulao de dados. Como a regio mapeada num endereo local, leituras e escritas neste endereo se processam com os comandos de associao e cpia binria providos pelas linguagem C. Deve-se observar ainda, que este mecanismo de comunicao sempre assncrono, e pode suportar comunicao do tipo de-um-para-muitos (um processo escreve na memria compartilhada e vrios outros lem). Memria compartilhada implementada pelo ncleo atravs de uma tabela de regies alocadas por shmget. Esta tabela aponta para a tabela de regies de memria mantida pelo ncleo. Aps a chamada shmat, a tabela de regies do processo aponta para a respectiva regio mantida pelo ncleo (gura 2.4). O cdigo abaixo aloca um texto numa regio de memria compartilhada. /* #include #include */

DCA-FEEC-UNICAMPTabela de Memria Compartilhada


43

Tabela de Regies

pregion (processo 1)

Tabela de Processos

processo 1

processo 2

pregion (processo 2) memria principal

regio de memria compartilhada aps chamada de sistema shmat

Figura 2.4: Esquema de memria compartilhada #include #include #define KEY 67 extern char *shmat(); main() { char *buff; char *poema[16]; int i; int sh; /* cr

Documents

Apostila Faina