Visit Our UNIX and Linux User Community


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


 
Thread Tools Search this Thread
Top Forums Programming why the implementatoin of Bakery algorithm in ANSI C does not work in ANSI C
# 1  
Old 08-25-2010
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))

ThanksSmilie
# 2  
Old 08-25-2010
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 03:37 PM..
This User Gave Thanks to Corona688 For This Post:
# 3  
Old 08-25-2010
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

Previous Thread | Next Thread
Test Your Knowledge in Computers #291
Difficulty: Easy
In August 2016, the United States government announced a new federal source-code policy. This policy mandates that at least 50% of custom source code developed by or for any agency of the federal government must be released as open-source software (OSS).
True or False?

10 More Discussions You Might Find Interesting

1. Programming

C fdopen with and without -ansi

I have very little experience with gcc compilation under different environments, so please bear with me. I carried over 20 years old project into Ubuntu 18.04, it has old style K&R parameters, no function declarations to speak of, many functions without return are not declared void, and on and... (8 Replies)
Discussion started by: migurus
8 Replies

2. HP-UX

HP-UX ansi c precompiler

Hi, How can i find which ansi c precompiler are installed on my hp-ux b11.23 itanuim machine ? Thanks (3 Replies)
Discussion started by: yoavbe
3 Replies

3. HP-UX

Unix_ANSI to PC-ANSI

I want to convert a file from Unix-ANSI to PC-ANSI format. How can i achieve that? (0 Replies)
Discussion started by: ssmallya
0 Replies

4. Shell Programming and Scripting

Convert file from Unix - ANSI to PC - ANSI

Hi, I am creating a file in Unix using a shell script. The file is getting created in the Unix - ANSI format. My requirement is to convert it to the PC - ANSI format. Can anyone tell me how to do this? Thanks, Sunil (0 Replies)
Discussion started by: ssmallya
0 Replies

5. Programming

hint on ansi c

I am a student. And need help on following program. I want to make a c program. I have to scan a sentence and I have to interchange a word from that sentence. Example: Scan the sentence is " Drilling machine and Milling machine " . Replace the word "machine" by "operation". And output should... (2 Replies)
Discussion started by: dhaval chevli
2 Replies

6. HP-UX

ANSI / C Compiler for HP-UX 11.11

Good Day I downloaded Server Evaluation copy of C/ANSI compiler, but when I try to compile a file with it, it gives me following error - (for HP-UX 11.11 v1 PA-RISC) Internal Error: Codeword file /opt/ansic/newconfig/ansic.cwd missing or empty. Detailed Errors are as follows Internal... (3 Replies)
Discussion started by: shawnbishop
3 Replies

7. HP-UX

ansi problem

Hi! Can anyone help me with the problem i am having. Im new to hpux and i am trying to set up the programs i use. One such program is the irc client BitchX, ive ran it on several pc/sun boxes with no problems. On my c360 with an fx6 card and a eizo f56 17in monitor (1024x768 85hz vesa) the ansi... (0 Replies)
Discussion started by: Lewis
0 Replies

8. Programming

ANSI C vs POSIX

can somebody explain about the ANSI C vs POSIX. say i was using open and fopen, i know that open is POSIX, and fopen is ANSI C. i read that that POSIX is a system call and ANSI C is like a standard library function. wouldn't the fopen function has to call on open function anyway to open any kind... (2 Replies)
Discussion started by: bb00y
2 Replies

9. Programming

Ansi C

Dear All, I have to develope some C functions in Unix for a Magic program. The original MSE code which compiles the attached C program uses a +z option, but the cc compiler don't know this. The complete command in the compiler script is 'cc -c -Aa +z myfile.c'. The warning message is 'The -z... (4 Replies)
Discussion started by: Frankie
4 Replies

10. Programming

K&R vs. ANSI

To anyone that can answer this: Are the differences great between the ANSI and K&R standard? What are some of the major differences between them?? -REM (1 Reply)
Discussion started by: REM
1 Replies

Featured Tech Videos