Gerenciamento de Memória no Linux

(Créditos para Gustavo Pinheiro e Leandro Lima)

• Características gerais

Assim como todos sistemas Unix recentes, Linux oferece uma abstração para gerenciamento de memória chamada memória virtual (virtual memory). Tal camada permite que muitos processos sejam executados simultaneamente, aplicações sejam executadas mesmo se necessitarem de quantidade de memória física superior à existente, entre outras vantagens.

Em geral, um esquema que mistura paginação e segmentação é utilizado para contruir o esquema de memória virtual. Entretanto, o Linux utiliza segmentação de forma extremamente limitada. Linux prefere paginação à segmentação por motivos de portabilidade e para tornar o gerenciamento de memória mais simples. Na versão 2.4, por exemplo, segmentação é utilizada apenas quando exigida pela arquitetura 80x86.

Como a maioria dos processos utilizam apenas uma pequena porção do espaço total de endereço virtual, Linux utiliza uma estrutra hierárquica para a tabela de páginas, constituída por três níveis. Isto permite que as subárvores correspondentes a regiões não utilizadas do espaço de endereço estejam ausentes, economizando espaço.

Proteção é garantida já que cada processo no sistema tem seu próprio espaço de endereço virutal. Estes estão separados de modo que um processo executando determinada apliacação não pode afetar um outro. Além disso, mecanismos de hardware permitem que determinadas regiões de memória estejam protegidas contra escrita. Isso evita que código e dado sejam sobrescritos por aplicações maliciosas.

• Funcionamento do Translation Lookaside Buffer (TLB)

TLBs são utilizados para acelerar o processo de tradução de endereços virtual para o físico correpsondende. Quando um endereço virtual é utilizado pela primeira vez, o endereço físico correspondente é computado através de acessos lentos a tabela de páginas. O endereço físico encontrado é então armazenado em uma entrada TLB para que futuras referêcias àquele endereço virtual tenham tradução rápida.
Assim, cada vez que uma referência a um endereço virtual é feita, o processador tentará encontrar uma entrada correspondente no cache (TLB). Se não encontrar na TLB, deve sinalizar para o Sistema Operacional que uma TLB miss ocorreu. O SO então gera uma nova entrada TLB. Quando a exceção for eliminada, o processador tentará mais uma vez buscar o endereço na TLB, desta vez com sucesso. A desvantagem deste esquema é que tempo e espaço são gastos para manter tal cache.

• Tabelas de páginas (page tables)

As tabelas de páginas são as estruturas de dados que mapeiam endereços virtuais para endereços físicos e se encontram na mémoria principal (main memory). Devem ser apropriadamente inicializadas pelo kernel antes que a unidade de paginação seja iniciada.
O acesso à tabela de páginas é realizado em três passos, o que corresponde ao esquema de três níveis adotado em Linux. As três tabelas são: Page Global Directory, Page Middle Directory e Page Table. O objetivo desse esquema é reduzir a quantidade de RAM necessária por tabela de página por processo. Ele reduz a memória necessária já que requer Page Tables apenas para as regiões da memória virtual de fato utilizadas por um processo.

• Remoção de Páginas no Linux

O mecanismo de swappping é extremamente valioso por permitir a expansão do espaço de endereços (address space) utilizável por um processo, assim como a quantidade de RAM necessária para carregar determinada aplicação. Para que seja efetivamente bem sucedida, faz-se necessário eficientes algoritmos para a remoção de páginas, permitindo que o swap ocorra.

Vários kernels têm utilizado algoritmos Least Recently Used (LRU). A prinicpal idéia é utilizar um contador que armazena a idade da página junto de cada página na RAM (isto é, o intervalo de tempo desde o último acesso à referida página). A página mais velha pode então ser removida.

• Interfaces para gerenciamento de memória

Em Linux, processos são criados através das system calls clone(), fork() e vfork(). Esta última cria um processo que compartilha o espaço de endereços do procesos pai. A flag CLONE_VM permite demandar que o processo filho compartilhe o memory descriptor e todas tabelas de páginas.
Quando da criação de um novo processo, o kernel invoca copy_mm() para criar o espaço de endereços do processo e settar todas tabelas de páginas e memory descriptor do novo processo.
Quando um processo termina, o kernel invoca exit_mm() para liberar o espaço de endereços daquele processo.

Note ainda que um processo pode criar um novo mapeamento de memória através da chamada mmap().

• Compartilhamento de Memória no Linux

Um dos mecanismos mais úteis para intercomunicação de processos é o compartilhamento de memória, o qual permite que processos acessem estruturas de dados comuns em uma região de memória compartilhada. Cada processo que desejar acessar as estruturas de dados presentes em uma região de compartilhamento deve adicionar ao seu próprio espaço de endereços uma nova região de memória que mapeia as páginas associadas à região compartilhada. Tais page frames podem então ser facilmente manipuladas pelo kernel através do mecanismo de paginação por demanda.

• Mapeamento de arquivos na memória virtual

Através deste mapeamento, arquivos são carregados espaço de endereços de um processo. À medida que necessário, as partes dos arquivos são carregadas em memória. O kernel fica então responsável por traduzir o acesso aos bytes dentro de uma página em uma operação no arquivo correspondente. As estruturas de dados utilizadas para tal procedimento são:

• inode associado com o arquivo mapeado
• address_space
• file object para cada mapeamento feito por um processo diferente
• vm_area_struct
• page descriptor
  

• Tratamento de áreas de memória fixas

Pelo menos 128MB de endereços virtuais são sempre deixados disponíveis pois o kernel utiliza tal espaço para implementar alocação de memória não-contígua e área de memória de mapeamento fixos. Basicamente, um área de memória de mapeamento fixo é um endereço virtual cosnte como 0xfffff0 cujo endereço físico correspondente pode ser settado de forma arbitrária. Assim, cada endereço fixo mapeia um frame de memória física. Com relação a ponteiros de variáveis, estes endereços são mais eficientes. Basta notar que para dereferenciar um ponteiro de varíavel requer um acesso de memória a mais que dereferenciar um endereço constante imediato.

• Segurança

Tradicionalmente, sistemas Unix associam credenciais a cada processo, as quais ligam o refererido processo a um usuário específico de determinado user group. Tais credenciais são importantes em sistemas multi-usuários pois determinam o que cada processo pode ou não fazer, preservando portanto a integridade dos arquivos de um usuário e a estabilidade do sistema como um todo.
O uso desste mecanismo requer suporte tanto nas estruturas de dados do processo assim como naquilo que está sendo protegido, por exemplo, arquivos. Assim, no sistema de arquivos Ext2, cada arquivo pertence a um usuário específico, o qual decide que tipo de operações são permitidas naquele arquivo. Quando um processo tenta acessar um arquivo, o VFS sempre checa se tal acesso é permitido, de acordo com as permissões estabelecidadas pelo dono do usuário e credenciais do processo.

• Área de swap

As páginas removidas de memória são armazenadas na área de swap, a qual pode ser implementada tanto como uma partição de disco própria ou como um arquivo em uma partição maior. Muitas áreas de swap podem ser definidas, até um um número máximo especificado por
MAX_SWAPFILES (normalmente 32).
As informações contidas em uma área de swap são úteis enquanto o sistema estiver ligado. Quando este for desligado, todos os processos são destrúidos, então toda informação armazena nas áreas de swap pelos processos é descartada.
O tamanho máximo de uma área de swap é determinado pelo número de bits disponíveis para identificar um slot de página. Na arquitetura 80x86, 24 bits estão disponíveis portanto o limite para o tamanho da área de swap é 224 slots (64 GB).

• Experimentos

A fim de testar os limites do sistema, alguns experimentos foram realizados. Utilizamos o MacOSX, o qual utiliza o kernel Darwin (compatível com a Single UNIX Specification). Utilizando o comando ulimit -a , o sistema informa que o número máximo de processos de usuário possível é 266. Um simples programa que chama fork() continuamente foi executado, e tal valor foi confirmado.
Para testar o máximo tamananho de área heap, podemos executar um programa que continuamente pede alocação de memória para um inteiro, por exemplo.
O tamanho máximo de pilha é 8MB. Como mencionado anteriormente, existe um tamanho máximo para a área de swap, portanto ela pode ser esgotada.

• Referencias

Understand the Linux Kernel. By Daniel P. Bovet, Marco Cesati

Gerenciamento de Memória no Linux - Uma visão geral

Olá caros leitores!

Iniciamos aqui uma nova série de posts relacionados a Sistemas Operacionais, como parte do curso CES-33 (ITA), ministrado pelo Professor Edgar Yano. Os créditos desta nova série vão para Gustavo Pinheiro e Leandro Lima (Engenharia de Computação ITA - Turma 2010).

Abordaremos o complexo problema de "Gerenciamento de Memória no Linux", tocando nos seguintes pontos:

1. Características gerais
2. Funcionamento do Translation Lookaside Buffer (TLB) no Linux.
3. Acesso e localização das Tabelas de Páginas (page tables).
4. Algoritmos e estruturas de dados para remoção de páginas.
5. Gerenciamento de memória na criação e destruição de processos, troca de contexto e page-faults.
6. Como utilizar memória compartilhada?
7. Como mapear arquivos na memória virtual?
   
8. Tratamento de áreas de memória fixas.
9. Segurança
10. Áreas de swap.

Até o próximo post, quando todos tópicos acima mencionados serão respondidos!

Projeto 2 (Device Drivers)

(Créditos para Gustavo Pinheiro e Leandro Lima)

1. Introdução:

Um device driver é um módulo carregável do kernel que gerencia a transferência de dados entre um dispositivo e o sistema operacional. Módulos carregáveis são carregados no momento do boot, ou por pedidos e são descarregados por pedidos. Um device driver é uma coleção de rotinas em C e estruturas de dados que podem ser acessados por outros módulos do kernel. Essas rotinas devem usar interfaces padrão chamadas de pontos de entrada. Pelo uso de pontos de entrada, os módulos requisitantes ficam isolados dos detalhes internos do driver. Esses componentes são muito importantes, pois tornam a programação muito mais simples, assumindo a responsabilidade por tratar com as complexidades de cada dispositivo instalado. Os drivers atuam basicamente como atores entre o dispositivo e o aplicativo ou o sistema operacional que o utiliza. O código de alto nível pode ser escrito indepedentemente dos hardwares controlados. Cada versão de um dispositivo, como impressoras, requerem comandos especializados. Por outro lado, a maioria dos aplicativos acessam os dispositivos (como ao enviar um arquivo para a impressora) utilizando comandos de alto nível (por exemplo, println). O driver aceita essas sentenças genéricas e as convertem em comandos de baixo nível que o dispositivo possa entender.

Sem esses drivers, o computador não consegue estabelecer nenhuma comunicação externa, através dos dipositivos nele instalados. Não haveria maneiras de entrar com dados, nem de lê-los. Dentro do kernel do Linux, os device drivers ocupam uma parte bastante significativa. Assim como em outras partes do sistema operacional, eles devem operar em ambientes com alto nível de privilégio. Por isso, muito cuidado deve ser tomado ao programá-los.

Os device drivers para Linux são gerenciados pelo próprio kernel. Os módulos aqui trabalham como device drivers. Os módulos podem interagir com kernels diretamente. Quando desenvolvemos device drivers, utilizamos a estrutura de módulos para especificar rotinas personalizadas.

Para carregar o driver, usamos module_init e para descarregar, usamos module_exit. Quando module_init é executado, a primeira rotina também é executada. O kernel registra os drivers usando uma rotina de registro register_chrdev ao carregar o módulo, e ao descarregar o módulo usa unregister_chrdev. Isso funciona para dispositivos de caracteres.

No Linux, dispositivos são rotulados por números (0-255). Esses 256 números são conhecidos por números maiores. Um número maior é atribuído a um dispsositivo em particular. Com isso, o Linx pode manipular 256 dispositivos de uma vez (dispositivos maiores). Cada dispositivo maior pode manipular mais 256 dispositivos adicionais de seu tipo (o total fica em 256x256=65535). O arquivo documentation/devices.txt deve possuir a lista de todos os dispositivos maiores.

Os aplicativos não podem acessar o dispositivo pelo número maior diretamente. Em vez disso, eles usam as entradas do sistema de arquivos. Um ponto forte do Linux é que ele pode tratar todos os dispositivos físicos, dispositivos virtuais e sistemas de arquivos reais como sistemas de arquivos. Isso nos possibilita utilizar uma estrutura genérica para todos eles, sem precisar saber que tipo de dispositivo estamos usando. Todos os pontos de entrada de drivers estão localizados num diretório /dev. Por exemplo, /dev/tty1 é a porta serial 1 (COM1). Aplicativos que quiserem usar um driver, utilizam uma chamada de sistema para conseguir o manipulador do dispositivo. Uma vez que consegue o manipulador, ele ganha acesso aos dispositivos e pode usar o dispositivo pelas outras chamadas de sistema.

Figura 1 – Esquema de hardware/software

2. Requisitos:

As principais características de um driver são:

• Executar gerenciamento de I/O
• Prover gerenciamento de dispositivos transparente, evitando programação de baixo nível (ports).
• Aumentar a velocidade de I/O, porque normalmente ela já é otimizada.
• Incluir gerenciamento de erro para hardware e software. - Permitir o acesso concorrente aos diversos processos de hardware.

Há 4 tipos de drivers: character drivers, block drivers, terminal drivers e streams.

Character drivers transmitem informação do usuário para o dispositivo (e vice-versa) byte por byte (figura 2). Dois exemplos são a impressora, /dev/lp, e a memória (também é dispositivo), /dev/mem.

Figura 2 - Character Drivers

Block drivers (figura 3) transmitem informação bloco por bloco. Isso significa que os dados que chegam (do usuário ou do dispositivo) são armazenados num buffer até que o buffer se encha. Quando isso ocorre, o conteúdo do buffer é fisicamente enviado ao dispositivo ou ao usuário. Essa é a razão pela qual todas as mensagens impressas não aparecem na tela quando um programa trava (as mensagens no buffer são perdidas), ou a luz do disquete nem sempre acende quando o usuário escreve em um arquivo. Os exemplos mais claros desse tipo de driver são discos: disquetes (/dev/fd0), discos rígidos IDE (/dev/hda) e discos rígidos SCSI (/dev/sd1).

Figura 3 - Block Drivers

Terminals drivers (figura 4) constituem um conjunto especial de character drivers para comunicação do usuário. Por exemplo, ferramentas de comando em um ambiente de janelas abertas, um terminal X ou um console são dispositivos que requerem funções especiais, por exemplo, as setas para cima e para baixo para um gerenciador de buffer de comando ou procedimentos especiais para drivers de tabulações, para lidar com todas as características especiais.

Figura 4 - Terminal Drivers

Streams são os drivers mais novos (figura 5) e são projetados para fluxo de dados de velocidades muito altas. Ambos o kernel e o driver incluem diversas camadas de protocolos. O melhor exemplo desse tipo é um network driver.

Figura 5 - Stream Drivers

Como foi dito, um driver é uma parte de um programa. Ele é composto por um conjunto de funções em C, algumas das quais obrigatórias. Por exemplo, para um dispositivo de impressão, algumas funções típicas somente chamadas pelo kernel podem ser:

lp_init(): Inicializa o driver e é chamada apenas no momento do boot.
lp_open(): Abre uma conexão com o dispositivo.
lp_read(): Lê a partir do dispositivo.
lp_write(): Escreve no dispositivo.
lp_ioctl(): Executa operações de configuração de dispositivo.
lp_release(): Interrompe a conexão com o dispositivo.
lp_irqhandler(): Funções específicas chamadas pelo dispositivo para manipular interrupções.

Algumas funções adicionais estão disponíveis para alguns aplicativos, como *_lseek(), *_readdir(), *_select() e *_mmap().

3. Ferramentas:

Para se desenvolver device drivers no Linux, é necessário possuir um conhecimento de:

• Programação em C. É necessário ter conhecimento profundo dessa linguagem, notadamente no que diz respeito ao manuseio de ponteiros e manipulação de funções.

• Microprogramação. É necessário saber como os microcomputadores funcionam internamente (endereçamento de memória, interrupções, etc). Todos esses conceitos devem ser familiares para um programador de assembly.

4. Desenvolvimento:

O kernel do Linux suporta dois principais tipos principais de drivers USB: drivers em sistema host e drivers em um dispositivo. Os drivers USB para um sistema host controlam os dispositivos USB em que são conectados, pelo ponto de vista do host (um host USB comum é um computador desktop). Os drivers USB, num dispositivo, controlam como aquele dispositivo é visto pelo computador host como um dispositivo USB. Como o termo ”USB device drivers” é um pouco confuso, os desenvolvedores USB criaram o termo “USB gadget drivers” para descrever os drivers que controlam um dispositivo USB que se conecta a um computador. Os drivers USB residem entre os diferentes subsistemas do kernel (block, net, char, ...) e os controladores de hardware USB. O USB core fornece uma interface para drivers USB utilizarem e controlar o hardware USB, sem se preocupar com os diferentes tipos de controladores de hardware USB presentes no sistema.

Desenvolvendo um Driver USB

A abordagem para se desenvolver um driver USB é similar à de um PCI: o driver registra seus objetos com o subsistema USB e depois usa identificadores da marca e do dispositivo para dizer se seu hardware foi instalado.

Dispositivos suportados pelo driver

A estrututura da struct usb_device_id fornece uma lista de diferentes tipos de dispositivos USB que este driver suporta. A lista é usada pelo USB core para decidir a qual driver deve fornecer um dispositivo, e, pelos scripts hotplug, decidir que driver carregar automaticamente quando um dipositivo específico é conectado ao sistema.

A estrututura struct usb_device_id é definida com os seguintes campos:

__u16 match_flags
Determina qual dos campos a seguir na estrutura o dipositivo deve ser correlacionado. Esse é um campo pequeno definido pelos valores USB_DEVICE_ID_MATCH_* especificados no arquivo include/linux/mod_devicetable.h. Esse campo normalmente não é diretamente definido, mas é inicializado pelas macros do tipo USB_DEVICE definidas posteriormente.

__u16 idVendor
A ID USB da marca para o dispositivo. Este número é atribuído pelo fórum USB aos seus membros e não pode ser criado por mais ninguém.

__u16 idProduct
A ID USB do produto para o dispositivo. Todas as marcas que possuem uma ID de marca atribuída a eles podem gerenciar suas IDs de produtos de qualquer modo que escolherem.

__u16 bcdDevice_lo __u16 bcdDevice_hi
Definem os finais inferior e superior da extensão de todos números da versão dos produtos atribuídos a uma marca. O valor bcdDevice_hi é inclusivo; seu valor é o número do dipositivo com a maior numeração. Ambos esses valores são expressos na forma decimal de codificação binária (BCD). Essas variáveis, combinadas com o idVendor e o idProduct, são usadas para definir uma versão específica do dispositivo.

__u8 bDeviceClass __u8 bDeviceSubClass __u8 bDeviceProtocol
Definem a classe, a subclasse e o protocolo do dispositivo, respectivamente. Esses números são atribuídos pelo fórum USB e são definidos na especificação USB. Esses valores especificam o comportamento de todo o dispositivo, incluindo todas as interfaces nesse dispositivo.
__u8 bInterfaceClass __u8 bInterfaceSubClass __u8 bInterfaceProtocol
Assim como os valores específicos dos dispositivos citados acima, esses definem a classe, a subclasse e o protocolo da interface individual, respectivamente. Esses números são atribuídos pelo fórum USB e são definidos na especificação USB.

kernel_ulong_t driver_info
Esse valor não é usado para ser correlacionado, mas ele carrega a informação que o driver pode usar para diferenciar os dispositivos entre si na função probe de chamada ao driver USB. Assim como com os dispositivos PCI, há muitas macros que são utilizadas para iniciallizar essa estrutura:

USB_DEVICE(vendor, product)
Cria uma struct usb_device que pode ser usada para correlacionar somente os valores da ID do produto e da marca específica.

USB_DEVICE_VER(vendor, product, lo, hi)
Cria uma struct usb_device que pode ser usada para correlacionar somente os valores da ID do produto e da marca específica dentro do escopo da versão.

USB_DEVICE_INFO(class, subclass, protocol)
Cria uma struct usb_device que pode ser usada para correlacionar uma classe específica de dispositivos USB.

USB_INTERFACE_INFO(class, subclass, protocol)
Cria uma struct usb_device que pode ser usada para correlacionar uma classe específica de interfaces USB. Assim, para um simples driver USB que controla um único dispositivo USB de uma marca única, a tabela da struct usb_device_id fica definida como:

/* tabela de dispositivos que funcionam com esse driver */ static struct usb_device_id skel_table [ ] = { { USB_DEVICE(USB_SKEL_VENDOR_ID, USB_SKEL_PRODUCT_ID) }, { } /* Entrada para finalização */ }; MODULE_DEVICE_TABLE (usb, skel_table);

Assim como com um driver PCI, a macro MODULE_DEVICE_TABLE é necessária para permitir que as ferramentas do espaço do usuário descubram quais dispositivos esse driver pode controlar. Mas para drivers USB, a string usb deve ser o primeiro valor na macro.

5. Instalação:

A instalação de drivers varia conforme a distribuição do Linux. O Linux usa módulos como device drivers. Todos os drivers estão instalados como módulos e localizados num diretório “/lib/modules/kernel_x.x.xx”. Um arquivo de configuração localizado em /etc/modules.conf é utilizado pelo kernel (e pelo usuário se você quiser substituí-lo) para carregar e descarregar módulos. A instalação e desinstalação de módulos pode ser feita por utilitários de módulo do kernel como insmod, rmmod e modprobe. Inserir e instalar um módulo não é tudo. O módulo tem que estar registrado como uma entrada de dispositivo no diretório /dev. O utilitário mknod reliza essa tarefa.

6. Testes:

Para testar os drives, deve-se entender de teste de softwares. Contudo, os drivers estão numa classe especial de software, porque eles podem mais livremente acessar recursos de baixo-nível do sistema do que qualquer outro aplicativo. Deve-se ter cuidado quando se criar um plano de testes e desenvolver testes de drivers, porque se um teste falhar, o sistema pode parar de responder.


** Estratégias de Testes

Estratégias para testar drivers podem ser geralmente categorizadas nas seguintes áreas:

• Use automação sempre que possível para detectar a maioria dos bugs.
• Teste cedo para detectar bugs de desenvolvimento durante essa fase.
• Use uma combinação de configurações gerais e de dispositivos.
• Use testes de equivalência, como agrupar drivers em classes e testar essa classe.
• Rode testes de estresse junto com testes de sistema.
• Incorpore aspectos que são específicos ao subsistema do driver, não ao do software aplicativo, em testes funcionais.
• Use recursos de testes já estabelecidos e teste o framework em si.
• Execute testes de integração e de cenários baseados em dados do cliente que utilizam a mesma classe de drivers.
  

** Metodologias de Testes

Os métodos a seguir são tipicamente usados para testar device drivers:
* Análise Estática

Um driver é um programa de software, e, como qualquer outro programa, o código-fonte deve ser testado por várias ferramentas diferentes de verificação e de análise para encontrar defeitos no código durante o desenvolvimento. A análise estática pode ser conduzida por ferramentas específicas que detectam certas classes de erros que não são detectadas por um compilador, como checar pelo nível correto de requisição de interrupção.

Testadores e Desenvolvedores de testes utilizam ferramentas que, a partir de um driver estabelecido em um estado instável, testa sistematicamente todos os code paths procurando por violações em regras específicas (pacotes de requição de I/O, níveis de requisição de interrupções, gerenciamento de energia, etc.). A análise em tempo real e as ferramentas de depuração são úteis quando o driver está executando uma operação.

* Testes Funcionais

Os testes funcionais se aplicam a qualquer software. Para drivers, esses testes incluem a avaliação se o comportamento do driver segue a documentação de projeto para esse driver. Rodam-se testes funcionais sob condições regulares em um dispositivo de teste isolado que contém o driver e está minimamente configurado ou customizado. Deve-se começar os testes funcionais durante a fase de desenvolvimento assim que driver for utilizável e estiver estável o suficiente. Pode-se utilizar esses testes repetidamente durante as fases subsequentes do teste e do desenvolvimento do driver.

* Testes de Configurações

Um driver pode se comportar se maneira distinta em diferentes configurações. Portanto, devem-se conduzir testes em vários tipos de ambientes e fazer dos testes de configurações uma parte da aprovação do teste regular. Testes de configuração incluem mudanças de configuração do sistema, mudanças no ambiente do sistema e mudanças nas configurações de dispositivos:

• Configuração de sistema: Teste o driver e diversas plataformas diferentes como x86, x64, dispositivos de multiprocessador e multicore com chipsets diferentes e builds checados.

• Ambientes de Sistema: Teste o driver com diferentes configurações de memória, de pouca a muita memória. Este teste pode gerar erros inesperados que não se detectariam de outra forma. Outro teste bom é aumentar a utilização da CPU de outro programa enquanto testa o driver. Este teste frequentemente gera bugs de timing.

• Configurações de dispositivos: Teste o driver com diferentes configurações de dispositivos, desde opções default ate opções raramente usadas. As opções menos usadas podem gerar erros inesperados, porque essa área geralente recebe pouca atenção durante o desenvolvimento. Se o dipositivo utiliza recursos de hardware, a matriz de testes deve incluir mudanças de teste nesses recursos. O teste de compatibilidade de harware também é importante. Esse teste consiste em se testar o driver e diversos dispositivos que utilizam diferentes tipos de conexão, como PCI e PCI-Extender (se o harware for baseado em PCI).

* Teste de Integração e de Cenário

Testes de cenário são ótimos para testar qualquer software, quer seja um software aplicativo, um banco de dados ou um driver. De dados históricos do cliente, pode-se geralmente inferir como o driver será utilizado pelo cliente, e tais cenários devem ser testados. Testar o comportamento funcional e usar automação são um ótimas maneiras de encontrar bugs. Contudo, a maioria do erros inesperados são encontrados por testes de integração e de cenário.

Testes de integração também simulam o ambiente do usuário em alguns casos. Por exemplo, a maioria dos clientes se logam como um usuário (em vez de com permissões de administrador) e instalam algum software. Testar o driver em um ambiente que simula esse cenário pode encontrar bugs que não seriam encontrados durante a verificação funcional típica.

* Testes de estresse

O objetivo de testes de estresse é colocar o driver em um ambiente com condições altas ou inesperadas de sobrecarga. Testar o estresse de drivers é muito importante. Ele é executado utilizando repetidamente as mesmas funções para encontrar falhas no sistema e vazamentos na memória. Testes de estresse são úteis quando rodados em combinação com a alta utilização da CPU por algum outro software.

* Testes Longos

Ocasionalmente, testadores e desenvolvedores confudem testes longos com testes de estresse. O objetivo dos testes longos é simular como um driver é utilizado numa base diária no ambiente do usuário final. Testes longos rodam aplicativos por períodos longos de tempo enquanto aplicam uma carga de driver típica. Esses testes encontram bugs difíceis de se encontrar que são relacionados com o timing e que não seriam descobertos pelos testes típicos.

* Testes de privilégios

Como os drivers possuem altos privilégios para acessar recursos de sistema, devem-se testá-los em formas diferentes das da maioria dos aplicativos. Esses testes adicionais incluem:

• Testes de memória
• Testes de cancelamento de I/O
• Testes de setup
• Testes de gerenciamento de energia
• Testes de penetração
• Testes de segurança

7. Referências:

http://www.linuxjournal.com/article/2476
http://www.lrr.in.tum.de/Par/arch/usb/usbdoc/node14.html
http://learningdevicedrivers.blogspot.com/
http://www.ddj.com/linux-open-source/

"Banheiro da Balada" : como controlar entrada de homens e mulheres?

Neste exercício, propomos uma solução para sincronizar o acesso ao banheiro de uma "balada". Como normalmente um único banheiro está disponível para ambos os sexos utilizarem, faz-se necessário desenvolver uma solução que sincronize o acesso de homens e mulheres, com algumas restrições. Caso o banheiro esteja vazio, qualquer pessoa pode entrar. As seguintes devem ser do mesmo sexo, até que o banheiro se esvazie novamente, dando oportunidade para alguém do sexo oposto entrar.

A seguir apresentamos o código-fonte da solução proposta seguido de testes que compravam o bom-funcionamento do programa.

// banheiro da balada

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include <errno.h>

#define N_MULHERES 5
#define N_HOMENS 5

// estados do banheiro
#define VAZIO 0
#define COM_MULHER 1
#define COM_HOMEM 2

pthread_mutex_t mutex_banheiro;
int homens_no_banheiro = 0;
int mulheres_no_banheiro = 0;
int estado = 0;

char *homem_nome[N_HOMENS] = {"Abraham", "Bill", "Carl", "David", "Stri"};
char *mulher_nome[N_MULHERES] = {"Alice", "Pri", "Julia", "Yoko", "Pam"};

int dummy[5]; 

void *homem(void *arg);
void *mulher(void *arg);

void mulher_quer_entrar(int id);
void mulher_quer_sair(int id);
void homem_quer_entrar(int id);
void homem_quer_sair(int id);

void error_exit(const char*);

int main() {
 
 srand(time(NULL));

 int res;
 pthread_t mulher_thread[N_MULHERES], homem_thread[N_HOMENS];
 void *thread_result;
 int index;

 //init dummy array
 for (index = 0; index < 5; index++){
  dummy[index]=index;
 }
 
 // iniciar mutex
 res = pthread_mutex_init(&mutex_banheiro, NULL);
 if(res != 0) error_exit("Inicializacao do mutex falhou");

 
 // criar threads
 for (index = 0; index < N_MULHERES; index ++) {
  res = pthread_create(&mulher_thread[index],NULL,mulher, (void *)&dummy[index]);
  if (res != 0) error_exit("Thread creation failed");
 }
 for (index = 0; index < N_HOMENS; index ++) {
  res = pthread_create(&homem_thread[index],NULL,homem, (void *)&dummy[index]);
  if (res != 0) error_exit("Criacao de thread falhou");
 }

 // join todos threads. assim, esperamos todos threads criados
 // terminarem sua execução

 for (index = 0; index < N_MULHERES; index++) {
  res = pthread_join(mulher_thread[index],&thread_result);
  if (res != 0) error_exit("Thread join falhou");
 }
 
 for (index = 0; index < N_HOMENS; index++) {
  res = pthread_join(homem_thread[index],&thread_result);
  if (res != 0) error_exit("Thread join falhou");
 }

 // kill semaphores, mutexes
 pthread_mutex_destroy(&mutex_banheiro);


 return 1;
}

void *mulher(void *arg){
 int id = *(int *) arg;

 sleep(rand() % 4); // antes de tentar entrar pela 1a vez

 mulher_quer_entrar(id);
 sleep(rand()% 4); // dentro do banheiro
 mulher_quer_sair(id);
 
 pthread_exit("exiting thread.\n"); 
  
}

void *homem(void *arg){
 int id = *(int *) arg;
 
 sleep(rand() % 4); // antes de tentar entrar pela 1a vez
 
 homem_quer_entrar(id);
 sleep(rand()% 4); // dentro do banheiro
 homem_quer_sair(id);
 
 pthread_exit("exiting thread.\n"); 
}

void mulher_quer_entrar(int id) {
 
 printf("%s quer entrar no banheiro.\n.", mulher_nome[id]);
 while (1) {
  pthread_mutex_lock(&mutex_banheiro);
  if (estado != COM_HOMEM) {
   estado = COM_MULHER;
   mulheres_no_banheiro++;
   printf("%s entra no banheiro, agora com %d mulheres.\n",
       mulher_nome[id], mulheres_no_banheiro);
   pthread_mutex_unlock(&mutex_banheiro);
   break;
  }
  pthread_mutex_unlock(&mutex_banheiro);
 }
}

void mulher_quer_sair(int id) {

 printf("%s quer entrar no banheiro\n.", mulher_nome[id]);
 pthread_mutex_lock(&mutex_banheiro);
 mulheres_no_banheiro--;
 if (mulheres_no_banheiro == 0){
  estado = VAZIO;
  printf("%s sai do banheiro, agora vazio.\n",
      mulher_nome[id]);
 }else{
  printf("%s sai do banheiro, agora com %d mulheres.\n",
      mulher_nome[id], mulheres_no_banheiro);
 }
 pthread_mutex_unlock(&mutex_banheiro);
 
}

void homem_quer_entrar(int id) {
 
 printf("%s quer entrar no banheiro\n.", homem_nome[id]);
 while (1) {
  pthread_mutex_lock(&mutex_banheiro);
  if (estado != COM_MULHER) {
   estado = COM_HOMEM;
   homens_no_banheiro++;
   printf("%s entra no banheiro, agora com %d homens.\n",
       homem_nome[id], homens_no_banheiro);
   pthread_mutex_unlock(&mutex_banheiro);
   break;
  }
  pthread_mutex_unlock(&mutex_banheiro);
 }
}

void homem_quer_sair(int id) {
 printf("%s quer sair do banheiro\n.", homem_nome[id]);
 
 pthread_mutex_lock(&mutex_banheiro);
 homens_no_banheiro--;
 if (homens_no_banheiro == 0){
  estado = VAZIO;
  printf("%s sai do banheiro, agora vazio.\n",
      homem_nome[id]);
 }else{
  printf("%s sai do banheiro, agora com %d homens.\n",
      homem_nome[id], homens_no_banheiro);
 }
 pthread_mutex_unlock(&mutex_banheiro);
 
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

O teste a seguir descreve uma possível sequência de utilização do banheiro. Observe que os resultados estão de acordo com o esperado.

Bill quer entrar no banheiro
.Yoko quer entrar no banheiro.
.Pri quer entrar no banheiro.
.Bill entra no banheiro, agora com 1 homens.
Pam quer entrar no banheiro.
.Julia quer entrar no banheiro.
.Alice quer entrar no banheiro.
.Carl quer entrar no banheiro
.Stri quer entrar no banheiro
.Carl entra no banheiro, agora com 2 homens.
Stri entra no banheiro, agora com 3 homens.
Abraham quer entrar no banheiro
.Abraham entra no banheiro, agora com 4 homens.
Abraham quer sair do banheiro
.Abraham sai do banheiro, agora com 3 homens.
Bill quer sair do banheiro
.Bill sai do banheiro, agora com 2 homens.
Carl quer sair do banheiro
.Carl sai do banheiro, agora com 1 homens.
David quer entrar no banheiro
.Stri quer sair do banheiro
.David entra no banheiro, agora com 2 homens.
Stri sai do banheiro, agora com 1 homens.
David quer sair do banheiro
.David sai do banheiro, agora vazio.
Pam entra no banheiro, agora com 1 mulheres.
Yoko entra no banheiro, agora com 2 mulheres.
Pri entra no banheiro, agora com 3 mulheres.
Alice entra no banheiro, agora com 4 mulheres.
Julia entra no banheiro, agora com 5 mulheres.
Julia quer entrar no banheiro
.Julia sai do banheiro, agora com 4 mulheres.
Pam quer entrar no banheiro
.Pam sai do banheiro, agora com 3 mulheres.
Yoko quer entrar no banheiro
.Yoko sai do banheiro, agora com 2 mulheres.
Pri quer entrar no banheiro
.Pri sai do banheiro, agora com 1 mulheres.
Alice quer entrar no banheiro
.Alice sai do banheiro, agora vazio.

Comunicação entre processos: "Produtores e Consumidores" utilizando pipes e processos

Nos posts anteriores utilizamos threads para solucionar alguns clássicos problemas IPC. Neste post utilizaremos pipes e forks para solucionar o problema dos "Produtores e Consumidores", demonstrando como pode ser feita a comunicação entre processos.

Produtores colocam dados em um buffer, enquanto consumidores retiram dados do buffer. O problema surge quando produtores tentarem colocar dados em um buffer já cheio ou, analogamente, consumidores tentarem retirar dados de um buffer vazio.

A solução aqui apresentada utiliza pipes, permitindo que processos produtores se comuniquem com consumidores. Mais especificamente, um único pipe é criado e todos os processos o utilizam para retirar ou inserir dados. Considerando que as operações são thread-safe, a solução garante o bom comportamento do programa, como demonstrado pelos testes.

Os processos gerados a partir do processo pai executarão o código de Producer ou Consumer.
A fim de permitir a comunicação entre os mesmos, inicialmente criamos um pipe (executando na linha de comando -- $ mkfifo thePipe

A seguir, apresentamos o código-fonte dos dois arquivos.

// producer.c

#include <stdio.h>
#include <fcntl.h>
#include <string.h>

int main () {
  int fd, messageLen, i;
  char message [100]; /* Prepare message */
  sprintf (message, "Hello from producer PID %d parent is %d",
           getpid (), getppid());
  messageLen = strlen (message) + 1;
  do /* Keep trying to open the file until successful */
  {
      fd = open ("thePipe", O_WRONLY); /* Open named pipe for writing */
      if (fd == -1) sleep (1); /* Try again in 1 second */
  } while (fd == -1);
  for (i = 1; i <= 3; i++) /* Send three messages */     {         write (fd, message, messageLen); /* Write message down pipe */         sleep (3); /* Pause a while */     }     close (fd); /* Close pipe descriptor */     return 1; }  

// consumer.c

#include <stdio.h>
#include <fcntl.h>
#include <sys/types.h>

int readLine (int fd,char *str);
int main () {
int fd;
char str[100];
fd = open ("thePipe", O_RDONLY); /* Open it for reading */
while (readLine (fd, str)) /* Display received messages */
 printf ("%s\n", str);
close (fd); /* Close pipe */
sleep(3);
return 1;
}

/* Read a single NULL-terminated line into str from fd */
/* Return 0 when the end-of-input is reached and 1 otherwise */
int readLine (int fd,char *str) {
int n;
do /* Read characters until NULL or end-of-input */
{
n = read (fd, str, 1); /* Read one character */
} while (n > 0 && *str++ != 0 );
return (n > 0); /* Return false if end-of-input */
}

Finalmente, apresentamos o programa que será executado e ordenará a geração dos processos-filho.

//producer_consumer.c

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>

void create_producer();
void create_consumer();

int main() {

int index;

create_producer();
create_producer();
create_consumer();

return 1;

}

void create_producer() {
printf("Produtor criado.\n");
int pid = fork();
if (pid == 0) {
execlp("./producer","producer",NULL);
}
}

void create_consumer() {
printf("Consumidor criado.\n");
int pid = fork();
if (pid == 0) {
execlp("./consumer","consumer",NULL);
}
}

Note que quando o processo filho completa sua execução mas ainda tem uma entrada em sua process table (para permitir que o pai leia seu status de saída) este passa a se denominar zombie.
Podemos simular tal situação se colocarmos o processo-pai para dormir por um longo período e o processo-filho apenas executando exit(0). Enquanto o pai dormir, o filho será um zombie. Note que isto é diferente de processo-órfão.

Finalmente, um simples teste.

bash-3.2$ ./consumer & ./producer &./producer &
[1] 2526
[2] 2527
[3] 2528
Hello from producer PID 2527
Hello from producer PID 2528
Hello from producer PID 2527
Hello from producer PID 2528
Hello from producer PID 2527
Hello from producer PID 2528

[1]   Exit 1                  ./consumer
[2]-  Exit 1                  ./producer
[3]+  Exit 1                  ./producer
bash-3.2$

Utilizando semáforos em sistemas Darwin

Nos últimos posts, apresentamos soluções para alguns clássicos problemas de comunicação entre processos e threads. Os programas foram implementados e executados no Mac OS X , sistema operacional baseado em UNIX e construído sobre uma camada Darwin.

Neste post, apresentamos algumas (sensíveis) restrições acerca do uso de semáforos em sistemas Darwin.

O padrão POSIX inclui especificações para semáforos nomeados e não-nomeados.
Para a nossa finalidade , semáforos não-nomeados (unnamed semaphores) seriam suficientes. Entretato, apenas o padrão nomeado (named semaphores) está disponível no Darwin. Neste caso, podemos criar e finalizar um semáforo da seguinte forma:

#include <semaphore.h>
sem_t * sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
int sem_close(sem_t *sem);
int sem_unlink(const char *name);

O sútil problema ocorre quando o processo do programa é killed durante execução, situação na qual os semáforos não são fechados e unlinked apropriadamente. Como o kernel do Darwin (aparentemente) não limpa estes semáforos imediatamente, uma solução é necessária para evitar que subsequentes execuções do programa utilizem o antigo semáforo (residual).
Isto pode ocorrer caso novas chamadas de sem_open() utilizem a mesma string 'name'.

A solução proposta é gerar uma (longa) string aleatória cada vez que se deseje um novo semáforo. Assim em posts anteriores, as declarações tomam a seguinte forma:

sem_t * sem_open(rand_str(const char *sem_name,int strlength),
      O_CREAT ,0, unsigned int sem_init_value);

Usar semáforos no Mac OS X passa então a não mais ser uma experiência frustrante!

Implementando problema dos "Leitores e Escritores" utilizando semáforos.

Olá leitores! Continuamos aqui a série de posts sobre problemas de comunicação entre threads e processos, desta vez abordando o problema dos "Leitores e Escritores".
Esse clássico problema de concorrência modela o acesso a um banco de dados. A situação proposta é a de um banco de dados que é acessado por leitores e escritores. A operação de leitura não requer uso exclusivo de tal banco, isto é, outros leitores também podem estar presentes. Já a operação de escrita requer exclusividade de acesso. A questão então é: como sincronizar leitores e escritores?

A seguir, apresentamos uma solução para tal problema utilizando semáforos.
Finalmente, os testes apresentados comprovam o bom funcionamento de nossa implementação.

CÓDIGO-FONTE

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
#include <errno.h>

#define NREADERS 5
#define NWRITERS 5
#define MAX_DB_TIME 2
#define MAX_TIME_BEFORE_START 4

sem_t *db;
pthread_mutex_t mutex;
int rc = 0;
char *readers[5] = {"Abraham", "Bill", "Carl", "David", "Ellen"};
char *writers[5] = {"Stri", "ManoPri", "Chipuruto", "Cone", "Flavio"};

int dummy[NREADERS];

void *reader(void *arg);
void *writer(void *arg);
void read_data_base();
void use_data_read();
void think_up_data();
void write_data_base();

void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);


int main() {
 
 srand(time(NULL));

 int res;
 pthread_t reader_thread[NREADERS], writer_thread[NWRITERS];
 void *thread_result;
 char *dbsem_name; // utilizaremos o padrao POSIX named sem
 int index;

 //init dummy array
 for (index = 0; index < NREADERS; index++){
  dummy[index]=index;
 }
 
 // iniciar mutex
 res = pthread_mutex_init(&mutex, NULL);
 if(res != 0) error_exit("Inicializacao do mutex falhou");

 // iniciar semaforos
 // atencao: em sistemas darwin, utilizamos sem_open ao inves de sem_init
 // no Mac OS X, apenas *semaforos nomeados* estao implementados.

 db = sem_open(rand_str(dbsem_name,8),O_CREAT,0,1);
 if (db == SEM_FAILED) printf("criacao de semaforo falhou.\n");
 
 // criar threads
 for (index = 0; index < NWRITERS; index ++) {
  res = pthread_create(&writer_thread[index],NULL,writer, (void *)&dummy[index]);
  if (res != 0) error_exit("Thread creation failed");
 }
 for (index = 0; index < NREADERS; index ++) {
  res = pthread_create(&reader_thread[index],NULL,reader, (void *)&dummy[index]);
  if (res != 0) error_exit("Criacao de thread falhou");
 }

 // join thread. é suficiente único join p/ este programa
 // pois todas as threads tem loop infinito.

 res = pthread_join(writer_thread[0],&thread_result);
 if (res != 0) error_exit("Thread join falhou");

 // kill semaphores, mutexes
 pthread_mutex_destroy(&mutex);
 // closing and unlink semaphores
 sem_close_n_unlink(db, dbsem_name);

 return 1;
}

void *reader(void *arg){
 int id = *(int *) arg;

 while (1) {
  pthread_mutex_lock(&mutex);
  printf("=%s will try to read.\n", readers[id]);
  rc = rc + 1;
  if (rc == 1) sem_wait(db);  // se 1o leitor...
  pthread_mutex_unlock(&mutex);
  printf("==%s is reading, totaling  %d readers.\n",
      readers[id], rc);
  read_data_base();
  pthread_mutex_lock(&mutex);
  rc = rc - 1;
  if (rc == 0) {
   sem_post(db); //se ultimo leitor...
   printf("=%s is done reading and realease db.\n", readers[id]);
  }
  else {
   printf("%s is done reading. %d readers are left\n", 
       readers[id], rc);
  }
  pthread_mutex_unlock(&mutex);
  use_data_read();
 }

 pthread_exit("exiting thread.\n"); 
}

void *writer(void *arg){
 int id = *(int *) arg;
 
 while (1) {
  think_up_data();
  printf(".%s will try  to write into db.\n", writers[id]);  
  sem_wait(db);
  printf("..%s is writing into db.\n", writers[id]);  
  write_data_base();
  sem_post(db);
  printf(".%s is done writing and realesed db.\n", writers[id]);  
 }
 
 pthread_exit("exiting thread.\n"); 
}

void read_data_base() {
 sleep(rand() % MAX_DB_TIME);
}

void use_data_read() {
 sleep(rand() % MAX_DB_TIME);
}

void think_up_data() {
 sleep(rand() % MAX_DB_TIME); 
}

void write_data_base() {
 sleep(rand() % MAX_DB_TIME);
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}

TESTES

  

.Stri will try  to write into db.
..Stri is writing into db.
.Stri is done writing and realesed db.
.Stri will try  to write into db.
..Stri is writing into db.
.Chipuruto will try  to write into db.
.Cone will try  to write into db.
=Abraham will try to read.
.Stri is done writing and realesed db.
..Chipuruto is writing into db.
.Stri will try  to write into db.
.ManoPri will try  to write into db.
.Flavio will try  to write into db.
.Chipuruto is done writing and realesed db.
..Cone is writing into db.
.Chipuruto will try  to write into db.
.Cone is done writing and realesed db.
==Abraham is reading, totaling  1 readers.
=Bill will try to read.
.Cone will try  to write into db.
==Bill is reading, totaling  2 readers.
=Carl will try to read.
==Carl is reading, totaling  3 readers.
=David will try to read.
==David is reading, totaling  4 readers.
=Ellen will try to read.
==Ellen is reading, totaling  5 readers.
Abraham is done reading. 4 readers are left
David is done reading. 3 readers are left
=Abraham will try to read.
==Abraham is reading, totaling  4 readers.
Bill is done reading. 3 readers are left
Ellen is done reading. 2 readers are left
Carl is done reading. 1 readers are left
=Carl will try to read.
==Carl is reading, totaling  2 readers.
=David will try to read.
==David is reading, totaling  3 readers.
Abraham is done reading. 2 readers are left
=Bill will try to read.
==Bill is reading, totaling  3 readers.
=Ellen will try to read.
==Ellen is reading, totaling  4 readers.
Carl is done reading. 3 readers are left
Ellen is done reading. 2 readers are left
=Ellen will try to read.
==Ellen is reading, totaling  3 readers.
David is done reading. 2 readers are left
=David will try to read.
==David is reading, totaling  3 readers.
=Abraham will try to read.
==Abraham is reading, totaling  4 readers.
Abraham is done reading. 3 readers are left
Bill is done reading. 2 readers are left
=Carl will try to read.
==Carl is reading, totaling  3 readers.
Carl is done reading. 2 readers are left
Ellen is done reading. 1 readers are left
=David is done reading and realease db.
=David will try to read.
..Stri is writing into db.
.Stri is done writing and realesed db.
..ManoPri is writing into db.
.Stri will try  to write into db.
.ManoPri is done writing and realesed db.
.ManoPri will try  to write into db.
..Flavio is writing into db.
.Flavio is done writing and realesed db.
..Chipuruto is writing into db.
.Flavio will try  to write into db.

Implementando as operações send e receive utilizando semáforos.

Desta vez, implementaremos as importantes operações de send e receive utilizando semáforos! Esta implementação simples demonstra como dois threads um receiver e outro sender podem simular o ambiente para utilizar as funções send e receive.

CÓDIGO-FONTE

  
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>

#define BUFFER_SIZE 10
#define FANCIEST_MSG 15
#define BUSY_WAIT 3
#define FILE_MODE       (S_IRWXU | S_IRWXG | S_IRWXO )


sem_t *empty_msgs, *full_msgs;
pthread_mutex_t buffer_mutex;
int buffer[BUFFER_SIZE];
int buffer_head = 0;
int dummy = 0;

void *sender (void *arg);
void *receiver (void *arg);
void send (int msg);
void receive();
void print_buffer();
void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);


int main() {
 srand(time(NULL));
 int res;
 pthread_t my_sender, my_receiver;
 void *thread_result;
 
 // start w/ N EMPTY MESSAGES << sem empty messages.
 // produces has an item to give to the consumer?
  // sem_wait(&sem_empty_msg)
  // sem_post(&sem_full_msg)
 res = pthread_mutex_init(&buffer_mutex,NULL);
 if(res != 0){
  perror("Inicializacao de mutex falhou");
  exit(EXIT_FAILURE);
 }

 char *empty_sem_name, *full_sem_name;
 
 empty_msgs = sem_open(rand_str(empty_sem_name,8),O_CREAT,0,BUFFER_SIZE);//, FILE_MODE,BUFFER_SIZE);
 if (empty_msgs == SEM_FAILED) {printf ("sem_failed.\n");}
 full_msgs = sem_open(rand_str(full_sem_name,8),O_CREAT,0,0);
 // if (full_msgs == SEM_FAILED) {printf ("sem_failed.\n");}

 res  = pthread_create(&my_sender,NULL,sender,(void *)&dummy);
 if (res != 0){
  perror("Thread creation failed");
  exit(EXIT_FAILURE);
 }
 res =  pthread_create(&my_receiver,NULL,receiver,(void *)&dummy);
 if (res != 0){
  perror("Thread creation failed");
  exit(EXIT_FAILURE);
 }

 res = pthread_join(my_sender, &thread_result);
 if (res != 0){
  perror("Thread join failed");
  exit(EXIT_FAILURE);
 }

 //destroy mutex
 pthread_mutex_destroy(&buffer_mutex);
 // closing and unlink semaphores
 sem_close_n_unlink(empty_msgs, empty_sem_name);
 sem_close_n_unlink(full_msgs, full_sem_name);
 return 1;
}


void *sender (void *arg) {
 int id = *(int *) arg; // irrelevante pois supomos apenas um sender
 int msg;
 while(1){
  msg = rand () % FANCIEST_MSG;
  sleep(rand() % BUSY_WAIT);
  printf("sender has a msg: %d\n", msg);
  sem_wait(empty_msgs); //check whether we can send
  send(msg);
  sem_post(full_msgs); //receive remembers to receive
 }
}

void *receiver (void *arg) {
 int id = *(int *) arg; 
 while(1){
  sem_wait(full_msgs);
  sleep(rand() % BUSY_WAIT);
  receive();
  sem_post(empty_msgs);
 }
}

void send(int msg) {
 pthread_mutex_lock(&buffer_mutex);
 printf("sender inserted msg %d in buffer\n", msg);
 buffer[buffer_head] = msg;
 buffer_head++;
 print_buffer();
 pthread_mutex_unlock(&buffer_mutex);
}

void receive() {
 int msg;
 pthread_mutex_lock(&buffer_mutex);
 printf("receiver removing msg %d in buffer\n", buffer[buffer_head - 1]);
 msg = buffer[buffer_head - 1];
 buffer_head--;
 print_buffer();
 pthread_mutex_unlock(&buffer_mutex);
}
 
void print_buffer(){
 int index;
 printf("buffer is... ");
 for (index = 0; index < buffer_head; index++){
  printf(". %d .", buffer[index]);
 }
 printf("\n");
}


void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}
 

TESTES

sender has a msg: 5
sender inserted msg 5 in buffer
buffer is... . 5 .
sender has a msg: 2
sender inserted msg 2 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 1
sender inserted msg 1 in buffer
buffer is... . 5 .. 2 .. 1 .
receiver removing msg 1 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 13
sender inserted msg 13 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 3
sender inserted msg 3 in buffer
buffer is... . 5 .. 2 .. 13 .. 3 .
receiver removing msg 3 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 9
sender inserted msg 9 in buffer
buffer is... . 5 .. 2 .. 13 .. 9 .
receiver removing msg 9 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 10
sender inserted msg 10 in buffer
buffer is... . 5 .. 2 .. 13 .. 10 .
sender has a msg: 0
receiver removing msg 10 in buffer
buffer is... . 5 .. 2 .. 13 .
sender inserted msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .. 0 .
sender has a msg: 4
receiver removing msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .
sender inserted msg 4 in buffer
buffer is... . 5 .. 2 .. 13 .. 4 .
receiver removing msg 4 in buffer
buffer is... . 5 .. 2 .. 13 .
sender has a msg: 0
sender inserted msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .. 0 .
receiver removing msg 0 in buffer
buffer is... . 5 .. 2 .. 13 .
receiver removing msg 13 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 11
sender inserted msg 11 in buffer
buffer is... . 5 .. 2 .. 11 .
sender has a msg: 9
receiver removing msg 11 in buffer
buffer is... . 5 .. 2 .
sender inserted msg 9 in buffer
buffer is... . 5 .. 2 .. 9 .
receiver removing msg 9 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 14
sender inserted msg 14 in buffer
buffer is... . 5 .. 2 .. 14 .
receiver removing msg 14 in buffer
buffer is... . 5 .. 2 .
sender has a msg: 7
sender inserted msg 7 in buffer
buffer is... . 5 .. 2 .. 7 .
sender has a msg: 13
sender inserted msg 13 in buffer
buffer is... . 5 .. 2 .. 7 .. 13 .
sender has a msg: 2
sender inserted msg 2 in buffer
buffer is... . 5 .. 2 .. 7 .. 13 .. 2 .

"O barbeiro dorminhoco": Uma solução utilizando threads e semáforos

Olá pessoal!
Continuando a série de posts sobre problemas IPC (Inter-Process Communication), apresentamos agora o problema do "Barbeiro Dorminhoco", acompanhado por uma uma solução que utiliza threads e semáforos. Finalmente, testes são apresentados, comprovando o bom funcionamento de nossa solução.

A situação é bem simples: imagine uma salão de cabelereiros onde, após demissões em massa, apenas o barbeiro-chefe trabalha, atendendo aos clientes que chegam.
Sempre que o expediente está tranquilo demais..... o barbeiro adormece! Este só volta a acordar quando um novo cliente chega, ansioso por um corte.

CÓDIGO-FONTE

 
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
#include <errno.h>

#define N 20
#define CHAIRS 5
#define MAX_CUT_TIME 5
#define MAX_TIME_BEFORE_START 8

sem_t *customers, *barbers;
pthread_mutex_t mutex;
int waiting = 0;
int customer_id[N];
int barber_id;
char* customer_name[20] = 
 {"A","B","C","D","E", "F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T"};

void *barber(void *arg);
void *customer(void *arg);
void cut_hair();
void get_haircut(int i);
void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);

int main() {
 
 srand(time(NULL));

 int res;
 pthread_t barber_thread, cust_thread[N];
 void *thread_result; 
 int index;

 for (index = 0; index < N; index++) {
  customer_id[index] = index;
 }
 barber_id = 0;
 
 //iniciar mutex
 res = pthread_mutex_init(&mutex, NULL);
 if (res != 0) error_exit("Inicializacao do mutex falhou");

 // iniciar semaforos
 // atencao: em sistemas darwin, utilizamos sem_open ao inves de sem_init
 // pois no Mac OS X, apenas *semaforos nomeados* estao implementados.

 char *barbersem , *customersem;
 barbers = sem_open(rand_str(barbersem,8),O_CREAT,0,0);
 customers = sem_open(rand_str(customersem,8),O_CREAT,0,0);

 // criar threads
 res = pthread_create(&barber_thread, NULL, barber, (void *)&barber_id);
 if (res != 0) error_exit("Criacao de thread falhou");

 for (index = 0; index < N; index++) {
  res = pthread_create(&cust_thread[index],NULL,customer,(void *)&customer_id[index]);
  if (res != 0) error_exit("Criacao de thread falhou");
 }

 res = pthread_join(barber_thread,&thread_result);
 if (res != 0) error_exit("Falhou quando tentou pthread_join");

 //destroy mutex
 pthread_mutex_destroy(&mutex);
 // closing and unlink semaphores
 sem_close_n_unlink(barbers, barbersem);
 sem_close_n_unlink(customers, customersem);

 return 1;
}

void *barber(void *arg){
 int id = *(int *) arg;
 while (1) {
  printf("Barbeiro desocupado.\n");
  sem_wait(customers);
  printf("== Fila de espera tem  %d clientes.\n", waiting);
  pthread_mutex_lock(&mutex);
  waiting = waiting - 1;
  sem_post(barbers);
  printf("Barbeiro pronto para cortar algum cabelo.\n");
  pthread_mutex_unlock(&mutex);
  cut_hair();
 }
}

void *customer(void *arg) {
 
 int id = *(int *) arg;
 sleep(rand() % MAX_TIME_BEFORE_START); //simular o comportamento de chegada dos clientes
 
 pthread_mutex_lock(&mutex);
 if (waiting < CHAIRS) {
  waiting = waiting + 1;
  sem_post(customers);
  printf("%s esta na fila de espera. Tamanho da fila eh %d.\n", customer_name[id], waiting);
  pthread_mutex_unlock(&mutex);
  sem_wait(barbers);
  get_haircut(id);
 }
 else {
  printf("  Cliente %s passando direto. Fila cheia!\n", customer_name[id]);
  pthread_mutex_unlock(&mutex);
 }
 pthread_exit("customer exits.\n");
}

void cut_hair() {
 sleep(3);
}

void get_haircut(int i) {
 printf("%s esta cortando o cabelo\n", customer_name[i]);
 sleep(3);
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}
 

TESTES

Abaixo, apresentamos a saída obtida durante execução do problema. Observe
que, de fato, ela é consistente com as restrições impostas pelo enunciado do
problema.

Barbeiro desocupado.
F esta na fila de espera. Tamanho da fila eh 1.
H esta na fila de espera. Tamanho da fila eh 2.
Q esta na fila de espera. Tamanho da fila eh 3.
== Fila de espera tem 3 clientes.
Barbeiro pronto para cortar algum cabelo.
F esta cortando o cabelo
D esta na fila de espera. Tamanho da fila eh 3.
N esta na fila de espera. Tamanho da fila eh 4.
I esta na fila de espera. Tamanho da fila eh 5.
Cliente J passando direto. Fila cheia!
Cliente C passando direto. Fila cheia!
Cliente K passando direto. Fila cheia!
Cliente P passando direto. Fila cheia!
Barbeiro desocupado.
== Fila de espera tem 5 clientes.
Barbeiro pronto para cortar algum cabelo.
H esta cortando o cabelo
A esta na fila de espera. Tamanho da fila eh 5.
Cliente E passando direto. Fila cheia!
Cliente S passando direto. Fila cheia!
Cliente T passando direto. Fila cheia!
Cliente L passando direto. Fila cheia!
Cliente O passando direto. Fila cheia!
Cliente R passando direto. Fila cheia!
Barbeiro desocupado.
== Fila de espera tem 5 clientes.
Barbeiro pronto para cortar algum cabelo.
Q esta cortando o cabelo

"Jantar dos Filósofos" - Uma Solução utilizando Threads e Semáforos

Proposto em 1965 por Esdger Dijkstra, o clássico "Jantar dos Filósofos" ilustra o problema de concorrência em computação, apresentando-se como uma explicação teórica do deadlock.

A situação proposta é a de um mesa de jantar ao redor da qual estão sentados 5 (cinco) filósofos, cada um capaz de realizar apenas duas atividades, mutuamente exclusivas: pensar ou comer.
Na frente de cada filósofo existe um delicioso prato de spaghetti pronto para ser devorado. Um garfo é posicionado entre cada par de filósofos e, considerando a dificuldade para comer tal saboroso macarrão, cada filósofo precisa de dois garfos para fazer sua refeição. Além disso, podem apenas usar o garfo imediatamente à sua direita ou esquerda.

A questão proposta por Dijkstra é então: como programar os filósofos de modo evitar a situação de deadlock, onde todos esperam eternamente para o outro garfo tornar-se disponível?

A seguir, apresentamos o código que implementa uma solução para tal problema, utilizando threads e semáforos. Finalmente, testes são apresentados para comprovar o bom funcionamento da solução.


CÓDIGO-FONTE

 
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>

#define MAX_THINK_TIME 5   
#define MAX_EAT_TIME 5    
#define N  5    
#define LEFT  (i+N-1)%N   
#define RIGHT  (i+1)%N  
#define THINKING 0   
#define HUNGRY  1   
#define EATING  2   

int state[N];       // vetor de estados. um estado para cada filósofo
pthread_mutex_t mutex;     // mutex para região crítica
sem_t *sem[N];       // vetor de semáforos. um sem para cada filósofo.
char *friends[5] = {"Abraham", "Bill", "Carl", "David", "Ellen"};  // pretty-printing para N=5

int dummy[N];

void *philosopher (void *arg);  
void take_forks(int i);    
void put_forks(int i);
void test(int i);
void think(int i);
void eat(int i);
void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);


int main() {

 srand(time(NULL));   // fornecendo seed para uma nova série números pseudo-random
 int res;
 pthread_t philo_thread[N];  // vetor contém uma thread para cada filósofo
 void *thread_result;  // thread resultado para ser usada em pthread_join
 int index;
 
 //init dummy array
 for (index = 0; index < N; index++){
  dummy[index]=index;
 }
 
 // iniciar mutex
 res = pthread_mutex_init(&mutex, NULL);
 if(res != 0){
  perror("Inicializacao de mutex falhou");
  exit(EXIT_FAILURE);
 }

 // iniciar semaforos
 // atencao: em sistemas darwin, utilizamos sem_open ao inves de sem_init
 // no Mac OS X, apenas *semaforos nomeados* estao implementados.
 char *philosem_names[N];
 for (index = 0; index < N; index ++){
  sem[index] = sem_open(rand_str(philosem_names[N],8),O_CREAT,0,0);
 }

 for (index = 0; index < N; index++){
  state[index]=THINKING; //estado inicial dos filosofos
 }
 
 //criar filosofos
 for (index = 0; index < N; index++){
  res = pthread_create(&philo_thread[index], NULL, philosopher, (void *)&dummy[index] );
  if (res != 0){
   perror("Thread creation failed");
   exit(EXIT_FAILURE);
  }
 }

 res = pthread_join(philo_thread[0], &thread_result);
 if (res != 0){
  perror("Thread join failed");
  exit(EXIT_FAILURE);
 }
 printf("Thread joined, it returned this %s\n", (char*)thread_result);

 pthread_mutex_destroy(&mutex);
 // closing and unlink semaphores
 for (index = 0; index < N; index++) {
  sem_close_n_unlink(sem[index], philosem_names[index]);
 }
 return 1;
}

//what does a philopher do?
void *philosopher(void *arg){
 int id = *(int *) arg;
 while(1){
  think(id);
  take_forks(id);
  eat(id);
  put_forks(id);
 }
}

void take_forks(int i) {
 pthread_mutex_lock(&mutex);
 printf("Filosófo %s está com fome\n", friends[i]);
 state[i] = HUNGRY;
 test(i);
 pthread_mutex_unlock(&mutex);
 sem_wait(sem[i]);
}

void put_forks(int i) {
 pthread_mutex_lock(&mutex);
 printf("Filosófo %s está pensando\n", friends[i]);
 state[i] = THINKING;
 test(LEFT);
 test(RIGHT);
 pthread_mutex_unlock(&mutex);
}

void test(int i){
 if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
  printf("Filosófo %s está comendo.  %s está %d. %s está %d.\n",
      friends[i], friends[LEFT],state[LEFT], friends[RIGHT], state[RIGHT]);
  
  state[i] = EATING;
  sem_post(sem[i]);
 }else{
  printf("Filosófo %s está %d.  %s está %d. %s está %d.\n",
      friends[i], state[i], friends[LEFT], state[LEFT], friends[RIGHT], state[RIGHT]);
 }
}

void think(int i){
 sleep(rand() % MAX_THINK_TIME);
}

void eat(int i){
 sleep(rand() % MAX_EAT_TIME);
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}

TESTES
A seguir apresentamos a saída do programa em execução. Esta foi desenvolvida de modo a tornar evidente o bom funcionamento do programa.
Considere o mapeamento: THINKING --> 0, HUNGRY --> 1, EATING --> 2.
A fim de facilitar a compreensão da saída, considere:
"Filósofo Carl está comendo. Bill está 0. David está 0." significa que enquanto o filósofo Carl está comendo, os dois ao seu lado estão pensando, significando que as restrições do problema estão satisfeitas.

Filosófo Carl está com fome
Filosófo Carl está comendo.  Bill está 0. David está 0.
Filosófo Abraham está com fome
Filosófo Abraham está comendo.  Ellen está 0. Bill está 0.
Filosófo Bill está com fome
Filosófo Bill está 1.  Abraham está 2. Carl está 2.
Filosófo Abraham está pensando
Filosófo Ellen está 0.  David está 0. Abraham está 0.
Filosófo Bill está 1.  Abraham está 0. Carl está 2.
Filosófo Carl está pensando
Filosófo Bill está comendo.  Abraham está 0. Carl está 0.
Filosófo David está 0.  Carl está 0. Ellen está 0.
Filosófo David está com fome
Filosófo David está comendo.  Carl está 0. Ellen está 0.
Filosófo Ellen está com fome
Filosófo Ellen está 1.  David está 2. Abraham está 0.
Filosófo Abraham está com fome
Filosófo Abraham está 1.  Ellen está 1. Bill está 2.
Filosófo Bill está pensando
Filosófo Abraham está comendo.  Ellen está 1. Bill está 0.
Filosófo Carl está 0.  Bill está 0. David está 2.
Filosófo David está pensando
Filosófo Carl está 0.  Bill está 0. David está 0.
Filosófo Ellen está 1.  David está 0. Abraham está 2.
Filosófo Ellen está pensando
Filosófo David está 0.  Carl está 0. Ellen está 0.
Filosófo Abraham está 2.  Ellen está 0. Bill está 0.
Filosófo Ellen está com fome
Filosófo Ellen está 1.  David está 0. Abraham está 2.
Filosófo David está com fome
Filosófo David está comendo.  Carl está 0. Ellen está 1.
Filosófo Carl está com fome
Filosófo Carl está 1.  Bill está 0. David está 2.
Filosófo Abraham está pensando
Filosófo Ellen está 1.  David está 2. Abraham está 0.
Filosófo Bill está 0.  Abraham está 0. Carl está 1.
Filosófo Ellen está pensando
Filosófo David está 2.  Carl está 1. Ellen está 0.
Filosófo Abraham está 0.  Ellen está 0. Bill está 0.
Filosófo Abraham está com fome
Filosófo Abraham está comendo.  Ellen está 0. Bill está 0.
Filosófo David está pensando
Filosófo Carl está comendo.  Bill está 0. David está 0.
Filosófo Ellen está 0.  David está 0. Abraham está 2.
Filosófo David está com fome
Filosófo David está 1.  Carl está 2. Ellen está 0.
Filosófo David está pensando
Filosófo Carl está 2.  Bill está 0. David está 0.
Filosófo Ellen está 0.  David está 0. Abraham está 2.
Filosófo Bill está com fome
Filosófo Bill está 1.  Abraham está 2. Carl está 2.