Projeto de MC104 - SISTEMAS OPERACIONAIS

Sincronização entre Processos: Mecanismo de Semáforos

 

Objetivos do Projeto

Desenvolver um programa com base no Programa Exemplo de modo a explorar a Sincronização entre Processos utilizando mecanismo de semáforos. Semáforos são geralmente utilizados quando processos necessitam do acesso exclusivo a um dado recurso. Dentre os objetivos deste projeto destacamos:

 

Aspectos Teóricos

A seguir são discutidos conceitos diretamente relacionados com o projeto e, deste modo, 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 de maneira exclusiva para impedir que outros processos tenham acesso ao mesmo simultaneamente. Em um sistema operacional multi-tarefa, a execução de processos de maneira intercalada ou paralela pode ocasionar situações imprevisíveis. Quando existe interação com o usuário e esta é a responsável pelo acesso e uso do recurso, fica mais difícil para um projetista de SO's predizer quando o processo irá acessar o recurso. Além disso, quando são considerados sistemas multi-processadores, dois processos executando em paralelo poderiam acessar um recurso simultaneamente. Com todos estes fatores, um método garantido para impedir que dois processos acessem um recurso crítico faz-se necessário.

A solução teórica para o problema do recurso crítico é simples: antes de entrar na região crítica de código, aquela em que o recurso é manipulado, o recurso é tornado indisponível ("locked"). Indisponibilizando ("locked") o recurso, nenhum outro processo pode entrar na sua região crítica. Uma vez que o processo acabe de ter sua região crítica executada, o mesmo disponibiliza ("unlocked") 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.

A solução do problema de acesso a um recurso crítico pode ser descrita como se segue:

  1. Processo executa uma Região de código NÃO Crítica
  2. Processo requisita "lock" para a "Região Crítica"
  3. Processo acessa a "Região Crítica"
  4. Processo devolve "lock" para a "Região Crítica"
  5. Processo continua com uma Região de código NÃO Crítica

A próxima questão é como implementar o "lock". Pode parecer que uma simples atribuição de valores funcione. Por exemplo, uma tentativa de implementação usando a linguagem C poderia ser:

  #define UNLOCKED 0
  #define LOCKED 1

  int lock_field = UNLOCKED; /* variavel global */

  ... Região de Código NÃO Crítica ...

  while( lock_filed == LOCKED )  /* Testa a Disponibilidade */
  sleep(1);   /* Se Indisponível, espera bloqueado um pouco */
  lock_field = LOCKED;   /* Estabelece a Indisponibilidade */

  ... REGIÃO CRÍTICA ...

  lock_field = UNLOCKED; /* disponibiliza o recurso */

  ... Região de Código NÃO Crítica ...

 

Exclusão Mútua

O código acima, entretanto, poderá não funcionar corretamente, permitindo a violação da exclusão mútua. Exclusão mútua é o princípio de que só um processo tem acesso à região crítica em um dado momento. Considere a seguinte situação:

Sempre que um processo está entre a fase de fazer o teste e a de indisponibilizar o 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 é aquela que é inteiramente completada antes que um processo perca a CPU. Implementando uma operação teste-e-atribua de forma atômica em software é uma tarefa difícil. Até existem algoritmos para isto, mas são grandes e lentos. Uma operação teste-e-atribua atômica é tipicamente implementada ou por uma instrução de processador de máquina (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.

 

Mecanismo de 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 dois tipos de operação sobre ele: trancando e destrancando a execução de instruções (p. ex., operações UP e DOWN, P e V). As operações sobre um semáforo são atômicas.

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 mensagems, 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.

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

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, reveja os experimentos anteriores.

Semáforos no System V são agrupados em conjuntos. 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 ao Projeto #3. NO_OF_SEMS é o número de semáforos no conjunto, ou seja, um no nosso caso (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];

  ... adquirindo 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 ser um pouco confuso, 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. Para este experimento, entretanto, abordaremos apenas operações envolvendo um único semáforo. 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 e 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 são muito mais cheias de detalhes que o explicado aqui. O manual lhe dará uma explicação completa.

Como dito anteriormente, "semctl(...)" é usado para remover um conjunto de semáforos. Como a chamada para "semctl(...)" é semelhante às outras chamadas IPC "ctl", também não será explicada em detalhes aqui.

É importante notar que o valor default 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 semaforo deve ser destrancado, para poder ser usado como mecanismo para exclusão mútua. Isto pode parecer estranho, mas é o modo como os semáforos são implementados.

 

Entendendo o Programa Exemplo

O programa exemplo demonstra como podem ser usados semáforos para proteger recursos compartilhados. No programa exemplo, o recurso compartilhado é uma string de caracteres que é exibida na tela e no qual vários processos tentarão colocar letras do alfabeto cooperativamente de maneira correta. 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.

O programa é similar aos programas vistos nos experimentos anteriores. Um único processo pai inicia vários processos filhos. O pai realiza a inicialização e o fechamento, enquanto os filhos realizam o trabalho. O Processo Pai segue o algoritmo:

Os Processos Filhos usam o seguinte algoritmo:

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 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ
  abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ
  abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ
  abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ
  abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ
  abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ
  abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ
  abcdefghijklmnopqrstuvwxyz 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ

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 cada. Estas sã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 na função main( ) do 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 (IPC_CREAT). Como declarado previamente, imediatamente depois da criação, o semáforo deve ser inicializado, para que possa ser destrancado. 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
  if( 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 lê o índice atual a partir do segmento de memória compartilhada e o armazena em uma variável local. A segunda linha, algum tempo depois, escreve o 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.

 

Descrição do Projeto

Cada projeto constitui uma atividade que precisa ser completada através de duas tarefas básicas. A primeira se refere à compilação e entendimento do programa exemplo que trata de assuntos cobertos em sala de aula e na teoria. A segunda se refere à implementação de uma modificação sobre o exemplo e/ou a geração de um novo código fonte.

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 nos trechos de código que manipulam semáforos e segmento de memória compartilhada do programa exemplo, escreva um programa para resolver o problema descrito abaixo.

Coloque instruções de saída em tela nos processos usuários T1, T2 e T3 de forma a acompanhar em que etapa cada um deles está. Execute o programa gerado várias vezes. Para cada execução varie o número de processos do tipo T1, T2 e T3. Crie um quadro adequado para apresentar os resultados. Analise os resultados obtidos e conclua com o que conseguiu assimilar deste experimento.

 


Luís Fernando Faina - faina@facom.ufu.br
Last modified: Wed Sep 13 18:34:53 2006