Semáforos

São variáveis que permitem sincronização entre processos, de modo a evitar race conditions (quando dois ou mais processos necessitam de escrever/ler dados partilhados simultaneamente) ,cujas operações são atómicas (indivisíveis) e executadas pelo kernel. São utilizados para a gestão de recursos (ex: se temos uma impressora que só admite 5 impressões simultâneas, temos de assegurar que em cada instante existem no máximo 5 processos a imprimir - ficando os outros à espera para imprimir). Uma situação especial da competição por um recurso é a exclusão mútua (apenas um processo pode efectuar uma determinada operação). Um exemplo desta situação é actualização de uma base de dados partilhada por vários processos.

Modo de Armazenamento

• O kernel mantém um array - Tabela de Semáforos.
• Uma entrada no array possui:
• um apontador para um array de semáforos;
• uma estrutura.

struct semid_ds

{

struct ipc_perm sem_perm; /* estrutura de permissões */

short pad1[7]; /* reservado */

unshort sem_nsems; /* nº de semáforos no array */

time_t sem_otime; /* instante da última operação semop */

time_t sem_ctime; /* instante da última alteração de atributos do conjunto de semáforos através de semctl + IPC_SET */

}

• Cada entrada no array de semáforos (conteúdo de um semáforo) possui:

- o valor do semáforo;

- pid do último processo a manipular o semáforo (através de semop/semctl);

- o número de processos que estão à espera que o valor do semáforo seja 0 .

- o número de processos que estão à espera que seja feito um UP (libertar recursos) no semáforo;

System Calls

• int semget (int chave, int nsems, int flags) - permite criar ou aceder a um conjunto de semáforos. Retorna um identificador associado ao conjunto de semáforos chave de nsems elementos, de acordo com as flags flags. Este identificador vai ser utilizado nas outras operações de semáforos.

O nome pode ter os seguintes valores:

• 0 (IPC_PRIVATE)

- permite criar um conjunto de semáforos privado ao processo invocador;

- o identificador resultante nunca vai ser retornado a outros processos que invoquem semget, seja qual for o seu parâmetro chave;

- existe a garantia de que o sistema cria um conjunto novo;

- o identificador do conjunto pode ser partilhado com outros processos, ao serem feitos sucessivos fork(), em que os valores das variáveis do processo pai são herdados pelas correspondentes variáveis dos processos filho.

• ¹ 0

- permite criar ou aceder a um conjunto de semáforos, de acordo com o conteúdo das flags flags;

- o conjunto pode ser partilhado com qualquer outro processo, desde que o parâmetro chave seja igual.

Valores que flags pode ter:

• Flag IPC_CREAT activa e flag IPC_EXCL activa

- Cria um conjunto de semáforos nome (se este não existir);

- Permite verificar se um dado conjunto existe ou não.

• Flag IPC_CREAT não activa e flag IPC_EXCL não activa

- Acede ao conjunto de semáforos nome (se existir);

- Se já existir o conjunto nome e o seu número de semáforos é inferior que nsems, então retorna erro.

• Flag IPC_CREAT activa e flag IPC_EXCL não activa

- Acede ao conjunto de semáforos nome (se existir); se não existir cria-o;

- Se já existir o conjunto nome e o seu número de semáforos é inferior que nsems, então retorna erro.

Nota: Na operação de abertura de um conjunto de semáforos, devem ser respeitadas as permissões de acesso, isto é, as flags de permissão presentes no argumento flags (escritas na forma 0xxx), devem conter aquelas presentes no conjunto de semáforos (aquando da sua criação).

Se a system call originar um erro, o valor retornado é -1, sendo associado à variável global errno o erro correspondente.

• int semop(int semid, struct sembuf *sops, unsigned nsops) - executa as nsops operações presentes em sops, sobre o conjunto de semáforos associado ao identificador semid.

Argumento sops:

• uma operação é do tipo:

struct sembuf

{ short sem_num; /* número do semáforo */

int sem_op; /* operação */

int flags;

}

e significa executar a operação sem_op sobre o semáforo sem_num de acordo com flags.

• campo sem_op:

< 0

o executa uma operação DOWN(P) - aloca p recursos.

o Se valor(sem_num) ³ ô sem_opô , a operação tem sucesso e é decrementado ao valor do semáforo ô sem_opô ;

o Se o resultado é 0, o kernel acorda todos os processos bloqueados à espera que o semáforo sem_num fosse igual a 0.

> 0

o executa a operação UP(V) - liberta v recursos.

o O valor de sem_op é adicionado ao valor de sem_num;

o O kernel acorda todos os processos bloqueados devido a esse semáforo.

= 0

o espera que o semáforo sem_num seja igual a 0.

• campo Flags

Flag IPC_NOWAIT:

- caso de sem_op < 0 e valor(sem_num) <ô sem_opô

Activa: semop falha e retorna erro.

Não activa: semop suspende o processo invocador até que:

- valor(sem_num) ³ ô sem_opô ;

- semid seja removido do sistema, o que origina erro como valor de retorno da system call semop;

- o processo invocador recebe um sinal capturado

- caso de sem_op = 0 e valor(sem_num) ¹ 0

Activa: semop falha e retorna erro.

Não activa: semop suspende o processo invocador até que:

- valor(sem_num) = 0, o que implica que semop retorna com sucesso;

- valor(sem_num) = ô sem_opô , o que implica que o kernel execute de novo a operação.

- semid seja removido do sistema, o que origina um erro como valor de retorno.

- O processo invocador receba um sinal capturado.

Flag SEM_UNDO

Existe a possibilidade de uma secção crítica ficar bloqueada eternamente - quando o processo que a reservou não a libertar (ex: quando um processo recebe um sinal no meio da secção crítica, termina o processo, sem desbloquear a secção crítica).

Esta flag, tem como objectivo tornar fiável a utilização de semáforos, fazendo com que o kernel mantenha memorizadas as operações de sincronização executadas pelos processos. É utilizada uma estrutura dinâmica que memoriza todas as operações executadas pelo processo sobre cada semáforo. Quando o processo termina, o kernel percorre toda a estrutura e reactualiza os valores dos semáforos.

• int semctl(int semid, int semnum, int cmd, union semun arg ) - permite alterar os atributos de um conjunto de semáforos identificado por semid, ou destruir o conjunto. Executa o comando cmd do semáforo semnum pertencente ao conjunto identificado por semid.

union semun

{

int val;

struct semid_ds *buf;

unsigned short *array;

}

cmd pode ter os seguintes valores:

• SETVAL - inicializa o semáforo semnum=arg.val;
• GETVAL - retorna o valor do semáforo semnum;
• GETPID - retorna o pid do último processo que executou semop sobre semnum;
• GETNCNT - retorna o número de processos bloqueados à espera que o semáforo semnum execute um UP (liberta recursos);
• GETZCNT - retorna o número de processos bloqueados à espera que o semáforo semnum seja igual a 0;
• SETALL - inicializa o conjunto de semáforos com o valor contido no array apontado por arg.array;
• GETALL - retorna o valor de todos os semáforos para o array arg.array;
• IPC_STAT - retorna o conjunto de atributos do conjunto de semáforos para arg.buf;
• IPC_SET - altera os atributos do conjunto de semáforos para os valores em arg.buf (apenas sem_perm.uid, sem_perm.cuid, e sem_perm.mode);
• IPC_RMID - destrói o conjunto de semáforos, assim como o seu identificador.

Observações:

• O utilizador para executar os comandos GETVAL, GETPID, GETNCNT, GETZCNT, GETALL e IPC_STAT necessita de ter permissão de leitura;
• O utilizador para executar os comandos SETVAL e SETALL necessita de permissão de escrita;
• O utilizador para executar os comandos IPC_SET e IPC_RMID deve ter uid equivalente ao campo sem_perm.uid, ou igual ao campo sem_perm.cuid ou então deve ser o superuser.

Exemplo

#include <unistd.h>

#include <stdlib.h>

#include <stdio.h>

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/sem.h>

/* Este exemplo cria 20 processos. Em cada instante existem no maximo 5 processos - so' cria outro processo quando um filho terminar e libertar o recurso...*/

main()

{

int s,i,j;

pid_t pid;

union semun seu;

struct sembuf up,down;

/* estrutura para libertar um recurso */

up.sem_num=0; /* numero do semaforo - array de semaforos…*/

up.sem_op=1; /* numero de recursos que liberta */

up.sem_flg=0;

/* estrutura usada para ocupar um recurso */

down.sem_num=0; /* numero do semaforo */

down.sem_op=-1; /* numero de recursos que ocupa */

down.sem_flg=0;

/* cria o semaforo */

if ((s=semget((key_t)0,1,0777|IPC_CREAT)) == -1)

{

printf("Erro ao abrir o semaforo\n");

exit(-1);

}

/* inicializa o semaforo - neste caso existem 5 unidades disponiveis */

seu.val=5;

semctl(s,0,SETVAL,seu);

/* cria,cao dos 20 processos - apenas podem existir 5 processos filho

em cada instante */

for(i=0;i<20;i++)

{ /* ocupa um recurso - so' continua quando existirem recursos...*/

semop(s,&down,1);

if ((pid=fork())==0)

{

/* filho */

break;

}

}

if (pid>0)

{

for (i=0;i<20;i++)

wait(&j);

semctl(s,0,IPC_RMID,NULL);

}

else

{

/* filho */

printf("O filho %d foi criado\n",i);

sleep(i);

semop(s,&up,1); /* liberta o recurso utilizado */

printf("Fim do filho %d\n",i);

exit(0);

}

}

Exercícios

1- Faça as seguintes funções:

int cria_semaforo(int chave, int n_recursos) - esta função cria um semáforo com n_recursos.

int ocupa_recursos(int identificador, int n_recursos) - esta função ocupa n_recursos de um semáforo

int liberta_recursos(int identificador, int n_recursos) - esta função liberta n_recursos de um semáforo

int remove_semaforo(int identificador) - esta função remove do sistema um semáforo.

Nota: todas as funções partem do pressuposto que para cada conjunto de semáforos apenas é utilizado um semáforo.

2 - Faça um programa que:

• crie 5 processos;
• cada processo filho escreve 200 números num ficheiro de texto;
• o semáforo deve ser privado;
• garanta a exclusão mútua.

3 - Faça um programa que:

• escreva uma linha num ficheiro de texto;
• espera 2 segundos;
• deve garantir exclusão mútua, isto é, quando um processo está a escrever, apenas ele o pode fazer, de modo a evitar incoerências no ficheiro;
• o ficheiro apenas pode conter um máximo de dez linhas;
• Execute o programa várias vezes para testar a funcionalidade do exercício.

Nota: utilize semáforos para resolver o problema. Também pode fazer o programa de remoção de linhas, ou seja, o programa que liberta recursos.

4 - O mesmo que o exercício anterior, mas agora cada processo pode escrever 3 linhas no ficheiro de texto.

5 - Faça os seguintes programas:

Leitor

• Tem como função ler de uma base de dados;
• Como os leitores não alteram a base de dados, podem existir vários leitores a aceder aos dados em cada instante;
• Os leitores têm prioridade em relação aos escritores, isto é, enquanto existir um processo a querer ler, nenhum processo pode escrever na base de dados.
• Cada leitor deve imprimir o número de leitores nesse instante.

Escritor

• Tem como função escrever na base de dados;
• É necessário garantir exclusão mútua (em cada instante só pode existir um processo a escrever na base de dados) ;
• Os escritores só acedem à base de dados, quando não existirem leitores;
• Cada escritor deve imprimir o número de escritores nesse instante, bem como o número de leitores.

Execute vários leitores e escritores para testar a funcionalidade do programa desenvolvido.

6 - Considere uma ponte onde em cada instante apenas é possível a passagem de automóveis num sentido (AB ou BA). Na ponte podem estar 15 automóveis, sendo que cada automóvel antes de entrar na ponte tem de cumprir os seguintes requisitos:

- Só pode entrar na ponte se ainda não estiverem lá 15 automóveis e seja esse o sentido actual dos carros que estão a percorrer a ponte. Se já estiverem na ponte 15 automóveis e for esse o sentido actual da ponte, então deve esperar que um dos automóveis saia da ponte, assegurando que vai para a ponte na sua vez.

Para testar o impacto no tráfego, você foi encarregado em desenvolver os programas que permitam a simulação desta situação.

Nota 1: O comportamento dos automóveis é efectuado através dos programas SENTIDO_AB e SENTIDO_BA. Considere que esses programas vão ser executados pelo programa gera_teste que é responsável por lançar novos automóveis na simulação.

Nota 2: Cada "automóvel" deve apresentar no monitor o tempo que demorou a atravessar a ponte.

Nota 4: implmente também o programa gera_teste que é responsável por lançar novos automóveis na simulação.