Sistemas_Operacionais

1

Sistemas Operacionais

Fernando Morse

[email protected]

2



Gerenciamento de processador: chamadas, comunicação interprocesso, agendamento, multiprogramação, processos concorrentes, primitivas de sincronização;

Gerenciamento de periféricos: hardware e software de entrada e saída, deadlock, contenção, balanceamento de carga

3


Introdução

Características

4


Definição:

O Sistema Operacional (SO) é um programa que controla e coordena todas as operações de um sistema de computação. É, muitas vezes, também chamado de Supervisor, Monitor, Executivo ou Controlador.

É um programa que atua como intermediário entre o usuário e o hardware de um computador com o propósito de fornecer um ambiente para a execução de programas.

5


4

USUÁRIOS

SISTEMA OPERACIOANAL

HARDWARE

6


Características de Sistema Operacional

Sistema Operacional é um conjunto de rotinas executado pelo

processador, da mesma forma que nossos programas.

SO é um programa que permite às pessoas usar o Hardware do

computador (CPU, Memória e Armazenamento Secundário).

Os usuários não dão instruções diretamente ao computador. Em vez

disso, eles dão instruções ao Sistema Operacional. O SO instruí o

Hardware a executar as tarefas desejadas.

Kernel é o único programa que executa sempre, todo o resto são

programas aplicativos.

7


Características de Sistema Operacional

• O Sistema Operacional é responsável por alocar recursos de hardware e escalonar tarefas. Ele também deve prover uma interface para o usuário - ele fornece ao usuário uma maneira de acesso aos recursos do computador.

• Um Sistema Operacional pode ser definido como um gerenciador dos recursos que compõem o computador (processador, memória, I/O, arquivos, etc). Os problemas centrais que o Sistema Operacional deve resolver são o compartilhamento ordenado, a proteção dos recursos a serem usados pelas aplicações do usuário e o interfaceamento entre este e a máquina.

8


Funções que o SO deve desempenhar

Permitir que os programas armazenem e obtenham informação; Isolar os programas dos detalhes específicos de hardware; Controlar o fluxo de dados entre os componentes de um computador; Permitir que os programas sejam executados sem a interferência de

outros programas; Permitir que os programas independentes cooperem periodicamente e

compartilhem informações; Responder aos erros ou a solicitações dos usuários; Impor um escalonamento entre programas que solicitam recursos; Facilitar o acesso aos recursos do sistema.

9


Busca do Setor de Boot

Quando o computador é ligado, um pequeno programa gravado no primeiro ou nos dois primeiros setores do disco (BOOT) é carregado para memória automaticamente. Sua função será unicamente ler o sistema operacional para RAM.

10


BOOT

Em computação, boot é o termo em inglês para o processo de iniciação do computador que carrega o sistema operacional quando a máquina é ligada.

Muitos computadores podem executar apenas códigos existentes na memória de trabalho (ROM ou RAM); os sistemas operacionais modernos são normalmente armazenados em disco rígido, CD-ROM ou outros dispositivos de armazenamento. Logo que o computador é ligado, ele não tem um sistema operacional na memória. O computador hardware não pode fazer as ações do sistema operacional, como carregar um programa do disco; assim um aparente insolúvel paradoxo é criado: para carregar o sistema operacional na memória, precisamos de um sistema operacional já carregado.

11


Sistema de iniciação ou Boot loader

A solução para o paradoxo está na utilização de um pequeno e especial programa, chamado sistema de iniciação, boot loader ou bootstrap. Este programa não tem a completa funcionalidade de um sistema operacional, mas é especialmente construído para que seja capaz de carregar um outro programa para permitir a iniciação do sistema operacional. Freqüentemente, boot loaders de múltiplos estágios são usados, neste caso vários pequenos programas se complementam em seqüência, até que o último deles carrega o sistema operacional.

12


Modo Real

Os programas podem acessar diretamente posições de memória, executar operações de E/S de baixo nível ou acessar diretamente o hardware de periféricos.

Os programas executados em MODO REAL podem ter o completo controle do computador.

O processsamento em MODO REAL é inaceitável em ambiente multiprogramação pois permite que os programas se afetem mutuamente.

13


Modo Protegido

Os programas não podem acessar diretamente posições de memória, executar operações de E/S de baixo nível ou acessar diretamente o hardware de periféricos.

O SO mantém um estrito controle de cada aplicação, protegendo cada programa de outros programas.

O processsamento em MODO PROTEGIDO é aceitável em ambiente multiprogramação

14


Estruturas de Processamento

Existem 5 estruturas básicas de processamento:

- monousuário

- multiusuário

- multitarefa

- multiprogramação

- multiprocessamento.

15


Monousuário

Nesta estrutura de processamento somente um programa é executado de cada vez e apenas por um usuário também de cada vez.

Multiusuário

Nesta estrutura de processamento além de multiprogramação vários usuários passam a compartilhar o mesmo computador.

A arquitetura tradicional é um computador central e vários terminais, chamados de terminais burros por não terem capacidade de processamento próprio.

16


Multitarefa

Nesta estrutura de processamento é permitido a realização de diferentes tarefas simultaneamente.

Exemplos de tarefas que podem ser realizadas simultaneamente:

imprimir editar um texto gravar um programa em disco enviar dados por modem.

Na Multitarefa o processador trabalha em várias partes de um mesmo programa e não em vários programas concorrentemente.

17


MULTITAREFA PREEMPTIVA (Unix e Win 95 (osr2), 98, XP, VISTA)

Em um sistema Multitarefa preemptivo, cada encadeamento é executado durante um tempo determinado ou até que outro encadeamento de prioridade maior esteja pronto para ser executado.

Como o agendamento é controlado pelo sistema operacional sem a cooperação do aplicativo, torna-se mais difícil para um programa ou encadeamento monopolizar o processador.

Para impedir que encadeamentos de processos diferentes tenham acesso a um recursos que não podem ser compartilhados (como uma porta serial), o programa pode definir semáforos (sinalizadores especiais utilizados pelo programa) para bloquear este recurso até que ele termine de ser utilizado. No Windows 95-OSR2, programas do MS-DOS e de 32 bits baseados no Windows são Multitarefa Preemptiva.

18


MULTITAREFA COOPERATIVA (Windows 95 e 3.11)

Na técnica de MULTITAREFA COOPERATIVA, cada processo controla a CPU até decidir libertá-la.

Em sistema Multitarefa cooperativos, um encadeamento é executado até que voluntariamente abandone o processador.

O programa determina quando o encadeamento pára a execução. No Windows 95, programas de 16 bits baseados no Windows são Multitarefa de modo cooperativo.

19


Multiprogramação

Nesta estrutura de processamento é permitido a execução concorrente, ou aparentemente simultânea de múltiplos programas por um único computador.

Multiprocessamento

Nesta estrutura o sistema multiusuário usa múltiplos processadores para executar um ou vários programas. Também é chamado de processamento paralelo.

20


SO Distribuido / Paralelo

21

Sistema Operacional Distribuído

• Um sistema operacional distribuído deve se apresentar aos usuários como um sistema operacional centralizado, mas que, na realidade, tem suas funções executadas por um conjunto de máquinas independentes;• Sistemas fracamente acoplados, pois cada processador tem a sua memória local.• Excelente para compartilhamento de recursos• Incrementa a velocidade de computação – realiza compartilhamento de carga.


22

Sistema Operacional Paralelo

• Sistemas multiprocessados com uma ou mais CPU em comunicação próxima.

• Sistema fortemente acoplados, processadores compartilham memória e um clock.

•Maior throughput


23

Multiprocessamento Simétrico (SMP- Symmetric multiprocessing)

• Cada processador executa uma cópia idêntica do SO• Muitos processos podem executar ao mesmo tempo, sem deterioração do desempenho• Grandes parte dos sistemas operacionais modernos suportam SMP

Multiprocessamento Assimétrico

• A cada processador é atribuída uma tarefa específica ;• Princípio de funcionamento é que um processador,denominado mestre, aloca trabalho para o outro processador, denominado escravo.


24


Sistemas fortemente acoplados

• Permitem que os programas dos usuários sejam divididos em

subprogramas, para execução simultânea em mais de um processador• Sistemas Assimétricos• Sistemas Simétricos• Multiprocessamento

25


Sistemas fracamente acoplados

• Permitem que as máquinas e os usuários de um sistema distribuído

sejam completamente independentes (ex: rede de PCs que compartilham

recursos, como uma impressora, via uma rede local - LAN)

• Sistemas Operacionais de Rede

• Sistemas Operacionais Distribuídos

26


Sistema Operacional como Gerenciador de Recursos

27


SISTEMA OPERACIONAL COMO GERENCIADOR DE RECURSOS

Normalmente os SOs são encarados como gerenciadores de recursos, responsáveis principalmente pela atualização permanente do estado de cada recurso, definição da política de alocação de recursos (quem recebe, quanto e o que) e a liberação dos mesmos.

Os SOs podem ser divididos em quatro gerências:

gerência de memória

gerência de processador

gerência de periféricos

gerência de informações.

28


Gerência de Memória

A Gerência de Memória tem como função primordial manter atualizado o estado de memória, isto é, controlar as partes de memórias que estão sendo utilizadas, identificar quem as está usando e supervisionar as áreas disponíveis.

Além disso, determina a alocação de mais memória (quando e quanto), garante a integridade das áreas de programa, impedindo que outro processo acesse posições de memórias reservadas para um determinado programa, e libera com facilidade as áreas de memórias quando um processo não mais delas precisa.

29


Gerência de Processador

A Gerência de Processador, através de seus vários módulos, é responsável pelo controle de todos os processos em andamento num computador.

Veremos mais adiante os vários estágios que passa um processo.

30


Gerência de Periféricos

A Gerência de Periféricos mantém o controle dos periféricos, canais e unidades de controle, decidindo sobre sua alocação e iniciando operações de entrada/saída, bem como garantindo a segurança, isto é, impedindo a utilização indevida de um recurso previamente alocado.

Gerência de Informações

A Gerência de Informações é responsável pelo controle do uso de arquivos, ou seja, abre e fecha arquivos e decide se o processo pode ou não acessar as informações.

31


Kernel

32


Kernel

Kernel de um sistema operacional é entendido como o núcleo. Ele representa a camada mais baixa de interface com o Hardware, sendo responsável por gerenciar os recursos do Sistema Operacional como um todo. É no kernel que estão definidas funções para operação com periféricos (mouse, disco, impressora, interface serial/interface paralela), gerenciamento de memória, entre outros. Resumidamente, o kernel é um conjunto de programas que fornece para os programas de usuário (aplicativos) uma interface para utilizar os recursos do sistema.

33


Kernel

Quanto à sua arquitetura, o kernel pode ser monolíticomonolítico - em um único bloco, com todas as funcionalidades carregadas na memória - ou modular (micro-kernel)modular (micro-kernel) - com os módulos específicos para cada tarefa carregados opcionalmente, dinamicamente e híbridohíbrido.

O kernel é a parte mais importante do sistema operacional, pois, sem ele, a cada programa novo que se criasse seria necessário que o programador se preocupasse em escrever as funções de entrada/saída, de impressão, entre outras, em baixo nível, causando uma duplicação de trabalho e uma perda enorme de tempo. Como o kernel já fornece a interface para que os programas possam acessar os recursos do sistema de um nível mais alto e de forma transparente, fica resolvido o problema da duplicação do trabalho.

34


Kernel

Quando há periféricos ou elementos de um sistema computacional que o kernel não cobre, então se faz necessário escrever a interface para eles, os chamados device drivers. Geralmente, os kernels oferecem uma função para se executar chamadas de sistema, como por exemplo a ioctl() do Linux. Valendo-se dessa função, podem-se escrever rotinas para qualquer dispositivo.

35


Kernel monolítico

Kernel monolítico ou mono-bloco é um kernel que implementa um interface de alto nível para possibilitar chamadas de sistema específicas para gestão de processos, concorrência por parte de módulos dedicados que são executados com privilégios especiais. Alguns exemplos deste tipo de kernel:

Linux; Unix; BSD MS-DOS; e Windows 95, Windows 98 e Windows ME.

36


Kernel monolítico

Diagrama de interação de um kernel monolítico

37


Micro-Kernel

Micro-kernel é um termo usado para caracterizar o sistema cujas funcionalidades do sistema saíram do kernel e foram para servidores, que se comunicam com um núcleo mínimo, usando o mínimo possível o "espaço do sistema" (nesse local o programa tem acesso a todas as instruções e a todo o hardware) e deixando o máximo de recursos rodando no "espaço do usuário" (no espaço do usuário, o software sofre algumas restrições, não podendo acessar alguns hardwares, nem tem acesso a todas as instruções).

38


Micro-Kernel

Diagrama de interação de um micro-kernel

Exemplo de SO : Minix QNX

39


Kernel Híbrido ou em Camadas

Kernel híbrido define um kernel baseado em micro-kernel no qual módulos externos a ele podem executar operações em modo kernel (protegido), a fim de evitar trocas de contexto e melhorar o desempenho geral do sistema.

40


Diagrama de interação de um kernel híbrido

Exemplo de So: Microsoft Windows NT, XP, 2000, Vista.

Kernel Híbrido

ou em Camadas

41


Concorrência

42

Concorrência

A possibilidade de o processador executar instruções em

paralelo com operações de E/S permitem que diversas tarefas

sejam executadas concorrentemente. O conceito de

concorrência é o principio básico para o projeto e a

implementação dos sistemas multiprogramáveis.


43

Concorrência

A utilização concorrente da UCP deve ser implementada de

maneira que, quando um programa perde o uso do processador

e depois retorna para continuar sua execução, seu estado deve

ser idêntico ao do momento em que foi interrompido. O

programa deverá continuar sua execução exatamente na

instrução seguinte àquela em que havia parado, aparentando ao

usuário que nada aconteceu.


44


Interrupção e Exceção

45

Interrupção e exceção

Durante a execução de um programa, alguns eventos

inesperados podem ocorrer, ocasionando um desvio forçado no

seu fluxo de execução. Estes tipos de eventos são conhecidos

por interrupção ou exceção e podem ser conseqüência da

sinalização de algum dispositivo de hardware externo ao

processador ou da execução de instruções do próprio programa.

A diferença entre interrupção e exceção é dada pelo tipo evento

ocorrido.


46

Interrupção

É o mecanismo que o sistema operacional sincroniza a execução de todas as sua rotinas e dos programas dos usuários, além de controlar dispositivos.

É sempre gerada por algum evento externo ao programa e, neste caso, independe da instrução que está sendo executada. Um exemplo de interrupção ocorre quando um dispositivo avisa ao processador que alguma operação de E/S está completa. Neste caso, o processador deve interromper o programa para tratar o término da operação.


47

Interrupção

Ao final da execução de cada instrução, a unidade de controle verifica a ocorrência de algum tipo de interrupção. Neste caso, o programa em execução é interrompido e o controle desviado para uma rotina responsável por tratar o evento ocorrido, denominada rotina de tratamento de interrupção. Para que o programa possa posteriormente voltar a ser executado, é necessário que, no momento da interrupção, um conjunto de informações sobre a sua execução seja preservado. Essas informações consistem no conteúdo registradores, que deverão ser restaurados para a continuação do programa.


48

Interrupção

As interrupções são decorrentes de eventos assíncronos, ou

seja, não relacionados à instrução do programa corrente. Como

por exemplo dispositivo de E/S informar ao processador que

está pronto para receber ou transmitir dados.


49

Exceção

Uma exceção é semelhante a uma interrupção, sendo a principal

diferença o motivo pela qual o evento é gerado. A execução é

resultado direto da execução de uma instrução do próprio programaexecução de uma instrução do próprio programa,

como a divisão de um número por zero ou a ocorrência de overflow em

uma operação aritmética.

A diferença fundamental entre exceção e interrupçãoexceção e interrupção é que a primeira

é gerada por um evento síncronosíncrono, enquanto a segunda é gerada por

eventos assíncronosassíncronos. Um evento síncrono quando é resultado direto da

execução do programa corrente.


50


• Intervenção do Sistema Operacional na execução de um programa devido a ocorrência de um evento

• Causas da interrupção:

• Resultado da execução de instruções de um programa (Exceção)

•Gerado pelo sistema operacional (Interrupção)

• Gerado por algum dispositivo de hardware (Interrupção)

• O fluxo da execução do programa é desviado para uma rotina especial de tratamento


51



52

Interrupção

Genericamente as interrupções podem ser de 2 tipos:

• Interrupção de Software (System call ou TRAP)

• Interrupção de Hardware (IRQ)


53

INTERRUPÇÃO DE SOFTWARE - System Call ou TRAP

A interrupção de software é um sinal de interrupção gerado por uma

instrução especial (portanto por software) denominada chamada do

sistema (system call) ou chamada do supervisor (supervisor call).

Alguns autores também chamam as interrupções geradas por software

de TRAP (armadilha). Um TRAP desencadeia as mesmas ações

desencadeadas por uma interrupção de hardware, isto é, o programa

em execução é suspenso, informações são salvas e uma rotina

específica do SO é executada.


54

System Call ou TRAP

Resumindo: Em computação, uma chamada de sistema

(system call) é o mecanismo usado pelo programa para

requisitar um serviço do sistema operacional, ou mais

especificamente, do kernel do sistema operacional.


55


System Call ou TRAP

É a interface entre os programas dos usuários e o Sistema Operacional

56

Interrupção de Hardware

Uma interrupção de hardware é um sinal originado em algum dispositivo físico, que

faz com que a UCP suspenda a execução do programa que vinha executando

(guardando informações para continuar a execução desse programa, mais tarde) e

passe a executar uma rotina específica que trate da interrupção ocorrida.

Interrupções de hardware são geradas pelos diversos periféricos (discos, teclados,

impressoras etc.) ou pelo relógio. O relógio (timer) timer) é um dispositivo que

decrementa automaticamente o conteúdo de um registrador, com uma freqüência

constante, e interrompe a CPU quando o valor do registrador atinge zero.


57


Uma IRQ (abreviação para Interrupt Request) é a forma pela

qual componentes de hardware requisitam tempo computacional

da CPU. Uma IRQ é a sinalização de um pedido de interrupção

de hardware.


58


Os computadores modernos compatíveis com o IBM PC possuem

16 designações de IRQ (0-15), cada uma delas representando

uma peça física (ou virtual) de hardware. Por exemplo, a IRQ0 é

reservada para o temporizador do sistema, enquanto a IRQ1 é

reservada para o teclado. Quanto menor for o número da IRQ,

mais crítica é sua função.


59

Tratamento de Interrupções de Dispositivos de E/S

O dispositivo de E/S interromperá a CPU assim que terminar de atender

uma I/O request

Quando um pedido de E/S é iniciado o SO varre a tabela de status dos

dispositivos (device status table) para saber o status do dispositivo

(ocupado, livre, não disponível).

No caso de ocupado o SO adiciona o pedido na lista de pedidos

pendentes - processo “BloqueadoBloqueado”


60

Tratamento de Interrupções de Dispositivos de E/S

Quando um dispositivo acaba sua tarefa interrompe a CPU, avisando o

término do tratamento de E/S.

O SO identifica qual dispositivo fez a interrupção, consulta a lista de

pedidos pendentes e trata o próximo pedido (BloqueadoBloqueado -> EsperaEspera)

O processo que estava em Espera aguardando o término da E/S é

colocado na lista de processos prontos. (EsperaEspera -> ProntoPronto)


61

Proteção do Sistema

•Objetivo: garantir a integridade dos dados pertencentes a cada usuário.

•Vários programas ocupam a memória simultaneamente e cada usuário

possui uma área onde dados e códigos são armazenados => o SO deve

preservar as informações contra acessos indevidos (confiabilidade)

•Proteção aos recursos compartilhados do sistema: memória, dispositivos

de E/S e CPU

•Quando o programa tenta acessar uma posição de memória fora de sua

área endereçável (erro de violação de acesso) o programa é encerrado.


62


•No estado usuário somente são executadas instruções não privilegiadas

(não afetam diretamente outros programas)

•Caso um programa tente executar uma instrução privilegiada, sem estar

no modo supervisor, uma interrupção é gerada e o programa é encerrado.

•O estado de execução de um processo é determinado por um conjunto de

bits, localizado em um registrador especial da CPU (PSW - Process Status

Word) - indica se uma instrução pode ou não ser executada.


63


Divisão da área de memória do SO:

•Espaço de Endereçamento do Sistema (EES) : parte de endereços

mais baixa, reservada para o próprio SO

•Espaço de Endereçamento do Usuário (EEU) : parte de endereços

mais altos, reservada para os programas dos usuários.


64


•Programas dos usuários só podem ter acesso ao EES (área reservada do

SO) via “systems call”, que é invocado sempre que um processo precisa

ter acesso a algum serviço disponível.


65

EESAcesso

Privilegiado

EEUUsuário


System call

66


System Call

67


Entrada e Saída

68


Gerenciamento de Entrada e Saída

Uma das principais funções de um sistema operacional é controlar

todos os dispositivos de E/S.

Ele deve enviar comandos para os dispositivos, capturar

interrupções e tratar erros.

Também deve oferecer uma interface entre os dispositivos e o

restante do sistema que seja simples e fácil de usar.

Na medida do possível, a interface deve ser a mesma para todos os

dispositivos. (TanenbaumTanenbaum)

69


Gerenciamento de Entrada e Saída

Nos primeiros sistemas computacionais, a comunicação entre o processador e os periféricos era controlada por um conjunto de instruções especiais, denominadas instruções de entrada/saída, executadas pelo próprio processador. O surgimento do controlador de interface permitiu ao processador agir de maneira independente dos dispositivos de E/S. Com esse novo elemento, o processador não mais se comunicava diretamente com os periféricos, mas sim através do controlador. Isso simplificou as instruções de E/S, por não mais ser necessário especificar detalhes de operação dos periféricos, tarefa esta realizada pelo controlador.

70


71


Dispositivos de E/S

Os dispositivos de E/S podem ser divididos em duas categorias:

Dispositivos de Blocos; e

Dispositivos de Caractere.

72


Dispositivo de Bloco

Um dispositivo de bloco, armazena as informações em blocos de tamanho fixo, cada um com seu próprio endereço. A propriedade essencial de um dispositivo de bloco é que é possível ler ou gravar cada bloco independente de todos os outros. Os Discos são os dispositivos de blocos mais comuns.

É endereçável e possui operações de busca (Exemplo: Busca de um dado no disco rígido).

73


Dispositivo de Caractere

É o dispositivo que entrega ou aceita um fluxo de caracteres sem considerar qualquer estrutura de bloco. Ele não é endereçável e tampouco tem qualquer operação de busca.

Exemplos: Impressoras, interfaces de rede, mouse.

74


Não é dispositivo Bloco ou Caractere

Os relógios não são endereçáveis por bloco, tampouco aceitam fluxo de caracteres.

Tudo que fazem é gerar interrupções em intervalos bem definidos.

75


Controle das Operações de Entrada e Saída:

E/S controlada por programa;

E/S controlada por Pooling; e

E/S Controlada por Interrupção;

76


E/S controlada por programa

Neste tipo de operação, o processador sincronizava-se com o periférico para o início da transferência de dados e, após iniciada a transferência, o sistema ficava permanentemente testando o estado do periférico para saber quando a operação chegaria ao seu final.

Este controle, chamado e E/S controlada por programa, mantinha o processador ocupado até o término da operação de E/S (busy wait).

Como o processador executa uma instrução muito mais rapidamente que a realização de uma operação de E/S pelo controlador, havia um enorme desperdício de tempo da UCP.

77


E/S controlada por Pooling

A evolução do modelo anterior foi permitir que, após o início da transferência dos dados, o processador permanecesse livre para realizar outras tarefas. Assim, em determinados intervalos de tempo, o sistema operacional deveria testar cada dispositivo para saber do término da operação de E/S (polling). Esse tipo de operação introduziu certo grau de paralelismo, visto que um programa poderia ser processado, enquanto outro esperava pelo término de uma operação de E/S. Isso permitiu o surgimento dos primeiros sistemas multiprogramáveis, onde vários programas poderiam ser executados concorrentemente, já que o tempo de uma operação de E/S é relativamente grande.

78


E/S Controlada por Interrupção

Com a implementação do mecanismo de interrupção, as operações de E/S puderam ser realizadas de uma forma mais eficiente. Em vez de o sistema periodicamente verificar o estado de uma operação pendente, o próprio controlador interrompia o processador para avisar do término da operação. Com esse mecanismo, denominado E/S controlada por E/S controlada por interrupçãointerrupção, o processador, após a execução de um comando de leitura ou gravação, permanece livre para o processamento de outras tarefas.

79


E/S Controlada por Interrupção

A operação de E/S controlada por interrupção é muito mais eficiente que a controlada por programa, já que elimina a necessidade de o processador esperar pelo término da operação, além de permitir que várias operações de E/S sejam executadas simultaneamente. Apesar disso, a transferência de grande volume de dados exige muitas intervenções do processador, reduzindo sua eficiência. A solução para esse problema foi a implementação de uma técnica de transferência de dados denominada DMA (Direct Memory Access).

80


Controladora

Uma placa controladora é uma parte do hardware de computadores que comanda outras partes da máquina. Normalmente é conectada na placa-mãe através de slots apropriados de acordo com o barramento relativo à placa.

81


Device driver

Device driver (Controlador de Dispositivo) é uma camada de software que implementa um conjunto de funções que realiza a comunicação com o dispositivo.

Device driver é o comando de um dispositivo ou programa. É a forma a partir da qual uma unidade periférica cria uma interface com o sistema operacional para se conectar com o dispositivo do hardware.

82


83


DMA

84


DMA

Está técnica permite que um bloco de dados seja transferido entre a memória principal e dispositivos de E/S; sem a intervenção do processador, exceto no início e o final da transferência.

Quando o sistema deseja ler ou gravar um bloco de dados, o processador informa ao controlador sua localização, o dispositivo de E/S, a posição inicial da memória de onde os dados serão lidos ou gravados e o tamanho do bloco.

85


DMA

Com estas informações, o controlador realiza a transferência entre o periférico e a memória principal, e o processador é interrompido somente no início e no final da operação. A área de memória utilizada pelo controlador na técnica de DMA é chamada de bufferbuffer de entrada/saída.

No momento em que uma transferência de dados através da técnica de DMA é realizada, o controlador deve assumir, momentaneamente, o controle do barramento.

86


Canal de Entrada e Saída

87



A extensão do conceito de DMA possibilitou o surgimento do canal de entrada/saída.

O canal é um processador com capacidade de executar programas de E/S, permitindo o controle total sobre operações de E/S. As instruções de E/S são armazenadas na memória principal pelo processador, porém o canal é responsável pela sua execução.

Assim, o processador realiza uma operação de E/S, instruindo o canal para executar um programa localizado na memória (programa de canal).

88



Este programa especifica os dispositivos para transferência, buffers e ações a serem tomadas em caso de erros.

O canal de E/S realiza a transferência e, ao final, gera uma interrupção, avisando do término da operação. Um canal de E/S pode controlar múltiplos dispositivos através de diversos controladores.

Cada dispositivo, ou conjunto de dispositivos, é manipulado por um único controlador. O canal atua como um elo de ligação entre o processador e o controlador.

89


90



A evolução do canal permitiu que este possuísse sua própria memória, eliminando a necessidade de os programas de E/S serem carregados para a memória principal. Com essa nova arquitetura, varias funções de E/S puderam ser controladas com mínima intervenção da UCP. Esse estágio do canal é também denominado processador de entrada/saída.

91


Buffering

92


Buffering

A técnica de buffering consiste na utilização de uma área na memória principal, denominada buffer, para a transferência de dados entre os dispositivos de E/S e a memória. Essa técnica permite que uma operação de leitura o dado seja transferido primeiramente para o buffer, liberando imediatamente o dispositivo de entrada para realizar uma nova leitura.

O objetivo principal desta técnica é minimizar o problema da disparidade da velocidade de processamento existente entre a UCP e os dispositivos de E/S, mantendo-os ocupados na maior parte do tempo.

93


Buffering

94


Spooling

95


Spooling

A técnica de spooling (simultaneous peripheral operation on-line), é semelhante à técnica de buffering, utiliza uma área em disco como se fosse um grande buffer. Neste caso, dados podem ser lidos ou gravados em disco, enquanto programas são executados concorrentemente.

Atualmente essa técnica está presente na maioria dos sistemas operacionais, sendo utilizada no gerenciamento de impressão.

96


Spooling

No momento em que um comando de impressão é executado, as informações que serão impressas são gravadas antes em um arquivo em disco, conhecido como arquivo de spool, liberando imediatamente o programa para outras atividades. Posteriormente, o sistema operacional encarrega-se de direcionar o conteúdo do arquivo de spool para a impressora.

97


Spooling

98


Reentrância

99


Reentrância

É a capacidade de um código executável (código reentrante) ser compartilhado por diversos usuários, exigindo que apenas uma cópia do programa esteja na memória.

A reentrância permite que cada usuário possa estar em um ponto diferente do código reentrante, manipulando dados próprios, exclusivos de cada usuário.

100


Reentrância

101


Pipeline

102


Pipeline

É uma técnica que permite ao processador executar múltiplas instruções paralelamente em estágios diferentes.

Pipeline é uma técnica de hardware que permite que a CPU realize a busca de uma ou mais instruções além da próxima a ser executada. Estas instruções são colocadas em uma fila de memória (dentro da CPU) onde aguardam o momento de serem executadas.

A técnica de pipeline é utilizada para acelerar a velocidade de operação da CPU, uma vez que a próxima instrução a ser executada está normalmente armazenada dentro da CPU e não precisa ser buscada da memória, normalmente muito mais lenta que a CPU.

103


Chamadas de Sistemas

104



É a interface entre o Sistema operacional e seus programas aplicativos.

Em computação, uma chamada de sistema (system call) é o mecanismo usado pelo programa para requisitar um serviço do sistema operacional, ou mais especificamente, do kernel do sistema operacional.

105



Podem ser:

Gerenciamento de Processos;

Gerenciamento de Sinalização;

Gerenciamento de Arquivos;

Gerenciamento de Diretórios e Sistemas de Arquivos; e

Gerenciamento de Tempo.

106


Gerenciamento de Processo

Trata os estados que o processo passa, deste a sua criação (running, ready, wait, blocked).

Subprocesso e Thread.

Será coberto no tópico PROCESSO, adiante......

107


108


Gerenciamento de Sinalização

Em alguns casos é necessário intervir na execução de um processo, seja por motivos planejados ou por instruções ilegais passadas ao sistema (falhas).

Por exemplo se um usuário instrui um editor de texto a imprimir o conteúdo deste arquivo, e então verifica que não quer mais imprimir, deverá haver uma maneira de interromper o editor e eliminar o processo, neste caso é utilizado a chamada kill.

109


110


Gerenciamento de Arquivo

Muitas chamadas de sistemas estão relacionadas com o sistema de arquivos e os seus métodos de acesso, como por exemplo, solicitações de: criação, leitura e exclusão de arquivos.

A criação de um arquivo pode ser definida como uma chamada creat(“abc”,751), assim um novo arquivo denominado abcabc seria gerado com permissões 77 – ler, gravar e executar para o proprietário; 55 – ler e executar para o grupo e 11 – apenas executar para os outros. (RWX).

111


112


Gerenciamento de Diretórios e Sistemas de Arquivos

São as chamadas que se relacionam com diretórios ou com o sistema de arquivos, como um todo, em vez de um arquivo específico.

Em se tratando de gerenciamento de diretórios, as duas chamadas mais importantes seriam: mkdirmkdir e rmdirrmdir, que permitem a criação e remoção de diretórios.

Outra chamada importante neste grupo são aquelas que tratam “montarmontar” um dispositivo para permitir o acesso aos seus diretórios e arquivos, como exemplo o comando “mountmount” para disponibilizar e “umountumount” para interromper o seu uso.

113


114


Gerenciamento de Tempo

Basicamente trata-se de chamadas de sistema que envolvem o tempo de relógio convencional. Entre as possibilidades estão, exemplo:

Time: que retorna a hora do sistema;

Stime: Relógio possa ser configurado pelo Superusuário;

Utime: Permite que o arquivo tenha definido os atributos de data e hora de criação e modificação; e

TimeS: Retorne o tempo de utilização da CPU.

115


116


Processo

117


Processo

Em Sistemas Operacionais, processo é um módulo executável único, que roda concorrentemente com outros módulos executáveis. Por exemplo, em um ambiente multi-tarefa (como o Unix) que suporta processos, um processador de texto, um navegador e um sistema de banco de dados são processos separados que podem rodar concomitantemente. Processos são módulos separados e carregáveis, ao contrário de threads, que não podem ser carregadas. Múltiplas threads de execução podem ocorrer dentro de um mesmo processo. Além das threads, o processo também inclui certos recursos, como arquivos e alocações dinâmicas de memória.

118


Program a

C ontexto deSo ftw are

p riorida de deexecuçã o reg istra dor PC

d a ta / h orad e cria çã o

tem po d ep rocessa dor

reg istra dor SP

q uota s

p rivilég ios

en dereços d e m em óriap rincipa l a loca dos

reg istra dord e sta tus

own er (U ID )PID

nom ereg istra dores

g era is

C ontexto d eH ardw are

Espaço deEndereça mento

119


Processo

Um processo é basicamente um programa em execução, sendo constituído do código executável, dos dados referentes ao código, além de outras informações necessárias à execução do programa.

120


Processo

Um processo, em um sistema multiprogramável, não é executado todo o

tempo pelo processador. Durante sua existência, passa por uma série de

estados. Basicamente existem três:

Execução (running): quando está sendo processado pela UCP.

Pronto (ready): quando apenas aguarda uma oportunidade para

executar, ou seja, espera que o SO aloque a UCP para sua

execução. O SO é responsável por determinar a ordem pela qual os

processos em estado de pronto devem ganhar a UCP. Normalmente

existem vários processos no estado de pronto.

121


Processo

Espera (wait): quando aguarda algum evento externo ou por

algum recurso para poder prosseguir seu processamento. Ex.: o

término de uma operação de E/S ou a espera de uma

determinada data para poder continuar sua execução.

Quando o processo espera por um recurso do sistema que não

se encontra disponível, é dito que o processo está no estado de

bloqueado (blocked) em vez de espera (wait).

122


Processo

• A diferença básica entre o estado de bloqueado e o de espera é

que um processo bloqueado espera ser autorizado a utilizar um

recurso, enquanto o processo em estado de espera aguarda pela

conclusão de uma operação em um recurso que já foi garantido.

• Um processo em estado de pronto ou de espera pode não se encontrar, momentaneamente, na memória principal, ou seja, armazenado na memória secundária. Uma técnica denominada Swapping pode retirar processos da mamória principal quando não existe espaço suficiente para todos os processos.

123


Processo

• O SO gerencia os processos através de listas, são estas: listas de processos em estado de pronto e listas de processos no estado de espera.

• Um processo muda de estado diversas vezes, durante seu

processamento, em função de eventos originados por ele próprio

(eventos voluntários) ou pelo sistema operacional (eventos

involuntários)

124


Processo

• Eventos originados pelo próprio processo: operação de E/S (SVC) ou

qualquer chamada a uma rotina do sistema, requisitando algum tipo de

serviço

• Eventos que se originem do SO têm a intenção de permitir maior

compartilhamento dos recursos do sistema (Ex.: se um programa está

em looping, o sistema deve intervir para que o processador não fique

dedicado eternamente ao processo onde o programa está sendo

executado.

125


Basicamente, existem 4 mudanças de estado que podem ocorrer a um

processo (Diagrama de Transição de Estado):

1 . Pronto - Execução: quando um processo é criado, o sistema o coloca em uma lista de processos no estado de pronto, onde aguarda uma oportunidade para ser executado. Cada SO tem seus próprios critérios e algoritmos para a escolha da ordem em que os processos serão executados (escalonamento ou schedulling)

2 . Execução - Espera: um processo em execução passa para o estado de espera por eventos gerados pelo próprio processo, como por exemplo, uma operação de E/S. Nesse caso o processo ficará nesse estado esperando pela conclusão do evento solicitado.

126


3 . Espera - Pronto: um processo em espera passa para pronto quando a operação solicitada é atendida ou o recurso esperado é concedido. Um processo em espera sempre terá de passar pelo estado de pronto antes de poder ser novamente selecionado para execução. Não existe a mudança do estado de espera para o estado de execução diretamente.

4 . Execução - Pronto : um processo em execução passa para o estado de pronto por eventos gerados pelo sistema, como por exemplo, o fim da fatia de tempo que o processo possui para sua execução. Nesse caso, o processo volta para a fila de processos prontos, onde aguarda uma nova oportunidade para continuar seu processamento.

127


CriaçãoPronto Espera

Execução

DespachoInterrupção

Time-Slice

Serviço

Fim Anormal

Fim Normal

Periféricos

Recurso Atendido

Processo

ou BLOQUEADO

128


Principais filas de processos

Fila de Pronto(Ready): Quando um processo é criado, o sistema o coloca em uma fila de processos no estado de pronto, onde aguarda uma oportunidade para ser executado.

Fila de Espera(Wait): Quando aguarda algum evento externo ou por algum recurso para poder prosseguir seu processamento.

Fila de Bloqueado(Blocked): Quando o processo espera por um recurso do sistema que não se encontra disponível.

129


Processo

Quando um processo passa a maior parte do temp no estado de execução, a este chamamos de CPU BOUND. Este tipo de processo é muito comum em aplicações matemáticas, científicas e gráficas por efetuarem muitos cálculos.

Quando o processo passa a maior parte do tempo em estado de espera e realizando muitas operações de I/O, a este chamamos de I/O BOUND. É o processo mais comum em aplicações comerciais.

130


Subprocesso e Thread

131

SUBPROCESSO

Um processo pode criar outros processos de forma hierárquica.

•Quando um processo (processo pai) cria outro processo, chamamos de subprocesso ou processo filho.

•O subprocesso pde criar outros subprocessos.

•Como conseqüência dessa estrutura, caso um processo deixe de existir, os subprocessos subordinados são eliminados.


132

SUBPROCESSO

•A utilização de subprocessos permite dividir uma aplicação em partes que podem trabalhar de forma concorrente.Com o uso de subprocessos, cada solicitação implicaria a criação de um novo processo para atendê-la, aumentando o throughput da aplicação e, conseqüentemente, melhorando seu desempenho.•O uso de subprocessos no desenvolvimento de aplicações concorrentes demanda consumo de diversos recursos do sistema.•Sempre que um novo processo é criado (no Unix isto é feito pela system call fork), o SO deve alocar recursos (contexto de HW, contexto de SW e espaço de endereçamento) para cada processo além de consumir tempo de UCP neste trabalho.


133

THREAD

Thread, ou linha de execução em português, é uma forma de um processo dividir a si mesmo em duas ou mais tarefas que podem ser executadas simultaneamente. O suporte à thread é fornecido pelo próprio sistema operacional (SO).

Uma linha de execução permite que o usuário de programa, por exemplo, utilize uma funcionalidade do ambiente enquanto outras linhas de execução realizam outros cálculos e operações.


134

THREAD

Em hardwares equipados com uma única CPU, cada linha de execução(Thread) é processada de forma aparentemente simultânea, pois a mudança entre uma linha e outra é feita de forma tão rápida que para o usuário isso está acontecendo paralelamente. Em hardwares com multiplos CPUs ou milti-cores as linhas de execução(Threads) podem ser realizadas realmente de forma simultânea;Os sistemas que suportam apenas uma única linha de execução são chamados de monothread e aqueles sistemas que suportam múltiplas linhas de execução são chamados de multithread.


135

THREAD

•Threads compartilham o processador da mesma maneira que processos.

•Cada linha de execução tem o mesmo contexto de software e compartilha o mesmo espaço de memória (endereçado a um mesmo processo pai), porém o contexto de hardware é diferente. Sendo assim o overhead causado pelo escalonamento de linha de execução é muito menor do que o escalonamento de processos, entretanto, não há acesso protegido a memória nativamente (sua implementação fica a cargo do programador) devido ao compartilhamento do espaço de memória.


136

THREAD

Basicamente uma linha de execução pode assumir os seguintes estados:

Criação Neste estado, o processo pai está criando a thread que é levada a fila de prontos; Execução Neste estado a linha de execução está usando a CPU; Pronto Neste estado a linha de execução avisa a CPU que pode entrar no estado de execução e entra na fila de prontos; Bloqueado Neste estado, por algum motivo, a CPU bloqueia a linha de execução, geralmente enquanto aguarda algum dispositivo de I/O; Término Neste estado são desativados os contextos de hardware e a pilha é deslocada


137


Multiprogramação

138


Multiprogramação

Num sistema multiprogramado, mesmo que só exista um processador é possível vários processos estarem activos simultaneamente

Contudo, em cada instante temporal, apenas um deles pode utilizar o processador

A esta ilusão de vários processos correrem aparentemente em paralelo, dá-se o nome de pseudo-paralelismo

139


Multiprogramação

Depois de uma comutação do processador, o próximo processo a utilizá-lo é escolhido pelo sequenciador de processos do SO (Escalonador).

Concorrência

– Os vários processos “competem” entre si pela atenção do processador.

140


Multiprogramação

Cooperação

– Processos podem trabalhar em conjunto para a realização de tarefas mais complexas.

– Esta cooperação exige ao SO a existência de mecanismos de sincronização e comunicação entre processos

141


Comunicação Interprocesso

142


Comunicação Interprocessos

A comunicação entre processos, em inglês Inter-Process

Communication (IPC), é o grupo de mecanismos que permite

aos processos transferirem informação entre si.

143


Comunicação Interprocessos

Deveremos verificar 3 questões envolvidas neste processo de comunicação (Regras para programação concorrente):

1 – Como um processo pode passar informações para outro processo;

2 – Deverá ser certificado que dois ou mais processos não interfiram um com outro quando envolvidos em atividades críticas;

3 – O seqüenciamento adequado quando estão presentes dependências: Se o processo A produz dados e o processo B os imprime, B tem de esperar ate que A tenha produzido alguns dados antes de começar a imprimir.

144


Condições de Corrida

Situação onde dois ou mais processos estão acessando dados compartilhados e o resultado do processamento depende de quem roda quando.

Quando um processo quer imprimir um arquivo, ele insere o nome deste arquivo em um diretório de spooler. O servidor de impressão verifica periodicamente se há qualquer arquivo a ser impresso e, se houver ele os imprime e, então remove seus nomes do diretório de spooler.

145



Imagine que nosso diretório de spooler esteja vazio, com números de entradas seqüenciais 0,1,2..., cada uma capaz de armazenar um arquivo a ser impresso, imagine também que existem 2 variáveis OUTOUT que aponta para o próximo arquivo a ser impresso e ININ que aponta para a próxima entrada livre no diretório de spooler.

Em nosso exemplo OUT = IN = 0 (zero), ou seja, não, existem arquivos no spooler.

146



Mais ou menos simultaneamente os processos A e B, decidem que querem colocar um arquivo na fila de impressão (spooler).

O processo A lê a variável IN e armazena o valor 0 (zero), em uma variável local de controle (next_free_slot), só que acontece uma interrupção de relógio, e a CPU decide que o processo A executou por tempo suficiente (Time Slice) e então alterna para o processo B .

147



148



O processo B também lê a variável IN e também recebe 0 (zero) e escreve o nome do seu arquivo na posição 0 (zero) do spooler.

149



150



Por fim o processo executa novamente, iniciando do lugar que parou, ela examina a sua variável de controle (next_free_slot) e encontra o valor 0 (zero), então escreve o nome do arquivo na posição zero do spooler, sobrescrevendo o nome do arquivo que o processo B acabou de colocar ali.

Ele então calcula next_free_slot+1 e armazena em IN (1).

O processo B numca realizará qualquer saída, após esta situação.

Para evitar as condições de corrida, precisamos implementar Para evitar as condições de corrida, precisamos implementar algoritmos de exclusão mútua de execução e, para tanto, definimos algoritmos de exclusão mútua de execução e, para tanto, definimos as regiões críticas do processo.as regiões críticas do processo.

151



152


Seções Criticas ou Regiões Críticas

Como evitamos a condição de corrida ?

A chave para prevenir problemas aqui e em muitas outras situações envolvendo memória compartilhada, arquivos compartilhados e tudo mais compartilhado é encontrar alguma maneira de proibir que mais de um processo leia e grave os dados compartilhados ao mesmo tempo.

Dito em outras palavras precisamos de uma exclusão mútuaexclusão mútua – é uma maneira de certificarmo-nos de que se um processo esta utilizando um arquivo ou uma variável compartilhada, ou outros processos serão impedidos de fazer a mesma coisa.

153


Seções Criticas

A dificuldade do exemplo anterior ocorria porque o processo BB começava utilizando uma das variáveis compartilhadas antes de o processo AA ter acabado de ter trabalhado com ela.

A parte do programa cujo processamento, por manipular A parte do programa cujo processamento, por manipular dados compartilhados, pode levar à ocorrência de condições dados compartilhados, pode levar à ocorrência de condições de corrida é chamada REGIÃO CRÍTICA.de corrida é chamada REGIÃO CRÍTICA.

154


Seções Criticas

Objetivo: nunca permitir que dois processos entrem simultaneamente em suas regiões críticas correspondentes (i.e. referentes à mesma variável compartilhada).

Condições para uma boa solução ao problema:

1) Dois ou mais processos não podem estar simultaneamente dentro de suas regiões críticas correspondentes.

2) Nenhum processo rodando fora de sua região crítica pode bloquear a execução de outro processo.

155


Seções Criticas

Condições para uma boa solução ao problema:

3) Nenhum processo pode ser obrigado a esperar indefinidamente para entrar em sua região crítica.

4) Nenhuma consideração pode ser feita a respeito da velocidade relativa dos processos, ou a respeito do número de processadores do sistema.

156


Seções Criticas ou Regiões Críticas

Resumo:

– seção do programa onde são efectuados acessos (para leitura e escrita) a recursos partilhados por dois ou mais processos.

– é necessário assegurar que dois ou mais processos não se encontrem simultaneamente na região crítica.

157


Exclusão Mútua

(Mecanismos de Sincronização)

158


Exclusão Mútua

Espera Ativa (ou Ocupada)

159


Desativando as InterrupçõesDesativando as Interrupções

O processo desativa todas as interrupções logo após entrar em uma região crítica, e as habilita ao sair. Assim, o processo não poderá ser interrompido mesmo após acabar o seu tempo de execução.

Com as interrupções desativadas, nenhuma interrupção de relógio pode ocorrer, com isso a CPU não poderá alternar de um processo para outro.

Sendo assim após o processo desativar as interrupções, ele pode examinar e atualizar a memória compartilhada, sem medo de outro processo intervir.

160



Problemas:

Não é boa prática dar ao usuário a capacidade de ativar interrupções; O processo pode desativar as interrupções e nunca mais ativá-las; Se o sistema é multiprocessado (com 2 ou mais CPUs), desativar as interrupções afeta apenas a CPU que executou a instrução de desativamento.

161



Conclusão:

Desativar interrupções é freqüentemente uma técnica útil dentro do sistema operacional em si, mas não é apropriada como um mecanismo geral de exclusão mútua para processos de usuário.

162


Variáveis de BloqueioVariáveis de Bloqueio

Como uma segunda tentativa, vamos procurar uma solução de software. Considere ter uma variável única compartilhada de nome bloqueiobloqueio (inicialmente com o valor Zero) que pode assumir os seguintes valores/situação:

Variável compartilhada:

– 0: ninguém está na região crítica; – 1: existe alguém na região crítica.

163



Quando um processo quer entrar na sua região crítica, ele primeiro testa o bloqueio. Se o bloqueio for 0, o processo passa o bloqueio para 1 e entra na região crítica.

Se o bloqueio já for 1, ele espera até o bloqueio ir para 0.

164



Problema:

Contém o mesmo erro fatal, visto no spoolerspooler. Suponha que o processo P1 leia o bloqueio e veja que ele é 0, porém antes de ele poder definir o bloqueio como 1, outro processo P2 é agendado, executa e define o bloqueio como 1, quando P1 executa novamente, ele também definirá o bloqueio igual a 1, e os dois processos estarão em suas regiões críticas ao mesmo tempo.

165


Alternância Estrita ou TurnoAlternância Estrita ou Turno

"vezvez": variável compartilhada, inicialmente valendo 0. Se há dois processos (A) e (B), sendo que vez==0 indica a vez do processo (A) entrar em sua região crítica e vez==1, a vez do processo (B).

166


Alternância EstritaAlternância Estrita

Problemas:

Espera ocupada (teste contínuo da variável compartilhada "vez"): consumo desnecessário do tempo do processador (espera ativaespera ativa).

Um processo só terá vez se o outro entrar e sair da sua região crítica. Isto representa uma violação da condição 2violação da condição 2 acima. (Nenhum processo rodando fora de sua região crítica pode bloquear a execução de outro processo. )

Este esquema para exclusão mútua é muito inadequado quando um dos processos é mais lento que o outro.

167


ATENÇÂOATENÇÂO

Testar continuamente uma variável até que algum valor apareça é chamado de espera ativa. espera ativa. Normalmente deve ser evitado, uma vez que desperdiça tempo de CPU.

Somente quando existe uma expectativa de que a espera será curta é que a espera ativa será utilizada.

168


A solução de Peterson

Combinando a idéia de turnos com a de variáveis de bloqueio e variáveis de aviso, foi projetado a primeira solução de softwaresolução de software para o problema da exclusão mútua que não requer alternância estrita.

Antes de utilizar as variáveis compartilhadas(antes de entrar na sua região crítica), cada processo chama a rotina enter_regionenter_region com o seu próprio número de processo (nosso exemplo apenas 2 processos P1 pid 0 e P2 pid 1), como parâmetro. Essa chamada poderá causar espera, se necessário, até que seja seguro entrar.

169


Solução de Peterson

170



Depois que terminou de trabalhar com as variáveis compartilhadas, o processo chama a rotina leave_regionleave_region para indicar que terminou e permitir que o outro processo entre, se ele, então quiser.

Inicialmente nenhum processo está em sua região crítica. Agora o processo P1 (pid 0) chama enter_regionenter_region. Ele indica seu interesse, configurando turnturn com 0, nesta estapa o P2 não possui interesse em sua região crítica, então teremos para P1 os seguintes valores em enter_region, enter_region, a saber:

171


P1 pid 0 então:

Process = 0

Other = 1

Interested[0] = True

Interested[1] = False

Turn=0

While(0==0 and

interested[1]== TRUE)

Sairá do loop

enter_region P1 enter_region P1

172



Se o processo P2 (pid 1) chamar agora enter_regionenter_region, ele ficará parado até que interested[0] seja FALSE, evento que só acontece quando o processo P1 (pid 0) chama leave_regionleave_region para sair da região crítica.

173


P2 pid 1 então:

Process = 1

Other = 0



Turn=1

While(1==1 and

interested[0] == TRUE)

Somente sairá do loop quando P1 (pid 0) chamar leave_regionleave_region

enter_region P2enter_region P2

leave_regionleave_region

P1 pid 0

Sairá do LoopSairá do Loop

174



Agora considere o caso em que os 2 processos P1(pid 0) e P2 (pid 1), chamam a enter_regionenter_region quase simultaneamente. Ambos armazenarão os seus números de processos em turn. Qualquer que seja o armazenamento feito por último, é este que conta, o primeiro é perdido (spooler).Suponha que o processo 1 armazene por último, assim turn é 1. Quando ambos os processos chegam na declaração while, o processo P1 (pid 0) entra em loop e não entra em sua região crítica.

175


P2 pid 1 e turn = 1 então:

Process = 1

Other = 0

Interested[0] = False


Turn=1

While(1==1 and

interested[0] == TRUE)

Sai do loop

enter_region P1 e P2enter_region P1 e P2

P1 pid 0 ... Process =0 .... Other = 1

Interested[0] = True interested[1] = True

Turn=0

While (0=0 and interested[1] == True)

Entra em loop, somente sai P2 leave_regionleave_region

176


Instrução TSL (Test and Set Lock)Instrução TSL (Test and Set Lock)

A instrução TSL é uma chamada de sistema que bloqueia o acesso a memória (bloqueia o barramento) até o término da execução da instrução. Funciona monitorando uma variável compartilhada para coordenar o acesso de Leitura e Escrita na memória, semelhante a solução de Peterson.

177


Exclusão Mútua

Espera Bloqueada

178


Bloqueio e Desbloqueio: Primitivas Sleep/WakeupBloqueio e Desbloqueio: Primitivas Sleep/Wakeup

As soluções por espera ocupada possuem a série deficiência de consumirem muito tempo do processador. Outro problema é o problema de inversão de prioridadeproblema de inversão de prioridade, cuja descrição é dada a seguir:

1) Dois processos L e H, de baixa e alta prioridade;

2) H esta bloqueado e L esta na sua região crítica;

3) Acaba o time slot de L e ele é suspenso;

4) H esta em estado Ready;

179



5) Como H tem maior prioridade que L, então H é executado antes;

6) Entretanto, H deseja entrar em sua região crítica. Como L está na sua região crítica, H entra em loop para verificar se pode entrar em região crítica até esgotar o seu time slot de tempo;

7) No entanto, tanto H como L estão em estado de Ready e sempre H vai ser escolhido para a execução;

8) Dessa maneira, L nunca será executado e deixará sua região crítica e H ficará em loop eterno.

180



A metodologia de Bloqueio e Desbloqueio de processos, propõe o seguinte algoritmo básico:

1) Dois processos H e L;

2) H entra em sua região crítica;

3) H é suspenso pois, terminou seu time slot;

4) L deseja entrar em sua região critica. Ao invés de entrar em loop, onde ficará verificando se o acesso a região crítica está livre até esgotar o seu time slot, ele será bloqueado (blocked) e o processador liberado;

181



A metodologia de Bloqueio e Desbloqueio de processos, propõe o seguinte algoritmo básico:

5) H sai de sua região crítica e desbloqueia L (estava aguardando o recurso), L então entra em estado de Ready e aguarda atendimento para entrar em sua região crítica.

O mecanismo de bloqueio e desbloqueio utiliza 2 primitivas:

Sleep – Bloqueia o processo que chamou; e

Wakeup Desbloqueia um processo pelo PID.

182



A utilização de sleep e wakeup evita esperas ativas, e em conjunto com outros mecanismos (e.g. TSL, Peterson) consegue-se garantir a exclusão mútua

Problema : lost Wakeup signal – um processo manda “acordar” o

outro sem este ter “adormecido” ainda

183


Problema do Produtor e Consumidor (Sleep e Wakeup)

Exemplo de como as primitivas (sleep e wakeup) podem ser utilizadas. Este problema também é conhecido como o problema do buffer limitado.

Assume-se a existência de 2 processos que compartilham um determinado buffer buffer de tamanho fixo, número de itens do buffer count (c)count (c), um chamado ProdutorProdutor que cria dados e aloca no bufferbuffer, e um outro processo chamado ConsumidorConsumidor que retira dados do bufferbuffer .

184



185



Problema:

1) O buffer está cheio e o Produtor deseja colocar mais dados no buffer.

Solução: Bloquear o Produtor e convocar o Consumidor;Solução: Bloquear o Produtor e convocar o Consumidor;

2) O buffer está vazio e o Produtor deseja retirar um dado do buffer.

Solução: Bloquear o Consumidor e convocar o Produtor;Solução: Bloquear o Consumidor e convocar o Produtor;

186



Quando o buffer enche o Produtor executa sleep e vai dormir esperando que o consumidor o acorde (wakeup – pid do Produtor).

Um wakeup executado pelo consumidor ao consumir um dado Um wakeup executado pelo consumidor ao consumir um dado acorda o Produtor.acorda o Produtor.

Quando o buffer esta vazio o Consumidor executa sleep e vai dormir esperando que o Produtor o acorde (wakeup pid do Consumidor).

Um Wakeup executado pelo Produtor ao produzir um dado Um Wakeup executado pelo Produtor ao produzir um dado acorda o Consumidor.acorda o Consumidor.

187



Ainda assim pode haver condição de corrida:Ainda assim pode haver condição de corrida:

1) Fila vazia (cont == 0); 2) Consumidor testou se cont == 0, mas ainda não dormiu (sleep); 3) Interrupção; 4) Produtor coloca item na fila e tenta acordar o consumidor, sem que este esteja dormindo (wakeup sem término do sleep - perde-se o wakeup). 5) Consumidor volta a executar e dorme (sleep); 6) Produtor enche a fila e dorme (sleep).

SISTEMA TRAVADO! SISTEMA TRAVADO!

188



O problema é chamado de : Problema de Mensagem perdidaProblema de Mensagem perdida

A essência deste problema esta no fato de enviarmos um sinal para acordar (wakeup) para um processo que ainda não esta dormindo.

Solução: Adicionar um bit de espera por despertarbit de espera por despertar. Quando um sinal para acordar é enviado para um processo que ainda esta acordado, esse bit é ativado. Mais tarde, quando o processo tenta ir dormir, se o bit de espera estiver ativado, ele será desativado, mas o processo permanecerá acordado. Esta solução é paliativa quando pensamos em vários processos esse bit crescerá e o problema em princípio continuará a existir.

189


Semáforos

Uma solução para o problema da Mensagem PerdidaMensagem Perdida foi a proposta de uso de uma variável inteira para contar o número de sinais de acordar e salvá-los para uso futuro. Esta variável recebeu o nome de SemáforoSemáforo e é usada para sincronizar processos. Seu objetivo é coordenar o acesso a região crítica e evitar os problemas que levam a condição de corrida. Esta variável pode armazenar o valor zero (indicando que nenhum sinal de acordar foi salvo – wakeup) ou outro valor positivo caso 1 ou mais sinais de acordar estejam pendentes. Além disso foi proposto as seguintes operações sobre esta variável chamada semáforo:

190


Semáforos

DownDown (Correspondente ao sleep): verifica se o valor do semáforo é maior que 0, se for decrementa o valor do semáforo e prossegue. Caso semáforo = 0 o processo irá dormir (blocked) sem terminar de executar o DOWN (por enquanto).

As operações, verificar valor do semáforo e alterar seu conteúdo são tarefas executadas como uma ação atômica e indivisível. Com isso, evitamos o problema de uma interrupção entre essas duas atividades.

191


Semáforos

UP UP (Correspondente ao wakeup): esta operação incrementa o valor do semáforo que estão dormindo associado ao semáforo em questão. Se houver algum ou alguns processos bloqueados, impedidos de chamar a primitiva DOWN, um deles é escolhido para desbloqueio (aleatoriamente) e é dado a permissão de terminar a execução da operação DOWN que ele havia começado anteriormente, com isso o processo acordado que estava bloqueado irá decrementar o valor do semáforo, fazendo com que ele permaneça em zero. No entanto existirá um processo a menos dormindo no semáforo.

192


Semáforos

As operações de semáforos são atômicas,ou seja, não podem ser interrompidas. As operações sobre semáforos são feitas via chamadas de SO (sistema operacional) , onde o SO desativará as interrupções enquanto o semáforo estiver seno utilizado.

É garantido que após o início de uma operação de semáforo, nenhum outro processo acesse o semáforo até que a operação tenha se completado.

Semáforo MutexMutex é binário (assume 0 ou 1) e é responsável por garantir a exclusão mútua. Mutex_lock Impedido 0 e Mutex_unlock Desimpedido 1

193


Problema do Produtor e Consumidor (Semáforo)

Ainda assim pode haver condição de corrida: Ainda assim pode haver condição de corrida:

1) Fila vazia (cont == 0); 2) Consumidor testou se cont == 0, Down (bloqueado), semáforo+1; 3) Interrupção; 4) Produtor coloca item na fila e tenta acordar o consumidor, executa UP5) Consumidor sai de bloqueado, continua a executar o Down, semáforo-1 – acorda Consumidor ; 6) Consumidor retira dados da fila...Produto coloca dados na filaSISTEMA NÂO IRÁ TRAVAR! SISTEMA NÂO IRÁ TRAVAR!

194


Monitores

È uma primitiva de sincronização de alto nível. Um MonitorMonitor é uma coleção de variáveis de procedimentos e de estruturas de dados ou são agrupados em um tipo especial de módulo ou de pacote. Os processos podem chamar os procedimentos em um monitor sempre que quiserem, mas eles não podem acessar diretamente as estruturas de dados internas do monitor a partir de procedimentos declarados fora do monitor.

195


RESUMO:RESUMO:

Mecanismos de espera ativa:Mecanismos de espera ativa:Desabilitar InterrupçãoVariáveis de BloqueioAlternância EstritaSolução de PetersonInstrução TSL

Mecanismos de espera bloqueada:Mecanismos de espera bloqueada:Sleep/WakeupSemáforosMutexMonitores

196


Escalonamento ou

Agendamento

197


Agendamento de Processo ou Escalonamento

Para implementar o compartilhamento da CPU entre diversos processos, um sistema operacional multiprogramável deve possuir um critério para determinar, entre os diversos processos no estado pronto, qual o próximo processo a executar.

Esse procedimento de seleção é realizado por um importante componente do sistema operacional denominado escalonador, e, por isso, recebe o nome de Escalonamento de Processos ou Agendamento de Escalonamento de Processos ou Agendamento de ProcessosProcessos

198


Tipos de escalonamento:

Não-preemptivo: processo que está executando não pode ser interrompido. Presente nos primeiros sistemas multiprogramáveis, onde predominava o processamento em batch. As políticas que implementam escalonamento não-preemptivo não são aplicáveis à sistemas de tempo compartilhado, pois em processos interativos é necessário um tempo de resposta ao usuário razoável.

Preemptivo: o processador pode ser retirado do processo que está executando. Permite atenção imediata aos processos mais prioritários (tempo real), melhores tempos de resposta (tempo compartilhado), compartilhamento uniforme do processador.

199


Escalonamento

• A principal função do escalonamento é decidir qual dos processos prontos para execução deve ser alocado à CPU.

• Cada SO necessita de um algoritmo de escalonamento adequado a seu tipo de processamento. Os principais critérios que o escalonamento tenta otimizar:

• Utilização da CPU: deseja-se que a CPU fique a maior parte do tempo ocupada, sendo dividida de forma imparcial entre os processos. Uma faixa de utilização de 90% indica um sistema bastante ocupado, próximo de sua capacidade ideal.

200


Escalonamento

• Throughput: representa o número de processos (tarefas) executados em um determinado intervalo de tempo. Quanto maior o Throughout , maior o número de tarefas executadas em função do tempo.

• Tempo de turnaround: é o tempo que um processo leva desde sua admissão até o seu término, levando-se em consideração o tempo de espera para alocação de memória, espera na fila de processos prontos, processamento na CPU e operações de E/S.

201


Escalonamento

• Tempo de resposta: em sistemas interativos, este tempo é o tempo

decorrido do momento da submissão do pedido até a primeira

resposta produzida. O tempo de resposta não é o tempo utilizado no

processamento total de uma tarefa, e sim o tempo decorrido até que

uma resposta seja apresentada.

• De uma maneira geral, qualquer algoritmo de escalonamento busca

otimizar a utilização da CPU e o Throughput , enquanto tenta diminuir

os tempos de turnaround e de resposta .

202


Escalonamento

• O algoritmo de execução não é o único responsável pelo tempo de

execução de um processo. Outros fatores, como o tempo de

processamento (tempo de CPU) e de espera em operações de E/S

devem ser considerados no tempo total da execução (tempo de parede

ou elapsed time ou wall clock time).

• O escalonamento somente afeta o tempo de espera de processos na fila

de pronto.

203

Escalonamentos Não Preemptivos

•Nos primeiros Sistemas Operacionais Multiprogramáveis, onde predominava tipicamente o processo batch, o escalonamento implementado era do tipo Não Preemptivo .

•Neste tipo de escalonamento, quando um processo ganha o direito de utilizar a CPU nenhum outro processo pode lhe tirar este recurso.

•Podem ser:

•Escalonamento Circular Simples - FIFO

•Escalonamento Shortest Job First - SJF

•Escalonamento Cooperativo


204

Escalonamento Circular Simples – FIFO

•Há uma fila única de processos prontos

•O primeiro processo da fila (first-in) é o primeiro a ser selecionado para execução (first-out)

•O processo selecionado pode usar a CPU indefinidamente

•Novos jobs são encaminhados para o fim da fila

•Quando um processo bloqueia, o próximo da fila é selecionado

•Processos que passaram do estado bloqueado para pronto são colocados no fim da fila

•Fácil de implementar

•A falta de preempção pode trazer desvantagens


205

Escalonamento Shortest Job First - SJF

•Neste escalonamento cada processo tem associado o seu tempo de

execução. Desta forma quando a CPU está livre o processo em estado de

pronto que tiver menor tempo de execução será selecionado para execução.

•O escalonamento SJF favorece os processos que executam processos

menores, além de reduzir o tempo médio de espera (na fila de processos

prontos) em relação ao escalonamento FIFO.

•A dificuldade é determinar, exatamente, quanto tempo de CPU cada processo

necessita para terminar seu processamento.


206

Escalonamento Cooperativo

•Neste escalonamento alguma política não-preemptiva deve ser adotada. A

partir do momento que um processo está em execução, este voluntariamente

libera o processador, retornando para a fila de pronto.

•Este tipo de escalonamento permite a implementação de sistemas

multiprogramáveis com uma melhor distribuição do uso do processador entre

os processos.

•Sua principal característica está no fato de a liberação do processador ser

uma tarefa realizada exclusivamente pelo processo em execução, que de

maneira cooperativa libera a CPU para um outro processo.


207

Escalonamento Cooperativo

•No escalonamento cooperativo, não existe nenhuma intervenção do SO na

execução do processo. Isto pode ocasionar sérios problemas na medida em

que um programa pode não liberar o processador ou um programa mal escrito

pode entrar em looping, monopolizando dessa forma o processados.

•Um exemplo deste tipo de escalonamento pode ser encontrado nos sistemas

Windows 3.1 e 3.11, sendo conhecido como Multitarefa Cooperativa . Nestes

sistemas as aplicações verificam uma fila de mensagens periodicamente para

determinar se existem outras aplicações que desejam usar a UCP. Caso uma

aplicação não verifique a fila de mensagens as outras tarefas não terão chance

de ser executadas até o término do programa.


208

Escalonamentos Preemptivos

•Um algoritmo de escalonamento é dito preemptivo quando o sistema pode interromper um processo em execução, para que outro utilize o processador.

•O escalonamento preemptivo permite que o sistema dê atenção imediata a processos mais prioritários, como no caso de sistemas de tempo real, além de proporcionar melhores tempos de resposta em sistemas de tempo compartilhado.

•Outro benefício deste tipo de escalonamento é o compartilhamento do processador de uma maneira mais uniforme entre os processos.


209


•A troca de um processo por outro na CPU (troca de contexto), causada pela preempção, gera um overhead ao sistema.

•Para isto não se tornar crítico, o sistema deve estabelecer corretamente os critérios de preempção.


210


•Podem ser:

•Round-Robin

•Prioridades

•Filas Múltiplas

•Múltiplos Processadores


211

Escalonamento Circular - Round Robin

Um dos algoritmos mais simples, mais antigo e mais amplamente utilizado. A cada processo á atribuido um intervalo de tempo, chamado de quantum durante o qual lhe é permitido executar.

Caso o processo ainda esteja executando ao final do quantum, é feita a troca do mesmo por outro processo que esteja pronto para a fase de execução.

Se o processo bloqueou ou terminou antes de o quantum ter acabado, a troca por outro processo é realizada no exato momento do bloqueio ou do término da operação do processo.


212


TIME-SLICING ou QUANTUM

Para evitar que um processo monopolize o sistema, a técnica de TIME-

SLICING ou QUANTUM divide o tempo de processamento de cada um

em fatias (slice). Quantum é o tempo limite de uso da CPU pelo

processo.

Um processo do usuário, uma vez interrompido por término do seu

quantum, volta à fila de pronto para executar e permite o escalonamento

de outro processo.

213


A única coisa que pode dar um pouco de trabalho na implementação

do Round Robin é a determinação do tamanho do quantum.

Um quantum de tamanho muito pequeno, causa sucessivas troca de

contexto, baixando a eficiência do processador.

Um quantum de tamanho muito grande pode levar a um tempo de

resposta não aceitável para usuários interativos.


214


•O algoritmo é semelhante ao FIFO, porém, quando um processo passa para o estado de execução, existe um tempo limite para a sua utilização de forma contínua. Quando este tempo (time-slice ou quantum) expira sem que antes a CPU seja liberada pelo processo, este volta ao estado de pronto (preempção por tempo), dando a vez a outro processo.

•A fila de processos é tratada como uma fila circular.

B AUCP

C

Processosprontos

E/S

FimProcessamento

Fim detime-slice


215

Escalonamento por Prioridades

O escalonamento Round Robin assume de forma implícita que todos os processos são igualmente importantes.

A necessidade de se considerar fatores externos para a escolha do próximo processo que vai ganha o processador é denominada escalonamento por prioridade.escalonamento por prioridade.

Cada processo é associado uma prioridade, e o processo pronto com maior prioridade será aquele que vai rodar primeiro.


216


A prioridade é uma característica do contexto de SW do processo,

podendo ser estática ou dinâmica .

A prioridade é dita estática quando não é modificada durante a

existência do processo.

Na prioridade dinâmica a prioridade do processo pode ser ajustada de

acordo com o tipo de processamento realizado pelo processo e/ou pela

carga do sistema.


217


Toda vez que um processo for para a fila de processos prontos com prioridade superior ao processo em execução, o SO deverá interromper o processo corrente, colocá-lo como pronto e escalonar o processo de maior prioridade para execução ( preempção por prioridade )

Assim como na preempção por tempo a preempção por prioridade é implementada mediante um clock, que interrompe o processador em determinados intervalos de tempo, para que a rotina de Escalonamento reavalie as prioridades e, possivelmente, escalone outro processo.

Para evitar que processos com alta prioridade monopolizem o processador (evitando o starvation), o escalonador deverá decrementar a prioridade do processo que esta monopolizando a CPU, a cada interrupção de tempo.


218


Os processos poderão ser agrupados em classes de prioridade e usar o escalonamento de prioridades entre as classes e o Round Robin dentro de cada classe. Conforme figura abaixo:


219


Algoritmo: enquanto houver processos com prioridade 4: round-robin na

classe (processos em outras classes não são escolhidos). Se prioridade 4

vazia, round-robin na prioridade 3 e assim por diante. Cada vez que o processo

recebe o tempo para executar, a sua prioridade é decrementada. Quando todos

os processos se encontrarem no mesmo nível, as prioridades iniciais são

restauradas.


220

Escalonamento por Filas Múltiplas

•Processos não permanecem numa mesma classe de prioridade até o fim de sua execução

•Quando seu quantum expira, ele vai para uma fila de prioridade mais baixa/quantum mais alto

•Filas de prioridades diferentes têm quantum diferentes

•Diminuição de prioridade X aumento de quantum

•Reduzir a quantidade de trocas de contexto para processos grandes


221

Escalonamento Filas Múltiplas


222

Escalonamento Garantido

Cada processo tem direito a 1/n tempo da CPU, sendo n o número de processos.

Para isso a CPU deve saber quanto tempo cada processo já usou.

Dividindo o tempo que já usou pelo tempo que deveria ter para completar a operação (Tempo prometido), obtém-se uma razão entre ambos, onde:

Se essa razão for menor do que 1, então o processo terá direito a mais tempo de CPU;

Se essa razão for maior do que 1, então o processo terá menos tempo de CPU do que os outros processos.


223

Escalonamento em 2 níveis

Caso não haja memória disponível para todos os processos,

alguns destes deverão ser mantidos em disco.

Esta situação tem grande impacto sobre o escalonamento, uma

vez que o tempo gasto na troca de contexto envolvendo o disco

é algumas ordens de magnitude maior do que quando ambos os

processos estão na memória principal.


224


•Uma forma mais prática de tratar com o swap de processos é usando um escalonador de 2 níveis.

•Um subconjunto de processos prontos é carregado na memória principal, e outro subconjunto é mantido em disco.

•Um escalonador, denominado escalonador de nível mais baixo, se restringe a escolher processos somente da memória, utilizando qualquer uma das políticas de escalonamentoqualquer uma das políticas de escalonamento.


225


•Um outro escalonador de nível mais alto é invocado para remover processos que estão na memória há bastante tempo, e trazer para a memória aqueles processos que estão em disco há muito tempo.

•Quando esta troca for feita, o escalonador de nível mais baixo se restringe, novamente, a escolher processos que estão na memória para serem executados.

•Esta solução faz com que o escalonador de baixo nível se preocupe em escalar os processos que estão na memória enquanto que o de alto nível em trazer e levar processos entre a memória e o disco (swap).


226


O escalonador de alto nível pode usar um dos seguintes critérios de escolha de processos:

Qual o tempo decorrido desde que o processo foi trazido para a memória e levado de volta para o disco;

Quando tempo de CPU o processo teve;

Qual o tamanho do processo;

Qual a prioridade do processo.

Poderemos utilizar o Round Robin, prioridade, ou qualquer outro método de escalonamento, para programar o escalonador de alto nível.


227

Escalonamento de Sistemas de Tempo Real

• Nestes sistemas o fator tempo é crítico.

•Diferentemente dos sistemas de tempo compartilhado, onde um pequeno tempo de resposta é desejado porém não obrigatório, todo processamento em tempo real deve ser realizado dentro de limites rígidos de tempo ou, caso contrário, todo sistema pode ficar comprometido.


228


DeadLock

229

Deadlock

Deadlock (blocagem, impasse), no contexto do sistemas operacionais (SO), caracteriza uma situação em que ocorre um impasse e dois ou mais processos ficam impedidos de continuar suas execuções, ou seja, ficam bloqueados.

O deadlock ocorre com um conjunto de processos e recursos não-preemptíveis, onde um ou mais processos desse conjunto está aguardando a liberação de um recurso por um outro processo que, por sua vez, aguarda a liberação de outro recurso alocado ou dependente do primeiro processo.


230

Deadlock

A definição textual de deadlock normalmente, por ser muito abstrata, é mais difícil de se compreender do que a representação por grafos, que será resumida mais adiante. No entanto, algumas observações são pertinentes:

O deadlock pode ocorrer mesmo que haja somente um processo no SO, considerando que este processo utilize múltiplos threads e que tais threads requisitem os recursos alocados a outros threads no mesmo processo;


231

Deadlock

O deadlock independe da quantidade de recursos disponíveis no sistema;

Normalmente o deadlock ocorre com recursos como dispositivos, arquivos, etc. Apesar da CPU ser considerada como recurso para o SO, em geral é um recurso facilmente preemptível, pois existem os escalonadores para compartilhar o processador entre os diversos processos, quando trata-se de um ambiente multitarefa.


232

Deadlock - Condições necessárias para a ocorrência de deadlock

É comum dizer que o deadlock ocorre naturalmente em alguns sistemas. No entanto, é necessário ressaltar que tais sistemas precisam obedecer a algumas condições para que uma situação de deadlock se manifeste.

Essas condições estão listadas abaixo, onde as três primeiras caracterizam um modelo de sistema, e a última é o deadlock propriamente dito:

processos que estejam de posse de recursos obtidos anteriormente podem solicitar novos recursos. Caso estes recursos já estejam alocados a outros processos, o processo solicitante deve aguardar pela liberação do mesmo;


233


1 – Condição de exclusão mútua: Cada recurso ou está alocado a

exatamente um processo ou está disponível;

2 - Condição de posse-e-espera: Processos que estejam de posse de

recursos obtidos anteriormente podem solicitar novos recursos;


234


3 - Condição de não-preempção: recursos já alocados a processos

não podem ser tomados a força. Eles precisam ser liberados

explicitamente pelo processo que detém a sua posse;

4 - Condição de espera circular: deve existir uma cadeia circular de

dois ou mais processos, cada um dos quais esperando por um recurso

que está com o próximo membro da cadeia.


235

Deadlock - Representação de deadlock em grafos

O deadlock também pode ser representado na forma de grafos dirigidos, onde o processo é representado por um círculo e o recurso, por um quadrado. Quando um processo solicita um recurso, uma seta é dirigida do círculo ao quadrado. Quando um recurso é alocado a um processo, uma seta é dirigida do quadrado ao círculo.

Na figura seguinte, podem-se ver dois processos diferentes (A e B), cada um com um recurso diferente alocado (R1 e R2). Nesse exemplo clássico de deadlock, é facilmente visível a condição de espera circular em que os processos se encontram, onde cada um solicita o recurso que está alocado ao outro processo.


236

Deadlock


237

Deadlock - Tratamento de deadlock

As situações de deadlock podem ser tratadas ou não em um sistema, e

cabe aos desenvolvedores avaliar o custo/benefício que essas

implementações podem trazer.

Normalmente, as estratégias usadas para detectar e tratar as situações

de deadlocks geram grande sobrecarga, podendo até causar um dano

maior que a própria ocorrência do deadlock, sendo, às vezes, melhor

ignorar a situação.


238

Deadlock - Tratamento de deadlock

Existem três estratégias para tratamento de deadlocks:

1) Ignorar a situação;

2) Detectar o deadlock e recuperar o sistema; e

3) Evitar o deadlock;


239

Deadlock


Ou seja, o Processo 1 reserva para si o Recurso 1, por sua vez o Processo 2 e o Processo 3 reservam respectivamente para si o Recurso 2 e o Recurso 3. Por exemplo se um dos outros processos necessitar de um dos recursos anteriormente reservados por outros processos, como acontece no diagrama da figura anterior entramos numa situação de Deadlock.

Exemplo 1

240

Os recursos são de 2 tipos :

• Preemptíveis e;• Não-preemptíveis.

Um recurso preemptível é aquele que pode ser tomado do processo que estiver usando o recurso, sem nenhum prejuízo para o processo.

A memória é um exemplo de recurso preemptível.

Sistemas Operacionais - DeadLock

241

RECURSO PREEMPTÍVEL:

Considere um sistema com 512 Kb de memória disponível para usuários, uma impressora e 2 processos de 512 Kb (P1 e P2) cada. Estes processos desejam imprimir alguma coisa.

O processo P1 é carregado na memória e requisita e obtém acesso a impressora, este então inicia o processamento de impressão (cálculos,lay-out etc), porém antes de terminar P1 excede o seu tempo (time slice) e é retirado da memória (sai de EXECUTANDO e vai para PRONTO).

O processo P2 começa então o seu processamento e tenta obviamente sem sucesso, garantir para si o uso da impressora.


242

RECURSO PREEMPTÍVEL:

Potencialmente temos configurado uma situação de DEADLOCK, pois P1 tem a impressora e P2 tem a memória, e nenhum dos dois pode prosseguir sem o recurso que esta com o outro.

Felizmente é possível tomar a memória de P2 (vai para BLOCKED), copiando P1 (swapp) do disco para a memória agora P1 pode executar, realizar a impressão e liberar a impressora, que quando liberada será entregue a P2 (sai de BLOCKED e vai para PRONTO), para que este termine o seu processamento.

Neste caso não vai ocorrer DEADLOCK.


243

RECURSO NÃO-PREEMPTÍVEL:

Em contrapartida um recurso não-preemptível é aquele que não pode ser tomado de seu proprietário atual sem causar problemas no processamento corrente.

Por exemplo se um processo iniciou a impressão de resultados, a impressora não poderá ser tomada dele e entregue a outro processo, sem que haja um prejuízo considerável no processo.

Para recurso não-preemptível ocorrerá DEADLOCK.


Documents

Sistemas_Operacionais