Алгоритм сортировки пузырьков с использованием семафоров

Question

Мне был задан вопрос о создании соответствующих семафоров и использовании команд signal и wait соответственно, чтобы сделать сортировку корректной. Я получил следующий код скелета

bubble.cpp

#include <iostream> 
#include <sched.h> 
#include <time.h> 
#include <pthread.h> 
#include "sem.h" 
#define NUM_CELLS 32 

using namespace std; 

extern sim_semaphore create_sim_sem(int) ; 
extern void wait_sem (sim_semaphore) ; 
extern void signal_sem (sim_semaphore) ; 

     /* When debugging, we need to use this lock to get 
     intelligible printouts of what the various threads are 
     doing. Warning: Don't change how this is done. 
     If you insist on changing it, you need to have 
     thought a WHOLE lot about the consequences. */ 

pthread_mutex_t stdoutLock ; 

    /* Here declare whatever semaphores, flags, counters, and 
     so forth, that you want to use for synchronization. Variables 
     declared here will be visible to (shared by) all 
     the threads in the task. */ 




     /* This is the array that will be filled and then sorted by 
     a group of child threads. */ 

int cell[NUM_CELLS] ; 

    /* These are global variable to represent threads created dynamically. */ 
pthread_t thr[NUM_CELLS] ; 

    /* This is included to facilitate adding random delays in the code -- as a 
     debugging aid. */ 
extern long random(void); 

    /* This can be changed to 1, but diagnostic output will probably 
     seem excessive. */ 
int checking = 0 ; 

    /* A data type - a struct with an int field to represent a thread ID. */ 
struct threadIdType 
{ 
    int id ; 
}; 

/* ################################################## */ 
/*       init      */ 
/* ################################################## */ 
void init() 
{ 
     /* This code initializes special lock for screen output. 
     Just leave this alone. */ 
    if (0!=pthread_mutex_init(&stdoutLock, NULL)) 
    { cout << "MUTEX INITIALIZATION FAILURE!" << endl ; 
    exit(-1) ;} 

    /* Here insert the code you want to intialize semaphores, flags, counters, 
     and so forth. */ 








     /* This initializes a random number generator */ 
    srandom(time((time_t *) 0)); 

} 

/* ################################################## */ 
/*      child      */ 
/* ################################################## */ 
void * child(void * idPtr) 
{ 
    int m_delay, j ; 

     /* This is just a change of data type for convenience. 
      Now 'me' is the number of the child. Children have 
      numbers from 1 to 31=NUM_CELLS-1. */ 
    int me = ((threadIdType *) (idPtr))->id, temp ; 
    do 
    { 
     /* Put entry code below here. */ 



     /* This next segment of code is 'critical' because TWO child threads 
     can access most of the cells. */ 

    if (cell[me-1] > cell[me])  
    { 
     /* Start the swap of the cell values. */ 
     temp = cell[me-1] ; 
     cell[me-1] = cell[me] ; 

      /* I inserted delay code here below to magnify the chances 
       that child threads will interfere with each other. 
       It's a "stress test" -- if the synchronization code 
       the student puts in the program is good, the delays 
       won't cause incorrect results. On the other hand, 
       if the student's code is flawed, the delay code below may 
       increase the likelihood that the program will output 
       incorrect results. Leave this here. */ 
     m_delay = (int) random()%100 ; 
     for (j=0; j<m_delay; j++) sched_yield(); 

      /* Finish up with the swap. */ 
     cell[me] = temp ; 
    } 

     /* Put exit code below here. */ 



    } while (true) ; 

    pthread_exit ((void *)0) ; 
} 

/* ################################################## */ 
/*      mother      */ 
/* ################################################## */ 

/* The mother spawns a given number of children and then waits 
    for them all to finish. */ 

void mother() 
{ 
    int i; 

     /* This is a pointer to a struct that contains an int 
     field - it is a convenient data type to use as the 
     parameter to the child function. */ 
    threadIdType * idPtr ; 

    for (i = 1; i < NUM_CELLS ; i++) 
    { 
     /* Mother forks a child and detaches it - she will 
      not join it. In other words, she will not block, 
      waiting for it to exit. */ 
    idPtr = new threadIdType ; 

     /* This records the current index as this child's ID */ 
    idPtr->id = i ; 

     /* The call below is what actually creates the child 
     thread and passes a pointer to the struct 'idPtr' as 
     the parameter to the child function. */ 

    if (0!=pthread_create(&thr[i], NULL, child, (void *) idPtr)) 
    { cout << "THREAD CREATION FAILURE!" << endl ; 
     exit(-1) ; } 

    if (0!=pthread_detach(thr[i])) 
    { cout << "THREAD DETACHMENT FAILURE!" << endl ; 
     exit(-1) ;} 
    } 

    bool sorted ; 
    int m_delay, j; 

    /* The code below can be used to check to see if the 
     list is sorted. However, you can't leave it just as it 
     is. When the mother checks the condition 
      cell[i-1] > cell[i] 
     she is accessing memory that she shares with 
     one or two of the child threads, and the child threads 
     could be writing that memory concurrently, so you need to 
     add entry and exit code that synchronizes the 
     mother with the children. 

     You can try to think of an algorithm different from the 
     one below, if you want. It's possible for 
     the child processes to figure out collectively 
     whether the list is sorted. */ 

    do 
    { 
       /* You can insert random delays like the 
        one below where you want - to vary 
        timing. */ 
     /* 
      m_delay = (int) random()%100 ; 
      for (j=0; j<m_delay; j++) sched_yield(); 
     */ 

     /* MOTHER WALKS UP THE ARRAY, CHECKING */ 
    sorted = true ; 

     /* You may need to add some entry code here. */ 

    for (i=1; i<NUM_CELLS; i++) 
    { 
     /* You may need to add some entry code here. */ 

     if (cell[i-1] > cell[i]) sorted = false ; 

     /* You may need to add some exit code here. */ 

    } 
     /* You may need to add some exit code here. */ 

    } while (!sorted) ; 

     /* This code prints the array - which should be sorted now. */ 
    for (i=0; i<NUM_CELLS; i++) cout << cell[i] << endl ; 
} 

/* ################################################## */ 
/*       main      */ 
/* ################################################## */ 

int main() 
{ 
    /* This calls the function that performs initializations. */ 
    init(); 
    int idx ; 
     /* Read the (unsorted) input into the array */ 
    for (idx=0; idx<NUM_CELLS; idx++) cin >> cell[idx] ; 
     /* Echo the (unsorted) input to the screen. */ 
    for (idx=0; idx<NUM_CELLS; idx++) cout << cell[idx] 
    << endl ; 
    cout << endl ; 

     /* Execute the mother() function, which creates the 
      child threads that sort the list. */ 
    mother(); 
    return 0 ; 
} 

Я работал немного с семафоры и раньше, но я до сих пор совершенно новой концепции и, возможно, потребуется немного больше руководства.

Я обязан создавать глобальные переменные семафора, я сделал что-то вроде этого раньше, например:

sim_semaphore empty[i] ;sim_semaphore full[i] ;

Могу ли я снова использовать ту же логику? Значение, когда ячейка имеет значение (aka is full) и меняет местами, я бы просто использовал команды signal/wait соответственно? Могу ли я решить это, используя только два разных семафора?

Далее я бы инициализировать их внутри init(), в последний раз, когда я это сделал, я использовал для цикла, например:

for (index=0; index<numTrivets; index++) full[index] = create_sim_sem(0) ;

Это самый эффективный способ сделать это снова?

Наконец, где он говорит, что мне нужен вход и выход, код, я думал об использовании решения Петерсона инициализации boolean flag и установке flag = 1 для первого прохода и обратно flag = 0, когда он закончит. Тем не менее, я пришел к выводу, что это не самый «правильный» способ решить эту программу. Что я должен сделать вместо этого?

Спасибо всем, кто положил время на попытку помочь мне! Если у вас есть какие-либо вопросы или разъяснения, пожалуйста, не стесняйтесь спрашивать меня, я сделаю все возможное, чтобы облегчить мне помощь.

Я рисую мои примеры из моей последней программы, которая здесь: Indexing into an array of semaphores

Я Эталонный раствор Петерсона, который можно найти здесь: http://mathbits.com/MathBits/CompSci/Arrays/Bubble.htm

Answer 1

Для того, чтобы ответить на мой вопрос, решение было проще, чем я думал. Я просто нужен один массив семафоров в начале,

sim_semaphore semArray[NUM_CELLS] ;

, а затем инициализируется, как указано в моем вопросе.

for (index=0; index<NUM_CELLS; index++) semArray[index] = create_sim_sem(1) ;

работа ребенок просто состоял из signal и wait и цели состоит в том, чтобы иметь возможность сразу поменять места данных без необходимости ждать один на один раз. Вы можете сделать это, если ребенок ждет на i-1 и i до того, как произойдет фактический алгоритм подкачки, и сигнал по i-1 и i после алгоритма.

Работа матери заключается в том, чтобы существенно спуститься по линии данных и дважды проверить, что ребенок выполнил свою работу.Вы можете сделать это, создав for-loop до и после уже введенного for-loop. После этого все, что вам нужно сделать, это wait на i и signal на i после. Это всего лишь одно решение, но есть более сложные решения, но это, вероятно, самый простой.