Unix/Linux Go Back    


Programming Post questions about C, C++, Java, SQL, and other programming languages here.

why the implementatoin of Bakery algorithm in ANSI C does not work in ANSI C

Programming


Tags
bakery algorithm

Closed    
 
Thread Tools Search this Thread Display Modes
    #1  
Old Unix and Linux 08-25-2010   -   Original Discussion by sehang
sehang's Unix or Linux Image
sehang sehang is offline
Registered User
 
Join Date: Aug 2010
Last Activity: 26 May 2011, 10:05 AM EDT
Location: Macau
Posts: 31
Thanks: 6
Thanked 0 Times in 0 Posts
why the implementatoin of Bakery algorithm in ANSI C does not work in ANSI C

I follow the description of wiki (Lamport's bakery algorithm - Wikipedia, the free encyclopedia), then implement that algorithm in C, but it doesn't work, Starving is still here, is the implementation worry?

Only print out:

Code:
Thread ID: 0 START!
Thread ID: 0 END!
Thread ID: 0 START!
Thread ID: 0 END!
.....


Code:
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define COUNT 2                                 /* Number of thread. */
static int Entering[ COUNT ], Number[ COUNT ];  /* Global variables for Lamport's bakery algorithm. */

int max ( int* arr ) {
    int i, max = arr[ 0 ];
    for ( i = 1 ; i < COUNT ; i++ )
        if ( Number[ i ] > max )
            return Number[ i ];
    return Number[ 0 ];
}


static void* T1 ( void* args ) {
    pthread_detach( pthread_self() );                   /* Guarantees that thread resources are deallocated upon return. */
    int i = 0, j;
    while ( 1 ) {
        /* Request to enter critical section. */
        Entering[ i ] = 1;
        Number[ i ] = 1 + max( Number );
        Entering[ i ] = 0;
        for ( j = 0 ; j < COUNT ; j++ ) {
            while ( Entering[ j ] ) {}
            while ( Number[ j ] != 0 && ( Number[ j ] <  Number[ i ] || ( Number[ j ] == Number[ i ] && j < i ) ) ) {}
        }

        /* Critical section. */
        printf( "Thread ID: %d START!\n", i );
        for ( j = 0 ; j < 0xFFFFFF ; j++ ) {}
        printf( "Thread ID: %d END!\n", i );

        /* End of critical section. */
        Number[ i ] = 0;
    }
    return NULL;
}

static void* T2 ( void* args ) {
    pthread_detach( pthread_self() );                   /* Guarantees that thread resources are deallocated upon return. */
    int i = 1, j;
    while ( 1 ) {
        /* Request to enter critical section. */
        Entering[ i ] = 1;
        Number[ i ] = 1 + max( Number );
        Entering[ i ] = 0;
        for ( j = 0 ; j < COUNT ; j++ ) {
            while ( Entering[ j ] ) {}
            while ( Number[ j ] != 0 && ( Number[ j ] <  Number[ i ] || ( Number[ j ] == Number[ i ] && j < i ) ) ) {}
        }

        /* Critical section. */
        printf( "Thread ID: %d START!\n", i );
        for ( j = 0 ; j < 0xFFFFFF ; j++ ) {}
        printf( "Thread ID: %d END!\n", i );

        /* End of critical section. */
        Number[ i ] = 0;
    }
    return NULL;
}

int main () {
    int i = 0;
    pthread_t t1;

    /* Initial Bakery algorithm. */
    for ( i = 0 ; i < COUNT ; i++ )
        Number[ i ] = Entering[ i ] = 0;

    /* Thread Creation. */
    if ( pthread_create( &t1, NULL, T1, NULL ) )
        exit( -1 );
    if ( pthread_create( &t1, NULL, T2, NULL ) )
        exit( -1 );

    /* Loop forever. */
    while ( 1 ) {}
    return EXIT_SUCCESS;
}

The pseudocode of Lamport's bakery algorithm

Code:
    // declaration and initial values of global variables
    Entering: array [1..NUM_THREADS] of bool = {false};
    Number: array [1..NUM_THREADS] of integer = {0};
    
 1  lock(integer i) {
 2      Entering[i] = true;
 3      Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
 4      Entering[i] = false;
 5      for (j = 1; j <= NUM_THREADS; j++) {
 6          // Wait until thread j receives its number:
 7          while (Entering[j]) { /* nothing */ }
 8          // Wait until all threads with smaller numbers or with the same
 9          // number, but with higher priority, finish their work:
10          while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
11              /* nothing */
12          }
13      }
14  }
15
16  unlock(integer i) {
17      Number[i] = 0;
18  }
19
20  Thread(integer i) {
21      while (true) {
22          lock(i);
23          // The critical section goes here...
24          unlock(i);
25          // non-critical section...
26      }
27  }

and

Code:
(a, b) < (c, d)

which is equivalent to:

Code:
(a < c) or ((a == c) and (b < d))

ThanksLinux
Sponsored Links
    #2  
Old Unix and Linux 08-25-2010   -   Original Discussion by sehang
Corona688's Unix or Linux Image
Corona688 Corona688 is offline Forum Staff  
Mead Rotor
 
Join Date: Aug 2005
Last Activity: 11 December 2017, 5:38 PM EST
Location: Saskatchewan
Posts: 22,546
Thanks: 1,159
Thanked 4,286 Times in 3,955 Posts
A few problems with writing it in C.

1) You're assuming variables are atomic. Sometimes they're not.

2) You're assuming different threads have access to the same memory/cache. In multicore systems, this isn't always true, "memory barriers" are needed to force cores to be consistent with each other when necessary.

3) The compiler makes certain assumptions about memory. Unless you tell it otherwise, it will assume a variable is not "magic" and won't change mysteriously when its not looking (which is precisely what you're doing with threads). You have to make a variable volatile(i.e. "volatile int i") if you're going to have threads competing over it this way.

So, writing the algorithm in raw ANSI C isn't recommended. You might be able to make this work in raw C on a single-core system, maybe, if you make the shared variables volatile. I think there's also some extensions in GNU gcc for explicit atomic operations.

Last edited by Corona688; 08-25-2010 at 02:37 PM..
The Following User Says Thank You to Corona688 For This Useful Post:
sehang (08-26-2010)
Sponsored Links
    #3  
Old Unix and Linux 08-25-2010   -   Original Discussion by sehang
sehang's Unix or Linux Image
sehang sehang is offline
Registered User
 
Join Date: Aug 2010
Last Activity: 26 May 2011, 10:05 AM EDT
Location: Macau
Posts: 31
Thanks: 6
Thanked 0 Times in 0 Posts
Thanks, I have solved my problem and I am reading the Atomic Builtins of GCC, I just post these links here, for those people who may have same problem.

Atomic Builtins - Using the GNU Compiler Collection (GCC)
Techie Stuff Atomic Operations
Sponsored Links
Closed

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Linux More UNIX and Linux Forum Topics You Might Find Helpful
Thread Thread Starter Forum Replies Last Post
Convert file from Unix - ANSI to PC - ANSI ssmallya Shell Programming and Scripting 0 02-05-2008 06:07 AM
hint on ansi c dhaval chevli Programming 2 06-15-2006 04:40 AM
ANSI C vs POSIX bb00y Programming 2 11-05-2002 09:20 AM
Ansi C Frankie Programming 4 11-23-2001 09:55 AM
K&R vs. ANSI REM Programming 1 06-08-2001 12:20 PM



All times are GMT -4. The time now is 11:47 AM.