Bem vindo ao MEGG! Este Recurso Educacional Aberto (REA) foi criado com o objetivo de ensinar sobre os conceitos de mutexes e semáforos através de teoria e animações interativas. Clique em algum tópico na barra de navegação para começar, ou em Sobre para saber mais. É recomendado que a sequência seja seguida:
Semáforos > Mutexes > Produtor / Consumidor
Welcome to MEGG! This Open Educational Resource was created aiming to teach about the concept of mutexes and semaphores through the use of theory and interactive animations. Click a topic on the navigation bar to start, or About to know more. We recommend you follow this sequence:
Semaphores > Mutexes > Producer / Consumer
Em comunicação de processos, é comum nos deparamos com o cenário da utilização de recursos compartilhados. Assim, como podemos ter vários processos tentando adquirir esse recurso, por exemplo uma região da memória, existe entre eles uma condição de disputa. Mas o que podemos fazer para tratá-la?
A resposta para essa questão é impedir que mais de um processo leia e escreva simultaneamente na região de memória compartilhada. A partir desta ideia surge o conceito de exclusão mútua, que consiste em impedir que outros processos utilizem uma variável ou qualquer outro recurso compartilhado enquanto este já estiver em uso por outro processo. A parte do código que tenta fazer o acesso à memória ou ao arquivo compartilhado é chamada de região crítica ou seção crítica. Basicamente para encontrarmos uma boa solução para esse problema da exclusão mútua, devemos satisfazer quatro princípios básicos:
Na literatura, podemos encontrar diversas formas de atacar a exclusão mútua, como desabilitar interrupções, inserir variáveis “lock”, realizar chaveamento obrigatório, utilizar a solução de Peterson ou fazer uso da instrução TSL. Porém, elas tem o problema da espera ocupada a qual prejudica o desempenho geral dos processos, pois elas fazem com que o algoritmo fique verificando continuamente se o recurso compartilhado já foi liberado ou não, fazendo com que sejam gastos ciclos de CPU para esta verificação ao invés de realizar o processamento de algum outro processo.
Desta forma, surge a técnica do sleep e wakeup, que consiste em suspender o processo enquanto o recurso compartilhado não seja liberado. Quando este recurso se tornar disponível, o processo é acordado e continua sua execução, acessando agora a região compartilhada. Assim, evitamos o problema da espera ocupada e o desperdício de processamento.
Agora você deve estar pensando que está tudo resolvido, né? Mas existe um problema que ainda não foi solucionado: imagine a situação onde temos um processo produtor (P) e um processo consumidor (C) e estes tentem acessar uma variável compartilhada count. O consumidor acabou de realizar a leitura de count e percebeu que seu valor é zero. Imediatamente após essa verificação, o escalonador decide parar de executar o processo consumidor e iniciar a execução do processo produtor. O processo produtor então também realiza a leitura de count, que ainda é zero, e logo após isso, executa uma operação que incrementa o valor de count, que possui agora valor igual a um. Ainda em execução, o processo produtor possui um comando que envia um wakeup para o processo consumidor, indicando que agora existe um item que ele pode consumir. E aí que temos o problema: o consumidor ainda não está logicamente adormecido e por isso não pode ser acordado.
Quando o escalonador resolver voltar para a execução do processo consumidor, este irá adormecer, visto que segundo a leitura realizada por ele na variável count seu valor ainda era zero, indicando que não existiam itens para serem consumidos, ele deveria dormir até que o produtor o enviasse um sinal indicando que foi produzido um item. Desta forma, com o envio de um wakeup para um processo que ainda não executou seu sleep, faz com que este sinal de wakeup seja perdido, e portanto quando o processo executar o sleep, ele nunca mais será acordado.
Neste contexto, em 1965, visando uma implementação que tratasse o problema da Exclusão Mútua, sem o uso da espera ocupada, o holandês Edsger Wybe Dijkstra propôs o uso de uma variável inteira, denominada semáforo (“Counting Semaphores”). Esta variável seria responsável por armazenar o número de sinais de acordar salvos, e assim, ela apenas assumiria valores maiores ou iguais a zero. Quando a variável tem um valor maior que zero, este indica o número de sinais de acordar pendentes para a execução.
Inspirado na técnica sleep e wakeup, Dijkstra propõe uma generalização destas operações, denominadas P e V. Porém, é mais comum na literatura encontrarmos os termos down e up como sinônimos para as siglas P e V do trabalho de Dijkstra. Quando a operação down é executada, é verificado o valor do semáforo: caso ele seja maior que zero, ocorrerá o decremento do valor (isto é, um sinal de acordar é gasto) e a execução das outras operações prosseguirá; caso o valor seja zero, então o processo será colocado para dormir, sem executar o down neste instante.
Já a operação up incrementa o valor da variável semáforo. Assim, caso exista um ou mais processos “dormindo” naquele semáforo (incapacitados de terminar a execução do down naquele instante), um deles será escolhido pelo sistema, de forma arbitrária por exemplo, para que este possa terminar seu down.
Como o semáforo implementa suas operações como chamadas de sistema, estas são realizadas como única ação atômica e indivisível, ou seja, não poderá acontecer chaveamento de contexto enquanto elas estiverem em execução. Assim, tratamos possíveis condições de corrida que possam ocorrer quando verificamos, alteramos (incremento ou decremento) o valor da variável semáforo, ou quando executamos a operação sleep.
Na animação, é possível ver que há uma geladeira, que representa um semáforo. Os gatos à sua direita representam processos. Note que se você clicar no botão up de um dos gatos, ele deixará um leite na geladeira. Isso é equivalente a executar um up no semáforo. Caso o botão down de um dos felinos seja clicado, então ele tentará retirar um leite para consumo próprio, já que todos sabem que gatos gostam de leite.
Caso exista leite na geladeira, o gato simplesmente o consumirá e ficará satisfeito. No entanto, caso um gato queira beber leite da geladeira e ela esteja vazia (sem leite), ele deve aguardar - dormindo, no caso - até que o leite esteja disponível na geladeira. Quando o outro gato preencher a geladeira com um litro de leite, o gato que estiver dormindo recebe um sinal de wakeup para que possa acordar e consumir o leite que está disponível na geladeira.
Note que na animação não é possível executar mais de uma operação ao mesmo tempo: não é possível por exemplo, um gato tirar leite da geladeira enquanto o outro está colocando. Isso representa a atomicidade das operações relacionadas a semáforo, onde temos que completar todas as operações, sem que exista condição de corrida entre os gatos.
In process communication, it’s common to face a situation where there are shared resources. So, as we can have lots of processes trying to acquire this resource, i.e. a memory region, there’s between them a race condition. But, how can we deal with it?
The answer for this question is preventing that more than one process read and write in this shared memory region at the same time. From this idea arises the mutual exclusion concept, that consists in preventing that other processes use the variable or any other shared resource while it’s already being used by another process. The piece of the algorithm that tries to access the shared memory or file is called critical section. Essentially, we need to satisfy four basic principles to find a good solution for the mutual exclusion problem:
In the literature, we can find lots of ways to attack mutual exclusion, like disabling interruptions, inserting lock variables, doing strict alternation, using Peterson’s solution or TSL instruction. However, they have busy waiting problem which affects processes general performance, because it’s a technique in which a process repeatedly checks to see if shared resource has already be realeased or not, spending CPUs times in this examination instead of processing another process.
In this way, arises sleep and wakeup technique, that is based on suspending the process while the shared resource is not released. When this resource becomes available, the process is waked up and goes on its execution, accessing shared section now. By this way, we avoid busy waiting problem and processing time spending.
Now you must be thinking that everything is okay, aren’t you? But there’s a problem that isn’t solved yet: imagine a situation where we have a producer process (P) and a consumer process (C) and they try to access a shared variable called count. The consumer has already read count and realized that its value is zero. Immediately, scheduler decides to pause executing consumer process and starts processing producer process. And then, producer process also reads count value, that is still zero, and after it, executes an operation that increases count value, that has value equal to one. Still running, producer process has a command that sends a wakeup signal to consumer process, indicating that there’s now an item that he can consume. And then, we’ve got a problem: consumer isn’t logic asleep yet and that’s why he can’t be awaken.
When the scheduler decides to go back consumer process execution, it’s going to sleep, because count value read by him was equal to zero yet, which indicates that there’s no items to be consumed, and then consumer shoud sleep until producer send him a signal an item has been produced. So, sending a wakeup signal to a process that hasn’t executed his “sleep”, mades this wakeup signal be lost, and then, when the process executes his sleep, he’s going to sleep forever.
In this context, in 1965, looking for an implementation that lead with mutual exclusion problem, without using busy waiting, a Dutch researcher, Edsger Wybe Dijkstra, has proposed the use of an integer variable, called semaphore. This variable would be responsible for storing the number of saved wakeup signals, and then, it would only admit values greater or equal to zero. When a variable has a value greater than zero, it represents the number of pending wakeup signals for the execution.
Inspired by sleep and wakeup technique, Dijkstra has proposed general operations, called P and V. Although, it’s more commom in literature we find down and up terms as synonyms for the operations described in Dijkstra’s project. When an operation down happen, it’s verified if smaphore value: if it’s greater than zero, semaphore value is going to be decreased (i.e., a wakeup signal is spent) and execution of the rest of the operations is going to go on; but if the vale is equal to zero, the process is going to sleep, without executing down in this moment.
The operation up increases semaphore value. Therefore, if there’s one ou more processes sleeping (processes that are unable to execute down operation in that time) in that semaphore, one of them is going to be chosen, arbitrarily for example, to finish its down operation.
As semaphore implements its operations as system calls, they are executed as an atomic and indivisible action, so context switch can’t happen while these operations are running. By this way, we deal with race conditions that can happen while we verify, change (increasing or decreasing) semaphore value, or when we execute sleep operation.
In this animation, it’s possible to see there’s a fridge, that represents a semaphore. The cats which are in the right place of the screen represents the processes. You can notice you click on up button of one of the cats, this cat will bring a milk bottle in the fridge. It’s equivalent to execute an up operation on semaphore, that is represented by the refrigerator. If down button of any of the cats was pressed, the cat is going to try to withdraw a milk bottle to consume, since all of us know that cats love milk.
If there’s milk bottles int the fridge, the cat is going to consume it and be pleased. However, if there’s no milk bottle for the cat inside the fridge, the cat must wait, sleeping in this case, until a milk bottle is available in the refrigerator. When the other cat takes a milk bottle to the fridge, the sleeping cat receives a wakeup signal so he can wake up and consume the milk bottle it’s available in the fridge.
Note that in the animation isn’t possible to execute more than one operation at the same time: it’s not possible, for example, a cat removes a milk bottle from the fridge while the other cat is inserting a milk bottle. It represents the atomicity of the operations related to the semaphore, where we have to complete all the operations, without a race condition between the cats.
Nem sempre é necessário ter uma primitiva de sincronização que armazena sinais de wakeup. Por exemplo, pode-se apenas querer garantir a exclusão mútua no acesso a um recurso, sem que se necessite da capacidade de contagem do semáforo. Nesse caso, é possível usar uma primitiva de sincronização mais simples: o mutex, uma especialização do semáforo.
Um mutex tem duas operações fundamentais: lock (impedido) e unlock (desimpedido). A operação lock consiste numa operação atômica de tentar adquirir alguma região crítica que o mutex protege. Caso esta esteja disponível, a região é cedida ao processo que o requisitou. Caso não esteja disponível, o processo é bloqueado até que o processo que adquiriu o recurso libere-o através da operação unlock. É claro que a semântica disso depende completamente de quem está programando, visto que qualquer processo pode executar a operação unlock em qualquer mutex, mesmo que não o detenha.
Além disso, outro problema que pode surgir ao se usar mutex é se um processo que já detém um mutex tentar executar a operação lock no mesmo mutex novamente. Nesse caso, o que acontece a seguir é definido pela implementação do mutex, mas geralmente o que acontece é que o processo fica eternamente bloqueado, esperando pelo unlock do mutex no qual ele mesmo deveria executar a operação unlock, mas não pode fazê-lo por estar bloqueado.
Análoga a animação do semáforo, esta animação se difere pelo fato que existe apenas um litro de leite que pode ser acessado pelos dois gatos. Assim, caso um gato queira tomar posse do litro de leite, ele chama a operação use que é análoga a operação lock do mutex. É válido lembrar que no caso do mutex, quando o gato que estiver de posse do litro de leite terminar de usá-lo, este já o libera, executando a operação de unlock do recurso compartilhado (litro de leite).
It’s not always necessary to have a synchronization primitive that stores wakeup signals. For example, you may want to only guarantee mutual exclusion in the access of a resource, without the counting ability of a semaphore. In this case, it’s possible to use simpler sinchronization primitive: the mutex, a specialization of the semaphore.
A mutex has two fundamental operations: lock (blocked) and unlock (unblocked). The lock operation consists in an atomic operation of trying to acquire a critical region that the mutex protects. In case it’s available, the region is given to the process which requested it. In case it’s not available, the process is blocked until the process that acquired it frees it through the unlock operation. Of course, the semantic of this depends completely on the programmer, since any process can execute the unlock operation of any mutex, even if it doesn’t actually acquired it.
Furthermore, another problem can emerge when you use a mutex is if the process that already holds the mutex tries to execute the lock operation in the same mutex, again. In this case, what happens next is defined by the mutex implementation, but usually what happens is that the process remains eternally blocked, waiting for the unlock of the mutex on which it should execute the unlock operation, but can’t do it because it’s blocked.
Analogous to the semaphore animation, this animation is different because there is only one milk bottle that can be accessed by the two kitties. Therefore, if a kitty wants to acquire the milk, it calls the use operation, which is analogous to the mutex’ lock operation. It’s valid to remember that in the mutex case, when the kitty that holds the milk finishes using it, it frees the “milk resource”, executing the unlock operation of the shared resource.
O problema do Produtor-Consumidor é um problema clássico da área de comunicação entre processos. Geralmente, tratamos de apenas um único produtor e um único consumidor, para efeito de simplificação, porém a teoria pode ser ampliada para n produtores e n consumidores, bastando apenas que a semântica seja seguida.
Basicamente a dinâmica ocorre da seguinte maneira: existe o produtor que insere um item no buffer e o consumidor consome os itens produzidos que estão armazenados no buffer. A ideia é simples, não? Porém existem alguns problemas como a tentativa de inserção de um novo item no buffer cheio e de consumo de um item do buffer vazio.
Para solucioná-los, existem diversas técnicas, tais como troca de mensagens, monitores, semáforos, mutexes, etc. Neste trabalho, vamos abordar uma solução que contempla o uso de semáforos.
Na animação, podemos ver um cenário que ilustra o problema: a galinha (processo produtor) produz ovos que são armazenados no ninho (buffer) e que são coletados pelo fazendeiro (processo consumidor).
Logo no início, percebemos que o processo do fazendeiro é escalonado primeiro. Este tenta colher os ovos do ninho, porém como este está vazio, o fazendeiro é colocado para dormir, através da operação sleep, onde fica esperando que a galinha comece a botar ovos. Quando a galinha é escalonada e bota o primeiro ovo, o fazendeiro recebe um sinal de wakeup, e então acorda e coleta o ovo do ninho.
Neste momento, a galinha é escalonada novamente, e bota dois ovos, quando o fazendeiro é escalonado e começa a coletar os ovos do ninho. Nesta etapa o fazendeiro consegue coletar todos os ovos do ninho, e quando tenta continuar coletando, acaba sofrendo um sleep, pois não existem mais ovos no ninho.
Então, a galinha é novamente escalonada e recomeça o processo. Como o fazendeiro está dormindo a espera de um ovo, quando a galinha começa a botar, o fazendeiro recebe o sinal de wakeup e sai do estado adormecido. A galinha então bota três ovos até que o fazendeiro é novamente escalonado.
O fazendeiro então inicia o processo de coleta até que esvazie o ninho e adormeça novamente à espera de novos ovos. A galinha é novamente escalonada e reinicia o processo, botando quatro ovos, até que o ninho esteja cheio, visto que neste caso, definimos o ninho cheio com quatro ovos. Assim, quando ela tenta botar o quinto ovo, ela recebe um sinal de sleep pois não há mais espaço no ninho para receber ovos.
Desta forma, ela aguarda até que o fazendeiro reinicie seu processo de coleta e possa liberar espaço no ninho. Quando isso ocorre, a galinha recebe um sinal de wakeup e sai do estado de adormecido. O processo do fazendeiro continua coletado mais um ovo até que o escalonador resolve retornar à galinha que bota mais ovo, finalizando o exemplo.
Por meio desta animação, podemos verificar que o ninho se torna uma região crítica do nosso problema, sendo que produtor e consumidor não podem executar operações simultaneamente sobre ele, visando assim solucionar o problema da condição de disputa.
The Producer and Consumer problem is a classical one in the area of process communication. Usually we only have a single producer and a single consumer, for simplification purposes, but the problem can be generalized to an arbitrary amount of N producers and N consumers, as long as the logic behind the problem is kept.
Basically, it happens this way: there is the producer which inserts an item in the buffer, and the consumer consumes the produced items that are stored in the buffer. The idea is simple, right? However, there are a few problems like trying to insert a new item in a full buffer, or trying to consume an item from an empty buffer.
To solve them, there are many techniques, like message passing, monitors, semaphores, mutexes, etc. Here, we will approach a solution that contemplates the use of semaphores.
In the animation, we can see a scenario that illustrates the problem: a chicken (the producer thread) produces eggs that are stored in the nest (or, the buffer) and that are collected by the farmer (the consumer thread).
Right in the beginning, we noticed that the farmer’s process is scheduled first. It tries to collect eggs from the nest, but since it’s locked, the farmer is put to sleep, by means of the sleep operation, where it waits until the chicken lays eggs. When the chicken is scheduled and lays their first egg, the farmer receives a wakeup signal. He then awakes and collects the egg from the nest.
In this moment, the chicken is scheduled again, and lays two eggs. Then the farmer is scheduled and starts collecting eggs from the nest. In this situation, the farmer can collect all the eggs from the nest, and when he tries to keep collecting, he goes through a sleep operation, since there are no more eggs in the nest.
Then the chicken is scheduled again and restarts the process. Since the farmer is sleeping while he waits for an egg, when the chicken starts laying eggs the farmer receives a wakeup signal and exits the sleeping state. The chicken lays three eggs and then the farmer is scheduled again.
The farmer starts collecting until he empties the nest and sleeps again waiting for new eggs. The chicken is scheduled again and restarts the process, laying four eggs, until the nest is full, since, in this case, we defined the nest as being full when it has four eggs. When the chicken tries to lay the fifth egg, it received a sleep signal since there is no more room in the nest.
This way, she waits until the farmer makes room for new eggs by collecting them. When this occurs, the chicken receives a wakeup signal and exits the sleeping state.The farmer process continues collecting one more egg until the scheduler decides to return to the chicken, which lays one more egg, finalizing the example.
Through this animation, we can see that the nest acts as a critical region of our problem, where the consumer and the producer can’t execute operations simultaneously, thus solving through a mutex the race condition.
Este projeto foi desenvolvido por alunos atualmente do curso de Engenharia de Computação, das unidades ICMC e EESC, da Universidade de São Paulo (USP) de acordo com as exigências da disciplina de Sistemas Operacionais, ministrada pelo professor Paulo Sérgio Lopes de Souza, e tem como objetivo elucidar o conceito de mutexes e semáforos, através de animações interativas e teoria.
Denilson A. Marques Junior
denilsonjnr6@gmail.com
Elisa Jorge Marcatto
elisamarcatto@gmail.com
Lucas Tomazela
tomazela.lucas@gmail.com
Victor Marcelino Nunes
victor95nunes@gmail.com
TANEMBAUM, Andrew S. Modern Operating Systems. Editora Pearson Prentice Hall, Upper Saddle River, 3a edição, 2008.
This project was developed by Computer Engineering graduate students, from ICMC and EESC, of University of São Paulo (USP), for the course of Operating Systems, given by the professor Paulo Sérgio Lopes de Souza, and aims at elucidating the concept of mutexes and semaphores, through theory and interactive animations.
Denilson A. Marques Junior
denilsonjnr6@gmail.com
Elisa Jorge Marcatto
elisamarcatto@gmail.com
Lucas Tomazela
tomazela.lucas@gmail.com
Victor Marcelino Nunes
victor95nunes@gmail.com
TANEMBAUM, Andrew S. Modern Operating Systems. Publisher Pearson Prentice Hall, Upper Saddle River, 3rd edition, 2008.