Real-tempo Experiência #1: Tempo

Sistemas Operacionais, 1⁰ semestre/2004

Experimento # 4

1. Introdução

Nos experimentos prévios foram utilizados mecanismos de IPC (Inter-Process Communication) baseados em fila de mensagens, memória compartilhada e sinais. Usando estes mecanismos foi possível compartilhar dados entre diferentes processos. De fato, no experimento # 2 foi usada fila de mensagens para comunicação de dados. No experimento # 3 foi usada memória compartilhada, porém, foi tomado muito cuidado para assegurar que os processos não escrevessem dados ao mesmo tempo na mesma região de memória. Quando uma região de memória é compartilhada entre dois processos que podem ter acesso a esta memória simultaneamente, esta região de memória deve ser protegida.

Diferentemente do experimento #2, onde o programador teve que estabelecer áreas diferentes para diferentes processos, um mecanismo que pode ser usado para solucionar o problema de acesso simultâneo a uma mesma área de memória, se chama semáforo. Semáforos são mecanismos compartilháveis entre processos que garantem sincronismo, se utilizados de maneira adequada, por exemplo para que um processo tenha acesso exclusivo a um recurso crítico em uma localização de memória.

Neste experimento deseja-se explorar o conceito de exclusão mútua e perceber o funcionamento de semáforos.

Este exercício foi definido a partir dos experimentos existentes em http://www.rt.db.erau.edu/experiments/unix-rt que pertencem ao Laboratório Embry-Riddle de tempo-real.

2. Objetivos

A seguir estão os objetivos deste experimento com relação ao aluno:

Observar e entender por que um recurso crítico deve ser protegido contra acessos simultâneos.

Esclarecer o conceito de exclusão mútua, de maneira a ser capaz de explicá-lo e descrevê-lo.

Entender como e quando usar semáforos.

3. Teoria

A seguir são discutidos conceitos diretamente relacionados com o experimento, sua leitura é importante e será cobrada quando da apresentação. Caso o entendimento desses conceitos não se concretize procure reler e, se necessário, realizar pequenas experiências de programação até que ocorra o entendimento.

Às vezes é necessário manter um recurso crítico de maneira exclusiva para impedir que outros processos tenham acesso a esse recurso simultaneamente.

Em um SO multi-tarefa, a execução de processos de maneira simultânea ou mesmo intercalada pode ocasionar situações imprevisíveis. Quando a interação com o usuário é adicionada e esta é a responsável pelo acesso e uso ao recurso, fica mais difícil para um projetista do SO predizer quando um dos processos tentará ter acesso ao recurso.

Dois processos que são executados separadamente, se tentam ter acesso a um recurso "simultaneamente", necessitam de um método que impeça que os dois ou mais processos tenham acesso ao recurso.

A solução teórica para o problema do recurso crítico é simples: antes de entrar na região crítica de código (parte do programa em que o recurso é acessado), o recurso é tornado indisponível.

Deixando o recurso indisponível, nenhum outro processo pode entrar na sua região crítica. Uma vez que o processo acaba de ter sua região crítica executada, o mesmo disponibiliza o recurso, de forma que outros processos possam ter acesso. Um processo desejando acessar o recurso compartilhado necessita apenas verificar a disponibilidade do mesmo antes de ter sua região crítica executada.

Exclusão mútua

Exclusão mútua é o princípio em que só um processo pode ter acesso à região crítica em um momento. Tente perceber a situação seguinte:

Processo A testa a disponibilidade do recurso e o encontra disponível.

Processo A perde a CPU e o processo B é escalonado (se houver uma tentativa de controle de acesso, o processo A perde a CPU depois que realizou o teste em que se verifica se o recurso está disponível e antes de estabelecer a indisponibilidade).

Processo B testa a disponibilidade do recurso e o encontra disponível.

Processo B torna o recurso indisponível.

Processo B entra na região crítica.

Processo B perde a CPU e A é escalonado.

Processo A torna o recurso indisponível.

Processo A entra na região crítica e a exclusão mútua é violada.

Sempre que um processo está na fase de fazer o teste e indisponibilidade do recurso, há uma chance da exclusão mútua ser violada. Então, devem ser executados o teste e a indisponiblização em uma única e atômica operação. Uma operação atômica tem que ser completada inteira antes que um processo perca a CPU.

Implementando uma operação que teste e indisponibilize de maneira atômica, através de software, é uma tarefa difícil. Algoritmos existem, mas são grandes e lentos. Uma operação teste-e-indisponibilize atômica é implementada tipicamente ou por uma instrução de processador de máquina (como o operador test_and_set) ou pelo núcleo do sistema operacional, que usa operadores de hardware. O SO pode controlar o escalonamento de um processo e pode garantir então que este não seja interrompido com relação ao acesso ao recurso.

Semáforos

Semáforos são mecanismos que resolvem o problema de exclusão mútua. Um semáforo pode ser visto como um objeto que pode sofrer uma operação de duas formas: trancando e destrancando a execução de instruções (estas operações de trancar e destrancar são comumente chamadas com outros nomes, por exemplo como up e down). As operações sobre um semáforo são atômicas (ou seja, não são interrompidas até sua completa finalização).

Semáforos são implementados no sistema operacional e são considerados uma forma de IPC (semáforos também podem ser usados para sincronização, tão bem como para obtenção de exclusão mútua). Da mesma maneira que SO´s diferentes implementam versões diferentes de memória compartilhada e filas de mensagens, há várias implementações de semáforos. O POSIX.1b implementa semáforos com identificadores e sem identificadores. O System V também implementa semáforos e são estes os que vão ser usados neste experimento.

Semáforos do System V

As seguintes chamadas de sistema são usadas para operar semáforos no System V:

semget () cria um conjunto de semáforos com base em uma determinada chave e retorna o identificador do semáforo

semop () permite ao processo testar, trancar e destrancar o semáforo

semctl () permite executar operações gerais sobre o semáforo, tal como remover ou reinicializar.

Igualmente aos mecanismos de memória compartilhada e de fila de mensagens, os semáforos no System V usam uma chave única para identificar um conjunto de semáforos, que individualmente são identificados por números seqüenciais começando em 0. Para detalhes sobre a operação e uso de chave associada a mecanismo de IPC, olhar os experimentos anteriores.

Semáforos no System V são agrupados em conjuntos. Isto significa que um conjunto contém um ou mais semáforos.

Para cada conjunto deve ser associada uma chave, através da qual especificam-se operações que podem ser executadas sobre qualquer membro do conjunto.

Neste experimento, todos os conjuntos de semáforos criados conterão apenas um semáforo e as operações usadas não se aplicam ao conjunto de semáforos, mas a um semáforo individual. Para mais informação sobre conjuntos de semáforos, leia as páginas correspondentes usando o comando man.

O exemplo de código seguinte mostra como criar um semáforo no System V:

#define SEM_KEY 1234

#define NO_OF_SEMS 1

#define SEM_PERMS 0666

int id;

if ((id = semget (SEM_KEY, NO_OF_SEMS, SEM_PERMS | IPC_CREAT)) == -1) {

perror ("chamada de semget falhou !");

exit(1);

}

No código acima, a chamada semget () recebe três argumentos. SEM_KEY é a chave única para o IPC do System V. Veja mais informação sobre a chave (e o id) junto aos experimentos anteriores. NO_OF_SEMS é o número de semáforos no conjunto, ou seja, um (lembrar que esta opção permite associar múltiplos semáforos com um único key/id). Finalmente, o último argumento corresponde às permissões de acesso ao conjunto e ao flag para criação.

semget () devolverá o id do conjunto de semáforos, se terminar bem, e -1 caso contrário.

O exemplo de código seguinte mostra como trancar e destrancar um semáforo no System V:

int id;

struct sembuf sembuf[1];

... addquirindo o ID do conjunto de semáforos ...

sembuf[0] .sem_num = 0;

sembuf[0] .sem_op = -1; / * use 1 para destrancar * /

sembuf[0] .sem_flg = 0;

if (semop (id, sembuf, 1) == -1)

{

perror (chamada de " semop falhou !");

exit(1);

}

O código acima pode confundir um pouco, portanto um exame detalhado deve ser feito.

Como dito anteriormente, semop () é usado para trancar e destrancar semáforos. A chamada semop () recebe três argumentos, o ID do conjunto de semáforos, um ponteiro para um vetor de estruturas do tipo sembuf, e o número de elementos no vetor. Isto permite que a chamada semop () opere sobre vários semáforos em uma única operação atômica.

A estrutura sembuf contém três elementos, sem_num, sem_op, e sem_flg. sem_num é o número do semáforo dentro do conjunto sobre o qual será realizada a operação, ou seja, neste experimento sem_num será sempre 0 (que representa o primeiro semáforo no conjunto). sem_flg é um flag que pode ser usado para executar operações especiais. Neste experimento, será sempre 0. sem_op é a operação a ser executada. Use -1 para trancar o semáforo e 1 para destrancar.

NOTA, para mais informação sobre os valores para estas estruturas, use o comando man. As operações sobre semáforos têm muito mais detalhes que o explicado aqui.

Como mencionado anteriormente, semctl () pode ser usado para remover um conjunto de semáforos. Como a chamada para semctl () é semelhante a uma chamada IPC "ctl", também não será explicada em detalhes aqui, ver experimento #2.

É importante notar que o valor padrão de inicialização de um semáforo é 0. No contexto acima, 0 indica que o semáforo está trancado. Então, imediatamente depois de criar o semáforo, o semáforo deve ser destrancado, para poder usado como mecanismo para exclusão mútua. Isto pode parecer estranho, mas é o modo como os semáforos são implementados.

Programa exemplo

O programa exemplo demonstra como podem ser usados semáforos para proteger recursos compartilhados. No programa exemplo, o recurso compartilhado é um string de caracteres que é exibido na tela e no qual vários processos tentarão colocar letras do alfabeto cooperativamente, de maneira que não ocorra desordem das letras. O programa é projetado para ser compilado de dois modos, um em que não há proteção de semáforo para exclusão mútua e um outro com proteção de semáforo.

Examine como o programa se comporta em cada um dos dois modos.

Um único processo pai inicia vários processos filhos, seguindo o algoritmo:

Inicialize as estruturas de semáforo

Crie e inicialize o semáforo

Crie, associe e inicialize o segmento de memória compartilhada

Inicie o número especificado de filhos de forma que cada um chama PrintAlphabet

Espere por vinte segundos

Mate os filhos

Destrua o semáforo

Destrua o segmento de memória compartilhada

Termine

Os filhos usam o seguinte algoritmo:

Durma por um período pequeno de tempo para dar a todos os filhos uma chance de terem começado.

Adquira a hora do dia e gere um número pseudo randômico.

Se PROTECT é especificado, tranque o semáforo.

Obtenha o índice atual do segmento de memória compartilhada.

Execute um loop o número de vezes variável e escreva um único caractere na tela a cada iteração.

Durma por 1 microsegundo para dar aos outros processos uma chance para executar.

Copie o índice de volta ao segmento de memória compartilhada.

Verifique se o índice atual não está além da fronteira do vetor e, se estiver, escreva um caractere de retorno na tela e coloque zero no índice.

Se PROTECT é especificado, destranque o semáforo.

Repita o loop

A string de caracteres que estará sendo exibida pelos processos é:

char g_alphabet [ ] = " abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ ";

Com PROTECT definido, a saída deve parecer com algo do tipo:

Filho 1 iniciado

Filho 2 iniciado

Filho 3 iniciado

abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ

abcdefghijklmnopqrstuvwxyz 12345

Com PROTECT não definido, a saída é dramaticamente diferente (NOTA: A barra invertida indica uma mudança de linha que não foi produzida através de um caractere de retorno):

Filho 1 iniciado

Filho 2 iniciado

Filho 3 iniciado

abacbdcceddfeegffhggihhjiikjjlkkmllnmmonnpooqpprqqsrrtssuttvuuwvvxwwyxxzyy zz1 \

211322433544655766877988099 00A BACADBBECCFDDGEEHFFIGGJHHKIILJJMKKNLLOMMPNNQO \

ORPPSQQTRRUSSVTTWUUXVVYWWZXX YY ZZ

a b c

da

eabfcbgcdhediefjgfkghlihmijnkjoklpmlqmnronsoptqpuqrvsrwstxutyuvzwv wx1yx2yz3 z4 \

1521623743845965067 87A89B09C0 DA EABFCBGCDHEDIEFJGFKGHLIHMIJNKJOKLPMLQMNRONSO \

PTQPUQRVSRWSTXUTYUVZWV WX YX

aYZb cd de Z

a

abefcbcdghedefijgfghklihijmnkjklopmlmnqronopstqpqruvsrstwxutuvyzwvwx 1yxyz23 z \

14521236743458965670 8789AB090 CDA ABEFCBCDGHEDEFIJGFGHKLIHIJMNKJKLOPMLMNQRONO \

PSTQPQRUVSRSTWXUTUVYZWVWX YXYZ

A razão para isto é simples, todos os três processos estão acessando o índice armazenado simultaneamente na memória compartilhada e o ato de trancar é necessário para proteger o recurso.

Em seguida são apresentadas várias seções do código onde pode-se perceber o que o programa está fazendo exatamente. As operações sobre semáforos são examinadas em detalhes. O código seguinte cria e inicializa um semáforo e várias estruturas usadas em operações de semáforo:

#define SEM_KEY 0x1234

...

struct sembuf g_lock_sembuf[1];

struct sembuf g_unlock_sembuf[1];

...

g_lock_sembuf[0] .sem_num = 0;

g_lock_sembuf[0] .sem_op = -1;

g_lock_sembuf[0] .sem_flg = 0;

g_unlock_sembuf[0] .sem_num = 0;

g_unlock_sembuf[0] .sem_op = 1;

g_unlock_sembuf[0] .sem_flg = 0;

...

if ((g_sem_id = semget (SEM_KEY, 1, IPC_CREAT | 0666)) == -1) {

fprintf(stderr, "chamada semget () falhou, nao pode criar semaforo !");

exit(1);

}

if (semop (g_sem_id, g_unlock_sembuf, 1) == -1) {

fprintf(stderr, "chamada semop () falhou, nao pode inicializar semaforo " );

exit(1);

}

...

if (semctl (g_sem_id, 0, IPC_RMID, 0) != 0) {

fprintf(stderr," nao foi possivel remover o semaforo!\n ");

exit(1);

}

A primeira seqüência de código cria dois arrays de estruturas do tipo sembuf, com um elemento.

A seguir estão as operações que serão executadas no semáforo. Uma é usada para trancar e a outra para destrancar. Estas estruturas são inicializadas no processo pai. Há três elementos na estrutura, sem_num, sem_op, e sem_flg.

Para ambas as estruturas, sem_num é inicializado com zero declarando que estamos operando no primeiro semáforo do conjunto (único criado no conjunto!) e sem_flg é inicializado com zero declarando que nenhuma "ação especial" é necessária. sem_op é inicializado com -1 para trancamento e 1 para o destrancamento.

Em seguida, o conjunto de semáforos com a chave SEM_KEY é criado usando a chamada semget (). As permissões são fixadas em 0666 e o conjunto é criado se não existe ainda. Como declarado previamente, imediatamente depois da criação, o semáforo deve ser inicializado destrancando. A chamada semop () faz isto. Finalmente, a chamada semctl () remove o semáforo do sistema.

O código seguinte nos filhos permite o trancamento e destrancamento do semáforo:

...

#ifdef PROTECT

se (semop (g_sem_id, g_lock_sembuf, 1) == -1) {

fprintf(stderr, "A chamada semop () falhou, nao pode trancar semaforo!");

exit(1);

}

#endif

...

#ifdef PROTECT

if (semop (g_sem_id, g_unlock_sembuf, 1) == -1) {

fprintf(stderr, " A chamada semop () falhou, nao pode destrancar o semaforo !");

exit(1);

}

#endif

...

Note o #ifdef PROTECT ao redor da chamada semop () para permitir compilar a proteção antes e depois do código. Esta é uma prática comum na indústria para adicionar ou remover código baseado em opções de compilação.

Note o motivo pelo qual o programa acima pode violar a exclusão mútua, analisando duas linhas de código:

...

tmp_index = *g_shm_addr;

...

*g_shm_addr = tmp_index + i;

...

A primeira linha estabelece a leitura do índice atual a partir do segmento de memória compartilhada e o armazena em uma variável local. A segunda linha, algum tempo depois, estabelece a escrita do novo índice de volta à localização da memória compartilhada.

Exclusão mútua pode ser violada quando um processo lê o índice da memória compartilhada antes de um processo que o leu anteriormente acabe a sua operação de atualização do novo índice. Quando isto acontece, ambos os processos têm o mesmo valor de índice e ambos os processos escrevem as mesmas letras na tela. Olhe o resultado para verificar isto. Os semáforos asseguram que dois processos não acessam o recurso crítico ao mesmo tempo.

4. Resultado

Cada experimento constitui uma atividade que precisa de ser completada através de duas tarefas básicas. A primeira se refere à compilação e entendimento de um programa exemplo que trata de assuntos relacionados com aqueles cobertos em sala de aula e na teoria. A segunda se refere à implementação baseada no exemplo.

Este experimento deve ser acompanhado de um relatório com as seguintes partes obrigatórias:

Introdução, indicando, em não mais do que 20 linhas, quais os objetivos do experimento;

Resultados da execução do programa exemplo;

Resultados da execução do programa implementado;

Análise dos resultados, onde deve-se explicar o motivo da desigualdade de resultados;

Conclusão indicando o que foi aprendido com o experimento.

A entrega do experimento deve ocorrer através do envio de um e-mail "Encaminhando programa 4", de acordo com o cronograma previamente estabelecido. A data e hora limites correspondem à segunda-feira às 24:00, da semana marcada para entrega e apresentação. Anexos a esse e-mail devem constar:

os TRÊS programas fonte,

os TRÊS executáveis,

o relatório final do trabalho e

uma imagem do comando ls -l sobre os arquivos usados no experimento ao final do mesmo.

A falta de qualquer elemento no e-mail ou a perda da data de entrega implica na perda da nota correspondente. Somente duas exceções serão consideradas, o fechamento do laboratório durante o período disponibilizado para a realização do experimento, ou problema de doença avisado com antecedência mínima de dois dias antes da data da entrega.

Laboratório cheio, quedas de máquinas, falta de linha telefônica, problemas pessoais ou "blackouts" não serão aceitos como desculpas por atrasos. Por isso, recomenda-se fortemente que o início do trabalho ocorra o mais rapidamente possível.

Tarefas

A tarefa para este experimento é: primeiro, compilar duas vezes o programa exemplo, uma com proteção, outra sem proteção. Anotar os resultados das execuções dessas duas compilações.

Baseando-se no programa exemplo, escreva um programa para medir o tempo que o sistema operacional leva para trancar e destrancar um semáforo, da seguinte maneira:

Crie um conjunto de semáforos com um único semáforo.

Chame o relógio clock_gettime () para adquirir o valor da hora inicial.

Chame semop () para trancar o semáforo.

Chame semop () para destrancar o semáforo.

Chame clock_gettime (), para adquirir o valor da hora final.

Totalize as durações medidas e salve a maior e a menor delas.

Repita os cinco passos anteriores 500 vezes.

Calcule o tempo médio usando os dados coletados acima.

Execute o programa modificado dez vezes. Para cada execução varie a carga do sistema. Crie um quadro adequado para apresentar os resultados. Analise os resultados obtidos e explique as diferenças. O que significa este número médio? Para que serve esta medida?

5. Apresentação

O resultado do experimento será apresentado em sala de aula no dia de aula prática da semana marcada para a entrega, com a presença obrigatória de todos os alunos, de acordo com o cronograma previamente estabelecido.

Serão escolhidos dois alunos para a apresentação e discussão do resultado. A critério do professor pode, inclusive, ocorrer o convite a qualquer dos alunos não escolhidos para que façam essa apresentação.

Todos os alunos que completaram o experimento devem preparar para a apresentação:

Os programas exemplo e modificado,

A introdução,

Os resultados,

A análise dos resultados, e

A conclusão.

Durante a apresentação deverão ser respondidas perguntas do Professor e de colegas.