2ª AV de Sistemas Operacionais

Qual a importância dos Sistemas Operacionais?

R. O sistema operacional é importante porque ele quem define o ambiente no qual o usuário interage como computador.

O que é Sistema Operacional?

Um sistema operacional (SO) é uma coleção de programas que inicializam o hardware do computador. Fornece rotinas básicas para controle de dispositivos. Fornece gerência, escalonamento e interação de tarefas. Mantém a integridade de sistema.

Sistema Operacional é o mesmo que Sistema Computacional?

R. Não, pois, o Sistema Operacional (SO) é uma coleção de programas que inicializam o hardware do computador. Já o Sistema Computacional consiste num conjunto de dispositivos eletrônicos (hardware) capazes de processar informações de acordo com um programa (software).

O que é um Sistema Computacional? Defina seus componentes.

R. Um sistema computacional é aquele que automatiza ou apoia a realização de atividades humanas através do processamento de informações. Seus componentes são: Hardware; Software; Informações; Usuários; Procedimentos ou Tarefas; Documentação.

O que é um processo?

Um processo ou tarefa é uma porção de um programa em alguma fase de execução. Um programa pode consistir de várias tarefas, cada uma com funcionamento próprio ou como uma unidade (talvez se comunicando entre si periodicamente).

Estrutura dos Sistemas Operacionais

1. Monolíticos.

R. No modelo monolítico, não há estruturação visível, como o próprio nome diz (mono=um), o SO consiste em um conjunto de procedimentos independentes, que pode chamar uns aos outros e que são combinados em um único programa para formar o kernel (núcleo) do Sistema Operacional. As vantagens são: é simplicidade e grande desempenho e como desvantagem, uma falha pode paralisar todo o núcleo.

2. Em camadas.

R. O SO é dividido em camadas sobrepostas, onde cada módulo oferece um conjunto de funções que podem ser utilizadas por outros módulos. Módulos de uma camada podem fazer referências apenas aos módulos das camadas inferiores. A vantagem neste tipo de estruturação é isolar as funções do SO, facilitando sua alteração e depuração, além de criar uma hierarquia de níveis de acesso que permite proteger as camadas mais internas. Como desvantagem, cada nova camada implica uma mudança no modo de acesso.

3. Máquinas Virtuais.

R. Uma máquina virtual é uma cópia via software que busca simular uma máquina real. Uma máquina virtual (Virtual Machine – VM) pode ser definida como “uma duplicata eficiente e isolada de uma máquina real”. Sua memória, processador e outros recursos são virtualizados. A virtualização é a interposição do software (máquina virtual) em várias camadas do sistema. É uma forma de dividir os recursos de um computador em múltiplos ambientes de execução. Como vantagens: flexibilidade no SO e a desvantagem, como simular diversas máquinas virtuais não é uma tarefa simples, pode ocorrer sobrecarga nesse SO.

4. Arquitetura Micro-kernel;

R. Tem a idéia de tornar o núcleo menor e mais simples possível e para implementar esta idéia o sistema é dividido em processos. Desta forma, sempre que uma aplicação desejar algum serviço ela solicitará ao processo responsável, assim, a aplicação que solicita um serviço é chamada de cliente e o processo que responde a solicitação é chamado de servidor.

5. Cliente-Servidor.

R. Sistemas Cliente-Servidor são modelos de computação que disntiguem dois tipos básicos de equipamentos computacionais: clientes e servidores, sendo interligados entre si e geralmente utilizam uma rede de computadores. Neste modelo, geralmente os servidores agregam as funções mais importantes do sistema, deixando aos clientes apenas o processamento de aplicações mais básicas.

Aulas 5 – Algoritmo para escalonamento de processos

Algoritmos de Escalonamento de Sistemas em Batch:

Três níveis:

Escalonador De Admissão: decide qual job será admitido no sistema. Por exemplo, uma mescla de Jobs orientados a CPU e orientados à E/S; Processos com menor tempo de acesso à CPU e maior tempo de interação com dispositivos de E/S;

Escalonador Da Memória: decisões sobre quais processos vão para a MP: Há quanto tempo o processo está esperando? Quanto tempo da CPU o processo já utilizou? Qual o tamanho do processo? Qual a importância do processo?

Escalonador da CPU: seleciona qual o próximo processo a ser executado;

Algoritmo First-Come First-Served (ou FIFO):

Não-preemptivo (CPU não controla o tempo dos processos!); Processos são executados na CPU seguindo a ordem de requisição; Fácil de entender e programar;

Desvantagem: Ineficiente quando se tem processos que demoram na sua execução;

Algoritmo Shortest Job First (SJF) (o primeiro processo que entra é o mais curto):

Não-preemptivo; Possível prever o tempo de execução do processo (por que percorre todos os processos para verificar qual menor); Menor processo é executado primeiro; Menor turnaround (tempo em que o usuário espera pela saída do processo);

Desvantagem: Baixo aproveitamento quando se tem poucos processos prontos para serem executados;

Shortest Remaining Time Next (SRTN) (executar o processo com menor tempo de execução mais curto.):

Não - Preemptivo; Processos com menor tempo de execução são executados primeiro; Se um processo novo chega e seu tempo de execução é menor do que do processo corrente na CPU, a CPU suspende o processo corrente e executa o processo que acabou de chegar;

Desvantagem: processos que consomem mais tempo podem demorar muito para serem finalizados se muitos processos pequenos chegarem!

Algoritmos de Escalonamento para Sistemas Interativos:

Utilizam escalonamento em dois níveis (escalonador da CPU e memória);

Algoritmo Round-Robin:

Antigo, mais simples e mais utilizado; Preemptivo; Cada processo recebe um tempo de execução chamado quantum; ao final desse tempo, o processo é suspenso e outro processo é colocado em execução; Escalonador mantém uma lista de processos prontos; Quantum: se for muito pequeno, ocorrem muitas trocas diminuindo, assim, a eficiência da CPU; se for muito longo o tempo de resposta é comprometido;

Algoritmo com Prioridades:

Cada processo possui uma prioridade > os processos prontos com maior prioridade são executados primeiro; Prioridades são atribuídas dinâmica ou estaticamente; Classes de processos com mesma prioridade; Preemptivo;

Como evitar que os processos com maior prioridade sejam executados indefinidamente?

Diminuir a prioridade do processo corrente a cada interrupção do relógio e trocá-lo pelo próximo processo assim que sua prioridade caia abaixo da prioridade do próximo processo com prioridade mais alta (chaveamento); Atribuir um quantum máximo no qual o processo pode executar;

Algoritmo de Múltiplas Filas:

CTSS (Compatible Time Sharing System); Classes de prioridades; Preemptivo; Cada classe de prioridades possui quantum diferentes; Assim, a cada vez que um processo é executado e suspenso ele recebe mais tempo para execução, mas passa para uma fila com menor prioridade de execução.

Algoritmo Shortest Process Next(Próximo processo mais curto.);

Mesma idéia do Shortest Job First; Processos Interativos: não se conhece o tempo necessário para execução; Solução: realizar uma estimativa com base no comportamento passado e executar o processo cujo tempo de execução estimado seja o menor;

Algoritmo Garantido;

Garantias são dadas aos processos dos usuários; Exemplo: n processos > 1/n do tempo de CPU para cada processo: Deve ser mantida taxa de utilização de cada processo; Tem prioridade o que estiver mais distante do prometido. Difícil de implementar.

Algoritmo Lottery;

Cada processo recebe “tickets” que lhe dão direito de execução; A cada troca de processo um “tickets” é sorteado; O dono dos “tickets” sorteado recebe o direito de ocupar a CPU; Possível definir prioridade entre os processos por meio do número de “tickets” atribuído a cada processo; Fácil de implementar e de adaptar.

Algoritmo por Fração Justa (Fair-Share);

O escalonamento é feito considerando o dono dos processos; Cada usuário recebe uma fração da CPU e processos são escalonados visando garantir essa fração; Se um usuário A possui mais processos que um usuário B e os dois têm a mesma prioridade, os processos de A demorarão mais que os do B.

Algoritmos de Escalonamento de Sistemas em Tempo Real:

Tempo é um fator crítico; Sistemas críticos: Aviões; Hospitais; Usinas Nucleares; Bancos; Multimídia;

Ponto importante: obter respostas em atraso é tão ruim quanto não obter respostas;

Tipos de STR:

Hard Real Time: atrasos não são tolerados: Aviões, usinas nucleares, hospitais;

Soft Real Time: atrasos são tolerados: Bancos; Multimídia;

Programas são divididos em vários processos; Eventos causam a execução de processos: Periódicos: ocorrem em intervalos regulares de tempo; Aperiódicos: ocorrem em intervalos irregulares de tempo;

Algoritmos podem ser: Estáticos: decisões de escalonamento antes do sistema começar;

Informação disponível previamente; Dinâmicos: decisões de escalonamento em tempo de execução;

Aula 06 –Thread

Processos

Sistemas Operacionais tradicionais: Cada processo tem um único espaço de endereçamento e um único fluxo de controle. Existem situações onde é desejável ter múltiplos fluxos de controle compartilhando o mesmo espaço de endereçamento: Solução: THREADS

THREADS

Um processo tradicional (pesado) possui um contador de programas, um espaço de endereço e apenas uma thread de controle (ou fluxo de controle);

Multithreading: Sistemas atuais suportam múltiplas threads de controle, ou seja, pode fazer mais de uma tarefa ao mesmo tempo, servindo ao mesmo propósito;

Thread é uma entidade básica de utilização da CPU. Também conhecidos como processos leves (lightweight process ou LWP); Processos com múltiplas threads podem realizar mais de uma tarefa de cada vez; Processos são usados para agrupar recursos; Threads são as entidades escalonadas para execução na CPU: A CPU alterna entre as threads dando a impressão de que elas estão executando em paralelo; Como cada thread pode ter acesso a qualquer endereço de memória dentro do espaço de endereçamento do processo, uma thread pode ler, escrever ou apagar a pilha de outra thread; Não existe proteção pois: Não é necessário pois, diferente dos processos que podem pertencer a diferentes usuários, as threads são sempre de um mesmo usuário.

Razões para existência de threads:

Em múltiplas aplicações ocorrem múltiplas atividades “ao mesmo tempo”, e algumas dessas atividades podem bloquear de tempos em tempos; As threads são mais fáceis de gerenciar do que processos, pois elas não possuem recursos próprios > o processo é que tem!

Desempenho: quando há grande quantidade de E/S, as threads permitem que essas atividades se sobreponham, acelerando a aplicação; Paralelismo Real em sistemas com múltiplas CPUs.

Considere um navegador WEB:

Muitas páginas WEB contêm muitas figuras que devem ser mostradas assim que a página é carregada;

Para cada figura, o navegador deve estabelecer uma conexão separada com o servidor da página e requisitar a figura > tempo; Com múltiplas threads, muitas imagens podem ser requisitadas ao mesmo tempo melhorando o desempenho;

Benefícios das Threads:

Capacidade de resposta: aplicações interativas. Ex.: servidor WEB;

Compartilhamento de recursos: mesmo endereçamento, memória, recursos;

Economia: criar e realizar chaveamento de threads é mais barato;

Utilização de arquiteturas multiprocessador: processamento paralelo;

Tipos de threads:

Em modo usuário (espaço do usuário):

Implementadas por bibliotecas no espaço do usuário; Criação e escalonamento são realizados sem o conhecimento do kernel; Sistema Supervisor (run-time system): coleção de

procedimentos que gerenciam as threads; Tabela de threads para cada processo;

Cada processo possui sua própria tabela de threads, que armazena todas a informações referentes à cada thread relacionada àquele processo;

Vantagens: Alternância de threads no nível do usuário é mais rápida do que alternância no kernel; Menos chamadas ao kernel são realizadas; Permite que cada processo possa ter seu próprio algoritmo de escalonamento; Podem ser implementado em Sistemas Operacionais que não têm threads.

Principal desvantagem: Processo inteiro é bloqueado se uma thread realizar uma chamada bloqueante ao sistema;

Em modo kernel:

Suportadas diretamente pelo SO;

Criação, escalonamento e gerenciamento são feitos pelo kernel:

Tabela de threads e tabela de processos separadas: As tabelas de threads possuem as mesmas informações que as tabelas de threads em modo usuário, só que agora estão implementadas no kernel;

Vantagem: Processo inteiro não é bloqueado se uma thread realizar uma chamada bloqueante ao sistema;

Desvantagem: Gerenciar threads em modo kernel é mais caro devido às chamadas de sistema durante a alternância entre modo usuário e modo kernel;

Modelos Multithreading:

Muitos-para-um: (Green Threads e GNU Portable Threads)

Mapeia muitas threads de usuário em apenas uma thread de kernel;

Não permite múltiplas threads em paralelo em multiprocessadores;

Gerenciamento Eficiente

Se uma bloquear todas bloqueiam

Um-para-um: (Linux, Família Windows, OS/2, Solaris 9)

Mapeia para cada thread de usuário uma thread de kernel;

Permite múltiplas threads em paralelo;

Problema – criação de thread no kernel prejudica o desempenho.

Muitos-para-muitos: (Solaris até versão 8, HP-UX, Tru64 Unix, IRIX)

Mapeia para múltiplos threads de usuário um número menor ou igual de threads de kernel;

Permite múltiplas threads em paralelo;

Estados das Threads: executando, pronta, bloqueada;

Comandos para manipular threads: Thread_create; Thread_exit; Thread_wait; Thread_yield (permite que uma thread desista voluntariamente da CPU);

Aula 07 –Deadlock

Dispositivos e recursos são compartilhados a todo o momento: impressora, disco, arquivos, etc...;

Deadlock: processos ficam parados sem possibilidade de poderem continuar seu

processamento;

Recursos

Recursos: objetos acessados, os quais podem ser tanto hardware quanto uma informação.

Preemptivos: podem ser retirados do processo sem prejuízos: Memória; CPU;

Não-preemptivos: não podem ser retirados do processo, pois causam prejuízos: CD-ROM; Unidades de fita;

DEADLOCKS ocorrem com recursos não-preemptivos;

Operações sobre recursos/dispositivos:

Requisição do recurso; Utilização do recurso; Liberação do recurso;

Se o recurso requerido não está disponível, duas situações podem ocorrer:

Processo que requisitou o recurso fica bloqueado até que o recurso seja liberado, ou;

Processo que requisitou o recurso falha, e depois de um certo tempo tenta novamente requisitar o recurso;

Aquisição do recurso:

Para alguns tipos de recursos, os processos dos usuários gerenciam o uso dos recursos, através, por exemplo, de semáforos: Exemplo: acesso a registros em um sistema de banco de dados.

Se vários processos tentam acessar os mesmos recursos, podem ocorrer situações onde a ordem de solicitação dos recursos pode conduzir ao um deadlock ou não.

O que é um DEADLOCK?

R. “Um conjunto de processos estará em situação de deadlock se todo processo pertencente ao conjunto estiver esperando por um evento que somente um outro processo desse mesmo conjunto poderá fazer acontecer.”

Quatro condições para que ocorra um deadlock:

Exclusão mútua: cada recurso pode estar somente em uma de duas situações: ou associado a um único processo ou disponível;

Posse e espera (hold and wait): processos que já possuem algum recurso podem requer outros recursos;

Não-preempção: recursos já alocados não podem ser retirados do processo que os alocou; somente o processo que alocou os recursos pode liberá-los;

Espera Circular: um processo pode esperar por recursos alocados a outro processo;

Todas as condições devem ocorrer para que ocorra um deadlock.

Geralmente, deadlocks são representados por grafos a fim de facilitar sua detecção, prevenção e recuperação:

Ocorrência de ciclos pode levar a um deadlock;

a) Recurso R alocado ao Processo A;

b) Processo B requisita Recurso S;

c) Deadlock.

Aula 8 - Gerenciamento de Memória

Memória - recurso muito importante;

Tendência atual do software: Lei de Parkinson: “Os programas se expandem para preencher a memória disponível para eles” (adaptação);

Requisitos: Muito grande; Rápida; Não volátil; Baixo custo.

Hierarquia de Memória:

Cache – vários sub-níveis: Pequena quantidade – k/M bytes; Alto custo por byte; Muito rápida; Volátil.

Memória Principal: Quantidade intermediária – M/G bytes; Custo médio por byte; Velocidade média; Volátil.

Disco: Grande quantidade – G/T bytes; Baixo custo por byte; Lenta; Não volátil.

Para cada tipo de memória: gerenciar espaços livres/ocupados; Alocar processos/dados na memória; Localizar dado.

Entre os níveis de memória: Gerenciar trocas.

Gerenciador de memória: responsável por alocar e liberar espaços na memória para os processos em execução; também responsável por gerenciar chaveamento entre os níveis de memória: principal e disco; principal e cache.

A função principal da memória é a alocação de áreas contíguas (memória) e fragmentação dos dados em memória.

Tipos básicos de gerenciamento:

Com paginação (chaveamento): Processos são movidos entre a memória principal e o disco; artifício usado para resolver o problema da falta de memória; Se existe MP suficiente não há necessidade de se ter paginação;

Sem paginação: não há chaveamento;

Monoprogramação:

Sem paginação: gerenciamento mais simples; Apenas um processo na memória;

Modelo de Multiprogramação:

Múltiplos processos sendo executados; Eficiência da CPU;

Vários processos na memória: como proteger os processos uns dos outros? E kernel de todos os processos? Como tratar a realocação? Todas as soluções envolvem equipar a CPU com um hardware especial: MMU (memory management unit).

Realocação:

Quando um programa é montado (link), i.e. programa principal + rotinas do usuário + rotinas da biblioteca > executável, o montador (linker) deve saber em que endereço o programa irá iniciar na memória;

Nesse caso, para que o montador não escreva em um local indevido (por exemplo na área do SO), é preciso de realocação.

Proteção:

Com várias partições e programas ocupando diferentes espaços da memória é possível acontecer um acesso indevido;

Solução para ambos os problemas:

Dois registradores > base e limite:

Quando um processo é escalonado o registrador - base é carregado com o endereço de início da partição e o registrador - limite com o tamanho da partição; O registrador - base torna impossível a um processo uma remissão a qualquer parte de memória abaixo de si mesmo. Automaticamente, a MMU adiciona o conteúdo do registrador - base a cada endereço de memória gerado; Endereços são comparados com o registrador - limite para prevenir acessos indevidos;

Partições

Particionamento da memória pode ser realizado de duas maneiras:

Partições fixas (alocação estática): Tamanho e número de partições são fixos (estáticos); Não é atrativo, porque partições fixas tendem a desperdiçar memória (Qualquer espaço não utilizado é literalmente perdido); Mais simples;

Partições variáveis (alocação dinâmica): Tamanho e número de partições variam; Otimiza a utilização da memória, mas complica a alocação e liberação da memória; Partições são alocadas dinamicamente; SO mantém na memória uma lista com os espaços livres; Menor fragmentação interna e grande fragmentação externa; Solução: Compactação;

Minimizar espaço de memória inutilizado:

Compactação: necessária para recuperar os espaços perdidos por fragmentação; no entanto, muito custosa para a CPU;

Técnicas para alocação dinâmica de memória:

Bitmaps: Memória é dividida em unidades de alocação em kbytes; Cada unidade corresponde a um bit no bitmap: 0 > livre 1 > ocupado; Tamanho do bitmap depende do tamanho da unidade e do tamanho da memória; Ex.: Unidades de alocação pequenas > bitmap grande; Unidades de alocação grandes > perda de espaço;

Listas Encadeadas.

O que fazer quando não existe espaço suficiente para todos os processos ativos?

Swapping

Chaveamento de processos inteiros entre a memória principal e o disco. Transferência do processo da memória principal para a memória secundária (normalmente disco): Swap-out; Transferência do processo da memória secundária para a memória principal: Swap-in; Pode ser utilizado tanto com partições fixas quanto com partições variáveis;

Overlays > Memória Virtual

Programas são divididos em pedaços menores; Pedaços são chaveados entre a memória principal e o disco.

Memória Virtual (MV)

Programas maiores que a memória eram divididos em pedaços menores chamados overlays > programador;

Desvantagem: custo muito alto;

Memória Virtual: Sistema operacional é responsável por dividir o programa em overlays;

Sistema operacional realiza o chaveamento desses pedaços entre a memória e o disco;