Undefined behaviour pthread C

[imitheos]

Γκρρρ. Χειρότερος editor από αυτόν της αναβάθμισης του φόρουμ δεν υπάρχιε. Μου έφαγε ολόκληρο το μήνυμα. Πάμε άλλη μία φορά.

Edit: Επειδή το μήνυμα μου είναι άσκοπα μεγάλο, αλλάζω τον αριθμό νημάτων από 10 σε 4 για να είναι πιο εύκολα κατανοητό.

 

Αναφορά σε κείμενο

If  the  mutex is  already  locked  by  another thread, the calling thread shall block
until the mutex becomes available.
If a thread attempts to relock a mutex that it has
already  locked,  pthread_mutex_lock() shall behave as described in the
Relock column of the following table. If a thread attempts to unlock  a
mutex   that   it  has  not  locked  or  a  mutex  which  is  unlocked,
pthread_mutex_unlock() shall behave as described in the Unlock When Not
Owner column of the following table.

 

┌───────────┬────────────┬────────────────┬───────────────────────┐
  │Mutex Type │ Robustness │     Relock     │ Unlock When Not Owner │
  ├───────────┼────────────┼────────────────┼───────────────────────┤
  │NORMAL     │ non-robust │ deadlock       │ undefined behavior    │
  ├───────────┼────────────┼────────────────┼───────────────────────┤
  │NORMAL     │ robust     │ deadlock       │ error returned        │      
  ├───────────┼────────────┼────────────────┼───────────────────────┤
  │ERRORCHECK │ either     │ error returned │ error returned        │      
  ├───────────┼────────────┼────────────────┼───────────────────────┤
  │RECURSIVE  │ either     │ recursive      │ error returned        │      
  │           │            │ (see below)    │                       │      
  ├───────────┼────────────┼────────────────┼───────────────────────┤
  │DEFAULT    │ non-robust │ undefined      │ undefined behavior†   │
  │           │            │ behavior†      │                       │      
  ├───────────┼────────────┼────────────────┼───────────────────────┤
  │DEFAULT    │ robust     │ undefined      │ error returned        │      
  │           │            │ behavior†      │                       │      
  └───────────┴────────────┴────────────────┴───────────────────────┘

Όπως διαβάζεις, αν δεν αλλάξεις εσύ τα attributes ενός mutex, η μανίσια συμπεριφορά είναι  όταν ένα νήμα πάει να αποκτήσει ένα ήδη υπάρχον lock, να μπλοκάρει και να μην τρέχει οπότε δεν έχεις πρόβλημα. Ας δούμε ένα χαζό παράδειγμα.

#include <pthread.h>                                                            
#include <stdio.h>                                                              
                                                                                
struct thread_s {                                                               
    pthread_t id;                                                               
    int       i;                                                                
    unsigned int fact_res;                                                      
};                                                                              
                                                                                
pthread_mutex_t lock;                                                           
                                                                                
unsigned int fact(unsigned int i)                                               
{                                                                               
        if (i <= 1)                                                             
                return 1;                                                       
        return fact(i - 1) * i;                                                 
}                                                                               
                                                                                
void *thread_func(void *val)                                                    
{                                                                               
    struct thread_s *thread = val;                                              
    int err;                                                                    
                                                                                
    err = pthread_mutex_lock(&lock);                                            
    printf("Locking returned %d in thread %d\n", err, thread->i);               
    printf("Running thread %d\n", thread->i);                                   
    err = pthread_mutex_unlock(&lock);                                          
    printf("Unlocking returned %d in thread %d\n", err, thread->i);             
                                                                                
    thread->fact_res = fact(thread->i);                                         
                                                                                
    return NULL;                                                                
}                                                                               
                                                                                
int main(void)                                                                  
{                                                                               
    struct thread_s threads[4];                                                
    int i;                                                                      
    int err;                                                                    
                                                                                
                                                                                
    for (i = 0; i < 4; i++) {                                                  
            threads[i].i = i;                                                   
            err = pthread_create(&threads[i].id, NULL, &thread_func, &threads[i]);
    }                                                                           
                                                                                
    for (i = 0; i < 4; i++) {                                                  
            err = pthread_join(threads[i].id, NULL);                            
            printf("Joined with finished thread %d: Factorial(%d) = %u\n", i, i, threads[i].fact_res);
    }                                                                           
                                                                                
    return 0;                                                                   
}

% ./tmp 
Locking returned 0 in thread 0
Running thread 0
Unlocking returned 0 in thread 0
Locking returned 0 in thread 1
Running thread 1
Unlocking returned 0 in thread 1
Locking returned 0 in thread 2
Running thread 2
Unlocking returned 0 in thread 2
Locking returned 0 in thread 3
Running thread 3
Unlocking returned 0 in thread 3
Joined with finished thread 0: Factorial(0) = 1
Joined with finished thread 1: Factorial(1) = 1
Joined with finished thread 2: Factorial(2) = 2
Joined with finished thread 3: Factorial(3) = 6

Στην παραπάνω έξοδο βλέπουμε:

α) Δεν έχει σχέση με την ερώτησή σου βέβαια αλλά ο scheduler του λειτουργικού μπορεί να επιλέξει να εκτελέσει τα νήματα με όποια σειρά κρίνει και όχι με την σειρά που τα ξεκίνησες.

β) Όλες οι περιπτώσεις κλειδώματος επέστρεψαν 0 δηλαδή επέτυχαν και πιο σημαντικά δεν υπάρχει πουθενά μήνυμα κλειδώματος χωρίς να προηγείται μήνυμα ξεκλειδώματος αυτό δηλαδή που είπαμε ότι μπλοκάρει το νήμα και δεν εκτελείται.

Αντί τώρα να μπλέξουμε με attributes και το παραπάνω πινακάκι για να δούμε undefined behavior, μπορούμε να δοκιμάσουμε την συνάρτηση trylock η οποία δεν μπλοκάρει οπότε θα μας δώσει στο περίπου το ίδιο αποτέλεσμα.

void *thread_func(void *val)                                                    
{                                                                               
    struct thread_s *thread = val;                                              
    int err = 1;                                                                
                                                                                
    while ((err = pthread_mutex_trylock(&lock)) != 0) {                         
            printf("Locking returned %d in thread %d\n", err, thread->i);       
    }                                                                           
    printf("Running thread %d\n", thread->i);                                   
    err = pthread_mutex_unlock(&lock);                                          
    printf("Unlocking returned %d in thread %d\n", err, thread->i);             
                                                                                
    thread->fact_res = fact(thread->i);                                         
                                                                                
    return NULL;                                                                
}       

Όπως βλέπεις, άλλαξα λίγο τον κώδικα και έβαλα με while να προσπαθεί να κλειδώσει συνέχεια. Αυτό θα έχει ως αποτέλεσμα την ίδια συμπεριφορά με πριν που τρέξαμε την lock. Ας δούμε τώρα την έξοδο:

% ./tmp |uniq -c
      1 Locking returned 0 in thread 0
      1 Running thread 0
      1 Unlocking returned 0 in thread 0
      1 Locking returned 0 in thread 3
      1 Running thread 3
      1 Unlocking returned 0 in thread 3
      1 Locking returned 16 in thread 1
      1 Locking returned 0 in thread 1
     11 Locking returned 16 in thread 2
      1 Running thread 1
      1 Locking returned 16 in thread 2
      1 Unlocking returned 0 in thread 1
      1 Locking returned 0 in thread 2
      1 Running thread 2
      1 Unlocking returned 0 in thread 2
      1 Joined with finished thread 0: Factorial(0) = 1
      1 Joined with finished thread 1: Factorial(1) = 1
      1 Joined with finished thread 2: Factorial(2) = 2
      1 Joined with finished thread 3: Factorial(3) = 6

Για να μην έχουμε άπειρα μηνύματα, χρησιμοποίησα την uniq η οποία μας εμφανίζει πόσες φορές τυπώθηκε στην σειρά το ίδιο πράγμα. Όπως διαβάζεις, κάποιες προσπάθειες κλειδώματος επέστρεψαν κωδικό 16 ο οποίος σύμφωνα με τον errno (σε linux είναι στο /usr/include/asm-generic/errno-base.h) είναι ο EBUSY δηλαδή ακριβώς ότι λέει η manpage ότι θα γίνει όταν το lock είναι κλειδωμένο. Το νήμα 2 έκανε 11 προσπάθειες κλειδώματος χωρίς να πετύχει κλείδωμα.

Αν δεν είχαμε βάλει το while για να προσπαθεί ξανά και ξανά, μετά την προσπάθεια κλειδώματος που απέτυχε ο κώδικας θα συνεχιζόταν και ενδεχομένως θα γ..ταν ο δίας. Εφόσον το πρόγραμμά σου παίζει σωστά, δοκίμασε να αλλάξεις όλες τις περιπτώσεις lock σε trylock και δες τι αποτέλεσμα θα κάνει

Επεξ/σία 5 Σεπτεμβρίου 2018 από imitheos

[sir ImPeCaBlE]

Είναι μέσα στο quote το μνμ σου . Περίμενα την απάντησή σου tbh. Thanx, το διαβάζω τώρα.

[dtzgr]

Στο sleeping barber, ο server και ο client πρέπει να lock-αρουν με κάποιο τρόπο (mutex ή ό,τι άλλο) τον έλεγχο της ουράς αναμονής. Μόνο ένας μπορεί να ελέγχει την ουρά και να ενεργεί κάθε φορά. Lock-άρει πριν αρχίσει, και ξε-lock-αρει όταν πάρει την απόφαση και την εκτελέσει (πχ πήρα νέο task και ξεκίνησα επεξεργασία ή έκανα έλεγχο της ουράς και μπήκα στο τέλος της κλπ). ΔΕΝ lockarei ο μπαρμπέρης για να ξελοκάρει ο πελάτης (ή αντίστροφα).

Επομένως, αυτό που λες ότι έφτιαξες ΔΕΝ τεστάρεται με αυτό τον αλγόριθμο.

Επίσης, λες ότι η υλοποίησή σου έχει σκοπό να επιτρέψει σε ένα thread να μπλοκάρει μέχρι ένα άλλο thread να το ξεμπλοκάρει. Αυτό ΔΕΝ γίνεται με απλά mutexes (για το λόγο που ανέφερες: δεν μπορεί ένα thread να ξε-lock-άρει lock που έχει θέσει άλλο thread: αυτός είναι ο σκοπός των mutexes -- mutual exclusion = αμοιβαίος αποκλεισμός = ένας δεσμεύει ένα resource και έχει την εγγύηση ότι άλλος ΔΕΝ μπορεί να το πειράξει μέχρι να το ελευθερώσει ο ίδιος). Αυτό που λες γίνεται με το μηχανισμό pthread_cond_wait(), pthread_cond_signal(), pthread_cond_broadcast().

[sir ImPeCaBlE]

Έπαιξα λίγο με τη trylock (+uniq). Έβαλα και κάποια printf μέσα στις συναρτήσεις της βιβλιοθήκης μου για να φαίνεται πιο καθαρά τι γίνεται. Good stuff. Φάνηκε το ub άμεσα. Μετά άλλαξα και το attribute σε "ERRORCHECK" που μου επέστρεψε μήνυμα λάθους 1 = EPERM = The current thread does not own the mutex.

OK, όπως είπα, μάλλον γίνεται κάποια σύμβαση στο μάθημα αφού άλλο τρόπο να λύσω την άσκηση δε βλέπω.

Tbh λίγο ξενέρωτη η πρώτη μου σκόπιμη επαφή με ub . Τουλάχιστον έγινε η αφορμή να βρω 2-3 άρθρα να διαβάσω για το θέμα.

@dtzgr Δεν είμαι σίγουρος τι εννοείς στις πρώτες 2 παραγράφους ή γιατί μου τα λες (γενικά η συνεννόηση σε όλο το thread ήταν προβληματική :lol:). Μάλλον εννοείς ότι ο κώδικας μου είναι λάθος. Τον αντέγραψα τελείως πρόχειρα από τις διαλέξεις για να δω τι πρόβλημα παίζει να βγάλει το ub των συναρτήσεων μου. Νομίζω έχω καταλάβει σχετικά καλά τα κλασσικά προβλήματα του μαθήματος (sleeping barber, producer/consumer, readers/writers, dining philosophers) και πως λύνονται, τουλάχιστον σε θεωρητικό επίπεδο/ψευδοκώδικα. Δεν ήταν εκεί η απορία μου.

Στη τελευταία παράγραφο πάντως μέσα στη παρένθεση νομίζω το εξήγησες πολύ κομψά. 

Οι συναρτήσεις που αναφέρεις χρησιμοποιούνται στα επόμενα set ασκήσεων οπότε θα τις δω.

Επεξ/σία 6 Σεπτεμβρίου 2018 από sir ImPeCaBlE

[dtzgr]

Στις 31/8/2018 στις 11:10 ΜΜ, sir ImPeCaBlE είπε

Αυτό που καταλαβαίνω είναι ότι το thread του barber κλειδώνει το mutex του sleep_sem (όταν δεν υπάρχει πελάτης διαθέσιμος) και το ξεκλειδώνει το πρώτο thread customer.

Αυτό προσπάθησα να σου εξηγήσω. Δεν το έχεις καταλάβει σωστά.

[sir ImPeCaBlE]

Νομίζω θα ξεκινήσουμε πάλι να μπερδευόμαστε. Ειλικρινά, thanx για τη προσπάθεια αλλά νομίζω είμαι ΟΚ πλέον. 

[_Gikoskos_]

Στις 31/8/2018 στις 11:10 ΜΜ, sir ImPeCaBlE είπε

ζητάει να υλοποιήσουμε συναρτήσεις up(binary semaphore) και down(binary semaphore) χρησιμοποιώντας της συναρτήσεις της pthread mutex_init,  mutex_lock και mutex_unlock

Υλοποίηση δυαδικού σηματοφόρου μόνο με mutex, αναγκαστικά θα είναι με ενεργή αναμονή. Θα χρησιμοποιηθεί μόνο ένα mutex για τον αμοιβαίο αποκλεισμό του μετρητή. Άρα εδώ

Στις 31/8/2018 στις 11:10 ΜΜ, sir ImPeCaBlE είπε

Χονδρικά ένα struct με 2 mutex και ένα int. Στο int κρατάω τη τιμή του σηματοφόρου (0 ή 1), ένα mutex για τη προστασία της τιμής και ένα ακόμα για να κάνω μπλοκάρω το thread. 

φαίνεται ότι έχεις λάθος στην υλοποίηση. Δεν χρειάζεσαι ούτε 2 mutex ούτε trylock. Χονδρικά ο ψευδοκώδικας για τα up/down πρέπει να είναι έτσι:

struct binsem {
  int cnt;
  mutex mtx;
};

down(binsem *bsem){
  while (1) {
    lock(bsem->mtx);

    if (bsem->cnt > 0) {
      
      bsem->cnt--;
      unlock(bsem->mtx);
      break;

    }

    unlock(bsem->mtx);
  }
}

up(binsem *bsem){
  lock(bsem->mtx);

  if (bsem->cnt <= 0) {
    bsem->cnt++;
  }

  unlock(bsem->mtx);
}