Introdução aos Sistemas Operativos

Unidade 1 Introdução aos Sistemas Operativos Componentes de um Sistema de Computação Temos o hardware (processador, memória, discos, etc) e temos as aplicações (browsers, compiladores, desenvolvimento) que são de natureza diferente, ou seja, de domínio diferente, mas para o sistema de comp...

Unidade 1 Introdução aos Sistemas Operativos Componentes de um Sistema de Computação Temos o hardware (processador, memória, discos, etc) e temos as aplicações (browsers, compiladores, desenvolvimento) que são de natureza diferente, ou seja, de domínio diferente, mas para o sistema de computação são iguais. Temos, então, o sistema operativo que é uma camada entre o hardware e as aplicações. Para que serve um Sistema Operativo O hardware por si só não é particularmente fácil de utilizar. Programas precisam de muitas funcionalidades comuns e, caso estejam em execução simultânea, de uma entidade que coordene a utilização de recursos. Essas funcionalidades são colocadas num programa especial designado Sistema Operativo que irá facilitar o desenvolvimento e execução dos outros programas. NOTA: o login é uma aplicação iniciada pelo SO, depois fica na base de segurança e quando entramos inicia o indicador de comandos. O que é um Sistema Operativo? Um programa que age como um intermediário entre o utilizador e o hardware criando um ambiente adequado para que um utilizador possa executar os seus programas. Um dos objetivos de um SO é fazer com que um sistema de computação seja mais fácil de utilizar e outro objetivo é promover uma utilização eficiente dos recursos de hardware. Evolução dos Sistemas Operativos » Sistemas Batch Utilizadores preparam tarefas (programa, dados e informação de controlo) para submissão. O sistema é manuseado apenas pelo operador, que controla a execução das várias tarefas agrupadas numa fita magnética. A fita é lida pelo computador principal e o resultado era escrito noutra fita e depois imprimido através de um computador de pequenas dimensões. Problema: baixo desempenho. » Sistemas Multi-programação Temos a memória dividida em partes e cada parte pode ter um programa diferente, sendo o CPU multiplexado entre eles. Requisitos: ★ Gestão de memória - o sistema tem de atribuir a memória às diferentes tarefas. ★ Escalonamento do CPU - o sistema tem de selecionar a tarefa a executar de entre todas as tarefas prontas a executar. ★ Proteção entre tarefas. ★ Suporte a I/O. » Sistemas Time-sharing (multitasking) A gestão de ficheiros foi muito importante, uma vez que tínhamos vários utilizadores a interagir com a máquina de forma independente e eles tinham de guardar os seus resultados (cada utilizador dispõe de um terminal CPU multiplexado entre várias tarefas). É imposta a divisão do tempo disponível do processador pelos vários utilizadores, atribuindo-lhes fatias de tempo que permitem dar-lhes a sensação de dispor de uma máquina dedicada. Fornecia um serviço on-line e as trocas entre tarefas eram muito rápidas. Requisitos: ★ Gestão de memória. ★ Gestão de ficheiros. ★ Sistemas de proteção. ★ Algoritmos de escalonamento de tempo de CPU sofisticados. Começou a ser mais exigente (utilizadores queriam “justiça” na utilização da máquina) então começaram a aparecer muitos algoritmos de escalonamento bastante sofisticados. » Sistemas para PC No passado apresentavam requisitos diferentes das grandes máquinas. Eram normalmente sistemas mono-utilizador e mono-programados (apenas um programa em memória, além do sistema operativo). A evolução de sistemas de janelas introduziu o requisito da multitarefa. A ligação a redes de computadores fez evoluir o requisito de proteção de ficheiros (multi-utilizador). As versões modernas incluem o Windows.../7/8/9/10, Linux e Mac OSX. » Outros Sistemas Operativos ★ Sistemas operativos distribuídos. ★ Sistemas operativos de tempo real. ★ Sistemas operativos para sistemas embebidos. ★ Sistemas operativos para dispositivos móveis. Os conceitos são os mesmos mas têm nomes diferentes porque os requisitos das aplicações também são diferentes. Organização do Sistema Operativo Podemos explicar o SO pelos seus componentes típicos (gestão de memória, gestão de processos, gestão de I/O, gestão de ficheiros, etc), mas também podemos olhar para o conjunto das chamadas ao sistema (também se dividem em componentes). Podemos olhar para o SO pelos serviços que oferece e pelo interpretador de comandos (alguns comandos são aplicações). Gestão de Processos Um processo é um programa em execução e um programa é constituído por dados. Quando executamos um programa, o interpretador de comandos pede ao SO para criar um processo (tem um programa associado). Se o processo estiver com problemas, terminamo-lo e o SO liberta tudo relacionado com o processo. O SO precisa de saber qual é o espaço de endereçamento do programa e onde é que estão carregados os códigos, os dados e a stack. Tem de ter um program counter, stack pointer e outros registos. Necessita também do estado da execução (em execução, pronto a executar ou bloqueado) e dos requisitos atribuídos. O SO, através do gestor de processos, é responsável por: ★ Criar e terminar processos. ★ Suspender e acordar processos. ★ Oferecer mecanismos para: ○ Sincronização de processos. ○ Comunicação entre processos. ★ Identificação de processos em ambientes de multi-programação (uid user identifier- e gid- group identifier). Gestão de Memória Memória Principal: é um enorme array de bytes, cada um com o seu endereço (acedida diretamente pelo CPU e dispositivos de I/O). Os programas para serem executados têm de ser carregados, pelo menos parcialmente, para a memória principal. Memória Virtual: é um conjunto de mecanismos que permite que o programa possa ser executado estando apenas parcialmente carregado em memória principal. O SO, através do gestor de memória, é responsável por: ★ Manter o registo de quais as partes de memória estão a ser usadas num dado instante e por quem. ★ Decidir sobre que processos carregar para memória quando existe espaço livre. ★ Atribuir e libertar espaço de memória quando necessário. Gestão de Ficheiros A Memória Principal é volátil e diminuta para armazenar todos os programas e dados permanentemente (os sistemas de computação oferecem a memória secundária). O SO abstrai as propriedades físicas dos dispositivos de entrada e saída e define uma unidade lógica de armazenamento: o ficheiro. Um ficheiro é uma coleção de informação relacionada que esconde a complexidade dos dispositivos físicos de armazenamento de informação. É um conceito abstrato. O SO, através do componente de gestão de ficheiros (sistema de ficheiros), é responsável por: ★ Criar e apagar ficheiros. ★ Criar e apagar diretorias. ★ Suportar primitivas para manipular ficheiros e diretorias. ★ Associar ficheiros ao sistema de memória secundária. ★ Gestão do espaço livre em disco. ★ Atribuição de espaço em disco. Gestão de E/S (ou I/O) O SO é responsável, através do seu componente de gestão de E/S, por: ★ Esconder a complexidade dos dispositivos de E/S ao utilizador, oferecendo-lhe uma interface abstrata de alto nível. ★ Conceitos básicos. ★ Interface para device-drivers genérica (componente independente do dispositivo). ★ Drivers específicos (componente dependente do dispositivo). Chamadas ao Sistema Oferecem uma interface entre os programas e o sistema operativo. Genericamente, disponíveis como instruções assembly. São normalmente agrupadas por serviços: gestão de ficheiros, gestão de memória e gestão de processos. Sistema de Proteção O mecanismo de proteção é responsável por controlar o acesso de processos ou utilizadores tanto a recursos do sistema como do utilizador. O SO, através do sistema de proteção, é responsável por: ★ Distinguir entre o acesso autorizado e o acesso não autorizado. ★ Especificar o controlo a impor. ★ Providenciar uma forma de implementar essa proteção. Interpretador de comandos Programa que estabelece uma interface entre o utilizador e o sistema operativo para a execução de operações genéricas. Interpreta e executa comandos no sistema operativo, como por exemplo executar um programa. Implementa um ciclo de leitura, interpretação e execução de comandos. No Unix/Linux é conhecida pela Shell. QUESTÕES Quais são as principais vantagens de suportar multi-programação num sistema de computação? Podemos ter vários programas carregados em memória; tornou o processador mais útil, ou seja, o tempo de utilização do CPU aumentou. Conceção de Sistemas Operativos O SO é um programa, ou um conjunto de programas, e um programa é, essencialmente, algoritmos e estruturas de dados. Há um componente dentro do SO chamado kernel. Requisitos São características que o programa tem de cumprir. Seja uma funcionalidade (requisito funcional) sejam qualidades (requisitos não funcionais). » Desempenho ★ Utilização dos recursos da máquina: queremos um SO que use da melhor forma o CPU e a memória. ★ Sobrecarga no desempenho das aplicações: fazer com que o SO seja o menos possível uma sobrecarga para as aplicações. ★ Balanço entre funcionalidade e custos: perceber o que é que tem de estar dentro do SO, porque como é caro pedir serviços ao SO (estar a acrescentar funcionalidades) temos de estar sempre a verificar os custos. » Segurança ★ Multiprogramação -> partilha de recursos: as aplicações partilham os recursos, então temos de ter mecanismos para impedir que interfiram umas na outras. ★ Isolamento dos recursos: garantir que a memória de um programa é só desse programa e ninguém vai lá. ★ Trusted software vs Untrusted software: “trusted software” é testado e verificado pelas empresas e garante certos requisitos que tem de cumprir; “untrusted software” não é verificado e não tem privilégios para executar tudo o que queira. » Flexibilidade ★ Refere-se à capacidade do software evoluir, ou seja, de acrescentar e alterar funcionalidades. » Portabilidade ★ Capacidade de adaptação do SO a diferentes máquinas/hardware. ★ Capacidade de adaptação de programas/aplicações a diferentes SO. Modos de Execução duo mode - pode estar a executar num modo ou noutro: ★ Se estiver a 0: System mode/kernel mode/supervisor mode. ★ Se estiver a 1: User mode. mode bit: modo Supervisor ou Utilizador (elemento chave para o conceito de trusted software). Modo Supervisor: ★ Em modo supervisor é possível executar todas as instruções máquina. ★ Em modo supervisor é possível referenciar todas as posições de memória. Modo Utilizador: ★ Em modo utilizador só é possível executar um subconjunto de instruções. ★ Em modo utilizador só é possível referenciar um subconjunto de posições de memória. Kernel Software crítico para o funcionamento da máquina (trusted software). Executa em modo supervisor. A instrução máquina trap serve para fazer a mudança entre modos. Chamadas ao Sistema São requisições de serviços ao kernel (abrir ficheiros, executar programas e criar processos). NOTAS: ★ Muda o modo de utilização. ★ Depois de executar o fork volta para o programa. ★ A trap table só tem endereços de execução. Portabilidade de aplicações Dificuldades: ★ Os sistemas operativos definem formatos para ficheiros executáveis diferentes. ★ O conjunto de chamadas ao sistema de cada sistema operativo pode variar. ★ Existem instruction sets diferentes entre processadores. Arquiteturas » Monolítica (kernel monolítico) ★ Integra os componentes lógicos do SO num único programa executável. ★ Baseia-se no elevado grau de interação entre os diferentes módulos. ★ Bom desempenho. ★ Baixa flexibilidade: era mais difícil acrescentar funcionalidades. ★ Baixa robustez/fiabilidade: se houvesse um erro, deitava o sistema todo abaixo.  O UNIX era monolítico, ou seja, tudo o que era importante para a execução estava tudo no mesmo programa. O mecanismo para se poder colar um task driver estava fora. » Microkernel ★ Programa mais pequeno apenas com funcionalidades fundamentais. ★ Boa flexibilidade. ★ Boa imunidade a bugs. ★ Boa robustez: se falha um componente, não quer dizer que o SO falhe todo. ★ Baixo desempenho. » Arquitetura baseada em módulos do kernel (loadable kernel modules) ★ Toda a funcionalidade do kernel é executada em modo supervisor. ★ Serviços adicionais podem ser ligados ao kernel quando este inicia ou em execução, através de módulos (permite acrescentar funcionalidades de SO). ★ Cada módulo define uma interface que pode ser utilizada pelas aplicações ou outros módulos. ★ Boa flexibilidade (novas funcionalidades podem ser adicionadas sem necessidade de modificar o kernel). ★ Boa facilidade de debug. ★ Bom desempenho. ★ Menos memória utilizada. Módulos Linux O Linux é baseado numa arquitetura modular. Define um kernel inicial, que inclui um conjunto de funções definidas em tempo de compilação. Um módulo Linux é um conjunto de funções e estruturas de dados compilados como um programa independente. Os módulos podem ser instalados estaticamente, quando o kernel inicia, ou dinamicamente, em tempo de execução. Os módulos executam em modo supervisor. QUESTÕES Porque é que o Sistema Operativo representa uma sobrecarga para as aplicações? Um programa a executar, se estiver com os recursos todos para ele, ou seja, se não for necessário gerir recursos (memória, processador, disco), é mais eficiente. É nessa perspetiva que podemos afirmar que o SO é uma sobrecarga para as aplicações: por um lado permite que o sistema de computação seja mais eficaz, mas apresenta sobrecarga para uma aplicação individual, uma vez que essa aplicação tem de ter o SO a gerir os recursos. Apresente exemplos de operações que devem ser executadas apenas em modo supervisor (trusted software). Carregar um programa para memória, executar programas, escolher memória e gestão de processos. Indique vantagens e desvantagens de incluir no Kernel Unix o interpretador de Comandos (shell). Vantagem: a bash não teria de pedir ao SO para fazer algo. Desvantagem: muitas funcionalidades da bash não estariam como chamadas ao sistema e isso impedia que alguém fizesse o seu interpretador de comandos. NOTAS: Comandos cat: usado para exibir, concatenar e manipular ficheiros de texto. strace (system trace): ferramenta de diagnóstico usada para monitorizar e registar chamadas ao sistema feitas por um programa. É essencial para a análise de como os processos interagem com o kernel de SO.  Unidade 2 Processos e Operações sobre Processos Gestão de Processos Num sistema de computação decorrem simultaneamente várias tarefas. Temos vários tipos de tarefas (dos utilizadores, do kernel, etc) e todas elas competem nos recursos (há necessidade de gerir recursos - perceber que recursos é que estão a ser utilizados por cada programa em execução em cada instante), tudo isso levou à criação do conceito de “processo”. Um processo é um programa em execução, com toda a informação que o caracteriza (espaço de endereçamento, registos, etc). Elementos de um processo: ★ Identificador. ★ Estado de execução. ★ Program counter. ★ Outros registos do CPU. ★ Instruções e dados. ★ Informação de accounting: criador de processos, utilizadores, grupo, tempos de CPU. ★ Estado de I/O: lista de dispositivos em utilização. ★ Prioridade. » Process Control Block (PCB) ★ Contém todos os elementos necessários ao kernel para gerir a execução dos processos. ★ É criado e mantido pelo kernel (só código do kernel é que pode alterar esta estrutura). ★ Possibilita o suporte a múltiplos processos. NOTAS: User time: tempo que demorou a executar as instruções escritas pelo utilizador. System time: tempo que demorou a executar em modo kernel.  Os processos competem pelos recursos do sistema: memória, disco, processador e periféricos. Depois de admitidos no sistema: ★ Um processo está em execução quando as suas instruções estão a ser executadas por um processador. ★ Um processo que possui todos os recursos necessários, mas que ainda não está a executar, está pronto a ser executado pelo processador. ★ Se um processo precisa de um recurso que não está disponível, bloqueia até que esse recurso fique disponível. O sistema operativo mantém informação sobre que processos estão bloqueados e que processos esperam por recursos. Os gestores de recursos são responsáveis por atribuir os recursos aos processos bloqueados segundo uma determinada política em vigor. 1 - é selecionado para execução 2 - há uma interrupção e o processador é retirado ao processo 3 - I/O ou evento de espera 4 - I/O finalizado ou evento completado » Pseudo-paralelismo Em ambientes de multiprogramação múltiplos processos progridem em paralelo no sistema de modo a maximizar a utilização do CPU (multitarefa). Em cada instante, um processador (ou core) só executa as instruções de um determinado processo. Os processos são suspensos e reiniciados várias vezes durante a sua execução. O tempo de execução de um processo varia de execução para execução (a menos que o processo tenha requisitos de tempo real...). » Escalonamento de Processos (Scheduling) Uma das principais funções do SO: faz a gestão do CPU que é um recurso crítico do sistema. ★ Tenta optimizar a sua utilização, mantendo-o tanto quanto possível ocupado. ★ A sua relação com os restantes sistemas é importante. Exemplo: gestão de memória. ★ Responsável pela transição execução-pronto do diagrama de estado e pronto. ★ Decide que processo vai executar, quando e por quanto tempo. Troca de contexto de processos: temos um processo que quer ser executado e há uma interrupção de tempo ou uma chamada ao sistema - SO/kernel entra em ação e o processo fica bloqueado. Dispatcher: grava o estado do processo. Principais operações suportadas pelo sistema operativo: ★ Criação de um processo. ★ Execução de um programa. ★ Terminação de um processo. ★ Obter informação sobre um processo. » Criação de Processos Conceptualmente existe um processo que carrega o kernel para memória. O método mais comum para criação de processos é a execução de uma chamada ao sistema (system call). A chamada ao sistema é invocada pelo processo conhecido como processo pai e dá origem a um novo processo conhecido como processo filho. Os processos pai e filho executam concorrentemente ou, em alternativa, o processo pai espera que o processo filho termine. » Terminação de processos Um processo executa a última instrução e de seguida requisita ao kernel que o elimine: ★ Passagem de informação entre processo pai e filho. ★ Os recursos do processo são apagados pelo sistema operativo. Processo pai pode terminar a execução de um processo filho quando: ★ O processo filho excede os recursos. ★ A tarefa atribuída ao processo filho não é necessária. ★ O processo pai termina. » Modelo Posix (Unix e Linux) Chamada ao sistema fork(): ★ A bash pede ao SO para criar um processo. ★ Novo process identifier. ★ O espaço de endereçamento é duplicado. ★ Partilha de recursos, mas execução independente. ★ Execução concorrente de processos. » API Posix (Unix e Linux) Chamada ao sistema wait(): ★ Permite ao processo pai esperar pelo fim da execução de um dos filhos. ★ Se há mais do que um filho que ainda não terminou, bloqueia o processo pai até que pelo menos um dos filhos termine. ★ Retorna o pid do filho que terminou. ★ Permite ao pai saber como é que o processo filho terminou a sua execução. Chamada ao sistema exit(): ★ Permite a um processo solicitar ao SO para terminar. ★ O kernel através da chamada ao sistema wait() informa o pai sobre a terminação do filho. Chamada ao sistema execve(): ★ Substitui o espaço de endereçamento do processo que a invoca pelo novo programa. ★ Não é criado um novo processo. ★ Tipicamente é invocada após um fork(), pelo processo filho (ex: interpretador de comandos). ★ Retira o programa da memória e põe lá o execve(). NOTA: Variantes do exec() Tarefas Cooperantes e Threads (Introdução à Programação Concorrente) Gestão de Processos » Interação entre Tarefas Uma tarefa é independente se a sua execução não afeta ou não é afetada pela execução de outras tarefas no sistema. Uma tarefa é cooperante se a sua execução afeta ou é afetada pela execução de outras tarefas no sistema. Razões para Tarefas Cooperantes: ★ Partilha de informação: diferentes tarefas num sistema podem necessitar dos mesmos dados (ex: quando estamos a editar um ficheiro no Word e temos erros ortográficos, é uma situação em que temos partilha de informação entre duas tarefas). ★ Desempenho: diferentes tarefas podem estar a cooperar para o mesmo objetivo, contribuindo para um aumento de desempenho (em casos em que existem múltiplos elementos de processamento). É mais rápido de executar e solícito a responder. ★ Modularidade: uma tarefa pode ser dividida em sub-tarefas que se comunicam entre si. ★ Conveniência: facilitar a execução concorrente de várias tarefas dentro de uma mesma aplicação Para que duas tarefas possam cooperar, o sistema operativo terá de permitir a comunicação entre processos. É o kernel que fornece esses mecanismos de comunicação entre processos. A maneira de dois processos no mesmo sistema comunicarem de modo a suportar a sua cooperação envolve Memória Partilhada e Troca de Mensagens. Dificuldade destes modelos: ★ Os processos necessitam de requisitar as regiões de memória partilhada e as caixas de mensagens ao sistema operativo. ★ Exemplo: Processador de texto. Threads Um processo é um programa em execução e pode ser visto como tendo duas componentes fundamentais: ★ A gestão dos recursos necessários para a execução do programa (variáveis, ficheiros abertos, processos filhos, etc...). ★ Uma linha de execução que vai percorrendo o código correspondente ao programa até atingir o final (program counter, uma stack e registos que vão guardando os valores das variáveis que estão a ser processadas num determinado momento). O conceito de thread vem separar estas duas componentes e permite assim que a um mesmo conjunto de recursos gerido por um processo possam corresponder diversas linhas de execução mais ou menos independentes. Têm a sua complexidade a nível de implementação, porque há muitas maneiras. Um programador pode dar origem a várias linhas de execução pedindo mais threads, no contexto do mesmo processo. Vantagem: não existe o conceito de Shared Text (a memória é partilhada pelas diferentes linhas de execução). Multithreaded Processes: partilham os mesmos dados no mesmo código. Uma thread tem em exclusivo: ★ Um thread ID. ★ Um program counter. ★ Um conjunto de registos. ★ Uma stack. Uma thread partilha com as restantes threads do mesmo processo: ★ Um process ID. ★ Código. ★ Memória de dados (variáveis globais). ★ Recursos (ficheiros abertos, sinais, etc..). 1 - CPU time atribuído. 2 - CPU time atribuído a outro processo. 3 - pedido de um recurso. 4 - recurso concedido. Vantagens de multithreading: » Agilidade na resposta (responsiveness) ★ Programas interactivos podem ser mais solícitos a responder aos pedidos dos utilizadores. ★ Vai demorar mais tempo porque temos várias threads a executar (o scheduler dá um bocado de tempo a cada uma), mas os utilizadores vão começar a receber as respostas aos poucos. ★ Nota: não confundir com desempenho. » Partilha de recursos ★ Forma de partilhar recursos mais simples do que a memória partilhada entre múltiplos processos. » Eficiência ★ Criação de threads mais simples do que nos processos. ★ Trocas de contexto mais simples do que nos processos. ★ É mais eficiente do que estar a fazer multitasking com processos porque são mais pesados - ao criar um processo temos de duplicar o espaço de endereçamento e a entrada da tabela de processos. » Escalabilidade ★ Melhor uso de arquiteturas multi-processador. ★ Se tiver mais recursos, os programas adaptam-se e melhoram o desempenho. Threads em C Um programa em C tem no mínimo uma linha de execução (thread ) – a que foi definida no método main. Um programa pode criar linhas de execução (threads) adicionais recorrendo à seguinte função (system call de threads): Sincronização de Processos e Threads Dois ou mais processos/threads interagem/cooperam para executar uma aplicação comum. Exemplo: ★ Um processo/thread apenas poderá prosseguir depois de outro(s)/a(s) ter(em) executado uma determinada ação. ★ Dois ou mais processos/threads partilham dados. No entanto, o acesso concorrente a dados partilhados pode resultar na inconsistência desses dados. Um processo/thread executa uma tarefa seguindo para isso uma sequência de passos (um algoritmo). Execução sequencial desses passos pode ser correta num cenário em que apenas exista um processo/thread a executar a tarefa. Execução pode falhar se vários processos/threads estiverem a executar concorrentemente essa mesma tarefa ou a manipular os mesmos dados. NOTA: neste caso, a execução do mesmo programa pode levar a diferentes soluções. » Race Conditions Situação em que várias threads acedem e modificam os mesmos dados concorrentemente e em que o resultado da execução depende da ordem pela qual o acesso aos dados se faz. Situação em que não há garantia de que os valores obtidos são equivalentes aos valores que seriam obtidos nos casos em que as duas threads/processos seriam executados sequencialmente em alguma ordem. Explicação: O problema de detetar problemas de programação concorrente é que nem sempre acontecem. Acontecem porque temos linhas de execução concorrentes e o scheduler pode interromper a execução das linhas a qualquer instante, logo pode interromper em situações que uma thread já leu o contador com determinado valor, mas depois foi executada outra thread que modifica o contador e quando a outra volta o contador já tem um valor diferente ao que tinha lido. Serialização de Secções Críticas A solução é definir o que é uma Secção Crítica. Uma Secção Crítica define um conjunto de instruções que manipulam os tais dados partilhados e não podem ser executadas concorrentemente. O processo de serialização consiste em definir as Secções Críticas e garantir que apenas um processo/thread executa as instruções correspondentes em cada instante. Se as instruções de uma Secção Crítica estão a ser executadas num dado instante por um processo/thread, outro processo/thread que tente executar as mesmas instruções será forçado a esperar que a primeira execução termine - execução em exclusão mútua. Definir as Secções Críticas dos programas e garantir: 1. Exclusão mútua no acesso à Secção Crítica: Se o processo/thread Pi está a executar uma Secção Crítica nenhum outro processo/thread pode estar a executar a mesma Secção Crítica. 2. Progresso: Nenhum processo/thread a executar fora de uma Secção Crítica (remainder section) pode bloquear outro processo/thread que deseja entrar na Secção Crítica. 3. Tempo de espera limitado: Nenhum processo/thread, após requisitar a execução da sua Secção Crítica, poderá ficar indefinidamente à espera. Variável de exclusão mútua (mutex) Objeto do SO para garantir a exclusão mútua no acesso a Secções Críticas em programas concorrentes. Oferece duas operações: ★ fechar (mutex): Chamada pelo processo/thread quando quer entrar na Secção Crítica. ○ Se a Secção Crítica estiver aberta, o processo/thread entra e fecha-a. ○ Se a Secção Crítica estiver fechada, o processo/thread bloqueia até esta ser aberta. ★ abrir (mutex): Chamada pelo programa quando quer sair da Secção Crítica. ○ Liberta a Secção Crítica. ○ Se houver processos/threads bloqueados na Secção Crítica, desbloqueia um(a). Semáforos Semáforo S – variável inteira positiva partilhada. Tem associada uma fila de processos/threads bloqueados. Apenas suporta duas operações atómicas: » Semáforos Binários Inicializados com o valor 1. Alternam entre o valor 1 e 0. Implementam a exclusão mútua. » Semáforos Genéricos Os semáforos são utilizados para sincronizar processos/threads noutras situações que não de exclusão mútua. São utilizados para sincronizar programas do tipo produtor/consumidor. Os programas produtor/consumidor são programas concorrentes em que existem processos/threads produtor que geram algum tipo de recurso (dados ou não) que será consumido pelos processos/threads consumidor (ex: serviços de impressão). Os problemas de sincronização são: ★ O consumidor só pode consumir após o produtor ter produzido. ★ Em alguns casos, se houver limite de produção, o produtor só pode produzir sempre que o limite não for atingido. Metodologia para serialização de Secções Críticas 1. Identificar as secções críticas Uma secção crítica é um conjunto de instruções que acedem e modificam uma ou mais variáveis partilhadas por vários processos/threads. 2. Associar um objeto de exclusão mútua a cada uma delas A mesma variável partilhada tem que estar protegida sempre pelo mesmo objeto de exclusão mútua. Usam-se objetos de exclusão mútua diferentes para proteger variáveis completamente independentes, que podem ser acedidas concorrentemente. 3. Invocar fechar(mutex) no início e abrir(mutex) no fim de cada secção crítica OU 4. Inicializar S=1 e invocar wait(S) no início e post(S) no fim de cada secção crítica NOTAS: ★ Se protege = 0, bloqueia tudo -> erro na inicialização do semáforo. ★ Invertendo a ordem -> entram as 2 na Secção Crítica. Monitores Coleção de procedimentos, estruturas de dados e variáveis, agrupados numa espécie de módulo, package ou objeto. Os processos/threads invocam os procedimentos/métodos contidos no monitor mas não acedem diretamente às suas estruturas de dados. Num determinado instante apenas um processo/thread pode estar ativo num monitor. Quando um determinado processo/thread invoca um procedimento é verificado se existe mais algum processo/thread ativo no monitor; se já existir, o processo/thread é suspenso até que o outro processo abandone o monitor; garante exclusão mútua. Desta forma, a exclusão mútua é garantida pelo gerador de código (compilador) e não pelo programador. A exclusão mútua é normalmente implementada através de semáforos binários. O objetivo é simplificar a programação e evitar erros. Além do suporte a problemas de exclusão mútua, os monitores oferecem suporte a esquemas de sincronização mais complexos que se baseiam em bloquear processo/threads quando estes não têm condições para prosseguir, através do conceito de: ★ variável de condição e operações WAIT e SIGNAL: Quando um processo/thread não pode prosseguir (através do teste de uma determinada condição) executa a operação WAIT numa variável de condição do monitor. Esta ação bloqueia o processo/thread. Um processo/thread, bloqueado numa variável de condição, é desbloqueado através da operação SIGNAL na variável de condição. A operação SIGNAL é executada por processos/threads que verificam que a condição esperada pelos processos bloqueados na variável de condição é satisfeita. Quando um processo/thread executa a operação SIGNAL, desbloqueando um processo/thread na fila de espera da variável de condição, deve ser garantido que processos/threads não executem o monitor simultaneamente. Se a operação SIGNAL é executada numa variável de condição na qual estão bloqueados vários processos/threads, normalmente apenas um deles é desbloqueado. O problema do Produtor-Consumidor Geralmente, este problema modela uma situação em que dois ou mais processos/threads cooperam entre si: processos/threads produtores(as) produzem informação que é consumida por processos/threads consumidores(as). A informação produzida/consumida é armazenada num buffer. O produtor produz items enquanto o consumidor consome items. Os produtores e consumidores deverão estar sincronizados de modo que o consumidor não consuma até existir items no buffer e, no caso de existir um limite para o número de items produzidos, o produtor não produza um item se não houver espaço no buffer. Monitores POSIX A API POSIX não oferece uma implementação de monitores. Para garantir o acesso em exclusão mútua a um recurso, recorre-se, como vimos, aos mutexes ou semáforos binários. Os mutexes ou semáforos binários, se usados corretamente, eliminam a ocorrência de race conditions. No entanto, um mutex, ou semáforo binário, só tem dois estados: lock e unlock. Cada uma das threads, depois de entrar na secção crítica, verifica uma condição para poder a prosseguir (ex: count < BUFFER_SIZE ou count > 0). Se a condição não se verificar, o método retorna e, neste caso particular, tenta mais tarde (na iteração seguinte). » Variáveis de condição (associadas a um mutex) Uma thread poderá verificar se pode continuar ou não, dependendo de uma condição: ★ Esta situação acontecerá, por exemplo, se a thread Produtor do sistema produtor-consumidor invocar o método enter() e o Buffer está cheio. Nesta situação, o método poderá retornar ou poderá permitir que a thread bloqueie até que a condição se verifique, fazendo pthread_cond_wait(). Nesta situação, a thread é bloqueada e liberta o mutex. Quando uma outra thread verifica que a condição é satisfeita, poderá desbloquear uma thread, fazendo pthread_cond_signal(). Quando uma thread invoca pthread_cond_wait(): ★ A thread liberta o mutex associado. ★ A thread transita para o estado de “bloqueada”. ★ Até que uma outra thread invoque pthread_cond_signal()no mesmo mutex. Quando uma thread invoca pthread_cond_signal(): ★ É selecionada aleatoriamente uma thread T da lista de threads bloqueadas na mesma variável de condição. ★ A thread T passa para o estado de ““pronta a executar”. » Sistema Produtor-Consumidor (com mutex) A thread Produtor depois de obter o mutex verifica se existe espaço no array buffer (count < BUFFER_SIZE). Se há espaço, insere o item e liberta o mutex, se não há espaço a thread Produtor faz pthread_cond_wait(). A thread Consumidor, depois de obter o mutex, verifica se existem items (count > 0). Se existem, consome o item e liberta o mutex, se não existem items a thread Consumidor faz pthread_cond_wait(). A thread Produtor, depois de obter o mutex, e inserir um item, faz pthread_cond_signal(). A thread Consumidor, depois de obter o mutex, e consumir um item, faz pthread_cond_signal(). NOTAS: pthread_cond_wait(): liberta o mutex (Produtor). pthread_cond_signal(): liberta o mutex (Consumidor). » Semáforos A sincronização de threads baseada na verificação de uma dada condição pode ser implementada recorrendo a semáforos. O número de recursos disponíveis é representado por um semáforo cujo valor inicial é o número de recursos disponíveis no início do sistema. Sempre que um recurso é consumido, o semáforo correspondente é decrementado. Sempre que é produzido um novo recurso, o semáforo correspondente é incrementado. » Sistema Produtor-Consumidor (com semáforos) Semáforo cheio: representa o número de lugares cheios no buffer. Semáforo vazio: representa o número de lugares vazios no buffer. Semáforos cheio e vazio são usados para sincronizar as threads no acesso ao buffer: ★ O cheio é inicializado a 0, é incrementado pela thread Produtor e decrementado pela thread Consumidor. ★ O vazio é inicializado a BUFFER_SIZE, é incrementado pela thread Consumidor e decrementado pela thread Produtor. NOTAS: O recurso é o nosso buffer e no início temos lugares cheios e vazios. As threads consumidoras precisam de lugares cheios e as threads produtoras precisam de lugares vazios. Logo, temos 2 semáforos para regular os recursos cheios e os vazios. SOLUÇÃO PADRÃO: 1. Verificar estado. 2. Se o estado não permitir avançar: bloquear. 3. Ficar à espera que seja libertado pelas threads que mudam o estado. Escalonamento de Processos É a tarefa de fazer a gestão de partilha do(s) CPU(s) entre um conjunto de processos/threads prontos a executar. O número de processos/threads a executar é limitado pelo número de CPUs (cores). Os restantes processos têm de esperar a sua vez mesmo que estejam prontos para serem executados. Estas atividades competem pelo CPU e deste modo surge a necessidade de fazer o seu escalonamento. » Conceitos Básicos CPU-burst: período de avanço na execução do programa. I/O-burst: período de bloqueio à espera de operações de entrada-saída de dados (I/O), sinais, etc… A execução de um processo alterna entre um CPU-burst e um I/O-burst. Duração e números de CPU bursts varia muito de programa para programa: CPU bound: processo caracterizado por CPU-bursts mais longos (poucas interrupções causadas por I/O). I/O bound: processo caracterizado por muitos CPU-bursts de curta duração (muitas interrupções causadas por I/O). A seleção de qual o próximo processo/thread a executar, quando começa e quanto tempo dura a execução é feita pelo Scheduler (componente de escalonamento), responsável pelas transições 2 e 4. As decisões de escalonamento podem ser tomadas nas seguintes situações: ★ Quando um processo transita do estado de execução para o estado de bloqueado (por exemplo, como resultado de uma operação de I/O). ★ Quando um processo transita do estado de execução para o estado de pronto (por exemplo, quando ocorre uma interrupção). ★ Quando um processo transita do estado de bloqueado para o estado de pronto (por exemplo, quando termina uma operação de I/O). ★ Quando um processo termina. » Non-preemptive scheduling (escalonamento não forçado) Permite que o processo execute até que liberte voluntariamente o CPU (fique bloqueado - transição 1) ou termine a execução. Vantagens: Fácil implementação. Desvantagens: não se adequa a sistemas multitarefa (por exemplo sistemas multi-utilizador com time-sharing). » Preemptive scheduling (escalonamento forçado) Suspensão de processos, mesmo que tenham todas as condições para executar. Necessita de suporte específico de hardware (interrupções de hardware). Problemas: as race conditions e consequentemente a necessidade de implementar mecanismos de sincronização complexos como os semáforos. Garantem normalmente tempos de resposta rápidos a processos/threads prioritários ou garantem a partilha equilibrada do CPU pelos diferentes processos/threads. Critérios de escalonamento: ★ Utilização de CPU. ★ Throughput– número de processos finalizados por unidade de tempo. ★ Turnaround time– tempo total de execução de um processo. ★ Waiting time – tempo em espera no estado de pronto. ★ Response time - tempo decorrido entre a submissão de um pedido (pelo utilizador) e o momento em que é iniciada a resposta. Objetivos de escalonamento: ★ Maximizar a utilização do CPU e outros recursos (manter o CPU ocupado). ★ Maximizar o número de processos executados por unidade de tempo (throughput). ★ Minimizar o tempo total de execução (turnaround). ★ Minimizar o tempo de resposta (response time) aos utilizadores interativos. ★ Minimizar o tempo de espera (waiting time). Algoritmos de Escalonamento » First-Come, First-Served (FCFS) O processador é atribuído pela ordem de chegada dos processos à fila de processos prontos a executar. É implementado por uma fila FIFO. Por definição é non-preemptive. O tempo médio de espera de cada processo é, no entanto, muitas vezes longo. É particularmente inadequado a sistemas de partilha de tempo. » Shortest Job First (SJF) Associa a cada processo o tempo de execução do próximo CPU-burst. Utiliza estes tempos para selecionar o processo com o CPU-burst mais curto. Dois esquemas: ★ nonpreemptive– assim que o CPU é atribuído a um processo, o processo tem garantia que termina o seu CPU burst. ★ preemptive– se um processo novo é submetido com um tempo de CPU burst menor que o tempo que falta executar ao processo corrente, há desafetação forçada. Este esquema é conhecido como o Shortest-Remaining-Time-First (SRTF). O SJF é óptimo – produz uma média de tempo de espera mínima para um dado conjunto de processos. Dificuldades do “Shortest Job First” (SJF): ★ Como determinar a duração do próximo CPU-burst? ★ Nos sistemas batch pode ser utilizado o limite de tempo de execução especificado quando um job é submetido. ★ Nos sistemas de partilha de tempo podemos aproximar o SJF se utilizarmos uma estimativa do tempo de execução do próximo CPU-burst calculada com base na duração dos CPU-bursts anteriores (deste modo, o processo com o tempo de execução do próximo CPU-burst previsto menor é selecionado). » Round Robin (RR) É atribuído a cada processo um intervalo de tempo de CPU (time quantum), normalmente entre 10 e 100ms. A fila de processos prontos é uma fila do tipo FIFO. Os processos novos são adicionados no final da fila. O Scheduler seleciona o primeiro processo da fila, configura o relógio para gerar uma interrupção dentro do tempo definido pelo quantum e despacha o processo. De seguida, uma de duas coisas pode acontecer: ★ Se o CPU burst do processo é menor que o quantum, o processo entretanto termina (ou bloqueia para I/O ou outra situação) e liberta voluntariamente o CPU; o Scheduler seleciona o processo seguinte para execução. ★ Se o CPU burst do processo em execução é mais longo do que o quantum, será gerada uma interrupção no final do quantum; o processo é inserido novamente na fila de processos prontos; o Scheduler seleciona o processo seguinte para execução; é executada uma mudança de contexto. Se existem n processos na fila de espera e o quantum é q, então cada processo obtém 1/n do tempo do CPU, dividido em quantidades de tempo q de cada vez. Nenhum processo espera mais de (n-1)q unidades de tempo até nova execução. Desempenho: ★ q grande -> FCFS. ★ q pequeno -> pode resultar em muitas mudanças de contexto (overhead). » Prioridades A cada processo é associada uma prioridade (número inteiro). O processador é atribuído ao processo com maior prioridade (normalmente, inteiro menor = maior prioridade). Dois esquemas: ★ Preemptive - se a prioridade de um processo é mais alta que a prioridade do processo corrente, há desafetação forçada. ★ NonPreemptive - o processo de maior prioridade é simplesmente colocado à cabeça da lista de processos prontos. Atribuição de prioridades: ★ Externamente - definidas segundo critérios externos ao SO, normalmente associadas a fatores económicos e políticos. ★ Internamente - o SO utiliza fatores quantificáveis para determinar a prioridade de um processo, como por exemplo, os limites de tempo, os requisitos de memória, o número de ficheiros abertos, a relação entre tempo médio de I/O-burst e tempo médio de CPU-burst (por exemplo dar maior prioridade a processos que utilizam I/O mais frequentemente - executam pouco e esperam muito). Problema: Starvation - processos de baixa prioridade podem nunca executar. Solução: Aging – à medida que o tempo progride, a prioridade dos processos que estão à espera para executar incrementa. » Multilevel Queue Scheduling A fila de processos prontos é dividida em filas separadas (ex: fila dos processos fg e fila dos processos bg). Cada fila tem o seu algoritmo de escalonamento próprio (ex: fg- RR; bg FCFS). É necessário fazer escalonamento entre filas: ★ Prioridade fixa, isto é, apenas executa processos em bg se a fila dos processos fg está vazia - Situação de starvation é possível. ★ Fatia de tempo – é atribuída a cada fila uma fatia de tempo de CPU a qual será dividida pelos processos da fila (ex: 80% to fg com RR e 20% to bg com FCFS). » Multilevel Feedback Queue A fila de processos prontos é dividida em filas separadas, os processos podem passar de umas filas para as outras. Se um processo usa muito CPU passa para uma fila com menor prioridade. Processos interativos e com muito I/O mantêm-se na fila prioritária. Processos nas filas com menor prioridade vão sendo subidos através de um processo de aging.