Thread: Peterson's Algorithm on Producer/Single Consumer Question

  1. #1
    Registered User
    Join Date
    Dec 2015
    Posts
    112

    Peterson's Algorithm on Producer/Single Consumer Question

    I'm trying to make some code I've written run faster. I have a single produer and single consumer at the moment. I am using semafores and mutexes to control the critical sections. I have been reading and this does take quite a bit of overhead.

    I stumbled across this from wikipedia, https://en.wikipedia.org/wiki/Peterson%27s_algorithm.

    Has anyone used it before? I read some conflicting things like C99 can't implement a full peterson lock. Once I get a better idea I'll post some code.

    Do the while loops have any sort of Sleep or Delay? Or do they run as fast as they can for a short duration.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,625
    > Has anyone used it before?
    Yes.

    > I read some conflicting things like C99 can't implement a full peterson lock.
    Where?

    > Once I get a better idea I'll post some code.
    The algorithm is simple, why not just try it?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Did you read the "Note" on the wiki article?

    A bounded SPSC queue isn't that hard once you understand the instructions. A bounded MPMC queue isn't that bad either - if you know where to look: Bounded MPMC queue - 1024cores

    gg

  4. #4
    Registered User
    Join Date
    Dec 2015
    Posts
    112
    I gave this a try on this very simple example. From what I can tell, the mutex version might even be slightly faster. Did I implement this right and is this too simple of an example to really test this out on?

    Code:
    #include <windows.h>#include <stdio.h>
    #include <stdbool.h>
    #include <time.h>
    
    
    #ifdef MUTEX_FLAG
    HANDLE ghMutex;
    #else
    bool flag[2] = { false, false };
    int turn;
    #endif
    
    
    DWORD WINAPI ThreadRoutine1(LPVOID lpArg)
    {
        int i = 0;
        while (i<100)
        {
    #ifdef MUTEX_FLAG
            WaitForSingleObject(
                ghMutex,    // handle to mutex
                INFINITE);  // no time-out interval
    #else
            flag[0] = true;
            turn = 1;
            while (flag[1] && turn == 1)
            {
                #ifdef LOOP_DELAY
                    Sleep(1);
                #endif
            }
    #endif // MUTEX_FLAG
            // critical section
            printf("Thread1 i = %d\n", --*(int *)lpArg);
            // end of critical section
    
    
    #ifdef MUTEX_FLAG
            ReleaseMutex(ghMutex);
    #else
            flag[0] = false;
    #endif
            i++;
        }
        return NULL;
    }
    
    
    DWORD WINAPI ThreadRoutine2(LPVOID lpArg)
    {
        int i = 0;
        while (i<100)
        {
    #ifdef MUTEX_FLAG
            WaitForSingleObject(
                ghMutex,    // handle to mutex
                INFINITE);  // no time-out interval
    #else
            flag[1] = true;
            turn = 0;
            while (flag[0] && turn == 0)
            {
                #ifdef LOOP_DELAY
                    Sleep(1);
                #endif    
            }
    #endif
            // critical section
            printf("Thread2 i = %d\n", ++*(int *)lpArg);
            // end of critical section
    #ifdef MUTEX_FLAG
            ReleaseMutex(ghMutex);
    #else
            flag[1] = false;
    #endif
            i++;
        }
        return NULL;
    }
    
    
    int main()
    {
        int lpArgPtr;
        HANDLE hHandles[2];
        DWORD ThreadId;
        clock_t t0;
    
    
        t0 = clock();
        lpArgPtr = 10;
    
    
    #ifdef MUTEX_FLAG
        ghMutex = CreateMutex(
            NULL,              // default security attributes
            FALSE,             // initially not owned
            NULL);             // unnamed mutex
    
    
        if (ghMutex == NULL)
        {
            printf("CreateMutex error: %d\n", GetLastError());
            return 1;
        }
    #endif
    
    
        hHandles[0] = CreateThread(NULL, 0, ThreadRoutine1, &lpArgPtr, 0, &ThreadId);
        if (hHandles[0] == NULL) {
            fprintf(stderr, "Could not create Thread\n");
            exit(0);
        }
        else 
            printf("Thread %d was created\n", ThreadId);
    
    
        hHandles[1] = CreateThread(NULL, 0, ThreadRoutine2, &lpArgPtr, 0, &ThreadId);
        if (hHandles[1] == NULL) {
            fprintf(stderr, "Could not create Thread\n");
            exit(0);
        }
        else
            printf("Thread %d was created\n", ThreadId);
        
    
    
        for (int i = 0; i < 2; i++) 
        {
            WaitForSingleObject(hHandles[i], INFINITE);
        }
    #ifdef MUTEX_FLAG
        CloseHandle(ghMutex);
    #endif
    
    
        printf("program runtime %.4f\n", 1.0 * (clock() - t0) / CLOCKS_PER_SEC);
    
    
        system("Pause");
    
    
        return 0;
    }

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Forget about Peterson's. You need to use proper synchronization at the hardware level - ie atomic instruction intrinsics provided by your compiler. Otherwise, you'll just get burned either by the compiler or the hardware (or both).

    gg

  6. #6
    Registered User
    Join Date
    Dec 2015
    Posts
    112
    Quote Originally Posted by Codeplug View Post
    Forget about Peterson's. You need to use proper synchronization at the hardware level - ie atomic instruction intrinsics provided by your compiler. Otherwise, you'll just get burned either by the compiler or the hardware (or both).

    gg
    Thanks for the reply.

    First question, with mutex am I guranteed not to have any issues with two threads writing the same memory at the same time?

    Two, Are the two variables I need to worry about with atomic instructions turn and lpArgPtr?

    This article has proven to be helpful. Am I searching for a C99 solution on a windows 7 machine.

  7. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Yes, a mutex will provide mutually exclusive access to a resource. On Windows, you should be using a CriticalSection instead. A Windows Mutex is used when multiple process's need to synchronize with each other.

    When two or more threads access the same memory location, and at least one of them writes to that location, then you must provide synchronization.

    >> I'm trying to make some code I've written run faster.
    Let us help with that by explaining or showing some of your code. Rolling your own synchronization is going to the far extreme of trying to achieve that goal. It's also very difficult to get right.

    gg

  8. #8
    Registered User
    Join Date
    Dec 2015
    Posts
    112
    I'm going to look at this a different way. If one thread only produces and the other only consumes do I only need to worry that the compiler doesn't do any optimization to reorder instructions?

  9. #9
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    You always have to worry about compiler and hardware re-ordering.

    First, why don't you try out the queue_MT class in this post: ReadDirectoryChangesW question

    Be sure to re-code your consumer to use the dequeue_all() interface. See if you get satisfactory speed up with that.

    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Producer-Consumer problem
    By mistereff in forum C++ Programming
    Replies: 12
    Last Post: 11-29-2012, 04:09 PM
  2. Producer/Consumer Problem
    By AvengedGoat in forum C++ Programming
    Replies: 5
    Last Post: 03-21-2010, 12:33 PM
  3. producer consumer deadlock
    By strider1974 in forum C Programming
    Replies: 11
    Last Post: 08-17-2009, 10:47 AM
  4. producer / consumer question
    By pheres in forum C++ Programming
    Replies: 8
    Last Post: 08-02-2007, 05:55 PM
  5. Consumer - Producer
    By MethodMan in forum C Programming
    Replies: 0
    Last Post: 04-18-2003, 07:14 PM