Fundamentos de Sistemas Operativos 2024-2025 PDF

Fundamentos de Sistemas Operativos 2024-2025 Jorge Pais  Fundamentos de Sistemas Operativos 1. Introdução O sistema operativo é o programa que mais utilização tem em qualquer computador. Seja qual for a área de funcionalidade de um utilizador do computador, desde a área...

Fundamentos de Sistemas Operativos 2024-2025 Jorge Pais  Fundamentos de Sistemas Operativos 1. Introdução O sistema operativo é o programa que mais utilização tem em qualquer computador. Seja qual for a área de funcionalidade de um utilizador do computador, desde a área meramente lúdica (jogos, mails, skype, etc) até à área de programador de sistemas (desenvolvimento de aplicações), todos eles utilizam um programa designado por sistema operativo. Os sistemas operativos mais conhecidos e utilizados são o UNIX, Linux, OSX e o Microsoft Windows. Um computador é uma arquitetura hardware que engloba os módulos designados por microprocessador, memória e portos de entrada e saída, mostrados na figura 1.1. Um exemplo duma arquitetura é o arduino que foi um microsistema com que o aluno já trabalhou na disciplina de Computação Física da LEIM. Memória Microprocessador exterior Portos de Entrada/Saída Figura 1.1: Uma arquitetura computacional básica. A programação ao nível da linguagem máquina de um microprocessador é difícil e consome muito tempo. O mesmo se passa ao nível da configuração, gestão e partilha dos componentes hardware. Desta forma, o objetivo principal Utilizadores do programa designado por sistema operativo é facilitar e maximizar a gestão máquina virtual dos recursos hardware ao criar um nível de abstração ao utilizador designado sistema operativo máquina física por máquina virtual. arquitetura A utilização da máquina virtual permite manipular os dispositivos hardware de uma forma muito mais simples e intuitiva para os vários tipos de utilizadores Figura 1.2: Os vários níveis de abstração. tal como o ilustrado na figura 1.2. 2  Fundamentos de Sistemas Operativos 2. Tipos de Sistemas Operativos 2.1. Sistemas Operativos Mono-Utilizador Os sistemas operativos mono-utilizador foram aqueles que inicialmente foram utilizados nos primeiros computadores pessoais, tais como o CPM da Digital Research ou o MS/DOS da Microsoft, estes já dos anos 80. Estes sistemas operativos eram simples e tiveram o impato de tornar credível que os computadores poderiam ser utilizados nas mais diversas funções por utilizadores heterogéneos. Tiveram o impato de desmistificar o uso dos computadores que até então eram propriedade dos especialistas em informática. 2.2. Sistemas Operativos Multi-Utilizador O primeiro sistema operativo multi-utilizador com grande divulgação e uso foi o Unix para computadores de médio porte que serviam de suporte a aplicações multi-utilizador, tal como a edição de notícias, etc. Como o Unix é um sistema operativo proprietário, então foi desenvolvido o Linux como um sistema operativo com um modelo semelhante, mas open source, o que permitiu o desenvolvimento de muitas aplicações inovadoras e foi adotado em muitas universidades americanas e europeias. Depois vem o sistema operativo Windows 3.1 da Microsoft que começou por ser uma evolução gráfica do MS/DOS mas que depois degenerou em múltiplas versões multi-utilizador e multi-processos, tais como o Windows 95 e 98, Windows XP, Windows Vista, Windows 7, 8 e 10. É sobre estes sistemas operativos multi-utilizador, multi-processo e multi-programados que vai acentar o estudo da disciplina de Fundamentos de Sistemas Operativos 3  Fundamentos de Sistemas Operativos 3. Estudo de um Sistema Operativo Um sistema operativo pode ser decomposto em camadas funcionais, cada camada é responsável pela gestão eficiente de um recurso físico da máquina hardware. Estas camadas são um modo de definir a concepção de um sistema operativo duma maneira modular e estruturada, embora as camadas não sejam inteiramente disjuntas. A abordagem ao sistema operativo vai ser feita de forma modular seguindo a hierarquia apresentada na figura 3.1. Gestão de Processos Sincronização Gestão de Memória Comunicação Ficheiros e Tarefas Figura 3.1: Abordagem modular e hierarquica a um sistema operativo. Na disciplina de FSO vamos utilizar a linguagem Java para desenvolvimento de aplicações. Assim,o sistema operativo e cada uma das camadas funcionais vão ser exploradas utilizando a API disponibilizada pela linguagem de programação. A partir desta secção o estudo de cada camada vai ser direcionada e explorada a partir da linguagem Java que acenta na Java Virtual Machine ficando o código desenvolvido portável para vários hardware alvo, desde computadores até telemóveis. 3.1. Gestão de Processos e Tarefas Por gestão de processos entende-se a partilha da máquina física por um conjunto de programas independentes ou inter- dependentes. Um processo é um programa que pode ser executado a partir do sistema operativo e que desenvolve uma determinada atividade no computador, por exemplo os editores de texto (Word, Ultraedit, NotePad, etc), os compiladores de linguagens de programação (C, C++, Java, etc), os editores de imagem (Photoshop, Paint, Illustrator, etc), os programas de comunicação (Messenger, Skype, WhatsApp, etc). Todas estas aplicações são processos que partilham os recursos físicos duma máquina e que do ponto de vista dos utlizadores dum computador estão a ser executados em paralelo. Um processo tem vários estados de funcionamento, o diagrama de estados de um processo está ilustrado na figura 3.2. fim Inicialização – o processo foi criado mas espera a Inicialização interrupção Execução Terminado atribuição de recursos. espera I/O ou evento Pronto – espera a atribuição do processador. admitido scheduler dispatch Espera Execução – está na posse da máquina física. Pronto evento ou I/O recebido Espera - espera algum evento ou comunicação. Terminado – a execução terminou e falta assinalar 4 ao Figura 3.2: Diagrama de estados de um processo. processo pai este acontecimento.  Fundamentos de Sistemas Operativos 3.1.1. Um processo em Java Em Java, um processo pode ser criado utilizando um objeto da classe ProcessBuilder tendo como parâmetro de entrada o “nomeProcesso” do tipo String. Um processo é criado a partir da instância da classe ProcessBuilder chamando o método start() da classe. No parâmetro “nomeProcesso” consta o nome do processo executável mais o respetivo caminho (path). Por exemplo: ProcessBuilder pb= new ProcessBuilder(nomeProcesso); // cria um processo Win32 passado no parâmetro de entrada. Em Java, um processo é lançado para execução utilizando o seguinte método: Process p= pb.start(); // executa um processo O código completo duma classe denominada “lancarEEsperarProcessoWin32” em Java para lançar um ou mais processos está descrito na figura 3.1.1.1. public class lancarEsperarProcessoWin32{ public static void main(String[] args) { ProcessBuilder pb; Process p; lancarEsperarProcessoWin32 lep= new lancarEsperarProcessoWin32(); public void lancarProcessoWin32(String s) { lep.lancarProcessoWin32(("c:\\Windows\\system32\\mspaint.exe"); pb= new ProcessBuilder(s); lep. esperarFimProcessoWin32(); try { // executar o processo } p = pb.start(); } System.out.println(“Processo executando."); } catch (IOException e) { p= null; } } public void esperarFimProcessoWin32(){ if (p!= null) try { p.waitFor(); System.out.println(“Processo terminou."); Figura 3.1.1.1 – Classe em Java para lançar processos de sistema Win32. } catch (InterruptedException e) { p= null; } } 5 Fundamentos de Sistemas Operativos Um programa Java pode ser executado a partir do sistema operativo, desde que convertido num ficheiro.JAR executável. Para fazer esta operação, é necessário um programa Java que tenha um método main() que é a base da aplicação para convertê-lo num ficheiro com extensão.JAR executável. Por exemplo, em eclipse a produção do ficheiro.JAR é realizado através da seguinte sequência de comandos: 1. Selecionar File-> Export->Runnable JAR file ; 2. Clicar em NEXT; 3. Definir a Launch configuration dentro das opções disponibilizadas e definir o caminho(path) e nome do ficheiro executável com extensão.JAR; 4. Clicar em Finish. O código completo duma classe denominada “lancarEEsperarProcessoJAVA” em Java executar um ou mais processos está descrito na figura 3.1.1.2. public class lancarEEsperarProcessoJAVA{ public static void main(String[] args) { // maneira de executar a partir do Java um processo JAVA Process p= null; try { p= Runtime.getRuntime().exec("java -jar C:\\Users\\jpais\\Desktop\\T1.jar “); System.out.println(“T1 executando."); } catch (IOException e) { e.printStackTrace(); } If (p!= null) { try { // esperar pelo fim do processo T1 p.waitFor(); System.out.println(“T1 terminou."); } catch (InterruptedException e) { System.err.println(e.getMessage()); } } } } Figura 3.1.1.2 – Classe em Java para lançar processos JAVA. 6  Fundamentos de Sistemas Operativos 3.1.2. Comunicação entre processos em Java A comunicação em JAVA entre processos independentes (IPC – Inter-Process Communication) na mesma máquina pode ser realizado com as seguintes tecnologias: Memória partilhada; Sockets por TCP (Transfer Control Protocol); Sockets por UDP (User Datagram Protocol). A comunicação entre máquinas diferentes é realizada pelas tecnologias: Sockets por TCP (Transfer Control Protocol); Sockets por UDP (User Datagram Protocol). Função das técnicas a passagem da informação entre processos pode demorar mais ou menos tempo, os tempos para cada uma das técnicas são da seguinte ordem de grandeza: Memória partilhada e 1 core de cpu: 1,5 microsegundos; Memória partilhada e mais de 1 core de cpu: 0,7 microsegundos; TCP e 1 core de CPU : 30 microsegundos; TCP e mais de 1 core de CPU : 22 microsegundos; UDP e 1 core de CPU: 5 microsegundos; UDP e mais de 1 core de CPU: 8 microsegundos. 7  Fundamentos de Sistemas Operativos 3.1.3. Comunicação entre processos com Memória Partilhada A comunicação em JAVA entre processos independentes (IPC – Inter-Process Communication) na mesma máquina pode ser realizado de forma eficiente através de memória partilhada que em JAVA é designada por memória mapeada. A memória mapeada em Java tem um modelo que mapeia numa área de memória virtual o conteúdo de um ficheiro. Esta memória pode ser manipulada como sendo um buffer normal sem necessidade das operações de leitura e escrita explícitas sobre ficheiro. O conteúdo desta memória pode ou não estar disponível na memória principal do processo, portanto o tempo de acesso aos dados pode variar um pouco com a utilização da memória mapeada. A classe que suporta o conceito de memória mapeada é o tipo MappedByteBuffer que tem a seguinte definição: public abstract class MappedByteBuffer extends ByteBuffer Uma instância do tipo MappedByteBuffer representa um buffer de acesso direto com conteúdo igual ao de um ficheiro. As instâncias de buffers do tipo MappedByteBuffer são criados através do método FileChannel.map e existem até as instâncias deixarem de existir no processo. Qualquer processo JAVA pode alterar o conteúdo de um MappedByteBuffer. Se o MappedByteBuffer for truncado ou fechado por um processo, a partir daqui, todos os processos deixam de aceder ao MappedeByteBuffer, gerando-se uma excepção de acesso. A manipulação de um MappedByteBuffer é exatamente igual à de um Buffer. Apenas adiciona os seguintes métodos: MappedByteBuffer force() – obriga a atualização da memória secundária com o conteúdo do buffer. boolean isLoaded() – indica se o conteúdo do buffer está em memória principal. MappedByteBuffer load() – carrega o conteúdo do buffer em memória principal. 8  Fundamentos de Sistemas Operativos Processo 1 Processo N Código Leitura Código Leitura Escrita Objeto Escrita Objeto MappedByteBuffer MappedByteBuffer Nível utilizador Leitura ou Escrita Leitura ou Escrita Nível sistémico FileChannel Leitura Escrita File Modelo da comunicação entre processos utilizando Memória Partilhada 9 Fundamentos de Sistemas Operativos Exercicio: Implemente uma classe que permita a comunicação por memória partilhada entre processos JAVA no mesmo computador. public class canalComunicacao { // ficheiro private File ficheiro; Resolução: // canal que liga o conteúdo do ficheiro ao Buffer A memória partilhada em JAVA é private FileChannel canal; uma memória mapeada de um ficheiro // buffer que tem de ser conhecido dos vários private MappedByteBuffer buffer; processos através do path e nome do // dimensão máxima em bytes do buffer ficheiro. final int BUFFER_MAX= 30; A classe para implementar a comunicação entre processos tem o // construtor onde se cria o canal nome “canalComunicacao” e tem a public canalComunicacao(){ } composição mostrada na figura 3.1.3.1. // abre o canal de comunicação public boolean abrirCanal(){} // recebe uma mensagem convertendo-a numa String public String receberMensagem() {} // envia uma String como mensagem public void enviarMensagem(String) {} // fecha o canal de comunicação public void fecharCanal() {} Figura 3.1.3.1 – Estrutura da classe ProcessoM. 10  Fundamentos de Sistemas Operativos public canalComunicacao(){ ficheiro=null; canal= null; buffer= null; } public boolean abrirCanal() { // envia uma String como mensagem // cria um ficheiro com o nome comunicacao.dat void enviarMensagem(String msg) { ficheiro = new File("comunicacao.dat"); char c; //cria um canal de comunicação de leitura e escrita buffer.position(0); try { for (int i= 0 ; i< msg.length() ; ++i){ canal = new RandomAccessFile(ficheiro, "rw").getChannel(); c= msg.charAt(i); } catch (FileNotFoundException e) { return false;} buffer.putChar(c); } // mapeia para memória o conteúdo do ficheiro buffer.putChar('\0'); try { } buffer = canal.map(FileChannel.MapMode.READ_WRITE, 0, BUFFER_MAX); } catch (IOException e) { return false;} // fecha o canal entre o buffer e o ficheiro return true; void fecharCanal() { } if (canal!=null) try { // recebe uma mensagem convertendo-a numa String canal.close(); String receberMensagem() { } catch (IOException e) { canal= null; } String msg=new String(); } char c; 1 de 2 2 de 2 buffer.position(0); while (c= buffer.getChar()) != '\0') msg += c; return msg; } 11  Fundamentos de Sistemas Operativos 3.1.4. Consistência na informação Para haver consistência na informação no acesso ao canal de comunicação, na escrita ou na leitura, tem de se garantir que só um processo de cada vez acede ao canal tanto na escrita como na leitura ou nas duas ações em simultâneo. A técnica de acesso de só um processo a um recurso físico designa-se por exclusão mútua. A exclusão mútua no acesso ao canal pode ser feito em JAVA usando um objeto da classe FileLock. Por exemplo, FileLock fl= canal.lock(); … // aceder ao canal de comunicação em exclusão mútua … fl.release(); O troço de código anterior garante que se todos os processos o executarem, só um processo de cada vez acede ao canal de comunicação. O que em caso de leitura ou escrita ou de leitura e escrita de informação no canal é garantida a consistência da informação. 3.1.5. Protocolo de comunicação O protocolo de comunicação é um conjunto de campos definidos pelo programador. Cada campo é constituído por um conjunto de bytes. O protocolo é conhecido por todos os processos, sejam escritores ou leitores, de forma a poder haver interpretação da informação recebida e assim haver comunicação entre os vários processos. A base de um protocolo de comunicação é a mensagem que pode ser dividida em vários campos. Por exemplo: Mensagem: Número: int Tipo: int Texto: String 12  Fundamentos de Sistemas Operativos 3.2. Processos leves ou Tarefas Os processos leves ou tarefas executam-se só num computador e são partes de um único processo designado por processo-pai que os lança e executa. Os processos leves cooperam dentro dum processo-pai para realizar uma funcionalidade desejada em pseudo-paralelismo num processador de um core ou em paralelismo num processador com múltiplos-cores. Os processos leves concorrem e partilham os recursos do computador e podem partilhar os dados do processo-pai. Como simplificação do texto, ao conceito de processo leve vamos abreviar e apenas designar como Tarefa. Na figura seguinte ilustra-se o modelo de memória de uma aplicação Multitarefa. Processo-pai Aplicação Code Heap start() Stack start() start() Data Shared Data Data Data Data Code Code Code Stack Stack Stack Heap Heap Heap Tarefa 1 Tarefa 2 Tarefa N 13  Fundamentos de Sistemas Operativos 3.2.1. Tarefa em Java Um processo pode ser desenhado de modo a conter múltiplas tarefas. Uma tarefa é a implementação de uma atividade dentro de um processo tendo uma estrutura de dados e código independente das outras tarefas. Uma tarefa em Java pode ser implementada como uma classe Java que deriva da classe Thread herdando assim todos os métodos desta classe. A classe Thread é acedida através da biblioteca java.lang.Thread e tem a declaração public class Thread extends Object implements Runnable. Uma classe que derive da class Thread é uma tarefa que se executa dentro duma aplicação ou processo-pai. A máquina virtual Java permite a execução de várias tarefas (Threads) dentro de um processo. Há duas maneiras para definir uma classe do tipo Thread, que de seguida se explica. 1. public class controlarRobot1 extends Thread { ArrayList comandos; controlarRobot1() { comandos= new ArrayList(); } run() { } } } O modo para criar e lançar uma instância da classe controlarRobot1 é a seguinte: controlarRobot1 cr1= new controlarRobot1(); // cria uma instância da classe controlarRobot1 cr1.start(); // lança o processo 14 Fundamentos de Sistemas Operativos 2. A outra maneira alternativa é: public class controlarRobot2 implements Runnable { ArrayList comandos; controlarRobot2() { comandos= new ArrayList(); } run() { } } } A maneira para criar e lançar uma instância da classe controlarRobot2 é a seguinte: controlarRobot2 cr2= new controlarRobot2(); // cria uma instância da classe controlarRobot2 new Thread(cr2).start(); // executa o método run() da classe controlarRobot2 15  Fundamentos de Sistemas Operativos 3.2.2. Sincronização entre Tarefas A comunicação entre tarefas exige sincronização, porque o tempo de processamento de cada tarefa e a sua execução é imprevisivel num computador, as tarefas executam-se de forma assíncrona. Portanto, para se conseguir êxito na cooperação entre as várias tarefas é preciso haver pontos de sincronismo nas atividades. Um ponto de sincronismo, é um ponto no código em que uma tarefa espera por outra tarefa em relação às atividades a executar. Quando duas ou mais tarefas acedem nas suas atividades a recursos não partilháveis, como por exemplo, dispositivos de entrada/saída, canais de comunicação, ficheiros ou dados em memória, estes dispositivos devem ser protegidos do acesso simultâneo das várias tarefas. Uma das técnicas de programação para proibir o acesso simultâneo a um recurso físico é a técnica designada por exclusão mútua. Exclusão Mútua O acesso ao robot utiliza o canal de comunicação bluetooth que é um recurso único no computador e se existirem duas tarefas no nosso computador que queiram aceder ao canal bluetooth este tem de ser feito em exclusão mútua. Por exemplo, analise o código da figura 3.2.2.1.. Tarefa 1 Tarefa 2 Se o canal bluetooth está livre Se o canal bluetooth está livre então então canal Bluetooth ocupado, canal Bluetooth ocupado, utilizar o canal Bluetooth, utilizar o canal Bluetooth, canal Bluetooth livre canal Bluetooth livre Figura 3.2.2.1 – Tarefas concorrentes a aceder a um canal bluetooth e ao mesmo recurso físico. O código da figura 3.2.2.1. está errado porque permite que dois processos acedam ao canal bluetooth simultâneamente porque a execução de cada tarefa é independente da outra e o teste do canal bluetooth estar livre pode ser feito simultâneamente e ambas as tarefas avançarem para a utilização do canal bluetooth. 16  Fundamentos de Sistemas Operativos O problema do acesso simultâneo de duas tarefas ao canal bluetooth estende-se a todos os recursos não partilháveis que incluem práticamente todos os periféricos, ficheiros para escrita e as áreas de dados que se pretendem modificar. Os recursos não partilháveis só podem ser acedidos por uma tarefa de cada vez, sendo o programa desenvolvido que deve de garantir esta exclusão mútua. Se redesenharmos o pseudo-código das tarefas 1 e 2 da figura 3.2.2.1 para o código da figura 3.2.2.2. Tarefa 1 Tarefa 2 while (getAndSet(semaforo)); while (getAndSet(semaforo)); utilizar o canal bluetooth; utilizar o canal bluetooth; semaforo= false; semaforo= false; Figura 3.2.2.2 – Tarefas concorrentes a aceder a um canal bluetooth e ao mesmo recurso físico em exclusão mútua. A exclusão mútua ao canal bluetooth é garantida pela variável “semaforo” que tem de ser conhecida pelas duas tarefas conjuntamente com a instrução getAndSet(AtomicBoolean) existente na máquina virtual Java. Esta instrução devolve o valor lógico da variável passada como parâmetro de entrada e afeta a variável com o valor true. Com esta manipulação duma variável booleana garante-se que só uma tarefa acede ao canal bluetooth de cada vez, chamando- se a esta técnica de exclusão mútua entre tarefas num acesso a um recurso não-partilhável. Semáforos em Java O conceito de semáforo foi introduzido por Dijkstra em 1965 e foi a primeira entidade que permitia a comunicação entre processos. A operação sobre um semáforo “s” que permite o incremento do seu valor inteiro designava-se originalmente por Dijkstra como V(s) (abreviatura da palavra holandesa Verhogen que significa em português Incrementar), em terminologia anglo- saxónica por signal(s) e em java por s.release() sendo s do tipo semaphore. A operação sobre um semáforo “s” que permite o decremento do seu valor inteiro quando s>0, originalmente por Dijkstra designava-se por P(s) (abreviatura da palavra holandesa Proberan que significa Testar), em terminologia anglo-saxónica por wait(s) e em Java por s.acquire(). 17  Fundamentos de Sistemas Operativos O acesso simultâneo de dois processos ao canal bluetooth resolvido em Java ficaria com o pseudo-código da figura 3.1.4.3. Tarefa 1 Tarefa 2 semaforo.acquire(); semaforo.aquire(); utilizar o canal bluetooth; utilizar o canal bluetooth; semaforo.release(); semaforo.release(); Figura 3.2.2.3 – Processos concorrentes em Java a aceder ao mesmo recurso físico em exclusão mútua. O código da figura 3.2.2.3. pode provocar um deadlock nos dois processos caso o valor do semáforo tenha sido inicializado com zero unidades. Pois cada uma das tarefas quando executam o método acquire são suspensas e ficam na lista de espera do semáforo até que outro processo faça um release. Quando os processos ficam à espera dum recurso e o recurso não é libertado por falha algoritmica ou outra falha qualquer, a esta situação designa-se por deadlock. E o efeito sentido pelo utilizador é a aplicação onde os processos estão inseridos falhar ou até mesmo parar a sua execução. Para o código da figura 3.2.2.3 funcionar, no ato de criação do semáforo, este tem de ser criado com o valor inicial de 1 para não haver deadlock nas tarefas 1 e 2. Em java o código de inicialização de um semáforo com 1 unidade e o lançamento dos processos 1 e 2 é ilustrado na figura 3.2.2.4. public class Tarefa extends Thread{ import java.util.concurrence.Semaphore; Semaphore semaforo; public static void main(String[] args) { Tarefa(Semaphore s) { Semaphore semaforo; semaforo= s; Tarefa tarefa1, tarefa2; } semaforo= new Semaphore(1); run() { tarefa1= new Tarefa(semaforo); while (true) { tarefa1.start(); semaforo.acquire(); tarefa2= new Tarefa(semaforo); utilizarCanalBluetooth; tarefa2.start(); semaforo.release(); 18 } Figura 3.2.2.4 }}  Fundamentos de Sistemas Operativos Outra situação típica de deadlock quando vários processos utilizam os mesmos recursos não-partilháveis ou esperam uns pelos outros para completar certas acções, na figura 3.2.2.5 ilustra-se outro exemplo com dois semáforos e com duas tarefas. Processo 1 Processo 2...... semaforo1.acquire(); semaforo2.aquire();....... semaforo2.acquire(); semaforo1.acquire();...... Figura 3.2.2.5 – Processos concorrentes em deadlock. Considerando que os valores iniciais dos semáforos semaforo1 e semaforo2 têm o valor unitário, 1, e quando completam a primeira execução de acquire ficam reduzidos ao valor zero, 0, então na segunda execução do acquire os dois processos ficam suspensos em cada um dos semáforos à espera que alguém faça release. Como não existe mais nenhum processo, a execução dos dois processos é suspensa ocorrendo uma situação de deadlock. A partilha de um semáforo é definida pelo seu valor inicial, se o valor for unitário apenas um processo o partilha e se o valor do semáforo for n então n processos podem partilhar o semáforo ou o recurso abrangido pelo semáforo. A ilação mais importante destes exemplos é que o deadlock pode ocorrer como resultado de uma sequência incorreta de execuções de acquire sobre vários semáforos. Existem sistemas de prova que permitem avaliar qual a probabilidade de acontecer deadlock numa determinada aplicação multi- processo. Estes sistemas de prova demonstram que seja qual for o fio de execução de um programa multi-processo para um dado semáforo inicializado com o valor N, é respeitada a condição no tempo: Quantidade(acquire)