Implementar semáforo de Dijkstra em C

pakuista · 18 de junho de 2010

Pessoal, estou com um problema do tamanho do mundo aqui, eu tenho que fazer um trabalho sobre o semáforo de Dijkstra em sistemas operacionais. Eu achei um código que na internet mais sempre da erro nos pacotes que tento importar(desculpa a linguagem orientada a objeto, eu to acostumado a programar em JAVA e o professor força o cara a implementar em C, sei não viu). Olha aqui o exemplo do código pessoal:


int sem_create(key_t key, int initval)  
{
     int semid ;

     union semun {
          int val ;
          struct semid_ds *buf ;
          ushort array[1] ;
     } arg_ctl ;

     semid = semget(ftok("dijkstra.h",key),1,IPC_CREAT|IPC_EXCL|0666) ;
     if (semid == -1) {
          semid = semget(ftok("dijkstra.h",key),1,0666) ; 
          if (semid == -1) {
               perror("Erro semget()") ;
               exit(1) ;
          }
     }

     arg_ctl.val = initval ;
     if (semctl(semid,0,SETVAL,arg_ctl) == -1) {
          perror("Erro inicializacao semaforo") ;
          exit(1) ;
     }
     return(semid) ;
}

void P(int semid) 
{
     struct sembuf sempar[1];
     sempar[0].sem_num = 0 ;
     sempar[0].sem_op = -1 ;
     sempar[0].sem_flg = SEM_UNDO ;
     if (semop(semid, sempar, 1) == -1)
          perror("Erro operacao P") ;
}

void V(int semid)
{
     struct sembuf sempar[1];
     sempar[0].sem_num = 0 ;
     sempar[0].sem_op =  1 ;
     sempar[0].sem_flg = SEM_UNDO ;
     if (semop(semid, sempar, 1) == -1)
          perror("Erro operacao V") ;
}

void sem_delete(int semid) 
{
     if (semctl(semid,0,IPC_RMID,0) == -1)
       perror("Erro na destruicao do semaforo");
}

No mesmo local que achei o código achei o código de teste do semáforo:


#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <stdio.h>
#include <unistd.h>
#include "dijkstra.h"

#define KEY 456

int main()
{
  int sem ;
  sem = sem_create(KEY,1) ;
  printf("\nCriacao do semaforo do identificador %d\n",sem) ;
  // P(sem);
 if (fork() == 0) { 
     printf("\tEu sou o FILHO e fazer P sobre o semaforo\n");
     P(sem);
     printf("\tEu sou o FILHO e vou dormir 10 segundos...\n") ;
     sleep(10) ;
     printf("\tEu sou o FILHO e vou fazer V sobre o semaforo\n") ;
     V(sem) ;
      sleep(1);
   }
   else {
     printf("Eu sou o PAI e vou dormir 2 segundos...\n") ;
     sleep(2);
     printf("Eu sou o PAI e vou me bloquear fazendo P sobre o semaforo\n");
     P(sem) ;
     printf("Eu sou o PAI e acabei de me desbloquear\n") ;
     sem_delete(sem) ;
     printf("Eu sou o PAI e vou acabar o processamento\n\n");
   }
   exit(0);
}

O que pode esta dando errado na importacção dos pacotes? Eu coloquei esses dois códigos numa mesma classe, pode ser assim? O erro que esta dando é: "sys/ipc.h no such file or directory. "

Pessoal, toda ajuda é bem vinda.

pakuista · 19 de junho de 2010

Nada gente? To perdido nesse trabalho!!

Pessoal, deixa e dar mais esclarecimentos que vim perceber agora.

Olha pessoal, o primeiro código o cara chamou de "dijkstra.h". o que vem a ser um ".h"? Biblioteca?

.

No segundo código podemos ver que o cara inclui o dijkstra.h fazendo #include "dijkstra.h" -- Ou seja, é uma biblioteca mesmo? Como faço para pegar o primeiro código e tranformar em .h?

pakuista · 19 de junho de 2010

Pessoal, estou com o seguinte código para gerar um .h no dev c++


int sem_create(key_t key, int initval)  
{
     int semid ;

     union semun {
          int val ;
          struct semid_ds *buf ;
          ushort array[1] ;
     } arg_ctl ;

     semid = semget(ftok("dijkstra.h",key),1,IPC_CREAT|IPC_EXCL|0666) ;
     if (semid == -1) {
          semid = semget(ftok("dijkstra.h",key),1,0666) ; 
          if (semid == -1) {
               perror("Erro semget()") ;
               exit(1) ;
          }
     }

     arg_ctl.val = initval ;
     if (semctl(semid,0,SETVAL,arg_ctl) == -1) {
          perror("Erro inicializacao semaforo") ;
          exit(1) ;
     }
     return(semid) ;
}

void P(int semid) 
{
     struct sembuf sempar[1];
     sempar[0].sem_num = 0 ;
     sempar[0].sem_op = -1 ;
     sempar[0].sem_flg = SEM_UNDO ;
     if (semop(semid, sempar, 1) == -1)
          perror("Erro operacao P") ;
}

void V(int semid)
{
     struct sembuf sempar[1];
     sempar[0].sem_num = 0 ;
     sempar[0].sem_op =  1 ;
     sempar[0].sem_flg = SEM_UNDO ;
     if (semop(semid, sempar, 1) == -1)
          perror("Erro operacao V") ;
}

void sem_delete(int semid) 
{
     if (semctl(semid,0,IPC_RMID,0) == -1)
       perror("Erro na destruicao do semaforo");
}

Como faço para gerar o .h? .h é um header certo? Depois de criar o .h como faço para incluir essa biblioteca no dev c++?

Alguém poderia fazer isto pra mim, ta osso esse trabalho, tenho que mostrar para o professor de SO próxima semana. Fods

Até mais pessoal..

ScreenBlack · 20 de junho de 2010

procurei nas bibliotecas quem vem no MinGW e no Microsoft Visual C++ 2008, e em ambos não encontrei essa biblioteca.

Imagino que ela exista apenas um sistemas Unix, e no Windows, o tratamento é diferente.

Talvez esse link te ajude:

http://www.ibm.com/developerworks/systems/library/es-win32linux-sem.html

Em C, dividimos o código em dois arquivos diferentes. Em um colocamos as estruturas, assinatura de funções e qualquer informação na qual queiramos que os próximos programadores tenham acesso a informação (Ex: #define, typedef, ...). Esse arquivo chamamos de cabeçalho, e nomeamos com a extensão .h.

No outro, colocaremos as rotinas completas, o núcleo do processamento. Esse arquivo chamamos de código, e nomeamos com .c.

Ambos os arquivos são chamados de biblioteca, e no caso do arquivo .c, ele será compilado, gerando um .a, .o, .so, .dll, ... (depende do sistema e do tipo que quer criar).

Assim, tendo um arquivo .h e um outro compilado, faremos o "include" do .h no código onde chamaremos as funções da biblioteca, e no momento de compilarmos, o arquivo onde efetivamente fará a "linkagem" será lido pelo compilador.

pakuista · 20 de junho de 2010

Então não vou conseguir incluir os headers <sys/ipc.h> e <sys/sem.h> utilizando windows?

Você falou sobre o .h e .c, como faço para com o primeiro códico mostrei gerar um .h?

Eu só fiz renomear ele para .h e coloquei na past include, o problema é que quando dou um include nele no segundo código e tento compilar acusa muitos erros no dijkstra.h e como já disse, acusa também o problema do <sys/ipc.h><sys/sem.h> .

ScreenBlack · 20 de junho de 2010

No windows, a bibliote utilizada é "windows.h".

Segue exemplo do site MSDN:

http://msdn.microsoft.com/en-us/library/ms686946%28VS.85%29.aspx

Outro link que encontrei:

http://www.experts-exchange.com/Programming/Languages/C/Q_20787752.html

pakuista · 21 de junho de 2010

O exemplo que tu me mostrou usa semáforos para limitar o numero de threads que podem acessar uma certa tarefa né?

Assim, já que no windows usa o windows.h, eu posso tirar o <sys/ipc.h> e <sys/sem.h> e importar só o windows.h né?

Agora ta dando erro só no dijkstra.h.

Tipo, eu não sei o procedimento para criar um arquivo .h, mas eu to fazendo assim, criando um projeto: "File" > "New" > "Project" > "Console Application", aí coloquei o código abaixo e compilei. O problema é que esse código tem muitos erros, eu não consigo compilar de jeito algum. O segundo código não tem erro, o unico erro que da é do #include "dijkstra.h" pois não tenho ele ainda. Ta barra aqui. Acho que vou ter que encontrar outro código. Me diz, o código que tu me enviou aí no primeiro link, será que eu posso usar ele para mostrar o funcionamento de um semáforo?


int sem_create(key_t key, int initval)  
{
     int semid ;

     union semun {
          int val ;
          struct semid_ds *buf ;
          ushort array[1] ;
     } arg_ctl ;

     semid = semget(ftok("dijkstra.h",key),1,IPC_CREAT|IPC_EXCL|0666) ;
     if (semid == -1) {
          semid = semget(ftok("dijkstra.h",key),1,0666) ; 
          if (semid == -1) {
               perror("Erro semget()") ;
               exit(1) ;
          }
     }

     arg_ctl.val = initval ;
     if (semctl(semid,0,SETVAL,arg_ctl) == -1) {
          perror("Erro inicializacao semaforo") ;
          exit(1) ;
     }
     return(semid) ;
}

void P(int semid) 
{
     struct sembuf sempar[1];
     sempar[0].sem_num = 0 ;
     sempar[0].sem_op = -1 ;
     sempar[0].sem_flg = SEM_UNDO ;
     if (semop(semid, sempar, 1) == -1)
          perror("Erro operacao P") ;
}

void V(int semid)
{
     struct sembuf sempar[1];
     sempar[0].sem_num = 0 ;
     sempar[0].sem_op =  1 ;
     sempar[0].sem_flg = SEM_UNDO ;
     if (semop(semid, sempar, 1) == -1)
          perror("Erro operacao V") ;
}

void sem_delete(int semid) 
{
     if (semctl(semid,0,IPC_RMID,0) == -1)
       perror("Erro na destruicao do semaforo");
}

edit: Cara, coloquei o código do primeiro link que tu me mandou e compilou direitinho a não ser por um warning "return type of main is not int". Mas um warning não impede de compilar né. Bom, o problema é que quando vou executar o código aparece uma mensagem dizendo que o projeto não está compilado.

Sabe o que pode está acontecendo?

ScreenBlack · 21 de junho de 2010

Sobre a mensagem "return type of main is not int", você precisa retornar um int na função main.

Exemplo:


int main(void)
{
[ ... ]
    return 0;
}

Sobre o projeto não estar compilado, isso é questão da ferramenta que você está utilizando, no caso o Dev-C++. Essa ferramenta já está defasada, faz mais de 5 anos que não há atualizações. Costumo utilizar o Code::Blocks, é simples, leve e funcional.

pakuista · 21 de junho de 2010

Mas sabe o que é que eu acho estranho? A função main é declarada como void, como ela vai retornar um int se é void? o erro que relatei parou de acontecer quando fechei e abri de novo o dev-cpp. Bom, agora compilou normalmente e só deu esse warning. Quando executo não acontece nada, aparece só uma tela preta e desaparece de novo. 0o

ScreenBlack · 21 de junho de 2010

Tente ativar o debugger pra ver o que está acontecendo.

Ou então, poste o código para eu poder ajudar.

pakuista · 21 de junho de 2010

Vamos lá, o código que estou testando é esse aqui:


#include <windows.h>
#include <stdio.h>
#define MAX_SEM_COUNT 10
#define THREADCOUNT 12

HANDLE ghSemaphore;

DWORD WINAPI ThreadProc( LPVOID );

void main()
{
    HANDLE aThread[THREADCOUNT];
    DWORD ThreadID;
    int i;

    // Create a semaphore with initial and max counts of MAX_SEM_COUNT

    ghSemaphore = CreateSemaphore( 
        NULL,           // default security attributes
        MAX_SEM_COUNT,  // initial count
        MAX_SEM_COUNT,  // maximum count
        NULL);          // unnamed semaphore

    if (ghSemaphore == NULL) 
    {
        printf("CreateSemaphore error: %d\n", GetLastError());
        return;
    }

    // Create worker threads

    for( i=0; i < THREADCOUNT; i++ )
    {
        aThread[i] = CreateThread( 
                     NULL,       // default security attributes
                     0,          // default stack size
                     (LPTHREAD_START_ROUTINE) ThreadProc, 
                     NULL,       // no thread function arguments
                     0,          // default creation flags
                     &ThreadID); // receive thread identifier

        if( aThread[i] == NULL )
        {
            printf("CreateThread error: %d\n", GetLastError());
            return;
        }
    }

    // Wait for all threads to terminate

    WaitForMultipleObjects(THREADCOUNT, aThread, TRUE, INFINITE);

    // Close thread and semaphore handles

    for( i=0; i < THREADCOUNT; i++ )
        CloseHandle(aThread[i]);

    CloseHandle(ghSemaphore);
}

DWORD WINAPI ThreadProc( LPVOID lpParam )
{
    DWORD dwWaitResult; 
    BOOL bContinue=TRUE;

    while(bContinue)
    {
        // Try to enter the semaphore gate.

        dwWaitResult = WaitForSingleObject( 
            ghSemaphore,   // handle to semaphore
            0L);           // zero-second time-out interval

        switch (dwWaitResult) 
        { 
            // The semaphore object was signaled.
            case WAIT_OBJECT_0: 
                // TODO: Perform task
                printf("Thread %d: wait succeeded\n", GetCurrentThreadId());
                bContinue=FALSE;            

                // Simulate thread spending time on task
                Sleep(5);

                // Release the semaphore when task is finished

                if (!ReleaseSemaphore( 
                        ghSemaphore,  // handle to semaphore
                        1,            // increase count by one
                        NULL) )       // not interested in previous count
                {
                    printf("ReleaseSemaphore error: %d\n", GetLastError());
                }
                break; 

            // The semaphore was nonsignaled, so a time-out occurred.
            case WAIT_TIMEOUT: 
                printf("Thread %d: wait timed out\n", GetCurrentThreadId());
                break; 
        }
    }
}

Na hora que compilo o único problema que da é um warning dizendo assim: "Return type of main is not int" e tem outra mensagem que creio que não seja nada, ela dia assim "In fuction 'main' "

Bom, o que eu achei estranho desse warning é que a funçao é void e não precisa de return.

Na hora que executo a função aparece uma tela preta(um prompt) e em fração de segundos ela desaparece.

dontpanic · 21 de junho de 2010

A função correta deveria ser int.

int main() {

return 0;

}

pakuista · 22 de junho de 2010

Pronto, coloquei aqui o int ao invés de void, sumiu o warning.

Mas assim, quando executo continua aquilo que falei, aparece muito rápido o prompt e some. 0o

dontpanic · 22 de junho de 2010

Iniciar -> Programas -> Acessorios -> Prompt

Se o seu programa estiver, por exemplo, na pasta "C:\Codigo\c", você digita:

cd c:\codigo\c

Depois é só digitar o nome do programa.

22 de junho de 2010

coloca no final da função main:

system("pause");

Vai aparecer uma mensagem "Pressione qualquer tecla para continuar..."

Assim a tela não some direto.


int main(void)
{
....................................................
// Close thread and semaphore handles

    for( i=0; i < THREADCOUNT; i++ )
        CloseHandle(aThread[i]);

    CloseHandle(ghSemaphore);
    system("pause");
}

pakuista · 23 de junho de 2010

Bom, eu testei o primeiro código que mostrei aqui no linux e rodou direitinho. Vou apresentar ele mesmo, mas como tem algumas passagens no código que não sei explicar vou precisar da ajuda de vocês.

Bom, nesse código abaixo:


if (fork() == 0) { 
     printf("\tEu sou o FILHO e fazer P sobre o semaforo\n");
     P(sem);
     printf("\tEu sou o FILHO e vou dormir 10 segundos...\n") ;
     sleep(10) ;
     printf("\tEu sou o FILHO e vou fazer V sobre o semaforo\n") ;
     V(sem) ;
      sleep(1);
   }

Quando é feito


if (fork() == 0)

o que quer dizer, sei que fork() é uma chamada de sistema que cria um processo filho, mas quando ele faz fork() == 0 ela ta comparando o que? Ele quer saber se não foi gerado nenhum processo?

Opa, Opa, dei uma olhadinha e vi o que ele quis dizer com esse if(fork()==0), o fork() retorna 0 para o processo filho quando ele é criado e retorna o id do processo filho para o processo pai, e retorna -1 se der erro.

Essa dúvida já foi, deixa eu dizer outra aqui, no código abaixo:


union semun {
          int val ;
          struct semid_ds *buf ;
          ushort array[1] ;
     } arg_ctl ;

o que é Union? È um tipo de estrutura de dados? E no final tem arg_ctl, o que vem a ser essa parte também?

ScreenBlack · 23 de junho de 2010

"union" é o mesmo principio do "struct", a diferença é que as variáveis compartilham da mesma memória alocada. e o arg_ctl é o nome dado para esse "union", assim como acontece no "struct".

o tipo de strutura "union" pode ser bem perigosa, quando você sobrescreve uma variável, estará sobrescrevendo na verdade a memória compartilhada para essa estrutura.

Exemplo:


#include <stdlib.h>
#include <stdio.h>

typedef union
{
        int valor;
        char string[5];
} TUnion;

int main( void )
{

        int i;
        TUnion teste; // Nao foi atribuido nenhum valor \
                      // para as variaveis da estrutura ainda

        for ( i = 0; i < 5; i++ )
                teste.string[i] = '\0'; // zera todo o vetor

        teste.valor = 70;
        printf("conteudo de string: %s\n", teste.string);
        printf("conteudo de valor: %d\n", teste.valor);

        return 0;

}

Como pode ver, zerei o vetor "string", atribui um valor para "valor", e este mesmo, foi mostrado como conteúdo de string (valor 70 em decimal é o "F" em ASCII).

pakuista · 23 de junho de 2010

Hum, agora sim entendi. Acho que para entender o código todo(pelo menos para explicar amanha na apresentaçã) só falta esse trecho:


semid = semget(ftok("dijkstra.h",key),1,IPC_CREAT|IPC_EXCL|0666) ;

Bom, sei que o semid é o id do semáforo e pelo nome acho que o semget deve ser alguma função que pega ou gera o id do semaforo, ou mesmo o semáforo. Mas o resto da trecho o que significa?

Se não souber não tem problema, eu digo para o professor que ele tem que aprender a abstrair.

Obrigado mesmo cara. Esta sendo de grande ajuda.

ScreenBlack · 23 de junho de 2010

Esse link explica sobre o semget, e que por sinal, é muita boa:

http://www.dca.ufrn.br/~adelardo/cursos/DCA409/node88.html

Sobre a função ftok, ela criará uma chave para o arquivo especificado.

pakuista · 24 de junho de 2010

Obrigado cara, ia perguntar outras coisas mas não vai dar tempo não, vou apresentar amanhã de manhã. Valeu mesmo pelas respostas.

JhOnE RoSsInI · 24 de junho de 2010

o erro esta na chave porque será?

#include <windows.h>
#include <stdio.h>

#define MAX_SEM_COUNT 10

#define THREADCOUNT 12

HANDLE ghSemaphore;

DWORD WINAPI ThreadProc( LPVOID );

void main()

{ <- o primeiro erro esta aqui

HANDLE aThread[THREADCOUNT];

DWORD ThreadID;

int i;

// Create a semaphore with initial and max counts of MAX_SEM_COUNT

ghSemaphore = CreateSemaphore(

NULL, // default security attributes

MAX_SEM_COUNT, // initial count

MAX_SEM_COUNT, // maximum count

NULL); // unnamed semaphore

if (ghSemaphore == NULL)

{

printf("CreateSemaphore error: %d\n", GetLastError());

return;

}

// Create worker threads

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

{

aThread = CreateThread(

NULL, // default security attributes

0, // default stack size

(LPTHREAD_START_ROUTINE) ThreadProc,

NULL, // no thread function arguments

0, // default creation flags

&ThreadID); // receive thread identifier

if( aThread == NULL )

{

printf("CreateThread error: %d\n", GetLastError());

return;

}

}

// Wait for all threads to terminate

WaitForMultipleObjects(THREADCOUNT, aThread, TRUE, INFINITE);

// Close thread and semaphore handles

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

CloseHandle(aThread);

CloseHandle(ghSemaphore);

}

DWORD WINAPI ThreadProc( LPVOID lpParam )

{

DWORD dwWaitResult;

BOOL bContinue=TRUE;

while(bContinue)

{

// Try to enter the semaphore gate.

dwWaitResult = WaitForSingleObject(

ghSemaphore, // handle to semaphore

0L); // zero-second time-out interval

switch (dwWaitResult)

{

// The semaphore object was signaled.

case WAIT_OBJECT_0:

// TODO: Perform task

printf("Thread %d: wait succeeded\n", GetCurrentThreadId());

bContinue=FALSE;

// Simulate thread spending time on task

Sleep(5);

// Release the semaphore when task is finished

if (!ReleaseSemaphore(

ghSemaphore, // handle to semaphore

1, // increase count by one

NULL) ) // not interested in previous count

{

printf("ReleaseSemaphore error: %d\n", GetLastError());

}

break;

// The semaphore was nonsignaled, so a time-out occurred.

case WAIT_TIMEOUT:

printf("Thread %d: wait timed out\n", GetCurrentThreadId());

break;

}

}

}