CES 33 - Sistemas Operacionais

A matéria "CES33 - Sistemas Operacionais" é ministrada no curso de Engenharia da Computação do Instituto Tecnológico de Aeronáutica - ITA.

Este ano, 2009, esta cadeira esta sendo ministrada pelo professor Edgar Toshiro Yano.

A pedido do professor, cada aluno deve postar em um blog os resultados das experiências de laboratório realizadas durante o curso.

Este espaço corresponde às experiências realizadas por mim.

Mãos à obra!

Projetando um device-driver USB para o Linux

Neste post iremos discutir os fundamentos necessários para se realizar o projeto de um device-driver USB para o Linux.

Este post foi elaborado em dupla, juntamente com o aluno José Gerardo Arruda Júnior.

• A importância dos device drivers

Os device drivers são componentes fundamentais para o funcionamento de qualquer sistema operacional (SO). A principal função de um device driver é traduzir as chamadas realizadas pelo SO a um determinado dispositivo através da implementação de uma interface definida pelo próprio SO, que estabelece como é que o controle de um dispositivo deve ser realizado. Dessa forma, os device-drivers podem ser entendidos como os responsáveis pelo controle dos periféricos conectados a um computador, tais como HDs, mouses, teclados, monitores, placas de vídeo e rede, dispositivos USB, etc... Exemplos de operações implementadas pelos drivers são: Open, Release, Write, Read, Init e Cleanup.

Eles atuam como uma camada de abstração entre os dispositivos de hardware e o SO, ou aplicativos, e simplificam a programação, tornando possível a escrita de softwares independentes do tipo de hardware que está sendo utilizado (para citar um rápido exemplo, ao escrever um programa que necessita enviar um comando de impressão para uma impressora, é desejável que o fato da impressora ser da HP ou da Lexmark não faça diferença).

Além de prover uma camada de abstração e de mapear as chamadas do SO ao hardware, os device drivers também são importantes por otimizarem o desempenho de operações de IO, incluir tratamento de erro a nível de hardware e software e permitir acesso paralelo, por diversos dispositivos, ao hardware.

• Arquitetura de device drivers do Linux

Figura 1. Diagrama esquemático da arquitetura de device drivers do Linux

No Linux, os device drivers se comportam como "caixas pretas" responsáveis por fazer com que determinado componente de hardware responda às chamadas de uma API bem definida, que é a interface de comunicação entre os drivers e o SO, já vista anteriormente.

A arquitetura de device drivers no Linux apresenta modularidade, ou seja, os drivers são construídos separadamente do restante do Kernel e, quando necessário, são "plugados" em tempo de execução. Essa modularidade facilita o desenvolvimento de drivers para Linux.

Assim, podemos dizer que no Linux os device drivers são representados como módulos, que são programas que estendem a funcionalidade do Kernel e que realizam sua comunicação através de chamadas de funções/métodos das interfaces públicas disponibilizadas por eles.

• O que é desejável de um device-driver?

Alguns dos requisitos essenciais de um device driver vistos até agora foram: implementação de uma interface disponibilizada pelo SO para mapear as requisições do SO ao hardware, fornecimento de uma camada de abstração ao programador, otimização de desempenho de operações de IO, tratamento de erros a nível de software e hardware, e gerenciamento de acesso paralelo, por diversos dispositivos, ao hardware. Contudo, falta explicitar uma característica muito importante desejável aos device drivers, que é a flexibilidade.

A palavra flexibilidade enfatiza o papel do device driver de prover um mecanismo e não uma política. A idéia de mecanismo vem de "Quais funcionalidades devem ser fornecidas?" enquanto a de política vem de "Como essas funcionalidades podem ser utilizadas?" .

Dessa forma, quando se está desenvolvendo um driver, o programador deve estar atento ao conceito de escrever código para acessar o hardware, mas não forçar políticas ao usuário, uma vez que diferentes usuários possuem diferentes necessidades. Dessa forma, o driver deve lidar com o problema de tornar o hardware acessível, deixando o problema de como usar o hardware para o SO/aplicativos.

• O que é necessário para poder desenvolver um device-driver no Linux?

Inicialmente, em termos de pré-requisitos, para desenvolver device drivers para o Linux, é necessário que se tenha algum conhecimento mais aprofundado em programação C, (como ponteiros, funções de manipulação de bits, etc) e programação de microprocessadores (saber como os microcomputadores funcionam internamente: endereçamento de memória, interrupções, etc).

Em termos práticos, de ambiente de desenvolvimento, a partir da versão 2.6.x do Kernel do Linux, a compilação de drivers tornou-se um pouco mais complicada do que era anteriormente, tornando-se necessário que se tenha a árvore de código fonte do kernel completa compilada, uma vez que é necessário compilar o módulo (driver) utilizando-se o mesmo kernel no qual você irá instalar o seu módulo (driver) (ver abaixo).

Vamos descrever aqui como fazer para criar e compilar um device driver bem simples (inútil na verdade, mas serve a título de exemplo), a ser incorporado ao kernel como um módulo.

Primeiramente crie um arquivo .c (driverTest.c) com o seguinte conteúdo:

#include [linux/module.h]
#include [linux/init.h]
#include [linux/kernel.h]
MODULE_LICENSE("GPL")
static int hello_init(void){
printk(" [1] Hello World!\n");
return 0;
}

static void hello_exit(void){
printk(" [1] Bye World!\n");
}

module_init(hello_init);
module_exit(hello_exit);

Explicando um pouco do código:
Quando um device driver é carregado no kernel, algumas tarefas preliminares são executadas, como resetar o dispositivo, reservar memória RAM, reservar interrupções, reservar ports de IO, etc. Essas tarefas são executadas em kernel-space por duas funções que precisam estar presentes (e explicitamente declaradas) no código do seu módulo (driver): module_init e module_exit. Elas correspondem aos comandos insmod e rmmod do user-space (ver abaixo), que são utilizados para instalar e remover módulos do kernel, respectivamente.

As funções hello_init e hello_exit podem receber qualquer nome. Contudo, para que elas sejam identificadas como sendo as funções de instalação e remoção do driver, elas precisam ser passadas como parâmetro para as funções module_init e module_exit. É isso que está acontecendo no nosso exemplo.

A função printk é bem parecida com a conhecida função printf, com a diferença que ela só funciona dentro do kernel.

Para compilar o seu módulo vc precisa gerar um makefile (chame-o de Makefile) com o seguinte conteúdo:

obj-m := driverTest.o

e para compilar o módulo digite (assumindo que a versão do kernel utilizado é 2.6.8):

$ make -C /usr/src/kernel-source-2.6.8 M=pwd modules

Esse módulo agora pertence ao kernel-space e irá se tornar parte dele assim que for carregado.

• Como se instalar um device-driver USB?

Assim como qualquer outro módulo carregável, no user-space, como root, pode-se instalar o módulo (driver) através do comando insmod, que permite a instalação do módulo (driver) no kernel.

Para remover o módulo (driver) do kernel utiliza-se o comando rmmod.

Através do comando lsmod é possível verificar se o módulo (driver) foi instalado/desinstalado corretamente.

• Descrevendo uma implementação de driver USB

Figura 2. Diagrama representativo do suporte oferecido pelo Linux à tecnologia USB

A necessidade de facilitar a conexão de dispositivos periféricos a um computador caracteriza um dos principais motivos que acarretaram na criação da tecnologia USB (Universal Serial Bus).

Inicialmente especificada em 1996 e muito difundida na atualidade, a tecnologia USB apresenta diversas características muito vantajosas como por exemplo: a padronização de conexão, utilização de tecnologia Plug and Play, alimentação elétrica própria, conexão de vários aparelhos ao mesmo tempo (é possível conectar até 127 dispositivos ao mesmo tempo em uma única porta USB), ampla compatibilidade (relativo a plataformas e sistemas operacionais), cabos longos (até cinco metros de comprimento), hot-swap (possibilidade de conectar e desconectar o dispositivo com o computador ligado).

O protocolo de comunicação entre os dispositivos conectados via USB é tal que o host, ou o computador ou equipamento que recebe as conexões, emite um sinal para encontrar os dispositivos conectados e estabelece um endereço para cada um deles.
Uma vez estabelecida a comunicação, o host recebe informação sobre qual tipo de conexão o dispositivo conectado utiliza.
Há quatro tipos distintos de conexões USB, a saber: Bulk (utilizado por dispositivos que manipulam grandes volumes de informações, como scanners e impressoras), Control (utilizado para controle e configuração de dispositivos), Interrupt (utilizado para dispositivos que manipulam/transferem poucos dados, como teclados e mouses) e Isochronous (utilizado em transmissões contínuas, onde os dados são transferidos a todo momento, como em caixas de som).

Na figura 2, temos um esquema representativo do suporte oferecido pelo Linux à tecnologia USB. Na figura podemos ver o USB Core, que é um subsistema do kernel que fornece uma API específica para suportar dispositivos USB e controladores host. A função do USB Core é abstrair todo o hardware ou partes dependentes de dispositivos através da definição de estruturas de dados, macros e funções.

Para exemplificar como isso é feito, podemos apresentar algumas das funções mais utiilzadas, como por exemplo a função interface_to_usbdev() que muitos drivers utilizam para acessar sua estrutura usb_device a partir da estrutura usb_interface, que é fornecida pelo USB Core.

Na API do USB Core, dispositivos são representados pela estrutura usb_device e drivers USB devem definir uma estrutura usb_driver como a seguir:

//Nome único ao driver.
//Normalmente utiliza-se o nome do módulo.
const char *name;
const struct usb_device_id *id_table;

int (*probe)
(struct usb_interface *intf,
const struct usb_device_id *id);

void (*disconnect)
(struct usb_interface *intf);

Para se registrar o seu driver, deve-se utilizar a função usb_register(), como no exemplo a seguir:

static struct usb_driver mtouchusb_driver = {
.name       = "mtouchusb",
.probe      = mtouchusb_probe,
.disconnect = mtouchusb_disconnect,
.id_table   = mtouchusb_devices,
};

static int __init mtouchusb_init(void){
dbg("%s - celled", __FUNCTION__);
return usb_register(&mtouchusb_driver);
}

e para se desregistrar o driver deve-se utilizar usb_deregister(), como a seguir:

static int __exit mtouchusb_cleanup(void){
dbg("%s - celled", __FUNCTION__);
return usb_deregister(&mtouchusb_driver);
}

Vale ressaltar que o código do kernel do Linux direcionado para USB se comunica com todos os dispositivos USB através de algo chamado urb (USB request block). Esse bloco é descrito com a estrutura struct_urb e pode ser encontrada no arquivo /linux/usb.h.

Para saber mais respeito de como utilizar a API do USB Core, recomendo [12] e [13]

• Como se testar um device-driver?

Executar testes em device drivers pode fazer com que seu sistema se comporte de maneira inesperada e possivelmente danificar o kernel. A seguir estão descritos alguns passos aconselháveis a serem seguidos no momento de testar seu device driver.

1) Instale o seu driver em um local temporário:
Instale os drivers no diretório /tmp até que se tenha concluído as modificações e testes das rotinas __info(), __init() e attach(). Copie o binário do seu driver no diretório /tmp e faça o link para o driver do diretório de drivers do kernel.
2) Utilize uma conexão serial para controlar sua máquina de testes através de um sistema host separado.
3) Utilize um kernel alternativo.
4) Utilize um kernel adicional para realizar experimentos com configurações diferentes de variáveis de kernel.
5) Construir planos de contingência para potenciais perdas de dados durante a execução dos testes do sistema.


Referências:
Todos os sites utilizados como referência foram visitados no dia 12 de Julho de 2009.

[1] http://en.wikipedia.org/wiki/Device_driver

[2] http://www.inf.pucrs.br/~eduardob/disciplinas/ProgPerif/sem09.1/trabalhos/Seminarios/g3/Device%20Drivers%20no%20Windows%20e%20Linux.doc

[3] http://www.linuxjournal.com/article/2476

[4] http://www.lrr.in.tum.de/Par/arch/usb/usbdoc/

[5] http://lwn.net/Kernel/LDD3/

[6] http://www.freesoftwaremagazine.com/articles/drivers_linux?page=0%2C0

[7] http://matthias.vallentin.cc/2007/04/writing-a-linux-kernel-driver-for-an-unknown-usb-device/

[8] http://linux.about.com/od/commands/l/blcmdl8_insmod.htm

[9] http://linux.about.com/library/cmd/blcmdl8_rmmod.htm

[10] http://linux.about.com/library/cmd/blcmdl8_lsmod.htm

[11] http://www.infowester.com/usb.php

[12] http://free-electrons.com/docs/linux-usb/

[13] http://www.lrr.in.tum.de/Par/arch/usb/usbdoc/node18.html

[14] http://docs.sun.com/app/docs/doc/819-3159/fsfqv?a=view

[15] http://docs.sun.com/app/docs/doc/819-3159/fdlbq?a=view

Configuração de Ambiente de Desenvolvimento - Linux

Utilizando-se a distribuição Ubuntu 8.04 do Linux, configurou-se o ambiente de programação para a execução das experiências de laboratório, que consistem em programação em linguagem C, utilizando bibliotecas como pthreads e semaphores, incluídas no padrão POSIX, implementado pelo sistema operacional (Linux).

Assumindo-se que o compilador gcc, da linguagem C, já se encontra instalado na máquina (vem instalado com a instalação padrão), instalou-se o pacote libc6-dev, que contém os cabeçalhos das bibliotecas necessárias para programarmos. Sem esse pacote o compilador não entenderá as diretivas #include de inclusão de bibliotecas padrão do C.

Para isso, no terminal, foi digitado:
sudo apt-get install libc6-dev

Após isso, instalou-se a famosa IDE eclipse, com o plugin CDT, o qual habilita a programação em linguagem C em tal IDE.

Para isso, no terminal, foi digitado:
sudo apt-get install eclipse eclipse-cdt

Após isso, no Eclipse, para cada um das experiências, foram criados projetos do tipo Managed Make C Project.

Cada projeto foi executado como Local C/C++ Application.

Adicionalmente, os projetos também puderam ser compilados pela linha de comando, no terminal, utilizando-se os comandos:

• gcc nome_do_arquivo.c -o nome_desejado_para_o_executavel
• gcc nome_do_arquivo.c -o nome_desejado_para_o_executavel -lpthread

O segundo comando deve ser utilizado quando se estiver compilando algo que utilize pthreads.

POSIX, Pthreads e afins...

POSIX (Portable Operating System Interface, que pode ser traduzido como Interface Portável entre Sistemas Operacionais) é uma família de normas definidas pelo IEEE que tem como objetivo garantir a portabilidade do código-fonte de um programa escrito para um sistema operacional que atenda as normas POSIX para outro sistema POSIX. Desta forma, as regras atuam como uma interface entre sistemas operacionais distintos.

A normalização das especificações POSIX surgiu de um projeto, iniciado por volta de 1985, que tinha como objetivo normalizar a API para softwares criados para serem executados em variantes do sistema operacional UNIX. O termo POSIX foi sugerido por Richard Stallman em resposta a um pedido da IEEE de um nome fácil de lembrar. É uma sigla aproximada de Portable Operating System Interface, com o X representando a herança que tal interface tem do sistema UNIX.

Como exemplo de recurso normalizado pelo padrão POSIX, temos as POSIX Threads, que é um padrão POSIX para threads, o qual define uma API padrão para criar e manipular threads.

As bibliotecas que implementam as POSIX Threads são chamadas pthreads, sendo muito difundidas no universo UNIX e outros sistemas operacionais semelhantes, como Linux e Solaris. Utilizaremos as pthreads em algumas das experiências desse laboratório.

Mais exemplos de normalizações impostas pelo padrão POSIX são (por versão):

• POSIX.1, Serviços de núcleo (incorpora o padrão ANSI C)
  • Criação e controle de processos
  • Signals
  • Exceções de Ponto Flutuante
  • Violações de Segmentação
  • Instruções Ilegais
  • Erros de Barramento
  • Timers
  • Operações com Arquivos e Diretórios
  • Pipes
  • Biblioteca padrão C
  • I/O - Controle e Interface de Portas

• POSIX.1b, Real-time extensions
  • Scheduling de Prioridade
  • Signals de Tempo-real
  • Clocks e Timers
  • Semáforos
  • Passagem de Mensagens
  • Memória Compartilhada
  • E/S Assíncronas e Síncronas
  • Bloqueamento(Locking) de Memória

• POSIX.1c, Threads extensions
  • Criação, Controle e Limpeza de Threads
  • Scheduling de Threads
  • Sincronização de Threads
  • Manipulação de Signals

Fontes:

http://pt.wikipedia.org/wiki/Posix
http://pt.wikipedia.org/wiki/POSIX_Threads

Algumas das Principais Funções Utilizadas

Biblioteca unistd.h

/* Clona o processo que está chamando a função, criando uma cópia exata.
Retorna -1 para erros, 0 para o novo processo e o ID do novo processo para o processo inicial.*/
__pid_t fork (void)

/* Cria um canal de comunicação de via única (pipe).
Caso a execução ocorra com sucesso, dois filedescriptors são armazenados em __pipedes;
Os bytes escritos em __pipedes[1] podem ser lidos em __pipedes[0].
Retorna 0 quando ocorre sucesso, -1 caso contrário.*/
int pipe (int __pipedes[2])

/* Fecha o file descriptor __fd.*/
int close (int __fd);

/* Lê __n bytes de __fd para __buf. Retorna o número lido, -1 para erros ou 0 para EOF.*/
ssize_t read (int __fd, void *__buf, size_t __nbytes)

/* Escreve __n bytes de __buf para __fd. Retorna o número escrito, ou -1.*/
ssize_t write (int __fd, __const void *__buf, size_t __n);

/* Faz com que o processo durma por __seconds, ou até que um signal chegue e não seja ignorado. A função retorna __seconds menos o número de segundos que o processo de fato dormiu (logo, retorna zero se ele dormiu todo o período).
Não há valor de retorno para indicar erro, mas caso a função retorne __seconds, então provavelmente a função não executou corretamente.*/
unsigned int sleep (unsigned int __seconds);


Biblioteca semaphore.h

/*Initializa o semáforo apontado por __sem, setando seu contador interno para __value. Se o argumento __pshared tiver um valor diferente de zero, então o semáforo é compartilhado entre processos; nesse caso, qualquer processo que puder acessar o semáforo __sem poderá usar __sem para executar as operações sem_wait(), sem_post(), sem_trywait() e sem_destroy();
Sempre retorna 0.*/
int sem_init(sem_t * __sem, int __pshared, unsigned int __value);

/* Aumenta atomicamente o contador do semáforo apontado por __sem. Essa função nunca é bloqueada e pode ser usada com segurança em tratadores de sinais assíncronos. Sempre retorna 0.*/
int sem_post(sem_t * __sem);

/* Suspende a tarefa de chamada até que o contador do semáforo apontado por __sem tenha um valor diferente de zero. Então, o contador é atomicamente decrementado. */
int sem_wait(sem_t * __sem);


Biblioteca pthread.h

/* Faz com que a thread que está chamando espere o fim da execução da thread __th. O status de saída da thread é armazenado em *__thread_return, se __thread_return não for nulo. */
int pthread_join (pthread_t __th, void **__thread_return);

/* Cria uma thread com os atributos especificados por __attr e que ao ser criada executa a função __start_routine com o argumento __arg. */
int pthread_create(pthread_t *__thread, const pthread_attr_t *__attr, void*(*__start_routine)(void *), void *__arg);

O Problema do Produtor e Consumidor (com pipes)

Em ciência da computação, o problema do produtor-consumidor (também conhecido como problema do buffer limitado) é um exemplo clássico de problema de sincronização multi-processo.

O problema descreve dois processos, o produtor e o consumidor, que compartilham um buffer de tamanho fixo. O trabalho do produtor é gerar um dado, colocá-lo no buffer e repetir essa operação indefinidamente. Ao mesmo tempo, a tarefa do consumidor é consumir tais dados (i.e. removendo do buffer), um de cada vez.

O problema consiste em assegurar que o produtor não irá tentar adicionar dados no buffer quando este estiver cheio, e que o consumidor não tentará remover dados quando o buffer estiver vazio.

A solução para o produtor é dormir quando o buffer estiver cheio. Na próxima vez que o consumidor remover um item do buffer, ele irá acordar o produtor, que continuará a colocar dados no buffer. Da mesma forma, o consumidor dorme quando encontra o buffer vazio. Na próxima vez que o produtor adicionar um dado no buffer, ele acordará o consumidor.

O problema pode ser generalizado para múltiplos produtores e múltiplos consumidores.

Para esta experiência, foi resolvido o problema do produtor-consumidor apenas para 1 produtor e 1 consumidor. A implementação foi feita utilizando-se pipes, os quais possuem seu próprio buffer interno. Foi assumido que os pipes são thread-safe (i.e., garantem a exclusão mútua e eliminam condições de disputa) visto que isto é previsto, de acordo com o padrão POSIX.

Vale ressaltar que, como o tamanho padrão do buffer interno do pipe é de 5Kbytes (muito grande), não foi possível, através da execução do programa implementado, visualizar a ocorrência de buffer cheio, previsto no problema do produtor-consumidor. No entanto, assumiu-se que a implementação do pipe, de acordo com o padrão POSIX, lida com a situação de buffer cheio adequadamente.

A saída para o programa pode ser verificada na figura abaixo:

Figura1: Saída do Programa
(clique na figura para melhor visualização)

Código:

#include "stdio.h"
#include "stdlib.h"
#include "unistd.h"

#define READ 0
#define WRITE 1
#define TRUE 1

/* protótipos */
void cria_item(int i);
void consome_item(int i);
void produtor(int fd[2], int qtde_itens);
void consumidor(int fd[2]);

int main (){
int fd[2];

/* criando pipe */
pipe (fd);

/* criando novo processo */
int pid = fork();

if (pid == -1) {
perror("Erro ao criar um novo processo!");
} else if (pid == 0) {
/* o novo processo funciona como produtor */
produtor(fd, 15);
} else {
/* o processo pai funciona como consumidor */
consumidor(fd);
}

return 0;
}

void produtor(int fd[2], int qtde_itens) {
close(fd[READ]);

int i, bytesEscritos;
for (i = 1 ; i <= qtde_itens; i++) {
sleep( rand() % 5 );
cria_item(i);

/* escreve no pipe */
bytesEscritos = write(fd[WRITE], &i, sizeof(int));

if (bytesEscritos == -1) {
   perror("Erro de escrita no pipe!");
}
}
close (fd[WRITE]);
}


void consumidor(int fd[2]){
close (fd[WRITE]);

int i, bytesLidos;
while (TRUE) {
/* lê do pipe */
bytesLidos = read (fd[READ], &i, sizeof(int));
sleep( rand() % 5 );
consome_item(i);

if (bytesLidos == -1) {
   perror("Erro de leitura no pipe!");
} else if (bytesLidos == 0) {
   break;
}
}
close (fd[READ]);
}

void cria_item(int i){
printf("Produtor criou o %d.o item.\n", i);
}

void consome_item(int i){
printf("Consumidor consumiu o %d.o item.\n", i);
}

Fontes:

http://en.wikipedia.org/wiki/Producer-consumer_problem
Sistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum

O Problema do Jantar dos Filósofos (com threads)

Em ciência da computação, o problema do jantar dos filósofos é um exemplo ilustrativo de um problema comum de programação concorrente. É mais um problema clássico de sincronização multi-processo.

O problema pode ser resumido como cinco filósofos sentados ao redor de uma mesa redonda, cada qual fazendo exclusivamente uma das duas coisas: comendo ou pensando. Enquanto está comendo, um filósofo não pode pensar, e vice-versa.

Cada filósofo possui um prato cheio de spaghetti à sua frente. Além disso, um garfo é posicionado entre cada par adjacente de filósofos (portanto, cada filósofo tem exatamente um garfo à sua esquerda e exatamente um garfo à sua direita).


Como spaghetti é uma comida díficil para se servir e comer com um único garfo, assume-se que um filósofo necessita de dois garfos para poder comer. E, além disso, um filósofo só pode utilizar um garfo que esteja imediatamente à sua esquerda ou imediatamente à sua direita.

A falta de disponibilidade de garfos é uma analogia à falta de recursos compartilhados em programação de computadores (situação conhecida como concorrência). Travar (lock) um recurso é um técnica comumemente utilizada para assegurar que o recurso está sendo acessado somente por um programa ou trecho de código, por vez. Quando um programa está interessado em um recurso que já foi travado por outro, o programa espera até que ele seja destravado. Quando existem vários programas envolvidos no travamento de recursos, um deadlock pode acontecer, dependendo das circunstâncias.

Para exemplificar, podemos citar um programa que necessita processar dois arquivos. Quando duas instâncias desse programa travam um arquivo cada, ambos os programas esperam o outro destravar o arquivo que falta, o que nunca irá ocorrerá.

Em geral, o problema do jantar dos filósofos é um problema genérico e abstrato que é utilizado para explicar diversas situações indesejáveis que podem ocorrer em problemas que tem como principal idéia a exclusão mútua.
Por exemplo, assim como no caso acima, deadlock/livelock é um conceito que pode ser bem explicado através do problema dos filósofos.

Abaixo encontra-se uma possível solução para o problema.
A solução apresentada é livre de deadlocks e permite o máximo de paralelismo a um número arbitrário de filósofos. Ela usa um arranjo, state, para controlar se um filósofo está comendo, pensando ou faminto (tentando pegar garfos). Um filósofo só pode mudar para o estado 'comendo' se nenhum dos vizinhos estiver comendo. Os vizinhos do filósofo i são definidos pelas macros LEFT e RIGHT. Em outras palavras, se i for 2, LEFT será 1 e RIGHT será 3.
O programa usa um arranjo de semáforos, um por filósofo; assim, filósofos famintos podem ser bloqueados se os garfos necessários estiverem ocupados. Observe que cada thread executa o procedimento philosopher como seu código principal, mas os outros procedimentos - take_forks, put_forks e test - são procedimentos ordinários, e não processos separados.

Figura1: Saída do Programa
(clique na figura para melhor visualização)

Código:

#include "stdio.h"
#include "stdlib.h"
#include "unistd.h"
#include "fcntl.h"
#include "sys/types.h"
#include "pthread.h"
#include "semaphore.h"

#define N           5           /* número de filósofos*/
#define LEFT        (i+N-1)%N   /* número do vizinho à esquerda de i*/
#define RIGHT       (i+1)%N     /* número do vizinho à direito de i*/
#define THINKING    0           /* o filósofo está pensando*/
#define HUNGRY      1           /* o filósofo está tentando pegar garfos*/
#define EATING      2           /* o filósofo está comendo*/
#define TRUE        1  
<
int state[N];                   /* arranjo para controlar o estado de cada um*/
sem_t mutex;                    /* exclusão mútua para as regiões críticas*/
sem_t s[N];                     /* um semáforo por filósofo*/

/* protótipos */
void* philosopher(void* arg);
void take_forks(int i);
void put_forks(int i);
void test(int i);
void eat(int i);
void think(int i);

int main() {
 int i;

 sem_init(&mutex, TRUE, 1);

 for(i = 0; i < N; i++) {
     sem_init(&s[i], TRUE, 1);
 }

 pthread_t tphil[5];

   /* criando os 5 filósofo - 1 thread para cada*/
   for(i = 0; i < N; i++) {
     pthread_create(&tphil[i], NULL, (void *) philosopher, (void *) &i);
 }

 for(i = 0; i < N; i++) {
     pthread_join(tphil[i], NULL);
 }

 return 0;
}

void* philosopher(void * arg) { /*i: o número do filósofo, de 0 a N-1*/
 int i = *((int *) arg);

 while(TRUE) {               /* repete para sempre*/
     think(i);               /* o filósofo está pensando*/
     take_forks(i);          /* pega dois garfos ou bloqueia*/
     eat(i);                 /* o filósofo está comendo*/
     put_forks(i);           /* devolve os dois garfos à mesa*/
 }

 pthread_exit(NULL);
}

void take_forks(int i) {        /*i: o número do filósofo, de 0 a N-1*/
 sem_wait(&mutex);           /* entra na região crítica*/
 state[i] = HUNGRY;          /* registra que o filósofo está faminto*/
 test(i);                    /* tenta pegar dois garfos*/
 sem_post(&mutex);           /* sai da região crítica*/
 sem_wait(&s[i]);            /* bloqueia se os garfos não foram pegos*/
}

void put_forks(int i) {         /*i: o número do filósofo, de 0 a N-1*/
 sem_wait(&mutex);           /* entra na região crítica*/
 state[i] = THINKING;        /* o filósofo acabou de comer*/
 test(LEFT);                 /* vê se o vizinho da esquerda pode comer agora*/
 test(RIGHT);                /* vê se o vizinho da direito pode comer agora*/
 sem_post(&mutex);           /* sai da região crítica*/
}

void test(int i) {
 if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
     state[i] = EATING;
     sem_post(&s[i]);
 }
}

void eat(int i) {               /*i: o número do filósofo, de 0 a N-1*/
 printf("Filosofo %d estah comendo!\n", i);
 sleep( rand()%5 );
}

void think(int i) {             /*i: o número do filósofo, de 0 a N-1*/
 printf("Filosofo %d estah pensando!\n", i);
 sleep( rand()%10 );
}

Fontes:

http://en.wikipedia.org/wiki/Dining_philosophers_problem
Sistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum

O Problema do Barbeiro Dorminhoco (com threads)

Em ciência da computação, o problema do barbeiro dorminhoco é um problema clássico de comunicação inter-processo e sincronização entre múltiplos processos.
O problema é análogo a manter o barbeiro ocupado enquanto há clientes, e descansando quando não há nenhum (fazendo isso de uma maneira ordenada).
O barbeiro e seus clientes correspondem aos processos mencionados acima.

O problema:
Na barbearia há um barbeiro, uma cadeira de barbeiro e n cadeiras para eventuais clientes esperarem a vez. Quando não há clientes, o barbeiro senta-se na cadeira de barbeiro e cai no sono. Quando chega um cliente, ele precisa acordar o barbeiro. Se outros clientes chegarem enquanto o barbeiro estiver cortando o cabelo de um cliente, eles se sentarão (se houver cadeiras vazias) ou sairão da barbearia (se todas as cadeiras estiverem ocupadas). O problema é programar o barbeiro e os clientes sem cair em condições de disputa. Esse problema é semelhante a situações com várias filas, como uma mesa de atendimento de telemarketing com diversos atendentes e com um sistema computadorizado de chamadas em espera, atendendo a um número limitado de chamadas que chegam.

A solução aqui apresentada usa três semáforos: customers, que conta os clientes à espera de atendimento (exceto o cliente que está na cadeira de barbeiro, que não está esperando); barbers, o número de barbeiros (0 ou 1) que estão ociosos à espera de clientes, e mutex, que é usado para exclusão mútua. Precisamos ainda de uma variável, waiting, que também conta os clientes à espera de atendimento. É essencialmente uma cópia de customers. A razão de se ter waiting é que não há uma maneira de ler o valor atual do semáforo. Nessa solução, um cliente que entra na barbearia deve contar o número de clientes à espera de atendimento. Se este for menor que o número de cadeiras, ele ficará; do contrário, ele sairá.

Na solução, quando chega de manhã para trabalhar, o barbeiro executa o método barber, que o leva a bloquear sobre o semáforo customers, que inicialmente está em 0. O barbeiro então vai dormir, e permanece dormindo até que o primeiro cliente apareça.
Quando chega, o cliente executa customer e inicia obtendo mutex para entrar em uma região crítica. Se um outro cliente chega logo em seguida, o segundo nada pode fazer até que o primeiro libere o mutex. O cliente então verifica se o número de clientes à espera é menor que o número de cadeiras. Se não for, ele liberará o mutex e sairá sem cortar o cabelo.
Se houver uma cadeira disponível, o cliente incrementará a variável inteira waiting. Ele faz então um up no semáforo customers, que acorda o barbeiro. Nesse ponto, o cliente e o barbeiro estão ambos acordados. Quando o cliente libera mutex, o barbeiro o pega, faz alguma limpeza e começa a cortar o cabelo.
Quando termina o corte de cabelo, o cliente sai do procedimento e deixa a barbearia. Diferente de nossos exemplos anteriores, não há um laço para o cliente porque para cada um deles terá apenas um corte de cabelo. O barbeiro, contudo, contém um laço para tentar obter o próximo cliente. Se houver algum outro cliente, um novo corte de cabelo será iniciado. Do contrário, o barbeiro cairá no sono.

Abaixo está a implementação do problema, com os resultados obtidos:

Figura1: Saída do Programa
(clique na figura para melhor visualização)

Código:

#include "stdio.h"
#include "unistd.h"
#include "stdlib.h"
#include "pthread.h"
#include "semaphore.h"

#define CHAIRS 5                /* número de cadeiras para os clientes à espera */
#define TRUE 1

sem_t customers;                /* número de cliente à espera de atendimento */
sem_t barbers;                  /* número de barbeiros à espera de clientes */
sem_t mutex;                    /* para exclusão mútua */
int waiting = 0;                /* clientes que estão esperando (não estão cortando) */

/* protótipos */
void* barber(void *arg);
void* customer(void *arg);
void cut_hair();
void customer_arrived();
void get_haircut();
void giveup_haircut();

int main() {
sem_init(&customers, TRUE, 0);
sem_init(&barbers, TRUE, 0);
sem_init(&mutex, TRUE, 1);

pthread_t b, c;

 /* criando único barbeiro */
 pthread_create(&b, NULL, (void *) barber, NULL);


 /* criação indefinida de clientes */
 while(TRUE) {
pthread_create(&c, NULL, (void *) customer, NULL);
sleep(1);
}

return 0;
}

void* barber(void *arg) {
while(TRUE) {
sem_wait(&customers);   /* vai dormir se o número de clientes for 0 */
sem_wait(&mutex);       /* obtém acesso a 'waiting' */
waiting = waiting - 1;  /*descresce de um o contador de clientes à espera */
sem_post(&barbers);     /* um barbeiro está agora pronto para cortar cabelo */
sem_post(&mutex);       /* libera 'waiting' */
cut_hair();             /* corta o cabelo (fora da região crítica) */
}

pthread_exit(NULL);
}

void* customer(void *arg) {
sem_wait(&mutex);           /* entra na região crítica */

if(waiting < CHAIRS) {      /* se não houver cadeiras vazias, saia */
customer_arrived();
waiting = waiting + 1;  /* incrementa o contador de clientes à espera */
sem_post(&customers);   /* acorda o barbeiro se necessário */
sem_post(&mutex);       /* libera o acesso a 'waiting' */
sem_wait(&barbers);     /* vai dormir se o número de barbeiros livres for 0 */
get_haircut();          /* sentado e sendo servido */
} else {
sem_post(&mutex);       /* a barbearia está cheia; não espera */
giveup_haircut();

}

pthread_exit(NULL);
}

void cut_hair() {
printf("Barbeiro estah cortando o cabelo de alguem!\n");
sleep(3);
}

void customer_arrived() {
printf("Cliente chegou para cortar cabelo!\n");
}
void get_haircut() {
printf("Cliente estah tendo o cabelo cortado!\n");
}

void giveup_haircut() {
printf("Cliente desistiu! (O salao estah muito cheio!)\n");
}

Fontes:

http://en.wikipedia.org/wiki/Sleeping_barber_problem
Sistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum

O Problema do Leitores e Escritores (com mutex e semáforos)

Outro problema famoso é o caso dos leitores e escritores, que modela o acesso a uma base de dados.
Imagine, por exemplo, um sistema de reserva de linhas aéreas, com muitos processos em competição, querendo ler e escrever. É aceitável que múltiplos processos leiam a base de dados ao mesmo tempo, mas, se um processo estiver atualizando (escrevendo) na base de dados, nenhum outro processo pode ter acesso ao banco de dados, nem mesmo os leitores. A questão é: como programar os leitores e os escritores?

Na solução apresentada abaixo, para obter o acesso à base de dados, o primeiro leitor faz um down no semáforo db. Os leitores subsequentes meramente incrementam um contador, rc. Conforme saem, os leitores decrescem o contador de um e o último leitor a sair faz um up no semáforo, permitindo que um eventual escritor bloqueado entre.

Tal solução contém implicitamente uma decisão sutil que vale a pena ser comentada. Suponha que, enquanto um leitor está usando a base de dados, um outro leitor chegue. Como ter dois leitores ao mesmo tempo não é um problema, o segundo leitor é admitido. Um terceiro leitor e outros subsequentes podem também ser admitidos se chegarem.
Agora, imagine que chegue um escritor. O escritor não pode ser admitido na base de dados, pois escritores devem ter acesso exclusivo. O escritor é então suspenso. Leitores adicionais chegam. Enquanto houver pelo menos um leitor ativo, leitores subsequentes serão admitidos. Como consequência dessa estratégia, enquanto houver um fluxo estável de leitores chegando, todos entrarão assim que chegarem. O escritor permanecerá suspenso até que nenhum leitor esteja presente. Se um novo leitor chegar - digamos, a cada dois segundos - e cada leitor levar cinco segundos para fazer seu trabalho, o escritor nunca entrará.
O programa poderia ser escrito de um modo um pouco diferente: se um leitor chegar quando um escritor estiver esperando, o leitor será suspenso logo depois do escritor, em vez de ser admitido de imediato. Dessa maneira, um escritor, para terminar, precisa esperar por leitores que estavam ativos quando ele chegou, mas não por leitores que chegaram depois dele. A desvantagem dessa solução é que se consegue menos concorrência e, portanto, um desempenho menor.

A implementação da solução descrita está exemplificada abaixo para o caso de 3 leitores e 2 escritores.

Figura1: Saída do Programa
(clique na figura para melhor visualização)

Código:

#include "stdio.h"
#include "unistd.h"
#include "stdlib.h"
#include "pthread.h"
#include "semaphore.h"

#define TRUE 1

sem_t mutex;                    /* controla o acesso a 'rc' */
sem_t db;                       /* controla o acesso a base de dados */
int rc = 0;                     /* número de processos lendo ou querendo ler */

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

int main() {
sem_init(&mutex, 0, 1);
sem_init(&db, 0, 1);

pthread_t r[3], w[2];

int i;

    /* criando leitores */
    for (i = 0; i < 3 ; i++) {
 pthread_create(&r[i], NULL, reader, (void*) &i);
}

    /* criando escritores */
    for (i = 0; i< 2; i++) {
 pthread_create(&w[i], NULL, writer, (void*) &i);
}

while(TRUE);
return 0;
}

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

while(TRUE) {               /* repere para sempre */
 sem_wait(&mutex);       /* obtém acesso exclusivo à 'rc' */
 rc = rc + 1;            /* um leitor a mais agora */

 if (rc == 1) {          /* se este for o primeiro leitor... */
     sem_wait(&db);   
 }

 sem_post(&mutex);       /* libera o acesso exclusivo a 'rc' */
 read_data_base(i);       /* acesso aos dados */
 sem_wait(&mutex);       /* obtém acesso exclusivo a 'rc' */
 rc = rc - 1;            /* um leitor a menos agora */

 if (rc == 0) {          /* se este for o último leitor */   
     sem_post(&db);
 }

 sem_post(&mutex);       /* libera o acesso exclusivo a 'rc' */
 use_data_read(i);        /* região não crítica */
}
}

void* writer(void *arg) {
int i = *((int *) arg);

while(TRUE) {               /* repete para sempre */
 think_up_data(i);        /* região não crítica */
 sem_wait(&db);          /* obtém acesso exclusivo */
 write_data_base(i);      /* atualiza os dados */
 sem_post(&db);          /* libera o acesso exclusivo */
}
}

void read_data_base(int i) {
printf("Reader %d estah lendo os dados!\n", i);
sleep( rand() % 5);
}

void use_data_read(int i) {
printf("Reader %d estah usando os dados lidos!\n", i);
sleep(rand() % 5);
}

void think_up_data(int i) {
printf("Writer %d estah pensando no que escrever!\n", i);
sleep(rand() % 5);
}

void write_data_base(int i) {
printf("Writer %d estah escrevendo os dados!\n", i);
sleep( rand() % 5);
}

Fontes:

http://en.wikipedia.org/wiki/Readers-writers_problem
Sistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum